summaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c
Commit message (Collapse)AuthorAgeFilesLines
* [IPV4] fib_trie: build fixStephen Hemminger2006-01-031-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>
* [IPV4] fib_trie: Add credits.Robert Olsson2006-01-031-0/+7
| | | | | Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
* [FIB_TRIE]: Don't show local table in /proc/net/route outputPatrick McHardy2005-11-201-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>
* [IPV4]: Kill redundant rcu_dereference on fa_infoHerbert Xu2005-10-261-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>
* [IPV4]: fib_trie root-node expansionRobert Olsson2005-10-041-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>
* [FIB_TRIE]: message cleanupStephen Hemminger2005-09-211-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>
* [IPV4]: fib_trie RCU refinementsRobert Olsson2005-09-191-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>
* [IPV4]: fib_trie tnode stats refinementsRobert Olsson2005-09-191-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>
* [IPV4] fib_trie: fix proc interfaceStephen Hemminger2005-09-091-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>
* [NET]: use __read_mostly on kmem_cache_t , DEFINE_SNMP_STAT pointersEric Dumazet2005-08-291-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>
* [IPV4]: Convert FIB Trie to RCU.Robert Olsson2005-08-291-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>
* [IPV4]: FIB trie cleanupStephen Hemminger2005-08-291-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>
* [IPV4]: fib_trie: Use constStephen Hemmigner2005-08-291-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>
* [IPV4]: fib_trie: Use ERR_PTR to handle errno returnRobert Olsson2005-08-291-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>
* [IPV4]: FIB Trie cleanups.Olof Johansson2005-08-291-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>
* [FIB_TRIE]: Don't ignore negative results from fib_semantic_matchPatrick McHardy2005-08-231-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>
* [IPV4]: Fix up lots of little whitespace indentation stuff in fib_trie.Stephen Hemminger2005-07-191-385/+387
| | | | | Signed-off-by: Stephen Hemminger <shemminger@osdl.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4]: More broken memory allocation fixes for fib_trieRobert Olsson2005-07-051-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>
* [IPV4]: Handle large allocations in fib_triePatrick McHardy2005-07-051-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>
* [IPV4]: Broken memory allocation in fib_trieRobert Olsson2005-06-281-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>
* [IPV4]: Fix fib_trie.c's args to fib_dump_info().David S. Miller2005-06-211-1/+1
| | | | Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4]: Add LC-Trie FIB lookup algorithm.Robert Olsson2005-06-211-0/+2454
Signed-off-by: Robert Olsson <Robert.Olsson@data.slu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
OpenPOWER on IntegriCloud