1 /*
2 * Copyright (c) 2001, 2020, 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
25 #ifndef SHARE_GC_G1_G1DIRTYCARDQUEUE_HPP
26 #define SHARE_GC_G1_G1DIRTYCARDQUEUE_HPP
27
28 #include "gc/g1/g1BufferNodeList.hpp"
29 #include "gc/g1/g1FreeIdSet.hpp"
30 #include "gc/shared/ptrQueue.hpp"
31 #include "memory/allocation.hpp"
32 #include "memory/padded.hpp"
33
34 class G1ConcurrentRefineThread;
35 class G1DirtyCardQueueSet;
36 class G1RedirtyCardsQueueSet;
37 class Thread;
38
39 // A ptrQueue whose elements are "oops", pointers to object heads.
40 class G1DirtyCardQueue: public PtrQueue {
41 protected:
42 virtual void handle_completed_buffer();
43
44 public:
45 G1DirtyCardQueue(G1DirtyCardQueueSet* qset);
46
47 // Flush before destroying; queue may be used to capture pending work while
48 // doing something else, with auto-flush on completion.
49 ~G1DirtyCardQueue();
50
51 // Process queue entries and release resources.
52 void flush() { flush_impl(); }
53
54 inline G1DirtyCardQueueSet* dirty_card_qset() const;
55
56 // Compiler support.
57 static ByteSize byte_offset_of_index() {
58 return PtrQueue::byte_offset_of_index<G1DirtyCardQueue>();
59 }
60 using PtrQueue::byte_width_of_index;
61
62 static ByteSize byte_offset_of_buf() {
63 return PtrQueue::byte_offset_of_buf<G1DirtyCardQueue>();
64 }
65 using PtrQueue::byte_width_of_buf;
66
67 };
68
69 class G1DirtyCardQueueSet: public PtrQueueSet {
70 // Head and tail of a list of BufferNodes, linked through their next()
71 // fields. Similar to G1BufferNodeList, but without the _entry_count.
72 struct HeadTail {
73 BufferNode* _head;
74 BufferNode* _tail;
75 HeadTail() : _head(NULL), _tail(NULL) {}
76 HeadTail(BufferNode* head, BufferNode* tail) : _head(head), _tail(tail) {}
77 };
78
79 // A lock-free FIFO of BufferNodes, linked through their next() fields.
80 // This class has a restriction that pop() may return NULL when there are
81 // buffers in the queue if there is a concurrent push/append operation.
82 class Queue {
83 BufferNode* volatile _head;
84 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(BufferNode*));
85 BufferNode* volatile _tail;
86 DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(BufferNode*));
87
88 NONCOPYABLE(Queue);
89
90 public:
91 Queue() : _head(NULL), _tail(NULL) {}
92 DEBUG_ONLY(~Queue();)
93
94 // Return the first buffer in the queue.
95 // Thread-safe, but the result may change immediately.
96 BufferNode* top() const;
97
98 // Thread-safe add the buffer to the end of the queue.
99 void push(BufferNode& node) { append(node, node); }
100
101 // Thread-safe add the buffers from first to last to the end of the queue.
102 void append(BufferNode& first, BufferNode& last);
103
104 // Thread-safe attempt to remove and return the first buffer in the queue.
105 // Returns NULL if the queue is empty, or if a concurrent push/append
106 // interferes. Uses GlobalCounter critical sections to address the ABA
107 // problem; this works with the buffer allocator's use of GlobalCounter
108 // synchronization.
109 BufferNode* pop();
110
111 // Take all the buffers from the queue, leaving the queue empty.
112 // Not thread-safe.
113 HeadTail take_all();
114 };
115
116 // Concurrent refinement may stop processing in the middle of a buffer if
117 // there is a pending safepoint, to avoid long delays to safepoint. A
118 // partially processed buffer needs to be recorded for processing by the
119 // safepoint if it's a GC safepoint; otherwise it needs to be recorded for
120 // further concurrent refinement work after the safepoint. But if the
121 // buffer was obtained from the completed buffer queue then it can't simply
122 // be added back to the queue, as that would introduce a new source of ABA
123 // for the queue.
124 //
125 // The PausedBuffer object is used to record such buffers for the upcoming
126 // safepoint, and provides access to the buffers recorded for previous
127 // safepoints. Before obtaining a buffer from the completed buffers queue,
128 // we first transfer any buffers from previous safepoints to the queue.
129 // This is ABA-safe because threads cannot be in the midst of a queue pop
130 // across a safepoint.
131 //
132 // The paused buffers are conceptually an extension of the completed buffers
133 // queue, and operations which need to deal with all of the queued buffers
134 // (such as concatenate_logs) also need to deal with any paused buffers. In
135 // general, if a safepoint performs a GC then the paused buffers will be
136 // processed as part of it, and there won't be any paused buffers after a
137 // GC safepoint.
138 class PausedBuffers {
139 class PausedList : public CHeapObj<mtGC> {
140 BufferNode* volatile _head;
141 BufferNode* _tail;
142 size_t _safepoint_id;
143
144 NONCOPYABLE(PausedList);
145
146 public:
147 PausedList();
148 DEBUG_ONLY(~PausedList();)
149
150 // Return true if this list was created to hold buffers for the
151 // next safepoint.
152 // precondition: not at safepoint.
153 bool is_next() const;
154
155 // Thread-safe add the buffer to the list.
156 // precondition: not at safepoint.
157 // precondition: is_next().
158 void add(BufferNode* node);
159
160 // Take all the buffers from the list. Not thread-safe.
161 HeadTail take();
162 };
163
164 // The most recently created list, which might be for either the next or
165 // a previous safepoint, or might be NULL if the next list hasn't been
166 // created yet. We only need one list because of the requirement that
167 // threads calling add() must first ensure there are no paused buffers
168 // from a previous safepoint. There might be many list instances existing
169 // at the same time though; there can be many threads competing to create
170 // and install the next list, and meanwhile there can be a thread dealing
171 // with the previous list.
172 PausedList* volatile _plist;
173 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(PausedList*));
174
175 NONCOPYABLE(PausedBuffers);
176
177 public:
178 PausedBuffers();
179 DEBUG_ONLY(~PausedBuffers();)
180
181 // Test whether there are any paused lists.
182 // Thread-safe, but the answer may change immediately.
183 bool is_empty() const;
184
185 // Thread-safe add the buffer to paused list for next safepoint.
186 // precondition: not at safepoint.
187 // precondition: does not have paused buffers from a previous safepoint.
188 void add(BufferNode* node);
189
190 // Thread-safe take all paused buffers for previous safepoints.
191 // precondition: not at safepoint.
192 HeadTail take_previous();
193
194 // Take all the paused buffers.
195 // precondition: at safepoint.
196 HeadTail take_all();
197 };
198
199 // The primary refinement thread, for activation when the processing
200 // threshold is reached. NULL if there aren't any refinement threads.
201 G1ConcurrentRefineThread* _primary_refinement_thread;
202 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(G1ConcurrentRefineThread*));
203 // Upper bound on the number of cards in the completed and paused buffers.
204 volatile size_t _num_cards;
205 DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(size_t));
206 // Buffers ready for refinement.
207 Queue _completed; // Has inner padding, including trailer.
208 // Buffers for which refinement is temporarily paused.
209 PausedBuffers _paused; // Has inner padding, including trailer.
210
211 G1FreeIdSet _free_ids;
212
213 // Activation threshold for the primary refinement thread.
214 size_t _process_cards_threshold;
215
216 // If the queue contains more cards than configured here, the
217 // mutator must start doing some of the concurrent refinement work.
218 size_t _max_cards;
219 size_t _max_cards_padding;
220 static const size_t MaxCardsUnlimited = SIZE_MAX;
221
222 // Array of cumulative dirty cards refined by mutator threads.
223 // Array has an entry per id in _free_ids.
224 size_t* _mutator_refined_cards_counters;
225
226 // Verify _num_cards == sum of cards in the completed queue.
227 void verify_num_cards() const NOT_DEBUG_RETURN;
228
229 // Thread-safe add a buffer to paused list for next safepoint.
230 // precondition: not at safepoint.
231 // precondition: does not have paused buffers from a previous safepoint.
232 void record_paused_buffer(BufferNode* node);
233 void enqueue_paused_buffers_aux(const HeadTail& paused);
234 // Thread-safe transfer paused buffers for previous safepoints to the queue.
235 // precondition: not at safepoint.
236 void enqueue_previous_paused_buffers();
237 // Transfer all paused buffers to the queue.
238 // precondition: at safepoint.
239 void enqueue_all_paused_buffers();
240
241 void abandon_completed_buffers();
242
243 // Refine the cards in "node" from its index to buffer_size.
244 // Stops processing if SuspendibleThreadSet::should_yield() is true.
245 // Returns true if the entire buffer was processed, false if there
246 // is a pending yield request. The node's index is updated to exclude
247 // the processed elements, e.g. up to the element before processing
248 // stopped, or one past the last element if the entire buffer was
249 // processed. Increments *total_refined_cards by the number of cards
250 // processed and removed from the buffer.
251 bool refine_buffer(BufferNode* node, uint worker_id, size_t* total_refined_cards);
252
253 bool mut_process_buffer(BufferNode* node);
254
255 // If the number of completed buffers is > stop_at, then remove and
256 // return a completed buffer from the list. Otherwise, return NULL.
257 BufferNode* get_completed_buffer(size_t stop_at = 0);
258
259 public:
260 G1DirtyCardQueueSet(BufferNode::Allocator* allocator);
261 ~G1DirtyCardQueueSet();
262
263 void set_primary_refinement_thread(G1ConcurrentRefineThread* thread) {
264 _primary_refinement_thread = thread;
265 }
266
267 // The number of parallel ids that can be claimed to allow collector or
268 // mutator threads to do card-processing work.
269 static uint num_par_ids();
270
271 static void handle_zero_index_for_thread(Thread* t);
272
273 // Either process the entire buffer and return true, or enqueue the
274 // buffer and return false. If the buffer is completely processed,
275 // it can be reused in place.
276 bool process_or_enqueue_completed_buffer(BufferNode* node);
277
278 virtual void enqueue_completed_buffer(BufferNode* node);
279
280 // Upper bound on the number of cards currently in in this queue set.
281 // Read without synchronization. The value may be high because there
282 // is a concurrent modification of the set of buffers.
283 size_t num_cards() const { return _num_cards; }
284
285 // Get/Set the number of cards that triggers log processing.
286 // Log processing should be done when the number of cards exceeds the
287 // threshold.
288 void set_process_cards_threshold(size_t sz) {
289 _process_cards_threshold = sz;
290 }
291 size_t process_cards_threshold() const {
292 return _process_cards_threshold;
293 }
294 static const size_t ProcessCardsThresholdNever = SIZE_MAX;
295
296 // Notify the consumer if the number of buffers crossed the threshold
297 void notify_if_necessary();
298
299 void merge_bufferlists(G1RedirtyCardsQueueSet* src);
300
301 G1BufferNodeList take_all_completed_buffers();
302
303 // If there are more than stop_at cards in the completed buffers, pop
304 // a buffer, refine its contents, and return true. Otherwise return
305 // false.
306 //
307 // Stops processing a buffer if SuspendibleThreadSet::should_yield(),
308 // recording the incompletely processed buffer for later processing of
309 // the remainder.
310 //
311 // Increments *total_refined_cards by the number of cards processed and
312 // removed from the buffer.
313 bool refine_completed_buffer_concurrently(uint worker_id,
314 size_t stop_at,
315 size_t* total_refined_cards);
316
317 // If a full collection is happening, reset partial logs, and release
318 // completed ones: the full collection will make them all irrelevant.
319 void abandon_logs();
320
321 // If any threads have partial logs, add them to the global list of logs.
322 void concatenate_logs();
323
324 void set_max_cards(size_t m) {
325 _max_cards = m;
326 }
327 size_t max_cards() const {
328 return _max_cards;
329 }
330
331 void set_max_cards_padding(size_t padding) {
332 _max_cards_padding = padding;
333 }
334 size_t max_cards_padding() const {
335 return _max_cards_padding;
336 }
337
338 // Total dirty cards refined by mutator threads.
339 size_t total_mutator_refined_cards() const;
340 };
341
342 inline G1DirtyCardQueueSet* G1DirtyCardQueue::dirty_card_qset() const {
343 return static_cast<G1DirtyCardQueueSet*>(qset());
344 }
345
346 #endif // SHARE_GC_G1_G1DIRTYCARDQUEUE_HPP