BlockDirectoryBits.h   [plain text]

/*
 * Copyright (C) 2019 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#pragma once

#include <array>
#include <wtf/FastBitVector.h>
#include <wtf/Vector.h>

namespace JSC {

#define FOR_EACH_BLOCK_DIRECTORY_BIT(macro) \
    macro(live, Live) /* The set of block indices that have actual blocks. */\
    macro(empty, Empty) /* The set of all blocks that have no live objects. */ \
    macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
    macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
    macro(destructible, Destructible) /* The set of all blocks that may have destructors to run. */\
    macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
    macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
    \
    /* These are computed during marking. */\
    macro(markingNotEmpty, MarkingNotEmpty) /* The set of all blocks that are not empty. */ \
    macro(markingRetired, MarkingRetired) /* The set of all blocks that are retired. */

// FIXME: We defined canAllocateButNotEmpty and empty to be exclusive:
//
//     canAllocateButNotEmpty & empty == 0
//
// Instead of calling it canAllocate and making it inclusive:
//
//     canAllocate & empty == empty
//
// The latter is probably better. I'll leave it to a future bug to fix that, since breathing on
// this code leads to regressions for days, and it's not clear that making this change would
// improve perf since it would not change the collector's behavior, and either way the directory
// has to look at both bitvectors.
// https://bugs.webkit.org/show_bug.cgi?id=162121

class BlockDirectoryBits {
    WTF_MAKE_FAST_ALLOCATED;
public:
    static constexpr unsigned bitsPerSegment = 32;
    static constexpr unsigned segmentShift = 5;
    static constexpr unsigned indexMask = (1U << segmentShift) - 1;
    static_assert((1 << segmentShift) == bitsPerSegment);

#define BLOCK_DIRECTORY_BIT_KIND_COUNT(lowerBitName, capitalBitName) + 1
    static constexpr unsigned numberOfBlockDirectoryBitKinds = 0 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_KIND_COUNT);
#undef BLOCK_DIRECTORY_BIT_KIND_COUNT

    enum class Kind {
#define BLOCK_DIRECTORY_BIT_KIND_DECLARATION(lowerBitName, capitalBitName) \
        capitalBitName,
        FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_KIND_DECLARATION)
#undef BLOCK_DIRECTORY_BIT_KIND_DECLARATION
    };

    class Segment {
    public:
        Segment() = default;
        std::array<uint32_t, numberOfBlockDirectoryBitKinds> m_data { };
    };

    template<Kind kind>
    class BlockDirectoryBitVectorWordView {
        WTF_MAKE_FAST_ALLOCATED;
    public:
        using ViewType = BlockDirectoryBitVectorWordView;

        BlockDirectoryBitVectorWordView() = default;

        BlockDirectoryBitVectorWordView(const Segment* segments, size_t numBits)
            : m_segments(segments)
            , m_numBits(numBits)
        {
        }

        size_t numBits() const
        {
            return m_numBits;
        }

        uint32_t word(size_t index) const
        {
            ASSERT(index < WTF::fastBitVectorArrayLength(numBits()));
            return m_segments[index].m_data[static_cast<unsigned>(kind)];
        }

        uint32_t& word(size_t index)
        {
            ASSERT(index < WTF::fastBitVectorArrayLength(numBits()));
            return const_cast<Segment*>(m_segments)[index].m_data[static_cast<unsigned>(kind)];
        }

        void clearAll()
        {
            for (size_t index = 0; index < WTF::fastBitVectorArrayLength(numBits()); ++index)
                const_cast<Segment*>(m_segments)[index].m_data[static_cast<unsigned>(kind)] = 0;
        }

        BlockDirectoryBitVectorWordView view() const { return *this; }

    private:
        const Segment* m_segments { nullptr };
        size_t m_numBits { 0 };
    };

    template<Kind kind>
    using BlockDirectoryBitVectorView = WTF::FastBitVectorImpl<BlockDirectoryBitVectorWordView<kind>>;

    template<Kind kind>
    class BlockDirectoryBitVectorRef final : public BlockDirectoryBitVectorView<kind> {
    public:
        using Base = BlockDirectoryBitVectorView<kind>;

        explicit BlockDirectoryBitVectorRef(BlockDirectoryBitVectorWordView<kind> view)
            : Base(view)
        {
        }

        template<typename OtherWords>
        BlockDirectoryBitVectorRef& operator=(const WTF::FastBitVectorImpl<OtherWords>& other)
        {
            ASSERT(Base::numBits() == other.numBits());
            for (unsigned i = Base::arrayLength(); i--;)
                Base::unsafeWords().word(i) = other.unsafeWords().word(i);
            return *this;
        }

        template<typename OtherWords>
        BlockDirectoryBitVectorRef& operator|=(const WTF::FastBitVectorImpl<OtherWords>& other)
        {
            ASSERT(Base::numBits() == other.numBits());
            for (unsigned i = Base::arrayLength(); i--;)
                Base::unsafeWords().word(i) |= other.unsafeWords().word(i);
            return *this;
        }

        void clearAll()
        {
            Base::unsafeWords().clearAll();
        }

        WTF::FastBitReference at(size_t index)
        {
            ASSERT(index < Base::numBits());
            return WTF::FastBitReference(&Base::unsafeWords().word(index >> 5), 1 << (index & 31));
        }

        WTF::FastBitReference operator[](size_t index)
        {
            return at(index);
        }
    };

#define BLOCK_DIRECTORY_BIT_ACCESSORS(lowerBitName, capitalBitName)     \
    bool is ## capitalBitName(size_t index) const \
    { \
        return lowerBitName()[index]; \
    } \
    void setIs ## capitalBitName(size_t index, bool value) \
    { \
        lowerBitName()[index] = value; \
    } \
    BlockDirectoryBitVectorView<Kind::capitalBitName> lowerBitName() const \
    { \
        return BlockDirectoryBitVectorView<Kind::capitalBitName>(BlockDirectoryBitVectorWordView<Kind::capitalBitName>(m_segments.data(), m_numBits)); \
    } \
    BlockDirectoryBitVectorRef<Kind::capitalBitName> lowerBitName() \
    { \
        return BlockDirectoryBitVectorRef<Kind::capitalBitName>(BlockDirectoryBitVectorWordView<Kind::capitalBitName>(m_segments.data(), m_numBits)); \
    }
    FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_ACCESSORS)
#undef BLOCK_DIRECTORY_BIT_ACCESSORS

    unsigned numBits() const { return m_numBits; }

    void resize(unsigned numBits)
    {
        unsigned oldNumBits = m_numBits;
        m_numBits = numBits;
        m_segments.resize(WTF::fastBitVectorArrayLength(numBits));
        unsigned usedBitsInLastSegment = numBits & indexMask; // This is 0 if all bits are used.
        if (numBits < oldNumBits && usedBitsInLastSegment) {
            // Clear the last segment.
            ASSERT(usedBitsInLastSegment < bitsPerSegment);
            auto& segment = m_segments.last();
            uint32_t mask = (1U << usedBitsInLastSegment) - 1;
            for (unsigned index = 0; index < numberOfBlockDirectoryBitKinds; ++index)
                segment.m_data[index] &= mask;
        }
    }

    template<typename Func>
    void forEachSegment(const Func& func)
    {
        unsigned index = 0;
        for (auto& segment : m_segments)
            func(index++, segment);
    }

private:
    Vector<Segment> m_segments;
    unsigned m_numBits { 0 };
};

} // namespace JSC