1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#define pr_fmt(fmt) "IPv6: " fmt
17
18#include <linux/errno.h>
19#include <linux/types.h>
20#include <linux/net.h>
21#include <linux/route.h>
22#include <linux/netdevice.h>
23#include <linux/in6.h>
24#include <linux/init.h>
25#include <linux/list.h>
26#include <linux/slab.h>
27
28#include <net/ip.h>
29#include <net/ipv6.h>
30#include <net/ndisc.h>
31#include <net/addrconf.h>
32#include <net/lwtunnel.h>
33#include <net/fib_notifier.h>
34
35#include <net/ip_fib.h>
36#include <net/ip6_fib.h>
37#include <net/ip6_route.h>
38
39static struct kmem_cache *fib6_node_kmem __read_mostly;
40
41struct fib6_cleaner {
42 struct fib6_walker w;
43 struct net *net;
44 int (*func)(struct fib6_info *, void *arg);
45 int sernum;
46 void *arg;
47 bool skip_notify;
48};
49
50#ifdef CONFIG_IPV6_SUBTREES
51#define FWS_INIT FWS_S
52#else
53#define FWS_INIT FWS_L
54#endif
55
56static struct fib6_info *fib6_find_prefix(struct net *net,
57 struct fib6_table *table,
58 struct fib6_node *fn);
59static struct fib6_node *fib6_repair_tree(struct net *net,
60 struct fib6_table *table,
61 struct fib6_node *fn);
62static int fib6_walk(struct net *net, struct fib6_walker *w);
63static int fib6_walk_continue(struct fib6_walker *w);
64
65
66
67
68
69
70
71
72static void fib6_gc_timer_cb(struct timer_list *t);
73
74#define FOR_WALKERS(net, w) \
75 list_for_each_entry(w, &(net)->ipv6.fib6_walkers, lh)
76
77static void fib6_walker_link(struct net *net, struct fib6_walker *w)
78{
79 write_lock_bh(&net->ipv6.fib6_walker_lock);
80 list_add(&w->lh, &net->ipv6.fib6_walkers);
81 write_unlock_bh(&net->ipv6.fib6_walker_lock);
82}
83
84static void fib6_walker_unlink(struct net *net, struct fib6_walker *w)
85{
86 write_lock_bh(&net->ipv6.fib6_walker_lock);
87 list_del(&w->lh);
88 write_unlock_bh(&net->ipv6.fib6_walker_lock);
89}
90
91static int fib6_new_sernum(struct net *net)
92{
93 int new, old;
94
95 do {
96 old = atomic_read(&net->ipv6.fib6_sernum);
97 new = old < INT_MAX ? old + 1 : 1;
98 } while (atomic_cmpxchg(&net->ipv6.fib6_sernum,
99 old, new) != old);
100 return new;
101}
102
103enum {
104 FIB6_NO_SERNUM_CHANGE = 0,
105};
106
107void fib6_update_sernum(struct net *net, struct fib6_info *f6i)
108{
109 struct fib6_node *fn;
110
111 fn = rcu_dereference_protected(f6i->fib6_node,
112 lockdep_is_held(&f6i->fib6_table->tb6_lock));
113 if (fn)
114 fn->fn_sernum = fib6_new_sernum(net);
115}
116
117
118
119
120
121
122
123
124
125
126
127#if defined(__LITTLE_ENDIAN)
128# define BITOP_BE32_SWIZZLE (0x1F & ~7)
129#else
130# define BITOP_BE32_SWIZZLE 0
131#endif
132
133static __be32 addr_bit_set(const void *token, int fn_bit)
134{
135 const __be32 *addr = token;
136
137
138
139
140
141
142
143 return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
144 addr[fn_bit >> 5];
145}
146
147struct fib6_info *fib6_info_alloc(gfp_t gfp_flags, bool with_fib6_nh)
148{
149 struct fib6_info *f6i;
150 size_t sz = sizeof(*f6i);
151
152 if (with_fib6_nh)
153 sz += sizeof(struct fib6_nh);
154
155 f6i = kzalloc(sz, gfp_flags);
156 if (!f6i)
157 return NULL;
158
159
160 INIT_LIST_HEAD(&f6i->fib6_siblings);
161 refcount_set(&f6i->fib6_ref, 1);
162
163 return f6i;
164}
165
166void fib6_info_destroy_rcu(struct rcu_head *head)
167{
168 struct fib6_info *f6i = container_of(head, struct fib6_info, rcu);
169
170 WARN_ON(f6i->fib6_node);
171
172 if (f6i->nh)
173 nexthop_put(f6i->nh);
174 else
175 fib6_nh_release(f6i->fib6_nh);
176
177 ip_fib_metrics_put(f6i->fib6_metrics);
178 kfree(f6i);
179}
180EXPORT_SYMBOL_GPL(fib6_info_destroy_rcu);
181
182static struct fib6_node *node_alloc(struct net *net)
183{
184 struct fib6_node *fn;
185
186 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
187 if (fn)
188 net->ipv6.rt6_stats->fib_nodes++;
189
190 return fn;
191}
192
193static void node_free_immediate(struct net *net, struct fib6_node *fn)
194{
195 kmem_cache_free(fib6_node_kmem, fn);
196 net->ipv6.rt6_stats->fib_nodes--;
197}
198
199static void node_free_rcu(struct rcu_head *head)
200{
201 struct fib6_node *fn = container_of(head, struct fib6_node, rcu);
202
203 kmem_cache_free(fib6_node_kmem, fn);
204}
205
206static void node_free(struct net *net, struct fib6_node *fn)
207{
208 call_rcu(&fn->rcu, node_free_rcu);
209 net->ipv6.rt6_stats->fib_nodes--;
210}
211
212static void fib6_free_table(struct fib6_table *table)
213{
214 inetpeer_invalidate_tree(&table->tb6_peers);
215 kfree(table);
216}
217
218static void fib6_link_table(struct net *net, struct fib6_table *tb)
219{
220 unsigned int h;
221
222
223
224
225
226 spin_lock_init(&tb->tb6_lock);
227 h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
228
229
230
231
232
233 hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
234}
235
236#ifdef CONFIG_IPV6_MULTIPLE_TABLES
237
238static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
239{
240 struct fib6_table *table;
241
242 table = kzalloc(sizeof(*table), GFP_ATOMIC);
243 if (table) {
244 table->tb6_id = id;
245 rcu_assign_pointer(table->tb6_root.leaf,
246 net->ipv6.fib6_null_entry);
247 table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
248 inet_peer_base_init(&table->tb6_peers);
249 }
250
251 return table;
252}
253
254struct fib6_table *fib6_new_table(struct net *net, u32 id)
255{
256 struct fib6_table *tb;
257
258 if (id == 0)
259 id = RT6_TABLE_MAIN;
260 tb = fib6_get_table(net, id);
261 if (tb)
262 return tb;
263
264 tb = fib6_alloc_table(net, id);
265 if (tb)
266 fib6_link_table(net, tb);
267
268 return tb;
269}
270EXPORT_SYMBOL_GPL(fib6_new_table);
271
272struct fib6_table *fib6_get_table(struct net *net, u32 id)
273{
274 struct fib6_table *tb;
275 struct hlist_head *head;
276 unsigned int h;
277
278 if (id == 0)
279 id = RT6_TABLE_MAIN;
280 h = id & (FIB6_TABLE_HASHSZ - 1);
281 rcu_read_lock();
282 head = &net->ipv6.fib_table_hash[h];
283 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
284 if (tb->tb6_id == id) {
285 rcu_read_unlock();
286 return tb;
287 }
288 }
289 rcu_read_unlock();
290
291 return NULL;
292}
293EXPORT_SYMBOL_GPL(fib6_get_table);
294
295static void __net_init fib6_tables_init(struct net *net)
296{
297 fib6_link_table(net, net->ipv6.fib6_main_tbl);
298 fib6_link_table(net, net->ipv6.fib6_local_tbl);
299}
300#else
301
302struct fib6_table *fib6_new_table(struct net *net, u32 id)
303{
304 return fib6_get_table(net, id);
305}
306
307struct fib6_table *fib6_get_table(struct net *net, u32 id)
308{
309 return net->ipv6.fib6_main_tbl;
310}
311
312struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
313 const struct sk_buff *skb,
314 int flags, pol_lookup_t lookup)
315{
316 struct rt6_info *rt;
317
318 rt = pol_lookup_func(lookup,
319 net, net->ipv6.fib6_main_tbl, fl6, skb, flags);
320 if (rt->dst.error == -EAGAIN) {
321 ip6_rt_put_flags(rt, flags);
322 rt = net->ipv6.ip6_null_entry;
323 if (!(flags & RT6_LOOKUP_F_DST_NOREF))
324 dst_hold(&rt->dst);
325 }
326
327 return &rt->dst;
328}
329
330
331int fib6_lookup(struct net *net, int oif, struct flowi6 *fl6,
332 struct fib6_result *res, int flags)
333{
334 return fib6_table_lookup(net, net->ipv6.fib6_main_tbl, oif, fl6,
335 res, flags);
336}
337
338static void __net_init fib6_tables_init(struct net *net)
339{
340 fib6_link_table(net, net->ipv6.fib6_main_tbl);
341}
342
343#endif
344
345unsigned int fib6_tables_seq_read(struct net *net)
346{
347 unsigned int h, fib_seq = 0;
348
349 rcu_read_lock();
350 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
351 struct hlist_head *head = &net->ipv6.fib_table_hash[h];
352 struct fib6_table *tb;
353
354 hlist_for_each_entry_rcu(tb, head, tb6_hlist)
355 fib_seq += tb->fib_seq;
356 }
357 rcu_read_unlock();
358
359 return fib_seq;
360}
361
362static int call_fib6_entry_notifier(struct notifier_block *nb,
363 enum fib_event_type event_type,
364 struct fib6_info *rt,
365 struct netlink_ext_ack *extack)
366{
367 struct fib6_entry_notifier_info info = {
368 .info.extack = extack,
369 .rt = rt,
370 };
371
372 return call_fib6_notifier(nb, event_type, &info.info);
373}
374
375static int call_fib6_multipath_entry_notifier(struct notifier_block *nb,
376 enum fib_event_type event_type,
377 struct fib6_info *rt,
378 unsigned int nsiblings,
379 struct netlink_ext_ack *extack)
380{
381 struct fib6_entry_notifier_info info = {
382 .info.extack = extack,
383 .rt = rt,
384 .nsiblings = nsiblings,
385 };
386
387 return call_fib6_notifier(nb, event_type, &info.info);
388}
389
390int call_fib6_entry_notifiers(struct net *net,
391 enum fib_event_type event_type,
392 struct fib6_info *rt,
393 struct netlink_ext_ack *extack)
394{
395 struct fib6_entry_notifier_info info = {
396 .info.extack = extack,
397 .rt = rt,
398 };
399
400 rt->fib6_table->fib_seq++;
401 return call_fib6_notifiers(net, event_type, &info.info);
402}
403
404int call_fib6_multipath_entry_notifiers(struct net *net,
405 enum fib_event_type event_type,
406 struct fib6_info *rt,
407 unsigned int nsiblings,
408 struct netlink_ext_ack *extack)
409{
410 struct fib6_entry_notifier_info info = {
411 .info.extack = extack,
412 .rt = rt,
413 .nsiblings = nsiblings,
414 };
415
416 rt->fib6_table->fib_seq++;
417 return call_fib6_notifiers(net, event_type, &info.info);
418}
419
420int call_fib6_entry_notifiers_replace(struct net *net, struct fib6_info *rt)
421{
422 struct fib6_entry_notifier_info info = {
423 .rt = rt,
424 .nsiblings = rt->fib6_nsiblings,
425 };
426
427 rt->fib6_table->fib_seq++;
428 return call_fib6_notifiers(net, FIB_EVENT_ENTRY_REPLACE, &info.info);
429}
430
431struct fib6_dump_arg {
432 struct net *net;
433 struct notifier_block *nb;
434 struct netlink_ext_ack *extack;
435};
436
437static int fib6_rt_dump(struct fib6_info *rt, struct fib6_dump_arg *arg)
438{
439 enum fib_event_type fib_event = FIB_EVENT_ENTRY_REPLACE;
440 int err;
441
442 if (!rt || rt == arg->net->ipv6.fib6_null_entry)
443 return 0;
444
445 if (rt->fib6_nsiblings)
446 err = call_fib6_multipath_entry_notifier(arg->nb, fib_event,
447 rt,
448 rt->fib6_nsiblings,
449 arg->extack);
450 else
451 err = call_fib6_entry_notifier(arg->nb, fib_event, rt,
452 arg->extack);
453
454 return err;
455}
456
457static int fib6_node_dump(struct fib6_walker *w)
458{
459 int err;
460
461 err = fib6_rt_dump(w->leaf, w->args);
462 w->leaf = NULL;
463 return err;
464}
465
466static int fib6_table_dump(struct net *net, struct fib6_table *tb,
467 struct fib6_walker *w)
468{
469 int err;
470
471 w->root = &tb->tb6_root;
472 spin_lock_bh(&tb->tb6_lock);
473 err = fib6_walk(net, w);
474 spin_unlock_bh(&tb->tb6_lock);
475 return err;
476}
477
478
479int fib6_tables_dump(struct net *net, struct notifier_block *nb,
480 struct netlink_ext_ack *extack)
481{
482 struct fib6_dump_arg arg;
483 struct fib6_walker *w;
484 unsigned int h;
485 int err = 0;
486
487 w = kzalloc(sizeof(*w), GFP_ATOMIC);
488 if (!w)
489 return -ENOMEM;
490
491 w->func = fib6_node_dump;
492 arg.net = net;
493 arg.nb = nb;
494 arg.extack = extack;
495 w->args = &arg;
496
497 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
498 struct hlist_head *head = &net->ipv6.fib_table_hash[h];
499 struct fib6_table *tb;
500
501 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
502 err = fib6_table_dump(net, tb, w);
503 if (err)
504 goto out;
505 }
506 }
507
508out:
509 kfree(w);
510
511
512 return err > 0 ? -EINVAL : err;
513}
514
515static int fib6_dump_node(struct fib6_walker *w)
516{
517 int res;
518 struct fib6_info *rt;
519
520 for_each_fib6_walker_rt(w) {
521 res = rt6_dump_route(rt, w->args, w->skip_in_node);
522 if (res >= 0) {
523
524 w->leaf = rt;
525
526
527
528
529 w->skip_in_node += res;
530
531 return 1;
532 }
533 w->skip_in_node = 0;
534
535
536
537
538
539
540 if (rt->fib6_nsiblings)
541 rt = list_last_entry(&rt->fib6_siblings,
542 struct fib6_info,
543 fib6_siblings);
544 }
545 w->leaf = NULL;
546 return 0;
547}
548
549static void fib6_dump_end(struct netlink_callback *cb)
550{
551 struct net *net = sock_net(cb->skb->sk);
552 struct fib6_walker *w = (void *)cb->args[2];
553
554 if (w) {
555 if (cb->args[4]) {
556 cb->args[4] = 0;
557 fib6_walker_unlink(net, w);
558 }
559 cb->args[2] = 0;
560 kfree(w);
561 }
562 cb->done = (void *)cb->args[3];
563 cb->args[1] = 3;
564}
565
566static int fib6_dump_done(struct netlink_callback *cb)
567{
568 fib6_dump_end(cb);
569 return cb->done ? cb->done(cb) : 0;
570}
571
572static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
573 struct netlink_callback *cb)
574{
575 struct net *net = sock_net(skb->sk);
576 struct fib6_walker *w;
577 int res;
578
579 w = (void *)cb->args[2];
580 w->root = &table->tb6_root;
581
582 if (cb->args[4] == 0) {
583 w->count = 0;
584 w->skip = 0;
585 w->skip_in_node = 0;
586
587 spin_lock_bh(&table->tb6_lock);
588 res = fib6_walk(net, w);
589 spin_unlock_bh(&table->tb6_lock);
590 if (res > 0) {
591 cb->args[4] = 1;
592 cb->args[5] = w->root->fn_sernum;
593 }
594 } else {
595 if (cb->args[5] != w->root->fn_sernum) {
596
597 cb->args[5] = w->root->fn_sernum;
598 w->state = FWS_INIT;
599 w->node = w->root;
600 w->skip = w->count;
601 w->skip_in_node = 0;
602 } else
603 w->skip = 0;
604
605 spin_lock_bh(&table->tb6_lock);
606 res = fib6_walk_continue(w);
607 spin_unlock_bh(&table->tb6_lock);
608 if (res <= 0) {
609 fib6_walker_unlink(net, w);
610 cb->args[4] = 0;
611 }
612 }
613
614 return res;
615}
616
617static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
618{
619 struct rt6_rtnl_dump_arg arg = { .filter.dump_exceptions = true,
620 .filter.dump_routes = true };
621 const struct nlmsghdr *nlh = cb->nlh;
622 struct net *net = sock_net(skb->sk);
623 unsigned int h, s_h;
624 unsigned int e = 0, s_e;
625 struct fib6_walker *w;
626 struct fib6_table *tb;
627 struct hlist_head *head;
628 int res = 0;
629
630 if (cb->strict_check) {
631 int err;
632
633 err = ip_valid_fib_dump_req(net, nlh, &arg.filter, cb);
634 if (err < 0)
635 return err;
636 } else if (nlmsg_len(nlh) >= sizeof(struct rtmsg)) {
637 struct rtmsg *rtm = nlmsg_data(nlh);
638
639 if (rtm->rtm_flags & RTM_F_PREFIX)
640 arg.filter.flags = RTM_F_PREFIX;
641 }
642
643 w = (void *)cb->args[2];
644 if (!w) {
645
646
647
648
649 cb->args[3] = (long)cb->done;
650 cb->done = fib6_dump_done;
651
652
653
654
655 w = kzalloc(sizeof(*w), GFP_ATOMIC);
656 if (!w)
657 return -ENOMEM;
658 w->func = fib6_dump_node;
659 cb->args[2] = (long)w;
660 }
661
662 arg.skb = skb;
663 arg.cb = cb;
664 arg.net = net;
665 w->args = &arg;
666
667 if (arg.filter.table_id) {
668 tb = fib6_get_table(net, arg.filter.table_id);
669 if (!tb) {
670 if (rtnl_msg_family(cb->nlh) != PF_INET6)
671 goto out;
672
673 NL_SET_ERR_MSG_MOD(cb->extack, "FIB table does not exist");
674 return -ENOENT;
675 }
676
677 if (!cb->args[0]) {
678 res = fib6_dump_table(tb, skb, cb);
679 if (!res)
680 cb->args[0] = 1;
681 }
682 goto out;
683 }
684
685 s_h = cb->args[0];
686 s_e = cb->args[1];
687
688 rcu_read_lock();
689 for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
690 e = 0;
691 head = &net->ipv6.fib_table_hash[h];
692 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
693 if (e < s_e)
694 goto next;
695 res = fib6_dump_table(tb, skb, cb);
696 if (res != 0)
697 goto out_unlock;
698next:
699 e++;
700 }
701 }
702out_unlock:
703 rcu_read_unlock();
704 cb->args[1] = e;
705 cb->args[0] = h;
706out:
707 res = res < 0 ? res : skb->len;
708 if (res <= 0)
709 fib6_dump_end(cb);
710 return res;
711}
712
713void fib6_metric_set(struct fib6_info *f6i, int metric, u32 val)
714{
715 if (!f6i)
716 return;
717
718 if (f6i->fib6_metrics == &dst_default_metrics) {
719 struct dst_metrics *p = kzalloc(sizeof(*p), GFP_ATOMIC);
720
721 if (!p)
722 return;
723
724 refcount_set(&p->refcnt, 1);
725 f6i->fib6_metrics = p;
726 }
727
728 f6i->fib6_metrics->metrics[metric - 1] = val;
729}
730
731
732
733
734
735
736
737
738
739static struct fib6_node *fib6_add_1(struct net *net,
740 struct fib6_table *table,
741 struct fib6_node *root,
742 struct in6_addr *addr, int plen,
743 int offset, int allow_create,
744 int replace_required,
745 struct netlink_ext_ack *extack)
746{
747 struct fib6_node *fn, *in, *ln;
748 struct fib6_node *pn = NULL;
749 struct rt6key *key;
750 int bit;
751 __be32 dir = 0;
752
753 RT6_TRACE("fib6_add_1\n");
754
755
756
757 fn = root;
758
759 do {
760 struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
761 lockdep_is_held(&table->tb6_lock));
762 key = (struct rt6key *)((u8 *)leaf + offset);
763
764
765
766
767 if (plen < fn->fn_bit ||
768 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
769 if (!allow_create) {
770 if (replace_required) {
771 NL_SET_ERR_MSG(extack,
772 "Can not replace route - no match found");
773 pr_warn("Can't replace route, no match found\n");
774 return ERR_PTR(-ENOENT);
775 }
776 pr_warn("NLM_F_CREATE should be set when creating new route\n");
777 }
778 goto insert_above;
779 }
780
781
782
783
784
785 if (plen == fn->fn_bit) {
786
787 if (!(fn->fn_flags & RTN_RTINFO)) {
788 RCU_INIT_POINTER(fn->leaf, NULL);
789 fib6_info_release(leaf);
790
791 } else if (fn->fn_flags & RTN_TL_ROOT &&
792 rcu_access_pointer(fn->leaf) ==
793 net->ipv6.fib6_null_entry) {
794 RCU_INIT_POINTER(fn->leaf, NULL);
795 }
796
797 return fn;
798 }
799
800
801
802
803
804
805 dir = addr_bit_set(addr, fn->fn_bit);
806 pn = fn;
807 fn = dir ?
808 rcu_dereference_protected(fn->right,
809 lockdep_is_held(&table->tb6_lock)) :
810 rcu_dereference_protected(fn->left,
811 lockdep_is_held(&table->tb6_lock));
812 } while (fn);
813
814 if (!allow_create) {
815
816
817
818
819
820
821
822
823
824 if (replace_required) {
825 NL_SET_ERR_MSG(extack,
826 "Can not replace route - no match found");
827 pr_warn("Can't replace route, no match found\n");
828 return ERR_PTR(-ENOENT);
829 }
830 pr_warn("NLM_F_CREATE should be set when creating new route\n");
831 }
832
833
834
835
836
837 ln = node_alloc(net);
838
839 if (!ln)
840 return ERR_PTR(-ENOMEM);
841 ln->fn_bit = plen;
842 RCU_INIT_POINTER(ln->parent, pn);
843
844 if (dir)
845 rcu_assign_pointer(pn->right, ln);
846 else
847 rcu_assign_pointer(pn->left, ln);
848
849 return ln;
850
851
852insert_above:
853
854
855
856
857
858
859
860
861 pn = rcu_dereference_protected(fn->parent,
862 lockdep_is_held(&table->tb6_lock));
863
864
865
866
867
868
869
870 bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
871
872
873
874
875
876
877 if (plen > bit) {
878 in = node_alloc(net);
879 ln = node_alloc(net);
880
881 if (!in || !ln) {
882 if (in)
883 node_free_immediate(net, in);
884 if (ln)
885 node_free_immediate(net, ln);
886 return ERR_PTR(-ENOMEM);
887 }
888
889
890
891
892
893
894
895
896
897 in->fn_bit = bit;
898
899 RCU_INIT_POINTER(in->parent, pn);
900 in->leaf = fn->leaf;
901 fib6_info_hold(rcu_dereference_protected(in->leaf,
902 lockdep_is_held(&table->tb6_lock)));
903
904
905 if (dir)
906 rcu_assign_pointer(pn->right, in);
907 else
908 rcu_assign_pointer(pn->left, in);
909
910 ln->fn_bit = plen;
911
912 RCU_INIT_POINTER(ln->parent, in);
913 rcu_assign_pointer(fn->parent, in);
914
915 if (addr_bit_set(addr, bit)) {
916 rcu_assign_pointer(in->right, ln);
917 rcu_assign_pointer(in->left, fn);
918 } else {
919 rcu_assign_pointer(in->left, ln);
920 rcu_assign_pointer(in->right, fn);
921 }
922 } else {
923
924
925
926
927
928
929
930 ln = node_alloc(net);
931
932 if (!ln)
933 return ERR_PTR(-ENOMEM);
934
935 ln->fn_bit = plen;
936
937 RCU_INIT_POINTER(ln->parent, pn);
938
939 if (addr_bit_set(&key->addr, plen))
940 RCU_INIT_POINTER(ln->right, fn);
941 else
942 RCU_INIT_POINTER(ln->left, fn);
943
944 rcu_assign_pointer(fn->parent, ln);
945
946 if (dir)
947 rcu_assign_pointer(pn->right, ln);
948 else
949 rcu_assign_pointer(pn->left, ln);
950 }
951 return ln;
952}
953
954static void __fib6_drop_pcpu_from(struct fib6_nh *fib6_nh,
955 const struct fib6_info *match,
956 const struct fib6_table *table)
957{
958 int cpu;
959
960 if (!fib6_nh->rt6i_pcpu)
961 return;
962
963
964
965
966 for_each_possible_cpu(cpu) {
967 struct rt6_info **ppcpu_rt;
968 struct rt6_info *pcpu_rt;
969
970 ppcpu_rt = per_cpu_ptr(fib6_nh->rt6i_pcpu, cpu);
971 pcpu_rt = *ppcpu_rt;
972
973
974
975
976
977
978 if (pcpu_rt && rcu_access_pointer(pcpu_rt->from) == match) {
979 struct fib6_info *from;
980
981 from = xchg((__force struct fib6_info **)&pcpu_rt->from, NULL);
982 fib6_info_release(from);
983 }
984 }
985}
986
987struct fib6_nh_pcpu_arg {
988 struct fib6_info *from;
989 const struct fib6_table *table;
990};
991
992static int fib6_nh_drop_pcpu_from(struct fib6_nh *nh, void *_arg)
993{
994 struct fib6_nh_pcpu_arg *arg = _arg;
995
996 __fib6_drop_pcpu_from(nh, arg->from, arg->table);
997 return 0;
998}
999
1000static void fib6_drop_pcpu_from(struct fib6_info *f6i,
1001 const struct fib6_table *table)
1002{
1003
1004
1005
1006 f6i->fib6_destroying = 1;
1007 mb();
1008
1009 if (f6i->nh) {
1010 struct fib6_nh_pcpu_arg arg = {
1011 .from = f6i,
1012 .table = table
1013 };
1014
1015 nexthop_for_each_fib6_nh(f6i->nh, fib6_nh_drop_pcpu_from,
1016 &arg);
1017 } else {
1018 struct fib6_nh *fib6_nh;
1019
1020 fib6_nh = f6i->fib6_nh;
1021 __fib6_drop_pcpu_from(fib6_nh, f6i, table);
1022 }
1023}
1024
1025static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,
1026 struct net *net)
1027{
1028 struct fib6_table *table = rt->fib6_table;
1029
1030
1031 rt6_flush_exceptions(rt);
1032 fib6_drop_pcpu_from(rt, table);
1033
1034 if (rt->nh && !list_empty(&rt->nh_list))
1035 list_del_init(&rt->nh_list);
1036
1037 if (refcount_read(&rt->fib6_ref) != 1) {
1038
1039
1040
1041
1042
1043
1044 while (fn) {
1045 struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
1046 lockdep_is_held(&table->tb6_lock));
1047 struct fib6_info *new_leaf;
1048 if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {
1049 new_leaf = fib6_find_prefix(net, table, fn);
1050 fib6_info_hold(new_leaf);
1051
1052 rcu_assign_pointer(fn->leaf, new_leaf);
1053 fib6_info_release(rt);
1054 }
1055 fn = rcu_dereference_protected(fn->parent,
1056 lockdep_is_held(&table->tb6_lock));
1057 }
1058 }
1059}
1060
1061
1062
1063
1064
1065static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,
1066 struct nl_info *info,
1067 struct netlink_ext_ack *extack)
1068{
1069 struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
1070 lockdep_is_held(&rt->fib6_table->tb6_lock));
1071 struct fib6_info *iter = NULL;
1072 struct fib6_info __rcu **ins;
1073 struct fib6_info __rcu **fallback_ins = NULL;
1074 int replace = (info->nlh &&
1075 (info->nlh->nlmsg_flags & NLM_F_REPLACE));
1076 int add = (!info->nlh ||
1077 (info->nlh->nlmsg_flags & NLM_F_CREATE));
1078 int found = 0;
1079 bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
1080 bool notify_sibling_rt = false;
1081 u16 nlflags = NLM_F_EXCL;
1082 int err;
1083
1084 if (info->nlh && (info->nlh->nlmsg_flags & NLM_F_APPEND))
1085 nlflags |= NLM_F_APPEND;
1086
1087 ins = &fn->leaf;
1088
1089 for (iter = leaf; iter;
1090 iter = rcu_dereference_protected(iter->fib6_next,
1091 lockdep_is_held(&rt->fib6_table->tb6_lock))) {
1092
1093
1094
1095
1096 if (iter->fib6_metric == rt->fib6_metric) {
1097
1098
1099
1100 if (info->nlh &&
1101 (info->nlh->nlmsg_flags & NLM_F_EXCL))
1102 return -EEXIST;
1103
1104 nlflags &= ~NLM_F_EXCL;
1105 if (replace) {
1106 if (rt_can_ecmp == rt6_qualify_for_ecmp(iter)) {
1107 found++;
1108 break;
1109 }
1110 fallback_ins = fallback_ins ?: ins;
1111 goto next_iter;
1112 }
1113
1114 if (rt6_duplicate_nexthop(iter, rt)) {
1115 if (rt->fib6_nsiblings)
1116 rt->fib6_nsiblings = 0;
1117 if (!(iter->fib6_flags & RTF_EXPIRES))
1118 return -EEXIST;
1119 if (!(rt->fib6_flags & RTF_EXPIRES))
1120 fib6_clean_expires(iter);
1121 else
1122 fib6_set_expires(iter, rt->expires);
1123
1124 if (rt->fib6_pmtu)
1125 fib6_metric_set(iter, RTAX_MTU,
1126 rt->fib6_pmtu);
1127 return -EEXIST;
1128 }
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140 if (rt_can_ecmp &&
1141 rt6_qualify_for_ecmp(iter))
1142 rt->fib6_nsiblings++;
1143 }
1144
1145 if (iter->fib6_metric > rt->fib6_metric)
1146 break;
1147
1148next_iter:
1149 ins = &iter->fib6_next;
1150 }
1151
1152 if (fallback_ins && !found) {
1153
1154
1155
1156 ins = fallback_ins;
1157 iter = rcu_dereference_protected(*ins,
1158 lockdep_is_held(&rt->fib6_table->tb6_lock));
1159 found++;
1160 }
1161
1162
1163 if (ins == &fn->leaf)
1164 fn->rr_ptr = NULL;
1165
1166
1167 if (rt->fib6_nsiblings) {
1168 unsigned int fib6_nsiblings;
1169 struct fib6_info *sibling, *temp_sibling;
1170
1171
1172 sibling = leaf;
1173 notify_sibling_rt = true;
1174 while (sibling) {
1175 if (sibling->fib6_metric == rt->fib6_metric &&
1176 rt6_qualify_for_ecmp(sibling)) {
1177 list_add_tail(&rt->fib6_siblings,
1178 &sibling->fib6_siblings);
1179 break;
1180 }
1181 sibling = rcu_dereference_protected(sibling->fib6_next,
1182 lockdep_is_held(&rt->fib6_table->tb6_lock));
1183 notify_sibling_rt = false;
1184 }
1185
1186
1187
1188
1189 fib6_nsiblings = 0;
1190 list_for_each_entry_safe(sibling, temp_sibling,
1191 &rt->fib6_siblings, fib6_siblings) {
1192 sibling->fib6_nsiblings++;
1193 BUG_ON(sibling->fib6_nsiblings != rt->fib6_nsiblings);
1194 fib6_nsiblings++;
1195 }
1196 BUG_ON(fib6_nsiblings != rt->fib6_nsiblings);
1197 rt6_multipath_rebalance(temp_sibling);
1198 }
1199
1200
1201
1202
1203 if (!replace) {
1204 if (!add)
1205 pr_warn("NLM_F_CREATE should be set when creating new route\n");
1206
1207add:
1208 nlflags |= NLM_F_CREATE;
1209
1210
1211
1212
1213
1214 if (!info->skip_notify_kernel &&
1215 (notify_sibling_rt || ins == &fn->leaf)) {
1216 enum fib_event_type fib_event;
1217
1218 if (notify_sibling_rt)
1219 fib_event = FIB_EVENT_ENTRY_APPEND;
1220 else
1221 fib_event = FIB_EVENT_ENTRY_REPLACE;
1222 err = call_fib6_entry_notifiers(info->nl_net,
1223 fib_event, rt,
1224 extack);
1225 if (err) {
1226 struct fib6_info *sibling, *next_sibling;
1227
1228
1229
1230
1231 if (!rt->fib6_nsiblings)
1232 return err;
1233
1234 list_for_each_entry_safe(sibling, next_sibling,
1235 &rt->fib6_siblings,
1236 fib6_siblings)
1237 sibling->fib6_nsiblings--;
1238 rt->fib6_nsiblings = 0;
1239 list_del_init(&rt->fib6_siblings);
1240 rt6_multipath_rebalance(next_sibling);
1241 return err;
1242 }
1243 }
1244
1245 rcu_assign_pointer(rt->fib6_next, iter);
1246 fib6_info_hold(rt);
1247 rcu_assign_pointer(rt->fib6_node, fn);
1248 rcu_assign_pointer(*ins, rt);
1249 if (!info->skip_notify)
1250 inet6_rt_notify(RTM_NEWROUTE, rt, info, nlflags);
1251 info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
1252
1253 if (!(fn->fn_flags & RTN_RTINFO)) {
1254 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
1255 fn->fn_flags |= RTN_RTINFO;
1256 }
1257
1258 } else {
1259 int nsiblings;
1260
1261 if (!found) {
1262 if (add)
1263 goto add;
1264 pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
1265 return -ENOENT;
1266 }
1267
1268 if (!info->skip_notify_kernel && ins == &fn->leaf) {
1269 err = call_fib6_entry_notifiers(info->nl_net,
1270 FIB_EVENT_ENTRY_REPLACE,
1271 rt, extack);
1272 if (err)
1273 return err;
1274 }
1275
1276 fib6_info_hold(rt);
1277 rcu_assign_pointer(rt->fib6_node, fn);
1278 rt->fib6_next = iter->fib6_next;
1279 rcu_assign_pointer(*ins, rt);
1280 if (!info->skip_notify)
1281 inet6_rt_notify(RTM_NEWROUTE, rt, info, NLM_F_REPLACE);
1282 if (!(fn->fn_flags & RTN_RTINFO)) {
1283 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
1284 fn->fn_flags |= RTN_RTINFO;
1285 }
1286 nsiblings = iter->fib6_nsiblings;
1287 iter->fib6_node = NULL;
1288 fib6_purge_rt(iter, fn, info->nl_net);
1289 if (rcu_access_pointer(fn->rr_ptr) == iter)
1290 fn->rr_ptr = NULL;
1291 fib6_info_release(iter);
1292
1293 if (nsiblings) {
1294
1295 ins = &rt->fib6_next;
1296 iter = rcu_dereference_protected(*ins,
1297 lockdep_is_held(&rt->fib6_table->tb6_lock));
1298 while (iter) {
1299 if (iter->fib6_metric > rt->fib6_metric)
1300 break;
1301 if (rt6_qualify_for_ecmp(iter)) {
1302 *ins = iter->fib6_next;
1303 iter->fib6_node = NULL;
1304 fib6_purge_rt(iter, fn, info->nl_net);
1305 if (rcu_access_pointer(fn->rr_ptr) == iter)
1306 fn->rr_ptr = NULL;
1307 fib6_info_release(iter);
1308 nsiblings--;
1309 info->nl_net->ipv6.rt6_stats->fib_rt_entries--;
1310 } else {
1311 ins = &iter->fib6_next;
1312 }
1313 iter = rcu_dereference_protected(*ins,
1314 lockdep_is_held(&rt->fib6_table->tb6_lock));
1315 }
1316 WARN_ON(nsiblings != 0);
1317 }
1318 }
1319
1320 return 0;
1321}
1322
1323static void fib6_start_gc(struct net *net, struct fib6_info *rt)
1324{
1325 if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
1326 (rt->fib6_flags & RTF_EXPIRES))
1327 mod_timer(&net->ipv6.ip6_fib_timer,
1328 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
1329}
1330
1331void fib6_force_start_gc(struct net *net)
1332{
1333 if (!timer_pending(&net->ipv6.ip6_fib_timer))
1334 mod_timer(&net->ipv6.ip6_fib_timer,
1335 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
1336}
1337
1338static void __fib6_update_sernum_upto_root(struct fib6_info *rt,
1339 int sernum)
1340{
1341 struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,
1342 lockdep_is_held(&rt->fib6_table->tb6_lock));
1343
1344
1345 smp_wmb();
1346 while (fn) {
1347 fn->fn_sernum = sernum;
1348 fn = rcu_dereference_protected(fn->parent,
1349 lockdep_is_held(&rt->fib6_table->tb6_lock));
1350 }
1351}
1352
1353void fib6_update_sernum_upto_root(struct net *net, struct fib6_info *rt)
1354{
1355 __fib6_update_sernum_upto_root(rt, fib6_new_sernum(net));
1356}
1357
1358
1359void fib6_update_sernum_stub(struct net *net, struct fib6_info *f6i)
1360{
1361 spin_lock_bh(&f6i->fib6_table->tb6_lock);
1362 fib6_update_sernum_upto_root(net, f6i);
1363 spin_unlock_bh(&f6i->fib6_table->tb6_lock);
1364}
1365
1366
1367
1368
1369
1370
1371
1372
1373int fib6_add(struct fib6_node *root, struct fib6_info *rt,
1374 struct nl_info *info, struct netlink_ext_ack *extack)
1375{
1376 struct fib6_table *table = rt->fib6_table;
1377 struct fib6_node *fn, *pn = NULL;
1378 int err = -ENOMEM;
1379 int allow_create = 1;
1380 int replace_required = 0;
1381
1382 if (info->nlh) {
1383 if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
1384 allow_create = 0;
1385 if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
1386 replace_required = 1;
1387 }
1388 if (!allow_create && !replace_required)
1389 pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
1390
1391 fn = fib6_add_1(info->nl_net, table, root,
1392 &rt->fib6_dst.addr, rt->fib6_dst.plen,
1393 offsetof(struct fib6_info, fib6_dst), allow_create,
1394 replace_required, extack);
1395 if (IS_ERR(fn)) {
1396 err = PTR_ERR(fn);
1397 fn = NULL;
1398 goto out;
1399 }
1400
1401 pn = fn;
1402
1403#ifdef CONFIG_IPV6_SUBTREES
1404 if (rt->fib6_src.plen) {
1405 struct fib6_node *sn;
1406
1407 if (!rcu_access_pointer(fn->subtree)) {
1408 struct fib6_node *sfn;
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421 sfn = node_alloc(info->nl_net);
1422 if (!sfn)
1423 goto failure;
1424
1425 fib6_info_hold(info->nl_net->ipv6.fib6_null_entry);
1426 rcu_assign_pointer(sfn->leaf,
1427 info->nl_net->ipv6.fib6_null_entry);
1428 sfn->fn_flags = RTN_ROOT;
1429
1430
1431
1432 sn = fib6_add_1(info->nl_net, table, sfn,
1433 &rt->fib6_src.addr, rt->fib6_src.plen,
1434 offsetof(struct fib6_info, fib6_src),
1435 allow_create, replace_required, extack);
1436
1437 if (IS_ERR(sn)) {
1438
1439
1440
1441
1442 node_free_immediate(info->nl_net, sfn);
1443 err = PTR_ERR(sn);
1444 goto failure;
1445 }
1446
1447
1448 rcu_assign_pointer(sfn->parent, fn);
1449 rcu_assign_pointer(fn->subtree, sfn);
1450 } else {
1451 sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),
1452 &rt->fib6_src.addr, rt->fib6_src.plen,
1453 offsetof(struct fib6_info, fib6_src),
1454 allow_create, replace_required, extack);
1455
1456 if (IS_ERR(sn)) {
1457 err = PTR_ERR(sn);
1458 goto failure;
1459 }
1460 }
1461
1462 if (!rcu_access_pointer(fn->leaf)) {
1463 if (fn->fn_flags & RTN_TL_ROOT) {
1464
1465 rcu_assign_pointer(fn->leaf,
1466 info->nl_net->ipv6.fib6_null_entry);
1467 } else {
1468 fib6_info_hold(rt);
1469 rcu_assign_pointer(fn->leaf, rt);
1470 }
1471 }
1472 fn = sn;
1473 }
1474#endif
1475
1476 err = fib6_add_rt2node(fn, rt, info, extack);
1477 if (!err) {
1478 if (rt->nh)
1479 list_add(&rt->nh_list, &rt->nh->f6i_list);
1480 __fib6_update_sernum_upto_root(rt, fib6_new_sernum(info->nl_net));
1481 fib6_start_gc(info->nl_net, rt);
1482 }
1483
1484out:
1485 if (err) {
1486#ifdef CONFIG_IPV6_SUBTREES
1487
1488
1489
1490
1491 if (pn != fn) {
1492 struct fib6_info *pn_leaf =
1493 rcu_dereference_protected(pn->leaf,
1494 lockdep_is_held(&table->tb6_lock));
1495 if (pn_leaf == rt) {
1496 pn_leaf = NULL;
1497 RCU_INIT_POINTER(pn->leaf, NULL);
1498 fib6_info_release(rt);
1499 }
1500 if (!pn_leaf && !(pn->fn_flags & RTN_RTINFO)) {
1501 pn_leaf = fib6_find_prefix(info->nl_net, table,
1502 pn);
1503#if RT6_DEBUG >= 2
1504 if (!pn_leaf) {
1505 WARN_ON(!pn_leaf);
1506 pn_leaf =
1507 info->nl_net->ipv6.fib6_null_entry;
1508 }
1509#endif
1510 fib6_info_hold(pn_leaf);
1511 rcu_assign_pointer(pn->leaf, pn_leaf);
1512 }
1513 }
1514#endif
1515 goto failure;
1516 } else if (fib6_requires_src(rt)) {
1517 fib6_routes_require_src_inc(info->nl_net);
1518 }
1519 return err;
1520
1521failure:
1522
1523
1524
1525
1526
1527
1528
1529 if (fn &&
1530 (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||
1531 (fn->fn_flags & RTN_TL_ROOT &&
1532 !rcu_access_pointer(fn->leaf))))
1533 fib6_repair_tree(info->nl_net, table, fn);
1534 return err;
1535}
1536
1537
1538
1539
1540
1541
1542struct lookup_args {
1543 int offset;
1544 const struct in6_addr *addr;
1545};
1546
1547static struct fib6_node *fib6_node_lookup_1(struct fib6_node *root,
1548 struct lookup_args *args)
1549{
1550 struct fib6_node *fn;
1551 __be32 dir;
1552
1553 if (unlikely(args->offset == 0))
1554 return NULL;
1555
1556
1557
1558
1559
1560 fn = root;
1561
1562 for (;;) {
1563 struct fib6_node *next;
1564
1565 dir = addr_bit_set(args->addr, fn->fn_bit);
1566
1567 next = dir ? rcu_dereference(fn->right) :
1568 rcu_dereference(fn->left);
1569
1570 if (next) {
1571 fn = next;
1572 continue;
1573 }
1574 break;
1575 }
1576
1577 while (fn) {
1578 struct fib6_node *subtree = FIB6_SUBTREE(fn);
1579
1580 if (subtree || fn->fn_flags & RTN_RTINFO) {
1581 struct fib6_info *leaf = rcu_dereference(fn->leaf);
1582 struct rt6key *key;
1583
1584 if (!leaf)
1585 goto backtrack;
1586
1587 key = (struct rt6key *) ((u8 *)leaf + args->offset);
1588
1589 if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
1590#ifdef CONFIG_IPV6_SUBTREES
1591 if (subtree) {
1592 struct fib6_node *sfn;
1593 sfn = fib6_node_lookup_1(subtree,
1594 args + 1);
1595 if (!sfn)
1596 goto backtrack;
1597 fn = sfn;
1598 }
1599#endif
1600 if (fn->fn_flags & RTN_RTINFO)
1601 return fn;
1602 }
1603 }
1604backtrack:
1605 if (fn->fn_flags & RTN_ROOT)
1606 break;
1607
1608 fn = rcu_dereference(fn->parent);
1609 }
1610
1611 return NULL;
1612}
1613
1614
1615
1616struct fib6_node *fib6_node_lookup(struct fib6_node *root,
1617 const struct in6_addr *daddr,
1618 const struct in6_addr *saddr)
1619{
1620 struct fib6_node *fn;
1621 struct lookup_args args[] = {
1622 {
1623 .offset = offsetof(struct fib6_info, fib6_dst),
1624 .addr = daddr,
1625 },
1626#ifdef CONFIG_IPV6_SUBTREES
1627 {
1628 .offset = offsetof(struct fib6_info, fib6_src),
1629 .addr = saddr,
1630 },
1631#endif
1632 {
1633 .offset = 0,
1634 }
1635 };
1636
1637 fn = fib6_node_lookup_1(root, daddr ? args : args + 1);
1638 if (!fn || fn->fn_flags & RTN_TL_ROOT)
1639 fn = root;
1640
1641 return fn;
1642}
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656static struct fib6_node *fib6_locate_1(struct fib6_node *root,
1657 const struct in6_addr *addr,
1658 int plen, int offset,
1659 bool exact_match)
1660{
1661 struct fib6_node *fn, *prev = NULL;
1662
1663 for (fn = root; fn ; ) {
1664 struct fib6_info *leaf = rcu_dereference(fn->leaf);
1665 struct rt6key *key;
1666
1667
1668 if (!leaf) {
1669 if (plen <= fn->fn_bit)
1670 goto out;
1671 else
1672 goto next;
1673 }
1674
1675 key = (struct rt6key *)((u8 *)leaf + offset);
1676
1677
1678
1679
1680 if (plen < fn->fn_bit ||
1681 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1682 goto out;
1683
1684 if (plen == fn->fn_bit)
1685 return fn;
1686
1687 if (fn->fn_flags & RTN_RTINFO)
1688 prev = fn;
1689
1690next:
1691
1692
1693
1694 if (addr_bit_set(addr, fn->fn_bit))
1695 fn = rcu_dereference(fn->right);
1696 else
1697 fn = rcu_dereference(fn->left);
1698 }
1699out:
1700 if (exact_match)
1701 return NULL;
1702 else
1703 return prev;
1704}
1705
1706struct fib6_node *fib6_locate(struct fib6_node *root,
1707 const struct in6_addr *daddr, int dst_len,
1708 const struct in6_addr *saddr, int src_len,
1709 bool exact_match)
1710{
1711 struct fib6_node *fn;
1712
1713 fn = fib6_locate_1(root, daddr, dst_len,
1714 offsetof(struct fib6_info, fib6_dst),
1715 exact_match);
1716
1717#ifdef CONFIG_IPV6_SUBTREES
1718 if (src_len) {
1719 WARN_ON(saddr == NULL);
1720 if (fn) {
1721 struct fib6_node *subtree = FIB6_SUBTREE(fn);
1722
1723 if (subtree) {
1724 fn = fib6_locate_1(subtree, saddr, src_len,
1725 offsetof(struct fib6_info, fib6_src),
1726 exact_match);
1727 }
1728 }
1729 }
1730#endif
1731
1732 if (fn && fn->fn_flags & RTN_RTINFO)
1733 return fn;
1734
1735 return NULL;
1736}
1737
1738
1739
1740
1741
1742
1743
1744static struct fib6_info *fib6_find_prefix(struct net *net,
1745 struct fib6_table *table,
1746 struct fib6_node *fn)
1747{
1748 struct fib6_node *child_left, *child_right;
1749
1750 if (fn->fn_flags & RTN_ROOT)
1751 return net->ipv6.fib6_null_entry;
1752
1753 while (fn) {
1754 child_left = rcu_dereference_protected(fn->left,
1755 lockdep_is_held(&table->tb6_lock));
1756 child_right = rcu_dereference_protected(fn->right,
1757 lockdep_is_held(&table->tb6_lock));
1758 if (child_left)
1759 return rcu_dereference_protected(child_left->leaf,
1760 lockdep_is_held(&table->tb6_lock));
1761 if (child_right)
1762 return rcu_dereference_protected(child_right->leaf,
1763 lockdep_is_held(&table->tb6_lock));
1764
1765 fn = FIB6_SUBTREE(fn);
1766 }
1767 return NULL;
1768}
1769
1770
1771
1772
1773
1774
1775
1776static struct fib6_node *fib6_repair_tree(struct net *net,
1777 struct fib6_table *table,
1778 struct fib6_node *fn)
1779{
1780 int children;
1781 int nstate;
1782 struct fib6_node *child;
1783 struct fib6_walker *w;
1784 int iter = 0;
1785
1786
1787 if (fn->fn_flags & RTN_TL_ROOT) {
1788 rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);
1789 return fn;
1790 }
1791
1792 for (;;) {
1793 struct fib6_node *fn_r = rcu_dereference_protected(fn->right,
1794 lockdep_is_held(&table->tb6_lock));
1795 struct fib6_node *fn_l = rcu_dereference_protected(fn->left,
1796 lockdep_is_held(&table->tb6_lock));
1797 struct fib6_node *pn = rcu_dereference_protected(fn->parent,
1798 lockdep_is_held(&table->tb6_lock));
1799 struct fib6_node *pn_r = rcu_dereference_protected(pn->right,
1800 lockdep_is_held(&table->tb6_lock));
1801 struct fib6_node *pn_l = rcu_dereference_protected(pn->left,
1802 lockdep_is_held(&table->tb6_lock));
1803 struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,
1804 lockdep_is_held(&table->tb6_lock));
1805 struct fib6_info *pn_leaf = rcu_dereference_protected(pn->leaf,
1806 lockdep_is_held(&table->tb6_lock));
1807 struct fib6_info *new_fn_leaf;
1808
1809 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1810 iter++;
1811
1812 WARN_ON(fn->fn_flags & RTN_RTINFO);
1813 WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1814 WARN_ON(fn_leaf);
1815
1816 children = 0;
1817 child = NULL;
1818 if (fn_r) {
1819 child = fn_r;
1820 children |= 1;
1821 }
1822 if (fn_l) {
1823 child = fn_l;
1824 children |= 2;
1825 }
1826
1827 if (children == 3 || FIB6_SUBTREE(fn)
1828#ifdef CONFIG_IPV6_SUBTREES
1829
1830 || (children && fn->fn_flags & RTN_ROOT)
1831#endif
1832 ) {
1833 new_fn_leaf = fib6_find_prefix(net, table, fn);
1834#if RT6_DEBUG >= 2
1835 if (!new_fn_leaf) {
1836 WARN_ON(!new_fn_leaf);
1837 new_fn_leaf = net->ipv6.fib6_null_entry;
1838 }
1839#endif
1840 fib6_info_hold(new_fn_leaf);
1841 rcu_assign_pointer(fn->leaf, new_fn_leaf);
1842 return pn;
1843 }
1844
1845#ifdef CONFIG_IPV6_SUBTREES
1846 if (FIB6_SUBTREE(pn) == fn) {
1847 WARN_ON(!(fn->fn_flags & RTN_ROOT));
1848 RCU_INIT_POINTER(pn->subtree, NULL);
1849 nstate = FWS_L;
1850 } else {
1851 WARN_ON(fn->fn_flags & RTN_ROOT);
1852#endif
1853 if (pn_r == fn)
1854 rcu_assign_pointer(pn->right, child);
1855 else if (pn_l == fn)
1856 rcu_assign_pointer(pn->left, child);
1857#if RT6_DEBUG >= 2
1858 else
1859 WARN_ON(1);
1860#endif
1861 if (child)
1862 rcu_assign_pointer(child->parent, pn);
1863 nstate = FWS_R;
1864#ifdef CONFIG_IPV6_SUBTREES
1865 }
1866#endif
1867
1868 read_lock(&net->ipv6.fib6_walker_lock);
1869 FOR_WALKERS(net, w) {
1870 if (!child) {
1871 if (w->node == fn) {
1872 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1873 w->node = pn;
1874 w->state = nstate;
1875 }
1876 } else {
1877 if (w->node == fn) {
1878 w->node = child;
1879 if (children&2) {
1880 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1881 w->state = w->state >= FWS_R ? FWS_U : FWS_INIT;
1882 } else {
1883 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1884 w->state = w->state >= FWS_C ? FWS_U : FWS_INIT;
1885 }
1886 }
1887 }
1888 }
1889 read_unlock(&net->ipv6.fib6_walker_lock);
1890
1891 node_free(net, fn);
1892 if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
1893 return pn;
1894
1895 RCU_INIT_POINTER(pn->leaf, NULL);
1896 fib6_info_release(pn_leaf);
1897 fn = pn;
1898 }
1899}
1900
1901static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,
1902 struct fib6_info __rcu **rtp, struct nl_info *info)
1903{
1904 struct fib6_info *leaf, *replace_rt = NULL;
1905 struct fib6_walker *w;
1906 struct fib6_info *rt = rcu_dereference_protected(*rtp,
1907 lockdep_is_held(&table->tb6_lock));
1908 struct net *net = info->nl_net;
1909 bool notify_del = false;
1910
1911 RT6_TRACE("fib6_del_route\n");
1912
1913
1914
1915
1916
1917 leaf = rcu_dereference_protected(fn->leaf,
1918 lockdep_is_held(&table->tb6_lock));
1919 if (leaf == rt && !rt->fib6_nsiblings) {
1920 if (rcu_access_pointer(rt->fib6_next))
1921 replace_rt = rcu_dereference_protected(rt->fib6_next,
1922 lockdep_is_held(&table->tb6_lock));
1923 else
1924 notify_del = true;
1925 }
1926
1927
1928 *rtp = rt->fib6_next;
1929 rt->fib6_node = NULL;
1930 net->ipv6.rt6_stats->fib_rt_entries--;
1931 net->ipv6.rt6_stats->fib_discarded_routes++;
1932
1933
1934 if (rcu_access_pointer(fn->rr_ptr) == rt)
1935 fn->rr_ptr = NULL;
1936
1937
1938 if (rt->fib6_nsiblings) {
1939 struct fib6_info *sibling, *next_sibling;
1940
1941
1942
1943
1944
1945
1946 if (rt->fib6_metric == leaf->fib6_metric &&
1947 rt6_qualify_for_ecmp(leaf))
1948 notify_del = true;
1949 list_for_each_entry_safe(sibling, next_sibling,
1950 &rt->fib6_siblings, fib6_siblings)
1951 sibling->fib6_nsiblings--;
1952 rt->fib6_nsiblings = 0;
1953 list_del_init(&rt->fib6_siblings);
1954 rt6_multipath_rebalance(next_sibling);
1955 }
1956
1957
1958 read_lock(&net->ipv6.fib6_walker_lock);
1959 FOR_WALKERS(net, w) {
1960 if (w->state == FWS_C && w->leaf == rt) {
1961 RT6_TRACE("walker %p adjusted by delroute\n", w);
1962 w->leaf = rcu_dereference_protected(rt->fib6_next,
1963 lockdep_is_held(&table->tb6_lock));
1964 if (!w->leaf)
1965 w->state = FWS_U;
1966 }
1967 }
1968 read_unlock(&net->ipv6.fib6_walker_lock);
1969
1970
1971
1972
1973
1974 if (!rcu_access_pointer(fn->leaf)) {
1975 if (!(fn->fn_flags & RTN_TL_ROOT)) {
1976 fn->fn_flags &= ~RTN_RTINFO;
1977 net->ipv6.rt6_stats->fib_route_nodes--;
1978 }
1979 fn = fib6_repair_tree(net, table, fn);
1980 }
1981
1982 fib6_purge_rt(rt, fn, net);
1983
1984 if (!info->skip_notify_kernel) {
1985 if (notify_del)
1986 call_fib6_entry_notifiers(net, FIB_EVENT_ENTRY_DEL,
1987 rt, NULL);
1988 else if (replace_rt)
1989 call_fib6_entry_notifiers_replace(net, replace_rt);
1990 }
1991 if (!info->skip_notify)
1992 inet6_rt_notify(RTM_DELROUTE, rt, info, 0);
1993
1994 fib6_info_release(rt);
1995}
1996
1997
1998int fib6_del(struct fib6_info *rt, struct nl_info *info)
1999{
2000 struct net *net = info->nl_net;
2001 struct fib6_info __rcu **rtp;
2002 struct fib6_info __rcu **rtp_next;
2003 struct fib6_table *table;
2004 struct fib6_node *fn;
2005
2006 if (rt == net->ipv6.fib6_null_entry)
2007 return -ENOENT;
2008
2009 table = rt->fib6_table;
2010 fn = rcu_dereference_protected(rt->fib6_node,
2011 lockdep_is_held(&table->tb6_lock));
2012 if (!fn)
2013 return -ENOENT;
2014
2015 WARN_ON(!(fn->fn_flags & RTN_RTINFO));
2016
2017
2018
2019
2020
2021 for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {
2022 struct fib6_info *cur = rcu_dereference_protected(*rtp,
2023 lockdep_is_held(&table->tb6_lock));
2024 if (rt == cur) {
2025 if (fib6_requires_src(cur))
2026 fib6_routes_require_src_dec(info->nl_net);
2027 fib6_del_route(table, fn, rtp, info);
2028 return 0;
2029 }
2030 rtp_next = &cur->fib6_next;
2031 }
2032 return -ENOENT;
2033}
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061static int fib6_walk_continue(struct fib6_walker *w)
2062{
2063 struct fib6_node *fn, *pn, *left, *right;
2064
2065
2066 WARN_ON_ONCE(!(w->root->fn_flags & RTN_TL_ROOT));
2067
2068 for (;;) {
2069 fn = w->node;
2070 if (!fn)
2071 return 0;
2072
2073 switch (w->state) {
2074#ifdef CONFIG_IPV6_SUBTREES
2075 case FWS_S:
2076 if (FIB6_SUBTREE(fn)) {
2077 w->node = FIB6_SUBTREE(fn);
2078 continue;
2079 }
2080 w->state = FWS_L;
2081 fallthrough;
2082#endif
2083 case FWS_L:
2084 left = rcu_dereference_protected(fn->left, 1);
2085 if (left) {
2086 w->node = left;
2087 w->state = FWS_INIT;
2088 continue;
2089 }
2090 w->state = FWS_R;
2091 fallthrough;
2092 case FWS_R:
2093 right = rcu_dereference_protected(fn->right, 1);
2094 if (right) {
2095 w->node = right;
2096 w->state = FWS_INIT;
2097 continue;
2098 }
2099 w->state = FWS_C;
2100 w->leaf = rcu_dereference_protected(fn->leaf, 1);
2101 fallthrough;
2102 case FWS_C:
2103 if (w->leaf && fn->fn_flags & RTN_RTINFO) {
2104 int err;
2105
2106 if (w->skip) {
2107 w->skip--;
2108 goto skip;
2109 }
2110
2111 err = w->func(w);
2112 if (err)
2113 return err;
2114
2115 w->count++;
2116 continue;
2117 }
2118skip:
2119 w->state = FWS_U;
2120 fallthrough;
2121 case FWS_U:
2122 if (fn == w->root)
2123 return 0;
2124 pn = rcu_dereference_protected(fn->parent, 1);
2125 left = rcu_dereference_protected(pn->left, 1);
2126 right = rcu_dereference_protected(pn->right, 1);
2127 w->node = pn;
2128#ifdef CONFIG_IPV6_SUBTREES
2129 if (FIB6_SUBTREE(pn) == fn) {
2130 WARN_ON(!(fn->fn_flags & RTN_ROOT));
2131 w->state = FWS_L;
2132 continue;
2133 }
2134#endif
2135 if (left == fn) {
2136 w->state = FWS_R;
2137 continue;
2138 }
2139 if (right == fn) {
2140 w->state = FWS_C;
2141 w->leaf = rcu_dereference_protected(w->node->leaf, 1);
2142 continue;
2143 }
2144#if RT6_DEBUG >= 2
2145 WARN_ON(1);
2146#endif
2147 }
2148 }
2149}
2150
2151static int fib6_walk(struct net *net, struct fib6_walker *w)
2152{
2153 int res;
2154
2155 w->state = FWS_INIT;
2156 w->node = w->root;
2157
2158 fib6_walker_link(net, w);
2159 res = fib6_walk_continue(w);
2160 if (res <= 0)
2161 fib6_walker_unlink(net, w);
2162 return res;
2163}
2164
2165static int fib6_clean_node(struct fib6_walker *w)
2166{
2167 int res;
2168 struct fib6_info *rt;
2169 struct fib6_cleaner *c = container_of(w, struct fib6_cleaner, w);
2170 struct nl_info info = {
2171 .nl_net = c->net,
2172 .skip_notify = c->skip_notify,
2173 };
2174
2175 if (c->sernum != FIB6_NO_SERNUM_CHANGE &&
2176 w->node->fn_sernum != c->sernum)
2177 w->node->fn_sernum = c->sernum;
2178
2179 if (!c->func) {
2180 WARN_ON_ONCE(c->sernum == FIB6_NO_SERNUM_CHANGE);
2181 w->leaf = NULL;
2182 return 0;
2183 }
2184
2185 for_each_fib6_walker_rt(w) {
2186 res = c->func(rt, c->arg);
2187 if (res == -1) {
2188 w->leaf = rt;
2189 res = fib6_del(rt, &info);
2190 if (res) {
2191#if RT6_DEBUG >= 2
2192 pr_debug("%s: del failed: rt=%p@%p err=%d\n",
2193 __func__, rt,
2194 rcu_access_pointer(rt->fib6_node),
2195 res);
2196#endif
2197 continue;
2198 }
2199 return 0;
2200 } else if (res == -2) {
2201 if (WARN_ON(!rt->fib6_nsiblings))
2202 continue;
2203 rt = list_last_entry(&rt->fib6_siblings,
2204 struct fib6_info, fib6_siblings);
2205 continue;
2206 }
2207 WARN_ON(res != 0);
2208 }
2209 w->leaf = rt;
2210 return 0;
2211}
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222static void fib6_clean_tree(struct net *net, struct fib6_node *root,
2223 int (*func)(struct fib6_info *, void *arg),
2224 int sernum, void *arg, bool skip_notify)
2225{
2226 struct fib6_cleaner c;
2227
2228 c.w.root = root;
2229 c.w.func = fib6_clean_node;
2230 c.w.count = 0;
2231 c.w.skip = 0;
2232 c.w.skip_in_node = 0;
2233 c.func = func;
2234 c.sernum = sernum;
2235 c.arg = arg;
2236 c.net = net;
2237 c.skip_notify = skip_notify;
2238
2239 fib6_walk(net, &c.w);
2240}
2241
2242static void __fib6_clean_all(struct net *net,
2243 int (*func)(struct fib6_info *, void *),
2244 int sernum, void *arg, bool skip_notify)
2245{
2246 struct fib6_table *table;
2247 struct hlist_head *head;
2248 unsigned int h;
2249
2250 rcu_read_lock();
2251 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
2252 head = &net->ipv6.fib_table_hash[h];
2253 hlist_for_each_entry_rcu(table, head, tb6_hlist) {
2254 spin_lock_bh(&table->tb6_lock);
2255 fib6_clean_tree(net, &table->tb6_root,
2256 func, sernum, arg, skip_notify);
2257 spin_unlock_bh(&table->tb6_lock);
2258 }
2259 }
2260 rcu_read_unlock();
2261}
2262
2263void fib6_clean_all(struct net *net, int (*func)(struct fib6_info *, void *),
2264 void *arg)
2265{
2266 __fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, false);
2267}
2268
2269void fib6_clean_all_skip_notify(struct net *net,
2270 int (*func)(struct fib6_info *, void *),
2271 void *arg)
2272{
2273 __fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, true);
2274}
2275
2276static void fib6_flush_trees(struct net *net)
2277{
2278 int new_sernum = fib6_new_sernum(net);
2279
2280 __fib6_clean_all(net, NULL, new_sernum, NULL, false);
2281}
2282
2283
2284
2285
2286
2287static int fib6_age(struct fib6_info *rt, void *arg)
2288{
2289 struct fib6_gc_args *gc_args = arg;
2290 unsigned long now = jiffies;
2291
2292
2293
2294
2295
2296
2297 if (rt->fib6_flags & RTF_EXPIRES && rt->expires) {
2298 if (time_after(now, rt->expires)) {
2299 RT6_TRACE("expiring %p\n", rt);
2300 return -1;
2301 }
2302 gc_args->more++;
2303 }
2304
2305
2306
2307
2308
2309 rt6_age_exceptions(rt, gc_args, now);
2310
2311 return 0;
2312}
2313
2314void fib6_run_gc(unsigned long expires, struct net *net, bool force)
2315{
2316 struct fib6_gc_args gc_args;
2317 unsigned long now;
2318
2319 if (force) {
2320 spin_lock_bh(&net->ipv6.fib6_gc_lock);
2321 } else if (!spin_trylock_bh(&net->ipv6.fib6_gc_lock)) {
2322 mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
2323 return;
2324 }
2325 gc_args.timeout = expires ? (int)expires :
2326 net->ipv6.sysctl.ip6_rt_gc_interval;
2327 gc_args.more = 0;
2328
2329 fib6_clean_all(net, fib6_age, &gc_args);
2330 now = jiffies;
2331 net->ipv6.ip6_rt_last_gc = now;
2332
2333 if (gc_args.more)
2334 mod_timer(&net->ipv6.ip6_fib_timer,
2335 round_jiffies(now
2336 + net->ipv6.sysctl.ip6_rt_gc_interval));
2337 else
2338 del_timer(&net->ipv6.ip6_fib_timer);
2339 spin_unlock_bh(&net->ipv6.fib6_gc_lock);
2340}
2341
2342static void fib6_gc_timer_cb(struct timer_list *t)
2343{
2344 struct net *arg = from_timer(arg, t, ipv6.ip6_fib_timer);
2345
2346 fib6_run_gc(0, arg, true);
2347}
2348
2349static int __net_init fib6_net_init(struct net *net)
2350{
2351 size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
2352 int err;
2353
2354 err = fib6_notifier_init(net);
2355 if (err)
2356 return err;
2357
2358
2359 net->ipv6.sysctl.multipath_hash_fields =
2360 FIB_MULTIPATH_HASH_FIELD_DEFAULT_MASK;
2361
2362 spin_lock_init(&net->ipv6.fib6_gc_lock);
2363 rwlock_init(&net->ipv6.fib6_walker_lock);
2364 INIT_LIST_HEAD(&net->ipv6.fib6_walkers);
2365 timer_setup(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, 0);
2366
2367 net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
2368 if (!net->ipv6.rt6_stats)
2369 goto out_notifier;
2370
2371
2372 size = max_t(size_t, size, L1_CACHE_BYTES);
2373
2374 net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
2375 if (!net->ipv6.fib_table_hash)
2376 goto out_rt6_stats;
2377
2378 net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
2379 GFP_KERNEL);
2380 if (!net->ipv6.fib6_main_tbl)
2381 goto out_fib_table_hash;
2382
2383 net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
2384 rcu_assign_pointer(net->ipv6.fib6_main_tbl->tb6_root.leaf,
2385 net->ipv6.fib6_null_entry);
2386 net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
2387 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
2388 inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
2389
2390#ifdef CONFIG_IPV6_MULTIPLE_TABLES
2391 net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
2392 GFP_KERNEL);
2393 if (!net->ipv6.fib6_local_tbl)
2394 goto out_fib6_main_tbl;
2395 net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
2396 rcu_assign_pointer(net->ipv6.fib6_local_tbl->tb6_root.leaf,
2397 net->ipv6.fib6_null_entry);
2398 net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
2399 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
2400 inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
2401#endif
2402 fib6_tables_init(net);
2403
2404 return 0;
2405
2406#ifdef CONFIG_IPV6_MULTIPLE_TABLES
2407out_fib6_main_tbl:
2408 kfree(net->ipv6.fib6_main_tbl);
2409#endif
2410out_fib_table_hash:
2411 kfree(net->ipv6.fib_table_hash);
2412out_rt6_stats:
2413 kfree(net->ipv6.rt6_stats);
2414out_notifier:
2415 fib6_notifier_exit(net);
2416 return -ENOMEM;
2417}
2418
2419static void fib6_net_exit(struct net *net)
2420{
2421 unsigned int i;
2422
2423 del_timer_sync(&net->ipv6.ip6_fib_timer);
2424
2425 for (i = 0; i < FIB6_TABLE_HASHSZ; i++) {
2426 struct hlist_head *head = &net->ipv6.fib_table_hash[i];
2427 struct hlist_node *tmp;
2428 struct fib6_table *tb;
2429
2430 hlist_for_each_entry_safe(tb, tmp, head, tb6_hlist) {
2431 hlist_del(&tb->tb6_hlist);
2432 fib6_free_table(tb);
2433 }
2434 }
2435
2436 kfree(net->ipv6.fib_table_hash);
2437 kfree(net->ipv6.rt6_stats);
2438 fib6_notifier_exit(net);
2439}
2440
2441static struct pernet_operations fib6_net_ops = {
2442 .init = fib6_net_init,
2443 .exit = fib6_net_exit,
2444};
2445
2446int __init fib6_init(void)
2447{
2448 int ret = -ENOMEM;
2449
2450 fib6_node_kmem = kmem_cache_create("fib6_nodes",
2451 sizeof(struct fib6_node), 0,
2452 SLAB_HWCACHE_ALIGN | SLAB_ACCOUNT,
2453 NULL);
2454 if (!fib6_node_kmem)
2455 goto out;
2456
2457 ret = register_pernet_subsys(&fib6_net_ops);
2458 if (ret)
2459 goto out_kmem_cache_create;
2460
2461 ret = rtnl_register_module(THIS_MODULE, PF_INET6, RTM_GETROUTE, NULL,
2462 inet6_dump_fib, 0);
2463 if (ret)
2464 goto out_unregister_subsys;
2465
2466 __fib6_flush_trees = fib6_flush_trees;
2467out:
2468 return ret;
2469
2470out_unregister_subsys:
2471 unregister_pernet_subsys(&fib6_net_ops);
2472out_kmem_cache_create:
2473 kmem_cache_destroy(fib6_node_kmem);
2474 goto out;
2475}
2476
2477void fib6_gc_cleanup(void)
2478{
2479 unregister_pernet_subsys(&fib6_net_ops);
2480 kmem_cache_destroy(fib6_node_kmem);
2481}
2482
2483#ifdef CONFIG_PROC_FS
2484static int ipv6_route_native_seq_show(struct seq_file *seq, void *v)
2485{
2486 struct fib6_info *rt = v;
2487 struct ipv6_route_iter *iter = seq->private;
2488 struct fib6_nh *fib6_nh = rt->fib6_nh;
2489 unsigned int flags = rt->fib6_flags;
2490 const struct net_device *dev;
2491
2492 if (rt->nh)
2493 fib6_nh = nexthop_fib6_nh_bh(rt->nh);
2494
2495 seq_printf(seq, "%pi6 %02x ", &rt->fib6_dst.addr, rt->fib6_dst.plen);
2496
2497#ifdef CONFIG_IPV6_SUBTREES
2498 seq_printf(seq, "%pi6 %02x ", &rt->fib6_src.addr, rt->fib6_src.plen);
2499#else
2500 seq_puts(seq, "00000000000000000000000000000000 00 ");
2501#endif
2502 if (fib6_nh->fib_nh_gw_family) {
2503 flags |= RTF_GATEWAY;
2504 seq_printf(seq, "%pi6", &fib6_nh->fib_nh_gw6);
2505 } else {
2506 seq_puts(seq, "00000000000000000000000000000000");
2507 }
2508
2509 dev = fib6_nh->fib_nh_dev;
2510 seq_printf(seq, " %08x %08x %08x %08x %8s\n",
2511 rt->fib6_metric, refcount_read(&rt->fib6_ref), 0,
2512 flags, dev ? dev->name : "");
2513 iter->w.leaf = NULL;
2514 return 0;
2515}
2516
2517static int ipv6_route_yield(struct fib6_walker *w)
2518{
2519 struct ipv6_route_iter *iter = w->args;
2520
2521 if (!iter->skip)
2522 return 1;
2523
2524 do {
2525 iter->w.leaf = rcu_dereference_protected(
2526 iter->w.leaf->fib6_next,
2527 lockdep_is_held(&iter->tbl->tb6_lock));
2528 iter->skip--;
2529 if (!iter->skip && iter->w.leaf)
2530 return 1;
2531 } while (iter->w.leaf);
2532
2533 return 0;
2534}
2535
2536static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter,
2537 struct net *net)
2538{
2539 memset(&iter->w, 0, sizeof(iter->w));
2540 iter->w.func = ipv6_route_yield;
2541 iter->w.root = &iter->tbl->tb6_root;
2542 iter->w.state = FWS_INIT;
2543 iter->w.node = iter->w.root;
2544 iter->w.args = iter;
2545 iter->sernum = iter->w.root->fn_sernum;
2546 INIT_LIST_HEAD(&iter->w.lh);
2547 fib6_walker_link(net, &iter->w);
2548}
2549
2550static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
2551 struct net *net)
2552{
2553 unsigned int h;
2554 struct hlist_node *node;
2555
2556 if (tbl) {
2557 h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
2558 node = rcu_dereference_bh(hlist_next_rcu(&tbl->tb6_hlist));
2559 } else {
2560 h = 0;
2561 node = NULL;
2562 }
2563
2564 while (!node && h < FIB6_TABLE_HASHSZ) {
2565 node = rcu_dereference_bh(
2566 hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
2567 }
2568 return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
2569}
2570
2571static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
2572{
2573 if (iter->sernum != iter->w.root->fn_sernum) {
2574 iter->sernum = iter->w.root->fn_sernum;
2575 iter->w.state = FWS_INIT;
2576 iter->w.node = iter->w.root;
2577 WARN_ON(iter->w.skip);
2578 iter->w.skip = iter->w.count;
2579 }
2580}
2581
2582static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2583{
2584 int r;
2585 struct fib6_info *n;
2586 struct net *net = seq_file_net(seq);
2587 struct ipv6_route_iter *iter = seq->private;
2588
2589 ++(*pos);
2590 if (!v)
2591 goto iter_table;
2592
2593 n = rcu_dereference_bh(((struct fib6_info *)v)->fib6_next);
2594 if (n)
2595 return n;
2596
2597iter_table:
2598 ipv6_route_check_sernum(iter);
2599 spin_lock_bh(&iter->tbl->tb6_lock);
2600 r = fib6_walk_continue(&iter->w);
2601 spin_unlock_bh(&iter->tbl->tb6_lock);
2602 if (r > 0) {
2603 return iter->w.leaf;
2604 } else if (r < 0) {
2605 fib6_walker_unlink(net, &iter->w);
2606 return NULL;
2607 }
2608 fib6_walker_unlink(net, &iter->w);
2609
2610 iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
2611 if (!iter->tbl)
2612 return NULL;
2613
2614 ipv6_route_seq_setup_walk(iter, net);
2615 goto iter_table;
2616}
2617
2618static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
2619 __acquires(RCU_BH)
2620{
2621 struct net *net = seq_file_net(seq);
2622 struct ipv6_route_iter *iter = seq->private;
2623
2624 rcu_read_lock_bh();
2625 iter->tbl = ipv6_route_seq_next_table(NULL, net);
2626 iter->skip = *pos;
2627
2628 if (iter->tbl) {
2629 loff_t p = 0;
2630
2631 ipv6_route_seq_setup_walk(iter, net);
2632 return ipv6_route_seq_next(seq, NULL, &p);
2633 } else {
2634 return NULL;
2635 }
2636}
2637
2638static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
2639{
2640 struct fib6_walker *w = &iter->w;
2641 return w->node && !(w->state == FWS_U && w->node == w->root);
2642}
2643
2644static void ipv6_route_native_seq_stop(struct seq_file *seq, void *v)
2645 __releases(RCU_BH)
2646{
2647 struct net *net = seq_file_net(seq);
2648 struct ipv6_route_iter *iter = seq->private;
2649
2650 if (ipv6_route_iter_active(iter))
2651 fib6_walker_unlink(net, &iter->w);
2652
2653 rcu_read_unlock_bh();
2654}
2655
2656#if IS_BUILTIN(CONFIG_IPV6) && defined(CONFIG_BPF_SYSCALL)
2657static int ipv6_route_prog_seq_show(struct bpf_prog *prog,
2658 struct bpf_iter_meta *meta,
2659 void *v)
2660{
2661 struct bpf_iter__ipv6_route ctx;
2662
2663 ctx.meta = meta;
2664 ctx.rt = v;
2665 return bpf_iter_run_prog(prog, &ctx);
2666}
2667
2668static int ipv6_route_seq_show(struct seq_file *seq, void *v)
2669{
2670 struct ipv6_route_iter *iter = seq->private;
2671 struct bpf_iter_meta meta;
2672 struct bpf_prog *prog;
2673 int ret;
2674
2675 meta.seq = seq;
2676 prog = bpf_iter_get_info(&meta, false);
2677 if (!prog)
2678 return ipv6_route_native_seq_show(seq, v);
2679
2680 ret = ipv6_route_prog_seq_show(prog, &meta, v);
2681 iter->w.leaf = NULL;
2682
2683 return ret;
2684}
2685
2686static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
2687{
2688 struct bpf_iter_meta meta;
2689 struct bpf_prog *prog;
2690
2691 if (!v) {
2692 meta.seq = seq;
2693 prog = bpf_iter_get_info(&meta, true);
2694 if (prog)
2695 (void)ipv6_route_prog_seq_show(prog, &meta, v);
2696 }
2697
2698 ipv6_route_native_seq_stop(seq, v);
2699}
2700#else
2701static int ipv6_route_seq_show(struct seq_file *seq, void *v)
2702{
2703 return ipv6_route_native_seq_show(seq, v);
2704}
2705
2706static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
2707{
2708 ipv6_route_native_seq_stop(seq, v);
2709}
2710#endif
2711
2712const struct seq_operations ipv6_route_seq_ops = {
2713 .start = ipv6_route_seq_start,
2714 .next = ipv6_route_seq_next,
2715 .stop = ipv6_route_seq_stop,
2716 .show = ipv6_route_seq_show
2717};
2718#endif
2719