]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * Copyright (C) 1996-2025 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_IPC_STOREMAP_H | |
10 | #define SQUID_SRC_IPC_STOREMAP_H | |
11 | ||
12 | #include "ipc/mem/FlexibleArray.h" | |
13 | #include "ipc/mem/Pointer.h" | |
14 | #include "ipc/ReadWriteLock.h" | |
15 | #include "sbuf/SBuf.h" | |
16 | #include "store/forward.h" | |
17 | #include "store_key_md5.h" | |
18 | ||
19 | #include <functional> | |
20 | ||
21 | namespace Ipc | |
22 | { | |
23 | ||
24 | typedef int32_t StoreMapSliceId; | |
25 | ||
26 | /// a piece of Store entry, linked to other pieces, forming a chain | |
27 | /// slices may be appended by writers while readers read the entry | |
28 | class StoreMapSlice | |
29 | { | |
30 | public: | |
31 | typedef uint32_t Size; | |
32 | ||
33 | StoreMapSlice(): size(0), next(-1) {} | |
34 | StoreMapSlice(const StoreMapSlice &o) { | |
35 | size.exchange(o.size); | |
36 | next.exchange(o.next); | |
37 | } | |
38 | ||
39 | StoreMapSlice &operator =(const StoreMapSlice &o) { | |
40 | size.store(o.size); | |
41 | next.store(o.next); | |
42 | return *this; | |
43 | } | |
44 | ||
45 | /// restore default-constructed state | |
46 | void clear() { size = 0; next = -1; } | |
47 | ||
48 | std::atomic<Size> size; ///< slice contents size | |
49 | std::atomic<StoreMapSliceId> next; ///< ID of the next entry slice | |
50 | }; | |
51 | ||
52 | /// Maintains shareable information about a StoreEntry as a whole. | |
53 | /// An anchor points to one or more StoreEntry slices. This is the | |
54 | /// only lockable part of shared StoreEntry information, providing | |
55 | /// protection for all StoreEntry slices. | |
56 | class StoreMapAnchor | |
57 | { | |
58 | public: | |
59 | StoreMapAnchor(); | |
60 | ||
61 | /// store StoreEntry key and basics for an inode slot | |
62 | void set(const StoreEntry &anEntry, const cache_key *aKey = nullptr); | |
63 | /// load StoreEntry basics that were previously stored with set() | |
64 | void exportInto(StoreEntry &) const; | |
65 | ||
66 | void setKey(const cache_key *const aKey); | |
67 | bool sameKey(const cache_key *const aKey) const; | |
68 | ||
69 | /// undo the effects of set(), setKey(), etc., but keep locks and state | |
70 | void rewind(); | |
71 | ||
72 | /* entry state may change immediately after calling these methods unless | |
73 | * the caller holds an appropriate lock */ | |
74 | bool empty() const { return !key[0] && !key[1]; } | |
75 | bool reading() const { return lock.readers; } | |
76 | bool writing() const { return lock.writing; } | |
77 | bool complete() const { return !empty() && !writing(); } | |
78 | ||
79 | public: | |
80 | mutable ReadWriteLock lock; ///< protects slot data below | |
81 | std::atomic<uint8_t> waitingToBeFreed; ///< may be accessed w/o a lock | |
82 | /// whether StoreMap::abortWriting() was called for a read-locked entry | |
83 | std::atomic<uint8_t> writerHalted; | |
84 | ||
85 | // fields marked with [app] can be modified when appending-while-reading | |
86 | // fields marked with [update] can be modified when updating-while-reading | |
87 | ||
88 | uint64_t key[2] = {0, 0}; ///< StoreEntry key | |
89 | ||
90 | // STORE_META_STD TLV field from StoreEntry | |
91 | struct Basics { | |
92 | void clear() { | |
93 | timestamp = 0; | |
94 | lastref = 0; | |
95 | expires = 0; | |
96 | lastmod = 0; | |
97 | swap_file_sz.store(0); | |
98 | refcount = 0; | |
99 | flags = 0; | |
100 | } | |
101 | time_t timestamp = 0; | |
102 | time_t lastref = 0; | |
103 | time_t expires = 0; | |
104 | time_t lastmod = 0; | |
105 | std::atomic<uint64_t> swap_file_sz; // [app] | |
106 | uint16_t refcount = 0; | |
107 | uint16_t flags = 0; | |
108 | } basics; | |
109 | ||
110 | /// where the chain of StoreEntry slices begins [app] | |
111 | std::atomic<StoreMapSliceId> start; | |
112 | ||
113 | /// where the updated chain prefix containing metadata/headers ends [update] | |
114 | /// if unset, this anchor points to a chain that was never updated | |
115 | std::atomic<StoreMapSliceId> splicingPoint; | |
116 | }; | |
117 | ||
118 | /// an array of shareable Items | |
119 | /// must be the last data member or, if used as a parent class, the last parent | |
120 | template <class C> | |
121 | class StoreMapItems | |
122 | { | |
123 | public: | |
124 | typedef C Item; | |
125 | typedef Ipc::Mem::Owner< StoreMapItems<Item> > Owner; | |
126 | ||
127 | explicit StoreMapItems(const int aCapacity): capacity(aCapacity), items(aCapacity) {} | |
128 | ||
129 | size_t sharedMemorySize() const { return SharedMemorySize(capacity); } | |
130 | static size_t SharedMemorySize(const int aCapacity) { return sizeof(StoreMapItems<Item>) + aCapacity*sizeof(Item); } | |
131 | ||
132 | Item &at(const int index) | |
133 | { | |
134 | assert(index >= 0); | |
135 | assert(index < capacity); | |
136 | return items[index]; | |
137 | } | |
138 | ||
139 | const Item &at(const int index) const | |
140 | { | |
141 | return const_cast<StoreMapItems<C>&>(*this).at(index); | |
142 | } | |
143 | ||
144 | /// reset all items to the same value | |
145 | void fill(const Item &value) | |
146 | { | |
147 | for (int index = 0; index < capacity; ++index) | |
148 | items[index] = value; | |
149 | } | |
150 | ||
151 | const int capacity; ///< total number of items | |
152 | Ipc::Mem::FlexibleArray<Item> items; ///< storage | |
153 | }; | |
154 | ||
155 | /// StoreMapSlices indexed by their slice ID. | |
156 | typedef StoreMapItems<StoreMapSlice> StoreMapSlices; | |
157 | ||
158 | /// StoreMapAnchors (indexed by fileno) plus | |
159 | /// sharing-safe basic housekeeping info about Store entries | |
160 | class StoreMapAnchors | |
161 | { | |
162 | public: | |
163 | typedef Ipc::Mem::Owner< StoreMapAnchors > Owner; | |
164 | ||
165 | explicit StoreMapAnchors(const int aCapacity); | |
166 | ||
167 | size_t sharedMemorySize() const; | |
168 | static size_t SharedMemorySize(const int anAnchorLimit); | |
169 | ||
170 | std::atomic<int32_t> count; ///< current number of entries | |
171 | std::atomic<uint32_t> victim; ///< starting point for purge search | |
172 | const int capacity; ///< total number of anchors | |
173 | Ipc::Mem::FlexibleArray<StoreMapAnchor> items; ///< anchors storage | |
174 | }; | |
175 | // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors | |
176 | ||
177 | /// StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash) | |
178 | typedef StoreMapItems< std::atomic<sfileno> > StoreMapFileNos; | |
179 | ||
180 | /// Aggregates information required for updating entry metadata and headers. | |
181 | class StoreMapUpdate | |
182 | { | |
183 | public: | |
184 | /// During an update, the stored entry has two editions: stale and fresh. | |
185 | class Edition | |
186 | { | |
187 | public: | |
188 | Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {} | |
189 | ||
190 | /// whether this entry edition is currently used/initialized | |
191 | explicit operator bool() const { return anchor; } | |
192 | ||
193 | StoreMapAnchor *anchor; ///< StoreMap::anchors[fileNo], for convenience/speed | |
194 | sfileno fileNo; ///< StoreMap::fileNos[name], for convenience/speed | |
195 | sfileno name; ///< StoreEntry position in StoreMap::fileNos, for swapping Editions | |
196 | ||
197 | /// the last slice in the chain still containing metadata/headers | |
198 | StoreMapSliceId splicingPoint; | |
199 | }; | |
200 | ||
201 | explicit StoreMapUpdate(StoreEntry *anEntry); | |
202 | StoreMapUpdate(const StoreMapUpdate &other); | |
203 | ~StoreMapUpdate(); | |
204 | ||
205 | StoreMapUpdate &operator =(const StoreMapUpdate &other) = delete; | |
206 | ||
207 | StoreEntry *entry; ///< the store entry being updated | |
208 | Edition stale; ///< old anchor and chain | |
209 | Edition fresh; ///< new anchor and the updated chain prefix | |
210 | }; | |
211 | ||
212 | class StoreMapCleaner; | |
213 | ||
214 | /// Manages shared Store index (e.g., locking/unlocking/freeing entries) using | |
215 | /// StoreMapFileNos indexed by hashed entry keys (a.k.a. entry names), | |
216 | /// StoreMapAnchors indexed by fileno, and | |
217 | /// StoreMapSlices indexed by slice ID. | |
218 | class StoreMap | |
219 | { | |
220 | public: | |
221 | typedef StoreMapFileNos FileNos; | |
222 | typedef StoreMapAnchor Anchor; | |
223 | typedef StoreMapAnchors Anchors; | |
224 | typedef sfileno AnchorId; | |
225 | typedef StoreMapSlice Slice; | |
226 | typedef StoreMapSlices Slices; | |
227 | typedef StoreMapSliceId SliceId; | |
228 | typedef StoreMapUpdate Update; | |
229 | ||
230 | public: | |
231 | /// aggregates anchor and slice owners for Init() caller convenience | |
232 | class Owner | |
233 | { | |
234 | public: | |
235 | Owner(); | |
236 | ~Owner(); | |
237 | FileNos::Owner *fileNos; | |
238 | Anchors::Owner *anchors; | |
239 | Slices::Owner *slices; | |
240 | private: | |
241 | Owner(const Owner &); // not implemented | |
242 | Owner &operator =(const Owner &); // not implemented | |
243 | }; | |
244 | ||
245 | /// initialize shared memory | |
246 | static Owner *Init(const SBuf &path, const int slotLimit); | |
247 | ||
248 | StoreMap(const SBuf &aPath); | |
249 | ||
250 | /// computes map entry anchor position for a given entry key | |
251 | sfileno fileNoByKey(const cache_key *const key) const; | |
252 | ||
253 | /// Like strcmp(mapped, new), but for store entry versions/timestamps. | |
254 | /// Returns +2 if the mapped entry does not exist; -1/0/+1 otherwise. | |
255 | /// Comparison may be inaccurate unless the caller is a lock holder. | |
256 | int compareVersions(const sfileno oldFileno, time_t newVersion) const; | |
257 | ||
258 | /// finds, locks, and returns an anchor for an empty key position, | |
259 | /// erasing the old entry (if any) | |
260 | Anchor *openForWriting(const cache_key *const key, sfileno &fileno); | |
261 | /// locks and returns an anchor for the empty fileno position; if | |
262 | /// overwriteExisting is false and the position is not empty, returns nil | |
263 | Anchor *openForWritingAt(sfileno fileno, bool overwriteExisting = true); | |
264 | /// restrict opened for writing entry to appending operations; allow reads | |
265 | void startAppending(const sfileno fileno); | |
266 | /// successfully finish creating or updating the entry at fileno pos | |
267 | void closeForWriting(const sfileno fileno); | |
268 | /// stop writing (or updating) the locked entry and start reading it | |
269 | void switchWritingToReading(const sfileno fileno); | |
270 | /// unlock and "forget" openForWriting entry, making it Empty again | |
271 | /// this call does not free entry slices so the caller has to do that | |
272 | void forgetWritingEntry(const sfileno fileno); | |
273 | ||
274 | /// finds and locks the Update entry for an exclusive metadata update | |
275 | bool openForUpdating(Update &update, sfileno fileNoHint); | |
276 | /// makes updated info available to others, unlocks, and cleans up | |
277 | void closeForUpdating(Update &update); | |
278 | /// undoes partial update, unlocks, and cleans up | |
279 | void abortUpdating(Update &update); | |
280 | ||
281 | /// the caller must hold a lock on the entry | |
282 | /// \returns nullptr unless the slice is readable | |
283 | const Anchor *peekAtReader(const sfileno fileno) const; | |
284 | ||
285 | /// the caller must hold a lock on the entry | |
286 | /// \returns nullptr unless the slice is writeable | |
287 | const Anchor *peekAtWriter(const sfileno fileno) const; | |
288 | ||
289 | /// the caller must hold a lock on the entry | |
290 | /// \returns the corresponding Anchor | |
291 | const Anchor &peekAtEntry(const sfileno fileno) const; | |
292 | ||
293 | /// free the entry if possible or mark it as waiting to be freed if not | |
294 | /// \returns whether the entry was neither empty nor marked | |
295 | bool freeEntry(const sfileno); | |
296 | /// free the entry if possible or mark it as waiting to be freed if not | |
297 | /// does nothing if we cannot check that the key matches the cached entry | |
298 | void freeEntryByKey(const cache_key *const key); | |
299 | ||
300 | /// whether the entry with the given key exists and was marked as | |
301 | /// "waiting to be freed" some time ago | |
302 | bool markedForDeletion(const cache_key *const); | |
303 | ||
304 | /// whether the index contains a valid readable entry with the given key | |
305 | bool hasReadableEntry(const cache_key *const); | |
306 | ||
307 | /// opens entry (identified by key) for reading, increments read level | |
308 | const Anchor *openForReading(const cache_key *const key, sfileno &fileno); | |
309 | /// opens entry (identified by sfileno) for reading, increments read level | |
310 | const Anchor *openForReadingAt(const sfileno, const cache_key *const); | |
311 | /// closes open entry after reading, decrements read level | |
312 | void closeForReading(const sfileno fileno); | |
313 | /// same as closeForReading() but also frees the entry if it is unlocked | |
314 | void closeForReadingAndFreeIdle(const sfileno fileno); | |
315 | ||
316 | /// openForReading() but creates a new entry if there is no old one | |
317 | const Anchor *openOrCreateForReading(const cache_key *, sfileno &); | |
318 | ||
319 | /// writeable slice within an entry chain created by openForWriting() | |
320 | Slice &writeableSlice(const AnchorId anchorId, const SliceId sliceId); | |
321 | /// readable slice within an entry chain opened by openForReading() | |
322 | const Slice &readableSlice(const AnchorId anchorId, const SliceId sliceId) const; | |
323 | /// writeable anchor for the entry created by openForWriting() | |
324 | Anchor &writeableEntry(const AnchorId anchorId); | |
325 | /// readable anchor for the entry created by openForReading() | |
326 | const Anchor &readableEntry(const AnchorId anchorId) const; | |
327 | ||
328 | /// prepare a chain-unaffiliated slice for being added to an entry chain | |
329 | void prepFreeSlice(const SliceId sliceId); | |
330 | ||
331 | /// Returns the ID of the entry slice containing n-th byte or | |
332 | /// a negative ID if the entry does not store that many bytes (yet). | |
333 | /// Requires a read lock. | |
334 | SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const; | |
335 | ||
336 | /// stop writing the entry, freeing its slot for others to use if possible | |
337 | void abortWriting(const sfileno fileno); | |
338 | ||
339 | /// either finds and frees an entry with at least 1 slice or returns false | |
340 | bool purgeOne(); | |
341 | ||
342 | /// validates locked hit metadata and calls freeEntry() for invalid entries | |
343 | /// \returns whether hit metadata is correct | |
344 | bool validateHit(const sfileno); | |
345 | ||
346 | void disableHitValidation() { hitValidation = false; } | |
347 | ||
348 | /// copies slice to its designated position | |
349 | void importSlice(const SliceId sliceId, const Slice &slice); | |
350 | ||
351 | /* SwapFilenMax limits the number of entries, but not slices or slots */ | |
352 | bool validEntry(const int n) const; ///< whether n is a valid slice coordinate | |
353 | bool validSlice(const int n) const; ///< whether n is a valid slice coordinate | |
354 | int entryCount() const; ///< number of writeable and readable entries | |
355 | int entryLimit() const; ///< maximum entryCount() possible | |
356 | int sliceLimit() const; ///< maximum number of slices possible | |
357 | ||
358 | /// adds approximate current stats to the supplied ones | |
359 | void updateStats(ReadWriteLockStats &stats) const; | |
360 | ||
361 | StoreMapCleaner *cleaner; ///< notified before a readable entry is freed | |
362 | ||
363 | protected: | |
364 | const SBuf path; ///< cache_dir path or similar cache name; for logging | |
365 | Mem::Pointer<StoreMapFileNos> fileNos; ///< entry inodes (starting blocks) | |
366 | Mem::Pointer<StoreMapAnchors> anchors; ///< entry inodes (starting blocks) | |
367 | Mem::Pointer<StoreMapSlices> slices; ///< chained entry pieces positions | |
368 | ||
369 | private: | |
370 | /// computes entry name (i.e., key hash) for a given entry key | |
371 | sfileno nameByKey(const cache_key *const key) const; | |
372 | /// computes anchor position for a given entry name | |
373 | sfileno fileNoByName(const sfileno name) const; | |
374 | void relocate(const sfileno name, const sfileno fileno); | |
375 | ||
376 | Anchor &anchorAt(const sfileno fileno); | |
377 | const Anchor &anchorAt(const sfileno fileno) const; | |
378 | Anchor &anchorByKey(const cache_key *const key); | |
379 | ||
380 | Slice &sliceAt(const SliceId sliceId); | |
381 | const Slice &sliceAt(const SliceId sliceId) const; | |
382 | Anchor *openForReading(Slice &s); | |
383 | bool openKeyless(Update::Edition &edition); | |
384 | void closeForUpdateFinal(Update &update); | |
385 | ||
386 | typedef std::function<bool (const sfileno name)> NameFilter; // a "name"-based test | |
387 | bool visitVictims(const NameFilter filter); | |
388 | ||
389 | void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock); | |
390 | void freeChainAt(SliceId sliceId, const SliceId splicingPoint); | |
391 | ||
392 | /// whether paranoid_hit_validation should be performed | |
393 | bool hitValidation; | |
394 | }; | |
395 | ||
396 | /// API for adjusting external state when dirty map slice is being freed | |
397 | class StoreMapCleaner | |
398 | { | |
399 | public: | |
400 | virtual ~StoreMapCleaner() {} | |
401 | ||
402 | /// adjust slice-linked state before a locked Readable slice is erased | |
403 | virtual void noteFreeMapSlice(const StoreMapSliceId sliceId) = 0; | |
404 | }; | |
405 | ||
406 | } // namespace Ipc | |
407 | ||
408 | // We do not reuse FileMap because we cannot control its size, | |
409 | // resulting in sfilenos that are pointing beyond the database. | |
410 | ||
411 | #endif /* SQUID_SRC_IPC_STOREMAP_H */ | |
412 |