netdev - [FIB]: full_children & empty_children should be uint, not ushort

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <18314.35427.947982.424287@robur.slu.se>
Date:	Sun, 13 Jan 2008 23:02:11 +0100
From:	Robert Olsson <Robert.Olsson@...a.slu.se>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	David Miller <davem@...emloft.net>,
	Stephen Hemminger <stephen.hemminger@...tta.com>,
	Robert Olsson <robert.olsson@....uu.se>, netdev@...r.kernel.org
Subject: [FIB]: full_children & empty_children should be uint, not ushort


Eric Dumazet writes:
 > Eric Dumazet a écrit :
 > > 4) full_children & empty_children being 'unsigned short',
 > >    we probably are limited to 2^15 elements, but I could not
 > >    find this limit enforced somewhere.

 > Two fixes are possible : Enlarge full_children & empty_children to 32bits, or 
 > force a limit in code to never exceed 2^15 children in a tnode. I chose the 
 > first solution since it can be done with 0 memory cost on 64bit arches.

 Hello,

 Thanks for spotting this. No we don't want put limits on the (root) node size.
 You see the comment in code is correct so unsigned short are some leftover from 
 old testing which could have hit us hard as the routing table slowly grows.

 Cheers
						--ro


Signed-off-by: Robert Olsson <robert.olsson@....uu.se>
 

 > [FIB]: full_children & empty_children should be uint, not ushort
 > 
 > If declared as unsigned short, these fields can overflow, and whole trie logic
 > is broken. I could not make the machine crash, but some tnode can never
 > be freed.
 > 
 > Note for 64 bit arches : By reordering t_key and parent in [node, leaf, tnode] 
 > structures, we can use 32 bits hole after t_key so that sizeof(struct tnode) 
 > doesnt change after this patch.
 > 
 > Signed-off-by: Eric Dumazet <dada1@...mosbay.com>
 > 
 > diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
 > index f26ba31..9696722 100644
 > --- a/net/ipv4/fib_trie.c
 > +++ b/net/ipv4/fib_trie.c
 > @@ -97,13 +97,13 @@ typedef unsigned int t_key;
 >  #define IS_LEAF(n) (n->parent & T_LEAF)
 >  
 >  struct node {
 > -	t_key key;
 >  	unsigned long parent;
 > +	t_key key;
 >  };
 >  
 >  struct leaf {
 > -	t_key key;
 >  	unsigned long parent;
 > +	t_key key;
 >  	struct hlist_head list;
 >  	struct rcu_head rcu;
 >  };
 > @@ -116,12 +116,12 @@ struct leaf_info {
 >  };
 >  
 >  struct tnode {
 > -	t_key key;
 >  	unsigned long parent;
 > +	t_key key;
 >  	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
 >  	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
 > -	unsigned short full_children;	/* KEYLENGTH bits needed */
 > -	unsigned short empty_children;	/* KEYLENGTH bits needed */
 > +	unsigned int full_children;	/* KEYLENGTH bits needed */
 > +	unsigned int empty_children;	/* KEYLENGTH bits needed */
 >  	struct rcu_head rcu;
 >  	struct node *child[0];
 >  };
 > @@ -329,12 +329,12 @@ static inline void free_leaf_info(struct leaf_info *leaf)
 >  	call_rcu(&leaf->rcu, __leaf_info_free_rcu);
 >  }
 >  
 > -static struct tnode *tnode_alloc(unsigned int size)
 > +static struct tnode *tnode_alloc(size_t size)
 >  {
 >  	struct page *pages;
 >  
 >  	if (size <= PAGE_SIZE)
 > -		return kcalloc(size, 1, GFP_KERNEL);
 > +		return kzalloc(size, GFP_KERNEL);
 >  
 >  	pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
 >  	if (!pages)
 > @@ -346,8 +346,8 @@ static struct tnode *tnode_alloc(unsigned int size)
 >  static void __tnode_free_rcu(struct rcu_head *head)
 >  {
 >  	struct tnode *tn = container_of(head, struct tnode, rcu);
 > -	unsigned int size = sizeof(struct tnode) +
 > -		(1 << tn->bits) * sizeof(struct node *);
 > +	size_t size = sizeof(struct tnode) +
 > +		      (sizeof(struct node *) << tn->bits);
 >  
 >  	if (size <= PAGE_SIZE)
 >  		kfree(tn);
 > @@ -386,8 +386,7 @@ static struct leaf_info *leaf_info_new(int plen)
 >  
 >  static struct tnode* tnode_new(t_key key, int pos, int bits)
 >  {
 > -	int nchildren = 1<<bits;
 > -	int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
 > +	size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
 >  	struct tnode *tn = tnode_alloc(sz);
 >  
 >  	if (tn) {
 > @@ -399,8 +398,8 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
 >  		tn->empty_children = 1<<bits;
 >  	}
 >  
 > -	pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
 > -		 (unsigned int) (sizeof(struct node) * 1<<bits));
 > +	pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
 > +		 (unsigned long) (sizeof(struct node) << bits));
 >  	return tn;
 >  }
 >  
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html