[Qemu-devel] [PATCH 0/6] qht improvements for 3.1

[Qemu-devel] [PATCH 0/6] qht improvements for 3.1

[Emilio G. Cota]

A small series with:

- The addition of qht_iter_remove, necessary to safely remove
  a set of elements. This currently has no users, but it's
  easy to implement and very useful to have. (I initially wrote
  it for the sync-profiler, but for unrelated reasons I ended up
  changing the profiler's design not to remove elements.)

- A 3.75X speedup for test-qht

- Improvements to qht.c's code coverage with test-qht

You can fetch this series from:
  https://github.com/cota/qemu/tree/qht-for-3.1

Thanks,

		Emilio

[Qemu-devel] [PATCH 1/6] qht: remove unused map param from qht_remove__locked

[Emilio G. Cota]

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 util/qht.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/util/qht.c b/util/qht.c
index c138777a9c..7b57b50a24 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -665,8 +665,7 @@ static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)
 
 /* call with b->lock held */
 static inline
-bool qht_remove__locked(struct qht_map *map, struct qht_bucket *head,
-                        const void *p, uint32_t hash)
+bool qht_remove__locked(struct qht_bucket *head, const void *p, uint32_t hash)
 {
     struct qht_bucket *b = head;
     int i;
@@ -701,7 +700,7 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
     qht_debug_assert(p);
 
     b = qht_bucket_lock__no_stale(ht, hash, &map);
-    ret = qht_remove__locked(map, b, p, hash);
+    ret = qht_remove__locked(b, p, hash);
     qht_bucket_debug__locked(b);
     qemu_spin_unlock(&b->lock);
     return ret;
-- 
2.17.1

[Qemu-devel] [PATCH 2/6] qht: add qht_iter_remove

[Emilio G. Cota]

This currently has no users, but the use case is so common that I
think we must support it.

Note that without the appended we cannot safely remove a set of
elements; a 2-step approach (i.e. qht_iter first, keep track of
the to-be-deleted elements, and then a bunch of qht_remove calls)
would be racy, since between the iteration and the removals other
threads might insert additional elements.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 include/qemu/qht.h | 19 ++++++++++++
 util/qht.c         | 74 +++++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 85 insertions(+), 8 deletions(-)

diff --git a/include/qemu/qht.h b/include/qemu/qht.h
index 1fb9116fa0..91bc9b00cf 100644
--- a/include/qemu/qht.h
+++ b/include/qemu/qht.h
@@ -44,6 +44,8 @@ struct qht_stats {
 
 typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp);
 typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up);
+typedef bool (*qht_iter_bool_func_t)(struct qht *ht, void *p, uint32_t h,
+                                     void *up);
 
 #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */
 
@@ -178,9 +180,26 @@ bool qht_resize(struct qht *ht, size_t n_elems);
  *
  * Each time it is called, user-provided @func is passed a pointer-hash pair,
  * plus @userp.
+ *
+ * Note: @ht cannot be accessed from @func
+ * See also: qht_iter_remove()
  */
 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp);
 
