1/* 2 * Copyright (c) 2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20/* 21 Bitmap.h 22 High Performance Bitmap 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#pragma once 27#ifndef __AUTO_BITMAP__ 28#define __AUTO_BITMAP__ 29 30#include "Definitions.h" 31#include "Range.h" 32 33 34namespace Auto { 35 36 //----- Bitmap -----// 37 38 // 39 // Bitmaps (bit vectors) are a fast and lightweight means of showing set 40 // representation. A single bit is used to indicate membership in the set; 1 41 // indicating membership and 0 indicating exclusion. In this representation we use 42 // an array of unsigned long words. Each word represents a unit of bits_per_word members 43 // numbered from the least significant bit (endian representation is not 44 // important.) Thus for any member k its word index would be equal to (k / bits_per_word) or 45 // (k >> ilog2(bits_per_word)) and its bit position would be equal to (k % bits_per_word). 46 // 47 48 class Bitmap : public Range { 49 50 private: 51 52 // 53 // index 54 // 55 // Returns the word index of a specified bit. 56 // 57 static inline const usword_t index(const usword_t bp) { return bp >> bits_per_word_log2; } 58 59 60 // 61 // shift 62 // 63 // Returns the shift of a specified bit. 64 // 65 static inline const usword_t shift(const usword_t bp) { return bp & bits_mask; } 66 67 68 // 69 // cursor_bp 70 // 71 // Returns the bit position of the specified cursor. 72 // 73 inline usword_t cursor_bp(const usword_t *cursor) const { return ((uintptr_t)cursor - (uintptr_t)address()) << bits_per_byte_log2; } 74 75 76 // 77 // end_cursor 78 // 79 // Returns the end of the bits as a word address. 80 // 81 inline usword_t *end_cursor() const { return (usword_t *)Range::end(); } 82 83 84 public: 85 86 // 87 // Constructors 88 // 89 Bitmap() {} 90 Bitmap(usword_t n, void *bits) { 91 // keep aligned for vector operations 92 ASSERTION(!((uintptr_t)bits & mask(bytes_per_quad_log2)) && !(bytes_needed(n) & mask(bytes_per_quad_log2))); 93 set_range(bits, bytes_needed(n)); 94 } 95 96 97 // 98 // bp_cursor 99 // 100 // Returns the word address containing a specified bit. 101 // 102 inline usword_t *bp_cursor(const usword_t bp) const { 103 return (usword_t *)displace(address(), (bp >> (bits_per_word_log2 - bytes_per_word_log2)) & ~mask(bytes_per_word_log2)); 104 } 105 106 107 // 108 // size_in_bits 109 // 110 // Return the number of bits in the bitmap. 111 // 112 inline usword_t size_in_bits() const { return size() << bits_per_byte_log2; } 113 114 115 // 116 // initialize 117 // 118 // Set up the bit map for use. 119 // 120 inline void initialize(usword_t n, void *bits) { set_range(bits, bytes_needed(n)); } 121 122 123 // 124 // bytes_needed 125 // 126 // Returns the number of bytes needed to represent 'n' bits. 127 // 128 static inline const usword_t bytes_needed(usword_t n) { return partition2(n, bits_per_word_log2) << bytes_per_word_log2; } 129 130 131 // 132 // bit 133 // 134 // Returns the state of a bit in the bit map. 135 // 136 inline usword_t bit(const usword_t bp) const { return (*bp_cursor(bp) >> shift(bp)) & 1L; } 137 138 139 // 140 // set_bit 141 // 142 // Set a bit in the bit map to 1. 143 // 144 inline void set_bit(const usword_t bp) const { 145 usword_t *cursor = bp_cursor(bp); 146 *cursor |= (1L << shift(bp)); 147 } 148 149 150 // 151 // set_bits_large 152 // 153 // Set n bits in the bit map to 1 spanning more than one word. 154 // Assumes that range spans more than one word. 155 // 156 void set_bits_large(const usword_t bp, const usword_t n) const; 157 158 159 // 160 // set_bits 161 // 162 // Set bits in the bit map to 1. 163 // 164 inline void set_bits(const usword_t bp, const usword_t n) const { 165 const usword_t sh = shift(bp); // bit shift 166 167 if ((sh + n) > bits_per_word) { 168 set_bits_large(bp, n); 169 } else { 170 usword_t m = mask(n); // mask of n bits 171 *bp_cursor(bp) |= (m << sh); // set bits to 1 172 } 173 } 174 175 // 176 // clear_bit 177 // 178 // Set a bit in the bit map to 0. 179 // 180 inline void clear_bit(const usword_t bp) const { 181 usword_t *cursor = bp_cursor(bp); 182 *cursor &= ~(1L << shift(bp)); 183 } 184 185 186 // 187 // clear_bits_large 188 // 189 // Set n bits in the bit map to 0 spanning more than one word. 190 // Assumes that range spans more than one word. 191 // 192 void clear_bits_large(const usword_t bp, const usword_t n) const; 193 194 // 195 // clear_bits 196 // 197 // Set n bits in the bit map to 0. 198 // 199 inline void clear_bits(const usword_t bp, const usword_t n) const { 200 const usword_t sh = shift(bp); // bit shift 201 202 if ((sh + n) > bits_per_word) { 203 clear_bits_large(bp, n); 204 } else { 205 usword_t m = mask(n); // mask of n bits 206 *bp_cursor(bp) &= ~(m << sh); // set bits to 0 207 } 208 } 209 210 // 211 // bits_are_clear_large 212 // 213 // Checks to see if a range of bits, spanning more than one word, are all 0. 214 // 215 bool bits_are_clear_large(const usword_t bp, const usword_t n) const; 216 217 218 // 219 // bits_are_clear 220 // 221 inline bool bits_are_clear(const usword_t bp, const usword_t n) const { 222 const usword_t sh = shift(bp); // bit shift 223 224 if ((sh + n) > bits_per_word) { 225 return bits_are_clear_large(bp, n); 226 } else { 227 usword_t m = mask(n); // mask of n bits 228 return (*bp_cursor(bp) & (m << sh)) == 0; // see if bits are 0 229 } 230 } 231 232 233 // 234 // skip_all_zeros 235 // 236 // Rapidly skips through words of all zeros. 237 // 238 static inline usword_t *skip_all_zeros(usword_t *cursor, usword_t *end) { 239 // near end address (allows multiple reads) 240 usword_t *near_end = end - 4; 241 242 // skip through as many all zeros as we can 243 while (cursor < near_end) { 244 // prefetch four words 245 usword_t word0 = cursor[0]; 246 usword_t word1 = cursor[1]; 247 usword_t word2 = cursor[2]; 248 usword_t word3 = cursor[3]; 249 250 // assume they are all filled with zeros 251 cursor += 4; 252 253 // backtrack if we find out otherwise 254 if (!is_all_zeros(word0)) { cursor -= 4; break; } 255 if (!is_all_zeros(word1)) { cursor -= 3; break; } 256 if (!is_all_zeros(word2)) { cursor -= 2; break; } 257 if (!is_all_zeros(word3)) { cursor -= 1; break; } 258 } 259 260 // finish off the rest 261 while (cursor < end) { 262 usword_t word = *cursor++; 263 if (!is_all_zeros(word)) { cursor--; break; } 264 } 265 266 return cursor; 267 } 268 269 270 // 271 // skip_backward_all_zeros 272 // 273 // Rapidly skips through words of all zeros. 274 // 275 static inline usword_t *skip_backward_all_zeros(usword_t *cursor, usword_t *first) { 276 // near first address (allows multiple reads) 277 usword_t *near_first = first + 3; 278 279 // skip through as many all zeros as we can 280 while (near_first <= cursor) { 281 // prefetch four words 282 usword_t word0 = cursor[0]; 283 usword_t word1 = cursor[-1]; 284 usword_t word2 = cursor[-2]; 285 usword_t word3 = cursor[-3]; 286 287 // assume they are all filled with zeros 288 cursor -= 4; 289 290 // backtrack if we find out otherwise 291 if (!is_all_zeros(word0)) { cursor += 4; break; } 292 if (!is_all_zeros(word1)) { cursor += 3; break; } 293 if (!is_all_zeros(word2)) { cursor += 2; break; } 294 if (!is_all_zeros(word3)) { cursor += 1; break; } 295 } 296 297 // finish off the rest 298 while (first <= cursor) { 299 usword_t word = *cursor--; 300 if (!is_all_zeros(word)) { cursor++; break; } 301 } 302 303 return cursor; 304 } 305 306 307 // 308 // count_set 309 // 310 // Returns the number of bits set (one) in the bit map using 311 // a standard bit population algoirithm. 312 // 313 usword_t count_set() const ; 314 315 316 // 317 // previous_set 318 // 319 // Return the bit postion of the 1 that comes at or prior to the bit position 'bp'. 320 // 321 usword_t previous_set(const usword_t bp) const ; 322 323 324 // 325 // next_set 326 // 327 // Return the bit postion of the 1 that comes at or after to the bit position 'bp'. 328 // 329 usword_t next_set(const usword_t bp) const; 330 331 332 // ***** Atomic bitmap operations 333 334 // 335 // atomic_compare_and_swap_word 336 // 337 // This is the basis for all the Bitmap atomic operations 338 // 339 static inline bool atomic_compare_and_swap_word(usword_t old_value, usword_t new_value, volatile usword_t *addr) { 340 ASSERTION(((uintptr_t)addr & mask(bytes_per_word_log2)) == 0); 341 return auto_atomic_compare_and_swap(old_value, new_value, addr); 342 } 343 344 // 345 // atomic_and_return_orig 346 // 347 // Perform an atomic and operation and return the original value 348 // 349 static usword_t atomic_and_return_orig(usword_t mask, volatile usword_t *addr) { 350 usword_t old_value; 351 do { 352 old_value = *addr; 353 } while (!atomic_compare_and_swap_word(old_value, old_value & mask, addr)); 354 return old_value; 355 } 356 357 // 358 // atomic_or_return_orig 359 // 360 // Perform an atomic or operation and return the original value 361 // 362 static usword_t atomic_or_return_orig(usword_t mask, volatile usword_t *addr) { 363 usword_t old_value; 364 do { 365 old_value = *addr; 366 } while (!atomic_compare_and_swap_word(old_value, old_value | mask, addr)); 367 return old_value; 368 } 369 370 // 371 // set_bit_atomic 372 // 373 // Set a bit in the bit map to 1 atomically. 374 // 375 inline void set_bit_atomic(const usword_t bp) const { 376 test_set_bit_atomic(bp); 377 } 378 379 // 380 // test_and_set_bit_atomic 381 // 382 // Test a bit, and set it atomically if it hasn't bee set yet. Returns old bit value. 383 // 384 inline bool test_set_bit_atomic(const usword_t bp) const { 385 usword_t bit = 1L << shift(bp); 386 volatile usword_t *cursor = bp_cursor(bp); 387 usword_t old = *cursor; 388 if ((old & bit)==0) { 389 old = atomic_or_return_orig(bit, cursor); 390 } 391 return (old & bit) != 0; // return false if the bit was set by this call 392 } 393 394 // 395 // clear_bit_atomic 396 // 397 // Set a bit in the bit map to 0 atomically. 398 // 399 inline void clear_bit_atomic(const usword_t bp) const { 400 test_clear_bit_atomic(bp); 401 } 402 403 404 // 405 // test_and_clear_bit 406 // 407 // Test a bit, and clear it if was set. Returns old bit value. 408 // 409 inline bool test_clear_bit_atomic(const usword_t bp) const { 410 usword_t bit = 1L << shift(bp); 411 volatile usword_t *cursor = bp_cursor(bp); 412 usword_t old = *cursor; 413 if ((old & bit)!=0) { 414 old = atomic_and_return_orig(~bit, cursor); 415 } 416 return (old & bit)!=0; // return true if the bit was cleared by this call 417 } 418 419 420 //----- AtomicCursor -----// 421 422 // 423 // AtomicCursor provides a specialized way of doing test and clear searching of a range in a bitmap. 424 // It returns the indices for bits which are found to be set, clearing the bits as a side effect. 425 // The bitmap is accessed using atomic operations, but a word at a time. A word worth of bits is fetched 426 // into a local buffer which is then accessed using nonatomic operations. 427 // 428 class AtomicCursor { 429 Bitmap &_bitmap; // the bitmap being examined 430 usword_t _index; // the "current bit" - the value that will be returned from next_set_bit() if the bit is set 431 usword_t _offset; // arbitrary offset that is subtracted from values returned by next_set_bit() (adjusts for subzone quanum bias 432 usword_t _max_index; // end point of the scan. the last possible return from next_set_bit() is _max_index-1 433 usword_t _copied_bits; // bits copied out of the bitmap 434 usword_t _valid_bits; // number of valid bits in _copied_bits 435 436 public: 437 438 // 439 // Constructor 440 // 441 // arguments are the bitmap, starting index, and number of bits to enumerate 442 AtomicCursor(Bitmap &b, usword_t start, usword_t length) : _bitmap(b), _index(start), _offset(start), _max_index(start + length) { 443 // Perform the first fetch, which may not be word aligned. 444 // This lets us assume _index is word aligned when we fetch in next_set_bit(). 445 _copied_bits = fetch_clear_bits_atomic(_index, _max_index, _valid_bits); 446 }; 447 448 // 449 // fetch_clear_bits_atomic 450 // 451 // fetch and clear multiple bits at a time 452 // bp is the index of the first bit to fetch, max is the first index *not* to be fetched 453 // returns a word containing the fetched bits, and by reference in count the number of valid bits in the return 454 // returned bits start at bit 0, and bits higher than count are zeroed 455 // 456 usword_t fetch_clear_bits_atomic(const usword_t bp, const usword_t max, usword_t &count); 457 458 // 459 // next_set_bit 460 // 461 // Returns the index of a set bit from the bitmap range. If no bits are set, returns -1. 462 // The returned value is the offset from the start index passed to the constructor. 463 // So if 5 is passed as the start bit to the constructor and bit 8 is the first set bit in the bitmap, 464 // the first callto next_set_bit() will return 3. (This is done because the cursor is used 465 // to enumerate subzone quanta, which are zero based.) 466 // 467 usword_t next_set_bit(); 468 }; 469 }; 470 471 472}; 473 474 475#endif // __AUTO_BITMAP__ 476