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