summaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c
Commit message (Collapse)AuthorAgeFilesLines
* ipv4: Fix fib_trie rebalancingJarek Poplawski2009-06-151-10/+37
| | | | | | | | | | | | | | | | | | While doing trie_rebalance(): resize(), inflate(), halve() RCU free tnodes before updating their parents. It depends on RCU delaying the real destruction, but if RCU readers start after call_rcu() and before parent update they could access freed memory. It is currently prevented with preempt_disable() on the update side, but it's not safe, except maybe classic RCU, plus it conflicts with memory allocations with GFP_KERNEL flag used from these functions. This patch explicitly delays freeing of tnodes by adding them to the list, which is flushed after the update is finished. Reported-by: Yan Zheng <zheng.yan@oracle.com> Signed-off-by: Jarek Poplawski <jarkao2@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* Merge branch 'master' of ↵David S. Miller2009-05-251-1/+5
|\ | | | | | | | | | | | | | | | | master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6 Conflicts: drivers/net/wireless/ath/ath5k/phy.c drivers/net/wireless/iwlwifi/iwl-agn.c drivers/net/wireless/iwlwifi/iwl3945-base.c
| * ipv4: Fix oops with FIB_TRIERobert Olsson2009-05-211-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | It seems we can fix this by disabling preemption while we re-balance the trie. This is with the CONFIG_CLASSIC_RCU. It's been stress-tested at high loads continuesly taking a full BGP table up/down via iproute -batch. Note. fib_trie is not updated for CONFIG_PREEMPT_RCU Reported-by: Andrei Popa Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
* | ipv4: cleanup - remove two unused parameters from fib_semantic_match().Rami Rosen2009-05-181-2/+1
|/ | | | | Signed-off-by: Rami Rosen <ramirose@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* net: replace NIPQUAD() in net/ipv4/ net/ipv6/Harvey Harrison2008-10-311-3/+3
| | | | | | | | Using NIPQUAD() with NIPQUAD_FMT, %d.%d.%d.%d or %u.%u.%u.%u can be replaced with %pI4 Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* proc: consolidate per-net single-release callersPavel Emelyanov2008-07-181-8/+1
| | | | | | | They are symmetrical to single_open ones :) Signed-off-by: Pavel Emelyanov <xemul@openvz.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* proc: consolidate per-net single_open callersPavel Emelyanov2008-07-181-12/+1
| | | | | | | There are already 7 of them - time to kill some duplicate code. Signed-off-by: Pavel Emelyanov <xemul@openvz.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* Merge branch 'master' of ↵David S. Miller2008-07-141-11/+6
|\ | | | | | | | | | | | | | | master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6 Conflicts: net/netfilter/nf_conntrack_proto_tcp.c
| * ipv4: fib_trie: Fix lookup error returnBen Hutchings2008-07-101-11/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In commit a07f5f508a4d9728c8e57d7f66294bf5b254ff7f "[IPV4] fib_trie: style cleanup", the changes to check_leaf() and fn_trie_lookup() were wrong - where fn_trie_lookup() would previously return a negative error value from check_leaf(), it now returns 0. Now fn_trie_lookup() doesn't appear to care about plen, so we can revert check_leaf() to returning the error value. Signed-off-by: Ben Hutchings <bhutchings@solarflare.com> Tested-by: William Boughton <bill@boughton.de> Acked-by: Stephen Heminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* | netns: add namespace parameter to rt_cache_flushDenis V. Lunev2008-07-051-3/+3
| | | | | | | | | | Signed-off-by: Denis V. Lunev <den@openvz.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* | net: remove CVS keywordsAdrian Bunk2008-06-111-2/+0
|/ | | | | | | | This patch removes CVS keywords that weren't updated for a long time from comments. Signed-off-by: Adrian Bunk <bunk@kernel.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NET]: Fix heavy stack usage in seq_file output routines.Pavel Emelyanov2008-04-241-8/+10
| | | | | | | | | Plan C: we can follow the Al Viro's proposal about %n like in this patch. The same applies to udp, fib (the /proc/net/route file), rt_cache and sctp debug. This is minus ~150-200 bytes for each. Signed-off-by: Pavel Emelyanov <xemul@openvz.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4]: Use NIPQUAD_FMT to format ipv4 addresses.YOSHIFUJI Hideaki2008-04-141-2/+2
| | | | | | | And use %u to format port. Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* ipv4: fib_trie leaf free optimizationStephen Hemminger2008-04-101-8/+11
| | | | | | | | | Avoid unneeded test in the case where object to be freed has to be a leaf. Don't need to use the generic tnode_free() function, instead just setup leaf to be freed. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* ipv4: fib_trie remove unused argumentStephen Hemminger2008-04-101-4/+4
| | | | | | | | The trie pointer is passed down to flush_list and flush_leaf but never used. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* IPV4: fib_trie use vmalloc for large tnodesStephen Hemminger2008-04-101-10/+15
| | | | | | | | | | | | | | | Use vmalloc rather than alloc_pages to avoid wasting memory. The problem is that tnode structure has a power of 2 sized array, plus a header. So the current code wastes almost half the memory allocated because it always needs the next bigger size to hold that small header. This is similar to an earlier patch by Eric, but instead of a list and lock, I used a workqueue to handle the fact that vfree can't be done in interrupt context. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NET] NETNS: Omit seq_net_private->net without CONFIG_NET_NS.YOSHIFUJI Hideaki2008-03-261-7/+6
| | | | | | | Without CONFIG_NET_NS, no namespace other than &init_net exists, no need to store net in seq_net_private. Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>
* Merge branch 'master' of ../net-2.6/David S. Miller2008-03-231-2/+5
|\ | | | | | | | | | | Conflicts: net/ipv6/ndisc.c
| * [IPV4] fib_trie: fix warning from rcu_assign_poingerStephen Hemminger2008-03-221-2/+5
| | | | | | | | | | | | | | | | | | | | | | | | This gets rid of a warning caused by the test in rcu_assign_pointer. I tried to fix rcu_assign_pointer, but that devolved into a long set of discussions about doing it right that came to no real solution. Since the test in rcu_assign_pointer for constant NULL would never succeed in fib_trie, just open code instead. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Acked-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* | fib_trie: print information on all routing tablesStephen Hemminger2008-03-231-84/+95
|/ | | | | | | | Make /proc/net/fib_trie and /proc/net/fib_triestat display all routing tables, not just local and main. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* fib_trie: /proc/net/route performance improvementStephen Hemminger2008-02-121-11/+82
| | | | | | | | | Use key/offset caching to change /proc/net/route (use by iputils route) from O(n^2) to O(n). This improves performance from 30sec with 160,000 routes to 1sec. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* fib_trie: handle empty treeStephen Hemminger2008-02-121-4/+2
| | | | | | | | This fixes possible problems when trie_firstleaf() returns NULL to trie_leafindex(). Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4]: Formatting fix for /proc/net/fib_trie.Denis V. Lunev2008-02-051-2/+1
| | | | | | | | | | | | The line in the /proc/net/fib_trie for route with TOS specified - has extra \n at the end - does not have a space after route scope like below. |-- 1.1.1.1 /32 universe UNICASTtos =1 Signed-off-by: Denis V. Lunev <den@openvz.org> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: rescan if key is lost during dumpStephen Hemminger2008-01-311-17/+32
| | | | | | | | | | 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 <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: apply fixes from fib_hashJulian Anastasov2008-01-311-20/+35
| | | | | | | | | | | | | | | Update fib_trie with some fib_hash fixes: - check for duplicate alternative routes for prefix+tos+priority when replacing route - properly insert by matching tos together with priority - fix alias walking to use list_for_each_entry_continue for insertion and deletion when fa_head is not NULL - copy state from fa to new_fa on replace (not a problem for now) - additionally, avoid replacement without error if new route is same, as Joonwoo Park suggests. Signed-off-by: Julian Anastasov <ja@ssi.bg> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: remove unneeded NULL checkStephen Hemminger2008-01-281-3/+0
| | | | | | | | Since fib_route_seq_show now uses hlist_for_each_entry(), the leaf info can not be NULL. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: More whitespace cleanup.Stephen Hemminger2008-01-281-6/+0
| | | | | | | Remove extra blank lines. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: avoid rescan on dumpStephen Hemminger2008-01-281-13/+21
| | | | | | | | | | | | | | | 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 <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: avoid extra search on deleteStephen Hemminger2008-01-281-38/+12
| | | | | | | Get rid of extra search that made route deletion O(n). Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: dump table in sorted orderStephen Hemminger2008-01-281-35/+39
| | | | | | | | | 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 <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: iterator recodeStephen Hemminger2008-01-281-51/+52
| | | | | | | | | 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 <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: dump message multiple part flagStephen Hemminger2008-01-281-1/+1
| | | | | | | Match fib_hash, and set NLM_F_MULTI to handle multiple part messages. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: use hash listStephen Hemminger2008-01-281-25/+24
| | | | | | | | The code to dump can use the existing hash chain rather than doing repeated lookup. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: compute size when neededStephen Hemminger2008-01-281-8/+13
| | | | | | | Compute the number of prefixes when needed, rather than doing bookeeping. Signed-off-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: style cleanupStephen Hemminger2008-01-281-95/+142
| | | | | | | | | | | Style cleanups: * make check_leaf return -1 or plen, rather than by reference * Get rid of #ifdef that is always set * split out embedded function calls in if statements. * checkpatch warnings Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: put leaf nodes in a slab cacheStephen Hemminger2008-01-281-3/+10
| | | | | | | | This improves locality for operations that touch all the leaves. Save space since these entries don't need to be hardware cache aligned. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [FIB]: Fix rcu_dereference() abuses in fib_trie.cEric Dumazet2008-01-281-12/+21
| | | | | | | | | | | | | | | | | | | | | | 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 <dada1@cosmosbay.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4]: fib hash|trie initializationStephen Hemminger2008-01-281-8/+8
| | | | | | | | | Initialization of the slab cache's should be done when IP is initialized to make sure of available memory, and that code can be marked __init. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: size and statisticsStephen Hemminger2008-01-281-35/+20
| | | | | | | | | | | | Show number of entries in trie, the size field was being set but never used, but it only counted leaves, not all entries. Refactor the two cases in fib_triestat_seq_show into a single routine. Note: the stat structure was being malloc'd but the stack usage isn't so high (288 bytes) that it is worth the additional complexity. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [FIB]: Avoid using static variables without proper lockingEric Dumazet2008-01-281-10/+12
| | | | | | | | | | | 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 <dada1@cosmosbay.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [FIB]: full_children & empty_children should be uint, not ushortEric Dumazet2008-01-281-13/+12
| | | | | | | | | | | | | | 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 <dada1@cosmosbay.com> Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: removes a memset() call in tnode_new()Eric Dumazet2008-01-281-1/+0
| | | | | | | | tnode_alloc() already clears allocated memory, using kcalloc() or alloc_pages(GFP_KERNEL|__GFP_ZERO, ...) Signed-off-by: Eric Dumazet <dada1@cosmosbay.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [FIB]: Reduce text size of net/ipv4/fib_trie.oEric Dumazet2008-01-281-2/+2
| | | | | | | | | | | | | | | | | 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 <dada1@cosmosbay.com> Acked-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: Fix sparse warnings.Stephen Hemminger2008-01-281-3/+4
| | | | | | | Make FIB TRIE go through sparse checker without warnings. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: Add statistics.Stephen Hemminger2008-01-281-12/+19
| | | | | | | | | | | 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 <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: fib_insert_node cleanupStephen Hemminger2008-01-281-17/+11
| | | | | | | | | 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 <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: Use %u for unsigned printfs.Stephen Hemminger2008-01-281-7/+7
| | | | | | | Use %u instead of %d when printing unsigned values. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: Get rid of unused revision element.Stephen Hemminger2008-01-281-10/+4
| | | | | | | | The revision element must of been part of an earlier design, because currently it is set but never used. Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [IPV4] fib_trie: Get rid of trie_init().Stephen Hemminger2008-01-281-16/+1
| | | | | | | | 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 <stephen.hemminger@vyatta.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* [NETNS]: Show routing information from correct namespace (fib_trie.c)Denis V. Lunev2008-01-281-12/+32
| | | | | | | | | | | | This is the second part (for the CONFIG_IP_FIB_TRIE case) of the patch #4, where we have created proc files in namespaces. Now we can dump correct info in them. Acked-by: Benjamin Thery <benjamin.thery@bull.net> Acked-by: Daniel Lezcano <dlezcano@fr.ibm.com> Signed-off-by: Denis V. Lunev <den@openvz.org> Signed-off-by: David S. Miller <davem@davemloft.net>
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-07 19:57:05 +0000