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