Version:  2.0.40 2.2.26 2.4.37 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4

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

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