blob: 5cb72786a8af59e290737e6e37896aeaadd4e094 [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 *
Robert Olsson19baf832005-06-21 12:43:18 -070025 *
26 * Code from fib_hash has been reused which includes the following header:
27 *
28 *
29 * INET An implementation of the TCP/IP protocol suite for the LINUX
30 * operating system. INET is implemented using the BSD Socket
31 * interface as the means of communication with the user level.
32 *
33 * IPv4 FIB: lookup engine and maintenance routines.
34 *
35 *
36 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
37 *
38 * This program is free software; you can redistribute it and/or
39 * modify it under the terms of the GNU General Public License
40 * as published by the Free Software Foundation; either version
41 * 2 of the License, or (at your option) any later version.
Robert Olssonfd966252005-12-22 11:25:10 -080042 *
43 * Substantial contributions to this work comes from:
44 *
45 * David S. Miller, <davem@davemloft.net>
46 * Stephen Hemminger <shemminger@osdl.org>
47 * Paul E. McKenney <paulmck@us.ibm.com>
48 * Patrick McHardy <kaber@trash.net>
Robert Olsson19baf832005-06-21 12:43:18 -070049 */
50
Robert Olsson05eee482007-03-19 16:27:37 -070051#define VERSION "0.408"
Robert Olsson19baf832005-06-21 12:43:18 -070052
Robert Olsson19baf832005-06-21 12:43:18 -070053#include <asm/uaccess.h>
54#include <asm/system.h>
Jiri Slaby1977f032007-10-18 23:40:25 -070055#include <linux/bitops.h>
Robert Olsson19baf832005-06-21 12:43:18 -070056#include <linux/types.h>
57#include <linux/kernel.h>
Robert Olsson19baf832005-06-21 12:43:18 -070058#include <linux/mm.h>
59#include <linux/string.h>
60#include <linux/socket.h>
61#include <linux/sockios.h>
62#include <linux/errno.h>
63#include <linux/in.h>
64#include <linux/inet.h>
Stephen Hemmingercd8787a2006-01-03 14:38:34 -080065#include <linux/inetdevice.h>
Robert Olsson19baf832005-06-21 12:43:18 -070066#include <linux/netdevice.h>
67#include <linux/if_arp.h>
68#include <linux/proc_fs.h>
Robert Olsson2373ce12005-08-25 13:01:29 -070069#include <linux/rcupdate.h>
Robert Olsson19baf832005-06-21 12:43:18 -070070#include <linux/skbuff.h>
71#include <linux/netlink.h>
72#include <linux/init.h>
73#include <linux/list.h>
Eric W. Biederman457c4cb2007-09-12 12:01:34 +020074#include <net/net_namespace.h>
Robert Olsson19baf832005-06-21 12:43:18 -070075#include <net/ip.h>
76#include <net/protocol.h>
77#include <net/route.h>
78#include <net/tcp.h>
79#include <net/sock.h>
80#include <net/ip_fib.h>
81#include "fib_lookup.h"
82
Robert Olsson06ef9212006-03-20 21:35:01 -080083#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070084
Robert Olsson19baf832005-06-21 12:43:18 -070085#define KEYLENGTH (8*sizeof(t_key))
Robert Olsson19baf832005-06-21 12:43:18 -070086
Robert Olsson19baf832005-06-21 12:43:18 -070087typedef unsigned int t_key;
88
89#define T_TNODE 0
90#define T_LEAF 1
91#define NODE_TYPE_MASK 0x1UL
Robert Olsson2373ce12005-08-25 13:01:29 -070092#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
93
Olof Johansson91b9a272005-08-09 20:24:39 -070094#define IS_TNODE(n) (!(n->parent & T_LEAF))
95#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -070096
97struct node {
Olof Johansson91b9a272005-08-09 20:24:39 -070098 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -080099 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700100};
101
102struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700103 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800104 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700105 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700106 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700107};
108
109struct leaf_info {
110 struct hlist_node hlist;
Robert Olsson2373ce12005-08-25 13:01:29 -0700111 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700112 int plen;
113 struct list_head falh;
114};
115
116struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700117 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800118 t_key key;
Eric Dumazet112d8cf2008-01-12 21:27:41 -0800119 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
120 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
Eric Dumazet8d965442008-01-13 22:31:44 -0800121 unsigned int full_children; /* KEYLENGTH bits needed */
122 unsigned int empty_children; /* KEYLENGTH bits needed */
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700123 union {
124 struct rcu_head rcu;
125 struct work_struct work;
126 };
Olof Johansson91b9a272005-08-09 20:24:39 -0700127 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700128};
129
130#ifdef CONFIG_IP_FIB_TRIE_STATS
131struct trie_use_stats {
132 unsigned int gets;
133 unsigned int backtrack;
134 unsigned int semantic_match_passed;
135 unsigned int semantic_match_miss;
136 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700137 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700138};
139#endif
140
141struct trie_stat {
142 unsigned int totdepth;
143 unsigned int maxdepth;
144 unsigned int tnodes;
145 unsigned int leaves;
146 unsigned int nullpointers;
Stephen Hemminger93672292008-01-22 21:54:05 -0800147 unsigned int prefixes;
Robert Olsson06ef9212006-03-20 21:35:01 -0800148 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700149};
Robert Olsson19baf832005-06-21 12:43:18 -0700150
151struct trie {
Olof Johansson91b9a272005-08-09 20:24:39 -0700152 struct node *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700153#ifdef CONFIG_IP_FIB_TRIE_STATS
154 struct trie_use_stats stats;
155#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700156};
157
Robert Olsson19baf832005-06-21 12:43:18 -0700158static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800159static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
160 int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700161static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700162static struct tnode *inflate(struct trie *t, struct tnode *tn);
163static struct tnode *halve(struct trie *t, struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -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
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700180/* Same as rcu_assign_pointer
181 * but that macro() assumes that value is a pointer.
182 */
Stephen Hemminger06801912007-08-10 15:22:13 -0700183static inline void node_set_parent(struct node *node, struct tnode *ptr)
184{
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700185 smp_wmb();
186 node->parent = (unsigned long)ptr | NODE_TYPE(node);
Stephen Hemminger06801912007-08-10 15:22:13 -0700187}
Robert Olsson2373ce12005-08-25 13:01:29 -0700188
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800189static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700190{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800191 BUG_ON(i >= 1U << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700192
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800193 return tn->child[i];
194}
195
196static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
197{
198 struct node *ret = tnode_get_child(tn, i);
199
200 return rcu_dereference(ret);
Robert Olsson19baf832005-06-21 12:43:18 -0700201}
202
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700203static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700204{
Olof Johansson91b9a272005-08-09 20:24:39 -0700205 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700206}
207
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700208static inline t_key mask_pfx(t_key k, unsigned short l)
209{
210 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
211}
212
Robert Olsson19baf832005-06-21 12:43:18 -0700213static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
214{
Olof Johansson91b9a272005-08-09 20:24:39 -0700215 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700216 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700217 else
Robert Olsson19baf832005-06-21 12:43:18 -0700218 return 0;
219}
220
221static inline int tkey_equals(t_key a, t_key b)
222{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700223 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700224}
225
226static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
227{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700228 if (bits == 0 || offset >= KEYLENGTH)
229 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700230 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
231 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700232}
Robert Olsson19baf832005-06-21 12:43:18 -0700233
234static inline int tkey_mismatch(t_key a, int offset, t_key b)
235{
236 t_key diff = a ^ b;
237 int i = offset;
238
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700239 if (!diff)
240 return 0;
241 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700242 i++;
243 return i;
244}
245
Robert Olsson19baf832005-06-21 12:43:18 -0700246/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900247 To understand this stuff, an understanding of keys and all their bits is
248 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700249 all of the bits in that key are significant.
250
251 Consider a node 'n' and its parent 'tp'.
252
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900253 If n is a leaf, every bit in its key is significant. Its presence is
254 necessitated by path compression, since during a tree traversal (when
255 searching for a leaf - unless we are doing an insertion) we will completely
256 ignore all skipped bits we encounter. Thus we need to verify, at the end of
257 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700258 correct key path.
259
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900260 Note that we can never "miss" the correct key in the tree if present by
261 following the wrong path. Path compression ensures that segments of the key
262 that are the same for all keys with a given prefix are skipped, but the
263 skipped part *is* identical for each node in the subtrie below the skipped
264 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700265 call to tkey_sub_equals() in trie_insert().
266
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900267 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700268 have many different meanings.
269
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900270 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700271 _________________________________________________________________
272 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
273 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900274 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700275
276 _________________________________________________________________
277 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
278 -----------------------------------------------------------------
279 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
280
281 tp->pos = 7
282 tp->bits = 3
283 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700284 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700285
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900286 First, let's just ignore the bits that come before the parent tp, that is
287 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700288 not use them for anything.
289
290 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900291 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700292 'n' among tp's children.
293
294 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
295 for the node n.
296
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900297 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700298 of the bits are really not needed or indeed known in n->key.
299
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900300 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700301 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900302
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700303
Robert Olsson19baf832005-06-21 12:43:18 -0700304 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
305 at this point.
306
307*/
308
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700309static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700310{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700311 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700312}
313
Denis V. Lunevf5026fa2007-12-13 09:47:57 -0800314static const int halve_threshold = 25;
315static const int inflate_threshold = 50;
316static const int halve_threshold_root = 8;
317static const int inflate_threshold_root = 15;
Robert Olsson19baf832005-06-21 12:43:18 -0700318
Robert Olsson2373ce12005-08-25 13:01:29 -0700319
320static void __alias_free_mem(struct rcu_head *head)
321{
322 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
323 kmem_cache_free(fn_alias_kmem, fa);
324}
325
326static inline void alias_free_mem_rcu(struct fib_alias *fa)
327{
328 call_rcu(&fa->rcu, __alias_free_mem);
329}
330
331static void __leaf_free_rcu(struct rcu_head *head)
332{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800333 struct leaf *l = container_of(head, struct leaf, rcu);
334 kmem_cache_free(trie_leaf_kmem, l);
Robert Olsson2373ce12005-08-25 13:01:29 -0700335}
336
Stephen Hemminger387a5482008-04-10 03:47:34 -0700337static inline void free_leaf(struct leaf *l)
338{
339 call_rcu_bh(&l->rcu, __leaf_free_rcu);
340}
341
Robert Olsson2373ce12005-08-25 13:01:29 -0700342static void __leaf_info_free_rcu(struct rcu_head *head)
343{
344 kfree(container_of(head, struct leaf_info, rcu));
345}
346
347static inline void free_leaf_info(struct leaf_info *leaf)
348{
349 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
350}
351
Eric Dumazet8d965442008-01-13 22:31:44 -0800352static struct tnode *tnode_alloc(size_t size)
Robert Olsson2373ce12005-08-25 13:01:29 -0700353{
Robert Olsson2373ce12005-08-25 13:01:29 -0700354 if (size <= PAGE_SIZE)
Eric Dumazet8d965442008-01-13 22:31:44 -0800355 return kzalloc(size, GFP_KERNEL);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700356 else
357 return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
358}
Robert Olsson2373ce12005-08-25 13:01:29 -0700359
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700360static void __tnode_vfree(struct work_struct *arg)
361{
362 struct tnode *tn = container_of(arg, struct tnode, work);
363 vfree(tn);
Robert Olsson2373ce12005-08-25 13:01:29 -0700364}
365
366static void __tnode_free_rcu(struct rcu_head *head)
367{
368 struct tnode *tn = container_of(head, struct tnode, rcu);
Eric Dumazet8d965442008-01-13 22:31:44 -0800369 size_t size = sizeof(struct tnode) +
370 (sizeof(struct node *) << tn->bits);
Robert Olsson2373ce12005-08-25 13:01:29 -0700371
372 if (size <= PAGE_SIZE)
373 kfree(tn);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700374 else {
375 INIT_WORK(&tn->work, __tnode_vfree);
376 schedule_work(&tn->work);
377 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700378}
379
380static inline void tnode_free(struct tnode *tn)
381{
Stephen Hemminger387a5482008-04-10 03:47:34 -0700382 if (IS_LEAF(tn))
383 free_leaf((struct leaf *) tn);
384 else
Robert Olsson550e29b2006-04-04 12:53:35 -0700385 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700386}
387
Robert Olsson19baf832005-06-21 12:43:18 -0700388static struct leaf *leaf_new(void)
389{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800390 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700391 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700392 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700393 INIT_HLIST_HEAD(&l->list);
394 }
395 return l;
396}
397
398static struct leaf_info *leaf_info_new(int plen)
399{
400 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700401 if (li) {
402 li->plen = plen;
403 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700404 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700405 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700406}
407
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800408static struct tnode *tnode_new(t_key key, int pos, int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700409{
Eric Dumazet8d965442008-01-13 22:31:44 -0800410 size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700411 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700412
Olof Johansson91b9a272005-08-09 20:24:39 -0700413 if (tn) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700414 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700415 tn->pos = pos;
416 tn->bits = bits;
417 tn->key = key;
418 tn->full_children = 0;
419 tn->empty_children = 1<<bits;
420 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700421
Eric Dumazet8d965442008-01-13 22:31:44 -0800422 pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
423 (unsigned long) (sizeof(struct node) << bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700424 return tn;
425}
426
Robert Olsson19baf832005-06-21 12:43:18 -0700427/*
428 * Check whether a tnode 'n' is "full", i.e. it is an internal node
429 * and no bits are skipped. See discussion in dyntree paper p. 6
430 */
431
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700432static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700433{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700434 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700435 return 0;
436
437 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
438}
439
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800440static inline void put_child(struct trie *t, struct tnode *tn, int i,
441 struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700442{
443 tnode_put_child_reorg(tn, i, n, -1);
444}
445
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700446 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700447 * Add a child at position i overwriting the old value.
448 * Update the value of full_children and empty_children.
449 */
450
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800451static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
452 int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700453{
Robert Olsson2373ce12005-08-25 13:01:29 -0700454 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700455 int isfull;
456
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700457 BUG_ON(i >= 1<<tn->bits);
458
Robert Olsson19baf832005-06-21 12:43:18 -0700459 /* update emptyChildren */
460 if (n == NULL && chi != NULL)
461 tn->empty_children++;
462 else if (n != NULL && chi == NULL)
463 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700464
Robert Olsson19baf832005-06-21 12:43:18 -0700465 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700466 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700467 wasfull = tnode_full(tn, chi);
468
469 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700470 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700471 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700472 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700473 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700474
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700475 if (n)
Stephen Hemminger06801912007-08-10 15:22:13 -0700476 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700477
Robert Olsson2373ce12005-08-25 13:01:29 -0700478 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700479}
480
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700481static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700482{
483 int i;
Robert Olsson2f368952005-07-05 15:02:40 -0700484 int err = 0;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700485 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700486 int inflate_threshold_use;
487 int halve_threshold_use;
Robert Olsson05eee482007-03-19 16:27:37 -0700488 int max_resize;
Robert Olsson19baf832005-06-21 12:43:18 -0700489
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900490 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700491 return NULL;
492
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700493 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
494 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700495
496 /* No children */
497 if (tn->empty_children == tnode_child_length(tn)) {
498 tnode_free(tn);
499 return NULL;
500 }
501 /* One child */
502 if (tn->empty_children == tnode_child_length(tn) - 1)
503 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700504 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700505
Olof Johansson91b9a272005-08-09 20:24:39 -0700506 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700507 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700508 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700509
510 /* compress one level */
Stephen Hemminger06801912007-08-10 15:22:13 -0700511 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700512 tnode_free(tn);
513 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700514 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700515 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700516 * Double as long as the resulting node has a number of
517 * nonempty nodes that are above the threshold.
518 */
519
520 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700521 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
522 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700523 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700524 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700525 * children in the *doubled* node is at least 'high'."
526 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700527 * 'high' in this instance is the variable 'inflate_threshold'. It
528 * is expressed as a percentage, so we multiply it with
529 * tnode_child_length() and instead of multiplying by 2 (since the
530 * child array will be doubled by inflate()) and multiplying
531 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700532 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700533 *
534 * The left-hand side may look a bit weird: tnode_child_length(tn)
535 * - tn->empty_children is of course the number of non-null children
536 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700537 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700538 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700539 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700540 *
Robert Olsson19baf832005-06-21 12:43:18 -0700541 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700542 *
Robert Olsson19baf832005-06-21 12:43:18 -0700543 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700544 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700545 * tn->full_children;
546 *
547 * new_child_length = tnode_child_length(tn) * 2;
548 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700549 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700550 * new_child_length;
551 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700552 *
553 * ...and so on, tho it would mess up the while () loop.
554 *
Robert Olsson19baf832005-06-21 12:43:18 -0700555 * anyway,
556 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
557 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700558 *
Robert Olsson19baf832005-06-21 12:43:18 -0700559 * avoid a division:
560 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
561 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700562 *
Robert Olsson19baf832005-06-21 12:43:18 -0700563 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700564 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700565 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700566 *
Robert Olsson19baf832005-06-21 12:43:18 -0700567 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700568 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700569 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700570 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700571 *
Robert Olsson19baf832005-06-21 12:43:18 -0700572 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700573 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700574 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700575 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700576 *
Robert Olsson19baf832005-06-21 12:43:18 -0700577 */
578
579 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700580
Robert Olssone6308be2005-10-04 13:01:58 -0700581 /* Keep root node larger */
582
Stephen Hemminger132adf52007-03-08 20:44:43 -0800583 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700584 inflate_threshold_use = inflate_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900585 else
Robert Olssone6308be2005-10-04 13:01:58 -0700586 inflate_threshold_use = inflate_threshold;
587
Robert Olsson2f368952005-07-05 15:02:40 -0700588 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700589 max_resize = 10;
590 while ((tn->full_children > 0 && max_resize-- &&
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800591 50 * (tn->full_children + tnode_child_length(tn)
592 - tn->empty_children)
593 >= inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700594
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700595 old_tn = tn;
596 tn = inflate(t, tn);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800597
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700598 if (IS_ERR(tn)) {
599 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700600#ifdef CONFIG_IP_FIB_TRIE_STATS
601 t->stats.resize_node_skipped++;
602#endif
603 break;
604 }
Robert Olsson19baf832005-06-21 12:43:18 -0700605 }
606
Robert Olsson05eee482007-03-19 16:27:37 -0700607 if (max_resize < 0) {
608 if (!tn->parent)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800609 pr_warning("Fix inflate_threshold_root."
610 " Now=%d size=%d bits\n",
611 inflate_threshold_root, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700612 else
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800613 pr_warning("Fix inflate_threshold."
614 " Now=%d size=%d bits\n",
615 inflate_threshold, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700616 }
617
Robert Olsson19baf832005-06-21 12:43:18 -0700618 check_tnode(tn);
619
620 /*
621 * Halve as long as the number of empty children in this
622 * node is above threshold.
623 */
Robert Olsson2f368952005-07-05 15:02:40 -0700624
Robert Olssone6308be2005-10-04 13:01:58 -0700625
626 /* Keep root node larger */
627
Stephen Hemminger132adf52007-03-08 20:44:43 -0800628 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700629 halve_threshold_use = halve_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900630 else
Robert Olssone6308be2005-10-04 13:01:58 -0700631 halve_threshold_use = halve_threshold;
632
Robert Olsson2f368952005-07-05 15:02:40 -0700633 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700634 max_resize = 10;
635 while (tn->bits > 1 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700636 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700637 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700638
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700639 old_tn = tn;
640 tn = halve(t, tn);
641 if (IS_ERR(tn)) {
642 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700643#ifdef CONFIG_IP_FIB_TRIE_STATS
644 t->stats.resize_node_skipped++;
645#endif
646 break;
647 }
648 }
649
Robert Olsson05eee482007-03-19 16:27:37 -0700650 if (max_resize < 0) {
651 if (!tn->parent)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800652 pr_warning("Fix halve_threshold_root."
653 " Now=%d size=%d bits\n",
654 halve_threshold_root, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700655 else
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800656 pr_warning("Fix halve_threshold."
657 " Now=%d size=%d bits\n",
658 halve_threshold, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700659 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700660
Robert Olsson19baf832005-06-21 12:43:18 -0700661 /* Only one child remains */
Robert Olsson19baf832005-06-21 12:43:18 -0700662 if (tn->empty_children == tnode_child_length(tn) - 1)
663 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700664 struct node *n;
665
Olof Johansson91b9a272005-08-09 20:24:39 -0700666 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700667 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700668 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700669
670 /* compress one level */
671
Stephen Hemminger06801912007-08-10 15:22:13 -0700672 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700673 tnode_free(tn);
674 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700675 }
676
677 return (struct node *) tn;
678}
679
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700680static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700681{
Robert Olsson19baf832005-06-21 12:43:18 -0700682 struct tnode *oldtnode = tn;
683 int olen = tnode_child_length(tn);
684 int i;
685
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700686 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700687
688 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
689
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700690 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700691 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700692
693 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700694 * Preallocate and store tnodes before the actual work so we
695 * don't get into an inconsistent state if memory allocation
696 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700697 * of tnode is ignored.
698 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700699
700 for (i = 0; i < olen; i++) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800701 struct tnode *inode;
Robert Olsson2f368952005-07-05 15:02:40 -0700702
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800703 inode = (struct tnode *) tnode_get_child(oldtnode, i);
Robert Olsson2f368952005-07-05 15:02:40 -0700704 if (inode &&
705 IS_TNODE(inode) &&
706 inode->pos == oldtnode->pos + oldtnode->bits &&
707 inode->bits > 1) {
708 struct tnode *left, *right;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700709 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700710
Robert Olsson2f368952005-07-05 15:02:40 -0700711 left = tnode_new(inode->key&(~m), inode->pos + 1,
712 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700713 if (!left)
714 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700715
Robert Olsson2f368952005-07-05 15:02:40 -0700716 right = tnode_new(inode->key|m, inode->pos + 1,
717 inode->bits - 1);
718
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900719 if (!right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700720 tnode_free(left);
721 goto nomem;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900722 }
Robert Olsson2f368952005-07-05 15:02:40 -0700723
724 put_child(t, tn, 2*i, (struct node *) left);
725 put_child(t, tn, 2*i+1, (struct node *) right);
726 }
727 }
728
Olof Johansson91b9a272005-08-09 20:24:39 -0700729 for (i = 0; i < olen; i++) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -0800730 struct tnode *inode;
Robert Olsson19baf832005-06-21 12:43:18 -0700731 struct node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700732 struct tnode *left, *right;
733 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700734
Robert Olsson19baf832005-06-21 12:43:18 -0700735 /* An empty child */
736 if (node == NULL)
737 continue;
738
739 /* A leaf or an internal node with skipped bits */
740
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700741 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700742 tn->pos + tn->bits - 1) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800743 if (tkey_extract_bits(node->key,
744 oldtnode->pos + oldtnode->bits,
745 1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700746 put_child(t, tn, 2*i, node);
747 else
748 put_child(t, tn, 2*i+1, node);
749 continue;
750 }
751
752 /* An internal node with two children */
753 inode = (struct tnode *) node;
754
755 if (inode->bits == 1) {
756 put_child(t, tn, 2*i, inode->child[0]);
757 put_child(t, tn, 2*i+1, inode->child[1]);
758
759 tnode_free(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700760 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700761 }
762
Olof Johansson91b9a272005-08-09 20:24:39 -0700763 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700764
Olof Johansson91b9a272005-08-09 20:24:39 -0700765 /* We will replace this node 'inode' with two new
766 * ones, 'left' and 'right', each with half of the
767 * original children. The two new nodes will have
768 * a position one bit further down the key and this
769 * means that the "significant" part of their keys
770 * (see the discussion near the top of this file)
771 * will differ by one bit, which will be "0" in
772 * left's key and "1" in right's key. Since we are
773 * moving the key position by one step, the bit that
774 * we are moving away from - the bit at position
775 * (inode->pos) - is the one that will differ between
776 * left and right. So... we synthesize that bit in the
777 * two new keys.
778 * The mask 'm' below will be a single "one" bit at
779 * the position (inode->pos)
780 */
Robert Olsson19baf832005-06-21 12:43:18 -0700781
Olof Johansson91b9a272005-08-09 20:24:39 -0700782 /* Use the old key, but set the new significant
783 * bit to zero.
784 */
Robert Olsson19baf832005-06-21 12:43:18 -0700785
Olof Johansson91b9a272005-08-09 20:24:39 -0700786 left = (struct tnode *) tnode_get_child(tn, 2*i);
787 put_child(t, tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700788
Olof Johansson91b9a272005-08-09 20:24:39 -0700789 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700790
Olof Johansson91b9a272005-08-09 20:24:39 -0700791 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
792 put_child(t, tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700793
Olof Johansson91b9a272005-08-09 20:24:39 -0700794 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700795
Olof Johansson91b9a272005-08-09 20:24:39 -0700796 size = tnode_child_length(left);
797 for (j = 0; j < size; j++) {
798 put_child(t, left, j, inode->child[j]);
799 put_child(t, right, j, inode->child[j + size]);
Robert Olsson19baf832005-06-21 12:43:18 -0700800 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700801 put_child(t, tn, 2*i, resize(t, left));
802 put_child(t, tn, 2*i+1, resize(t, right));
803
804 tnode_free(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700805 }
806 tnode_free(oldtnode);
807 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700808nomem:
809 {
810 int size = tnode_child_length(tn);
811 int j;
812
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700813 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700814 if (tn->child[j])
815 tnode_free((struct tnode *)tn->child[j]);
816
817 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700818
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700819 return ERR_PTR(-ENOMEM);
820 }
Robert Olsson19baf832005-06-21 12:43:18 -0700821}
822
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700823static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700824{
825 struct tnode *oldtnode = tn;
826 struct node *left, *right;
827 int i;
828 int olen = tnode_child_length(tn);
829
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700830 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700831
832 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700833
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700834 if (!tn)
835 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700836
837 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700838 * Preallocate and store tnodes before the actual work so we
839 * don't get into an inconsistent state if memory allocation
840 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700841 * of tnode is ignored.
842 */
843
Olof Johansson91b9a272005-08-09 20:24:39 -0700844 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700845 left = tnode_get_child(oldtnode, i);
846 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700847
Robert Olsson2f368952005-07-05 15:02:40 -0700848 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700849 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700850 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700851
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700852 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700853
854 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700855 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700856
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700857 put_child(t, tn, i/2, (struct node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700858 }
Robert Olsson2f368952005-07-05 15:02:40 -0700859
Robert Olsson2f368952005-07-05 15:02:40 -0700860 }
Robert Olsson19baf832005-06-21 12:43:18 -0700861
Olof Johansson91b9a272005-08-09 20:24:39 -0700862 for (i = 0; i < olen; i += 2) {
863 struct tnode *newBinNode;
864
Robert Olsson19baf832005-06-21 12:43:18 -0700865 left = tnode_get_child(oldtnode, i);
866 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700867
Robert Olsson19baf832005-06-21 12:43:18 -0700868 /* At least one of the children is empty */
869 if (left == NULL) {
870 if (right == NULL) /* Both are empty */
871 continue;
872 put_child(t, tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700873 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700874 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700875
876 if (right == NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700877 put_child(t, tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700878 continue;
879 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700880
Robert Olsson19baf832005-06-21 12:43:18 -0700881 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700882 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
883 put_child(t, tn, i/2, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700884 put_child(t, newBinNode, 0, left);
885 put_child(t, newBinNode, 1, right);
886 put_child(t, tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700887 }
888 tnode_free(oldtnode);
889 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700890nomem:
891 {
892 int size = tnode_child_length(tn);
893 int j;
894
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700895 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700896 if (tn->child[j])
897 tnode_free((struct tnode *)tn->child[j]);
898
899 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700900
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700901 return ERR_PTR(-ENOMEM);
902 }
Robert Olsson19baf832005-06-21 12:43:18 -0700903}
904
Robert Olsson772cb712005-09-19 15:31:18 -0700905/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700906 via get_fa_head and dump */
907
Robert Olsson772cb712005-09-19 15:31:18 -0700908static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700909{
Robert Olsson772cb712005-09-19 15:31:18 -0700910 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700911 struct hlist_node *node;
912 struct leaf_info *li;
913
Robert Olsson2373ce12005-08-25 13:01:29 -0700914 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700915 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700916 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700917
Robert Olsson19baf832005-06-21 12:43:18 -0700918 return NULL;
919}
920
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800921static inline struct list_head *get_fa_head(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700922{
Robert Olsson772cb712005-09-19 15:31:18 -0700923 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700924
Olof Johansson91b9a272005-08-09 20:24:39 -0700925 if (!li)
926 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700927
Olof Johansson91b9a272005-08-09 20:24:39 -0700928 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700929}
930
931static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
932{
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900933 struct leaf_info *li = NULL, *last = NULL;
934 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700935
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900936 if (hlist_empty(head)) {
937 hlist_add_head_rcu(&new->hlist, head);
938 } else {
939 hlist_for_each_entry(li, node, head, hlist) {
940 if (new->plen > li->plen)
941 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700942
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900943 last = li;
944 }
945 if (last)
946 hlist_add_after_rcu(&last->hlist, &new->hlist);
947 else
948 hlist_add_before_rcu(&new->hlist, &li->hlist);
949 }
Robert Olsson19baf832005-06-21 12:43:18 -0700950}
951
Robert Olsson2373ce12005-08-25 13:01:29 -0700952/* rcu_read_lock needs to be hold by caller from readside */
953
Robert Olsson19baf832005-06-21 12:43:18 -0700954static struct leaf *
955fib_find_node(struct trie *t, u32 key)
956{
957 int pos;
958 struct tnode *tn;
959 struct node *n;
960
961 pos = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700962 n = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700963
964 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
965 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700966
Robert Olsson19baf832005-06-21 12:43:18 -0700967 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700968
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700969 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700970 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800971 n = tnode_get_child_rcu(tn,
972 tkey_extract_bits(key,
973 tn->pos,
974 tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700975 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700976 break;
977 }
978 /* Case we have found a leaf. Compare prefixes */
979
Olof Johansson91b9a272005-08-09 20:24:39 -0700980 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
981 return (struct leaf *)n;
982
Robert Olsson19baf832005-06-21 12:43:18 -0700983 return NULL;
984}
985
986static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
987{
Robert Olsson19baf832005-06-21 12:43:18 -0700988 int wasfull;
Stephen Hemminger06801912007-08-10 15:22:13 -0700989 t_key cindex, key = tn->key;
990 struct tnode *tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700991
Stephen Hemminger06801912007-08-10 15:22:13 -0700992 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700993 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
994 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800995 tn = (struct tnode *) resize(t, (struct tnode *)tn);
996
997 tnode_put_child_reorg((struct tnode *)tp, cindex,
998 (struct node *)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -0700999
Stephen Hemminger06801912007-08-10 15:22:13 -07001000 tp = node_parent((struct node *) tn);
1001 if (!tp)
Robert Olsson19baf832005-06-21 12:43:18 -07001002 break;
Stephen Hemminger06801912007-08-10 15:22:13 -07001003 tn = tp;
Robert Olsson19baf832005-06-21 12:43:18 -07001004 }
Stephen Hemminger06801912007-08-10 15:22:13 -07001005
Robert Olsson19baf832005-06-21 12:43:18 -07001006 /* Handle last (top) tnode */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001007 if (IS_TNODE(tn))
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001008 tn = (struct tnode *)resize(t, (struct tnode *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001009
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001010 return (struct node *)tn;
Robert Olsson19baf832005-06-21 12:43:18 -07001011}
1012
Robert Olsson2373ce12005-08-25 13:01:29 -07001013/* only used from updater-side */
1014
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001015static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -07001016{
1017 int pos, newpos;
1018 struct tnode *tp = NULL, *tn = NULL;
1019 struct node *n;
1020 struct leaf *l;
1021 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001022 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001023 struct leaf_info *li;
1024 t_key cindex;
1025
1026 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001027 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001028
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001029 /* If we point to NULL, stop. Either the tree is empty and we should
1030 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001031 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001032 * If we point to a T_TNODE, check if it matches our key. Note that
1033 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001034 * not be the parent's 'pos'+'bits'!
1035 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001036 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001037 * the index from our key, push the T_TNODE and walk the tree.
1038 *
1039 * If it doesn't, we have to replace it with a new T_TNODE.
1040 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001041 * If we point to a T_LEAF, it might or might not have the same key
1042 * as we do. If it does, just change the value, update the T_LEAF's
1043 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001044 * If it doesn't, we need to replace it with a T_TNODE.
1045 */
1046
1047 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1048 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001049
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001050 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001051
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001052 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001053 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001054 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001055 n = tnode_get_child(tn,
1056 tkey_extract_bits(key,
1057 tn->pos,
1058 tn->bits));
Robert Olsson19baf832005-06-21 12:43:18 -07001059
Stephen Hemminger06801912007-08-10 15:22:13 -07001060 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001061 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001062 break;
1063 }
1064
1065 /*
1066 * n ----> NULL, LEAF or TNODE
1067 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001068 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001069 */
1070
Olof Johansson91b9a272005-08-09 20:24:39 -07001071 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001072
1073 /* Case 1: n is a leaf. Compare prefixes */
1074
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001075 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08001076 l = (struct leaf *) n;
Robert Olsson19baf832005-06-21 12:43:18 -07001077 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001078
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001079 if (!li)
1080 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001081
1082 fa_head = &li->falh;
1083 insert_leaf_info(&l->list, li);
1084 goto done;
1085 }
Robert Olsson19baf832005-06-21 12:43:18 -07001086 l = leaf_new();
1087
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001088 if (!l)
1089 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001090
1091 l->key = key;
1092 li = leaf_info_new(plen);
1093
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001094 if (!li) {
Stephen Hemminger387a5482008-04-10 03:47:34 -07001095 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001096 return NULL;
Robert Olssonf835e472005-06-28 15:00:39 -07001097 }
Robert Olsson19baf832005-06-21 12:43:18 -07001098
1099 fa_head = &li->falh;
1100 insert_leaf_info(&l->list, li);
1101
Robert Olsson19baf832005-06-21 12:43:18 -07001102 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001103 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001104
Stephen Hemminger06801912007-08-10 15:22:13 -07001105 node_set_parent((struct node *)l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001106
Olof Johansson91b9a272005-08-09 20:24:39 -07001107 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1108 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1109 } else {
1110 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001111 /*
1112 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001113 * first tnode need some special handling
1114 */
1115
1116 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001117 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001118 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001119 pos = 0;
1120
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001121 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001122 newpos = tkey_mismatch(key, pos, n->key);
1123 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001124 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001125 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001126 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001127 }
Robert Olsson19baf832005-06-21 12:43:18 -07001128
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001129 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001130 free_leaf_info(li);
Stephen Hemminger387a5482008-04-10 03:47:34 -07001131 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001132 return NULL;
Olof Johansson91b9a272005-08-09 20:24:39 -07001133 }
1134
Stephen Hemminger06801912007-08-10 15:22:13 -07001135 node_set_parent((struct node *)tn, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001136
Olof Johansson91b9a272005-08-09 20:24:39 -07001137 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001138 put_child(t, tn, missbit, (struct node *)l);
1139 put_child(t, tn, 1-missbit, n);
1140
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001141 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001142 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001143 put_child(t, (struct tnode *)tp, cindex,
1144 (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001145 } else {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001146 rcu_assign_pointer(t->trie, (struct node *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001147 tp = tn;
1148 }
1149 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001150
1151 if (tp && tp->pos + tp->bits > 32)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001152 pr_warning("fib_trie"
1153 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1154 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001155
Robert Olsson19baf832005-06-21 12:43:18 -07001156 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001157
1158 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Robert Olssonf835e472005-06-28 15:00:39 -07001159done:
Robert Olsson19baf832005-06-21 12:43:18 -07001160 return fa_head;
1161}
1162
Robert Olssond562f1f2007-03-26 14:22:22 -07001163/*
1164 * Caller must hold RTNL.
1165 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001166static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001167{
1168 struct trie *t = (struct trie *) tb->tb_data;
1169 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001170 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001171 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001172 int plen = cfg->fc_dst_len;
1173 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001174 u32 key, mask;
1175 int err;
1176 struct leaf *l;
1177
1178 if (plen > 32)
1179 return -EINVAL;
1180
Thomas Graf4e902c52006-08-17 18:14:52 -07001181 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001182
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001183 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001184
Olof Johansson91b9a272005-08-09 20:24:39 -07001185 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001186
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001187 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001188 return -EINVAL;
1189
1190 key = key & mask;
1191
Thomas Graf4e902c52006-08-17 18:14:52 -07001192 fi = fib_create_info(cfg);
1193 if (IS_ERR(fi)) {
1194 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001195 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001196 }
Robert Olsson19baf832005-06-21 12:43:18 -07001197
1198 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001199 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001200
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001201 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001202 fa_head = get_fa_head(l, plen);
1203 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1204 }
1205
1206 /* Now fa, if non-NULL, points to the first fib alias
1207 * with the same keys [prefix,tos,priority], if such key already
1208 * exists or to the node before which we will insert new one.
1209 *
1210 * If fa is NULL, we will need to allocate a new one and
1211 * insert to the head of f.
1212 *
1213 * If f is NULL, no fib node matched the destination key
1214 * and we need to allocate a new one of those as well.
1215 */
1216
Julian Anastasov936f6f82008-01-28 21:18:06 -08001217 if (fa && fa->fa_tos == tos &&
1218 fa->fa_info->fib_priority == fi->fib_priority) {
1219 struct fib_alias *fa_first, *fa_match;
Robert Olsson19baf832005-06-21 12:43:18 -07001220
1221 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001222 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001223 goto out;
1224
Julian Anastasov936f6f82008-01-28 21:18:06 -08001225 /* We have 2 goals:
1226 * 1. Find exact match for type, scope, fib_info to avoid
1227 * duplicate routes
1228 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1229 */
1230 fa_match = NULL;
1231 fa_first = fa;
1232 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1233 list_for_each_entry_continue(fa, fa_head, fa_list) {
1234 if (fa->fa_tos != tos)
1235 break;
1236 if (fa->fa_info->fib_priority != fi->fib_priority)
1237 break;
1238 if (fa->fa_type == cfg->fc_type &&
1239 fa->fa_scope == cfg->fc_scope &&
1240 fa->fa_info == fi) {
1241 fa_match = fa;
1242 break;
1243 }
1244 }
1245
Thomas Graf4e902c52006-08-17 18:14:52 -07001246 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001247 struct fib_info *fi_drop;
1248 u8 state;
1249
Julian Anastasov936f6f82008-01-28 21:18:06 -08001250 fa = fa_first;
1251 if (fa_match) {
1252 if (fa == fa_match)
1253 err = 0;
Joonwoo Park67250332008-01-18 03:45:18 -08001254 goto out;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001255 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001256 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001257 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001258 if (new_fa == NULL)
1259 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001260
1261 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001262 new_fa->fa_tos = fa->fa_tos;
1263 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001264 new_fa->fa_type = cfg->fc_type;
1265 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001266 state = fa->fa_state;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001267 new_fa->fa_state = state & ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001268
Robert Olsson2373ce12005-08-25 13:01:29 -07001269 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1270 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001271
1272 fib_release_info(fi_drop);
1273 if (state & FA_S_ACCESSED)
Denis V. Lunev76e6ebf2008-07-05 19:00:44 -07001274 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
Milan Kocianb8f55832007-05-23 14:55:06 -07001275 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1276 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001277
Olof Johansson91b9a272005-08-09 20:24:39 -07001278 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001279 }
1280 /* Error if we find a perfect match which
1281 * uses the same scope, type, and nexthop
1282 * information.
1283 */
Julian Anastasov936f6f82008-01-28 21:18:06 -08001284 if (fa_match)
1285 goto out;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001286
Thomas Graf4e902c52006-08-17 18:14:52 -07001287 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001288 fa = fa_first;
Robert Olsson19baf832005-06-21 12:43:18 -07001289 }
1290 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001291 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001292 goto out;
1293
1294 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001295 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001296 if (new_fa == NULL)
1297 goto out;
1298
1299 new_fa->fa_info = fi;
1300 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001301 new_fa->fa_type = cfg->fc_type;
1302 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001303 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001304 /*
1305 * Insert new entry to the list.
1306 */
1307
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001308 if (!fa_head) {
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001309 fa_head = fib_insert_node(t, key, plen);
1310 if (unlikely(!fa_head)) {
1311 err = -ENOMEM;
Robert Olssonf835e472005-06-28 15:00:39 -07001312 goto out_free_new_fa;
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001313 }
Robert Olssonf835e472005-06-28 15:00:39 -07001314 }
Robert Olsson19baf832005-06-21 12:43:18 -07001315
Robert Olsson2373ce12005-08-25 13:01:29 -07001316 list_add_tail_rcu(&new_fa->fa_list,
1317 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001318
Denis V. Lunev76e6ebf2008-07-05 19:00:44 -07001319 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001320 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001321 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001322succeeded:
1323 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001324
1325out_free_new_fa:
1326 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001327out:
1328 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001329err:
Robert Olsson19baf832005-06-21 12:43:18 -07001330 return err;
1331}
1332
Robert Olsson772cb712005-09-19 15:31:18 -07001333/* should be called with rcu_read_lock */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001334static int check_leaf(struct trie *t, struct leaf *l,
1335 t_key key, const struct flowi *flp,
1336 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001337{
Robert Olsson19baf832005-06-21 12:43:18 -07001338 struct leaf_info *li;
1339 struct hlist_head *hhead = &l->list;
1340 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001341
Robert Olsson2373ce12005-08-25 13:01:29 -07001342 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001343 int err;
1344 int plen = li->plen;
1345 __be32 mask = inet_make_mask(plen);
1346
Al Viro888454c2006-09-19 13:42:46 -07001347 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001348 continue;
1349
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001350 err = fib_semantic_match(&li->falh, flp, res,
1351 htonl(l->key), mask, plen);
1352
Robert Olsson19baf832005-06-21 12:43:18 -07001353#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001354 if (err <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001355 t->stats.semantic_match_passed++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001356 else
1357 t->stats.semantic_match_miss++;
Robert Olsson19baf832005-06-21 12:43:18 -07001358#endif
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001359 if (err <= 0)
Ben Hutchings2e655572008-07-10 16:52:52 -07001360 return err;
Robert Olsson19baf832005-06-21 12:43:18 -07001361 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001362
Ben Hutchings2e655572008-07-10 16:52:52 -07001363 return 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001364}
1365
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001366static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
1367 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001368{
1369 struct trie *t = (struct trie *) tb->tb_data;
Ben Hutchings2e655572008-07-10 16:52:52 -07001370 int ret;
Robert Olsson19baf832005-06-21 12:43:18 -07001371 struct node *n;
1372 struct tnode *pn;
1373 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001374 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001375 int chopped_off;
1376 t_key cindex = 0;
1377 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001378 struct tnode *cn;
1379 t_key node_prefix, key_prefix, pref_mismatch;
1380 int mp;
1381
Robert Olsson2373ce12005-08-25 13:01:29 -07001382 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001383
Robert Olsson2373ce12005-08-25 13:01:29 -07001384 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001385 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001386 goto failed;
1387
1388#ifdef CONFIG_IP_FIB_TRIE_STATS
1389 t->stats.gets++;
1390#endif
1391
1392 /* Just a leaf? */
1393 if (IS_LEAF(n)) {
Ben Hutchings2e655572008-07-10 16:52:52 -07001394 ret = check_leaf(t, (struct leaf *)n, key, flp, res);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001395 goto found;
Robert Olsson19baf832005-06-21 12:43:18 -07001396 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001397
Robert Olsson19baf832005-06-21 12:43:18 -07001398 pn = (struct tnode *) n;
1399 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001400
Olof Johansson91b9a272005-08-09 20:24:39 -07001401 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001402 pos = pn->pos;
1403 bits = pn->bits;
1404
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001405 if (!chopped_off)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001406 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1407 pos, bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001408
1409 n = tnode_get_child(pn, cindex);
1410
1411 if (n == NULL) {
1412#ifdef CONFIG_IP_FIB_TRIE_STATS
1413 t->stats.null_node_hit++;
1414#endif
1415 goto backtrace;
1416 }
1417
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001418 if (IS_LEAF(n)) {
Ben Hutchings2e655572008-07-10 16:52:52 -07001419 ret = check_leaf(t, (struct leaf *)n, key, flp, res);
1420 if (ret > 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07001421 goto backtrace;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001422 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001423 }
1424
Olof Johansson91b9a272005-08-09 20:24:39 -07001425 cn = (struct tnode *)n;
1426
1427 /*
1428 * It's a tnode, and we can do some extra checks here if we
1429 * like, to avoid descending into a dead-end branch.
1430 * This tnode is in the parent's child array at index
1431 * key[p_pos..p_pos+p_bits] but potentially with some bits
1432 * chopped off, so in reality the index may be just a
1433 * subprefix, padded with zero at the end.
1434 * We can also take a look at any skipped bits in this
1435 * tnode - everything up to p_pos is supposed to be ok,
1436 * and the non-chopped bits of the index (se previous
1437 * paragraph) are also guaranteed ok, but the rest is
1438 * considered unknown.
1439 *
1440 * The skipped bits are key[pos+bits..cn->pos].
1441 */
1442
1443 /* If current_prefix_length < pos+bits, we are already doing
1444 * actual prefix matching, which means everything from
1445 * pos+(bits-chopped_off) onward must be zero along some
1446 * branch of this subtree - otherwise there is *no* valid
1447 * prefix present. Here we can only check the skipped
1448 * bits. Remember, since we have already indexed into the
1449 * parent's child array, we know that the bits we chopped of
1450 * *are* zero.
1451 */
1452
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001453 /* NOTA BENE: Checking only skipped bits
1454 for the new node here */
Olof Johansson91b9a272005-08-09 20:24:39 -07001455
1456 if (current_prefix_length < pos+bits) {
1457 if (tkey_extract_bits(cn->key, current_prefix_length,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001458 cn->pos - current_prefix_length)
1459 || !(cn->child[0]))
Olof Johansson91b9a272005-08-09 20:24:39 -07001460 goto backtrace;
1461 }
1462
1463 /*
1464 * If chopped_off=0, the index is fully validated and we
1465 * only need to look at the skipped bits for this, the new,
1466 * tnode. What we actually want to do is to find out if
1467 * these skipped bits match our key perfectly, or if we will
1468 * have to count on finding a matching prefix further down,
1469 * because if we do, we would like to have some way of
1470 * verifying the existence of such a prefix at this point.
1471 */
1472
1473 /* The only thing we can do at this point is to verify that
1474 * any such matching prefix can indeed be a prefix to our
1475 * key, and if the bits in the node we are inspecting that
1476 * do not match our key are not ZERO, this cannot be true.
1477 * Thus, find out where there is a mismatch (before cn->pos)
1478 * and verify that all the mismatching bits are zero in the
1479 * new tnode's key.
1480 */
1481
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001482 /*
1483 * Note: We aren't very concerned about the piece of
1484 * the key that precede pn->pos+pn->bits, since these
1485 * have already been checked. The bits after cn->pos
1486 * aren't checked since these are by definition
1487 * "unknown" at this point. Thus, what we want to see
1488 * is if we are about to enter the "prefix matching"
1489 * state, and in that case verify that the skipped
1490 * bits that will prevail throughout this subtree are
1491 * zero, as they have to be if we are to find a
1492 * matching prefix.
Olof Johansson91b9a272005-08-09 20:24:39 -07001493 */
1494
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001495 node_prefix = mask_pfx(cn->key, cn->pos);
1496 key_prefix = mask_pfx(key, cn->pos);
Olof Johansson91b9a272005-08-09 20:24:39 -07001497 pref_mismatch = key_prefix^node_prefix;
1498 mp = 0;
1499
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001500 /*
1501 * In short: If skipped bits in this node do not match
1502 * the search key, enter the "prefix matching"
1503 * state.directly.
Olof Johansson91b9a272005-08-09 20:24:39 -07001504 */
1505 if (pref_mismatch) {
1506 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1507 mp++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001508 pref_mismatch = pref_mismatch << 1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001509 }
1510 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1511
1512 if (key_prefix != 0)
1513 goto backtrace;
1514
1515 if (current_prefix_length >= cn->pos)
1516 current_prefix_length = mp;
1517 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001518
Olof Johansson91b9a272005-08-09 20:24:39 -07001519 pn = (struct tnode *)n; /* Descend */
1520 chopped_off = 0;
1521 continue;
1522
Robert Olsson19baf832005-06-21 12:43:18 -07001523backtrace:
1524 chopped_off++;
1525
1526 /* As zero don't change the child key (cindex) */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001527 while ((chopped_off <= pn->bits)
1528 && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001529 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001530
1531 /* Decrease current_... with bits chopped off */
1532 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001533 current_prefix_length = pn->pos + pn->bits
1534 - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001535
Robert Olsson19baf832005-06-21 12:43:18 -07001536 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001537 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001538 * chopped off all bits in this tnode walk up to our parent.
1539 */
1540
Olof Johansson91b9a272005-08-09 20:24:39 -07001541 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001542 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001543 } else {
Stephen Hemminger06801912007-08-10 15:22:13 -07001544 struct tnode *parent = node_parent((struct node *) pn);
1545 if (!parent)
Robert Olsson19baf832005-06-21 12:43:18 -07001546 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001547
Robert Olsson19baf832005-06-21 12:43:18 -07001548 /* Get Child's index */
Stephen Hemminger06801912007-08-10 15:22:13 -07001549 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1550 pn = parent;
Robert Olsson19baf832005-06-21 12:43:18 -07001551 chopped_off = 0;
1552
1553#ifdef CONFIG_IP_FIB_TRIE_STATS
1554 t->stats.backtrack++;
1555#endif
1556 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001557 }
Robert Olsson19baf832005-06-21 12:43:18 -07001558 }
1559failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001560 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001561found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001562 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001563 return ret;
1564}
1565
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001566/*
1567 * Remove the leaf and return parent.
1568 */
1569static void trie_leaf_remove(struct trie *t, struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001570{
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001571 struct tnode *tp = node_parent((struct node *) l);
Robert Olsson19baf832005-06-21 12:43:18 -07001572
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001573 pr_debug("entering trie_leaf_remove(%p)\n", l);
Robert Olsson19baf832005-06-21 12:43:18 -07001574
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001575 if (tp) {
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001576 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001577 put_child(t, (struct tnode *)tp, cindex, NULL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001578 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Olof Johansson91b9a272005-08-09 20:24:39 -07001579 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001580 rcu_assign_pointer(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001581
Stephen Hemminger387a5482008-04-10 03:47:34 -07001582 free_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001583}
1584
Robert Olssond562f1f2007-03-26 14:22:22 -07001585/*
1586 * Caller must hold RTNL.
1587 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001588static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001589{
1590 struct trie *t = (struct trie *) tb->tb_data;
1591 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001592 int plen = cfg->fc_dst_len;
1593 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001594 struct fib_alias *fa, *fa_to_delete;
1595 struct list_head *fa_head;
1596 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001597 struct leaf_info *li;
1598
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001599 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001600 return -EINVAL;
1601
Thomas Graf4e902c52006-08-17 18:14:52 -07001602 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001603 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001604
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001605 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001606 return -EINVAL;
1607
1608 key = key & mask;
1609 l = fib_find_node(t, key);
1610
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001611 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001612 return -ESRCH;
1613
1614 fa_head = get_fa_head(l, plen);
1615 fa = fib_find_alias(fa_head, tos, 0);
1616
1617 if (!fa)
1618 return -ESRCH;
1619
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001620 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001621
1622 fa_to_delete = NULL;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001623 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1624 list_for_each_entry_continue(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001625 struct fib_info *fi = fa->fa_info;
1626
1627 if (fa->fa_tos != tos)
1628 break;
1629
Thomas Graf4e902c52006-08-17 18:14:52 -07001630 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1631 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1632 fa->fa_scope == cfg->fc_scope) &&
1633 (!cfg->fc_protocol ||
1634 fi->fib_protocol == cfg->fc_protocol) &&
1635 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001636 fa_to_delete = fa;
1637 break;
1638 }
1639 }
1640
Olof Johansson91b9a272005-08-09 20:24:39 -07001641 if (!fa_to_delete)
1642 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001643
Olof Johansson91b9a272005-08-09 20:24:39 -07001644 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001645 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001646 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001647
Olof Johansson91b9a272005-08-09 20:24:39 -07001648 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001649 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001650
Robert Olsson2373ce12005-08-25 13:01:29 -07001651 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001652
Olof Johansson91b9a272005-08-09 20:24:39 -07001653 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001654 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001655 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001656 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001657
1658 if (hlist_empty(&l->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001659 trie_leaf_remove(t, l);
Olof Johansson91b9a272005-08-09 20:24:39 -07001660
1661 if (fa->fa_state & FA_S_ACCESSED)
Denis V. Lunev76e6ebf2008-07-05 19:00:44 -07001662 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001663
Robert Olsson2373ce12005-08-25 13:01:29 -07001664 fib_release_info(fa->fa_info);
1665 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001666 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001667}
1668
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001669static int trie_flush_list(struct list_head *head)
Robert Olsson19baf832005-06-21 12:43:18 -07001670{
1671 struct fib_alias *fa, *fa_node;
1672 int found = 0;
1673
1674 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1675 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001676
Robert Olsson2373ce12005-08-25 13:01:29 -07001677 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1678 list_del_rcu(&fa->fa_list);
1679 fib_release_info(fa->fa_info);
1680 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001681 found++;
1682 }
1683 }
1684 return found;
1685}
1686
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001687static int trie_flush_leaf(struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001688{
1689 int found = 0;
1690 struct hlist_head *lih = &l->list;
1691 struct hlist_node *node, *tmp;
1692 struct leaf_info *li = NULL;
1693
1694 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001695 found += trie_flush_list(&li->falh);
Robert Olsson19baf832005-06-21 12:43:18 -07001696
1697 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001698 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001699 free_leaf_info(li);
1700 }
1701 }
1702 return found;
1703}
1704
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001705/*
1706 * Scan for the next right leaf starting at node p->child[idx]
1707 * Since we have back pointer, no recursion necessary.
1708 */
1709static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)
Robert Olsson19baf832005-06-21 12:43:18 -07001710{
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001711 do {
1712 t_key idx;
Robert Olsson19baf832005-06-21 12:43:18 -07001713
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001714 if (c)
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001715 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001716 else
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001717 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001718
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001719 while (idx < 1u << p->bits) {
1720 c = tnode_get_child_rcu(p, idx++);
Robert Olsson2373ce12005-08-25 13:01:29 -07001721 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001722 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001723
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001724 if (IS_LEAF(c)) {
1725 prefetch(p->child[idx]);
1726 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001727 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001728
1729 /* Rescan start scanning in new node */
1730 p = (struct tnode *) c;
1731 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001732 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001733
1734 /* Node empty, walk back up to parent */
Olof Johansson91b9a272005-08-09 20:24:39 -07001735 c = (struct node *) p;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001736 } while ( (p = node_parent_rcu(c)) != NULL);
1737
1738 return NULL; /* Root of trie */
1739}
1740
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001741static struct leaf *trie_firstleaf(struct trie *t)
1742{
1743 struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
1744
1745 if (!n)
1746 return NULL;
1747
1748 if (IS_LEAF(n)) /* trie is just a leaf */
1749 return (struct leaf *) n;
1750
1751 return leaf_walk_rcu(n, NULL);
1752}
1753
1754static struct leaf *trie_nextleaf(struct leaf *l)
1755{
1756 struct node *c = (struct node *) l;
1757 struct tnode *p = node_parent(c);
1758
1759 if (!p)
1760 return NULL; /* trie with just one leaf */
1761
1762 return leaf_walk_rcu(p, c);
Robert Olsson19baf832005-06-21 12:43:18 -07001763}
1764
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001765static struct leaf *trie_leafindex(struct trie *t, int index)
1766{
1767 struct leaf *l = trie_firstleaf(t);
1768
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001769 while (l && index-- > 0)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001770 l = trie_nextleaf(l);
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001771
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001772 return l;
1773}
1774
1775
Robert Olssond562f1f2007-03-26 14:22:22 -07001776/*
1777 * Caller must hold RTNL.
1778 */
Robert Olsson19baf832005-06-21 12:43:18 -07001779static int fn_trie_flush(struct fib_table *tb)
1780{
1781 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001782 struct leaf *l, *ll = NULL;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001783 int found = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001784
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001785 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001786 found += trie_flush_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001787
1788 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001789 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001790 ll = l;
1791 }
1792
1793 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001794 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001795
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001796 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001797 return found;
1798}
1799
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001800static void fn_trie_select_default(struct fib_table *tb,
1801 const struct flowi *flp,
1802 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001803{
1804 struct trie *t = (struct trie *) tb->tb_data;
1805 int order, last_idx;
1806 struct fib_info *fi = NULL;
1807 struct fib_info *last_resort;
1808 struct fib_alias *fa = NULL;
1809 struct list_head *fa_head;
1810 struct leaf *l;
1811
1812 last_idx = -1;
1813 last_resort = NULL;
1814 order = -1;
1815
Robert Olsson2373ce12005-08-25 13:01:29 -07001816 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001817
Robert Olsson19baf832005-06-21 12:43:18 -07001818 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001819 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001820 goto out;
1821
1822 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001823 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001824 goto out;
1825
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001826 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001827 goto out;
1828
Robert Olsson2373ce12005-08-25 13:01:29 -07001829 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001830 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001831
Robert Olsson19baf832005-06-21 12:43:18 -07001832 if (fa->fa_scope != res->scope ||
1833 fa->fa_type != RTN_UNICAST)
1834 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001835
Robert Olsson19baf832005-06-21 12:43:18 -07001836 if (next_fi->fib_priority > res->fi->fib_priority)
1837 break;
1838 if (!next_fi->fib_nh[0].nh_gw ||
1839 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1840 continue;
1841 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001842
Robert Olsson19baf832005-06-21 12:43:18 -07001843 if (fi == NULL) {
1844 if (next_fi != res->fi)
1845 break;
1846 } else if (!fib_detect_death(fi, order, &last_resort,
Denis V. Lunev971b8932007-12-08 00:32:23 -08001847 &last_idx, tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001848 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001849 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001850 goto out;
1851 }
1852 fi = next_fi;
1853 order++;
1854 }
1855 if (order <= 0 || fi == NULL) {
Denis V. Lunev971b8932007-12-08 00:32:23 -08001856 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001857 goto out;
1858 }
1859
Denis V. Lunev971b8932007-12-08 00:32:23 -08001860 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1861 tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001862 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001863 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001864 goto out;
1865 }
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001866 if (last_idx >= 0)
1867 fib_result_assign(res, last_resort);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001868 tb->tb_default = last_idx;
1869out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001870 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001871}
1872
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001873static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1874 struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001875 struct sk_buff *skb, struct netlink_callback *cb)
1876{
1877 int i, s_i;
1878 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07001879 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001880
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001881 s_i = cb->args[5];
Robert Olsson19baf832005-06-21 12:43:18 -07001882 i = 0;
1883
Robert Olsson2373ce12005-08-25 13:01:29 -07001884 /* rcu_read_lock is hold by caller */
1885
1886 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001887 if (i < s_i) {
1888 i++;
1889 continue;
1890 }
Robert Olsson19baf832005-06-21 12:43:18 -07001891
1892 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1893 cb->nlh->nlmsg_seq,
1894 RTM_NEWROUTE,
1895 tb->tb_id,
1896 fa->fa_type,
1897 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001898 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001899 plen,
1900 fa->fa_tos,
Stephen Hemminger64347f72008-01-22 21:55:01 -08001901 fa->fa_info, NLM_F_MULTI) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001902 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001903 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001904 }
Robert Olsson19baf832005-06-21 12:43:18 -07001905 i++;
1906 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001907 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001908 return skb->len;
1909}
1910
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001911static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1912 struct sk_buff *skb, struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001913{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001914 struct leaf_info *li;
1915 struct hlist_node *node;
1916 int i, s_i;
Robert Olsson19baf832005-06-21 12:43:18 -07001917
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001918 s_i = cb->args[4];
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001919 i = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001920
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001921 /* rcu_read_lock is hold by caller */
1922 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1923 if (i < s_i) {
1924 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001925 continue;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001926 }
Robert Olsson19baf832005-06-21 12:43:18 -07001927
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001928 if (i > s_i)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001929 cb->args[5] = 0;
Olof Johansson91b9a272005-08-09 20:24:39 -07001930
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001931 if (list_empty(&li->falh))
Robert Olsson19baf832005-06-21 12:43:18 -07001932 continue;
1933
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001934 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001935 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001936 return -1;
1937 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001938 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001939 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001940
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001941 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001942 return skb->len;
1943}
1944
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001945static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
1946 struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001947{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001948 struct leaf *l;
Robert Olsson19baf832005-06-21 12:43:18 -07001949 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001950 t_key key = cb->args[2];
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001951 int count = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001952
Robert Olsson2373ce12005-08-25 13:01:29 -07001953 rcu_read_lock();
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001954 /* Dump starting at last key.
1955 * Note: 0.0.0.0/0 (ie default) is first key.
1956 */
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001957 if (count == 0)
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001958 l = trie_firstleaf(t);
1959 else {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001960 /* Normally, continue from last key, but if that is missing
1961 * fallback to using slow rescan
1962 */
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001963 l = fib_find_node(t, key);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001964 if (!l)
1965 l = trie_leafindex(t, count);
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001966 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001967
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001968 while (l) {
1969 cb->args[2] = l->key;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001970 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001971 cb->args[3] = count;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001972 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001973 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001974 }
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001975
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001976 ++count;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001977 l = trie_nextleaf(l);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001978 memset(&cb->args[4], 0,
1979 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001980 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001981 cb->args[3] = count;
Robert Olsson2373ce12005-08-25 13:01:29 -07001982 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001983
Robert Olsson19baf832005-06-21 12:43:18 -07001984 return skb->len;
Robert Olsson19baf832005-06-21 12:43:18 -07001985}
1986
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001987void __init fib_hash_init(void)
1988{
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001989 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1990 sizeof(struct fib_alias),
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08001991 0, SLAB_PANIC, NULL);
1992
1993 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1994 max(sizeof(struct leaf),
1995 sizeof(struct leaf_info)),
1996 0, SLAB_PANIC, NULL);
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001997}
Robert Olsson19baf832005-06-21 12:43:18 -07001998
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001999
2000/* Fix more generic FIB names for init later */
2001struct fib_table *fib_hash_table(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07002002{
2003 struct fib_table *tb;
2004 struct trie *t;
2005
Robert Olsson19baf832005-06-21 12:43:18 -07002006 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2007 GFP_KERNEL);
2008 if (tb == NULL)
2009 return NULL;
2010
2011 tb->tb_id = id;
Denis V. Lunev971b8932007-12-08 00:32:23 -08002012 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07002013 tb->tb_lookup = fn_trie_lookup;
2014 tb->tb_insert = fn_trie_insert;
2015 tb->tb_delete = fn_trie_delete;
2016 tb->tb_flush = fn_trie_flush;
2017 tb->tb_select_default = fn_trie_select_default;
2018 tb->tb_dump = fn_trie_dump;
Robert Olsson19baf832005-06-21 12:43:18 -07002019
2020 t = (struct trie *) tb->tb_data;
Stephen Hemmingerc28a1cf2008-01-12 20:49:13 -08002021 memset(t, 0, sizeof(*t));
Robert Olsson19baf832005-06-21 12:43:18 -07002022
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002023 if (id == RT_TABLE_LOCAL)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002024 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07002025
2026 return tb;
2027}
2028
Robert Olsson19baf832005-06-21 12:43:18 -07002029#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002030/* Depth first Trie walk iterator */
2031struct fib_trie_iter {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002032 struct seq_net_private p;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002033 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002034 struct tnode *tnode;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002035 unsigned index;
2036 unsigned depth;
2037};
Robert Olsson19baf832005-06-21 12:43:18 -07002038
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002039static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002040{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002041 struct tnode *tn = iter->tnode;
2042 unsigned cindex = iter->index;
2043 struct tnode *p;
2044
Eric W. Biederman6640e692007-01-24 14:42:04 -08002045 /* A single entry routing table */
2046 if (!tn)
2047 return NULL;
2048
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002049 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2050 iter->tnode, iter->index, iter->depth);
2051rescan:
2052 while (cindex < (1<<tn->bits)) {
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002053 struct node *n = tnode_get_child_rcu(tn, cindex);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002054
2055 if (n) {
2056 if (IS_LEAF(n)) {
2057 iter->tnode = tn;
2058 iter->index = cindex + 1;
2059 } else {
2060 /* push down one level */
2061 iter->tnode = (struct tnode *) n;
2062 iter->index = 0;
2063 ++iter->depth;
2064 }
2065 return n;
2066 }
2067
2068 ++cindex;
2069 }
2070
2071 /* Current node exhausted, pop back up */
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002072 p = node_parent_rcu((struct node *)tn);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002073 if (p) {
2074 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2075 tn = p;
2076 --iter->depth;
2077 goto rescan;
2078 }
2079
2080 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002081 return NULL;
2082}
2083
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002084static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2085 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002086{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002087 struct node *n;
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002088
Stephen Hemminger132adf52007-03-08 20:44:43 -08002089 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002090 return NULL;
2091
2092 n = rcu_dereference(t->trie);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002093 if (!n)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002094 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002095
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002096 if (IS_TNODE(n)) {
2097 iter->tnode = (struct tnode *) n;
2098 iter->index = 0;
2099 iter->depth = 1;
2100 } else {
2101 iter->tnode = NULL;
2102 iter->index = 0;
2103 iter->depth = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002104 }
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002105
2106 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002107}
2108
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002109static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002110{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002111 struct node *n;
2112 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002113
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002114 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002115
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002116 rcu_read_lock();
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002117 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002118 if (IS_LEAF(n)) {
Stephen Hemminger93672292008-01-22 21:54:05 -08002119 struct leaf *l = (struct leaf *)n;
2120 struct leaf_info *li;
2121 struct hlist_node *tmp;
2122
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002123 s->leaves++;
2124 s->totdepth += iter.depth;
2125 if (iter.depth > s->maxdepth)
2126 s->maxdepth = iter.depth;
Stephen Hemminger93672292008-01-22 21:54:05 -08002127
2128 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2129 ++s->prefixes;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002130 } else {
2131 const struct tnode *tn = (const struct tnode *) n;
2132 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002133
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002134 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002135 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002136 s->nodesizes[tn->bits]++;
2137
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002138 for (i = 0; i < (1<<tn->bits); i++)
2139 if (!tn->child[i])
2140 s->nullpointers++;
2141 }
2142 }
2143 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002144}
2145
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002146/*
Robert Olsson19baf832005-06-21 12:43:18 -07002147 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002148 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002149static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002150{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002151 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002152
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002153 if (stat->leaves)
2154 avdepth = stat->totdepth*100 / stat->leaves;
2155 else
2156 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002157
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002158 seq_printf(seq, "\tAver depth: %u.%02d\n",
2159 avdepth / 100, avdepth % 100);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002160 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002161
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002162 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002163 bytes = sizeof(struct leaf) * stat->leaves;
Stephen Hemminger93672292008-01-22 21:54:05 -08002164
2165 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2166 bytes += sizeof(struct leaf_info) * stat->prefixes;
2167
Stephen Hemminger187b5182008-01-12 20:55:55 -08002168 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002169 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002170
Robert Olsson06ef9212006-03-20 21:35:01 -08002171 max = MAX_STAT_DEPTH;
2172 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002173 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002174
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002175 pointers = 0;
2176 for (i = 1; i <= max; i++)
2177 if (stat->nodesizes[i] != 0) {
Stephen Hemminger187b5182008-01-12 20:55:55 -08002178 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002179 pointers += (1<<i) * stat->nodesizes[i];
2180 }
2181 seq_putc(seq, '\n');
Stephen Hemminger187b5182008-01-12 20:55:55 -08002182 seq_printf(seq, "\tPointers: %u\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002183
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002184 bytes += sizeof(struct node *) * pointers;
Stephen Hemminger187b5182008-01-12 20:55:55 -08002185 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2186 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002187}
Robert Olsson19baf832005-06-21 12:43:18 -07002188
2189#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002190static void trie_show_usage(struct seq_file *seq,
2191 const struct trie_use_stats *stats)
2192{
2193 seq_printf(seq, "\nCounters:\n---------\n");
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002194 seq_printf(seq, "gets = %u\n", stats->gets);
2195 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2196 seq_printf(seq, "semantic match passed = %u\n",
2197 stats->semantic_match_passed);
2198 seq_printf(seq, "semantic match miss = %u\n",
2199 stats->semantic_match_miss);
2200 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2201 seq_printf(seq, "skipped node resize = %u\n\n",
2202 stats->resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002203}
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002204#endif /* CONFIG_IP_FIB_TRIE_STATS */
2205
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002206static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002207{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002208 if (tb->tb_id == RT_TABLE_LOCAL)
2209 seq_puts(seq, "Local:\n");
2210 else if (tb->tb_id == RT_TABLE_MAIN)
2211 seq_puts(seq, "Main:\n");
2212 else
2213 seq_printf(seq, "Id %d:\n", tb->tb_id);
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002214}
Robert Olsson19baf832005-06-21 12:43:18 -07002215
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002216
Robert Olsson19baf832005-06-21 12:43:18 -07002217static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2218{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002219 struct net *net = (struct net *)seq->private;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002220 unsigned int h;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002221
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002222 seq_printf(seq,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002223 "Basic info: size of leaf:"
2224 " %Zd bytes, size of tnode: %Zd bytes.\n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002225 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002226
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002227 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2228 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2229 struct hlist_node *node;
2230 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002231
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002232 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2233 struct trie *t = (struct trie *) tb->tb_data;
2234 struct trie_stat stat;
2235
2236 if (!t)
2237 continue;
2238
2239 fib_table_print(seq, tb);
2240
2241 trie_collect_stats(t, &stat);
2242 trie_show_stats(seq, &stat);
2243#ifdef CONFIG_IP_FIB_TRIE_STATS
2244 trie_show_usage(seq, &t->stats);
2245#endif
2246 }
2247 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002248
Robert Olsson19baf832005-06-21 12:43:18 -07002249 return 0;
2250}
2251
Robert Olsson19baf832005-06-21 12:43:18 -07002252static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2253{
Pavel Emelyanovde05c552008-07-18 04:07:21 -07002254 return single_open_net(inode, file, fib_triestat_seq_show);
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002255}
2256
Arjan van de Ven9a321442007-02-12 00:55:35 -08002257static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002258 .owner = THIS_MODULE,
2259 .open = fib_triestat_seq_open,
2260 .read = seq_read,
2261 .llseek = seq_lseek,
Pavel Emelyanovb6fcbdb2008-07-18 04:07:44 -07002262 .release = single_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002263};
2264
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002265static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002266{
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002267 struct fib_trie_iter *iter = seq->private;
2268 struct net *net = seq_file_net(seq);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002269 loff_t idx = 0;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002270 unsigned int h;
Robert Olsson19baf832005-06-21 12:43:18 -07002271
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002272 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2273 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2274 struct hlist_node *node;
2275 struct fib_table *tb;
2276
2277 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2278 struct node *n;
2279
2280 for (n = fib_trie_get_first(iter,
2281 (struct trie *) tb->tb_data);
2282 n; n = fib_trie_get_next(iter))
2283 if (pos == idx++) {
2284 iter->tb = tb;
2285 return n;
2286 }
2287 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002288 }
Robert Olsson19baf832005-06-21 12:43:18 -07002289
Robert Olsson19baf832005-06-21 12:43:18 -07002290 return NULL;
2291}
2292
2293static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002294 __acquires(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002295{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002296 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002297 return fib_trie_get_idx(seq, *pos);
Robert Olsson19baf832005-06-21 12:43:18 -07002298}
2299
2300static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2301{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002302 struct fib_trie_iter *iter = seq->private;
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002303 struct net *net = seq_file_net(seq);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002304 struct fib_table *tb = iter->tb;
2305 struct hlist_node *tb_node;
2306 unsigned int h;
2307 struct node *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002308
Robert Olsson19baf832005-06-21 12:43:18 -07002309 ++*pos;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002310 /* next node in same table */
2311 n = fib_trie_get_next(iter);
2312 if (n)
2313 return n;
Olof Johansson91b9a272005-08-09 20:24:39 -07002314
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002315 /* walk rest of this hash chain */
2316 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2317 while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
2318 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2319 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2320 if (n)
2321 goto found;
2322 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002323
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002324 /* new hash chain */
2325 while (++h < FIB_TABLE_HASHSZ) {
2326 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2327 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2328 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2329 if (n)
2330 goto found;
2331 }
2332 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002333 return NULL;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002334
2335found:
2336 iter->tb = tb;
2337 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002338}
2339
2340static void fib_trie_seq_stop(struct seq_file *seq, void *v)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002341 __releases(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002342{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002343 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002344}
2345
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002346static void seq_indent(struct seq_file *seq, int n)
2347{
2348 while (n-- > 0) seq_puts(seq, " ");
2349}
Robert Olsson19baf832005-06-21 12:43:18 -07002350
Eric Dumazet28d36e32008-01-14 23:09:56 -08002351static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002352{
Stephen Hemminger132adf52007-03-08 20:44:43 -08002353 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002354 case RT_SCOPE_UNIVERSE: return "universe";
2355 case RT_SCOPE_SITE: return "site";
2356 case RT_SCOPE_LINK: return "link";
2357 case RT_SCOPE_HOST: return "host";
2358 case RT_SCOPE_NOWHERE: return "nowhere";
2359 default:
Eric Dumazet28d36e32008-01-14 23:09:56 -08002360 snprintf(buf, len, "scope=%d", s);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002361 return buf;
2362 }
2363}
2364
2365static const char *rtn_type_names[__RTN_MAX] = {
2366 [RTN_UNSPEC] = "UNSPEC",
2367 [RTN_UNICAST] = "UNICAST",
2368 [RTN_LOCAL] = "LOCAL",
2369 [RTN_BROADCAST] = "BROADCAST",
2370 [RTN_ANYCAST] = "ANYCAST",
2371 [RTN_MULTICAST] = "MULTICAST",
2372 [RTN_BLACKHOLE] = "BLACKHOLE",
2373 [RTN_UNREACHABLE] = "UNREACHABLE",
2374 [RTN_PROHIBIT] = "PROHIBIT",
2375 [RTN_THROW] = "THROW",
2376 [RTN_NAT] = "NAT",
2377 [RTN_XRESOLVE] = "XRESOLVE",
2378};
2379
Eric Dumazet28d36e32008-01-14 23:09:56 -08002380static inline const char *rtn_type(char *buf, size_t len, unsigned t)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002381{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002382 if (t < __RTN_MAX && rtn_type_names[t])
2383 return rtn_type_names[t];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002384 snprintf(buf, len, "type %u", t);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002385 return buf;
2386}
2387
2388/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002389static int fib_trie_seq_show(struct seq_file *seq, void *v)
2390{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002391 const struct fib_trie_iter *iter = seq->private;
2392 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002393
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002394 if (!node_parent_rcu(n))
2395 fib_table_print(seq, iter->tb);
Robert Olsson095b8502007-01-26 19:06:01 -08002396
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002397 if (IS_TNODE(n)) {
2398 struct tnode *tn = (struct tnode *) n;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07002399 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002400
Robert Olsson1d25cd62005-09-19 15:29:52 -07002401 seq_indent(seq, iter->depth-1);
YOSHIFUJI Hideakia7d632b2008-04-14 04:09:00 -07002402 seq_printf(seq, " +-- " NIPQUAD_FMT "/%d %d %d %d\n",
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002403 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002404 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002405
Olof Johansson91b9a272005-08-09 20:24:39 -07002406 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002407 struct leaf *l = (struct leaf *) n;
Stephen Hemminger13280422008-01-22 21:54:37 -08002408 struct leaf_info *li;
2409 struct hlist_node *node;
Al Viro32ab5f82006-09-26 22:21:45 -07002410 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002411
2412 seq_indent(seq, iter->depth);
YOSHIFUJI Hideakia7d632b2008-04-14 04:09:00 -07002413 seq_printf(seq, " |-- " NIPQUAD_FMT "\n", NIPQUAD(val));
Eric Dumazet28d36e32008-01-14 23:09:56 -08002414
Stephen Hemminger13280422008-01-22 21:54:37 -08002415 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2416 struct fib_alias *fa;
Eric Dumazet28d36e32008-01-14 23:09:56 -08002417
Stephen Hemminger13280422008-01-22 21:54:37 -08002418 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2419 char buf1[32], buf2[32];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002420
Stephen Hemminger13280422008-01-22 21:54:37 -08002421 seq_indent(seq, iter->depth+1);
2422 seq_printf(seq, " /%d %s %s", li->plen,
2423 rtn_scope(buf1, sizeof(buf1),
2424 fa->fa_scope),
2425 rtn_type(buf2, sizeof(buf2),
2426 fa->fa_type));
2427 if (fa->fa_tos)
Denis V. Lunevb9c4d822008-02-05 02:58:45 -08002428 seq_printf(seq, " tos=%d", fa->fa_tos);
Stephen Hemminger13280422008-01-22 21:54:37 -08002429 seq_putc(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002430 }
2431 }
Robert Olsson19baf832005-06-21 12:43:18 -07002432 }
2433
2434 return 0;
2435}
2436
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002437static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002438 .start = fib_trie_seq_start,
2439 .next = fib_trie_seq_next,
2440 .stop = fib_trie_seq_stop,
2441 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002442};
2443
2444static int fib_trie_seq_open(struct inode *inode, struct file *file)
2445{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002446 return seq_open_net(inode, file, &fib_trie_seq_ops,
2447 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002448}
2449
Arjan van de Ven9a321442007-02-12 00:55:35 -08002450static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002451 .owner = THIS_MODULE,
2452 .open = fib_trie_seq_open,
2453 .read = seq_read,
2454 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002455 .release = seq_release_net,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002456};
2457
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002458struct fib_route_iter {
2459 struct seq_net_private p;
2460 struct trie *main_trie;
2461 loff_t pos;
2462 t_key key;
2463};
2464
2465static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2466{
2467 struct leaf *l = NULL;
2468 struct trie *t = iter->main_trie;
2469
2470 /* use cache location of last found key */
2471 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2472 pos -= iter->pos;
2473 else {
2474 iter->pos = 0;
2475 l = trie_firstleaf(t);
2476 }
2477
2478 while (l && pos-- > 0) {
2479 iter->pos++;
2480 l = trie_nextleaf(l);
2481 }
2482
2483 if (l)
2484 iter->key = pos; /* remember it */
2485 else
2486 iter->pos = 0; /* forget it */
2487
2488 return l;
2489}
2490
2491static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2492 __acquires(RCU)
2493{
2494 struct fib_route_iter *iter = seq->private;
2495 struct fib_table *tb;
2496
2497 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002498 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002499 if (!tb)
2500 return NULL;
2501
2502 iter->main_trie = (struct trie *) tb->tb_data;
2503 if (*pos == 0)
2504 return SEQ_START_TOKEN;
2505 else
2506 return fib_route_get_idx(iter, *pos - 1);
2507}
2508
2509static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2510{
2511 struct fib_route_iter *iter = seq->private;
2512 struct leaf *l = v;
2513
2514 ++*pos;
2515 if (v == SEQ_START_TOKEN) {
2516 iter->pos = 0;
2517 l = trie_firstleaf(iter->main_trie);
2518 } else {
2519 iter->pos++;
2520 l = trie_nextleaf(l);
2521 }
2522
2523 if (l)
2524 iter->key = l->key;
2525 else
2526 iter->pos = 0;
2527 return l;
2528}
2529
2530static void fib_route_seq_stop(struct seq_file *seq, void *v)
2531 __releases(RCU)
2532{
2533 rcu_read_unlock();
2534}
2535
Al Viro32ab5f82006-09-26 22:21:45 -07002536static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002537{
2538 static unsigned type2flags[RTN_MAX + 1] = {
2539 [7] = RTF_REJECT, [8] = RTF_REJECT,
2540 };
2541 unsigned flags = type2flags[type];
2542
2543 if (fi && fi->fib_nh->nh_gw)
2544 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002545 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002546 flags |= RTF_HOST;
2547 flags |= RTF_UP;
2548 return flags;
2549}
2550
2551/*
2552 * This outputs /proc/net/route.
2553 * The format of the file is not supposed to be changed
2554 * and needs to be same as fib_hash output to avoid breaking
2555 * legacy utilities
2556 */
2557static int fib_route_seq_show(struct seq_file *seq, void *v)
2558{
2559 struct leaf *l = v;
Stephen Hemminger13280422008-01-22 21:54:37 -08002560 struct leaf_info *li;
2561 struct hlist_node *node;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002562
2563 if (v == SEQ_START_TOKEN) {
2564 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2565 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2566 "\tWindow\tIRTT");
2567 return 0;
2568 }
2569
Stephen Hemminger13280422008-01-22 21:54:37 -08002570 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002571 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002572 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002573
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002574 mask = inet_make_mask(li->plen);
2575 prefix = htonl(l->key);
2576
2577 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002578 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002579 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002580 int len;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002581
2582 if (fa->fa_type == RTN_BROADCAST
2583 || fa->fa_type == RTN_MULTICAST)
2584 continue;
2585
2586 if (fi)
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002587 seq_printf(seq,
2588 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2589 "%d\t%08X\t%d\t%u\t%u%n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002590 fi->fib_dev ? fi->fib_dev->name : "*",
2591 prefix,
2592 fi->fib_nh->nh_gw, flags, 0, 0,
2593 fi->fib_priority,
2594 mask,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002595 (fi->fib_advmss ?
2596 fi->fib_advmss + 40 : 0),
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002597 fi->fib_window,
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002598 fi->fib_rtt >> 3, &len);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002599 else
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002600 seq_printf(seq,
2601 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2602 "%d\t%08X\t%d\t%u\t%u%n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002603 prefix, 0, flags, 0, 0, 0,
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002604 mask, 0, 0, 0, &len);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002605
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002606 seq_printf(seq, "%*s\n", 127 - len, "");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002607 }
2608 }
2609
2610 return 0;
2611}
2612
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002613static const struct seq_operations fib_route_seq_ops = {
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002614 .start = fib_route_seq_start,
2615 .next = fib_route_seq_next,
2616 .stop = fib_route_seq_stop,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002617 .show = fib_route_seq_show,
2618};
2619
2620static int fib_route_seq_open(struct inode *inode, struct file *file)
2621{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002622 return seq_open_net(inode, file, &fib_route_seq_ops,
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002623 sizeof(struct fib_route_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002624}
2625
Arjan van de Ven9a321442007-02-12 00:55:35 -08002626static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002627 .owner = THIS_MODULE,
2628 .open = fib_route_seq_open,
2629 .read = seq_read,
2630 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002631 .release = seq_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002632};
2633
Denis V. Lunev61a02652008-01-10 03:21:09 -08002634int __net_init fib_proc_init(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002635{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002636 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002637 goto out1;
2638
Denis V. Lunev61a02652008-01-10 03:21:09 -08002639 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2640 &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002641 goto out2;
2642
Denis V. Lunev61a02652008-01-10 03:21:09 -08002643 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002644 goto out3;
2645
Robert Olsson19baf832005-06-21 12:43:18 -07002646 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002647
2648out3:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002649 proc_net_remove(net, "fib_triestat");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002650out2:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002651 proc_net_remove(net, "fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002652out1:
2653 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002654}
2655
Denis V. Lunev61a02652008-01-10 03:21:09 -08002656void __net_exit fib_proc_exit(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002657{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002658 proc_net_remove(net, "fib_trie");
2659 proc_net_remove(net, "fib_triestat");
2660 proc_net_remove(net, "route");
Robert Olsson19baf832005-06-21 12:43:18 -07002661}
2662
2663#endif /* CONFIG_PROC_FS */