Changes in kernel/generic/src/adt/bitmap.c [6e75f2d:7de18418] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/adt/bitmap.c (modified) (11 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/bitmap.c
r6e75f2d r7de18418 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 … … 238 280 } 239 281 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 range246 *247 * Find a continuous zero bit range in the bitmap. The address248 * computed as the sum of the index of the first zero bit and249 * the base argument needs to be compliant with the constraint250 * (those bits that are set in the constraint cannot be set in251 * the address).252 *253 * If the index argument is non-NULL, the continuous zero range254 * 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 zero262 * bit. Can be NULL (in which case the bitmap263 * is not modified).264 *265 * @return Non-zero if a continuous range of zero bits satisfying266 * 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 else304 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 } else316 i += continuous;317 }318 }319 }320 321 return false;322 }323 324 282 /** @} 325 283 */
Note:
See TracChangeset
for help on using the changeset viewer.
