blob: cfb249cc0a5859c2fb06cf3877a978c9e066b14c [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 *
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences.
12 *
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
14 *
15 * This work is based on the LPC-trie which is originally descibed in:
16 *
17 * 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 Olsson550e29b2006-04-04 12:53:35 -070053#define VERSION "0.407"
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>
60#include <linux/sched.h>
61#include <linux/mm.h>
62#include <linux/string.h>
63#include <linux/socket.h>
64#include <linux/sockios.h>
65#include <linux/errno.h>
66#include <linux/in.h>
67#include <linux/inet.h>
Stephen Hemmingercd8787a2006-01-03 14:38:34 -080068#include <linux/inetdevice.h>
Robert Olsson19baf832005-06-21 12:43:18 -070069#include <linux/netdevice.h>
70#include <linux/if_arp.h>
71#include <linux/proc_fs.h>
Robert Olsson2373ce12005-08-25 13:01:29 -070072#include <linux/rcupdate.h>
Robert Olsson19baf832005-06-21 12:43:18 -070073#include <linux/skbuff.h>
74#include <linux/netlink.h>
75#include <linux/init.h>
76#include <linux/list.h>
77#include <net/ip.h>
78#include <net/protocol.h>
79#include <net/route.h>
80#include <net/tcp.h>
81#include <net/sock.h>
82#include <net/ip_fib.h>
83#include "fib_lookup.h"
84
85#undef CONFIG_IP_FIB_TRIE_STATS
Robert Olsson06ef9212006-03-20 21:35:01 -080086#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070087
Robert Olsson19baf832005-06-21 12:43:18 -070088#define KEYLENGTH (8*sizeof(t_key))
89#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
90#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
91
Robert Olsson19baf832005-06-21 12:43:18 -070092typedef unsigned int t_key;
93
94#define T_TNODE 0
95#define T_LEAF 1
96#define NODE_TYPE_MASK 0x1UL
Olof Johansson91b9a272005-08-09 20:24:39 -070097#define NODE_PARENT(node) \
Robert Olsson2373ce12005-08-25 13:01:29 -070098 ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
99
100#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
101
102#define NODE_SET_PARENT(node, ptr) \
103 rcu_assign_pointer((node)->parent, \
104 ((unsigned long)(ptr)) | NODE_TYPE(node))
Robert Olsson19baf832005-06-21 12:43:18 -0700105
Olof Johansson91b9a272005-08-09 20:24:39 -0700106#define IS_TNODE(n) (!(n->parent & T_LEAF))
107#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -0700108
109struct node {
Olof Johansson91b9a272005-08-09 20:24:39 -0700110 t_key key;
111 unsigned long parent;
Robert Olsson19baf832005-06-21 12:43:18 -0700112};
113
114struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700115 t_key key;
116 unsigned long parent;
Robert Olsson19baf832005-06-21 12:43:18 -0700117 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700118 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700119};
120
121struct leaf_info {
122 struct hlist_node hlist;
Robert Olsson2373ce12005-08-25 13:01:29 -0700123 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700124 int plen;
125 struct list_head falh;
126};
127
128struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700129 t_key key;
130 unsigned long parent;
131 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
132 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
133 unsigned short full_children; /* KEYLENGTH bits needed */
134 unsigned short empty_children; /* KEYLENGTH bits needed */
Robert Olsson2373ce12005-08-25 13:01:29 -0700135 struct rcu_head rcu;
Olof Johansson91b9a272005-08-09 20:24:39 -0700136 struct node *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700137};
138
139#ifdef CONFIG_IP_FIB_TRIE_STATS
140struct trie_use_stats {
141 unsigned int gets;
142 unsigned int backtrack;
143 unsigned int semantic_match_passed;
144 unsigned int semantic_match_miss;
145 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700146 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700147};
148#endif
149
150struct trie_stat {
151 unsigned int totdepth;
152 unsigned int maxdepth;
153 unsigned int tnodes;
154 unsigned int leaves;
155 unsigned int nullpointers;
Robert Olsson06ef9212006-03-20 21:35:01 -0800156 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700157};
Robert Olsson19baf832005-06-21 12:43:18 -0700158
159struct trie {
Olof Johansson91b9a272005-08-09 20:24:39 -0700160 struct node *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700161#ifdef CONFIG_IP_FIB_TRIE_STATS
162 struct trie_use_stats stats;
163#endif
Olof Johansson91b9a272005-08-09 20:24:39 -0700164 int size;
Robert Olsson19baf832005-06-21 12:43:18 -0700165 unsigned int revision;
166};
167
Robert Olsson19baf832005-06-21 12:43:18 -0700168static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
169static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
Robert Olsson19baf832005-06-21 12:43:18 -0700170static struct node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700171static struct tnode *inflate(struct trie *t, struct tnode *tn);
172static struct tnode *halve(struct trie *t, struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700173static void tnode_free(struct tnode *tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700174
Christoph Lametere18b8902006-12-06 20:33:20 -0800175static struct kmem_cache *fn_alias_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700176static struct trie *trie_local = NULL, *trie_main = NULL;
177
Robert Olsson2373ce12005-08-25 13:01:29 -0700178
179/* rcu_read_lock needs to be hold by caller from readside */
180
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700181static inline struct node *tnode_get_child(struct tnode *tn, int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700182{
Olof Johansson91b9a272005-08-09 20:24:39 -0700183 BUG_ON(i >= 1 << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700184
Robert Olsson2373ce12005-08-25 13:01:29 -0700185 return rcu_dereference(tn->child[i]);
Robert Olsson19baf832005-06-21 12:43:18 -0700186}
187
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700188static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700189{
Olof Johansson91b9a272005-08-09 20:24:39 -0700190 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700191}
192
Robert Olsson19baf832005-06-21 12:43:18 -0700193static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
194{
Olof Johansson91b9a272005-08-09 20:24:39 -0700195 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700196 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700197 else
Robert Olsson19baf832005-06-21 12:43:18 -0700198 return 0;
199}
200
201static inline int tkey_equals(t_key a, t_key b)
202{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700203 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700204}
205
206static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
207{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700208 if (bits == 0 || offset >= KEYLENGTH)
209 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700210 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
211 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700212}
Robert Olsson19baf832005-06-21 12:43:18 -0700213
214static inline int tkey_mismatch(t_key a, int offset, t_key b)
215{
216 t_key diff = a ^ b;
217 int i = offset;
218
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700219 if (!diff)
220 return 0;
221 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700222 i++;
223 return i;
224}
225
Robert Olsson19baf832005-06-21 12:43:18 -0700226/*
227 To understand this stuff, an understanding of keys and all their bits is
228 necessary. Every node in the trie has a key associated with it, but not
229 all of the bits in that key are significant.
230
231 Consider a node 'n' and its parent 'tp'.
232
233 If n is a leaf, every bit in its key is significant. Its presence is
Robert Olsson772cb712005-09-19 15:31:18 -0700234 necessitated by path compression, since during a tree traversal (when
Robert Olsson19baf832005-06-21 12:43:18 -0700235 searching for a leaf - unless we are doing an insertion) we will completely
236 ignore all skipped bits we encounter. Thus we need to verify, at the end of
237 a potentially successful search, that we have indeed been walking the
238 correct key path.
239
240 Note that we can never "miss" the correct key in the tree if present by
241 following the wrong path. Path compression ensures that segments of the key
242 that are the same for all keys with a given prefix are skipped, but the
243 skipped part *is* identical for each node in the subtrie below the skipped
244 bit! trie_insert() in this implementation takes care of that - note the
245 call to tkey_sub_equals() in trie_insert().
246
247 if n is an internal node - a 'tnode' here, the various parts of its key
248 have many different meanings.
249
250 Example:
251 _________________________________________________________________
252 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
253 -----------------------------------------------------------------
254 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
255
256 _________________________________________________________________
257 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
258 -----------------------------------------------------------------
259 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
260
261 tp->pos = 7
262 tp->bits = 3
263 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700264 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700265
266 First, let's just ignore the bits that come before the parent tp, that is
267 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
268 not use them for anything.
269
270 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
271 index into the parent's child array. That is, they will be used to find
272 'n' among tp's children.
273
274 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
275 for the node n.
276
277 All the bits we have seen so far are significant to the node n. The rest
278 of the bits are really not needed or indeed known in n->key.
279
280 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
281 n's child array, and will of course be different for each child.
282
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700283
Robert Olsson19baf832005-06-21 12:43:18 -0700284 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
285 at this point.
286
287*/
288
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700289static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700290{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700291 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700292}
293
294static int halve_threshold = 25;
295static int inflate_threshold = 50;
Robert Olssone6308be2005-10-04 13:01:58 -0700296static int halve_threshold_root = 15;
297static int inflate_threshold_root = 25;
Robert Olsson19baf832005-06-21 12:43:18 -0700298
Robert Olsson2373ce12005-08-25 13:01:29 -0700299
300static void __alias_free_mem(struct rcu_head *head)
301{
302 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
303 kmem_cache_free(fn_alias_kmem, fa);
304}
305
306static inline void alias_free_mem_rcu(struct fib_alias *fa)
307{
308 call_rcu(&fa->rcu, __alias_free_mem);
309}
310
311static void __leaf_free_rcu(struct rcu_head *head)
312{
313 kfree(container_of(head, struct leaf, rcu));
314}
315
Robert Olsson2373ce12005-08-25 13:01:29 -0700316static void __leaf_info_free_rcu(struct rcu_head *head)
317{
318 kfree(container_of(head, struct leaf_info, rcu));
319}
320
321static inline void free_leaf_info(struct leaf_info *leaf)
322{
323 call_rcu(&leaf->rcu, __leaf_info_free_rcu);
324}
325
326static struct tnode *tnode_alloc(unsigned int size)
327{
328 struct page *pages;
329
330 if (size <= PAGE_SIZE)
331 return kcalloc(size, 1, GFP_KERNEL);
332
333 pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
334 if (!pages)
335 return NULL;
336
337 return page_address(pages);
338}
339
340static void __tnode_free_rcu(struct rcu_head *head)
341{
342 struct tnode *tn = container_of(head, struct tnode, rcu);
343 unsigned int size = sizeof(struct tnode) +
344 (1 << tn->bits) * sizeof(struct node *);
345
346 if (size <= PAGE_SIZE)
347 kfree(tn);
348 else
349 free_pages((unsigned long)tn, get_order(size));
350}
351
352static inline void tnode_free(struct tnode *tn)
353{
Robert Olsson550e29b2006-04-04 12:53:35 -0700354 if(IS_LEAF(tn)) {
355 struct leaf *l = (struct leaf *) tn;
356 call_rcu_bh(&l->rcu, __leaf_free_rcu);
357 }
358 else
359 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700360}
361
Robert Olsson19baf832005-06-21 12:43:18 -0700362static struct leaf *leaf_new(void)
363{
364 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700365 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700366 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700367 INIT_HLIST_HEAD(&l->list);
368 }
369 return l;
370}
371
372static struct leaf_info *leaf_info_new(int plen)
373{
374 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700375 if (li) {
376 li->plen = plen;
377 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700378 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700379 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700380}
381
Robert Olsson19baf832005-06-21 12:43:18 -0700382static struct tnode* tnode_new(t_key key, int pos, int bits)
383{
384 int nchildren = 1<<bits;
385 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700386 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700387
Olof Johansson91b9a272005-08-09 20:24:39 -0700388 if (tn) {
Robert Olsson19baf832005-06-21 12:43:18 -0700389 memset(tn, 0, sz);
Robert Olsson2373ce12005-08-25 13:01:29 -0700390 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700391 tn->pos = pos;
392 tn->bits = bits;
393 tn->key = key;
394 tn->full_children = 0;
395 tn->empty_children = 1<<bits;
396 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700397
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700398 pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
399 (unsigned int) (sizeof(struct node) * 1<<bits));
Robert Olsson19baf832005-06-21 12:43:18 -0700400 return tn;
401}
402
Robert Olsson19baf832005-06-21 12:43:18 -0700403/*
404 * Check whether a tnode 'n' is "full", i.e. it is an internal node
405 * and no bits are skipped. See discussion in dyntree paper p. 6
406 */
407
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700408static inline int tnode_full(const struct tnode *tn, const struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700409{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700410 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700411 return 0;
412
413 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
414}
415
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700416static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700417{
418 tnode_put_child_reorg(tn, i, n, -1);
419}
420
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700421 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700422 * Add a child at position i overwriting the old value.
423 * Update the value of full_children and empty_children.
424 */
425
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700426static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700427{
Robert Olsson2373ce12005-08-25 13:01:29 -0700428 struct node *chi = tn->child[i];
Robert Olsson19baf832005-06-21 12:43:18 -0700429 int isfull;
430
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700431 BUG_ON(i >= 1<<tn->bits);
432
Robert Olsson19baf832005-06-21 12:43:18 -0700433
434 /* update emptyChildren */
435 if (n == NULL && chi != NULL)
436 tn->empty_children++;
437 else if (n != NULL && chi == NULL)
438 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700439
Robert Olsson19baf832005-06-21 12:43:18 -0700440 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700441 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700442 wasfull = tnode_full(tn, chi);
443
444 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700445 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700446 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700447 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700448 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700449
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700450 if (n)
451 NODE_SET_PARENT(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700452
Robert Olsson2373ce12005-08-25 13:01:29 -0700453 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700454}
455
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700456static struct node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700457{
458 int i;
Robert Olsson2f368952005-07-05 15:02:40 -0700459 int err = 0;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700460 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700461 int inflate_threshold_use;
462 int halve_threshold_use;
Robert Olsson19baf832005-06-21 12:43:18 -0700463
464 if (!tn)
465 return NULL;
466
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700467 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
468 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700469
470 /* No children */
471 if (tn->empty_children == tnode_child_length(tn)) {
472 tnode_free(tn);
473 return NULL;
474 }
475 /* One child */
476 if (tn->empty_children == tnode_child_length(tn) - 1)
477 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700478 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700479
Olof Johansson91b9a272005-08-09 20:24:39 -0700480 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700481 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700482 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700483
484 /* compress one level */
Robert Olsson2373ce12005-08-25 13:01:29 -0700485 NODE_SET_PARENT(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700486 tnode_free(tn);
487 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700488 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700489 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700490 * Double as long as the resulting node has a number of
491 * nonempty nodes that are above the threshold.
492 */
493
494 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700495 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
496 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700497 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700498 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700499 * children in the *doubled* node is at least 'high'."
500 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700501 * 'high' in this instance is the variable 'inflate_threshold'. It
502 * is expressed as a percentage, so we multiply it with
503 * tnode_child_length() and instead of multiplying by 2 (since the
504 * child array will be doubled by inflate()) and multiplying
505 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700506 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700507 *
508 * The left-hand side may look a bit weird: tnode_child_length(tn)
509 * - tn->empty_children is of course the number of non-null children
510 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700511 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700512 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700513 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700514 *
Robert Olsson19baf832005-06-21 12:43:18 -0700515 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700516 *
Robert Olsson19baf832005-06-21 12:43:18 -0700517 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700518 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700519 * tn->full_children;
520 *
521 * new_child_length = tnode_child_length(tn) * 2;
522 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700523 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700524 * new_child_length;
525 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700526 *
527 * ...and so on, tho it would mess up the while () loop.
528 *
Robert Olsson19baf832005-06-21 12:43:18 -0700529 * anyway,
530 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
531 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700532 *
Robert Olsson19baf832005-06-21 12:43:18 -0700533 * avoid a division:
534 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
535 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700536 *
Robert Olsson19baf832005-06-21 12:43:18 -0700537 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700538 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700539 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700540 *
Robert Olsson19baf832005-06-21 12:43:18 -0700541 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700542 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700543 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700544 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700545 *
Robert Olsson19baf832005-06-21 12:43:18 -0700546 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700547 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700548 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700549 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700550 *
Robert Olsson19baf832005-06-21 12:43:18 -0700551 */
552
553 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700554
Robert Olssone6308be2005-10-04 13:01:58 -0700555 /* Keep root node larger */
556
557 if(!tn->parent)
558 inflate_threshold_use = inflate_threshold_root;
559 else
560 inflate_threshold_use = inflate_threshold;
561
Robert Olsson2f368952005-07-05 15:02:40 -0700562 err = 0;
Robert Olsson19baf832005-06-21 12:43:18 -0700563 while ((tn->full_children > 0 &&
564 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
578 check_tnode(tn);
579
580 /*
581 * Halve as long as the number of empty children in this
582 * node is above threshold.
583 */
Robert Olsson2f368952005-07-05 15:02:40 -0700584
Robert Olssone6308be2005-10-04 13:01:58 -0700585
586 /* Keep root node larger */
587
588 if(!tn->parent)
589 halve_threshold_use = halve_threshold_root;
590 else
591 halve_threshold_use = halve_threshold;
592
Robert Olsson2f368952005-07-05 15:02:40 -0700593 err = 0;
Robert Olsson19baf832005-06-21 12:43:18 -0700594 while (tn->bits > 1 &&
595 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700596 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700597
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700598 old_tn = tn;
599 tn = halve(t, tn);
600 if (IS_ERR(tn)) {
601 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700602#ifdef CONFIG_IP_FIB_TRIE_STATS
603 t->stats.resize_node_skipped++;
604#endif
605 break;
606 }
607 }
608
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700609
Robert Olsson19baf832005-06-21 12:43:18 -0700610 /* Only one child remains */
Robert Olsson19baf832005-06-21 12:43:18 -0700611 if (tn->empty_children == tnode_child_length(tn) - 1)
612 for (i = 0; i < tnode_child_length(tn); i++) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700613 struct node *n;
614
Olof Johansson91b9a272005-08-09 20:24:39 -0700615 n = tn->child[i];
Robert Olsson2373ce12005-08-25 13:01:29 -0700616 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700617 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700618
619 /* compress one level */
620
Robert Olsson2373ce12005-08-25 13:01:29 -0700621 NODE_SET_PARENT(n, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700622 tnode_free(tn);
623 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700624 }
625
626 return (struct node *) tn;
627}
628
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700629static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700630{
631 struct tnode *inode;
632 struct tnode *oldtnode = tn;
633 int olen = tnode_child_length(tn);
634 int i;
635
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700636 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700637
638 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
639
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700640 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700641 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700642
643 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700644 * Preallocate and store tnodes before the actual work so we
645 * don't get into an inconsistent state if memory allocation
646 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700647 * of tnode is ignored.
648 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700649
650 for (i = 0; i < olen; i++) {
Robert Olsson2f368952005-07-05 15:02:40 -0700651 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
652
653 if (inode &&
654 IS_TNODE(inode) &&
655 inode->pos == oldtnode->pos + oldtnode->bits &&
656 inode->bits > 1) {
657 struct tnode *left, *right;
Robert Olsson2f368952005-07-05 15:02:40 -0700658 t_key m = TKEY_GET_MASK(inode->pos, 1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700659
Robert Olsson2f368952005-07-05 15:02:40 -0700660 left = tnode_new(inode->key&(~m), inode->pos + 1,
661 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700662 if (!left)
663 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700664
Robert Olsson2f368952005-07-05 15:02:40 -0700665 right = tnode_new(inode->key|m, inode->pos + 1,
666 inode->bits - 1);
667
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700668 if (!right) {
669 tnode_free(left);
670 goto nomem;
671 }
Robert Olsson2f368952005-07-05 15:02:40 -0700672
673 put_child(t, tn, 2*i, (struct node *) left);
674 put_child(t, tn, 2*i+1, (struct node *) right);
675 }
676 }
677
Olof Johansson91b9a272005-08-09 20:24:39 -0700678 for (i = 0; i < olen; i++) {
Robert Olsson19baf832005-06-21 12:43:18 -0700679 struct node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700680 struct tnode *left, *right;
681 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700682
Robert Olsson19baf832005-06-21 12:43:18 -0700683 /* An empty child */
684 if (node == NULL)
685 continue;
686
687 /* A leaf or an internal node with skipped bits */
688
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700689 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700690 tn->pos + tn->bits - 1) {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700691 if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
Robert Olsson19baf832005-06-21 12:43:18 -0700692 1) == 0)
693 put_child(t, tn, 2*i, node);
694 else
695 put_child(t, tn, 2*i+1, node);
696 continue;
697 }
698
699 /* An internal node with two children */
700 inode = (struct tnode *) node;
701
702 if (inode->bits == 1) {
703 put_child(t, tn, 2*i, inode->child[0]);
704 put_child(t, tn, 2*i+1, inode->child[1]);
705
706 tnode_free(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700707 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700708 }
709
Olof Johansson91b9a272005-08-09 20:24:39 -0700710 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700711
Olof Johansson91b9a272005-08-09 20:24:39 -0700712 /* We will replace this node 'inode' with two new
713 * ones, 'left' and 'right', each with half of the
714 * original children. The two new nodes will have
715 * a position one bit further down the key and this
716 * means that the "significant" part of their keys
717 * (see the discussion near the top of this file)
718 * will differ by one bit, which will be "0" in
719 * left's key and "1" in right's key. Since we are
720 * moving the key position by one step, the bit that
721 * we are moving away from - the bit at position
722 * (inode->pos) - is the one that will differ between
723 * left and right. So... we synthesize that bit in the
724 * two new keys.
725 * The mask 'm' below will be a single "one" bit at
726 * the position (inode->pos)
727 */
Robert Olsson19baf832005-06-21 12:43:18 -0700728
Olof Johansson91b9a272005-08-09 20:24:39 -0700729 /* Use the old key, but set the new significant
730 * bit to zero.
731 */
Robert Olsson19baf832005-06-21 12:43:18 -0700732
Olof Johansson91b9a272005-08-09 20:24:39 -0700733 left = (struct tnode *) tnode_get_child(tn, 2*i);
734 put_child(t, tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700735
Olof Johansson91b9a272005-08-09 20:24:39 -0700736 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700737
Olof Johansson91b9a272005-08-09 20:24:39 -0700738 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
739 put_child(t, tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700740
Olof Johansson91b9a272005-08-09 20:24:39 -0700741 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700742
Olof Johansson91b9a272005-08-09 20:24:39 -0700743 size = tnode_child_length(left);
744 for (j = 0; j < size; j++) {
745 put_child(t, left, j, inode->child[j]);
746 put_child(t, right, j, inode->child[j + size]);
Robert Olsson19baf832005-06-21 12:43:18 -0700747 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700748 put_child(t, tn, 2*i, resize(t, left));
749 put_child(t, tn, 2*i+1, resize(t, right));
750
751 tnode_free(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700752 }
753 tnode_free(oldtnode);
754 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700755nomem:
756 {
757 int size = tnode_child_length(tn);
758 int j;
759
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700760 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700761 if (tn->child[j])
762 tnode_free((struct tnode *)tn->child[j]);
763
764 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700765
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700766 return ERR_PTR(-ENOMEM);
767 }
Robert Olsson19baf832005-06-21 12:43:18 -0700768}
769
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700770static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700771{
772 struct tnode *oldtnode = tn;
773 struct node *left, *right;
774 int i;
775 int olen = tnode_child_length(tn);
776
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700777 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700778
779 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700780
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700781 if (!tn)
782 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700783
784 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700785 * Preallocate and store tnodes before the actual work so we
786 * don't get into an inconsistent state if memory allocation
787 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700788 * of tnode is ignored.
789 */
790
Olof Johansson91b9a272005-08-09 20:24:39 -0700791 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700792 left = tnode_get_child(oldtnode, i);
793 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700794
Robert Olsson2f368952005-07-05 15:02:40 -0700795 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700796 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700797 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700798
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700799 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700800
801 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700802 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700803
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700804 put_child(t, tn, i/2, (struct node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700805 }
Robert Olsson2f368952005-07-05 15:02:40 -0700806
Robert Olsson2f368952005-07-05 15:02:40 -0700807 }
Robert Olsson19baf832005-06-21 12:43:18 -0700808
Olof Johansson91b9a272005-08-09 20:24:39 -0700809 for (i = 0; i < olen; i += 2) {
810 struct tnode *newBinNode;
811
Robert Olsson19baf832005-06-21 12:43:18 -0700812 left = tnode_get_child(oldtnode, i);
813 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700814
Robert Olsson19baf832005-06-21 12:43:18 -0700815 /* At least one of the children is empty */
816 if (left == NULL) {
817 if (right == NULL) /* Both are empty */
818 continue;
819 put_child(t, tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700820 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700821 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700822
823 if (right == NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700824 put_child(t, tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700825 continue;
826 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700827
Robert Olsson19baf832005-06-21 12:43:18 -0700828 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700829 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
830 put_child(t, tn, i/2, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700831 put_child(t, newBinNode, 0, left);
832 put_child(t, newBinNode, 1, right);
833 put_child(t, tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700834 }
835 tnode_free(oldtnode);
836 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700837nomem:
838 {
839 int size = tnode_child_length(tn);
840 int j;
841
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700842 for (j = 0; j < size; j++)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700843 if (tn->child[j])
844 tnode_free((struct tnode *)tn->child[j]);
845
846 tnode_free(tn);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700847
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700848 return ERR_PTR(-ENOMEM);
849 }
Robert Olsson19baf832005-06-21 12:43:18 -0700850}
851
Olof Johansson91b9a272005-08-09 20:24:39 -0700852static void trie_init(struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -0700853{
Olof Johansson91b9a272005-08-09 20:24:39 -0700854 if (!t)
855 return;
856
857 t->size = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700858 rcu_assign_pointer(t->trie, NULL);
Olof Johansson91b9a272005-08-09 20:24:39 -0700859 t->revision = 0;
Robert Olsson19baf832005-06-21 12:43:18 -0700860#ifdef CONFIG_IP_FIB_TRIE_STATS
Olof Johansson91b9a272005-08-09 20:24:39 -0700861 memset(&t->stats, 0, sizeof(struct trie_use_stats));
Robert Olsson19baf832005-06-21 12:43:18 -0700862#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700863}
864
Robert Olsson772cb712005-09-19 15:31:18 -0700865/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700866 via get_fa_head and dump */
867
Robert Olsson772cb712005-09-19 15:31:18 -0700868static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700869{
Robert Olsson772cb712005-09-19 15:31:18 -0700870 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700871 struct hlist_node *node;
872 struct leaf_info *li;
873
Robert Olsson2373ce12005-08-25 13:01:29 -0700874 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700875 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700876 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700877
Robert Olsson19baf832005-06-21 12:43:18 -0700878 return NULL;
879}
880
881static inline struct list_head * get_fa_head(struct leaf *l, int plen)
882{
Robert Olsson772cb712005-09-19 15:31:18 -0700883 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700884
Olof Johansson91b9a272005-08-09 20:24:39 -0700885 if (!li)
886 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700887
Olof Johansson91b9a272005-08-09 20:24:39 -0700888 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700889}
890
891static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
892{
Robert Olsson2373ce12005-08-25 13:01:29 -0700893 struct leaf_info *li = NULL, *last = NULL;
894 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700895
Robert Olsson2373ce12005-08-25 13:01:29 -0700896 if (hlist_empty(head)) {
897 hlist_add_head_rcu(&new->hlist, head);
898 } else {
899 hlist_for_each_entry(li, node, head, hlist) {
900 if (new->plen > li->plen)
901 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700902
Robert Olsson2373ce12005-08-25 13:01:29 -0700903 last = li;
904 }
905 if (last)
906 hlist_add_after_rcu(&last->hlist, &new->hlist);
907 else
908 hlist_add_before_rcu(&new->hlist, &li->hlist);
909 }
Robert Olsson19baf832005-06-21 12:43:18 -0700910}
911
Robert Olsson2373ce12005-08-25 13:01:29 -0700912/* rcu_read_lock needs to be hold by caller from readside */
913
Robert Olsson19baf832005-06-21 12:43:18 -0700914static struct leaf *
915fib_find_node(struct trie *t, u32 key)
916{
917 int pos;
918 struct tnode *tn;
919 struct node *n;
920
921 pos = 0;
Robert Olsson2373ce12005-08-25 13:01:29 -0700922 n = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700923
924 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
925 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700926
Robert Olsson19baf832005-06-21 12:43:18 -0700927 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700928
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700929 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700930 pos = tn->pos + tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700931 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700932 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700933 break;
934 }
935 /* Case we have found a leaf. Compare prefixes */
936
Olof Johansson91b9a272005-08-09 20:24:39 -0700937 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
938 return (struct leaf *)n;
939
Robert Olsson19baf832005-06-21 12:43:18 -0700940 return NULL;
941}
942
943static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
944{
Robert Olsson19baf832005-06-21 12:43:18 -0700945 int wasfull;
946 t_key cindex, key;
947 struct tnode *tp = NULL;
948
Robert Olsson19baf832005-06-21 12:43:18 -0700949 key = tn->key;
Robert Olsson19baf832005-06-21 12:43:18 -0700950
951 while (tn != NULL && NODE_PARENT(tn) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -0700952
953 tp = NODE_PARENT(tn);
954 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
955 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
956 tn = (struct tnode *) resize (t, (struct tnode *)tn);
957 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -0700958
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700959 if (!NODE_PARENT(tn))
Robert Olsson19baf832005-06-21 12:43:18 -0700960 break;
961
962 tn = NODE_PARENT(tn);
963 }
964 /* Handle last (top) tnode */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700965 if (IS_TNODE(tn))
Robert Olsson19baf832005-06-21 12:43:18 -0700966 tn = (struct tnode*) resize(t, (struct tnode *)tn);
967
968 return (struct node*) tn;
969}
970
Robert Olsson2373ce12005-08-25 13:01:29 -0700971/* only used from updater-side */
972
Robert Olssonf835e472005-06-28 15:00:39 -0700973static struct list_head *
974fib_insert_node(struct trie *t, int *err, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700975{
976 int pos, newpos;
977 struct tnode *tp = NULL, *tn = NULL;
978 struct node *n;
979 struct leaf *l;
980 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700981 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -0700982 struct leaf_info *li;
983 t_key cindex;
984
985 pos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700986 n = t->trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700987
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700988 /* If we point to NULL, stop. Either the tree is empty and we should
989 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -0700990 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700991 * If we point to a T_TNODE, check if it matches our key. Note that
992 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -0700993 * not be the parent's 'pos'+'bits'!
994 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700995 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -0700996 * the index from our key, push the T_TNODE and walk the tree.
997 *
998 * If it doesn't, we have to replace it with a new T_TNODE.
999 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001000 * If we point to a T_LEAF, it might or might not have the same key
1001 * as we do. If it does, just change the value, update the T_LEAF's
1002 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001003 * If it doesn't, we need to replace it with a T_TNODE.
1004 */
1005
1006 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1007 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001008
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001009 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001010
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001011 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001012 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001013 pos = tn->pos + tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001014 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1015
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001016 BUG_ON(n && NODE_PARENT(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001017 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001018 break;
1019 }
1020
1021 /*
1022 * n ----> NULL, LEAF or TNODE
1023 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001024 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001025 */
1026
Olof Johansson91b9a272005-08-09 20:24:39 -07001027 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001028
1029 /* Case 1: n is a leaf. Compare prefixes */
1030
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001031 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001032 struct leaf *l = (struct leaf *) n;
1033
Robert Olsson19baf832005-06-21 12:43:18 -07001034 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001035
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001036 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001037 *err = -ENOMEM;
1038 goto err;
1039 }
Robert Olsson19baf832005-06-21 12:43:18 -07001040
1041 fa_head = &li->falh;
1042 insert_leaf_info(&l->list, li);
1043 goto done;
1044 }
1045 t->size++;
1046 l = leaf_new();
1047
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001048 if (!l) {
Robert Olssonf835e472005-06-28 15:00:39 -07001049 *err = -ENOMEM;
1050 goto err;
1051 }
Robert Olsson19baf832005-06-21 12:43:18 -07001052
1053 l->key = key;
1054 li = leaf_info_new(plen);
1055
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001056 if (!li) {
Robert Olssonf835e472005-06-28 15:00:39 -07001057 tnode_free((struct tnode *) l);
1058 *err = -ENOMEM;
1059 goto err;
1060 }
Robert Olsson19baf832005-06-21 12:43:18 -07001061
1062 fa_head = &li->falh;
1063 insert_leaf_info(&l->list, li);
1064
Robert Olsson19baf832005-06-21 12:43:18 -07001065 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001066 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001067
1068 NODE_SET_PARENT(l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001069
Olof Johansson91b9a272005-08-09 20:24:39 -07001070 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1071 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1072 } else {
1073 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001074 /*
1075 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001076 * first tnode need some special handling
1077 */
1078
1079 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001080 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001081 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001082 pos = 0;
1083
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001084 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001085 newpos = tkey_mismatch(key, pos, n->key);
1086 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001087 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001088 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001089 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001090 }
Robert Olsson19baf832005-06-21 12:43:18 -07001091
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001092 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001093 free_leaf_info(li);
1094 tnode_free((struct tnode *) l);
1095 *err = -ENOMEM;
1096 goto err;
Olof Johansson91b9a272005-08-09 20:24:39 -07001097 }
1098
Robert Olsson19baf832005-06-21 12:43:18 -07001099 NODE_SET_PARENT(tn, tp);
1100
Olof Johansson91b9a272005-08-09 20:24:39 -07001101 missbit = tkey_extract_bits(key, newpos, 1);
Robert Olsson19baf832005-06-21 12:43:18 -07001102 put_child(t, tn, missbit, (struct node *)l);
1103 put_child(t, tn, 1-missbit, n);
1104
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001105 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001106 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1107 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001108 } else {
Robert Olsson2373ce12005-08-25 13:01:29 -07001109 rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001110 tp = tn;
1111 }
1112 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001113
1114 if (tp && tp->pos + tp->bits > 32)
Stephen Hemminger78c66712005-09-21 00:15:39 -07001115 printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
Robert Olsson19baf832005-06-21 12:43:18 -07001116 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001117
Robert Olsson19baf832005-06-21 12:43:18 -07001118 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001119
1120 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Robert Olssonf835e472005-06-28 15:00:39 -07001121done:
1122 t->revision++;
Olof Johansson91b9a272005-08-09 20:24:39 -07001123err:
Robert Olsson19baf832005-06-21 12:43:18 -07001124 return fa_head;
1125}
1126
Thomas Graf4e902c52006-08-17 18:14:52 -07001127static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001128{
1129 struct trie *t = (struct trie *) tb->tb_data;
1130 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001131 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001132 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001133 int plen = cfg->fc_dst_len;
1134 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001135 u32 key, mask;
1136 int err;
1137 struct leaf *l;
1138
1139 if (plen > 32)
1140 return -EINVAL;
1141
Thomas Graf4e902c52006-08-17 18:14:52 -07001142 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001143
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001144 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001145
Olof Johansson91b9a272005-08-09 20:24:39 -07001146 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001147
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001148 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001149 return -EINVAL;
1150
1151 key = key & mask;
1152
Thomas Graf4e902c52006-08-17 18:14:52 -07001153 fi = fib_create_info(cfg);
1154 if (IS_ERR(fi)) {
1155 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001156 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001157 }
Robert Olsson19baf832005-06-21 12:43:18 -07001158
1159 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001160 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001161
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001162 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001163 fa_head = get_fa_head(l, plen);
1164 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1165 }
1166
1167 /* Now fa, if non-NULL, points to the first fib alias
1168 * with the same keys [prefix,tos,priority], if such key already
1169 * exists or to the node before which we will insert new one.
1170 *
1171 * If fa is NULL, we will need to allocate a new one and
1172 * insert to the head of f.
1173 *
1174 * If f is NULL, no fib node matched the destination key
1175 * and we need to allocate a new one of those as well.
1176 */
1177
Olof Johansson91b9a272005-08-09 20:24:39 -07001178 if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
Robert Olsson19baf832005-06-21 12:43:18 -07001179 struct fib_alias *fa_orig;
1180
1181 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001182 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001183 goto out;
1184
Thomas Graf4e902c52006-08-17 18:14:52 -07001185 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001186 struct fib_info *fi_drop;
1187 u8 state;
1188
Robert Olsson2373ce12005-08-25 13:01:29 -07001189 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001190 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001191 if (new_fa == NULL)
1192 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001193
1194 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001195 new_fa->fa_tos = fa->fa_tos;
1196 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001197 new_fa->fa_type = cfg->fc_type;
1198 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001199 state = fa->fa_state;
Robert Olsson2373ce12005-08-25 13:01:29 -07001200 new_fa->fa_state &= ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001201
Robert Olsson2373ce12005-08-25 13:01:29 -07001202 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1203 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001204
1205 fib_release_info(fi_drop);
1206 if (state & FA_S_ACCESSED)
Olof Johansson91b9a272005-08-09 20:24:39 -07001207 rt_cache_flush(-1);
Robert Olsson19baf832005-06-21 12:43:18 -07001208
Olof Johansson91b9a272005-08-09 20:24:39 -07001209 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001210 }
1211 /* Error if we find a perfect match which
1212 * uses the same scope, type, and nexthop
1213 * information.
1214 */
1215 fa_orig = fa;
1216 list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
1217 if (fa->fa_tos != tos)
1218 break;
1219 if (fa->fa_info->fib_priority != fi->fib_priority)
1220 break;
Thomas Graf4e902c52006-08-17 18:14:52 -07001221 if (fa->fa_type == cfg->fc_type &&
1222 fa->fa_scope == cfg->fc_scope &&
Robert Olsson19baf832005-06-21 12:43:18 -07001223 fa->fa_info == fi) {
1224 goto out;
1225 }
1226 }
Thomas Graf4e902c52006-08-17 18:14:52 -07001227 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Robert Olsson19baf832005-06-21 12:43:18 -07001228 fa = fa_orig;
1229 }
1230 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001231 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001232 goto out;
1233
1234 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001235 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001236 if (new_fa == NULL)
1237 goto out;
1238
1239 new_fa->fa_info = fi;
1240 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001241 new_fa->fa_type = cfg->fc_type;
1242 new_fa->fa_scope = cfg->fc_scope;
Robert Olsson19baf832005-06-21 12:43:18 -07001243 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001244 /*
1245 * Insert new entry to the list.
1246 */
1247
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001248 if (!fa_head) {
Robert Olssonf835e472005-06-28 15:00:39 -07001249 err = 0;
Herbert Xub47b2ec2006-07-12 13:29:56 -07001250 fa_head = fib_insert_node(t, &err, key, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001251 if (err)
Robert Olssonf835e472005-06-28 15:00:39 -07001252 goto out_free_new_fa;
1253 }
Robert Olsson19baf832005-06-21 12:43:18 -07001254
Robert Olsson2373ce12005-08-25 13:01:29 -07001255 list_add_tail_rcu(&new_fa->fa_list,
1256 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001257
1258 rt_cache_flush(-1);
Thomas Graf4e902c52006-08-17 18:14:52 -07001259 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
1260 &cfg->fc_nlinfo);
Robert Olsson19baf832005-06-21 12:43:18 -07001261succeeded:
1262 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001263
1264out_free_new_fa:
1265 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001266out:
1267 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001268err:
Robert Olsson19baf832005-06-21 12:43:18 -07001269 return err;
1270}
1271
Robert Olsson2373ce12005-08-25 13:01:29 -07001272
Robert Olsson772cb712005-09-19 15:31:18 -07001273/* should be called with rcu_read_lock */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001274static inline int check_leaf(struct trie *t, struct leaf *l,
1275 t_key key, int *plen, const struct flowi *flp,
Patrick McHardy06c74272005-08-23 22:06:09 -07001276 struct fib_result *res)
Robert Olsson19baf832005-06-21 12:43:18 -07001277{
Patrick McHardy06c74272005-08-23 22:06:09 -07001278 int err, i;
Al Viro888454c2006-09-19 13:42:46 -07001279 __be32 mask;
Robert Olsson19baf832005-06-21 12:43:18 -07001280 struct leaf_info *li;
1281 struct hlist_head *hhead = &l->list;
1282 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001283
Robert Olsson2373ce12005-08-25 13:01:29 -07001284 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001285 i = li->plen;
Al Viro888454c2006-09-19 13:42:46 -07001286 mask = inet_make_mask(i);
1287 if (l->key != (key & ntohl(mask)))
Robert Olsson19baf832005-06-21 12:43:18 -07001288 continue;
1289
Al Viro888454c2006-09-19 13:42:46 -07001290 if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001291 *plen = i;
1292#ifdef CONFIG_IP_FIB_TRIE_STATS
1293 t->stats.semantic_match_passed++;
1294#endif
Patrick McHardy06c74272005-08-23 22:06:09 -07001295 return err;
Robert Olsson19baf832005-06-21 12:43:18 -07001296 }
1297#ifdef CONFIG_IP_FIB_TRIE_STATS
1298 t->stats.semantic_match_miss++;
1299#endif
1300 }
Patrick McHardy06c74272005-08-23 22:06:09 -07001301 return 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001302}
1303
1304static int
1305fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1306{
1307 struct trie *t = (struct trie *) tb->tb_data;
1308 int plen, ret = 0;
1309 struct node *n;
1310 struct tnode *pn;
1311 int pos, bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001312 t_key key = ntohl(flp->fl4_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001313 int chopped_off;
1314 t_key cindex = 0;
1315 int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001316 struct tnode *cn;
1317 t_key node_prefix, key_prefix, pref_mismatch;
1318 int mp;
1319
Robert Olsson2373ce12005-08-25 13:01:29 -07001320 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001321
Robert Olsson2373ce12005-08-25 13:01:29 -07001322 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001323 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001324 goto failed;
1325
1326#ifdef CONFIG_IP_FIB_TRIE_STATS
1327 t->stats.gets++;
1328#endif
1329
1330 /* Just a leaf? */
1331 if (IS_LEAF(n)) {
Patrick McHardy06c74272005-08-23 22:06:09 -07001332 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001333 goto found;
1334 goto failed;
1335 }
1336 pn = (struct tnode *) n;
1337 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001338
Olof Johansson91b9a272005-08-09 20:24:39 -07001339 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001340 pos = pn->pos;
1341 bits = pn->bits;
1342
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001343 if (!chopped_off)
Robert Olsson19baf832005-06-21 12:43:18 -07001344 cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);
1345
1346 n = tnode_get_child(pn, cindex);
1347
1348 if (n == NULL) {
1349#ifdef CONFIG_IP_FIB_TRIE_STATS
1350 t->stats.null_node_hit++;
1351#endif
1352 goto backtrace;
1353 }
1354
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001355 if (IS_LEAF(n)) {
Patrick McHardy06c74272005-08-23 22:06:09 -07001356 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
Robert Olsson19baf832005-06-21 12:43:18 -07001357 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001358 else
1359 goto backtrace;
1360 }
1361
1362#define HL_OPTIMIZE
1363#ifdef HL_OPTIMIZE
1364 cn = (struct tnode *)n;
1365
1366 /*
1367 * It's a tnode, and we can do some extra checks here if we
1368 * like, to avoid descending into a dead-end branch.
1369 * This tnode is in the parent's child array at index
1370 * key[p_pos..p_pos+p_bits] but potentially with some bits
1371 * chopped off, so in reality the index may be just a
1372 * subprefix, padded with zero at the end.
1373 * We can also take a look at any skipped bits in this
1374 * tnode - everything up to p_pos is supposed to be ok,
1375 * and the non-chopped bits of the index (se previous
1376 * paragraph) are also guaranteed ok, but the rest is
1377 * considered unknown.
1378 *
1379 * The skipped bits are key[pos+bits..cn->pos].
1380 */
1381
1382 /* If current_prefix_length < pos+bits, we are already doing
1383 * actual prefix matching, which means everything from
1384 * pos+(bits-chopped_off) onward must be zero along some
1385 * branch of this subtree - otherwise there is *no* valid
1386 * prefix present. Here we can only check the skipped
1387 * bits. Remember, since we have already indexed into the
1388 * parent's child array, we know that the bits we chopped of
1389 * *are* zero.
1390 */
1391
1392 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1393
1394 if (current_prefix_length < pos+bits) {
1395 if (tkey_extract_bits(cn->key, current_prefix_length,
1396 cn->pos - current_prefix_length) != 0 ||
1397 !(cn->child[0]))
1398 goto backtrace;
1399 }
1400
1401 /*
1402 * If chopped_off=0, the index is fully validated and we
1403 * only need to look at the skipped bits for this, the new,
1404 * tnode. What we actually want to do is to find out if
1405 * these skipped bits match our key perfectly, or if we will
1406 * have to count on finding a matching prefix further down,
1407 * because if we do, we would like to have some way of
1408 * verifying the existence of such a prefix at this point.
1409 */
1410
1411 /* The only thing we can do at this point is to verify that
1412 * any such matching prefix can indeed be a prefix to our
1413 * key, and if the bits in the node we are inspecting that
1414 * do not match our key are not ZERO, this cannot be true.
1415 * Thus, find out where there is a mismatch (before cn->pos)
1416 * and verify that all the mismatching bits are zero in the
1417 * new tnode's key.
1418 */
1419
1420 /* Note: We aren't very concerned about the piece of the key
1421 * that precede pn->pos+pn->bits, since these have already been
1422 * checked. The bits after cn->pos aren't checked since these are
1423 * by definition "unknown" at this point. Thus, what we want to
1424 * see is if we are about to enter the "prefix matching" state,
1425 * and in that case verify that the skipped bits that will prevail
1426 * throughout this subtree are zero, as they have to be if we are
1427 * to find a matching prefix.
1428 */
1429
1430 node_prefix = MASK_PFX(cn->key, cn->pos);
1431 key_prefix = MASK_PFX(key, cn->pos);
1432 pref_mismatch = key_prefix^node_prefix;
1433 mp = 0;
1434
1435 /* In short: If skipped bits in this node do not match the search
1436 * key, enter the "prefix matching" state.directly.
1437 */
1438 if (pref_mismatch) {
1439 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1440 mp++;
1441 pref_mismatch = pref_mismatch <<1;
1442 }
1443 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1444
1445 if (key_prefix != 0)
1446 goto backtrace;
1447
1448 if (current_prefix_length >= cn->pos)
1449 current_prefix_length = mp;
1450 }
1451#endif
1452 pn = (struct tnode *)n; /* Descend */
1453 chopped_off = 0;
1454 continue;
1455
Robert Olsson19baf832005-06-21 12:43:18 -07001456backtrace:
1457 chopped_off++;
1458
1459 /* As zero don't change the child key (cindex) */
Olof Johansson91b9a272005-08-09 20:24:39 -07001460 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001461 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001462
1463 /* Decrease current_... with bits chopped off */
1464 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1465 current_prefix_length = pn->pos + pn->bits - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001466
Robert Olsson19baf832005-06-21 12:43:18 -07001467 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001468 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001469 * chopped off all bits in this tnode walk up to our parent.
1470 */
1471
Olof Johansson91b9a272005-08-09 20:24:39 -07001472 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001473 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001474 } else {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001475 if (NODE_PARENT(pn) == NULL)
Robert Olsson19baf832005-06-21 12:43:18 -07001476 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001477
Robert Olsson19baf832005-06-21 12:43:18 -07001478 /* Get Child's index */
1479 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
1480 pn = NODE_PARENT(pn);
1481 chopped_off = 0;
1482
1483#ifdef CONFIG_IP_FIB_TRIE_STATS
1484 t->stats.backtrack++;
1485#endif
1486 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001487 }
Robert Olsson19baf832005-06-21 12:43:18 -07001488 }
1489failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001490 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001491found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001492 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001493 return ret;
1494}
1495
Robert Olsson2373ce12005-08-25 13:01:29 -07001496/* only called from updater side */
Robert Olsson19baf832005-06-21 12:43:18 -07001497static int trie_leaf_remove(struct trie *t, t_key key)
1498{
1499 t_key cindex;
1500 struct tnode *tp = NULL;
1501 struct node *n = t->trie;
1502 struct leaf *l;
1503
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001504 pr_debug("entering trie_leaf_remove(%p)\n", n);
Robert Olsson19baf832005-06-21 12:43:18 -07001505
1506 /* Note that in the case skipped bits, those bits are *not* checked!
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001507 * When we finish this, we will have NULL or a T_LEAF, and the
Robert Olsson19baf832005-06-21 12:43:18 -07001508 * T_LEAF may or may not match our key.
1509 */
1510
Olof Johansson91b9a272005-08-09 20:24:39 -07001511 while (n != NULL && IS_TNODE(n)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001512 struct tnode *tn = (struct tnode *) n;
1513 check_tnode(tn);
1514 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1515
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001516 BUG_ON(n && NODE_PARENT(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001517 }
Robert Olsson19baf832005-06-21 12:43:18 -07001518 l = (struct leaf *) n;
1519
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001520 if (!n || !tkey_equals(l->key, key))
Robert Olsson19baf832005-06-21 12:43:18 -07001521 return 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001522
1523 /*
1524 * Key found.
1525 * Remove the leaf and rebalance the tree
Robert Olsson19baf832005-06-21 12:43:18 -07001526 */
1527
1528 t->revision++;
1529 t->size--;
1530
Robert Olsson2373ce12005-08-25 13:01:29 -07001531 preempt_disable();
Robert Olsson19baf832005-06-21 12:43:18 -07001532 tp = NODE_PARENT(n);
1533 tnode_free((struct tnode *) n);
1534
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001535 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001536 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1537 put_child(t, (struct tnode *)tp, cindex, NULL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001538 rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
Olof Johansson91b9a272005-08-09 20:24:39 -07001539 } else
Robert Olsson2373ce12005-08-25 13:01:29 -07001540 rcu_assign_pointer(t->trie, NULL);
1541 preempt_enable();
Robert Olsson19baf832005-06-21 12:43:18 -07001542
1543 return 1;
1544}
1545
Thomas Graf4e902c52006-08-17 18:14:52 -07001546static int fn_trie_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001547{
1548 struct trie *t = (struct trie *) tb->tb_data;
1549 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001550 int plen = cfg->fc_dst_len;
1551 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001552 struct fib_alias *fa, *fa_to_delete;
1553 struct list_head *fa_head;
1554 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001555 struct leaf_info *li;
1556
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001557 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001558 return -EINVAL;
1559
Thomas Graf4e902c52006-08-17 18:14:52 -07001560 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001561 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001562
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001563 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001564 return -EINVAL;
1565
1566 key = key & mask;
1567 l = fib_find_node(t, key);
1568
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001569 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001570 return -ESRCH;
1571
1572 fa_head = get_fa_head(l, plen);
1573 fa = fib_find_alias(fa_head, tos, 0);
1574
1575 if (!fa)
1576 return -ESRCH;
1577
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001578 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001579
1580 fa_to_delete = NULL;
1581 fa_head = fa->fa_list.prev;
Robert Olsson2373ce12005-08-25 13:01:29 -07001582
Robert Olsson19baf832005-06-21 12:43:18 -07001583 list_for_each_entry(fa, fa_head, fa_list) {
1584 struct fib_info *fi = fa->fa_info;
1585
1586 if (fa->fa_tos != tos)
1587 break;
1588
Thomas Graf4e902c52006-08-17 18:14:52 -07001589 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1590 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
1591 fa->fa_scope == cfg->fc_scope) &&
1592 (!cfg->fc_protocol ||
1593 fi->fib_protocol == cfg->fc_protocol) &&
1594 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001595 fa_to_delete = fa;
1596 break;
1597 }
1598 }
1599
Olof Johansson91b9a272005-08-09 20:24:39 -07001600 if (!fa_to_delete)
1601 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001602
Olof Johansson91b9a272005-08-09 20:24:39 -07001603 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001604 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
1605 &cfg->fc_nlinfo);
Robert Olsson19baf832005-06-21 12:43:18 -07001606
Olof Johansson91b9a272005-08-09 20:24:39 -07001607 l = fib_find_node(t, key);
Robert Olsson772cb712005-09-19 15:31:18 -07001608 li = find_leaf_info(l, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001609
Robert Olsson2373ce12005-08-25 13:01:29 -07001610 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001611
Olof Johansson91b9a272005-08-09 20:24:39 -07001612 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001613 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001614 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001615 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001616
1617 if (hlist_empty(&l->list))
1618 trie_leaf_remove(t, key);
1619
1620 if (fa->fa_state & FA_S_ACCESSED)
1621 rt_cache_flush(-1);
1622
Robert Olsson2373ce12005-08-25 13:01:29 -07001623 fib_release_info(fa->fa_info);
1624 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001625 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001626}
1627
1628static int trie_flush_list(struct trie *t, struct list_head *head)
1629{
1630 struct fib_alias *fa, *fa_node;
1631 int found = 0;
1632
1633 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1634 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001635
Robert Olsson2373ce12005-08-25 13:01:29 -07001636 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1637 list_del_rcu(&fa->fa_list);
1638 fib_release_info(fa->fa_info);
1639 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001640 found++;
1641 }
1642 }
1643 return found;
1644}
1645
1646static int trie_flush_leaf(struct trie *t, struct leaf *l)
1647{
1648 int found = 0;
1649 struct hlist_head *lih = &l->list;
1650 struct hlist_node *node, *tmp;
1651 struct leaf_info *li = NULL;
1652
1653 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Robert Olsson19baf832005-06-21 12:43:18 -07001654 found += trie_flush_list(t, &li->falh);
1655
1656 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001657 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001658 free_leaf_info(li);
1659 }
1660 }
1661 return found;
1662}
1663
Robert Olsson2373ce12005-08-25 13:01:29 -07001664/* rcu_read_lock needs to be hold by caller from readside */
1665
Robert Olsson19baf832005-06-21 12:43:18 -07001666static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1667{
1668 struct node *c = (struct node *) thisleaf;
1669 struct tnode *p;
1670 int idx;
Robert Olsson2373ce12005-08-25 13:01:29 -07001671 struct node *trie = rcu_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -07001672
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001673 if (c == NULL) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001674 if (trie == NULL)
Robert Olsson19baf832005-06-21 12:43:18 -07001675 return NULL;
1676
Robert Olsson2373ce12005-08-25 13:01:29 -07001677 if (IS_LEAF(trie)) /* trie w. just a leaf */
1678 return (struct leaf *) trie;
Robert Olsson19baf832005-06-21 12:43:18 -07001679
Robert Olsson2373ce12005-08-25 13:01:29 -07001680 p = (struct tnode*) trie; /* Start */
Olof Johansson91b9a272005-08-09 20:24:39 -07001681 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001682 p = (struct tnode *) NODE_PARENT(c);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001683
Robert Olsson19baf832005-06-21 12:43:18 -07001684 while (p) {
1685 int pos, last;
1686
1687 /* Find the next child of the parent */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001688 if (c)
1689 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1690 else
Robert Olsson19baf832005-06-21 12:43:18 -07001691 pos = 0;
1692
1693 last = 1 << p->bits;
Olof Johansson91b9a272005-08-09 20:24:39 -07001694 for (idx = pos; idx < last ; idx++) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001695 c = rcu_dereference(p->child[idx]);
1696
1697 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001698 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001699
Olof Johansson91b9a272005-08-09 20:24:39 -07001700 /* Decend if tnode */
Robert Olsson2373ce12005-08-25 13:01:29 -07001701 while (IS_TNODE(c)) {
1702 p = (struct tnode *) c;
1703 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001704
Olof Johansson91b9a272005-08-09 20:24:39 -07001705 /* Rightmost non-NULL branch */
1706 if (p && IS_TNODE(p))
Robert Olsson2373ce12005-08-25 13:01:29 -07001707 while (!(c = rcu_dereference(p->child[idx]))
1708 && idx < (1<<p->bits)) idx++;
Robert Olsson19baf832005-06-21 12:43:18 -07001709
Olof Johansson91b9a272005-08-09 20:24:39 -07001710 /* Done with this tnode? */
Robert Olsson2373ce12005-08-25 13:01:29 -07001711 if (idx >= (1 << p->bits) || !c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001712 goto up;
Robert Olsson19baf832005-06-21 12:43:18 -07001713 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001714 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001715 }
1716up:
1717 /* No more children go up one step */
Olof Johansson91b9a272005-08-09 20:24:39 -07001718 c = (struct node *) p;
Robert Olsson19baf832005-06-21 12:43:18 -07001719 p = (struct tnode *) NODE_PARENT(p);
1720 }
1721 return NULL; /* Ready. Root of trie */
1722}
1723
1724static int fn_trie_flush(struct fib_table *tb)
1725{
1726 struct trie *t = (struct trie *) tb->tb_data;
1727 struct leaf *ll = NULL, *l = NULL;
1728 int found = 0, h;
1729
1730 t->revision++;
1731
Olof Johansson91b9a272005-08-09 20:24:39 -07001732 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001733 found += trie_flush_leaf(t, l);
1734
1735 if (ll && hlist_empty(&ll->list))
1736 trie_leaf_remove(t, ll->key);
1737 ll = l;
1738 }
1739
1740 if (ll && hlist_empty(&ll->list))
1741 trie_leaf_remove(t, ll->key);
1742
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001743 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001744 return found;
1745}
1746
Olof Johansson91b9a272005-08-09 20:24:39 -07001747static int trie_last_dflt = -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001748
1749static void
1750fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1751{
1752 struct trie *t = (struct trie *) tb->tb_data;
1753 int order, last_idx;
1754 struct fib_info *fi = NULL;
1755 struct fib_info *last_resort;
1756 struct fib_alias *fa = NULL;
1757 struct list_head *fa_head;
1758 struct leaf *l;
1759
1760 last_idx = -1;
1761 last_resort = NULL;
1762 order = -1;
1763
Robert Olsson2373ce12005-08-25 13:01:29 -07001764 rcu_read_lock();
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001765
Robert Olsson19baf832005-06-21 12:43:18 -07001766 l = fib_find_node(t, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001767 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001768 goto out;
1769
1770 fa_head = get_fa_head(l, 0);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001771 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001772 goto out;
1773
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001774 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001775 goto out;
1776
Robert Olsson2373ce12005-08-25 13:01:29 -07001777 list_for_each_entry_rcu(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001778 struct fib_info *next_fi = fa->fa_info;
Olof Johansson91b9a272005-08-09 20:24:39 -07001779
Robert Olsson19baf832005-06-21 12:43:18 -07001780 if (fa->fa_scope != res->scope ||
1781 fa->fa_type != RTN_UNICAST)
1782 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -07001783
Robert Olsson19baf832005-06-21 12:43:18 -07001784 if (next_fi->fib_priority > res->fi->fib_priority)
1785 break;
1786 if (!next_fi->fib_nh[0].nh_gw ||
1787 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1788 continue;
1789 fa->fa_state |= FA_S_ACCESSED;
Olof Johansson91b9a272005-08-09 20:24:39 -07001790
Robert Olsson19baf832005-06-21 12:43:18 -07001791 if (fi == NULL) {
1792 if (next_fi != res->fi)
1793 break;
1794 } else if (!fib_detect_death(fi, order, &last_resort,
1795 &last_idx, &trie_last_dflt)) {
1796 if (res->fi)
1797 fib_info_put(res->fi);
1798 res->fi = fi;
1799 atomic_inc(&fi->fib_clntref);
1800 trie_last_dflt = order;
1801 goto out;
1802 }
1803 fi = next_fi;
1804 order++;
1805 }
1806 if (order <= 0 || fi == NULL) {
1807 trie_last_dflt = -1;
1808 goto out;
1809 }
1810
1811 if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) {
1812 if (res->fi)
1813 fib_info_put(res->fi);
1814 res->fi = fi;
1815 atomic_inc(&fi->fib_clntref);
1816 trie_last_dflt = order;
1817 goto out;
1818 }
1819 if (last_idx >= 0) {
1820 if (res->fi)
1821 fib_info_put(res->fi);
1822 res->fi = last_resort;
1823 if (last_resort)
1824 atomic_inc(&last_resort->fib_clntref);
1825 }
1826 trie_last_dflt = last_idx;
1827 out:;
Robert Olsson2373ce12005-08-25 13:01:29 -07001828 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001829}
1830
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001831static 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 -07001832 struct sk_buff *skb, struct netlink_callback *cb)
1833{
1834 int i, s_i;
1835 struct fib_alias *fa;
1836
Al Viro32ab5f82006-09-26 22:21:45 -07001837 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001838
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001839 s_i = cb->args[4];
Robert Olsson19baf832005-06-21 12:43:18 -07001840 i = 0;
1841
Robert Olsson2373ce12005-08-25 13:01:29 -07001842 /* rcu_read_lock is hold by caller */
1843
1844 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001845 if (i < s_i) {
1846 i++;
1847 continue;
1848 }
Stephen Hemminger78c66712005-09-21 00:15:39 -07001849 BUG_ON(!fa->fa_info);
Robert Olsson19baf832005-06-21 12:43:18 -07001850
1851 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1852 cb->nlh->nlmsg_seq,
1853 RTM_NEWROUTE,
1854 tb->tb_id,
1855 fa->fa_type,
1856 fa->fa_scope,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001857 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001858 plen,
1859 fa->fa_tos,
David S. Miller90f66912005-06-21 14:43:28 -07001860 fa->fa_info, 0) < 0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001861 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001862 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001863 }
Robert Olsson19baf832005-06-21 12:43:18 -07001864 i++;
1865 }
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001866 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001867 return skb->len;
1868}
1869
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001870static 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 -07001871 struct netlink_callback *cb)
1872{
1873 int h, s_h;
1874 struct list_head *fa_head;
1875 struct leaf *l = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001876
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001877 s_h = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001878
Olof Johansson91b9a272005-08-09 20:24:39 -07001879 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001880 if (h < s_h)
1881 continue;
1882 if (h > s_h)
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001883 memset(&cb->args[4], 0,
1884 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001885
1886 fa_head = get_fa_head(l, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001887
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001888 if (!fa_head)
Robert Olsson19baf832005-06-21 12:43:18 -07001889 continue;
1890
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001891 if (list_empty(fa_head))
Robert Olsson19baf832005-06-21 12:43:18 -07001892 continue;
1893
1894 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001895 cb->args[3] = h;
Robert Olsson19baf832005-06-21 12:43:18 -07001896 return -1;
1897 }
1898 }
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001899 cb->args[3] = h;
Robert Olsson19baf832005-06-21 12:43:18 -07001900 return skb->len;
1901}
1902
1903static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1904{
1905 int m, s_m;
1906 struct trie *t = (struct trie *) tb->tb_data;
1907
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001908 s_m = cb->args[2];
Robert Olsson19baf832005-06-21 12:43:18 -07001909
Robert Olsson2373ce12005-08-25 13:01:29 -07001910 rcu_read_lock();
Olof Johansson91b9a272005-08-09 20:24:39 -07001911 for (m = 0; m <= 32; m++) {
Robert Olsson19baf832005-06-21 12:43:18 -07001912 if (m < s_m)
1913 continue;
1914 if (m > s_m)
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001915 memset(&cb->args[3], 0,
1916 sizeof(cb->args) - 3*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001917
1918 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001919 cb->args[2] = m;
Robert Olsson19baf832005-06-21 12:43:18 -07001920 goto out;
1921 }
1922 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001923 rcu_read_unlock();
Patrick McHardy1af5a8c2006-08-10 23:10:46 -07001924 cb->args[2] = m;
Robert Olsson19baf832005-06-21 12:43:18 -07001925 return skb->len;
Olof Johansson91b9a272005-08-09 20:24:39 -07001926out:
Robert Olsson2373ce12005-08-25 13:01:29 -07001927 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001928 return -1;
1929}
1930
1931/* Fix more generic FIB names for init later */
1932
1933#ifdef CONFIG_IP_MULTIPLE_TABLES
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001934struct fib_table * fib_hash_init(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001935#else
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001936struct fib_table * __init fib_hash_init(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001937#endif
1938{
1939 struct fib_table *tb;
1940 struct trie *t;
1941
1942 if (fn_alias_kmem == NULL)
1943 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1944 sizeof(struct fib_alias),
1945 0, SLAB_HWCACHE_ALIGN,
1946 NULL, NULL);
1947
1948 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1949 GFP_KERNEL);
1950 if (tb == NULL)
1951 return NULL;
1952
1953 tb->tb_id = id;
1954 tb->tb_lookup = fn_trie_lookup;
1955 tb->tb_insert = fn_trie_insert;
1956 tb->tb_delete = fn_trie_delete;
1957 tb->tb_flush = fn_trie_flush;
1958 tb->tb_select_default = fn_trie_select_default;
1959 tb->tb_dump = fn_trie_dump;
1960 memset(tb->tb_data, 0, sizeof(struct trie));
1961
1962 t = (struct trie *) tb->tb_data;
1963
1964 trie_init(t);
1965
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001966 if (id == RT_TABLE_LOCAL)
Olof Johansson91b9a272005-08-09 20:24:39 -07001967 trie_local = t;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001968 else if (id == RT_TABLE_MAIN)
Olof Johansson91b9a272005-08-09 20:24:39 -07001969 trie_main = t;
Robert Olsson19baf832005-06-21 12:43:18 -07001970
1971 if (id == RT_TABLE_LOCAL)
Stephen Hemminger78c66712005-09-21 00:15:39 -07001972 printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
Robert Olsson19baf832005-06-21 12:43:18 -07001973
1974 return tb;
1975}
1976
Robert Olsson19baf832005-06-21 12:43:18 -07001977#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07001978/* Depth first Trie walk iterator */
1979struct fib_trie_iter {
1980 struct tnode *tnode;
1981 struct trie *trie;
1982 unsigned index;
1983 unsigned depth;
1984};
Robert Olsson19baf832005-06-21 12:43:18 -07001985
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07001986static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07001987{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07001988 struct tnode *tn = iter->tnode;
1989 unsigned cindex = iter->index;
1990 struct tnode *p;
1991
1992 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
1993 iter->tnode, iter->index, iter->depth);
1994rescan:
1995 while (cindex < (1<<tn->bits)) {
1996 struct node *n = tnode_get_child(tn, cindex);
1997
1998 if (n) {
1999 if (IS_LEAF(n)) {
2000 iter->tnode = tn;
2001 iter->index = cindex + 1;
2002 } else {
2003 /* push down one level */
2004 iter->tnode = (struct tnode *) n;
2005 iter->index = 0;
2006 ++iter->depth;
2007 }
2008 return n;
2009 }
2010
2011 ++cindex;
2012 }
2013
2014 /* Current node exhausted, pop back up */
2015 p = NODE_PARENT(tn);
2016 if (p) {
2017 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2018 tn = p;
2019 --iter->depth;
2020 goto rescan;
2021 }
2022
2023 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002024 return NULL;
2025}
2026
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002027static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
2028 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002029{
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002030 struct node *n ;
2031
2032 if(!t)
2033 return NULL;
2034
2035 n = rcu_dereference(t->trie);
2036
2037 if(!iter)
2038 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002039
2040 if (n && IS_TNODE(n)) {
2041 iter->tnode = (struct tnode *) n;
2042 iter->trie = t;
2043 iter->index = 0;
Robert Olsson1d25cd62005-09-19 15:29:52 -07002044 iter->depth = 1;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002045 return n;
2046 }
Robert Olsson19baf832005-06-21 12:43:18 -07002047 return NULL;
2048}
2049
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002050static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002051{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002052 struct node *n;
2053 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002054
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002055 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002056
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002057 rcu_read_lock();
2058 for (n = fib_trie_get_first(&iter, t); n;
2059 n = fib_trie_get_next(&iter)) {
2060 if (IS_LEAF(n)) {
2061 s->leaves++;
2062 s->totdepth += iter.depth;
2063 if (iter.depth > s->maxdepth)
2064 s->maxdepth = iter.depth;
2065 } else {
2066 const struct tnode *tn = (const struct tnode *) n;
2067 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002068
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002069 s->tnodes++;
Robert Olsson06ef9212006-03-20 21:35:01 -08002070 if(tn->bits < MAX_STAT_DEPTH)
2071 s->nodesizes[tn->bits]++;
2072
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002073 for (i = 0; i < (1<<tn->bits); i++)
2074 if (!tn->child[i])
2075 s->nullpointers++;
2076 }
2077 }
2078 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002079}
2080
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002081/*
Robert Olsson19baf832005-06-21 12:43:18 -07002082 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002083 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002084static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002085{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002086 unsigned i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002087
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002088 if (stat->leaves)
2089 avdepth = stat->totdepth*100 / stat->leaves;
2090 else
2091 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002092
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002093 seq_printf(seq, "\tAver depth: %d.%02d\n", avdepth / 100, avdepth % 100 );
2094 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002095
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002096 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Olof Johansson91b9a272005-08-09 20:24:39 -07002097
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002098 bytes = sizeof(struct leaf) * stat->leaves;
2099 seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
2100 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002101
Robert Olsson06ef9212006-03-20 21:35:01 -08002102 max = MAX_STAT_DEPTH;
2103 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002104 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002105
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002106 pointers = 0;
2107 for (i = 1; i <= max; i++)
2108 if (stat->nodesizes[i] != 0) {
2109 seq_printf(seq, " %d: %d", i, stat->nodesizes[i]);
2110 pointers += (1<<i) * stat->nodesizes[i];
2111 }
2112 seq_putc(seq, '\n');
2113 seq_printf(seq, "\tPointers: %d\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002114
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002115 bytes += sizeof(struct node *) * pointers;
2116 seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
2117 seq_printf(seq, "Total size: %d kB\n", (bytes + 1023) / 1024);
Robert Olsson19baf832005-06-21 12:43:18 -07002118
2119#ifdef CONFIG_IP_FIB_TRIE_STATS
2120 seq_printf(seq, "Counters:\n---------\n");
2121 seq_printf(seq,"gets = %d\n", t->stats.gets);
2122 seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
2123 seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
2124 seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
2125 seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
Robert Olsson2f368952005-07-05 15:02:40 -07002126 seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002127#ifdef CLEAR_STATS
2128 memset(&(t->stats), 0, sizeof(t->stats));
2129#endif
2130#endif /* CONFIG_IP_FIB_TRIE_STATS */
2131}
2132
2133static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2134{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002135 struct trie_stat *stat;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002136
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002137 stat = kmalloc(sizeof(*stat), GFP_KERNEL);
2138 if (!stat)
2139 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002140
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002141 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2142 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002143
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002144 if (trie_local) {
2145 seq_printf(seq, "Local:\n");
2146 trie_collect_stats(trie_local, stat);
2147 trie_show_stats(seq, stat);
Robert Olsson19baf832005-06-21 12:43:18 -07002148 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002149
2150 if (trie_main) {
2151 seq_printf(seq, "Main:\n");
2152 trie_collect_stats(trie_main, stat);
2153 trie_show_stats(seq, stat);
2154 }
2155 kfree(stat);
2156
Robert Olsson19baf832005-06-21 12:43:18 -07002157 return 0;
2158}
2159
Robert Olsson19baf832005-06-21 12:43:18 -07002160static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2161{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002162 return single_open(file, fib_triestat_seq_show, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07002163}
2164
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002165static struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002166 .owner = THIS_MODULE,
2167 .open = fib_triestat_seq_open,
2168 .read = seq_read,
2169 .llseek = seq_lseek,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002170 .release = single_release,
Robert Olsson19baf832005-06-21 12:43:18 -07002171};
2172
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002173static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
2174 loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002175{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002176 loff_t idx = 0;
2177 struct node *n;
Robert Olsson19baf832005-06-21 12:43:18 -07002178
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002179 for (n = fib_trie_get_first(iter, trie_local);
2180 n; ++idx, n = fib_trie_get_next(iter)) {
2181 if (pos == idx)
2182 return n;
2183 }
Robert Olsson19baf832005-06-21 12:43:18 -07002184
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002185 for (n = fib_trie_get_first(iter, trie_main);
2186 n; ++idx, n = fib_trie_get_next(iter)) {
2187 if (pos == idx)
2188 return n;
2189 }
Robert Olsson19baf832005-06-21 12:43:18 -07002190 return NULL;
2191}
2192
2193static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2194{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002195 rcu_read_lock();
2196 if (*pos == 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07002197 return SEQ_START_TOKEN;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002198 return fib_trie_get_idx(seq->private, *pos - 1);
Robert Olsson19baf832005-06-21 12:43:18 -07002199}
2200
2201static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2202{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002203 struct fib_trie_iter *iter = seq->private;
2204 void *l = v;
2205
Robert Olsson19baf832005-06-21 12:43:18 -07002206 ++*pos;
Olof Johansson91b9a272005-08-09 20:24:39 -07002207 if (v == SEQ_START_TOKEN)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002208 return fib_trie_get_idx(iter, 0);
Olof Johansson91b9a272005-08-09 20:24:39 -07002209
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002210 v = fib_trie_get_next(iter);
2211 BUG_ON(v == l);
2212 if (v)
2213 return v;
2214
2215 /* continue scan in next trie */
2216 if (iter->trie == trie_local)
2217 return fib_trie_get_first(iter, trie_main);
2218
2219 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07002220}
2221
2222static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2223{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002224 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002225}
2226
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002227static void seq_indent(struct seq_file *seq, int n)
2228{
2229 while (n-- > 0) seq_puts(seq, " ");
2230}
Robert Olsson19baf832005-06-21 12:43:18 -07002231
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002232static inline const char *rtn_scope(enum rt_scope_t s)
2233{
2234 static char buf[32];
2235
2236 switch(s) {
2237 case RT_SCOPE_UNIVERSE: return "universe";
2238 case RT_SCOPE_SITE: return "site";
2239 case RT_SCOPE_LINK: return "link";
2240 case RT_SCOPE_HOST: return "host";
2241 case RT_SCOPE_NOWHERE: return "nowhere";
2242 default:
2243 snprintf(buf, sizeof(buf), "scope=%d", s);
2244 return buf;
2245 }
2246}
2247
2248static const char *rtn_type_names[__RTN_MAX] = {
2249 [RTN_UNSPEC] = "UNSPEC",
2250 [RTN_UNICAST] = "UNICAST",
2251 [RTN_LOCAL] = "LOCAL",
2252 [RTN_BROADCAST] = "BROADCAST",
2253 [RTN_ANYCAST] = "ANYCAST",
2254 [RTN_MULTICAST] = "MULTICAST",
2255 [RTN_BLACKHOLE] = "BLACKHOLE",
2256 [RTN_UNREACHABLE] = "UNREACHABLE",
2257 [RTN_PROHIBIT] = "PROHIBIT",
2258 [RTN_THROW] = "THROW",
2259 [RTN_NAT] = "NAT",
2260 [RTN_XRESOLVE] = "XRESOLVE",
2261};
2262
2263static inline const char *rtn_type(unsigned t)
2264{
2265 static char buf[32];
2266
2267 if (t < __RTN_MAX && rtn_type_names[t])
2268 return rtn_type_names[t];
2269 snprintf(buf, sizeof(buf), "type %d", t);
2270 return buf;
2271}
2272
2273/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002274static int fib_trie_seq_show(struct seq_file *seq, void *v)
2275{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002276 const struct fib_trie_iter *iter = seq->private;
2277 struct node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002278
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002279 if (v == SEQ_START_TOKEN)
2280 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002281
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002282 if (IS_TNODE(n)) {
2283 struct tnode *tn = (struct tnode *) n;
Al Viro32ab5f82006-09-26 22:21:45 -07002284 __be32 prf = htonl(MASK_PFX(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002285
2286 if (!NODE_PARENT(n)) {
2287 if (iter->trie == trie_local)
2288 seq_puts(seq, "<local>:\n");
2289 else
2290 seq_puts(seq, "<main>:\n");
Robert Olsson1d25cd62005-09-19 15:29:52 -07002291 }
2292 seq_indent(seq, iter->depth-1);
2293 seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
2294 NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
2295 tn->empty_children);
2296
Olof Johansson91b9a272005-08-09 20:24:39 -07002297 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002298 struct leaf *l = (struct leaf *) n;
2299 int i;
Al Viro32ab5f82006-09-26 22:21:45 -07002300 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002301
2302 seq_indent(seq, iter->depth);
2303 seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
2304 for (i = 32; i >= 0; i--) {
Robert Olsson772cb712005-09-19 15:31:18 -07002305 struct leaf_info *li = find_leaf_info(l, i);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002306 if (li) {
2307 struct fib_alias *fa;
2308 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2309 seq_indent(seq, iter->depth+1);
2310 seq_printf(seq, " /%d %s %s", i,
2311 rtn_scope(fa->fa_scope),
2312 rtn_type(fa->fa_type));
2313 if (fa->fa_tos)
2314 seq_printf(seq, "tos =%d\n",
2315 fa->fa_tos);
2316 seq_putc(seq, '\n');
2317 }
2318 }
2319 }
Robert Olsson19baf832005-06-21 12:43:18 -07002320 }
2321
2322 return 0;
2323}
2324
2325static struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002326 .start = fib_trie_seq_start,
2327 .next = fib_trie_seq_next,
2328 .stop = fib_trie_seq_stop,
2329 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002330};
2331
2332static int fib_trie_seq_open(struct inode *inode, struct file *file)
2333{
2334 struct seq_file *seq;
2335 int rc = -ENOMEM;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002336 struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2337
2338 if (!s)
2339 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07002340
2341 rc = seq_open(file, &fib_trie_seq_ops);
2342 if (rc)
2343 goto out_kfree;
2344
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002345 seq = file->private_data;
2346 seq->private = s;
2347 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002348out:
2349 return rc;
2350out_kfree:
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002351 kfree(s);
Robert Olsson19baf832005-06-21 12:43:18 -07002352 goto out;
2353}
2354
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002355static struct file_operations fib_trie_fops = {
2356 .owner = THIS_MODULE,
2357 .open = fib_trie_seq_open,
2358 .read = seq_read,
2359 .llseek = seq_lseek,
2360 .release = seq_release_private,
2361};
2362
Al Viro32ab5f82006-09-26 22:21:45 -07002363static unsigned fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002364{
2365 static unsigned type2flags[RTN_MAX + 1] = {
2366 [7] = RTF_REJECT, [8] = RTF_REJECT,
2367 };
2368 unsigned flags = type2flags[type];
2369
2370 if (fi && fi->fib_nh->nh_gw)
2371 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002372 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002373 flags |= RTF_HOST;
2374 flags |= RTF_UP;
2375 return flags;
2376}
2377
2378/*
2379 * This outputs /proc/net/route.
2380 * The format of the file is not supposed to be changed
2381 * and needs to be same as fib_hash output to avoid breaking
2382 * legacy utilities
2383 */
2384static int fib_route_seq_show(struct seq_file *seq, void *v)
2385{
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002386 const struct fib_trie_iter *iter = seq->private;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002387 struct leaf *l = v;
2388 int i;
2389 char bf[128];
2390
2391 if (v == SEQ_START_TOKEN) {
2392 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2393 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2394 "\tWindow\tIRTT");
2395 return 0;
2396 }
2397
Patrick McHardyc9e53cb2005-11-20 21:09:00 -08002398 if (iter->trie == trie_local)
2399 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002400 if (IS_TNODE(l))
2401 return 0;
2402
2403 for (i=32; i>=0; i--) {
Robert Olsson772cb712005-09-19 15:31:18 -07002404 struct leaf_info *li = find_leaf_info(l, i);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002405 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002406 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002407
2408 if (!li)
2409 continue;
2410
2411 mask = inet_make_mask(li->plen);
2412 prefix = htonl(l->key);
2413
2414 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002415 const struct fib_info *fi = fa->fa_info;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002416 unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
2417
2418 if (fa->fa_type == RTN_BROADCAST
2419 || fa->fa_type == RTN_MULTICAST)
2420 continue;
2421
2422 if (fi)
2423 snprintf(bf, sizeof(bf),
2424 "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2425 fi->fib_dev ? fi->fib_dev->name : "*",
2426 prefix,
2427 fi->fib_nh->nh_gw, flags, 0, 0,
2428 fi->fib_priority,
2429 mask,
2430 (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
2431 fi->fib_window,
2432 fi->fib_rtt >> 3);
2433 else
2434 snprintf(bf, sizeof(bf),
2435 "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
2436 prefix, 0, flags, 0, 0, 0,
2437 mask, 0, 0, 0);
2438
2439 seq_printf(seq, "%-127s\n", bf);
2440 }
2441 }
2442
2443 return 0;
2444}
2445
2446static struct seq_operations fib_route_seq_ops = {
2447 .start = fib_trie_seq_start,
2448 .next = fib_trie_seq_next,
2449 .stop = fib_trie_seq_stop,
2450 .show = fib_route_seq_show,
2451};
2452
2453static int fib_route_seq_open(struct inode *inode, struct file *file)
2454{
2455 struct seq_file *seq;
2456 int rc = -ENOMEM;
2457 struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
2458
2459 if (!s)
2460 goto out;
2461
2462 rc = seq_open(file, &fib_route_seq_ops);
2463 if (rc)
2464 goto out_kfree;
2465
2466 seq = file->private_data;
2467 seq->private = s;
2468 memset(s, 0, sizeof(*s));
2469out:
2470 return rc;
2471out_kfree:
2472 kfree(s);
2473 goto out;
2474}
2475
2476static struct file_operations fib_route_fops = {
2477 .owner = THIS_MODULE,
2478 .open = fib_route_seq_open,
2479 .read = seq_read,
2480 .llseek = seq_lseek,
2481 .release = seq_release_private,
Robert Olsson19baf832005-06-21 12:43:18 -07002482};
2483
2484int __init fib_proc_init(void)
2485{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002486 if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops))
2487 goto out1;
2488
2489 if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops))
2490 goto out2;
2491
2492 if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops))
2493 goto out3;
2494
Robert Olsson19baf832005-06-21 12:43:18 -07002495 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002496
2497out3:
2498 proc_net_remove("fib_triestat");
2499out2:
2500 proc_net_remove("fib_trie");
2501out1:
2502 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002503}
2504
2505void __init fib_proc_exit(void)
2506{
2507 proc_net_remove("fib_trie");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002508 proc_net_remove("fib_triestat");
2509 proc_net_remove("route");
Robert Olsson19baf832005-06-21 12:43:18 -07002510}
2511
2512#endif /* CONFIG_PROC_FS */