blob: 8d8c2915e064f98d16d1409c2524f2277107185b [file] [log] [blame]
Robert Olsson19baf832005-06-21 12:43:18 -07001/*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
6 *
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
9 *
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090010 * Jens Laas <jens.laas@data.slu.se> Swedish University of
Robert Olsson19baf832005-06-21 12:43:18 -070011 * Agricultural Sciences.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090012 *
Robert Olsson19baf832005-06-21 12:43:18 -070013 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
14 *
15 * This work is based on the LPC-trie which is originally descibed in:
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090016 *
Robert Olsson19baf832005-06-21 12:43:18 -070017 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
20 *
21 *
22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
24 *
25 * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
26 *
27 *
28 * Code from fib_hash has been reused which includes the following header:
29 *
30 *
31 * INET An implementation of the TCP/IP protocol suite for the LINUX
32 * operating system. INET is implemented using the BSD Socket
33 * interface as the means of communication with the user level.
34 *
35 * IPv4 FIB: lookup engine and maintenance routines.
36 *
37 *
38 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
39 *
40 * This program is free software; you can redistribute it and/or
41 * modify it under the terms of the GNU General Public License
42 * as published by the Free Software Foundation; either version
43 * 2 of the License, or (at your option) any later version.
Robert Olssonfd966252005-12-22 11:25:10 -080044 *
45 * Substantial contributions to this work comes from:
46 *
47 * David S. Miller, <davem@davemloft.net>
48 * Stephen Hemminger <shemminger@osdl.org>
49 * Paul E. McKenney <paulmck@us.ibm.com>
50 * Patrick McHardy <kaber@trash.net>
Robert Olsson19baf832005-06-21 12:43:18 -070051 */
52
Robert Olsson05eee482007-03-19 16:27:37 -070053#define VERSION "0.408"
Robert Olsson19baf832005-06-21 12:43:18 -070054
Robert Olsson19baf832005-06-21 12:43:18 -070055#include <asm/uaccess.h>
56#include <asm/system.h>
Jiri Slaby1977f032007-10-18 23:40:25 -070057#include <linux/bitops.h>
Robert Olsson19baf832005-06-21 12:43:18 -070058#include <linux/types.h>
59#include <linux/kernel.h>
Robert Olsson19baf832005-06-21 12:43:18 -070060#include <linux/mm.h>
61#include <linux/string.h>
62#include <linux/socket.h>
63#include <linux/sockios.h>
64#include <linux/errno.h>
65#include <linux/in.h>
66#include <linux/inet.h>
Stephen Hemmingercd8787a2006-01-03 14:38:34 -080067#include <linux/inetdevice.h>
Robert Olsson19baf832005-06-21 12:43:18 -070068#include <linux/netdevice.h>
69#include <linux/if_arp.h>
70#include <linux/proc_fs.h>
Robert Olsson2373ce12005-08-25 13:01:29 -070071#include <linux/rcupdate.h>
Robert Olsson19baf832005-06-21 12:43:18 -070072#include <linux/skbuff.h>
73#include <linux/netlink.h>
74#include <linux/init.h>
75#include <linux/list.h>
Eric W. Biederman457c4cb2007-09-12 12:01:34 +020076#include <net/net_namespace.h>
Robert Olsson19baf832005-06-21 12:43:18 -070077#include <net/ip.h>
78#include <net/protocol.h>
79#include <net/route.h>
80#include <net/tcp.h>
81#include <net/sock.h>
82#include <net/ip_fib.h>
83#include "fib_lookup.h"
84
85#undef CONFIG_IP_FIB_TRIE_STATS
Robert Olsson06ef9212006-03-20 21:35:01 -080086#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070087
Robert Olsson19baf832005-06-21 12:43:18 -070088#define KEYLENGTH (8*sizeof(t_key))
Robert Olsson19baf832005-06-21 12:43:18 -070089
Robert Olsson19baf832005-06-21 12:43:18 -070090typedef unsigned int t_key;
91
92#define T_TNODE 0
93#define T_LEAF 1
94#define NODE_TYPE_MASK 0x1UL
Robert Olsson2373ce12005-08-25 13:01:29 -070095#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
96
Olof Johansson91b9a272005-08-09 20:24:39 -070097#define IS_TNODE(n) (!(n->parent & T_LEAF))
98#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -070099
100struct node {
Olof Johansson91b9a272005-08-09 20:24:39 -0700101 t_key key;
102 unsigned long parent;
Robert Olsson19baf832005-06-21 12:43:18 -0700103};
104
105struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700106 t_key key;
107 unsigned long parent;
Robert Olsson19baf832005-06-21 12:43:18 -0700108 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700109 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700110};
111
112struct leaf_info {
113 struct hlist_node hlist;
Robert Olsson2373ce12005-08-25 13:01:29 -0700114 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700115 int plen;
116 struct list_head falh;
117};
118
119struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700120 t_key key;
121 unsigned long parent;
122 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
123 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
124 unsigned short full_children; /* KEYLENGTH bits needed */
125 unsigned short empty_children; /* KEYLENGTH bits needed */
Robert Olsson2373ce12005-08-25 13:01:29 -0700126 struct rcu_head rcu;
Olof Johansson91b9a272005-08-09 20:24:39 -0700127 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700128};
129
130#ifdef CONFIG_IP_FIB_TRIE_STATS
131struct trie_use_stats {
132 unsigned int gets;
133 unsigned int backtrack;
134 unsigned int semantic_match_passed;
135 unsigned int semantic_match_miss;
136 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700137 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700138};
139#endif
140
141struct trie_stat {
142 unsigned int totdepth;
143 unsigned int maxdepth;
144 unsigned int tnodes;
145 unsigned int leaves;
146 unsigned int nullpointers;
Robert Olsson06ef9212006-03-20 21:35:01 -0800147 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700148};
Robert Olsson19baf832005-06-21 12:43:18 -0700149
150struct trie {
Olof Johansson91b9a272005-08-09 20:24:39 -0700151 struct node *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700152#ifdef CONFIG_IP_FIB_TRIE_STATS
153 struct trie_use_stats stats;
154#endif
Olof Johansson91b9a272005-08-09 20:24:39 -0700155 int size;
Robert Olsson19baf832005-06-21 12:43:18 -0700156 unsigned int revision;
157};
158
Robert Olsson19baf832005-06-21 12:43:18 -0700159static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
160static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700161static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700162static struct tnode *inflate(struct trie *t, struct tnode *tn);
163static struct tnode *halve(struct trie *t, struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700164static void tnode_free(struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700165
Christoph Lametere18b8902006-12-06 20:33:20 -0800166static struct kmem_cache *fn_alias_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700167static struct trie *trie_local = NULL, *trie_main = NULL;
168
Stephen Hemminger06801912007-08-10 15:22:13 -0700169static inline struct tnode *node_parent(struct node *node)
170{
171 struct tnode *ret;
172
173 ret = (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
174 return rcu_dereference(ret);
175}
176
177static inline void node_set_parent(struct node *node, struct tnode *ptr)
178{
179 rcu_assign_pointer(node->parent,
180 (unsigned long)ptr | NODE_TYPE(node));
181}
Robert Olsson2373ce12005-08-25 13:01:29 -0700182
183/* rcu_read_lock needs to be hold by caller from readside */
184
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700185static inline struct node *tnode_get_child(struct tnode *tn, int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700186{
Olof Johansson91b9a272005-08-09 20:24:39 -0700187 BUG_ON(i >= 1 << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700188
Robert Olsson2373ce12005-08-25 13:01:29 -0700189 return rcu_dereference(tn->child[i]);
Robert Olsson19baf832005-06-21 12:43:18 -0700190}
191
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700192static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700193{
Olof Johansson91b9a272005-08-09 20:24:39 -0700194 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700195}
196
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700197static inline t_key mask_pfx(t_key k, unsigned short l)
198{
199 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
200}
201
Robert Olsson19baf832005-06-21 12:43:18 -0700202static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
203{
Olof Johansson91b9a272005-08-09 20:24:39 -0700204 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700205 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700206 else
Robert Olsson19baf832005-06-21 12:43:18 -0700207 return 0;
208}
209
210static inline int tkey_equals(t_key a, t_key b)
211{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700212 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700213}
214
215static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
216{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700217 if (bits == 0 || offset >= KEYLENGTH)
218 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700219 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
220 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700221}
Robert Olsson19baf832005-06-21 12:43:18 -0700222
223static inline int tkey_mismatch(t_key a, int offset, t_key b)
224{
225 t_key diff = a ^ b;
226 int i = offset;
227
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700228 if (!diff)
229 return 0;
230 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700231 i++;
232 return i;
233}
234
Robert Olsson19baf832005-06-21 12:43:18 -0700235/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900236 To understand this stuff, an understanding of keys and all their bits is
237 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700238 all of the bits in that key are significant.
239
240 Consider a node 'n' and its parent 'tp'.
241
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900242 If n is a leaf, every bit in its key is significant. Its presence is
243 necessitated by path compression, since during a tree traversal (when
244 searching for a leaf - unless we are doing an insertion) we will completely
245 ignore all skipped bits we encounter. Thus we need to verify, at the end of
246 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700247 correct key path.
248
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900249 Note that we can never "miss" the correct key in the tree if present by
250 following the wrong path. Path compression ensures that segments of the key
251 that are the same for all keys with a given prefix are skipped, but the
252 skipped part *is* identical for each node in the subtrie below the skipped
253 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700254 call to tkey_sub_equals() in trie_insert().
255
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900256 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700257 have many different meanings.
258
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900259 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700260 _________________________________________________________________
261 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
262 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900263 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700264
265 _________________________________________________________________
266 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
267 -----------------------------------------------------------------
268 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
269
270 tp->pos = 7
271 tp->bits = 3
272 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700273 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700274
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900275 First, let's just ignore the bits that come before the parent tp, that is
276 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700277 not use them for anything.
278
279 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900280 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700281 'n' among tp's children.
282
283 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
284 for the node n.
285
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900286 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700287 of the bits are really not needed or indeed known in n->key.
288
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900289 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700290 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900291
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700292
Robert Olsson19baf832005-06-21 12:43:18 -0700293 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
294 at this point.
295
296*/
297
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700298static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700299{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700300 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700301}
302
303static int halve_threshold = 25;
304static int inflate_threshold = 50;
Robert Olsson965ffea2007-03-19 16:29:58 -0700305static int halve_threshold_root = 8;
306static int inflate_threshold_root = 15;
Robert Olsson19baf832005-06-21 12:43:18 -0700307
Robert Olsson2373ce12005-08-25 13:01:29 -0700308
309static void __alias_free_mem(struct rcu_head *head)
310{
311 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
312 kmem_cache_free(fn_alias_kmem, fa);
313}
314
315static inline void alias_free_mem_rcu(struct fib_alias *fa)
316{
317 call_rcu(&fa->rcu, __alias_free_mem);
318}
319
320static void __leaf_free_rcu(struct rcu_head *head)
321{
322 kfree(container_of(head, struct leaf, rcu));
323}
324
Robert Olsson2373ce12005-08-25 13:01:29 -0700325static void __leaf_info_free_rcu(struct rcu_head *head)
326{
327 kfree(container_of(head, struct leaf_info, rcu));
328}
329
330static inline void free_leaf_info(struct leaf_info *leaf)
331{
332 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
333}
334
335static struct tnode *tnode_alloc(unsigned int size)
336{
337 struct page *pages;
338
339 if (size <= PAGE_SIZE)
340 return kcalloc(size, 1, GFP_KERNEL);
341
342 pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
343 if (!pages)
344 return NULL;
345
346 return page_address(pages);
347}
348
349static void __tnode_free_rcu(struct rcu_head *head)
350{
351 struct tnode *tn = container_of(head, struct tnode, rcu);
352 unsigned int size = sizeof(struct tnode) +
353 (1 << tn->bits) * sizeof(struct node *);
354
355 if (size <= PAGE_SIZE)
356 kfree(tn);
357 else
358 free_pages((unsigned long)tn, get_order(size));
359}
360
361static inline void tnode_free(struct tnode *tn)
362{
Stephen Hemminger132adf52007-03-08 20:44:43 -0800363 if (IS_LEAF(tn)) {
Robert Olsson550e29b2006-04-04 12:53:35 -0700364 struct leaf *l = (struct leaf *) tn;
365 call_rcu_bh(&l->rcu, __leaf_free_rcu);
Stephen Hemminger132adf52007-03-08 20:44:43 -0800366 } else
Robert Olsson550e29b2006-04-04 12:53:35 -0700367 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700368}
369
Robert Olsson19baf832005-06-21 12:43:18 -0700370static struct leaf *leaf_new(void)
371{
372 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700373 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700374 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700375 INIT_HLIST_HEAD(&l->list);
376 }
377 return l;
378}
379
380static struct leaf_info *leaf_info_new(int plen)
381{
382 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700383 if (li) {
384 li->plen = plen;
385 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700386 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700387 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700388}
389
Robert Olsson19baf832005-06-21 12:43:18 -0700390static struct tnode* tnode_new(t_key key, int pos, int bits)
391{
392 int nchildren = 1<<bits;
393 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700394 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700395
Olof Johansson91b9a272005-08-09 20:24:39 -0700396 if (tn) {
Robert Olsson19baf832005-06-21 12:43:18 -0700397 memset(tn, 0, sz);
Robert Olsson2373ce12005-08-25 13:01:29 -0700398 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700399 tn->pos = pos;
400 tn->bits = bits;
401 tn->key = key;
402 tn->full_children = 0;
403 tn->empty_children = 1<<bits;
404 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700405
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700406 pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
407 (unsigned int) (sizeof(struct node) * 1<<bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700408 return tn;
409}
410
Robert Olsson19baf832005-06-21 12:43:18 -0700411/*
412 * Check whether a tnode 'n' is "full", i.e. it is an internal node
413 * and no bits are skipped. See discussion in dyntree paper p. 6
414 */
415
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700416static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700417{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700418 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700419 return 0;
420
421 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
422}
423
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700424static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700425{
426 tnode_put_child_reorg(tn, i, n, -1);
427}
428
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700429 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700430 * Add a child at position i overwriting the old value.
431 * Update the value of full_children and empty_children.
432 */
433
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700434static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700435{
Robert Olsson2373ce12005-08-25 13:01:29 -0700436 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700437 int isfull;
438
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700439 BUG_ON(i >= 1<<tn->bits);
440
Robert Olsson19baf832005-06-21 12:43:18 -0700441
442 /* update emptyChildren */
443 if (n == NULL && chi != NULL)
444 tn->empty_children++;
445 else if (n != NULL && chi == NULL)
446 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700447
Robert Olsson19baf832005-06-21 12:43:18 -0700448 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700449 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700450 wasfull = tnode_full(tn, chi);
451
452 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700453 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700454 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700455 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700456 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700457
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700458 if (n)
Stephen Hemminger06801912007-08-10 15:22:13 -0700459 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700460
Robert Olsson2373ce12005-08-25 13:01:29 -0700461 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700462}
463
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700464static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700465{
466 int i;
Robert Olsson2f368952005-07-05 15:02:40 -0700467 int err = 0;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700468 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700469 int inflate_threshold_use;
470 int halve_threshold_use;
Robert Olsson05eee482007-03-19 16:27:37 -0700471 int max_resize;
Robert Olsson19baf832005-06-21 12:43:18 -0700472
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900473 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700474 return NULL;
475
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700476 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
477 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700478
479 /* No children */
480 if (tn->empty_children == tnode_child_length(tn)) {
481 tnode_free(tn);
482 return NULL;
483 }
484 /* One child */
485 if (tn->empty_children == tnode_child_length(tn) - 1)
486 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700487 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700488
Olof Johansson91b9a272005-08-09 20:24:39 -0700489 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700490 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700491 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700492
493 /* compress one level */
Stephen Hemminger06801912007-08-10 15:22:13 -0700494 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700495 tnode_free(tn);
496 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700497 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700498 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700499 * Double as long as the resulting node has a number of
500 * nonempty nodes that are above the threshold.
501 */
502
503 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700504 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
505 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700506 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700507 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700508 * children in the *doubled* node is at least 'high'."
509 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700510 * 'high' in this instance is the variable 'inflate_threshold'. It
511 * is expressed as a percentage, so we multiply it with
512 * tnode_child_length() and instead of multiplying by 2 (since the
513 * child array will be doubled by inflate()) and multiplying
514 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700515 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700516 *
517 * The left-hand side may look a bit weird: tnode_child_length(tn)
518 * - tn->empty_children is of course the number of non-null children
519 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700520 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700521 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700522 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700523 *
Robert Olsson19baf832005-06-21 12:43:18 -0700524 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700525 *
Robert Olsson19baf832005-06-21 12:43:18 -0700526 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700527 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700528 * tn->full_children;
529 *
530 * new_child_length = tnode_child_length(tn) * 2;
531 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700532 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700533 * new_child_length;
534 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700535 *
536 * ...and so on, tho it would mess up the while () loop.
537 *
Robert Olsson19baf832005-06-21 12:43:18 -0700538 * anyway,
539 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
540 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700541 *
Robert Olsson19baf832005-06-21 12:43:18 -0700542 * avoid a division:
543 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
544 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700545 *
Robert Olsson19baf832005-06-21 12:43:18 -0700546 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700547 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700548 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700549 *
Robert Olsson19baf832005-06-21 12:43:18 -0700550 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700551 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700552 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700553 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700554 *
Robert Olsson19baf832005-06-21 12:43:18 -0700555 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700556 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700557 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700558 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700559 *
Robert Olsson19baf832005-06-21 12:43:18 -0700560 */
561
562 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700563
Robert Olssone6308be2005-10-04 13:01:58 -0700564 /* Keep root node larger */
565
Stephen Hemminger132adf52007-03-08 20:44:43 -0800566 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700567 inflate_threshold_use = inflate_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900568 else
Robert Olssone6308be2005-10-04 13:01:58 -0700569 inflate_threshold_use = inflate_threshold;
570
Robert Olsson2f368952005-07-05 15:02:40 -0700571 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700572 max_resize = 10;
573 while ((tn->full_children > 0 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700574 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
Robert Olssone6308be2005-10-04 13:01:58 -0700575 inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700576
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700577 old_tn = tn;
578 tn = inflate(t, tn);
579 if (IS_ERR(tn)) {
580 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700581#ifdef CONFIG_IP_FIB_TRIE_STATS
582 t->stats.resize_node_skipped++;
583#endif
584 break;
585 }
Robert Olsson19baf832005-06-21 12:43:18 -0700586 }
587
Robert Olsson05eee482007-03-19 16:27:37 -0700588 if (max_resize < 0) {
589 if (!tn->parent)
590 printk(KERN_WARNING "Fix inflate_threshold_root. Now=%d size=%d bits\n",
591 inflate_threshold_root, tn->bits);
592 else
593 printk(KERN_WARNING "Fix inflate_threshold. Now=%d size=%d bits\n",
594 inflate_threshold, tn->bits);
595 }
596
Robert Olsson19baf832005-06-21 12:43:18 -0700597 check_tnode(tn);
598
599 /*
600 * Halve as long as the number of empty children in this
601 * node is above threshold.
602 */
Robert Olsson2f368952005-07-05 15:02:40 -0700603
Robert Olssone6308be2005-10-04 13:01:58 -0700604
605 /* Keep root node larger */
606
Stephen Hemminger132adf52007-03-08 20:44:43 -0800607 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700608 halve_threshold_use = halve_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900609 else
Robert Olssone6308be2005-10-04 13:01:58 -0700610 halve_threshold_use = halve_threshold;
611
Robert Olsson2f368952005-07-05 15:02:40 -0700612 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700613 max_resize = 10;
614 while (tn->bits > 1 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700615 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700616 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700617
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700618 old_tn = tn;
619 tn = halve(t, tn);
620 if (IS_ERR(tn)) {
621 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700622#ifdef CONFIG_IP_FIB_TRIE_STATS
623 t->stats.resize_node_skipped++;
624#endif
625 break;
626 }
627 }
628
Robert Olsson05eee482007-03-19 16:27:37 -0700629 if (max_resize < 0) {
630 if (!tn->parent)
631 printk(KERN_WARNING "Fix halve_threshold_root. Now=%d size=%d bits\n",
632 halve_threshold_root, tn->bits);
633 else
634 printk(KERN_WARNING "Fix halve_threshold. Now=%d size=%d bits\n",
635 halve_threshold, tn->bits);
636 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700637
Robert Olsson19baf832005-06-21 12:43:18 -0700638 /* Only one child remains */
Robert Olsson19baf832005-06-21 12:43:18 -0700639 if (tn->empty_children == tnode_child_length(tn) - 1)
640 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700641 struct node *n;
642
Olof Johansson91b9a272005-08-09 20:24:39 -0700643 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700644 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700645 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700646
647 /* compress one level */
648
Stephen Hemminger06801912007-08-10 15:22:13 -0700649 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700650 tnode_free(tn);
651 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700652 }
653
654 return (struct node *) tn;
655}
656
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700657static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700658{
659 struct tnode *inode;
660 struct tnode *oldtnode = tn;
661 int olen = tnode_child_length(tn);
662 int i;
663
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700664 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700665
666 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
667
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700668 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700669 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700670
671 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700672 * Preallocate and store tnodes before the actual work so we
673 * don't get into an inconsistent state if memory allocation
674 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700675 * of tnode is ignored.
676 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700677
678 for (i = 0; i < olen; i++) {
Robert Olsson2f368952005-07-05 15:02:40 -0700679 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
680
681 if (inode &&
682 IS_TNODE(inode) &&
683 inode->pos == oldtnode->pos + oldtnode->bits &&
684 inode->bits > 1) {
685 struct tnode *left, *right;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700686 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700687
Robert Olsson2f368952005-07-05 15:02:40 -0700688 left = tnode_new(inode->key&(~m), inode->pos + 1,
689 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700690 if (!left)
691 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700692
Robert Olsson2f368952005-07-05 15:02:40 -0700693 right = tnode_new(inode->key|m, inode->pos + 1,
694 inode->bits - 1);
695
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900696 if (!right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700697 tnode_free(left);
698 goto nomem;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900699 }
Robert Olsson2f368952005-07-05 15:02:40 -0700700
701 put_child(t, tn, 2*i, (struct node *) left);
702 put_child(t, tn, 2*i+1, (struct node *) right);
703 }
704 }
705
Olof Johansson91b9a272005-08-09 20:24:39 -0700706 for (i = 0; i < olen; i++) {
Robert Olsson19baf832005-06-21 12:43:18 -0700707 struct node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700708 struct tnode *left, *right;
709 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700710
Robert Olsson19baf832005-06-21 12:43:18 -0700711 /* An empty child */
712 if (node == NULL)
713 continue;
714
715 /* A leaf or an internal node with skipped bits */
716
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700717 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700718 tn->pos + tn->bits - 1) {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700719 if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
Robert Olsson19baf832005-06-21 12:43:18 -0700720 1) == 0)
721 put_child(t, tn, 2*i, node);
722 else
723 put_child(t, tn, 2*i+1, node);
724 continue;
725 }
726
727 /* An internal node with two children */
728 inode = (struct tnode *) node;
729
730 if (inode->bits == 1) {
731 put_child(t, tn, 2*i, inode->child[0]);
732 put_child(t, tn, 2*i+1, inode->child[1]);
733
734 tnode_free(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700735 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700736 }
737
Olof Johansson91b9a272005-08-09 20:24:39 -0700738 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700739
Olof Johansson91b9a272005-08-09 20:24:39 -0700740 /* We will replace this node 'inode' with two new
741 * ones, 'left' and 'right', each with half of the
742 * original children. The two new nodes will have
743 * a position one bit further down the key and this
744 * means that the "significant" part of their keys
745 * (see the discussion near the top of this file)
746 * will differ by one bit, which will be "0" in
747 * left's key and "1" in right's key. Since we are
748 * moving the key position by one step, the bit that
749 * we are moving away from - the bit at position
750 * (inode->pos) - is the one that will differ between
751 * left and right. So... we synthesize that bit in the
752 * two new keys.
753 * The mask 'm' below will be a single "one" bit at
754 * the position (inode->pos)
755 */
Robert Olsson19baf832005-06-21 12:43:18 -0700756
Olof Johansson91b9a272005-08-09 20:24:39 -0700757 /* Use the old key, but set the new significant
758 * bit to zero.
759 */
Robert Olsson19baf832005-06-21 12:43:18 -0700760
Olof Johansson91b9a272005-08-09 20:24:39 -0700761 left = (struct tnode *) tnode_get_child(tn, 2*i);
762 put_child(t, tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700763
Olof Johansson91b9a272005-08-09 20:24:39 -0700764 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700765
Olof Johansson91b9a272005-08-09 20:24:39 -0700766 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
767 put_child(t, tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700768
Olof Johansson91b9a272005-08-09 20:24:39 -0700769 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700770
Olof Johansson91b9a272005-08-09 20:24:39 -0700771 size = tnode_child_length(left);
772 for (j = 0; j < size; j++) {
773 put_child(t, left, j, inode->child[j]);
774 put_child(t, right, j, inode->child[j + size]);
Robert Olsson19baf832005-06-21 12:43:18 -0700775 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700776 put_child(t, tn, 2*i, resize(t, left));
777 put_child(t, tn, 2*i+1, resize(t, right));
778
779 tnode_free(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700780 }
781 tnode_free(oldtnode);
782 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700783nomem:
784 {
785 int size = tnode_child_length(tn);
786 int j;
787
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700788 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700789 if (tn->child[j])
790 tnode_free((struct tnode *)tn->child[j]);
791
792 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700793
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700794 return ERR_PTR(-ENOMEM);
795 }
Robert Olsson19baf832005-06-21 12:43:18 -0700796}
797
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700798static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700799{
800 struct tnode *oldtnode = tn;
801 struct node *left, *right;
802 int i;
803 int olen = tnode_child_length(tn);
804
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700805 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700806
807 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700808
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700809 if (!tn)
810 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700811
812 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700813 * Preallocate and store tnodes before the actual work so we
814 * don't get into an inconsistent state if memory allocation
815 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700816 * of tnode is ignored.
817 */
818
Olof Johansson91b9a272005-08-09 20:24:39 -0700819 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700820 left = tnode_get_child(oldtnode, i);
821 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700822
Robert Olsson2f368952005-07-05 15:02:40 -0700823 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700824 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700825 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700826
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700827 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700828
829 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700830 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700831
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700832 put_child(t, tn, i/2, (struct node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700833 }
Robert Olsson2f368952005-07-05 15:02:40 -0700834
Robert Olsson2f368952005-07-05 15:02:40 -0700835 }
Robert Olsson19baf832005-06-21 12:43:18 -0700836
Olof Johansson91b9a272005-08-09 20:24:39 -0700837 for (i = 0; i < olen; i += 2) {
838 struct tnode *newBinNode;
839
Robert Olsson19baf832005-06-21 12:43:18 -0700840 left = tnode_get_child(oldtnode, i);
841 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700842
Robert Olsson19baf832005-06-21 12:43:18 -0700843 /* At least one of the children is empty */
844 if (left == NULL) {
845 if (right == NULL) /* Both are empty */
846 continue;
847 put_child(t, tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700848 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700849 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700850
851 if (right == NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700852 put_child(t, tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700853 continue;
854 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700855
Robert Olsson19baf832005-06-21 12:43:18 -0700856 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700857 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
858 put_child(t, tn, i/2, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700859 put_child(t, newBinNode, 0, left);
860 put_child(t, newBinNode, 1, right);
861 put_child(t, tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700862 }
863 tnode_free(oldtnode);
864 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700865nomem:
866 {
867 int size = tnode_child_length(tn);
868 int j;
869
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700870 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700871 if (tn->child[j])
872 tnode_free((struct tnode *)tn->child[j]);
873
874 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700875
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700876 return ERR_PTR(-ENOMEM);
877 }
Robert Olsson19baf832005-06-21 12:43:18 -0700878}
879
Olof Johansson91b9a272005-08-09 20:24:39 -0700880static void trie_init(struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -0700881{
Olof Johansson91b9a272005-08-09 20:24:39 -0700882 if (!t)
883 return;
884
885 t->size = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700886 rcu_assign_pointer(t->trie, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700887 t->revision = 0;
Robert Olsson19baf832005-06-21 12:43:18 -0700888#ifdef CONFIG_IP_FIB_TRIE_STATS
Olof Johansson91b9a272005-08-09 20:24:39 -0700889 memset(&t->stats, 0, sizeof(struct trie_use_stats));
Robert Olsson19baf832005-06-21 12:43:18 -0700890#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700891}
892
Robert Olsson772cb712005-09-19 15:31:18 -0700893/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700894 via get_fa_head and dump */
895
Robert Olsson772cb712005-09-19 15:31:18 -0700896static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700897{
Robert Olsson772cb712005-09-19 15:31:18 -0700898 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700899 struct hlist_node *node;
900 struct leaf_info *li;
901
Robert Olsson2373ce12005-08-25 13:01:29 -0700902 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700903 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700904 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700905
Robert Olsson19baf832005-06-21 12:43:18 -0700906 return NULL;
907}
908
909static inline struct list_head * get_fa_head(struct leaf *l, int plen)
910{
Robert Olsson772cb712005-09-19 15:31:18 -0700911 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700912
Olof Johansson91b9a272005-08-09 20:24:39 -0700913 if (!li)
914 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700915
Olof Johansson91b9a272005-08-09 20:24:39 -0700916 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700917}
918
919static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
920{
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900921 struct leaf_info *li = NULL, *last = NULL;
922 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700923
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900924 if (hlist_empty(head)) {
925 hlist_add_head_rcu(&new->hlist, head);
926 } else {
927 hlist_for_each_entry(li, node, head, hlist) {
928 if (new->plen > li->plen)
929 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700930
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900931 last = li;
932 }
933 if (last)
934 hlist_add_after_rcu(&last->hlist, &new->hlist);
935 else
936 hlist_add_before_rcu(&new->hlist, &li->hlist);
937 }
Robert Olsson19baf832005-06-21 12:43:18 -0700938}
939
Robert Olsson2373ce12005-08-25 13:01:29 -0700940/* rcu_read_lock needs to be hold by caller from readside */
941
Robert Olsson19baf832005-06-21 12:43:18 -0700942static struct leaf *
943fib_find_node(struct trie *t, u32 key)
944{
945 int pos;
946 struct tnode *tn;
947 struct node *n;
948
949 pos = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700950 n = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700951
952 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
953 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700954
Robert Olsson19baf832005-06-21 12:43:18 -0700955 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700956
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700957 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700958 pos = tn->pos + tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700959 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700960 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700961 break;
962 }
963 /* Case we have found a leaf. Compare prefixes */
964
Olof Johansson91b9a272005-08-09 20:24:39 -0700965 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
966 return (struct leaf *)n;
967
Robert Olsson19baf832005-06-21 12:43:18 -0700968 return NULL;
969}
970
971static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
972{
Robert Olsson19baf832005-06-21 12:43:18 -0700973 int wasfull;
Stephen Hemminger06801912007-08-10 15:22:13 -0700974 t_key cindex, key = tn->key;
975 struct tnode *tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700976
Stephen Hemminger06801912007-08-10 15:22:13 -0700977 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700978 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
979 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
980 tn = (struct tnode *) resize (t, (struct tnode *)tn);
981 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -0700982
Stephen Hemminger06801912007-08-10 15:22:13 -0700983 tp = node_parent((struct node *) tn);
984 if (!tp)
Robert Olsson19baf832005-06-21 12:43:18 -0700985 break;
Stephen Hemminger06801912007-08-10 15:22:13 -0700986 tn = tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700987 }
Stephen Hemminger06801912007-08-10 15:22:13 -0700988
Robert Olsson19baf832005-06-21 12:43:18 -0700989 /* Handle last (top) tnode */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700990 if (IS_TNODE(tn))
Robert Olsson19baf832005-06-21 12:43:18 -0700991 tn = (struct tnode*) resize(t, (struct tnode *)tn);
992
993 return (struct node*) tn;
994}
995
Robert Olsson2373ce12005-08-25 13:01:29 -0700996/* only used from updater-side */
997
Robert Olssonf835e472005-06-28 15:00:39 -0700998static struct list_head *
999fib_insert_node(struct trie *t, int *err, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -07001000{
1001 int pos, newpos;
1002 struct tnode *tp = NULL, *tn = NULL;
1003 struct node *n;
1004 struct leaf *l;
1005 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001006 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001007 struct leaf_info *li;
1008 t_key cindex;
1009
1010 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001011 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001012
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001013 /* If we point to NULL, stop. Either the tree is empty and we should
1014 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001015 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001016 * If we point to a T_TNODE, check if it matches our key. Note that
1017 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001018 * not be the parent's 'pos'+'bits'!
1019 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001020 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001021 * the index from our key, push the T_TNODE and walk the tree.
1022 *
1023 * If it doesn't, we have to replace it with a new T_TNODE.
1024 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001025 * If we point to a T_LEAF, it might or might not have the same key
1026 * as we do. If it does, just change the value, update the T_LEAF's
1027 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001028 * If it doesn't, we need to replace it with a T_TNODE.
1029 */
1030
1031 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1032 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001033
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001034 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001035
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001036 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001037 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001038 pos = tn->pos + tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001039 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1040
Stephen Hemminger06801912007-08-10 15:22:13 -07001041 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001042 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001043 break;
1044 }
1045
1046 /*
1047 * n ----> NULL, LEAF or TNODE
1048 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001049 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001050 */
1051
Olof Johansson91b9a272005-08-09 20:24:39 -07001052 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001053
1054 /* Case 1: n is a leaf. Compare prefixes */
1055
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001056 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001057 struct leaf *l = (struct leaf *) n;
1058
Robert Olsson19baf832005-06-21 12:43:18 -07001059 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001060
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001061 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001062 *err = -ENOMEM;
1063 goto err;
1064 }
Robert Olsson19baf832005-06-21 12:43:18 -07001065
1066 fa_head = &li->falh;
1067 insert_leaf_info(&l->list, li);
1068 goto done;
1069 }
1070 t->size++;
1071 l = leaf_new();
1072
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001073 if (!l) {
Robert Olssonf835e472005-06-28 15:00:39 -07001074 *err = -ENOMEM;
1075 goto err;
1076 }
Robert Olsson19baf832005-06-21 12:43:18 -07001077
1078 l->key = key;
1079 li = leaf_info_new(plen);
1080
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001081 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001082 tnode_free((struct tnode *) l);
1083 *err = -ENOMEM;
1084 goto err;
1085 }
Robert Olsson19baf832005-06-21 12:43:18 -07001086
1087 fa_head = &li->falh;
1088 insert_leaf_info(&l->list, li);
1089
Robert Olsson19baf832005-06-21 12:43:18 -07001090 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001091 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001092
Stephen Hemminger06801912007-08-10 15:22:13 -07001093 node_set_parent((struct node *)l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001094
Olof Johansson91b9a272005-08-09 20:24:39 -07001095 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1096 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1097 } else {
1098 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001099 /*
1100 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001101 * first tnode need some special handling
1102 */
1103
1104 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001105 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001106 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001107 pos = 0;
1108
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001109 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001110 newpos = tkey_mismatch(key, pos, n->key);
1111 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001112 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001113 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001114 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001115 }
Robert Olsson19baf832005-06-21 12:43:18 -07001116
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001117 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001118 free_leaf_info(li);
1119 tnode_free((struct tnode *) l);
1120 *err = -ENOMEM;
1121 goto err;
Olof Johansson91b9a272005-08-09 20:24:39 -07001122 }
1123
Stephen Hemminger06801912007-08-10 15:22:13 -07001124 node_set_parent((struct node *)tn, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001125
Olof Johansson91b9a272005-08-09 20:24:39 -07001126 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001127 put_child(t, tn, missbit, (struct node *)l);
1128 put_child(t, tn, 1-missbit, n);
1129
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001130 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001131 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1132 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001133 } else {
Robert Olsson2373ce12005-08-25 13:01:29 -07001134 rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001135 tp = tn;
1136 }
1137 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001138
1139 if (tp && tp->pos + tp->bits > 32)
Stephen Hemminger78c66712005-09-21 00:15:39 -07001140 printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
Robert Olsson19baf832005-06-21 12:43:18 -07001141 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001142
Robert Olsson19baf832005-06-21 12:43:18 -07001143 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001144
1145 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Robert Olssonf835e472005-06-28 15:00:39 -07001146done:
1147 t->revision++;
Olof Johansson91b9a272005-08-09 20:24:39 -07001148err:
Robert Olsson19baf832005-06-21 12:43:18 -07001149 return fa_head;
1150}
1151
Robert Olssond562f1f2007-03-26 14:22:22 -07001152/*
1153 * Caller must hold RTNL.
1154 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001155static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001156{
1157 struct trie *t = (struct trie *) tb->tb_data;
1158 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001159 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001160 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001161 int plen = cfg->fc_dst_len;
1162 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001163 u32 key, mask;
1164 int err;
1165 struct leaf *l;
1166
1167 if (plen > 32)
1168 return -EINVAL;
1169
Thomas Graf4e902c52006-08-17 18:14:52 -07001170 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001171
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001172 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001173
Olof Johansson91b9a272005-08-09 20:24:39 -07001174 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001175
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001176 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001177 return -EINVAL;
1178
1179 key = key & mask;
1180
Thomas Graf4e902c52006-08-17 18:14:52 -07001181 fi = fib_create_info(cfg);
1182 if (IS_ERR(fi)) {
1183 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001184 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001185 }
Robert Olsson19baf832005-06-21 12:43:18 -07001186
1187 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001188 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001189
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001190 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001191 fa_head = get_fa_head(l, plen);
1192 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1193 }
1194
1195 /* Now fa, if non-NULL, points to the first fib alias
1196 * with the same keys [prefix,tos,priority], if such key already
1197 * exists or to the node before which we will insert new one.
1198 *
1199 * If fa is NULL, we will need to allocate a new one and
1200 * insert to the head of f.
1201 *
1202 * If f is NULL, no fib node matched the destination key
1203 * and we need to allocate a new one of those as well.
1204 */
1205
Olof Johansson91b9a272005-08-09 20:24:39 -07001206 if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
Robert Olsson19baf832005-06-21 12:43:18 -07001207 struct fib_alias *fa_orig;
1208
1209 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001210 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001211 goto out;
1212
Thomas Graf4e902c52006-08-17 18:14:52 -07001213 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001214 struct fib_info *fi_drop;
1215 u8 state;
1216
Robert Olsson2373ce12005-08-25 13:01:29 -07001217 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001218 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001219 if (new_fa == NULL)
1220 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001221
1222 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001223 new_fa->fa_tos = fa->fa_tos;
1224 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001225 new_fa->fa_type = cfg->fc_type;
1226 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001227 state = fa->fa_state;
Robert Olsson2373ce12005-08-25 13:01:29 -07001228 new_fa->fa_state &= ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001229
Robert Olsson2373ce12005-08-25 13:01:29 -07001230 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1231 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001232
1233 fib_release_info(fi_drop);
1234 if (state & FA_S_ACCESSED)
Olof Johansson91b9a272005-08-09 20:24:39 -07001235 rt_cache_flush(-1);
Milan Kocianb8f55832007-05-23 14:55:06 -07001236 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1237 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001238
Olof Johansson91b9a272005-08-09 20:24:39 -07001239 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001240 }
1241 /* Error if we find a perfect match which
1242 * uses the same scope, type, and nexthop
1243 * information.
1244 */
1245 fa_orig = fa;
1246 list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
1247 if (fa->fa_tos != tos)
1248 break;
1249 if (fa->fa_info->fib_priority != fi->fib_priority)
1250 break;
Thomas Graf4e902c52006-08-17 18:14:52 -07001251 if (fa->fa_type == cfg->fc_type &&
1252 fa->fa_scope == cfg->fc_scope &&
Robert Olsson19baf832005-06-21 12:43:18 -07001253 fa->fa_info == fi) {
1254 goto out;
1255 }
1256 }
Thomas Graf4e902c52006-08-17 18:14:52 -07001257 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Robert Olsson19baf832005-06-21 12:43:18 -07001258 fa = fa_orig;
1259 }
1260 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001261 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001262 goto out;
1263
1264 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001265 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001266 if (new_fa == NULL)
1267 goto out;
1268
1269 new_fa->fa_info = fi;
1270 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001271 new_fa->fa_type = cfg->fc_type;
1272 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001273 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001274 /*
1275 * Insert new entry to the list.
1276 */
1277
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001278 if (!fa_head) {
Robert Olssonf835e472005-06-28 15:00:39 -07001279 err = 0;
Herbert Xub47b2ec2006-07-12 13:29:56 -07001280 fa_head = fib_insert_node(t, &err, key, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001281 if (err)
Robert Olssonf835e472005-06-28 15:00:39 -07001282 goto out_free_new_fa;
1283 }
Robert Olsson19baf832005-06-21 12:43:18 -07001284
Robert Olsson2373ce12005-08-25 13:01:29 -07001285 list_add_tail_rcu(&new_fa->fa_list,
1286 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001287
1288 rt_cache_flush(-1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001289 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001290 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001291succeeded:
1292 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001293
1294out_free_new_fa:
1295 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001296out:
1297 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001298err:
Robert Olsson19baf832005-06-21 12:43:18 -07001299 return err;
1300}
1301
Robert Olsson2373ce12005-08-25 13:01:29 -07001302
Robert Olsson772cb712005-09-19 15:31:18 -07001303/* should be called with rcu_read_lock */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001304static inline int check_leaf(struct trie *t, struct leaf *l,
1305 t_key key, int *plen, const struct flowi *flp,
Patrick McHardy06c74272005-08-23 22:06:09 -07001306 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001307{
Patrick McHardy06c74272005-08-23 22:06:09 -07001308 int err, i;
Al Viro888454c2006-09-19 13:42:46 -07001309 __be32 mask;
Robert Olsson19baf832005-06-21 12:43:18 -07001310 struct leaf_info *li;
1311 struct hlist_head *hhead = &l->list;
1312 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001313
Robert Olsson2373ce12005-08-25 13:01:29 -07001314 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001315 i = li->plen;
Al Viro888454c2006-09-19 13:42:46 -07001316 mask = inet_make_mask(i);
1317 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001318 continue;
1319
Al Viro888454c2006-09-19 13:42:46 -07001320 if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001321 *plen = i;
1322#ifdef CONFIG_IP_FIB_TRIE_STATS
1323 t->stats.semantic_match_passed++;
1324#endif
Patrick McHardy06c74272005-08-23 22:06:09 -07001325 return err;
Robert Olsson19baf832005-06-21 12:43:18 -07001326 }
1327#ifdef CONFIG_IP_FIB_TRIE_STATS
1328 t->stats.semantic_match_miss++;
1329#endif
1330 }
Patrick McHardy06c74272005-08-23 22:06:09 -07001331 return 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001332}
1333
1334static int
1335fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1336{
1337 struct trie *t = (struct trie *) tb->tb_data;
1338 int plen, ret = 0;
1339 struct node *n;
1340 struct tnode *pn;
1341 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001342 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001343 int chopped_off;
1344 t_key cindex = 0;
1345 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001346 struct tnode *cn;
1347 t_key node_prefix, key_prefix, pref_mismatch;
1348 int mp;
1349
Robert Olsson2373ce12005-08-25 13:01:29 -07001350 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001351
Robert Olsson2373ce12005-08-25 13:01:29 -07001352 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001353 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001354 goto failed;
1355
1356#ifdef CONFIG_IP_FIB_TRIE_STATS
1357 t->stats.gets++;
1358#endif
1359
1360 /* Just a leaf? */
1361 if (IS_LEAF(n)) {
Patrick McHardy06c74272005-08-23 22:06:09 -07001362 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001363 goto found;
1364 goto failed;
1365 }
1366 pn = (struct tnode *) n;
1367 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001368
Olof Johansson91b9a272005-08-09 20:24:39 -07001369 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001370 pos = pn->pos;
1371 bits = pn->bits;
1372
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001373 if (!chopped_off)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001374 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1375 pos, bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001376
1377 n = tnode_get_child(pn, cindex);
1378
1379 if (n == NULL) {
1380#ifdef CONFIG_IP_FIB_TRIE_STATS
1381 t->stats.null_node_hit++;
1382#endif
1383 goto backtrace;
1384 }
1385
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001386 if (IS_LEAF(n)) {
Patrick McHardy06c74272005-08-23 22:06:09 -07001387 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001388 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001389 else
1390 goto backtrace;
1391 }
1392
1393#define HL_OPTIMIZE
1394#ifdef HL_OPTIMIZE
1395 cn = (struct tnode *)n;
1396
1397 /*
1398 * It's a tnode, and we can do some extra checks here if we
1399 * like, to avoid descending into a dead-end branch.
1400 * This tnode is in the parent's child array at index
1401 * key[p_pos..p_pos+p_bits] but potentially with some bits
1402 * chopped off, so in reality the index may be just a
1403 * subprefix, padded with zero at the end.
1404 * We can also take a look at any skipped bits in this
1405 * tnode - everything up to p_pos is supposed to be ok,
1406 * and the non-chopped bits of the index (se previous
1407 * paragraph) are also guaranteed ok, but the rest is
1408 * considered unknown.
1409 *
1410 * The skipped bits are key[pos+bits..cn->pos].
1411 */
1412
1413 /* If current_prefix_length < pos+bits, we are already doing
1414 * actual prefix matching, which means everything from
1415 * pos+(bits-chopped_off) onward must be zero along some
1416 * branch of this subtree - otherwise there is *no* valid
1417 * prefix present. Here we can only check the skipped
1418 * bits. Remember, since we have already indexed into the
1419 * parent's child array, we know that the bits we chopped of
1420 * *are* zero.
1421 */
1422
1423 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1424
1425 if (current_prefix_length < pos+bits) {
1426 if (tkey_extract_bits(cn->key, current_prefix_length,
1427 cn->pos - current_prefix_length) != 0 ||
1428 !(cn->child[0]))
1429 goto backtrace;
1430 }
1431
1432 /*
1433 * If chopped_off=0, the index is fully validated and we
1434 * only need to look at the skipped bits for this, the new,
1435 * tnode. What we actually want to do is to find out if
1436 * these skipped bits match our key perfectly, or if we will
1437 * have to count on finding a matching prefix further down,
1438 * because if we do, we would like to have some way of
1439 * verifying the existence of such a prefix at this point.
1440 */
1441
1442 /* The only thing we can do at this point is to verify that
1443 * any such matching prefix can indeed be a prefix to our
1444 * key, and if the bits in the node we are inspecting that
1445 * do not match our key are not ZERO, this cannot be true.
1446 * Thus, find out where there is a mismatch (before cn->pos)
1447 * and verify that all the mismatching bits are zero in the
1448 * new tnode's key.
1449 */
1450
1451 /* Note: We aren't very concerned about the piece of the key
1452 * that precede pn->pos+pn->bits, since these have already been
1453 * checked. The bits after cn->pos aren't checked since these are
1454 * by definition "unknown" at this point. Thus, what we want to
1455 * see is if we are about to enter the "prefix matching" state,
1456 * and in that case verify that the skipped bits that will prevail
1457 * throughout this subtree are zero, as they have to be if we are
1458 * to find a matching prefix.
1459 */
1460
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001461 node_prefix = mask_pfx(cn->key, cn->pos);
1462 key_prefix = mask_pfx(key, cn->pos);
Olof Johansson91b9a272005-08-09 20:24:39 -07001463 pref_mismatch = key_prefix^node_prefix;
1464 mp = 0;
1465
1466 /* In short: If skipped bits in this node do not match the search
1467 * key, enter the "prefix matching" state.directly.
1468 */
1469 if (pref_mismatch) {
1470 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1471 mp++;
1472 pref_mismatch = pref_mismatch <<1;
1473 }
1474 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1475
1476 if (key_prefix != 0)
1477 goto backtrace;
1478
1479 if (current_prefix_length >= cn->pos)
1480 current_prefix_length = mp;
1481 }
1482#endif
1483 pn = (struct tnode *)n; /* Descend */
1484 chopped_off = 0;
1485 continue;
1486
Robert Olsson19baf832005-06-21 12:43:18 -07001487backtrace:
1488 chopped_off++;
1489
1490 /* As zero don't change the child key (cindex) */
Olof Johansson91b9a272005-08-09 20:24:39 -07001491 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001492 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001493
1494 /* Decrease current_... with bits chopped off */
1495 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1496 current_prefix_length = pn->pos + pn->bits - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001497
Robert Olsson19baf832005-06-21 12:43:18 -07001498 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001499 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001500 * chopped off all bits in this tnode walk up to our parent.
1501 */
1502
Olof Johansson91b9a272005-08-09 20:24:39 -07001503 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001504 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001505 } else {
Stephen Hemminger06801912007-08-10 15:22:13 -07001506 struct tnode *parent = node_parent((struct node *) pn);
1507 if (!parent)
Robert Olsson19baf832005-06-21 12:43:18 -07001508 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001509
Robert Olsson19baf832005-06-21 12:43:18 -07001510 /* Get Child's index */
Stephen Hemminger06801912007-08-10 15:22:13 -07001511 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1512 pn = parent;
Robert Olsson19baf832005-06-21 12:43:18 -07001513 chopped_off = 0;
1514
1515#ifdef CONFIG_IP_FIB_TRIE_STATS
1516 t->stats.backtrack++;
1517#endif
1518 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001519 }
Robert Olsson19baf832005-06-21 12:43:18 -07001520 }
1521failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001522 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001523found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001524 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001525 return ret;
1526}
1527
Robert Olsson2373ce12005-08-25 13:01:29 -07001528/* only called from updater side */
Robert Olsson19baf832005-06-21 12:43:18 -07001529static int trie_leaf_remove(struct trie *t, t_key key)
1530{
1531 t_key cindex;
1532 struct tnode *tp = NULL;
1533 struct node *n = t->trie;
1534 struct leaf *l;
1535
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001536 pr_debug("entering trie_leaf_remove(%p)\n", n);
Robert Olsson19baf832005-06-21 12:43:18 -07001537
1538 /* Note that in the case skipped bits, those bits are *not* checked!
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001539 * When we finish this, we will have NULL or a T_LEAF, and the
Robert Olsson19baf832005-06-21 12:43:18 -07001540 * T_LEAF may or may not match our key.
1541 */
1542
Olof Johansson91b9a272005-08-09 20:24:39 -07001543 while (n != NULL && IS_TNODE(n)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001544 struct tnode *tn = (struct tnode *) n;
1545 check_tnode(tn);
1546 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1547
Stephen Hemminger06801912007-08-10 15:22:13 -07001548 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001549 }
Robert Olsson19baf832005-06-21 12:43:18 -07001550 l = (struct leaf *) n;
1551
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001552 if (!n || !tkey_equals(l->key, key))
Robert Olsson19baf832005-06-21 12:43:18 -07001553 return 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001554
1555 /*
1556 * Key found.
1557 * Remove the leaf and rebalance the tree
Robert Olsson19baf832005-06-21 12:43:18 -07001558 */
1559
1560 t->revision++;
1561 t->size--;
1562
Stephen Hemminger06801912007-08-10 15:22:13 -07001563 tp = node_parent(n);
Robert Olsson19baf832005-06-21 12:43:18 -07001564 tnode_free((struct tnode *) n);
1565
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001566 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001567 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1568 put_child(t, (struct tnode *)tp, cindex, NULL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001569 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Olof Johansson91b9a272005-08-09 20:24:39 -07001570 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001571 rcu_assign_pointer(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001572
1573 return 1;
1574}
1575
Robert Olssond562f1f2007-03-26 14:22:22 -07001576/*
1577 * Caller must hold RTNL.
1578 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001579static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001580{
1581 struct trie *t = (struct trie *) tb->tb_data;
1582 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001583 int plen = cfg->fc_dst_len;
1584 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001585 struct fib_alias *fa, *fa_to_delete;
1586 struct list_head *fa_head;
1587 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001588 struct leaf_info *li;
1589
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001590 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001591 return -EINVAL;
1592
Thomas Graf4e902c52006-08-17 18:14:52 -07001593 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001594 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001595
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001596 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001597 return -EINVAL;
1598
1599 key = key & mask;
1600 l = fib_find_node(t, key);
1601
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001602 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001603 return -ESRCH;
1604
1605 fa_head = get_fa_head(l, plen);
1606 fa = fib_find_alias(fa_head, tos, 0);
1607
1608 if (!fa)
1609 return -ESRCH;
1610
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001611 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001612
1613 fa_to_delete = NULL;
1614 fa_head = fa->fa_list.prev;
Robert Olsson2373ce12005-08-25 13:01:29 -07001615
Robert Olsson19baf832005-06-21 12:43:18 -07001616 list_for_each_entry(fa, fa_head, fa_list) {
1617 struct fib_info *fi = fa->fa_info;
1618
1619 if (fa->fa_tos != tos)
1620 break;
1621
Thomas Graf4e902c52006-08-17 18:14:52 -07001622 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1623 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1624 fa->fa_scope == cfg->fc_scope) &&
1625 (!cfg->fc_protocol ||
1626 fi->fib_protocol == cfg->fc_protocol) &&
1627 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001628 fa_to_delete = fa;
1629 break;
1630 }
1631 }
1632
Olof Johansson91b9a272005-08-09 20:24:39 -07001633 if (!fa_to_delete)
1634 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001635
Olof Johansson91b9a272005-08-09 20:24:39 -07001636 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001637 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001638 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001639
Olof Johansson91b9a272005-08-09 20:24:39 -07001640 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001641 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001642
Robert Olsson2373ce12005-08-25 13:01:29 -07001643 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001644
Olof Johansson91b9a272005-08-09 20:24:39 -07001645 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001646 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001647 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001648 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001649
1650 if (hlist_empty(&l->list))
1651 trie_leaf_remove(t, key);
1652
1653 if (fa->fa_state & FA_S_ACCESSED)
1654 rt_cache_flush(-1);
1655
Robert Olsson2373ce12005-08-25 13:01:29 -07001656 fib_release_info(fa->fa_info);
1657 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001658 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001659}
1660
1661static int trie_flush_list(struct trie *t, struct list_head *head)
1662{
1663 struct fib_alias *fa, *fa_node;
1664 int found = 0;
1665
1666 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1667 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001668
Robert Olsson2373ce12005-08-25 13:01:29 -07001669 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1670 list_del_rcu(&fa->fa_list);
1671 fib_release_info(fa->fa_info);
1672 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001673 found++;
1674 }
1675 }
1676 return found;
1677}
1678
1679static int trie_flush_leaf(struct trie *t, struct leaf *l)
1680{
1681 int found = 0;
1682 struct hlist_head *lih = &l->list;
1683 struct hlist_node *node, *tmp;
1684 struct leaf_info *li = NULL;
1685
1686 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001687 found += trie_flush_list(t, &li->falh);
1688
1689 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001690 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001691 free_leaf_info(li);
1692 }
1693 }
1694 return found;
1695}
1696
Robert Olsson2373ce12005-08-25 13:01:29 -07001697/* rcu_read_lock needs to be hold by caller from readside */
1698
Robert Olsson19baf832005-06-21 12:43:18 -07001699static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1700{
1701 struct node *c = (struct node *) thisleaf;
1702 struct tnode *p;
1703 int idx;
Robert Olsson2373ce12005-08-25 13:01:29 -07001704 struct node *trie = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -07001705
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001706 if (c == NULL) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001707 if (trie == NULL)
Robert Olsson19baf832005-06-21 12:43:18 -07001708 return NULL;
1709
Robert Olsson2373ce12005-08-25 13:01:29 -07001710 if (IS_LEAF(trie)) /* trie w. just a leaf */
1711 return (struct leaf *) trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001712
Robert Olsson2373ce12005-08-25 13:01:29 -07001713 p = (struct tnode*) trie; /* Start */
Olof Johansson91b9a272005-08-09 20:24:39 -07001714 } else
Stephen Hemminger06801912007-08-10 15:22:13 -07001715 p = node_parent(c);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001716
Robert Olsson19baf832005-06-21 12:43:18 -07001717 while (p) {
1718 int pos, last;
1719
1720 /* Find the next child of the parent */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001721 if (c)
1722 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1723 else
Robert Olsson19baf832005-06-21 12:43:18 -07001724 pos = 0;
1725
1726 last = 1 << p->bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001727 for (idx = pos; idx < last ; idx++) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001728 c = rcu_dereference(p->child[idx]);
1729
1730 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001731 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001732
Olof Johansson91b9a272005-08-09 20:24:39 -07001733 /* Decend if tnode */
Robert Olsson2373ce12005-08-25 13:01:29 -07001734 while (IS_TNODE(c)) {
1735 p = (struct tnode *) c;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09001736 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001737
Olof Johansson91b9a272005-08-09 20:24:39 -07001738 /* Rightmost non-NULL branch */
1739 if (p && IS_TNODE(p))
Robert Olsson2373ce12005-08-25 13:01:29 -07001740 while (!(c = rcu_dereference(p->child[idx]))
1741 && idx < (1<<p->bits)) idx++;
Robert Olsson19baf832005-06-21 12:43:18 -07001742
Olof Johansson91b9a272005-08-09 20:24:39 -07001743 /* Done with this tnode? */
Robert Olsson2373ce12005-08-25 13:01:29 -07001744 if (idx >= (1 << p->bits) || !c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001745 goto up;
Robert Olsson19baf832005-06-21 12:43:18 -07001746 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001747 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001748 }
1749up:
1750 /* No more children go up one step */
Olof Johansson91b9a272005-08-09 20:24:39 -07001751 c = (struct node *) p;
Stephen Hemminger06801912007-08-10 15:22:13 -07001752 p = node_parent(c);
Robert Olsson19baf832005-06-21 12:43:18 -07001753 }
1754 return NULL; /* Ready. Root of trie */
1755}
1756
Robert Olssond562f1f2007-03-26 14:22:22 -07001757/*
1758 * Caller must hold RTNL.
1759 */
Robert Olsson19baf832005-06-21 12:43:18 -07001760static int fn_trie_flush(struct fib_table *tb)
1761{
1762 struct trie *t = (struct trie *) tb->tb_data;
1763 struct leaf *ll = NULL, *l = NULL;
1764 int found = 0, h;
1765
1766 t->revision++;
1767
Olof Johansson91b9a272005-08-09 20:24:39 -07001768 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001769 found += trie_flush_leaf(t, l);
1770
1771 if (ll && hlist_empty(&ll->list))
1772 trie_leaf_remove(t, ll->key);
1773 ll = l;
1774 }
1775
1776 if (ll && hlist_empty(&ll->list))
1777 trie_leaf_remove(t, ll->key);
1778
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001779 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001780 return found;
1781}
1782
Olof Johansson91b9a272005-08-09 20:24:39 -07001783static int trie_last_dflt = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001784
1785static void
1786fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1787{
1788 struct trie *t = (struct trie *) tb->tb_data;
1789 int order, last_idx;
1790 struct fib_info *fi = NULL;
1791 struct fib_info *last_resort;
1792 struct fib_alias *fa = NULL;
1793 struct list_head *fa_head;
1794 struct leaf *l;
1795
1796 last_idx = -1;
1797 last_resort = NULL;
1798 order = -1;
1799
Robert Olsson2373ce12005-08-25 13:01:29 -07001800 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001801
Robert Olsson19baf832005-06-21 12:43:18 -07001802 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001803 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001804 goto out;
1805
1806 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001807 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001808 goto out;
1809
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001810 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001811 goto out;
1812
Robert Olsson2373ce12005-08-25 13:01:29 -07001813 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001814 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001815
Robert Olsson19baf832005-06-21 12:43:18 -07001816 if (fa->fa_scope != res->scope ||
1817 fa->fa_type != RTN_UNICAST)
1818 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001819
Robert Olsson19baf832005-06-21 12:43:18 -07001820 if (next_fi->fib_priority > res->fi->fib_priority)
1821 break;
1822 if (!next_fi->fib_nh[0].nh_gw ||
1823 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1824 continue;
1825 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001826
Robert Olsson19baf832005-06-21 12:43:18 -07001827 if (fi == NULL) {
1828 if (next_fi != res->fi)
1829 break;
1830 } else if (!fib_detect_death(fi, order, &last_resort,
1831 &last_idx, &trie_last_dflt)) {
1832 if (res->fi)
1833 fib_info_put(res->fi);
1834 res->fi = fi;
1835 atomic_inc(&fi->fib_clntref);
1836 trie_last_dflt = order;
1837 goto out;
1838 }
1839 fi = next_fi;
1840 order++;
1841 }
1842 if (order <= 0 || fi == NULL) {
1843 trie_last_dflt = -1;
1844 goto out;
1845 }
1846
1847 if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) {
1848 if (res->fi)
1849 fib_info_put(res->fi);
1850 res->fi = fi;
1851 atomic_inc(&fi->fib_clntref);
1852 trie_last_dflt = order;
1853 goto out;
1854 }
1855 if (last_idx >= 0) {
1856 if (res->fi)
1857 fib_info_put(res->fi);
1858 res->fi = last_resort;
1859 if (last_resort)
1860 atomic_inc(&last_resort->fib_clntref);
1861 }
1862 trie_last_dflt = last_idx;
1863 out:;
Robert Olsson2373ce12005-08-25 13:01:29 -07001864 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001865}
1866
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001867static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001868 struct sk_buff *skb, struct netlink_callback *cb)
1869{
1870 int i, s_i;
1871 struct fib_alias *fa;
1872
Al Viro32ab5f82006-09-26 22:21:45 -07001873 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001874
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001875 s_i = cb->args[4];
Robert Olsson19baf832005-06-21 12:43:18 -07001876 i = 0;
1877
Robert Olsson2373ce12005-08-25 13:01:29 -07001878 /* rcu_read_lock is hold by caller */
1879
1880 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001881 if (i < s_i) {
1882 i++;
1883 continue;
1884 }
Stephen Hemminger78c66712005-09-21 00:15:39 -07001885 BUG_ON(!fa->fa_info);
Robert Olsson19baf832005-06-21 12:43:18 -07001886
1887 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1888 cb->nlh->nlmsg_seq,
1889 RTM_NEWROUTE,
1890 tb->tb_id,
1891 fa->fa_type,
1892 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001893 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001894 plen,
1895 fa->fa_tos,
David S. Miller90f66912005-06-21 14:43:28 -07001896 fa->fa_info, 0) < 0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001897 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001898 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001899 }
Robert Olsson19baf832005-06-21 12:43:18 -07001900 i++;
1901 }
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001902 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001903 return skb->len;
1904}
1905
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001906static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
Robert Olsson19baf832005-06-21 12:43:18 -07001907 struct netlink_callback *cb)
1908{
1909 int h, s_h;
1910 struct list_head *fa_head;
1911 struct leaf *l = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001912
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001913 s_h = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001914
Olof Johansson91b9a272005-08-09 20:24:39 -07001915 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001916 if (h < s_h)
1917 continue;
1918 if (h > s_h)
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001919 memset(&cb->args[4], 0,
1920 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001921
1922 fa_head = get_fa_head(l, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001923
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001924 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001925 continue;
1926
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001927 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001928 continue;
1929
1930 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001931 cb->args[3] = h;
Robert Olsson19baf832005-06-21 12:43:18 -07001932 return -1;
1933 }
1934 }
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001935 cb->args[3] = h;
Robert Olsson19baf832005-06-21 12:43:18 -07001936 return skb->len;
1937}
1938
1939static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1940{
1941 int m, s_m;
1942 struct trie *t = (struct trie *) tb->tb_data;
1943
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001944 s_m = cb->args[2];
Robert Olsson19baf832005-06-21 12:43:18 -07001945
Robert Olsson2373ce12005-08-25 13:01:29 -07001946 rcu_read_lock();
Olof Johansson91b9a272005-08-09 20:24:39 -07001947 for (m = 0; m <= 32; m++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001948 if (m < s_m)
1949 continue;
1950 if (m > s_m)
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001951 memset(&cb->args[3], 0,
1952 sizeof(cb->args) - 3*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001953
1954 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001955 cb->args[2] = m;
Robert Olsson19baf832005-06-21 12:43:18 -07001956 goto out;
1957 }
1958 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001959 rcu_read_unlock();
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001960 cb->args[2] = m;
Robert Olsson19baf832005-06-21 12:43:18 -07001961 return skb->len;
Olof Johansson91b9a272005-08-09 20:24:39 -07001962out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001963 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001964 return -1;
1965}
1966
1967/* Fix more generic FIB names for init later */
1968
1969#ifdef CONFIG_IP_MULTIPLE_TABLES
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001970struct fib_table * fib_hash_init(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001971#else
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001972struct fib_table * __init fib_hash_init(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001973#endif
1974{
1975 struct fib_table *tb;
1976 struct trie *t;
1977
1978 if (fn_alias_kmem == NULL)
1979 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1980 sizeof(struct fib_alias),
1981 0, SLAB_HWCACHE_ALIGN,
Paul Mundt20c2df82007-07-20 10:11:58 +09001982 NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001983
1984 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1985 GFP_KERNEL);
1986 if (tb == NULL)
1987 return NULL;
1988
1989 tb->tb_id = id;
1990 tb->tb_lookup = fn_trie_lookup;
1991 tb->tb_insert = fn_trie_insert;
1992 tb->tb_delete = fn_trie_delete;
1993 tb->tb_flush = fn_trie_flush;
1994 tb->tb_select_default = fn_trie_select_default;
1995 tb->tb_dump = fn_trie_dump;
1996 memset(tb->tb_data, 0, sizeof(struct trie));
1997
1998 t = (struct trie *) tb->tb_data;
1999
2000 trie_init(t);
2001
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002002 if (id == RT_TABLE_LOCAL)
Olof Johansson91b9a272005-08-09 20:24:39 -07002003 trie_local = t;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002004 else if (id == RT_TABLE_MAIN)
Olof Johansson91b9a272005-08-09 20:24:39 -07002005 trie_main = t;
Robert Olsson19baf832005-06-21 12:43:18 -07002006
2007 if (id == RT_TABLE_LOCAL)
Stephen Hemminger78c66712005-09-21 00:15:39 -07002008 printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07002009
2010 return tb;
2011}
2012
Robert Olsson19baf832005-06-21 12:43:18 -07002013#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002014/* Depth first Trie walk iterator */
2015struct fib_trie_iter {
2016 struct tnode *tnode;
2017 struct trie *trie;
2018 unsigned index;
2019 unsigned depth;
2020};
Robert Olsson19baf832005-06-21 12:43:18 -07002021
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002022static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002023{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002024 struct tnode *tn = iter->tnode;
2025 unsigned cindex = iter->index;
2026 struct tnode *p;
2027
Eric W. Biederman6640e692007-01-24 14:42:04 -08002028 /* A single entry routing table */
2029 if (!tn)
2030 return NULL;
2031
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002032 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2033 iter->tnode, iter->index, iter->depth);
2034rescan:
2035 while (cindex < (1<<tn->bits)) {
2036 struct node *n = tnode_get_child(tn, cindex);
2037
2038 if (n) {
2039 if (IS_LEAF(n)) {
2040 iter->tnode = tn;
2041 iter->index = cindex + 1;
2042 } else {
2043 /* push down one level */
2044 iter->tnode = (struct tnode *) n;
2045 iter->index = 0;
2046 ++iter->depth;
2047 }
2048 return n;
2049 }
2050
2051 ++cindex;
2052 }
2053
2054 /* Current node exhausted, pop back up */
Stephen Hemminger06801912007-08-10 15:22:13 -07002055 p = node_parent((struct node *)tn);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002056 if (p) {
2057 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2058 tn = p;
2059 --iter->depth;
2060 goto rescan;
2061 }
2062
2063 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002064 return NULL;
2065}
2066
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002067static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2068 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002069{
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002070 struct node *n ;
2071
Stephen Hemminger132adf52007-03-08 20:44:43 -08002072 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002073 return NULL;
2074
2075 n = rcu_dereference(t->trie);
2076
Stephen Hemminger132adf52007-03-08 20:44:43 -08002077 if (!iter)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002078 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002079
Eric W. Biederman6640e692007-01-24 14:42:04 -08002080 if (n) {
2081 if (IS_TNODE(n)) {
2082 iter->tnode = (struct tnode *) n;
2083 iter->trie = t;
2084 iter->index = 0;
2085 iter->depth = 1;
2086 } else {
2087 iter->tnode = NULL;
2088 iter->trie = t;
2089 iter->index = 0;
2090 iter->depth = 0;
2091 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002092 return n;
2093 }
Robert Olsson19baf832005-06-21 12:43:18 -07002094 return NULL;
2095}
2096
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002097static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002098{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002099 struct node *n;
2100 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002101
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002102 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002103
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002104 rcu_read_lock();
2105 for (n = fib_trie_get_first(&iter, t); n;
2106 n = fib_trie_get_next(&iter)) {
2107 if (IS_LEAF(n)) {
2108 s->leaves++;
2109 s->totdepth += iter.depth;
2110 if (iter.depth > s->maxdepth)
2111 s->maxdepth = iter.depth;
2112 } else {
2113 const struct tnode *tn = (const struct tnode *) n;
2114 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002115
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002116 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002117 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002118 s->nodesizes[tn->bits]++;
2119
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002120 for (i = 0; i < (1<<tn->bits); i++)
2121 if (!tn->child[i])
2122 s->nullpointers++;
2123 }
2124 }
2125 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002126}
2127
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002128/*
Robert Olsson19baf832005-06-21 12:43:18 -07002129 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002130 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002131static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002132{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002133 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002134
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002135 if (stat->leaves)
2136 avdepth = stat->totdepth*100 / stat->leaves;
2137 else
2138 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002139
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002140 seq_printf(seq, "\tAver depth: %d.%02d\n", avdepth / 100, avdepth % 100 );
2141 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002142
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002143 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Olof Johansson91b9a272005-08-09 20:24:39 -07002144
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002145 bytes = sizeof(struct leaf) * stat->leaves;
2146 seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
2147 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002148
Robert Olsson06ef9212006-03-20 21:35:01 -08002149 max = MAX_STAT_DEPTH;
2150 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002151 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002152
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002153 pointers = 0;
2154 for (i = 1; i <= max; i++)
2155 if (stat->nodesizes[i] != 0) {
2156 seq_printf(seq, " %d: %d", i, stat->nodesizes[i]);
2157 pointers += (1<<i) * stat->nodesizes[i];
2158 }
2159 seq_putc(seq, '\n');
2160 seq_printf(seq, "\tPointers: %d\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002161
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002162 bytes += sizeof(struct node *) * pointers;
2163 seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
2164 seq_printf(seq, "Total size: %d kB\n", (bytes + 1023) / 1024);
Robert Olsson19baf832005-06-21 12:43:18 -07002165
2166#ifdef CONFIG_IP_FIB_TRIE_STATS
2167 seq_printf(seq, "Counters:\n---------\n");
2168 seq_printf(seq,"gets = %d\n", t->stats.gets);
2169 seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
2170 seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
2171 seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
2172 seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
Robert Olsson2f368952005-07-05 15:02:40 -07002173 seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002174#ifdef CLEAR_STATS
2175 memset(&(t->stats), 0, sizeof(t->stats));
2176#endif
2177#endif /* CONFIG_IP_FIB_TRIE_STATS */
2178}
2179
2180static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2181{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002182 struct trie_stat *stat;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002183
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002184 stat = kmalloc(sizeof(*stat), GFP_KERNEL);
2185 if (!stat)
2186 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002187
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002188 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2189 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002190
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002191 if (trie_local) {
2192 seq_printf(seq, "Local:\n");
2193 trie_collect_stats(trie_local, stat);
2194 trie_show_stats(seq, stat);
Robert Olsson19baf832005-06-21 12:43:18 -07002195 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002196
2197 if (trie_main) {
2198 seq_printf(seq, "Main:\n");
2199 trie_collect_stats(trie_main, stat);
2200 trie_show_stats(seq, stat);
2201 }
2202 kfree(stat);
2203
Robert Olsson19baf832005-06-21 12:43:18 -07002204 return 0;
2205}
2206
Robert Olsson19baf832005-06-21 12:43:18 -07002207static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2208{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002209 return single_open(file, fib_triestat_seq_show, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07002210}
2211
Arjan van de Ven9a321442007-02-12 00:55:35 -08002212static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002213 .owner = THIS_MODULE,
2214 .open = fib_triestat_seq_open,
2215 .read = seq_read,
2216 .llseek = seq_lseek,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002217 .release = single_release,
Robert Olsson19baf832005-06-21 12:43:18 -07002218};
2219
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002220static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2221 loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002222{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002223 loff_t idx = 0;
2224 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -07002225
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002226 for (n = fib_trie_get_first(iter, trie_local);
2227 n; ++idx, n = fib_trie_get_next(iter)) {
2228 if (pos == idx)
2229 return n;
2230 }
Robert Olsson19baf832005-06-21 12:43:18 -07002231
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002232 for (n = fib_trie_get_first(iter, trie_main);
2233 n; ++idx, n = fib_trie_get_next(iter)) {
2234 if (pos == idx)
2235 return n;
2236 }
Robert Olsson19baf832005-06-21 12:43:18 -07002237 return NULL;
2238}
2239
2240static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2241{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002242 rcu_read_lock();
2243 if (*pos == 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07002244 return SEQ_START_TOKEN;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002245 return fib_trie_get_idx(seq->private, *pos - 1);
Robert Olsson19baf832005-06-21 12:43:18 -07002246}
2247
2248static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2249{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002250 struct fib_trie_iter *iter = seq->private;
2251 void *l = v;
2252
Robert Olsson19baf832005-06-21 12:43:18 -07002253 ++*pos;
Olof Johansson91b9a272005-08-09 20:24:39 -07002254 if (v == SEQ_START_TOKEN)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002255 return fib_trie_get_idx(iter, 0);
Olof Johansson91b9a272005-08-09 20:24:39 -07002256
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002257 v = fib_trie_get_next(iter);
2258 BUG_ON(v == l);
2259 if (v)
2260 return v;
2261
2262 /* continue scan in next trie */
2263 if (iter->trie == trie_local)
2264 return fib_trie_get_first(iter, trie_main);
2265
2266 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07002267}
2268
2269static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2270{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002271 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002272}
2273
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002274static void seq_indent(struct seq_file *seq, int n)
2275{
2276 while (n-- > 0) seq_puts(seq, " ");
2277}
Robert Olsson19baf832005-06-21 12:43:18 -07002278
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002279static inline const char *rtn_scope(enum rt_scope_t s)
2280{
2281 static char buf[32];
2282
Stephen Hemminger132adf52007-03-08 20:44:43 -08002283 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002284 case RT_SCOPE_UNIVERSE: return "universe";
2285 case RT_SCOPE_SITE: return "site";
2286 case RT_SCOPE_LINK: return "link";
2287 case RT_SCOPE_HOST: return "host";
2288 case RT_SCOPE_NOWHERE: return "nowhere";
2289 default:
2290 snprintf(buf, sizeof(buf), "scope=%d", s);
2291 return buf;
2292 }
2293}
2294
2295static const char *rtn_type_names[__RTN_MAX] = {
2296 [RTN_UNSPEC] = "UNSPEC",
2297 [RTN_UNICAST] = "UNICAST",
2298 [RTN_LOCAL] = "LOCAL",
2299 [RTN_BROADCAST] = "BROADCAST",
2300 [RTN_ANYCAST] = "ANYCAST",
2301 [RTN_MULTICAST] = "MULTICAST",
2302 [RTN_BLACKHOLE] = "BLACKHOLE",
2303 [RTN_UNREACHABLE] = "UNREACHABLE",
2304 [RTN_PROHIBIT] = "PROHIBIT",
2305 [RTN_THROW] = "THROW",
2306 [RTN_NAT] = "NAT",
2307 [RTN_XRESOLVE] = "XRESOLVE",
2308};
2309
2310static inline const char *rtn_type(unsigned t)
2311{
2312 static char buf[32];
2313
2314 if (t < __RTN_MAX && rtn_type_names[t])
2315 return rtn_type_names[t];
2316 snprintf(buf, sizeof(buf), "type %d", t);
2317 return buf;
2318}
2319
2320/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002321static int fib_trie_seq_show(struct seq_file *seq, void *v)
2322{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002323 const struct fib_trie_iter *iter = seq->private;
2324 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002325
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002326 if (v == SEQ_START_TOKEN)
2327 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002328
Stephen Hemminger06801912007-08-10 15:22:13 -07002329 if (!node_parent(n)) {
Robert Olsson095b8502007-01-26 19:06:01 -08002330 if (iter->trie == trie_local)
2331 seq_puts(seq, "<local>:\n");
2332 else
2333 seq_puts(seq, "<main>:\n");
2334 }
2335
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002336 if (IS_TNODE(n)) {
2337 struct tnode *tn = (struct tnode *) n;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07002338 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002339
Robert Olsson1d25cd62005-09-19 15:29:52 -07002340 seq_indent(seq, iter->depth-1);
2341 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002342 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002343 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002344
Olof Johansson91b9a272005-08-09 20:24:39 -07002345 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002346 struct leaf *l = (struct leaf *) n;
2347 int i;
Al Viro32ab5f82006-09-26 22:21:45 -07002348 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002349
2350 seq_indent(seq, iter->depth);
2351 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
2352 for (i = 32; i >= 0; i--) {
Robert Olsson772cb712005-09-19 15:31:18 -07002353 struct leaf_info *li = find_leaf_info(l, i);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002354 if (li) {
2355 struct fib_alias *fa;
2356 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2357 seq_indent(seq, iter->depth+1);
2358 seq_printf(seq, " /%d %s %s", i,
2359 rtn_scope(fa->fa_scope),
2360 rtn_type(fa->fa_type));
2361 if (fa->fa_tos)
2362 seq_printf(seq, "tos =%d\n",
2363 fa->fa_tos);
2364 seq_putc(seq, '\n');
2365 }
2366 }
2367 }
Robert Olsson19baf832005-06-21 12:43:18 -07002368 }
2369
2370 return 0;
2371}
2372
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002373static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002374 .start = fib_trie_seq_start,
2375 .next = fib_trie_seq_next,
2376 .stop = fib_trie_seq_stop,
2377 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002378};
2379
2380static int fib_trie_seq_open(struct inode *inode, struct file *file)
2381{
Pavel Emelyanovcf7732e2007-10-10 02:29:29 -07002382 return seq_open_private(file, &fib_trie_seq_ops,
2383 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002384}
2385
Arjan van de Ven9a321442007-02-12 00:55:35 -08002386static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002387 .owner = THIS_MODULE,
2388 .open = fib_trie_seq_open,
2389 .read = seq_read,
2390 .llseek = seq_lseek,
2391 .release = seq_release_private,
2392};
2393
Al Viro32ab5f82006-09-26 22:21:45 -07002394static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002395{
2396 static unsigned type2flags[RTN_MAX + 1] = {
2397 [7] = RTF_REJECT, [8] = RTF_REJECT,
2398 };
2399 unsigned flags = type2flags[type];
2400
2401 if (fi && fi->fib_nh->nh_gw)
2402 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002403 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002404 flags |= RTF_HOST;
2405 flags |= RTF_UP;
2406 return flags;
2407}
2408
2409/*
2410 * This outputs /proc/net/route.
2411 * The format of the file is not supposed to be changed
2412 * and needs to be same as fib_hash output to avoid breaking
2413 * legacy utilities
2414 */
2415static int fib_route_seq_show(struct seq_file *seq, void *v)
2416{
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002417 const struct fib_trie_iter *iter = seq->private;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002418 struct leaf *l = v;
2419 int i;
2420 char bf[128];
2421
2422 if (v == SEQ_START_TOKEN) {
2423 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2424 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2425 "\tWindow\tIRTT");
2426 return 0;
2427 }
2428
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002429 if (iter->trie == trie_local)
2430 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002431 if (IS_TNODE(l))
2432 return 0;
2433
2434 for (i=32; i>=0; i--) {
Robert Olsson772cb712005-09-19 15:31:18 -07002435 struct leaf_info *li = find_leaf_info(l, i);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002436 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002437 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002438
2439 if (!li)
2440 continue;
2441
2442 mask = inet_make_mask(li->plen);
2443 prefix = htonl(l->key);
2444
2445 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002446 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002447 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2448
2449 if (fa->fa_type == RTN_BROADCAST
2450 || fa->fa_type == RTN_MULTICAST)
2451 continue;
2452
2453 if (fi)
2454 snprintf(bf, sizeof(bf),
2455 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2456 fi->fib_dev ? fi->fib_dev->name : "*",
2457 prefix,
2458 fi->fib_nh->nh_gw, flags, 0, 0,
2459 fi->fib_priority,
2460 mask,
2461 (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
2462 fi->fib_window,
2463 fi->fib_rtt >> 3);
2464 else
2465 snprintf(bf, sizeof(bf),
2466 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2467 prefix, 0, flags, 0, 0, 0,
2468 mask, 0, 0, 0);
2469
2470 seq_printf(seq, "%-127s\n", bf);
2471 }
2472 }
2473
2474 return 0;
2475}
2476
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002477static const struct seq_operations fib_route_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002478 .start = fib_trie_seq_start,
2479 .next = fib_trie_seq_next,
2480 .stop = fib_trie_seq_stop,
2481 .show = fib_route_seq_show,
2482};
2483
2484static int fib_route_seq_open(struct inode *inode, struct file *file)
2485{
Pavel Emelyanovcf7732e2007-10-10 02:29:29 -07002486 return seq_open_private(file, &fib_route_seq_ops,
2487 sizeof(struct fib_trie_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002488}
2489
Arjan van de Ven9a321442007-02-12 00:55:35 -08002490static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002491 .owner = THIS_MODULE,
2492 .open = fib_route_seq_open,
2493 .read = seq_read,
2494 .llseek = seq_lseek,
2495 .release = seq_release_private,
Robert Olsson19baf832005-06-21 12:43:18 -07002496};
2497
2498int __init fib_proc_init(void)
2499{
Eric W. Biederman457c4cb2007-09-12 12:01:34 +02002500 if (!proc_net_fops_create(&init_net, "fib_trie", S_IRUGO, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002501 goto out1;
2502
Eric W. Biederman457c4cb2007-09-12 12:01:34 +02002503 if (!proc_net_fops_create(&init_net, "fib_triestat", S_IRUGO, &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002504 goto out2;
2505
Eric W. Biederman457c4cb2007-09-12 12:01:34 +02002506 if (!proc_net_fops_create(&init_net, "route", S_IRUGO, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002507 goto out3;
2508
Robert Olsson19baf832005-06-21 12:43:18 -07002509 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002510
2511out3:
Eric W. Biederman457c4cb2007-09-12 12:01:34 +02002512 proc_net_remove(&init_net, "fib_triestat");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002513out2:
Eric W. Biederman457c4cb2007-09-12 12:01:34 +02002514 proc_net_remove(&init_net, "fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002515out1:
2516 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002517}
2518
2519void __init fib_proc_exit(void)
2520{
Eric W. Biederman457c4cb2007-09-12 12:01:34 +02002521 proc_net_remove(&init_net, "fib_trie");
2522 proc_net_remove(&init_net, "fib_triestat");
2523 proc_net_remove(&init_net, "route");
Robert Olsson19baf832005-06-21 12:43:18 -07002524}
2525
2526#endif /* CONFIG_PROC_FS */