Index: kernel/generic/include/adt/bitmap.h =================================================================== --- kernel/generic/include/adt/bitmap.h (revision 64f3d3b30214b99ffdce5634420154819c802b37) +++ kernel/generic/include/adt/bitmap.h (revision c5396c1804ab53d2d15266e72be0b0617bebb8b3) @@ -44,7 +44,4 @@ size_t elements; uint8_t *bits; - - size_t block_size; - uint8_t *blocks; } bitmap_t; @@ -52,24 +49,14 @@ 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)); - } - } + if (element >= bitmap->elements) + return; + + size_t byte = element / BITMAP_ELEMENT; + uint8_t mask = 1 << (element & BITMAP_REMAINER); + + if (value) { + bitmap->bits[byte] |= mask; + } else { + bitmap->bits[byte] &= ~mask; } } @@ -80,10 +67,12 @@ return 0; - return !!((bitmap->bits)[element / BITMAP_ELEMENT] & - (1 << (element & BITMAP_REMAINER))); + size_t byte = element / BITMAP_ELEMENT; + uint8_t mask = 1 << (element & BITMAP_REMAINER); + + return !!((bitmap->bits)[byte] & mask); } -extern size_t bitmap_size(size_t, size_t); -extern void bitmap_initialize(bitmap_t *, size_t, size_t, void *); +extern size_t bitmap_size(size_t); +extern void bitmap_initialize(bitmap_t *, size_t, void *); extern void bitmap_set_range(bitmap_t *, size_t, size_t); Index: kernel/generic/src/adt/bitmap.c =================================================================== --- kernel/generic/src/adt/bitmap.c (revision 64f3d3b30214b99ffdce5634420154819c802b37) +++ kernel/generic/src/adt/bitmap.c (revision c5396c1804ab53d2d15266e72be0b0617bebb8b3) @@ -37,12 +37,4 @@ * 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. - * */ @@ -56,49 +48,4 @@ #define ALL_ZEROES 0x00 -/** Compute the size of a bitmap - * - * Compute the size of a bitmap that can store given number - * of elements. - * - * @param elements Number of elements to store. - * - * @return Size of the bitmap (in units of BITMAP_ELEMENT bits). - * - */ -static size_t bitmap_bytes(size_t elements) -{ - size_t bytes = elements / BITMAP_ELEMENT; - - if ((elements % BITMAP_ELEMENT) != 0) - bytes++; - - return bytes; -} - -/** Compute the number of 2nd level blocks - * - * Compute the number of 2nd level blocks for a given number - * of elements. - * - * @param elements Number of elements. - * @param block_size Number of elements in one block. - * - * @return Number of 2nd level blocks. - * @return Zero if block_size is zero. - * - */ -static size_t bitmap_blocks(size_t elements, size_t block_size) -{ - if (block_size == 0) - return 0; - - size_t blocks = elements / block_size; - - if ((elements % block_size) != 0) - blocks++; - - return blocks; -} - /** Unchecked version of bitmap_get() * @@ -113,6 +60,8 @@ static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element) { - return !!((bitmap->bits)[element / BITMAP_ELEMENT] & - (1 << (element & BITMAP_REMAINER))); + size_t byte = element / BITMAP_ELEMENT; + uint8_t mask = 1 << (element & BITMAP_REMAINER); + + return !!((bitmap->bits)[byte] & mask); } @@ -122,15 +71,16 @@ * * @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 blocks = bitmap_blocks(elements, block_size); - - return (bitmap_bytes(elements) + bitmap_bytes(blocks)); +size_t bitmap_size(size_t elements) +{ + size_t size = elements / BITMAP_ELEMENT; + + if ((elements % BITMAP_ELEMENT) != 0) + size++; + + return size; } @@ -141,6 +91,4 @@ * @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 @@ -148,60 +96,8 @@ * */ -void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size, - void *data) +void bitmap_initialize(bitmap_t *bitmap, size_t elements, 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. */ - bits[start / BITMAP_ELEMENT] |= - ((1 << lub) - 1) << (start & BITMAP_REMAINER); - return; - } - - if (lub) { - /* Make sure to set any leading unaligned bits. */ - 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. */ - bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES; - } - - if (tab) { - /* Make sure to set any trailing aligned bits. */ - bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1; - } } @@ -217,25 +113,4 @@ 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; @@ -253,14 +128,14 @@ if (start + count < aligned_start) { - /* Set bits in the middle of byte */ - bits[start / BITMAP_ELEMENT] &= - ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); + /* Set bits in the middle of byte. */ + bitmap->bits[start / BITMAP_ELEMENT] |= + ((1 << lub) - 1) << (start & BITMAP_REMAINER); return; } if (lub) { - /* Make sure to clear any leading unaligned bits. */ - bits[start / BITMAP_ELEMENT] &= - (1 << (BITMAP_ELEMENT - lub)) - 1; + /* Make sure to set any leading unaligned bits. */ + bitmap->bits[start / BITMAP_ELEMENT] |= + ~((1 << (BITMAP_ELEMENT - lub)) - 1); } @@ -268,11 +143,13 @@ for (i = 0; i < amb / BITMAP_ELEMENT; i++) { - /* The middle bits can be cleared byte by byte. */ - bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES; + /* The middle bits can be set byte by byte. */ + bitmap->bits[aligned_start / BITMAP_ELEMENT + i] = + ALL_ONES; } if (tab) { - /* Make sure to clear any trailing aligned bits. */ - bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1); + /* Make sure to set any trailing aligned bits. */ + bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |= + (1 << tab) - 1; } } @@ -289,18 +166,43 @@ 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); + 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->bits[start / BITMAP_ELEMENT] &= + ~(((1 << lub) - 1) << (start & BITMAP_REMAINER)); + return; + } + + if (lub) { + /* Make sure to clear any leading unaligned bits. */ + bitmap->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->bits[aligned_start / BITMAP_ELEMENT + i] = + ALL_ZEROES; + } + + if (tab) { + /* Make sure to clear any trailing aligned bits. */ + bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &= + ~((1 << tab) - 1); } } @@ -367,5 +269,5 @@ return false; - size_t bytes = bitmap_bytes(bitmap->elements); + size_t bytes = bitmap_size(bitmap->elements); for (size_t byte = 0; byte < bytes; byte++) { Index: kernel/generic/src/mm/frame.c =================================================================== --- kernel/generic/src/mm/frame.c (revision 64f3d3b30214b99ffdce5634420154819c802b37) +++ kernel/generic/src/mm/frame.c (revision c5396c1804ab53d2d15266e72be0b0617bebb8b3) @@ -60,6 +60,4 @@ #include #include - -#define BITMAP_BLOCK_SIZE 128 zones_t zones; @@ -410,6 +408,5 @@ bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count, - BITMAP_BLOCK_SIZE, confdata + - (sizeof(frame_t) * zones.info[z1].count)); + confdata + (sizeof(frame_t) * zones.info[z1].count)); bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count); @@ -578,6 +575,6 @@ */ - bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE, - confdata + (sizeof(frame_t) * count)); + bitmap_initialize(&zone->bitmap, count, confdata + + (sizeof(frame_t) * count)); bitmap_clear_range(&zone->bitmap, 0, count); @@ -591,5 +588,5 @@ frame_initialize(&zone->frames[i]); } else { - bitmap_initialize(&zone->bitmap, 0, 0, NULL); + bitmap_initialize(&zone->bitmap, 0, NULL); zone->frames = NULL; } @@ -605,6 +602,5 @@ size_t zone_conf_size(size_t count) { - return (count * sizeof(frame_t) + - bitmap_size(count, BITMAP_BLOCK_SIZE)); + return (count * sizeof(frame_t) + bitmap_size(count)); }