blob: 01bce1506cd76a82551c44102c9d397be0970f1b [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 Gortmakerbc3b2d72011-07-15 11:47:34 -040074#include <linux/export.h>
David S. Millerffa915d2015-05-27 00:19:03 -040075#include <linux/vmalloc.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>
Scott Feldman8e05fd72015-03-05 21:21:19 -080083#include <net/switchdev.h>
Robert Olsson19baf832005-06-21 12:43:18 -070084#include "fib_lookup.h"
85
Robert Olsson06ef9212006-03-20 21:35:01 -080086#define MAX_STAT_DEPTH 32
Robert Olsson19baf832005-06-21 12:43:18 -070087
Alexander Duyck95f60ea2015-01-22 15:51:26 -080088#define KEYLENGTH (8*sizeof(t_key))
89#define KEY_MAX ((t_key)~0)
Robert Olsson19baf832005-06-21 12:43:18 -070090
Robert Olsson19baf832005-06-21 12:43:18 -070091typedef unsigned int t_key;
92
Alexander Duyck88bae712015-03-06 09:54:52 -080093#define IS_TRIE(n) ((n)->pos >= KEYLENGTH)
94#define IS_TNODE(n) ((n)->bits)
95#define IS_LEAF(n) (!(n)->bits)
Robert Olsson2373ce12005-08-25 13:01:29 -070096
Alexander Duyck35c6eda2015-03-06 09:54:08 -080097struct key_vector {
Alexander Duyck41b489f2015-03-04 15:02:33 -080098 t_key key;
99 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
100 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
101 unsigned char slen;
Alexander Duyckadaf9812014-12-31 10:55:47 -0800102 union {
Alexander Duyck41b489f2015-03-04 15:02:33 -0800103 /* This list pointer if valid if (pos | bits) == 0 (LEAF) */
Alexander Duyck79e5ad22015-02-25 15:31:51 -0800104 struct hlist_head leaf;
Alexander Duyck41b489f2015-03-04 15:02:33 -0800105 /* This array is valid if (pos | bits) > 0 (TNODE) */
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800106 struct key_vector __rcu *tnode[0];
Alexander Duyckadaf9812014-12-31 10:55:47 -0800107 };
Robert Olsson19baf832005-06-21 12:43:18 -0700108};
109
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800110struct tnode {
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800111 struct rcu_head rcu;
Alexander Duyck6e22d172015-03-06 09:54:39 -0800112 t_key empty_children; /* KEYLENGTH bits needed */
113 t_key full_children; /* KEYLENGTH bits needed */
Alexander Duyckf23e59f2015-03-06 09:54:46 -0800114 struct key_vector __rcu *parent;
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800115 struct key_vector kv[1];
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800116#define tn_bits kv[0].bits
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800117};
118
119#define TNODE_SIZE(n) offsetof(struct tnode, kv[0].tnode[n])
Alexander Duyck41b489f2015-03-04 15:02:33 -0800120#define LEAF_SIZE TNODE_SIZE(1)
121
Robert Olsson19baf832005-06-21 12:43:18 -0700122#ifdef CONFIG_IP_FIB_TRIE_STATS
123struct trie_use_stats {
124 unsigned int gets;
125 unsigned int backtrack;
126 unsigned int semantic_match_passed;
127 unsigned int semantic_match_miss;
128 unsigned int null_node_hit;
Robert Olsson2f368952005-07-05 15:02:40 -0700129 unsigned int resize_node_skipped;
Robert Olsson19baf832005-06-21 12:43:18 -0700130};
131#endif
132
133struct trie_stat {
134 unsigned int totdepth;
135 unsigned int maxdepth;
136 unsigned int tnodes;
137 unsigned int leaves;
138 unsigned int nullpointers;
Stephen Hemminger93672292008-01-22 21:54:05 -0800139 unsigned int prefixes;
Robert Olsson06ef9212006-03-20 21:35:01 -0800140 unsigned int nodesizes[MAX_STAT_DEPTH];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700141};
Robert Olsson19baf832005-06-21 12:43:18 -0700142
143struct trie {
Alexander Duyck88bae712015-03-06 09:54:52 -0800144 struct key_vector kv[1];
Robert Olsson19baf832005-06-21 12:43:18 -0700145#ifdef CONFIG_IP_FIB_TRIE_STATS
Alexander Duyck8274a972014-12-31 10:55:29 -0800146 struct trie_use_stats __percpu *stats;
Robert Olsson19baf832005-06-21 12:43:18 -0700147#endif
Robert Olsson19baf832005-06-21 12:43:18 -0700148};
149
Alexander Duyck88bae712015-03-06 09:54:52 -0800150static struct key_vector *resize(struct trie *t, struct key_vector *tn);
Jarek Poplawskic3059472009-07-14 08:33:08 +0000151static size_t tnode_free_size;
152
153/*
154 * synchronize_rcu after call_rcu for that many pages; it should be especially
155 * useful before resizing the root node with PREEMPT_NONE configs; the value was
156 * obtained experimentally, aiming to avoid visible slowdown.
157 */
158static const int sync_pages = 128;
Robert Olsson19baf832005-06-21 12:43:18 -0700159
Christoph Lametere18b8902006-12-06 20:33:20 -0800160static struct kmem_cache *fn_alias_kmem __read_mostly;
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -0800161static struct kmem_cache *trie_leaf_kmem __read_mostly;
Robert Olsson19baf832005-06-21 12:43:18 -0700162
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800163static inline struct tnode *tn_info(struct key_vector *kv)
164{
165 return container_of(kv, struct tnode, kv[0]);
166}
167
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800168/* caller must hold RTNL */
Alexander Duyckf23e59f2015-03-06 09:54:46 -0800169#define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
Alexander Duyck754baf82015-03-06 09:54:14 -0800170#define get_child(tn, i) rtnl_dereference((tn)->tnode[i])
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700171
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800172/* caller must hold RCU read lock or RTNL */
Alexander Duyckf23e59f2015-03-06 09:54:46 -0800173#define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
Alexander Duyck754baf82015-03-06 09:54:14 -0800174#define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700175
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800176/* wrapper for rcu_assign_pointer */
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800177static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
Stephen Hemminger06801912007-08-10 15:22:13 -0700178{
Alexander Duyckadaf9812014-12-31 10:55:47 -0800179 if (n)
Alexander Duyckf23e59f2015-03-06 09:54:46 -0800180 rcu_assign_pointer(tn_info(n)->parent, tp);
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800181}
182
Alexander Duyckf23e59f2015-03-06 09:54:46 -0800183#define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p)
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800184
185/* This provides us with the number of children in this node, in the case of a
186 * leaf this will return 0 meaning none of the children are accessible.
187 */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800188static inline unsigned long child_length(const struct key_vector *tn)
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800189{
190 return (1ul << tn->bits) & ~(1ul);
Stephen Hemminger06801912007-08-10 15:22:13 -0700191}
Robert Olsson2373ce12005-08-25 13:01:29 -0700192
Alexander Duyck88bae712015-03-06 09:54:52 -0800193#define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)
194
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800195static inline unsigned long get_index(t_key key, struct key_vector *kv)
196{
197 unsigned long index = key ^ kv->key;
198
Alexander Duyck88bae712015-03-06 09:54:52 -0800199 if ((BITS_PER_LONG <= KEYLENGTH) && (KEYLENGTH == kv->pos))
200 return 0;
201
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800202 return index >> kv->pos;
203}
204
Alexander Duycke9b44012014-12-31 10:56:12 -0800205/* To understand this stuff, an understanding of keys and all their bits is
206 * necessary. Every node in the trie has a key associated with it, but not
207 * all of the bits in that key are significant.
208 *
209 * Consider a node 'n' and its parent 'tp'.
210 *
211 * If n is a leaf, every bit in its key is significant. Its presence is
212 * necessitated by path compression, since during a tree traversal (when
213 * searching for a leaf - unless we are doing an insertion) we will completely
214 * ignore all skipped bits we encounter. Thus we need to verify, at the end of
215 * a potentially successful search, that we have indeed been walking the
216 * correct key path.
217 *
218 * Note that we can never "miss" the correct key in the tree if present by
219 * following the wrong path. Path compression ensures that segments of the key
220 * that are the same for all keys with a given prefix are skipped, but the
221 * skipped part *is* identical for each node in the subtrie below the skipped
222 * bit! trie_insert() in this implementation takes care of that.
223 *
224 * if n is an internal node - a 'tnode' here, the various parts of its key
225 * have many different meanings.
226 *
227 * Example:
228 * _________________________________________________________________
229 * | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
230 * -----------------------------------------------------------------
231 * 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16
232 *
233 * _________________________________________________________________
234 * | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
235 * -----------------------------------------------------------------
236 * 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
237 *
238 * tp->pos = 22
239 * tp->bits = 3
240 * n->pos = 13
241 * n->bits = 4
242 *
243 * First, let's just ignore the bits that come before the parent tp, that is
244 * the bits from (tp->pos + tp->bits) to 31. They are *known* but at this
245 * point we do not use them for anything.
246 *
247 * The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
248 * index into the parent's child array. That is, they will be used to find
249 * 'n' among tp's children.
250 *
251 * The bits from (n->pos + n->bits) to (tn->pos - 1) - "S" - are skipped bits
252 * for the node n.
253 *
254 * All the bits we have seen so far are significant to the node n. The rest
255 * of the bits are really not needed or indeed known in n->key.
256 *
257 * The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
258 * n's child array, and will of course be different for each child.
259 *
260 * The rest of the bits, from 0 to (n->pos + n->bits), are completely unknown
261 * at this point.
262 */
Robert Olsson19baf832005-06-21 12:43:18 -0700263
Denis V. Lunevf5026fa2007-12-13 09:47:57 -0800264static const int halve_threshold = 25;
265static const int inflate_threshold = 50;
Jarek Poplawski345aa032009-07-07 19:39:16 -0700266static const int halve_threshold_root = 15;
Jens Låås80b71b82009-08-28 23:57:15 -0700267static const int inflate_threshold_root = 30;
Robert Olsson2373ce12005-08-25 13:01:29 -0700268
269static void __alias_free_mem(struct rcu_head *head)
270{
271 struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
272 kmem_cache_free(fn_alias_kmem, fa);
273}
274
275static inline void alias_free_mem_rcu(struct fib_alias *fa)
276{
277 call_rcu(&fa->rcu, __alias_free_mem);
278}
279
Alexander Duyck37fd30f2014-12-31 10:55:41 -0800280#define TNODE_KMALLOC_MAX \
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800281 ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
Alexander Duyck1de3d872015-03-04 15:04:46 -0800282#define TNODE_VMALLOC_MAX \
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800283 ilog2((SIZE_MAX - TNODE_SIZE(0)) / sizeof(struct key_vector *))
Alexander Duyck37fd30f2014-12-31 10:55:41 -0800284
285static void __node_free_rcu(struct rcu_head *head)
Robert Olsson2373ce12005-08-25 13:01:29 -0700286{
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800287 struct tnode *n = container_of(head, struct tnode, rcu);
Alexander Duyck37fd30f2014-12-31 10:55:41 -0800288
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800289 if (!n->tn_bits)
Alexander Duyck37fd30f2014-12-31 10:55:41 -0800290 kmem_cache_free(trie_leaf_kmem, n);
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800291 else if (n->tn_bits <= TNODE_KMALLOC_MAX)
Alexander Duyck37fd30f2014-12-31 10:55:41 -0800292 kfree(n);
293 else
294 vfree(n);
Robert Olsson2373ce12005-08-25 13:01:29 -0700295}
296
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800297#define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu)
Stephen Hemminger387a5482008-04-10 03:47:34 -0700298
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800299static struct tnode *tnode_alloc(int bits)
Robert Olsson2373ce12005-08-25 13:01:29 -0700300{
Alexander Duyck1de3d872015-03-04 15:04:46 -0800301 size_t size;
302
303 /* verify bits is within bounds */
304 if (bits > TNODE_VMALLOC_MAX)
305 return NULL;
306
307 /* determine size and verify it is non-zero and didn't overflow */
308 size = TNODE_SIZE(1ul << bits);
309
Robert Olsson2373ce12005-08-25 13:01:29 -0700310 if (size <= PAGE_SIZE)
Eric Dumazet8d965442008-01-13 22:31:44 -0800311 return kzalloc(size, GFP_KERNEL);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700312 else
Eric Dumazet7a1c8e52010-11-20 07:46:35 +0000313 return vzalloc(size);
Stephen Hemminger15be75c2008-04-10 02:56:38 -0700314}
Robert Olsson2373ce12005-08-25 13:01:29 -0700315
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800316static inline void empty_child_inc(struct key_vector *n)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800317{
Alexander Duyck6e22d172015-03-06 09:54:39 -0800318 ++tn_info(n)->empty_children ? : ++tn_info(n)->full_children;
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800319}
320
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800321static inline void empty_child_dec(struct key_vector *n)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800322{
Alexander Duyck6e22d172015-03-06 09:54:39 -0800323 tn_info(n)->empty_children-- ? : tn_info(n)->full_children--;
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800324}
325
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800326static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
Robert Olsson19baf832005-06-21 12:43:18 -0700327{
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800328 struct tnode *kv = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
329 struct key_vector *l = kv->kv;
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800330
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800331 if (!kv)
332 return NULL;
333
334 /* initialize key vector */
335 l->key = key;
336 l->pos = 0;
337 l->bits = 0;
338 l->slen = fa->fa_slen;
339
340 /* link leaf to fib alias */
341 INIT_HLIST_HEAD(&l->leaf);
342 hlist_add_head(&fa->fa_list, &l->leaf);
343
Robert Olsson19baf832005-06-21 12:43:18 -0700344 return l;
345}
346
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800347static struct key_vector *tnode_new(t_key key, int pos, int bits)
Robert Olsson19baf832005-06-21 12:43:18 -0700348{
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800349 struct tnode *tnode = tnode_alloc(bits);
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800350 unsigned int shift = pos + bits;
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800351 struct key_vector *tn = tnode->kv;
Alexander Duyck64c9b6f2014-12-31 10:55:35 -0800352
353 /* verify bits and pos their msb bits clear and values are valid */
354 BUG_ON(!bits || (shift > KEYLENGTH));
Robert Olsson19baf832005-06-21 12:43:18 -0700355
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800356 pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800357 sizeof(struct key_vector *) << bits);
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800358
359 if (!tnode)
360 return NULL;
361
362 if (bits == KEYLENGTH)
Alexander Duyck6e22d172015-03-06 09:54:39 -0800363 tnode->full_children = 1;
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800364 else
Alexander Duyck6e22d172015-03-06 09:54:39 -0800365 tnode->empty_children = 1ul << bits;
Alexander Duyckdc35dbe2015-03-06 09:54:27 -0800366
367 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
368 tn->pos = pos;
369 tn->bits = bits;
370 tn->slen = pos;
371
Robert Olsson19baf832005-06-21 12:43:18 -0700372 return tn;
373}
374
Alexander Duycke9b44012014-12-31 10:56:12 -0800375/* Check whether a tnode 'n' is "full", i.e. it is an internal node
Robert Olsson19baf832005-06-21 12:43:18 -0700376 * and no bits are skipped. See discussion in dyntree paper p. 6
377 */
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800378static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700379{
Alexander Duycke9b44012014-12-31 10:56:12 -0800380 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
Robert Olsson19baf832005-06-21 12:43:18 -0700381}
382
Alexander Duyckff181ed2014-12-31 10:56:43 -0800383/* Add a child at position i overwriting the old value.
384 * Update the value of full_children and empty_children.
385 */
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800386static void put_child(struct key_vector *tn, unsigned long i,
387 struct key_vector *n)
Robert Olsson19baf832005-06-21 12:43:18 -0700388{
Alexander Duyck754baf82015-03-06 09:54:14 -0800389 struct key_vector *chi = get_child(tn, i);
Alexander Duyckff181ed2014-12-31 10:56:43 -0800390 int isfull, wasfull;
Robert Olsson19baf832005-06-21 12:43:18 -0700391
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800392 BUG_ON(i >= child_length(tn));
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700393
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800394 /* update emptyChildren, overflow into fullChildren */
Ian Morris00db4122015-04-03 09:17:27 +0100395 if (!n && chi)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800396 empty_child_inc(tn);
Ian Morris00db4122015-04-03 09:17:27 +0100397 if (n && !chi)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800398 empty_child_dec(tn);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700399
Robert Olsson19baf832005-06-21 12:43:18 -0700400 /* update fullChildren */
Alexander Duyckff181ed2014-12-31 10:56:43 -0800401 wasfull = tnode_full(tn, chi);
Robert Olsson19baf832005-06-21 12:43:18 -0700402 isfull = tnode_full(tn, n);
Alexander Duyckff181ed2014-12-31 10:56:43 -0800403
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700404 if (wasfull && !isfull)
Alexander Duyck6e22d172015-03-06 09:54:39 -0800405 tn_info(tn)->full_children--;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700406 else if (!wasfull && isfull)
Alexander Duyck6e22d172015-03-06 09:54:39 -0800407 tn_info(tn)->full_children++;
Olof Johansson91b9a272005-08-09 20:24:39 -0700408
Alexander Duyck5405afd2014-12-31 10:57:08 -0800409 if (n && (tn->slen < n->slen))
410 tn->slen = n->slen;
411
Alexander Duyck41b489f2015-03-04 15:02:33 -0800412 rcu_assign_pointer(tn->tnode[i], n);
Robert Olsson19baf832005-06-21 12:43:18 -0700413}
414
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800415static void update_children(struct key_vector *tn)
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800416{
417 unsigned long i;
418
419 /* update all of the child parent pointers */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800420 for (i = child_length(tn); i;) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800421 struct key_vector *inode = get_child(tn, --i);
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800422
423 if (!inode)
424 continue;
425
426 /* Either update the children of a tnode that
427 * already belongs to us or update the child
428 * to point to ourselves.
429 */
430 if (node_parent(inode) == tn)
431 update_children(inode);
432 else
433 node_set_parent(inode, tn);
434 }
435}
436
Alexander Duyck88bae712015-03-06 09:54:52 -0800437static inline void put_child_root(struct key_vector *tp, t_key key,
438 struct key_vector *n)
Alexander Duyck836a0122014-12-31 10:56:06 -0800439{
Alexander Duyck88bae712015-03-06 09:54:52 -0800440 if (IS_TRIE(tp))
441 rcu_assign_pointer(tp->tnode[0], n);
Alexander Duyck836a0122014-12-31 10:56:06 -0800442 else
Alexander Duyck88bae712015-03-06 09:54:52 -0800443 put_child(tp, get_index(key, tp), n);
Alexander Duyck836a0122014-12-31 10:56:06 -0800444}
445
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800446static inline void tnode_free_init(struct key_vector *tn)
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700447{
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800448 tn_info(tn)->rcu.next = NULL;
Alexander Duyckfc86a932014-12-31 10:56:49 -0800449}
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700450
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800451static inline void tnode_free_append(struct key_vector *tn,
452 struct key_vector *n)
Alexander Duyckfc86a932014-12-31 10:56:49 -0800453{
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800454 tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
455 tn_info(tn)->rcu.next = &tn_info(n)->rcu;
Alexander Duyckfc86a932014-12-31 10:56:49 -0800456}
457
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800458static void tnode_free(struct key_vector *tn)
Alexander Duyckfc86a932014-12-31 10:56:49 -0800459{
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800460 struct callback_head *head = &tn_info(tn)->rcu;
Alexander Duyckfc86a932014-12-31 10:56:49 -0800461
462 while (head) {
463 head = head->next;
Alexander Duyck41b489f2015-03-04 15:02:33 -0800464 tnode_free_size += TNODE_SIZE(1ul << tn->bits);
Alexander Duyckfc86a932014-12-31 10:56:49 -0800465 node_free(tn);
466
Alexander Duyck56ca2ad2015-03-06 09:54:33 -0800467 tn = container_of(head, struct tnode, rcu)->kv;
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700468 }
Alexander Duyckfc86a932014-12-31 10:56:49 -0800469
470 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
471 tnode_free_size = 0;
472 synchronize_rcu();
473 }
Eric Dumazet0a5c0472011-03-31 01:51:35 -0700474}
475
Alexander Duyck88bae712015-03-06 09:54:52 -0800476static struct key_vector *replace(struct trie *t,
477 struct key_vector *oldtnode,
478 struct key_vector *tn)
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800479{
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800480 struct key_vector *tp = node_parent(oldtnode);
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800481 unsigned long i;
482
483 /* setup the parent pointer out of and back into this node */
484 NODE_INIT_PARENT(tn, tp);
Alexander Duyck88bae712015-03-06 09:54:52 -0800485 put_child_root(tp, tn->key, tn);
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800486
487 /* update all of the child parent pointers */
488 update_children(tn);
489
490 /* all pointers should be clean so we are done */
491 tnode_free(oldtnode);
492
493 /* resize children now that oldtnode is freed */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800494 for (i = child_length(tn); i;) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800495 struct key_vector *inode = get_child(tn, --i);
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800496
497 /* resize child node */
498 if (tnode_full(tn, inode))
Alexander Duyck88bae712015-03-06 09:54:52 -0800499 tn = resize(t, inode);
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800500 }
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800501
Alexander Duyck88bae712015-03-06 09:54:52 -0800502 return tp;
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800503}
504
Alexander Duyck88bae712015-03-06 09:54:52 -0800505static struct key_vector *inflate(struct trie *t,
506 struct key_vector *oldtnode)
Robert Olsson19baf832005-06-21 12:43:18 -0700507{
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800508 struct key_vector *tn;
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800509 unsigned long i;
Alexander Duycke9b44012014-12-31 10:56:12 -0800510 t_key m;
Robert Olsson19baf832005-06-21 12:43:18 -0700511
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700512 pr_debug("In inflate\n");
Robert Olsson19baf832005-06-21 12:43:18 -0700513
Alexander Duycke9b44012014-12-31 10:56:12 -0800514 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700515 if (!tn)
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800516 goto notnode;
Robert Olsson2f368952005-07-05 15:02:40 -0700517
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800518 /* prepare oldtnode to be freed */
519 tnode_free_init(oldtnode);
520
Alexander Duyck12c081a2014-12-31 10:56:55 -0800521 /* Assemble all of the pointers in our cluster, in this case that
522 * represents all of the pointers out of our allocated nodes that
523 * point to existing tnodes and the links between our allocated
524 * nodes.
Robert Olsson2f368952005-07-05 15:02:40 -0700525 */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800526 for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800527 struct key_vector *inode = get_child(oldtnode, --i);
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800528 struct key_vector *node0, *node1;
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800529 unsigned long j, k;
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700530
Robert Olsson19baf832005-06-21 12:43:18 -0700531 /* An empty child */
Ian Morris51456b22015-04-03 09:17:26 +0100532 if (!inode)
Robert Olsson19baf832005-06-21 12:43:18 -0700533 continue;
534
535 /* A leaf or an internal node with skipped bits */
Alexander Duyckadaf9812014-12-31 10:55:47 -0800536 if (!tnode_full(oldtnode, inode)) {
Alexander Duycke9b44012014-12-31 10:56:12 -0800537 put_child(tn, get_index(inode->key, tn), inode);
Robert Olsson19baf832005-06-21 12:43:18 -0700538 continue;
539 }
540
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800541 /* drop the node in the old tnode free list */
542 tnode_free_append(oldtnode, inode);
543
Robert Olsson19baf832005-06-21 12:43:18 -0700544 /* An internal node with two children */
Robert Olsson19baf832005-06-21 12:43:18 -0700545 if (inode->bits == 1) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800546 put_child(tn, 2 * i + 1, get_child(inode, 1));
547 put_child(tn, 2 * i, get_child(inode, 0));
Olof Johansson91b9a272005-08-09 20:24:39 -0700548 continue;
Robert Olsson19baf832005-06-21 12:43:18 -0700549 }
550
Olof Johansson91b9a272005-08-09 20:24:39 -0700551 /* We will replace this node 'inode' with two new
Alexander Duyck12c081a2014-12-31 10:56:55 -0800552 * ones, 'node0' and 'node1', each with half of the
Olof Johansson91b9a272005-08-09 20:24:39 -0700553 * original children. The two new nodes will have
554 * a position one bit further down the key and this
555 * means that the "significant" part of their keys
556 * (see the discussion near the top of this file)
557 * will differ by one bit, which will be "0" in
Alexander Duyck12c081a2014-12-31 10:56:55 -0800558 * node0's key and "1" in node1's key. Since we are
Olof Johansson91b9a272005-08-09 20:24:39 -0700559 * moving the key position by one step, the bit that
560 * we are moving away from - the bit at position
Alexander Duyck12c081a2014-12-31 10:56:55 -0800561 * (tn->pos) - is the one that will differ between
562 * node0 and node1. So... we synthesize that bit in the
563 * two new keys.
Olof Johansson91b9a272005-08-09 20:24:39 -0700564 */
Alexander Duyck12c081a2014-12-31 10:56:55 -0800565 node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
566 if (!node1)
567 goto nomem;
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800568 node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
Robert Olsson19baf832005-06-21 12:43:18 -0700569
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800570 tnode_free_append(tn, node1);
Alexander Duyck12c081a2014-12-31 10:56:55 -0800571 if (!node0)
572 goto nomem;
573 tnode_free_append(tn, node0);
Robert Olsson19baf832005-06-21 12:43:18 -0700574
Alexander Duyck12c081a2014-12-31 10:56:55 -0800575 /* populate child pointers in new nodes */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800576 for (k = child_length(inode), j = k / 2; j;) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800577 put_child(node1, --j, get_child(inode, --k));
578 put_child(node0, j, get_child(inode, j));
579 put_child(node1, --j, get_child(inode, --k));
580 put_child(node0, j, get_child(inode, j));
Robert Olsson19baf832005-06-21 12:43:18 -0700581 }
Alexander Duyckff181ed2014-12-31 10:56:43 -0800582
Alexander Duyck12c081a2014-12-31 10:56:55 -0800583 /* link new nodes to parent */
584 NODE_INIT_PARENT(node1, tn);
585 NODE_INIT_PARENT(node0, tn);
Olof Johansson91b9a272005-08-09 20:24:39 -0700586
Alexander Duyck12c081a2014-12-31 10:56:55 -0800587 /* link parent to nodes */
588 put_child(tn, 2 * i + 1, node1);
589 put_child(tn, 2 * i, node0);
Robert Olsson19baf832005-06-21 12:43:18 -0700590 }
Alexander Duyckff181ed2014-12-31 10:56:43 -0800591
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800592 /* setup the parent pointers into and out of this node */
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800593 return replace(t, oldtnode, tn);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700594nomem:
Alexander Duyckfc86a932014-12-31 10:56:49 -0800595 /* all pointers should be clean so we are done */
596 tnode_free(tn);
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800597notnode:
598 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -0700599}
600
Alexander Duyck88bae712015-03-06 09:54:52 -0800601static struct key_vector *halve(struct trie *t,
602 struct key_vector *oldtnode)
Robert Olsson19baf832005-06-21 12:43:18 -0700603{
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800604 struct key_vector *tn;
Alexander Duyck12c081a2014-12-31 10:56:55 -0800605 unsigned long i;
Robert Olsson19baf832005-06-21 12:43:18 -0700606
Stephen Hemminger0c7770c2005-08-23 21:59:41 -0700607 pr_debug("In halve\n");
Stephen Hemmingerc877efb2005-07-19 14:01:51 -0700608
Alexander Duycke9b44012014-12-31 10:56:12 -0800609 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
Robert Olsson2f80b3c2005-08-09 20:25:06 -0700610 if (!tn)
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800611 goto notnode;
Robert Olsson2f368952005-07-05 15:02:40 -0700612
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800613 /* prepare oldtnode to be freed */
614 tnode_free_init(oldtnode);
615
Alexander Duyck12c081a2014-12-31 10:56:55 -0800616 /* Assemble all of the pointers in our cluster, in this case that
617 * represents all of the pointers out of our allocated nodes that
618 * point to existing tnodes and the links between our allocated
619 * nodes.
Robert Olsson2f368952005-07-05 15:02:40 -0700620 */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800621 for (i = child_length(oldtnode); i;) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800622 struct key_vector *node1 = get_child(oldtnode, --i);
623 struct key_vector *node0 = get_child(oldtnode, --i);
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800624 struct key_vector *inode;
Robert Olsson2f368952005-07-05 15:02:40 -0700625
Alexander Duyck12c081a2014-12-31 10:56:55 -0800626 /* At least one of the children is empty */
627 if (!node1 || !node0) {
628 put_child(tn, i / 2, node1 ? : node0);
629 continue;
Robert Olsson2f368952005-07-05 15:02:40 -0700630 }
Robert Olsson2f368952005-07-05 15:02:40 -0700631
Alexander Duyck12c081a2014-12-31 10:56:55 -0800632 /* Two nonempty children */
633 inode = tnode_new(node0->key, oldtnode->pos, 1);
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800634 if (!inode)
635 goto nomem;
Alexander Duyck12c081a2014-12-31 10:56:55 -0800636 tnode_free_append(tn, inode);
637
638 /* initialize pointers out of node */
639 put_child(inode, 1, node1);
640 put_child(inode, 0, node0);
641 NODE_INIT_PARENT(inode, tn);
642
643 /* link parent to node */
644 put_child(tn, i / 2, inode);
Robert Olsson2f368952005-07-05 15:02:40 -0700645 }
Robert Olsson19baf832005-06-21 12:43:18 -0700646
Alexander Duyck69fa57b2015-01-22 15:51:14 -0800647 /* setup the parent pointers into and out of this node */
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800648 return replace(t, oldtnode, tn);
649nomem:
650 /* all pointers should be clean so we are done */
651 tnode_free(tn);
652notnode:
653 return NULL;
Robert Olsson19baf832005-06-21 12:43:18 -0700654}
655
Alexander Duyck88bae712015-03-06 09:54:52 -0800656static struct key_vector *collapse(struct trie *t,
657 struct key_vector *oldtnode)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800658{
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800659 struct key_vector *n, *tp;
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800660 unsigned long i;
661
662 /* scan the tnode looking for that one child that might still exist */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800663 for (n = NULL, i = child_length(oldtnode); !n && i;)
Alexander Duyck754baf82015-03-06 09:54:14 -0800664 n = get_child(oldtnode, --i);
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800665
666 /* compress one level */
667 tp = node_parent(oldtnode);
Alexander Duyck88bae712015-03-06 09:54:52 -0800668 put_child_root(tp, oldtnode->key, n);
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800669 node_set_parent(n, tp);
670
671 /* drop dead node */
672 node_free(oldtnode);
Alexander Duyck88bae712015-03-06 09:54:52 -0800673
674 return tp;
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800675}
676
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800677static unsigned char update_suffix(struct key_vector *tn)
Alexander Duyck5405afd2014-12-31 10:57:08 -0800678{
679 unsigned char slen = tn->pos;
680 unsigned long stride, i;
681
682 /* search though the list of children looking for nodes that might
683 * have a suffix greater than the one we currently have. This is
684 * why we start with a stride of 2 since a stride of 1 would
685 * represent the nodes with suffix length equal to tn->pos
686 */
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800687 for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
Alexander Duyck754baf82015-03-06 09:54:14 -0800688 struct key_vector *n = get_child(tn, i);
Alexander Duyck5405afd2014-12-31 10:57:08 -0800689
690 if (!n || (n->slen <= slen))
691 continue;
692
693 /* update stride and slen based on new value */
694 stride <<= (n->slen - slen);
695 slen = n->slen;
696 i &= ~(stride - 1);
697
698 /* if slen covers all but the last bit we can stop here
699 * there will be nothing longer than that since only node
700 * 0 and 1 << (bits - 1) could have that as their suffix
701 * length.
702 */
703 if ((slen + 1) >= (tn->pos + tn->bits))
704 break;
705 }
706
707 tn->slen = slen;
708
709 return slen;
710}
711
Alexander Duyckf05a4812014-12-31 10:56:37 -0800712/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
713 * the Helsinki University of Technology and Matti Tikkanen of Nokia
714 * Telecommunications, page 6:
715 * "A node is doubled if the ratio of non-empty children to all
716 * children in the *doubled* node is at least 'high'."
717 *
718 * 'high' in this instance is the variable 'inflate_threshold'. It
719 * is expressed as a percentage, so we multiply it with
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800720 * child_length() and instead of multiplying by 2 (since the
Alexander Duyckf05a4812014-12-31 10:56:37 -0800721 * child array will be doubled by inflate()) and multiplying
722 * the left-hand side by 100 (to handle the percentage thing) we
723 * multiply the left-hand side by 50.
724 *
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800725 * The left-hand side may look a bit weird: child_length(tn)
Alexander Duyckf05a4812014-12-31 10:56:37 -0800726 * - tn->empty_children is of course the number of non-null children
727 * in the current node. tn->full_children is the number of "full"
728 * children, that is non-null tnodes with a skip value of 0.
729 * All of those will be doubled in the resulting inflated tnode, so
730 * we just count them one extra time here.
731 *
732 * A clearer way to write this would be:
733 *
734 * to_be_doubled = tn->full_children;
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800735 * not_to_be_doubled = child_length(tn) - tn->empty_children -
Alexander Duyckf05a4812014-12-31 10:56:37 -0800736 * tn->full_children;
737 *
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800738 * new_child_length = child_length(tn) * 2;
Alexander Duyckf05a4812014-12-31 10:56:37 -0800739 *
740 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
741 * new_child_length;
742 * if (new_fill_factor >= inflate_threshold)
743 *
744 * ...and so on, tho it would mess up the while () loop.
745 *
746 * anyway,
747 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
748 * inflate_threshold
749 *
750 * avoid a division:
751 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
752 * inflate_threshold * new_child_length
753 *
754 * expand not_to_be_doubled and to_be_doubled, and shorten:
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800755 * 100 * (child_length(tn) - tn->empty_children +
Alexander Duyckf05a4812014-12-31 10:56:37 -0800756 * tn->full_children) >= inflate_threshold * new_child_length
757 *
758 * expand new_child_length:
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800759 * 100 * (child_length(tn) - tn->empty_children +
Alexander Duyckf05a4812014-12-31 10:56:37 -0800760 * tn->full_children) >=
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800761 * inflate_threshold * child_length(tn) * 2
Alexander Duyckf05a4812014-12-31 10:56:37 -0800762 *
763 * shorten again:
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800764 * 50 * (tn->full_children + child_length(tn) -
Alexander Duyckf05a4812014-12-31 10:56:37 -0800765 * tn->empty_children) >= inflate_threshold *
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800766 * child_length(tn)
Alexander Duyckf05a4812014-12-31 10:56:37 -0800767 *
768 */
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800769static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
Alexander Duyckf05a4812014-12-31 10:56:37 -0800770{
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800771 unsigned long used = child_length(tn);
Alexander Duyckf05a4812014-12-31 10:56:37 -0800772 unsigned long threshold = used;
773
774 /* Keep root node larger */
Alexander Duyck88bae712015-03-06 09:54:52 -0800775 threshold *= IS_TRIE(tp) ? inflate_threshold_root : inflate_threshold;
Alexander Duyck6e22d172015-03-06 09:54:39 -0800776 used -= tn_info(tn)->empty_children;
777 used += tn_info(tn)->full_children;
Alexander Duyckf05a4812014-12-31 10:56:37 -0800778
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800779 /* if bits == KEYLENGTH then pos = 0, and will fail below */
780
781 return (used > 1) && tn->pos && ((50 * used) >= threshold);
Alexander Duyckf05a4812014-12-31 10:56:37 -0800782}
783
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800784static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
Alexander Duyckf05a4812014-12-31 10:56:37 -0800785{
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800786 unsigned long used = child_length(tn);
Alexander Duyckf05a4812014-12-31 10:56:37 -0800787 unsigned long threshold = used;
788
789 /* Keep root node larger */
Alexander Duyck88bae712015-03-06 09:54:52 -0800790 threshold *= IS_TRIE(tp) ? halve_threshold_root : halve_threshold;
Alexander Duyck6e22d172015-03-06 09:54:39 -0800791 used -= tn_info(tn)->empty_children;
Alexander Duyckf05a4812014-12-31 10:56:37 -0800792
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800793 /* if bits == KEYLENGTH then used = 100% on wrap, and will fail below */
794
795 return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
796}
797
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800798static inline bool should_collapse(struct key_vector *tn)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800799{
Alexander Duyck2e1ac882015-03-06 09:54:21 -0800800 unsigned long used = child_length(tn);
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800801
Alexander Duyck6e22d172015-03-06 09:54:39 -0800802 used -= tn_info(tn)->empty_children;
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800803
804 /* account for bits == KEYLENGTH case */
Alexander Duyck6e22d172015-03-06 09:54:39 -0800805 if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)
Alexander Duyck95f60ea2015-01-22 15:51:26 -0800806 used -= KEY_MAX;
807
808 /* One child or none, time to drop us from the trie */
809 return used < 2;
Alexander Duyckf05a4812014-12-31 10:56:37 -0800810}
811
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800812#define MAX_WORK 10
Alexander Duyck88bae712015-03-06 09:54:52 -0800813static struct key_vector *resize(struct trie *t, struct key_vector *tn)
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800814{
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800815#ifdef CONFIG_IP_FIB_TRIE_STATS
816 struct trie_use_stats __percpu *stats = t->stats;
817#endif
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800818 struct key_vector *tp = node_parent(tn);
Alexander Duyck88bae712015-03-06 09:54:52 -0800819 unsigned long cindex = get_index(tn->key, tp);
Alexander Duycka80e89d2015-01-22 15:51:20 -0800820 int max_work = MAX_WORK;
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800821
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800822 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
823 tn, inflate_threshold, halve_threshold);
824
Alexander Duyckff181ed2014-12-31 10:56:43 -0800825 /* track the tnode via the pointer from the parent instead of
826 * doing it ourselves. This way we can let RCU fully do its
827 * thing without us interfering
828 */
Alexander Duyck88bae712015-03-06 09:54:52 -0800829 BUG_ON(tn != get_child(tp, cindex));
Alexander Duyckff181ed2014-12-31 10:56:43 -0800830
Alexander Duyckf05a4812014-12-31 10:56:37 -0800831 /* Double as long as the resulting node has a number of
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800832 * nonempty nodes that are above the threshold.
833 */
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700834 while (should_inflate(tp, tn) && max_work) {
Alexander Duyck88bae712015-03-06 09:54:52 -0800835 tp = inflate(t, tn);
836 if (!tp) {
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800837#ifdef CONFIG_IP_FIB_TRIE_STATS
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800838 this_cpu_inc(stats->resize_node_skipped);
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800839#endif
840 break;
841 }
Alexander Duyckff181ed2014-12-31 10:56:43 -0800842
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700843 max_work--;
Alexander Duyck88bae712015-03-06 09:54:52 -0800844 tn = get_child(tp, cindex);
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800845 }
846
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700847 /* update parent in case inflate failed */
848 tp = node_parent(tn);
849
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800850 /* Return if at least one inflate is run */
851 if (max_work != MAX_WORK)
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700852 return tp;
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800853
Alexander Duyckf05a4812014-12-31 10:56:37 -0800854 /* Halve as long as the number of empty children in this
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800855 * node is above threshold.
856 */
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700857 while (should_halve(tp, tn) && max_work) {
Alexander Duyck88bae712015-03-06 09:54:52 -0800858 tp = halve(t, tn);
859 if (!tp) {
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800860#ifdef CONFIG_IP_FIB_TRIE_STATS
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800861 this_cpu_inc(stats->resize_node_skipped);
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800862#endif
863 break;
864 }
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800865
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700866 max_work--;
Alexander Duyck88bae712015-03-06 09:54:52 -0800867 tn = get_child(tp, cindex);
Alexander Duyckff181ed2014-12-31 10:56:43 -0800868 }
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800869
870 /* Only one child remains */
Alexander Duyck88bae712015-03-06 09:54:52 -0800871 if (should_collapse(tn))
872 return collapse(t, tn);
873
Alexander Duyckb6f15f82015-03-23 11:51:53 -0700874 /* update parent in case halve failed */
Alexander Duyck88bae712015-03-06 09:54:52 -0800875 tp = node_parent(tn);
Alexander Duyck5405afd2014-12-31 10:57:08 -0800876
877 /* Return if at least one deflate was run */
878 if (max_work != MAX_WORK)
Alexander Duyck88bae712015-03-06 09:54:52 -0800879 return tp;
Alexander Duyck5405afd2014-12-31 10:57:08 -0800880
881 /* push the suffix length to the parent node */
882 if (tn->slen > tn->pos) {
883 unsigned char slen = update_suffix(tn);
884
Alexander Duyck88bae712015-03-06 09:54:52 -0800885 if (slen > tp->slen)
Alexander Duyck5405afd2014-12-31 10:57:08 -0800886 tp->slen = slen;
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800887 }
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800888
Alexander Duyck88bae712015-03-06 09:54:52 -0800889 return tp;
Alexander Duyckcf3637b2014-12-31 10:56:31 -0800890}
891
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800892static void leaf_pull_suffix(struct key_vector *tp, struct key_vector *l)
Robert Olsson19baf832005-06-21 12:43:18 -0700893{
Alexander Duyck88bae712015-03-06 09:54:52 -0800894 while ((tp->slen > tp->pos) && (tp->slen > l->slen)) {
Alexander Duyck5405afd2014-12-31 10:57:08 -0800895 if (update_suffix(tp) > l->slen)
896 break;
897 tp = node_parent(tp);
898 }
899}
900
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800901static void leaf_push_suffix(struct key_vector *tn, struct key_vector *l)
Alexander Duyck5405afd2014-12-31 10:57:08 -0800902{
Alexander Duyck5405afd2014-12-31 10:57:08 -0800903 /* if this is a new leaf then tn will be NULL and we can sort
904 * out parent suffix lengths as a part of trie_rebalance
905 */
Alexander Duyck88bae712015-03-06 09:54:52 -0800906 while (tn->slen < l->slen) {
Alexander Duyck5405afd2014-12-31 10:57:08 -0800907 tn->slen = l->slen;
908 tn = node_parent(tn);
909 }
910}
911
Robert Olsson2373ce12005-08-25 13:01:29 -0700912/* rcu_read_lock needs to be hold by caller from readside */
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800913static struct key_vector *fib_find_node(struct trie *t,
914 struct key_vector **tp, u32 key)
Robert Olsson19baf832005-06-21 12:43:18 -0700915{
Alexander Duyck88bae712015-03-06 09:54:52 -0800916 struct key_vector *pn, *n = t->kv;
917 unsigned long index = 0;
Robert Olsson19baf832005-06-21 12:43:18 -0700918
Alexander Duyck88bae712015-03-06 09:54:52 -0800919 do {
920 pn = n;
921 n = get_child_rcu(n, index);
922
923 if (!n)
924 break;
925
926 index = get_cindex(key, n);
Alexander Duyck939afb02014-12-31 10:56:00 -0800927
928 /* This bit of code is a bit tricky but it combines multiple
929 * checks into a single check. The prefix consists of the
930 * prefix plus zeros for the bits in the cindex. The index
931 * is the difference between the key and this value. From
932 * this we can actually derive several pieces of data.
Alexander Duyckd4a975e2015-03-04 15:01:59 -0800933 * if (index >= (1ul << bits))
Alexander Duyck939afb02014-12-31 10:56:00 -0800934 * we have a mismatch in skip bits and failed
Alexander Duyckb3832112015-01-22 15:51:08 -0800935 * else
936 * we know the value is cindex
Alexander Duyckd4a975e2015-03-04 15:01:59 -0800937 *
938 * This check is safe even if bits == KEYLENGTH due to the
939 * fact that we can only allocate a node with 32 bits if a
940 * long is greater than 32 bits.
Alexander Duyck939afb02014-12-31 10:56:00 -0800941 */
Alexander Duyckd4a975e2015-03-04 15:01:59 -0800942 if (index >= (1ul << n->bits)) {
943 n = NULL;
944 break;
945 }
Alexander Duyck939afb02014-12-31 10:56:00 -0800946
Alexander Duyck88bae712015-03-06 09:54:52 -0800947 /* keep searching until we find a perfect match leaf or NULL */
948 } while (IS_TNODE(n));
Robert Olsson19baf832005-06-21 12:43:18 -0700949
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800950 *tp = pn;
Alexander Duyckd4a975e2015-03-04 15:01:59 -0800951
Alexander Duyck939afb02014-12-31 10:56:00 -0800952 return n;
Robert Olsson19baf832005-06-21 12:43:18 -0700953}
954
Alexander Duyck02525362015-01-22 15:51:39 -0800955/* Return the first fib alias matching TOS with
956 * priority less than or equal to PRIO.
957 */
Alexander Duyck79e5ad22015-02-25 15:31:51 -0800958static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen,
Alexander Duyck0b65bd92015-03-12 14:46:29 -0700959 u8 tos, u32 prio, u32 tb_id)
Alexander Duyck02525362015-01-22 15:51:39 -0800960{
961 struct fib_alias *fa;
962
963 if (!fah)
964 return NULL;
965
Alexander Duyck56315f92015-02-25 15:31:31 -0800966 hlist_for_each_entry(fa, fah, fa_list) {
Alexander Duyck79e5ad22015-02-25 15:31:51 -0800967 if (fa->fa_slen < slen)
968 continue;
969 if (fa->fa_slen != slen)
970 break;
Alexander Duyck0b65bd92015-03-12 14:46:29 -0700971 if (fa->tb_id > tb_id)
972 continue;
973 if (fa->tb_id != tb_id)
974 break;
Alexander Duyck02525362015-01-22 15:51:39 -0800975 if (fa->fa_tos > tos)
976 continue;
977 if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos)
978 return fa;
979 }
980
981 return NULL;
982}
983
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800984static void trie_rebalance(struct trie *t, struct key_vector *tn)
Robert Olsson19baf832005-06-21 12:43:18 -0700985{
Alexander Duyck88bae712015-03-06 09:54:52 -0800986 while (!IS_TRIE(tn))
987 tn = resize(t, tn);
Robert Olsson19baf832005-06-21 12:43:18 -0700988}
989
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800990static int fib_insert_node(struct trie *t, struct key_vector *tp,
Alexander Duyckd5d64872015-03-04 15:02:18 -0800991 struct fib_alias *new, t_key key)
Robert Olsson19baf832005-06-21 12:43:18 -0700992{
Alexander Duyck35c6eda2015-03-06 09:54:08 -0800993 struct key_vector *n, *l;
Alexander Duyck836a0122014-12-31 10:56:06 -0800994
Alexander Duyckd5d64872015-03-04 15:02:18 -0800995 l = leaf_new(key, new);
Alexander Duyck79e5ad22015-02-25 15:31:51 -0800996 if (!l)
Alexander Duyck8d8e8102015-03-06 09:54:02 -0800997 goto noleaf;
Alexander Duyckd5d64872015-03-04 15:02:18 -0800998
999 /* retrieve child from parent node */
Alexander Duyck88bae712015-03-06 09:54:52 -08001000 n = get_child(tp, get_index(key, tp));
Alexander Duyck836a0122014-12-31 10:56:06 -08001001
1002 /* Case 2: n is a LEAF or a TNODE and the key doesn't match.
1003 *
1004 * Add a new tnode here
1005 * first tnode need some special handling
1006 * leaves us in position for handling as case 3
1007 */
1008 if (n) {
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001009 struct key_vector *tn;
Alexander Duyck836a0122014-12-31 10:56:06 -08001010
Alexander Duycke9b44012014-12-31 10:56:12 -08001011 tn = tnode_new(key, __fls(key ^ n->key), 1);
Alexander Duyck8d8e8102015-03-06 09:54:02 -08001012 if (!tn)
1013 goto notnode;
Olof Johansson91b9a272005-08-09 20:24:39 -07001014
Alexander Duyck836a0122014-12-31 10:56:06 -08001015 /* initialize routes out of node */
1016 NODE_INIT_PARENT(tn, tp);
1017 put_child(tn, get_index(key, tn) ^ 1, n);
Robert Olsson19baf832005-06-21 12:43:18 -07001018
Alexander Duyck836a0122014-12-31 10:56:06 -08001019 /* start adding routes into the node */
Alexander Duyck88bae712015-03-06 09:54:52 -08001020 put_child_root(tp, key, tn);
Alexander Duyck836a0122014-12-31 10:56:06 -08001021 node_set_parent(n, tn);
Robert Olsson19baf832005-06-21 12:43:18 -07001022
Alexander Duyck836a0122014-12-31 10:56:06 -08001023 /* parent now has a NULL spot where the leaf can go */
Alexander Duycke962f302014-12-10 21:49:22 -08001024 tp = tn;
Robert Olsson19baf832005-06-21 12:43:18 -07001025 }
Olof Johansson91b9a272005-08-09 20:24:39 -07001026
Alexander Duyck836a0122014-12-31 10:56:06 -08001027 /* Case 3: n is NULL, and will just insert a new leaf */
Alexander Duyckd5d64872015-03-04 15:02:18 -08001028 NODE_INIT_PARENT(l, tp);
Alexander Duyck88bae712015-03-06 09:54:52 -08001029 put_child_root(tp, key, l);
Alexander Duyckd5d64872015-03-04 15:02:18 -08001030 trie_rebalance(t, tp);
Olof Johansson91b9a272005-08-09 20:24:39 -07001031
Alexander Duyckd5d64872015-03-04 15:02:18 -08001032 return 0;
Alexander Duyck8d8e8102015-03-06 09:54:02 -08001033notnode:
1034 node_free(l);
1035noleaf:
1036 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07001037}
1038
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001039static int fib_insert_alias(struct trie *t, struct key_vector *tp,
1040 struct key_vector *l, struct fib_alias *new,
Alexander Duyckd5d64872015-03-04 15:02:18 -08001041 struct fib_alias *fa, t_key key)
1042{
1043 if (!l)
1044 return fib_insert_node(t, tp, new, key);
1045
1046 if (fa) {
1047 hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
1048 } else {
1049 struct fib_alias *last;
1050
1051 hlist_for_each_entry(last, &l->leaf, fa_list) {
1052 if (new->fa_slen < last->fa_slen)
1053 break;
Alexander Duyck0b65bd92015-03-12 14:46:29 -07001054 if ((new->fa_slen == last->fa_slen) &&
1055 (new->tb_id > last->tb_id))
1056 break;
Alexander Duyckd5d64872015-03-04 15:02:18 -08001057 fa = last;
1058 }
1059
1060 if (fa)
1061 hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
1062 else
1063 hlist_add_head_rcu(&new->fa_list, &l->leaf);
1064 }
1065
1066 /* if we added to the tail node then we need to update slen */
1067 if (l->slen < new->fa_slen) {
1068 l->slen = new->fa_slen;
1069 leaf_push_suffix(tp, l);
1070 }
1071
1072 return 0;
1073}
1074
1075/* Caller must hold RTNL. */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001076int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001077{
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001078 struct trie *t = (struct trie *)tb->tb_data;
Robert Olsson19baf832005-06-21 12:43:18 -07001079 struct fib_alias *fa, *new_fa;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001080 struct key_vector *l, *tp;
Robert Olsson19baf832005-06-21 12:43:18 -07001081 struct fib_info *fi;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001082 u8 plen = cfg->fc_dst_len;
1083 u8 slen = KEYLENGTH - plen;
Thomas Graf4e902c52006-08-17 18:14:52 -07001084 u8 tos = cfg->fc_tos;
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001085 u32 key;
Robert Olsson19baf832005-06-21 12:43:18 -07001086 int err;
Robert Olsson19baf832005-06-21 12:43:18 -07001087
Alexander Duyck5786ec62015-02-25 15:31:37 -08001088 if (plen > KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -07001089 return -EINVAL;
1090
Thomas Graf4e902c52006-08-17 18:14:52 -07001091 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001092
Patrick McHardy2dfe55b2006-08-10 23:08:33 -07001093 pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);
Robert Olsson19baf832005-06-21 12:43:18 -07001094
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001095 if ((plen < KEYLENGTH) && (key << plen))
Robert Olsson19baf832005-06-21 12:43:18 -07001096 return -EINVAL;
1097
Thomas Graf4e902c52006-08-17 18:14:52 -07001098 fi = fib_create_info(cfg);
1099 if (IS_ERR(fi)) {
1100 err = PTR_ERR(fi);
Robert Olsson19baf832005-06-21 12:43:18 -07001101 goto err;
Thomas Graf4e902c52006-08-17 18:14:52 -07001102 }
Robert Olsson19baf832005-06-21 12:43:18 -07001103
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001104 l = fib_find_node(t, &tp, key);
Alexander Duyck0b65bd92015-03-12 14:46:29 -07001105 fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority,
1106 tb->tb_id) : NULL;
Robert Olsson19baf832005-06-21 12:43:18 -07001107
1108 /* Now fa, if non-NULL, points to the first fib alias
1109 * with the same keys [prefix,tos,priority], if such key already
1110 * exists or to the node before which we will insert new one.
1111 *
1112 * If fa is NULL, we will need to allocate a new one and
Alexander Duyck56315f92015-02-25 15:31:31 -08001113 * insert to the tail of the section matching the suffix length
1114 * of the new alias.
Robert Olsson19baf832005-06-21 12:43:18 -07001115 */
1116
Julian Anastasov936f6f82008-01-28 21:18:06 -08001117 if (fa && fa->fa_tos == tos &&
1118 fa->fa_info->fib_priority == fi->fib_priority) {
1119 struct fib_alias *fa_first, *fa_match;
Robert Olsson19baf832005-06-21 12:43:18 -07001120
1121 err = -EEXIST;
Thomas Graf4e902c52006-08-17 18:14:52 -07001122 if (cfg->fc_nlflags & NLM_F_EXCL)
Robert Olsson19baf832005-06-21 12:43:18 -07001123 goto out;
1124
Julian Anastasov936f6f82008-01-28 21:18:06 -08001125 /* We have 2 goals:
1126 * 1. Find exact match for type, scope, fib_info to avoid
1127 * duplicate routes
1128 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
1129 */
1130 fa_match = NULL;
1131 fa_first = fa;
Alexander Duyck56315f92015-02-25 15:31:31 -08001132 hlist_for_each_entry_from(fa, fa_list) {
Alexander Duyck0b65bd92015-03-12 14:46:29 -07001133 if ((fa->fa_slen != slen) ||
1134 (fa->tb_id != tb->tb_id) ||
1135 (fa->fa_tos != tos))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001136 break;
1137 if (fa->fa_info->fib_priority != fi->fib_priority)
1138 break;
1139 if (fa->fa_type == cfg->fc_type &&
Julian Anastasov936f6f82008-01-28 21:18:06 -08001140 fa->fa_info == fi) {
1141 fa_match = fa;
1142 break;
1143 }
1144 }
1145
Thomas Graf4e902c52006-08-17 18:14:52 -07001146 if (cfg->fc_nlflags & NLM_F_REPLACE) {
Robert Olsson19baf832005-06-21 12:43:18 -07001147 struct fib_info *fi_drop;
1148 u8 state;
1149
Julian Anastasov936f6f82008-01-28 21:18:06 -08001150 fa = fa_first;
1151 if (fa_match) {
1152 if (fa == fa_match)
1153 err = 0;
Joonwoo Park67250332008-01-18 03:45:18 -08001154 goto out;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001155 }
Robert Olsson2373ce12005-08-25 13:01:29 -07001156 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001157 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Ian Morris51456b22015-04-03 09:17:26 +01001158 if (!new_fa)
Robert Olsson2373ce12005-08-25 13:01:29 -07001159 goto out;
Robert Olsson19baf832005-06-21 12:43:18 -07001160
1161 fi_drop = fa->fa_info;
Robert Olsson2373ce12005-08-25 13:01:29 -07001162 new_fa->fa_tos = fa->fa_tos;
1163 new_fa->fa_info = fi;
Thomas Graf4e902c52006-08-17 18:14:52 -07001164 new_fa->fa_type = cfg->fc_type;
Robert Olsson19baf832005-06-21 12:43:18 -07001165 state = fa->fa_state;
Julian Anastasov936f6f82008-01-28 21:18:06 -08001166 new_fa->fa_state = state & ~FA_S_ACCESSED;
Alexander Duyck9b6ebad2015-02-25 15:31:44 -08001167 new_fa->fa_slen = fa->fa_slen;
Michal Kubečekd4e64c22015-05-22 13:40:09 +02001168 new_fa->tb_id = tb->tb_id;
Robert Olsson19baf832005-06-21 12:43:18 -07001169
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001170 err = switchdev_fib_ipv4_add(key, plen, fi,
1171 new_fa->fa_tos,
1172 cfg->fc_type,
1173 cfg->fc_nlflags,
1174 tb->tb_id);
Scott Feldman8e05fd72015-03-05 21:21:19 -08001175 if (err) {
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001176 switchdev_fib_ipv4_abort(fi);
Scott Feldman8e05fd72015-03-05 21:21:19 -08001177 kmem_cache_free(fn_alias_kmem, new_fa);
1178 goto out;
1179 }
1180
Alexander Duyck56315f92015-02-25 15:31:31 -08001181 hlist_replace_rcu(&fa->fa_list, &new_fa->fa_list);
Scott Feldman8e05fd72015-03-05 21:21:19 -08001182
Robert Olsson2373ce12005-08-25 13:01:29 -07001183 alias_free_mem_rcu(fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001184
1185 fib_release_info(fi_drop);
1186 if (state & FA_S_ACCESSED)
Nicolas Dichtel4ccfe6d2012-09-07 00:45:29 +00001187 rt_cache_flush(cfg->fc_nlinfo.nl_net);
Milan Kocianb8f55832007-05-23 14:55:06 -07001188 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
1189 tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);
Robert Olsson19baf832005-06-21 12:43:18 -07001190
Olof Johansson91b9a272005-08-09 20:24:39 -07001191 goto succeeded;
Robert Olsson19baf832005-06-21 12:43:18 -07001192 }
1193 /* Error if we find a perfect match which
1194 * uses the same scope, type, and nexthop
1195 * information.
1196 */
Julian Anastasov936f6f82008-01-28 21:18:06 -08001197 if (fa_match)
1198 goto out;
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001199
Thomas Graf4e902c52006-08-17 18:14:52 -07001200 if (!(cfg->fc_nlflags & NLM_F_APPEND))
Julian Anastasov936f6f82008-01-28 21:18:06 -08001201 fa = fa_first;
Robert Olsson19baf832005-06-21 12:43:18 -07001202 }
1203 err = -ENOENT;
Thomas Graf4e902c52006-08-17 18:14:52 -07001204 if (!(cfg->fc_nlflags & NLM_F_CREATE))
Robert Olsson19baf832005-06-21 12:43:18 -07001205 goto out;
1206
1207 err = -ENOBUFS;
Christoph Lametere94b1762006-12-06 20:33:17 -08001208 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
Ian Morris51456b22015-04-03 09:17:26 +01001209 if (!new_fa)
Robert Olsson19baf832005-06-21 12:43:18 -07001210 goto out;
1211
1212 new_fa->fa_info = fi;
1213 new_fa->fa_tos = tos;
Thomas Graf4e902c52006-08-17 18:14:52 -07001214 new_fa->fa_type = cfg->fc_type;
Robert Olsson19baf832005-06-21 12:43:18 -07001215 new_fa->fa_state = 0;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001216 new_fa->fa_slen = slen;
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001217 new_fa->tb_id = tb->tb_id;
Robert Olsson19baf832005-06-21 12:43:18 -07001218
Scott Feldman8e05fd72015-03-05 21:21:19 -08001219 /* (Optionally) offload fib entry to switch hardware. */
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001220 err = switchdev_fib_ipv4_add(key, plen, fi, tos, cfg->fc_type,
1221 cfg->fc_nlflags, tb->tb_id);
Scott Feldman8e05fd72015-03-05 21:21:19 -08001222 if (err) {
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001223 switchdev_fib_ipv4_abort(fi);
Scott Feldman8e05fd72015-03-05 21:21:19 -08001224 goto out_free_new_fa;
1225 }
1226
Alexander Duyck9b6ebad2015-02-25 15:31:44 -08001227 /* Insert new entry to the list. */
Alexander Duyckd5d64872015-03-04 15:02:18 -08001228 err = fib_insert_alias(t, tp, l, new_fa, fa, key);
1229 if (err)
Scott Feldman8e05fd72015-03-05 21:21:19 -08001230 goto out_sw_fib_del;
Robert Olsson19baf832005-06-21 12:43:18 -07001231
David S. Miller21d8c492011-04-14 14:49:37 -07001232 if (!plen)
1233 tb->tb_num_default++;
1234
Nicolas Dichtel4ccfe6d2012-09-07 00:45:29 +00001235 rt_cache_flush(cfg->fc_nlinfo.nl_net);
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001236 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, new_fa->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001237 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001238succeeded:
1239 return 0;
Robert Olssonf835e472005-06-28 15:00:39 -07001240
Scott Feldman8e05fd72015-03-05 21:21:19 -08001241out_sw_fib_del:
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001242 switchdev_fib_ipv4_del(key, plen, fi, tos, cfg->fc_type, tb->tb_id);
Robert Olssonf835e472005-06-28 15:00:39 -07001243out_free_new_fa:
1244 kmem_cache_free(fn_alias_kmem, new_fa);
Robert Olsson19baf832005-06-21 12:43:18 -07001245out:
1246 fib_release_info(fi);
Olof Johansson91b9a272005-08-09 20:24:39 -07001247err:
Robert Olsson19baf832005-06-21 12:43:18 -07001248 return err;
1249}
1250
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001251static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001252{
1253 t_key prefix = n->key;
1254
1255 return (key ^ prefix) & (prefix | -prefix);
1256}
1257
Alexander Duyck345e9b52014-12-31 10:56:24 -08001258/* should be called with rcu_read_lock */
David S. Miller22bd5b92011-03-11 19:54:08 -05001259int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
Eric Dumazetebc0ffa2010-10-05 10:41:36 +00001260 struct fib_result *res, int fib_flags)
Robert Olsson19baf832005-06-21 12:43:18 -07001261{
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001262 struct trie *t = (struct trie *) tb->tb_data;
Alexander Duyck8274a972014-12-31 10:55:29 -08001263#ifdef CONFIG_IP_FIB_TRIE_STATS
1264 struct trie_use_stats __percpu *stats = t->stats;
1265#endif
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001266 const t_key key = ntohl(flp->daddr);
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001267 struct key_vector *n, *pn;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001268 struct fib_alias *fa;
Alexander Duyck71e8b672015-03-04 15:04:03 -08001269 unsigned long index;
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001270 t_key cindex;
Robert Olsson19baf832005-06-21 12:43:18 -07001271
Alexander Duyck88bae712015-03-06 09:54:52 -08001272 pn = t->kv;
1273 cindex = 0;
1274
1275 n = get_child_rcu(pn, cindex);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001276 if (!n)
Alexander Duyck345e9b52014-12-31 10:56:24 -08001277 return -EAGAIN;
Robert Olsson19baf832005-06-21 12:43:18 -07001278
1279#ifdef CONFIG_IP_FIB_TRIE_STATS
Alexander Duyck8274a972014-12-31 10:55:29 -08001280 this_cpu_inc(stats->gets);
Robert Olsson19baf832005-06-21 12:43:18 -07001281#endif
1282
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001283 /* Step 1: Travel to the longest prefix match in the trie */
1284 for (;;) {
Alexander Duyck88bae712015-03-06 09:54:52 -08001285 index = get_cindex(key, n);
Robert Olsson19baf832005-06-21 12:43:18 -07001286
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001287 /* This bit of code is a bit tricky but it combines multiple
1288 * checks into a single check. The prefix consists of the
1289 * prefix plus zeros for the "bits" in the prefix. The index
1290 * is the difference between the key and this value. From
1291 * this we can actually derive several pieces of data.
Alexander Duyck71e8b672015-03-04 15:04:03 -08001292 * if (index >= (1ul << bits))
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001293 * we have a mismatch in skip bits and failed
Alexander Duyckb3832112015-01-22 15:51:08 -08001294 * else
1295 * we know the value is cindex
Alexander Duyck71e8b672015-03-04 15:04:03 -08001296 *
1297 * This check is safe even if bits == KEYLENGTH due to the
1298 * fact that we can only allocate a node with 32 bits if a
1299 * long is greater than 32 bits.
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001300 */
Alexander Duyck71e8b672015-03-04 15:04:03 -08001301 if (index >= (1ul << n->bits))
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001302 break;
Robert Olsson19baf832005-06-21 12:43:18 -07001303
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001304 /* we have found a leaf. Prefixes have already been compared */
1305 if (IS_LEAF(n))
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001306 goto found;
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001307
1308 /* only record pn and cindex if we are going to be chopping
1309 * bits later. Otherwise we are just wasting cycles.
1310 */
Alexander Duyck5405afd2014-12-31 10:57:08 -08001311 if (n->slen > n->pos) {
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001312 pn = n;
1313 cindex = index;
Olof Johansson91b9a272005-08-09 20:24:39 -07001314 }
1315
Alexander Duyck754baf82015-03-06 09:54:14 -08001316 n = get_child_rcu(n, index);
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001317 if (unlikely(!n))
Robert Olsson19baf832005-06-21 12:43:18 -07001318 goto backtrace;
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001319 }
1320
1321 /* Step 2: Sort out leaves and begin backtracing for longest prefix */
1322 for (;;) {
1323 /* record the pointer where our next node pointer is stored */
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001324 struct key_vector __rcu **cptr = n->tnode;
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001325
1326 /* This test verifies that none of the bits that differ
1327 * between the key and the prefix exist in the region of
1328 * the lsb and higher in the prefix.
1329 */
Alexander Duyck5405afd2014-12-31 10:57:08 -08001330 if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001331 goto backtrace;
1332
1333 /* exit out and process leaf */
1334 if (unlikely(IS_LEAF(n)))
1335 break;
1336
1337 /* Don't bother recording parent info. Since we are in
1338 * prefix match mode we will have to come back to wherever
1339 * we started this traversal anyway
1340 */
1341
1342 while ((n = rcu_dereference(*cptr)) == NULL) {
1343backtrace:
1344#ifdef CONFIG_IP_FIB_TRIE_STATS
1345 if (!n)
1346 this_cpu_inc(stats->null_node_hit);
1347#endif
1348 /* If we are at cindex 0 there are no more bits for
1349 * us to strip at this level so we must ascend back
1350 * up one level to see if there are any more bits to
1351 * be stripped there.
1352 */
1353 while (!cindex) {
1354 t_key pkey = pn->key;
1355
Alexander Duyck88bae712015-03-06 09:54:52 -08001356 /* If we don't have a parent then there is
1357 * nothing for us to do as we do not have any
1358 * further nodes to parse.
1359 */
1360 if (IS_TRIE(pn))
Alexander Duyck345e9b52014-12-31 10:56:24 -08001361 return -EAGAIN;
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001362#ifdef CONFIG_IP_FIB_TRIE_STATS
1363 this_cpu_inc(stats->backtrack);
1364#endif
1365 /* Get Child's index */
Alexander Duyck88bae712015-03-06 09:54:52 -08001366 pn = node_parent_rcu(pn);
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001367 cindex = get_index(pkey, pn);
1368 }
1369
1370 /* strip the least significant bit from the cindex */
1371 cindex &= cindex - 1;
1372
1373 /* grab pointer for next child node */
Alexander Duyck41b489f2015-03-04 15:02:33 -08001374 cptr = &pn->tnode[cindex];
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001375 }
Robert Olsson19baf832005-06-21 12:43:18 -07001376 }
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001377
Robert Olsson19baf832005-06-21 12:43:18 -07001378found:
Alexander Duyck71e8b672015-03-04 15:04:03 -08001379 /* this line carries forward the xor from earlier in the function */
1380 index = key ^ n->key;
1381
Alexander Duyck9f9e6362014-12-31 10:55:54 -08001382 /* Step 3: Process the leaf, if that fails fall back to backtracing */
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001383 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
1384 struct fib_info *fi = fa->fa_info;
1385 int nhsel, err;
Alexander Duyck345e9b52014-12-31 10:56:24 -08001386
Alexander Duyck71e8b672015-03-04 15:04:03 -08001387 if ((index >= (1ul << fa->fa_slen)) &&
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001388 ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen != KEYLENGTH)))
Alexander Duyck71e8b672015-03-04 15:04:03 -08001389 continue;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001390 if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
1391 continue;
1392 if (fi->fib_dead)
1393 continue;
1394 if (fa->fa_info->fib_scope < flp->flowi4_scope)
1395 continue;
1396 fib_alias_accessed(fa);
1397 err = fib_props[fa->fa_type].error;
1398 if (unlikely(err < 0)) {
Alexander Duyck345e9b52014-12-31 10:56:24 -08001399#ifdef CONFIG_IP_FIB_TRIE_STATS
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001400 this_cpu_inc(stats->semantic_match_passed);
Alexander Duyck345e9b52014-12-31 10:56:24 -08001401#endif
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001402 return err;
1403 }
1404 if (fi->fib_flags & RTNH_F_DEAD)
1405 continue;
1406 for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
1407 const struct fib_nh *nh = &fi->fib_nh[nhsel];
1408
1409 if (nh->nh_flags & RTNH_F_DEAD)
Alexander Duyck345e9b52014-12-31 10:56:24 -08001410 continue;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001411 if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
1412 continue;
Alexander Duyck345e9b52014-12-31 10:56:24 -08001413
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001414 if (!(fib_flags & FIB_LOOKUP_NOREF))
1415 atomic_inc(&fi->fib_clntref);
Alexander Duyck345e9b52014-12-31 10:56:24 -08001416
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001417 res->prefixlen = KEYLENGTH - fa->fa_slen;
1418 res->nh_sel = nhsel;
1419 res->type = fa->fa_type;
1420 res->scope = fi->fib_scope;
1421 res->fi = fi;
1422 res->table = tb;
1423 res->fa_head = &n->leaf;
Alexander Duyck345e9b52014-12-31 10:56:24 -08001424#ifdef CONFIG_IP_FIB_TRIE_STATS
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001425 this_cpu_inc(stats->semantic_match_passed);
Alexander Duyck345e9b52014-12-31 10:56:24 -08001426#endif
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001427 return err;
Alexander Duyck345e9b52014-12-31 10:56:24 -08001428 }
Alexander Duyck345e9b52014-12-31 10:56:24 -08001429 }
Alexander Duyck9b6ebad2015-02-25 15:31:44 -08001430#ifdef CONFIG_IP_FIB_TRIE_STATS
1431 this_cpu_inc(stats->semantic_match_miss);
1432#endif
Alexander Duyck345e9b52014-12-31 10:56:24 -08001433 goto backtrace;
Robert Olsson19baf832005-06-21 12:43:18 -07001434}
Florian Westphal6fc01432011-08-25 13:46:12 +02001435EXPORT_SYMBOL_GPL(fib_table_lookup);
Robert Olsson19baf832005-06-21 12:43:18 -07001436
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001437static void fib_remove_alias(struct trie *t, struct key_vector *tp,
1438 struct key_vector *l, struct fib_alias *old)
Alexander Duyckd5d64872015-03-04 15:02:18 -08001439{
1440 /* record the location of the previous list_info entry */
1441 struct hlist_node **pprev = old->fa_list.pprev;
1442 struct fib_alias *fa = hlist_entry(pprev, typeof(*fa), fa_list.next);
1443
1444 /* remove the fib_alias from the list */
1445 hlist_del_rcu(&old->fa_list);
1446
1447 /* if we emptied the list this leaf will be freed and we can sort
1448 * out parent suffix lengths as a part of trie_rebalance
1449 */
1450 if (hlist_empty(&l->leaf)) {
Alexander Duyck88bae712015-03-06 09:54:52 -08001451 put_child_root(tp, l->key, NULL);
Alexander Duyckd5d64872015-03-04 15:02:18 -08001452 node_free(l);
1453 trie_rebalance(t, tp);
1454 return;
1455 }
1456
1457 /* only access fa if it is pointing at the last valid hlist_node */
1458 if (*pprev)
1459 return;
1460
1461 /* update the trie with the latest suffix length */
1462 l->slen = fa->fa_slen;
1463 leaf_pull_suffix(tp, l);
1464}
1465
1466/* Caller must hold RTNL. */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001467int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
Robert Olsson19baf832005-06-21 12:43:18 -07001468{
1469 struct trie *t = (struct trie *) tb->tb_data;
Robert Olsson19baf832005-06-21 12:43:18 -07001470 struct fib_alias *fa, *fa_to_delete;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001471 struct key_vector *l, *tp;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001472 u8 plen = cfg->fc_dst_len;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001473 u8 slen = KEYLENGTH - plen;
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001474 u8 tos = cfg->fc_tos;
1475 u32 key;
Olof Johansson91b9a272005-08-09 20:24:39 -07001476
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001477 if (plen > KEYLENGTH)
Robert Olsson19baf832005-06-21 12:43:18 -07001478 return -EINVAL;
1479
Thomas Graf4e902c52006-08-17 18:14:52 -07001480 key = ntohl(cfg->fc_dst);
Robert Olsson19baf832005-06-21 12:43:18 -07001481
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001482 if ((plen < KEYLENGTH) && (key << plen))
Robert Olsson19baf832005-06-21 12:43:18 -07001483 return -EINVAL;
1484
Alexander Duyckd4a975e2015-03-04 15:01:59 -08001485 l = fib_find_node(t, &tp, key);
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07001486 if (!l)
Robert Olsson19baf832005-06-21 12:43:18 -07001487 return -ESRCH;
1488
Alexander Duyck0b65bd92015-03-12 14:46:29 -07001489 fa = fib_find_alias(&l->leaf, slen, tos, 0, tb->tb_id);
Robert Olsson19baf832005-06-21 12:43:18 -07001490 if (!fa)
1491 return -ESRCH;
1492
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001493 pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
Robert Olsson19baf832005-06-21 12:43:18 -07001494
1495 fa_to_delete = NULL;
Alexander Duyck56315f92015-02-25 15:31:31 -08001496 hlist_for_each_entry_from(fa, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001497 struct fib_info *fi = fa->fa_info;
1498
Alexander Duyck0b65bd92015-03-12 14:46:29 -07001499 if ((fa->fa_slen != slen) ||
1500 (fa->tb_id != tb->tb_id) ||
1501 (fa->fa_tos != tos))
Robert Olsson19baf832005-06-21 12:43:18 -07001502 break;
1503
Thomas Graf4e902c52006-08-17 18:14:52 -07001504 if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
1505 (cfg->fc_scope == RT_SCOPE_NOWHERE ||
David S. Miller37e826c2011-03-24 18:06:47 -07001506 fa->fa_info->fib_scope == cfg->fc_scope) &&
Julian Anastasov74cb3c12011-03-19 12:13:46 +00001507 (!cfg->fc_prefsrc ||
1508 fi->fib_prefsrc == cfg->fc_prefsrc) &&
Thomas Graf4e902c52006-08-17 18:14:52 -07001509 (!cfg->fc_protocol ||
1510 fi->fib_protocol == cfg->fc_protocol) &&
1511 fib_nh_match(cfg, fi) == 0) {
Robert Olsson19baf832005-06-21 12:43:18 -07001512 fa_to_delete = fa;
1513 break;
1514 }
1515 }
1516
Olof Johansson91b9a272005-08-09 20:24:39 -07001517 if (!fa_to_delete)
1518 return -ESRCH;
Robert Olsson19baf832005-06-21 12:43:18 -07001519
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001520 switchdev_fib_ipv4_del(key, plen, fa_to_delete->fa_info, tos,
1521 cfg->fc_type, tb->tb_id);
Scott Feldman8e05fd72015-03-05 21:21:19 -08001522
Alexander Duyckd5d64872015-03-04 15:02:18 -08001523 rtmsg_fib(RTM_DELROUTE, htonl(key), fa_to_delete, plen, tb->tb_id,
Milan Kocianb8f55832007-05-23 14:55:06 -07001524 &cfg->fc_nlinfo, 0);
Robert Olsson19baf832005-06-21 12:43:18 -07001525
David S. Miller21d8c492011-04-14 14:49:37 -07001526 if (!plen)
1527 tb->tb_num_default--;
1528
Alexander Duyckd5d64872015-03-04 15:02:18 -08001529 fib_remove_alias(t, tp, l, fa_to_delete);
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001530
Alexander Duyckd5d64872015-03-04 15:02:18 -08001531 if (fa_to_delete->fa_state & FA_S_ACCESSED)
Nicolas Dichtel4ccfe6d2012-09-07 00:45:29 +00001532 rt_cache_flush(cfg->fc_nlinfo.nl_net);
Olof Johansson91b9a272005-08-09 20:24:39 -07001533
Alexander Duyckd5d64872015-03-04 15:02:18 -08001534 fib_release_info(fa_to_delete->fa_info);
1535 alias_free_mem_rcu(fa_to_delete);
Olof Johansson91b9a272005-08-09 20:24:39 -07001536 return 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001537}
1538
Alexander Duyck8be33e92015-03-04 14:59:19 -08001539/* Scan for the next leaf starting at the provided key value */
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001540static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
Robert Olsson19baf832005-06-21 12:43:18 -07001541{
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001542 struct key_vector *pn, *n = *tn;
Alexander Duyck8be33e92015-03-04 14:59:19 -08001543 unsigned long cindex;
Robert Olsson19baf832005-06-21 12:43:18 -07001544
Alexander Duyck8be33e92015-03-04 14:59:19 -08001545 /* this loop is meant to try and find the key in the trie */
Alexander Duyck88bae712015-03-06 09:54:52 -08001546 do {
1547 /* record parent and next child index */
1548 pn = n;
Alexander Duyck3ec320d2015-03-10 11:25:41 -07001549 cindex = key ? get_index(key, pn) : 0;
Alexander Duyck88bae712015-03-06 09:54:52 -08001550
1551 if (cindex >> pn->bits)
1552 break;
1553
1554 /* descend into the next child */
1555 n = get_child_rcu(pn, cindex++);
1556 if (!n)
1557 break;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001558
Alexander Duyck8be33e92015-03-04 14:59:19 -08001559 /* guarantee forward progress on the keys */
1560 if (IS_LEAF(n) && (n->key >= key))
1561 goto found;
Alexander Duyck88bae712015-03-06 09:54:52 -08001562 } while (IS_TNODE(n));
Alexander Duyck8be33e92015-03-04 14:59:19 -08001563
1564 /* this loop will search for the next leaf with a greater key */
Alexander Duyck88bae712015-03-06 09:54:52 -08001565 while (!IS_TRIE(pn)) {
Alexander Duyck8be33e92015-03-04 14:59:19 -08001566 /* if we exhausted the parent node we will need to climb */
1567 if (cindex >= (1ul << pn->bits)) {
1568 t_key pkey = pn->key;
1569
1570 pn = node_parent_rcu(pn);
Alexander Duyck8be33e92015-03-04 14:59:19 -08001571 cindex = get_index(pkey, pn) + 1;
1572 continue;
Robert Olsson19baf832005-06-21 12:43:18 -07001573 }
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001574
Alexander Duyck8be33e92015-03-04 14:59:19 -08001575 /* grab the next available node */
Alexander Duyck754baf82015-03-06 09:54:14 -08001576 n = get_child_rcu(pn, cindex++);
Alexander Duyck8be33e92015-03-04 14:59:19 -08001577 if (!n)
1578 continue;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001579
Alexander Duyck8be33e92015-03-04 14:59:19 -08001580 /* no need to compare keys since we bumped the index */
1581 if (IS_LEAF(n))
1582 goto found;
1583
1584 /* Rescan start scanning in new node */
1585 pn = n;
1586 cindex = 0;
1587 }
1588
1589 *tn = pn;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001590 return NULL; /* Root of trie */
Alexander Duyck8be33e92015-03-04 14:59:19 -08001591found:
1592 /* if we are at the limit for keys just return NULL for the tnode */
Alexander Duyck88bae712015-03-06 09:54:52 -08001593 *tn = pn;
Alexander Duyck8be33e92015-03-04 14:59:19 -08001594 return n;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001595}
1596
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001597static void fib_trie_free(struct fib_table *tb)
1598{
1599 struct trie *t = (struct trie *)tb->tb_data;
1600 struct key_vector *pn = t->kv;
1601 unsigned long cindex = 1;
1602 struct hlist_node *tmp;
1603 struct fib_alias *fa;
1604
1605 /* walk trie in reverse order and free everything */
1606 for (;;) {
1607 struct key_vector *n;
1608
1609 if (!(cindex--)) {
1610 t_key pkey = pn->key;
1611
1612 if (IS_TRIE(pn))
1613 break;
1614
1615 n = pn;
1616 pn = node_parent(pn);
1617
1618 /* drop emptied tnode */
1619 put_child_root(pn, n->key, NULL);
1620 node_free(n);
1621
1622 cindex = get_index(pkey, pn);
1623
1624 continue;
1625 }
1626
1627 /* grab the next available node */
1628 n = get_child(pn, cindex);
1629 if (!n)
1630 continue;
1631
1632 if (IS_TNODE(n)) {
1633 /* record pn and cindex for leaf walking */
1634 pn = n;
1635 cindex = 1ul << n->bits;
1636
1637 continue;
1638 }
1639
1640 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1641 hlist_del_rcu(&fa->fa_list);
1642 alias_free_mem_rcu(fa);
1643 }
1644
1645 put_child_root(pn, n->key, NULL);
1646 node_free(n);
1647 }
1648
1649#ifdef CONFIG_IP_FIB_TRIE_STATS
1650 free_percpu(t->stats);
1651#endif
1652 kfree(tb);
1653}
1654
1655struct fib_table *fib_trie_unmerge(struct fib_table *oldtb)
1656{
1657 struct trie *ot = (struct trie *)oldtb->tb_data;
1658 struct key_vector *l, *tp = ot->kv;
1659 struct fib_table *local_tb;
1660 struct fib_alias *fa;
1661 struct trie *lt;
1662 t_key key = 0;
1663
1664 if (oldtb->tb_data == oldtb->__data)
1665 return oldtb;
1666
1667 local_tb = fib_trie_table(RT_TABLE_LOCAL, NULL);
1668 if (!local_tb)
1669 return NULL;
1670
1671 lt = (struct trie *)local_tb->tb_data;
1672
1673 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
1674 struct key_vector *local_l = NULL, *local_tp;
1675
1676 hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
1677 struct fib_alias *new_fa;
1678
1679 if (local_tb->tb_id != fa->tb_id)
1680 continue;
1681
1682 /* clone fa for new local table */
1683 new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
1684 if (!new_fa)
1685 goto out;
1686
1687 memcpy(new_fa, fa, sizeof(*fa));
1688
1689 /* insert clone into table */
1690 if (!local_l)
1691 local_l = fib_find_node(lt, &local_tp, l->key);
1692
1693 if (fib_insert_alias(lt, local_tp, local_l, new_fa,
1694 NULL, l->key))
1695 goto out;
1696 }
1697
1698 /* stop loop if key wrapped back to 0 */
1699 key = l->key + 1;
1700 if (key < l->key)
1701 break;
1702 }
1703
1704 return local_tb;
1705out:
1706 fib_trie_free(local_tb);
1707
1708 return NULL;
1709}
1710
Scott Feldman104616e2015-03-05 21:21:16 -08001711/* Caller must hold RTNL */
1712void fib_table_flush_external(struct fib_table *tb)
1713{
1714 struct trie *t = (struct trie *)tb->tb_data;
Alexander Duyck88bae712015-03-06 09:54:52 -08001715 struct key_vector *pn = t->kv;
1716 unsigned long cindex = 1;
1717 struct hlist_node *tmp;
Scott Feldman104616e2015-03-05 21:21:16 -08001718 struct fib_alias *fa;
Scott Feldman104616e2015-03-05 21:21:16 -08001719
Alexander Duyck88bae712015-03-06 09:54:52 -08001720 /* walk trie in reverse order */
1721 for (;;) {
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001722 unsigned char slen = 0;
Alexander Duyck88bae712015-03-06 09:54:52 -08001723 struct key_vector *n;
Scott Feldman104616e2015-03-05 21:21:16 -08001724
Alexander Duyck88bae712015-03-06 09:54:52 -08001725 if (!(cindex--)) {
1726 t_key pkey = pn->key;
Scott Feldman104616e2015-03-05 21:21:16 -08001727
Alexander Duyck88bae712015-03-06 09:54:52 -08001728 /* cannot resize the trie vector */
1729 if (IS_TRIE(pn))
1730 break;
Scott Feldman104616e2015-03-05 21:21:16 -08001731
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001732 /* resize completed node */
1733 pn = resize(t, pn);
Alexander Duyck88bae712015-03-06 09:54:52 -08001734 cindex = get_index(pkey, pn);
Scott Feldman104616e2015-03-05 21:21:16 -08001735
Alexander Duyck88bae712015-03-06 09:54:52 -08001736 continue;
1737 }
Scott Feldman104616e2015-03-05 21:21:16 -08001738
Alexander Duyck88bae712015-03-06 09:54:52 -08001739 /* grab the next available node */
1740 n = get_child(pn, cindex);
1741 if (!n)
Alexander Duyck72be7262015-03-06 09:53:56 -08001742 continue;
1743
Alexander Duyck88bae712015-03-06 09:54:52 -08001744 if (IS_TNODE(n)) {
1745 /* record pn and cindex for leaf walking */
1746 pn = n;
1747 cindex = 1ul << n->bits;
Scott Feldman104616e2015-03-05 21:21:16 -08001748
Alexander Duyck88bae712015-03-06 09:54:52 -08001749 continue;
1750 }
1751
1752 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1753 struct fib_info *fi = fa->fa_info;
1754
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001755 /* if alias was cloned to local then we just
1756 * need to remove the local copy from main
1757 */
1758 if (tb->tb_id != fa->tb_id) {
1759 hlist_del_rcu(&fa->fa_list);
1760 alias_free_mem_rcu(fa);
1761 continue;
1762 }
1763
1764 /* record local slen */
1765 slen = fa->fa_slen;
1766
Roopa Prabhueea39942015-05-13 21:17:41 -07001767 if (!fi || !(fi->fib_flags & RTNH_F_OFFLOAD))
Alexander Duyck88bae712015-03-06 09:54:52 -08001768 continue;
1769
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001770 switchdev_fib_ipv4_del(n->key, KEYLENGTH - fa->fa_slen,
1771 fi, fa->fa_tos, fa->fa_type,
1772 tb->tb_id);
Alexander Duyck88bae712015-03-06 09:54:52 -08001773 }
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001774
1775 /* update leaf slen */
1776 n->slen = slen;
1777
1778 if (hlist_empty(&n->leaf)) {
1779 put_child_root(pn, n->key, NULL);
1780 node_free(n);
1781 } else {
1782 leaf_pull_suffix(pn, n);
1783 }
Alexander Duyck88bae712015-03-06 09:54:52 -08001784 }
Scott Feldman104616e2015-03-05 21:21:16 -08001785}
1786
Alexander Duyck8be33e92015-03-04 14:59:19 -08001787/* Caller must hold RTNL. */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001788int fib_table_flush(struct fib_table *tb)
Robert Olsson19baf832005-06-21 12:43:18 -07001789{
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001790 struct trie *t = (struct trie *)tb->tb_data;
Alexander Duyck88bae712015-03-06 09:54:52 -08001791 struct key_vector *pn = t->kv;
1792 unsigned long cindex = 1;
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001793 struct hlist_node *tmp;
1794 struct fib_alias *fa;
Stephen Hemminger82cfbb02008-01-22 21:55:32 -08001795 int found = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07001796
Alexander Duyck88bae712015-03-06 09:54:52 -08001797 /* walk trie in reverse order */
1798 for (;;) {
1799 unsigned char slen = 0;
1800 struct key_vector *n;
Robert Olsson19baf832005-06-21 12:43:18 -07001801
Alexander Duyck88bae712015-03-06 09:54:52 -08001802 if (!(cindex--)) {
1803 t_key pkey = pn->key;
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001804
Alexander Duyck88bae712015-03-06 09:54:52 -08001805 /* cannot resize the trie vector */
1806 if (IS_TRIE(pn))
1807 break;
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001808
Alexander Duyck88bae712015-03-06 09:54:52 -08001809 /* resize completed node */
1810 pn = resize(t, pn);
1811 cindex = get_index(pkey, pn);
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001812
Alexander Duyck88bae712015-03-06 09:54:52 -08001813 continue;
1814 }
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001815
Alexander Duyck88bae712015-03-06 09:54:52 -08001816 /* grab the next available node */
1817 n = get_child(pn, cindex);
1818 if (!n)
1819 continue;
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001820
Alexander Duyck88bae712015-03-06 09:54:52 -08001821 if (IS_TNODE(n)) {
1822 /* record pn and cindex for leaf walking */
1823 pn = n;
1824 cindex = 1ul << n->bits;
1825
1826 continue;
1827 }
1828
1829 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
1830 struct fib_info *fi = fa->fa_info;
1831
1832 if (!fi || !(fi->fib_flags & RTNH_F_DEAD)) {
1833 slen = fa->fa_slen;
1834 continue;
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001835 }
1836
Jiri Pirkoebb9a032015-05-10 09:47:46 -07001837 switchdev_fib_ipv4_del(n->key, KEYLENGTH - fa->fa_slen,
1838 fi, fa->fa_tos, fa->fa_type,
1839 tb->tb_id);
Alexander Duyck7289e6d2015-03-04 14:58:19 -08001840 hlist_del_rcu(&fa->fa_list);
1841 fib_release_info(fa->fa_info);
1842 alias_free_mem_rcu(fa);
1843 found++;
Alexander Duyck64c62722015-01-22 15:51:45 -08001844 }
1845
Alexander Duyck88bae712015-03-06 09:54:52 -08001846 /* update leaf slen */
1847 n->slen = slen;
1848
1849 if (hlist_empty(&n->leaf)) {
1850 put_child_root(pn, n->key, NULL);
1851 node_free(n);
1852 } else {
1853 leaf_pull_suffix(pn, n);
1854 }
Robert Olsson19baf832005-06-21 12:43:18 -07001855 }
1856
Stephen Hemminger0c7770c2005-08-23 21:59:41 -07001857 pr_debug("trie_flush found=%d\n", found);
Robert Olsson19baf832005-06-21 12:43:18 -07001858 return found;
1859}
1860
Alexander Duycka7e53532015-03-04 15:02:44 -08001861static void __trie_free_rcu(struct rcu_head *head)
Pavel Emelyanov4aa2c462010-10-28 02:00:43 +00001862{
Alexander Duycka7e53532015-03-04 15:02:44 -08001863 struct fib_table *tb = container_of(head, struct fib_table, rcu);
Alexander Duyck8274a972014-12-31 10:55:29 -08001864#ifdef CONFIG_IP_FIB_TRIE_STATS
1865 struct trie *t = (struct trie *)tb->tb_data;
1866
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001867 if (tb->tb_data == tb->__data)
1868 free_percpu(t->stats);
Alexander Duyck8274a972014-12-31 10:55:29 -08001869#endif /* CONFIG_IP_FIB_TRIE_STATS */
Pavel Emelyanov4aa2c462010-10-28 02:00:43 +00001870 kfree(tb);
1871}
1872
Alexander Duycka7e53532015-03-04 15:02:44 -08001873void fib_free_table(struct fib_table *tb)
1874{
1875 call_rcu(&tb->rcu, __trie_free_rcu);
1876}
1877
Alexander Duyck35c6eda2015-03-06 09:54:08 -08001878static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001879 struct sk_buff *skb, struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001880{
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001881 __be32 xkey = htonl(l->key);
Robert Olsson19baf832005-06-21 12:43:18 -07001882 struct fib_alias *fa;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001883 int i, s_i;
Robert Olsson19baf832005-06-21 12:43:18 -07001884
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001885 s_i = cb->args[4];
Robert Olsson19baf832005-06-21 12:43:18 -07001886 i = 0;
1887
Robert Olsson2373ce12005-08-25 13:01:29 -07001888 /* rcu_read_lock is hold by caller */
Alexander Duyck79e5ad22015-02-25 15:31:51 -08001889 hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
Robert Olsson19baf832005-06-21 12:43:18 -07001890 if (i < s_i) {
1891 i++;
1892 continue;
1893 }
Robert Olsson19baf832005-06-21 12:43:18 -07001894
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001895 if (tb->tb_id != fa->tb_id) {
1896 i++;
1897 continue;
1898 }
1899
Eric W. Biederman15e47302012-09-07 20:12:54 +00001900 if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
Robert Olsson19baf832005-06-21 12:43:18 -07001901 cb->nlh->nlmsg_seq,
1902 RTM_NEWROUTE,
1903 tb->tb_id,
1904 fa->fa_type,
Thomas Grafbe403ea2006-08-17 18:15:17 -07001905 xkey,
Alexander Duyck9b6ebad2015-02-25 15:31:44 -08001906 KEYLENGTH - fa->fa_slen,
Robert Olsson19baf832005-06-21 12:43:18 -07001907 fa->fa_tos,
Stephen Hemminger64347f72008-01-22 21:55:01 -08001908 fa->fa_info, NLM_F_MULTI) < 0) {
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001909 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001910 return -1;
1911 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001912 i++;
Robert Olsson19baf832005-06-21 12:43:18 -07001913 }
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001914
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001915 cb->args[4] = i;
Robert Olsson19baf832005-06-21 12:43:18 -07001916 return skb->len;
1917}
1918
Alexander Duycka7e53532015-03-04 15:02:44 -08001919/* rcu_read_lock needs to be hold by caller from readside */
Stephen Hemminger16c6cf82009-09-20 10:35:36 +00001920int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
1921 struct netlink_callback *cb)
Robert Olsson19baf832005-06-21 12:43:18 -07001922{
Alexander Duyck8be33e92015-03-04 14:59:19 -08001923 struct trie *t = (struct trie *)tb->tb_data;
Alexander Duyck88bae712015-03-06 09:54:52 -08001924 struct key_vector *l, *tp = t->kv;
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001925 /* Dump starting at last key.
1926 * Note: 0.0.0.0/0 (ie default) is first key.
1927 */
Alexander Duyck8be33e92015-03-04 14:59:19 -08001928 int count = cb->args[2];
1929 t_key key = cb->args[3];
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001930
Alexander Duyck8be33e92015-03-04 14:59:19 -08001931 while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001932 if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
Alexander Duyck8be33e92015-03-04 14:59:19 -08001933 cb->args[3] = key;
1934 cb->args[2] = count;
Stephen Hemmingera88ee222008-01-22 21:56:11 -08001935 return -1;
Robert Olsson19baf832005-06-21 12:43:18 -07001936 }
Stephen Hemmingerd5ce8a02008-01-22 21:57:22 -08001937
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001938 ++count;
Alexander Duyck8be33e92015-03-04 14:59:19 -08001939 key = l->key + 1;
1940
Stephen Hemminger71d67e62008-01-31 16:45:47 -08001941 memset(&cb->args[4], 0,
1942 sizeof(cb->args) - 4*sizeof(cb->args[0]));
Alexander Duyck8be33e92015-03-04 14:59:19 -08001943
1944 /* stop loop if key wrapped back to 0 */
1945 if (key < l->key)
1946 break;
Robert Olsson19baf832005-06-21 12:43:18 -07001947 }
Alexander Duyck8be33e92015-03-04 14:59:19 -08001948
Alexander Duyck8be33e92015-03-04 14:59:19 -08001949 cb->args[3] = key;
1950 cb->args[2] = count;
1951
Robert Olsson19baf832005-06-21 12:43:18 -07001952 return skb->len;
Robert Olsson19baf832005-06-21 12:43:18 -07001953}
1954
David S. Miller5348ba82011-02-01 15:30:56 -08001955void __init fib_trie_init(void)
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001956{
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08001957 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
1958 sizeof(struct fib_alias),
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08001959 0, SLAB_PANIC, NULL);
1960
1961 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
Alexander Duyck41b489f2015-03-04 15:02:33 -08001962 LEAF_SIZE,
Stephen Hemmingerbc3c8c12008-01-22 21:51:50 -08001963 0, SLAB_PANIC, NULL);
Stephen Hemminger7f9b8052008-01-14 23:14:20 -08001964}
Robert Olsson19baf832005-06-21 12:43:18 -07001965
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001966struct fib_table *fib_trie_table(u32 id, struct fib_table *alias)
Robert Olsson19baf832005-06-21 12:43:18 -07001967{
1968 struct fib_table *tb;
1969 struct trie *t;
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001970 size_t sz = sizeof(*tb);
Robert Olsson19baf832005-06-21 12:43:18 -07001971
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001972 if (!alias)
1973 sz += sizeof(struct trie);
1974
1975 tb = kzalloc(sz, GFP_KERNEL);
Ian Morris51456b22015-04-03 09:17:26 +01001976 if (!tb)
Robert Olsson19baf832005-06-21 12:43:18 -07001977 return NULL;
1978
1979 tb->tb_id = id;
Denis V. Lunev971b8932007-12-08 00:32:23 -08001980 tb->tb_default = -1;
David S. Miller21d8c492011-04-14 14:49:37 -07001981 tb->tb_num_default = 0;
Alexander Duyck0ddcf432015-03-06 13:47:00 -08001982 tb->tb_data = (alias ? alias->__data : tb->__data);
1983
1984 if (alias)
1985 return tb;
Robert Olsson19baf832005-06-21 12:43:18 -07001986
1987 t = (struct trie *) tb->tb_data;
Alexander Duyck88bae712015-03-06 09:54:52 -08001988 t->kv[0].pos = KEYLENGTH;
1989 t->kv[0].slen = KEYLENGTH;
Alexander Duyck8274a972014-12-31 10:55:29 -08001990#ifdef CONFIG_IP_FIB_TRIE_STATS
1991 t->stats = alloc_percpu(struct trie_use_stats);
1992 if (!t->stats) {
1993 kfree(tb);
1994 tb = NULL;
1995 }
1996#endif
Robert Olsson19baf832005-06-21 12:43:18 -07001997
Robert Olsson19baf832005-06-21 12:43:18 -07001998 return tb;
1999}
2000
Robert Olsson19baf832005-06-21 12:43:18 -07002001#ifdef CONFIG_PROC_FS
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002002/* Depth first Trie walk iterator */
2003struct fib_trie_iter {
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002004 struct seq_net_private p;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002005 struct fib_table *tb;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002006 struct key_vector *tnode;
Eric Dumazeta034ee32010-09-09 23:32:28 +00002007 unsigned int index;
2008 unsigned int depth;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002009};
Robert Olsson19baf832005-06-21 12:43:18 -07002010
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002011static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter)
Robert Olsson19baf832005-06-21 12:43:18 -07002012{
Alexander Duyck98293e82014-12-31 10:56:18 -08002013 unsigned long cindex = iter->index;
Alexander Duyck88bae712015-03-06 09:54:52 -08002014 struct key_vector *pn = iter->tnode;
2015 t_key pkey;
Eric W. Biederman6640e692007-01-24 14:42:04 -08002016
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002017 pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
2018 iter->tnode, iter->index, iter->depth);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002019
Alexander Duyck88bae712015-03-06 09:54:52 -08002020 while (!IS_TRIE(pn)) {
2021 while (cindex < child_length(pn)) {
2022 struct key_vector *n = get_child_rcu(pn, cindex++);
2023
2024 if (!n)
2025 continue;
2026
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002027 if (IS_LEAF(n)) {
Alexander Duyck88bae712015-03-06 09:54:52 -08002028 iter->tnode = pn;
2029 iter->index = cindex;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002030 } else {
2031 /* push down one level */
Alexander Duyckadaf9812014-12-31 10:55:47 -08002032 iter->tnode = n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002033 iter->index = 0;
2034 ++iter->depth;
2035 }
Alexander Duyck88bae712015-03-06 09:54:52 -08002036
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002037 return n;
2038 }
2039
Alexander Duyck88bae712015-03-06 09:54:52 -08002040 /* Current node exhausted, pop back up */
2041 pkey = pn->key;
2042 pn = node_parent_rcu(pn);
2043 cindex = get_index(pkey, pn) + 1;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002044 --iter->depth;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002045 }
2046
Alexander Duyck88bae712015-03-06 09:54:52 -08002047 /* record root node so further searches know we are done */
2048 iter->tnode = pn;
2049 iter->index = 0;
2050
Robert Olsson19baf832005-06-21 12:43:18 -07002051 return NULL;
2052}
2053
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002054static struct key_vector *fib_trie_get_first(struct fib_trie_iter *iter,
2055 struct trie *t)
Robert Olsson19baf832005-06-21 12:43:18 -07002056{
Alexander Duyck88bae712015-03-06 09:54:52 -08002057 struct key_vector *n, *pn = t->kv;
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002058
Stephen Hemminger132adf52007-03-08 20:44:43 -08002059 if (!t)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002060 return NULL;
2061
Alexander Duyck88bae712015-03-06 09:54:52 -08002062 n = rcu_dereference(pn->tnode[0]);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002063 if (!n)
Robert Olsson5ddf0eb2006-03-20 21:34:12 -08002064 return NULL;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002065
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002066 if (IS_TNODE(n)) {
Alexander Duyckadaf9812014-12-31 10:55:47 -08002067 iter->tnode = n;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002068 iter->index = 0;
2069 iter->depth = 1;
2070 } else {
Alexander Duyck88bae712015-03-06 09:54:52 -08002071 iter->tnode = pn;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002072 iter->index = 0;
2073 iter->depth = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002074 }
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002075
2076 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002077}
2078
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002079static void trie_collect_stats(struct trie *t, struct trie_stat *s)
Robert Olsson19baf832005-06-21 12:43:18 -07002080{
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002081 struct key_vector *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002082 struct fib_trie_iter iter;
Robert Olsson19baf832005-06-21 12:43:18 -07002083
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002084 memset(s, 0, sizeof(*s));
Robert Olsson19baf832005-06-21 12:43:18 -07002085
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002086 rcu_read_lock();
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002087 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002088 if (IS_LEAF(n)) {
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002089 struct fib_alias *fa;
Stephen Hemminger93672292008-01-22 21:54:05 -08002090
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002091 s->leaves++;
2092 s->totdepth += iter.depth;
2093 if (iter.depth > s->maxdepth)
2094 s->maxdepth = iter.depth;
Stephen Hemminger93672292008-01-22 21:54:05 -08002095
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002096 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list)
Stephen Hemminger93672292008-01-22 21:54:05 -08002097 ++s->prefixes;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002098 } else {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002099 s->tnodes++;
Alexander Duyckadaf9812014-12-31 10:55:47 -08002100 if (n->bits < MAX_STAT_DEPTH)
2101 s->nodesizes[n->bits]++;
Alexander Duyck6e22d172015-03-06 09:54:39 -08002102 s->nullpointers += tn_info(n)->empty_children;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002103 }
2104 }
2105 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002106}
2107
Stephen Hemmingerc877efb2005-07-19 14:01:51 -07002108/*
Robert Olsson19baf832005-06-21 12:43:18 -07002109 * This outputs /proc/net/fib_triestats
Robert Olsson19baf832005-06-21 12:43:18 -07002110 */
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002111static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
Robert Olsson19baf832005-06-21 12:43:18 -07002112{
Eric Dumazeta034ee32010-09-09 23:32:28 +00002113 unsigned int i, max, pointers, bytes, avdepth;
Robert Olsson19baf832005-06-21 12:43:18 -07002114
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002115 if (stat->leaves)
2116 avdepth = stat->totdepth*100 / stat->leaves;
2117 else
2118 avdepth = 0;
Robert Olsson19baf832005-06-21 12:43:18 -07002119
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002120 seq_printf(seq, "\tAver depth: %u.%02d\n",
2121 avdepth / 100, avdepth % 100);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002122 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
Robert Olsson19baf832005-06-21 12:43:18 -07002123
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002124 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
Alexander Duyck41b489f2015-03-04 15:02:33 -08002125 bytes = LEAF_SIZE * stat->leaves;
Stephen Hemminger93672292008-01-22 21:54:05 -08002126
2127 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002128 bytes += sizeof(struct fib_alias) * stat->prefixes;
Stephen Hemminger93672292008-01-22 21:54:05 -08002129
Stephen Hemminger187b5182008-01-12 20:55:55 -08002130 seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
Alexander Duyck41b489f2015-03-04 15:02:33 -08002131 bytes += TNODE_SIZE(0) * stat->tnodes;
Robert Olsson19baf832005-06-21 12:43:18 -07002132
Robert Olsson06ef9212006-03-20 21:35:01 -08002133 max = MAX_STAT_DEPTH;
2134 while (max > 0 && stat->nodesizes[max-1] == 0)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002135 max--;
Robert Olsson19baf832005-06-21 12:43:18 -07002136
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002137 pointers = 0;
Jerry Snitselaarf585a992013-07-22 12:01:58 -07002138 for (i = 1; i < max; i++)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002139 if (stat->nodesizes[i] != 0) {
Stephen Hemminger187b5182008-01-12 20:55:55 -08002140 seq_printf(seq, " %u: %u", i, stat->nodesizes[i]);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002141 pointers += (1<<i) * stat->nodesizes[i];
2142 }
2143 seq_putc(seq, '\n');
Stephen Hemminger187b5182008-01-12 20:55:55 -08002144 seq_printf(seq, "\tPointers: %u\n", pointers);
Robert Olsson19baf832005-06-21 12:43:18 -07002145
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002146 bytes += sizeof(struct key_vector *) * pointers;
Stephen Hemminger187b5182008-01-12 20:55:55 -08002147 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
2148 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002149}
Robert Olsson19baf832005-06-21 12:43:18 -07002150
2151#ifdef CONFIG_IP_FIB_TRIE_STATS
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002152static void trie_show_usage(struct seq_file *seq,
Alexander Duyck8274a972014-12-31 10:55:29 -08002153 const struct trie_use_stats __percpu *stats)
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002154{
Alexander Duyck8274a972014-12-31 10:55:29 -08002155 struct trie_use_stats s = { 0 };
2156 int cpu;
2157
2158 /* loop through all of the CPUs and gather up the stats */
2159 for_each_possible_cpu(cpu) {
2160 const struct trie_use_stats *pcpu = per_cpu_ptr(stats, cpu);
2161
2162 s.gets += pcpu->gets;
2163 s.backtrack += pcpu->backtrack;
2164 s.semantic_match_passed += pcpu->semantic_match_passed;
2165 s.semantic_match_miss += pcpu->semantic_match_miss;
2166 s.null_node_hit += pcpu->null_node_hit;
2167 s.resize_node_skipped += pcpu->resize_node_skipped;
2168 }
2169
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002170 seq_printf(seq, "\nCounters:\n---------\n");
Alexander Duyck8274a972014-12-31 10:55:29 -08002171 seq_printf(seq, "gets = %u\n", s.gets);
2172 seq_printf(seq, "backtracks = %u\n", s.backtrack);
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002173 seq_printf(seq, "semantic match passed = %u\n",
Alexander Duyck8274a972014-12-31 10:55:29 -08002174 s.semantic_match_passed);
2175 seq_printf(seq, "semantic match miss = %u\n", s.semantic_match_miss);
2176 seq_printf(seq, "null node hit= %u\n", s.null_node_hit);
2177 seq_printf(seq, "skipped node resize = %u\n\n", s.resize_node_skipped);
Robert Olsson19baf832005-06-21 12:43:18 -07002178}
Stephen Hemminger66a2f7f2008-01-12 21:23:17 -08002179#endif /* CONFIG_IP_FIB_TRIE_STATS */
2180
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002181static void fib_table_print(struct seq_file *seq, struct fib_table *tb)
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002182{
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002183 if (tb->tb_id == RT_TABLE_LOCAL)
2184 seq_puts(seq, "Local:\n");
2185 else if (tb->tb_id == RT_TABLE_MAIN)
2186 seq_puts(seq, "Main:\n");
2187 else
2188 seq_printf(seq, "Id %d:\n", tb->tb_id);
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002189}
Robert Olsson19baf832005-06-21 12:43:18 -07002190
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002191
Robert Olsson19baf832005-06-21 12:43:18 -07002192static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2193{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002194 struct net *net = (struct net *)seq->private;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002195 unsigned int h;
Eric W. Biederman877a9bf2007-12-07 00:47:47 -08002196
Stephen Hemmingerd717a9a2008-01-14 23:11:54 -08002197 seq_printf(seq,
Stephen Hemmingera07f5f52008-01-22 21:53:36 -08002198 "Basic info: size of leaf:"
2199 " %Zd bytes, size of tnode: %Zd bytes.\n",
Alexander Duyck41b489f2015-03-04 15:02:33 -08002200 LEAF_SIZE, TNODE_SIZE(0));
Olof Johansson91b9a272005-08-09 20:24:39 -07002201
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002202 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
2203 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002204 struct fib_table *tb;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002205
Sasha Levinb67bfe02013-02-27 17:06:00 -08002206 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002207 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
Alexander Duyck8274a972014-12-31 10:55:29 -08002218 trie_show_usage(seq, t->stats);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002219#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
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002239static struct key_vector *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];
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002248 struct fib_table *tb;
2249
Sasha Levinb67bfe02013-02-27 17:06:00 -08002250 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002251 struct key_vector *n;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002252
2253 for (n = fib_trie_get_first(iter,
2254 (struct trie *) tb->tb_data);
2255 n; n = fib_trie_get_next(iter))
2256 if (pos == idx++) {
2257 iter->tb = tb;
2258 return n;
2259 }
2260 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002261 }
Robert Olsson19baf832005-06-21 12:43:18 -07002262
Robert Olsson19baf832005-06-21 12:43:18 -07002263 return NULL;
2264}
2265
2266static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002267 __acquires(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002268{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002269 rcu_read_lock();
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002270 return fib_trie_get_idx(seq, *pos);
Robert Olsson19baf832005-06-21 12:43:18 -07002271}
2272
2273static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2274{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002275 struct fib_trie_iter *iter = seq->private;
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002276 struct net *net = seq_file_net(seq);
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002277 struct fib_table *tb = iter->tb;
2278 struct hlist_node *tb_node;
2279 unsigned int h;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002280 struct key_vector *n;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002281
Robert Olsson19baf832005-06-21 12:43:18 -07002282 ++*pos;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002283 /* next node in same table */
2284 n = fib_trie_get_next(iter);
2285 if (n)
2286 return n;
Olof Johansson91b9a272005-08-09 20:24:39 -07002287
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002288 /* walk rest of this hash chain */
2289 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
Eric Dumazet0a5c0472011-03-31 01:51:35 -07002290 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002291 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2292 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2293 if (n)
2294 goto found;
2295 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002296
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002297 /* new hash chain */
2298 while (++h < FIB_TABLE_HASHSZ) {
2299 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
Sasha Levinb67bfe02013-02-27 17:06:00 -08002300 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002301 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2302 if (n)
2303 goto found;
2304 }
2305 }
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002306 return NULL;
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002307
2308found:
2309 iter->tb = tb;
2310 return n;
Robert Olsson19baf832005-06-21 12:43:18 -07002311}
2312
2313static void fib_trie_seq_stop(struct seq_file *seq, void *v)
Stephen Hemmingerc95aaf92008-01-12 21:25:02 -08002314 __releases(RCU)
Robert Olsson19baf832005-06-21 12:43:18 -07002315{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002316 rcu_read_unlock();
Robert Olsson19baf832005-06-21 12:43:18 -07002317}
2318
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002319static void seq_indent(struct seq_file *seq, int n)
2320{
Eric Dumazeta034ee32010-09-09 23:32:28 +00002321 while (n-- > 0)
2322 seq_puts(seq, " ");
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002323}
Robert Olsson19baf832005-06-21 12:43:18 -07002324
Eric Dumazet28d36e32008-01-14 23:09:56 -08002325static inline const char *rtn_scope(char *buf, size_t len, enum rt_scope_t s)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002326{
Stephen Hemminger132adf52007-03-08 20:44:43 -08002327 switch (s) {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002328 case RT_SCOPE_UNIVERSE: return "universe";
2329 case RT_SCOPE_SITE: return "site";
2330 case RT_SCOPE_LINK: return "link";
2331 case RT_SCOPE_HOST: return "host";
2332 case RT_SCOPE_NOWHERE: return "nowhere";
2333 default:
Eric Dumazet28d36e32008-01-14 23:09:56 -08002334 snprintf(buf, len, "scope=%d", s);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002335 return buf;
2336 }
2337}
2338
Jan Engelhardt36cbd3d2009-08-05 10:42:58 -07002339static const char *const rtn_type_names[__RTN_MAX] = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002340 [RTN_UNSPEC] = "UNSPEC",
2341 [RTN_UNICAST] = "UNICAST",
2342 [RTN_LOCAL] = "LOCAL",
2343 [RTN_BROADCAST] = "BROADCAST",
2344 [RTN_ANYCAST] = "ANYCAST",
2345 [RTN_MULTICAST] = "MULTICAST",
2346 [RTN_BLACKHOLE] = "BLACKHOLE",
2347 [RTN_UNREACHABLE] = "UNREACHABLE",
2348 [RTN_PROHIBIT] = "PROHIBIT",
2349 [RTN_THROW] = "THROW",
2350 [RTN_NAT] = "NAT",
2351 [RTN_XRESOLVE] = "XRESOLVE",
2352};
2353
Eric Dumazeta034ee32010-09-09 23:32:28 +00002354static inline const char *rtn_type(char *buf, size_t len, unsigned int t)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002355{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002356 if (t < __RTN_MAX && rtn_type_names[t])
2357 return rtn_type_names[t];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002358 snprintf(buf, len, "type %u", t);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002359 return buf;
2360}
2361
2362/* Pretty print the trie */
Robert Olsson19baf832005-06-21 12:43:18 -07002363static int fib_trie_seq_show(struct seq_file *seq, void *v)
2364{
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002365 const struct fib_trie_iter *iter = seq->private;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002366 struct key_vector *n = v;
Robert Olsson19baf832005-06-21 12:43:18 -07002367
Alexander Duyck88bae712015-03-06 09:54:52 -08002368 if (IS_TRIE(node_parent_rcu(n)))
Stephen Hemminger3d3b2d22008-03-23 22:43:56 -07002369 fib_table_print(seq, iter->tb);
Robert Olsson095b8502007-01-26 19:06:01 -08002370
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002371 if (IS_TNODE(n)) {
Alexander Duyckadaf9812014-12-31 10:55:47 -08002372 __be32 prf = htonl(n->key);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002373
Alexander Duycke9b44012014-12-31 10:56:12 -08002374 seq_indent(seq, iter->depth-1);
2375 seq_printf(seq, " +-- %pI4/%zu %u %u %u\n",
2376 &prf, KEYLENGTH - n->pos - n->bits, n->bits,
Alexander Duyck6e22d172015-03-06 09:54:39 -08002377 tn_info(n)->full_children,
2378 tn_info(n)->empty_children);
Olof Johansson91b9a272005-08-09 20:24:39 -07002379 } else {
Alexander Duyckadaf9812014-12-31 10:55:47 -08002380 __be32 val = htonl(n->key);
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002381 struct fib_alias *fa;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002382
2383 seq_indent(seq, iter->depth);
Harvey Harrison673d57e2008-10-31 00:53:57 -07002384 seq_printf(seq, " |-- %pI4\n", &val);
Eric Dumazet28d36e32008-01-14 23:09:56 -08002385
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002386 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
2387 char buf1[32], buf2[32];
Eric Dumazet28d36e32008-01-14 23:09:56 -08002388
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002389 seq_indent(seq, iter->depth + 1);
2390 seq_printf(seq, " /%zu %s %s",
2391 KEYLENGTH - fa->fa_slen,
2392 rtn_scope(buf1, sizeof(buf1),
2393 fa->fa_info->fib_scope),
2394 rtn_type(buf2, sizeof(buf2),
2395 fa->fa_type));
2396 if (fa->fa_tos)
2397 seq_printf(seq, " tos=%d", fa->fa_tos);
2398 seq_putc(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002399 }
Robert Olsson19baf832005-06-21 12:43:18 -07002400 }
2401
2402 return 0;
2403}
2404
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002405static const struct seq_operations fib_trie_seq_ops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002406 .start = fib_trie_seq_start,
2407 .next = fib_trie_seq_next,
2408 .stop = fib_trie_seq_stop,
2409 .show = fib_trie_seq_show,
Robert Olsson19baf832005-06-21 12:43:18 -07002410};
2411
2412static int fib_trie_seq_open(struct inode *inode, struct file *file)
2413{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002414 return seq_open_net(inode, file, &fib_trie_seq_ops,
2415 sizeof(struct fib_trie_iter));
Robert Olsson19baf832005-06-21 12:43:18 -07002416}
2417
Arjan van de Ven9a321442007-02-12 00:55:35 -08002418static const struct file_operations fib_trie_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002419 .owner = THIS_MODULE,
2420 .open = fib_trie_seq_open,
2421 .read = seq_read,
2422 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002423 .release = seq_release_net,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002424};
2425
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002426struct fib_route_iter {
2427 struct seq_net_private p;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002428 struct fib_table *main_tb;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002429 struct key_vector *tnode;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002430 loff_t pos;
2431 t_key key;
2432};
2433
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002434static struct key_vector *fib_route_get_idx(struct fib_route_iter *iter,
2435 loff_t pos)
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002436{
Alexander Duyck8be33e92015-03-04 14:59:19 -08002437 struct fib_table *tb = iter->main_tb;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002438 struct key_vector *l, **tp = &iter->tnode;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002439 struct trie *t;
2440 t_key key;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002441
Alexander Duyck8be33e92015-03-04 14:59:19 -08002442 /* use cache location of next-to-find key */
2443 if (iter->pos > 0 && pos >= iter->pos) {
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002444 pos -= iter->pos;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002445 key = iter->key;
2446 } else {
2447 t = (struct trie *)tb->tb_data;
Alexander Duyck88bae712015-03-06 09:54:52 -08002448 iter->tnode = t->kv;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002449 iter->pos = 0;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002450 key = 0;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002451 }
2452
Alexander Duyck8be33e92015-03-04 14:59:19 -08002453 while ((l = leaf_walk_rcu(tp, key)) != NULL) {
2454 key = l->key + 1;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002455 iter->pos++;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002456
2457 if (pos-- <= 0)
2458 break;
2459
2460 l = NULL;
2461
2462 /* handle unlikely case of a key wrap */
2463 if (!key)
2464 break;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002465 }
2466
2467 if (l)
Alexander Duyck8be33e92015-03-04 14:59:19 -08002468 iter->key = key; /* remember it */
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002469 else
2470 iter->pos = 0; /* forget it */
2471
2472 return l;
2473}
2474
2475static void *fib_route_seq_start(struct seq_file *seq, loff_t *pos)
2476 __acquires(RCU)
2477{
2478 struct fib_route_iter *iter = seq->private;
2479 struct fib_table *tb;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002480 struct trie *t;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002481
2482 rcu_read_lock();
Alexander Duyck8be33e92015-03-04 14:59:19 -08002483
YOSHIFUJI Hideaki12188542008-03-26 02:36:06 +09002484 tb = fib_get_table(seq_file_net(seq), RT_TABLE_MAIN);
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002485 if (!tb)
2486 return NULL;
2487
Alexander Duyck8be33e92015-03-04 14:59:19 -08002488 iter->main_tb = tb;
2489
2490 if (*pos != 0)
2491 return fib_route_get_idx(iter, *pos);
2492
2493 t = (struct trie *)tb->tb_data;
Alexander Duyck88bae712015-03-06 09:54:52 -08002494 iter->tnode = t->kv;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002495 iter->pos = 0;
2496 iter->key = 0;
2497
2498 return SEQ_START_TOKEN;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002499}
2500
2501static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2502{
2503 struct fib_route_iter *iter = seq->private;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002504 struct key_vector *l = NULL;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002505 t_key key = iter->key;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002506
2507 ++*pos;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002508
2509 /* only allow key of 0 for start of sequence */
2510 if ((v == SEQ_START_TOKEN) || key)
2511 l = leaf_walk_rcu(&iter->tnode, key);
2512
2513 if (l) {
2514 iter->key = l->key + 1;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002515 iter->pos++;
Alexander Duyck8be33e92015-03-04 14:59:19 -08002516 } else {
2517 iter->pos = 0;
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002518 }
2519
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002520 return l;
2521}
2522
2523static void fib_route_seq_stop(struct seq_file *seq, void *v)
2524 __releases(RCU)
2525{
2526 rcu_read_unlock();
2527}
2528
Eric Dumazeta034ee32010-09-09 23:32:28 +00002529static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info *fi)
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002530{
Eric Dumazeta034ee32010-09-09 23:32:28 +00002531 unsigned int flags = 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002532
Eric Dumazeta034ee32010-09-09 23:32:28 +00002533 if (type == RTN_UNREACHABLE || type == RTN_PROHIBIT)
2534 flags = RTF_REJECT;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002535 if (fi && fi->fib_nh->nh_gw)
2536 flags |= RTF_GATEWAY;
Al Viro32ab5f82006-09-26 22:21:45 -07002537 if (mask == htonl(0xFFFFFFFF))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002538 flags |= RTF_HOST;
2539 flags |= RTF_UP;
2540 return flags;
2541}
2542
2543/*
2544 * This outputs /proc/net/route.
2545 * The format of the file is not supposed to be changed
Eric Dumazeta034ee32010-09-09 23:32:28 +00002546 * and needs to be same as fib_hash output to avoid breaking
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002547 * legacy utilities
2548 */
2549static int fib_route_seq_show(struct seq_file *seq, void *v)
2550{
Alexander Duyck654eff42015-03-11 16:36:08 -07002551 struct fib_route_iter *iter = seq->private;
2552 struct fib_table *tb = iter->main_tb;
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002553 struct fib_alias *fa;
Alexander Duyck35c6eda2015-03-06 09:54:08 -08002554 struct key_vector *l = v;
Alexander Duyck9b6ebad2015-02-25 15:31:44 -08002555 __be32 prefix;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002556
2557 if (v == SEQ_START_TOKEN) {
2558 seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
2559 "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
2560 "\tWindow\tIRTT");
2561 return 0;
2562 }
2563
Alexander Duyck9b6ebad2015-02-25 15:31:44 -08002564 prefix = htonl(l->key);
2565
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002566 hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
2567 const struct fib_info *fi = fa->fa_info;
2568 __be32 mask = inet_make_mask(KEYLENGTH - fa->fa_slen);
2569 unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002570
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002571 if ((fa->fa_type == RTN_BROADCAST) ||
2572 (fa->fa_type == RTN_MULTICAST))
2573 continue;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002574
Alexander Duyck654eff42015-03-11 16:36:08 -07002575 if (fa->tb_id != tb->tb_id)
2576 continue;
2577
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002578 seq_setwidth(seq, 127);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002579
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002580 if (fi)
2581 seq_printf(seq,
2582 "%s\t%08X\t%08X\t%04X\t%d\t%u\t"
2583 "%d\t%08X\t%d\t%u\t%u",
2584 fi->fib_dev ? fi->fib_dev->name : "*",
2585 prefix,
2586 fi->fib_nh->nh_gw, flags, 0, 0,
2587 fi->fib_priority,
2588 mask,
2589 (fi->fib_advmss ?
2590 fi->fib_advmss + 40 : 0),
2591 fi->fib_window,
2592 fi->fib_rtt >> 3);
2593 else
2594 seq_printf(seq,
2595 "*\t%08X\t%08X\t%04X\t%d\t%u\t"
2596 "%d\t%08X\t%d\t%u\t%u",
2597 prefix, 0, flags, 0, 0, 0,
2598 mask, 0, 0, 0);
Tetsuo Handa652586d2013-11-14 14:31:57 -08002599
Alexander Duyck79e5ad22015-02-25 15:31:51 -08002600 seq_pad(seq, '\n');
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002601 }
2602
2603 return 0;
2604}
2605
Stephen Hemmingerf6908082007-03-12 14:34:29 -07002606static const struct seq_operations fib_route_seq_ops = {
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002607 .start = fib_route_seq_start,
2608 .next = fib_route_seq_next,
2609 .stop = fib_route_seq_stop,
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002610 .show = fib_route_seq_show,
2611};
2612
2613static int fib_route_seq_open(struct inode *inode, struct file *file)
2614{
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002615 return seq_open_net(inode, file, &fib_route_seq_ops,
Stephen Hemminger8315f5d2008-02-11 21:14:39 -08002616 sizeof(struct fib_route_iter));
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002617}
2618
Arjan van de Ven9a321442007-02-12 00:55:35 -08002619static const struct file_operations fib_route_fops = {
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002620 .owner = THIS_MODULE,
2621 .open = fib_route_seq_open,
2622 .read = seq_read,
2623 .llseek = seq_lseek,
Denis V. Lunev1c340b22008-01-10 03:27:17 -08002624 .release = seq_release_net,
Robert Olsson19baf832005-06-21 12:43:18 -07002625};
2626
Denis V. Lunev61a02652008-01-10 03:21:09 -08002627int __net_init fib_proc_init(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002628{
Gao fengd4beaa62013-02-18 01:34:54 +00002629 if (!proc_create("fib_trie", S_IRUGO, net->proc_net, &fib_trie_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002630 goto out1;
2631
Gao fengd4beaa62013-02-18 01:34:54 +00002632 if (!proc_create("fib_triestat", S_IRUGO, net->proc_net,
2633 &fib_triestat_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002634 goto out2;
2635
Gao fengd4beaa62013-02-18 01:34:54 +00002636 if (!proc_create("route", S_IRUGO, net->proc_net, &fib_route_fops))
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002637 goto out3;
2638
Robert Olsson19baf832005-06-21 12:43:18 -07002639 return 0;
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002640
2641out3:
Gao fengece31ff2013-02-18 01:34:56 +00002642 remove_proc_entry("fib_triestat", net->proc_net);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002643out2:
Gao fengece31ff2013-02-18 01:34:56 +00002644 remove_proc_entry("fib_trie", net->proc_net);
Stephen Hemmingercb7b5932005-09-09 13:35:42 -07002645out1:
2646 return -ENOMEM;
Robert Olsson19baf832005-06-21 12:43:18 -07002647}
2648
Denis V. Lunev61a02652008-01-10 03:21:09 -08002649void __net_exit fib_proc_exit(struct net *net)
Robert Olsson19baf832005-06-21 12:43:18 -07002650{
Gao fengece31ff2013-02-18 01:34:56 +00002651 remove_proc_entry("fib_trie", net->proc_net);
2652 remove_proc_entry("fib_triestat", net->proc_net);
2653 remove_proc_entry("route", net->proc_net);
Robert Olsson19baf832005-06-21 12:43:18 -07002654}
2655
2656#endif /* CONFIG_PROC_FS */