include/net/ip_fib.h | 5
net/ipv4/Kconfig | 7
net/ipv4/af_inet.c | 4
net/ipv4/fib_hash.c | 43 +--
net/ipv4/fib_lookup.h | 12
net/ipv4/fib_semantics.c | 6
net/ipv4/fib_trie.c | 569 +++++++++++++++++++++++------------------------
7 files changed, 330 insertions(+), 316 deletions(-)
New commits:
commit 1c2b60ccc7ec348b26acf891b3bae064155d70e1
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Mon Feb 11 21:12:49 2008 -0800
fib_trie: handle empty tree
This fixes possible problems when trie_firstleaf() returns NULL
to trie_leafindex().
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit c2f97c50dc2eed5368c686b6227c826e5a47f2c5
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Thu Jan 31 16:45:47 2008 -0800
[IPV4] fib_trie: rescan if key is lost during dump
Normally during a dump the key of the last dumped entry is used for
continuation, but since lock is dropped it might be lost. In that case
fallback to the old counter based N^2 behaviour. This means the dump
will end up skipping some routes which matches what FIB_HASH does.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 18d8cf30206fc9394e27fe37f01acb25b4410497
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Wed Jan 23 20:38:24 2008 -0800
[IPV4] fib_trie: remove unneeded NULL check
Since fib_route_seq_show now uses hlist_for_each_entry(), the leaf
info can not be NULL.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 75a8897bb3933589f93665e13502af8a9d4ba5c6
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Tue Jan 22 21:57:22 2008 -0800
[IPV4] fib_trie: avoid rescan on dump
This converts dumping (and flushing) of large route tables form O(N^2)
to O(N). If the route dump took multiple pages then the dump routine
gets called again. The old code kept track of location by counter, the
new code instead uses the last key.
This is a really big win ( 0.3 sec vs 12 sec) for big route tables.
One side effect is that if the table changes during the dump, then the
last key will not be found, and we will return -EBUSY.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 5c39ab7b2f3d24c852229cb8086e2ad08dc2262a
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Tue Jan 22 21:56:34 2008 -0800
[IPV4] fib_trie: avoid extra search on delete
Get rid of extra search that made route deletion O(n).
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 18f7c42f03154d88177b0124b21b9bc9d81ecbae
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Tue Jan 22 21:56:11 2008 -0800
[IPV4] fib_trie: dump table in sorted order
It is easier with TRIE to dump the data traversal rather than
interating over every possible prefix. This saves some time and makes
the dump come out in sorted order.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit b8a4da8b4dc1259a29b235ffad17eee6b0b00075
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Tue Jan 22 21:55:32 2008 -0800
[IPV4] fib_trie: iterator recode
Remove the complex loop structure of nextleaf() and replace it with a
simpler tree walker. This improves the performance and is much
cleaner.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit a5cbc65543de1219fa13eca8179537916979426e
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Tue Jan 22 21:55:01 2008 -0800
[IPV4] fib_trie: dump message multiple part flag
Match fib_hash, and set NLM_F_MULTI to handle multiple part messages.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit d05b33be7085bf689404c03d48b2140f298c1411
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Tue Jan 22 21:54:05 2008 -0800
[IPV4] fib_trie: compute size when needed
Compute the number of prefixes when needed, rather than doing bookeeping.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit b06ce73052d4fbca5b9e4f189fbf94e50c7cf458
Author: Denis V. Lunev <[EMAIL PROTECTED]>
Date: Thu Jan 10 03:21:09 2008 -0800
[NETNS]: Add namespace to API for routing /proc entries creation.
This adds netns parameter to fib_proc_init/exit and replaces __init
specifier with __net_init. After this, we will not yet have these proc
files show info from the specific namespace - this will be done when
these tables become namespaced.
Acked-by: Benjamin Thery <[EMAIL PROTECTED]>
Acked-by: Daniel Lezcano <[EMAIL PROTECTED]>
Signed-off-by: Denis V. Lunev <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit f19e46863bd10407ffba30d942021d7dff4d8b03
Author: Eric Dumazet <[EMAIL PROTECTED]>
Date: Fri Jan 18 03:31:36 2008 -0800
[FIB]: Fix rcu_dereference() abuses in fib_trie.c
node_parent() and tnode_get_child() currently use rcu_dereference().
These functions are called from both
- readers only paths (where rcu_dereference() is needed), and
- writer path (where rcu_dereference() is not needed)
To make explicit where rcu_dereference() is really needed, I
introduced new node_parent_rcu() and tnode_get_child_rcu() functions
which use rcu_dereference(), while node_parent() and tnode_get_child()
dont use it.
Then I changed calling sites where rcu_dereference() was really needed
to call the _rcu() variants.
This should have no impact but for alpha architecture, and may help
future sparse checks.
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 98f72042becd6df269a13bc79930aa2a90dc6f9c
Author: Eric Dumazet <[EMAIL PROTECTED]>
Date: Mon Jan 14 23:09:56 2008 -0800
[FIB]: Avoid using static variables without proper locking
fib_trie_seq_show() uses two helper functions, rtn_scope() and
rtn_type() that can write to static storage without locking.
Just pass to them a temporary buffer to avoid potential corruption
(probably not triggerable but still...)
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 0f41432e9b32d9dc49d5044466bc95580d5dfe02
Author: Eric Dumazet <[EMAIL PROTECTED]>
Date: Sun Jan 13 22:31:44 2008 -0800
[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 <[EMAIL PROTECTED]>
Signed-off-by: Robert Olsson <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 068c91ff5b3375875f8dddd16ff2e1490c7c9488
Author: Eric Dumazet <[EMAIL PROTECTED]>
Date: Sun Jan 13 00:43:22 2008 -0800
[IPV4] fib_trie: removes a memset() call in tnode_new()
tnode_alloc() already clears allocated memory, using kcalloc() or
alloc_pages(GFP_KERNEL|__GFP_ZERO, ...)
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 959ad4935fde65573e345d4a08fe0f2740b0d592
Author: Eric Dumazet <[EMAIL PROTECTED]>
Date: Sat Jan 12 21:27:41 2008 -0800
[FIB]: Reduce text size of net/ipv4/fib_trie.o
In struct tnode, we use two fields of 5 bits for 'pos' and 'bits'.
Switching to plain 'unsigned char' (8 bits) take the same space
because of compiler alignments, and reduce text size by 435 bytes
on i386.
On i386 :
$ size net/ipv4/fib_trie.o.before_patch net/ipv4/fib_trie.o
text data bss dec hex filename
13714 4 64 13782 35d6 net/ipv4/fib_trie.o.before
13279 4 64 13347 3423 net/ipv4/fib_trie.o
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
Acked-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 616b915196ade8750b418b80ec3036da8167b8d5
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Sat Jan 12 21:25:02 2008 -0800
[IPV4] fib_trie: Fix sparse warnings.
Make FIB TRIE go through sparse checker without warnings.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 6ae1a7af3e35696f6a79420c28078fc7ee983240
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Sat Jan 12 21:23:17 2008 -0800
[IPV4] fib_trie: Add statistics.
The FIB TRIE code has a bunch of statistics, but the code is hidden
behind an ifdef that was never implemented. Since it was dead code, it
was broken as well.
This patch fixes that by making it a config option.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit ff9edd22ef047d70dacd32d8e646ffce29f4c371
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Sat Jan 12 20:57:07 2008 -0800
[IPV4] fib_trie: fib_insert_node cleanup
The only error from fib_insert_node is if memory allocation fails, so
instead of passing by reference, just use the convention of returning
NULL.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 5d144b69dc9b3ed220020352c49ffa35a2f9b30a
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Sat Jan 12 20:55:55 2008 -0800
[IPV4] fib_trie: Use %u for unsigned printfs.
Use %u instead of %d when printing unsigned values.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 836bfe30ae9c61dd16e782800bcc14f2f6f5c410
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Sat Jan 12 20:50:23 2008 -0800
[IPV4] fib_trie: Get rid of unused revision element.
The revision element must of been part of an earlier design, because
currently it is set but never used.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 0bce9875722013622b390c701d65a11b7159a675
Author: Denis V. Lunev <[EMAIL PROTECTED]>
Date: Sat Dec 8 00:32:23 2007 -0800
[IPV4]: last default route is a fib table property
Signed-off-by: Denis V. Lunev <[EMAIL PROTECTED]>
Acked-by: Alexey Kuznetsov <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 0f98bb782f67c0d5fca763abadab868845c80544
Author: Denis V. Lunev <[EMAIL PROTECTED]>
Date: Sat Dec 8 00:31:44 2007 -0800
[IPV4]: Unify assignment of fi to fib_result
Signed-off-by: Denis V. Lunev <[EMAIL PROTECTED]>
Acked-by: Alexey Kuznetsov <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit ca59b6ddb69c5afad714ca4919d746a79b67adaf
Author: Denis V. Lunev <[EMAIL PROTECTED]>
Date: Sat Dec 8 00:22:13 2007 -0800
[IPV4]: no need pass pointer to a default into fib_detect_death
ipv4: no need pass pointer to a default into fib_detect_death
Signed-off-by: Denis V. Lunev <[EMAIL PROTECTED]>
Acked-by: Alexey Kuznetsov <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 512323116c68ab9f9d6f6769aca417de3c017374
Author: Eric W. Biederman <[EMAIL PROTECTED]>
Date: Fri Dec 7 00:47:47 2007 -0800
[IPV4]: Move trie_local and trie_main into the proc iterator.
We only use these variables when displaying the trie in proc so
place them into the iterator to make this explicit. We should
probably do something smarter to handle the CONFIG_IP_MULTIPLE_TABLES
case but at least this makes it clear that the silliness is limited
to the display in /proc.
Signed-off-by: Eric W. Biederman <[EMAIL PROTECTED]>
Signed-off-by: Denis V. Lunev <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit 71aa5b3ec7da1668892f17447e6c549fdfb53093
Author: Denis V. Lunev <[EMAIL PROTECTED]>
Date: Thu Dec 13 09:47:57 2007 -0800
[IPV4]: Thresholds in fib_trie.c are used as consts, so make them const.
There are several thresholds for trie fib hash management. They are used
in the code as a constants. Make them constants from the compiler point of
view.
Signed-off-by: Denis V. Lunev <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
commit a9290b81c5fd3c2c665663e75c9b8c31f326e9ec
Author: Stephen Hemminger <[EMAIL PROTECTED]>
Date: Sat Jan 12 20:49:13 2008 -0800
[IPV4] fib_trie: Get rid of trie_init().
trie_init is worthless it is just zeroing stuff that is already zero!
Move the memset() down to make it obvious.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=1c2b60ccc7ec348b26acf891b3bae064155d70e1
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=c2f97c50dc2eed5368c686b6227c826e5a47f2c5
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=18d8cf30206fc9394e27fe37f01acb25b4410497
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=75a8897bb3933589f93665e13502af8a9d4ba5c6
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=5c39ab7b2f3d24c852229cb8086e2ad08dc2262a
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=18f7c42f03154d88177b0124b21b9bc9d81ecbae
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=b8a4da8b4dc1259a29b235ffad17eee6b0b00075
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=a5cbc65543de1219fa13eca8179537916979426e
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=d05b33be7085bf689404c03d48b2140f298c1411
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=b06ce73052d4fbca5b9e4f189fbf94e50c7cf458
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=f19e46863bd10407ffba30d942021d7dff4d8b03
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=98f72042becd6df269a13bc79930aa2a90dc6f9c
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=0f41432e9b32d9dc49d5044466bc95580d5dfe02
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=068c91ff5b3375875f8dddd16ff2e1490c7c9488
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=959ad4935fde65573e345d4a08fe0f2740b0d592
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=616b915196ade8750b418b80ec3036da8167b8d5
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=6ae1a7af3e35696f6a79420c28078fc7ee983240
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=ff9edd22ef047d70dacd32d8e646ffce29f4c371
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=5d144b69dc9b3ed220020352c49ffa35a2f9b30a
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=836bfe30ae9c61dd16e782800bcc14f2f6f5c410
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=0bce9875722013622b390c701d65a11b7159a675
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=0f98bb782f67c0d5fca763abadab868845c80544
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=ca59b6ddb69c5afad714ca4919d746a79b67adaf
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=512323116c68ab9f9d6f6769aca417de3c017374
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=71aa5b3ec7da1668892f17447e6c549fdfb53093
http://suva.vyatta.com/git/?p=linux-vyatta.git;a=commitdiff;h=a9290b81c5fd3c2c665663e75c9b8c31f326e9ec
_______________________________________________
svn mailing list
[email protected]
http://mailman.vyatta.com/mailman/listinfo/svn
