Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * INET An implementation of the TCP/IP protocol suite for the LINUX | |
3 | * operating system. INET is implemented using the BSD Socket | |
4 | * interface as the means of communication with the user level. | |
5 | * | |
6 | * IPv4 FIB: lookup engine and maintenance routines. | |
7 | * | |
1da177e4 LT |
8 | * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> |
9 | * | |
10 | * This program is free software; you can redistribute it and/or | |
11 | * modify it under the terms of the GNU General Public License | |
12 | * as published by the Free Software Foundation; either version | |
13 | * 2 of the License, or (at your option) any later version. | |
14 | */ | |
15 | ||
1da177e4 LT |
16 | #include <asm/uaccess.h> |
17 | #include <asm/system.h> | |
18 | #include <linux/bitops.h> | |
19 | #include <linux/types.h> | |
20 | #include <linux/kernel.h> | |
1da177e4 LT |
21 | #include <linux/mm.h> |
22 | #include <linux/string.h> | |
23 | #include <linux/socket.h> | |
24 | #include <linux/sockios.h> | |
25 | #include <linux/errno.h> | |
26 | #include <linux/in.h> | |
27 | #include <linux/inet.h> | |
14c85021 | 28 | #include <linux/inetdevice.h> |
1da177e4 LT |
29 | #include <linux/netdevice.h> |
30 | #include <linux/if_arp.h> | |
31 | #include <linux/proc_fs.h> | |
32 | #include <linux/skbuff.h> | |
33 | #include <linux/netlink.h> | |
34 | #include <linux/init.h> | |
35 | ||
457c4cbc | 36 | #include <net/net_namespace.h> |
1da177e4 LT |
37 | #include <net/ip.h> |
38 | #include <net/protocol.h> | |
39 | #include <net/route.h> | |
40 | #include <net/tcp.h> | |
41 | #include <net/sock.h> | |
42 | #include <net/ip_fib.h> | |
43 | ||
44 | #include "fib_lookup.h" | |
45 | ||
e18b890b CL |
46 | static struct kmem_cache *fn_hash_kmem __read_mostly; |
47 | static struct kmem_cache *fn_alias_kmem __read_mostly; | |
1da177e4 LT |
48 | |
49 | struct fib_node { | |
50 | struct hlist_node fn_hash; | |
51 | struct list_head fn_alias; | |
b6e80c6c | 52 | __be32 fn_key; |
a6501e08 | 53 | struct fib_alias fn_embedded_alias; |
1da177e4 LT |
54 | }; |
55 | ||
56 | struct fn_zone { | |
57 | struct fn_zone *fz_next; /* Next not empty zone */ | |
58 | struct hlist_head *fz_hash; /* Hash table pointer */ | |
59 | int fz_nent; /* Number of entries */ | |
60 | ||
61 | int fz_divisor; /* Hash divisor */ | |
62 | u32 fz_hashmask; /* (fz_divisor - 1) */ | |
63 | #define FZ_HASHMASK(fz) ((fz)->fz_hashmask) | |
64 | ||
65 | int fz_order; /* Zone order */ | |
b6e80c6c | 66 | __be32 fz_mask; |
1da177e4 LT |
67 | #define FZ_MASK(fz) ((fz)->fz_mask) |
68 | }; | |
69 | ||
70 | /* NOTE. On fast computers evaluation of fz_hashmask and fz_mask | |
71 | * can be cheaper than memory lookup, so that FZ_* macros are used. | |
72 | */ | |
73 | ||
74 | struct fn_hash { | |
75 | struct fn_zone *fn_zones[33]; | |
76 | struct fn_zone *fn_zone_list; | |
77 | }; | |
78 | ||
b6e80c6c | 79 | static inline u32 fn_hash(__be32 key, struct fn_zone *fz) |
1da177e4 LT |
80 | { |
81 | u32 h = ntohl(key)>>(32 - fz->fz_order); | |
82 | h ^= (h>>20); | |
83 | h ^= (h>>10); | |
84 | h ^= (h>>5); | |
85 | h &= FZ_HASHMASK(fz); | |
86 | return h; | |
87 | } | |
88 | ||
b6e80c6c | 89 | static inline __be32 fz_key(__be32 dst, struct fn_zone *fz) |
1da177e4 LT |
90 | { |
91 | return dst & FZ_MASK(fz); | |
92 | } | |
93 | ||
94 | static DEFINE_RWLOCK(fib_hash_lock); | |
95 | static unsigned int fib_hash_genid; | |
96 | ||
97 | #define FZ_MAX_DIVISOR ((PAGE_SIZE<<MAX_ORDER) / sizeof(struct hlist_head)) | |
98 | ||
99 | static struct hlist_head *fz_hash_alloc(int divisor) | |
100 | { | |
101 | unsigned long size = divisor * sizeof(struct hlist_head); | |
102 | ||
103 | if (size <= PAGE_SIZE) { | |
3015a347 | 104 | return kzalloc(size, GFP_KERNEL); |
1da177e4 LT |
105 | } else { |
106 | return (struct hlist_head *) | |
3015a347 | 107 | __get_free_pages(GFP_KERNEL | __GFP_ZERO, get_order(size)); |
1da177e4 LT |
108 | } |
109 | } | |
110 | ||
111 | /* The fib hash lock must be held when this is called. */ | |
112 | static inline void fn_rebuild_zone(struct fn_zone *fz, | |
113 | struct hlist_head *old_ht, | |
114 | int old_divisor) | |
115 | { | |
116 | int i; | |
117 | ||
118 | for (i = 0; i < old_divisor; i++) { | |
119 | struct hlist_node *node, *n; | |
120 | struct fib_node *f; | |
121 | ||
122 | hlist_for_each_entry_safe(f, node, n, &old_ht[i], fn_hash) { | |
123 | struct hlist_head *new_head; | |
124 | ||
125 | hlist_del(&f->fn_hash); | |
126 | ||
127 | new_head = &fz->fz_hash[fn_hash(f->fn_key, fz)]; | |
128 | hlist_add_head(&f->fn_hash, new_head); | |
129 | } | |
130 | } | |
131 | } | |
132 | ||
133 | static void fz_hash_free(struct hlist_head *hash, int divisor) | |
134 | { | |
135 | unsigned long size = divisor * sizeof(struct hlist_head); | |
136 | ||
137 | if (size <= PAGE_SIZE) | |
138 | kfree(hash); | |
139 | else | |
140 | free_pages((unsigned long)hash, get_order(size)); | |
141 | } | |
142 | ||
143 | static void fn_rehash_zone(struct fn_zone *fz) | |
144 | { | |
145 | struct hlist_head *ht, *old_ht; | |
146 | int old_divisor, new_divisor; | |
147 | u32 new_hashmask; | |
e905a9ed | 148 | |
1da177e4 LT |
149 | old_divisor = fz->fz_divisor; |
150 | ||
151 | switch (old_divisor) { | |
152 | case 16: | |
153 | new_divisor = 256; | |
154 | break; | |
155 | case 256: | |
156 | new_divisor = 1024; | |
157 | break; | |
158 | default: | |
159 | if ((old_divisor << 1) > FZ_MAX_DIVISOR) { | |
160 | printk(KERN_CRIT "route.c: bad divisor %d!\n", old_divisor); | |
161 | return; | |
162 | } | |
163 | new_divisor = (old_divisor << 1); | |
164 | break; | |
165 | } | |
166 | ||
167 | new_hashmask = (new_divisor - 1); | |
168 | ||
169 | #if RT_CACHE_DEBUG >= 2 | |
a6db9010 SH |
170 | printk(KERN_DEBUG "fn_rehash_zone: hash for zone %d grows from %d\n", |
171 | fz->fz_order, old_divisor); | |
1da177e4 LT |
172 | #endif |
173 | ||
174 | ht = fz_hash_alloc(new_divisor); | |
175 | ||
176 | if (ht) { | |
1da177e4 LT |
177 | write_lock_bh(&fib_hash_lock); |
178 | old_ht = fz->fz_hash; | |
179 | fz->fz_hash = ht; | |
180 | fz->fz_hashmask = new_hashmask; | |
181 | fz->fz_divisor = new_divisor; | |
182 | fn_rebuild_zone(fz, old_ht, old_divisor); | |
183 | fib_hash_genid++; | |
184 | write_unlock_bh(&fib_hash_lock); | |
185 | ||
186 | fz_hash_free(old_ht, old_divisor); | |
187 | } | |
188 | } | |
189 | ||
190 | static inline void fn_free_node(struct fib_node * f) | |
191 | { | |
192 | kmem_cache_free(fn_hash_kmem, f); | |
193 | } | |
194 | ||
a6501e08 | 195 | static inline void fn_free_alias(struct fib_alias *fa, struct fib_node *f) |
1da177e4 LT |
196 | { |
197 | fib_release_info(fa->fa_info); | |
a6501e08 ED |
198 | if (fa == &f->fn_embedded_alias) |
199 | fa->fa_info = NULL; | |
200 | else | |
201 | kmem_cache_free(fn_alias_kmem, fa); | |
1da177e4 LT |
202 | } |
203 | ||
204 | static struct fn_zone * | |
205 | fn_new_zone(struct fn_hash *table, int z) | |
206 | { | |
207 | int i; | |
0da974f4 | 208 | struct fn_zone *fz = kzalloc(sizeof(struct fn_zone), GFP_KERNEL); |
1da177e4 LT |
209 | if (!fz) |
210 | return NULL; | |
211 | ||
1da177e4 LT |
212 | if (z) { |
213 | fz->fz_divisor = 16; | |
214 | } else { | |
215 | fz->fz_divisor = 1; | |
216 | } | |
217 | fz->fz_hashmask = (fz->fz_divisor - 1); | |
218 | fz->fz_hash = fz_hash_alloc(fz->fz_divisor); | |
219 | if (!fz->fz_hash) { | |
220 | kfree(fz); | |
221 | return NULL; | |
222 | } | |
1da177e4 LT |
223 | fz->fz_order = z; |
224 | fz->fz_mask = inet_make_mask(z); | |
225 | ||
226 | /* Find the first not empty zone with more specific mask */ | |
227 | for (i=z+1; i<=32; i++) | |
228 | if (table->fn_zones[i]) | |
229 | break; | |
230 | write_lock_bh(&fib_hash_lock); | |
231 | if (i>32) { | |
232 | /* No more specific masks, we are the first. */ | |
233 | fz->fz_next = table->fn_zone_list; | |
234 | table->fn_zone_list = fz; | |
235 | } else { | |
236 | fz->fz_next = table->fn_zones[i]->fz_next; | |
237 | table->fn_zones[i]->fz_next = fz; | |
238 | } | |
239 | table->fn_zones[z] = fz; | |
240 | fib_hash_genid++; | |
241 | write_unlock_bh(&fib_hash_lock); | |
242 | return fz; | |
243 | } | |
244 | ||
16c6cf8b SH |
245 | int fib_table_lookup(struct fib_table *tb, |
246 | const struct flowi *flp, struct fib_result *res) | |
1da177e4 LT |
247 | { |
248 | int err; | |
249 | struct fn_zone *fz; | |
6ed2533e | 250 | struct fn_hash *t = (struct fn_hash *)tb->tb_data; |
1da177e4 LT |
251 | |
252 | read_lock(&fib_hash_lock); | |
253 | for (fz = t->fn_zone_list; fz; fz = fz->fz_next) { | |
254 | struct hlist_head *head; | |
255 | struct hlist_node *node; | |
256 | struct fib_node *f; | |
b6e80c6c | 257 | __be32 k = fz_key(flp->fl4_dst, fz); |
1da177e4 LT |
258 | |
259 | head = &fz->fz_hash[fn_hash(k, fz)]; | |
260 | hlist_for_each_entry(f, node, head, fn_hash) { | |
261 | if (f->fn_key != k) | |
262 | continue; | |
263 | ||
264 | err = fib_semantic_match(&f->fn_alias, | |
265 | flp, res, | |
1da177e4 LT |
266 | fz->fz_order); |
267 | if (err <= 0) | |
268 | goto out; | |
269 | } | |
270 | } | |
271 | err = 1; | |
272 | out: | |
273 | read_unlock(&fib_hash_lock); | |
274 | return err; | |
275 | } | |
276 | ||
16c6cf8b SH |
277 | void fib_table_select_default(struct fib_table *tb, |
278 | const struct flowi *flp, struct fib_result *res) | |
1da177e4 LT |
279 | { |
280 | int order, last_idx; | |
281 | struct hlist_node *node; | |
282 | struct fib_node *f; | |
283 | struct fib_info *fi = NULL; | |
284 | struct fib_info *last_resort; | |
6ed2533e | 285 | struct fn_hash *t = (struct fn_hash *)tb->tb_data; |
1da177e4 LT |
286 | struct fn_zone *fz = t->fn_zones[0]; |
287 | ||
288 | if (fz == NULL) | |
289 | return; | |
290 | ||
291 | last_idx = -1; | |
292 | last_resort = NULL; | |
293 | order = -1; | |
294 | ||
295 | read_lock(&fib_hash_lock); | |
296 | hlist_for_each_entry(f, node, &fz->fz_hash[0], fn_hash) { | |
297 | struct fib_alias *fa; | |
298 | ||
299 | list_for_each_entry(fa, &f->fn_alias, fa_list) { | |
300 | struct fib_info *next_fi = fa->fa_info; | |
301 | ||
302 | if (fa->fa_scope != res->scope || | |
303 | fa->fa_type != RTN_UNICAST) | |
304 | continue; | |
305 | ||
306 | if (next_fi->fib_priority > res->fi->fib_priority) | |
307 | break; | |
308 | if (!next_fi->fib_nh[0].nh_gw || | |
309 | next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK) | |
310 | continue; | |
311 | fa->fa_state |= FA_S_ACCESSED; | |
312 | ||
313 | if (fi == NULL) { | |
314 | if (next_fi != res->fi) | |
315 | break; | |
316 | } else if (!fib_detect_death(fi, order, &last_resort, | |
971b893e | 317 | &last_idx, tb->tb_default)) { |
a2bbe682 | 318 | fib_result_assign(res, fi); |
971b893e | 319 | tb->tb_default = order; |
1da177e4 LT |
320 | goto out; |
321 | } | |
322 | fi = next_fi; | |
323 | order++; | |
324 | } | |
325 | } | |
326 | ||
327 | if (order <= 0 || fi == NULL) { | |
971b893e | 328 | tb->tb_default = -1; |
1da177e4 LT |
329 | goto out; |
330 | } | |
331 | ||
971b893e DL |
332 | if (!fib_detect_death(fi, order, &last_resort, &last_idx, |
333 | tb->tb_default)) { | |
a2bbe682 | 334 | fib_result_assign(res, fi); |
971b893e | 335 | tb->tb_default = order; |
1da177e4 LT |
336 | goto out; |
337 | } | |
338 | ||
a2bbe682 DL |
339 | if (last_idx >= 0) |
340 | fib_result_assign(res, last_resort); | |
971b893e | 341 | tb->tb_default = last_idx; |
1da177e4 LT |
342 | out: |
343 | read_unlock(&fib_hash_lock); | |
344 | } | |
345 | ||
346 | /* Insert node F to FZ. */ | |
347 | static inline void fib_insert_node(struct fn_zone *fz, struct fib_node *f) | |
348 | { | |
349 | struct hlist_head *head = &fz->fz_hash[fn_hash(f->fn_key, fz)]; | |
350 | ||
351 | hlist_add_head(&f->fn_hash, head); | |
352 | } | |
353 | ||
354 | /* Return the node in FZ matching KEY. */ | |
b6e80c6c | 355 | static struct fib_node *fib_find_node(struct fn_zone *fz, __be32 key) |
1da177e4 LT |
356 | { |
357 | struct hlist_head *head = &fz->fz_hash[fn_hash(key, fz)]; | |
358 | struct hlist_node *node; | |
359 | struct fib_node *f; | |
360 | ||
361 | hlist_for_each_entry(f, node, head, fn_hash) { | |
362 | if (f->fn_key == key) | |
363 | return f; | |
364 | } | |
365 | ||
366 | return NULL; | |
367 | } | |
368 | ||
16c6cf8b | 369 | int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) |
1da177e4 LT |
370 | { |
371 | struct fn_hash *table = (struct fn_hash *) tb->tb_data; | |
94cb1503 AB |
372 | struct fib_node *new_f = NULL; |
373 | struct fib_node *f; | |
1da177e4 LT |
374 | struct fib_alias *fa, *new_fa; |
375 | struct fn_zone *fz; | |
376 | struct fib_info *fi; | |
4e902c57 | 377 | u8 tos = cfg->fc_tos; |
b6e80c6c | 378 | __be32 key; |
1da177e4 LT |
379 | int err; |
380 | ||
4e902c57 | 381 | if (cfg->fc_dst_len > 32) |
1da177e4 | 382 | return -EINVAL; |
4e902c57 TG |
383 | |
384 | fz = table->fn_zones[cfg->fc_dst_len]; | |
385 | if (!fz && !(fz = fn_new_zone(table, cfg->fc_dst_len))) | |
1da177e4 LT |
386 | return -ENOBUFS; |
387 | ||
388 | key = 0; | |
4e902c57 TG |
389 | if (cfg->fc_dst) { |
390 | if (cfg->fc_dst & ~FZ_MASK(fz)) | |
1da177e4 | 391 | return -EINVAL; |
4e902c57 | 392 | key = fz_key(cfg->fc_dst, fz); |
1da177e4 LT |
393 | } |
394 | ||
4e902c57 TG |
395 | fi = fib_create_info(cfg); |
396 | if (IS_ERR(fi)) | |
397 | return PTR_ERR(fi); | |
1da177e4 LT |
398 | |
399 | if (fz->fz_nent > (fz->fz_divisor<<1) && | |
400 | fz->fz_divisor < FZ_MAX_DIVISOR && | |
4e902c57 TG |
401 | (cfg->fc_dst_len == 32 || |
402 | (1 << cfg->fc_dst_len) > fz->fz_divisor)) | |
1da177e4 LT |
403 | fn_rehash_zone(fz); |
404 | ||
405 | f = fib_find_node(fz, key); | |
406 | ||
407 | if (!f) | |
408 | fa = NULL; | |
409 | else | |
410 | fa = fib_find_alias(&f->fn_alias, tos, fi->fib_priority); | |
411 | ||
412 | /* Now fa, if non-NULL, points to the first fib alias | |
413 | * with the same keys [prefix,tos,priority], if such key already | |
414 | * exists or to the node before which we will insert new one. | |
415 | * | |
416 | * If fa is NULL, we will need to allocate a new one and | |
417 | * insert to the head of f. | |
418 | * | |
419 | * If f is NULL, no fib node matched the destination key | |
420 | * and we need to allocate a new one of those as well. | |
421 | */ | |
422 | ||
423 | if (fa && fa->fa_tos == tos && | |
424 | fa->fa_info->fib_priority == fi->fib_priority) { | |
c18865f3 | 425 | struct fib_alias *fa_first, *fa_match; |
1da177e4 LT |
426 | |
427 | err = -EEXIST; | |
4e902c57 | 428 | if (cfg->fc_nlflags & NLM_F_EXCL) |
1da177e4 LT |
429 | goto out; |
430 | ||
c18865f3 JA |
431 | /* We have 2 goals: |
432 | * 1. Find exact match for type, scope, fib_info to avoid | |
433 | * duplicate routes | |
434 | * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it | |
435 | */ | |
436 | fa_match = NULL; | |
437 | fa_first = fa; | |
438 | fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list); | |
439 | list_for_each_entry_continue(fa, &f->fn_alias, fa_list) { | |
440 | if (fa->fa_tos != tos) | |
441 | break; | |
442 | if (fa->fa_info->fib_priority != fi->fib_priority) | |
443 | break; | |
444 | if (fa->fa_type == cfg->fc_type && | |
445 | fa->fa_scope == cfg->fc_scope && | |
446 | fa->fa_info == fi) { | |
447 | fa_match = fa; | |
448 | break; | |
449 | } | |
450 | } | |
451 | ||
4e902c57 | 452 | if (cfg->fc_nlflags & NLM_F_REPLACE) { |
1da177e4 LT |
453 | struct fib_info *fi_drop; |
454 | u8 state; | |
455 | ||
c18865f3 JA |
456 | fa = fa_first; |
457 | if (fa_match) { | |
458 | if (fa == fa_match) | |
459 | err = 0; | |
bd566e75 | 460 | goto out; |
c18865f3 | 461 | } |
1da177e4 LT |
462 | write_lock_bh(&fib_hash_lock); |
463 | fi_drop = fa->fa_info; | |
464 | fa->fa_info = fi; | |
4e902c57 TG |
465 | fa->fa_type = cfg->fc_type; |
466 | fa->fa_scope = cfg->fc_scope; | |
1da177e4 LT |
467 | state = fa->fa_state; |
468 | fa->fa_state &= ~FA_S_ACCESSED; | |
469 | fib_hash_genid++; | |
470 | write_unlock_bh(&fib_hash_lock); | |
471 | ||
472 | fib_release_info(fi_drop); | |
473 | if (state & FA_S_ACCESSED) | |
76e6ebfb | 474 | rt_cache_flush(cfg->fc_nlinfo.nl_net, -1); |
b8f55831 MK |
475 | rtmsg_fib(RTM_NEWROUTE, key, fa, cfg->fc_dst_len, tb->tb_id, |
476 | &cfg->fc_nlinfo, NLM_F_REPLACE); | |
1da177e4 LT |
477 | return 0; |
478 | } | |
479 | ||
480 | /* Error if we find a perfect match which | |
481 | * uses the same scope, type, and nexthop | |
482 | * information. | |
483 | */ | |
c18865f3 JA |
484 | if (fa_match) |
485 | goto out; | |
486 | ||
4e902c57 | 487 | if (!(cfg->fc_nlflags & NLM_F_APPEND)) |
c18865f3 | 488 | fa = fa_first; |
1da177e4 LT |
489 | } |
490 | ||
491 | err = -ENOENT; | |
4e902c57 | 492 | if (!(cfg->fc_nlflags & NLM_F_CREATE)) |
1da177e4 LT |
493 | goto out; |
494 | ||
495 | err = -ENOBUFS; | |
1da177e4 | 496 | |
1da177e4 | 497 | if (!f) { |
a6501e08 | 498 | new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL); |
1da177e4 | 499 | if (new_f == NULL) |
a6501e08 | 500 | goto out; |
1da177e4 LT |
501 | |
502 | INIT_HLIST_NODE(&new_f->fn_hash); | |
503 | INIT_LIST_HEAD(&new_f->fn_alias); | |
504 | new_f->fn_key = key; | |
505 | f = new_f; | |
506 | } | |
507 | ||
a6501e08 ED |
508 | new_fa = &f->fn_embedded_alias; |
509 | if (new_fa->fa_info != NULL) { | |
510 | new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL); | |
511 | if (new_fa == NULL) | |
94cb1503 | 512 | goto out; |
a6501e08 | 513 | } |
1da177e4 LT |
514 | new_fa->fa_info = fi; |
515 | new_fa->fa_tos = tos; | |
4e902c57 TG |
516 | new_fa->fa_type = cfg->fc_type; |
517 | new_fa->fa_scope = cfg->fc_scope; | |
1da177e4 LT |
518 | new_fa->fa_state = 0; |
519 | ||
520 | /* | |
521 | * Insert new entry to the list. | |
522 | */ | |
523 | ||
524 | write_lock_bh(&fib_hash_lock); | |
525 | if (new_f) | |
526 | fib_insert_node(fz, new_f); | |
527 | list_add_tail(&new_fa->fa_list, | |
528 | (fa ? &fa->fa_list : &f->fn_alias)); | |
529 | fib_hash_genid++; | |
530 | write_unlock_bh(&fib_hash_lock); | |
531 | ||
532 | if (new_f) | |
533 | fz->fz_nent++; | |
76e6ebfb | 534 | rt_cache_flush(cfg->fc_nlinfo.nl_net, -1); |
1da177e4 | 535 | |
4e902c57 | 536 | rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id, |
b8f55831 | 537 | &cfg->fc_nlinfo, 0); |
1da177e4 LT |
538 | return 0; |
539 | ||
1da177e4 | 540 | out: |
94cb1503 AB |
541 | if (new_f) |
542 | kmem_cache_free(fn_hash_kmem, new_f); | |
1da177e4 LT |
543 | fib_release_info(fi); |
544 | return err; | |
545 | } | |
546 | ||
16c6cf8b | 547 | int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) |
1da177e4 | 548 | { |
6ed2533e | 549 | struct fn_hash *table = (struct fn_hash *)tb->tb_data; |
1da177e4 LT |
550 | struct fib_node *f; |
551 | struct fib_alias *fa, *fa_to_delete; | |
1da177e4 | 552 | struct fn_zone *fz; |
b6e80c6c | 553 | __be32 key; |
1da177e4 | 554 | |
4e902c57 | 555 | if (cfg->fc_dst_len > 32) |
1da177e4 | 556 | return -EINVAL; |
4e902c57 TG |
557 | |
558 | if ((fz = table->fn_zones[cfg->fc_dst_len]) == NULL) | |
1da177e4 LT |
559 | return -ESRCH; |
560 | ||
561 | key = 0; | |
4e902c57 TG |
562 | if (cfg->fc_dst) { |
563 | if (cfg->fc_dst & ~FZ_MASK(fz)) | |
1da177e4 | 564 | return -EINVAL; |
4e902c57 | 565 | key = fz_key(cfg->fc_dst, fz); |
1da177e4 LT |
566 | } |
567 | ||
568 | f = fib_find_node(fz, key); | |
569 | ||
570 | if (!f) | |
571 | fa = NULL; | |
572 | else | |
4e902c57 | 573 | fa = fib_find_alias(&f->fn_alias, cfg->fc_tos, 0); |
1da177e4 LT |
574 | if (!fa) |
575 | return -ESRCH; | |
576 | ||
577 | fa_to_delete = NULL; | |
578 | fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list); | |
579 | list_for_each_entry_continue(fa, &f->fn_alias, fa_list) { | |
580 | struct fib_info *fi = fa->fa_info; | |
581 | ||
4e902c57 | 582 | if (fa->fa_tos != cfg->fc_tos) |
1da177e4 LT |
583 | break; |
584 | ||
4e902c57 TG |
585 | if ((!cfg->fc_type || |
586 | fa->fa_type == cfg->fc_type) && | |
587 | (cfg->fc_scope == RT_SCOPE_NOWHERE || | |
588 | fa->fa_scope == cfg->fc_scope) && | |
589 | (!cfg->fc_protocol || | |
590 | fi->fib_protocol == cfg->fc_protocol) && | |
591 | fib_nh_match(cfg, fi) == 0) { | |
1da177e4 LT |
592 | fa_to_delete = fa; |
593 | break; | |
594 | } | |
595 | } | |
596 | ||
597 | if (fa_to_delete) { | |
598 | int kill_fn; | |
599 | ||
600 | fa = fa_to_delete; | |
4e902c57 | 601 | rtmsg_fib(RTM_DELROUTE, key, fa, cfg->fc_dst_len, |
b8f55831 | 602 | tb->tb_id, &cfg->fc_nlinfo, 0); |
1da177e4 LT |
603 | |
604 | kill_fn = 0; | |
605 | write_lock_bh(&fib_hash_lock); | |
606 | list_del(&fa->fa_list); | |
607 | if (list_empty(&f->fn_alias)) { | |
608 | hlist_del(&f->fn_hash); | |
609 | kill_fn = 1; | |
610 | } | |
611 | fib_hash_genid++; | |
612 | write_unlock_bh(&fib_hash_lock); | |
613 | ||
614 | if (fa->fa_state & FA_S_ACCESSED) | |
76e6ebfb | 615 | rt_cache_flush(cfg->fc_nlinfo.nl_net, -1); |
a6501e08 | 616 | fn_free_alias(fa, f); |
1da177e4 LT |
617 | if (kill_fn) { |
618 | fn_free_node(f); | |
619 | fz->fz_nent--; | |
620 | } | |
621 | ||
622 | return 0; | |
623 | } | |
624 | return -ESRCH; | |
625 | } | |
626 | ||
627 | static int fn_flush_list(struct fn_zone *fz, int idx) | |
628 | { | |
629 | struct hlist_head *head = &fz->fz_hash[idx]; | |
630 | struct hlist_node *node, *n; | |
631 | struct fib_node *f; | |
632 | int found = 0; | |
633 | ||
634 | hlist_for_each_entry_safe(f, node, n, head, fn_hash) { | |
635 | struct fib_alias *fa, *fa_node; | |
636 | int kill_f; | |
637 | ||
638 | kill_f = 0; | |
639 | list_for_each_entry_safe(fa, fa_node, &f->fn_alias, fa_list) { | |
640 | struct fib_info *fi = fa->fa_info; | |
641 | ||
642 | if (fi && (fi->fib_flags&RTNH_F_DEAD)) { | |
643 | write_lock_bh(&fib_hash_lock); | |
644 | list_del(&fa->fa_list); | |
645 | if (list_empty(&f->fn_alias)) { | |
646 | hlist_del(&f->fn_hash); | |
647 | kill_f = 1; | |
648 | } | |
649 | fib_hash_genid++; | |
650 | write_unlock_bh(&fib_hash_lock); | |
651 | ||
a6501e08 | 652 | fn_free_alias(fa, f); |
1da177e4 LT |
653 | found++; |
654 | } | |
655 | } | |
656 | if (kill_f) { | |
657 | fn_free_node(f); | |
658 | fz->fz_nent--; | |
659 | } | |
660 | } | |
661 | return found; | |
662 | } | |
663 | ||
16c6cf8b | 664 | int fib_table_flush(struct fib_table *tb) |
1da177e4 LT |
665 | { |
666 | struct fn_hash *table = (struct fn_hash *) tb->tb_data; | |
667 | struct fn_zone *fz; | |
668 | int found = 0; | |
669 | ||
670 | for (fz = table->fn_zone_list; fz; fz = fz->fz_next) { | |
671 | int i; | |
672 | ||
673 | for (i = fz->fz_divisor - 1; i >= 0; i--) | |
674 | found += fn_flush_list(fz, i); | |
675 | } | |
676 | return found; | |
677 | } | |
678 | ||
679 | ||
680 | static inline int | |
681 | fn_hash_dump_bucket(struct sk_buff *skb, struct netlink_callback *cb, | |
682 | struct fib_table *tb, | |
683 | struct fn_zone *fz, | |
684 | struct hlist_head *head) | |
685 | { | |
686 | struct hlist_node *node; | |
687 | struct fib_node *f; | |
688 | int i, s_i; | |
689 | ||
1af5a8c4 | 690 | s_i = cb->args[4]; |
1da177e4 LT |
691 | i = 0; |
692 | hlist_for_each_entry(f, node, head, fn_hash) { | |
693 | struct fib_alias *fa; | |
694 | ||
695 | list_for_each_entry(fa, &f->fn_alias, fa_list) { | |
696 | if (i < s_i) | |
697 | goto next; | |
698 | ||
699 | if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid, | |
700 | cb->nlh->nlmsg_seq, | |
701 | RTM_NEWROUTE, | |
702 | tb->tb_id, | |
703 | fa->fa_type, | |
704 | fa->fa_scope, | |
be403ea1 | 705 | f->fn_key, |
1da177e4 LT |
706 | fz->fz_order, |
707 | fa->fa_tos, | |
b6544c0b JHS |
708 | fa->fa_info, |
709 | NLM_F_MULTI) < 0) { | |
1af5a8c4 | 710 | cb->args[4] = i; |
1da177e4 LT |
711 | return -1; |
712 | } | |
713 | next: | |
714 | i++; | |
715 | } | |
716 | } | |
1af5a8c4 | 717 | cb->args[4] = i; |
1da177e4 LT |
718 | return skb->len; |
719 | } | |
720 | ||
721 | static inline int | |
722 | fn_hash_dump_zone(struct sk_buff *skb, struct netlink_callback *cb, | |
723 | struct fib_table *tb, | |
724 | struct fn_zone *fz) | |
725 | { | |
726 | int h, s_h; | |
727 | ||
8d3f099a ED |
728 | if (fz->fz_hash == NULL) |
729 | return skb->len; | |
1af5a8c4 | 730 | s_h = cb->args[3]; |
8d3f099a ED |
731 | for (h = s_h; h < fz->fz_divisor; h++) { |
732 | if (hlist_empty(&fz->fz_hash[h])) | |
1da177e4 | 733 | continue; |
8d3f099a | 734 | if (fn_hash_dump_bucket(skb, cb, tb, fz, &fz->fz_hash[h]) < 0) { |
1af5a8c4 | 735 | cb->args[3] = h; |
1da177e4 LT |
736 | return -1; |
737 | } | |
8d3f099a ED |
738 | memset(&cb->args[4], 0, |
739 | sizeof(cb->args) - 4*sizeof(cb->args[0])); | |
1da177e4 | 740 | } |
1af5a8c4 | 741 | cb->args[3] = h; |
1da177e4 LT |
742 | return skb->len; |
743 | } | |
744 | ||
16c6cf8b SH |
745 | int fib_table_dump(struct fib_table *tb, struct sk_buff *skb, |
746 | struct netlink_callback *cb) | |
1da177e4 LT |
747 | { |
748 | int m, s_m; | |
749 | struct fn_zone *fz; | |
6ed2533e | 750 | struct fn_hash *table = (struct fn_hash *)tb->tb_data; |
1da177e4 | 751 | |
1af5a8c4 | 752 | s_m = cb->args[2]; |
1da177e4 LT |
753 | read_lock(&fib_hash_lock); |
754 | for (fz = table->fn_zone_list, m=0; fz; fz = fz->fz_next, m++) { | |
755 | if (m < s_m) continue; | |
1da177e4 | 756 | if (fn_hash_dump_zone(skb, cb, tb, fz) < 0) { |
1af5a8c4 | 757 | cb->args[2] = m; |
1da177e4 LT |
758 | read_unlock(&fib_hash_lock); |
759 | return -1; | |
760 | } | |
8d3f099a ED |
761 | memset(&cb->args[3], 0, |
762 | sizeof(cb->args) - 3*sizeof(cb->args[0])); | |
1da177e4 LT |
763 | } |
764 | read_unlock(&fib_hash_lock); | |
1af5a8c4 | 765 | cb->args[2] = m; |
1da177e4 LT |
766 | return skb->len; |
767 | } | |
768 | ||
7f9b8052 | 769 | void __init fib_hash_init(void) |
1da177e4 | 770 | { |
7f9b8052 | 771 | fn_hash_kmem = kmem_cache_create("ip_fib_hash", sizeof(struct fib_node), |
a6501e08 | 772 | 0, SLAB_PANIC, NULL); |
7f9b8052 SH |
773 | |
774 | fn_alias_kmem = kmem_cache_create("ip_fib_alias", sizeof(struct fib_alias), | |
a6501e08 | 775 | 0, SLAB_PANIC, NULL); |
7f9b8052 SH |
776 | |
777 | } | |
1da177e4 | 778 | |
7f9b8052 SH |
779 | struct fib_table *fib_hash_table(u32 id) |
780 | { | |
781 | struct fib_table *tb; | |
1da177e4 LT |
782 | |
783 | tb = kmalloc(sizeof(struct fib_table) + sizeof(struct fn_hash), | |
784 | GFP_KERNEL); | |
785 | if (tb == NULL) | |
786 | return NULL; | |
787 | ||
788 | tb->tb_id = id; | |
971b893e | 789 | tb->tb_default = -1; |
16c6cf8b | 790 | |
1da177e4 LT |
791 | memset(tb->tb_data, 0, sizeof(struct fn_hash)); |
792 | return tb; | |
793 | } | |
794 | ||
795 | /* ------------------------------------------------------------------------ */ | |
796 | #ifdef CONFIG_PROC_FS | |
797 | ||
798 | struct fib_iter_state { | |
6e04d01d | 799 | struct seq_net_private p; |
1da177e4 LT |
800 | struct fn_zone *zone; |
801 | int bucket; | |
802 | struct hlist_head *hash_head; | |
803 | struct fib_node *fn; | |
804 | struct fib_alias *fa; | |
805 | loff_t pos; | |
806 | unsigned int genid; | |
807 | int valid; | |
808 | }; | |
809 | ||
810 | static struct fib_alias *fib_get_first(struct seq_file *seq) | |
811 | { | |
812 | struct fib_iter_state *iter = seq->private; | |
6e04d01d DL |
813 | struct fib_table *main_table; |
814 | struct fn_hash *table; | |
815 | ||
1218854a | 816 | main_table = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN); |
6e04d01d | 817 | table = (struct fn_hash *)main_table->tb_data; |
1da177e4 LT |
818 | |
819 | iter->bucket = 0; | |
820 | iter->hash_head = NULL; | |
821 | iter->fn = NULL; | |
822 | iter->fa = NULL; | |
823 | iter->pos = 0; | |
824 | iter->genid = fib_hash_genid; | |
825 | iter->valid = 1; | |
826 | ||
827 | for (iter->zone = table->fn_zone_list; iter->zone; | |
828 | iter->zone = iter->zone->fz_next) { | |
829 | int maxslot; | |
830 | ||
831 | if (!iter->zone->fz_nent) | |
832 | continue; | |
833 | ||
834 | iter->hash_head = iter->zone->fz_hash; | |
835 | maxslot = iter->zone->fz_divisor; | |
836 | ||
837 | for (iter->bucket = 0; iter->bucket < maxslot; | |
838 | ++iter->bucket, ++iter->hash_head) { | |
839 | struct hlist_node *node; | |
840 | struct fib_node *fn; | |
841 | ||
6ed2533e | 842 | hlist_for_each_entry(fn, node, iter->hash_head, fn_hash) { |
1da177e4 LT |
843 | struct fib_alias *fa; |
844 | ||
6ed2533e | 845 | list_for_each_entry(fa, &fn->fn_alias, fa_list) { |
1da177e4 LT |
846 | iter->fn = fn; |
847 | iter->fa = fa; | |
848 | goto out; | |
849 | } | |
850 | } | |
851 | } | |
852 | } | |
853 | out: | |
854 | return iter->fa; | |
855 | } | |
856 | ||
857 | static struct fib_alias *fib_get_next(struct seq_file *seq) | |
858 | { | |
859 | struct fib_iter_state *iter = seq->private; | |
860 | struct fib_node *fn; | |
861 | struct fib_alias *fa; | |
862 | ||
863 | /* Advance FA, if any. */ | |
864 | fn = iter->fn; | |
865 | fa = iter->fa; | |
866 | if (fa) { | |
867 | BUG_ON(!fn); | |
868 | list_for_each_entry_continue(fa, &fn->fn_alias, fa_list) { | |
869 | iter->fa = fa; | |
870 | goto out; | |
871 | } | |
872 | } | |
873 | ||
874 | fa = iter->fa = NULL; | |
875 | ||
876 | /* Advance FN. */ | |
877 | if (fn) { | |
878 | struct hlist_node *node = &fn->fn_hash; | |
879 | hlist_for_each_entry_continue(fn, node, fn_hash) { | |
880 | iter->fn = fn; | |
881 | ||
882 | list_for_each_entry(fa, &fn->fn_alias, fa_list) { | |
883 | iter->fa = fa; | |
884 | goto out; | |
885 | } | |
886 | } | |
887 | } | |
888 | ||
889 | fn = iter->fn = NULL; | |
890 | ||
891 | /* Advance hash chain. */ | |
892 | if (!iter->zone) | |
893 | goto out; | |
894 | ||
895 | for (;;) { | |
896 | struct hlist_node *node; | |
897 | int maxslot; | |
898 | ||
899 | maxslot = iter->zone->fz_divisor; | |
900 | ||
901 | while (++iter->bucket < maxslot) { | |
902 | iter->hash_head++; | |
903 | ||
904 | hlist_for_each_entry(fn, node, iter->hash_head, fn_hash) { | |
905 | list_for_each_entry(fa, &fn->fn_alias, fa_list) { | |
906 | iter->fn = fn; | |
907 | iter->fa = fa; | |
908 | goto out; | |
909 | } | |
910 | } | |
911 | } | |
912 | ||
913 | iter->zone = iter->zone->fz_next; | |
914 | ||
915 | if (!iter->zone) | |
916 | goto out; | |
e905a9ed | 917 | |
1da177e4 LT |
918 | iter->bucket = 0; |
919 | iter->hash_head = iter->zone->fz_hash; | |
920 | ||
921 | hlist_for_each_entry(fn, node, iter->hash_head, fn_hash) { | |
922 | list_for_each_entry(fa, &fn->fn_alias, fa_list) { | |
923 | iter->fn = fn; | |
924 | iter->fa = fa; | |
925 | goto out; | |
926 | } | |
927 | } | |
928 | } | |
929 | out: | |
930 | iter->pos++; | |
931 | return fa; | |
932 | } | |
933 | ||
934 | static struct fib_alias *fib_get_idx(struct seq_file *seq, loff_t pos) | |
935 | { | |
936 | struct fib_iter_state *iter = seq->private; | |
937 | struct fib_alias *fa; | |
e905a9ed | 938 | |
1da177e4 LT |
939 | if (iter->valid && pos >= iter->pos && iter->genid == fib_hash_genid) { |
940 | fa = iter->fa; | |
941 | pos -= iter->pos; | |
942 | } else | |
943 | fa = fib_get_first(seq); | |
944 | ||
945 | if (fa) | |
946 | while (pos && (fa = fib_get_next(seq))) | |
947 | --pos; | |
948 | return pos ? NULL : fa; | |
949 | } | |
950 | ||
951 | static void *fib_seq_start(struct seq_file *seq, loff_t *pos) | |
9a429c49 | 952 | __acquires(fib_hash_lock) |
1da177e4 LT |
953 | { |
954 | void *v = NULL; | |
955 | ||
956 | read_lock(&fib_hash_lock); | |
1218854a | 957 | if (fib_get_table(seq_file_net(seq), RT_TABLE_MAIN)) |
1da177e4 LT |
958 | v = *pos ? fib_get_idx(seq, *pos - 1) : SEQ_START_TOKEN; |
959 | return v; | |
960 | } | |
961 | ||
962 | static void *fib_seq_next(struct seq_file *seq, void *v, loff_t *pos) | |
963 | { | |
964 | ++*pos; | |
965 | return v == SEQ_START_TOKEN ? fib_get_first(seq) : fib_get_next(seq); | |
966 | } | |
967 | ||
968 | static void fib_seq_stop(struct seq_file *seq, void *v) | |
9a429c49 | 969 | __releases(fib_hash_lock) |
1da177e4 LT |
970 | { |
971 | read_unlock(&fib_hash_lock); | |
972 | } | |
973 | ||
b6e80c6c | 974 | static unsigned fib_flag_trans(int type, __be32 mask, struct fib_info *fi) |
1da177e4 | 975 | { |
9b5b5cff | 976 | static const unsigned type2flags[RTN_MAX + 1] = { |
1da177e4 LT |
977 | [7] = RTF_REJECT, [8] = RTF_REJECT, |
978 | }; | |
979 | unsigned flags = type2flags[type]; | |
980 | ||
981 | if (fi && fi->fib_nh->nh_gw) | |
982 | flags |= RTF_GATEWAY; | |
b6e80c6c | 983 | if (mask == htonl(0xFFFFFFFF)) |
1da177e4 LT |
984 | flags |= RTF_HOST; |
985 | flags |= RTF_UP; | |
986 | return flags; | |
987 | } | |
988 | ||
e905a9ed | 989 | /* |
1da177e4 LT |
990 | * This outputs /proc/net/route. |
991 | * | |
992 | * It always works in backward compatibility mode. | |
993 | * The format of the file is not supposed to be changed. | |
994 | */ | |
995 | static int fib_seq_show(struct seq_file *seq, void *v) | |
996 | { | |
997 | struct fib_iter_state *iter; | |
5e659e4c | 998 | int len; |
b6e80c6c | 999 | __be32 prefix, mask; |
1da177e4 LT |
1000 | unsigned flags; |
1001 | struct fib_node *f; | |
1002 | struct fib_alias *fa; | |
1003 | struct fib_info *fi; | |
1004 | ||
1005 | if (v == SEQ_START_TOKEN) { | |
1006 | seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway " | |
1007 | "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU" | |
1008 | "\tWindow\tIRTT"); | |
1009 | goto out; | |
1010 | } | |
1011 | ||
1012 | iter = seq->private; | |
1013 | f = iter->fn; | |
1014 | fa = iter->fa; | |
1015 | fi = fa->fa_info; | |
1016 | prefix = f->fn_key; | |
1017 | mask = FZ_MASK(iter->zone); | |
1018 | flags = fib_flag_trans(fa->fa_type, mask, fi); | |
1019 | if (fi) | |
5e659e4c PE |
1020 | seq_printf(seq, |
1021 | "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u%n", | |
1da177e4 LT |
1022 | fi->fib_dev ? fi->fib_dev->name : "*", prefix, |
1023 | fi->fib_nh->nh_gw, flags, 0, 0, fi->fib_priority, | |
1024 | mask, (fi->fib_advmss ? fi->fib_advmss + 40 : 0), | |
1025 | fi->fib_window, | |
5e659e4c | 1026 | fi->fib_rtt >> 3, &len); |
1da177e4 | 1027 | else |
5e659e4c PE |
1028 | seq_printf(seq, |
1029 | "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u%n", | |
1030 | prefix, 0, flags, 0, 0, 0, mask, 0, 0, 0, &len); | |
1031 | ||
1032 | seq_printf(seq, "%*s\n", 127 - len, ""); | |
1da177e4 LT |
1033 | out: |
1034 | return 0; | |
1035 | } | |
1036 | ||
f690808e | 1037 | static const struct seq_operations fib_seq_ops = { |
1da177e4 LT |
1038 | .start = fib_seq_start, |
1039 | .next = fib_seq_next, | |
1040 | .stop = fib_seq_stop, | |
1041 | .show = fib_seq_show, | |
1042 | }; | |
1043 | ||
1044 | static int fib_seq_open(struct inode *inode, struct file *file) | |
1045 | { | |
6e04d01d DL |
1046 | return seq_open_net(inode, file, &fib_seq_ops, |
1047 | sizeof(struct fib_iter_state)); | |
1da177e4 LT |
1048 | } |
1049 | ||
9a32144e | 1050 | static const struct file_operations fib_seq_fops = { |
1da177e4 LT |
1051 | .owner = THIS_MODULE, |
1052 | .open = fib_seq_open, | |
1053 | .read = seq_read, | |
1054 | .llseek = seq_lseek, | |
6e04d01d | 1055 | .release = seq_release_net, |
1da177e4 LT |
1056 | }; |
1057 | ||
61a02653 | 1058 | int __net_init fib_proc_init(struct net *net) |
1da177e4 | 1059 | { |
61a02653 | 1060 | if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_seq_fops)) |
1da177e4 LT |
1061 | return -ENOMEM; |
1062 | return 0; | |
1063 | } | |
1064 | ||
61a02653 | 1065 | void __net_exit fib_proc_exit(struct net *net) |
1da177e4 | 1066 | { |
61a02653 | 1067 | proc_net_remove(net, "route"); |
1da177e4 LT |
1068 | } |
1069 | #endif /* CONFIG_PROC_FS */ |