From nobody Fri Oct 24 20:04:05 2025 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 151971025600550.7896751202569; Mon, 26 Feb 2018 21:44:16 -0800 (PST) Received: from localhost ([::1]:34939 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eqY3f-00083L-Ri for importer@patchew.org; Tue, 27 Feb 2018 00:44:11 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50948) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eqXzG-0004ag-Cj for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:45 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eqXzC-0000Pg-AC for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:38 -0500 Received: from out2-smtp.messagingengine.com ([66.111.4.26]:51425) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eqXzC-0000Ns-0y for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:34 -0500 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 8A71920CD4; Tue, 27 Feb 2018 00:39:32 -0500 (EST) Received: from frontend1 ([10.202.2.160]) by compute4.internal (MEProxy); Tue, 27 Feb 2018 00:39:32 -0500 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 579B57E4AA; Tue, 27 Feb 2018 00:39:32 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :date:from:in-reply-to:message-id:references:subject:to :x-me-sender:x-me-sender:x-sasl-enc; s=mesmtp; bh=u9jontrmlPw5kO /5DDeqULtrIhT8Ybk6Mv65fNq1EkY=; b=LLktvmIfsIZIguM7ZyxXdV4utrm4Od 6kahTNochk7iitxEfCK1JYlPT4gX0CXTw3+VuO5fMxv9yoH3tBLP76cdv8rGPnho B8KaevRLTG8Rt0SuBS/zVjAq0ELtQZ+5VNb7CTBZFdJJjGuXHjrHqFtF2Wd88slk Ewyx6l3FLtOsA= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:date:from:in-reply-to:message-id :references:subject:to:x-me-sender:x-me-sender:x-sasl-enc; s= fm2; bh=u9jontrmlPw5kO/5DDeqULtrIhT8Ybk6Mv65fNq1EkY=; b=ly1s342n AeEwcP2B7DyQsmPo2IX+mL/sbO05Z3CAx4ecbYLgML8j2nqoo9kgcscXwHS7eDD9 ko9jY1ALmML/dIxIxeynf6IrEHGSkuiz+4GSUrzKNNdf8TJa2ZTJwc/+GJ43a9Vs +I5alJORHmKdp3FJ7eaV4nwFm3BrF6nN9rHvyz16kjBLEy4W2W+zzCQpHSwroGQE pIfLxpK1E+MJDzqjCTBCLZFSg7DtESCNx29I28fJGL32LlowaAM0Jb782W17ztsr BOHtKVcJrUtGn8r/3X/XfOC7SJ+ZrpFqCagC4Uee1XUAueybGnP/885X6Dc7Ojuk EkMYcnWoThKTsA== X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Tue, 27 Feb 2018 00:39:10 -0500 Message-Id: <1519709965-29833-2-git-send-email-cota@braap.org> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1519709965-29833-1-git-send-email-cota@braap.org> References: <1519709965-29833-1-git-send-email-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 66.111.4.26 Subject: [Qemu-devel] [PATCH 01/16] qht: require a default comparison function X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Paolo Bonzini , Richard Henderson Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail: RSF_0 Z_629925259 SPT_0 Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" qht_lookup now uses the default cmp function. qht_lookup_custom is defined to retain the old behaviour, that is a cmp function is explicitly provided. qht_insert will gain use of the default cmp in the next patch. Signed-off-by: Emilio G. Cota Reviewed-by: Alex Benn=C3=A9e Reviewed-by: Richard Henderson --- accel/tcg/cpu-exec.c | 4 ++-- accel/tcg/translate-all.c | 16 +++++++++++++++- include/qemu/qht.h | 23 +++++++++++++++++++---- tests/qht-bench.c | 14 +++++++------- tests/test-qht.c | 15 ++++++++++----- util/qht.c | 14 +++++++++++--- 6 files changed, 64 insertions(+), 22 deletions(-) diff --git a/accel/tcg/cpu-exec.c b/accel/tcg/cpu-exec.c index 280200f..ec57564 100644 --- a/accel/tcg/cpu-exec.c +++ b/accel/tcg/cpu-exec.c @@ -293,7 +293,7 @@ struct tb_desc { uint32_t trace_vcpu_dstate; }; =20 -static bool tb_cmp(const void *p, const void *d) +static bool tb_lookup_cmp(const void *p, const void *d) { const TranslationBlock *tb =3D p; const struct tb_desc *desc =3D d; @@ -338,7 +338,7 @@ TranslationBlock *tb_htable_lookup(CPUState *cpu, targe= t_ulong pc, phys_pc =3D get_page_addr_code(desc.env, pc); desc.phys_page1 =3D phys_pc & TARGET_PAGE_MASK; h =3D tb_hash_func(phys_pc, pc, flags, cf_mask, *cpu->trace_dstate); - return qht_lookup(&tb_ctx.htable, tb_cmp, &desc, h); + return qht_lookup_custom(&tb_ctx.htable, tb_lookup_cmp, &desc, h); } =20 void tb_set_jmp_target(TranslationBlock *tb, int n, uintptr_t addr) diff --git a/accel/tcg/translate-all.c b/accel/tcg/translate-all.c index 67795cd..1cf10f8 100644 --- a/accel/tcg/translate-all.c +++ b/accel/tcg/translate-all.c @@ -785,11 +785,25 @@ static inline void code_gen_alloc(size_t tb_size) qemu_mutex_init(&tb_ctx.tb_lock); } =20 +static bool tb_cmp(const void *ap, const void *bp) +{ + const TranslationBlock *a =3D ap; + const TranslationBlock *b =3D bp; + + return a->pc =3D=3D b->pc && + a->cs_base =3D=3D b->cs_base && + a->flags =3D=3D b->flags && + (tb_cflags(a) & CF_HASH_MASK) =3D=3D (tb_cflags(b) & CF_HASH_MASK)= && + a->trace_vcpu_dstate =3D=3D b->trace_vcpu_dstate && + a->page_addr[0] =3D=3D b->page_addr[0] && + a->page_addr[1] =3D=3D b->page_addr[1]; +} + static void tb_htable_init(void) { unsigned int mode =3D QHT_MODE_AUTO_RESIZE; =20 - qht_init(&tb_ctx.htable, CODE_GEN_HTABLE_SIZE, mode); + qht_init(&tb_ctx.htable, tb_cmp, CODE_GEN_HTABLE_SIZE, mode); } =20 /* Must be called before using the QEMU cpus. 'tb_size' is the size diff --git a/include/qemu/qht.h b/include/qemu/qht.h index 531aa95..dd512bf 100644 --- a/include/qemu/qht.h +++ b/include/qemu/qht.h @@ -11,8 +11,11 @@ #include "qemu/thread.h" #include "qemu/qdist.h" =20 +typedef bool (*qht_cmp_func_t)(const void *a, const void *b); + struct qht { struct qht_map *map; + qht_cmp_func_t cmp; QemuMutex lock; /* serializes setters of ht->map */ unsigned int mode; }; @@ -47,10 +50,12 @@ typedef void (*qht_iter_func_t)(struct qht *ht, void *p= , uint32_t h, void *up); /** * qht_init - Initialize a QHT * @ht: QHT to be initialized + * @cmp: default comparison function. Cannot be NULL. * @n_elems: number of entries the hash table should be optimized for. * @mode: bitmask with OR'ed QHT_MODE_* */ -void qht_init(struct qht *ht, size_t n_elems, unsigned int mode); +void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems, + unsigned int mode); =20 /** * qht_destroy - destroy a previously initialized QHT @@ -78,7 +83,7 @@ void qht_destroy(struct qht *ht); bool qht_insert(struct qht *ht, void *p, uint32_t hash); =20 /** - * qht_lookup - Look up a pointer in a QHT + * qht_lookup_custom - Look up a pointer using a custom comparison functio= n. * @ht: QHT to be looked up * @func: function to compare existing pointers against @userp * @userp: pointer to pass to @func @@ -94,8 +99,18 @@ bool qht_insert(struct qht *ht, void *p, uint32_t hash); * Returns the corresponding pointer when a match is found. * Returns NULL otherwise. */ -void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, - uint32_t hash); +void *qht_lookup_custom(struct qht *ht, qht_lookup_func_t func, + const void *userp, uint32_t hash); + +/** + * qht_lookup - Look up a pointer in a QHT + * @ht: QHT to be looked up + * @userp: pointer to pass to @func + * @hash: hash of the pointer to be looked up + * + * Calls qht_lookup_custom() using @ht's default comparison function. + */ +void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash); =20 /** * qht_remove - remove a pointer from the hash table diff --git a/tests/qht-bench.c b/tests/qht-bench.c index 4cabdfd..c94ac25 100644 --- a/tests/qht-bench.c +++ b/tests/qht-bench.c @@ -93,10 +93,10 @@ static void usage_complete(int argc, char *argv[]) exit(-1); } =20 -static bool is_equal(const void *obj, const void *userp) +static bool is_equal(const void *ap, const void *bp) { - const long *a =3D obj; - const long *b =3D userp; + const long *a =3D ap; + const long *b =3D bp; =20 return *a =3D=3D *b; } @@ -150,7 +150,7 @@ static void do_rw(struct thread_info *info) =20 p =3D &keys[info->r & (lookup_range - 1)]; hash =3D h(*p); - read =3D qht_lookup(&ht, is_equal, p, hash); + read =3D qht_lookup(&ht, p, hash); if (read) { stats->rd++; } else { @@ -162,7 +162,7 @@ static void do_rw(struct thread_info *info) if (info->write_op) { bool written =3D false; =20 - if (qht_lookup(&ht, is_equal, p, hash) =3D=3D NULL) { + if (qht_lookup(&ht, p, hash) =3D=3D NULL) { written =3D qht_insert(&ht, p, hash); } if (written) { @@ -173,7 +173,7 @@ static void do_rw(struct thread_info *info) } else { bool removed =3D false; =20 - if (qht_lookup(&ht, is_equal, p, hash)) { + if (qht_lookup(&ht, p, hash)) { removed =3D qht_remove(&ht, p, hash); } if (removed) { @@ -308,7 +308,7 @@ static void htable_init(void) } =20 /* initialize the hash table */ - qht_init(&ht, qht_n_elems, qht_mode); + qht_init(&ht, is_equal, qht_n_elems, qht_mode); assert(init_size <=3D init_range); =20 pr_params(); diff --git a/tests/test-qht.c b/tests/test-qht.c index 9b7423a..f8f2886 100644 --- a/tests/test-qht.c +++ b/tests/test-qht.c @@ -13,10 +13,10 @@ static struct qht ht; static int32_t arr[N * 2]; =20 -static bool is_equal(const void *obj, const void *userp) +static bool is_equal(const void *ap, const void *bp) { - const int32_t *a =3D obj; - const int32_t *b =3D userp; + const int32_t *a =3D ap; + const int32_t *b =3D bp; =20 return *a =3D=3D *b; } @@ -60,7 +60,12 @@ static void check(int a, int b, bool expected) =20 val =3D i; hash =3D i; - p =3D qht_lookup(&ht, is_equal, &val, hash); + /* test both lookup variants; results should be the same */ + if (i % 2) { + p =3D qht_lookup(&ht, &val, hash); + } else { + p =3D qht_lookup_custom(&ht, is_equal, &val, hash); + } g_assert_true(!!p =3D=3D expected); } rcu_read_unlock(); @@ -102,7 +107,7 @@ static void qht_do_test(unsigned int mode, size_t init_= entries) /* under KVM we might fetch stats from an uninitialized qht */ check_n(0); =20 - qht_init(&ht, 0, mode); + qht_init(&ht, is_equal, 0, mode); =20 check_n(0); insert(0, N); diff --git a/util/qht.c b/util/qht.c index ff4d2e6..dcb3ee1 100644 --- a/util/qht.c +++ b/util/qht.c @@ -351,11 +351,14 @@ static struct qht_map *qht_map_create(size_t n_bucket= s) return map; } =20 -void qht_init(struct qht *ht, size_t n_elems, unsigned int mode) +void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems, + unsigned int mode) { struct qht_map *map; size_t n_buckets =3D qht_elems_to_buckets(n_elems); =20 + g_assert(cmp); + ht->cmp =3D cmp; ht->mode =3D mode; qemu_mutex_init(&ht->lock); map =3D qht_map_create(n_buckets); @@ -479,8 +482,8 @@ void *qht_lookup__slowpath(struct qht_bucket *b, qht_lo= okup_func_t func, return ret; } =20 -void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, - uint32_t hash) +void *qht_lookup_custom(struct qht *ht, qht_lookup_func_t func, + const void *userp, uint32_t hash) { struct qht_bucket *b; struct qht_map *map; @@ -502,6 +505,11 @@ void *qht_lookup(struct qht *ht, qht_lookup_func_t fun= c, const void *userp, return qht_lookup__slowpath(b, func, userp, hash); } =20 +void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash) +{ + return qht_lookup_custom(ht, ht->cmp, userp, hash); +} + /* call with head->lock held */ static bool qht_insert__locked(struct qht *ht, struct qht_map *map, struct qht_bucket *head, void *p, uint32_t = hash, --=20 2.7.4