/*
* 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_