* This patch is from Paul McKenney's RCU reviewing. 
Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

* Prints the route tnode and set the stats level deepth as before.
Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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=5209Signed-off-by: NStephen Hemminger <shemminger@osdl.org>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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: NEric Dumazet <dada1@cosmosbay.com>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

* 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: NRobert Olsson <Robert.Olsson@data.slu.se>
Signed-off-by: NStephen Hemminger <shemminger@osdl.org>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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: NStephen Hemminger <shemminger@osdl.org>
Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Use const where possible and get rid of EXTRACT() macro
that was never used.
Signed-off-by: NStephen Hemmigner <shemminger@osdl.org>
Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NStephen Hemminger <shemminger@osdl.org>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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: NOlof Johansson <olof@lixom.net>
Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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: NPatrick McHardy <kaber@trash.net>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Signed-off-by: NStephen Hemminger <shemminger@osdl.org>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

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: NPatrick McHardy <kaber@trash.net>
Acked-by: NRobert Olsson <Robert.Olsson@data.slu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

This should help up the insertion... but the resize is more crucial.
and complex and needs some thinking. 
Signed-off-by: NRobert Olsson <robert.olsson@its.uu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Signed-off-by: NDavid S. Miller <davem@davemloft.net>

Signed-off-by: NRobert Olsson <Robert.Olsson@data.slu.se>
Signed-off-by: NDavid S. Miller <davem@davemloft.net>