src/base/ClpMap.h

   1 /*
   2  * Copyright (C) 1996-2023 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #ifndef SQUID__SRC_BASE_CLPMAP_H
  10 #define SQUID__SRC_BASE_CLPMAP_H
  11
  12 #include "mem/PoolingAllocator.h"
  13 #include "SquidMath.h"
  14 #include "time/gadgets.h"
  15
  16 #include <functional>
  17 #include <limits>
  18 #include <list>
  19 #include <optional>
  20 #include <unordered_map>
  21
  22 template<class Value>
  23 uint64_t
  24 DefaultMemoryUsage(const Value &e)
  25 {
  26     return sizeof(e);
  27 }
  28
  29 /// An in-memory associative container enforcing three primary caching policies:
  30 /// * Capacity: The memory used by cached entries has a configurable limit;
  31 /// * Lifetime: Entries are hidden (and may be deleted) after their TTL expires;
  32 /// * Priority: Capacity victims are purged in LRU order.
  33 /// Individual cache entry operations have average constant-time complexity.
  34 ///
  35 /// Value must meet STL requirements of Erasable and EmplaceConstructible.
  36 /// Key must come with std::hash<Key> and std::equal_to<Key> instantiations.
  37 /// Key::length() must return the number of memory bytes in use by the key.
  38 /// MemoryUsedBy() must return the number of memory bytes in use by the value.
  39 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &) = DefaultMemoryUsage>
  40 class ClpMap
  41 {
  42 public:
  43     /// maximum desired entry caching duration (a.k.a. TTL), in seconds
  44     using Ttl = int;
  45
  46     explicit ClpMap(const uint64_t capacity) { setMemLimit(capacity); }
  47     ClpMap(uint64_t capacity, Ttl defaultTtl);
  48     ~ClpMap() = default;
  49
  50     // copying disabled because it may be expensive for large maps
  51     // moving (implicitly) disabled for simplicity sake
  52     ClpMap(const ClpMap &) = delete;
  53     ClpMap &operator =(const ClpMap &) = delete;
  54
  55     /// \return a pointer to a fresh cached value (or nil)
  56     /// The underlying value is owned by the map, so the pointer may be
  57     /// invalidated by any non-constant method call, including another get().
  58     /// Also moves the found entry to the end of the purging queue.
  59     const Value *get(const Key &);
  60
  61     /// Copy the given value into the map (with the given key and TTL)
  62     /// \retval true the value was successfully copied into the map
  63     /// \retval false caching was rejected (the map remains unchanged)
  64     bool add(const Key &, const Value &, Ttl);
  65
  66     /// Copy the given value into the map (with the given key and default TTL)
  67     bool add(const Key &key, const Value &v) { return add(key, v, defaultTtl_); }
  68
  69     /// Remove the corresponding entry (if any)
  70     void del(const Key &);
  71
  72     /// Reset the memory capacity for this map, purging if needed
  73     void setMemLimit(uint64_t newLimit);
  74
  75     /// The memory capacity for the map
  76     uint64_t memLimit() const { return memLimit_; }
  77
  78     /// The free space of the map
  79     uint64_t freeMem() const { return memLimit() - memoryUsed(); }
  80
  81     /// The current (approximate) memory usage of the map
  82     uint64_t memoryUsed() const { return memUsed_; }
  83
  84     /// The number of currently stored entries, including expired ones
  85     size_t entries() const { return entries_.size(); }
  86
  87 private:
  88     /// the keeper of cache entry Key, Value, and caching-related entry metadata
  89     class Entry
  90     {
  91     public:
  92         Entry(const Key &, const Value &, const Ttl);
  93
  94         /// whether the entry is stale
  95         bool expired() const { return expires < squid_curtime; }
  96
  97     public:
  98         Key key; ///< the entry search key; see ClpMap::get()
  99         Value value; ///< cached value provided by the map user
 100         time_t expires = 0; ///< get() stops returning the entry after this time
 101         uint64_t memCounted = 0; ///< memory accounted for this entry in our ClpMap
 102     };
 103
 104     /// Entries in LRU order
 105     using Entries = std::list<Entry, PoolingAllocator<Entry> >;
 106     using EntriesIterator = typename Entries::iterator;
 107
 108     using IndexItem = std::pair<const Key, EntriesIterator>;
 109     /// key:entry_position mapping for fast entry lookups by key
 110     using Index = std::unordered_map<Key, EntriesIterator, std::hash<Key>, std::equal_to<Key>, PoolingAllocator<IndexItem> >;
 111     using IndexIterator = typename Index::iterator;
 112
 113     static std::optional<uint64_t> MemoryCountedFor(const Key &, const Value &);
 114
 115     void trim(uint64_t wantSpace);
 116     void erase(const IndexIterator &);
 117     IndexIterator find(const Key &);
 118
 119     /// cached entries, including expired ones, in LRU order
 120     Entries entries_;
 121
 122     /// entries_ positions indexed by the entry key
 123     Index index_;
 124
 125     /// entry TTL to use if none provided to add()
 126     Ttl defaultTtl_ = std::numeric_limits<Ttl>::max();
 127
 128     /// the maximum memory we are allowed to use for all cached entries
 129     uint64_t memLimit_ = 0;
 130
 131     /// the total amount of memory we currently use for all cached entries
 132     uint64_t memUsed_ = 0;
 133 };
 134
 135 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 136 ClpMap<Key, Value, MemoryUsedBy>::ClpMap(const uint64_t capacity, const Ttl defaultTtl):
 137     defaultTtl_(defaultTtl)
 138 {
 139     assert(defaultTtl >= 0);
 140     setMemLimit(capacity);
 141 }
 142
 143 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 144 void
 145 ClpMap<Key, Value, MemoryUsedBy>::setMemLimit(const uint64_t newLimit)
 146 {
 147     if (memUsed_ > newLimit)
 148         trim(memLimit_ - newLimit);
 149     memLimit_ = newLimit;
 150 }
 151
 152 /// \returns the index position of an entry identified by its key (or end())
 153 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 154 typename ClpMap<Key, Value, MemoryUsedBy>::IndexIterator
 155 ClpMap<Key, Value, MemoryUsedBy>::find(const Key &key)
 156 {
 157     const auto i = index_.find(key);
 158     if (i == index_.end())
 159         return i;
 160
 161     const auto entryPosition = i->second;
 162     if (!entryPosition->expired()) {
 163         if (entryPosition != entries_.begin())
 164             entries_.splice(entries_.begin(), entries_, entryPosition);
 165         return i;
 166     }
 167     // else fall through to cleanup
 168
 169     erase(i);
 170     return index_.end();
 171 }
 172
 173 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 174 const Value *
 175 ClpMap<Key, Value, MemoryUsedBy>::get(const Key &key)
 176 {
 177     const auto i = find(key);
 178     if (i != index_.end()) {
 179         const auto &entry = *(i->second);
 180         return &entry.value;
 181     }
 182     return nullptr;
 183 }
 184
 185 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 186 std::optional<uint64_t>
 187 ClpMap<Key, Value, MemoryUsedBy>::MemoryCountedFor(const Key &k, const Value &v)
 188 {
 189     // Both storage and index store keys, but we count keySz once, assuming that
 190     // copying a Key does not consume more memory. This assumption holds for
 191     // Key=SBuf, but, ideally, we should be outsourcing this decision to another
 192     // configurable function, storing each key once, or hard-coding Key=SBuf.
 193     const auto keySz = k.length();
 194
 195     // approximate calculation (e.g., containers store wrappers not value_types)
 196     return NaturalSum<uint64_t>(
 197                keySz,
 198                // storage
 199                sizeof(typename Entries::value_type),
 200                MemoryUsedBy(v),
 201                // index
 202                sizeof(typename Index::value_type));
 203 }
 204
 205 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 206 bool
 207 ClpMap<Key, Value, MemoryUsedBy>::add(const Key &key, const Value &v, const Ttl ttl)
 208 {
 209     // optimization: avoid del() search, MemoryCountedFor() in always-empty maps
 210     if (memLimit() == 0)
 211         return false;
 212
 213     del(key);
 214
 215     if (ttl < 0)
 216         return false; // already expired; will never be returned by get()
 217
 218     const auto memoryRequirements = MemoryCountedFor(key, v);
 219     if (!memoryRequirements)
 220         return false; // cannot even compute memory requirements
 221
 222     const auto wantSpace = memoryRequirements.value();
 223     if (wantSpace > memLimit() || wantSpace == 0) // 0 is 64-bit integer overflow
 224         return false; // will never fit
 225     trim(wantSpace);
 226
 227     auto &addedEntry = entries_.emplace_front(key, v, ttl);
 228     index_.emplace(key, entries_.begin());
 229
 230     addedEntry.memCounted = wantSpace;
 231     memUsed_ += wantSpace;
 232     assert(memUsed_ >= wantSpace); // no overflows
 233     return true;
 234 }
 235
 236 /// removes the cached entry (identified by its index) from the map
 237 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 238 void
 239 ClpMap<Key, Value, MemoryUsedBy>::erase(const IndexIterator &i)
 240 {
 241     assert(i != index_.end());
 242     const auto entryPosition = i->second;
 243
 244     assert(entryPosition != entries_.end());
 245     const auto sz = entryPosition->memCounted;
 246     assert(memUsed_ >= sz);
 247     memUsed_ -= sz;
 248
 249     index_.erase(i); // destroys a "pointer" to our Entry
 250     entries_.erase(entryPosition); // destroys our Entry
 251 }
 252
 253 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 254 void
 255 ClpMap<Key, Value, MemoryUsedBy>::del(const Key &key)
 256 {
 257     const auto i = find(key);
 258     if (i != index_.end())
 259         erase(i);
 260 }
 261
 262 /// purges entries to make free memory large enough to fit wantSpace bytes
 263 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 264 void
 265 ClpMap<Key, Value, MemoryUsedBy>::trim(const uint64_t wantSpace)
 266 {
 267     assert(wantSpace <= memLimit()); // no infinite loops and in-vain trimming
 268     while (freeMem() < wantSpace) {
 269         assert(!entries_.empty());
 270         // TODO: Purge expired entries first. They are useless, but their
 271         // presence may lead to purging potentially useful fresh entries here.
 272         del(entries_.rbegin()->key);
 273     }
 274 }
 275
 276 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
 277 ClpMap<Key, Value, MemoryUsedBy>::Entry::Entry(const Key &aKey, const Value &v, const Ttl ttl) :
 278     key(aKey),
 279     value(v),
 280     expires(0) // reset below
 281 {
 282     SetToNaturalSumOrMax(expires, squid_curtime, ttl);
 283 }
 284
 285 #endif /* SQUID__SRC_BASE_CLPMAP_H */
 286