src/ipc/mem/PageStack.cc

   1 /*
   2  * Copyright (C) 1996-2016 The Squid Software Foundation and contributors
   3  *
   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.
   7  */
   8
   9 /* DEBUG: section 54    Interprocess Communication */
  10
  11 #include "squid.h"
  12
  13 #include "base/TextException.h"
  14 #include "Debug.h"
  15 #include "ipc/mem/Page.h"
  16 #include "ipc/mem/PageStack.h"
  17
  18 /// used to mark a stack slot available for storing free page offsets
  19 const Ipc::Mem::PageStack::Value Writable = 0;
  20
  21 Ipc::Mem::PageStack::PageStack(const uint32_t aPoolId, const unsigned int aCapacity, const size_t aPageSize):
  22     thePoolId(aPoolId), theCapacity(aCapacity), thePageSize(aPageSize),
  23     theSize(theCapacity),
  24     theLastReadable(prev(theSize)), theFirstWritable(next(theLastReadable)),
  25     theItems(aCapacity)
  26 {
  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
  30 }
  31
  32 /*
  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().
  38  */
  39 bool
  40 Ipc::Mem::PageStack::pop(PageId &page)
  41 {
  42     Must(!page);
  43
  44     // we may fail to dequeue, but be conservative to prevent long searches
  45     --theSize;
  46
  47     // find a Readable slot, starting with theLastReadable and going left
  48     while (theSize >= 0) {
  49         Offset idx = theLastReadable;
  50         // mark the slot at ids Writable while extracting its current value
  51         const Value value = theItems[idx].fetch_and(0); // works if Writable is 0
  52         const bool popped = value != Writable;
  53         // theItems[idx] is probably not Readable [any more]
  54
  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.compare_exchange_weak(idx, prev(idx)); // may fail or lie
  59
  60         if (popped) {
  61             // the slot we emptied may already be filled, but that is OK
  62             theFirstWritable = idx; // may lie
  63             page.pool = thePoolId;
  64             page.number = value;
  65             debugs(54, 9, page << " at " << idx << " size: " << theSize);
  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     debugs(54, 9, page);
  79
  80     if (!page)
  81         return;
  82
  83     Must(pageIdIsValid(page));
  84     // find a Writable slot, starting with theFirstWritable and going right
  85     while (theSize < theCapacity) {
  86         Offset idx = theFirstWritable;
  87         auto isWritable = Writable;
  88         const bool pushed = theItems[idx].compare_exchange_strong(isWritable, page.number);
  89         // theItems[idx] is probably not Writable [any more];
  90
  91         // Whether we pushed the page number or not, we should try going right
  92         // to maintain the index (and make progress).
  93         // We may fail if others already updated the index, but that is OK.
  94         theFirstWritable.compare_exchange_weak(idx, next(idx)); // may fail or lie
  95
  96         if (pushed) {
  97             // the enqueued value may already by gone, but that is OK
  98             theLastReadable = idx; // may lie
  99             ++theSize;
 100             debugs(54, 9, page << " at " << idx << " size: " << theSize);
 101             page = PageId();
 102             return;
 103         }
 104         // TODO: report suspiciously long loops
 105     }
 106     Must(false); // the number of pages cannot exceed theCapacity
 107 }
 108
 109 bool
 110 Ipc::Mem::PageStack::pageIdIsValid(const PageId &page) const
 111 {
 112     return page.pool == thePoolId && page.number != Writable &&
 113            page.number <= capacity();
 114 }
 115
 116 size_t
 117 Ipc::Mem::PageStack::sharedMemorySize() const
 118 {
 119     return SharedMemorySize(thePoolId, theCapacity, thePageSize);
 120 }
 121
 122 size_t
 123 Ipc::Mem::PageStack::SharedMemorySize(const uint32_t, const unsigned int capacity, const size_t pageSize)
 124 {
 125     const size_t levelsSize = PageId::maxPurpose * sizeof(std::atomic<Ipc::Mem::PageStack::Value>);
 126     const size_t pagesDataSize = capacity * pageSize;
 127     return StackSize(capacity) + pagesDataSize + levelsSize;
 128 }
 129
 130 size_t
 131 Ipc::Mem::PageStack::StackSize(const unsigned int capacity)
 132 {
 133     return sizeof(PageStack) + capacity * sizeof(Item);
 134 }
 135
 136 size_t
 137 Ipc::Mem::PageStack::stackSize() const
 138 {
 139     return StackSize(theCapacity);
 140 }
 141