w_gc_pool_forest.h

Go to the documentation of this file.

/*
 * (c) Copyright 2014, Hewlett-Packard Development Company, LP
 */
#ifndef __W_GC_POOL_FOREST_H
#define __W_GC_POOL_FOREST_H

#include <cstdint>
#include <memory>
#include "AtomicCounter.hpp"
#include "w_defines.h"
#include "w_debug.h"
#include "lsn.h"

template<class T> class GcPointer;

template<class T>
struct GcSegment;
template<class T>
struct GcGeneration;
template<class T>
struct GcPoolForest;

typedef int32_t gc_status;

typedef uint32_t gc_aba;

typedef uint8_t gc_generation;

const size_t GC_MAX_GENERATIONS = (1 << (sizeof(gc_generation) * 8));

typedef uint8_t gc_segment;

const size_t GC_MAX_SEGMENTS = (1 << (sizeof(gc_segment) * 8));

typedef uint16_t gc_offset;

const size_t GC_MAX_OFFSETS = (1 << (sizeof(gc_offset) * 8));

typedef uint64_t gc_thread_id;

union gc_pointer_raw {
    // so far 4/1/1/2. Maybe 2/2/2/2 might make sense if we need more generations/segments.
    struct {
        gc_status status;
        gc_generation generation;
        gc_segment segment;
        gc_offset offset;
    } components;

    uint64_t word;
};

// csauer: gcc 6+ needs this
inline bool operator==(const gc_pointer_raw& a, const gc_pointer_raw& b) {
    return a.word == b.word;
};

inline bool operator!=(const gc_pointer_raw& a, const gc_pointer_raw& b) {
    return a.word != b.word;
};

template<class T>
class GcPointer {
public:
    GcPointer() {
        _raw.word = 0;
    }

    explicit GcPointer(gc_pointer_raw raw) : _raw(raw) {}

    GcPointer(const GcPointer& other) {
        operator=(other);
    }

    GcPointer& operator=(const GcPointer& other) {
        // ACCESS_ONCE semantics to make it at least regular.
        _raw.word = static_cast<const volatile gc_pointer_raw&>(other._raw).word;
        return *this;
    }

    bool operator==(const GcPointer& other) const {
        return _raw == other._raw;
    }

    bool operator!=(const GcPointer& other) const {
        return _raw != other._raw;
    }

    bool is_equal_address(const GcPointer& other) const {
        return _raw.components.generation == other._raw.components.generation
               && _raw.components.segment == other._raw.components.segment
               && _raw.components.offset == other._raw.components.offset;
    }

    T* dereference(GcPoolForest<T>& pool) const;

    void set_mark(bool on) {
        _raw.components.status = get_aba() | (on ? 0x80000000 : 0);
    }

    bool is_marked() const {
        return _raw.components.status < 0;
    }

    gc_aba get_aba() const {
        return static_cast<gc_aba>(_raw.components.status & 0x7FFFFFFF);
    }

    void set_aba(gc_aba stamp) {
        _raw.components.status = (_raw.components.status & 0x80000000)
                                 | static_cast<gc_status>(stamp);
    }

    gc_generation get_generation() const {
        return _raw.components.generation;
    }

    gc_segment get_segment() const {
        return _raw.components.segment;
    }

    gc_offset get_offset() const {
        return _raw.components.offset;
    }

    bool is_null() const {
        return get_generation() == 0;
    }

    gc_pointer_raw& raw() {
        return _raw;
    }

    gc_pointer_raw raw() const {
        return _raw;
    }

    bool atomic_cas(const GcPointer& expected, const GcPointer& desired) {
        gc_pointer_raw expected_tmp = expected._raw;
        return lintel::unsafe::atomic_compare_exchange_strong<gc_pointer_raw>(
                &_raw, &expected_tmp, desired._raw);
    }

    GcPointer atomic_swap(const GcPointer& new_ptr) {
        return GcPointer(lintel::unsafe::atomic_exchange<gc_pointer_raw>(&_raw, new_ptr._raw));
    }

protected:
    gc_pointer_raw _raw;
};

template<class T>
struct GcSegment {
    GcSegment(gc_offset size) :
            owner(0),
            total_objects(size),
            allocated_objects(0) {
        objects = new T[size];
        w_assert1(objects != nullptr);
    }

    ~GcSegment() {
        delete[] objects;
    }

    void recycle() {
        owner = 0;
        allocated_objects = 0;
    }

    gc_thread_id owner;

    gc_offset total_objects;

    gc_offset allocated_objects;

    T* objects;
};

template<class T>
struct GcGeneration {
    GcGeneration(uint32_t generation_nowrap_arg) :
            retire_suggested(false),
            total_segments(0),
            allocated_segments(0),
            generation_nowrap(generation_nowrap_arg) {}

    ~GcGeneration() {
        DBGOUT1(<<"Destroying a GC Generation " << generation_nowrap
                        << ". total_segments=" << total_segments
                        << ", allocated_segments=" << allocated_segments);
        for (gc_segment i = 0; i < total_segments; ++i) {
            delete segments[i];
        }
    }

    uint32_t get_free_count() const {
        return total_segments - allocated_segments;
    }

    bool preallocate_segments(size_t segment_count, gc_offset segment_size);

    void recycle(uint32_t generation_nowrap_arg) {
        retire_suggested = false;
        generation_nowrap = generation_nowrap_arg;
        for (uint32_t seg = 0; seg < total_segments; ++seg) {
            if (segments[seg]->owner != 0) {
                segments[seg]->recycle();
            }
        }
        allocated_segments = 0;
    }

    bool retire_suggested;

    uint32_t total_segments;

    uint32_t allocated_segments;

    uint32_t generation_nowrap;

    GcSegment<T>* segments[GC_MAX_SEGMENTS];
};

struct GcPoolEntry {
    gc_pointer_raw gc_pointer;
};

struct GcWakeupFunctor {
    virtual ~GcWakeupFunctor() {}

    virtual void wakeup() = 0;
};

template<class T>
struct GcPoolForest {
    GcPoolForest(const char* debug_name, uint32_t desired_gens,
                 size_t initial_segment_count, gc_offset initial_segment_size) :
            name(debug_name),
            head_nowrap(1), // generation=0 is an invalid generation, so we start from 1.
            curr_nowrap(1),
            tail_nowrap(2),
            desired_generations(desired_gens),
            gc_wakeup_functor(nullptr) {
        // We always have at least one active generation
        generations[0] = nullptr;
        generations[1] = new GcGeneration<T>(1);
        if (initial_segment_count > 0) {
            generations[1]->preallocate_segments(initial_segment_count, initial_segment_size);
        }
        epochs[0].set(0);
        epochs[1].set(0);
    }

    ~GcPoolForest() {
        DBGOUT1(<< name << ": Destroying a GC Pool Forest. head_nowrap=" << head_nowrap
                        << ", tail_nowrap=" << tail_nowrap);
        for (size_t i = head_nowrap; i < tail_nowrap; ++i) {
            delete generations[wrap(i)];
        }
    }

    T* resolve_pointer(const GcPointer<T>& pointer) {
        return pointer.raw();
    }

    T* resolve_pointer(gc_pointer_raw pointer);

    GcGeneration<T>* resolve_generation(gc_pointer_raw pointer) {
        return resolve_generation(pointer.components.generation);
    }

    GcGeneration<T>* resolve_generation(gc_generation gen) {
        return generations[gen];
    }

    GcSegment<T>* resolve_segment(gc_pointer_raw pointer) {
        return resolve_segment(pointer.components.generation, pointer.components.segment);
    }

    GcSegment<T>* resolve_segment(gc_generation gen, gc_segment seg) {
        w_assert1(is_valid_generation(gen));
        GcGeneration<T>* generation = resolve_generation(gen);
        w_assert1(seg < generation->total_segments);
        return generation->segments[seg];
    }

    T* allocate(gc_pointer_raw& next, gc_thread_id self);

    void deallocate(T* pointer) {
        deallocate(pointer->gc_pointer);
    }

    void deallocate(gc_pointer_raw pointer);

    gc_pointer_raw occupy_segment(gc_thread_id self);

    gc_generation head() const {
        return wrap(head_nowrap);
    }

