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

[Juergen Gross <jgross@suse.com>]

[-- Attachment #1.1.1: Type: text/plain, Size: 5075 bytes --]

On 12.05.22 22:01, Boris Ostrovsky wrote:
> 
> On 5/7/22 2:19 PM, Oleksandr Tyshchenko wrote:
>> +
>> +/*
>> + * Handling of free grants:
>> + *
>> + * Free grants are in a simple list anchored in gnttab_free_head. They are
>> + * linked by grant ref, the last element contains GNTTAB_LIST_END. The number
>> + * of free entries is stored in gnttab_free_count.
>> + * Additionally there is a bitmap of free entries anchored in
>> + * gnttab_free_bitmap. This is being used for simplifying allocation of
>> + * multiple consecutive grants, which is needed e.g. for support of virtio.
>> + * gnttab_last_free is used to add free entries of new frames at the end of
>> + * the free list.
>> + * gnttab_free_tail_ptr specifies the variable which references the start
> 
> 
> If this references the start of the free interval, why is it called 
> gnttab_free_*tail*_ptr?

Because this is the tail of the whole area which is free.

It could be renamed to gnttab_free_tail_start_ptr. :-)

> 
> 
>> + * of consecutive free grants ending with gnttab_last_free. This pointer is
>> + * updated in a rather defensive way, in order to avoid performance hits in
>> + * hot paths.
>> + * All those variables are protected by gnttab_list_lock.
>> + */
>>   static int gnttab_free_count;
>> -static grant_ref_t gnttab_free_head;
>> +static unsigned int gnttab_size;
>> +static grant_ref_t gnttab_free_head = GNTTAB_LIST_END;
>> +static grant_ref_t gnttab_last_free = GNTTAB_LIST_END;
>> +static grant_ref_t *gnttab_free_tail_ptr;
>> +static unsigned long *gnttab_free_bitmap;
>>   static DEFINE_SPINLOCK(gnttab_list_lock);
>> +
>>   struct grant_frames xen_auto_xlat_grant_frames;
>>   static unsigned int xen_gnttab_version;
>>   module_param_named(version, xen_gnttab_version, uint, 0);
>> @@ -170,16 +194,111 @@ static int get_free_entries(unsigned count)
>>       ref = head = gnttab_free_head;
>>       gnttab_free_count -= count;
>> -    while (count-- > 1)
>> -        head = gnttab_entry(head);
>> +    while (count--) {
>> +        bitmap_clear(gnttab_free_bitmap, head, 1);
>> +        if (gnttab_free_tail_ptr == __gnttab_entry(head))
>> +            gnttab_free_tail_ptr = &gnttab_free_head;
>> +        if (count)
>> +            head = gnttab_entry(head);
>> +    }
>>       gnttab_free_head = gnttab_entry(head);
>>       gnttab_entry(head) = GNTTAB_LIST_END;
>> +    if (!gnttab_free_count) {
>> +        gnttab_last_free = GNTTAB_LIST_END;
>> +        gnttab_free_tail_ptr = NULL;
>> +    }
>> +
>>       spin_unlock_irqrestore(&gnttab_list_lock, flags);
>>       return ref;
>>   }
>> +static int get_seq_entry_count(void)
>> +{
>> +    if (gnttab_last_free == GNTTAB_LIST_END || !gnttab_free_tail_ptr ||
>> +        *gnttab_free_tail_ptr == GNTTAB_LIST_END)
>> +        return 0;
>> +
>> +    return gnttab_last_free - *gnttab_free_tail_ptr + 1;
>> +}
>> +
>> +/* 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.

> 
> 
>> +            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).


Juergen

[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 3149 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 495 bytes --]