blob: f5fba3f71c06e09283a29d48f2719bc9ad1be15b [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
Robert Olsson06ef9212006-03-20 21:35:01 -080085#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070086
Robert Olsson19baf832005-06-21 12:43:18 -070087#define KEYLENGTH (8*sizeof(t_key))
Robert Olsson19baf832005-06-21 12:43:18 -070088
Robert Olsson19baf832005-06-21 12:43:18 -070089typedef unsigned int t_key;
90
91#define T_TNODE 0
92#define T_LEAF 1
93#define NODE_TYPE_MASK 0x1UL
Robert Olsson2373ce12005-08-25 13:01:29 -070094#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
95
Olof Johansson91b9a272005-08-09 20:24:39 -070096#define IS_TNODE(n) (!(n->parent & T_LEAF))
97#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -070098
99struct node {
Olof Johansson91b9a272005-08-09 20:24:39 -0700100 unsigned long parent;
Eric Dumazet8d9654442008-01-13 22:31:44 -0800101 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700102};
103
104struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700105 unsigned long parent;
Eric Dumazet8d9654442008-01-13 22:31:44 -0800106 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700107 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700108 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700109};
110
111struct leaf_info {
112 struct hlist_node hlist;
Robert Olsson2373ce12005-08-25 13:01:29 -0700113 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700114 int plen;
115 struct list_head falh;
116};
117
118struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700119 unsigned long parent;
Eric Dumazet8d9654442008-01-13 22:31:44 -0800120 t_key key;
Eric Dumazet112d8cf2008-01-12 21:27:41 -0800121 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
122 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
Eric Dumazet8d9654442008-01-13 22:31:44 -0800123 unsigned int full_children; /* KEYLENGTH bits needed */
124 unsigned int empty_children; /* KEYLENGTH bits needed */
Robert Olsson2373ce12005-08-25 13:01:29 -0700125 struct rcu_head rcu;
Olof Johansson91b9a272005-08-09 20:24:39 -0700126 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700127};
128
129#ifdef CONFIG_IP_FIB_TRIE_STATS
130struct trie_use_stats {
131 unsigned int gets;
132 unsigned int backtrack;
133 unsigned int semantic_match_passed;
134 unsigned int semantic_match_miss;
135 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700136 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700137};
138#endif
139
140struct trie_stat {
141 unsigned int totdepth;
142 unsigned int maxdepth;
143 unsigned int tnodes;
144 unsigned int leaves;
145 unsigned int nullpointers;
Stephen Hemminger93672292008-01-22 21:54:05 -0800146 unsigned int prefixes;
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
Robert Olsson19baf832005-06-21 12:43:18 -0700155};
156
Robert Olsson19baf832005-06-21 12:43:18 -0700157static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800158static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
159 int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700160static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700161static struct tnode *inflate(struct trie *t, struct tnode *tn);
162static struct tnode *halve(struct trie *t, struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700163static void tnode_free(struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700164
Christoph Lametere18b8902006-12-06 20:33:20 -0800165static struct kmem_cache *fn_alias_kmem __read_mostly;
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800166static struct kmem_cache *trie_leaf_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700167
Stephen Hemminger06801912007-08-10 15:22:13 -0700168static inline struct tnode *node_parent(struct node *node)
169{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800170 return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
171}
Stephen Hemminger06801912007-08-10 15:22:13 -0700172
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800173static inline struct tnode *node_parent_rcu(struct node *node)
174{
175 struct tnode *ret = node_parent(node);
176
Stephen Hemminger06801912007-08-10 15:22:13 -0700177 return rcu_dereference(ret);
178}
179
180static inline void node_set_parent(struct node *node, struct tnode *ptr)
181{
182 rcu_assign_pointer(node->parent,
183 (unsigned long)ptr | NODE_TYPE(node));
184}
Robert Olsson2373ce12005-08-25 13:01:29 -0700185
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800186static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700187{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800188 BUG_ON(i >= 1U << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700189
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800190 return tn->child[i];
191}
192
193static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
194{
195 struct node *ret = tnode_get_child(tn, i);
196
197 return rcu_dereference(ret);
Robert Olsson19baf832005-06-21 12:43:18 -0700198}
199
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700200static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700201{
Olof Johansson91b9a272005-08-09 20:24:39 -0700202 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700203}
204
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700205static inline t_key mask_pfx(t_key k, unsigned short l)
206{
207 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
208}
209
Robert Olsson19baf832005-06-21 12:43:18 -0700210static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
211{
Olof Johansson91b9a272005-08-09 20:24:39 -0700212 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700213 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700214 else
Robert Olsson19baf832005-06-21 12:43:18 -0700215 return 0;
216}
217
218static inline int tkey_equals(t_key a, t_key b)
219{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700220 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700221}
222
223static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
224{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700225 if (bits == 0 || offset >= KEYLENGTH)
226 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700227 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
228 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700229}
Robert Olsson19baf832005-06-21 12:43:18 -0700230
231static inline int tkey_mismatch(t_key a, int offset, t_key b)
232{
233 t_key diff = a ^ b;
234 int i = offset;
235
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700236 if (!diff)
237 return 0;
238 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700239 i++;
240 return i;
241}
242
Robert Olsson19baf832005-06-21 12:43:18 -0700243/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900244 To understand this stuff, an understanding of keys and all their bits is
245 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700246 all of the bits in that key are significant.
247
248 Consider a node 'n' and its parent 'tp'.
249
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900250 If n is a leaf, every bit in its key is significant. Its presence is
251 necessitated by path compression, since during a tree traversal (when
252 searching for a leaf - unless we are doing an insertion) we will completely
253 ignore all skipped bits we encounter. Thus we need to verify, at the end of
254 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700255 correct key path.
256
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900257 Note that we can never "miss" the correct key in the tree if present by
258 following the wrong path. Path compression ensures that segments of the key
259 that are the same for all keys with a given prefix are skipped, but the
260 skipped part *is* identical for each node in the subtrie below the skipped
261 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700262 call to tkey_sub_equals() in trie_insert().
263
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900264 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700265 have many different meanings.
266
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900267 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700268 _________________________________________________________________
269 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
270 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900271 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700272
273 _________________________________________________________________
274 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
275 -----------------------------------------------------------------
276 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
277
278 tp->pos = 7
279 tp->bits = 3
280 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700281 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700282
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900283 First, let's just ignore the bits that come before the parent tp, that is
284 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700285 not use them for anything.
286
287 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900288 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700289 'n' among tp's children.
290
291 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
292 for the node n.
293
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900294 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700295 of the bits are really not needed or indeed known in n->key.
296
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900297 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700298 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900299
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700300
Robert Olsson19baf832005-06-21 12:43:18 -0700301 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
302 at this point.
303
304*/
305
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700306static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700307{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700308 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700309}
310
Denis V. Lunevf5026fa2007-12-13 09:47:57 -0800311static const int halve_threshold = 25;
312static const int inflate_threshold = 50;
313static const int halve_threshold_root = 8;
314static const int inflate_threshold_root = 15;
Robert Olsson19baf832005-06-21 12:43:18 -0700315
Robert Olsson2373ce12005-08-25 13:01:29 -0700316
317static void __alias_free_mem(struct rcu_head *head)
318{
319 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
320 kmem_cache_free(fn_alias_kmem, fa);
321}
322
323static inline void alias_free_mem_rcu(struct fib_alias *fa)
324{
325 call_rcu(&fa->rcu, __alias_free_mem);
326}
327
328static void __leaf_free_rcu(struct rcu_head *head)
329{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800330 struct leaf *l = container_of(head, struct leaf, rcu);
331 kmem_cache_free(trie_leaf_kmem, l);
Robert Olsson2373ce12005-08-25 13:01:29 -0700332}
333
Robert Olsson2373ce12005-08-25 13:01:29 -0700334static void __leaf_info_free_rcu(struct rcu_head *head)
335{
336 kfree(container_of(head, struct leaf_info, rcu));
337}
338
339static inline void free_leaf_info(struct leaf_info *leaf)
340{
341 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
342}
343
Eric Dumazet8d9654442008-01-13 22:31:44 -0800344static struct tnode *tnode_alloc(size_t size)
Robert Olsson2373ce12005-08-25 13:01:29 -0700345{
346 struct page *pages;
347
348 if (size <= PAGE_SIZE)
Eric Dumazet8d9654442008-01-13 22:31:44 -0800349 return kzalloc(size, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700350
351 pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
352 if (!pages)
353 return NULL;
354
355 return page_address(pages);
356}
357
358static void __tnode_free_rcu(struct rcu_head *head)
359{
360 struct tnode *tn = container_of(head, struct tnode, rcu);
Eric Dumazet8d9654442008-01-13 22:31:44 -0800361 size_t size = sizeof(struct tnode) +
362 (sizeof(struct node *) << tn->bits);
Robert Olsson2373ce12005-08-25 13:01:29 -0700363
364 if (size <= PAGE_SIZE)
365 kfree(tn);
366 else
367 free_pages((unsigned long)tn, get_order(size));
368}
369
370static inline void tnode_free(struct tnode *tn)
371{
Stephen Hemminger132adf52007-03-08 20:44:43 -0800372 if (IS_LEAF(tn)) {
Robert Olsson550e29b2006-04-04 12:53:35 -0700373 struct leaf *l = (struct leaf *) tn;
374 call_rcu_bh(&l->rcu, __leaf_free_rcu);
Stephen Hemminger132adf52007-03-08 20:44:43 -0800375 } else
Robert Olsson550e29b2006-04-04 12:53:35 -0700376 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700377}
378
Robert Olsson19baf832005-06-21 12:43:18 -0700379static struct leaf *leaf_new(void)
380{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800381 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700382 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700383 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700384 INIT_HLIST_HEAD(&l->list);
385 }
386 return l;
387}
388
389static struct leaf_info *leaf_info_new(int plen)
390{
391 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700392 if (li) {
393 li->plen = plen;
394 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700395 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700396 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700397}
398
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800399static struct tnode *tnode_new(t_key key, int pos, int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700400{
Eric Dumazet8d9654442008-01-13 22:31:44 -0800401 size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700402 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700403
Olof Johansson91b9a272005-08-09 20:24:39 -0700404 if (tn) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700405 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700406 tn->pos = pos;
407 tn->bits = bits;
408 tn->key = key;
409 tn->full_children = 0;
410 tn->empty_children = 1<<bits;
411 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700412
Eric Dumazet8d9654442008-01-13 22:31:44 -0800413 pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
414 (unsigned long) (sizeof(struct node) << bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700415 return tn;
416}
417
Robert Olsson19baf832005-06-21 12:43:18 -0700418/*
419 * Check whether a tnode 'n' is "full", i.e. it is an internal node
420 * and no bits are skipped. See discussion in dyntree paper p. 6
421 */
422
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700423static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700424{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700425 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700426 return 0;
427
428 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
429}
430
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800431static inline void put_child(struct trie *t, struct tnode *tn, int i,
432 struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700433{
434 tnode_put_child_reorg(tn, i, n, -1);
435}
436
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700437 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700438 * Add a child at position i overwriting the old value.
439 * Update the value of full_children and empty_children.
440 */
441
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800442static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
443 int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700444{
Robert Olsson2373ce12005-08-25 13:01:29 -0700445 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700446 int isfull;
447
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700448 BUG_ON(i >= 1<<tn->bits);
449
Robert Olsson19baf832005-06-21 12:43:18 -0700450 /* update emptyChildren */
451 if (n == NULL && chi != NULL)
452 tn->empty_children++;
453 else if (n != NULL && chi == NULL)
454 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700455
Robert Olsson19baf832005-06-21 12:43:18 -0700456 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700457 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700458 wasfull = tnode_full(tn, chi);
459
460 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700461 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700462 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700463 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700464 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700465
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700466 if (n)
Stephen Hemminger06801912007-08-10 15:22:13 -0700467 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700468
Robert Olsson2373ce12005-08-25 13:01:29 -0700469 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700470}
471
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700472static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700473{
474 int i;
Robert Olsson2f368952005-07-05 15:02:40 -0700475 int err = 0;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700476 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700477 int inflate_threshold_use;
478 int halve_threshold_use;
Robert Olsson05eee482007-03-19 16:27:37 -0700479 int max_resize;
Robert Olsson19baf832005-06-21 12:43:18 -0700480
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900481 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700482 return NULL;
483
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700484 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
485 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700486
487 /* No children */
488 if (tn->empty_children == tnode_child_length(tn)) {
489 tnode_free(tn);
490 return NULL;
491 }
492 /* One child */
493 if (tn->empty_children == tnode_child_length(tn) - 1)
494 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700495 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700496
Olof Johansson91b9a272005-08-09 20:24:39 -0700497 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700498 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700499 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700500
501 /* compress one level */
Stephen Hemminger06801912007-08-10 15:22:13 -0700502 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700503 tnode_free(tn);
504 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700505 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700506 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700507 * Double as long as the resulting node has a number of
508 * nonempty nodes that are above the threshold.
509 */
510
511 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700512 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
513 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700514 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700515 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700516 * children in the *doubled* node is at least 'high'."
517 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700518 * 'high' in this instance is the variable 'inflate_threshold'. It
519 * is expressed as a percentage, so we multiply it with
520 * tnode_child_length() and instead of multiplying by 2 (since the
521 * child array will be doubled by inflate()) and multiplying
522 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700523 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700524 *
525 * The left-hand side may look a bit weird: tnode_child_length(tn)
526 * - tn->empty_children is of course the number of non-null children
527 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700528 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700529 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700530 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700531 *
Robert Olsson19baf832005-06-21 12:43:18 -0700532 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700533 *
Robert Olsson19baf832005-06-21 12:43:18 -0700534 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700535 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700536 * tn->full_children;
537 *
538 * new_child_length = tnode_child_length(tn) * 2;
539 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700540 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700541 * new_child_length;
542 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700543 *
544 * ...and so on, tho it would mess up the while () loop.
545 *
Robert Olsson19baf832005-06-21 12:43:18 -0700546 * anyway,
547 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
548 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700549 *
Robert Olsson19baf832005-06-21 12:43:18 -0700550 * avoid a division:
551 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
552 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700553 *
Robert Olsson19baf832005-06-21 12:43:18 -0700554 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700555 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700556 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700557 *
Robert Olsson19baf832005-06-21 12:43:18 -0700558 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700559 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700560 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700561 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700562 *
Robert Olsson19baf832005-06-21 12:43:18 -0700563 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700564 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700565 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700566 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700567 *
Robert Olsson19baf832005-06-21 12:43:18 -0700568 */
569
570 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700571
Robert Olssone6308be2005-10-04 13:01:58 -0700572 /* Keep root node larger */
573
Stephen Hemminger132adf52007-03-08 20:44:43 -0800574 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700575 inflate_threshold_use = inflate_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900576 else
Robert Olssone6308be2005-10-04 13:01:58 -0700577 inflate_threshold_use = inflate_threshold;
578
Robert Olsson2f368952005-07-05 15:02:40 -0700579 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700580 max_resize = 10;
581 while ((tn->full_children > 0 && max_resize-- &&
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800582 50 * (tn->full_children + tnode_child_length(tn)
583 - tn->empty_children)
584 >= inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700585
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700586 old_tn = tn;
587 tn = inflate(t, tn);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800588
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700589 if (IS_ERR(tn)) {
590 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700591#ifdef CONFIG_IP_FIB_TRIE_STATS
592 t->stats.resize_node_skipped++;
593#endif
594 break;
595 }
Robert Olsson19baf832005-06-21 12:43:18 -0700596 }
597
Robert Olsson05eee482007-03-19 16:27:37 -0700598 if (max_resize < 0) {
599 if (!tn->parent)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800600 pr_warning("Fix inflate_threshold_root."
601 " Now=%d size=%d bits\n",
602 inflate_threshold_root, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700603 else
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800604 pr_warning("Fix inflate_threshold."
605 " Now=%d size=%d bits\n",
606 inflate_threshold, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700607 }
608
Robert Olsson19baf832005-06-21 12:43:18 -0700609 check_tnode(tn);
610
611 /*
612 * Halve as long as the number of empty children in this
613 * node is above threshold.
614 */
Robert Olsson2f368952005-07-05 15:02:40 -0700615
Robert Olssone6308be2005-10-04 13:01:58 -0700616
617 /* Keep root node larger */
618
Stephen Hemminger132adf52007-03-08 20:44:43 -0800619 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700620 halve_threshold_use = halve_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900621 else
Robert Olssone6308be2005-10-04 13:01:58 -0700622 halve_threshold_use = halve_threshold;
623
Robert Olsson2f368952005-07-05 15:02:40 -0700624 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700625 max_resize = 10;
626 while (tn->bits > 1 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700627 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700628 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700629
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700630 old_tn = tn;
631 tn = halve(t, tn);
632 if (IS_ERR(tn)) {
633 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700634#ifdef CONFIG_IP_FIB_TRIE_STATS
635 t->stats.resize_node_skipped++;
636#endif
637 break;
638 }
639 }
640
Robert Olsson05eee482007-03-19 16:27:37 -0700641 if (max_resize < 0) {
642 if (!tn->parent)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800643 pr_warning("Fix halve_threshold_root."
644 " Now=%d size=%d bits\n",
645 halve_threshold_root, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700646 else
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800647 pr_warning("Fix halve_threshold."
648 " Now=%d size=%d bits\n",
649 halve_threshold, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700650 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700651
Robert Olsson19baf832005-06-21 12:43:18 -0700652 /* Only one child remains */
Robert Olsson19baf832005-06-21 12:43:18 -0700653 if (tn->empty_children == tnode_child_length(tn) - 1)
654 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700655 struct node *n;
656
Olof Johansson91b9a272005-08-09 20:24:39 -0700657 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700658 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700659 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700660
661 /* compress one level */
662
Stephen Hemminger06801912007-08-10 15:22:13 -0700663 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700664 tnode_free(tn);
665 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700666 }
667
668 return (struct node *) tn;
669}
670
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700671static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700672{
Robert Olsson19baf832005-06-21 12:43:18 -0700673 struct tnode *oldtnode = tn;
674 int olen = tnode_child_length(tn);
675 int i;
676
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700677 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700678
679 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
680
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700681 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700682 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700683
684 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700685 * Preallocate and store tnodes before the actual work so we
686 * don't get into an inconsistent state if memory allocation
687 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700688 * of tnode is ignored.
689 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700690
691 for (i = 0; i < olen; i++) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800692 struct tnode *inode;
Robert Olsson2f368952005-07-05 15:02:40 -0700693
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800694 inode = (struct tnode *) tnode_get_child(oldtnode, i);
Robert Olsson2f368952005-07-05 15:02:40 -0700695 if (inode &&
696 IS_TNODE(inode) &&
697 inode->pos == oldtnode->pos + oldtnode->bits &&
698 inode->bits > 1) {
699 struct tnode *left, *right;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700700 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700701
Robert Olsson2f368952005-07-05 15:02:40 -0700702 left = tnode_new(inode->key&(~m), inode->pos + 1,
703 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700704 if (!left)
705 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700706
Robert Olsson2f368952005-07-05 15:02:40 -0700707 right = tnode_new(inode->key|m, inode->pos + 1,
708 inode->bits - 1);
709
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900710 if (!right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700711 tnode_free(left);
712 goto nomem;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900713 }
Robert Olsson2f368952005-07-05 15:02:40 -0700714
715 put_child(t, tn, 2*i, (struct node *) left);
716 put_child(t, tn, 2*i+1, (struct node *) right);
717 }
718 }
719
Olof Johansson91b9a272005-08-09 20:24:39 -0700720 for (i = 0; i < olen; i++) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -0800721 struct tnode *inode;
Robert Olsson19baf832005-06-21 12:43:18 -0700722 struct node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700723 struct tnode *left, *right;
724 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700725
Robert Olsson19baf832005-06-21 12:43:18 -0700726 /* An empty child */
727 if (node == NULL)
728 continue;
729
730 /* A leaf or an internal node with skipped bits */
731
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700732 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700733 tn->pos + tn->bits - 1) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800734 if (tkey_extract_bits(node->key,
735 oldtnode->pos + oldtnode->bits,
736 1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700737 put_child(t, tn, 2*i, node);
738 else
739 put_child(t, tn, 2*i+1, node);
740 continue;
741 }
742
743 /* An internal node with two children */
744 inode = (struct tnode *) node;
745
746 if (inode->bits == 1) {
747 put_child(t, tn, 2*i, inode->child[0]);
748 put_child(t, tn, 2*i+1, inode->child[1]);
749
750 tnode_free(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700751 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700752 }
753
Olof Johansson91b9a272005-08-09 20:24:39 -0700754 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700755
Olof Johansson91b9a272005-08-09 20:24:39 -0700756 /* We will replace this node 'inode' with two new
757 * ones, 'left' and 'right', each with half of the
758 * original children. The two new nodes will have
759 * a position one bit further down the key and this
760 * means that the "significant" part of their keys
761 * (see the discussion near the top of this file)
762 * will differ by one bit, which will be "0" in
763 * left's key and "1" in right's key. Since we are
764 * moving the key position by one step, the bit that
765 * we are moving away from - the bit at position
766 * (inode->pos) - is the one that will differ between
767 * left and right. So... we synthesize that bit in the
768 * two new keys.
769 * The mask 'm' below will be a single "one" bit at
770 * the position (inode->pos)
771 */
Robert Olsson19baf832005-06-21 12:43:18 -0700772
Olof Johansson91b9a272005-08-09 20:24:39 -0700773 /* Use the old key, but set the new significant
774 * bit to zero.
775 */
Robert Olsson19baf832005-06-21 12:43:18 -0700776
Olof Johansson91b9a272005-08-09 20:24:39 -0700777 left = (struct tnode *) tnode_get_child(tn, 2*i);
778 put_child(t, tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700779
Olof Johansson91b9a272005-08-09 20:24:39 -0700780 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700781
Olof Johansson91b9a272005-08-09 20:24:39 -0700782 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
783 put_child(t, tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700784
Olof Johansson91b9a272005-08-09 20:24:39 -0700785 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700786
Olof Johansson91b9a272005-08-09 20:24:39 -0700787 size = tnode_child_length(left);
788 for (j = 0; j < size; j++) {
789 put_child(t, left, j, inode->child[j]);
790 put_child(t, right, j, inode->child[j + size]);
Robert Olsson19baf832005-06-21 12:43:18 -0700791 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700792 put_child(t, tn, 2*i, resize(t, left));
793 put_child(t, tn, 2*i+1, resize(t, right));
794
795 tnode_free(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700796 }
797 tnode_free(oldtnode);
798 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700799nomem:
800 {
801 int size = tnode_child_length(tn);
802 int j;
803
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700804 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700805 if (tn->child[j])
806 tnode_free((struct tnode *)tn->child[j]);
807
808 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700809
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700810 return ERR_PTR(-ENOMEM);
811 }
Robert Olsson19baf832005-06-21 12:43:18 -0700812}
813
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700814static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700815{
816 struct tnode *oldtnode = tn;
817 struct node *left, *right;
818 int i;
819 int olen = tnode_child_length(tn);
820
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700821 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700822
823 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700824
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700825 if (!tn)
826 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700827
828 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700829 * Preallocate and store tnodes before the actual work so we
830 * don't get into an inconsistent state if memory allocation
831 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700832 * of tnode is ignored.
833 */
834
Olof Johansson91b9a272005-08-09 20:24:39 -0700835 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700836 left = tnode_get_child(oldtnode, i);
837 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700838
Robert Olsson2f368952005-07-05 15:02:40 -0700839 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700840 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700841 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700842
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700843 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700844
845 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700846 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700847
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700848 put_child(t, tn, i/2, (struct node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700849 }
Robert Olsson2f368952005-07-05 15:02:40 -0700850
Robert Olsson2f368952005-07-05 15:02:40 -0700851 }
Robert Olsson19baf832005-06-21 12:43:18 -0700852
Olof Johansson91b9a272005-08-09 20:24:39 -0700853 for (i = 0; i < olen; i += 2) {
854 struct tnode *newBinNode;
855
Robert Olsson19baf832005-06-21 12:43:18 -0700856 left = tnode_get_child(oldtnode, i);
857 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700858
Robert Olsson19baf832005-06-21 12:43:18 -0700859 /* At least one of the children is empty */
860 if (left == NULL) {
861 if (right == NULL) /* Both are empty */
862 continue;
863 put_child(t, tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700864 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700865 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700866
867 if (right == NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700868 put_child(t, tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700869 continue;
870 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700871
Robert Olsson19baf832005-06-21 12:43:18 -0700872 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700873 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
874 put_child(t, tn, i/2, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700875 put_child(t, newBinNode, 0, left);
876 put_child(t, newBinNode, 1, right);
877 put_child(t, tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700878 }
879 tnode_free(oldtnode);
880 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700881nomem:
882 {
883 int size = tnode_child_length(tn);
884 int j;
885
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700886 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700887 if (tn->child[j])
888 tnode_free((struct tnode *)tn->child[j]);
889
890 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700891
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700892 return ERR_PTR(-ENOMEM);
893 }
Robert Olsson19baf832005-06-21 12:43:18 -0700894}
895
Robert Olsson772cb712005-09-19 15:31:18 -0700896/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700897 via get_fa_head and dump */
898
Robert Olsson772cb712005-09-19 15:31:18 -0700899static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700900{
Robert Olsson772cb712005-09-19 15:31:18 -0700901 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700902 struct hlist_node *node;
903 struct leaf_info *li;
904
Robert Olsson2373ce12005-08-25 13:01:29 -0700905 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700906 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700907 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700908
Robert Olsson19baf832005-06-21 12:43:18 -0700909 return NULL;
910}
911
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800912static inline struct list_head *get_fa_head(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700913{
Robert Olsson772cb712005-09-19 15:31:18 -0700914 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700915
Olof Johansson91b9a272005-08-09 20:24:39 -0700916 if (!li)
917 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700918
Olof Johansson91b9a272005-08-09 20:24:39 -0700919 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700920}
921
922static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
923{
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900924 struct leaf_info *li = NULL, *last = NULL;
925 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700926
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900927 if (hlist_empty(head)) {
928 hlist_add_head_rcu(&new->hlist, head);
929 } else {
930 hlist_for_each_entry(li, node, head, hlist) {
931 if (new->plen > li->plen)
932 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700933
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900934 last = li;
935 }
936 if (last)
937 hlist_add_after_rcu(&last->hlist, &new->hlist);
938 else
939 hlist_add_before_rcu(&new->hlist, &li->hlist);
940 }
Robert Olsson19baf832005-06-21 12:43:18 -0700941}
942
Robert Olsson2373ce12005-08-25 13:01:29 -0700943/* rcu_read_lock needs to be hold by caller from readside */
944
Robert Olsson19baf832005-06-21 12:43:18 -0700945static struct leaf *
946fib_find_node(struct trie *t, u32 key)
947{
948 int pos;
949 struct tnode *tn;
950 struct node *n;
951
952 pos = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700953 n = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700954
955 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
956 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700957
Robert Olsson19baf832005-06-21 12:43:18 -0700958 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700959
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700960 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700961 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800962 n = tnode_get_child_rcu(tn,
963 tkey_extract_bits(key,
964 tn->pos,
965 tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700966 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700967 break;
968 }
969 /* Case we have found a leaf. Compare prefixes */
970
Olof Johansson91b9a272005-08-09 20:24:39 -0700971 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
972 return (struct leaf *)n;
973
Robert Olsson19baf832005-06-21 12:43:18 -0700974 return NULL;
975}
976
977static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
978{
Robert Olsson19baf832005-06-21 12:43:18 -0700979 int wasfull;
Stephen Hemminger06801912007-08-10 15:22:13 -0700980 t_key cindex, key = tn->key;
981 struct tnode *tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700982
Stephen Hemminger06801912007-08-10 15:22:13 -0700983 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700984 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
985 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800986 tn = (struct tnode *) resize(t, (struct tnode *)tn);
987
988 tnode_put_child_reorg((struct tnode *)tp, cindex,
989 (struct node *)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -0700990
Stephen Hemminger06801912007-08-10 15:22:13 -0700991 tp = node_parent((struct node *) tn);
992 if (!tp)
Robert Olsson19baf832005-06-21 12:43:18 -0700993 break;
Stephen Hemminger06801912007-08-10 15:22:13 -0700994 tn = tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700995 }
Stephen Hemminger06801912007-08-10 15:22:13 -0700996
Robert Olsson19baf832005-06-21 12:43:18 -0700997 /* Handle last (top) tnode */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700998 if (IS_TNODE(tn))
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800999 tn = (struct tnode *)resize(t, (struct tnode *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001000
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001001 return (struct node *)tn;
Robert Olsson19baf832005-06-21 12:43:18 -07001002}
1003
Robert Olsson2373ce12005-08-25 13:01:29 -07001004/* only used from updater-side */
1005
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001006static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -07001007{
1008 int pos, newpos;
1009 struct tnode *tp = NULL, *tn = NULL;
1010 struct node *n;
1011 struct leaf *l;
1012 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001013 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001014 struct leaf_info *li;
1015 t_key cindex;
1016
1017 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001018 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001019
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001020 /* If we point to NULL, stop. Either the tree is empty and we should
1021 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001022 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001023 * If we point to a T_TNODE, check if it matches our key. Note that
1024 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001025 * not be the parent's 'pos'+'bits'!
1026 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001027 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001028 * the index from our key, push the T_TNODE and walk the tree.
1029 *
1030 * If it doesn't, we have to replace it with a new T_TNODE.
1031 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001032 * If we point to a T_LEAF, it might or might not have the same key
1033 * as we do. If it does, just change the value, update the T_LEAF's
1034 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001035 * If it doesn't, we need to replace it with a T_TNODE.
1036 */
1037
1038 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1039 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001040
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001041 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001042
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001043 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001044 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001045 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001046 n = tnode_get_child(tn,
1047 tkey_extract_bits(key,
1048 tn->pos,
1049 tn->bits));
Robert Olsson19baf832005-06-21 12:43:18 -07001050
Stephen Hemminger06801912007-08-10 15:22:13 -07001051 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001052 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001053 break;
1054 }
1055
1056 /*
1057 * n ----> NULL, LEAF or TNODE
1058 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001059 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001060 */
1061
Olof Johansson91b9a272005-08-09 20:24:39 -07001062 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001063
1064 /* Case 1: n is a leaf. Compare prefixes */
1065
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001066 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08001067 l = (struct leaf *) n;
Robert Olsson19baf832005-06-21 12:43:18 -07001068 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001069
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001070 if (!li)
1071 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001072
1073 fa_head = &li->falh;
1074 insert_leaf_info(&l->list, li);
1075 goto done;
1076 }
Robert Olsson19baf832005-06-21 12:43:18 -07001077 l = leaf_new();
1078
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001079 if (!l)
1080 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001081
1082 l->key = key;
1083 li = leaf_info_new(plen);
1084
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001085 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001086 tnode_free((struct tnode *) l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001087 return NULL;
Robert Olssonf835e472005-06-28 15:00:39 -07001088 }
Robert Olsson19baf832005-06-21 12:43:18 -07001089
1090 fa_head = &li->falh;
1091 insert_leaf_info(&l->list, li);
1092
Robert Olsson19baf832005-06-21 12:43:18 -07001093 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001094 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001095
Stephen Hemminger06801912007-08-10 15:22:13 -07001096 node_set_parent((struct node *)l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001097
Olof Johansson91b9a272005-08-09 20:24:39 -07001098 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1099 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1100 } else {
1101 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001102 /*
1103 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001104 * first tnode need some special handling
1105 */
1106
1107 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001108 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001109 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001110 pos = 0;
1111
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001112 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001113 newpos = tkey_mismatch(key, pos, n->key);
1114 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001115 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001116 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001117 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001118 }
Robert Olsson19baf832005-06-21 12:43:18 -07001119
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001120 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001121 free_leaf_info(li);
1122 tnode_free((struct tnode *) l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001123 return NULL;
Olof Johansson91b9a272005-08-09 20:24:39 -07001124 }
1125
Stephen Hemminger06801912007-08-10 15:22:13 -07001126 node_set_parent((struct node *)tn, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001127
Olof Johansson91b9a272005-08-09 20:24:39 -07001128 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001129 put_child(t, tn, missbit, (struct node *)l);
1130 put_child(t, tn, 1-missbit, n);
1131
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001132 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001133 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001134 put_child(t, (struct tnode *)tp, cindex,
1135 (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001136 } else {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001137 rcu_assign_pointer(t->trie, (struct node *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001138 tp = tn;
1139 }
1140 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001141
1142 if (tp && tp->pos + tp->bits > 32)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001143 pr_warning("fib_trie"
1144 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1145 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001146
Robert Olsson19baf832005-06-21 12:43:18 -07001147 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001148
1149 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Robert Olssonf835e472005-06-28 15:00:39 -07001150done:
Robert Olsson19baf832005-06-21 12:43:18 -07001151 return fa_head;
1152}
1153
Robert Olssond562f1f2007-03-26 14:22:22 -07001154/*
1155 * Caller must hold RTNL.
1156 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001157static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001158{
1159 struct trie *t = (struct trie *) tb->tb_data;
1160 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001161 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001162 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001163 int plen = cfg->fc_dst_len;
1164 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001165 u32 key, mask;
1166 int err;
1167 struct leaf *l;
1168
1169 if (plen > 32)
1170 return -EINVAL;
1171
Thomas Graf4e902c52006-08-17 18:14:52 -07001172 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001173
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001174 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001175
Olof Johansson91b9a272005-08-09 20:24:39 -07001176 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001177
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001178 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001179 return -EINVAL;
1180
1181 key = key & mask;
1182
Thomas Graf4e902c52006-08-17 18:14:52 -07001183 fi = fib_create_info(cfg);
1184 if (IS_ERR(fi)) {
1185 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001186 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001187 }
Robert Olsson19baf832005-06-21 12:43:18 -07001188
1189 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001190 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001191
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001192 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001193 fa_head = get_fa_head(l, plen);
1194 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1195 }
1196
1197 /* Now fa, if non-NULL, points to the first fib alias
1198 * with the same keys [prefix,tos,priority], if such key already
1199 * exists or to the node before which we will insert new one.
1200 *
1201 * If fa is NULL, we will need to allocate a new one and
1202 * insert to the head of f.
1203 *
1204 * If f is NULL, no fib node matched the destination key
1205 * and we need to allocate a new one of those as well.
1206 */
1207
Julian Anastasov936f6f82008-01-28 21:18:06 -08001208 if (fa && fa->fa_tos == tos &&
1209 fa->fa_info->fib_priority == fi->fib_priority) {
1210 struct fib_alias *fa_first, *fa_match;
Robert Olsson19baf832005-06-21 12:43:18 -07001211
1212 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001213 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001214 goto out;
1215
Julian Anastasov936f6f82008-01-28 21:18:06 -08001216 /* We have 2 goals:
1217 * 1. Find exact match for type, scope, fib_info to avoid
1218 * duplicate routes
1219 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1220 */
1221 fa_match = NULL;
1222 fa_first = fa;
1223 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1224 list_for_each_entry_continue(fa, fa_head, fa_list) {
1225 if (fa->fa_tos != tos)
1226 break;
1227 if (fa->fa_info->fib_priority != fi->fib_priority)
1228 break;
1229 if (fa->fa_type == cfg->fc_type &&
1230 fa->fa_scope == cfg->fc_scope &&
1231 fa->fa_info == fi) {
1232 fa_match = fa;
1233 break;
1234 }
1235 }
1236
Thomas Graf4e902c52006-08-17 18:14:52 -07001237 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001238 struct fib_info *fi_drop;
1239 u8 state;
1240
Julian Anastasov936f6f82008-01-28 21:18:06 -08001241 fa = fa_first;
1242 if (fa_match) {
1243 if (fa == fa_match)
1244 err = 0;
Joonwoo Park67250332008-01-18 03:45:18 -08001245 goto out;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001246 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001247 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001248 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001249 if (new_fa == NULL)
1250 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001251
1252 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001253 new_fa->fa_tos = fa->fa_tos;
1254 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001255 new_fa->fa_type = cfg->fc_type;
1256 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001257 state = fa->fa_state;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001258 new_fa->fa_state = state & ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001259
Robert Olsson2373ce12005-08-25 13:01:29 -07001260 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1261 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001262
1263 fib_release_info(fi_drop);
1264 if (state & FA_S_ACCESSED)
Olof Johansson91b9a272005-08-09 20:24:39 -07001265 rt_cache_flush(-1);
Milan Kocianb8f55832007-05-23 14:55:06 -07001266 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1267 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001268
Olof Johansson91b9a272005-08-09 20:24:39 -07001269 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001270 }
1271 /* Error if we find a perfect match which
1272 * uses the same scope, type, and nexthop
1273 * information.
1274 */
Julian Anastasov936f6f82008-01-28 21:18:06 -08001275 if (fa_match)
1276 goto out;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001277
Thomas Graf4e902c52006-08-17 18:14:52 -07001278 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001279 fa = fa_first;
Robert Olsson19baf832005-06-21 12:43:18 -07001280 }
1281 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001282 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001283 goto out;
1284
1285 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001286 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001287 if (new_fa == NULL)
1288 goto out;
1289
1290 new_fa->fa_info = fi;
1291 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001292 new_fa->fa_type = cfg->fc_type;
1293 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001294 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001295 /*
1296 * Insert new entry to the list.
1297 */
1298
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001299 if (!fa_head) {
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001300 fa_head = fib_insert_node(t, key, plen);
1301 if (unlikely(!fa_head)) {
1302 err = -ENOMEM;
Robert Olssonf835e472005-06-28 15:00:39 -07001303 goto out_free_new_fa;
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001304 }
Robert Olssonf835e472005-06-28 15:00:39 -07001305 }
Robert Olsson19baf832005-06-21 12:43:18 -07001306
Robert Olsson2373ce12005-08-25 13:01:29 -07001307 list_add_tail_rcu(&new_fa->fa_list,
1308 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001309
1310 rt_cache_flush(-1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001311 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001312 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001313succeeded:
1314 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001315
1316out_free_new_fa:
1317 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001318out:
1319 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001320err:
Robert Olsson19baf832005-06-21 12:43:18 -07001321 return err;
1322}
1323
Robert Olsson772cb712005-09-19 15:31:18 -07001324/* should be called with rcu_read_lock */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001325static int check_leaf(struct trie *t, struct leaf *l,
1326 t_key key, const struct flowi *flp,
1327 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001328{
Robert Olsson19baf832005-06-21 12:43:18 -07001329 struct leaf_info *li;
1330 struct hlist_head *hhead = &l->list;
1331 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001332
Robert Olsson2373ce12005-08-25 13:01:29 -07001333 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001334 int err;
1335 int plen = li->plen;
1336 __be32 mask = inet_make_mask(plen);
1337
Al Viro888454c2006-09-19 13:42:46 -07001338 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001339 continue;
1340
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001341 err = fib_semantic_match(&li->falh, flp, res,
1342 htonl(l->key), mask, plen);
1343
Robert Olsson19baf832005-06-21 12:43:18 -07001344#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001345 if (err <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001346 t->stats.semantic_match_passed++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001347 else
1348 t->stats.semantic_match_miss++;
Robert Olsson19baf832005-06-21 12:43:18 -07001349#endif
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001350 if (err <= 0)
1351 return plen;
Robert Olsson19baf832005-06-21 12:43:18 -07001352 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001353
1354 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001355}
1356
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001357static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
1358 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001359{
1360 struct trie *t = (struct trie *) tb->tb_data;
1361 int plen, ret = 0;
1362 struct node *n;
1363 struct tnode *pn;
1364 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001365 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001366 int chopped_off;
1367 t_key cindex = 0;
1368 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001369 struct tnode *cn;
1370 t_key node_prefix, key_prefix, pref_mismatch;
1371 int mp;
1372
Robert Olsson2373ce12005-08-25 13:01:29 -07001373 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001374
Robert Olsson2373ce12005-08-25 13:01:29 -07001375 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001376 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001377 goto failed;
1378
1379#ifdef CONFIG_IP_FIB_TRIE_STATS
1380 t->stats.gets++;
1381#endif
1382
1383 /* Just a leaf? */
1384 if (IS_LEAF(n)) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001385 plen = check_leaf(t, (struct leaf *)n, key, flp, res);
1386 if (plen < 0)
1387 goto failed;
1388 ret = 0;
1389 goto found;
Robert Olsson19baf832005-06-21 12:43:18 -07001390 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001391
Robert Olsson19baf832005-06-21 12:43:18 -07001392 pn = (struct tnode *) n;
1393 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001394
Olof Johansson91b9a272005-08-09 20:24:39 -07001395 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001396 pos = pn->pos;
1397 bits = pn->bits;
1398
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001399 if (!chopped_off)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001400 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1401 pos, bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001402
1403 n = tnode_get_child(pn, cindex);
1404
1405 if (n == NULL) {
1406#ifdef CONFIG_IP_FIB_TRIE_STATS
1407 t->stats.null_node_hit++;
1408#endif
1409 goto backtrace;
1410 }
1411
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001412 if (IS_LEAF(n)) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001413 plen = check_leaf(t, (struct leaf *)n, key, flp, res);
1414 if (plen < 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07001415 goto backtrace;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001416
1417 ret = 0;
1418 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001419 }
1420
Olof Johansson91b9a272005-08-09 20:24:39 -07001421 cn = (struct tnode *)n;
1422
1423 /*
1424 * It's a tnode, and we can do some extra checks here if we
1425 * like, to avoid descending into a dead-end branch.
1426 * This tnode is in the parent's child array at index
1427 * key[p_pos..p_pos+p_bits] but potentially with some bits
1428 * chopped off, so in reality the index may be just a
1429 * subprefix, padded with zero at the end.
1430 * We can also take a look at any skipped bits in this
1431 * tnode - everything up to p_pos is supposed to be ok,
1432 * and the non-chopped bits of the index (se previous
1433 * paragraph) are also guaranteed ok, but the rest is
1434 * considered unknown.
1435 *
1436 * The skipped bits are key[pos+bits..cn->pos].
1437 */
1438
1439 /* If current_prefix_length < pos+bits, we are already doing
1440 * actual prefix matching, which means everything from
1441 * pos+(bits-chopped_off) onward must be zero along some
1442 * branch of this subtree - otherwise there is *no* valid
1443 * prefix present. Here we can only check the skipped
1444 * bits. Remember, since we have already indexed into the
1445 * parent's child array, we know that the bits we chopped of
1446 * *are* zero.
1447 */
1448
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001449 /* NOTA BENE: Checking only skipped bits
1450 for the new node here */
Olof Johansson91b9a272005-08-09 20:24:39 -07001451
1452 if (current_prefix_length < pos+bits) {
1453 if (tkey_extract_bits(cn->key, current_prefix_length,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001454 cn->pos - current_prefix_length)
1455 || !(cn->child[0]))
Olof Johansson91b9a272005-08-09 20:24:39 -07001456 goto backtrace;
1457 }
1458
1459 /*
1460 * If chopped_off=0, the index is fully validated and we
1461 * only need to look at the skipped bits for this, the new,
1462 * tnode. What we actually want to do is to find out if
1463 * these skipped bits match our key perfectly, or if we will
1464 * have to count on finding a matching prefix further down,
1465 * because if we do, we would like to have some way of
1466 * verifying the existence of such a prefix at this point.
1467 */
1468
1469 /* The only thing we can do at this point is to verify that
1470 * any such matching prefix can indeed be a prefix to our
1471 * key, and if the bits in the node we are inspecting that
1472 * do not match our key are not ZERO, this cannot be true.
1473 * Thus, find out where there is a mismatch (before cn->pos)
1474 * and verify that all the mismatching bits are zero in the
1475 * new tnode's key.
1476 */
1477
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001478 /*
1479 * Note: We aren't very concerned about the piece of
1480 * the key that precede pn->pos+pn->bits, since these
1481 * have already been checked. The bits after cn->pos
1482 * aren't checked since these are by definition
1483 * "unknown" at this point. Thus, what we want to see
1484 * is if we are about to enter the "prefix matching"
1485 * state, and in that case verify that the skipped
1486 * bits that will prevail throughout this subtree are
1487 * zero, as they have to be if we are to find a
1488 * matching prefix.
Olof Johansson91b9a272005-08-09 20:24:39 -07001489 */
1490
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001491 node_prefix = mask_pfx(cn->key, cn->pos);
1492 key_prefix = mask_pfx(key, cn->pos);
Olof Johansson91b9a272005-08-09 20:24:39 -07001493 pref_mismatch = key_prefix^node_prefix;
1494 mp = 0;
1495
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001496 /*
1497 * In short: If skipped bits in this node do not match
1498 * the search key, enter the "prefix matching"
1499 * state.directly.
Olof Johansson91b9a272005-08-09 20:24:39 -07001500 */
1501 if (pref_mismatch) {
1502 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1503 mp++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001504 pref_mismatch = pref_mismatch << 1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001505 }
1506 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1507
1508 if (key_prefix != 0)
1509 goto backtrace;
1510
1511 if (current_prefix_length >= cn->pos)
1512 current_prefix_length = mp;
1513 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001514
Olof Johansson91b9a272005-08-09 20:24:39 -07001515 pn = (struct tnode *)n; /* Descend */
1516 chopped_off = 0;
1517 continue;
1518
Robert Olsson19baf832005-06-21 12:43:18 -07001519backtrace:
1520 chopped_off++;
1521
1522 /* As zero don't change the child key (cindex) */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001523 while ((chopped_off <= pn->bits)
1524 && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001525 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001526
1527 /* Decrease current_... with bits chopped off */
1528 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001529 current_prefix_length = pn->pos + pn->bits
1530 - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001531
Robert Olsson19baf832005-06-21 12:43:18 -07001532 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001533 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001534 * chopped off all bits in this tnode walk up to our parent.
1535 */
1536
Olof Johansson91b9a272005-08-09 20:24:39 -07001537 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001538 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001539 } else {
Stephen Hemminger06801912007-08-10 15:22:13 -07001540 struct tnode *parent = node_parent((struct node *) pn);
1541 if (!parent)
Robert Olsson19baf832005-06-21 12:43:18 -07001542 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001543
Robert Olsson19baf832005-06-21 12:43:18 -07001544 /* Get Child's index */
Stephen Hemminger06801912007-08-10 15:22:13 -07001545 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1546 pn = parent;
Robert Olsson19baf832005-06-21 12:43:18 -07001547 chopped_off = 0;
1548
1549#ifdef CONFIG_IP_FIB_TRIE_STATS
1550 t->stats.backtrack++;
1551#endif
1552 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001553 }
Robert Olsson19baf832005-06-21 12:43:18 -07001554 }
1555failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001556 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001557found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001558 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001559 return ret;
1560}
1561
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001562/*
1563 * Remove the leaf and return parent.
1564 */
1565static void trie_leaf_remove(struct trie *t, struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001566{
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001567 struct tnode *tp = node_parent((struct node *) l);
Robert Olsson19baf832005-06-21 12:43:18 -07001568
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001569 pr_debug("entering trie_leaf_remove(%p)\n", l);
Robert Olsson19baf832005-06-21 12:43:18 -07001570
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001571 if (tp) {
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001572 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001573 put_child(t, (struct tnode *)tp, cindex, NULL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001574 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Olof Johansson91b9a272005-08-09 20:24:39 -07001575 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001576 rcu_assign_pointer(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001577
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001578 tnode_free((struct tnode *) l);
Robert Olsson19baf832005-06-21 12:43:18 -07001579}
1580
Robert Olssond562f1f2007-03-26 14:22:22 -07001581/*
1582 * Caller must hold RTNL.
1583 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001584static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001585{
1586 struct trie *t = (struct trie *) tb->tb_data;
1587 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001588 int plen = cfg->fc_dst_len;
1589 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001590 struct fib_alias *fa, *fa_to_delete;
1591 struct list_head *fa_head;
1592 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001593 struct leaf_info *li;
1594
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001595 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001596 return -EINVAL;
1597
Thomas Graf4e902c52006-08-17 18:14:52 -07001598 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001599 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001600
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001601 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001602 return -EINVAL;
1603
1604 key = key & mask;
1605 l = fib_find_node(t, key);
1606
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001607 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001608 return -ESRCH;
1609
1610 fa_head = get_fa_head(l, plen);
1611 fa = fib_find_alias(fa_head, tos, 0);
1612
1613 if (!fa)
1614 return -ESRCH;
1615
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001616 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001617
1618 fa_to_delete = NULL;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001619 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1620 list_for_each_entry_continue(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001621 struct fib_info *fi = fa->fa_info;
1622
1623 if (fa->fa_tos != tos)
1624 break;
1625
Thomas Graf4e902c52006-08-17 18:14:52 -07001626 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1627 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1628 fa->fa_scope == cfg->fc_scope) &&
1629 (!cfg->fc_protocol ||
1630 fi->fib_protocol == cfg->fc_protocol) &&
1631 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001632 fa_to_delete = fa;
1633 break;
1634 }
1635 }
1636
Olof Johansson91b9a272005-08-09 20:24:39 -07001637 if (!fa_to_delete)
1638 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001639
Olof Johansson91b9a272005-08-09 20:24:39 -07001640 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001641 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001642 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001643
Olof Johansson91b9a272005-08-09 20:24:39 -07001644 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001645 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001646
Robert Olsson2373ce12005-08-25 13:01:29 -07001647 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001648
Olof Johansson91b9a272005-08-09 20:24:39 -07001649 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001650 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001651 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001652 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001653
1654 if (hlist_empty(&l->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001655 trie_leaf_remove(t, l);
Olof Johansson91b9a272005-08-09 20:24:39 -07001656
1657 if (fa->fa_state & FA_S_ACCESSED)
1658 rt_cache_flush(-1);
1659
Robert Olsson2373ce12005-08-25 13:01:29 -07001660 fib_release_info(fa->fa_info);
1661 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001662 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001663}
1664
1665static int trie_flush_list(struct trie *t, struct list_head *head)
1666{
1667 struct fib_alias *fa, *fa_node;
1668 int found = 0;
1669
1670 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1671 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001672
Robert Olsson2373ce12005-08-25 13:01:29 -07001673 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1674 list_del_rcu(&fa->fa_list);
1675 fib_release_info(fa->fa_info);
1676 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001677 found++;
1678 }
1679 }
1680 return found;
1681}
1682
1683static int trie_flush_leaf(struct trie *t, struct leaf *l)
1684{
1685 int found = 0;
1686 struct hlist_head *lih = &l->list;
1687 struct hlist_node *node, *tmp;
1688 struct leaf_info *li = NULL;
1689
1690 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001691 found += trie_flush_list(t, &li->falh);
1692
1693 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001694 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001695 free_leaf_info(li);
1696 }
1697 }
1698 return found;
1699}
1700
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001701/*
1702 * Scan for the next right leaf starting at node p->child[idx]
1703 * Since we have back pointer, no recursion necessary.
1704 */
1705static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)
Robert Olsson19baf832005-06-21 12:43:18 -07001706{
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001707 do {
1708 t_key idx;
Robert Olsson19baf832005-06-21 12:43:18 -07001709
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001710 if (c)
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001711 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001712 else
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001713 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001714
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001715 while (idx < 1u << p->bits) {
1716 c = tnode_get_child_rcu(p, idx++);
Robert Olsson2373ce12005-08-25 13:01:29 -07001717 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001718 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001719
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001720 if (IS_LEAF(c)) {
1721 prefetch(p->child[idx]);
1722 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001723 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001724
1725 /* Rescan start scanning in new node */
1726 p = (struct tnode *) c;
1727 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001728 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001729
1730 /* Node empty, walk back up to parent */
Olof Johansson91b9a272005-08-09 20:24:39 -07001731 c = (struct node *) p;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001732 } while ( (p = node_parent_rcu(c)) != NULL);
1733
1734 return NULL; /* Root of trie */
1735}
1736
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001737static struct leaf *trie_firstleaf(struct trie *t)
1738{
1739 struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
1740
1741 if (!n)
1742 return NULL;
1743
1744 if (IS_LEAF(n)) /* trie is just a leaf */
1745 return (struct leaf *) n;
1746
1747 return leaf_walk_rcu(n, NULL);
1748}
1749
1750static struct leaf *trie_nextleaf(struct leaf *l)
1751{
1752 struct node *c = (struct node *) l;
1753 struct tnode *p = node_parent(c);
1754
1755 if (!p)
1756 return NULL; /* trie with just one leaf */
1757
1758 return leaf_walk_rcu(p, c);
Robert Olsson19baf832005-06-21 12:43:18 -07001759}
1760
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001761static struct leaf *trie_leafindex(struct trie *t, int index)
1762{
1763 struct leaf *l = trie_firstleaf(t);
1764
1765 while (index-- > 0) {
1766 l = trie_nextleaf(l);
1767 if (!l)
1768 break;
1769 }
1770 return l;
1771}
1772
1773
Robert Olssond562f1f2007-03-26 14:22:22 -07001774/*
1775 * Caller must hold RTNL.
1776 */
Robert Olsson19baf832005-06-21 12:43:18 -07001777static int fn_trie_flush(struct fib_table *tb)
1778{
1779 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001780 struct leaf *l, *ll = NULL;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001781 int found = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001782
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001783 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001784 found += trie_flush_leaf(t, l);
1785
1786 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001787 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001788 ll = l;
1789 }
1790
1791 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001792 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001793
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001794 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001795 return found;
1796}
1797
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001798static void fn_trie_select_default(struct fib_table *tb,
1799 const struct flowi *flp,
1800 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001801{
1802 struct trie *t = (struct trie *) tb->tb_data;
1803 int order, last_idx;
1804 struct fib_info *fi = NULL;
1805 struct fib_info *last_resort;
1806 struct fib_alias *fa = NULL;
1807 struct list_head *fa_head;
1808 struct leaf *l;
1809
1810 last_idx = -1;
1811 last_resort = NULL;
1812 order = -1;
1813
Robert Olsson2373ce12005-08-25 13:01:29 -07001814 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001815
Robert Olsson19baf832005-06-21 12:43:18 -07001816 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001817 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001818 goto out;
1819
1820 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001821 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001822 goto out;
1823
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001824 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001825 goto out;
1826
Robert Olsson2373ce12005-08-25 13:01:29 -07001827 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001828 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001829
Robert Olsson19baf832005-06-21 12:43:18 -07001830 if (fa->fa_scope != res->scope ||
1831 fa->fa_type != RTN_UNICAST)
1832 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001833
Robert Olsson19baf832005-06-21 12:43:18 -07001834 if (next_fi->fib_priority > res->fi->fib_priority)
1835 break;
1836 if (!next_fi->fib_nh[0].nh_gw ||
1837 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1838 continue;
1839 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001840
Robert Olsson19baf832005-06-21 12:43:18 -07001841 if (fi == NULL) {
1842 if (next_fi != res->fi)
1843 break;
1844 } else if (!fib_detect_death(fi, order, &last_resort,
Denis V. Lunev971b8932007-12-08 00:32:23 -08001845 &last_idx, tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001846 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001847 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001848 goto out;
1849 }
1850 fi = next_fi;
1851 order++;
1852 }
1853 if (order <= 0 || fi == NULL) {
Denis V. Lunev971b8932007-12-08 00:32:23 -08001854 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001855 goto out;
1856 }
1857
Denis V. Lunev971b8932007-12-08 00:32:23 -08001858 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1859 tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001860 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001861 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001862 goto out;
1863 }
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001864 if (last_idx >= 0)
1865 fib_result_assign(res, last_resort);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001866 tb->tb_default = last_idx;
1867out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001868 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001869}
1870
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001871static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1872 struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001873 struct sk_buff *skb, struct netlink_callback *cb)
1874{
1875 int i, s_i;
1876 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07001877 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001878
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001879 s_i = cb->args[5];
Robert Olsson19baf832005-06-21 12:43:18 -07001880 i = 0;
1881
Robert Olsson2373ce12005-08-25 13:01:29 -07001882 /* rcu_read_lock is hold by caller */
1883
1884 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001885 if (i < s_i) {
1886 i++;
1887 continue;
1888 }
Robert Olsson19baf832005-06-21 12:43:18 -07001889
1890 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1891 cb->nlh->nlmsg_seq,
1892 RTM_NEWROUTE,
1893 tb->tb_id,
1894 fa->fa_type,
1895 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001896 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001897 plen,
1898 fa->fa_tos,
Stephen Hemminger64347f72008-01-22 21:55:01 -08001899 fa->fa_info, NLM_F_MULTI) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001900 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001901 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001902 }
Robert Olsson19baf832005-06-21 12:43:18 -07001903 i++;
1904 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001905 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001906 return skb->len;
1907}
1908
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001909static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1910 struct sk_buff *skb, struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001911{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001912 struct leaf_info *li;
1913 struct hlist_node *node;
1914 int i, s_i;
Robert Olsson19baf832005-06-21 12:43:18 -07001915
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001916 s_i = cb->args[4];
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001917 i = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001918
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001919 /* rcu_read_lock is hold by caller */
1920 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1921 if (i < s_i) {
1922 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001923 continue;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001924 }
Robert Olsson19baf832005-06-21 12:43:18 -07001925
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001926 if (i > s_i)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001927 cb->args[5] = 0;
Olof Johansson91b9a272005-08-09 20:24:39 -07001928
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001929 if (list_empty(&li->falh))
Robert Olsson19baf832005-06-21 12:43:18 -07001930 continue;
1931
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001932 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001933 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001934 return -1;
1935 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001936 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001937 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001938
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001939 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001940 return skb->len;
1941}
1942
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001943static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
1944 struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001945{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001946 struct leaf *l;
Robert Olsson19baf832005-06-21 12:43:18 -07001947 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001948 t_key key = cb->args[2];
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001949 int count = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001950
Robert Olsson2373ce12005-08-25 13:01:29 -07001951 rcu_read_lock();
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001952 /* Dump starting at last key.
1953 * Note: 0.0.0.0/0 (ie default) is first key.
1954 */
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001955 if (count == 0)
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001956 l = trie_firstleaf(t);
1957 else {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001958 /* Normally, continue from last key, but if that is missing
1959 * fallback to using slow rescan
1960 */
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001961 l = fib_find_node(t, key);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001962 if (!l)
1963 l = trie_leafindex(t, count);
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001964 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001965
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001966 while (l) {
1967 cb->args[2] = l->key;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001968 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001969 cb->args[3] = count;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001970 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001971 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001972 }
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001973
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001974 ++count;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001975 l = trie_nextleaf(l);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001976 memset(&cb->args[4], 0,
1977 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001978 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001979 cb->args[3] = count;
Robert Olsson2373ce12005-08-25 13:01:29 -07001980 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001981
Robert Olsson19baf832005-06-21 12:43:18 -07001982 return skb->len;
Robert Olsson19baf832005-06-21 12:43:18 -07001983}
1984
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001985void __init fib_hash_init(void)
1986{
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001987 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1988 sizeof(struct fib_alias),
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08001989 0, SLAB_PANIC, NULL);
1990
1991 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1992 max(sizeof(struct leaf),
1993 sizeof(struct leaf_info)),
1994 0, SLAB_PANIC, NULL);
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001995}
Robert Olsson19baf832005-06-21 12:43:18 -07001996
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001997
1998/* Fix more generic FIB names for init later */
1999struct fib_table *fib_hash_table(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07002000{
2001 struct fib_table *tb;
2002 struct trie *t;
2003
Robert Olsson19baf832005-06-21 12:43:18 -07002004 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2005 GFP_KERNEL);
2006 if (tb == NULL)
2007 return NULL;
2008
2009 tb->tb_id = id;
Denis V. Lunev971b8932007-12-08 00:32:23 -08002010 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07002011 tb->tb_lookup = fn_trie_lookup;
2012 tb->tb_insert = fn_trie_insert;
2013 tb->tb_delete = fn_trie_delete;
2014 tb->tb_flush = fn_trie_flush;
2015 tb->tb_select_default = fn_trie_select_default;
2016 tb->tb_dump = fn_trie_dump;
Robert Olsson19baf832005-06-21 12:43:18 -07002017
2018 t = (struct trie *) tb->tb_data;
Stephen Hemmingerc28a1cf2008-01-12 20:49:13 -08002019 memset(t, 0, sizeof(*t));
Robert Olsson19baf832005-06-21 12:43:18 -07002020
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002021 if (id == RT_TABLE_LOCAL)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002022 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07002023
2024 return tb;
2025}
2026
Robert Olsson19baf832005-06-21 12:43:18 -07002027#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002028/* Depth first Trie walk iterator */
2029struct fib_trie_iter {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002030 struct seq_net_private p;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002031 struct trie *trie_local, *trie_main;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002032 struct tnode *tnode;
2033 struct trie *trie;
2034 unsigned index;
2035 unsigned depth;
2036};
Robert Olsson19baf832005-06-21 12:43:18 -07002037
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002038static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002039{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002040 struct tnode *tn = iter->tnode;
2041 unsigned cindex = iter->index;
2042 struct tnode *p;
2043
Eric W. Biederman6640e692007-01-24 14:42:04 -08002044 /* A single entry routing table */
2045 if (!tn)
2046 return NULL;
2047
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002048 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2049 iter->tnode, iter->index, iter->depth);
2050rescan:
2051 while (cindex < (1<<tn->bits)) {
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002052 struct node *n = tnode_get_child_rcu(tn, cindex);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002053
2054 if (n) {
2055 if (IS_LEAF(n)) {
2056 iter->tnode = tn;
2057 iter->index = cindex + 1;
2058 } else {
2059 /* push down one level */
2060 iter->tnode = (struct tnode *) n;
2061 iter->index = 0;
2062 ++iter->depth;
2063 }
2064 return n;
2065 }
2066
2067 ++cindex;
2068 }
2069
2070 /* Current node exhausted, pop back up */
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002071 p = node_parent_rcu((struct node *)tn);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002072 if (p) {
2073 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2074 tn = p;
2075 --iter->depth;
2076 goto rescan;
2077 }
2078
2079 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002080 return NULL;
2081}
2082
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002083static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2084 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002085{
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002086 struct node *n ;
2087
Stephen Hemminger132adf52007-03-08 20:44:43 -08002088 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002089 return NULL;
2090
2091 n = rcu_dereference(t->trie);
2092
Stephen Hemminger132adf52007-03-08 20:44:43 -08002093 if (!iter)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002094 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002095
Eric W. Biederman6640e692007-01-24 14:42:04 -08002096 if (n) {
2097 if (IS_TNODE(n)) {
2098 iter->tnode = (struct tnode *) n;
2099 iter->trie = t;
2100 iter->index = 0;
2101 iter->depth = 1;
2102 } else {
2103 iter->tnode = NULL;
2104 iter->trie = t;
2105 iter->index = 0;
2106 iter->depth = 0;
2107 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002108 return n;
2109 }
Robert Olsson19baf832005-06-21 12:43:18 -07002110 return NULL;
2111}
2112
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002113static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002114{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002115 struct node *n;
2116 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002117
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002118 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002119
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002120 rcu_read_lock();
2121 for (n = fib_trie_get_first(&iter, t); n;
2122 n = fib_trie_get_next(&iter)) {
2123 if (IS_LEAF(n)) {
Stephen Hemminger93672292008-01-22 21:54:05 -08002124 struct leaf *l = (struct leaf *)n;
2125 struct leaf_info *li;
2126 struct hlist_node *tmp;
2127
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002128 s->leaves++;
2129 s->totdepth += iter.depth;
2130 if (iter.depth > s->maxdepth)
2131 s->maxdepth = iter.depth;
Stephen Hemminger93672292008-01-22 21:54:05 -08002132
2133 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2134 ++s->prefixes;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002135 } else {
2136 const struct tnode *tn = (const struct tnode *) n;
2137 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002138
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002139 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002140 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002141 s->nodesizes[tn->bits]++;
2142
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002143 for (i = 0; i < (1<<tn->bits); i++)
2144 if (!tn->child[i])
2145 s->nullpointers++;
2146 }
2147 }
2148 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002149}
2150
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002151/*
Robert Olsson19baf832005-06-21 12:43:18 -07002152 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002153 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002154static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002155{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002156 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002157
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002158 if (stat->leaves)
2159 avdepth = stat->totdepth*100 / stat->leaves;
2160 else
2161 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002162
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002163 seq_printf(seq, "\tAver depth: %u.%02d\n",
2164 avdepth / 100, avdepth % 100);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002165 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002166
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002167 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002168 bytes = sizeof(struct leaf) * stat->leaves;
Stephen Hemminger93672292008-01-22 21:54:05 -08002169
2170 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2171 bytes += sizeof(struct leaf_info) * stat->prefixes;
2172
Stephen Hemminger187b5182008-01-12 20:55:55 -08002173 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002174 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002175
Robert Olsson06ef9212006-03-20 21:35:01 -08002176 max = MAX_STAT_DEPTH;
2177 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002178 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002179
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002180 pointers = 0;
2181 for (i = 1; i <= max; i++)
2182 if (stat->nodesizes[i] != 0) {
Stephen Hemminger187b5182008-01-12 20:55:55 -08002183 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002184 pointers += (1<<i) * stat->nodesizes[i];
2185 }
2186 seq_putc(seq, '\n');
Stephen Hemminger187b5182008-01-12 20:55:55 -08002187 seq_printf(seq, "\tPointers: %u\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002188
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002189 bytes += sizeof(struct node *) * pointers;
Stephen Hemminger187b5182008-01-12 20:55:55 -08002190 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2191 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002192}
Robert Olsson19baf832005-06-21 12:43:18 -07002193
2194#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002195static void trie_show_usage(struct seq_file *seq,
2196 const struct trie_use_stats *stats)
2197{
2198 seq_printf(seq, "\nCounters:\n---------\n");
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002199 seq_printf(seq, "gets = %u\n", stats->gets);
2200 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2201 seq_printf(seq, "semantic match passed = %u\n",
2202 stats->semantic_match_passed);
2203 seq_printf(seq, "semantic match miss = %u\n",
2204 stats->semantic_match_miss);
2205 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2206 seq_printf(seq, "skipped node resize = %u\n\n",
2207 stats->resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002208}
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002209#endif /* CONFIG_IP_FIB_TRIE_STATS */
2210
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002211static void fib_trie_show(struct seq_file *seq, const char *name,
2212 struct trie *trie)
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002213{
2214 struct trie_stat stat;
2215
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002216 trie_collect_stats(trie, &stat);
Stephen Hemminger93672292008-01-22 21:54:05 -08002217 seq_printf(seq, "%s:\n", name);
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002218 trie_show_stats(seq, &stat);
2219#ifdef CONFIG_IP_FIB_TRIE_STATS
2220 trie_show_usage(seq, &trie->stats);
2221#endif
2222}
Robert Olsson19baf832005-06-21 12:43:18 -07002223
2224static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2225{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002226 struct net *net = (struct net *)seq->private;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002227 struct fib_table *tb;
2228
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002229 seq_printf(seq,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002230 "Basic info: size of leaf:"
2231 " %Zd bytes, size of tnode: %Zd bytes.\n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002232 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002233
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002234 tb = fib_get_table(net, RT_TABLE_LOCAL);
2235 if (tb)
2236 fib_trie_show(seq, "Local", (struct trie *) tb->tb_data);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002237
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002238 tb = fib_get_table(net, RT_TABLE_MAIN);
2239 if (tb)
2240 fib_trie_show(seq, "Main", (struct trie *) tb->tb_data);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002241
Robert Olsson19baf832005-06-21 12:43:18 -07002242 return 0;
2243}
2244
Robert Olsson19baf832005-06-21 12:43:18 -07002245static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2246{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002247 int err;
2248 struct net *net;
2249
2250 net = get_proc_net(inode);
2251 if (net == NULL)
2252 return -ENXIO;
2253 err = single_open(file, fib_triestat_seq_show, net);
2254 if (err < 0) {
2255 put_net(net);
2256 return err;
2257 }
2258 return 0;
2259}
2260
2261static int fib_triestat_seq_release(struct inode *ino, struct file *f)
2262{
2263 struct seq_file *seq = f->private_data;
2264 put_net(seq->private);
2265 return single_release(ino, f);
Robert Olsson19baf832005-06-21 12:43:18 -07002266}
2267
Arjan van de Ven9a321442007-02-12 00:55:35 -08002268static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002269 .owner = THIS_MODULE,
2270 .open = fib_triestat_seq_open,
2271 .read = seq_read,
2272 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002273 .release = fib_triestat_seq_release,
Robert Olsson19baf832005-06-21 12:43:18 -07002274};
2275
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002276static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2277 loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002278{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002279 loff_t idx = 0;
2280 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -07002281
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002282 for (n = fib_trie_get_first(iter, iter->trie_local);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002283 n; ++idx, n = fib_trie_get_next(iter)) {
2284 if (pos == idx)
2285 return n;
2286 }
Robert Olsson19baf832005-06-21 12:43:18 -07002287
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002288 for (n = fib_trie_get_first(iter, iter->trie_main);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002289 n; ++idx, n = fib_trie_get_next(iter)) {
2290 if (pos == idx)
2291 return n;
2292 }
Robert Olsson19baf832005-06-21 12:43:18 -07002293 return NULL;
2294}
2295
2296static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002297 __acquires(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002298{
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002299 struct fib_trie_iter *iter = seq->private;
2300 struct fib_table *tb;
2301
2302 if (!iter->trie_local) {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002303 tb = fib_get_table(iter->p.net, RT_TABLE_LOCAL);
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002304 if (tb)
2305 iter->trie_local = (struct trie *) tb->tb_data;
2306 }
2307 if (!iter->trie_main) {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002308 tb = fib_get_table(iter->p.net, RT_TABLE_MAIN);
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002309 if (tb)
2310 iter->trie_main = (struct trie *) tb->tb_data;
2311 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002312 rcu_read_lock();
2313 if (*pos == 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07002314 return SEQ_START_TOKEN;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002315 return fib_trie_get_idx(iter, *pos - 1);
Robert Olsson19baf832005-06-21 12:43:18 -07002316}
2317
2318static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2319{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002320 struct fib_trie_iter *iter = seq->private;
2321 void *l = v;
2322
Robert Olsson19baf832005-06-21 12:43:18 -07002323 ++*pos;
Olof Johansson91b9a272005-08-09 20:24:39 -07002324 if (v == SEQ_START_TOKEN)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002325 return fib_trie_get_idx(iter, 0);
Olof Johansson91b9a272005-08-09 20:24:39 -07002326
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002327 v = fib_trie_get_next(iter);
2328 BUG_ON(v == l);
2329 if (v)
2330 return v;
2331
2332 /* continue scan in next trie */
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002333 if (iter->trie == iter->trie_local)
2334 return fib_trie_get_first(iter, iter->trie_main);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002335
2336 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07002337}
2338
2339static void fib_trie_seq_stop(struct seq_file *seq, void *v)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002340 __releases(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002341{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002342 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002343}
2344
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002345static void seq_indent(struct seq_file *seq, int n)
2346{
2347 while (n-- > 0) seq_puts(seq, " ");
2348}
Robert Olsson19baf832005-06-21 12:43:18 -07002349
Eric Dumazet28d36e32008-01-14 23:09:56 -08002350static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002351{
Stephen Hemminger132adf52007-03-08 20:44:43 -08002352 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002353 case RT_SCOPE_UNIVERSE: return "universe";
2354 case RT_SCOPE_SITE: return "site";
2355 case RT_SCOPE_LINK: return "link";
2356 case RT_SCOPE_HOST: return "host";
2357 case RT_SCOPE_NOWHERE: return "nowhere";
2358 default:
Eric Dumazet28d36e32008-01-14 23:09:56 -08002359 snprintf(buf, len, "scope=%d", s);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002360 return buf;
2361 }
2362}
2363
2364static const char *rtn_type_names[__RTN_MAX] = {
2365 [RTN_UNSPEC] = "UNSPEC",
2366 [RTN_UNICAST] = "UNICAST",
2367 [RTN_LOCAL] = "LOCAL",
2368 [RTN_BROADCAST] = "BROADCAST",
2369 [RTN_ANYCAST] = "ANYCAST",
2370 [RTN_MULTICAST] = "MULTICAST",
2371 [RTN_BLACKHOLE] = "BLACKHOLE",
2372 [RTN_UNREACHABLE] = "UNREACHABLE",
2373 [RTN_PROHIBIT] = "PROHIBIT",
2374 [RTN_THROW] = "THROW",
2375 [RTN_NAT] = "NAT",
2376 [RTN_XRESOLVE] = "XRESOLVE",
2377};
2378
Eric Dumazet28d36e32008-01-14 23:09:56 -08002379static inline const char *rtn_type(char *buf, size_t len, unsigned t)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002380{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002381 if (t < __RTN_MAX && rtn_type_names[t])
2382 return rtn_type_names[t];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002383 snprintf(buf, len, "type %u", t);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002384 return buf;
2385}
2386
2387/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002388static int fib_trie_seq_show(struct seq_file *seq, void *v)
2389{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002390 const struct fib_trie_iter *iter = seq->private;
2391 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002392
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002393 if (v == SEQ_START_TOKEN)
2394 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002395
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002396 if (!node_parent_rcu(n)) {
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002397 if (iter->trie == iter->trie_local)
Robert Olsson095b8502007-01-26 19:06:01 -08002398 seq_puts(seq, "<local>:\n");
2399 else
2400 seq_puts(seq, "<main>:\n");
2401 }
2402
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002403 if (IS_TNODE(n)) {
2404 struct tnode *tn = (struct tnode *) n;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07002405 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002406
Robert Olsson1d25cd62005-09-19 15:29:52 -07002407 seq_indent(seq, iter->depth-1);
2408 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002409 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002410 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002411
Olof Johansson91b9a272005-08-09 20:24:39 -07002412 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002413 struct leaf *l = (struct leaf *) n;
Stephen Hemminger13280422008-01-22 21:54:37 -08002414 struct leaf_info *li;
2415 struct hlist_node *node;
Al Viro32ab5f82006-09-26 22:21:45 -07002416 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002417
2418 seq_indent(seq, iter->depth);
2419 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
Eric Dumazet28d36e32008-01-14 23:09:56 -08002420
Stephen Hemminger13280422008-01-22 21:54:37 -08002421 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2422 struct fib_alias *fa;
Eric Dumazet28d36e32008-01-14 23:09:56 -08002423
Stephen Hemminger13280422008-01-22 21:54:37 -08002424 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2425 char buf1[32], buf2[32];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002426
Stephen Hemminger13280422008-01-22 21:54:37 -08002427 seq_indent(seq, iter->depth+1);
2428 seq_printf(seq, " /%d %s %s", li->plen,
2429 rtn_scope(buf1, sizeof(buf1),
2430 fa->fa_scope),
2431 rtn_type(buf2, sizeof(buf2),
2432 fa->fa_type));
2433 if (fa->fa_tos)
Denis V. Lunevb9c4d822008-02-05 02:58:45 -08002434 seq_printf(seq, " tos=%d", fa->fa_tos);
Stephen Hemminger13280422008-01-22 21:54:37 -08002435 seq_putc(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002436 }
2437 }
Robert Olsson19baf832005-06-21 12:43:18 -07002438 }
2439
2440 return 0;
2441}
2442
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002443static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002444 .start = fib_trie_seq_start,
2445 .next = fib_trie_seq_next,
2446 .stop = fib_trie_seq_stop,
2447 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002448};
2449
2450static int fib_trie_seq_open(struct inode *inode, struct file *file)
2451{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002452 return seq_open_net(inode, file, &fib_trie_seq_ops,
2453 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002454}
2455
Arjan van de Ven9a321442007-02-12 00:55:35 -08002456static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002457 .owner = THIS_MODULE,
2458 .open = fib_trie_seq_open,
2459 .read = seq_read,
2460 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002461 .release = seq_release_net,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002462};
2463
Al Viro32ab5f82006-09-26 22:21:45 -07002464static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002465{
2466 static unsigned type2flags[RTN_MAX + 1] = {
2467 [7] = RTF_REJECT, [8] = RTF_REJECT,
2468 };
2469 unsigned flags = type2flags[type];
2470
2471 if (fi && fi->fib_nh->nh_gw)
2472 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002473 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002474 flags |= RTF_HOST;
2475 flags |= RTF_UP;
2476 return flags;
2477}
2478
2479/*
2480 * This outputs /proc/net/route.
2481 * The format of the file is not supposed to be changed
2482 * and needs to be same as fib_hash output to avoid breaking
2483 * legacy utilities
2484 */
2485static int fib_route_seq_show(struct seq_file *seq, void *v)
2486{
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002487 const struct fib_trie_iter *iter = seq->private;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002488 struct leaf *l = v;
Stephen Hemminger13280422008-01-22 21:54:37 -08002489 struct leaf_info *li;
2490 struct hlist_node *node;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002491
2492 if (v == SEQ_START_TOKEN) {
2493 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2494 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2495 "\tWindow\tIRTT");
2496 return 0;
2497 }
2498
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002499 if (iter->trie == iter->trie_local)
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002500 return 0;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002501
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002502 if (IS_TNODE(l))
2503 return 0;
2504
Stephen Hemminger13280422008-01-22 21:54:37 -08002505 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002506 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002507 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002508
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002509 mask = inet_make_mask(li->plen);
2510 prefix = htonl(l->key);
2511
2512 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002513 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002514 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
Stephen Hemminger13280422008-01-22 21:54:37 -08002515 char bf[128];
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002516
2517 if (fa->fa_type == RTN_BROADCAST
2518 || fa->fa_type == RTN_MULTICAST)
2519 continue;
2520
2521 if (fi)
2522 snprintf(bf, sizeof(bf),
2523 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2524 fi->fib_dev ? fi->fib_dev->name : "*",
2525 prefix,
2526 fi->fib_nh->nh_gw, flags, 0, 0,
2527 fi->fib_priority,
2528 mask,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002529 (fi->fib_advmss ?
2530 fi->fib_advmss + 40 : 0),
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002531 fi->fib_window,
2532 fi->fib_rtt >> 3);
2533 else
2534 snprintf(bf, sizeof(bf),
2535 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2536 prefix, 0, flags, 0, 0, 0,
2537 mask, 0, 0, 0);
2538
2539 seq_printf(seq, "%-127s\n", bf);
2540 }
2541 }
2542
2543 return 0;
2544}
2545
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002546static const struct seq_operations fib_route_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002547 .start = fib_trie_seq_start,
2548 .next = fib_trie_seq_next,
2549 .stop = fib_trie_seq_stop,
2550 .show = fib_route_seq_show,
2551};
2552
2553static int fib_route_seq_open(struct inode *inode, struct file *file)
2554{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002555 return seq_open_net(inode, file, &fib_route_seq_ops,
2556 sizeof(struct fib_trie_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002557}
2558
Arjan van de Ven9a321442007-02-12 00:55:35 -08002559static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002560 .owner = THIS_MODULE,
2561 .open = fib_route_seq_open,
2562 .read = seq_read,
2563 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002564 .release = seq_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002565};
2566
Denis V. Lunev61a02652008-01-10 03:21:09 -08002567int __net_init fib_proc_init(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002568{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002569 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002570 goto out1;
2571
Denis V. Lunev61a02652008-01-10 03:21:09 -08002572 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2573 &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002574 goto out2;
2575
Denis V. Lunev61a02652008-01-10 03:21:09 -08002576 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002577 goto out3;
2578
Robert Olsson19baf832005-06-21 12:43:18 -07002579 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002580
2581out3:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002582 proc_net_remove(net, "fib_triestat");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002583out2:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002584 proc_net_remove(net, "fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002585out1:
2586 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002587}
2588
Denis V. Lunev61a02652008-01-10 03:21:09 -08002589void __net_exit fib_proc_exit(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002590{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002591 proc_net_remove(net, "fib_trie");
2592 proc_net_remove(net, "fib_triestat");
2593 proc_net_remove(net, "route");
Robert Olsson19baf832005-06-21 12:43:18 -07002594}
2595
2596#endif /* CONFIG_PROC_FS */