rev 9846 : [mq]: par-scav-patch rev 9847 : 8146987: Improve Parallel GC Full GC by caching results of live_words_in_range() Summary: A large part of time in the parallel scavenge collector is spent finding out the amount of live words within memory ranges to find out where to move an object to. Try to incrementally calculate this value. Reviewed-by: tschatzl, mgerdin Contributed-by: ray alex <sky1young@gmail.com>
1 /* 2 * Copyright (c) 2005, 2016, 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/parallel/parMarkBitMap.hpp" 27 #include "gc/parallel/psCompactionManager.inline.hpp" 28 #include "gc/parallel/psParallelCompact.hpp" 29 #include "oops/oop.inline.hpp" 30 #include "runtime/atomic.inline.hpp" 31 #include "runtime/os.hpp" 32 #include "services/memTracker.hpp" 33 #include "utilities/bitMap.inline.hpp" 34 35 bool 36 ParMarkBitMap::initialize(MemRegion covered_region) 37 { 38 const idx_t bits = bits_required(covered_region); 39 // The bits will be divided evenly between two bitmaps; each of them should be 40 // an integral number of words. 41 assert(bits % (BitsPerWord * 2) == 0, "region size unaligned"); 42 43 const size_t words = bits / BitsPerWord; 44 const size_t raw_bytes = words * sizeof(idx_t); 45 const size_t page_sz = os::page_size_for_region_aligned(raw_bytes, 10); 46 const size_t granularity = os::vm_allocation_granularity(); 47 _reserved_byte_size = align_size_up(raw_bytes, MAX2(page_sz, granularity)); 48 49 const size_t rs_align = page_sz == (size_t) os::vm_page_size() ? 0 : 50 MAX2(page_sz, granularity); 51 ReservedSpace rs(_reserved_byte_size, rs_align, rs_align > 0); 52 os::trace_page_sizes("par bitmap", raw_bytes, raw_bytes, page_sz, 53 rs.base(), rs.size()); 54 55 MemTracker::record_virtual_memory_type((address)rs.base(), mtGC); 56 57 _virtual_space = new PSVirtualSpace(rs, page_sz); 58 if (_virtual_space != NULL && _virtual_space->expand_by(_reserved_byte_size)) { 59 _region_start = covered_region.start(); 60 _region_size = covered_region.word_size(); 61 BitMap::bm_word_t* map = (BitMap::bm_word_t*)_virtual_space->reserved_low_addr(); 62 _beg_bits.set_map(map); 63 _beg_bits.set_size(bits / 2); 64 _end_bits.set_map(map + words / 2); 65 _end_bits.set_size(bits / 2); 66 return true; 67 } 68 69 _region_start = 0; 70 _region_size = 0; 71 if (_virtual_space != NULL) { 72 delete _virtual_space; 73 _virtual_space = NULL; 74 // Release memory reserved in the space. 75 rs.release(); 76 } 77 return false; 78 } 79 80 #ifdef ASSERT 81 extern size_t mark_bitmap_count; 82 extern size_t mark_bitmap_size; 83 #endif // #ifdef ASSERT 84 85 bool 86 ParMarkBitMap::mark_obj(HeapWord* addr, size_t size) 87 { 88 const idx_t beg_bit = addr_to_bit(addr); 89 if (_beg_bits.par_set_bit(beg_bit)) { 90 const idx_t end_bit = addr_to_bit(addr + size - 1); 91 bool end_bit_ok = _end_bits.par_set_bit(end_bit); 92 assert(end_bit_ok, "concurrency problem"); 93 DEBUG_ONLY(Atomic::inc_ptr(&mark_bitmap_count)); 94 DEBUG_ONLY(Atomic::add_ptr(size, &mark_bitmap_size)); 95 return true; 96 } 97 return false; 98 } 99 100 inline bool 101 ParMarkBitMap::is_live_words_in_range_in_cache(ParCompactionManager* cm, HeapWord* beg_addr) const { 102 return cm->last_query_begin() == beg_addr; 103 } 104 105 inline void 106 ParMarkBitMap::update_live_words_in_range_cache(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj, size_t result) const { 107 cm->set_last_query_begin(beg_addr); 108 cm->set_last_query_object(end_obj); 109 cm->set_last_query_return(result); 110 } 111 112 size_t 113 ParMarkBitMap::live_words_in_range_helper(HeapWord* beg_addr, oop end_obj) const 114 { 115 assert(beg_addr <= (HeapWord*)end_obj, "bad range"); 116 assert(is_marked(end_obj), "end_obj must be live"); 117 118 idx_t live_bits = 0; 119 120 // The bitmap routines require the right boundary to be word-aligned. 121 const idx_t end_bit = addr_to_bit((HeapWord*)end_obj); 122 const idx_t range_end = BitMap::word_align_up(end_bit); 123 124 idx_t beg_bit = find_obj_beg(addr_to_bit(beg_addr), range_end); 125 while (beg_bit < end_bit) { 126 idx_t tmp_end = find_obj_end(beg_bit, range_end); 127 assert(tmp_end < end_bit, "missing end bit"); 128 live_bits += tmp_end - beg_bit + 1; 129 beg_bit = find_obj_beg(tmp_end + 1, range_end); 130 } 131 return bits_to_words(live_bits); 132 } 133 134 size_t 135 ParMarkBitMap::live_words_in_range_use_cache(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj) const 136 { 137 HeapWord* last_beg = cm->last_query_begin(); 138 oop last_obj = cm->last_query_object(); 139 size_t last_ret = cm->last_query_return(); 140 if (end_obj > last_obj) { 141 last_ret = last_ret + live_words_in_range_helper((HeapWord*)last_obj, end_obj); 142 last_obj = end_obj; 143 } else if (end_obj < last_obj) { 144 if (pointer_delta((HeapWord*)end_obj, (HeapWord*)beg_addr) > pointer_delta((HeapWord*)last_obj, (HeapWord*)end_obj)) { 145 last_ret = last_ret - live_words_in_range_helper((HeapWord*)end_obj, last_obj); 146 } else { 147 last_ret = live_words_in_range_helper(beg_addr, end_obj); 148 } 149 last_obj = end_obj; 150 } 151 152 update_live_words_in_range_cache(cm, last_beg, last_obj, last_ret); 153 return last_ret; 154 } 155 156 size_t 157 ParMarkBitMap::live_words_in_range(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj) const 158 { 159 // Try to reuse result from ParCompactionManager cache first. 160 if (is_live_words_in_range_in_cache(cm, beg_addr)) { 161 return live_words_in_range_use_cache(cm, beg_addr, end_obj); 162 } 163 size_t ret = live_words_in_range_helper(beg_addr, end_obj); 164 update_live_words_in_range_cache(cm, beg_addr, end_obj, ret); 165 return ret; 166 } 167 168 ParMarkBitMap::IterationStatus 169 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure, 170 idx_t range_beg, idx_t range_end) const 171 { 172 DEBUG_ONLY(verify_bit(range_beg);) 173 DEBUG_ONLY(verify_bit(range_end);) 174 assert(range_beg <= range_end, "live range invalid"); 175 176 // The bitmap routines require the right boundary to be word-aligned. 177 const idx_t search_end = BitMap::word_align_up(range_end); 178 179 idx_t cur_beg = find_obj_beg(range_beg, search_end); 180 while (cur_beg < range_end) { 181 const idx_t cur_end = find_obj_end(cur_beg, search_end); 182 if (cur_end >= range_end) { 183 // The obj ends outside the range. 184 live_closure->set_source(bit_to_addr(cur_beg)); 185 return incomplete; 186 } 187 188 const size_t size = obj_size(cur_beg, cur_end); 189 IterationStatus status = live_closure->do_addr(bit_to_addr(cur_beg), size); 190 if (status != incomplete) { 191 assert(status == would_overflow || status == full, "sanity"); 192 return status; 193 } 194 195 // Successfully processed the object; look for the next object. 196 cur_beg = find_obj_beg(cur_end + 1, search_end); 197 } 198 199 live_closure->set_source(bit_to_addr(range_end)); 200 return complete; 201 } 202 203 ParMarkBitMap::IterationStatus 204 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure, 205 ParMarkBitMapClosure* dead_closure, 206 idx_t range_beg, idx_t range_end, 207 idx_t dead_range_end) const 208 { 209 DEBUG_ONLY(verify_bit(range_beg);) 210 DEBUG_ONLY(verify_bit(range_end);) 211 DEBUG_ONLY(verify_bit(dead_range_end);) 212 assert(range_beg <= range_end, "live range invalid"); 213 assert(range_end <= dead_range_end, "dead range invalid"); 214 215 // The bitmap routines require the right boundary to be word-aligned. 216 const idx_t live_search_end = BitMap::word_align_up(range_end); 217 const idx_t dead_search_end = BitMap::word_align_up(dead_range_end); 218 219 idx_t cur_beg = range_beg; 220 if (range_beg < range_end && is_unmarked(range_beg)) { 221 // The range starts with dead space. Look for the next object, then fill. 222 cur_beg = find_obj_beg(range_beg + 1, dead_search_end); 223 const idx_t dead_space_end = MIN2(cur_beg - 1, dead_range_end - 1); 224 const size_t size = obj_size(range_beg, dead_space_end); 225 dead_closure->do_addr(bit_to_addr(range_beg), size); 226 } 227 228 while (cur_beg < range_end) { 229 const idx_t cur_end = find_obj_end(cur_beg, live_search_end); 230 if (cur_end >= range_end) { 231 // The obj ends outside the range. 232 live_closure->set_source(bit_to_addr(cur_beg)); 233 return incomplete; 234 } 235 236 const size_t size = obj_size(cur_beg, cur_end); 237 IterationStatus status = live_closure->do_addr(bit_to_addr(cur_beg), size); 238 if (status != incomplete) { 239 assert(status == would_overflow || status == full, "sanity"); 240 return status; 241 } 242 243 // Look for the start of the next object. 244 const idx_t dead_space_beg = cur_end + 1; 245 cur_beg = find_obj_beg(dead_space_beg, dead_search_end); 246 if (cur_beg > dead_space_beg) { 247 // Found dead space; compute the size and invoke the dead closure. 248 const idx_t dead_space_end = MIN2(cur_beg - 1, dead_range_end - 1); 249 const size_t size = obj_size(dead_space_beg, dead_space_end); 250 dead_closure->do_addr(bit_to_addr(dead_space_beg), size); 251 } 252 } 253 254 live_closure->set_source(bit_to_addr(range_end)); 255 return complete; 256 } 257 258 #ifdef ASSERT 259 void ParMarkBitMap::verify_clear() const 260 { 261 const idx_t* const beg = (const idx_t*)_virtual_space->committed_low_addr(); 262 const idx_t* const end = (const idx_t*)_virtual_space->committed_high_addr(); 263 for (const idx_t* p = beg; p < end; ++p) { 264 assert(*p == 0, "bitmap not clear"); 265 } 266 } 267 #endif // #ifdef ASSERT --- EOF ---