/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef gc_StoreBuffer_h
#define gc_StoreBuffer_h

#ifdef JSGC_GENERATIONAL

#ifndef JSGC_USE_EXACT_ROOTING
# error "Generational GC requires exact rooting."
#endif

#include "jsgc.h"
#include "jsalloc.h"
#include "jsobj.h"

namespace js {
namespace gc {

class AccumulateEdgesTracer;

/*
 * BufferableRef represents an abstract reference for use in the generational
 * GC's remembered set. Entries in the store buffer that cannot be represented
 * with the simple pointer-to-a-pointer scheme must derive from this class and
 * use the generic store buffer interface.
 */
class BufferableRef
{
  public:
    virtual void mark(JSTracer *trc) = 0;
};

/*
 * HashKeyRef represents a reference to a HashTable key. Manual HashTable
 * barriers should should instantiate this template with their own table/key
 * type to insert into the generic buffer with putGeneric.
 */
template <typename Map, typename Key>
class HashKeyRef : public BufferableRef
{
    Map *map;
    Key key;

    typedef typename Map::Entry::ValueType ValueType;
    typedef typename Map::Ptr Ptr;

  public:
    HashKeyRef(Map *m, const Key &k) : map(m), key(k) {}

    void mark(JSTracer *trc) {
        Key prior = key;
        typename Map::Ptr p = map->lookup(key);
        if (!p)
            return;
        ValueType value = p->value;
        JS_SET_TRACING_LOCATION(trc, (void*)&p->key);
        Mark(trc, &key, "HashKeyRef");
        if (prior != key) {
            map->remove(prior);
            map->put(key, value);
        }
    }
};

typedef HashSet<void *, PointerHasher<void *, 3>, SystemAllocPolicy> EdgeSet;

/*
 * The StoreBuffer observes all writes that occur in the system and performs
 * efficient filtering of them to derive a remembered set for nursery GC.
 */
class StoreBuffer
{
    /*
     * This buffer holds only a single type of edge. Using this buffer is more
     * efficient than the generic buffer when many writes will be to the same
     * type of edge: e.g. Value or Cell*.
     */
    template<typename T>
    class MonoTypeBuffer
    {
        friend class StoreBuffer;

        StoreBuffer *owner;

        T *base;      /* Pointer to the start of the buffer. */
        T *pos;       /* Pointer to the current insertion position. */
        T *top;       /* Pointer to one element after the end. */

        /*
         * If the buffer's insertion position goes over the high-water-mark,
         * we trigger a minor GC at the next operation callback.
         */
        T *highwater;

        /*
         * This set stores duplicates found when compacting. We create the set
         * here, rather than local to the algorithm to avoid malloc overhead in
         * the common case.
         */
        EdgeSet duplicates;

        MonoTypeBuffer(StoreBuffer *owner)
          : owner(owner), base(NULL), pos(NULL), top(NULL)
        {
            duplicates.init();
        }

        MonoTypeBuffer &operator=(const MonoTypeBuffer& other) MOZ_DELETE;

        bool enable(uint8_t *region, size_t len);
        void disable();
        void clear();

        bool isEmpty() const { return pos == base; }
        bool isFull() const { JS_ASSERT(pos <= top); return pos == top; }
        bool isAboutToOverflow() const { return pos >= highwater; }

        /* Compaction algorithms. */
        void compactNotInSet(const Nursery &nursery);
        void compactRemoveDuplicates();

        /*
         * Attempts to reduce the usage of the buffer by removing unnecessary
         * entries.
         */
        virtual void compact();

        /* Add one item to the buffer. */
        void put(const T &v) {
            JS_ASSERT(!owner->inParallelSection());

            /* Check if we have been enabled. */
            if (!pos)
                return;

            /*
             * Note: it is sometimes valid for a put to happen in the middle of a GC,
             * e.g. a rekey of a Relocatable may end up here. In general, we do not
             * care about these new entries or any overflows they cause.
             */
            *pos++ = v;
            if (isAboutToOverflow()) {
                owner->setAboutToOverflow();
                if (isFull()) {
                    compact();
                    if (isFull()) {
                        owner->setOverflowed();
                        clear();
                    }
                }
            }
        }

        /* Mark the source of all edges in the store buffer. */
        void mark(JSTracer *trc);
    };

    /*
     * Overrides the MonoTypeBuffer to support pointers that may be moved in
     * memory outside of the GC's control.
     */
    template <typename T>
    class RelocatableMonoTypeBuffer : public MonoTypeBuffer<T>
    {
        friend class StoreBuffer;

        RelocatableMonoTypeBuffer(StoreBuffer *owner)
          : MonoTypeBuffer<T>(owner)
        {}

        /* Override compaction to filter out removed items. */
        void compactMoved();
        virtual void compact();

        /* Record a removal from the buffer. */
        void unput(const T &v) {
            JS_ASSERT(!this->owner->inParallelSection());
            MonoTypeBuffer<T>::put(v.tagged());
        }
    };

    class GenericBuffer
    {
        friend class StoreBuffer;

        StoreBuffer *owner;

        uint8_t *base; /* Pointer to start of buffer. */
        uint8_t *pos;  /* Pointer to current buffer position. */
        uint8_t *top;  /* Pointer to one past the last entry. */

        GenericBuffer(StoreBuffer *owner)
          : owner(owner)
        {}

        GenericBuffer &operator=(const GenericBuffer& other) MOZ_DELETE;

        bool enable(uint8_t *region, size_t len);
        void disable();
        void clear();

        /* Mark all generic edges. */
        void mark(JSTracer *trc);

        template <typename T>
        void put(const T &t) {
            JS_ASSERT(!owner->inParallelSection());

            /* Check if we have been enabled. */
            if (!pos)
                return;

            /* Check for overflow. */
            if (top - pos < (unsigned)(sizeof(unsigned) + sizeof(T))) {
                owner->setOverflowed();
                return;
            }

            *((unsigned *)pos) = sizeof(T);
            pos += sizeof(unsigned);

            T *p = (T *)pos;
            new (p) T(t);
            pos += sizeof(T);
        }
    };

    class CellPtrEdge
    {
        friend class StoreBuffer;
        friend class StoreBuffer::MonoTypeBuffer<CellPtrEdge>;
        friend class StoreBuffer::RelocatableMonoTypeBuffer<CellPtrEdge>;

        Cell **edge;

        CellPtrEdge(Cell **v) : edge(v) {}
        bool operator==(const CellPtrEdge &other) const { return edge == other.edge; }
        bool operator!=(const CellPtrEdge &other) const { return edge != other.edge; }

        void *location() const { return (void *)edge; }

        bool inRememberedSet(const Nursery &nursery) const {
            return !nursery.isInside(edge) && nursery.isInside(*edge);
        }

        bool isNullEdge() const {
            return !*edge;
        }

        void mark(JSTracer *trc);

        CellPtrEdge tagged() const { return CellPtrEdge((Cell **)(uintptr_t(edge) | 1)); }
        CellPtrEdge untagged() const { return CellPtrEdge((Cell **)(uintptr_t(edge) & ~1)); }
        bool isTagged() const { return bool(uintptr_t(edge) & 1); }
    };

    class ValueEdge
    {
        friend class StoreBuffer;
        friend class StoreBuffer::MonoTypeBuffer<ValueEdge>;
        friend class StoreBuffer::RelocatableMonoTypeBuffer<ValueEdge>;

        Value *edge;

        ValueEdge(Value *v) : edge(v) {}
        bool operator==(const ValueEdge &other) const { return edge == other.edge; }
        bool operator!=(const ValueEdge &other) const { return edge != other.edge; }

        void *deref() const { return edge->isGCThing() ? edge->toGCThing() : NULL; }
        void *location() const { return (void *)edge; }

        bool inRememberedSet(const Nursery &nursery) const {
            return !nursery.isInside(edge) && nursery.isInside(deref());
        }

        bool isNullEdge() const {
            return !deref();
        }

        void mark(JSTracer *trc);

        ValueEdge tagged() const { return ValueEdge((Value *)(uintptr_t(edge) | 1)); }
        ValueEdge untagged() const { return ValueEdge((Value *)(uintptr_t(edge) & ~1)); }
        bool isTagged() const { return bool(uintptr_t(edge) & 1); }
    };

    struct SlotEdge
    {
        friend class StoreBuffer;
        friend class StoreBuffer::MonoTypeBuffer<SlotEdge>;

        JSObject *object;
        uint32_t offset;
        HeapSlot::Kind kind;

        SlotEdge(JSObject *object, HeapSlot::Kind kind, uint32_t offset)
          : object(object), offset(offset), kind(kind)
        {}

        bool operator==(const SlotEdge &other) const {
            return object == other.object && offset == other.offset && kind == other.kind;
        }

        bool operator!=(const SlotEdge &other) const {
            return object != other.object || offset != other.offset || kind != other.kind;
        }

        JS_ALWAYS_INLINE HeapSlot *slotLocation() const;

        JS_ALWAYS_INLINE void *deref() const;

        JS_ALWAYS_INLINE void *location() const;

        JS_ALWAYS_INLINE bool inRememberedSet(const Nursery &nursery) const;

