Re: [Minios-devel] [UNIKRAFT PATCH 1/2] lib/ukallocbbuddy: Fix definition and assertions of memr.nr_pages

[Costin Lupu <costin.lup@xxxxxxxxx>]

On 03/17/2018 01:19 AM, Bruno Alvisio wrote:
> 
> 
> On Thu, Mar 15, 2018 at 11:41 AM, Costin Lupu <costin.lup@xxxxxxxxx
> <mailto:costin.lup@xxxxxxxxx>> wrote:
> 
>     Hi Bruno,
> 
>     First of all thanks for pointing out this issue! Please see my comments
>     inline.
> 
>     On 03/15/2018 05:38 PM, Bruno Alvisio wrote:
>     > Currently, nr_pages is set to the range size instead of the number of 
> pages in
>     > the memory region. Fixed by shifting by __PAGE_SIZE. Assertions are 
> fixed
>     > accordingly.
>     >
>     > Signed-off-by: Bruno Alvisio <bruno.alvisio@xxxxxxxxx 
> <mailto:bruno.alvisio@xxxxxxxxx>>
>     > ---
>     >  lib/ukallocbbuddy/bbuddy.c | 7 ++++---
>     >  1 file changed, 4 insertions(+), 3 deletions(-)
>     >
>     > diff --git a/lib/ukallocbbuddy/bbuddy.c b/lib/ukallocbbuddy/bbuddy.c
>     > index b830995..13cb0c8 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)))
> 
>     Here page_num should be renamed to either page or page_va (page virtual
>     address) because it checks if the page address is in the memory region.
>     Also if you're using bit shifting then it's __PAGE_SHIFT, not
>     __PAGE_SIZE.
> 
> 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));
> 
>     Again, it's __PAGE_SHIFT, not __PAGE_SIZE. More than that, the assertion
>     is incomplete. The correct assertion would be:
>     +       UK_ASSERT((first_page + (nr_pages << __PAGE_SHIFT))
>     +             <= (memr->first_page + (memr->nr_pages << __PAGE_SHIFT)));
> 
>     >
>     >       first_page -= memr->first_page;
>     >       curr_idx = first_page / PAGES_PER_MAPWORD;
>     > @@ -362,7 +362,8 @@ 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;
>     > +     memr->nr_pages = (max - min) >> __PAGE_SIZE;
>     > +
> 
>     Again, it's __PAGE_SHIFT, not __PAGE_SIZE.
> 
> 
> Ack. Sorry for the typo. 
> 
> 
>     The number of pages is not the best one. If
>     range = 8 * PAGE_SIZE * (PAGE_SIZE - sizeof(*memr) + 1), then
>     we would lose one page for book keeping because
>     memr_size = round_pgup(PAGE_SIZE + 1).
> 
>     The right number of page is given by the inequality:
>     sizeof(*memr) + bitmap_size + page_num * page_size <= range,
>     where bitmap_size = page_num / BITS_PER_BYTE (please define this macro
>     in bbuddy.c to avoid confusion). Therefore, the number of pages is:
> 
>     BITS_PER_BYTE * (range - sizeof(*memr)) /
>     (BITS_PER_BYTE * __PAGE_SIZE + 1)
> 
> I follow the arithmetic that you are doing here but I am not clear on
> exactly we want to achieve.
> 
> Right now, memr_size is forced to be a multiple of PAGE_SIZE. 
> memr_size = round_pgup(..)
> 
> and then min and range are modified accordingly:
> 
> min += memr_size;
> 
> range -= memr_size;
> 
> 
> Thus:
> 
> nr_pages = (max - min) >> __PAGE_SHIFT
> 
>  looks OK even for the case that you mentioned:
> 
> If instead 
> 
> nr_pages = BITS_PER_BYTE * (range - sizeof(*memr)) /
> (BITS_PER_BYTE * __PAGE_SIZE + 1)
> 
> would be the same. Are you suggesting to use this formula just for clarity?
> 
> Or are you suggesting that we should enforce memr_size to be a multiple
> of PAGE_SIZE
> so that first_page always ends up being one memory location after the
> bitmap and we optimize
> the number of pages?
> 
> I am not sure if I am missing something about what you said.

What I'm trying to say is that following the current approach we waste
pages with book keeping (bitmaps). In both aproaches memr_size ends up
being a multiple of PAGE_SIZE.

In that example when the *whole* memory region size is:
8 * PAGE_SIZE * (PAGE_SIZE - sizeof(*memr) + 1)
memr_size ends up being round_pgup(PAGE_SIZE + 1), that is 2 pages,
instead of round_pgup(PAGE_SIZE) which should be just 1 page.

> 
>     Also, the bitmap should be set to ones before calling map_free.
> 
> 
> Ack. 
> 
> 
>     >       /* add to list */
>     >       memr->next = b->memr_head;
>     >       b->memr_head = memr;
>     >
> 
>     The patch should also include:
>     - changes to allocated_in_map function:
>       1. rename page_num to page/page_va
> 
> Ack. 
> 
>       2. return unsigned long instead of int
> 
> Ack. 
> 
>       3. change the return value by using the correct bitmap array index and
>     offset in map word
>     - in map_alloc, correct values for curr_idx, start_off, end_idx, end_off
> 
> The look OK to me. What I am missing? 

For example, curr_idx should be the bitmap word index. first_page is a
page address, therefore curr_idx should be:
(first_page / PAGE_SIZE) / PAGES_PER_MAPWORD

instead of:
first_page / PAGES_PER_MAPWORD

> 
>     - in map_free, correct values for curr_idx, start_off, end_idx, end_off
> 
> They look OK to me.
> 
>     Please include all the changes into a single patch and test them before
>     submission.

Let me know if you have further questions.

Thanks,
Costin

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