aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv6
diff options
context:
space:
mode:
authorPatrick McHardy <kaber@trash.net>2006-08-11 02:11:17 -0400
committerDavid S. Miller <davem@sunset.davemloft.net>2006-09-22 17:54:27 -0400
commit1b43af5480c351dbcb2eef478bafe179cbeb6e83 (patch)
treec69adf005f89c7f5147ad338f1e7243aebc14008 /net/ipv6
parent1af5a8c4a11cfed0c9a7f30fcfb689981750599c (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.c171
-rw-r--r--net/ipv6/route.c128
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
165static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ];
166
167static 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
162static struct fib6_table fib6_local_tbl = { 181static 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
172static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ];
173
174static struct fib6_table *fib6_alloc_table(u32 id) 190static 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
189static 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
202struct fib6_table *fib6_new_table(u32 id) 205struct 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
264static void __init fib6_tables_init(void) 267static 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
274static 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
292static 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
304static int fib6_dump_done(struct netlink_callback *cb)
305{
306 fib6_dump_end(cb);
307 return cb->done ? cb->done(cb) : 0;
308}
309
310static 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 }
337end:
338 return res;
339}
340
341int 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;
385next:
386 e++;
387 }
388 }
389out:
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,
1187void fib6_clean_all(int (*func)(struct rt6_info *, void *arg), 1315void 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
1203static int fib6_prune_clone(struct rt6_info *rt, void *arg) 1334static 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
1877struct rt6_rtnl_dump_arg
1878{
1879 struct sk_buff *skb;
1880 struct netlink_callback *cb;
1881};
1882
1883static int rt6_fill_node(struct sk_buff *skb, struct rt6_info *rt, 1877static 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
1979static int rt6_dump_route(struct rt6_info *rt, void *p_arg) 1973int 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
1995static 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
2013static 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
2025static int fib6_dump_done(struct netlink_callback *cb)
2026{
2027 fib6_dump_end(cb);
2028 return cb->done ? cb->done(cb) : 0;
2029}
2030
2031int 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 }
2101end:
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
2115int inet6_rtm_getroute(struct sk_buff *in_skb, struct nlmsghdr* nlh, void *arg) 1989int 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;