PageStack.cc
Go to the documentation of this file.
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/* DEBUG: section 54 Interprocess Communication */
10
11#include "squid.h"
12
13#include "debug/Stream.h"
14#include "ipc/mem/Page.h"
15#include "ipc/mem/PageStack.h"
16
17#include <cmath>
18#include <algorithm>
19#include <limits>
20
21/*
22
23Ipc::Mem::IdSet and related code maintains a perfect full binary tree structure:
24
25 (l,r)
26 /\
27 (ll,lr) (rl,rr)
28 /\ /\
29 L1 L2 L3 L4
30
31where
32
33 * (l,r) is an always-present root node;
34 * inner nodes, including the root one, count the total number of available
35 IDs in the leaf nodes of the left and right subtrees (e.g., r = rl + rr);
36 * leaf nodes are bitsets of available IDs (e.g., rl = number of 1s in L3);
37 all leaf nodes are always present.
38
39The above sample tree would be stored as seven 64-bit atomic integers:
40 (l,r), (ll,lr), (rl,rr), L1, L2, L3, L4
41
42*/
43
44namespace Ipc
45{
46
47namespace Mem
48{
49
51static const IdSet::size_type BitsPerLeaf = 64;
52
54{
55public:
57
58 IdSetPosition() = default;
59 IdSetPosition(size_type aLevel, size_type anOffset);
60
62 bool atRoot() const { return !level && !offset; }
63
66
71};
72
75{
76public:
78 typedef uint64_t Packed;
79
81 static IdSetInnerNode Unpack(Packed packed);
82
83 IdSetInnerNode() = default;
85
87 Packed pack() const { return (static_cast<Packed>(left) << 32) | right; }
88
91};
92
93} // namespace Mem
94
95} // namespace Ipc
96
97/* Ipc::Mem::IdSetPosition */
98
100 level(aLevel),
101 offset(anOffset)
102{
103}
104
107{
108 return (offset % 2 == 0) ? dirLeft : dirRight;
109}
110
111/* Ipc::Mem::IdSetMeasurements */
112
114{
115 capacity = aCapacity;
116
117 // For simplicity, we want a perfect full binary tree with root and leaves.
118 // We could compute all this with log2() calls, but rounding and honoring
119 // root+leaves minimums make that approach more complex than this fast loop.
120 requestedLeafNodeCount = (capacity + (BitsPerLeaf-1))/BitsPerLeaf;
121 treeHeight = 1+1; // the root level plus the leaf nodes level
122 leafNodeCount = 2; // the root node can have only two leaf nodes
123 while (leafNodeCount < requestedLeafNodeCount) {
124 leafNodeCount *= 2;
125 ++treeHeight;
126 }
127 innerLevelCount = treeHeight - 1;
128
129 debugs(54, 5, "rounded capacity up from " << capacity << " to " << (leafNodeCount*BitsPerLeaf));
130
131 // we do (1 << level) when computing 32-bit IdSetInnerNode::left
132 assert(treeHeight < 32);
133}
134
135/* Ipc::Mem::IdSetInnerNode */
136
138 left(aLeft),
139 right(aRight)
140{
141}
142
145{
146 // truncation during the cast is intentional here
147 return IdSetInnerNode(packed >> 32, static_cast<uint32_t>(packed));
148}
149
150/* Ipc::Mem::IdSet */
151
153 measurements(capacity),
154 nodes_(capacity)
155{
156 // For valueAddress() to be able to return a raw uint64_t pointer, the
157 // atomic wrappers in nodes_ must be zero-size. Check the best we can. Once.
158 static_assert(sizeof(StoredNode) == sizeof(Node), "atomic locks use no storage");
159 assert(StoredNode().is_lock_free());
160}
161
162void
164{
165 // initially, all IDs are marked as available
166 fillAllNodes();
167
168 // ... but IDs beyond the requested capacity should not be available
169 if (measurements.capacity != measurements.leafNodeCount*BitsPerLeaf)
170 truncateExtras();
171}
172
175void
177{
178 // leaf nodes
179 auto pos = Position(measurements.treeHeight-1, 0);
180 const auto allOnes = ~uint64_t(0);
181 std::fill_n(valueAddress(pos), measurements.leafNodeCount, allOnes);
182
183 // inner nodes, starting from the bottom of the tree
184 auto nodesAtLevel = measurements.leafNodeCount/2;
185 auto pagesBelow = BitsPerLeaf;
186 do {
187 pos = ascend(pos);
188 const auto value = IdSetInnerNode(pagesBelow, pagesBelow).pack();
189 std::fill_n(valueAddress(pos), nodesAtLevel, value);
190 nodesAtLevel /= 2;
191 pagesBelow *= 2;
192 } while (!pos.atRoot());
193}
194
196void
198{
199 // leaf nodes
200 // start with the left-most leaf that should have some 0s; it may even have
201 // no 1s at all (i.e. be completely unused)
202 auto pos = Position(measurements.treeHeight-1, measurements.capacity/BitsPerLeaf);
203 leafTruncate(pos, measurements.capacity % BitsPerLeaf);
204 const auto rightLeaves = measurements.leafNodeCount - measurements.requestedLeafNodeCount;
205 // this zeroing of the leaf nodes to the right from pos is only necessary to
206 // trigger asserts if the code dealing with the inner node counters is buggy
207 if (rightLeaves > 1)
208 std::fill_n(valueAddress(pos) + 1, rightLeaves-1, 0);
209
210 // inner nodes, starting from the bottom of the tree; optimization: only
211 // adjusting nodes on the way up from the first leaf-with-0s position
212 auto toSubtract = BitsPerLeaf - (measurements.capacity % BitsPerLeaf);
213 do {
214 const auto direction = pos.ascendDirection();
215 pos = ascend(pos);
216 toSubtract = innerTruncate(pos, direction, toSubtract);
217 } while (!pos.atRoot());
218}
219
221void
223{
224 Node &node = *valueAddress(pos); // no auto to simplify the asserts() below
226 static_assert(std::is_unsigned<Node>::value, "right shift prepends 0s");
227 node >>= BitsPerLeaf - idsToKeep;
228 // node can be anything here, including all 0s and all 1s
229}
230
236{
237 auto *valuePtr = valueAddress(pos);
238 auto value = IdSetInnerNode::Unpack(*valuePtr);
239 size_type toSubtractNext = 0;
240 if (dir == dirLeft) {
241 toSubtractNext = toSubtract + value.right;
242 assert(value.left >= toSubtract);
243 value.left -= toSubtract;
244 value.right = 0;
245 } else {
246 assert(dir == dirRight);
247 toSubtractNext = toSubtract;
248 assert(value.right >= toSubtract);
249 // value.left is unchanged; we have only adjusted the right branch
250 value.right -= toSubtract;
251 }
252 *valuePtr = value.pack();
253 return toSubtractNext;
254}
255
257void
259{
260 // either left or right component will be true/1; the other will be false/0
261 const auto increment = IdSetInnerNode(dir == dirLeft, dir == dirRight).pack();
262 const auto previousValue = nodeAt(pos).fetch_add(increment);
263 // no overflows
264 assert(previousValue <= std::numeric_limits<Node>::max() - increment);
265}
266
271{
272 NavigationDirection direction = dirNone;
273
274 auto &node = nodeAt(pos);
275 auto oldValue = node.load();
276 IdSetInnerNode newValue;
277 do {
278 newValue = IdSetInnerNode::Unpack(oldValue);
279 if (newValue.left) {
280 --newValue.left;
281 direction = dirLeft;
282 } else if (newValue.right) {
283 --newValue.right;
284 direction = dirRight;
285 } else {
286 return dirEnd;
287 }
288 } while (!node.compare_exchange_weak(oldValue, newValue.pack()));
289
290 assert(direction == dirLeft || direction == dirRight);
291 return direction;
292}
293
295void
297{
298 const auto mask = Node(1) << (id % BitsPerLeaf);
299 const auto oldValue = nodeAt(pos).fetch_or(mask);
300 // this was a new entry
301 assert((oldValue & mask) == 0);
302}
303
304// TODO: After switching to C++20, use countr_zero() which may compile to a
305// single TZCNT assembly instruction on modern CPUs.
307static inline
308int trailingZeros(uint64_t x)
309{
310 if (!x)
311 return 64;
312 int count = 0;
313 for (uint64_t mask = 1; !(x & mask); mask <<= 1)
314 ++count;
315 return count;
316}
317
321{
322 auto &node = nodeAt(pos);
323 auto oldValue = node.load();
324 Node newValue;
325 do {
326 assert(oldValue > 0);
327 const auto mask = oldValue - 1; // flips the rightmost 1 and trailing 0s
328 newValue = oldValue & mask; // clears the rightmost 1
329 } while (!node.compare_exchange_weak(oldValue, newValue));
330
331 return pos.offset*BitsPerLeaf + trailingZeros(oldValue);
332}
333
337{
338 assert(pos.level > 0);
339 --pos.level;
340 pos.offset /= 2;
341 return pos;
342}
343
348{
349 assert(pos.level < measurements.treeHeight);
350 ++pos.level;
351
352 pos.offset *= 2;
353 if (direction == dirRight)
354 ++pos.offset;
355 else
356 assert(direction == dirLeft);
357
358 return pos;
359}
360
364{
365 assert(pos.level < measurements.treeHeight);
366 // n = 2^(h+1) - 1 with h = level-1
367 const auto nodesAbove = (1U << pos.level) - 1;
368
369 // the second clause is for the special case of a root node
370 assert(pos.offset < nodesAbove*2 || (pos.atRoot() && nodesAbove == 0));
371 const auto nodesToTheLeft = pos.offset;
372
373 const size_t nodesBefore = nodesAbove + nodesToTheLeft;
374 assert(nodesBefore < measurements.nodeCount());
375 return nodes_[nodesBefore];
376}
377
381{
382 // IdSet() constructor asserts that this frequent reinterpret_cast is safe
383 return &reinterpret_cast<Node&>(nodeAt(pos));
384}
385
386bool
388{
389 Position rootPos;
390 const auto directionFromRoot = innerPop(rootPos);
391 if (directionFromRoot == dirEnd)
392 return false; // an empty tree
393
394 auto pos = descend(rootPos, directionFromRoot);
395 for (size_t level = 1; level < measurements.innerLevelCount; ++level) {
396 const auto direction = innerPop(pos);
397 pos = descend(pos, direction);
398 }
399
400 id = leafPop(pos);
401 return true;
402}
403
404void
406{
407 const auto offsetAtLeafLevel = id/BitsPerLeaf;
408 auto pos = Position(measurements.innerLevelCount, offsetAtLeafLevel);
409 leafPush(pos, id);
410
411 do {
412 const auto direction = pos.ascendDirection();
413 pos = ascend(pos);
414 innerPush(pos, direction);
415 } while (!pos.atRoot());
416}
417
418size_t
420{
421 const IdSetMeasurements measurements(capacity);
422 // Adding sizeof(IdSet) double-counts the first node but it is better to
423 // overestimate (a little) than to underestimate our memory needs due to
424 // padding, new data members, etc.
425 return sizeof(IdSet) + measurements.nodeCount() * sizeof(StoredNode);
426}
427
428/* Ipc::Mem::PageStack */
429
431 config_(config),
432 size_(0),
433 ids_(config_.capacity)
434{
435 if (config.createFull) {
438 }
439}
440
441bool
443{
444 assert(!page);
445
446 if (!config_.capacity)
447 return false;
448
449 IdSet::size_type pageIndex = 0;
450 if (!ids_.pop(pageIndex))
451 return false;
452
453 // must decrement after removing the page to avoid underflow
454 const auto newSize = --size_;
455 assert(newSize < config_.capacity);
456
457 page.number = pageIndex + 1;
458 page.pool = config_.poolId;
459 debugs(54, 8, page << " size: " << newSize);
460 assert(pageIdIsValid(page));
461 return true;
462}
463
464void
466{
467 debugs(54, 8, page);
468 assert(page);
469 assert(pageIdIsValid(page));
470
471 // must increment before inserting the page to avoid underflow in pop()
472 const auto newSize = ++size_;
473 assert(newSize <= config_.capacity);
474
475 const auto pageIndex = page.number - 1;
476 ids_.push(pageIndex);
477
478 debugs(54, 8, page << " size: " << newSize);
479 page = PageId();
480}
481
482bool
484{
485 return page.pool == config_.poolId &&
486 0 < page.number && page.number <= capacity();
487}
488
489size_t
491{
492 return SharedMemorySize(config_);
493}
494
495size_t
497{
498 const auto levelsSize = PageId::maxPurpose * sizeof(Levels_t);
499 const size_t pagesDataSize = cfg.capacity * cfg.pageSize;
500 return StackSize(cfg.capacity) + pagesDataSize + levelsSize;
501}
502
503size_t
505{
506 // Adding sizeof(PageStack) double-counts the fixed portion of the ids_ data
507 // member but it is better to overestimate (a little) than to underestimate
508 // our memory needs due to padding, new data members, etc.
509 return sizeof(PageStack) + IdSet::MemorySize(capacity);
510}
511
512size_t
514{
515 return StackSize(config_.capacity);
516}
517
518size_t
520{
521 const auto displacement = StackSize(capacity) % alignof(Levels_t);
522 return displacement ? alignof(Levels_t) - displacement : 0;
523}
524
static int trailingZeros(uint64_t x)
a temporary C++20 countr_zero() replacement
Definition: PageStack.cc:308
#define assert(EX)
Definition: assert.h:17
a helper class to perform inner node manipulation for IdSet
Definition: PageStack.cc:75
Packed pack() const
returns a serializes value suitable for shared memory storage
Definition: PageStack.cc:87
size_type right
the number of available IDs in the right subtree
Definition: PageStack.cc:90
static IdSetInnerNode Unpack(Packed packed)
de-serializes a given value
Definition: PageStack.cc:144
uint64_t Packed
(atomically) stored serialized value
Definition: PageStack.cc:78
size_type left
the number of available IDs in the left subtree
Definition: PageStack.cc:89
IdSet::size_type size_type
Definition: PageStack.cc:77
basic IdSet storage parameters, extracted here to keep them constant
Definition: PageStack.h:31
uint32_t size_type
we need to fit two size_type counters into one 64-bit lockless atomic
Definition: PageStack.h:34
IdSetMeasurements(size_type capacity)
Definition: PageStack.cc:113
size_type nodeCount() const
the total number of nodes at all levels
Definition: PageStack.h:49
IdSetNavigationDirection ascendDirection() const
which direction is this position from our parent node
Definition: PageStack.cc:106
IdSetPosition()=default
root node position
IdSet::size_type size_type
Definition: PageStack.cc:56
IdSet::size_type level
the number of levels above us (e.g., zero for the root node)
Definition: PageStack.cc:68
IdSet::size_type offset
the number of nodes (at our level) to the left of us
Definition: PageStack.cc:70
bool atRoot() const
whether we are at the top of the tree
Definition: PageStack.cc:62
a shareable set of positive uint32_t IDs with O(1) insertion/removal ops
Definition: PageStack.h:54
size_type leafPop(Position)
extracts and returns an ID from the leaf node at the given position
Definition: PageStack.cc:320
void leafTruncate(Position pos, size_type idsToKeep)
fill the leaf node at a given position with 0s, leaving only idsToKeep IDs
Definition: PageStack.cc:222
StoredNode & nodeAt(Position)
Definition: PageStack.cc:363
void truncateExtras()
effectively removes IDs that exceed the requested capacity after makeFull()
Definition: PageStack.cc:197
size_type innerTruncate(Position pos, NavigationDirection dir, size_type toSubtract)
Definition: PageStack.cc:235
void makeFullBeforeSharing()
Definition: PageStack.cc:163
void innerPush(Position, NavigationDirection)
accounts for an ID added to subtree in the given dir from the given position
Definition: PageStack.cc:258
uint64_t Node
either leaf or intermediate node
Definition: PageStack.h:79
static size_t MemorySize(size_type capacity)
memory size required to store a tree with the given capacity
Definition: PageStack.cc:419
Position ascend(Position)
Definition: PageStack.cc:336
void fillAllNodes()
Definition: PageStack.cc:176
Node * valueAddress(Position)
Definition: PageStack.cc:380
void push(size_type id)
makes id value available to future pop() callers
Definition: PageStack.cc:405
NavigationDirection innerPop(Position)
Definition: PageStack.cc:270
IdSet(size_type capacity)
Definition: PageStack.cc:152
std::atomic< Node > StoredNode
a Node stored in shared memory
Definition: PageStack.h:80
Position descend(Position, NavigationDirection)
Definition: PageStack.cc:347
void leafPush(Position, size_type id)
adds the given ID to the leaf node at the given position
Definition: PageStack.cc:296
IdSetMeasurements::size_type size_type
Definition: PageStack.h:56
bool pop(size_type &id)
Definition: PageStack.cc:387
Shared memory page identifier, address, or handler.
Definition: Page.h:24
PoolId pool
Definition: Page.h:39
uint32_t number
page number within the segment
Definition: Page.h:42
PageStack construction and SharedMemorySize calculation parameters.
Definition: PageStack.h:123
PageCount capacity
the maximum number of pages
Definition: PageStack.h:127
size_t pageSize
page size, used to calculate shared memory size
Definition: PageStack.h:126
bool createFull
whether a newly created PageStack should be prefilled with PageIds
Definition: PageStack.h:130
IdSet ids_
free pages (valid with positive capacity_)
Definition: PageStack.h:178
static size_t LevelsPaddingSize(const PageCount capacity)
Definition: PageStack.cc:519
static size_t SharedMemorySize(const Config &)
total shared memory size required to share
Definition: PageStack.cc:496
bool pageIdIsValid(const PageId &page) const
Definition: PageStack.cc:483
std::atomic< size_t > Levels_t
Definition: PageStack.h:111
std::atomic< PageCount > size_
a lower bound for the number of free pages (for debugging purposes)
Definition: PageStack.h:176
size_t stackSize() const
Definition: PageStack.cc:513
PageStack(const Config &)
Definition: PageStack.cc:430
unsigned int PageCount
the number of (free and/or used) pages in a stack
Definition: PageStack.h:117
const Config config_
Definition: PageStack.h:174
size_t sharedMemorySize() const
Definition: PageStack.cc:490
static size_t StackSize(const PageCount capacity)
Definition: PageStack.cc:504
bool pop(PageId &page)
sets value and returns true unless no free page numbers are found
Definition: PageStack.cc:442
void push(PageId &page)
makes value available as a free page number to future pop() callers
Definition: PageStack.cc:465
A const & max(A const &lhs, A const &rhs)
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:194
IdSetNavigationDirection
Definition: PageStack.h:27
@ dirLeft
Definition: PageStack.h:27
@ dirRight
Definition: PageStack.h:27
@ dirEnd
Definition: PageStack.h:27
@ dirNone
Definition: PageStack.h:27
static const IdSet::size_type BitsPerLeaf
the maximum number of pages that a leaf node can store
Definition: PageStack.cc:51
Definition: IpcIoFile.h:24
Memory Management.
Definition: Allocator.h:17
Definition: parse.c:104

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors