1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
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 #ifndef gc_ArenaList_inl_h
8 #define gc_ArenaList_inl_h
9
10 #include "gc/ArenaList.h"
11
12 #include "gc/Heap.h"
13 #include "gc/Zone.h"
14
append(Arena * arena)15 void js::gc::SortedArenaListSegment::append(Arena* arena) {
16 MOZ_ASSERT(arena);
17 MOZ_ASSERT_IF(head, head->getAllocKind() == arena->getAllocKind());
18 *tailp = arena;
19 tailp = &arena->next;
20 }
21
ArenaList()22 inline js::gc::ArenaList::ArenaList() { clear(); }
23
ArenaList(ArenaList && other)24 inline js::gc::ArenaList::ArenaList(ArenaList&& other) { moveFrom(other); }
25
~ArenaList()26 inline js::gc::ArenaList::~ArenaList() { MOZ_ASSERT(isEmpty()); }
27
moveFrom(ArenaList & other)28 void js::gc::ArenaList::moveFrom(ArenaList& other) {
29 other.check();
30
31 head_ = other.head_;
32 cursorp_ = other.isCursorAtHead() ? &head_ : other.cursorp_;
33 other.clear();
34
35 check();
36 }
37
38 js::gc::ArenaList& js::gc::ArenaList::operator=(ArenaList&& other) {
39 MOZ_ASSERT(isEmpty());
40 moveFrom(other);
41 return *this;
42 }
43
ArenaList(const SortedArenaListSegment & segment)44 inline js::gc::ArenaList::ArenaList(const SortedArenaListSegment& segment) {
45 head_ = segment.head;
46 cursorp_ = segment.isEmpty() ? &head_ : segment.tailp;
47 check();
48 }
49
50 // This does checking just of |head_| and |cursorp_|.
check()51 void js::gc::ArenaList::check() const {
52 #ifdef DEBUG
53 // If the list is empty, it must have this form.
54 MOZ_ASSERT_IF(!head_, cursorp_ == &head_);
55
56 // If there's an arena following the cursor, it must not be full.
57 Arena* cursor = *cursorp_;
58 MOZ_ASSERT_IF(cursor, cursor->hasFreeThings());
59 #endif
60 }
61
clear()62 void js::gc::ArenaList::clear() {
63 head_ = nullptr;
64 cursorp_ = &head_;
65 check();
66 }
67
isEmpty()68 bool js::gc::ArenaList::isEmpty() const {
69 check();
70 return !head_;
71 }
72
head()73 js::gc::Arena* js::gc::ArenaList::head() const {
74 check();
75 return head_;
76 }
77
isCursorAtHead()78 bool js::gc::ArenaList::isCursorAtHead() const {
79 check();
80 return cursorp_ == &head_;
81 }
82
isCursorAtEnd()83 bool js::gc::ArenaList::isCursorAtEnd() const {
84 check();
85 return !*cursorp_;
86 }
87
arenaAfterCursor()88 js::gc::Arena* js::gc::ArenaList::arenaAfterCursor() const {
89 check();
90 return *cursorp_;
91 }
92
takeNextArena()93 js::gc::Arena* js::gc::ArenaList::takeNextArena() {
94 check();
95 Arena* arena = *cursorp_;
96 if (!arena) {
97 return nullptr;
98 }
99 cursorp_ = &arena->next;
100 check();
101 return arena;
102 }
103
insertAtCursor(Arena * a)104 void js::gc::ArenaList::insertAtCursor(Arena* a) {
105 check();
106 a->next = *cursorp_;
107 *cursorp_ = a;
108 // At this point, the cursor is sitting before |a|. Move it after |a|
109 // if necessary.
110 if (!a->hasFreeThings()) {
111 cursorp_ = &a->next;
112 }
113 check();
114 }
115
insertBeforeCursor(Arena * a)116 void js::gc::ArenaList::insertBeforeCursor(Arena* a) {
117 check();
118 a->next = *cursorp_;
119 *cursorp_ = a;
120 cursorp_ = &a->next;
121 check();
122 }
123
insertListWithCursorAtEnd(ArenaList & other)124 js::gc::ArenaList& js::gc::ArenaList::insertListWithCursorAtEnd(
125 ArenaList& other) {
126 check();
127 other.check();
128 MOZ_ASSERT(other.isCursorAtEnd());
129
130 if (other.isEmpty()) {
131 return *this;
132 }
133
134 // Insert the full arenas of |other| after those of |this|.
135 *other.cursorp_ = *cursorp_;
136 *cursorp_ = other.head_;
137 cursorp_ = other.cursorp_;
138 check();
139
140 other.clear();
141 return *this;
142 }
143
takeFirstArena()144 js::gc::Arena* js::gc::ArenaList::takeFirstArena() {
145 check();
146 Arena* arena = head_;
147 if (!arena) {
148 return nullptr;
149 }
150
151 head_ = arena->next;
152 if (cursorp_ == &arena->next) {
153 cursorp_ = &head_;
154 }
155
156 check();
157 return arena;
158 }
159
SortedArenaList(size_t thingsPerArena)160 js::gc::SortedArenaList::SortedArenaList(size_t thingsPerArena) {
161 reset(thingsPerArena);
162 }
163
setThingsPerArena(size_t thingsPerArena)164 void js::gc::SortedArenaList::setThingsPerArena(size_t thingsPerArena) {
165 MOZ_ASSERT(thingsPerArena && thingsPerArena <= MaxThingsPerArena);
166 thingsPerArena_ = thingsPerArena;
167 }
168
reset(size_t thingsPerArena)169 void js::gc::SortedArenaList::reset(size_t thingsPerArena) {
170 setThingsPerArena(thingsPerArena);
171 // Initialize the segments.
172 for (size_t i = 0; i <= thingsPerArena; ++i) {
173 segments[i].clear();
174 }
175 }
176
insertAt(Arena * arena,size_t nfree)177 void js::gc::SortedArenaList::insertAt(Arena* arena, size_t nfree) {
178 MOZ_ASSERT(nfree <= thingsPerArena_);
179 segments[nfree].append(arena);
180 }
181
extractEmpty(Arena ** empty)182 void js::gc::SortedArenaList::extractEmpty(Arena** empty) {
183 SortedArenaListSegment& segment = segments[thingsPerArena_];
184 if (segment.head) {
185 *segment.tailp = *empty;
186 *empty = segment.head;
187 segment.clear();
188 }
189 }
190
toArenaList()191 js::gc::ArenaList js::gc::SortedArenaList::toArenaList() {
192 // Link the non-empty segment tails up to the non-empty segment heads.
193 size_t tailIndex = 0;
194 for (size_t headIndex = 1; headIndex <= thingsPerArena_; ++headIndex) {
195 if (headAt(headIndex)) {
196 segments[tailIndex].linkTo(headAt(headIndex));
197 tailIndex = headIndex;
198 }
199 }
200 // Point the tail of the final non-empty segment at null. Note that if
201 // the list is empty, this will just set segments[0].head to null.
202 segments[tailIndex].linkTo(nullptr);
203 // Create an ArenaList with head and cursor set to the head and tail of
204 // the first segment (if that segment is empty, only the head is used).
205 return ArenaList(segments[0]);
206 }
207
208 #ifdef DEBUG
209
allEmpty()210 bool js::gc::FreeLists::allEmpty() const {
211 for (auto i : AllAllocKinds()) {
212 if (!isEmpty(i)) {
213 return false;
214 }
215 }
216 return true;
217 }
218
isEmpty(AllocKind kind)219 bool js::gc::FreeLists::isEmpty(AllocKind kind) const {
220 return freeLists_[kind]->isEmpty();
221 }
222
223 #endif
224
clear()225 void js::gc::FreeLists::clear() {
226 for (auto i : AllAllocKinds()) {
227 #ifdef DEBUG
228 auto old = freeLists_[i];
229 if (!old->isEmpty()) {
230 old->getArena()->checkNoMarkedFreeCells();
231 }
232 #endif
233 freeLists_[i] = &emptySentinel;
234 }
235 }
236
allocate(AllocKind kind)237 js::gc::TenuredCell* js::gc::FreeLists::allocate(AllocKind kind) {
238 return freeLists_[kind]->allocate(Arena::thingSize(kind));
239 }
240
unmarkPreMarkedFreeCells(AllocKind kind)241 void js::gc::FreeLists::unmarkPreMarkedFreeCells(AllocKind kind) {
242 FreeSpan* freeSpan = freeLists_[kind];
243 if (!freeSpan->isEmpty()) {
244 freeSpan->getArena()->unmarkPreMarkedFreeCells();
245 }
246 }
247
runtime()248 JSRuntime* js::gc::ArenaLists::runtime() {
249 return zone_->runtimeFromMainThread();
250 }
251
runtimeFromAnyThread()252 JSRuntime* js::gc::ArenaLists::runtimeFromAnyThread() {
253 return zone_->runtimeFromAnyThread();
254 }
255
getFirstArena(AllocKind thingKind)256 js::gc::Arena* js::gc::ArenaLists::getFirstArena(AllocKind thingKind) const {
257 return arenaList(thingKind).head();
258 }
259
getFirstCollectingArena(AllocKind thingKind)260 js::gc::Arena* js::gc::ArenaLists::getFirstCollectingArena(
261 AllocKind thingKind) const {
262 return collectingArenaList(thingKind).head();
263 }
264
getFirstSweptArena(AllocKind thingKind)265 js::gc::Arena* js::gc::ArenaLists::getFirstSweptArena(
266 AllocKind thingKind) const {
267 if (thingKind != incrementalSweptArenaKind.ref()) {
268 return nullptr;
269 }
270 return incrementalSweptArenas.ref().head();
271 }
272
getArenaAfterCursor(AllocKind thingKind)273 js::gc::Arena* js::gc::ArenaLists::getArenaAfterCursor(
274 AllocKind thingKind) const {
275 return arenaList(thingKind).arenaAfterCursor();
276 }
277
arenaListsAreEmpty()278 bool js::gc::ArenaLists::arenaListsAreEmpty() const {
279 for (auto i : AllAllocKinds()) {
280 /*
281 * The arena cannot be empty if the background finalization is not yet
282 * done.
283 */
284 if (concurrentUse(i) == ConcurrentUse::BackgroundFinalize) {
285 return false;
286 }
287 if (!arenaList(i).isEmpty()) {
288 return false;
289 }
290 }
291 return true;
292 }
293
doneBackgroundFinalize(AllocKind kind)294 bool js::gc::ArenaLists::doneBackgroundFinalize(AllocKind kind) const {
295 return concurrentUse(kind) != ConcurrentUse::BackgroundFinalize;
296 }
297
needBackgroundFinalizeWait(AllocKind kind)298 bool js::gc::ArenaLists::needBackgroundFinalizeWait(AllocKind kind) const {
299 return concurrentUse(kind) == ConcurrentUse::BackgroundFinalize;
300 }
301
clearFreeLists()302 void js::gc::ArenaLists::clearFreeLists() { freeLists().clear(); }
303
allocateFromFreeList(AllocKind thingKind)304 MOZ_ALWAYS_INLINE js::gc::TenuredCell* js::gc::ArenaLists::allocateFromFreeList(
305 AllocKind thingKind) {
306 return freeLists().allocate(thingKind);
307 }
308
unmarkPreMarkedFreeCells()309 void js::gc::ArenaLists::unmarkPreMarkedFreeCells() {
310 for (auto i : AllAllocKinds()) {
311 freeLists().unmarkPreMarkedFreeCells(i);
312 }
313 }
314
checkEmptyFreeLists()315 void js::gc::ArenaLists::checkEmptyFreeLists() {
316 MOZ_ASSERT(freeLists().allEmpty());
317 }
318
checkEmptyArenaLists()319 void js::gc::ArenaLists::checkEmptyArenaLists() {
320 #ifdef DEBUG
321 for (auto i : AllAllocKinds()) {
322 checkEmptyArenaList(i);
323 }
324 #endif
325 }
326
327 #endif // gc_ArenaList_inl_h
328