From nobody Wed Nov 5 11:06:32 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 1534549563231598.2612918228444; Fri, 17 Aug 2018 16:46:03 -0700 (PDT) Received: from localhost ([::1]:36802 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoRO-0006QE-20 for importer@patchew.org; Fri, 17 Aug 2018 19:46:02 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57566) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoPE-0004q3-DN for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:43:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fqoBj-0003HP-M8 for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:55 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:57943) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fqoBj-0003Gv-EL for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:51 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id EDF28225FA; Fri, 17 Aug 2018 19:29:50 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Fri, 17 Aug 2018 19:29:50 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 82B591025D; Fri, 17 Aug 2018 19:29:50 -0400 (EDT) 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=jiGCv1p+hKqW1f Fp947jDJrT3lXSi7gGUkBKgprs4ZY=; b=1Ren50ADTz3OMh3Ru3cSR+0js2SM2Q iSSHO6MXMAvd/Ps5S4iTfb7GgMJBEzHhg20SnHx3DjvP2mHLCbAalQwHwR7QUzo4 Hd8hl8Qla6f66elNlSAxMBIOsTfC+54IKu//eOVDGkVGDnkD2zjQ373AT21vzeXA uy1bhpNffMm6k= 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= fm3; bh=jiGCv1p+hKqW1fFp947jDJrT3lXSi7gGUkBKgprs4ZY=; b=EWlXB2GV xew7j5Q/to6+Shm7q3ehPUvLsLje4jesz5y18lvPw0nTsd+PM6B3+rVcHyCjXAdA YmhZ/7NPZBuqAL8+firM94y1qOHmQAbs5esJwegrbBUTIJRSRsL+dS8kdAxyH9j+ dnT7cqgUQamBasYzaV3r1G2xy/EofPet9SZwgNtVrb8SpOZQvNBrh+Kv0Dn+oE4w 8BP5a2AGTfCEW5jpTs5XW60oRJn92rj6+7ayh/srQeNq/Kg78JWUuEEXVeIKsQ43 KNK88HKfr7prLYZy1yldYZ+6JbKkMnzQ6exhjicvQYP/oTLW4zyQxDJqrF+3cj6s dv+2j8tKeMdJdw== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Fri, 17 Aug 2018 19:29:18 -0400 Message-Id: <20180817232923.28899-2-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180817232923.28899-1-cota@braap.org> References: <20180817232923.28899-1-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.25 Subject: [Qemu-devel] [PATCH 1/6] qht: remove unused map param from qht_remove__locked 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: =?UTF-8?q?Alex=20Benn=C3=A9e?= , 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" Signed-off-by: Emilio G. Cota Reviewed-by: Alex Benn=C3=A9e --- 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_b= ucket *orig, int pos) =20 /* 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 h= ash) { struct qht_bucket *b =3D head; int i; @@ -701,7 +700,7 @@ bool qht_remove(struct qht *ht, const void *p, uint32_t= hash) qht_debug_assert(p); =20 b =3D qht_bucket_lock__no_stale(ht, hash, &map); - ret =3D qht_remove__locked(map, b, p, hash); + ret =3D qht_remove__locked(b, p, hash); qht_bucket_debug__locked(b); qemu_spin_unlock(&b->lock); return ret; --=20 2.17.1 From nobody Wed Nov 5 11:06:32 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 (208.118.235.17 [208.118.235.17]) by mx.zohomail.com with SMTPS id 1534549880093795.7903302704726; Fri, 17 Aug 2018 16:51:20 -0700 (PDT) Received: from localhost ([::1]:36826 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoWM-0002TQ-NR for importer@patchew.org; Fri, 17 Aug 2018 19:51:10 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57651) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoPE-0004rh-CY for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:43:49 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fqoBj-0003HZ-Mw for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:55 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:54451) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fqoBj-0003H0-EL for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:51 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 2CF33225FD; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Fri, 17 Aug 2018 19:29:51 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id B394F10268; Fri, 17 Aug 2018 19:29:50 -0400 (EDT) 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=dCttIWviY0ltYU 4qNLPRQWx4E7MutHfhHu5aCeHyf50=; b=LzaWi472lkQ35jE+qzL7bBOtztYV// Cibl4XOK/JQhep87ZtDuTPX2lSwDecESJlhT1YWMT+6fYEyqaOUWtnMaKyUz62N9 FWJHCKqP+uEHadGzJXBJ2M7tZD3ta3GMFen9nf0Lrvgl7E81Uvw2lAjVIhjcyuUv wiwVOkPXvtQzg= 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= fm3; bh=dCttIWviY0ltYU4qNLPRQWx4E7MutHfhHu5aCeHyf50=; b=XK/J+QCw pvoegBiLFVy5hE9RLZiO7VYijIiuRRf+Bc2cIEPertLzlUMopJcE81gqsBzdPpgu +gSoS4YRPfxRLHr84r+Wey6p/TpXCOZMbwCbSkxDu/76Y+QGy6kUmoVO1f6mNF90 KDZnPT7knLXktrq9Bh/rQY39XZL/0TuFSVFEhI3JOMjccLKrEMD3ziDlOvHKrkRa eA8RYIsagoPJVHhx58dVQjTG41jktmU6n+H0L6JjDPbiS2GVY6FC9/ReXR+nKiNj 8oAzuISis0wAi0sUX76XoTfYdfYXUu6glMgxSKeDWoiYUYAxapvTEk0xEWPWtcl4 tBYIIra4ex+XBw== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Fri, 17 Aug 2018 19:29:19 -0400 Message-Id: <20180817232923.28899-3-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180817232923.28899-1-cota@braap.org> References: <20180817232923.28899-1-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.25 Subject: [Qemu-devel] [PATCH 2/6] qht: add qht_iter_remove 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: =?UTF-8?q?Alex=20Benn=C3=A9e?= , 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" 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 Reviewed-by: Alex Benn=C3=A9e --- 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 { =20 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); =20 #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ =20 @@ -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 pa= ir, * 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); =20 +/** + * 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 pa= ir, + * 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 *user= p); + /** * 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 =20 +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; } =20 -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 *user= p) { + struct qht_bucket *b =3D head; int i; =20 do { @@ -716,7 +730,25 @@ static inline void qht_bucket_iter(struct qht *ht, str= uct qht_bucket *b, if (b->pointers[i] =3D=3D 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], user= p)) { + /* 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 =3D b->next; } while (b); @@ -724,26 +756,48 @@ static inline void qht_bucket_iter(struct qht *ht, st= ruct qht_bucket *b, =20 /* 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 *us= erp) + const struct qht_iter *iter, + void *userp) { size_t i; =20 for (i =3D 0; i < map->n_buckets; i++) { - qht_bucket_iter(ht, &map->buckets[i], func, userp); + qht_bucket_iter(ht, &map->buckets[i], iter, userp); } } =20 -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; =20 map =3D atomic_rcu_read(&ht->map); qht_map_lock_buckets(map); /* Note: ht here is merely for carrying ht->mode; ht->map won't be rea= d */ - qht_map_iter__all_locked(ht, map, func, userp); + qht_map_iter__all_locked(ht, map, iter, userp); qht_map_unlock_buckets(map); } =20 +void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp) +{ + const struct qht_iter iter =3D { + .f.retvoid =3D func, + .type =3D QHT_ITER_VOID, + }; + + do_qht_iter(ht, &iter, userp); +} + +void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *user= p) +{ + const struct qht_iter iter =3D { + .f.retbool =3D func, + .type =3D QHT_ITER_RM, + }; + + do_qht_iter(ht, &iter, userp); +} + static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *use= rp) { struct qht_map *new =3D userp; @@ -760,6 +814,10 @@ static void qht_map_copy(struct qht *ht, void *p, uint= 32_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 =3D { + .f.retvoid =3D qht_map_copy, + .type =3D QHT_ITER_VOID, + }; =20 old =3D 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) } =20 g_assert(new->n_buckets !=3D 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); =20 atomic_rcu_set(&ht->map, new); --=20 2.17.1 From nobody Wed Nov 5 11:06:32 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 153454956180639.33594652917975; Fri, 17 Aug 2018 16:46:01 -0700 (PDT) Received: from localhost ([::1]:36801 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoRI-0006PT-Rv for importer@patchew.org; Fri, 17 Aug 2018 19:45:56 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57745) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoPE-0004vU-Gy for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:43:49 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fqoBj-0003Hh-Ow for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:55 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:45909) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fqoBj-0003H6-Hl for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:51 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 58B37225A9; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Fri, 17 Aug 2018 19:29:51 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id E309B10273; Fri, 17 Aug 2018 19:29:50 -0400 (EDT) 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=iVB3otnAoUMS5A XKH1XbRmjf7QkdZZPUT+7het1x1Yo=; b=K1u7R8tdR6Vi7cMxXLm+Fw4LiEN61z AFwTruftvewZbLFheoYgQyOM6Vex0yNJitXckqoKHOFfwuSYEU+4QKLofqSDrscA xLIrGBXvyUqqvr17mzSxgwMX7P4lfarNY2IBw0Cz+EN5jBIzrHO5gFSMoMvMN5zL HsZbYitj/LiHs= 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= fm3; bh=iVB3otnAoUMS5AXKH1XbRmjf7QkdZZPUT+7het1x1Yo=; b=ieO0Y4WM DGeTcdNhKwFc5lB+9sHXqRL07biXKOwnfZaYGs8ygt0Ny3iGregmM/3yJiak1AlC K5JRjMTru/4e46sly3YFjHQjMF8oDcTOAbZMr3FXB3P7HNHuMpR6FmkcmGmVjX/b uwm1bV2AAI5/xSJfeMlETN46MoFBJ8Uebn88Lq1Q7bUMymZ6SMM52tTOnoOUoOod yAaViaHcXECF9r4Q2c43aedeWz1/8ywKR6CeejKJfzF2yjpjA/jllncu5EfEGf04 08gjrydu2od6oAtAIRqf20uF9Xd05jXzZjMoGqL46DsDkaF0CHPFjDXtYIbjlw6D HSmfslNEnXGBQQ== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Fri, 17 Aug 2018 19:29:20 -0400 Message-Id: <20180817232923.28899-4-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180817232923.28899-1-cota@braap.org> References: <20180817232923.28899-1-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.25 Subject: [Qemu-devel] [PATCH 3/6] test-qht: test qht_iter_remove 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: =?UTF-8?q?Alex=20Benn=C3=A9e?= , 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" Signed-off-by: Emilio G. Cota Reviewed-by: Alex Benn=C3=A9e --- 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, =3D=3D, count); } =20 +static void sum_func(struct qht *ht, void *p, uint32_t hash, void *userp) +{ + uint32_t *sum =3D userp; + uint32_t a =3D *(uint32_t *)p; + + *sum +=3D a; +} + +static void iter_sum_check(unsigned int expected) +{ + unsigned int sum =3D 0; + + qht_iter(&ht, sum_func, &sum); + g_assert_cmpuint(sum, =3D=3D, expected); +} + +static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *user= p) +{ + uint32_t a =3D *(uint32_t *)p; + unsigned int mod =3D *(unsigned int *)userp; + + return a % mod =3D=3D 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 =3D 0; + unsigned int i; + + for (i =3D 0; i < N; i++) { + if (i % mod =3D=3D 0) { + continue; + } + expected +=3D 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); =20 - 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); --=20 2.17.1 From nobody Wed Nov 5 11:06:32 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 153454956178165.1434797900846; Fri, 17 Aug 2018 16:46:01 -0700 (PDT) Received: from localhost ([::1]:36800 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoRI-0006Om-Dn for importer@patchew.org; Fri, 17 Aug 2018 19:45:56 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57566) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoPA-0004q3-MR for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:43:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fqoBj-0003Hp-S4 for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:55 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:58609) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fqoBj-0003HE-N5 for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:51 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 7AFB7225DD; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Fri, 17 Aug 2018 19:29:51 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 1DACE10255; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) 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=hWH4N6sQn7wQPw RgEdSUU8g4ZKdWu0GCeB38wDM+m4Q=; b=VyB+hpWrTDsGr/9UQIiZ/KDdaRa7lL FgOFii7IfBLkOicQJhb+ccEMsVBdm0x3SSUFXIW5jKPoy6UBUTXQ59sufHf6meDR zLjz4WMFkorx2+nImAlAk7tWobhEe16NNdhbU/jRzV8bdp63gurNpS+ESW+ISa7S N0cM7eczYFPmw= 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= fm3; bh=hWH4N6sQn7wQPwRgEdSUU8g4ZKdWu0GCeB38wDM+m4Q=; b=ExbqLnnJ oR+mM3XsbYcih6+dnzFKfrRDqSwZ/gQRbWAsCqNJMcKz1AZTmz0FBk0k/zpjBuUh uvnPcQEsiQI8GpHkcdNs0npTW3Uu6wuFfofq0aewhOJnBA5aaf8eyDAvxfVuNw+z LGZqdLsqBmA+/AT0fh+/CrAN5XLySmRMa6cUvbK475tFSAqMZXD3i7gCaSKFEsPM 9zJk+tNLIPitKIu3y0MK/ZbusQ1gayWnk6Up7HM+eSxmL6P3aaTGvgOUBX9XVS4X JMUv6wvTuFWW9pyKBY+Yft4Ed+yOxqJF7ta4L6PylOhJoObNwOU4bxcjw2V+CHor o+FUL8bR6NMazQ== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Fri, 17 Aug 2018 19:29:21 -0400 Message-Id: <20180817232923.28899-5-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180817232923.28899-1-cota@braap.org> References: <20180817232923.28899-1-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.25 Subject: [Qemu-devel] [PATCH 4/6] test-qht: test removal of non-existent entries 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: =?UTF-8?q?Alex=20Benn=C3=A9e?= , 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" This improves qht.c code coverage from 89.44% to 90.00%. Signed-off-by: Emilio G. Cota Reviewed-by: Alex Benn=C3=A9e --- 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) } } =20 -static void rm(int init, int end) +static void do_rm(int init, int end, bool exist) { int i; =20 @@ -49,10 +49,24 @@ static void rm(int init, int end) uint32_t hash; =20 hash =3D 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)); + } } } =20 +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); =20 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); =20 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) =20 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); --=20 2.17.1 From nobody Wed Nov 5 11:06:32 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 1534549752946998.9050483317104; Fri, 17 Aug 2018 16:49:12 -0700 (PDT) Received: from localhost ([::1]:36812 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoUR-0000Ro-Qg for importer@patchew.org; Fri, 17 Aug 2018 19:49:11 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57566) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoPF-0004q3-3J for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:43:49 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fqoBk-0003Hz-2p for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:55 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:51333) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fqoBj-0003Hl-UV for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:52 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id AC16B225DE; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Fri, 17 Aug 2018 19:29:51 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 4E0E01025D; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) 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=N1Y9nCHy99iNrD ZfH5M2c9aYYWk4nnU7rMyul2XBbvg=; b=UJV4Ebsl3pxOBYjZtaqyZxM6cEEmNC NWj+WbLFguZs9UmeCwfwhktKqy7FSf/h0i5ldvw/DoNkAem/FhKYvP31UyKZ6e9z VqRKyZpIFgc0MQIZlS1lXkcGgslvswks9mXqNp2FZWJQjYxQX/OBrTaDSH9XKr8a OSh80L6Z6JOOA= 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= fm3; bh=N1Y9nCHy99iNrDZfH5M2c9aYYWk4nnU7rMyul2XBbvg=; b=rUCVmFTD 2kWOZQlFzxkmG1J3VHOO4qWptSUTrew8ouDjnjIs1Vxcz7HYsePWnSN31/sdKCzC 7H9igkTf30G+uRESGG0p4V4JE7zYPuulWrivWG8jYXg8lOmUmscl+SPtDrsbEJeZ 1xpS25fhpopvX6vZlg9Uvq3/gw8ZLn+fzQl2SlLkZ7w6xj8/ZBGupGbGvWT790yf o17Q5LsvCIHvT/Suj080VMmlslO4gwa18E+dVsNsLG5+EKMKhmMzDRBONZDRisWx ukTrWbIbkxi4P04Wx81LQ0j5iLSC+6M+MSSumsTMk67W+m7mDE558jvZx5je7OP5 q1X4Aytes2UOkA== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Fri, 17 Aug 2018 19:29:22 -0400 Message-Id: <20180817232923.28899-6-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180817232923.28899-1-cota@braap.org> References: <20180817232923.28899-1-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.25 Subject: [Qemu-devel] [PATCH 5/6] test-qht: test deletion of the last entry in a bucket 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: =?UTF-8?q?Alex=20Benn=C3=A9e?= , 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" 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 Reviewed-by: Alex Benn=C3=A9e --- 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) =20 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 <=3D 1. + * Given that the number of elements per bucket can be 4 or 6 dependin= g on + * the host's pointer size, test the removal of the 4th and 6th elemen= ts. + */ 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); =20 --=20 2.17.1 From nobody Wed Nov 5 11:06:32 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 1534549752534536.2361904855577; Fri, 17 Aug 2018 16:49:12 -0700 (PDT) Received: from localhost ([::1]:36811 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoUR-0000RO-96 for importer@patchew.org; Fri, 17 Aug 2018 19:49:11 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:57651) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fqoPA-0004rh-Js for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:43:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fqoBk-0003I6-7C for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:55 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:36437) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fqoBk-0003Ht-1i for qemu-devel@nongnu.org; Fri, 17 Aug 2018 19:29:52 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id CFE41225FB; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Fri, 17 Aug 2018 19:29:51 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 8022510268; Fri, 17 Aug 2018 19:29:51 -0400 (EDT) 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=BQcF4PFVHCj9gA rphkYuadyNhi7MG9O2sAt3oKKn92w=; b=dyUUdgEe0SWpQWmiuzhlHYcJtWRivs CgZDLuYVu2KOzwyL2H8Mem2xCtp+hte8gUHd3FWpBDhW2V1al0hYqhjyxArfz/SA y+aIYImbDK8umbb1TMh7XxQHFdLqWb5DtZzKT3NwGFRObnoEZPIhDLpiGYPU3BTr uNFfnykRfpg44= 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= fm3; bh=BQcF4PFVHCj9gArphkYuadyNhi7MG9O2sAt3oKKn92w=; b=RSQ10zhl RXJCb9iJl24ws1A5y/GA25qS/9PkxyGb08O1WVKupm0FIRw7oaVv1OdArwlbpyXQ s8vXhXFjZgVY0kXQ40LwQimzK4EzGzMYP74Vy+YtZcH/bLIyRhho6p7D6sDJSkdj VHrT08oufAE/FvjvaZQ+Y++IzA1OonK3klI9RN2F4r+NZaeKd4QTRSoQTe+W3cw4 5B2ipBXPbItUwMEM71cmrMN8nCWYbZnkdOFKU3X8cd9uws7eUtZJagSf/dhIaAxl 16j4A8fZSbKXpNWcpotb96dv6iRid4CAychK48TriqEkLKTUyu/dCFbZd7lSpxqP 4aAdDru1rQdN/g== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Fri, 17 Aug 2018 19:29:23 -0400 Message-Id: <20180817232923.28899-7-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180817232923.28899-1-cota@braap.org> References: <20180817232923.28899-1-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.25 Subject: [Qemu-devel] [PATCH 6/6] test-qht: speed up + test qht_resize 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: =?UTF-8?q?Alex=20Benn=C3=A9e?= , 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" 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 Reviewed-by: Alex Benn=C3=A9e --- 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); =20 + if (!(mode & QHT_MODE_AUTO_RESIZE)) { + qht_resize(&ht, init_entries * 4 + 4); + } + check_n(0); rm_nonexist(0, 10); insert(0, N); --=20 2.17.1