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 #ifndef SHARE_VM_GC_PARALLEL_PARMARKBITMAP_HPP 26 #define SHARE_VM_GC_PARALLEL_PARMARKBITMAP_HPP 27 28 #include "memory/memRegion.hpp" 29 #include "oops/oop.hpp" 30 #include "utilities/bitMap.hpp" 31 32 class ParMarkBitMapClosure; 33 class PSVirtualSpace; 34 class ParCompactionManager; 35 36 class ParMarkBitMap: public CHeapObj<mtGC> 37 { 38 public: 39 typedef BitMap::idx_t idx_t; 40 41 // Values returned by the iterate() methods. 42 enum IterationStatus { incomplete, complete, full, would_overflow }; 43 44 inline ParMarkBitMap(); 45 bool initialize(MemRegion covered_region); 46 47 // Atomically mark an object as live. 48 bool mark_obj(HeapWord* addr, size_t size); 49 inline bool mark_obj(oop obj, int size); 50 51 // Return whether the specified begin or end bit is set. 52 inline bool is_obj_beg(idx_t bit) const; 53 inline bool is_obj_end(idx_t bit) const; 54 55 // Traditional interface for testing whether an object is marked or not (these 56 // test only the begin bits). 57 inline bool is_marked(idx_t bit) const; 58 inline bool is_marked(HeapWord* addr) const; 59 inline bool is_marked(oop obj) const; 60 61 inline bool is_unmarked(idx_t bit) const; 62 inline bool is_unmarked(HeapWord* addr) const; 63 inline bool is_unmarked(oop obj) const; 64 65 // Convert sizes from bits to HeapWords and back. An object that is n bits 66 // long will be bits_to_words(n) words long. An object that is m words long 67 // will take up words_to_bits(m) bits in the bitmap. 68 inline static size_t bits_to_words(idx_t bits); 69 inline static idx_t words_to_bits(size_t words); 70 71 // Return the size in words of an object given a begin bit and an end bit, or 72 // the equivalent beg_addr and end_addr. 73 inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const; 74 inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const; 75 76 // Return the size in words of the object (a search is done for the end bit). 77 inline size_t obj_size(idx_t beg_bit) const; 78 inline size_t obj_size(HeapWord* addr) const; 79 80 // Apply live_closure to each live object that lies completely within the 81 // range [live_range_beg, live_range_end). This is used to iterate over the 82 // compacted region of the heap. Return values: 83 // 84 // incomplete The iteration is not complete. The last object that 85 // begins in the range does not end in the range; 86 // closure->source() is set to the start of that object. 87 // 88 // complete The iteration is complete. All objects in the range 89 // were processed and the closure is not full; 90 // closure->source() is set one past the end of the range. 91 // 92 // full The closure is full; closure->source() is set to one 93 // past the end of the last object processed. 94 // 95 // would_overflow The next object in the range would overflow the closure; 96 // closure->source() is set to the start of that object. 97 IterationStatus iterate(ParMarkBitMapClosure* live_closure, 98 idx_t range_beg, idx_t range_end) const; 99 inline IterationStatus iterate(ParMarkBitMapClosure* live_closure, 100 HeapWord* range_beg, 101 HeapWord* range_end) const; 102 103 // Apply live closure as above and additionally apply dead_closure to all dead 104 // space in the range [range_beg, dead_range_end). Note that dead_range_end 105 // must be >= range_end. This is used to iterate over the dense prefix. 106 // 107 // This method assumes that if the first bit in the range (range_beg) is not 108 // marked, then dead space begins at that point and the dead_closure is 109 // applied. Thus callers must ensure that range_beg is not in the middle of a 110 // live object. 111 IterationStatus iterate(ParMarkBitMapClosure* live_closure, 112 ParMarkBitMapClosure* dead_closure, 113 idx_t range_beg, idx_t range_end, 114 idx_t dead_range_end) const; 115 inline IterationStatus iterate(ParMarkBitMapClosure* live_closure, 116 ParMarkBitMapClosure* dead_closure, 117 HeapWord* range_beg, 118 HeapWord* range_end, 119 HeapWord* dead_range_end) const; 120 121 // Return the number of live words in the range [beg_addr, end_obj) due to 122 // objects that start in the range. If a live object extends onto the range, 123 // the caller must detect and account for any live words due to that object. 124 // If a live object extends beyond the end of the range, only the words within 125 // the range are included in the result. The end of the range must be a live object, 126 // which is the case when updating pointers. This allows a branch to be removed 127 // from inside the loop. 128 size_t live_words_in_range(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj) const; 129 130 inline HeapWord* region_start() const; 131 inline HeapWord* region_end() const; 132 inline size_t region_size() const; 133 inline size_t size() const; 134 135 size_t reserved_byte_size() const { return _reserved_byte_size; } 136 137 // Convert a heap address to/from a bit index. 138 inline idx_t addr_to_bit(HeapWord* addr) const; 139 inline HeapWord* bit_to_addr(idx_t bit) const; 140 141 // Return the bit index of the first marked object that begins (or ends, 142 // respectively) in the range [beg, end). If no object is found, return end. 143 inline idx_t find_obj_beg(idx_t beg, idx_t end) const; 144 inline idx_t find_obj_end(idx_t beg, idx_t end) const; 145 146 inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const; 147 inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const; 148 149 // Clear a range of bits or the entire bitmap (both begin and end bits are 150 // cleared). 151 inline void clear_range(idx_t beg, idx_t end); 152 153 // Return the number of bits required to represent the specified number of 154 // HeapWords, or the specified region. 155 static inline idx_t bits_required(size_t words); 156 static inline idx_t bits_required(MemRegion covered_region); 157 158 void print_on_error(outputStream* st) const { 159 st->print_cr("Marking Bits: (ParMarkBitMap*) " PTR_FORMAT, p2i(this)); 160 _beg_bits.print_on_error(st, " Begin Bits: "); 161 _end_bits.print_on_error(st, " End Bits: "); 162 } 163 164 #ifdef ASSERT 165 void verify_clear() const; 166 inline void verify_bit(idx_t bit) const; 167 inline void verify_addr(HeapWord* addr) const; 168 #endif // #ifdef ASSERT 169 170 private: 171 size_t live_words_in_range_helper(HeapWord* beg_addr, oop end_obj) const; 172 173 bool is_live_words_in_range_in_cache(ParCompactionManager* cm, HeapWord* beg_addr) const; 174 size_t live_words_in_range_use_cache(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj) const; 175 void update_live_words_in_range_cache(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj, size_t result) const; 176 177 // Each bit in the bitmap represents one unit of 'object granularity.' Objects 178 // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit 179 // granularity is 2, 64-bit is 1. 180 static inline size_t obj_granularity() { return size_t(MinObjAlignment); } 181 static inline int obj_granularity_shift() { return LogMinObjAlignment; } 182 183 HeapWord* _region_start; 184 size_t _region_size; 185 BitMap _beg_bits; 186 BitMap _end_bits; 187 PSVirtualSpace* _virtual_space; 188 size_t _reserved_byte_size; 189 }; 190 191 inline ParMarkBitMap::ParMarkBitMap(): 192 _beg_bits(), _end_bits(), _region_start(NULL), _region_size(0), _virtual_space(NULL), _reserved_byte_size(0) 193 { } 194 195 inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end) 196 { 197 _beg_bits.clear_range(beg, end); 198 _end_bits.clear_range(beg, end); 199 } 200 201 inline ParMarkBitMap::idx_t 202 ParMarkBitMap::bits_required(size_t words) 203 { 204 // Need two bits (one begin bit, one end bit) for each unit of 'object 205 // granularity' in the heap. 206 return words_to_bits(words * 2); 207 } 208 209 inline ParMarkBitMap::idx_t 210 ParMarkBitMap::bits_required(MemRegion covered_region) 211 { 212 return bits_required(covered_region.word_size()); 213 } 214 215 inline HeapWord* 216 ParMarkBitMap::region_start() const 217 { 218 return _region_start; 219 } 220 221 inline HeapWord* 222 ParMarkBitMap::region_end() const 223 { 224 return region_start() + region_size(); 225 } 226 227 inline size_t 228 ParMarkBitMap::region_size() const 229 { 230 return _region_size; 231 } 232 233 inline size_t 234 ParMarkBitMap::size() const 235 { 236 return _beg_bits.size(); 237 } 238 239 inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const 240 { 241 return _beg_bits.at(bit); 242 } 243 244 inline bool ParMarkBitMap::is_obj_end(idx_t bit) const 245 { 246 return _end_bits.at(bit); 247 } 248 249 inline bool ParMarkBitMap::is_marked(idx_t bit) const 250 { 251 return is_obj_beg(bit); 252 } 253 254 inline bool ParMarkBitMap::is_marked(HeapWord* addr) const 255 { 256 return is_marked(addr_to_bit(addr)); 257 } 258 259 inline bool ParMarkBitMap::is_marked(oop obj) const 260 { 261 return is_marked((HeapWord*)obj); 262 } 263 264 inline bool ParMarkBitMap::is_unmarked(idx_t bit) const 265 { 266 return !is_marked(bit); 267 } 268 269 inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const 270 { 271 return !is_marked(addr); 272 } 273 274 inline bool ParMarkBitMap::is_unmarked(oop obj) const 275 { 276 return !is_marked(obj); 277 } 278 279 inline size_t 280 ParMarkBitMap::bits_to_words(idx_t bits) 281 { 282 return bits << obj_granularity_shift(); 283 } 284 285 inline ParMarkBitMap::idx_t 286 ParMarkBitMap::words_to_bits(size_t words) 287 { 288 return words >> obj_granularity_shift(); 289 } 290 291 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const 292 { 293 DEBUG_ONLY(verify_bit(beg_bit);) 294 DEBUG_ONLY(verify_bit(end_bit);) 295 return bits_to_words(end_bit - beg_bit + 1); 296 } 297 298 inline size_t 299 ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const 300 { 301 DEBUG_ONLY(verify_addr(beg_addr);) 302 DEBUG_ONLY(verify_addr(end_addr);) 303 return pointer_delta(end_addr, beg_addr) + obj_granularity(); 304 } 305 306 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const 307 { 308 const idx_t end_bit = _end_bits.get_next_one_offset_inline(beg_bit, size()); 309 assert(is_marked(beg_bit), "obj not marked"); 310 assert(end_bit < size(), "end bit missing"); 311 return obj_size(beg_bit, end_bit); 312 } 313 314 inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const 315 { 316 return obj_size(addr_to_bit(addr)); 317 } 318 319 inline ParMarkBitMap::IterationStatus 320 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure, 321 HeapWord* range_beg, 322 HeapWord* range_end) const 323 { 324 return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end)); 325 } 326 327 inline ParMarkBitMap::IterationStatus 328 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure, 329 ParMarkBitMapClosure* dead_closure, 330 HeapWord* range_beg, 331 HeapWord* range_end, 332 HeapWord* dead_range_end) const 333 { 334 return iterate(live_closure, dead_closure, 335 addr_to_bit(range_beg), addr_to_bit(range_end), 336 addr_to_bit(dead_range_end)); 337 } 338 339 inline bool 340 ParMarkBitMap::mark_obj(oop obj, int size) 341 { 342 return mark_obj((HeapWord*)obj, (size_t)size); 343 } 344 345 inline BitMap::idx_t 346 ParMarkBitMap::addr_to_bit(HeapWord* addr) const 347 { 348 DEBUG_ONLY(verify_addr(addr);) 349 return words_to_bits(pointer_delta(addr, region_start())); 350 } 351 352 inline HeapWord* 353 ParMarkBitMap::bit_to_addr(idx_t bit) const 354 { 355 DEBUG_ONLY(verify_bit(bit);) 356 return region_start() + bits_to_words(bit); 357 } 358 359 inline ParMarkBitMap::idx_t 360 ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const 361 { 362 return _beg_bits.get_next_one_offset_inline_aligned_right(beg, end); 363 } 364 365 inline ParMarkBitMap::idx_t 366 ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const 367 { 368 return _end_bits.get_next_one_offset_inline_aligned_right(beg, end); 369 } 370 371 inline HeapWord* 372 ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const 373 { 374 const idx_t beg_bit = addr_to_bit(beg); 375 const idx_t end_bit = addr_to_bit(end); 376 const idx_t search_end = BitMap::word_align_up(end_bit); 377 const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit); 378 return bit_to_addr(res_bit); 379 } 380 381 inline HeapWord* 382 ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const 383 { 384 const idx_t beg_bit = addr_to_bit(beg); 385 const idx_t end_bit = addr_to_bit(end); 386 const idx_t search_end = BitMap::word_align_up(end_bit); 387 const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit); 388 return bit_to_addr(res_bit); 389 } 390 391 #ifdef ASSERT 392 inline void ParMarkBitMap::verify_bit(idx_t bit) const { 393 // Allow one past the last valid bit; useful for loop bounds. 394 assert(bit <= _beg_bits.size(), "bit out of range"); 395 } 396 397 inline void ParMarkBitMap::verify_addr(HeapWord* addr) const { 398 // Allow one past the last valid address; useful for loop bounds. 399 assert(addr >= region_start(), 400 "addr too small, addr: " PTR_FORMAT " region start: " PTR_FORMAT, p2i(addr), p2i(region_start())); 401 assert(addr <= region_end(), 402 "addr too big, addr: " PTR_FORMAT " region end: " PTR_FORMAT, p2i(addr), p2i(region_end())); 403 } 404 #endif // #ifdef ASSERT 405 406 #endif // SHARE_VM_GC_PARALLEL_PARMARKBITMAP_HPP --- EOF ---