Changes in kernel/generic/src/adt/bitmap.c [64f3d3b:f72906c] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/adt/bitmap.c (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
r64f3d3b rf72906c 37 37 * setting and clearing ranges of bits and for finding ranges 38 38 * of unset bits. 39 *40 * The bitmap ADT can optionally implement a two-level hierarchy41 * for faster range searches. The second level bitmap (of blocks)42 * is not precise, but conservative. This means that if the block43 * bit is set, it guarantees that all bits in the block are set.44 * But if the block bit is unset, nothing can be said about the45 * bits in the block.46 *47 39 */ 48 40 … … 56 48 #define ALL_ZEROES 0x00 57 49 58 /** Compute the size of a bitmap59 *60 * Compute the size of a bitmap that can store given number61 * of elements.62 *63 * @param elements Number of elements to store.64 *65 * @return Size of the bitmap (in units of BITMAP_ELEMENT bits).66 *67 */68 static size_t bitmap_bytes(size_t elements)69 {70 size_t bytes = elements / BITMAP_ELEMENT;71 72 if ((elements % BITMAP_ELEMENT) != 0)73 bytes++;74 75 return bytes;76 }77 78 /** Compute the number of 2nd level blocks79 *80 * Compute the number of 2nd level blocks for a given number81 * of elements.82 *83 * @param elements Number of elements.84 * @param block_size Number of elements in one block.85 *86 * @return Number of 2nd level blocks.87 * @return Zero if block_size is zero.88 *89 */90 static size_t bitmap_blocks(size_t elements, size_t block_size)91 {92 if (block_size == 0)93 return 0;94 95 size_t blocks = elements / block_size;96 97 if ((elements % block_size) != 0)98 blocks++;99 100 return blocks;101 }102 103 50 /** Unchecked version of bitmap_get() 104 51 * … … 113 60 static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element) 114 61 { 115 return !!((bitmap->bits)[element / BITMAP_ELEMENT] & 116 (1 << (element & BITMAP_REMAINER))); 62 size_t byte = element / BITMAP_ELEMENT; 63 uint8_t mask = 1 << (element & BITMAP_REMAINER); 64 65 return !!((bitmap->bits)[byte] & mask); 117 66 } 118 67 … … 122 71 * 123 72 * @param elements Number bits stored in bitmap. 124 * @param block_size Block size of the 2nd level bitmap.125 * If set to zero, no 2nd level is used.126 73 * 127 74 * @return Size (in bytes) required for the bitmap. 128 75 * 129 76 */ 130 size_t bitmap_size(size_t elements, size_t block_size) 131 { 132 size_t blocks = bitmap_blocks(elements, block_size); 133 134 return (bitmap_bytes(elements) + bitmap_bytes(blocks)); 77 size_t bitmap_size(size_t elements) 78 { 79 size_t size = elements / BITMAP_ELEMENT; 80 81 if ((elements % BITMAP_ELEMENT) != 0) 82 size++; 83 84 return size; 135 85 } 136 86 … … 141 91 * @param bitmap Bitmap structure. 142 92 * @param elements Number of bits stored in bitmap. 143 * @param block_size Block size of the 2nd level bitmap.144 * If set to zero, no 2nd level is used.145 93 * @param data Address of the memory used to hold the map. 146 94 * The optional 2nd level bitmap follows the 1st … … 148 96 * 149 97 */ 150 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 151 void *data) 98 void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data) 152 99 { 153 100 bitmap->elements = elements; 154 101 bitmap->bits = (uint8_t *) data; 155 156 if (block_size > 0) { 157 bitmap->block_size = block_size; 158 bitmap->blocks = bitmap->bits + 159 bitmap_size(elements, 0); 160 } else { 161 bitmap->block_size = 0; 162 bitmap->blocks = NULL; 163 } 164 } 165 166 static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count) 167 { 168 if (count == 0) 169 return; 170 171 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 172 173 /* Leading unaligned bits */ 174 size_t lub = min(aligned_start - start, count); 175 176 /* Aligned middle bits */ 177 size_t amb = (count > lub) ? (count - lub) : 0; 178 179 /* Trailing aligned bits */ 180 size_t tab = amb % BITMAP_ELEMENT; 181 182 if (start + count < aligned_start) { 183 /* Set bits in the middle of byte. */ 184 bits[start / BITMAP_ELEMENT] |= 185 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 186 return; 187 } 188 189 if (lub) { 190 /* Make sure to set any leading unaligned bits. */ 191 bits[start / BITMAP_ELEMENT] |= 192 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 193 } 194 195 size_t i; 196 197 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 198 /* The middle bits can be set byte by byte. */ 199 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES; 200 } 201 202 if (tab) { 203 /* Make sure to set any trailing aligned bits. */ 204 bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1; 205 } 102 bitmap->next_fit = 0; 206 103 } 207 104 … … 217 114 ASSERT(start + count <= bitmap->elements); 218 115 219 bitmap_set_range_internal(bitmap->bits, start, count);220 221 if (bitmap->block_size > 0) {222 size_t aligned_start = ALIGN_UP(start, bitmap->block_size);223 224 /* Leading unaligned bits */225 size_t lub = min(aligned_start - start, count);226 227 /* Aligned middle bits */228 size_t amb = (count > lub) ? (count - lub) : 0;229 230 size_t aligned_size = amb / bitmap->block_size;231 232 bitmap_set_range_internal(bitmap->blocks, aligned_start,233 aligned_size);234 }235 }236 237 static void bitmap_clear_range_internal(uint8_t *bits, size_t start,238 size_t count)239 {240 116 if (count == 0) 241 117 return; 242 118 119 size_t start_byte = start / BITMAP_ELEMENT; 243 120 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 244 121 … … 253 130 254 131 if (start + count < aligned_start) { 255 /* Set bits in the middle of byte */256 bit s[start / BITMAP_ELEMENT] &=257 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));132 /* Set bits in the middle of byte. */ 133 bitmap->bits[start_byte] |= 134 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 258 135 return; 259 136 } 260 137 261 138 if (lub) { 262 /* Make sure to clearany leading unaligned bits. */263 bit s[start / BITMAP_ELEMENT] &=264 (1 << (BITMAP_ELEMENT - lub)) - 1;139 /* Make sure to set any leading unaligned bits. */ 140 bitmap->bits[start_byte] |= 141 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 265 142 } 266 143 … … 268 145 269 146 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 270 /* The middle bits can be cleared byte by byte. */ 271 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; 147 /* The middle bits can be set byte by byte. */ 148 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 149 ALL_ONES; 272 150 } 273 151 274 152 if (tab) { 275 /* Make sure to clear any trailing aligned bits. */ 276 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); 153 /* Make sure to set any trailing aligned bits. */ 154 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |= 155 (1 << tab) - 1; 277 156 } 278 157 } … … 289 168 ASSERT(start + count <= bitmap->elements); 290 169 291 bitmap_clear_range_internal(bitmap->bits, start, count); 292 293 if (bitmap->block_size > 0) { 294 size_t aligned_start = start / bitmap->block_size; 295 296 size_t aligned_end = (start + count) / bitmap->block_size; 297 298 if (((start + count) % bitmap->block_size) != 0) 299 aligned_end++; 300 301 size_t aligned_size = aligned_end - aligned_start; 302 303 bitmap_clear_range_internal(bitmap->blocks, aligned_start, 304 aligned_size); 305 } 170 if (count == 0) 171 return; 172 173 size_t start_byte = start / BITMAP_ELEMENT; 174 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 175 176 /* Leading unaligned bits */ 177 size_t lub = min(aligned_start - start, count); 178 179 /* Aligned middle bits */ 180 size_t amb = (count > lub) ? (count - lub) : 0; 181 182 /* Trailing aligned bits */ 183 size_t tab = amb % BITMAP_ELEMENT; 184 185 if (start + count < aligned_start) { 186 /* Set bits in the middle of byte */ 187 bitmap->bits[start_byte] &= 188 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); 189 return; 190 } 191 192 if (lub) { 193 /* Make sure to clear any leading unaligned bits. */ 194 bitmap->bits[start_byte] &= 195 (1 << (BITMAP_ELEMENT - lub)) - 1; 196 } 197 198 size_t i; 199 200 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 201 /* The middle bits can be cleared byte by byte. */ 202 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 203 ALL_ZEROES; 204 } 205 206 if (tab) { 207 /* Make sure to clear any trailing aligned bits. */ 208 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &= 209 ~((1 << tab) - 1); 210 } 211 212 bitmap->next_fit = start_byte; 306 213 } 307 214 … … 351 258 * @param count Number of continuous zero bits to find. 352 259 * @param base Address of the first bit in the bitmap. 260 * @param prefered Prefered address to start searching from. 353 261 * @param constraint Constraint for the address of the first zero bit. 354 262 * @param index Place to store the index of the first zero … … 362 270 */ 363 271 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base, 364 size_t constraint, size_t *index)272 size_t prefered, size_t constraint, size_t *index) 365 273 { 366 274 if (count == 0) 367 275 return false; 368 276 369 size_t bytes = bitmap_bytes(bitmap->elements); 370 371 for (size_t byte = 0; byte < bytes; byte++) { 277 size_t size = bitmap_size(bitmap->elements); 278 size_t next_fit = bitmap->next_fit; 279 280 /* 281 * Adjust the next-fit value according to the address 282 * the caller prefers to start the search at. 283 */ 284 if ((prefered > base) && (prefered < base + bitmap->elements)) { 285 size_t prefered_fit = (prefered - base) / BITMAP_ELEMENT; 286 287 if (prefered_fit > next_fit) 288 next_fit = prefered_fit; 289 } 290 291 for (size_t pos = 0; pos < size; pos++) { 292 size_t byte = (next_fit + pos) % size; 293 372 294 /* Skip if the current byte has all bits set */ 373 295 if (bitmap->bits[byte] == ALL_ONES) … … 386 308 387 309 if (!bitmap_get_fast(bitmap, i)) { 388 bool continuous = true;310 size_t continuous = 1; 389 311 390 312 for (size_t j = 1; j < count; j++) { 391 if ((i + j >= bitmap->elements) || 392 (bitmap_get_fast(bitmap, i + j))) { 393 continuous = false; 313 if ((i + j < bitmap->elements) && 314 (!bitmap_get_fast(bitmap, i + j))) 315 continuous++; 316 else 394 317 break; 395 }396 318 } 397 319 398 if (continuous ) {320 if (continuous == count) { 399 321 if (index != NULL) { 400 322 bitmap_set_range(bitmap, i, count); 323 bitmap->next_fit = i / BITMAP_ELEMENT; 401 324 *index = i; 402 325 } 403 326 404 327 return true; 405 } 328 } else 329 i += continuous; 406 330 } 407 331 }
Note:
See TracChangeset
for help on using the changeset viewer.
