src/ipc/StoreMap.h

   1 /*
   2  * Copyright (C) 1996-2019 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
  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     const int capacity; ///< total number of items
 133     Ipc::Mem::FlexibleArray<Item> items; ///< storage
 134 };
 135
 136 /// StoreMapSlices indexed by their slice ID.
 137 typedef StoreMapItems<StoreMapSlice> StoreMapSlices;
 138
 139 /// StoreMapAnchors (indexed by fileno) plus
 140 /// sharing-safe basic housekeeping info about Store entries
 141 class StoreMapAnchors
 142 {
 143 public:
 144     typedef Ipc::Mem::Owner< StoreMapAnchors > Owner;
 145
 146     explicit StoreMapAnchors(const int aCapacity);
 147
 148     size_t sharedMemorySize() const;
 149     static size_t SharedMemorySize(const int anAnchorLimit);
 150
 151     std::atomic<int32_t> count; ///< current number of entries
 152     std::atomic<uint32_t> victim; ///< starting point for purge search
 153     const int capacity; ///< total number of anchors
 154     Ipc::Mem::FlexibleArray<StoreMapAnchor> items; ///< anchors storage
 155 };
 156 // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
 157
 158 /// StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash)
 159 typedef StoreMapItems< std::atomic<sfileno> > StoreMapFileNos;
 160
 161 /// Aggregates information required for updating entry metadata and headers.
 162 class StoreMapUpdate
 163 {
 164 public:
 165     /// During an update, the stored entry has two editions: stale and fresh.
 166     class Edition
 167     {
 168     public:
 169         Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {}
 170
 171         /// whether this entry edition is currently used/initialized
 172         explicit operator bool() const { return anchor; }
 173
 174         StoreMapAnchor *anchor; ///< StoreMap::anchors[fileNo], for convenience/speed
 175         sfileno fileNo; ///< StoreMap::fileNos[name], for convenience/speed
 176         sfileno name; ///< StoreEntry position in StoreMap::fileNos, for swapping Editions
 177
 178         /// the last slice in the chain still containing metadata/headers
 179         StoreMapSliceId splicingPoint;
 180     };
 181
 182     explicit StoreMapUpdate(StoreEntry *anEntry);
 183     StoreMapUpdate(const StoreMapUpdate &other);
 184     ~StoreMapUpdate();
 185
 186     StoreMapUpdate &operator =(const StoreMapUpdate &other) = delete;
 187
 188     StoreEntry *entry; ///< the store entry being updated
 189     Edition stale; ///< old anchor and chain
 190     Edition fresh; ///< new anchor and the updated chain prefix
 191 };
 192
 193 class StoreMapCleaner;
 194
 195 /// Manages shared Store index (e.g., locking/unlocking/freeing entries) using
 196 /// StoreMapFileNos indexed by hashed entry keys (a.k.a. entry names),
 197 /// StoreMapAnchors indexed by fileno, and
 198 /// StoreMapSlices indexed by slice ID.
 199 class StoreMap
 200 {
 201 public:
 202     typedef StoreMapFileNos FileNos;
 203     typedef StoreMapAnchor Anchor;
 204     typedef StoreMapAnchors Anchors;
 205     typedef sfileno AnchorId;
 206     typedef StoreMapSlice Slice;
 207     typedef StoreMapSlices Slices;
 208     typedef StoreMapSliceId SliceId;
 209     typedef StoreMapUpdate Update;
 210
 211 public:
 212     /// aggregates anchor and slice owners for Init() caller convenience
 213     class Owner
 214     {
 215     public:
 216         Owner();
 217         ~Owner();
 218         FileNos::Owner *fileNos;
 219         Anchors::Owner *anchors;
 220         Slices::Owner *slices;
 221     private:
 222         Owner(const Owner &); // not implemented
 223         Owner &operator =(const Owner &); // not implemented
 224     };
 225
 226     /// initialize shared memory
 227     static Owner *Init(const SBuf &path, const int slotLimit);
 228
 229     StoreMap(const SBuf &aPath);
 230
 231     /// computes map entry anchor position for a given entry key
 232     sfileno fileNoByKey(const cache_key *const key) const;
 233
 234     /// Like strcmp(mapped, new), but for store entry versions/timestamps.
 235     /// Returns +2 if the mapped entry does not exist; -1/0/+1 otherwise.
 236     /// Comparison may be inaccurate unless the caller is a lock holder.
 237     int compareVersions(const sfileno oldFileno, time_t newVersion) const;
 238
 239     /// finds, locks, and returns an anchor for an empty key position,
 240     /// erasing the old entry (if any)
 241     Anchor *openForWriting(const cache_key *const key, sfileno &fileno);
 242     /// locks and returns an anchor for the empty fileno position; if
 243     /// overwriteExisting is false and the position is not empty, returns nil
 244     Anchor *openForWritingAt(sfileno fileno, bool overwriteExisting = true);
 245     /// restrict opened for writing entry to appending operations; allow reads
 246     void startAppending(const sfileno fileno);
 247     /// successfully finish creating or updating the entry at fileno pos
 248     void closeForWriting(const sfileno fileno);
 249     /// stop writing (or updating) the locked entry and start reading it
 250     void switchWritingToReading(const sfileno fileno);
 251     /// unlock and "forget" openForWriting entry, making it Empty again
 252     /// this call does not free entry slices so the caller has to do that
 253     void forgetWritingEntry(const sfileno fileno);
 254
 255     /// finds and locks the Update entry for an exclusive metadata update
 256     bool openForUpdating(Update &update, sfileno fileNoHint);
 257     /// makes updated info available to others, unlocks, and cleans up
 258     void closeForUpdating(Update &update);
 259     /// undoes partial update, unlocks, and cleans up
 260     void abortUpdating(Update &update);
 261
 262     /// only works on locked entries; returns nil unless the slice is readable
 263     const Anchor *peekAtReader(const sfileno fileno) const;
 264
 265     /// only works on locked entries; returns the corresponding Anchor
 266     const Anchor &peekAtEntry(const sfileno fileno) const;
 267
 268     /// free the entry if possible or mark it as waiting to be freed if not
 269     /// \returns whether the entry was neither empty nor marked
 270     bool freeEntry(const sfileno);
 271     /// free the entry if possible or mark it as waiting to be freed if not
 272     /// does nothing if we cannot check that the key matches the cached entry
 273     void freeEntryByKey(const cache_key *const key);
 274
 275     /// whether the entry with the given key exists and was marked as
 276     /// "waiting to be freed" some time ago
 277     bool markedForDeletion(const cache_key *const);
 278
 279     /// whether the index contains a valid readable entry with the given key
 280     bool hasReadableEntry(const cache_key *const);
 281
 282     /// opens entry (identified by key) for reading, increments read level
 283     const Anchor *openForReading(const cache_key *const key, sfileno &fileno);
 284     /// opens entry (identified by sfileno) for reading, increments read level
 285     const Anchor *openForReadingAt(const sfileno fileno);
 286     /// closes open entry after reading, decrements read level
 287     void closeForReading(const sfileno fileno);
 288
 289     /// writeable slice within an entry chain created by openForWriting()
 290     Slice &writeableSlice(const AnchorId anchorId, const SliceId sliceId);
 291     /// readable slice within an entry chain opened by openForReading()
 292     const Slice &readableSlice(const AnchorId anchorId, const SliceId sliceId) const;
 293     /// writeable anchor for the entry created by openForWriting()
 294     Anchor &writeableEntry(const AnchorId anchorId);
 295     /// readable anchor for the entry created by openForReading()
 296     const Anchor &readableEntry(const AnchorId anchorId) const;
 297
 298     /// prepare a chain-unaffiliated slice for being added to an entry chain
 299     void prepFreeSlice(const SliceId sliceId);
 300
 301     /// Returns the ID of the entry slice containing n-th byte or
 302     /// a negative ID if the entry does not store that many bytes (yet).
 303     /// Requires a read lock.
 304     SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const;
 305
 306     /// stop writing the entry, freeing its slot for others to use if possible
 307     void abortWriting(const sfileno fileno);
 308
 309     /// either finds and frees an entry with at least 1 slice or returns false
 310     bool purgeOne();
 311
 312     /// copies slice to its designated position
 313     void importSlice(const SliceId sliceId, const Slice &slice);
 314
 315     /* SwapFilenMax limits the number of entries, but not slices or slots */
 316     bool validEntry(const int n) const; ///< whether n is a valid slice coordinate
 317     bool validSlice(const int n) const; ///< whether n is a valid slice coordinate
 318     int entryCount() const; ///< number of writeable and readable entries
 319     int entryLimit() const; ///< maximum entryCount() possible
 320     int sliceLimit() const; ///< maximum number of slices possible
 321
 322     /// adds approximate current stats to the supplied ones
 323     void updateStats(ReadWriteLockStats &stats) const;
 324
 325     StoreMapCleaner *cleaner; ///< notified before a readable entry is freed
 326
 327 protected:
 328     const SBuf path; ///< cache_dir path or similar cache name; for logging
 329     Mem::Pointer<StoreMapFileNos> fileNos; ///< entry inodes (starting blocks)
 330     Mem::Pointer<StoreMapAnchors> anchors; ///< entry inodes (starting blocks)
 331     Mem::Pointer<StoreMapSlices> slices; ///< chained entry pieces positions
 332
 333 private:
 334     /// computes entry name (i.e., key hash) for a given entry key
 335     sfileno nameByKey(const cache_key *const key) const;
 336     /// computes anchor position for a given entry name
 337     sfileno fileNoByName(const sfileno name) const;
 338     void relocate(const sfileno name, const sfileno fileno);
 339
 340     Anchor &anchorAt(const sfileno fileno);
 341     const Anchor &anchorAt(const sfileno fileno) const;
 342     Anchor &anchorByKey(const cache_key *const key);
 343
 344     Slice &sliceAt(const SliceId sliceId);
 345     const Slice &sliceAt(const SliceId sliceId) const;
 346     Anchor *openForReading(Slice &s);
 347     bool openKeyless(Update::Edition &edition);
 348     void closeForUpdateFinal(Update &update);
 349
 350     typedef std::function<bool (const sfileno name)> NameFilter; // a "name"-based test
 351     bool visitVictims(const NameFilter filter);
 352
 353     void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock);
 354     void freeChainAt(SliceId sliceId, const SliceId splicingPoint);
 355 };
 356
 357 /// API for adjusting external state when dirty map slice is being freed
 358 class StoreMapCleaner
 359 {
 360 public:
 361     virtual ~StoreMapCleaner() {}
 362
 363     /// adjust slice-linked state before a locked Readable slice is erased
 364     virtual void noteFreeMapSlice(const StoreMapSliceId sliceId) = 0;
 365 };
 366
 367 } // namespace Ipc
 368
 369 // We do not reuse FileMap because we cannot control its size,
 370 // resulting in sfilenos that are pointing beyond the database.
 371
 372 #endif /* SQUID_IPC_STORE_MAP_H */
 373