56 void free(bm_word_t* map, idx_t size_in_words) const {
57 ArrayAllocator<bm_word_t>::free(map, size_in_words);
58 }
59 };
60
61 class ArenaBitMapAllocator : StackObj {
62 Arena* _arena;
63
64 public:
65 ArenaBitMapAllocator(Arena* arena) : _arena(arena) {}
66 bm_word_t* allocate(idx_t size_in_words) const {
67 return (bm_word_t*)_arena->Amalloc(size_in_words * BytesPerWord);
68 }
69 void free(bm_word_t* map, idx_t size_in_words) const {
70 // ArenaBitMaps currently don't free memory.
71 }
72 };
73
74 template <class Allocator>
75 BitMap::bm_word_t* BitMap::reallocate(const Allocator& allocator, bm_word_t* old_map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear) {
76 verify_max_size_limited(new_size_in_bits);
77 size_t old_size_in_words = calc_size_in_words(old_size_in_bits);
78 size_t new_size_in_words = calc_size_in_words(new_size_in_bits);
79
80 bm_word_t* map = NULL;
81
82 if (new_size_in_words > 0) {
83 map = allocator.allocate(new_size_in_words);
84
85 if (old_map != NULL) {
86 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) map,
87 MIN2(old_size_in_words, new_size_in_words));
88 }
89
90 if (clear && new_size_in_words > old_size_in_words) {
91 clear_range_of_words(map, old_size_in_words, new_size_in_words);
92 }
93 }
94
95 if (old_map != NULL) {
96 allocator.free(old_map, old_size_in_words);
158 : BitMap(allocate(CHeapBitMapAllocator(flags), size_in_bits, clear), size_in_bits), _flags(flags) {
159 }
160
161 CHeapBitMap::~CHeapBitMap() {
162 free(CHeapBitMapAllocator(_flags), map(), size());
163 }
164
165 void CHeapBitMap::resize(idx_t new_size_in_bits, bool clear) {
166 BitMap::resize(CHeapBitMapAllocator(_flags), new_size_in_bits, clear);
167 }
168
169 void CHeapBitMap::initialize(idx_t size_in_bits, bool clear) {
170 BitMap::initialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
171 }
172
173 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
174 BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
175 }
176
177 #ifdef ASSERT
178 void BitMap::verify_max_size_limited(idx_t bit) {
179 assert(bit <= max_size_in_bits(), "out of bounds: " SIZE_FORMAT, bit);
180 }
181
182 void BitMap::verify_index(idx_t index) const {
183 assert(index < _size, "BitMap index out of bounds");
184 }
185
186 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
187 assert(beg_index <= end_index, "BitMap range error");
188 // Note that [0,0) and [size,size) are both valid ranges.
189 assert(end_index <= _size, "BitMap range out of bounds");
190 }
191 #endif // #ifdef ASSERT
192
193 void BitMap::pretouch() {
194 os::pretouch_memory(word_addr(0), word_addr(size()));
195 }
196
197 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
198 // With a valid range (beg <= end), this test ensures that end != 0, as
199 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
216 assert(value == 0 || value == 1, "0 for clear, 1 for set");
217 // With a valid range (beg <= end), this test ensures that end != 0, as
218 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
219 if (beg != end) {
220 bm_word_t* pw = word_addr(beg);
221 bm_word_t w = *pw;
222 bm_word_t mr = inverted_bit_mask_for_range(beg, end);
223 bm_word_t nw = value ? (w | ~mr) : (w & mr);
224 while (true) {
225 bm_word_t res = Atomic::cmpxchg(nw, pw, w);
226 if (res == w) break;
227 w = res;
228 nw = value ? (w | ~mr) : (w & mr);
229 }
230 }
231 }
232
233 void BitMap::set_range(idx_t beg, idx_t end) {
234 verify_range(beg, end);
235
236 idx_t beg_full_word = word_index_round_up(beg);
237 idx_t end_full_word = word_index(end);
238
239 if (beg_full_word < end_full_word) {
240 // The range includes at least one full word.
241 set_range_within_word(beg, bit_index(beg_full_word));
242 set_range_of_words(beg_full_word, end_full_word);
243 set_range_within_word(bit_index(end_full_word), end);
244 } else {
245 // The range spans at most 2 partial words.
246 idx_t boundary = MIN2(bit_index(beg_full_word), end);
247 set_range_within_word(beg, boundary);
248 set_range_within_word(boundary, end);
249 }
250 }
251
252 void BitMap::clear_range(idx_t beg, idx_t end) {
253 verify_range(beg, end);
254
255 idx_t beg_full_word = word_index_round_up(beg);
256 idx_t end_full_word = word_index(end);
257
258 if (beg_full_word < end_full_word) {
259 // The range includes at least one full word.
260 clear_range_within_word(beg, bit_index(beg_full_word));
261 clear_range_of_words(beg_full_word, end_full_word);
262 clear_range_within_word(bit_index(end_full_word), end);
263 } else {
264 // The range spans at most 2 partial words.
265 idx_t boundary = MIN2(bit_index(beg_full_word), end);
266 clear_range_within_word(beg, boundary);
267 clear_range_within_word(boundary, end);
268 }
269 }
270
271 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
272 // There is little point to call large version on small ranges.
273 // Need to check carefully, keeping potential idx_t underflow in mind.
274 // The threshold should be at least one word.
275 STATIC_ASSERT(small_range_words >= 1);
276 return (beg_full_word + small_range_words >= end_full_word);
277 }
278
279 void BitMap::set_large_range(idx_t beg, idx_t end) {
280 verify_range(beg, end);
281
282 idx_t beg_full_word = word_index_round_up(beg);
283 idx_t end_full_word = word_index(end);
284
285 if (is_small_range_of_words(beg_full_word, end_full_word)) {
286 set_range(beg, end);
287 return;
288 }
289
290 // The range includes at least one full word.
291 set_range_within_word(beg, bit_index(beg_full_word));
292 set_large_range_of_words(beg_full_word, end_full_word);
293 set_range_within_word(bit_index(end_full_word), end);
294 }
295
296 void BitMap::clear_large_range(idx_t beg, idx_t end) {
297 verify_range(beg, end);
298
299 idx_t beg_full_word = word_index_round_up(beg);
300 idx_t end_full_word = word_index(end);
301
302 if (is_small_range_of_words(beg_full_word, end_full_word)) {
303 clear_range(beg, end);
304 return;
305 }
306
307 // The range includes at least one full word.
308 clear_range_within_word(beg, bit_index(beg_full_word));
309 clear_large_range_of_words(beg_full_word, end_full_word);
310 clear_range_within_word(bit_index(end_full_word), end);
311 }
312
313 void BitMap::at_put(idx_t offset, bool value) {
314 if (value) {
315 set_bit(offset);
316 } else {
317 clear_bit(offset);
318 }
319 }
320
321 // Return true to indicate that this thread changed
322 // the bit, false to indicate that someone else did.
323 // In either case, the requested bit is in the
324 // requested state some time during the period that
325 // this thread is executing this call. More importantly,
326 // if no other thread is executing an action to
327 // change the requested bit to a state other than
328 // the one that this thread is trying to set it to,
329 // then the the bit is in the expected state
330 // at exit from this method. However, rather than
331 // make such a strong assertion here, based on
332 // assuming such constrained use (which though true
333 // today, could change in the future to service some
334 // funky parallel algorithm), we encourage callers
335 // to do such verification, as and when appropriate.
336 bool BitMap::par_at_put(idx_t bit, bool value) {
337 return value ? par_set_bit(bit) : par_clear_bit(bit);
338 }
339
340 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
341 if (value) {
342 set_range(start_offset, end_offset);
343 } else {
344 clear_range(start_offset, end_offset);
345 }
346 }
347
348 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
349 verify_range(beg, end);
350
351 idx_t beg_full_word = word_index_round_up(beg);
352 idx_t end_full_word = word_index(end);
353
354 if (beg_full_word < end_full_word) {
355 // The range includes at least one full word.
356 par_put_range_within_word(beg, bit_index(beg_full_word), value);
357 if (value) {
358 set_range_of_words(beg_full_word, end_full_word);
359 } else {
360 clear_range_of_words(beg_full_word, end_full_word);
361 }
362 par_put_range_within_word(bit_index(end_full_word), end, value);
363 } else {
364 // The range spans at most 2 partial words.
365 idx_t boundary = MIN2(bit_index(beg_full_word), end);
366 par_put_range_within_word(beg, boundary, value);
367 par_put_range_within_word(boundary, end, value);
368 }
369
370 }
371
372 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
373 if (value) {
374 set_large_range(beg, end);
375 } else {
376 clear_large_range(beg, end);
377 }
378 }
379
380 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
381 verify_range(beg, end);
382
383 idx_t beg_full_word = word_index_round_up(beg);
384 idx_t end_full_word = word_index(end);
385
386 if (is_small_range_of_words(beg_full_word, end_full_word)) {
387 par_at_put_range(beg, end, value);
388 return;
389 }
390
391 // The range includes at least one full word.
392 par_put_range_within_word(beg, bit_index(beg_full_word), value);
393 if (value) {
394 set_large_range_of_words(beg_full_word, end_full_word);
395 } else {
396 clear_large_range_of_words(beg_full_word, end_full_word);
397 }
398 par_put_range_within_word(bit_index(end_full_word), end, value);
399 }
400
401 inline bm_word_t tail_mask(idx_t tail_bits) {
402 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
403 assert(tail_bits < (idx_t)BitsPerWord, "precondition");
404 return (bm_word_t(1) << tail_bits) - 1;
405 }
406
407 // Get the low tail_bits of value, which is the last partial word of a map.
408 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
409 return value & tail_mask(tail_bits);
410 }
411
412 // Compute the new last word of a map with a non-aligned length.
413 // new_value has the new trailing bits of the map in the low tail_bits.
414 // old_value is the last word of the map, including bits beyond the end.
415 // Returns old_value with the low tail_bits replaced by the corresponding
416 // bits in new_value.
417 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
418 bm_word_t old_value,
|
56 void free(bm_word_t* map, idx_t size_in_words) const {
57 ArrayAllocator<bm_word_t>::free(map, size_in_words);
58 }
59 };
60
61 class ArenaBitMapAllocator : StackObj {
62 Arena* _arena;
63
64 public:
65 ArenaBitMapAllocator(Arena* arena) : _arena(arena) {}
66 bm_word_t* allocate(idx_t size_in_words) const {
67 return (bm_word_t*)_arena->Amalloc(size_in_words * BytesPerWord);
68 }
69 void free(bm_word_t* map, idx_t size_in_words) const {
70 // ArenaBitMaps currently don't free memory.
71 }
72 };
73
74 template <class Allocator>
75 BitMap::bm_word_t* BitMap::reallocate(const Allocator& allocator, bm_word_t* old_map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear) {
76 size_t old_size_in_words = calc_size_in_words(old_size_in_bits);
77 size_t new_size_in_words = calc_size_in_words(new_size_in_bits);
78
79 bm_word_t* map = NULL;
80
81 if (new_size_in_words > 0) {
82 map = allocator.allocate(new_size_in_words);
83
84 if (old_map != NULL) {
85 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) map,
86 MIN2(old_size_in_words, new_size_in_words));
87 }
88
89 if (clear && new_size_in_words > old_size_in_words) {
90 clear_range_of_words(map, old_size_in_words, new_size_in_words);
91 }
92 }
93
94 if (old_map != NULL) {
95 allocator.free(old_map, old_size_in_words);
157 : BitMap(allocate(CHeapBitMapAllocator(flags), size_in_bits, clear), size_in_bits), _flags(flags) {
158 }
159
160 CHeapBitMap::~CHeapBitMap() {
161 free(CHeapBitMapAllocator(_flags), map(), size());
162 }
163
164 void CHeapBitMap::resize(idx_t new_size_in_bits, bool clear) {
165 BitMap::resize(CHeapBitMapAllocator(_flags), new_size_in_bits, clear);
166 }
167
168 void CHeapBitMap::initialize(idx_t size_in_bits, bool clear) {
169 BitMap::initialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
170 }
171
172 void CHeapBitMap::reinitialize(idx_t size_in_bits, bool clear) {
173 BitMap::reinitialize(CHeapBitMapAllocator(_flags), size_in_bits, clear);
174 }
175
176 #ifdef ASSERT
177 void BitMap::verify_valid_size(idx_t size_in_bits) {
178 assert(size_in_bits <= max_size_in_bits(),
179 "out of bounds: " SIZE_FORMAT, size_in_bits);
180 }
181
182 void BitMap::verify_index(idx_t index) const {
183 assert(index < _size, "BitMap index out of bounds");
184 }
185
186 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
187 assert(beg_index <= end_index, "BitMap range error");
188 // Note that [0,0) and [size,size) are both valid ranges.
189 assert(end_index <= _size, "BitMap range out of bounds");
190 }
191 #endif // #ifdef ASSERT
192
193 void BitMap::pretouch() {
194 os::pretouch_memory(word_addr(0), word_addr(size()));
195 }
196
197 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
198 // With a valid range (beg <= end), this test ensures that end != 0, as
199 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
216 assert(value == 0 || value == 1, "0 for clear, 1 for set");
217 // With a valid range (beg <= end), this test ensures that end != 0, as
218 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
219 if (beg != end) {
220 bm_word_t* pw = word_addr(beg);
221 bm_word_t w = *pw;
222 bm_word_t mr = inverted_bit_mask_for_range(beg, end);
223 bm_word_t nw = value ? (w | ~mr) : (w & mr);
224 while (true) {
225 bm_word_t res = Atomic::cmpxchg(nw, pw, w);
226 if (res == w) break;
227 w = res;
228 nw = value ? (w | ~mr) : (w & mr);
229 }
230 }
231 }
232
233 void BitMap::set_range(idx_t beg, idx_t end) {
234 verify_range(beg, end);
235
236 idx_t beg_aligned = range_begin_align_up(beg);
237 idx_t end_aligned = range_end_align_down(end);
238
239 if (beg_aligned < end_aligned) {
240 // The range includes at least one full word.
241 set_range_within_word(beg, beg_aligned);
242 set_range_of_words(word_index(beg_aligned), word_index(end_aligned));
243 set_range_within_word(end_aligned, end);
244 } else {
245 // The range spans at most 2 partial words.
246 idx_t boundary = MIN2(beg_aligned, end);
247 set_range_within_word(beg, boundary);
248 set_range_within_word(boundary, end);
249 }
250 }
251
252 void BitMap::clear_range(idx_t beg, idx_t end) {
253 verify_range(beg, end);
254
255 idx_t beg_aligned = range_begin_align_up(beg);
256 idx_t end_aligned = range_end_align_down(end);
257
258 if (beg_aligned < end_aligned) {
259 // The range includes at least one full word.
260 clear_range_within_word(beg, beg_aligned);
261 clear_range_of_words(word_index(beg_aligned), word_index(end_aligned));
262 clear_range_within_word(end_aligned, end);
263 } else {
264 // The range spans at most 2 partial words.
265 idx_t boundary = MIN2(beg_aligned, end);
266 clear_range_within_word(beg, boundary);
267 clear_range_within_word(boundary, end);
268 }
269 }
270
271 bool BitMap::is_small_aligned_range(idx_t beg_aligned, idx_t end_aligned) {
272 // There is little point to call large version on small ranges.
273 // Need to check carefully, keeping potential idx_t over/underflow in mind,
274 // because beg_aligned > end_aligned can occur when beg and end are in the
275 // same word.
276 // The threshold should be at least one word.
277 STATIC_ASSERT(small_range_words >= 1);
278 return word_index(beg_aligned) + small_range_words >= word_index(end_aligned);
279 }
280
281 void BitMap::set_large_range(idx_t beg, idx_t end) {
282 verify_range(beg, end);
283
284 idx_t beg_aligned = range_begin_align_up(beg);
285 idx_t end_aligned = range_end_align_down(end);
286
287 if (is_small_aligned_range(beg_aligned, end_aligned)) {
288 set_range(beg, end);
289 return;
290 }
291
292 // The range includes at least one full word.
293 set_range_within_word(beg, beg_aligned);
294 set_large_range_of_words(word_index(beg_aligned), word_index(end_aligned));
295 set_range_within_word(end_aligned, end);
296 }
297
298 void BitMap::clear_large_range(idx_t beg, idx_t end) {
299 verify_range(beg, end);
300
301 idx_t beg_aligned = range_begin_align_up(beg);
302 idx_t end_aligned = range_end_align_down(end);
303
304 if (is_small_aligned_range(beg_aligned, end_aligned)) {
305 clear_range(beg, end);
306 return;
307 }
308
309 // The range includes at least one full word.
310 clear_range_within_word(beg, beg_aligned);
311 clear_large_range_of_words(word_index(beg_aligned), word_index(end_aligned));
312 clear_range_within_word(end_aligned, end);
313 }
314
315 void BitMap::at_put(idx_t offset, bool value) {
316 if (value) {
317 set_bit(offset);
318 } else {
319 clear_bit(offset);
320 }
321 }
322
323 // Return true to indicate that this thread changed
324 // the bit, false to indicate that someone else did.
325 // In either case, the requested bit is in the
326 // requested state some time during the period that
327 // this thread is executing this call. More importantly,
328 // if no other thread is executing an action to
329 // change the requested bit to a state other than
330 // the one that this thread is trying to set it to,
331 // then the the bit is in the expected state
332 // at exit from this method. However, rather than
333 // make such a strong assertion here, based on
334 // assuming such constrained use (which though true
335 // today, could change in the future to service some
336 // funky parallel algorithm), we encourage callers
337 // to do such verification, as and when appropriate.
338 bool BitMap::par_at_put(idx_t bit, bool value) {
339 return value ? par_set_bit(bit) : par_clear_bit(bit);
340 }
341
342 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
343 if (value) {
344 set_range(start_offset, end_offset);
345 } else {
346 clear_range(start_offset, end_offset);
347 }
348 }
349
350 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
351 verify_range(beg, end);
352
353 idx_t beg_aligned = range_begin_align_up(beg);
354 idx_t end_aligned = range_end_align_down(end);
355
356 if (beg_aligned < end_aligned) {
357 // The range includes at least one full word.
358 par_put_range_within_word(beg, beg_aligned, value);
359 idx_t beg_full_word = word_index(beg_aligned);
360 idx_t end_full_word = word_index(end_aligned);
361 if (value) {
362 set_range_of_words(beg_full_word, end_full_word);
363 } else {
364 clear_range_of_words(beg_full_word, end_full_word);
365 }
366 par_put_range_within_word(end_aligned, end, value);
367 } else {
368 // The range spans at most 2 partial words.
369 idx_t boundary = MIN2(beg_aligned, end);
370 par_put_range_within_word(beg, boundary, value);
371 par_put_range_within_word(boundary, end, value);
372 }
373
374 }
375
376 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
377 if (value) {
378 set_large_range(beg, end);
379 } else {
380 clear_large_range(beg, end);
381 }
382 }
383
384 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
385 verify_range(beg, end);
386
387 idx_t beg_aligned = range_begin_align_up(beg);
388 idx_t end_aligned = range_end_align_down(end);
389
390 if (is_small_aligned_range(beg_aligned, end_aligned)) {
391 par_at_put_range(beg, end, value);
392 return;
393 }
394
395 // The range includes at least one full word.
396 par_put_range_within_word(beg, beg_aligned, value);
397 idx_t beg_full_word = word_index(beg_aligned);
398 idx_t end_full_word = word_index(end_aligned);
399 if (value) {
400 set_large_range_of_words(beg_full_word, end_full_word);
401 } else {
402 clear_large_range_of_words(beg_full_word, end_full_word);
403 }
404 par_put_range_within_word(end_aligned, end, value);
405 }
406
407 inline bm_word_t tail_mask(idx_t tail_bits) {
408 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
409 assert(tail_bits < (idx_t)BitsPerWord, "precondition");
410 return (bm_word_t(1) << tail_bits) - 1;
411 }
412
413 // Get the low tail_bits of value, which is the last partial word of a map.
414 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
415 return value & tail_mask(tail_bits);
416 }
417
418 // Compute the new last word of a map with a non-aligned length.
419 // new_value has the new trailing bits of the map in the low tail_bits.
420 // old_value is the last word of the map, including bits beyond the end.
421 // Returns old_value with the low tail_bits replaced by the corresponding
422 // bits in new_value.
423 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
424 bm_word_t old_value,
|