Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S934553AbcLIQYO (ORCPT ); Fri, 9 Dec 2016 11:24:14 -0500 Received: from mail.linuxfoundation.org ([140.211.169.12]:58310 "EHLO mail.linuxfoundation.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754037AbcLIQYL (ORCPT ); Fri, 9 Dec 2016 11:24:11 -0500 From: Greg Kroah-Hartman To: linux-kernel@vger.kernel.org Cc: Greg Kroah-Hartman , stable@vger.kernel.org, Robert Shearman , Alexander Duyck , "David S. Miller" Subject: [PATCH 4.8 34/45] ipv4: Drop suffix update from resize code Date: Fri, 9 Dec 2016 17:21:03 +0100 Message-Id: <20161209161756.362121813@linuxfoundation.org> X-Mailer: git-send-email 2.10.2 In-Reply-To: <20161209161754.912203877@linuxfoundation.org> References: <20161209161754.912203877@linuxfoundation.org> User-Agent: quilt/0.65 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3957 Lines: 124 4.8-stable review patch. If anyone has any objections, please let me know. ------------------ From: Alexander Duyck [ Upstream commit a52ca62c4a6771028da9c1de934cdbcd93d54bb4 ] It has been reported that update_suffix can be expensive when it is called on a large node in which most of the suffix lengths are the same. The time required to add 200K entries had increased from around 3 seconds to almost 49 seconds. In order to address this we need to move the code for updating the suffix out of resize and instead just have it handled in the cases where we are pushing a node that increases the suffix length, or will decrease the suffix length. Fixes: 5405afd1a306 ("fib_trie: Add tracking value for suffix length") Reported-by: Robert Shearman Signed-off-by: Alexander Duyck Reviewed-by: Robert Shearman Tested-by: Robert Shearman Signed-off-by: David S. Miller Signed-off-by: Greg Kroah-Hartman --- net/ipv4/fib_trie.c | 42 +++++++++++++++++++++--------------------- 1 file changed, 21 insertions(+), 21 deletions(-) --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -681,6 +681,13 @@ static unsigned char update_suffix(struc { unsigned char slen = tn->pos; unsigned long stride, i; + unsigned char slen_max; + + /* only vector 0 can have a suffix length greater than or equal to + * tn->pos + tn->bits, the second highest node will have a suffix + * length at most of tn->pos + tn->bits - 1 + */ + slen_max = min_t(unsigned char, tn->pos + tn->bits - 1, tn->slen); /* search though the list of children looking for nodes that might * have a suffix greater than the one we currently have. This is @@ -698,12 +705,8 @@ static unsigned char update_suffix(struc slen = n->slen; i &= ~(stride - 1); - /* if slen covers all but the last bit we can stop here - * there will be nothing longer than that since only node - * 0 and 1 << (bits - 1) could have that as their suffix - * length. - */ - if ((slen + 1) >= (tn->pos + tn->bits)) + /* stop searching if we have hit the maximum possible value */ + if (slen >= slen_max) break; } @@ -875,21 +878,7 @@ static struct key_vector *resize(struct return collapse(t, tn); /* update parent in case halve failed */ - tp = node_parent(tn); - - /* Return if at least one deflate was run */ - if (max_work != MAX_WORK) - return tp; - - /* push the suffix length to the parent node */ - if (tn->slen > tn->pos) { - unsigned char slen = update_suffix(tn); - - if (slen > tp->slen) - tp->slen = slen; - } - - return tp; + return node_parent(tn); } static void node_pull_suffix(struct key_vector *tn, unsigned char slen) @@ -1030,6 +1019,7 @@ static int fib_insert_node(struct trie * } /* Case 3: n is NULL, and will just insert a new leaf */ + node_push_suffix(tp, new->fa_slen); NODE_INIT_PARENT(l, tp); put_child_root(tp, key, l); trie_rebalance(t, tp); @@ -1472,6 +1462,8 @@ static void fib_remove_alias(struct trie * out parent suffix lengths as a part of trie_rebalance */ if (hlist_empty(&l->leaf)) { + if (tp->slen == l->slen) + node_pull_suffix(tp, tp->pos); put_child_root(tp, l->key, NULL); node_free(l); trie_rebalance(t, tp); @@ -1755,6 +1747,10 @@ void fib_table_flush_external(struct fib if (IS_TRIE(pn)) break; + /* update the suffix to address pulled leaves */ + if (pn->slen > pn->pos) + update_suffix(pn); + /* resize completed node */ pn = resize(t, pn); cindex = get_index(pkey, pn); @@ -1830,6 +1826,10 @@ int fib_table_flush(struct fib_table *tb if (IS_TRIE(pn)) break; + /* update the suffix to address pulled leaves */ + if (pn->slen > pn->pos) + update_suffix(pn); + /* resize completed node */ pn = resize(t, pn); cindex = get_index(pkey, pn);