Changes in kernel/generic/src/adt/bitmap.c [d5f774f6:f72906c] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
rd5f774f6 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 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 58 68 /** Get bitmap size 59 69 * … … 61 71 * 62 72 * @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.65 73 * 66 74 * @return Size (in bytes) required for the bitmap. 67 75 * 68 76 */ 69 size_t bitmap_size(size_t elements , size_t block_size)77 size_t bitmap_size(size_t elements) 70 78 { 71 79 size_t size = elements / BITMAP_ELEMENT; … … 74 82 size++; 75 83 76 if (block_size > 0) {77 size += elements / block_size;78 79 if ((elements % block_size) != 0)80 size++;81 }82 83 84 return size; 84 85 } … … 90 91 * @param bitmap Bitmap structure. 91 92 * @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.94 93 * @param data Address of the memory used to hold the map. 95 94 * The optional 2nd level bitmap follows the 1st … … 97 96 * 98 97 */ 99 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 100 void *data) 98 void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data) 101 99 { 102 100 bitmap->elements = elements; 103 101 bitmap->bits = (uint8_t *) data; 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 } 102 bitmap->next_fit = 0; 155 103 } 156 104 … … 166 114 ASSERT(start + count <= bitmap->elements); 167 115 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 {189 116 if (count == 0) 190 117 return; 191 118 119 size_t start_byte = start / BITMAP_ELEMENT; 192 120 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 193 121 … … 202 130 203 131 if (start + count < aligned_start) { 204 /* Set bits in the middle of byte */205 bit s[start / BITMAP_ELEMENT] &=206 ~(((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); 207 135 return; 208 136 } 209 137 210 138 if (lub) { 211 /* Make sure to clearany leading unaligned bits. */212 bit s[start / BITMAP_ELEMENT] &=213 (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); 214 142 } 215 143 … … 217 145 218 146 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 219 /* The middle bits can be cleared byte by byte. */ 220 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; 221 150 } 222 151 223 152 if (tab) { 224 /* Make sure to clear any trailing aligned bits. */ 225 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; 226 156 } 227 157 } … … 238 168 ASSERT(start + count <= bitmap->elements); 239 169 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 } 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; 255 213 } 256 214 … … 300 258 * @param count Number of continuous zero bits to find. 301 259 * @param base Address of the first bit in the bitmap. 260 * @param prefered Prefered address to start searching from. 302 261 * @param constraint Constraint for the address of the first zero bit. 303 262 * @param index Place to store the index of the first zero … … 311 270 */ 312 271 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base, 313 size_t constraint, size_t *index)272 size_t prefered, size_t constraint, size_t *index) 314 273 { 315 274 if (count == 0) 316 275 return false; 317 276 277 size_t size = bitmap_size(bitmap->elements); 278 size_t next_fit = bitmap->next_fit; 279 318 280 /* 319 * This is a trivial implementation that should be320 * optimized further.281 * Adjust the next-fit value according to the address 282 * the caller prefers to start the search at. 321 283 */ 322 323 for (size_t i = 0; i < bitmap->elements; i++) { 324 if (!constraint_satisfy(i, base, constraint)) 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) 325 296 continue; 326 297 327 if (!bitmap_get(bitmap, i)) { 328 bool continuous = true; 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; 329 302 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 } 303 if (i >= bitmap->elements) 304 break; 337 305 338 if (continuous) { 339 if (index != NULL) { 340 bitmap_set_range(bitmap, i, count); 341 *index = i; 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; 342 318 } 343 319 344 return true; 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; 345 330 } 346 331 } 347 348 332 } 349 333 … … 351 335 } 352 336 353 /** Clear range of set bits.354 *355 * This is essentially bitmap_clear_range(), but it also356 * 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 be367 * 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 378 337 /** @} 379 338 */
Note:
See TracChangeset
for help on using the changeset viewer.