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

[Simon Kuenzer <simon.kuenzer@xxxxxxxxx>]

On 15.03.2018 16:44, Bruno Alvisio wrote:
> On Wed, Mar 14, 2018 at 1:18 AM, Simon Kuenzer <simon.kuenzer@xxxxxxxxx 
> <mailto: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.
Oh, right. I found that the UK_ASSERT and UK_WARNIF macro is not 
handling the string conversion correctly. The problem is that the 
condition is handed over stringified to the format of uk_printd() to 
print a message. In your case, the modulo operation ('%') is causing a 
problem. I am going to send out a patch that fixes this.
>     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@xxxxxxxxxxxxxxxxxxxx
>         <mailto:Minios-devel@xxxxxxxxxxxxxxxxxxxx>
>         https://lists.xenproject.org/mailman/listinfo/minios-devel
>         <https://lists.xenproject.org/mailman/listinfo/minios-devel>
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel