Re: [Minios-devel] Unikraft: Question about binary buddy allocator

[Simon Kuenzer <simon.kuenzer@xxxxxxxxx>]

Hey Bruno,

you are right, this looks suspicious. The units (page address vs. byte 
address) are definitely mixed up right now.
On 08.03.2018 17:34, Bruno Alvisio wrote:
> Hello all,
>
> I was reading the binary buddy memory allocator code and I am confused 
> by the meaning of a variable “(struct uk_bbpalloc_memr) memr->nr_pages”. 
> From its name, it seems to hold the number of pages that belong to the 
> memory region. However, in lib/ukallocbbuddy/bbuddy.c:365 :
> memr->nr_pages = max - min;
>
> which seems to be the actual memory size of the region rather than the 
> number of pages. If my understanding is correct, the following 
> modifications would be needed:
> diff --git a/lib/ukallocbbuddy/bbuddy.c b/lib/ukallocbbuddy/bbuddy.c
>
> index b830995..c927524 100644
>
> --- a/lib/ukallocbbuddy/bbuddy.c
>
> +++ b/lib/ukallocbbuddy/bbuddy.c
>
> @@ -107,7 +107,7 @@ static inline struct uk_bbpalloc_memr 
> *map_get_memr(struct uk_bbpalloc *b,
> */
>
> for (memr = b->memr_head; memr != NULL; memr = memr->next) {
>
> if ((page_num >= memr->first_page)
>
> -&& (page_num < (memr->first_page + memr->nr_pages)))
>
> +&& (page_num < (memr->first_page + memr->nr_pages * __PAGE_SIZE)))
Use __PAGE_SHIFT instead. This operation should be faster:

+&& (page_num < (memr->first_page + (memr->nr_pages << __PAGE_SHIFT))))

> return memr;
>
> }
>
> @@ -145,7 +145,7 @@ 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));
>
> +<= (memr->first_page + memr->nr_pages * __PAGE_SIZE));
+<= (memr->first_page + (memr->nr_pages << __PAGE_SHIFT)));

> first_page -= memr->first_page;
>
> curr_idx = first_page / PAGES_PER_MAPWORD;
>
> @@ -362,7 +362,9 @@ 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;
>
> +int spare = (min - max) % __PAGE_SIZE;
>
> +UK_ASSERT(spare == 0);
Is this spare variable used somewhere else? I guess you want to make 
sure that min and max are aligned to pages - which happens a few lines 
ahead.
In general, we should keep the ability to let libukdebug remove code 
that is used for a assertions only. This means that the operation should 
be self-contained within the UK_ASSERT. So, I would do
UK_ASSERT((min - max) % __PAGE_SIZE);

instead of introducing the spare variable and doing the operation for 
the check outside of the assertion.
Alternatively you could also just check that the alignment was working:

UK_ASSERT(max & __PAGE_MASK == max);
UK_ASSERT(min & __PAGE_MASK == min);

But in principle I do not think this check is really required.

> +memr->nr_pages = (max - min)/__PAGE_SIZE;
(max - min) >> __PAGE_SHIFT;

> /* add to list */
>
> memr->next = b->memr_head;
>
> b->memr_head = memr;
>
> Let me know if I am missing something. If the change looks correct I can 
> provide a patch.
This would be great. Thanks a lot!

> Cheers,
>
> Bruno
>
>
>
>
> _______________________________________________
> Minios-devel mailing list
> Minios-devel@xxxxxxxxxxxxxxxxxxxx
> https://lists.xenproject.org/mailman/listinfo/minios-devel
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel