PageStack.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 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 
23 Ipc::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 
31 where
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 
39 The 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 
44 namespace Ipc
45 {
46 
47 namespace Mem
48 {
49 
51 static const IdSet::size_type BitsPerLeaf = 64;
52 
54 {
55 public:
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 {
76 public:
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 
162 void
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 
175 void
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 
196 void
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 
221 void
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 
257 void
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 
295 void
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.
307 static inline
308 int 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 
386 bool
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 
404 void
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 
418 size_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 
441 bool
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 
464 void
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 
482 bool
484 {
485  return page.pool == config_.poolId &&
486  0 < page.number && page.number <= capacity();
487 }
488 
489 size_t
491 {
492  return SharedMemorySize(config_);
493 }
494 
495 size_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 
503 size_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 
512 size_t
514 {
515  return StackSize(config_.capacity);
516 }
517 
518 size_t
520 {
521  const auto displacement = StackSize(capacity) % alignof(Levels_t);
522  return displacement ? alignof(Levels_t) - displacement : 0;
523 }
524 
PageStack(const Config &)
Definition: PageStack.cc:430
bool pageIdIsValid(const PageId &page) const
Definition: PageStack.cc:483
Definition: parse.c:104
void leafPush(Position, size_type id)
adds the given ID to the leaf node at the given position
Definition: PageStack.cc:296
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
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
size_type nodeCount() const
the total number of nodes at all levels
Definition: PageStack.h:49
IdSetMeasurements::size_type size_type
Definition: PageStack.h:56
static const IdSet::size_type BitsPerLeaf
the maximum number of pages that a leaf node can store
Definition: PageStack.cc:51
IdSetNavigationDirection ascendDirection() const
which direction is this position from our parent node
Definition: PageStack.cc:106
StoredNode & nodeAt(Position)
Definition: PageStack.cc:363
void innerPush(Position, NavigationDirection)
accounts for an ID added to subtree in the given dir from the given position
Definition: PageStack.cc:258
a shareable set of positive uint32_t IDs with O(1) insertion/removal ops
Definition: PageStack.h:54
PoolId pool
Definition: Page.h:39
Shared memory page identifier, address, or handler.
Definition: Page.h:24
Position ascend(Position)
Definition: PageStack.cc:336
IdSetNavigationDirection
Definition: PageStack.h:27
unsigned int PageCount
the number of (free and/or used) pages in a stack
Definition: PageStack.h:117
basic IdSet storage parameters, extracted here to keep them constant
Definition: PageStack.h:31
IdSet::size_type size_type
Definition: PageStack.cc:56
size_type right
the number of available IDs in the right subtree
Definition: PageStack.cc:90
std::atomic< size_t > Levels_t
Definition: PageStack.h:111
@ dirRight
Definition: PageStack.h:27
IdSet::size_type size_type
Definition: PageStack.cc:77
@ dirEnd
Definition: PageStack.h:27
std::atomic< PageCount > size_
a lower bound for the number of free pages (for debugging purposes)
Definition: PageStack.h:176
IdSet::size_type offset
the number of nodes (at our level) to the left of us
Definition: PageStack.cc:70
void push(PageId &page)
makes value available as a free page number to future pop() callers
Definition: PageStack.cc:465
std::atomic< Node > StoredNode
a Node stored in shared memory
Definition: PageStack.h:80
Node * valueAddress(Position)
Definition: PageStack.cc:380
void push(size_type id)
makes id value available to future pop() callers
Definition: PageStack.cc:405
A const & max(A const &lhs, A const &rhs)
Memory Management.
IdSet::size_type level
the number of levels above us (e.g., zero for the root node)
Definition: PageStack.cc:68
static size_t StackSize(const PageCount capacity)
Definition: PageStack.cc:504
static size_t LevelsPaddingSize(const PageCount capacity)
Definition: PageStack.cc:519
const Config config_
Definition: PageStack.h:174
size_t sharedMemorySize() const
Definition: PageStack.cc:490
size_type leafPop(Position)
extracts and returns an ID from the leaf node at the given position
Definition: PageStack.cc:320
NavigationDirection innerPop(Position)
Definition: PageStack.cc:270
bool pop(size_type &id)
Definition: PageStack.cc:387
#define assert(EX)
Definition: assert.h:19
size_type innerTruncate(Position pos, NavigationDirection dir, size_type toSubtract)
Definition: PageStack.cc:235
Packed pack() const
returns a serializes value suitable for shared memory storage
Definition: PageStack.cc:87
static int trailingZeros(uint64_t x)
a temporary C++20 countr_zero() replacement
Definition: PageStack.cc:308
bool atRoot() const
whether we are at the top of the tree
Definition: PageStack.cc:62
size_type left
the number of available IDs in the left subtree
Definition: PageStack.cc:89
size_t pageSize
page size, used to calculate shared memory size
Definition: PageStack.h:126
bool pop(PageId &page)
sets value and returns true unless no free page numbers are found
Definition: PageStack.cc:442
IdSetMeasurements(size_type capacity)
Definition: PageStack.cc:113
uint32_t number
page number within the segment
Definition: Page.h:42
IdSetPosition()=default
root node position
PageStack construction and SharedMemorySize calculation parameters.
Definition: PageStack.h:123
void fillAllNodes()
Definition: PageStack.cc:176
IdSet(size_type capacity)
Definition: PageStack.cc:152
uint32_t size_type
we need to fit two size_type counters into one 64-bit lockless atomic
Definition: PageStack.h:34
bool createFull
whether a newly created PageStack should be prefilled with PageIds
Definition: PageStack.h:130
static size_t MemorySize(size_type capacity)
memory size required to store a tree with the given capacity
Definition: PageStack.cc:419
uint64_t Node
either leaf or intermediate node
Definition: PageStack.h:79
@ dirLeft
Definition: PageStack.h:27
PageCount capacity
the maximum number of pages
Definition: PageStack.h:127
void makeFullBeforeSharing()
Definition: PageStack.cc:163
void truncateExtras()
effectively removes IDs that exceed the requested capacity after makeFull()
Definition: PageStack.cc:197
Position descend(Position, NavigationDirection)
Definition: PageStack.cc:347
IdSet ids_
free pages (valid with positive capacity_)
Definition: PageStack.h:178
a helper class to perform inner node manipulation for IdSet
Definition: PageStack.cc:75
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
size_t stackSize() const
Definition: PageStack.cc:513
static size_t SharedMemorySize(const Config &)
total shared memory size required to share
Definition: PageStack.cc:496
@ dirNone
Definition: PageStack.h:27
Definition: IpcIoFile.h:24

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors