Re: [Qemu-devel] [PATCH v2 10/17] translate-all: use per-page locking in !user-mode

[Richard Henderson <richard.henderson@linaro.org>]

On 04/05/2018 04:13 PM, Emilio G. Cota wrote:
> +/**
> + * struct page_collection - tracks a set of pages (i.e. &struct page_entry's)
> + * @tree:   Binary search tree (BST) of the pages, with key == page index
> + * @max:    Pointer to the page in @tree with the highest page index
> + *
> + * To avoid deadlock we lock pages in ascending order of page index.
> + * When operating on a set of pages, we need to keep track of them so that
> + * we can lock them in order and also unlock them later. For this we collect
> + * pages (i.e. &struct page_entry's) in a binary search @tree. Given that the
> + * @tree implementation we use does not provide an O(1) operation to obtain the
> + * highest-ranked element, we use @max to keep track of the inserted page
> + * with the highest index. This is valuable because if a page is not in
> + * the tree and its index is higher than @max's, then we can lock it
> + * without breaking the locking order rule.
> + *
> + * Note on naming: 'struct page_set' would be shorter, but we already have a few
> + * page_set_*() helpers, so page_collection is used instead to avoid confusion.
> + *
> + * See also: page_collection_lock().
> + */
> +struct page_collection {
> +    GTree *tree;
> +    struct page_entry *max;
> +};

I don't understand the motivation for this data structure.  Substituting one
tree for another does not, on the face of it, seem to be a win.

Given that your locking order is based on the physical address, I can
understand that the sequential virtual addresses that these routines are given
is not appropriate.  But surely you should know how many pages are involved,
and therefore be able to allocate a flat array to hold the PageDesc.

> +/*
> + * Lock a range of pages ([@start,@end[) as well as the pages of all
> + * intersecting TBs.
> + * Locking order: acquire locks in ascending order of page index.
> + */

I don't think I understand this either.  From whence do you wind up with a
range of physical addresses?

> +struct page_collection *
> +page_collection_lock(tb_page_addr_t start, tb_page_addr_t end)

...

> +    /*
> +     * Add the TB to the page list.
> +     * To avoid deadlock, acquire first the lock of the lower-addressed page.
> +     */
> +    p = page_find_alloc(phys_pc >> TARGET_PAGE_BITS, 1);
> +    if (likely(phys_page2 == -1)) {
>          tb->page_addr[1] = -1;
> +        page_lock(p);
> +        tb_page_add(p, tb, 0, phys_pc & TARGET_PAGE_MASK);
> +    } else {
> +        p2 = page_find_alloc(phys_page2 >> TARGET_PAGE_BITS, 1);
> +        if (phys_pc < phys_page2) {
> +            page_lock(p);
> +            page_lock(p2);
> +        } else {
> +            page_lock(p2);
> +            page_lock(p);
> +        }

Extract this as a helper for use here and page_lock_tb?

>  /*
>   * Invalidate all TBs which intersect with the target physical address range
> + * [start;end[. NOTE: start and end must refer to the *same* physical page.
> + * 'is_cpu_write_access' should be true if called from a real cpu write
> + * access: the virtual CPU will exit the current TB if code is modified inside
> + * this TB.
> + *
> + * Called with tb_lock/mmap_lock held for user-mode emulation
> + * Called with tb_lock held for system-mode emulation
> + */
> +void tb_invalidate_phys_page_range(tb_page_addr_t start, tb_page_addr_t end,
> +                                   int is_cpu_write_access)

FWIW, we should probably notice and optimize end = start + 1, which appears to
have the largest number of users for e.g. watchpoints.


r~