aboutsummaryrefslogtreecommitdiff
path: root/net/ipv4/fib_trie.c
AgeCommit message (Collapse)Author
2006-09-28[IPV4] fib_trie.c: trivial annotationsAl Viro
Signed-off-by: Al Viro <viro@zeniv.linux.org.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-09-22[IPv4]: Convert FIB dumping to use new netlink apiThomas Graf
Signed-off-by: Thomas Graf <tgraf@suug.ch> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-09-22[IPv4]: FIB configuration using struct fib_configThomas Graf
Introduces struct fib_config replacing the ugly struct kern_rta prone to ordering issues. Avoids creating faked netlink messages for auto generated routes or requests via ioctl. A new interface net/nexthop.h is added to help navigate through nexthop configuration arrays. A new struct nl_info will be used to carry the necessary netlink information to be used for notifications later on. Signed-off-by: Thomas Graf <tgraf@suug.ch> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-09-22[IPV4]: Increase number of possible routing tables to 2^32Patrick McHardy
Increase the number of possible routing tables to 2^32 by replacing the fixed sized array of pointers by a hash table and replacing iterations over all possible table IDs by hash table walking. Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-09-22[NET]: Use u32 for routing table IDsPatrick McHardy
Use u32 for routing table IDs in net/ipv4 and net/decnet in preparation of support for a larger number of routing tables. net/ipv6 already uses u32 everywhere and needs no further changes. No functional changes are made by this patch. Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-09-19[IPV4] fib_trie: missing ntohl() when calling fib_semantic_match()Al Viro
fib_trie.c::check_leaf() passes host-endian where fib_semantic_match() expects (and stores into) net-endian. Signed-off-by: Al Viro <viro@zeniv.linux.org.uk> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-07-12[IPV4]: Fix error handling for fib_insert_node callHerbert Xu
The error handling around fib_insert_node was broken because we always zeroed the error before checking it. Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au> Signed-off-by: David S. Miller <davem@davemloft.net>
2006-06-30Remove obsolete #include <linux/config.h>Jörn Engel
Signed-off-by: Jörn Engel <joern@wohnheim.fh-wedel.de> Signed-off-by: Adrian Bunk <bunk@stusta.de>
2006-04-09[FIB_TRIE]: Fix leaf freeing.Robert Olsson
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 Olsson
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 Olsson
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 Hemminger
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 Olsson
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 McHardy
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 Xu
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 Olsson
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 Hemminger
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 Olsson
* 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 Olsson
* 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 Hemminger
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 Dumazet
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 Olsson
* 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 Hemminger
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 Hemmigner
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 Olsson
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 Johansson
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 McHardy
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 Hemminger
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 Olsson
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 McHardy
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 Olsson
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. Miller
Signed-off-by: David S. Miller <davem@davemloft.net>
2005-06-21[IPV4]: Add LC-Trie FIB lookup algorithm.Robert Olsson
Signed-off-by: Robert Olsson <Robert.Olsson@data.slu.se> Signed-off-by: David S. Miller <davem@davemloft.net>