Messages in this thread | | | Date | Fri, 13 May 2022 22:34:19 -0400 | Subject | Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants | From | Boris Ostrovsky <> |
| |
On 5/13/22 1:33 AM, Juergen Gross wrote: > On 12.05.22 22:01, Boris Ostrovsky wrote: >> >> On 5/7/22 2:19 PM, Oleksandr Tyshchenko wrote:
>>> +/* Rebuilds the free grant list and tries to find count consecutive entries. */ >>> +static int get_free_seq(unsigned int count) >>> +{ >>> + int ret = -ENOSPC; >>> + unsigned int from, to; >>> + grant_ref_t *last; >>> + >>> + gnttab_free_tail_ptr = &gnttab_free_head; >>> + last = &gnttab_free_head; >>> + >>> + for (from = find_first_bit(gnttab_free_bitmap, gnttab_size); >>> + from < gnttab_size; >>> + from = find_next_bit(gnttab_free_bitmap, gnttab_size, to + 1)) { >>> + to = find_next_zero_bit(gnttab_free_bitmap, gnttab_size, >>> + from + 1); >>> + if (ret < 0 && to - from >= count) { >>> + ret = from; >>> + bitmap_clear(gnttab_free_bitmap, ret, count); >>> + from += count; >>> + gnttab_free_count -= count; >> >> >> IIUIC we can have multiple passes over this, meaning that the gnttab_free_count may be decremented more than once. Is that intentional? > > After the first pass decrementing gnttab_free_cnt, ret will no > longer be less than zero, so this can be hit only once.
Oh, yes, of course.
> >> >> >>> + if (from == to) >>> + continue; >>> + } >>> + >>> + while (from < to) { >>> + *last = from; >>> + last = __gnttab_entry(from); >>> + gnttab_last_free = from; >>> + from++; >>> + } >> >> >> I have been looking at this loop and I can't understand what it is doing ;-( Can you enlighten me? > > It is recreating the free list in order to have it properly sorted. > This is needed to make sure that the free tail has the maximum > possible size (you can take the tail off the list without having > to worry about breaking the linked list because of references into > the tail).
So let's say we have the (one-dimensional) table of length 13
idx .. 2 3 ... 10 11 12
grant 12 11 2 -1 3
and gnttab_free_head is 10. I.e. the free list is 2, 12, 3, 11.
What will this look like after the 2 iterations of the outer loop?
(I am really having a mental block on this).
-boris
| |