ClpMap.h

Go to the documentation of this file.

/*
 * 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_BASE_CLPMAP_H
#define SQUID__SRC_BASE_CLPMAP_H
 
#include "mem/PoolingAllocator.h"
#include "SquidMath.h"
#include "time/gadgets.h"
 
#include <functional>
#include <limits>
#include <list>
#include <optional>
#include <unordered_map>
 
template<class Value>
uint64_t
DefaultMemoryUsage(const Value &e)
{
    return sizeof(e);
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &) = DefaultMemoryUsage>
class ClpMap
{
public:
    using key_type = Key;
    using mapped_type = Value;
 
    using Ttl = int;
 
    class Entry
    {
    public:
        Entry(const Key &, const Value &, const Ttl);
 
        bool expired() const { return expires < squid_curtime; }
 
    public:
        Key key; 
        Value value; 
        time_t expires = 0; 
        uint64_t memCounted = 0; 
    };
 
    using Entries = std::list<Entry, PoolingAllocator<Entry> >;
    using EntriesIterator = typename Entries::iterator;
    using ConstEntriesIterator = typename Entries::const_iterator;
 
    explicit ClpMap(const uint64_t capacity) { setMemLimit(capacity); }
    ClpMap(uint64_t capacity, Ttl defaultTtl);
    ~ClpMap() = default;
 
    // copying disabled because it may be expensive for large maps
    // moving (implicitly) disabled for simplicity sake
    ClpMap(const ClpMap &) = delete;
    ClpMap &operator =(const ClpMap &) = delete;
 
    const Value *get(const Key &);
 
    bool add(const Key &, const Value &, Ttl);
 
    bool add(const Key &key, const Value &v) { return add(key, v, defaultTtl_); }
 
    void del(const Key &);
 
    void setMemLimit(uint64_t newLimit);
 
    uint64_t memLimit() const { return memLimit_; }
 
    uint64_t freeMem() const { return memLimit() - memoryUsed(); }
 
    uint64_t memoryUsed() const { return memUsed_; }
 
    size_t entries() const { return entries_.size(); }
 
    ConstEntriesIterator cbegin() const { return entries_.cbegin(); }
    ConstEntriesIterator cend() const { return entries_.cend(); }
    ConstEntriesIterator begin() const { return cbegin(); }
    ConstEntriesIterator end() const { return cend(); }
 
private:
    using IndexItem = std::pair<const Key, EntriesIterator>;
    using Index = std::unordered_map<Key, EntriesIterator, std::hash<Key>, std::equal_to<Key>, PoolingAllocator<IndexItem> >;
    using IndexIterator = typename Index::iterator;
 
    static std::optional<uint64_t> MemoryCountedFor(const Key &, const Value &);
 
    void trim(uint64_t wantSpace);
    void erase(const IndexIterator &);
    IndexIterator find(const Key &);
 
    Entries entries_;
 
    Index index_;
 
    Ttl defaultTtl_ = std::numeric_limits<Ttl>::max();
 
    uint64_t memLimit_ = 0;
 
    uint64_t memUsed_ = 0;
};
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
ClpMap<Key, Value, MemoryUsedBy>::ClpMap(const uint64_t capacity, const Ttl defaultTtl):
    defaultTtl_(defaultTtl)
{
    assert(defaultTtl >= 0);
    setMemLimit(capacity);
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
void
ClpMap<Key, Value, MemoryUsedBy>::setMemLimit(const uint64_t newLimit)
{
    if (memUsed_ > newLimit)
        trim(memLimit_ - newLimit);
    memLimit_ = newLimit;
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
typename ClpMap<Key, Value, MemoryUsedBy>::IndexIterator
ClpMap<Key, Value, MemoryUsedBy>::find(const Key &key)
{
    const auto i = index_.find(key);
    if (i == index_.end())
        return i;
 
    const auto entryPosition = i->second;
    if (!entryPosition->expired()) {
        if (entryPosition != entries_.begin())
            entries_.splice(entries_.begin(), entries_, entryPosition);
        return i;
    }
    // else fall through to cleanup
 
    erase(i);
    return index_.end();
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
const Value *
ClpMap<Key, Value, MemoryUsedBy>::get(const Key &key)
{
    const auto i = find(key);
    if (i != index_.end()) {
        const auto &entry = *(i->second);
        return &entry.value;
    }
    return nullptr;
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
std::optional<uint64_t>
ClpMap<Key, Value, MemoryUsedBy>::MemoryCountedFor(const Key &k, const Value &v)
{
    // Both storage and index store keys, but we count keySz once, assuming that
    // copying a Key does not consume more memory. This assumption holds for
    // Key=SBuf, but, ideally, we should be outsourcing this decision to another
    // configurable function, storing each key once, or hard-coding Key=SBuf.
    const auto keySz = k.length();
 
    // approximate calculation (e.g., containers store wrappers not value_types)
    return NaturalSum<uint64_t>(
               keySz,
               // storage
               sizeof(typename Entries::value_type),
               MemoryUsedBy(v),
               // index
               sizeof(typename Index::value_type));
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
bool
ClpMap<Key, Value, MemoryUsedBy>::add(const Key &key, const Value &v, const Ttl ttl)
{
    // optimization: avoid del() search, MemoryCountedFor() in always-empty maps
    if (memLimit() == 0)
        return false;
 
    del(key);
 
    if (ttl < 0)
        return false; // already expired; will never be returned by get()
 
    const auto memoryRequirements = MemoryCountedFor(key, v);
    if (!memoryRequirements)
        return false; // cannot even compute memory requirements
 
    const auto wantSpace = memoryRequirements.value();
    if (wantSpace > memLimit() || wantSpace == 0) // 0 is 64-bit integer overflow
        return false; // will never fit
    trim(wantSpace);
 
    auto &addedEntry = entries_.emplace_front(key, v, ttl);
    index_.emplace(key, entries_.begin());
 
    addedEntry.memCounted = wantSpace;
    memUsed_ += wantSpace;
    assert(memUsed_ >= wantSpace); // no overflows
    return true;
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
void
ClpMap<Key, Value, MemoryUsedBy>::erase(const IndexIterator &i)
{
    assert(i != index_.end());
    const auto entryPosition = i->second;
 
    assert(entryPosition != entries_.end());
    const auto sz = entryPosition->memCounted;
    assert(memUsed_ >= sz);
    memUsed_ -= sz;
 
    index_.erase(i); // destroys a "pointer" to our Entry
    entries_.erase(entryPosition); // destroys our Entry
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
void
ClpMap<Key, Value, MemoryUsedBy>::del(const Key &key)
{
    const auto i = find(key);
    if (i != index_.end())
        erase(i);
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
void
ClpMap<Key, Value, MemoryUsedBy>::trim(const uint64_t wantSpace)
{
    assert(wantSpace <= memLimit()); // no infinite loops and in-vain trimming
    while (freeMem() < wantSpace) {
        assert(!entries_.empty());
        // TODO: Purge expired entries first. They are useless, but their
        // presence may lead to purging potentially useful fresh entries here.
        del(entries_.rbegin()->key);
    }
}
 
template <class Key, class Value, uint64_t MemoryUsedBy(const Value &)>
ClpMap<Key, Value, MemoryUsedBy>::Entry::Entry(const Key &aKey, const Value &v, const Ttl ttl) :
    key(aKey),
    value(v),
    expires(0) // reset below
{
    SetToNaturalSumOrMax(expires, squid_curtime, ttl);
}
 
#endif /* SQUID__SRC_BASE_CLPMAP_H */