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