src/ipc/StoreMap.h

   1 /*
   2  * Copyright (C) 1996-2016 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     std::atomic<Size> size; ///< slice contents size
  46     std::atomic<StoreMapSliceId> next; ///< ID of the next entry slice
  47 };
  48
  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
  54 {
  55 public:
  56     StoreMapAnchor();
  57
  58     /// store StoreEntry key and basics for an inode slot
  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
  64     /// undo the effects of set(), setKey(), etc., but keep locks and state
  65     void rewind();
  66
  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; }
  71     bool writing() const { return lock.writing; }
  72     bool complete() const { return !empty() && !writing(); }
  73
  74 public:
  75     mutable ReadWriteLock lock; ///< protects slot data below
  76     std::atomic<uint8_t> waitingToBeFreed; ///< may be accessed w/o a lock
  77
  78     // fields marked with [app] can be modified when appending-while-reading
  79     // fields marked with [update] can be modified when updating-while-reading
  80
  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;
  89         std::atomic<uint64_t> swap_file_sz; // [app]
  90         uint16_t refcount;
  91         uint16_t flags;
  92     } basics;
  93
  94     /// where the chain of StoreEntry slices begins [app]
  95     std::atomic<StoreMapSliceId> start;
  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;
 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) {}
 112
 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
 118 };
 119
 120 /// StoreMapSlices indexed by their slice ID.
 121 typedef StoreMapItems<StoreMapSlice> StoreMapSlices;
 122
 123 /// StoreMapAnchors (indexed by fileno) plus
 124 /// sharing-safe basic housekeeping info about Store entries
 125 class StoreMapAnchors
 126 {
 127 public:
 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
 135     std::atomic<int32_t> count; ///< current number of entries
 136     std::atomic<uint32_t> victim; ///< starting point for purge search
 137     const int capacity; ///< total number of anchors
 138     Ipc::Mem::FlexibleArray<StoreMapAnchor> items; ///< anchors storage
 139 };
 140 // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
 141
 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
 177 class StoreMapCleaner;
 178
 179 /// Manages shared Store index (e.g., locking/unlocking/freeing entries) using
 180 /// StoreMapFileNos indexed by hashed entry keys (a.k.a. entry names),
 181 /// StoreMapAnchors indexed by fileno, and
 182 /// StoreMapSlices indexed by slice ID.
 183 class StoreMap
 184 {
 185 public:
 186     typedef StoreMapFileNos FileNos;
 187     typedef StoreMapAnchor Anchor;
 188     typedef StoreMapAnchors Anchors;
 189     typedef sfileno AnchorId;
 190     typedef StoreMapSlice Slice;
 191     typedef StoreMapSlices Slices;
 192     typedef StoreMapSliceId SliceId;
 193     typedef StoreMapUpdate Update;
 194
 195 public:
 196     /// aggregates anchor and slice owners for Init() caller convenience
 197     class Owner
 198     {
 199     public:
 200         Owner();
 201         ~Owner();
 202         FileNos::Owner *fileNos;
 203         Anchors::Owner *anchors;
 204         Slices::Owner *slices;
 205     private:
 206         Owner(const Owner &); // not implemented
 207         Owner &operator =(const Owner &); // not implemented
 208     };
 209
 210     /// initialize shared memory
 211     static Owner *Init(const SBuf &path, const int slotLimit);
 212
 213     StoreMap(const SBuf &aPath);
 214
 215     /// computes map entry anchor position for a given entry key
 216     sfileno fileNoByKey(const cache_key *const key) const;
 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);
 229     /// restrict opened for writing entry to appending operations; allow reads
 230     void startAppending(const sfileno fileno);
 231     /// successfully finish creating or updating the entry at fileno pos
 232     void closeForWriting(const sfileno fileno, bool lockForReading = false);
 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
 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
 244     /// only works on locked entries; returns nil unless the slice is readable
 245     const Anchor *peekAtReader(const sfileno fileno) const;
 246
 247     /// only works on locked entries; returns the corresponding Anchor
 248     const Anchor &peekAtEntry(const sfileno fileno) const;
 249
 250     /// free the entry if possible or mark it as waiting to be freed if not
 251     void freeEntry(const sfileno fileno);
 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);
 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);
 262
 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);
 269     /// readable anchor for the entry created by openForReading()
 270     const Anchor &readableEntry(const AnchorId anchorId) const;
 271
 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
 277     /// stop writing the entry, freeing its slot for others to use if possible
 278     void abortWriting(const sfileno fileno);
 279
 280     /// either finds and frees an entry with at least 1 slice or returns false
 281     bool purgeOne();
 282
 283     /// copies slice to its designated position
 284     void importSlice(const SliceId sliceId, const Slice &slice);
 285
 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
 289     int entryCount() const; ///< number of writeable and readable entries
 290     int entryLimit() const; ///< maximum entryCount() possible
 291     int sliceLimit() const; ///< maximum number of slices possible
 292
 293     /// adds approximate current stats to the supplied ones
 294     void updateStats(ReadWriteLockStats &stats) const;
 295
 296     StoreMapCleaner *cleaner; ///< notified before a readable entry is freed
 297
 298 protected:
 299     const SBuf path; ///< cache_dir path or similar cache name; for logging
 300     Mem::Pointer<StoreMapFileNos> fileNos; ///< entry inodes (starting blocks)
 301     Mem::Pointer<StoreMapAnchors> anchors; ///< entry inodes (starting blocks)
 302     Mem::Pointer<StoreMapSlices> slices; ///< chained entry pieces positions
 303
 304 private:
 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
 311     Anchor &anchorAt(const sfileno fileno);
 312     const Anchor &anchorAt(const sfileno fileno) const;
 313     Anchor &anchorByKey(const cache_key *const key);
 314
 315     Slice &sliceAt(const SliceId sliceId);
 316     const Slice &sliceAt(const SliceId sliceId) const;
 317     Anchor *openForReading(Slice &s);
 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);
 323
 324     void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock);
 325     void freeChainAt(SliceId sliceId, const SliceId splicingPoint);
 326 };
 327
 328 /// API for adjusting external state when dirty map slice is being freed
 329 class StoreMapCleaner
 330 {
 331 public:
 332     virtual ~StoreMapCleaner() {}
 333
 334     /// adjust slice-linked state before a locked Readable slice is erased
 335     virtual void noteFreeMapSlice(const StoreMapSliceId sliceId) = 0;
 336 };
 337
 338 } // namespace Ipc
 339
 340 // We do not reuse FileMap because we cannot control its size,
 341 // resulting in sfilenos that are pointing beyond the database.
 342
 343 #endif /* SQUID_IPC_STORE_MAP_H */
 344