Changes in kernel/generic/src/adt/bitmap.c [d5f774f6:9d58539] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/adt/bitmap.c (modified) (4 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
rd5f774f6 r9d58539 35 35 * 36 36 * This file implements bitmap ADT and provides functions for 37 * setting and clearing ranges of bits and for finding ranges 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 * 37 * setting and clearing ranges of bits. 47 38 */ 48 39 … … 53 44 #include <macros.h> 54 45 55 #define ALL_ONES 0xff 56 #define ALL_ZEROES 0x00 57 58 /** Get bitmap size 59 * 60 * Return the size (in bytes) required for the bitmap. 61 * 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. 65 * 66 * @return Size (in bytes) required for the bitmap. 67 * 68 */ 69 size_t bitmap_size(size_t elements, size_t block_size) 70 { 71 size_t size = elements / BITMAP_ELEMENT; 72 73 if ((elements % BITMAP_ELEMENT) != 0) 74 size++; 75 76 if (block_size > 0) { 77 size += elements / block_size; 78 79 if ((elements % block_size) != 0) 80 size++; 81 } 82 83 return size; 84 } 46 #define ALL_ONES 0xff 47 #define ALL_ZEROES 0x00 85 48 86 49 /** Initialize bitmap. … … 88 51 * No portion of the bitmap is set or cleared by this function. 89 52 * 90 * @param bitmap Bitmap structure. 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. 94 * @param data Address of the memory used to hold the map. 95 * The optional 2nd level bitmap follows the 1st 96 * level bitmap. 97 * 53 * @param bitmap Bitmap structure. 54 * @param map Address of the memory used to hold the map. 55 * @param bits Number of bits stored in bitmap. 98 56 */ 99 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 100 void *data) 57 void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits) 101 58 { 102 bitmap->elements = elements; 103 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 } 59 bitmap->map = map; 60 bitmap->bits = bits; 113 61 } 114 62 115 static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count) 63 /** Set range of bits. 64 * 65 * @param bitmap Bitmap structure. 66 * @param start Starting bit. 67 * @param bits Number of bits to set. 68 */ 69 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits) 116 70 { 117 if (count == 0) 71 size_t i = 0; 72 size_t aligned_start; 73 size_t lub; /* leading unaligned bits */ 74 size_t amb; /* aligned middle bits */ 75 size_t tab; /* trailing aligned bits */ 76 77 ASSERT(start + bits <= bitmap->bits); 78 79 aligned_start = ALIGN_UP(start, 8); 80 lub = min(aligned_start - start, bits); 81 amb = bits > lub ? bits - lub : 0; 82 tab = amb % 8; 83 84 if (!bits) 118 85 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) { 86 87 if (start + bits < aligned_start) { 132 88 /* Set bits in the middle of byte. */ 133 bits[start / BITMAP_ELEMENT] |= 134 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 89 bitmap->map[start / 8] |= ((1 << lub) - 1) << (start & 7); 135 90 return; 136 91 } … … 138 93 if (lub) { 139 94 /* Make sure to set any leading unaligned bits. */ 140 bits[start / BITMAP_ELEMENT] |= 141 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 95 bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1); 96 } 97 for (i = 0; i < amb / 8; i++) { 98 /* The middle bits can be set byte by byte. */ 99 bitmap->map[aligned_start / 8 + i] = ALL_ONES; 100 } 101 if (tab) { 102 /* Make sure to set any trailing aligned bits. */ 103 bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1; 142 104 } 143 105 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 }155 }156 157 /** Set range of bits.158 *159 * @param bitmap Bitmap structure.160 * @param start Starting bit.161 * @param count Number of bits to set.162 *163 */164 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)165 {166 ASSERT(start + count <= bitmap->elements);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 {189 if (count == 0)190 return;191 192 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);193 194 /* Leading unaligned bits */195 size_t lub = min(aligned_start - start, count);196 197 /* Aligned middle bits */198 size_t amb = (count > lub) ? (count - lub) : 0;199 200 /* Trailing aligned bits */201 size_t tab = amb % BITMAP_ELEMENT;202 203 if (start + count < aligned_start) {204 /* Set bits in the middle of byte */205 bits[start / BITMAP_ELEMENT] &=206 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));207 return;208 }209 210 if (lub) {211 /* Make sure to clear any leading unaligned bits. */212 bits[start / BITMAP_ELEMENT] &=213 (1 << (BITMAP_ELEMENT - lub)) - 1;214 }215 216 size_t i;217 218 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;221 }222 223 if (tab) {224 /* Make sure to clear any trailing aligned bits. */225 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1);226 }227 106 } 228 107 229 108 /** Clear range of bits. 230 109 * 231 * @param bitmap Bitmap structure. 232 * @param start Starting bit. 233 * @param count Number of bits to clear. 234 * 110 * @param bitmap Bitmap structure. 111 * @param start Starting bit. 112 * @param bits Number of bits to clear. 235 113 */ 236 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)114 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits) 237 115 { 238 ASSERT(start + count <= bitmap->elements); 116 size_t i = 0; 117 size_t aligned_start; 118 size_t lub; /* leading unaligned bits */ 119 size_t amb; /* aligned middle bits */ 120 size_t tab; /* trailing aligned bits */ 239 121 240 bitmap_clear_range_internal(bitmap->bits, start, count);122 ASSERT(start + bits <= bitmap->bits); 241 123 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);124 aligned_start = ALIGN_UP(start, 8); 125 lub = min(aligned_start - start, bits); 126 amb = bits > lub ? bits - lub : 0; 127 tab = amb % 8; 128 129 if (!bits) 130 return; 131 132 if (start + bits < aligned_start) { 133 /* Set bits in the middle of byte */ 134 bitmap->map[start / 8] &= ~(((1 << lub) - 1) << (start & 7)); 135 return; 254 136 } 137 138 if (lub) { 139 /* Make sure to clear any leading unaligned bits. */ 140 bitmap->map[start / 8] &= (1 << (8 - lub)) - 1; 141 } 142 for (i = 0; i < amb / 8; i++) { 143 /* The middle bits can be cleared byte by byte. */ 144 bitmap->map[aligned_start / 8 + i] = ALL_ZEROES; 145 } 146 if (tab) { 147 /* Make sure to clear any trailing aligned bits. */ 148 bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1); 149 } 150 255 151 } 256 152 257 153 /** Copy portion of one bitmap into another bitmap. 258 154 * 259 * @param dst Destination bitmap. 260 * @param src Source bitmap. 261 * @param count Number of bits to copy. 262 * 155 * @param dst Destination bitmap. 156 * @param src Source bitmap. 157 * @param bits Number of bits to copy. 263 158 */ 264 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count)159 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits) 265 160 { 266 ASSERT(count <= dst->elements);267 ASSERT(count <= src->elements);268 269 161 size_t i; 270 162 271 for (i = 0; i < count / BITMAP_ELEMENT; i++)272 dst->bits[i] = src->bits[i];163 ASSERT(bits <= dst->bits); 164 ASSERT(bits <= src->bits); 273 165 274 if (count % BITMAP_ELEMENT) { 275 bitmap_clear_range(dst, i * BITMAP_ELEMENT, 276 count % BITMAP_ELEMENT); 277 dst->bits[i] |= src->bits[i] & 278 ((1 << (count % BITMAP_ELEMENT)) - 1); 166 for (i = 0; i < bits / 8; i++) 167 dst->map[i] = src->map[i]; 168 169 if (bits % 8) { 170 bitmap_clear_range(dst, i * 8, bits % 8); 171 dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1); 279 172 } 280 }281 282 static int constraint_satisfy(size_t index, size_t base, size_t constraint)283 {284 return (((base + index) & constraint) == 0);285 }286 287 /** Find a continuous zero bit range288 *289 * Find a continuous zero bit range in the bitmap. The address290 * computed as the sum of the index of the first zero bit and291 * the base argument needs to be compliant with the constraint292 * (those bits that are set in the constraint cannot be set in293 * the address).294 *295 * If the index argument is non-NULL, the continuous zero range296 * is set and the index of the first bit is stored to index.297 * Otherwise the bitmap stays untouched.298 *299 * @param bitmap Bitmap structure.300 * @param count Number of continuous zero bits to find.301 * @param base Address of the first bit in the bitmap.302 * @param constraint Constraint for the address of the first zero bit.303 * @param index Place to store the index of the first zero304 * bit. Can be NULL (in which case the bitmap305 * is not modified).306 *307 * @return Non-zero if a continuous range of zero bits satisfying308 * the constraint has been found.309 * @return Zero otherwise.310 *311 */312 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base,313 size_t constraint, size_t *index)314 {315 if (count == 0)316 return false;317 318 /*319 * This is a trivial implementation that should be320 * optimized further.321 */322 323 for (size_t i = 0; i < bitmap->elements; i++) {324 if (!constraint_satisfy(i, base, constraint))325 continue;326 327 if (!bitmap_get(bitmap, i)) {328 bool continuous = true;329 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 }337 338 if (continuous) {339 if (index != NULL) {340 bitmap_set_range(bitmap, i, count);341 *index = i;342 }343 344 return true;345 }346 }347 348 }349 350 return false;351 }352 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 173 } 377 174
Note:
See TracChangeset
for help on using the changeset viewer.
