blob: 93717435013e0a146c10bc8cf3ea4cbddb627f9b [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.
12 */
13
14/*
15 * Changes:
16 * Yuji SEKIYA @USAGI: Support default route on router node;
17 * remove ip6_null_entry from the top of
18 * routing table.
YOSHIFUJI Hideakic0bece92006-08-23 17:23:25 -070019 * Ville Nuorvala: Fixed routing subtrees.
Linus Torvalds1da177e2005-04-16 15:20:36 -070020 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include <linux/errno.h>
22#include <linux/types.h>
23#include <linux/net.h>
24#include <linux/route.h>
25#include <linux/netdevice.h>
26#include <linux/in6.h>
27#include <linux/init.h>
Thomas Grafc71099a2006-08-04 23:20:06 -070028#include <linux/list.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090029#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070030
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include <net/ipv6.h>
32#include <net/ndisc.h>
33#include <net/addrconf.h>
34
35#include <net/ip6_fib.h>
36#include <net/ip6_route.h>
37
38#define RT6_DEBUG 2
39
40#if RT6_DEBUG >= 3
41#define RT6_TRACE(x...) printk(KERN_DEBUG x)
42#else
43#define RT6_TRACE(x...) do { ; } while (0)
44#endif
45
Christoph Lametere18b8902006-12-06 20:33:20 -080046static struct kmem_cache * fib6_node_kmem __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070047
48enum fib_walk_state_t
49{
50#ifdef CONFIG_IPV6_SUBTREES
51 FWS_S,
52#endif
53 FWS_L,
54 FWS_R,
55 FWS_C,
56 FWS_U
57};
58
59struct fib6_cleaner_t
60{
61 struct fib6_walker_t w;
Benjamin Theryec7d43c2008-03-03 23:31:57 -080062 struct net *net;
Linus Torvalds1da177e2005-04-16 15:20:36 -070063 int (*func)(struct rt6_info *, void *arg);
64 void *arg;
65};
66
Adrian Bunk90d41122006-08-14 23:49:16 -070067static DEFINE_RWLOCK(fib6_walker_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070068
69#ifdef CONFIG_IPV6_SUBTREES
70#define FWS_INIT FWS_S
Linus Torvalds1da177e2005-04-16 15:20:36 -070071#else
72#define FWS_INIT FWS_L
Linus Torvalds1da177e2005-04-16 15:20:36 -070073#endif
74
Benjamin Theryec7d43c2008-03-03 23:31:57 -080075static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
76 struct rt6_info *rt);
Daniel Lezcano8ed67782008-03-04 13:48:30 -080077static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
78static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
Adrian Bunk90d41122006-08-14 23:49:16 -070079static int fib6_walk(struct fib6_walker_t *w);
80static int fib6_walk_continue(struct fib6_walker_t *w);
Linus Torvalds1da177e2005-04-16 15:20:36 -070081
82/*
83 * A routing update causes an increase of the serial number on the
84 * affected subtree. This allows for cached routes to be asynchronously
85 * tested when modifications are made to the destination cache as a
86 * result of redirects, path MTU changes, etc.
87 */
88
89static __u32 rt_sernum;
90
Daniel Lezcano5b7c9312008-03-03 23:28:58 -080091static void fib6_gc_timer_cb(unsigned long arg);
92
Alexey Dobriyanbbef49d2010-02-18 08:13:30 +000093static LIST_HEAD(fib6_walkers);
94#define FOR_WALKERS(w) list_for_each_entry(w, &fib6_walkers, lh)
Linus Torvalds1da177e2005-04-16 15:20:36 -070095
Adrian Bunk90d41122006-08-14 23:49:16 -070096static inline void fib6_walker_link(struct fib6_walker_t *w)
97{
98 write_lock_bh(&fib6_walker_lock);
Alexey Dobriyanbbef49d2010-02-18 08:13:30 +000099 list_add(&w->lh, &fib6_walkers);
Adrian Bunk90d41122006-08-14 23:49:16 -0700100 write_unlock_bh(&fib6_walker_lock);
101}
102
103static inline void fib6_walker_unlink(struct fib6_walker_t *w)
104{
105 write_lock_bh(&fib6_walker_lock);
Alexey Dobriyanbbef49d2010-02-18 08:13:30 +0000106 list_del(&w->lh);
Adrian Bunk90d41122006-08-14 23:49:16 -0700107 write_unlock_bh(&fib6_walker_lock);
108}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109static __inline__ u32 fib6_new_sernum(void)
110{
111 u32 n = ++rt_sernum;
112 if ((__s32)n <= 0)
113 rt_sernum = n = 1;
114 return n;
115}
116
117/*
118 * Auxiliary address test functions for the radix tree.
119 *
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900120 * These assume a 32bit processor (although it will work on
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 * 64bit processors)
122 */
123
124/*
125 * test bit
126 */
YOSHIFUJI Hideaki / 吉藤英明02cdce52010-03-27 01:24:16 +0000127#if defined(__LITTLE_ENDIAN)
128# define BITOP_BE32_SWIZZLE (0x1F & ~7)
129#else
130# define BITOP_BE32_SWIZZLE 0
131#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700132
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000133static __inline__ __be32 addr_bit_set(const void *token, int fn_bit)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134{
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000135 const __be32 *addr = token;
YOSHIFUJI Hideaki / 吉藤英明02cdce52010-03-27 01:24:16 +0000136 /*
137 * Here,
138 * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
139 * is optimized version of
140 * htonl(1 << ((~fn_bit)&0x1F))
141 * See include/asm-generic/bitops/le.h.
142 */
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700143 return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
144 addr[fn_bit >> 5];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145}
146
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147static __inline__ struct fib6_node * node_alloc(void)
148{
149 struct fib6_node *fn;
150
Robert P. J. Dayc3762222007-02-10 01:45:03 -0800151 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
153 return fn;
154}
155
156static __inline__ void node_free(struct fib6_node * fn)
157{
158 kmem_cache_free(fib6_node_kmem, fn);
159}
160
161static __inline__ void rt6_release(struct rt6_info *rt)
162{
163 if (atomic_dec_and_test(&rt->rt6i_ref))
Changli Gaod8d1f302010-06-10 23:31:35 -0700164 dst_free(&rt->dst);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165}
166
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800167static void fib6_link_table(struct net *net, struct fib6_table *tb)
Patrick McHardy1b43af52006-08-10 23:11:17 -0700168{
169 unsigned int h;
170
Thomas Graf375216a2006-10-21 20:20:54 -0700171 /*
172 * Initialize table lock at a single place to give lockdep a key,
173 * tables aren't visible prior to being linked to the list.
174 */
175 rwlock_init(&tb->tb6_lock);
176
Neil Hormana33bc5c2009-07-30 18:52:15 -0700177 h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700178
179 /*
180 * No protection necessary, this is the only list mutatation
181 * operation, tables never disappear once they exist.
182 */
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800183 hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700184}
185
186#ifdef CONFIG_IPV6_MULTIPLE_TABLES
Daniel Lezcanoe0b85592008-03-03 23:24:31 -0800187
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800188static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700189{
190 struct fib6_table *table;
191
192 table = kzalloc(sizeof(*table), GFP_ATOMIC);
David S. Miller507c9b12011-12-03 17:50:45 -0500193 if (table) {
Thomas Grafc71099a2006-08-04 23:20:06 -0700194 table->tb6_id = id;
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800195 table->tb6_root.leaf = net->ipv6.ip6_null_entry;
Thomas Grafc71099a2006-08-04 23:20:06 -0700196 table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
197 }
198
199 return table;
200}
201
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800202struct fib6_table *fib6_new_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700203{
204 struct fib6_table *tb;
205
206 if (id == 0)
207 id = RT6_TABLE_MAIN;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800208 tb = fib6_get_table(net, id);
Thomas Grafc71099a2006-08-04 23:20:06 -0700209 if (tb)
210 return tb;
211
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800212 tb = fib6_alloc_table(net, id);
David S. Miller507c9b12011-12-03 17:50:45 -0500213 if (tb)
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800214 fib6_link_table(net, tb);
Thomas Grafc71099a2006-08-04 23:20:06 -0700215
216 return tb;
217}
218
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800219struct fib6_table *fib6_get_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700220{
221 struct fib6_table *tb;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800222 struct hlist_head *head;
Thomas Grafc71099a2006-08-04 23:20:06 -0700223 struct hlist_node *node;
224 unsigned int h;
225
226 if (id == 0)
227 id = RT6_TABLE_MAIN;
Neil Hormana33bc5c2009-07-30 18:52:15 -0700228 h = id & (FIB6_TABLE_HASHSZ - 1);
Thomas Grafc71099a2006-08-04 23:20:06 -0700229 rcu_read_lock();
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800230 head = &net->ipv6.fib_table_hash[h];
231 hlist_for_each_entry_rcu(tb, node, head, tb6_hlist) {
Thomas Grafc71099a2006-08-04 23:20:06 -0700232 if (tb->tb6_id == id) {
233 rcu_read_unlock();
234 return tb;
235 }
236 }
237 rcu_read_unlock();
238
239 return NULL;
240}
241
Alexey Dobriyan2c8c1e72010-01-17 03:35:32 +0000242static void __net_init fib6_tables_init(struct net *net)
Thomas Grafc71099a2006-08-04 23:20:06 -0700243{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800244 fib6_link_table(net, net->ipv6.fib6_main_tbl);
245 fib6_link_table(net, net->ipv6.fib6_local_tbl);
Thomas Grafc71099a2006-08-04 23:20:06 -0700246}
Thomas Grafc71099a2006-08-04 23:20:06 -0700247#else
248
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800249struct fib6_table *fib6_new_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700250{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800251 return fib6_get_table(net, id);
Thomas Grafc71099a2006-08-04 23:20:06 -0700252}
253
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800254struct fib6_table *fib6_get_table(struct net *net, u32 id)
Thomas Grafc71099a2006-08-04 23:20:06 -0700255{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800256 return net->ipv6.fib6_main_tbl;
Thomas Grafc71099a2006-08-04 23:20:06 -0700257}
258
David S. Miller4c9483b2011-03-12 16:22:43 -0500259struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800260 int flags, pol_lookup_t lookup)
Thomas Grafc71099a2006-08-04 23:20:06 -0700261{
David S. Miller4c9483b2011-03-12 16:22:43 -0500262 return (struct dst_entry *) lookup(net, net->ipv6.fib6_main_tbl, fl6, flags);
Thomas Grafc71099a2006-08-04 23:20:06 -0700263}
264
Alexey Dobriyan2c8c1e72010-01-17 03:35:32 +0000265static void __net_init fib6_tables_init(struct net *net)
Thomas Grafc71099a2006-08-04 23:20:06 -0700266{
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800267 fib6_link_table(net, net->ipv6.fib6_main_tbl);
Thomas Grafc71099a2006-08-04 23:20:06 -0700268}
269
270#endif
271
Patrick McHardy1b43af52006-08-10 23:11:17 -0700272static int fib6_dump_node(struct fib6_walker_t *w)
273{
274 int res;
275 struct rt6_info *rt;
276
Changli Gaod8d1f302010-06-10 23:31:35 -0700277 for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700278 res = rt6_dump_route(rt, w->args);
279 if (res < 0) {
280 /* Frame is full, suspend walking */
281 w->leaf = rt;
282 return 1;
283 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700284 WARN_ON(res == 0);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700285 }
286 w->leaf = NULL;
287 return 0;
288}
289
290static void fib6_dump_end(struct netlink_callback *cb)
291{
292 struct fib6_walker_t *w = (void*)cb->args[2];
293
294 if (w) {
Herbert Xu7891cc82009-01-13 22:17:51 -0800295 if (cb->args[4]) {
296 cb->args[4] = 0;
297 fib6_walker_unlink(w);
298 }
Patrick McHardy1b43af52006-08-10 23:11:17 -0700299 cb->args[2] = 0;
300 kfree(w);
301 }
302 cb->done = (void*)cb->args[3];
303 cb->args[1] = 3;
304}
305
306static int fib6_dump_done(struct netlink_callback *cb)
307{
308 fib6_dump_end(cb);
309 return cb->done ? cb->done(cb) : 0;
310}
311
312static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
313 struct netlink_callback *cb)
314{
315 struct fib6_walker_t *w;
316 int res;
317
318 w = (void *)cb->args[2];
319 w->root = &table->tb6_root;
320
321 if (cb->args[4] == 0) {
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000322 w->count = 0;
323 w->skip = 0;
324
Patrick McHardy1b43af52006-08-10 23:11:17 -0700325 read_lock_bh(&table->tb6_lock);
326 res = fib6_walk(w);
327 read_unlock_bh(&table->tb6_lock);
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000328 if (res > 0) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700329 cb->args[4] = 1;
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000330 cb->args[5] = w->root->fn_sernum;
331 }
Patrick McHardy1b43af52006-08-10 23:11:17 -0700332 } else {
Patrick McHardy2bec5a32010-02-08 05:19:03 +0000333 if (cb->args[5] != w->root->fn_sernum) {
334 /* Begin at the root if the tree changed */
335 cb->args[5] = w->root->fn_sernum;
336 w->state = FWS_INIT;
337 w->node = w->root;
338 w->skip = w->count;
339 } else
340 w->skip = 0;
341
Patrick McHardy1b43af52006-08-10 23:11:17 -0700342 read_lock_bh(&table->tb6_lock);
343 res = fib6_walk_continue(w);
344 read_unlock_bh(&table->tb6_lock);
Herbert Xu7891cc82009-01-13 22:17:51 -0800345 if (res <= 0) {
346 fib6_walker_unlink(w);
347 cb->args[4] = 0;
Patrick McHardy1b43af52006-08-10 23:11:17 -0700348 }
Patrick McHardy1b43af52006-08-10 23:11:17 -0700349 }
Herbert Xu7891cc82009-01-13 22:17:51 -0800350
Patrick McHardy1b43af52006-08-10 23:11:17 -0700351 return res;
352}
353
Thomas Grafc127ea22007-03-22 11:58:32 -0700354static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
Patrick McHardy1b43af52006-08-10 23:11:17 -0700355{
YOSHIFUJI Hideaki3b1e0a62008-03-26 02:26:21 +0900356 struct net *net = sock_net(skb->sk);
Patrick McHardy1b43af52006-08-10 23:11:17 -0700357 unsigned int h, s_h;
358 unsigned int e = 0, s_e;
359 struct rt6_rtnl_dump_arg arg;
360 struct fib6_walker_t *w;
361 struct fib6_table *tb;
362 struct hlist_node *node;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800363 struct hlist_head *head;
Patrick McHardy1b43af52006-08-10 23:11:17 -0700364 int res = 0;
365
366 s_h = cb->args[0];
367 s_e = cb->args[1];
368
369 w = (void *)cb->args[2];
David S. Miller507c9b12011-12-03 17:50:45 -0500370 if (!w) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700371 /* New dump:
372 *
373 * 1. hook callback destructor.
374 */
375 cb->args[3] = (long)cb->done;
376 cb->done = fib6_dump_done;
377
378 /*
379 * 2. allocate and initialize walker.
380 */
381 w = kzalloc(sizeof(*w), GFP_ATOMIC);
David S. Miller507c9b12011-12-03 17:50:45 -0500382 if (!w)
Patrick McHardy1b43af52006-08-10 23:11:17 -0700383 return -ENOMEM;
384 w->func = fib6_dump_node;
385 cb->args[2] = (long)w;
386 }
387
388 arg.skb = skb;
389 arg.cb = cb;
Brian Haley191cd582008-08-14 15:33:21 -0700390 arg.net = net;
Patrick McHardy1b43af52006-08-10 23:11:17 -0700391 w->args = &arg;
392
Eric Dumazete67f88d2011-04-27 22:56:07 +0000393 rcu_read_lock();
Neil Hormana33bc5c2009-07-30 18:52:15 -0700394 for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700395 e = 0;
Daniel Lezcano58f09b72008-03-03 23:25:27 -0800396 head = &net->ipv6.fib_table_hash[h];
Eric Dumazete67f88d2011-04-27 22:56:07 +0000397 hlist_for_each_entry_rcu(tb, node, head, tb6_hlist) {
Patrick McHardy1b43af52006-08-10 23:11:17 -0700398 if (e < s_e)
399 goto next;
400 res = fib6_dump_table(tb, skb, cb);
401 if (res != 0)
402 goto out;
403next:
404 e++;
405 }
406 }
407out:
Eric Dumazete67f88d2011-04-27 22:56:07 +0000408 rcu_read_unlock();
Patrick McHardy1b43af52006-08-10 23:11:17 -0700409 cb->args[1] = e;
410 cb->args[0] = h;
411
412 res = res < 0 ? res : skb->len;
413 if (res <= 0)
414 fib6_dump_end(cb);
415 return res;
416}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417
418/*
419 * Routing Table
420 *
421 * return the appropriate node for a routing tree "add" operation
422 * by either creating and inserting or by returning an existing
423 * node.
424 */
425
426static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
427 int addrlen, int plen,
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000428 int offset, int allow_create,
429 int replace_required)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700430{
431 struct fib6_node *fn, *in, *ln;
432 struct fib6_node *pn = NULL;
433 struct rt6key *key;
434 int bit;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900435 __be32 dir = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436 __u32 sernum = fib6_new_sernum();
437
438 RT6_TRACE("fib6_add_1\n");
439
440 /* insert node in tree */
441
442 fn = root;
443
444 do {
445 key = (struct rt6key *)((u8 *)fn->leaf + offset);
446
447 /*
448 * Prefix match
449 */
450 if (plen < fn->fn_bit ||
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000451 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
Matti Vaittinen14df0152011-11-16 21:18:02 +0000452 if (!allow_create) {
453 if (replace_required) {
David S. Miller8d267842011-11-17 03:18:28 -0500454 pr_warn("IPv6: Can't replace route, "
455 "no match found\n");
Matti Vaittinen14df0152011-11-16 21:18:02 +0000456 return ERR_PTR(-ENOENT);
457 }
David S. Miller8d267842011-11-17 03:18:28 -0500458 pr_warn("IPv6: NLM_F_CREATE should be set "
459 "when creating new route\n");
Matti Vaittinen14df0152011-11-16 21:18:02 +0000460 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700461 goto insert_above;
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000462 }
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900463
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 /*
465 * Exact match ?
466 */
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900467
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468 if (plen == fn->fn_bit) {
469 /* clean up an intermediate node */
David S. Miller507c9b12011-12-03 17:50:45 -0500470 if (!(fn->fn_flags & RTN_RTINFO)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700471 rt6_release(fn->leaf);
472 fn->leaf = NULL;
473 }
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900474
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 fn->fn_sernum = sernum;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900476
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 return fn;
478 }
479
480 /*
481 * We have more bits to go
482 */
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900483
Linus Torvalds1da177e2005-04-16 15:20:36 -0700484 /* Try to walk down on tree. */
485 fn->fn_sernum = sernum;
486 dir = addr_bit_set(addr, fn->fn_bit);
487 pn = fn;
488 fn = dir ? fn->right: fn->left;
489 } while (fn);
490
Matti Vaittinen14df0152011-11-16 21:18:02 +0000491 if (!allow_create) {
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000492 /* We should not create new node because
493 * NLM_F_REPLACE was specified without NLM_F_CREATE
494 * I assume it is safe to require NLM_F_CREATE when
495 * REPLACE flag is used! Later we may want to remove the
496 * check for replace_required, because according
497 * to netlink specification, NLM_F_CREATE
498 * MUST be specified if new route is created.
499 * That would keep IPv6 consistent with IPv4
500 */
Matti Vaittinen14df0152011-11-16 21:18:02 +0000501 if (replace_required) {
David S. Miller8d267842011-11-17 03:18:28 -0500502 pr_warn("IPv6: Can't replace route, no match found\n");
Matti Vaittinen14df0152011-11-16 21:18:02 +0000503 return ERR_PTR(-ENOENT);
504 }
David S. Miller8d267842011-11-17 03:18:28 -0500505 pr_warn("IPv6: NLM_F_CREATE should be set "
506 "when creating new route\n");
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000507 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508 /*
509 * We walked to the bottom of tree.
510 * Create new leaf node without children.
511 */
512
513 ln = node_alloc();
514
David S. Miller507c9b12011-12-03 17:50:45 -0500515 if (!ln)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516 return NULL;
517 ln->fn_bit = plen;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900518
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 ln->parent = pn;
520 ln->fn_sernum = sernum;
521
522 if (dir)
523 pn->right = ln;
524 else
525 pn->left = ln;
526
527 return ln;
528
529
530insert_above:
531 /*
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900532 * split since we don't have a common prefix anymore or
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533 * we have a less significant route.
534 * we've to insert an intermediate node on the list
535 * this new node will point to the one we need to create
536 * and the current
537 */
538
539 pn = fn->parent;
540
541 /* find 1st bit in difference between the 2 addrs.
542
YOSHIFUJI Hideaki971f3592005-11-08 09:37:56 -0800543 See comment in __ipv6_addr_diff: bit may be an invalid value,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544 but if it is >= plen, the value is ignored in any case.
545 */
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900546
YOSHIFUJI Hideaki971f3592005-11-08 09:37:56 -0800547 bit = __ipv6_addr_diff(addr, &key->addr, addrlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700548
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900549 /*
550 * (intermediate)[in]
Linus Torvalds1da177e2005-04-16 15:20:36 -0700551 * / \
552 * (new leaf node)[ln] (old node)[fn]
553 */
554 if (plen > bit) {
555 in = node_alloc();
556 ln = node_alloc();
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900557
David S. Miller507c9b12011-12-03 17:50:45 -0500558 if (!in || !ln) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559 if (in)
560 node_free(in);
561 if (ln)
562 node_free(ln);
563 return NULL;
564 }
565
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900566 /*
567 * new intermediate node.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568 * RTN_RTINFO will
569 * be off since that an address that chooses one of
570 * the branches would not match less specific routes
571 * in the other branch
572 */
573
574 in->fn_bit = bit;
575
576 in->parent = pn;
577 in->leaf = fn->leaf;
578 atomic_inc(&in->leaf->rt6i_ref);
579
580 in->fn_sernum = sernum;
581
582 /* update parent pointer */
583 if (dir)
584 pn->right = in;
585 else
586 pn->left = in;
587
588 ln->fn_bit = plen;
589
590 ln->parent = in;
591 fn->parent = in;
592
593 ln->fn_sernum = sernum;
594
595 if (addr_bit_set(addr, bit)) {
596 in->right = ln;
597 in->left = fn;
598 } else {
599 in->left = ln;
600 in->right = fn;
601 }
602 } else { /* plen <= bit */
603
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900604 /*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605 * (new leaf node)[ln]
606 * / \
607 * (old node)[fn] NULL
608 */
609
610 ln = node_alloc();
611
David S. Miller507c9b12011-12-03 17:50:45 -0500612 if (!ln)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700613 return NULL;
614
615 ln->fn_bit = plen;
616
617 ln->parent = pn;
618
619 ln->fn_sernum = sernum;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +0900620
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621 if (dir)
622 pn->right = ln;
623 else
624 pn->left = ln;
625
626 if (addr_bit_set(&key->addr, plen))
627 ln->right = fn;
628 else
629 ln->left = fn;
630
631 fn->parent = ln;
632 }
633 return ln;
634}
635
636/*
637 * Insert routing information in a node.
638 */
639
640static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
Thomas Graf86872cb2006-08-22 00:01:08 -0700641 struct nl_info *info)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642{
643 struct rt6_info *iter = NULL;
644 struct rt6_info **ins;
David S. Miller507c9b12011-12-03 17:50:45 -0500645 int replace = (info->nlh &&
646 (info->nlh->nlmsg_flags & NLM_F_REPLACE));
647 int add = (!info->nlh ||
648 (info->nlh->nlmsg_flags & NLM_F_CREATE));
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000649 int found = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700650
651 ins = &fn->leaf;
652
David S. Miller507c9b12011-12-03 17:50:45 -0500653 for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700654 /*
655 * Search for duplicates
656 */
657
658 if (iter->rt6i_metric == rt->rt6i_metric) {
659 /*
660 * Same priority level
661 */
David S. Miller507c9b12011-12-03 17:50:45 -0500662 if (info->nlh &&
663 (info->nlh->nlmsg_flags & NLM_F_EXCL))
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000664 return -EEXIST;
665 if (replace) {
666 found++;
667 break;
668 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700669
David S. Millerd1918542011-12-28 20:19:20 -0500670 if (iter->dst.dev == rt->dst.dev &&
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671 iter->rt6i_idev == rt->rt6i_idev &&
672 ipv6_addr_equal(&iter->rt6i_gateway,
673 &rt->rt6i_gateway)) {
David S. Miller507c9b12011-12-03 17:50:45 -0500674 if (!(iter->rt6i_flags & RTF_EXPIRES))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 return -EEXIST;
Gao feng1716a962012-04-06 00:13:10 +0000676 if (!(rt->rt6i_flags & RTF_EXPIRES))
677 rt6_clean_expires(iter);
678 else
679 rt6_set_expires(iter, rt->dst.expires);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 return -EEXIST;
681 }
682 }
683
684 if (iter->rt6i_metric > rt->rt6i_metric)
685 break;
686
Changli Gaod8d1f302010-06-10 23:31:35 -0700687 ins = &iter->dst.rt6_next;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688 }
689
David S. Millerf11e6652007-03-24 20:36:25 -0700690 /* Reset round-robin state, if necessary */
691 if (ins == &fn->leaf)
692 fn->rr_ptr = NULL;
693
Linus Torvalds1da177e2005-04-16 15:20:36 -0700694 /*
695 * insert node
696 */
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000697 if (!replace) {
698 if (!add)
David S. Miller8d267842011-11-17 03:18:28 -0500699 pr_warn("IPv6: NLM_F_CREATE should be set when creating new route\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000701add:
702 rt->dst.rt6_next = iter;
703 *ins = rt;
704 rt->rt6i_node = fn;
705 atomic_inc(&rt->rt6i_ref);
706 inet6_rt_notify(RTM_NEWROUTE, rt, info);
707 info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700708
David S. Miller507c9b12011-12-03 17:50:45 -0500709 if (!(fn->fn_flags & RTN_RTINFO)) {
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000710 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
711 fn->fn_flags |= RTN_RTINFO;
712 }
713
714 } else {
715 if (!found) {
716 if (add)
717 goto add;
David S. Miller8d267842011-11-17 03:18:28 -0500718 pr_warn("IPv6: NLM_F_REPLACE set, but no existing node found!\n");
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000719 return -ENOENT;
720 }
721 *ins = rt;
722 rt->rt6i_node = fn;
723 rt->dst.rt6_next = iter->dst.rt6_next;
724 atomic_inc(&rt->rt6i_ref);
725 inet6_rt_notify(RTM_NEWROUTE, rt, info);
726 rt6_release(iter);
David S. Miller507c9b12011-12-03 17:50:45 -0500727 if (!(fn->fn_flags & RTN_RTINFO)) {
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000728 info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
729 fn->fn_flags |= RTN_RTINFO;
730 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731 }
732
733 return 0;
734}
735
Daniel Lezcano63152fc2008-03-03 23:31:11 -0800736static __inline__ void fib6_start_gc(struct net *net, struct rt6_info *rt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700737{
Stephen Hemminger417f28b2008-07-22 14:33:45 -0700738 if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
David S. Miller507c9b12011-12-03 17:50:45 -0500739 (rt->rt6i_flags & (RTF_EXPIRES | RTF_CACHE)))
Stephen Hemminger417f28b2008-07-22 14:33:45 -0700740 mod_timer(&net->ipv6.ip6_fib_timer,
Stephen Hemminger847499c2008-07-21 13:21:35 -0700741 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700742}
743
Daniel Lezcano63152fc2008-03-03 23:31:11 -0800744void fib6_force_start_gc(struct net *net)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700745{
Stephen Hemminger417f28b2008-07-22 14:33:45 -0700746 if (!timer_pending(&net->ipv6.ip6_fib_timer))
747 mod_timer(&net->ipv6.ip6_fib_timer,
Stephen Hemminger847499c2008-07-21 13:21:35 -0700748 jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749}
750
751/*
752 * Add routing information to the routing tree.
753 * <destination addr>/<source addr>
754 * with source addr info in sub-trees
755 */
756
Thomas Graf86872cb2006-08-22 00:01:08 -0700757int fib6_add(struct fib6_node *root, struct rt6_info *rt, struct nl_info *info)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700758{
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700759 struct fib6_node *fn, *pn = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700760 int err = -ENOMEM;
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000761 int allow_create = 1;
762 int replace_required = 0;
David S. Miller507c9b12011-12-03 17:50:45 -0500763
764 if (info->nlh) {
765 if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000766 allow_create = 0;
David S. Miller507c9b12011-12-03 17:50:45 -0500767 if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000768 replace_required = 1;
769 }
770 if (!allow_create && !replace_required)
David S. Miller8d267842011-11-17 03:18:28 -0500771 pr_warn("IPv6: RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772
773 fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
David S. Miller507c9b12011-12-03 17:50:45 -0500774 rt->rt6i_dst.plen, offsetof(struct rt6_info, rt6i_dst),
775 allow_create, replace_required);
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000776
777 if (IS_ERR(fn)) {
778 err = PTR_ERR(fn);
779 fn = NULL;
780 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700781
David S. Miller507c9b12011-12-03 17:50:45 -0500782 if (!fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783 goto out;
784
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700785 pn = fn;
786
Linus Torvalds1da177e2005-04-16 15:20:36 -0700787#ifdef CONFIG_IPV6_SUBTREES
788 if (rt->rt6i_src.plen) {
789 struct fib6_node *sn;
790
David S. Miller507c9b12011-12-03 17:50:45 -0500791 if (!fn->subtree) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700792 struct fib6_node *sfn;
793
794 /*
795 * Create subtree.
796 *
797 * fn[main tree]
798 * |
799 * sfn[subtree root]
800 * \
801 * sn[new leaf node]
802 */
803
804 /* Create subtree root node */
805 sfn = node_alloc();
David S. Miller507c9b12011-12-03 17:50:45 -0500806 if (!sfn)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700807 goto st_failure;
808
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800809 sfn->leaf = info->nl_net->ipv6.ip6_null_entry;
810 atomic_inc(&info->nl_net->ipv6.ip6_null_entry->rt6i_ref);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700811 sfn->fn_flags = RTN_ROOT;
812 sfn->fn_sernum = fib6_new_sernum();
813
814 /* Now add the first leaf node to new subtree */
815
816 sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
817 sizeof(struct in6_addr), rt->rt6i_src.plen,
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000818 offsetof(struct rt6_info, rt6i_src),
819 allow_create, replace_required);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820
David S. Miller507c9b12011-12-03 17:50:45 -0500821 if (!sn) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700822 /* If it is failed, discard just allocated
823 root, and then (in st_failure) stale node
824 in main tree.
825 */
826 node_free(sfn);
827 goto st_failure;
828 }
829
830 /* Now link new subtree to main tree */
831 sfn->parent = fn;
832 fn->subtree = sfn;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833 } else {
834 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
835 sizeof(struct in6_addr), rt->rt6i_src.plen,
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000836 offsetof(struct rt6_info, rt6i_src),
837 allow_create, replace_required);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Matti Vaittinen4a287eb2011-11-14 00:15:14 +0000839 if (IS_ERR(sn)) {
840 err = PTR_ERR(sn);
841 sn = NULL;
842 }
David S. Miller507c9b12011-12-03 17:50:45 -0500843 if (!sn)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844 goto st_failure;
845 }
846
David S. Miller507c9b12011-12-03 17:50:45 -0500847 if (!fn->leaf) {
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700848 fn->leaf = rt;
849 atomic_inc(&rt->rt6i_ref);
850 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851 fn = sn;
852 }
853#endif
854
Thomas Graf86872cb2006-08-22 00:01:08 -0700855 err = fib6_add_rt2node(fn, rt, info);
David S. Miller507c9b12011-12-03 17:50:45 -0500856 if (!err) {
Daniel Lezcano63152fc2008-03-03 23:31:11 -0800857 fib6_start_gc(info->nl_net, rt);
David S. Miller507c9b12011-12-03 17:50:45 -0500858 if (!(rt->rt6i_flags & RTF_CACHE))
Benjamin Theryec7d43c2008-03-03 23:31:57 -0800859 fib6_prune_clones(info->nl_net, pn, rt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860 }
861
862out:
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700863 if (err) {
864#ifdef CONFIG_IPV6_SUBTREES
865 /*
866 * If fib6_add_1 has cleared the old leaf pointer in the
867 * super-tree leaf node we have to find a new one for it.
868 */
David S. Miller3c051232008-04-18 01:46:19 -0700869 if (pn != fn && pn->leaf == rt) {
870 pn->leaf = NULL;
871 atomic_dec(&rt->rt6i_ref);
872 }
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700873 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800874 pn->leaf = fib6_find_prefix(info->nl_net, pn);
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700875#if RT6_DEBUG >= 2
876 if (!pn->leaf) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700877 WARN_ON(pn->leaf == NULL);
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800878 pn->leaf = info->nl_net->ipv6.ip6_null_entry;
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700879 }
880#endif
881 atomic_inc(&pn->leaf->rt6i_ref);
882 }
883#endif
Changli Gaod8d1f302010-06-10 23:31:35 -0700884 dst_free(&rt->dst);
YOSHIFUJI Hideaki66729e12006-08-23 17:20:34 -0700885 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886 return err;
887
888#ifdef CONFIG_IPV6_SUBTREES
889 /* Subtree creation failed, probably main tree node
890 is orphan. If it is, shoot it.
891 */
892st_failure:
893 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
Daniel Lezcano8ed67782008-03-04 13:48:30 -0800894 fib6_repair_tree(info->nl_net, fn);
Changli Gaod8d1f302010-06-10 23:31:35 -0700895 dst_free(&rt->dst);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700896 return err;
897#endif
898}
899
900/*
901 * Routing tree lookup
902 *
903 */
904
905struct lookup_args {
David S. Miller507c9b12011-12-03 17:50:45 -0500906 int offset; /* key offset on rt6_info */
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000907 const struct in6_addr *addr; /* search key */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700908};
909
910static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
911 struct lookup_args *args)
912{
913 struct fib6_node *fn;
Al Viroe69a4ad2006-11-14 20:56:00 -0800914 __be32 dir;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700915
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -0700916 if (unlikely(args->offset == 0))
917 return NULL;
918
Linus Torvalds1da177e2005-04-16 15:20:36 -0700919 /*
920 * Descend on a tree
921 */
922
923 fn = root;
924
925 for (;;) {
926 struct fib6_node *next;
927
928 dir = addr_bit_set(args->addr, fn->fn_bit);
929
930 next = dir ? fn->right : fn->left;
931
932 if (next) {
933 fn = next;
934 continue;
935 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936 break;
937 }
938
David S. Miller507c9b12011-12-03 17:50:45 -0500939 while (fn) {
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -0700940 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941 struct rt6key *key;
942
943 key = (struct rt6key *) ((u8 *) fn->leaf +
944 args->offset);
945
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -0700946 if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
947#ifdef CONFIG_IPV6_SUBTREES
948 if (fn->subtree)
949 fn = fib6_lookup_1(fn->subtree, args + 1);
950#endif
951 if (!fn || fn->fn_flags & RTN_RTINFO)
952 return fn;
953 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954 }
955
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -0700956 if (fn->fn_flags & RTN_ROOT)
957 break;
958
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959 fn = fn->parent;
960 }
961
962 return NULL;
963}
964
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000965struct fib6_node * fib6_lookup(struct fib6_node *root, const struct in6_addr *daddr,
966 const struct in6_addr *saddr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 struct fib6_node *fn;
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -0700969 struct lookup_args args[] = {
970 {
971 .offset = offsetof(struct rt6_info, rt6i_dst),
972 .addr = daddr,
973 },
Linus Torvalds1da177e2005-04-16 15:20:36 -0700974#ifdef CONFIG_IPV6_SUBTREES
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -0700975 {
976 .offset = offsetof(struct rt6_info, rt6i_src),
977 .addr = saddr,
978 },
Linus Torvalds1da177e2005-04-16 15:20:36 -0700979#endif
YOSHIFUJI Hideaki825e2882006-08-23 17:21:29 -0700980 {
981 .offset = 0, /* sentinel */
982 }
983 };
Linus Torvalds1da177e2005-04-16 15:20:36 -0700984
YOSHIFUJI Hideakifefc2a62006-08-23 17:21:50 -0700985 fn = fib6_lookup_1(root, daddr ? args : args + 1);
David S. Miller507c9b12011-12-03 17:50:45 -0500986 if (!fn || fn->fn_flags & RTN_TL_ROOT)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700987 fn = root;
988
989 return fn;
990}
991
992/*
993 * Get node with specified destination prefix (and source prefix,
994 * if subtrees are used)
995 */
996
997
998static struct fib6_node * fib6_locate_1(struct fib6_node *root,
Eric Dumazetb71d1d42011-04-22 04:53:02 +0000999 const struct in6_addr *addr,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001000 int plen, int offset)
1001{
1002 struct fib6_node *fn;
1003
1004 for (fn = root; fn ; ) {
1005 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
1006
1007 /*
1008 * Prefix match
1009 */
1010 if (plen < fn->fn_bit ||
1011 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
1012 return NULL;
1013
1014 if (plen == fn->fn_bit)
1015 return fn;
1016
1017 /*
1018 * We have more bits to go
1019 */
1020 if (addr_bit_set(addr, fn->fn_bit))
1021 fn = fn->right;
1022 else
1023 fn = fn->left;
1024 }
1025 return NULL;
1026}
1027
1028struct fib6_node * fib6_locate(struct fib6_node *root,
Eric Dumazetb71d1d42011-04-22 04:53:02 +00001029 const struct in6_addr *daddr, int dst_len,
1030 const struct in6_addr *saddr, int src_len)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001031{
1032 struct fib6_node *fn;
1033
1034 fn = fib6_locate_1(root, daddr, dst_len,
1035 offsetof(struct rt6_info, rt6i_dst));
1036
1037#ifdef CONFIG_IPV6_SUBTREES
1038 if (src_len) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001039 WARN_ON(saddr == NULL);
YOSHIFUJI Hideaki3fc5e042006-08-23 17:21:12 -07001040 if (fn && fn->subtree)
1041 fn = fib6_locate_1(fn->subtree, saddr, src_len,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001042 offsetof(struct rt6_info, rt6i_src));
1043 }
1044#endif
1045
David S. Miller507c9b12011-12-03 17:50:45 -05001046 if (fn && fn->fn_flags & RTN_RTINFO)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001047 return fn;
1048
1049 return NULL;
1050}
1051
1052
1053/*
1054 * Deletion
1055 *
1056 */
1057
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001058static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059{
David S. Miller507c9b12011-12-03 17:50:45 -05001060 if (fn->fn_flags & RTN_ROOT)
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001061 return net->ipv6.ip6_null_entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062
David S. Miller507c9b12011-12-03 17:50:45 -05001063 while (fn) {
1064 if (fn->left)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001065 return fn->left->leaf;
David S. Miller507c9b12011-12-03 17:50:45 -05001066 if (fn->right)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067 return fn->right->leaf;
1068
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001069 fn = FIB6_SUBTREE(fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001070 }
1071 return NULL;
1072}
1073
1074/*
1075 * Called to trim the tree of intermediate nodes when possible. "fn"
1076 * is the node we want to try and remove.
1077 */
1078
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001079static struct fib6_node *fib6_repair_tree(struct net *net,
1080 struct fib6_node *fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001081{
1082 int children;
1083 int nstate;
1084 struct fib6_node *child, *pn;
1085 struct fib6_walker_t *w;
1086 int iter = 0;
1087
1088 for (;;) {
1089 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1090 iter++;
1091
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001092 WARN_ON(fn->fn_flags & RTN_RTINFO);
1093 WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1094 WARN_ON(fn->leaf != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001095
1096 children = 0;
1097 child = NULL;
1098 if (fn->right) child = fn->right, children |= 1;
1099 if (fn->left) child = fn->left, children |= 2;
1100
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001101 if (children == 3 || FIB6_SUBTREE(fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001102#ifdef CONFIG_IPV6_SUBTREES
1103 /* Subtree root (i.e. fn) may have one child */
David S. Miller507c9b12011-12-03 17:50:45 -05001104 || (children && fn->fn_flags & RTN_ROOT)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001105#endif
1106 ) {
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001107 fn->leaf = fib6_find_prefix(net, fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108#if RT6_DEBUG >= 2
David S. Miller507c9b12011-12-03 17:50:45 -05001109 if (!fn->leaf) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001110 WARN_ON(!fn->leaf);
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001111 fn->leaf = net->ipv6.ip6_null_entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001112 }
1113#endif
1114 atomic_inc(&fn->leaf->rt6i_ref);
1115 return fn->parent;
1116 }
1117
1118 pn = fn->parent;
1119#ifdef CONFIG_IPV6_SUBTREES
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001120 if (FIB6_SUBTREE(pn) == fn) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001121 WARN_ON(!(fn->fn_flags & RTN_ROOT));
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001122 FIB6_SUBTREE(pn) = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123 nstate = FWS_L;
1124 } else {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001125 WARN_ON(fn->fn_flags & RTN_ROOT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001126#endif
1127 if (pn->right == fn) pn->right = child;
1128 else if (pn->left == fn) pn->left = child;
1129#if RT6_DEBUG >= 2
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001130 else
1131 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001132#endif
1133 if (child)
1134 child->parent = pn;
1135 nstate = FWS_R;
1136#ifdef CONFIG_IPV6_SUBTREES
1137 }
1138#endif
1139
1140 read_lock(&fib6_walker_lock);
1141 FOR_WALKERS(w) {
David S. Miller507c9b12011-12-03 17:50:45 -05001142 if (!child) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143 if (w->root == fn) {
1144 w->root = w->node = NULL;
1145 RT6_TRACE("W %p adjusted by delroot 1\n", w);
1146 } else if (w->node == fn) {
1147 RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
1148 w->node = pn;
1149 w->state = nstate;
1150 }
1151 } else {
1152 if (w->root == fn) {
1153 w->root = child;
1154 RT6_TRACE("W %p adjusted by delroot 2\n", w);
1155 }
1156 if (w->node == fn) {
1157 w->node = child;
1158 if (children&2) {
1159 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1160 w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
1161 } else {
1162 RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
1163 w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
1164 }
1165 }
1166 }
1167 }
1168 read_unlock(&fib6_walker_lock);
1169
1170 node_free(fn);
David S. Miller507c9b12011-12-03 17:50:45 -05001171 if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001172 return pn;
1173
1174 rt6_release(pn->leaf);
1175 pn->leaf = NULL;
1176 fn = pn;
1177 }
1178}
1179
1180static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
Thomas Graf86872cb2006-08-22 00:01:08 -07001181 struct nl_info *info)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001182{
1183 struct fib6_walker_t *w;
1184 struct rt6_info *rt = *rtp;
Benjamin Theryc5728722008-03-03 23:34:17 -08001185 struct net *net = info->nl_net;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001186
1187 RT6_TRACE("fib6_del_route\n");
1188
1189 /* Unlink it */
Changli Gaod8d1f302010-06-10 23:31:35 -07001190 *rtp = rt->dst.rt6_next;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001191 rt->rt6i_node = NULL;
Benjamin Theryc5728722008-03-03 23:34:17 -08001192 net->ipv6.rt6_stats->fib_rt_entries--;
1193 net->ipv6.rt6_stats->fib_discarded_routes++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194
David S. Millerf11e6652007-03-24 20:36:25 -07001195 /* Reset round-robin state, if necessary */
1196 if (fn->rr_ptr == rt)
1197 fn->rr_ptr = NULL;
1198
Linus Torvalds1da177e2005-04-16 15:20:36 -07001199 /* Adjust walkers */
1200 read_lock(&fib6_walker_lock);
1201 FOR_WALKERS(w) {
1202 if (w->state == FWS_C && w->leaf == rt) {
1203 RT6_TRACE("walker %p adjusted by delroute\n", w);
Changli Gaod8d1f302010-06-10 23:31:35 -07001204 w->leaf = rt->dst.rt6_next;
David S. Miller507c9b12011-12-03 17:50:45 -05001205 if (!w->leaf)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001206 w->state = FWS_U;
1207 }
1208 }
1209 read_unlock(&fib6_walker_lock);
1210
Changli Gaod8d1f302010-06-10 23:31:35 -07001211 rt->dst.rt6_next = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001212
Linus Torvalds1da177e2005-04-16 15:20:36 -07001213 /* If it was last route, expunge its radix tree node */
David S. Miller507c9b12011-12-03 17:50:45 -05001214 if (!fn->leaf) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215 fn->fn_flags &= ~RTN_RTINFO;
Benjamin Theryc5728722008-03-03 23:34:17 -08001216 net->ipv6.rt6_stats->fib_route_nodes--;
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001217 fn = fib6_repair_tree(net, fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218 }
1219
1220 if (atomic_read(&rt->rt6i_ref) != 1) {
1221 /* This route is used as dummy address holder in some split
1222 * nodes. It is not leaked, but it still holds other resources,
1223 * which must be released in time. So, scan ascendant nodes
1224 * and replace dummy references to this route with references
1225 * to still alive ones.
1226 */
1227 while (fn) {
David S. Miller507c9b12011-12-03 17:50:45 -05001228 if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) {
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001229 fn->leaf = fib6_find_prefix(net, fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001230 atomic_inc(&fn->leaf->rt6i_ref);
1231 rt6_release(rt);
1232 }
1233 fn = fn->parent;
1234 }
1235 /* No more references are possible at this point. */
Pavel Emelyanov2df96af2008-02-18 20:50:42 -08001236 BUG_ON(atomic_read(&rt->rt6i_ref) != 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237 }
1238
Thomas Graf86872cb2006-08-22 00:01:08 -07001239 inet6_rt_notify(RTM_DELROUTE, rt, info);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240 rt6_release(rt);
1241}
1242
Thomas Graf86872cb2006-08-22 00:01:08 -07001243int fib6_del(struct rt6_info *rt, struct nl_info *info)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001244{
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001245 struct net *net = info->nl_net;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001246 struct fib6_node *fn = rt->rt6i_node;
1247 struct rt6_info **rtp;
1248
1249#if RT6_DEBUG >= 2
Changli Gaod8d1f302010-06-10 23:31:35 -07001250 if (rt->dst.obsolete>0) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001251 WARN_ON(fn != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252 return -ENOENT;
1253 }
1254#endif
David S. Miller507c9b12011-12-03 17:50:45 -05001255 if (!fn || rt == net->ipv6.ip6_null_entry)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001256 return -ENOENT;
1257
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001258 WARN_ON(!(fn->fn_flags & RTN_RTINFO));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001259
David S. Miller507c9b12011-12-03 17:50:45 -05001260 if (!(rt->rt6i_flags & RTF_CACHE)) {
YOSHIFUJI Hideaki150730d2006-08-23 17:22:55 -07001261 struct fib6_node *pn = fn;
1262#ifdef CONFIG_IPV6_SUBTREES
1263 /* clones of this route might be in another subtree */
1264 if (rt->rt6i_src.plen) {
David S. Miller507c9b12011-12-03 17:50:45 -05001265 while (!(pn->fn_flags & RTN_ROOT))
YOSHIFUJI Hideaki150730d2006-08-23 17:22:55 -07001266 pn = pn->parent;
1267 pn = pn->parent;
1268 }
1269#endif
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001270 fib6_prune_clones(info->nl_net, pn, rt);
YOSHIFUJI Hideaki150730d2006-08-23 17:22:55 -07001271 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001272
1273 /*
1274 * Walk the leaf entries looking for ourself
1275 */
1276
Changli Gaod8d1f302010-06-10 23:31:35 -07001277 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001278 if (*rtp == rt) {
Thomas Graf86872cb2006-08-22 00:01:08 -07001279 fib6_del_route(fn, rtp, info);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001280 return 0;
1281 }
1282 }
1283 return -ENOENT;
1284}
1285
1286/*
1287 * Tree traversal function.
1288 *
1289 * Certainly, it is not interrupt safe.
1290 * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
1291 * It means, that we can modify tree during walking
1292 * and use this function for garbage collection, clone pruning,
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09001293 * cleaning tree when a device goes down etc. etc.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294 *
1295 * It guarantees that every node will be traversed,
1296 * and that it will be traversed only once.
1297 *
1298 * Callback function w->func may return:
1299 * 0 -> continue walking.
1300 * positive value -> walking is suspended (used by tree dumps,
1301 * and probably by gc, if it will be split to several slices)
1302 * negative value -> terminate walking.
1303 *
1304 * The function itself returns:
1305 * 0 -> walk is complete.
1306 * >0 -> walk is incomplete (i.e. suspended)
1307 * <0 -> walk is terminated by an error.
1308 */
1309
Adrian Bunk90d41122006-08-14 23:49:16 -07001310static int fib6_walk_continue(struct fib6_walker_t *w)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311{
1312 struct fib6_node *fn, *pn;
1313
1314 for (;;) {
1315 fn = w->node;
David S. Miller507c9b12011-12-03 17:50:45 -05001316 if (!fn)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001317 return 0;
1318
1319 if (w->prune && fn != w->root &&
David S. Miller507c9b12011-12-03 17:50:45 -05001320 fn->fn_flags & RTN_RTINFO && w->state < FWS_C) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001321 w->state = FWS_C;
1322 w->leaf = fn->leaf;
1323 }
1324 switch (w->state) {
1325#ifdef CONFIG_IPV6_SUBTREES
1326 case FWS_S:
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001327 if (FIB6_SUBTREE(fn)) {
1328 w->node = FIB6_SUBTREE(fn);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329 continue;
1330 }
1331 w->state = FWS_L;
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09001332#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001333 case FWS_L:
1334 if (fn->left) {
1335 w->node = fn->left;
1336 w->state = FWS_INIT;
1337 continue;
1338 }
1339 w->state = FWS_R;
1340 case FWS_R:
1341 if (fn->right) {
1342 w->node = fn->right;
1343 w->state = FWS_INIT;
1344 continue;
1345 }
1346 w->state = FWS_C;
1347 w->leaf = fn->leaf;
1348 case FWS_C:
David S. Miller507c9b12011-12-03 17:50:45 -05001349 if (w->leaf && fn->fn_flags & RTN_RTINFO) {
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001350 int err;
1351
1352 if (w->count < w->skip) {
1353 w->count++;
1354 continue;
1355 }
1356
1357 err = w->func(w);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001358 if (err)
1359 return err;
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001360
1361 w->count++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001362 continue;
1363 }
1364 w->state = FWS_U;
1365 case FWS_U:
1366 if (fn == w->root)
1367 return 0;
1368 pn = fn->parent;
1369 w->node = pn;
1370#ifdef CONFIG_IPV6_SUBTREES
YOSHIFUJI Hideaki7fc33162006-08-23 17:22:24 -07001371 if (FIB6_SUBTREE(pn) == fn) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001372 WARN_ON(!(fn->fn_flags & RTN_ROOT));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001373 w->state = FWS_L;
1374 continue;
1375 }
1376#endif
1377 if (pn->left == fn) {
1378 w->state = FWS_R;
1379 continue;
1380 }
1381 if (pn->right == fn) {
1382 w->state = FWS_C;
1383 w->leaf = w->node->leaf;
1384 continue;
1385 }
1386#if RT6_DEBUG >= 2
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001387 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001388#endif
1389 }
1390 }
1391}
1392
Adrian Bunk90d41122006-08-14 23:49:16 -07001393static int fib6_walk(struct fib6_walker_t *w)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001394{
1395 int res;
1396
1397 w->state = FWS_INIT;
1398 w->node = w->root;
1399
1400 fib6_walker_link(w);
1401 res = fib6_walk_continue(w);
1402 if (res <= 0)
1403 fib6_walker_unlink(w);
1404 return res;
1405}
1406
1407static int fib6_clean_node(struct fib6_walker_t *w)
1408{
1409 int res;
1410 struct rt6_info *rt;
Benjamin Thery0a8891a2007-10-08 20:39:36 -07001411 struct fib6_cleaner_t *c = container_of(w, struct fib6_cleaner_t, w);
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001412 struct nl_info info = {
1413 .nl_net = c->net,
1414 };
Linus Torvalds1da177e2005-04-16 15:20:36 -07001415
Changli Gaod8d1f302010-06-10 23:31:35 -07001416 for (rt = w->leaf; rt; rt = rt->dst.rt6_next) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001417 res = c->func(rt, c->arg);
1418 if (res < 0) {
1419 w->leaf = rt;
Denis V. Lunev528c4ce2007-12-13 09:45:12 -08001420 res = fib6_del(rt, &info);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421 if (res) {
1422#if RT6_DEBUG >= 2
1423 printk(KERN_DEBUG "fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt, rt->rt6i_node, res);
1424#endif
1425 continue;
1426 }
1427 return 0;
1428 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001429 WARN_ON(res != 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430 }
1431 w->leaf = rt;
1432 return 0;
1433}
1434
1435/*
1436 * Convenient frontend to tree walker.
YOSHIFUJI Hideaki1ab14572007-02-09 23:24:49 +09001437 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001438 * func is called on each route.
1439 * It may return -1 -> delete this route.
1440 * 0 -> continue walking
1441 *
1442 * prune==1 -> only immediate children of node (certainly,
1443 * ignoring pure split nodes) will be scanned.
1444 */
1445
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001446static void fib6_clean_tree(struct net *net, struct fib6_node *root,
Adrian Bunk8ce11e62006-08-07 21:50:48 -07001447 int (*func)(struct rt6_info *, void *arg),
1448 int prune, void *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001449{
1450 struct fib6_cleaner_t c;
1451
1452 c.w.root = root;
1453 c.w.func = fib6_clean_node;
1454 c.w.prune = prune;
Patrick McHardy2bec5a32010-02-08 05:19:03 +00001455 c.w.count = 0;
1456 c.w.skip = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001457 c.func = func;
1458 c.arg = arg;
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001459 c.net = net;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460
1461 fib6_walk(&c.w);
1462}
1463
Josh Hunt32b293a2011-12-28 13:23:07 +00001464void fib6_clean_all_ro(struct net *net, int (*func)(struct rt6_info *, void *arg),
1465 int prune, void *arg)
1466{
1467 struct fib6_table *table;
1468 struct hlist_node *node;
1469 struct hlist_head *head;
1470 unsigned int h;
1471
1472 rcu_read_lock();
1473 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
1474 head = &net->ipv6.fib_table_hash[h];
1475 hlist_for_each_entry_rcu(table, node, head, tb6_hlist) {
1476 read_lock_bh(&table->tb6_lock);
1477 fib6_clean_tree(net, &table->tb6_root,
1478 func, prune, arg);
1479 read_unlock_bh(&table->tb6_lock);
1480 }
1481 }
1482 rcu_read_unlock();
1483}
Daniel Lezcanof3db4852008-03-03 23:27:06 -08001484void fib6_clean_all(struct net *net, int (*func)(struct rt6_info *, void *arg),
Thomas Grafc71099a2006-08-04 23:20:06 -07001485 int prune, void *arg)
1486{
Thomas Grafc71099a2006-08-04 23:20:06 -07001487 struct fib6_table *table;
Patrick McHardy1b43af52006-08-10 23:11:17 -07001488 struct hlist_node *node;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001489 struct hlist_head *head;
Patrick McHardy1b43af52006-08-10 23:11:17 -07001490 unsigned int h;
Thomas Grafc71099a2006-08-04 23:20:06 -07001491
Patrick McHardy1b43af52006-08-10 23:11:17 -07001492 rcu_read_lock();
Neil Hormana33bc5c2009-07-30 18:52:15 -07001493 for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
Daniel Lezcanof3db4852008-03-03 23:27:06 -08001494 head = &net->ipv6.fib_table_hash[h];
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001495 hlist_for_each_entry_rcu(table, node, head, tb6_hlist) {
Thomas Grafc71099a2006-08-04 23:20:06 -07001496 write_lock_bh(&table->tb6_lock);
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001497 fib6_clean_tree(net, &table->tb6_root,
1498 func, prune, arg);
Thomas Grafc71099a2006-08-04 23:20:06 -07001499 write_unlock_bh(&table->tb6_lock);
1500 }
1501 }
Patrick McHardy1b43af52006-08-10 23:11:17 -07001502 rcu_read_unlock();
Thomas Grafc71099a2006-08-04 23:20:06 -07001503}
1504
Linus Torvalds1da177e2005-04-16 15:20:36 -07001505static int fib6_prune_clone(struct rt6_info *rt, void *arg)
1506{
1507 if (rt->rt6i_flags & RTF_CACHE) {
1508 RT6_TRACE("pruning clone %p\n", rt);
1509 return -1;
1510 }
1511
1512 return 0;
1513}
1514
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001515static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
1516 struct rt6_info *rt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001517{
Benjamin Theryec7d43c2008-03-03 23:31:57 -08001518 fib6_clean_tree(net, fn, fib6_prune_clone, 1, rt);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001519}
1520
1521/*
1522 * Garbage collection
1523 */
1524
1525static struct fib6_gc_args
1526{
1527 int timeout;
1528 int more;
1529} gc_args;
1530
1531static int fib6_age(struct rt6_info *rt, void *arg)
1532{
1533 unsigned long now = jiffies;
1534
1535 /*
1536 * check addrconf expiration here.
1537 * Routes are expired even if they are in use.
1538 *
1539 * Also age clones. Note, that clones are aged out
1540 * only if they are not in use now.
1541 */
1542
David S. Millerd1918542011-12-28 20:19:20 -05001543 if (rt->rt6i_flags & RTF_EXPIRES && rt->dst.expires) {
1544 if (time_after(now, rt->dst.expires)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001545 RT6_TRACE("expiring %p\n", rt);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001546 return -1;
1547 }
1548 gc_args.more++;
1549 } else if (rt->rt6i_flags & RTF_CACHE) {
Changli Gaod8d1f302010-06-10 23:31:35 -07001550 if (atomic_read(&rt->dst.__refcnt) == 0 &&
1551 time_after_eq(now, rt->dst.lastuse + gc_args.timeout)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001552 RT6_TRACE("aging clone %p\n", rt);
1553 return -1;
David S. Miller5339ab82012-01-27 15:14:01 -08001554 } else if (rt->rt6i_flags & RTF_GATEWAY) {
1555 struct neighbour *neigh;
1556 __u8 neigh_flags = 0;
1557
1558 neigh = dst_neigh_lookup(&rt->dst, &rt->rt6i_gateway);
1559 if (neigh) {
1560 neigh_flags = neigh->flags;
1561 neigh_release(neigh);
1562 }
1563 if (neigh_flags & NTF_ROUTER) {
1564 RT6_TRACE("purging route %p via non-router but gateway\n",
1565 rt);
1566 return -1;
1567 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001568 }
1569 gc_args.more++;
1570 }
1571
1572 return 0;
1573}
1574
1575static DEFINE_SPINLOCK(fib6_gc_lock);
1576
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001577void fib6_run_gc(unsigned long expires, struct net *net)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001578{
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001579 if (expires != ~0UL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001580 spin_lock_bh(&fib6_gc_lock);
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001581 gc_args.timeout = expires ? (int)expires :
1582 net->ipv6.sysctl.ip6_rt_gc_interval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583 } else {
Stephen Hemmingera76d7342008-07-22 14:34:35 -07001584 if (!spin_trylock_bh(&fib6_gc_lock)) {
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001585 mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001586 return;
1587 }
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001588 gc_args.timeout = net->ipv6.sysctl.ip6_rt_gc_interval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001589 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001590
Stephen Hemminger3d0f24a2008-07-22 14:35:50 -07001591 gc_args.more = icmp6_dst_gc();
Daniel Lezcanof3db4852008-03-03 23:27:06 -08001592
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001593 fib6_clean_all(net, fib6_age, 0, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001594
1595 if (gc_args.more)
Stephen Hemmingerc8a45222008-07-22 14:34:09 -07001596 mod_timer(&net->ipv6.ip6_fib_timer,
1597 round_jiffies(jiffies
1598 + net->ipv6.sysctl.ip6_rt_gc_interval));
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001599 else
1600 del_timer(&net->ipv6.ip6_fib_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001601 spin_unlock_bh(&fib6_gc_lock);
1602}
1603
Daniel Lezcano5b7c9312008-03-03 23:28:58 -08001604static void fib6_gc_timer_cb(unsigned long arg)
1605{
1606 fib6_run_gc(0, (struct net *)arg);
1607}
1608
Alexey Dobriyan2c8c1e72010-01-17 03:35:32 +00001609static int __net_init fib6_net_init(struct net *net)
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001610{
Eric Dumazet10da66f2010-10-13 08:22:03 +00001611 size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
1612
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001613 setup_timer(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, (unsigned long)net);
Daniel Lezcano63152fc2008-03-03 23:31:11 -08001614
Benjamin Theryc5728722008-03-03 23:34:17 -08001615 net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
1616 if (!net->ipv6.rt6_stats)
1617 goto out_timer;
1618
Eric Dumazet10da66f2010-10-13 08:22:03 +00001619 /* Avoid false sharing : Use at least a full cache line */
1620 size = max_t(size_t, size, L1_CACHE_BYTES);
1621
1622 net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001623 if (!net->ipv6.fib_table_hash)
Benjamin Theryc5728722008-03-03 23:34:17 -08001624 goto out_rt6_stats;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001625
1626 net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
1627 GFP_KERNEL);
1628 if (!net->ipv6.fib6_main_tbl)
1629 goto out_fib_table_hash;
1630
1631 net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001632 net->ipv6.fib6_main_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001633 net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
1634 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1635
1636#ifdef CONFIG_IPV6_MULTIPLE_TABLES
1637 net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
1638 GFP_KERNEL);
1639 if (!net->ipv6.fib6_local_tbl)
1640 goto out_fib6_main_tbl;
1641 net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001642 net->ipv6.fib6_local_tbl->tb6_root.leaf = net->ipv6.ip6_null_entry;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001643 net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
1644 RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
1645#endif
1646 fib6_tables_init(net);
1647
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001648 return 0;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001649
1650#ifdef CONFIG_IPV6_MULTIPLE_TABLES
1651out_fib6_main_tbl:
1652 kfree(net->ipv6.fib6_main_tbl);
1653#endif
1654out_fib_table_hash:
1655 kfree(net->ipv6.fib_table_hash);
Benjamin Theryc5728722008-03-03 23:34:17 -08001656out_rt6_stats:
1657 kfree(net->ipv6.rt6_stats);
Daniel Lezcano63152fc2008-03-03 23:31:11 -08001658out_timer:
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001659 return -ENOMEM;
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001660 }
1661
1662static void fib6_net_exit(struct net *net)
1663{
Daniel Lezcano8ed67782008-03-04 13:48:30 -08001664 rt6_ifdown(net, NULL);
Stephen Hemminger417f28b2008-07-22 14:33:45 -07001665 del_timer_sync(&net->ipv6.ip6_fib_timer);
1666
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001667#ifdef CONFIG_IPV6_MULTIPLE_TABLES
1668 kfree(net->ipv6.fib6_local_tbl);
1669#endif
1670 kfree(net->ipv6.fib6_main_tbl);
1671 kfree(net->ipv6.fib_table_hash);
Benjamin Theryc5728722008-03-03 23:34:17 -08001672 kfree(net->ipv6.rt6_stats);
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001673}
1674
1675static struct pernet_operations fib6_net_ops = {
1676 .init = fib6_net_init,
1677 .exit = fib6_net_exit,
1678};
1679
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001680int __init fib6_init(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001681{
Daniel Lezcanoe0b85592008-03-03 23:24:31 -08001682 int ret = -ENOMEM;
Daniel Lezcano63152fc2008-03-03 23:31:11 -08001683
Linus Torvalds1da177e2005-04-16 15:20:36 -07001684 fib6_node_kmem = kmem_cache_create("fib6_nodes",
1685 sizeof(struct fib6_node),
Daniel Lezcanof845ab62007-12-07 00:45:16 -08001686 0, SLAB_HWCACHE_ALIGN,
Paul Mundt20c2df82007-07-20 10:11:58 +09001687 NULL);
Daniel Lezcanof845ab62007-12-07 00:45:16 -08001688 if (!fib6_node_kmem)
Daniel Lezcanoe0b85592008-03-03 23:24:31 -08001689 goto out;
1690
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001691 ret = register_pernet_subsys(&fib6_net_ops);
1692 if (ret)
Benjamin Theryc5728722008-03-03 23:34:17 -08001693 goto out_kmem_cache_create;
Daniel Lezcanoe0b85592008-03-03 23:24:31 -08001694
Greg Rosec7ac8672011-06-10 01:27:09 +00001695 ret = __rtnl_register(PF_INET6, RTM_GETROUTE, NULL, inet6_dump_fib,
1696 NULL);
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001697 if (ret)
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001698 goto out_unregister_subsys;
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001699out:
1700 return ret;
1701
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001702out_unregister_subsys:
1703 unregister_pernet_subsys(&fib6_net_ops);
Daniel Lezcanod63bddb2007-12-07 00:40:34 -08001704out_kmem_cache_create:
1705 kmem_cache_destroy(fib6_node_kmem);
1706 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001707}
1708
1709void fib6_gc_cleanup(void)
1710{
Daniel Lezcano58f09b72008-03-03 23:25:27 -08001711 unregister_pernet_subsys(&fib6_net_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001712 kmem_cache_destroy(fib6_node_kmem);
1713}