/* * Copyright (C) 1996-2023 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_STOREMAP_H #define SQUID_SRC_IPC_STOREMAP_H #include "ipc/mem/FlexibleArray.h" #include "ipc/mem/Pointer.h" #include "ipc/ReadWriteLock.h" #include "sbuf/SBuf.h" #include "store/forward.h" #include "store_key_md5.h" #include namespace Ipc { typedef int32_t StoreMapSliceId; /// a piece of Store entry, linked to other pieces, forming a chain /// slices may be appended by writers while readers read the entry class StoreMapSlice { public: typedef uint32_t Size; StoreMapSlice(): size(0), next(-1) {} StoreMapSlice(const StoreMapSlice &o) { size.exchange(o.size); next.exchange(o.next); } StoreMapSlice &operator =(const StoreMapSlice &o) { size.store(o.size); next.store(o.next); return *this; } /// restore default-constructed state void clear() { size = 0; next = -1; } std::atomic size; ///< slice contents size std::atomic next; ///< ID of the next entry slice }; /// Maintains shareable information about a StoreEntry as a whole. /// An anchor points to one or more StoreEntry slices. This is the /// only lockable part of shared StoreEntry information, providing /// protection for all StoreEntry slices. class StoreMapAnchor { public: StoreMapAnchor(); /// store StoreEntry key and basics for an inode slot void set(const StoreEntry &anEntry, const cache_key *aKey = nullptr); /// load StoreEntry basics that were previously stored with set() void exportInto(StoreEntry &) const; void setKey(const cache_key *const aKey); bool sameKey(const cache_key *const aKey) const; /// undo the effects of set(), setKey(), etc., but keep locks and state void rewind(); /* entry state may change immediately after calling these methods unless * the caller holds an appropriate lock */ bool empty() const { return !key[0] && !key[1]; } bool reading() const { return lock.readers; } bool writing() const { return lock.writing; } bool complete() const { return !empty() && !writing(); } public: mutable ReadWriteLock lock; ///< protects slot data below std::atomic waitingToBeFreed; ///< may be accessed w/o a lock /// whether StoreMap::abortWriting() was called for a read-locked entry std::atomic writerHalted; // fields marked with [app] can be modified when appending-while-reading // fields marked with [update] can be modified when updating-while-reading uint64_t key[2] = {0, 0}; ///< StoreEntry key // STORE_META_STD TLV field from StoreEntry struct Basics { void clear() { timestamp = 0; lastref = 0; expires = 0; lastmod = 0; swap_file_sz.store(0); refcount = 0; flags = 0; } time_t timestamp = 0; time_t lastref = 0; time_t expires = 0; time_t lastmod = 0; std::atomic swap_file_sz; // [app] uint16_t refcount = 0; uint16_t flags = 0; } basics; /// where the chain of StoreEntry slices begins [app] std::atomic start; /// where the updated chain prefix containing metadata/headers ends [update] /// if unset, this anchor points to a chain that was never updated std::atomic splicingPoint; }; /// an array of shareable Items /// must be the last data member or, if used as a parent class, the last parent template class StoreMapItems { public: typedef C Item; typedef Ipc::Mem::Owner< StoreMapItems > Owner; explicit StoreMapItems(const int aCapacity): capacity(aCapacity), items(aCapacity) {} size_t sharedMemorySize() const { return SharedMemorySize(capacity); } static size_t SharedMemorySize(const int aCapacity) { return sizeof(StoreMapItems) + aCapacity*sizeof(Item); } Item &at(const int index) { assert(index >= 0); assert(index < capacity); return items[index]; } const Item &at(const int index) const { return const_cast&>(*this).at(index); } /// reset all items to the same value void fill(const Item &value) { for (int index = 0; index < capacity; ++index) items[index] = value; } const int capacity; ///< total number of items Ipc::Mem::FlexibleArray items; ///< storage }; /// StoreMapSlices indexed by their slice ID. typedef StoreMapItems StoreMapSlices; /// StoreMapAnchors (indexed by fileno) plus /// sharing-safe basic housekeeping info about Store entries class StoreMapAnchors { public: typedef Ipc::Mem::Owner< StoreMapAnchors > Owner; explicit StoreMapAnchors(const int aCapacity); size_t sharedMemorySize() const; static size_t SharedMemorySize(const int anAnchorLimit); std::atomic count; ///< current number of entries std::atomic victim; ///< starting point for purge search const int capacity; ///< total number of anchors Ipc::Mem::FlexibleArray items; ///< anchors storage }; // TODO: Find an elegant way to use StoreMapItems in StoreMapAnchors /// StoreMapAnchor positions, indexed by entry "name" (i.e., the entry key hash) typedef StoreMapItems< std::atomic > StoreMapFileNos; /// Aggregates information required for updating entry metadata and headers. class StoreMapUpdate { public: /// During an update, the stored entry has two editions: stale and fresh. class Edition { public: Edition(): anchor(nullptr), fileNo(-1), name(-1), splicingPoint(-1) {} /// whether this entry edition is currently used/initialized explicit operator bool() const { return anchor; } StoreMapAnchor *anchor; ///< StoreMap::anchors[fileNo], for convenience/speed sfileno fileNo; ///< StoreMap::fileNos[name], for convenience/speed sfileno name; ///< StoreEntry position in StoreMap::fileNos, for swapping Editions /// the last slice in the chain still containing metadata/headers StoreMapSliceId splicingPoint; }; explicit StoreMapUpdate(StoreEntry *anEntry); StoreMapUpdate(const StoreMapUpdate &other); ~StoreMapUpdate(); StoreMapUpdate &operator =(const StoreMapUpdate &other) = delete; StoreEntry *entry; ///< the store entry being updated Edition stale; ///< old anchor and chain Edition fresh; ///< new anchor and the updated chain prefix }; class StoreMapCleaner; /// Manages shared Store index (e.g., locking/unlocking/freeing entries) using /// StoreMapFileNos indexed by hashed entry keys (a.k.a. entry names), /// StoreMapAnchors indexed by fileno, and /// StoreMapSlices indexed by slice ID. class StoreMap { public: typedef StoreMapFileNos FileNos; typedef StoreMapAnchor Anchor; typedef StoreMapAnchors Anchors; typedef sfileno AnchorId; typedef StoreMapSlice Slice; typedef StoreMapSlices Slices; typedef StoreMapSliceId SliceId; typedef StoreMapUpdate Update; public: /// aggregates anchor and slice owners for Init() caller convenience class Owner { public: Owner(); ~Owner(); FileNos::Owner *fileNos; Anchors::Owner *anchors; Slices::Owner *slices; private: Owner(const Owner &); // not implemented Owner &operator =(const Owner &); // not implemented }; /// initialize shared memory static Owner *Init(const SBuf &path, const int slotLimit); StoreMap(const SBuf &aPath); /// computes map entry anchor position for a given entry key sfileno fileNoByKey(const cache_key *const key) const; /// Like strcmp(mapped, new), but for store entry versions/timestamps. /// Returns +2 if the mapped entry does not exist; -1/0/+1 otherwise. /// Comparison may be inaccurate unless the caller is a lock holder. int compareVersions(const sfileno oldFileno, time_t newVersion) const; /// finds, locks, and returns an anchor for an empty key position, /// erasing the old entry (if any) Anchor *openForWriting(const cache_key *const key, sfileno &fileno); /// locks and returns an anchor for the empty fileno position; if /// overwriteExisting is false and the position is not empty, returns nil Anchor *openForWritingAt(sfileno fileno, bool overwriteExisting = true); /// restrict opened for writing entry to appending operations; allow reads void startAppending(const sfileno fileno); /// successfully finish creating or updating the entry at fileno pos void closeForWriting(const sfileno fileno); /// stop writing (or updating) the locked entry and start reading it void switchWritingToReading(const sfileno fileno); /// unlock and "forget" openForWriting entry, making it Empty again /// this call does not free entry slices so the caller has to do that void forgetWritingEntry(const sfileno fileno); /// finds and locks the Update entry for an exclusive metadata update bool openForUpdating(Update &update, sfileno fileNoHint); /// makes updated info available to others, unlocks, and cleans up void closeForUpdating(Update &update); /// undoes partial update, unlocks, and cleans up void abortUpdating(Update &update); /// the caller must hold a lock on the entry /// \returns nullptr unless the slice is readable const Anchor *peekAtReader(const sfileno fileno) const; /// the caller must hold a lock on the entry /// \returns nullptr unless the slice is writeable const Anchor *peekAtWriter(const sfileno fileno) const; /// the caller must hold a lock on the entry /// \returns the corresponding Anchor const Anchor &peekAtEntry(const sfileno fileno) const; /// free the entry if possible or mark it as waiting to be freed if not /// \returns whether the entry was neither empty nor marked bool freeEntry(const sfileno); /// free the entry if possible or mark it as waiting to be freed if not /// does nothing if we cannot check that the key matches the cached entry void freeEntryByKey(const cache_key *const key); /// whether the entry with the given key exists and was marked as /// "waiting to be freed" some time ago bool markedForDeletion(const cache_key *const); /// whether the index contains a valid readable entry with the given key bool hasReadableEntry(const cache_key *const); /// opens entry (identified by key) for reading, increments read level const Anchor *openForReading(const cache_key *const key, sfileno &fileno); /// opens entry (identified by sfileno) for reading, increments read level const Anchor *openForReadingAt(const sfileno, const cache_key *const); /// closes open entry after reading, decrements read level void closeForReading(const sfileno fileno); /// same as closeForReading() but also frees the entry if it is unlocked void closeForReadingAndFreeIdle(const sfileno fileno); /// openForReading() but creates a new entry if there is no old one const Anchor *openOrCreateForReading(const cache_key *, sfileno &); /// writeable slice within an entry chain created by openForWriting() Slice &writeableSlice(const AnchorId anchorId, const SliceId sliceId); /// readable slice within an entry chain opened by openForReading() const Slice &readableSlice(const AnchorId anchorId, const SliceId sliceId) const; /// writeable anchor for the entry created by openForWriting() Anchor &writeableEntry(const AnchorId anchorId); /// readable anchor for the entry created by openForReading() const Anchor &readableEntry(const AnchorId anchorId) const; /// prepare a chain-unaffiliated slice for being added to an entry chain void prepFreeSlice(const SliceId sliceId); /// Returns the ID of the entry slice containing n-th byte or /// a negative ID if the entry does not store that many bytes (yet). /// Requires a read lock. SliceId sliceContaining(const sfileno fileno, const uint64_t nth) const; /// stop writing the entry, freeing its slot for others to use if possible void abortWriting(const sfileno fileno); /// either finds and frees an entry with at least 1 slice or returns false bool purgeOne(); /// validates locked hit metadata and calls freeEntry() for invalid entries /// \returns whether hit metadata is correct bool validateHit(const sfileno); void disableHitValidation() { hitValidation = false; } /// copies slice to its designated position void importSlice(const SliceId sliceId, const Slice &slice); /* SwapFilenMax limits the number of entries, but not slices or slots */ bool validEntry(const int n) const; ///< whether n is a valid slice coordinate bool validSlice(const int n) const; ///< whether n is a valid slice coordinate int entryCount() const; ///< number of writeable and readable entries int entryLimit() const; ///< maximum entryCount() possible int sliceLimit() const; ///< maximum number of slices possible /// adds approximate current stats to the supplied ones void updateStats(ReadWriteLockStats &stats) const; StoreMapCleaner *cleaner; ///< notified before a readable entry is freed protected: const SBuf path; ///< cache_dir path or similar cache name; for logging Mem::Pointer fileNos; ///< entry inodes (starting blocks) Mem::Pointer anchors; ///< entry inodes (starting blocks) Mem::Pointer slices; ///< chained entry pieces positions private: /// computes entry name (i.e., key hash) for a given entry key sfileno nameByKey(const cache_key *const key) const; /// computes anchor position for a given entry name sfileno fileNoByName(const sfileno name) const; void relocate(const sfileno name, const sfileno fileno); Anchor &anchorAt(const sfileno fileno); const Anchor &anchorAt(const sfileno fileno) const; Anchor &anchorByKey(const cache_key *const key); Slice &sliceAt(const SliceId sliceId); const Slice &sliceAt(const SliceId sliceId) const; Anchor *openForReading(Slice &s); bool openKeyless(Update::Edition &edition); void closeForUpdateFinal(Update &update); typedef std::function NameFilter; // a "name"-based test bool visitVictims(const NameFilter filter); void freeChain(const sfileno fileno, Anchor &inode, const bool keepLock); void freeChainAt(SliceId sliceId, const SliceId splicingPoint); /// whether paranoid_hit_validation should be performed bool hitValidation; }; /// API for adjusting external state when dirty map slice is being freed class StoreMapCleaner { public: virtual ~StoreMapCleaner() {} /// adjust slice-linked state before a locked Readable slice is erased virtual void noteFreeMapSlice(const StoreMapSliceId sliceId) = 0; }; } // namespace Ipc // We do not reuse FileMap because we cannot control its size, // resulting in sfilenos that are pointing beyond the database. #endif /* SQUID_SRC_IPC_STOREMAP_H */