1 /*
2 * Copyright (c) 1997, 2018, 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 *
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_index(idx_t index) const {
178 assert(index < _size, "BitMap index out of bounds");
179 }
180
181 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
182 assert(beg_index <= end_index, "BitMap range error");
183 // Note that [0,0) and [size,size) are both valid ranges.
184 if (end_index != _size) verify_index(end_index);
185 }
186 #endif // #ifdef ASSERT
187
188 void BitMap::pretouch() {
189 os::pretouch_memory(word_addr(0), word_addr(size()));
190 }
191
192 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
193 // With a valid range (beg <= end), this test ensures that end != 0, as
194 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
195 if (beg != end) {
196 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
197 *word_addr(beg) |= ~mask;
198 }
199 }
200
201 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
202 // With a valid range (beg <= end), this test ensures that end != 0, as
203 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
204 if (beg != end) {
211 assert(value == 0 || value == 1, "0 for clear, 1 for set");
212 // With a valid range (beg <= end), this test ensures that end != 0, as
213 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
214 if (beg != end) {
215 bm_word_t* pw = word_addr(beg);
216 bm_word_t w = *pw;
217 bm_word_t mr = inverted_bit_mask_for_range(beg, end);
218 bm_word_t nw = value ? (w | ~mr) : (w & mr);
219 while (true) {
220 bm_word_t res = Atomic::cmpxchg(nw, pw, w);
221 if (res == w) break;
222 w = res;
223 nw = value ? (w | ~mr) : (w & mr);
224 }
225 }
226 }
227
228 void BitMap::set_range(idx_t beg, idx_t end) {
229 verify_range(beg, end);
230
231 idx_t beg_full_word = word_index_round_up(beg);
232 idx_t end_full_word = word_index(end);
233
234 if (beg_full_word < end_full_word) {
235 // The range includes at least one full word.
236 set_range_within_word(beg, bit_index(beg_full_word));
237 set_range_of_words(beg_full_word, end_full_word);
238 set_range_within_word(bit_index(end_full_word), end);
239 } else {
240 // The range spans at most 2 partial words.
241 idx_t boundary = MIN2(bit_index(beg_full_word), end);
242 set_range_within_word(beg, boundary);
243 set_range_within_word(boundary, end);
244 }
245 }
246
247 void BitMap::clear_range(idx_t beg, idx_t end) {
248 verify_range(beg, end);
249
250 idx_t beg_full_word = word_index_round_up(beg);
251 idx_t end_full_word = word_index(end);
252
253 if (beg_full_word < end_full_word) {
254 // The range includes at least one full word.
255 clear_range_within_word(beg, bit_index(beg_full_word));
256 clear_range_of_words(beg_full_word, end_full_word);
257 clear_range_within_word(bit_index(end_full_word), end);
258 } else {
259 // The range spans at most 2 partial words.
260 idx_t boundary = MIN2(bit_index(beg_full_word), end);
261 clear_range_within_word(beg, boundary);
262 clear_range_within_word(boundary, end);
263 }
264 }
265
266 bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
267 // There is little point to call large version on small ranges.
268 // Need to check carefully, keeping potential idx_t underflow in mind.
269 // The threshold should be at least one word.
270 STATIC_ASSERT(small_range_words >= 1);
271 return (beg_full_word + small_range_words >= end_full_word);
272 }
273
274 void BitMap::set_large_range(idx_t beg, idx_t end) {
275 verify_range(beg, end);
276
277 idx_t beg_full_word = word_index_round_up(beg);
278 idx_t end_full_word = word_index(end);
279
280 if (is_small_range_of_words(beg_full_word, end_full_word)) {
281 set_range(beg, end);
282 return;
283 }
284
285 // The range includes at least one full word.
286 set_range_within_word(beg, bit_index(beg_full_word));
287 set_large_range_of_words(beg_full_word, end_full_word);
288 set_range_within_word(bit_index(end_full_word), end);
289 }
290
291 void BitMap::clear_large_range(idx_t beg, idx_t end) {
292 verify_range(beg, end);
293
294 idx_t beg_full_word = word_index_round_up(beg);
295 idx_t end_full_word = word_index(end);
296
297 if (is_small_range_of_words(beg_full_word, end_full_word)) {
298 clear_range(beg, end);
299 return;
300 }
301
302 // The range includes at least one full word.
303 clear_range_within_word(beg, bit_index(beg_full_word));
304 clear_large_range_of_words(beg_full_word, end_full_word);
305 clear_range_within_word(bit_index(end_full_word), end);
306 }
307
308 void BitMap::at_put(idx_t offset, bool value) {
309 if (value) {
310 set_bit(offset);
311 } else {
312 clear_bit(offset);
313 }
314 }
315
316 // Return true to indicate that this thread changed
317 // the bit, false to indicate that someone else did.
318 // In either case, the requested bit is in the
319 // requested state some time during the period that
320 // this thread is executing this call. More importantly,
321 // if no other thread is executing an action to
322 // change the requested bit to a state other than
323 // the one that this thread is trying to set it to,
324 // then the the bit is in the expected state
325 // at exit from this method. However, rather than
326 // make such a strong assertion here, based on
327 // assuming such constrained use (which though true
328 // today, could change in the future to service some
329 // funky parallel algorithm), we encourage callers
330 // to do such verification, as and when appropriate.
331 bool BitMap::par_at_put(idx_t bit, bool value) {
332 return value ? par_set_bit(bit) : par_clear_bit(bit);
333 }
334
335 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
336 if (value) {
337 set_range(start_offset, end_offset);
338 } else {
339 clear_range(start_offset, end_offset);
340 }
341 }
342
343 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
344 verify_range(beg, end);
345
346 idx_t beg_full_word = word_index_round_up(beg);
347 idx_t end_full_word = word_index(end);
348
349 if (beg_full_word < end_full_word) {
350 // The range includes at least one full word.
351 par_put_range_within_word(beg, bit_index(beg_full_word), value);
352 if (value) {
353 set_range_of_words(beg_full_word, end_full_word);
354 } else {
355 clear_range_of_words(beg_full_word, end_full_word);
356 }
357 par_put_range_within_word(bit_index(end_full_word), end, value);
358 } else {
359 // The range spans at most 2 partial words.
360 idx_t boundary = MIN2(bit_index(beg_full_word), end);
361 par_put_range_within_word(beg, boundary, value);
362 par_put_range_within_word(boundary, end, value);
363 }
364
365 }
366
367 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
368 if (value) {
369 set_large_range(beg, end);
370 } else {
371 clear_large_range(beg, end);
372 }
373 }
374
375 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
376 verify_range(beg, end);
377
378 idx_t beg_full_word = word_index_round_up(beg);
379 idx_t end_full_word = word_index(end);
380
381 if (is_small_range_of_words(beg_full_word, end_full_word)) {
382 par_at_put_range(beg, end, value);
383 return;
384 }
385
386 // The range includes at least one full word.
387 par_put_range_within_word(beg, bit_index(beg_full_word), value);
388 if (value) {
389 set_large_range_of_words(beg_full_word, end_full_word);
390 } else {
391 clear_large_range_of_words(beg_full_word, end_full_word);
392 }
393 par_put_range_within_word(bit_index(end_full_word), end, value);
394 }
395
396 inline bm_word_t tail_mask(idx_t tail_bits) {
397 assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
398 assert(tail_bits < (idx_t)BitsPerWord, "precondition");
399 return (bm_word_t(1) << tail_bits) - 1;
400 }
401
402 // Get the low tail_bits of value, which is the last partial word of a map.
403 inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
404 return value & tail_mask(tail_bits);
405 }
406
407 // Compute the new last word of a map with a non-aligned length.
408 // new_value has the new trailing bits of the map in the low tail_bits.
409 // old_value is the last word of the map, including bits beyond the end.
410 // Returns old_value with the low tail_bits replaced by the corresponding
411 // bits in new_value.
412 inline bm_word_t merge_tail_of_map(bm_word_t new_value,
413 bm_word_t old_value,
|
1 /*
2 * Copyright (c) 1997, 2019, 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 *
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.
200 if (beg != end) {
201 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
202 *word_addr(beg) |= ~mask;
203 }
204 }
205
206 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
207 // With a valid range (beg <= end), this test ensures that end != 0, as
208 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
209 if (beg != end) {
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,
|