]>
Commit | Line | Data |
---|---|---|
be17aa82 | 1 | /* |
b8ae064d | 2 | * Copyright (C) 1996-2023 The Squid Software Foundation and contributors |
bbc27441 AJ |
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. | |
be17aa82 AR |
7 | */ |
8 | ||
9 | #ifndef SQUID_IPC_MEM_PAGE_STACK_H | |
10 | #define SQUID_IPC_MEM_PAGE_STACK_H | |
11 | ||
3a8c5551 | 12 | #include "ipc/mem/FlexibleArray.h" |
1fe7f70f | 13 | #include "ipc/mem/forward.h" |
be17aa82 | 14 | |
2253ee0b | 15 | #include <atomic> |
c3408a33 | 16 | #include <limits> |
2253ee0b | 17 | |
9199139f AR |
18 | namespace Ipc |
19 | { | |
be17aa82 | 20 | |
9199139f AR |
21 | namespace Mem |
22 | { | |
be17aa82 | 23 | |
68353d5a DK |
24 | class PageId; |
25 | ||
a5860854 AR |
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 | |
c3408a33 EB |
54 | { |
55 | public: | |
a5860854 AR |
56 | using size_type = IdSetMeasurements::size_type; |
57 | using Position = IdSetPosition; | |
58 | using NavigationDirection = IdSetNavigationDirection; | |
c3408a33 | 59 | |
a5860854 AR |
60 | /// memory size required to store a tree with the given capacity |
61 | static size_t MemorySize(size_type capacity); | |
c3408a33 | 62 | |
a5860854 | 63 | explicit IdSet(size_type capacity); |
c3408a33 | 64 | |
a5860854 AR |
65 | /// populates the allocated tree with the requested capacity IDs |
66 | /// optimized to run without atomic protection | |
67 | void makeFullBeforeSharing(); | |
c3408a33 | 68 | |
a5860854 AR |
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); | |
c3408a33 | 72 | |
a5860854 AR |
73 | /// makes `id` value available to future pop() callers |
74 | void push(size_type id); | |
75 | ||
76 | const IdSetMeasurements measurements; | |
c3408a33 EB |
77 | |
78 | private: | |
a5860854 AR |
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. | |
c3408a33 EB |
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. | |
9199139f AR |
108 | class PageStack |
109 | { | |
be17aa82 | 110 | public: |
2a10e977 | 111 | typedef std::atomic<size_t> Levels_t; |
be17aa82 | 112 | |
c3408a33 EB |
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 | ||
f670688c EB |
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 | }; | |
be17aa82 | 132 | |
f670688c EB |
133 | explicit PageStack(const Config &); |
134 | ||
135 | PageCount capacity() const { return config_.capacity; } | |
136 | size_t pageSize() const { return config_.pageSize; } | |
c3408a33 EB |
137 | /// an approximate number of free pages |
138 | PageCount size() const { return size_.load(); } | |
b940ff87 | 139 | |
be17aa82 | 140 | /// sets value and returns true unless no free page numbers are found |
68353d5a | 141 | bool pop(PageId &page); |
be17aa82 | 142 | /// makes value available as a free page number to future pop() callers |
68353d5a DK |
143 | void push(PageId &page); |
144 | ||
145 | bool pageIdIsValid(const PageId &page) const; | |
146 | ||
147 | /// total shared memory size required to share | |
f670688c | 148 | static size_t SharedMemorySize(const Config &); |
68353d5a | 149 | size_t sharedMemorySize() const; |
be17aa82 | 150 | |
551f8a18 DK |
151 | /// shared memory size required only by PageStack, excluding |
152 | /// shared counters and page data | |
c3408a33 | 153 | static size_t StackSize(const PageCount capacity); |
551f8a18 DK |
154 | size_t stackSize() const; |
155 | ||
2a10e977 | 156 | /// \returns the number of padding bytes to align PagePool::theLevels array |
c3408a33 | 157 | static size_t LevelsPaddingSize(const PageCount capacity); |
f670688c | 158 | size_t levelsPaddingSize() const { return LevelsPaddingSize(config_.capacity); } |
2a10e977 | 159 | |
1fe7f70f EB |
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 | ||
be17aa82 | 173 | private: |
f670688c | 174 | const Config config_; |
c3408a33 EB |
175 | /// a lower bound for the number of free pages (for debugging purposes) |
176 | std::atomic<PageCount> size_; | |
be17aa82 | 177 | |
a5860854 AR |
178 | IdSet ids_; ///< free pages (valid with positive capacity_) |
179 | // No more data members should follow! See IdSet for details. | |
be17aa82 AR |
180 | }; |
181 | ||
182 | } // namespace Mem | |
183 | ||
184 | } // namespace Ipc | |
185 | ||
186 | #endif // SQUID_IPC_MEM_PAGE_STACK_H | |
f53969cc | 187 |