[Qemu-devel] [PATCH v2 00/12] qht improvements for 3.1

[Qemu-devel] [PATCH v2 00/12] qht improvements for 3.1

[Emilio G. Cota]

v1: https://github.com/cota/qemu/tree/qht-for-3.1-v2

Changes since v1:

- Added Alex's R-b tags to patches 1-6
- Added a patch to drop *ht from qht_iter and qht_iter_remove,
  as suggested by Alex.
- Added some constification patches
- Added a flag to qht-bench to precompute the hashes, which
  allows us to spend more time accessing the hash table
  thereby yielding higher throughput.

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

Thanks,

		Emilio

[Qemu-devel] [PATCH v2 01/12] qht: remove unused map param from qht_remove__locked

[Emilio G. Cota]

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
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 1e3a072e25..28d9273371 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -692,8 +692,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;
@@ -728,7 +727,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 v2 02/12] 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.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
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 c9a11cc29a..3a9618db69 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 */
 #define QHT_MODE_RAW_MUTEXES 0x2 /* bypass the profiler (QSP) */
@@ -179,9 +181,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 28d9273371..c190e89f5b 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;
+};
+
 /*
  * Do _not_ use qemu_mutex_[try]lock directly! Use these macros, otherwise
  * the profiler (QSP) will deadlock.
@@ -733,9 +746,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 {
@@ -743,7 +757,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);
@@ -751,26 +783,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;
@@ -787,6 +841,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);
@@ -801,7 +859,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 v2 03/12] test-qht: test qht_iter_remove

[Emilio G. Cota]

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
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 v2 04/12] test-qht: test removal of non-existent entries

[Emilio G. Cota]

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

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
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 v2 05/12] 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%.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
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 v2 06/12] 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.

Reviewed-by: Alex Bennée <alex.bennee@linaro.org>
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

[Qemu-devel] [PATCH v2 07/12] qht: drop ht argument from qht iterators

[Emilio G. Cota]

Accessing the HT from an iterator results almost always
in a deadlock. Given that only one qht-internal function
uses this argument, drop it from the interface.

Suggested-by: Alex Bennée <alex.bennee@linaro.org>
Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 include/qemu/qht.h        |  5 ++---
 accel/tcg/translate-all.c |  6 ++----
 tests/test-qht.c          |  6 +++---
 util/qht.c                | 29 +++++++++++++++++++----------
 util/qsp.c                | 11 +++++------
 5 files changed, 31 insertions(+), 26 deletions(-)

diff --git a/include/qemu/qht.h b/include/qemu/qht.h
index 3a9618db69..6484837487 100644
--- a/include/qemu/qht.h
+++ b/include/qemu/qht.h
@@ -43,9 +43,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);
+typedef void (*qht_iter_func_t)(void *p, uint32_t h, void *up);
+typedef bool (*qht_iter_bool_func_t)(void *p, uint32_t h, void *up);
 
 #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */
 #define QHT_MODE_RAW_MUTEXES 0x2 /* bypass the profiler (QSP) */
diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c
index 898c3bb3d1..9ffbbc2fbd 100644
--- a/accel/tcg/translate-all.c
+++ b/accel/tcg/translate-all.c
@@ -1282,8 +1282,7 @@ void tb_flush(CPUState *cpu)
  */
 #ifdef CONFIG_USER_ONLY
 
-static void
-do_tb_invalidate_check(struct qht *ht, void *p, uint32_t hash, void *userp)
+static void do_tb_invalidate_check(void *p, uint32_t hash, void *userp)
 {
     TranslationBlock *tb = p;
     target_ulong addr = *(target_ulong *)userp;
@@ -1304,8 +1303,7 @@ static void tb_invalidate_check(target_ulong address)
     qht_iter(&tb_ctx.htable, do_tb_invalidate_check, &address);
 }
 
-static void
-do_tb_page_check(struct qht *ht, void *p, uint32_t hash, void *userp)
+static void do_tb_page_check(void *p, uint32_t hash, void *userp)
 {
     TranslationBlock *tb = p;
     int flags1, flags2;
diff --git a/tests/test-qht.c b/tests/test-qht.c
index 1ec039d636..4d23cefab6 100644
--- a/tests/test-qht.c
+++ b/tests/test-qht.c
@@ -98,7 +98,7 @@ static void check(int a, int b, bool expected)
     qht_statistics_destroy(&stats);
 }
 
