From patchwork Wed Sep 26 18:36:58 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 147631 Delivered-To: patch@linaro.org Received: by 2002:a2e:8595:0:0:0:0:0 with SMTP id b21-v6csp1066784lji; Wed, 26 Sep 2018 11:38:01 -0700 (PDT) X-Google-Smtp-Source: ACcGV62/XeQVDdjID6/+8SxWTGTx9xI241dP2n8rMFdCFCSx71AP/nlU0+ax3PM/49uIva5nx7jr X-Received: by 2002:a0c:ec8e:: with SMTP id u14-v6mr5261064qvo.173.1537987080928; Wed, 26 Sep 2018 11:38:00 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1537987080; cv=none; d=google.com; s=arc-20160816; b=yfDnKUUcyNbKc+vHDQNBteys653OF3Hc5UDRLTnBs8KcKNHZvmwy9vG7nq2h+jUY12 cz0NhKJl3EEQ9ZgsdhpRESoxzo3RLdTC/6Xxx8mon76cwsjP2rQN+f2lbdziiY5dUILY APK6JxOQyy8V0UFtir1uIy4Om+YjAPa5eZpL7PAKe5KXXjLaZypWtKSq0WKJRXLXQWgv c/Kq3xFqV7U0AdoWmDw6B9dX4LAiCZjKV94Vxa+jTj8te4ObYYjx/G2CbpKPwUlx63Jm UO7cLNOl+zgbi80vNHRg3XrkTb+bQTLY0YxzxzNIQWGE82zrQ2yWaa/CZLmyvp04mThQ iNfg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:subject :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:to:from:dkim-signature; bh=fWoa1Zi9X4ZzdLHzaNha+kvw53UENpeP3xojdxN2gO0=; b=v0+gtVHICurRCUWh4VhUCme04WqQG4XCGXKFYtOfn+L4WJopZVK4XQaQfeoqeQbQme JmeE+h577UoCD5D3Z2Wn9GNKXwesDSPaHVes69Jlddu5Z7FwTPdtf8D4yQ2TGRo4+J1d 5Jf2EMC74yI2DoEIBN3Ngr4DFWABkxlVZGCrcqKQMho+FQGKOV1np5m5PnPl5xYX5GG7 mZQQjsQEmTwihW52WJ6H0Ag4RQ9mT0wdHrn+/KBv/28MbMv2dWdimBUz/I154jO5SMA7 4O+xkMuEZ8u/B+8SeSdg29anmbECJZ05bgIPq71l9GWOauxHd98S/TlvBEmey99kXEfV nYoA== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail header.i=@linaro.org header.s=google header.b=LFW4ZT8H; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from lists.gnu.org (lists.gnu.org. [2001:4830:134:3::11]) by mx.google.com with ESMTPS id x9-v6si4366357qkl.52.2018.09.26.11.38.00 for (version=TLS1 cipher=AES128-SHA bits=128/128); Wed, 26 Sep 2018 11:38:00 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) client-ip=2001:4830:134:3::11; Authentication-Results: mx.google.com; dkim=fail header.i=@linaro.org header.s=google header.b=LFW4ZT8H; spf=pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) smtp.mailfrom="qemu-devel-bounces+patch=linaro.org@nongnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from localhost ([::1]:60163 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1g5EhE-0001eo-BC for patch@linaro.org; Wed, 26 Sep 2018 14:38:00 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53559) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1g5Egj-0001SH-SC for qemu-devel@nongnu.org; Wed, 26 Sep 2018 14:37:32 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1g5Ege-0007Iz-UC for qemu-devel@nongnu.org; Wed, 26 Sep 2018 14:37:27 -0400 Received: from mail-pg1-x543.google.com ([2607:f8b0:4864:20::543]:41407) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1g5Egc-000799-9h for qemu-devel@nongnu.org; Wed, 26 Sep 2018 14:37:24 -0400 Received: by mail-pg1-x543.google.com with SMTP id z3-v6so9436213pgv.8 for ; Wed, 26 Sep 2018 11:37:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=fWoa1Zi9X4ZzdLHzaNha+kvw53UENpeP3xojdxN2gO0=; b=LFW4ZT8HSXg4J3y4dY39P8jEQSSWVqPG4pgbtFSWEwSlP0ayD7mhetnqlkwTiJp1lp Xab1ivLod54l1ILb4WLwFP5T+uXOCA517DH59tUdKGmqPMYhSuE8pDunmUMf+T+ta2TN jH1aJHn8rS+kQFLVfsme6+1tfKR/Y+KHvMOgs= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=fWoa1Zi9X4ZzdLHzaNha+kvw53UENpeP3xojdxN2gO0=; b=cqMg8JeJPSoDs37RroiPsk5guUBa0Ecaymy641ZZXVxt/cfd8CU4H0S5p/Z1kB55c1 YZVDWkL1oHkXdW1RiEvc/ywHSKkTWg4Y4LYQHq4ZFNxQ98Pvu9GFzCFesoOCwc5bFOTi jNT7dp81zmwWT2Yu6TrAtToAPNfsF62iqT7RBkM8/95U/xnrwcYjI3yBkcCMH5zKtG7Q IH479DUbi40ADE5hFap+rqWnTzKsxZ0HSbsh1yk/68Hb6nw/GujQj0UwZOi6d0sQP1Xo Brhl/P83cfBAA39I+4J+OnKDU1yvxIEYM3O/nykwpWvpgcjq3CaR3S0ph82cRfTpyEGn lFgw== X-Gm-Message-State: ABuFfoiMG91I79Hp0zp0Ta/7mdrz1D8EM8IQrAYk3GVxm/TwPlsKFXOt eEgEBsT3qP3w5Z43BQBm7/JKQXFN/ys= X-Received: by 2002:a63:c046:: with SMTP id z6-v6mr6849275pgi.114.1537987035271; Wed, 26 Sep 2018 11:37:15 -0700 (PDT) Received: from cloudburst.twiddle.net (97-113-8-179.tukw.qwest.net. [97.113.8.179]) by smtp.gmail.com with ESMTPSA id b14-v6sm9735952pfc.178.2018.09.26.11.37.13 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 26 Sep 2018 11:37:14 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Wed, 26 Sep 2018 11:36:58 -0700 Message-Id: <20180926183709.21293-3-richard.henderson@linaro.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180926183709.21293-1-richard.henderson@linaro.org> References: <20180926183709.21293-1-richard.henderson@linaro.org> MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::543 Subject: [Qemu-devel] [PULL 02/13] 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: peter.maydell@linaro.org, "Emilio G. Cota" Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: "Qemu-devel" From: "Emilio G. Cota" 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ée Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- include/qemu/qht.h | 19 ++++++++++++ util/qht.c | 74 +++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 85 insertions(+), 8 deletions(-) -- 2.17.1 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 { 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); #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 pair, * 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); +/** + * 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 pair, + * 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 *userp); + /** * 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 +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; } -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 *userp) { + struct qht_bucket *b = head; int i; do { @@ -743,7 +757,25 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b, if (b->pointers[i] == 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], userp)) { + /* 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 = b->next; } while (b); @@ -751,26 +783,48 @@ static inline void qht_bucket_iter(struct qht *ht, struct qht_bucket *b, /* 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 *userp) + const struct qht_iter *iter, + void *userp) { size_t i; for (i = 0; i < map->n_buckets; i++) { - qht_bucket_iter(ht, &map->buckets[i], func, userp); + qht_bucket_iter(ht, &map->buckets[i], iter, userp); } } -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; map = atomic_rcu_read(&ht->map); qht_map_lock_buckets(map); /* Note: ht here is merely for carrying ht->mode; ht->map won't be read */ - qht_map_iter__all_locked(ht, map, func, userp); + qht_map_iter__all_locked(ht, map, iter, userp); qht_map_unlock_buckets(map); } +void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp) +{ + const struct qht_iter iter = { + .f.retvoid = func, + .type = QHT_ITER_VOID, + }; + + do_qht_iter(ht, &iter, userp); +} + +void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp) +{ + const struct qht_iter iter = { + .f.retbool = func, + .type = QHT_ITER_RM, + }; + + do_qht_iter(ht, &iter, userp); +} + static void qht_map_copy(struct qht *ht, void *p, uint32_t hash, void *userp) { struct qht_map *new = userp; @@ -787,6 +841,10 @@ static void qht_map_copy(struct qht *ht, void *p, uint32_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 = { + .f.retvoid = qht_map_copy, + .type = QHT_ITER_VOID, + }; old = 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) } g_assert(new->n_buckets != 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); atomic_rcu_set(&ht->map, new);