summaryrefslogtreecommitdiff
path: root/src/base
diff options
context:
space:
mode:
authorGabe Black <gabeblack@google.com>2017-10-18 19:55:59 -0700
committerNikos Nikoleris <nikos.nikoleris@arm.com>2018-06-19 14:24:25 +0000
commitc31af7e89b89fbfecfad9634b2de8ec613f6fde3 (patch)
tree0b324981ef987ffe567932350abe30528f027231 /src/base
parent683f411dcab4bb2275902f79f32eeee7c2e0b00a (diff)
downloadgem5-c31af7e89b89fbfecfad9634b2de8ec613f6fde3.tar.xz
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>
Diffstat (limited to 'src/base')
-rw-r--r--src/base/addr_range_map.hh53
1 files changed, 52 insertions, 1 deletions
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 5c627bef5..417d66346 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 @@ class AddrRangeMap
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 @@ class AddrRangeMap
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 @@ class AddrRangeMap
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 @@ class AddrRangeMap
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 @@ class AddrRangeMap
}
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__