From patchwork Fri Jul 31 09:23:21 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anton Ivanov X-Patchwork-Id: 1339347 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.133; helo=hemlock.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=cambridgegreys.com Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BJ2016QDfz9sRK for ; Fri, 31 Jul 2020 19:23:44 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 9129E88794; Fri, 31 Jul 2020 09:23:42 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wb90vW7BDDoE; Fri, 31 Jul 2020 09:23:40 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by hemlock.osuosl.org (Postfix) with ESMTP id 1DB6C88788; Fri, 31 Jul 2020 09:23:40 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id F01E3C0888; Fri, 31 Jul 2020 09:23:39 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3A033C004D for ; Fri, 31 Jul 2020 09:23:35 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 2506320430 for ; Fri, 31 Jul 2020 09:23:35 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5wekr1tySxRd for ; Fri, 31 Jul 2020 09:23:33 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from www.kot-begemot.co.uk (ivanoab7.miniserver.com [37.128.132.42]) by silver.osuosl.org (Postfix) with ESMTPS id 966CE20428 for ; Fri, 31 Jul 2020 09:23:33 +0000 (UTC) Received: from tun252.jain.kot-begemot.co.uk ([192.168.18.6] helo=jain.kot-begemot.co.uk) by www.kot-begemot.co.uk with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1k1RGF-0004o7-FZ for dev@openvswitch.org; Fri, 31 Jul 2020 09:23:31 +0000 Received: from jain.kot-begemot.co.uk ([192.168.3.3]) by jain.kot-begemot.co.uk with esmtp (Exim 4.92) (envelope-from ) id 1k1RGC-0000TV-Tb; Fri, 31 Jul 2020 10:23:30 +0100 From: anton.ivanov@cambridgegreys.com To: dev@openvswitch.org Date: Fri, 31 Jul 2020 10:23:21 +0100 Message-Id: <20200731092323.763-2-anton.ivanov@cambridgegreys.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20200731092323.763-1-anton.ivanov@cambridgegreys.com> References: <20200731092323.763-1-anton.ivanov@cambridgegreys.com> MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett Cc: Anton Ivanov Subject: [ovs-dev] [PATCH 1/3] Optimise shash disposal X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" From: Anton Ivanov SHASH as written at present relies on HMAP and iterator macros to dispose of all of its elements. This results in a lot of unnecessary hash comparisons and walk attempts which simply return the next item. This patch switches this to direct removal where the whole shash is cleared at once in O(N) without any hash recomputations and comparisons. Signed-off-by: Anton Ivanov --- lib/shash.c | 48 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 37 insertions(+), 11 deletions(-) diff --git a/lib/shash.c b/lib/shash.c index a8433629a..09505b73d 100644 --- a/lib/shash.c +++ b/lib/shash.c @@ -68,27 +68,53 @@ shash_moved(struct shash *sh) void shash_clear(struct shash *sh) { - struct shash_node *node, *next; + struct shash_node *node; + struct hmap_node *hn; + + int i; - SHASH_FOR_EACH_SAFE (node, next, sh) { - hmap_remove(&sh->map, &node->node); - free(node->name); - free(node); + if (sh->map.n == 0) { + return; + } + + for (i = 0; i <= sh->map.mask; i++) { + hn = sh->map.buckets[i]; + while (hn != NULL) { + node = CONTAINER_OF(hn, struct shash_node, node); + hn = hn->next; + free(node->name); + free(node); + } + sh->map.buckets[i] = NULL; } + sh->map.n = 0; } /* Like shash_clear(), but also free() each node's 'data'. */ void shash_clear_free_data(struct shash *sh) { - struct shash_node *node, *next; + struct shash_node *node; + struct hmap_node *hn; + + int i; - SHASH_FOR_EACH_SAFE (node, next, sh) { - hmap_remove(&sh->map, &node->node); - free(node->data); - free(node->name); - free(node); + if (sh->map.n == 0) { + return; + } + + for (i = 0; i <= sh->map.mask; i++) { + hn = sh->map.buckets[i]; + while (hn != NULL) { + node = CONTAINER_OF(hn, struct shash_node, node); + hn = hn->next; + free(node->data); + free(node->name); + free(node); + } + sh->map.buckets[i] = NULL; } + sh->map.n = 0; } bool