1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include "MarkedBlock.h"
29#include <wtf/Bitmap.h>
30#include <wtf/ConcurrentVector.h>
31#include <wtf/FastBitVector.h>
32#include <wtf/SentinelLinkedList.h>
33#include <wtf/SharedTask.h>
34
35namespace JSC {
36
37class HeapCell;
38class IsoSubspace;
39
40// Create a set of cells that are in an IsoSubspace. This allows concurrent O(1) set insertion and
41// removal. Each such set should be thought of as a 0.8% increase in object size for objects in that
42// IsoSubspace (it's like adding 1 bit every 16 bytes, or 1 bit every 128 bits).
43class IsoCellSet : public BasicRawSentinelNode<IsoCellSet> {
44public:
45 IsoCellSet(IsoSubspace& subspace);
46 ~IsoCellSet();
47
48 bool add(HeapCell* cell); // Returns true if the cell was newly added.
49
50 bool remove(HeapCell* cell); // Returns true if the cell was previously present and got removed.
51
52 bool contains(HeapCell* cell) const;
53
54 JS_EXPORT_PRIVATE Ref<SharedTask<MarkedBlock::Handle*()>> parallelNotEmptyMarkedBlockSource();
55
56 // This will have to do a combined search over whatever Subspace::forEachMarkedCell uses and
57 // our m_blocksWithBits.
58 template<typename Func>
59 void forEachMarkedCell(const Func&);
60
61 template<typename Func>
62 Ref<SharedTask<void(SlotVisitor&)>> forEachMarkedCellInParallel(const Func&);
63
64 template<typename Func>
65 void forEachLiveCell(const Func&);
66
67private:
68 friend class IsoSubspace;
69
70 Bitmap<MarkedBlock::atomsPerBlock>* addSlow(size_t blockIndex);
71
72 void didResizeBits(size_t newSize);
73 void didRemoveBlock(size_t blockIndex);
74 void sweepToFreeList(MarkedBlock::Handle*);
75
76 IsoSubspace& m_subspace;
77
78 // Idea: sweeping to free-list clears bits for those cells that were free-listed. The first time
79 // we add a cell in a block, that block gets a free-list. Unless we do something that obviously
80 // clears all bits for a block, we keep it set in blocksWithBits.
81
82 FastBitVector m_blocksWithBits;
83 ConcurrentVector<std::unique_ptr<Bitmap<MarkedBlock::atomsPerBlock>>> m_bits;
84};
85
86} // namespace JSC
87
88