|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Minios-devel] [UNIKRAFT PATCH v2] lib/ukallocbbuddy: Correct region bitmap allocation and usage
Hey Costin,
there are some comments inline.
-Yuri.
Costin Lupu <costin.lupu@xxxxxxxxx> writes:
> The usage of a each memory region that is added to the binary
> buddy allocator is tracked with a bitmap. This patch corrects
> wrong size calculation for the bitmap and wrong calculations
> of bit postitions.
>
> Signed-off-by: Costin Lupu <costin.lupu@xxxxxxxxx>
> ---
> lib/ukallocbbuddy/bbuddy.c | 83
> +++++++++++++++++++++++++++++++---------------
> 1 file changed, 57 insertions(+), 26 deletions(-)
>
> diff --git a/lib/ukallocbbuddy/bbuddy.c b/lib/ukallocbbuddy/bbuddy.c
> index 20a9b70..63288f0 100644
> --- a/lib/ukallocbbuddy/bbuddy.c
> +++ b/lib/ukallocbbuddy/bbuddy.c
> @@ -69,7 +69,7 @@ struct uk_bbpalloc_memr {
> unsigned long first_page;
> unsigned long nr_pages;
> unsigned long mm_alloc_bitmap_size;
> - unsigned long mm_alloc_bitmap[];
> + unsigned long *mm_alloc_bitmap;
> };
>
> struct uk_bbpalloc {
> @@ -93,10 +93,11 @@ struct uk_bbpalloc {
> * *_idx == Index into `mm_alloc_bitmap' array.
> * *_off == Bit offset within an element of the `mm_alloc_bitmap' array.
> */
> -#define PAGES_PER_MAPWORD (sizeof(unsigned long) * 8)
> +#define BITS_PER_BYTE 8
> +#define PAGES_PER_MAPWORD (sizeof(unsigned long) * BITS_PER_BYTE)
>
> static inline struct uk_bbpalloc_memr *map_get_memr(struct uk_bbpalloc *b,
> - unsigned long page_num)
> + unsigned long page_va)
> {
> struct uk_bbpalloc_memr *memr = NULL;
>
> @@ -106,8 +107,9 @@ static inline struct uk_bbpalloc_memr
> *map_get_memr(struct uk_bbpalloc *b,
> * of them. It should be just one region in most cases
> */
> for (memr = b->memr_head; memr != NULL; memr = memr->next) {
> - if ((page_num >= memr->first_page)
> - && (page_num < (memr->first_page + memr->nr_pages)))
> + if ((page_va >= memr->first_page)
> + && (page_va < (memr->first_page +
> + memr->nr_pages * __PAGE_SIZE)))
Is not a huge performance improvement, but better to use
memr->nr_pages << __PAGE_SHIFT
> return memr;
> }
>
> @@ -117,24 +119,29 @@ static inline struct uk_bbpalloc_memr
> *map_get_memr(struct uk_bbpalloc *b,
> return NULL;
> }
>
> -static inline int allocated_in_map(struct uk_bbpalloc *b,
> - unsigned long page_num)
> +static inline unsigned long allocated_in_map(struct uk_bbpalloc *b,
> + unsigned long page_va)
> {
> - struct uk_bbpalloc_memr *memr = map_get_memr(b, page_num);
> + struct uk_bbpalloc_memr *memr = map_get_memr(b, page_va);
> + unsigned long page_idx;
> + unsigned long bm_idx, bm_off;
>
> /* treat pages outside of region as allocated */
> if (!memr)
> return 1;
>
> - page_num -= memr->first_page;
> - return ((memr)->mm_alloc_bitmap[(page_num) / PAGES_PER_MAPWORD]
> - & (1UL << ((page_num) & (PAGES_PER_MAPWORD - 1))));
> + page_idx = (page_va - memr->first_page) / __PAGE_SIZE;
> + bm_idx = page_idx / PAGES_PER_MAPWORD;
> + bm_off = page_idx & (PAGES_PER_MAPWORD - 1);
> +
> + return ((memr)->mm_alloc_bitmap[bm_idx] & (1UL << bm_off));
> }
>
> static void map_alloc(struct uk_bbpalloc *b, uintptr_t first_page,
> unsigned long nr_pages)
> {
> struct uk_bbpalloc_memr *memr;
> + unsigned long first_page_idx, end_page_idx;
> unsigned long start_off, end_off, curr_idx, end_idx;
>
> /*
> @@ -144,14 +151,16 @@ static void map_alloc(struct uk_bbpalloc *b, uintptr_t
> first_page,
> */
> memr = map_get_memr(b, first_page);
> UK_ASSERT(memr != NULL);
> - UK_ASSERT((first_page + nr_pages)
> - <= (memr->first_page + memr->nr_pages));
> + UK_ASSERT((first_page + nr_pages * __PAGE_SIZE)
> + <= (memr->first_page + memr->nr_pages * __PAGE_SIZE));
>
> first_page -= memr->first_page;
> - curr_idx = first_page / PAGES_PER_MAPWORD;
> - start_off = first_page & (PAGES_PER_MAPWORD - 1);
> - end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
> - end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD - 1);
> + first_page_idx = first_page / __PAGE_SIZE;
> + curr_idx = first_page_idx / PAGES_PER_MAPWORD;
> + start_off = first_page_idx & (PAGES_PER_MAPWORD - 1);
> + end_page_idx = first_page_idx + nr_pages;
> + end_idx = end_page_idx / PAGES_PER_MAPWORD;
> + end_off = end_page_idx & (PAGES_PER_MAPWORD - 1);
Same preference of shifts over divisions. I stop pointing it out here,
but I think using shift in other places in the code would improve a
little bit performance, and readability.
>
> if (curr_idx == end_idx) {
> memr->mm_alloc_bitmap[curr_idx] |=
> @@ -170,6 +179,7 @@ static void map_free(struct uk_bbpalloc *b, uintptr_t
> first_page,
> unsigned long nr_pages)
> {
> struct uk_bbpalloc_memr *memr;
> + unsigned long first_page_idx, end_page_idx;
> unsigned long start_off, end_off, curr_idx, end_idx;
>
> /*
> @@ -179,14 +189,16 @@ static void map_free(struct uk_bbpalloc *b, uintptr_t
> first_page,
> */
> memr = map_get_memr(b, first_page);
> UK_ASSERT(memr != NULL);
> - UK_ASSERT((first_page + nr_pages)
> - <= (memr->first_page + memr->nr_pages));
> + UK_ASSERT((first_page + nr_pages * __PAGE_SIZE)
> + <= (memr->first_page + memr->nr_pages * __PAGE_SIZE));
>
> first_page -= memr->first_page;
> - curr_idx = first_page / PAGES_PER_MAPWORD;
> - start_off = first_page & (PAGES_PER_MAPWORD - 1);
> - end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
> - end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD - 1);
> + first_page_idx = first_page / __PAGE_SIZE;
> + curr_idx = first_page_idx / PAGES_PER_MAPWORD;
> + start_off = first_page_idx & (PAGES_PER_MAPWORD - 1);
> + end_page_idx = first_page_idx + nr_pages;
> + end_idx = end_page_idx / PAGES_PER_MAPWORD;
> + end_off = end_page_idx & (PAGES_PER_MAPWORD - 1);
>
> if (curr_idx == end_idx) {
> memr->mm_alloc_bitmap[curr_idx] &=
> @@ -345,10 +357,25 @@ static int bbuddy_addmem(struct uk_alloc *a, void
> *base, size_t len)
> min = round_pgup((uintptr_t)base);
> max = round_pgdown((uintptr_t)base + (uintptr_t)len);
> range = max - min;
> - memr_size =
> - round_pgup(sizeof(*memr) + DIV_ROUND_UP(range >> __PAGE_SHIFT, 8));
>
> memr = (struct uk_bbpalloc_memr *)min;
> +
> + /*
> + * The number of pages is found by solving the inequality:
> + *
> + * sizeof(*memr) + bitmap_size + page_num * page_size <= range
> + *
> + * where: bitmap_size = page_num / BITS_PER_BYTE
> + *
> + */
> + memr->nr_pages =
> + BITS_PER_BYTE * (range - sizeof(*memr)) /
> + (BITS_PER_BYTE * __PAGE_SIZE + 1);
I had a bad time trying to understand this math. I would like to propose
a comment like this here
/* The available amount of memory in bits is:
* BITS_PER_BYTE * (range - sizeof(*memr))
*
* Every page occupies one bit in the bitmap. So total number of bits
* used by one page is:
* BITS_PER_BYTE * __PAGE_SIZE + 1
*/
> + memr->mm_alloc_bitmap = (unsigned long *) (min + sizeof(*memr));
> + memr->mm_alloc_bitmap_size =
> + round_pgup(memr->nr_pages / BITS_PER_BYTE) - sizeof(*memr);
I think I found a problem in the math..
Let's assume this function is called with len=132952064 (32459 pages). In
this case memr->nr_pages=32457,
memr->mm_alloc_bitmap_size=4056. However, to represent 32457 pages we
are going to need 32457/8 = 4057.125 = 4058 bytes.
This math probably could be replaced with an easier one. Currently it is
a bit too complicated. It is difficult to verify, and quite easy to make
a mistake.
Here is an idea. What if we approach the problem from the other side. We
know how many pages one page of a bitmap can handle. I wrote a small
snippet to demonstrate:
#define BITMAP_FIRST_PAGE_BYTES ( __PAGE_SIZE - \
sizeof(struct uk_bbpalloc_memr))
#define BITMAP_FIRST_PAGE_BITS ((ssize_t) (BITMAP_FIRST_PAGE_BYTES << 3))
#define BITS_PER_PAGE (__PAGE_SIZE << 3)
ssize_t memr_pg_num = 1;
ssize_t rem_pages = range >> __PAGE_SHIFT;
/* The very first page is special - it is shared between memr
* and initial portion of the bitmap.
*
* This page is already taken from the page budget, we
* decrease number of pages we should care about.
*/
if (rem_pages > BITMAP_FIRST_PAGE_BITS) {
/* We have a bitmap that is capable of handling
* BITMAP_FIRST_PAGE_BITS pages anyways. If we are
* here that was not enough
*/
/* We don not need to care about pages handled by
* bitmap in the first page
*/
rem_pages -= BITMAP_FIRST_PAGE_BITS;
/* To handle the remaining part we going to need
* (rem_pages / BITS_PER_PAGE) pages. But with every
* next bitmap page, the number of usable pages
* reduces by 1. That is why we actually need to
* divide by (BITS_PER_PAGE +1)
*/
memr_pg_num += (rem_pages + BITS_PER_PAGE - 1) /
(BITS_PER_PAGE + 1);
}
What do you think?
> + memr_size = sizeof(*memr) + memr->mm_alloc_bitmap_size;
> +
> min += memr_size;
> range -= memr_size;
> if (max < min) {
> @@ -362,10 +389,14 @@ static int bbuddy_addmem(struct uk_alloc *a, void
> *base, size_t len)
> * Initialize region's bitmap
> */
> memr->first_page = min;
> - memr->nr_pages = max - min;
> /* add to list */
> memr->next = b->memr_head;
> b->memr_head = memr;
> +
> + /* All allocated by default. */
> + memset(memr->mm_alloc_bitmap, (unsigned char) ~0,
> + memr->mm_alloc_bitmap_size);
Very minor thing. Probably '0xff' is nicer then '(unsigned char) ~0'
> +
> /* free up the memory we've been given to play with */
> map_free(b, min, (unsigned long)(range >> __PAGE_SHIFT));
>
> --
> 2.11.0
>
--
Yuri Volchkov
Software Specialist
NEC Europe Ltd
Kurfürsten-Anlage 36
D-69115 Heidelberg
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |