1 /*
2 * Copyright (c) 2016, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 #include "precompiled.hpp"
25 #include "gc/z/zErrno.hpp"
26 #include "gc/z/zFlags.hpp"
27 #include "gc/z/zGlobals.hpp"
28 #include "gc/z/zLock.inline.hpp"
29 #include "gc/z/zMarkStack.inline.hpp"
30 #include "logging/log.hpp"
31 #include "runtime/atomic.hpp"
32 #include "utilities/debug.hpp"
33
34 #include <sys/mman.h>
35 #include <sys/types.h>
36
37 ZMarkStackSpace::ZMarkStackSpace() :
38 _expand_lock(),
39 _top(0),
40 _end(0) {
41 assert(ZMarkStacksMax >= ZMarkStackSpaceExpandSize, "ZMarkStacksMax too small");
42 assert(ZMarkStacksMax <= ZMarkStackSpaceSize, "ZMarkStacksMax too large");
43
44 // Reserve address space
45 const void* res = mmap((void*)ZMarkStackSpaceStart, ZMarkStackSpaceSize,
46 PROT_NONE, MAP_ANONYMOUS|MAP_PRIVATE|MAP_NORESERVE, -1, 0);
47 if (res != (void*)ZMarkStackSpaceStart) {
48 log_error(gc, marking)("Failed to reserve address space for marking stacks");
49 return;
50 }
51
52 // Successfully initialized
53 _top = _end = ZMarkStackSpaceStart;
54 }
55
56 bool ZMarkStackSpace::is_initialized() const {
57 return _top != 0;
58 }
59
60 bool ZMarkStackSpace::expand() {
61 const size_t max = ZMarkStackSpaceStart + ZMarkStacksMax;
62 if (_end + ZMarkStackSpaceExpandSize > max) {
63 // Expansion limit reached
64 return false;
65 }
66
67 void* const res = mmap((void*)_end, ZMarkStackSpaceExpandSize,
68 PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE|MAP_FIXED, -1, 0);
69 if (res == MAP_FAILED) {
70 ZErrno err;
71 log_error(gc, marking)("Failed to map memory for marking stacks (%s)", err.to_string());
72 return false;
73 }
74
75 return true;
76 }
77
78 uintptr_t ZMarkStackSpace::alloc_space(size_t size) {
79 uintptr_t top = _top;
80
81 for (;;) {
82 const uintptr_t new_top = top + size;
83 if (new_top > _end) {
84 // Not enough space left
85 return 0;
86 }
87
88 const uintptr_t prev_top = Atomic::cmpxchg(new_top, &_top, top);
89 if (prev_top == top) {
90 // Success
91 return top;
92 }
93
94 // Retry
95 top = prev_top;
96 }
97 }
98
99 uintptr_t ZMarkStackSpace::expand_and_alloc_space(size_t size) {
100 ZLocker locker(&_expand_lock);
101
102 // Retry allocation before expanding
103 uintptr_t addr = alloc_space(size);
104 if (addr != 0) {
105 return addr;
106 }
107
108 // Expand stack space
109 if (!expand()) {
110 // We currently can't handle the situation where we
111 // are running out of mark stack space.
112 fatal("Mark stack overflow (allocated " SIZE_FORMAT "M, size " SIZE_FORMAT "M, max " SIZE_FORMAT "M),"
113 " use -XX:ZMarkStacksMax=? to increase this limit",
114 (_end - ZMarkStackSpaceStart) / M, size / M, ZMarkStacksMax / M);
115 return 0;
116 }
117
118 log_debug(gc, marking)("Expanding mark stack space: " SIZE_FORMAT "M->" SIZE_FORMAT "M",
119 (_end - ZMarkStackSpaceStart) / M,
120 (_end - ZMarkStackSpaceStart + ZMarkStackSpaceExpandSize) / M);
121
122 // Increment top before end to make sure another
123 // thread can't steal out newly expanded space.
124 addr = Atomic::add(size, &_top) - size;
125 _end += ZMarkStackSpaceExpandSize;
126
127 return addr;
128 }
129
130 uintptr_t ZMarkStackSpace::alloc(size_t size) {
131 const uintptr_t addr = alloc_space(size);
132 if (addr != 0) {
133 return addr;
134 }
135
136 return expand_and_alloc_space(size);
137 }
138
139 ZMarkStackAllocator::ZMarkStackAllocator() :
140 _freelist(),
141 _space() {
142 guarantee(sizeof(ZMarkStack) == ZMarkStackSize, "Size mismatch");
143 guarantee(sizeof(ZMarkStackMagazine) <= ZMarkStackSize, "Size mismatch");
144
145 // Prime free list to avoid an immediate space
146 // expansion when marking starts.
147 if (_space.is_initialized()) {
148 prime_freelist();
149 }
150 }
151
152 bool ZMarkStackAllocator::is_initialized() const {
153 return _space.is_initialized();
154 }
155
156 void ZMarkStackAllocator::prime_freelist() {
157 for (size_t size = 0; size < ZMarkStackSpaceExpandSize; size += ZMarkStackMagazineSize) {
158 const uintptr_t addr = _space.alloc(ZMarkStackMagazineSize);
159 ZMarkStackMagazine* const magazine = create_magazine_from_space(addr, ZMarkStackMagazineSize);
160 free_magazine(magazine);
161 }
162 }
163
164 ZMarkStackMagazine* ZMarkStackAllocator::create_magazine_from_space(uintptr_t addr, size_t size) {
165 assert(is_aligned(size, ZMarkStackSize), "Invalid size");
166
167 // Use first stack as magazine
168 ZMarkStackMagazine* const magazine = new ((void*)addr) ZMarkStackMagazine();
169 for (size_t i = ZMarkStackSize; i < size; i += ZMarkStackSize) {
170 ZMarkStack* const stack = new ((void*)(addr + i)) ZMarkStack();
171 const bool success = magazine->push(stack);
172 assert(success, "Magazine should never get full");
173 }
174
175 return magazine;
176 }
177
178 ZMarkStackMagazine* ZMarkStackAllocator::alloc_magazine() {
179 // Try allocating from the free list first
180 ZMarkStackMagazine* const magazine = _freelist.pop_atomic();
181 if (magazine != NULL) {
182 return magazine;
183 }
184
185 // Allocate new magazine
186 const uintptr_t addr = _space.alloc(ZMarkStackMagazineSize);
187 if (addr == 0) {
188 return NULL;
189 }
190
191 return create_magazine_from_space(addr, ZMarkStackMagazineSize);
192 }
193
194 void ZMarkStackAllocator::free_magazine(ZMarkStackMagazine* magazine) {
195 _freelist.push_atomic(magazine);
196 }
197
198 ZMarkStripe::ZMarkStripe() :
199 _published(),
200 _overflowed() {}
201
202 ZMarkStripeSet::ZMarkStripeSet() :
203 _nstripes(0),
204 _nstripes_mask(0),
205 _stripes() {}
206
207 void ZMarkStripeSet::set_nstripes(size_t nstripes) {
208 assert(is_power_of_2(nstripes), "Must be a power of two");
209 assert(is_power_of_2(ZMarkStripesMax), "Must be a power of two");
210 assert(nstripes >= 1, "Invalid number of stripes");
211 assert(nstripes <= ZMarkStripesMax, "Invalid number of stripes");
212
213 _nstripes = nstripes;
214 _nstripes_mask = nstripes - 1;
215
216 log_debug(gc, marking)("Using " SIZE_FORMAT " mark stripes", _nstripes);
217 }
218
219 bool ZMarkStripeSet::is_empty() const {
220 for (size_t i = 0; i < _nstripes; i++) {
221 if (!_stripes[i].is_empty()) {
222 return false;
223 }
224 }
225
226 return true;
227 }
228
229 ZMarkStripe* ZMarkStripeSet::stripe_for_worker(uint nworkers, uint worker_id) {
230 const size_t spillover_limit = (nworkers / _nstripes) * _nstripes;
231 size_t index;
232
233 if (worker_id < spillover_limit) {
234 // Not a spillover worker, use natural stripe
235 index = worker_id & _nstripes_mask;
236 } else {
237 // Distribute spillover workers evenly across stripes
238 const size_t spillover_nworkers = nworkers - spillover_limit;
239 const size_t spillover_worker_id = worker_id - spillover_limit;
240 const double spillover_chunk = (double)_nstripes / (double)spillover_nworkers;
241 index = spillover_worker_id * spillover_chunk;
242 }
243
244 assert(index < _nstripes, "Invalid index");
245 return &_stripes[index];
246 }
247
248 ZMarkThreadLocalStacks::ZMarkThreadLocalStacks() :
249 _magazine(NULL) {
250 for (size_t i = 0; i < ZMarkStripesMax; i++) {
251 _stacks[i] = NULL;
252 }
253 }
254
255 bool ZMarkThreadLocalStacks::is_empty(const ZMarkStripeSet* stripes) const {
256 for (size_t i = 0; i < stripes->nstripes(); i++) {
257 ZMarkStack* const stack = _stacks[i];
258 if (stack != NULL) {
259 return false;
260 }
261 }
262
263 return true;
264 }
265
266 ZMarkStack* ZMarkThreadLocalStacks::allocate_stack(ZMarkStackAllocator* allocator) {
267 if (_magazine == NULL) {
268 // Allocate new magazine
269 _magazine = allocator->alloc_magazine();
270 if (_magazine == NULL) {
271 return NULL;
272 }
273 }
274
275 ZMarkStack* stack = NULL;
276
277 if (!_magazine->pop(stack)) {
278 // Magazine is empty, convert magazine into a new stack
279 _magazine->~ZMarkStackMagazine();
280 stack = new ((void*)_magazine) ZMarkStack();
281 _magazine = NULL;
282 }
283
284 return stack;
285 }
286
287 void ZMarkThreadLocalStacks::free_stack(ZMarkStackAllocator* allocator, ZMarkStack* stack) {
288 for (;;) {
289 if (_magazine == NULL) {
290 // Convert stack into a new magazine
291 stack->~ZMarkStack();
292 _magazine = new ((void*)stack) ZMarkStackMagazine();
293 return;
294 }
295
296 if (_magazine->push(stack)) {
297 // Success
298 return;
299 }
300
301 // Free and uninstall full magazine
302 allocator->free_magazine(_magazine);
303 _magazine = NULL;
304 }
305 }
306
307 bool ZMarkThreadLocalStacks::push_slow(ZMarkStackAllocator* allocator,
308 ZMarkStripe* stripe,
309 ZMarkStack** stackp,
310 ZMarkStackEntry entry,
311 bool publish) {
312 ZMarkStack* stack = *stackp;
313
314 for (;;) {
315 if (stack == NULL) {
316 // Allocate and install new stack
317 *stackp = stack = allocate_stack(allocator);
318 if (stack == NULL) {
319 // Out of mark stack memory
320 return false;
321 }
322 }
323
324 if (stack->push(entry)) {
325 // Success
326 return true;
327 }
328
329 // Publish/Overflow and uninstall stack
330 stripe->publish_stack(stack, publish);
331 *stackp = stack = NULL;
332 }
333 }
334
335 bool ZMarkThreadLocalStacks::pop_slow(ZMarkStackAllocator* allocator,
336 ZMarkStripe* stripe,
337 ZMarkStack** stackp,
338 ZMarkStackEntry& entry) {
339 ZMarkStack* stack = *stackp;
340
341 for (;;) {
342 if (stack == NULL) {
343 // Try steal and install stack
344 *stackp = stack = stripe->steal_stack();
345 if (stack == NULL) {
346 // Nothing to steal
347 return false;
348 }
349 }
350
351 if (stack->pop(entry)) {
352 // Success
353 return true;
354 }
355
356 // Free and uninstall stack
357 free_stack(allocator, stack);
358 *stackp = stack = NULL;
359 }
360 }
361
362 bool ZMarkThreadLocalStacks::flush(ZMarkStackAllocator* allocator, ZMarkStripeSet* stripes) {
363 bool flushed = false;
364
365 // Flush all stacks
366 for (size_t i = 0; i < stripes->nstripes(); i++) {
367 ZMarkStripe* const stripe = stripes->stripe_at(i);
368 ZMarkStack** const stackp = &_stacks[i];
369 ZMarkStack* const stack = *stackp;
370 if (stack == NULL) {
371 continue;
372 }
373
374 // Free/Publish and uninstall stack
375 if (stack->is_empty()) {
376 free_stack(allocator, stack);
377 } else {
378 stripe->publish_stack(stack);
379 flushed = true;
380 }
381 *stackp = NULL;
382 }
383
384 return flushed;
385 }
386
387 void ZMarkThreadLocalStacks::free(ZMarkStackAllocator* allocator) {
388 // Free and uninstall magazine
389 if (_magazine != NULL) {
390 allocator->free_magazine(_magazine);
391 _magazine = NULL;
392 }
393 }