base: Build caching into the AddrRangeMap class
Rather than have each consumer of the AddrRangeMap implement caching
lookups on their own, this change adds a centralized mechanism to the
AddrRangeMap class itself.
Some benefits of this approach are that the cache handles deleted
entries correctly/automatically, the cache is maintained by
adding/removing entries from a linked list rather than moving elements
in an array and checking valid bits, and it's easy to enable in places
which might otherwise not bother with caching. The amount of caching
is tunable to balance overhead with improved lookup performance.
Change-Id: Ic25997e23de4eea501e47f039bb52ed0502c58d2
Reviewed-on: https://gem5-review.googlesource.com/5242
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 5c627be..417d663 100644
--- a/src/base/addr_range_map.hh
+++ b/src/base/addr_range_map.hh
@@ -54,7 +54,7 @@
* address decoding. The value stored is a template type and can be
* e.g. a port identifier, or a pointer.
*/
-template <typename V>
+template <typename V, int max_cache_size=0>
class AddrRangeMap
{
private:
@@ -124,18 +124,23 @@
void
erase(iterator p)
{
+ cache.remove(p);
tree.erase(p);
}
void
erase(iterator p, iterator q)
{
+ for (auto it = p; it != q; it++) {
+ cache.remove(p);
+ }
tree.erase(p,q);
}
void
clear()
{
+ cache.erase(cache.begin(), cache.end());
tree.erase(tree.begin(), tree.end());
}
@@ -177,6 +182,31 @@
private:
/**
+ * Add an address range map entry to the cache.
+ *
+ * @param it Iterator to the entry in the address range map
+ */
+ void
+ addNewEntryToCache(const_iterator it) const
+ {
+ if (max_cache_size != 0) {
+ // If there's a cache, add this element to it.
+ if (cache.size() >= max_cache_size) {
+ // If the cache is full, move the last element to the
+ // front and overwrite it with the new value. This
+ // avoids creating or destroying elements of the list.
+ auto last = cache.end();
+ last--;
+ *last = it;
+ if (max_cache_size > 1)
+ cache.splice(cache.begin(), cache, last);
+ } else {
+ cache.push_front(it);
+ }
+ }
+ }
+
+ /**
* Find entry that satisfies a condition on an address range
*
* Searches through the ranges in the address map and returns an
@@ -190,8 +220,20 @@
const_iterator
find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const
{
+ // Check the cache first
+ for (auto c = cache.begin(); c != cache.end(); c++) {
+ auto it = *c;
+ if (cond(it->first)) {
+ // If this entry matches, promote it to the front
+ // of the cache and return it.
+ cache.splice(cache.begin(), cache, c);
+ return it;
+ }
+ }
+
const_iterator next = tree.upper_bound(r);
if (next != end() && cond(next->first)) {
+ addNewEntryToCache(next);
return next;
}
if (next == begin())
@@ -202,6 +244,7 @@
do {
i = next;
if (cond(i->first)) {
+ addNewEntryToCache(i);
return i;
}
// Keep looking if the next range merges with the current one.
@@ -212,6 +255,14 @@
}
RangeMap tree;
+
+ /**
+ * A list of iterator that correspond to the max_cache_size most
+ * recently used entries in the address range map. This mainly
+ * used to optimize lookups. The elements in the list should
+ * always be valid iterators of the tree.
+ */
+ mutable std::list<const_iterator> cache;
};
#endif //__BASE_ADDR_RANGE_MAP_HH__
