StoreMap.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 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_IPC_STORE_MAP_H
10#define SQUID_IPC_STORE_MAP_H
11
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
21namespace Ipc
22{
23
24typedef int32_t StoreMapSliceId;
25
29{
30public:
31 typedef uint32_t Size;
32
33 StoreMapSlice(): size(0), next(-1) {}
35 size.exchange(o.size);
36 next.exchange(o.next);
37 }
38
40 size.store(o.size);
41 next.store(o.next);
42 return *this;
43 }
44
46 void clear() { size = 0; next = -1; }
47
48 std::atomic<Size> size;
49 std::atomic<StoreMapSliceId> next;
50};
51
57{
58public:
60
62 void set(const StoreEntry &anEntry, const cache_key *aKey = nullptr);
64 void exportInto(StoreEntry &) const;
65
66 void setKey(const cache_key *const aKey);
67 bool sameKey(const cache_key *const aKey) const;
68
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
79public:
81 std::atomic<uint8_t> waitingToBeFreed;
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};
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;
109
111 std::atomic<StoreMapSliceId> start;
112
115 std::atomic<StoreMapSliceId> splicingPoint;
116};
117
120template <class C>
122{
123public:
124 typedef C Item;
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
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;
153};
154
157
161{
162public:
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;
171 std::atomic<uint32_t> victim;
172 const int capacity;
174};
175// TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
176
179
182{
183public:
186 {
187 public:
188 Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {}
189
191 explicit operator bool() const { return anchor; }
192
196
199 };
200
201 explicit StoreMapUpdate(StoreEntry *anEntry);
202 StoreMapUpdate(const StoreMapUpdate &other);
204
205 StoreMapUpdate &operator =(const StoreMapUpdate &other) = delete;
206
210};
211
212class StoreMapCleaner;
213
219{
220public:
229
230public:
232 class Owner
233 {
234 public:
235 Owner();
236 ~Owner();
240 private:
241 Owner(const Owner &); // not implemented
242 Owner &operator =(const Owner &); // not implemented
243 };
244
246 static Owner *Init(const SBuf &path, const int slotLimit);
247
248 StoreMap(const SBuf &aPath);
249
251 sfileno fileNoByKey(const cache_key *const key) const;
252
256 int compareVersions(const sfileno oldFileno, time_t newVersion) const;
257
260 Anchor *openForWriting(const cache_key *const key, sfileno &fileno);
263 Anchor *openForWritingAt(sfileno fileno, bool overwriteExisting = true);
265 void startAppending(const sfileno fileno);
267 void closeForWriting(const sfileno fileno);
269 void switchWritingToReading(const sfileno fileno);
272 void forgetWritingEntry(const sfileno fileno);
273
275 bool openForUpdating(Update &update, sfileno fileNoHint);
277 void closeForUpdating(Update &update);
279 void abortUpdating(Update &update);
280
283 const Anchor *peekAtReader(const sfileno fileno) const;
284
287 const Anchor *peekAtWriter(const sfileno fileno) const;
288
291 const Anchor &peekAtEntry(const sfileno fileno) const;
292
295 bool freeEntry(const sfileno);
298 void freeEntryByKey(const cache_key *const key);
299
302 bool markedForDeletion(const cache_key *const);
303
305 bool hasReadableEntry(const cache_key *const);
306
308 const Anchor *openForReading(const cache_key *const key, sfileno &fileno);
310 const Anchor *openForReadingAt(const sfileno, const cache_key *const);
312 void closeForReading(const sfileno fileno);
314 void closeForReadingAndFreeIdle(const sfileno fileno);
315
317 const Anchor *openOrCreateForReading(const cache_key *, sfileno &, const StoreEntry &);
318
320 Slice &writeableSlice(const AnchorId anchorId, const SliceId sliceId);
322 const Slice &readableSlice(const AnchorId anchorId, const SliceId sliceId) const;
324 Anchor &writeableEntry(const AnchorId anchorId);
326 const Anchor &readableEntry(const AnchorId anchorId) const;
327
329 void prepFreeSlice(const SliceId sliceId);
330
334 SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const;
335
337 void abortWriting(const sfileno fileno);
338
340 bool purgeOne();
341
344 bool validateHit(const sfileno);
345
347
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;
353 bool validSlice(const int n) const;
354 int entryCount() const;
355 int entryLimit() const;
356 int sliceLimit() const;
357
360
362
363protected:
364 const SBuf path;
368
369private:
371 sfileno nameByKey(const cache_key *const key) const;
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;
383 bool openKeyless(Update::Edition &edition);
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
394};
395
398{
399public:
400 virtual ~StoreMapCleaner() {}
401
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_IPC_STORE_MAP_H */
412
#define assert(EX)
Definition: assert.h:19
approximate stats of a set of ReadWriteLocks
Definition: ReadWriteLock.h:66
std::atomic< uint32_t > readers
number of reading users
Definition: ReadWriteLock.h:49
std::atomic< bool > writing
there is a writing user (there can be at most 1)
Definition: ReadWriteLock.h:50
std::atomic< StoreMapSliceId > splicingPoint
Definition: StoreMap.h:115
std::atomic< StoreMapSliceId > start
where the chain of StoreEntry slices begins [app]
Definition: StoreMap.h:111
void rewind()
undo the effects of set(), setKey(), etc., but keep locks and state
Definition: StoreMap.cc:1003
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:952
bool empty() const
Definition: StoreMap.h:74
struct Ipc::StoreMapAnchor::Basics basics
uint64_t key[2]
StoreEntry key.
Definition: StoreMap.h:88
bool complete() const
Definition: StoreMap.h:77
std::atomic< uint8_t > writerHalted
whether StoreMap::abortWriting() was called for a read-locked entry
Definition: StoreMap.h:83
bool writing() const
Definition: StoreMap.h:76
void set(const StoreEntry &anEntry, const cache_key *aKey=nullptr)
store StoreEntry key and basics for an inode slot
Definition: StoreMap.cc:959
bool reading() const
Definition: StoreMap.h:75
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:945
ReadWriteLock lock
protects slot data below
Definition: StoreMap.h:80
std::atomic< uint8_t > waitingToBeFreed
Definition: StoreMap.h:81
void exportInto(StoreEntry &) const
load StoreEntry basics that were previously stored with set()
Definition: StoreMap.cc:979
Ipc::Mem::FlexibleArray< StoreMapAnchor > items
anchors storage
Definition: StoreMap.h:173
Ipc::Mem::Owner< StoreMapAnchors > Owner
Definition: StoreMap.h:163
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:1054
std::atomic< int32_t > count
current number of entries
Definition: StoreMap.h:170
const int capacity
total number of anchors
Definition: StoreMap.h:172
std::atomic< uint32_t > victim
starting point for purge search
Definition: StoreMap.h:171
size_t sharedMemorySize() const
Definition: StoreMap.cc:1063
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:1069
API for adjusting external state when dirty map slice is being freed.
Definition: StoreMap.h:398
virtual void noteFreeMapSlice(const StoreMapSliceId sliceId)=0
adjust slice-linked state before a locked Readable slice is erased
virtual ~StoreMapCleaner()
Definition: StoreMap.h:400
StoreMapItems(const int aCapacity)
Definition: StoreMap.h:127
const Item & at(const int index) const
Definition: StoreMap.h:139
Item & at(const int index)
Definition: StoreMap.h:132
const int capacity
total number of items
Definition: StoreMap.h:151
void fill(const Item &value)
reset all items to the same value
Definition: StoreMap.h:145
Ipc::Mem::Owner< StoreMapItems< Item > > Owner
Definition: StoreMap.h:125
static size_t SharedMemorySize(const int aCapacity)
Definition: StoreMap.h:130
Ipc::Mem::FlexibleArray< Item > items
storage
Definition: StoreMap.h:152
size_t sharedMemorySize() const
Definition: StoreMap.h:129
void clear()
restore default-constructed state
Definition: StoreMap.h:46
uint32_t Size
Definition: StoreMap.h:31
std::atomic< StoreMapSliceId > next
ID of the next entry slice.
Definition: StoreMap.h:49
std::atomic< Size > size
slice contents size
Definition: StoreMap.h:48
StoreMapSlice(const StoreMapSlice &o)
Definition: StoreMap.h:34
StoreMapSlice & operator=(const StoreMapSlice &o)
Definition: StoreMap.h:39
During an update, the stored entry has two editions: stale and fresh.
Definition: StoreMap.h:186
sfileno name
StoreEntry position in StoreMap::fileNos, for swapping Editions.
Definition: StoreMap.h:195
sfileno fileNo
StoreMap::fileNos[name], for convenience/speed.
Definition: StoreMap.h:194
StoreMapSliceId splicingPoint
the last slice in the chain still containing metadata/headers
Definition: StoreMap.h:198
StoreMapAnchor * anchor
StoreMap::anchors[fileNo], for convenience/speed.
Definition: StoreMap.h:193
Aggregates information required for updating entry metadata and headers.
Definition: StoreMap.h:182
Edition fresh
new anchor and the updated chain prefix
Definition: StoreMap.h:209
Edition stale
old anchor and chain
Definition: StoreMap.h:208
StoreMapUpdate & operator=(const StoreMapUpdate &other)=delete
StoreEntry * entry
the store entry being updated
Definition: StoreMap.h:207
StoreMapUpdate(StoreEntry *anEntry)
Definition: StoreMap.cc:1017
aggregates anchor and slice owners for Init() caller convenience
Definition: StoreMap.h:233
Slices::Owner * slices
Definition: StoreMap.h:239
Anchors::Owner * anchors
Definition: StoreMap.h:238
Owner & operator=(const Owner &)
Owner(const Owner &)
FileNos::Owner * fileNos
Definition: StoreMap.h:237
Anchor * openForWriting(const cache_key *const key, sfileno &fileno)
Definition: StoreMap.cc:140
const Slice & readableSlice(const AnchorId anchorId, const SliceId sliceId) const
readable slice within an entry chain opened by openForReading()
Definition: StoreMap.cc:229
StoreMapSlices Slices
Definition: StoreMap.h:226
const Anchor * openForReadingAt(const sfileno, const cache_key *const)
opens entry (identified by sfileno) for reading, increments read level
Definition: StoreMap.cc:453
bool validateHit(const sfileno)
Definition: StoreMap.cc:801
bool openForUpdating(Update &update, sfileno fileNoHint)
finds and locks the Update entry for an exclusive metadata update
Definition: StoreMap.cc:523
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:155
bool visitVictims(const NameFilter filter)
Definition: StoreMap.cc:685
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:355
Anchor & writeableEntry(const AnchorId anchorId)
writeable anchor for the entry created by openForWriting()
Definition: StoreMap.cc:237
StoreMapUpdate Update
Definition: StoreMap.h:228
sfileno AnchorId
Definition: StoreMap.h:224
Mem::Pointer< StoreMapAnchors > anchors
entry inodes (starting blocks)
Definition: StoreMap.h:366
const Anchor * peekAtReader(const sfileno fileno) const
Definition: StoreMap.cc:287
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:758
const Anchor & readableEntry(const AnchorId anchorId) const
readable anchor for the entry created by openForReading()
Definition: StoreMap.cc:244
void closeForUpdateFinal(Update &update)
Anchor & anchorByKey(const cache_key *const key)
Definition: StoreMap.cc:919
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:739
static Owner * Init(const SBuf &path, const int slotLimit)
initialize shared memory
Definition: StoreMap.cc:42
void relocate(const sfileno name, const sfileno fileno)
map name to fileNo
Definition: StoreMap.cc:905
void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock)
unconditionally frees an already locked chain of slots, unlocking if needed
Definition: StoreMap.cc:375
const Anchor * openOrCreateForReading(const cache_key *, sfileno &, const StoreEntry &)
openForReading() but creates a new entry if there is no old one
Definition: StoreMap.cc:103
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:925
void closeForWriting(const sfileno fileno)
successfully finish creating or updating the entry at fileno pos
Definition: StoreMap.cc:200
StoreMapCleaner * cleaner
notified before a readable entry is freed
Definition: StoreMap.h:361
void abortUpdating(Update &update)
undoes partial update, unlocks, and cleans up
Definition: StoreMap.cc:269
bool hitValidation
whether paranoid_hit_validation should be performed
Definition: StoreMap.h:393
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:421
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:440
void forgetWritingEntry(const sfileno fileno)
Definition: StoreMap.cc:84
int compareVersions(const sfileno oldFileno, time_t newVersion) const
Definition: StoreMap.cc:68
bool freeEntry(const sfileno)
Definition: StoreMap.cc:313
const SBuf path
cache_dir path or similar cache name; for logging
Definition: StoreMap.h:364
StoreMapFileNos FileNos
Definition: StoreMap.h:221
void closeForReading(const sfileno fileno)
closes open entry after reading, decrements read level
Definition: StoreMap.cc:497
StoreMap(const SBuf &aPath)
Definition: StoreMap.cc:54
void importSlice(const SliceId sliceId, const Slice &slice)
copies slice to its designated position
Definition: StoreMap.cc:722
const Anchor * peekAtWriter(const sfileno fileno) const
Definition: StoreMap.cc:297
void closeForReadingAndFreeIdle(const sfileno fileno)
same as closeForReading() but also frees the entry if it is unlocked
Definition: StoreMap.cc:506
void abortWriting(const sfileno fileno)
stop writing the entry, freeing its slot for others to use if possible
Definition: StoreMap.cc:251
bool validSlice(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:764
void startAppending(const sfileno fileno)
restrict opened for writing entry to appending operations; allow reads
Definition: StoreMap.cc:191
sfileno nameByKey(const cache_key *const key) const
computes entry name (i.e., key hash) for a given entry key
Definition: StoreMap.cc:884
Anchor * openForReading(Slice &s)
void prepFreeSlice(const SliceId sliceId)
prepare a chain-unaffiliated slice for being added to an entry chain
Definition: StoreMap.cc:413
StoreMapAnchors Anchors
Definition: StoreMap.h:223
Mem::Pointer< StoreMapSlices > slices
chained entry pieces positions
Definition: StoreMap.h:367
void closeForUpdating(Update &update)
makes updated info available to others, unlocks, and cleans up
Definition: StoreMap.cc:605
std::function< bool(const sfileno name)> NameFilter
Definition: StoreMap.h:386
bool openKeyless(Update::Edition &edition)
Definition: StoreMap.cc:587
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:702
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:751
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:912
StoreMapAnchor Anchor
Definition: StoreMap.h:222
bool hasReadableEntry(const cache_key *const)
whether the index contains a valid readable entry with the given key
Definition: StoreMap.cc:363
StoreMapSliceId SliceId
Definition: StoreMap.h:227
void freeEntryByKey(const cache_key *const key)
Definition: StoreMap.cc:331
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:894
StoreMapSlice Slice
Definition: StoreMap.h:225
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:871
const Anchor & peekAtEntry(const sfileno fileno) const
Definition: StoreMap.cc:307
Mem::Pointer< StoreMapFileNos > fileNos
entry inodes (starting blocks)
Definition: StoreMap.h:365
Slice & writeableSlice(const AnchorId anchorId, const SliceId sliceId)
writeable slice within an entry chain created by openForWriting()
Definition: StoreMap.cc:221
void switchWritingToReading(const sfileno fileno)
stop writing (or updating) the locked entry and start reading it
Definition: StoreMap.cc:211
int sliceLimit() const
maximum number of slices possible
Definition: StoreMap.cc:745
void disableHitValidation()
Definition: StoreMap.h:346
void freeChainAt(SliceId sliceId, const SliceId splicingPoint)
unconditionally frees an already locked chain of slots; no anchor maintenance
Definition: StoreMap.cc:391
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:733
Definition: SBuf.h:94
static uint32 C
Definition: md4.c:43
Definition: IpcIoFile.h:24
int32_t StoreMapSliceId
Definition: StoreMap.h:24
StoreMapItems< std::atomic< sfileno > > StoreMapFileNos
StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash)
Definition: StoreMap.h:178
StoreMapItems< StoreMapSlice > StoreMapSlices
StoreMapSlices indexed by their slice ID.
Definition: StoreMap.h:156
class Ping::pingStats_ stats
unsigned char cache_key
Store key.
Definition: forward.h:29
signed_int32_t sfileno
Definition: forward.h:22
std::atomic< uint64_t > swap_file_sz
Definition: StoreMap.h:105

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors