blob: ea294fffb9cef37c621fec8c9e14485d98475f83 [file] [log] [blame]
Robert Olsson19baf832005-06-21 12:43:18 -07001/*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
6 *
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
9 *
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090010 * Jens Laas <jens.laas@data.slu.se> Swedish University of
Robert Olsson19baf832005-06-21 12:43:18 -070011 * Agricultural Sciences.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090012 *
Robert Olsson19baf832005-06-21 12:43:18 -070013 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
14 *
15 * This work is based on the LPC-trie which is originally descibed in:
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090016 *
Robert Olsson19baf832005-06-21 12:43:18 -070017 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
20 *
21 *
22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
24 *
25 * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
26 *
27 *
28 * Code from fib_hash has been reused which includes the following header:
29 *
30 *
31 * INET An implementation of the TCP/IP protocol suite for the LINUX
32 * operating system. INET is implemented using the BSD Socket
33 * interface as the means of communication with the user level.
34 *
35 * IPv4 FIB: lookup engine and maintenance routines.
36 *
37 *
38 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
39 *
40 * This program is free software; you can redistribute it and/or
41 * modify it under the terms of the GNU General Public License
42 * as published by the Free Software Foundation; either version
43 * 2 of the License, or (at your option) any later version.
Robert Olssonfd966252005-12-22 11:25:10 -080044 *
45 * Substantial contributions to this work comes from:
46 *
47 * David S. Miller, <davem@davemloft.net>
48 * Stephen Hemminger <shemminger@osdl.org>
49 * Paul E. McKenney <paulmck@us.ibm.com>
50 * Patrick McHardy <kaber@trash.net>
Robert Olsson19baf832005-06-21 12:43:18 -070051 */
52
Robert Olsson05eee482007-03-19 16:27:37 -070053#define VERSION "0.408"
Robert Olsson19baf832005-06-21 12:43:18 -070054
Robert Olsson19baf832005-06-21 12:43:18 -070055#include <asm/uaccess.h>
56#include <asm/system.h>
Jiri Slaby1977f032007-10-18 23:40:25 -070057#include <linux/bitops.h>
Robert Olsson19baf832005-06-21 12:43:18 -070058#include <linux/types.h>
59#include <linux/kernel.h>
Robert Olsson19baf832005-06-21 12:43:18 -070060#include <linux/mm.h>
61#include <linux/string.h>
62#include <linux/socket.h>
63#include <linux/sockios.h>
64#include <linux/errno.h>
65#include <linux/in.h>
66#include <linux/inet.h>
Stephen Hemmingercd8787a2006-01-03 14:38:34 -080067#include <linux/inetdevice.h>
Robert Olsson19baf832005-06-21 12:43:18 -070068#include <linux/netdevice.h>
69#include <linux/if_arp.h>
70#include <linux/proc_fs.h>
Robert Olsson2373ce12005-08-25 13:01:29 -070071#include <linux/rcupdate.h>
Robert Olsson19baf832005-06-21 12:43:18 -070072#include <linux/skbuff.h>
73#include <linux/netlink.h>
74#include <linux/init.h>
75#include <linux/list.h>
Eric W. Biederman457c4cb2007-09-12 12:01:34 +020076#include <net/net_namespace.h>
Robert Olsson19baf832005-06-21 12:43:18 -070077#include <net/ip.h>
78#include <net/protocol.h>
79#include <net/route.h>
80#include <net/tcp.h>
81#include <net/sock.h>
82#include <net/ip_fib.h>
83#include "fib_lookup.h"
84
Robert Olsson06ef9212006-03-20 21:35:01 -080085#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070086
Robert Olsson19baf832005-06-21 12:43:18 -070087#define KEYLENGTH (8*sizeof(t_key))
Robert Olsson19baf832005-06-21 12:43:18 -070088
Robert Olsson19baf832005-06-21 12:43:18 -070089typedef unsigned int t_key;
90
91#define T_TNODE 0
92#define T_LEAF 1
93#define NODE_TYPE_MASK 0x1UL
Robert Olsson2373ce12005-08-25 13:01:29 -070094#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
95
Olof Johansson91b9a272005-08-09 20:24:39 -070096#define IS_TNODE(n) (!(n->parent & T_LEAF))
97#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -070098
99struct node {
Olof Johansson91b9a272005-08-09 20:24:39 -0700100 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800101 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700102};
103
104struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700105 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800106 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700107 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700108 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700109};
110
111struct leaf_info {
112 struct hlist_node hlist;
Robert Olsson2373ce12005-08-25 13:01:29 -0700113 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700114 int plen;
115 struct list_head falh;
116};
117
118struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700119 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800120 t_key key;
Eric Dumazet112d8cf2008-01-12 21:27:41 -0800121 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
122 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
Eric Dumazet8d965442008-01-13 22:31:44 -0800123 unsigned int full_children; /* KEYLENGTH bits needed */
124 unsigned int empty_children; /* KEYLENGTH bits needed */
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700125 union {
126 struct rcu_head rcu;
127 struct work_struct work;
128 };
Olof Johansson91b9a272005-08-09 20:24:39 -0700129 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700130};
131
132#ifdef CONFIG_IP_FIB_TRIE_STATS
133struct trie_use_stats {
134 unsigned int gets;
135 unsigned int backtrack;
136 unsigned int semantic_match_passed;
137 unsigned int semantic_match_miss;
138 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700139 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700140};
141#endif
142
143struct trie_stat {
144 unsigned int totdepth;
145 unsigned int maxdepth;
146 unsigned int tnodes;
147 unsigned int leaves;
148 unsigned int nullpointers;
Stephen Hemminger93672292008-01-22 21:54:05 -0800149 unsigned int prefixes;
Robert Olsson06ef9212006-03-20 21:35:01 -0800150 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700151};
Robert Olsson19baf832005-06-21 12:43:18 -0700152
153struct trie {
Olof Johansson91b9a272005-08-09 20:24:39 -0700154 struct node *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700155#ifdef CONFIG_IP_FIB_TRIE_STATS
156 struct trie_use_stats stats;
157#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700158};
159
Robert Olsson19baf832005-06-21 12:43:18 -0700160static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800161static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
162 int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700163static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700164static struct tnode *inflate(struct trie *t, struct tnode *tn);
165static struct tnode *halve(struct trie *t, struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700166
Christoph Lametere18b8902006-12-06 20:33:20 -0800167static struct kmem_cache *fn_alias_kmem __read_mostly;
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800168static struct kmem_cache *trie_leaf_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700169
Stephen Hemminger06801912007-08-10 15:22:13 -0700170static inline struct tnode *node_parent(struct node *node)
171{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800172 return (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
173}
Stephen Hemminger06801912007-08-10 15:22:13 -0700174
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800175static inline struct tnode *node_parent_rcu(struct node *node)
176{
177 struct tnode *ret = node_parent(node);
178
Stephen Hemminger06801912007-08-10 15:22:13 -0700179 return rcu_dereference(ret);
180}
181
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700182/* Same as rcu_assign_pointer
183 * but that macro() assumes that value is a pointer.
184 */
Stephen Hemminger06801912007-08-10 15:22:13 -0700185static inline void node_set_parent(struct node *node, struct tnode *ptr)
186{
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700187 smp_wmb();
188 node->parent = (unsigned long)ptr | NODE_TYPE(node);
Stephen Hemminger06801912007-08-10 15:22:13 -0700189}
Robert Olsson2373ce12005-08-25 13:01:29 -0700190
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800191static inline struct node *tnode_get_child(struct tnode *tn, unsigned int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700192{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800193 BUG_ON(i >= 1U << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700194
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800195 return tn->child[i];
196}
197
198static inline struct node *tnode_get_child_rcu(struct tnode *tn, unsigned int i)
199{
200 struct node *ret = tnode_get_child(tn, i);
201
202 return rcu_dereference(ret);
Robert Olsson19baf832005-06-21 12:43:18 -0700203}
204
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700205static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700206{
Olof Johansson91b9a272005-08-09 20:24:39 -0700207 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700208}
209
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700210static inline t_key mask_pfx(t_key k, unsigned short l)
211{
212 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
213}
214
Robert Olsson19baf832005-06-21 12:43:18 -0700215static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
216{
Olof Johansson91b9a272005-08-09 20:24:39 -0700217 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700218 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700219 else
Robert Olsson19baf832005-06-21 12:43:18 -0700220 return 0;
221}
222
223static inline int tkey_equals(t_key a, t_key b)
224{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700225 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700226}
227
228static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
229{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700230 if (bits == 0 || offset >= KEYLENGTH)
231 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700232 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
233 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700234}
Robert Olsson19baf832005-06-21 12:43:18 -0700235
236static inline int tkey_mismatch(t_key a, int offset, t_key b)
237{
238 t_key diff = a ^ b;
239 int i = offset;
240
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700241 if (!diff)
242 return 0;
243 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700244 i++;
245 return i;
246}
247
Robert Olsson19baf832005-06-21 12:43:18 -0700248/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900249 To understand this stuff, an understanding of keys and all their bits is
250 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700251 all of the bits in that key are significant.
252
253 Consider a node 'n' and its parent 'tp'.
254
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900255 If n is a leaf, every bit in its key is significant. Its presence is
256 necessitated by path compression, since during a tree traversal (when
257 searching for a leaf - unless we are doing an insertion) we will completely
258 ignore all skipped bits we encounter. Thus we need to verify, at the end of
259 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700260 correct key path.
261
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900262 Note that we can never "miss" the correct key in the tree if present by
263 following the wrong path. Path compression ensures that segments of the key
264 that are the same for all keys with a given prefix are skipped, but the
265 skipped part *is* identical for each node in the subtrie below the skipped
266 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700267 call to tkey_sub_equals() in trie_insert().
268
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900269 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700270 have many different meanings.
271
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900272 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700273 _________________________________________________________________
274 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
275 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900276 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700277
278 _________________________________________________________________
279 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
280 -----------------------------------------------------------------
281 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
282
283 tp->pos = 7
284 tp->bits = 3
285 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700286 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700287
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900288 First, let's just ignore the bits that come before the parent tp, that is
289 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700290 not use them for anything.
291
292 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900293 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700294 'n' among tp's children.
295
296 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
297 for the node n.
298
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900299 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700300 of the bits are really not needed or indeed known in n->key.
301
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900302 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700303 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900304
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700305
Robert Olsson19baf832005-06-21 12:43:18 -0700306 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
307 at this point.
308
309*/
310
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700311static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700312{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700313 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700314}
315
Denis V. Lunevf5026fa2007-12-13 09:47:57 -0800316static const int halve_threshold = 25;
317static const int inflate_threshold = 50;
318static const int halve_threshold_root = 8;
319static const int inflate_threshold_root = 15;
Robert Olsson19baf832005-06-21 12:43:18 -0700320
Robert Olsson2373ce12005-08-25 13:01:29 -0700321
322static void __alias_free_mem(struct rcu_head *head)
323{
324 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
325 kmem_cache_free(fn_alias_kmem, fa);
326}
327
328static inline void alias_free_mem_rcu(struct fib_alias *fa)
329{
330 call_rcu(&fa->rcu, __alias_free_mem);
331}
332
333static void __leaf_free_rcu(struct rcu_head *head)
334{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800335 struct leaf *l = container_of(head, struct leaf, rcu);
336 kmem_cache_free(trie_leaf_kmem, l);
Robert Olsson2373ce12005-08-25 13:01:29 -0700337}
338
Stephen Hemminger387a5482008-04-10 03:47:34 -0700339static inline void free_leaf(struct leaf *l)
340{
341 call_rcu_bh(&l->rcu, __leaf_free_rcu);
342}
343
Robert Olsson2373ce12005-08-25 13:01:29 -0700344static void __leaf_info_free_rcu(struct rcu_head *head)
345{
346 kfree(container_of(head, struct leaf_info, rcu));
347}
348
349static inline void free_leaf_info(struct leaf_info *leaf)
350{
351 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
352}
353
Eric Dumazet8d965442008-01-13 22:31:44 -0800354static struct tnode *tnode_alloc(size_t size)
Robert Olsson2373ce12005-08-25 13:01:29 -0700355{
Robert Olsson2373ce12005-08-25 13:01:29 -0700356 if (size <= PAGE_SIZE)
Eric Dumazet8d965442008-01-13 22:31:44 -0800357 return kzalloc(size, GFP_KERNEL);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700358 else
359 return __vmalloc(size, GFP_KERNEL | __GFP_ZERO, PAGE_KERNEL);
360}
Robert Olsson2373ce12005-08-25 13:01:29 -0700361
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700362static void __tnode_vfree(struct work_struct *arg)
363{
364 struct tnode *tn = container_of(arg, struct tnode, work);
365 vfree(tn);
Robert Olsson2373ce12005-08-25 13:01:29 -0700366}
367
368static void __tnode_free_rcu(struct rcu_head *head)
369{
370 struct tnode *tn = container_of(head, struct tnode, rcu);
Eric Dumazet8d965442008-01-13 22:31:44 -0800371 size_t size = sizeof(struct tnode) +
372 (sizeof(struct node *) << tn->bits);
Robert Olsson2373ce12005-08-25 13:01:29 -0700373
374 if (size <= PAGE_SIZE)
375 kfree(tn);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700376 else {
377 INIT_WORK(&tn->work, __tnode_vfree);
378 schedule_work(&tn->work);
379 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700380}
381
382static inline void tnode_free(struct tnode *tn)
383{
Stephen Hemminger387a5482008-04-10 03:47:34 -0700384 if (IS_LEAF(tn))
385 free_leaf((struct leaf *) tn);
386 else
Robert Olsson550e29b2006-04-04 12:53:35 -0700387 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700388}
389
Robert Olsson19baf832005-06-21 12:43:18 -0700390static struct leaf *leaf_new(void)
391{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800392 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700393 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700394 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700395 INIT_HLIST_HEAD(&l->list);
396 }
397 return l;
398}
399
400static struct leaf_info *leaf_info_new(int plen)
401{
402 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700403 if (li) {
404 li->plen = plen;
405 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700406 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700407 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700408}
409
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800410static struct tnode *tnode_new(t_key key, int pos, int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700411{
Eric Dumazet8d965442008-01-13 22:31:44 -0800412 size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700413 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700414
Olof Johansson91b9a272005-08-09 20:24:39 -0700415 if (tn) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700416 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700417 tn->pos = pos;
418 tn->bits = bits;
419 tn->key = key;
420 tn->full_children = 0;
421 tn->empty_children = 1<<bits;
422 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700423
Eric Dumazet8d965442008-01-13 22:31:44 -0800424 pr_debug("AT %p s=%u %lu\n", tn, (unsigned int) sizeof(struct tnode),
425 (unsigned long) (sizeof(struct node) << bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700426 return tn;
427}
428
Robert Olsson19baf832005-06-21 12:43:18 -0700429/*
430 * Check whether a tnode 'n' is "full", i.e. it is an internal node
431 * and no bits are skipped. See discussion in dyntree paper p. 6
432 */
433
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700434static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700435{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700436 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700437 return 0;
438
439 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
440}
441
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800442static inline void put_child(struct trie *t, struct tnode *tn, int i,
443 struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700444{
445 tnode_put_child_reorg(tn, i, n, -1);
446}
447
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700448 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700449 * Add a child at position i overwriting the old value.
450 * Update the value of full_children and empty_children.
451 */
452
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800453static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
454 int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700455{
Robert Olsson2373ce12005-08-25 13:01:29 -0700456 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700457 int isfull;
458
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700459 BUG_ON(i >= 1<<tn->bits);
460
Robert Olsson19baf832005-06-21 12:43:18 -0700461 /* update emptyChildren */
462 if (n == NULL && chi != NULL)
463 tn->empty_children++;
464 else if (n != NULL && chi == NULL)
465 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700466
Robert Olsson19baf832005-06-21 12:43:18 -0700467 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700468 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700469 wasfull = tnode_full(tn, chi);
470
471 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700472 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700473 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700474 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700475 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700476
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700477 if (n)
Stephen Hemminger06801912007-08-10 15:22:13 -0700478 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700479
Robert Olsson2373ce12005-08-25 13:01:29 -0700480 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700481}
482
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700483static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700484{
485 int i;
Robert Olsson2f368952005-07-05 15:02:40 -0700486 int err = 0;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700487 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700488 int inflate_threshold_use;
489 int halve_threshold_use;
Robert Olsson05eee482007-03-19 16:27:37 -0700490 int max_resize;
Robert Olsson19baf832005-06-21 12:43:18 -0700491
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900492 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700493 return NULL;
494
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700495 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
496 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700497
498 /* No children */
499 if (tn->empty_children == tnode_child_length(tn)) {
500 tnode_free(tn);
501 return NULL;
502 }
503 /* One child */
504 if (tn->empty_children == tnode_child_length(tn) - 1)
505 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700506 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700507
Olof Johansson91b9a272005-08-09 20:24:39 -0700508 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700509 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700510 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700511
512 /* compress one level */
Stephen Hemminger06801912007-08-10 15:22:13 -0700513 node_set_parent(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700514 tnode_free(tn);
515 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700516 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700517 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700518 * Double as long as the resulting node has a number of
519 * nonempty nodes that are above the threshold.
520 */
521
522 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700523 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
524 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700525 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700526 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700527 * children in the *doubled* node is at least 'high'."
528 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700529 * 'high' in this instance is the variable 'inflate_threshold'. It
530 * is expressed as a percentage, so we multiply it with
531 * tnode_child_length() and instead of multiplying by 2 (since the
532 * child array will be doubled by inflate()) and multiplying
533 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700534 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700535 *
536 * The left-hand side may look a bit weird: tnode_child_length(tn)
537 * - tn->empty_children is of course the number of non-null children
538 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700539 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700540 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700541 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700542 *
Robert Olsson19baf832005-06-21 12:43:18 -0700543 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700544 *
Robert Olsson19baf832005-06-21 12:43:18 -0700545 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700546 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700547 * tn->full_children;
548 *
549 * new_child_length = tnode_child_length(tn) * 2;
550 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700551 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700552 * new_child_length;
553 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700554 *
555 * ...and so on, tho it would mess up the while () loop.
556 *
Robert Olsson19baf832005-06-21 12:43:18 -0700557 * anyway,
558 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
559 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700560 *
Robert Olsson19baf832005-06-21 12:43:18 -0700561 * avoid a division:
562 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
563 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700564 *
Robert Olsson19baf832005-06-21 12:43:18 -0700565 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700566 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700567 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700568 *
Robert Olsson19baf832005-06-21 12:43:18 -0700569 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700570 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700571 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700572 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700573 *
Robert Olsson19baf832005-06-21 12:43:18 -0700574 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700575 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700576 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700577 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700578 *
Robert Olsson19baf832005-06-21 12:43:18 -0700579 */
580
581 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700582
Robert Olssone6308be2005-10-04 13:01:58 -0700583 /* Keep root node larger */
584
Stephen Hemminger132adf52007-03-08 20:44:43 -0800585 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700586 inflate_threshold_use = inflate_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900587 else
Robert Olssone6308be2005-10-04 13:01:58 -0700588 inflate_threshold_use = inflate_threshold;
589
Robert Olsson2f368952005-07-05 15:02:40 -0700590 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700591 max_resize = 10;
592 while ((tn->full_children > 0 && max_resize-- &&
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800593 50 * (tn->full_children + tnode_child_length(tn)
594 - tn->empty_children)
595 >= inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700596
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700597 old_tn = tn;
598 tn = inflate(t, tn);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800599
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700600 if (IS_ERR(tn)) {
601 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700602#ifdef CONFIG_IP_FIB_TRIE_STATS
603 t->stats.resize_node_skipped++;
604#endif
605 break;
606 }
Robert Olsson19baf832005-06-21 12:43:18 -0700607 }
608
Robert Olsson05eee482007-03-19 16:27:37 -0700609 if (max_resize < 0) {
610 if (!tn->parent)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800611 pr_warning("Fix inflate_threshold_root."
612 " Now=%d size=%d bits\n",
613 inflate_threshold_root, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700614 else
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800615 pr_warning("Fix inflate_threshold."
616 " Now=%d size=%d bits\n",
617 inflate_threshold, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700618 }
619
Robert Olsson19baf832005-06-21 12:43:18 -0700620 check_tnode(tn);
621
622 /*
623 * Halve as long as the number of empty children in this
624 * node is above threshold.
625 */
Robert Olsson2f368952005-07-05 15:02:40 -0700626
Robert Olssone6308be2005-10-04 13:01:58 -0700627
628 /* Keep root node larger */
629
Stephen Hemminger132adf52007-03-08 20:44:43 -0800630 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700631 halve_threshold_use = halve_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900632 else
Robert Olssone6308be2005-10-04 13:01:58 -0700633 halve_threshold_use = halve_threshold;
634
Robert Olsson2f368952005-07-05 15:02:40 -0700635 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700636 max_resize = 10;
637 while (tn->bits > 1 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700638 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700639 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700640
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700641 old_tn = tn;
642 tn = halve(t, tn);
643 if (IS_ERR(tn)) {
644 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700645#ifdef CONFIG_IP_FIB_TRIE_STATS
646 t->stats.resize_node_skipped++;
647#endif
648 break;
649 }
650 }
651
Robert Olsson05eee482007-03-19 16:27:37 -0700652 if (max_resize < 0) {
653 if (!tn->parent)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800654 pr_warning("Fix halve_threshold_root."
655 " Now=%d size=%d bits\n",
656 halve_threshold_root, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700657 else
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800658 pr_warning("Fix halve_threshold."
659 " Now=%d size=%d bits\n",
660 halve_threshold, tn->bits);
Robert Olsson05eee482007-03-19 16:27:37 -0700661 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700662
Robert Olsson19baf832005-06-21 12:43:18 -0700663 /* Only one child remains */
Robert Olsson19baf832005-06-21 12:43:18 -0700664 if (tn->empty_children == tnode_child_length(tn) - 1)
665 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);
Olof Johansson91b9a272005-08-09 20:24:39 -0700675 tnode_free(tn);
676 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700677 }
678
679 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
761 tnode_free(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
806 tnode_free(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700807 }
808 tnode_free(oldtnode);
809 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 }
890 tnode_free(oldtnode);
891 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
988static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
989{
Robert Olsson19baf832005-06-21 12:43:18 -0700990 int wasfull;
Stephen Hemminger06801912007-08-10 15:22:13 -0700991 t_key cindex, key = tn->key;
992 struct tnode *tp;
Robert Olsson19baf832005-06-21 12:43:18 -0700993
Stephen Hemminger06801912007-08-10 15:22:13 -0700994 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700995 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
996 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800997 tn = (struct tnode *) resize(t, (struct tnode *)tn);
998
999 tnode_put_child_reorg((struct tnode *)tp, cindex,
1000 (struct node *)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -07001001
Stephen Hemminger06801912007-08-10 15:22:13 -07001002 tp = node_parent((struct node *) tn);
1003 if (!tp)
Robert Olsson19baf832005-06-21 12:43:18 -07001004 break;
Stephen Hemminger06801912007-08-10 15:22:13 -07001005 tn = tp;
Robert Olsson19baf832005-06-21 12:43:18 -07001006 }
Stephen Hemminger06801912007-08-10 15:22:13 -07001007
Robert Olsson19baf832005-06-21 12:43:18 -07001008 /* Handle last (top) tnode */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001009 if (IS_TNODE(tn))
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001010 tn = (struct tnode *)resize(t, (struct tnode *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001011
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001012 return (struct node *)tn;
Robert Olsson19baf832005-06-21 12:43:18 -07001013}
1014
Robert Olsson2373ce12005-08-25 13:01:29 -07001015/* only used from updater-side */
1016
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001017static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -07001018{
1019 int pos, newpos;
1020 struct tnode *tp = NULL, *tn = NULL;
1021 struct node *n;
1022 struct leaf *l;
1023 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001024 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001025 struct leaf_info *li;
1026 t_key cindex;
1027
1028 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001029 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001030
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001031 /* If we point to NULL, stop. Either the tree is empty and we should
1032 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001033 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001034 * If we point to a T_TNODE, check if it matches our key. Note that
1035 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001036 * not be the parent's 'pos'+'bits'!
1037 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001038 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001039 * the index from our key, push the T_TNODE and walk the tree.
1040 *
1041 * If it doesn't, we have to replace it with a new T_TNODE.
1042 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001043 * If we point to a T_LEAF, it might or might not have the same key
1044 * as we do. If it does, just change the value, update the T_LEAF's
1045 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001046 * If it doesn't, we need to replace it with a T_TNODE.
1047 */
1048
1049 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1050 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001051
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001052 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001053
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001054 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001055 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001056 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001057 n = tnode_get_child(tn,
1058 tkey_extract_bits(key,
1059 tn->pos,
1060 tn->bits));
Robert Olsson19baf832005-06-21 12:43:18 -07001061
Stephen Hemminger06801912007-08-10 15:22:13 -07001062 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001063 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001064 break;
1065 }
1066
1067 /*
1068 * n ----> NULL, LEAF or TNODE
1069 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001070 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001071 */
1072
Olof Johansson91b9a272005-08-09 20:24:39 -07001073 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001074
1075 /* Case 1: n is a leaf. Compare prefixes */
1076
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001077 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08001078 l = (struct leaf *) n;
Robert Olsson19baf832005-06-21 12:43:18 -07001079 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001080
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001081 if (!li)
1082 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001083
1084 fa_head = &li->falh;
1085 insert_leaf_info(&l->list, li);
1086 goto done;
1087 }
Robert Olsson19baf832005-06-21 12:43:18 -07001088 l = leaf_new();
1089
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001090 if (!l)
1091 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001092
1093 l->key = key;
1094 li = leaf_info_new(plen);
1095
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001096 if (!li) {
Stephen Hemminger387a5482008-04-10 03:47:34 -07001097 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001098 return NULL;
Robert Olssonf835e472005-06-28 15:00:39 -07001099 }
Robert Olsson19baf832005-06-21 12:43:18 -07001100
1101 fa_head = &li->falh;
1102 insert_leaf_info(&l->list, li);
1103
Robert Olsson19baf832005-06-21 12:43:18 -07001104 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001105 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001106
Stephen Hemminger06801912007-08-10 15:22:13 -07001107 node_set_parent((struct node *)l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001108
Olof Johansson91b9a272005-08-09 20:24:39 -07001109 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1110 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1111 } else {
1112 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001113 /*
1114 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001115 * first tnode need some special handling
1116 */
1117
1118 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001119 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001120 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001121 pos = 0;
1122
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001123 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001124 newpos = tkey_mismatch(key, pos, n->key);
1125 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001126 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001127 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001128 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001129 }
Robert Olsson19baf832005-06-21 12:43:18 -07001130
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001131 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001132 free_leaf_info(li);
Stephen Hemminger387a5482008-04-10 03:47:34 -07001133 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001134 return NULL;
Olof Johansson91b9a272005-08-09 20:24:39 -07001135 }
1136
Stephen Hemminger06801912007-08-10 15:22:13 -07001137 node_set_parent((struct node *)tn, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001138
Olof Johansson91b9a272005-08-09 20:24:39 -07001139 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001140 put_child(t, tn, missbit, (struct node *)l);
1141 put_child(t, tn, 1-missbit, n);
1142
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001143 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001144 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001145 put_child(t, (struct tnode *)tp, cindex,
1146 (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001147 } else {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001148 rcu_assign_pointer(t->trie, (struct node *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001149 tp = tn;
1150 }
1151 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001152
1153 if (tp && tp->pos + tp->bits > 32)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001154 pr_warning("fib_trie"
1155 " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1156 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001157
Robert Olsson19baf832005-06-21 12:43:18 -07001158 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001159
1160 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Robert Olssonf835e472005-06-28 15:00:39 -07001161done:
Robert Olsson19baf832005-06-21 12:43:18 -07001162 return fa_head;
1163}
1164
Robert Olssond562f1f2007-03-26 14:22:22 -07001165/*
1166 * Caller must hold RTNL.
1167 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001168static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001169{
1170 struct trie *t = (struct trie *) tb->tb_data;
1171 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001172 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001173 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001174 int plen = cfg->fc_dst_len;
1175 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001176 u32 key, mask;
1177 int err;
1178 struct leaf *l;
1179
1180 if (plen > 32)
1181 return -EINVAL;
1182
Thomas Graf4e902c52006-08-17 18:14:52 -07001183 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001184
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001185 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001186
Olof Johansson91b9a272005-08-09 20:24:39 -07001187 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001188
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001189 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001190 return -EINVAL;
1191
1192 key = key & mask;
1193
Thomas Graf4e902c52006-08-17 18:14:52 -07001194 fi = fib_create_info(cfg);
1195 if (IS_ERR(fi)) {
1196 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001197 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001198 }
Robert Olsson19baf832005-06-21 12:43:18 -07001199
1200 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001201 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001202
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001203 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001204 fa_head = get_fa_head(l, plen);
1205 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1206 }
1207
1208 /* Now fa, if non-NULL, points to the first fib alias
1209 * with the same keys [prefix,tos,priority], if such key already
1210 * exists or to the node before which we will insert new one.
1211 *
1212 * If fa is NULL, we will need to allocate a new one and
1213 * insert to the head of f.
1214 *
1215 * If f is NULL, no fib node matched the destination key
1216 * and we need to allocate a new one of those as well.
1217 */
1218
Julian Anastasov936f6f82008-01-28 21:18:06 -08001219 if (fa && fa->fa_tos == tos &&
1220 fa->fa_info->fib_priority == fi->fib_priority) {
1221 struct fib_alias *fa_first, *fa_match;
Robert Olsson19baf832005-06-21 12:43:18 -07001222
1223 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001224 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001225 goto out;
1226
Julian Anastasov936f6f82008-01-28 21:18:06 -08001227 /* We have 2 goals:
1228 * 1. Find exact match for type, scope, fib_info to avoid
1229 * duplicate routes
1230 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1231 */
1232 fa_match = NULL;
1233 fa_first = fa;
1234 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1235 list_for_each_entry_continue(fa, fa_head, fa_list) {
1236 if (fa->fa_tos != tos)
1237 break;
1238 if (fa->fa_info->fib_priority != fi->fib_priority)
1239 break;
1240 if (fa->fa_type == cfg->fc_type &&
1241 fa->fa_scope == cfg->fc_scope &&
1242 fa->fa_info == fi) {
1243 fa_match = fa;
1244 break;
1245 }
1246 }
1247
Thomas Graf4e902c52006-08-17 18:14:52 -07001248 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001249 struct fib_info *fi_drop;
1250 u8 state;
1251
Julian Anastasov936f6f82008-01-28 21:18:06 -08001252 fa = fa_first;
1253 if (fa_match) {
1254 if (fa == fa_match)
1255 err = 0;
Joonwoo Park67250332008-01-18 03:45:18 -08001256 goto out;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001257 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001258 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001259 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001260 if (new_fa == NULL)
1261 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001262
1263 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001264 new_fa->fa_tos = fa->fa_tos;
1265 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001266 new_fa->fa_type = cfg->fc_type;
1267 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001268 state = fa->fa_state;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001269 new_fa->fa_state = state & ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001270
Robert Olsson2373ce12005-08-25 13:01:29 -07001271 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1272 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001273
1274 fib_release_info(fi_drop);
1275 if (state & FA_S_ACCESSED)
Olof Johansson91b9a272005-08-09 20:24:39 -07001276 rt_cache_flush(-1);
Milan Kocianb8f55832007-05-23 14:55:06 -07001277 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1278 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001279
Olof Johansson91b9a272005-08-09 20:24:39 -07001280 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001281 }
1282 /* Error if we find a perfect match which
1283 * uses the same scope, type, and nexthop
1284 * information.
1285 */
Julian Anastasov936f6f82008-01-28 21:18:06 -08001286 if (fa_match)
1287 goto out;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001288
Thomas Graf4e902c52006-08-17 18:14:52 -07001289 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001290 fa = fa_first;
Robert Olsson19baf832005-06-21 12:43:18 -07001291 }
1292 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001293 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001294 goto out;
1295
1296 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001297 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001298 if (new_fa == NULL)
1299 goto out;
1300
1301 new_fa->fa_info = fi;
1302 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001303 new_fa->fa_type = cfg->fc_type;
1304 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001305 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001306 /*
1307 * Insert new entry to the list.
1308 */
1309
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001310 if (!fa_head) {
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001311 fa_head = fib_insert_node(t, key, plen);
1312 if (unlikely(!fa_head)) {
1313 err = -ENOMEM;
Robert Olssonf835e472005-06-28 15:00:39 -07001314 goto out_free_new_fa;
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001315 }
Robert Olssonf835e472005-06-28 15:00:39 -07001316 }
Robert Olsson19baf832005-06-21 12:43:18 -07001317
Robert Olsson2373ce12005-08-25 13:01:29 -07001318 list_add_tail_rcu(&new_fa->fa_list,
1319 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001320
1321 rt_cache_flush(-1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001322 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001323 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001324succeeded:
1325 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001326
1327out_free_new_fa:
1328 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001329out:
1330 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001331err:
Robert Olsson19baf832005-06-21 12:43:18 -07001332 return err;
1333}
1334
Robert Olsson772cb712005-09-19 15:31:18 -07001335/* should be called with rcu_read_lock */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001336static int check_leaf(struct trie *t, struct leaf *l,
1337 t_key key, const struct flowi *flp,
1338 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001339{
Robert Olsson19baf832005-06-21 12:43:18 -07001340 struct leaf_info *li;
1341 struct hlist_head *hhead = &l->list;
1342 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001343
Robert Olsson2373ce12005-08-25 13:01:29 -07001344 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001345 int err;
1346 int plen = li->plen;
1347 __be32 mask = inet_make_mask(plen);
1348
Al Viro888454c2006-09-19 13:42:46 -07001349 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001350 continue;
1351
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001352 err = fib_semantic_match(&li->falh, flp, res,
1353 htonl(l->key), mask, plen);
1354
Robert Olsson19baf832005-06-21 12:43:18 -07001355#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001356 if (err <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001357 t->stats.semantic_match_passed++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001358 else
1359 t->stats.semantic_match_miss++;
Robert Olsson19baf832005-06-21 12:43:18 -07001360#endif
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001361 if (err <= 0)
1362 return plen;
Robert Olsson19baf832005-06-21 12:43:18 -07001363 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001364
1365 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001366}
1367
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001368static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
1369 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001370{
1371 struct trie *t = (struct trie *) tb->tb_data;
1372 int plen, ret = 0;
1373 struct node *n;
1374 struct tnode *pn;
1375 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001376 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001377 int chopped_off;
1378 t_key cindex = 0;
1379 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001380 struct tnode *cn;
1381 t_key node_prefix, key_prefix, pref_mismatch;
1382 int mp;
1383
Robert Olsson2373ce12005-08-25 13:01:29 -07001384 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001385
Robert Olsson2373ce12005-08-25 13:01:29 -07001386 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001387 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001388 goto failed;
1389
1390#ifdef CONFIG_IP_FIB_TRIE_STATS
1391 t->stats.gets++;
1392#endif
1393
1394 /* Just a leaf? */
1395 if (IS_LEAF(n)) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001396 plen = check_leaf(t, (struct leaf *)n, key, flp, res);
1397 if (plen < 0)
1398 goto failed;
1399 ret = 0;
1400 goto found;
Robert Olsson19baf832005-06-21 12:43:18 -07001401 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001402
Robert Olsson19baf832005-06-21 12:43:18 -07001403 pn = (struct tnode *) n;
1404 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001405
Olof Johansson91b9a272005-08-09 20:24:39 -07001406 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001407 pos = pn->pos;
1408 bits = pn->bits;
1409
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001410 if (!chopped_off)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001411 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1412 pos, bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001413
1414 n = tnode_get_child(pn, cindex);
1415
1416 if (n == NULL) {
1417#ifdef CONFIG_IP_FIB_TRIE_STATS
1418 t->stats.null_node_hit++;
1419#endif
1420 goto backtrace;
1421 }
1422
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001423 if (IS_LEAF(n)) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001424 plen = check_leaf(t, (struct leaf *)n, key, flp, res);
1425 if (plen < 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07001426 goto backtrace;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001427
1428 ret = 0;
1429 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001430 }
1431
Olof Johansson91b9a272005-08-09 20:24:39 -07001432 cn = (struct tnode *)n;
1433
1434 /*
1435 * It's a tnode, and we can do some extra checks here if we
1436 * like, to avoid descending into a dead-end branch.
1437 * This tnode is in the parent's child array at index
1438 * key[p_pos..p_pos+p_bits] but potentially with some bits
1439 * chopped off, so in reality the index may be just a
1440 * subprefix, padded with zero at the end.
1441 * We can also take a look at any skipped bits in this
1442 * tnode - everything up to p_pos is supposed to be ok,
1443 * and the non-chopped bits of the index (se previous
1444 * paragraph) are also guaranteed ok, but the rest is
1445 * considered unknown.
1446 *
1447 * The skipped bits are key[pos+bits..cn->pos].
1448 */
1449
1450 /* If current_prefix_length < pos+bits, we are already doing
1451 * actual prefix matching, which means everything from
1452 * pos+(bits-chopped_off) onward must be zero along some
1453 * branch of this subtree - otherwise there is *no* valid
1454 * prefix present. Here we can only check the skipped
1455 * bits. Remember, since we have already indexed into the
1456 * parent's child array, we know that the bits we chopped of
1457 * *are* zero.
1458 */
1459
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001460 /* NOTA BENE: Checking only skipped bits
1461 for the new node here */
Olof Johansson91b9a272005-08-09 20:24:39 -07001462
1463 if (current_prefix_length < pos+bits) {
1464 if (tkey_extract_bits(cn->key, current_prefix_length,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001465 cn->pos - current_prefix_length)
1466 || !(cn->child[0]))
Olof Johansson91b9a272005-08-09 20:24:39 -07001467 goto backtrace;
1468 }
1469
1470 /*
1471 * If chopped_off=0, the index is fully validated and we
1472 * only need to look at the skipped bits for this, the new,
1473 * tnode. What we actually want to do is to find out if
1474 * these skipped bits match our key perfectly, or if we will
1475 * have to count on finding a matching prefix further down,
1476 * because if we do, we would like to have some way of
1477 * verifying the existence of such a prefix at this point.
1478 */
1479
1480 /* The only thing we can do at this point is to verify that
1481 * any such matching prefix can indeed be a prefix to our
1482 * key, and if the bits in the node we are inspecting that
1483 * do not match our key are not ZERO, this cannot be true.
1484 * Thus, find out where there is a mismatch (before cn->pos)
1485 * and verify that all the mismatching bits are zero in the
1486 * new tnode's key.
1487 */
1488
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001489 /*
1490 * Note: We aren't very concerned about the piece of
1491 * the key that precede pn->pos+pn->bits, since these
1492 * have already been checked. The bits after cn->pos
1493 * aren't checked since these are by definition
1494 * "unknown" at this point. Thus, what we want to see
1495 * is if we are about to enter the "prefix matching"
1496 * state, and in that case verify that the skipped
1497 * bits that will prevail throughout this subtree are
1498 * zero, as they have to be if we are to find a
1499 * matching prefix.
Olof Johansson91b9a272005-08-09 20:24:39 -07001500 */
1501
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001502 node_prefix = mask_pfx(cn->key, cn->pos);
1503 key_prefix = mask_pfx(key, cn->pos);
Olof Johansson91b9a272005-08-09 20:24:39 -07001504 pref_mismatch = key_prefix^node_prefix;
1505 mp = 0;
1506
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001507 /*
1508 * In short: If skipped bits in this node do not match
1509 * the search key, enter the "prefix matching"
1510 * state.directly.
Olof Johansson91b9a272005-08-09 20:24:39 -07001511 */
1512 if (pref_mismatch) {
1513 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1514 mp++;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001515 pref_mismatch = pref_mismatch << 1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001516 }
1517 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1518
1519 if (key_prefix != 0)
1520 goto backtrace;
1521
1522 if (current_prefix_length >= cn->pos)
1523 current_prefix_length = mp;
1524 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001525
Olof Johansson91b9a272005-08-09 20:24:39 -07001526 pn = (struct tnode *)n; /* Descend */
1527 chopped_off = 0;
1528 continue;
1529
Robert Olsson19baf832005-06-21 12:43:18 -07001530backtrace:
1531 chopped_off++;
1532
1533 /* As zero don't change the child key (cindex) */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001534 while ((chopped_off <= pn->bits)
1535 && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001536 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001537
1538 /* Decrease current_... with bits chopped off */
1539 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001540 current_prefix_length = pn->pos + pn->bits
1541 - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001542
Robert Olsson19baf832005-06-21 12:43:18 -07001543 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001544 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001545 * chopped off all bits in this tnode walk up to our parent.
1546 */
1547
Olof Johansson91b9a272005-08-09 20:24:39 -07001548 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001549 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001550 } else {
Stephen Hemminger06801912007-08-10 15:22:13 -07001551 struct tnode *parent = node_parent((struct node *) pn);
1552 if (!parent)
Robert Olsson19baf832005-06-21 12:43:18 -07001553 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001554
Robert Olsson19baf832005-06-21 12:43:18 -07001555 /* Get Child's index */
Stephen Hemminger06801912007-08-10 15:22:13 -07001556 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1557 pn = parent;
Robert Olsson19baf832005-06-21 12:43:18 -07001558 chopped_off = 0;
1559
1560#ifdef CONFIG_IP_FIB_TRIE_STATS
1561 t->stats.backtrack++;
1562#endif
1563 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001564 }
Robert Olsson19baf832005-06-21 12:43:18 -07001565 }
1566failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001567 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001568found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001569 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001570 return ret;
1571}
1572
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001573/*
1574 * Remove the leaf and return parent.
1575 */
1576static void trie_leaf_remove(struct trie *t, struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001577{
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001578 struct tnode *tp = node_parent((struct node *) l);
Robert Olsson19baf832005-06-21 12:43:18 -07001579
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001580 pr_debug("entering trie_leaf_remove(%p)\n", l);
Robert Olsson19baf832005-06-21 12:43:18 -07001581
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001582 if (tp) {
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001583 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001584 put_child(t, (struct tnode *)tp, cindex, NULL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001585 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Olof Johansson91b9a272005-08-09 20:24:39 -07001586 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001587 rcu_assign_pointer(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001588
Stephen Hemminger387a5482008-04-10 03:47:34 -07001589 free_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001590}
1591
Robert Olssond562f1f2007-03-26 14:22:22 -07001592/*
1593 * Caller must hold RTNL.
1594 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001595static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001596{
1597 struct trie *t = (struct trie *) tb->tb_data;
1598 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001599 int plen = cfg->fc_dst_len;
1600 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001601 struct fib_alias *fa, *fa_to_delete;
1602 struct list_head *fa_head;
1603 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001604 struct leaf_info *li;
1605
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001606 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001607 return -EINVAL;
1608
Thomas Graf4e902c52006-08-17 18:14:52 -07001609 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001610 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001611
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001612 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001613 return -EINVAL;
1614
1615 key = key & mask;
1616 l = fib_find_node(t, key);
1617
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001618 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001619 return -ESRCH;
1620
1621 fa_head = get_fa_head(l, plen);
1622 fa = fib_find_alias(fa_head, tos, 0);
1623
1624 if (!fa)
1625 return -ESRCH;
1626
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001627 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001628
1629 fa_to_delete = NULL;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001630 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1631 list_for_each_entry_continue(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001632 struct fib_info *fi = fa->fa_info;
1633
1634 if (fa->fa_tos != tos)
1635 break;
1636
Thomas Graf4e902c52006-08-17 18:14:52 -07001637 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1638 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1639 fa->fa_scope == cfg->fc_scope) &&
1640 (!cfg->fc_protocol ||
1641 fi->fib_protocol == cfg->fc_protocol) &&
1642 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001643 fa_to_delete = fa;
1644 break;
1645 }
1646 }
1647
Olof Johansson91b9a272005-08-09 20:24:39 -07001648 if (!fa_to_delete)
1649 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001650
Olof Johansson91b9a272005-08-09 20:24:39 -07001651 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001652 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001653 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001654
Olof Johansson91b9a272005-08-09 20:24:39 -07001655 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001656 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001657
Robert Olsson2373ce12005-08-25 13:01:29 -07001658 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001659
Olof Johansson91b9a272005-08-09 20:24:39 -07001660 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001661 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001662 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001663 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001664
1665 if (hlist_empty(&l->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001666 trie_leaf_remove(t, l);
Olof Johansson91b9a272005-08-09 20:24:39 -07001667
1668 if (fa->fa_state & FA_S_ACCESSED)
1669 rt_cache_flush(-1);
1670
Robert Olsson2373ce12005-08-25 13:01:29 -07001671 fib_release_info(fa->fa_info);
1672 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001673 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001674}
1675
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001676static int trie_flush_list(struct list_head *head)
Robert Olsson19baf832005-06-21 12:43:18 -07001677{
1678 struct fib_alias *fa, *fa_node;
1679 int found = 0;
1680
1681 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1682 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001683
Robert Olsson2373ce12005-08-25 13:01:29 -07001684 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1685 list_del_rcu(&fa->fa_list);
1686 fib_release_info(fa->fa_info);
1687 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001688 found++;
1689 }
1690 }
1691 return found;
1692}
1693
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001694static int trie_flush_leaf(struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001695{
1696 int found = 0;
1697 struct hlist_head *lih = &l->list;
1698 struct hlist_node *node, *tmp;
1699 struct leaf_info *li = NULL;
1700
1701 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001702 found += trie_flush_list(&li->falh);
Robert Olsson19baf832005-06-21 12:43:18 -07001703
1704 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001705 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001706 free_leaf_info(li);
1707 }
1708 }
1709 return found;
1710}
1711
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001712/*
1713 * Scan for the next right leaf starting at node p->child[idx]
1714 * Since we have back pointer, no recursion necessary.
1715 */
1716static struct leaf *leaf_walk_rcu(struct tnode *p, struct node *c)
Robert Olsson19baf832005-06-21 12:43:18 -07001717{
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001718 do {
1719 t_key idx;
Robert Olsson19baf832005-06-21 12:43:18 -07001720
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001721 if (c)
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001722 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001723 else
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001724 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001725
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001726 while (idx < 1u << p->bits) {
1727 c = tnode_get_child_rcu(p, idx++);
Robert Olsson2373ce12005-08-25 13:01:29 -07001728 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001729 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001730
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001731 if (IS_LEAF(c)) {
1732 prefetch(p->child[idx]);
1733 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001734 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001735
1736 /* Rescan start scanning in new node */
1737 p = (struct tnode *) c;
1738 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001739 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001740
1741 /* Node empty, walk back up to parent */
Olof Johansson91b9a272005-08-09 20:24:39 -07001742 c = (struct node *) p;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001743 } while ( (p = node_parent_rcu(c)) != NULL);
1744
1745 return NULL; /* Root of trie */
1746}
1747
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001748static struct leaf *trie_firstleaf(struct trie *t)
1749{
1750 struct tnode *n = (struct tnode *) rcu_dereference(t->trie);
1751
1752 if (!n)
1753 return NULL;
1754
1755 if (IS_LEAF(n)) /* trie is just a leaf */
1756 return (struct leaf *) n;
1757
1758 return leaf_walk_rcu(n, NULL);
1759}
1760
1761static struct leaf *trie_nextleaf(struct leaf *l)
1762{
1763 struct node *c = (struct node *) l;
1764 struct tnode *p = node_parent(c);
1765
1766 if (!p)
1767 return NULL; /* trie with just one leaf */
1768
1769 return leaf_walk_rcu(p, c);
Robert Olsson19baf832005-06-21 12:43:18 -07001770}
1771
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001772static struct leaf *trie_leafindex(struct trie *t, int index)
1773{
1774 struct leaf *l = trie_firstleaf(t);
1775
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001776 while (l && index-- > 0)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001777 l = trie_nextleaf(l);
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001778
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001779 return l;
1780}
1781
1782
Robert Olssond562f1f2007-03-26 14:22:22 -07001783/*
1784 * Caller must hold RTNL.
1785 */
Robert Olsson19baf832005-06-21 12:43:18 -07001786static int fn_trie_flush(struct fib_table *tb)
1787{
1788 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001789 struct leaf *l, *ll = NULL;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001790 int found = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001791
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001792 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001793 found += trie_flush_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001794
1795 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001796 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001797 ll = l;
1798 }
1799
1800 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001801 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001802
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001803 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001804 return found;
1805}
1806
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001807static void fn_trie_select_default(struct fib_table *tb,
1808 const struct flowi *flp,
1809 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001810{
1811 struct trie *t = (struct trie *) tb->tb_data;
1812 int order, last_idx;
1813 struct fib_info *fi = NULL;
1814 struct fib_info *last_resort;
1815 struct fib_alias *fa = NULL;
1816 struct list_head *fa_head;
1817 struct leaf *l;
1818
1819 last_idx = -1;
1820 last_resort = NULL;
1821 order = -1;
1822
Robert Olsson2373ce12005-08-25 13:01:29 -07001823 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001824
Robert Olsson19baf832005-06-21 12:43:18 -07001825 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001826 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001827 goto out;
1828
1829 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001830 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001831 goto out;
1832
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001833 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001834 goto out;
1835
Robert Olsson2373ce12005-08-25 13:01:29 -07001836 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001837 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001838
Robert Olsson19baf832005-06-21 12:43:18 -07001839 if (fa->fa_scope != res->scope ||
1840 fa->fa_type != RTN_UNICAST)
1841 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001842
Robert Olsson19baf832005-06-21 12:43:18 -07001843 if (next_fi->fib_priority > res->fi->fib_priority)
1844 break;
1845 if (!next_fi->fib_nh[0].nh_gw ||
1846 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1847 continue;
1848 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001849
Robert Olsson19baf832005-06-21 12:43:18 -07001850 if (fi == NULL) {
1851 if (next_fi != res->fi)
1852 break;
1853 } else if (!fib_detect_death(fi, order, &last_resort,
Denis V. Lunev971b8932007-12-08 00:32:23 -08001854 &last_idx, tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001855 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001856 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001857 goto out;
1858 }
1859 fi = next_fi;
1860 order++;
1861 }
1862 if (order <= 0 || fi == NULL) {
Denis V. Lunev971b8932007-12-08 00:32:23 -08001863 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001864 goto out;
1865 }
1866
Denis V. Lunev971b8932007-12-08 00:32:23 -08001867 if (!fib_detect_death(fi, order, &last_resort, &last_idx,
1868 tb->tb_default)) {
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001869 fib_result_assign(res, fi);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001870 tb->tb_default = order;
Robert Olsson19baf832005-06-21 12:43:18 -07001871 goto out;
1872 }
Denis V. Luneva2bbe682007-12-08 00:31:44 -08001873 if (last_idx >= 0)
1874 fib_result_assign(res, last_resort);
Denis V. Lunev971b8932007-12-08 00:32:23 -08001875 tb->tb_default = last_idx;
1876out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001877 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001878}
1879
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001880static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1881 struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001882 struct sk_buff *skb, struct netlink_callback *cb)
1883{
1884 int i, s_i;
1885 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07001886 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001887
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001888 s_i = cb->args[5];
Robert Olsson19baf832005-06-21 12:43:18 -07001889 i = 0;
1890
Robert Olsson2373ce12005-08-25 13:01:29 -07001891 /* rcu_read_lock is hold by caller */
1892
1893 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001894 if (i < s_i) {
1895 i++;
1896 continue;
1897 }
Robert Olsson19baf832005-06-21 12:43:18 -07001898
1899 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1900 cb->nlh->nlmsg_seq,
1901 RTM_NEWROUTE,
1902 tb->tb_id,
1903 fa->fa_type,
1904 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001905 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001906 plen,
1907 fa->fa_tos,
Stephen Hemminger64347f72008-01-22 21:55:01 -08001908 fa->fa_info, NLM_F_MULTI) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001909 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001910 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001911 }
Robert Olsson19baf832005-06-21 12:43:18 -07001912 i++;
1913 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001914 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001915 return skb->len;
1916}
1917
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001918static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1919 struct sk_buff *skb, struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001920{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001921 struct leaf_info *li;
1922 struct hlist_node *node;
1923 int i, s_i;
Robert Olsson19baf832005-06-21 12:43:18 -07001924
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001925 s_i = cb->args[4];
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001926 i = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001927
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001928 /* rcu_read_lock is hold by caller */
1929 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1930 if (i < s_i) {
1931 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001932 continue;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001933 }
Robert Olsson19baf832005-06-21 12:43:18 -07001934
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001935 if (i > s_i)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001936 cb->args[5] = 0;
Olof Johansson91b9a272005-08-09 20:24:39 -07001937
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001938 if (list_empty(&li->falh))
Robert Olsson19baf832005-06-21 12:43:18 -07001939 continue;
1940
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001941 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001942 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001943 return -1;
1944 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001945 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001946 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001947
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001948 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001949 return skb->len;
1950}
1951
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001952static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
1953 struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001954{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001955 struct leaf *l;
Robert Olsson19baf832005-06-21 12:43:18 -07001956 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001957 t_key key = cb->args[2];
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001958 int count = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001959
Robert Olsson2373ce12005-08-25 13:01:29 -07001960 rcu_read_lock();
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001961 /* Dump starting at last key.
1962 * Note: 0.0.0.0/0 (ie default) is first key.
1963 */
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001964 if (count == 0)
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001965 l = trie_firstleaf(t);
1966 else {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001967 /* Normally, continue from last key, but if that is missing
1968 * fallback to using slow rescan
1969 */
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001970 l = fib_find_node(t, key);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001971 if (!l)
1972 l = trie_leafindex(t, count);
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001973 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001974
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001975 while (l) {
1976 cb->args[2] = l->key;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001977 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001978 cb->args[3] = count;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001979 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001980 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001981 }
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001982
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001983 ++count;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001984 l = trie_nextleaf(l);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001985 memset(&cb->args[4], 0,
1986 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001987 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001988 cb->args[3] = count;
Robert Olsson2373ce12005-08-25 13:01:29 -07001989 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001990
Robert Olsson19baf832005-06-21 12:43:18 -07001991 return skb->len;
Robert Olsson19baf832005-06-21 12:43:18 -07001992}
1993
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001994void __init fib_hash_init(void)
1995{
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001996 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1997 sizeof(struct fib_alias),
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08001998 0, SLAB_PANIC, NULL);
1999
2000 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
2001 max(sizeof(struct leaf),
2002 sizeof(struct leaf_info)),
2003 0, SLAB_PANIC, NULL);
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08002004}
Robert Olsson19baf832005-06-21 12:43:18 -07002005
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08002006
2007/* Fix more generic FIB names for init later */
2008struct fib_table *fib_hash_table(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07002009{
2010 struct fib_table *tb;
2011 struct trie *t;
2012
Robert Olsson19baf832005-06-21 12:43:18 -07002013 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2014 GFP_KERNEL);
2015 if (tb == NULL)
2016 return NULL;
2017
2018 tb->tb_id = id;
Denis V. Lunev971b8932007-12-08 00:32:23 -08002019 tb->tb_default = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07002020 tb->tb_lookup = fn_trie_lookup;
2021 tb->tb_insert = fn_trie_insert;
2022 tb->tb_delete = fn_trie_delete;
2023 tb->tb_flush = fn_trie_flush;
2024 tb->tb_select_default = fn_trie_select_default;
2025 tb->tb_dump = fn_trie_dump;
Robert Olsson19baf832005-06-21 12:43:18 -07002026
2027 t = (struct trie *) tb->tb_data;
Stephen Hemmingerc28a1cf2008-01-12 20:49:13 -08002028 memset(t, 0, sizeof(*t));
Robert Olsson19baf832005-06-21 12:43:18 -07002029
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002030 if (id == RT_TABLE_LOCAL)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002031 pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07002032
2033 return tb;
2034}
2035
Robert Olsson19baf832005-06-21 12:43:18 -07002036#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002037/* Depth first Trie walk iterator */
2038struct fib_trie_iter {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002039 struct seq_net_private p;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002040 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002041 struct tnode *tnode;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002042 unsigned index;
2043 unsigned depth;
2044};
Robert Olsson19baf832005-06-21 12:43:18 -07002045
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002046static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002047{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002048 struct tnode *tn = iter->tnode;
2049 unsigned cindex = iter->index;
2050 struct tnode *p;
2051
Eric W. Biederman6640e692007-01-24 14:42:04 -08002052 /* A single entry routing table */
2053 if (!tn)
2054 return NULL;
2055
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002056 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2057 iter->tnode, iter->index, iter->depth);
2058rescan:
2059 while (cindex < (1<<tn->bits)) {
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002060 struct node *n = tnode_get_child_rcu(tn, cindex);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002061
2062 if (n) {
2063 if (IS_LEAF(n)) {
2064 iter->tnode = tn;
2065 iter->index = cindex + 1;
2066 } else {
2067 /* push down one level */
2068 iter->tnode = (struct tnode *) n;
2069 iter->index = 0;
2070 ++iter->depth;
2071 }
2072 return n;
2073 }
2074
2075 ++cindex;
2076 }
2077
2078 /* Current node exhausted, pop back up */
Eric Dumazetb59cfbf2008-01-18 03:31:36 -08002079 p = node_parent_rcu((struct node *)tn);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002080 if (p) {
2081 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2082 tn = p;
2083 --iter->depth;
2084 goto rescan;
2085 }
2086
2087 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002088 return NULL;
2089}
2090
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002091static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2092 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002093{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002094 struct node *n;
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002095
Stephen Hemminger132adf52007-03-08 20:44:43 -08002096 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002097 return NULL;
2098
2099 n = rcu_dereference(t->trie);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002100 if (!n)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002101 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002102
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002103 if (IS_TNODE(n)) {
2104 iter->tnode = (struct tnode *) n;
2105 iter->index = 0;
2106 iter->depth = 1;
2107 } else {
2108 iter->tnode = NULL;
2109 iter->index = 0;
2110 iter->depth = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002111 }
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002112
2113 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002114}
2115
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002116static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002117{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002118 struct node *n;
2119 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002120
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002121 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002122
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002123 rcu_read_lock();
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002124 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002125 if (IS_LEAF(n)) {
Stephen Hemminger93672292008-01-22 21:54:05 -08002126 struct leaf *l = (struct leaf *)n;
2127 struct leaf_info *li;
2128 struct hlist_node *tmp;
2129
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002130 s->leaves++;
2131 s->totdepth += iter.depth;
2132 if (iter.depth > s->maxdepth)
2133 s->maxdepth = iter.depth;
Stephen Hemminger93672292008-01-22 21:54:05 -08002134
2135 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2136 ++s->prefixes;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002137 } else {
2138 const struct tnode *tn = (const struct tnode *) n;
2139 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002140
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002141 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002142 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002143 s->nodesizes[tn->bits]++;
2144
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002145 for (i = 0; i < (1<<tn->bits); i++)
2146 if (!tn->child[i])
2147 s->nullpointers++;
2148 }
2149 }
2150 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002151}
2152
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002153/*
Robert Olsson19baf832005-06-21 12:43:18 -07002154 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002155 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002156static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002157{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002158 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002159
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002160 if (stat->leaves)
2161 avdepth = stat->totdepth*100 / stat->leaves;
2162 else
2163 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002164
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002165 seq_printf(seq, "\tAver depth: %u.%02d\n",
2166 avdepth / 100, avdepth % 100);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002167 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002168
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002169 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002170 bytes = sizeof(struct leaf) * stat->leaves;
Stephen Hemminger93672292008-01-22 21:54:05 -08002171
2172 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2173 bytes += sizeof(struct leaf_info) * stat->prefixes;
2174
Stephen Hemminger187b5182008-01-12 20:55:55 -08002175 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002176 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002177
Robert Olsson06ef9212006-03-20 21:35:01 -08002178 max = MAX_STAT_DEPTH;
2179 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002180 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002181
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002182 pointers = 0;
2183 for (i = 1; i <= max; i++)
2184 if (stat->nodesizes[i] != 0) {
Stephen Hemminger187b5182008-01-12 20:55:55 -08002185 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002186 pointers += (1<<i) * stat->nodesizes[i];
2187 }
2188 seq_putc(seq, '\n');
Stephen Hemminger187b5182008-01-12 20:55:55 -08002189 seq_printf(seq, "\tPointers: %u\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002190
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002191 bytes += sizeof(struct node *) * pointers;
Stephen Hemminger187b5182008-01-12 20:55:55 -08002192 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2193 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002194}
Robert Olsson19baf832005-06-21 12:43:18 -07002195
2196#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002197static void trie_show_usage(struct seq_file *seq,
2198 const struct trie_use_stats *stats)
2199{
2200 seq_printf(seq, "\nCounters:\n---------\n");
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002201 seq_printf(seq, "gets = %u\n", stats->gets);
2202 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2203 seq_printf(seq, "semantic match passed = %u\n",
2204 stats->semantic_match_passed);
2205 seq_printf(seq, "semantic match miss = %u\n",
2206 stats->semantic_match_miss);
2207 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2208 seq_printf(seq, "skipped node resize = %u\n\n",
2209 stats->resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002210}
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002211#endif /* CONFIG_IP_FIB_TRIE_STATS */
2212
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002213static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002214{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002215 if (tb->tb_id == RT_TABLE_LOCAL)
2216 seq_puts(seq, "Local:\n");
2217 else if (tb->tb_id == RT_TABLE_MAIN)
2218 seq_puts(seq, "Main:\n");
2219 else
2220 seq_printf(seq, "Id %d:\n", tb->tb_id);
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002221}
Robert Olsson19baf832005-06-21 12:43:18 -07002222
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002223
Robert Olsson19baf832005-06-21 12:43:18 -07002224static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2225{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002226 struct net *net = (struct net *)seq->private;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002227 unsigned int h;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002228
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002229 seq_printf(seq,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002230 "Basic info: size of leaf:"
2231 " %Zd bytes, size of tnode: %Zd bytes.\n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002232 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002233
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002234 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2235 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2236 struct hlist_node *node;
2237 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002238
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002239 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2240 struct trie *t = (struct trie *) tb->tb_data;
2241 struct trie_stat stat;
2242
2243 if (!t)
2244 continue;
2245
2246 fib_table_print(seq, tb);
2247
2248 trie_collect_stats(t, &stat);
2249 trie_show_stats(seq, &stat);
2250#ifdef CONFIG_IP_FIB_TRIE_STATS
2251 trie_show_usage(seq, &t->stats);
2252#endif
2253 }
2254 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002255
Robert Olsson19baf832005-06-21 12:43:18 -07002256 return 0;
2257}
2258
Robert Olsson19baf832005-06-21 12:43:18 -07002259static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2260{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002261 int err;
2262 struct net *net;
2263
2264 net = get_proc_net(inode);
2265 if (net == NULL)
2266 return -ENXIO;
2267 err = single_open(file, fib_triestat_seq_show, net);
2268 if (err < 0) {
2269 put_net(net);
2270 return err;
2271 }
2272 return 0;
2273}
2274
2275static int fib_triestat_seq_release(struct inode *ino, struct file *f)
2276{
2277 struct seq_file *seq = f->private_data;
2278 put_net(seq->private);
2279 return single_release(ino, f);
Robert Olsson19baf832005-06-21 12:43:18 -07002280}
2281
Arjan van de Ven9a321442007-02-12 00:55:35 -08002282static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002283 .owner = THIS_MODULE,
2284 .open = fib_triestat_seq_open,
2285 .read = seq_read,
2286 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002287 .release = fib_triestat_seq_release,
Robert Olsson19baf832005-06-21 12:43:18 -07002288};
2289
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002290static struct node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002291{
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002292 struct fib_trie_iter *iter = seq->private;
2293 struct net *net = seq_file_net(seq);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002294 loff_t idx = 0;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002295 unsigned int h;
Robert Olsson19baf832005-06-21 12:43:18 -07002296
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002297 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2298 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2299 struct hlist_node *node;
2300 struct fib_table *tb;
2301
2302 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2303 struct node *n;
2304
2305 for (n = fib_trie_get_first(iter,
2306 (struct trie *) tb->tb_data);
2307 n; n = fib_trie_get_next(iter))
2308 if (pos == idx++) {
2309 iter->tb = tb;
2310 return n;
2311 }
2312 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002313 }
Robert Olsson19baf832005-06-21 12:43:18 -07002314
Robert Olsson19baf832005-06-21 12:43:18 -07002315 return NULL;
2316}
2317
2318static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002319 __acquires(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002320{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002321 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002322 return fib_trie_get_idx(seq, *pos);
Robert Olsson19baf832005-06-21 12:43:18 -07002323}
2324
2325static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2326{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002327 struct fib_trie_iter *iter = seq->private;
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002328 struct net *net = seq_file_net(seq);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002329 struct fib_table *tb = iter->tb;
2330 struct hlist_node *tb_node;
2331 unsigned int h;
2332 struct node *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002333
Robert Olsson19baf832005-06-21 12:43:18 -07002334 ++*pos;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002335 /* next node in same table */
2336 n = fib_trie_get_next(iter);
2337 if (n)
2338 return n;
Olof Johansson91b9a272005-08-09 20:24:39 -07002339
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002340 /* walk rest of this hash chain */
2341 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2342 while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) {
2343 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2344 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2345 if (n)
2346 goto found;
2347 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002348
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002349 /* new hash chain */
2350 while (++h < FIB_TABLE_HASHSZ) {
2351 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2352 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2353 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2354 if (n)
2355 goto found;
2356 }
2357 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002358 return NULL;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002359
2360found:
2361 iter->tb = tb;
2362 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002363}
2364
2365static void fib_trie_seq_stop(struct seq_file *seq, void *v)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002366 __releases(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002367{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002368 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002369}
2370
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002371static void seq_indent(struct seq_file *seq, int n)
2372{
2373 while (n-- > 0) seq_puts(seq, " ");
2374}
Robert Olsson19baf832005-06-21 12:43:18 -07002375
Eric Dumazet28d36e32008-01-14 23:09:56 -08002376static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002377{
Stephen Hemminger132adf52007-03-08 20:44:43 -08002378 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002379 case RT_SCOPE_UNIVERSE: return "universe";
2380 case RT_SCOPE_SITE: return "site";
2381 case RT_SCOPE_LINK: return "link";
2382 case RT_SCOPE_HOST: return "host";
2383 case RT_SCOPE_NOWHERE: return "nowhere";
2384 default:
Eric Dumazet28d36e32008-01-14 23:09:56 -08002385 snprintf(buf, len, "scope=%d", s);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002386 return buf;
2387 }
2388}
2389
2390static const char *rtn_type_names[__RTN_MAX] = {
2391 [RTN_UNSPEC] = "UNSPEC",
2392 [RTN_UNICAST] = "UNICAST",
2393 [RTN_LOCAL] = "LOCAL",
2394 [RTN_BROADCAST] = "BROADCAST",
2395 [RTN_ANYCAST] = "ANYCAST",
2396 [RTN_MULTICAST] = "MULTICAST",
2397 [RTN_BLACKHOLE] = "BLACKHOLE",
2398 [RTN_UNREACHABLE] = "UNREACHABLE",
2399 [RTN_PROHIBIT] = "PROHIBIT",
2400 [RTN_THROW] = "THROW",
2401 [RTN_NAT] = "NAT",
2402 [RTN_XRESOLVE] = "XRESOLVE",
2403};
2404
Eric Dumazet28d36e32008-01-14 23:09:56 -08002405static inline const char *rtn_type(char *buf, size_t len, unsigned t)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002406{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002407 if (t < __RTN_MAX && rtn_type_names[t])
2408 return rtn_type_names[t];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002409 snprintf(buf, len, "type %u", t);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002410 return buf;
2411}
2412
2413/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002414static int fib_trie_seq_show(struct seq_file *seq, void *v)
2415{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002416 const struct fib_trie_iter *iter = seq->private;
2417 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002418
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002419 if (!node_parent_rcu(n))
2420 fib_table_print(seq, iter->tb);
Robert Olsson095b8502007-01-26 19:06:01 -08002421
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002422 if (IS_TNODE(n)) {
2423 struct tnode *tn = (struct tnode *) n;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07002424 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002425
Robert Olsson1d25cd62005-09-19 15:29:52 -07002426 seq_indent(seq, iter->depth-1);
YOSHIFUJI Hideakia7d632b2008-04-14 04:09:00 -07002427 seq_printf(seq, " +-- " NIPQUAD_FMT "/%d %d %d %d\n",
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002428 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002429 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002430
Olof Johansson91b9a272005-08-09 20:24:39 -07002431 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002432 struct leaf *l = (struct leaf *) n;
Stephen Hemminger13280422008-01-22 21:54:37 -08002433 struct leaf_info *li;
2434 struct hlist_node *node;
Al Viro32ab5f82006-09-26 22:21:45 -07002435 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002436
2437 seq_indent(seq, iter->depth);
YOSHIFUJI Hideakia7d632b2008-04-14 04:09:00 -07002438 seq_printf(seq, " |-- " NIPQUAD_FMT "\n", NIPQUAD(val));
Eric Dumazet28d36e32008-01-14 23:09:56 -08002439
Stephen Hemminger13280422008-01-22 21:54:37 -08002440 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2441 struct fib_alias *fa;
Eric Dumazet28d36e32008-01-14 23:09:56 -08002442
Stephen Hemminger13280422008-01-22 21:54:37 -08002443 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2444 char buf1[32], buf2[32];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002445
Stephen Hemminger13280422008-01-22 21:54:37 -08002446 seq_indent(seq, iter->depth+1);
2447 seq_printf(seq, " /%d %s %s", li->plen,
2448 rtn_scope(buf1, sizeof(buf1),
2449 fa->fa_scope),
2450 rtn_type(buf2, sizeof(buf2),
2451 fa->fa_type));
2452 if (fa->fa_tos)
Denis V. Lunevb9c4d822008-02-05 02:58:45 -08002453 seq_printf(seq, " tos=%d", fa->fa_tos);
Stephen Hemminger13280422008-01-22 21:54:37 -08002454 seq_putc(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002455 }
2456 }
Robert Olsson19baf832005-06-21 12:43:18 -07002457 }
2458
2459 return 0;
2460}
2461
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002462static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002463 .start = fib_trie_seq_start,
2464 .next = fib_trie_seq_next,
2465 .stop = fib_trie_seq_stop,
2466 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002467};
2468
2469static int fib_trie_seq_open(struct inode *inode, struct file *file)
2470{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002471 return seq_open_net(inode, file, &fib_trie_seq_ops,
2472 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002473}
2474
Arjan van de Ven9a321442007-02-12 00:55:35 -08002475static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002476 .owner = THIS_MODULE,
2477 .open = fib_trie_seq_open,
2478 .read = seq_read,
2479 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002480 .release = seq_release_net,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002481};
2482
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002483struct fib_route_iter {
2484 struct seq_net_private p;
2485 struct trie *main_trie;
2486 loff_t pos;
2487 t_key key;
2488};
2489
2490static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2491{
2492 struct leaf *l = NULL;
2493 struct trie *t = iter->main_trie;
2494
2495 /* use cache location of last found key */
2496 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2497 pos -= iter->pos;
2498 else {
2499 iter->pos = 0;
2500 l = trie_firstleaf(t);
2501 }
2502
2503 while (l && pos-- > 0) {
2504 iter->pos++;
2505 l = trie_nextleaf(l);
2506 }
2507
2508 if (l)
2509 iter->key = pos; /* remember it */
2510 else
2511 iter->pos = 0; /* forget it */
2512
2513 return l;
2514}
2515
2516static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2517 __acquires(RCU)
2518{
2519 struct fib_route_iter *iter = seq->private;
2520 struct fib_table *tb;
2521
2522 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002523 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002524 if (!tb)
2525 return NULL;
2526
2527 iter->main_trie = (struct trie *) tb->tb_data;
2528 if (*pos == 0)
2529 return SEQ_START_TOKEN;
2530 else
2531 return fib_route_get_idx(iter, *pos - 1);
2532}
2533
2534static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2535{
2536 struct fib_route_iter *iter = seq->private;
2537 struct leaf *l = v;
2538
2539 ++*pos;
2540 if (v == SEQ_START_TOKEN) {
2541 iter->pos = 0;
2542 l = trie_firstleaf(iter->main_trie);
2543 } else {
2544 iter->pos++;
2545 l = trie_nextleaf(l);
2546 }
2547
2548 if (l)
2549 iter->key = l->key;
2550 else
2551 iter->pos = 0;
2552 return l;
2553}
2554
2555static void fib_route_seq_stop(struct seq_file *seq, void *v)
2556 __releases(RCU)
2557{
2558 rcu_read_unlock();
2559}
2560
Al Viro32ab5f82006-09-26 22:21:45 -07002561static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002562{
2563 static unsigned type2flags[RTN_MAX + 1] = {
2564 [7] = RTF_REJECT, [8] = RTF_REJECT,
2565 };
2566 unsigned flags = type2flags[type];
2567
2568 if (fi && fi->fib_nh->nh_gw)
2569 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002570 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002571 flags |= RTF_HOST;
2572 flags |= RTF_UP;
2573 return flags;
2574}
2575
2576/*
2577 * This outputs /proc/net/route.
2578 * The format of the file is not supposed to be changed
2579 * and needs to be same as fib_hash output to avoid breaking
2580 * legacy utilities
2581 */
2582static int fib_route_seq_show(struct seq_file *seq, void *v)
2583{
2584 struct leaf *l = v;
Stephen Hemminger13280422008-01-22 21:54:37 -08002585 struct leaf_info *li;
2586 struct hlist_node *node;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002587
2588 if (v == SEQ_START_TOKEN) {
2589 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2590 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2591 "\tWindow\tIRTT");
2592 return 0;
2593 }
2594
Stephen Hemminger13280422008-01-22 21:54:37 -08002595 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002596 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002597 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002598
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002599 mask = inet_make_mask(li->plen);
2600 prefix = htonl(l->key);
2601
2602 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002603 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002604 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
Stephen Hemminger13280422008-01-22 21:54:37 -08002605 char bf[128];
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002606
2607 if (fa->fa_type == RTN_BROADCAST
2608 || fa->fa_type == RTN_MULTICAST)
2609 continue;
2610
2611 if (fi)
2612 snprintf(bf, sizeof(bf),
2613 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2614 fi->fib_dev ? fi->fib_dev->name : "*",
2615 prefix,
2616 fi->fib_nh->nh_gw, flags, 0, 0,
2617 fi->fib_priority,
2618 mask,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002619 (fi->fib_advmss ?
2620 fi->fib_advmss + 40 : 0),
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002621 fi->fib_window,
2622 fi->fib_rtt >> 3);
2623 else
2624 snprintf(bf, sizeof(bf),
2625 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2626 prefix, 0, flags, 0, 0, 0,
2627 mask, 0, 0, 0);
2628
2629 seq_printf(seq, "%-127s\n", bf);
2630 }
2631 }
2632
2633 return 0;
2634}
2635
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002636static const struct seq_operations fib_route_seq_ops = {
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002637 .start = fib_route_seq_start,
2638 .next = fib_route_seq_next,
2639 .stop = fib_route_seq_stop,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002640 .show = fib_route_seq_show,
2641};
2642
2643static int fib_route_seq_open(struct inode *inode, struct file *file)
2644{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002645 return seq_open_net(inode, file, &fib_route_seq_ops,
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002646 sizeof(struct fib_route_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002647}
2648
Arjan van de Ven9a321442007-02-12 00:55:35 -08002649static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002650 .owner = THIS_MODULE,
2651 .open = fib_route_seq_open,
2652 .read = seq_read,
2653 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002654 .release = seq_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002655};
2656
Denis V. Lunev61a02652008-01-10 03:21:09 -08002657int __net_init fib_proc_init(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002658{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002659 if (!proc_net_fops_create(net, "fib_trie", S_IRUGO, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002660 goto out1;
2661
Denis V. Lunev61a02652008-01-10 03:21:09 -08002662 if (!proc_net_fops_create(net, "fib_triestat", S_IRUGO,
2663 &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002664 goto out2;
2665
Denis V. Lunev61a02652008-01-10 03:21:09 -08002666 if (!proc_net_fops_create(net, "route", S_IRUGO, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002667 goto out3;
2668
Robert Olsson19baf832005-06-21 12:43:18 -07002669 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002670
2671out3:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002672 proc_net_remove(net, "fib_triestat");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002673out2:
Denis V. Lunev61a02652008-01-10 03:21:09 -08002674 proc_net_remove(net, "fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002675out1:
2676 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002677}
2678
Denis V. Lunev61a02652008-01-10 03:21:09 -08002679void __net_exit fib_proc_exit(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002680{
Denis V. Lunev61a02652008-01-10 03:21:09 -08002681 proc_net_remove(net, "fib_trie");
2682 proc_net_remove(net, "fib_triestat");
2683 proc_net_remove(net, "route");
Robert Olsson19baf832005-06-21 12:43:18 -07002684}
2685
2686#endif /* CONFIG_PROC_FS */