blob: a39b143f773016a3b5daec835f331937ed83e193 [file] [log] [blame]
/*
* 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