src/ipc/StoreMap.h

   1 /*
   2  * Copyright (C) 1996-2015 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.h"
  16 #include "store/forward.h"
  17 #include "store_key_md5.h"
  18
  19 namespace Ipc
  20 {
  21
  22 typedef int32_t StoreMapSliceId;
  23
  24 /// a piece of Store entry, linked to other pieces, forming a chain
  25 /// slices may be appended by writers while readers read the entry
  26 class StoreMapSlice
  27 {
  28 public:
  29     typedef uint32_t Size;
  30
  31     StoreMapSlice(): size(0), next(-1) {}
  32     StoreMapSlice(const StoreMapSlice &o) {
  33         size.exchange(o.size);
  34         next.exchange(o.next);
  35     }
  36
  37     StoreMapSlice &operator =(const StoreMapSlice &o) {
  38         size.store(o.size);
  39         next.store(o.next);
  40         return *this;
  41     }
  42
  43     std::atomic<Size> size; ///< slice contents size
  44     std::atomic<StoreMapSliceId> next; ///< ID of the next entry slice
  45 };
  46
  47 /// Maintains shareable information about a StoreEntry as a whole.
  48 /// An anchor points to one or more StoreEntry slices. This is the
  49 /// only lockable part of shared StoreEntry information, providing
  50 /// protection for all StoreEntry slices.
  51 class StoreMapAnchor
  52 {
  53 public:
  54     StoreMapAnchor();
  55
  56     /// store StoreEntry key and basics for an inode slot
  57     void set(const StoreEntry &anEntry);
  58
  59     void setKey(const cache_key *const aKey);
  60     bool sameKey(const cache_key *const aKey) const;
  61
  62     /// undo the effects of set(), setKey(), etc., but keep locks and state
  63     void rewind();
  64
  65     /* entry state may change immediately after calling these methods unless
  66      * the caller holds an appropriate lock */
  67     bool empty() const { return !key[0] && !key[1]; }
  68     bool reading() const { return lock.readers; }
  69     bool writing() const { return lock.writing; }
  70     bool complete() const { return !empty() && !writing(); }
  71
  72 public:
  73     mutable ReadWriteLock lock; ///< protects slot data below
  74     std::atomic<uint8_t> waitingToBeFreed; ///< may be accessed w/o a lock
  75
  76     // fields marked with [app] can be modified when appending-while-reading
  77
  78     uint64_t key[2]; ///< StoreEntry key
  79
  80     // STORE_META_STD TLV field from StoreEntry
  81     struct Basics {
  82         time_t timestamp;
  83         time_t lastref;
  84         time_t expires;
  85         time_t lastmod;
  86         std::atomic<uint64_t> swap_file_sz; // [app]
  87         uint16_t refcount;
  88         uint16_t flags;
  89     } basics;
  90
  91     /// where the chain of StoreEntry slices begins [app]
  92     std::atomic<StoreMapSliceId> start;
  93 };
  94
  95 /// an array of shareable Items
  96 /// must be the last data member or, if used as a parent class, the last parent
  97 template <class C>
  98 class StoreMapItems
  99 {
 100 public:
 101     typedef C Item;
 102     typedef Ipc::Mem::Owner< StoreMapItems<Item> > Owner;
 103
 104     explicit StoreMapItems(const int aCapacity): capacity(aCapacity), items(aCapacity) {}
 105
 106     size_t sharedMemorySize() const { return SharedMemorySize(capacity); }
 107     static size_t SharedMemorySize(const int aCapacity) { return sizeof(StoreMapItems<Item>) + aCapacity*sizeof(Item); }
 108
 109     const int capacity; ///< total number of items
 110     Ipc::Mem::FlexibleArray<Item> items; ///< storage
 111 };
 112
 113 /// StoreMapSlices indexed by their slice ID.
 114 typedef StoreMapItems<StoreMapSlice> StoreMapSlices;
 115
 116 /// StoreMapAnchors indexed by entry fileno plus
 117 /// sharing-safe basic housekeeping info about Store entries
 118 class StoreMapAnchors
 119 {
 120 public:
 121     typedef Ipc::Mem::Owner< StoreMapAnchors > Owner;
 122
 123     explicit StoreMapAnchors(const int aCapacity);
 124
 125     size_t sharedMemorySize() const;
 126     static size_t SharedMemorySize(const int anAnchorLimit);
 127
 128     std::atomic<int32_t> count; ///< current number of entries
 129     std::atomic<uint32_t> victim; ///< starting point for purge search
 130     const int capacity; ///< total number of anchors
 131     Ipc::Mem::FlexibleArray<StoreMapAnchor> items; ///< anchors storage
 132 };
 133 // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors
 134
 135 class StoreMapCleaner;
 136
 137 /// Manages shared Store index (e.g., locking/unlocking/freeing entries) using
 138 /// StoreMapAnchors indexed by their keys and
 139 /// StoreMapSlices indexed by their slide ID.
 140 class StoreMap
 141 {
 142 public:
 143     typedef StoreMapAnchor Anchor;
 144     typedef StoreMapAnchors Anchors;
 145     typedef sfileno AnchorId;
 146     typedef StoreMapSlice Slice;
 147     typedef StoreMapSlices Slices;
 148     typedef StoreMapSliceId SliceId;
 149
 150 public:
 151     /// aggregates anchor and slice owners for Init() caller convenience
 152     class Owner
 153     {
 154     public:
 155         Owner();
 156         ~Owner();
 157         Anchors::Owner *anchors;
 158         Slices::Owner *slices;
 159     private:
 160         Owner(const Owner &); // not implemented
 161         Owner &operator =(const Owner &); // not implemented
 162     };
 163
 164     /// initialize shared memory
 165     static Owner *Init(const SBuf &path, const int slotLimit);
 166
 167     StoreMap(const SBuf &aPath);
 168
 169     /// computes map entry position for a given entry key
 170     sfileno anchorIndexByKey(const cache_key *const key) const;
 171
 172     /// Like strcmp(mapped, new), but for store entry versions/timestamps.
 173     /// Returns +2 if the mapped entry does not exist; -1/0/+1 otherwise.
 174     /// Comparison may be inaccurate unless the caller is a lock holder.
 175     int compareVersions(const sfileno oldFileno, time_t newVersion) const;
 176
 177     /// finds, locks, and returns an anchor for an empty key position,
 178     /// erasing the old entry (if any)
 179     Anchor *openForWriting(const cache_key *const key, sfileno &fileno);
 180     /// locks and returns an anchor for the empty fileno position; if
 181     /// overwriteExisting is false and the position is not empty, returns nil
 182     Anchor *openForWritingAt(sfileno fileno, bool overwriteExisting = true);
 183     /// restrict opened for writing entry to appending operations; allow reads
 184     void startAppending(const sfileno fileno);
 185     /// successfully finish creating or updating the entry at fileno pos
 186     void closeForWriting(const sfileno fileno, bool lockForReading = false);
 187     /// unlock and "forget" openForWriting entry, making it Empty again
 188     /// this call does not free entry slices so the caller has to do that
 189     void forgetWritingEntry(const sfileno fileno);
 190
 191     /// only works on locked entries; returns nil unless the slice is readable
 192     const Anchor *peekAtReader(const sfileno fileno) const;
 193
 194     /// only works on locked entries; returns the corresponding Anchor
 195     const Anchor &peekAtEntry(const sfileno fileno) const;
 196
 197     /// free the entry if possible or mark it as waiting to be freed if not
 198     void freeEntry(const sfileno fileno);
 199     /// free the entry if possible or mark it as waiting to be freed if not
 200     /// does nothing if we cannot check that the key matches the cached entry
 201     void freeEntryByKey(const cache_key *const key);
 202
 203     /// opens entry (identified by key) for reading, increments read level
 204     const Anchor *openForReading(const cache_key *const key, sfileno &fileno);
 205     /// opens entry (identified by sfileno) for reading, increments read level
 206     const Anchor *openForReadingAt(const sfileno fileno);
 207     /// closes open entry after reading, decrements read level
 208     void closeForReading(const sfileno fileno);
 209
 210     /// writeable slice within an entry chain created by openForWriting()
 211     Slice &writeableSlice(const AnchorId anchorId, const SliceId sliceId);
 212     /// readable slice within an entry chain opened by openForReading()
 213     const Slice &readableSlice(const AnchorId anchorId, const SliceId sliceId) const;
 214     /// writeable anchor for the entry created by openForWriting()
 215     Anchor &writeableEntry(const AnchorId anchorId);
 216     /// readable anchor for the entry created by openForReading()
 217     const Anchor &readableEntry(const AnchorId anchorId) const;
 218
 219     /// stop writing the entry, freeing its slot for others to use if possible
 220     void abortWriting(const sfileno fileno);
 221
 222     /// either finds and frees an entry with at least 1 slice or returns false
 223     bool purgeOne();
 224
 225     /// copies slice to its designated position
 226     void importSlice(const SliceId sliceId, const Slice &slice);
 227
 228     /* SwapFilenMax limits the number of entries, but not slices or slots */
 229     bool validEntry(const int n) const; ///< whether n is a valid slice coordinate
 230     bool validSlice(const int n) const; ///< whether n is a valid slice coordinate
 231     int entryCount() const; ///< number of writeable and readable entries
 232     int entryLimit() const; ///< maximum entryCount() possible
 233     int sliceLimit() const; ///< maximum number of slices possible
 234
 235     /// adds approximate current stats to the supplied ones
 236     void updateStats(ReadWriteLockStats &stats) const;
 237
 238     StoreMapCleaner *cleaner; ///< notified before a readable entry is freed
 239
 240 protected:
 241     const SBuf path; ///< cache_dir path or similar cache name; for logging
 242     Mem::Pointer<StoreMapAnchors> anchors; ///< entry inodes (starting blocks)
 243     Mem::Pointer<StoreMapSlices> slices; ///< chained entry pieces positions
 244
 245 private:
 246     Anchor &anchorAt(const sfileno fileno);
 247     const Anchor &anchorAt(const sfileno fileno) const;
 248     Anchor &anchorByKey(const cache_key *const key);
 249
 250     Slice &sliceAt(const SliceId sliceId);
 251     const Slice &sliceAt(const SliceId sliceId) const;
 252     Anchor *openForReading(Slice &s);
 253
 254     void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock);
 255 };
 256
 257 /// API for adjusting external state when dirty map slice is being freed
 258 class StoreMapCleaner
 259 {
 260 public:
 261     virtual ~StoreMapCleaner() {}
 262
 263     /// adjust slice-linked state before a locked Readable slice is erased
 264     virtual void noteFreeMapSlice(const StoreMapSliceId sliceId) = 0;
 265 };
 266
 267 } // namespace Ipc
 268
 269 // We do not reuse FileMap because we cannot control its size,
 270 // resulting in sfilenos that are pointing beyond the database.
 271
 272 #endif /* SQUID_IPC_STORE_MAP_H */
 273