src/ipc/mem/PageStack.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_IPC_MEM_PAGE_STACK_H
  10 #define SQUID_IPC_MEM_PAGE_STACK_H
  11
  12 #include "ipc/mem/FlexibleArray.h"
  13 #include "ipc/mem/forward.h"
  14
  15 #include <atomic>
  16 #include <limits>
  17
  18 namespace Ipc
  19 {
  20
  21 namespace Mem
  22 {
  23
  24 class PageId;
  25
  26 class IdSetPosition;
  27 typedef enum { dirNone, dirLeft, dirRight, dirEnd } IdSetNavigationDirection;
  28
  29 /// basic IdSet storage parameters, extracted here to keep them constant
  30 class IdSetMeasurements
  31 {
  32 public:
  33     /// we need to fit two size_type counters into one 64-bit lockless atomic
  34     typedef uint32_t size_type;
  35
  36     explicit IdSetMeasurements(size_type capacity);
  37
  38     /// the maximum number of pages our tree is allowed to store
  39     size_type capacity = 0;
  40
  41     /// the number of leaf nodes that satisfy capacity requirements
  42     size_type requestedLeafNodeCount = 0;
  43
  44     size_type treeHeight = 0; ///< total number of levels, including the leaf level
  45     size_type leafNodeCount = 0; ///< the number of nodes at the leaf level
  46     size_type innerLevelCount = 0; ///< all levels except the leaf level
  47
  48     /// the total number of nodes at all levels
  49     size_type nodeCount() const { return leafNodeCount ? leafNodeCount*2 -1 : 0; }
  50 };
  51
  52 /// a shareable set of positive uint32_t IDs with O(1) insertion/removal ops
  53 class IdSet
  54 {
  55 public:
  56     using size_type = IdSetMeasurements::size_type;
  57     using Position = IdSetPosition;
  58     using NavigationDirection = IdSetNavigationDirection;
  59
  60     /// memory size required to store a tree with the given capacity
  61     static size_t MemorySize(size_type capacity);
  62
  63     explicit IdSet(size_type capacity);
  64
  65     /// populates the allocated tree with the requested capacity IDs
  66     /// optimized to run without atomic protection
  67     void makeFullBeforeSharing();
  68
  69     /// finds/extracts (into the given `id`) an ID value and returns true
  70     /// \retval false no IDs are left
  71     bool pop(size_type &id);
  72
  73     /// makes `id` value available to future pop() callers
  74     void push(size_type id);
  75
  76     const IdSetMeasurements measurements;
  77
  78 private:
  79     typedef uint64_t Node; ///< either leaf or intermediate node
  80     typedef std::atomic<Node> StoredNode; ///< a Node stored in shared memory
  81
  82     /* optimization: these initialization methods bypass atomic protections */
  83     void fillAllNodes();
  84     void truncateExtras();
  85     Node *valueAddress(Position);
  86     size_type innerTruncate(Position pos, NavigationDirection dir, size_type toSubtract);
  87     void leafTruncate(Position pos, size_type idsToKeep);
  88
  89     void innerPush(Position, NavigationDirection);
  90     NavigationDirection innerPop(Position);
  91
  92     void leafPush(Position, size_type id);
  93     size_type leafPop(Position);
  94
  95     Position ascend(Position);
  96     Position descend(Position, NavigationDirection);
  97
  98     StoredNode &nodeAt(Position);
  99
 100     /// the entire binary tree flattened into an array
 101     FlexibleArray<StoredNode> nodes_;
 102     // No more data members should follow! See FlexibleArray<> for details.
 103 };
 104
 105 /// Atomic container of "free" PageIds. Detects (some) double-free bugs.
 106 /// Assumptions: All page numbers are unique, positive, with a known maximum.
 107 /// A pushed page may not become available immediately but is never truly lost.
 108 class PageStack
 109 {
 110 public:
 111     typedef std::atomic<size_t> Levels_t;
 112
 113     // XXX: The actual type may have been on PagePool::Init() but may conflict
 114     // with PageLimit(), StoreMapSliceId, Rock::SwapDirRr::slotLimitActual(),
 115     // Rock::SlotId, PageId::number, etc.
 116     /// the number of (free and/or used) pages in a stack
 117     typedef unsigned int PageCount;
 118
 119     // XXX: poolId, pageSize look misplaced due to messy separation of PagePool
 120     // (which should support multiple Segments but does not) and PageStack
 121     // (which should not calculate the Segment size but does) duties.
 122     /// PageStack construction and SharedMemorySize calculation parameters
 123     class Config {
 124     public:
 125         uint32_t poolId = 0; ///< pool ID
 126         size_t pageSize = 0; ///< page size, used to calculate shared memory size
 127         PageCount capacity = 0; ///< the maximum number of pages
 128
 129         /// whether a newly created PageStack should be prefilled with PageIds
 130         bool createFull = false;
 131     };
 132
 133     explicit PageStack(const Config &);
 134
 135     PageCount capacity() const { return config_.capacity; }
 136     size_t pageSize() const { return config_.pageSize; }
 137     /// an approximate number of free pages
 138     PageCount size() const { return size_.load(); }
 139
 140     /// sets value and returns true unless no free page numbers are found
 141     bool pop(PageId &page);
 142     /// makes value available as a free page number to future pop() callers
 143     void push(PageId &page);
 144
 145     bool pageIdIsValid(const PageId &page) const;
 146
 147     /// total shared memory size required to share
 148     static size_t SharedMemorySize(const Config &);
 149     size_t sharedMemorySize() const;
 150
 151     /// shared memory size required only by PageStack, excluding
 152     /// shared counters and page data
 153     static size_t StackSize(const PageCount capacity);
 154     size_t stackSize() const;
 155
 156     /// \returns the number of padding bytes to align PagePool::theLevels array
 157     static size_t LevelsPaddingSize(const PageCount capacity);
 158     size_t levelsPaddingSize() const { return LevelsPaddingSize(config_.capacity); }
 159
 160     /**
 161      * The following functions return PageStack IDs for the corresponding
 162      * PagePool or a similar PageStack user. The exact values are unimportant,
 163      * but their uniqueness and stability eases debugging.
 164      */
 165
 166     /// stack of free cache_mem slot positions
 167     static PoolId IdForMemStoreSpace() { return 10; }
 168     /// multipurpose PagePool of shared memory pages
 169     static PoolId IdForMultipurposePool() { return 200; } // segments could use 2xx
 170     /// stack of free rock cache_dir slot numbers
 171     static PoolId IdForSwapDirSpace(const int dirIdx) { return 900 + dirIdx + 1; }
 172
 173 private:
 174     const Config config_;
 175     /// a lower bound for the number of free pages (for debugging purposes)
 176     std::atomic<PageCount> size_;
 177
 178     IdSet ids_; ///< free pages (valid with positive capacity_)
 179     // No more data members should follow! See IdSet for details.
 180 };
 181
 182 } // namespace Mem
 183
 184 } // namespace Ipc
 185
 186 #endif // SQUID_IPC_MEM_PAGE_STACK_H
 187