From patchwork Mon Aug 12 15:28:09 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bruce Richardson X-Patchwork-Id: 143092 X-Patchwork-Delegate: bruce.richardson@intel.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 222A9457A1; Mon, 12 Aug 2024 17:29:37 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id A3B1340E1F; Mon, 12 Aug 2024 17:28:47 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.16]) by mails.dpdk.org (Postfix) with ESMTP id 95EFB40B9A for ; Mon, 12 Aug 2024 17:28:38 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1723476519; x=1755012519; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=WNGvCEHT2eO8jmDMYmqgWt/AiLTTGF2USXUYqSHc79s=; b=Krlw/8yJFdJaRDHrNLJeKjxMLwKOU1y7WCdifu7kKVsBl7QavVeD+YuT 8FmLUpE6zGGr7Wgzi5ZP/PIALcKFUs87JS2lJdHi231ebjrMQ4YbEHQ0y NaZuCDrr3fFQ7E+dHotGv7f5x163bSenJmY7V/Qa+TIbJKCLF4N3AApj5 IcosOGD+iXVlw1JnH2nXbLT9ED1727Rj71iYIiRkUBdDCxGz+G7gGMm11 iaGodvQ3d2xnh2EsWQneAnqokc+EnEarH5U6iUOlCfpt9V990ngq0u5sV t67F5RHSS5Q6FAoiItnq9FDWjtl64QzirjRu6QC9LtzqPf/F/urKPbFiT Q==; X-CSE-ConnectionGUID: PDQuNp7FQWyAG0BbI0gSwA== X-CSE-MsgGUID: La6ThGLvT0ypJSHvI3XFGQ== X-IronPort-AV: E=McAfee;i="6700,10204,11162"; a="21743050" X-IronPort-AV: E=Sophos;i="6.09,283,1716274800"; d="scan'208";a="21743050" Received: from orviesa004.jf.intel.com ([10.64.159.144]) by orvoesa108.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 12 Aug 2024 08:28:38 -0700 X-CSE-ConnectionGUID: 6RVii8+lS8aOzUtcmocO2w== X-CSE-MsgGUID: C9dHZGWFRRa0dni+OfiUgA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.09,283,1716274800"; d="scan'208";a="63222582" Received: from silpixa00400562.ir.intel.com (HELO silpixa00401385.ir.intel.com) ([10.237.214.39]) by orviesa004.jf.intel.com with ESMTP; 12 Aug 2024 08:28:38 -0700 From: Bruce Richardson To: dev@dpdk.org Cc: Bruce Richardson Subject: [PATCH v3 10/16] net/ice/base: optimize subtree searches Date: Mon, 12 Aug 2024 16:28:09 +0100 Message-ID: <20240812152815.1132697-11-bruce.richardson@intel.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20240812152815.1132697-1-bruce.richardson@intel.com> References: <20240807093407.452784-1-bruce.richardson@intel.com> <20240812152815.1132697-1-bruce.richardson@intel.com> MIME-Version: 1.0 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org In a number of places throughout the driver code, we want to confirm that a scheduler node is indeed a child of another node. Currently, this is confirmed by searching down the tree from the base until the desired node is hit, a search which may hit many irrelevant tree nodes when recursing down wrong branches. By switching the direction of search, to check upwards from the node to the parent, we can avoid any incorrect paths, and so speed up processing. Signed-off-by: Bruce Richardson --- drivers/net/ice/base/ice_sched.c | 18 +++++------------- 1 file changed, 5 insertions(+), 13 deletions(-) diff --git a/drivers/net/ice/base/ice_sched.c b/drivers/net/ice/base/ice_sched.c index be13833e1e..f7d5f8f415 100644 --- a/drivers/net/ice/base/ice_sched.c +++ b/drivers/net/ice/base/ice_sched.c @@ -1475,20 +1475,12 @@ ice_sched_find_node_in_subtree(struct ice_hw *hw, struct ice_sched_node *base, { u16 i; - for (i = 0; i < base->num_children; i++) { - struct ice_sched_node *child = base->children[i]; - - if (node == child) - return true; - - if (child->tx_sched_layer > node->tx_sched_layer) - return false; - - /* this recursion is intentional, and wouldn't - * go more than 8 calls - */ - if (ice_sched_find_node_in_subtree(hw, child, node)) + if (base == node) + return true; + while (node->tx_sched_layer != 0 && node->parent != NULL) { + if (node->parent == base) return true; + node = node->parent; } return false; }