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