PageStack.h
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 #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;
28 
31 {
32 public:
34  typedef uint32_t size_type;
35 
37 
40 
43 
47 
49  size_type nodeCount() const { return leafNodeCount ? leafNodeCount*2 -1 : 0; }
50 };
51 
53 class IdSet
54 {
55 public:
59 
61  static size_t MemorySize(size_type capacity);
62 
63  explicit IdSet(size_type capacity);
64 
67  void makeFullBeforeSharing();
68 
71  bool pop(size_type &id);
72 
74  void push(size_type id);
75 
77 
78 private:
79  typedef uint64_t Node;
80  typedef std::atomic<Node> StoredNode;
81 
82  /* optimization: these initialization methods bypass atomic protections */
83  void fillAllNodes();
84  void truncateExtras();
87  void leafTruncate(Position pos, size_type idsToKeep);
88 
91 
92  void leafPush(Position, size_type id);
94 
97 
99 
102  // No more data members should follow! See FlexibleArray<> for details.
103 };
104 
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.
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.
123  class Config {
124  public:
125  uint32_t poolId = 0;
126  size_t pageSize = 0;
128 
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; }
138  PageCount size() const { return size_.load(); }
139 
141  bool pop(PageId &page);
143  void push(PageId &page);
144 
145  bool pageIdIsValid(const PageId &page) const;
146 
148  static size_t SharedMemorySize(const Config &);
149  size_t sharedMemorySize() const;
150 
153  static size_t StackSize(const PageCount capacity);
154  size_t stackSize() const;
155 
157  static size_t LevelsPaddingSize(const PageCount capacity);
159 
166  static PoolId IdForMemStoreSpace() { return 10; }
169  static PoolId IdForMultipurposePool() { return 200; } // segments could use 2xx
171  static PoolId IdForSwapDirSpace(const int dirIdx) { return 900 + dirIdx + 1; }
172 
173 private:
176  std::atomic<PageCount> size_;
177 
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 
PageStack(const Config &)
Definition: PageStack.cc:430
bool pageIdIsValid(const PageId &page) const
Definition: PageStack.cc:483
size_type leafNodeCount
the number of nodes at the leaf level
Definition: PageStack.h:45
void leafPush(Position, size_type id)
adds the given ID to the leaf node at the given position
Definition: PageStack.cc:296
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
uint32_t poolId
pool ID
Definition: PageStack.h:125
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
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
size_type treeHeight
total number of levels, including the leaf level
Definition: PageStack.h:44
a shareable set of positive uint32_t IDs with O(1) insertion/removal ops
Definition: PageStack.h:54
size_t pageSize() const
Definition: PageStack.h:136
Shared memory page identifier, address, or handler.
Definition: Page.h:24
static PoolId IdForMemStoreSpace()
stack of free cache_mem slot positions
Definition: PageStack.h:167
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
std::atomic< size_t > Levels_t
Definition: PageStack.h:111
@ dirRight
Definition: PageStack.h:27
@ dirEnd
Definition: PageStack.h:27
size_t levelsPaddingSize() const
Definition: PageStack.h:158
std::atomic< PageCount > size_
a lower bound for the number of free pages (for debugging purposes)
Definition: PageStack.h:176
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
uint32_t PoolId
Definition: forward.h:17
PageCount capacity() const
Definition: PageStack.h:135
size_type capacity
the maximum number of pages our tree is allowed to store
Definition: PageStack.h:39
Memory Management.
static PoolId IdForMultipurposePool()
multipurpose PagePool of shared memory pages
Definition: PageStack.h:169
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
size_type requestedLeafNodeCount
the number of leaf nodes that satisfy capacity requirements
Definition: PageStack.h:42
size_type innerLevelCount
all levels except the leaf level
Definition: PageStack.h:46
size_type innerTruncate(Position pos, NavigationDirection dir, size_type toSubtract)
Definition: PageStack.cc:235
FlexibleArray< StoredNode > nodes_
the entire binary tree flattened into an array
Definition: PageStack.h:101
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
PageCount size() const
an approximate number of free pages
Definition: PageStack.h:138
IdSetMeasurements(size_type capacity)
Definition: PageStack.cc:113
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
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
static PoolId IdForSwapDirSpace(const int dirIdx)
stack of free rock cache_dir slot numbers
Definition: PageStack.h:171
@ dirNone
Definition: PageStack.h:27
class SquidConfig Config
Definition: SquidConfig.cc:12
Definition: IpcIoFile.h:24
const IdSetMeasurements measurements
Definition: PageStack.h:76

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors