1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Linux INET6 implementation
4 * Forwarding Information Database
7 * Pedro Roque <roque@di.fc.ul.pt>
10 * Yuji SEKIYA @USAGI: Support default route on router node;
11 * remove ip6_null_entry from the top of
13 * Ville Nuorvala: Fixed routing subtrees.
16 #define pr_fmt(fmt) "IPv6: " fmt
18 #include <linux/bpf.h>
19 #include <linux/errno.h>
20 #include <linux/types.h>
21 #include <linux/net.h>
22 #include <linux/route.h>
23 #include <linux/netdevice.h>
24 #include <linux/in6.h>
25 #include <linux/init.h>
26 #include <linux/list.h>
27 #include <linux/slab.h>
31 #include <net/ndisc.h>
32 #include <net/addrconf.h>
33 #include <net/lwtunnel.h>
34 #include <net/fib_notifier.h>
36 #include <net/ip_fib.h>
37 #include <net/ip6_fib.h>
38 #include <net/ip6_route.h>
40 static struct kmem_cache
*fib6_node_kmem __read_mostly
;
45 int (*func
)(struct fib6_info
*, void *arg
);
51 #ifdef CONFIG_IPV6_SUBTREES
52 #define FWS_INIT FWS_S
54 #define FWS_INIT FWS_L
57 static struct fib6_info
*fib6_find_prefix(struct net
*net
,
58 struct fib6_table
*table
,
59 struct fib6_node
*fn
);
60 static struct fib6_node
*fib6_repair_tree(struct net
*net
,
61 struct fib6_table
*table
,
62 struct fib6_node
*fn
);
63 static int fib6_walk(struct net
*net
, struct fib6_walker
*w
);
64 static int fib6_walk_continue(struct fib6_walker
*w
);
67 * A routing update causes an increase of the serial number on the
68 * affected subtree. This allows for cached routes to be asynchronously
69 * tested when modifications are made to the destination cache as a
70 * result of redirects, path MTU changes, etc.
73 static void fib6_gc_timer_cb(struct timer_list
*t
);
75 #define FOR_WALKERS(net, w) \
76 list_for_each_entry(w, &(net)->ipv6.fib6_walkers, lh)
78 static void fib6_walker_link(struct net
*net
, struct fib6_walker
*w
)
80 write_lock_bh(&net
->ipv6
.fib6_walker_lock
);
81 list_add(&w
->lh
, &net
->ipv6
.fib6_walkers
);
82 write_unlock_bh(&net
->ipv6
.fib6_walker_lock
);
85 static void fib6_walker_unlink(struct net
*net
, struct fib6_walker
*w
)
87 write_lock_bh(&net
->ipv6
.fib6_walker_lock
);
89 write_unlock_bh(&net
->ipv6
.fib6_walker_lock
);
92 static int fib6_new_sernum(struct net
*net
)
97 old
= atomic_read(&net
->ipv6
.fib6_sernum
);
98 new = old
< INT_MAX
? old
+ 1 : 1;
99 } while (atomic_cmpxchg(&net
->ipv6
.fib6_sernum
,
105 FIB6_NO_SERNUM_CHANGE
= 0,
108 void fib6_update_sernum(struct net
*net
, struct fib6_info
*f6i
)
110 struct fib6_node
*fn
;
112 fn
= rcu_dereference_protected(f6i
->fib6_node
,
113 lockdep_is_held(&f6i
->fib6_table
->tb6_lock
));
115 WRITE_ONCE(fn
->fn_sernum
, fib6_new_sernum(net
));
119 * Auxiliary address test functions for the radix tree.
121 * These assume a 32bit processor (although it will work on
128 #if defined(__LITTLE_ENDIAN)
129 # define BITOP_BE32_SWIZZLE (0x1F & ~7)
131 # define BITOP_BE32_SWIZZLE 0
134 static __be32
addr_bit_set(const void *token
, int fn_bit
)
136 const __be32
*addr
= token
;
139 * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
140 * is optimized version of
141 * htonl(1 << ((~fn_bit)&0x1F))
142 * See include/asm-generic/bitops/le.h.
144 return (__force __be32
)(1 << ((~fn_bit
^ BITOP_BE32_SWIZZLE
) & 0x1f)) &
148 struct fib6_info
*fib6_info_alloc(gfp_t gfp_flags
, bool with_fib6_nh
)
150 struct fib6_info
*f6i
;
151 size_t sz
= sizeof(*f6i
);
154 sz
+= sizeof(struct fib6_nh
);
156 f6i
= kzalloc(sz
, gfp_flags
);
160 /* fib6_siblings is a union with nh_list, so this initializes both */
161 INIT_LIST_HEAD(&f6i
->fib6_siblings
);
162 refcount_set(&f6i
->fib6_ref
, 1);
167 void fib6_info_destroy_rcu(struct rcu_head
*head
)
169 struct fib6_info
*f6i
= container_of(head
, struct fib6_info
, rcu
);
171 WARN_ON(f6i
->fib6_node
);
174 nexthop_put(f6i
->nh
);
176 fib6_nh_release(f6i
->fib6_nh
);
178 ip_fib_metrics_put(f6i
->fib6_metrics
);
181 EXPORT_SYMBOL_GPL(fib6_info_destroy_rcu
);
183 static struct fib6_node
*node_alloc(struct net
*net
)
185 struct fib6_node
*fn
;
187 fn
= kmem_cache_zalloc(fib6_node_kmem
, GFP_ATOMIC
);
189 net
->ipv6
.rt6_stats
->fib_nodes
++;
194 static void node_free_immediate(struct net
*net
, struct fib6_node
*fn
)
196 kmem_cache_free(fib6_node_kmem
, fn
);
197 net
->ipv6
.rt6_stats
->fib_nodes
--;
200 static void node_free_rcu(struct rcu_head
*head
)
202 struct fib6_node
*fn
= container_of(head
, struct fib6_node
, rcu
);
204 kmem_cache_free(fib6_node_kmem
, fn
);
207 static void node_free(struct net
*net
, struct fib6_node
*fn
)
209 call_rcu(&fn
->rcu
, node_free_rcu
);
210 net
->ipv6
.rt6_stats
->fib_nodes
--;
213 static void fib6_free_table(struct fib6_table
*table
)
215 inetpeer_invalidate_tree(&table
->tb6_peers
);
219 static void fib6_link_table(struct net
*net
, struct fib6_table
*tb
)
224 * Initialize table lock at a single place to give lockdep a key,
225 * tables aren't visible prior to being linked to the list.
227 spin_lock_init(&tb
->tb6_lock
);
228 h
= tb
->tb6_id
& (FIB6_TABLE_HASHSZ
- 1);
231 * No protection necessary, this is the only list mutatation
232 * operation, tables never disappear once they exist.
234 hlist_add_head_rcu(&tb
->tb6_hlist
, &net
->ipv6
.fib_table_hash
[h
]);
237 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
239 static struct fib6_table
*fib6_alloc_table(struct net
*net
, u32 id
)
241 struct fib6_table
*table
;
243 table
= kzalloc(sizeof(*table
), GFP_ATOMIC
);
246 rcu_assign_pointer(table
->tb6_root
.leaf
,
247 net
->ipv6
.fib6_null_entry
);
248 table
->tb6_root
.fn_flags
= RTN_ROOT
| RTN_TL_ROOT
| RTN_RTINFO
;
249 inet_peer_base_init(&table
->tb6_peers
);
255 struct fib6_table
*fib6_new_table(struct net
*net
, u32 id
)
257 struct fib6_table
*tb
;
261 tb
= fib6_get_table(net
, id
);
265 tb
= fib6_alloc_table(net
, id
);
267 fib6_link_table(net
, tb
);
271 EXPORT_SYMBOL_GPL(fib6_new_table
);
273 struct fib6_table
*fib6_get_table(struct net
*net
, u32 id
)
275 struct fib6_table
*tb
;
276 struct hlist_head
*head
;
281 h
= id
& (FIB6_TABLE_HASHSZ
- 1);
283 head
= &net
->ipv6
.fib_table_hash
[h
];
284 hlist_for_each_entry_rcu(tb
, head
, tb6_hlist
) {
285 if (tb
->tb6_id
== id
) {
294 EXPORT_SYMBOL_GPL(fib6_get_table
);
296 static void __net_init
fib6_tables_init(struct net
*net
)
298 fib6_link_table(net
, net
->ipv6
.fib6_main_tbl
);
299 fib6_link_table(net
, net
->ipv6
.fib6_local_tbl
);
303 struct fib6_table
*fib6_new_table(struct net
*net
, u32 id
)
305 return fib6_get_table(net
, id
);
308 struct fib6_table
*fib6_get_table(struct net
*net
, u32 id
)
310 return net
->ipv6
.fib6_main_tbl
;
313 struct dst_entry
*fib6_rule_lookup(struct net
*net
, struct flowi6
*fl6
,
314 const struct sk_buff
*skb
,
315 int flags
, pol_lookup_t lookup
)
319 rt
= pol_lookup_func(lookup
,
320 net
, net
->ipv6
.fib6_main_tbl
, fl6
, skb
, flags
);
321 if (rt
->dst
.error
== -EAGAIN
) {
322 ip6_rt_put_flags(rt
, flags
);
323 rt
= net
->ipv6
.ip6_null_entry
;
324 if (!(flags
& RT6_LOOKUP_F_DST_NOREF
))
331 /* called with rcu lock held; no reference taken on fib6_info */
332 int fib6_lookup(struct net
*net
, int oif
, struct flowi6
*fl6
,
333 struct fib6_result
*res
, int flags
)
335 return fib6_table_lookup(net
, net
->ipv6
.fib6_main_tbl
, oif
, fl6
,
339 static void __net_init
fib6_tables_init(struct net
*net
)
341 fib6_link_table(net
, net
->ipv6
.fib6_main_tbl
);
346 unsigned int fib6_tables_seq_read(struct net
*net
)
348 unsigned int h
, fib_seq
= 0;
351 for (h
= 0; h
< FIB6_TABLE_HASHSZ
; h
++) {
352 struct hlist_head
*head
= &net
->ipv6
.fib_table_hash
[h
];
353 struct fib6_table
*tb
;
355 hlist_for_each_entry_rcu(tb
, head
, tb6_hlist
)
356 fib_seq
+= tb
->fib_seq
;
363 static int call_fib6_entry_notifier(struct notifier_block
*nb
,
364 enum fib_event_type event_type
,
365 struct fib6_info
*rt
,
366 struct netlink_ext_ack
*extack
)
368 struct fib6_entry_notifier_info info
= {
369 .info
.extack
= extack
,
373 return call_fib6_notifier(nb
, event_type
, &info
.info
);
376 static int call_fib6_multipath_entry_notifier(struct notifier_block
*nb
,
377 enum fib_event_type event_type
,
378 struct fib6_info
*rt
,
379 unsigned int nsiblings
,
380 struct netlink_ext_ack
*extack
)
382 struct fib6_entry_notifier_info info
= {
383 .info
.extack
= extack
,
385 .nsiblings
= nsiblings
,
388 return call_fib6_notifier(nb
, event_type
, &info
.info
);
391 int call_fib6_entry_notifiers(struct net
*net
,
392 enum fib_event_type event_type
,
393 struct fib6_info
*rt
,
394 struct netlink_ext_ack
*extack
)
396 struct fib6_entry_notifier_info info
= {
397 .info
.extack
= extack
,
401 rt
->fib6_table
->fib_seq
++;
402 return call_fib6_notifiers(net
, event_type
, &info
.info
);
405 int call_fib6_multipath_entry_notifiers(struct net
*net
,
406 enum fib_event_type event_type
,
407 struct fib6_info
*rt
,
408 unsigned int nsiblings
,
409 struct netlink_ext_ack
*extack
)
411 struct fib6_entry_notifier_info info
= {
412 .info
.extack
= extack
,
414 .nsiblings
= nsiblings
,
417 rt
->fib6_table
->fib_seq
++;
418 return call_fib6_notifiers(net
, event_type
, &info
.info
);
421 int call_fib6_entry_notifiers_replace(struct net
*net
, struct fib6_info
*rt
)
423 struct fib6_entry_notifier_info info
= {
425 .nsiblings
= rt
->fib6_nsiblings
,
428 rt
->fib6_table
->fib_seq
++;
429 return call_fib6_notifiers(net
, FIB_EVENT_ENTRY_REPLACE
, &info
.info
);
432 struct fib6_dump_arg
{
434 struct notifier_block
*nb
;
435 struct netlink_ext_ack
*extack
;
438 static int fib6_rt_dump(struct fib6_info
*rt
, struct fib6_dump_arg
*arg
)
440 enum fib_event_type fib_event
= FIB_EVENT_ENTRY_REPLACE
;
443 if (!rt
|| rt
== arg
->net
->ipv6
.fib6_null_entry
)
446 if (rt
->fib6_nsiblings
)
447 err
= call_fib6_multipath_entry_notifier(arg
->nb
, fib_event
,
452 err
= call_fib6_entry_notifier(arg
->nb
, fib_event
, rt
,
458 static int fib6_node_dump(struct fib6_walker
*w
)
462 err
= fib6_rt_dump(w
->leaf
, w
->args
);
467 static int fib6_table_dump(struct net
*net
, struct fib6_table
*tb
,
468 struct fib6_walker
*w
)
472 w
->root
= &tb
->tb6_root
;
473 spin_lock_bh(&tb
->tb6_lock
);
474 err
= fib6_walk(net
, w
);
475 spin_unlock_bh(&tb
->tb6_lock
);
479 /* Called with rcu_read_lock() */
480 int fib6_tables_dump(struct net
*net
, struct notifier_block
*nb
,
481 struct netlink_ext_ack
*extack
)
483 struct fib6_dump_arg arg
;
484 struct fib6_walker
*w
;
488 w
= kzalloc(sizeof(*w
), GFP_ATOMIC
);
492 w
->func
= fib6_node_dump
;
498 for (h
= 0; h
< FIB6_TABLE_HASHSZ
; h
++) {
499 struct hlist_head
*head
= &net
->ipv6
.fib_table_hash
[h
];
500 struct fib6_table
*tb
;
502 hlist_for_each_entry_rcu(tb
, head
, tb6_hlist
) {
503 err
= fib6_table_dump(net
, tb
, w
);
512 /* The tree traversal function should never return a positive value. */
513 return err
> 0 ? -EINVAL
: err
;
516 static int fib6_dump_node(struct fib6_walker
*w
)
519 struct fib6_info
*rt
;
521 for_each_fib6_walker_rt(w
) {
522 res
= rt6_dump_route(rt
, w
->args
, w
->skip_in_node
);
524 /* Frame is full, suspend walking */
527 /* We'll restart from this node, so if some routes were
528 * already dumped, skip them next time.
530 w
->skip_in_node
+= res
;
536 /* Multipath routes are dumped in one route with the
537 * RTA_MULTIPATH attribute. Jump 'rt' to point to the
538 * last sibling of this route (no need to dump the
539 * sibling routes again)
541 if (rt
->fib6_nsiblings
)
542 rt
= list_last_entry(&rt
->fib6_siblings
,
550 static void fib6_dump_end(struct netlink_callback
*cb
)
552 struct net
*net
= sock_net(cb
->skb
->sk
);
553 struct fib6_walker
*w
= (void *)cb
->args
[2];
558 fib6_walker_unlink(net
, w
);
563 cb
->done
= (void *)cb
->args
[3];
567 static int fib6_dump_done(struct netlink_callback
*cb
)
570 return cb
->done
? cb
->done(cb
) : 0;
573 static int fib6_dump_table(struct fib6_table
*table
, struct sk_buff
*skb
,
574 struct netlink_callback
*cb
)
576 struct net
*net
= sock_net(skb
->sk
);
577 struct fib6_walker
*w
;
580 w
= (void *)cb
->args
[2];
581 w
->root
= &table
->tb6_root
;
583 if (cb
->args
[4] == 0) {
588 spin_lock_bh(&table
->tb6_lock
);
589 res
= fib6_walk(net
, w
);
590 spin_unlock_bh(&table
->tb6_lock
);
593 cb
->args
[5] = READ_ONCE(w
->root
->fn_sernum
);
596 int sernum
= READ_ONCE(w
->root
->fn_sernum
);
597 if (cb
->args
[5] != sernum
) {
598 /* Begin at the root if the tree changed */
599 cb
->args
[5] = sernum
;
607 spin_lock_bh(&table
->tb6_lock
);
608 res
= fib6_walk_continue(w
);
609 spin_unlock_bh(&table
->tb6_lock
);
611 fib6_walker_unlink(net
, w
);
619 static int inet6_dump_fib(struct sk_buff
*skb
, struct netlink_callback
*cb
)
621 struct rt6_rtnl_dump_arg arg
= { .filter
.dump_exceptions
= true,
622 .filter
.dump_routes
= true };
623 const struct nlmsghdr
*nlh
= cb
->nlh
;
624 struct net
*net
= sock_net(skb
->sk
);
626 unsigned int e
= 0, s_e
;
627 struct fib6_walker
*w
;
628 struct fib6_table
*tb
;
629 struct hlist_head
*head
;
632 if (cb
->strict_check
) {
635 err
= ip_valid_fib_dump_req(net
, nlh
, &arg
.filter
, cb
);
638 } else if (nlmsg_len(nlh
) >= sizeof(struct rtmsg
)) {
639 struct rtmsg
*rtm
= nlmsg_data(nlh
);
641 if (rtm
->rtm_flags
& RTM_F_PREFIX
)
642 arg
.filter
.flags
= RTM_F_PREFIX
;
645 w
= (void *)cb
->args
[2];
649 * 1. hook callback destructor.
651 cb
->args
[3] = (long)cb
->done
;
652 cb
->done
= fib6_dump_done
;
655 * 2. allocate and initialize walker.
657 w
= kzalloc(sizeof(*w
), GFP_ATOMIC
);
660 w
->func
= fib6_dump_node
;
661 cb
->args
[2] = (long)w
;
669 if (arg
.filter
.table_id
) {
670 tb
= fib6_get_table(net
, arg
.filter
.table_id
);
672 if (rtnl_msg_family(cb
->nlh
) != PF_INET6
)
675 NL_SET_ERR_MSG_MOD(cb
->extack
, "FIB table does not exist");
680 res
= fib6_dump_table(tb
, skb
, cb
);
691 for (h
= s_h
; h
< FIB6_TABLE_HASHSZ
; h
++, s_e
= 0) {
693 head
= &net
->ipv6
.fib_table_hash
[h
];
694 hlist_for_each_entry_rcu(tb
, head
, tb6_hlist
) {
697 res
= fib6_dump_table(tb
, skb
, cb
);
709 res
= res
< 0 ? res
: skb
->len
;
715 void fib6_metric_set(struct fib6_info
*f6i
, int metric
, u32 val
)
720 if (f6i
->fib6_metrics
== &dst_default_metrics
) {
721 struct dst_metrics
*p
= kzalloc(sizeof(*p
), GFP_ATOMIC
);
726 refcount_set(&p
->refcnt
, 1);
727 f6i
->fib6_metrics
= p
;
730 f6i
->fib6_metrics
->metrics
[metric
- 1] = val
;
736 * return the appropriate node for a routing tree "add" operation
737 * by either creating and inserting or by returning an existing
741 static struct fib6_node
*fib6_add_1(struct net
*net
,
742 struct fib6_table
*table
,
743 struct fib6_node
*root
,
744 struct in6_addr
*addr
, int plen
,
745 int offset
, int allow_create
,
746 int replace_required
,
747 struct netlink_ext_ack
*extack
)
749 struct fib6_node
*fn
, *in
, *ln
;
750 struct fib6_node
*pn
= NULL
;
755 RT6_TRACE("fib6_add_1\n");
757 /* insert node in tree */
762 struct fib6_info
*leaf
= rcu_dereference_protected(fn
->leaf
,
763 lockdep_is_held(&table
->tb6_lock
));
764 key
= (struct rt6key
*)((u8
*)leaf
+ offset
);
769 if (plen
< fn
->fn_bit
||
770 !ipv6_prefix_equal(&key
->addr
, addr
, fn
->fn_bit
)) {
772 if (replace_required
) {
773 NL_SET_ERR_MSG(extack
,
774 "Can not replace route - no match found");
775 pr_warn("Can't replace route, no match found\n");
776 return ERR_PTR(-ENOENT
);
778 pr_warn("NLM_F_CREATE should be set when creating new route\n");
787 if (plen
== fn
->fn_bit
) {
788 /* clean up an intermediate node */
789 if (!(fn
->fn_flags
& RTN_RTINFO
)) {
790 RCU_INIT_POINTER(fn
->leaf
, NULL
);
791 fib6_info_release(leaf
);
792 /* remove null_entry in the root node */
793 } else if (fn
->fn_flags
& RTN_TL_ROOT
&&
794 rcu_access_pointer(fn
->leaf
) ==
795 net
->ipv6
.fib6_null_entry
) {
796 RCU_INIT_POINTER(fn
->leaf
, NULL
);
803 * We have more bits to go
806 /* Try to walk down on tree. */
807 dir
= addr_bit_set(addr
, fn
->fn_bit
);
810 rcu_dereference_protected(fn
->right
,
811 lockdep_is_held(&table
->tb6_lock
)) :
812 rcu_dereference_protected(fn
->left
,
813 lockdep_is_held(&table
->tb6_lock
));
817 /* We should not create new node because
818 * NLM_F_REPLACE was specified without NLM_F_CREATE
819 * I assume it is safe to require NLM_F_CREATE when
820 * REPLACE flag is used! Later we may want to remove the
821 * check for replace_required, because according
822 * to netlink specification, NLM_F_CREATE
823 * MUST be specified if new route is created.
824 * That would keep IPv6 consistent with IPv4
826 if (replace_required
) {
827 NL_SET_ERR_MSG(extack
,
828 "Can not replace route - no match found");
829 pr_warn("Can't replace route, no match found\n");
830 return ERR_PTR(-ENOENT
);
832 pr_warn("NLM_F_CREATE should be set when creating new route\n");
835 * We walked to the bottom of tree.
836 * Create new leaf node without children.
839 ln
= node_alloc(net
);
842 return ERR_PTR(-ENOMEM
);
844 RCU_INIT_POINTER(ln
->parent
, pn
);
847 rcu_assign_pointer(pn
->right
, ln
);
849 rcu_assign_pointer(pn
->left
, ln
);
856 * split since we don't have a common prefix anymore or
857 * we have a less significant route.
858 * we've to insert an intermediate node on the list
859 * this new node will point to the one we need to create
863 pn
= rcu_dereference_protected(fn
->parent
,
864 lockdep_is_held(&table
->tb6_lock
));
866 /* find 1st bit in difference between the 2 addrs.
868 See comment in __ipv6_addr_diff: bit may be an invalid value,
869 but if it is >= plen, the value is ignored in any case.
872 bit
= __ipv6_addr_diff(addr
, &key
->addr
, sizeof(*addr
));
877 * (new leaf node)[ln] (old node)[fn]
880 in
= node_alloc(net
);
881 ln
= node_alloc(net
);
885 node_free_immediate(net
, in
);
887 node_free_immediate(net
, ln
);
888 return ERR_PTR(-ENOMEM
);
892 * new intermediate node.
894 * be off since that an address that chooses one of
895 * the branches would not match less specific routes
896 * in the other branch
901 RCU_INIT_POINTER(in
->parent
, pn
);
903 fib6_info_hold(rcu_dereference_protected(in
->leaf
,
904 lockdep_is_held(&table
->tb6_lock
)));
906 /* update parent pointer */
908 rcu_assign_pointer(pn
->right
, in
);
910 rcu_assign_pointer(pn
->left
, in
);
914 RCU_INIT_POINTER(ln
->parent
, in
);
915 rcu_assign_pointer(fn
->parent
, in
);
917 if (addr_bit_set(addr
, bit
)) {
918 rcu_assign_pointer(in
->right
, ln
);
919 rcu_assign_pointer(in
->left
, fn
);
921 rcu_assign_pointer(in
->left
, ln
);
922 rcu_assign_pointer(in
->right
, fn
);
924 } else { /* plen <= bit */
927 * (new leaf node)[ln]
929 * (old node)[fn] NULL
932 ln
= node_alloc(net
);
935 return ERR_PTR(-ENOMEM
);
939 RCU_INIT_POINTER(ln
->parent
, pn
);
941 if (addr_bit_set(&key
->addr
, plen
))
942 RCU_INIT_POINTER(ln
->right
, fn
);
944 RCU_INIT_POINTER(ln
->left
, fn
);
946 rcu_assign_pointer(fn
->parent
, ln
);
949 rcu_assign_pointer(pn
->right
, ln
);
951 rcu_assign_pointer(pn
->left
, ln
);
956 static void __fib6_drop_pcpu_from(struct fib6_nh
*fib6_nh
,
957 const struct fib6_info
*match
,
958 const struct fib6_table
*table
)
962 if (!fib6_nh
->rt6i_pcpu
)
965 /* release the reference to this fib entry from
966 * all of its cached pcpu routes
968 for_each_possible_cpu(cpu
) {
969 struct rt6_info
**ppcpu_rt
;
970 struct rt6_info
*pcpu_rt
;
972 ppcpu_rt
= per_cpu_ptr(fib6_nh
->rt6i_pcpu
, cpu
);
975 /* only dropping the 'from' reference if the cached route
976 * is using 'match'. The cached pcpu_rt->from only changes
977 * from a fib6_info to NULL (ip6_dst_destroy); it can never
978 * change from one fib6_info reference to another
980 if (pcpu_rt
&& rcu_access_pointer(pcpu_rt
->from
) == match
) {
981 struct fib6_info
*from
;
983 from
= xchg((__force
struct fib6_info
**)&pcpu_rt
->from
, NULL
);
984 fib6_info_release(from
);
989 struct fib6_nh_pcpu_arg
{
990 struct fib6_info
*from
;
991 const struct fib6_table
*table
;
994 static int fib6_nh_drop_pcpu_from(struct fib6_nh
*nh
, void *_arg
)
996 struct fib6_nh_pcpu_arg
*arg
= _arg
;
998 __fib6_drop_pcpu_from(nh
, arg
->from
, arg
->table
);
1002 static void fib6_drop_pcpu_from(struct fib6_info
*f6i
,
1003 const struct fib6_table
*table
)
1005 /* Make sure rt6_make_pcpu_route() wont add other percpu routes
1006 * while we are cleaning them here.
1008 f6i
->fib6_destroying
= 1;
1009 mb(); /* paired with the cmpxchg() in rt6_make_pcpu_route() */
1012 struct fib6_nh_pcpu_arg arg
= {
1017 nexthop_for_each_fib6_nh(f6i
->nh
, fib6_nh_drop_pcpu_from
,
1020 struct fib6_nh
*fib6_nh
;
1022 fib6_nh
= f6i
->fib6_nh
;
1023 __fib6_drop_pcpu_from(fib6_nh
, f6i
, table
);
1027 static void fib6_purge_rt(struct fib6_info
*rt
, struct fib6_node
*fn
,
1030 struct fib6_table
*table
= rt
->fib6_table
;
1032 /* Flush all cached dst in exception table */
1033 rt6_flush_exceptions(rt
);
1034 fib6_drop_pcpu_from(rt
, table
);
1036 if (rt
->nh
&& !list_empty(&rt
->nh_list
))
1037 list_del_init(&rt
->nh_list
);
1039 if (refcount_read(&rt
->fib6_ref
) != 1) {
1040 /* This route is used as dummy address holder in some split
1041 * nodes. It is not leaked, but it still holds other resources,
1042 * which must be released in time. So, scan ascendant nodes
1043 * and replace dummy references to this route with references
1044 * to still alive ones.
1047 struct fib6_info
*leaf
= rcu_dereference_protected(fn
->leaf
,
1048 lockdep_is_held(&table
->tb6_lock
));
1049 struct fib6_info
*new_leaf
;
1050 if (!(fn
->fn_flags
& RTN_RTINFO
) && leaf
== rt
) {
1051 new_leaf
= fib6_find_prefix(net
, table
, fn
);
1052 fib6_info_hold(new_leaf
);
1054 rcu_assign_pointer(fn
->leaf
, new_leaf
);
1055 fib6_info_release(rt
);
1057 fn
= rcu_dereference_protected(fn
->parent
,
1058 lockdep_is_held(&table
->tb6_lock
));
1064 * Insert routing information in a node.
1067 static int fib6_add_rt2node(struct fib6_node
*fn
, struct fib6_info
*rt
,
1068 struct nl_info
*info
,
1069 struct netlink_ext_ack
*extack
)
1071 struct fib6_info
*leaf
= rcu_dereference_protected(fn
->leaf
,
1072 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1073 struct fib6_info
*iter
= NULL
;
1074 struct fib6_info __rcu
**ins
;
1075 struct fib6_info __rcu
**fallback_ins
= NULL
;
1076 int replace
= (info
->nlh
&&
1077 (info
->nlh
->nlmsg_flags
& NLM_F_REPLACE
));
1078 int add
= (!info
->nlh
||
1079 (info
->nlh
->nlmsg_flags
& NLM_F_CREATE
));
1081 bool rt_can_ecmp
= rt6_qualify_for_ecmp(rt
);
1082 bool notify_sibling_rt
= false;
1083 u16 nlflags
= NLM_F_EXCL
;
1086 if (info
->nlh
&& (info
->nlh
->nlmsg_flags
& NLM_F_APPEND
))
1087 nlflags
|= NLM_F_APPEND
;
1091 for (iter
= leaf
; iter
;
1092 iter
= rcu_dereference_protected(iter
->fib6_next
,
1093 lockdep_is_held(&rt
->fib6_table
->tb6_lock
))) {
1095 * Search for duplicates
1098 if (iter
->fib6_metric
== rt
->fib6_metric
) {
1100 * Same priority level
1103 (info
->nlh
->nlmsg_flags
& NLM_F_EXCL
))
1106 nlflags
&= ~NLM_F_EXCL
;
1108 if (rt_can_ecmp
== rt6_qualify_for_ecmp(iter
)) {
1112 fallback_ins
= fallback_ins
?: ins
;
1116 if (rt6_duplicate_nexthop(iter
, rt
)) {
1117 if (rt
->fib6_nsiblings
)
1118 rt
->fib6_nsiblings
= 0;
1119 if (!(iter
->fib6_flags
& RTF_EXPIRES
))
1121 if (!(rt
->fib6_flags
& RTF_EXPIRES
))
1122 fib6_clean_expires(iter
);
1124 fib6_set_expires(iter
, rt
->expires
);
1127 fib6_metric_set(iter
, RTAX_MTU
,
1131 /* If we have the same destination and the same metric,
1132 * but not the same gateway, then the route we try to
1133 * add is sibling to this route, increment our counter
1134 * of siblings, and later we will add our route to the
1136 * Only static routes (which don't have flag
1137 * RTF_EXPIRES) are used for ECMPv6.
1139 * To avoid long list, we only had siblings if the
1140 * route have a gateway.
1143 rt6_qualify_for_ecmp(iter
))
1144 rt
->fib6_nsiblings
++;
1147 if (iter
->fib6_metric
> rt
->fib6_metric
)
1151 ins
= &iter
->fib6_next
;
1154 if (fallback_ins
&& !found
) {
1155 /* No matching route with same ecmp-able-ness found, replace
1156 * first matching route
1159 iter
= rcu_dereference_protected(*ins
,
1160 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1164 /* Reset round-robin state, if necessary */
1165 if (ins
== &fn
->leaf
)
1168 /* Link this route to others same route. */
1169 if (rt
->fib6_nsiblings
) {
1170 unsigned int fib6_nsiblings
;
1171 struct fib6_info
*sibling
, *temp_sibling
;
1173 /* Find the first route that have the same metric */
1175 notify_sibling_rt
= true;
1177 if (sibling
->fib6_metric
== rt
->fib6_metric
&&
1178 rt6_qualify_for_ecmp(sibling
)) {
1179 list_add_tail(&rt
->fib6_siblings
,
1180 &sibling
->fib6_siblings
);
1183 sibling
= rcu_dereference_protected(sibling
->fib6_next
,
1184 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1185 notify_sibling_rt
= false;
1187 /* For each sibling in the list, increment the counter of
1188 * siblings. BUG() if counters does not match, list of siblings
1192 list_for_each_entry_safe(sibling
, temp_sibling
,
1193 &rt
->fib6_siblings
, fib6_siblings
) {
1194 sibling
->fib6_nsiblings
++;
1195 BUG_ON(sibling
->fib6_nsiblings
!= rt
->fib6_nsiblings
);
1198 BUG_ON(fib6_nsiblings
!= rt
->fib6_nsiblings
);
1199 rt6_multipath_rebalance(temp_sibling
);
1207 pr_warn("NLM_F_CREATE should be set when creating new route\n");
1210 nlflags
|= NLM_F_CREATE
;
1212 /* The route should only be notified if it is the first
1213 * route in the node or if it is added as a sibling
1214 * route to the first route in the node.
1216 if (!info
->skip_notify_kernel
&&
1217 (notify_sibling_rt
|| ins
== &fn
->leaf
)) {
1218 enum fib_event_type fib_event
;
1220 if (notify_sibling_rt
)
1221 fib_event
= FIB_EVENT_ENTRY_APPEND
;
1223 fib_event
= FIB_EVENT_ENTRY_REPLACE
;
1224 err
= call_fib6_entry_notifiers(info
->nl_net
,
1228 struct fib6_info
*sibling
, *next_sibling
;
1230 /* If the route has siblings, then it first
1231 * needs to be unlinked from them.
1233 if (!rt
->fib6_nsiblings
)
1236 list_for_each_entry_safe(sibling
, next_sibling
,
1239 sibling
->fib6_nsiblings
--;
1240 rt
->fib6_nsiblings
= 0;
1241 list_del_init(&rt
->fib6_siblings
);
1242 rt6_multipath_rebalance(next_sibling
);
1247 rcu_assign_pointer(rt
->fib6_next
, iter
);
1249 rcu_assign_pointer(rt
->fib6_node
, fn
);
1250 rcu_assign_pointer(*ins
, rt
);
1251 if (!info
->skip_notify
)
1252 inet6_rt_notify(RTM_NEWROUTE
, rt
, info
, nlflags
);
1253 info
->nl_net
->ipv6
.rt6_stats
->fib_rt_entries
++;
1255 if (!(fn
->fn_flags
& RTN_RTINFO
)) {
1256 info
->nl_net
->ipv6
.rt6_stats
->fib_route_nodes
++;
1257 fn
->fn_flags
|= RTN_RTINFO
;
1266 pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
1270 if (!info
->skip_notify_kernel
&& ins
== &fn
->leaf
) {
1271 err
= call_fib6_entry_notifiers(info
->nl_net
,
1272 FIB_EVENT_ENTRY_REPLACE
,
1279 rcu_assign_pointer(rt
->fib6_node
, fn
);
1280 rt
->fib6_next
= iter
->fib6_next
;
1281 rcu_assign_pointer(*ins
, rt
);
1282 if (!info
->skip_notify
)
1283 inet6_rt_notify(RTM_NEWROUTE
, rt
, info
, NLM_F_REPLACE
);
1284 if (!(fn
->fn_flags
& RTN_RTINFO
)) {
1285 info
->nl_net
->ipv6
.rt6_stats
->fib_route_nodes
++;
1286 fn
->fn_flags
|= RTN_RTINFO
;
1288 nsiblings
= iter
->fib6_nsiblings
;
1289 iter
->fib6_node
= NULL
;
1290 fib6_purge_rt(iter
, fn
, info
->nl_net
);
1291 if (rcu_access_pointer(fn
->rr_ptr
) == iter
)
1293 fib6_info_release(iter
);
1296 /* Replacing an ECMP route, remove all siblings */
1297 ins
= &rt
->fib6_next
;
1298 iter
= rcu_dereference_protected(*ins
,
1299 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1301 if (iter
->fib6_metric
> rt
->fib6_metric
)
1303 if (rt6_qualify_for_ecmp(iter
)) {
1304 *ins
= iter
->fib6_next
;
1305 iter
->fib6_node
= NULL
;
1306 fib6_purge_rt(iter
, fn
, info
->nl_net
);
1307 if (rcu_access_pointer(fn
->rr_ptr
) == iter
)
1309 fib6_info_release(iter
);
1311 info
->nl_net
->ipv6
.rt6_stats
->fib_rt_entries
--;
1313 ins
= &iter
->fib6_next
;
1315 iter
= rcu_dereference_protected(*ins
,
1316 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1318 WARN_ON(nsiblings
!= 0);
1325 static void fib6_start_gc(struct net
*net
, struct fib6_info
*rt
)
1327 if (!timer_pending(&net
->ipv6
.ip6_fib_timer
) &&
1328 (rt
->fib6_flags
& RTF_EXPIRES
))
1329 mod_timer(&net
->ipv6
.ip6_fib_timer
,
1330 jiffies
+ net
->ipv6
.sysctl
.ip6_rt_gc_interval
);
1333 void fib6_force_start_gc(struct net
*net
)
1335 if (!timer_pending(&net
->ipv6
.ip6_fib_timer
))
1336 mod_timer(&net
->ipv6
.ip6_fib_timer
,
1337 jiffies
+ net
->ipv6
.sysctl
.ip6_rt_gc_interval
);
1340 static void __fib6_update_sernum_upto_root(struct fib6_info
*rt
,
1343 struct fib6_node
*fn
= rcu_dereference_protected(rt
->fib6_node
,
1344 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1346 /* paired with smp_rmb() in fib6_get_cookie_safe() */
1349 WRITE_ONCE(fn
->fn_sernum
, sernum
);
1350 fn
= rcu_dereference_protected(fn
->parent
,
1351 lockdep_is_held(&rt
->fib6_table
->tb6_lock
));
1355 void fib6_update_sernum_upto_root(struct net
*net
, struct fib6_info
*rt
)
1357 __fib6_update_sernum_upto_root(rt
, fib6_new_sernum(net
));
1360 /* allow ipv4 to update sernum via ipv6_stub */
1361 void fib6_update_sernum_stub(struct net
*net
, struct fib6_info
*f6i
)
1363 spin_lock_bh(&f6i
->fib6_table
->tb6_lock
);
1364 fib6_update_sernum_upto_root(net
, f6i
);
1365 spin_unlock_bh(&f6i
->fib6_table
->tb6_lock
);
1369 * Add routing information to the routing tree.
1370 * <destination addr>/<source addr>
1371 * with source addr info in sub-trees
1372 * Need to own table->tb6_lock
1375 int fib6_add(struct fib6_node
*root
, struct fib6_info
*rt
,
1376 struct nl_info
*info
, struct netlink_ext_ack
*extack
)
1378 struct fib6_table
*table
= rt
->fib6_table
;
1379 struct fib6_node
*fn
, *pn
= NULL
;
1381 int allow_create
= 1;
1382 int replace_required
= 0;
1385 if (!(info
->nlh
->nlmsg_flags
& NLM_F_CREATE
))
1387 if (info
->nlh
->nlmsg_flags
& NLM_F_REPLACE
)
1388 replace_required
= 1;
1390 if (!allow_create
&& !replace_required
)
1391 pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
1393 fn
= fib6_add_1(info
->nl_net
, table
, root
,
1394 &rt
->fib6_dst
.addr
, rt
->fib6_dst
.plen
,
1395 offsetof(struct fib6_info
, fib6_dst
), allow_create
,
1396 replace_required
, extack
);
1405 #ifdef CONFIG_IPV6_SUBTREES
1406 if (rt
->fib6_src
.plen
) {
1407 struct fib6_node
*sn
;
1409 if (!rcu_access_pointer(fn
->subtree
)) {
1410 struct fib6_node
*sfn
;
1422 /* Create subtree root node */
1423 sfn
= node_alloc(info
->nl_net
);
1427 fib6_info_hold(info
->nl_net
->ipv6
.fib6_null_entry
);
1428 rcu_assign_pointer(sfn
->leaf
,
1429 info
->nl_net
->ipv6
.fib6_null_entry
);
1430 sfn
->fn_flags
= RTN_ROOT
;
1432 /* Now add the first leaf node to new subtree */
1434 sn
= fib6_add_1(info
->nl_net
, table
, sfn
,
1435 &rt
->fib6_src
.addr
, rt
->fib6_src
.plen
,
1436 offsetof(struct fib6_info
, fib6_src
),
1437 allow_create
, replace_required
, extack
);
1440 /* If it is failed, discard just allocated
1441 root, and then (in failure) stale node
1444 node_free_immediate(info
->nl_net
, sfn
);
1449 /* Now link new subtree to main tree */
1450 rcu_assign_pointer(sfn
->parent
, fn
);
1451 rcu_assign_pointer(fn
->subtree
, sfn
);
1453 sn
= fib6_add_1(info
->nl_net
, table
, FIB6_SUBTREE(fn
),
1454 &rt
->fib6_src
.addr
, rt
->fib6_src
.plen
,
1455 offsetof(struct fib6_info
, fib6_src
),
1456 allow_create
, replace_required
, extack
);
1464 if (!rcu_access_pointer(fn
->leaf
)) {
1465 if (fn
->fn_flags
& RTN_TL_ROOT
) {
1466 /* put back null_entry for root node */
1467 rcu_assign_pointer(fn
->leaf
,
1468 info
->nl_net
->ipv6
.fib6_null_entry
);
1471 rcu_assign_pointer(fn
->leaf
, rt
);
1478 err
= fib6_add_rt2node(fn
, rt
, info
, extack
);
1481 list_add(&rt
->nh_list
, &rt
->nh
->f6i_list
);
1482 __fib6_update_sernum_upto_root(rt
, fib6_new_sernum(info
->nl_net
));
1483 fib6_start_gc(info
->nl_net
, rt
);
1488 #ifdef CONFIG_IPV6_SUBTREES
1490 * If fib6_add_1 has cleared the old leaf pointer in the
1491 * super-tree leaf node we have to find a new one for it.
1494 struct fib6_info
*pn_leaf
=
1495 rcu_dereference_protected(pn
->leaf
,
1496 lockdep_is_held(&table
->tb6_lock
));
1497 if (pn_leaf
== rt
) {
1499 RCU_INIT_POINTER(pn
->leaf
, NULL
);
1500 fib6_info_release(rt
);
1502 if (!pn_leaf
&& !(pn
->fn_flags
& RTN_RTINFO
)) {
1503 pn_leaf
= fib6_find_prefix(info
->nl_net
, table
,
1509 info
->nl_net
->ipv6
.fib6_null_entry
;
1512 fib6_info_hold(pn_leaf
);
1513 rcu_assign_pointer(pn
->leaf
, pn_leaf
);
1518 } else if (fib6_requires_src(rt
)) {
1519 fib6_routes_require_src_inc(info
->nl_net
);
1524 /* fn->leaf could be NULL and fib6_repair_tree() needs to be called if:
1525 * 1. fn is an intermediate node and we failed to add the new
1526 * route to it in both subtree creation failure and fib6_add_rt2node()
1528 * 2. fn is the root node in the table and we fail to add the first
1529 * default route to it.
1532 (!(fn
->fn_flags
& (RTN_RTINFO
|RTN_ROOT
)) ||
1533 (fn
->fn_flags
& RTN_TL_ROOT
&&
1534 !rcu_access_pointer(fn
->leaf
))))
1535 fib6_repair_tree(info
->nl_net
, table
, fn
);
1540 * Routing tree lookup
1544 struct lookup_args
{
1545 int offset
; /* key offset on fib6_info */
1546 const struct in6_addr
*addr
; /* search key */
1549 static struct fib6_node
*fib6_node_lookup_1(struct fib6_node
*root
,
1550 struct lookup_args
*args
)
1552 struct fib6_node
*fn
;
1555 if (unlikely(args
->offset
== 0))
1565 struct fib6_node
*next
;
1567 dir
= addr_bit_set(args
->addr
, fn
->fn_bit
);
1569 next
= dir
? rcu_dereference(fn
->right
) :
1570 rcu_dereference(fn
->left
);
1580 struct fib6_node
*subtree
= FIB6_SUBTREE(fn
);
1582 if (subtree
|| fn
->fn_flags
& RTN_RTINFO
) {
1583 struct fib6_info
*leaf
= rcu_dereference(fn
->leaf
);
1589 key
= (struct rt6key
*) ((u8
*)leaf
+ args
->offset
);
1591 if (ipv6_prefix_equal(&key
->addr
, args
->addr
, key
->plen
)) {
1592 #ifdef CONFIG_IPV6_SUBTREES
1594 struct fib6_node
*sfn
;
1595 sfn
= fib6_node_lookup_1(subtree
,
1602 if (fn
->fn_flags
& RTN_RTINFO
)
1607 if (fn
->fn_flags
& RTN_ROOT
)
1610 fn
= rcu_dereference(fn
->parent
);
1616 /* called with rcu_read_lock() held
1618 struct fib6_node
*fib6_node_lookup(struct fib6_node
*root
,
1619 const struct in6_addr
*daddr
,
1620 const struct in6_addr
*saddr
)
1622 struct fib6_node
*fn
;
1623 struct lookup_args args
[] = {
1625 .offset
= offsetof(struct fib6_info
, fib6_dst
),
1628 #ifdef CONFIG_IPV6_SUBTREES
1630 .offset
= offsetof(struct fib6_info
, fib6_src
),
1635 .offset
= 0, /* sentinel */
1639 fn
= fib6_node_lookup_1(root
, daddr
? args
: args
+ 1);
1640 if (!fn
|| fn
->fn_flags
& RTN_TL_ROOT
)
1647 * Get node with specified destination prefix (and source prefix,
1648 * if subtrees are used)
1649 * exact_match == true means we try to find fn with exact match of
1650 * the passed in prefix addr
1651 * exact_match == false means we try to find fn with longest prefix
1652 * match of the passed in prefix addr. This is useful for finding fn
1653 * for cached route as it will be stored in the exception table under
1654 * the node with longest prefix length.
1658 static struct fib6_node
*fib6_locate_1(struct fib6_node
*root
,
1659 const struct in6_addr
*addr
,
1660 int plen
, int offset
,
1663 struct fib6_node
*fn
, *prev
= NULL
;
1665 for (fn
= root
; fn
; ) {
1666 struct fib6_info
*leaf
= rcu_dereference(fn
->leaf
);
1669 /* This node is being deleted */
1671 if (plen
<= fn
->fn_bit
)
1677 key
= (struct rt6key
*)((u8
*)leaf
+ offset
);
1682 if (plen
< fn
->fn_bit
||
1683 !ipv6_prefix_equal(&key
->addr
, addr
, fn
->fn_bit
))
1686 if (plen
== fn
->fn_bit
)
1689 if (fn
->fn_flags
& RTN_RTINFO
)
1694 * We have more bits to go
1696 if (addr_bit_set(addr
, fn
->fn_bit
))
1697 fn
= rcu_dereference(fn
->right
);
1699 fn
= rcu_dereference(fn
->left
);
1708 struct fib6_node
*fib6_locate(struct fib6_node
*root
,
1709 const struct in6_addr
*daddr
, int dst_len
,
1710 const struct in6_addr
*saddr
, int src_len
,
1713 struct fib6_node
*fn
;
1715 fn
= fib6_locate_1(root
, daddr
, dst_len
,
1716 offsetof(struct fib6_info
, fib6_dst
),
1719 #ifdef CONFIG_IPV6_SUBTREES
1721 WARN_ON(saddr
== NULL
);
1723 struct fib6_node
*subtree
= FIB6_SUBTREE(fn
);
1726 fn
= fib6_locate_1(subtree
, saddr
, src_len
,
1727 offsetof(struct fib6_info
, fib6_src
),
1734 if (fn
&& fn
->fn_flags
& RTN_RTINFO
)
1746 static struct fib6_info
*fib6_find_prefix(struct net
*net
,
1747 struct fib6_table
*table
,
1748 struct fib6_node
*fn
)
1750 struct fib6_node
*child_left
, *child_right
;
1752 if (fn
->fn_flags
& RTN_ROOT
)
1753 return net
->ipv6
.fib6_null_entry
;
1756 child_left
= rcu_dereference_protected(fn
->left
,
1757 lockdep_is_held(&table
->tb6_lock
));
1758 child_right
= rcu_dereference_protected(fn
->right
,
1759 lockdep_is_held(&table
->tb6_lock
));
1761 return rcu_dereference_protected(child_left
->leaf
,
1762 lockdep_is_held(&table
->tb6_lock
));
1764 return rcu_dereference_protected(child_right
->leaf
,
1765 lockdep_is_held(&table
->tb6_lock
));
1767 fn
= FIB6_SUBTREE(fn
);
1773 * Called to trim the tree of intermediate nodes when possible. "fn"
1774 * is the node we want to try and remove.
1775 * Need to own table->tb6_lock
1778 static struct fib6_node
*fib6_repair_tree(struct net
*net
,
1779 struct fib6_table
*table
,
1780 struct fib6_node
*fn
)
1784 struct fib6_node
*child
;
1785 struct fib6_walker
*w
;
1788 /* Set fn->leaf to null_entry for root node. */
1789 if (fn
->fn_flags
& RTN_TL_ROOT
) {
1790 rcu_assign_pointer(fn
->leaf
, net
->ipv6
.fib6_null_entry
);
1795 struct fib6_node
*fn_r
= rcu_dereference_protected(fn
->right
,
1796 lockdep_is_held(&table
->tb6_lock
));
1797 struct fib6_node
*fn_l
= rcu_dereference_protected(fn
->left
,
1798 lockdep_is_held(&table
->tb6_lock
));
1799 struct fib6_node
*pn
= rcu_dereference_protected(fn
->parent
,
1800 lockdep_is_held(&table
->tb6_lock
));
1801 struct fib6_node
*pn_r
= rcu_dereference_protected(pn
->right
,
1802 lockdep_is_held(&table
->tb6_lock
));
1803 struct fib6_node
*pn_l
= rcu_dereference_protected(pn
->left
,
1804 lockdep_is_held(&table
->tb6_lock
));
1805 struct fib6_info
*fn_leaf
= rcu_dereference_protected(fn
->leaf
,
1806 lockdep_is_held(&table
->tb6_lock
));
1807 struct fib6_info
*pn_leaf
= rcu_dereference_protected(pn
->leaf
,
1808 lockdep_is_held(&table
->tb6_lock
));
1809 struct fib6_info
*new_fn_leaf
;
1811 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn
->fn_bit
, iter
);
1814 WARN_ON(fn
->fn_flags
& RTN_RTINFO
);
1815 WARN_ON(fn
->fn_flags
& RTN_TL_ROOT
);
1829 if (children
== 3 || FIB6_SUBTREE(fn
)
1830 #ifdef CONFIG_IPV6_SUBTREES
1831 /* Subtree root (i.e. fn) may have one child */
1832 || (children
&& fn
->fn_flags
& RTN_ROOT
)
1835 new_fn_leaf
= fib6_find_prefix(net
, table
, fn
);
1838 WARN_ON(!new_fn_leaf
);
1839 new_fn_leaf
= net
->ipv6
.fib6_null_entry
;
1842 fib6_info_hold(new_fn_leaf
);
1843 rcu_assign_pointer(fn
->leaf
, new_fn_leaf
);
1847 #ifdef CONFIG_IPV6_SUBTREES
1848 if (FIB6_SUBTREE(pn
) == fn
) {
1849 WARN_ON(!(fn
->fn_flags
& RTN_ROOT
));
1850 RCU_INIT_POINTER(pn
->subtree
, NULL
);
1853 WARN_ON(fn
->fn_flags
& RTN_ROOT
);
1856 rcu_assign_pointer(pn
->right
, child
);
1857 else if (pn_l
== fn
)
1858 rcu_assign_pointer(pn
->left
, child
);
1864 rcu_assign_pointer(child
->parent
, pn
);
1866 #ifdef CONFIG_IPV6_SUBTREES
1870 read_lock(&net
->ipv6
.fib6_walker_lock
);
1871 FOR_WALKERS(net
, w
) {
1873 if (w
->node
== fn
) {
1874 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w
, w
->state
, nstate
);
1879 if (w
->node
== fn
) {
1882 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w
, w
->state
);
1883 w
->state
= w
->state
>= FWS_R
? FWS_U
: FWS_INIT
;
1885 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w
, w
->state
);
1886 w
->state
= w
->state
>= FWS_C
? FWS_U
: FWS_INIT
;
1891 read_unlock(&net
->ipv6
.fib6_walker_lock
);
1894 if (pn
->fn_flags
& RTN_RTINFO
|| FIB6_SUBTREE(pn
))
1897 RCU_INIT_POINTER(pn
->leaf
, NULL
);
1898 fib6_info_release(pn_leaf
);
1903 static void fib6_del_route(struct fib6_table
*table
, struct fib6_node
*fn
,
1904 struct fib6_info __rcu
**rtp
, struct nl_info
*info
)
1906 struct fib6_info
*leaf
, *replace_rt
= NULL
;
1907 struct fib6_walker
*w
;
1908 struct fib6_info
*rt
= rcu_dereference_protected(*rtp
,
1909 lockdep_is_held(&table
->tb6_lock
));
1910 struct net
*net
= info
->nl_net
;
1911 bool notify_del
= false;
1913 RT6_TRACE("fib6_del_route\n");
1915 /* If the deleted route is the first in the node and it is not part of
1916 * a multipath route, then we need to replace it with the next route
1917 * in the node, if exists.
1919 leaf
= rcu_dereference_protected(fn
->leaf
,
1920 lockdep_is_held(&table
->tb6_lock
));
1921 if (leaf
== rt
&& !rt
->fib6_nsiblings
) {
1922 if (rcu_access_pointer(rt
->fib6_next
))
1923 replace_rt
= rcu_dereference_protected(rt
->fib6_next
,
1924 lockdep_is_held(&table
->tb6_lock
));
1930 *rtp
= rt
->fib6_next
;
1931 rt
->fib6_node
= NULL
;
1932 net
->ipv6
.rt6_stats
->fib_rt_entries
--;
1933 net
->ipv6
.rt6_stats
->fib_discarded_routes
++;
1935 /* Reset round-robin state, if necessary */
1936 if (rcu_access_pointer(fn
->rr_ptr
) == rt
)
1939 /* Remove this entry from other siblings */
1940 if (rt
->fib6_nsiblings
) {
1941 struct fib6_info
*sibling
, *next_sibling
;
1943 /* The route is deleted from a multipath route. If this
1944 * multipath route is the first route in the node, then we need
1945 * to emit a delete notification. Otherwise, we need to skip
1948 if (rt
->fib6_metric
== leaf
->fib6_metric
&&
1949 rt6_qualify_for_ecmp(leaf
))
1951 list_for_each_entry_safe(sibling
, next_sibling
,
1952 &rt
->fib6_siblings
, fib6_siblings
)
1953 sibling
->fib6_nsiblings
--;
1954 rt
->fib6_nsiblings
= 0;
1955 list_del_init(&rt
->fib6_siblings
);
1956 rt6_multipath_rebalance(next_sibling
);
1959 /* Adjust walkers */
1960 read_lock(&net
->ipv6
.fib6_walker_lock
);
1961 FOR_WALKERS(net
, w
) {
1962 if (w
->state
== FWS_C
&& w
->leaf
== rt
) {
1963 RT6_TRACE("walker %p adjusted by delroute\n", w
);
1964 w
->leaf
= rcu_dereference_protected(rt
->fib6_next
,
1965 lockdep_is_held(&table
->tb6_lock
));
1970 read_unlock(&net
->ipv6
.fib6_walker_lock
);
1972 /* If it was last route, call fib6_repair_tree() to:
1973 * 1. For root node, put back null_entry as how the table was created.
1974 * 2. For other nodes, expunge its radix tree node.
1976 if (!rcu_access_pointer(fn
->leaf
)) {
1977 if (!(fn
->fn_flags
& RTN_TL_ROOT
)) {
1978 fn
->fn_flags
&= ~RTN_RTINFO
;
1979 net
->ipv6
.rt6_stats
->fib_route_nodes
--;
1981 fn
= fib6_repair_tree(net
, table
, fn
);
1984 fib6_purge_rt(rt
, fn
, net
);
1986 if (!info
->skip_notify_kernel
) {
1988 call_fib6_entry_notifiers(net
, FIB_EVENT_ENTRY_DEL
,
1990 else if (replace_rt
)
1991 call_fib6_entry_notifiers_replace(net
, replace_rt
);
1993 if (!info
->skip_notify
)
1994 inet6_rt_notify(RTM_DELROUTE
, rt
, info
, 0);
1996 fib6_info_release(rt
);
1999 /* Need to own table->tb6_lock */
2000 int fib6_del(struct fib6_info
*rt
, struct nl_info
*info
)
2002 struct net
*net
= info
->nl_net
;
2003 struct fib6_info __rcu
**rtp
;
2004 struct fib6_info __rcu
**rtp_next
;
2005 struct fib6_table
*table
;
2006 struct fib6_node
*fn
;
2008 if (rt
== net
->ipv6
.fib6_null_entry
)
2011 table
= rt
->fib6_table
;
2012 fn
= rcu_dereference_protected(rt
->fib6_node
,
2013 lockdep_is_held(&table
->tb6_lock
));
2017 WARN_ON(!(fn
->fn_flags
& RTN_RTINFO
));
2020 * Walk the leaf entries looking for ourself
2023 for (rtp
= &fn
->leaf
; *rtp
; rtp
= rtp_next
) {
2024 struct fib6_info
*cur
= rcu_dereference_protected(*rtp
,
2025 lockdep_is_held(&table
->tb6_lock
));
2027 if (fib6_requires_src(cur
))
2028 fib6_routes_require_src_dec(info
->nl_net
);
2029 fib6_del_route(table
, fn
, rtp
, info
);
2032 rtp_next
= &cur
->fib6_next
;
2038 * Tree traversal function.
2040 * Certainly, it is not interrupt safe.
2041 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
2042 * It means, that we can modify tree during walking
2043 * and use this function for garbage collection, clone pruning,
2044 * cleaning tree when a device goes down etc. etc.
2046 * It guarantees that every node will be traversed,
2047 * and that it will be traversed only once.
2049 * Callback function w->func may return:
2050 * 0 -> continue walking.
2051 * positive value -> walking is suspended (used by tree dumps,
2052 * and probably by gc, if it will be split to several slices)
2053 * negative value -> terminate walking.
2055 * The function itself returns:
2056 * 0 -> walk is complete.
2057 * >0 -> walk is incomplete (i.e. suspended)
2058 * <0 -> walk is terminated by an error.
2060 * This function is called with tb6_lock held.
2063 static int fib6_walk_continue(struct fib6_walker
*w
)
2065 struct fib6_node
*fn
, *pn
, *left
, *right
;
2067 /* w->root should always be table->tb6_root */
2068 WARN_ON_ONCE(!(w
->root
->fn_flags
& RTN_TL_ROOT
));
2076 #ifdef CONFIG_IPV6_SUBTREES
2078 if (FIB6_SUBTREE(fn
)) {
2079 w
->node
= FIB6_SUBTREE(fn
);
2086 left
= rcu_dereference_protected(fn
->left
, 1);
2089 w
->state
= FWS_INIT
;
2095 right
= rcu_dereference_protected(fn
->right
, 1);
2098 w
->state
= FWS_INIT
;
2102 w
->leaf
= rcu_dereference_protected(fn
->leaf
, 1);
2105 if (w
->leaf
&& fn
->fn_flags
& RTN_RTINFO
) {
2126 pn
= rcu_dereference_protected(fn
->parent
, 1);
2127 left
= rcu_dereference_protected(pn
->left
, 1);
2128 right
= rcu_dereference_protected(pn
->right
, 1);
2130 #ifdef CONFIG_IPV6_SUBTREES
2131 if (FIB6_SUBTREE(pn
) == fn
) {
2132 WARN_ON(!(fn
->fn_flags
& RTN_ROOT
));
2143 w
->leaf
= rcu_dereference_protected(w
->node
->leaf
, 1);
2153 static int fib6_walk(struct net
*net
, struct fib6_walker
*w
)
2157 w
->state
= FWS_INIT
;
2160 fib6_walker_link(net
, w
);
2161 res
= fib6_walk_continue(w
);
2163 fib6_walker_unlink(net
, w
);
2167 static int fib6_clean_node(struct fib6_walker
*w
)
2170 struct fib6_info
*rt
;
2171 struct fib6_cleaner
*c
= container_of(w
, struct fib6_cleaner
, w
);
2172 struct nl_info info
= {
2174 .skip_notify
= c
->skip_notify
,
2177 if (c
->sernum
!= FIB6_NO_SERNUM_CHANGE
&&
2178 READ_ONCE(w
->node
->fn_sernum
) != c
->sernum
)
2179 WRITE_ONCE(w
->node
->fn_sernum
, c
->sernum
);
2182 WARN_ON_ONCE(c
->sernum
== FIB6_NO_SERNUM_CHANGE
);
2187 for_each_fib6_walker_rt(w
) {
2188 res
= c
->func(rt
, c
->arg
);
2191 res
= fib6_del(rt
, &info
);
2194 pr_debug("%s: del failed: rt=%p@%p err=%d\n",
2196 rcu_access_pointer(rt
->fib6_node
),
2202 } else if (res
== -2) {
2203 if (WARN_ON(!rt
->fib6_nsiblings
))
2205 rt
= list_last_entry(&rt
->fib6_siblings
,
2206 struct fib6_info
, fib6_siblings
);
2216 * Convenient frontend to tree walker.
2218 * func is called on each route.
2219 * It may return -2 -> skip multipath route.
2220 * -1 -> delete this route.
2221 * 0 -> continue walking
2224 static void fib6_clean_tree(struct net
*net
, struct fib6_node
*root
,
2225 int (*func
)(struct fib6_info
*, void *arg
),
2226 int sernum
, void *arg
, bool skip_notify
)
2228 struct fib6_cleaner c
;
2231 c
.w
.func
= fib6_clean_node
;
2234 c
.w
.skip_in_node
= 0;
2239 c
.skip_notify
= skip_notify
;
2241 fib6_walk(net
, &c
.w
);
2244 static void __fib6_clean_all(struct net
*net
,
2245 int (*func
)(struct fib6_info
*, void *),
2246 int sernum
, void *arg
, bool skip_notify
)
2248 struct fib6_table
*table
;
2249 struct hlist_head
*head
;
2253 for (h
= 0; h
< FIB6_TABLE_HASHSZ
; h
++) {
2254 head
= &net
->ipv6
.fib_table_hash
[h
];
2255 hlist_for_each_entry_rcu(table
, head
, tb6_hlist
) {
2256 spin_lock_bh(&table
->tb6_lock
);
2257 fib6_clean_tree(net
, &table
->tb6_root
,
2258 func
, sernum
, arg
, skip_notify
);
2259 spin_unlock_bh(&table
->tb6_lock
);
2265 void fib6_clean_all(struct net
*net
, int (*func
)(struct fib6_info
*, void *),
2268 __fib6_clean_all(net
, func
, FIB6_NO_SERNUM_CHANGE
, arg
, false);
2271 void fib6_clean_all_skip_notify(struct net
*net
,
2272 int (*func
)(struct fib6_info
*, void *),
2275 __fib6_clean_all(net
, func
, FIB6_NO_SERNUM_CHANGE
, arg
, true);
2278 static void fib6_flush_trees(struct net
*net
)
2280 int new_sernum
= fib6_new_sernum(net
);
2282 __fib6_clean_all(net
, NULL
, new_sernum
, NULL
, false);
2286 * Garbage collection
2289 static int fib6_age(struct fib6_info
*rt
, void *arg
)
2291 struct fib6_gc_args
*gc_args
= arg
;
2292 unsigned long now
= jiffies
;
2295 * check addrconf expiration here.
2296 * Routes are expired even if they are in use.
2299 if (rt
->fib6_flags
& RTF_EXPIRES
&& rt
->expires
) {
2300 if (time_after(now
, rt
->expires
)) {
2301 RT6_TRACE("expiring %p\n", rt
);
2307 /* Also age clones in the exception table.
2308 * Note, that clones are aged out
2309 * only if they are not in use now.
2311 rt6_age_exceptions(rt
, gc_args
, now
);
2316 void fib6_run_gc(unsigned long expires
, struct net
*net
, bool force
)
2318 struct fib6_gc_args gc_args
;
2322 spin_lock_bh(&net
->ipv6
.fib6_gc_lock
);
2323 } else if (!spin_trylock_bh(&net
->ipv6
.fib6_gc_lock
)) {
2324 mod_timer(&net
->ipv6
.ip6_fib_timer
, jiffies
+ HZ
);
2327 gc_args
.timeout
= expires
? (int)expires
:
2328 net
->ipv6
.sysctl
.ip6_rt_gc_interval
;
2331 fib6_clean_all(net
, fib6_age
, &gc_args
);
2333 net
->ipv6
.ip6_rt_last_gc
= now
;
2336 mod_timer(&net
->ipv6
.ip6_fib_timer
,
2338 + net
->ipv6
.sysctl
.ip6_rt_gc_interval
));
2340 del_timer(&net
->ipv6
.ip6_fib_timer
);
2341 spin_unlock_bh(&net
->ipv6
.fib6_gc_lock
);
2344 static void fib6_gc_timer_cb(struct timer_list
*t
)
2346 struct net
*arg
= from_timer(arg
, t
, ipv6
.ip6_fib_timer
);
2348 fib6_run_gc(0, arg
, true);
2351 static int __net_init
fib6_net_init(struct net
*net
)
2353 size_t size
= sizeof(struct hlist_head
) * FIB6_TABLE_HASHSZ
;
2356 err
= fib6_notifier_init(net
);
2360 /* Default to 3-tuple */
2361 net
->ipv6
.sysctl
.multipath_hash_fields
=
2362 FIB_MULTIPATH_HASH_FIELD_DEFAULT_MASK
;
2364 spin_lock_init(&net
->ipv6
.fib6_gc_lock
);
2365 rwlock_init(&net
->ipv6
.fib6_walker_lock
);
2366 INIT_LIST_HEAD(&net
->ipv6
.fib6_walkers
);
2367 timer_setup(&net
->ipv6
.ip6_fib_timer
, fib6_gc_timer_cb
, 0);
2369 net
->ipv6
.rt6_stats
= kzalloc(sizeof(*net
->ipv6
.rt6_stats
), GFP_KERNEL
);
2370 if (!net
->ipv6
.rt6_stats
)
2373 /* Avoid false sharing : Use at least a full cache line */
2374 size
= max_t(size_t, size
, L1_CACHE_BYTES
);
2376 net
->ipv6
.fib_table_hash
= kzalloc(size
, GFP_KERNEL
);
2377 if (!net
->ipv6
.fib_table_hash
)
2380 net
->ipv6
.fib6_main_tbl
= kzalloc(sizeof(*net
->ipv6
.fib6_main_tbl
),
2382 if (!net
->ipv6
.fib6_main_tbl
)
2383 goto out_fib_table_hash
;
2385 net
->ipv6
.fib6_main_tbl
->tb6_id
= RT6_TABLE_MAIN
;
2386 rcu_assign_pointer(net
->ipv6
.fib6_main_tbl
->tb6_root
.leaf
,
2387 net
->ipv6
.fib6_null_entry
);
2388 net
->ipv6
.fib6_main_tbl
->tb6_root
.fn_flags
=
2389 RTN_ROOT
| RTN_TL_ROOT
| RTN_RTINFO
;
2390 inet_peer_base_init(&net
->ipv6
.fib6_main_tbl
->tb6_peers
);
2392 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
2393 net
->ipv6
.fib6_local_tbl
= kzalloc(sizeof(*net
->ipv6
.fib6_local_tbl
),
2395 if (!net
->ipv6
.fib6_local_tbl
)
2396 goto out_fib6_main_tbl
;
2397 net
->ipv6
.fib6_local_tbl
->tb6_id
= RT6_TABLE_LOCAL
;
2398 rcu_assign_pointer(net
->ipv6
.fib6_local_tbl
->tb6_root
.leaf
,
2399 net
->ipv6
.fib6_null_entry
);
2400 net
->ipv6
.fib6_local_tbl
->tb6_root
.fn_flags
=
2401 RTN_ROOT
| RTN_TL_ROOT
| RTN_RTINFO
;
2402 inet_peer_base_init(&net
->ipv6
.fib6_local_tbl
->tb6_peers
);
2404 fib6_tables_init(net
);
2408 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
2410 kfree(net
->ipv6
.fib6_main_tbl
);
2413 kfree(net
->ipv6
.fib_table_hash
);
2415 kfree(net
->ipv6
.rt6_stats
);
2417 fib6_notifier_exit(net
);
2421 static void fib6_net_exit(struct net
*net
)
2425 del_timer_sync(&net
->ipv6
.ip6_fib_timer
);
2427 for (i
= 0; i
< FIB6_TABLE_HASHSZ
; i
++) {
2428 struct hlist_head
*head
= &net
->ipv6
.fib_table_hash
[i
];
2429 struct hlist_node
*tmp
;
2430 struct fib6_table
*tb
;
2432 hlist_for_each_entry_safe(tb
, tmp
, head
, tb6_hlist
) {
2433 hlist_del(&tb
->tb6_hlist
);
2434 fib6_free_table(tb
);
2438 kfree(net
->ipv6
.fib_table_hash
);
2439 kfree(net
->ipv6
.rt6_stats
);
2440 fib6_notifier_exit(net
);
2443 static struct pernet_operations fib6_net_ops
= {
2444 .init
= fib6_net_init
,
2445 .exit
= fib6_net_exit
,
2448 int __init
fib6_init(void)
2452 fib6_node_kmem
= kmem_cache_create("fib6_nodes",
2453 sizeof(struct fib6_node
), 0,
2454 SLAB_HWCACHE_ALIGN
| SLAB_ACCOUNT
,
2456 if (!fib6_node_kmem
)
2459 ret
= register_pernet_subsys(&fib6_net_ops
);
2461 goto out_kmem_cache_create
;
2463 ret
= rtnl_register_module(THIS_MODULE
, PF_INET6
, RTM_GETROUTE
, NULL
,
2466 goto out_unregister_subsys
;
2468 __fib6_flush_trees
= fib6_flush_trees
;
2472 out_unregister_subsys
:
2473 unregister_pernet_subsys(&fib6_net_ops
);
2474 out_kmem_cache_create
:
2475 kmem_cache_destroy(fib6_node_kmem
);
2479 void fib6_gc_cleanup(void)
2481 unregister_pernet_subsys(&fib6_net_ops
);
2482 kmem_cache_destroy(fib6_node_kmem
);
2485 #ifdef CONFIG_PROC_FS
2486 static int ipv6_route_native_seq_show(struct seq_file
*seq
, void *v
)
2488 struct fib6_info
*rt
= v
;
2489 struct ipv6_route_iter
*iter
= seq
->private;
2490 struct fib6_nh
*fib6_nh
= rt
->fib6_nh
;
2491 unsigned int flags
= rt
->fib6_flags
;
2492 const struct net_device
*dev
;
2495 fib6_nh
= nexthop_fib6_nh_bh(rt
->nh
);
2497 seq_printf(seq
, "%pi6 %02x ", &rt
->fib6_dst
.addr
, rt
->fib6_dst
.plen
);
2499 #ifdef CONFIG_IPV6_SUBTREES
2500 seq_printf(seq
, "%pi6 %02x ", &rt
->fib6_src
.addr
, rt
->fib6_src
.plen
);
2502 seq_puts(seq
, "00000000000000000000000000000000 00 ");
2504 if (fib6_nh
->fib_nh_gw_family
) {
2505 flags
|= RTF_GATEWAY
;
2506 seq_printf(seq
, "%pi6", &fib6_nh
->fib_nh_gw6
);
2508 seq_puts(seq
, "00000000000000000000000000000000");
2511 dev
= fib6_nh
->fib_nh_dev
;
2512 seq_printf(seq
, " %08x %08x %08x %08x %8s\n",
2513 rt
->fib6_metric
, refcount_read(&rt
->fib6_ref
), 0,
2514 flags
, dev
? dev
->name
: "");
2515 iter
->w
.leaf
= NULL
;
2519 static int ipv6_route_yield(struct fib6_walker
*w
)
2521 struct ipv6_route_iter
*iter
= w
->args
;
2527 iter
->w
.leaf
= rcu_dereference_protected(
2528 iter
->w
.leaf
->fib6_next
,
2529 lockdep_is_held(&iter
->tbl
->tb6_lock
));
2531 if (!iter
->skip
&& iter
->w
.leaf
)
2533 } while (iter
->w
.leaf
);
2538 static void ipv6_route_seq_setup_walk(struct ipv6_route_iter
*iter
,
2541 memset(&iter
->w
, 0, sizeof(iter
->w
));
2542 iter
->w
.func
= ipv6_route_yield
;
2543 iter
->w
.root
= &iter
->tbl
->tb6_root
;
2544 iter
->w
.state
= FWS_INIT
;
2545 iter
->w
.node
= iter
->w
.root
;
2546 iter
->w
.args
= iter
;
2547 iter
->sernum
= READ_ONCE(iter
->w
.root
->fn_sernum
);
2548 INIT_LIST_HEAD(&iter
->w
.lh
);
2549 fib6_walker_link(net
, &iter
->w
);
2552 static struct fib6_table
*ipv6_route_seq_next_table(struct fib6_table
*tbl
,
2556 struct hlist_node
*node
;
2559 h
= (tbl
->tb6_id
& (FIB6_TABLE_HASHSZ
- 1)) + 1;
2560 node
= rcu_dereference_bh(hlist_next_rcu(&tbl
->tb6_hlist
));
2566 while (!node
&& h
< FIB6_TABLE_HASHSZ
) {
2567 node
= rcu_dereference_bh(
2568 hlist_first_rcu(&net
->ipv6
.fib_table_hash
[h
++]));
2570 return hlist_entry_safe(node
, struct fib6_table
, tb6_hlist
);
2573 static void ipv6_route_check_sernum(struct ipv6_route_iter
*iter
)
2575 int sernum
= READ_ONCE(iter
->w
.root
->fn_sernum
);
2577 if (iter
->sernum
!= sernum
) {
2578 iter
->sernum
= sernum
;
2579 iter
->w
.state
= FWS_INIT
;
2580 iter
->w
.node
= iter
->w
.root
;
2581 WARN_ON(iter
->w
.skip
);
2582 iter
->w
.skip
= iter
->w
.count
;
2586 static void *ipv6_route_seq_next(struct seq_file
*seq
, void *v
, loff_t
*pos
)
2589 struct fib6_info
*n
;
2590 struct net
*net
= seq_file_net(seq
);
2591 struct ipv6_route_iter
*iter
= seq
->private;
2597 n
= rcu_dereference_bh(((struct fib6_info
*)v
)->fib6_next
);
2602 ipv6_route_check_sernum(iter
);
2603 spin_lock_bh(&iter
->tbl
->tb6_lock
);
2604 r
= fib6_walk_continue(&iter
->w
);
2605 spin_unlock_bh(&iter
->tbl
->tb6_lock
);
2607 return iter
->w
.leaf
;
2609 fib6_walker_unlink(net
, &iter
->w
);
2612 fib6_walker_unlink(net
, &iter
->w
);
2614 iter
->tbl
= ipv6_route_seq_next_table(iter
->tbl
, net
);
2618 ipv6_route_seq_setup_walk(iter
, net
);
2622 static void *ipv6_route_seq_start(struct seq_file
*seq
, loff_t
*pos
)
2625 struct net
*net
= seq_file_net(seq
);
2626 struct ipv6_route_iter
*iter
= seq
->private;
2629 iter
->tbl
= ipv6_route_seq_next_table(NULL
, net
);
2635 ipv6_route_seq_setup_walk(iter
, net
);
2636 return ipv6_route_seq_next(seq
, NULL
, &p
);
2642 static bool ipv6_route_iter_active(struct ipv6_route_iter
*iter
)
2644 struct fib6_walker
*w
= &iter
->w
;
2645 return w
->node
&& !(w
->state
== FWS_U
&& w
->node
== w
->root
);
2648 static void ipv6_route_native_seq_stop(struct seq_file
*seq
, void *v
)
2651 struct net
*net
= seq_file_net(seq
);
2652 struct ipv6_route_iter
*iter
= seq
->private;
2654 if (ipv6_route_iter_active(iter
))
2655 fib6_walker_unlink(net
, &iter
->w
);
2657 rcu_read_unlock_bh();
2660 #if IS_BUILTIN(CONFIG_IPV6) && defined(CONFIG_BPF_SYSCALL)
2661 static int ipv6_route_prog_seq_show(struct bpf_prog
*prog
,
2662 struct bpf_iter_meta
*meta
,
2665 struct bpf_iter__ipv6_route ctx
;
2669 return bpf_iter_run_prog(prog
, &ctx
);
2672 static int ipv6_route_seq_show(struct seq_file
*seq
, void *v
)
2674 struct ipv6_route_iter
*iter
= seq
->private;
2675 struct bpf_iter_meta meta
;
2676 struct bpf_prog
*prog
;
2680 prog
= bpf_iter_get_info(&meta
, false);
2682 return ipv6_route_native_seq_show(seq
, v
);
2684 ret
= ipv6_route_prog_seq_show(prog
, &meta
, v
);
2685 iter
->w
.leaf
= NULL
;
2690 static void ipv6_route_seq_stop(struct seq_file
*seq
, void *v
)
2692 struct bpf_iter_meta meta
;
2693 struct bpf_prog
*prog
;
2697 prog
= bpf_iter_get_info(&meta
, true);
2699 (void)ipv6_route_prog_seq_show(prog
, &meta
, v
);
2702 ipv6_route_native_seq_stop(seq
, v
);
2705 static int ipv6_route_seq_show(struct seq_file
*seq
, void *v
)
2707 return ipv6_route_native_seq_show(seq
, v
);
2710 static void ipv6_route_seq_stop(struct seq_file
*seq
, void *v
)
2712 ipv6_route_native_seq_stop(seq
, v
);
2716 const struct seq_operations ipv6_route_seq_ops
= {
2717 .start
= ipv6_route_seq_start
,
2718 .next
= ipv6_route_seq_next
,
2719 .stop
= ipv6_route_seq_stop
,
2720 .show
= ipv6_route_seq_show
2722 #endif /* CONFIG_PROC_FS */