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