2 * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
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.
9 #ifndef SQUID_IPC_STORE_MAP_H
10 #define SQUID_IPC_STORE_MAP_H
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"
24 typedef int32_t StoreMapSliceId
;
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
31 typedef uint32_t Size
;
33 StoreMapSlice(): size(0), next(-1) {}
34 StoreMapSlice(const StoreMapSlice
&o
) {
35 size
.exchange(o
.size
);
36 next
.exchange(o
.next
);
39 StoreMapSlice
&operator =(const StoreMapSlice
&o
) {
45 /// restore default-constructed state
46 void clear() { size
= 0; next
= -1; }
48 std::atomic
<Size
> size
; ///< slice contents size
49 std::atomic
<StoreMapSliceId
> next
; ///< ID of the next entry slice
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.
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;
66 void setKey(const cache_key
*const aKey
);
67 bool sameKey(const cache_key
*const aKey
) const;
69 /// undo the effects of set(), setKey(), etc., but keep locks and state
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(); }
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
;
85 // fields marked with [app] can be modified when appending-while-reading
86 // fields marked with [update] can be modified when updating-while-reading
88 uint64_t key
[2] = {0, 0}; ///< StoreEntry key
90 // STORE_META_STD TLV field from StoreEntry
97 swap_file_sz
.store(0);
101 time_t timestamp
= 0;
105 std::atomic
<uint64_t> swap_file_sz
; // [app]
106 uint16_t refcount
= 0;
110 /// where the chain of StoreEntry slices begins [app]
111 std::atomic
<StoreMapSliceId
> start
;
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
;
118 /// an array of shareable Items
119 /// must be the last data member or, if used as a parent class, the last parent
125 typedef Ipc::Mem::Owner
< StoreMapItems
<Item
> > Owner
;
127 explicit StoreMapItems(const int aCapacity
): capacity(aCapacity
), items(aCapacity
) {}
129 size_t sharedMemorySize() const { return SharedMemorySize(capacity
); }
130 static size_t SharedMemorySize(const int aCapacity
) { return sizeof(StoreMapItems
<Item
>) + aCapacity
*sizeof(Item
); }
132 Item
&at(const int index
)
135 assert(index
< capacity
);
139 const Item
&at(const int index
) const
141 return const_cast<StoreMapItems
<C
>&>(*this).at(index
);
144 /// reset all items to the same value
145 void fill(const Item
&value
)
147 for (int index
= 0; index
< capacity
; ++index
)
148 items
[index
] = value
;
151 const int capacity
; ///< total number of items
152 Ipc::Mem::FlexibleArray
<Item
> items
; ///< storage
155 /// StoreMapSlices indexed by their slice ID.
156 typedef StoreMapItems
<StoreMapSlice
> StoreMapSlices
;
158 /// StoreMapAnchors (indexed by fileno) plus
159 /// sharing-safe basic housekeeping info about Store entries
160 class StoreMapAnchors
163 typedef Ipc::Mem::Owner
< StoreMapAnchors
> Owner
;
165 explicit StoreMapAnchors(const int aCapacity
);
167 size_t sharedMemorySize() const;
168 static size_t SharedMemorySize(const int anAnchorLimit
);
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
175 // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
177 /// StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash)
178 typedef StoreMapItems
< std::atomic
<sfileno
> > StoreMapFileNos
;
180 /// Aggregates information required for updating entry metadata and headers.
184 /// During an update, the stored entry has two editions: stale and fresh.
188 Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {}
190 /// whether this entry edition is currently used/initialized
191 explicit operator bool() const { return anchor
; }
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
197 /// the last slice in the chain still containing metadata/headers
198 StoreMapSliceId splicingPoint
;
201 explicit StoreMapUpdate(StoreEntry
*anEntry
);
202 StoreMapUpdate(const StoreMapUpdate
&other
);
205 StoreMapUpdate
&operator =(const StoreMapUpdate
&other
) = delete;
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
212 class StoreMapCleaner
;
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.
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
;
231 /// aggregates anchor and slice owners for Init() caller convenience
237 FileNos::Owner
*fileNos
;
238 Anchors::Owner
*anchors
;
239 Slices::Owner
*slices
;
241 Owner(const Owner
&); // not implemented
242 Owner
&operator =(const Owner
&); // not implemented
245 /// initialize shared memory
246 static Owner
*Init(const SBuf
&path
, const int slotLimit
);
248 StoreMap(const SBuf
&aPath
);
250 /// computes map entry anchor position for a given entry key
251 sfileno
fileNoByKey(const cache_key
*const key
) const;
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;
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
);
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
);
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;
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;
289 /// the caller must hold a lock on the entry
290 /// \returns the corresponding Anchor
291 const Anchor
&peekAtEntry(const sfileno fileno
) const;
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
);
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);
304 /// whether the index contains a valid readable entry with the given key
305 bool hasReadableEntry(const cache_key
*const);
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
);
316 /// openForReading() but creates a new entry if there is no old one
317 const Anchor
*openOrCreateForReading(const cache_key
*, sfileno
&, const StoreEntry
&);
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;
328 /// prepare a chain-unaffiliated slice for being added to an entry chain
329 void prepFreeSlice(const SliceId sliceId
);
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;
336 /// stop writing the entry, freeing its slot for others to use if possible
337 void abortWriting(const sfileno fileno
);
339 /// either finds and frees an entry with at least 1 slice or returns false
342 /// validates locked hit metadata and calls freeEntry() for invalid entries
343 /// \returns whether hit metadata is correct
344 bool validateHit(const sfileno
);
346 void disableHitValidation() { hitValidation
= false; }
348 /// copies slice to its designated position
349 void importSlice(const SliceId sliceId
, const Slice
&slice
);
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
358 /// adds approximate current stats to the supplied ones
359 void updateStats(ReadWriteLockStats
&stats
) const;
361 StoreMapCleaner
*cleaner
; ///< notified before a readable entry is freed
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
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
);
376 Anchor
&anchorAt(const sfileno fileno
);
377 const Anchor
&anchorAt(const sfileno fileno
) const;
378 Anchor
&anchorByKey(const cache_key
*const key
);
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
);
386 typedef std::function
<bool (const sfileno name
)> NameFilter
; // a "name"-based test
387 bool visitVictims(const NameFilter filter
);
389 void freeChain(const sfileno fileno
, Anchor
&inode
, const bool keepLock
);
390 void freeChainAt(SliceId sliceId
, const SliceId splicingPoint
);
392 /// whether paranoid_hit_validation should be performed
396 /// API for adjusting external state when dirty map slice is being freed
397 class StoreMapCleaner
400 virtual ~StoreMapCleaner() {}
402 /// adjust slice-linked state before a locked Readable slice is erased
403 virtual void noteFreeMapSlice(const StoreMapSliceId sliceId
) = 0;
408 // We do not reuse FileMap because we cannot control its size,
409 // resulting in sfilenos that are pointing beyond the database.
411 #endif /* SQUID_IPC_STORE_MAP_H */