Branch data Line data Source code
1 : : /*
2 : : * Linux INET6 implementation
3 : : * Forwarding Information Database
4 : : *
5 : : * Authors:
6 : : * Pedro Roque <roque@di.fc.ul.pt>
7 : : *
8 : : * This program is free software; you can redistribute it and/or
9 : : * modify it under the terms of the GNU General Public License
10 : : * as published by the Free Software Foundation; either version
11 : : * 2 of the License, or (at your option) any later version.
12 : : */
13 : :
14 : : /*
15 : : * Changes:
16 : : * Yuji SEKIYA @USAGI: Support default route on router node;
17 : : * remove ip6_null_entry from the top of
18 : : * routing table.
19 : : * Ville Nuorvala: Fixed routing subtrees.
20 : : */
21 : :
22 : : #define pr_fmt(fmt) "IPv6: " fmt
23 : :
24 : : #include <linux/errno.h>
25 : : #include <linux/types.h>
26 : : #include <linux/net.h>
27 : : #include <linux/route.h>
28 : : #include <linux/netdevice.h>
29 : : #include <linux/in6.h>
30 : : #include <linux/init.h>
31 : : #include <linux/list.h>
32 : : #include <linux/slab.h>
33 : :
34 : : #include <net/ipv6.h>
35 : : #include <net/ndisc.h>
36 : : #include <net/addrconf.h>
37 : :
38 : : #include <net/ip6_fib.h>
39 : : #include <net/ip6_route.h>
40 : :
41 : : #define RT6_DEBUG 2
42 : :
43 : : #if RT6_DEBUG >= 3
44 : : #define RT6_TRACE(x...) pr_debug(x)
45 : : #else
46 : : #define RT6_TRACE(x...) do { ; } while (0)
47 : : #endif
48 : :
49 : : static struct kmem_cache * fib6_node_kmem __read_mostly;
50 : :
51 : : enum fib_walk_state_t
52 : : {
53 : : #ifdef CONFIG_IPV6_SUBTREES
54 : : FWS_S,
55 : : #endif
56 : : FWS_L,
57 : : FWS_R,
58 : : FWS_C,
59 : : FWS_U
60 : : };
61 : :
62 : : struct fib6_cleaner_t
63 : : {
64 : : struct fib6_walker_t w;
65 : : struct net *net;
66 : : int (*func)(struct rt6_info *, void *arg);
67 : : void *arg;
68 : : };
69 : :
70 : : static DEFINE_RWLOCK(fib6_walker_lock);
71 : :
72 : : #ifdef CONFIG_IPV6_SUBTREES
73 : : #define FWS_INIT FWS_S
74 : : #else
75 : : #define FWS_INIT FWS_L
76 : : #endif
77 : :
78 : : static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
79 : : struct rt6_info *rt);
80 : : static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
81 : : static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
82 : : static int fib6_walk(struct fib6_walker_t *w);
83 : : static int fib6_walk_continue(struct fib6_walker_t *w);
84 : :
85 : : /*
86 : : * A routing update causes an increase of the serial number on the
87 : : * affected subtree. This allows for cached routes to be asynchronously
88 : : * tested when modifications are made to the destination cache as a
89 : : * result of redirects, path MTU changes, etc.
90 : : */
91 : :
92 : : static __u32 rt_sernum;
93 : :
94 : : static void fib6_gc_timer_cb(unsigned long arg);
95 : :
96 : : static LIST_HEAD(fib6_walkers);
97 : : #define FOR_WALKERS(w) list_for_each_entry(w, &fib6_walkers, lh)
98 : :
99 : : static inline void fib6_walker_link(struct fib6_walker_t *w)
100 : : {
101 : 7 : write_lock_bh(&fib6_walker_lock);
102 : 7 : list_add(&w->lh, &fib6_walkers);
103 : 7 : write_unlock_bh(&fib6_walker_lock);
104 : : }
105 : :
106 : : static inline void fib6_walker_unlink(struct fib6_walker_t *w)
107 : : {
108 : 7 : write_lock_bh(&fib6_walker_lock);
109 : : list_del(&w->lh);
110 : 7 : write_unlock_bh(&fib6_walker_lock);
111 : : }
112 : : static __inline__ u32 fib6_new_sernum(void)
113 : : {
114 : 5 : u32 n = ++rt_sernum;
115 [ - + ]: 5 : if ((__s32)n <= 0)
116 : 5 : rt_sernum = n = 1;
117 : : return n;
118 : : }
119 : :
120 : : /*
121 : : * Auxiliary address test functions for the radix tree.
122 : : *
123 : : * These assume a 32bit processor (although it will work on
124 : : * 64bit processors)
125 : : */
126 : :
127 : : /*
128 : : * test bit
129 : : */
130 : : #if defined(__LITTLE_ENDIAN)
131 : : # define BITOP_BE32_SWIZZLE (0x1F & ~7)
132 : : #else
133 : : # define BITOP_BE32_SWIZZLE 0
134 : : #endif
135 : :
136 : : static __inline__ __be32 addr_bit_set(const void *token, int fn_bit)
137 : : {
138 : : const __be32 *addr = token;
139 : : /*
140 : : * Here,
141 : : * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
142 : : * is optimized version of
143 : : * htonl(1 << ((~fn_bit)&0x1F))
144 : : * See include/asm-generic/bitops/le.h.
145 : : */
146 : 60 : return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
147 : 30 : addr[fn_bit >> 5];
148 : : }
149 : :
150 : : static __inline__ struct fib6_node * node_alloc(void)
151 : : {
152 : : struct fib6_node *fn;
153 : :
154 : 5 : fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
155 : :
156 : : return fn;
157 : : }
158 : :
159 : : static __inline__ void node_free(struct fib6_node * fn)
160 : : {
161 : 5 : kmem_cache_free(fib6_node_kmem, fn);
162 : : }
163 : :
164 : : static __inline__ void rt6_release(struct rt6_info *rt)
165 : : {
166 [ # # + - : 5 : if (atomic_dec_and_test(&rt->rt6i_ref))
# # # # #
# ]
167 : 5 : dst_free(&rt->dst);
168 : : }
169 : :
170 : : static void fib6_link_table(struct net *net, struct fib6_table *tb)
171 : : {
172 : : unsigned int h;
173 : :
174 : : /*
175 : : * Initialize table lock at a single place to give lockdep a key,
176 : : * tables aren't visible prior to being linked to the list.
177 : : */
178 : 0 : rwlock_init(&tb->tb6_lock);
179 : :
180 : : h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
181 : :
182 : : /*
183 : : * No protection necessary, this is the only list mutatation
184 : : * operation, tables never disappear once they exist.
185 : : */
186 : 0 : hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
187 : : }
188 : :
189 : : #ifdef CONFIG_IPV6_MULTIPLE_TABLES
190 : :
191 : : static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
192 : : {
193 : : struct fib6_table *table;
194 : :
195 : : table = kzalloc(sizeof(*table), GFP_ATOMIC);
196 : : if (table) {
197 : : table->tb6_id = id;
198 : : table->tb6_root.leaf = net->ipv6.ip6_null_entry;
199 : : table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
200 : : inet_peer_base_init(&table->tb6_peers);
201 : : }
202 : :
203 : : return table;
204 : : }
205 : :
206 : : struct fib6_table *fib6_new_table(struct net *net, u32 id)
207 : : {
208 : : struct fib6_table *tb;
209 : :
210 : : if (id == 0)
211 : : id = RT6_TABLE_MAIN;
212 : : tb = fib6_get_table(net, id);
213 : : if (tb)
214 : : return tb;
215 : :
216 : : tb = fib6_alloc_table(net, id);
217 : : if (tb)
218 : : fib6_link_table(net, tb);
219 : :
220 : : return tb;
221 : : }
222 : :
223 : : struct fib6_table *fib6_get_table(struct net *net, u32 id)
224 : : {
225 : : struct fib6_table *tb;
226 : : struct hlist_head *head;
227 : : unsigned int h;
228 : :
229 : : if (id == 0)
230 : : id = RT6_TABLE_MAIN;
231 : : h = id & (FIB6_TABLE_HASHSZ - 1);
232 : : rcu_read_lock();
233 : : head = &net->ipv6.fib_table_hash[h];
234 : : hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
235 : : if (tb->tb6_id == id) {
236 : : rcu_read_unlock();
237 : : return tb;
238 : : }
239 : : }
240 : : rcu_read_unlock();
241 : :
242 : : return NULL;
243 : : }
244 : :
245 : : static void __net_init fib6_tables_init(struct net *net)
246 : : {
247 : : fib6_link_table(net, net->ipv6.fib6_main_tbl);
248 : : fib6_link_table(net, net->ipv6.fib6_local_tbl);
249 : : }
250 : : #else
251 : :
252 : 0 : struct fib6_table *fib6_new_table(struct net *net, u32 id)
253 : : {
254 : 0 : return fib6_get_table(net, id);
255 : : }
256 : :
257 : 0 : struct fib6_table *fib6_get_table(struct net *net, u32 id)
258 : : {
259 : 0 : return net->ipv6.fib6_main_tbl;
260 : : }
261 : :
262 : 0 : struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
263 : : int flags, pol_lookup_t lookup)
264 : : {
265 : 5 : return (struct dst_entry *) lookup(net, net->ipv6.fib6_main_tbl, fl6, flags);
266 : : }
267 : :
268 : 0 : static void __net_init fib6_tables_init(struct net *net)
269 : : {
270 : 0 : fib6_link_table(net, net->ipv6.fib6_main_tbl);
271 : 0 : }
272 : :
273 : : #endif
274 : :
275 : 0 : static int fib6_dump_node(struct fib6_walker_t *w)
276 : : {
277 : : int res;
278 : : struct rt6_info *rt;
279 : :
280 [ # # ]: 0 : for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
281 : 0 : res = rt6_dump_route(rt, w->args);
282 [ # # ]: 0 : if (res < 0) {
283 : : /* Frame is full, suspend walking */
284 : 0 : w->leaf = rt;
285 : 0 : return 1;
286 : : }
287 [ # # ]: 0 : WARN_ON(res == 0);
288 : : }
289 : 0 : w->leaf = NULL;
290 : 0 : return 0;
291 : : }
292 : :
293 : 0 : static void fib6_dump_end(struct netlink_callback *cb)
294 : : {
295 : 0 : struct fib6_walker_t *w = (void*)cb->args[2];
296 : :
297 [ # # ]: 0 : if (w) {
298 [ # # ]: 0 : if (cb->args[4]) {
299 : 0 : cb->args[4] = 0;
300 : : fib6_walker_unlink(w);
301 : : }
302 : 0 : cb->args[2] = 0;
303 : 0 : kfree(w);
304 : : }
305 : 0 : cb->done = (void*)cb->args[3];
306 : 0 : cb->args[1] = 3;
307 : 0 : }
308 : :
309 : 0 : static int fib6_dump_done(struct netlink_callback *cb)
310 : : {
311 : 0 : fib6_dump_end(cb);
312 [ # # ]: 0 : return cb->done ? cb->done(cb) : 0;
313 : : }
314 : :
315 : 0 : static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
316 : : struct netlink_callback *cb)
317 : : {
318 : : struct fib6_walker_t *w;
319 : : int res;
320 : :
321 : 0 : w = (void *)cb->args[2];
322 : 0 : w->root = &table->tb6_root;
323 : :
324 [ # # ]: 0 : if (cb->args[4] == 0) {
325 : 0 : w->count = 0;
326 : 0 : w->skip = 0;
327 : :
328 : 0 : read_lock_bh(&table->tb6_lock);
329 : 0 : res = fib6_walk(w);
330 : 0 : read_unlock_bh(&table->tb6_lock);
331 [ # # ]: 0 : if (res > 0) {
332 : 0 : cb->args[4] = 1;
333 : 0 : cb->args[5] = w->root->fn_sernum;
334 : : }
335 : : } else {
336 [ # # ]: 0 : if (cb->args[5] != w->root->fn_sernum) {
337 : : /* Begin at the root if the tree changed */
338 : 0 : cb->args[5] = w->root->fn_sernum;
339 : 0 : w->state = FWS_INIT;
340 : 0 : w->node = w->root;
341 : 0 : w->skip = w->count;
342 : : } else
343 : 0 : w->skip = 0;
344 : :
345 : 0 : read_lock_bh(&table->tb6_lock);
346 : 0 : res = fib6_walk_continue(w);
347 : 0 : read_unlock_bh(&table->tb6_lock);
348 [ # # ]: 0 : if (res <= 0) {
349 : : fib6_walker_unlink(w);
350 : 0 : cb->args[4] = 0;
351 : : }
352 : : }
353 : :
354 : 0 : return res;
355 : : }
356 : :
357 : 0 : static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
358 : : {
359 : : struct net *net = sock_net(skb->sk);
360 : : unsigned int h, s_h;
361 : : unsigned int e = 0, s_e;
362 : : struct rt6_rtnl_dump_arg arg;
363 : : struct fib6_walker_t *w;
364 : : struct fib6_table *tb;
365 : : struct hlist_head *head;
366 : : int res = 0;
367 : :
368 : 0 : s_h = cb->args[0];
369 : 0 : s_e = cb->args[1];
370 : :
371 : 0 : w = (void *)cb->args[2];
372 [ # # ]: 0 : if (!w) {
373 : : /* New dump:
374 : : *
375 : : * 1. hook callback destructor.
376 : : */
377 : 0 : cb->args[3] = (long)cb->done;
378 : 0 : cb->done = fib6_dump_done;
379 : :
380 : : /*
381 : : * 2. allocate and initialize walker.
382 : : */
383 : : w = kzalloc(sizeof(*w), GFP_ATOMIC);
384 [ # # ]: 0 : if (!w)
385 : : return -ENOMEM;
386 : 0 : w->func = fib6_dump_node;
387 : 0 : cb->args[2] = (long)w;
388 : : }
389 : :
390 : 0 : arg.skb = skb;
391 : 0 : arg.cb = cb;
392 : 0 : arg.net = net;
393 : 0 : w->args = &arg;
394 : :
395 : : rcu_read_lock();
396 [ # # ]: 0 : for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
397 : : e = 0;
398 : 0 : head = &net->ipv6.fib_table_hash[h];
399 [ # # ][ # # ]: 0 : hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
[ # # ]
400 [ # # ]: 0 : if (e < s_e)
401 : : goto next;
402 : 0 : res = fib6_dump_table(tb, skb, cb);
403 [ # # ]: 0 : if (res != 0)
404 : : goto out;
405 : : next:
406 : 0 : e++;
407 : : }
408 : : }
409 : : out:
410 : : rcu_read_unlock();
411 : 0 : cb->args[1] = e;
412 : 0 : cb->args[0] = h;
413 : :
414 [ # # ]: 0 : res = res < 0 ? res : skb->len;
415 [ # # ]: 0 : if (res <= 0)
416 : 0 : fib6_dump_end(cb);
417 : 0 : return res;
418 : : }
419 : :
420 : : /*
421 : : * Routing Table
422 : : *
423 : : * return the appropriate node for a routing tree "add" operation
424 : : * by either creating and inserting or by returning an existing
425 : : * node.
426 : : */
427 : :
428 : 0 : static struct fib6_node *fib6_add_1(struct fib6_node *root,
429 : : struct in6_addr *addr, int plen,
430 : : int offset, int allow_create,
431 : : int replace_required)
432 : : {
433 : : struct fib6_node *fn, *in, *ln;
434 : : struct fib6_node *pn = NULL;
435 : : struct rt6key *key;
436 : : int bit;
437 : : __be32 dir = 0;
438 : : __u32 sernum = fib6_new_sernum();
439 : :
440 : : RT6_TRACE("fib6_add_1\n");
441 : :
442 : : /* insert node in tree */
443 : :
444 : : fn = root;
445 : :
446 : : do {
447 : 15 : key = (struct rt6key *)((u8 *)fn->leaf + offset);
448 : :
449 : : /*
450 : : * Prefix match
451 : : */
452 [ + - ][ - + ]: 30 : if (plen < fn->fn_bit ||
453 : 15 : !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
454 [ # # ]: 0 : if (!allow_create) {
455 [ # # ]: 0 : if (replace_required) {
456 : 0 : pr_warn("Can't replace route, no match found\n");
457 : 0 : return ERR_PTR(-ENOENT);
458 : : }
459 : 0 : pr_warn("NLM_F_CREATE should be set when creating new route\n");
460 : : }
461 : : goto insert_above;
462 : : }
463 : :
464 : : /*
465 : : * Exact match ?
466 : : */
467 : :
468 [ - + ]: 15 : if (plen == fn->fn_bit) {
469 : : /* clean up an intermediate node */
470 [ # # ]: 0 : if (!(fn->fn_flags & RTN_RTINFO)) {
471 : : rt6_release(fn->leaf);
472 : 0 : fn->leaf = NULL;
473 : : }
474 : :
475 : 0 : fn->fn_sernum = sernum;
476 : :
477 : 0 : return fn;
478 : : }
479 : :
480 : : /*
481 : : * We have more bits to go
482 : : */
483 : :
484 : : /* Try to walk down on tree. */
485 : 15 : fn->fn_sernum = sernum;
486 : : dir = addr_bit_set(addr, fn->fn_bit);
487 : : pn = fn;
488 [ + + ]: 15 : fn = dir ? fn->right: fn->left;
489 [ + + ]: 15 : } while (fn);
490 : :
491 [ - + ]: 5 : if (!allow_create) {
492 : : /* We should not create new node because
493 : : * NLM_F_REPLACE was specified without NLM_F_CREATE
494 : : * I assume it is safe to require NLM_F_CREATE when
495 : : * REPLACE flag is used! Later we may want to remove the
496 : : * check for replace_required, because according
497 : : * to netlink specification, NLM_F_CREATE
498 : : * MUST be specified if new route is created.
499 : : * That would keep IPv6 consistent with IPv4
500 : : */
501 [ # # ]: 0 : if (replace_required) {
502 : 0 : pr_warn("Can't replace route, no match found\n");
503 : 0 : return ERR_PTR(-ENOENT);
504 : : }
505 : 0 : pr_warn("NLM_F_CREATE should be set when creating new route\n");
506 : : }
507 : : /*
508 : : * We walked to the bottom of tree.
509 : : * Create new leaf node without children.
510 : : */
511 : :
512 : : ln = node_alloc();
513 : :
514 [ + - ]: 5 : if (!ln)
515 : : return ERR_PTR(-ENOMEM);
516 : 5 : ln->fn_bit = plen;
517 : :
518 : 5 : ln->parent = pn;
519 : 5 : ln->fn_sernum = sernum;
520 : :
521 [ - + ]: 5 : if (dir)
522 : 0 : pn->right = ln;
523 : : else
524 : 5 : pn->left = ln;
525 : :
526 : 5 : return ln;
527 : :
528 : :
529 : : insert_above:
530 : : /*
531 : : * split since we don't have a common prefix anymore or
532 : : * we have a less significant route.
533 : : * we've to insert an intermediate node on the list
534 : : * this new node will point to the one we need to create
535 : : * and the current
536 : : */
537 : :
538 : 5 : pn = fn->parent;
539 : :
540 : : /* find 1st bit in difference between the 2 addrs.
541 : :
542 : : See comment in __ipv6_addr_diff: bit may be an invalid value,
543 : : but if it is >= plen, the value is ignored in any case.
544 : : */
545 : :
546 : 5 : bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
547 : :
548 : : /*
549 : : * (intermediate)[in]
550 : : * / \
551 : : * (new leaf node)[ln] (old node)[fn]
552 : : */
553 [ # # ]: 0 : if (plen > bit) {
554 : : in = node_alloc();
555 : : ln = node_alloc();
556 : :
557 [ # # ]: 0 : if (!in || !ln) {
558 [ # # ]: 0 : if (in)
559 : : node_free(in);
560 [ # # ]: 0 : if (ln)
561 : : node_free(ln);
562 : : return ERR_PTR(-ENOMEM);
563 : : }
564 : :
565 : : /*
566 : : * new intermediate node.
567 : : * RTN_RTINFO will
568 : : * be off since that an address that chooses one of
569 : : * the branches would not match less specific routes
570 : : * in the other branch
571 : : */
572 : :
573 : 0 : in->fn_bit = bit;
574 : :
575 : 0 : in->parent = pn;
576 : 0 : in->leaf = fn->leaf;
577 : 0 : atomic_inc(&in->leaf->rt6i_ref);
578 : :
579 : 0 : in->fn_sernum = sernum;
580 : :
581 : : /* update parent pointer */
582 [ # # ]: 0 : if (dir)
583 : 0 : pn->right = in;
584 : : else
585 : 0 : pn->left = in;
586 : :
587 : 0 : ln->fn_bit = plen;
588 : :
589 : 0 : ln->parent = in;
590 : 0 : fn->parent = in;
591 : :
592 : 0 : ln->fn_sernum = sernum;
593 : :
594 [ # # ]: 0 : if (addr_bit_set(addr, bit)) {
595 : 0 : in->right = ln;
596 : 0 : in->left = fn;
597 : : } else {
598 : 0 : in->left = ln;
599 : 0 : in->right = fn;
600 : : }
601 : : } else { /* plen <= bit */
602 : :
603 : : /*
604 : : * (new leaf node)[ln]
605 : : * / \
606 : : * (old node)[fn] NULL
607 : : */
608 : :
609 : : ln = node_alloc();
610 : :
611 [ # # ]: 0 : if (!ln)
612 : : return ERR_PTR(-ENOMEM);
613 : :
614 : 0 : ln->fn_bit = plen;
615 : :
616 : 0 : ln->parent = pn;
617 : :
618 : 0 : ln->fn_sernum = sernum;
619 : :
620 [ # # ]: 0 : if (dir)
621 : 0 : pn->right = ln;
622 : : else
623 : 0 : pn->left = ln;
624 : :
625 [ # # ]: 0 : if (addr_bit_set(&key->addr, plen))
626 : 0 : ln->right = fn;
627 : : else
628 : 0 : ln->left = fn;
629 : :
630 : 0 : fn->parent = ln;
631 : : }
632 : 0 : return ln;
633 : : }
634 : :
635 : : static inline bool rt6_qualify_for_ecmp(struct rt6_info *rt)
636 : : {
637 : 5 : return (rt->rt6i_flags & (RTF_GATEWAY|RTF_ADDRCONF|RTF_DYNAMIC)) ==
638 : : RTF_GATEWAY;
639 : : }
640 : :
641 : : /*
642 : : * Insert routing information in a node.
643 : : */
644 : :
645 : 0 : static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
646 : : struct nl_info *info)
647 : : {
648 : 0 : struct rt6_info *iter = NULL;
649 : : struct rt6_info **ins;
650 [ - + ][ # # ]: 5 : int replace = (info->nlh &&
651 : 0 : (info->nlh->nlmsg_flags & NLM_F_REPLACE));
652 [ - + ][ # # ]: 5 : int add = (!info->nlh ||
653 : 0 : (info->nlh->nlmsg_flags & NLM_F_CREATE));
654 : : int found = 0;
655 : : bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
656 : :
657 : 5 : ins = &fn->leaf;
658 : :
659 [ - + ]: 5 : for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) {
660 : : /*
661 : : * Search for duplicates
662 : : */
663 : :
664 [ # # ]: 0 : if (iter->rt6i_metric == rt->rt6i_metric) {
665 : : /*
666 : : * Same priority level
667 : : */
668 [ # # ][ # # ]: 0 : if (info->nlh &&
669 : 0 : (info->nlh->nlmsg_flags & NLM_F_EXCL))
670 : : return -EEXIST;
671 [ - + ]: 5 : if (replace) {
672 : : found++;
673 : : break;
674 : : }
675 : :
676 [ # # ][ # # ]: 0 : if (iter->dst.dev == rt->dst.dev &&
677 [ # # ]: 0 : iter->rt6i_idev == rt->rt6i_idev &&
678 : : ipv6_addr_equal(&iter->rt6i_gateway,
679 : : &rt->rt6i_gateway)) {
680 [ # # ]: 0 : if (rt->rt6i_nsiblings)
681 : 0 : rt->rt6i_nsiblings = 0;
682 [ # # ]: 0 : if (!(iter->rt6i_flags & RTF_EXPIRES))
683 : : return -EEXIST;
684 [ # # ]: 0 : if (!(rt->rt6i_flags & RTF_EXPIRES))
685 : : rt6_clean_expires(iter);
686 : : else
687 : 0 : rt6_set_expires(iter, rt->dst.expires);
688 : : return -EEXIST;
689 : : }
690 : : /* If we have the same destination and the same metric,
691 : : * but not the same gateway, then the route we try to
692 : : * add is sibling to this route, increment our counter
693 : : * of siblings, and later we will add our route to the
694 : : * list.
695 : : * Only static routes (which don't have flag
696 : : * RTF_EXPIRES) are used for ECMPv6.
697 : : *
698 : : * To avoid long list, we only had siblings if the
699 : : * route have a gateway.
700 : : */
701 [ # # ][ # # ]: 0 : if (rt_can_ecmp &&
702 : : rt6_qualify_for_ecmp(iter))
703 : 0 : rt->rt6i_nsiblings++;
704 : : }
705 : :
706 [ # # ]: 0 : if (iter->rt6i_metric > rt->rt6i_metric)
707 : : break;
708 : :
709 : 0 : ins = &iter->dst.rt6_next;
710 : : }
711 : :
712 : : /* Reset round-robin state, if necessary */
713 [ + - ]: 10 : if (ins == &fn->leaf)
714 : 5 : fn->rr_ptr = NULL;
715 : :
716 : : /* Link this route to others same route. */
717 [ - + ]: 5 : if (rt->rt6i_nsiblings) {
718 : : unsigned int rt6i_nsiblings;
719 : 0 : struct rt6_info *sibling, *temp_sibling;
720 : :
721 : : /* Find the first route that have the same metric */
722 : 0 : sibling = fn->leaf;
723 [ # # ]: 0 : while (sibling) {
724 [ # # ][ # # ]: 0 : if (sibling->rt6i_metric == rt->rt6i_metric &&
725 : : rt6_qualify_for_ecmp(sibling)) {
726 : 0 : list_add_tail(&rt->rt6i_siblings,
727 : : &sibling->rt6i_siblings);
728 : : break;
729 : : }
730 : 0 : sibling = sibling->dst.rt6_next;
731 : : }
732 : : /* For each sibling in the list, increment the counter of
733 : : * siblings. BUG() if counters does not match, list of siblings
734 : : * is broken!
735 : : */
736 : : rt6i_nsiblings = 0;
737 [ # # ]: 0 : list_for_each_entry_safe(sibling, temp_sibling,
738 : : &rt->rt6i_siblings, rt6i_siblings) {
739 : 0 : sibling->rt6i_nsiblings++;
740 [ # # ]: 0 : BUG_ON(sibling->rt6i_nsiblings != rt->rt6i_nsiblings);
741 : 0 : rt6i_nsiblings++;
742 : : }
743 [ # # ]: 0 : BUG_ON(rt6i_nsiblings != rt->rt6i_nsiblings);
744 : : }
745 : :
746 : : /*
747 : : * insert node
748 : : */
749 [ + - ]: 5 : if (!replace) {
750 [ - + ]: 5 : if (!add)
751 : 0 : pr_warn("NLM_F_CREATE should be set when creating new route\n");
752 : :
753 : : add:
754 : 5 : rt->dst.rt6_next = iter;
755 : 5 : *ins = rt;
756 : 5 : rt->rt6i_node = fn;
757 : 5 : atomic_inc(&rt->rt6i_ref);
758 : 5 : inet6_rt_notify(RTM_NEWROUTE, rt, info);
759 : 5 : info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
760 : :
761 [ + - ]: 5 : if (!(fn->fn_flags & RTN_RTINFO)) {
762 : 5 : info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
763 : 5 : fn->fn_flags |= RTN_RTINFO;
764 : : }
765 : :
766 : : } else {
767 [ # # ]: 0 : if (!found) {
768 [ # # ]: 0 : if (add)
769 : : goto add;
770 : 0 : pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
771 : 0 : return -ENOENT;
772 : : }
773 : 0 : *ins = rt;
774 : 0 : rt->rt6i_node = fn;
775 : 0 : rt->dst.rt6_next = iter->dst.rt6_next;
776 : 0 : atomic_inc(&rt->rt6i_ref);
777 : 0 : inet6_rt_notify(RTM_NEWROUTE, rt, info);
778 : : rt6_release(iter);
779 [ # # ]: 0 : if (!(fn->fn_flags & RTN_RTINFO)) {
780 : 0 : info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
781 : 0 : fn->fn_flags |= RTN_RTINFO;
782 : : }
783 : : }
784 : :
785 : : return 0;
786 : : }
787 : :
788 : : static __inline__ void fib6_start_gc(struct net *net, struct rt6_info *rt)
789 : : {
790 [ + - ][ + - ]: 5 : if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
791 : 5 : (rt->rt6i_flags & (RTF_EXPIRES | RTF_CACHE)))
792 : 5 : mod_timer(&net->ipv6.ip6_fib_timer,
793 : 5 : jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
794 : : }
795 : :
796 : 0 : void fib6_force_start_gc(struct net *net)
797 : : {
798 [ # # ]: 0 : if (!timer_pending(&net->ipv6.ip6_fib_timer))
799 : 0 : mod_timer(&net->ipv6.ip6_fib_timer,
800 : 0 : jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
801 : 0 : }
802 : :
803 : : /*
804 : : * Add routing information to the routing tree.
805 : : * <destination addr>/<source addr>
806 : : * with source addr info in sub-trees
807 : : */
808 : :
809 : 0 : int fib6_add(struct fib6_node *root, struct rt6_info *rt, struct nl_info *info)
810 : : {
811 : : struct fib6_node *fn, *pn = NULL;
812 : : int err = -ENOMEM;
813 : : int allow_create = 1;
814 : : int replace_required = 0;
815 : :
816 [ - + ]: 5 : if (info->nlh) {
817 [ # # ]: 0 : if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
818 : : allow_create = 0;
819 [ # # ]: 0 : if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
820 : : replace_required = 1;
821 : : }
822 [ - + ]: 5 : if (!allow_create && !replace_required)
823 : 0 : pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
824 : :
825 : 5 : fn = fib6_add_1(root, &rt->rt6i_dst.addr, rt->rt6i_dst.plen,
826 : : offsetof(struct rt6_info, rt6i_dst), allow_create,
827 : : replace_required);
828 [ - + ]: 5 : if (IS_ERR(fn)) {
829 : : err = PTR_ERR(fn);
830 : : fn = NULL;
831 : 0 : goto out;
832 : : }
833 : :
834 : : pn = fn;
835 : :
836 : : #ifdef CONFIG_IPV6_SUBTREES
837 : : if (rt->rt6i_src.plen) {
838 : : struct fib6_node *sn;
839 : :
840 : : if (!fn->subtree) {
841 : : struct fib6_node *sfn;
842 : :
843 : : /*
844 : : * Create subtree.
845 : : *
846 : : * fn[main tree]
847 : : * |
848 : : * sfn[subtree root]
849 : : * \
850 : : * sn[new leaf node]
851 : : */
852 : :
853 : : /* Create subtree root node */
854 : : sfn = node_alloc();
855 : : if (!sfn)
856 : : goto st_failure;
857 : :
858 : : sfn->leaf = info->nl_net->ipv6.ip6_null_entry;
859 : : atomic_inc(&info->nl_net->ipv6.ip6_null_entry->rt6i_ref);
860 : : sfn->fn_flags = RTN_ROOT;
861 : : sfn->fn_sernum = fib6_new_sernum();
862 : :
863 : : /* Now add the first leaf node to new subtree */
864 : :
865 : : sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
866 : : rt->rt6i_src.plen,
867 : : offsetof(struct rt6_info, rt6i_src),
868 : : allow_create, replace_required);
869 : :
870 : : if (IS_ERR(sn)) {
871 : : /* If it is failed, discard just allocated
872 : : root, and then (in st_failure) stale node
873 : : in main tree.
874 : : */
875 : : node_free(sfn);
876 : : err = PTR_ERR(sn);
877 : : goto st_failure;
878 : : }
879 : :
880 : : /* Now link new subtree to main tree */
881 : : sfn->parent = fn;
882 : : fn->subtree = sfn;
883 : : } else {
884 : : sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
885 : : rt->rt6i_src.plen,
886 : : offsetof(struct rt6_info, rt6i_src),
887 : : allow_create, replace_required);
888 : :
889 : : if (IS_ERR(sn)) {
890 : : err = PTR_ERR(sn);
891 : : goto st_failure;
892 : : }
893 : : }
894 : :
895 : : if (!fn->leaf) {
896 : : fn->leaf = rt;
897 : : atomic_inc(&rt->rt6i_ref);
898 : : }
899 : : fn = sn;
900 : : }
901 : : #endif
902 : :
903 : 5 : err = fib6_add_rt2node(fn, rt, info);
904 [ + - ]: 5 : if (!err) {
905 : 5 : fib6_start_gc(info->nl_net, rt);
906 [ - + ]: 5 : if (!(rt->rt6i_flags & RTF_CACHE))
907 : 0 : fib6_prune_clones(info->nl_net, pn, rt);
908 : : }
909 : :
910 : : out:
911 [ - + ]: 5 : if (err) {
912 : : #ifdef CONFIG_IPV6_SUBTREES
913 : : /*
914 : : * If fib6_add_1 has cleared the old leaf pointer in the
915 : : * super-tree leaf node we have to find a new one for it.
916 : : */
917 : : if (pn != fn && pn->leaf == rt) {
918 : : pn->leaf = NULL;
919 : : atomic_dec(&rt->rt6i_ref);
920 : : }
921 : : if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
922 : : pn->leaf = fib6_find_prefix(info->nl_net, pn);
923 : : #if RT6_DEBUG >= 2
924 : : if (!pn->leaf) {
925 : : WARN_ON(pn->leaf == NULL);
926 : : pn->leaf = info->nl_net->ipv6.ip6_null_entry;
927 : : }
928 : : #endif
929 : : atomic_inc(&pn->leaf->rt6i_ref);
930 : : }
931 : : #endif
932 : 0 : dst_free(&rt->dst);
933 : : }
934 : 5 : return err;
935 : :
936 : : #ifdef CONFIG_IPV6_SUBTREES
937 : : /* Subtree creation failed, probably main tree node
938 : : is orphan. If it is, shoot it.
939 : : */
940 : : st_failure:
941 : : if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
942 : : fib6_repair_tree(info->nl_net, fn);
943 : : dst_free(&rt->dst);
944 : : return err;
945 : : #endif
946 : : }
947 : :
948 : : /*
949 : : * Routing tree lookup
950 : : *
951 : : */
952 : :
953 : : struct lookup_args {
954 : : int offset; /* key offset on rt6_info */
955 : : const struct in6_addr *addr; /* search key */
956 : : };
957 : :
958 : 0 : static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
959 : : struct lookup_args *args)
960 : : {
961 : : struct fib6_node *fn;
962 : : __be32 dir;
963 : :
964 [ + ]: 5 : if (unlikely(args->offset == 0))
965 : : return NULL;
966 : :
967 : : /*
968 : : * Descend on a tree
969 : : */
970 : :
971 : : fn = root;
972 : :
973 : : for (;;) {
974 : : struct fib6_node *next;
975 : :
976 : 15 : dir = addr_bit_set(args->addr, fn->fn_bit);
977 : :
978 [ + + ]: 15 : next = dir ? fn->right : fn->left;
979 : :
980 [ + + ]: 15 : if (next) {
981 : : fn = next;
982 : 10 : continue;
983 : : }
984 : : break;
985 : 10 : }
986 : :
987 [ + - ]: 5 : while (fn) {
988 [ + - ]: 5 : if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
989 : : struct rt6key *key;
990 : :
991 : 5 : key = (struct rt6key *) ((u8 *) fn->leaf +
992 : : args->offset);
993 : :
994 [ + - ]: 5 : if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
995 : : #ifdef CONFIG_IPV6_SUBTREES
996 : : if (fn->subtree) {
997 : : struct fib6_node *sfn;
998 : : sfn = fib6_lookup_1(fn->subtree,
999 : : args + 1);
1000 : : if (!sfn)
1001 : : goto backtrack;
1002 : : fn = sfn;
1003 : : }
1004 : : #endif
1005 [ - + ]: 5 : if (fn->fn_flags & RTN_RTINFO)
1006 : : return fn;
1007 : : }
1008 : : }
1009 : : #ifdef CONFIG_IPV6_SUBTREES
1010 : : backtrack:
1011 : : #endif
1012 [ # # ]: 0 : if (fn->fn_flags & RTN_ROOT)
1013 : : break;
1014 : :
1015 : 0 : fn = fn->parent;
1016 : : }
1017 : :
1018 : : return NULL;
1019 : : }
1020 : :
1021 : 0 : struct fib6_node * fib6_lookup(struct fib6_node *root, const struct in6_addr *daddr,
1022 : : const struct in6_addr *saddr)
1023 : : {
1024 : : struct fib6_node *fn;
1025 : 5 : struct lookup_args args[] = {
1026 : : {
1027 : : .offset = offsetof(struct rt6_info, rt6i_dst),
1028 : : .addr = daddr,
1029 : : },
1030 : : #ifdef CONFIG_IPV6_SUBTREES
1031 : : {
1032 : : .offset = offsetof(struct rt6_info, rt6i_src),
1033 : : .addr = saddr,
1034 : : },
1035 : : #endif
1036 : : {
1037 : : .offset = 0, /* sentinel */
1038 : : }
1039 : : };
1040 : :
1041 [ - + ]: 5 : fn = fib6_lookup_1(root, daddr ? args : args + 1);
1042 [ + - ][ - + ]: 5 : if (!fn || fn->fn_flags & RTN_TL_ROOT)
1043 : : fn = root;
1044 : :
1045 : 5 : return fn;
1046 : : }
1047 : :
1048 : : /*
1049 : : * Get node with specified destination prefix (and source prefix,
1050 : : * if subtrees are used)
1051 : : */
1052 : :
1053 : :
1054 : 0 : static struct fib6_node * fib6_locate_1(struct fib6_node *root,
1055 : : const struct in6_addr *addr,
1056 : : int plen, int offset)
1057 : : {
1058 : : struct fib6_node *fn;
1059 : :
1060 [ # # ]: 0 : for (fn = root; fn ; ) {
1061 : 0 : struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
1062 : :
1063 : : /*
1064 : : * Prefix match
1065 : : */
1066 [ # # ][ # # ]: 0 : if (plen < fn->fn_bit ||
1067 : 0 : !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1068 : : return NULL;
1069 : :
1070 [ # # ]: 0 : if (plen == fn->fn_bit)
1071 : : return fn;
1072 : :
1073 : : /*
1074 : : * We have more bits to go
1075 : : */
1076 [ # # ]: 0 : if (addr_bit_set(addr, fn->fn_bit))
1077 : 0 : fn = fn->right;
1078 : : else
1079 : 0 : fn = fn->left;
1080 : : }
1081 : : return NULL;
1082 : : }
1083 : :
1084 : 0 : struct fib6_node * fib6_locate(struct fib6_node *root,
1085 : : const struct in6_addr *daddr, int dst_len,
1086 : : const struct in6_addr *saddr, int src_len)
1087 : : {
1088 : : struct fib6_node *fn;
1089 : :
1090 : 0 : fn = fib6_locate_1(root, daddr, dst_len,
1091 : : offsetof(struct rt6_info, rt6i_dst));
1092 : :
1093 : : #ifdef CONFIG_IPV6_SUBTREES
1094 : : if (src_len) {
1095 : : WARN_ON(saddr == NULL);
1096 : : if (fn && fn->subtree)
1097 : : fn = fib6_locate_1(fn->subtree, saddr, src_len,
1098 : : offsetof(struct rt6_info, rt6i_src));
1099 : : }
1100 : : #endif
1101 : :
1102 [ # # ][ # # ]: 0 : if (fn && fn->fn_flags & RTN_RTINFO)
1103 : 0 : return fn;
1104 : :
1105 : : return NULL;
1106 : : }
1107 : :
1108 : :
1109 : : /*
1110 : : * Deletion
1111 : : *
1112 : : */
1113 : :
1114 : : static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn)
1115 : : {
1116 [ # # ][ # # ]: 0 : if (fn->fn_flags & RTN_ROOT)
1117 : 0 : return net->ipv6.ip6_null_entry;
1118 : :
1119 [ # # ][ # # ]: 0 : while (fn) {
1120 [ # # ][ # # ]: 0 : if (fn->left)
1121 : 0 : return fn->left->leaf;
1122 [ # # ][ # # ]: 0 : if (fn->right)
1123 : 0 : return fn->right->leaf;
1124 : :
1125 : : fn = FIB6_SUBTREE(fn);
1126 : : }
1127 : : return NULL;
1128 : : }
1129 : :
1130 : : /*
1131 : : * Called to trim the tree of intermediate nodes when possible. "fn"
1132 : : * is the node we want to try and remove.
1133 : : */
1134 : :
1135 : 5 : static struct fib6_node *fib6_repair_tree(struct net *net,
1136 : : struct fib6_node *fn)
1137 : : {
1138 : : int children;
1139 : : int nstate;
1140 : : struct fib6_node *child, *pn;
1141 : : struct fib6_walker_t *w;
1142 : : int iter = 0;
1143 : :
1144 : : for (;;) {
1145 : : RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1146 : : iter++;
1147 : :
1148 [ - + ]: 5 : WARN_ON(fn->fn_flags & RTN_RTINFO);
1149 [ - + ]: 10 : WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1150 [ - + ]: 5 : WARN_ON(fn->leaf != NULL);
1151 : :
1152 : : children = 0;
1153 : : child = NULL;
1154 [ - + ]: 5 : if (fn->right) child = fn->right, children |= 1;
1155 [ - + ]: 5 : if (fn->left) child = fn->left, children |= 2;
1156 : :
1157 [ - + ]: 5 : if (children == 3 || FIB6_SUBTREE(fn)
1158 : : #ifdef CONFIG_IPV6_SUBTREES
1159 : : /* Subtree root (i.e. fn) may have one child */
1160 : : || (children && fn->fn_flags & RTN_ROOT)
1161 : : #endif
1162 : : ) {
1163 : 0 : fn->leaf = fib6_find_prefix(net, fn);
1164 : : #if RT6_DEBUG >= 2
1165 [ # # ]: 0 : if (!fn->leaf) {
1166 [ # # ]: 0 : WARN_ON(!fn->leaf);
1167 : 0 : fn->leaf = net->ipv6.ip6_null_entry;
1168 : : }
1169 : : #endif
1170 : 0 : atomic_inc(&fn->leaf->rt6i_ref);
1171 : 0 : return fn->parent;
1172 : : }
1173 : :
1174 : 5 : pn = fn->parent;
1175 : : #ifdef CONFIG_IPV6_SUBTREES
1176 : : if (FIB6_SUBTREE(pn) == fn) {
1177 : : WARN_ON(!(fn->fn_flags & RTN_ROOT));
1178 : : FIB6_SUBTREE(pn) = NULL;
1179 : : nstate = FWS_L;
1180 : : } else {
1181 : : WARN_ON(fn->fn_flags & RTN_ROOT);
1182 : : #endif
1183 [ - + ]: 5 : if (pn->right == fn) pn->right = child;
1184 [ + - ]: 5 : else if (pn->left == fn) pn->left = child;
1185 : : #if RT6_DEBUG >= 2
1186 : : else
1187 : 0 : WARN_ON(1);
1188 : : #endif
1189 [ - + ]: 5 : if (child)
1190 : 0 : child->parent = pn;
1191 : : nstate = FWS_R;
1192 : : #ifdef CONFIG_IPV6_SUBTREES
1193 : : }
1194 : : #endif
1195 : :
1196 : 5 : read_lock(&fib6_walker_lock);
1197 [ + + ]: 10 : FOR_WALKERS(w) {
1198 [ + - ]: 5 : if (!child) {
1199 [ - + ]: 5 : if (w->root == fn) {
1200 : 0 : w->root = w->node = NULL;
1201 : : RT6_TRACE("W %p adjusted by delroot 1\n", w);
1202 [ + - ]: 5 : } else if (w->node == fn) {
1203 : : RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1204 : 5 : w->node = pn;
1205 : 5 : w->state = nstate;
1206 : : }
1207 : : } else {
1208 [ # # ]: 0 : if (w->root == fn) {
1209 : 0 : w->root = child;
1210 : : RT6_TRACE("W %p adjusted by delroot 2\n", w);
1211 : : }
1212 [ # # ]: 0 : if (w->node == fn) {
1213 : 0 : w->node = child;
1214 [ # # ]: 0 : if (children&2) {
1215 : : RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1216 [ # # ]: 0 : w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
1217 : : } else {
1218 : : RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1219 [ # # ]: 0 : w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
1220 : : }
1221 : : }
1222 : : }
1223 : : }
1224 : : read_unlock(&fib6_walker_lock);
1225 : :
1226 : : node_free(fn);
1227 [ - + ]: 5 : if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
1228 : : return pn;
1229 : :
1230 : 0 : rt6_release(pn->leaf);
1231 : 0 : pn->leaf = NULL;
1232 : : fn = pn;
1233 : 0 : }
1234 : : }
1235 : :
1236 : 0 : static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
1237 : : struct nl_info *info)
1238 : : {
1239 : : struct fib6_walker_t *w;
1240 : 5 : struct rt6_info *rt = *rtp;
1241 : 5 : struct net *net = info->nl_net;
1242 : :
1243 : : RT6_TRACE("fib6_del_route\n");
1244 : :
1245 : : /* Unlink it */
1246 : 5 : *rtp = rt->dst.rt6_next;
1247 : 5 : rt->rt6i_node = NULL;
1248 : 5 : net->ipv6.rt6_stats->fib_rt_entries--;
1249 : 5 : net->ipv6.rt6_stats->fib_discarded_routes++;
1250 : :
1251 : : /* Reset round-robin state, if necessary */
1252 [ - + ]: 5 : if (fn->rr_ptr == rt)
1253 : 0 : fn->rr_ptr = NULL;
1254 : :
1255 : : /* Remove this entry from other siblings */
1256 [ - + ]: 5 : if (rt->rt6i_nsiblings) {
1257 : : struct rt6_info *sibling, *next_sibling;
1258 : :
1259 [ # # ]: 0 : list_for_each_entry_safe(sibling, next_sibling,
1260 : : &rt->rt6i_siblings, rt6i_siblings)
1261 : 0 : sibling->rt6i_nsiblings--;
1262 : 0 : rt->rt6i_nsiblings = 0;
1263 : 0 : list_del_init(&rt->rt6i_siblings);
1264 : : }
1265 : :
1266 : : /* Adjust walkers */
1267 : 5 : read_lock(&fib6_walker_lock);
1268 [ + + ]: 10 : FOR_WALKERS(w) {
1269 [ + - ][ + - ]: 5 : if (w->state == FWS_C && w->leaf == rt) {
1270 : : RT6_TRACE("walker %p adjusted by delroute\n", w);
1271 : 5 : w->leaf = rt->dst.rt6_next;
1272 [ + - ]: 5 : if (!w->leaf)
1273 : 5 : w->state = FWS_U;
1274 : : }
1275 : : }
1276 : : read_unlock(&fib6_walker_lock);
1277 : :
1278 : 5 : rt->dst.rt6_next = NULL;
1279 : :
1280 : : /* If it was last route, expunge its radix tree node */
1281 [ + - ]: 5 : if (!fn->leaf) {
1282 : 5 : fn->fn_flags &= ~RTN_RTINFO;
1283 : 5 : net->ipv6.rt6_stats->fib_route_nodes--;
1284 : 5 : fn = fib6_repair_tree(net, fn);
1285 : : }
1286 : :
1287 [ - + ]: 5 : if (atomic_read(&rt->rt6i_ref) != 1) {
1288 : : /* This route is used as dummy address holder in some split
1289 : : * nodes. It is not leaked, but it still holds other resources,
1290 : : * which must be released in time. So, scan ascendant nodes
1291 : : * and replace dummy references to this route with references
1292 : : * to still alive ones.
1293 : : */
1294 [ # # ]: 0 : while (fn) {
1295 [ # # ][ # # ]: 0 : if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) {
1296 : 0 : fn->leaf = fib6_find_prefix(net, fn);
1297 : 0 : atomic_inc(&fn->leaf->rt6i_ref);
1298 : : rt6_release(rt);
1299 : : }
1300 : 0 : fn = fn->parent;
1301 : : }
1302 : : /* No more references are possible at this point. */
1303 [ # # ]: 0 : BUG_ON(atomic_read(&rt->rt6i_ref) != 1);
1304 : : }
1305 : :
1306 : 5 : inet6_rt_notify(RTM_DELROUTE, rt, info);
1307 : : rt6_release(rt);
1308 : 5 : }
1309 : :
1310 : 0 : int fib6_del(struct rt6_info *rt, struct nl_info *info)
1311 : : {
1312 : 5 : struct net *net = info->nl_net;
1313 : 5 : struct fib6_node *fn = rt->rt6i_node;
1314 : : struct rt6_info **rtp;
1315 : :
1316 : : #if RT6_DEBUG >= 2
1317 [ - + ]: 5 : if (rt->dst.obsolete>0) {
1318 [ # # ]: 0 : WARN_ON(fn != NULL);
1319 : : return -ENOENT;
1320 : : }
1321 : : #endif
1322 [ + - ][ + - ]: 5 : if (!fn || rt == net->ipv6.ip6_null_entry)
1323 : : return -ENOENT;
1324 : :
1325 [ - + ]: 5 : WARN_ON(!(fn->fn_flags & RTN_RTINFO));
1326 : :
1327 [ - + ]: 5 : if (!(rt->rt6i_flags & RTF_CACHE)) {
1328 : : struct fib6_node *pn = fn;
1329 : : #ifdef CONFIG_IPV6_SUBTREES
1330 : : /* clones of this route might be in another subtree */
1331 : : if (rt->rt6i_src.plen) {
1332 : : while (!(pn->fn_flags & RTN_ROOT))
1333 : : pn = pn->parent;
1334 : : pn = pn->parent;
1335 : : }
1336 : : #endif
1337 : 0 : fib6_prune_clones(info->nl_net, pn, rt);
1338 : : }
1339 : :
1340 : : /*
1341 : : * Walk the leaf entries looking for ourself
1342 : : */
1343 : :
1344 [ + - ]: 5 : for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) {
1345 [ + - ]: 5 : if (*rtp == rt) {
1346 : 5 : fib6_del_route(fn, rtp, info);
1347 : 5 : return 0;
1348 : : }
1349 : : }
1350 : : return -ENOENT;
1351 : : }
1352 : :
1353 : : /*
1354 : : * Tree traversal function.
1355 : : *
1356 : : * Certainly, it is not interrupt safe.
1357 : : * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1358 : : * It means, that we can modify tree during walking
1359 : : * and use this function for garbage collection, clone pruning,
1360 : : * cleaning tree when a device goes down etc. etc.
1361 : : *
1362 : : * It guarantees that every node will be traversed,
1363 : : * and that it will be traversed only once.
1364 : : *
1365 : : * Callback function w->func may return:
1366 : : * 0 -> continue walking.
1367 : : * positive value -> walking is suspended (used by tree dumps,
1368 : : * and probably by gc, if it will be split to several slices)
1369 : : * negative value -> terminate walking.
1370 : : *
1371 : : * The function itself returns:
1372 : : * 0 -> walk is complete.
1373 : : * >0 -> walk is incomplete (i.e. suspended)
1374 : : * <0 -> walk is terminated by an error.
1375 : : */
1376 : :
1377 : 101 : static int fib6_walk_continue(struct fib6_walker_t *w)
1378 : : {
1379 : : struct fib6_node *fn, *pn;
1380 : :
1381 : : for (;;) {
1382 : 101 : fn = w->node;
1383 [ + - ]: 101 : if (!fn)
1384 : : return 0;
1385 : :
1386 [ - + ][ # # ]: 101 : if (w->prune && fn != w->root &&
[ # # ]
1387 [ # # ]: 0 : fn->fn_flags & RTN_RTINFO && w->state < FWS_C) {
1388 : 0 : w->state = FWS_C;
1389 : 0 : w->leaf = fn->leaf;
1390 : : }
1391 [ - + + + : 101 : switch (w->state) {
- ]
1392 : : #ifdef CONFIG_IPV6_SUBTREES
1393 : : case FWS_S:
1394 : : if (FIB6_SUBTREE(fn)) {
1395 : : w->node = FIB6_SUBTREE(fn);
1396 : : continue;
1397 : : }
1398 : : w->state = FWS_L;
1399 : : #endif
1400 : : case FWS_L:
1401 [ + + ]: 40 : if (fn->left) {
1402 : 19 : w->node = fn->left;
1403 : 19 : w->state = FWS_INIT;
1404 : 19 : continue;
1405 : : }
1406 : 21 : w->state = FWS_R;
1407 : : case FWS_R:
1408 [ + + ]: 40 : if (fn->right) {
1409 : 14 : w->node = fn->right;
1410 : 14 : w->state = FWS_INIT;
1411 : 14 : continue;
1412 : : }
1413 : 26 : w->state = FWS_C;
1414 : 26 : w->leaf = fn->leaf;
1415 : : case FWS_C:
1416 [ + + ][ + + ]: 68 : if (w->leaf && fn->fn_flags & RTN_RTINFO) {
1417 : : int err;
1418 : :
1419 [ - + ]: 33 : if (w->skip) {
1420 : 0 : w->skip--;
1421 : 0 : continue;
1422 : : }
1423 : :
1424 : 33 : err = w->func(w);
1425 [ + + ]: 33 : if (err)
1426 : : return err;
1427 : :
1428 : 29 : w->count++;
1429 : 29 : continue;
1430 : : }
1431 : 35 : w->state = FWS_U;
1432 : : case FWS_U:
1433 [ + ]: 35 : if (fn == w->root)
1434 : : return 0;
1435 : 28 : pn = fn->parent;
1436 : 28 : w->node = pn;
1437 : : #ifdef CONFIG_IPV6_SUBTREES
1438 : : if (FIB6_SUBTREE(pn) == fn) {
1439 : : WARN_ON(!(fn->fn_flags & RTN_ROOT));
1440 : : w->state = FWS_L;
1441 : : continue;
1442 : : }
1443 : : #endif
1444 [ + + ]: 28 : if (pn->left == fn) {
1445 : 14 : w->state = FWS_R;
1446 : 14 : continue;
1447 : : }
1448 [ + - ]: 14 : if (pn->right == fn) {
1449 : 14 : w->state = FWS_C;
1450 : 14 : w->leaf = w->node->leaf;
1451 : 14 : continue;
1452 : : }
1453 : : #if RT6_DEBUG >= 2
1454 : 0 : WARN_ON(1);
1455 : : #endif
1456 : : }
1457 : : }
1458 : : }
1459 : :
1460 : 0 : static int fib6_walk(struct fib6_walker_t *w)
1461 : : {
1462 : : int res;
1463 : :
1464 : 5 : w->state = FWS_INIT;
1465 : 5 : w->node = w->root;
1466 : :
1467 : : fib6_walker_link(w);
1468 : 5 : res = fib6_walk_continue(w);
1469 [ + - ]: 5 : if (res <= 0)
1470 : : fib6_walker_unlink(w);
1471 : 0 : return res;
1472 : : }
1473 : :
1474 : 0 : static int fib6_clean_node(struct fib6_walker_t *w)
1475 : : {
1476 : : int res;
1477 : : struct rt6_info *rt;
1478 : : struct fib6_cleaner_t *c = container_of(w, struct fib6_cleaner_t, w);
1479 : 50 : struct nl_info info = {
1480 : 25 : .nl_net = c->net,
1481 : : };
1482 : :
1483 [ + + ]: 45 : for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
1484 : 25 : res = c->func(rt, c->arg);
1485 [ + + ]: 25 : if (res < 0) {
1486 : 5 : w->leaf = rt;
1487 : 5 : res = fib6_del(rt, &info);
1488 [ - + ]: 5 : if (res) {
1489 : : #if RT6_DEBUG >= 2
1490 : : pr_debug("%s: del failed: rt=%p@%p err=%d\n",
1491 : : __func__, rt, rt->rt6i_node, res);
1492 : : #endif
1493 : 0 : continue;
1494 : : }
1495 : : return 0;
1496 : : }
1497 [ - + ]: 20 : WARN_ON(res != 0);
1498 : : }
1499 : 20 : w->leaf = rt;
1500 : 20 : return 0;
1501 : : }
1502 : :
1503 : : /*
1504 : : * Convenient frontend to tree walker.
1505 : : *
1506 : : * func is called on each route.
1507 : : * It may return -1 -> delete this route.
1508 : : * 0 -> continue walking
1509 : : *
1510 : : * prune==1 -> only immediate children of node (certainly,
1511 : : * ignoring pure split nodes) will be scanned.
1512 : : */
1513 : :
1514 : : static void fib6_clean_tree(struct net *net, struct fib6_node *root,
1515 : : int (*func)(struct rt6_info *, void *arg),
1516 : : int prune, void *arg)
1517 : : {
1518 : : struct fib6_cleaner_t c;
1519 : :
1520 : 5 : c.w.root = root;
1521 : 5 : c.w.func = fib6_clean_node;
1522 : 5 : c.w.prune = prune;
1523 : 5 : c.w.count = 0;
1524 : 5 : c.w.skip = 0;
1525 : 5 : c.func = func;
1526 : 5 : c.arg = arg;
1527 : 5 : c.net = net;
1528 : :
1529 : 5 : fib6_walk(&c.w);
1530 : : }
1531 : :
1532 : 0 : void fib6_clean_all(struct net *net, int (*func)(struct rt6_info *, void *arg),
1533 : : void *arg)
1534 : : {
1535 : : struct fib6_table *table;
1536 : : struct hlist_head *head;
1537 : : unsigned int h;
1538 : :
1539 : : rcu_read_lock();
1540 [ + + ]: 10 : for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
1541 : 5 : head = &net->ipv6.fib_table_hash[h];
1542 [ + - ][ - + ]: 15 : hlist_for_each_entry_rcu(table, head, tb6_hlist) {
[ + + ]
1543 : 5 : write_lock_bh(&table->tb6_lock);
1544 : 5 : fib6_clean_tree(net, &table->tb6_root,
1545 : : func, 0, arg);
1546 : 5 : write_unlock_bh(&table->tb6_lock);
1547 : : }
1548 : : }
1549 : : rcu_read_unlock();
1550 : 5 : }
1551 : :
1552 : 0 : static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1553 : : {
1554 [ # # ]: 0 : if (rt->rt6i_flags & RTF_CACHE) {
1555 : : RT6_TRACE("pruning clone %p\n", rt);
1556 : : return -1;
1557 : : }
1558 : :
1559 : 0 : return 0;
1560 : : }
1561 : :
1562 : 0 : static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
1563 : : struct rt6_info *rt)
1564 : : {
1565 : : fib6_clean_tree(net, fn, fib6_prune_clone, 1, rt);
1566 : 0 : }
1567 : :
1568 : : /*
1569 : : * Garbage collection
1570 : : */
1571 : :
1572 : : static struct fib6_gc_args
1573 : : {
1574 : : int timeout;
1575 : : int more;
1576 : : } gc_args;
1577 : :
1578 : 0 : static int fib6_age(struct rt6_info *rt, void *arg)
1579 : : {
1580 : 25 : unsigned long now = jiffies;
1581 : :
1582 : : /*
1583 : : * check addrconf expiration here.
1584 : : * Routes are expired even if they are in use.
1585 : : *
1586 : : * Also age clones. Note, that clones are aged out
1587 : : * only if they are not in use now.
1588 : : */
1589 : :
1590 [ - + ][ # # ]: 25 : if (rt->rt6i_flags & RTF_EXPIRES && rt->dst.expires) {
1591 [ # # ]: 0 : if (time_after(now, rt->dst.expires)) {
1592 : : RT6_TRACE("expiring %p\n", rt);
1593 : : return -1;
1594 : : }
1595 : 0 : gc_args.more++;
1596 [ + + ]: 25 : } else if (rt->rt6i_flags & RTF_CACHE) {
1597 [ + - ]: 5 : if (atomic_read(&rt->dst.__refcnt) == 0 &&
1598 [ - + ]: 5 : time_after_eq(now, rt->dst.lastuse + gc_args.timeout)) {
1599 : : RT6_TRACE("aging clone %p\n", rt);
1600 : : return -1;
1601 [ # # ]: 0 : } else if (rt->rt6i_flags & RTF_GATEWAY) {
1602 : : struct neighbour *neigh;
1603 : : __u8 neigh_flags = 0;
1604 : :
1605 : 0 : neigh = dst_neigh_lookup(&rt->dst, &rt->rt6i_gateway);
1606 [ # # ]: 0 : if (neigh) {
1607 : 0 : neigh_flags = neigh->flags;
1608 : : neigh_release(neigh);
1609 : : }
1610 [ # # ]: 0 : if (!(neigh_flags & NTF_ROUTER)) {
1611 : : RT6_TRACE("purging route %p via non-router but gateway\n",
1612 : : rt);
1613 : : return -1;
1614 : : }
1615 : : }
1616 : 0 : gc_args.more++;
1617 : : }
1618 : :
1619 : : return 0;
1620 : : }
1621 : :
1622 : : static DEFINE_SPINLOCK(fib6_gc_lock);
1623 : :
1624 : 0 : void fib6_run_gc(unsigned long expires, struct net *net, bool force)
1625 : : {
1626 : : unsigned long now;
1627 : :
1628 [ + - ]: 5 : if (force) {
1629 : : spin_lock_bh(&fib6_gc_lock);
1630 [ # # ]: 0 : } else if (!spin_trylock_bh(&fib6_gc_lock)) {
1631 : 0 : mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
1632 : 0 : return;
1633 : : }
1634 [ - + ]: 10 : gc_args.timeout = expires ? (int)expires :
1635 : : net->ipv6.sysctl.ip6_rt_gc_interval;
1636 : :
1637 : 5 : gc_args.more = icmp6_dst_gc();
1638 : :
1639 : 5 : fib6_clean_all(net, fib6_age, NULL);
1640 : 5 : now = jiffies;
1641 : 5 : net->ipv6.ip6_rt_last_gc = now;
1642 : :
1643 [ - + ]: 5 : if (gc_args.more)
1644 : 0 : mod_timer(&net->ipv6.ip6_fib_timer,
1645 : : round_jiffies(now
1646 : 0 : + net->ipv6.sysctl.ip6_rt_gc_interval));
1647 : : else
1648 : 5 : del_timer(&net->ipv6.ip6_fib_timer);
1649 : : spin_unlock_bh(&fib6_gc_lock);
1650 : : }
1651 : :
1652 : 0 : static void fib6_gc_timer_cb(unsigned long arg)
1653 : : {
1654 : 5 : fib6_run_gc(0, (struct net *)arg, true);
1655 : 5 : }
1656 : :
1657 : 0 : static int __net_init fib6_net_init(struct net *net)
1658 : : {
1659 : : size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
1660 : :
1661 : 0 : setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (unsigned long)net);
1662 : :
1663 : 0 : net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
1664 [ # # ]: 0 : if (!net->ipv6.rt6_stats)
1665 : : goto out_timer;
1666 : :
1667 : : /* Avoid false sharing : Use at least a full cache line */
1668 : : size = max_t(size_t, size, L1_CACHE_BYTES);
1669 : :
1670 : 0 : net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
1671 [ # # ]: 0 : if (!net->ipv6.fib_table_hash)
1672 : : goto out_rt6_stats;
1673 : :
1674 : 0 : net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
1675 : : GFP_KERNEL);
1676 [ # # ]: 0 : if (!net->ipv6.fib6_main_tbl)
1677 : : goto out_fib_table_hash;
1678 : :
1679 : 0 : net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
1680 : 0 : net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1681 : 0 : net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
1682 : : RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1683 : 0 : inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
1684 : :
1685 : : #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1686 : : net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
1687 : : GFP_KERNEL);
1688 : : if (!net->ipv6.fib6_local_tbl)
1689 : : goto out_fib6_main_tbl;
1690 : : net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
1691 : : net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1692 : : net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
1693 : : RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1694 : : inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
1695 : : #endif
1696 : 0 : fib6_tables_init(net);
1697 : :
1698 : 0 : return 0;
1699 : :
1700 : : #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1701 : : out_fib6_main_tbl:
1702 : : kfree(net->ipv6.fib6_main_tbl);
1703 : : #endif
1704 : : out_fib_table_hash:
1705 : 0 : kfree(net->ipv6.fib_table_hash);
1706 : : out_rt6_stats:
1707 : 0 : kfree(net->ipv6.rt6_stats);
1708 : : out_timer:
1709 : : return -ENOMEM;
1710 : : }
1711 : :
1712 : 0 : static void fib6_net_exit(struct net *net)
1713 : : {
1714 : 0 : rt6_ifdown(net, NULL);
1715 : 0 : del_timer_sync(&net->ipv6.ip6_fib_timer);
1716 : :
1717 : : #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1718 : : inetpeer_invalidate_tree(&net->ipv6.fib6_local_tbl->tb6_peers);
1719 : : kfree(net->ipv6.fib6_local_tbl);
1720 : : #endif
1721 : 0 : inetpeer_invalidate_tree(&net->ipv6.fib6_main_tbl->tb6_peers);
1722 : 0 : kfree(net->ipv6.fib6_main_tbl);
1723 : 0 : kfree(net->ipv6.fib_table_hash);
1724 : 0 : kfree(net->ipv6.rt6_stats);
1725 : 0 : }
1726 : :
1727 : : static struct pernet_operations fib6_net_ops = {
1728 : : .init = fib6_net_init,
1729 : : .exit = fib6_net_exit,
1730 : : };
1731 : :
1732 : 0 : int __init fib6_init(void)
1733 : : {
1734 : : int ret = -ENOMEM;
1735 : :
1736 : 0 : fib6_node_kmem = kmem_cache_create("fib6_nodes",
1737 : : sizeof(struct fib6_node),
1738 : : 0, SLAB_HWCACHE_ALIGN,
1739 : : NULL);
1740 [ # # ]: 0 : if (!fib6_node_kmem)
1741 : : goto out;
1742 : :
1743 : 0 : ret = register_pernet_subsys(&fib6_net_ops);
1744 [ # # ]: 0 : if (ret)
1745 : : goto out_kmem_cache_create;
1746 : :
1747 : 0 : ret = __rtnl_register(PF_INET6, RTM_GETROUTE, NULL, inet6_dump_fib,
1748 : : NULL);
1749 [ # # ]: 0 : if (ret)
1750 : : goto out_unregister_subsys;
1751 : : out:
1752 : 0 : return ret;
1753 : :
1754 : : out_unregister_subsys:
1755 : 0 : unregister_pernet_subsys(&fib6_net_ops);
1756 : : out_kmem_cache_create:
1757 : 0 : kmem_cache_destroy(fib6_node_kmem);
1758 : 0 : goto out;
1759 : : }
1760 : :
1761 : 0 : void fib6_gc_cleanup(void)
1762 : : {
1763 : 0 : unregister_pernet_subsys(&fib6_net_ops);
1764 : 0 : kmem_cache_destroy(fib6_node_kmem);
1765 : 0 : }
1766 : :
1767 : : #ifdef CONFIG_PROC_FS
1768 : :
1769 : : struct ipv6_route_iter {
1770 : : struct seq_net_private p;
1771 : : struct fib6_walker_t w;
1772 : : loff_t skip;
1773 : : struct fib6_table *tbl;
1774 : : __u32 sernum;
1775 : : };
1776 : :
1777 : 0 : static int ipv6_route_seq_show(struct seq_file *seq, void *v)
1778 : : {
1779 : : struct rt6_info *rt = v;
1780 : 4 : struct ipv6_route_iter *iter = seq->private;
1781 : :
1782 : 4 : seq_printf(seq, "%pi6 %02x ", &rt->rt6i_dst.addr, rt->rt6i_dst.plen);
1783 : :
1784 : : #ifdef CONFIG_IPV6_SUBTREES
1785 : : seq_printf(seq, "%pi6 %02x ", &rt->rt6i_src.addr, rt->rt6i_src.plen);
1786 : : #else
1787 : 4 : seq_puts(seq, "00000000000000000000000000000000 00 ");
1788 : : #endif
1789 [ - + ]: 4 : if (rt->rt6i_flags & RTF_GATEWAY)
1790 : 0 : seq_printf(seq, "%pi6", &rt->rt6i_gateway);
1791 : : else
1792 : 4 : seq_puts(seq, "00000000000000000000000000000000");
1793 : :
1794 [ + - ]: 8 : seq_printf(seq, " %08x %08x %08x %08x %8s\n",
1795 : : rt->rt6i_metric, atomic_read(&rt->dst.__refcnt),
1796 : : rt->dst.__use, rt->rt6i_flags,
1797 : 4 : rt->dst.dev ? rt->dst.dev->name : "");
1798 : 4 : iter->w.leaf = NULL;
1799 : 4 : return 0;
1800 : : }
1801 : :
1802 : 0 : static int ipv6_route_yield(struct fib6_walker_t *w)
1803 : : {
1804 : 8 : struct ipv6_route_iter *iter = w->args;
1805 : :
1806 [ + + ]: 8 : if (!iter->skip)
1807 : : return 1;
1808 : :
1809 : : do {
1810 : 4 : iter->w.leaf = iter->w.leaf->dst.rt6_next;
1811 : 4 : iter->skip--;
1812 [ + + ][ + ]: 4 : if (!iter->skip && iter->w.leaf)
1813 : : return 1;
1814 [ - + ]: 12 : } while (iter->w.leaf);
1815 : :
1816 : : return 0;
1817 : : }
1818 : :
1819 : 0 : static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter)
1820 : : {
1821 : 2 : memset(&iter->w, 0, sizeof(iter->w));
1822 : 2 : iter->w.func = ipv6_route_yield;
1823 : 2 : iter->w.root = &iter->tbl->tb6_root;
1824 : 2 : iter->w.state = FWS_INIT;
1825 : 2 : iter->w.node = iter->w.root;
1826 : 2 : iter->w.args = iter;
1827 : 2 : iter->sernum = iter->w.root->fn_sernum;
1828 : 2 : INIT_LIST_HEAD(&iter->w.lh);
1829 : : fib6_walker_link(&iter->w);
1830 : 2 : }
1831 : :
1832 : : static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
1833 : : struct net *net)
1834 : : {
1835 : : unsigned int h;
1836 : : struct hlist_node *node;
1837 : :
1838 [ + - ]: 2 : if (tbl) {
1839 : : h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
1840 : 2 : node = rcu_dereference_bh(hlist_next_rcu(&tbl->tb6_hlist));
1841 : : } else {
1842 : : h = 0;
1843 : : node = NULL;
1844 : : }
1845 : :
1846 [ + + ][ - + ]: 6 : while (!node && h < FIB6_TABLE_HASHSZ) {
1847 : 2 : node = rcu_dereference_bh(
1848 : : hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
1849 : : }
1850 [ + - ][ - + ]: 4 : return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
1851 : : }
1852 : :
1853 : 0 : static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
1854 : : {
1855 [ - + ]: 6 : if (iter->sernum != iter->w.root->fn_sernum) {
1856 : 0 : iter->sernum = iter->w.root->fn_sernum;
1857 : 0 : iter->w.state = FWS_INIT;
1858 : 0 : iter->w.node = iter->w.root;
1859 [ # # ]: 0 : WARN_ON(iter->w.skip);
1860 : 0 : iter->w.skip = iter->w.count;
1861 : : }
1862 : 0 : }
1863 : :
1864 : 0 : static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
1865 : : {
1866 : : int r;
1867 : : struct rt6_info *n;
1868 : : struct net *net = seq_file_net(seq);
1869 : 6 : struct ipv6_route_iter *iter = seq->private;
1870 : :
1871 [ + + ]: 6 : if (!v)
1872 : : goto iter_table;
1873 : :
1874 : 4 : n = ((struct rt6_info *)v)->dst.rt6_next;
1875 [ + - ]: 6 : if (n) {
1876 : 0 : ++*pos;
1877 : 0 : return n;
1878 : : }
1879 : :
1880 : : iter_table:
1881 : 6 : ipv6_route_check_sernum(iter);
1882 : 6 : read_lock(&iter->tbl->tb6_lock);
1883 : 6 : r = fib6_walk_continue(&iter->w);
1884 : 6 : read_unlock(&iter->tbl->tb6_lock);
1885 [ + + ]: 6 : if (r > 0) {
1886 [ + + ]: 4 : if (v)
1887 : 3 : ++*pos;
1888 : 4 : return iter->w.leaf;
1889 [ - + ]: 2 : } else if (r < 0) {
1890 : : fib6_walker_unlink(&iter->w);
1891 : 0 : return NULL;
1892 : : }
1893 : : fib6_walker_unlink(&iter->w);
1894 : :
1895 : 4 : iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
1896 [ - + ]: 2 : if (!iter->tbl)
1897 : : return NULL;
1898 : :
1899 : 0 : ipv6_route_seq_setup_walk(iter);
1900 : 0 : goto iter_table;
1901 : : }
1902 : :
1903 : 0 : static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
1904 : : __acquires(RCU_BH)
1905 : : {
1906 : : struct net *net = seq_file_net(seq);
1907 : 2 : struct ipv6_route_iter *iter = seq->private;
1908 : :
1909 : : rcu_read_lock_bh();
1910 : 2 : iter->tbl = ipv6_route_seq_next_table(NULL, net);
1911 : 2 : iter->skip = *pos;
1912 : :
1913 [ + - ]: 2 : if (iter->tbl) {
1914 : 2 : ipv6_route_seq_setup_walk(iter);
1915 : 2 : return ipv6_route_seq_next(seq, NULL, pos);
1916 : : } else {
1917 : : return NULL;
1918 : : }
1919 : : }
1920 : :
1921 : : static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
1922 : : {
1923 : : struct fib6_walker_t *w = &iter->w;
1924 [ + - ][ + - ]: 2 : return w->node && !(w->state == FWS_U && w->node == w->root);
[ + - ]
1925 : : }
1926 : :
1927 : 0 : static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
1928 : : __releases(RCU_BH)
1929 : : {
1930 : 2 : struct ipv6_route_iter *iter = seq->private;
1931 : :
1932 [ # # ]: 2 : if (ipv6_route_iter_active(iter))
1933 : : fib6_walker_unlink(&iter->w);
1934 : :
1935 : : rcu_read_unlock_bh();
1936 : 2 : }
1937 : :
1938 : : static const struct seq_operations ipv6_route_seq_ops = {
1939 : : .start = ipv6_route_seq_start,
1940 : : .next = ipv6_route_seq_next,
1941 : : .stop = ipv6_route_seq_stop,
1942 : : .show = ipv6_route_seq_show
1943 : : };
1944 : :
1945 : 0 : int ipv6_route_open(struct inode *inode, struct file *file)
1946 : : {
1947 : 1 : return seq_open_net(inode, file, &ipv6_route_seq_ops,
1948 : : sizeof(struct ipv6_route_iter));
1949 : : }
1950 : :
1951 : : #endif /* CONFIG_PROC_FS */
|
