]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | * $Id$ | |
3 | * | |
4 | * DEBUG: section 54 Interprocess Communication | |
5 | * | |
6 | */ | |
7 | ||
8 | #include "squid.h" | |
9 | ||
10 | #include "base/TextException.h" | |
11 | #include "ipc/mem/Page.h" | |
12 | #include "ipc/mem/PageStack.h" | |
13 | ||
14 | /// used to mark a stack slot available for storing free page offsets | |
15 | const Ipc::Mem::PageStack::Value Writable = 0; | |
16 | ||
17 | Ipc::Mem::PageStack::PageStack(const uint32_t aPoolId, const unsigned int aCapacity, const size_t aPageSize): | |
18 | thePoolId(aPoolId), theCapacity(aCapacity), thePageSize(aPageSize), | |
19 | theSize(theCapacity), | |
20 | theLastReadable(prev(theSize)), theFirstWritable(next(theLastReadable)) | |
21 | { | |
22 | // initially, all pages are free | |
23 | for (Offset i = 0; i < theSize; ++i) | |
24 | theItems[i] = i + 1; // skip page number zero to keep numbers positive | |
25 | theItems=new Item[theSize]; | |
26 | } | |
27 | ||
28 | Ipc::Mem::PageStack::~PageStack() | |
29 | { | |
30 | delete[] theItems; | |
31 | } | |
32 | ||
33 | /* | |
34 | * TODO: We currently rely on the theLastReadable hint during each | |
35 | * loop iteration. We could also use hint just for the start position: | |
36 | * (const Offset start = theLastReadable) and then scan the stack | |
37 | * sequentially regardless of theLastReadable changes by others. Which | |
38 | * approach is better? Same for push(). | |
39 | */ | |
40 | bool | |
41 | Ipc::Mem::PageStack::pop(PageId &page) | |
42 | { | |
43 | Must(!page); | |
44 | ||
45 | // we may fail to dequeue, but be conservative to prevent long searches | |
46 | --theSize; | |
47 | ||
48 | // find a Readable slot, starting with theLastReadable and going left | |
49 | while (theSize >= 0) { | |
50 | const Offset idx = theLastReadable; | |
51 | // mark the slot at ids Writable while extracting its current value | |
52 | const Value value = theItems[idx].fetchAndAnd(0); // works if Writable is 0 | |
53 | const bool popped = value != Writable; | |
54 | // theItems[idx] is probably not Readable [any more] | |
55 | ||
56 | // Whether we popped a Readable value or not, we should try going left | |
57 | // to maintain the index (and make progress). | |
58 | // We may fail if others already updated the index, but that is OK. | |
59 | theLastReadable.swap_if(idx, prev(idx)); // may fail or lie | |
60 | ||
61 | if (popped) { | |
62 | // the slot we emptied may already be filled, but that is OK | |
63 | theFirstWritable = idx; // may lie | |
64 | page.pool = thePoolId; | |
65 | page.number = value; | |
66 | return true; | |
67 | } | |
68 | // TODO: report suspiciously long loops | |
69 | } | |
70 | ||
71 | ++theSize; | |
72 | return false; | |
73 | } | |
74 | ||
75 | void | |
76 | Ipc::Mem::PageStack::push(PageId &page) | |
77 | { | |
78 | if (!page) | |
79 | return; | |
80 | ||
81 | Must(pageIdIsValid(page)); | |
82 | // find a Writable slot, starting with theFirstWritable and going right | |
83 | while (theSize < theCapacity) { | |
84 | const Offset idx = theFirstWritable; | |
85 | const bool pushed = theItems[idx].swap_if(Writable, page.number); | |
86 | // theItems[idx] is probably not Writable [any more]; | |
87 | ||
88 | // Whether we pushed the page number or not, we should try going right | |
89 | // to maintain the index (and make progress). | |
90 | // We may fail if others already updated the index, but that is OK. | |
91 | theFirstWritable.swap_if(idx, next(idx)); // may fail or lie | |
92 | ||
93 | if (pushed) { | |
94 | // the enqueued value may already by gone, but that is OK | |
95 | theLastReadable = idx; // may lie | |
96 | ++theSize; | |
97 | page = PageId(); | |
98 | return; | |
99 | } | |
100 | // TODO: report suspiciously long loops | |
101 | } | |
102 | Must(false); // the number of pages cannot exceed theCapacity | |
103 | } | |
104 | ||
105 | bool | |
106 | Ipc::Mem::PageStack::pageIdIsValid(const PageId &page) const | |
107 | { | |
108 | return page.pool == thePoolId && page.number != Writable && | |
109 | page.number <= capacity(); | |
110 | } | |
111 | ||
112 | size_t | |
113 | Ipc::Mem::PageStack::sharedMemorySize() const | |
114 | { | |
115 | return SharedMemorySize(thePoolId, theCapacity, thePageSize); | |
116 | } | |
117 | ||
118 | size_t | |
119 | Ipc::Mem::PageStack::SharedMemorySize(const uint32_t, const unsigned int capacity, const size_t pageSize) | |
120 | { | |
121 | const size_t levelsSize = PageId::maxPurpose * sizeof(Atomic::Word); | |
122 | const size_t pagesDataSize = capacity * pageSize; | |
123 | return StackSize(capacity) + pagesDataSize + levelsSize; | |
124 | } | |
125 | ||
126 | size_t | |
127 | Ipc::Mem::PageStack::StackSize(const unsigned int capacity) | |
128 | { | |
129 | return sizeof(PageStack) + capacity * sizeof(Item); | |
130 | } | |
131 | ||
132 | size_t | |
133 | Ipc::Mem::PageStack::stackSize() const | |
134 | { | |
135 | return StackSize(theCapacity); | |
136 | } |