Version:  2.0.40 2.2.26 2.4.37 2.6.39 3.0 3.1 3.2 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

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_after_rcu(&last->hlist, &new->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                         tp = tn;
1147                 }
1148         }
1149 
1150         if (tp && tp->pos + tp->bits > 32)
1151                 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1152                         tp, tp->pos, tp->bits, key, plen);
1153 
1154         /* Rebalance the trie */
1155 
1156         trie_rebalance(t, tp);
1157 done:
1158         return fa_head;
1159 }
1160 
1161 /*
1162  * Caller must hold RTNL.
1163  */
1164 int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
1165 {
1166         struct trie *t = (struct trie *) tb->tb_data;
1167         struct fib_alias *fa, *new_fa;
1168         struct list_head *fa_head = NULL;
1169         struct fib_info *fi;
1170         int plen = cfg->fc_dst_len;
1171         u8 tos = cfg->fc_tos;
1172         u32 key, mask;
1173         int err;
1174         struct leaf *l;
1175 
1176         if (plen > 32)
1177                 return -EINVAL;
1178 
1179         key = ntohl(cfg->fc_dst);
1180 
1181         pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
1182 
1183         mask = ntohl(inet_make_mask(plen));
1184 
1185         if (key & ~mask)
1186                 return -EINVAL;
1187 
1188         key = key & mask;
1189 
1190         fi = fib_create_info(cfg);
1191         if (IS_ERR(fi)) {
1192                 err = PTR_ERR(fi);
1193                 goto err;
1194         }
1195 
1196         l = fib_find_node(t, key);
1197         fa = NULL;
1198 
1199         if (l) {
1200                 fa_head = get_fa_head(l, plen);
1201                 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1202         }
1203 
1204         /* Now fa, if non-NULL, points to the first fib alias
1205          * with the same keys [prefix,tos,priority], if such key already
1206          * exists or to the node before which we will insert new one.
1207          *
1208          * If fa is NULL, we will need to allocate a new one and
1209          * insert to the head of f.
1210          *
1211          * If f is NULL, no fib node matched the destination key
1212          * and we need to allocate a new one of those as well.
1213          */
1214 
1215         if (fa && fa->fa_tos == tos &&
1216             fa->fa_info->fib_priority == fi->fib_priority) {
1217                 struct fib_alias *fa_first, *fa_match;
1218 
1219                 err = -EEXIST;
1220                 if (cfg->fc_nlflags & NLM_F_EXCL)
1221                         goto out;
1222 
1223                 /* We have 2 goals:
1224                  * 1. Find exact match for type, scope, fib_info to avoid
1225                  * duplicate routes
1226                  * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1227                  */
1228                 fa_match = NULL;
1229                 fa_first = fa;
1230                 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1231                 list_for_each_entry_continue(fa, fa_head, fa_list) {
1232                         if (fa->fa_tos != tos)
1233                                 break;
1234                         if (fa->fa_info->fib_priority != fi->fib_priority)
1235                                 break;
1236                         if (fa->fa_type == cfg->fc_type &&
1237                             fa->fa_info == fi) {
1238                                 fa_match = fa;
1239                                 break;
1240                         }
1241                 }
1242 
1243                 if (cfg->fc_nlflags & NLM_F_REPLACE) {
1244                         struct fib_info *fi_drop;
1245                         u8 state;
1246 
1247                         fa = fa_first;
1248                         if (fa_match) {
1249                                 if (fa == fa_match)
1250                                         err = 0;
1251                                 goto out;
1252                         }
1253                         err = -ENOBUFS;
1254                         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1255                         if (new_fa == NULL)
1256                                 goto out;
1257 
1258                         fi_drop = fa->fa_info;
1259                         new_fa->fa_tos = fa->fa_tos;
1260                         new_fa->fa_info = fi;
1261                         new_fa->fa_type = cfg->fc_type;
1262                         state = fa->fa_state;
1263                         new_fa->fa_state = state & ~FA_S_ACCESSED;
1264 
1265                         list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1266                         alias_free_mem_rcu(fa);
1267 
1268                         fib_release_info(fi_drop);
1269                         if (state & FA_S_ACCESSED)
1270                                 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1271                         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1272                                 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
1273 
1274                         goto succeeded;
1275                 }
1276                 /* Error if we find a perfect match which
1277                  * uses the same scope, type, and nexthop
1278                  * information.
1279                  */
1280                 if (fa_match)
1281                         goto out;
1282 
1283                 if (!(cfg->fc_nlflags & NLM_F_APPEND))
1284                         fa = fa_first;
1285         }
1286         err = -ENOENT;
1287         if (!(cfg->fc_nlflags & NLM_F_CREATE))
1288                 goto out;
1289 
1290         err = -ENOBUFS;
1291         new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1292         if (new_fa == NULL)
1293                 goto out;
1294 
1295         new_fa->fa_info = fi;
1296         new_fa->fa_tos = tos;
1297         new_fa->fa_type = cfg->fc_type;
1298         new_fa->fa_state = 0;
1299         /*
1300          * Insert new entry to the list.
1301          */
1302 
1303         if (!fa_head) {
1304                 fa_head = fib_insert_node(t, key, plen);
1305                 if (unlikely(!fa_head)) {
1306                         err = -ENOMEM;
1307                         goto out_free_new_fa;
1308                 }
1309         }
1310 
1311         if (!plen)
1312                 tb->tb_num_default++;
1313 
1314         list_add_tail_rcu(&new_fa->fa_list,
1315                           (fa ? &fa->fa_list : fa_head));
1316 
1317         rt_cache_flush(cfg->fc_nlinfo.nl_net);
1318         rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1319                   &cfg->fc_nlinfo, 0);
1320 succeeded:
1321         return 0;
1322 
1323 out_free_new_fa:
1324         kmem_cache_free(fn_alias_kmem, new_fa);
1325 out:
1326         fib_release_info(fi);
1327 err:
1328         return err;
1329 }
1330 
1331 /* should be called with rcu_read_lock */
1332 static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
1333                       t_key key,  const struct flowi4 *flp,
1334                       struct fib_result *res, int fib_flags)
1335 {
1336         struct leaf_info *li;
1337         struct hlist_head *hhead = &l->list;
1338 
1339         hlist_for_each_entry_rcu(li, hhead, hlist) {
1340                 struct fib_alias *fa;
1341 
1342                 if (l->key != (key & li->mask_plen))
1343                         continue;
1344 
1345                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1346                         struct fib_info *fi = fa->fa_info;
1347                         int nhsel, err;
1348 
1349                         if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1350                                 continue;
1351                         if (fi->fib_dead)
1352                                 continue;
1353                         if (fa->fa_info->fib_scope < flp->flowi4_scope)
1354                                 continue;
1355                         fib_alias_accessed(fa);
1356                         err = fib_props[fa->fa_type].error;
1357                         if (err) {
1358 #ifdef CONFIG_IP_FIB_TRIE_STATS
1359                                 t->stats.semantic_match_passed++;
1360 #endif
1361                                 return err;
1362                         }
1363                         if (fi->fib_flags & RTNH_F_DEAD)
1364                                 continue;
1365                         for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1366                                 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1367 
1368                                 if (nh->nh_flags & RTNH_F_DEAD)
1369                                         continue;
1370                                 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1371                                         continue;
1372 
1373 #ifdef CONFIG_IP_FIB_TRIE_STATS
1374                                 t->stats.semantic_match_passed++;
1375 #endif
1376                                 res->prefixlen = li->plen;
1377                                 res->nh_sel = nhsel;
1378                                 res->type = fa->fa_type;
1379                                 res->scope = fa->fa_info->fib_scope;
1380                                 res->fi = fi;
1381                                 res->table = tb;
1382                                 res->fa_head = &li->falh;
1383                                 if (!(fib_flags & FIB_LOOKUP_NOREF))
1384                                         atomic_inc(&fi->fib_clntref);
1385                                 return 0;
1386                         }
1387                 }
1388 
1389 #ifdef CONFIG_IP_FIB_TRIE_STATS
1390                 t->stats.semantic_match_miss++;
1391 #endif
1392         }
1393 
1394         return 1;
1395 }
1396 
1397 int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
1398                      struct fib_result *res, int fib_flags)
1399 {
1400         struct trie *t = (struct trie *) tb->tb_data;
1401         int ret;
1402         struct rt_trie_node *n;
1403         struct tnode *pn;
1404         unsigned int pos, bits;
1405         t_key key = ntohl(flp->daddr);
1406         unsigned int chopped_off;
1407         t_key cindex = 0;
1408         unsigned int current_prefix_length = KEYLENGTH;
1409         struct tnode *cn;
1410         t_key pref_mismatch;
1411 
1412         rcu_read_lock();
1413 
1414         n = rcu_dereference(t->trie);
1415         if (!n)
1416                 goto failed;
1417 
1418 #ifdef CONFIG_IP_FIB_TRIE_STATS
1419         t->stats.gets++;
1420 #endif
1421 
1422         /* Just a leaf? */
1423         if (IS_LEAF(n)) {
1424                 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1425                 goto found;
1426         }
1427 
1428         pn = (struct tnode *) n;
1429         chopped_off = 0;
1430 
1431         while (pn) {
1432                 pos = pn->pos;
1433                 bits = pn->bits;
1434 
1435                 if (!chopped_off)
1436                         cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1437                                                    pos, bits);
1438 
1439                 n = tnode_get_child_rcu(pn, cindex);
1440 
1441                 if (n == NULL) {
1442 #ifdef CONFIG_IP_FIB_TRIE_STATS
1443                         t->stats.null_node_hit++;
1444 #endif
1445                         goto backtrace;
1446                 }
1447 
1448                 if (IS_LEAF(n)) {
1449                         ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
1450                         if (ret > 0)
1451                                 goto backtrace;
1452                         goto found;
1453                 }
1454 
1455                 cn = (struct tnode *)n;
1456 
1457                 /*
1458                  * It's a tnode, and we can do some extra checks here if we
1459                  * like, to avoid descending into a dead-end branch.
1460                  * This tnode is in the parent's child array at index
1461                  * key[p_pos..p_pos+p_bits] but potentially with some bits
1462                  * chopped off, so in reality the index may be just a
1463                  * subprefix, padded with zero at the end.
1464                  * We can also take a look at any skipped bits in this
1465                  * tnode - everything up to p_pos is supposed to be ok,
1466                  * and the non-chopped bits of the index (se previous
1467                  * paragraph) are also guaranteed ok, but the rest is
1468                  * considered unknown.
1469                  *
1470                  * The skipped bits are key[pos+bits..cn->pos].
1471                  */
1472 
1473                 /* If current_prefix_length < pos+bits, we are already doing
1474                  * actual prefix  matching, which means everything from
1475                  * pos+(bits-chopped_off) onward must be zero along some
1476                  * branch of this subtree - otherwise there is *no* valid
1477                  * prefix present. Here we can only check the skipped
1478                  * bits. Remember, since we have already indexed into the
1479                  * parent's child array, we know that the bits we chopped of
1480                  * *are* zero.
1481                  */
1482 
1483                 /* NOTA BENE: Checking only skipped bits
1484                    for the new node here */
1485 
1486                 if (current_prefix_length < pos+bits) {
1487                         if (tkey_extract_bits(cn->key, current_prefix_length,
1488                                                 cn->pos - current_prefix_length)
1489                             || !(cn->child[0]))
1490                                 goto backtrace;
1491                 }
1492 
1493                 /*
1494                  * If chopped_off=0, the index is fully validated and we
1495                  * only need to look at the skipped bits for this, the new,
1496                  * tnode. What we actually want to do is to find out if
1497                  * these skipped bits match our key perfectly, or if we will
1498                  * have to count on finding a matching prefix further down,
1499                  * because if we do, we would like to have some way of
1500                  * verifying the existence of such a prefix at this point.
1501                  */
1502 
1503                 /* The only thing we can do at this point is to verify that
1504                  * any such matching prefix can indeed be a prefix to our
1505                  * key, and if the bits in the node we are inspecting that
1506                  * do not match our key are not ZERO, this cannot be true.
1507                  * Thus, find out where there is a mismatch (before cn->pos)
1508                  * and verify that all the mismatching bits are zero in the
1509                  * new tnode's key.
1510                  */
1511 
1512                 /*
1513                  * Note: We aren't very concerned about the piece of
1514                  * the key that precede pn->pos+pn->bits, since these
1515                  * have already been checked. The bits after cn->pos
1516                  * aren't checked since these are by definition
1517                  * "unknown" at this point. Thus, what we want to see
1518                  * is if we are about to enter the "prefix matching"
1519                  * state, and in that case verify that the skipped
1520                  * bits that will prevail throughout this subtree are
1521                  * zero, as they have to be if we are to find a
1522                  * matching prefix.
1523                  */
1524 
1525                 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
1526 
1527                 /*
1528                  * In short: If skipped bits in this node do not match
1529                  * the search key, enter the "prefix matching"
1530                  * state.directly.
1531                  */
1532                 if (pref_mismatch) {
1533                         /* fls(x) = __fls(x) + 1 */
1534                         int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
1535 
1536                         if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
1537                                 goto backtrace;
1538 
1539                         if (current_prefix_length >= cn->pos)
1540                                 current_prefix_length = mp;
1541                 }
1542 
1543                 pn = (struct tnode *)n; /* Descend */
1544                 chopped_off = 0;
1545                 continue;
1546 
1547 backtrace:
1548                 chopped_off++;
1549 
1550                 /* As zero don't change the child key (cindex) */
1551                 while ((chopped_off <= pn->bits)
1552                        && !(cindex & (1<<(chopped_off-1))))
1553                         chopped_off++;
1554 
1555                 /* Decrease current_... with bits chopped off */
1556                 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1557                         current_prefix_length = pn->pos + pn->bits
1558                                 - chopped_off;
1559 
1560                 /*
1561                  * Either we do the actual chop off according or if we have
1562                  * chopped off all bits in this tnode walk up to our parent.
1563                  */
1564 
1565                 if (chopped_off <= pn->bits) {
1566                         cindex &= ~(1 << (chopped_off-1));
1567                 } else {
1568                         struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
1569                         if (!parent)
1570                                 goto failed;
1571 
1572                         /* Get Child's index */
1573                         cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1574                         pn = parent;
1575                         chopped_off = 0;
1576 
1577 #ifdef CONFIG_IP_FIB_TRIE_STATS
1578                         t->stats.backtrack++;
1579 #endif
1580                         goto backtrace;
1581                 }
1582         }
1583 failed:
1584         ret = 1;
1585 found:
1586         rcu_read_unlock();
1587         return ret;
1588 }
1589 EXPORT_SYMBOL_GPL(fib_table_lookup);
1590 
1591 /*
1592  * Remove the leaf and return parent.
1593  */
1594 static void trie_leaf_remove(struct trie *t, struct leaf *l)
1595 {
1596         struct tnode *tp = node_parent((struct rt_trie_node *) l);
1597 
1598         pr_debug("entering trie_leaf_remove(%p)\n", l);
1599 
1600         if (tp) {
1601                 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
1602                 put_child(tp, cindex, NULL);
1603                 trie_rebalance(t, tp);
1604         } else
1605                 RCU_INIT_POINTER(t->trie, NULL);
1606 
1607         free_leaf(l);
1608 }
1609 
1610 /*
1611  * Caller must hold RTNL.
1612  */
1613 int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
1614 {
1615         struct trie *t = (struct trie *) tb->tb_data;
1616         u32 key, mask;
1617         int plen = cfg->fc_dst_len;
1618         u8 tos = cfg->fc_tos;
1619         struct fib_alias *fa, *fa_to_delete;
1620         struct list_head *fa_head;
1621         struct leaf *l;
1622         struct leaf_info *li;
1623 
1624         if (plen > 32)
1625                 return -EINVAL;
1626 
1627         key = ntohl(cfg->fc_dst);
1628         mask = ntohl(inet_make_mask(plen));
1629 
1630         if (key & ~mask)
1631                 return -EINVAL;
1632 
1633         key = key & mask;
1634         l = fib_find_node(t, key);
1635 
1636         if (!l)
1637                 return -ESRCH;
1638 
1639         li = find_leaf_info(l, plen);
1640 
1641         if (!li)
1642                 return -ESRCH;
1643 
1644         fa_head = &li->falh;
1645         fa = fib_find_alias(fa_head, tos, 0);
1646 
1647         if (!fa)
1648                 return -ESRCH;
1649 
1650         pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1651 
1652         fa_to_delete = NULL;
1653         fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1654         list_for_each_entry_continue(fa, fa_head, fa_list) {
1655                 struct fib_info *fi = fa->fa_info;
1656 
1657                 if (fa->fa_tos != tos)
1658                         break;
1659 
1660                 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1661                     (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1662                      fa->fa_info->fib_scope == cfg->fc_scope) &&
1663                     (!cfg->fc_prefsrc ||
1664                      fi->fib_prefsrc == cfg->fc_prefsrc) &&
1665                     (!cfg->fc_protocol ||
1666                      fi->fib_protocol == cfg->fc_protocol) &&
1667                     fib_nh_match(cfg, fi) == 0) {
1668                         fa_to_delete = fa;
1669                         break;
1670                 }
1671         }
1672 
1673         if (!fa_to_delete)
1674                 return -ESRCH;
1675 
1676         fa = fa_to_delete;
1677         rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1678                   &cfg->fc_nlinfo, 0);
1679 
1680         list_del_rcu(&fa->fa_list);
1681 
1682         if (!plen)
1683                 tb->tb_num_default--;
1684 
1685         if (list_empty(fa_head)) {
1686                 hlist_del_rcu(&li->hlist);
1687                 free_leaf_info(li);
1688         }
1689 
1690         if (hlist_empty(&l->list))
1691                 trie_leaf_remove(t, l);
1692 
1693         if (fa->fa_state & FA_S_ACCESSED)
1694                 rt_cache_flush(cfg->fc_nlinfo.nl_net);
1695 
1696         fib_release_info(fa->fa_info);
1697         alias_free_mem_rcu(fa);
1698         return 0;
1699 }
1700 
1701 static int trie_flush_list(struct list_head *head)
1702 {
1703         struct fib_alias *fa, *fa_node;
1704         int found = 0;
1705 
1706         list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1707                 struct fib_info *fi = fa->fa_info;
1708 
1709                 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1710                         list_del_rcu(&fa->fa_list);
1711                         fib_release_info(fa->fa_info);
1712                         alias_free_mem_rcu(fa);
1713                         found++;
1714                 }
1715         }
1716         return found;
1717 }
1718 
1719 static int trie_flush_leaf(struct leaf *l)
1720 {
1721         int found = 0;
1722         struct hlist_head *lih = &l->list;
1723         struct hlist_node *tmp;
1724         struct leaf_info *li = NULL;
1725 
1726         hlist_for_each_entry_safe(li, tmp, lih, hlist) {
1727                 found += trie_flush_list(&li->falh);
1728 
1729                 if (list_empty(&li->falh)) {
1730                         hlist_del_rcu(&li->hlist);
1731                         free_leaf_info(li);
1732                 }
1733         }
1734         return found;
1735 }
1736 
1737 /*
1738  * Scan for the next right leaf starting at node p->child[idx]
1739  * Since we have back pointer, no recursion necessary.
1740  */
1741 static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1742 {
1743         do {
1744                 t_key idx;
1745 
1746                 if (c)
1747                         idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
1748                 else
1749                         idx = 0;
1750 
1751                 while (idx < 1u << p->bits) {
1752                         c = tnode_get_child_rcu(p, idx++);
1753                         if (!c)
1754                                 continue;
1755 
1756                         if (IS_LEAF(c))
1757                                 return (struct leaf *) c;
1758 
1759                         /* Rescan start scanning in new node */
1760                         p = (struct tnode *) c;
1761                         idx = 0;
1762                 }
1763 
1764                 /* Node empty, walk back up to parent */
1765                 c = (struct rt_trie_node *) p;
1766         } while ((p = node_parent_rcu(c)) != NULL);
1767 
1768         return NULL; /* Root of trie */
1769 }
1770 
1771 static struct leaf *trie_firstleaf(struct trie *t)
1772 {
1773         struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
1774 
1775         if (!n)
1776                 return NULL;
1777 
1778         if (IS_LEAF(n))          /* trie is just a leaf */
1779                 return (struct leaf *) n;
1780 
1781         return leaf_walk_rcu(n, NULL);
1782 }
1783 
1784 static struct leaf *trie_nextleaf(struct leaf *l)
1785 {
1786         struct rt_trie_node *c = (struct rt_trie_node *) l;
1787         struct tnode *p = node_parent_rcu(c);
1788 
1789         if (!p)
1790                 return NULL;    /* trie with just one leaf */
1791 
1792         return leaf_walk_rcu(p, c);
1793 }
1794 
1795 static struct leaf *trie_leafindex(struct trie *t, int index)
1796 {
1797         struct leaf *l = trie_firstleaf(t);
1798 
1799         while (l && index-- > 0)
1800                 l = trie_nextleaf(l);
1801 
1802         return l;
1803 }
1804 
1805 
1806 /*
1807  * Caller must hold RTNL.
1808  */
1809 int fib_table_flush(struct fib_table *tb)
1810 {
1811         struct trie *t = (struct trie *) tb->tb_data;
1812         struct leaf *l, *ll = NULL;
1813         int found = 0;
1814 
1815         for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
1816                 found += trie_flush_leaf(l);
1817 
1818                 if (ll && hlist_empty(&ll->list))
1819                         trie_leaf_remove(t, ll);
1820                 ll = l;
1821         }
1822 
1823         if (ll && hlist_empty(&ll->list))
1824                 trie_leaf_remove(t, ll);
1825 
1826         pr_debug("trie_flush found=%d\n", found);
1827         return found;
1828 }
1829 
1830 void fib_free_table(struct fib_table *tb)
1831 {
1832         kfree(tb);
1833 }
1834 
1835 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1836                            struct fib_table *tb,
1837                            struct sk_buff *skb, struct netlink_callback *cb)
1838 {
1839         int i, s_i;
1840         struct fib_alias *fa;
1841         __be32 xkey = htonl(key);
1842 
1843         s_i = cb->args[5];
1844         i = 0;
1845 
1846         /* rcu_read_lock is hold by caller */
1847 
1848         list_for_each_entry_rcu(fa, fah, fa_list) {
1849                 if (i < s_i) {
1850                         i++;
1851                         continue;
1852                 }
1853 
1854                 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
1855                                   cb->nlh->nlmsg_seq,
1856                                   RTM_NEWROUTE,
1857                                   tb->tb_id,
1858                                   fa->fa_type,
1859                                   xkey,
1860                                   plen,
1861                                   fa->fa_tos,
1862                                   fa->fa_info, NLM_F_MULTI) < 0) {
1863                         cb->args[5] = i;
1864                         return -1;
1865                 }
1866                 i++;
1867         }
1868         cb->args[5] = i;
1869         return skb->len;
1870 }
1871 
1872 static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1873                         struct sk_buff *skb, struct netlink_callback *cb)
1874 {
1875         struct leaf_info *li;
1876         int i, s_i;
1877 
1878         s_i = cb->args[4];
1879         i = 0;
1880 
1881         /* rcu_read_lock is hold by caller */
1882         hlist_for_each_entry_rcu(li, &l->list, hlist) {
1883                 if (i < s_i) {
1884                         i++;
1885                         continue;
1886                 }
1887 
1888                 if (i > s_i)
1889                         cb->args[5] = 0;
1890 
1891                 if (list_empty(&li->falh))
1892                         continue;
1893 
1894                 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
1895                         cb->args[4] = i;
1896                         return -1;
1897                 }
1898                 i++;
1899         }
1900 
1901         cb->args[4] = i;
1902         return skb->len;
1903 }
1904 
1905 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1906                    struct netlink_callback *cb)
1907 {
1908         struct leaf *l;
1909         struct trie *t = (struct trie *) tb->tb_data;
1910         t_key key = cb->args[2];
1911         int count = cb->args[3];
1912 
1913         rcu_read_lock();
1914         /* Dump starting at last key.
1915          * Note: 0.0.0.0/0 (ie default) is first key.
1916          */
1917         if (count == 0)
1918                 l = trie_firstleaf(t);
1919         else {
1920                 /* Normally, continue from last key, but if that is missing
1921                  * fallback to using slow rescan
1922                  */
1923                 l = fib_find_node(t, key);
1924                 if (!l)
1925                         l = trie_leafindex(t, count);
1926         }
1927 
1928         while (l) {
1929                 cb->args[2] = l->key;
1930                 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
1931                         cb->args[3] = count;
1932                         rcu_read_unlock();
1933                         return -1;
1934                 }
1935 
1936                 ++count;
1937                 l = trie_nextleaf(l);
1938                 memset(&cb->args[4], 0,
1939                        sizeof(cb->args) - 4*sizeof(cb->args[0]));
1940         }
1941         cb->args[3] = count;
1942         rcu_read_unlock();
1943 
1944         return skb->len;
1945 }
1946 
1947 void __init fib_trie_init(void)
1948 {
1949         fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1950                                           sizeof(struct fib_alias),
1951                                           0, SLAB_PANIC, NULL);
1952 
1953         trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1954                                            max(sizeof(struct leaf),
1955                                                sizeof(struct leaf_info)),
1956                                            0, SLAB_PANIC, NULL);
1957 }
1958 
1959 
1960 struct fib_table *fib_trie_table(u32 id)
1961 {
1962         struct fib_table *tb;
1963         struct trie *t;
1964 
1965         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1966                      GFP_KERNEL);
1967         if (tb == NULL)
1968                 return NULL;
1969 
1970         tb->tb_id = id;
1971         tb->tb_default = -1;
1972         tb->tb_num_default = 0;
1973 
1974         t = (struct trie *) tb->tb_data;
1975         memset(t, 0, sizeof(*t));
1976 
1977         return tb;
1978 }
1979 
1980 #ifdef CONFIG_PROC_FS
1981 /* Depth first Trie walk iterator */
1982 struct fib_trie_iter {
1983         struct seq_net_private p;
1984         struct fib_table *tb;
1985         struct tnode *tnode;
1986         unsigned int index;
1987         unsigned int depth;
1988 };
1989 
1990 static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
1991 {
1992         struct tnode *tn = iter->tnode;
1993         unsigned int cindex = iter->index;
1994         struct tnode *p;
1995 
1996         /* A single entry routing table */
1997         if (!tn)
1998                 return NULL;
1999 
2000         pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2001                  iter->tnode, iter->index, iter->depth);
2002 rescan:
2003         while (cindex < (1<<tn->bits)) {
2004                 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
2005 
2006                 if (n) {
2007                         if (IS_LEAF(n)) {
2008                                 iter->tnode = tn;
2009                                 iter->index = cindex + 1;
2010                         } else {
2011                                 /* push down one level */
2012                                 iter->tnode = (struct tnode *) n;
2013                                 iter->index = 0;
2014                                 ++iter->depth;
2015                         }
2016                         return n;
2017                 }
2018 
2019                 ++cindex;
2020         }
2021 
2022         /* Current node exhausted, pop back up */
2023         p = node_parent_rcu((struct rt_trie_node *)tn);
2024         if (p) {
2025                 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2026                 tn = p;
2027                 --iter->depth;
2028                 goto rescan;
2029         }
2030 
2031         /* got root? */
2032         return NULL;
2033 }
2034 
2035 static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
2036                                        struct trie *t)
2037 {
2038         struct rt_trie_node *n;
2039 
2040         if (!t)
2041                 return NULL;
2042 
2043         n = rcu_dereference(t->trie);
2044         if (!n)
2045                 return NULL;
2046 
2047         if (IS_TNODE(n)) {
2048                 iter->tnode = (struct tnode *) n;
2049                 iter->index = 0;
2050                 iter->depth = 1;
2051         } else {
2052                 iter->tnode = NULL;
2053                 iter->index = 0;
2054                 iter->depth = 0;
2055         }
2056 
2057         return n;
2058 }
2059 
2060 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
2061 {
2062         struct rt_trie_node *n;
2063         struct fib_trie_iter iter;
2064 
2065         memset(s, 0, sizeof(*s));
2066 
2067         rcu_read_lock();
2068         for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
2069                 if (IS_LEAF(n)) {
2070                         struct leaf *l = (struct leaf *)n;
2071                         struct leaf_info *li;
2072 
2073                         s->leaves++;
2074                         s->totdepth += iter.depth;
2075                         if (iter.depth > s->maxdepth)
2076                                 s->maxdepth = iter.depth;
2077 
2078                         hlist_for_each_entry_rcu(li, &l->list, hlist)
2079                                 ++s->prefixes;
2080                 } else {
2081                         const struct tnode *tn = (const struct tnode *) n;
2082                         int i;
2083 
2084                         s->tnodes++;
2085                         if (tn->bits < MAX_STAT_DEPTH)
2086                                 s->nodesizes[tn->bits]++;
2087 
2088                         for (i = 0; i < (1<<tn->bits); i++)
2089                                 if (!tn->child[i])
2090                                         s->nullpointers++;
2091                 }
2092         }
2093         rcu_read_unlock();
2094 }
2095 
2096 /*
2097  *      This outputs /proc/net/fib_triestats
2098  */
2099 static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
2100 {
2101         unsigned int i, max, pointers, bytes, avdepth;
2102 
2103         if (stat->leaves)
2104                 avdepth = stat->totdepth*100 / stat->leaves;
2105         else
2106                 avdepth = 0;
2107 
2108         seq_printf(seq, "\tAver depth:     %u.%02d\n",
2109                    avdepth / 100, avdepth % 100);
2110         seq_printf(seq, "\tMax depth:      %u\n", stat->maxdepth);
2111 
2112         seq_printf(seq, "\tLeaves:         %u\n", stat->leaves);
2113         bytes = sizeof(struct leaf) * stat->leaves;
2114 
2115         seq_printf(seq, "\tPrefixes:       %u\n", stat->prefixes);
2116         bytes += sizeof(struct leaf_info) * stat->prefixes;
2117 
2118         seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
2119         bytes += sizeof(struct tnode) * stat->tnodes;
2120 
2121         max = MAX_STAT_DEPTH;
2122         while (max > 0 && stat->nodesizes[max-1] == 0)
2123                 max--;
2124 
2125         pointers = 0;
2126         for (i = 1; i < max; i++)
2127                 if (stat->nodesizes[i] != 0) {
2128                         seq_printf(seq, "  %u: %u",  i, stat->nodesizes[i]);
2129                         pointers += (1<<i) * stat->nodesizes[i];
2130                 }
2131         seq_putc(seq, '\n');
2132         seq_printf(seq, "\tPointers: %u\n", pointers);
2133 
2134         bytes += sizeof(struct rt_trie_node *) * pointers;
2135         seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2136         seq_printf(seq, "Total size: %u  kB\n", (bytes + 1023) / 1024);
2137 }
2138 
2139 #ifdef CONFIG_IP_FIB_TRIE_STATS
2140 static void trie_show_usage(struct seq_file *seq,
2141                             const struct trie_use_stats *stats)
2142 {
2143         seq_printf(seq, "\nCounters:\n---------\n");
2144         seq_printf(seq, "gets = %u\n", stats->gets);
2145         seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2146         seq_printf(seq, "semantic match passed = %u\n",
2147                    stats->semantic_match_passed);
2148         seq_printf(seq, "semantic match miss = %u\n",
2149                    stats->semantic_match_miss);
2150         seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2151         seq_printf(seq, "skipped node resize = %u\n\n",
2152                    stats->resize_node_skipped);
2153 }
2154 #endif /*  CONFIG_IP_FIB_TRIE_STATS */
2155 
2156 static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
2157 {
2158         if (tb->tb_id == RT_TABLE_LOCAL)
2159                 seq_puts(seq, "Local:\n");
2160         else if (tb->tb_id == RT_TABLE_MAIN)
2161                 seq_puts(seq, "Main:\n");
2162         else
2163                 seq_printf(seq, "Id %d:\n", tb->tb_id);
2164 }
2165 
2166 
2167 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2168 {
2169         struct net *net = (struct net *)seq->private;
2170         unsigned int h;
2171 
2172         seq_printf(seq,
2173                    "Basic info: size of leaf:"
2174                    " %Zd bytes, size of tnode: %Zd bytes.\n",
2175                    sizeof(struct leaf), sizeof(struct tnode));
2176 
2177         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2178                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2179                 struct fib_table *tb;
2180 
2181                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2182                         struct trie *t = (struct trie *) tb->tb_data;
2183                         struct trie_stat stat;
2184 
2185                         if (!t)
2186                                 continue;
2187 
2188                         fib_table_print(seq, tb);
2189 
2190                         trie_collect_stats(t, &stat);
2191                         trie_show_stats(seq, &stat);
2192 #ifdef CONFIG_IP_FIB_TRIE_STATS
2193                         trie_show_usage(seq, &t->stats);
2194 #endif
2195                 }
2196         }
2197 
2198         return 0;
2199 }
2200 
2201 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2202 {
2203         return single_open_net(inode, file, fib_triestat_seq_show);
2204 }
2205 
2206 static const struct file_operations fib_triestat_fops = {
2207         .owner  = THIS_MODULE,
2208         .open   = fib_triestat_seq_open,
2209         .read   = seq_read,
2210         .llseek = seq_lseek,
2211         .release = single_release_net,
2212 };
2213 
2214 static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
2215 {
2216         struct fib_trie_iter *iter = seq->private;
2217         struct net *net = seq_file_net(seq);
2218         loff_t idx = 0;
2219         unsigned int h;
2220 
2221         for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2222                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2223                 struct fib_table *tb;
2224 
2225                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2226                         struct rt_trie_node *n;
2227 
2228                         for (n = fib_trie_get_first(iter,
2229                                                     (struct trie *) tb->tb_data);
2230                              n; n = fib_trie_get_next(iter))
2231                                 if (pos == idx++) {
2232                                         iter->tb = tb;
2233                                         return n;
2234                                 }
2235                 }
2236         }
2237 
2238         return NULL;
2239 }
2240 
2241 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2242         __acquires(RCU)
2243 {
2244         rcu_read_lock();
2245         return fib_trie_get_idx(seq, *pos);
2246 }
2247 
2248 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2249 {
2250         struct fib_trie_iter *iter = seq->private;
2251         struct net *net = seq_file_net(seq);
2252         struct fib_table *tb = iter->tb;
2253         struct hlist_node *tb_node;
2254         unsigned int h;
2255         struct rt_trie_node *n;
2256 
2257         ++*pos;
2258         /* next node in same table */
2259         n = fib_trie_get_next(iter);
2260         if (n)
2261                 return n;
2262 
2263         /* walk rest of this hash chain */
2264         h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2265         while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2266                 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2267                 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2268                 if (n)
2269                         goto found;
2270         }
2271 
2272         /* new hash chain */
2273         while (++h < FIB_TABLE_HASHSZ) {
2274                 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2275                 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
2276                         n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2277                         if (n)
2278                                 goto found;
2279                 }
2280         }
2281         return NULL;
2282 
2283 found:
2284         iter->tb = tb;
2285         return n;
2286 }
2287 
2288 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2289         __releases(RCU)
2290 {
2291         rcu_read_unlock();
2292 }
2293 
2294 static void seq_indent(struct seq_file *seq, int n)
2295 {
2296         while (n-- > 0)
2297                 seq_puts(seq, "   ");
2298 }
2299 
2300 static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
2301 {
2302         switch (s) {
2303         case RT_SCOPE_UNIVERSE: return "universe";
2304         case RT_SCOPE_SITE:     return "site";
2305         case RT_SCOPE_LINK:     return "link";
2306         case RT_SCOPE_HOST:     return "host";
2307         case RT_SCOPE_NOWHERE:  return "nowhere";
2308         default:
2309                 snprintf(buf, len, "scope=%d", s);
2310                 return buf;
2311         }
2312 }
2313 
2314 static const char *const rtn_type_names[__RTN_MAX] = {
2315         [RTN_UNSPEC] = "UNSPEC",
2316         [RTN_UNICAST] = "UNICAST",
2317         [RTN_LOCAL] = "LOCAL",
2318         [RTN_BROADCAST] = "BROADCAST",
2319         [RTN_ANYCAST] = "ANYCAST",
2320         [RTN_MULTICAST] = "MULTICAST",
2321         [RTN_BLACKHOLE] = "BLACKHOLE",
2322         [RTN_UNREACHABLE] = "UNREACHABLE",
2323         [RTN_PROHIBIT] = "PROHIBIT",
2324         [RTN_THROW] = "THROW",
2325         [RTN_NAT] = "NAT",
2326         [RTN_XRESOLVE] = "XRESOLVE",
2327 };
2328 
2329 static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
2330 {
2331         if (t < __RTN_MAX && rtn_type_names[t])
2332                 return rtn_type_names[t];
2333         snprintf(buf, len, "type %u", t);
2334         return buf;
2335 }
2336 
2337 /* Pretty print the trie */
2338 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2339 {
2340         const struct fib_trie_iter *iter = seq->private;
2341         struct rt_trie_node *n = v;
2342 
2343         if (!node_parent_rcu(n))
2344                 fib_table_print(seq, iter->tb);
2345 
2346         if (IS_TNODE(n)) {
2347                 struct tnode *tn = (struct tnode *) n;
2348                 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
2349 
2350                 seq_indent(seq, iter->depth-1);
2351                 seq_printf(seq, "  +-- %pI4/%d %d %d %d\n",
2352                            &prf, tn->pos, tn->bits, tn->full_children,
2353                            tn->empty_children);
2354 
2355         } else {
2356                 struct leaf *l = (struct leaf *) n;
2357                 struct leaf_info *li;
2358                 __be32 val = htonl(l->key);
2359 
2360                 seq_indent(seq, iter->depth);
2361                 seq_printf(seq, "  |-- %pI4\n", &val);
2362 
2363                 hlist_for_each_entry_rcu(li, &l->list, hlist) {
2364                         struct fib_alias *fa;
2365 
2366                         list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2367                                 char buf1[32], buf2[32];
2368 
2369                                 seq_indent(seq, iter->depth+1);
2370                                 seq_printf(seq, "  /%d %s %s", li->plen,
2371                                            rtn_scope(buf1, sizeof(buf1),
2372                                                      fa->fa_info->fib_scope),
2373                                            rtn_type(buf2, sizeof(buf2),
2374                                                     fa->fa_type));
2375                                 if (fa->fa_tos)
2376                                         seq_printf(seq, " tos=%d", fa->fa_tos);
2377                                 seq_putc(seq, '\n');
2378                         }
2379                 }
2380         }
2381 
2382         return 0;
2383 }
2384 
2385 static const struct seq_operations fib_trie_seq_ops = {
2386         .start  = fib_trie_seq_start,
2387         .next   = fib_trie_seq_next,
2388         .stop   = fib_trie_seq_stop,
2389         .show   = fib_trie_seq_show,
2390 };
2391 
2392 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2393 {
2394         return seq_open_net(inode, file, &fib_trie_seq_ops,
2395                             sizeof(struct fib_trie_iter));
2396 }
2397 
2398 static const struct file_operations fib_trie_fops = {
2399         .owner  = THIS_MODULE,
2400         .open   = fib_trie_seq_open,
2401         .read   = seq_read,
2402         .llseek = seq_lseek,
2403         .release = seq_release_net,
2404 };
2405 
2406 struct fib_route_iter {
2407         struct seq_net_private p;
2408         struct trie *main_trie;
2409         loff_t  pos;
2410         t_key   key;
2411 };
2412 
2413 static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2414 {
2415         struct leaf *l = NULL;
2416         struct trie *t = iter->main_trie;
2417 
2418         /* use cache location of last found key */
2419         if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2420                 pos -= iter->pos;
2421         else {
2422                 iter->pos = 0;
2423                 l = trie_firstleaf(t);
2424         }
2425 
2426         while (l && pos-- > 0) {
2427                 iter->pos++;
2428                 l = trie_nextleaf(l);
2429         }
2430 
2431         if (l)
2432                 iter->key = pos;        /* remember it */
2433         else
2434                 iter->pos = 0;          /* forget it */
2435 
2436         return l;
2437 }
2438 
2439 static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2440         __acquires(RCU)
2441 {
2442         struct fib_route_iter *iter = seq->private;
2443         struct fib_table *tb;
2444 
2445         rcu_read_lock();
2446         tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
2447         if (!tb)
2448                 return NULL;
2449 
2450         iter->main_trie = (struct trie *) tb->tb_data;
2451         if (*pos == 0)
2452                 return SEQ_START_TOKEN;
2453         else
2454                 return fib_route_get_idx(iter, *pos - 1);
2455 }
2456 
2457 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2458 {
2459         struct fib_route_iter *iter = seq->private;
2460         struct leaf *l = v;
2461 
2462         ++*pos;
2463         if (v == SEQ_START_TOKEN) {
2464                 iter->pos = 0;
2465                 l = trie_firstleaf(iter->main_trie);
2466         } else {
2467                 iter->pos++;
2468                 l = trie_nextleaf(l);
2469         }
2470 
2471         if (l)
2472                 iter->key = l->key;
2473         else
2474                 iter->pos = 0;
2475         return l;
2476 }
2477 
2478 static void fib_route_seq_stop(struct seq_file *seq, void *v)
2479         __releases(RCU)
2480 {
2481         rcu_read_unlock();
2482 }
2483 
2484 static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
2485 {
2486         unsigned int flags = 0;
2487 
2488         if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2489                 flags = RTF_REJECT;
2490         if (fi && fi->fib_nh->nh_gw)
2491                 flags |= RTF_GATEWAY;
2492         if (mask == htonl(0xFFFFFFFF))
2493                 flags |= RTF_HOST;
2494         flags |= RTF_UP;
2495         return flags;
2496 }
2497 
2498 /*
2499  *      This outputs /proc/net/route.
2500  *      The format of the file is not supposed to be changed
2501  *      and needs to be same as fib_hash output to avoid breaking
2502  *      legacy utilities
2503  */
2504 static int fib_route_seq_show(struct seq_file *seq, void *v)
2505 {
2506         struct leaf *l = v;
2507         struct leaf_info *li;
2508 
2509         if (v == SEQ_START_TOKEN) {
2510                 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2511                            "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2512                            "\tWindow\tIRTT");
2513                 return 0;
2514         }
2515 
2516         hlist_for_each_entry_rcu(li, &l->list, hlist) {
2517                 struct fib_alias *fa;
2518                 __be32 mask, prefix;
2519 
2520                 mask = inet_make_mask(li->plen);
2521                 prefix = htonl(l->key);
2522 
2523                 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2524                         const struct fib_info *fi = fa->fa_info;
2525                         unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
2526 
2527                         if (fa->fa_type == RTN_BROADCAST
2528                             || fa->fa_type == RTN_MULTICAST)
2529                                 continue;
2530 
2531                         seq_setwidth(seq, 127);
2532 
2533                         if (fi)
2534                                 seq_printf(seq,
2535                                          "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2536                                          "%d\t%08X\t%d\t%u\t%u",
2537                                          fi->fib_dev ? fi->fib_dev->name : "*",
2538                                          prefix,
2539                                          fi->fib_nh->nh_gw, flags, 0, 0,
2540                                          fi->fib_priority,
2541                                          mask,
2542                                          (fi->fib_advmss ?
2543                                           fi->fib_advmss + 40 : 0),
2544                                          fi->fib_window,
2545                                          fi->fib_rtt >> 3);
2546                         else
2547                                 seq_printf(seq,
2548                                          "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2549                                          "%d\t%08X\t%d\t%u\t%u",
2550                                          prefix, 0, flags, 0, 0, 0,
2551                                          mask, 0, 0, 0);
2552 
2553                         seq_pad(seq, '\n');
2554                 }
2555         }
2556 
2557         return 0;
2558 }
2559 
2560 static const struct seq_operations fib_route_seq_ops = {
2561         .start  = fib_route_seq_start,
2562         .next   = fib_route_seq_next,
2563         .stop   = fib_route_seq_stop,
2564         .show   = fib_route_seq_show,
2565 };
2566 
2567 static int fib_route_seq_open(struct inode *inode, struct file *file)
2568 {
2569         return seq_open_net(inode, file, &fib_route_seq_ops,
2570                             sizeof(struct fib_route_iter));
2571 }
2572 
2573 static const struct file_operations fib_route_fops = {
2574         .owner  = THIS_MODULE,
2575         .open   = fib_route_seq_open,
2576         .read   = seq_read,
2577         .llseek = seq_lseek,
2578         .release = seq_release_net,
2579 };
2580 
2581 int __net_init fib_proc_init(struct net *net)
2582 {
2583         if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
2584                 goto out1;
2585 
2586         if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2587                          &fib_triestat_fops))
2588                 goto out2;
2589 
2590         if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
2591                 goto out3;
2592 
2593         return 0;
2594 
2595 out3:
2596         remove_proc_entry("fib_triestat", net->proc_net);
2597 out2:
2598         remove_proc_entry("fib_trie", net->proc_net);
2599 out1:
2600         return -ENOMEM;
2601 }
2602 
2603 void __net_exit fib_proc_exit(struct net *net)
2604 {
2605         remove_proc_entry("fib_trie", net->proc_net);
2606         remove_proc_entry("fib_triestat", net->proc_net);
2607         remove_proc_entry("route", net->proc_net);
2608 }
2609 
2610 #endif /* CONFIG_PROC_FS */
2611 

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