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