Xen project Mailing List

On Sat, Mar 17, 2018 at 3:48 AM, Costin Lupu <costin.lup@xxxxxxxxx> wrote:

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@gmail.com>>

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

I am still trying to come up with an example in which the number of pages would

end up being different by using the current code vs. your approach. E.g.: (that doesn't work)

Start with min = 0; PAGE_SIZE = 512; size(*m) = 20:

1. Code:

range = 8 * PAGE_SIZE * (PAGE_SIZE - sizeof(*memr) + 1) = 8 * (512 * 493) = 2019328

memr_size = 2*512 = 1024 // 2*PAGE_SIZE

min = 1024

nr_pages = (2019328 - 1024) >> 9 = 3942.

2. Using inequality:

nr_pages = BITS_PER_BYTE * (range - sizeof(*memr)) / (BITS_PER_BYTE * __PAGE_SIZE + 1)

nr_pages = 8 * (2019328 -20) / (8 * 512 + 1) = 16154464/4097 = 3942.99 -> 3942

=> memr_size = round_pgup( 20 + 3942/8 ) = round_pgup(20 + 492.75) = round_pgup(513) = 1024 // 2*PAGE_SIZE

It would be great if you can provide me a corner case that shows the difference.

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

Got it. Didn't see that in this function was also recieving the address instead of page num.

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

Thanks for the clarifications,

Bruno

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