    gc_generation tail() const {
        return wrap(tail_nowrap);
    }

    gc_generation curr() const {
        return wrap(curr_nowrap);
    }

    size_t active_generations() const {
        return tail_nowrap - head_nowrap;
    }

    GcGeneration<T>* head_generation() {
        return generations[head()];
    }

    GcGeneration<T>* curr_generation() {
        return generations[curr()];
    }

    bool is_valid_generation(gc_generation generation) const {
        // CS: changed check conditions because otherwise the tail might wrap
        // around and in that case it will be greater than the given generation
        // return generation != 0 && generation >= head() && generation < tail();
        if (generation == 0) {
            return false;
        }
        if (head() < tail()) {
            return generation >= head() && generation < tail();
        } else if (tail() < head()) {
            return (generation >= head() && generation < GC_MAX_GENERATIONS)
                   || generation < tail();
        }
        return false;
    }

    bool advance_generation(lsn_t low_water_mark, lsn_t now,
                            size_t initial_segment_count, gc_offset segment_size);

    void retire_generations(lsn_t low_water_mark, lsn_t recycle_now = lsn_t::null);

    void mfence() const {
        lintel::atomic_thread_fence(lintel::memory_order_seq_cst);
    }

    static gc_generation wrap(size_t i) {
        return static_cast<gc_generation>(i);
    }

    const char* name;

    uint32_t head_nowrap;

    uint32_t curr_nowrap;

    uint32_t tail_nowrap;

    uint32_t desired_generations;

    GcGeneration<T>* generations[GC_MAX_GENERATIONS];

    lsn_t epochs[GC_MAX_GENERATIONS];

    GcWakeupFunctor* gc_wakeup_functor;
};

template<class T>
inline T* GcPoolForest<T>::resolve_pointer(gc_pointer_raw pointer) {
    gc_generation generation = pointer.components.generation;
    if (generation == 0) {
        return nullptr;
    }

    lintel::atomic_thread_fence(lintel::memory_order_consume);
    w_assert1(is_valid_generation(generation));
    GcGeneration<T>* gen = generations[generation];
    w_assert1(gen != nullptr);

    w_assert1(pointer.components.segment < gen->allocated_segments);
    GcSegment<T>* segment = gen->segments[pointer.components.segment];
    w_assert1(segment != nullptr);

    gc_offset offset = pointer.components.offset;
    w_assert1(offset < segment->total_objects);
    w_assert1(offset < segment->allocated_objects);

    return segment->objects + offset;
}

template<class T>
inline T* GcPoolForest<T>::allocate(gc_pointer_raw& next, gc_thread_id self) {
    if (!is_valid_generation(next.components.generation)
        || generations[next.components.generation]->retire_suggested
        || next.components.generation != curr()) {
        next = occupy_segment(self);
    }

    w_assert1(is_valid_generation(next.components.generation));
    GcGeneration<T>* gen = generations[next.components.generation];
    w_assert1(gen != nullptr);

    if (next.components.segment >= gen->allocated_segments
        || gen->segments[next.components.segment]->owner != self
        || gen->segments[next.components.segment]->allocated_objects
           >= gen->segments[next.components.segment]->total_objects) {
        next = occupy_segment(self);
        gen = generations[next.components.generation];
    }
    w_assert1(next.components.segment < gen->allocated_segments);
    GcSegment<T>* segment = gen->segments[next.components.segment];
    w_assert1(segment != nullptr);
    w_assert1(segment->owner == self);
    w_assert1(segment->allocated_objects < segment->total_objects);

    next.components.offset = segment->allocated_objects;
    T* ret = segment->objects + next.components.offset;
    ret->gc_pointer = next;

    ++segment->allocated_objects;
    next.components.offset = segment->allocated_objects;
    return ret;
}

template<class T>
inline void GcPoolForest<T>::deallocate(gc_pointer_raw pointer) {
    // We don't do anything in deallocate.
    w_assert1(is_valid_generation(pointer.components.generation));
    GcGeneration<T>* gen = generations[pointer.components.generation];
    w_assert1(gen != nullptr);

    w_assert1(pointer.components.segment < gen->allocated_segments);
    GcSegment<T>* segment = gen->segments[pointer.components.segment];
    w_assert1(segment != nullptr);

    // we don't check double-free or anything
    w_assert1(pointer.components.offset < segment->allocated_objects);
}

template<class T>
inline gc_pointer_raw GcPoolForest<T>::occupy_segment(gc_thread_id self) {
    // this method is relatively infrequently called, so we can afford barriers and atomics.
    while (true) {
        mfence();
        gc_generation generation = curr();
        GcGeneration<T>* gen = generations[generation];
        if (gen->allocated_segments >= gen->total_segments) {
            // allocator threads are not catching up. This must be rare. let's sleep.
            DBGOUT0(<< name << ": GC Thread is not catching up. have to sleep. me=" << self);
            if (gc_wakeup_functor != nullptr) {
                gc_wakeup_functor->wakeup();
            }
            const uint32_t SLEEP_MICROSEC = 10000;
            ::usleep(SLEEP_MICROSEC);
            continue;
        }
        uint32_t alloc_segment = gen->allocated_segments;
        mfence();
        if (lintel::unsafe::atomic_compare_exchange_strong<uint32_t>(
                &gen->allocated_segments, &alloc_segment, alloc_segment + 1)) {
            // Okay, we are surely the only winner of the pre-allocated segment.
            GcSegment<T>* segment = gen->segments[alloc_segment];
            while (segment == nullptr) {
                // possible right after CAS in preallocate_segments. wait.
                mfence();
                DBGOUT3(<< name << ": Waiting for segment " << alloc_segment << " in generation "
                                << gen->generation_nowrap << ". me=" << self);
                segment = gen->segments[alloc_segment];
            }
            w_assert1(segment->owner == 0);
            w_assert1(segment->allocated_objects == 0);
            w_assert1(segment->total_objects > 0);

            // Occupied!
            DBGOUT1(<< name << ": Occupied a pre-allocated Segment " << alloc_segment
                            << " in generation " << gen->generation_nowrap << ". me=" << self << ".");
            segment->owner = self;
            mfence(); // let the world know (though the CAS above should be enough..)
            gc_pointer_raw ret;
            ret.components.status = 0;
            ret.components.generation = generation;
            ret.components.segment = alloc_segment;
            ret.components.offset = 0;
            return ret;
        } else {
            DBGOUT1(<< "Oops, CAS failed");
            continue;
        }
    }
}

template<class T>
inline bool GcPoolForest<T>::advance_generation(lsn_t low_water_mark, lsn_t now,
                                                size_t segment_count, gc_offset segment_size) {
    while (true) {
        mfence();
        if (low_water_mark != lsn_t::null && active_generations() >= desired_generations) {
            // try recycling oldest generation
            uint32_t old_tail_nowrap = tail_nowrap;
            retire_generations(low_water_mark, now);
            if (old_tail_nowrap < tail_nowrap) {
                return true; // it worked!
            }
        }
        if (tail_nowrap - head_nowrap >= GC_MAX_GENERATIONS - 1) {
            ERROUT(<< name << ": Too many generations!");
            return false; // too many generations
        }
        uint32_t new_generation_nowrap = tail_nowrap;
        uint32_t new_tail = new_generation_nowrap + 1;
        if (wrap(new_tail) == 0) {
            DBGOUT1(<< name << ": Generation wrapped!");
            ++new_tail; // skip generation==0
        }
        if (lintel::unsafe::atomic_compare_exchange_strong<uint32_t>(
                &tail_nowrap, &new_generation_nowrap, new_tail)) {
            // okay, let's create the generation
            gc_generation new_generation = wrap(new_generation_nowrap);
            generations[new_generation] = new GcGeneration<T>(new_generation_nowrap);
            epochs[new_generation] = now;
            generations[new_generation]->preallocate_segments(segment_count, segment_size);
            DBGOUT1(<< name << ": Generation " << new_generation_nowrap
                            << " created. epoch=" << now.data());
            curr_nowrap = new_generation_nowrap;
            mfence();
            return true;
        }
        // else retry
    }
}

