1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:56:18 -0800
3 Subject: [PATCH] fib_trie: Use unsigned long for anything dealing with a
6 This change makes it so that anything that can be shifted by, or compared
7 to a value shifted by bits is updated to be an unsigned long. This is
8 mostly a precaution against an insanely huge address space that somehow
9 starts coming close to the 2^32 root node size which would require
10 something like 1.5 billion addresses.
12 I chose unsigned long instead of unsigned long long since I do not believe
13 it is possible to allocate a 32 bit tnode on a 32 bit system as the memory
14 consumed would be 16GB + 28B which exceeds the addressible space for any
17 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
18 Signed-off-by: David S. Miller <davem@davemloft.net>
21 --- a/net/ipv4/fib_trie.c
22 +++ b/net/ipv4/fib_trie.c
23 @@ -146,8 +146,8 @@ struct trie {
27 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
29 +static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
30 + struct tnode *n, int wasfull);
31 static struct tnode *resize(struct trie *t, struct tnode *tn);
32 static struct tnode *inflate(struct trie *t, struct tnode *tn);
33 static struct tnode *halve(struct trie *t, struct tnode *tn);
34 @@ -183,25 +183,23 @@ static inline void node_set_parent(struc
35 /* This provides us with the number of children in this node, in the case of a
36 * leaf this will return 0 meaning none of the children are accessible.
38 -static inline int tnode_child_length(const struct tnode *tn)
39 +static inline unsigned long tnode_child_length(const struct tnode *tn)
41 return (1ul << tn->bits) & ~(1ul);
45 - * caller must hold RTNL
47 -static inline struct tnode *tnode_get_child(const struct tnode *tn, unsigned int i)
48 +/* caller must hold RTNL */
49 +static inline struct tnode *tnode_get_child(const struct tnode *tn,
52 BUG_ON(i >= tnode_child_length(tn));
54 return rtnl_dereference(tn->child[i]);
58 - * caller must hold RCU read lock or RTNL
60 -static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
61 +/* caller must hold RCU read lock or RTNL */
62 +static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn,
65 BUG_ON(i >= tnode_child_length(tn));
67 @@ -400,7 +398,7 @@ static inline int tnode_full(const struc
68 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
71 -static inline void put_child(struct tnode *tn, int i,
72 +static inline void put_child(struct tnode *tn, unsigned long i,
75 tnode_put_child_reorg(tn, i, n, -1);
76 @@ -411,13 +409,13 @@ static inline void put_child(struct tnod
77 * Update the value of full_children and empty_children.
80 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
82 +static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
83 + struct tnode *n, int wasfull)
85 struct tnode *chi = rtnl_dereference(tn->child[i]);
88 - BUG_ON(i >= 1<<tn->bits);
89 + BUG_ON(i >= tnode_child_length(tn));
91 /* update emptyChildren */
92 if (n == NULL && chi != NULL)
93 @@ -607,10 +605,10 @@ no_children:
94 static void tnode_clean_free(struct tnode *tn)
100 for (i = 0; i < tnode_child_length(tn); i++) {
101 - tofree = rtnl_dereference(tn->child[i]);
102 + tofree = tnode_get_child(tn, i);
106 @@ -619,10 +617,10 @@ static void tnode_clean_free(struct tnod
108 static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
110 - int olen = tnode_child_length(oldtnode);
111 + unsigned long olen = tnode_child_length(oldtnode);
117 pr_debug("In inflate\n");
119 @@ -664,7 +662,7 @@ static struct tnode *inflate(struct trie
120 for (i = 0; i < olen; i++) {
121 struct tnode *inode = tnode_get_child(oldtnode, i);
122 struct tnode *left, *right;
124 + unsigned long size, j;
128 @@ -737,7 +735,7 @@ nomem:
130 static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
132 - int olen = tnode_child_length(oldtnode);
133 + unsigned long olen = tnode_child_length(oldtnode);
134 struct tnode *tn, *left, *right;
137 @@ -1532,9 +1530,9 @@ static int trie_flush_leaf(struct tnode
138 static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c)
141 - t_key idx = c ? idx = get_index(c->key, p) + 1 : 0;
142 + unsigned long idx = c ? idx = get_index(c->key, p) + 1 : 0;
144 - while (idx < 1u << p->bits) {
145 + while (idx < tnode_child_length(p)) {
146 c = tnode_get_child_rcu(p, idx++);
149 @@ -1786,8 +1784,8 @@ struct fib_trie_iter {
151 static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
153 + unsigned long cindex = iter->index;
154 struct tnode *tn = iter->tnode;
155 - unsigned int cindex = iter->index;
158 /* A single entry routing table */
159 @@ -1797,7 +1795,7 @@ static struct tnode *fib_trie_get_next(s
160 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
161 iter->tnode, iter->index, iter->depth);
163 - while (cindex < (1<<tn->bits)) {
164 + while (cindex < tnode_child_length(tn)) {
165 struct tnode *n = tnode_get_child_rcu(tn, cindex);
168 @@ -1874,15 +1872,16 @@ static void trie_collect_stats(struct tr
169 hlist_for_each_entry_rcu(li, &n->list, hlist)
176 if (n->bits < MAX_STAT_DEPTH)
177 s->nodesizes[n->bits]++;
179 - for (i = 0; i < tnode_child_length(n); i++)
180 + for (i = 0; i < tnode_child_length(n); i++) {
181 if (!rcu_access_pointer(n->child[i]))