From nobody Fri Oct 24 20:22:35 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 1519710281557912.2810978874288; Mon, 26 Feb 2018 21:44:41 -0800 (PST) Received: from localhost ([::1]:34940 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eqY48-0008U6-AQ for importer@patchew.org; Tue, 27 Feb 2018 00:44:40 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50935) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eqXzG-0004aY-9a for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:40 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eqXzC-0000Po-De for qemu-devel@nongnu.org; Tue, 27 Feb 2018 00:39:38 -0500 Received: from out2-smtp.messagingengine.com ([66.111.4.26]:41993) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1eqXzC-0000Ob-A2 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 D319420C4A; Tue, 27 Feb 2018 00:39:32 -0500 (EST) Received: from frontend2 ([10.202.2.161]) 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 8845E24575; 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=VxF+4rCA5Ocnpo PSXahnIWA6AAMz8Vid6Ij5sGaqKoY=; b=UFnVrc68pJM9gJ85PhLBCQR1tW1duV ySzK2uvgg9Wy+nYsstMWJ6xy6rLCCYsNG3+9tOKq4VafRExOMtg82aqUpmDHPFZJ eiuDUuOhrq/C886gTramFWcV9rxkY96b1/z5WWh1DK+2+2zD3Hv+MJ1S/Tp+ECyH X6JDj6fF8Iz+0= 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=VxF+4rCA5OcnpoPSXahnIWA6AAMz8Vid6Ij5sGaqKoY=; b=iqr3ZDaL 0Els7ejUg5WLjq33b62dcC21P8ChZue4ICUlgtv6lnklxlsatgCaspVoy54EAlPF GZZg8ULAwjb9/pmhnmcPcFfFSX3jwNj/Of6fa+Pli5C1UCRed5mBbcheFE5c9cY6 hWCqK2eFAP2pDXmDdEKMK2/7JexCjX6rxmZwDwBZjlZlkDdjf3nDDyoNBsEuENJX pcZ2texn513fUJbLkJlFGxA7FxRsXJbF0f7M+dGZ0qQLLxSW0Dd7Is8M5dN1zdmX ibufBVhkWtzXiUTvyt8EE7eEkajrdpinE7Y3+ynO3iUD0+5TF8tu7J4YmlxwGLMW HNnZLRGnu8bcUg== X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Tue, 27 Feb 2018 00:39:11 -0500 Message-Id: <1519709965-29833-3-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 02/16] qht: return existing entry when qht_insert fails 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" The meaning of "existing" is now changed to "matches in hash and ht->cmp result". This is saner than just checking the pointer value. Note that we now return NULL on insertion success, or the existing pointer on failure. We can do this because NULL pointers are not allowed to be inserted in QHT. Suggested-by: Richard Henderson Signed-off-by: Emilio G. Cota Reviewed-by: Richard Henderson --- include/qemu/qht.h | 7 ++++--- tests/qht-bench.c | 4 ++-- tests/test-qht.c | 5 ++++- util/qht.c | 17 +++++++++-------- 4 files changed, 19 insertions(+), 14 deletions(-) diff --git a/include/qemu/qht.h b/include/qemu/qht.h index dd512bf..c320cb6 100644 --- a/include/qemu/qht.h +++ b/include/qemu/qht.h @@ -77,10 +77,11 @@ void qht_destroy(struct qht *ht); * In case of successful operation, smp_wmb() is implied before the pointe= r is * inserted into the hash table. * - * Returns true on success. - * Returns false if the @p-@hash pair already exists in the hash table. + * On success, returns NULL. + * On failure, returns the pointer from an entry that is equivalent (i.e. + * ht->cmp matches and the hash is the same) to @p-@h. */ -bool qht_insert(struct qht *ht, void *p, uint32_t hash); +void *qht_insert(struct qht *ht, void *p, uint32_t hash); =20 /** * qht_lookup_custom - Look up a pointer using a custom comparison functio= n. diff --git a/tests/qht-bench.c b/tests/qht-bench.c index c94ac25..2f88400 100644 --- a/tests/qht-bench.c +++ b/tests/qht-bench.c @@ -163,7 +163,7 @@ static void do_rw(struct thread_info *info) bool written =3D false; =20 if (qht_lookup(&ht, p, hash) =3D=3D NULL) { - written =3D qht_insert(&ht, p, hash); + written =3D !qht_insert(&ht, p, hash); } if (written) { stats->in++; @@ -322,7 +322,7 @@ static void htable_init(void) r =3D xorshift64star(r); p =3D &keys[r & (init_range - 1)]; hash =3D h(*p); - if (qht_insert(&ht, p, hash)) { + if (qht_insert(&ht, p, hash) =3D=3D NULL) { break; } retries++; diff --git a/tests/test-qht.c b/tests/test-qht.c index f8f2886..7164ae4 100644 --- a/tests/test-qht.c +++ b/tests/test-qht.c @@ -27,11 +27,14 @@ static void insert(int a, int b) =20 for (i =3D a; i < b; i++) { uint32_t hash; + void *existing; =20 arr[i] =3D i; hash =3D i; =20 - qht_insert(&ht, &arr[i], hash); + g_assert_true(!qht_insert(&ht, &arr[i], hash)); + existing =3D qht_insert(&ht, &arr[i], hash); + g_assert_true(existing =3D=3D &arr[i]); } } =20 diff --git a/util/qht.c b/util/qht.c index dcb3ee1..f9f49a9 100644 --- a/util/qht.c +++ b/util/qht.c @@ -511,9 +511,9 @@ void *qht_lookup(struct qht *ht, const void *userp, uin= t32_t hash) } =20 /* 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, - bool *needs_resize) +static void *qht_insert__locked(struct qht *ht, struct qht_map *map, + struct qht_bucket *head, void *p, uint32_t= hash, + bool *needs_resize) { struct qht_bucket *b =3D head; struct qht_bucket *prev =3D NULL; @@ -523,8 +523,9 @@ static bool qht_insert__locked(struct qht *ht, struct q= ht_map *map, do { for (i =3D 0; i < QHT_BUCKET_ENTRIES; i++) { if (b->pointers[i]) { - if (unlikely(b->pointers[i] =3D=3D p)) { - return false; + if (unlikely(b->hashes[i] =3D=3D hash && + ht->cmp(b->pointers[i], p))) { + return b->pointers[i]; } } else { goto found; @@ -553,7 +554,7 @@ static bool qht_insert__locked(struct qht *ht, struct q= ht_map *map, atomic_set(&b->hashes[i], hash); atomic_set(&b->pointers[i], p); seqlock_write_end(&head->sequence); - return true; + return NULL; } =20 static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht) @@ -577,12 +578,12 @@ static __attribute__((noinline)) void qht_grow_maybe(= struct qht *ht) qemu_mutex_unlock(&ht->lock); } =20 -bool qht_insert(struct qht *ht, void *p, uint32_t hash) +void *qht_insert(struct qht *ht, void *p, uint32_t hash) { struct qht_bucket *b; struct qht_map *map; bool needs_resize =3D false; - bool ret; + void *ret; =20 /* NULL pointers are not supported */ qht_debug_assert(p); --=20 2.7.4