template<class T>
inline bool GcGeneration<T>::preallocate_segments(size_t segment_count, gc_offset segment_size) {
    // this method is infrequently called by background thread,
    // so barriers/atomics and big allocations are fine.
    while (segment_count > 0) {
        w_assert1(!retire_suggested);
        if (total_segments >= GC_MAX_SEGMENTS - 1) {
            return false; // already full!
        }

        uint32_t new_segment = total_segments;
        if (lintel::unsafe::atomic_compare_exchange_strong<uint32_t>(
                &total_segments, &new_segment, new_segment + 1)) {
            // okay, we exclusively own this segment index
            GcSegment<T>* seg = new GcSegment<T>(segment_size);
            segments[new_segment] = seg;
            --segment_count;
            DBGOUT1(<<"Pre-allocated Segment " << new_segment << " in generation "
                            << generation_nowrap << ". segment size=" << segment_size << ".");
        }
        // else, someone else has just changed. retry
    }
    return true;
}

template<class T>
inline void GcPoolForest<T>::retire_generations(lsn_t low_water_mark, lsn_t recycle_now) {
    // this method is infrequently called by background thread,
    // so barriers/atomics and big deallocations are fine.
    w_assert1(tail_nowrap > 0);
    while (true) {
        mfence();
        uint32_t oldest_nowrap = head_nowrap;
        uint32_t next_oldest_nowrap = oldest_nowrap + 1;
        if (wrap(next_oldest_nowrap) == 0) {
            ++next_oldest_nowrap; // skip generation==0
        }
        const uint32_t MIN_HEALTHY_GENERATIONS = 2;
        if (tail_nowrap <= next_oldest_nowrap + MIN_HEALTHY_GENERATIONS) {
            return;
        }

        GcGeneration<T>* oldest = generations[wrap(oldest_nowrap)];
        oldest->retire_suggested = true; // this softly requests threads to move onto new gen
        mfence();
        if (low_water_mark >= epochs[wrap(next_oldest_nowrap)]) {
            // if even the next generation's beginning LSN is older than low water mark,
            // there is no chance that the oldest generation has anything used.
            // Let _me_ retire that.
            if (lintel::unsafe::atomic_compare_exchange_strong<uint32_t>(
                    &head_nowrap, &oldest_nowrap, next_oldest_nowrap)) {
                // okay, I'm exclusively retiring this generation.
                generations[wrap(oldest_nowrap)] = nullptr;
                epochs[wrap(oldest_nowrap)].set(0);

                DBGOUT1(<< name << ": Successfully retired generation " << oldest_nowrap);
                if (recycle_now != lsn_t::null && active_generations() <= desired_generations) {
                    DBGOUT1(<< "Now recycling it as new generation ...");
                    mfence();
                    uint32_t new_generation_nowrap = tail_nowrap;
                    uint32_t new_tail = new_generation_nowrap + 1;
                    if (wrap(new_tail) == 0) {
                        DBGOUT1(<< name << ": Generation wrapped!");
                        ++new_tail; // skip generation==0
                    }

                    if (lintel::unsafe::atomic_compare_exchange_strong<uint32_t>(
                            &tail_nowrap, &new_generation_nowrap, new_tail)) {
                        oldest->recycle(new_generation_nowrap);
                        generations[wrap(new_generation_nowrap)] = oldest;
                        epochs[wrap(new_generation_nowrap)].set(recycle_now.data());
                        curr_nowrap = new_generation_nowrap;
                        DBGOUT1(<< name << ": Successfully recycled as gen " << new_generation_nowrap);
                        mfence();
                        return;
                    } else {
                        DBGOUT1(<< name << ": Oops, others incremented generation. couldn't "
                                        << " reuse the retired generation");
                        delete oldest; // well, no other way.
                    }
                } else {
                    delete oldest;
                }
            } else {
                // someone else has retired it.
                DBGOUT1(<< name << ": Oops, CAS failed, someone has retired it?");
                continue;
            }
        } else {
            // then, we can't safely retire this generation. yet.
            return;
        }
    }
}

template<class T>
inline T* GcPointer<T>::dereference(GcPoolForest<T>& pool) const {
    T* pointer = pool.resolve_pointer(_raw);
    w_assert1(pointer != nullptr);
    return pointer;
}

#endif // __W_GC_POOL_FOREST_H