target/linux/generic/pending-3.18/080-05-fib_trie-Merge-leaf-into-tnode.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:55:47 -0800
   3 Subject: [PATCH] fib_trie: Merge leaf into tnode
   4
   5 This change makes it so that leaf and tnode are the same struct.  As a
   6 result there is no need for rt_trie_node anymore since everyting can be
   7 merged into tnode.
   8
   9 On 32b systems this results in the leaf being 4 bytes larger, however I
  10 don't know if that is really an issue as this and an eariler patch that
  11 added bits & pos have increased the size from 20 to 28.  If I am not
  12 mistaken slub/slab allocate on power of 2 sizes so 20 was likely being
  13 rounded up to 32 anyway.
  14
  15 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  16 Signed-off-by: David S. Miller <davem@davemloft.net>
  17 ---
  18
  19 --- a/net/ipv4/fib_trie.c
  20 +++ b/net/ipv4/fib_trie.c
  21 @@ -96,32 +96,16 @@ struct tnode {
  22         unsigned char pos;              /* 2log(KEYLENGTH) bits needed */
  23         struct tnode __rcu *parent;
  24         struct rcu_head rcu;
  25 -       /* everything above this comment must be the same as rt_trie_node */
  26 -       unsigned int full_children;     /* KEYLENGTH bits needed */
  27 -       unsigned int empty_children;    /* KEYLENGTH bits needed */
  28 -       struct rt_trie_node __rcu *child[0];
  29 -};
  30 -
  31 -/* This struct represents the shared bits between tnode and leaf.  If any
  32 - * ordering is changed here is must also be updated in tnode and leaf as
  33 - * well.
  34 - */
  35 -struct rt_trie_node {
  36 -       t_key key;
  37 -       unsigned char bits;
  38 -       unsigned char pos;
  39 -       struct tnode __rcu *parent;
  40 -       struct rcu_head rcu;
  41 -};
  42 -
  43 -struct leaf {
  44 -       t_key key;
  45 -       unsigned char bits;
  46 -       unsigned char pos;
  47 -       struct tnode __rcu *parent;
  48 -       struct rcu_head rcu;
  49 -       /* everything above this comment must be the same as rt_trie_node */
  50 -       struct hlist_head list;
  51 +       union {
  52 +               /* The fields in this struct are valid if bits > 0 (TNODE) */
  53 +               struct {
  54 +                       unsigned int full_children;  /* KEYLENGTH bits needed */
  55 +                       unsigned int empty_children; /* KEYLENGTH bits needed */
  56 +                       struct tnode __rcu *child[0];
  57 +               };
  58 +               /* This list pointer if valid if bits == 0 (LEAF) */
  59 +               struct hlist_head list;
  60 +       };
  61  };
  62
  63  struct leaf_info {
  64 @@ -154,15 +138,15 @@ struct trie_stat {
  65  };
  66
  67  struct trie {
  68 -       struct rt_trie_node __rcu *trie;
  69 +       struct tnode __rcu *trie;
  70  #ifdef CONFIG_IP_FIB_TRIE_STATS
  71         struct trie_use_stats __percpu *stats;
  72  #endif
  73  };
  74
  75 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
  76 +static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
  77                                   int wasfull);
  78 -static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
  79 +static struct tnode *resize(struct trie *t, struct tnode *tn);
  80  static struct tnode *inflate(struct trie *t, struct tnode *tn);
  81  static struct tnode *halve(struct trie *t, struct tnode *tn);
  82  /* tnodes to free after resize(); protected by RTNL */
  83 @@ -186,10 +170,10 @@ static struct kmem_cache *trie_leaf_kmem
  84  #define node_parent_rcu(n) rcu_dereference_rtnl((n)->parent)
  85
  86  /* wrapper for rcu_assign_pointer */
  87 -static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
  88 +static inline void node_set_parent(struct tnode *n, struct tnode *tp)
  89  {
  90 -       if (node)
  91 -               rcu_assign_pointer(node->parent, ptr);
  92 +       if (n)
  93 +               rcu_assign_pointer(n->parent, tp);
  94  }
  95
  96  #define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER((n)->parent, p)
  97 @@ -205,7 +189,7 @@ static inline int tnode_child_length(con
  98  /*
  99   * caller must hold RTNL
 100   */
 101 -static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
 102 +static inline struct tnode *tnode_get_child(const struct tnode *tn, unsigned int i)
 103  {
 104         BUG_ON(i >= tnode_child_length(tn));
 105
 106 @@ -215,7 +199,7 @@ static inline struct rt_trie_node *tnode
 107  /*
 108   * caller must hold RCU read lock or RTNL
 109   */
 110 -static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
 111 +static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
 112  {
 113         BUG_ON(i >= tnode_child_length(tn));
 114
 115 @@ -340,11 +324,11 @@ static inline void alias_free_mem_rcu(st
 116  }
 117
 118  #define TNODE_KMALLOC_MAX \
 119 -       ilog2((PAGE_SIZE - sizeof(struct tnode)) / sizeof(struct rt_trie_node *))
 120 +       ilog2((PAGE_SIZE - sizeof(struct tnode)) / sizeof(struct tnode *))
 121
 122  static void __node_free_rcu(struct rcu_head *head)
 123  {
 124 -       struct rt_trie_node *n = container_of(head, struct rt_trie_node, rcu);
 125 +       struct tnode *n = container_of(head, struct tnode, rcu);
 126
 127         if (IS_LEAF(n))
 128                 kmem_cache_free(trie_leaf_kmem, n);
 129 @@ -395,9 +379,9 @@ static void tnode_free_flush(void)
 130         }
 131  }
 132
 133 -static struct leaf *leaf_new(t_key key)
 134 +static struct tnode *leaf_new(t_key key)
 135  {
 136 -       struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
 137 +       struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
 138         if (l) {
 139                 l->parent = NULL;
 140                 /* set key and pos to reflect full key value
 141 @@ -444,7 +428,7 @@ static struct tnode *tnode_new(t_key key
 142         }
 143
 144         pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
 145 -                sizeof(struct rt_trie_node *) << bits);
 146 +                sizeof(struct tnode *) << bits);
 147         return tn;
 148  }
 149
 150 @@ -453,13 +437,13 @@ static struct tnode *tnode_new(t_key key
 151   * and no bits are skipped. See discussion in dyntree paper p. 6
 152   */
 153
 154 -static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
 155 +static inline int tnode_full(const struct tnode *tn, const struct tnode *n)
 156  {
 157         return n && IS_TNODE(n) && (n->pos == (tn->pos + tn->bits));
 158  }
 159
 160  static inline void put_child(struct tnode *tn, int i,
 161 -                            struct rt_trie_node *n)
 162 +                            struct tnode *n)
 163  {
 164         tnode_put_child_reorg(tn, i, n, -1);
 165  }
 166 @@ -469,10 +453,10 @@ static inline void put_child(struct tnod
 167    * Update the value of full_children and empty_children.
 168    */
 169
 170 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
 171 +static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
 172                                   int wasfull)
 173  {
 174 -       struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
 175 +       struct tnode *chi = rtnl_dereference(tn->child[i]);
 176         int isfull;
 177
 178         BUG_ON(i >= 1<<tn->bits);
 179 @@ -499,10 +483,9 @@ static void tnode_put_child_reorg(struct
 180  }
 181
 182  #define MAX_WORK 10
 183 -static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
 184 +static struct tnode *resize(struct trie *t, struct tnode *tn)
 185  {
 186 -       struct rt_trie_node *n = NULL;
 187 -       struct tnode *old_tn;
 188 +       struct tnode *old_tn, *n = NULL;
 189         int inflate_threshold_use;
 190         int halve_threshold_use;
 191         int max_work;
 192 @@ -614,7 +597,7 @@ static struct rt_trie_node *resize(struc
 193
 194         /* Return if at least one inflate is run */
 195         if (max_work != MAX_WORK)
 196 -               return (struct rt_trie_node *) tn;
 197 +               return tn;
 198
 199         /*
 200          * Halve as long as the number of empty children in this
 201 @@ -650,13 +633,13 @@ no_children:
 202                 tnode_free_safe(tn);
 203                 return n;
 204         }
 205 -       return (struct rt_trie_node *) tn;
 206 +       return tn;
 207  }
 208
 209
 210  static void tnode_clean_free(struct tnode *tn)
 211  {
 212 -       struct rt_trie_node *tofree;
 213 +       struct tnode *tofree;
 214         int i;
 215
 216         for (i = 0; i < tnode_child_length(tn); i++) {
 217 @@ -667,10 +650,10 @@ static void tnode_clean_free(struct tnod
 218         node_free(tn);
 219  }
 220
 221 -static struct tnode *inflate(struct trie *t, struct tnode *tn)
 222 +static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
 223  {
 224 -       struct tnode *oldtnode = tn;
 225 -       int olen = tnode_child_length(tn);
 226 +       int olen = tnode_child_length(oldtnode);
 227 +       struct tnode *tn;
 228         int i;
 229
 230         pr_debug("In inflate\n");
 231 @@ -690,11 +673,8 @@ static struct tnode *inflate(struct trie
 232         for (i = 0; i < olen; i++) {
 233                 struct tnode *inode;
 234
 235 -               inode = (struct tnode *) tnode_get_child(oldtnode, i);
 236 -               if (inode &&
 237 -                   IS_TNODE(inode) &&
 238 -                   inode->pos == oldtnode->pos + oldtnode->bits &&
 239 -                   inode->bits > 1) {
 240 +               inode = tnode_get_child(oldtnode, i);
 241 +               if (tnode_full(oldtnode, inode) && inode->bits > 1) {
 242                         struct tnode *left, *right;
 243                         t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
 244
 245 @@ -711,33 +691,29 @@ static struct tnode *inflate(struct trie
 246                                 goto nomem;
 247                         }
 248
 249 -                       put_child(tn, 2*i, (struct rt_trie_node *) left);
 250 -                       put_child(tn, 2*i+1, (struct rt_trie_node *) right);
 251 +                       put_child(tn, 2*i, left);
 252 +                       put_child(tn, 2*i+1, right);
 253                 }
 254         }
 255
 256         for (i = 0; i < olen; i++) {
 257 -               struct tnode *inode;
 258 -               struct rt_trie_node *node = tnode_get_child(oldtnode, i);
 259 +               struct tnode *inode = tnode_get_child(oldtnode, i);
 260                 struct tnode *left, *right;
 261                 int size, j;
 262
 263                 /* An empty child */
 264 -               if (node == NULL)
 265 +               if (inode == NULL)
 266                         continue;
 267
 268                 /* A leaf or an internal node with skipped bits */
 269 -
 270 -               if (IS_LEAF(node) || (node->pos > (tn->pos + tn->bits - 1))) {
 271 +               if (!tnode_full(oldtnode, inode)) {
 272                         put_child(tn,
 273 -                               tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
 274 -                               node);
 275 +                               tkey_extract_bits(inode->key, tn->pos, tn->bits),
 276 +                               inode);
 277                         continue;
 278                 }
 279
 280                 /* An internal node with two children */
 281 -               inode = (struct tnode *) node;
 282 -
 283                 if (inode->bits == 1) {
 284                         put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
 285                         put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
 286 @@ -769,12 +745,12 @@ static struct tnode *inflate(struct trie
 287                  *   bit to zero.
 288                  */
 289
 290 -               left = (struct tnode *) tnode_get_child(tn, 2*i);
 291 +               left = tnode_get_child(tn, 2*i);
 292                 put_child(tn, 2*i, NULL);
 293
 294                 BUG_ON(!left);
 295
 296 -               right = (struct tnode *) tnode_get_child(tn, 2*i+1);
 297 +               right = tnode_get_child(tn, 2*i+1);
 298                 put_child(tn, 2*i+1, NULL);
 299
 300                 BUG_ON(!right);
 301 @@ -796,12 +772,11 @@ nomem:
 302         return ERR_PTR(-ENOMEM);
 303  }
 304
 305 -static struct tnode *halve(struct trie *t, struct tnode *tn)
 306 +static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
 307  {
 308 -       struct tnode *oldtnode = tn;
 309 -       struct rt_trie_node *left, *right;
 310 +       int olen = tnode_child_length(oldtnode);
 311 +       struct tnode *tn, *left, *right;
 312         int i;
 313 -       int olen = tnode_child_length(tn);
 314
 315         pr_debug("In halve\n");
 316
 317 @@ -830,7 +805,7 @@ static struct tnode *halve(struct trie *
 318                         if (!newn)
 319                                 goto nomem;
 320
 321 -                       put_child(tn, i/2, (struct rt_trie_node *)newn);
 322 +                       put_child(tn, i/2, newn);
 323                 }
 324
 325         }
 326 @@ -855,7 +830,7 @@ static struct tnode *halve(struct trie *
 327                 }
 328
 329                 /* Two nonempty children */
 330 -               newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
 331 +               newBinNode = tnode_get_child(tn, i/2);
 332                 put_child(tn, i/2, NULL);
 333                 put_child(newBinNode, 0, left);
 334                 put_child(newBinNode, 1, right);
 335 @@ -871,7 +846,7 @@ nomem:
 336  /* readside must use rcu_read_lock currently dump routines
 337   via get_fa_head and dump */
 338
 339 -static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
 340 +static struct leaf_info *find_leaf_info(struct tnode *l, int plen)
 341  {
 342         struct hlist_head *head = &l->list;
 343         struct leaf_info *li;
 344 @@ -883,7 +858,7 @@ static struct leaf_info *find_leaf_info(
 345         return NULL;
 346  }
 347
 348 -static inline struct list_head *get_fa_head(struct leaf *l, int plen)
 349 +static inline struct list_head *get_fa_head(struct tnode *l, int plen)
 350  {
 351         struct leaf_info *li = find_leaf_info(l, plen);
 352
 353 @@ -915,32 +890,25 @@ static void insert_leaf_info(struct hlis
 354
 355  /* rcu_read_lock needs to be hold by caller from readside */
 356
 357 -static struct leaf *
 358 -fib_find_node(struct trie *t, u32 key)
 359 +static struct tnode *fib_find_node(struct trie *t, u32 key)
 360  {
 361 -       int pos;
 362 -       struct tnode *tn;
 363 -       struct rt_trie_node *n;
 364 -
 365 -       pos = 0;
 366 -       n = rcu_dereference_rtnl(t->trie);
 367 +       struct tnode *n = rcu_dereference_rtnl(t->trie);
 368 +       int pos = 0;
 369
 370         while (n && IS_TNODE(n)) {
 371 -               tn = (struct tnode *) n;
 372 -
 373 -               if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
 374 -                       pos = tn->pos + tn->bits;
 375 -                       n = tnode_get_child_rcu(tn,
 376 +               if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
 377 +                       pos = n->pos + n->bits;
 378 +                       n = tnode_get_child_rcu(n,
 379                                                 tkey_extract_bits(key,
 380 -                                                                 tn->pos,
 381 -                                                                 tn->bits));
 382 +                                                                 n->pos,
 383 +                                                                 n->bits));
 384                 } else
 385                         break;
 386         }
 387         /* Case we have found a leaf. Compare prefixes */
 388
 389         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
 390 -               return (struct leaf *)n;
 391 +               return n;
 392
 393         return NULL;
 394  }
 395 @@ -956,14 +924,13 @@ static void trie_rebalance(struct trie *
 396         while (tn != NULL && (tp = node_parent(tn)) != NULL) {
 397                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 398                 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
 399 -               tn = (struct tnode *)resize(t, tn);
 400 +               tn = resize(t, tn);
 401
 402 -               tnode_put_child_reorg(tp, cindex,
 403 -                                     (struct rt_trie_node *)tn, wasfull);
 404 +               tnode_put_child_reorg(tp, cindex, tn, wasfull);
 405
 406                 tp = node_parent(tn);
 407                 if (!tp)
 408 -                       rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
 409 +                       rcu_assign_pointer(t->trie, tn);
 410
 411                 tnode_free_flush();
 412                 if (!tp)
 413 @@ -973,9 +940,9 @@ static void trie_rebalance(struct trie *
 414
 415         /* Handle last (top) tnode */
 416         if (IS_TNODE(tn))
 417 -               tn = (struct tnode *)resize(t, tn);
 418 +               tn = resize(t, tn);
 419
 420 -       rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
 421 +       rcu_assign_pointer(t->trie, tn);
 422         tnode_free_flush();
 423  }
 424
 425 @@ -985,8 +952,8 @@ static struct list_head *fib_insert_node
 426  {
 427         int pos, newpos;
 428         struct tnode *tp = NULL, *tn = NULL;
 429 -       struct rt_trie_node *n;
 430 -       struct leaf *l;
 431 +       struct tnode *n;
 432 +       struct tnode *l;
 433         int missbit;
 434         struct list_head *fa_head = NULL;
 435         struct leaf_info *li;
 436 @@ -1014,17 +981,15 @@ static struct list_head *fib_insert_node
 437          */
 438
 439         while (n && IS_TNODE(n)) {
 440 -               tn = (struct tnode *) n;
 441 -
 442 -               if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
 443 -                       tp = tn;
 444 -                       pos = tn->pos + tn->bits;
 445 -                       n = tnode_get_child(tn,
 446 +               if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
 447 +                       tp = n;
 448 +                       pos = n->pos + n->bits;
 449 +                       n = tnode_get_child(n,
 450                                             tkey_extract_bits(key,
 451 -                                                             tn->pos,
 452 -                                                             tn->bits));
 453 +                                                             n->pos,
 454 +                                                             n->bits));
 455
 456 -                       BUG_ON(n && node_parent(n) != tn);
 457 +                       BUG_ON(n && node_parent(n) != tp);
 458                 } else
 459                         break;
 460         }
 461 @@ -1040,14 +1005,13 @@ static struct list_head *fib_insert_node
 462         /* Case 1: n is a leaf. Compare prefixes */
 463
 464         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
 465 -               l = (struct leaf *) n;
 466                 li = leaf_info_new(plen);
 467
 468                 if (!li)
 469                         return NULL;
 470
 471                 fa_head = &li->falh;
 472 -               insert_leaf_info(&l->list, li);
 473 +               insert_leaf_info(&n->list, li);
 474                 goto done;
 475         }
 476         l = leaf_new(key);
 477 @@ -1068,10 +1032,10 @@ static struct list_head *fib_insert_node
 478         if (t->trie && n == NULL) {
 479                 /* Case 2: n is NULL, and will just insert a new leaf */
 480
 481 -               node_set_parent((struct rt_trie_node *)l, tp);
 482 +               node_set_parent(l, tp);
 483
 484                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 485 -               put_child(tp, cindex, (struct rt_trie_node *)l);
 486 +               put_child(tp, cindex, l);
 487         } else {
 488                 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
 489                 /*
 490 @@ -1094,17 +1058,17 @@ static struct list_head *fib_insert_node
 491                         return NULL;
 492                 }
 493
 494 -               node_set_parent((struct rt_trie_node *)tn, tp);
 495 +               node_set_parent(tn, tp);
 496
 497                 missbit = tkey_extract_bits(key, newpos, 1);
 498 -               put_child(tn, missbit, (struct rt_trie_node *)l);
 499 +               put_child(tn, missbit, l);
 500                 put_child(tn, 1-missbit, n);
 501
 502                 if (tp) {
 503                         cindex = tkey_extract_bits(key, tp->pos, tp->bits);
 504 -                       put_child(tp, cindex, (struct rt_trie_node *)tn);
 505 +                       put_child(tp, cindex, tn);
 506                 } else {
 507 -                       rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
 508 +                       rcu_assign_pointer(t->trie, tn);
 509                 }
 510
 511                 tp = tn;
 512 @@ -1134,7 +1098,7 @@ int fib_table_insert(struct fib_table *t
 513         u8 tos = cfg->fc_tos;
 514         u32 key, mask;
 515         int err;
 516 -       struct leaf *l;
 517 +       struct tnode *l;
 518
 519         if (plen > 32)
 520                 return -EINVAL;
 521 @@ -1292,7 +1256,7 @@ err:
 522  }
 523
 524  /* should be called with rcu_read_lock */
 525 -static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
 526 +static int check_leaf(struct fib_table *tb, struct trie *t, struct tnode *l,
 527                       t_key key,  const struct flowi4 *flp,
 528                       struct fib_result *res, int fib_flags)
 529  {
 530 @@ -1365,7 +1329,7 @@ int fib_table_lookup(struct fib_table *t
 531         struct trie_use_stats __percpu *stats = t->stats;
 532  #endif
 533         int ret;
 534 -       struct rt_trie_node *n;
 535 +       struct tnode *n;
 536         struct tnode *pn;
 537         unsigned int pos, bits;
 538         t_key key = ntohl(flp->daddr);
 539 @@ -1387,11 +1351,11 @@ int fib_table_lookup(struct fib_table *t
 540
 541         /* Just a leaf? */
 542         if (IS_LEAF(n)) {
 543 -               ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
 544 +               ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
 545                 goto found;
 546         }
 547
 548 -       pn = (struct tnode *) n;
 549 +       pn = n;
 550         chopped_off = 0;
 551
 552         while (pn) {
 553 @@ -1412,13 +1376,13 @@ int fib_table_lookup(struct fib_table *t
 554                 }
 555
 556                 if (IS_LEAF(n)) {
 557 -                       ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
 558 +                       ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
 559                         if (ret > 0)
 560                                 goto backtrace;
 561                         goto found;
 562                 }
 563
 564 -               cn = (struct tnode *)n;
 565 +               cn = n;
 566
 567                 /*
 568                  * It's a tnode, and we can do some extra checks here if we
 569 @@ -1506,7 +1470,7 @@ int fib_table_lookup(struct fib_table *t
 570                                 current_prefix_length = mp;
 571                 }
 572
 573 -               pn = (struct tnode *)n; /* Descend */
 574 +               pn = n; /* Descend */
 575                 chopped_off = 0;
 576                 continue;
 577
 578 @@ -1557,7 +1521,7 @@ EXPORT_SYMBOL_GPL(fib_table_lookup);
 579  /*
 580   * Remove the leaf and return parent.
 581   */
 582 -static void trie_leaf_remove(struct trie *t, struct leaf *l)
 583 +static void trie_leaf_remove(struct trie *t, struct tnode *l)
 584  {
 585         struct tnode *tp = node_parent(l);
 586
 587 @@ -1584,7 +1548,7 @@ int fib_table_delete(struct fib_table *t
 588         u8 tos = cfg->fc_tos;
 589         struct fib_alias *fa, *fa_to_delete;
 590         struct list_head *fa_head;
 591 -       struct leaf *l;
 592 +       struct tnode *l;
 593         struct leaf_info *li;
 594
 595         if (plen > 32)
 596 @@ -1682,7 +1646,7 @@ static int trie_flush_list(struct list_h
 597         return found;
 598  }
 599
 600 -static int trie_flush_leaf(struct leaf *l)
 601 +static int trie_flush_leaf(struct tnode *l)
 602  {
 603         int found = 0;
 604         struct hlist_head *lih = &l->list;
 605 @@ -1704,7 +1668,7 @@ static int trie_flush_leaf(struct leaf *
 606   * Scan for the next right leaf starting at node p->child[idx]
 607   * Since we have back pointer, no recursion necessary.
 608   */
 609 -static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
 610 +static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c)
 611  {
 612         do {
 613                 t_key idx;
 614 @@ -1720,47 +1684,46 @@ static struct leaf *leaf_walk_rcu(struct
 615                                 continue;
 616
 617                         if (IS_LEAF(c))
 618 -                               return (struct leaf *) c;
 619 +                               return c;
 620
 621                         /* Rescan start scanning in new node */
 622 -                       p = (struct tnode *) c;
 623 +                       p = c;
 624                         idx = 0;
 625                 }
 626
 627                 /* Node empty, walk back up to parent */
 628 -               c = (struct rt_trie_node *) p;
 629 +               c = p;
 630         } while ((p = node_parent_rcu(c)) != NULL);
 631
 632         return NULL; /* Root of trie */
 633  }
 634
 635 -static struct leaf *trie_firstleaf(struct trie *t)
 636 +static struct tnode *trie_firstleaf(struct trie *t)
 637  {
 638 -       struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
 639 +       struct tnode *n = rcu_dereference_rtnl(t->trie);
 640
 641         if (!n)
 642                 return NULL;
 643
 644         if (IS_LEAF(n))          /* trie is just a leaf */
 645 -               return (struct leaf *) n;
 646 +               return n;
 647
 648         return leaf_walk_rcu(n, NULL);
 649  }
 650
 651 -static struct leaf *trie_nextleaf(struct leaf *l)
 652 +static struct tnode *trie_nextleaf(struct tnode *l)
 653  {
 654 -       struct rt_trie_node *c = (struct rt_trie_node *) l;
 655 -       struct tnode *p = node_parent_rcu(c);
 656 +       struct tnode *p = node_parent_rcu(l);
 657
 658         if (!p)
 659                 return NULL;    /* trie with just one leaf */
 660
 661 -       return leaf_walk_rcu(p, c);
 662 +       return leaf_walk_rcu(p, l);
 663  }
 664
 665 -static struct leaf *trie_leafindex(struct trie *t, int index)
 666 +static struct tnode *trie_leafindex(struct trie *t, int index)
 667  {
 668 -       struct leaf *l = trie_firstleaf(t);
 669 +       struct tnode *l = trie_firstleaf(t);
 670
 671         while (l && index-- > 0)
 672                 l = trie_nextleaf(l);
 673 @@ -1775,7 +1738,7 @@ static struct leaf *trie_leafindex(struc
 674  int fib_table_flush(struct fib_table *tb)
 675  {
 676         struct trie *t = (struct trie *) tb->tb_data;
 677 -       struct leaf *l, *ll = NULL;
 678 +       struct tnode *l, *ll = NULL;
 679         int found = 0;
 680
 681         for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
 682 @@ -1840,7 +1803,7 @@ static int fn_trie_dump_fa(t_key key, in
 683         return skb->len;
 684  }
 685
 686 -static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
 687 +static int fn_trie_dump_leaf(struct tnode *l, struct fib_table *tb,
 688                         struct sk_buff *skb, struct netlink_callback *cb)
 689  {
 690         struct leaf_info *li;
 691 @@ -1876,7 +1839,7 @@ static int fn_trie_dump_leaf(struct leaf
 692  int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
 693                    struct netlink_callback *cb)
 694  {
 695 -       struct leaf *l;
 696 +       struct tnode *l;
 697         struct trie *t = (struct trie *) tb->tb_data;
 698         t_key key = cb->args[2];
 699         int count = cb->args[3];
 700 @@ -1922,7 +1885,7 @@ void __init fib_trie_init(void)
 701                                           0, SLAB_PANIC, NULL);
 702
 703         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
 704 -                                          max(sizeof(struct leaf),
 705 +                                          max(sizeof(struct tnode),
 706                                                sizeof(struct leaf_info)),
 707                                            0, SLAB_PANIC, NULL);
 708  }
 709 @@ -1965,7 +1928,7 @@ struct fib_trie_iter {
 710         unsigned int depth;
 711  };
 712
 713 -static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
 714 +static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
 715  {
 716         struct tnode *tn = iter->tnode;
 717         unsigned int cindex = iter->index;
 718 @@ -1979,7 +1942,7 @@ static struct rt_trie_node *fib_trie_get
 719                  iter->tnode, iter->index, iter->depth);
 720  rescan:
 721         while (cindex < (1<<tn->bits)) {
 722 -               struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
 723 +               struct tnode *n = tnode_get_child_rcu(tn, cindex);
 724
 725                 if (n) {
 726                         if (IS_LEAF(n)) {
 727 @@ -1987,7 +1950,7 @@ rescan:
 728                                 iter->index = cindex + 1;
 729                         } else {
 730                                 /* push down one level */
 731 -                               iter->tnode = (struct tnode *) n;
 732 +                               iter->tnode = n;
 733                                 iter->index = 0;
 734                                 ++iter->depth;
 735                         }
 736 @@ -1998,7 +1961,7 @@ rescan:
 737         }
 738
 739         /* Current node exhausted, pop back up */
 740 -       p = node_parent_rcu((struct rt_trie_node *)tn);
 741 +       p = node_parent_rcu(tn);
 742         if (p) {
 743                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
 744                 tn = p;
 745 @@ -2010,10 +1973,10 @@ rescan:
 746         return NULL;
 747  }
 748
 749 -static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
 750 +static struct tnode *fib_trie_get_first(struct fib_trie_iter *iter,
 751                                        struct trie *t)
 752  {
 753 -       struct rt_trie_node *n;
 754 +       struct tnode *n;
 755
 756         if (!t)
 757                 return NULL;
 758 @@ -2023,7 +1986,7 @@ static struct rt_trie_node *fib_trie_get
 759                 return NULL;
 760
 761         if (IS_TNODE(n)) {
 762 -               iter->tnode = (struct tnode *) n;
 763 +               iter->tnode = n;
 764                 iter->index = 0;
 765                 iter->depth = 1;
 766         } else {
 767 @@ -2037,7 +2000,7 @@ static struct rt_trie_node *fib_trie_get
 768
 769  static void trie_collect_stats(struct trie *t, struct trie_stat *s)
 770  {
 771 -       struct rt_trie_node *n;
 772 +       struct tnode *n;
 773         struct fib_trie_iter iter;
 774
 775         memset(s, 0, sizeof(*s));
 776 @@ -2045,7 +2008,6 @@ static void trie_collect_stats(struct tr
 777         rcu_read_lock();
 778         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
 779                 if (IS_LEAF(n)) {
 780 -                       struct leaf *l = (struct leaf *)n;
 781                         struct leaf_info *li;
 782
 783                         s->leaves++;
 784 @@ -2053,18 +2015,17 @@ static void trie_collect_stats(struct tr
 785                         if (iter.depth > s->maxdepth)
 786                                 s->maxdepth = iter.depth;
 787
 788 -                       hlist_for_each_entry_rcu(li, &l->list, hlist)
 789 +                       hlist_for_each_entry_rcu(li, &n->list, hlist)
 790                                 ++s->prefixes;
 791                 } else {
 792 -                       const struct tnode *tn = (const struct tnode *) n;
 793                         int i;
 794
 795                         s->tnodes++;
 796 -                       if (tn->bits < MAX_STAT_DEPTH)
 797 -                               s->nodesizes[tn->bits]++;
 798 +                       if (n->bits < MAX_STAT_DEPTH)
 799 +                               s->nodesizes[n->bits]++;
 800
 801 -                       for (i = 0; i < (1<<tn->bits); i++)
 802 -                               if (!tn->child[i])
 803 +                       for (i = 0; i < tnode_child_length(n); i++)
 804 +                               if (!rcu_access_pointer(n->child[i]))
 805                                         s->nullpointers++;
 806                 }
 807         }
 808 @@ -2088,7 +2049,7 @@ static void trie_show_stats(struct seq_f
 809         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
 810
 811         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
 812 -       bytes = sizeof(struct leaf) * stat->leaves;
 813 +       bytes = sizeof(struct tnode) * stat->leaves;
 814
 815         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
 816         bytes += sizeof(struct leaf_info) * stat->prefixes;
 817 @@ -2109,7 +2070,7 @@ static void trie_show_stats(struct seq_f
 818         seq_putc(seq, '\n');
 819         seq_printf(seq, "\tPointers: %u\n", pointers);
 820
 821 -       bytes += sizeof(struct rt_trie_node *) * pointers;
 822 +       bytes += sizeof(struct tnode *) * pointers;
 823         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
 824         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
 825  }
 826 @@ -2163,7 +2124,7 @@ static int fib_triestat_seq_show(struct
 827         seq_printf(seq,
 828                    "Basic info: size of leaf:"
 829                    " %Zd bytes, size of tnode: %Zd bytes.\n",
 830 -                  sizeof(struct leaf), sizeof(struct tnode));
 831 +                  sizeof(struct tnode), sizeof(struct tnode));
 832
 833         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
 834                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
 835 @@ -2202,7 +2163,7 @@ static const struct file_operations fib_
 836         .release = single_release_net,
 837  };
 838
 839 -static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
 840 +static struct tnode *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
 841  {
 842         struct fib_trie_iter *iter = seq->private;
 843         struct net *net = seq_file_net(seq);
 844 @@ -2214,7 +2175,7 @@ static struct rt_trie_node *fib_trie_get
 845                 struct fib_table *tb;
 846
 847                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
 848 -                       struct rt_trie_node *n;
 849 +                       struct tnode *n;
 850
 851                         for (n = fib_trie_get_first(iter,
 852                                                     (struct trie *) tb->tb_data);
 853 @@ -2243,7 +2204,7 @@ static void *fib_trie_seq_next(struct se
 854         struct fib_table *tb = iter->tb;
 855         struct hlist_node *tb_node;
 856         unsigned int h;
 857 -       struct rt_trie_node *n;
 858 +       struct tnode *n;
 859
 860         ++*pos;
 861         /* next node in same table */
 862 @@ -2329,29 +2290,26 @@ static inline const char *rtn_type(char
 863  static int fib_trie_seq_show(struct seq_file *seq, void *v)
 864  {
 865         const struct fib_trie_iter *iter = seq->private;
 866 -       struct rt_trie_node *n = v;
 867 +       struct tnode *n = v;
 868
 869         if (!node_parent_rcu(n))
 870                 fib_table_print(seq, iter->tb);
 871
 872         if (IS_TNODE(n)) {
 873 -               struct tnode *tn = (struct tnode *) n;
 874 -               __be32 prf = htonl(tn->key);
 875 +               __be32 prf = htonl(n->key);
 876
 877 -               seq_indent(seq, iter->depth-1);
 878 +               seq_indent(seq, iter->depth - 1);
 879                 seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
 880 -                          &prf, tn->pos, tn->bits, tn->full_children,
 881 -                          tn->empty_children);
 882 -
 883 +                          &prf, n->pos, n->bits, n->full_children,
 884 +                          n->empty_children);
 885         } else {
 886 -               struct leaf *l = (struct leaf *) n;
 887                 struct leaf_info *li;
 888 -               __be32 val = htonl(l->key);
 889 +               __be32 val = htonl(n->key);
 890
 891                 seq_indent(seq, iter->depth);
 892                 seq_printf(seq, "  |-- %pI4\n", &val);
 893
 894 -               hlist_for_each_entry_rcu(li, &l->list, hlist) {
 895 +               hlist_for_each_entry_rcu(li, &n->list, hlist) {
 896                         struct fib_alias *fa;
 897
 898                         list_for_each_entry_rcu(fa, &li->falh, fa_list) {
 899 @@ -2401,9 +2359,9 @@ struct fib_route_iter {
 900         t_key   key;
 901  };
 902
 903 -static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
 904 +static struct tnode *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
 905  {
 906 -       struct leaf *l = NULL;
 907 +       struct tnode *l = NULL;
 908         struct trie *t = iter->main_trie;
 909
 910         /* use cache location of last found key */
 911 @@ -2448,7 +2406,7 @@ static void *fib_route_seq_start(struct
 912  static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 913  {
 914         struct fib_route_iter *iter = seq->private;
 915 -       struct leaf *l = v;
 916 +       struct tnode *l = v;
 917
 918         ++*pos;
 919         if (v == SEQ_START_TOKEN) {
 920 @@ -2494,7 +2452,7 @@ static unsigned int fib_flag_trans(int t
 921   */
 922  static int fib_route_seq_show(struct seq_file *seq, void *v)
 923  {
 924 -       struct leaf *l = v;
 925 +       struct tnode *l = v;
 926         struct leaf_info *li;
 927
 928         if (v == SEQ_START_TOKEN) {