-static void count_func(struct qht *ht, void *p, uint32_t hash, void *userp)
+static void count_func(void *p, uint32_t hash, void *userp)
 {
     unsigned int *curr = userp;
 
@@ -122,7 +122,7 @@ 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)
+static void sum_func(void *p, uint32_t hash, void *userp)
 {
     uint32_t *sum = userp;
     uint32_t a = *(uint32_t *)p;
@@ -138,7 +138,7 @@ static void iter_sum_check(unsigned int expected)
     g_assert_cmpuint(sum, ==, expected);
 }
 
-static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *userp)
+static bool rm_mod_func(void *p, uint32_t hash, void *userp)
 {
     uint32_t a = *(uint32_t *)p;
     unsigned int mod = *(unsigned int *)userp;
diff --git a/util/qht.c b/util/qht.c
index c190e89f5b..50ed7a2102 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -746,7 +746,7 @@ 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 *head,
+static inline void qht_bucket_iter(struct qht_bucket *head,
                                    const struct qht_iter *iter, void *userp)
 {
     struct qht_bucket *b = head;
@@ -759,10 +759,10 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *head,
             }
             switch (iter->type) {
             case QHT_ITER_VOID:
-                iter->f.retvoid(ht, b->pointers[i], b->hashes[i], userp);
+                iter->f.retvoid(b->pointers[i], b->hashes[i], userp);
                 break;
             case QHT_ITER_RM:
-                if (iter->f.retbool(ht, b->pointers[i], b->hashes[i], userp)) {
+                if (iter->f.retbool(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);
@@ -782,14 +782,14 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *head,
 }
 
 /* call with all of the map's locks held */
-static inline void qht_map_iter__all_locked(struct qht *ht, struct qht_map *map,
+static inline void qht_map_iter__all_locked(struct qht_map *map,
                                             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], iter, userp);
+        qht_bucket_iter(&map->buckets[i], iter, userp);
     }
 }
 
@@ -800,8 +800,7 @@ do_qht_iter(struct qht *ht, const struct qht_iter *iter, void *userp)
 
     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, iter, userp);
+    qht_map_iter__all_locked(map, iter, userp);
     qht_map_unlock_buckets(map);
 }
 
@@ -825,9 +824,16 @@ void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp)
     do_qht_iter(ht, &iter, userp);
 }
 
-static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp)
+struct qht_map_copy_data {
+    struct qht *ht;
+    struct qht_map *new;
+};
+
+static void qht_map_copy(void *p, uint32_t hash, void *userp)
 {
-    struct qht_map *new = userp;
+    struct qht_map_copy_data *data = userp;
+    struct qht *ht = data->ht;
+    struct qht_map *new = data->new;
     struct qht_bucket *b = qht_map_to_bucket(new, hash);
 
     /* no need to acquire b->lock because no thread has seen this map yet */
@@ -845,6 +851,7 @@ static void qht_do_resize_reset(struct qht *ht, struct qht_map *new, bool reset)
         .f.retvoid = qht_map_copy,
         .type = QHT_ITER_VOID,
     };
+    struct qht_map_copy_data data;
 
     old = ht->map;
     qht_map_lock_buckets(old);
@@ -859,7 +866,9 @@ 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, &iter, new);
+    data.ht = ht;
+    data.new = new;
+    qht_map_iter__all_locked(old, &iter, &data);
     qht_map_debug__all_locked(new);
 
     atomic_rcu_set(&ht->map, new);
diff --git a/util/qsp.c b/util/qsp.c
index b0c2575d10..2de3a97594 100644
--- a/util/qsp.c
+++ b/util/qsp.c
@@ -533,7 +533,7 @@ static gint qsp_tree_cmp(gconstpointer ap, gconstpointer bp, gpointer up)
     }
 }
 
