Mercurial > hg > truffle
annotate src/share/vm/utilities/bitMap.hpp @ 8733:9def4075da6d
8008079: G1: Add nextObject routine to CMBitMapRO and replace nextWord
Summary: Update the task local finger to the start of the next object when marking aborts, in order to avoid the redundant scanning of all 0's when the marking task restarts, if otherwise updating to the next word. In addition, reuse the routine nextObject() in routine iterate().
Reviewed-by: johnc, ysr
Contributed-by: tamao <tao.mao@oracle.com>
| author | tamao |
|---|---|
| date | Tue, 05 Mar 2013 15:36:56 -0800 |
| parents | 2a0172480595 |
| children | 7b835924c31c |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
5988
2a0172480595
7127697: G1: remove dead code after recent concurrent mark changes
tonyp
parents:
3771
diff
changeset
|
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_UTILITIES_BITMAP_HPP |
| 26 #define SHARE_VM_UTILITIES_BITMAP_HPP | |
| 27 | |
| 28 #include "memory/allocation.hpp" | |
| 29 #include "utilities/top.hpp" | |
| 30 | |
| 342 | 31 // Forward decl; |
| 32 class BitMapClosure; | |
| 0 | 33 |
| 342 | 34 // Operations for bitmaps represented as arrays of unsigned integers. |
| 35 // Bit offsets are numbered from 0 to size-1. | |
| 0 | 36 |
| 37 class BitMap VALUE_OBJ_CLASS_SPEC { | |
| 38 friend class BitMap2D; | |
| 39 | |
| 40 public: | |
| 41 typedef size_t idx_t; // Type used for bit and word indices. | |
| 342 | 42 typedef uintptr_t bm_word_t; // Element type of array that represents |
| 43 // the bitmap. | |
| 0 | 44 |
| 45 // Hints for range sizes. | |
| 46 typedef enum { | |
| 47 unknown_range, small_range, large_range | |
| 48 } RangeSizeHint; | |
| 49 | |
| 50 private: | |
| 342 | 51 bm_word_t* _map; // First word in bitmap |
| 52 idx_t _size; // Size of bitmap (in bits) | |
| 0 | 53 |
| 54 // Puts the given value at the given offset, using resize() to size | |
| 55 // the bitmap appropriately if needed using factor-of-two expansion. | |
| 56 void at_put_grow(idx_t index, bool value); | |
| 57 | |
| 58 protected: | |
| 59 // Return the position of bit within the word that contains it (e.g., if | |
| 60 // bitmap words are 32 bits, return a number 0 <= n <= 31). | |
| 61 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); } | |
| 62 | |
| 63 // Return a mask that will select the specified bit, when applied to the word | |
| 64 // containing the bit. | |
| 342 | 65 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); } |
| 0 | 66 |
| 67 // Return the index of the word containing the specified bit. | |
| 68 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; } | |
| 69 | |
| 70 // Return the bit number of the first bit in the specified word. | |
| 71 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; } | |
| 72 | |
| 73 // Return the array of bitmap words, or a specific word from it. | |
| 342 | 74 bm_word_t* map() const { return _map; } |
| 75 bm_word_t map(idx_t word) const { return _map[word]; } | |
| 0 | 76 |
| 77 // Return a pointer to the word containing the specified bit. | |
| 342 | 78 bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); } |
| 0 | 79 |
| 80 // Set a word to a specified value or to all ones; clear a word. | |
| 342 | 81 void set_word (idx_t word, bm_word_t val) { _map[word] = val; } |
| 0 | 82 void set_word (idx_t word) { set_word(word, ~(uintptr_t)0); } |
| 83 void clear_word(idx_t word) { _map[word] = 0; } | |
| 84 | |
| 85 // Utilities for ranges of bits. Ranges are half-open [beg, end). | |
| 86 | |
| 87 // Ranges within a single word. | |
| 342 | 88 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const; |
| 89 void set_range_within_word (idx_t beg, idx_t end); | |
| 90 void clear_range_within_word (idx_t beg, idx_t end); | |
| 91 void par_put_range_within_word (idx_t beg, idx_t end, bool value); | |
| 0 | 92 |
| 93 // Ranges spanning entire words. | |
| 342 | 94 void set_range_of_words (idx_t beg, idx_t end); |
| 95 void clear_range_of_words (idx_t beg, idx_t end); | |
| 96 void set_large_range_of_words (idx_t beg, idx_t end); | |
| 97 void clear_large_range_of_words (idx_t beg, idx_t end); | |
| 0 | 98 |
| 99 // The index of the first full word in a range. | |
| 342 | 100 idx_t word_index_round_up(idx_t bit) const; |
| 0 | 101 |
|
809
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
102 // Verification. |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
103 inline void verify_index(idx_t index) const NOT_DEBUG_RETURN; |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
104 inline void verify_range(idx_t beg_index, idx_t end_index) const |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
105 NOT_DEBUG_RETURN; |
| 0 | 106 |
|
809
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
107 // Statistics. |
| 342 | 108 static idx_t* _pop_count_table; |
| 109 static void init_pop_count_table(); | |
| 110 static idx_t num_set_bits(bm_word_t w); | |
| 111 static idx_t num_set_bits_from_table(unsigned char c); | |
| 0 | 112 |
| 113 public: | |
| 114 | |
| 115 // Constructs a bitmap with no map, and size 0. | |
| 116 BitMap() : _map(NULL), _size(0) {} | |
| 117 | |
| 342 | 118 // Constructs a bitmap with the given map and size. |
| 119 BitMap(bm_word_t* map, idx_t size_in_bits); | |
| 0 | 120 |
| 342 | 121 // Constructs an empty bitmap of the given size (that is, this clears the |
| 122 // new bitmap). Allocates the map array in resource area if | |
| 123 // "in_resource_area" is true, else in the C heap. | |
| 124 BitMap(idx_t size_in_bits, bool in_resource_area = true); | |
| 0 | 125 |
| 342 | 126 // Set the map and size. |
| 127 void set_map(bm_word_t* map) { _map = map; } | |
| 0 | 128 void set_size(idx_t size_in_bits) { _size = size_in_bits; } |
| 129 | |
| 342 | 130 // Allocates necessary data structure, either in the resource area |
| 131 // or in the C heap, as indicated by "in_resource_area." | |
| 0 | 132 // Preserves state currently in bit map by copying data. |
| 133 // Zeros any newly-addressable bits. | |
| 342 | 134 // If "in_resource_area" is false, frees the current map. |
| 135 // (Note that this assumes that all calls to "resize" on the same BitMap | |
| 136 // use the same value for "in_resource_area".) | |
| 137 void resize(idx_t size_in_bits, bool in_resource_area = true); | |
| 0 | 138 |
| 139 // Accessing | |
| 140 idx_t size() const { return _size; } | |
| 141 idx_t size_in_words() const { | |
| 142 return word_index(size() + BitsPerWord - 1); | |
| 143 } | |
| 144 | |
| 145 bool at(idx_t index) const { | |
| 146 verify_index(index); | |
| 147 return (*word_addr(index) & bit_mask(index)) != 0; | |
| 148 } | |
| 149 | |
| 150 // Align bit index up or down to the next bitmap word boundary, or check | |
| 151 // alignment. | |
| 152 static idx_t word_align_up(idx_t bit) { | |
| 153 return align_size_up(bit, BitsPerWord); | |
| 154 } | |
| 155 static idx_t word_align_down(idx_t bit) { | |
| 156 return align_size_down(bit, BitsPerWord); | |
| 157 } | |
| 158 static bool is_word_aligned(idx_t bit) { | |
| 159 return word_align_up(bit) == bit; | |
| 160 } | |
| 161 | |
| 162 // Set or clear the specified bit. | |
| 163 inline void set_bit(idx_t bit); | |
| 3771 | 164 inline void clear_bit(idx_t bit); |
| 0 | 165 |
| 166 // Atomically set or clear the specified bit. | |
| 3771 | 167 inline bool par_set_bit(idx_t bit); |
| 168 inline bool par_clear_bit(idx_t bit); | |
| 0 | 169 |
| 170 // Put the given value at the given offset. The parallel version | |
| 171 // will CAS the value into the bitmap and is quite a bit slower. | |
| 172 // The parallel version also returns a value indicating if the | |
| 173 // calling thread was the one that changed the value of the bit. | |
| 174 void at_put(idx_t index, bool value); | |
| 175 bool par_at_put(idx_t index, bool value); | |
| 176 | |
| 177 // Update a range of bits. Ranges are half-open [beg, end). | |
| 178 void set_range (idx_t beg, idx_t end); | |
| 179 void clear_range (idx_t beg, idx_t end); | |
| 180 void set_large_range (idx_t beg, idx_t end); | |
| 181 void clear_large_range (idx_t beg, idx_t end); | |
| 182 void at_put_range(idx_t beg, idx_t end, bool value); | |
| 183 void par_at_put_range(idx_t beg, idx_t end, bool value); | |
| 184 void at_put_large_range(idx_t beg, idx_t end, bool value); | |
| 185 void par_at_put_large_range(idx_t beg, idx_t end, bool value); | |
| 186 | |
| 187 // Update a range of bits, using a hint about the size. Currently only | |
| 188 // inlines the predominant case of a 1-bit range. Works best when hint is a | |
| 189 // compile-time constant. | |
| 342 | 190 void set_range(idx_t beg, idx_t end, RangeSizeHint hint); |
| 191 void clear_range(idx_t beg, idx_t end, RangeSizeHint hint); | |
| 192 void par_set_range(idx_t beg, idx_t end, RangeSizeHint hint); | |
| 193 void par_clear_range (idx_t beg, idx_t end, RangeSizeHint hint); | |
| 194 | |
| 0 | 195 // Clearing |
| 196 void clear_large(); | |
| 342 | 197 inline void clear(); |
| 0 | 198 |
| 342 | 199 // Iteration support. Returns "true" if the iteration completed, false |
| 200 // if the iteration terminated early (because the closure "blk" returned | |
| 201 // false). | |
| 202 bool iterate(BitMapClosure* blk, idx_t leftIndex, idx_t rightIndex); | |
| 203 bool iterate(BitMapClosure* blk) { | |
| 0 | 204 // call the version that takes an interval |
| 342 | 205 return iterate(blk, 0, size()); |
| 0 | 206 } |
| 207 | |
| 342 | 208 // Looking for 1's and 0's at indices equal to or greater than "l_index", |
| 209 // stopping if none has been found before "r_index", and returning | |
| 210 // "r_index" (which must be at most "size") in that case. | |
| 211 idx_t get_next_one_offset_inline (idx_t l_index, idx_t r_index) const; | |
| 212 idx_t get_next_zero_offset_inline(idx_t l_index, idx_t r_index) const; | |
| 213 | |
| 214 // Like "get_next_one_offset_inline", except requires that "r_index" is | |
| 215 // aligned to bitsizeof(bm_word_t). | |
| 216 idx_t get_next_one_offset_inline_aligned_right(idx_t l_index, | |
| 217 idx_t r_index) const; | |
| 218 | |
| 219 // Non-inline versionsof the above. | |
| 0 | 220 idx_t get_next_one_offset (idx_t l_index, idx_t r_index) const; |
| 221 idx_t get_next_zero_offset(idx_t l_index, idx_t r_index) const; | |
| 222 | |
| 223 idx_t get_next_one_offset(idx_t offset) const { | |
| 224 return get_next_one_offset(offset, size()); | |
| 225 } | |
| 226 idx_t get_next_zero_offset(idx_t offset) const { | |
| 227 return get_next_zero_offset(offset, size()); | |
| 228 } | |
| 229 | |
| 342 | 230 // Returns the number of bits set in the bitmap. |
| 231 idx_t count_one_bits() const; | |
| 0 | 232 |
| 233 // Set operations. | |
| 234 void set_union(BitMap bits); | |
| 235 void set_difference(BitMap bits); | |
| 236 void set_intersection(BitMap bits); | |
| 237 // Returns true iff "this" is a superset of "bits". | |
| 238 bool contains(const BitMap bits) const; | |
| 239 // Returns true iff "this and "bits" have a non-empty intersection. | |
| 240 bool intersects(const BitMap bits) const; | |
| 241 | |
| 242 // Returns result of whether this map changed | |
| 243 // during the operation | |
| 244 bool set_union_with_result(BitMap bits); | |
| 245 bool set_difference_with_result(BitMap bits); | |
| 246 bool set_intersection_with_result(BitMap bits); | |
| 247 | |
| 342 | 248 // Requires the submap of "bits" starting at offset to be at least as |
| 249 // large as "this". Modifies "this" to be the intersection of its | |
| 250 // current contents and the submap of "bits" starting at "offset" of the | |
| 251 // same length as "this." | |
| 252 // (For expedience, currently requires the offset to be aligned to the | |
| 253 // bitsize of a uintptr_t. This should go away in the future though it | |
| 254 // will probably remain a good case to optimize.) | |
| 255 void set_intersection_at_offset(BitMap bits, idx_t offset); | |
| 256 | |
| 0 | 257 void set_from(BitMap bits); |
| 258 | |
| 259 bool is_same(BitMap bits); | |
| 260 | |
| 261 // Test if all bits are set or cleared | |
| 262 bool is_full() const; | |
| 263 bool is_empty() const; | |
| 264 | |
| 265 | |
| 266 #ifndef PRODUCT | |
| 267 public: | |
| 268 // Printing | |
| 269 void print_on(outputStream* st) const; | |
| 270 #endif | |
| 271 }; | |
| 272 | |
| 273 // Convenience class wrapping BitMap which provides multiple bits per slot. | |
| 274 class BitMap2D VALUE_OBJ_CLASS_SPEC { | |
| 275 public: | |
| 342 | 276 typedef BitMap::idx_t idx_t; // Type used for bit and word indices. |
| 277 typedef BitMap::bm_word_t bm_word_t; // Element type of array that | |
| 278 // represents the bitmap. | |
| 0 | 279 private: |
| 280 BitMap _map; | |
| 281 idx_t _bits_per_slot; | |
| 282 | |
| 283 idx_t bit_index(idx_t slot_index, idx_t bit_within_slot_index) const { | |
| 284 return slot_index * _bits_per_slot + bit_within_slot_index; | |
| 285 } | |
| 286 | |
| 287 void verify_bit_within_slot_index(idx_t index) const { | |
| 288 assert(index < _bits_per_slot, "bit_within_slot index out of bounds"); | |
| 289 } | |
| 290 | |
| 291 public: | |
| 292 // Construction. bits_per_slot must be greater than 0. | |
| 342 | 293 BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot); |
| 0 | 294 |
| 295 // Allocates necessary data structure in resource area. bits_per_slot must be greater than 0. | |
| 296 BitMap2D(idx_t size_in_slots, idx_t bits_per_slot); | |
| 297 | |
| 298 idx_t size_in_bits() { | |
| 299 return _map.size(); | |
| 300 } | |
| 301 | |
| 302 // Returns number of full slots that have been allocated | |
| 303 idx_t size_in_slots() { | |
| 304 // Round down | |
| 305 return _map.size() / _bits_per_slot; | |
| 306 } | |
| 307 | |
| 308 bool is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) { | |
| 309 verify_bit_within_slot_index(bit_within_slot_index); | |
| 310 return (bit_index(slot_index, bit_within_slot_index) < size_in_bits()); | |
| 311 } | |
| 312 | |
| 313 bool at(idx_t slot_index, idx_t bit_within_slot_index) const { | |
| 314 verify_bit_within_slot_index(bit_within_slot_index); | |
| 315 return _map.at(bit_index(slot_index, bit_within_slot_index)); | |
| 316 } | |
| 317 | |
| 318 void set_bit(idx_t slot_index, idx_t bit_within_slot_index) { | |
| 319 verify_bit_within_slot_index(bit_within_slot_index); | |
| 320 _map.set_bit(bit_index(slot_index, bit_within_slot_index)); | |
| 321 } | |
| 322 | |
| 323 void clear_bit(idx_t slot_index, idx_t bit_within_slot_index) { | |
| 324 verify_bit_within_slot_index(bit_within_slot_index); | |
| 325 _map.clear_bit(bit_index(slot_index, bit_within_slot_index)); | |
| 326 } | |
| 327 | |
| 328 void at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) { | |
| 329 verify_bit_within_slot_index(bit_within_slot_index); | |
| 330 _map.at_put(bit_index(slot_index, bit_within_slot_index), value); | |
| 331 } | |
| 332 | |
| 333 void at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) { | |
| 334 verify_bit_within_slot_index(bit_within_slot_index); | |
| 335 _map.at_put_grow(bit_index(slot_index, bit_within_slot_index), value); | |
| 336 } | |
| 337 | |
| 342 | 338 void clear(); |
| 0 | 339 }; |
| 340 | |
| 342 | 341 // Closure for iterating over BitMaps |
| 0 | 342 |
| 342 | 343 class BitMapClosure VALUE_OBJ_CLASS_SPEC { |
| 344 public: | |
| 345 // Callback when bit in map is set. Should normally return "true"; | |
| 346 // return of false indicates that the bitmap iteration should terminate. | |
| 347 virtual bool do_bit(BitMap::idx_t offset) = 0; | |
| 348 }; | |
| 1972 | 349 |
| 350 #endif // SHARE_VM_UTILITIES_BITMAP_HPP |