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

[Costin Lupu <costin.lup@xxxxxxxxx>]

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>


Costin

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