diff options
author | Patrick McHardy <kaber@trash.net> | 2006-08-11 02:11:17 -0400 |
---|---|---|
committer | David S. Miller <davem@sunset.davemloft.net> | 2006-09-22 17:54:27 -0400 |
commit | 1b43af5480c351dbcb2eef478bafe179cbeb6e83 (patch) | |
tree | c69adf005f89c7f5147ad338f1e7243aebc14008 /net/ipv6 | |
parent | 1af5a8c4a11cfed0c9a7f30fcfb689981750599c (diff) |
[IPV6]: Increase number of possible routing tables to 2^32
Increase number of possible routing tables to 2^32 by 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>
Diffstat (limited to 'net/ipv6')
-rw-r--r-- | net/ipv6/ip6_fib.c | 171 | ||||
-rw-r--r-- | net/ipv6/route.c | 128 |
2 files changed, 152 insertions, 147 deletions
diff --git a/net/ipv6/ip6_fib.c b/net/ipv6/ip6_fib.c index 1f2316187ca4..bececbe9dd2c 100644 --- a/net/ipv6/ip6_fib.c +++ b/net/ipv6/ip6_fib.c | |||
@@ -158,7 +158,26 @@ static struct fib6_table fib6_main_tbl = { | |||
158 | }; | 158 | }; |
159 | 159 | ||
160 | #ifdef CONFIG_IPV6_MULTIPLE_TABLES | 160 | #ifdef CONFIG_IPV6_MULTIPLE_TABLES |
161 | #define FIB_TABLE_HASHSZ 256 | ||
162 | #else | ||
163 | #define FIB_TABLE_HASHSZ 1 | ||
164 | #endif | ||
165 | static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ]; | ||
166 | |||
167 | static void fib6_link_table(struct fib6_table *tb) | ||
168 | { | ||
169 | unsigned int h; | ||
170 | |||
171 | h = tb->tb6_id & (FIB_TABLE_HASHSZ - 1); | ||
161 | 172 | ||
173 | /* | ||
174 | * No protection necessary, this is the only list mutatation | ||
175 | * operation, tables never disappear once they exist. | ||
176 | */ | ||
177 | hlist_add_head_rcu(&tb->tb6_hlist, &fib_table_hash[h]); | ||
178 | } | ||
179 | |||
180 | #ifdef CONFIG_IPV6_MULTIPLE_TABLES | ||
162 | static struct fib6_table fib6_local_tbl = { | 181 | static struct fib6_table fib6_local_tbl = { |
163 | .tb6_id = RT6_TABLE_LOCAL, | 182 | .tb6_id = RT6_TABLE_LOCAL, |
164 | .tb6_lock = RW_LOCK_UNLOCKED, | 183 | .tb6_lock = RW_LOCK_UNLOCKED, |
@@ -168,9 +187,6 @@ static struct fib6_table fib6_local_tbl = { | |||
168 | }, | 187 | }, |
169 | }; | 188 | }; |
170 | 189 | ||
171 | #define FIB_TABLE_HASHSZ 256 | ||
172 | static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ]; | ||
173 | |||
174 | static struct fib6_table *fib6_alloc_table(u32 id) | 190 | static struct fib6_table *fib6_alloc_table(u32 id) |
175 | { | 191 | { |
176 | struct fib6_table *table; | 192 | struct fib6_table *table; |
@@ -186,19 +202,6 @@ static struct fib6_table *fib6_alloc_table(u32 id) | |||
186 | return table; | 202 | return table; |
187 | } | 203 | } |
188 | 204 | ||
189 | static void fib6_link_table(struct fib6_table *tb) | ||
190 | { | ||
191 | unsigned int h; | ||
192 | |||
193 | h = tb->tb6_id & (FIB_TABLE_HASHSZ - 1); | ||
194 | |||
195 | /* | ||
196 | * No protection necessary, this is the only list mutatation | ||
197 | * operation, tables never disappear once they exist. | ||
198 | */ | ||
199 | hlist_add_head_rcu(&tb->tb6_hlist, &fib_table_hash[h]); | ||
200 | } | ||
201 | |||
202 | struct fib6_table *fib6_new_table(u32 id) | 205 | struct fib6_table *fib6_new_table(u32 id) |
203 | { | 206 | { |
204 | struct fib6_table *tb; | 207 | struct fib6_table *tb; |
@@ -263,10 +266,135 @@ struct dst_entry *fib6_rule_lookup(struct flowi *fl, int flags, | |||
263 | 266 | ||
264 | static void __init fib6_tables_init(void) | 267 | static void __init fib6_tables_init(void) |
265 | { | 268 | { |
269 | fib6_link_table(&fib6_main_tbl); | ||
266 | } | 270 | } |
267 | 271 | ||
268 | #endif | 272 | #endif |
269 | 273 | ||
274 | static int fib6_dump_node(struct fib6_walker_t *w) | ||
275 | { | ||
276 | int res; | ||
277 | struct rt6_info *rt; | ||
278 | |||
279 | for (rt = w->leaf; rt; rt = rt->u.next) { | ||
280 | res = rt6_dump_route(rt, w->args); | ||
281 | if (res < 0) { | ||
282 | /* Frame is full, suspend walking */ | ||
283 | w->leaf = rt; | ||
284 | return 1; | ||
285 | } | ||
286 | BUG_TRAP(res!=0); | ||
287 | } | ||
288 | w->leaf = NULL; | ||
289 | return 0; | ||
290 | } | ||
291 | |||
292 | static void fib6_dump_end(struct netlink_callback *cb) | ||
293 | { | ||
294 | struct fib6_walker_t *w = (void*)cb->args[2]; | ||
295 | |||
296 | if (w) { | ||
297 | cb->args[2] = 0; | ||
298 | kfree(w); | ||
299 | } | ||
300 | cb->done = (void*)cb->args[3]; | ||
301 | cb->args[1] = 3; | ||
302 | } | ||
303 | |||
304 | static int fib6_dump_done(struct netlink_callback *cb) | ||
305 | { | ||
306 | fib6_dump_end(cb); | ||
307 | return cb->done ? cb->done(cb) : 0; | ||
308 | } | ||
309 | |||
310 | static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb, | ||
311 | struct netlink_callback *cb) | ||
312 | { | ||
313 | struct fib6_walker_t *w; | ||
314 | int res; | ||
315 | |||
316 | w = (void *)cb->args[2]; | ||
317 | w->root = &table->tb6_root; | ||
318 | |||
319 | if (cb->args[4] == 0) { | ||
320 | read_lock_bh(&table->tb6_lock); | ||
321 | res = fib6_walk(w); | ||
322 | read_unlock_bh(&table->tb6_lock); | ||
323 | if (res > 0) | ||
324 | cb->args[4] = 1; | ||
325 | } else { | ||
326 | read_lock_bh(&table->tb6_lock); | ||
327 | res = fib6_walk_continue(w); | ||
328 | read_unlock_bh(&table->tb6_lock); | ||
329 | if (res != 0) { | ||
330 | if (res < 0) | ||
331 | fib6_walker_unlink(w); | ||
332 | goto end; | ||
333 | } | ||
334 | fib6_walker_unlink(w); | ||
335 | cb->args[4] = 0; | ||
336 | } | ||
337 | end: | ||
338 | return res; | ||
339 | } | ||
340 | |||
341 | int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb) | ||
342 | { | ||
343 | unsigned int h, s_h; | ||
344 | unsigned int e = 0, s_e; | ||
345 | struct rt6_rtnl_dump_arg arg; | ||
346 | struct fib6_walker_t *w; | ||
347 | struct fib6_table *tb; | ||
348 | struct hlist_node *node; | ||
349 | int res = 0; | ||
350 | |||
351 | s_h = cb->args[0]; | ||
352 | s_e = cb->args[1]; | ||
353 | |||
354 | w = (void *)cb->args[2]; | ||
355 | if (w == NULL) { | ||
356 | /* New dump: | ||
357 | * | ||
358 | * 1. hook callback destructor. | ||
359 | */ | ||
360 | cb->args[3] = (long)cb->done; | ||
361 | cb->done = fib6_dump_done; | ||
362 | |||
363 | /* | ||
364 | * 2. allocate and initialize walker. | ||
365 | */ | ||
366 | w = kzalloc(sizeof(*w), GFP_ATOMIC); | ||
367 | if (w == NULL) | ||
368 | return -ENOMEM; | ||
369 | w->func = fib6_dump_node; | ||
370 | cb->args[2] = (long)w; | ||
371 | } | ||
372 | |||
373 | arg.skb = skb; | ||
374 | arg.cb = cb; | ||
375 | w->args = &arg; | ||
376 | |||
377 | for (h = s_h; h < FIB_TABLE_HASHSZ; h++, s_e = 0) { | ||
378 | e = 0; | ||
379 | hlist_for_each_entry(tb, node, &fib_table_hash[h], tb6_hlist) { | ||
380 | if (e < s_e) | ||
381 | goto next; | ||
382 | res = fib6_dump_table(tb, skb, cb); | ||
383 | if (res != 0) | ||
384 | goto out; | ||
385 | next: | ||
386 | e++; | ||
387 | } | ||
388 | } | ||
389 | out: | ||
390 | cb->args[1] = e; | ||
391 | cb->args[0] = h; | ||
392 | |||
393 | res = res < 0 ? res : skb->len; | ||
394 | if (res <= 0) | ||
395 | fib6_dump_end(cb); | ||
396 | return res; | ||
397 | } | ||
270 | 398 | ||
271 | /* | 399 | /* |
272 | * Routing Table | 400 | * Routing Table |
@@ -1187,17 +1315,20 @@ static void fib6_clean_tree(struct fib6_node *root, | |||
1187 | void fib6_clean_all(int (*func)(struct rt6_info *, void *arg), | 1315 | void fib6_clean_all(int (*func)(struct rt6_info *, void *arg), |
1188 | int prune, void *arg) | 1316 | int prune, void *arg) |
1189 | { | 1317 | { |
1190 | int i; | ||
1191 | struct fib6_table *table; | 1318 | struct fib6_table *table; |
1319 | struct hlist_node *node; | ||
1320 | unsigned int h; | ||
1192 | 1321 | ||
1193 | for (i = FIB6_TABLE_MIN; i <= FIB6_TABLE_MAX; i++) { | 1322 | rcu_read_lock(); |
1194 | table = fib6_get_table(i); | 1323 | for (h = 0; h < FIB_TABLE_HASHSZ; h++) { |
1195 | if (table != NULL) { | 1324 | hlist_for_each_entry_rcu(table, node, &fib_table_hash[h], |
1325 | tb6_hlist) { | ||
1196 | write_lock_bh(&table->tb6_lock); | 1326 | write_lock_bh(&table->tb6_lock); |
1197 | fib6_clean_tree(&table->tb6_root, func, prune, arg); | 1327 | fib6_clean_tree(&table->tb6_root, func, prune, arg); |
1198 | write_unlock_bh(&table->tb6_lock); | 1328 | write_unlock_bh(&table->tb6_lock); |
1199 | } | 1329 | } |
1200 | } | 1330 | } |
1331 | rcu_read_unlock(); | ||
1201 | } | 1332 | } |
1202 | 1333 | ||
1203 | static int fib6_prune_clone(struct rt6_info *rt, void *arg) | 1334 | static int fib6_prune_clone(struct rt6_info *rt, void *arg) |
diff --git a/net/ipv6/route.c b/net/ipv6/route.c index 843c5509fced..9ce28277f47f 100644 --- a/net/ipv6/route.c +++ b/net/ipv6/route.c | |||
@@ -1874,12 +1874,6 @@ int inet6_rtm_newroute(struct sk_buff *skb, struct nlmsghdr* nlh, void *arg) | |||
1874 | rtm_get_table(arg, r->rtm_table)); | 1874 | rtm_get_table(arg, r->rtm_table)); |
1875 | } | 1875 | } |
1876 | 1876 | ||
1877 | struct rt6_rtnl_dump_arg | ||
1878 | { | ||
1879 | struct sk_buff *skb; | ||
1880 | struct netlink_callback *cb; | ||
1881 | }; | ||
1882 | |||
1883 | static int rt6_fill_node(struct sk_buff *skb, struct rt6_info *rt, | 1877 | static int rt6_fill_node(struct sk_buff *skb, struct rt6_info *rt, |
1884 | struct in6_addr *dst, struct in6_addr *src, | 1878 | struct in6_addr *dst, struct in6_addr *src, |
1885 | int iif, int type, u32 pid, u32 seq, | 1879 | int iif, int type, u32 pid, u32 seq, |
@@ -1976,7 +1970,7 @@ rtattr_failure: | |||
1976 | return -1; | 1970 | return -1; |
1977 | } | 1971 | } |
1978 | 1972 | ||
1979 | static int rt6_dump_route(struct rt6_info *rt, void *p_arg) | 1973 | int rt6_dump_route(struct rt6_info *rt, void *p_arg) |
1980 | { | 1974 | { |
1981 | struct rt6_rtnl_dump_arg *arg = (struct rt6_rtnl_dump_arg *) p_arg; | 1975 | struct rt6_rtnl_dump_arg *arg = (struct rt6_rtnl_dump_arg *) p_arg; |
1982 | int prefix; | 1976 | int prefix; |
@@ -1992,126 +1986,6 @@ static int rt6_dump_route(struct rt6_info *rt, void *p_arg) | |||
1992 | prefix, NLM_F_MULTI); | 1986 | prefix, NLM_F_MULTI); |
1993 | } | 1987 | } |
1994 | 1988 | ||
1995 | static int fib6_dump_node(struct fib6_walker_t *w) | ||
1996 | { | ||
1997 | int res; | ||
1998 | struct rt6_info *rt; | ||
1999 | |||
2000 | for (rt = w->leaf; rt; rt = rt->u.next) { | ||
2001 | res = rt6_dump_route(rt, w->args); | ||
2002 | if (res < 0) { | ||
2003 | /* Frame is full, suspend walking */ | ||
2004 | w->leaf = rt; | ||
2005 | return 1; | ||
2006 | } | ||
2007 | BUG_TRAP(res!=0); | ||
2008 | } | ||
2009 | w->leaf = NULL; | ||
2010 | return 0; | ||
2011 | } | ||
2012 | |||
2013 | static void fib6_dump_end(struct netlink_callback *cb) | ||
2014 | { | ||
2015 | struct fib6_walker_t *w = (void*)cb->args[0]; | ||
2016 | |||
2017 | if (w) { | ||
2018 | cb->args[0] = 0; | ||
2019 | kfree(w); | ||
2020 | } | ||
2021 | cb->done = (void*)cb->args[1]; | ||
2022 | cb->args[1] = 0; | ||
2023 | } | ||
2024 | |||
2025 | static int fib6_dump_done(struct netlink_callback *cb) | ||
2026 | { | ||
2027 | fib6_dump_end(cb); | ||
2028 | return cb->done ? cb->done(cb) : 0; | ||
2029 | } | ||
2030 | |||
2031 | int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb) | ||
2032 | { | ||
2033 | struct fib6_table *table; | ||
2034 | struct rt6_rtnl_dump_arg arg; | ||
2035 | struct fib6_walker_t *w; | ||
2036 | int i, res = 0; | ||
2037 | |||
2038 | arg.skb = skb; | ||
2039 | arg.cb = cb; | ||
2040 | |||
2041 | /* | ||
2042 | * cb->args[0] = pointer to walker structure | ||
2043 | * cb->args[1] = saved cb->done() pointer | ||
2044 | * cb->args[2] = current table being dumped | ||
2045 | */ | ||
2046 | |||
2047 | w = (void*)cb->args[0]; | ||
2048 | if (w == NULL) { | ||
2049 | /* New dump: | ||
2050 | * | ||
2051 | * 1. hook callback destructor. | ||
2052 | */ | ||
2053 | cb->args[1] = (long)cb->done; | ||
2054 | cb->done = fib6_dump_done; | ||
2055 | |||
2056 | /* | ||
2057 | * 2. allocate and initialize walker. | ||
2058 | */ | ||
2059 | w = kzalloc(sizeof(*w), GFP_ATOMIC); | ||
2060 | if (w == NULL) | ||
2061 | return -ENOMEM; | ||
2062 | w->func = fib6_dump_node; | ||
2063 | w->args = &arg; | ||
2064 | cb->args[0] = (long)w; | ||
2065 | cb->args[2] = FIB6_TABLE_MIN; | ||
2066 | } else { | ||
2067 | w->args = &arg; | ||
2068 | i = cb->args[2]; | ||
2069 | if (i > FIB6_TABLE_MAX) | ||
2070 | goto end; | ||
2071 | |||
2072 | table = fib6_get_table(i); | ||
2073 | if (table != NULL) { | ||
2074 | read_lock_bh(&table->tb6_lock); | ||
2075 | w->root = &table->tb6_root; | ||
2076 | res = fib6_walk_continue(w); | ||
2077 | read_unlock_bh(&table->tb6_lock); | ||
2078 | if (res != 0) { | ||
2079 | if (res < 0) | ||
2080 | fib6_walker_unlink(w); | ||
2081 | goto end; | ||
2082 | } | ||
2083 | } | ||
2084 | |||
2085 | fib6_walker_unlink(w); | ||
2086 | cb->args[2] = ++i; | ||
2087 | } | ||
2088 | |||
2089 | for (i = cb->args[2]; i <= FIB6_TABLE_MAX; i++) { | ||
2090 | table = fib6_get_table(i); | ||
2091 | if (table == NULL) | ||
2092 | continue; | ||
2093 | |||
2094 | read_lock_bh(&table->tb6_lock); | ||
2095 | w->root = &table->tb6_root; | ||
2096 | res = fib6_walk(w); | ||
2097 | read_unlock_bh(&table->tb6_lock); | ||
2098 | if (res) | ||
2099 | break; | ||
2100 | } | ||
2101 | end: | ||
2102 | cb->args[2] = i; | ||
2103 | |||
2104 | res = res < 0 ? res : skb->len; | ||
2105 | /* res < 0 is an error. (really, impossible) | ||
2106 | res == 0 means that dump is complete, but skb still can contain data. | ||
2107 | res > 0 dump is not complete, but frame is full. | ||
2108 | */ | ||
2109 | /* Destroy walker, if dump of this table is complete. */ | ||
2110 | if (res <= 0) | ||
2111 | fib6_dump_end(cb); | ||
2112 | return res; | ||
2113 | } | ||
2114 | |||
2115 | int inet6_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg) | 1989 | int inet6_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg) |
2116 | { | 1990 | { |
2117 | struct rtattr **rta = arg; | 1991 | struct rtattr **rta = arg; |