Messages in this thread | | | Subject | Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants | From | Oleksandr <> | Date | Fri, 13 May 2022 13:43:06 +0300 |
| |
On 13.05.22 08:33, Juergen Gross wrote: > On 12.05.22 22:01, Boris Ostrovsky wrote:
Hello Juergen, Boris
[Juergen, thank you for your explanation]
> >> >> 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).
I think the loop deserves a comment on top, I will add it.
> > > > Juergen
-- Regards,
Oleksandr Tyshchenko
| |