Index: kernel/generic/src/adt/bitmap.c =================================================================== --- kernel/generic/src/adt/bitmap.c (revision ef9a2a897b47371cfb43b8b8bb95ad044136eccf) +++ kernel/generic/src/adt/bitmap.c (revision e76fed96517738d2f3284f47ca00c2237183ff11) @@ -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); } } Index: kernel/generic/src/console/kconsole.c =================================================================== --- kernel/generic/src/console/kconsole.c (revision ef9a2a897b47371cfb43b8b8bb95ad044136eccf) +++ kernel/generic/src/console/kconsole.c (revision e76fed96517738d2f3284f47ca00c2237183ff11) @@ -53,5 +53,4 @@ #include #include -#include #include #include Index: kernel/generic/src/ddi/ddi.c =================================================================== --- kernel/generic/src/ddi/ddi.c (revision ef9a2a897b47371cfb43b8b8bb95ad044136eccf) +++ kernel/generic/src/ddi/ddi.c (revision e76fed96517738d2f3284f47ca00c2237183ff11) @@ -336,5 +336,5 @@ order = fnzb(pages - 1) + 1; - *phys = frame_alloc_noreserve(order, 0); + *phys = frame_alloc_noreserve(order, FRAME_DMA); if (*phys == NULL) return ENOMEM; @@ -361,6 +361,20 @@ NO_TRACE static int dmamem_unmap_anonymous(uintptr_t virt) { - // TODO: implement unlocking & unmap - return EOK; + // TODO: This is an ugly hack + as_t *as = TASK->as; + + mutex_lock(&as->lock); + as_area_t *area = find_locked_area(as, virt); + if (!area) { + mutex_unlock(&as->lock); + return ENOENT; + } + frame_free_noreserve(area->backend_data.base); + area->backend_data.base = 0; + area->backend_data.frames = 0; + mutex_unlock(&area->lock); + mutex_unlock(&as->lock); + + return as_area_destroy(as, virt); } Index: kernel/generic/src/mm/as.c =================================================================== --- kernel/generic/src/mm/as.c (revision ef9a2a897b47371cfb43b8b8bb95ad044136eccf) +++ kernel/generic/src/mm/as.c (revision e76fed96517738d2f3284f47ca00c2237183ff11) @@ -672,4 +672,11 @@ return NULL; +} + +/** UGLY! UGLY! UGLY! */ +// TODO: REMOVE ASAP! +as_area_t * find_locked_area(as_t *as, uintptr_t va) +{ + return find_area_and_lock(as, va); } Index: kernel/generic/src/mm/frame.c =================================================================== --- kernel/generic/src/mm/frame.c (revision ef9a2a897b47371cfb43b8b8bb95ad044136eccf) +++ kernel/generic/src/mm/frame.c (revision e76fed96517738d2f3284f47ca00c2237183ff11) @@ -518,5 +518,7 @@ NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t frame_idx) { - ASSERT(zone->flags & ZONE_AVAILABLE); + if (!(zone->flags & ZONE_AVAILABLE)) + return; +// ASSERT(zone->flags & ZONE_AVAILABLE); frame_t *frame = zone_get_frame(zone, frame_idx); @@ -935,6 +937,9 @@ } - if (confframe >= start + count) - panic("Cannot find configuration data for zone."); + if (confframe >= start + count) { + flags &= ~ZONE_AVAILABLE; + goto nonavail; +// panic("Cannot find configuration data for zone."); + } } @@ -960,5 +965,6 @@ return znum; } - +nonavail: + (void)0; // label trick /* Non-available zone */ size_t znum = zones_insert_zone(start, count, flags);