src/ipc/mem/PageStack.h

   1 /*
   2  * Copyright (C) 1996-2015 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 #ifndef SQUID_IPC_MEM_PAGE_STACK_H
  10 #define SQUID_IPC_MEM_PAGE_STACK_H
  11
  12 #include "ipc/mem/FlexibleArray.h"
  13
  14 #include <atomic>
  15
  16 namespace Ipc
  17 {
  18
  19 namespace Mem
  20 {
  21
  22 class PageId;
  23
  24 /// Atomic container of "free" page numbers inside a single SharedMemory space.
  25 /// Assumptions: all page numbers are unique, positive, have an known maximum,
  26 /// and can be temporary unavailable as long as they are never trully lost.
  27 class PageStack
  28 {
  29 public:
  30     typedef uint32_t Value; ///< stack item type (a free page number)
  31
  32     PageStack(const uint32_t aPoolId, const unsigned int aCapacity, const size_t aPageSize);
  33
  34     unsigned int capacity() const { return theCapacity; }
  35     size_t pageSize() const { return thePageSize; }
  36     /// lower bound for the number of free pages
  37     unsigned int size() const { return max(0, theSize.load()); }
  38
  39     /// sets value and returns true unless no free page numbers are found
  40     bool pop(PageId &page);
  41     /// makes value available as a free page number to future pop() callers
  42     void push(PageId &page);
  43
  44     bool pageIdIsValid(const PageId &page) const;
  45
  46     /// total shared memory size required to share
  47     static size_t SharedMemorySize(const uint32_t aPoolId, const unsigned int capacity, const size_t pageSize);
  48     size_t sharedMemorySize() const;
  49
  50     /// shared memory size required only by PageStack, excluding
  51     /// shared counters and page data
  52     static size_t StackSize(const unsigned int capacity);
  53     size_t stackSize() const;
  54
  55 private:
  56     /// stack index and size type (may temporary go negative)
  57     typedef int Offset;
  58
  59     // these help iterate the stack in search of a free spot or a page
  60     Offset next(const Offset idx) const { return (idx + 1) % theCapacity; }
  61     Offset prev(const Offset idx) const { return (theCapacity + idx - 1) % theCapacity; }
  62
  63     const uint32_t thePoolId; ///< pool ID
  64     const Offset theCapacity; ///< stack capacity, i.e. theItems size
  65     const size_t thePageSize; ///< page size, used to calculate shared memory size
  66     /// lower bound for the number of free pages (may get negative!)
  67     std::atomic<Offset> theSize;
  68
  69     /// last readable item index; just a hint, not a guarantee
  70     std::atomic<Offset> theLastReadable;
  71     /// first writable item index; just a hint, not a guarantee
  72     std::atomic<Offset> theFirstWritable;
  73
  74     typedef std::atomic<Value> Item;
  75     Ipc::Mem::FlexibleArray<Item> theItems; ///< page number storage
  76 };
  77
  78 } // namespace Mem
  79
  80 } // namespace Ipc
  81
  82 #endif // SQUID_IPC_MEM_PAGE_STACK_H
  83