Index: kernel/arch/amd64/src/ddi/ddi.c =================================================================== --- kernel/arch/amd64/src/ddi/ddi.c (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/arch/amd64/src/ddi/ddi.c (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -42,4 +42,5 @@ #include #include +#include #include #include @@ -58,27 +59,28 @@ int ddi_iospace_enable_arch(task_t *task, uintptr_t ioaddr, size_t size) { - size_t bits = ioaddr + size; - if (bits > IO_PORTS) + size_t elements = ioaddr + size; + if (elements > IO_PORTS) return ENOENT; - if (task->arch.iomap.bits < bits) { + if (task->arch.iomap.elements < elements) { /* * The I/O permission bitmap is too small and needs to be grown. */ - uint8_t *newmap = (uint8_t *) malloc(BITS2BYTES(bits), FRAME_ATOMIC); - if (!newmap) + void *store = malloc(bitmap_size(elements, 0), FRAME_ATOMIC); + if (!store) return ENOMEM; bitmap_t oldiomap; - bitmap_initialize(&oldiomap, task->arch.iomap.map, + bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0, task->arch.iomap.bits); - bitmap_initialize(&task->arch.iomap, newmap, bits); + + bitmap_initialize(&task->arch.iomap, elements, 0, store); /* * Mark the new range inaccessible. */ - bitmap_set_range(&task->arch.iomap, oldiomap.bits, - bits - oldiomap.bits); + bitmap_set_range(&task->arch.iomap, oldiomap.elements, + elements - oldiomap.elements); /* @@ -88,6 +90,7 @@ if (oldiomap.bits) { bitmap_copy(&task->arch.iomap, &oldiomap, - oldiomap.bits); - free(oldiomap.map); + oldiomap.elements); + + free(oldiomap.bits); } } @@ -96,5 +99,5 @@ * Enable the range and we are done. */ - bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, (size_t) size); + bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, size); /* @@ -118,13 +121,15 @@ /* First, copy the I/O Permission Bitmap. */ irq_spinlock_lock(&TASK->lock, false); + size_t ver = TASK->arch.iomapver; - size_t bits = TASK->arch.iomap.bits; - if (bits) { - ASSERT(TASK->arch.iomap.map); + size_t elements = TASK->arch.iomap.elements; + + if (elements > 0) { + ASSERT(TASK->arch.iomap.bits); bitmap_t iomap; - bitmap_initialize(&iomap, CPU->arch.tss->iomap, - TSS_IOMAP_SIZE * 8); - bitmap_copy(&iomap, &TASK->arch.iomap, bits); + bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0, + CPU->arch.tss->iomap); + bitmap_copy(&iomap, &TASK->arch.iomap, elements); /* @@ -132,16 +137,19 @@ * I/O access. */ - bitmap_set_range(&iomap, bits, ALIGN_UP(bits, 8) - bits); + bitmap_set_range(&iomap, elements, + ALIGN_UP(elements, 8) - elements); + /* * It is safe to set the trailing eight bits because of the * extra convenience byte in TSS_IOMAP_SIZE. */ - bitmap_set_range(&iomap, ALIGN_UP(bits, 8), 8); + bitmap_set_range(&iomap, ALIGN_UP(elements, 8), 8); } + irq_spinlock_unlock(&TASK->lock, false); /* * Second, adjust TSS segment limit. - * Take the extra ending byte will all bits set into account. + * Take the extra ending byte with all bits set into account. */ ptr_16_64_t cpugdtr; @@ -149,5 +157,6 @@ descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base; - gdt_tss_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + BITS2BYTES(bits)); + size_t size = bitmap_size(elements, 0); + gdt_tss_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size); gdtr_load(&cpugdtr); Index: kernel/arch/amd64/src/proc/task.c =================================================================== --- kernel/arch/amd64/src/proc/task.c (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/arch/amd64/src/proc/task.c (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -34,6 +34,7 @@ #include +#include +#include #include -#include /** Perform amd64 specific task initialization. @@ -45,5 +46,5 @@ { task->arch.iomapver = 0; - bitmap_initialize(&task->arch.iomap, NULL, 0); + bitmap_initialize(&task->arch.iomap, 0, 0, NULL); } @@ -55,6 +56,6 @@ void task_destroy_arch(task_t *task) { - if (task->arch.iomap.map) - free(task->arch.iomap.map); + if (task->arch.iomap.bits != NULL) + free(task->arch.iomap.bits); } Index: kernel/arch/ia32/src/ddi/ddi.c =================================================================== --- kernel/arch/ia32/src/ddi/ddi.c (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/arch/ia32/src/ddi/ddi.c (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -59,27 +59,28 @@ int ddi_iospace_enable_arch(task_t *task, uintptr_t ioaddr, size_t size) { - size_t bits = ioaddr + size; - if (bits > IO_PORTS) + size_t elements = ioaddr + size; + if (elements > IO_PORTS) return ENOENT; - if (task->arch.iomap.bits < bits) { + if (task->arch.iomap.elements < elements) { /* * The I/O permission bitmap is too small and needs to be grown. */ - uint8_t *newmap = (uint8_t *) malloc(BITS2BYTES(bits), FRAME_ATOMIC); - if (!newmap) + void *store = malloc(bitmap_size(elements, 0), FRAME_ATOMIC); + if (!store) return ENOMEM; bitmap_t oldiomap; - bitmap_initialize(&oldiomap, task->arch.iomap.map, + bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0, task->arch.iomap.bits); - bitmap_initialize(&task->arch.iomap, newmap, bits); + + bitmap_initialize(&task->arch.iomap, elements, 0, store); /* * Mark the new range inaccessible. */ - bitmap_set_range(&task->arch.iomap, oldiomap.bits, - bits - oldiomap.bits); + bitmap_set_range(&task->arch.iomap, oldiomap.elements, + elements - oldiomap.elements); /* @@ -89,6 +90,7 @@ if (oldiomap.bits) { bitmap_copy(&task->arch.iomap, &oldiomap, - oldiomap.bits); - free(oldiomap.map); + oldiomap.elements); + + free(oldiomap.bits); } } @@ -97,5 +99,5 @@ * Enable the range and we are done. */ - bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, (size_t) size); + bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, size); /* @@ -119,13 +121,15 @@ /* First, copy the I/O Permission Bitmap. */ irq_spinlock_lock(&TASK->lock, false); + size_t ver = TASK->arch.iomapver; - size_t bits = TASK->arch.iomap.bits; - if (bits) { - ASSERT(TASK->arch.iomap.map); + size_t elements = TASK->arch.iomap.elements; + + if (elements > 0) { + ASSERT(TASK->arch.iomap.bits); bitmap_t iomap; - bitmap_initialize(&iomap, CPU->arch.tss->iomap, - TSS_IOMAP_SIZE * 8); - bitmap_copy(&iomap, &TASK->arch.iomap, bits); + bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0, + CPU->arch.tss->iomap); + bitmap_copy(&iomap, &TASK->arch.iomap, elements); /* @@ -133,11 +137,14 @@ * I/O access. */ - bitmap_set_range(&iomap, bits, ALIGN_UP(bits, 8) - bits); + bitmap_set_range(&iomap, elements, + ALIGN_UP(elements, 8) - elements); + /* * It is safe to set the trailing eight bits because of the * extra convenience byte in TSS_IOMAP_SIZE. */ - bitmap_set_range(&iomap, ALIGN_UP(bits, 8), 8); + bitmap_set_range(&iomap, ALIGN_UP(elements, 8), 8); } + irq_spinlock_unlock(&TASK->lock, false); @@ -150,5 +157,6 @@ descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base; - gdt_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + BITS2BYTES(bits)); + size_t size = bitmap_size(elements, 0); + gdt_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size); gdtr_load(&cpugdtr); Index: kernel/arch/ia32/src/proc/task.c =================================================================== --- kernel/arch/ia32/src/proc/task.c (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/arch/ia32/src/proc/task.c (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -40,20 +40,22 @@ /** Perform ia32 specific task initialization. * - * @param t Task to be initialized. + * @param task Task to be initialized. + * */ -void task_create_arch(task_t *t) +void task_create_arch(task_t *task) { - t->arch.iomapver = 0; - bitmap_initialize(&t->arch.iomap, NULL, 0); + task->arch.iomapver = 0; + bitmap_initialize(&task->arch.iomap, 0, 0, NULL); } /** Perform ia32 specific task destruction. * - * @param t Task to be initialized. + * @param task Task to be initialized. + * */ -void task_destroy_arch(task_t *t) +void task_destroy_arch(task_t *task) { - if (t->arch.iomap.map) - free(t->arch.iomap.map); + if (task->arch.iomap.bits != NULL) + free(task->arch.iomap.bits); } Index: kernel/arch/ia64/src/ddi/ddi.c =================================================================== --- kernel/arch/ia64/src/ddi/ddi.c (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/arch/ia64/src/ddi/ddi.c (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -56,11 +56,13 @@ { if (!task->arch.iomap) { - uint8_t *map; - task->arch.iomap = malloc(sizeof(bitmap_t), 0); - map = malloc(BITS2BYTES(IO_MEMMAP_PAGES), 0); - if(!map) + if (task->arch.iomap == NULL) return ENOMEM; - bitmap_initialize(task->arch.iomap, map, IO_MEMMAP_PAGES); + + void *store = malloc(bitmap_size(IO_MEMMAP_PAGES, 0), 0); + if (store == NULL) + return ENOMEM; + + bitmap_initialize(task->arch.iomap, IO_MEMMAP_PAGES, 0, store); bitmap_clear_range(task->arch.iomap, 0, IO_MEMMAP_PAGES); } @@ -69,5 +71,5 @@ size = ALIGN_UP(size + ioaddr - 4 * iopage, PORTS_PER_PAGE); bitmap_set_range(task->arch.iomap, iopage, size / 4); - + return 0; } Index: kernel/generic/include/adt/bitmap.h =================================================================== --- kernel/generic/include/adt/bitmap.h (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/generic/include/adt/bitmap.h (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -38,24 +38,60 @@ #include -#define BITS2BYTES(bits) (bits ? ((((bits)-1)>>3)+1) : 0) +#define BITMAP_ELEMENT 8 +#define BITMAP_REMAINER 7 typedef struct { - uint8_t *map; - size_t bits; + size_t elements; + uint8_t *bits; + + size_t block_size; + uint8_t *blocks; } bitmap_t; -extern void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits); -extern void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits); -extern void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits); -extern void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits); +static inline void bitmap_set(bitmap_t *bitmap, size_t element, + unsigned int value) +{ + if (element < bitmap->elements) { + /* + * The 2nd level bitmap is conservative. + * Make sure we update it properly. + */ + + if (value) { + bitmap->bits[element / BITMAP_ELEMENT] |= + (1 << (element & BITMAP_REMAINER)); + } else { + bitmap->bits[element / BITMAP_ELEMENT] &= + ~(1 << (element & BITMAP_REMAINER)); + + if (bitmap->block_size > 0) { + size_t block = element / bitmap->block_size; + + bitmap->blocks[block / BITMAP_ELEMENT] &= + ~(1 << (block & BITMAP_REMAINER)); + } + } + } +} -static inline int bitmap_get(bitmap_t *bitmap, size_t bit) +static inline unsigned int bitmap_get(bitmap_t *bitmap, size_t element) { - if(bit >= bitmap->bits) + if (element >= bitmap->elements) return 0; - return !! ((bitmap->map)[bit/8] & (1 << (bit & 7))); + return !!((bitmap->bits)[element / BITMAP_ELEMENT] & + (1 << (element & BITMAP_REMAINER))); } +extern size_t bitmap_size(size_t, size_t); +extern void bitmap_initialize(bitmap_t *, size_t, size_t, void *); + +extern void bitmap_set_range(bitmap_t *, size_t, size_t); +extern void bitmap_clear_range(bitmap_t *, size_t, size_t); + +extern int bitmap_find_range(bitmap_t *, size_t, size_t, size_t); +extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t *); +extern void bitmap_free_range(bitmap_t *, size_t, size_t); +extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t); #endif Index: kernel/generic/src/adt/bitmap.c =================================================================== --- kernel/generic/src/adt/bitmap.c (revision a74d0ad855d5ae331fcd2023dcc2b0281b01e5e9) +++ kernel/generic/src/adt/bitmap.c (revision 29a38862b6cc96276502b777fad3e3293d542fe2) @@ -35,5 +35,14 @@ * * This file implements bitmap ADT and provides functions for - * setting and clearing ranges of bits. + * setting and clearing ranges of bits and for finding ranges + * of unset bits. + * + * The bitmap ADT can optionally implement a two-level hierarchy + * for faster range searches. The second level bitmap (of blocks) + * is not precise, but conservative. This means that if the block + * bit is set, it guarantees that all bits in the block are set. + * But if the block bit is unset, nothing can be said about the + * bits in the block. + * */ @@ -44,6 +53,34 @@ #include -#define ALL_ONES 0xff -#define ALL_ZEROES 0x00 +#define ALL_ONES 0xff +#define ALL_ZEROES 0x00 + +/** Get bitmap size + * + * Return the size (in bytes) required for the bitmap. + * + * @param elements Number bits stored in bitmap. + * @param block_size Block size of the 2nd level bitmap. + * If set to zero, no 2nd level is used. + * + * @return Size (in bytes) required for the bitmap. + * + */ +size_t bitmap_size(size_t elements, size_t block_size) +{ + size_t size = elements / BITMAP_ELEMENT; + + if ((elements % BITMAP_ELEMENT) != 0) + size++; + + if (block_size > 0) { + size += elements / block_size; + + if ((elements % block_size) != 0) + size++; + } + + return size; +} /** Initialize bitmap. @@ -51,41 +88,49 @@ * No portion of the bitmap is set or cleared by this function. * - * @param bitmap Bitmap structure. - * @param map Address of the memory used to hold the map. - * @param bits Number of bits stored in bitmap. - */ -void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits) -{ - bitmap->map = map; - bitmap->bits = bits; -} - -/** Set range of bits. - * - * @param bitmap Bitmap structure. - * @param start Starting bit. - * @param bits Number of bits to set. - */ -void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits) -{ - size_t i = 0; - size_t aligned_start; - size_t lub; /* leading unaligned bits */ - size_t amb; /* aligned middle bits */ - size_t tab; /* trailing aligned bits */ - - ASSERT(start + bits <= bitmap->bits); - - aligned_start = ALIGN_UP(start, 8); - lub = min(aligned_start - start, bits); - amb = bits > lub ? bits - lub : 0; - tab = amb % 8; - - if (!bits) - return; - - if (start + bits < aligned_start) { + * @param bitmap Bitmap structure. + * @param elements Number of bits stored in bitmap. + * @param block_size Block size of the 2nd level bitmap. + * If set to zero, no 2nd level is used. + * @param data Address of the memory used to hold the map. + * The optional 2nd level bitmap follows the 1st + * level bitmap. + * + */ +void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, + void *data) +{ + bitmap->elements = elements; + bitmap->bits = (uint8_t *) data; + + if (block_size > 0) { + bitmap->block_size = block_size; + bitmap->blocks = bitmap->bits + + bitmap_size(elements, 0); + } else { + bitmap->block_size = 0; + bitmap->blocks = NULL; + } +} + +static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count) +{ + if (count == 0) + return; + + size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); + + /* Leading unaligned bits */ + size_t lub = min(aligned_start - start, count); + + /* Aligned middle bits */ + size_t amb = (count > lub) ? (count - lub) : 0; + + /* Trailing aligned bits */ + size_t tab = amb % BITMAP_ELEMENT; + + if (start + count < aligned_start) { /* Set bits in the middle of byte. */ - bitmap->map[start / 8] |= ((1 << lub) - 1) << (start & 7); + bits[start / BITMAP_ELEMENT] |= + ((1 << lub) - 1) << (start & BITMAP_REMAINER); return; } @@ -93,81 +138,143 @@ if (lub) { /* Make sure to set any leading unaligned bits. */ - bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1); - } - for (i = 0; i < amb / 8; i++) { + bits[start / BITMAP_ELEMENT] |= + ~((1 << (BITMAP_ELEMENT - lub)) - 1); + } + + size_t i; + + for (i = 0; i < amb / BITMAP_ELEMENT; i++) { /* The middle bits can be set byte by byte. */ - bitmap->map[aligned_start / 8 + i] = ALL_ONES; - } + bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES; + } + if (tab) { /* Make sure to set any trailing aligned bits. */ - bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1; - } - -} - -/** Clear range of bits. - * - * @param bitmap Bitmap structure. - * @param start Starting bit. - * @param bits Number of bits to clear. - */ -void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits) -{ - size_t i = 0; - size_t aligned_start; - size_t lub; /* leading unaligned bits */ - size_t amb; /* aligned middle bits */ - size_t tab; /* trailing aligned bits */ - - ASSERT(start + bits <= bitmap->bits); - - aligned_start = ALIGN_UP(start, 8); - lub = min(aligned_start - start, bits); - amb = bits > lub ? bits - lub : 0; - tab = amb % 8; - - if (!bits) - return; - - if (start + bits < aligned_start) { + bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1; + } +} + +/** Set range of bits. + * + * @param bitmap Bitmap structure. + * @param start Starting bit. + * @param count Number of bits to set. + * + */ +void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count) +{ + ASSERT(start + count <= bitmap->elements); + + bitmap_set_range_internal(bitmap->bits, start, count); + + if (bitmap->block_size > 0) { + size_t aligned_start = ALIGN_UP(start, bitmap->block_size); + + /* Leading unaligned bits */ + size_t lub = min(aligned_start - start, count); + + /* Aligned middle bits */ + size_t amb = (count > lub) ? (count - lub) : 0; + + size_t aligned_size = amb / bitmap->block_size; + + bitmap_set_range_internal(bitmap->blocks, aligned_start, + aligned_size); + } +} + +static void bitmap_clear_range_internal(uint8_t *bits, size_t start, + size_t count) +{ + if (count == 0) + return; + + size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); + + /* Leading unaligned bits */ + size_t lub = min(aligned_start - start, count); + + /* Aligned middle bits */ + size_t amb = (count > lub) ? (count - lub) : 0; + + /* Trailing aligned bits */ + size_t tab = amb % BITMAP_ELEMENT; + + if (start + count < aligned_start) { /* Set bits in the middle of byte */ - bitmap->map[start / 8] &= ~(((1 << lub) - 1) << (start & 7)); - return; - } - + bits[start / BITMAP_ELEMENT] &= + ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); + return; + } + if (lub) { /* Make sure to clear any leading unaligned bits. */ - bitmap->map[start / 8] &= (1 << (8 - lub)) - 1; - } - for (i = 0; i < amb / 8; i++) { + bits[start / BITMAP_ELEMENT] &= + (1 << (BITMAP_ELEMENT - lub)) - 1; + } + + size_t i; + + for (i = 0; i < amb / BITMAP_ELEMENT; i++) { /* The middle bits can be cleared byte by byte. */ - bitmap->map[aligned_start / 8 + i] = ALL_ZEROES; - } + bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; + } + if (tab) { /* Make sure to clear any trailing aligned bits. */ - bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1); - } - + bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); + } +} + +/** Clear range of bits. + * + * @param bitmap Bitmap structure. + * @param start Starting bit. + * @param count Number of bits to clear. + * + */ +void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count) +{ + ASSERT(start + count <= bitmap->elements); + + bitmap_clear_range_internal(bitmap->bits, start, count); + + if (bitmap->block_size > 0) { + size_t aligned_start = start / bitmap->block_size; + + size_t aligned_end = (start + count) / bitmap->block_size; + + if (((start + count) % bitmap->block_size) != 0) + aligned_end++; + + size_t aligned_size = aligned_end - aligned_start; + + bitmap_clear_range_internal(bitmap->blocks, aligned_start, + aligned_size); + } } /** Copy portion of one bitmap into another bitmap. * - * @param dst Destination bitmap. - * @param src Source bitmap. - * @param bits Number of bits to copy. - */ -void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits) -{ + * @param dst Destination bitmap. + * @param src Source bitmap. + * @param count Number of bits to copy. + * + */ +void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count) +{ + ASSERT(count <= dst->elements); + ASSERT(count <= src->elements); + size_t i; - ASSERT(bits <= dst->bits); - ASSERT(bits <= src->bits); - - for (i = 0; i < bits / 8; i++) - dst->map[i] = src->map[i]; - - if (bits % 8) { - bitmap_clear_range(dst, i * 8, bits % 8); - dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1); + for (i = 0; i < count / BITMAP_ELEMENT; i++) + dst->bits[i] = src->bits[i]; + + if (count % BITMAP_ELEMENT) { + bitmap_clear_range(dst, i * BITMAP_ELEMENT, + count % BITMAP_ELEMENT); + dst->bits[i] |= src->bits[i] & + ((1 << (count % BITMAP_ELEMENT)) - 1); } }