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