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