src/ipc/StoreMap.h

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