]>
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 | ||
68353d5a | 17 | Ipc::Mem::PageStack::PageStack(const uint32_t aPoolId, const unsigned int aCapacity, const size_t aPageSize): |
9199139f AR |
18 | thePoolId(aPoolId), theCapacity(aCapacity), thePageSize(aPageSize), |
19 | theSize(theCapacity), | |
20 | theLastReadable(prev(theSize)), theFirstWritable(next(theLastReadable)) | |
c011f9bc | 21 | { |
68353d5a DK |
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 | |
2cde0303 FC |
25 | theItems=new Item[theSize]; |
26 | } | |
27 | ||
28 | Ipc::Mem::PageStack::~PageStack() | |
29 | { | |
30 | delete[] theItems; | |
c011f9bc DK |
31 | } |
32 | ||
be17aa82 AR |
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 | |
68353d5a | 41 | Ipc::Mem::PageStack::pop(PageId &page) |
be17aa82 | 42 | { |
8ed94021 DK |
43 | Must(!page); |
44 | ||
be17aa82 | 45 | // we may fail to dequeue, but be conservative to prevent long searches |
68353d5a | 46 | --theSize; |
be17aa82 AR |
47 | |
48 | // find a Readable slot, starting with theLastReadable and going left | |
68353d5a DK |
49 | while (theSize >= 0) { |
50 | const Offset idx = theLastReadable; | |
be17aa82 | 51 | // mark the slot at ids Writable while extracting its current value |
68353d5a | 52 | const Value value = theItems[idx].fetchAndAnd(0); // works if Writable is 0 |
be17aa82 AR |
53 | const bool popped = value != Writable; |
54 | // theItems[idx] is probably not Readable [any more] | |
03055efe AR |
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. | |
68353d5a | 59 | theLastReadable.swap_if(idx, prev(idx)); // may fail or lie |
03055efe | 60 | |
be17aa82 AR |
61 | if (popped) { |
62 | // the slot we emptied may already be filled, but that is OK | |
68353d5a DK |
63 | theFirstWritable = idx; // may lie |
64 | page.pool = thePoolId; | |
65 | page.number = value; | |
be17aa82 AR |
66 | return true; |
67 | } | |
68 | // TODO: report suspiciously long loops | |
69 | } | |
70 | ||
68353d5a | 71 | ++theSize; |
be17aa82 AR |
72 | return false; |
73 | } | |
74 | ||
75 | void | |
68353d5a | 76 | Ipc::Mem::PageStack::push(PageId &page) |
be17aa82 | 77 | { |
8ed94021 DK |
78 | if (!page) |
79 | return; | |
80 | ||
68353d5a | 81 | Must(pageIdIsValid(page)); |
be17aa82 | 82 | // find a Writable slot, starting with theFirstWritable and going right |
68353d5a DK |
83 | while (theSize < theCapacity) { |
84 | const Offset idx = theFirstWritable; | |
85 | const bool pushed = theItems[idx].swap_if(Writable, page.number); | |
be17aa82 | 86 | // theItems[idx] is probably not Writable [any more]; |
03055efe | 87 | |
68353d5a | 88 | // Whether we pushed the page number or not, we should try going right |
03055efe AR |
89 | // to maintain the index (and make progress). |
90 | // We may fail if others already updated the index, but that is OK. | |
68353d5a | 91 | theFirstWritable.swap_if(idx, next(idx)); // may fail or lie |
03055efe | 92 | |
be17aa82 AR |
93 | if (pushed) { |
94 | // the enqueued value may already by gone, but that is OK | |
68353d5a DK |
95 | theLastReadable = idx; // may lie |
96 | ++theSize; | |
97 | page = PageId(); | |
be17aa82 AR |
98 | return; |
99 | } | |
100 | // TODO: report suspiciously long loops | |
101 | } | |
102 | Must(false); // the number of pages cannot exceed theCapacity | |
103 | } | |
104 | ||
68353d5a DK |
105 | bool |
106 | Ipc::Mem::PageStack::pageIdIsValid(const PageId &page) const | |
be17aa82 | 107 | { |
68353d5a | 108 | return page.pool == thePoolId && page.number != Writable && |
9199139f | 109 | page.number <= capacity(); |
68353d5a DK |
110 | } |
111 | ||
112 | size_t | |
113 | Ipc::Mem::PageStack::sharedMemorySize() const | |
114 | { | |
115 | return SharedMemorySize(thePoolId, theCapacity, thePageSize); | |
be17aa82 | 116 | } |
2d0647fb DK |
117 | |
118 | size_t | |
68353d5a | 119 | Ipc::Mem::PageStack::SharedMemorySize(const uint32_t, const unsigned int capacity, const size_t pageSize) |
2d0647fb | 120 | { |
794d4c0c | 121 | const size_t levelsSize = PageId::maxPurpose * sizeof(Atomic::Word); |
551f8a18 DK |
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); | |
2d0647fb | 136 | } |