StoreMap.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2018 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 
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 
29 {
30 public:
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 
45  std::atomic<Size> size;
46  std::atomic<StoreMapSliceId> next;
47 };
48 
54 {
55 public:
57 
59  void set(const StoreEntry &anEntry, const cache_key *aKey = nullptr);
61  void exportInto(StoreEntry &) const;
62 
63  void setKey(const cache_key *const aKey);
64  bool sameKey(const cache_key *const aKey) const;
65 
67  void rewind();
68 
69  /* entry state may change immediately after calling these methods unless
70  * the caller holds an appropriate lock */
71  bool empty() const { return !key[0] && !key[1]; }
72  bool reading() const { return lock.readers; }
73  bool writing() const { return lock.writing; }
74  bool complete() const { return !empty() && !writing(); }
75 
76 public:
77  mutable ReadWriteLock lock;
78  std::atomic<uint8_t> waitingToBeFreed;
79  std::atomic<uint8_t> writerHalted;
81 
82  // fields marked with [app] can be modified when appending-while-reading
83  // fields marked with [update] can be modified when updating-while-reading
84 
85  uint64_t key[2];
86 
87  // STORE_META_STD TLV field from StoreEntry
88  struct Basics {
89  time_t timestamp;
90  time_t lastref;
91  time_t expires;
92  time_t lastmod;
93  std::atomic<uint64_t> swap_file_sz; // [app]
94  uint16_t refcount;
95  uint16_t flags;
96  } basics;
97 
99  std::atomic<StoreMapSliceId> start;
100 
103  std::atomic<StoreMapSliceId> splicingPoint;
104 };
105 
108 template <class C>
110 {
111 public:
112  typedef C Item;
114 
115  explicit StoreMapItems(const int aCapacity): capacity(aCapacity), items(aCapacity) {}
116 
117  size_t sharedMemorySize() const { return SharedMemorySize(capacity); }
118  static size_t SharedMemorySize(const int aCapacity) { return sizeof(StoreMapItems<Item>) + aCapacity*sizeof(Item); }
119 
120  const int capacity;
122 };
123 
126 
130 {
131 public:
133 
134  explicit StoreMapAnchors(const int aCapacity);
135 
136  size_t sharedMemorySize() const;
137  static size_t SharedMemorySize(const int anAnchorLimit);
138 
139  std::atomic<int32_t> count;
140  std::atomic<uint32_t> victim;
141  const int capacity;
143 };
144 // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
145 
148 
151 {
152 public:
154  class Edition
155  {
156  public:
157  Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {}
158 
160  explicit operator bool() const { return anchor; }
161 
165 
168  };
169 
170  explicit StoreMapUpdate(StoreEntry *anEntry);
171  StoreMapUpdate(const StoreMapUpdate &other);
172  ~StoreMapUpdate();
173 
174  StoreMapUpdate &operator =(const StoreMapUpdate &other) = delete;
175 
179 };
180 
181 class StoreMapCleaner;
182 
187 class StoreMap
188 {
189 public:
193  typedef sfileno AnchorId;
198 
199 public:
201  class Owner
202  {
203  public:
204  Owner();
205  ~Owner();
209  private:
210  Owner(const Owner &); // not implemented
211  Owner &operator =(const Owner &); // not implemented
212  };
213 
215  static Owner *Init(const SBuf &path, const int slotLimit);
216 
217  StoreMap(const SBuf &aPath);
218 
220  sfileno fileNoByKey(const cache_key *const key) const;
221 
225  int compareVersions(const sfileno oldFileno, time_t newVersion) const;
226 
229  Anchor *openForWriting(const cache_key *const key, sfileno &fileno);
232  Anchor *openForWritingAt(sfileno fileno, bool overwriteExisting = true);
234  void startAppending(const sfileno fileno);
236  void closeForWriting(const sfileno fileno);
238  void switchWritingToReading(const sfileno fileno);
241  void forgetWritingEntry(const sfileno fileno);
242 
244  bool openForUpdating(Update &update, sfileno fileNoHint);
246  void closeForUpdating(Update &update);
248  void abortUpdating(Update &update);
249 
251  const Anchor *peekAtReader(const sfileno fileno) const;
252 
254  const Anchor &peekAtEntry(const sfileno fileno) const;
255 
258  bool freeEntry(const sfileno);
261  void freeEntryByKey(const cache_key *const key);
262 
265  bool markedForDeletion(const cache_key *const);
266 
268  bool hasReadableEntry(const cache_key *const);
269 
271  const Anchor *openForReading(const cache_key *const key, sfileno &fileno);
273  const Anchor *openForReadingAt(const sfileno fileno);
275  void closeForReading(const sfileno fileno);
276 
278  Slice &writeableSlice(const AnchorId anchorId, const SliceId sliceId);
280  const Slice &readableSlice(const AnchorId anchorId, const SliceId sliceId) const;
282  Anchor &writeableEntry(const AnchorId anchorId);
284  const Anchor &readableEntry(const AnchorId anchorId) const;
285 
289  SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const;
290 
292  void abortWriting(const sfileno fileno);
293 
295  bool purgeOne();
296 
298  void importSlice(const SliceId sliceId, const Slice &slice);
299 
300  /* SwapFilenMax limits the number of entries, but not slices or slots */
301  bool validEntry(const int n) const;
302  bool validSlice(const int n) const;
303  int entryCount() const;
304  int entryLimit() const;
305  int sliceLimit() const;
306 
308  void updateStats(ReadWriteLockStats &stats) const;
309 
311 
312 protected:
313  const SBuf path;
317 
318 private:
320  sfileno nameByKey(const cache_key *const key) const;
322  sfileno fileNoByName(const sfileno name) const;
323  void relocate(const sfileno name, const sfileno fileno);
324 
325  Anchor &anchorAt(const sfileno fileno);
326  const Anchor &anchorAt(const sfileno fileno) const;
327  Anchor &anchorByKey(const cache_key *const key);
328 
329  Slice &sliceAt(const SliceId sliceId);
330  const Slice &sliceAt(const SliceId sliceId) const;
332  bool openKeyless(Update::Edition &edition);
333  void closeForUpdateFinal(Update &update);
334 
335  typedef std::function<bool (const sfileno name)> NameFilter; // a "name"-based test
336  bool visitVictims(const NameFilter filter);
337 
338  void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock);
339  void freeChainAt(SliceId sliceId, const SliceId splicingPoint);
340 };
341 
344 {
345 public:
346  virtual ~StoreMapCleaner() {}
347 
349  virtual void noteFreeMapSlice(const StoreMapSliceId sliceId) = 0;
350 };
351 
352 } // namespace Ipc
353 
354 // We do not reuse FileMap because we cannot control its size,
355 // resulting in sfilenos that are pointing beyond the database.
356 
357 #endif /* SQUID_IPC_STORE_MAP_H */
358 
virtual void noteFreeMapSlice(const StoreMapSliceId sliceId)=0
adjust slice-linked state before a locked Readable slice is erased
Mem::Pointer< StoreMapAnchors > anchors
entry inodes (starting blocks)
Definition: StoreMap.h:315
const Anchor * peekAtReader(const sfileno fileno) const
only works on locked entries; returns nil unless the slice is readable
Definition: StoreMap.cc:245
sfileno fileNo
StoreMap::fileNos[name], for convenience/speed.
Definition: StoreMap.h:163
sfileno fileNoByKey(const cache_key *const key) const
computes map entry anchor position for a given entry key
Definition: StoreMap.cc:730
bool validSlice(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:683
const Anchor * openForReadingAt(const sfileno fileno)
opens entry (identified by sfileno) for reading, increments read level
Definition: StoreMap.cc:400
bool freeEntry(const sfileno)
Definition: StoreMap.cc:263
std::atomic< uint64_t > swap_file_sz
Definition: StoreMap.h:93
void importSlice(const SliceId sliceId, const Slice &slice)
copies slice to its designated position
Definition: StoreMap.cc:641
bool complete() const
Definition: StoreMap.h:74
struct Ipc::StoreMapAnchor::Basics basics
Slices::Owner * slices
Definition: StoreMap.h:208
Anchors::Owner * anchors
Definition: StoreMap.h:207
std::atomic< StoreMapSliceId > next
ID of the next entry slice.
Definition: StoreMap.h:46
virtual ~StoreMapCleaner()
Definition: StoreMap.h:346
StoreMapSlice & operator=(const StoreMapSlice &o)
Definition: StoreMap.h:39
Aggregates information required for updating entry metadata and headers.
Definition: StoreMap.h:150
void rewind()
undo the effects of set(), setKey(), etc., but keep locks and state
Definition: StoreMap.cc:812
std::atomic< uint8_t > waitingToBeFreed
Definition: StoreMap.h:78
size_t sharedMemorySize() const
Definition: StoreMap.h:117
int entryLimit() const
maximum entryCount() possible
Definition: StoreMap.cc:652
Definition: SBuf.h:86
std::atomic< Size > size
slice contents size
Definition: StoreMap.h:45
unsigned char cache_key
Store key.
Definition: forward.h:29
std::function< bool(const sfileno name)> NameFilter
Definition: StoreMap.h:335
Anchor & anchorByKey(const cache_key *const key)
Definition: StoreMap.cc:737
bool markedForDeletion(const cache_key *const)
Definition: StoreMap.cc:305
void freeEntryByKey(const cache_key *const key)
Definition: StoreMap.cc:281
void switchWritingToReading(const sfileno fileno)
stop writing (or updating) the locked entry and start reading it
Definition: StoreMap.cc:169
StoreMapAnchors Anchors
Definition: StoreMap.h:192
bool visitVictims(const NameFilter filter)
Definition: StoreMap.cc:604
void abortUpdating(Update &update)
undoes partial update, unlocks, and cleans up
Definition: StoreMap.cc:227
class Ping::pingStats_ stats
StoreMap(const SBuf &aPath)
Definition: StoreMap.cc:50
Slice & sliceAt(const SliceId sliceId)
Definition: StoreMap.cc:743
StoreMapCleaner * cleaner
notified before a readable entry is freed
Definition: StoreMap.h:310
StoreMapSliceId SliceId
Definition: StoreMap.h:196
approximate stats of a set of ReadWriteLocks
Definition: ReadWriteLock.h:56
uint32_t Size
Definition: StoreMap.h:31
StoreMapUpdate Update
Definition: StoreMap.h:197
void closeForWriting(const sfileno fileno)
successfully finish creating or updating the entry at fileno pos
Definition: StoreMap.cc:158
static Owner * Init(const SBuf &path, const int slotLimit)
initialize shared memory
Definition: StoreMap.cc:38
bool openForUpdating(Update &update, sfileno fileNoHint)
finds and locks the Update entry for an exclusive metadata update
Definition: StoreMap.cc:439
std::atomic< int32_t > count
current number of entries
Definition: StoreMap.h:139
bool validEntry(const int n) const
whether n is a valid slice coordinate
Definition: StoreMap.cc:677
StoreMapSlices Slices
Definition: StoreMap.h:195
void closeForUpdateFinal(Update &update)
API for adjusting external state when dirty map slice is being freed.
Definition: StoreMap.h:343
StoreMapItems(const int aCapacity)
Definition: StoreMap.h:115
bool sameKey(const cache_key *const aKey) const
Definition: StoreMap.cc:772
StoreMapItems< StoreMapSlice > StoreMapSlices
StoreMapSlices indexed by their slice ID.
Definition: StoreMap.h:125
static size_t SharedMemorySize(const int aCapacity)
Definition: StoreMap.h:118
void forgetWritingEntry(const sfileno fileno)
Definition: StoreMap.cc:79
StoreMapFileNos FileNos
Definition: StoreMap.h:190
sfileno fileNoByName(const sfileno name) const
computes anchor position for a given entry name
Definition: StoreMap.cc:712
void startAppending(const sfileno fileno)
restrict opened for writing entry to appending operations; allow reads
Definition: StoreMap.cc:149
bool openKeyless(Update::Edition &edition)
Definition: StoreMap.cc:509
StoreMapAnchors(const int aCapacity)
Definition: StoreMap.cc:863
Slice & writeableSlice(const AnchorId anchorId, const SliceId sliceId)
writeable slice within an entry chain created by openForWriting()
Definition: StoreMap.cc:179
int32_t StoreMapSliceId
Definition: StoreMap.h:24
SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const
Definition: StoreMap.cc:364
void updateStats(ReadWriteLockStats &stats) const
adds approximate current stats to the supplied ones
Definition: StoreMap.cc:670
Ipc::Mem::FlexibleArray< Item > items
storage
Definition: StoreMap.h:121
Anchor & writeableEntry(const AnchorId anchorId)
writeable anchor for the entry created by openForWriting()
Definition: StoreMap.cc:195
sfileno nameByKey(const cache_key *const key) const
computes entry name (i.e., key hash) for a given entry key
Definition: StoreMap.cc:702
std::atomic< StoreMapSliceId > splicingPoint
Definition: StoreMap.h:103
const int capacity
total number of anchors
Definition: StoreMap.h:141
void abortWriting(const sfileno fileno)
stop writing the entry, freeing its slot for others to use if possible
Definition: StoreMap.cc:209
StoreMapAnchor * anchor
StoreMap::anchors[fileNo], for convenience/speed.
Definition: StoreMap.h:162
signed_int32_t sfileno
Definition: forward.h:22
StoreMapUpdate(StoreEntry *anEntry)
Definition: StoreMap.cc:826
StoreMapItems< std::atomic< sfileno > > StoreMapFileNos
StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash)
Definition: StoreMap.h:147
StoreMapSlice Slice
Definition: StoreMap.h:194
StoreMapAnchor Anchor
Definition: StoreMap.h:191
bool empty() const
Definition: StoreMap.h:71
size_t sharedMemorySize() const
Definition: StoreMap.cc:872
static size_t SharedMemorySize(const int anAnchorLimit)
Definition: StoreMap.cc:878
const Anchor & peekAtEntry(const sfileno fileno) const
only works on locked entries; returns the corresponding Anchor
Definition: StoreMap.cc:257
void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock)
unconditionally frees an already locked chain of slots, unlocking if needed
Definition: StoreMap.cc:325
int sliceLimit() const
maximum number of slices possible
Definition: StoreMap.cc:664
bool writing() const
Definition: StoreMap.h:73
int compareVersions(const sfileno oldFileno, time_t newVersion) const
Definition: StoreMap.cc:63
void freeChainAt(SliceId sliceId, const SliceId splicingPoint)
unconditionally frees an already locked chain of slots; no anchor maintenance
Definition: StoreMap.cc:341
Ipc::Mem::FlexibleArray< StoreMapAnchor > items
anchors storage
Definition: StoreMap.h:142
const Anchor * openForReading(const cache_key *const key, sfileno &fileno)
opens entry (identified by key) for reading, increments read level
Definition: StoreMap.cc:383
std::atomic< uint32_t > victim
starting point for purge search
Definition: StoreMap.h:140
const Anchor & readableEntry(const AnchorId anchorId) const
readable anchor for the entry created by openForReading()
Definition: StoreMap.cc:202
Edition stale
old anchor and chain being updated
Definition: StoreMap.h:177
Edition fresh
new anchor and updated chain prefix
Definition: StoreMap.h:178
std::atomic< uint8_t > writerHalted
whether StoreMap::abortWriting() was called for a read-locked entry
Definition: StoreMap.h:80
aggregates anchor and slice owners for Init() caller convenience
Definition: StoreMap.h:201
bool reading() const
Definition: StoreMap.h:72
void exportInto(StoreEntry &) const
load StoreEntry basics that were previously stored with set()
Definition: StoreMap.cc:799
sfileno name
StoreEntry position in StoreMap::fileNos, for swapping Editions.
Definition: StoreMap.h:164
Owner & operator=(const Owner &)
uint64_t key[2]
StoreEntry key.
Definition: StoreMap.h:85
Ipc::Mem::Owner< StoreMapItems< Item > > Owner
Definition: StoreMap.h:113
const SBuf path
cache_dir path or similar cache name; for logging
Definition: StoreMap.h:313
Mem::Pointer< StoreMapFileNos > fileNos
entry inodes (starting blocks)
Definition: StoreMap.h:314
void set(const StoreEntry &anEntry, const cache_key *aKey=nullptr)
store StoreEntry key and basics for an inode slot
Definition: StoreMap.cc:779
bool purgeOne()
either finds and frees an entry with at least 1 slice or returns false
Definition: StoreMap.cc:621
std::atomic< uint32_t > readers
number of reading users
Definition: ReadWriteLock.h:45
StoreMapSlice(const StoreMapSlice &o)
Definition: StoreMap.h:34
bool hasReadableEntry(const cache_key *const)
whether the index contains a valid readable entry with the given key
Definition: StoreMap.cc:313
const Slice & readableSlice(const AnchorId anchorId, const SliceId sliceId) const
readable slice within an entry chain opened by openForReading()
Definition: StoreMap.cc:187
Anchor * openForWritingAt(sfileno fileno, bool overwriteExisting=true)
Definition: StoreMap.cc:113
std::atomic< bool > writing
there is a writing user (there can be at most 1)
Definition: ReadWriteLock.h:46
StoreMapSliceId splicingPoint
the last slice in the chain still containing metadata/headers
Definition: StoreMap.h:167
ReadWriteLock lock
protects slot data below
Definition: StoreMap.h:77
Ipc::Mem::Owner< StoreMapAnchors > Owner
Definition: StoreMap.h:132
Anchor * openForWriting(const cache_key *const key, sfileno &fileno)
Definition: StoreMap.cc:98
void closeForReading(const sfileno fileno)
closes open entry after reading, decrements read level
Definition: StoreMap.cc:430
std::atomic< StoreMapSliceId > start
where the chain of StoreEntry slices begins [app]
Definition: StoreMap.h:99
int entryCount() const
number of writeable and readable entries
Definition: StoreMap.cc:658
void relocate(const sfileno name, const sfileno fileno)
map name to fileNo
Definition: StoreMap.cc:723
Anchor & anchorAt(const sfileno fileno)
Definition: StoreMap.cc:689
sfileno AnchorId
Definition: StoreMap.h:193
StoreMapUpdate & operator=(const StoreMapUpdate &other)=delete
FileNos::Owner * fileNos
Definition: StoreMap.h:206
Mem::Pointer< StoreMapSlices > slices
chained entry pieces positions
Definition: StoreMap.h:316
During an update, the stored entry has two editions: stale and fresh.
Definition: StoreMap.h:154
void closeForUpdating(Update &update)
makes updated info available to others, unlocks, and cleans up
Definition: StoreMap.cc:527
StoreEntry * entry
the store entry being updated
Definition: StoreMap.h:176
void setKey(const cache_key *const aKey)
Definition: StoreMap.cc:765
const int capacity
total number of items
Definition: StoreMap.h:120

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors