src/ipc/mem/PageStack.cc

   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 }