From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id ACDF31B429 for ; Mon, 9 Jul 2018 15:35:25 +0200 (CEST) X-Amp-Result: UNKNOWN X-Amp-Original-Verdict: FILE UNKNOWN X-Amp-File-Uploaded: False Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga102.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 09 Jul 2018 06:35:23 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.51,330,1526367600"; d="scan'208";a="63310050" Received: from bricha3-mobl.ger.corp.intel.com ([10.237.221.107]) by FMSMGA003.fm.intel.com with SMTP; 09 Jul 2018 06:35:10 -0700 Received: by (sSMTP sendmail emulation); Mon, 09 Jul 2018 14:35:06 +0100 Date: Mon, 9 Jul 2018 14:35:06 +0100 From: Bruce Richardson To: Alex Kiselev Cc: "dev@dpdk.org" Message-ID: <20180709133506.GA19364@bricha3-MOBL.ger.corp.intel.com> References: <20180709112439.GA18644@bricha3-MOBL.ger.corp.intel.com> <55621439.20180709153344@therouter.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <55621439.20180709153344@therouter.net> Organization: Intel Research and Development Ireland Ltd. User-Agent: Mutt/1.10.0 (2018-05-17) Subject: Re: [dpdk-dev] [PATCH v2] librte_lpm: Improve performance of the delete and add functions X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 09 Jul 2018 13:35:27 -0000 On Mon, Jul 09, 2018 at 03:33:44PM +0300, Alex Kiselev wrote: > >> + int ret = rte_hash_lookup_data(lpm->rules_tbl, (void *) &rule_key, > >> + (void **) &rule); > >> + if (ret >= 0) { > >> + /* delete the rule */ > >> + rte_hash_del_key(lpm->rules_tbl, (void *) &rule_key); > >> + lpm->used_rules--; > >> + rte_mempool_put(lpm->rules_pool, rule); > >> + } > > > Rather than doing a lookup and then delete, why not just try the delete > > straight off. If you want to check for the key not being present, it can be > > detected from the output of the delete call. From rte_hash.h: > > > * @return > > * - -EINVAL if the parameters are invalid. > > * - -ENOENT if the key is not found. > > A deleted rule has to be returned back to the mempool. > And I don't see any delete function in the rte_hash that can > return a deleted item back to a caller. > Good point, never mind my comment, so. > >> + > >> + return ret; > >> } > >> > >> /* > >> - * Deletes a rule > >> + * Deletes a group of rules > > > Include a comment that this bulk function will rebuild the lpm table, > > rather than doing incremental updates like the regular delete function. > ok > > > >> + * Convert a depth to a one byte long mask > >> + */ > >> +static uint8_t __attribute__((pure)) > >> +depth_to_mask_1b(uint8_t depth) > >> +{ > >> + /* To calculate a mask start with a 1 on the left hand side and right > >> + * shift while populating the left hand side with 1's > >> */ > >> - if ((lpm == NULL) || (ips == NULL) || (depths == NULL)) { > >> - return -EINVAL; > >> + return (signed char)0x80 >> (depth - 1); > > > I'd make the comment on the function a little clearer e.g. using an > example: "4 =>> 0xF0", which should remove the need to have the second comment > > above the return statement. > > > An alternative that might be a little clearer for the calculation would be: > "(uint8_t)(~(0xFF >>> depth))". > > I've just copied this function from rte_lpm.c and converted it to 1byte version. > I'll add an example 4 =>> 0xF0. > Ok. Keeping the code as-is is fine. > >> +} > >> + > >> +/* > >> + * Find a less specific rule > >> + */ > >> +static struct rte_lpm6_rule* > >> +rule_find_less_specific(struct rte_lpm6 *lpm, uint8_t *ip, uint8_t depth) > >> +{ > >> + if (depth == 1) > >> + return NULL; > >> + > >> + struct rte_lpm6_rule *rule; > >> + struct rte_lpm6_rule_key rule_key; > >> + rule_key_init(&rule_key, ip, depth); > >> + uint8_t mask; > >> + > >> + while (depth > 1) { > >> + depth--; > >> + > >> + /* each iteration zero one more bit of the key */ > >> + mask = depth & 7; /* depth % 8 */ > >> + if (mask > 0) > >> + mask = depth_to_mask_1b(mask); > >> + > >> + rule_key.depth = depth; > >> + rule_key.ip[depth >> 3] &= mask; > >> + > > > It seems strange that when you adjust the depth, you also need to mask out > > bits of the key which should be ignored. Can you make the masking part of > > the hash calculation, which would simplify the logic here a lot, and if so, > > does it affect performance much? > > The first version of rule_find_less_specific() was doing exactly what you are proposing, > masking whole ipv6 address every time. But then I just couldn't stop myself from > using this shortcut since it's a performance optimization patch. > > So, yes, it could be a part of the hash calculation, but why? It's definetly not > the most difficult part of the algorithm (even without this optimizations), > so it would not make life easier :) > Ok, makes sense. > >> } > >> -- > > Rest of the patch looks fine to me, though I can't say I've followed all > > the logic paths in full detail. > > > Main concern I have about the patch is the size. Is there any way this > > patch could be split up into a few smaller ones with more gradual changes? > I could try to split it in two parts. The first part will introduce the new rule > subsystem using a hashtable instead of a flat array. And the second one will include > the rest. > Please attempt to do so, if possible, for the next version. Thanks, /Bruce