-static void qsp_sort(struct qht *ht, void *p, uint32_t h, void *userp)
+static void qsp_sort(void *p, uint32_t h, void *userp)
 {
     QSPEntry *e = p;
     GTree *tree = userp;
@@ -541,7 +541,7 @@ static void qsp_sort(struct qht *ht, void *p, uint32_t h, void *userp)
     g_tree_insert(tree, e, NULL);
 }
 
-static void qsp_aggregate(struct qht *global_ht, void *p, uint32_t h, void *up)
+static void qsp_aggregate(void *p, uint32_t h, void *up)
 {
     struct qht *ht = up;
     const QSPEntry *e = p;
@@ -553,7 +553,7 @@ static void qsp_aggregate(struct qht *global_ht, void *p, uint32_t h, void *up)
     qsp_entry_aggregate(agg, e);
 }
 
-static void qsp_iter_diff(struct qht *orig, void *p, uint32_t hash, void *htp)
+static void qsp_iter_diff(void *p, uint32_t hash, void *htp)
 {
     struct qht *ht = htp;
     QSPEntry *old = p;
@@ -583,8 +583,7 @@ static void qsp_diff(struct qht *orig, struct qht *new)
     qht_iter(orig, qsp_iter_diff, new);
 }
 
-static void
-qsp_iter_callsite_coalesce(struct qht *orig, void *p, uint32_t h, void *htp)
+static void qsp_iter_callsite_coalesce(void *p, uint32_t h, void *htp)
 {
     struct qht *ht = htp;
     QSPEntry *old = p;
@@ -603,7 +602,7 @@ qsp_iter_callsite_coalesce(struct qht *orig, void *p, uint32_t h, void *htp)
     e->n_acqs += old->n_acqs;
 }
 
-static void qsp_ht_delete(struct qht *ht, void *p, uint32_t h, void *htp)
+static void qsp_ht_delete(void *p, uint32_t h, void *htp)
 {
     g_free(p);
 }
-- 
2.17.1

[Qemu-devel] [PATCH v2 08/12] qht: fix comment in qht_bucket_remove_entry

[Emilio G. Cota]

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

diff --git a/util/qht.c b/util/qht.c
index 50ed7a2102..3564a7e20f 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -671,7 +671,7 @@ qht_entry_move(struct qht_bucket *to, int i, struct qht_bucket *from, int j)
 }
 
 /*
- * Find the last valid entry in @head, and swap it with @orig[pos], which has
+ * Find the last valid entry in @orig, and swap it with @orig[pos], which has
  * just been invalidated.
  */
 static inline void qht_bucket_remove_entry(struct qht_bucket *orig, int pos)
-- 
2.17.1

[Qemu-devel] [PATCH v2 09/12] qht: constify qht_lookup

[Emilio G. Cota]

seqlock_read_begin takes a const param since c04649eeea
("seqlock: constify seqlock_read_begin", 2018-08-23), so
we can constify the entire lookup.

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

diff --git a/include/qemu/qht.h b/include/qemu/qht.h
index 6484837487..2e2d6bca93 100644
--- a/include/qemu/qht.h
+++ b/include/qemu/qht.h
@@ -104,7 +104,7 @@ bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing);
  * Returns the corresponding pointer when a match is found.
  * Returns NULL otherwise.
  */
-void *qht_lookup_custom(struct qht *ht, const void *userp, uint32_t hash,
+void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash,
                         qht_lookup_func_t func);
 
 /**
@@ -115,7 +115,7 @@ void *qht_lookup_custom(struct qht *ht, const void *userp, uint32_t hash,
  *
  * Calls qht_lookup_custom() using @ht's default comparison function.
  */
-void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash);
+void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash);
 
 /**
  * qht_remove - remove a pointer from the hash table
diff --git a/util/qht.c b/util/qht.c
index 3564a7e20f..020dfe6912 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -236,7 +236,7 @@ static inline void qht_head_init(struct qht_bucket *b)
 }
 
 static inline
-struct qht_bucket *qht_map_to_bucket(struct qht_map *map, uint32_t hash)
+struct qht_bucket *qht_map_to_bucket(const struct qht_map *map, uint32_t hash)
 {
     return &map->buckets[hash & (map->n_buckets - 1)];
 }
@@ -482,10 +482,10 @@ bool qht_reset_size(struct qht *ht, size_t n_elems)
 }
 
 static inline
-void *qht_do_lookup(struct qht_bucket *head, qht_lookup_func_t func,
+void *qht_do_lookup(const struct qht_bucket *head, qht_lookup_func_t func,
                     const void *userp, uint32_t hash)
 {
-    struct qht_bucket *b = head;
+    const struct qht_bucket *b = head;
     int i;
 
     do {
@@ -509,7 +509,7 @@ void *qht_do_lookup(struct qht_bucket *head, qht_lookup_func_t func,
 }
 
 static __attribute__((noinline))
-void *qht_lookup__slowpath(struct qht_bucket *b, qht_lookup_func_t func,
+void *qht_lookup__slowpath(const struct qht_bucket *b, qht_lookup_func_t func,
                            const void *userp, uint32_t hash)
 {
     unsigned int version;
@@ -522,11 +522,11 @@ void *qht_lookup__slowpath(struct qht_bucket *b, qht_lookup_func_t func,
     return ret;
 }
 
-void *qht_lookup_custom(struct qht *ht, const void *userp, uint32_t hash,
+void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash,
                         qht_lookup_func_t func)
 {
-    struct qht_bucket *b;
-    struct qht_map *map;
+    const struct qht_bucket *b;
+    const struct qht_map *map;
     unsigned int version;
     void *ret;
 
@@ -545,7 +545,7 @@ void *qht_lookup_custom(struct qht *ht, const void *userp, uint32_t hash,
     return qht_lookup__slowpath(b, func, userp, hash);
 }
 
-void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash)
+void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash)
 {
     return qht_lookup_custom(ht, userp, hash, ht->cmp);
 }
-- 
2.17.1

[Qemu-devel] [PATCH v2 10/12] qht: constify qht_statistics_init

[Emilio G. Cota]

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

diff --git a/include/qemu/qht.h b/include/qemu/qht.h
index 2e2d6bca93..758c7ac6c8 100644
--- a/include/qemu/qht.h
+++ b/include/qemu/qht.h
@@ -211,7 +211,7 @@ void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp);
  * When done with @stats, pass the struct to qht_statistics_destroy().
  * Failing to do this will leak memory.
  */
-void qht_statistics_init(struct qht *ht, struct qht_stats *stats);
+void qht_statistics_init(const struct qht *ht, struct qht_stats *stats);
 
 /**
  * qht_statistics_destroy - Destroy a &struct qht_stats
diff --git a/util/qht.c b/util/qht.c
index 020dfe6912..4378775d68 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -895,9 +895,9 @@ bool qht_resize(struct qht *ht, size_t n_elems)
 }
 
 /* pass @stats to qht_statistics_destroy() when done */
-void qht_statistics_init(struct qht *ht, struct qht_stats *stats)
+void qht_statistics_init(const struct qht *ht, struct qht_stats *stats)
 {
-    struct qht_map *map;
+    const struct qht_map *map;
     int i;
 
     map = atomic_rcu_read(&ht->map);
@@ -914,8 +914,8 @@ void qht_statistics_init(struct qht *ht, struct qht_stats *stats)
     stats->head_buckets = map->n_buckets;
 
     for (i = 0; i < map->n_buckets; i++) {
-        struct qht_bucket *head = &map->buckets[i];
-        struct qht_bucket *b;
+        const struct qht_bucket *head = &map->buckets[i];
+        const struct qht_bucket *b;
         unsigned int version;
         size_t buckets;
         size_t entries;
-- 
2.17.1

[Qemu-devel] [PATCH v2 11/12] qht: constify arguments to some internal functions

[Emilio G. Cota]

These functions do not modify their @ht or @bucket arguments.
Constify those arguments.

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

diff --git a/util/qht.c b/util/qht.c
index 4378775d68..aa51be3c52 100644
--- a/util/qht.c
+++ b/util/qht.c
@@ -268,7 +268,8 @@ static void qht_map_unlock_buckets(struct qht_map *map)
  * Call with at least a bucket lock held.
  * @map should be the value read before acquiring the lock (or locks).
  */
-static inline bool qht_map_is_stale__locked(struct qht *ht, struct qht_map *map)
+static inline bool qht_map_is_stale__locked(const struct qht *ht,
+                                            const struct qht_map *map)
 {
     return map != ht->map;
 }
@@ -337,12 +338,12 @@ struct qht_bucket *qht_bucket_lock__no_stale(struct qht *ht, uint32_t hash,
     return b;
 }
 
-static inline bool qht_map_needs_resize(struct qht_map *map)
+static inline bool qht_map_needs_resize(const struct qht_map *map)
 {
     return atomic_read(&map->n_added_buckets) > map->n_added_buckets_threshold;
 }
 
-static inline void qht_chain_destroy(struct qht_bucket *head)
+static inline void qht_chain_destroy(const struct qht_bucket *head)
 {
     struct qht_bucket *curr = head->next;
     struct qht_bucket *prev;
@@ -550,8 +551,11 @@ void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash)
     return qht_lookup_custom(ht, userp, hash, ht->cmp);
 }
 
-/* call with head->lock held */
-static void *qht_insert__locked(struct qht *ht, struct qht_map *map,
+/*
+ * call with head->lock held
+ * @ht is const since it is only used for ht->cmp()
+ */
+static void *qht_insert__locked(const struct qht *ht, struct qht_map *map,
                                 struct qht_bucket *head, void *p, uint32_t hash,
                                 bool *needs_resize)
 {
@@ -645,7 +649,7 @@ bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing)
     return false;
 }
 
-static inline bool qht_entry_is_last(struct qht_bucket *b, int pos)
+static inline bool qht_entry_is_last(const struct qht_bucket *b, int pos)
 {
     if (pos == QHT_BUCKET_ENTRIES - 1) {
         if (b->next == NULL) {
-- 
2.17.1

[Qemu-devel] [PATCH v2 12/12] qht-bench: add -p flag to precompute hash values

[Emilio G. Cota]

Precomputing the hash values allows us to perform more frequent
accesses to the hash table, thereby reaching higher throughputs.

We keep the old behaviour by default, since (1) we might confuse
users if they measured a speedup without changing anything in
the QHT implementation, and (2) benchmarking the hash function
"on line" is also valuable.

Before:
$ taskset -c 0 tests/qht-bench -n 1
 Throughput:        38.18 MT/s

After:
$ taskset -c 0 tests/qht-bench -n 1
 Throughput:        38.16 MT/s

After (with precomputing):
$ taskset -c 0 tests/qht-bench -n 1 -p
 Throughput:        50.87 MT/s

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

diff --git a/tests/qht-bench.c b/tests/qht-bench.c
index f492b3a20a..2089e2bed1 100644
--- a/tests/qht-bench.c
+++ b/tests/qht-bench.c
@@ -53,6 +53,7 @@ static unsigned long resize_delay = 1000;
 static double resize_rate; /* 0.0 to 1.0 */
 static unsigned int n_rz_threads = 1;
 static QemuThread *rz_threads;
+static bool precompute_hash;
 
 static double update_rate; /* 0.0 to 1.0 */
 static uint64_t update_threshold;
@@ -101,11 +102,18 @@ static bool is_equal(const void *ap, const void *bp)
     return *a == *b;
 }
 
-static inline uint32_t h(unsigned long v)
+static uint32_t h(unsigned long v)
 {
     return tb_hash_func7(v, 0, 0, 0, 0);
 }
 
+static uint32_t hval(unsigned long v)
+{
+    return v;
+}
+
+static uint32_t (*hfunc)(unsigned long v) = h;
+
 /*
  * From: https://en.wikipedia.org/wiki/Xorshift
  * This is faster than rand_r(), and gives us a wider range (RAND_MAX is only
@@ -149,7 +157,7 @@ static void do_rw(struct thread_info *info)
         bool read;
 
         p = &keys[info->r & (lookup_range - 1)];
-        hash = h(*p);
+        hash = hfunc(*p);
         read = qht_lookup(&ht, p, hash);
         if (read) {
             stats->rd++;
@@ -158,7 +166,7 @@ static void do_rw(struct thread_info *info)
         }
     } else {
         p = &keys[info->r & (update_range - 1)];
-        hash = h(*p);
+        hash = hfunc(*p);
         if (info->write_op) {
             bool written = false;
 
@@ -289,7 +297,9 @@ static void htable_init(void)
     /* avoid allocating memory later by allocating all the keys now */
     keys = g_malloc(sizeof(*keys) * n);
     for (i = 0; i < n; i++) {
-        keys[i] = populate_offset + i;
+        long val = populate_offset + i;
+
+        keys[i] = precompute_hash ? h(val) : hval(val);
     }
 
     /* some sanity checks */
@@ -321,7 +331,7 @@ static void htable_init(void)
 
             r = xorshift64star(r);
             p = &keys[r & (init_range - 1)];
-            hash = h(*p);
+            hash = hfunc(*p);
             if (qht_insert(&ht, p, hash, NULL)) {
                 break;
             }
@@ -412,7 +422,7 @@ static void parse_args(int argc, char *argv[])
     int c;
 
     for (;;) {
-        c = getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:r:Rs:S:u:");
+        c = getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:pr:Rs:S:u:");
         if (c < 0) {
             break;
         }
@@ -451,6 +461,10 @@ static void parse_args(int argc, char *argv[])
         case 'o':
             populate_offset = atol(optarg);
             break;
+        case 'p':
+            precompute_hash = true;
+            hfunc = hval;
+            break;
         case 'r':
             update_range = pow2ceil(atol(optarg));
             break;
-- 
2.17.1

Re: [Qemu-devel] [PATCH v2 12/12] qht-bench: add -p flag to precompute hash values

[Richard Henderson]

On 09/10/2018 11:58 AM, Emilio G. Cota wrote:
> @@ -289,7 +297,9 @@ static void htable_init(void)
>      /* avoid allocating memory later by allocating all the keys now */
>      keys = g_malloc(sizeof(*keys) * n);
>      for (i = 0; i < n; i++) {
> -        keys[i] = populate_offset + i;
> +        long val = populate_offset + i;
> +
> +        keys[i] = precompute_hash ? h(val) : hval(val);

hfunc?


r~

Re: [Qemu-devel] [PATCH v2 12/12] qht-bench: add -p flag to precompute hash values

[Emilio G. Cota]

On Tue, Sep 11, 2018 at 17:46:41 -0700, Richard Henderson wrote:
> On 09/10/2018 11:58 AM, Emilio G. Cota wrote:
> > @@ -289,7 +297,9 @@ static void htable_init(void)
> >      /* avoid allocating memory later by allocating all the keys now */
> >      keys = g_malloc(sizeof(*keys) * n);
> >      for (i = 0; i < n; i++) {
> > -        keys[i] = populate_offset + i;
> > +        long val = populate_offset + i;
> > +
> > +        keys[i] = precompute_hash ? h(val) : hval(val);
> 
> hfunc?

Here is where precomputation happens, so if precompute_hash is set,
then we insert the hashed value. Otherwise we insert the non-hashed
value (with hval()). In all other instances we use hfunc, since
hfunc is set to the "other" hash function wrt the above--see
this later hunk:

@@ -451,6 +461,10 @@ static void parse_args(int argc, char *argv[])
         case 'o':
             populate_offset = atol(optarg);
             break;
+        case 'p':
+            precompute_hash = true;
+            hfunc = hval;
+            break;

Thanks,

		Emilio

Re: [Qemu-devel] [PATCH v2 00/12] qht improvements for 3.1

[Richard Henderson]

On 09/10/2018 11:58 AM, Emilio G. Cota wrote:
> v1: https://github.com/cota/qemu/tree/qht-for-3.1-v2
> 
> Changes since v1:
> 
> - Added Alex's R-b tags to patches 1-6
> - Added a patch to drop *ht from qht_iter and qht_iter_remove,
>   as suggested by Alex.
> - Added some constification patches
> - Added a flag to qht-bench to precompute the hashes, which
>   allows us to spend more time accessing the hash table
>   thereby yielding higher throughput.
> 
> You can fetch this series from:
>   https://github.com/cota/qemu/tree/qht-for-3.1-v2

Applied to tcg-next.


r~