?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
dm writecache: fix incorrect flush sequence when doing SSD mode commit
[linux/fpc-iii.git] / net / ipv6 / ip6_fib.c
blob7bae6a91b48726173ef285e0449a4bcb29d75993
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * Linux INET6 implementation
4 * Forwarding Information Database
5 *
6 * Authors:
7 * Pedro Roque <roque@di.fc.ul.pt>
8 *
9 * Changes:
10 * Yuji SEKIYA @USAGI: Support default route on router node;
11 * remove ip6_null_entry from the top of
12 * routing table.
13 * Ville Nuorvala: Fixed routing subtrees.
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 * A routing update causes an increase of the serial number on the
66 * affected subtree. This allows for cached routes to be asynchronously
67 * tested when modifications are made to the destination cache as a
68 * result of redirects, path MTU changes, etc.
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 * Auxiliary address test functions for the radix tree.
118 *
119 * These assume a 32bit processor (although it will work on
120 * 64bit processors)
121 */
122
123 /*
124 * test bit
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 * Here,
137 * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
138 * is optimized version of
139 * htonl(1 << ((~fn_bit)&0x1F))
140 * See include/asm-generic/bitops/le.h.
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 /* fib6_siblings is a union with nh_list, so this initializes both */
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 * Initialize table lock at a single place to give lockdep a key,
223 * tables aren't visible prior to being linked to the list.
224 */
225 spin_lock_init(&tb->tb6_lock);
226 h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
227
228 /*
229 * No protection necessary, this is the only list mutatation
230 * operation, tables never disappear once they exist.
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 /* called with rcu lock held; no reference taken on fib6_info */
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,
361 enum fib_event_type event_type,
362 struct fib6_info *rt,
363 struct netlink_ext_ack *extack)
364 {
365 struct fib6_entry_notifier_info info = {
366 .info.extack = extack,
367 .rt = rt,
368 };
369
370 return call_fib6_notifier(nb, event_type, &info.info);
371 }
372
373 int call_fib6_entry_notifiers(struct net *net,
374 enum fib_event_type event_type,
375 struct fib6_info *rt,
376 struct netlink_ext_ack *extack)
377 {
378 struct fib6_entry_notifier_info info = {
379 .info.extack = extack,
380 .rt = rt,
381 };
382
383 rt->fib6_table->fib_seq++;
384 return call_fib6_notifiers(net, event_type, &info.info);
385 }
386
387 int call_fib6_multipath_entry_notifiers(struct net *net,
388 enum fib_event_type event_type,
389 struct fib6_info *rt,
390 unsigned int nsiblings,
391 struct netlink_ext_ack *extack)
392 {
393 struct fib6_entry_notifier_info info = {
394 .info.extack = extack,
395 .rt = rt,
396 .nsiblings = nsiblings,
397 };
398
399 rt->fib6_table->fib_seq++;
400 return call_fib6_notifiers(net, event_type, &info.info);
401 }
402
403 struct fib6_dump_arg {
404 struct net *net;
405 struct notifier_block *nb;
406 struct netlink_ext_ack *extack;
407 };
408
409 static int fib6_rt_dump(struct fib6_info *rt, struct fib6_dump_arg *arg)
410 {
411 if (rt == arg->net->ipv6.fib6_null_entry)
412 return 0;
413 return call_fib6_entry_notifier(arg->nb, FIB_EVENT_ENTRY_ADD,
414 rt, arg->extack);
415 }
416
417 static int fib6_node_dump(struct fib6_walker *w)
418 {
419 struct fib6_info *rt;
420 int err = 0;
421
422 for_each_fib6_walker_rt(w) {
423 err = fib6_rt_dump(rt, w->args);
424 if (err)
425 break;
426 }
427 w->leaf = NULL;
428 return err;
429 }
430
431 static int fib6_table_dump(struct net *net, struct fib6_table *tb,
432 struct fib6_walker *w)
433 {
434 int err;
435
436 w->root = &tb->tb6_root;
437 spin_lock_bh(&tb->tb6_lock);
438 err = fib6_walk(net, w);
439 spin_unlock_bh(&tb->tb6_lock);
440 return err;
441 }
442
443 /* Called with rcu_read_lock() */
444 int fib6_tables_dump(struct net *net, struct notifier_block *nb,
445 struct netlink_ext_ack *extack)
446 {
447 struct fib6_dump_arg arg;
448 struct fib6_walker *w;
449 unsigned int h;
450 int err = 0;
451
452 w = kzalloc(sizeof(*w), GFP_ATOMIC);
453 if (!w)
454 return -ENOMEM;
455
456 w->func = fib6_node_dump;
457 arg.net = net;
458 arg.nb = nb;
459 arg.extack = extack;
460 w->args = &arg;
461
462 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
463 struct hlist_head *head = &net->ipv6.fib_table_hash[h];
464 struct fib6_table *tb;
465
466 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
467 err = fib6_table_dump(net, tb, w);
468 if (err < 0)
469 goto out;
470 }
471 }
472
473 out:
474 kfree(w);
475
476 return err;
477 }
478
479 static int fib6_dump_node(struct fib6_walker *w)
480 {
481 int res;
482 struct fib6_info *rt;
483
484 for_each_fib6_walker_rt(w) {
485 res = rt6_dump_route(rt, w->args, w->skip_in_node);
486 if (res >= 0) {
487 /* Frame is full, suspend walking */
488 w->leaf = rt;
489
490 /* We'll restart from this node, so if some routes were
491 * already dumped, skip them next time.
492 */
493 w->skip_in_node += res;
494
495 return 1;
496 }
497 w->skip_in_node = 0;
498
499 /* Multipath routes are dumped in one route with the
500 * RTA_MULTIPATH attribute. Jump 'rt' to point to the
501 * last sibling of this route (no need to dump the
502 * sibling routes again)
503 */
504 if (rt->fib6_nsiblings)
505 rt = list_last_entry(&rt->fib6_siblings,
506 struct fib6_info,
507 fib6_siblings);
508 }
509 w->leaf = NULL;
510 return 0;
511 }
512
513 static void fib6_dump_end(struct netlink_callback *cb)
514 {
515 struct net *net = sock_net(cb->skb->sk);
516 struct fib6_walker *w = (void *)cb->args[2];
517
518 if (w) {
519 if (cb->args[4]) {
520 cb->args[4] = 0;
521 fib6_walker_unlink(net, w);
522 }
523 cb->args[2] = 0;
524 kfree(w);
525 }
526 cb->done = (void *)cb->args[3];
527 cb->args[1] = 3;
528 }
529
530 static int fib6_dump_done(struct netlink_callback *cb)
531 {
532 fib6_dump_end(cb);
533 return cb->done ? cb->done(cb) : 0;
534 }
535
536 static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
537 struct netlink_callback *cb)
538 {
539 struct net *net = sock_net(skb->sk);
540 struct fib6_walker *w;
541 int res;
542
543 w = (void *)cb->args[2];
544 w->root = &table->tb6_root;
545
546 if (cb->args[4] == 0) {
547 w->count = 0;
548 w->skip = 0;
549 w->skip_in_node = 0;
550
551 spin_lock_bh(&table->tb6_lock);
552 res = fib6_walk(net, w);
553 spin_unlock_bh(&table->tb6_lock);
554 if (res > 0) {
555 cb->args[4] = 1;
556 cb->args[5] = w->root->fn_sernum;
557 }
558 } else {
559 if (cb->args[5] != w->root->fn_sernum) {
560 /* Begin at the root if the tree changed */
561 cb->args[5] = w->root->fn_sernum;
562 w->state = FWS_INIT;
563 w->node = w->root;
564 w->skip = w->count;
565 w->skip_in_node = 0;
566 } else
567 w->skip = 0;
568
569 spin_lock_bh(&table->tb6_lock);
570 res = fib6_walk_continue(w);
571 spin_unlock_bh(&table->tb6_lock);
572 if (res <= 0) {
573 fib6_walker_unlink(net, w);
574 cb->args[4] = 0;
575 }
576 }
577
578 return res;
579 }
580
581 static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
582 {
583 struct rt6_rtnl_dump_arg arg = { .filter.dump_exceptions = true,
584 .filter.dump_routes = true };
585 const struct nlmsghdr *nlh = cb->nlh;
586 struct net *net = sock_net(skb->sk);
587 unsigned int h, s_h;
588 unsigned int e = 0, s_e;
589 struct fib6_walker *w;
590 struct fib6_table *tb;
591 struct hlist_head *head;
592 int res = 0;
593
594 if (cb->strict_check) {
595 int err;
596
597 err = ip_valid_fib_dump_req(net, nlh, &arg.filter, cb);
598 if (err < 0)
599 return err;
600 } else if (nlmsg_len(nlh) >= sizeof(struct rtmsg)) {
601 struct rtmsg *rtm = nlmsg_data(nlh);
602
603 if (rtm->rtm_flags & RTM_F_PREFIX)
604 arg.filter.flags = RTM_F_PREFIX;
605 }
606
607 w = (void *)cb->args[2];
608 if (!w) {
609 /* New dump:
610 *
611 * 1. hook callback destructor.
612 */
613 cb->args[3] = (long)cb->done;
614 cb->done = fib6_dump_done;
615
616 /*
617 * 2. allocate and initialize walker.
618 */
619 w = kzalloc(sizeof(*w), GFP_ATOMIC);
620 if (!w)
621 return -ENOMEM;
622 w->func = fib6_dump_node;
623 cb->args[2] = (long)w;
624 }
625
626 arg.skb = skb;
627 arg.cb = cb;
628 arg.net = net;
629 w->args = &arg;
630
631 if (arg.filter.table_id) {
632 tb = fib6_get_table(net, arg.filter.table_id);
633 if (!tb) {
634 if (arg.filter.dump_all_families)
635 goto out;
636
637 NL_SET_ERR_MSG_MOD(cb->extack, "FIB table does not exist");
638 return -ENOENT;
639 }
640
641 if (!cb->args[0]) {
642 res = fib6_dump_table(tb, skb, cb);
643 if (!res)
644 cb->args[0] = 1;
645 }
646 goto out;
647 }
648
649 s_h = cb->args[0];
650 s_e = cb->args[1];
651
652 rcu_read_lock();
653 for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
654 e = 0;
655 head = &net->ipv6.fib_table_hash[h];
656 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
657 if (e < s_e)
658 goto next;
659 res = fib6_dump_table(tb, skb, cb);
660 if (res != 0)
661 goto out_unlock;
662 next:
663 e++;
664 }
665 }
666 out_unlock:
667 rcu_read_unlock();
668 cb->args[1] = e;
669 cb->args[0] = h;
670 out:
671 res = res < 0 ? res : skb->len;
672 if (res <= 0)
673 fib6_dump_end(cb);
674 return res;
675 }
676
677 void fib6_metric_set(struct fib6_info *f6i, int metric, u32 val)
678 {
679 if (!f6i)
680 return;
681
682 if (f6i->fib6_metrics == &dst_default_metrics) {
683 struct dst_metrics *p = kzalloc(sizeof(*p), GFP_ATOMIC);
684
685 if (!p)
686 return;
687
688 refcount_set(&p->refcnt, 1);
689 f6i->fib6_metrics = p;
690 }
691
692 f6i->fib6_metrics->metrics[metric - 1] = val;
693 }
694
695 /*
696 * Routing Table
697 *
698 * return the appropriate node for a routing tree "add" operation
699 * by either creating and inserting or by returning an existing
700 * node.
701 */
702
703 static struct fib6_node *fib6_add_1(struct net *net,
704 struct fib6_table *table,
705 struct fib6_node *root,
706 struct in6_addr *addr, int plen,
707 int offset, int allow_create,
708 int replace_required,
709 struct netlink_ext_ack *extack)
710 {
711 struct fib6_node *fn, *in, *ln;
712 struct fib6_node *pn = NULL;
713 struct rt6key *key;
714 int bit;
715 __be32 dir = 0;
716
717 RT6_TRACE("fib6_add_1\n");
718
719 /* insert node in tree */
720
721 fn = root;
722
723 do {
724 struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
725 lockdep_is_held(&table->tb6_lock));
726 key = (struct rt6key *)((u8 *)leaf + offset);
727
728 /*
729 * Prefix match
730 */
731 if (plen < fn->fn_bit ||
732 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
733 if (!allow_create) {
734 if (replace_required) {
735 NL_SET_ERR_MSG(extack,
736 "Can not replace route - no match found");
737 pr_warn("Can't replace route, no match found\n");
738 return ERR_PTR(-ENOENT);
739 }
740 pr_warn("NLM_F_CREATE should be set when creating new route\n");
741 }
742 goto insert_above;
743 }
744
745 /*
746 * Exact match ?
747 */
748
749 if (plen == fn->fn_bit) {
750 /* clean up an intermediate node */
751 if (!(fn->fn_flags & RTN_RTINFO)) {
752 RCU_INIT_POINTER(fn->leaf, NULL);
753 fib6_info_release(leaf);
754 /* remove null_entry in the root node */
755 } else if (fn->fn_flags & RTN_TL_ROOT &&
756 rcu_access_pointer(fn->leaf) ==
757 net->ipv6.fib6_null_entry) {
758 RCU_INIT_POINTER(fn->leaf, NULL);
759 }
760
761 return fn;
762 }
763
764 /*
765 * We have more bits to go
766 */
767
768 /* Try to walk down on tree. */
769 dir = addr_bit_set(addr, fn->fn_bit);
770 pn = fn;
771 fn = dir ?
772 rcu_dereference_protected(fn->right,
773 lockdep_is_held(&table->tb6_lock)) :
774 rcu_dereference_protected(fn->left,
775 lockdep_is_held(&table->tb6_lock));
776 } while (fn);
777
778 if (!allow_create) {
779 /* We should not create new node because
780 * NLM_F_REPLACE was specified without NLM_F_CREATE
781 * I assume it is safe to require NLM_F_CREATE when
782 * REPLACE flag is used! Later we may want to remove the
783 * check for replace_required, because according
784 * to netlink specification, NLM_F_CREATE
785 * MUST be specified if new route is created.
786 * That would keep IPv6 consistent with IPv4
787 */
788 if (replace_required) {
789 NL_SET_ERR_MSG(extack,
790 "Can not replace route - no match found");
791 pr_warn("Can't replace route, no match found\n");
792 return ERR_PTR(-ENOENT);
793 }
794 pr_warn("NLM_F_CREATE should be set when creating new route\n");
795 }
796 /*
797 * We walked to the bottom of tree.
798 * Create new leaf node without children.
799 */
800
801 ln = node_alloc(net);
802
803 if (!ln)
804 return ERR_PTR(-ENOMEM);
805 ln->fn_bit = plen;
806 RCU_INIT_POINTER(ln->parent, pn);
807
808 if (dir)
809 rcu_assign_pointer(pn->right, ln);
810 else
811 rcu_assign_pointer(pn->left, ln);
812
813 return ln;
814
815
816 insert_above:
817 /*
818 * split since we don't have a common prefix anymore or
819 * we have a less significant route.
820 * we've to insert an intermediate node on the list
821 * this new node will point to the one we need to create
822 * and the current
823 */
824
825 pn = rcu_dereference_protected(fn->parent,
826 lockdep_is_held(&table->tb6_lock));
827
828 /* find 1st bit in difference between the 2 addrs.
829
830 See comment in __ipv6_addr_diff: bit may be an invalid value,
831 but if it is >= plen, the value is ignored in any case.
832 */
833
834 bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
835
836 /*
837 * (intermediate)[in]
838 * / \
839 * (new leaf node)[ln] (old node)[fn]
840 */
841 if (plen > bit) {
842 in = node_alloc(net);
843 ln = node_alloc(net);
844
845 if (!in || !ln) {
846 if (in)
847 node_free_immediate(net, in);
848 if (ln)
849 node_free_immediate(net, ln);
850 return ERR_PTR(-ENOMEM);
851 }
852
853 /*
854 * new intermediate node.
855 * RTN_RTINFO will
856 * be off since that an address that chooses one of
857 * the branches would not match less specific routes
858 * in the other branch
859 */
860
861 in->fn_bit = bit;
862
863 RCU_INIT_POINTER(in->parent, pn);
864 in->leaf = fn->leaf;
865 fib6_info_hold(rcu_dereference_protected(in->leaf,
866 lockdep_is_held(&table->tb6_lock)));
867
868 /* update parent pointer */
869 if (dir)
870 rcu_assign_pointer(pn->right, in);
871 else
872 rcu_assign_pointer(pn->left, in);
873
874 ln->fn_bit = plen;
875
876 RCU_INIT_POINTER(ln->parent, in);
877 rcu_assign_pointer(fn->parent, in);
878
879 if (addr_bit_set(addr, bit)) {
880 rcu_assign_pointer(in->right, ln);
881 rcu_assign_pointer(in->left, fn);
882 } else {
883 rcu_assign_pointer(in->left, ln);
884 rcu_assign_pointer(in->right, fn);
885 }
886 } else { /* plen <= bit */
887
888 /*
889 * (new leaf node)[ln]
890 * / \
891 * (old node)[fn] NULL
892 */
893
894 ln = node_alloc(net);
895
896 if (!ln)
897 return ERR_PTR(-ENOMEM);
898
899 ln->fn_bit = plen;
900
901 RCU_INIT_POINTER(ln->parent, pn);
902
903 if (addr_bit_set(&key->addr, plen))
904 RCU_INIT_POINTER(ln->right, fn);
905 else
906 RCU_INIT_POINTER(ln->left, fn);
907
908 rcu_assign_pointer(fn->parent, ln);
909
910 if (dir)
911 rcu_assign_pointer(pn->right, ln);
912 else
913 rcu_assign_pointer(pn->left, ln);
914 }
915 return ln;
916 }
917
918 static void __fib6_drop_pcpu_from(struct fib6_nh *fib6_nh,
919 const struct fib6_info *match,
920 const struct fib6_table *table)
921 {
922 int cpu;
923
924 if (!fib6_nh->rt6i_pcpu)
925 return;
926
927 /* release the reference to this fib entry from
928 * all of its cached pcpu routes
929 */
930 for_each_possible_cpu(cpu) {
931 struct rt6_info **ppcpu_rt;
932 struct rt6_info *pcpu_rt;
933
934 ppcpu_rt = per_cpu_ptr(fib6_nh->rt6i_pcpu, cpu);
935 pcpu_rt = *ppcpu_rt;
936
937 /* only dropping the 'from' reference if the cached route
938 * is using 'match'. The cached pcpu_rt->from only changes
939 * from a fib6_info to NULL (ip6_dst_destroy); it can never
940 * change from one fib6_info reference to another
941 */
942 if (pcpu_rt && rcu_access_pointer(pcpu_rt->from) == match) {
943 struct fib6_info *from;
944
945 from = xchg((__force struct fib6_info **)&pcpu_rt->from, NULL);
946 fib6_info_release(from);
947 }
948 }
949 }
950
951 struct fib6_nh_pcpu_arg {
952 struct fib6_info *from;
953 const struct fib6_table *table;
954 };
955
956 static int fib6_nh_drop_pcpu_from(struct fib6_nh *nh, void *_arg)
957 {
958 struct fib6_nh_pcpu_arg *arg = _arg;
959
960 __fib6_drop_pcpu_from(nh, arg->from, arg->table);
961 return 0;
962 }
963
964 static void fib6_drop_pcpu_from(struct fib6_info *f6i,
965 const struct fib6_table *table)
966 {
967 /* Make sure rt6_make_pcpu_route() wont add other percpu routes
968 * while we are cleaning them here.
969 */
970 f6i->fib6_destroying = 1;
971 mb(); /* paired with the cmpxchg() in rt6_make_pcpu_route() */
972
973 if (f6i->nh) {
974 struct fib6_nh_pcpu_arg arg = {
975 .from = f6i,
976 .table = table
977 };
978
979 nexthop_for_each_fib6_nh(f6i->nh, fib6_nh_drop_pcpu_from,
980 &arg);
981 } else {
982 struct fib6_nh *fib6_nh;
983
984 fib6_nh = f6i->fib6_nh;
985 __fib6_drop_pcpu_from(fib6_nh, f6i, table);
986 }
987 }
988
989 static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,
990 struct net *net)
991 {
992 struct fib6_table *table = rt->fib6_table;
993
994 fib6_drop_pcpu_from(rt, table);
995
996 if (rt->nh && !list_empty(&rt->nh_list))
997 list_del_init(&rt->nh_list);
998
999 if (refcount_read(&rt->fib6_ref) != 1) {
1000 /* This route is used as dummy address holder in some split
1001 * nodes. It is not leaked, but it still holds other resources,
1002 * which must be released in time. So, scan ascendant nodes
1003 * and replace dummy references to this route with references
1004 * to still alive ones.
1005 */
1006 while (fn) {
1007 struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
1008 lockdep_is_held(&table->tb6_lock));
1009 struct fib6_info *new_leaf;
1010 if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {
1011 new_leaf = fib6_find_prefix(net, table, fn);
1012 fib6_info_hold(new_leaf);
1013
1014 rcu_assign_pointer(fn->leaf, new_leaf);
1015 fib6_info_release(rt);
1016 }
1017 fn = rcu_dereference_protected(fn->parent,
1018 lockdep_is_held(&table->tb6_lock));
1019 }
1020 }
1021 }
1022
1023 /*
1024 * Insert routing information in a node.
1025 */
1026
1027 static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,
1028 struct nl_info *info,
1029 struct netlink_ext_ack *extack)
1030 {
1031 struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
1032 lockdep_is_held(&rt->fib6_table->tb6_lock));
1033 struct fib6_info *iter = NULL;
1034 struct fib6_info __rcu **ins;
1035 struct fib6_info __rcu **fallback_ins = NULL;
1036 int replace = (info->nlh &&
1037 (info->nlh->nlmsg_flags & NLM_F_REPLACE));
1038 int add = (!info->nlh ||
1039 (info->nlh->nlmsg_flags & NLM_F_CREATE));
1040 int found = 0;
1041 bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
1042 u16 nlflags = NLM_F_EXCL;
1043 int err;
1044
1045 if (info->nlh && (info->nlh->nlmsg_flags & NLM_F_APPEND))
1046 nlflags |= NLM_F_APPEND;
1047
1048 ins = &fn->leaf;
1049
1050 for (iter = leaf; iter;
1051 iter = rcu_dereference_protected(iter->fib6_next,
1052 lockdep_is_held(&rt->fib6_table->tb6_lock))) {
1053 /*
1054 * Search for duplicates
1055 */
1056
1057 if (iter->fib6_metric == rt->fib6_metric) {
1058 /*
1059 * Same priority level
1060 */
1061 if (info->nlh &&
1062 (info->nlh->nlmsg_flags & NLM_F_EXCL))
1063 return -EEXIST;
1064
1065 nlflags &= ~NLM_F_EXCL;
1066 if (replace) {
1067 if (rt_can_ecmp == rt6_qualify_for_ecmp(iter)) {
1068 found++;
1069 break;
1070 }
1071 if (rt_can_ecmp)
1072 fallback_ins = fallback_ins ?: ins;
1073 goto next_iter;
1074 }
1075
1076 if (rt6_duplicate_nexthop(iter, rt)) {
1077 if (rt->fib6_nsiblings)
1078 rt->fib6_nsiblings = 0;
1079 if (!(iter->fib6_flags & RTF_EXPIRES))
1080 return -EEXIST;
1081 if (!(rt->fib6_flags & RTF_EXPIRES))
1082 fib6_clean_expires(iter);
1083 else
1084 fib6_set_expires(iter, rt->expires);
1085
1086 if (rt->fib6_pmtu)
1087 fib6_metric_set(iter, RTAX_MTU,
1088 rt->fib6_pmtu);
1089 return -EEXIST;
1090 }
1091 /* If we have the same destination and the same metric,
1092 * but not the same gateway, then the route we try to
1093 * add is sibling to this route, increment our counter
1094 * of siblings, and later we will add our route to the
1095 * list.
1096 * Only static routes (which don't have flag
1097 * RTF_EXPIRES) are used for ECMPv6.
1098 *
1099 * To avoid long list, we only had siblings if the
1100 * route have a gateway.
1101 */
1102 if (rt_can_ecmp &&
1103 rt6_qualify_for_ecmp(iter))
1104 rt->fib6_nsiblings++;
1105 }
1106
1107 if (iter->fib6_metric > rt->fib6_metric)
1108 break;
1109
1110 next_iter:
1111 ins = &iter->fib6_next;
1112 }
1113
1114 if (fallback_ins && !found) {
1115 /* No ECMP-able route found, replace first non-ECMP one */
1116 ins = fallback_ins;
1117 iter = rcu_dereference_protected(*ins,
1118 lockdep_is_held(&rt->fib6_table->tb6_lock));
1119 found++;
1120 }
1121
1122 /* Reset round-robin state, if necessary */
1123 if (ins == &fn->leaf)
1124 fn->rr_ptr = NULL;
1125
1126 /* Link this route to others same route. */
1127 if (rt->fib6_nsiblings) {
1128 unsigned int fib6_nsiblings;
1129 struct fib6_info *sibling, *temp_sibling;
1130
1131 /* Find the first route that have the same metric */
1132 sibling = leaf;
1133 while (sibling) {
1134 if (sibling->fib6_metric == rt->fib6_metric &&
1135 rt6_qualify_for_ecmp(sibling)) {
1136 list_add_tail(&rt->fib6_siblings,
1137 &sibling->fib6_siblings);
1138 break;
1139 }
1140 sibling = rcu_dereference_protected(sibling->fib6_next,
1141 lockdep_is_held(&rt->fib6_table->tb6_lock));
1142 }
1143 /* For each sibling in the list, increment the counter of
1144 * siblings. BUG() if counters does not match, list of siblings
1145 * is broken!
1146 */
1147 fib6_nsiblings = 0;
1148 list_for_each_entry_safe(sibling, temp_sibling,
1149 &rt->fib6_siblings, fib6_siblings) {
1150 sibling->fib6_nsiblings++;
1151 BUG_ON(sibling->fib6_nsiblings != rt->fib6_nsiblings);
1152 fib6_nsiblings++;
1153 }
1154 BUG_ON(fib6_nsiblings != rt->fib6_nsiblings);
1155 rt6_multipath_rebalance(temp_sibling);
1156 }
1157
1158 /*
1159 * insert node
1160 */
1161 if (!replace) {
1162 if (!add)
1163 pr_warn("NLM_F_CREATE should be set when creating new route\n");
1164
1165 add:
1166 nlflags |= NLM_F_CREATE;
1167
1168 if (!info->skip_notify_kernel) {
1169 err = call_fib6_entry_notifiers(info->nl_net,
1170 FIB_EVENT_ENTRY_ADD,
1171 rt, extack);
1172 if (err) {
1173 struct fib6_info *sibling, *next_sibling;
1174
1175 /* If the route has siblings, then it first
1176 * needs to be unlinked from them.
1177 */
1178 if (!rt->fib6_nsiblings)
1179 return err;
1180
1181 list_for_each_entry_safe(sibling, next_sibling,
1182 &rt->fib6_siblings,
1183 fib6_siblings)
1184 sibling->fib6_nsiblings--;
1185 rt->fib6_nsiblings = 0;
1186 list_del_init(&rt->fib6_siblings);
1187 rt6_multipath_rebalance(next_sibling);
1188 return err;
1189 }
1190 }
1191
1192 rcu_assign_pointer(rt->fib6_next, iter);
1193 fib6_info_hold(rt);
1194 rcu_assign_pointer(rt->fib6_node, fn);
1195 rcu_assign_pointer(*ins, rt);
1196 if (!info->skip_notify)
1197 inet6_rt_notify(RTM_NEWROUTE, rt, info, nlflags);
1198 info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
1199
1200 if (!(fn->fn_flags & RTN_RTINFO)) {
1201 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
1202 fn->fn_flags |= RTN_RTINFO;
1203 }
1204
1205 } else {
1206 int nsiblings;
1207
1208 if (!found) {
1209 if (add)
1210 goto add;
1211 pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
1212 return -ENOENT;
1213 }
1214
1215 if (!info->skip_notify_kernel) {
1216 err = call_fib6_entry_notifiers(info->nl_net,
1217 FIB_EVENT_ENTRY_REPLACE,
1218 rt, extack);
1219 if (err)
1220 return err;
1221 }
1222
1223 fib6_info_hold(rt);
1224 rcu_assign_pointer(rt->fib6_node, fn);
1225 rt->fib6_next = iter->fib6_next;
1226 rcu_assign_pointer(*ins, rt);
1227 if (!info->skip_notify)
1228 inet6_rt_notify(RTM_NEWROUTE, rt, info, NLM_F_REPLACE);
1229 if (!(fn->fn_flags & RTN_RTINFO)) {
1230 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
1231 fn->fn_flags |= RTN_RTINFO;
1232 }
1233 nsiblings = iter->fib6_nsiblings;
1234 iter->fib6_node = NULL;
1235 fib6_purge_rt(iter, fn, info->nl_net);
1236 if (rcu_access_pointer(fn->rr_ptr) == iter)
1237 fn->rr_ptr = NULL;
1238 fib6_info_release(iter);
1239
1240 if (nsiblings) {
1241 /* Replacing an ECMP route, remove all siblings */
1242 ins = &rt->fib6_next;
1243 iter = rcu_dereference_protected(*ins,
1244 lockdep_is_held(&rt->fib6_table->tb6_lock));
1245 while (iter) {
1246 if (iter->fib6_metric > rt->fib6_metric)
1247 break;
1248 if (rt6_qualify_for_ecmp(iter)) {
1249 *ins = iter->fib6_next;
1250 iter->fib6_node = NULL;
1251 fib6_purge_rt(iter, fn, info->nl_net);
1252 if (rcu_access_pointer(fn->rr_ptr) == iter)
1253 fn->rr_ptr = NULL;
1254 fib6_info_release(iter);
1255 nsiblings--;
1256 info->nl_net->ipv6.rt6_stats->fib_rt_entries--;
1257 } else {
1258 ins = &iter->fib6_next;
1259 }
1260 iter = rcu_dereference_protected(*ins,
1261 lockdep_is_held(&rt->fib6_table->tb6_lock));
1262 }
1263 WARN_ON(nsiblings != 0);
1264 }
1265 }
1266
1267 return 0;
1268 }
1269
1270 static void fib6_start_gc(struct net *net, struct fib6_info *rt)
1271 {
1272 if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
1273 (rt->fib6_flags & RTF_EXPIRES))
1274 mod_timer(&net->ipv6.ip6_fib_timer,
1275 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
1276 }
1277
1278 void fib6_force_start_gc(struct net *net)
1279 {
1280 if (!timer_pending(&net->ipv6.ip6_fib_timer))
1281 mod_timer(&net->ipv6.ip6_fib_timer,
1282 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
1283 }
1284
1285 static void __fib6_update_sernum_upto_root(struct fib6_info *rt,
1286 int sernum)
1287 {
1288 struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,
1289 lockdep_is_held(&rt->fib6_table->tb6_lock));
1290
1291 /* paired with smp_rmb() in rt6_get_cookie_safe() */
1292 smp_wmb();
1293 while (fn) {
1294 fn->fn_sernum = sernum;
1295 fn = rcu_dereference_protected(fn->parent,
1296 lockdep_is_held(&rt->fib6_table->tb6_lock));
1297 }
1298 }
1299
1300 void fib6_update_sernum_upto_root(struct net *net, struct fib6_info *rt)
1301 {
1302 __fib6_update_sernum_upto_root(rt, fib6_new_sernum(net));
1303 }
1304
1305 /* allow ipv4 to update sernum via ipv6_stub */
1306 void fib6_update_sernum_stub(struct net *net, struct fib6_info *f6i)
1307 {
1308 spin_lock_bh(&f6i->fib6_table->tb6_lock);
1309 fib6_update_sernum_upto_root(net, f6i);
1310 spin_unlock_bh(&f6i->fib6_table->tb6_lock);
1311 }
1312
1313 /*
1314 * Add routing information to the routing tree.
1315 * <destination addr>/<source addr>
1316 * with source addr info in sub-trees
1317 * Need to own table->tb6_lock
1318 */
1319
1320 int fib6_add(struct fib6_node *root, struct fib6_info *rt,
1321 struct nl_info *info, struct netlink_ext_ack *extack)
1322 {
1323 struct fib6_table *table = rt->fib6_table;
1324 struct fib6_node *fn, *pn = NULL;
1325 int err = -ENOMEM;
1326 int allow_create = 1;
1327 int replace_required = 0;
1328 int sernum = fib6_new_sernum(info->nl_net);
1329
1330 if (info->nlh) {
1331 if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
1332 allow_create = 0;
1333 if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
1334 replace_required = 1;
1335 }
1336 if (!allow_create && !replace_required)
1337 pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
1338
1339 fn = fib6_add_1(info->nl_net, table, root,
1340 &rt->fib6_dst.addr, rt->fib6_dst.plen,
1341 offsetof(struct fib6_info, fib6_dst), allow_create,
1342 replace_required, extack);
1343 if (IS_ERR(fn)) {
1344 err = PTR_ERR(fn);
1345 fn = NULL;
1346 goto out;
1347 }
1348
1349 pn = fn;
1350
1351 #ifdef CONFIG_IPV6_SUBTREES
1352 if (rt->fib6_src.plen) {
1353 struct fib6_node *sn;
1354
1355 if (!rcu_access_pointer(fn->subtree)) {
1356 struct fib6_node *sfn;
1357
1358 /*
1359 * Create subtree.
1360 *
1361 * fn[main tree]
1362 * |
1363 * sfn[subtree root]
1364 * \
1365 * sn[new leaf node]
1366 */
1367
1368 /* Create subtree root node */
1369 sfn = node_alloc(info->nl_net);
1370 if (!sfn)
1371 goto failure;
1372
1373 fib6_info_hold(info->nl_net->ipv6.fib6_null_entry);
1374 rcu_assign_pointer(sfn->leaf,
1375 info->nl_net->ipv6.fib6_null_entry);
1376 sfn->fn_flags = RTN_ROOT;
1377
1378 /* Now add the first leaf node to new subtree */
1379
1380 sn = fib6_add_1(info->nl_net, table, sfn,
1381 &rt->fib6_src.addr, rt->fib6_src.plen,
1382 offsetof(struct fib6_info, fib6_src),
1383 allow_create, replace_required, extack);
1384
1385 if (IS_ERR(sn)) {
1386 /* If it is failed, discard just allocated
1387 root, and then (in failure) stale node
1388 in main tree.
1389 */
1390 node_free_immediate(info->nl_net, sfn);
1391 err = PTR_ERR(sn);
1392 goto failure;
1393 }
1394
1395 /* Now link new subtree to main tree */
1396 rcu_assign_pointer(sfn->parent, fn);
1397 rcu_assign_pointer(fn->subtree, sfn);
1398 } else {
1399 sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),
1400 &rt->fib6_src.addr, rt->fib6_src.plen,
1401 offsetof(struct fib6_info, fib6_src),
1402 allow_create, replace_required, extack);
1403
1404 if (IS_ERR(sn)) {
1405 err = PTR_ERR(sn);
1406 goto failure;
1407 }
1408 }
1409
1410 if (!rcu_access_pointer(fn->leaf)) {
1411 if (fn->fn_flags & RTN_TL_ROOT) {
1412 /* put back null_entry for root node */
1413 rcu_assign_pointer(fn->leaf,
1414 info->nl_net->ipv6.fib6_null_entry);
1415 } else {
1416 fib6_info_hold(rt);
1417 rcu_assign_pointer(fn->leaf, rt);
1418 }
1419 }
1420 fn = sn;
1421 }
1422 #endif
1423
1424 err = fib6_add_rt2node(fn, rt, info, extack);
1425 if (!err) {
1426 if (rt->nh)
1427 list_add(&rt->nh_list, &rt->nh->f6i_list);
1428 __fib6_update_sernum_upto_root(rt, sernum);
1429 fib6_start_gc(info->nl_net, rt);
1430 }
1431
1432 out:
1433 if (err) {
1434 #ifdef CONFIG_IPV6_SUBTREES
1435 /*
1436 * If fib6_add_1 has cleared the old leaf pointer in the
1437 * super-tree leaf node we have to find a new one for it.
1438 */
1439 if (pn != fn) {
1440 struct fib6_info *pn_leaf =
1441 rcu_dereference_protected(pn->leaf,
1442 lockdep_is_held(&table->tb6_lock));
1443 if (pn_leaf == rt) {
1444 pn_leaf = NULL;
1445 RCU_INIT_POINTER(pn->leaf, NULL);
1446 fib6_info_release(rt);
1447 }
1448 if (!pn_leaf && !(pn->fn_flags & RTN_RTINFO)) {
1449 pn_leaf = fib6_find_prefix(info->nl_net, table,
1450 pn);
1451 #if RT6_DEBUG >= 2
1452 if (!pn_leaf) {
1453 WARN_ON(!pn_leaf);
1454 pn_leaf =
1455 info->nl_net->ipv6.fib6_null_entry;
1456 }
1457 #endif
1458 fib6_info_hold(pn_leaf);
1459 rcu_assign_pointer(pn->leaf, pn_leaf);
1460 }
1461 }
1462 #endif
1463 goto failure;
1464 } else if (fib6_requires_src(rt)) {
1465 fib6_routes_require_src_inc(info->nl_net);
1466 }
1467 return err;
1468
1469 failure:
1470 /* fn->leaf could be NULL and fib6_repair_tree() needs to be called if:
1471 * 1. fn is an intermediate node and we failed to add the new
1472 * route to it in both subtree creation failure and fib6_add_rt2node()
1473 * failure case.
1474 * 2. fn is the root node in the table and we fail to add the first
1475 * default route to it.
1476 */
1477 if (fn &&
1478 (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||
1479 (fn->fn_flags & RTN_TL_ROOT &&
1480 !rcu_access_pointer(fn->leaf))))
1481 fib6_repair_tree(info->nl_net, table, fn);
1482 return err;
1483 }
1484
1485 /*
1486 * Routing tree lookup
1487 *
1488 */
1489
1490 struct lookup_args {
1491 int offset; /* key offset on fib6_info */
1492 const struct in6_addr *addr; /* search key */
1493 };
1494
1495 static struct fib6_node *fib6_node_lookup_1(struct fib6_node *root,
1496 struct lookup_args *args)
1497 {
1498 struct fib6_node *fn;
1499 __be32 dir;
1500
1501 if (unlikely(args->offset == 0))
1502 return NULL;
1503
1504 /*
1505 * Descend on a tree
1506 */
1507
1508 fn = root;
1509
1510 for (;;) {
1511 struct fib6_node *next;
1512
1513 dir = addr_bit_set(args->addr, fn->fn_bit);
1514
1515 next = dir ? rcu_dereference(fn->right) :
1516 rcu_dereference(fn->left);
1517
1518 if (next) {
1519 fn = next;
1520 continue;
1521 }
1522 break;
1523 }
1524
1525 while (fn) {
1526 struct fib6_node *subtree = FIB6_SUBTREE(fn);
1527
1528 if (subtree || fn->fn_flags & RTN_RTINFO) {
1529 struct fib6_info *leaf = rcu_dereference(fn->leaf);
1530 struct rt6key *key;
1531
1532 if (!leaf)
1533 goto backtrack;
1534
1535 key = (struct rt6key *) ((u8 *)leaf + args->offset);
1536
1537 if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
1538 #ifdef CONFIG_IPV6_SUBTREES
1539 if (subtree) {
1540 struct fib6_node *sfn;
1541 sfn = fib6_node_lookup_1(subtree,
1542 args + 1);
1543 if (!sfn)
1544 goto backtrack;
1545 fn = sfn;
1546 }
1547 #endif
1548 if (fn->fn_flags & RTN_RTINFO)
1549 return fn;
1550 }
1551 }
1552 backtrack:
1553 if (fn->fn_flags & RTN_ROOT)
1554 break;
1555
1556 fn = rcu_dereference(fn->parent);
1557 }
1558
1559 return NULL;
1560 }
1561
1562 /* called with rcu_read_lock() held
1563 */
1564 struct fib6_node *fib6_node_lookup(struct fib6_node *root,
1565 const struct in6_addr *daddr,
1566 const struct in6_addr *saddr)
1567 {
1568 struct fib6_node *fn;
1569 struct lookup_args args[] = {
1570 {
1571 .offset = offsetof(struct fib6_info, fib6_dst),
1572 .addr = daddr,
1573 },
1574 #ifdef CONFIG_IPV6_SUBTREES
1575 {
1576 .offset = offsetof(struct fib6_info, fib6_src),
1577 .addr = saddr,
1578 },
1579 #endif
1580 {
1581 .offset = 0, /* sentinel */
1582 }
1583 };
1584
1585 fn = fib6_node_lookup_1(root, daddr ? args : args + 1);
1586 if (!fn || fn->fn_flags & RTN_TL_ROOT)
1587 fn = root;
1588
1589 return fn;
1590 }
1591
1592 /*
1593 * Get node with specified destination prefix (and source prefix,
1594 * if subtrees are used)
1595 * exact_match == true means we try to find fn with exact match of
1596 * the passed in prefix addr
1597 * exact_match == false means we try to find fn with longest prefix
1598 * match of the passed in prefix addr. This is useful for finding fn
1599 * for cached route as it will be stored in the exception table under
1600 * the node with longest prefix length.
1601 */
1602
1603
1604 static struct fib6_node *fib6_locate_1(struct fib6_node *root,
1605 const struct in6_addr *addr,
1606 int plen, int offset,
1607 bool exact_match)
1608 {
1609 struct fib6_node *fn, *prev = NULL;
1610
1611 for (fn = root; fn ; ) {
1612 struct fib6_info *leaf = rcu_dereference(fn->leaf);
1613 struct rt6key *key;
1614
1615 /* This node is being deleted */
1616 if (!leaf) {
1617 if (plen <= fn->fn_bit)
1618 goto out;
1619 else
1620 goto next;
1621 }
1622
1623 key = (struct rt6key *)((u8 *)leaf + offset);
1624
1625 /*
1626 * Prefix match
1627 */
1628 if (plen < fn->fn_bit ||
1629 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1630 goto out;
1631
1632 if (plen == fn->fn_bit)
1633 return fn;
1634
1635 if (fn->fn_flags & RTN_RTINFO)
1636 prev = fn;
1637
1638 next:
1639 /*
1640 * We have more bits to go
1641 */
1642 if (addr_bit_set(addr, fn->fn_bit))
1643 fn = rcu_dereference(fn->right);
1644 else
1645 fn = rcu_dereference(fn->left);
1646 }
1647 out:
1648 if (exact_match)
1649 return NULL;
1650 else
1651 return prev;
1652 }
1653
1654 struct fib6_node *fib6_locate(struct fib6_node *root,
1655 const struct in6_addr *daddr, int dst_len,
1656 const struct in6_addr *saddr, int src_len,
1657 bool exact_match)
1658 {
1659 struct fib6_node *fn;
1660
1661 fn = fib6_locate_1(root, daddr, dst_len,
1662 offsetof(struct fib6_info, fib6_dst),
1663 exact_match);
1664
1665 #ifdef CONFIG_IPV6_SUBTREES
1666 if (src_len) {
1667 WARN_ON(saddr == NULL);
1668 if (fn) {
1669 struct fib6_node *subtree = FIB6_SUBTREE(fn);
1670
1671 if (subtree) {
1672 fn = fib6_locate_1(subtree, saddr, src_len,
1673 offsetof(struct fib6_info, fib6_src),
1674 exact_match);
1675 }
1676 }
1677 }
1678 #endif
1679
1680 if (fn && fn->fn_flags & RTN_RTINFO)
1681 return fn;
1682
1683 return NULL;
1684 }
1685
1686
1687 /*
1688 * Deletion
1689 *
1690 */
1691
1692 static struct fib6_info *fib6_find_prefix(struct net *net,
1693 struct fib6_table *table,
1694 struct fib6_node *fn)
1695 {
1696 struct fib6_node *child_left, *child_right;
1697
1698 if (fn->fn_flags & RTN_ROOT)
1699 return net->ipv6.fib6_null_entry;
1700
1701 while (fn) {
1702 child_left = rcu_dereference_protected(fn->left,
1703 lockdep_is_held(&table->tb6_lock));
1704 child_right = rcu_dereference_protected(fn->right,
1705 lockdep_is_held(&table->tb6_lock));
1706 if (child_left)
1707 return rcu_dereference_protected(child_left->leaf,
1708 lockdep_is_held(&table->tb6_lock));
1709 if (child_right)
1710 return rcu_dereference_protected(child_right->leaf,
1711 lockdep_is_held(&table->tb6_lock));
1712
1713 fn = FIB6_SUBTREE(fn);
1714 }
1715 return NULL;
1716 }
1717
1718 /*
1719 * Called to trim the tree of intermediate nodes when possible. "fn"
1720 * is the node we want to try and remove.
1721 * Need to own table->tb6_lock
1722 */
1723
1724 static struct fib6_node *fib6_repair_tree(struct net *net,
1725 struct fib6_table *table,
1726 struct fib6_node *fn)
1727 {
1728 int children;
1729 int nstate;
1730 struct fib6_node *child;
1731 struct fib6_walker *w;
1732 int iter = 0;
1733
1734 /* Set fn->leaf to null_entry for root node. */
1735 if (fn->fn_flags & RTN_TL_ROOT) {
1736 rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);
1737 return fn;
1738 }
1739
1740 for (;;) {
1741 struct fib6_node *fn_r = rcu_dereference_protected(fn->right,
1742 lockdep_is_held(&table->tb6_lock));
1743 struct fib6_node *fn_l = rcu_dereference_protected(fn->left,
1744 lockdep_is_held(&table->tb6_lock));
1745 struct fib6_node *pn = rcu_dereference_protected(fn->parent,
1746 lockdep_is_held(&table->tb6_lock));
1747 struct fib6_node *pn_r = rcu_dereference_protected(pn->right,
1748 lockdep_is_held(&table->tb6_lock));
1749 struct fib6_node *pn_l = rcu_dereference_protected(pn->left,
1750 lockdep_is_held(&table->tb6_lock));
1751 struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,
1752 lockdep_is_held(&table->tb6_lock));
1753 struct fib6_info *pn_leaf = rcu_dereference_protected(pn->leaf,
1754 lockdep_is_held(&table->tb6_lock));
1755 struct fib6_info *new_fn_leaf;
1756
1757 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1758 iter++;
1759
1760 WARN_ON(fn->fn_flags & RTN_RTINFO);
1761 WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1762 WARN_ON(fn_leaf);
1763
1764 children = 0;
1765 child = NULL;
1766 if (fn_r)
1767 child = fn_r, children |= 1;
1768 if (fn_l)
1769 child = fn_l, children |= 2;
1770
1771 if (children == 3 || FIB6_SUBTREE(fn)
1772 #ifdef CONFIG_IPV6_SUBTREES
1773 /* Subtree root (i.e. fn) may have one child */
1774 || (children && fn->fn_flags & RTN_ROOT)
1775 #endif
1776 ) {
1777 new_fn_leaf = fib6_find_prefix(net, table, fn);
1778 #if RT6_DEBUG >= 2
1779 if (!new_fn_leaf) {
1780 WARN_ON(!new_fn_leaf);
1781 new_fn_leaf = net->ipv6.fib6_null_entry;
1782 }
1783 #endif
1784 fib6_info_hold(new_fn_leaf);
1785 rcu_assign_pointer(fn->leaf, new_fn_leaf);
1786 return pn;
1787 }
1788
1789 #ifdef CONFIG_IPV6_SUBTREES
1790 if (FIB6_SUBTREE(pn) == fn) {
1791 WARN_ON(!(fn->fn_flags & RTN_ROOT));
1792 RCU_INIT_POINTER(pn->subtree, NULL);
1793 nstate = FWS_L;
1794 } else {
1795 WARN_ON(fn->fn_flags & RTN_ROOT);
1796 #endif
1797 if (pn_r == fn)
1798 rcu_assign_pointer(pn->right, child);
1799 else if (pn_l == fn)
1800 rcu_assign_pointer(pn->left, child);
1801 #if RT6_DEBUG >= 2
1802 else
1803 WARN_ON(1);
1804 #endif
1805 if (child)
1806 rcu_assign_pointer(child->parent, pn);
1807 nstate = FWS_R;
1808 #ifdef CONFIG_IPV6_SUBTREES
1809 }
1810 #endif
1811
1812 read_lock(&net->ipv6.fib6_walker_lock);
1813 FOR_WALKERS(net, w) {
1814 if (!child) {
1815 if (w->node == fn) {
1816 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1817 w->node = pn;
1818 w->state = nstate;
1819 }
1820 } else {
1821 if (w->node == fn) {
1822 w->node = child;
1823 if (children&2) {
1824 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1825 w->state = w->state >= FWS_R ? FWS_U : FWS_INIT;
1826 } else {
1827 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1828 w->state = w->state >= FWS_C ? FWS_U : FWS_INIT;
1829 }
1830 }
1831 }
1832 }
1833 read_unlock(&net->ipv6.fib6_walker_lock);
1834
1835 node_free(net, fn);
1836 if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
1837 return pn;
1838
1839 RCU_INIT_POINTER(pn->leaf, NULL);
1840 fib6_info_release(pn_leaf);
1841 fn = pn;
1842 }
1843 }
1844
1845 static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,
1846 struct fib6_info __rcu **rtp, struct nl_info *info)
1847 {
1848 struct fib6_walker *w;
1849 struct fib6_info *rt = rcu_dereference_protected(*rtp,
1850 lockdep_is_held(&table->tb6_lock));
1851 struct net *net = info->nl_net;
1852
1853 RT6_TRACE("fib6_del_route\n");
1854
1855 /* Unlink it */
1856 *rtp = rt->fib6_next;
1857 rt->fib6_node = NULL;
1858 net->ipv6.rt6_stats->fib_rt_entries--;
1859 net->ipv6.rt6_stats->fib_discarded_routes++;
1860
1861 /* Flush all cached dst in exception table */
1862 rt6_flush_exceptions(rt);
1863
1864 /* Reset round-robin state, if necessary */
1865 if (rcu_access_pointer(fn->rr_ptr) == rt)
1866 fn->rr_ptr = NULL;
1867
1868 /* Remove this entry from other siblings */
1869 if (rt->fib6_nsiblings) {
1870 struct fib6_info *sibling, *next_sibling;
1871
1872 list_for_each_entry_safe(sibling, next_sibling,
1873 &rt->fib6_siblings, fib6_siblings)
1874 sibling->fib6_nsiblings--;
1875 rt->fib6_nsiblings = 0;
1876 list_del_init(&rt->fib6_siblings);
1877 rt6_multipath_rebalance(next_sibling);
1878 }
1879
1880 /* Adjust walkers */
1881 read_lock(&net->ipv6.fib6_walker_lock);
1882 FOR_WALKERS(net, w) {
1883 if (w->state == FWS_C && w->leaf == rt) {
1884 RT6_TRACE("walker %p adjusted by delroute\n", w);
1885 w->leaf = rcu_dereference_protected(rt->fib6_next,
1886 lockdep_is_held(&table->tb6_lock));
1887 if (!w->leaf)
1888 w->state = FWS_U;
1889 }
1890 }
1891 read_unlock(&net->ipv6.fib6_walker_lock);
1892
1893 /* If it was last route, call fib6_repair_tree() to:
1894 * 1. For root node, put back null_entry as how the table was created.
1895 * 2. For other nodes, expunge its radix tree node.
1896 */
1897 if (!rcu_access_pointer(fn->leaf)) {
1898 if (!(fn->fn_flags & RTN_TL_ROOT)) {
1899 fn->fn_flags &= ~RTN_RTINFO;
1900 net->ipv6.rt6_stats->fib_route_nodes--;
1901 }
1902 fn = fib6_repair_tree(net, table, fn);
1903 }
1904
1905 fib6_purge_rt(rt, fn, net);
1906
1907 if (!info->skip_notify_kernel)
1908 call_fib6_entry_notifiers(net, FIB_EVENT_ENTRY_DEL, rt, NULL);
1909 if (!info->skip_notify)
1910 inet6_rt_notify(RTM_DELROUTE, rt, info, 0);
1911
1912 fib6_info_release(rt);
1913 }
1914
1915 /* Need to own table->tb6_lock */
1916 int fib6_del(struct fib6_info *rt, struct nl_info *info)
1917 {
1918 struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,
1919 lockdep_is_held(&rt->fib6_table->tb6_lock));
1920 struct fib6_table *table = rt->fib6_table;
1921 struct net *net = info->nl_net;
1922 struct fib6_info __rcu **rtp;
1923 struct fib6_info __rcu **rtp_next;
1924
1925 if (!fn || rt == net->ipv6.fib6_null_entry)
1926 return -ENOENT;
1927
1928 WARN_ON(!(fn->fn_flags & RTN_RTINFO));
1929
1930 /*
1931 * Walk the leaf entries looking for ourself
1932 */
1933
1934 for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {
1935 struct fib6_info *cur = rcu_dereference_protected(*rtp,
1936 lockdep_is_held(&table->tb6_lock));
1937 if (rt == cur) {
1938 if (fib6_requires_src(cur))
1939 fib6_routes_require_src_dec(info->nl_net);
1940 fib6_del_route(table, fn, rtp, info);
1941 return 0;
1942 }
1943 rtp_next = &cur->fib6_next;
1944 }
1945 return -ENOENT;
1946 }
1947
1948 /*
1949 * Tree traversal function.
1950 *
1951 * Certainly, it is not interrupt safe.
1952 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1953 * It means, that we can modify tree during walking
1954 * and use this function for garbage collection, clone pruning,
1955 * cleaning tree when a device goes down etc. etc.
1956 *
1957 * It guarantees that every node will be traversed,
1958 * and that it will be traversed only once.
1959 *
1960 * Callback function w->func may return:
1961 * 0 -> continue walking.
1962 * positive value -> walking is suspended (used by tree dumps,
1963 * and probably by gc, if it will be split to several slices)
1964 * negative value -> terminate walking.
1965 *
1966 * The function itself returns:
1967 * 0 -> walk is complete.
1968 * >0 -> walk is incomplete (i.e. suspended)
1969 * <0 -> walk is terminated by an error.
1970 *
1971 * This function is called with tb6_lock held.
1972 */
1973
1974 static int fib6_walk_continue(struct fib6_walker *w)
1975 {
1976 struct fib6_node *fn, *pn, *left, *right;
1977
1978 /* w->root should always be table->tb6_root */
1979 WARN_ON_ONCE(!(w->root->fn_flags & RTN_TL_ROOT));
1980
1981 for (;;) {
1982 fn = w->node;
1983 if (!fn)
1984 return 0;
1985
1986 switch (w->state) {
1987 #ifdef CONFIG_IPV6_SUBTREES
1988 case FWS_S:
1989 if (FIB6_SUBTREE(fn)) {
1990 w->node = FIB6_SUBTREE(fn);
1991 continue;
1992 }
1993 w->state = FWS_L;
1994 #endif
1995 /* fall through */
1996 case FWS_L:
1997 left = rcu_dereference_protected(fn->left, 1);
1998 if (left) {
1999 w->node = left;
2000 w->state = FWS_INIT;
2001 continue;
2002 }
2003 w->state = FWS_R;
2004 /* fall through */
2005 case FWS_R:
2006 right = rcu_dereference_protected(fn->right, 1);
2007 if (right) {
2008 w->node = right;
2009 w->state = FWS_INIT;
2010 continue;
2011 }
2012 w->state = FWS_C;
2013 w->leaf = rcu_dereference_protected(fn->leaf, 1);
2014 /* fall through */
2015 case FWS_C:
2016 if (w->leaf && fn->fn_flags & RTN_RTINFO) {
2017 int err;
2018
2019 if (w->skip) {
2020 w->skip--;
2021 goto skip;
2022 }
2023
2024 err = w->func(w);
2025 if (err)
2026 return err;
2027
2028 w->count++;
2029 continue;
2030 }
2031 skip:
2032 w->state = FWS_U;
2033 /* fall through */
2034 case FWS_U:
2035 if (fn == w->root)
2036 return 0;
2037 pn = rcu_dereference_protected(fn->parent, 1);
2038 left = rcu_dereference_protected(pn->left, 1);
2039 right = rcu_dereference_protected(pn->right, 1);
2040 w->node = pn;
2041 #ifdef CONFIG_IPV6_SUBTREES
2042 if (FIB6_SUBTREE(pn) == fn) {
2043 WARN_ON(!(fn->fn_flags & RTN_ROOT));
2044 w->state = FWS_L;
2045 continue;
2046 }
2047 #endif
2048 if (left == fn) {
2049 w->state = FWS_R;
2050 continue;
2051 }
2052 if (right == fn) {
2053 w->state = FWS_C;
2054 w->leaf = rcu_dereference_protected(w->node->leaf, 1);
2055 continue;
2056 }
2057 #if RT6_DEBUG >= 2
2058 WARN_ON(1);
2059 #endif
2060 }
2061 }
2062 }
2063
2064 static int fib6_walk(struct net *net, struct fib6_walker *w)
2065 {
2066 int res;
2067
2068 w->state = FWS_INIT;
2069 w->node = w->root;
2070
2071 fib6_walker_link(net, w);
2072 res = fib6_walk_continue(w);
2073 if (res <= 0)
2074 fib6_walker_unlink(net, w);
2075 return res;
2076 }
2077
2078 static int fib6_clean_node(struct fib6_walker *w)
2079 {
2080 int res;
2081 struct fib6_info *rt;
2082 struct fib6_cleaner *c = container_of(w, struct fib6_cleaner, w);
2083 struct nl_info info = {
2084 .nl_net = c->net,
2085 .skip_notify = c->skip_notify,
2086 };
2087
2088 if (c->sernum != FIB6_NO_SERNUM_CHANGE &&
2089 w->node->fn_sernum != c->sernum)
2090 w->node->fn_sernum = c->sernum;
2091
2092 if (!c->func) {
2093 WARN_ON_ONCE(c->sernum == FIB6_NO_SERNUM_CHANGE);
2094 w->leaf = NULL;
2095 return 0;
2096 }
2097
2098 for_each_fib6_walker_rt(w) {
2099 res = c->func(rt, c->arg);
2100 if (res == -1) {
2101 w->leaf = rt;
2102 res = fib6_del(rt, &info);
2103 if (res) {
2104 #if RT6_DEBUG >= 2
2105 pr_debug("%s: del failed: rt=%p@%p err=%d\n",
2106 __func__, rt,
2107 rcu_access_pointer(rt->fib6_node),
2108 res);
2109 #endif
2110 continue;
2111 }
2112 return 0;
2113 } else if (res == -2) {
2114 if (WARN_ON(!rt->fib6_nsiblings))
2115 continue;
2116 rt = list_last_entry(&rt->fib6_siblings,
2117 struct fib6_info, fib6_siblings);
2118 continue;
2119 }
2120 WARN_ON(res != 0);
2121 }
2122 w->leaf = rt;
2123 return 0;
2124 }
2125
2126 /*
2127 * Convenient frontend to tree walker.
2128 *
2129 * func is called on each route.
2130 * It may return -2 -> skip multipath route.
2131 * -1 -> delete this route.
2132 * 0 -> continue walking
2133 */
2134
2135 static void fib6_clean_tree(struct net *net, struct fib6_node *root,
2136 int (*func)(struct fib6_info *, void *arg),
2137 int sernum, void *arg, bool skip_notify)
2138 {
2139 struct fib6_cleaner c;
2140
2141 c.w.root = root;
2142 c.w.func = fib6_clean_node;
2143 c.w.count = 0;
2144 c.w.skip = 0;
2145 c.w.skip_in_node = 0;
2146 c.func = func;
2147 c.sernum = sernum;
2148 c.arg = arg;
2149 c.net = net;
2150 c.skip_notify = skip_notify;
2151
2152 fib6_walk(net, &c.w);
2153 }
2154
2155 static void __fib6_clean_all(struct net *net,
2156 int (*func)(struct fib6_info *, void *),
2157 int sernum, void *arg, bool skip_notify)
2158 {
2159 struct fib6_table *table;
2160 struct hlist_head *head;
2161 unsigned int h;
2162
2163 rcu_read_lock();
2164 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
2165 head = &net->ipv6.fib_table_hash[h];
2166 hlist_for_each_entry_rcu(table, head, tb6_hlist) {
2167 spin_lock_bh(&table->tb6_lock);
2168 fib6_clean_tree(net, &table->tb6_root,
2169 func, sernum, arg, skip_notify);
2170 spin_unlock_bh(&table->tb6_lock);
2171 }
2172 }
2173 rcu_read_unlock();
2174 }
2175
2176 void fib6_clean_all(struct net *net, int (*func)(struct fib6_info *, void *),
2177 void *arg)
2178 {
2179 __fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, false);
2180 }
2181
2182 void fib6_clean_all_skip_notify(struct net *net,
2183 int (*func)(struct fib6_info *, void *),
2184 void *arg)
2185 {
2186 __fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, true);
2187 }
2188
2189 static void fib6_flush_trees(struct net *net)
2190 {
2191 int new_sernum = fib6_new_sernum(net);
2192
2193 __fib6_clean_all(net, NULL, new_sernum, NULL, false);
2194 }
2195
2196 /*
2197 * Garbage collection
2198 */
2199
2200 static int fib6_age(struct fib6_info *rt, void *arg)
2201 {
2202 struct fib6_gc_args *gc_args = arg;
2203 unsigned long now = jiffies;
2204
2205 /*
2206 * check addrconf expiration here.
2207 * Routes are expired even if they are in use.
2208 */
2209
2210 if (rt->fib6_flags & RTF_EXPIRES && rt->expires) {
2211 if (time_after(now, rt->expires)) {
2212 RT6_TRACE("expiring %p\n", rt);
2213 return -1;
2214 }
2215 gc_args->more++;
2216 }
2217
2218 /* Also age clones in the exception table.
2219 * Note, that clones are aged out
2220 * only if they are not in use now.
2221 */
2222 rt6_age_exceptions(rt, gc_args, now);
2223
2224 return 0;
2225 }
2226
2227 void fib6_run_gc(unsigned long expires, struct net *net, bool force)
2228 {
2229 struct fib6_gc_args gc_args;
2230 unsigned long now;
2231
2232 if (force) {
2233 spin_lock_bh(&net->ipv6.fib6_gc_lock);
2234 } else if (!spin_trylock_bh(&net->ipv6.fib6_gc_lock)) {
2235 mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
2236 return;
2237 }
2238 gc_args.timeout = expires ? (int)expires :
2239 net->ipv6.sysctl.ip6_rt_gc_interval;
2240 gc_args.more = 0;
2241
2242 fib6_clean_all(net, fib6_age, &gc_args);
2243 now = jiffies;
2244 net->ipv6.ip6_rt_last_gc = now;
2245
2246 if (gc_args.more)
2247 mod_timer(&net->ipv6.ip6_fib_timer,
2248 round_jiffies(now
2249 + net->ipv6.sysctl.ip6_rt_gc_interval));
2250 else
2251 del_timer(&net->ipv6.ip6_fib_timer);
2252 spin_unlock_bh(&net->ipv6.fib6_gc_lock);
2253 }
2254
2255 static void fib6_gc_timer_cb(struct timer_list *t)
2256 {
2257 struct net *arg = from_timer(arg, t, ipv6.ip6_fib_timer);
2258
2259 fib6_run_gc(0, arg, true);
2260 }
2261
2262 static int __net_init fib6_net_init(struct net *net)
2263 {
2264 size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
2265 int err;
2266
2267 err = fib6_notifier_init(net);
2268 if (err)
2269 return err;
2270
2271 spin_lock_init(&net->ipv6.fib6_gc_lock);
2272 rwlock_init(&net->ipv6.fib6_walker_lock);
2273 INIT_LIST_HEAD(&net->ipv6.fib6_walkers);
2274 timer_setup(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, 0);
2275
2276 net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
2277 if (!net->ipv6.rt6_stats)
2278 goto out_timer;
2279
2280 /* Avoid false sharing : Use at least a full cache line */
2281 size = max_t(size_t, size, L1_CACHE_BYTES);
2282
2283 net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
2284 if (!net->ipv6.fib_table_hash)
2285 goto out_rt6_stats;
2286
2287 net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
2288 GFP_KERNEL);
2289 if (!net->ipv6.fib6_main_tbl)
2290 goto out_fib_table_hash;
2291
2292 net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
2293 rcu_assign_pointer(net->ipv6.fib6_main_tbl->tb6_root.leaf,
2294 net->ipv6.fib6_null_entry);
2295 net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
2296 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
2297 inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
2298
2299 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
2300 net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
2301 GFP_KERNEL);
2302 if (!net->ipv6.fib6_local_tbl)
2303 goto out_fib6_main_tbl;
2304 net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
2305 rcu_assign_pointer(net->ipv6.fib6_local_tbl->tb6_root.leaf,
2306 net->ipv6.fib6_null_entry);
2307 net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
2308 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
2309 inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
2310 #endif
2311 fib6_tables_init(net);
2312
2313 return 0;
2314
2315 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
2316 out_fib6_main_tbl:
2317 kfree(net->ipv6.fib6_main_tbl);
2318 #endif
2319 out_fib_table_hash:
2320 kfree(net->ipv6.fib_table_hash);
2321 out_rt6_stats:
2322 kfree(net->ipv6.rt6_stats);
2323 out_timer:
2324 fib6_notifier_exit(net);
2325 return -ENOMEM;
2326 }
2327
2328 static void fib6_net_exit(struct net *net)
2329 {
2330 unsigned int i;
2331
2332 del_timer_sync(&net->ipv6.ip6_fib_timer);
2333
2334 for (i = 0; i < FIB6_TABLE_HASHSZ; i++) {
2335 struct hlist_head *head = &net->ipv6.fib_table_hash[i];
2336 struct hlist_node *tmp;
2337 struct fib6_table *tb;
2338
2339 hlist_for_each_entry_safe(tb, tmp, head, tb6_hlist) {
2340 hlist_del(&tb->tb6_hlist);
2341 fib6_free_table(tb);
2342 }
2343 }
2344
2345 kfree(net->ipv6.fib_table_hash);
2346 kfree(net->ipv6.rt6_stats);
2347 fib6_notifier_exit(net);
2348 }
2349
2350 static struct pernet_operations fib6_net_ops = {
2351 .init = fib6_net_init,
2352 .exit = fib6_net_exit,
2353 };
2354
2355 int __init fib6_init(void)
2356 {
2357 int ret = -ENOMEM;
2358
2359 fib6_node_kmem = kmem_cache_create("fib6_nodes",
2360 sizeof(struct fib6_node),
2361 0, SLAB_HWCACHE_ALIGN,
2362 NULL);
2363 if (!fib6_node_kmem)
2364 goto out;
2365
2366 ret = register_pernet_subsys(&fib6_net_ops);
2367 if (ret)
2368 goto out_kmem_cache_create;
2369
2370 ret = rtnl_register_module(THIS_MODULE, PF_INET6, RTM_GETROUTE, NULL,
2371 inet6_dump_fib, 0);
2372 if (ret)
2373 goto out_unregister_subsys;
2374
2375 __fib6_flush_trees = fib6_flush_trees;
2376 out:
2377 return ret;
2378
2379 out_unregister_subsys:
2380 unregister_pernet_subsys(&fib6_net_ops);
2381 out_kmem_cache_create:
2382 kmem_cache_destroy(fib6_node_kmem);
2383 goto out;
2384 }
2385
2386 void fib6_gc_cleanup(void)
2387 {
2388 unregister_pernet_subsys(&fib6_net_ops);
2389 kmem_cache_destroy(fib6_node_kmem);
2390 }
2391
2392 #ifdef CONFIG_PROC_FS
2393 static int ipv6_route_seq_show(struct seq_file *seq, void *v)
2394 {
2395 struct fib6_info *rt = v;
2396 struct ipv6_route_iter *iter = seq->private;
2397 struct fib6_nh *fib6_nh = rt->fib6_nh;
2398 unsigned int flags = rt->fib6_flags;
2399 const struct net_device *dev;
2400
2401 if (rt->nh)
2402 fib6_nh = nexthop_fib6_nh(rt->nh);
2403
2404 seq_printf(seq, "%pi6 %02x ", &rt->fib6_dst.addr, rt->fib6_dst.plen);
2405
2406 #ifdef CONFIG_IPV6_SUBTREES
2407 seq_printf(seq, "%pi6 %02x ", &rt->fib6_src.addr, rt->fib6_src.plen);
2408 #else
2409 seq_puts(seq, "00000000000000000000000000000000 00 ");
2410 #endif
2411 if (fib6_nh->fib_nh_gw_family) {
2412 flags |= RTF_GATEWAY;
2413 seq_printf(seq, "%pi6", &fib6_nh->fib_nh_gw6);
2414 } else {
2415 seq_puts(seq, "00000000000000000000000000000000");
2416 }
2417
2418 dev = fib6_nh->fib_nh_dev;
2419 seq_printf(seq, " %08x %08x %08x %08x %8s\n",
2420 rt->fib6_metric, refcount_read(&rt->fib6_ref), 0,
2421 flags, dev ? dev->name : "");
2422 iter->w.leaf = NULL;
2423 return 0;
2424 }
2425
2426 static int ipv6_route_yield(struct fib6_walker *w)
2427 {
2428 struct ipv6_route_iter *iter = w->args;
2429
2430 if (!iter->skip)
2431 return 1;
2432
2433 do {
2434 iter->w.leaf = rcu_dereference_protected(
2435 iter->w.leaf->fib6_next,
2436 lockdep_is_held(&iter->tbl->tb6_lock));
2437 iter->skip--;
2438 if (!iter->skip && iter->w.leaf)
2439 return 1;
2440 } while (iter->w.leaf);
2441
2442 return 0;
2443 }
2444
2445 static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter,
2446 struct net *net)
2447 {
2448 memset(&iter->w, 0, sizeof(iter->w));
2449 iter->w.func = ipv6_route_yield;
2450 iter->w.root = &iter->tbl->tb6_root;
2451 iter->w.state = FWS_INIT;
2452 iter->w.node = iter->w.root;
2453 iter->w.args = iter;
2454 iter->sernum = iter->w.root->fn_sernum;
2455 INIT_LIST_HEAD(&iter->w.lh);
2456 fib6_walker_link(net, &iter->w);
2457 }
2458
2459 static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
2460 struct net *net)
2461 {
2462 unsigned int h;
2463 struct hlist_node *node;
2464
2465 if (tbl) {
2466 h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
2467 node = rcu_dereference_bh(hlist_next_rcu(&tbl->tb6_hlist));
2468 } else {
2469 h = 0;
2470 node = NULL;
2471 }
2472
2473 while (!node && h < FIB6_TABLE_HASHSZ) {
2474 node = rcu_dereference_bh(
2475 hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
2476 }
2477 return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
2478 }
2479
2480 static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
2481 {
2482 if (iter->sernum != iter->w.root->fn_sernum) {
2483 iter->sernum = iter->w.root->fn_sernum;
2484 iter->w.state = FWS_INIT;
2485 iter->w.node = iter->w.root;
2486 WARN_ON(iter->w.skip);
2487 iter->w.skip = iter->w.count;
2488 }
2489 }
2490
2491 static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2492 {
2493 int r;
2494 struct fib6_info *n;
2495 struct net *net = seq_file_net(seq);
2496 struct ipv6_route_iter *iter = seq->private;
2497
2498 if (!v)
2499 goto iter_table;
2500
2501 n = rcu_dereference_bh(((struct fib6_info *)v)->fib6_next);
2502 if (n) {
2503 ++*pos;
2504 return n;
2505 }
2506
2507 iter_table:
2508 ipv6_route_check_sernum(iter);
2509 spin_lock_bh(&iter->tbl->tb6_lock);
2510 r = fib6_walk_continue(&iter->w);
2511 spin_unlock_bh(&iter->tbl->tb6_lock);
2512 if (r > 0) {
2513 if (v)
2514 ++*pos;
2515 return iter->w.leaf;
2516 } else if (r < 0) {
2517 fib6_walker_unlink(net, &iter->w);
2518 return NULL;
2519 }
2520 fib6_walker_unlink(net, &iter->w);
2521
2522 iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
2523 if (!iter->tbl)
2524 return NULL;
2525
2526 ipv6_route_seq_setup_walk(iter, net);
2527 goto iter_table;
2528 }
2529
2530 static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
2531 __acquires(RCU_BH)
2532 {
2533 struct net *net = seq_file_net(seq);
2534 struct ipv6_route_iter *iter = seq->private;
2535
2536 rcu_read_lock_bh();
2537 iter->tbl = ipv6_route_seq_next_table(NULL, net);
2538 iter->skip = *pos;
2539
2540 if (iter->tbl) {
2541 ipv6_route_seq_setup_walk(iter, net);
2542 return ipv6_route_seq_next(seq, NULL, pos);
2543 } else {
2544 return NULL;
2545 }
2546 }
2547
2548 static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
2549 {
2550 struct fib6_walker *w = &iter->w;
2551 return w->node && !(w->state == FWS_U && w->node == w->root);
2552 }
2553
2554 static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
2555 __releases(RCU_BH)
2556 {
2557 struct net *net = seq_file_net(seq);
2558 struct ipv6_route_iter *iter = seq->private;
2559
2560 if (ipv6_route_iter_active(iter))
2561 fib6_walker_unlink(net, &iter->w);
2562
2563 rcu_read_unlock_bh();
2564 }
2565
2566 const struct seq_operations ipv6_route_seq_ops = {
2567 .start = ipv6_route_seq_start,
2568 .next = ipv6_route_seq_next,
2569 .stop = ipv6_route_seq_stop,
2570 .show = ipv6_route_seq_show
2571 };
2572 #endif /* CONFIG_PROC_FS */
Linux with added FPC-III support