Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #include "gc/AtomMarking-inl.h"
8 :
9 : #include "gc/PublicIterators.h"
10 : #include "vm/Realm.h"
11 :
12 : #include "gc/GC-inl.h"
13 : #include "gc/Heap-inl.h"
14 :
15 : namespace js {
16 : namespace gc {
17 :
18 : // Atom Marking Overview
19 : //
20 : // Things in the atoms zone (which includes atomized strings and other things,
21 : // all of which we will refer to as 'atoms' here) may be pointed to freely by
22 : // things in other zones. To avoid the need to perform garbage collections of
23 : // the entire runtime to collect atoms, we compute a separate atom mark bitmap
24 : // for each zone that is always an overapproximation of the atoms that zone is
25 : // using. When an atom is not in the mark bitmap for any zone, it can be
26 : // destroyed.
27 : //
28 : // To minimize interference with the rest of the GC, atom marking and sweeping
29 : // is done by manipulating the mark bitmaps in the chunks used for the atoms.
30 : // When the atoms zone is being collected, the mark bitmaps for the chunk(s)
31 : // used by the atoms are updated normally during marking. After marking
32 : // finishes, the chunk mark bitmaps are translated to a more efficient atom mark
33 : // bitmap (see below) that is stored on the zones which the GC collected
34 : // (computeBitmapFromChunkMarkBits). Before sweeping begins, the chunk mark
35 : // bitmaps are updated with any atoms that might be referenced by zones which
36 : // weren't collected (markAtomsUsedByUncollectedZones). The GC sweeping will
37 : // then release all atoms which are not marked by any zone.
38 : //
39 : // The representation of atom mark bitmaps is as follows:
40 : //
41 : // Each arena in the atoms zone has an atomBitmapStart() value indicating the
42 : // word index into the bitmap of the first thing in the arena. Each arena uses
43 : // ArenaBitmapWords of data to store its bitmap, which uses the same
44 : // representation as chunk mark bitmaps: one bit is allocated per Cell, with
45 : // bits for space between things being unused when things are larger than a
46 : // single Cell.
47 :
48 : void
49 0 : AtomMarkingRuntime::registerArena(Arena* arena, const AutoLockGC& lock)
50 : {
51 0 : MOZ_ASSERT(arena->getThingSize() != 0);
52 0 : MOZ_ASSERT(arena->getThingSize() % CellAlignBytes == 0);
53 0 : MOZ_ASSERT(arena->zone->isAtomsZone());
54 :
55 : // We need to find a range of bits from the atoms bitmap for this arena.
56 :
57 : // Look for a free range of bits compatible with this arena.
58 0 : if (freeArenaIndexes.ref().length()) {
59 0 : arena->atomBitmapStart() = freeArenaIndexes.ref().popCopy();
60 0 : return;
61 : }
62 :
63 : // Allocate a range of bits from the end for this arena.
64 0 : arena->atomBitmapStart() = allocatedWords;
65 0 : allocatedWords += ArenaBitmapWords;
66 : }
67 :
68 : void
69 0 : AtomMarkingRuntime::unregisterArena(Arena* arena, const AutoLockGC& lock)
70 : {
71 0 : MOZ_ASSERT(arena->zone->isAtomsZone());
72 :
73 : // Leak these atom bits if we run out of memory.
74 0 : mozilla::Unused << freeArenaIndexes.ref().emplaceBack(arena->atomBitmapStart());
75 0 : }
76 :
77 : bool
78 0 : AtomMarkingRuntime::computeBitmapFromChunkMarkBits(JSRuntime* runtime, DenseBitmap& bitmap)
79 : {
80 0 : MOZ_ASSERT(CurrentThreadIsPerformingGC());
81 0 : MOZ_ASSERT(!runtime->hasHelperThreadZones());
82 :
83 0 : if (!bitmap.ensureSpace(allocatedWords))
84 : return false;
85 :
86 0 : Zone* atomsZone = runtime->unsafeAtomsZone();
87 0 : for (auto thingKind : AllAllocKinds()) {
88 0 : for (ArenaIter aiter(atomsZone, thingKind); !aiter.done(); aiter.next()) {
89 0 : Arena* arena = aiter.get();
90 0 : uintptr_t* chunkWords = arena->chunk()->bitmap.arenaBits(arena);
91 0 : bitmap.copyBitsFrom(arena->atomBitmapStart(), ArenaBitmapWords, chunkWords);
92 : }
93 : }
94 :
95 : return true;
96 : }
97 :
98 : void
99 0 : AtomMarkingRuntime::refineZoneBitmapForCollectedZone(Zone* zone, const DenseBitmap& bitmap)
100 : {
101 0 : MOZ_ASSERT(zone->isCollectingFromAnyThread());
102 :
103 0 : if (zone->isAtomsZone())
104 : return;
105 :
106 : // Take the bitwise and between the two mark bitmaps to get the best new
107 : // overapproximation we can. |bitmap| might include bits that are not in
108 : // the zone's mark bitmap, if additional zones were collected by the GC.
109 0 : zone->markedAtoms().bitwiseAndWith(bitmap);
110 : }
111 :
112 : // Set any bits in the chunk mark bitmaps for atoms which are marked in bitmap.
113 : template <typename Bitmap>
114 : static void
115 0 : BitwiseOrIntoChunkMarkBits(JSRuntime* runtime, Bitmap& bitmap)
116 : {
117 : // Make sure that by copying the mark bits for one arena in word sizes we
118 : // do not affect the mark bits for other arenas.
119 : static_assert(ArenaBitmapBits == ArenaBitmapWords * JS_BITS_PER_WORD,
120 : "ArenaBitmapWords must evenly divide ArenaBitmapBits");
121 :
122 0 : Zone* atomsZone = runtime->unsafeAtomsZone();
123 0 : for (auto thingKind : AllAllocKinds()) {
124 0 : for (ArenaIter aiter(atomsZone, thingKind); !aiter.done(); aiter.next()) {
125 0 : Arena* arena = aiter.get();
126 0 : uintptr_t* chunkWords = arena->chunk()->bitmap.arenaBits(arena);
127 0 : bitmap.bitwiseOrRangeInto(arena->atomBitmapStart(), ArenaBitmapWords, chunkWords);
128 : }
129 : }
130 0 : }
131 :
132 : void
133 0 : AtomMarkingRuntime::markAtomsUsedByUncollectedZones(JSRuntime* runtime)
134 : {
135 0 : MOZ_ASSERT(CurrentThreadIsPerformingGC());
136 0 : MOZ_ASSERT(!runtime->hasHelperThreadZones());
137 :
138 : // Try to compute a simple union of the zone atom bitmaps before updating
139 : // the chunk mark bitmaps. If this allocation fails then fall back to
140 : // updating the chunk mark bitmaps separately for each zone.
141 0 : DenseBitmap markedUnion;
142 0 : if (markedUnion.ensureSpace(allocatedWords)) {
143 0 : for (ZonesIter zone(runtime, SkipAtoms); !zone.done(); zone.next()) {
144 : // We only need to update the chunk mark bits for zones which were
145 : // not collected in the current GC. Atoms which are referenced by
146 : // collected zones have already been marked.
147 0 : if (!zone->isCollectingFromAnyThread())
148 0 : zone->markedAtoms().bitwiseOrInto(markedUnion);
149 : }
150 0 : BitwiseOrIntoChunkMarkBits(runtime, markedUnion);
151 : } else {
152 0 : for (ZonesIter zone(runtime, SkipAtoms); !zone.done(); zone.next()) {
153 0 : if (!zone->isCollectingFromAnyThread())
154 0 : BitwiseOrIntoChunkMarkBits(runtime, zone->markedAtoms());
155 : }
156 : }
157 0 : }
158 :
159 : template <typename T>
160 : void
161 0 : AtomMarkingRuntime::markAtom(JSContext* cx, T* thing)
162 : {
163 134875 : return inlinedMarkAtom(cx, thing);
164 : }
165 :
166 : template void AtomMarkingRuntime::markAtom(JSContext* cx, JSAtom* thing);
167 : template void AtomMarkingRuntime::markAtom(JSContext* cx, JS::Symbol* thing);
168 :
169 : void
170 0 : AtomMarkingRuntime::markId(JSContext* cx, jsid id)
171 : {
172 0 : if (JSID_IS_ATOM(id)) {
173 30742 : markAtom(cx, JSID_TO_ATOM(id));
174 0 : return;
175 : }
176 0 : if (JSID_IS_SYMBOL(id)) {
177 225 : markAtom(cx, JSID_TO_SYMBOL(id));
178 225 : return;
179 : }
180 : MOZ_ASSERT(!JSID_IS_GCTHING(id));
181 : }
182 :
183 : void
184 0 : AtomMarkingRuntime::markAtomValue(JSContext* cx, const Value& value)
185 : {
186 0 : if (value.isString()) {
187 2220 : if (value.toString()->isAtom())
188 1110 : markAtom(cx, &value.toString()->asAtom());
189 : return;
190 : }
191 0 : if (value.isSymbol()) {
192 5 : markAtom(cx, value.toSymbol());
193 0 : return;
194 : }
195 896 : MOZ_ASSERT_IF(value.isGCThing(),
196 : value.isObject() ||
197 : value.isPrivateGCThing() ||
198 : IF_BIGINT(value.isBigInt(), false));
199 : }
200 :
201 : void
202 0 : AtomMarkingRuntime::adoptMarkedAtoms(Zone* target, Zone* source)
203 : {
204 0 : MOZ_ASSERT(CurrentThreadCanAccessZone(source));
205 0 : MOZ_ASSERT(CurrentThreadCanAccessZone(target));
206 10 : target->markedAtoms().bitwiseOrWith(source->markedAtoms());
207 5 : }
208 :
209 : #ifdef DEBUG
210 : template <typename T>
211 : bool
212 655834 : AtomMarkingRuntime::atomIsMarked(Zone* zone, T* thing)
213 : {
214 : static_assert(mozilla::IsSame<T, JSAtom>::value ||
215 : mozilla::IsSame<T, JS::Symbol>::value,
216 : "Should only be called with JSAtom* or JS::Symbol* argument");
217 :
218 0 : MOZ_ASSERT(thing);
219 655834 : MOZ_ASSERT(!IsInsideNursery(thing));
220 0 : MOZ_ASSERT(thing->zoneFromAnyThread()->isAtomsZone());
221 :
222 1311664 : if (!zone->runtimeFromAnyThread()->permanentAtoms)
223 : return true;
224 :
225 1276658 : if (ThingIsPermanent(thing))
226 : return true;
227 :
228 359311 : size_t bit = GetAtomBit(&thing->asTenured());
229 359313 : return zone->markedAtoms().getBit(bit);
230 : }
231 :
232 : template bool AtomMarkingRuntime::atomIsMarked(Zone* zone, JSAtom* thing);
233 : template bool AtomMarkingRuntime::atomIsMarked(Zone* zone, JS::Symbol* thing);
234 :
235 : template<>
236 : bool
237 0 : AtomMarkingRuntime::atomIsMarked(Zone* zone, TenuredCell* thing)
238 : {
239 0 : if (!thing)
240 : return true;
241 :
242 0 : if (thing->is<JSString>()) {
243 0 : JSString* str = thing->as<JSString>();
244 0 : if (!str->isAtom())
245 : return true;
246 0 : return atomIsMarked(zone, &str->asAtom());
247 : }
248 :
249 0 : if (thing->is<JS::Symbol>())
250 0 : return atomIsMarked(zone, thing->as<JS::Symbol>());
251 :
252 : return true;
253 : }
254 :
255 : bool
256 0 : AtomMarkingRuntime::idIsMarked(Zone* zone, jsid id)
257 : {
258 73344 : if (JSID_IS_ATOM(id))
259 0 : return atomIsMarked(zone, JSID_TO_ATOM(id));
260 :
261 992 : if (JSID_IS_SYMBOL(id))
262 963 : return atomIsMarked(zone, JSID_TO_SYMBOL(id));
263 :
264 : MOZ_ASSERT(!JSID_IS_GCTHING(id));
265 : return true;
266 : }
267 :
268 : bool
269 0 : AtomMarkingRuntime::valueIsMarked(Zone* zone, const Value& value)
270 : {
271 0 : if (value.isString()) {
272 157400 : if (value.toString()->isAtom())
273 55786 : return atomIsMarked(zone, &value.toString()->asAtom());
274 : return true;
275 : }
276 :
277 342839 : if (value.isSymbol())
278 0 : return atomIsMarked(zone, value.toSymbol());
279 :
280 348054 : MOZ_ASSERT_IF(value.isGCThing(),
281 : value.isObject() ||
282 : value.isPrivateGCThing() ||
283 : IF_BIGINT(value.isBigInt(), false));
284 : return true;
285 : }
286 :
287 : #endif // DEBUG
288 :
289 : } // namespace gc
290 :
291 : #ifdef DEBUG
292 :
293 : bool
294 0 : AtomIsMarked(Zone* zone, JSAtom* atom)
295 : {
296 355201 : return zone->runtimeFromAnyThread()->gc.atomMarking.atomIsMarked(zone, atom);
297 : }
298 :
299 : bool
300 0 : AtomIsMarked(Zone* zone, jsid id)
301 : {
302 73344 : return zone->runtimeFromAnyThread()->gc.atomMarking.idIsMarked(zone, id);
303 : }
304 :
305 : bool
306 0 : AtomIsMarked(Zone* zone, const Value& value)
307 : {
308 : return zone->runtimeFromAnyThread()->gc.atomMarking.valueIsMarked(zone, value);
309 : }
310 :
311 : #endif // DEBUG
312 :
313 : } // namespace js
|
