1 /*
2 * Copyright (c) 2001, 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
25 #include "precompiled.hpp"
26 #include "gc/g1/g1CollectedHeap.inline.hpp"
27 #include "gc/g1/g1ConcurrentRefine.hpp"
28 #include "gc/g1/heapRegion.hpp"
29 #include "gc/g1/heapRegionManager.inline.hpp"
30 #include "gc/g1/heapRegionSet.inline.hpp"
31 #include "memory/allocation.hpp"
32
33 class MasterFreeRegionListChecker : public HeapRegionSetChecker {
34 public:
35 void check_mt_safety() {
36 // Master Free List MT safety protocol:
37 // (a) If we're at a safepoint, operations on the master free list
38 // should be invoked by either the VM thread (which will serialize
39 // them) or by the GC workers while holding the
40 // FreeList_lock.
41 // (b) If we're not at a safepoint, operations on the master free
42 // list should be invoked while holding the Heap_lock.
43
44 if (SafepointSynchronize::is_at_safepoint()) {
45 guarantee(Thread::current()->is_VM_thread() ||
46 FreeList_lock->owned_by_self(), "master free list MT safety protocol at a safepoint");
47 } else {
48 guarantee(Heap_lock->owned_by_self(), "master free list MT safety protocol outside a safepoint");
49 }
50 }
51 bool is_correct_type(HeapRegion* hr) { return hr->is_free(); }
52 const char* get_description() { return "Free Regions"; }
53 };
54
55 HeapRegionManager::HeapRegionManager() :
56 _regions(), _heap_mapper(NULL),
57 _prev_bitmap_mapper(NULL),
58 _next_bitmap_mapper(NULL),
59 _bot_mapper(NULL),
60 _cardtable_mapper(NULL),
61 _card_counts_mapper(NULL),
62 _free_list("Free list", new MasterFreeRegionListChecker()),
63 _available_map(mtGC),
64 _num_committed(0),
65 _allocated_heapregions_length(0)
66 { }
67
68 void HeapRegionManager::initialize(G1RegionToSpaceMapper* heap_storage,
69 G1RegionToSpaceMapper* prev_bitmap,
70 G1RegionToSpaceMapper* next_bitmap,
71 G1RegionToSpaceMapper* bot,
72 G1RegionToSpaceMapper* cardtable,
73 G1RegionToSpaceMapper* card_counts) {
74 _allocated_heapregions_length = 0;
75
76 _heap_mapper = heap_storage;
77
78 _prev_bitmap_mapper = prev_bitmap;
79 _next_bitmap_mapper = next_bitmap;
80
81 _bot_mapper = bot;
82 _cardtable_mapper = cardtable;
83
84 _card_counts_mapper = card_counts;
85
86 MemRegion reserved = heap_storage->reserved();
87 _regions.initialize(reserved.start(), reserved.end(), HeapRegion::GrainBytes);
88
89 _available_map.initialize(_regions.length());
90 }
91
92 bool HeapRegionManager::is_available(uint region) const {
93 return _available_map.at(region);
94 }
95
96 #ifdef ASSERT
97 bool HeapRegionManager::is_free(HeapRegion* hr) const {
98 return _free_list.contains(hr);
99 }
100 #endif
101
102 HeapRegion* HeapRegionManager::new_heap_region(uint hrm_index) {
103 G1CollectedHeap* g1h = G1CollectedHeap::heap();
104 HeapWord* bottom = g1h->bottom_addr_for_region(hrm_index);
105 MemRegion mr(bottom, bottom + HeapRegion::GrainWords);
106 assert(reserved().contains(mr), "invariant");
107 return g1h->new_heap_region(hrm_index, mr);
108 }
109
110 void HeapRegionManager::commit_regions(uint index, size_t num_regions, WorkGang* pretouch_gang) {
111 guarantee(num_regions > 0, "Must commit more than zero regions");
112 guarantee(_num_committed + num_regions <= max_length(), "Cannot commit more than the maximum amount of regions");
113
114 _num_committed += (uint)num_regions;
115
116 _heap_mapper->commit_regions(index, num_regions, pretouch_gang);
117
118 // Also commit auxiliary data
119 _prev_bitmap_mapper->commit_regions(index, num_regions, pretouch_gang);
120 _next_bitmap_mapper->commit_regions(index, num_regions, pretouch_gang);
121
122 _bot_mapper->commit_regions(index, num_regions, pretouch_gang);
123 _cardtable_mapper->commit_regions(index, num_regions, pretouch_gang);
124
125 _card_counts_mapper->commit_regions(index, num_regions, pretouch_gang);
126 }
127
128 void HeapRegionManager::uncommit_regions(uint start, size_t num_regions) {
129 guarantee(num_regions >= 1, "Need to specify at least one region to uncommit, tried to uncommit zero regions at %u", start);
130 guarantee(_num_committed >= num_regions, "pre-condition");
131
132 // Print before uncommitting.
133 if (G1CollectedHeap::heap()->hr_printer()->is_active()) {
134 for (uint i = start; i < start + num_regions; i++) {
135 HeapRegion* hr = at(i);
136 G1CollectedHeap::heap()->hr_printer()->uncommit(hr);
137 }
138 }
139
140 _num_committed -= (uint)num_regions;
141
142 _available_map.par_clear_range(start, start + num_regions, BitMap::unknown_range);
143 _heap_mapper->uncommit_regions(start, num_regions);
144
145 // Also uncommit auxiliary data
146 _prev_bitmap_mapper->uncommit_regions(start, num_regions);
147 _next_bitmap_mapper->uncommit_regions(start, num_regions);
148
149 _bot_mapper->uncommit_regions(start, num_regions);
150 _cardtable_mapper->uncommit_regions(start, num_regions);
151
152 _card_counts_mapper->uncommit_regions(start, num_regions);
153 }
154
155 void HeapRegionManager::make_regions_available(uint start, uint num_regions, WorkGang* pretouch_gang) {
156 guarantee(num_regions > 0, "No point in calling this for zero regions");
157 commit_regions(start, num_regions, pretouch_gang);
158 for (uint i = start; i < start + num_regions; i++) {
159 if (_regions.get_by_index(i) == NULL) {
160 HeapRegion* new_hr = new_heap_region(i);
161 OrderAccess::storestore();
162 _regions.set_by_index(i, new_hr);
163 _allocated_heapregions_length = MAX2(_allocated_heapregions_length, i + 1);
164 }
165 }
166
167 _available_map.par_set_range(start, start + num_regions, BitMap::unknown_range);
168
169 for (uint i = start; i < start + num_regions; i++) {
170 assert(is_available(i), "Just made region %u available but is apparently not.", i);
171 HeapRegion* hr = at(i);
172 if (G1CollectedHeap::heap()->hr_printer()->is_active()) {
173 G1CollectedHeap::heap()->hr_printer()->commit(hr);
174 }
175 HeapWord* bottom = G1CollectedHeap::heap()->bottom_addr_for_region(i);
176 MemRegion mr(bottom, bottom + HeapRegion::GrainWords);
177
178 hr->initialize(mr);
179 insert_into_free_list(at(i));
180 }
181 }
182
183 MemoryUsage HeapRegionManager::get_auxiliary_data_memory_usage() const {
184 size_t used_sz =
185 _prev_bitmap_mapper->committed_size() +
186 _next_bitmap_mapper->committed_size() +
187 _bot_mapper->committed_size() +
188 _cardtable_mapper->committed_size() +
189 _card_counts_mapper->committed_size();
190
191 size_t committed_sz =
192 _prev_bitmap_mapper->reserved_size() +
193 _next_bitmap_mapper->reserved_size() +
194 _bot_mapper->reserved_size() +
195 _cardtable_mapper->reserved_size() +
196 _card_counts_mapper->reserved_size();
197
198 return MemoryUsage(0, used_sz, committed_sz, committed_sz);
199 }
200
201 uint HeapRegionManager::expand_by(uint num_regions, WorkGang* pretouch_workers) {
202 return expand_at(0, num_regions, pretouch_workers);
203 }
204
205 uint HeapRegionManager::expand_at(uint start, uint num_regions, WorkGang* pretouch_workers) {
206 if (num_regions == 0) {
207 return 0;
208 }
209
210 uint cur = start;
211 uint idx_last_found = 0;
212 uint num_last_found = 0;
213
214 uint expanded = 0;
215
216 while (expanded < num_regions &&
217 (num_last_found = find_unavailable_from_idx(cur, &idx_last_found)) > 0) {
218 uint to_expand = MIN2(num_regions - expanded, num_last_found);
219 make_regions_available(idx_last_found, to_expand, pretouch_workers);
220 expanded += to_expand;
221 cur = idx_last_found + num_last_found + 1;
222 }
223
224 verify_optional();
225 return expanded;
226 }
227
228 uint HeapRegionManager::find_contiguous(size_t num, bool empty_only) {
229 uint found = 0;
230 size_t length_found = 0;
231 uint cur = 0;
232
233 while (length_found < num && cur < max_length()) {
234 HeapRegion* hr = _regions.get_by_index(cur);
235 if ((!empty_only && !is_available(cur)) || (is_available(cur) && hr != NULL && hr->is_empty())) {
236 // This region is a potential candidate for allocation into.
237 length_found++;
238 } else {
239 // This region is not a candidate. The next region is the next possible one.
240 found = cur + 1;
241 length_found = 0;
242 }
243 cur++;
244 }
245
246 if (length_found == num) {
247 for (uint i = found; i < (found + num); i++) {
248 HeapRegion* hr = _regions.get_by_index(i);
249 // sanity check
250 guarantee((!empty_only && !is_available(i)) || (is_available(i) && hr != NULL && hr->is_empty()),
251 "Found region sequence starting at " UINT32_FORMAT ", length " SIZE_FORMAT
252 " that is not empty at " UINT32_FORMAT ". Hr is " PTR_FORMAT, found, num, i, p2i(hr));
253 }
254 return found;
255 } else {
256 return G1_NO_HRM_INDEX;
257 }
258 }
259
260 HeapRegion* HeapRegionManager::next_region_in_heap(const HeapRegion* r) const {
261 guarantee(r != NULL, "Start region must be a valid region");
262 guarantee(is_available(r->hrm_index()), "Trying to iterate starting from region %u which is not in the heap", r->hrm_index());
263 for (uint i = r->hrm_index() + 1; i < _allocated_heapregions_length; i++) {
264 HeapRegion* hr = _regions.get_by_index(i);
265 if (is_available(i)) {
266 return hr;
267 }
268 }
269 return NULL;
270 }
271
272 void HeapRegionManager::iterate(HeapRegionClosure* blk) const {
273 uint len = max_length();
274
275 for (uint i = 0; i < len; i++) {
276 if (!is_available(i)) {
277 continue;
278 }
279 guarantee(at(i) != NULL, "Tried to access region %u that has a NULL HeapRegion*", i);
280 bool res = blk->do_heap_region(at(i));
281 if (res) {
282 blk->set_incomplete();
283 return;
284 }
285 }
286 }
287
288 uint HeapRegionManager::find_unavailable_from_idx(uint start_idx, uint* res_idx) const {
289 guarantee(res_idx != NULL, "checking");
290 guarantee(start_idx <= (max_length() + 1), "checking");
291
292 uint num_regions = 0;
293
294 uint cur = start_idx;
295 while (cur < max_length() && is_available(cur)) {
296 cur++;
297 }
298 if (cur == max_length()) {
299 return num_regions;
300 }
301 *res_idx = cur;
302 while (cur < max_length() && !is_available(cur)) {
303 cur++;
304 }
305 num_regions = cur - *res_idx;
306 #ifdef ASSERT
307 for (uint i = *res_idx; i < (*res_idx + num_regions); i++) {
308 assert(!is_available(i), "just checking");
309 }
310 assert(cur == max_length() || num_regions == 0 || is_available(cur),
311 "The region at the current position %u must be available or at the end of the heap.", cur);
312 #endif
313 return num_regions;
314 }
315
316 uint HeapRegionManager::find_highest_free(bool* expanded) {
317 // Loop downwards from the highest region index, looking for an
318 // entry which is either free or not yet committed. If not yet
319 // committed, expand_at that index.
320 uint curr = max_length() - 1;
321 while (true) {
322 HeapRegion *hr = _regions.get_by_index(curr);
323 if (hr == NULL) {
324 uint res = expand_at(curr, 1, NULL);
325 if (res == 1) {
326 *expanded = true;
327 return curr;
328 }
329 } else {
330 if (hr->is_free()) {
331 *expanded = false;
332 return curr;
333 }
334 }
335 if (curr == 0) {
336 return G1_NO_HRM_INDEX;
337 }
338 curr--;
339 }
340 }
341
342 bool HeapRegionManager::allocate_containing_regions(MemRegion range, size_t* commit_count, WorkGang* pretouch_workers) {
343 size_t commits = 0;
344 uint start_index = (uint)_regions.get_index_by_address(range.start());
345 uint last_index = (uint)_regions.get_index_by_address(range.last());
346
347 // Ensure that each G1 region in the range is free, returning false if not.
348 // Commit those that are not yet available, and keep count.
349 for (uint curr_index = start_index; curr_index <= last_index; curr_index++) {
350 if (!is_available(curr_index)) {
351 commits++;
352 expand_at(curr_index, 1, pretouch_workers);
353 }
354 HeapRegion* curr_region = _regions.get_by_index(curr_index);
355 if (!curr_region->is_free()) {
356 return false;
357 }
358 }
359
360 allocate_free_regions_starting_at(start_index, (last_index - start_index) + 1);
361 *commit_count = commits;
362 return true;
363 }
364
365 void HeapRegionManager::par_iterate(HeapRegionClosure* blk, HeapRegionClaimer* hrclaimer, const uint start_index) const {
366 // Every worker will actually look at all regions, skipping over regions that
367 // are currently not committed.
368 // This also (potentially) iterates over regions newly allocated during GC. This
369 // is no problem except for some extra work.
370 const uint n_regions = hrclaimer->n_regions();
371 for (uint count = 0; count < n_regions; count++) {
372 const uint index = (start_index + count) % n_regions;
373 assert(index < n_regions, "sanity");
374 // Skip over unavailable regions
375 if (!is_available(index)) {
376 continue;
377 }
378 HeapRegion* r = _regions.get_by_index(index);
379 // We'll ignore regions already claimed.
380 // However, if the iteration is specified as concurrent, the values for
381 // is_starts_humongous and is_continues_humongous can not be trusted,
382 // and we should just blindly iterate over regions regardless of their
383 // humongous status.
384 if (hrclaimer->is_region_claimed(index)) {
385 continue;
386 }
387 // OK, try to claim it
388 if (!hrclaimer->claim_region(index)) {
389 continue;
390 }
391 bool res = blk->do_heap_region(r);
392 if (res) {
393 return;
394 }
395 }
396 }
397
398 uint HeapRegionManager::shrink_by(uint num_regions_to_remove) {
399 assert(length() > 0, "the region sequence should not be empty");
400 assert(length() <= _allocated_heapregions_length, "invariant");
401 assert(_allocated_heapregions_length > 0, "we should have at least one region committed");
402 assert(num_regions_to_remove < length(), "We should never remove all regions");
403
404 if (num_regions_to_remove == 0) {
405 return 0;
406 }
407
408 uint removed = 0;
409 uint cur = _allocated_heapregions_length - 1;
410 uint idx_last_found = 0;
411 uint num_last_found = 0;
412
413 while ((removed < num_regions_to_remove) &&
414 (num_last_found = find_empty_from_idx_reverse(cur, &idx_last_found)) > 0) {
415 uint to_remove = MIN2(num_regions_to_remove - removed, num_last_found);
416
417 shrink_at(idx_last_found + num_last_found - to_remove, to_remove);
418
419 cur = idx_last_found;
420 removed += to_remove;
421 }
422
423 verify_optional();
424
425 return removed;
426 }
427
428 void HeapRegionManager::shrink_at(uint index, size_t num_regions) {
429 #ifdef ASSERT
430 for (uint i = index; i < (index + num_regions); i++) {
431 assert(is_available(i), "Expected available region at index %u", i);
432 assert(at(i)->is_empty(), "Expected empty region at index %u", i);
433 assert(at(i)->is_free(), "Expected free region at index %u", i);
434 }
435 #endif
436 uncommit_regions(index, num_regions);
437 }
438
439 uint HeapRegionManager::find_empty_from_idx_reverse(uint start_idx, uint* res_idx) const {
440 guarantee(start_idx < _allocated_heapregions_length, "checking");
441 guarantee(res_idx != NULL, "checking");
442
443 uint num_regions_found = 0;
444
445 jlong cur = start_idx;
446 while (cur != -1 && !(is_available(cur) && at(cur)->is_empty())) {
447 cur--;
448 }
449 if (cur == -1) {
450 return num_regions_found;
451 }
452 jlong old_cur = cur;
453 // cur indexes the first empty region
454 while (cur != -1 && is_available(cur) && at(cur)->is_empty()) {
455 cur--;
456 }
457 *res_idx = cur + 1;
458 num_regions_found = old_cur - cur;
459
460 #ifdef ASSERT
461 for (uint i = *res_idx; i < (*res_idx + num_regions_found); i++) {
462 assert(at(i)->is_empty(), "just checking");
463 }
464 #endif
465 return num_regions_found;
466 }
467
468 void HeapRegionManager::verify() {
469 guarantee(length() <= _allocated_heapregions_length,
470 "invariant: _length: %u _allocated_length: %u",
471 length(), _allocated_heapregions_length);
472 guarantee(_allocated_heapregions_length <= max_length(),
473 "invariant: _allocated_length: %u _max_length: %u",
474 _allocated_heapregions_length, max_length());
475
476 bool prev_committed = true;
477 uint num_committed = 0;
478 HeapWord* prev_end = heap_bottom();
479 for (uint i = 0; i < _allocated_heapregions_length; i++) {
480 if (!is_available(i)) {
481 prev_committed = false;
482 continue;
483 }
484 num_committed++;
485 HeapRegion* hr = _regions.get_by_index(i);
486 guarantee(hr != NULL, "invariant: i: %u", i);
487 guarantee(!prev_committed || hr->bottom() == prev_end,
488 "invariant i: %u " HR_FORMAT " prev_end: " PTR_FORMAT,
489 i, HR_FORMAT_PARAMS(hr), p2i(prev_end));
490 guarantee(hr->hrm_index() == i,
491 "invariant: i: %u hrm_index(): %u", i, hr->hrm_index());
492 // Asserts will fire if i is >= _length
493 HeapWord* addr = hr->bottom();
494 guarantee(addr_to_region(addr) == hr, "sanity");
495 // We cannot check whether the region is part of a particular set: at the time
496 // this method may be called, we have only completed allocation of the regions,
497 // but not put into a region set.
498 prev_committed = true;
499 prev_end = hr->end();
500 }
501 for (uint i = _allocated_heapregions_length; i < max_length(); i++) {
502 guarantee(_regions.get_by_index(i) == NULL, "invariant i: %u", i);
503 }
504
505 guarantee(num_committed == _num_committed, "Found %u committed regions, but should be %u", num_committed, _num_committed);
506 _free_list.verify();
507 }
508
509 #ifndef PRODUCT
510 void HeapRegionManager::verify_optional() {
511 verify();
512 }
513 #endif // PRODUCT
514
515 HeapRegionClaimer::HeapRegionClaimer(uint n_workers) :
516 _n_workers(n_workers), _n_regions(G1CollectedHeap::heap()->_hrm->_allocated_heapregions_length), _claims(NULL) {
517 assert(n_workers > 0, "Need at least one worker.");
518 uint* new_claims = NEW_C_HEAP_ARRAY(uint, _n_regions, mtGC);
519 memset(new_claims, Unclaimed, sizeof(*_claims) * _n_regions);
520 _claims = new_claims;
521 }
522
523 HeapRegionClaimer::~HeapRegionClaimer() {
524 if (_claims != NULL) {
525 FREE_C_HEAP_ARRAY(uint, _claims);
526 }
527 }
528
529 uint HeapRegionClaimer::offset_for_worker(uint worker_id) const {
530 assert(worker_id < _n_workers, "Invalid worker_id.");
531 return _n_regions * worker_id / _n_workers;
532 }
533
534 bool HeapRegionClaimer::is_region_claimed(uint region_index) const {
535 assert(region_index < _n_regions, "Invalid index.");
536 return _claims[region_index] == Claimed;
537 }
538
539 bool HeapRegionClaimer::claim_region(uint region_index) {
540 assert(region_index < _n_regions, "Invalid index.");
541 uint old_val = Atomic::cmpxchg(Claimed, &_claims[region_index], Unclaimed);
542 return old_val == Unclaimed;
543 }