Re: [Qemu-devel] [PATCH 10/16] translate-all: use per-page locking in !user-mode
On Thu, Mar 29, 2018 at 15:55:13 +0100, Alex Bennée wrote:
>
> Emilio G. Cota writes:
(snip)
> > +/* lock the page(s) of a TB in the correct acquisition order */
> > +static inline void page_lock_tb(const TranslationBlock *tb)
> > +{
> > +if (likely(tb->page_addr[1] == -1)) {
> > +page_lock(page_find(tb->page_addr[0] >> TARGET_PAGE_BITS));
> > +return;
> > +}
> > +if (tb->page_addr[0] < tb->page_addr[1]) {
> > +page_lock(page_find(tb->page_addr[0] >> TARGET_PAGE_BITS));
> > +page_lock(page_find(tb->page_addr[1] >> TARGET_PAGE_BITS));
> > +} else {
> > +page_lock(page_find(tb->page_addr[1] >> TARGET_PAGE_BITS));
> > +page_lock(page_find(tb->page_addr[0] >> TARGET_PAGE_BITS));
> > +}
> > +}
(snip)
> > +/*
> > + * 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);
> > +}
>
> Give we repeat this check further up perhaps a:
>
> page_lock_pair(PageDesc *p1, th_page_addr_t phys1, PageDesc *p2,
> tb_page_addr_t phys2)
After trying, I don't think it's worth the trouble.
Note that page_lock_tb expands to nothing in user-mode,
whereas the latter snippet is shared by user-mode and
!user-mode. Dealing with that gets ugly quickly;
besides, we'd have to optionally return *p1 and *p2,
plus choose whether to use page_find or page_find_alloc..
(snip)
> The diff is a little messy around tb_page_add but I think we need an
> assert_page_lock(p) which compiles to check mmap_lock in CONFIG_USER
> instead of the assert_memory_lock().
>
> Then we can be clear about tb, memory and page locks.
I've added an extra patch to v2 to do this, since this patch is
already huge.
Thanks,
Emilio
Re: [Qemu-devel] [PATCH 10/16] translate-all: use per-page locking in !user-mode
Emilio G. Cota writes:
> Groundwork for supporting parallel TCG generation.
>
> Instead of using a global lock (tb_lock) to protect changes
> to pages, use fine-grained, per-page locks in !user-mode.
> User-mode stays with mmap_lock.
>
> Sometimes changes need to happen atomically on more than one
> page (e.g. when a TB that spans across two pages is
> added/invalidated, or when a range of pages is invalidated).
> We therefore introduce struct page_collection, which helps
> us keep track of a set of pages that have been locked in
> the appropriate locking order (i.e. by ascending page index).
>
> This commit first introduces the structs and the function helpers,
> to then convert the calling code to use per-page locking. Note
> that tb_lock is not removed yet.
>
> While at it, rename tb_alloc_page to tb_page_add, which pairs with
> tb_page_remove.
>
> Signed-off-by: Emilio G. Cota
> ---
> accel/tcg/translate-all.c | 432
> +-
> accel/tcg/translate-all.h | 3 +
> include/exec/exec-all.h | 3 +-
> 3 files changed, 396 insertions(+), 42 deletions(-)
>
> diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c
> index 4cb03f1..07527d5 100644
> --- a/accel/tcg/translate-all.c
> +++ b/accel/tcg/translate-all.c
> @@ -112,8 +112,55 @@ typedef struct PageDesc {
> #else
> unsigned long flags;
> #endif
> +#ifndef CONFIG_USER_ONLY
> +QemuSpin lock;
> +#endif
> } PageDesc;
>
> +/**
> + * struct page_entry - page descriptor entry
> + * @pd: pointer to the &struct PageDesc of the page this entry represents
> + * @index: page index of the page
> + * @locked: whether the page is locked
> + *
> + * This struct helps us keep track of the locked state of a page, without
> + * bloating &struct PageDesc.
> + *
> + * A page lock protects accesses to all fields of &struct PageDesc.
> + *
> + * See also: &struct page_collection.
> + */
> +struct page_entry {
> +PageDesc *pd;
> +tb_page_addr_t index;
> +bool locked;
> +};
> +
> +/**
> + * 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;
> +};
> +
> /* list iterators for lists of tagged pointers in TranslationBlock */
> #define TB_FOR_EACH_TAGGED(head, tb, n, field) \
> for (n = (head) & 1,\
> @@ -510,6 +557,15 @@ static PageDesc *page_find_alloc(tb_page_addr_t index,
> int alloc)
> return NULL;
> }
> pd = g_new0(PageDesc, V_L2_SIZE);
> +#ifndef CONFIG_USER_ONLY
> +{
> +int i;
> +
> +for (i = 0; i < V_L2_SIZE; i++) {
> +qemu_spin_init(&pd[i].lock);
> +}
> +}
> +#endif
> existing = atomic_cmpxchg(lp, NULL, pd);
> if (unlikely(existing)) {
> g_free(pd);
> @@ -525,6 +581,228 @@ static inline PageDesc *page_find(tb_page_addr_t index)
> return page_find_alloc(index, 0);
> }
>
> +/* In user-mode page locks aren't used; mmap_lock is enough */
> +#ifdef CONFIG_USER_ONLY
> +static inline void page_lock(PageDesc *pd)
> +{ }
> +
> +static inline void page_unlock(PageDesc *pd)
> +{ }
> +
> +static inline void page_lock_tb(const TranslationBlock *tb)
> +{ }
> +
> +static inline void page_unlock_tb(const TranslationBlock *tb)
> +{ }
> +
> +struct page_collection *
> +page_collection_lock(tb_page_addr_t start, tb_page_addr_t end)
> +{
> +return NULL;
> +}
> +
> +void page_collection_unlock(struct page_collection *set)
> +{ }
> +#else /* !CONFIG_USER_ONLY */
> +
> +static inline void page_lock(PageDesc *pd)
> +{
> +qemu_spin_lock(&pd->lock);
> +}
> +
> +static inline void page_unlock(PageDesc *pd)
> +{
> +qemu_spin_unlock(&pd->lock);
> +}
> +
> +/* lock the page(s) of a TB in the correct acquisition order */
> +static inline void page_lock_tb(const Translatio
[Qemu-devel] [PATCH 10/16] translate-all: use per-page locking in !user-mode
Groundwork for supporting parallel TCG generation.
Instead of using a global lock (tb_lock) to protect changes
to pages, use fine-grained, per-page locks in !user-mode.
User-mode stays with mmap_lock.
Sometimes changes need to happen atomically on more than one
page (e.g. when a TB that spans across two pages is
added/invalidated, or when a range of pages is invalidated).
We therefore introduce struct page_collection, which helps
us keep track of a set of pages that have been locked in
the appropriate locking order (i.e. by ascending page index).
This commit first introduces the structs and the function helpers,
to then convert the calling code to use per-page locking. Note
that tb_lock is not removed yet.
While at it, rename tb_alloc_page to tb_page_add, which pairs with
tb_page_remove.
Signed-off-by: Emilio G. Cota
---
accel/tcg/translate-all.c | 432 +-
accel/tcg/translate-all.h | 3 +
include/exec/exec-all.h | 3 +-
3 files changed, 396 insertions(+), 42 deletions(-)
diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c
index 4cb03f1..07527d5 100644
--- a/accel/tcg/translate-all.c
+++ b/accel/tcg/translate-all.c
@@ -112,8 +112,55 @@ typedef struct PageDesc {
#else
unsigned long flags;
#endif
+#ifndef CONFIG_USER_ONLY
+QemuSpin lock;
+#endif
} PageDesc;
+/**
+ * struct page_entry - page descriptor entry
+ * @pd: pointer to the &struct PageDesc of the page this entry represents
+ * @index: page index of the page
+ * @locked: whether the page is locked
+ *
+ * This struct helps us keep track of the locked state of a page, without
+ * bloating &struct PageDesc.
+ *
+ * A page lock protects accesses to all fields of &struct PageDesc.
+ *
+ * See also: &struct page_collection.
+ */
+struct page_entry {
+PageDesc *pd;
+tb_page_addr_t index;
+bool locked;
+};
+
+/**
+ * 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;
+};
+
/* list iterators for lists of tagged pointers in TranslationBlock */
#define TB_FOR_EACH_TAGGED(head, tb, n, field) \
for (n = (head) & 1,\
@@ -510,6 +557,15 @@ static PageDesc *page_find_alloc(tb_page_addr_t index, int
alloc)
return NULL;
}
pd = g_new0(PageDesc, V_L2_SIZE);
+#ifndef CONFIG_USER_ONLY
+{
+int i;
+
+for (i = 0; i < V_L2_SIZE; i++) {
+qemu_spin_init(&pd[i].lock);
+}
+}
+#endif
existing = atomic_cmpxchg(lp, NULL, pd);
if (unlikely(existing)) {
g_free(pd);
@@ -525,6 +581,228 @@ static inline PageDesc *page_find(tb_page_addr_t index)
return page_find_alloc(index, 0);
}
+/* In user-mode page locks aren't used; mmap_lock is enough */
+#ifdef CONFIG_USER_ONLY
+static inline void page_lock(PageDesc *pd)
+{ }
+
+static inline void page_unlock(PageDesc *pd)
+{ }
+
+static inline void page_lock_tb(const TranslationBlock *tb)
+{ }
+
+static inline void page_unlock_tb(const TranslationBlock *tb)
+{ }
+
+struct page_collection *
+page_collection_lock(tb_page_addr_t start, tb_page_addr_t end)
+{
+return NULL;
+}
+
+void page_collection_unlock(struct page_collection *set)
+{ }
+#else /* !CONFIG_USER_ONLY */
+
+static inline void page_lock(PageDesc *pd)
+{
+qemu_spin_lock(&pd->lock);
+}
+
+static inline void page_unlock(PageDesc *pd)
+{
+qemu_spin_unlock(&pd->lock);
+}
+
+/* lock the page(s) of a TB in the correct acquisition order */
+static inline void page_lock_tb(const TranslationBlock *tb)
+{
+if (likely(tb->page_addr[1] == -1)) {
+page_lock(page_find(tb->page_addr[0] >> TARGET_PAGE_BITS));
+return;
+}
+if (tb->page_addr[0] < tb->page_addr[1]) {
+page_lock(page_find(tb->page_addr[0] >> TARGET_PAGE_BITS));
+page_lock(page_find(tb->page_addr[1] >
