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

[Bruno Alvisio <bruno.alvisio@xxxxxxxxx>]

On Wed, Mar 14, 2018 at 1:18 AM, Simon Kuenzer <simon.kuenzer@xxxxxxxxx> wrote:

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))))

Ack. 

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)));

Ack. 

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.

The reason I didn't do it as above is that when using % in the assertion I was getting some formatting errors while compiling. Yes, spare is not used anywhere.

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.

Ack. 

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

(max - min) >> __PAGE_SHIFT;

Ack. 

/* 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!

I just sent the patch. 

Cheers,

Bruno 

_______________________________________________
Minios-devel mailing list
Minios-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/minios-devel

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