aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4
diff options
context:
space:
mode:
authorPatrick McHardy <kaber@trash.net>2006-08-11 02:10:46 -0400
committerDavid S. Miller <davem@sunset.davemloft.net>2006-09-22 17:54:26 -0400
commit1af5a8c4a11cfed0c9a7f30fcfb689981750599c (patch)
tree9affafefd0b4a023d527e3f5d386957bd1dace7b /net/ipv4
parent9e762a4a89b302cb3b26a1f9bb33eff459eaeca9 (diff)
[IPV4]: Increase number of possible routing tables to 2^32
Increase the number of possible routing tables to 2^32 by replacing the fixed sized array of pointers by a hash table and 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/ipv4')
-rw-r--r--net/ipv4/fib_frontend.c102
-rw-r--r--net/ipv4/fib_hash.c26
-rw-r--r--net/ipv4/fib_rules.c4
-rw-r--r--net/ipv4/fib_trie.c26
4 files changed, 96 insertions, 62 deletions
diff --git a/net/ipv4/fib_frontend.c b/net/ipv4/fib_frontend.c
index 2696ede52de2..ad4c14f968a1 100644
--- a/net/ipv4/fib_frontend.c
+++ b/net/ipv4/fib_frontend.c
@@ -37,6 +37,7 @@
37#include <linux/skbuff.h> 37#include <linux/skbuff.h>
38#include <linux/netlink.h> 38#include <linux/netlink.h>
39#include <linux/init.h> 39#include <linux/init.h>
40#include <linux/list.h>
40 41
41#include <net/ip.h> 42#include <net/ip.h>
42#include <net/protocol.h> 43#include <net/protocol.h>
@@ -51,48 +52,67 @@
51 52
52#ifndef CONFIG_IP_MULTIPLE_TABLES 53#ifndef CONFIG_IP_MULTIPLE_TABLES
53 54
54#define RT_TABLE_MIN RT_TABLE_MAIN
55
56struct fib_table *ip_fib_local_table; 55struct fib_table *ip_fib_local_table;
57struct fib_table *ip_fib_main_table; 56struct fib_table *ip_fib_main_table;
58 57
59#else 58#define FIB_TABLE_HASHSZ 1
59static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ];
60 60
61#define RT_TABLE_MIN 1 61#else
62 62
63struct fib_table *fib_tables[RT_TABLE_MAX+1]; 63#define FIB_TABLE_HASHSZ 256
64static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ];
64 65
65struct fib_table *__fib_new_table(u32 id) 66struct fib_table *fib_new_table(u32 id)
66{ 67{
67 struct fib_table *tb; 68 struct fib_table *tb;
69 unsigned int h;
68 70
71 if (id == 0)
72 id = RT_TABLE_MAIN;
73 tb = fib_get_table(id);
74 if (tb)
75 return tb;
69 tb = fib_hash_init(id); 76 tb = fib_hash_init(id);
70 if (!tb) 77 if (!tb)
71 return NULL; 78 return NULL;
72 fib_tables[id] = tb; 79 h = id & (FIB_TABLE_HASHSZ - 1);
80 hlist_add_head_rcu(&tb->tb_hlist, &fib_table_hash[h]);
73 return tb; 81 return tb;
74} 82}
75 83
84struct fib_table *fib_get_table(u32 id)
85{
86 struct fib_table *tb;
87 struct hlist_node *node;
88 unsigned int h;
76 89
90 if (id == 0)
91 id = RT_TABLE_MAIN;
92 h = id & (FIB_TABLE_HASHSZ - 1);
93 rcu_read_lock();
94 hlist_for_each_entry_rcu(tb, node, &fib_table_hash[h], tb_hlist) {
95 if (tb->tb_id == id) {
96 rcu_read_unlock();
97 return tb;
98 }
99 }
100 rcu_read_unlock();
101 return NULL;
102}
77#endif /* CONFIG_IP_MULTIPLE_TABLES */ 103#endif /* CONFIG_IP_MULTIPLE_TABLES */
78 104
79
80static void fib_flush(void) 105static void fib_flush(void)
81{ 106{
82 int flushed = 0; 107 int flushed = 0;
83#ifdef CONFIG_IP_MULTIPLE_TABLES
84 struct fib_table *tb; 108 struct fib_table *tb;
85 u32 id; 109 struct hlist_node *node;
110 unsigned int h;
86 111
87 for (id = RT_TABLE_MAX; id>0; id--) { 112 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
88 if ((tb = fib_get_table(id))==NULL) 113 hlist_for_each_entry(tb, node, &fib_table_hash[h], tb_hlist)
89 continue; 114 flushed += tb->tb_flush(tb);
90 flushed += tb->tb_flush(tb);
91 } 115 }
92#else /* CONFIG_IP_MULTIPLE_TABLES */
93 flushed += ip_fib_main_table->tb_flush(ip_fib_main_table);
94 flushed += ip_fib_local_table->tb_flush(ip_fib_local_table);
95#endif /* CONFIG_IP_MULTIPLE_TABLES */
96 116
97 if (flushed) 117 if (flushed)
98 rt_cache_flush(-1); 118 rt_cache_flush(-1);
@@ -334,29 +354,37 @@ int inet_rtm_newroute(struct sk_buff *skb, struct nlmsghdr* nlh, void *arg)
334 354
335int inet_dump_fib(struct sk_buff *skb, struct netlink_callback *cb) 355int inet_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
336{ 356{
337 u32 t; 357 unsigned int h, s_h;
338 u32 s_t; 358 unsigned int e = 0, s_e;
339 struct fib_table *tb; 359 struct fib_table *tb;
360 struct hlist_node *node;
361 int dumped = 0;
340 362
341 if (NLMSG_PAYLOAD(cb->nlh, 0) >= sizeof(struct rtmsg) && 363 if (NLMSG_PAYLOAD(cb->nlh, 0) >= sizeof(struct rtmsg) &&
342 ((struct rtmsg*)NLMSG_DATA(cb->nlh))->rtm_flags&RTM_F_CLONED) 364 ((struct rtmsg*)NLMSG_DATA(cb->nlh))->rtm_flags&RTM_F_CLONED)
343 return ip_rt_dump(skb, cb); 365 return ip_rt_dump(skb, cb);
344 366
345 s_t = cb->args[0]; 367 s_h = cb->args[0];
346 if (s_t == 0) 368 s_e = cb->args[1];
347 s_t = cb->args[0] = RT_TABLE_MIN; 369
348 370 for (h = s_h; h < FIB_TABLE_HASHSZ; h++, s_e = 0) {
349 for (t=s_t; t<=RT_TABLE_MAX; t++) { 371 e = 0;
350 if (t < s_t) continue; 372 hlist_for_each_entry(tb, node, &fib_table_hash[h], tb_hlist) {
351 if (t > s_t) 373 if (e < s_e)
352 memset(&cb->args[1], 0, sizeof(cb->args)-sizeof(cb->args[0])); 374 goto next;
353 if ((tb = fib_get_table(t))==NULL) 375 if (dumped)
354 continue; 376 memset(&cb->args[2], 0, sizeof(cb->args) -
355 if (tb->tb_dump(tb, skb, cb) < 0) 377 2 * sizeof(cb->args[0]));
356 break; 378 if (tb->tb_dump(tb, skb, cb) < 0)
379 goto out;
380 dumped = 1;
381next:
382 e++;
383 }
357 } 384 }
358 385out:
359 cb->args[0] = t; 386 cb->args[1] = e;
387 cb->args[0] = h;
360 388
361 return skb->len; 389 return skb->len;
362} 390}
@@ -654,9 +682,15 @@ static struct notifier_block fib_netdev_notifier = {
654 682
655void __init ip_fib_init(void) 683void __init ip_fib_init(void)
656{ 684{
685 unsigned int i;
686
687 for (i = 0; i < FIB_TABLE_HASHSZ; i++)
688 INIT_HLIST_HEAD(&fib_table_hash[i]);
657#ifndef CONFIG_IP_MULTIPLE_TABLES 689#ifndef CONFIG_IP_MULTIPLE_TABLES
658 ip_fib_local_table = fib_hash_init(RT_TABLE_LOCAL); 690 ip_fib_local_table = fib_hash_init(RT_TABLE_LOCAL);
691 hlist_add_head_rcu(&ip_fib_local_table->tb_hlist, &fib_table_hash[0]);
659 ip_fib_main_table = fib_hash_init(RT_TABLE_MAIN); 692 ip_fib_main_table = fib_hash_init(RT_TABLE_MAIN);
693 hlist_add_head_rcu(&ip_fib_main_table->tb_hlist, &fib_table_hash[0]);
660#else 694#else
661 fib4_rules_init(); 695 fib4_rules_init();
662#endif 696#endif
diff --git a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c
index f8d5c8024ccb..b5bee1a71e5c 100644
--- a/net/ipv4/fib_hash.c
+++ b/net/ipv4/fib_hash.c
@@ -684,7 +684,7 @@ fn_hash_dump_bucket(struct sk_buff *skb, struct netlink_callback *cb,
684 struct fib_node *f; 684 struct fib_node *f;
685 int i, s_i; 685 int i, s_i;
686 686
687 s_i = cb->args[3]; 687 s_i = cb->args[4];
688 i = 0; 688 i = 0;
689 hlist_for_each_entry(f, node, head, fn_hash) { 689 hlist_for_each_entry(f, node, head, fn_hash) {
690 struct fib_alias *fa; 690 struct fib_alias *fa;
@@ -704,14 +704,14 @@ fn_hash_dump_bucket(struct sk_buff *skb, struct netlink_callback *cb,
704 fa->fa_tos, 704 fa->fa_tos,
705 fa->fa_info, 705 fa->fa_info,
706 NLM_F_MULTI) < 0) { 706 NLM_F_MULTI) < 0) {
707 cb->args[3] = i; 707 cb->args[4] = i;
708 return -1; 708 return -1;
709 } 709 }
710 next: 710 next:
711 i++; 711 i++;
712 } 712 }
713 } 713 }
714 cb->args[3] = i; 714 cb->args[4] = i;
715 return skb->len; 715 return skb->len;
716} 716}
717 717
@@ -722,21 +722,21 @@ fn_hash_dump_zone(struct sk_buff *skb, struct netlink_callback *cb,
722{ 722{
723 int h, s_h; 723 int h, s_h;
724 724
725 s_h = cb->args[2]; 725 s_h = cb->args[3];
726 for (h=0; h < fz->fz_divisor; h++) { 726 for (h=0; h < fz->fz_divisor; h++) {
727 if (h < s_h) continue; 727 if (h < s_h) continue;
728 if (h > s_h) 728 if (h > s_h)
729 memset(&cb->args[3], 0, 729 memset(&cb->args[4], 0,
730 sizeof(cb->args) - 3*sizeof(cb->args[0])); 730 sizeof(cb->args) - 4*sizeof(cb->args[0]));
731 if (fz->fz_hash == NULL || 731 if (fz->fz_hash == NULL ||
732 hlist_empty(&fz->fz_hash[h])) 732 hlist_empty(&fz->fz_hash[h]))
733 continue; 733 continue;
734 if (fn_hash_dump_bucket(skb, cb, tb, fz, &fz->fz_hash[h])<0) { 734 if (fn_hash_dump_bucket(skb, cb, tb, fz, &fz->fz_hash[h])<0) {
735 cb->args[2] = h; 735 cb->args[3] = h;
736 return -1; 736 return -1;
737 } 737 }
738 } 738 }
739 cb->args[2] = h; 739 cb->args[3] = h;
740 return skb->len; 740 return skb->len;
741} 741}
742 742
@@ -746,21 +746,21 @@ static int fn_hash_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin
746 struct fn_zone *fz; 746 struct fn_zone *fz;
747 struct fn_hash *table = (struct fn_hash*)tb->tb_data; 747 struct fn_hash *table = (struct fn_hash*)tb->tb_data;
748 748
749 s_m = cb->args[1]; 749 s_m = cb->args[2];
750 read_lock(&fib_hash_lock); 750 read_lock(&fib_hash_lock);
751 for (fz = table->fn_zone_list, m=0; fz; fz = fz->fz_next, m++) { 751 for (fz = table->fn_zone_list, m=0; fz; fz = fz->fz_next, m++) {
752 if (m < s_m) continue; 752 if (m < s_m) continue;
753 if (m > s_m) 753 if (m > s_m)
754 memset(&cb->args[2], 0, 754 memset(&cb->args[3], 0,
755 sizeof(cb->args) - 2*sizeof(cb->args[0])); 755 sizeof(cb->args) - 3*sizeof(cb->args[0]));
756 if (fn_hash_dump_zone(skb, cb, tb, fz) < 0) { 756 if (fn_hash_dump_zone(skb, cb, tb, fz) < 0) {
757 cb->args[1] = m; 757 cb->args[2] = m;
758 read_unlock(&fib_hash_lock); 758 read_unlock(&fib_hash_lock);
759 return -1; 759 return -1;
760 } 760 }
761 } 761 }
762 read_unlock(&fib_hash_lock); 762 read_unlock(&fib_hash_lock);
763 cb->args[1] = m; 763 cb->args[2] = m;
764 return skb->len; 764 return skb->len;
765} 765}
766 766
diff --git a/net/ipv4/fib_rules.c b/net/ipv4/fib_rules.c
index 0330b9cc4b58..ce185ac6f260 100644
--- a/net/ipv4/fib_rules.c
+++ b/net/ipv4/fib_rules.c
@@ -172,8 +172,8 @@ static struct fib_table *fib_empty_table(void)
172 u32 id; 172 u32 id;
173 173
174 for (id = 1; id <= RT_TABLE_MAX; id++) 174 for (id = 1; id <= RT_TABLE_MAX; id++)
175 if (fib_tables[id] == NULL) 175 if (fib_get_table(id) == NULL)
176 return __fib_new_table(id); 176 return fib_new_table(id);
177 return NULL; 177 return NULL;
178} 178}
179 179
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 4a27b2d573a3..2a580eb2579b 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -1848,7 +1848,7 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
1848 1848
1849 u32 xkey = htonl(key); 1849 u32 xkey = htonl(key);
1850 1850
1851 s_i = cb->args[3]; 1851 s_i = cb->args[4];
1852 i = 0; 1852 i = 0;
1853 1853
1854 /* rcu_read_lock is hold by caller */ 1854 /* rcu_read_lock is hold by caller */
@@ -1870,12 +1870,12 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
1870 plen, 1870 plen,
1871 fa->fa_tos, 1871 fa->fa_tos,
1872 fa->fa_info, 0) < 0) { 1872 fa->fa_info, 0) < 0) {
1873 cb->args[3] = i; 1873 cb->args[4] = i;
1874 return -1; 1874 return -1;
1875 } 1875 }
1876 i++; 1876 i++;
1877 } 1877 }
1878 cb->args[3] = i; 1878 cb->args[4] = i;
1879 return skb->len; 1879 return skb->len;
1880} 1880}
1881 1881
@@ -1886,14 +1886,14 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str
1886 struct list_head *fa_head; 1886 struct list_head *fa_head;
1887 struct leaf *l = NULL; 1887 struct leaf *l = NULL;
1888 1888
1889 s_h = cb->args[2]; 1889 s_h = cb->args[3];
1890 1890
1891 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) { 1891 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1892 if (h < s_h) 1892 if (h < s_h)
1893 continue; 1893 continue;
1894 if (h > s_h) 1894 if (h > s_h)
1895 memset(&cb->args[3], 0, 1895 memset(&cb->args[4], 0,
1896 sizeof(cb->args) - 3*sizeof(cb->args[0])); 1896 sizeof(cb->args) - 4*sizeof(cb->args[0]));
1897 1897
1898 fa_head = get_fa_head(l, plen); 1898 fa_head = get_fa_head(l, plen);
1899 1899
@@ -1904,11 +1904,11 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str
1904 continue; 1904 continue;
1905 1905
1906 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) { 1906 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1907 cb->args[2] = h; 1907 cb->args[3] = h;
1908 return -1; 1908 return -1;
1909 } 1909 }
1910 } 1910 }
1911 cb->args[2] = h; 1911 cb->args[3] = h;
1912 return skb->len; 1912 return skb->len;
1913} 1913}
1914 1914
@@ -1917,23 +1917,23 @@ static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin
1917 int m, s_m; 1917 int m, s_m;
1918 struct trie *t = (struct trie *) tb->tb_data; 1918 struct trie *t = (struct trie *) tb->tb_data;
1919 1919
1920 s_m = cb->args[1]; 1920 s_m = cb->args[2];
1921 1921
1922 rcu_read_lock(); 1922 rcu_read_lock();
1923 for (m = 0; m <= 32; m++) { 1923 for (m = 0; m <= 32; m++) {
1924 if (m < s_m) 1924 if (m < s_m)
1925 continue; 1925 continue;
1926 if (m > s_m) 1926 if (m > s_m)
1927 memset(&cb->args[2], 0, 1927 memset(&cb->args[3], 0,
1928 sizeof(cb->args) - 2*sizeof(cb->args[0])); 1928 sizeof(cb->args) - 3*sizeof(cb->args[0]));
1929 1929
1930 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) { 1930 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
1931 cb->args[1] = m; 1931 cb->args[2] = m;
1932 goto out; 1932 goto out;
1933 } 1933 }
1934 } 1934 }
1935 rcu_read_unlock(); 1935 rcu_read_unlock();
1936 cb->args[1] = m; 1936 cb->args[2] = m;
1937 return skb->len; 1937 return skb->len;
1938out: 1938out:
1939 rcu_read_unlock(); 1939 rcu_read_unlock();