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