StoredBitSet.hxx

Go to the documentation of this file.

 
#ifndef _UTILS_STOREDBITSET_HXX_
#define _UTILS_STOREDBITSET_HXX_
 
#include <stdint.h>
#include <string.h>
 
#include "utils/macros.h"
#include "utils/Atomic.hxx"
 
class StoredBitSet
{
public:
    virtual StoredBitSet &set_bit(unsigned offset, bool value) = 0;
 
    virtual bool get_bit(unsigned offset) = 0;
 
    virtual StoredBitSet &set_multi(
        unsigned offset, unsigned size, unsigned value) = 0;
 
    virtual unsigned get_multi(unsigned offset, unsigned size) = 0;
 
    virtual unsigned size() = 0;
 
    virtual void flush() = 0;
 
    virtual void lock_and_flush() = 0;
};
 
class ShadowedStoredBitSet : public StoredBitSet, protected Atomic
{
public:
    StoredBitSet &set_bit(unsigned offset, bool value) override {
        HASSERT(offset < size_);
        auto* shadow_ptr = shadow_ + (offset >> 5);
        auto bit = (UINT32_C(1) << (offset & 31));
        if (value) {
            if (__atomic_fetch_or(shadow_ptr, bit, __ATOMIC_SEQ_CST) & bit) {
                return *this; // nothing to do
            }
        } else {
            if ((__atomic_fetch_and(shadow_ptr, ~bit, __ATOMIC_SEQ_CST) & bit) == 0) {
                return *this; // nothing to do
            }
        }
        cell_offs_t d = offset / granularity_;
        __atomic_fetch_or(dirty_ + (d >> 5), UINT32_C(1) << (d & 31), __ATOMIC_SEQ_CST);
        update_dirty_bounds(d);
        return *this;
    }
 
    bool get_bit(unsigned offset) override {
        HASSERT(offset < size_);
        return shadow_[offset >> 5] & (UINT32_C(1) << (offset & 31));
    }
 
