blob: cb4459bd1d294d1901cc03b9c203fbcbf761f53f [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09002 * Linux INET6 implementation
Linus Torvalds1da177e2005-04-16 15:20:36 -07003 * Forwarding Information Database
4 *
5 * Authors:
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09006 * Pedro Roque <roque@di.fc.ul.pt>
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 * 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.
Wang Yufen8db46f12014-03-28 12:07:02 +080012 *
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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070018 */
Joe Perchesf3213832012-05-15 14:11:53 +000019
20#define pr_fmt(fmt) "IPv6: " fmt
21
Linus Torvalds1da177e2005-04-16 15:20:36 -070022#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>
Thomas Grafc71099a2006-08-04 23:20:06 -070029#include <linux/list.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090030#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070031
Linus Torvalds1da177e2005-04-16 15:20:36 -070032#include <net/ipv6.h>
33#include <net/ndisc.h>
34#include <net/addrconf.h>
35
36#include <net/ip6_fib.h>
37#include <net/ip6_route.h>
38
39#define RT6_DEBUG 2
40
41#if RT6_DEBUG >= 3
Joe Perches91df42b2012-05-15 14:11:54 +000042#define RT6_TRACE(x...) pr_debug(x)
Linus Torvalds1da177e2005-04-16 15:20:36 -070043#else
44#define RT6_TRACE(x...) do { ; } while (0)
45#endif
46
Wang Yufen437de072014-03-28 12:07:04 +080047static struct kmem_cache *fib6_node_kmem __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070048
Wang Yufen49e253e2014-03-28 12:07:03 +080049enum fib_walk_state_t {
Linus Torvalds1da177e2005-04-16 15:20:36 -070050#ifdef CONFIG_IPV6_SUBTREES
51 FWS_S,
52#endif
53 FWS_L,
54 FWS_R,
55 FWS_C,
56 FWS_U
57};
58
Wang Yufen49e253e2014-03-28 12:07:03 +080059struct fib6_cleaner_t {
Linus Torvalds1da177e2005-04-16 15:20:36 -070060 struct fib6_walker_t w;
Benjamin Theryec7d43c2008-03-03 23:31:57 -080061 struct net *net;
Linus Torvalds1da177e2005-04-16 15:20:36 -070062 int (*func)(struct rt6_info *, void *arg);
63 void *arg;
64};
65
Adrian Bunk90d41122006-08-14 23:49:16 -070066static DEFINE_RWLOCK(fib6_walker_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070067
68#ifdef CONFIG_IPV6_SUBTREES
69#define FWS_INIT FWS_S
Linus Torvalds1da177e2005-04-16 15:20:36 -070070#else
71#define FWS_INIT FWS_L
Linus Torvalds1da177e2005-04-16 15:20:36 -070072#endif
73
Duan Jiong163cd4e2014-05-09 13:31:43 +080074static void fib6_prune_clones(struct net *net, struct fib6_node *fn);
Daniel Lezcano8ed67782008-03-04 13:48:30 -080075static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
76static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
Adrian Bunk90d41122006-08-14 23:49:16 -070077static int fib6_walk(struct fib6_walker_t *w);
78static int fib6_walk_continue(struct fib6_walker_t *w);
Linus Torvalds1da177e2005-04-16 15:20:36 -070079
80/*
81 * A routing update causes an increase of the serial number on the
82 * affected subtree. This allows for cached routes to be asynchronously
83 * tested when modifications are made to the destination cache as a
84 * result of redirects, path MTU changes, etc.
85 */
86
87static __u32 rt_sernum;
88
Daniel Lezcano5b7c9312008-03-03 23:28:58 -080089static void fib6_gc_timer_cb(unsigned long arg);
90
Alexey Dobriyanbbef49d2010-02-18 08:13:30 +000091static LIST_HEAD(fib6_walkers);
92#define FOR_WALKERS(w) list_for_each_entry(w, &fib6_walkers, lh)
Linus Torvalds1da177e2005-04-16 15:20:36 -070093
Adrian Bunk90d41122006-08-14 23:49:16 -070094static inline void fib6_walker_link(struct fib6_walker_t *w)
95{
96 write_lock_bh(&fib6_walker_lock);
Alexey Dobriyanbbef49d2010-02-18 08:13:30 +000097 list_add(&w->lh, &fib6_walkers);
Adrian Bunk90d41122006-08-14 23:49:16 -070098 write_unlock_bh(&fib6_walker_lock);
99}
100
101static inline void fib6_walker_unlink(struct fib6_walker_t *w)
102{
103 write_lock_bh(&fib6_walker_lock);
Alexey Dobriyanbbef49d2010-02-18 08:13:30 +0000104 list_del(&w->lh);
Adrian Bunk90d41122006-08-14 23:49:16 -0700105 write_unlock_bh(&fib6_walker_lock);
106}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700107static __inline__ u32 fib6_new_sernum(void)
108{
109 u32 n = ++rt_sernum;
110 if ((__s32)n <= 0)
111 rt_sernum = n = 1;
112 return n;
113}
114
115/*
116 * Auxiliary address test functions for the radix tree.
117 *
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900118 * These assume a 32bit processor (although it will work on
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119 * 64bit processors)
120 */
121
122/*
123 * test bit
124 */
YOSHIFUJI Hideaki / 吉藤英明02cdce52010-03-27 01:24:16 +0000125#if defined(__LITTLE_ENDIAN)
126# define BITOP_BE32_SWIZZLE (0x1F & ~7)
127#else
128# define BITOP_BE32_SWIZZLE 0
129#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000131static __inline__ __be32 addr_bit_set(const void *token, int fn_bit)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700132{
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000133 const __be32 *addr = token;
YOSHIFUJI Hideaki / 吉藤英明02cdce52010-03-27 01:24:16 +0000134 /*
135 * Here,
Wang Yufen8db46f12014-03-28 12:07:02 +0800136 * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
YOSHIFUJI Hideaki / 吉藤英明02cdce52010-03-27 01:24:16 +0000137 * is optimized version of
138 * htonl(1 << ((~fn_bit)&0x1F))
139 * See include/asm-generic/bitops/le.h.
140 */
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700141 return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
142 addr[fn_bit >> 5];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143}
144
Wang Yufen437de072014-03-28 12:07:04 +0800145static __inline__ struct fib6_node *node_alloc(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146{
147 struct fib6_node *fn;
148
Robert P. J. Dayc3762222007-02-10 01:45:03 -0800149 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150
151 return fn;
152}
153
Wang Yufen437de072014-03-28 12:07:04 +0800154static __inline__ void node_free(struct fib6_node *fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155{
156 kmem_cache_free(fib6_node_kmem, fn);
157}
158
159static __inline__ void rt6_release(struct rt6_info *rt)
160{
161 if (atomic_dec_and_test(&rt->rt6i_ref))
Changli Gaod8d1f302010-06-10 23:31:35 -0700162 dst_free(&rt->dst);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163}
164
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800165static void fib6_link_table(struct net *net, struct fib6_table *tb)
Patrick McHardy1b43af52006-08-10 23:11:17 -0700166{
167 unsigned int h;
168
Thomas Graf375216a2006-10-21 20:20:54 -0700169 /*
170 * Initialize table lock at a single place to give lockdep a key,
171 * tables aren't visible prior to being linked to the list.
172 */
173 rwlock_init(&tb->tb6_lock);
174
Neil Hormana33bc5c2009-07-30 18:52:15 -0700175 h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700176
177 /*
178 * No protection necessary, this is the only list mutatation
179 * operation, tables never disappear once they exist.
180 */
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800181 hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700182}
183
184#ifdef CONFIG_IPV6_MULTIPLE_TABLES
Daniel Lezcanoe0b855902008-03-03 23:24:31 -0800185
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800186static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700187{
188 struct fib6_table *table;
189
190 table = kzalloc(sizeof(*table), GFP_ATOMIC);
David S. Miller507c9b12011-12-03 17:50:45 -0500191 if (table) {
Thomas Grafc71099a2006-08-04 23:20:06 -0700192 table->tb6_id = id;
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800193 table->tb6_root.leaf = net->ipv6.ip6_null_entry;
Thomas Grafc71099a2006-08-04 23:20:06 -0700194 table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
David S. Miller8e773272012-06-11 00:01:52 -0700195 inet_peer_base_init(&table->tb6_peers);
Thomas Grafc71099a2006-08-04 23:20:06 -0700196 }
197
198 return table;
199}
200
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800201struct fib6_table *fib6_new_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700202{
203 struct fib6_table *tb;
204
205 if (id == 0)
206 id = RT6_TABLE_MAIN;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800207 tb = fib6_get_table(net, id);
Thomas Grafc71099a2006-08-04 23:20:06 -0700208 if (tb)
209 return tb;
210
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800211 tb = fib6_alloc_table(net, id);
David S. Miller507c9b12011-12-03 17:50:45 -0500212 if (tb)
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800213 fib6_link_table(net, tb);
Thomas Grafc71099a2006-08-04 23:20:06 -0700214
215 return tb;
216}
217
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800218struct fib6_table *fib6_get_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700219{
220 struct fib6_table *tb;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800221 struct hlist_head *head;
Thomas Grafc71099a2006-08-04 23:20:06 -0700222 unsigned int h;
223
224 if (id == 0)
225 id = RT6_TABLE_MAIN;
Neil Hormana33bc5c2009-07-30 18:52:15 -0700226 h = id & (FIB6_TABLE_HASHSZ - 1);
Thomas Grafc71099a2006-08-04 23:20:06 -0700227 rcu_read_lock();
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800228 head = &net->ipv6.fib_table_hash[h];
Sasha Levinb67bfe02013-02-27 17:06:00 -0800229 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
Thomas Grafc71099a2006-08-04 23:20:06 -0700230 if (tb->tb6_id == id) {
231 rcu_read_unlock();
232 return tb;
233 }
234 }
235 rcu_read_unlock();
236
237 return NULL;
238}
239
Alexey Dobriyan2c8c1e72010-01-17 03:35:32 +0000240static void __net_init fib6_tables_init(struct net *net)
Thomas Grafc71099a2006-08-04 23:20:06 -0700241{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800242 fib6_link_table(net, net->ipv6.fib6_main_tbl);
243 fib6_link_table(net, net->ipv6.fib6_local_tbl);
Thomas Grafc71099a2006-08-04 23:20:06 -0700244}
Thomas Grafc71099a2006-08-04 23:20:06 -0700245#else
246
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800247struct fib6_table *fib6_new_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700248{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800249 return fib6_get_table(net, id);
Thomas Grafc71099a2006-08-04 23:20:06 -0700250}
251
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800252struct fib6_table *fib6_get_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700253{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800254 return net->ipv6.fib6_main_tbl;
Thomas Grafc71099a2006-08-04 23:20:06 -0700255}
256
David S. Miller4c9483b2011-03-12 16:22:43 -0500257struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800258 int flags, pol_lookup_t lookup)
Thomas Grafc71099a2006-08-04 23:20:06 -0700259{
David S. Miller4c9483b2011-03-12 16:22:43 -0500260 return (struct dst_entry *) lookup(net, net->ipv6.fib6_main_tbl, fl6, flags);
Thomas Grafc71099a2006-08-04 23:20:06 -0700261}
262
Alexey Dobriyan2c8c1e72010-01-17 03:35:32 +0000263static void __net_init fib6_tables_init(struct net *net)
Thomas Grafc71099a2006-08-04 23:20:06 -0700264{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800265 fib6_link_table(net, net->ipv6.fib6_main_tbl);
Thomas Grafc71099a2006-08-04 23:20:06 -0700266}
267
268#endif
269
Patrick McHardy1b43af52006-08-10 23:11:17 -0700270static int fib6_dump_node(struct fib6_walker_t *w)
271{
272 int res;
273 struct rt6_info *rt;
274
Changli Gaod8d1f302010-06-10 23:31:35 -0700275 for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700276 res = rt6_dump_route(rt, w->args);
277 if (res < 0) {
278 /* Frame is full, suspend walking */
279 w->leaf = rt;
280 return 1;
281 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700282 WARN_ON(res == 0);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700283 }
284 w->leaf = NULL;
285 return 0;
286}
287
288static void fib6_dump_end(struct netlink_callback *cb)
289{
Wang Yufen437de072014-03-28 12:07:04 +0800290 struct fib6_walker_t *w = (void *)cb->args[2];
Patrick McHardy1b43af52006-08-10 23:11:17 -0700291
292 if (w) {
Herbert Xu7891cc82009-01-13 22:17:51 -0800293 if (cb->args[4]) {
294 cb->args[4] = 0;
295 fib6_walker_unlink(w);
296 }
Patrick McHardy1b43af52006-08-10 23:11:17 -0700297 cb->args[2] = 0;
298 kfree(w);
299 }
Wang Yufen437de072014-03-28 12:07:04 +0800300 cb->done = (void *)cb->args[3];
Patrick McHardy1b43af52006-08-10 23:11:17 -0700301 cb->args[1] = 3;
302}
303
304static int fib6_dump_done(struct netlink_callback *cb)
305{
306 fib6_dump_end(cb);
307 return cb->done ? cb->done(cb) : 0;
308}
309
310static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
311 struct netlink_callback *cb)
312{
313 struct fib6_walker_t *w;
314 int res;
315
316 w = (void *)cb->args[2];
317 w->root = &table->tb6_root;
318
319 if (cb->args[4] == 0) {
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000320 w->count = 0;
321 w->skip = 0;
322
Patrick McHardy1b43af52006-08-10 23:11:17 -0700323 read_lock_bh(&table->tb6_lock);
324 res = fib6_walk(w);
325 read_unlock_bh(&table->tb6_lock);
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000326 if (res > 0) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700327 cb->args[4] = 1;
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000328 cb->args[5] = w->root->fn_sernum;
329 }
Patrick McHardy1b43af52006-08-10 23:11:17 -0700330 } else {
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000331 if (cb->args[5] != w->root->fn_sernum) {
332 /* Begin at the root if the tree changed */
333 cb->args[5] = w->root->fn_sernum;
334 w->state = FWS_INIT;
335 w->node = w->root;
336 w->skip = w->count;
337 } else
338 w->skip = 0;
339
Patrick McHardy1b43af52006-08-10 23:11:17 -0700340 read_lock_bh(&table->tb6_lock);
341 res = fib6_walk_continue(w);
342 read_unlock_bh(&table->tb6_lock);
Herbert Xu7891cc82009-01-13 22:17:51 -0800343 if (res <= 0) {
344 fib6_walker_unlink(w);
345 cb->args[4] = 0;
Patrick McHardy1b43af52006-08-10 23:11:17 -0700346 }
Patrick McHardy1b43af52006-08-10 23:11:17 -0700347 }
Herbert Xu7891cc82009-01-13 22:17:51 -0800348
Patrick McHardy1b43af52006-08-10 23:11:17 -0700349 return res;
350}
351
Thomas Grafc127ea22007-03-22 11:58:32 -0700352static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
Patrick McHardy1b43af52006-08-10 23:11:17 -0700353{
YOSHIFUJI Hideaki3b1e0a62008-03-26 02:26:21 +0900354 struct net *net = sock_net(skb->sk);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700355 unsigned int h, s_h;
356 unsigned int e = 0, s_e;
357 struct rt6_rtnl_dump_arg arg;
358 struct fib6_walker_t *w;
359 struct fib6_table *tb;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800360 struct hlist_head *head;
Patrick McHardy1b43af52006-08-10 23:11:17 -0700361 int res = 0;
362
363 s_h = cb->args[0];
364 s_e = cb->args[1];
365
366 w = (void *)cb->args[2];
David S. Miller507c9b12011-12-03 17:50:45 -0500367 if (!w) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700368 /* New dump:
369 *
370 * 1. hook callback destructor.
371 */
372 cb->args[3] = (long)cb->done;
373 cb->done = fib6_dump_done;
374
375 /*
376 * 2. allocate and initialize walker.
377 */
378 w = kzalloc(sizeof(*w), GFP_ATOMIC);
David S. Miller507c9b12011-12-03 17:50:45 -0500379 if (!w)
Patrick McHardy1b43af52006-08-10 23:11:17 -0700380 return -ENOMEM;
381 w->func = fib6_dump_node;
382 cb->args[2] = (long)w;
383 }
384
385 arg.skb = skb;
386 arg.cb = cb;
Brian Haley191cd582008-08-14 15:33:21 -0700387 arg.net = net;
Patrick McHardy1b43af52006-08-10 23:11:17 -0700388 w->args = &arg;
389
Eric Dumazete67f88d2011-04-27 22:56:07 +0000390 rcu_read_lock();
Neil Hormana33bc5c2009-07-30 18:52:15 -0700391 for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700392 e = 0;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800393 head = &net->ipv6.fib_table_hash[h];
Sasha Levinb67bfe02013-02-27 17:06:00 -0800394 hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700395 if (e < s_e)
396 goto next;
397 res = fib6_dump_table(tb, skb, cb);
398 if (res != 0)
399 goto out;
400next:
401 e++;
402 }
403 }
404out:
Eric Dumazete67f88d2011-04-27 22:56:07 +0000405 rcu_read_unlock();
Patrick McHardy1b43af52006-08-10 23:11:17 -0700406 cb->args[1] = e;
407 cb->args[0] = h;
408
409 res = res < 0 ? res : skb->len;
410 if (res <= 0)
411 fib6_dump_end(cb);
412 return res;
413}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414
415/*
416 * Routing Table
417 *
418 * return the appropriate node for a routing tree "add" operation
419 * by either creating and inserting or by returning an existing
420 * node.
421 */
422
fan.du9225b232013-07-22 14:21:09 +0800423static struct fib6_node *fib6_add_1(struct fib6_node *root,
424 struct in6_addr *addr, int plen,
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000425 int offset, int allow_create,
426 int replace_required)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427{
428 struct fib6_node *fn, *in, *ln;
429 struct fib6_node *pn = NULL;
430 struct rt6key *key;
431 int bit;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900432 __be32 dir = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433 __u32 sernum = fib6_new_sernum();
434
435 RT6_TRACE("fib6_add_1\n");
436
437 /* insert node in tree */
438
439 fn = root;
440
441 do {
442 key = (struct rt6key *)((u8 *)fn->leaf + offset);
443
444 /*
445 * Prefix match
446 */
447 if (plen < fn->fn_bit ||
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000448 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
Matti Vaittinen14df0152011-11-16 21:18:02 +0000449 if (!allow_create) {
450 if (replace_required) {
Joe Perchesf3213832012-05-15 14:11:53 +0000451 pr_warn("Can't replace route, no match found\n");
Matti Vaittinen14df0152011-11-16 21:18:02 +0000452 return ERR_PTR(-ENOENT);
453 }
Joe Perchesf3213832012-05-15 14:11:53 +0000454 pr_warn("NLM_F_CREATE should be set when creating new route\n");
Matti Vaittinen14df0152011-11-16 21:18:02 +0000455 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700456 goto insert_above;
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000457 }
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900458
Linus Torvalds1da177e2005-04-16 15:20:36 -0700459 /*
460 * Exact match ?
461 */
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900462
Linus Torvalds1da177e2005-04-16 15:20:36 -0700463 if (plen == fn->fn_bit) {
464 /* clean up an intermediate node */
David S. Miller507c9b12011-12-03 17:50:45 -0500465 if (!(fn->fn_flags & RTN_RTINFO)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466 rt6_release(fn->leaf);
467 fn->leaf = NULL;
468 }
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900469
Linus Torvalds1da177e2005-04-16 15:20:36 -0700470 fn->fn_sernum = sernum;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900471
Linus Torvalds1da177e2005-04-16 15:20:36 -0700472 return fn;
473 }
474
475 /*
476 * We have more bits to go
477 */
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900478
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479 /* Try to walk down on tree. */
480 fn->fn_sernum = sernum;
481 dir = addr_bit_set(addr, fn->fn_bit);
482 pn = fn;
Wang Yufen8db46f12014-03-28 12:07:02 +0800483 fn = dir ? fn->right : fn->left;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700484 } while (fn);
485
Matti Vaittinen14df0152011-11-16 21:18:02 +0000486 if (!allow_create) {
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000487 /* We should not create new node because
488 * NLM_F_REPLACE was specified without NLM_F_CREATE
489 * I assume it is safe to require NLM_F_CREATE when
490 * REPLACE flag is used! Later we may want to remove the
491 * check for replace_required, because according
492 * to netlink specification, NLM_F_CREATE
493 * MUST be specified if new route is created.
494 * That would keep IPv6 consistent with IPv4
495 */
Matti Vaittinen14df0152011-11-16 21:18:02 +0000496 if (replace_required) {
Joe Perchesf3213832012-05-15 14:11:53 +0000497 pr_warn("Can't replace route, no match found\n");
Matti Vaittinen14df0152011-11-16 21:18:02 +0000498 return ERR_PTR(-ENOENT);
499 }
Joe Perchesf3213832012-05-15 14:11:53 +0000500 pr_warn("NLM_F_CREATE should be set when creating new route\n");
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000501 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502 /*
503 * We walked to the bottom of tree.
504 * Create new leaf node without children.
505 */
506
507 ln = node_alloc();
508
David S. Miller507c9b12011-12-03 17:50:45 -0500509 if (!ln)
Lin Ming188c5172012-09-25 15:17:07 +0000510 return ERR_PTR(-ENOMEM);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511 ln->fn_bit = plen;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900512
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513 ln->parent = pn;
514 ln->fn_sernum = sernum;
515
516 if (dir)
517 pn->right = ln;
518 else
519 pn->left = ln;
520
521 return ln;
522
523
524insert_above:
525 /*
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900526 * split since we don't have a common prefix anymore or
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527 * we have a less significant route.
528 * we've to insert an intermediate node on the list
529 * this new node will point to the one we need to create
530 * and the current
531 */
532
533 pn = fn->parent;
534
535 /* find 1st bit in difference between the 2 addrs.
536
YOSHIFUJI Hideaki971f3592005-11-08 09:37:56 -0800537 See comment in __ipv6_addr_diff: bit may be an invalid value,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700538 but if it is >= plen, the value is ignored in any case.
539 */
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900540
fan.du9225b232013-07-22 14:21:09 +0800541 bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700542
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900543 /*
544 * (intermediate)[in]
Linus Torvalds1da177e2005-04-16 15:20:36 -0700545 * / \
546 * (new leaf node)[ln] (old node)[fn]
547 */
548 if (plen > bit) {
549 in = node_alloc();
550 ln = node_alloc();
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900551
David S. Miller507c9b12011-12-03 17:50:45 -0500552 if (!in || !ln) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553 if (in)
554 node_free(in);
555 if (ln)
556 node_free(ln);
Lin Ming188c5172012-09-25 15:17:07 +0000557 return ERR_PTR(-ENOMEM);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558 }
559
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900560 /*
561 * new intermediate node.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700562 * RTN_RTINFO will
563 * be off since that an address that chooses one of
564 * the branches would not match less specific routes
565 * in the other branch
566 */
567
568 in->fn_bit = bit;
569
570 in->parent = pn;
571 in->leaf = fn->leaf;
572 atomic_inc(&in->leaf->rt6i_ref);
573
574 in->fn_sernum = sernum;
575
576 /* update parent pointer */
577 if (dir)
578 pn->right = in;
579 else
580 pn->left = in;
581
582 ln->fn_bit = plen;
583
584 ln->parent = in;
585 fn->parent = in;
586
587 ln->fn_sernum = sernum;
588
589 if (addr_bit_set(addr, bit)) {
590 in->right = ln;
591 in->left = fn;
592 } else {
593 in->left = ln;
594 in->right = fn;
595 }
596 } else { /* plen <= bit */
597
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900598 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599 * (new leaf node)[ln]
600 * / \
601 * (old node)[fn] NULL
602 */
603
604 ln = node_alloc();
605
David S. Miller507c9b12011-12-03 17:50:45 -0500606 if (!ln)
Lin Ming188c5172012-09-25 15:17:07 +0000607 return ERR_PTR(-ENOMEM);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700608
609 ln->fn_bit = plen;
610
611 ln->parent = pn;
612
613 ln->fn_sernum = sernum;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900614
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615 if (dir)
616 pn->right = ln;
617 else
618 pn->left = ln;
619
620 if (addr_bit_set(&key->addr, plen))
621 ln->right = fn;
622 else
623 ln->left = fn;
624
625 fn->parent = ln;
626 }
627 return ln;
628}
629
Hannes Frederic Sowa307f2fb2013-07-12 23:46:33 +0200630static inline bool rt6_qualify_for_ecmp(struct rt6_info *rt)
631{
632 return (rt->rt6i_flags & (RTF_GATEWAY|RTF_ADDRCONF|RTF_DYNAMIC)) ==
633 RTF_GATEWAY;
634}
635
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100636static int fib6_commit_metrics(struct dst_entry *dst,
637 struct nlattr *mx, int mx_len)
638{
639 struct nlattr *nla;
640 int remaining;
641 u32 *mp;
642
643 if (dst->flags & DST_HOST) {
644 mp = dst_metrics_write_ptr(dst);
645 } else {
646 mp = kzalloc(sizeof(u32) * RTAX_MAX, GFP_KERNEL);
647 if (!mp)
648 return -ENOMEM;
649 dst_init_metrics(dst, mp, 0);
650 }
651
652 nla_for_each_attr(nla, mx, mx_len, remaining) {
653 int type = nla_type(nla);
654
655 if (type) {
656 if (type > RTAX_MAX)
657 return -EINVAL;
658
659 mp[type - 1] = nla_get_u32(nla);
660 }
661 }
662 return 0;
663}
664
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665/*
666 * Insert routing information in a node.
667 */
668
669static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100670 struct nl_info *info, struct nlattr *mx, int mx_len)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671{
672 struct rt6_info *iter = NULL;
673 struct rt6_info **ins;
David S. Miller507c9b12011-12-03 17:50:45 -0500674 int replace = (info->nlh &&
675 (info->nlh->nlmsg_flags & NLM_F_REPLACE));
676 int add = (!info->nlh ||
677 (info->nlh->nlmsg_flags & NLM_F_CREATE));
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000678 int found = 0;
Hannes Frederic Sowa307f2fb2013-07-12 23:46:33 +0200679 bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100680 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681
682 ins = &fn->leaf;
683
David S. Miller507c9b12011-12-03 17:50:45 -0500684 for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685 /*
686 * Search for duplicates
687 */
688
689 if (iter->rt6i_metric == rt->rt6i_metric) {
690 /*
691 * Same priority level
692 */
David S. Miller507c9b12011-12-03 17:50:45 -0500693 if (info->nlh &&
694 (info->nlh->nlmsg_flags & NLM_F_EXCL))
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000695 return -EEXIST;
696 if (replace) {
697 found++;
698 break;
699 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700
David S. Millerd1918542011-12-28 20:19:20 -0500701 if (iter->dst.dev == rt->dst.dev &&
Linus Torvalds1da177e2005-04-16 15:20:36 -0700702 iter->rt6i_idev == rt->rt6i_idev &&
703 ipv6_addr_equal(&iter->rt6i_gateway,
704 &rt->rt6i_gateway)) {
Nicolas Dichtel51ebd312012-10-22 03:42:09 +0000705 if (rt->rt6i_nsiblings)
706 rt->rt6i_nsiblings = 0;
David S. Miller507c9b12011-12-03 17:50:45 -0500707 if (!(iter->rt6i_flags & RTF_EXPIRES))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700708 return -EEXIST;
Gao feng1716a962012-04-06 00:13:10 +0000709 if (!(rt->rt6i_flags & RTF_EXPIRES))
710 rt6_clean_expires(iter);
711 else
712 rt6_set_expires(iter, rt->dst.expires);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 return -EEXIST;
714 }
Nicolas Dichtel51ebd312012-10-22 03:42:09 +0000715 /* If we have the same destination and the same metric,
716 * but not the same gateway, then the route we try to
717 * add is sibling to this route, increment our counter
718 * of siblings, and later we will add our route to the
719 * list.
720 * Only static routes (which don't have flag
721 * RTF_EXPIRES) are used for ECMPv6.
722 *
723 * To avoid long list, we only had siblings if the
724 * route have a gateway.
725 */
Hannes Frederic Sowa307f2fb2013-07-12 23:46:33 +0200726 if (rt_can_ecmp &&
727 rt6_qualify_for_ecmp(iter))
Nicolas Dichtel51ebd312012-10-22 03:42:09 +0000728 rt->rt6i_nsiblings++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700729 }
730
731 if (iter->rt6i_metric > rt->rt6i_metric)
732 break;
733
Changli Gaod8d1f302010-06-10 23:31:35 -0700734 ins = &iter->dst.rt6_next;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700735 }
736
David S. Millerf11e6652007-03-24 20:36:25 -0700737 /* Reset round-robin state, if necessary */
738 if (ins == &fn->leaf)
739 fn->rr_ptr = NULL;
740
Nicolas Dichtel51ebd312012-10-22 03:42:09 +0000741 /* Link this route to others same route. */
742 if (rt->rt6i_nsiblings) {
743 unsigned int rt6i_nsiblings;
744 struct rt6_info *sibling, *temp_sibling;
745
746 /* Find the first route that have the same metric */
747 sibling = fn->leaf;
748 while (sibling) {
Hannes Frederic Sowa307f2fb2013-07-12 23:46:33 +0200749 if (sibling->rt6i_metric == rt->rt6i_metric &&
750 rt6_qualify_for_ecmp(sibling)) {
Nicolas Dichtel51ebd312012-10-22 03:42:09 +0000751 list_add_tail(&rt->rt6i_siblings,
752 &sibling->rt6i_siblings);
753 break;
754 }
755 sibling = sibling->dst.rt6_next;
756 }
757 /* For each sibling in the list, increment the counter of
758 * siblings. BUG() if counters does not match, list of siblings
759 * is broken!
760 */
761 rt6i_nsiblings = 0;
762 list_for_each_entry_safe(sibling, temp_sibling,
763 &rt->rt6i_siblings, rt6i_siblings) {
764 sibling->rt6i_nsiblings++;
765 BUG_ON(sibling->rt6i_nsiblings != rt->rt6i_nsiblings);
766 rt6i_nsiblings++;
767 }
768 BUG_ON(rt6i_nsiblings != rt->rt6i_nsiblings);
769 }
770
Linus Torvalds1da177e2005-04-16 15:20:36 -0700771 /*
772 * insert node
773 */
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000774 if (!replace) {
775 if (!add)
Joe Perchesf3213832012-05-15 14:11:53 +0000776 pr_warn("NLM_F_CREATE should be set when creating new route\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700777
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000778add:
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100779 if (mx) {
780 err = fib6_commit_metrics(&rt->dst, mx, mx_len);
781 if (err)
782 return err;
783 }
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000784 rt->dst.rt6_next = iter;
785 *ins = rt;
786 rt->rt6i_node = fn;
787 atomic_inc(&rt->rt6i_ref);
788 inet6_rt_notify(RTM_NEWROUTE, rt, info);
789 info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700790
David S. Miller507c9b12011-12-03 17:50:45 -0500791 if (!(fn->fn_flags & RTN_RTINFO)) {
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000792 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
793 fn->fn_flags |= RTN_RTINFO;
794 }
795
796 } else {
797 if (!found) {
798 if (add)
799 goto add;
Joe Perchesf3213832012-05-15 14:11:53 +0000800 pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000801 return -ENOENT;
802 }
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100803 if (mx) {
804 err = fib6_commit_metrics(&rt->dst, mx, mx_len);
805 if (err)
806 return err;
807 }
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000808 *ins = rt;
809 rt->rt6i_node = fn;
810 rt->dst.rt6_next = iter->dst.rt6_next;
811 atomic_inc(&rt->rt6i_ref);
812 inet6_rt_notify(RTM_NEWROUTE, rt, info);
813 rt6_release(iter);
David S. Miller507c9b12011-12-03 17:50:45 -0500814 if (!(fn->fn_flags & RTN_RTINFO)) {
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000815 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
816 fn->fn_flags |= RTN_RTINFO;
817 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700818 }
819
820 return 0;
821}
822
Daniel Lezcano63152fc2008-03-03 23:31:11 -0800823static __inline__ void fib6_start_gc(struct net *net, struct rt6_info *rt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824{
Stephen Hemminger417f28b2008-07-22 14:33:45 -0700825 if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
David S. Miller507c9b12011-12-03 17:50:45 -0500826 (rt->rt6i_flags & (RTF_EXPIRES | RTF_CACHE)))
Stephen Hemminger417f28b2008-07-22 14:33:45 -0700827 mod_timer(&net->ipv6.ip6_fib_timer,
Stephen Hemminger847499c2008-07-21 13:21:35 -0700828 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829}
830
Daniel Lezcano63152fc2008-03-03 23:31:11 -0800831void fib6_force_start_gc(struct net *net)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832{
Stephen Hemminger417f28b2008-07-22 14:33:45 -0700833 if (!timer_pending(&net->ipv6.ip6_fib_timer))
834 mod_timer(&net->ipv6.ip6_fib_timer,
Stephen Hemminger847499c2008-07-21 13:21:35 -0700835 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836}
837
838/*
839 * Add routing information to the routing tree.
840 * <destination addr>/<source addr>
841 * with source addr info in sub-trees
842 */
843
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100844int fib6_add(struct fib6_node *root, struct rt6_info *rt, struct nl_info *info,
845 struct nlattr *mx, int mx_len)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846{
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700847 struct fib6_node *fn, *pn = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848 int err = -ENOMEM;
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000849 int allow_create = 1;
850 int replace_required = 0;
David S. Miller507c9b12011-12-03 17:50:45 -0500851
852 if (info->nlh) {
853 if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000854 allow_create = 0;
David S. Miller507c9b12011-12-03 17:50:45 -0500855 if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000856 replace_required = 1;
857 }
858 if (!allow_create && !replace_required)
Joe Perchesf3213832012-05-15 14:11:53 +0000859 pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860
fan.du9225b232013-07-22 14:21:09 +0800861 fn = fib6_add_1(root, &rt->rt6i_dst.addr, rt->rt6i_dst.plen,
862 offsetof(struct rt6_info, rt6i_dst), allow_create,
863 replace_required);
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000864 if (IS_ERR(fn)) {
865 err = PTR_ERR(fn);
Daniel Borkmannae7b4e12013-09-07 15:13:20 +0200866 fn = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867 goto out;
Lin Ming188c5172012-09-25 15:17:07 +0000868 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700869
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700870 pn = fn;
871
Linus Torvalds1da177e2005-04-16 15:20:36 -0700872#ifdef CONFIG_IPV6_SUBTREES
873 if (rt->rt6i_src.plen) {
874 struct fib6_node *sn;
875
David S. Miller507c9b12011-12-03 17:50:45 -0500876 if (!fn->subtree) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700877 struct fib6_node *sfn;
878
879 /*
880 * Create subtree.
881 *
882 * fn[main tree]
883 * |
884 * sfn[subtree root]
885 * \
886 * sn[new leaf node]
887 */
888
889 /* Create subtree root node */
890 sfn = node_alloc();
David S. Miller507c9b12011-12-03 17:50:45 -0500891 if (!sfn)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 goto st_failure;
893
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800894 sfn->leaf = info->nl_net->ipv6.ip6_null_entry;
895 atomic_inc(&info->nl_net->ipv6.ip6_null_entry->rt6i_ref);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700896 sfn->fn_flags = RTN_ROOT;
897 sfn->fn_sernum = fib6_new_sernum();
898
899 /* Now add the first leaf node to new subtree */
900
901 sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
fan.du9225b232013-07-22 14:21:09 +0800902 rt->rt6i_src.plen,
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000903 offsetof(struct rt6_info, rt6i_src),
904 allow_create, replace_required);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905
Wei Yongjunf950c0e2012-09-20 18:29:56 +0000906 if (IS_ERR(sn)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700907 /* If it is failed, discard just allocated
908 root, and then (in st_failure) stale node
909 in main tree.
910 */
911 node_free(sfn);
Lin Ming188c5172012-09-25 15:17:07 +0000912 err = PTR_ERR(sn);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913 goto st_failure;
914 }
915
916 /* Now link new subtree to main tree */
917 sfn->parent = fn;
918 fn->subtree = sfn;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700919 } else {
920 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
fan.du9225b232013-07-22 14:21:09 +0800921 rt->rt6i_src.plen,
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000922 offsetof(struct rt6_info, rt6i_src),
923 allow_create, replace_required);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700924
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000925 if (IS_ERR(sn)) {
926 err = PTR_ERR(sn);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700927 goto st_failure;
Lin Ming188c5172012-09-25 15:17:07 +0000928 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700929 }
930
David S. Miller507c9b12011-12-03 17:50:45 -0500931 if (!fn->leaf) {
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700932 fn->leaf = rt;
933 atomic_inc(&rt->rt6i_ref);
934 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700935 fn = sn;
936 }
937#endif
938
Michal Kubečeke5fd3872014-03-27 13:04:08 +0100939 err = fib6_add_rt2node(fn, rt, info, mx, mx_len);
David S. Miller507c9b12011-12-03 17:50:45 -0500940 if (!err) {
Daniel Lezcano63152fc2008-03-03 23:31:11 -0800941 fib6_start_gc(info->nl_net, rt);
David S. Miller507c9b12011-12-03 17:50:45 -0500942 if (!(rt->rt6i_flags & RTF_CACHE))
Duan Jiong163cd4e2014-05-09 13:31:43 +0800943 fib6_prune_clones(info->nl_net, pn);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700944 }
945
946out:
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700947 if (err) {
948#ifdef CONFIG_IPV6_SUBTREES
949 /*
950 * If fib6_add_1 has cleared the old leaf pointer in the
951 * super-tree leaf node we have to find a new one for it.
952 */
David S. Miller3c051232008-04-18 01:46:19 -0700953 if (pn != fn && pn->leaf == rt) {
954 pn->leaf = NULL;
955 atomic_dec(&rt->rt6i_ref);
956 }
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700957 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800958 pn->leaf = fib6_find_prefix(info->nl_net, pn);
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700959#if RT6_DEBUG >= 2
960 if (!pn->leaf) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700961 WARN_ON(pn->leaf == NULL);
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800962 pn->leaf = info->nl_net->ipv6.ip6_null_entry;
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700963 }
964#endif
965 atomic_inc(&pn->leaf->rt6i_ref);
966 }
967#endif
Changli Gaod8d1f302010-06-10 23:31:35 -0700968 dst_free(&rt->dst);
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700969 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970 return err;
971
972#ifdef CONFIG_IPV6_SUBTREES
973 /* Subtree creation failed, probably main tree node
974 is orphan. If it is, shoot it.
975 */
976st_failure:
977 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800978 fib6_repair_tree(info->nl_net, fn);
Changli Gaod8d1f302010-06-10 23:31:35 -0700979 dst_free(&rt->dst);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 return err;
981#endif
982}
983
984/*
985 * Routing tree lookup
986 *
987 */
988
989struct lookup_args {
David S. Miller507c9b12011-12-03 17:50:45 -0500990 int offset; /* key offset on rt6_info */
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000991 const struct in6_addr *addr; /* search key */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700992};
993
Wang Yufen437de072014-03-28 12:07:04 +0800994static struct fib6_node *fib6_lookup_1(struct fib6_node *root,
995 struct lookup_args *args)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700996{
997 struct fib6_node *fn;
Al Viroe69a4adc2006-11-14 20:56:00 -0800998 __be32 dir;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700999
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -07001000 if (unlikely(args->offset == 0))
1001 return NULL;
1002
Linus Torvalds1da177e2005-04-16 15:20:36 -07001003 /*
1004 * Descend on a tree
1005 */
1006
1007 fn = root;
1008
1009 for (;;) {
1010 struct fib6_node *next;
1011
1012 dir = addr_bit_set(args->addr, fn->fn_bit);
1013
1014 next = dir ? fn->right : fn->left;
1015
1016 if (next) {
1017 fn = next;
1018 continue;
1019 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020 break;
1021 }
1022
David S. Miller507c9b12011-12-03 17:50:45 -05001023 while (fn) {
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001024 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001025 struct rt6key *key;
1026
1027 key = (struct rt6key *) ((u8 *) fn->leaf +
1028 args->offset);
1029
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -07001030 if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
1031#ifdef CONFIG_IPV6_SUBTREES
Hannes Frederic Sowa3e3be272013-08-07 02:34:31 +02001032 if (fn->subtree) {
1033 struct fib6_node *sfn;
1034 sfn = fib6_lookup_1(fn->subtree,
1035 args + 1);
1036 if (!sfn)
1037 goto backtrack;
1038 fn = sfn;
1039 }
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -07001040#endif
Hannes Frederic Sowa3e3be272013-08-07 02:34:31 +02001041 if (fn->fn_flags & RTN_RTINFO)
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -07001042 return fn;
1043 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044 }
Hannes Frederic Sowa3e3be272013-08-07 02:34:31 +02001045#ifdef CONFIG_IPV6_SUBTREES
1046backtrack:
1047#endif
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -07001048 if (fn->fn_flags & RTN_ROOT)
1049 break;
1050
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051 fn = fn->parent;
1052 }
1053
1054 return NULL;
1055}
1056
Wang Yufen437de072014-03-28 12:07:04 +08001057struct fib6_node *fib6_lookup(struct fib6_node *root, const struct in6_addr *daddr,
1058 const struct in6_addr *saddr)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001060 struct fib6_node *fn;
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -07001061 struct lookup_args args[] = {
1062 {
1063 .offset = offsetof(struct rt6_info, rt6i_dst),
1064 .addr = daddr,
1065 },
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066#ifdef CONFIG_IPV6_SUBTREES
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -07001067 {
1068 .offset = offsetof(struct rt6_info, rt6i_src),
1069 .addr = saddr,
1070 },
Linus Torvalds1da177e2005-04-16 15:20:36 -07001071#endif
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -07001072 {
1073 .offset = 0, /* sentinel */
1074 }
1075 };
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076
YOSHIFUJI Hideakifefc2a62006-08-23 17:21:50 -07001077 fn = fib6_lookup_1(root, daddr ? args : args + 1);
David S. Miller507c9b12011-12-03 17:50:45 -05001078 if (!fn || fn->fn_flags & RTN_TL_ROOT)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001079 fn = root;
1080
1081 return fn;
1082}
1083
1084/*
1085 * Get node with specified destination prefix (and source prefix,
1086 * if subtrees are used)
1087 */
1088
1089
Wang Yufen437de072014-03-28 12:07:04 +08001090static struct fib6_node *fib6_locate_1(struct fib6_node *root,
1091 const struct in6_addr *addr,
1092 int plen, int offset)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001093{
1094 struct fib6_node *fn;
1095
1096 for (fn = root; fn ; ) {
1097 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
1098
1099 /*
1100 * Prefix match
1101 */
1102 if (plen < fn->fn_bit ||
1103 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1104 return NULL;
1105
1106 if (plen == fn->fn_bit)
1107 return fn;
1108
1109 /*
1110 * We have more bits to go
1111 */
1112 if (addr_bit_set(addr, fn->fn_bit))
1113 fn = fn->right;
1114 else
1115 fn = fn->left;
1116 }
1117 return NULL;
1118}
1119
Wang Yufen437de072014-03-28 12:07:04 +08001120struct fib6_node *fib6_locate(struct fib6_node *root,
1121 const struct in6_addr *daddr, int dst_len,
1122 const struct in6_addr *saddr, int src_len)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123{
1124 struct fib6_node *fn;
1125
1126 fn = fib6_locate_1(root, daddr, dst_len,
1127 offsetof(struct rt6_info, rt6i_dst));
1128
1129#ifdef CONFIG_IPV6_SUBTREES
1130 if (src_len) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001131 WARN_ON(saddr == NULL);
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -07001132 if (fn && fn->subtree)
1133 fn = fib6_locate_1(fn->subtree, saddr, src_len,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001134 offsetof(struct rt6_info, rt6i_src));
1135 }
1136#endif
1137
David S. Miller507c9b12011-12-03 17:50:45 -05001138 if (fn && fn->fn_flags & RTN_RTINFO)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001139 return fn;
1140
1141 return NULL;
1142}
1143
1144
1145/*
1146 * Deletion
1147 *
1148 */
1149
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001150static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001151{
David S. Miller507c9b12011-12-03 17:50:45 -05001152 if (fn->fn_flags & RTN_ROOT)
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001153 return net->ipv6.ip6_null_entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154
David S. Miller507c9b12011-12-03 17:50:45 -05001155 while (fn) {
1156 if (fn->left)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157 return fn->left->leaf;
David S. Miller507c9b12011-12-03 17:50:45 -05001158 if (fn->right)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001159 return fn->right->leaf;
1160
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001161 fn = FIB6_SUBTREE(fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001162 }
1163 return NULL;
1164}
1165
1166/*
1167 * Called to trim the tree of intermediate nodes when possible. "fn"
1168 * is the node we want to try and remove.
1169 */
1170
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001171static struct fib6_node *fib6_repair_tree(struct net *net,
1172 struct fib6_node *fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001173{
1174 int children;
1175 int nstate;
1176 struct fib6_node *child, *pn;
1177 struct fib6_walker_t *w;
1178 int iter = 0;
1179
1180 for (;;) {
1181 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1182 iter++;
1183
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001184 WARN_ON(fn->fn_flags & RTN_RTINFO);
1185 WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1186 WARN_ON(fn->leaf != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001187
1188 children = 0;
1189 child = NULL;
Wang Yufen49e253e2014-03-28 12:07:03 +08001190 if (fn->right)
1191 child = fn->right, children |= 1;
1192 if (fn->left)
1193 child = fn->left, children |= 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001195 if (children == 3 || FIB6_SUBTREE(fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196#ifdef CONFIG_IPV6_SUBTREES
1197 /* Subtree root (i.e. fn) may have one child */
David S. Miller507c9b12011-12-03 17:50:45 -05001198 || (children && fn->fn_flags & RTN_ROOT)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001199#endif
1200 ) {
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001201 fn->leaf = fib6_find_prefix(net, fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001202#if RT6_DEBUG >= 2
David S. Miller507c9b12011-12-03 17:50:45 -05001203 if (!fn->leaf) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001204 WARN_ON(!fn->leaf);
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001205 fn->leaf = net->ipv6.ip6_null_entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001206 }
1207#endif
1208 atomic_inc(&fn->leaf->rt6i_ref);
1209 return fn->parent;
1210 }
1211
1212 pn = fn->parent;
1213#ifdef CONFIG_IPV6_SUBTREES
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001214 if (FIB6_SUBTREE(pn) == fn) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001215 WARN_ON(!(fn->fn_flags & RTN_ROOT));
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001216 FIB6_SUBTREE(pn) = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001217 nstate = FWS_L;
1218 } else {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001219 WARN_ON(fn->fn_flags & RTN_ROOT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001220#endif
Wang Yufen49e253e2014-03-28 12:07:03 +08001221 if (pn->right == fn)
1222 pn->right = child;
1223 else if (pn->left == fn)
1224 pn->left = child;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001225#if RT6_DEBUG >= 2
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001226 else
1227 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001228#endif
1229 if (child)
1230 child->parent = pn;
1231 nstate = FWS_R;
1232#ifdef CONFIG_IPV6_SUBTREES
1233 }
1234#endif
1235
1236 read_lock(&fib6_walker_lock);
1237 FOR_WALKERS(w) {
David S. Miller507c9b12011-12-03 17:50:45 -05001238 if (!child) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001239 if (w->root == fn) {
1240 w->root = w->node = NULL;
1241 RT6_TRACE("W %p adjusted by delroot 1\n", w);
1242 } else if (w->node == fn) {
1243 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1244 w->node = pn;
1245 w->state = nstate;
1246 }
1247 } else {
1248 if (w->root == fn) {
1249 w->root = child;
1250 RT6_TRACE("W %p adjusted by delroot 2\n", w);
1251 }
1252 if (w->node == fn) {
1253 w->node = child;
1254 if (children&2) {
1255 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
Wang Yufen8db46f12014-03-28 12:07:02 +08001256 w->state = w->state >= FWS_R ? FWS_U : FWS_INIT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001257 } else {
1258 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
Wang Yufen8db46f12014-03-28 12:07:02 +08001259 w->state = w->state >= FWS_C ? FWS_U : FWS_INIT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001260 }
1261 }
1262 }
1263 }
1264 read_unlock(&fib6_walker_lock);
1265
1266 node_free(fn);
David S. Miller507c9b12011-12-03 17:50:45 -05001267 if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001268 return pn;
1269
1270 rt6_release(pn->leaf);
1271 pn->leaf = NULL;
1272 fn = pn;
1273 }
1274}
1275
1276static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
Thomas Graf86872cb2006-08-22 00:01:08 -07001277 struct nl_info *info)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001278{
1279 struct fib6_walker_t *w;
1280 struct rt6_info *rt = *rtp;
Benjamin Theryc5728722008-03-03 23:34:17 -08001281 struct net *net = info->nl_net;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001282
1283 RT6_TRACE("fib6_del_route\n");
1284
1285 /* Unlink it */
Changli Gaod8d1f302010-06-10 23:31:35 -07001286 *rtp = rt->dst.rt6_next;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001287 rt->rt6i_node = NULL;
Benjamin Theryc5728722008-03-03 23:34:17 -08001288 net->ipv6.rt6_stats->fib_rt_entries--;
1289 net->ipv6.rt6_stats->fib_discarded_routes++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001290
David S. Millerf11e6652007-03-24 20:36:25 -07001291 /* Reset round-robin state, if necessary */
1292 if (fn->rr_ptr == rt)
1293 fn->rr_ptr = NULL;
1294
Nicolas Dichtel51ebd312012-10-22 03:42:09 +00001295 /* Remove this entry from other siblings */
1296 if (rt->rt6i_nsiblings) {
1297 struct rt6_info *sibling, *next_sibling;
1298
1299 list_for_each_entry_safe(sibling, next_sibling,
1300 &rt->rt6i_siblings, rt6i_siblings)
1301 sibling->rt6i_nsiblings--;
1302 rt->rt6i_nsiblings = 0;
1303 list_del_init(&rt->rt6i_siblings);
1304 }
1305
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306 /* Adjust walkers */
1307 read_lock(&fib6_walker_lock);
1308 FOR_WALKERS(w) {
1309 if (w->state == FWS_C && w->leaf == rt) {
1310 RT6_TRACE("walker %p adjusted by delroute\n", w);
Changli Gaod8d1f302010-06-10 23:31:35 -07001311 w->leaf = rt->dst.rt6_next;
David S. Miller507c9b12011-12-03 17:50:45 -05001312 if (!w->leaf)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001313 w->state = FWS_U;
1314 }
1315 }
1316 read_unlock(&fib6_walker_lock);
1317
Changli Gaod8d1f302010-06-10 23:31:35 -07001318 rt->dst.rt6_next = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
Linus Torvalds1da177e2005-04-16 15:20:36 -07001320 /* If it was last route, expunge its radix tree node */
David S. Miller507c9b12011-12-03 17:50:45 -05001321 if (!fn->leaf) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001322 fn->fn_flags &= ~RTN_RTINFO;
Benjamin Theryc5728722008-03-03 23:34:17 -08001323 net->ipv6.rt6_stats->fib_route_nodes--;
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001324 fn = fib6_repair_tree(net, fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001325 }
1326
1327 if (atomic_read(&rt->rt6i_ref) != 1) {
1328 /* This route is used as dummy address holder in some split
1329 * nodes. It is not leaked, but it still holds other resources,
1330 * which must be released in time. So, scan ascendant nodes
1331 * and replace dummy references to this route with references
1332 * to still alive ones.
1333 */
1334 while (fn) {
David S. Miller507c9b12011-12-03 17:50:45 -05001335 if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) {
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001336 fn->leaf = fib6_find_prefix(net, fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001337 atomic_inc(&fn->leaf->rt6i_ref);
1338 rt6_release(rt);
1339 }
1340 fn = fn->parent;
1341 }
1342 /* No more references are possible at this point. */
Pavel Emelyanov2df96af2008-02-18 20:50:42 -08001343 BUG_ON(atomic_read(&rt->rt6i_ref) != 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344 }
1345
Thomas Graf86872cb2006-08-22 00:01:08 -07001346 inet6_rt_notify(RTM_DELROUTE, rt, info);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001347 rt6_release(rt);
1348}
1349
Thomas Graf86872cb2006-08-22 00:01:08 -07001350int fib6_del(struct rt6_info *rt, struct nl_info *info)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001351{
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001352 struct net *net = info->nl_net;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001353 struct fib6_node *fn = rt->rt6i_node;
1354 struct rt6_info **rtp;
1355
1356#if RT6_DEBUG >= 2
Wang Yufen8db46f12014-03-28 12:07:02 +08001357 if (rt->dst.obsolete > 0) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001358 WARN_ON(fn != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359 return -ENOENT;
1360 }
1361#endif
David S. Miller507c9b12011-12-03 17:50:45 -05001362 if (!fn || rt == net->ipv6.ip6_null_entry)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363 return -ENOENT;
1364
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001365 WARN_ON(!(fn->fn_flags & RTN_RTINFO));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001366
David S. Miller507c9b12011-12-03 17:50:45 -05001367 if (!(rt->rt6i_flags & RTF_CACHE)) {
YOSHIFUJI Hideaki150730d2006-08-23 17:22:55 -07001368 struct fib6_node *pn = fn;
1369#ifdef CONFIG_IPV6_SUBTREES
1370 /* clones of this route might be in another subtree */
1371 if (rt->rt6i_src.plen) {
David S. Miller507c9b12011-12-03 17:50:45 -05001372 while (!(pn->fn_flags & RTN_ROOT))
YOSHIFUJI Hideaki150730d2006-08-23 17:22:55 -07001373 pn = pn->parent;
1374 pn = pn->parent;
1375 }
1376#endif
Duan Jiong163cd4e2014-05-09 13:31:43 +08001377 fib6_prune_clones(info->nl_net, pn);
YOSHIFUJI Hideaki150730d2006-08-23 17:22:55 -07001378 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001379
1380 /*
1381 * Walk the leaf entries looking for ourself
1382 */
1383
Changli Gaod8d1f302010-06-10 23:31:35 -07001384 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001385 if (*rtp == rt) {
Thomas Graf86872cb2006-08-22 00:01:08 -07001386 fib6_del_route(fn, rtp, info);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001387 return 0;
1388 }
1389 }
1390 return -ENOENT;
1391}
1392
1393/*
1394 * Tree traversal function.
1395 *
1396 * Certainly, it is not interrupt safe.
1397 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1398 * It means, that we can modify tree during walking
1399 * and use this function for garbage collection, clone pruning,
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09001400 * cleaning tree when a device goes down etc. etc.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 *
1402 * It guarantees that every node will be traversed,
1403 * and that it will be traversed only once.
1404 *
1405 * Callback function w->func may return:
1406 * 0 -> continue walking.
1407 * positive value -> walking is suspended (used by tree dumps,
1408 * and probably by gc, if it will be split to several slices)
1409 * negative value -> terminate walking.
1410 *
1411 * The function itself returns:
1412 * 0 -> walk is complete.
1413 * >0 -> walk is incomplete (i.e. suspended)
1414 * <0 -> walk is terminated by an error.
1415 */
1416
Adrian Bunk90d41122006-08-14 23:49:16 -07001417static int fib6_walk_continue(struct fib6_walker_t *w)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418{
1419 struct fib6_node *fn, *pn;
1420
1421 for (;;) {
1422 fn = w->node;
David S. Miller507c9b12011-12-03 17:50:45 -05001423 if (!fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001424 return 0;
1425
1426 if (w->prune && fn != w->root &&
David S. Miller507c9b12011-12-03 17:50:45 -05001427 fn->fn_flags & RTN_RTINFO && w->state < FWS_C) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428 w->state = FWS_C;
1429 w->leaf = fn->leaf;
1430 }
1431 switch (w->state) {
1432#ifdef CONFIG_IPV6_SUBTREES
1433 case FWS_S:
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001434 if (FIB6_SUBTREE(fn)) {
1435 w->node = FIB6_SUBTREE(fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001436 continue;
1437 }
1438 w->state = FWS_L;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09001439#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001440 case FWS_L:
1441 if (fn->left) {
1442 w->node = fn->left;
1443 w->state = FWS_INIT;
1444 continue;
1445 }
1446 w->state = FWS_R;
1447 case FWS_R:
1448 if (fn->right) {
1449 w->node = fn->right;
1450 w->state = FWS_INIT;
1451 continue;
1452 }
1453 w->state = FWS_C;
1454 w->leaf = fn->leaf;
1455 case FWS_C:
David S. Miller507c9b12011-12-03 17:50:45 -05001456 if (w->leaf && fn->fn_flags & RTN_RTINFO) {
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001457 int err;
1458
Eric Dumazetfa809e22012-06-25 15:37:19 -07001459 if (w->skip) {
1460 w->skip--;
Kumar Sundararajan1c265852014-04-24 09:48:53 -04001461 goto skip;
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001462 }
1463
1464 err = w->func(w);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001465 if (err)
1466 return err;
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001467
1468 w->count++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001469 continue;
1470 }
Kumar Sundararajan1c265852014-04-24 09:48:53 -04001471skip:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001472 w->state = FWS_U;
1473 case FWS_U:
1474 if (fn == w->root)
1475 return 0;
1476 pn = fn->parent;
1477 w->node = pn;
1478#ifdef CONFIG_IPV6_SUBTREES
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001479 if (FIB6_SUBTREE(pn) == fn) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001480 WARN_ON(!(fn->fn_flags & RTN_ROOT));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481 w->state = FWS_L;
1482 continue;
1483 }
1484#endif
1485 if (pn->left == fn) {
1486 w->state = FWS_R;
1487 continue;
1488 }
1489 if (pn->right == fn) {
1490 w->state = FWS_C;
1491 w->leaf = w->node->leaf;
1492 continue;
1493 }
1494#if RT6_DEBUG >= 2
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001495 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001496#endif
1497 }
1498 }
1499}
1500
Adrian Bunk90d41122006-08-14 23:49:16 -07001501static int fib6_walk(struct fib6_walker_t *w)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001502{
1503 int res;
1504
1505 w->state = FWS_INIT;
1506 w->node = w->root;
1507
1508 fib6_walker_link(w);
1509 res = fib6_walk_continue(w);
1510 if (res <= 0)
1511 fib6_walker_unlink(w);
1512 return res;
1513}
1514
1515static int fib6_clean_node(struct fib6_walker_t *w)
1516{
1517 int res;
1518 struct rt6_info *rt;
Benjamin Thery0a8891a2007-10-08 20:39:36 -07001519 struct fib6_cleaner_t *c = container_of(w, struct fib6_cleaner_t, w);
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001520 struct nl_info info = {
1521 .nl_net = c->net,
1522 };
Linus Torvalds1da177e2005-04-16 15:20:36 -07001523
Changli Gaod8d1f302010-06-10 23:31:35 -07001524 for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001525 res = c->func(rt, c->arg);
1526 if (res < 0) {
1527 w->leaf = rt;
Denis V. Lunev528c4ce2007-12-13 09:45:12 -08001528 res = fib6_del(rt, &info);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001529 if (res) {
1530#if RT6_DEBUG >= 2
Joe Perches91df42b2012-05-15 14:11:54 +00001531 pr_debug("%s: del failed: rt=%p@%p err=%d\n",
1532 __func__, rt, rt->rt6i_node, res);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001533#endif
1534 continue;
1535 }
1536 return 0;
1537 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001538 WARN_ON(res != 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539 }
1540 w->leaf = rt;
1541 return 0;
1542}
1543
1544/*
1545 * Convenient frontend to tree walker.
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09001546 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001547 * func is called on each route.
1548 * It may return -1 -> delete this route.
1549 * 0 -> continue walking
1550 *
1551 * prune==1 -> only immediate children of node (certainly,
1552 * ignoring pure split nodes) will be scanned.
1553 */
1554
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001555static void fib6_clean_tree(struct net *net, struct fib6_node *root,
Adrian Bunk8ce11e62006-08-07 21:50:48 -07001556 int (*func)(struct rt6_info *, void *arg),
1557 int prune, void *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001558{
1559 struct fib6_cleaner_t c;
1560
1561 c.w.root = root;
1562 c.w.func = fib6_clean_node;
1563 c.w.prune = prune;
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001564 c.w.count = 0;
1565 c.w.skip = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001566 c.func = func;
1567 c.arg = arg;
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001568 c.net = net;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569
1570 fib6_walk(&c.w);
1571}
1572
Daniel Lezcanof3db4852008-03-03 23:27:06 -08001573void fib6_clean_all(struct net *net, int (*func)(struct rt6_info *, void *arg),
Li RongQing0c3584d2013-12-27 16:32:38 +08001574 void *arg)
Thomas Grafc71099a2006-08-04 23:20:06 -07001575{
Thomas Grafc71099a2006-08-04 23:20:06 -07001576 struct fib6_table *table;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001577 struct hlist_head *head;
Patrick McHardy1b43af52006-08-10 23:11:17 -07001578 unsigned int h;
Thomas Grafc71099a2006-08-04 23:20:06 -07001579
Patrick McHardy1b43af52006-08-10 23:11:17 -07001580 rcu_read_lock();
Neil Hormana33bc5c2009-07-30 18:52:15 -07001581 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
Daniel Lezcanof3db4852008-03-03 23:27:06 -08001582 head = &net->ipv6.fib_table_hash[h];
Sasha Levinb67bfe02013-02-27 17:06:00 -08001583 hlist_for_each_entry_rcu(table, head, tb6_hlist) {
Thomas Grafc71099a2006-08-04 23:20:06 -07001584 write_lock_bh(&table->tb6_lock);
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001585 fib6_clean_tree(net, &table->tb6_root,
Li RongQing0c3584d2013-12-27 16:32:38 +08001586 func, 0, arg);
Thomas Grafc71099a2006-08-04 23:20:06 -07001587 write_unlock_bh(&table->tb6_lock);
1588 }
1589 }
Patrick McHardy1b43af52006-08-10 23:11:17 -07001590 rcu_read_unlock();
Thomas Grafc71099a2006-08-04 23:20:06 -07001591}
1592
Linus Torvalds1da177e2005-04-16 15:20:36 -07001593static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1594{
1595 if (rt->rt6i_flags & RTF_CACHE) {
1596 RT6_TRACE("pruning clone %p\n", rt);
1597 return -1;
1598 }
1599
1600 return 0;
1601}
1602
Duan Jiong163cd4e2014-05-09 13:31:43 +08001603static void fib6_prune_clones(struct net *net, struct fib6_node *fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001604{
Duan Jiong163cd4e2014-05-09 13:31:43 +08001605 fib6_clean_tree(net, fn, fib6_prune_clone, 1, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001606}
1607
1608/*
1609 * Garbage collection
1610 */
1611
1612static struct fib6_gc_args
1613{
1614 int timeout;
1615 int more;
1616} gc_args;
1617
1618static int fib6_age(struct rt6_info *rt, void *arg)
1619{
1620 unsigned long now = jiffies;
1621
1622 /*
1623 * check addrconf expiration here.
1624 * Routes are expired even if they are in use.
1625 *
1626 * Also age clones. Note, that clones are aged out
1627 * only if they are not in use now.
1628 */
1629
David S. Millerd1918542011-12-28 20:19:20 -05001630 if (rt->rt6i_flags & RTF_EXPIRES && rt->dst.expires) {
1631 if (time_after(now, rt->dst.expires)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001632 RT6_TRACE("expiring %p\n", rt);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001633 return -1;
1634 }
1635 gc_args.more++;
1636 } else if (rt->rt6i_flags & RTF_CACHE) {
Changli Gaod8d1f302010-06-10 23:31:35 -07001637 if (atomic_read(&rt->dst.__refcnt) == 0 &&
1638 time_after_eq(now, rt->dst.lastuse + gc_args.timeout)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001639 RT6_TRACE("aging clone %p\n", rt);
1640 return -1;
David S. Miller5339ab82012-01-27 15:14:01 -08001641 } else if (rt->rt6i_flags & RTF_GATEWAY) {
1642 struct neighbour *neigh;
1643 __u8 neigh_flags = 0;
1644
1645 neigh = dst_neigh_lookup(&rt->dst, &rt->rt6i_gateway);
1646 if (neigh) {
1647 neigh_flags = neigh->flags;
1648 neigh_release(neigh);
1649 }
Thomas Graf8bd74512012-06-07 06:51:04 +00001650 if (!(neigh_flags & NTF_ROUTER)) {
David S. Miller5339ab82012-01-27 15:14:01 -08001651 RT6_TRACE("purging route %p via non-router but gateway\n",
1652 rt);
1653 return -1;
1654 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001655 }
1656 gc_args.more++;
1657 }
1658
1659 return 0;
1660}
1661
1662static DEFINE_SPINLOCK(fib6_gc_lock);
1663
Michal Kubeček2ac3ac82013-08-01 10:04:14 +02001664void fib6_run_gc(unsigned long expires, struct net *net, bool force)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001665{
Michal Kubeček49a18d82013-08-01 10:04:24 +02001666 unsigned long now;
1667
Michal Kubeček2ac3ac82013-08-01 10:04:14 +02001668 if (force) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001669 spin_lock_bh(&fib6_gc_lock);
Michal Kubeček2ac3ac82013-08-01 10:04:14 +02001670 } else if (!spin_trylock_bh(&fib6_gc_lock)) {
1671 mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
1672 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001673 }
Michal Kubeček2ac3ac82013-08-01 10:04:14 +02001674 gc_args.timeout = expires ? (int)expires :
1675 net->ipv6.sysctl.ip6_rt_gc_interval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001676
Stephen Hemminger3d0f24a2008-07-22 14:35:50 -07001677 gc_args.more = icmp6_dst_gc();
Daniel Lezcanof3db4852008-03-03 23:27:06 -08001678
Li RongQing0c3584d2013-12-27 16:32:38 +08001679 fib6_clean_all(net, fib6_age, NULL);
Michal Kubeček49a18d82013-08-01 10:04:24 +02001680 now = jiffies;
1681 net->ipv6.ip6_rt_last_gc = now;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001682
1683 if (gc_args.more)
Stephen Hemmingerc8a45222008-07-22 14:34:09 -07001684 mod_timer(&net->ipv6.ip6_fib_timer,
Michal Kubeček49a18d82013-08-01 10:04:24 +02001685 round_jiffies(now
Stephen Hemmingerc8a45222008-07-22 14:34:09 -07001686 + net->ipv6.sysctl.ip6_rt_gc_interval));
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001687 else
1688 del_timer(&net->ipv6.ip6_fib_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001689 spin_unlock_bh(&fib6_gc_lock);
1690}
1691
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001692static void fib6_gc_timer_cb(unsigned long arg)
1693{
Michal Kubeček2ac3ac82013-08-01 10:04:14 +02001694 fib6_run_gc(0, (struct net *)arg, true);
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001695}
1696
Alexey Dobriyan2c8c1e72010-01-17 03:35:32 +00001697static int __net_init fib6_net_init(struct net *net)
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001698{
Eric Dumazet10da66f2010-10-13 08:22:03 +00001699 size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
1700
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001701 setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (unsigned long)net);
Daniel Lezcano63152fc2008-03-03 23:31:11 -08001702
Benjamin Theryc5728722008-03-03 23:34:17 -08001703 net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
1704 if (!net->ipv6.rt6_stats)
1705 goto out_timer;
1706
Eric Dumazet10da66f2010-10-13 08:22:03 +00001707 /* Avoid false sharing : Use at least a full cache line */
1708 size = max_t(size_t, size, L1_CACHE_BYTES);
1709
1710 net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001711 if (!net->ipv6.fib_table_hash)
Benjamin Theryc5728722008-03-03 23:34:17 -08001712 goto out_rt6_stats;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001713
1714 net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
1715 GFP_KERNEL);
1716 if (!net->ipv6.fib6_main_tbl)
1717 goto out_fib_table_hash;
1718
1719 net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001720 net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001721 net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
1722 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
David S. Miller8e773272012-06-11 00:01:52 -07001723 inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001724
1725#ifdef CONFIG_IPV6_MULTIPLE_TABLES
1726 net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
1727 GFP_KERNEL);
1728 if (!net->ipv6.fib6_local_tbl)
1729 goto out_fib6_main_tbl;
1730 net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001731 net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001732 net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
1733 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
David S. Miller8e773272012-06-11 00:01:52 -07001734 inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001735#endif
1736 fib6_tables_init(net);
1737
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001738 return 0;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001739
1740#ifdef CONFIG_IPV6_MULTIPLE_TABLES
1741out_fib6_main_tbl:
1742 kfree(net->ipv6.fib6_main_tbl);
1743#endif
1744out_fib_table_hash:
1745 kfree(net->ipv6.fib_table_hash);
Benjamin Theryc5728722008-03-03 23:34:17 -08001746out_rt6_stats:
1747 kfree(net->ipv6.rt6_stats);
Daniel Lezcano63152fc2008-03-03 23:31:11 -08001748out_timer:
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001749 return -ENOMEM;
Wang Yufen8db46f12014-03-28 12:07:02 +08001750}
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001751
1752static void fib6_net_exit(struct net *net)
1753{
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001754 rt6_ifdown(net, NULL);
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001755 del_timer_sync(&net->ipv6.ip6_fib_timer);
1756
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001757#ifdef CONFIG_IPV6_MULTIPLE_TABLES
David S. Miller8e773272012-06-11 00:01:52 -07001758 inetpeer_invalidate_tree(&net->ipv6.fib6_local_tbl->tb6_peers);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001759 kfree(net->ipv6.fib6_local_tbl);
1760#endif
David S. Miller8e773272012-06-11 00:01:52 -07001761 inetpeer_invalidate_tree(&net->ipv6.fib6_main_tbl->tb6_peers);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001762 kfree(net->ipv6.fib6_main_tbl);
1763 kfree(net->ipv6.fib_table_hash);
Benjamin Theryc5728722008-03-03 23:34:17 -08001764 kfree(net->ipv6.rt6_stats);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001765}
1766
1767static struct pernet_operations fib6_net_ops = {
1768 .init = fib6_net_init,
1769 .exit = fib6_net_exit,
1770};
1771
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001772int __init fib6_init(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001773{
Daniel Lezcanoe0b855902008-03-03 23:24:31 -08001774 int ret = -ENOMEM;
Daniel Lezcano63152fc2008-03-03 23:31:11 -08001775
Linus Torvalds1da177e2005-04-16 15:20:36 -07001776 fib6_node_kmem = kmem_cache_create("fib6_nodes",
1777 sizeof(struct fib6_node),
Daniel Lezcanof845ab62007-12-07 00:45:16 -08001778 0, SLAB_HWCACHE_ALIGN,
Paul Mundt20c2df82007-07-20 10:11:58 +09001779 NULL);
Daniel Lezcanof845ab62007-12-07 00:45:16 -08001780 if (!fib6_node_kmem)
Daniel Lezcanoe0b855902008-03-03 23:24:31 -08001781 goto out;
1782
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001783 ret = register_pernet_subsys(&fib6_net_ops);
1784 if (ret)
Benjamin Theryc5728722008-03-03 23:34:17 -08001785 goto out_kmem_cache_create;
David S. Millere8803b62012-06-16 01:12:19 -07001786
1787 ret = __rtnl_register(PF_INET6, RTM_GETROUTE, NULL, inet6_dump_fib,
1788 NULL);
1789 if (ret)
1790 goto out_unregister_subsys;
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001791out:
1792 return ret;
1793
David S. Millere8803b62012-06-16 01:12:19 -07001794out_unregister_subsys:
1795 unregister_pernet_subsys(&fib6_net_ops);
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001796out_kmem_cache_create:
1797 kmem_cache_destroy(fib6_node_kmem);
1798 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799}
1800
1801void fib6_gc_cleanup(void)
1802{
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001803 unregister_pernet_subsys(&fib6_net_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001804 kmem_cache_destroy(fib6_node_kmem);
1805}
Hannes Frederic Sowa8d2ca1d2013-09-21 16:55:59 +02001806
1807#ifdef CONFIG_PROC_FS
1808
1809struct ipv6_route_iter {
1810 struct seq_net_private p;
1811 struct fib6_walker_t w;
1812 loff_t skip;
1813 struct fib6_table *tbl;
Hannes Frederic Sowa0a67d3e2013-09-21 16:56:10 +02001814 __u32 sernum;
Hannes Frederic Sowa8d2ca1d2013-09-21 16:55:59 +02001815};
1816
1817static int ipv6_route_seq_show(struct seq_file *seq, void *v)
1818{
1819 struct rt6_info *rt = v;
1820 struct ipv6_route_iter *iter = seq->private;
1821
1822 seq_printf(seq, "%pi6 %02x ", &rt->rt6i_dst.addr, rt->rt6i_dst.plen);
1823
1824#ifdef CONFIG_IPV6_SUBTREES
1825 seq_printf(seq, "%pi6 %02x ", &rt->rt6i_src.addr, rt->rt6i_src.plen);
1826#else
1827 seq_puts(seq, "00000000000000000000000000000000 00 ");
1828#endif
1829 if (rt->rt6i_flags & RTF_GATEWAY)
1830 seq_printf(seq, "%pi6", &rt->rt6i_gateway);
1831 else
1832 seq_puts(seq, "00000000000000000000000000000000");
1833
1834 seq_printf(seq, " %08x %08x %08x %08x %8s\n",
1835 rt->rt6i_metric, atomic_read(&rt->dst.__refcnt),
1836 rt->dst.__use, rt->rt6i_flags,
1837 rt->dst.dev ? rt->dst.dev->name : "");
1838 iter->w.leaf = NULL;
1839 return 0;
1840}
1841
1842static int ipv6_route_yield(struct fib6_walker_t *w)
1843{
1844 struct ipv6_route_iter *iter = w->args;
1845
1846 if (!iter->skip)
1847 return 1;
1848
1849 do {
1850 iter->w.leaf = iter->w.leaf->dst.rt6_next;
1851 iter->skip--;
1852 if (!iter->skip && iter->w.leaf)
1853 return 1;
1854 } while (iter->w.leaf);
1855
1856 return 0;
1857}
1858
1859static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter)
1860{
1861 memset(&iter->w, 0, sizeof(iter->w));
1862 iter->w.func = ipv6_route_yield;
1863 iter->w.root = &iter->tbl->tb6_root;
1864 iter->w.state = FWS_INIT;
1865 iter->w.node = iter->w.root;
1866 iter->w.args = iter;
Hannes Frederic Sowa0a67d3e2013-09-21 16:56:10 +02001867 iter->sernum = iter->w.root->fn_sernum;
Hannes Frederic Sowa8d2ca1d2013-09-21 16:55:59 +02001868 INIT_LIST_HEAD(&iter->w.lh);
1869 fib6_walker_link(&iter->w);
1870}
1871
1872static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
1873 struct net *net)
1874{
1875 unsigned int h;
1876 struct hlist_node *node;
1877
1878 if (tbl) {
1879 h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
1880 node = rcu_dereference_bh(hlist_next_rcu(&tbl->tb6_hlist));
1881 } else {
1882 h = 0;
1883 node = NULL;
1884 }
1885
1886 while (!node && h < FIB6_TABLE_HASHSZ) {
1887 node = rcu_dereference_bh(
1888 hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
1889 }
1890 return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
1891}
1892
Hannes Frederic Sowa0a67d3e2013-09-21 16:56:10 +02001893static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
1894{
1895 if (iter->sernum != iter->w.root->fn_sernum) {
1896 iter->sernum = iter->w.root->fn_sernum;
1897 iter->w.state = FWS_INIT;
1898 iter->w.node = iter->w.root;
1899 WARN_ON(iter->w.skip);
1900 iter->w.skip = iter->w.count;
1901 }
1902}
1903
Hannes Frederic Sowa8d2ca1d2013-09-21 16:55:59 +02001904static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
1905{
1906 int r;
1907 struct rt6_info *n;
1908 struct net *net = seq_file_net(seq);
1909 struct ipv6_route_iter *iter = seq->private;
1910
1911 if (!v)
1912 goto iter_table;
1913
1914 n = ((struct rt6_info *)v)->dst.rt6_next;
1915 if (n) {
1916 ++*pos;
1917 return n;
1918 }
1919
1920iter_table:
Hannes Frederic Sowa0a67d3e2013-09-21 16:56:10 +02001921 ipv6_route_check_sernum(iter);
Hannes Frederic Sowa8d2ca1d2013-09-21 16:55:59 +02001922 read_lock(&iter->tbl->tb6_lock);
1923 r = fib6_walk_continue(&iter->w);
1924 read_unlock(&iter->tbl->tb6_lock);
1925 if (r > 0) {
1926 if (v)
1927 ++*pos;
1928 return iter->w.leaf;
1929 } else if (r < 0) {
1930 fib6_walker_unlink(&iter->w);
1931 return NULL;
1932 }
1933 fib6_walker_unlink(&iter->w);
1934
1935 iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
1936 if (!iter->tbl)
1937 return NULL;
1938
1939 ipv6_route_seq_setup_walk(iter);
1940 goto iter_table;
1941}
1942
1943static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
1944 __acquires(RCU_BH)
1945{
1946 struct net *net = seq_file_net(seq);
1947 struct ipv6_route_iter *iter = seq->private;
1948
1949 rcu_read_lock_bh();
1950 iter->tbl = ipv6_route_seq_next_table(NULL, net);
1951 iter->skip = *pos;
1952
1953 if (iter->tbl) {
1954 ipv6_route_seq_setup_walk(iter);
1955 return ipv6_route_seq_next(seq, NULL, pos);
1956 } else {
1957 return NULL;
1958 }
1959}
1960
1961static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
1962{
1963 struct fib6_walker_t *w = &iter->w;
1964 return w->node && !(w->state == FWS_U && w->node == w->root);
1965}
1966
1967static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
1968 __releases(RCU_BH)
1969{
1970 struct ipv6_route_iter *iter = seq->private;
1971
1972 if (ipv6_route_iter_active(iter))
1973 fib6_walker_unlink(&iter->w);
1974
1975 rcu_read_unlock_bh();
1976}
1977
1978static const struct seq_operations ipv6_route_seq_ops = {
1979 .start = ipv6_route_seq_start,
1980 .next = ipv6_route_seq_next,
1981 .stop = ipv6_route_seq_stop,
1982 .show = ipv6_route_seq_show
1983};
1984
1985int ipv6_route_open(struct inode *inode, struct file *file)
1986{
1987 return seq_open_net(inode, file, &ipv6_route_seq_ops,
1988 sizeof(struct ipv6_route_iter));
1989}
1990
1991#endif /* CONFIG_PROC_FS */