ClpMap.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2020 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 "base/Optional.h"
13 #include "mem/PoolingAllocator.h"
14 #include "SquidMath.h"
15 #include "SquidTime.h"
16 
17 #include <functional>
18 #include <limits>
19 #include <list>
20 #include <unordered_map>
21 
22 template<class Value>
23 uint64_t
24 DefaultMemoryUsage(const Value &e)
25 {
26  return sizeof(e);
27 }
28 
39 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &) = DefaultMemoryUsage>
40 class ClpMap
41 {
42 public:
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 
59  const Value *get(const Key &);
60 
64  bool add(const Key &, const Value &, Ttl);
65 
67  bool add(const Key &key, const Value &v) { return add(key, v, defaultTtl_); }
68 
70  void del(const Key &);
71 
73  void setMemLimit(uint64_t newLimit);
74 
76  uint64_t memLimit() const { return memLimit_; }
77 
79  uint64_t freeMem() const { return memLimit() - memoryUsed(); }
80 
82  uint64_t memoryUsed() const { return memUsed_; }
83 
85  size_t entries() const { return entries_.size(); }
86 
87 private:
89  class Entry
90  {
91  public:
92  Entry(const Key &, const Value &, const Ttl);
93 
95  bool expired() const { return expires < squid_curtime; }
96 
97  public:
98  Key key;
99  Value value;
100  time_t expires = 0;
101  uint64_t memCounted = 0;
102  };
103 
105  using Entries = std::list<Entry, PoolingAllocator<Entry> >;
106  using EntriesIterator = typename Entries::iterator;
107 
108  using IndexItem = std::pair<Key, EntriesIterator>;
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 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 
121 
124 
127 
129  uint64_t memLimit_ = 0;
130 
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
146 {
147  if (memUsed_ > newLimit)
148  trim(memLimit_ - newLimit);
149  memLimit_ = newLimit;
150 }
151 
153 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
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 *
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 &)>
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 Sum<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  entries_.emplace_front(key, v, ttl); // TODO: After C++17 migration, use the return value
228  index_.emplace(key, entries_.begin());
229 
230  entries_.begin()->memCounted = wantSpace;
231  memUsed_ += wantSpace;
232  assert(memUsed_ >= wantSpace); // no overflows
233  return true;
234 }
235 
237 template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
238 void
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
256 {
257  const auto i = find(key);
258  if (i != index_.end())
259  erase(i);
260 }
261 
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(Sum(squid_curtime, ttl).value_or(std::numeric_limits<time_t>::max()))
281 {
282 }
283 
284 #endif /* SQUID__SRC_BASE_CLPMAP_H */
uint64_t freeMem() const
The free space of the map.
Definition: ClpMap.h:79
Entry(const Key &, const Value &, const Ttl)
Definition: ClpMap.h:277
ClpMap & operator=(const ClpMap &)=delete
typename Index::iterator IndexIterator
Definition: ClpMap.h:111
std::pair< Key, EntriesIterator > IndexItem
Definition: ClpMap.h:108
int const char int
Definition: stub_libmem.cc:75
ClpMap(const uint64_t capacity)
Definition: ClpMap.h:46
const A & max(A const &lhs, A const &rhs)
uint64_t memCounted
memory accounted for this entry in our ClpMap
Definition: ClpMap.h:101
uint64_t memLimit() const
The memory capacity for the map.
Definition: ClpMap.h:76
(limited) std::optional replacement (until we upgrade to C++17)
Definition: forward.h:19
~ClpMap()=default
const Value * get(const Key &)
Definition: ClpMap.h:175
uint64_t memLimit_
the maximum memory we are allowed to use for all cached entries
Definition: ClpMap.h:129
void trim(uint64_t wantSpace)
purges entries to make free memory large enough to fit wantSpace bytes
Definition: ClpMap.h:265
Ttl defaultTtl_
entry TTL to use if none provided to add()
Definition: ClpMap.h:126
Definition: ClpMap.h:40
Optional< T > Sum(const T a, const U b)
Definition: SquidMath.h:51
Index index_
entries_ positions indexed by the entry key
Definition: ClpMap.h:123
time_t expires
get() stops returning the entry after this time
Definition: ClpMap.h:100
#define assert(EX)
Definition: assert.h:19
int Ttl
maximum desired entry caching duration (a.k.a. TTL), in seconds
Definition: ClpMap.h:44
void del(const Key &)
Remove the corresponding entry (if any)
Definition: ClpMap.h:255
typename Entries::iterator EntriesIterator
Definition: ClpMap.h:106
void const char int sz
Definition: stub_cbdata.cc:16
size_t entries() const
The number of currently stored entries, including expired ones.
Definition: ClpMap.h:85
time_t squid_curtime
Definition: stub_time.cc:17
Entries entries_
cached entries, including expired ones, in LRU order
Definition: ClpMap.h:120
bool add(const Key &, const Value &, Ttl)
Definition: ClpMap.h:207
static Optional< uint64_t > MemoryCountedFor(const Key &, const Value &)
Definition: ClpMap.h:187
std::list< Entry, PoolingAllocator< Entry > > Entries
Entries in LRU order.
Definition: ClpMap.h:105
bool add(const Key &key, const Value &v)
Copy the given value into the map (with the given key and default TTL)
Definition: ClpMap.h:67
void setMemLimit(uint64_t newLimit)
Reset the memory capacity for this map, purging if needed.
Definition: ClpMap.h:145
std::unordered_map< Key, EntriesIterator, std::hash< Key >, std::equal_to< Key >, PoolingAllocator< IndexItem > > Index
key:entry_position mapping for fast entry lookups by key
Definition: ClpMap.h:110
STL Allocator that uses Squid memory pools for memory management.
static const char * trim(char const *s)
Definition: Expression.cc:674
uint64_t memoryUsed() const
The current (approximate) memory usage of the map.
Definition: ClpMap.h:82
bool expired() const
whether the entry is stale
Definition: ClpMap.h:95
uint64_t DefaultMemoryUsage(const Value &e)
Definition: ClpMap.h:24
Key key
the entry search key; see ClpMap::get()
Definition: ClpMap.h:98
uint64_t memUsed_
the total amount of memory we currently use for all cached entries
Definition: ClpMap.h:132
void erase(const IndexIterator &)
removes the cached entry (identified by its index) from the map
Definition: ClpMap.h:239
the keeper of cache entry Key, Value, and caching-related entry metadata
Definition: ClpMap.h:89
IndexIterator find(const Key &)
Definition: ClpMap.h:155
Value value
cached value provided by the map user
Definition: ClpMap.h:99

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors