blob: 61e03da3e1f59cf02e6502150a8497b5c3b770fc [file] [log] [blame]
Robert Olsson19baf832005-06-21 12:43:18 -07001/*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
6 *
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
9 *
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090010 * Jens Laas <jens.laas@data.slu.se> Swedish University of
Robert Olsson19baf832005-06-21 12:43:18 -070011 * Agricultural Sciences.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090012 *
Robert Olsson19baf832005-06-21 12:43:18 -070013 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
14 *
Lucas De Marchi25985ed2011-03-30 22:57:33 -030015 * This work is based on the LPC-trie which is originally described in:
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +090016 *
Robert Olsson19baf832005-06-21 12:43:18 -070017 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
Justin P. Mattock631dd1a2010-10-18 11:03:14 +020019 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
Robert Olsson19baf832005-06-21 12:43:18 -070020 *
21 *
22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
24 *
Robert Olsson19baf832005-06-21 12:43:18 -070025 *
26 * Code from fib_hash has been reused which includes the following header:
27 *
28 *
29 * INET An implementation of the TCP/IP protocol suite for the LINUX
30 * operating system. INET is implemented using the BSD Socket
31 * interface as the means of communication with the user level.
32 *
33 * IPv4 FIB: lookup engine and maintenance routines.
34 *
35 *
36 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
37 *
38 * This program is free software; you can redistribute it and/or
39 * modify it under the terms of the GNU General Public License
40 * as published by the Free Software Foundation; either version
41 * 2 of the License, or (at your option) any later version.
Robert Olssonfd966252005-12-22 11:25:10 -080042 *
43 * Substantial contributions to this work comes from:
44 *
45 * David S. Miller, <davem@davemloft.net>
46 * Stephen Hemminger <shemminger@osdl.org>
47 * Paul E. McKenney <paulmck@us.ibm.com>
48 * Patrick McHardy <kaber@trash.net>
Robert Olsson19baf832005-06-21 12:43:18 -070049 */
50
Jens Låås80b71b82009-08-28 23:57:15 -070051#define VERSION "0.409"
Robert Olsson19baf832005-06-21 12:43:18 -070052
Robert Olsson19baf832005-06-21 12:43:18 -070053#include <asm/uaccess.h>
Jiri Slaby1977f032007-10-18 23:40:25 -070054#include <linux/bitops.h>
Robert Olsson19baf832005-06-21 12:43:18 -070055#include <linux/types.h>
56#include <linux/kernel.h>
Robert Olsson19baf832005-06-21 12:43:18 -070057#include <linux/mm.h>
58#include <linux/string.h>
59#include <linux/socket.h>
60#include <linux/sockios.h>
61#include <linux/errno.h>
62#include <linux/in.h>
63#include <linux/inet.h>
Stephen Hemmingercd8787a2006-01-03 14:38:34 -080064#include <linux/inetdevice.h>
Robert Olsson19baf832005-06-21 12:43:18 -070065#include <linux/netdevice.h>
66#include <linux/if_arp.h>
67#include <linux/proc_fs.h>
Robert Olsson2373ce12005-08-25 13:01:29 -070068#include <linux/rcupdate.h>
Robert Olsson19baf832005-06-21 12:43:18 -070069#include <linux/skbuff.h>
70#include <linux/netlink.h>
71#include <linux/init.h>
72#include <linux/list.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090073#include <linux/slab.h>
Paul Gortmaker70c71602011-05-22 16:47:17 -040074#include <linux/prefetch.h>
Paul Gortmakerbc3b2d72011-07-15 11:47:34 -040075#include <linux/export.h>
Eric W. Biederman457c4cb2007-09-12 12:01:34 +020076#include <net/net_namespace.h>
Robert Olsson19baf832005-06-21 12:43:18 -070077#include <net/ip.h>
78#include <net/protocol.h>
79#include <net/route.h>
80#include <net/tcp.h>
81#include <net/sock.h>
82#include <net/ip_fib.h>
83#include "fib_lookup.h"
84
Robert Olsson06ef9212006-03-20 21:35:01 -080085#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070086
Robert Olsson19baf832005-06-21 12:43:18 -070087#define KEYLENGTH (8*sizeof(t_key))
Robert Olsson19baf832005-06-21 12:43:18 -070088
Robert Olsson19baf832005-06-21 12:43:18 -070089typedef unsigned int t_key;
90
91#define T_TNODE 0
92#define T_LEAF 1
93#define NODE_TYPE_MASK 0x1UL
Robert Olsson2373ce12005-08-25 13:01:29 -070094#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
95
Olof Johansson91b9a272005-08-09 20:24:39 -070096#define IS_TNODE(n) (!(n->parent & T_LEAF))
97#define IS_LEAF(n) (n->parent & T_LEAF)
Robert Olsson19baf832005-06-21 12:43:18 -070098
David S. Millerb299e4f2011-02-02 20:48:10 -080099struct rt_trie_node {
Olof Johansson91b9a272005-08-09 20:24:39 -0700100 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800101 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700102};
103
104struct leaf {
Olof Johansson91b9a272005-08-09 20:24:39 -0700105 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800106 t_key key;
Robert Olsson19baf832005-06-21 12:43:18 -0700107 struct hlist_head list;
Robert Olsson2373ce12005-08-25 13:01:29 -0700108 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700109};
110
111struct leaf_info {
112 struct hlist_node hlist;
113 int plen;
Eric Dumazet5c745012011-07-18 03:16:33 +0000114 u32 mask_plen; /* ntohl(inet_make_mask(plen)) */
Robert Olsson19baf832005-06-21 12:43:18 -0700115 struct list_head falh;
Eric Dumazet5c745012011-07-18 03:16:33 +0000116 struct rcu_head rcu;
Robert Olsson19baf832005-06-21 12:43:18 -0700117};
118
119struct tnode {
Olof Johansson91b9a272005-08-09 20:24:39 -0700120 unsigned long parent;
Eric Dumazet8d965442008-01-13 22:31:44 -0800121 t_key key;
Eric Dumazet112d8cf2008-01-12 21:27:41 -0800122 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
123 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
Eric Dumazet8d965442008-01-13 22:31:44 -0800124 unsigned int full_children; /* KEYLENGTH bits needed */
125 unsigned int empty_children; /* KEYLENGTH bits needed */
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700126 union {
127 struct rcu_head rcu;
128 struct work_struct work;
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700129 struct tnode *tnode_free;
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700130 };
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700131 struct rt_trie_node __rcu *child[0];
Robert Olsson19baf832005-06-21 12:43:18 -0700132};
133
134#ifdef CONFIG_IP_FIB_TRIE_STATS
135struct trie_use_stats {
136 unsigned int gets;
137 unsigned int backtrack;
138 unsigned int semantic_match_passed;
139 unsigned int semantic_match_miss;
140 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700141 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700142};
143#endif
144
145struct trie_stat {
146 unsigned int totdepth;
147 unsigned int maxdepth;
148 unsigned int tnodes;
149 unsigned int leaves;
150 unsigned int nullpointers;
Stephen Hemminger93672292008-01-22 21:54:05 -0800151 unsigned int prefixes;
Robert Olsson06ef9212006-03-20 21:35:01 -0800152 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700153};
Robert Olsson19baf832005-06-21 12:43:18 -0700154
155struct trie {
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700156 struct rt_trie_node __rcu *trie;
Robert Olsson19baf832005-06-21 12:43:18 -0700157#ifdef CONFIG_IP_FIB_TRIE_STATS
158 struct trie_use_stats stats;
159#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700160};
161
David S. Millerb299e4f2011-02-02 20:48:10 -0800162static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800163 int wasfull);
David S. Millerb299e4f2011-02-02 20:48:10 -0800164static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700165static struct tnode *inflate(struct trie *t, struct tnode *tn);
166static struct tnode *halve(struct trie *t, struct tnode *tn);
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700167/* tnodes to free after resize(); protected by RTNL */
168static struct tnode *tnode_free_head;
Jarek Poplawskic3059472009-07-14 08:33:08 +0000169static size_t tnode_free_size;
170
171/*
172 * synchronize_rcu after call_rcu for that many pages; it should be especially
173 * useful before resizing the root node with PREEMPT_NONE configs; the value was
174 * obtained experimentally, aiming to avoid visible slowdown.
175 */
176static const int sync_pages = 128;
Robert Olsson19baf832005-06-21 12:43:18 -0700177
Christoph Lametere18b8902006-12-06 20:33:20 -0800178static struct kmem_cache *fn_alias_kmem __read_mostly;
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800179static struct kmem_cache *trie_leaf_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700180
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700181/*
182 * caller must hold RTNL
183 */
184static inline struct tnode *node_parent(const struct rt_trie_node *node)
Stephen Hemminger06801912007-08-10 15:22:13 -0700185{
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700186 unsigned long parent;
187
188 parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
189
190 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800191}
Stephen Hemminger06801912007-08-10 15:22:13 -0700192
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700193/*
194 * caller must hold RCU read lock or RTNL
195 */
196static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800197{
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700198 unsigned long parent;
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800199
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700200 parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
201 lockdep_rtnl_is_held());
202
203 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
Stephen Hemminger06801912007-08-10 15:22:13 -0700204}
205
Eric Dumazetcf778b02012-01-12 04:41:32 +0000206/* Same as rcu_assign_pointer
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700207 * but that macro() assumes that value is a pointer.
208 */
David S. Millerb299e4f2011-02-02 20:48:10 -0800209static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
Stephen Hemminger06801912007-08-10 15:22:13 -0700210{
Stephen Hemminger6440cc92008-03-22 17:59:58 -0700211 smp_wmb();
212 node->parent = (unsigned long)ptr | NODE_TYPE(node);
Stephen Hemminger06801912007-08-10 15:22:13 -0700213}
Robert Olsson2373ce12005-08-25 13:01:29 -0700214
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700215/*
216 * caller must hold RTNL
217 */
218static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
Robert Olsson19baf832005-06-21 12:43:18 -0700219{
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800220 BUG_ON(i >= 1U << tn->bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700221
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700222 return rtnl_dereference(tn->child[i]);
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800223}
224
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700225/*
226 * caller must hold RCU read lock or RTNL
227 */
228static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800229{
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700230 BUG_ON(i >= 1U << tn->bits);
Eric Dumazetb59cfbf2008-01-18 03:31:36 -0800231
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700232 return rcu_dereference_rtnl(tn->child[i]);
Robert Olsson19baf832005-06-21 12:43:18 -0700233}
234
Stephen Hemmignerbb435b82005-08-09 20:25:39 -0700235static inline int tnode_child_length(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700236{
Olof Johansson91b9a272005-08-09 20:24:39 -0700237 return 1 << tn->bits;
Robert Olsson19baf832005-06-21 12:43:18 -0700238}
239
David S. Miller3b004562011-02-16 14:56:22 -0800240static inline t_key mask_pfx(t_key k, unsigned int l)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700241{
242 return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
243}
244
David S. Miller3b004562011-02-16 14:56:22 -0800245static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700246{
Olof Johansson91b9a272005-08-09 20:24:39 -0700247 if (offset < KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -0700248 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
Olof Johansson91b9a272005-08-09 20:24:39 -0700249 else
Robert Olsson19baf832005-06-21 12:43:18 -0700250 return 0;
251}
252
253static inline int tkey_equals(t_key a, t_key b)
254{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700255 return a == b;
Robert Olsson19baf832005-06-21 12:43:18 -0700256}
257
258static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
259{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700260 if (bits == 0 || offset >= KEYLENGTH)
261 return 1;
Olof Johansson91b9a272005-08-09 20:24:39 -0700262 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
263 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700264}
Robert Olsson19baf832005-06-21 12:43:18 -0700265
266static inline int tkey_mismatch(t_key a, int offset, t_key b)
267{
268 t_key diff = a ^ b;
269 int i = offset;
270
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700271 if (!diff)
272 return 0;
273 while ((diff << i) >> (KEYLENGTH-1) == 0)
Robert Olsson19baf832005-06-21 12:43:18 -0700274 i++;
275 return i;
276}
277
Robert Olsson19baf832005-06-21 12:43:18 -0700278/*
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900279 To understand this stuff, an understanding of keys and all their bits is
280 necessary. Every node in the trie has a key associated with it, but not
Robert Olsson19baf832005-06-21 12:43:18 -0700281 all of the bits in that key are significant.
282
283 Consider a node 'n' and its parent 'tp'.
284
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900285 If n is a leaf, every bit in its key is significant. Its presence is
286 necessitated by path compression, since during a tree traversal (when
287 searching for a leaf - unless we are doing an insertion) we will completely
288 ignore all skipped bits we encounter. Thus we need to verify, at the end of
289 a potentially successful search, that we have indeed been walking the
Robert Olsson19baf832005-06-21 12:43:18 -0700290 correct key path.
291
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900292 Note that we can never "miss" the correct key in the tree if present by
293 following the wrong path. Path compression ensures that segments of the key
294 that are the same for all keys with a given prefix are skipped, but the
295 skipped part *is* identical for each node in the subtrie below the skipped
296 bit! trie_insert() in this implementation takes care of that - note the
Robert Olsson19baf832005-06-21 12:43:18 -0700297 call to tkey_sub_equals() in trie_insert().
298
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900299 if n is an internal node - a 'tnode' here, the various parts of its key
Robert Olsson19baf832005-06-21 12:43:18 -0700300 have many different meanings.
301
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900302 Example:
Robert Olsson19baf832005-06-21 12:43:18 -0700303 _________________________________________________________________
304 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
305 -----------------------------------------------------------------
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900306 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Robert Olsson19baf832005-06-21 12:43:18 -0700307
308 _________________________________________________________________
309 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
310 -----------------------------------------------------------------
311 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
312
313 tp->pos = 7
314 tp->bits = 3
315 n->pos = 15
Olof Johansson91b9a272005-08-09 20:24:39 -0700316 n->bits = 4
Robert Olsson19baf832005-06-21 12:43:18 -0700317
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900318 First, let's just ignore the bits that come before the parent tp, that is
319 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
Robert Olsson19baf832005-06-21 12:43:18 -0700320 not use them for anything.
321
322 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900323 index into the parent's child array. That is, they will be used to find
Robert Olsson19baf832005-06-21 12:43:18 -0700324 'n' among tp's children.
325
326 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
327 for the node n.
328
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900329 All the bits we have seen so far are significant to the node n. The rest
Robert Olsson19baf832005-06-21 12:43:18 -0700330 of the bits are really not needed or indeed known in n->key.
331
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900332 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
Robert Olsson19baf832005-06-21 12:43:18 -0700333 n's child array, and will of course be different for each child.
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900334
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700335
Robert Olsson19baf832005-06-21 12:43:18 -0700336 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
337 at this point.
338
339*/
340
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700341static inline void check_tnode(const struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700342{
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700343 WARN_ON(tn && tn->pos+tn->bits > 32);
Robert Olsson19baf832005-06-21 12:43:18 -0700344}
345
Denis V. Lunevf5026fa2007-12-13 09:47:57 -0800346static const int halve_threshold = 25;
347static const int inflate_threshold = 50;
Jarek Poplawski345aa032009-07-07 19:39:16 -0700348static const int halve_threshold_root = 15;
Jens Låås80b71b82009-08-28 23:57:15 -0700349static const int inflate_threshold_root = 30;
Robert Olsson2373ce12005-08-25 13:01:29 -0700350
351static void __alias_free_mem(struct rcu_head *head)
352{
353 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
354 kmem_cache_free(fn_alias_kmem, fa);
355}
356
357static inline void alias_free_mem_rcu(struct fib_alias *fa)
358{
359 call_rcu(&fa->rcu, __alias_free_mem);
360}
361
362static void __leaf_free_rcu(struct rcu_head *head)
363{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800364 struct leaf *l = container_of(head, struct leaf, rcu);
365 kmem_cache_free(trie_leaf_kmem, l);
Robert Olsson2373ce12005-08-25 13:01:29 -0700366}
367
Stephen Hemminger387a5482008-04-10 03:47:34 -0700368static inline void free_leaf(struct leaf *l)
369{
Eric Dumazet0c03eca2012-08-07 00:47:11 +0000370 call_rcu(&l->rcu, __leaf_free_rcu);
Stephen Hemminger387a5482008-04-10 03:47:34 -0700371}
372
Robert Olsson2373ce12005-08-25 13:01:29 -0700373static inline void free_leaf_info(struct leaf_info *leaf)
374{
Lai Jiangshanbceb0f42011-03-18 11:42:34 +0800375 kfree_rcu(leaf, rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700376}
377
Eric Dumazet8d965442008-01-13 22:31:44 -0800378static struct tnode *tnode_alloc(size_t size)
Robert Olsson2373ce12005-08-25 13:01:29 -0700379{
Robert Olsson2373ce12005-08-25 13:01:29 -0700380 if (size <= PAGE_SIZE)
Eric Dumazet8d965442008-01-13 22:31:44 -0800381 return kzalloc(size, GFP_KERNEL);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700382 else
Eric Dumazet7a1c8e52010-11-20 07:46:35 +0000383 return vzalloc(size);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700384}
Robert Olsson2373ce12005-08-25 13:01:29 -0700385
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700386static void __tnode_vfree(struct work_struct *arg)
387{
388 struct tnode *tn = container_of(arg, struct tnode, work);
389 vfree(tn);
Robert Olsson2373ce12005-08-25 13:01:29 -0700390}
391
392static void __tnode_free_rcu(struct rcu_head *head)
393{
394 struct tnode *tn = container_of(head, struct tnode, rcu);
Eric Dumazet8d965442008-01-13 22:31:44 -0800395 size_t size = sizeof(struct tnode) +
David S. Millerb299e4f2011-02-02 20:48:10 -0800396 (sizeof(struct rt_trie_node *) << tn->bits);
Robert Olsson2373ce12005-08-25 13:01:29 -0700397
398 if (size <= PAGE_SIZE)
399 kfree(tn);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700400 else {
401 INIT_WORK(&tn->work, __tnode_vfree);
402 schedule_work(&tn->work);
403 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700404}
405
406static inline void tnode_free(struct tnode *tn)
407{
Stephen Hemminger387a5482008-04-10 03:47:34 -0700408 if (IS_LEAF(tn))
409 free_leaf((struct leaf *) tn);
410 else
Robert Olsson550e29b2006-04-04 12:53:35 -0700411 call_rcu(&tn->rcu, __tnode_free_rcu);
Robert Olsson2373ce12005-08-25 13:01:29 -0700412}
413
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700414static void tnode_free_safe(struct tnode *tn)
415{
416 BUG_ON(IS_LEAF(tn));
Jarek Poplawski7b855762009-06-18 00:28:51 -0700417 tn->tnode_free = tnode_free_head;
418 tnode_free_head = tn;
Jarek Poplawskic3059472009-07-14 08:33:08 +0000419 tnode_free_size += sizeof(struct tnode) +
David S. Millerb299e4f2011-02-02 20:48:10 -0800420 (sizeof(struct rt_trie_node *) << tn->bits);
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700421}
422
423static void tnode_free_flush(void)
424{
425 struct tnode *tn;
426
427 while ((tn = tnode_free_head)) {
428 tnode_free_head = tn->tnode_free;
429 tn->tnode_free = NULL;
430 tnode_free(tn);
431 }
Jarek Poplawskic3059472009-07-14 08:33:08 +0000432
433 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
434 tnode_free_size = 0;
435 synchronize_rcu();
436 }
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700437}
438
Robert Olsson19baf832005-06-21 12:43:18 -0700439static struct leaf *leaf_new(void)
440{
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800441 struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700442 if (l) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700443 l->parent = T_LEAF;
Robert Olsson19baf832005-06-21 12:43:18 -0700444 INIT_HLIST_HEAD(&l->list);
445 }
446 return l;
447}
448
449static struct leaf_info *leaf_info_new(int plen)
450{
451 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -0700452 if (li) {
453 li->plen = plen;
Eric Dumazet5c745012011-07-18 03:16:33 +0000454 li->mask_plen = ntohl(inet_make_mask(plen));
Robert Olsson2373ce12005-08-25 13:01:29 -0700455 INIT_LIST_HEAD(&li->falh);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700456 }
Robert Olsson2373ce12005-08-25 13:01:29 -0700457 return li;
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700458}
459
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800460static struct tnode *tnode_new(t_key key, int pos, int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700461{
David S. Millerb299e4f2011-02-02 20:48:10 -0800462 size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
Patrick McHardyf0e36f82005-07-05 14:44:55 -0700463 struct tnode *tn = tnode_alloc(sz);
Robert Olsson19baf832005-06-21 12:43:18 -0700464
Olof Johansson91b9a272005-08-09 20:24:39 -0700465 if (tn) {
Robert Olsson2373ce12005-08-25 13:01:29 -0700466 tn->parent = T_TNODE;
Robert Olsson19baf832005-06-21 12:43:18 -0700467 tn->pos = pos;
468 tn->bits = bits;
469 tn->key = key;
470 tn->full_children = 0;
471 tn->empty_children = 1<<bits;
472 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700473
Eric Dumazeta034ee32010-09-09 23:32:28 +0000474 pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
Lin Ming4ea4bf72012-07-29 01:19:55 +0000475 sizeof(struct rt_trie_node *) << bits);
Robert Olsson19baf832005-06-21 12:43:18 -0700476 return tn;
477}
478
Robert Olsson19baf832005-06-21 12:43:18 -0700479/*
480 * Check whether a tnode 'n' is "full", i.e. it is an internal node
481 * and no bits are skipped. See discussion in dyntree paper p. 6
482 */
483
David S. Millerb299e4f2011-02-02 20:48:10 -0800484static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700485{
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700486 if (n == NULL || IS_LEAF(n))
Robert Olsson19baf832005-06-21 12:43:18 -0700487 return 0;
488
489 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
490}
491
Lin Ming61648d92012-07-29 02:00:03 +0000492static inline void put_child(struct tnode *tn, int i,
David S. Millerb299e4f2011-02-02 20:48:10 -0800493 struct rt_trie_node *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700494{
495 tnode_put_child_reorg(tn, i, n, -1);
496}
497
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700498 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700499 * Add a child at position i overwriting the old value.
500 * Update the value of full_children and empty_children.
501 */
502
David S. Millerb299e4f2011-02-02 20:48:10 -0800503static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800504 int wasfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700505{
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700506 struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
Robert Olsson19baf832005-06-21 12:43:18 -0700507 int isfull;
508
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700509 BUG_ON(i >= 1<<tn->bits);
510
Robert Olsson19baf832005-06-21 12:43:18 -0700511 /* update emptyChildren */
512 if (n == NULL && chi != NULL)
513 tn->empty_children++;
514 else if (n != NULL && chi == NULL)
515 tn->empty_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700516
Robert Olsson19baf832005-06-21 12:43:18 -0700517 /* update fullChildren */
Olof Johansson91b9a272005-08-09 20:24:39 -0700518 if (wasfull == -1)
Robert Olsson19baf832005-06-21 12:43:18 -0700519 wasfull = tnode_full(tn, chi);
520
521 isfull = tnode_full(tn, n);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700522 if (wasfull && !isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700523 tn->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700524 else if (!wasfull && isfull)
Robert Olsson19baf832005-06-21 12:43:18 -0700525 tn->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700526
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700527 if (n)
Stephen Hemminger06801912007-08-10 15:22:13 -0700528 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700529
Eric Dumazetcf778b02012-01-12 04:41:32 +0000530 rcu_assign_pointer(tn->child[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700531}
532
Jens Låås80b71b82009-08-28 23:57:15 -0700533#define MAX_WORK 10
David S. Millerb299e4f2011-02-02 20:48:10 -0800534static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700535{
536 int i;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700537 struct tnode *old_tn;
Robert Olssone6308be2005-10-04 13:01:58 -0700538 int inflate_threshold_use;
539 int halve_threshold_use;
Jens Låås80b71b82009-08-28 23:57:15 -0700540 int max_work;
Robert Olsson19baf832005-06-21 12:43:18 -0700541
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900542 if (!tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700543 return NULL;
544
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700545 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
546 tn, inflate_threshold, halve_threshold);
Robert Olsson19baf832005-06-21 12:43:18 -0700547
548 /* No children */
549 if (tn->empty_children == tnode_child_length(tn)) {
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700550 tnode_free_safe(tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700551 return NULL;
552 }
553 /* One child */
554 if (tn->empty_children == tnode_child_length(tn) - 1)
Jens Låås80b71b82009-08-28 23:57:15 -0700555 goto one_child;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700556 /*
Robert Olsson19baf832005-06-21 12:43:18 -0700557 * Double as long as the resulting node has a number of
558 * nonempty nodes that are above the threshold.
559 */
560
561 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700562 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
563 * the Helsinki University of Technology and Matti Tikkanen of Nokia
Robert Olsson19baf832005-06-21 12:43:18 -0700564 * Telecommunications, page 6:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700565 * "A node is doubled if the ratio of non-empty children to all
Robert Olsson19baf832005-06-21 12:43:18 -0700566 * children in the *doubled* node is at least 'high'."
567 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700568 * 'high' in this instance is the variable 'inflate_threshold'. It
569 * is expressed as a percentage, so we multiply it with
570 * tnode_child_length() and instead of multiplying by 2 (since the
571 * child array will be doubled by inflate()) and multiplying
572 * the left-hand side by 100 (to handle the percentage thing) we
Robert Olsson19baf832005-06-21 12:43:18 -0700573 * multiply the left-hand side by 50.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700574 *
575 * The left-hand side may look a bit weird: tnode_child_length(tn)
576 * - tn->empty_children is of course the number of non-null children
577 * in the current node. tn->full_children is the number of "full"
Robert Olsson19baf832005-06-21 12:43:18 -0700578 * children, that is non-null tnodes with a skip value of 0.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700579 * All of those will be doubled in the resulting inflated tnode, so
Robert Olsson19baf832005-06-21 12:43:18 -0700580 * we just count them one extra time here.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700581 *
Robert Olsson19baf832005-06-21 12:43:18 -0700582 * A clearer way to write this would be:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700583 *
Robert Olsson19baf832005-06-21 12:43:18 -0700584 * to_be_doubled = tn->full_children;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700585 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
Robert Olsson19baf832005-06-21 12:43:18 -0700586 * tn->full_children;
587 *
588 * new_child_length = tnode_child_length(tn) * 2;
589 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700590 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
Robert Olsson19baf832005-06-21 12:43:18 -0700591 * new_child_length;
592 * if (new_fill_factor >= inflate_threshold)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700593 *
594 * ...and so on, tho it would mess up the while () loop.
595 *
Robert Olsson19baf832005-06-21 12:43:18 -0700596 * anyway,
597 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
598 * inflate_threshold
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700599 *
Robert Olsson19baf832005-06-21 12:43:18 -0700600 * avoid a division:
601 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
602 * inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700603 *
Robert Olsson19baf832005-06-21 12:43:18 -0700604 * expand not_to_be_doubled and to_be_doubled, and shorten:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700605 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700606 * tn->full_children) >= inflate_threshold * new_child_length
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700607 *
Robert Olsson19baf832005-06-21 12:43:18 -0700608 * expand new_child_length:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700609 * 100 * (tnode_child_length(tn) - tn->empty_children +
Olof Johansson91b9a272005-08-09 20:24:39 -0700610 * tn->full_children) >=
Robert Olsson19baf832005-06-21 12:43:18 -0700611 * inflate_threshold * tnode_child_length(tn) * 2
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700612 *
Robert Olsson19baf832005-06-21 12:43:18 -0700613 * shorten again:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700614 * 50 * (tn->full_children + tnode_child_length(tn) -
Olof Johansson91b9a272005-08-09 20:24:39 -0700615 * tn->empty_children) >= inflate_threshold *
Robert Olsson19baf832005-06-21 12:43:18 -0700616 * tnode_child_length(tn)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700617 *
Robert Olsson19baf832005-06-21 12:43:18 -0700618 */
619
620 check_tnode(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700621
Robert Olssone6308be2005-10-04 13:01:58 -0700622 /* Keep root node larger */
623
David S. Millerb299e4f2011-02-02 20:48:10 -0800624 if (!node_parent((struct rt_trie_node *)tn)) {
Jens Låås80b71b82009-08-28 23:57:15 -0700625 inflate_threshold_use = inflate_threshold_root;
626 halve_threshold_use = halve_threshold_root;
Eric Dumazeta034ee32010-09-09 23:32:28 +0000627 } else {
Robert Olssone6308be2005-10-04 13:01:58 -0700628 inflate_threshold_use = inflate_threshold;
Jens Låås80b71b82009-08-28 23:57:15 -0700629 halve_threshold_use = halve_threshold;
630 }
Robert Olssone6308be2005-10-04 13:01:58 -0700631
Jens Låås80b71b82009-08-28 23:57:15 -0700632 max_work = MAX_WORK;
633 while ((tn->full_children > 0 && max_work-- &&
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800634 50 * (tn->full_children + tnode_child_length(tn)
635 - tn->empty_children)
636 >= inflate_threshold_use * tnode_child_length(tn))) {
Robert Olsson19baf832005-06-21 12:43:18 -0700637
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700638 old_tn = tn;
639 tn = inflate(t, tn);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800640
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700641 if (IS_ERR(tn)) {
642 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700643#ifdef CONFIG_IP_FIB_TRIE_STATS
644 t->stats.resize_node_skipped++;
645#endif
646 break;
647 }
Robert Olsson19baf832005-06-21 12:43:18 -0700648 }
649
650 check_tnode(tn);
651
Jens Låås80b71b82009-08-28 23:57:15 -0700652 /* Return if at least one inflate is run */
Eric Dumazeta034ee32010-09-09 23:32:28 +0000653 if (max_work != MAX_WORK)
David S. Millerb299e4f2011-02-02 20:48:10 -0800654 return (struct rt_trie_node *) tn;
Jens Låås80b71b82009-08-28 23:57:15 -0700655
Robert Olsson19baf832005-06-21 12:43:18 -0700656 /*
657 * Halve as long as the number of empty children in this
658 * node is above threshold.
659 */
Robert Olsson2f368952005-07-05 15:02:40 -0700660
Jens Låås80b71b82009-08-28 23:57:15 -0700661 max_work = MAX_WORK;
662 while (tn->bits > 1 && max_work-- &&
Robert Olsson19baf832005-06-21 12:43:18 -0700663 100 * (tnode_child_length(tn) - tn->empty_children) <
Robert Olssone6308be2005-10-04 13:01:58 -0700664 halve_threshold_use * tnode_child_length(tn)) {
Robert Olsson19baf832005-06-21 12:43:18 -0700665
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700666 old_tn = tn;
667 tn = halve(t, tn);
668 if (IS_ERR(tn)) {
669 tn = old_tn;
Robert Olsson2f368952005-07-05 15:02:40 -0700670#ifdef CONFIG_IP_FIB_TRIE_STATS
671 t->stats.resize_node_skipped++;
672#endif
673 break;
674 }
675 }
676
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700677
Robert Olsson19baf832005-06-21 12:43:18 -0700678 /* Only one child remains */
Jens Låås80b71b82009-08-28 23:57:15 -0700679 if (tn->empty_children == tnode_child_length(tn) - 1) {
680one_child:
Robert Olsson19baf832005-06-21 12:43:18 -0700681 for (i = 0; i < tnode_child_length(tn); i++) {
David S. Millerb299e4f2011-02-02 20:48:10 -0800682 struct rt_trie_node *n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700683
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700684 n = rtnl_dereference(tn->child[i]);
Robert Olsson2373ce12005-08-25 13:01:29 -0700685 if (!n)
Olof Johansson91b9a272005-08-09 20:24:39 -0700686 continue;
Olof Johansson91b9a272005-08-09 20:24:39 -0700687
688 /* compress one level */
689
Stephen Hemminger06801912007-08-10 15:22:13 -0700690 node_set_parent(n, NULL);
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700691 tnode_free_safe(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700692 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700693 }
Jens Låås80b71b82009-08-28 23:57:15 -0700694 }
David S. Millerb299e4f2011-02-02 20:48:10 -0800695 return (struct rt_trie_node *) tn;
Robert Olsson19baf832005-06-21 12:43:18 -0700696}
697
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700698
699static void tnode_clean_free(struct tnode *tn)
700{
701 int i;
702 struct tnode *tofree;
703
704 for (i = 0; i < tnode_child_length(tn); i++) {
705 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
706 if (tofree)
707 tnode_free(tofree);
708 }
709 tnode_free(tn);
710}
711
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700712static struct tnode *inflate(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700713{
Robert Olsson19baf832005-06-21 12:43:18 -0700714 struct tnode *oldtnode = tn;
715 int olen = tnode_child_length(tn);
716 int i;
717
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700718 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700719
720 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
721
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700722 if (!tn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700723 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700724
725 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700726 * Preallocate and store tnodes before the actual work so we
727 * don't get into an inconsistent state if memory allocation
728 * fails. In case of failure we return the oldnode and inflate
Robert Olsson2f368952005-07-05 15:02:40 -0700729 * of tnode is ignored.
730 */
Olof Johansson91b9a272005-08-09 20:24:39 -0700731
732 for (i = 0; i < olen; i++) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800733 struct tnode *inode;
Robert Olsson2f368952005-07-05 15:02:40 -0700734
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800735 inode = (struct tnode *) tnode_get_child(oldtnode, i);
Robert Olsson2f368952005-07-05 15:02:40 -0700736 if (inode &&
737 IS_TNODE(inode) &&
738 inode->pos == oldtnode->pos + oldtnode->bits &&
739 inode->bits > 1) {
740 struct tnode *left, *right;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -0700741 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700742
Robert Olsson2f368952005-07-05 15:02:40 -0700743 left = tnode_new(inode->key&(~m), inode->pos + 1,
744 inode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700745 if (!left)
746 goto nomem;
Olof Johansson91b9a272005-08-09 20:24:39 -0700747
Robert Olsson2f368952005-07-05 15:02:40 -0700748 right = tnode_new(inode->key|m, inode->pos + 1,
749 inode->bits - 1);
750
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900751 if (!right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700752 tnode_free(left);
753 goto nomem;
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900754 }
Robert Olsson2f368952005-07-05 15:02:40 -0700755
Lin Ming61648d92012-07-29 02:00:03 +0000756 put_child(tn, 2*i, (struct rt_trie_node *) left);
757 put_child(tn, 2*i+1, (struct rt_trie_node *) right);
Robert Olsson2f368952005-07-05 15:02:40 -0700758 }
759 }
760
Olof Johansson91b9a272005-08-09 20:24:39 -0700761 for (i = 0; i < olen; i++) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -0800762 struct tnode *inode;
David S. Millerb299e4f2011-02-02 20:48:10 -0800763 struct rt_trie_node *node = tnode_get_child(oldtnode, i);
Olof Johansson91b9a272005-08-09 20:24:39 -0700764 struct tnode *left, *right;
765 int size, j;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700766
Robert Olsson19baf832005-06-21 12:43:18 -0700767 /* An empty child */
768 if (node == NULL)
769 continue;
770
771 /* A leaf or an internal node with skipped bits */
772
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700773 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
Robert Olsson19baf832005-06-21 12:43:18 -0700774 tn->pos + tn->bits - 1) {
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800775 if (tkey_extract_bits(node->key,
776 oldtnode->pos + oldtnode->bits,
777 1) == 0)
Lin Ming61648d92012-07-29 02:00:03 +0000778 put_child(tn, 2*i, node);
Robert Olsson19baf832005-06-21 12:43:18 -0700779 else
Lin Ming61648d92012-07-29 02:00:03 +0000780 put_child(tn, 2*i+1, node);
Robert Olsson19baf832005-06-21 12:43:18 -0700781 continue;
782 }
783
784 /* An internal node with two children */
785 inode = (struct tnode *) node;
786
787 if (inode->bits == 1) {
Lin Ming61648d92012-07-29 02:00:03 +0000788 put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
789 put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
Robert Olsson19baf832005-06-21 12:43:18 -0700790
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700791 tnode_free_safe(inode);
Olof Johansson91b9a272005-08-09 20:24:39 -0700792 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700793 }
794
Olof Johansson91b9a272005-08-09 20:24:39 -0700795 /* An internal node with more than two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700796
Olof Johansson91b9a272005-08-09 20:24:39 -0700797 /* We will replace this node 'inode' with two new
798 * ones, 'left' and 'right', each with half of the
799 * original children. The two new nodes will have
800 * a position one bit further down the key and this
801 * means that the "significant" part of their keys
802 * (see the discussion near the top of this file)
803 * will differ by one bit, which will be "0" in
804 * left's key and "1" in right's key. Since we are
805 * moving the key position by one step, the bit that
806 * we are moving away from - the bit at position
807 * (inode->pos) - is the one that will differ between
808 * left and right. So... we synthesize that bit in the
809 * two new keys.
810 * The mask 'm' below will be a single "one" bit at
811 * the position (inode->pos)
812 */
Robert Olsson19baf832005-06-21 12:43:18 -0700813
Olof Johansson91b9a272005-08-09 20:24:39 -0700814 /* Use the old key, but set the new significant
815 * bit to zero.
816 */
Robert Olsson19baf832005-06-21 12:43:18 -0700817
Olof Johansson91b9a272005-08-09 20:24:39 -0700818 left = (struct tnode *) tnode_get_child(tn, 2*i);
Lin Ming61648d92012-07-29 02:00:03 +0000819 put_child(tn, 2*i, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -0700820
Olof Johansson91b9a272005-08-09 20:24:39 -0700821 BUG_ON(!left);
Robert Olsson2f368952005-07-05 15:02:40 -0700822
Olof Johansson91b9a272005-08-09 20:24:39 -0700823 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
Lin Ming61648d92012-07-29 02:00:03 +0000824 put_child(tn, 2*i+1, NULL);
Robert Olsson2f368952005-07-05 15:02:40 -0700825
Olof Johansson91b9a272005-08-09 20:24:39 -0700826 BUG_ON(!right);
Robert Olsson2f368952005-07-05 15:02:40 -0700827
Olof Johansson91b9a272005-08-09 20:24:39 -0700828 size = tnode_child_length(left);
829 for (j = 0; j < size; j++) {
Lin Ming61648d92012-07-29 02:00:03 +0000830 put_child(left, j, rtnl_dereference(inode->child[j]));
831 put_child(right, j, rtnl_dereference(inode->child[j + size]));
Robert Olsson19baf832005-06-21 12:43:18 -0700832 }
Lin Ming61648d92012-07-29 02:00:03 +0000833 put_child(tn, 2*i, resize(t, left));
834 put_child(tn, 2*i+1, resize(t, right));
Olof Johansson91b9a272005-08-09 20:24:39 -0700835
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700836 tnode_free_safe(inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700837 }
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700838 tnode_free_safe(oldtnode);
Robert Olsson19baf832005-06-21 12:43:18 -0700839 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700840nomem:
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700841 tnode_clean_free(tn);
842 return ERR_PTR(-ENOMEM);
Robert Olsson19baf832005-06-21 12:43:18 -0700843}
844
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700845static struct tnode *halve(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700846{
847 struct tnode *oldtnode = tn;
David S. Millerb299e4f2011-02-02 20:48:10 -0800848 struct rt_trie_node *left, *right;
Robert Olsson19baf832005-06-21 12:43:18 -0700849 int i;
850 int olen = tnode_child_length(tn);
851
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700852 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700853
854 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700855
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700856 if (!tn)
857 return ERR_PTR(-ENOMEM);
Robert Olsson2f368952005-07-05 15:02:40 -0700858
859 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700860 * Preallocate and store tnodes before the actual work so we
861 * don't get into an inconsistent state if memory allocation
862 * fails. In case of failure we return the oldnode and halve
Robert Olsson2f368952005-07-05 15:02:40 -0700863 * of tnode is ignored.
864 */
865
Olof Johansson91b9a272005-08-09 20:24:39 -0700866 for (i = 0; i < olen; i += 2) {
Robert Olsson2f368952005-07-05 15:02:40 -0700867 left = tnode_get_child(oldtnode, i);
868 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700869
Robert Olsson2f368952005-07-05 15:02:40 -0700870 /* Two nonempty children */
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700871 if (left && right) {
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700872 struct tnode *newn;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700873
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700874 newn = tnode_new(left->key, tn->pos + tn->bits, 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700875
876 if (!newn)
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700877 goto nomem;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700878
Lin Ming61648d92012-07-29 02:00:03 +0000879 put_child(tn, i/2, (struct rt_trie_node *)newn);
Robert Olsson2f368952005-07-05 15:02:40 -0700880 }
Robert Olsson2f368952005-07-05 15:02:40 -0700881
Robert Olsson2f368952005-07-05 15:02:40 -0700882 }
Robert Olsson19baf832005-06-21 12:43:18 -0700883
Olof Johansson91b9a272005-08-09 20:24:39 -0700884 for (i = 0; i < olen; i += 2) {
885 struct tnode *newBinNode;
886
Robert Olsson19baf832005-06-21 12:43:18 -0700887 left = tnode_get_child(oldtnode, i);
888 right = tnode_get_child(oldtnode, i+1);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700889
Robert Olsson19baf832005-06-21 12:43:18 -0700890 /* At least one of the children is empty */
891 if (left == NULL) {
892 if (right == NULL) /* Both are empty */
893 continue;
Lin Ming61648d92012-07-29 02:00:03 +0000894 put_child(tn, i/2, right);
Olof Johansson91b9a272005-08-09 20:24:39 -0700895 continue;
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700896 }
Olof Johansson91b9a272005-08-09 20:24:39 -0700897
898 if (right == NULL) {
Lin Ming61648d92012-07-29 02:00:03 +0000899 put_child(tn, i/2, left);
Olof Johansson91b9a272005-08-09 20:24:39 -0700900 continue;
901 }
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700902
Robert Olsson19baf832005-06-21 12:43:18 -0700903 /* Two nonempty children */
Olof Johansson91b9a272005-08-09 20:24:39 -0700904 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
Lin Ming61648d92012-07-29 02:00:03 +0000905 put_child(tn, i/2, NULL);
906 put_child(newBinNode, 0, left);
907 put_child(newBinNode, 1, right);
908 put_child(tn, i/2, resize(t, newBinNode));
Robert Olsson19baf832005-06-21 12:43:18 -0700909 }
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -0700910 tnode_free_safe(oldtnode);
Robert Olsson19baf832005-06-21 12:43:18 -0700911 return tn;
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700912nomem:
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700913 tnode_clean_free(tn);
914 return ERR_PTR(-ENOMEM);
Robert Olsson19baf832005-06-21 12:43:18 -0700915}
916
Robert Olsson772cb712005-09-19 15:31:18 -0700917/* readside must use rcu_read_lock currently dump routines
Robert Olsson2373ce12005-08-25 13:01:29 -0700918 via get_fa_head and dump */
919
Robert Olsson772cb712005-09-19 15:31:18 -0700920static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700921{
Robert Olsson772cb712005-09-19 15:31:18 -0700922 struct hlist_head *head = &l->list;
Robert Olsson19baf832005-06-21 12:43:18 -0700923 struct hlist_node *node;
924 struct leaf_info *li;
925
Robert Olsson2373ce12005-08-25 13:01:29 -0700926 hlist_for_each_entry_rcu(li, node, head, hlist)
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700927 if (li->plen == plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700928 return li;
Olof Johansson91b9a272005-08-09 20:24:39 -0700929
Robert Olsson19baf832005-06-21 12:43:18 -0700930 return NULL;
931}
932
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800933static inline struct list_head *get_fa_head(struct leaf *l, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -0700934{
Robert Olsson772cb712005-09-19 15:31:18 -0700935 struct leaf_info *li = find_leaf_info(l, plen);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700936
Olof Johansson91b9a272005-08-09 20:24:39 -0700937 if (!li)
938 return NULL;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700939
Olof Johansson91b9a272005-08-09 20:24:39 -0700940 return &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -0700941}
942
943static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
944{
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900945 struct leaf_info *li = NULL, *last = NULL;
946 struct hlist_node *node;
Robert Olsson19baf832005-06-21 12:43:18 -0700947
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900948 if (hlist_empty(head)) {
949 hlist_add_head_rcu(&new->hlist, head);
950 } else {
951 hlist_for_each_entry(li, node, head, hlist) {
952 if (new->plen > li->plen)
953 break;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700954
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +0900955 last = li;
956 }
957 if (last)
958 hlist_add_after_rcu(&last->hlist, &new->hlist);
959 else
960 hlist_add_before_rcu(&new->hlist, &li->hlist);
961 }
Robert Olsson19baf832005-06-21 12:43:18 -0700962}
963
Robert Olsson2373ce12005-08-25 13:01:29 -0700964/* rcu_read_lock needs to be hold by caller from readside */
965
Robert Olsson19baf832005-06-21 12:43:18 -0700966static struct leaf *
967fib_find_node(struct trie *t, u32 key)
968{
969 int pos;
970 struct tnode *tn;
David S. Millerb299e4f2011-02-02 20:48:10 -0800971 struct rt_trie_node *n;
Robert Olsson19baf832005-06-21 12:43:18 -0700972
973 pos = 0;
Eric Dumazeta034ee32010-09-09 23:32:28 +0000974 n = rcu_dereference_rtnl(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -0700975
976 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
977 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -0700978
Robert Olsson19baf832005-06-21 12:43:18 -0700979 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700980
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700981 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Olof Johansson91b9a272005-08-09 20:24:39 -0700982 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -0800983 n = tnode_get_child_rcu(tn,
984 tkey_extract_bits(key,
985 tn->pos,
986 tn->bits));
Olof Johansson91b9a272005-08-09 20:24:39 -0700987 } else
Robert Olsson19baf832005-06-21 12:43:18 -0700988 break;
989 }
990 /* Case we have found a leaf. Compare prefixes */
991
Olof Johansson91b9a272005-08-09 20:24:39 -0700992 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
993 return (struct leaf *)n;
994
Robert Olsson19baf832005-06-21 12:43:18 -0700995 return NULL;
996}
997
Jarek Poplawski7b855762009-06-18 00:28:51 -0700998static void trie_rebalance(struct trie *t, struct tnode *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700999{
Robert Olsson19baf832005-06-21 12:43:18 -07001000 int wasfull;
Robert Olsson3ed18d72009-05-21 15:20:59 -07001001 t_key cindex, key;
Stephen Hemminger06801912007-08-10 15:22:13 -07001002 struct tnode *tp;
Robert Olsson19baf832005-06-21 12:43:18 -07001003
Robert Olsson3ed18d72009-05-21 15:20:59 -07001004 key = tn->key;
1005
David S. Millerb299e4f2011-02-02 20:48:10 -08001006 while (tn != NULL && (tp = node_parent((struct rt_trie_node *)tn)) != NULL) {
Robert Olsson19baf832005-06-21 12:43:18 -07001007 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1008 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
Joe Perchese3192692012-06-03 17:41:40 +00001009 tn = (struct tnode *)resize(t, tn);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001010
Joe Perchese3192692012-06-03 17:41:40 +00001011 tnode_put_child_reorg(tp, cindex,
David S. Millerb299e4f2011-02-02 20:48:10 -08001012 (struct rt_trie_node *)tn, wasfull);
Olof Johansson91b9a272005-08-09 20:24:39 -07001013
David S. Millerb299e4f2011-02-02 20:48:10 -08001014 tp = node_parent((struct rt_trie_node *) tn);
Jarek Poplawski008440e2009-06-30 12:47:19 -07001015 if (!tp)
Eric Dumazetcf778b02012-01-12 04:41:32 +00001016 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
Jarek Poplawski008440e2009-06-30 12:47:19 -07001017
Jarek Poplawskie0f7cb82009-06-15 02:31:29 -07001018 tnode_free_flush();
Stephen Hemminger06801912007-08-10 15:22:13 -07001019 if (!tp)
Robert Olsson19baf832005-06-21 12:43:18 -07001020 break;
Stephen Hemminger06801912007-08-10 15:22:13 -07001021 tn = tp;
Robert Olsson19baf832005-06-21 12:43:18 -07001022 }
Stephen Hemminger06801912007-08-10 15:22:13 -07001023
Robert Olsson19baf832005-06-21 12:43:18 -07001024 /* Handle last (top) tnode */
Jarek Poplawski7b855762009-06-18 00:28:51 -07001025 if (IS_TNODE(tn))
Joe Perchese3192692012-06-03 17:41:40 +00001026 tn = (struct tnode *)resize(t, tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001027
Eric Dumazetcf778b02012-01-12 04:41:32 +00001028 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
Jarek Poplawski7b855762009-06-18 00:28:51 -07001029 tnode_free_flush();
Robert Olsson19baf832005-06-21 12:43:18 -07001030}
1031
Robert Olsson2373ce12005-08-25 13:01:29 -07001032/* only used from updater-side */
1033
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001034static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
Robert Olsson19baf832005-06-21 12:43:18 -07001035{
1036 int pos, newpos;
1037 struct tnode *tp = NULL, *tn = NULL;
David S. Millerb299e4f2011-02-02 20:48:10 -08001038 struct rt_trie_node *n;
Robert Olsson19baf832005-06-21 12:43:18 -07001039 struct leaf *l;
1040 int missbit;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001041 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001042 struct leaf_info *li;
1043 t_key cindex;
1044
1045 pos = 0;
Eric Dumazet0a5c0472011-03-31 01:51:35 -07001046 n = rtnl_dereference(t->trie);
Robert Olsson19baf832005-06-21 12:43:18 -07001047
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001048 /* If we point to NULL, stop. Either the tree is empty and we should
1049 * just put a new leaf in if, or we have reached an empty child slot,
Robert Olsson19baf832005-06-21 12:43:18 -07001050 * and we should just put our new leaf in that.
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001051 * If we point to a T_TNODE, check if it matches our key. Note that
1052 * a T_TNODE might be skipping any number of bits - its 'pos' need
Robert Olsson19baf832005-06-21 12:43:18 -07001053 * not be the parent's 'pos'+'bits'!
1054 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001055 * If it does match the current key, get pos/bits from it, extract
Robert Olsson19baf832005-06-21 12:43:18 -07001056 * the index from our key, push the T_TNODE and walk the tree.
1057 *
1058 * If it doesn't, we have to replace it with a new T_TNODE.
1059 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001060 * If we point to a T_LEAF, it might or might not have the same key
1061 * as we do. If it does, just change the value, update the T_LEAF's
1062 * value, and return it.
Robert Olsson19baf832005-06-21 12:43:18 -07001063 * If it doesn't, we need to replace it with a T_TNODE.
1064 */
1065
1066 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1067 tn = (struct tnode *) n;
Olof Johansson91b9a272005-08-09 20:24:39 -07001068
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001069 check_tnode(tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001070
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001071 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
Robert Olsson19baf832005-06-21 12:43:18 -07001072 tp = tn;
Olof Johansson91b9a272005-08-09 20:24:39 -07001073 pos = tn->pos + tn->bits;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001074 n = tnode_get_child(tn,
1075 tkey_extract_bits(key,
1076 tn->pos,
1077 tn->bits));
Robert Olsson19baf832005-06-21 12:43:18 -07001078
Stephen Hemminger06801912007-08-10 15:22:13 -07001079 BUG_ON(n && node_parent(n) != tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001080 } else
Robert Olsson19baf832005-06-21 12:43:18 -07001081 break;
1082 }
1083
1084 /*
1085 * n ----> NULL, LEAF or TNODE
1086 *
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001087 * tp is n's (parent) ----> NULL or TNODE
Robert Olsson19baf832005-06-21 12:43:18 -07001088 */
1089
Olof Johansson91b9a272005-08-09 20:24:39 -07001090 BUG_ON(tp && IS_LEAF(tp));
Robert Olsson19baf832005-06-21 12:43:18 -07001091
1092 /* Case 1: n is a leaf. Compare prefixes */
1093
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001094 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08001095 l = (struct leaf *) n;
Robert Olsson19baf832005-06-21 12:43:18 -07001096 li = leaf_info_new(plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001097
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001098 if (!li)
1099 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001100
1101 fa_head = &li->falh;
1102 insert_leaf_info(&l->list, li);
1103 goto done;
1104 }
Robert Olsson19baf832005-06-21 12:43:18 -07001105 l = leaf_new();
1106
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001107 if (!l)
1108 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001109
1110 l->key = key;
1111 li = leaf_info_new(plen);
1112
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001113 if (!li) {
Stephen Hemminger387a5482008-04-10 03:47:34 -07001114 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001115 return NULL;
Robert Olssonf835e472005-06-28 15:00:39 -07001116 }
Robert Olsson19baf832005-06-21 12:43:18 -07001117
1118 fa_head = &li->falh;
1119 insert_leaf_info(&l->list, li);
1120
Robert Olsson19baf832005-06-21 12:43:18 -07001121 if (t->trie && n == NULL) {
Olof Johansson91b9a272005-08-09 20:24:39 -07001122 /* Case 2: n is NULL, and will just insert a new leaf */
Robert Olsson19baf832005-06-21 12:43:18 -07001123
David S. Millerb299e4f2011-02-02 20:48:10 -08001124 node_set_parent((struct rt_trie_node *)l, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001125
Olof Johansson91b9a272005-08-09 20:24:39 -07001126 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
Lin Ming61648d92012-07-29 02:00:03 +00001127 put_child(tp, cindex, (struct rt_trie_node *)l);
Olof Johansson91b9a272005-08-09 20:24:39 -07001128 } else {
1129 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001130 /*
1131 * Add a new tnode here
Robert Olsson19baf832005-06-21 12:43:18 -07001132 * first tnode need some special handling
1133 */
1134
1135 if (tp)
Olof Johansson91b9a272005-08-09 20:24:39 -07001136 pos = tp->pos+tp->bits;
Robert Olsson19baf832005-06-21 12:43:18 -07001137 else
Olof Johansson91b9a272005-08-09 20:24:39 -07001138 pos = 0;
1139
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001140 if (n) {
Robert Olsson19baf832005-06-21 12:43:18 -07001141 newpos = tkey_mismatch(key, pos, n->key);
1142 tn = tnode_new(n->key, newpos, 1);
Olof Johansson91b9a272005-08-09 20:24:39 -07001143 } else {
Robert Olsson19baf832005-06-21 12:43:18 -07001144 newpos = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001145 tn = tnode_new(key, newpos, 1); /* First tnode */
Robert Olsson19baf832005-06-21 12:43:18 -07001146 }
Robert Olsson19baf832005-06-21 12:43:18 -07001147
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001148 if (!tn) {
Robert Olssonf835e472005-06-28 15:00:39 -07001149 free_leaf_info(li);
Stephen Hemminger387a5482008-04-10 03:47:34 -07001150 free_leaf(l);
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001151 return NULL;
Olof Johansson91b9a272005-08-09 20:24:39 -07001152 }
1153
David S. Millerb299e4f2011-02-02 20:48:10 -08001154 node_set_parent((struct rt_trie_node *)tn, tp);
Robert Olsson19baf832005-06-21 12:43:18 -07001155
Olof Johansson91b9a272005-08-09 20:24:39 -07001156 missbit = tkey_extract_bits(key, newpos, 1);
Lin Ming61648d92012-07-29 02:00:03 +00001157 put_child(tn, missbit, (struct rt_trie_node *)l);
1158 put_child(tn, 1-missbit, n);
Robert Olsson19baf832005-06-21 12:43:18 -07001159
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001160 if (tp) {
Robert Olsson19baf832005-06-21 12:43:18 -07001161 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
Lin Ming61648d92012-07-29 02:00:03 +00001162 put_child(tp, cindex, (struct rt_trie_node *)tn);
Olof Johansson91b9a272005-08-09 20:24:39 -07001163 } else {
Eric Dumazetcf778b02012-01-12 04:41:32 +00001164 rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001165 tp = tn;
1166 }
1167 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001168
1169 if (tp && tp->pos + tp->bits > 32)
Joe Perches058bd4d2012-03-11 18:36:11 +00001170 pr_warn("fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1171 tp, tp->pos, tp->bits, key, plen);
Olof Johansson91b9a272005-08-09 20:24:39 -07001172
Robert Olsson19baf832005-06-21 12:43:18 -07001173 /* Rebalance the trie */
Robert Olsson2373ce12005-08-25 13:01:29 -07001174
Jarek Poplawski7b855762009-06-18 00:28:51 -07001175 trie_rebalance(t, tp);
Robert Olssonf835e472005-06-28 15:00:39 -07001176done:
Robert Olsson19baf832005-06-21 12:43:18 -07001177 return fa_head;
1178}
1179
Robert Olssond562f1f2007-03-26 14:22:22 -07001180/*
1181 * Caller must hold RTNL.
1182 */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001183int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001184{
1185 struct trie *t = (struct trie *) tb->tb_data;
1186 struct fib_alias *fa, *new_fa;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001187 struct list_head *fa_head = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001188 struct fib_info *fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001189 int plen = cfg->fc_dst_len;
1190 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001191 u32 key, mask;
1192 int err;
1193 struct leaf *l;
1194
1195 if (plen > 32)
1196 return -EINVAL;
1197
Thomas Graf4e902c52006-08-17 18:14:52 -07001198 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001199
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001200 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001201
Olof Johansson91b9a272005-08-09 20:24:39 -07001202 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001203
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001204 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001205 return -EINVAL;
1206
1207 key = key & mask;
1208
Thomas Graf4e902c52006-08-17 18:14:52 -07001209 fi = fib_create_info(cfg);
1210 if (IS_ERR(fi)) {
1211 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001212 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001213 }
Robert Olsson19baf832005-06-21 12:43:18 -07001214
1215 l = fib_find_node(t, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001216 fa = NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001217
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001218 if (l) {
Robert Olsson19baf832005-06-21 12:43:18 -07001219 fa_head = get_fa_head(l, plen);
1220 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1221 }
1222
1223 /* Now fa, if non-NULL, points to the first fib alias
1224 * with the same keys [prefix,tos,priority], if such key already
1225 * exists or to the node before which we will insert new one.
1226 *
1227 * If fa is NULL, we will need to allocate a new one and
1228 * insert to the head of f.
1229 *
1230 * If f is NULL, no fib node matched the destination key
1231 * and we need to allocate a new one of those as well.
1232 */
1233
Julian Anastasov936f6f82008-01-28 21:18:06 -08001234 if (fa && fa->fa_tos == tos &&
1235 fa->fa_info->fib_priority == fi->fib_priority) {
1236 struct fib_alias *fa_first, *fa_match;
Robert Olsson19baf832005-06-21 12:43:18 -07001237
1238 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001239 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001240 goto out;
1241
Julian Anastasov936f6f82008-01-28 21:18:06 -08001242 /* We have 2 goals:
1243 * 1. Find exact match for type, scope, fib_info to avoid
1244 * duplicate routes
1245 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1246 */
1247 fa_match = NULL;
1248 fa_first = fa;
1249 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1250 list_for_each_entry_continue(fa, fa_head, fa_list) {
1251 if (fa->fa_tos != tos)
1252 break;
1253 if (fa->fa_info->fib_priority != fi->fib_priority)
1254 break;
1255 if (fa->fa_type == cfg->fc_type &&
Julian Anastasov936f6f82008-01-28 21:18:06 -08001256 fa->fa_info == fi) {
1257 fa_match = fa;
1258 break;
1259 }
1260 }
1261
Thomas Graf4e902c52006-08-17 18:14:52 -07001262 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001263 struct fib_info *fi_drop;
1264 u8 state;
1265
Julian Anastasov936f6f82008-01-28 21:18:06 -08001266 fa = fa_first;
1267 if (fa_match) {
1268 if (fa == fa_match)
1269 err = 0;
Joonwoo Park67250332008-01-18 03:45:18 -08001270 goto out;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001271 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001272 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001273 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson2373ce12005-08-25 13:01:29 -07001274 if (new_fa == NULL)
1275 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001276
1277 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001278 new_fa->fa_tos = fa->fa_tos;
1279 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001280 new_fa->fa_type = cfg->fc_type;
Robert Olsson19baf832005-06-21 12:43:18 -07001281 state = fa->fa_state;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001282 new_fa->fa_state = state & ~FA_S_ACCESSED;
Robert Olsson19baf832005-06-21 12:43:18 -07001283
Robert Olsson2373ce12005-08-25 13:01:29 -07001284 list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
1285 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001286
1287 fib_release_info(fi_drop);
1288 if (state & FA_S_ACCESSED)
Nicolas Dichtel4ccfe6d2012-09-07 00:45:29 +00001289 rt_cache_flush(cfg->fc_nlinfo.nl_net);
Milan Kocianb8f55832007-05-23 14:55:06 -07001290 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1291 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001292
Olof Johansson91b9a272005-08-09 20:24:39 -07001293 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001294 }
1295 /* Error if we find a perfect match which
1296 * uses the same scope, type, and nexthop
1297 * information.
1298 */
Julian Anastasov936f6f82008-01-28 21:18:06 -08001299 if (fa_match)
1300 goto out;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001301
Thomas Graf4e902c52006-08-17 18:14:52 -07001302 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001303 fa = fa_first;
Robert Olsson19baf832005-06-21 12:43:18 -07001304 }
1305 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001306 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001307 goto out;
1308
1309 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001310 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Robert Olsson19baf832005-06-21 12:43:18 -07001311 if (new_fa == NULL)
1312 goto out;
1313
1314 new_fa->fa_info = fi;
1315 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001316 new_fa->fa_type = cfg->fc_type;
Robert Olsson19baf832005-06-21 12:43:18 -07001317 new_fa->fa_state = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001318 /*
1319 * Insert new entry to the list.
1320 */
1321
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001322 if (!fa_head) {
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001323 fa_head = fib_insert_node(t, key, plen);
1324 if (unlikely(!fa_head)) {
1325 err = -ENOMEM;
Robert Olssonf835e472005-06-28 15:00:39 -07001326 goto out_free_new_fa;
Stephen Hemmingerfea86ad2008-01-12 20:57:07 -08001327 }
Robert Olssonf835e472005-06-28 15:00:39 -07001328 }
Robert Olsson19baf832005-06-21 12:43:18 -07001329
David S. Miller21d8c492011-04-14 14:49:37 -07001330 if (!plen)
1331 tb->tb_num_default++;
1332
Robert Olsson2373ce12005-08-25 13:01:29 -07001333 list_add_tail_rcu(&new_fa->fa_list,
1334 (fa ? &fa->fa_list : fa_head));
Robert Olsson19baf832005-06-21 12:43:18 -07001335
Nicolas Dichtel4ccfe6d2012-09-07 00:45:29 +00001336 rt_cache_flush(cfg->fc_nlinfo.nl_net);
Thomas Graf4e902c52006-08-17 18:14:52 -07001337 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001338 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001339succeeded:
1340 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001341
1342out_free_new_fa:
1343 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001344out:
1345 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001346err:
Robert Olsson19baf832005-06-21 12:43:18 -07001347 return err;
1348}
1349
Robert Olsson772cb712005-09-19 15:31:18 -07001350/* should be called with rcu_read_lock */
David S. Miller5b470442011-01-31 16:10:03 -08001351static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
David S. Miller22bd5b92011-03-11 19:54:08 -05001352 t_key key, const struct flowi4 *flp,
Eric Dumazetebc0ffa2010-10-05 10:41:36 +00001353 struct fib_result *res, int fib_flags)
Robert Olsson19baf832005-06-21 12:43:18 -07001354{
Robert Olsson19baf832005-06-21 12:43:18 -07001355 struct leaf_info *li;
1356 struct hlist_head *hhead = &l->list;
1357 struct hlist_node *node;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001358
Robert Olsson2373ce12005-08-25 13:01:29 -07001359 hlist_for_each_entry_rcu(li, node, hhead, hlist) {
David S. Miller3be06862011-03-07 15:01:10 -08001360 struct fib_alias *fa;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001361
Eric Dumazet5c745012011-07-18 03:16:33 +00001362 if (l->key != (key & li->mask_plen))
Robert Olsson19baf832005-06-21 12:43:18 -07001363 continue;
1364
David S. Miller3be06862011-03-07 15:01:10 -08001365 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
1366 struct fib_info *fi = fa->fa_info;
1367 int nhsel, err;
1368
David S. Miller22bd5b92011-03-11 19:54:08 -05001369 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
David S. Miller3be06862011-03-07 15:01:10 -08001370 continue;
David S. Millerdccd9ecc2012-05-10 22:16:32 -04001371 if (fi->fib_dead)
1372 continue;
David S. Miller37e826c2011-03-24 18:06:47 -07001373 if (fa->fa_info->fib_scope < flp->flowi4_scope)
David S. Miller3be06862011-03-07 15:01:10 -08001374 continue;
1375 fib_alias_accessed(fa);
1376 err = fib_props[fa->fa_type].error;
1377 if (err) {
1378#ifdef CONFIG_IP_FIB_TRIE_STATS
Julian Anastasov1fbc7842011-03-25 20:33:23 -07001379 t->stats.semantic_match_passed++;
David S. Miller3be06862011-03-07 15:01:10 -08001380#endif
Julian Anastasov1fbc7842011-03-25 20:33:23 -07001381 return err;
David S. Miller3be06862011-03-07 15:01:10 -08001382 }
1383 if (fi->fib_flags & RTNH_F_DEAD)
1384 continue;
1385 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1386 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1387
1388 if (nh->nh_flags & RTNH_F_DEAD)
1389 continue;
David S. Miller22bd5b92011-03-11 19:54:08 -05001390 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
David S. Miller3be06862011-03-07 15:01:10 -08001391 continue;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001392
Robert Olsson19baf832005-06-21 12:43:18 -07001393#ifdef CONFIG_IP_FIB_TRIE_STATS
David S. Miller3be06862011-03-07 15:01:10 -08001394 t->stats.semantic_match_passed++;
Robert Olsson19baf832005-06-21 12:43:18 -07001395#endif
Eric Dumazet5c745012011-07-18 03:16:33 +00001396 res->prefixlen = li->plen;
David S. Miller3be06862011-03-07 15:01:10 -08001397 res->nh_sel = nhsel;
1398 res->type = fa->fa_type;
David S. Miller37e826c2011-03-24 18:06:47 -07001399 res->scope = fa->fa_info->fib_scope;
David S. Miller3be06862011-03-07 15:01:10 -08001400 res->fi = fi;
1401 res->table = tb;
1402 res->fa_head = &li->falh;
1403 if (!(fib_flags & FIB_LOOKUP_NOREF))
Eric Dumazet5c745012011-07-18 03:16:33 +00001404 atomic_inc(&fi->fib_clntref);
David S. Miller3be06862011-03-07 15:01:10 -08001405 return 0;
1406 }
1407 }
1408
1409#ifdef CONFIG_IP_FIB_TRIE_STATS
1410 t->stats.semantic_match_miss++;
1411#endif
Robert Olsson19baf832005-06-21 12:43:18 -07001412 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001413
Ben Hutchings2e655572008-07-10 16:52:52 -07001414 return 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001415}
1416
David S. Miller22bd5b92011-03-11 19:54:08 -05001417int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
Eric Dumazetebc0ffa2010-10-05 10:41:36 +00001418 struct fib_result *res, int fib_flags)
Robert Olsson19baf832005-06-21 12:43:18 -07001419{
1420 struct trie *t = (struct trie *) tb->tb_data;
Ben Hutchings2e655572008-07-10 16:52:52 -07001421 int ret;
David S. Millerb299e4f2011-02-02 20:48:10 -08001422 struct rt_trie_node *n;
Robert Olsson19baf832005-06-21 12:43:18 -07001423 struct tnode *pn;
David S. Miller3b004562011-02-16 14:56:22 -08001424 unsigned int pos, bits;
David S. Miller22bd5b92011-03-11 19:54:08 -05001425 t_key key = ntohl(flp->daddr);
David S. Miller3b004562011-02-16 14:56:22 -08001426 unsigned int chopped_off;
Robert Olsson19baf832005-06-21 12:43:18 -07001427 t_key cindex = 0;
David S. Miller3b004562011-02-16 14:56:22 -08001428 unsigned int current_prefix_length = KEYLENGTH;
Olof Johansson91b9a272005-08-09 20:24:39 -07001429 struct tnode *cn;
Eric Dumazet874ffa82010-10-13 06:56:11 +00001430 t_key pref_mismatch;
Olof Johansson91b9a272005-08-09 20:24:39 -07001431
Robert Olsson2373ce12005-08-25 13:01:29 -07001432 rcu_read_lock();
Robert Olsson19baf832005-06-21 12:43:18 -07001433
Robert Olsson2373ce12005-08-25 13:01:29 -07001434 n = rcu_dereference(t->trie);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001435 if (!n)
Robert Olsson19baf832005-06-21 12:43:18 -07001436 goto failed;
1437
1438#ifdef CONFIG_IP_FIB_TRIE_STATS
1439 t->stats.gets++;
1440#endif
1441
1442 /* Just a leaf? */
1443 if (IS_LEAF(n)) {
David S. Miller5b470442011-01-31 16:10:03 -08001444 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001445 goto found;
Robert Olsson19baf832005-06-21 12:43:18 -07001446 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001447
Robert Olsson19baf832005-06-21 12:43:18 -07001448 pn = (struct tnode *) n;
1449 chopped_off = 0;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001450
Olof Johansson91b9a272005-08-09 20:24:39 -07001451 while (pn) {
Robert Olsson19baf832005-06-21 12:43:18 -07001452 pos = pn->pos;
1453 bits = pn->bits;
1454
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001455 if (!chopped_off)
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07001456 cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
1457 pos, bits);
Robert Olsson19baf832005-06-21 12:43:18 -07001458
Jarek Poplawskib902e572009-07-14 11:20:32 +00001459 n = tnode_get_child_rcu(pn, cindex);
Robert Olsson19baf832005-06-21 12:43:18 -07001460
1461 if (n == NULL) {
1462#ifdef CONFIG_IP_FIB_TRIE_STATS
1463 t->stats.null_node_hit++;
1464#endif
1465 goto backtrace;
1466 }
1467
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001468 if (IS_LEAF(n)) {
David S. Miller5b470442011-01-31 16:10:03 -08001469 ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
Ben Hutchings2e655572008-07-10 16:52:52 -07001470 if (ret > 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07001471 goto backtrace;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001472 goto found;
Olof Johansson91b9a272005-08-09 20:24:39 -07001473 }
1474
Olof Johansson91b9a272005-08-09 20:24:39 -07001475 cn = (struct tnode *)n;
1476
1477 /*
1478 * It's a tnode, and we can do some extra checks here if we
1479 * like, to avoid descending into a dead-end branch.
1480 * This tnode is in the parent's child array at index
1481 * key[p_pos..p_pos+p_bits] but potentially with some bits
1482 * chopped off, so in reality the index may be just a
1483 * subprefix, padded with zero at the end.
1484 * We can also take a look at any skipped bits in this
1485 * tnode - everything up to p_pos is supposed to be ok,
1486 * and the non-chopped bits of the index (se previous
1487 * paragraph) are also guaranteed ok, but the rest is
1488 * considered unknown.
1489 *
1490 * The skipped bits are key[pos+bits..cn->pos].
1491 */
1492
1493 /* If current_prefix_length < pos+bits, we are already doing
1494 * actual prefix matching, which means everything from
1495 * pos+(bits-chopped_off) onward must be zero along some
1496 * branch of this subtree - otherwise there is *no* valid
1497 * prefix present. Here we can only check the skipped
1498 * bits. Remember, since we have already indexed into the
1499 * parent's child array, we know that the bits we chopped of
1500 * *are* zero.
1501 */
1502
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001503 /* NOTA BENE: Checking only skipped bits
1504 for the new node here */
Olof Johansson91b9a272005-08-09 20:24:39 -07001505
1506 if (current_prefix_length < pos+bits) {
1507 if (tkey_extract_bits(cn->key, current_prefix_length,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001508 cn->pos - current_prefix_length)
1509 || !(cn->child[0]))
Olof Johansson91b9a272005-08-09 20:24:39 -07001510 goto backtrace;
1511 }
1512
1513 /*
1514 * If chopped_off=0, the index is fully validated and we
1515 * only need to look at the skipped bits for this, the new,
1516 * tnode. What we actually want to do is to find out if
1517 * these skipped bits match our key perfectly, or if we will
1518 * have to count on finding a matching prefix further down,
1519 * because if we do, we would like to have some way of
1520 * verifying the existence of such a prefix at this point.
1521 */
1522
1523 /* The only thing we can do at this point is to verify that
1524 * any such matching prefix can indeed be a prefix to our
1525 * key, and if the bits in the node we are inspecting that
1526 * do not match our key are not ZERO, this cannot be true.
1527 * Thus, find out where there is a mismatch (before cn->pos)
1528 * and verify that all the mismatching bits are zero in the
1529 * new tnode's key.
1530 */
1531
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001532 /*
1533 * Note: We aren't very concerned about the piece of
1534 * the key that precede pn->pos+pn->bits, since these
1535 * have already been checked. The bits after cn->pos
1536 * aren't checked since these are by definition
1537 * "unknown" at this point. Thus, what we want to see
1538 * is if we are about to enter the "prefix matching"
1539 * state, and in that case verify that the skipped
1540 * bits that will prevail throughout this subtree are
1541 * zero, as they have to be if we are to find a
1542 * matching prefix.
Olof Johansson91b9a272005-08-09 20:24:39 -07001543 */
1544
Eric Dumazet874ffa82010-10-13 06:56:11 +00001545 pref_mismatch = mask_pfx(cn->key ^ key, cn->pos);
Olof Johansson91b9a272005-08-09 20:24:39 -07001546
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001547 /*
1548 * In short: If skipped bits in this node do not match
1549 * the search key, enter the "prefix matching"
1550 * state.directly.
Olof Johansson91b9a272005-08-09 20:24:39 -07001551 */
1552 if (pref_mismatch) {
Eric Dumazet79cda752012-08-07 10:45:47 +00001553 /* fls(x) = __fls(x) + 1 */
1554 int mp = KEYLENGTH - __fls(pref_mismatch) - 1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001555
Eric Dumazet874ffa82010-10-13 06:56:11 +00001556 if (tkey_extract_bits(cn->key, mp, cn->pos - mp) != 0)
Olof Johansson91b9a272005-08-09 20:24:39 -07001557 goto backtrace;
1558
1559 if (current_prefix_length >= cn->pos)
1560 current_prefix_length = mp;
1561 }
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001562
Olof Johansson91b9a272005-08-09 20:24:39 -07001563 pn = (struct tnode *)n; /* Descend */
1564 chopped_off = 0;
1565 continue;
1566
Robert Olsson19baf832005-06-21 12:43:18 -07001567backtrace:
1568 chopped_off++;
1569
1570 /* As zero don't change the child key (cindex) */
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001571 while ((chopped_off <= pn->bits)
1572 && !(cindex & (1<<(chopped_off-1))))
Robert Olsson19baf832005-06-21 12:43:18 -07001573 chopped_off++;
Robert Olsson19baf832005-06-21 12:43:18 -07001574
1575 /* Decrease current_... with bits chopped off */
1576 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001577 current_prefix_length = pn->pos + pn->bits
1578 - chopped_off;
Olof Johansson91b9a272005-08-09 20:24:39 -07001579
Robert Olsson19baf832005-06-21 12:43:18 -07001580 /*
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001581 * Either we do the actual chop off according or if we have
Robert Olsson19baf832005-06-21 12:43:18 -07001582 * chopped off all bits in this tnode walk up to our parent.
1583 */
1584
Olof Johansson91b9a272005-08-09 20:24:39 -07001585 if (chopped_off <= pn->bits) {
Robert Olsson19baf832005-06-21 12:43:18 -07001586 cindex &= ~(1 << (chopped_off-1));
Olof Johansson91b9a272005-08-09 20:24:39 -07001587 } else {
David S. Millerb299e4f2011-02-02 20:48:10 -08001588 struct tnode *parent = node_parent_rcu((struct rt_trie_node *) pn);
Stephen Hemminger06801912007-08-10 15:22:13 -07001589 if (!parent)
Robert Olsson19baf832005-06-21 12:43:18 -07001590 goto failed;
Olof Johansson91b9a272005-08-09 20:24:39 -07001591
Robert Olsson19baf832005-06-21 12:43:18 -07001592 /* Get Child's index */
Stephen Hemminger06801912007-08-10 15:22:13 -07001593 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1594 pn = parent;
Robert Olsson19baf832005-06-21 12:43:18 -07001595 chopped_off = 0;
1596
1597#ifdef CONFIG_IP_FIB_TRIE_STATS
1598 t->stats.backtrack++;
1599#endif
1600 goto backtrace;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001601 }
Robert Olsson19baf832005-06-21 12:43:18 -07001602 }
1603failed:
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001604 ret = 1;
Robert Olsson19baf832005-06-21 12:43:18 -07001605found:
Robert Olsson2373ce12005-08-25 13:01:29 -07001606 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07001607 return ret;
1608}
Florian Westphal6fc01432011-08-25 13:46:12 +02001609EXPORT_SYMBOL_GPL(fib_table_lookup);
Robert Olsson19baf832005-06-21 12:43:18 -07001610
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001611/*
1612 * Remove the leaf and return parent.
1613 */
1614static void trie_leaf_remove(struct trie *t, struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001615{
David S. Millerb299e4f2011-02-02 20:48:10 -08001616 struct tnode *tp = node_parent((struct rt_trie_node *) l);
Robert Olsson19baf832005-06-21 12:43:18 -07001617
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001618 pr_debug("entering trie_leaf_remove(%p)\n", l);
Robert Olsson19baf832005-06-21 12:43:18 -07001619
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001620 if (tp) {
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001621 t_key cindex = tkey_extract_bits(l->key, tp->pos, tp->bits);
Lin Ming61648d92012-07-29 02:00:03 +00001622 put_child(tp, cindex, NULL);
Jarek Poplawski7b855762009-06-18 00:28:51 -07001623 trie_rebalance(t, tp);
Olof Johansson91b9a272005-08-09 20:24:39 -07001624 } else
Stephen Hemmingera9b3cd72011-08-01 16:19:00 +00001625 RCU_INIT_POINTER(t->trie, NULL);
Robert Olsson19baf832005-06-21 12:43:18 -07001626
Stephen Hemminger387a5482008-04-10 03:47:34 -07001627 free_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001628}
1629
Robert Olssond562f1f2007-03-26 14:22:22 -07001630/*
1631 * Caller must hold RTNL.
1632 */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001633int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001634{
1635 struct trie *t = (struct trie *) tb->tb_data;
1636 u32 key, mask;
Thomas Graf4e902c52006-08-17 18:14:52 -07001637 int plen = cfg->fc_dst_len;
1638 u8 tos = cfg->fc_tos;
Robert Olsson19baf832005-06-21 12:43:18 -07001639 struct fib_alias *fa, *fa_to_delete;
1640 struct list_head *fa_head;
1641 struct leaf *l;
Olof Johansson91b9a272005-08-09 20:24:39 -07001642 struct leaf_info *li;
1643
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001644 if (plen > 32)
Robert Olsson19baf832005-06-21 12:43:18 -07001645 return -EINVAL;
1646
Thomas Graf4e902c52006-08-17 18:14:52 -07001647 key = ntohl(cfg->fc_dst);
Olof Johansson91b9a272005-08-09 20:24:39 -07001648 mask = ntohl(inet_make_mask(plen));
Robert Olsson19baf832005-06-21 12:43:18 -07001649
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001650 if (key & ~mask)
Robert Olsson19baf832005-06-21 12:43:18 -07001651 return -EINVAL;
1652
1653 key = key & mask;
1654 l = fib_find_node(t, key);
1655
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001656 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001657 return -ESRCH;
1658
Igor Maravicad5b3102012-08-13 10:26:08 +02001659 li = find_leaf_info(l, plen);
1660
1661 if (!li)
1662 return -ESRCH;
1663
1664 fa_head = &li->falh;
Robert Olsson19baf832005-06-21 12:43:18 -07001665 fa = fib_find_alias(fa_head, tos, 0);
1666
1667 if (!fa)
1668 return -ESRCH;
1669
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001670 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001671
1672 fa_to_delete = NULL;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001673 fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
1674 list_for_each_entry_continue(fa, fa_head, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001675 struct fib_info *fi = fa->fa_info;
1676
1677 if (fa->fa_tos != tos)
1678 break;
1679
Thomas Graf4e902c52006-08-17 18:14:52 -07001680 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1681 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
David S. Miller37e826c2011-03-24 18:06:47 -07001682 fa->fa_info->fib_scope == cfg->fc_scope) &&
Julian Anastasov74cb3c12011-03-19 12:13:46 +00001683 (!cfg->fc_prefsrc ||
1684 fi->fib_prefsrc == cfg->fc_prefsrc) &&
Thomas Graf4e902c52006-08-17 18:14:52 -07001685 (!cfg->fc_protocol ||
1686 fi->fib_protocol == cfg->fc_protocol) &&
1687 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001688 fa_to_delete = fa;
1689 break;
1690 }
1691 }
1692
Olof Johansson91b9a272005-08-09 20:24:39 -07001693 if (!fa_to_delete)
1694 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001695
Olof Johansson91b9a272005-08-09 20:24:39 -07001696 fa = fa_to_delete;
Thomas Graf4e902c52006-08-17 18:14:52 -07001697 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001698 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001699
Robert Olsson2373ce12005-08-25 13:01:29 -07001700 list_del_rcu(&fa->fa_list);
Robert Olsson19baf832005-06-21 12:43:18 -07001701
David S. Miller21d8c492011-04-14 14:49:37 -07001702 if (!plen)
1703 tb->tb_num_default--;
1704
Olof Johansson91b9a272005-08-09 20:24:39 -07001705 if (list_empty(fa_head)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001706 hlist_del_rcu(&li->hlist);
Olof Johansson91b9a272005-08-09 20:24:39 -07001707 free_leaf_info(li);
Robert Olsson2373ce12005-08-25 13:01:29 -07001708 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001709
1710 if (hlist_empty(&l->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001711 trie_leaf_remove(t, l);
Olof Johansson91b9a272005-08-09 20:24:39 -07001712
1713 if (fa->fa_state & FA_S_ACCESSED)
Nicolas Dichtel4ccfe6d2012-09-07 00:45:29 +00001714 rt_cache_flush(cfg->fc_nlinfo.nl_net);
Olof Johansson91b9a272005-08-09 20:24:39 -07001715
Robert Olsson2373ce12005-08-25 13:01:29 -07001716 fib_release_info(fa->fa_info);
1717 alias_free_mem_rcu(fa);
Olof Johansson91b9a272005-08-09 20:24:39 -07001718 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001719}
1720
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001721static int trie_flush_list(struct list_head *head)
Robert Olsson19baf832005-06-21 12:43:18 -07001722{
1723 struct fib_alias *fa, *fa_node;
1724 int found = 0;
1725
1726 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1727 struct fib_info *fi = fa->fa_info;
Robert Olsson19baf832005-06-21 12:43:18 -07001728
Robert Olsson2373ce12005-08-25 13:01:29 -07001729 if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
1730 list_del_rcu(&fa->fa_list);
1731 fib_release_info(fa->fa_info);
1732 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001733 found++;
1734 }
1735 }
1736 return found;
1737}
1738
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001739static int trie_flush_leaf(struct leaf *l)
Robert Olsson19baf832005-06-21 12:43:18 -07001740{
1741 int found = 0;
1742 struct hlist_head *lih = &l->list;
1743 struct hlist_node *node, *tmp;
1744 struct leaf_info *li = NULL;
1745
1746 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001747 found += trie_flush_list(&li->falh);
Robert Olsson19baf832005-06-21 12:43:18 -07001748
1749 if (list_empty(&li->falh)) {
Robert Olsson2373ce12005-08-25 13:01:29 -07001750 hlist_del_rcu(&li->hlist);
Robert Olsson19baf832005-06-21 12:43:18 -07001751 free_leaf_info(li);
1752 }
1753 }
1754 return found;
1755}
1756
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001757/*
1758 * Scan for the next right leaf starting at node p->child[idx]
1759 * Since we have back pointer, no recursion necessary.
1760 */
David S. Millerb299e4f2011-02-02 20:48:10 -08001761static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
Robert Olsson19baf832005-06-21 12:43:18 -07001762{
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001763 do {
1764 t_key idx;
Robert Olsson19baf832005-06-21 12:43:18 -07001765
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001766 if (c)
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001767 idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001768 else
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001769 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001770
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001771 while (idx < 1u << p->bits) {
1772 c = tnode_get_child_rcu(p, idx++);
Robert Olsson2373ce12005-08-25 13:01:29 -07001773 if (!c)
Olof Johansson91b9a272005-08-09 20:24:39 -07001774 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001775
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001776 if (IS_LEAF(c)) {
Eric Dumazet0a5c0472011-03-31 01:51:35 -07001777 prefetch(rcu_dereference_rtnl(p->child[idx]));
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001778 return (struct leaf *) c;
Robert Olsson19baf832005-06-21 12:43:18 -07001779 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001780
1781 /* Rescan start scanning in new node */
1782 p = (struct tnode *) c;
1783 idx = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001784 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001785
1786 /* Node empty, walk back up to parent */
David S. Millerb299e4f2011-02-02 20:48:10 -08001787 c = (struct rt_trie_node *) p;
Eric Dumazeta034ee32010-09-09 23:32:28 +00001788 } while ((p = node_parent_rcu(c)) != NULL);
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001789
1790 return NULL; /* Root of trie */
1791}
1792
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001793static struct leaf *trie_firstleaf(struct trie *t)
1794{
Eric Dumazeta034ee32010-09-09 23:32:28 +00001795 struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001796
1797 if (!n)
1798 return NULL;
1799
1800 if (IS_LEAF(n)) /* trie is just a leaf */
1801 return (struct leaf *) n;
1802
1803 return leaf_walk_rcu(n, NULL);
1804}
1805
1806static struct leaf *trie_nextleaf(struct leaf *l)
1807{
David S. Millerb299e4f2011-02-02 20:48:10 -08001808 struct rt_trie_node *c = (struct rt_trie_node *) l;
Jarek Poplawskib902e572009-07-14 11:20:32 +00001809 struct tnode *p = node_parent_rcu(c);
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001810
1811 if (!p)
1812 return NULL; /* trie with just one leaf */
1813
1814 return leaf_walk_rcu(p, c);
Robert Olsson19baf832005-06-21 12:43:18 -07001815}
1816
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001817static struct leaf *trie_leafindex(struct trie *t, int index)
1818{
1819 struct leaf *l = trie_firstleaf(t);
1820
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001821 while (l && index-- > 0)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001822 l = trie_nextleaf(l);
Stephen Hemmingerec28cf72008-02-11 21:12:49 -08001823
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001824 return l;
1825}
1826
1827
Robert Olssond562f1f2007-03-26 14:22:22 -07001828/*
1829 * Caller must hold RTNL.
1830 */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001831int fib_table_flush(struct fib_table *tb)
Robert Olsson19baf832005-06-21 12:43:18 -07001832{
1833 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001834 struct leaf *l, *ll = NULL;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001835 int found = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001836
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001837 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
Stephen Hemmingeref3660c2008-04-10 03:46:12 -07001838 found += trie_flush_leaf(l);
Robert Olsson19baf832005-06-21 12:43:18 -07001839
1840 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001841 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001842 ll = l;
1843 }
1844
1845 if (ll && hlist_empty(&ll->list))
Stephen Hemminger9195bef2008-01-22 21:56:34 -08001846 trie_leaf_remove(t, ll);
Robert Olsson19baf832005-06-21 12:43:18 -07001847
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001848 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001849 return found;
1850}
1851
Pavel Emelyanov4aa2c462010-10-28 02:00:43 +00001852void fib_free_table(struct fib_table *tb)
1853{
1854 kfree(tb);
1855}
1856
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001857static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah,
1858 struct fib_table *tb,
Robert Olsson19baf832005-06-21 12:43:18 -07001859 struct sk_buff *skb, struct netlink_callback *cb)
1860{
1861 int i, s_i;
1862 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07001863 __be32 xkey = htonl(key);
Robert Olsson19baf832005-06-21 12:43:18 -07001864
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001865 s_i = cb->args[5];
Robert Olsson19baf832005-06-21 12:43:18 -07001866 i = 0;
1867
Robert Olsson2373ce12005-08-25 13:01:29 -07001868 /* rcu_read_lock is hold by caller */
1869
1870 list_for_each_entry_rcu(fa, fah, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001871 if (i < s_i) {
1872 i++;
1873 continue;
1874 }
Robert Olsson19baf832005-06-21 12:43:18 -07001875
Eric W. Biederman15e47302012-09-07 20:12:54 +00001876 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
Robert Olsson19baf832005-06-21 12:43:18 -07001877 cb->nlh->nlmsg_seq,
1878 RTM_NEWROUTE,
1879 tb->tb_id,
1880 fa->fa_type,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001881 xkey,
Robert Olsson19baf832005-06-21 12:43:18 -07001882 plen,
1883 fa->fa_tos,
Stephen Hemminger64347f72008-01-22 21:55:01 -08001884 fa->fa_info, NLM_F_MULTI) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001885 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001886 return -1;
Olof Johansson91b9a272005-08-09 20:24:39 -07001887 }
Robert Olsson19baf832005-06-21 12:43:18 -07001888 i++;
1889 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001890 cb->args[5] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001891 return skb->len;
1892}
1893
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001894static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
1895 struct sk_buff *skb, struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001896{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001897 struct leaf_info *li;
1898 struct hlist_node *node;
1899 int i, s_i;
Robert Olsson19baf832005-06-21 12:43:18 -07001900
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001901 s_i = cb->args[4];
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001902 i = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001903
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001904 /* rcu_read_lock is hold by caller */
1905 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
1906 if (i < s_i) {
1907 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001908 continue;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001909 }
Robert Olsson19baf832005-06-21 12:43:18 -07001910
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001911 if (i > s_i)
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001912 cb->args[5] = 0;
Olof Johansson91b9a272005-08-09 20:24:39 -07001913
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001914 if (list_empty(&li->falh))
Robert Olsson19baf832005-06-21 12:43:18 -07001915 continue;
1916
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001917 if (fn_trie_dump_fa(l->key, li->plen, &li->falh, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001918 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001919 return -1;
1920 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001921 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001922 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001923
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001924 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001925 return skb->len;
1926}
1927
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001928int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1929 struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001930{
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001931 struct leaf *l;
Robert Olsson19baf832005-06-21 12:43:18 -07001932 struct trie *t = (struct trie *) tb->tb_data;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001933 t_key key = cb->args[2];
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001934 int count = cb->args[3];
Robert Olsson19baf832005-06-21 12:43:18 -07001935
Robert Olsson2373ce12005-08-25 13:01:29 -07001936 rcu_read_lock();
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001937 /* Dump starting at last key.
1938 * Note: 0.0.0.0/0 (ie default) is first key.
1939 */
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001940 if (count == 0)
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001941 l = trie_firstleaf(t);
1942 else {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001943 /* Normally, continue from last key, but if that is missing
1944 * fallback to using slow rescan
1945 */
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001946 l = fib_find_node(t, key);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001947 if (!l)
1948 l = trie_leafindex(t, count);
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001949 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001950
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001951 while (l) {
1952 cb->args[2] = l->key;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001953 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001954 cb->args[3] = count;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001955 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001956 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001957 }
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001958
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001959 ++count;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001960 l = trie_nextleaf(l);
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001961 memset(&cb->args[4], 0,
1962 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Robert Olsson19baf832005-06-21 12:43:18 -07001963 }
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001964 cb->args[3] = count;
Robert Olsson2373ce12005-08-25 13:01:29 -07001965 rcu_read_unlock();
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001966
Robert Olsson19baf832005-06-21 12:43:18 -07001967 return skb->len;
Robert Olsson19baf832005-06-21 12:43:18 -07001968}
1969
David S. Miller5348ba82011-02-01 15:30:56 -08001970void __init fib_trie_init(void)
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001971{
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001972 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1973 sizeof(struct fib_alias),
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08001974 0, SLAB_PANIC, NULL);
1975
1976 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
1977 max(sizeof(struct leaf),
1978 sizeof(struct leaf_info)),
1979 0, SLAB_PANIC, NULL);
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001980}
Robert Olsson19baf832005-06-21 12:43:18 -07001981
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001982
David S. Miller5348ba82011-02-01 15:30:56 -08001983struct fib_table *fib_trie_table(u32 id)
Robert Olsson19baf832005-06-21 12:43:18 -07001984{
1985 struct fib_table *tb;
1986 struct trie *t;
1987
Robert Olsson19baf832005-06-21 12:43:18 -07001988 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
1989 GFP_KERNEL);
1990 if (tb == NULL)
1991 return NULL;
1992
1993 tb->tb_id = id;
Denis V. Lunev971b8932007-12-08 00:32:23 -08001994 tb->tb_default = -1;
David S. Miller21d8c492011-04-14 14:49:37 -07001995 tb->tb_num_default = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001996
1997 t = (struct trie *) tb->tb_data;
Stephen Hemmingerc28a1cf2008-01-12 20:49:13 -08001998 memset(t, 0, sizeof(*t));
Robert Olsson19baf832005-06-21 12:43:18 -07001999
Robert Olsson19baf832005-06-21 12:43:18 -07002000 return tb;
2001}
2002
Robert Olsson19baf832005-06-21 12:43:18 -07002003#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002004/* Depth first Trie walk iterator */
2005struct fib_trie_iter {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002006 struct seq_net_private p;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002007 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002008 struct tnode *tnode;
Eric Dumazeta034ee32010-09-09 23:32:28 +00002009 unsigned int index;
2010 unsigned int depth;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002011};
Robert Olsson19baf832005-06-21 12:43:18 -07002012
David S. Millerb299e4f2011-02-02 20:48:10 -08002013static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002014{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002015 struct tnode *tn = iter->tnode;
Eric Dumazeta034ee32010-09-09 23:32:28 +00002016 unsigned int cindex = iter->index;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002017 struct tnode *p;
2018
Eric W. Biederman6640e692007-01-24 14:42:04 -08002019 /* A single entry routing table */
2020 if (!tn)
2021 return NULL;
2022
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002023 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2024 iter->tnode, iter->index, iter->depth);
2025rescan:
2026 while (cindex < (1<<tn->bits)) {
David S. Millerb299e4f2011-02-02 20:48:10 -08002027 struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002028
2029 if (n) {
2030 if (IS_LEAF(n)) {
2031 iter->tnode = tn;
2032 iter->index = cindex + 1;
2033 } else {
2034 /* push down one level */
2035 iter->tnode = (struct tnode *) n;
2036 iter->index = 0;
2037 ++iter->depth;
2038 }
2039 return n;
2040 }
2041
2042 ++cindex;
2043 }
2044
2045 /* Current node exhausted, pop back up */
David S. Millerb299e4f2011-02-02 20:48:10 -08002046 p = node_parent_rcu((struct rt_trie_node *)tn);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002047 if (p) {
2048 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2049 tn = p;
2050 --iter->depth;
2051 goto rescan;
2052 }
2053
2054 /* got root? */
Robert Olsson19baf832005-06-21 12:43:18 -07002055 return NULL;
2056}
2057
David S. Millerb299e4f2011-02-02 20:48:10 -08002058static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002059 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002060{
David S. Millerb299e4f2011-02-02 20:48:10 -08002061 struct rt_trie_node *n;
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002062
Stephen Hemminger132adf52007-03-08 20:44:43 -08002063 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002064 return NULL;
2065
2066 n = rcu_dereference(t->trie);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002067 if (!n)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002068 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002069
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002070 if (IS_TNODE(n)) {
2071 iter->tnode = (struct tnode *) n;
2072 iter->index = 0;
2073 iter->depth = 1;
2074 } else {
2075 iter->tnode = NULL;
2076 iter->index = 0;
2077 iter->depth = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002078 }
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002079
2080 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002081}
2082
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002083static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002084{
David S. Millerb299e4f2011-02-02 20:48:10 -08002085 struct rt_trie_node *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002086 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002087
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002088 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002089
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002090 rcu_read_lock();
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002091 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002092 if (IS_LEAF(n)) {
Stephen Hemminger93672292008-01-22 21:54:05 -08002093 struct leaf *l = (struct leaf *)n;
2094 struct leaf_info *li;
2095 struct hlist_node *tmp;
2096
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002097 s->leaves++;
2098 s->totdepth += iter.depth;
2099 if (iter.depth > s->maxdepth)
2100 s->maxdepth = iter.depth;
Stephen Hemminger93672292008-01-22 21:54:05 -08002101
2102 hlist_for_each_entry_rcu(li, tmp, &l->list, hlist)
2103 ++s->prefixes;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002104 } else {
2105 const struct tnode *tn = (const struct tnode *) n;
2106 int i;
Robert Olsson19baf832005-06-21 12:43:18 -07002107
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002108 s->tnodes++;
Stephen Hemminger132adf52007-03-08 20:44:43 -08002109 if (tn->bits < MAX_STAT_DEPTH)
Robert Olsson06ef9212006-03-20 21:35:01 -08002110 s->nodesizes[tn->bits]++;
2111
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002112 for (i = 0; i < (1<<tn->bits); i++)
2113 if (!tn->child[i])
2114 s->nullpointers++;
2115 }
2116 }
2117 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002118}
2119
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002120/*
Robert Olsson19baf832005-06-21 12:43:18 -07002121 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002122 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002123static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002124{
Eric Dumazeta034ee32010-09-09 23:32:28 +00002125 unsigned int i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002126
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002127 if (stat->leaves)
2128 avdepth = stat->totdepth*100 / stat->leaves;
2129 else
2130 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002131
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002132 seq_printf(seq, "\tAver depth: %u.%02d\n",
2133 avdepth / 100, avdepth % 100);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002134 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002135
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002136 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002137 bytes = sizeof(struct leaf) * stat->leaves;
Stephen Hemminger93672292008-01-22 21:54:05 -08002138
2139 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
2140 bytes += sizeof(struct leaf_info) * stat->prefixes;
2141
Stephen Hemminger187b5182008-01-12 20:55:55 -08002142 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002143 bytes += sizeof(struct tnode) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002144
Robert Olsson06ef9212006-03-20 21:35:01 -08002145 max = MAX_STAT_DEPTH;
2146 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002147 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002148
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002149 pointers = 0;
2150 for (i = 1; i <= max; i++)
2151 if (stat->nodesizes[i] != 0) {
Stephen Hemminger187b5182008-01-12 20:55:55 -08002152 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002153 pointers += (1<<i) * stat->nodesizes[i];
2154 }
2155 seq_putc(seq, '\n');
Stephen Hemminger187b5182008-01-12 20:55:55 -08002156 seq_printf(seq, "\tPointers: %u\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002157
David S. Millerb299e4f2011-02-02 20:48:10 -08002158 bytes += sizeof(struct rt_trie_node *) * pointers;
Stephen Hemminger187b5182008-01-12 20:55:55 -08002159 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2160 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002161}
Robert Olsson19baf832005-06-21 12:43:18 -07002162
2163#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002164static void trie_show_usage(struct seq_file *seq,
2165 const struct trie_use_stats *stats)
2166{
2167 seq_printf(seq, "\nCounters:\n---------\n");
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002168 seq_printf(seq, "gets = %u\n", stats->gets);
2169 seq_printf(seq, "backtracks = %u\n", stats->backtrack);
2170 seq_printf(seq, "semantic match passed = %u\n",
2171 stats->semantic_match_passed);
2172 seq_printf(seq, "semantic match miss = %u\n",
2173 stats->semantic_match_miss);
2174 seq_printf(seq, "null node hit= %u\n", stats->null_node_hit);
2175 seq_printf(seq, "skipped node resize = %u\n\n",
2176 stats->resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002177}
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002178#endif /* CONFIG_IP_FIB_TRIE_STATS */
2179
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002180static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002181{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002182 if (tb->tb_id == RT_TABLE_LOCAL)
2183 seq_puts(seq, "Local:\n");
2184 else if (tb->tb_id == RT_TABLE_MAIN)
2185 seq_puts(seq, "Main:\n");
2186 else
2187 seq_printf(seq, "Id %d:\n", tb->tb_id);
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002188}
Robert Olsson19baf832005-06-21 12:43:18 -07002189
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002190
Robert Olsson19baf832005-06-21 12:43:18 -07002191static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2192{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002193 struct net *net = (struct net *)seq->private;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002194 unsigned int h;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002195
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002196 seq_printf(seq,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002197 "Basic info: size of leaf:"
2198 " %Zd bytes, size of tnode: %Zd bytes.\n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002199 sizeof(struct leaf), sizeof(struct tnode));
Olof Johansson91b9a272005-08-09 20:24:39 -07002200
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002201 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2202 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2203 struct hlist_node *node;
2204 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002205
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002206 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
2207 struct trie *t = (struct trie *) tb->tb_data;
2208 struct trie_stat stat;
2209
2210 if (!t)
2211 continue;
2212
2213 fib_table_print(seq, tb);
2214
2215 trie_collect_stats(t, &stat);
2216 trie_show_stats(seq, &stat);
2217#ifdef CONFIG_IP_FIB_TRIE_STATS
2218 trie_show_usage(seq, &t->stats);
2219#endif
2220 }
2221 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002222
Robert Olsson19baf832005-06-21 12:43:18 -07002223 return 0;
2224}
2225
Robert Olsson19baf832005-06-21 12:43:18 -07002226static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2227{
Pavel Emelyanovde05c552008-07-18 04:07:21 -07002228 return single_open_net(inode, file, fib_triestat_seq_show);
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002229}
2230
Arjan van de Ven9a321442007-02-12 00:55:35 -08002231static const struct file_operations fib_triestat_fops = {
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002232 .owner = THIS_MODULE,
2233 .open = fib_triestat_seq_open,
2234 .read = seq_read,
2235 .llseek = seq_lseek,
Pavel Emelyanovb6fcbdb2008-07-18 04:07:44 -07002236 .release = single_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002237};
2238
David S. Millerb299e4f2011-02-02 20:48:10 -08002239static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
Robert Olsson19baf832005-06-21 12:43:18 -07002240{
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002241 struct fib_trie_iter *iter = seq->private;
2242 struct net *net = seq_file_net(seq);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002243 loff_t idx = 0;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002244 unsigned int h;
Robert Olsson19baf832005-06-21 12:43:18 -07002245
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002246 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2247 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2248 struct hlist_node *node;
2249 struct fib_table *tb;
2250
2251 hlist_for_each_entry_rcu(tb, node, head, tb_hlist) {
David S. Millerb299e4f2011-02-02 20:48:10 -08002252 struct rt_trie_node *n;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002253
2254 for (n = fib_trie_get_first(iter,
2255 (struct trie *) tb->tb_data);
2256 n; n = fib_trie_get_next(iter))
2257 if (pos == idx++) {
2258 iter->tb = tb;
2259 return n;
2260 }
2261 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002262 }
Robert Olsson19baf832005-06-21 12:43:18 -07002263
Robert Olsson19baf832005-06-21 12:43:18 -07002264 return NULL;
2265}
2266
2267static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002268 __acquires(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002269{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002270 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002271 return fib_trie_get_idx(seq, *pos);
Robert Olsson19baf832005-06-21 12:43:18 -07002272}
2273
2274static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2275{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002276 struct fib_trie_iter *iter = seq->private;
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002277 struct net *net = seq_file_net(seq);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002278 struct fib_table *tb = iter->tb;
2279 struct hlist_node *tb_node;
2280 unsigned int h;
David S. Millerb299e4f2011-02-02 20:48:10 -08002281 struct rt_trie_node *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002282
Robert Olsson19baf832005-06-21 12:43:18 -07002283 ++*pos;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002284 /* next node in same table */
2285 n = fib_trie_get_next(iter);
2286 if (n)
2287 return n;
Olof Johansson91b9a272005-08-09 20:24:39 -07002288
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002289 /* walk rest of this hash chain */
2290 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
Eric Dumazet0a5c0472011-03-31 01:51:35 -07002291 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002292 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2293 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2294 if (n)
2295 goto found;
2296 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002297
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002298 /* new hash chain */
2299 while (++h < FIB_TABLE_HASHSZ) {
2300 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
2301 hlist_for_each_entry_rcu(tb, tb_node, head, tb_hlist) {
2302 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2303 if (n)
2304 goto found;
2305 }
2306 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002307 return NULL;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002308
2309found:
2310 iter->tb = tb;
2311 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002312}
2313
2314static void fib_trie_seq_stop(struct seq_file *seq, void *v)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002315 __releases(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002316{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002317 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002318}
2319
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002320static void seq_indent(struct seq_file *seq, int n)
2321{
Eric Dumazeta034ee32010-09-09 23:32:28 +00002322 while (n-- > 0)
2323 seq_puts(seq, " ");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002324}
Robert Olsson19baf832005-06-21 12:43:18 -07002325
Eric Dumazet28d36e32008-01-14 23:09:56 -08002326static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002327{
Stephen Hemminger132adf52007-03-08 20:44:43 -08002328 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002329 case RT_SCOPE_UNIVERSE: return "universe";
2330 case RT_SCOPE_SITE: return "site";
2331 case RT_SCOPE_LINK: return "link";
2332 case RT_SCOPE_HOST: return "host";
2333 case RT_SCOPE_NOWHERE: return "nowhere";
2334 default:
Eric Dumazet28d36e32008-01-14 23:09:56 -08002335 snprintf(buf, len, "scope=%d", s);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002336 return buf;
2337 }
2338}
2339
Jan Engelhardt36cbd3d2009-08-05 10:42:58 -07002340static const char *const rtn_type_names[__RTN_MAX] = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002341 [RTN_UNSPEC] = "UNSPEC",
2342 [RTN_UNICAST] = "UNICAST",
2343 [RTN_LOCAL] = "LOCAL",
2344 [RTN_BROADCAST] = "BROADCAST",
2345 [RTN_ANYCAST] = "ANYCAST",
2346 [RTN_MULTICAST] = "MULTICAST",
2347 [RTN_BLACKHOLE] = "BLACKHOLE",
2348 [RTN_UNREACHABLE] = "UNREACHABLE",
2349 [RTN_PROHIBIT] = "PROHIBIT",
2350 [RTN_THROW] = "THROW",
2351 [RTN_NAT] = "NAT",
2352 [RTN_XRESOLVE] = "XRESOLVE",
2353};
2354
Eric Dumazeta034ee32010-09-09 23:32:28 +00002355static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002356{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002357 if (t < __RTN_MAX && rtn_type_names[t])
2358 return rtn_type_names[t];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002359 snprintf(buf, len, "type %u", t);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002360 return buf;
2361}
2362
2363/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002364static int fib_trie_seq_show(struct seq_file *seq, void *v)
2365{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002366 const struct fib_trie_iter *iter = seq->private;
David S. Millerb299e4f2011-02-02 20:48:10 -08002367 struct rt_trie_node *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002368
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002369 if (!node_parent_rcu(n))
2370 fib_table_print(seq, iter->tb);
Robert Olsson095b8502007-01-26 19:06:01 -08002371
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002372 if (IS_TNODE(n)) {
2373 struct tnode *tn = (struct tnode *) n;
Stephen Hemmingerab66b4a2007-08-10 15:22:58 -07002374 __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002375
Robert Olsson1d25cd62005-09-19 15:29:52 -07002376 seq_indent(seq, iter->depth-1);
Harvey Harrison673d57e2008-10-31 00:53:57 -07002377 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
2378 &prf, tn->pos, tn->bits, tn->full_children,
Robert Olsson1d25cd62005-09-19 15:29:52 -07002379 tn->empty_children);
YOSHIFUJI Hideakie905a9e2007-02-09 23:24:47 +09002380
Olof Johansson91b9a272005-08-09 20:24:39 -07002381 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002382 struct leaf *l = (struct leaf *) n;
Stephen Hemminger13280422008-01-22 21:54:37 -08002383 struct leaf_info *li;
2384 struct hlist_node *node;
Al Viro32ab5f82006-09-26 22:21:45 -07002385 __be32 val = htonl(l->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002386
2387 seq_indent(seq, iter->depth);
Harvey Harrison673d57e2008-10-31 00:53:57 -07002388 seq_printf(seq, " |-- %pI4\n", &val);
Eric Dumazet28d36e32008-01-14 23:09:56 -08002389
Stephen Hemminger13280422008-01-22 21:54:37 -08002390 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
2391 struct fib_alias *fa;
Eric Dumazet28d36e32008-01-14 23:09:56 -08002392
Stephen Hemminger13280422008-01-22 21:54:37 -08002393 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
2394 char buf1[32], buf2[32];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002395
Stephen Hemminger13280422008-01-22 21:54:37 -08002396 seq_indent(seq, iter->depth+1);
2397 seq_printf(seq, " /%d %s %s", li->plen,
2398 rtn_scope(buf1, sizeof(buf1),
David S. Miller37e826c2011-03-24 18:06:47 -07002399 fa->fa_info->fib_scope),
Stephen Hemminger13280422008-01-22 21:54:37 -08002400 rtn_type(buf2, sizeof(buf2),
2401 fa->fa_type));
2402 if (fa->fa_tos)
Denis V. Lunevb9c4d822008-02-05 02:58:45 -08002403 seq_printf(seq, " tos=%d", fa->fa_tos);
Stephen Hemminger13280422008-01-22 21:54:37 -08002404 seq_putc(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002405 }
2406 }
Robert Olsson19baf832005-06-21 12:43:18 -07002407 }
2408
2409 return 0;
2410}
2411
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002412static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002413 .start = fib_trie_seq_start,
2414 .next = fib_trie_seq_next,
2415 .stop = fib_trie_seq_stop,
2416 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002417};
2418
2419static int fib_trie_seq_open(struct inode *inode, struct file *file)
2420{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002421 return seq_open_net(inode, file, &fib_trie_seq_ops,
2422 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002423}
2424
Arjan van de Ven9a321442007-02-12 00:55:35 -08002425static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002426 .owner = THIS_MODULE,
2427 .open = fib_trie_seq_open,
2428 .read = seq_read,
2429 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002430 .release = seq_release_net,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002431};
2432
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002433struct fib_route_iter {
2434 struct seq_net_private p;
2435 struct trie *main_trie;
2436 loff_t pos;
2437 t_key key;
2438};
2439
2440static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
2441{
2442 struct leaf *l = NULL;
2443 struct trie *t = iter->main_trie;
2444
2445 /* use cache location of last found key */
2446 if (iter->pos > 0 && pos >= iter->pos && (l = fib_find_node(t, iter->key)))
2447 pos -= iter->pos;
2448 else {
2449 iter->pos = 0;
2450 l = trie_firstleaf(t);
2451 }
2452
2453 while (l && pos-- > 0) {
2454 iter->pos++;
2455 l = trie_nextleaf(l);
2456 }
2457
2458 if (l)
2459 iter->key = pos; /* remember it */
2460 else
2461 iter->pos = 0; /* forget it */
2462
2463 return l;
2464}
2465
2466static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2467 __acquires(RCU)
2468{
2469 struct fib_route_iter *iter = seq->private;
2470 struct fib_table *tb;
2471
2472 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002473 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002474 if (!tb)
2475 return NULL;
2476
2477 iter->main_trie = (struct trie *) tb->tb_data;
2478 if (*pos == 0)
2479 return SEQ_START_TOKEN;
2480 else
2481 return fib_route_get_idx(iter, *pos - 1);
2482}
2483
2484static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2485{
2486 struct fib_route_iter *iter = seq->private;
2487 struct leaf *l = v;
2488
2489 ++*pos;
2490 if (v == SEQ_START_TOKEN) {
2491 iter->pos = 0;
2492 l = trie_firstleaf(iter->main_trie);
2493 } else {
2494 iter->pos++;
2495 l = trie_nextleaf(l);
2496 }
2497
2498 if (l)
2499 iter->key = l->key;
2500 else
2501 iter->pos = 0;
2502 return l;
2503}
2504
2505static void fib_route_seq_stop(struct seq_file *seq, void *v)
2506 __releases(RCU)
2507{
2508 rcu_read_unlock();
2509}
2510
Eric Dumazeta034ee32010-09-09 23:32:28 +00002511static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002512{
Eric Dumazeta034ee32010-09-09 23:32:28 +00002513 unsigned int flags = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002514
Eric Dumazeta034ee32010-09-09 23:32:28 +00002515 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2516 flags = RTF_REJECT;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002517 if (fi && fi->fib_nh->nh_gw)
2518 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002519 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002520 flags |= RTF_HOST;
2521 flags |= RTF_UP;
2522 return flags;
2523}
2524
2525/*
2526 * This outputs /proc/net/route.
2527 * The format of the file is not supposed to be changed
Eric Dumazeta034ee32010-09-09 23:32:28 +00002528 * and needs to be same as fib_hash output to avoid breaking
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002529 * legacy utilities
2530 */
2531static int fib_route_seq_show(struct seq_file *seq, void *v)
2532{
2533 struct leaf *l = v;
Stephen Hemminger13280422008-01-22 21:54:37 -08002534 struct leaf_info *li;
2535 struct hlist_node *node;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002536
2537 if (v == SEQ_START_TOKEN) {
2538 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2539 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2540 "\tWindow\tIRTT");
2541 return 0;
2542 }
2543
Stephen Hemminger13280422008-01-22 21:54:37 -08002544 hlist_for_each_entry_rcu(li, node, &l->list, hlist) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002545 struct fib_alias *fa;
Al Viro32ab5f82006-09-26 22:21:45 -07002546 __be32 mask, prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002547
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002548 mask = inet_make_mask(li->plen);
2549 prefix = htonl(l->key);
2550
2551 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
Herbert Xu1371e372005-10-15 09:42:39 +10002552 const struct fib_info *fi = fa->fa_info;
Eric Dumazeta034ee32010-09-09 23:32:28 +00002553 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002554 int len;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002555
2556 if (fa->fa_type == RTN_BROADCAST
2557 || fa->fa_type == RTN_MULTICAST)
2558 continue;
2559
2560 if (fi)
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002561 seq_printf(seq,
2562 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2563 "%d\t%08X\t%d\t%u\t%u%n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002564 fi->fib_dev ? fi->fib_dev->name : "*",
2565 prefix,
2566 fi->fib_nh->nh_gw, flags, 0, 0,
2567 fi->fib_priority,
2568 mask,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002569 (fi->fib_advmss ?
2570 fi->fib_advmss + 40 : 0),
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002571 fi->fib_window,
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002572 fi->fib_rtt >> 3, &len);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002573 else
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002574 seq_printf(seq,
2575 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2576 "%d\t%08X\t%d\t%u\t%u%n",
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002577 prefix, 0, flags, 0, 0, 0,
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002578 mask, 0, 0, 0, &len);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002579
Pavel Emelyanov5e659e42008-04-24 01:02:16 -07002580 seq_printf(seq, "%*s\n", 127 - len, "");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002581 }
2582 }
2583
2584 return 0;
2585}
2586
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002587static const struct seq_operations fib_route_seq_ops = {
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002588 .start = fib_route_seq_start,
2589 .next = fib_route_seq_next,
2590 .stop = fib_route_seq_stop,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002591 .show = fib_route_seq_show,
2592};
2593
2594static int fib_route_seq_open(struct inode *inode, struct file *file)
2595{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002596 return seq_open_net(inode, file, &fib_route_seq_ops,
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002597 sizeof(struct fib_route_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002598}
2599
Arjan van de Ven9a321442007-02-12 00:55:35 -08002600static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002601 .owner = THIS_MODULE,
2602 .open = fib_route_seq_open,
2603 .read = seq_read,
2604 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002605 .release = seq_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002606};
2607
Denis V. Lunev61a02652008-01-10 03:21:09 -08002608int __net_init fib_proc_init(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002609{
Gao fengd4beaa62013-02-18 01:34:54 +00002610 if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002611 goto out1;
2612
Gao fengd4beaa62013-02-18 01:34:54 +00002613 if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2614 &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002615 goto out2;
2616
Gao fengd4beaa62013-02-18 01:34:54 +00002617 if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002618 goto out3;
2619
Robert Olsson19baf832005-06-21 12:43:18 -07002620 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002621
2622out3:
Gao fengece31ff2013-02-18 01:34:56 +00002623 remove_proc_entry("fib_triestat", net->proc_net);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002624out2:
Gao fengece31ff2013-02-18 01:34:56 +00002625 remove_proc_entry("fib_trie", net->proc_net);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002626out1:
2627 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002628}
2629
Denis V. Lunev61a02652008-01-10 03:21:09 -08002630void __net_exit fib_proc_exit(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002631{
Gao fengece31ff2013-02-18 01:34:56 +00002632 remove_proc_entry("fib_trie", net->proc_net);
2633 remove_proc_entry("fib_triestat", net->proc_net);
2634 remove_proc_entry("route", net->proc_net);
Robert Olsson19baf832005-06-21 12:43:18 -07002635}
2636
2637#endif /* CONFIG_PROC_FS */