]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/ipc/mem/PageStack.cc
2 * Copyright (C) 1996-2014 The Squid Software Foundation and contributors
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.
9 /* DEBUG: section 54 Interprocess Communication */
13 #include "base/TextException.h"
15 #include "ipc/mem/Page.h"
16 #include "ipc/mem/PageStack.h"
18 /// used to mark a stack slot available for storing free page offsets
19 const Ipc::Mem::PageStack::Value Writable
= 0;
21 Ipc::Mem::PageStack::PageStack(const uint32_t aPoolId
, const unsigned int aCapacity
, const size_t aPageSize
):
22 thePoolId(aPoolId
), theCapacity(aCapacity
), thePageSize(aPageSize
),
24 theLastReadable(prev(theSize
)), theFirstWritable(next(theLastReadable
)),
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
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().
40 Ipc::Mem::PageStack::pop(PageId
&page
)
44 // we may fail to dequeue, but be conservative to prevent long searches
47 // find a Readable slot, starting with theLastReadable and going left
48 while (theSize
>= 0) {
49 const Offset idx
= theLastReadable
;
50 // mark the slot at ids Writable while extracting its current value
51 const Value value
= theItems
[idx
].fetchAndAnd(0); // works if Writable is 0
52 const bool popped
= value
!= Writable
;
53 // theItems[idx] is probably not Readable [any more]
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
.swap_if(idx
, prev(idx
)); // may fail or lie
61 // the slot we emptied may already be filled, but that is OK
62 theFirstWritable
= idx
; // may lie
63 page
.pool
= thePoolId
;
65 debugs(54, 9, page
<< " at " << idx
<< " size: " << theSize
);
68 // TODO: report suspiciously long loops
76 Ipc::Mem::PageStack::push(PageId
&page
)
83 Must(pageIdIsValid(page
));
84 // find a Writable slot, starting with theFirstWritable and going right
85 while (theSize
< theCapacity
) {
86 const Offset idx
= theFirstWritable
;
87 const bool pushed
= theItems
[idx
].swap_if(Writable
, page
.number
);
88 // theItems[idx] is probably not Writable [any more];
90 // Whether we pushed the page number or not, we should try going right
91 // to maintain the index (and make progress).
92 // We may fail if others already updated the index, but that is OK.
93 theFirstWritable
.swap_if(idx
, next(idx
)); // may fail or lie
96 // the enqueued value may already by gone, but that is OK
97 theLastReadable
= idx
; // may lie
99 debugs(54, 9, page
<< " at " << idx
<< " size: " << theSize
);
103 // TODO: report suspiciously long loops
105 Must(false); // the number of pages cannot exceed theCapacity
109 Ipc::Mem::PageStack::pageIdIsValid(const PageId
&page
) const
111 return page
.pool
== thePoolId
&& page
.number
!= Writable
&&
112 page
.number
<= capacity();
116 Ipc::Mem::PageStack::sharedMemorySize() const
118 return SharedMemorySize(thePoolId
, theCapacity
, thePageSize
);
122 Ipc::Mem::PageStack::SharedMemorySize(const uint32_t, const unsigned int capacity
, const size_t pageSize
)
124 const size_t levelsSize
= PageId::maxPurpose
* sizeof(Atomic::Word
);
125 const size_t pagesDataSize
= capacity
* pageSize
;
126 return StackSize(capacity
) + pagesDataSize
+ levelsSize
;
130 Ipc::Mem::PageStack::StackSize(const unsigned int capacity
)
132 return sizeof(PageStack
) + capacity
* sizeof(Item
);
136 Ipc::Mem::PageStack::stackSize() const
138 return StackSize(theCapacity
);