blob: 291bdf50a21f82b2ea1b0c64b638a3e14d877dcb [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
Jens Låås80b71b82009-08-28 23:57:15 -070051#define VERSION "0.409"
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 Dumazet8d9654442008-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 Dumazet8d9654442008-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 Dumazet8d9654442008-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 Dumazet8d9654442008-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;
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700126 struct tnode *tnode_free;
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700127 };
Olof Johansson91b9a272005-08-09 20:24:39 -0700128 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700129};
130
131#ifdef CONFIG_IP_FIB_TRIE_STATS
132struct trie_use_stats {
133 unsigned int gets;
134 unsigned int backtrack;
135 unsigned int semantic_match_passed;
136 unsigned int semantic_match_miss;
137 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700138 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700139};
140#endif
141
142struct trie_stat {
143 unsigned int totdepth;
144 unsigned int maxdepth;
145 unsigned int tnodes;
146 unsigned int leaves;
147 unsigned int nullpointers;
Stephen Hemminger93672292008-01-22 21:54:05 -0800148 unsigned int prefixes;
Robert Olsson06ef9212006-03-20 21:35:01 -0800149 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700150};
Robert Olsson19baf832005-06-21 12:43:18 -0700151
152struct trie {
Olof Johansson91b9a272005-08-09 20:24:39 -0700153 struct node *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700154#ifdef CONFIG_IP_FIB_TRIE_STATS
155 struct trie_use_stats stats;
156#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700157};
158
Robert Olsson19baf832005-06-21 12:43:18 -0700159static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800160static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
161 int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700162static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700163static struct tnode *inflate(struct trie *t, struct tnode *tn);
164static struct tnode *halve(struct trie *t, struct tnode *tn);
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700165/* tnodes to free after resize(); protected by RTNL */
166static struct tnode *tnode_free_head;
Jarek Poplawskic3059472009-07-14 08:33:08 +0000167static size_t tnode_free_size;
168
169/*
170 * synchronize_rcu after call_rcu for that many pages; it should be especially
171 * useful before resizing the root node with PREEMPT_NONE configs; the value was
172 * obtained experimentally, aiming to avoid visible slowdown.
173 */
174static const int sync_pages = 128;
Robert Olsson19baf832005-06-21 12:43:18 -0700175
Christoph Lametere18b8902006-12-06 20:33:20 -0800176static struct kmem_cache *fn_alias_kmem __read_mostly;
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800177static struct kmem_cache *trie_leaf_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700178
Stephen Hemminger06801912007-08-10 15:22:13 -0700179static inline struct tnode *node_parent(struct node *node)
180{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800181 return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
182}
Stephen Hemminger06801912007-08-10 15:22:13 -0700183
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800184static inline struct tnode *node_parent_rcu(struct node *node)
185{
186 struct tnode *ret = node_parent(node);
187
Stephen Hemminger06801912007-08-10 15:22:13 -0700188 return rcu_dereference(ret);
189}
190
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700191/* Same as rcu_assign_pointer
192 * but that macro() assumes that value is a pointer.
193 */
Stephen Hemminger06801912007-08-10 15:22:13 -0700194static inline void node_set_parent(struct node *node, struct tnode *ptr)
195{
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700196 smp_wmb();
197 node->parent = (unsigned long)ptr | NODE_TYPE(node);
Stephen Hemminger06801912007-08-10 15:22:13 -0700198}
Robert Olsson2373ce12005-08-25 13:01:29 -0700199
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800200static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700201{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800202 BUG_ON(i >= 1U << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700203
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800204 return tn->child[i];
205}
206
207static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
208{
209 struct node *ret = tnode_get_child(tn, i);
210
211 return rcu_dereference(ret);
Robert Olsson19baf832005-06-21 12:43:18 -0700212}
213
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700214static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700215{
Olof Johansson91b9a272005-08-09 20:24:39 -0700216 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700217}
218
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700219static inline t_key mask_pfx(t_key k, unsigned short l)
220{
221 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
222}
223
Robert Olsson19baf832005-06-21 12:43:18 -0700224static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
225{
Olof Johansson91b9a272005-08-09 20:24:39 -0700226 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700227 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700228 else
Robert Olsson19baf832005-06-21 12:43:18 -0700229 return 0;
230}
231
232static inline int tkey_equals(t_key a, t_key b)
233{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700234 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700235}
236
237static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
238{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700239 if (bits == 0 || offset >= KEYLENGTH)
240 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700241 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
242 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700243}
Robert Olsson19baf832005-06-21 12:43:18 -0700244
245static inline int tkey_mismatch(t_key a, int offset, t_key b)
246{
247 t_key diff = a ^ b;
248 int i = offset;
249
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700250 if (!diff)
251 return 0;
252 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700253 i++;
254 return i;
255}
256
Robert Olsson19baf832005-06-21 12:43:18 -0700257/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900258 To understand this stuff, an understanding of keys and all their bits is
259 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700260 all of the bits in that key are significant.
261
262 Consider a node 'n' and its parent 'tp'.
263
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900264 If n is a leaf, every bit in its key is significant. Its presence is
265 necessitated by path compression, since during a tree traversal (when
266 searching for a leaf - unless we are doing an insertion) we will completely
267 ignore all skipped bits we encounter. Thus we need to verify, at the end of
268 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700269 correct key path.
270
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900271 Note that we can never "miss" the correct key in the tree if present by
272 following the wrong path. Path compression ensures that segments of the key
273 that are the same for all keys with a given prefix are skipped, but the
274 skipped part *is* identical for each node in the subtrie below the skipped
275 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700276 call to tkey_sub_equals() in trie_insert().
277
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900278 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700279 have many different meanings.
280
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900281 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700282 _________________________________________________________________
283 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
284 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900285 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700286
287 _________________________________________________________________
288 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
289 -----------------------------------------------------------------
290 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
291
292 tp->pos = 7
293 tp->bits = 3
294 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700295 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700296
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900297 First, let's just ignore the bits that come before the parent tp, that is
298 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700299 not use them for anything.
300
301 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900302 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700303 'n' among tp's children.
304
305 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
306 for the node n.
307
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900308 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700309 of the bits are really not needed or indeed known in n->key.
310
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900311 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700312 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900313
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700314
Robert Olsson19baf832005-06-21 12:43:18 -0700315 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
316 at this point.
317
318*/
319
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700320static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700321{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700322 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700323}
324
Denis V. Lunevf5026fa2007-12-13 09:47:57 -0800325static const int halve_threshold = 25;
326static const int inflate_threshold = 50;
Jarek Poplawski345aa032009-07-07 19:39:16 -0700327static const int halve_threshold_root = 15;
Jens Låås80b71b82009-08-28 23:57:15 -0700328static const int inflate_threshold_root = 30;
Robert Olsson2373ce12005-08-25 13:01:29 -0700329
330static void __alias_free_mem(struct rcu_head *head)
331{
332 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
333 kmem_cache_free(fn_alias_kmem, fa);
334}
335
336static inline void alias_free_mem_rcu(struct fib_alias *fa)
337{
338 call_rcu(&fa->rcu, __alias_free_mem);
339}
340
341static void __leaf_free_rcu(struct rcu_head *head)
342{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800343 struct leaf *l = container_of(head, struct leaf, rcu);
344 kmem_cache_free(trie_leaf_kmem, l);
Robert Olsson2373ce12005-08-25 13:01:29 -0700345}
346
Stephen Hemminger387a5482008-04-10 03:47:34 -0700347static inline void free_leaf(struct leaf *l)
348{
349 call_rcu_bh(&l->rcu, __leaf_free_rcu);
350}
351
Robert Olsson2373ce12005-08-25 13:01:29 -0700352static void __leaf_info_free_rcu(struct rcu_head *head)
353{
354 kfree(container_of(head, struct leaf_info, rcu));
355}
356
357static inline void free_leaf_info(struct leaf_info *leaf)
358{
359 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
360}
361
Eric Dumazet8d9654442008-01-13 22:31:44 -0800362static struct tnode *tnode_alloc(size_t size)
Robert Olsson2373ce12005-08-25 13:01:29 -0700363{
Robert Olsson2373ce12005-08-25 13:01:29 -0700364 if (size <= PAGE_SIZE)
Eric Dumazet8d9654442008-01-13 22:31:44 -0800365 return kzalloc(size, GFP_KERNEL);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700366 else
367 return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
368}
Robert Olsson2373ce12005-08-25 13:01:29 -0700369
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700370static void __tnode_vfree(struct work_struct *arg)
371{
372 struct tnode *tn = container_of(arg, struct tnode, work);
373 vfree(tn);
Robert Olsson2373ce12005-08-25 13:01:29 -0700374}
375
376static void __tnode_free_rcu(struct rcu_head *head)
377{
378 struct tnode *tn = container_of(head, struct tnode, rcu);
Eric Dumazet8d9654442008-01-13 22:31:44 -0800379 size_t size = sizeof(struct tnode) +
380 (sizeof(struct node *) << tn->bits);
Robert Olsson2373ce12005-08-25 13:01:29 -0700381
382 if (size <= PAGE_SIZE)
383 kfree(tn);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700384 else {
385 INIT_WORK(&tn->work, __tnode_vfree);
386 schedule_work(&tn->work);
387 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700388}
389
390static inline void tnode_free(struct tnode *tn)
391{
Stephen Hemminger387a5482008-04-10 03:47:34 -0700392 if (IS_LEAF(tn))
393 free_leaf((struct leaf *) tn);
394 else
Robert Olsson550e29b2006-04-04 12:53:35 -0700395 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700396}
397
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700398static void tnode_free_safe(struct tnode *tn)
399{
400 BUG_ON(IS_LEAF(tn));
Jarek Poplawski7b855762009-06-18 00:28:51 -0700401 tn->tnode_free = tnode_free_head;
402 tnode_free_head = tn;
Jarek Poplawskic3059472009-07-14 08:33:08 +0000403 tnode_free_size += sizeof(struct tnode) +
404 (sizeof(struct node *) << tn->bits);
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700405}
406
407static void tnode_free_flush(void)
408{
409 struct tnode *tn;
410
411 while ((tn = tnode_free_head)) {
412 tnode_free_head = tn->tnode_free;
413 tn->tnode_free = NULL;
414 tnode_free(tn);
415 }
Jarek Poplawskic3059472009-07-14 08:33:08 +0000416
417 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
418 tnode_free_size = 0;
419 synchronize_rcu();
420 }
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700421}
422
Robert Olsson19baf832005-06-21 12:43:18 -0700423static struct leaf *leaf_new(void)
424{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800425 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700426 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700427 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700428 INIT_HLIST_HEAD(&l->list);
429 }
430 return l;
431}
432
433static struct leaf_info *leaf_info_new(int plen)
434{
435 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700436 if (li) {
437 li->plen = plen;
438 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700439 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700440 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700441}
442
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800443static struct tnode *tnode_new(t_key key, int pos, int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700444{
Eric Dumazet8d9654442008-01-13 22:31:44 -0800445 size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700446 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700447
Olof Johansson91b9a272005-08-09 20:24:39 -0700448 if (tn) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700449 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700450 tn->pos = pos;
451 tn->bits = bits;
452 tn->key = key;
453 tn->full_children = 0;
454 tn->empty_children = 1<<bits;
455 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700456
Eric Dumazet8d9654442008-01-13 22:31:44 -0800457 pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
458 (unsigned long) (sizeof(struct node) << bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700459 return tn;
460}
461
Robert Olsson19baf832005-06-21 12:43:18 -0700462/*
463 * Check whether a tnode 'n' is "full", i.e. it is an internal node
464 * and no bits are skipped. See discussion in dyntree paper p. 6
465 */
466
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700467static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700468{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700469 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700470 return 0;
471
472 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
473}
474
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800475static inline void put_child(struct trie *t, struct tnode *tn, int i,
476 struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700477{
478 tnode_put_child_reorg(tn, i, n, -1);
479}
480
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700481 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700482 * Add a child at position i overwriting the old value.
483 * Update the value of full_children and empty_children.
484 */
485
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800486static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
487 int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700488{
Robert Olsson2373ce12005-08-25 13:01:29 -0700489 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700490 int isfull;
491
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700492 BUG_ON(i >= 1<<tn->bits);
493
Robert Olsson19baf832005-06-21 12:43:18 -0700494 /* update emptyChildren */
495 if (n == NULL && chi != NULL)
496 tn->empty_children++;
497 else if (n != NULL && chi == NULL)
498 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700499
Robert Olsson19baf832005-06-21 12:43:18 -0700500 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700501 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700502 wasfull = tnode_full(tn, chi);
503
504 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700505 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700506 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700507 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700508 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700509
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700510 if (n)
Stephen Hemminger06801912007-08-10 15:22:13 -0700511 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700512
Robert Olsson2373ce12005-08-25 13:01:29 -0700513 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700514}
515
Jens Låås80b71b82009-08-28 23:57:15 -0700516#define MAX_WORK 10
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700517static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700518{
519 int i;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700520 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700521 int inflate_threshold_use;
522 int halve_threshold_use;
Jens Låås80b71b82009-08-28 23:57:15 -0700523 int max_work;
Robert Olsson19baf832005-06-21 12:43:18 -0700524
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900525 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700526 return NULL;
527
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700528 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
529 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700530
531 /* No children */
532 if (tn->empty_children == tnode_child_length(tn)) {
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700533 tnode_free_safe(tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700534 return NULL;
535 }
536 /* One child */
537 if (tn->empty_children == tnode_child_length(tn) - 1)
Jens Låås80b71b82009-08-28 23:57:15 -0700538 goto one_child;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700539 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700540 * Double as long as the resulting node has a number of
541 * nonempty nodes that are above the threshold.
542 */
543
544 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700545 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
546 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700547 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700548 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700549 * children in the *doubled* node is at least 'high'."
550 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700551 * 'high' in this instance is the variable 'inflate_threshold'. It
552 * is expressed as a percentage, so we multiply it with
553 * tnode_child_length() and instead of multiplying by 2 (since the
554 * child array will be doubled by inflate()) and multiplying
555 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700556 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700557 *
558 * The left-hand side may look a bit weird: tnode_child_length(tn)
559 * - tn->empty_children is of course the number of non-null children
560 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700561 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700562 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700563 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700564 *
Robert Olsson19baf832005-06-21 12:43:18 -0700565 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700566 *
Robert Olsson19baf832005-06-21 12:43:18 -0700567 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700568 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700569 * tn->full_children;
570 *
571 * new_child_length = tnode_child_length(tn) * 2;
572 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700573 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700574 * new_child_length;
575 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700576 *
577 * ...and so on, tho it would mess up the while () loop.
578 *
Robert Olsson19baf832005-06-21 12:43:18 -0700579 * anyway,
580 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
581 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700582 *
Robert Olsson19baf832005-06-21 12:43:18 -0700583 * avoid a division:
584 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
585 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700586 *
Robert Olsson19baf832005-06-21 12:43:18 -0700587 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700588 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700589 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700590 *
Robert Olsson19baf832005-06-21 12:43:18 -0700591 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700592 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700593 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700594 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700595 *
Robert Olsson19baf832005-06-21 12:43:18 -0700596 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700597 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700598 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700599 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700600 *
Robert Olsson19baf832005-06-21 12:43:18 -0700601 */
602
603 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700604
Robert Olssone6308be2005-10-04 13:01:58 -0700605 /* Keep root node larger */
606
Jens Låås80b71b82009-08-28 23:57:15 -0700607 if (!node_parent((struct node*) tn)) {
608 inflate_threshold_use = inflate_threshold_root;
609 halve_threshold_use = halve_threshold_root;
610 }
611 else {
Robert Olssone6308be2005-10-04 13:01:58 -0700612 inflate_threshold_use = inflate_threshold;
Jens Låås80b71b82009-08-28 23:57:15 -0700613 halve_threshold_use = halve_threshold;
614 }
Robert Olssone6308be2005-10-04 13:01:58 -0700615
Jens Låås80b71b82009-08-28 23:57:15 -0700616 max_work = MAX_WORK;
617 while ((tn->full_children > 0 && max_work-- &&
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800618 50 * (tn->full_children + tnode_child_length(tn)
619 - tn->empty_children)
620 >= inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700621
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700622 old_tn = tn;
623 tn = inflate(t, tn);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800624
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700625 if (IS_ERR(tn)) {
626 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700627#ifdef CONFIG_IP_FIB_TRIE_STATS
628 t->stats.resize_node_skipped++;
629#endif
630 break;
631 }
Robert Olsson19baf832005-06-21 12:43:18 -0700632 }
633
634 check_tnode(tn);
635
Jens Låås80b71b82009-08-28 23:57:15 -0700636 /* Return if at least one inflate is run */
637 if( max_work != MAX_WORK)
638 return (struct node *) tn;
639
Robert Olsson19baf832005-06-21 12:43:18 -0700640 /*
641 * Halve as long as the number of empty children in this
642 * node is above threshold.
643 */
Robert Olsson2f368952005-07-05 15:02:40 -0700644
Jens Låås80b71b82009-08-28 23:57:15 -0700645 max_work = MAX_WORK;
646 while (tn->bits > 1 && max_work-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700647 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700648 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700649
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700650 old_tn = tn;
651 tn = halve(t, tn);
652 if (IS_ERR(tn)) {
653 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700654#ifdef CONFIG_IP_FIB_TRIE_STATS
655 t->stats.resize_node_skipped++;
656#endif
657 break;
658 }
659 }
660
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700661
Robert Olsson19baf832005-06-21 12:43:18 -0700662 /* Only one child remains */
Jens Låås80b71b82009-08-28 23:57:15 -0700663 if (tn->empty_children == tnode_child_length(tn) - 1) {
664one_child:
Robert Olsson19baf832005-06-21 12:43:18 -0700665 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700666 struct node *n;
667
Olof Johansson91b9a272005-08-09 20:24:39 -0700668 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700669 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700670 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700671
672 /* compress one level */
673
Stephen Hemminger06801912007-08-10 15:22:13 -0700674 node_set_parent(n, NULL);
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700675 tnode_free_safe(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700676 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700677 }
Jens Låås80b71b82009-08-28 23:57:15 -0700678 }
Robert Olsson19baf832005-06-21 12:43:18 -0700679 return (struct node *) tn;
680}
681
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700682static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700683{
Robert Olsson19baf832005-06-21 12:43:18 -0700684 struct tnode *oldtnode = tn;
685 int olen = tnode_child_length(tn);
686 int i;
687
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700688 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700689
690 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
691
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700692 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700693 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700694
695 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700696 * Preallocate and store tnodes before the actual work so we
697 * don't get into an inconsistent state if memory allocation
698 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700699 * of tnode is ignored.
700 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700701
702 for (i = 0; i < olen; i++) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800703 struct tnode *inode;
Robert Olsson2f368952005-07-05 15:02:40 -0700704
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800705 inode = (struct tnode *) tnode_get_child(oldtnode, i);
Robert Olsson2f368952005-07-05 15:02:40 -0700706 if (inode &&
707 IS_TNODE(inode) &&
708 inode->pos == oldtnode->pos + oldtnode->bits &&
709 inode->bits > 1) {
710 struct tnode *left, *right;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700711 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700712
Robert Olsson2f368952005-07-05 15:02:40 -0700713 left = tnode_new(inode->key&(~m), inode->pos + 1,
714 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700715 if (!left)
716 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700717
Robert Olsson2f368952005-07-05 15:02:40 -0700718 right = tnode_new(inode->key|m, inode->pos + 1,
719 inode->bits - 1);
720
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900721 if (!right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700722 tnode_free(left);
723 goto nomem;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900724 }
Robert Olsson2f368952005-07-05 15:02:40 -0700725
726 put_child(t, tn, 2*i, (struct node *) left);
727 put_child(t, tn, 2*i+1, (struct node *) right);
728 }
729 }
730
Olof Johansson91b9a272005-08-09 20:24:39 -0700731 for (i = 0; i < olen; i++) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -0800732 struct tnode *inode;
Robert Olsson19baf832005-06-21 12:43:18 -0700733 struct node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700734 struct tnode *left, *right;
735 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700736
Robert Olsson19baf832005-06-21 12:43:18 -0700737 /* An empty child */
738 if (node == NULL)
739 continue;
740
741 /* A leaf or an internal node with skipped bits */
742
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700743 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700744 tn->pos + tn->bits - 1) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800745 if (tkey_extract_bits(node->key,
746 oldtnode->pos + oldtnode->bits,
747 1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700748 put_child(t, tn, 2*i, node);
749 else
750 put_child(t, tn, 2*i+1, node);
751 continue;
752 }
753
754 /* An internal node with two children */
755 inode = (struct tnode *) node;
756
757 if (inode->bits == 1) {
758 put_child(t, tn, 2*i, inode->child[0]);
759 put_child(t, tn, 2*i+1, inode->child[1]);
760
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700761 tnode_free_safe(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700762 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700763 }
764
Olof Johansson91b9a272005-08-09 20:24:39 -0700765 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700766
Olof Johansson91b9a272005-08-09 20:24:39 -0700767 /* We will replace this node 'inode' with two new
768 * ones, 'left' and 'right', each with half of the
769 * original children. The two new nodes will have
770 * a position one bit further down the key and this
771 * means that the "significant" part of their keys
772 * (see the discussion near the top of this file)
773 * will differ by one bit, which will be "0" in
774 * left's key and "1" in right's key. Since we are
775 * moving the key position by one step, the bit that
776 * we are moving away from - the bit at position
777 * (inode->pos) - is the one that will differ between
778 * left and right. So... we synthesize that bit in the
779 * two new keys.
780 * The mask 'm' below will be a single "one" bit at
781 * the position (inode->pos)
782 */
Robert Olsson19baf832005-06-21 12:43:18 -0700783
Olof Johansson91b9a272005-08-09 20:24:39 -0700784 /* Use the old key, but set the new significant
785 * bit to zero.
786 */
Robert Olsson19baf832005-06-21 12:43:18 -0700787
Olof Johansson91b9a272005-08-09 20:24:39 -0700788 left = (struct tnode *) tnode_get_child(tn, 2*i);
789 put_child(t, tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700790
Olof Johansson91b9a272005-08-09 20:24:39 -0700791 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700792
Olof Johansson91b9a272005-08-09 20:24:39 -0700793 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
794 put_child(t, tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700795
Olof Johansson91b9a272005-08-09 20:24:39 -0700796 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700797
Olof Johansson91b9a272005-08-09 20:24:39 -0700798 size = tnode_child_length(left);
799 for (j = 0; j < size; j++) {
800 put_child(t, left, j, inode->child[j]);
801 put_child(t, right, j, inode->child[j + size]);
Robert Olsson19baf832005-06-21 12:43:18 -0700802 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700803 put_child(t, tn, 2*i, resize(t, left));
804 put_child(t, tn, 2*i+1, resize(t, right));
805
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700806 tnode_free_safe(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700807 }
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700808 tnode_free_safe(oldtnode);
Robert Olsson19baf832005-06-21 12:43:18 -0700809 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700810nomem:
811 {
812 int size = tnode_child_length(tn);
813 int j;
814
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700815 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700816 if (tn->child[j])
817 tnode_free((struct tnode *)tn->child[j]);
818
819 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700820
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700821 return ERR_PTR(-ENOMEM);
822 }
Robert Olsson19baf832005-06-21 12:43:18 -0700823}
824
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700825static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700826{
827 struct tnode *oldtnode = tn;
828 struct node *left, *right;
829 int i;
830 int olen = tnode_child_length(tn);
831
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700832 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700833
834 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700835
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700836 if (!tn)
837 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700838
839 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700840 * Preallocate and store tnodes before the actual work so we
841 * don't get into an inconsistent state if memory allocation
842 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700843 * of tnode is ignored.
844 */
845
Olof Johansson91b9a272005-08-09 20:24:39 -0700846 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700847 left = tnode_get_child(oldtnode, i);
848 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700849
Robert Olsson2f368952005-07-05 15:02:40 -0700850 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700851 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700852 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700853
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700854 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700855
856 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700857 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700858
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700859 put_child(t, tn, i/2, (struct node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700860 }
Robert Olsson2f368952005-07-05 15:02:40 -0700861
Robert Olsson2f368952005-07-05 15:02:40 -0700862 }
Robert Olsson19baf832005-06-21 12:43:18 -0700863
Olof Johansson91b9a272005-08-09 20:24:39 -0700864 for (i = 0; i < olen; i += 2) {
865 struct tnode *newBinNode;
866
Robert Olsson19baf832005-06-21 12:43:18 -0700867 left = tnode_get_child(oldtnode, i);
868 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700869
Robert Olsson19baf832005-06-21 12:43:18 -0700870 /* At least one of the children is empty */
871 if (left == NULL) {
872 if (right == NULL) /* Both are empty */
873 continue;
874 put_child(t, tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700875 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700876 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700877
878 if (right == NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700879 put_child(t, tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700880 continue;
881 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700882
Robert Olsson19baf832005-06-21 12:43:18 -0700883 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700884 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
885 put_child(t, tn, i/2, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700886 put_child(t, newBinNode, 0, left);
887 put_child(t, newBinNode, 1, right);
888 put_child(t, tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700889 }
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700890 tnode_free_safe(oldtnode);
Robert Olsson19baf832005-06-21 12:43:18 -0700891 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700892nomem:
893 {
894 int size = tnode_child_length(tn);
895 int j;
896
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700897 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700898 if (tn->child[j])
899 tnode_free((struct tnode *)tn->child[j]);
900
901 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700902
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700903 return ERR_PTR(-ENOMEM);
904 }
Robert Olsson19baf832005-06-21 12:43:18 -0700905}
906
Robert Olsson772cb712005-09-19 15:31:18 -0700907/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700908 via get_fa_head and dump */
909
Robert Olsson772cb712005-09-19 15:31:18 -0700910static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700911{
Robert Olsson772cb712005-09-19 15:31:18 -0700912 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700913 struct hlist_node *node;
914 struct leaf_info *li;
915
Robert Olsson2373ce12005-08-25 13:01:29 -0700916 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700917 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700918 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700919
Robert Olsson19baf832005-06-21 12:43:18 -0700920 return NULL;
921}
922
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800923static inline struct list_head *get_fa_head(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700924{
Robert Olsson772cb712005-09-19 15:31:18 -0700925 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700926
Olof Johansson91b9a272005-08-09 20:24:39 -0700927 if (!li)
928 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700929
Olof Johansson91b9a272005-08-09 20:24:39 -0700930 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700931}
932
933static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
934{
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900935 struct leaf_info *li = NULL, *last = NULL;
936 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700937
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900938 if (hlist_empty(head)) {
939 hlist_add_head_rcu(&new->hlist, head);
940 } else {
941 hlist_for_each_entry(li, node, head, hlist) {
942 if (new->plen > li->plen)
943 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700944
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900945 last = li;
946 }
947 if (last)
948 hlist_add_after_rcu(&last->hlist, &new->hlist);
949 else
950 hlist_add_before_rcu(&new->hlist, &li->hlist);
951 }
Robert Olsson19baf832005-06-21 12:43:18 -0700952}
953
Robert Olsson2373ce12005-08-25 13:01:29 -0700954/* rcu_read_lock needs to be hold by caller from readside */
955
Robert Olsson19baf832005-06-21 12:43:18 -0700956static struct leaf *
957fib_find_node(struct trie *t, u32 key)
958{
959 int pos;
960 struct tnode *tn;
961 struct node *n;
962
963 pos = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700964 n = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700965
966 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
967 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700968
Robert Olsson19baf832005-06-21 12:43:18 -0700969 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700970
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700971 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700972 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800973 n = tnode_get_child_rcu(tn,
974 tkey_extract_bits(key,
975 tn->pos,
976 tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700977 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700978 break;
979 }
980 /* Case we have found a leaf. Compare prefixes */
981
Olof Johansson91b9a272005-08-09 20:24:39 -0700982 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
983 return (struct leaf *)n;
984
Robert Olsson19baf832005-06-21 12:43:18 -0700985 return NULL;
986}
987
Jarek Poplawski7b855762009-06-18 00:28:51 -0700988static void trie_rebalance(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700989{
Robert Olsson19baf832005-06-21 12:43:18 -0700990 int wasfull;
Robert Olsson3ed18d72009-05-21 15:20:59 -0700991 t_key cindex, key;
Stephen Hemminger06801912007-08-10 15:22:13 -0700992 struct tnode *tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700993
Robert Olsson3ed18d72009-05-21 15:20:59 -0700994 key = tn->key;
995
Stephen Hemminger06801912007-08-10 15:22:13 -0700996 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700997 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
998 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800999 tn = (struct tnode *) resize(t, (struct tnode *)tn);
1000
1001 tnode_put_child_reorg((struct tnode *)tp, cindex,
1002 (struct node *)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -07001003
Stephen Hemminger06801912007-08-10 15:22:13 -07001004 tp = node_parent((struct node *) tn);
Jarek Poplawski008440e2009-06-30 12:47:19 -07001005 if (!tp)
1006 rcu_assign_pointer(t->trie, (struct node *)tn);
1007
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -07001008 tnode_free_flush();
Stephen Hemminger06801912007-08-10 15:22:13 -07001009 if (!tp)
Robert Olsson19baf832005-06-21 12:43:18 -07001010 break;
Stephen Hemminger06801912007-08-10 15:22:13 -07001011 tn = tp;
Robert Olsson19baf832005-06-21 12:43:18 -07001012 }
Stephen Hemminger06801912007-08-10 15:22:13 -07001013
Robert Olsson19baf832005-06-21 12:43:18 -07001014 /* Handle last (top) tnode */
Jarek Poplawski7b855762009-06-18 00:28:51 -07001015 if (IS_TNODE(tn))
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001016 tn = (struct tnode *)resize(t, (struct tnode *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001017
Jarek Poplawski7b855762009-06-18 00:28:51 -07001018 rcu_assign_pointer(t->trie, (struct node *)tn);
1019 tnode_free_flush();
1020
1021 return;
Robert Olsson19baf832005-06-21 12:43:18 -07001022}
1023
Robert Olsson2373ce12005-08-25 13:01:29 -07001024/* only used from updater-side */
1025
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001026static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -07001027{
1028 int pos, newpos;
1029 struct tnode *tp = NULL, *tn = NULL;
1030 struct node *n;
1031 struct leaf *l;
1032 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001033 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001034 struct leaf_info *li;
1035 t_key cindex;
1036
1037 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001038 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001039
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001040 /* If we point to NULL, stop. Either the tree is empty and we should
1041 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001042 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001043 * If we point to a T_TNODE, check if it matches our key. Note that
1044 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001045 * not be the parent's 'pos'+'bits'!
1046 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001047 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001048 * the index from our key, push the T_TNODE and walk the tree.
1049 *
1050 * If it doesn't, we have to replace it with a new T_TNODE.
1051 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001052 * If we point to a T_LEAF, it might or might not have the same key
1053 * as we do. If it does, just change the value, update the T_LEAF's
1054 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001055 * If it doesn't, we need to replace it with a T_TNODE.
1056 */
1057
1058 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1059 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001060
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001061 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001062
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001063 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001064 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001065 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001066 n = tnode_get_child(tn,
1067 tkey_extract_bits(key,
1068 tn->pos,
1069 tn->bits));
Robert Olsson19baf832005-06-21 12:43:18 -07001070
Stephen Hemminger06801912007-08-10 15:22:13 -07001071 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001072 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001073 break;
1074 }
1075
1076 /*
1077 * n ----> NULL, LEAF or TNODE
1078 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001079 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001080 */
1081
Olof Johansson91b9a272005-08-09 20:24:39 -07001082 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001083
1084 /* Case 1: n is a leaf. Compare prefixes */
1085
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001086 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08001087 l = (struct leaf *) n;
Robert Olsson19baf832005-06-21 12:43:18 -07001088 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001089
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001090 if (!li)
1091 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001092
1093 fa_head = &li->falh;
1094 insert_leaf_info(&l->list, li);
1095 goto done;
1096 }
Robert Olsson19baf832005-06-21 12:43:18 -07001097 l = leaf_new();
1098
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001099 if (!l)
1100 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001101
1102 l->key = key;
1103 li = leaf_info_new(plen);
1104
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001105 if (!li) {
Stephen Hemminger387a5482008-04-10 03:47:34 -07001106 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001107 return NULL;
Robert Olssonf835e472005-06-28 15:00:39 -07001108 }
Robert Olsson19baf832005-06-21 12:43:18 -07001109
1110 fa_head = &li->falh;
1111 insert_leaf_info(&l->list, li);
1112
Robert Olsson19baf832005-06-21 12:43:18 -07001113 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001114 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001115
Stephen Hemminger06801912007-08-10 15:22:13 -07001116 node_set_parent((struct node *)l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001117
Olof Johansson91b9a272005-08-09 20:24:39 -07001118 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1119 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1120 } else {
1121 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001122 /*
1123 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001124 * first tnode need some special handling
1125 */
1126
1127 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001128 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001129 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001130 pos = 0;
1131
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001132 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001133 newpos = tkey_mismatch(key, pos, n->key);
1134 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001135 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001136 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001137 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001138 }
Robert Olsson19baf832005-06-21 12:43:18 -07001139
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001140 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001141 free_leaf_info(li);
Stephen Hemminger387a5482008-04-10 03:47:34 -07001142 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001143 return NULL;
Olof Johansson91b9a272005-08-09 20:24:39 -07001144 }
1145
Stephen Hemminger06801912007-08-10 15:22:13 -07001146 node_set_parent((struct node *)tn, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001147
Olof Johansson91b9a272005-08-09 20:24:39 -07001148 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001149 put_child(t, tn, missbit, (struct node *)l);
1150 put_child(t, tn, 1-missbit, n);
1151
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001152 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001153 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001154 put_child(t, (struct tnode *)tp, cindex,
1155 (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001156 } else {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001157 rcu_assign_pointer(t->trie, (struct node *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001158 tp = tn;
1159 }
1160 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001161
1162 if (tp && tp->pos + tp->bits > 32)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001163 pr_warning("fib_trie"
1164 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1165 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001166
Robert Olsson19baf832005-06-21 12:43:18 -07001167 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001168
Jarek Poplawski7b855762009-06-18 00:28:51 -07001169 trie_rebalance(t, tp);
Robert Olssonf835e472005-06-28 15:00:39 -07001170done:
Robert Olsson19baf832005-06-21 12:43:18 -07001171 return fa_head;
1172}
1173
Robert Olssond562f1f2007-03-26 14:22:22 -07001174/*
1175 * Caller must hold RTNL.
1176 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001177static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001178{
1179 struct trie *t = (struct trie *) tb->tb_data;
1180 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001181 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001182 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001183 int plen = cfg->fc_dst_len;
1184 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001185 u32 key, mask;
1186 int err;
1187 struct leaf *l;
1188
1189 if (plen > 32)
1190 return -EINVAL;
1191
Thomas Graf4e902c52006-08-17 18:14:52 -07001192 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001193
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001194 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001195
Olof Johansson91b9a272005-08-09 20:24:39 -07001196 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001197
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001198 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001199 return -EINVAL;
1200
1201 key = key & mask;
1202
Thomas Graf4e902c52006-08-17 18:14:52 -07001203 fi = fib_create_info(cfg);
1204 if (IS_ERR(fi)) {
1205 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001206 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001207 }
Robert Olsson19baf832005-06-21 12:43:18 -07001208
1209 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001210 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001211
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001212 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001213 fa_head = get_fa_head(l, plen);
1214 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1215 }
1216
1217 /* Now fa, if non-NULL, points to the first fib alias
1218 * with the same keys [prefix,tos,priority], if such key already
1219 * exists or to the node before which we will insert new one.
1220 *
1221 * If fa is NULL, we will need to allocate a new one and
1222 * insert to the head of f.
1223 *
1224 * If f is NULL, no fib node matched the destination key
1225 * and we need to allocate a new one of those as well.
1226 */
1227
Julian Anastasov936f6f82008-01-28 21:18:06 -08001228 if (fa && fa->fa_tos == tos &&
1229 fa->fa_info->fib_priority == fi->fib_priority) {
1230 struct fib_alias *fa_first, *fa_match;
Robert Olsson19baf832005-06-21 12:43:18 -07001231
1232 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001233 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001234 goto out;
1235
Julian Anastasov936f6f82008-01-28 21:18:06 -08001236 /* We have 2 goals:
1237 * 1. Find exact match for type, scope, fib_info to avoid
1238 * duplicate routes
1239 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1240 */
1241 fa_match = NULL;
1242 fa_first = fa;
1243 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1244 list_for_each_entry_continue(fa, fa_head, fa_list) {
1245 if (fa->fa_tos != tos)
1246 break;
1247 if (fa->fa_info->fib_priority != fi->fib_priority)
1248 break;
1249 if (fa->fa_type == cfg->fc_type &&
1250 fa->fa_scope == cfg->fc_scope &&
1251 fa->fa_info == fi) {
1252 fa_match = fa;
1253 break;
1254 }
1255 }
1256
Thomas Graf4e902c52006-08-17 18:14:52 -07001257 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001258 struct fib_info *fi_drop;
1259 u8 state;
1260
Julian Anastasov936f6f82008-01-28 21:18:06 -08001261 fa = fa_first;
1262 if (fa_match) {
1263 if (fa == fa_match)
1264 err = 0;
Joonwoo Park67250332008-01-18 03:45:18 -08001265 goto out;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001266 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001267 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001268 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001269 if (new_fa == NULL)
1270 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001271
1272 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001273 new_fa->fa_tos = fa->fa_tos;
1274 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001275 new_fa->fa_type = cfg->fc_type;
1276 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001277 state = fa->fa_state;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001278 new_fa->fa_state = state & ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001279
Robert Olsson2373ce12005-08-25 13:01:29 -07001280 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1281 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001282
1283 fib_release_info(fi_drop);
1284 if (state & FA_S_ACCESSED)
Denis V. Lunev76e6ebf2008-07-05 19:00:44 -07001285 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
Milan Kocianb8f55832007-05-23 14:55:06 -07001286 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1287 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001288
Olof Johansson91b9a272005-08-09 20:24:39 -07001289 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001290 }
1291 /* Error if we find a perfect match which
1292 * uses the same scope, type, and nexthop
1293 * information.
1294 */
Julian Anastasov936f6f82008-01-28 21:18:06 -08001295 if (fa_match)
1296 goto out;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001297
Thomas Graf4e902c52006-08-17 18:14:52 -07001298 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001299 fa = fa_first;
Robert Olsson19baf832005-06-21 12:43:18 -07001300 }
1301 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001302 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001303 goto out;
1304
1305 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001306 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001307 if (new_fa == NULL)
1308 goto out;
1309
1310 new_fa->fa_info = fi;
1311 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001312 new_fa->fa_type = cfg->fc_type;
1313 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001314 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001315 /*
1316 * Insert new entry to the list.
1317 */
1318
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001319 if (!fa_head) {
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001320 fa_head = fib_insert_node(t, key, plen);
1321 if (unlikely(!fa_head)) {
1322 err = -ENOMEM;
Robert Olssonf835e472005-06-28 15:00:39 -07001323 goto out_free_new_fa;
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001324 }
Robert Olssonf835e472005-06-28 15:00:39 -07001325 }
Robert Olsson19baf832005-06-21 12:43:18 -07001326
Robert Olsson2373ce12005-08-25 13:01:29 -07001327 list_add_tail_rcu(&new_fa->fa_list,
1328 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001329
Denis V. Lunev76e6ebf2008-07-05 19:00:44 -07001330 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001331 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001332 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001333succeeded:
1334 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001335
1336out_free_new_fa:
1337 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001338out:
1339 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001340err:
Robert Olsson19baf832005-06-21 12:43:18 -07001341 return err;
1342}
1343
Robert Olsson772cb712005-09-19 15:31:18 -07001344/* should be called with rcu_read_lock */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001345static int check_leaf(struct trie *t, struct leaf *l,
1346 t_key key, const struct flowi *flp,
1347 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001348{
Robert Olsson19baf832005-06-21 12:43:18 -07001349 struct leaf_info *li;
1350 struct hlist_head *hhead = &l->list;
1351 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001352
Robert Olsson2373ce12005-08-25 13:01:29 -07001353 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001354 int err;
1355 int plen = li->plen;
1356 __be32 mask = inet_make_mask(plen);
1357
Al Viro888454c2006-09-19 13:42:46 -07001358 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001359 continue;
1360
Rami Rosene204a342009-05-18 01:19:12 +00001361 err = fib_semantic_match(&li->falh, flp, res, plen);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001362
Robert Olsson19baf832005-06-21 12:43:18 -07001363#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001364 if (err <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001365 t->stats.semantic_match_passed++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001366 else
1367 t->stats.semantic_match_miss++;
Robert Olsson19baf832005-06-21 12:43:18 -07001368#endif
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001369 if (err <= 0)
Ben Hutchings2e655572008-07-10 16:52:52 -07001370 return err;
Robert Olsson19baf832005-06-21 12:43:18 -07001371 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001372
Ben Hutchings2e655572008-07-10 16:52:52 -07001373 return 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001374}
1375
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001376static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
1377 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001378{
1379 struct trie *t = (struct trie *) tb->tb_data;
Ben Hutchings2e655572008-07-10 16:52:52 -07001380 int ret;
Robert Olsson19baf832005-06-21 12:43:18 -07001381 struct node *n;
1382 struct tnode *pn;
1383 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001384 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001385 int chopped_off;
1386 t_key cindex = 0;
1387 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001388 struct tnode *cn;
1389 t_key node_prefix, key_prefix, pref_mismatch;
1390 int mp;
1391
Robert Olsson2373ce12005-08-25 13:01:29 -07001392 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001393
Robert Olsson2373ce12005-08-25 13:01:29 -07001394 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001395 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001396 goto failed;
1397
1398#ifdef CONFIG_IP_FIB_TRIE_STATS
1399 t->stats.gets++;
1400#endif
1401
1402 /* Just a leaf? */
1403 if (IS_LEAF(n)) {
Ben Hutchings2e655572008-07-10 16:52:52 -07001404 ret = check_leaf(t, (struct leaf *)n, key, flp, res);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001405 goto found;
Robert Olsson19baf832005-06-21 12:43:18 -07001406 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001407
Robert Olsson19baf832005-06-21 12:43:18 -07001408 pn = (struct tnode *) n;
1409 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001410
Olof Johansson91b9a272005-08-09 20:24:39 -07001411 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001412 pos = pn->pos;
1413 bits = pn->bits;
1414
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001415 if (!chopped_off)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001416 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1417 pos, bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001418
Jarek Poplawskib902e572009-07-14 11:20:32 +00001419 n = tnode_get_child_rcu(pn, cindex);
Robert Olsson19baf832005-06-21 12:43:18 -07001420
1421 if (n == NULL) {
1422#ifdef CONFIG_IP_FIB_TRIE_STATS
1423 t->stats.null_node_hit++;
1424#endif
1425 goto backtrace;
1426 }
1427
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001428 if (IS_LEAF(n)) {
Ben Hutchings2e655572008-07-10 16:52:52 -07001429 ret = check_leaf(t, (struct leaf *)n, key, flp, res);
1430 if (ret > 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07001431 goto backtrace;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001432 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001433 }
1434
Olof Johansson91b9a272005-08-09 20:24:39 -07001435 cn = (struct tnode *)n;
1436
1437 /*
1438 * It's a tnode, and we can do some extra checks here if we
1439 * like, to avoid descending into a dead-end branch.
1440 * This tnode is in the parent's child array at index
1441 * key[p_pos..p_pos+p_bits] but potentially with some bits
1442 * chopped off, so in reality the index may be just a
1443 * subprefix, padded with zero at the end.
1444 * We can also take a look at any skipped bits in this
1445 * tnode - everything up to p_pos is supposed to be ok,
1446 * and the non-chopped bits of the index (se previous
1447 * paragraph) are also guaranteed ok, but the rest is
1448 * considered unknown.
1449 *
1450 * The skipped bits are key[pos+bits..cn->pos].
1451 */
1452
1453 /* If current_prefix_length < pos+bits, we are already doing
1454 * actual prefix matching, which means everything from
1455 * pos+(bits-chopped_off) onward must be zero along some
1456 * branch of this subtree - otherwise there is *no* valid
1457 * prefix present. Here we can only check the skipped
1458 * bits. Remember, since we have already indexed into the
1459 * parent's child array, we know that the bits we chopped of
1460 * *are* zero.
1461 */
1462
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001463 /* NOTA BENE: Checking only skipped bits
1464 for the new node here */
Olof Johansson91b9a272005-08-09 20:24:39 -07001465
1466 if (current_prefix_length < pos+bits) {
1467 if (tkey_extract_bits(cn->key, current_prefix_length,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001468 cn->pos - current_prefix_length)
1469 || !(cn->child[0]))
Olof Johansson91b9a272005-08-09 20:24:39 -07001470 goto backtrace;
1471 }
1472
1473 /*
1474 * If chopped_off=0, the index is fully validated and we
1475 * only need to look at the skipped bits for this, the new,
1476 * tnode. What we actually want to do is to find out if
1477 * these skipped bits match our key perfectly, or if we will
1478 * have to count on finding a matching prefix further down,
1479 * because if we do, we would like to have some way of
1480 * verifying the existence of such a prefix at this point.
1481 */
1482
1483 /* The only thing we can do at this point is to verify that
1484 * any such matching prefix can indeed be a prefix to our
1485 * key, and if the bits in the node we are inspecting that
1486 * do not match our key are not ZERO, this cannot be true.
1487 * Thus, find out where there is a mismatch (before cn->pos)
1488 * and verify that all the mismatching bits are zero in the
1489 * new tnode's key.
1490 */
1491
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001492 /*
1493 * Note: We aren't very concerned about the piece of
1494 * the key that precede pn->pos+pn->bits, since these
1495 * have already been checked. The bits after cn->pos
1496 * aren't checked since these are by definition
1497 * "unknown" at this point. Thus, what we want to see
1498 * is if we are about to enter the "prefix matching"
1499 * state, and in that case verify that the skipped
1500 * bits that will prevail throughout this subtree are
1501 * zero, as they have to be if we are to find a
1502 * matching prefix.
Olof Johansson91b9a272005-08-09 20:24:39 -07001503 */
1504
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001505 node_prefix = mask_pfx(cn->key, cn->pos);
1506 key_prefix = mask_pfx(key, cn->pos);
Olof Johansson91b9a272005-08-09 20:24:39 -07001507 pref_mismatch = key_prefix^node_prefix;
1508 mp = 0;
1509
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001510 /*
1511 * In short: If skipped bits in this node do not match
1512 * the search key, enter the "prefix matching"
1513 * state.directly.
Olof Johansson91b9a272005-08-09 20:24:39 -07001514 */
1515 if (pref_mismatch) {
1516 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1517 mp++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001518 pref_mismatch = pref_mismatch << 1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001519 }
1520 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1521
1522 if (key_prefix != 0)
1523 goto backtrace;
1524
1525 if (current_prefix_length >= cn->pos)
1526 current_prefix_length = mp;
1527 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001528
Olof Johansson91b9a272005-08-09 20:24:39 -07001529 pn = (struct tnode *)n; /* Descend */
1530 chopped_off = 0;
1531 continue;
1532
Robert Olsson19baf832005-06-21 12:43:18 -07001533backtrace:
1534 chopped_off++;
1535
1536 /* As zero don't change the child key (cindex) */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001537 while ((chopped_off <= pn->bits)
1538 && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001539 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001540
1541 /* Decrease current_... with bits chopped off */
1542 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001543 current_prefix_length = pn->pos + pn->bits
1544 - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001545
Robert Olsson19baf832005-06-21 12:43:18 -07001546 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001547 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001548 * chopped off all bits in this tnode walk up to our parent.
1549 */
1550
Olof Johansson91b9a272005-08-09 20:24:39 -07001551 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001552 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001553 } else {
Jarek Poplawskib902e572009-07-14 11:20:32 +00001554 struct tnode *parent = node_parent_rcu((struct node *) pn);
Stephen Hemminger06801912007-08-10 15:22:13 -07001555 if (!parent)
Robert Olsson19baf832005-06-21 12:43:18 -07001556 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001557
Robert Olsson19baf832005-06-21 12:43:18 -07001558 /* Get Child's index */
Stephen Hemminger06801912007-08-10 15:22:13 -07001559 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1560 pn = parent;
Robert Olsson19baf832005-06-21 12:43:18 -07001561 chopped_off = 0;
1562
1563#ifdef CONFIG_IP_FIB_TRIE_STATS
1564 t->stats.backtrack++;
1565#endif
1566 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001567 }
Robert Olsson19baf832005-06-21 12:43:18 -07001568 }
1569failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001570 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001571found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001572 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001573 return ret;
1574}
1575
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001576/*
1577 * Remove the leaf and return parent.
1578 */
1579static void trie_leaf_remove(struct trie *t, struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001580{
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001581 struct tnode *tp = node_parent((struct node *) l);
Robert Olsson19baf832005-06-21 12:43:18 -07001582
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001583 pr_debug("entering trie_leaf_remove(%p)\n", l);
Robert Olsson19baf832005-06-21 12:43:18 -07001584
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001585 if (tp) {
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001586 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001587 put_child(t, (struct tnode *)tp, cindex, NULL);
Jarek Poplawski7b855762009-06-18 00:28:51 -07001588 trie_rebalance(t, tp);
Olof Johansson91b9a272005-08-09 20:24:39 -07001589 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001590 rcu_assign_pointer(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001591
Stephen Hemminger387a5482008-04-10 03:47:34 -07001592 free_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001593}
1594
Robert Olssond562f1f2007-03-26 14:22:22 -07001595/*
1596 * Caller must hold RTNL.
1597 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001598static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001599{
1600 struct trie *t = (struct trie *) tb->tb_data;
1601 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001602 int plen = cfg->fc_dst_len;
1603 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001604 struct fib_alias *fa, *fa_to_delete;
1605 struct list_head *fa_head;
1606 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001607 struct leaf_info *li;
1608
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001609 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001610 return -EINVAL;
1611
Thomas Graf4e902c52006-08-17 18:14:52 -07001612 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001613 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001614
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001615 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001616 return -EINVAL;
1617
1618 key = key & mask;
1619 l = fib_find_node(t, key);
1620
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001621 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001622 return -ESRCH;
1623
1624 fa_head = get_fa_head(l, plen);
1625 fa = fib_find_alias(fa_head, tos, 0);
1626
1627 if (!fa)
1628 return -ESRCH;
1629
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001630 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001631
1632 fa_to_delete = NULL;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001633 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1634 list_for_each_entry_continue(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001635 struct fib_info *fi = fa->fa_info;
1636
1637 if (fa->fa_tos != tos)
1638 break;
1639
Thomas Graf4e902c52006-08-17 18:14:52 -07001640 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1641 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1642 fa->fa_scope == cfg->fc_scope) &&
1643 (!cfg->fc_protocol ||
1644 fi->fib_protocol == cfg->fc_protocol) &&
1645 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001646 fa_to_delete = fa;
1647 break;
1648 }
1649 }
1650
Olof Johansson91b9a272005-08-09 20:24:39 -07001651 if (!fa_to_delete)
1652 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001653
Olof Johansson91b9a272005-08-09 20:24:39 -07001654 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001655 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001656 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001657
Olof Johansson91b9a272005-08-09 20:24:39 -07001658 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001659 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001660
Robert Olsson2373ce12005-08-25 13:01:29 -07001661 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001662
Olof Johansson91b9a272005-08-09 20:24:39 -07001663 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001664 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001665 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001666 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001667
1668 if (hlist_empty(&l->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001669 trie_leaf_remove(t, l);
Olof Johansson91b9a272005-08-09 20:24:39 -07001670
1671 if (fa->fa_state & FA_S_ACCESSED)
Denis V. Lunev76e6ebf2008-07-05 19:00:44 -07001672 rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001673
Robert Olsson2373ce12005-08-25 13:01:29 -07001674 fib_release_info(fa->fa_info);
1675 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001676 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001677}
1678
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001679static int trie_flush_list(struct list_head *head)
Robert Olsson19baf832005-06-21 12:43:18 -07001680{
1681 struct fib_alias *fa, *fa_node;
1682 int found = 0;
1683
1684 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1685 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001686
Robert Olsson2373ce12005-08-25 13:01:29 -07001687 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1688 list_del_rcu(&fa->fa_list);
1689 fib_release_info(fa->fa_info);
1690 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001691 found++;
1692 }
1693 }
1694 return found;
1695}
1696
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001697static int trie_flush_leaf(struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001698{
1699 int found = 0;
1700 struct hlist_head *lih = &l->list;
1701 struct hlist_node *node, *tmp;
1702 struct leaf_info *li = NULL;
1703
1704 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001705 found += trie_flush_list(&li->falh);
Robert Olsson19baf832005-06-21 12:43:18 -07001706
1707 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001708 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001709 free_leaf_info(li);
1710 }
1711 }
1712 return found;
1713}
1714
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001715/*
1716 * Scan for the next right leaf starting at node p->child[idx]
1717 * Since we have back pointer, no recursion necessary.
1718 */
1719static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)
Robert Olsson19baf832005-06-21 12:43:18 -07001720{
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001721 do {
1722 t_key idx;
Robert Olsson19baf832005-06-21 12:43:18 -07001723
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001724 if (c)
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001725 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001726 else
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001727 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001728
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001729 while (idx < 1u << p->bits) {
1730 c = tnode_get_child_rcu(p, idx++);
Robert Olsson2373ce12005-08-25 13:01:29 -07001731 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001732 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001733
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001734 if (IS_LEAF(c)) {
1735 prefetch(p->child[idx]);
1736 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001737 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001738
1739 /* Rescan start scanning in new node */
1740 p = (struct tnode *) c;
1741 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001742 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001743
1744 /* Node empty, walk back up to parent */
Olof Johansson91b9a272005-08-09 20:24:39 -07001745 c = (struct node *) p;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001746 } while ( (p = node_parent_rcu(c)) != NULL);
1747
1748 return NULL; /* Root of trie */
1749}
1750
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001751static struct leaf *trie_firstleaf(struct trie *t)
1752{
1753 struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
1754
1755 if (!n)
1756 return NULL;
1757
1758 if (IS_LEAF(n)) /* trie is just a leaf */
1759 return (struct leaf *) n;
1760
1761 return leaf_walk_rcu(n, NULL);
1762}
1763
1764static struct leaf *trie_nextleaf(struct leaf *l)
1765{
1766 struct node *c = (struct node *) l;
Jarek Poplawskib902e572009-07-14 11:20:32 +00001767 struct tnode *p = node_parent_rcu(c);
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001768
1769 if (!p)
1770 return NULL; /* trie with just one leaf */
1771
1772 return leaf_walk_rcu(p, c);
Robert Olsson19baf832005-06-21 12:43:18 -07001773}
1774
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001775static struct leaf *trie_leafindex(struct trie *t, int index)
1776{
1777 struct leaf *l = trie_firstleaf(t);
1778
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001779 while (l && index-- > 0)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001780 l = trie_nextleaf(l);
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001781
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001782 return l;
1783}
1784
1785
Robert Olssond562f1f2007-03-26 14:22:22 -07001786/*
1787 * Caller must hold RTNL.
1788 */
Robert Olsson19baf832005-06-21 12:43:18 -07001789static int fn_trie_flush(struct fib_table *tb)
1790{
1791 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001792 struct leaf *l, *ll = NULL;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001793 int found = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001794
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001795 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001796 found += trie_flush_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001797
1798 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001799 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001800 ll = l;
1801 }
1802
1803 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001804 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001805
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001806 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001807 return found;
1808}
1809
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001810static void fn_trie_select_default(struct fib_table *tb,
1811 const struct flowi *flp,
1812 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001813{
1814 struct trie *t = (struct trie *) tb->tb_data;
1815 int order, last_idx;
1816 struct fib_info *fi = NULL;
1817 struct fib_info *last_resort;
1818 struct fib_alias *fa = NULL;
1819 struct list_head *fa_head;
1820 struct leaf *l;
1821
1822 last_idx = -1;
1823 last_resort = NULL;
1824 order = -1;
1825
Robert Olsson2373ce12005-08-25 13:01:29 -07001826 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001827
Robert Olsson19baf832005-06-21 12:43:18 -07001828 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001829 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001830 goto out;
1831
1832 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001833 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001834 goto out;
1835
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001836 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001837 goto out;
1838
Robert Olsson2373ce12005-08-25 13:01:29 -07001839 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001840 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001841
Robert Olsson19baf832005-06-21 12:43:18 -07001842 if (fa->fa_scope != res->scope ||
1843 fa->fa_type != RTN_UNICAST)
1844 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001845
Robert Olsson19baf832005-06-21 12:43:18 -07001846 if (next_fi->fib_priority > res->fi->fib_priority)
1847 break;
1848 if (!next_fi->fib_nh[0].nh_gw ||
1849 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1850 continue;
1851 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001852
Robert Olsson19baf832005-06-21 12:43:18 -07001853 if (fi == NULL) {
1854 if (next_fi != res->fi)
1855 break;
1856 } else if (!fib_detect_death(fi, order, &last_resort,
Denis V. Lunev971b8932007-12-08 00:32:23 -08001857 &last_idx, tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001858 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001859 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001860 goto out;
1861 }
1862 fi = next_fi;
1863 order++;
1864 }
1865 if (order <= 0 || fi == NULL) {
Denis V. Lunev971b8932007-12-08 00:32:23 -08001866 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001867 goto out;
1868 }
1869
Denis V. Lunev971b8932007-12-08 00:32:23 -08001870 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1871 tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001872 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001873 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001874 goto out;
1875 }
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001876 if (last_idx >= 0)
1877 fib_result_assign(res, last_resort);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001878 tb->tb_default = last_idx;
1879out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001880 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001881}
1882
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001883static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1884 struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001885 struct sk_buff *skb, struct netlink_callback *cb)
1886{
1887 int i, s_i;
1888 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07001889 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001890
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001891 s_i = cb->args[5];
Robert Olsson19baf832005-06-21 12:43:18 -07001892 i = 0;
1893
Robert Olsson2373ce12005-08-25 13:01:29 -07001894 /* rcu_read_lock is hold by caller */
1895
1896 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001897 if (i < s_i) {
1898 i++;
1899 continue;
1900 }
Robert Olsson19baf832005-06-21 12:43:18 -07001901
1902 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1903 cb->nlh->nlmsg_seq,
1904 RTM_NEWROUTE,
1905 tb->tb_id,
1906 fa->fa_type,
1907 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001908 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001909 plen,
1910 fa->fa_tos,
Stephen Hemminger64347f72008-01-22 21:55:01 -08001911 fa->fa_info, NLM_F_MULTI) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001912 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001913 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001914 }
Robert Olsson19baf832005-06-21 12:43:18 -07001915 i++;
1916 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001917 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001918 return skb->len;
1919}
1920
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001921static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1922 struct sk_buff *skb, struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001923{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001924 struct leaf_info *li;
1925 struct hlist_node *node;
1926 int i, s_i;
Robert Olsson19baf832005-06-21 12:43:18 -07001927
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001928 s_i = cb->args[4];
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001929 i = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001930
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001931 /* rcu_read_lock is hold by caller */
1932 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1933 if (i < s_i) {
1934 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001935 continue;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001936 }
Robert Olsson19baf832005-06-21 12:43:18 -07001937
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001938 if (i > s_i)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001939 cb->args[5] = 0;
Olof Johansson91b9a272005-08-09 20:24:39 -07001940
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001941 if (list_empty(&li->falh))
Robert Olsson19baf832005-06-21 12:43:18 -07001942 continue;
1943
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001944 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001945 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001946 return -1;
1947 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001948 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001949 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001950
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001951 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001952 return skb->len;
1953}
1954
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001955static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
1956 struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001957{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001958 struct leaf *l;
Robert Olsson19baf832005-06-21 12:43:18 -07001959 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001960 t_key key = cb->args[2];
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001961 int count = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001962
Robert Olsson2373ce12005-08-25 13:01:29 -07001963 rcu_read_lock();
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001964 /* Dump starting at last key.
1965 * Note: 0.0.0.0/0 (ie default) is first key.
1966 */
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001967 if (count == 0)
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001968 l = trie_firstleaf(t);
1969 else {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001970 /* Normally, continue from last key, but if that is missing
1971 * fallback to using slow rescan
1972 */
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001973 l = fib_find_node(t, key);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001974 if (!l)
1975 l = trie_leafindex(t, count);
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001976 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001977
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001978 while (l) {
1979 cb->args[2] = l->key;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001980 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001981 cb->args[3] = count;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001982 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001983 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001984 }
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001985
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001986 ++count;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001987 l = trie_nextleaf(l);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001988 memset(&cb->args[4], 0,
1989 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001990 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001991 cb->args[3] = count;
Robert Olsson2373ce12005-08-25 13:01:29 -07001992 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001993
Robert Olsson19baf832005-06-21 12:43:18 -07001994 return skb->len;
Robert Olsson19baf832005-06-21 12:43:18 -07001995}
1996
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001997void __init fib_hash_init(void)
1998{
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001999 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
2000 sizeof(struct fib_alias),
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08002001 0, SLAB_PANIC, NULL);
2002
2003 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
2004 max(sizeof(struct leaf),
2005 sizeof(struct leaf_info)),
2006 0, SLAB_PANIC, NULL);
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08002007}
Robert Olsson19baf832005-06-21 12:43:18 -07002008
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08002009
2010/* Fix more generic FIB names for init later */
2011struct fib_table *fib_hash_table(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07002012{
2013 struct fib_table *tb;
2014 struct trie *t;
2015
Robert Olsson19baf832005-06-21 12:43:18 -07002016 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2017 GFP_KERNEL);
2018 if (tb == NULL)
2019 return NULL;
2020
2021 tb->tb_id = id;
Denis V. Lunev971b8932007-12-08 00:32:23 -08002022 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07002023 tb->tb_lookup = fn_trie_lookup;
2024 tb->tb_insert = fn_trie_insert;
2025 tb->tb_delete = fn_trie_delete;
2026 tb->tb_flush = fn_trie_flush;
2027 tb->tb_select_default = fn_trie_select_default;
2028 tb->tb_dump = fn_trie_dump;
Robert Olsson19baf832005-06-21 12:43:18 -07002029
2030 t = (struct trie *) tb->tb_data;
Stephen Hemmingerc28a1cf2008-01-12 20:49:13 -08002031 memset(t, 0, sizeof(*t));
Robert Olsson19baf832005-06-21 12:43:18 -07002032
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002033 if (id == RT_TABLE_LOCAL)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002034 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07002035
2036 return tb;
2037}
2038
Robert Olsson19baf832005-06-21 12:43:18 -07002039#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002040/* Depth first Trie walk iterator */
2041struct fib_trie_iter {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002042 struct seq_net_private p;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002043 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002044 struct tnode *tnode;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002045 unsigned index;
2046 unsigned depth;
2047};
Robert Olsson19baf832005-06-21 12:43:18 -07002048
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002049static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002050{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002051 struct tnode *tn = iter->tnode;
2052 unsigned cindex = iter->index;
2053 struct tnode *p;
2054
Eric W. Biederman6640e692007-01-24 14:42:04 -08002055 /* A single entry routing table */
2056 if (!tn)
2057 return NULL;
2058
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002059 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2060 iter->tnode, iter->index, iter->depth);
2061rescan:
2062 while (cindex < (1<<tn->bits)) {
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002063 struct node *n = tnode_get_child_rcu(tn, cindex);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002064
2065 if (n) {
2066 if (IS_LEAF(n)) {
2067 iter->tnode = tn;
2068 iter->index = cindex + 1;
2069 } else {
2070 /* push down one level */
2071 iter->tnode = (struct tnode *) n;
2072 iter->index = 0;
2073 ++iter->depth;
2074 }
2075 return n;
2076 }
2077
2078 ++cindex;
2079 }
2080
2081 /* Current node exhausted, pop back up */
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002082 p = node_parent_rcu((struct node *)tn);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002083 if (p) {
2084 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2085 tn = p;
2086 --iter->depth;
2087 goto rescan;
2088 }
2089
2090 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002091 return NULL;
2092}
2093
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002094static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2095 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002096{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002097 struct node *n;
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002098
Stephen Hemminger132adf52007-03-08 20:44:43 -08002099 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002100 return NULL;
2101
2102 n = rcu_dereference(t->trie);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002103 if (!n)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002104 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002105
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002106 if (IS_TNODE(n)) {
2107 iter->tnode = (struct tnode *) n;
2108 iter->index = 0;
2109 iter->depth = 1;
2110 } else {
2111 iter->tnode = NULL;
2112 iter->index = 0;
2113 iter->depth = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002114 }
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002115
2116 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002117}
2118
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002119static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002120{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002121 struct node *n;
2122 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002123
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002124 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002125
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002126 rcu_read_lock();
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002127 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002128 if (IS_LEAF(n)) {
Stephen Hemminger93672292008-01-22 21:54:05 -08002129 struct leaf *l = (struct leaf *)n;
2130 struct leaf_info *li;
2131 struct hlist_node *tmp;
2132
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002133 s->leaves++;
2134 s->totdepth += iter.depth;
2135 if (iter.depth > s->maxdepth)
2136 s->maxdepth = iter.depth;
Stephen Hemminger93672292008-01-22 21:54:05 -08002137
2138 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2139 ++s->prefixes;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002140 } else {
2141 const struct tnode *tn = (const struct tnode *) n;
2142 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002143
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002144 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002145 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002146 s->nodesizes[tn->bits]++;
2147
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002148 for (i = 0; i < (1<<tn->bits); i++)
2149 if (!tn->child[i])
2150 s->nullpointers++;
2151 }
2152 }
2153 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002154}
2155
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002156/*
Robert Olsson19baf832005-06-21 12:43:18 -07002157 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002158 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002159static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002160{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002161 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002162
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002163 if (stat->leaves)
2164 avdepth = stat->totdepth*100 / stat->leaves;
2165 else
2166 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002167
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002168 seq_printf(seq, "\tAver depth: %u.%02d\n",
2169 avdepth / 100, avdepth % 100);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002170 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002171
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002172 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002173 bytes = sizeof(struct leaf) * stat->leaves;
Stephen Hemminger93672292008-01-22 21:54:05 -08002174
2175 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2176 bytes += sizeof(struct leaf_info) * stat->prefixes;
2177
Stephen Hemminger187b5182008-01-12 20:55:55 -08002178 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002179 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002180
Robert Olsson06ef9212006-03-20 21:35:01 -08002181 max = MAX_STAT_DEPTH;
2182 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002183 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002184
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002185 pointers = 0;
2186 for (i = 1; i <= max; i++)
2187 if (stat->nodesizes[i] != 0) {
Stephen Hemminger187b5182008-01-12 20:55:55 -08002188 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002189 pointers += (1<<i) * stat->nodesizes[i];
2190 }
2191 seq_putc(seq, '\n');
Stephen Hemminger187b5182008-01-12 20:55:55 -08002192 seq_printf(seq, "\tPointers: %u\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002193
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002194 bytes += sizeof(struct node *) * pointers;
Stephen Hemminger187b5182008-01-12 20:55:55 -08002195 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2196 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002197}
Robert Olsson19baf832005-06-21 12:43:18 -07002198
2199#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002200static void trie_show_usage(struct seq_file *seq,
2201 const struct trie_use_stats *stats)
2202{
2203 seq_printf(seq, "\nCounters:\n---------\n");
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002204 seq_printf(seq, "gets = %u\n", stats->gets);
2205 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2206 seq_printf(seq, "semantic match passed = %u\n",
2207 stats->semantic_match_passed);
2208 seq_printf(seq, "semantic match miss = %u\n",
2209 stats->semantic_match_miss);
2210 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2211 seq_printf(seq, "skipped node resize = %u\n\n",
2212 stats->resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002213}
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002214#endif /* CONFIG_IP_FIB_TRIE_STATS */
2215
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002216static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002217{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002218 if (tb->tb_id == RT_TABLE_LOCAL)
2219 seq_puts(seq, "Local:\n");
2220 else if (tb->tb_id == RT_TABLE_MAIN)
2221 seq_puts(seq, "Main:\n");
2222 else
2223 seq_printf(seq, "Id %d:\n", tb->tb_id);
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002224}
Robert Olsson19baf832005-06-21 12:43:18 -07002225
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002226
Robert Olsson19baf832005-06-21 12:43:18 -07002227static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2228{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002229 struct net *net = (struct net *)seq->private;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002230 unsigned int h;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002231
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002232 seq_printf(seq,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002233 "Basic info: size of leaf:"
2234 " %Zd bytes, size of tnode: %Zd bytes.\n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002235 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002236
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002237 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2238 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2239 struct hlist_node *node;
2240 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002241
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002242 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2243 struct trie *t = (struct trie *) tb->tb_data;
2244 struct trie_stat stat;
2245
2246 if (!t)
2247 continue;
2248
2249 fib_table_print(seq, tb);
2250
2251 trie_collect_stats(t, &stat);
2252 trie_show_stats(seq, &stat);
2253#ifdef CONFIG_IP_FIB_TRIE_STATS
2254 trie_show_usage(seq, &t->stats);
2255#endif
2256 }
2257 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002258
Robert Olsson19baf832005-06-21 12:43:18 -07002259 return 0;
2260}
2261
Robert Olsson19baf832005-06-21 12:43:18 -07002262static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2263{
Pavel Emelyanovde05c552008-07-18 04:07:21 -07002264 return single_open_net(inode, file, fib_triestat_seq_show);
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002265}
2266
Arjan van de Ven9a321442007-02-12 00:55:35 -08002267static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002268 .owner = THIS_MODULE,
2269 .open = fib_triestat_seq_open,
2270 .read = seq_read,
2271 .llseek = seq_lseek,
Pavel Emelyanovb6fcbdb2008-07-18 04:07:44 -07002272 .release = single_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002273};
2274
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002275static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002276{
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002277 struct fib_trie_iter *iter = seq->private;
2278 struct net *net = seq_file_net(seq);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002279 loff_t idx = 0;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002280 unsigned int h;
Robert Olsson19baf832005-06-21 12:43:18 -07002281
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002282 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2283 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2284 struct hlist_node *node;
2285 struct fib_table *tb;
2286
2287 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2288 struct node *n;
2289
2290 for (n = fib_trie_get_first(iter,
2291 (struct trie *) tb->tb_data);
2292 n; n = fib_trie_get_next(iter))
2293 if (pos == idx++) {
2294 iter->tb = tb;
2295 return n;
2296 }
2297 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002298 }
Robert Olsson19baf832005-06-21 12:43:18 -07002299
Robert Olsson19baf832005-06-21 12:43:18 -07002300 return NULL;
2301}
2302
2303static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002304 __acquires(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002305{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002306 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002307 return fib_trie_get_idx(seq, *pos);
Robert Olsson19baf832005-06-21 12:43:18 -07002308}
2309
2310static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2311{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002312 struct fib_trie_iter *iter = seq->private;
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002313 struct net *net = seq_file_net(seq);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002314 struct fib_table *tb = iter->tb;
2315 struct hlist_node *tb_node;
2316 unsigned int h;
2317 struct node *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002318
Robert Olsson19baf832005-06-21 12:43:18 -07002319 ++*pos;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002320 /* next node in same table */
2321 n = fib_trie_get_next(iter);
2322 if (n)
2323 return n;
Olof Johansson91b9a272005-08-09 20:24:39 -07002324
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002325 /* walk rest of this hash chain */
2326 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2327 while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
2328 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2329 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2330 if (n)
2331 goto found;
2332 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002333
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002334 /* new hash chain */
2335 while (++h < FIB_TABLE_HASHSZ) {
2336 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2337 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2338 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2339 if (n)
2340 goto found;
2341 }
2342 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002343 return NULL;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002344
2345found:
2346 iter->tb = tb;
2347 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002348}
2349
2350static void fib_trie_seq_stop(struct seq_file *seq, void *v)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002351 __releases(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002352{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002353 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002354}
2355
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002356static void seq_indent(struct seq_file *seq, int n)
2357{
2358 while (n-- > 0) seq_puts(seq, " ");
2359}
Robert Olsson19baf832005-06-21 12:43:18 -07002360
Eric Dumazet28d36e32008-01-14 23:09:56 -08002361static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002362{
Stephen Hemminger132adf52007-03-08 20:44:43 -08002363 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002364 case RT_SCOPE_UNIVERSE: return "universe";
2365 case RT_SCOPE_SITE: return "site";
2366 case RT_SCOPE_LINK: return "link";
2367 case RT_SCOPE_HOST: return "host";
2368 case RT_SCOPE_NOWHERE: return "nowhere";
2369 default:
Eric Dumazet28d36e32008-01-14 23:09:56 -08002370 snprintf(buf, len, "scope=%d", s);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002371 return buf;
2372 }
2373}
2374
Jan Engelhardt36cbd3d2009-08-05 10:42:58 -07002375static const char *const rtn_type_names[__RTN_MAX] = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002376 [RTN_UNSPEC] = "UNSPEC",
2377 [RTN_UNICAST] = "UNICAST",
2378 [RTN_LOCAL] = "LOCAL",
2379 [RTN_BROADCAST] = "BROADCAST",
2380 [RTN_ANYCAST] = "ANYCAST",
2381 [RTN_MULTICAST] = "MULTICAST",
2382 [RTN_BLACKHOLE] = "BLACKHOLE",
2383 [RTN_UNREACHABLE] = "UNREACHABLE",
2384 [RTN_PROHIBIT] = "PROHIBIT",
2385 [RTN_THROW] = "THROW",
2386 [RTN_NAT] = "NAT",
2387 [RTN_XRESOLVE] = "XRESOLVE",
2388};
2389
Eric Dumazet28d36e32008-01-14 23:09:56 -08002390static inline const char *rtn_type(char *buf, size_t len, unsigned t)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002391{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002392 if (t < __RTN_MAX && rtn_type_names[t])
2393 return rtn_type_names[t];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002394 snprintf(buf, len, "type %u", t);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002395 return buf;
2396}
2397
2398/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002399static int fib_trie_seq_show(struct seq_file *seq, void *v)
2400{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002401 const struct fib_trie_iter *iter = seq->private;
2402 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002403
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002404 if (!node_parent_rcu(n))
2405 fib_table_print(seq, iter->tb);
Robert Olsson095b8502007-01-26 19:06:01 -08002406
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002407 if (IS_TNODE(n)) {
2408 struct tnode *tn = (struct tnode *) n;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07002409 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002410
Robert Olsson1d25cd62005-09-19 15:29:52 -07002411 seq_indent(seq, iter->depth-1);
Harvey Harrison673d57e2008-10-31 00:53:57 -07002412 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2413 &prf, tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002414 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002415
Olof Johansson91b9a272005-08-09 20:24:39 -07002416 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002417 struct leaf *l = (struct leaf *) n;
Stephen Hemminger13280422008-01-22 21:54:37 -08002418 struct leaf_info *li;
2419 struct hlist_node *node;
Al Viro32ab5f82006-09-26 22:21:45 -07002420 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002421
2422 seq_indent(seq, iter->depth);
Harvey Harrison673d57e2008-10-31 00:53:57 -07002423 seq_printf(seq, " |-- %pI4\n", &val);
Eric Dumazet28d36e32008-01-14 23:09:56 -08002424
Stephen Hemminger13280422008-01-22 21:54:37 -08002425 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2426 struct fib_alias *fa;
Eric Dumazet28d36e32008-01-14 23:09:56 -08002427
Stephen Hemminger13280422008-01-22 21:54:37 -08002428 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2429 char buf1[32], buf2[32];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002430
Stephen Hemminger13280422008-01-22 21:54:37 -08002431 seq_indent(seq, iter->depth+1);
2432 seq_printf(seq, " /%d %s %s", li->plen,
2433 rtn_scope(buf1, sizeof(buf1),
2434 fa->fa_scope),
2435 rtn_type(buf2, sizeof(buf2),
2436 fa->fa_type));
2437 if (fa->fa_tos)
Denis V. Lunevb9c4d822008-02-05 02:58:45 -08002438 seq_printf(seq, " tos=%d", fa->fa_tos);
Stephen Hemminger13280422008-01-22 21:54:37 -08002439 seq_putc(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002440 }
2441 }
Robert Olsson19baf832005-06-21 12:43:18 -07002442 }
2443
2444 return 0;
2445}
2446
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002447static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002448 .start = fib_trie_seq_start,
2449 .next = fib_trie_seq_next,
2450 .stop = fib_trie_seq_stop,
2451 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002452};
2453
2454static int fib_trie_seq_open(struct inode *inode, struct file *file)
2455{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002456 return seq_open_net(inode, file, &fib_trie_seq_ops,
2457 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002458}
2459
Arjan van de Ven9a321442007-02-12 00:55:35 -08002460static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002461 .owner = THIS_MODULE,
2462 .open = fib_trie_seq_open,
2463 .read = seq_read,
2464 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002465 .release = seq_release_net,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002466};
2467
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002468struct fib_route_iter {
2469 struct seq_net_private p;
2470 struct trie *main_trie;
2471 loff_t pos;
2472 t_key key;
2473};
2474
2475static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2476{
2477 struct leaf *l = NULL;
2478 struct trie *t = iter->main_trie;
2479
2480 /* use cache location of last found key */
2481 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2482 pos -= iter->pos;
2483 else {
2484 iter->pos = 0;
2485 l = trie_firstleaf(t);
2486 }
2487
2488 while (l && pos-- > 0) {
2489 iter->pos++;
2490 l = trie_nextleaf(l);
2491 }
2492
2493 if (l)
2494 iter->key = pos; /* remember it */
2495 else
2496 iter->pos = 0; /* forget it */
2497
2498 return l;
2499}
2500
2501static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2502 __acquires(RCU)
2503{
2504 struct fib_route_iter *iter = seq->private;
2505 struct fib_table *tb;
2506
2507 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002508 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002509 if (!tb)
2510 return NULL;
2511
2512 iter->main_trie = (struct trie *) tb->tb_data;
2513 if (*pos == 0)
2514 return SEQ_START_TOKEN;
2515 else
2516 return fib_route_get_idx(iter, *pos - 1);
2517}
2518
2519static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2520{
2521 struct fib_route_iter *iter = seq->private;
2522 struct leaf *l = v;
2523
2524 ++*pos;
2525 if (v == SEQ_START_TOKEN) {
2526 iter->pos = 0;
2527 l = trie_firstleaf(iter->main_trie);
2528 } else {
2529 iter->pos++;
2530 l = trie_nextleaf(l);
2531 }
2532
2533 if (l)
2534 iter->key = l->key;
2535 else
2536 iter->pos = 0;
2537 return l;
2538}
2539
2540static void fib_route_seq_stop(struct seq_file *seq, void *v)
2541 __releases(RCU)
2542{
2543 rcu_read_unlock();
2544}
2545
Al Viro32ab5f82006-09-26 22:21:45 -07002546static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002547{
2548 static unsigned type2flags[RTN_MAX + 1] = {
2549 [7] = RTF_REJECT, [8] = RTF_REJECT,
2550 };
2551 unsigned flags = type2flags[type];
2552
2553 if (fi && fi->fib_nh->nh_gw)
2554 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002555 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002556 flags |= RTF_HOST;
2557 flags |= RTF_UP;
2558 return flags;
2559}
2560
2561/*
2562 * This outputs /proc/net/route.
2563 * The format of the file is not supposed to be changed
2564 * and needs to be same as fib_hash output to avoid breaking
2565 * legacy utilities
2566 */
2567static int fib_route_seq_show(struct seq_file *seq, void *v)
2568{
2569 struct leaf *l = v;
Stephen Hemminger13280422008-01-22 21:54:37 -08002570 struct leaf_info *li;
2571 struct hlist_node *node;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002572
2573 if (v == SEQ_START_TOKEN) {
2574 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2575 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2576 "\tWindow\tIRTT");
2577 return 0;
2578 }
2579
Stephen Hemminger13280422008-01-22 21:54:37 -08002580 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002581 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002582 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002583
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002584 mask = inet_make_mask(li->plen);
2585 prefix = htonl(l->key);
2586
2587 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002588 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002589 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002590 int len;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002591
2592 if (fa->fa_type == RTN_BROADCAST
2593 || fa->fa_type == RTN_MULTICAST)
2594 continue;
2595
2596 if (fi)
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002597 seq_printf(seq,
2598 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2599 "%d\t%08X\t%d\t%u\t%u%n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002600 fi->fib_dev ? fi->fib_dev->name : "*",
2601 prefix,
2602 fi->fib_nh->nh_gw, flags, 0, 0,
2603 fi->fib_priority,
2604 mask,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002605 (fi->fib_advmss ?
2606 fi->fib_advmss + 40 : 0),
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002607 fi->fib_window,
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002608 fi->fib_rtt >> 3, &len);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002609 else
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002610 seq_printf(seq,
2611 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2612 "%d\t%08X\t%d\t%u\t%u%n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002613 prefix, 0, flags, 0, 0, 0,
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002614 mask, 0, 0, 0, &len);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002615
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002616 seq_printf(seq, "%*s\n", 127 - len, "");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002617 }
2618 }
2619
2620 return 0;
2621}
2622
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002623static const struct seq_operations fib_route_seq_ops = {
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002624 .start = fib_route_seq_start,
2625 .next = fib_route_seq_next,
2626 .stop = fib_route_seq_stop,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002627 .show = fib_route_seq_show,
2628};
2629
2630static int fib_route_seq_open(struct inode *inode, struct file *file)
2631{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002632 return seq_open_net(inode, file, &fib_route_seq_ops,
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002633 sizeof(struct fib_route_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002634}
2635
Arjan van de Ven9a321442007-02-12 00:55:35 -08002636static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002637 .owner = THIS_MODULE,
2638 .open = fib_route_seq_open,
2639 .read = seq_read,
2640 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002641 .release = seq_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002642};
2643
Denis V. Lunev61a02652008-01-10 03:21:09 -08002644int __net_init fib_proc_init(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002645{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002646 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002647 goto out1;
2648
Denis V. Lunev61a02652008-01-10 03:21:09 -08002649 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2650 &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002651 goto out2;
2652
Denis V. Lunev61a02652008-01-10 03:21:09 -08002653 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002654 goto out3;
2655
Robert Olsson19baf832005-06-21 12:43:18 -07002656 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002657
2658out3:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002659 proc_net_remove(net, "fib_triestat");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002660out2:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002661 proc_net_remove(net, "fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002662out1:
2663 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002664}
2665
Denis V. Lunev61a02652008-01-10 03:21:09 -08002666void __net_exit fib_proc_exit(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002667{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002668 proc_net_remove(net, "fib_trie");
2669 proc_net_remove(net, "fib_triestat");
2670 proc_net_remove(net, "route");
Robert Olsson19baf832005-06-21 12:43:18 -07002671}
2672
2673#endif /* CONFIG_PROC_FS */