    StoredBitSet &set_multi(
        unsigned offset, unsigned size, unsigned value) override {
        HASSERT(size <= 32);
        HASSERT(size > 0);
        HASSERT(offset + size <= size_);
        if (size < 32) {
            HASSERT((value >> size) == 0);
        }
        unsigned sidx = offset >> 5;
        uint32_t smask = UINT32_C(0xFFFFFFFF);
        smask >>= (32 - size); // gets `size' count of one bits
        smask <<= (offset & 31); // moves them to the right place
        uint32_t sval = value;
        sval <<= (offset & 31);
        int rollover = size + (offset & 31) - 32;
        if (rollover > 0) {  // there are leftover bits for a second word
            uint32_t smask2 = (UINT32_C(1) << rollover) - 1;
            uint32_t sval2 = value >> (size - rollover);
            // we need to atomically update two cells.
            uint32_t old1 = shadow_[sidx], new1, old2 = shadow_[sidx + 1], new2;
            do
            {
                new1 = (old1 & ~smask) | sval;
                new2 = (old2 & ~smask2) | sval2;
            } while (!__atomic_compare_exchange_n(shadow_ + sidx, &old1, new1,
                         false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ||
                !__atomic_compare_exchange_n(shadow_ + sidx + 1, &old2, new2,
                    false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
        }
        else
        {
            // just one cell
            uint32_t old1 = shadow_[sidx], new1;
            do
            {
                new1 = (old1 & ~smask) | sval;
            } while (!__atomic_compare_exchange_n(shadow_ + sidx, &old1, new1,
                         false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
        }
        // Sets dirty bits.
        unsigned d = offset / granularity_;
        update_dirty_bounds(d);
        unsigned de = (offset + size - 1)/granularity_;
        update_dirty_bounds(de);
        if (de > highestDirty_) highestDirty_ = de;
        while (d <= de) {
            __atomic_fetch_or(dirty_ + (d >> 5),(UINT32_C(1)<<(d & 31)), __ATOMIC_SEQ_CST);
            d++;
        }
        return *this;
    }
 
    unsigned get_multi(unsigned offset, unsigned size) override {
        HASSERT(size <= 32);
        HASSERT(size > 0);
        HASSERT(offset + size <= size_);
        unsigned val = shadow_[offset >> 5] >> (offset & 31);
        int rollover = size + (offset & 31) - 32;
        if (rollover > 0) {
            val |= shadow_[(offset >> 5) + 1] << (size - rollover);
        }
        if (size < 32) {
            val &= (UINT32_C(1) << size) - 1;
        }
        return val;
    }
    
    unsigned size() override {
        return size_;
    }
 
    void lock_and_flush() override {
        AtomicHolder h(this);
        flush();
    }
    
protected:
    ShadowedStoredBitSet(unsigned size, uint8_t granularity)
        : size_(size), granularity_(granularity) {
        unsigned ssize = (size + 31) >> 5;
        shadow_ = new uint32_t[ssize];
        memset(shadow_, 0, ssize * 4);
        unsigned dsize = (num_cells() + 31) >> 5;
        dirty_ = new uint32_t[dsize];
        memset(dirty_, 0, dsize * 4);
        HASSERT(num_cells() < NO_CELL);
    }
 
    ~ShadowedStoredBitSet() {
        delete[] shadow_;
        delete[] dirty_;
    }
 
    typedef uint8_t cell_offs_t;
    typedef unsigned bit_offs_t;
 
    static constexpr cell_offs_t NO_CELL = static_cast<cell_offs_t>(-1);
 
    cell_offs_t next_dirty() {
        if (lowestDirty_ > highestDirty_ || lowestDirty_ >= num_cells()) {
            lowestDirty_ = NO_CELL;
            highestDirty_ = 0;
            return NO_CELL;
        }
        unsigned dirty_idx = lowestDirty_ / 32;
        bool fresh_dirty = false;
        while (dirty_idx < dirty_size_uint32() && dirty_[dirty_idx] == 0) {
            ++dirty_idx;
            fresh_dirty = true;
        }
        if (dirty_idx >= dirty_size_uint32()) {
            lowestDirty_ = NO_CELL;
            highestDirty_ = 0;
            return NO_CELL;
        }
        unsigned bit_ofs = 0;
        if (!fresh_dirty) {
            bit_ofs = lowestDirty_ & 31;
        } else {
        }
        while (((UINT32_C(1)<<bit_ofs) & dirty_[dirty_idx]) == 0) {
            ++bit_ofs;
        }
        lowestDirty_ = (dirty_idx << 5) + bit_ofs;
        return lowestDirty_;
    }
 
    void clear_dirty(cell_offs_t cell) {
        HASSERT(cell < num_cells());
        dirty_[cell >> 5] &= ~(UINT32_C(1)<<(cell & 31));
        if (cell == lowestDirty_) {
            ++lowestDirty_;
        }
    }
 
    bool is_dirty(cell_offs_t cell) {
        HASSERT(cell < num_cells());
        return dirty_[cell >>5] & (UINT32_C(1)<<(cell & 31));
    }
    
    cell_offs_t num_cells() {
        return (size_ + granularity_ - 1) / granularity_;
    }
    
private:
    unsigned dirty_size_uint32() {
        return (num_cells() + 31) / 32;
    }
 
    void update_dirty_bounds(cell_offs_t d)
    {
        cell_offs_t old_val = lowestDirty_;
        do
        {
            if (d >= old_val)
                break;
        } while (!__atomic_compare_exchange_n(&lowestDirty_, &old_val, d, false,
                     __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
        old_val = highestDirty_;
        do
        {
            if (d <= old_val)
                break;
        } while (!__atomic_compare_exchange_n(&highestDirty_, &old_val, d,
                     false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
    }
 
    const unsigned size_;
    const uint8_t granularity_;
    cell_offs_t lowestDirty_{NO_CELL};
    cell_offs_t highestDirty_{0};
    
    uint32_t *shadow_;
    uint32_t *dirty_;
};
 
#endif // _UTILS_STOREDBITSET_HXX_