|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Minios-devel] [UNIKRAFT PATCH v2] lib/ukallocbbuddy: Correct region bitmap allocation and usage
Hi Yuri,
Thanks a lot for your comments. Please see my replies inline.
On 06/22/2018 08:03 PM, Yuri Volchkov wrote:
> Hey Costin,
>
> there are some comments inline.
>
> -Yuri.
>
> Costin Lupu <costin.lupu@xxxxxxxxx> writes:
>
>> The usage of a each memory region that is added to the binary
>> buddy allocator is tracked with a bitmap. This patch corrects
>> wrong size calculation for the bitmap and wrong calculations
>> of bit postitions.
>>
>> Signed-off-by: Costin Lupu <costin.lupu@xxxxxxxxx>
>> ---
>> lib/ukallocbbuddy/bbuddy.c | 83
>> +++++++++++++++++++++++++++++++---------------
>> 1 file changed, 57 insertions(+), 26 deletions(-)
>>
>> diff --git a/lib/ukallocbbuddy/bbuddy.c b/lib/ukallocbbuddy/bbuddy.c
>> index 20a9b70..63288f0 100644
>> --- a/lib/ukallocbbuddy/bbuddy.c
>> +++ b/lib/ukallocbbuddy/bbuddy.c
>> @@ -69,7 +69,7 @@ struct uk_bbpalloc_memr {
>> unsigned long first_page;
>> unsigned long nr_pages;
>> unsigned long mm_alloc_bitmap_size;
>> - unsigned long mm_alloc_bitmap[];
>> + unsigned long *mm_alloc_bitmap;
>> };
>>
>> struct uk_bbpalloc {
>> @@ -93,10 +93,11 @@ struct uk_bbpalloc {
>> * *_idx == Index into `mm_alloc_bitmap' array.
>> * *_off == Bit offset within an element of the `mm_alloc_bitmap' array.
>> */
>> -#define PAGES_PER_MAPWORD (sizeof(unsigned long) * 8)
>> +#define BITS_PER_BYTE 8
>> +#define PAGES_PER_MAPWORD (sizeof(unsigned long) * BITS_PER_BYTE)
>>
>> static inline struct uk_bbpalloc_memr *map_get_memr(struct uk_bbpalloc *b,
>> - unsigned long page_num)
>> + unsigned long page_va)
>> {
>> struct uk_bbpalloc_memr *memr = NULL;
>>
>> @@ -106,8 +107,9 @@ static inline struct uk_bbpalloc_memr
>> *map_get_memr(struct uk_bbpalloc *b,
>> * of them. It should be just one region in most cases
>> */
>> for (memr = b->memr_head; memr != NULL; memr = memr->next) {
>> - if ((page_num >= memr->first_page)
>> - && (page_num < (memr->first_page + memr->nr_pages)))
>> + if ((page_va >= memr->first_page)
>> + && (page_va < (memr->first_page +
>> + memr->nr_pages * __PAGE_SIZE)))
> Is not a huge performance improvement, but better to use
> memr->nr_pages << __PAGE_SHIFT
Agreed, although I believe it is easier to understand it using the
multiplication.
>> return memr;
>> }
>>
>> @@ -117,24 +119,29 @@ static inline struct uk_bbpalloc_memr
>> *map_get_memr(struct uk_bbpalloc *b,
>> return NULL;
>> }
>>
>> -static inline int allocated_in_map(struct uk_bbpalloc *b,
>> - unsigned long page_num)
>> +static inline unsigned long allocated_in_map(struct uk_bbpalloc *b,
>> + unsigned long page_va)
>> {
>> - struct uk_bbpalloc_memr *memr = map_get_memr(b, page_num);
>> + struct uk_bbpalloc_memr *memr = map_get_memr(b, page_va);
>> + unsigned long page_idx;
>> + unsigned long bm_idx, bm_off;
>>
>> /* treat pages outside of region as allocated */
>> if (!memr)
>> return 1;
>>
>> - page_num -= memr->first_page;
>> - return ((memr)->mm_alloc_bitmap[(page_num) / PAGES_PER_MAPWORD]
>> - & (1UL << ((page_num) & (PAGES_PER_MAPWORD - 1))));
>> + page_idx = (page_va - memr->first_page) / __PAGE_SIZE;
>> + bm_idx = page_idx / PAGES_PER_MAPWORD;
>> + bm_off = page_idx & (PAGES_PER_MAPWORD - 1);
>> +
>> + return ((memr)->mm_alloc_bitmap[bm_idx] & (1UL << bm_off));
>> }
>>
>> static void map_alloc(struct uk_bbpalloc *b, uintptr_t first_page,
>> unsigned long nr_pages)
>> {
>> struct uk_bbpalloc_memr *memr;
>> + unsigned long first_page_idx, end_page_idx;
>> unsigned long start_off, end_off, curr_idx, end_idx;
>>
>> /*
>> @@ -144,14 +151,16 @@ 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));
>> + UK_ASSERT((first_page + nr_pages * __PAGE_SIZE)
>> + <= (memr->first_page + memr->nr_pages * __PAGE_SIZE));
>>
>> first_page -= memr->first_page;
>> - curr_idx = first_page / PAGES_PER_MAPWORD;
>> - start_off = first_page & (PAGES_PER_MAPWORD - 1);
>> - end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
>> - end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD - 1);
>> + first_page_idx = first_page / __PAGE_SIZE;
>> + curr_idx = first_page_idx / PAGES_PER_MAPWORD;
>> + start_off = first_page_idx & (PAGES_PER_MAPWORD - 1);
>> + end_page_idx = first_page_idx + nr_pages;
>> + end_idx = end_page_idx / PAGES_PER_MAPWORD;
>> + end_off = end_page_idx & (PAGES_PER_MAPWORD - 1);
> Same preference of shifts over divisions. I stop pointing it out here,
> but I think using shift in other places in the code would improve a
> little bit performance, and readability.
Actually, in my opinion the division is more readable than the shifting.
Other than that, I agree.
>>
>> if (curr_idx == end_idx) {
>> memr->mm_alloc_bitmap[curr_idx] |=
>> @@ -170,6 +179,7 @@ static void map_free(struct uk_bbpalloc *b, uintptr_t
>> first_page,
>> unsigned long nr_pages)
>> {
>> struct uk_bbpalloc_memr *memr;
>> + unsigned long first_page_idx, end_page_idx;
>> unsigned long start_off, end_off, curr_idx, end_idx;
>>
>> /*
>> @@ -179,14 +189,16 @@ static void map_free(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));
>> + UK_ASSERT((first_page + nr_pages * __PAGE_SIZE)
>> + <= (memr->first_page + memr->nr_pages * __PAGE_SIZE));
>>
>> first_page -= memr->first_page;
>> - curr_idx = first_page / PAGES_PER_MAPWORD;
>> - start_off = first_page & (PAGES_PER_MAPWORD - 1);
>> - end_idx = (first_page + nr_pages) / PAGES_PER_MAPWORD;
>> - end_off = (first_page + nr_pages) & (PAGES_PER_MAPWORD - 1);
>> + first_page_idx = first_page / __PAGE_SIZE;
>> + curr_idx = first_page_idx / PAGES_PER_MAPWORD;
>> + start_off = first_page_idx & (PAGES_PER_MAPWORD - 1);
>> + end_page_idx = first_page_idx + nr_pages;
>> + end_idx = end_page_idx / PAGES_PER_MAPWORD;
>> + end_off = end_page_idx & (PAGES_PER_MAPWORD - 1);
>>
>> if (curr_idx == end_idx) {
>> memr->mm_alloc_bitmap[curr_idx] &=
>> @@ -345,10 +357,25 @@ static int bbuddy_addmem(struct uk_alloc *a, void
>> *base, size_t len)
>> min = round_pgup((uintptr_t)base);
>> max = round_pgdown((uintptr_t)base + (uintptr_t)len);
>> range = max - min;
>> - memr_size =
>> - round_pgup(sizeof(*memr) + DIV_ROUND_UP(range >> __PAGE_SHIFT, 8));
>>
>> memr = (struct uk_bbpalloc_memr *)min;
>> +
>> + /*
>> + * The number of pages is found by solving the inequality:
>> + *
>> + * sizeof(*memr) + bitmap_size + page_num * page_size <= range
>> + *
>> + * where: bitmap_size = page_num / BITS_PER_BYTE
>> + *
>> + */
>> + memr->nr_pages =
>> + BITS_PER_BYTE * (range - sizeof(*memr)) /
>> + (BITS_PER_BYTE * __PAGE_SIZE + 1);
> I had a bad time trying to understand this math. I would like to propose
> a comment like this here
> /* The available amount of memory in bits is:
> * BITS_PER_BYTE * (range - sizeof(*memr))
> *
> * Every page occupies one bit in the bitmap. So total number of bits
> * used by one page is:
> * BITS_PER_BYTE * __PAGE_SIZE + 1
> */
Unfortunately these comments are not quite right. They try to explain
the numerator and denominator, but the fraction is the result found by
solving the inequality.
>> + memr->mm_alloc_bitmap = (unsigned long *) (min + sizeof(*memr));
>> + memr->mm_alloc_bitmap_size =
>> + round_pgup(memr->nr_pages / BITS_PER_BYTE) - sizeof(*memr);
> I think I found a problem in the math..
>
> Let's assume this function is called with len=132952064 (32459 pages). In
> this case memr->nr_pages=32457,
Following the formula, you should get memr->nr_pages=32458, and for that
memr->mm_alloc_bitmap_size=4058.
> memr->mm_alloc_bitmap_size=4056. However, to represent 32457 pages we
> are going to need 32457/8 = 4057.125 = 4058 bytes.
That's right, 4058 is what you should get.
> This math probably could be replaced with an easier one. Currently it is
> a bit too complicated. It is difficult to verify, and quite easy to make
> a mistake.
>
> Here is an idea. What if we approach the problem from the other side. We
> know how many pages one page of a bitmap can handle. I wrote a small
> snippet to demonstrate:
>
> #define BITMAP_FIRST_PAGE_BYTES ( __PAGE_SIZE -
> \
> sizeof(struct uk_bbpalloc_memr))
> #define BITMAP_FIRST_PAGE_BITS ((ssize_t) (BITMAP_FIRST_PAGE_BYTES << 3))
> #define BITS_PER_PAGE (__PAGE_SIZE << 3)
>
> ssize_t memr_pg_num = 1;
> ssize_t rem_pages = range >> __PAGE_SHIFT;
>
> /* The very first page is special - it is shared between memr
> * and initial portion of the bitmap.
> *
> * This page is already taken from the page budget, we
> * decrease number of pages we should care about.
> */
> if (rem_pages > BITMAP_FIRST_PAGE_BITS) {
> /* We have a bitmap that is capable of handling
> * BITMAP_FIRST_PAGE_BITS pages anyways. If we are
> * here that was not enough
> */
>
> /* We don not need to care about pages handled by
> * bitmap in the first page
> */
> rem_pages -= BITMAP_FIRST_PAGE_BITS;
>
> /* To handle the remaining part we going to need
> * (rem_pages / BITS_PER_PAGE) pages. But with every
> * next bitmap page, the number of usable pages
> * reduces by 1. That is why we actually need to
> * divide by (BITS_PER_PAGE +1)
> */
> memr_pg_num += (rem_pages + BITS_PER_PAGE - 1) /
> (BITS_PER_PAGE + 1);
> }
>
>
> What do you think?
To me this solution looks more complicated. Actually it is a whole
different approach.
If you want to understand my proposed fix, the focus should be on the
equality (understanding it, finding the value for page_num and comparing
the result with what's in the code).
>> + memr_size = sizeof(*memr) + memr->mm_alloc_bitmap_size;
>> +
>> min += memr_size;
>> range -= memr_size;
>> if (max < min) {
>> @@ -362,10 +389,14 @@ 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;
>> /* add to list */
>> memr->next = b->memr_head;
>> b->memr_head = memr;
>> +
>> + /* All allocated by default. */
>> + memset(memr->mm_alloc_bitmap, (unsigned char) ~0,
>> + memr->mm_alloc_bitmap_size);
> Very minor thing. Probably '0xff' is nicer then '(unsigned char) ~0'
Please explain why it would be nicer. For sure it is not more portable.
>> +
>> /* free up the memory we've been given to play with */
>> map_free(b, min, (unsigned long)(range >> __PAGE_SHIFT));
>>
>> --
>> 2.11.0
>>
Thanks,
Costin
_______________________________________________
Minios-devel mailing list
Minios-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/minios-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |