+++ /dev/null
-From: Alexander Duyck <alexander.h.duyck@redhat.com>
-Date: Wed, 31 Dec 2014 10:56:18 -0800
-Subject: [PATCH] fib_trie: Use unsigned long for anything dealing with a
- shift by bits
-
-This change makes it so that anything that can be shifted by, or compared
-to a value shifted by bits is updated to be an unsigned long. This is
-mostly a precaution against an insanely huge address space that somehow
-starts coming close to the 2^32 root node size which would require
-something like 1.5 billion addresses.
-
-I chose unsigned long instead of unsigned long long since I do not believe
-it is possible to allocate a 32 bit tnode on a 32 bit system as the memory
-consumed would be 16GB + 28B which exceeds the addressible space for any
-one process.
-
-Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
-Signed-off-by: David S. Miller <davem@davemloft.net>
----
-
---- a/net/ipv4/fib_trie.c
-+++ b/net/ipv4/fib_trie.c
-@@ -146,8 +146,8 @@ struct trie {
- #endif
- };
-
--static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
-- int wasfull);
-+static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
-+ struct tnode *n, int wasfull);
- static struct tnode *resize(struct trie *t, struct tnode *tn);
- static struct tnode *inflate(struct trie *t, struct tnode *tn);
- static struct tnode *halve(struct trie *t, struct tnode *tn);
-@@ -183,25 +183,23 @@ static inline void node_set_parent(struc
- /* This provides us with the number of children in this node, in the case of a
- * leaf this will return 0 meaning none of the children are accessible.
- */
--static inline int tnode_child_length(const struct tnode *tn)
-+static inline unsigned long tnode_child_length(const struct tnode *tn)
- {
- return (1ul << tn->bits) & ~(1ul);
- }
-
--/*
-- * caller must hold RTNL
-- */
--static inline struct tnode *tnode_get_child(const struct tnode *tn, unsigned int i)
-+/* caller must hold RTNL */
-+static inline struct tnode *tnode_get_child(const struct tnode *tn,
-+ unsigned long i)
- {
- BUG_ON(i >= tnode_child_length(tn));
-
- return rtnl_dereference(tn->child[i]);
- }
-
--/*
-- * caller must hold RCU read lock or RTNL
-- */
--static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
-+/* caller must hold RCU read lock or RTNL */
-+static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn,
-+ unsigned long i)
- {
- BUG_ON(i >= tnode_child_length(tn));
-
-@@ -400,7 +398,7 @@ static inline int tnode_full(const struc
- return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
- }
-
--static inline void put_child(struct tnode *tn, int i,
-+static inline void put_child(struct tnode *tn, unsigned long i,
- struct tnode *n)
- {
- tnode_put_child_reorg(tn, i, n, -1);
-@@ -411,13 +409,13 @@ static inline void put_child(struct tnod
- * Update the value of full_children and empty_children.
- */
-
--static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
-- int wasfull)
-+static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
-+ struct tnode *n, int wasfull)
- {
- struct tnode *chi = rtnl_dereference(tn->child[i]);
- int isfull;
-
-- BUG_ON(i >= 1<<tn->bits);
-+ BUG_ON(i >= tnode_child_length(tn));
-
- /* update emptyChildren */
- if (n == NULL && chi != NULL)
-@@ -607,10 +605,10 @@ no_children:
- static void tnode_clean_free(struct tnode *tn)
- {
- struct tnode *tofree;
-- int i;
-+ unsigned long i;
-
- for (i = 0; i < tnode_child_length(tn); i++) {
-- tofree = rtnl_dereference(tn->child[i]);
-+ tofree = tnode_get_child(tn, i);
- if (tofree)
- node_free(tofree);
- }
-@@ -619,10 +617,10 @@ static void tnode_clean_free(struct tnod
-
- static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
- {
-- int olen = tnode_child_length(oldtnode);
-+ unsigned long olen = tnode_child_length(oldtnode);
- struct tnode *tn;
-+ unsigned long i;
- t_key m;
-- int i;
-
- pr_debug("In inflate\n");
-
-@@ -664,7 +662,7 @@ static struct tnode *inflate(struct trie
- for (i = 0; i < olen; i++) {
- struct tnode *inode = tnode_get_child(oldtnode, i);
- struct tnode *left, *right;
-- int size, j;
-+ unsigned long size, j;
-
- /* An empty child */
- if (inode == NULL)
-@@ -737,7 +735,7 @@ nomem:
-
- static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
- {
-- int olen = tnode_child_length(oldtnode);
-+ unsigned long olen = tnode_child_length(oldtnode);
- struct tnode *tn, *left, *right;
- int i;
-
-@@ -1532,9 +1530,9 @@ static int trie_flush_leaf(struct tnode
- static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c)
- {
- do {
-- t_key idx = c ? idx = get_index(c->key, p) + 1 : 0;
-+ unsigned long idx = c ? idx = get_index(c->key, p) + 1 : 0;
-
-- while (idx < 1u << p->bits) {
-+ while (idx < tnode_child_length(p)) {
- c = tnode_get_child_rcu(p, idx++);
- if (!c)
- continue;
-@@ -1786,8 +1784,8 @@ struct fib_trie_iter {
-
- static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
- {
-+ unsigned long cindex = iter->index;
- struct tnode *tn = iter->tnode;
-- unsigned int cindex = iter->index;
- struct tnode *p;
-
- /* A single entry routing table */
-@@ -1797,7 +1795,7 @@ static struct tnode *fib_trie_get_next(s
- pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
- iter->tnode, iter->index, iter->depth);
- rescan:
-- while (cindex < (1<<tn->bits)) {
-+ while (cindex < tnode_child_length(tn)) {
- struct tnode *n = tnode_get_child_rcu(tn, cindex);
-
- if (n) {
-@@ -1874,15 +1872,16 @@ static void trie_collect_stats(struct tr
- hlist_for_each_entry_rcu(li, &n->list, hlist)
- ++s->prefixes;
- } else {
-- int i;
-+ unsigned long i;
-
- s->tnodes++;
- if (n->bits < MAX_STAT_DEPTH)
- s->nodesizes[n->bits]++;
-
-- for (i = 0; i < tnode_child_length(n); i++)
-+ for (i = 0; i < tnode_child_length(n); i++) {
- if (!rcu_access_pointer(n->child[i]))
- s->nullpointers++;
-+ }
- }
- }
- rcu_read_unlock();
projects / openwrt / openwrt.git / blobdiff