diff options
| author | David S. Miller <davem@nuts.davemloft.net> | 2004-09-14 08:03:10 -0700 |
|---|---|---|
| committer | David S. Miller <davem@nuts.davemloft.net> | 2004-09-14 08:03:10 -0700 |
| commit | c862855daef3c523302d13e9eabb4d8f3fdaa42b (patch) | |
| tree | 2565ebd415ebefb9d533689f4fbcf41a8f7e137f /include/net | |
| parent | 0bdc860c38c284b46e6687e2e5bd19c28e2ddd9a (diff) | |
[IPV4]: Make fib_semantics algorithms scale better.
A singly linked list was previously used to
do fib_info object lookup for various actions
in the routing code. This does not scale very
well with many devices and even a moderate number
of routes. This was noted by Benjamin Lahaise.
To fix all of this we use 3 hash tables, two of
which grow dynamically as the number fib_info
objects increases while the final one is fixes in
size.
The statically sized table hashes on device index.
This is used for fib_sync_down, fib_sync_up, and
ip_fib_check_default.
The first dynamically sized table is keyed on
protocol, prefsrc, and priority. This is used
by fib_create_info() to look for existing fib_info
objects matching the new one being constructed.
The last dynamically sized table is keyed on
the preferred source of the route if it has one
specified. This is used by fib_sync_down when
a local address disappears.
There are still some scalability problems for
Bens test case in fib_hash.c and I will try to
attack those next.
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'include/net')
| -rw-r--r-- | include/net/ip_fib.h | 24 |
1 files changed, 12 insertions, 12 deletions
diff --git a/include/net/ip_fib.h b/include/net/ip_fib.h index 3c49b4d9bfd4..2cea1dc5a8cc 100644 --- a/include/net/ip_fib.h +++ b/include/net/ip_fib.h @@ -23,8 +23,7 @@ /* WARNING: The ordering of these elements must match ordering * of RTA_* rtnetlink attribute numbers. */ -struct kern_rta -{ +struct kern_rta { void *rta_dst; void *rta_src; int *rta_iif; @@ -40,9 +39,12 @@ struct kern_rta struct rta_session *rta_sess; }; -struct fib_nh -{ - struct net_device *nh_dev; +struct fib_info; + +struct fib_nh { + struct net_device *nh_dev; + struct hlist_node nh_hash; + struct fib_info *nh_parent; unsigned nh_flags; unsigned char nh_scope; #ifdef CONFIG_IP_ROUTE_MULTIPATH @@ -60,9 +62,9 @@ struct fib_nh * This structure contains data shared by many of routes. */ -struct fib_info -{ - struct list_head fib_list; +struct fib_info { + struct hlist_node fib_hash; + struct hlist_node fib_lhash; int fib_treeref; atomic_t fib_clntref; int fib_dead; @@ -88,8 +90,7 @@ struct fib_info struct fib_rule; #endif -struct fib_result -{ +struct fib_result { unsigned char prefixlen; unsigned char nh_sel; unsigned char type; @@ -118,8 +119,7 @@ struct fib_result #define FIB_RES_DEV(res) (FIB_RES_NH(res).nh_dev) #define FIB_RES_OIF(res) (FIB_RES_NH(res).nh_oif) -struct fib_table -{ +struct fib_table { unsigned char tb_id; unsigned tb_stamp; int (*tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res); |