ClpMap.h
Go to the documentation of this file.
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
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
22template<class Value>
23uint64_t
24DefaultMemoryUsage(const Value &e)
25{
26 return sizeof(e);
27}
28
39template <class Key, class Value, uint64_t MemoryUsedBy(const Value &) = DefaultMemoryUsage>
40class ClpMap
41{
42public:
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
87private:
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<const 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 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
121
124
127
129 uint64_t memLimit_ = 0;
130
132 uint64_t memUsed_ = 0;
133};
134
135template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
136ClpMap<Key, Value, MemoryUsedBy>::ClpMap(const uint64_t capacity, const Ttl defaultTtl):
137 defaultTtl_(defaultTtl)
138{
139 assert(defaultTtl >= 0);
140 setMemLimit(capacity);
141}
142
143template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
144void
146{
147 if (memUsed_ > newLimit)
148 trim(memLimit_ - newLimit);
149 memLimit_ = newLimit;
150}
151
153template <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
173template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
174const 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
185template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
186std::optional<uint64_t>
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
205template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
206bool
207ClpMap<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
237template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
238void
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
253template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
254void
256{
257 const auto i = find(key);
258 if (i != index_.end())
259 erase(i);
260}
261
263template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
264void
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
276template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
277ClpMap<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{
283}
284
285#endif /* SQUID__SRC_BASE_CLPMAP_H */
286
uint64_t DefaultMemoryUsage(const Value &e)
Definition: ClpMap.h:24
static char const * trim(char const *s)
Definition: Expression.cc:674
time_t squid_curtime
Definition: stub_libtime.cc:20
S SetToNaturalSumOrMax(S &var, const Args... args)
Definition: SquidMath.h:176
#define assert(EX)
Definition: assert.h:17
the keeper of cache entry Key, Value, and caching-related entry metadata
Definition: ClpMap.h:90
bool expired() const
whether the entry is stale
Definition: ClpMap.h:95
Value value
cached value provided by the map user
Definition: ClpMap.h:99
time_t expires
get() stops returning the entry after this time
Definition: ClpMap.h:100
uint64_t memCounted
memory accounted for this entry in our ClpMap
Definition: ClpMap.h:101
Key key
the entry search key; see ClpMap::get()
Definition: ClpMap.h:98
Entry(const Key &, const Value &, const Ttl)
Definition: ClpMap.h:277
Definition: ClpMap.h:41
const Value * get(const Key &)
Definition: ClpMap.h:175
std::pair< const Key, EntriesIterator > IndexItem
Definition: ClpMap.h:108
ClpMap(const ClpMap &)=delete
ClpMap(const uint64_t capacity)
Definition: ClpMap.h:46
void del(const Key &)
Remove the corresponding entry (if any)
Definition: ClpMap.h:255
void trim(uint64_t wantSpace)
purges entries to make free memory large enough to fit wantSpace bytes
Definition: ClpMap.h:265
typename Entries::iterator EntriesIterator
Definition: ClpMap.h:106
uint64_t memLimit() const
The memory capacity for the map.
Definition: ClpMap.h:76
uint64_t freeMem() const
The free space of the map.
Definition: ClpMap.h:79
ClpMap & operator=(const ClpMap &)=delete
Ttl defaultTtl_
entry TTL to use if none provided to add()
Definition: ClpMap.h:126
typename Index::iterator IndexIterator
Definition: ClpMap.h:111
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
Index index_
entries_ positions indexed by the entry key
Definition: ClpMap.h:123
static std::optional< uint64_t > MemoryCountedFor(const Key &, const Value &)
Definition: ClpMap.h:187
uint64_t memLimit_
the maximum memory we are allowed to use for all cached entries
Definition: ClpMap.h:129
IndexIterator find(const Key &)
Definition: ClpMap.h:155
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
int Ttl
maximum desired entry caching duration (a.k.a. TTL), in seconds
Definition: ClpMap.h:44
void setMemLimit(uint64_t newLimit)
Reset the memory capacity for this map, purging if needed.
Definition: ClpMap.h:145
size_t entries() const
The number of currently stored entries, including expired ones.
Definition: ClpMap.h:85
~ClpMap()=default
bool add(const Key &, const Value &, Ttl)
Definition: ClpMap.h:207
uint64_t memoryUsed() const
The current (approximate) memory usage of the map.
Definition: ClpMap.h:82
Entries entries_
cached entries, including expired ones, in LRU order
Definition: ClpMap.h:120
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
STL Allocator that uses Squid memory pools for memory management.
A const & max(A const &lhs, A const &rhs)
int unsigned int
Definition: stub_fd.cc:19
static StoreEntry * addedEntry(Store::Disk *aStore, String name, String, String)

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors