target/linux/generic/patches-3.18/080-10-fib_trie-Use-unsigned-long-for-anything-dealing-with.patch

   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
   4  shift by bits
   5
   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.
  11
  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
  15 one process.
  16
  17 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  18 Signed-off-by: David S. Miller <davem@davemloft.net>
  19 ---
  20
  21 --- a/net/ipv4/fib_trie.c
  22 +++ b/net/ipv4/fib_trie.c
  23 @@ -146,8 +146,8 @@ struct trie {
  24  #endif
  25  };
  26
  27 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
  28 -                                 int wasfull);
  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.
  37   */
  38 -static inline int tnode_child_length(const struct tnode *tn)
  39 +static inline unsigned long tnode_child_length(const struct tnode *tn)
  40  {
  41         return (1ul << tn->bits) & ~(1ul);
  42  }
  43
  44 -/*
  45 - * caller must hold RTNL
  46 - */
  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,
  50 +                                           unsigned long i)
  51  {
  52         BUG_ON(i >= tnode_child_length(tn));
  53
  54         return rtnl_dereference(tn->child[i]);
  55  }
  56
  57 -/*
  58 - * caller must hold RCU read lock or RTNL
  59 - */
  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,
  63 +                                               unsigned long i)
  64  {
  65         BUG_ON(i >= tnode_child_length(tn));
  66
  67 @@ -400,7 +398,7 @@ static inline int tnode_full(const struc
  68         return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
  69  }
  70
  71 -static inline void put_child(struct tnode *tn, int i,
  72 +static inline void put_child(struct tnode *tn, unsigned long i,
  73                              struct tnode *n)
  74  {
  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.
  78    */
  79
  80 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
  81 -                                 int wasfull)
  82 +static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
  83 +                                 struct tnode *n, int wasfull)
  84  {
  85         struct tnode *chi = rtnl_dereference(tn->child[i]);
  86         int isfull;
  87
  88 -       BUG_ON(i >= 1<<tn->bits);
  89 +       BUG_ON(i >= tnode_child_length(tn));
  90
  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)
  95  {
  96         struct tnode *tofree;
  97 -       int i;
  98 +       unsigned long i;
  99
 100         for (i = 0; i < tnode_child_length(tn); i++) {
 101 -               tofree = rtnl_dereference(tn->child[i]);
 102 +               tofree = tnode_get_child(tn, i);
 103                 if (tofree)
 104                         node_free(tofree);
 105         }
 106 @@ -619,10 +617,10 @@ static void tnode_clean_free(struct tnod
 107
 108  static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
 109  {
 110 -       int olen = tnode_child_length(oldtnode);
 111 +       unsigned long olen = tnode_child_length(oldtnode);
 112         struct tnode *tn;
 113 +       unsigned long i;
 114         t_key m;
 115 -       int i;
 116
 117         pr_debug("In inflate\n");
 118
 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;
 123 -               int size, j;
 124 +               unsigned long size, j;
 125
 126                 /* An empty child */
 127                 if (inode == NULL)
 128 @@ -737,7 +735,7 @@ nomem:
 129
 130  static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
 131  {
 132 -       int olen = tnode_child_length(oldtnode);
 133 +       unsigned long olen = tnode_child_length(oldtnode);
 134         struct tnode *tn, *left, *right;
 135         int i;
 136
 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)
 139  {
 140         do {
 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;
 143
 144 -               while (idx < 1u << p->bits) {
 145 +               while (idx < tnode_child_length(p)) {
 146                         c = tnode_get_child_rcu(p, idx++);
 147                         if (!c)
 148                                 continue;
 149 @@ -1786,8 +1784,8 @@ struct fib_trie_iter {
 150
 151  static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
 152  {
 153 +       unsigned long cindex = iter->index;
 154         struct tnode *tn = iter->tnode;
 155 -       unsigned int cindex = iter->index;
 156         struct tnode *p;
 157
 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);
 162  rescan:
 163 -       while (cindex < (1<<tn->bits)) {
 164 +       while (cindex < tnode_child_length(tn)) {
 165                 struct tnode *n = tnode_get_child_rcu(tn, cindex);
 166
 167                 if (n) {
 168 @@ -1874,15 +1872,16 @@ static void trie_collect_stats(struct tr
 169                         hlist_for_each_entry_rcu(li, &n->list, hlist)
 170                                 ++s->prefixes;
 171                 } else {
 172 -                       int i;
 173 +                       unsigned long i;
 174
 175                         s->tnodes++;
 176                         if (n->bits < MAX_STAT_DEPTH)
 177                                 s->nodesizes[n->bits]++;
 178
 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]))
 182                                         s->nullpointers++;
 183 +                       }
 184                 }
 185         }
 186         rcu_read_unlock();