+/**
+ * qht_iter_remove - Iterate over a QHT, optionally removing entries
+ * @ht: QHT to be iterated over
+ * @func: function to be called for each entry in QHT
+ * @userp: additional pointer to be passed to @func
+ *
+ * Each time it is called, user-provided @func is passed a pointer-hash pair,
+ * plus @userp. If @func returns true, the pointer-hash pair is removed.
+ *
+ * Note: @ht cannot be accessed from @func
+ * See also: qht_iter()
+ */
+void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp);
+
 /**
  * qht_statistics_init - Gather statistics from a QHT
  * @ht: QHT to gather statistics from
diff --git a/util/qht.c b/util/qht.c
index 7b57b50a24..caec53dd0e 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -89,6 +89,19 @@
 #define QHT_BUCKET_ENTRIES 4
 #endif
 
+enum qht_iter_type {
+    QHT_ITER_VOID,    /* do nothing; use retvoid */
+    QHT_ITER_RM,      /* remove element if retbool returns true */
+};
+
+struct qht_iter {
+    union {
+        qht_iter_func_t retvoid;
+        qht_iter_bool_func_t retbool;
+    } f;
+    enum qht_iter_type type;
+};
+
 /*
  * Note: reading partially-updated pointers in @pointers could lead to
  * segfaults. We thus access them with atomic_read/set; this guarantees
@@ -706,9 +719,10 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
     return ret;
 }
 
-static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
-                                   qht_iter_func_t func, void *userp)
+static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *head,
+                                   const struct qht_iter *iter, void *userp)
 {
+    struct qht_bucket *b = head;
     int i;
 
     do {
@@ -716,7 +730,25 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
             if (b->pointers[i] == NULL) {
                 return;
             }
-            func(ht, b->pointers[i], b->hashes[i], userp);
+            switch (iter->type) {
+            case QHT_ITER_VOID:
+                iter->f.retvoid(ht, b->pointers[i], b->hashes[i], userp);
+                break;
+            case QHT_ITER_RM:
+                if (iter->f.retbool(ht, b->pointers[i], b->hashes[i], userp)) {
+                    /* replace i with the last valid element in the bucket */
+                    seqlock_write_begin(&head->sequence);
+                    qht_bucket_remove_entry(b, i);
+                    seqlock_write_end(&head->sequence);
+                    qht_bucket_debug__locked(b);
+                    /* reevaluate i, since it just got replaced */
+                    i--;
+                    continue;
+                }
+                break;
+            default:
+                g_assert_not_reached();
+            }
         }
         b = b->next;
     } while (b);
@@ -724,26 +756,48 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
 
 /* call with all of the map's locks held */
 static inline void qht_map_iter__all_locked(struct qht *ht, struct qht_map *map,
-                                            qht_iter_func_t func, void *userp)
+                                            const struct qht_iter *iter,
+                                            void *userp)
 {
     size_t i;
 
     for (i = 0; i < map->n_buckets; i++) {
-        qht_bucket_iter(ht, &map->buckets[i], func, userp);
+        qht_bucket_iter(ht, &map->buckets[i], iter, userp);
     }
 }
 
-void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
+static inline void
+do_qht_iter(struct qht *ht, const struct qht_iter *iter, void *userp)
 {
     struct qht_map *map;
 
     map = atomic_rcu_read(&ht->map);
     qht_map_lock_buckets(map);
     /* Note: ht here is merely for carrying ht->mode; ht->map won't be read */
-    qht_map_iter__all_locked(ht, map, func, userp);
+    qht_map_iter__all_locked(ht, map, iter, userp);
     qht_map_unlock_buckets(map);
 }
 
+void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
+{
+    const struct qht_iter iter = {
+        .f.retvoid = func,
+        .type = QHT_ITER_VOID,
+    };
+
+    do_qht_iter(ht, &iter, userp);
+}
+
+void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp)
+{
+    const struct qht_iter iter = {
+        .f.retbool = func,
+        .type = QHT_ITER_RM,
+    };
+
+    do_qht_iter(ht, &iter, userp);
+}
+
 static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
 {
     struct qht_map *new = userp;
@@ -760,6 +814,10 @@ static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
 static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
 {
     struct qht_map *old;
+    const struct qht_iter iter = {
+        .f.retvoid = qht_map_copy,
+        .type = QHT_ITER_VOID,
+    };
 
     old = ht->map;
     qht_map_lock_buckets(old);
@@ -774,7 +832,7 @@ static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
     }
 
     g_assert(new->n_buckets != old->n_buckets);
-    qht_map_iter__all_locked(ht, old, qht_map_copy, new);
+    qht_map_iter__all_locked(ht, old, &iter, new);
     qht_map_debug__all_locked(new);
 
     atomic_rcu_set(&ht->map, new);
-- 
2.17.1

[Qemu-devel] [PATCH 3/6] test-qht: test qht_iter_remove

[Emilio G. Cota]

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 tests/test-qht.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 48 insertions(+), 2 deletions(-)

diff --git a/tests/test-qht.c b/tests/test-qht.c
index dda6a067be..283fb3db39 100644
--- a/tests/test-qht.c
+++ b/tests/test-qht.c
@@ -108,6 +108,49 @@ static void iter_check(unsigned int count)
     g_assert_cmpuint(curr, ==, count);
 }
 
+static void sum_func(struct qht *ht, void *p, uint32_t hash, void *userp)
+{
+    uint32_t *sum = userp;
+    uint32_t a = *(uint32_t *)p;
+
+    *sum += a;
+}
+
+static void iter_sum_check(unsigned int expected)
+{
+    unsigned int sum = 0;
+
+    qht_iter(&ht, sum_func, &sum);
+    g_assert_cmpuint(sum, ==, expected);
+}
+
+static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *userp)
+{
+    uint32_t a = *(uint32_t *)p;
+    unsigned int mod = *(unsigned int *)userp;
+
+    return a % mod == 0;
+}
+
+static void iter_rm_mod(unsigned int mod)
+{
+    qht_iter_remove(&ht, rm_mod_func, &mod);
+}
+
+static void iter_rm_mod_check(unsigned int mod)
+{
+    unsigned int expected = 0;
+    unsigned int i;
+
+    for (i = 0; i < N; i++) {
+        if (i % mod == 0) {
+            continue;
+        }
+        expected += i;
+    }
+    iter_sum_check(expected);
+}
+
 static void qht_do_test(unsigned int mode, size_t init_entries)
 {
     /* under KVM we might fetch stats from an uninitialized qht */
@@ -138,8 +181,11 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
     insert(10, 150);
     check_n(N);
 
-    rm(1, 2);
-    check_n(N - 1);
+    qht_reset(&ht);
+    insert(0, N);
+    iter_rm_mod(10);
+    iter_rm_mod_check(10);
+    check_n(N * 9 / 10);
     qht_reset_size(&ht, 0);
     check_n(0);
     check(0, N, false);
-- 
2.17.1

[Qemu-devel] [PATCH 4/6] test-qht: test removal of non-existent entries

[Emilio G. Cota]

This improves qht.c code coverage from 89.44% to 90.00%.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 tests/test-qht.c | 26 ++++++++++++++++++++++++--
 1 file changed, 24 insertions(+), 2 deletions(-)

diff --git a/tests/test-qht.c b/tests/test-qht.c
index 283fb3db39..05b1d6807a 100644
--- a/tests/test-qht.c
+++ b/tests/test-qht.c
@@ -41,7 +41,7 @@ static void insert(int a, int b)
     }
 }
 
-static void rm(int init, int end)
+static void do_rm(int init, int end, bool exist)
 {
     int i;
 
@@ -49,10 +49,24 @@ static void rm(int init, int end)
         uint32_t hash;
 
         hash = arr[i];
-        g_assert_true(qht_remove(&ht, &arr[i], hash));
+        if (exist) {
+            g_assert_true(qht_remove(&ht, &arr[i], hash));
+        } else {
+            g_assert_false(qht_remove(&ht, &arr[i], hash));
+        }
     }
 }
 
+static void rm(int init, int end)
+{
+    do_rm(init, end, true);
+}
+
+static void rm_nonexist(int init, int end)
+{
+    do_rm(init, end, false);
+}
+
 static void check(int a, int b, bool expected)
 {
     struct qht_stats stats;
@@ -157,8 +171,15 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
     check_n(0);
 
     qht_init(&ht, is_equal, 0, mode);
+    rm_nonexist(0, 4);
+    insert(0, 4);
+    rm_nonexist(5, 6);
+    insert(4, 6);
+    rm_nonexist(7, 8);
+    iter_rm_mod(1);
 
     check_n(0);
+    rm_nonexist(0, 10);
     insert(0, N);
     check(0, N, true);
     check_n(N);
@@ -183,6 +204,7 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
 
     qht_reset(&ht);
     insert(0, N);
+    rm_nonexist(N, N + 32);
     iter_rm_mod(10);
     iter_rm_mod_check(10);
     check_n(N * 9 / 10);
-- 
2.17.1

[Qemu-devel] [PATCH 5/6] test-qht: test deletion of the last entry in a bucket

[Emilio G. Cota]

This improves coverage by one (!) LoC in qht.c, bringing the
coverage rate up from 90.00% to 90.28%.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 tests/test-qht.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/tests/test-qht.c b/tests/test-qht.c
index 05b1d6807a..77666e8c5f 100644
--- a/tests/test-qht.c
+++ b/tests/test-qht.c
@@ -172,9 +172,20 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
 
     qht_init(&ht, is_equal, 0, mode);
     rm_nonexist(0, 4);
+    /*
+     * Test that we successfully delete the last element in a bucket.
+     * This is a hard-to-reach code path when resizing is on, but without
+     * resizing we can easily hit it if init_entries <= 1.
+     * Given that the number of elements per bucket can be 4 or 6 depending on
+     * the host's pointer size, test the removal of the 4th and 6th elements.
+     */
     insert(0, 4);
     rm_nonexist(5, 6);
-    insert(4, 6);
+    rm(3, 4);
+    check_n(3);
+    insert(3, 6);
+    rm(5, 6);
+    check_n(5);
     rm_nonexist(7, 8);
     iter_rm_mod(1);
 
-- 
2.17.1

[Qemu-devel] [PATCH 6/6] test-qht: speed up + test qht_resize

[Emilio G. Cota]

Perform first the tests that exercise code paths that are
easier to hit at small table sizes, and then resize the table
to speed up subsequent tests. If this resize is not too large,
we can make the test faster with no code coverage loss.

- With gcov enabled:

Before: 20.568s, 90.28% qht.c coverage
After:   5.168s, 93.06% qht.c coverage

The coverage increase is entirely due to calling qht_resize,
which we weren't calling before. Note that the code paths
that remain to be tested are either error handling or
can only occur when several threads are accessing the
hash table concurrently (e.g. seqlock retry, trylock fail).

- Without gcov:

Before: 1.987s
After:  0.528s

The speedup is almost the same as with gcov, although the
"before" run is a lot faster.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 tests/test-qht.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/tests/test-qht.c b/tests/test-qht.c
index 77666e8c5f..1ec039d636 100644
--- a/tests/test-qht.c
+++ b/tests/test-qht.c
@@ -189,6 +189,10 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
     rm_nonexist(7, 8);
     iter_rm_mod(1);
 
+    if (!(mode & QHT_MODE_AUTO_RESIZE)) {
+        qht_resize(&ht, init_entries * 4 + 4);
+    }
+
     check_n(0);
     rm_nonexist(0, 10);
     insert(0, N);
-- 
2.17.1

Re: [Qemu-devel] [PATCH 1/6] qht: remove unused map param from qht_remove__locked

[Alex Bennée]

Emilio G. Cota <cota@braap.org> writes:

> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

> ---
>  util/qht.c | 5 ++---
>  1 file changed, 2 insertions(+), 3 deletions(-)
>
> diff --git a/util/qht.c b/util/qht.c
> index c138777a9c..7b57b50a24 100644
> --- a/util/qht.c
> +++ b/util/qht.c
> @@ -665,8 +665,7 @@ static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)
>
>  /* call with b->lock held */
>  static inline
> -bool qht_remove__locked(struct qht_map *map, struct qht_bucket *head,
> -                        const void *p, uint32_t hash)
> +bool qht_remove__locked(struct qht_bucket *head, const void *p, uint32_t hash)
>  {
>      struct qht_bucket *b = head;
>      int i;
> @@ -701,7 +700,7 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
>      qht_debug_assert(p);
>
>      b = qht_bucket_lock__no_stale(ht, hash, &map);
> -    ret = qht_remove__locked(map, b, p, hash);
> +    ret = qht_remove__locked(b, p, hash);
>      qht_bucket_debug__locked(b);
>      qemu_spin_unlock(&b->lock);
>      return ret;


--
Alex Bennée

Re: [Qemu-devel] [PATCH 2/6] qht: add qht_iter_remove

[Alex Bennée]

Emilio G. Cota <cota@braap.org> writes:

> This currently has no users, but the use case is so common that I
> think we must support it.
>
> Note that without the appended we cannot safely remove a set of
> elements; a 2-step approach (i.e. qht_iter first, keep track of
> the to-be-deleted elements, and then a bunch of qht_remove calls)
> would be racy, since between the iteration and the removals other
> threads might insert additional elements.
>
> Signed-off-by: Emilio G. Cota <cota@braap.org>
> ---
>  include/qemu/qht.h | 19 ++++++++++++
>  util/qht.c         | 74 +++++++++++++++++++++++++++++++++++++++++-----
>  2 files changed, 85 insertions(+), 8 deletions(-)
>
> diff --git a/include/qemu/qht.h b/include/qemu/qht.h
> index 1fb9116fa0..91bc9b00cf 100644
> --- a/include/qemu/qht.h
> +++ b/include/qemu/qht.h
> @@ -44,6 +44,8 @@ struct qht_stats {
>
>  typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp);
>  typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up);
> +typedef bool (*qht_iter_bool_func_t)(struct qht *ht, void *p, uint32_t h,
> +                                     void *up);
>
>  #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */
>
> @@ -178,9 +180,26 @@ bool qht_resize(struct qht *ht, size_t n_elems);
>   *
>   * Each time it is called, user-provided @func is passed a pointer-hash pair,
>   * plus @userp.
> + *
> + * Note: @ht cannot be accessed from @func

I'm confused by this comment. If @ht cannot be accessed (or shouldn't be
accessed) from @func then why are we passing it?

> + * See also: qht_iter_remove()
>   */
>  void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp);
>
> +/**
> + * qht_iter_remove - Iterate over a QHT, optionally removing entries
> + * @ht: QHT to be iterated over
> + * @func: function to be called for each entry in QHT
> + * @userp: additional pointer to be passed to @func
> + *
> + * Each time it is called, user-provided @func is passed a pointer-hash pair,
> + * plus @userp. If @func returns true, the pointer-hash pair is removed.
> + *
> + * Note: @ht cannot be accessed from @func
> + * See also: qht_iter()
> + */
> +void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp);
> +
>  /**
>   * qht_statistics_init - Gather statistics from a QHT
>   * @ht: QHT to gather statistics from
> diff --git a/util/qht.c b/util/qht.c
> index 7b57b50a24..caec53dd0e 100644
> --- a/util/qht.c
> +++ b/util/qht.c
> @@ -89,6 +89,19 @@
>  #define QHT_BUCKET_ENTRIES 4
>  #endif
>
> +enum qht_iter_type {
> +    QHT_ITER_VOID,    /* do nothing; use retvoid */
> +    QHT_ITER_RM,      /* remove element if retbool returns true */
> +};
> +
> +struct qht_iter {
> +    union {
> +        qht_iter_func_t retvoid;
> +        qht_iter_bool_func_t retbool;
> +    } f;
> +    enum qht_iter_type type;
> +};
> +
>  /*
>   * Note: reading partially-updated pointers in @pointers could lead to
>   * segfaults. We thus access them with atomic_read/set; this guarantees
> @@ -706,9 +719,10 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t hash)
>      return ret;
>  }
>
> -static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
> -                                   qht_iter_func_t func, void *userp)
> +static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *head,
> +                                   const struct qht_iter *iter, void *userp)
>  {
> +    struct qht_bucket *b = head;
>      int i;
>
>      do {
> @@ -716,7 +730,25 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
>              if (b->pointers[i] == NULL) {
>                  return;
>              }
> -            func(ht, b->pointers[i], b->hashes[i], userp);
> +            switch (iter->type) {
> +            case QHT_ITER_VOID:
> +                iter->f.retvoid(ht, b->pointers[i], b->hashes[i], userp);
> +                break;
> +            case QHT_ITER_RM:
> +                if (iter->f.retbool(ht, b->pointers[i], b->hashes[i], userp)) {
> +                    /* replace i with the last valid element in the bucket */
> +                    seqlock_write_begin(&head->sequence);
> +                    qht_bucket_remove_entry(b, i);
> +                    seqlock_write_end(&head->sequence);
> +                    qht_bucket_debug__locked(b);
> +                    /* reevaluate i, since it just got replaced */
> +                    i--;
> +                    continue;
> +                }
> +                break;
> +            default:
> +                g_assert_not_reached();
> +            }
>          }
>          b = b->next;
>      } while (b);
> @@ -724,26 +756,48 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b,
>
>  /* call with all of the map's locks held */
>  static inline void qht_map_iter__all_locked(struct qht *ht, struct qht_map *map,
> -                                            qht_iter_func_t func, void *userp)
> +                                            const struct qht_iter *iter,
> +                                            void *userp)
>  {
>      size_t i;
>
>      for (i = 0; i < map->n_buckets; i++) {
> -        qht_bucket_iter(ht, &map->buckets[i], func, userp);
> +        qht_bucket_iter(ht, &map->buckets[i], iter, userp);
>      }
>  }
>
> -void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
> +static inline void
> +do_qht_iter(struct qht *ht, const struct qht_iter *iter, void *userp)
>  {
>      struct qht_map *map;
>
>      map = atomic_rcu_read(&ht->map);
>      qht_map_lock_buckets(map);
>      /* Note: ht here is merely for carrying ht->mode; ht->map won't be read */
> -    qht_map_iter__all_locked(ht, map, func, userp);
> +    qht_map_iter__all_locked(ht, map, iter, userp);
>      qht_map_unlock_buckets(map);
>  }
>
> +void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp)
> +{
> +    const struct qht_iter iter = {
> +        .f.retvoid = func,
> +        .type = QHT_ITER_VOID,
> +    };
> +
> +    do_qht_iter(ht, &iter, userp);
> +}
> +
> +void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp)
> +{
> +    const struct qht_iter iter = {
> +        .f.retbool = func,
> +        .type = QHT_ITER_RM,
> +    };
> +
> +    do_qht_iter(ht, &iter, userp);
> +}
> +
>  static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
>  {
>      struct qht_map *new = userp;
> @@ -760,6 +814,10 @@ static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
>  static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
>  {
>      struct qht_map *old;
> +    const struct qht_iter iter = {
> +        .f.retvoid = qht_map_copy,
> +        .type = QHT_ITER_VOID,
> +    };
>
>      old = ht->map;
>      qht_map_lock_buckets(old);
> @@ -774,7 +832,7 @@ static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
>      }
>
>      g_assert(new->n_buckets != old->n_buckets);
> -    qht_map_iter__all_locked(ht, old, qht_map_copy, new);
> +    qht_map_iter__all_locked(ht, old, &iter, new);
>      qht_map_debug__all_locked(new);
>
>      atomic_rcu_set(&ht->map, new);

Otherwise:

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

--
Alex Bennée

Re: [Qemu-devel] [PATCH 3/6] test-qht: test qht_iter_remove

[Alex Bennée]

Emilio G. Cota <cota@braap.org> writes:

> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

> ---
>  tests/test-qht.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 48 insertions(+), 2 deletions(-)
>
> diff --git a/tests/test-qht.c b/tests/test-qht.c
> index dda6a067be..283fb3db39 100644
> --- a/tests/test-qht.c
> +++ b/tests/test-qht.c
> @@ -108,6 +108,49 @@ static void iter_check(unsigned int count)
>      g_assert_cmpuint(curr, ==, count);
>  }
>
> +static void sum_func(struct qht *ht, void *p, uint32_t hash, void *userp)
> +{
> +    uint32_t *sum = userp;
> +    uint32_t a = *(uint32_t *)p;
> +
> +    *sum += a;
> +}
> +
> +static void iter_sum_check(unsigned int expected)
> +{
> +    unsigned int sum = 0;
> +
> +    qht_iter(&ht, sum_func, &sum);
> +    g_assert_cmpuint(sum, ==, expected);
> +}
> +
> +static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *userp)
> +{
> +    uint32_t a = *(uint32_t *)p;
> +    unsigned int mod = *(unsigned int *)userp;
> +
> +    return a % mod == 0;
> +}
> +
> +static void iter_rm_mod(unsigned int mod)
> +{
> +    qht_iter_remove(&ht, rm_mod_func, &mod);
> +}
> +
> +static void iter_rm_mod_check(unsigned int mod)
> +{
> +    unsigned int expected = 0;
> +    unsigned int i;
> +
> +    for (i = 0; i < N; i++) {
> +        if (i % mod == 0) {
> +            continue;
> +        }
> +        expected += i;
> +    }
> +    iter_sum_check(expected);
> +}
> +
>  static void qht_do_test(unsigned int mode, size_t init_entries)
>  {
>      /* under KVM we might fetch stats from an uninitialized qht */
> @@ -138,8 +181,11 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
>      insert(10, 150);
>      check_n(N);
>
> -    rm(1, 2);
> -    check_n(N - 1);
> +    qht_reset(&ht);
> +    insert(0, N);
> +    iter_rm_mod(10);
> +    iter_rm_mod_check(10);
> +    check_n(N * 9 / 10);
>      qht_reset_size(&ht, 0);
>      check_n(0);
>      check(0, N, false);


--
Alex Bennée

Re: [Qemu-devel] [PATCH 4/6] test-qht: test removal of non-existent entries

[Alex Bennée]

Emilio G. Cota <cota@braap.org> writes:

> This improves qht.c code coverage from 89.44% to 90.00%.
>
> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

> ---
>  tests/test-qht.c | 26 ++++++++++++++++++++++++--
>  1 file changed, 24 insertions(+), 2 deletions(-)
>
> diff --git a/tests/test-qht.c b/tests/test-qht.c
> index 283fb3db39..05b1d6807a 100644
> --- a/tests/test-qht.c
> +++ b/tests/test-qht.c
> @@ -41,7 +41,7 @@ static void insert(int a, int b)
>      }
>  }
>
> -static void rm(int init, int end)
> +static void do_rm(int init, int end, bool exist)
>  {
>      int i;
>
> @@ -49,10 +49,24 @@ static void rm(int init, int end)
>          uint32_t hash;
>
>          hash = arr[i];
> -        g_assert_true(qht_remove(&ht, &arr[i], hash));
> +        if (exist) {
> +            g_assert_true(qht_remove(&ht, &arr[i], hash));
> +        } else {
> +            g_assert_false(qht_remove(&ht, &arr[i], hash));
> +        }
>      }
>  }
>
> +static void rm(int init, int end)
> +{
> +    do_rm(init, end, true);
> +}
> +
> +static void rm_nonexist(int init, int end)
> +{
> +    do_rm(init, end, false);
> +}
> +
>  static void check(int a, int b, bool expected)
>  {
>      struct qht_stats stats;
> @@ -157,8 +171,15 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
>      check_n(0);
>
>      qht_init(&ht, is_equal, 0, mode);
> +    rm_nonexist(0, 4);
> +    insert(0, 4);
> +    rm_nonexist(5, 6);
> +    insert(4, 6);
> +    rm_nonexist(7, 8);
> +    iter_rm_mod(1);
>
>      check_n(0);
> +    rm_nonexist(0, 10);
>      insert(0, N);
>      check(0, N, true);
>      check_n(N);
> @@ -183,6 +204,7 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
>
>      qht_reset(&ht);
>      insert(0, N);
> +    rm_nonexist(N, N + 32);
>      iter_rm_mod(10);
>      iter_rm_mod_check(10);
>      check_n(N * 9 / 10);


--
Alex Bennée

Re: [Qemu-devel] [PATCH 5/6] test-qht: test deletion of the last entry in a bucket

[Alex Bennée]

Emilio G. Cota <cota@braap.org> writes:

> This improves coverage by one (!) LoC in qht.c, bringing the
> coverage rate up from 90.00% to 90.28%.
>
> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

> ---
>  tests/test-qht.c | 13 ++++++++++++-
>  1 file changed, 12 insertions(+), 1 deletion(-)
>
> diff --git a/tests/test-qht.c b/tests/test-qht.c
> index 05b1d6807a..77666e8c5f 100644
> --- a/tests/test-qht.c
> +++ b/tests/test-qht.c
> @@ -172,9 +172,20 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
>
>      qht_init(&ht, is_equal, 0, mode);
>      rm_nonexist(0, 4);
> +    /*
> +     * Test that we successfully delete the last element in a bucket.
> +     * This is a hard-to-reach code path when resizing is on, but without
> +     * resizing we can easily hit it if init_entries <= 1.
> +     * Given that the number of elements per bucket can be 4 or 6 depending on
> +     * the host's pointer size, test the removal of the 4th and 6th elements.
> +     */
>      insert(0, 4);
>      rm_nonexist(5, 6);
> -    insert(4, 6);
> +    rm(3, 4);
> +    check_n(3);
> +    insert(3, 6);
> +    rm(5, 6);
> +    check_n(5);
>      rm_nonexist(7, 8);
>      iter_rm_mod(1);


--
Alex Bennée

Re: [Qemu-devel] [PATCH 6/6] test-qht: speed up + test qht_resize

[Alex Bennée]

Emilio G. Cota <cota@braap.org> writes:

> Perform first the tests that exercise code paths that are
> easier to hit at small table sizes, and then resize the table
> to speed up subsequent tests. If this resize is not too large,
> we can make the test faster with no code coverage loss.
>
> - With gcov enabled:
>
> Before: 20.568s, 90.28% qht.c coverage
> After:   5.168s, 93.06% qht.c coverage
>
> The coverage increase is entirely due to calling qht_resize,
> which we weren't calling before. Note that the code paths
> that remain to be tested are either error handling or
> can only occur when several threads are accessing the
> hash table concurrently (e.g. seqlock retry, trylock fail).
>
> - Without gcov:
>
> Before: 1.987s
> After:  0.528s
>
> The speedup is almost the same as with gcov, although the
> "before" run is a lot faster.
>
> Signed-off-by: Emilio G. Cota <cota@braap.org>

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>

> ---
>  tests/test-qht.c | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/tests/test-qht.c b/tests/test-qht.c
> index 77666e8c5f..1ec039d636 100644
> --- a/tests/test-qht.c
> +++ b/tests/test-qht.c
> @@ -189,6 +189,10 @@ static void qht_do_test(unsigned int mode, size_t init_entries)
>      rm_nonexist(7, 8);
>      iter_rm_mod(1);
>
> +    if (!(mode & QHT_MODE_AUTO_RESIZE)) {
> +        qht_resize(&ht, init_entries * 4 + 4);
> +    }
> +
>      check_n(0);
>      rm_nonexist(0, 10);
>      insert(0, N);


--
Alex Bennée

Re: [Qemu-devel] [PATCH 2/6] qht: add qht_iter_remove

[Emilio G. Cota]

On Fri, Sep 07, 2018 at 15:51:12 +0100, Alex Bennée wrote:
> 
> Emilio G. Cota <cota@braap.org> writes:
> 
> > This currently has no users, but the use case is so common that I
> > think we must support it.
> >
> > Note that without the appended we cannot safely remove a set of
> > elements; a 2-step approach (i.e. qht_iter first, keep track of
> > the to-be-deleted elements, and then a bunch of qht_remove calls)
> > would be racy, since between the iteration and the removals other
> > threads might insert additional elements.
> >
> > Signed-off-by: Emilio G. Cota <cota@braap.org>
> > ---
> >  include/qemu/qht.h | 19 ++++++++++++
> >  util/qht.c         | 74 +++++++++++++++++++++++++++++++++++++++++-----
> >  2 files changed, 85 insertions(+), 8 deletions(-)
> >
> > diff --git a/include/qemu/qht.h b/include/qemu/qht.h
> > index 1fb9116fa0..91bc9b00cf 100644
> > --- a/include/qemu/qht.h
> > +++ b/include/qemu/qht.h
> > @@ -44,6 +44,8 @@ struct qht_stats {
> >
> >  typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp);
> >  typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up);
> > +typedef bool (*qht_iter_bool_func_t)(struct qht *ht, void *p, uint32_t h,
> > +                                     void *up);
> >
> >  #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */
> >
> > @@ -178,9 +180,26 @@ bool qht_resize(struct qht *ht, size_t n_elems);
> >   *
> >   * Each time it is called, user-provided @func is passed a pointer-hash pair,
> >   * plus @userp.
> > + *
> > + * Note: @ht cannot be accessed from @func
> 
> I'm confused by this comment. If @ht cannot be accessed (or shouldn't be
> accessed) from @func then why are we passing it?

We could probably do without. My original thinking was to pass the *ht
to tell the iter function which ht his k-v pair comes from.
But that's not a common use case, so we should remove it to
simplify the interface.

I think the comment is important right now; note that we can't even
perform a lookup from the callback without deadlock.

So I'll take your R-b for this patch and remove the *ht in
another patch.

Thanks,

		Emilio