Changes in kernel/generic/src/adt/bitmap.c [7de18418:6e75f2d] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/adt/bitmap.c (modified) (11 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
r7de18418 r6e75f2d 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 … … 280 238 } 281 239 240 static int constraint_satisfy(size_t index, size_t base, size_t constraint) 241 { 242 return (((base + index) & constraint) == 0); 243 } 244 245 /** Find a continuous zero bit range 246 * 247 * Find a continuous zero bit range in the bitmap. The address 248 * computed as the sum of the index of the first zero bit and 249 * the base argument needs to be compliant with the constraint 250 * (those bits that are set in the constraint cannot be set in 251 * the address). 252 * 253 * If the index argument is non-NULL, the continuous zero range 254 * is set and the index of the first bit is stored to index. 255 * Otherwise the bitmap stays untouched. 256 * 257 * @param bitmap Bitmap structure. 258 * @param count Number of continuous zero bits to find. 259 * @param base Address of the first bit in the bitmap. 260 * @param constraint Constraint for the address of the first zero bit. 261 * @param index Place to store the index of the first zero 262 * bit. Can be NULL (in which case the bitmap 263 * is not modified). 264 * 265 * @return Non-zero if a continuous range of zero bits satisfying 266 * the constraint has been found. 267 * @return Zero otherwise. 268 * 269 */ 270 int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base, 271 size_t constraint, size_t *index) 272 { 273 if (count == 0) 274 return false; 275 276 size_t size = bitmap_size(bitmap->elements); 277 278 for (size_t pos = 0; pos < size; pos++) { 279 size_t byte = (bitmap->next_fit + pos) % size; 280 281 /* Skip if the current byte has all bits set */ 282 if (bitmap->bits[byte] == ALL_ONES) 283 continue; 284 285 size_t byte_bit = byte * BITMAP_ELEMENT; 286 287 for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) { 288 size_t i = byte_bit + bit; 289 290 if (i >= bitmap->elements) 291 break; 292 293 if (!constraint_satisfy(i, base, constraint)) 294 continue; 295 296 if (!bitmap_get_fast(bitmap, i)) { 297 size_t continuous = 1; 298 299 for (size_t j = 1; j < count; j++) { 300 if ((i + j < bitmap->elements) && 301 (!bitmap_get_fast(bitmap, i + j))) 302 continuous++; 303 else 304 break; 305 } 306 307 if (continuous == count) { 308 if (index != NULL) { 309 bitmap_set_range(bitmap, i, count); 310 bitmap->next_fit = i / BITMAP_ELEMENT; 311 *index = i; 312 } 313 314 return true; 315 } else 316 i += continuous; 317 } 318 } 319 } 320 321 return false; 322 } 323 282 324 /** @} 283 325 */
Note:
See TracChangeset
for help on using the changeset viewer.
