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 *