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