Merge tag 'pull-tcg-20230328' of https://gitlab.com/rth7680/qemu into staging

Use a local version of GTree [#285]
Fix page_set_flags vs the last page of the address space [#1528]
Re-enable gdbstub breakpoints under KVM

# -----BEGIN PGP SIGNATURE-----
#
# iQFRBAABCgA7FiEEekgeeIaLTbaoWgXAZN846K9+IV8FAmQjcLIdHHJpY2hhcmQu
# aGVuZGVyc29uQGxpbmFyby5vcmcACgkQZN846K9+IV8rkgf/ZazodovRKxfaO622
# mGW7ywIm+hIZYmKC7ObiMKFrBoCyeXH9yOLSx42T70QstWvBMukjovLMz1+Ttbo1
# VOvpGH2B5W76l3i+muAlKxFRbBH2kMLTaL+BXtkmkL4FJ9bS8WiPApsL3lEX/q2E
# 3kqaT3N3C09sWO5oVAPGTUHL0EutKhOar2VZL0+PVPFzL3BNPhnQH9QcbNvDBV3n
# cx3GSXZyL7Plyi+qwsKf/3Jo+F2wr2NVf3Dqscu9T1N1kI5hSjRpwqUEJzJZ5rei
# ly/gBXC/J7+WN+x+w2JlN0kWXWqC0QbDfZnj96Pd3owWZ7j4sT9zR5fcNenecxlR
# 38Bo0w==
# =ysF7
# -----END PGP SIGNATURE-----
# gpg: Signature made Tue 28 Mar 2023 23:56:50 BST
# gpg:                using RSA key 7A481E78868B4DB6A85A05C064DF38E8AF7E215F
# gpg:                issuer "richard.henderson@linaro.org"
# gpg: Good signature from "Richard Henderson <richard.henderson@linaro.org>" [full]
# Primary key fingerprint: 7A48 1E78 868B 4DB6 A85A  05C0 64DF 38E8 AF7E 215F

* tag 'pull-tcg-20230328' of https://gitlab.com/rth7680/qemu:
  softmmu: Restore use of CPU watchpoint for all accelerators
  softmmu/watchpoint: Add missing 'qemu/error-report.h' include
  softmmu: Restrict cpu_check_watchpoint / address_matches to TCG accel
  linux-user/arm: Take more care allocating commpage
  include/exec: Change reserved_va semantics to last byte
  linux-user: Pass last not end to probe_guest_base
  accel/tcg: Pass last not end to tb_invalidate_phys_range
  accel/tcg: Pass last not end to tb_invalidate_phys_page_range__locked
  accel/tcg: Pass last not end to page_collection_lock
  accel/tcg: Pass last not end to PAGE_FOR_EACH_TB
  accel/tcg: Pass last not end to page_reset_target_data
  accel/tcg: Pass last not end to page_set_flags
  linux-user: Diagnose misaligned -R size
  tcg: use QTree instead of GTree
  util: import GTree as QTree

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>

4 files changed, 624 insertions, 0 deletions

diff --git a/tests/bench/meson.build b/tests/bench/meson.build
index 7477a1f..4e6b469 100644
--- a/tests/bench/meson.build
+++ b/tests/bench/meson.build
@@ -9,6 +9,10 @@ xbzrle_bench = executable('xbzrle-bench',
                        dependencies: [qemuutil,migration])
 endif
 
+qtree_bench = executable('qtree-bench',
+                         sources: 'qtree-bench.c',
+                         dependencies: [qemuutil])
+
 executable('atomic_add-bench',
            sources: files('atomic_add-bench.c'),
            dependencies: [qemuutil],
diff --git a/tests/bench/qtree-bench.c b/tests/bench/qtree-bench.c
new file mode 100644
index 0000000..f3d7edc
--- /dev/null
+++ b/tests/bench/qtree-bench.c
@@ -0,0 +1,286 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#include "qemu/osdep.h"
+#include "qemu/qtree.h"
+#include "qemu/timer.h"
+
+enum tree_op {
+    OP_LOOKUP,
+    OP_INSERT,
+    OP_REMOVE,
+    OP_REMOVE_ALL,
+    OP_TRAVERSE,
+};
+
+struct benchmark {
+    const char * const name;
+    enum tree_op op;
+    bool fill_on_init;
+};
+
+enum impl_type {
+    IMPL_GTREE,
+    IMPL_QTREE,
+};
+
+struct tree_implementation {
+    const char * const name;
+    enum impl_type type;
+};
+
+static const struct benchmark benchmarks[] = {
+    {
+        .name = "Lookup",
+        .op = OP_LOOKUP,
+        .fill_on_init = true,
+    },
+    {
+        .name = "Insert",
+        .op = OP_INSERT,
+        .fill_on_init = false,
+    },
+    {
+        .name = "Remove",
+        .op = OP_REMOVE,
+        .fill_on_init = true,
+    },
+    {
+        .name = "RemoveAll",
+        .op = OP_REMOVE_ALL,
+        .fill_on_init = true,
+    },
+    {
+        .name = "Traverse",
+        .op = OP_TRAVERSE,
+        .fill_on_init = true,
+    },
+};
+
+static const struct tree_implementation impls[] = {
+    {
+        .name = "GTree",
+        .type = IMPL_GTREE,
+    },
+    {
+        .name = "QTree",
+        .type = IMPL_QTREE,
+    },
+};
+
+static int compare_func(const void *ap, const void *bp)
+{
+    const size_t *a = ap;
+    const size_t *b = bp;
+
+    return *a - *b;
+}
+
+static void init_empty_tree_and_keys(enum impl_type impl,
+                                     void **ret_tree, size_t **ret_keys,
+                                     size_t n_elems)
+{
+    size_t *keys = g_malloc_n(n_elems, sizeof(*keys));
+    for (size_t i = 0; i < n_elems; i++) {
+        keys[i] = i;
+    }
+
+    void *tree;
+    switch (impl) {
+    case IMPL_GTREE:
+        tree = g_tree_new(compare_func);
+        break;
+    case IMPL_QTREE:
+        tree = q_tree_new(compare_func);
+        break;
+    default:
+        g_assert_not_reached();
+    }
+
+    *ret_tree = tree;
+    *ret_keys = keys;
+}
+
+static gboolean traverse_func(gpointer key, gpointer value, gpointer data)
+{
+    return FALSE;
+}
+
+static inline void remove_all(void *tree, enum impl_type impl)
+{
+    switch (impl) {
+    case IMPL_GTREE:
+        g_tree_destroy(tree);
+        break;
+    case IMPL_QTREE:
+        q_tree_destroy(tree);
+        break;
+    default:
+        g_assert_not_reached();
+    }
+}
+
+static int64_t run_benchmark(const struct benchmark *bench,
+                             enum impl_type impl,
+                             size_t n_elems)
+{
+    void *tree;
+    size_t *keys;
+
+    init_empty_tree_and_keys(impl, &tree, &keys, n_elems);
+    if (bench->fill_on_init) {
+        for (size_t i = 0; i < n_elems; i++) {
+            switch (impl) {
+            case IMPL_GTREE:
+                g_tree_insert(tree, &keys[i], &keys[i]);
+                break;
+            case IMPL_QTREE:
+                q_tree_insert(tree, &keys[i], &keys[i]);
+                break;
+            default:
+                g_assert_not_reached();
+            }
+        }
+    }
+
+    int64_t start_ns = get_clock();
+    switch (bench->op) {
+    case OP_LOOKUP:
+        for (size_t i = 0; i < n_elems; i++) {
+            void *value;
+            switch (impl) {
+            case IMPL_GTREE:
+                value = g_tree_lookup(tree, &keys[i]);
+                break;
+            case IMPL_QTREE:
+                value = q_tree_lookup(tree, &keys[i]);
+                break;
+            default:
+                g_assert_not_reached();
+            }
+            (void)value;
+        }
+        break;
+    case OP_INSERT:
+        for (size_t i = 0; i < n_elems; i++) {
+            switch (impl) {
+            case IMPL_GTREE:
+                g_tree_insert(tree, &keys[i], &keys[i]);
+                break;
+            case IMPL_QTREE:
+                q_tree_insert(tree, &keys[i], &keys[i]);
+                break;
+            default:
+                g_assert_not_reached();
+            }
+        }
+        break;
+    case OP_REMOVE:
+        for (size_t i = 0; i < n_elems; i++) {
+            switch (impl) {
+            case IMPL_GTREE:
+                g_tree_remove(tree, &keys[i]);
+                break;
+            case IMPL_QTREE:
+                q_tree_remove(tree, &keys[i]);
+                break;
+            default:
+                g_assert_not_reached();
+            }
+        }
+        break;
+    case OP_REMOVE_ALL:
+        remove_all(tree, impl);
+        break;
+    case OP_TRAVERSE:
+        switch (impl) {
+        case IMPL_GTREE:
+            g_tree_foreach(tree, traverse_func, NULL);
+            break;
+        case IMPL_QTREE:
+            q_tree_foreach(tree, traverse_func, NULL);
+            break;
+        default:
+            g_assert_not_reached();
+        }
+        break;
+    default:
+        g_assert_not_reached();
+    }
+    int64_t ns = get_clock() - start_ns;
+
+    if (bench->op != OP_REMOVE_ALL) {
+        remove_all(tree, impl);
+    }
+    g_free(keys);
+
+    return ns;
+}
+
+int main(int argc, char *argv[])
+{
+    size_t sizes[] = {
+        32,
+        1024,
+        1024 * 4,
+        1024 * 128,
+        1024 * 1024,
+    };
+
+    double res[ARRAY_SIZE(benchmarks)][ARRAY_SIZE(impls)][ARRAY_SIZE(sizes)];
+    for (int i = 0; i < ARRAY_SIZE(sizes); i++) {
+        size_t size = sizes[i];
+        for (int j = 0; j < ARRAY_SIZE(impls); j++) {
+            const struct tree_implementation *impl = &impls[j];
+            for (int k = 0; k < ARRAY_SIZE(benchmarks); k++) {
+                const struct benchmark *bench = &benchmarks[k];
+
+                /* warm-up run */
+                run_benchmark(bench, impl->type, size);
+
+                int64_t total_ns = 0;
+                int64_t n_runs = 0;
+                while (total_ns < 2e8 || n_runs < 5) {
+                    total_ns += run_benchmark(bench, impl->type, size);
+                    n_runs++;
+                }
+                double ns_per_run = (double)total_ns / n_runs;
+
+                /* Throughput, in Mops/s */
+                res[k][j][i] = size / ns_per_run * 1e3;
+            }
+        }
+    }
+
+    printf("# Results' breakdown: Tree, Op and #Elements. Units: Mops/s\n");
+    printf("%5s %10s ", "Tree", "Op");
+    for (int i = 0; i < ARRAY_SIZE(sizes); i++) {
+        printf("%7zu         ", sizes[i]);
+    }
+    printf("\n");
+    char separator[97];
+    for (int i = 0; i < ARRAY_SIZE(separator) - 1; i++) {
+        separator[i] = '-';
+    }
+    separator[ARRAY_SIZE(separator) - 1] = '\0';
+    printf("%s\n", separator);
+    for (int i = 0; i < ARRAY_SIZE(benchmarks); i++) {
+        for (int j = 0; j < ARRAY_SIZE(impls); j++) {
+            printf("%5s %10s ", impls[j].name, benchmarks[i].name);
+            for (int k = 0; k < ARRAY_SIZE(sizes); k++) {
+                printf("%7.2f ", res[i][j][k]);
+                if (j == 0) {
+                    printf("        ");
+                } else {
+                    if (res[i][0][k] != 0) {
+                        double speedup = res[i][j][k] / res[i][0][k];
+                        printf("(%4.2fx) ", speedup);
+                    } else {
+                        printf("(     ) ");
+                    }
+                }
+            }
+            printf("\n");
+        }
+    }
+    printf("%s\n", separator);
+    return 0;
+}
diff --git a/tests/unit/meson.build b/tests/unit/meson.build
index fa63cfe..3bc78d8 100644
--- a/tests/unit/meson.build
+++ b/tests/unit/meson.build
@@ -36,6 +36,7 @@ tests = {
   'test-rcu-slist': [],
   'test-qdist': [],
   'test-qht': [],
+  'test-qtree': [],
   'test-bitops': [],
   'test-bitcnt': [],
   'test-qgraph': ['../qtest/libqos/qgraph.c'],
diff --git a/tests/unit/test-qtree.c b/tests/unit/test-qtree.c
new file mode 100644
index 0000000..4d836d2
--- /dev/null
+++ b/tests/unit/test-qtree.c
@@ -0,0 +1,333 @@
+/*
+ * SPDX-License-Identifier: LGPL-2.1-or-later
+ *
+ * Tests for QTree.
+ * Original source: glib
+ *   https://gitlab.gnome.org/GNOME/glib/-/blob/main/glib/tests/tree.c
+ *   LGPL license.
+ *   Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/qtree.h"
+
+static gint my_compare(gconstpointer a, gconstpointer b)
+{
+    const char *cha = a;
+    const char *chb = b;
+
+    return *cha - *chb;
+}
+
+static gint my_compare_with_data(gconstpointer a,
+                                 gconstpointer b,
+                                 gpointer user_data)
+{
+    const char *cha = a;
+    const char *chb = b;
+
+    /* just check that we got the right data */
+    g_assert(GPOINTER_TO_INT(user_data) == 123);
+
+    return *cha - *chb;
+}
+
+static gint my_search(gconstpointer a, gconstpointer b)
+{
+    return my_compare(b, a);
+}
+
+static gpointer destroyed_key;
+static gpointer destroyed_value;
+static guint destroyed_key_count;
+static guint destroyed_value_count;
+
+static void my_key_destroy(gpointer key)
+{
+    destroyed_key = key;
+    destroyed_key_count++;
+}
+
+static void my_value_destroy(gpointer value)
+{
+    destroyed_value = value;
+    destroyed_value_count++;
+}
+
+static gint my_traverse(gpointer key, gpointer value, gpointer data)
+{
+    char *ch = key;
+
+    g_assert((*ch) > 0);
+
+    if (*ch == 'd') {
+        return TRUE;
+    }
+
+    return FALSE;
+}
+
+char chars[] =
+    "0123456789"
+    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+    "abcdefghijklmnopqrstuvwxyz";
+
+char chars2[] =
+    "0123456789"
+    "abcdefghijklmnopqrstuvwxyz";
+
+static gint check_order(gpointer key, gpointer value, gpointer data)
+{
+    char **p = data;
+    char *ch = key;
+
+    g_assert(**p == *ch);
+
+    (*p)++;
+
+    return FALSE;
+}
+
+static void test_tree_search(void)
+{
+    gint i;
+    QTree *tree;
+    gboolean removed;
+    gchar c;
+    gchar *p, *d;
+
+    tree = q_tree_new_with_data(my_compare_with_data, GINT_TO_POINTER(123));
+
+    for (i = 0; chars[i]; i++) {
+        q_tree_insert(tree, &chars[i], &chars[i]);
+    }
+
+    q_tree_foreach(tree, my_traverse, NULL);
+
+    g_assert(q_tree_nnodes(tree) == strlen(chars));
+    g_assert(q_tree_height(tree) == 6);
+
+    p = chars;
+    q_tree_foreach(tree, check_order, &p);
+
+    for (i = 0; i < 26; i++) {
+        removed = q_tree_remove(tree, &chars[i + 10]);
+        g_assert(removed);
+    }
+
+    c = '\0';
+    removed = q_tree_remove(tree, &c);
+    g_assert(!removed);
+
+    q_tree_foreach(tree, my_traverse, NULL);
+
+    g_assert(q_tree_nnodes(tree) == strlen(chars2));
+    g_assert(q_tree_height(tree) == 6);
+
+    p = chars2;
+    q_tree_foreach(tree, check_order, &p);
+
+    for (i = 25; i >= 0; i--) {
+        q_tree_insert(tree, &chars[i + 10], &chars[i + 10]);
+    }
+
+    p = chars;
+    q_tree_foreach(tree, check_order, &p);
+
+    c = '0';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p && *p == c);
+    g_assert(q_tree_lookup_extended(tree, &c, (gpointer *)&d, (gpointer *)&p));
+    g_assert(c == *d && c == *p);
+
+    c = 'A';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p && *p == c);
+
+    c = 'a';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p && *p == c);
+
+    c = 'z';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p && *p == c);
+
+    c = '!';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p == NULL);
+
+    c = '=';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p == NULL);
+
+    c = '|';
+    p = q_tree_lookup(tree, &c);
+    g_assert(p == NULL);
+
+    c = '0';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p && *p == c);
+
+    c = 'A';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p && *p == c);
+
+    c = 'a';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p && *p == c);
+
+    c = 'z';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p && *p == c);
+
+    c = '!';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p == NULL);
+
+    c = '=';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p == NULL);
+
+    c = '|';
+    p = q_tree_search(tree, my_search, &c);
+    g_assert(p == NULL);
+
+    q_tree_destroy(tree);
+}
+
+static void test_tree_remove(void)
+{
+    QTree *tree;
+    char c, d;
+    gint i;
+    gboolean removed;
+
+    tree = q_tree_new_full((GCompareDataFunc)my_compare, NULL,
+                           my_key_destroy,
+                           my_value_destroy);
+
+    for (i = 0; chars[i]; i++) {
+        q_tree_insert(tree, &chars[i], &chars[i]);
+    }
+
+    c = '0';
+    q_tree_insert(tree, &c, &c);
+    g_assert(destroyed_key == &c);
+    g_assert(destroyed_value == &chars[0]);
+    destroyed_key = NULL;
+    destroyed_value = NULL;
+
+    d = '1';
+    q_tree_replace(tree, &d, &d);
+    g_assert(destroyed_key == &chars[1]);
+    g_assert(destroyed_value == &chars[1]);
+    destroyed_key = NULL;
+    destroyed_value = NULL;
+
+    c = '2';
+    removed = q_tree_remove(tree, &c);
+    g_assert(removed);
+    g_assert(destroyed_key == &chars[2]);
+    g_assert(destroyed_value == &chars[2]);
+    destroyed_key = NULL;
+    destroyed_value = NULL;
+
+    c = '3';
+    removed = q_tree_steal(tree, &c);
+    g_assert(removed);
+    g_assert(destroyed_key == NULL);
+    g_assert(destroyed_value == NULL);
+
+    const gchar *remove = "omkjigfedba";
+    for (i = 0; remove[i]; i++) {
+        removed = q_tree_remove(tree, &remove[i]);
+        g_assert(removed);
+    }
+
+    q_tree_destroy(tree);
+}
+
+static void test_tree_destroy(void)
+{
+    QTree *tree;
+    gint i;
+
+    tree = q_tree_new(my_compare);
+
+    for (i = 0; chars[i]; i++) {
+        q_tree_insert(tree, &chars[i], &chars[i]);
+    }
+
+    g_assert(q_tree_nnodes(tree) == strlen(chars));
+
+    g_test_message("nnodes: %d", q_tree_nnodes(tree));
+    q_tree_ref(tree);
+    q_tree_destroy(tree);
+
+    g_test_message("nnodes: %d", q_tree_nnodes(tree));
+    g_assert(q_tree_nnodes(tree) == 0);
+
+    q_tree_unref(tree);
+}
+
+static void test_tree_insert(void)
+{
+    QTree *tree;
+    gchar *p;
+    gint i;
+    gchar *scrambled;
+
+    tree = q_tree_new(my_compare);
+
+    for (i = 0; chars[i]; i++) {
+        q_tree_insert(tree, &chars[i], &chars[i]);
+    }
+    p = chars;
+    q_tree_foreach(tree, check_order, &p);
+
+    q_tree_unref(tree);
+    tree = q_tree_new(my_compare);
+
+    for (i = strlen(chars) - 1; i >= 0; i--) {
+        q_tree_insert(tree, &chars[i], &chars[i]);
+    }
+    p = chars;
+    q_tree_foreach(tree, check_order, &p);
+
+    q_tree_unref(tree);
+    tree = q_tree_new(my_compare);
+
+    scrambled = g_strdup(chars);
+
+    for (i = 0; i < 30; i++) {
+        gchar tmp;
+        gint a, b;
+
+        a = g_random_int_range(0, strlen(scrambled));
+        b = g_random_int_range(0, strlen(scrambled));
+        tmp = scrambled[a];
+        scrambled[a] = scrambled[b];
+        scrambled[b] = tmp;
+    }
+
+    for (i = 0; scrambled[i]; i++) {
+        q_tree_insert(tree, &scrambled[i], &scrambled[i]);
+    }
+    p = chars;
+    q_tree_foreach(tree, check_order, &p);
+
+    g_free(scrambled);
+    q_tree_unref(tree);
+}
+
+int main(int argc, char *argv[])
+{
+    g_test_init(&argc, &argv, NULL);
+
+    g_test_add_func("/qtree/search", test_tree_search);
+    g_test_add_func("/qtree/remove", test_tree_remove);
+    g_test_add_func("/qtree/destroy", test_tree_destroy);
+    g_test_add_func("/qtree/insert", test_tree_insert);
+
+    return g_test_run();
+}