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

[Bruno Alvisio <bruno.alvisio@xxxxxxxxx>]

On Thu, Mar 22, 2018 at 1:30 PM, Costin Lupu <costin.lup@xxxxxxxxx> wrote:

Hi Bruno,

I removed the parts that were already agreed. Please see my comments inline.

On 03/17/2018 08:40 PM, Bruno Alvisio wrote:
> On Sat, Mar 17, 2018 at 3:48 AM, Costin Lupu <costin.lup@xxxxxxxxx
> <mailto: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>
>     > <mailto: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

<snip>

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

Right, my bad. I thought I was providing the corner case but because of
my bad math I didn't. Sorry about that!

So, a correct corner case value would be for range value:

range = 8 * PAGE_SIZE * (8 * PAGE_SIZE - sizeof(*memr) + 1)
      = 16699392

Following your approach what I get for PAGE_SIZE=512 and
sizeof(*memr)=20 is:

1. Code:
memr_size = 4608 = 9 * PAGE_SIZE
nr_pages = 32607

2. Using inequality:
nr_pages = 32608
memr_size = 4096 = 8 * PAGE_SIZE

Hope this helps. Let me know if you have further questions.

<snip>

Great catch! :)

Now I get it: the current code is spilling memory

since it is using the original range size but as more bits are used

for keeping track the range for pages becomes smaller. Your

corner case is the minimum range that uses a full page of bits for

tracking.

I will make all the modifications and send a patch in the following days.

Cheers,

Bruno 

Costin

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