/*
|
* Copyright (C) 2019 The Android Open Source Project
|
*
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
* you may not use this file except in compliance with the License.
|
* You may obtain a copy of the License at
|
*
|
* http://www.apache.org/licenses/LICENSE-2.0
|
*
|
* Unless required by applicable law or agreed to in writing, software
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
* See the License for the specific language governing permissions and
|
* limitations under the License.
|
*/
|
|
#ifndef ART_LIBARTBASE_BASE_MEMORY_TYPE_TABLE_H_
|
#define ART_LIBARTBASE_BASE_MEMORY_TYPE_TABLE_H_
|
|
#include <iostream>
|
#include <map>
|
#include <vector>
|
|
#include <android-base/macros.h> // For DISALLOW_COPY_AND_ASSIGN
|
#include <android-base/logging.h> // For DCHECK macros
|
|
namespace art {
|
|
// Class representing a memory range together with type attribute.
|
template <typename T>
|
class MemoryTypeRange final {
|
public:
|
MemoryTypeRange(uintptr_t start, uintptr_t limit, const T& type)
|
: start_(start), limit_(limit), type_(type) {}
|
MemoryTypeRange() : start_(0), limit_(0), type_() {}
|
MemoryTypeRange(MemoryTypeRange&& other) = default;
|
MemoryTypeRange(const MemoryTypeRange& other) = default;
|
MemoryTypeRange& operator=(const MemoryTypeRange& other) = default;
|
|
uintptr_t Start() const {
|
DCHECK(IsValid());
|
return start_;
|
}
|
|
uintptr_t Limit() const {
|
DCHECK(IsValid());
|
return limit_;
|
}
|
|
uintptr_t Size() const { return Limit() - Start(); }
|
|
const T& Type() const { return type_; }
|
|
bool IsValid() const { return start_ <= limit_; }
|
|
bool Contains(uintptr_t address) const {
|
return address >= Start() && address < Limit();
|
}
|
|
bool Overlaps(const MemoryTypeRange& other) const {
|
bool disjoint = Limit() <= other.Start() || Start() >= other.Limit();
|
return !disjoint;
|
}
|
|
bool Adjoins(const MemoryTypeRange& other) const {
|
return other.Start() == Limit() || other.Limit() == Start();
|
}
|
|
bool CombinableWith(const MemoryTypeRange& other) const {
|
return Type() == other.Type() && Adjoins(other);
|
}
|
|
private:
|
uintptr_t start_;
|
uintptr_t limit_;
|
T type_;
|
};
|
|
// Class representing a table of memory ranges.
|
template <typename T>
|
class MemoryTypeTable final {
|
public:
|
// Class used to construct and populate MemoryTypeTable instances.
|
class Builder;
|
|
MemoryTypeTable() {}
|
|
MemoryTypeTable(MemoryTypeTable&& table) : ranges_(std::move(table.ranges_)) {}
|
|
MemoryTypeTable& operator=(MemoryTypeTable&& table) {
|
ranges_ = std::move(table.ranges_);
|
return *this;
|
}
|
|
// Find the range containing |address|.
|
// Returns a pointer to a range on success, nullptr otherwise.
|
const MemoryTypeRange<T>* Lookup(uintptr_t address) const {
|
int last = static_cast<int>(ranges_.size()) - 1;
|
for (int l = 0, r = last; l <= r;) {
|
int m = l + (r - l) / 2;
|
if (address < ranges_[m].Start()) {
|
r = m - 1;
|
} else if (address >= ranges_[m].Limit()) {
|
l = m + 1;
|
} else {
|
DCHECK(ranges_[m].Contains(address))
|
<< reinterpret_cast<void*>(address) << " " << ranges_[m];
|
return &ranges_[m];
|
}
|
}
|
return nullptr;
|
}
|
|
size_t Size() const { return ranges_.size(); }
|
|
void Print(std::ostream& os) const {
|
for (const auto& range : ranges_) {
|
os << range << std::endl;
|
}
|
}
|
|
private:
|
std::vector<MemoryTypeRange<T>> ranges_;
|
|
DISALLOW_COPY_AND_ASSIGN(MemoryTypeTable);
|
};
|
|
// Class for building MemoryTypeTable instances. Supports
|
// adding ranges and looking up ranges.
|
template <typename T>
|
class MemoryTypeTable<T>::Builder final {
|
public:
|
Builder() {}
|
|
// Adds a range if it is valid and doesn't overlap with existing ranges. If the range adjoins
|
// with an existing range, then the ranges are merged.
|
//
|
// Overlapping ranges and ranges of zero size are not supported.
|
//
|
// Returns true on success, false otherwise.
|
inline bool Add(const MemoryTypeRange<T>& region);
|
|
// Find the range containing |address|.
|
// Returns a pointer to a range on success, nullptr otherwise.
|
inline const MemoryTypeRange<T>* Lookup(uintptr_t address) const;
|
|
// Returns number of unique ranges.
|
inline size_t Size() const { return ranges_.size(); }
|
|
// Generates a MemoryTypeTable for added ranges.
|
MemoryTypeTable Build() const {
|
MemoryTypeTable table;
|
for (const auto& it : ranges_) {
|
table.ranges_.push_back(it.second);
|
}
|
return table;
|
}
|
|
private:
|
std::map<uintptr_t, MemoryTypeRange<T>> ranges_;
|
|
DISALLOW_COPY_AND_ASSIGN(Builder);
|
};
|
|
template <typename T>
|
bool operator==(const MemoryTypeRange<T>& lhs, const MemoryTypeRange<T>& rhs) {
|
return (lhs.Start() == rhs.Start() && lhs.Limit() == rhs.Limit() && lhs.Type() == rhs.Type());
|
}
|
|
template <typename T>
|
bool operator!=(const MemoryTypeRange<T>& lhs, const MemoryTypeRange<T>& rhs) {
|
return !(lhs == rhs);
|
}
|
|
template <typename T>
|
std::ostream& operator<<(std::ostream& os, const MemoryTypeRange<T>& range) {
|
os << reinterpret_cast<void*>(range.Start())
|
<< '-'
|
<< reinterpret_cast<void*>(range.Limit())
|
<< ' '
|
<< range.Type();
|
return os;
|
}
|
|
template <typename T>
|
std::ostream& operator<<(std::ostream& os, const MemoryTypeTable<T>& table) {
|
table.Print(os);
|
return os;
|
}
|
|
template <typename T>
|
bool MemoryTypeTable<T>::Builder::Add(const MemoryTypeRange<T>& range) {
|
if (UNLIKELY(!range.IsValid() || range.Size() == 0u)) {
|
return false;
|
}
|
|
typename std::map<uintptr_t, MemoryTypeRange<T>>::iterator pred, succ;
|
|
// Find an iterator for the next element in the ranges.
|
succ = ranges_.lower_bound(range.Limit());
|
|
// Find an iterator for a predecessor element.
|
if (succ == ranges_.begin()) {
|
// No predecessor element if the successor is at the beginning of ranges.
|
pred = ranges_.end();
|
} else if (succ != ranges_.end()) {
|
// Predecessor is element before successor.
|
pred = std::prev(succ);
|
} else {
|
// Predecessor is the last element in a non-empty map when there is no successor.
|
pred = ranges_.find(ranges_.rbegin()->first);
|
}
|
|
// Invalidate |succ| if it cannot be combined with |range|.
|
if (succ != ranges_.end()) {
|
DCHECK_GE(succ->second.Limit(), range.Start());
|
if (range.Overlaps(succ->second)) {
|
return false;
|
}
|
if (!range.CombinableWith(succ->second)) {
|
succ = ranges_.end();
|
}
|
}
|
|
// Invalidate |pred| if it cannot be combined with |range|.
|
if (pred != ranges_.end()) {
|
if (range.Overlaps(pred->second)) {
|
return false;
|
}
|
if (!range.CombinableWith(pred->second)) {
|
pred = ranges_.end();
|
}
|
}
|
|
if (pred == ranges_.end()) {
|
if (succ == ranges_.end()) {
|
// |pred| is invalid, |succ| is invalid.
|
// No compatible neighbors for merging.
|
DCHECK(ranges_.find(range.Limit()) == ranges_.end());
|
ranges_[range.Limit()] = range;
|
} else {
|
// |pred| is invalid, |succ| is valid. Merge into |succ|.
|
const uintptr_t limit = succ->second.Limit();
|
DCHECK_GT(limit, range.Limit());
|
ranges_.erase(succ);
|
ranges_[limit] = MemoryTypeRange<T>(range.Start(), limit, range.Type());
|
}
|
} else {
|
if (succ == ranges_.end()) {
|
// |pred| is valid, |succ| is invalid. Merge into |pred|.
|
const uintptr_t start = pred->second.Start();
|
const uintptr_t limit = range.Limit();
|
DCHECK_LT(start, range.Start());
|
DCHECK_GT(limit, pred->second.Limit());
|
ranges_.erase(pred);
|
ranges_[limit] = MemoryTypeRange<T>(start, limit, range.Type());
|
} else {
|
// |pred| is valid, |succ| is valid. Merge between |pred| and |succ|.
|
DCHECK_LT(pred->second.Start(), range.Start());
|
DCHECK_GT(succ->second.Limit(), range.Limit());
|
const uintptr_t start = pred->second.Start();
|
const uintptr_t limit = succ->second.Limit();
|
ranges_.erase(pred, ++succ);
|
ranges_[limit] = MemoryTypeRange<T>(start, limit, range.Type());
|
}
|
}
|
return true;
|
}
|
|
template <typename T>
|
const MemoryTypeRange<T>* MemoryTypeTable<T>::Builder::Lookup(uintptr_t address) const {
|
auto it = ranges_.upper_bound(address);
|
if (it != ranges_.end() && it->second.Contains(address)) {
|
return &it->second;
|
} else {
|
return nullptr;
|
}
|
}
|
|
} // namespace art
|
|
#endif // ART_LIBARTBASE_BASE_MEMORY_TYPE_TABLE_H_
|
