PageStack.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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 "base/TextException.h"
14 #include "Debug.h"
15 #include "ipc/mem/Page.h"
16 #include "ipc/mem/PageStack.h"
17 
20 
21 Ipc::Mem::PageStack::PageStack(const uint32_t aPoolId, const unsigned int aCapacity, const size_t aPageSize):
22  thePoolId(aPoolId), theCapacity(aCapacity), thePageSize(aPageSize),
23  theSize(theCapacity),
24  theLastReadable(prev(theSize)), theFirstWritable(next(theLastReadable)),
25  theItems(aCapacity)
26 {
27  // initially, all pages are free
28  for (Offset i = 0; i < theSize; ++i)
29  theItems[i] = i + 1; // skip page number zero to keep numbers positive
30 }
31 
32 /*
33  * TODO: We currently rely on the theLastReadable hint during each
34  * loop iteration. We could also use hint just for the start position:
35  * (const Offset start = theLastReadable) and then scan the stack
36  * sequentially regardless of theLastReadable changes by others. Which
37  * approach is better? Same for push().
38  */
39 bool
41 {
42  Must(!page);
43 
44  // we may fail to dequeue, but be conservative to prevent long searches
45  --theSize;
46 
47  // find a Readable slot, starting with theLastReadable and going left
48  while (theSize >= 0) {
49  Offset idx = theLastReadable;
50  // mark the slot at ids Writable while extracting its current value
51  const Value value = theItems[idx].fetch_and(0); // works if Writable is 0
52  const bool popped = value != Writable;
53  // theItems[idx] is probably not Readable [any more]
54 
55  // Whether we popped a Readable value or not, we should try going left
56  // to maintain the index (and make progress).
57  // We may fail if others already updated the index, but that is OK.
58  theLastReadable.compare_exchange_weak(idx, prev(idx)); // may fail or lie
59 
60  if (popped) {
61  // the slot we emptied may already be filled, but that is OK
62  theFirstWritable = idx; // may lie
63  page.pool = thePoolId;
64  page.number = value;
65  debugs(54, 9, page << " at " << idx << " size: " << theSize);
66  return true;
67  }
68  // TODO: report suspiciously long loops
69  }
70 
71  ++theSize;
72  return false;
73 }
74 
75 void
77 {
78  debugs(54, 9, page);
79 
80  if (!page)
81  return;
82 
83  Must(pageIdIsValid(page));
84  // find a Writable slot, starting with theFirstWritable and going right
85  while (theSize < theCapacity) {
86  Offset idx = theFirstWritable;
87  auto isWritable = Writable;
88  const bool pushed = theItems[idx].compare_exchange_strong(isWritable, page.number);
89  // theItems[idx] is probably not Writable [any more];
90 
91  // Whether we pushed the page number or not, we should try going right
92  // to maintain the index (and make progress).
93  // We may fail if others already updated the index, but that is OK.
94  theFirstWritable.compare_exchange_weak(idx, next(idx)); // may fail or lie
95 
96  if (pushed) {
97  // the enqueued value may already by gone, but that is OK
98  theLastReadable = idx; // may lie
99  ++theSize;
100  debugs(54, 9, page << " at " << idx << " size: " << theSize);
101  page = PageId();
102  return;
103  }
104  // TODO: report suspiciously long loops
105  }
106  Must(false); // the number of pages cannot exceed theCapacity
107 }
108 
109 bool
111 {
112  return page.pool == thePoolId && page.number != Writable &&
113  page.number <= capacity();
114 }
115 
116 size_t
118 {
119  return SharedMemorySize(thePoolId, theCapacity, thePageSize);
120 }
121 
122 size_t
123 Ipc::Mem::PageStack::SharedMemorySize(const uint32_t, const unsigned int capacity, const size_t pageSize)
124 {
125  const size_t levelsSize = PageId::maxPurpose * sizeof(std::atomic<Ipc::Mem::PageStack::Value>);
126  const size_t pagesDataSize = capacity * pageSize;
127  return StackSize(capacity) + pagesDataSize + levelsSize;
128 }
129 
130 size_t
131 Ipc::Mem::PageStack::StackSize(const unsigned int capacity)
132 {
133  return sizeof(PageStack) + capacity * sizeof(Item);
134 }
135 
136 size_t
138 {
139  return StackSize(theCapacity);
140 }
141 
void push(PageId &page)
makes value available as a free page number to future pop() callers
Definition: PageStack.cc:76
int i
Definition: membanger.c:49
static size_t StackSize(const unsigned int capacity)
Definition: PageStack.cc:131
std::atomic< Value > Item
Definition: PageStack.h:74
uint32_t pool
page pool ID within Squid
Definition: Page.h:33
size_t sharedMemorySize() const
Definition: PageStack.cc:117
uint32_t number
page number within the segment
Definition: Page.h:35
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
bool pop(PageId &page)
sets value and returns true unless no free page numbers are found
Definition: PageStack.cc:40
Ipc::Mem::FlexibleArray< Item > theItems
page number storage
Definition: PageStack.h:75
int Offset
stack index and size type (may temporary go negative)
Definition: PageStack.h:57
static size_t SharedMemorySize(const uint32_t aPoolId, const unsigned int capacity, const size_t pageSize)
total shared memory size required to share
Definition: PageStack.cc:123
PageStack(const uint32_t aPoolId, const unsigned int aCapacity, const size_t aPageSize)
Definition: PageStack.cc:21
#define Must(cond)
Definition: TextException.h:89
const Ipc::Mem::PageStack::Value Writable
used to mark a stack slot available for storing free page offsets
Definition: PageStack.cc:19
size_t stackSize() const
Definition: PageStack.cc:137
std::atomic< Offset > theSize
lower bound for the number of free pages (may get negative!)
Definition: PageStack.h:67
Shared memory page identifier, address, or handler.
Definition: Page.h:21
bool pageIdIsValid(const PageId &page) const
Definition: PageStack.cc:110
uint32_t Value
stack item type (a free page number)
Definition: PageStack.h:30

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors