src/ipc/mem/PageStack.cc

   1 /*
   2  * Copyright (C) 1996-2020 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 /* Ipc::Mem::PageStackStorageSlot */
  19
  20 static_assert(sizeof(Ipc::Mem::PageStackStorageSlot::Pointer) ==
  21               sizeof(decltype(Ipc::Mem::PageId::number)), "page indexing types are consistent");
  22
  23 void
  24 Ipc::Mem::PageStackStorageSlot::take()
  25 {
  26     const auto nxt = nextOrMarker.exchange(TakenPage);
  27     assert(nxt != TakenPage);
  28 }
  29
  30 void
  31 Ipc::Mem::PageStackStorageSlot::put(const PointerOrMarker expected, const Pointer nxt)
  32 {
  33     assert(nxt != TakenPage);
  34     const auto old = nextOrMarker.exchange(nxt);
  35     assert(old == expected);
  36 }
  37
  38 /* Ipc::Mem::PageStack */
  39
  40 Ipc::Mem::PageStack::PageStack(const PoolId aPoolId, const PageCount aCapacity, const size_t aPageSize):
  41     thePoolId(aPoolId), capacity_(aCapacity), thePageSize(aPageSize),
  42     size_(0),
  43     head_(Slot::NilPtr),
  44     slots_(aCapacity)
  45 {
  46     assert(thePoolId);
  47
  48     assert(capacity_ < Slot::TakenPage);
  49     assert(capacity_ < Slot::NilPtr);
  50
  51     // initially, all pages are free
  52     if (capacity_) {
  53         const auto lastIndex = capacity_-1;
  54         // FlexibleArray cannot construct its phantom elements so, technically,
  55         // all slots (except the very first one) are uninitialized until now.
  56         for (Slot::Pointer i = 0; i < lastIndex; ++i)
  57             (void)new(&slots_[i])Slot(i+1);
  58         (void)new(&slots_[lastIndex])Slot(Slot::NilPtr);
  59         size_ = capacity_;
  60         head_ = 0;
  61     }
  62 }
  63
  64 bool
  65 Ipc::Mem::PageStack::pop(PageId &page)
  66 {
  67     assert(!page);
  68
  69     Slot::Pointer current = head_.load();
  70
  71     auto nextFree = Slot::NilPtr;
  72     do {
  73         if (current == Slot::NilPtr)
  74             return false;
  75         nextFree = slots_[current].next();
  76     } while (!head_.compare_exchange_weak(current, nextFree));
  77
  78     // must decrement after removing the page to avoid underflow
  79     const auto newSize = --size_;
  80     assert(newSize < capacity_);
  81
  82     slots_[current].take();
  83     page.number = current + 1;
  84     page.pool = thePoolId;
  85     debugs(54, 8, page << " size: " << newSize);
  86     return true;
  87 }
  88
  89 void
  90 Ipc::Mem::PageStack::push(PageId &page)
  91 {
  92     debugs(54, 8, page);
  93     assert(page);
  94     assert(pageIdIsValid(page));
  95
  96     const auto pageIndex = page.number - 1;
  97     auto &slot = slots_[pageIndex];
  98
  99     // must increment before inserting the page to avoid underflow in pop()
 100     const auto newSize = ++size_;
 101     assert(newSize <= capacity_);
 102
 103     auto current = head_.load();
 104     auto expected = Slot::TakenPage;
 105     do {
 106         slot.put(expected, current);
 107         expected = current;
 108     } while (!head_.compare_exchange_weak(current, pageIndex));
 109
 110     debugs(54, 8, page << " size: " << newSize);
 111     page = PageId();
 112 }
 113
 114 bool
 115 Ipc::Mem::PageStack::pageIdIsValid(const PageId &page) const
 116 {
 117     return page.pool == thePoolId &&
 118            0 < page.number && page.number <= capacity();
 119 }
 120
 121 size_t
 122 Ipc::Mem::PageStack::sharedMemorySize() const
 123 {
 124     return SharedMemorySize(thePoolId, capacity_, thePageSize);
 125 }
 126
 127 size_t
 128 Ipc::Mem::PageStack::SharedMemorySize(const PoolId, const PageCount capacity, const size_t pageSize)
 129 {
 130     const auto levelsSize = PageId::maxPurpose * sizeof(Levels_t);
 131     const size_t pagesDataSize = capacity * pageSize;
 132     return StackSize(capacity) + LevelsPaddingSize(capacity) + levelsSize + pagesDataSize;
 133 }
 134
 135 size_t
 136 Ipc::Mem::PageStack::StackSize(const PageCount capacity)
 137 {
 138     return sizeof(PageStack) + capacity * sizeof(Slot);
 139 }
 140
 141 size_t
 142 Ipc::Mem::PageStack::stackSize() const
 143 {
 144     return StackSize(capacity_);
 145 }
 146
 147 size_t
 148 Ipc::Mem::PageStack::LevelsPaddingSize(const PageCount capacity)
 149 {
 150     const auto displacement = StackSize(capacity) % alignof(Levels_t);
 151     return displacement ? alignof(Levels_t) - displacement : 0;
 152 }
 153