From patchwork Thu Aug 20 22:49:36 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Gregory Rose X-Patchwork-Id: 1348657 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.138; helo=whitealder.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20161025 header.b=S8ThfFgw; dkim-atps=neutral Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BXfxp0NvRz9sPB for ; Fri, 21 Aug 2020 08:50:38 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 900A888568; Thu, 20 Aug 2020 22:50:36 +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 2laCVrT9nKWY; Thu, 20 Aug 2020 22:50:29 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by whitealder.osuosl.org (Postfix) with ESMTP id C74A688494; Thu, 20 Aug 2020 22:50:20 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id B05FFC08A2; Thu, 20 Aug 2020 22:50:20 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3DE70C0051 for ; Thu, 20 Aug 2020 22:50:19 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 2BF5F88575 for ; Thu, 20 Aug 2020 22:50:19 +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 3qrBL-QcTuwe for ; Thu, 20 Aug 2020 22:50:18 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-pl1-f195.google.com (mail-pl1-f195.google.com [209.85.214.195]) by hemlock.osuosl.org (Postfix) with ESMTPS id 80AB588553 for ; Thu, 20 Aug 2020 22:50:18 +0000 (UTC) Received: by mail-pl1-f195.google.com with SMTP id v16so3746plo.1 for ; Thu, 20 Aug 2020 15:50:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=8Tgf/Sb5B/o19WQu3xUIuscVh0OjCV9HkxkkaO9+EM0=; b=S8ThfFgwpuIGizU+fPcI7iyHznSnRBydJhoZa2Pgw2sNOH1PQLolnvsXgb2zIR+oRo /2nPv5VGNpGIjnlMzgbeN6SlHamDM/OQLdkVsiDkgi6r6CAkszfdO3TN5LhdbStTiS37 BxI/lvQhRuiYKgJHMDOhigbGIOTzHtK1k5lwEwU7XandURbnTfL5CQ8PPqWeO/8JKDUh 0YBPazanc13/GzMV9/2fGDXS5xua832LUFB3T9HchFI1+SSZv04QuHksqZKgvjbBqpHo Z0qcot3MQRbhKViMOZdoLAVOfFzDjSJsdJ3xNmVFeWTac9EDAfHSh/YAAjxGKsgPcLVc H6bg== 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; bh=8Tgf/Sb5B/o19WQu3xUIuscVh0OjCV9HkxkkaO9+EM0=; b=AC6Q1UH3c9EXBbRW0zpPPE/gNFrGCk2HxexupXhwtc6D7DZFJBIb+v4jlAW+kevAsE 5Hp7hb8Ny9wsTgeyVpv3SZ5UlvuGPkYf08reEcx9r+kErV2T8uBWVAiMWVDfeU9Yt4DX O2qJ2dCasSkAI3VwHvVo9ORBSjG5StZdiBY7WazT4ltcVo8pSTbyhj35BHyDL3fZteNL Ok8V4XAH7rUj74FPNej9fHxHkstPTozwunKkYWUNm+CbJf9rN3BWHknvNBmj7bMTMiKs q3m9qkjrVXVe0EsN3DmAwOmvAjnXC7YkLkR7dibEHHWfy7zZgYlwnsXjH4xBUf3JWwIj huSQ== X-Gm-Message-State: AOAM5336tXxWMp+SpWRtu8KYxHyp6l/tIjoRrNxZQkH1d3l7JKTuehQ5 aCf8unCGEgnT2bXqDwT7in09SK7OL16vEA== X-Google-Smtp-Source: ABdhPJwbZWWrTS/nqQXs+LHdLAY1cM+yrBbdYmI2JhigYxMyy586v5h3qpe6HfPE4D6lPQtwzrCIDg== X-Received: by 2002:a17:90b:20d1:: with SMTP id ju17mr399645pjb.219.1597963817540; Thu, 20 Aug 2020 15:50:17 -0700 (PDT) Received: from gizo.domain (97-115-99-106.ptld.qwest.net. [97.115.99.106]) by smtp.gmail.com with ESMTPSA id y6sm116866pfr.61.2020.08.20.15.50.16 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 20 Aug 2020 15:50:16 -0700 (PDT) From: Greg Rose To: dev@openvswitch.org Date: Thu, 20 Aug 2020 15:49:36 -0700 Message-Id: <1597963790-12362-10-git-send-email-gvrose8192@gmail.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1597963790-12362-1-git-send-email-gvrose8192@gmail.com> References: <1597963790-12362-1-git-send-email-gvrose8192@gmail.com> Subject: [ovs-dev] [PATCH 09/23] datapath: optimize flow-mask looking up 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: , MIME-Version: 1.0 Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" From: Tonghao Zhang Upstream commit: commit 57f7d7b9164426c496300d254fd5167fbbf205ea Author: Tonghao Zhang Date: Fri Nov 1 22:23:49 2019 +0800 net: openvswitch: optimize flow-mask looking up The full looking up on flow table traverses all mask array. If mask-array is too large, the number of invalid flow-mask increase, performance will be drop. One bad case, for example: M means flow-mask is valid and NULL of flow-mask means deleted. +-------------------------------------------+ | M | NULL | ... | NULL | M| +-------------------------------------------+ In that case, without this patch, openvswitch will traverses all mask array, because there will be one flow-mask in the tail. This patch changes the way of flow-mask inserting and deleting, and the mask array will be keep as below: there is not a NULL hole. In the fast path, we can "break" "for" (not "continue") in flow_lookup when we get a NULL flow-mask. "break" v +-------------------------------------------+ | M | M | NULL |... | NULL | NULL| +-------------------------------------------+ This patch don't optimize slow or control path, still using ma->max to traverse. Slow path: * tbl_mask_array_realloc * ovs_flow_tbl_lookup_exact * flow_mask_find Signed-off-by: Tonghao Zhang Tested-by: Greg Rose Acked-by: Pravin B Shelar Signed-off-by: David S. Miller Cc: Tonghao Zhang Signed-off-by: Greg Rose Reviewed-by: Tonghao Zhang --- datapath/flow_table.c | 103 ++++++++++++++++++++++++++------------------------ 1 file changed, 53 insertions(+), 50 deletions(-) diff --git a/datapath/flow_table.c b/datapath/flow_table.c index 76b390e..62d726d 100644 --- a/datapath/flow_table.c +++ b/datapath/flow_table.c @@ -540,8 +540,8 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl, u32 *n_mask_hit, u32 *index) { - struct sw_flow_mask *mask; struct sw_flow *flow; + struct sw_flow_mask *mask; int i; if (*index < ma->max) { @@ -560,7 +560,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl, mask = rcu_dereference_ovsl(ma->masks[i]); if (!mask) - continue; + break; flow = masked_flow_lookup(ti, key, mask, n_mask_hit); if (flow) { /* Found */ @@ -716,7 +716,7 @@ int ovs_flow_tbl_num_masks(const struct flow_table *table) struct mask_array *ma; ma = rcu_dereference_ovsl(table->mask_array); - return ma->count; + return READ_ONCE(ma->count); } static struct table_instance *table_instance_expand(struct table_instance *ti, @@ -725,21 +725,33 @@ static struct table_instance *table_instance_expand(struct table_instance *ti, return table_instance_rehash(ti, ti->n_buckets * 2, ufid); } -static void tbl_mask_array_delete_mask(struct mask_array *ma, - struct sw_flow_mask *mask) +static void tbl_mask_array_del_mask(struct flow_table *tbl, + struct sw_flow_mask *mask) { - int i; + struct mask_array *ma = ovsl_dereference(tbl->mask_array); + int i, ma_count = READ_ONCE(ma->count); /* Remove the deleted mask pointers from the array */ - for (i = 0; i < ma->max; i++) { - if (mask == ovsl_dereference(ma->masks[i])) { - RCU_INIT_POINTER(ma->masks[i], NULL); - ma->count--; - kfree_rcu(mask, rcu); - return; - } + for (i = 0; i < ma_count; i++) { + if (mask == ovsl_dereference(ma->masks[i])) + goto found; } + BUG(); + return; + +found: + WRITE_ONCE(ma->count, ma_count -1); + + rcu_assign_pointer(ma->masks[i], ma->masks[ma_count -1]); + RCU_INIT_POINTER(ma->masks[ma_count -1], NULL); + + kfree_rcu(mask, rcu); + + /* Shrink the mask array if necessary. */ + if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) && + ma_count <= (ma->max / 3)) + tbl_mask_array_realloc(tbl, ma->max / 2); } /* Remove 'mask' from the mask list, if it is not needed any more. */ @@ -753,18 +765,8 @@ static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask) BUG_ON(!mask->ref_count); mask->ref_count--; - if (!mask->ref_count) { - struct mask_array *ma; - - ma = ovsl_dereference(tbl->mask_array); - tbl_mask_array_delete_mask(ma, mask); - - /* Shrink the mask array if necessary. */ - if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) && - ma->count <= (ma->max / 3)) - tbl_mask_array_realloc(tbl, ma->max / 2); - - } + if (!mask->ref_count) + tbl_mask_array_del_mask(tbl, mask); } } @@ -828,6 +830,29 @@ static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl, return NULL; } +static int tbl_mask_array_add_mask(struct flow_table *tbl, + struct sw_flow_mask *new) +{ + struct mask_array *ma = ovsl_dereference(tbl->mask_array); + int err, ma_count = READ_ONCE(ma->count); + + if (ma_count >= ma->max) { + err = tbl_mask_array_realloc(tbl, ma->max + + MASK_ARRAY_SIZE_MIN); + if (err) + return err; + + ma = ovsl_dereference(tbl->mask_array); + } + + BUG_ON(ovsl_dereference(ma->masks[ma_count])); + + rcu_assign_pointer(ma->masks[ma_count], new); + WRITE_ONCE(ma->count, ma_count +1); + + return 0; +} + /* Add 'mask' into the mask list, if it is not already there. */ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow, const struct sw_flow_mask *new) @@ -836,9 +861,6 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow, mask = flow_mask_find(tbl, new); if (!mask) { - struct mask_array *ma; - int i; - /* Allocate a new mask if none exsits. */ mask = mask_alloc(); if (!mask) @@ -848,28 +870,9 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow, mask->range = new->range; /* Add mask to mask-list. */ - ma = ovsl_dereference(tbl->mask_array); - if (ma->count >= ma->max) { - int err; - - err = tbl_mask_array_realloc(tbl, ma->max + - MASK_ARRAY_SIZE_MIN); - if (err) { - kfree(mask); - return err; - } - ma = ovsl_dereference(tbl->mask_array); - } - - for (i = 0; i < ma->max; i++) { - struct sw_flow_mask *t; - - t = ovsl_dereference(ma->masks[i]); - if (!t) { - rcu_assign_pointer(ma->masks[i], mask); - ma->count++; - break; - } + if (tbl_mask_array_add_mask(tbl, mask)) { + kfree(mask); + return -ENOMEM; } } else {