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 "jscompartment.h"
10 :
11 : #include "jsgcinlines.h"
12 : #include "gc/Heap-inl.h"
13 :
14 : namespace js {
15 : namespace gc {
16 :
17 : // Atom Marking Overview
18 : //
19 : // Things in the atoms zone (which includes atomized strings and other things,
20 : // all of which we will refer to as 'atoms' here) may be pointed to freely by
21 : // things in other zones. To avoid the need to perform garbage collections of
22 : // the entire runtime to collect atoms, we compute a separate atom mark bitmap
23 : // for each zone that is always an overapproximation of the atoms that zone is
24 : // using. When an atom is not in the mark bitmap for any zone, it can be
25 : // destroyed.
26 : //
27 : // To minimize interference with the rest of the GC, atom marking and sweeping
28 : // is done by manipulating the mark bitmaps in the chunks used for the atoms.
29 : // When the atoms zone is being collected, the mark bitmaps for the chunk(s)
30 : // used by the atoms are updated normally during marking. After marking
31 : // finishes, the chunk mark bitmaps are translated to a more efficient atom
32 : // mark bitmap (see below) that is stored on the zones which the GC collected
33 : // (computeBitmapFromChunkMarkBits). Before sweeping begins, the chunk mark
34 : // bitmaps are updated with any atoms that might be referenced by zones which
35 : // weren't collected (updateChunkMarkBits). The GC sweeping will then release
36 : // all atoms which are not marked by any zone.
37 : //
38 : // The representation of atom mark bitmaps is as follows:
39 : //
40 : // Each arena in the atoms zone has an atomBitmapStart() value indicating the
41 : // word index into the bitmap of the first thing in the arena. Each arena uses
42 : // ArenaBitmapWords of data to store its bitmap, which uses the same
43 : // representation as chunk mark bitmaps: one bit is allocated per Cell, with
44 : // bits for space between things being unused when things are larger than a
45 : // single Cell.
46 :
47 : void
48 654 : AtomMarkingRuntime::registerArena(Arena* arena)
49 : {
50 654 : MOZ_ASSERT(arena->getThingSize() != 0);
51 654 : MOZ_ASSERT(arena->getThingSize() % CellAlignBytes == 0);
52 654 : MOZ_ASSERT(arena->zone->isAtomsZone());
53 654 : MOZ_ASSERT(arena->zone->runtimeFromAnyThread()->currentThreadHasExclusiveAccess());
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 654 : 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 654 : arena->atomBitmapStart() = allocatedWords;
65 654 : allocatedWords += ArenaBitmapWords;
66 : }
67 :
68 : void
69 0 : AtomMarkingRuntime::unregisterArena(Arena* arena)
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(runtime->currentThreadHasExclusiveAccess());
81 :
82 0 : if (!bitmap.ensureSpace(allocatedWords))
83 0 : return false;
84 :
85 0 : Zone* atomsZone = runtime->unsafeAtomsCompartment()->zone();
86 0 : for (auto thingKind : AllAllocKinds()) {
87 0 : for (ArenaIter aiter(atomsZone, thingKind); !aiter.done(); aiter.next()) {
88 0 : Arena* arena = aiter.get();
89 0 : uintptr_t* chunkWords = arena->chunk()->bitmap.arenaBits(arena);
90 0 : bitmap.copyBitsFrom(arena->atomBitmapStart(), ArenaBitmapWords, chunkWords);
91 : }
92 : }
93 :
94 0 : return true;
95 : }
96 :
97 : void
98 0 : AtomMarkingRuntime::updateZoneBitmap(Zone* zone, const DenseBitmap& bitmap)
99 : {
100 0 : if (zone->isAtomsZone())
101 0 : return;
102 :
103 : // Take the bitwise and between the two mark bitmaps to get the best new
104 : // overapproximation we can. |bitmap| might include bits that are not in
105 : // the zone's mark bitmap, if additional zones were collected by the GC.
106 0 : zone->markedAtoms().bitwiseAndWith(bitmap);
107 : }
108 :
109 : // Set any bits in the chunk mark bitmaps for atoms which are marked in bitmap.
110 : template <typename Bitmap>
111 : static void
112 0 : AddBitmapToChunkMarkBits(JSRuntime* runtime, Bitmap& bitmap)
113 : {
114 : // Make sure that by copying the mark bits for one arena in word sizes we
115 : // do not affect the mark bits for other arenas.
116 : static_assert(ArenaBitmapBits == ArenaBitmapWords * JS_BITS_PER_WORD,
117 : "ArenaBitmapWords must evenly divide ArenaBitmapBits");
118 :
119 0 : Zone* atomsZone = runtime->unsafeAtomsCompartment()->zone();
120 0 : for (auto thingKind : AllAllocKinds()) {
121 0 : for (ArenaIter aiter(atomsZone, thingKind); !aiter.done(); aiter.next()) {
122 0 : Arena* arena = aiter.get();
123 0 : uintptr_t* chunkWords = arena->chunk()->bitmap.arenaBits(arena);
124 0 : bitmap.bitwiseOrRangeInto(arena->atomBitmapStart(), ArenaBitmapWords, chunkWords);
125 : }
126 : }
127 0 : }
128 :
129 : void
130 0 : AtomMarkingRuntime::updateChunkMarkBits(JSRuntime* runtime)
131 : {
132 0 : MOZ_ASSERT(runtime->currentThreadHasExclusiveAccess());
133 :
134 : // Try to compute a simple union of the zone atom bitmaps before updating
135 : // the chunk mark bitmaps. If this allocation fails then fall back to
136 : // updating the chunk mark bitmaps separately for each zone.
137 0 : DenseBitmap markedUnion;
138 0 : if (markedUnion.ensureSpace(allocatedWords)) {
139 0 : for (ZonesIter zone(runtime, SkipAtoms); !zone.done(); zone.next()) {
140 : // We only need to update the chunk mark bits for zones which were
141 : // not collected in the current GC. Atoms which are referenced by
142 : // collected zones have already been marked.
143 0 : if (!zone->isCollectingFromAnyThread())
144 0 : zone->markedAtoms().bitwiseOrInto(markedUnion);
145 : }
146 0 : AddBitmapToChunkMarkBits(runtime, markedUnion);
147 : } else {
148 0 : for (ZonesIter zone(runtime, SkipAtoms); !zone.done(); zone.next()) {
149 0 : if (!zone->isCollectingFromAnyThread())
150 0 : AddBitmapToChunkMarkBits(runtime, zone->markedAtoms());
151 : }
152 : }
153 0 : }
154 :
155 : template <typename T>
156 : void
157 152821 : AtomMarkingRuntime::markAtom(JSContext* cx, T* thing)
158 : {
159 152821 : return inlinedMarkAtom(cx, thing);
160 : }
161 :
162 : template void AtomMarkingRuntime::markAtom(JSContext* cx, JSAtom* thing);
163 : template void AtomMarkingRuntime::markAtom(JSContext* cx, JS::Symbol* thing);
164 :
165 : void
166 21129 : AtomMarkingRuntime::markId(JSContext* cx, jsid id)
167 : {
168 21129 : if (JSID_IS_ATOM(id)) {
169 20518 : markAtom(cx, JSID_TO_ATOM(id));
170 20518 : return;
171 : }
172 611 : if (JSID_IS_SYMBOL(id)) {
173 54 : markAtom(cx, JSID_TO_SYMBOL(id));
174 54 : return;
175 : }
176 557 : MOZ_ASSERT(!JSID_IS_GCTHING(id));
177 : }
178 :
179 : void
180 8579 : AtomMarkingRuntime::markAtomValue(JSContext* cx, const Value& value)
181 : {
182 8579 : if (value.isString()) {
183 1771 : if (value.toString()->isAtom())
184 1771 : markAtom(cx, &value.toString()->asAtom());
185 1771 : return;
186 : }
187 6808 : if (value.isSymbol()) {
188 0 : markAtom(cx, value.toSymbol());
189 0 : return;
190 : }
191 6808 : MOZ_ASSERT_IF(value.isGCThing(), value.isObject() || value.isPrivateGCThing());
192 : }
193 :
194 : void
195 15 : AtomMarkingRuntime::adoptMarkedAtoms(Zone* target, Zone* source)
196 : {
197 15 : MOZ_ASSERT(target->runtimeFromAnyThread()->currentThreadHasExclusiveAccess());
198 15 : target->markedAtoms().bitwiseOrWith(source->markedAtoms());
199 15 : }
200 :
201 : #ifdef DEBUG
202 : template <typename T>
203 : bool
204 716332 : AtomMarkingRuntime::atomIsMarked(Zone* zone, T* thing)
205 : {
206 : static_assert(mozilla::IsSame<T, JSAtom>::value ||
207 : mozilla::IsSame<T, JS::Symbol>::value,
208 : "Should only be called with JSAtom* or JS::Symbol* argument");
209 :
210 716332 : MOZ_ASSERT(thing);
211 716332 : MOZ_ASSERT(!IsInsideNursery(thing));
212 716329 : MOZ_ASSERT(thing->zoneFromAnyThread()->isAtomsZone());
213 :
214 716341 : if (!zone->runtimeFromAnyThread()->permanentAtoms)
215 50655 : return true;
216 :
217 665686 : if (ThingIsPermanent(thing))
218 210493 : return true;
219 :
220 : if (mozilla::IsSame<T, JSAtom>::value) {
221 455191 : JSAtom* atom = reinterpret_cast<JSAtom*>(thing);
222 455191 : if (AtomIsPinnedInRuntime(zone->runtimeFromAnyThread(), atom))
223 87439 : return true;
224 : }
225 :
226 367819 : size_t bit = GetAtomBit(thing);
227 367815 : return zone->markedAtoms().getBit(bit);
228 : }
229 :
230 : template bool AtomMarkingRuntime::atomIsMarked(Zone* zone, JSAtom* thing);
231 : template bool AtomMarkingRuntime::atomIsMarked(Zone* zone, JS::Symbol* thing);
232 :
233 : template<>
234 : bool
235 4115 : AtomMarkingRuntime::atomIsMarked(Zone* zone, TenuredCell* thing)
236 : {
237 4115 : if (!thing)
238 0 : return true;
239 :
240 4115 : JS::TraceKind kind = thing->getTraceKind();
241 4115 : if (kind == JS::TraceKind::String) {
242 4115 : JSString* str = static_cast<JSString*>(thing);
243 4115 : if (str->isAtom())
244 4115 : return atomIsMarked(zone, &str->asAtom());
245 0 : return true;
246 : }
247 0 : if (kind == JS::TraceKind::Symbol)
248 0 : return atomIsMarked(zone, static_cast<JS::Symbol*>(thing));
249 0 : return true;
250 : }
251 :
252 : bool
253 94846 : AtomMarkingRuntime::idIsMarked(Zone* zone, jsid id)
254 : {
255 94846 : if (JSID_IS_ATOM(id))
256 93093 : return atomIsMarked(zone, JSID_TO_ATOM(id));
257 :
258 1753 : if (JSID_IS_SYMBOL(id))
259 1719 : return atomIsMarked(zone, JSID_TO_SYMBOL(id));
260 :
261 34 : MOZ_ASSERT(!JSID_IS_GCTHING(id));
262 34 : return true;
263 : }
264 :
265 : bool
266 261139 : AtomMarkingRuntime::valueIsMarked(Zone* zone, const Value& value)
267 : {
268 261139 : if (value.isString()) {
269 29651 : if (value.toString()->isAtom())
270 26061 : return atomIsMarked(zone, &value.toString()->asAtom());
271 3590 : return true;
272 : }
273 :
274 231489 : if (value.isSymbol())
275 280 : return atomIsMarked(zone, value.toSymbol());
276 :
277 231209 : MOZ_ASSERT_IF(value.isGCThing(), value.isObject() || value.isPrivateGCThing());
278 231209 : return true;
279 : }
280 :
281 : #endif // DEBUG
282 :
283 : } // namespace gc
284 :
285 : #ifdef DEBUG
286 :
287 : bool
288 427731 : AtomIsMarked(Zone* zone, JSAtom* atom)
289 : {
290 427731 : return zone->runtimeFromAnyThread()->gc.atomMarking.atomIsMarked(zone, atom);
291 : }
292 :
293 : bool
294 94846 : AtomIsMarked(Zone* zone, jsid id)
295 : {
296 94846 : return zone->runtimeFromAnyThread()->gc.atomMarking.idIsMarked(zone, id);
297 : }
298 :
299 : bool
300 261138 : AtomIsMarked(Zone* zone, const Value& value)
301 : {
302 261138 : return zone->runtimeFromAnyThread()->gc.atomMarking.valueIsMarked(zone, value);
303 : }
304 :
305 : #endif // DEBUG
306 :
307 : } // namespace js
|
