blob: 9be7da7c3a8fa8ed474031e2375aa53586d81f12 [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>
57#include <asm/bitops.h>
58#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>
76#include <net/ip.h>
77#include <net/protocol.h>
78#include <net/route.h>
79#include <net/tcp.h>
80#include <net/sock.h>
81#include <net/ip_fib.h>
82#include "fib_lookup.h"
83
84#undef CONFIG_IP_FIB_TRIE_STATS
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))
88#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
89#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
90
Robert Olsson19baf832005-06-21 12:43:18 -070091typedef unsigned int t_key;
92
93#define T_TNODE 0
94#define T_LEAF 1
95#define NODE_TYPE_MASK 0x1UL
Olof Johansson91b9a272005-08-09 20:24:39 -070096#define NODE_PARENT(node) \
Robert Olsson2373ce12005-08-25 13:01:29 -070097 ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
98
99#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
100
101#define NODE_SET_PARENT(node, ptr) \
102 rcu_assign_pointer((node)->parent, \
103 ((unsigned long)(ptr)) | NODE_TYPE(node))
Robert Olsson19baf832005-06-21 12:43:18 -0700104
Olof Johansson91b9a272005-08-09 20:24:39 -0700105#define IS_TNODE(n) (!(n->parent & T_LEAF))
106#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -0700107
108struct node {
Olof Johansson91b9a272005-08-09 20:24:39 -0700109 t_key key;
110 unsigned long parent;
Robert Olsson19baf832005-06-21 12:43:18 -0700111};
112
113struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700114 t_key key;
115 unsigned long parent;
Robert Olsson19baf832005-06-21 12:43:18 -0700116 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700117 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700118};
119
120struct leaf_info {
121 struct hlist_node hlist;
Robert Olsson2373ce12005-08-25 13:01:29 -0700122 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700123 int plen;
124 struct list_head falh;
125};
126
127struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700128 t_key key;
129 unsigned long parent;
130 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
131 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
132 unsigned short full_children; /* KEYLENGTH bits needed */
133 unsigned short empty_children; /* KEYLENGTH bits needed */
Robert Olsson2373ce12005-08-25 13:01:29 -0700134 struct rcu_head rcu;
Olof Johansson91b9a272005-08-09 20:24:39 -0700135 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700136};
137
138#ifdef CONFIG_IP_FIB_TRIE_STATS
139struct trie_use_stats {
140 unsigned int gets;
141 unsigned int backtrack;
142 unsigned int semantic_match_passed;
143 unsigned int semantic_match_miss;
144 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700145 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700146};
147#endif
148
149struct trie_stat {
150 unsigned int totdepth;
151 unsigned int maxdepth;
152 unsigned int tnodes;
153 unsigned int leaves;
154 unsigned int nullpointers;
Robert Olsson06ef9212006-03-20 21:35:01 -0800155 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700156};
Robert Olsson19baf832005-06-21 12:43:18 -0700157
158struct trie {
Olof Johansson91b9a272005-08-09 20:24:39 -0700159 struct node *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700160#ifdef CONFIG_IP_FIB_TRIE_STATS
161 struct trie_use_stats stats;
162#endif
Olof Johansson91b9a272005-08-09 20:24:39 -0700163 int size;
Robert Olsson19baf832005-06-21 12:43:18 -0700164 unsigned int revision;
165};
166
Robert Olsson19baf832005-06-21 12:43:18 -0700167static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
168static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700169static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700170static struct tnode *inflate(struct trie *t, struct tnode *tn);
171static struct tnode *halve(struct trie *t, struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700172static void tnode_free(struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700173
Christoph Lametere18b8902006-12-06 20:33:20 -0800174static struct kmem_cache *fn_alias_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700175static struct trie *trie_local = NULL, *trie_main = NULL;
176
Robert Olsson2373ce12005-08-25 13:01:29 -0700177
178/* rcu_read_lock needs to be hold by caller from readside */
179
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700180static inline struct node *tnode_get_child(struct tnode *tn, int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700181{
Olof Johansson91b9a272005-08-09 20:24:39 -0700182 BUG_ON(i >= 1 << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700183
Robert Olsson2373ce12005-08-25 13:01:29 -0700184 return rcu_dereference(tn->child[i]);
Robert Olsson19baf832005-06-21 12:43:18 -0700185}
186
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700187static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700188{
Olof Johansson91b9a272005-08-09 20:24:39 -0700189 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700190}
191
Robert Olsson19baf832005-06-21 12:43:18 -0700192static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
193{
Olof Johansson91b9a272005-08-09 20:24:39 -0700194 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700195 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700196 else
Robert Olsson19baf832005-06-21 12:43:18 -0700197 return 0;
198}
199
200static inline int tkey_equals(t_key a, t_key b)
201{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700202 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700203}
204
205static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
206{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700207 if (bits == 0 || offset >= KEYLENGTH)
208 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700209 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
210 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700211}
Robert Olsson19baf832005-06-21 12:43:18 -0700212
213static inline int tkey_mismatch(t_key a, int offset, t_key b)
214{
215 t_key diff = a ^ b;
216 int i = offset;
217
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700218 if (!diff)
219 return 0;
220 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700221 i++;
222 return i;
223}
224
Robert Olsson19baf832005-06-21 12:43:18 -0700225/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900226 To understand this stuff, an understanding of keys and all their bits is
227 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700228 all of the bits in that key are significant.
229
230 Consider a node 'n' and its parent 'tp'.
231
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900232 If n is a leaf, every bit in its key is significant. Its presence is
233 necessitated by path compression, since during a tree traversal (when
234 searching for a leaf - unless we are doing an insertion) we will completely
235 ignore all skipped bits we encounter. Thus we need to verify, at the end of
236 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700237 correct key path.
238
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900239 Note that we can never "miss" the correct key in the tree if present by
240 following the wrong path. Path compression ensures that segments of the key
241 that are the same for all keys with a given prefix are skipped, but the
242 skipped part *is* identical for each node in the subtrie below the skipped
243 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700244 call to tkey_sub_equals() in trie_insert().
245
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900246 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700247 have many different meanings.
248
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900249 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700250 _________________________________________________________________
251 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
252 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900253 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700254
255 _________________________________________________________________
256 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
257 -----------------------------------------------------------------
258 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
259
260 tp->pos = 7
261 tp->bits = 3
262 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700263 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700264
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900265 First, let's just ignore the bits that come before the parent tp, that is
266 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700267 not use them for anything.
268
269 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900270 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700271 'n' among tp's children.
272
273 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
274 for the node n.
275
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900276 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700277 of the bits are really not needed or indeed known in n->key.
278
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900279 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700280 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900281
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700282
Robert Olsson19baf832005-06-21 12:43:18 -0700283 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
284 at this point.
285
286*/
287
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700288static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700289{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700290 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700291}
292
293static int halve_threshold = 25;
294static int inflate_threshold = 50;
Robert Olsson965ffea2007-03-19 16:29:58 -0700295static int halve_threshold_root = 8;
296static int inflate_threshold_root = 15;
Robert Olsson19baf832005-06-21 12:43:18 -0700297
Robert Olsson2373ce12005-08-25 13:01:29 -0700298
299static void __alias_free_mem(struct rcu_head *head)
300{
301 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
302 kmem_cache_free(fn_alias_kmem, fa);
303}
304
305static inline void alias_free_mem_rcu(struct fib_alias *fa)
306{
307 call_rcu(&fa->rcu, __alias_free_mem);
308}
309
310static void __leaf_free_rcu(struct rcu_head *head)
311{
312 kfree(container_of(head, struct leaf, rcu));
313}
314
Robert Olsson2373ce12005-08-25 13:01:29 -0700315static void __leaf_info_free_rcu(struct rcu_head *head)
316{
317 kfree(container_of(head, struct leaf_info, rcu));
318}
319
320static inline void free_leaf_info(struct leaf_info *leaf)
321{
322 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
323}
324
325static struct tnode *tnode_alloc(unsigned int size)
326{
327 struct page *pages;
328
329 if (size <= PAGE_SIZE)
330 return kcalloc(size, 1, GFP_KERNEL);
331
332 pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
333 if (!pages)
334 return NULL;
335
336 return page_address(pages);
337}
338
339static void __tnode_free_rcu(struct rcu_head *head)
340{
341 struct tnode *tn = container_of(head, struct tnode, rcu);
342 unsigned int size = sizeof(struct tnode) +
343 (1 << tn->bits) * sizeof(struct node *);
344
345 if (size <= PAGE_SIZE)
346 kfree(tn);
347 else
348 free_pages((unsigned long)tn, get_order(size));
349}
350
351static inline void tnode_free(struct tnode *tn)
352{
Stephen Hemminger132adf52007-03-08 20:44:43 -0800353 if (IS_LEAF(tn)) {
Robert Olsson550e29b2006-04-04 12:53:35 -0700354 struct leaf *l = (struct leaf *) tn;
355 call_rcu_bh(&l->rcu, __leaf_free_rcu);
Stephen Hemminger132adf52007-03-08 20:44:43 -0800356 } else
Robert Olsson550e29b2006-04-04 12:53:35 -0700357 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700358}
359
Robert Olsson19baf832005-06-21 12:43:18 -0700360static struct leaf *leaf_new(void)
361{
362 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700363 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700364 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700365 INIT_HLIST_HEAD(&l->list);
366 }
367 return l;
368}
369
370static struct leaf_info *leaf_info_new(int plen)
371{
372 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700373 if (li) {
374 li->plen = plen;
375 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700376 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700377 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700378}
379
Robert Olsson19baf832005-06-21 12:43:18 -0700380static struct tnode* tnode_new(t_key key, int pos, int bits)
381{
382 int nchildren = 1<<bits;
383 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700384 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700385
Olof Johansson91b9a272005-08-09 20:24:39 -0700386 if (tn) {
Robert Olsson19baf832005-06-21 12:43:18 -0700387 memset(tn, 0, sz);
Robert Olsson2373ce12005-08-25 13:01:29 -0700388 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700389 tn->pos = pos;
390 tn->bits = bits;
391 tn->key = key;
392 tn->full_children = 0;
393 tn->empty_children = 1<<bits;
394 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700395
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700396 pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
397 (unsigned int) (sizeof(struct node) * 1<<bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700398 return tn;
399}
400
Robert Olsson19baf832005-06-21 12:43:18 -0700401/*
402 * Check whether a tnode 'n' is "full", i.e. it is an internal node
403 * and no bits are skipped. See discussion in dyntree paper p. 6
404 */
405
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700406static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700407{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700408 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700409 return 0;
410
411 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
412}
413
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700414static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700415{
416 tnode_put_child_reorg(tn, i, n, -1);
417}
418
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700419 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700420 * Add a child at position i overwriting the old value.
421 * Update the value of full_children and empty_children.
422 */
423
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700424static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700425{
Robert Olsson2373ce12005-08-25 13:01:29 -0700426 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700427 int isfull;
428
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700429 BUG_ON(i >= 1<<tn->bits);
430
Robert Olsson19baf832005-06-21 12:43:18 -0700431
432 /* update emptyChildren */
433 if (n == NULL && chi != NULL)
434 tn->empty_children++;
435 else if (n != NULL && chi == NULL)
436 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700437
Robert Olsson19baf832005-06-21 12:43:18 -0700438 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700439 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700440 wasfull = tnode_full(tn, chi);
441
442 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700443 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700444 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700445 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700446 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700447
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700448 if (n)
449 NODE_SET_PARENT(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700450
Robert Olsson2373ce12005-08-25 13:01:29 -0700451 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700452}
453
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700454static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700455{
456 int i;
Robert Olsson2f368952005-07-05 15:02:40 -0700457 int err = 0;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700458 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700459 int inflate_threshold_use;
460 int halve_threshold_use;
Robert Olsson05eee482007-03-19 16:27:37 -0700461 int max_resize;
Robert Olsson19baf832005-06-21 12:43:18 -0700462
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900463 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700464 return NULL;
465
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700466 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
467 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700468
469 /* No children */
470 if (tn->empty_children == tnode_child_length(tn)) {
471 tnode_free(tn);
472 return NULL;
473 }
474 /* One child */
475 if (tn->empty_children == tnode_child_length(tn) - 1)
476 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700477 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700478
Olof Johansson91b9a272005-08-09 20:24:39 -0700479 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700480 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700481 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700482
483 /* compress one level */
Robert Olsson2373ce12005-08-25 13:01:29 -0700484 NODE_SET_PARENT(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700485 tnode_free(tn);
486 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700487 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700488 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700489 * Double as long as the resulting node has a number of
490 * nonempty nodes that are above the threshold.
491 */
492
493 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700494 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
495 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700496 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700497 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700498 * children in the *doubled* node is at least 'high'."
499 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700500 * 'high' in this instance is the variable 'inflate_threshold'. It
501 * is expressed as a percentage, so we multiply it with
502 * tnode_child_length() and instead of multiplying by 2 (since the
503 * child array will be doubled by inflate()) and multiplying
504 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700505 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700506 *
507 * The left-hand side may look a bit weird: tnode_child_length(tn)
508 * - tn->empty_children is of course the number of non-null children
509 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700510 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700511 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700512 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700513 *
Robert Olsson19baf832005-06-21 12:43:18 -0700514 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700515 *
Robert Olsson19baf832005-06-21 12:43:18 -0700516 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700517 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700518 * tn->full_children;
519 *
520 * new_child_length = tnode_child_length(tn) * 2;
521 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700522 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700523 * new_child_length;
524 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700525 *
526 * ...and so on, tho it would mess up the while () loop.
527 *
Robert Olsson19baf832005-06-21 12:43:18 -0700528 * anyway,
529 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
530 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700531 *
Robert Olsson19baf832005-06-21 12:43:18 -0700532 * avoid a division:
533 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
534 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700535 *
Robert Olsson19baf832005-06-21 12:43:18 -0700536 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700537 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700538 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700539 *
Robert Olsson19baf832005-06-21 12:43:18 -0700540 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700541 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700542 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700543 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700544 *
Robert Olsson19baf832005-06-21 12:43:18 -0700545 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700546 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700547 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700548 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700549 *
Robert Olsson19baf832005-06-21 12:43:18 -0700550 */
551
552 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700553
Robert Olssone6308be2005-10-04 13:01:58 -0700554 /* Keep root node larger */
555
Stephen Hemminger132adf52007-03-08 20:44:43 -0800556 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700557 inflate_threshold_use = inflate_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900558 else
Robert Olssone6308be2005-10-04 13:01:58 -0700559 inflate_threshold_use = inflate_threshold;
560
Robert Olsson2f368952005-07-05 15:02:40 -0700561 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700562 max_resize = 10;
563 while ((tn->full_children > 0 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700564 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
Robert Olssone6308be2005-10-04 13:01:58 -0700565 inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700566
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700567 old_tn = tn;
568 tn = inflate(t, tn);
569 if (IS_ERR(tn)) {
570 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700571#ifdef CONFIG_IP_FIB_TRIE_STATS
572 t->stats.resize_node_skipped++;
573#endif
574 break;
575 }
Robert Olsson19baf832005-06-21 12:43:18 -0700576 }
577
Robert Olsson05eee482007-03-19 16:27:37 -0700578 if (max_resize < 0) {
579 if (!tn->parent)
580 printk(KERN_WARNING "Fix inflate_threshold_root. Now=%d size=%d bits\n",
581 inflate_threshold_root, tn->bits);
582 else
583 printk(KERN_WARNING "Fix inflate_threshold. Now=%d size=%d bits\n",
584 inflate_threshold, tn->bits);
585 }
586
Robert Olsson19baf832005-06-21 12:43:18 -0700587 check_tnode(tn);
588
589 /*
590 * Halve as long as the number of empty children in this
591 * node is above threshold.
592 */
Robert Olsson2f368952005-07-05 15:02:40 -0700593
Robert Olssone6308be2005-10-04 13:01:58 -0700594
595 /* Keep root node larger */
596
Stephen Hemminger132adf52007-03-08 20:44:43 -0800597 if (!tn->parent)
Robert Olssone6308be2005-10-04 13:01:58 -0700598 halve_threshold_use = halve_threshold_root;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900599 else
Robert Olssone6308be2005-10-04 13:01:58 -0700600 halve_threshold_use = halve_threshold;
601
Robert Olsson2f368952005-07-05 15:02:40 -0700602 err = 0;
Robert Olsson05eee482007-03-19 16:27:37 -0700603 max_resize = 10;
604 while (tn->bits > 1 && max_resize-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700605 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700606 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700607
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700608 old_tn = tn;
609 tn = halve(t, tn);
610 if (IS_ERR(tn)) {
611 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700612#ifdef CONFIG_IP_FIB_TRIE_STATS
613 t->stats.resize_node_skipped++;
614#endif
615 break;
616 }
617 }
618
Robert Olsson05eee482007-03-19 16:27:37 -0700619 if (max_resize < 0) {
620 if (!tn->parent)
621 printk(KERN_WARNING "Fix halve_threshold_root. Now=%d size=%d bits\n",
622 halve_threshold_root, tn->bits);
623 else
624 printk(KERN_WARNING "Fix halve_threshold. Now=%d size=%d bits\n",
625 halve_threshold, tn->bits);
626 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700627
Robert Olsson19baf832005-06-21 12:43:18 -0700628 /* Only one child remains */
Robert Olsson19baf832005-06-21 12:43:18 -0700629 if (tn->empty_children == tnode_child_length(tn) - 1)
630 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700631 struct node *n;
632
Olof Johansson91b9a272005-08-09 20:24:39 -0700633 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700634 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700635 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700636
637 /* compress one level */
638
Robert Olsson2373ce12005-08-25 13:01:29 -0700639 NODE_SET_PARENT(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700640 tnode_free(tn);
641 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700642 }
643
644 return (struct node *) tn;
645}
646
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700647static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700648{
649 struct tnode *inode;
650 struct tnode *oldtnode = tn;
651 int olen = tnode_child_length(tn);
652 int i;
653
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700654 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700655
656 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
657
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700658 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700659 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700660
661 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700662 * Preallocate and store tnodes before the actual work so we
663 * don't get into an inconsistent state if memory allocation
664 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700665 * of tnode is ignored.
666 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700667
668 for (i = 0; i < olen; i++) {
Robert Olsson2f368952005-07-05 15:02:40 -0700669 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
670
671 if (inode &&
672 IS_TNODE(inode) &&
673 inode->pos == oldtnode->pos + oldtnode->bits &&
674 inode->bits > 1) {
675 struct tnode *left, *right;
Robert Olsson2f368952005-07-05 15:02:40 -0700676 t_key m = TKEY_GET_MASK(inode->pos, 1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700677
Robert Olsson2f368952005-07-05 15:02:40 -0700678 left = tnode_new(inode->key&(~m), inode->pos + 1,
679 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700680 if (!left)
681 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700682
Robert Olsson2f368952005-07-05 15:02:40 -0700683 right = tnode_new(inode->key|m, inode->pos + 1,
684 inode->bits - 1);
685
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900686 if (!right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700687 tnode_free(left);
688 goto nomem;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900689 }
Robert Olsson2f368952005-07-05 15:02:40 -0700690
691 put_child(t, tn, 2*i, (struct node *) left);
692 put_child(t, tn, 2*i+1, (struct node *) right);
693 }
694 }
695
Olof Johansson91b9a272005-08-09 20:24:39 -0700696 for (i = 0; i < olen; i++) {
Robert Olsson19baf832005-06-21 12:43:18 -0700697 struct node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700698 struct tnode *left, *right;
699 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700700
Robert Olsson19baf832005-06-21 12:43:18 -0700701 /* An empty child */
702 if (node == NULL)
703 continue;
704
705 /* A leaf or an internal node with skipped bits */
706
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700707 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700708 tn->pos + tn->bits - 1) {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700709 if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
Robert Olsson19baf832005-06-21 12:43:18 -0700710 1) == 0)
711 put_child(t, tn, 2*i, node);
712 else
713 put_child(t, tn, 2*i+1, node);
714 continue;
715 }
716
717 /* An internal node with two children */
718 inode = (struct tnode *) node;
719
720 if (inode->bits == 1) {
721 put_child(t, tn, 2*i, inode->child[0]);
722 put_child(t, tn, 2*i+1, inode->child[1]);
723
724 tnode_free(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700725 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700726 }
727
Olof Johansson91b9a272005-08-09 20:24:39 -0700728 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700729
Olof Johansson91b9a272005-08-09 20:24:39 -0700730 /* We will replace this node 'inode' with two new
731 * ones, 'left' and 'right', each with half of the
732 * original children. The two new nodes will have
733 * a position one bit further down the key and this
734 * means that the "significant" part of their keys
735 * (see the discussion near the top of this file)
736 * will differ by one bit, which will be "0" in
737 * left's key and "1" in right's key. Since we are
738 * moving the key position by one step, the bit that
739 * we are moving away from - the bit at position
740 * (inode->pos) - is the one that will differ between
741 * left and right. So... we synthesize that bit in the
742 * two new keys.
743 * The mask 'm' below will be a single "one" bit at
744 * the position (inode->pos)
745 */
Robert Olsson19baf832005-06-21 12:43:18 -0700746
Olof Johansson91b9a272005-08-09 20:24:39 -0700747 /* Use the old key, but set the new significant
748 * bit to zero.
749 */
Robert Olsson19baf832005-06-21 12:43:18 -0700750
Olof Johansson91b9a272005-08-09 20:24:39 -0700751 left = (struct tnode *) tnode_get_child(tn, 2*i);
752 put_child(t, tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700753
Olof Johansson91b9a272005-08-09 20:24:39 -0700754 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700755
Olof Johansson91b9a272005-08-09 20:24:39 -0700756 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
757 put_child(t, tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700758
Olof Johansson91b9a272005-08-09 20:24:39 -0700759 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700760
Olof Johansson91b9a272005-08-09 20:24:39 -0700761 size = tnode_child_length(left);
762 for (j = 0; j < size; j++) {
763 put_child(t, left, j, inode->child[j]);
764 put_child(t, right, j, inode->child[j + size]);
Robert Olsson19baf832005-06-21 12:43:18 -0700765 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700766 put_child(t, tn, 2*i, resize(t, left));
767 put_child(t, tn, 2*i+1, resize(t, right));
768
769 tnode_free(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700770 }
771 tnode_free(oldtnode);
772 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700773nomem:
774 {
775 int size = tnode_child_length(tn);
776 int j;
777
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700778 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700779 if (tn->child[j])
780 tnode_free((struct tnode *)tn->child[j]);
781
782 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700783
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700784 return ERR_PTR(-ENOMEM);
785 }
Robert Olsson19baf832005-06-21 12:43:18 -0700786}
787
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700788static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700789{
790 struct tnode *oldtnode = tn;
791 struct node *left, *right;
792 int i;
793 int olen = tnode_child_length(tn);
794
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700795 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700796
797 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700798
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700799 if (!tn)
800 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700801
802 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700803 * Preallocate and store tnodes before the actual work so we
804 * don't get into an inconsistent state if memory allocation
805 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700806 * of tnode is ignored.
807 */
808
Olof Johansson91b9a272005-08-09 20:24:39 -0700809 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700810 left = tnode_get_child(oldtnode, i);
811 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700812
Robert Olsson2f368952005-07-05 15:02:40 -0700813 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700814 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700815 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700816
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700817 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700818
819 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700820 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700821
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700822 put_child(t, tn, i/2, (struct node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700823 }
Robert Olsson2f368952005-07-05 15:02:40 -0700824
Robert Olsson2f368952005-07-05 15:02:40 -0700825 }
Robert Olsson19baf832005-06-21 12:43:18 -0700826
Olof Johansson91b9a272005-08-09 20:24:39 -0700827 for (i = 0; i < olen; i += 2) {
828 struct tnode *newBinNode;
829
Robert Olsson19baf832005-06-21 12:43:18 -0700830 left = tnode_get_child(oldtnode, i);
831 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700832
Robert Olsson19baf832005-06-21 12:43:18 -0700833 /* At least one of the children is empty */
834 if (left == NULL) {
835 if (right == NULL) /* Both are empty */
836 continue;
837 put_child(t, tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700838 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700839 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700840
841 if (right == NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700842 put_child(t, tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700843 continue;
844 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700845
Robert Olsson19baf832005-06-21 12:43:18 -0700846 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700847 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
848 put_child(t, tn, i/2, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700849 put_child(t, newBinNode, 0, left);
850 put_child(t, newBinNode, 1, right);
851 put_child(t, tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700852 }
853 tnode_free(oldtnode);
854 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700855nomem:
856 {
857 int size = tnode_child_length(tn);
858 int j;
859
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700860 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700861 if (tn->child[j])
862 tnode_free((struct tnode *)tn->child[j]);
863
864 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700865
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700866 return ERR_PTR(-ENOMEM);
867 }
Robert Olsson19baf832005-06-21 12:43:18 -0700868}
869
Olof Johansson91b9a272005-08-09 20:24:39 -0700870static void trie_init(struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -0700871{
Olof Johansson91b9a272005-08-09 20:24:39 -0700872 if (!t)
873 return;
874
875 t->size = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700876 rcu_assign_pointer(t->trie, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700877 t->revision = 0;
Robert Olsson19baf832005-06-21 12:43:18 -0700878#ifdef CONFIG_IP_FIB_TRIE_STATS
Olof Johansson91b9a272005-08-09 20:24:39 -0700879 memset(&t->stats, 0, sizeof(struct trie_use_stats));
Robert Olsson19baf832005-06-21 12:43:18 -0700880#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700881}
882
Robert Olsson772cb712005-09-19 15:31:18 -0700883/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700884 via get_fa_head and dump */
885
Robert Olsson772cb712005-09-19 15:31:18 -0700886static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700887{
Robert Olsson772cb712005-09-19 15:31:18 -0700888 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700889 struct hlist_node *node;
890 struct leaf_info *li;
891
Robert Olsson2373ce12005-08-25 13:01:29 -0700892 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700893 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700894 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700895
Robert Olsson19baf832005-06-21 12:43:18 -0700896 return NULL;
897}
898
899static inline struct list_head * get_fa_head(struct leaf *l, int plen)
900{
Robert Olsson772cb712005-09-19 15:31:18 -0700901 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700902
Olof Johansson91b9a272005-08-09 20:24:39 -0700903 if (!li)
904 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700905
Olof Johansson91b9a272005-08-09 20:24:39 -0700906 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700907}
908
909static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
910{
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900911 struct leaf_info *li = NULL, *last = NULL;
912 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700913
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900914 if (hlist_empty(head)) {
915 hlist_add_head_rcu(&new->hlist, head);
916 } else {
917 hlist_for_each_entry(li, node, head, hlist) {
918 if (new->plen > li->plen)
919 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700920
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900921 last = li;
922 }
923 if (last)
924 hlist_add_after_rcu(&last->hlist, &new->hlist);
925 else
926 hlist_add_before_rcu(&new->hlist, &li->hlist);
927 }
Robert Olsson19baf832005-06-21 12:43:18 -0700928}
929
Robert Olsson2373ce12005-08-25 13:01:29 -0700930/* rcu_read_lock needs to be hold by caller from readside */
931
Robert Olsson19baf832005-06-21 12:43:18 -0700932static struct leaf *
933fib_find_node(struct trie *t, u32 key)
934{
935 int pos;
936 struct tnode *tn;
937 struct node *n;
938
939 pos = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700940 n = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700941
942 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
943 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700944
Robert Olsson19baf832005-06-21 12:43:18 -0700945 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700946
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700947 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700948 pos = tn->pos + tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700949 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700950 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700951 break;
952 }
953 /* Case we have found a leaf. Compare prefixes */
954
Olof Johansson91b9a272005-08-09 20:24:39 -0700955 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
956 return (struct leaf *)n;
957
Robert Olsson19baf832005-06-21 12:43:18 -0700958 return NULL;
959}
960
961static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
962{
Robert Olsson19baf832005-06-21 12:43:18 -0700963 int wasfull;
964 t_key cindex, key;
965 struct tnode *tp = NULL;
966
Robert Olsson19baf832005-06-21 12:43:18 -0700967 key = tn->key;
Robert Olsson19baf832005-06-21 12:43:18 -0700968
969 while (tn != NULL && NODE_PARENT(tn) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700970
971 tp = NODE_PARENT(tn);
972 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
973 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
974 tn = (struct tnode *) resize (t, (struct tnode *)tn);
975 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -0700976
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700977 if (!NODE_PARENT(tn))
Robert Olsson19baf832005-06-21 12:43:18 -0700978 break;
979
980 tn = NODE_PARENT(tn);
981 }
982 /* Handle last (top) tnode */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700983 if (IS_TNODE(tn))
Robert Olsson19baf832005-06-21 12:43:18 -0700984 tn = (struct tnode*) resize(t, (struct tnode *)tn);
985
986 return (struct node*) tn;
987}
988
Robert Olsson2373ce12005-08-25 13:01:29 -0700989/* only used from updater-side */
990
Robert Olssonf835e472005-06-28 15:00:39 -0700991static struct list_head *
992fib_insert_node(struct trie *t, int *err, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700993{
994 int pos, newpos;
995 struct tnode *tp = NULL, *tn = NULL;
996 struct node *n;
997 struct leaf *l;
998 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700999 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001000 struct leaf_info *li;
1001 t_key cindex;
1002
1003 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001004 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001005
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001006 /* If we point to NULL, stop. Either the tree is empty and we should
1007 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001008 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001009 * If we point to a T_TNODE, check if it matches our key. Note that
1010 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001011 * not be the parent's 'pos'+'bits'!
1012 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001013 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001014 * the index from our key, push the T_TNODE and walk the tree.
1015 *
1016 * If it doesn't, we have to replace it with a new T_TNODE.
1017 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001018 * If we point to a T_LEAF, it might or might not have the same key
1019 * as we do. If it does, just change the value, update the T_LEAF's
1020 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001021 * If it doesn't, we need to replace it with a T_TNODE.
1022 */
1023
1024 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1025 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001026
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001027 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001028
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001029 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001030 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001031 pos = tn->pos + tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001032 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1033
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001034 BUG_ON(n && NODE_PARENT(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001035 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001036 break;
1037 }
1038
1039 /*
1040 * n ----> NULL, LEAF or TNODE
1041 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001042 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001043 */
1044
Olof Johansson91b9a272005-08-09 20:24:39 -07001045 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001046
1047 /* Case 1: n is a leaf. Compare prefixes */
1048
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001049 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001050 struct leaf *l = (struct leaf *) n;
1051
Robert Olsson19baf832005-06-21 12:43:18 -07001052 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001053
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001054 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001055 *err = -ENOMEM;
1056 goto err;
1057 }
Robert Olsson19baf832005-06-21 12:43:18 -07001058
1059 fa_head = &li->falh;
1060 insert_leaf_info(&l->list, li);
1061 goto done;
1062 }
1063 t->size++;
1064 l = leaf_new();
1065
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001066 if (!l) {
Robert Olssonf835e472005-06-28 15:00:39 -07001067 *err = -ENOMEM;
1068 goto err;
1069 }
Robert Olsson19baf832005-06-21 12:43:18 -07001070
1071 l->key = key;
1072 li = leaf_info_new(plen);
1073
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001074 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001075 tnode_free((struct tnode *) l);
1076 *err = -ENOMEM;
1077 goto err;
1078 }
Robert Olsson19baf832005-06-21 12:43:18 -07001079
1080 fa_head = &li->falh;
1081 insert_leaf_info(&l->list, li);
1082
Robert Olsson19baf832005-06-21 12:43:18 -07001083 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001084 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001085
1086 NODE_SET_PARENT(l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001087
Olof Johansson91b9a272005-08-09 20:24:39 -07001088 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1089 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1090 } else {
1091 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001092 /*
1093 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001094 * first tnode need some special handling
1095 */
1096
1097 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001098 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001099 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001100 pos = 0;
1101
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001102 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001103 newpos = tkey_mismatch(key, pos, n->key);
1104 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001105 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001106 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001107 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001108 }
Robert Olsson19baf832005-06-21 12:43:18 -07001109
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001110 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001111 free_leaf_info(li);
1112 tnode_free((struct tnode *) l);
1113 *err = -ENOMEM;
1114 goto err;
Olof Johansson91b9a272005-08-09 20:24:39 -07001115 }
1116
Robert Olsson19baf832005-06-21 12:43:18 -07001117 NODE_SET_PARENT(tn, tp);
1118
Olof Johansson91b9a272005-08-09 20:24:39 -07001119 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001120 put_child(t, tn, missbit, (struct node *)l);
1121 put_child(t, tn, 1-missbit, n);
1122
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001123 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001124 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1125 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001126 } else {
Robert Olsson2373ce12005-08-25 13:01:29 -07001127 rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001128 tp = tn;
1129 }
1130 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001131
1132 if (tp && tp->pos + tp->bits > 32)
Stephen Hemminger78c66712005-09-21 00:15:39 -07001133 printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
Robert Olsson19baf832005-06-21 12:43:18 -07001134 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001135
Robert Olsson19baf832005-06-21 12:43:18 -07001136 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001137
1138 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Robert Olssonf835e472005-06-28 15:00:39 -07001139done:
1140 t->revision++;
Olof Johansson91b9a272005-08-09 20:24:39 -07001141err:
Robert Olsson19baf832005-06-21 12:43:18 -07001142 return fa_head;
1143}
1144
Robert Olssond562f1f2007-03-26 14:22:22 -07001145/*
1146 * Caller must hold RTNL.
1147 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001148static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001149{
1150 struct trie *t = (struct trie *) tb->tb_data;
1151 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001152 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001153 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001154 int plen = cfg->fc_dst_len;
1155 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001156 u32 key, mask;
1157 int err;
1158 struct leaf *l;
1159
1160 if (plen > 32)
1161 return -EINVAL;
1162
Thomas Graf4e902c52006-08-17 18:14:52 -07001163 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001164
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001165 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001166
Olof Johansson91b9a272005-08-09 20:24:39 -07001167 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001168
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001169 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001170 return -EINVAL;
1171
1172 key = key & mask;
1173
Thomas Graf4e902c52006-08-17 18:14:52 -07001174 fi = fib_create_info(cfg);
1175 if (IS_ERR(fi)) {
1176 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001177 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001178 }
Robert Olsson19baf832005-06-21 12:43:18 -07001179
1180 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001181 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001182
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001183 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001184 fa_head = get_fa_head(l, plen);
1185 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1186 }
1187
1188 /* Now fa, if non-NULL, points to the first fib alias
1189 * with the same keys [prefix,tos,priority], if such key already
1190 * exists or to the node before which we will insert new one.
1191 *
1192 * If fa is NULL, we will need to allocate a new one and
1193 * insert to the head of f.
1194 *
1195 * If f is NULL, no fib node matched the destination key
1196 * and we need to allocate a new one of those as well.
1197 */
1198
Olof Johansson91b9a272005-08-09 20:24:39 -07001199 if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
Robert Olsson19baf832005-06-21 12:43:18 -07001200 struct fib_alias *fa_orig;
1201
1202 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001203 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001204 goto out;
1205
Thomas Graf4e902c52006-08-17 18:14:52 -07001206 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001207 struct fib_info *fi_drop;
1208 u8 state;
1209
Robert Olsson2373ce12005-08-25 13:01:29 -07001210 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001211 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001212 if (new_fa == NULL)
1213 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001214
1215 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001216 new_fa->fa_tos = fa->fa_tos;
1217 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001218 new_fa->fa_type = cfg->fc_type;
1219 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001220 state = fa->fa_state;
Robert Olsson2373ce12005-08-25 13:01:29 -07001221 new_fa->fa_state &= ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001222
Robert Olsson2373ce12005-08-25 13:01:29 -07001223 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1224 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001225
1226 fib_release_info(fi_drop);
1227 if (state & FA_S_ACCESSED)
Olof Johansson91b9a272005-08-09 20:24:39 -07001228 rt_cache_flush(-1);
Robert Olsson19baf832005-06-21 12:43:18 -07001229
Olof Johansson91b9a272005-08-09 20:24:39 -07001230 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001231 }
1232 /* Error if we find a perfect match which
1233 * uses the same scope, type, and nexthop
1234 * information.
1235 */
1236 fa_orig = fa;
1237 list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
1238 if (fa->fa_tos != tos)
1239 break;
1240 if (fa->fa_info->fib_priority != fi->fib_priority)
1241 break;
Thomas Graf4e902c52006-08-17 18:14:52 -07001242 if (fa->fa_type == cfg->fc_type &&
1243 fa->fa_scope == cfg->fc_scope &&
Robert Olsson19baf832005-06-21 12:43:18 -07001244 fa->fa_info == fi) {
1245 goto out;
1246 }
1247 }
Thomas Graf4e902c52006-08-17 18:14:52 -07001248 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Robert Olsson19baf832005-06-21 12:43:18 -07001249 fa = fa_orig;
1250 }
1251 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001252 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001253 goto out;
1254
1255 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001256 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001257 if (new_fa == NULL)
1258 goto out;
1259
1260 new_fa->fa_info = fi;
1261 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001262 new_fa->fa_type = cfg->fc_type;
1263 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001264 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001265 /*
1266 * Insert new entry to the list.
1267 */
1268
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001269 if (!fa_head) {
Robert Olssonf835e472005-06-28 15:00:39 -07001270 err = 0;
Herbert Xub47b2ec2006-07-12 13:29:56 -07001271 fa_head = fib_insert_node(t, &err, key, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001272 if (err)
Robert Olssonf835e472005-06-28 15:00:39 -07001273 goto out_free_new_fa;
1274 }
Robert Olsson19baf832005-06-21 12:43:18 -07001275
Robert Olsson2373ce12005-08-25 13:01:29 -07001276 list_add_tail_rcu(&new_fa->fa_list,
1277 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001278
1279 rt_cache_flush(-1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001280 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1281 &cfg->fc_nlinfo);
Robert Olsson19baf832005-06-21 12:43:18 -07001282succeeded:
1283 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001284
1285out_free_new_fa:
1286 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001287out:
1288 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001289err:
Robert Olsson19baf832005-06-21 12:43:18 -07001290 return err;
1291}
1292
Robert Olsson2373ce12005-08-25 13:01:29 -07001293
Robert Olsson772cb712005-09-19 15:31:18 -07001294/* should be called with rcu_read_lock */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001295static inline int check_leaf(struct trie *t, struct leaf *l,
1296 t_key key, int *plen, const struct flowi *flp,
Patrick McHardy06c74272005-08-23 22:06:09 -07001297 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001298{
Patrick McHardy06c74272005-08-23 22:06:09 -07001299 int err, i;
Al Viro888454c2006-09-19 13:42:46 -07001300 __be32 mask;
Robert Olsson19baf832005-06-21 12:43:18 -07001301 struct leaf_info *li;
1302 struct hlist_head *hhead = &l->list;
1303 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001304
Robert Olsson2373ce12005-08-25 13:01:29 -07001305 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001306 i = li->plen;
Al Viro888454c2006-09-19 13:42:46 -07001307 mask = inet_make_mask(i);
1308 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001309 continue;
1310
Al Viro888454c2006-09-19 13:42:46 -07001311 if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001312 *plen = i;
1313#ifdef CONFIG_IP_FIB_TRIE_STATS
1314 t->stats.semantic_match_passed++;
1315#endif
Patrick McHardy06c74272005-08-23 22:06:09 -07001316 return err;
Robert Olsson19baf832005-06-21 12:43:18 -07001317 }
1318#ifdef CONFIG_IP_FIB_TRIE_STATS
1319 t->stats.semantic_match_miss++;
1320#endif
1321 }
Patrick McHardy06c74272005-08-23 22:06:09 -07001322 return 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001323}
1324
1325static int
1326fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1327{
1328 struct trie *t = (struct trie *) tb->tb_data;
1329 int plen, ret = 0;
1330 struct node *n;
1331 struct tnode *pn;
1332 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001333 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001334 int chopped_off;
1335 t_key cindex = 0;
1336 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001337 struct tnode *cn;
1338 t_key node_prefix, key_prefix, pref_mismatch;
1339 int mp;
1340
Robert Olsson2373ce12005-08-25 13:01:29 -07001341 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001342
Robert Olsson2373ce12005-08-25 13:01:29 -07001343 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001344 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001345 goto failed;
1346
1347#ifdef CONFIG_IP_FIB_TRIE_STATS
1348 t->stats.gets++;
1349#endif
1350
1351 /* Just a leaf? */
1352 if (IS_LEAF(n)) {
Patrick McHardy06c74272005-08-23 22:06:09 -07001353 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001354 goto found;
1355 goto failed;
1356 }
1357 pn = (struct tnode *) n;
1358 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001359
Olof Johansson91b9a272005-08-09 20:24:39 -07001360 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001361 pos = pn->pos;
1362 bits = pn->bits;
1363
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001364 if (!chopped_off)
Robert Olsson19baf832005-06-21 12:43:18 -07001365 cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);
1366
1367 n = tnode_get_child(pn, cindex);
1368
1369 if (n == NULL) {
1370#ifdef CONFIG_IP_FIB_TRIE_STATS
1371 t->stats.null_node_hit++;
1372#endif
1373 goto backtrace;
1374 }
1375
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001376 if (IS_LEAF(n)) {
Patrick McHardy06c74272005-08-23 22:06:09 -07001377 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001378 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001379 else
1380 goto backtrace;
1381 }
1382
1383#define HL_OPTIMIZE
1384#ifdef HL_OPTIMIZE
1385 cn = (struct tnode *)n;
1386
1387 /*
1388 * It's a tnode, and we can do some extra checks here if we
1389 * like, to avoid descending into a dead-end branch.
1390 * This tnode is in the parent's child array at index
1391 * key[p_pos..p_pos+p_bits] but potentially with some bits
1392 * chopped off, so in reality the index may be just a
1393 * subprefix, padded with zero at the end.
1394 * We can also take a look at any skipped bits in this
1395 * tnode - everything up to p_pos is supposed to be ok,
1396 * and the non-chopped bits of the index (se previous
1397 * paragraph) are also guaranteed ok, but the rest is
1398 * considered unknown.
1399 *
1400 * The skipped bits are key[pos+bits..cn->pos].
1401 */
1402
1403 /* If current_prefix_length < pos+bits, we are already doing
1404 * actual prefix matching, which means everything from
1405 * pos+(bits-chopped_off) onward must be zero along some
1406 * branch of this subtree - otherwise there is *no* valid
1407 * prefix present. Here we can only check the skipped
1408 * bits. Remember, since we have already indexed into the
1409 * parent's child array, we know that the bits we chopped of
1410 * *are* zero.
1411 */
1412
1413 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1414
1415 if (current_prefix_length < pos+bits) {
1416 if (tkey_extract_bits(cn->key, current_prefix_length,
1417 cn->pos - current_prefix_length) != 0 ||
1418 !(cn->child[0]))
1419 goto backtrace;
1420 }
1421
1422 /*
1423 * If chopped_off=0, the index is fully validated and we
1424 * only need to look at the skipped bits for this, the new,
1425 * tnode. What we actually want to do is to find out if
1426 * these skipped bits match our key perfectly, or if we will
1427 * have to count on finding a matching prefix further down,
1428 * because if we do, we would like to have some way of
1429 * verifying the existence of such a prefix at this point.
1430 */
1431
1432 /* The only thing we can do at this point is to verify that
1433 * any such matching prefix can indeed be a prefix to our
1434 * key, and if the bits in the node we are inspecting that
1435 * do not match our key are not ZERO, this cannot be true.
1436 * Thus, find out where there is a mismatch (before cn->pos)
1437 * and verify that all the mismatching bits are zero in the
1438 * new tnode's key.
1439 */
1440
1441 /* Note: We aren't very concerned about the piece of the key
1442 * that precede pn->pos+pn->bits, since these have already been
1443 * checked. The bits after cn->pos aren't checked since these are
1444 * by definition "unknown" at this point. Thus, what we want to
1445 * see is if we are about to enter the "prefix matching" state,
1446 * and in that case verify that the skipped bits that will prevail
1447 * throughout this subtree are zero, as they have to be if we are
1448 * to find a matching prefix.
1449 */
1450
1451 node_prefix = MASK_PFX(cn->key, cn->pos);
1452 key_prefix = MASK_PFX(key, cn->pos);
1453 pref_mismatch = key_prefix^node_prefix;
1454 mp = 0;
1455
1456 /* In short: If skipped bits in this node do not match the search
1457 * key, enter the "prefix matching" state.directly.
1458 */
1459 if (pref_mismatch) {
1460 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1461 mp++;
1462 pref_mismatch = pref_mismatch <<1;
1463 }
1464 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1465
1466 if (key_prefix != 0)
1467 goto backtrace;
1468
1469 if (current_prefix_length >= cn->pos)
1470 current_prefix_length = mp;
1471 }
1472#endif
1473 pn = (struct tnode *)n; /* Descend */
1474 chopped_off = 0;
1475 continue;
1476
Robert Olsson19baf832005-06-21 12:43:18 -07001477backtrace:
1478 chopped_off++;
1479
1480 /* As zero don't change the child key (cindex) */
Olof Johansson91b9a272005-08-09 20:24:39 -07001481 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001482 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001483
1484 /* Decrease current_... with bits chopped off */
1485 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1486 current_prefix_length = pn->pos + pn->bits - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001487
Robert Olsson19baf832005-06-21 12:43:18 -07001488 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001489 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001490 * chopped off all bits in this tnode walk up to our parent.
1491 */
1492
Olof Johansson91b9a272005-08-09 20:24:39 -07001493 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001494 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001495 } else {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001496 if (NODE_PARENT(pn) == NULL)
Robert Olsson19baf832005-06-21 12:43:18 -07001497 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001498
Robert Olsson19baf832005-06-21 12:43:18 -07001499 /* Get Child's index */
1500 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
1501 pn = NODE_PARENT(pn);
1502 chopped_off = 0;
1503
1504#ifdef CONFIG_IP_FIB_TRIE_STATS
1505 t->stats.backtrack++;
1506#endif
1507 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001508 }
Robert Olsson19baf832005-06-21 12:43:18 -07001509 }
1510failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001511 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001512found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001513 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001514 return ret;
1515}
1516
Robert Olsson2373ce12005-08-25 13:01:29 -07001517/* only called from updater side */
Robert Olsson19baf832005-06-21 12:43:18 -07001518static int trie_leaf_remove(struct trie *t, t_key key)
1519{
1520 t_key cindex;
1521 struct tnode *tp = NULL;
1522 struct node *n = t->trie;
1523 struct leaf *l;
1524
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001525 pr_debug("entering trie_leaf_remove(%p)\n", n);
Robert Olsson19baf832005-06-21 12:43:18 -07001526
1527 /* Note that in the case skipped bits, those bits are *not* checked!
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001528 * When we finish this, we will have NULL or a T_LEAF, and the
Robert Olsson19baf832005-06-21 12:43:18 -07001529 * T_LEAF may or may not match our key.
1530 */
1531
Olof Johansson91b9a272005-08-09 20:24:39 -07001532 while (n != NULL && IS_TNODE(n)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001533 struct tnode *tn = (struct tnode *) n;
1534 check_tnode(tn);
1535 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1536
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001537 BUG_ON(n && NODE_PARENT(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001538 }
Robert Olsson19baf832005-06-21 12:43:18 -07001539 l = (struct leaf *) n;
1540
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001541 if (!n || !tkey_equals(l->key, key))
Robert Olsson19baf832005-06-21 12:43:18 -07001542 return 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001543
1544 /*
1545 * Key found.
1546 * Remove the leaf and rebalance the tree
Robert Olsson19baf832005-06-21 12:43:18 -07001547 */
1548
1549 t->revision++;
1550 t->size--;
1551
1552 tp = NODE_PARENT(n);
1553 tnode_free((struct tnode *) n);
1554
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001555 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001556 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1557 put_child(t, (struct tnode *)tp, cindex, NULL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001558 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Olof Johansson91b9a272005-08-09 20:24:39 -07001559 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001560 rcu_assign_pointer(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001561
1562 return 1;
1563}
1564
Robert Olssond562f1f2007-03-26 14:22:22 -07001565/*
1566 * Caller must hold RTNL.
1567 */
Thomas Graf4e902c52006-08-17 18:14:52 -07001568static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001569{
1570 struct trie *t = (struct trie *) tb->tb_data;
1571 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001572 int plen = cfg->fc_dst_len;
1573 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001574 struct fib_alias *fa, *fa_to_delete;
1575 struct list_head *fa_head;
1576 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001577 struct leaf_info *li;
1578
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001579 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001580 return -EINVAL;
1581
Thomas Graf4e902c52006-08-17 18:14:52 -07001582 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001583 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001584
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001585 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001586 return -EINVAL;
1587
1588 key = key & mask;
1589 l = fib_find_node(t, key);
1590
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001591 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001592 return -ESRCH;
1593
1594 fa_head = get_fa_head(l, plen);
1595 fa = fib_find_alias(fa_head, tos, 0);
1596
1597 if (!fa)
1598 return -ESRCH;
1599
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001600 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001601
1602 fa_to_delete = NULL;
1603 fa_head = fa->fa_list.prev;
Robert Olsson2373ce12005-08-25 13:01:29 -07001604
Robert Olsson19baf832005-06-21 12:43:18 -07001605 list_for_each_entry(fa, fa_head, fa_list) {
1606 struct fib_info *fi = fa->fa_info;
1607
1608 if (fa->fa_tos != tos)
1609 break;
1610
Thomas Graf4e902c52006-08-17 18:14:52 -07001611 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1612 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1613 fa->fa_scope == cfg->fc_scope) &&
1614 (!cfg->fc_protocol ||
1615 fi->fib_protocol == cfg->fc_protocol) &&
1616 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001617 fa_to_delete = fa;
1618 break;
1619 }
1620 }
1621
Olof Johansson91b9a272005-08-09 20:24:39 -07001622 if (!fa_to_delete)
1623 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001624
Olof Johansson91b9a272005-08-09 20:24:39 -07001625 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001626 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1627 &cfg->fc_nlinfo);
Robert Olsson19baf832005-06-21 12:43:18 -07001628
Olof Johansson91b9a272005-08-09 20:24:39 -07001629 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001630 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001631
Robert Olsson2373ce12005-08-25 13:01:29 -07001632 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001633
Olof Johansson91b9a272005-08-09 20:24:39 -07001634 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001635 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001636 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001637 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001638
1639 if (hlist_empty(&l->list))
1640 trie_leaf_remove(t, key);
1641
1642 if (fa->fa_state & FA_S_ACCESSED)
1643 rt_cache_flush(-1);
1644
Robert Olsson2373ce12005-08-25 13:01:29 -07001645 fib_release_info(fa->fa_info);
1646 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001647 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001648}
1649
1650static int trie_flush_list(struct trie *t, struct list_head *head)
1651{
1652 struct fib_alias *fa, *fa_node;
1653 int found = 0;
1654
1655 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1656 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001657
Robert Olsson2373ce12005-08-25 13:01:29 -07001658 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1659 list_del_rcu(&fa->fa_list);
1660 fib_release_info(fa->fa_info);
1661 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001662 found++;
1663 }
1664 }
1665 return found;
1666}
1667
1668static int trie_flush_leaf(struct trie *t, struct leaf *l)
1669{
1670 int found = 0;
1671 struct hlist_head *lih = &l->list;
1672 struct hlist_node *node, *tmp;
1673 struct leaf_info *li = NULL;
1674
1675 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001676 found += trie_flush_list(t, &li->falh);
1677
1678 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001679 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001680 free_leaf_info(li);
1681 }
1682 }
1683 return found;
1684}
1685
Robert Olsson2373ce12005-08-25 13:01:29 -07001686/* rcu_read_lock needs to be hold by caller from readside */
1687
Robert Olsson19baf832005-06-21 12:43:18 -07001688static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1689{
1690 struct node *c = (struct node *) thisleaf;
1691 struct tnode *p;
1692 int idx;
Robert Olsson2373ce12005-08-25 13:01:29 -07001693 struct node *trie = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -07001694
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001695 if (c == NULL) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001696 if (trie == NULL)
Robert Olsson19baf832005-06-21 12:43:18 -07001697 return NULL;
1698
Robert Olsson2373ce12005-08-25 13:01:29 -07001699 if (IS_LEAF(trie)) /* trie w. just a leaf */
1700 return (struct leaf *) trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001701
Robert Olsson2373ce12005-08-25 13:01:29 -07001702 p = (struct tnode*) trie; /* Start */
Olof Johansson91b9a272005-08-09 20:24:39 -07001703 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001704 p = (struct tnode *) NODE_PARENT(c);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001705
Robert Olsson19baf832005-06-21 12:43:18 -07001706 while (p) {
1707 int pos, last;
1708
1709 /* Find the next child of the parent */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001710 if (c)
1711 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1712 else
Robert Olsson19baf832005-06-21 12:43:18 -07001713 pos = 0;
1714
1715 last = 1 << p->bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001716 for (idx = pos; idx < last ; idx++) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001717 c = rcu_dereference(p->child[idx]);
1718
1719 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001720 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001721
Olof Johansson91b9a272005-08-09 20:24:39 -07001722 /* Decend if tnode */
Robert Olsson2373ce12005-08-25 13:01:29 -07001723 while (IS_TNODE(c)) {
1724 p = (struct tnode *) c;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09001725 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001726
Olof Johansson91b9a272005-08-09 20:24:39 -07001727 /* Rightmost non-NULL branch */
1728 if (p && IS_TNODE(p))
Robert Olsson2373ce12005-08-25 13:01:29 -07001729 while (!(c = rcu_dereference(p->child[idx]))
1730 && idx < (1<<p->bits)) idx++;
Robert Olsson19baf832005-06-21 12:43:18 -07001731
Olof Johansson91b9a272005-08-09 20:24:39 -07001732 /* Done with this tnode? */
Robert Olsson2373ce12005-08-25 13:01:29 -07001733 if (idx >= (1 << p->bits) || !c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001734 goto up;
Robert Olsson19baf832005-06-21 12:43:18 -07001735 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001736 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001737 }
1738up:
1739 /* No more children go up one step */
Olof Johansson91b9a272005-08-09 20:24:39 -07001740 c = (struct node *) p;
Robert Olsson19baf832005-06-21 12:43:18 -07001741 p = (struct tnode *) NODE_PARENT(p);
1742 }
1743 return NULL; /* Ready. Root of trie */
1744}
1745
Robert Olssond562f1f2007-03-26 14:22:22 -07001746/*
1747 * Caller must hold RTNL.
1748 */
Robert Olsson19baf832005-06-21 12:43:18 -07001749static int fn_trie_flush(struct fib_table *tb)
1750{
1751 struct trie *t = (struct trie *) tb->tb_data;
1752 struct leaf *ll = NULL, *l = NULL;
1753 int found = 0, h;
1754
1755 t->revision++;
1756
Olof Johansson91b9a272005-08-09 20:24:39 -07001757 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001758 found += trie_flush_leaf(t, l);
1759
1760 if (ll && hlist_empty(&ll->list))
1761 trie_leaf_remove(t, ll->key);
1762 ll = l;
1763 }
1764
1765 if (ll && hlist_empty(&ll->list))
1766 trie_leaf_remove(t, ll->key);
1767
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001768 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001769 return found;
1770}
1771
Olof Johansson91b9a272005-08-09 20:24:39 -07001772static int trie_last_dflt = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001773
1774static void
1775fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1776{
1777 struct trie *t = (struct trie *) tb->tb_data;
1778 int order, last_idx;
1779 struct fib_info *fi = NULL;
1780 struct fib_info *last_resort;
1781 struct fib_alias *fa = NULL;
1782 struct list_head *fa_head;
1783 struct leaf *l;
1784
1785 last_idx = -1;
1786 last_resort = NULL;
1787 order = -1;
1788
Robert Olsson2373ce12005-08-25 13:01:29 -07001789 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001790
Robert Olsson19baf832005-06-21 12:43:18 -07001791 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001792 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001793 goto out;
1794
1795 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001796 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001797 goto out;
1798
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001799 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001800 goto out;
1801
Robert Olsson2373ce12005-08-25 13:01:29 -07001802 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001803 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001804
Robert Olsson19baf832005-06-21 12:43:18 -07001805 if (fa->fa_scope != res->scope ||
1806 fa->fa_type != RTN_UNICAST)
1807 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001808
Robert Olsson19baf832005-06-21 12:43:18 -07001809 if (next_fi->fib_priority > res->fi->fib_priority)
1810 break;
1811 if (!next_fi->fib_nh[0].nh_gw ||
1812 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1813 continue;
1814 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001815
Robert Olsson19baf832005-06-21 12:43:18 -07001816 if (fi == NULL) {
1817 if (next_fi != res->fi)
1818 break;
1819 } else if (!fib_detect_death(fi, order, &last_resort,
1820 &last_idx, &trie_last_dflt)) {
1821 if (res->fi)
1822 fib_info_put(res->fi);
1823 res->fi = fi;
1824 atomic_inc(&fi->fib_clntref);
1825 trie_last_dflt = order;
1826 goto out;
1827 }
1828 fi = next_fi;
1829 order++;
1830 }
1831 if (order <= 0 || fi == NULL) {
1832 trie_last_dflt = -1;
1833 goto out;
1834 }
1835
1836 if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) {
1837 if (res->fi)
1838 fib_info_put(res->fi);
1839 res->fi = fi;
1840 atomic_inc(&fi->fib_clntref);
1841 trie_last_dflt = order;
1842 goto out;
1843 }
1844 if (last_idx >= 0) {
1845 if (res->fi)
1846 fib_info_put(res->fi);
1847 res->fi = last_resort;
1848 if (last_resort)
1849 atomic_inc(&last_resort->fib_clntref);
1850 }
1851 trie_last_dflt = last_idx;
1852 out:;
Robert Olsson2373ce12005-08-25 13:01:29 -07001853 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001854}
1855
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001856static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001857 struct sk_buff *skb, struct netlink_callback *cb)
1858{
1859 int i, s_i;
1860 struct fib_alias *fa;
1861
Al Viro32ab5f82006-09-26 22:21:45 -07001862 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001863
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001864 s_i = cb->args[4];
Robert Olsson19baf832005-06-21 12:43:18 -07001865 i = 0;
1866
Robert Olsson2373ce12005-08-25 13:01:29 -07001867 /* rcu_read_lock is hold by caller */
1868
1869 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001870 if (i < s_i) {
1871 i++;
1872 continue;
1873 }
Stephen Hemminger78c66712005-09-21 00:15:39 -07001874 BUG_ON(!fa->fa_info);
Robert Olsson19baf832005-06-21 12:43:18 -07001875
1876 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1877 cb->nlh->nlmsg_seq,
1878 RTM_NEWROUTE,
1879 tb->tb_id,
1880 fa->fa_type,
1881 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001882 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001883 plen,
1884 fa->fa_tos,
David S. Miller90f66912005-06-21 14:43:28 -07001885 fa->fa_info, 0) < 0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001886 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001887 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001888 }
Robert Olsson19baf832005-06-21 12:43:18 -07001889 i++;
1890 }
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001891 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001892 return skb->len;
1893}
1894
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001895static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
Robert Olsson19baf832005-06-21 12:43:18 -07001896 struct netlink_callback *cb)
1897{
1898 int h, s_h;
1899 struct list_head *fa_head;
1900 struct leaf *l = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001901
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001902 s_h = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001903
Olof Johansson91b9a272005-08-09 20:24:39 -07001904 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001905 if (h < s_h)
1906 continue;
1907 if (h > s_h)
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001908 memset(&cb->args[4], 0,
1909 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001910
1911 fa_head = get_fa_head(l, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001912
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001913 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001914 continue;
1915
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001916 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001917 continue;
1918
1919 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001920 cb->args[3] = h;
Robert Olsson19baf832005-06-21 12:43:18 -07001921 return -1;
1922 }
1923 }
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001924 cb->args[3] = h;
Robert Olsson19baf832005-06-21 12:43:18 -07001925 return skb->len;
1926}
1927
1928static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1929{
1930 int m, s_m;
1931 struct trie *t = (struct trie *) tb->tb_data;
1932
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001933 s_m = cb->args[2];
Robert Olsson19baf832005-06-21 12:43:18 -07001934
Robert Olsson2373ce12005-08-25 13:01:29 -07001935 rcu_read_lock();
Olof Johansson91b9a272005-08-09 20:24:39 -07001936 for (m = 0; m <= 32; m++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001937 if (m < s_m)
1938 continue;
1939 if (m > s_m)
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001940 memset(&cb->args[3], 0,
1941 sizeof(cb->args) - 3*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001942
1943 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001944 cb->args[2] = m;
Robert Olsson19baf832005-06-21 12:43:18 -07001945 goto out;
1946 }
1947 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001948 rcu_read_unlock();
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001949 cb->args[2] = m;
Robert Olsson19baf832005-06-21 12:43:18 -07001950 return skb->len;
Olof Johansson91b9a272005-08-09 20:24:39 -07001951out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001952 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001953 return -1;
1954}
1955
1956/* Fix more generic FIB names for init later */
1957
1958#ifdef CONFIG_IP_MULTIPLE_TABLES
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001959struct fib_table * fib_hash_init(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001960#else
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001961struct fib_table * __init fib_hash_init(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001962#endif
1963{
1964 struct fib_table *tb;
1965 struct trie *t;
1966
1967 if (fn_alias_kmem == NULL)
1968 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1969 sizeof(struct fib_alias),
1970 0, SLAB_HWCACHE_ALIGN,
1971 NULL, NULL);
1972
1973 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1974 GFP_KERNEL);
1975 if (tb == NULL)
1976 return NULL;
1977
1978 tb->tb_id = id;
1979 tb->tb_lookup = fn_trie_lookup;
1980 tb->tb_insert = fn_trie_insert;
1981 tb->tb_delete = fn_trie_delete;
1982 tb->tb_flush = fn_trie_flush;
1983 tb->tb_select_default = fn_trie_select_default;
1984 tb->tb_dump = fn_trie_dump;
1985 memset(tb->tb_data, 0, sizeof(struct trie));
1986
1987 t = (struct trie *) tb->tb_data;
1988
1989 trie_init(t);
1990
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001991 if (id == RT_TABLE_LOCAL)
Olof Johansson91b9a272005-08-09 20:24:39 -07001992 trie_local = t;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001993 else if (id == RT_TABLE_MAIN)
Olof Johansson91b9a272005-08-09 20:24:39 -07001994 trie_main = t;
Robert Olsson19baf832005-06-21 12:43:18 -07001995
1996 if (id == RT_TABLE_LOCAL)
Stephen Hemminger78c66712005-09-21 00:15:39 -07001997 printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07001998
1999 return tb;
2000}
2001
Robert Olsson19baf832005-06-21 12:43:18 -07002002#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002003/* Depth first Trie walk iterator */
2004struct fib_trie_iter {
2005 struct tnode *tnode;
2006 struct trie *trie;
2007 unsigned index;
2008 unsigned depth;
2009};
Robert Olsson19baf832005-06-21 12:43:18 -07002010
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002011static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002012{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002013 struct tnode *tn = iter->tnode;
2014 unsigned cindex = iter->index;
2015 struct tnode *p;
2016
Eric W. Biederman6640e692007-01-24 14:42:04 -08002017 /* A single entry routing table */
2018 if (!tn)
2019 return NULL;
2020
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002021 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2022 iter->tnode, iter->index, iter->depth);
2023rescan:
2024 while (cindex < (1<<tn->bits)) {
2025 struct node *n = tnode_get_child(tn, cindex);
2026
2027 if (n) {
2028 if (IS_LEAF(n)) {
2029 iter->tnode = tn;
2030 iter->index = cindex + 1;
2031 } else {
2032 /* push down one level */
2033 iter->tnode = (struct tnode *) n;
2034 iter->index = 0;
2035 ++iter->depth;
2036 }
2037 return n;
2038 }
2039
2040 ++cindex;
2041 }
2042
2043 /* Current node exhausted, pop back up */
2044 p = NODE_PARENT(tn);
2045 if (p) {
2046 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2047 tn = p;
2048 --iter->depth;
2049 goto rescan;
2050 }
2051
2052 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002053 return NULL;
2054}
2055
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002056static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2057 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002058{
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002059 struct node *n ;
2060
Stephen Hemminger132adf52007-03-08 20:44:43 -08002061 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002062 return NULL;
2063
2064 n = rcu_dereference(t->trie);
2065
Stephen Hemminger132adf52007-03-08 20:44:43 -08002066 if (!iter)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002067 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002068
Eric W. Biederman6640e692007-01-24 14:42:04 -08002069 if (n) {
2070 if (IS_TNODE(n)) {
2071 iter->tnode = (struct tnode *) n;
2072 iter->trie = t;
2073 iter->index = 0;
2074 iter->depth = 1;
2075 } else {
2076 iter->tnode = NULL;
2077 iter->trie = t;
2078 iter->index = 0;
2079 iter->depth = 0;
2080 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002081 return n;
2082 }
Robert Olsson19baf832005-06-21 12:43:18 -07002083 return NULL;
2084}
2085
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002086static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002087{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002088 struct node *n;
2089 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002090
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002091 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002092
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002093 rcu_read_lock();
2094 for (n = fib_trie_get_first(&iter, t); n;
2095 n = fib_trie_get_next(&iter)) {
2096 if (IS_LEAF(n)) {
2097 s->leaves++;
2098 s->totdepth += iter.depth;
2099 if (iter.depth > s->maxdepth)
2100 s->maxdepth = iter.depth;
2101 } else {
2102 const struct tnode *tn = (const struct tnode *) n;
2103 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002104
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002105 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002106 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002107 s->nodesizes[tn->bits]++;
2108
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002109 for (i = 0; i < (1<<tn->bits); i++)
2110 if (!tn->child[i])
2111 s->nullpointers++;
2112 }
2113 }
2114 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002115}
2116
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002117/*
Robert Olsson19baf832005-06-21 12:43:18 -07002118 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002119 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002120static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002121{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002122 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002123
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002124 if (stat->leaves)
2125 avdepth = stat->totdepth*100 / stat->leaves;
2126 else
2127 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002128
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002129 seq_printf(seq, "\tAver depth: %d.%02d\n", avdepth / 100, avdepth % 100 );
2130 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002131
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002132 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Olof Johansson91b9a272005-08-09 20:24:39 -07002133
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002134 bytes = sizeof(struct leaf) * stat->leaves;
2135 seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
2136 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002137
Robert Olsson06ef9212006-03-20 21:35:01 -08002138 max = MAX_STAT_DEPTH;
2139 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002140 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002141
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002142 pointers = 0;
2143 for (i = 1; i <= max; i++)
2144 if (stat->nodesizes[i] != 0) {
2145 seq_printf(seq, " %d: %d", i, stat->nodesizes[i]);
2146 pointers += (1<<i) * stat->nodesizes[i];
2147 }
2148 seq_putc(seq, '\n');
2149 seq_printf(seq, "\tPointers: %d\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002150
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002151 bytes += sizeof(struct node *) * pointers;
2152 seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
2153 seq_printf(seq, "Total size: %d kB\n", (bytes + 1023) / 1024);
Robert Olsson19baf832005-06-21 12:43:18 -07002154
2155#ifdef CONFIG_IP_FIB_TRIE_STATS
2156 seq_printf(seq, "Counters:\n---------\n");
2157 seq_printf(seq,"gets = %d\n", t->stats.gets);
2158 seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
2159 seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
2160 seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
2161 seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
Robert Olsson2f368952005-07-05 15:02:40 -07002162 seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002163#ifdef CLEAR_STATS
2164 memset(&(t->stats), 0, sizeof(t->stats));
2165#endif
2166#endif /* CONFIG_IP_FIB_TRIE_STATS */
2167}
2168
2169static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2170{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002171 struct trie_stat *stat;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002172
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002173 stat = kmalloc(sizeof(*stat), GFP_KERNEL);
2174 if (!stat)
2175 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002176
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002177 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2178 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002179
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002180 if (trie_local) {
2181 seq_printf(seq, "Local:\n");
2182 trie_collect_stats(trie_local, stat);
2183 trie_show_stats(seq, stat);
Robert Olsson19baf832005-06-21 12:43:18 -07002184 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002185
2186 if (trie_main) {
2187 seq_printf(seq, "Main:\n");
2188 trie_collect_stats(trie_main, stat);
2189 trie_show_stats(seq, stat);
2190 }
2191 kfree(stat);
2192
Robert Olsson19baf832005-06-21 12:43:18 -07002193 return 0;
2194}
2195
Robert Olsson19baf832005-06-21 12:43:18 -07002196static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2197{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002198 return single_open(file, fib_triestat_seq_show, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07002199}
2200
Arjan van de Ven9a321442007-02-12 00:55:35 -08002201static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002202 .owner = THIS_MODULE,
2203 .open = fib_triestat_seq_open,
2204 .read = seq_read,
2205 .llseek = seq_lseek,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002206 .release = single_release,
Robert Olsson19baf832005-06-21 12:43:18 -07002207};
2208
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002209static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2210 loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002211{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002212 loff_t idx = 0;
2213 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -07002214
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002215 for (n = fib_trie_get_first(iter, trie_local);
2216 n; ++idx, n = fib_trie_get_next(iter)) {
2217 if (pos == idx)
2218 return n;
2219 }
Robert Olsson19baf832005-06-21 12:43:18 -07002220
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002221 for (n = fib_trie_get_first(iter, trie_main);
2222 n; ++idx, n = fib_trie_get_next(iter)) {
2223 if (pos == idx)
2224 return n;
2225 }
Robert Olsson19baf832005-06-21 12:43:18 -07002226 return NULL;
2227}
2228
2229static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2230{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002231 rcu_read_lock();
2232 if (*pos == 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07002233 return SEQ_START_TOKEN;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002234 return fib_trie_get_idx(seq->private, *pos - 1);
Robert Olsson19baf832005-06-21 12:43:18 -07002235}
2236
2237static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2238{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002239 struct fib_trie_iter *iter = seq->private;
2240 void *l = v;
2241
Robert Olsson19baf832005-06-21 12:43:18 -07002242 ++*pos;
Olof Johansson91b9a272005-08-09 20:24:39 -07002243 if (v == SEQ_START_TOKEN)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002244 return fib_trie_get_idx(iter, 0);
Olof Johansson91b9a272005-08-09 20:24:39 -07002245
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002246 v = fib_trie_get_next(iter);
2247 BUG_ON(v == l);
2248 if (v)
2249 return v;
2250
2251 /* continue scan in next trie */
2252 if (iter->trie == trie_local)
2253 return fib_trie_get_first(iter, trie_main);
2254
2255 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07002256}
2257
2258static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2259{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002260 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002261}
2262
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002263static void seq_indent(struct seq_file *seq, int n)
2264{
2265 while (n-- > 0) seq_puts(seq, " ");
2266}
Robert Olsson19baf832005-06-21 12:43:18 -07002267
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002268static inline const char *rtn_scope(enum rt_scope_t s)
2269{
2270 static char buf[32];
2271
Stephen Hemminger132adf52007-03-08 20:44:43 -08002272 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002273 case RT_SCOPE_UNIVERSE: return "universe";
2274 case RT_SCOPE_SITE: return "site";
2275 case RT_SCOPE_LINK: return "link";
2276 case RT_SCOPE_HOST: return "host";
2277 case RT_SCOPE_NOWHERE: return "nowhere";
2278 default:
2279 snprintf(buf, sizeof(buf), "scope=%d", s);
2280 return buf;
2281 }
2282}
2283
2284static const char *rtn_type_names[__RTN_MAX] = {
2285 [RTN_UNSPEC] = "UNSPEC",
2286 [RTN_UNICAST] = "UNICAST",
2287 [RTN_LOCAL] = "LOCAL",
2288 [RTN_BROADCAST] = "BROADCAST",
2289 [RTN_ANYCAST] = "ANYCAST",
2290 [RTN_MULTICAST] = "MULTICAST",
2291 [RTN_BLACKHOLE] = "BLACKHOLE",
2292 [RTN_UNREACHABLE] = "UNREACHABLE",
2293 [RTN_PROHIBIT] = "PROHIBIT",
2294 [RTN_THROW] = "THROW",
2295 [RTN_NAT] = "NAT",
2296 [RTN_XRESOLVE] = "XRESOLVE",
2297};
2298
2299static inline const char *rtn_type(unsigned t)
2300{
2301 static char buf[32];
2302
2303 if (t < __RTN_MAX && rtn_type_names[t])
2304 return rtn_type_names[t];
2305 snprintf(buf, sizeof(buf), "type %d", t);
2306 return buf;
2307}
2308
2309/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002310static int fib_trie_seq_show(struct seq_file *seq, void *v)
2311{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002312 const struct fib_trie_iter *iter = seq->private;
2313 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002314
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002315 if (v == SEQ_START_TOKEN)
2316 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002317
Robert Olsson095b8502007-01-26 19:06:01 -08002318 if (!NODE_PARENT(n)) {
2319 if (iter->trie == trie_local)
2320 seq_puts(seq, "<local>:\n");
2321 else
2322 seq_puts(seq, "<main>:\n");
2323 }
2324
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002325 if (IS_TNODE(n)) {
2326 struct tnode *tn = (struct tnode *) n;
Al Viro32ab5f82006-09-26 22:21:45 -07002327 __be32 prf = htonl(MASK_PFX(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002328
Robert Olsson1d25cd62005-09-19 15:29:52 -07002329 seq_indent(seq, iter->depth-1);
2330 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002331 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002332 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002333
Olof Johansson91b9a272005-08-09 20:24:39 -07002334 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002335 struct leaf *l = (struct leaf *) n;
2336 int i;
Al Viro32ab5f82006-09-26 22:21:45 -07002337 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002338
2339 seq_indent(seq, iter->depth);
2340 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
2341 for (i = 32; i >= 0; i--) {
Robert Olsson772cb712005-09-19 15:31:18 -07002342 struct leaf_info *li = find_leaf_info(l, i);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002343 if (li) {
2344 struct fib_alias *fa;
2345 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2346 seq_indent(seq, iter->depth+1);
2347 seq_printf(seq, " /%d %s %s", i,
2348 rtn_scope(fa->fa_scope),
2349 rtn_type(fa->fa_type));
2350 if (fa->fa_tos)
2351 seq_printf(seq, "tos =%d\n",
2352 fa->fa_tos);
2353 seq_putc(seq, '\n');
2354 }
2355 }
2356 }
Robert Olsson19baf832005-06-21 12:43:18 -07002357 }
2358
2359 return 0;
2360}
2361
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002362static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002363 .start = fib_trie_seq_start,
2364 .next = fib_trie_seq_next,
2365 .stop = fib_trie_seq_stop,
2366 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002367};
2368
2369static int fib_trie_seq_open(struct inode *inode, struct file *file)
2370{
2371 struct seq_file *seq;
2372 int rc = -ENOMEM;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002373 struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2374
2375 if (!s)
2376 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07002377
2378 rc = seq_open(file, &fib_trie_seq_ops);
2379 if (rc)
2380 goto out_kfree;
2381
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002382 seq = file->private_data;
2383 seq->private = s;
2384 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002385out:
2386 return rc;
2387out_kfree:
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002388 kfree(s);
Robert Olsson19baf832005-06-21 12:43:18 -07002389 goto out;
2390}
2391
Arjan van de Ven9a321442007-02-12 00:55:35 -08002392static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002393 .owner = THIS_MODULE,
2394 .open = fib_trie_seq_open,
2395 .read = seq_read,
2396 .llseek = seq_lseek,
2397 .release = seq_release_private,
2398};
2399
Al Viro32ab5f82006-09-26 22:21:45 -07002400static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002401{
2402 static unsigned type2flags[RTN_MAX + 1] = {
2403 [7] = RTF_REJECT, [8] = RTF_REJECT,
2404 };
2405 unsigned flags = type2flags[type];
2406
2407 if (fi && fi->fib_nh->nh_gw)
2408 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002409 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002410 flags |= RTF_HOST;
2411 flags |= RTF_UP;
2412 return flags;
2413}
2414
2415/*
2416 * This outputs /proc/net/route.
2417 * The format of the file is not supposed to be changed
2418 * and needs to be same as fib_hash output to avoid breaking
2419 * legacy utilities
2420 */
2421static int fib_route_seq_show(struct seq_file *seq, void *v)
2422{
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002423 const struct fib_trie_iter *iter = seq->private;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002424 struct leaf *l = v;
2425 int i;
2426 char bf[128];
2427
2428 if (v == SEQ_START_TOKEN) {
2429 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2430 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2431 "\tWindow\tIRTT");
2432 return 0;
2433 }
2434
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002435 if (iter->trie == trie_local)
2436 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002437 if (IS_TNODE(l))
2438 return 0;
2439
2440 for (i=32; i>=0; i--) {
Robert Olsson772cb712005-09-19 15:31:18 -07002441 struct leaf_info *li = find_leaf_info(l, i);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002442 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002443 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002444
2445 if (!li)
2446 continue;
2447
2448 mask = inet_make_mask(li->plen);
2449 prefix = htonl(l->key);
2450
2451 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002452 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002453 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2454
2455 if (fa->fa_type == RTN_BROADCAST
2456 || fa->fa_type == RTN_MULTICAST)
2457 continue;
2458
2459 if (fi)
2460 snprintf(bf, sizeof(bf),
2461 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2462 fi->fib_dev ? fi->fib_dev->name : "*",
2463 prefix,
2464 fi->fib_nh->nh_gw, flags, 0, 0,
2465 fi->fib_priority,
2466 mask,
2467 (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
2468 fi->fib_window,
2469 fi->fib_rtt >> 3);
2470 else
2471 snprintf(bf, sizeof(bf),
2472 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2473 prefix, 0, flags, 0, 0, 0,
2474 mask, 0, 0, 0);
2475
2476 seq_printf(seq, "%-127s\n", bf);
2477 }
2478 }
2479
2480 return 0;
2481}
2482
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002483static const struct seq_operations fib_route_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002484 .start = fib_trie_seq_start,
2485 .next = fib_trie_seq_next,
2486 .stop = fib_trie_seq_stop,
2487 .show = fib_route_seq_show,
2488};
2489
2490static int fib_route_seq_open(struct inode *inode, struct file *file)
2491{
2492 struct seq_file *seq;
2493 int rc = -ENOMEM;
2494 struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2495
2496 if (!s)
2497 goto out;
2498
2499 rc = seq_open(file, &fib_route_seq_ops);
2500 if (rc)
2501 goto out_kfree;
2502
2503 seq = file->private_data;
2504 seq->private = s;
2505 memset(s, 0, sizeof(*s));
2506out:
2507 return rc;
2508out_kfree:
2509 kfree(s);
2510 goto out;
2511}
2512
Arjan van de Ven9a321442007-02-12 00:55:35 -08002513static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002514 .owner = THIS_MODULE,
2515 .open = fib_route_seq_open,
2516 .read = seq_read,
2517 .llseek = seq_lseek,
2518 .release = seq_release_private,
Robert Olsson19baf832005-06-21 12:43:18 -07002519};
2520
2521int __init fib_proc_init(void)
2522{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002523 if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops))
2524 goto out1;
2525
2526 if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops))
2527 goto out2;
2528
2529 if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops))
2530 goto out3;
2531
Robert Olsson19baf832005-06-21 12:43:18 -07002532 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002533
2534out3:
2535 proc_net_remove("fib_triestat");
2536out2:
2537 proc_net_remove("fib_trie");
2538out1:
2539 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002540}
2541
2542void __init fib_proc_exit(void)
2543{
2544 proc_net_remove("fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002545 proc_net_remove("fib_triestat");
2546 proc_net_remove("route");
Robert Olsson19baf832005-06-21 12:43:18 -07002547}
2548
2549#endif /* CONFIG_PROC_FS */