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 From patchwork Fri Jul 31 09:23:22 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anton Ivanov X-Patchwork-Id: 1339346 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.136; helo=silver.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 silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BJ1zz11rjz9sTH for ; Fri, 31 Jul 2020 19:23:42 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 803F720430; Fri, 31 Jul 2020 09:23:40 +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 hiS9+QRt+31o; Fri, 31 Jul 2020 09:23:38 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by silver.osuosl.org (Postfix) with ESMTP id A615B20447; Fri, 31 Jul 2020 09:23:38 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7FE3EC004D; Fri, 31 Jul 2020 09:23:38 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id F18DFC004D for ; Fri, 31 Jul 2020 09:23:34 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id DD9B087C89 for ; Fri, 31 Jul 2020 09:23:34 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GuBetqbkVMRO for ; Fri, 31 Jul 2020 09:23:34 +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 whitealder.osuosl.org (Postfix) with ESMTPS id 71BC587885 for ; Fri, 31 Jul 2020 09:23:34 +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 1k1RGH-0004oB-3o for dev@openvswitch.org; Fri, 31 Jul 2020 09:23:33 +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 1k1RGE-0000TV-IK; Fri, 31 Jul 2020 10:23:32 +0100 From: anton.ivanov@cambridgegreys.com To: dev@openvswitch.org Date: Fri, 31 Jul 2020 10:23:22 +0100 Message-Id: <20200731092323.763-3-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 2/3] Use and reuse hash wherever possible in shash 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 Add missing hash uses into shash to avoid hash recomputations. Signed-off-by: Anton Ivanov Acked-by: Dumitru Ceara --- lib/shash.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/lib/shash.c b/lib/shash.c index 09505b73d..f378d1656 100644 --- a/lib/shash.c +++ b/lib/shash.c @@ -158,8 +158,9 @@ shash_add(struct shash *sh, const char *name, const void *data) bool shash_add_once(struct shash *sh, const char *name, const void *data) { - if (!shash_find(sh, name)) { - shash_add(sh, name, data); + size_t hash = hash_name(name); + if (!shash_find__(sh, name, strlen(name), hash)) { + shash_add_nocopy__(sh, xstrdup(name), data, hash); return true; } else { return false; @@ -343,7 +344,7 @@ shash_equal_keys(const struct shash *a, const struct shash *b) return false; } SHASH_FOR_EACH (node, a) { - if (!shash_find(b, node->name)) { + if (!shash_find__(b, node->name, strlen(node->name), node->node.hash)) { return false; } } From patchwork Fri Jul 31 09:23:23 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anton Ivanov X-Patchwork-Id: 1339348 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.137; helo=fraxinus.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 fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BJ2041hRsz9sRK for ; Fri, 31 Jul 2020 19:23:47 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 94CC986B67; Fri, 31 Jul 2020 09:23:44 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BUWj7vn-N1Jd; Fri, 31 Jul 2020 09:23:42 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by fraxinus.osuosl.org (Postfix) with ESMTP id 89D1586916; Fri, 31 Jul 2020 09:23:41 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 45AF8C0893; Fri, 31 Jul 2020 09:23:41 +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 5AEACC004D for ; Fri, 31 Jul 2020 09:23:37 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id 4F02120504 for ; Fri, 31 Jul 2020 09:23:37 +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 2Di0qwhHZOnp for ; Fri, 31 Jul 2020 09:23:36 +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 2168D20447 for ; Fri, 31 Jul 2020 09:23:36 +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 1k1RGI-0004oF-Oe for dev@openvswitch.org; Fri, 31 Jul 2020 09:23:34 +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 1k1RGG-0000TV-6h; Fri, 31 Jul 2020 10:23:33 +0100 From: anton.ivanov@cambridgegreys.com To: dev@openvswitch.org Date: Fri, 31 Jul 2020 10:23:23 +0100 Message-Id: <20200731092323.763-4-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 3/3] Unroll operations inside shash_find_and_delete 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_find_and_delete at present looks up an item using shash_find then uses hmap_delete to delete it. As a result it computes the hash twice and does two walks of the linked list in the bucket. This change unrolls the first walk to preserve extra information making the second computation and walk unnecessary. Signed-off-by: Anton Ivanov --- lib/shash.c | 36 ++++++++++++++++++++++++++++++------ 1 file changed, 30 insertions(+), 6 deletions(-) diff --git a/lib/shash.c b/lib/shash.c index f378d1656..d2793c2e7 100644 --- a/lib/shash.c +++ b/lib/shash.c @@ -276,14 +276,38 @@ shash_find_data(const struct shash *sh, const char *name) void * shash_find_and_delete(struct shash *sh, const char *name) { - struct shash_node *node = shash_find(sh, name); - if (node) { - void *data = node->data; - shash_delete(sh, node); - return data; - } else { + struct shash_node *node; + + /* unroll shash_find and hmap_find */ + + struct hmap_node + **bucket = &sh->map.buckets[hash_name(name) & sh->map.mask]; + ssize_t name_len = strlen(name); + + while (*bucket != NULL) { + node = CONTAINER_OF(*bucket, struct shash_node, node); + if (!strncmp(node->name, name, name_len) && !node->name[name_len]) { + break; + } + bucket = &(*bucket)->next; + } + + if (*bucket == NULL) { return NULL; } + + void *data = node->data; + + /* use the underlying hmap node to do a direct hmap remove */ + + *bucket = node->node.next; + sh->map.n--; + + /* unroll smap_steal and smap_delete */ + + free(node->name); + free(node); + return data; } void *