PageStack.h

Go to the documentation of this file.

/*
 * Copyright (C) 1996-2025 The Squid Software Foundation and contributors
 *
 * Squid software is distributed under GPLv2+ license and includes
 * contributions from numerous individuals and organizations.
 * Please see the COPYING and CONTRIBUTORS files for details.
 */
 
#ifndef SQUID_SRC_IPC_MEM_PAGESTACK_H
#define SQUID_SRC_IPC_MEM_PAGESTACK_H
 
#include "ipc/mem/FlexibleArray.h"
#include "ipc/mem/forward.h"
 
#include <atomic>
#include <limits>
 
namespace Ipc
{
 
namespace Mem
{
 
class PageId;
 
class IdSetPosition;
typedef enum { dirNone, dirLeft, dirRight, dirEnd } IdSetNavigationDirection;
 
class IdSetMeasurements
{
public:
    typedef uint32_t size_type;
 
    explicit IdSetMeasurements(size_type capacity);
 
    size_type capacity = 0;
 
    size_type requestedLeafNodeCount = 0;
 
    size_type treeHeight = 0; 
    size_type leafNodeCount = 0; 
    size_type innerLevelCount = 0; 
 
    size_type nodeCount() const { return leafNodeCount ? leafNodeCount*2 -1 : 0; }
};
 
class IdSet
{
public:
    using size_type = IdSetMeasurements::size_type;
    using Position = IdSetPosition;
    using NavigationDirection = IdSetNavigationDirection;
 
    static size_t MemorySize(size_type capacity);
 
    explicit IdSet(size_type capacity);
 
    void makeFullBeforeSharing();
 
    bool pop(size_type &id);
 
    void push(size_type id);
 
    const IdSetMeasurements measurements;
 
private:
    typedef uint64_t Node; 
    typedef std::atomic<Node> StoredNode; 
 
    /* optimization: these initialization methods bypass atomic protections */
    void fillAllNodes();
    void truncateExtras();
    Node *valueAddress(Position);
    size_type innerTruncate(Position pos, NavigationDirection dir, size_type toSubtract);
    void leafTruncate(Position pos, size_type idsToKeep);
 
    void innerPush(Position, NavigationDirection);
    NavigationDirection innerPop(Position);
 
    void leafPush(Position, size_type id);
    size_type leafPop(Position);
 
    Position ascend(Position);
    Position descend(Position, NavigationDirection);
 
    StoredNode &nodeAt(Position);
 
    FlexibleArray<StoredNode> nodes_;
    // No more data members should follow! See FlexibleArray<> for details.
};
 
class PageStack
{
public:
    typedef std::atomic<size_t> Levels_t;
 
    // XXX: The actual type may have been on PagePool::Init() but may conflict
    // with PageLimit(), StoreMapSliceId, Rock::SwapDirRr::slotLimitActual(),
    // Rock::SlotId, PageId::number, etc.
    typedef unsigned int PageCount;
 
    // XXX: poolId, pageSize look misplaced due to messy separation of PagePool
    // (which should support multiple Segments but does not) and PageStack
    // (which should not calculate the Segment size but does) duties.
    class Config {
    public:
        uint32_t poolId = 0; 
        size_t pageSize = 0; 
        PageCount capacity = 0; 
 
        bool createFull = false;
    };
 
    explicit PageStack(const Config &);
 
    PageCount capacity() const { return config_.capacity; }
    size_t pageSize() const { return config_.pageSize; }
    PageCount size() const { return size_.load(); }
 
    bool pop(PageId &page);
    void push(PageId &page);
 
    bool pageIdIsValid(const PageId &page) const;
 
    static size_t SharedMemorySize(const Config &);
    size_t sharedMemorySize() const;
 
    static size_t StackSize(const PageCount capacity);
    size_t stackSize() const;
 
    static size_t LevelsPaddingSize(const PageCount capacity);
    size_t levelsPaddingSize() const { return LevelsPaddingSize(config_.capacity); }
 
    static PoolId IdForMemStoreSpace() { return 10; }
    static PoolId IdForMultipurposePool() { return 200; } // segments could use 2xx
    static PoolId IdForSwapDirSpace(const int dirIdx) { return 900 + dirIdx + 1; }
 
private:
    const Config config_;
    std::atomic<PageCount> size_;
 
    IdSet ids_; 
    // No more data members should follow! See IdSet for details.
};
 
} // namespace Mem
 
} // namespace Ipc
 
#endif /* SQUID_SRC_IPC_MEM_PAGESTACK_H */