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