From nobody Wed Nov 5 13:32:31 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