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