Version:  2.0.40 2.2.26 2.4.37 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19

Linux/net/ipv4/fib_trie.c

  1 /*
  2  *   This program is free software; you can redistribute it and/or
  3  *   modify it under the terms of the GNU General Public License
  4  *   as published by the Free Software Foundation; either version
  5  *   2 of the License, or (at your option) any later version.
  6  *
  7  *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
  8  *     & Swedish University of Agricultural Sciences.
  9  *
 10  *   Jens Laas <jens.laas@data.slu.se> Swedish University of
 11  *     Agricultural Sciences.
 12  *
 13  *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 14  *
 15  * This work is based on the LPC-trie which is originally described in:
 16  *
 17  * An experimental study of compression methods for dynamic tries
 18  * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
 19  * http://www.csc.kth.se/~snilsson/software/dyntrie2/
 20  *
 21  *
 22  * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
 23  * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
 24  *
 25  *
 26  * Code from fib_hash has been reused which includes the following header:
 27  *
 28  *
 29  * INET         An implementation of the TCP/IP protocol suite for the LINUX
 30  *              operating system.  INET is implemented using the  BSD Socket
 31  *              interface as the means of communication with the user level.
 32  *
 33  *              IPv4 FIB: lookup engine and maintenance routines.
 34  *
 35  *
 36  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 37  *
 38  *              This program is free software; you can redistribute it and/or
 39  *              modify it under the terms of the GNU General Public License
 40  *              as published by the Free Software Foundation; either version
 41  *              2 of the License, or (at your option) any later version.
 42  *
 43  * Substantial contributions to this work comes from:
 44  *
 45  *              David S. Miller, <davem@davemloft.net>
 46  *              Stephen Hemminger <shemminger@osdl.org>
 47  *              Paul E. McKenney <paulmck@us.ibm.com>
 48  *              Patrick McHardy <kaber@trash.net>
 49  */
 50 
 51 #define VERSION "0.409"
 52 
 53 #include <asm/uaccess.h>
 54 #include <linux/bitops.h>
 55 #include <linux/types.h>
 56 #include <linux/kernel.h>
 57 #include <linux/mm.h>
 58 #include <linux/string.h>
 59 #include <linux/socket.h>
 60 #include <linux/sockios.h>
 61 #include <linux/errno.h>
 62 #include <linux/in.h>
 63 #include <linux/inet.h>
 64 #include <linux/inetdevice.h>
 65 #include <linux/netdevice.h>
 66 #include <linux/if_arp.h>
 67 #include <linux/proc_fs.h>
 68 #include <linux/rcupdate.h>
 69 #include <linux/skbuff.h>
 70 #include <linux/netlink.h>
 71 #include <linux/init.h>
 72 #include <linux/list.h>
 73 #include <linux/slab.h>
 74 #include <linux/export.h>
 75 #include <net/net_namespace.h>
 76 #include <net/ip.h>
 77 #include <net/protocol.h>
 78 #include <net/route.h>
 79 #include <net/tcp.h>
 80 #include <net/sock.h>
 81 #include <net/ip_fib.h>
 82 #include "fib_lookup.h"
 83 
 84 #define MAX_STAT_DEPTH 32
 85 
 86 #define KEYLENGTH (8*sizeof(t_key))
 87 
 88 typedef unsigned int t_key;
 89 
 90 #define T_TNODE 0
 91 #define T_LEAF  1
 92 #define NODE_TYPE_MASK  0x1UL
 93 #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
 94 
 95 #define IS_TNODE(n) (!(n->parent & T_LEAF))
 96 #define IS_LEAF(n) (n->parent & T_LEAF)
 97 
 98 struct rt_trie_node {
 99         unsigned long parent;
100         t_key key;
101 };
102 
103 struct leaf {
104         unsigned long parent;
105         t_key key;
106         struct hlist_head list;
107         struct rcu_head rcu;
108 };
109 
110 struct leaf_info {
111         struct hlist_node hlist;
112         int plen;
113         u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
114         struct list_head falh;
115         struct rcu_head rcu;
116 };
117 
118 struct tnode {
119         unsigned long parent;
120         t_key key;
121         unsigned char pos;              /* 2log(KEYLENGTH) bits needed */
122         unsigned char bits;             /* 2log(KEYLENGTH) bits needed */
123         unsigned int full_children;     /* KEYLENGTH bits needed */
124         unsigned int empty_children;    /* KEYLENGTH bits needed */
125         union {
126                 struct rcu_head rcu;
127                 struct tnode *tnode_free;
128         };
129         struct rt_trie_node __rcu *child[0];
130 };
131 
132 #ifdef CONFIG_IP_FIB_TRIE_STATS
133 struct trie_use_stats {
134         unsigned int gets;
135         unsigned int backtrack;
136         unsigned int semantic_match_passed;
137         unsigned int semantic_match_miss;
138         unsigned int null_node_hit;
139         unsigned int resize_node_skipped;
140 };
141 #endif
142 
143 struct trie_stat {
144         unsigned int totdepth;
145         unsigned int maxdepth;
146         unsigned int tnodes;
147         unsigned int leaves;
148         unsigned int nullpointers;
149         unsigned int prefixes;
150         unsigned int nodesizes[MAX_STAT_DEPTH];
151 };
152 
153 struct trie {
154         struct rt_trie_node __rcu *trie;
155 #ifdef CONFIG_IP_FIB_TRIE_STATS
156         struct trie_use_stats stats;
157 #endif
158 };
159 
160 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
161                                   int wasfull);
162 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
163 static struct tnode *inflate(struct trie *t, struct tnode *tn);
164 static struct tnode *halve(struct trie *t, struct tnode *tn);
165 /* tnodes to free after resize(); protected by RTNL */
166 static struct tnode *tnode_free_head;
167 static size_t tnode_free_size;
168 
169 /*
170  * synchronize_rcu after call_rcu for that many pages; it should be especially
171  * useful before resizing the root node with PREEMPT_NONE configs; the value was
172  * obtained experimentally, aiming to avoid visible slowdown.
173  */
174 static const int sync_pages = 128;
175 
176 static struct kmem_cache *fn_alias_kmem __read_mostly;
177 static struct kmem_cache *trie_leaf_kmem __read_mostly;
178 
179 /*
180  * caller must hold RTNL
181  */
182 static inline struct tnode *node_parent(const struct rt_trie_node *node)
183 {
184         unsigned long parent;
185 
186         parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
187 
188         return (struct tnode *)(parent & ~NODE_TYPE_MASK);
189 }
190 
191 /*
192  * caller must hold RCU read lock or RTNL
193  */
194 static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
195 {
196         unsigned long parent;
197 
198         parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
199                                                            lockdep_rtnl_is_held());
200 
201         return (struct tnode *)(parent & ~NODE_TYPE_MASK);
202 }
203 
204 /* Same as rcu_assign_pointer
205  * but that macro() assumes that value is a pointer.
206  */
207 static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
208 {
209         smp_wmb();
210         node->parent = (unsigned long)ptr | NODE_TYPE(node);
211 }
212 
213 /*
214  * caller must hold RTNL
215  */
216 static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
217 {
218         BUG_ON(i >= 1U << tn->bits);
219 
220         return rtnl_dereference(tn->child[i]);
221 }
222 
223 /*
224  * caller must hold RCU read lock or RTNL
225  */
226 static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
227 {
228         BUG_ON(i >= 1U << tn->bits);
229 
230         return rcu_dereference_rtnl(tn->child[i]);
231 }
232 
233 static inline int tnode_child_length(const struct tnode *tn)
234 {
235         return 1 << tn->bits;
236 }
237 
238 static inline t_key mask_pfx(t_key k, unsigned int l)
239 {
240         return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
241 }
242 
243 static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
244 {
245         if (offset < KEYLENGTH)
246                 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
247         else
248                 return 0;
249 }
250 
251 static inline int tkey_equals(t_key a, t_key b)
252 {
253         return a == b;
254 }
255 
256 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
257 {
258         if (bits == 0 || offset >= KEYLENGTH)
259                 return 1;
260         bits = bits > KEYLENGTH ? KEYLENGTH : bits;
261         return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
262 }
263 
264 static inline int tkey_mismatch(t_key a, int offset, t_key b)
265 {
266         t_key diff = a ^ b;
267         int i = offset;
268 
269         if (!diff)
270                 return 0;
271         while ((diff << i) >> (KEYLENGTH-1) == 0)
272                 i++;
273         return i;
274 }
275 
276 /*
277   To understand this stuff, an understanding of keys and all their bits is
278   necessary. Every node in the trie has a key associated with it, but not
279   all of the bits in that key are significant.
280 
281   Consider a node 'n' and its parent 'tp'.
282 
283   If n is a leaf, every bit in its key is significant. Its presence is
284   necessitated by path compression, since during a tree traversal (when
285   searching for a leaf - unless we are doing an insertion) we will completely
286   ignore all skipped bits we encounter. Thus we need to verify, at the end of
287   a potentially successful search, that we have indeed been walking the
288   correct key path.
289 
290   Note that we can never "miss" the correct key in the tree if present by
291   following the wrong path. Path compression ensures that segments of the key
292   that are the same for all keys with a given prefix are skipped, but the
293   skipped part *is* identical for each node in the subtrie below the skipped
294   bit! trie_insert() in this implementation takes care of that - note the
295   call to tkey_sub_equals() in trie_insert().
296 
297   if n is an internal node - a 'tnode' here, the various parts of its key
298   have many different meanings.
299 
300   Example:
301   _________________________________________________________________
302   | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
303   -----------------------------------------------------------------
304     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
305 
306   _________________________________________________________________
307   | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
308   -----------------------------------------------------------------
309    16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
310 
311   tp->pos = 7
312   tp->bits = 3
313   n->pos = 15
314   n->bits = 4
315 
316   First, let's just ignore the bits that come before the parent tp, that is
317   the bits from 0 to (tp->pos-1). They are *known* but at this point we do
318   not use them for anything.
319 
320   The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
321   index into the parent's child array. That is, they will be used to find
322   'n' among tp's children.
323 
324   The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
325   for the node n.
326 
327   All the bits we have seen so far are significant to the node n. The rest
328   of the bits are really not needed or indeed known in n->key.
329 
330   The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
331   n's child array, and will of course be different for each child.
332 
333 
334   The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
335   at this point.
336 
337 */
338 
339 static inline void check_tnode(const struct tnode *tn)
340 {
341         WARN_ON(tn && tn->pos+tn->bits > 32);
342 }
343 
344 static const int halve_threshold = 25;
345 static const int inflate_threshold = 50;
346 static const int halve_threshold_root = 15;
347 static const int inflate_threshold_root = 30;
348 
349 static void __alias_free_mem(struct rcu_head *head)
350 {
351         struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
352         kmem_cache_free(fn_alias_kmem, fa);
353 }
354 
355 static inline void alias_free_mem_rcu(struct fib_alias *fa)
356 {
357         call_rcu(&fa->rcu, __alias_free_mem);
358 }
359 
360 static void __leaf_free_rcu(struct rcu_head *head)
361 {
362         struct leaf *l = container_of(head, struct leaf, rcu);
363         kmem_cache_free(trie_leaf_kmem, l);
364 }
365 
366 static inline void free_leaf(struct leaf *l)
367 {
368         call_rcu(&l->rcu, __leaf_free_rcu);
369 }
370 
371 static inline void free_leaf_info(struct leaf_info *leaf)
372 {
373         kfree_rcu(leaf, rcu);
374 }
375 
376 static struct tnode *tnode_alloc(size_t size)
377 {
378         if (size <= PAGE_SIZE)
379                 return kzalloc(size, GFP_KERNEL);
380         else
381                 return vzalloc(size);
382 }
383 
384 static void __tnode_free_rcu(struct rcu_head *head)
385 {
386         struct tnode *tn = container_of(head, struct tnode, rcu);
387         size_t size = sizeof(struct tnode) +
388                       (sizeof(struct rt_trie_node *) << tn->bits);
389 
390         if (size <= PAGE_SIZE)
391                 kfree(tn);
392         else
393                 vfree(tn);
394 }
395 
396 static inline void tnode_free(struct tnode *tn)
397 {
398         if (IS_LEAF(tn))
399                 free_leaf((struct leaf *) tn);
400         else
401                 call_rcu(&tn->rcu, __tnode_free_rcu);
402 }
403 
404 static void tnode_free_safe(struct tnode *tn)
405 {
406         BUG_ON(IS_LEAF(tn));
407         tn->tnode_free = tnode_free_head;
408         tnode_free_head = tn;
409         tnode_free_size += sizeof(struct tnode) +
410                            (sizeof(struct rt_trie_node *) << tn->bits);
411 }
412 
413 static void tnode_free_flush(void)
414 {
415         struct tnode *tn;
416 
417         while ((tn = tnode_free_head)) {
418                 tnode_free_head = tn->tnode_free;
419                 tn->tnode_free = NULL;
420                 tnode_free(tn);
421         }
422 
423         if (tnode_free_size >= PAGE_SIZE * sync_pages) {
424                 tnode_free_size = 0;
425                 synchronize_rcu();
426         }
427 }
428 
429 static struct leaf *leaf_new(void)
430 {
431         struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
432         if (l) {
433                 l->parent = T_LEAF;
434                 INIT_HLIST_HEAD(&l->list);
435         }
436         return l;
437 }
438 
439 static struct leaf_info *leaf_info_new(int plen)
440 {
441         struct leaf_info *li = kmalloc(sizeof(struct leaf_info),  GFP_KERNEL);
442         if (li) {
443                 li->plen = plen;
444                 li->mask_plen = ntohl(inet_make_mask(plen));
445                 INIT_LIST_HEAD(&li->falh);
446         }
447         return li;
448 }
449 
450 static struct tnode *tnode_new(t_key key, int pos, int bits)
451 {
452         size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
453         struct tnode *tn = tnode_alloc(sz);
454 
455         if (tn) {
456                 tn->parent = T_TNODE;
457                 tn->pos = pos;
458                 tn->bits = bits;
459                 tn->key = key;
460                 tn->full_children = 0;
461                 tn->empty_children = 1<<bits;
462         }
463 
464         pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
465                  sizeof(struct rt_trie_node *) << bits);
466         return tn;
467 }
468 
469 /*
470  * Check whether a tnode 'n' is "full", i.e. it is an internal node
471  * and no bits are skipped. See discussion in dyntree paper p. 6
472  */
473 
474 static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
475 {
476         if (n == NULL || IS_LEAF(n))
477                 return 0;
478 
479         return ((struct tnode *) n)->pos == tn->pos + tn->bits;
480 }
481 
482 static inline void put_child(struct tnode *tn, int i,
483                              struct rt_trie_node *n)
484 {
485         tnode_put_child_reorg(tn, i, n, -1);
486 }
487 
488  /*
489   * Add a child at position i overwriting the old value.
490   * Update the value of full_children and empty_children.
491   */
492 
493 static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
494                                   int wasfull)
495 {
496         struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
497         int isfull;
498 
499         BUG_ON(i >= 1<<tn->bits);
500 
501         /* update emptyChildren */
502         if (n == NULL && chi != NULL)
503                 tn->empty_children++;
504         else if (n != NULL && chi == NULL)
505                 tn->empty_children--;
506 
507         /* update fullChildren */
508         if (wasfull == -1)
509                 wasfull = tnode_full(tn, chi);
510 
511         isfull = tnode_full(tn, n);
512         if (wasfull && !isfull)
513                 tn->full_children--;
514         else if (!wasfull && isfull)
515                 tn->full_children++;
516 
517         if (n)
518                 node_set_parent(n, tn);
519 
520         rcu_assign_pointer(tn->child[i], n);
521 }
522 
523 #define MAX_WORK 10
524 static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
525 {
526         int i;
527         struct tnode *old_tn;
528         int inflate_threshold_use;
529         int halve_threshold_use;
530         int max_work;
531 
532         if (!tn)
533                 return NULL;
534 
535         pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
536                  tn, inflate_threshold, halve_threshold);
537 
538         /* No children */
539         if (tn->empty_children == tnode_child_length(tn)) {
540                 tnode_free_safe(tn);
541                 return NULL;
542         }
543         /* One child */
544         if (tn->empty_children == tnode_child_length(tn) - 1)
545                 goto one_child;
546         /*
547          * Double as long as the resulting node has a number of
548          * nonempty nodes that are above the threshold.
549          */
550 
551         /*
552          * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
553          * the Helsinki University of Technology and Matti Tikkanen of Nokia
554          * Telecommunications, page 6:
555          * "A node is doubled if the ratio of non-empty children to all
556          * children in the *doubled* node is at least 'high'."
557          *
558          * 'high' in this instance is the variable 'inflate_threshold'. It
559          * is expressed as a percentage, so we multiply it with
560          * tnode_child_length() and instead of multiplying by 2 (since the
561          * child array will be doubled by inflate()) and multiplying
562          * the left-hand side by 100 (to handle the percentage thing) we
563          * multiply the left-hand side by 50.
564          *
565          * The left-hand side may look a bit weird: tnode_child_length(tn)
566          * - tn->empty_children is of course the number of non-null children
567          * in the current node. tn->full_children is the number of "full"
568          * children, that is non-null tnodes with a skip value of 0.
569          * All of those will be doubled in the resulting inflated tnode, so
570          * we just count them one extra time here.
571          *
572          * A clearer way to write this would be:
573          *
574          * to_be_doubled = tn->full_children;
575          * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
576          *     tn->full_children;
577          *
578          * new_child_length = tnode_child_length(tn) * 2;
579          *
580          * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
581          *      new_child_length;
582          * if (new_fill_factor >= inflate_threshold)
583          *
584          * ...and so on, tho it would mess up the while () loop.
585          *
586          * anyway,
587          * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
588          *      inflate_threshold
589          *
590          * avoid a division:
591          * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
592          *      inflate_threshold * new_child_length
593          *
594          * expand not_to_be_doubled and to_be_doubled, and shorten:
595          * 100 * (tnode_child_length(tn) - tn->empty_children +
596          *    tn->full_children) >= inflate_threshold * new_child_length
597          *
598          * expand new_child_length:
599          * 100 * (tnode_child_length(tn) - tn->empty_children +
600          *    tn->full_children) >=
601          *      inflate_threshold * tnode_child_length(tn) * 2
602          *
603          * shorten again:
604          * 50 * (tn->full_children + tnode_child_length(tn) -
605          *    tn->empty_children) >= inflate_threshold *
606          *    tnode_child_length(tn)
607          *
608          */
609 
610         check_tnode(tn);
611 
612         /* Keep root node larger  */
613 
614         if (!node_parent((struct rt_trie_node *)tn)) {
615                 inflate_threshold_use = inflate_threshold_root;
616                 halve_threshold_use = halve_threshold_root;
617         } else {
618                 inflate_threshold_use = inflate_threshold;
619                 halve_threshold_use = halve_threshold;
620         }
621 
622         max_work = MAX_WORK;
623         while ((tn->full_children > 0 &&  max_work-- &&
624                 50 * (tn->full_children + tnode_child_length(tn)
625                       - tn->empty_children)
626                 >= inflate_threshold_use * tnode_child_length(tn))) {
627 
628                 old_tn = tn;
629                 tn = inflate(t, tn);
630 
631                 if (IS_ERR(tn)) {
632                         tn = old_tn;
633 #ifdef CONFIG_IP_FIB_TRIE_STATS
634                         t->stats.resize_node_skipped++;
635 #endif
636                         break;
637                 }
638         }
639 
640         check_tnode(tn);
641 
642         /* Return if at least one inflate is run */
643         if (max_work != MAX_WORK)
644                 return (struct rt_trie_node *) tn;
645 
646         /*
647          * Halve as long as the number of empty children in this
648          * node is above threshold.
649          */
650 
651         max_work = MAX_WORK;
652         while (tn->bits > 1 &&  max_work-- &&
653                100 * (tnode_child_length(tn) - tn->empty_children) <
654                halve_threshold_use * tnode_child_length(tn)) {
655 
656                 old_tn = tn;
657                 tn = halve(t, tn);
658                 if (IS_ERR(tn)) {
659                         tn = old_tn;
660 #ifdef CONFIG_IP_FIB_TRIE_STATS
661                         t->stats.resize_node_skipped++;
662 #endif
663                         break;
664                 }
665         }
666 
667 
668         /* Only one child remains */
669         if (tn->empty_children == tnode_child_length(tn) - 1) {
670 one_child:
671                 for (i = 0; i < tnode_child_length(tn); i++) {
672                         struct rt_trie_node *n;
673 
674                         n = rtnl_dereference(tn->child[i]);
675                         if (!n)
676                                 continue;
677 
678                         /* compress one level */
679 
680                         node_set_parent(n, NULL);
681                         tnode_free_safe(tn);
682                         return n;
683                 }
684         }
685         return (struct rt_trie_node *) tn;
686 }
687 
688 
689 static void tnode_clean_free(struct tnode *tn)
690 {
691         int i;
692         struct tnode *tofree;
693 
694         for (i = 0; i < tnode_child_length(tn); i++) {
695                 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
696                 if (tofree)
697                         tnode_free(tofree);
698         }
699         tnode_free(tn);
700 }
701 
702 static struct tnode *inflate(struct trie *t, struct tnode *tn)
703 {
704         struct tnode *oldtnode = tn;
705         int olen = tnode_child_length(tn);
706         int i;
707 
708         pr_debug("In inflate\n");
709 
710         tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
711 
712         if (!tn)
713                 return ERR_PTR(-ENOMEM);
714 
715         /*
716          * Preallocate and store tnodes before the actual work so we
717          * don't get into an inconsistent state if memory allocation
718          * fails. In case of failure we return the oldnode and  inflate
719          * of tnode is ignored.
720          */
721 
722         for (i = 0; i < olen; i++) {
723                 struct tnode *inode;
724 
725                 inode = (struct tnode *) tnode_get_child(oldtnode, i);
726                 if (inode &&
727                     IS_TNODE(inode) &&
728                     inode->pos == oldtnode->pos + oldtnode->bits &&
729                     inode->bits > 1) {
730                         struct tnode *left, *right;
731                         t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
732 
733                         left = tnode_new(inode->key&(~m), inode->pos + 1,
734                                          inode->bits - 1);
735                         if (!left)
736                                 goto nomem;
737 
738                         right = tnode_new(inode->key|m, inode->pos + 1,
739                                           inode->bits - 1);
740 
741                         if (!right) {
742                                 tnode_free(left);
743                                 goto nomem;
744                         }
745 
746                         put_child(tn, 2*i, (struct rt_trie_node *) left);
747                         put_child(tn, 2*i+1, (struct rt_trie_node *) right);
748                 }
749         }
750 
751         for (i = 0; i < olen; i++) {
752                 struct tnode *inode;
753                 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
754                 struct tnode *left, *right;
755                 int size, j;
756 
757                 /* An empty child */
758                 if (node == NULL)
759                         continue;
760 
761                 /* A leaf or an internal node with skipped bits */
762 
763                 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
764                    tn->pos + tn->bits - 1) {
765                         put_child(tn,
766                                 tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
767                                 node);
768                         continue;
769                 }
770 
771                 /* An internal node with two children */
772                 inode = (struct tnode *) node;
773 
774                 if (inode->bits == 1) {
775                         put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
776                         put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
777 
778                         tnode_free_safe(inode);
779                         continue;
780                 }
781 
782                 /* An internal node with more than two children */
783 
784                 /* We will replace this node 'inode' with two new
785                  * ones, 'left' and 'right', each with half of the
786                  * original children. The two new nodes will have
787                  * a position one bit further down the key and this
788                  * means that the "significant" part of their keys
789                  * (see the discussion near the top of this file)
790                  * will differ by one bit, which will be "" in
791                  * left's key and "1" in right's key. Since we are
792                  * moving the key position by one step, the bit that
793                  * we are moving away from - the bit at position
794                  * (inode->pos) - is the one that will differ between
795                  * left and right. So... we synthesize that bit in the
796                  * two  new keys.
797                  * The mask 'm' below will be a single "one" bit at
798                  * the position (inode->pos)
799                  */
800 
801                 /* Use the old key, but set the new significant
802                  *   bit to zero.
803                  */
804 
805                 left = (struct tnode *) tnode_get_child(tn, 2*i);
806                 put_child(tn, 2*i, NULL);
807 
808                 BUG_ON(!left);
809 
810                 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
811                 put_child(tn, 2*i+1, NULL);
812 
813                 BUG_ON(!right);
814 
815                 size = tnode_child_length(left);
816                 for (j = 0; j < size; j++) {
817                         put_child(left, j, rtnl_dereference(inode->child[j]));
818                         put_child(right, j, rtnl_dereference(inode->child[j + size]));
819                 }
820                 put_child(tn, 2*i, resize(t, left));
821                 put_child(tn, 2*i+1, resize(t, right));
822 
823                 tnode_free_safe(inode);
824         }
825         tnode_free_safe(oldtnode);
826         return tn;
827 nomem:
828         tnode_clean_free(tn);
829         return ERR_PTR(-ENOMEM);
830 }
831 
832 static struct tnode *halve(struct trie *t, struct tnode *tn)
833 {
834         struct tnode *oldtnode = tn;
835         struct rt_trie_node *left, *right;
836         int i;
837         int olen = tnode_child_length(tn);
838 
839         pr_debug("In halve\n");
840 
841         tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
842 
843         if (!tn)
844                 return ERR_PTR(-ENOMEM);
845 
846         /*
847          * Preallocate and store tnodes before the actual work so we
848          * don't get into an inconsistent state if memory allocation
849          * fails. In case of failure we return the oldnode and halve
850          * of tnode is ignored.
851          */
852 
853         for (i = 0; i < olen; i += 2) {
854                 left = tnode_get_child(oldtnode, i);
855                 right = tnode_get_child(oldtnode, i+1);
856 
857                 /* Two nonempty children */
858                 if (left && right) {
859                         struct tnode *newn;
860 
861                         newn = tnode_new(left->key, tn->pos + tn->bits, 1);
862 
863                         if (!newn)
864                                 goto nomem;
865 
866                         put_child(tn, i/2, (struct rt_trie_node *)newn);
867                 }
868 
869         }
870 
871         for (i = 0; i < olen; i += 2) {
872                 struct tnode *newBinNode;
873 
874                 left = tnode_get_child(oldtnode, i);
875                 right = tnode_get_child(oldtnode, i+1);
876 
877                 /* At least one of the children is empty */
878                 if (left == NULL) {
879                         if (right == NULL)    /* Both are empty */
880                                 continue;
881                         put_child(tn, i/2, right);
882                         continue;
883                 }
884 
885                 if (right == NULL) {
886                         put_child(tn, i/2, left);
887                         continue;
888                 }
889 
890                 /* Two nonempty children */
891                 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
892                 put_child(tn, i/2, NULL);
893                 put_child(newBinNode, 0, left);
894                 put_child(newBinNode, 1, right);
895                 put_child(tn, i/2, resize(t, newBinNode));
896         }
897         tnode_free_safe(oldtnode);
898         return tn;
899 nomem:
900         tnode_clean_free(tn);
901         return ERR_PTR(-ENOMEM);
902 }
903 
904 /* readside must use rcu_read_lock currently dump routines
905  via get_fa_head and dump */
906 
907 static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
908 {
909         struct hlist_head *head = &l->list;
910         struct leaf_info *li;
911 
912         hlist_for_each_entry_rcu(li, head, hlist)
913                 if (li->plen == plen)
914                         return li;
915 
916         return NULL;
917 }
918 
919 static inline struct list_head *get_fa_head(struct leaf *l, int plen)
920 {
921         struct leaf_info *li = find_leaf_info(l, plen);
922 
923         if (!li)
924                 return NULL;
925 
926         return &li->falh;
927 }
928 
929 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
930 {
931         struct leaf_info *li = NULL, *last = NULL;
932 
933         if (hlist_empty(head)) {
934                 hlist_add_head_rcu(&new->hlist, head);
935         } else {
936                 hlist_for_each_entry(li, head, hlist) {
937                         if (new->plen > li->plen)
938                                 break;
939 
940                         last = li;
941                 }
942                 if (last)
943                         hlist_add_behind_rcu(&new->hlist, &last->hlist);
944                 else
945                         hlist_add_before_rcu(&new->hlist, &li->hlist);
946         }
947 }
948 
949 /* rcu_read_lock needs to be hold by caller from readside */
950 
951 static struct leaf *
952 fib_find_node(struct trie *t, u32 key)
953 {
954         int pos;
955         struct tnode *tn;
956         struct rt_trie_node *n;
957 
958         pos = 0;
959         n = rcu_dereference_rtnl(t->trie);
960 
961         while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
962                 tn = (struct tnode *) n;
963 
964                 check_tnode(tn);
965 
966                 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
967                         pos = tn->pos + tn->bits;
968                         n = tnode_get_child_rcu(tn,
969                                                 tkey_extract_bits(key,
970                                                                   tn->pos,
971                                                                   tn->bits));
972                 } else
973                         break;
974         }
975         /* Case we have found a leaf. Compare prefixes */
976 
977         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
978                 return (struct leaf *)n;
979 
980         return NULL;
981 }
982 
983 static void trie_rebalance(struct trie *t, struct tnode *tn)
984 {
985         int wasfull;
986         t_key cindex, key;
987         struct tnode *tp;
988 
989         key = tn->key;
990 
991         while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
992                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
993                 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
994                 tn = (struct tnode *)resize(t, tn);
995 
996                 tnode_put_child_reorg(tp, cindex,
997                                       (struct rt_trie_node *)tn, wasfull);
998 
999                 tp = node_parent((struct rt_trie_node *) tn);
1000                 if (!tp)
1001                         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1002 
1003                 tnode_free_flush();
1004                 if (!tp)
1005                         break;
1006                 tn = tp;
1007         }
1008 
1009         /* Handle last (top) tnode */
1010         if (IS_TNODE(tn))
1011                 tn = (struct tnode *)resize(t, tn);
1012 
1013         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1014         tnode_free_flush();
1015 }
1016 
1017 /* only used from updater-side */
1018 
1019 static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1020 {
1021         int pos, newpos;
1022         struct tnode *tp = NULL, *tn = NULL;
1023         struct rt_trie_node *n;
1024         struct leaf *l;
1025         int missbit;
1026         struct list_head *fa_head = NULL;
1027         struct leaf_info *li;
1028         t_key cindex;
1029 
1030         pos = 0;
1031         n = rtnl_dereference(t->trie);
1032 
1033         /* If we point to NULL, stop. Either the tree is empty and we should
1034          * just put a new leaf in if, or we have reached an empty child slot,
1035          * and we should just put our new leaf in that.
1036          * If we point to a T_TNODE, check if it matches our key. Note that
1037          * a T_TNODE might be skipping any number of bits - its 'pos' need
1038          * not be the parent's 'pos'+'bits'!
1039          *
1040          * If it does match the current key, get pos/bits from it, extract
1041          * the index from our key, push the T_TNODE and walk the tree.
1042          *
1043          * If it doesn't, we have to replace it with a new T_TNODE.
1044          *
1045          * If we point to a T_LEAF, it might or might not have the same key
1046          * as we do. If it does, just change the value, update the T_LEAF's
1047          * value, and return it.
1048          * If it doesn't, we need to replace it with a T_TNODE.
1049          */
1050 
1051         while (n != NULL &&  NODE_TYPE(n) == T_TNODE) {
1052                 tn = (struct tnode *) n;
1053 
1054                 check_tnode(tn);
1055 
1056                 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1057                         tp = tn;
1058                         pos = tn->pos + tn->bits;
1059                         n = tnode_get_child(tn,
1060                                             tkey_extract_bits(key,
1061                                                               tn->pos,
1062                                                               tn->bits));
1063 
1064                         BUG_ON(n && node_parent(n) != tn);
1065                 } else
1066                         break;
1067         }
1068 
1069         /*
1070          * n  ----> NULL, LEAF or TNODE
1071          *
1072          * tp is n's (parent) ----> NULL or TNODE
1073          */
1074 
1075         BUG_ON(tp && IS_LEAF(tp));
1076 
1077         /* Case 1: n is a leaf. Compare prefixes */
1078 
1079         if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1080                 l = (struct leaf *) n;
1081                 li = leaf_info_new(plen);
1082 
1083                 if (!li)
1084                         return NULL;
1085 
1086                 fa_head = &li->falh;
1087                 insert_leaf_info(&l->list, li);
1088                 goto done;
1089         }
1090         l = leaf_new();
1091 
1092         if (!l)
1093                 return NULL;
1094 
1095         l->key = key;
1096         li = leaf_info_new(plen);
1097 
1098         if (!li) {
1099                 free_leaf(l);
1100                 return NULL;
1101         }
1102 
1103         fa_head = &li->falh;
1104         insert_leaf_info(&l->list, li);
1105 
1106         if (t->trie && n == NULL) {
1107                 /* Case 2: n is NULL, and will just insert a new leaf */
1108 
1109                 node_set_parent((struct rt_trie_node *)l, tp);
1110 
1111                 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1112                 put_child(tp, cindex, (struct rt_trie_node *)l);
1113         } else {
1114                 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1115                 /*
1116                  *  Add a new tnode here
1117                  *  first tnode need some special handling
1118                  */
1119 
1120                 if (n) {
1121                         pos = tp ? tp->pos+tp->bits : 0;
1122                         newpos = tkey_mismatch(key, pos, n->key);
1123                         tn = tnode_new(n->key, newpos, 1);
1124                 } else {
1125                         newpos = 0;
1126                         tn = tnode_new(key, newpos, 1); /* First tnode */
1127                 }
1128 
1129                 if (!tn) {
1130                         free_leaf_info(li);
1131                         free_leaf(l);
1132                         return NULL;
1133                 }
1134 
1135                 node_set_parent((struct rt_trie_node *)tn, tp);
1136 
1137                 missbit = tkey_extract_bits(key, newpos, 1);
1138                 put_child(tn, missbit, (struct rt_trie_node *)l);
1139                 put_child(tn, 1-missbit, n);
1140 
1141                 if (tp) {
1142                         cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1143                         put_child(tp, cindex, (struct rt_trie_node *)tn);
1144                 } else {
1145                         rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
1146                 }
1147 
1148                 tp = tn;
1149         }
1150 
1151         if (tp && tp->pos + tp->bits > 32)
1152                 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1153                         tp, tp->pos, tp->bits, key, plen);
1154 
1155         /* Rebalance the trie */
1156 
1157         trie_rebalance(t, tp);
1158 done:
1159         return fa_head;
1160 }
1161 
1162 /*
1163  * Caller must hold RTNL.
1164  */
1165 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1166 {
1167         struct trie *t = (struct trie *) tb->tb_data;
1168         struct fib_alias *fa, *new_fa;
1169         struct list_head *fa_head = NULL;
1170         struct fib_info *fi;
1171         int plen = cfg->fc_dst_len;
1172         u8 tos = cfg->fc_tos;
1173         u32 key, mask;
1174         int err;
1175         struct leaf *l;
1176 
1177         if (plen > 32)
1178                 return -EINVAL;
1179 
1180         key = ntohl(cfg->fc_dst);
1181 
1182         pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1183 
1184         mask = ntohl(inet_make_mask(plen));
1185 
1186         if (key & ~mask)
1187                 return -EINVAL;
1188 
1189         key = key & mask;
1190 
1191         fi = fib_create_info(cfg);
1192         if (IS_ERR(fi)) {
1193                 err = PTR_ERR(fi);
1194                 goto err;
1195         }
1196 
1197         l = fib_find_node(t, key);
1198         fa = NULL;
1199 
1200         if (l) {
1201                 fa_head = get_fa_head(l, plen);
1202                 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1203         }
1204 
1205         /* Now fa, if non-NULL, points to the first fib alias
1206          * with the same keys [prefix,tos,priority], if such key already
1207          * exists or to the node before which we will insert new one.
1208          *
1209          * If fa is NULL, we will need to allocate a new one and
1210          * insert to the head of f.
1211          *
1212          * If f is NULL, no fib node matched the destination key
1213          * and we need to allocate a new one of those as well.
1214          */
1215 
1216         if (fa && fa->fa_tos == tos &&
1217             fa->fa_info->fib_priority == fi->fib_priority) {
1218                 struct fib_alias *fa_first, *fa_match;
1219 
1220                 err = -EEXIST;
1221                 if (cfg->fc_nlflags & NLM_F_EXCL)
1222                         goto out;
1223 
1224                 /* We have 2 goals:
1225                  * 1. Find exact match for type, scope, fib_info to avoid
1226                  * duplicate routes
1227                  * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1228                  */
1229                 fa_match = NULL;
1230                 fa_first = fa;
1231                 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1232                 list_for_each_entry_continue(fa, fa_head, fa_list) {
1233                         if (fa->fa_tos != tos)
1234                                 break;
1235                         if (fa->fa_info->fib_priority != fi->fib_priority)
1236                                 break;
1237                         if (fa->fa_type == cfg->fc_type &&
1238                             fa->fa_info == fi) {
1239                                 fa_match = fa;
1240                                 break;
1241                         }
1242                 }
1243 
1244                 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1245                         struct fib_info *fi_drop;
1246                         u8 state;
1247 
1248                         fa = fa_first;
1249                         if (fa_match) {
1250                                 if (fa == fa_match)
1251                                         err = 0;
1252                                 goto out;
1253                         }
1254                         err = -ENOBUFS;
1255                         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1256                         if (new_fa == NULL)
1257                                 goto out;
1258 
1259                         fi_drop = fa->fa_info;
1260                         new_fa->fa_tos = fa->fa_tos;
1261                         new_fa->fa_info = fi;
1262                         new_fa->fa_type = cfg->fc_type;
1263                         state = fa->fa_state;
1264                         new_fa->fa_state = state & ~FA_S_ACCESSED;
1265 
1266                         list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1267                         alias_free_mem_rcu(fa);
1268 
1269                         fib_release_info(fi_drop);
1270                         if (state & FA_S_ACCESSED)
1271                                 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1272                         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1273                                 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1274 
1275                         goto succeeded;
1276                 }
1277                 /* Error if we find a perfect match which
1278                  * uses the same scope, type, and nexthop
1279                  * information.
1280                  */
1281                 if (fa_match)
1282                         goto out;
1283 
1284                 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1285                         fa = fa_first;
1286         }
1287         err = -ENOENT;
1288         if (!(cfg->fc_nlflags & NLM_F_CREATE))
1289                 goto out;
1290 
1291         err = -ENOBUFS;
1292         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1293         if (new_fa == NULL)
1294                 goto out;
1295 
1296         new_fa->fa_info = fi;
1297         new_fa->fa_tos = tos;
1298         new_fa->fa_type = cfg->fc_type;
1299         new_fa->fa_state = 0;
1300         /*
1301          * Insert new entry to the list.
1302          */
1303 
1304         if (!fa_head) {
1305                 fa_head = fib_insert_node(t, key, plen);
1306                 if (unlikely(!fa_head)) {
1307                         err = -ENOMEM;
1308                         goto out_free_new_fa;
1309                 }
1310         }
1311 
1312         if (!plen)
1313                 tb->tb_num_default++;
1314 
1315         list_add_tail_rcu(&new_fa->fa_list,
1316                           (fa ? &fa->fa_list : fa_head));
1317 
1318         rt_cache_flush(cfg->fc_nlinfo.nl_net);
1319         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1320                   &cfg->fc_nlinfo, 0);
1321 succeeded:
1322         return 0;
1323 
1324 out_free_new_fa:
1325         kmem_cache_free(fn_alias_kmem, new_fa);
1326 out:
1327         fib_release_info(fi);
1328 err:
1329         return err;
1330 }
1331 
1332 /* should be called with rcu_read_lock */
1333 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1334                       t_key key,  const struct flowi4 *flp,
1335                       struct fib_result *res, int fib_flags)
1336 {
1337         struct leaf_info *li;
1338         struct hlist_head *hhead = &l->list;
1339 
1340         hlist_for_each_entry_rcu(li, hhead, hlist) {
1341                 struct fib_alias *fa;
1342 
1343                 if (l->key != (key & li->mask_plen))
1344                         continue;
1345 
1346                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1347                         struct fib_info *fi = fa->fa_info;
1348                         int nhsel, err;
1349 
1350                         if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1351                                 continue;
1352                         if (fi->fib_dead)
1353                                 continue;
1354                         if (fa->fa_info->fib_scope < flp->flowi4_scope)
1355                                 continue;
1356                         fib_alias_accessed(fa);
1357                         err = fib_props[fa->fa_type].error;
1358                         if (err) {
1359 #ifdef CONFIG_IP_FIB_TRIE_STATS
1360                                 t->stats.semantic_match_passed++;
1361 #endif
1362                                 return err;
1363                         }
1364                         if (fi->fib_flags & RTNH_F_DEAD)
1365                                 continue;
1366                         for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1367                                 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1368 
1369                                 if (nh->nh_flags & RTNH_F_DEAD)
1370                                         continue;
1371                                 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1372                                         continue;
1373 
1374 #ifdef CONFIG_IP_FIB_TRIE_STATS
1375                                 t->stats.semantic_match_passed++;
1376 #endif
1377                                 res->prefixlen = li->plen;
1378                                 res->nh_sel = nhsel;
1379                                 res->type = fa->fa_type;
1380                                 res->scope = fa->fa_info->fib_scope;
1381                                 res->fi = fi;
1382                                 res->table = tb;
1383                                 res->fa_head = &li->falh;
1384                                 if (!(fib_flags & FIB_LOOKUP_NOREF))
1385                                         atomic_inc(&fi->fib_clntref);
1386                                 return 0;
1387                         }
1388                 }
1389 
1390 #ifdef CONFIG_IP_FIB_TRIE_STATS
1391                 t->stats.semantic_match_miss++;
1392 #endif
1393         }
1394 
1395         return 1;
1396 }
1397 
1398 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1399                      struct fib_result *res, int fib_flags)
1400 {
1401         struct trie *t = (struct trie *) tb->tb_data;
1402         int ret;
1403         struct rt_trie_node *n;
1404         struct tnode *pn;
1405         unsigned int pos, bits;
1406         t_key key = ntohl(flp->daddr);
1407         unsigned int chopped_off;
1408         t_key cindex = 0;
1409         unsigned int current_prefix_length = KEYLENGTH;
1410         struct tnode *cn;
1411         t_key pref_mismatch;
1412 
1413         rcu_read_lock();
1414 
1415         n = rcu_dereference(t->trie);
1416         if (!n)
1417                 goto failed;
1418 
1419 #ifdef CONFIG_IP_FIB_TRIE_STATS
1420         t->stats.gets++;
1421 #endif
1422 
1423         /* Just a leaf? */
1424         if (IS_LEAF(n)) {
1425                 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1426                 goto found;
1427         }
1428 
1429         pn = (struct tnode *) n;
1430         chopped_off = 0;
1431 
1432         while (pn) {
1433                 pos = pn->pos;
1434                 bits = pn->bits;
1435 
1436                 if (!chopped_off)
1437                         cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1438                                                    pos, bits);
1439 
1440                 n = tnode_get_child_rcu(pn, cindex);
1441 
1442                 if (n == NULL) {
1443 #ifdef CONFIG_IP_FIB_TRIE_STATS
1444                         t->stats.null_node_hit++;
1445 #endif
1446                         goto backtrace;
1447                 }
1448 
1449                 if (IS_LEAF(n)) {
1450                         ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1451                         if (ret > 0)
1452                                 goto backtrace;
1453                         goto found;
1454                 }
1455 
1456                 cn = (struct tnode *)n;
1457 
1458                 /*
1459                  * It's a tnode, and we can do some extra checks here if we
1460                  * like, to avoid descending into a dead-end branch.
1461                  * This tnode is in the parent's child array at index
1462                  * key[p_pos..p_pos+p_bits] but potentially with some bits
1463                  * chopped off, so in reality the index may be just a
1464                  * subprefix, padded with zero at the end.
1465                  * We can also take a look at any skipped bits in this
1466                  * tnode - everything up to p_pos is supposed to be ok,
1467                  * and the non-chopped bits of the index (se previous
1468                  * paragraph) are also guaranteed ok, but the rest is
1469                  * considered unknown.
1470                  *
1471                  * The skipped bits are key[pos+bits..cn->pos].
1472                  */
1473 
1474                 /* If current_prefix_length < pos+bits, we are already doing
1475                  * actual prefix  matching, which means everything from
1476                  * pos+(bits-chopped_off) onward must be zero along some
1477                  * branch of this subtree - otherwise there is *no* valid
1478                  * prefix present. Here we can only check the skipped
1479                  * bits. Remember, since we have already indexed into the
1480                  * parent's child array, we know that the bits we chopped of
1481                  * *are* zero.
1482                  */
1483 
1484                 /* NOTA BENE: Checking only skipped bits
1485                    for the new node here */
1486 
1487                 if (current_prefix_length < pos+bits) {
1488                         if (tkey_extract_bits(cn->key, current_prefix_length,
1489                                                 cn->pos - current_prefix_length)
1490                             || !(cn->child[0]))
1491                                 goto backtrace;
1492                 }
1493 
1494                 /*
1495                  * If chopped_off=0, the index is fully validated and we
1496                  * only need to look at the skipped bits for this, the new,
1497                  * tnode. What we actually want to do is to find out if
1498                  * these skipped bits match our key perfectly, or if we will
1499                  * have to count on finding a matching prefix further down,
1500                  * because if we do, we would like to have some way of
1501                  * verifying the existence of such a prefix at this point.
1502                  */
1503 
1504                 /* The only thing we can do at this point is to verify that
1505                  * any such matching prefix can indeed be a prefix to our
1506                  * key, and if the bits in the node we are inspecting that
1507                  * do not match our key are not ZERO, this cannot be true.
1508                  * Thus, find out where there is a mismatch (before cn->pos)
1509                  * and verify that all the mismatching bits are zero in the
1510                  * new tnode's key.
1511                  */
1512 
1513                 /*
1514                  * Note: We aren't very concerned about the piece of
1515                  * the key that precede pn->pos+pn->bits, since these
1516                  * have already been checked. The bits after cn->pos
1517                  * aren't checked since these are by definition
1518                  * "unknown" at this point. Thus, what we want to see
1519                  * is if we are about to enter the "prefix matching"
1520                  * state, and in that case verify that the skipped
1521                  * bits that will prevail throughout this subtree are
1522                  * zero, as they have to be if we are to find a
1523                  * matching prefix.
1524                  */
1525 
1526                 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1527 
1528                 /*
1529                  * In short: If skipped bits in this node do not match
1530                  * the search key, enter the "prefix matching"
1531                  * state.directly.
1532                  */
1533                 if (pref_mismatch) {
1534                         /* fls(x) = __fls(x) + 1 */
1535                         int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
1536 
1537                         if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1538                                 goto backtrace;
1539 
1540                         if (current_prefix_length >= cn->pos)
1541                                 current_prefix_length = mp;
1542                 }
1543 
1544                 pn = (struct tnode *)n; /* Descend */
1545                 chopped_off = 0;
1546                 continue;
1547 
1548 backtrace:
1549                 chopped_off++;
1550 
1551                 /* As zero don't change the child key (cindex) */
1552                 while ((chopped_off <= pn->bits)
1553                        && !(cindex & (1<<(chopped_off-1))))
1554                         chopped_off++;
1555 
1556                 /* Decrease current_... with bits chopped off */
1557                 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1558                         current_prefix_length = pn->pos + pn->bits
1559                                 - chopped_off;
1560 
1561                 /*
1562                  * Either we do the actual chop off according or if we have
1563                  * chopped off all bits in this tnode walk up to our parent.
1564                  */
1565 
1566                 if (chopped_off <= pn->bits) {
1567                         cindex &= ~(1 << (chopped_off-1));
1568                 } else {
1569                         struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1570                         if (!parent)
1571                                 goto failed;
1572 
1573                         /* Get Child's index */
1574                         cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1575                         pn = parent;
1576                         chopped_off = 0;
1577 
1578 #ifdef CONFIG_IP_FIB_TRIE_STATS
1579                         t->stats.backtrack++;
1580 #endif
1581                         goto backtrace;
1582                 }
1583         }
1584 failed:
1585         ret = 1;
1586 found:
1587         rcu_read_unlock();
1588         return ret;
1589 }
1590 EXPORT_SYMBOL_GPL(fib_table_lookup);
1591 
1592 /*
1593  * Remove the leaf and return parent.
1594  */
1595 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1596 {
1597         struct tnode *tp = node_parent((struct rt_trie_node *) l);
1598 
1599         pr_debug("entering trie_leaf_remove(%p)\n", l);
1600 
1601         if (tp) {
1602                 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1603                 put_child(tp, cindex, NULL);
1604                 trie_rebalance(t, tp);
1605         } else
1606                 RCU_INIT_POINTER(t->trie, NULL);
1607 
1608         free_leaf(l);
1609 }
1610 
1611 /*
1612  * Caller must hold RTNL.
1613  */
1614 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1615 {
1616         struct trie *t = (struct trie *) tb->tb_data;
1617         u32 key, mask;
1618         int plen = cfg->fc_dst_len;
1619         u8 tos = cfg->fc_tos;
1620         struct fib_alias *fa, *fa_to_delete;
1621         struct list_head *fa_head;
1622         struct leaf *l;
1623         struct leaf_info *li;
1624 
1625         if (plen > 32)
1626                 return -EINVAL;
1627 
1628         key = ntohl(cfg->fc_dst);
1629         mask = ntohl(inet_make_mask(plen));
1630 
1631         if (key & ~mask)
1632                 return -EINVAL;
1633 
1634         key = key & mask;
1635         l = fib_find_node(t, key);
1636 
1637         if (!l)
1638                 return -ESRCH;
1639 
1640         li = find_leaf_info(l, plen);
1641 
1642         if (!li)
1643                 return -ESRCH;
1644 
1645         fa_head = &li->falh;
1646         fa = fib_find_alias(fa_head, tos, 0);
1647 
1648         if (!fa)
1649                 return -ESRCH;
1650 
1651         pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1652 
1653         fa_to_delete = NULL;
1654         fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1655         list_for_each_entry_continue(fa, fa_head, fa_list) {
1656                 struct fib_info *fi = fa->fa_info;
1657 
1658                 if (fa->fa_tos != tos)
1659                         break;
1660 
1661                 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1662                     (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1663                      fa->fa_info->fib_scope == cfg->fc_scope) &&
1664                     (!cfg->fc_prefsrc ||
1665                      fi->fib_prefsrc == cfg->fc_prefsrc) &&
1666                     (!cfg->fc_protocol ||
1667                      fi->fib_protocol == cfg->fc_protocol) &&
1668                     fib_nh_match(cfg, fi) == 0) {
1669                         fa_to_delete = fa;
1670                         break;
1671                 }
1672         }
1673 
1674         if (!fa_to_delete)
1675                 return -ESRCH;
1676 
1677         fa = fa_to_delete;
1678         rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1679                   &cfg->fc_nlinfo, 0);
1680 
1681         list_del_rcu(&fa->fa_list);
1682 
1683         if (!plen)
1684                 tb->tb_num_default--;
1685 
1686         if (list_empty(fa_head)) {
1687                 hlist_del_rcu(&li->hlist);
1688                 free_leaf_info(li);
1689         }
1690 
1691         if (hlist_empty(&l->list))
1692                 trie_leaf_remove(t, l);
1693 
1694         if (fa->fa_state & FA_S_ACCESSED)
1695                 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1696 
1697         fib_release_info(fa->fa_info);
1698         alias_free_mem_rcu(fa);
1699         return 0;
1700 }
1701 
1702 static int trie_flush_list(struct list_head *head)
1703 {
1704         struct fib_alias *fa, *fa_node;
1705         int found = 0;
1706 
1707         list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1708                 struct fib_info *fi = fa->fa_info;
1709 
1710                 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1711                         list_del_rcu(&fa->fa_list);
1712                         fib_release_info(fa->fa_info);
1713                         alias_free_mem_rcu(fa);
1714                         found++;
1715                 }
1716         }
1717         return found;
1718 }
1719 
1720 static int trie_flush_leaf(struct leaf *l)
1721 {
1722         int found = 0;
1723         struct hlist_head *lih = &l->list;
1724         struct hlist_node *tmp;
1725         struct leaf_info *li = NULL;
1726 
1727         hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1728                 found += trie_flush_list(&li->falh);
1729 
1730                 if (list_empty(&li->falh)) {
1731                         hlist_del_rcu(&li->hlist);
1732                         free_leaf_info(li);
1733                 }
1734         }
1735         return found;
1736 }
1737 
1738 /*
1739  * Scan for the next right leaf starting at node p->child[idx]
1740  * Since we have back pointer, no recursion necessary.
1741  */
1742 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1743 {
1744         do {
1745                 t_key idx;
1746 
1747                 if (c)
1748                         idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1749                 else
1750                         idx = 0;
1751 
1752                 while (idx < 1u << p->bits) {
1753                         c = tnode_get_child_rcu(p, idx++);
1754                         if (!c)
1755                                 continue;
1756 
1757                         if (IS_LEAF(c))
1758                                 return (struct leaf *) c;
1759 
1760                         /* Rescan start scanning in new node */
1761                         p = (struct tnode *) c;
1762                         idx = 0;
1763                 }
1764 
1765                 /* Node empty, walk back up to parent */
1766                 c = (struct rt_trie_node *) p;
1767         } while ((p = node_parent_rcu(c)) != NULL);
1768 
1769         return NULL; /* Root of trie */
1770 }
1771 
1772 static struct leaf *trie_firstleaf(struct trie *t)
1773 {
1774         struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1775 
1776         if (!n)
1777                 return NULL;
1778 
1779         if (IS_LEAF(n))          /* trie is just a leaf */
1780                 return (struct leaf *) n;
1781 
1782         return leaf_walk_rcu(n, NULL);
1783 }
1784 
1785 static struct leaf *trie_nextleaf(struct leaf *l)
1786 {
1787         struct rt_trie_node *c = (struct rt_trie_node *) l;
1788         struct tnode *p = node_parent_rcu(c);
1789 
1790         if (!p)
1791                 return NULL;    /* trie with just one leaf */
1792 
1793         return leaf_walk_rcu(p, c);
1794 }
1795 
1796 static struct leaf *trie_leafindex(struct trie *t, int index)
1797 {
1798         struct leaf *l = trie_firstleaf(t);
1799 
1800         while (l && index-- > 0)
1801                 l = trie_nextleaf(l);
1802 
1803         return l;
1804 }
1805 
1806 
1807 /*
1808  * Caller must hold RTNL.
1809  */
1810 int fib_table_flush(struct fib_table *tb)
1811 {
1812         struct trie *t = (struct trie *) tb->tb_data;
1813         struct leaf *l, *ll = NULL;
1814         int found = 0;
1815 
1816         for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1817                 found += trie_flush_leaf(l);
1818 
1819                 if (ll && hlist_empty(&ll->list))
1820                         trie_leaf_remove(t, ll);
1821                 ll = l;
1822         }
1823 
1824         if (ll && hlist_empty(&ll->list))
1825                 trie_leaf_remove(t, ll);
1826 
1827         pr_debug("trie_flush found=%d\n", found);
1828         return found;
1829 }
1830 
1831 void fib_free_table(struct fib_table *tb)
1832 {
1833         kfree(tb);
1834 }
1835 
1836 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1837                            struct fib_table *tb,
1838                            struct sk_buff *skb, struct netlink_callback *cb)
1839 {
1840         int i, s_i;
1841         struct fib_alias *fa;
1842         __be32 xkey = htonl(key);
1843 
1844         s_i = cb->args[5];
1845         i = 0;
1846 
1847         /* rcu_read_lock is hold by caller */
1848 
1849         list_for_each_entry_rcu(fa, fah, fa_list) {
1850                 if (i < s_i) {
1851                         i++;
1852                         continue;
1853                 }
1854 
1855                 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1856                                   cb->nlh->nlmsg_seq,
1857                                   RTM_NEWROUTE,
1858                                   tb->tb_id,
1859                                   fa->fa_type,
1860                                   xkey,
1861                                   plen,
1862                                   fa->fa_tos,
1863                                   fa->fa_info, NLM_F_MULTI) < 0) {
1864                         cb->args[5] = i;
1865                         return -1;
1866                 }
1867                 i++;
1868         }
1869         cb->args[5] = i;
1870         return skb->len;
1871 }
1872 
1873 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1874                         struct sk_buff *skb, struct netlink_callback *cb)
1875 {
1876         struct leaf_info *li;
1877         int i, s_i;
1878 
1879         s_i = cb->args[4];
1880         i = 0;
1881 
1882         /* rcu_read_lock is hold by caller */
1883         hlist_for_each_entry_rcu(li, &l->list, hlist) {
1884                 if (i < s_i) {
1885                         i++;
1886                         continue;
1887                 }
1888 
1889                 if (i > s_i)
1890                         cb->args[5] = 0;
1891 
1892                 if (list_empty(&li->falh))
1893                         continue;
1894 
1895                 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1896                         cb->args[4] = i;
1897                         return -1;
1898                 }
1899                 i++;
1900         }
1901 
1902         cb->args[4] = i;
1903         return skb->len;
1904 }
1905 
1906 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1907                    struct netlink_callback *cb)
1908 {
1909         struct leaf *l;
1910         struct trie *t = (struct trie *) tb->tb_data;
1911         t_key key = cb->args[2];
1912         int count = cb->args[3];
1913 
1914         rcu_read_lock();
1915         /* Dump starting at last key.
1916          * Note: 0.0.0.0/0 (ie default) is first key.
1917          */
1918         if (count == 0)
1919                 l = trie_firstleaf(t);
1920         else {
1921                 /* Normally, continue from last key, but if that is missing
1922                  * fallback to using slow rescan
1923                  */
1924                 l = fib_find_node(t, key);
1925                 if (!l)
1926                         l = trie_leafindex(t, count);
1927         }
1928 
1929         while (l) {
1930                 cb->args[2] = l->key;
1931                 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1932                         cb->args[3] = count;
1933                         rcu_read_unlock();
1934                         return -1;
1935                 }
1936 
1937                 ++count;
1938                 l = trie_nextleaf(l);
1939                 memset(&cb->args[4], 0,
1940                        sizeof(cb->args) - 4*sizeof(cb->args[0]));
1941         }
1942         cb->args[3] = count;
1943         rcu_read_unlock();
1944 
1945         return skb->len;
1946 }
1947 
1948 void __init fib_trie_init(void)
1949 {
1950         fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1951                                           sizeof(struct fib_alias),
1952                                           0, SLAB_PANIC, NULL);
1953 
1954         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1955                                            max(sizeof(struct leaf),
1956                                                sizeof(struct leaf_info)),
1957                                            0, SLAB_PANIC, NULL);
1958 }
1959 
1960 
1961 struct fib_table *fib_trie_table(u32 id)
1962 {
1963         struct fib_table *tb;
1964         struct trie *t;
1965 
1966         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1967                      GFP_KERNEL);
1968         if (tb == NULL)
1969                 return NULL;
1970 
1971         tb->tb_id = id;
1972         tb->tb_default = -1;
1973         tb->tb_num_default = 0;
1974 
1975         t = (struct trie *) tb->tb_data;
1976         memset(t, 0, sizeof(*t));
1977 
1978         return tb;
1979 }
1980 
1981 #ifdef CONFIG_PROC_FS
1982 /* Depth first Trie walk iterator */
1983 struct fib_trie_iter {
1984         struct seq_net_private p;
1985         struct fib_table *tb;
1986         struct tnode *tnode;
1987         unsigned int index;
1988         unsigned int depth;
1989 };
1990 
1991 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
1992 {
1993         struct tnode *tn = iter->tnode;
1994         unsigned int cindex = iter->index;
1995         struct tnode *p;
1996 
1997         /* A single entry routing table */
1998         if (!tn)
1999                 return NULL;
2000 
2001         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2002                  iter->tnode, iter->index, iter->depth);
2003 rescan:
2004         while (cindex < (1<<tn->bits)) {
2005                 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2006 
2007                 if (n) {
2008                         if (IS_LEAF(n)) {
2009                                 iter->tnode = tn;
2010                                 iter->index = cindex + 1;
2011                         } else {
2012                                 /* push down one level */
2013                                 iter->tnode = (struct tnode *) n;
2014                                 iter->index = 0;
2015                                 ++iter->depth;
2016                         }
2017                         return n;
2018                 }
2019 
2020                 ++cindex;
2021         }
2022 
2023         /* Current node exhausted, pop back up */
2024         p = node_parent_rcu((struct rt_trie_node *)tn);
2025         if (p) {
2026                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2027                 tn = p;
2028                 --iter->depth;
2029                 goto rescan;
2030         }
2031 
2032         /* got root? */
2033         return NULL;
2034 }
2035 
2036 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2037                                        struct trie *t)
2038 {
2039         struct rt_trie_node *n;
2040 
2041         if (!t)
2042                 return NULL;
2043 
2044         n = rcu_dereference(t->trie);
2045         if (!n)
2046                 return NULL;
2047 
2048         if (IS_TNODE(n)) {
2049                 iter->tnode = (struct tnode *) n;
2050                 iter->index = 0;
2051                 iter->depth = 1;
2052         } else {
2053                 iter->tnode = NULL;
2054                 iter->index = 0;
2055                 iter->depth = 0;
2056         }
2057 
2058         return n;
2059 }
2060 
2061 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2062 {
2063         struct rt_trie_node *n;
2064         struct fib_trie_iter iter;
2065 
2066         memset(s, 0, sizeof(*s));
2067 
2068         rcu_read_lock();
2069         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2070                 if (IS_LEAF(n)) {
2071                         struct leaf *l = (struct leaf *)n;
2072                         struct leaf_info *li;
2073 
2074                         s->leaves++;
2075                         s->totdepth += iter.depth;
2076                         if (iter.depth > s->maxdepth)
2077                                 s->maxdepth = iter.depth;
2078 
2079                         hlist_for_each_entry_rcu(li, &l->list, hlist)
2080                                 ++s->prefixes;
2081                 } else {
2082                         const struct tnode *tn = (const struct tnode *) n;
2083                         int i;
2084 
2085                         s->tnodes++;
2086                         if (tn->bits < MAX_STAT_DEPTH)
2087                                 s->nodesizes[tn->bits]++;
2088 
2089                         for (i = 0; i < (1<<tn->bits); i++)
2090                                 if (!tn->child[i])
2091                                         s->nullpointers++;
2092                 }
2093         }
2094         rcu_read_unlock();
2095 }
2096 
2097 /*
2098  *      This outputs /proc/net/fib_triestats
2099  */
2100 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2101 {
2102         unsigned int i, max, pointers, bytes, avdepth;
2103 
2104         if (stat->leaves)
2105                 avdepth = stat->totdepth*100 / stat->leaves;
2106         else
2107                 avdepth = 0;
2108 
2109         seq_printf(seq, "\tAver depth:     %u.%02d\n",
2110                    avdepth / 100, avdepth % 100);
2111         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2112 
2113         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2114         bytes = sizeof(struct leaf) * stat->leaves;
2115 
2116         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2117         bytes += sizeof(struct leaf_info) * stat->prefixes;
2118 
2119         seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2120         bytes += sizeof(struct tnode) * stat->tnodes;
2121 
2122         max = MAX_STAT_DEPTH;
2123         while (max > 0 && stat->nodesizes[max-1] == 0)
2124                 max--;
2125 
2126         pointers = 0;
2127         for (i = 1; i < max; i++)
2128                 if (stat->nodesizes[i] != 0) {
2129                         seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2130                         pointers += (1<<i) * stat->nodesizes[i];
2131                 }
2132         seq_putc(seq, '\n');
2133         seq_printf(seq, "\tPointers: %u\n", pointers);
2134 
2135         bytes += sizeof(struct rt_trie_node *) * pointers;
2136         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2137         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2138 }
2139 
2140 #ifdef CONFIG_IP_FIB_TRIE_STATS
2141 static void trie_show_usage(struct seq_file *seq,
2142                             const struct trie_use_stats *stats)
2143 {
2144         seq_printf(seq, "\nCounters:\n---------\n");
2145         seq_printf(seq, "gets = %u\n", stats->gets);
2146         seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2147         seq_printf(seq, "semantic match passed = %u\n",
2148                    stats->semantic_match_passed);
2149         seq_printf(seq, "semantic match miss = %u\n",
2150                    stats->semantic_match_miss);
2151         seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2152         seq_printf(seq, "skipped node resize = %u\n\n",
2153                    stats->resize_node_skipped);
2154 }
2155 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2156 
2157 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2158 {
2159         if (tb->tb_id == RT_TABLE_LOCAL)
2160                 seq_puts(seq, "Local:\n");
2161         else if (tb->tb_id == RT_TABLE_MAIN)
2162                 seq_puts(seq, "Main:\n");
2163         else
2164                 seq_printf(seq, "Id %d:\n", tb->tb_id);
2165 }
2166 
2167 
2168 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2169 {
2170         struct net *net = (struct net *)seq->private;
2171         unsigned int h;
2172 
2173         seq_printf(seq,
2174                    "Basic info: size of leaf:"
2175                    " %Zd bytes, size of tnode: %Zd bytes.\n",
2176                    sizeof(struct leaf), sizeof(struct tnode));
2177 
2178         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2179                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2180                 struct fib_table *tb;
2181 
2182                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2183                         struct trie *t = (struct trie *) tb->tb_data;
2184                         struct trie_stat stat;
2185 
2186                         if (!t)
2187                                 continue;
2188 
2189                         fib_table_print(seq, tb);
2190 
2191                         trie_collect_stats(t, &stat);
2192                         trie_show_stats(seq, &stat);
2193 #ifdef CONFIG_IP_FIB_TRIE_STATS
2194                         trie_show_usage(seq, &t->stats);
2195 #endif
2196                 }
2197         }
2198 
2199         return 0;
2200 }
2201 
2202 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2203 {
2204         return single_open_net(inode, file, fib_triestat_seq_show);
2205 }
2206 
2207 static const struct file_operations fib_triestat_fops = {
2208         .owner  = THIS_MODULE,
2209         .open   = fib_triestat_seq_open,
2210         .read   = seq_read,
2211         .llseek = seq_lseek,
2212         .release = single_release_net,
2213 };
2214 
2215 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2216 {
2217         struct fib_trie_iter *iter = seq->private;
2218         struct net *net = seq_file_net(seq);
2219         loff_t idx = 0;
2220         unsigned int h;
2221 
2222         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2223                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2224                 struct fib_table *tb;
2225 
2226                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2227                         struct rt_trie_node *n;
2228 
2229                         for (n = fib_trie_get_first(iter,
2230                                                     (struct trie *) tb->tb_data);
2231                              n; n = fib_trie_get_next(iter))
2232                                 if (pos == idx++) {
2233                                         iter->tb = tb;
2234                                         return n;
2235                                 }
2236                 }
2237         }
2238 
2239         return NULL;
2240 }
2241 
2242 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2243         __acquires(RCU)
2244 {
2245         rcu_read_lock();
2246         return fib_trie_get_idx(seq, *pos);
2247 }
2248 
2249 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2250 {
2251         struct fib_trie_iter *iter = seq->private;
2252         struct net *net = seq_file_net(seq);
2253         struct fib_table *tb = iter->tb;
2254         struct hlist_node *tb_node;
2255         unsigned int h;
2256         struct rt_trie_node *n;
2257 
2258         ++*pos;
2259         /* next node in same table */
2260         n = fib_trie_get_next(iter);
2261         if (n)
2262                 return n;
2263 
2264         /* walk rest of this hash chain */
2265         h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2266         while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2267                 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2268                 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2269                 if (n)
2270                         goto found;
2271         }
2272 
2273         /* new hash chain */
2274         while (++h < FIB_TABLE_HASHSZ) {
2275                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2276                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2277                         n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2278                         if (n)
2279                                 goto found;
2280                 }
2281         }
2282         return NULL;
2283 
2284 found:
2285         iter->tb = tb;
2286         return n;
2287 }
2288 
2289 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2290         __releases(RCU)
2291 {
2292         rcu_read_unlock();
2293 }
2294 
2295 static void seq_indent(struct seq_file *seq, int n)
2296 {
2297         while (n-- > 0)
2298                 seq_puts(seq, "   ");
2299 }
2300 
2301 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2302 {
2303         switch (s) {
2304         case RT_SCOPE_UNIVERSE: return "universe";
2305         case RT_SCOPE_SITE:     return "site";
2306         case RT_SCOPE_LINK:     return "link";
2307         case RT_SCOPE_HOST:     return "host";
2308         case RT_SCOPE_NOWHERE:  return "nowhere";
2309         default:
2310                 snprintf(buf, len, "scope=%d", s);
2311                 return buf;
2312         }
2313 }
2314 
2315 static const char *const rtn_type_names[__RTN_MAX] = {
2316         [RTN_UNSPEC] = "UNSPEC",
2317         [RTN_UNICAST] = "UNICAST",
2318         [RTN_LOCAL] = "LOCAL",
2319         [RTN_BROADCAST] = "BROADCAST",
2320         [RTN_ANYCAST] = "ANYCAST",
2321         [RTN_MULTICAST] = "MULTICAST",
2322         [RTN_BLACKHOLE] = "BLACKHOLE",
2323         [RTN_UNREACHABLE] = "UNREACHABLE",
2324         [RTN_PROHIBIT] = "PROHIBIT",
2325         [RTN_THROW] = "THROW",
2326         [RTN_NAT] = "NAT",
2327         [RTN_XRESOLVE] = "XRESOLVE",
2328 };
2329 
2330 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2331 {
2332         if (t < __RTN_MAX && rtn_type_names[t])
2333                 return rtn_type_names[t];
2334         snprintf(buf, len, "type %u", t);
2335         return buf;
2336 }
2337 
2338 /* Pretty print the trie */
2339 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2340 {
2341         const struct fib_trie_iter *iter = seq->private;
2342         struct rt_trie_node *n = v;
2343 
2344         if (!node_parent_rcu(n))
2345                 fib_table_print(seq, iter->tb);
2346 
2347         if (IS_TNODE(n)) {
2348                 struct tnode *tn = (struct tnode *) n;
2349                 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2350 
2351                 seq_indent(seq, iter->depth-1);
2352                 seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2353                            &prf, tn->pos, tn->bits, tn->full_children,
2354                            tn->empty_children);
2355 
2356         } else {
2357                 struct leaf *l = (struct leaf *) n;
2358                 struct leaf_info *li;
2359                 __be32 val = htonl(l->key);
2360 
2361                 seq_indent(seq, iter->depth);
2362                 seq_printf(seq, "  |-- %pI4\n", &val);
2363 
2364                 hlist_for_each_entry_rcu(li, &l->list, hlist) {
2365                         struct fib_alias *fa;
2366 
2367                         list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2368                                 char buf1[32], buf2[32];
2369 
2370                                 seq_indent(seq, iter->depth+1);
2371                                 seq_printf(seq, "  /%d %s %s", li->plen,
2372                                            rtn_scope(buf1, sizeof(buf1),
2373                                                      fa->fa_info->fib_scope),
2374                                            rtn_type(buf2, sizeof(buf2),
2375                                                     fa->fa_type));
2376                                 if (fa->fa_tos)
2377                                         seq_printf(seq, " tos=%d", fa->fa_tos);
2378                                 seq_putc(seq, '\n');
2379                         }
2380                 }
2381         }
2382 
2383         return 0;
2384 }
2385 
2386 static const struct seq_operations fib_trie_seq_ops = {
2387         .start  = fib_trie_seq_start,
2388         .next   = fib_trie_seq_next,
2389         .stop   = fib_trie_seq_stop,
2390         .show   = fib_trie_seq_show,
2391 };
2392 
2393 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2394 {
2395         return seq_open_net(inode, file, &fib_trie_seq_ops,
2396                             sizeof(struct fib_trie_iter));
2397 }
2398 
2399 static const struct file_operations fib_trie_fops = {
2400         .owner  = THIS_MODULE,
2401         .open   = fib_trie_seq_open,
2402         .read   = seq_read,
2403         .llseek = seq_lseek,
2404         .release = seq_release_net,
2405 };
2406 
2407 struct fib_route_iter {
2408         struct seq_net_private p;
2409         struct trie *main_trie;
2410         loff_t  pos;
2411         t_key   key;
2412 };
2413 
2414 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2415 {
2416         struct leaf *l = NULL;
2417         struct trie *t = iter->main_trie;
2418 
2419         /* use cache location of last found key */
2420         if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2421                 pos -= iter->pos;
2422         else {
2423                 iter->pos = 0;
2424                 l = trie_firstleaf(t);
2425         }
2426 
2427         while (l && pos-- > 0) {
2428                 iter->pos++;
2429                 l = trie_nextleaf(l);
2430         }
2431 
2432         if (l)
2433                 iter->key = pos;        /* remember it */
2434         else
2435                 iter->pos = 0;          /* forget it */
2436 
2437         return l;
2438 }
2439 
2440 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2441         __acquires(RCU)
2442 {
2443         struct fib_route_iter *iter = seq->private;
2444         struct fib_table *tb;
2445 
2446         rcu_read_lock();
2447         tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2448         if (!tb)
2449                 return NULL;
2450 
2451         iter->main_trie = (struct trie *) tb->tb_data;
2452         if (*pos == 0)
2453                 return SEQ_START_TOKEN;
2454         else
2455                 return fib_route_get_idx(iter, *pos - 1);
2456 }
2457 
2458 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2459 {
2460         struct fib_route_iter *iter = seq->private;
2461         struct leaf *l = v;
2462 
2463         ++*pos;
2464         if (v == SEQ_START_TOKEN) {
2465                 iter->pos = 0;
2466                 l = trie_firstleaf(iter->main_trie);
2467         } else {
2468                 iter->pos++;
2469                 l = trie_nextleaf(l);
2470         }
2471 
2472         if (l)
2473                 iter->key = l->key;
2474         else
2475                 iter->pos = 0;
2476         return l;
2477 }
2478 
2479 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2480         __releases(RCU)
2481 {
2482         rcu_read_unlock();
2483 }
2484 
2485 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2486 {
2487         unsigned int flags = 0;
2488 
2489         if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2490                 flags = RTF_REJECT;
2491         if (fi && fi->fib_nh->nh_gw)
2492                 flags |= RTF_GATEWAY;
2493         if (mask == htonl(0xFFFFFFFF))
2494                 flags |= RTF_HOST;
2495         flags |= RTF_UP;
2496         return flags;
2497 }
2498 
2499 /*
2500  *      This outputs /proc/net/route.
2501  *      The format of the file is not supposed to be changed
2502  *      and needs to be same as fib_hash output to avoid breaking
2503  *      legacy utilities
2504  */
2505 static int fib_route_seq_show(struct seq_file *seq, void *v)
2506 {
2507         struct leaf *l = v;
2508         struct leaf_info *li;
2509 
2510         if (v == SEQ_START_TOKEN) {
2511                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2512                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2513                            "\tWindow\tIRTT");
2514                 return 0;
2515         }
2516 
2517         hlist_for_each_entry_rcu(li, &l->list, hlist) {
2518                 struct fib_alias *fa;
2519                 __be32 mask, prefix;
2520 
2521                 mask = inet_make_mask(li->plen);
2522                 prefix = htonl(l->key);
2523 
2524                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2525                         const struct fib_info *fi = fa->fa_info;
2526                         unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2527 
2528                         if (fa->fa_type == RTN_BROADCAST
2529                             || fa->fa_type == RTN_MULTICAST)
2530                                 continue;
2531 
2532                         seq_setwidth(seq, 127);
2533 
2534                         if (fi)
2535                                 seq_printf(seq,
2536                                          "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2537                                          "%d\t%08X\t%d\t%u\t%u",
2538                                          fi->fib_dev ? fi->fib_dev->name : "*",
2539                                          prefix,
2540                                          fi->fib_nh->nh_gw, flags, 0, 0,
2541                                          fi->fib_priority,
2542                                          mask,
2543                                          (fi->fib_advmss ?
2544                                           fi->fib_advmss + 40 : 0),
2545                                          fi->fib_window,
2546                                          fi->fib_rtt >> 3);
2547                         else
2548                                 seq_printf(seq,
2549                                          "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2550                                          "%d\t%08X\t%d\t%u\t%u",
2551                                          prefix, 0, flags, 0, 0, 0,
2552                                          mask, 0, 0, 0);
2553 
2554                         seq_pad(seq, '\n');
2555                 }
2556         }
2557 
2558         return 0;
2559 }
2560 
2561 static const struct seq_operations fib_route_seq_ops = {
2562         .start  = fib_route_seq_start,
2563         .next   = fib_route_seq_next,
2564         .stop   = fib_route_seq_stop,
2565         .show   = fib_route_seq_show,
2566 };
2567 
2568 static int fib_route_seq_open(struct inode *inode, struct file *file)
2569 {
2570         return seq_open_net(inode, file, &fib_route_seq_ops,
2571                             sizeof(struct fib_route_iter));
2572 }
2573 
2574 static const struct file_operations fib_route_fops = {
2575         .owner  = THIS_MODULE,
2576         .open   = fib_route_seq_open,
2577         .read   = seq_read,
2578         .llseek = seq_lseek,
2579         .release = seq_release_net,
2580 };
2581 
2582 int __net_init fib_proc_init(struct net *net)
2583 {
2584         if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2585                 goto out1;
2586 
2587         if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2588                          &fib_triestat_fops))
2589                 goto out2;
2590 
2591         if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2592                 goto out3;
2593 
2594         return 0;
2595 
2596 out3:
2597         remove_proc_entry("fib_triestat", net->proc_net);
2598 out2:
2599         remove_proc_entry("fib_trie", net->proc_net);
2600 out1:
2601         return -ENOMEM;
2602 }
2603 
2604 void __net_exit fib_proc_exit(struct net *net)
2605 {
2606         remove_proc_entry("fib_trie", net->proc_net);
2607         remove_proc_entry("fib_triestat", net->proc_net);
2608         remove_proc_entry("route", net->proc_net);
2609 }
2610 
2611 #endif /* CONFIG_PROC_FS */
2612 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us