aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c (follow)
AgeCommit message (Collapse)AuthorFilesLines
2006-04-09[FIB_TRIE]: Fix leaf freeing.Robert Olsson1-7/+7
Seems like leaf (end-nodes) has been freed by __tnode_free_rcu and not by __leaf_free_rcu. This fixes the problem. Only tnode_free is now used which checks for appropriate node type. free_leaf can be removed. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-03-20[IPV4]: fib_trie stats fixRobert Olsson1-6/+8
fib_triestats has been buggy and caused oopses some platforms as openwrt. The patch below should cure those problems. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-03-20[IPV4]: fib_trie initialzation fixRobert Olsson1-2/+10
In some kernel configs /proc functions seems to be accessed before the trie is initialized. The patch below checks for this. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-01-03[IPV4] fib_trie: build fixStephen Hemminger1-0/+1
Need this to fix build of fib_trie in net-2.6.16 (rebased) tree. The code needs the new inet_make_mask inline. Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-01-03[IPV4] fib_trie: Add credits.Robert Olsson1-0/+7
Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-11-20[FIB_TRIE]: Don't show local table in /proc/net/route outputPatrick McHardy1-0/+3
Don't show local table to behave similar to fib_hash. Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-10-26[IPV4]: Kill redundant rcu_dereference on fa_infoHerbert Xu1-1/+1
This patch kills a redundant rcu_dereference on fa->fa_info in fib_trie.c. As this dereference directly follows a list_for_each_entry_rcu line, we have already taken a read barrier with respect to getting an entry from the list. This read barrier guarantees that all values read out of fa are valid. In particular, the contents of structure pointed to by fa->fa_info is initialised before fa->fa_info is actually set (see fn_trie_insert); the setting of fa->fa_info itself is further separated with a write barrier from the insertion of fa into the list. Therefore by taking a read barrier after obtaining fa from the list (which is given by list_for_each_entry_rcu), we can be sure that fa->fa_info contains a valid pointer, as well as the fact that the data pointed to by fa->fa_info is itself valid. Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au> Acked-by: Paul E. McKenney <paulmck@us.ibm.com> Signed-off-by: David S. Miller <davem@davemloft.net> Signed-off-by: Arnaldo Carvalho de Melo <acme@mandriva.com>
2005-10-04[IPV4]: fib_trie root-node expansionRobert Olsson1-2/+21
The patch below introduces special thresholds to keep root node in the trie large. This gives a flatter tree at the cost of a modest memory increase. Overall it seems to be gain and this was also proposed by one the authors of the paper in recent a seminar. Main table after loading 123 k routes. Aver depth: 3.30 Max depth: 9 Root-node size 12 bits Total size: 4044 kB With the patch: Aver depth: 2.78 Max depth: 8 Root-node size 15 bits Total size: 4150 kB An increase of 8-10% was seen in forwading performance for an rDoS attack. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-09-21[FIB_TRIE]: message cleanupStephen Hemminger1-12/+3
Cleanup the printk's in fib_trie: * Convert a couple of places in the dump code to BUG_ON * Put log level's on each message The version message really needed the message since it leaks out on the pretty Fedora bootup. Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Acked-by: Robert Olsson <Robert.Olsson@data.slu.se>, Signed-off-by: David S. Miller <davem@davemloft.net>
2005-09-19[IPV4]: fib_trie RCU refinementsRobert Olsson1-11/+10
* This patch is from Paul McKenney's RCU reviewing. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-09-19[IPV4]: fib_trie tnode stats refinementsRobert Olsson1-6/+7
* Prints the route tnode and set the stats level deepth as before. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-09-09[IPV4] fib_trie: fix proc interfaceStephen Hemminger1-419/+385
Create one iterator for walking over FIB trie, and use it for all the /proc functions. Add a /proc/net/route output for backwards compatibility with old applications. Make initialization of fib_trie same as fib_hash so no #ifdef is needed in af_inet.c Fixes: http://bugzilla.kernel.org/show_bug.cgi?id=5209 Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-29[NET]: use __read_mostly on kmem_cache_t , DEFINE_SNMP_STAT pointersEric Dumazet1-1/+1
This patch puts mostly read only data in the right section (read_mostly), to help sharing of these data between CPUS without memory ping pongs. On one of my production machine, tcp_statistics was sitting in a heavily modified cache line, so *every* SNMP update had to force a reload. Signed-off-by: Eric Dumazet <dada1@cosmosbay.com> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-29[IPV4]: Convert FIB Trie to RCU.Robert Olsson1-187/+202
* Removes RW-lock * Proteced read functions uses rcu_dereference proteced with rcu_read_lock() * writing of procted pointer w. rcu_assigen_pointer * Insert/Replace atomic list_replace_rcu * A BUG_ON condition removed.in trie_rebalance With help from Paul E. McKenney. Signed-off-by: Robert Olsson <Robert.Olsson@data.slu.se> Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-29[IPV4]: FIB trie cleanupStephen Hemminger1-69/+31
This is a redo of earlier cleanup stuff: * replace DBG() macro with pr_debug() * get rid of duplicate extern's that are already in fib_lookup.h * use BUG_ON and WARN_ON * don't use BUG checks for null pointers where next statement would get a fault anyway * remove debug printout when rebalance causes deep tree * remove trailing blanks Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-29[IPV4]: fib_trie: Use constStephen Hemmigner1-5/+2
Use const where possible and get rid of EXTRACT() macro that was never used. Signed-off-by: Stephen Hemmigner <shemminger@osdl.org> Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-29[IPV4]: fib_trie: Use ERR_PTR to handle errno returnRobert Olsson1-62/+57
Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-29[IPV4]: FIB Trie cleanups.Olof Johansson1-645/+592
Below is a patch that cleans up some of this, supposedly without changing any behaviour: * Whitespace cleanups * Introduce DBG() * BUG_ON() instead of if () { BUG(); } * Remove some of the deep nesting to make the code flow more comprehensible * Some mask operations were simplified Signed-off-by: Olof Johansson <olof@lixom.net> Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-08-23[FIB_TRIE]: Don't ignore negative results from fib_semantic_matchPatrick McHardy1-7/+7
When a semantic match occurs either success, not found or an error (for matching unreachable routes/blackholes) is returned. fib_trie ignores the errors and looks for a different matching route. Treat results other than "no match" as success and end lookup. Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-07-19[IPV4]: Fix up lots of little whitespace indentation stuff in fib_trie.Stephen Hemminger1-385/+387
Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-07-05[IPV4]: More broken memory allocation fixes for fib_trieRobert Olsson1-32/+145
Below a patch to preallocate memory when doing resize of trie (inflate halve) If preallocations fails it just skips the resize of this tnode for this time. The oops we got when killing bgpd (with full routing) is now gone. Patrick memory patch is also used. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-07-05[IPV4]: Handle large allocations in fib_triePatrick McHardy1-2/+23
Inflating a node a couple of times makes it exceed the 128k kmalloc limit. Use __get_free_pages for allocations > PAGE_SIZE, as in fib_hash. Signed-off-by: Patrick McHardy <kaber@trash.net> Acked-by: Robert Olsson <Robert.Olsson@data.slu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-06-28[IPV4]: Broken memory allocation in fib_trieRobert Olsson1-17/+39
This should help up the insertion... but the resize is more crucial. and complex and needs some thinking. Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
2005-06-21[IPV4]: Fix fib_trie.c's args to fib_dump_info().David S. Miller1-1/+1
Signed-off-by: David S. Miller <davem@davemloft.net>
2005-06-21[IPV4]: Add LC-Trie FIB lookup algorithm.Robert Olsson1-0/+2454
Signed-off-by: Robert Olsson <Robert.Olsson@data.slu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.