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