22 #define pr_fmt(fmt) "IPv6: " fmt
24 #include <linux/errno.h>
25 #include <linux/types.h>
26 #include <linux/net.h>
28 #include <linux/netdevice.h>
29 #include <linux/in6.h>
31 #include <linux/list.h>
32 #include <linux/slab.h>
44 #define RT6_TRACE(x...) pr_debug(x)
46 #define RT6_TRACE(x...) do { ; } while (0)
53 #ifdef CONFIG_IPV6_SUBTREES
72 #ifdef CONFIG_IPV6_SUBTREES
73 #define FWS_INIT FWS_S
75 #define FWS_INIT FWS_L
92 static __u32 rt_sernum;
94 static void fib6_gc_timer_cb(
unsigned long arg);
97 #define FOR_WALKERS(w) list_for_each_entry(w, &fib6_walkers, lh)
102 list_add(&w->
lh, &fib6_walkers);
130 #if defined(__LITTLE_ENDIAN)
131 # define BITOP_BE32_SWIZZLE (0x1F & ~7)
133 # define BITOP_BE32_SWIZZLE 0
154 fn = kmem_cache_zalloc(fib6_node_kmem,
GFP_ATOMIC);
186 hlist_add_head_rcu(&tb->
tb6_hlist, &net->ipv6.fib_table_hash[h]);
189 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
198 table->
tb6_root.leaf = net->ipv6.ip6_null_entry;
216 tb = fib6_alloc_table(net,
id);
218 fib6_link_table(net, tb);
234 head = &net->ipv6.fib_table_hash[
h];
235 hlist_for_each_entry_rcu(tb, node, head, tb6_hlist) {
246 static void __net_init fib6_tables_init(
struct net *net)
248 fib6_link_table(net, net->ipv6.fib6_main_tbl);
249 fib6_link_table(net, net->ipv6.fib6_local_tbl);
260 return net->ipv6.fib6_main_tbl;
266 return (
struct dst_entry *)
lookup(net, net->ipv6.fib6_main_tbl, fl6, flags);
269 static void __net_init fib6_tables_init(
struct net *net)
271 fib6_link_table(net, net->ipv6.fib6_main_tbl);
281 for (rt = w->
leaf; rt; rt = rt->
dst.rt6_next) {
301 fib6_walker_unlink(w);
322 w = (
void *)cb->
args[2];
337 if (cb->
args[5] != w->
root->fn_sernum) {
347 res = fib6_walk_continue(w);
350 fib6_walker_unlink(w);
360 struct net *net = sock_net(skb->
sk);
362 unsigned int e = 0, s_e;
373 w = (
void *)cb->
args[2];
380 cb->
done = fib6_dump_done;
388 w->
func = fib6_dump_node;
400 head = &net->ipv6.fib_table_hash[
h];
401 hlist_for_each_entry_rcu(tb, node, head, tb6_hlist) {
404 res = fib6_dump_table(tb, skb, cb);
416 res = res < 0 ? res : skb->
len;
431 int addrlen,
int plen,
432 int offset,
int allow_create,
433 int replace_required)
440 __u32 sernum = fib6_new_sernum();
454 if (plen < fn->fn_bit ||
455 !ipv6_prefix_equal(&key->
addr, addr, fn->
fn_bit)) {
457 if (replace_required) {
458 pr_warn(
"Can't replace route, no match found\n");
461 pr_warn(
"NLM_F_CREATE should be set when creating new route\n");
473 rt6_release(fn->
leaf);
488 dir = addr_bit_set(addr, fn->
fn_bit);
503 if (replace_required) {
504 pr_warn(
"Can't replace route, no match found\n");
507 pr_warn(
"NLM_F_CREATE should be set when creating new route\n");
548 bit = __ipv6_addr_diff(addr, &key->
addr, addrlen);
596 if (addr_bit_set(addr, bit)) {
627 if (addr_bit_set(&key->
addr, plen))
646 int replace = (info->
nlh &&
654 for (iter = fn->
leaf; iter; iter = iter->
dst.rt6_next) {
671 if (iter->
dst.dev == rt->
dst.dev &&
678 rt6_clean_expires(iter);
680 rt6_set_expires(iter, rt->
dst.expires);
688 ins = &iter->
dst.rt6_next;
692 if (ins == &fn->
leaf)
700 pr_warn(
"NLM_F_CREATE should be set when creating new route\n");
703 rt->
dst.rt6_next = iter;
708 info->
nl_net->ipv6.rt6_stats->fib_rt_entries++;
711 info->
nl_net->ipv6.rt6_stats->fib_route_nodes++;
719 pr_warn(
"NLM_F_REPLACE set, but no existing node found!\n");
724 rt->
dst.rt6_next = iter->
dst.rt6_next;
729 info->
nl_net->ipv6.rt6_stats->fib_route_nodes++;
739 if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
742 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
747 if (!timer_pending(&net->ipv6.ip6_fib_timer))
749 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
762 int allow_create = 1;
763 int replace_required = 0;
769 replace_required = 1;
771 if (!allow_create && !replace_required)
772 pr_warn(
"RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
774 fn = fib6_add_1(root, &rt->rt6i_dst.addr,
sizeof(
struct in6_addr),
776 allow_create, replace_required);
785 #ifdef CONFIG_IPV6_SUBTREES
807 sfn->
leaf = info->
nl_net->ipv6.ip6_null_entry;
814 sn = fib6_add_1(sfn, &rt->
rt6i_src.addr,
817 allow_create, replace_required);
833 sn = fib6_add_1(fn->subtree, &rt->
rt6i_src.addr,
836 allow_create, replace_required);
852 err = fib6_add_rt2node(fn, rt, info);
854 fib6_start_gc(info->
nl_net, rt);
856 fib6_prune_clones(info->
nl_net, pn, rt);
861 #ifdef CONFIG_IPV6_SUBTREES
866 if (pn != fn && pn->
leaf == rt) {
871 pn->
leaf = fib6_find_prefix(info->
nl_net, pn);
885 #ifdef CONFIG_IPV6_SUBTREES
891 fib6_repair_tree(info->
nl_net, fn);
943 if (ipv6_prefix_equal(&key->
addr, args->
addr, key->
plen)) {
944 #ifdef CONFIG_IPV6_SUBTREES
946 fn = fib6_lookup_1(fn->subtree, args + 1);
971 #ifdef CONFIG_IPV6_SUBTREES
982 fn = fib6_lookup_1(root, daddr ? args : args + 1);
997 int plen,
int offset)
1001 for (fn = root;
fn ; ) {
1007 if (plen < fn->fn_bit ||
1008 !ipv6_prefix_equal(&key->
addr, addr, fn->
fn_bit))
1017 if (addr_bit_set(addr, fn->
fn_bit))
1031 fn = fib6_locate_1(root, daddr, dst_len,
1034 #ifdef CONFIG_IPV6_SUBTREES
1037 if (fn && fn->subtree)
1038 fn = fib6_locate_1(fn->subtree, saddr, src_len,
1058 return net->ipv6.ip6_null_entry;
1062 return fn->
left->leaf;
1064 return fn->
right->leaf;
1076 static struct fib6_node *fib6_repair_tree(
struct net *net,
1095 if (fn->
right) child = fn->
right, children |= 1;
1096 if (fn->
left) child = fn->
left, children |= 2;
1099 #ifdef CONFIG_IPV6_SUBTREES
1104 fn->
leaf = fib6_find_prefix(net, fn);
1108 fn->
leaf = net->ipv6.ip6_null_entry;
1116 #ifdef CONFIG_IPV6_SUBTREES
1125 else if (pn->
left == fn) pn->
left = child;
1133 #ifdef CONFIG_IPV6_SUBTREES
1140 if (w->
root == fn) {
1142 RT6_TRACE(
"W %p adjusted by delroot 1\n", w);
1143 }
else if (w->
node == fn) {
1144 RT6_TRACE(
"W %p adjusted by delnode 1, s=%d/%d\n", w, w->
state, nstate);
1149 if (w->
root == fn) {
1151 RT6_TRACE(
"W %p adjusted by delroot 2\n", w);
1153 if (w->
node == fn) {
1171 rt6_release(pn->
leaf);
1182 struct net *net = info->
nl_net;
1187 *rtp = rt->
dst.rt6_next;
1189 net->ipv6.rt6_stats->fib_rt_entries--;
1190 net->ipv6.rt6_stats->fib_discarded_routes++;
1200 RT6_TRACE(
"walker %p adjusted by delroute\n", w);
1213 net->ipv6.rt6_stats->fib_route_nodes--;
1214 fn = fib6_repair_tree(net, fn);
1226 fn->
leaf = fib6_find_prefix(net, fn);
1242 struct net *net = info->
nl_net;
1247 if (rt->
dst.obsolete>0) {
1252 if (!fn || rt == net->ipv6.ip6_null_entry)
1259 #ifdef CONFIG_IPV6_SUBTREES
1267 fib6_prune_clones(info->
nl_net, pn, rt);
1274 for (rtp = &fn->
leaf; *rtp; rtp = &(*rtp)->
dst.rt6_next) {
1276 fib6_del_route(fn, rtp, info);
1322 #ifdef CONFIG_IPV6_SUBTREES
1367 #ifdef CONFIG_IPV6_SUBTREES
1374 if (pn->
left == fn) {
1378 if (pn->
right == fn) {
1397 fib6_walker_link(w);
1398 res = fib6_walk_continue(w);
1400 fib6_walker_unlink(w);
1413 for (rt = w->
leaf; rt; rt = rt->
dst.rt6_next) {
1420 pr_debug(
"%s: del failed: rt=%p@%p err=%d\n",
1444 static void fib6_clean_tree(
struct net *net,
struct fib6_node *root,
1446 int prune,
void *arg)
1451 c.
w.func = fib6_clean_node;
1463 int prune,
void *arg)
1472 head = &net->ipv6.fib_table_hash[
h];
1473 hlist_for_each_entry_rcu(table, node, head, tb6_hlist) {
1475 fib6_clean_tree(net, &table->
tb6_root,
1483 int prune,
void *arg)
1492 head = &net->ipv6.fib_table_hash[
h];
1493 hlist_for_each_entry_rcu(table, node, head, tb6_hlist) {
1495 fib6_clean_tree(net, &table->
tb6_root,
1503 static int fib6_prune_clone(
struct rt6_info *rt,
void *
arg)
1513 static void fib6_prune_clones(
struct net *net,
struct fib6_node *fn,
1516 fib6_clean_tree(net, fn, fib6_prune_clone, 1, rt);
1523 static struct fib6_gc_args
1529 static int fib6_age(
struct rt6_info *rt,
void *arg)
1554 __u8 neigh_flags = 0;
1558 neigh_flags = neigh->
flags;
1559 neigh_release(neigh);
1562 RT6_TRACE(
"purging route %p via non-router but gateway\n",
1577 if (expires != ~0
UL) {
1578 spin_lock_bh(&fib6_gc_lock);
1579 gc_args.timeout = expires ? (
int)expires :
1580 net->ipv6.sysctl.ip6_rt_gc_interval;
1582 if (!spin_trylock_bh(&fib6_gc_lock)) {
1586 gc_args.timeout = net->ipv6.sysctl.ip6_rt_gc_interval;
1596 + net->ipv6.sysctl.ip6_rt_gc_interval));
1599 spin_unlock_bh(&fib6_gc_lock);
1602 static void fib6_gc_timer_cb(
unsigned long arg)
1607 static int __net_init fib6_net_init(
struct net *net)
1611 setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (
unsigned long)net);
1613 net->ipv6.rt6_stats = kzalloc(
sizeof(*net->ipv6.rt6_stats),
GFP_KERNEL);
1614 if (!net->ipv6.rt6_stats)
1620 net->ipv6.fib_table_hash = kzalloc(size,
GFP_KERNEL);
1621 if (!net->ipv6.fib_table_hash)
1624 net->ipv6.fib6_main_tbl = kzalloc(
sizeof(*net->ipv6.fib6_main_tbl),
1626 if (!net->ipv6.fib6_main_tbl)
1627 goto out_fib_table_hash;
1630 net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1631 net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
1635 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1636 net->ipv6.fib6_local_tbl = kzalloc(
sizeof(*net->ipv6.fib6_local_tbl),
1638 if (!net->ipv6.fib6_local_tbl)
1639 goto out_fib6_main_tbl;
1641 net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
1642 net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
1646 fib6_tables_init(net);
1650 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1652 kfree(net->ipv6.fib6_main_tbl);
1655 kfree(net->ipv6.fib_table_hash);
1657 kfree(net->ipv6.rt6_stats);
1662 static void fib6_net_exit(
struct net *net)
1667 #ifdef CONFIG_IPV6_MULTIPLE_TABLES
1669 kfree(net->ipv6.fib6_local_tbl);
1672 kfree(net->ipv6.fib6_main_tbl);
1673 kfree(net->ipv6.fib_table_hash);
1674 kfree(net->ipv6.rt6_stats);
1678 .init = fib6_net_init,
1679 .exit = fib6_net_exit,
1690 if (!fib6_node_kmem)
1695 goto out_kmem_cache_create;
1700 goto out_unregister_subsys;
1704 out_unregister_subsys:
1706 out_kmem_cache_create: