Changes in kernel/generic/src/adt/bitmap.c [f72906c:d5f774f6] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/adt/bitmap.c (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
rf72906c rd5f774f6 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 hierarchy 41 * for faster range searches. The second level bitmap (of blocks) 42 * is not precise, but conservative. This means that if the block 43 * 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 the 45 * bits in the block. 46 * 39 47 */ 40 48 … … 48 56 #define ALL_ZEROES 0x00 49 57 50 /** Unchecked version of bitmap_get()51 *52 * This version of bitmap_get() does not do any boundary checks.53 *54 * @param bitmap Bitmap to access.55 * @param element Element to access.56 *57 * @return Bit value of the element in the bitmap.58 *59 */60 static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element)61 {62 size_t byte = element / BITMAP_ELEMENT;63 uint8_t mask = 1 << (element & BITMAP_REMAINER);64 65 return !!((bitmap->bits)[byte] & mask);66 }67 68 58 /** Get bitmap size 69 59 * … … 71 61 * 72 62 * @param elements Number bits stored in bitmap. 63 * @param block_size Block size of the 2nd level bitmap. 64 * If set to zero, no 2nd level is used. 73 65 * 74 66 * @return Size (in bytes) required for the bitmap. 75 67 * 76 68 */ 77 size_t bitmap_size(size_t elements )69 size_t bitmap_size(size_t elements, size_t block_size) 78 70 { 79 71 size_t size = elements / BITMAP_ELEMENT; … … 82 74 size++; 83 75 76 if (block_size > 0) { 77 size += elements / block_size; 78 79 if ((elements % block_size) != 0) 80 size++; 81 } 82 84 83 return size; 85 84 } … … 91 90 * @param bitmap Bitmap structure. 92 91 * @param elements Number of bits stored in bitmap. 92 * @param block_size Block size of the 2nd level bitmap. 93 * If set to zero, no 2nd level is used. 93 94 * @param data Address of the memory used to hold the map. 94 95 * The optional 2nd level bitmap follows the 1st … … 96 97 * 97 98 */ 98 void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data) 99 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 100 void *data) 99 101 { 100 102 bitmap->elements = elements; 101 103 bitmap->bits = (uint8_t *) data; 102 bitmap->next_fit = 0; 104 105 if (block_size > 0) { 106 bitmap->block_size = block_size; 107 bitmap->blocks = bitmap->bits + 108 bitmap_size(elements, 0); 109 } else { 110 bitmap->block_size = 0; 111 bitmap->blocks = NULL; 112 } 113 } 114 115 static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count) 116 { 117 if (count == 0) 118 return; 119 120 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 121 122 /* Leading unaligned bits */ 123 size_t lub = min(aligned_start - start, count); 124 125 /* Aligned middle bits */ 126 size_t amb = (count > lub) ? (count - lub) : 0; 127 128 /* Trailing aligned bits */ 129 size_t tab = amb % BITMAP_ELEMENT; 130 131 if (start + count < aligned_start) { 132 /* Set bits in the middle of byte. */ 133 bits[start / BITMAP_ELEMENT] |= 134 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 135 return; 136 } 137 138 if (lub) { 139 /* Make sure to set any leading unaligned bits. */ 140 bits[start / BITMAP_ELEMENT] |= 141 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 142 } 143 144 size_t i; 145 146 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 147 /* The middle bits can be set byte by byte. */ 148 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES; 149 } 150 151 if (tab) { 152 /* Make sure to set any trailing aligned bits. */ 153 bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1; 154 } 103 155 } 104 156 … … 114 166 ASSERT(start + count <= bitmap->elements); 115 167 168 bitmap_set_range_internal(bitmap->bits, start, count); 169 170 if (bitmap->block_size > 0) { 171 size_t aligned_start = ALIGN_UP(start, bitmap->block_size); 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 size_t aligned_size = amb / bitmap->block_size; 180 181 bitmap_set_range_internal(bitmap->blocks, aligned_start, 182 aligned_size); 183 } 184 } 185 186 static void bitmap_clear_range_internal(uint8_t *bits, size_t start, 187 size_t count) 188 { 116 189 if (count == 0) 117 190 return; 118 191 119 size_t start_byte = start / BITMAP_ELEMENT;120 192 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 121 193 … … 130 202 131 203 if (start + count < aligned_start) { 132 /* Set bits in the middle of byte .*/133 bit map->bits[start_byte] |=134 ((1 << lub) - 1) << (start & BITMAP_REMAINER);204 /* Set bits in the middle of byte */ 205 bits[start / BITMAP_ELEMENT] &= 206 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); 135 207 return; 136 208 } 137 209 138 210 if (lub) { 139 /* Make sure to setany leading unaligned bits. */140 bit map->bits[start_byte] |=141 ~((1 << (BITMAP_ELEMENT - lub)) - 1);211 /* Make sure to clear any leading unaligned bits. */ 212 bits[start / BITMAP_ELEMENT] &= 213 (1 << (BITMAP_ELEMENT - lub)) - 1; 142 214 } 143 215 … … 145 217 146 218 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 147 /* The middle bits can be set byte by byte. */ 148 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 149 ALL_ONES; 219 /* The middle bits can be cleared byte by byte. */ 220 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; 150 221 } 151 222 152 223 if (tab) { 153 /* Make sure to set any trailing aligned bits. */ 154 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |= 155 (1 << tab) - 1; 224 /* Make sure to clear any trailing aligned bits. */ 225 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); 156 226 } 157 227 } … … 168 238 ASSERT(start + count <= bitmap->elements); 169 239 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; 240 bitmap_clear_range_internal(bitmap->bits, start, count); 241 242 if (bitmap->block_size > 0) { 243 size_t aligned_start = start / bitmap->block_size; 244 245 size_t aligned_end = (start + count) / bitmap->block_size; 246 247 if (((start + count) % bitmap->block_size) != 0) 248 aligned_end++; 249 250 size_t aligned_size = aligned_end - aligned_start; 251 252 bitmap_clear_range_internal(bitmap->blocks, aligned_start, 253 aligned_size); 254 } 213 255 } 214 256 … … 258 300 * @param count Number of continuous zero bits to find. 259 301 * @param base Address of the first bit in the bitmap. 260 * @param prefered Prefered address to start searching from.261 302 * @param constraint Constraint for the address of the first zero bit. 262 303 * @param index Place to store the index of the first zero … … 270 311 */ 271 312 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base, 272 size_t prefered, size_tconstraint, size_t *index)313 size_t constraint, size_t *index) 273 314 { 274 315 if (count == 0) 275 316 return false; 276 317 277 size_t size = bitmap_size(bitmap->elements);278 size_t next_fit = bitmap->next_fit;279 280 318 /* 281 * Adjust the next-fit value according to the address282 * the caller prefers to start the search at.319 * This is a trivial implementation that should be 320 * optimized further. 283 321 */ 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 294 /* Skip if the current byte has all bits set */ 295 if (bitmap->bits[byte] == ALL_ONES) 322 323 for (size_t i = 0; i < bitmap->elements; i++) { 324 if (!constraint_satisfy(i, base, constraint)) 296 325 continue; 297 326 298 size_t byte_bit = byte * BITMAP_ELEMENT; 299 300 for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) { 301 size_t i = byte_bit + bit; 327 if (!bitmap_get(bitmap, i)) { 328 bool continuous = true; 302 329 303 if (i >= bitmap->elements) 304 break; 330 for (size_t j = 1; j < count; j++) { 331 if ((i + j >= bitmap->elements) || 332 (bitmap_get(bitmap, i + j))) { 333 continuous = false; 334 break; 335 } 336 } 305 337 306 if (!constraint_satisfy(i, base, constraint)) 307 continue; 308 309 if (!bitmap_get_fast(bitmap, i)) { 310 size_t continuous = 1; 311 312 for (size_t j = 1; j < count; j++) { 313 if ((i + j < bitmap->elements) && 314 (!bitmap_get_fast(bitmap, i + j))) 315 continuous++; 316 else 317 break; 338 if (continuous) { 339 if (index != NULL) { 340 bitmap_set_range(bitmap, i, count); 341 *index = i; 318 342 } 319 343 320 if (continuous == count) { 321 if (index != NULL) { 322 bitmap_set_range(bitmap, i, count); 323 bitmap->next_fit = i / BITMAP_ELEMENT; 324 *index = i; 325 } 326 327 return true; 328 } else 329 i += continuous; 344 return true; 330 345 } 331 346 } 347 332 348 } 333 349 … … 335 351 } 336 352 353 /** Clear range of set bits. 354 * 355 * This is essentially bitmap_clear_range(), but it also 356 * checks whether all the cleared bits are actually set. 357 * 358 * @param bitmap Bitmap structure. 359 * @param start Starting bit. 360 * @param count Number of bits to clear. 361 * 362 */ 363 void bitmap_free_range(bitmap_t *bitmap, size_t start, size_t count) 364 { 365 /* 366 * This is a trivial implementation that should be 367 * optimized further. 368 */ 369 370 for (size_t i = 0; i < count; i++) { 371 if (!bitmap_get(bitmap, start + i)) 372 panic("Freeing a bitmap range that is not set"); 373 } 374 375 bitmap_clear_range(bitmap, start, count); 376 } 377 337 378 /** @} 338 379 */
Note:
See TracChangeset
for help on using the changeset viewer.
