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/zMarkStack.inline.hpp"
26#include "gc/z/zMarkStackAllocator.hpp"
27#include "logging/log.hpp"
28#include "utilities/debug.hpp"
29
30ZMarkStripe::ZMarkStripe() :
31 _published(),
32 _overflowed() {}
33
34ZMarkStripeSet::ZMarkStripeSet() :
35 _nstripes(0),
36 _nstripes_mask(0),
37 _stripes() {}
38
39void ZMarkStripeSet::set_nstripes(size_t nstripes) {
40 assert(is_power_of_2(nstripes), "Must be a power of two");
41 assert(is_power_of_2(ZMarkStripesMax), "Must be a power of two");
42 assert(nstripes >= 1, "Invalid number of stripes");
43 assert(nstripes <= ZMarkStripesMax, "Invalid number of stripes");
44
45 _nstripes = nstripes;
46 _nstripes_mask = nstripes - 1;
47
48 log_debug(gc, marking)("Using " SIZE_FORMAT " mark stripes", _nstripes);
49}
50
51bool ZMarkStripeSet::is_empty() const {
52 for (size_t i = 0; i < _nstripes; i++) {
53 if (!_stripes[i].is_empty()) {
54 return false;
55 }
56 }
57
58 return true;
59}
60
61ZMarkStripe* ZMarkStripeSet::stripe_for_worker(uint nworkers, uint worker_id) {
62 const size_t spillover_limit = (nworkers / _nstripes) * _nstripes;
63 size_t index;
64
65 if (worker_id < spillover_limit) {
66 // Not a spillover worker, use natural stripe
67 index = worker_id & _nstripes_mask;
68 } else {
69 // Distribute spillover workers evenly across stripes
70 const size_t spillover_nworkers = nworkers - spillover_limit;
71 const size_t spillover_worker_id = worker_id - spillover_limit;
72 const double spillover_chunk = (double)_nstripes / (double)spillover_nworkers;
73 index = spillover_worker_id * spillover_chunk;
74 }
75
76 assert(index < _nstripes, "Invalid index");
77 return &_stripes[index];
78}
79
80ZMarkThreadLocalStacks::ZMarkThreadLocalStacks() :
81 _magazine(NULL) {
82 for (size_t i = 0; i < ZMarkStripesMax; i++) {
83 _stacks[i] = NULL;
84 }
85}
86
87bool ZMarkThreadLocalStacks::is_empty(const ZMarkStripeSet* stripes) const {
88 for (size_t i = 0; i < stripes->nstripes(); i++) {
89 ZMarkStack* const stack = _stacks[i];
90 if (stack != NULL) {
91 return false;
92 }
93 }
94
95 return true;
96}
97
98ZMarkStack* ZMarkThreadLocalStacks::allocate_stack(ZMarkStackAllocator* allocator) {
99 if (_magazine == NULL) {
100 // Allocate new magazine
101 _magazine = allocator->alloc_magazine();
102 if (_magazine == NULL) {
103 return NULL;
104 }
105 }
106
107 ZMarkStack* stack = NULL;
108
109 if (!_magazine->pop(stack)) {
110 // Magazine is empty, convert magazine into a new stack
111 _magazine->~ZMarkStackMagazine();
112 stack = new ((void*)_magazine) ZMarkStack();
113 _magazine = NULL;
114 }
115
116 return stack;
117}
118
119void ZMarkThreadLocalStacks::free_stack(ZMarkStackAllocator* allocator, ZMarkStack* stack) {
120 for (;;) {
121 if (_magazine == NULL) {
122 // Convert stack into a new magazine
123 stack->~ZMarkStack();
124 _magazine = new ((void*)stack) ZMarkStackMagazine();
125 return;
126 }
127
128 if (_magazine->push(stack)) {
129 // Success
130 return;
131 }
132
133 // Free and uninstall full magazine
134 allocator->free_magazine(_magazine);
135 _magazine = NULL;
136 }
137}
138
139bool ZMarkThreadLocalStacks::push_slow(ZMarkStackAllocator* allocator,
140 ZMarkStripe* stripe,
141 ZMarkStack** stackp,
142 ZMarkStackEntry entry,
143 bool publish) {
144 ZMarkStack* stack = *stackp;
145
146 for (;;) {
147 if (stack == NULL) {
148 // Allocate and install new stack
149 *stackp = stack = allocate_stack(allocator);
150 if (stack == NULL) {
151 // Out of mark stack memory
152 return false;
153 }
154 }
155
156 if (stack->push(entry)) {
157 // Success
158 return true;
159 }
160
161 // Publish/Overflow and uninstall stack
162 stripe->publish_stack(stack, publish);
163 *stackp = stack = NULL;
164 }
165}
166
167bool ZMarkThreadLocalStacks::pop_slow(ZMarkStackAllocator* allocator,
168 ZMarkStripe* stripe,
169 ZMarkStack** stackp,
170 ZMarkStackEntry& entry) {
171 ZMarkStack* stack = *stackp;
172
173 for (;;) {
174 if (stack == NULL) {
175 // Try steal and install stack
176 *stackp = stack = stripe->steal_stack();
177 if (stack == NULL) {
178 // Nothing to steal
179 return false;
180 }
181 }
182
183 if (stack->pop(entry)) {
184 // Success
185 return true;
186 }
187
188 // Free and uninstall stack
189 free_stack(allocator, stack);
190 *stackp = stack = NULL;
191 }
192}
193
194bool ZMarkThreadLocalStacks::flush(ZMarkStackAllocator* allocator, ZMarkStripeSet* stripes) {
195 bool flushed = false;
196
197 // Flush all stacks
198 for (size_t i = 0; i < stripes->nstripes(); i++) {
199 ZMarkStripe* const stripe = stripes->stripe_at(i);
200 ZMarkStack** const stackp = &_stacks[i];
201 ZMarkStack* const stack = *stackp;
202 if (stack == NULL) {
203 continue;
204 }
205
206 // Free/Publish and uninstall stack
207 if (stack->is_empty()) {
208 free_stack(allocator, stack);
209 } else {
210 stripe->publish_stack(stack);
211 flushed = true;
212 }
213 *stackp = NULL;
214 }
215
216 return flushed;
217}
218
219void ZMarkThreadLocalStacks::free(ZMarkStackAllocator* allocator) {
220 // Free and uninstall magazine
221 if (_magazine != NULL) {
222 allocator->free_magazine(_magazine);
223 _magazine = NULL;
224 }
225}
226