Messages in this thread | | | Date | Mon, 16 May 2022 07:59:45 +0200 | Subject | Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants | From | Juergen Gross <> |
| |
On 14.05.22 04:34, Boris Ostrovsky wrote: > > > 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.
You meant 10, 2, 12, 3, 11, I guess?
> > What will this look like after the 2 iterations of the outer loop?
idx .. 2 3 ... 10 11 12
grant 3 10 11 12 -1
with gnttab_free_head being 2, i.e the free list is now 2, 3, 10, 11, 12.
Juergen [unhandled content-type:application/pgp-keys][unhandled content-type:application/pgp-signature] | |