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 // Thread-safe add the buffer to paused list for next safepoint.
182 // precondition: not at safepoint.
183 // precondition: does not have paused buffers from a previous safepoint.
184 void add(BufferNode* node);
185
186 // Thread-safe take all paused buffers for previous safepoints.
187 // precondition: not at safepoint.
188 HeadTail take_previous();
189
190 // Take all the paused buffers.
191 // precondition: at safepoint.
192 HeadTail take_all();
193 };
194
195 // The primary refinement thread, for activation when the processing
196 // threshold is reached. NULL if there aren't any refinement threads.
197 G1ConcurrentRefineThread* _primary_refinement_thread;
198 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(G1ConcurrentRefineThread*));
199 // Upper bound on the number of cards in the completed and paused buffers.
200 volatile size_t _num_cards;
201 DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(size_t));
202 // Buffers ready for refinement.
203 Queue _completed; // Has inner padding, including trailer.
204 // Buffers for which refinement is temporarily paused.
205 PausedBuffers _paused; // Has inner padding, including trailer.
206
207 G1FreeIdSet _free_ids;
208
209 // Activation threshold for the primary refinement thread.
210 size_t _process_cards_threshold;
211
212 // If the queue contains more cards than configured here, the
213 // mutator must start doing some of the concurrent refinement work.
214 size_t _max_cards;
215 size_t _max_cards_padding;
216 static const size_t MaxCardsUnlimited = SIZE_MAX;
217
218 // Array of cumulative dirty cards refined by mutator threads.
219 // Array has an entry per id in _free_ids.
220 size_t* _mutator_refined_cards_counters;
221
222 // Verify _num_cards == sum of cards in the completed queue.
223 void verify_num_cards() const NOT_DEBUG_RETURN;
224
225 // Thread-safe add a buffer to paused list for next safepoint.
226 // precondition: not at safepoint.
227 void record_paused_buffer(BufferNode* node);
228 void enqueue_paused_buffers_aux(const HeadTail& paused);
229 // Thread-safe transfer paused buffers for previous safepoints to the queue.
230 // precondition: not at safepoint.
231 void enqueue_previous_paused_buffers();
232 // Transfer all paused buffers to the queue.
233 // precondition: at safepoint.
234 void enqueue_all_paused_buffers();
235
236 void abandon_completed_buffers();
237
238 // Refine the cards in "node" from its index to buffer_size.
239 // Stops processing if SuspendibleThreadSet::should_yield() is true.
240 // Returns true if the entire buffer was processed, false if there
241 // is a pending yield request. The node's index is updated to exclude
242 // the processed elements, e.g. up to the element before processing
243 // stopped, or one past the last element if the entire buffer was
244 // processed. Increments *total_refined_cards by the number of cards
245 // processed and removed from the buffer.
246 bool refine_buffer(BufferNode* node, uint worker_id, size_t* total_refined_cards);
247
248 bool mut_process_buffer(BufferNode* node);
249
250 // If the number of completed buffers is > stop_at, then remove and
251 // return a completed buffer from the list. Otherwise, return NULL.
252 BufferNode* get_completed_buffer(size_t stop_at = 0);
253
254 public:
255 G1DirtyCardQueueSet(BufferNode::Allocator* allocator);
256 ~G1DirtyCardQueueSet();
257
258 void set_primary_refinement_thread(G1ConcurrentRefineThread* thread) {
259 _primary_refinement_thread = thread;
260 }
261
262 // The number of parallel ids that can be claimed to allow collector or
263 // mutator threads to do card-processing work.
264 static uint num_par_ids();
265
266 static void handle_zero_index_for_thread(Thread* t);
267
268 // Either process the entire buffer and return true, or enqueue the
269 // buffer and return false. If the buffer is completely processed,
270 // it can be reused in place.
271 bool process_or_enqueue_completed_buffer(BufferNode* node);
272
273 virtual void enqueue_completed_buffer(BufferNode* node);
274
275 // Upper bound on the number of cards currently in in this queue set.
276 // Read without synchronization. The value may be high because there
277 // is a concurrent modification of the set of buffers.
278 size_t num_cards() const { return _num_cards; }
279
280 // Get/Set the number of cards that triggers log processing.
281 // Log processing should be done when the number of cards exceeds the
282 // threshold.
283 void set_process_cards_threshold(size_t sz) {
284 _process_cards_threshold = sz;
285 }
286 size_t process_cards_threshold() const {
287 return _process_cards_threshold;
288 }
289 static const size_t ProcessCardsThresholdNever = SIZE_MAX;
290
291 // Notify the consumer if the number of buffers crossed the threshold
292 void notify_if_necessary();
293
294 void merge_bufferlists(G1RedirtyCardsQueueSet* src);
295
296 G1BufferNodeList take_all_completed_buffers();
297
298 // If there are more than stop_at cards in the completed buffers, pop
299 // a buffer, refine its contents, and return true. Otherwise return
300 // false.
301 //
302 // Stops processing a buffer if SuspendibleThreadSet::should_yield(),
303 // recording the incompletely processed buffer for later processing of
304 // the remainder.
305 //
306 // Increments *total_refined_cards by the number of cards processed and
307 // removed from the buffer.
308 bool refine_completed_buffer_concurrently(uint worker_id,
309 size_t stop_at,
310 size_t* total_refined_cards);
311
312 // If a full collection is happening, reset partial logs, and release
313 // completed ones: the full collection will make them all irrelevant.
314 void abandon_logs();
315
316 // If any threads have partial logs, add them to the global list of logs.
317 void concatenate_logs();
318
319 void set_max_cards(size_t m) {
320 _max_cards = m;
321 }
322 size_t max_cards() const {
323 return _max_cards;
324 }
325
326 void set_max_cards_padding(size_t padding) {
327 _max_cards_padding = padding;
328 }
329 size_t max_cards_padding() const {
330 return _max_cards_padding;
331 }
332
333 // Total dirty cards refined by mutator threads.
334 size_t total_mutator_refined_cards() const;
335 };
336
337 inline G1DirtyCardQueueSet* G1DirtyCardQueue::dirty_card_qset() const {
338 return static_cast<G1DirtyCardQueueSet*>(qset());
339 }
340
341 #endif // SHARE_GC_G1_G1DIRTYCARDQUEUE_HPP