Changeset c5396c1 in mainline
- Timestamp:
- 2013-09-12T10:27:17Z (11 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 6e75f2d
- Parents:
- 4a5f2b0
- Location:
- kernel
- Files:
-
- 8 edited
-
arch/amd64/src/ddi/ddi.c (modified) (3 diffs)
-
arch/amd64/src/proc/task.c (modified) (1 diff)
-
arch/ia32/src/ddi/ddi.c (modified) (3 diffs)
-
arch/ia32/src/proc/task.c (modified) (1 diff)
-
arch/ia64/src/ddi/ddi.c (modified) (1 diff)
-
generic/include/adt/bitmap.h (modified) (3 diffs)
-
generic/src/adt/bitmap.c (modified) (11 diffs)
-
generic/src/mm/frame.c (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/arch/amd64/src/ddi/ddi.c
r4a5f2b0 rc5396c1 68 68 */ 69 69 70 void *store = malloc(bitmap_size(elements , 0), FRAME_ATOMIC);70 void *store = malloc(bitmap_size(elements), FRAME_ATOMIC); 71 71 if (!store) 72 72 return ENOMEM; 73 73 74 74 bitmap_t oldiomap; 75 bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0,75 bitmap_initialize(&oldiomap, task->arch.iomap.elements, 76 76 task->arch.iomap.bits); 77 77 78 bitmap_initialize(&task->arch.iomap, elements, 0,store);78 bitmap_initialize(&task->arch.iomap, elements, store); 79 79 80 80 /* … … 129 129 130 130 bitmap_t iomap; 131 bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0,131 bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 132 132 CPU->arch.tss->iomap); 133 133 bitmap_copy(&iomap, &TASK->arch.iomap, elements); … … 157 157 158 158 descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base; 159 size_t size = bitmap_size(elements , 0);159 size_t size = bitmap_size(elements); 160 160 gdt_tss_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size); 161 161 gdtr_load(&cpugdtr); -
kernel/arch/amd64/src/proc/task.c
r4a5f2b0 rc5396c1 46 46 { 47 47 task->arch.iomapver = 0; 48 bitmap_initialize(&task->arch.iomap, 0, 0,NULL);48 bitmap_initialize(&task->arch.iomap, 0, NULL); 49 49 } 50 50 -
kernel/arch/ia32/src/ddi/ddi.c
r4a5f2b0 rc5396c1 68 68 */ 69 69 70 void *store = malloc(bitmap_size(elements , 0), FRAME_ATOMIC);70 void *store = malloc(bitmap_size(elements), FRAME_ATOMIC); 71 71 if (!store) 72 72 return ENOMEM; 73 73 74 74 bitmap_t oldiomap; 75 bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0,75 bitmap_initialize(&oldiomap, task->arch.iomap.elements, 76 76 task->arch.iomap.bits); 77 77 78 bitmap_initialize(&task->arch.iomap, elements, 0,store);78 bitmap_initialize(&task->arch.iomap, elements, store); 79 79 80 80 /* … … 129 129 130 130 bitmap_t iomap; 131 bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0,131 bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 132 132 CPU->arch.tss->iomap); 133 133 bitmap_copy(&iomap, &TASK->arch.iomap, elements); … … 157 157 158 158 descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base; 159 size_t size = bitmap_size(elements , 0);159 size_t size = bitmap_size(elements); 160 160 gdt_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size); 161 161 gdtr_load(&cpugdtr); -
kernel/arch/ia32/src/proc/task.c
r4a5f2b0 rc5396c1 46 46 { 47 47 task->arch.iomapver = 0; 48 bitmap_initialize(&task->arch.iomap, 0, 0,NULL);48 bitmap_initialize(&task->arch.iomap, 0, NULL); 49 49 } 50 50 -
kernel/arch/ia64/src/ddi/ddi.c
r4a5f2b0 rc5396c1 60 60 return ENOMEM; 61 61 62 void *store = malloc(bitmap_size(IO_MEMMAP_PAGES , 0), 0);62 void *store = malloc(bitmap_size(IO_MEMMAP_PAGES), 0); 63 63 if (store == NULL) 64 64 return ENOMEM; 65 65 66 bitmap_initialize(task->arch.iomap, IO_MEMMAP_PAGES, 0,store);66 bitmap_initialize(task->arch.iomap, IO_MEMMAP_PAGES, store); 67 67 bitmap_clear_range(task->arch.iomap, 0, IO_MEMMAP_PAGES); 68 68 } -
kernel/generic/include/adt/bitmap.h
r4a5f2b0 rc5396c1 44 44 size_t elements; 45 45 uint8_t *bits; 46 47 size_t block_size;48 uint8_t *blocks;49 46 } bitmap_t; 50 47 … … 52 49 unsigned int value) 53 50 { 54 if (element < bitmap->elements) { 55 /* 56 * The 2nd level bitmap is conservative. 57 * Make sure we update it properly. 58 */ 59 60 if (value) { 61 bitmap->bits[element / BITMAP_ELEMENT] |= 62 (1 << (element & BITMAP_REMAINER)); 63 } else { 64 bitmap->bits[element / BITMAP_ELEMENT] &= 65 ~(1 << (element & BITMAP_REMAINER)); 66 67 if (bitmap->block_size > 0) { 68 size_t block = element / bitmap->block_size; 69 70 bitmap->blocks[block / BITMAP_ELEMENT] &= 71 ~(1 << (block & BITMAP_REMAINER)); 72 } 73 } 51 if (element >= bitmap->elements) 52 return; 53 54 size_t byte = element / BITMAP_ELEMENT; 55 uint8_t mask = 1 << (element & BITMAP_REMAINER); 56 57 if (value) { 58 bitmap->bits[byte] |= mask; 59 } else { 60 bitmap->bits[byte] &= ~mask; 74 61 } 75 62 } … … 80 67 return 0; 81 68 82 return !!((bitmap->bits)[element / BITMAP_ELEMENT] & 83 (1 << (element & BITMAP_REMAINER))); 69 size_t byte = element / BITMAP_ELEMENT; 70 uint8_t mask = 1 << (element & BITMAP_REMAINER); 71 72 return !!((bitmap->bits)[byte] & mask); 84 73 } 85 74 86 extern size_t bitmap_size(size_t , size_t);87 extern void bitmap_initialize(bitmap_t *, size_t, size_t,void *);75 extern size_t bitmap_size(size_t); 76 extern void bitmap_initialize(bitmap_t *, size_t, void *); 88 77 89 78 extern void bitmap_set_range(bitmap_t *, size_t, size_t); -
kernel/generic/src/adt/bitmap.c
r4a5f2b0 rc5396c1 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 58 /** Compute the size of a bitmap59 *60 * Compute the size of a bitmap that can store given number61 * of elements.62 *63 * @param elements Number of elements to store.64 *65 * @return Size of the bitmap (in units of BITMAP_ELEMENT bits).66 *67 */68 static size_t bitmap_bytes(size_t elements)69 {70 size_t bytes = elements / BITMAP_ELEMENT;71 72 if ((elements % BITMAP_ELEMENT) != 0)73 bytes++;74 75 return bytes;76 }77 78 /** Compute the number of 2nd level blocks79 *80 * Compute the number of 2nd level blocks for a given number81 * of elements.82 *83 * @param elements Number of elements.84 * @param block_size Number of elements in one block.85 *86 * @return Number of 2nd level blocks.87 * @return Zero if block_size is zero.88 *89 */90 static size_t bitmap_blocks(size_t elements, size_t block_size)91 {92 if (block_size == 0)93 return 0;94 95 size_t blocks = elements / block_size;96 97 if ((elements % block_size) != 0)98 blocks++;99 100 return blocks;101 }102 103 50 /** Unchecked version of bitmap_get() 104 51 * … … 113 60 static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element) 114 61 { 115 return !!((bitmap->bits)[element / BITMAP_ELEMENT] & 116 (1 << (element & BITMAP_REMAINER))); 62 size_t byte = element / BITMAP_ELEMENT; 63 uint8_t mask = 1 << (element & BITMAP_REMAINER); 64 65 return !!((bitmap->bits)[byte] & mask); 117 66 } 118 67 … … 122 71 * 123 72 * @param elements Number bits stored in bitmap. 124 * @param block_size Block size of the 2nd level bitmap.125 * If set to zero, no 2nd level is used.126 73 * 127 74 * @return Size (in bytes) required for the bitmap. 128 75 * 129 76 */ 130 size_t bitmap_size(size_t elements, size_t block_size) 131 { 132 size_t blocks = bitmap_blocks(elements, block_size); 133 134 return (bitmap_bytes(elements) + bitmap_bytes(blocks)); 77 size_t bitmap_size(size_t elements) 78 { 79 size_t size = elements / BITMAP_ELEMENT; 80 81 if ((elements % BITMAP_ELEMENT) != 0) 82 size++; 83 84 return size; 135 85 } 136 86 … … 141 91 * @param bitmap Bitmap structure. 142 92 * @param elements Number of bits stored in bitmap. 143 * @param block_size Block size of the 2nd level bitmap.144 * If set to zero, no 2nd level is used.145 93 * @param data Address of the memory used to hold the map. 146 94 * The optional 2nd level bitmap follows the 1st … … 148 96 * 149 97 */ 150 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, 151 void *data) 98 void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data) 152 99 { 153 100 bitmap->elements = elements; 154 101 bitmap->bits = (uint8_t *) data; 155 156 if (block_size > 0) {157 bitmap->block_size = block_size;158 bitmap->blocks = bitmap->bits +159 bitmap_size(elements, 0);160 } else {161 bitmap->block_size = 0;162 bitmap->blocks = NULL;163 }164 }165 166 static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count)167 {168 if (count == 0)169 return;170 171 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);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 /* Trailing aligned bits */180 size_t tab = amb % BITMAP_ELEMENT;181 182 if (start + count < aligned_start) {183 /* Set bits in the middle of byte. */184 bits[start / BITMAP_ELEMENT] |=185 ((1 << lub) - 1) << (start & BITMAP_REMAINER);186 return;187 }188 189 if (lub) {190 /* Make sure to set any leading unaligned bits. */191 bits[start / BITMAP_ELEMENT] |=192 ~((1 << (BITMAP_ELEMENT - lub)) - 1);193 }194 195 size_t i;196 197 for (i = 0; i < amb / BITMAP_ELEMENT; i++) {198 /* The middle bits can be set byte by byte. */199 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES;200 }201 202 if (tab) {203 /* Make sure to set any trailing aligned bits. */204 bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1;205 }206 102 } 207 103 … … 217 113 ASSERT(start + count <= bitmap->elements); 218 114 219 bitmap_set_range_internal(bitmap->bits, start, count);220 221 if (bitmap->block_size > 0) {222 size_t aligned_start = ALIGN_UP(start, bitmap->block_size);223 224 /* Leading unaligned bits */225 size_t lub = min(aligned_start - start, count);226 227 /* Aligned middle bits */228 size_t amb = (count > lub) ? (count - lub) : 0;229 230 size_t aligned_size = amb / bitmap->block_size;231 232 bitmap_set_range_internal(bitmap->blocks, aligned_start,233 aligned_size);234 }235 }236 237 static void bitmap_clear_range_internal(uint8_t *bits, size_t start,238 size_t count)239 {240 115 if (count == 0) 241 116 return; … … 253 128 254 129 if (start + count < aligned_start) { 255 /* Set bits in the middle of byte */256 bit s[start / BITMAP_ELEMENT] &=257 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));130 /* Set bits in the middle of byte. */ 131 bitmap->bits[start / BITMAP_ELEMENT] |= 132 ((1 << lub) - 1) << (start & BITMAP_REMAINER); 258 133 return; 259 134 } 260 135 261 136 if (lub) { 262 /* Make sure to clearany leading unaligned bits. */263 bit s[start / BITMAP_ELEMENT] &=264 (1 << (BITMAP_ELEMENT - lub)) - 1;137 /* Make sure to set any leading unaligned bits. */ 138 bitmap->bits[start / BITMAP_ELEMENT] |= 139 ~((1 << (BITMAP_ELEMENT - lub)) - 1); 265 140 } 266 141 … … 268 143 269 144 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 270 /* The middle bits can be cleared byte by byte. */ 271 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; 145 /* The middle bits can be set byte by byte. */ 146 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 147 ALL_ONES; 272 148 } 273 149 274 150 if (tab) { 275 /* Make sure to clear any trailing aligned bits. */ 276 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); 151 /* Make sure to set any trailing aligned bits. */ 152 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |= 153 (1 << tab) - 1; 277 154 } 278 155 } … … 289 166 ASSERT(start + count <= bitmap->elements); 290 167 291 bitmap_clear_range_internal(bitmap->bits, start, count); 292 293 if (bitmap->block_size > 0) { 294 size_t aligned_start = start / bitmap->block_size; 295 296 size_t aligned_end = (start + count) / bitmap->block_size; 297 298 if (((start + count) % bitmap->block_size) != 0) 299 aligned_end++; 300 301 size_t aligned_size = aligned_end - aligned_start; 302 303 bitmap_clear_range_internal(bitmap->blocks, aligned_start, 304 aligned_size); 168 if (count == 0) 169 return; 170 171 size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); 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 /* Trailing aligned bits */ 180 size_t tab = amb % BITMAP_ELEMENT; 181 182 if (start + count < aligned_start) { 183 /* Set bits in the middle of byte */ 184 bitmap->bits[start / BITMAP_ELEMENT] &= 185 ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); 186 return; 187 } 188 189 if (lub) { 190 /* Make sure to clear any leading unaligned bits. */ 191 bitmap->bits[start / BITMAP_ELEMENT] &= 192 (1 << (BITMAP_ELEMENT - lub)) - 1; 193 } 194 195 size_t i; 196 197 for (i = 0; i < amb / BITMAP_ELEMENT; i++) { 198 /* The middle bits can be cleared byte by byte. */ 199 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = 200 ALL_ZEROES; 201 } 202 203 if (tab) { 204 /* Make sure to clear any trailing aligned bits. */ 205 bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &= 206 ~((1 << tab) - 1); 305 207 } 306 208 } … … 367 269 return false; 368 270 369 size_t bytes = bitmap_ bytes(bitmap->elements);271 size_t bytes = bitmap_size(bitmap->elements); 370 272 371 273 for (size_t byte = 0; byte < bytes; byte++) { -
kernel/generic/src/mm/frame.c
r4a5f2b0 rc5396c1 60 60 #include <config.h> 61 61 #include <str.h> 62 63 #define BITMAP_BLOCK_SIZE 12864 62 65 63 zones_t zones; … … 410 408 411 409 bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count, 412 BITMAP_BLOCK_SIZE, confdata + 413 (sizeof(frame_t) * zones.info[z1].count)); 410 confdata + (sizeof(frame_t) * zones.info[z1].count)); 414 411 bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count); 415 412 … … 578 575 */ 579 576 580 bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE,581 confdata +(sizeof(frame_t) * count));577 bitmap_initialize(&zone->bitmap, count, confdata + 578 (sizeof(frame_t) * count)); 582 579 bitmap_clear_range(&zone->bitmap, 0, count); 583 580 … … 591 588 frame_initialize(&zone->frames[i]); 592 589 } else { 593 bitmap_initialize(&zone->bitmap, 0, 0,NULL);590 bitmap_initialize(&zone->bitmap, 0, NULL); 594 591 zone->frames = NULL; 595 592 } … … 605 602 size_t zone_conf_size(size_t count) 606 603 { 607 return (count * sizeof(frame_t) + 608 bitmap_size(count, BITMAP_BLOCK_SIZE)); 604 return (count * sizeof(frame_t) + bitmap_size(count)); 609 605 } 610 606
Note:
See TracChangeset
for help on using the changeset viewer.
