From nobody Wed Nov 5 11:00:04 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 1536606118335698.7613756901725; Mon, 10 Sep 2018 12:01:58 -0700 (PDT) Received: from localhost ([::1]:53540 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRRZ-0002Wx-1e for importer@patchew.org; Mon, 10 Sep 2018 15:01:53 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49101) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPP-0001H1-Rx for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:40 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPO-0001Cp-Go for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:55623) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPO-0000zJ-4X for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:38 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 6895A21F35; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:07 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 69B3B10299; Mon, 10 Sep 2018 14:59:06 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=2ZHVnEZQCpeesOZ9Fvpnv1WOu1 I2d2tRgqtZXLOhqRU=; b=BdU0GHy+w4VyEKxB+/QaBN8G1aR4MGCLIw5eoBaEpF d4kT0EFYAjI3/99H2NN6HmF2EzPZ0KyUZmJwndi6Qa3oZF9aRTB8go/ODy1ZRr3R qYQw3FjaRw4FCVKhmDuqgr++Go4hJY7+Z3nQHSi4BxuXDPaKJ7TtWpk5BRrkg489 0= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=2ZHVnE ZQCpeesOZ9Fvpnv1WOu1I2d2tRgqtZXLOhqRU=; b=Huijy5isrREwzDAX/Kdxgj bTJ8yb/PmzHpbVyi7QLVJOfIJPkiuFNzAVg9Y+yZl2nAzoEDZfBksfEDgK+KbTko 4PHgNJ/w0peTu/Ij25R6p5U8S3KRE29cTUdZfafRkeuKlPGq2KWyyRW6tBsDQPSv 6qXcqNfv1j2v5FTSO29qt64FyhzzqazJL0s8ZRiKd/BMlcbtyUHyjSNVifpfHhgU R0RoDDNZbmO4buBXYig0neVgI3m5A83D+cHwJhvL2OLpAEw6i6hcUXe4X2bfelva 1j3aBWqVa4CWqXxCjUTQp5KkNcreOAVeYdxrdp5f1FxLhbstLYjyA6VBEWhD+/GQ == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:48 -0400 Message-Id: <20180910185859.27917-2-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 01/12] 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 Reviewed-by: Alex Benn=C3=A9e Signed-off-by: Emilio G. Cota --- 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_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; @@ -728,7 +727,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:00:04 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 1536606111263142.8061908278578; Mon, 10 Sep 2018 12:01:51 -0700 (PDT) Received: from localhost ([::1]:53537 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRRQ-0002Rz-31 for importer@patchew.org; Mon, 10 Sep 2018 15:01:44 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49045) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPM-0001Fl-3R for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:38 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRP6-00013B-UN for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:30 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:51791) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzROy-0000zG-Lv for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:15 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 6740221F2F; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:07 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 932D51029E; Mon, 10 Sep 2018 14:59:06 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=e0xACtdS3cGDyWNTzlZVbe34ws ffCOG/e3O2CU5Rxsw=; b=OokuY+odkLXu1MDAQvvRrsww1wJRtx3Tx06ucmrICE hmsMPSE7XAV9bWWOofbEuF+pstlHONU+umqsHKFOr9a9cJXeHCYCrGJZPNmw83vG F6sJOq7iHmOapgudo/TtpvRJtuJd/vSwhgDCWmjjblm48kNv+FsWyb7F2rUspvw6 M= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=e0xACt dS3cGDyWNTzlZVbe34wsffCOG/e3O2CU5Rxsw=; b=WPZY/eNWlWPGNTie5Rtz1j VBXsAZZ5IL8cNFJqdq2ILIZ9A2Eykz6bGvLWAvoIROl+AkXmC6woRYqZvZCxVs3n 5h4rqPdARbmVT9kGKnCQvWfpR8gwrqtxp9rUfjKc175yyfImQi0zETKyBZqVZ6xc KF8eKKfxwESMNcNHtvZU4EEXuH6sZP9ThAGx4fKb9ryvM2Kkq0bO9P/zF7qZy5m2 HCUOKo62ivcTrV3BypxG8dBnPjmiv4Ne1YUfgulrSvhkIVtQGvZycym9LRj4m1ox r+19PbhXlMb/oLLHs8a11e0AsNiNiG/vjzQTfJKidH/t42vppRrlta/yPVn6QZeg == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:49 -0400 Message-Id: <20180910185859.27917-3-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 02/12] 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 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=C3=A9e Signed-off-by: Emilio G. Cota --- 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 { =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 */ #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 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 28d9273371..c190e89f5b 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; +}; + /* * 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; } =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 { @@ -743,7 +757,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); @@ -751,26 +783,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; @@ -787,6 +841,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); @@ -801,7 +859,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:00:04 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 15366061335671009.1870619074775; Mon, 10 Sep 2018 12:02:13 -0700 (PDT) Received: from localhost ([::1]:53541 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRRh-0002cd-FT for importer@patchew.org; Mon, 10 Sep 2018 15:02:01 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49207) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPS-0001JO-IT for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:46 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPP-0001Dz-Kg for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:42 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:51329) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPP-0000zK-93 for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 648AE21F2E; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:07 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id C5502102A1; Mon, 10 Sep 2018 14:59:06 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=yRwg9YcszVBM4yNeMgy8ySbTYq F5e2vF1rKtNXRnXuQ=; b=nY9Utf4QJh0j8KXQLxdDBvvjP9fc1OgAlXMNKByuHo 5pkTloMg2gs6bxAjx3/bON0deQfygczk9EB1frZI5fmtrwYH7mnq97fg4wjP/dCz dxgPYP3/xIGnFrZrg+IrDsbOKkg8qi/YwAqlJKSxNiSC9f6C61sp+FAldl8U0wU9 k= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=yRwg9Y cszVBM4yNeMgy8ySbTYqF5e2vF1rKtNXRnXuQ=; b=koDH4sP6phMXxV5h6I3bKM 4hVn90WMHJQLv3I/LI2UQoA9iwjPQa4MymliXji9xr8C/x9nQUf3UquCWcwf7C/B RV5ZYWoqlgXkJdyuMFdTXza0rm+PoixsLyWcXh6gL8P+o5+fHhL3/vM7UxT7mkOu VCIkvq2m7ydWxA9JfbaDCMZrO42otj9tCLbExW/wJWbwt4Xiln9tA7OCw5LJcujp QMqUbhbsQ6edERqJ87mr0MGMzx06r1We5vMpnr3mCJtBpztrT+pihRhKZ+Er/ePT OUHu31DJDNiJWgwAldO2/mPab0u2+kdT0QtLEBNPQ4G34Ku3/QeuRvXJss8MOoBQ == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:50 -0400 Message-Id: <20180910185859.27917-4-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 03/12] 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 Reviewed-by: Alex Benn=C3=A9e Signed-off-by: Emilio G. Cota --- 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:00:04 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 1536606471998807.2255042221628; Mon, 10 Sep 2018 12:07:51 -0700 (PDT) Received: from localhost ([::1]:53569 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRXL-0007ZY-0d for importer@patchew.org; Mon, 10 Sep 2018 15:07:51 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49140) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPQ-0001Hq-SB for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:42 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPP-0001Dd-BF for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:40 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:52791) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPP-0000zH-0Q for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 69B6221F37; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:07 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 01927102A3; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=oXFEAlJ4YDyX0kBgpl6dH4hVjM Vm+r9TAR+9xxyhScQ=; b=qoozoricGP8uzmDJstVzUKgqKS92e9c/LTlybn0Qyt Wz41P/No9vLtW9zDVPtMoeU0G7oXkc18FFPEeWNtBF+MYuZ1lLHASYaW6fz+3mY3 DascqEtnkujI++xhWFUS0PuCy+/ZsrSuHiSl5s86wRpiugR6CkfQTtX8ZEfqb+ey E= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=oXFEAl J4YDyX0kBgpl6dH4hVjMVm+r9TAR+9xxyhScQ=; b=Krwsd5P93i61n5SJRaYGPd hBBdXRI/hN8B9AVtDOjep81ryN6oiXEF7Qc04+BaJAbgTiMR5/ybDwUFC/SfRdC/ TcgeKRns0f/jszUynYdIU1YvDBY+kcu2VJmrN5cccwS87sviRF+cBkOGq3ySbkar IRFRhM5lWYCO7+KHofp7KvkYJkjxy3EQYns2a2RtS9oqL2nxmZ+lOVRNS/iXPtf3 ed0NIp+Qcp7cYkFUVBdTrYDA8WO4yMHpUc21nWSTYed3nhJYzPqsga7lGiNLvtzh bd/i6gnyAOpH9qhkpR5fquXnd8XhUC1ZkA49B/DljxBNItLjfFlSskmte0qknTeA == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:51 -0400 Message-Id: <20180910185859.27917-5-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 04/12] 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 This improves qht.c code coverage from 89.44% to 90.00%. Reviewed-by: Alex Benn=C3=A9e Signed-off-by: Emilio G. Cota --- 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:00:04 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 1536606590552544.3617903532588; Mon, 10 Sep 2018 12:09:50 -0700 (PDT) Received: from localhost ([::1]:53578 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRZF-0000U0-HO for importer@patchew.org; Mon, 10 Sep 2018 15:09:49 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49208) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPS-0001JP-Ic for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:46 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPQ-0001Ej-7S for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:42 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:36299) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPP-00013L-KI for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 8F4F221C5F; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:07 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 31F3B102A9; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=mDW1bpU8LZHVmYbAuYwFaDzRgC kzPTfrTIP6+P4z2yY=; b=GQWri1QSnEufh5xLYqnHiItFdyfALkJRnmYsE4lFlx E0yiM0kbTx8ywIZwoyqQ5+KA/JCBl4KTvK1r2nmm/Xu/m7w9W0pxmm0FaspCPai8 FynhGMT7RePFcP3o/p4bE1edZRV3Ot0oFIk/T39UivyZJx+smTMP8RlZTXMBhBOm c= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=mDW1bp U8LZHVmYbAuYwFaDzRgCkzPTfrTIP6+P4z2yY=; b=D0LFp46cExt4EG2DmH+tf0 AaruVGeNC6Nl1Bf6CI9Cc+GhTgBo+vam9BwW6O5Ufvg0oos1iUeHnK9RFWak5HLD 0KPC0IPe+YkuquZCsySMZYZSK5xLA1GHs0Lz/fe1e3p9AlvzXZIpjptcdMQ3OdXh FinCKISLXnPz762GRoqAiksb1jEKzJ3z27nutu0evmphcu40A20o54Py4MD1nXL9 yQRRRndVhd9unmftf/6FDKjlmp8xIB6Bjm+24gbVWjVqgKaanxBVBKBpasiCltoB pgNuNjhkEWrrZBfV/dAR0gx2eLe7BzQ4eEQCy9psLRRLTYnuGDTlV8SY7VGa2X3g == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:52 -0400 Message-Id: <20180910185859.27917-6-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 05/12] 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 This improves coverage by one (!) LoC in qht.c, bringing the coverage rate up from 90.00% to 90.28%. Reviewed-by: Alex Benn=C3=A9e Signed-off-by: Emilio G. Cota --- 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:00:04 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 1536606477944311.28467090664856; Mon, 10 Sep 2018 12:07:57 -0700 (PDT) Received: from localhost ([::1]:53570 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRXQ-0007fr-VP for importer@patchew.org; Mon, 10 Sep 2018 15:07:57 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49200) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPS-0001JC-CT for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:46 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPQ-0001F5-G1 for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:41 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:47803) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPQ-00013K-1y for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:40 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id BA6D321F3A; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:07 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 62E5B102AA; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=6BL/3joOqPSUYInxy9V+VS1rnR 71YW2beJNdmGlVusk=; b=rfuhNJcxAi4ZoxF9uEHqK2VfflUlz5S5G/CdTRkPrw GBOnarOksW1ohr1fSc7F4KaFkFakpqN4DhPsVcwFWmxN9Tcn+/801rSEQiuIYxU5 LTVgD/+oSFCqtwDJZ841kmIypms6pjsGSHc3YNaPSzSxCZoeRrX3QpDqGzlrbwbu U= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=6BL/3j oOqPSUYInxy9V+VS1rnR71YW2beJNdmGlVusk=; b=HyU9SRsw3A01WUpPDRqf4T hte1LzE0B3whXad2j0ka2KLBiUiMZOvKtxHhQDfm+j/DtIT51BhvewMpmhgGw/SB NqKX+wGlRJXDTmCGnvqoDsyvasYLt8hmoj+ES0PUcRKAjckkJACmc7/45/2MwqxG 4SS4pG8R59RRmLJSRcKQ/Y5Oslgqrfze3MfKkg1xrphS2Eaq7/gVoQB9u2caJnNK JmQWl8nRi+c3uBN8QDdIl592WFua+T9nZ5DdzeKxTKZ69w9eIVsjbEAGwNoGSTPo IQ8YVqnK4+C4jCmDD4idkmXPQaX7nX/9qvx+5F07LwLcLzeGERzSaj4znwrgbTHg == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:53 -0400 Message-Id: <20180910185859.27917-7-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 06/12] 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 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=C3=A9e Signed-off-by: Emilio G. Cota --- 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 From nobody Wed Nov 5 11:00:04 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 1536606584925177.38435313302455; Mon, 10 Sep 2018 12:09:44 -0700 (PDT) Received: from localhost ([::1]:53577 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRZ9-0000Pz-Q0 for importer@patchew.org; Mon, 10 Sep 2018 15:09:43 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49259) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPX-0001Nw-5w for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPP-0001Dq-Fw for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:43 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:32811) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPP-000195-5r for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 101D321F3D; Mon, 10 Sep 2018 14:59:08 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:08 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 958B610298; Mon, 10 Sep 2018 14:59:07 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=braap.org; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=RLCfPMTL/JO1SO5Zh/J+HY0LJY /mMkWgZmokCbT6yfE=; b=INYCbVZ0h3ShsSzsMwqXmsys4CVGFMKd3RMcGrp59H BOtIjjxgZ5aCpYPmR9TkieKObyXVWmfWAd7Qw7CwBDzHDQYORLRLQZQFqiH8trVx aCdV07Vr6AFswuhy8PZ++0DxCDzciz530o6+xPtshNMK4L+qLQ2koTwJDervrnk9 8= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=RLCfPM TL/JO1SO5Zh/J+HY0LJY/mMkWgZmokCbT6yfE=; b=S5eImlJp4wq8Le30XZ1lE7 1oI3PxVfpDN011aP89+gNJ55sWr3U/TI6eHCxAOH4GFuGOMILK2ekpXBhjv3pJS2 SnICNkWtZVJtMMCQJ3Pc1ObnAwNwcL4PUCLKFXeSX231SvEMNgh3RYCFB/HTTyH3 IXfC6BZLU6llHGfPUC0/lRfWgCSYKegc7k957BjtqQfdIh5tZp8X5Z6MqIyXMdhk yjZWqoSSAlkt03ZmhgvLbqaujx1NWHrzIdB9+U5OTOD6DwBYRoxl8RJlJKCZY60+ 8uRdr2el76RJX2JeXVn8io8NIzZAxNVBBNF7WlK7Z8vZavy6C1lL2+i29aLiXafw == X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:54 -0400 Message-Id: <20180910185859.27917-8-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-1-cota@braap.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 v2 07/12] qht: drop ht argument from qht iterators 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 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=C3=A9e Signed-off-by: Emilio G. Cota --- 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 { }; =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); +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); =20 #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 =20 -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 =3D p; target_ulong addr =3D *(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); } =20 -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 =3D 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); } =20 -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 =3D userp; =20 @@ -122,7 +122,7 @@ 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) +static void sum_func(void *p, uint32_t hash, void *userp) { uint32_t *sum =3D userp; uint32_t a =3D *(uint32_t *)p; @@ -138,7 +138,7 @@ static void iter_sum_check(unsigned int expected) g_assert_cmpuint(sum, =3D=3D, expected); } =20 -static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *user= p) +static bool rm_mod_func(void *p, uint32_t hash, void *userp) { uint32_t a =3D *(uint32_t *)p; unsigned int mod =3D *(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; } =20 -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 *user= p) { struct qht_bucket *b =3D head; @@ -759,10 +759,10 @@ static inline void qht_bucket_iter(struct qht *ht, st= ruct 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], user= p)) { + 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, st= ruct qht_bucket *head, } =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, +static inline void qht_map_iter__all_locked(struct qht_map *map, 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], iter, userp); + qht_bucket_iter(&map->buckets[i], iter, userp); } } =20 @@ -800,8 +800,7 @@ do_qht_iter(struct qht *ht, const struct qht_iter *iter= , void *userp) =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, iter, userp); + qht_map_iter__all_locked(map, iter, userp); qht_map_unlock_buckets(map); } =20 @@ -825,9 +824,16 @@ void qht_iter_remove(struct qht *ht, qht_iter_bool_fun= c_t func, void *userp) do_qht_iter(ht, &iter, userp); } =20 -static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *use= rp) +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 =3D userp; + struct qht_map_copy_data *data =3D userp; + struct qht *ht =3D data->ht; + struct qht_map *new =3D data->new; struct qht_bucket *b =3D qht_map_to_bucket(new, hash); =20 /* 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 =3D qht_map_copy, .type =3D QHT_ITER_VOID, }; + struct qht_map_copy_data data; =20 old =3D 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) } =20 g_assert(new->n_buckets !=3D old->n_buckets); - qht_map_iter__all_locked(ht, old, &iter, new); + data.ht =3D ht; + data.new =3D new; + qht_map_iter__all_locked(old, &iter, &data); qht_map_debug__all_locked(new); =20 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, gconstpointe= r bp, gpointer up) } } =20 -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 =3D p; GTree *tree =3D 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); } =20 -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 =3D up; const QSPEntry *e =3D 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); } =20 -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 =3D htp; QSPEntry *old =3D p; @@ -583,8 +583,7 @@ static void qsp_diff(struct qht *orig, struct qht *new) qht_iter(orig, qsp_iter_diff, new); } =20 -static void -qsp_iter_callsite_coalesce(struct qht *orig, void *p, uint32_t h, void *ht= p) +static void qsp_iter_callsite_coalesce(void *p, uint32_t h, void *htp) { struct qht *ht =3D htp; QSPEntry *old =3D p; @@ -603,7 +602,7 @@ qsp_iter_callsite_coalesce(struct qht *orig, void *p, u= int32_t h, void *htp) e->n_acqs +=3D old->n_acqs; } =20 -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); } --=20 2.17.1 From nobody Wed Nov 5 11:00:04 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 1536606309294846.7289095343914; Mon, 10 Sep 2018 12:05:09 -0700 (PDT) Received: from localhost ([::1]:53552 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRUi-0005SJ-4Q for importer@patchew.org; Mon, 10 Sep 2018 15:05:08 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49143) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPQ-0001Hu-V4 for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:42 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPP-0001Di-BF for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:40 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:36487) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPP-000196-02 for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 29D9A21F41; Mon, 10 Sep 2018 14:59:08 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:08 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id CC94410299; Mon, 10 Sep 2018 14:59:07 -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=zAR92fAzzGMW3n /sQbpIuVUh9jBWuzXNG2FSaF0dGYM=; b=tSXU4lj8S+xisYpzgit08ekChcVTdz dmny3kIroJZW+q/VcEwJwJVhblaap44LfUOPZF46+6UO2Vy6ACI4wzNUNIu50ilE f7EwME1ZQtMJVSxXDjqsKCLCmBvJuA2nAJukIEUELbz6ILzA0hTA1ExczQJO6WZ/ tLQrfFgjs2fuA= 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=zAR92fAzzGMW3n/sQbpIuVUh9jBWuzXNG2FSaF0dGYM=; b=Cg5HU/9F zYpIIZi+vfpXdNjPWm3QKWojhaMGIXls4lMrVcHBJBaK2EHKzEq0DEm0zLp9t2xy a9z5ks9hL7r+Pxtf5LSzov23fiLGTpzfNBWSeFUxS2NJpHQSYM0lefCE1jBjXALG z+uV0iSXLitICFgkjOpi9TaosY+fjh8xA9cVDHEuOz5K8zEIrZCcwbSErzlR3A+O jogHzI7IMoVs4qwZ24kvfwdfhU7XW7QEvbc3pnPEHfBoMSWw51+GyfZZFi2vwlLj W8SVgLryyjeOxf2oPmAadhW0Libe64807cjgEPeZ6Oc/EYqbzY47XLqj6J3gkGho EnUvLWOkqhAKWw== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:55 -0400 Message-Id: <20180910185859.27917-9-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-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 v2 08/12] qht: fix comment in qht_bucket_remove_entry 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 --- 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) } =20 /* - * 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 po= s) --=20 2.17.1 From nobody Wed Nov 5 11:00:04 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 153660631972073.00236953306216; Mon, 10 Sep 2018 12:05:19 -0700 (PDT) Received: from localhost ([::1]:53553 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRUs-0005a1-JG for importer@patchew.org; Mon, 10 Sep 2018 15:05:18 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49252) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPV-0001MS-RR for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:46 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPQ-0001FI-Pb for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:43 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:35481) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPQ-0001Cr-Gh for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:40 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 7980B21F43; Mon, 10 Sep 2018 14:59:08 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:08 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 0AB921029E; Mon, 10 Sep 2018 14:59:08 -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=cofvh+1D3FvnYV HED0DObiPkMcCboFUZYsZNu239q40=; b=cWQYml4HT9vHNnxCXP484gXu5EaozV 4l6Z3WxGOQqlmtJ9vOkSXPUiAQ5jIwxmP0RwfbY+16plAkVKKfw+65uFp41L0N+B 7TPF4pdTItWW1aI3hIfntRsE4p9utG0NabZgA9EzfGEWUTd+jpV8PLNv29F5fzHw TmG6yOo66N714= 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=cofvh+1D3FvnYVHED0DObiPkMcCboFUZYsZNu239q40=; b=RuNXL/Up fr5YUjZHH+iSFpgnfJdZWz4Capd89WRB93BbCcjhMhFXz9AnZFHbcszgdh8eBGTY SHatiM9XIm34Is1fPPVcJ1BjZy8/4Fwkn9U0HW1MYysqBzke8qi8dF7W6iTzFr+I 7tuWFGtfxx+/7aoYLRvWPN8H+8vOTbWbrc06/xqg0MQSvGuG2VMnmJMb+KylT0vQ V+VK0FeOScTokxNs0FEIc/J81Goy39ryLZ+OvpnLAnQ7GTdsee8O0huL+PSLDCmn 5o/zvImFufo8ROW8vPYoXaVZPSuNeyJQu9lDVqtXo+k03NhUbaV5HQxe27jThJ9I 8DlN0a0d/ze7gg== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:56 -0400 Message-Id: <20180910185859.27917-10-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-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 v2 09/12] qht: constify qht_lookup 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" 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 --- 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); =20 /** @@ -115,7 +115,7 @@ void *qht_lookup_custom(struct qht *ht, const void *use= rp, 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); =20 /** * 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) } =20 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 h= ash) { return &map->buckets[hash & (map->n_buckets - 1)]; } @@ -482,10 +482,10 @@ bool qht_reset_size(struct qht *ht, size_t n_elems) } =20 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 =3D head; + const struct qht_bucket *b =3D head; int i; =20 do { @@ -509,7 +509,7 @@ void *qht_do_lookup(struct qht_bucket *head, qht_lookup= _func_t func, } =20 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 f= unc, 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; } =20 -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; =20 @@ -545,7 +545,7 @@ void *qht_lookup_custom(struct qht *ht, const void *use= rp, uint32_t hash, return qht_lookup__slowpath(b, func, userp, hash); } =20 -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); } --=20 2.17.1 From nobody Wed Nov 5 11:00:04 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 1536606305076343.92570435586003; Mon, 10 Sep 2018 12:05:05 -0700 (PDT) Received: from localhost ([::1]:53551 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRUe-0005NW-0n for importer@patchew.org; Mon, 10 Sep 2018 15:05:04 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49151) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPR-0001IA-5j for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:42 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPP-0001DV-8y for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:41 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:46327) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPO-0001Cu-VB for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:39 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 8A49921F40; Mon, 10 Sep 2018 14:59:08 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:08 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 3B7C110298; Mon, 10 Sep 2018 14:59:08 -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=tFMvAYeVvbo8fD VzUqKfQ18MPUl9JN/wksfVJXaKRpw=; b=K/BJiBMI7AHxGpdkcrZaW2BiO3Ucet TLaC4e/p/jTg6oR5ANggwEC1I1kMm0B9k9WjgDFYZHhd3daA0uaPCNi1NEnSQOyT x6LB9nao1puNCuvOoCxVCsmdhHcWnC6tXtIAx9hFq2O78vp+NsxnmM+wWR/ukqPP X3ueK3pGwmDqc= 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=tFMvAYeVvbo8fDVzUqKfQ18MPUl9JN/wksfVJXaKRpw=; b=jihElqfs gxEcInrz3zhByeWTy2r9p4DF4ejLMQiTIl4CimpeG+aJcZoiG4/3NbY16PSmjXhk kumc0LDTrPuc7qNkfWQJn+BN0Zg9W4jg7J3iVU9oqF8SAh8U9kwaoDfRzJOwgkbt JSuUd6huWvO4nctGqUCfLByCDia1UBnZO1YtdFtOMoT1e7h6qHZSbQbx6whm6/7y CKUSw9gjxnfjiNXryW4ihjMaROym35/eQn0noI/KCPI1HyCZrILjURlActOnf5op JdmybGQzDcSLeeU9AKunABEG8Wjbnd7YxbRat43MvQQTOdRDql5BVld3WKtjZuua bEwFYeuRUqqYww== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:57 -0400 Message-Id: <20180910185859.27917-11-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-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 v2 10/12] qht: constify qht_statistics_init 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 --- 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); =20 /** * 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) } =20 /* 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; =20 map =3D atomic_rcu_read(&ht->map); @@ -914,8 +914,8 @@ void qht_statistics_init(struct qht *ht, struct qht_sta= ts *stats) stats->head_buckets =3D map->n_buckets; =20 for (i =3D 0; i < map->n_buckets; i++) { - struct qht_bucket *head =3D &map->buckets[i]; - struct qht_bucket *b; + const struct qht_bucket *head =3D &map->buckets[i]; + const struct qht_bucket *b; unsigned int version; size_t buckets; size_t entries; --=20 2.17.1 From nobody Wed Nov 5 11:00:04 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 1536606421856899.0802250967074; Mon, 10 Sep 2018 12:07:01 -0700 (PDT) Received: from localhost ([::1]:53567 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRWW-0006uO-8N for importer@patchew.org; Mon, 10 Sep 2018 15:07:00 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49218) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPT-0001Jy-0E for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:46 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPQ-0001FU-UF for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:42 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:55397) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPQ-0001DQ-La for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:40 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id CE8F9211B7; Mon, 10 Sep 2018 14:59:08 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:08 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 68CC110299; Mon, 10 Sep 2018 14:59:08 -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=k3bKALiBg0cana 4eIJoaO6qbiIbNpu3LCCVpAZ6Mu50=; b=TgofNBldtp76wpTUA2C71qHhUDF2iR miwOAWfqw7MEpsrF/LxnSWK/FnuF4gnvz0w/cyu6DTNybJbwpq3yF+BsluCha3SK WQ7gPc8bmOuK3d5E0P2sy2YYsuw2LIOZ5C+yI6VMLYnnZd7TQ4lDyJwGp07SoBWb o/uuWMyKuuGUw= 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=k3bKALiBg0cana4eIJoaO6qbiIbNpu3LCCVpAZ6Mu50=; b=Iz9sWLoO 0LABrncJHa6mcIUCSxVP4sjjs/ttnyQ9gfw8MDIkc1k4m5jrpqNEc7TsaFA9rUAD FOAcY3xzRJL4ykfvDX6lI2pC/TmZW4xFWlu9EaKt88+LuOC2Ac5qJSymDIqEXwUK c4f7W+n33kiociry46iZ8CRw0ewaWeVpgzFx1QBIpgBVSv7bVj3f0c1MraWTy3KS 0LthsCN8pjG3phYLWkHvkHnUk471KpIlsJ1ZGCpaeWxBMHyYWhJtvYHtj1WkfhTl H5YUdadwsjgHTym+D+BGmJTv+pR4aKOkNl1e9N7lkC+0eSPfmwIhg/FnfIjAsPcX TspadXyCvBUxHQ== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:58 -0400 Message-Id: <20180910185859.27917-12-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-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 v2 11/12] qht: constify arguments to some internal functions 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" These functions do not modify their @ht or @bucket arguments. Constify those arguments. Signed-off-by: Emilio G. Cota --- 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 !=3D ht->map; } @@ -337,12 +338,12 @@ struct qht_bucket *qht_bucket_lock__no_stale(struct q= ht *ht, uint32_t hash, return b; } =20 -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_thres= hold; } =20 -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 =3D head->next; struct qht_bucket *prev; @@ -550,8 +551,11 @@ void *qht_lookup(const struct qht *ht, const void *use= rp, uint32_t hash) return qht_lookup_custom(ht, userp, hash, ht->cmp); } =20 -/* 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; } =20 -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 =3D=3D QHT_BUCKET_ENTRIES - 1) { if (b->next =3D=3D NULL) { --=20 2.17.1 From nobody Wed Nov 5 11:00:04 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 1536606671665434.52484597657974; Mon, 10 Sep 2018 12:11:11 -0700 (PDT) Received: from localhost ([::1]:53587 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRaY-0001P7-Km for importer@patchew.org; Mon, 10 Sep 2018 15:11:10 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49315) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fzRPc-0001Tk-Qa for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:57 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fzRPb-0001Kw-3l for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:52 -0400 Received: from out1-smtp.messagingengine.com ([66.111.4.25]:35791) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fzRPa-0001DR-Tn for qemu-devel@nongnu.org; Mon, 10 Sep 2018 14:59:50 -0400 Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id EF2A821F3C; Mon, 10 Sep 2018 14:59:08 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute4.internal (MEProxy); Mon, 10 Sep 2018 14:59:08 -0400 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 9C34510298; Mon, 10 Sep 2018 14:59:08 -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=iN5Wimj//o+Y/q ruL0UaJpUL1+d3vp9l2ed7Y8857OY=; b=E10xLwGAzzqeywRqo2FhdL33ASqnOe nyJJhEudbfTvHGMk5FacaC08/3GvjakyCsrFEQOGkmC0R9GyqhfXH+FEueTU08/h Z2e5CcS/SUDSmSG8y5oWzLiIfaHng1MA1C7x7YjfVPCleLneEN184e//+rK7Xtz+ R7dblR/TY/MSg= 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=iN5Wimj//o+Y/qruL0UaJpUL1+d3vp9l2ed7Y8857OY=; b=oF/2hgbm l6e4xhRF0rU1x8bqzXv1hedHaAdryEEiI0/G4J2EiAFxiE2BLVBp/1h0j3iIn4+R 8Dn3JpShya43bx3Iyl3whKBwnFifvcwk5eg3tVW+Yl8O78KV0l6T0LE5yNyl0+TB TH4gRJLVfbpwcWEBu7+ttbnbVqkJ9sFl6tpa4ihDUEZUZlKA6ERp+evTwcK8uEuQ sFaNaDT9U65ZIo6QpFh2PBgqLf5sOOrZhB4G7Qd/bHcH3sB7CE3WXVXs96SKcS0j y4z/VVxkS39YIzmx8krqeBfmAq53DY6CihCas5x4Hnfn9WQZiMZQzVmWu0uSbR+W bstdujaG8HTZiw== X-ME-Proxy: X-ME-Sender: From: "Emilio G. Cota" To: qemu-devel@nongnu.org Date: Mon, 10 Sep 2018 14:58:59 -0400 Message-Id: <20180910185859.27917-13-cota@braap.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180910185859.27917-1-cota@braap.org> References: <20180910185859.27917-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 v2 12/12] qht-bench: add -p flag to precompute hash values 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" 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 --- 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 =3D 1000; static double resize_rate; /* 0.0 to 1.0 */ static unsigned int n_rz_threads =3D 1; static QemuThread *rz_threads; +static bool precompute_hash; =20 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 =3D=3D *b; } =20 -static inline uint32_t h(unsigned long v) +static uint32_t h(unsigned long v) { return tb_hash_func7(v, 0, 0, 0, 0); } =20 +static uint32_t hval(unsigned long v) +{ + return v; +} + +static uint32_t (*hfunc)(unsigned long v) =3D h; + /* * From: https://en.wikipedia.org/wiki/Xorshift * This is faster than rand_r(), and gives us a wider range (RAND_MAX is o= nly @@ -149,7 +157,7 @@ static void do_rw(struct thread_info *info) bool read; =20 p =3D &keys[info->r & (lookup_range - 1)]; - hash =3D h(*p); + hash =3D hfunc(*p); read =3D qht_lookup(&ht, p, hash); if (read) { stats->rd++; @@ -158,7 +166,7 @@ static void do_rw(struct thread_info *info) } } else { p =3D &keys[info->r & (update_range - 1)]; - hash =3D h(*p); + hash =3D hfunc(*p); if (info->write_op) { bool written =3D false; =20 @@ -289,7 +297,9 @@ static void htable_init(void) /* avoid allocating memory later by allocating all the keys now */ keys =3D g_malloc(sizeof(*keys) * n); for (i =3D 0; i < n; i++) { - keys[i] =3D populate_offset + i; + long val =3D populate_offset + i; + + keys[i] =3D precompute_hash ? h(val) : hval(val); } =20 /* some sanity checks */ @@ -321,7 +331,7 @@ static void htable_init(void) =20 r =3D xorshift64star(r); p =3D &keys[r & (init_range - 1)]; - hash =3D h(*p); + hash =3D hfunc(*p); if (qht_insert(&ht, p, hash, NULL)) { break; } @@ -412,7 +422,7 @@ static void parse_args(int argc, char *argv[]) int c; =20 for (;;) { - c =3D getopt(argc, argv, "d:D:g:k:K:l:hn:N:o:r:Rs:S:u:"); + c =3D 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 =3D atol(optarg); break; + case 'p': + precompute_hash =3D true; + hfunc =3D hval; + break; case 'r': update_range =3D pow2ceil(atol(optarg)); break; --=20 2.17.1