From patchwork Mon Jun 15 06:53:33 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jarek Poplawski X-Patchwork-Id: 28690 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@bilbo.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from ozlabs.org (ozlabs.org [203.10.76.45]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "mx.ozlabs.org", Issuer "CA Cert Signing Authority" (verified OK)) by bilbo.ozlabs.org (Postfix) with ESMTPS id 2F74DB713B for ; Mon, 15 Jun 2009 16:54:20 +1000 (EST) Received: by ozlabs.org (Postfix) id 21FB5DDD1C; Mon, 15 Jun 2009 16:54:20 +1000 (EST) Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id 8EF0FDDD04 for ; Mon, 15 Jun 2009 16:54:19 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751979AbZFOGxk (ORCPT ); Mon, 15 Jun 2009 02:53:40 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1751992AbZFOGxj (ORCPT ); Mon, 15 Jun 2009 02:53:39 -0400 Received: from mail-fx0-f206.google.com ([209.85.220.206]:62971 "EHLO mail-fx0-f206.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751552AbZFOGxi (ORCPT ); Mon, 15 Jun 2009 02:53:38 -0400 Received: by fxm2 with SMTP id 2so67202fxm.37 for ; Sun, 14 Jun 2009 23:53:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:date:from:to:cc:subject :message-id:mime-version:content-type:content-disposition :in-reply-to:user-agent; bh=21FnnY3l7CFEZgJjUGsDrMEcFWBbbhTlzi+DHwMu77k=; b=pIdRI+Ff3ncYJxawM1JYZiBRRnJCugc4howEJAmX866JXXeRIV03lhbHNRUzx7qiKN b8dITWtF1HJNQp4/D2RdvDcfboM2S0Kd5K80GdQ9pJAYVK8czlkWeQNQK7Fv4jwaeYkE K1WHBd9dXi5tXmF3xL7ZS+i+DpddNoexVm7qw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=date:from:to:cc:subject:message-id:mime-version:content-type :content-disposition:in-reply-to:user-agent; b=tj7At95arrMM0XwJ7V696Sc28yb1RPOimqQK7dnhC583bi4ynuUZICJvazG7AKayzh /JEyMW6BVduZ0gz9x+m9RdpxQXXUj0imP09M1jKKtYRPHxAAvGe8Zlnyv9ycrNmX/I5K s2c3mmBiTOK6QtaXS18le8H4fGdsk1SxZg3rg= Received: by 10.204.31.207 with SMTP id z15mr6703903bkc.63.1245048819575; Sun, 14 Jun 2009 23:53:39 -0700 (PDT) Received: from ff.dom.local (bv170.internetdsl.tpnet.pl [80.53.205.170]) by mx.google.com with ESMTPS id g28sm7076968fkg.15.2009.06.14.23.53.36 (version=SSLv3 cipher=RC4-MD5); Sun, 14 Jun 2009 23:53:38 -0700 (PDT) Date: Mon, 15 Jun 2009 06:53:33 +0000 From: Jarek Poplawski To: David Miller Cc: Robert Olsson , Yan Zheng , linux-kernel@vger.kernel.org, netdev@vger.kernel.org Subject: [PATCH] Re: [BUG] fib_tries related Oops in 2.6.30 Message-ID: <20090615065333.GA4378@ff.dom.local> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20090612072557.GA2761@ami.dom.local> User-Agent: Mutt/1.5.18 (2008-05-17) Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org On 12-06-2009 09:25, Jarek Poplawski wrote: > Jarek Poplawski wrote, On 06/11/2009 04:39 PM: > >> Cc Robert Olsson. >> >> Jarek P. >> >> Yan Zheng wrote, On 06/10/2009 06:05 PM: >> >>> Hello, >>> >>> I pull linux-2.6.30 from linus-2.6 git tree. I got following oops >>> immediately after boot. >>> >>> # uname -a >>> Linux zhyan-cn 2.6.30 #1 SMP PREEMPT Wed Jun 10 23:37:22 CST 2009 i686 >>> i686 i386 GNU/Linux >>> >>> --- >>> BUG: sleeping function called from invalid context at > ... > > Robert, probably I miss something, but since I don't understand this > last patch with preempt_disable(), I've looked a bit at this place and > found this parent update after IMHO possible child destruction quite > suspicious, so I wonder if you could check if this patch could change > anything with previous oops. (It's mainly to test the idea, not to > optimally fix it.) Since I'm not sure Robert is working on this, here is a patch which I guess should fix this issue more optimally. Alas, until it's tested by somebody, I can recommend it only for net-next. Jarek P. -------------------------> ipv4: Fix fib_trie rebalancing While doing trie_rebalance(): resize(), inflate(), halve() RCU free tnodes before updating their parents. It depends on RCU delaying the real destruction, but if RCU readers start after call_rcu() and before parent update they could access freed memory. It is currently prevented with preempt_disable() on the update side, but it's not safe, except maybe classic RCU, plus it conflicts with memory allocations with GFP_KERNEL flag used from these functions. This patch explicitly delays freeing of tnodes by adding them to the list, which is flushed after the update is finished. Reported-by: Yan Zheng Signed-off-by: Jarek Poplawski --- net/ipv4/fib_trie.c | 47 +++++++++++++++++++++++++++++++++++++---------- 1 files changed, 37 insertions(+), 10 deletions(-) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 538d2a9..d1a39b1 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -123,6 +123,7 @@ struct tnode { union { struct rcu_head rcu; struct work_struct work; + struct tnode *tnode_free; }; struct node *child[0]; }; @@ -161,6 +162,8 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, static struct node *resize(struct trie *t, struct tnode *tn); static struct tnode *inflate(struct trie *t, struct tnode *tn); static struct tnode *halve(struct trie *t, struct tnode *tn); +/* tnodes to free after resize(); protected by RTNL */ +static struct tnode *tnode_free_head; static struct kmem_cache *fn_alias_kmem __read_mostly; static struct kmem_cache *trie_leaf_kmem __read_mostly; @@ -385,6 +388,29 @@ static inline void tnode_free(struct tnode *tn) call_rcu(&tn->rcu, __tnode_free_rcu); } +static void tnode_free_safe(struct tnode *tn) +{ + BUG_ON(IS_LEAF(tn)); + + if (node_parent((struct node *) tn)) { + tn->tnode_free = tnode_free_head; + tnode_free_head = tn; + } else { + tnode_free(tn); + } +} + +static void tnode_free_flush(void) +{ + struct tnode *tn; + + while ((tn = tnode_free_head)) { + tnode_free_head = tn->tnode_free; + tn->tnode_free = NULL; + tnode_free(tn); + } +} + static struct leaf *leaf_new(void) { struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL); @@ -495,7 +521,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) /* No children */ if (tn->empty_children == tnode_child_length(tn)) { - tnode_free(tn); + tnode_free_safe(tn); return NULL; } /* One child */ @@ -509,7 +535,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) /* compress one level */ node_set_parent(n, NULL); - tnode_free(tn); + tnode_free_safe(tn); return n; } /* @@ -670,7 +696,7 @@ static struct node *resize(struct trie *t, struct tnode *tn) /* compress one level */ node_set_parent(n, NULL); - tnode_free(tn); + tnode_free_safe(tn); return n; } @@ -756,7 +782,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn) put_child(t, tn, 2*i, inode->child[0]); put_child(t, tn, 2*i+1, inode->child[1]); - tnode_free(inode); + tnode_free_safe(inode); continue; } @@ -801,9 +827,9 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn) put_child(t, tn, 2*i, resize(t, left)); put_child(t, tn, 2*i+1, resize(t, right)); - tnode_free(inode); + tnode_free_safe(inode); } - tnode_free(oldtnode); + tnode_free_safe(oldtnode); return tn; nomem: { @@ -885,7 +911,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn) put_child(t, newBinNode, 1, right); put_child(t, tn, i/2, resize(t, newBinNode)); } - tnode_free(oldtnode); + tnode_free_safe(oldtnode); return tn; nomem: { @@ -989,7 +1015,6 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn) t_key cindex, key; struct tnode *tp; - preempt_disable(); key = tn->key; while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) { @@ -1001,16 +1026,18 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn) (struct node *)tn, wasfull); tp = node_parent((struct node *) tn); + tnode_free_flush(); if (!tp) break; tn = tp; } /* Handle last (top) tnode */ - if (IS_TNODE(tn)) + if (IS_TNODE(tn)) { tn = (struct tnode *)resize(t, (struct tnode *)tn); + tnode_free_flush(); + } - preempt_enable(); return (struct node *)tn; }