Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants

[Boris Ostrovsky <boris.ostrovsky@xxxxxxxxxx>]

On 5/16/22 1:59 AM, Juergen Gross wrote:
> 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.


OK, thanks, that helped. I couldn't link the free chunks in my head


With the error handling in gnttab_init() fixed

Reviewed-by: Boris Ostrovsky <boris.ostrovsky@xxxxxxxxxx>



-boris