src/ipc/StoreMap.h

   1 /*
   2  * Copyright (C) 1996-2023 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_SRC_IPC_STOREMAP_H
  10 #define SQUID_SRC_IPC_STOREMAP_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     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
 144     /// reset all items to the same value
 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; ///< total number of items
 152     Ipc::Mem::FlexibleArray<Item> items; ///< storage
 153 };
 154
 155 /// StoreMapSlices indexed by their slice ID.
 156 typedef StoreMapItems<StoreMapSlice> StoreMapSlices;
 157
 158 /// StoreMapAnchors (indexed by fileno) plus
 159 /// sharing-safe basic housekeeping info about Store entries
 160 class StoreMapAnchors
 161 {
 162 public:
 163     typedef Ipc::Mem::Owner< StoreMapAnchors > Owner;
 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; ///< 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
 174 };
 175 // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
 176
 177 /// StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash)
 178 typedef StoreMapItems< std::atomic<sfileno> > StoreMapFileNos;
 179
 180 /// Aggregates information required for updating entry metadata and headers.
 181 class StoreMapUpdate
 182 {
 183 public:
 184     /// During an update, the stored entry has two editions: stale and fresh.
 185     class Edition
 186     {
 187     public:
 188         Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {}
 189
 190         /// whether this entry edition is currently used/initialized
 191         explicit operator bool() const { return anchor; }
 192
 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
 196
 197         /// the last slice in the chain still containing metadata/headers
 198         StoreMapSliceId splicingPoint;
 199     };
 200
 201     explicit StoreMapUpdate(StoreEntry *anEntry);
 202     StoreMapUpdate(const StoreMapUpdate &other);
 203     ~StoreMapUpdate();
 204
 205     StoreMapUpdate &operator =(const StoreMapUpdate &other) = delete;
 206
 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
 210 };
 211
 212 class StoreMapCleaner;
 213
 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.
 218 class StoreMap
 219 {
 220 public:
 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;
 229
 230 public:
 231     /// aggregates anchor and slice owners for Init() caller convenience
 232     class Owner
 233     {
 234     public:
 235         Owner();
 236         ~Owner();
 237         FileNos::Owner *fileNos;
 238         Anchors::Owner *anchors;
 239         Slices::Owner *slices;
 240     private:
 241         Owner(const Owner &); // not implemented
 242         Owner &operator =(const Owner &); // not implemented
 243     };
 244
 245     /// initialize shared memory
 246     static Owner *Init(const SBuf &path, const int slotLimit);
 247
 248     StoreMap(const SBuf &aPath);
 249
 250     /// computes map entry anchor position for a given entry key
 251     sfileno fileNoByKey(const cache_key *const key) const;
 252
 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;
 257
 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);
 273
 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);
 280
 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;
 284
 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;
 288
 289     /// the caller must hold a lock on the entry
 290     /// \returns the corresponding Anchor
 291     const Anchor &peekAtEntry(const sfileno fileno) const;
 292
 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);
 299
 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);
 303
 304     /// whether the index contains a valid readable entry with the given key
 305     bool hasReadableEntry(const cache_key *const);
 306
 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);
 315
 316     /// openForReading() but creates a new entry if there is no old one
 317     const Anchor *openOrCreateForReading(const cache_key *, sfileno &);
 318
 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;
 327
 328     /// prepare a chain-unaffiliated slice for being added to an entry chain
 329     void prepFreeSlice(const SliceId sliceId);
 330
 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;
 335
 336     /// stop writing the entry, freeing its slot for others to use if possible
 337     void abortWriting(const sfileno fileno);
 338
 339     /// either finds and frees an entry with at least 1 slice or returns false
 340     bool purgeOne();
 341
 342     /// validates locked hit metadata and calls freeEntry() for invalid entries
 343     /// \returns whether hit metadata is correct
 344     bool validateHit(const sfileno);
 345
 346     void disableHitValidation() { hitValidation = false; }
 347
 348     /// copies slice to its designated position
 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; ///< 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
 357
 358     /// adds approximate current stats to the supplied ones
 359     void updateStats(ReadWriteLockStats &stats) const;
 360
 361     StoreMapCleaner *cleaner; ///< notified before a readable entry is freed
 362
 363 protected:
 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
 368
 369 private:
 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);
 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;
 382     Anchor *openForReading(Slice &s);
 383     bool openKeyless(Update::Edition &edition);
 384     void closeForUpdateFinal(Update &update);
 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
 392     /// whether paranoid_hit_validation should be performed
 393     bool hitValidation;
 394 };
 395
 396 /// API for adjusting external state when dirty map slice is being freed
 397 class StoreMapCleaner
 398 {
 399 public:
 400     virtual ~StoreMapCleaner() {}
 401
 402     /// adjust slice-linked state before a locked Readable slice is erased
 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_SRC_IPC_STOREMAP_H */
 412