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