        JS_ALWAYS_INLINE bool isNullEdge() const;

        void mark(JSTracer *trc);
    };

    class WholeCellEdges
    {
        friend class StoreBuffer;
        friend class StoreBuffer::MonoTypeBuffer<WholeCellEdges>;

        Cell *tenured;

        WholeCellEdges(Cell *cell) : tenured(cell) {
            JS_ASSERT(tenured->isTenured());
        }

        bool operator==(const WholeCellEdges &other) const { return tenured == other.tenured; }
        bool operator!=(const WholeCellEdges &other) const { return tenured != other.tenured; }

        bool inRememberedSet(const Nursery &nursery) const { return true; }

        /* This is used by RemoveDuplicates as a unique pointer to this Edge. */
        void *location() const { return (void *)tenured; }

        bool isNullEdge() const { return false; }

        void mark(JSTracer *trc);
    };

    MonoTypeBuffer<ValueEdge> bufferVal;
    MonoTypeBuffer<CellPtrEdge> bufferCell;
    MonoTypeBuffer<SlotEdge> bufferSlot;
    MonoTypeBuffer<WholeCellEdges> bufferWholeCell;
    RelocatableMonoTypeBuffer<ValueEdge> bufferRelocVal;
    RelocatableMonoTypeBuffer<CellPtrEdge> bufferRelocCell;
    GenericBuffer bufferGeneric;

    JSRuntime *runtime;

    void *buffer;

    bool aboutToOverflow;
    bool overflowed;
    bool enabled;

    /* TODO: profile to find the ideal size for these. */
    static const size_t ValueBufferSize = 1 * 1024 * sizeof(ValueEdge);
    static const size_t CellBufferSize = 2 * 1024 * sizeof(CellPtrEdge);
    static const size_t SlotBufferSize = 2 * 1024 * sizeof(SlotEdge);
    static const size_t WholeCellBufferSize = 2 * 1024 * sizeof(WholeCellEdges);
    static const size_t RelocValueBufferSize = 1 * 1024 * sizeof(ValueEdge);
    static const size_t RelocCellBufferSize = 1 * 1024 * sizeof(CellPtrEdge);
    static const size_t GenericBufferSize = 1 * 1024 * sizeof(int);
    static const size_t TotalSize = ValueBufferSize + CellBufferSize +
                                    SlotBufferSize + WholeCellBufferSize +
                                    RelocValueBufferSize + RelocCellBufferSize +
                                    GenericBufferSize;

  public:
    explicit StoreBuffer(JSRuntime *rt)
      : bufferVal(this), bufferCell(this), bufferSlot(this), bufferWholeCell(this),
        bufferRelocVal(this), bufferRelocCell(this), bufferGeneric(this),
        runtime(rt), buffer(NULL), aboutToOverflow(false), overflowed(false),
        enabled(false)
    {}

    bool enable();
    void disable();
    bool isEnabled() { return enabled; }

    bool clear();

    /* Get the overflowed status. */
    bool isAboutToOverflow() const { return aboutToOverflow; }
    bool hasOverflowed() const { return overflowed; }

    /* Insert a single edge into the buffer/remembered set. */
    void putValue(Value *v) {
        bufferVal.put(v);
    }
    void putCell(Cell **o) {
        bufferCell.put(o);
    }
    void putSlot(JSObject *obj, HeapSlot::Kind kind, uint32_t slot) {
        bufferSlot.put(SlotEdge(obj, kind, slot));
    }
    void putWholeCell(Cell *cell) {
        bufferWholeCell.put(WholeCellEdges(cell));
    }

    /* Insert or update a single edge in the Relocatable buffer. */
    void putRelocatableValue(Value *v) {
        bufferRelocVal.put(v);
    }
    void putRelocatableCell(Cell **c) {
        bufferRelocCell.put(c);
    }
    void removeRelocatableValue(Value *v) {
        bufferRelocVal.unput(v);
    }
    void removeRelocatableCell(Cell **c) {
        bufferRelocCell.unput(c);
    }

    /* Insert an entry into the generic buffer. */
    template <typename T>
    void putGeneric(const T &t) {
        bufferGeneric.put(t);
    }

    /* Mark the source of all edges in the store buffer. */
    void mark(JSTracer *trc);

    /* We cannot call InParallelSection directly because of a circular dependency. */
    bool inParallelSection() const;

    /* For use by our owned buffers and for testing. */
    void setAboutToOverflow();
    void setOverflowed();
};

} /* namespace gc */
} /* namespace js */

#endif /* JSGC_GENERATIONAL */

#endif /* gc_StoreBuffer_h */