drivers/net/wireless/zd1201.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

/*
 *	Copyright (c) 2004, 2005 Jeroen Vreeken (pe1rxq@amsat.org)
 *
 *	This program is free software; you can redistribute it and/or
 *	modify it under the terms of the GNU General Public License
 *	version 2 as published by the Free Software Foundation.
 *
 *	Parts of this driver have been derived from a wlan-ng version
 *	modified by ZyDAS.
 *	Copyright (C) 1999 AbsoluteValue Systems, Inc.  All Rights Reserved.
 */

#ifndef _INCLUDE_ZD1201_H_
#define _INCLUDE_ZD1201_H_

#define ZD1201_NUMKEYS		4
#define ZD1201_MAXKEYLEN	13
#define ZD1201_MAXMULTI		16
#define ZD1201_FRAGMAX		2500
#define ZD1201_FRAGMIN		256
#define ZD1201_RTSMAX		2500

#define ZD1201_RXSIZE		3000

struct zd1201 {
	struct usb_device	*usb;
	int			removed;
	struct net_device	*dev;
	struct iw_statistics	iwstats;

	int			endp_in;
	int			endp_out;
	int			endp_out2;
	struct urb		*rx_urb;
	struct urb		*tx_urb;

	unsigned char 		rxdata[ZD1201_RXSIZE];
	int			rxlen;
	wait_queue_head_t	rxdataq;
	int			rxdatas;
	struct hlist_head	fraglist;
	unsigned char		txdata[ZD1201_RXSIZE];

	int			ap;
	char			essid[IW_ESSID_MAX_SIZE+1];
	int			essidlen;
	int			mac_enabled;
	int			was_enabled;
	int			monitor;
	int			encode_enabled;
	int			encode_restricted;
	unsigned char		encode_keys[ZD1201_NUMKEYS][ZD1201_MAXKEYLEN];
	int			encode_keylen[ZD1201_NUMKEYS];
};

struct zd1201_frag {
	struct hlist_node	fnode;
	int			seq;
	struct sk_buff		*skb;
};

#define ZD1201SIWHOSTAUTH SIOCIWFIRSTPRIV
#define ZD1201GIWHOSTAUTH ZD1201SIWHOSTAUTH+1
#define ZD1201SIWAUTHSTA SIOCIWFIRSTPRIV+2
#define ZD1201SIWMAXASSOC SIOCIWFIRSTPRIV+4
#define ZD1201GIWMAXASSOC ZD1201SIWMAXASSOC+1

#define ZD1201_FW_TIMEOUT	(1000)

#define ZD1201_TX_TIMEOUT	(2000)

#define ZD1201_USB_CMDREQ	0
#define ZD1201_USB_RESREQ	1

#define	ZD1201_CMDCODE_INIT	0x00
#define ZD1201_CMDCODE_ENABLE	0x01
#define ZD1201_CMDCODE_DISABLE	0x02
#define ZD1201_CMDCODE_ALLOC	0x0a
#define ZD1201_CMDCODE_INQUIRE	0x11
#define ZD1201_CMDCODE_SETRXRID	0x17
#define ZD1201_CMDCODE_ACCESS	0x21

#define ZD1201_PACKET_EVENTSTAT	0x0
#define ZD1201_PACKET_RXDATA	0x1
#define ZD1201_PACKET_INQUIRE	0x2
#define ZD1201_PACKET_RESOURCE	0x3

#define ZD1201_ACCESSBIT	0x0100

#define ZD1201_RID_CNFPORTTYPE		0xfc00
#define ZD1201_RID_CNFOWNMACADDR	0xfc01
#define ZD1201_RID_CNFDESIREDSSID	0xfc02
#define ZD1201_RID_CNFOWNCHANNEL	0xfc03
#define ZD1201_RID_CNFOWNSSID		0xfc04
#define ZD1201_RID_CNFMAXDATALEN	0xfc07
#define ZD1201_RID_CNFPMENABLED		0xfc09
#define ZD1201_RID_CNFPMEPS		0xfc0a
#define ZD1201_RID_CNFMAXSLEEPDURATION	0xfc0c
#define ZD1201_RID_CNFDEFAULTKEYID	0xfc23
#define ZD1201_RID_CNFDEFAULTKEY0	0xfc24
#define ZD1201_RID_CNFDEFAULTKEY1	0xfc25
#define ZD1201_RID_CNFDEFAULTKEY2	0xfc26
#define ZD1201_RID_CNFDEFAULTKEY3	0xfc27
#define ZD1201_RID_CNFWEBFLAGS		0xfc28
#define ZD1201_RID_CNFAUTHENTICATION	0xfc2a
#define ZD1201_RID_CNFMAXASSOCSTATIONS	0xfc2b
#define ZD1201_RID_CNFHOSTAUTH		0xfc2e
#define ZD1201_RID_CNFGROUPADDRESS	0xfc80
#define ZD1201_RID_CNFFRAGTHRESHOLD	0xfc82
#define ZD1201_RID_CNFRTSTHRESHOLD	0xfc83
#define ZD1201_RID_TXRATECNTL		0xfc84
#define ZD1201_RID_PROMISCUOUSMODE	0xfc85
#define ZD1201_RID_CNFBASICRATES	0xfcb3
#define ZD1201_RID_AUTHENTICATESTA	0xfce3
#define ZD1201_RID_CURRENTBSSID		0xfd42
#define ZD1201_RID_COMMSQUALITY		0xfd43
#define ZD1201_RID_CURRENTTXRATE	0xfd44
#define ZD1201_RID_CNFMAXTXBUFFERNUMBER	0xfda0
#define ZD1201_RID_CURRENTCHANNEL	0xfdc1

#define ZD1201_INQ_SCANRESULTS		0xf101

#define ZD1201_INF_LINKSTATUS		0xf200
#define ZD1201_INF_ASSOCSTATUS		0xf201
#define ZD1201_INF_AUTHREQ		0xf202

#define ZD1201_ASSOCSTATUS_STAASSOC	0x1
#define ZD1201_ASSOCSTATUS_REASSOC	0x2
#define ZD1201_ASSOCSTATUS_DISASSOC	0x3
#define ZD1201_ASSOCSTATUS_ASSOCFAIL	0x4
#define ZD1201_ASSOCSTATUS_AUTHFAIL	0x5

#define ZD1201_PORTTYPE_IBSS		0
#define ZD1201_PORTTYPE_BSS		1
#define ZD1201_PORTTYPE_WDS		2
#define ZD1201_PORTTYPE_PSEUDOIBSS	3
#define ZD1201_PORTTYPE_AP		6

#define ZD1201_RATEB1	1
#define ZD1201_RATEB2	2
#define ZD1201_RATEB5	4	/* 5.5 really, but 5 is shorter :) */
#define ZD1201_RATEB11	8

#define ZD1201_CNFAUTHENTICATION_OPENSYSTEM	0x0001
#define ZD1201_CNFAUTHENTICATION_SHAREDKEY	0x0002

#endif /* _INCLUDE_ZD1201_H_ */
/*
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version
 *   2 of the License, or (at your option) any later version.
 *
 *   Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
 *     & Swedish University of Agricultural Sciences.
 *
 *   Jens Laas <jens.laas@data.slu.se> Swedish University of
 *     Agricultural Sciences.
 *
 *   Hans Liss <hans.liss@its.uu.se>  Uppsala Universitet
 *
 * This work is based on the LPC-trie which is originally described in:
 *
 * An experimental study of compression methods for dynamic tries
 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
 * http://www.csc.kth.se/~snilsson/software/dyntrie2/
 *
 *
 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
 *
 *
 * Code from fib_hash has been reused which includes the following header:
 *
 *
 * INET		An implementation of the TCP/IP protocol suite for the LINUX
 *		operating system.  INET is implemented using the  BSD Socket
 *		interface as the means of communication with the user level.
 *
 *		IPv4 FIB: lookup engine and maintenance routines.
 *
 *
 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
 *
 * Substantial contributions to this work comes from:
 *
 *		David S. Miller, <davem@davemloft.net>
 *		Stephen Hemminger <shemminger@osdl.org>
 *		Paul E. McKenney <paulmck@us.ibm.com>
 *		Patrick McHardy <kaber@trash.net>
 */

#define VERSION "0.409"

#include <asm/uaccess.h>
#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/string.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/errno.h>
#include <linux/in.h>
#include <linux/inet.h>
#include <linux/inetdevice.h>
#include <linux/netdevice.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
#include <linux/rcupdate.h>
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/export.h>
#include <net/net_namespace.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#include <net/tcp.h>
#include <net/sock.h>
#include <net/ip_fib.h>
#include <net/switchdev.h>
#include "fib_lookup.h"

#define MAX_STAT_DEPTH 32

#define KEYLENGTH	(8*sizeof(t_key))
#define KEY_MAX		((t_key)~0)

typedef unsigned int t_key;

#define IS_TRIE(n)	((n)->pos >= KEYLENGTH)
#define IS_TNODE(n)	((n)->bits)
#define IS_LEAF(n)	(!(n)->bits)

struct key_vector {
	t_key key;
	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
	unsigned char slen;
	union {
		/* This list pointer if valid if (pos | bits) == 0 (LEAF) */
		struct hlist_head leaf;
		/* This array is valid if (pos | bits) > 0 (TNODE) */
		struct key_vector __rcu *tnode[0];
	};
};

struct tnode {
	struct rcu_head rcu;
	t_key empty_children;		/* KEYLENGTH bits needed */
	t_key full_children;		/* KEYLENGTH bits needed */
	struct key_vector __rcu *parent;
	struct key_vector kv[1];
#define tn_bits kv[0].bits
};

#define TNODE_SIZE(n)	offsetof(struct tnode, kv[0].tnode[n])
#define LEAF_SIZE	TNODE_SIZE(1)

#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats {
	unsigned int gets;
	unsigned int backtrack;
	unsigned int semantic_match_passed;
	unsigned int semantic_match_miss;
	unsigned int null_node_hit;
	unsigned int resize_node_skipped;
};
#endif

struct trie_stat {
	unsigned int totdepth;
	unsigned int maxdepth;
	unsigned int tnodes;
	unsigned int leaves;
	unsigned int nullpointers;
	unsigned int prefixes;
	unsigned int nodesizes[MAX_STAT_DEPTH];
};

struct trie {
	struct key_vector kv[1];
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats __percpu *stats;
#endif
};

static struct key_vector *resize(struct trie *t, struct key_vector *tn);
static size_t tnode_free_size;

/*
 * synchronize_rcu after call_rcu for that many pages; it should be especially
 * useful before resizing the root node with PREEMPT_NONE configs; the value was
 * obtained experimentally, aiming to avoid visible slowdown.
 */
static const int sync_pages = 128;

static struct kmem_cache *fn_alias_kmem __read_mostly;
static struct kmem_cache *trie_leaf_kmem __read_mostly;

static inline struct tnode *tn_info(struct key_vector *kv)
{
	return container_of(kv, struct tnode, kv[0]);
}

/* caller must hold RTNL */
#define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)
#define get_child(tn, i) rtnl_dereference((tn)->tnode[i])

/* caller must hold RCU read lock or RTNL */
#define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)
#define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])

/* wrapper for rcu_assign_pointer */
static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
{
	if (n)
		rcu_assign_pointer(tn_info(n)->parent, tp);
}

#define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p)

/* This provides us with the number of children in this node, in the case of a
 * leaf this will return 0 meaning none of the children are accessible.
 */
static inline unsigned long child_length(const struct key_vector *tn)
{
	return (1ul << tn->bits) & ~(1ul);
}

#define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)

static inline unsigned long get_index(t_key key, struct key_vector *kv)
{
	unsigned long index = key ^ kv->key;

	if ((BITS_PER_LONG <= KEYLENGTH) && (KEYLENGTH == kv->pos))
		return 0;

	return index >> kv->pos;
}

/* To understand this stuff, an understanding of keys and all their bits is
 * necessary. Every node in the trie has a key associated with it, but not
 * all of the bits in that key are significant.
 *
 * Consider a node 'n' and its parent 'tp'.
 *
 * If n is a leaf, every bit in its key is significant. Its presence is
 * necessitated by path compression, since during a tree traversal (when
 * searching for a leaf - unless we are doing an insertion) we will completely
 * ignore all skipped bits we encounter. Thus we need to verify, at the end of
 * a potentially successful search, that we have indeed been walking the
 * correct key path.
 *
 * Note that we can never "miss" the correct key in the tree if present by
 * following the wrong path. Path compression ensures that segments of the key
 * that are the same for all keys with a given prefix are skipped, but the
 * skipped part *is* identical for each node in the subtrie below the skipped
 * bit! trie_insert() in this implementation takes care of that.
 *
 * if n is an internal node - a 'tnode' here, the various parts of its key
 * have many different meanings.
 *
 * Example:
 * _________________________________________________________________
 * | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
 * -----------------------------------------------------------------
 *  31  30  29  28  27  26  25  24  23  22  21  20  19  18  17  16
 *
 * _________________________________________________________________
 * | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
 * -----------------------------------------------------------------
 *  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0
 *
 * tp->pos = 22
 * tp->bits = 3
 * n->pos = 13
 * n->bits = 4
 *
 * First, let's just ignore the bits that come before the parent tp, that is
 * the bits from (tp->pos + tp->bits) to 31. They are *known* but at this
 * point we do not use them for anything.
 *
 * The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
 * index into the parent's child array. That is, they will be used to find
 * 'n' among tp's children.
 *
 * The bits from (n->pos + n->bits) to (tn->pos - 1) - "S" - are skipped bits
 * for the node n.
 *
 * All the bits we have seen so far are significant to the node n. The rest
 * of the bits are really not needed or indeed known in n->key.
 *
 * The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
 * n's child array, and will of course be different for each child.
 *
 * The rest of the bits, from 0 to (n->pos + n->bits), are completely unknown
 * at this point.
 */

static const int halve_threshold = 25;
static const int inflate_threshold = 50;
static const int halve_threshold_root = 15;
static const int inflate_threshold_root = 30;

static void __alias_free_mem(struct rcu_head *head)
{
	struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
	kmem_cache_free(fn_alias_kmem, fa);
}

static inline void alias_free_mem_rcu(struct fib_alias *fa)
{
	call_rcu(&fa->rcu, __alias_free_mem);
}

#define TNODE_KMALLOC_MAX \
	ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
#define TNODE_VMALLOC_MAX \
	ilog2((SIZE_MAX - TNODE_SIZE(0)) / sizeof(struct key_vector *))

static void __node_free_rcu(struct rcu_head *head)
{
	struct tnode *n = container_of(head, struct tnode, rcu);

	if (!n->tn_bits)
		kmem_cache_free(trie_leaf_kmem, n);
	else if (n->tn_bits <= TNODE_KMALLOC_MAX)
		kfree(n);
	else
		vfree(n);
}

#define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu)

static struct tnode *tnode_alloc(int bits)
{
	size_t size;

	/* verify bits is within bounds */
	if (bits > TNODE_VMALLOC_MAX)
		return NULL;

	/* determine size and verify it is non-zero and didn't overflow */
	size = TNODE_SIZE(1ul << bits);

	if (size <= PAGE_SIZE)
		return kzalloc(size, GFP_KERNEL);
	else
		return vzalloc(size);
}

static inline void empty_child_inc(struct key_vector *n)
{
	++tn_info(n)->empty_children ? : ++tn_info(n)->full_children;
}

static inline void empty_child_dec(struct key_vector *n)
{
	tn_info(n)->empty_children-- ? : tn_info(n)->full_children--;
}

static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
{
	struct tnode *kv = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
	struct key_vector *l = kv->kv;

	if (!kv)
		return NULL;

	/* initialize key vector */
	l->key = key;
	l->pos = 0;
	l->bits = 0;
	l->slen = fa->fa_slen;

	/* link leaf to fib alias */
	INIT_HLIST_HEAD(&l->leaf);
	hlist_add_head(&fa->fa_list, &l->leaf);

	return l;
}

static struct key_vector *tnode_new(t_key key, int pos, int bits)
{
	struct tnode *tnode = tnode_alloc(bits);
	unsigned int shift = pos + bits;
	struct key_vector *tn = tnode->kv;

	/* verify bits and pos their msb bits clear and values are valid */
	BUG_ON(!bits || (shift > KEYLENGTH));

	pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
		 sizeof(struct key_vector *) << bits);

	if (!tnode)
		return NULL;

	if (bits == KEYLENGTH)
		tnode->full_children = 1;
	else
		tnode->empty_children = 1ul << bits;

	tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
	tn->pos = pos;
	tn->bits = bits;
	tn->slen = pos;

	return tn;
}

/* Check whether a tnode 'n' is "full", i.e. it is an internal node
 * and no bits are skipped. See discussion in dyntree paper p. 6
 */
static inline int tnode_full(struct key_vector *tn, struct key_vector *n)
{
	return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
}

/* Add a child at position i overwriting the old value.
 * Update the value of full_children and empty_children.
 */
static void put_child(struct key_vector *tn, unsigned long i,
		      struct key_vector *n)
{
	struct key_vector *chi = get_child(tn, i);
	int isfull, wasfull;

	BUG_ON(i >= child_length(tn));

	/* update emptyChildren, overflow into fullChildren */
	if (!n && chi)
		empty_child_inc(tn);
	if (n && !chi)
		empty_child_dec(tn);

	/* update fullChildren */
	wasfull = tnode_full(tn, chi);
	isfull = tnode_full(tn, n);

	if (wasfull && !isfull)
		tn_info(tn)->full_children--;
	else if (!wasfull && isfull)
		tn_info(tn)->full_children++;

	if (n && (tn->slen < n->slen))
		tn->slen = n->slen;

	rcu_assign_pointer(tn->tnode[i], n);
}

static void update_children(struct key_vector *tn)
{
	unsigned long i;

	/* update all of the child parent pointers */
	for (i = child_length(tn); i;) {
		struct key_vector *inode = get_child(tn, --i);

		if (!inode)
			continue;

		/* Either update the children of a tnode that
		 * already belongs to us or update the child
		 * to point to ourselves.
		 */
		if (node_parent(inode) == tn)
			update_children(inode);
		else
			node_set_parent(inode, tn);
	}
}

static inline void put_child_root(struct key_vector *tp, t_key key,
				  struct key_vector *n)
{
	if (IS_TRIE(tp))
		rcu_assign_pointer(tp->tnode[0], n);
	else
		put_child(tp, get_index(key, tp), n);
}

static inline void tnode_free_init(struct key_vector *tn)
{
	tn_info(tn)->rcu.next = NULL;
}

static inline void tnode_free_append(struct key_vector *tn,
				     struct key_vector *n)
{
	tn_info(n)->rcu.next = tn_info(tn)->rcu.next;
	tn_info(tn)->rcu.next = &tn_info(n)->rcu;
}

static void tnode_free(struct key_vector *tn)
{
	struct callback_head *head = &tn_info(tn)->rcu;

	while (head) {
		head = head->next;
		tnode_free_size += TNODE_SIZE(1ul << tn->bits);
		node_free(tn);

		tn = container_of(head, struct tnode, rcu)->kv;
	}

	if (tnode_free_size >= PAGE_SIZE * sync_pages) {
		tnode_free_size = 0;
		synchronize_rcu();
	}
}

static struct key_vector *replace(struct trie *t,
				  struct key_vector *oldtnode,
				  struct key_vector *tn)
{
	struct key_vector *tp = node_parent(oldtnode);
	unsigned long i;

	/* setup the parent pointer out of and back into this node */
	NODE_INIT_PARENT(tn, tp);
	put_child_root(tp, tn->key, tn);

	/* update all of the child parent pointers */
	update_children(tn);

	/* all pointers should be clean so we are done */
	tnode_free(oldtnode);

	/* resize children now that oldtnode is freed */
	for (i = child_length(tn); i;) {
		struct key_vector *inode = get_child(tn, --i);

		/* resize child node */
		if (tnode_full(tn, inode))
			tn = resize(t, inode);
	}

	return tp;
}

static struct key_vector *inflate(struct trie *t,
				  struct key_vector *oldtnode)
{
	struct key_vector *tn;
	unsigned long i;
	t_key m;

	pr_debug("In inflate\n");

	tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
	if (!tn)
		goto notnode;

	/* prepare oldtnode to be freed */
	tnode_free_init(oldtnode);

	/* Assemble all of the pointers in our cluster, in this case that
	 * represents all of the pointers out of our allocated nodes that
	 * point to existing tnodes and the links between our allocated
	 * nodes.
	 */
	for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {
		struct key_vector *inode = get_child(oldtnode, --i);
		struct key_vector *node0, *node1;
		unsigned long j, k;

		/* An empty child */
		if (!inode)
			continue;

		/* A leaf or an internal node with skipped bits */
		if (!tnode_full(oldtnode, inode)) {
			put_child(tn, get_index(inode->key, tn), inode);
			continue;
		}

		/* drop the node in the old tnode free list */
		tnode_free_append(oldtnode, inode);

		/* An internal node with two children */
		if (inode->bits == 1) {
			put_child(tn, 2 * i + 1, get_child(inode, 1));
			put_child(tn, 2 * i, get_child(inode, 0));
			continue;
		}

		/* We will replace this node 'inode' with two new
		 * ones, 'node0' and 'node1', each with half of the
		 * original children. The two new nodes will have
		 * a position one bit further down the key and this
		 * means that the "significant" part of their keys
		 * (see the discussion near the top of this file)
		 * will differ by one bit, which will be "0" in
		 * node0's key and "1" in node1's key. Since we are
		 * moving the key position by one step, the bit that
		 * we are moving away from - the bit at position
		 * (tn->pos) - is the one that will differ between
		 * node0 and node1. So... we synthesize that bit in the
		 * two new keys.
		 */
		node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
		if (!node1)
			goto nomem;
		node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);

		tnode_free_append(tn, node1);
		if (!node0)
			goto nomem;
		tnode_free_append(tn, node0);

		/* populate child pointers in new nodes */
		for (k = child_length(inode), j = k / 2; j;) {
			put_child(node1, --j, get_child(inode, --k));
			put_child(node0, j, get_child(inode, j));
			put_child(node1, --j, get_child(inode, --k));
			put_child(node0, j, get_child(inode, j));
		}

		/* link new nodes to parent */
		NODE_INIT_PARENT(node1, tn);
		NODE_INIT_PARENT(node0, tn);

		/* link parent to nodes */
		put_child(tn, 2 * i + 1, node1);
		put_child(tn, 2 * i, node0);
	}

	/* setup the parent pointers into and out of this node */
	return replace(t, oldtnode, tn);
nomem:
	/* all pointers should be clean so we are done */
	tnode_free(tn);
notnode:
	return NULL;
}

static struct key_vector *halve(struct trie *t,
				struct key_vector *oldtnode)
{
	struct key_vector *tn;
	unsigned long i;

	pr_debug("In halve\n");

	tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
	if (!tn)
		goto notnode;

	/* prepare oldtnode to be freed */
	tnode_free_init(oldtnode);

	/* Assemble all of the pointers in our cluster, in this case that
	 * represents all of the pointers out of our allocated nodes that
	 * point to existing tnodes and the links between our allocated
	 * nodes.
	 */
	for (i = child_length(oldtnode); i;) {
		struct key_vector *node1 = get_child(oldtnode, --i);
		struct key_vector *node0 = get_child(oldtnode, --i);
		struct key_vector *inode;

		/* At least one of the children is empty */
		if (!node1 || !node0) {
			put_child(tn, i / 2, node1 ? : node0);
			continue;
		}

		/* Two nonempty children */
		inode = tnode_new(node0->key, oldtnode->pos, 1);
		if (!inode)
			goto nomem;
		tnode_free_append(tn, inode);

		/* initialize pointers out of node */
		put_child(inode, 1, node1);
		put_child(inode, 0, node0);
		NODE_INIT_PARENT(inode, tn);

		/* link parent to node */
		put_child(tn, i / 2, inode);
	}

	/* setup the parent pointers into and out of this node */
	return replace(t, oldtnode, tn);
nomem:
	/* all pointers should be clean so we are done */
	tnode_free(tn);
notnode:
	return NULL;
}

static struct key_vector *collapse(struct trie *t,
				   struct key_vector *oldtnode)
{
	struct key_vector *n, *tp;
	unsigned long i;

	/* scan the tnode looking for that one child that might still exist */
	for (n = NULL, i = child_length(oldtnode); !n && i;)
		n = get_child(oldtnode, --i);

	/* compress one level */
	tp = node_parent(oldtnode);
	put_child_root(tp, oldtnode->key, n);
	node_set_parent(n, tp);

	/* drop dead node */
	node_free(oldtnode);

	return tp;
}

static unsigned char update_suffix(struct key_vector *tn)
{
	unsigned char slen = tn->pos;
	unsigned long stride, i;

	/* search though the list of children looking for nodes that might
	 * have a suffix greater than the one we currently have.  This is
	 * why we start with a stride of 2 since a stride of 1 would
	 * represent the nodes with suffix length equal to tn->pos
	 */
	for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {
		struct key_vector *n = get_child(tn, i);

		if (!n || (n->slen <= slen))
			continue;

		/* update stride and slen based on new value */
		stride <<= (n->slen - slen);
		slen = n->slen;
		i &= ~(stride - 1);

		/* if slen covers all but the last bit we can stop here
		 * there will be nothing longer than that since only node
		 * 0 and 1 << (bits - 1) could have that as their suffix
		 * length.
		 */
		if ((slen + 1) >= (tn->pos + tn->bits))
			break;
	}

	tn->slen = slen;

	return slen;
}

/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
 * the Helsinki University of Technology and Matti Tikkanen of Nokia
 * Telecommunications, page 6:
 * "A node is doubled if the ratio of non-empty children to all
 * children in the *doubled* node is at least 'high'."
 *
 * 'high' in this instance is the variable 'inflate_threshold'. It
 * is expressed as a percentage, so we multiply it with
 * child_length() and instead of multiplying by 2 (since the
 * child array will be doubled by inflate()) and multiplying
 * the left-hand side by 100 (to handle the percentage thing) we
 * multiply the left-hand side by 50.
 *
 * The left-hand side may look a bit weird: child_length(tn)
 * - tn->empty_children is of course the number of non-null children
 * in the current node. tn->full_children is the number of "full"
 * children, that is non-null tnodes with a skip value of 0.
 * All of those will be doubled in the resulting inflated tnode, so
 * we just count them one extra time here.
 *
 * A clearer way to write this would be:
 *
 * to_be_doubled = tn->full_children;
 * not_to_be_doubled = child_length(tn) - tn->empty_children -
 *     tn->full_children;
 *
 * new_child_length = child_length(tn) * 2;
 *
 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
 *      new_child_length;
 * if (new_fill_factor >= inflate_threshold)
 *
 * ...and so on, tho it would mess up the while () loop.
 *
 * anyway,
 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
 *      inflate_threshold
 *
 * avoid a division:
 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
 *      inflate_threshold * new_child_length
 *
 * expand not_to_be_doubled and to_be_doubled, and shorten:
 * 100 * (child_length(tn) - tn->empty_children +
 *    tn->full_children) >= inflate_threshold * new_child_length
 *
 * expand new_child_length:
 * 100 * (child_length(tn) - tn->empty_children +
 *    tn->full_children) >=
 *      inflate_threshold * child_length(tn) * 2
 *
 * shorten again:
 * 50 * (tn->full_children + child_length(tn) -
 *    tn->empty_children) >= inflate_threshold *
 *    child_length(tn)
 *
 */
static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
{
	unsigned long used = child_length(tn);
	unsigned long threshold = used;

	/* Keep root node larger */
	threshold *= IS_TRIE(tp) ? inflate_threshold_root : inflate_threshold;
	used -= tn_info(tn)->empty_children;
	used += tn_info(tn)->full_children;

	/* if bits == KEYLENGTH then pos = 0, and will fail below */

	return (used > 1) && tn->pos && ((50 * used) >= threshold);
}

static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
{
	unsigned long used = child_length(tn);
	unsigned long threshold = used;

	/* Keep root node larger */
	threshold *= IS_TRIE(tp) ? halve_threshold_root : halve_threshold;
	used -= tn_info(tn)->empty_children;

	/* if bits == KEYLENGTH then used = 100% on wrap, and will fail below */

	return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
}

static inline bool should_collapse(struct key_vector *tn)
{
	unsigned long used = child_length(tn);

	used -= tn_info(tn)->empty_children;

	/* account for bits == KEYLENGTH case */
	if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)
		used -= KEY_MAX;

	/* One child or none, time to drop us from the trie */
	return used < 2;
}

#define MAX_WORK 10
static struct key_vector *resize(struct trie *t, struct key_vector *tn)
{
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats __percpu *stats = t->stats;
#endif
	struct key_vector *tp = node_parent(tn);
	unsigned long cindex = get_index(tn->key, tp);
	int max_work = MAX_WORK;

	pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
		 tn, inflate_threshold, halve_threshold);

	/* track the tnode via the pointer from the parent instead of
	 * doing it ourselves.  This way we can let RCU fully do its
	 * thing without us interfering
	 */
	BUG_ON(tn != get_child(tp, cindex));

	/* Double as long as the resulting node has a number of
	 * nonempty nodes that are above the threshold.
	 */
	while (should_inflate(tp, tn) && max_work) {
		tp = inflate(t, tn);
		if (!tp) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
			this_cpu_inc(stats->resize_node_skipped);
#endif
			break;
		}

		max_work--;
		tn = get_child(tp, cindex);
	}

	/* update parent in case inflate failed */
	tp = node_parent(tn);

	/* Return if at least one inflate is run */
	if (max_work != MAX_WORK)
		return tp;

	/* Halve as long as the number of empty children in this
	 * node is above threshold.
	 */
	while (should_halve(tp, tn) && max_work) {
		tp = halve(t, tn);
		if (!tp) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
			this_cpu_inc(stats->resize_node_skipped);
#endif
			break;
		}

		max_work--;
		tn = get_child(tp, cindex);
	}

	/* Only one child remains */
	if (should_collapse(tn))
		return collapse(t, tn);

	/* update parent in case halve failed */
	tp = node_parent(tn);

	/* Return if at least one deflate was run */
	if (max_work != MAX_WORK)
		return tp;

	/* push the suffix length to the parent node */
	if (tn->slen > tn->pos) {
		unsigned char slen = update_suffix(tn);

		if (slen > tp->slen)
			tp->slen = slen;
	}

	return tp;
}

static void leaf_pull_suffix(struct key_vector *tp, struct key_vector *l)
{
	while ((tp->slen > tp->pos) && (tp->slen > l->slen)) {
		if (update_suffix(tp) > l->slen)
			break;
		tp = node_parent(tp);
	}
}

static void leaf_push_suffix(struct key_vector *tn, struct key_vector *l)
{
	/* if this is a new leaf then tn will be NULL and we can sort
	 * out parent suffix lengths as a part of trie_rebalance
	 */
	while (tn->slen < l->slen) {
		tn->slen = l->slen;
		tn = node_parent(tn);
	}
}

/* rcu_read_lock needs to be hold by caller from readside */
static struct key_vector *fib_find_node(struct trie *t,
					struct key_vector **tp, u32 key)
{
	struct key_vector *pn, *n = t->kv;
	unsigned long index = 0;

	do {
		pn = n;
		n = get_child_rcu(n, index);

		if (!n)
			break;

		index = get_cindex(key, n);

		/* This bit of code is a bit tricky but it combines multiple
		 * checks into a single check.  The prefix consists of the
		 * prefix plus zeros for the bits in the cindex. The index
		 * is the difference between the key and this value.  From
		 * this we can actually derive several pieces of data.
		 *   if (index >= (1ul << bits))
		 *     we have a mismatch in skip bits and failed
		 *   else
		 *     we know the value is cindex
		 *
		 * This check is safe even if bits == KEYLENGTH due to the
		 * fact that we can only allocate a node with 32 bits if a
		 * long is greater than 32 bits.
		 */
		if (index >= (1ul << n->bits)) {
			n = NULL;
			break;
		}

		/* keep searching until we find a perfect match leaf or NULL */
	} while (IS_TNODE(n));

	*tp = pn;

	return n;
}

/* Return the first fib alias matching TOS with
 * priority less than or equal to PRIO.
 */
static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen,
					u8 tos, u32 prio, u32 tb_id)
{
	struct fib_alias *fa;

	if (!fah)
		return NULL;

	hlist_for_each_entry(fa, fah, fa_list) {
		if (fa->fa_slen < slen)
			continue;
		if (fa->fa_slen != slen)
			break;
		if (fa->tb_id > tb_id)
			continue;
		if (fa->tb_id != tb_id)
			break;
		if (fa->fa_tos > tos)
			continue;
		if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos)
			return fa;
	}

	return NULL;
}

static void trie_rebalance(struct trie *t, struct key_vector *tn)
{
	while (!IS_TRIE(tn))
		tn = resize(t, tn);
}

static int fib_insert_node(struct trie *t, struct key_vector *tp,
			   struct fib_alias *new, t_key key)
{
	struct key_vector *n, *l;

	l = leaf_new(key, new);
	if (!l)
		goto noleaf;

	/* retrieve child from parent node */
	n = get_child(tp, get_index(key, tp));

	/* Case 2: n is a LEAF or a TNODE and the key doesn't match.
	 *
	 *  Add a new tnode here
	 *  first tnode need some special handling
	 *  leaves us in position for handling as case 3
	 */
	if (n) {
		struct key_vector *tn;

		tn = tnode_new(key, __fls(key ^ n->key), 1);
		if (!tn)
			goto notnode;

		/* initialize routes out of node */
		NODE_INIT_PARENT(tn, tp);
		put_child(tn, get_index(key, tn) ^ 1, n);

		/* start adding routes into the node */
		put_child_root(tp, key, tn);
		node_set_parent(n, tn);

		/* parent now has a NULL spot where the leaf can go */
		tp = tn;
	}

	/* Case 3: n is NULL, and will just insert a new leaf */
	NODE_INIT_PARENT(l, tp);
	put_child_root(tp, key, l);
	trie_rebalance(t, tp);

	return 0;
notnode:
	node_free(l);
noleaf:
	return -ENOMEM;
}

static int fib_insert_alias(struct trie *t, struct key_vector *tp,
			    struct key_vector *l, struct fib_alias *new,
			    struct fib_alias *fa, t_key key)
{
	if (!l)
		return fib_insert_node(t, tp, new, key);

	if (fa) {
		hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
	} else {
		struct fib_alias *last;

		hlist_for_each_entry(last, &l->leaf, fa_list) {
			if (new->fa_slen < last->fa_slen)
				break;
			if ((new->fa_slen == last->fa_slen) &&
			    (new->tb_id > last->tb_id))
				break;
			fa = last;
		}

		if (fa)
			hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
		else
			hlist_add_head_rcu(&new->fa_list, &l->leaf);
	}

	/* if we added to the tail node then we need to update slen */
	if (l->slen < new->fa_slen) {
		l->slen = new->fa_slen;
		leaf_push_suffix(tp, l);
	}

	return 0;
}

/* Caller must hold RTNL. */
int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
{
	struct trie *t = (struct trie *)tb->tb_data;
	struct fib_alias *fa, *new_fa;
	struct key_vector *l, *tp;
	struct fib_info *fi;
	u8 plen = cfg->fc_dst_len;
	u8 slen = KEYLENGTH - plen;
	u8 tos = cfg->fc_tos;
	u32 key;
	int err;

	if (plen > KEYLENGTH)
		return -EINVAL;

	key = ntohl(cfg->fc_dst);

	pr_debug("Insert table=%u %08x/%d\n", tb->tb_id, key, plen);

	if ((plen < KEYLENGTH) && (key << plen))
		return -EINVAL;

	fi = fib_create_info(cfg);
	if (IS_ERR(fi)) {
		err = PTR_ERR(fi);
		goto err;
	}

	l = fib_find_node(t, &tp, key);
	fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority,
				tb->tb_id) : NULL;

	/* Now fa, if non-NULL, points to the first fib alias
	 * with the same keys [prefix,tos,priority], if such key already
	 * exists or to the node before which we will insert new one.
	 *
	 * If fa is NULL, we will need to allocate a new one and
	 * insert to the tail of the section matching the suffix length
	 * of the new alias.
	 */

	if (fa && fa->fa_tos == tos &&
	    fa->fa_info->fib_priority == fi->fib_priority) {
		struct fib_alias *fa_first, *fa_match;

		err = -EEXIST;
		if (cfg->fc_nlflags & NLM_F_EXCL)
			goto out;

		/* We have 2 goals:
		 * 1. Find exact match for type, scope, fib_info to avoid
		 * duplicate routes
		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
		 */
		fa_match = NULL;
		fa_first = fa;
		hlist_for_each_entry_from(fa, fa_list) {
			if ((fa->fa_slen != slen) ||
			    (fa->tb_id != tb->tb_id) ||
			    (fa->fa_tos != tos))
				break;
			if (fa->fa_info->fib_priority != fi->fib_priority)
				break;
			if (fa->fa_type == cfg->fc_type &&
			    fa->fa_info == fi) {
				fa_match = fa;
				break;
			}
		}

		if (cfg->fc_nlflags & NLM_F_REPLACE) {
			struct fib_info *fi_drop;
			u8 state;

			fa = fa_first;
			if (fa_match) {
				if (fa == fa_match)
					err = 0;
				goto out;
			}
			err = -ENOBUFS;
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
			if (!new_fa)
				goto out;

			fi_drop = fa->fa_info;
			new_fa->fa_tos = fa->fa_tos;
			new_fa->fa_info = fi;
			new_fa->fa_type = cfg->fc_type;
			state = fa->fa_state;
			new_fa->fa_state = state & ~FA_S_ACCESSED;
			new_fa->fa_slen = fa->fa_slen;
			new_fa->tb_id = tb->tb_id;

			err = netdev_switch_fib_ipv4_add(key, plen, fi,
							 new_fa->fa_tos,
							 cfg->fc_type,
							 cfg->fc_nlflags,
							 tb->tb_id);
			if (err) {
				netdev_switch_fib_ipv4_abort(fi);
				kmem_cache_free(fn_alias_kmem, new_fa);
				goto out;
			}

			hlist_replace_rcu(&fa->fa_list, &new_fa->fa_list);

			alias_free_mem_rcu(fa);

			fib_release_info(fi_drop);
			if (state & FA_S_ACCESSED)
				rt_cache_flush(cfg->fc_nlinfo.nl_net);
			rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen,
				tb->tb_id, &cfg->fc_nlinfo, NLM_F_REPLACE);

			goto succeeded;
		}
		/* Error if we find a perfect match which
		 * uses the same scope, type, and nexthop
		 * information.
		 */
		if (fa_match)
			goto out;

		if (!(cfg->fc_nlflags & NLM_F_APPEND))
			fa = fa_first;
	}
	err = -ENOENT;
	if (!(cfg->fc_nlflags & NLM_F_CREATE))
		goto out;

	err = -ENOBUFS;
	new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
	if (!new_fa)
		goto out;

	new_fa->fa_info = fi;
	new_fa->fa_tos = tos;
	new_fa->fa_type = cfg->fc_type;
	new_fa->fa_state = 0;
	new_fa->fa_slen = slen;
	new_fa->tb_id = tb->tb_id;

	/* (Optionally) offload fib entry to switch hardware. */
	err = netdev_switch_fib_ipv4_add(key, plen, fi, tos,
					 cfg->fc_type,
					 cfg->fc_nlflags,
					 tb->tb_id);
	if (err) {
		netdev_switch_fib_ipv4_abort(fi);
		goto out_free_new_fa;
	}

	/* Insert new entry to the list. */
	err = fib_insert_alias(t, tp, l, new_fa, fa, key);
	if (err)
		goto out_sw_fib_del;

	if (!plen)
		tb->tb_num_default++;

	rt_cache_flush(cfg->fc_nlinfo.nl_net);
	rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, new_fa->tb_id,
		  &cfg->fc_nlinfo, 0);
succeeded:
	return 0;

out_sw_fib_del:
	netdev_switch_fib_ipv4_del(key, plen, fi, tos, cfg->fc_type, tb->tb_id);
out_free_new_fa:
	kmem_cache_free(fn_alias_kmem, new_fa);
out:
	fib_release_info(fi);
err:
	return err;
}

static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
{
	t_key prefix = n->key;

	return (key ^ prefix) & (prefix | -prefix);
}

/* should be called with rcu_read_lock */
int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
		     struct fib_result *res, int fib_flags)
{
	struct trie *t = (struct trie *) tb->tb_data;
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie_use_stats __percpu *stats = t->stats;
#endif
	const t_key key = ntohl(flp->daddr);
	struct key_vector *n, *pn;
	struct fib_alias *fa;
	unsigned long index;
	t_key cindex;

	pn = t->kv;
	cindex = 0;

	n = get_child_rcu(pn, cindex);
	if (!n)
		return -EAGAIN;

#ifdef CONFIG_IP_FIB_TRIE_STATS
	this_cpu_inc(stats->gets);
#endif

	/* Step 1: Travel to the longest prefix match in the trie */
	for (;;) {
		index = get_cindex(key, n);

		/* This bit of code is a bit tricky but it combines multiple
		 * checks into a single check.  The prefix consists of the
		 * prefix plus zeros for the "bits" in the prefix. The index
		 * is the difference between the key and this value.  From
		 * this we can actually derive several pieces of data.
		 *   if (index >= (1ul << bits))
		 *     we have a mismatch in skip bits and failed
		 *   else
		 *     we know the value is cindex
		 *
		 * This check is safe even if bits == KEYLENGTH due to the
		 * fact that we can only allocate a node with 32 bits if a
		 * long is greater than 32 bits.
		 */
		if (index >= (1ul << n->bits))
			break;

		/* we have found a leaf. Prefixes have already been compared */
		if (IS_LEAF(n))
			goto found;

		/* only record pn and cindex if we are going to be chopping
		 * bits later.  Otherwise we are just wasting cycles.
		 */
		if (n->slen > n->pos) {
			pn = n;
			cindex = index;
		}

		n = get_child_rcu(n, index);
		if (unlikely(!n))
			goto backtrace;
	}

	/* Step 2: Sort out leaves and begin backtracing for longest prefix */
	for (;;) {
		/* record the pointer where our next node pointer is stored */
		struct key_vector __rcu **cptr = n->tnode;

		/* This test verifies that none of the bits that differ
		 * between the key and the prefix exist in the region of
		 * the lsb and higher in the prefix.
		 */
		if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
			goto backtrace;

		/* exit out and process leaf */
		if (unlikely(IS_LEAF(n)))
			break;

		/* Don't bother recording parent info.  Since we are in
		 * prefix match mode we will have to come back to wherever
		 * we started this traversal anyway
		 */

		while ((n = rcu_dereference(*cptr)) == NULL) {
backtrace:
#ifdef CONFIG_IP_FIB_TRIE_STATS
			if (!n)
				this_cpu_inc(stats->null_node_hit);
#endif
			/* If we are at cindex 0 there are no more bits for
			 * us to strip at this level so we must ascend back
			 * up one level to see if there are any more bits to
			 * be stripped there.
			 */
			while (!cindex) {
				t_key pkey = pn->key;

				/* If we don't have a parent then there is
				 * nothing for us to do as we do not have any
				 * further nodes to parse.
				 */
				if (IS_TRIE(pn))
					return -EAGAIN;
#ifdef CONFIG_IP_FIB_TRIE_STATS
				this_cpu_inc(stats->backtrack);
#endif
				/* Get Child's index */
				pn = node_parent_rcu(pn);
				cindex = get_index(pkey, pn);
			}

			/* strip the least significant bit from the cindex */
			cindex &= cindex - 1;

			/* grab pointer for next child node */
			cptr = &pn->tnode[cindex];
		}
	}

found:
	/* this line carries forward the xor from earlier in the function */
	index = key ^ n->key;

	/* Step 3: Process the leaf, if that fails fall back to backtracing */
	hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {
		struct fib_info *fi = fa->fa_info;
		int nhsel, err;

		if ((index >= (1ul << fa->fa_slen)) &&
		    ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen != KEYLENGTH)))
			continue;
		if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
			continue;
		if (fi->fib_dead)
			continue;
		if (fa->fa_info->fib_scope < flp->flowi4_scope)
			continue;
		fib_alias_accessed(fa);
		err = fib_props[fa->fa_type].error;
		if (unlikely(err < 0)) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
			this_cpu_inc(stats->semantic_match_passed);
#endif
			return err;
		}
		if (fi->fib_flags & RTNH_F_DEAD)
			continue;
		for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
			const struct fib_nh *nh = &fi->fib_nh[nhsel];

			if (nh->nh_flags & RTNH_F_DEAD)
				continue;
			if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
				continue;

			if (!(fib_flags & FIB_LOOKUP_NOREF))
				atomic_inc(&fi->fib_clntref);

			res->prefixlen = KEYLENGTH - fa->fa_slen;
			res->nh_sel = nhsel;
			res->type = fa->fa_type;
			res->scope = fi->fib_scope;
			res->fi = fi;
			res->table = tb;
			res->fa_head = &n->leaf;
#ifdef CONFIG_IP_FIB_TRIE_STATS
			this_cpu_inc(stats->semantic_match_passed);
#endif
			return err;
		}
	}
#ifdef CONFIG_IP_FIB_TRIE_STATS
	this_cpu_inc(stats->semantic_match_miss);
#endif
	goto backtrace;
}
EXPORT_SYMBOL_GPL(fib_table_lookup);

static void fib_remove_alias(struct trie *t, struct key_vector *tp,
			     struct key_vector *l, struct fib_alias *old)
{
	/* record the location of the previous list_info entry */
	struct hlist_node **pprev = old->fa_list.pprev;
	struct fib_alias *fa = hlist_entry(pprev, typeof(*fa), fa_list.next);

	/* remove the fib_alias from the list */
	hlist_del_rcu(&old->fa_list);

	/* if we emptied the list this leaf will be freed and we can sort
	 * out parent suffix lengths as a part of trie_rebalance
	 */
	if (hlist_empty(&l->leaf)) {
		put_child_root(tp, l->key, NULL);
		node_free(l);
		trie_rebalance(t, tp);
		return;
	}

	/* only access fa if it is pointing at the last valid hlist_node */
	if (*pprev)
		return;

	/* update the trie with the latest suffix length */
	l->slen = fa->fa_slen;
	leaf_pull_suffix(tp, l);
}

/* Caller must hold RTNL. */
int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct fib_alias *fa, *fa_to_delete;
	struct key_vector *l, *tp;
	u8 plen = cfg->fc_dst_len;
	u8 slen = KEYLENGTH - plen;
	u8 tos = cfg->fc_tos;
	u32 key;

	if (plen > KEYLENGTH)
		return -EINVAL;

	key = ntohl(cfg->fc_dst);

	if ((plen < KEYLENGTH) && (key << plen))
		return -EINVAL;

	l = fib_find_node(t, &tp, key);
	if (!l)
		return -ESRCH;

	fa = fib_find_alias(&l->leaf, slen, tos, 0, tb->tb_id);
	if (!fa)
		return -ESRCH;

	pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);

	fa_to_delete = NULL;
	hlist_for_each_entry_from(fa, fa_list) {
		struct fib_info *fi = fa->fa_info;

		if ((fa->fa_slen != slen) ||
		    (fa->tb_id != tb->tb_id) ||
		    (fa->fa_tos != tos))
			break;

		if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) &&
		    (cfg->fc_scope == RT_SCOPE_NOWHERE ||
		     fa->fa_info->fib_scope == cfg->fc_scope) &&
		    (!cfg->fc_prefsrc ||
		     fi->fib_prefsrc == cfg->fc_prefsrc) &&
		    (!cfg->fc_protocol ||
		     fi->fib_protocol == cfg->fc_protocol) &&
		    fib_nh_match(cfg, fi) == 0) {
			fa_to_delete = fa;
			break;
		}
	}

	if (!fa_to_delete)
		return -ESRCH;

	netdev_switch_fib_ipv4_del(key, plen, fa_to_delete->fa_info, tos,
				   cfg->fc_type, tb->tb_id);

	rtmsg_fib(RTM_DELROUTE, htonl(key), fa_to_delete, plen, tb->tb_id,
		  &cfg->fc_nlinfo, 0);

	if (!plen)
		tb->tb_num_default--;

	fib_remove_alias(t, tp, l, fa_to_delete);

	if (fa_to_delete->fa_state & FA_S_ACCESSED)
		rt_cache_flush(cfg->fc_nlinfo.nl_net);

	fib_release_info(fa_to_delete->fa_info);
	alias_free_mem_rcu(fa_to_delete);
	return 0;
}

/* Scan for the next leaf starting at the provided key value */
static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)
{
	struct key_vector *pn, *n = *tn;
	unsigned long cindex;

	/* this loop is meant to try and find the key in the trie */
	do {
		/* record parent and next child index */
		pn = n;
		cindex = key ? get_index(key, pn) : 0;

		if (cindex >> pn->bits)
			break;

		/* descend into the next child */
		n = get_child_rcu(pn, cindex++);
		if (!n)
			break;

		/* guarantee forward progress on the keys */
		if (IS_LEAF(n) && (n->key >= key))
			goto found;
	} while (IS_TNODE(n));

	/* this loop will search for the next leaf with a greater key */
	while (!IS_TRIE(pn)) {
		/* if we exhausted the parent node we will need to climb */
		if (cindex >= (1ul << pn->bits)) {
			t_key pkey = pn->key;

			pn = node_parent_rcu(pn);
			cindex = get_index(pkey, pn) + 1;
			continue;
		}

		/* grab the next available node */
		n = get_child_rcu(pn, cindex++);
		if (!n)
			continue;

		/* no need to compare keys since we bumped the index */
		if (IS_LEAF(n))
			goto found;

		/* Rescan start scanning in new node */
		pn = n;
		cindex = 0;
	}

	*tn = pn;
	return NULL; /* Root of trie */
found:
	/* if we are at the limit for keys just return NULL for the tnode */
	*tn = pn;
	return n;
}

static void fib_trie_free(struct fib_table *tb)
{
	struct trie *t = (struct trie *)tb->tb_data;
	struct key_vector *pn = t->kv;
	unsigned long cindex = 1;
	struct hlist_node *tmp;
	struct fib_alias *fa;

	/* walk trie in reverse order and free everything */
	for (;;) {
		struct key_vector *n;

		if (!(cindex--)) {
			t_key pkey = pn->key;

			if (IS_TRIE(pn))
				break;

			n = pn;
			pn = node_parent(pn);

			/* drop emptied tnode */
			put_child_root(pn, n->key, NULL);
			node_free(n);

			cindex = get_index(pkey, pn);

			continue;
		}

		/* grab the next available node */
		n = get_child(pn, cindex);
		if (!n)
			continue;

		if (IS_TNODE(n)) {
			/* record pn and cindex for leaf walking */
			pn = n;
			cindex = 1ul << n->bits;

			continue;
		}

		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
			hlist_del_rcu(&fa->fa_list);
			alias_free_mem_rcu(fa);
		}

		put_child_root(pn, n->key, NULL);
		node_free(n);
	}

#ifdef CONFIG_IP_FIB_TRIE_STATS
	free_percpu(t->stats);
#endif
	kfree(tb);
}

struct fib_table *fib_trie_unmerge(struct fib_table *oldtb)
{
	struct trie *ot = (struct trie *)oldtb->tb_data;
	struct key_vector *l, *tp = ot->kv;
	struct fib_table *local_tb;
	struct fib_alias *fa;
	struct trie *lt;
	t_key key = 0;

	if (oldtb->tb_data == oldtb->__data)
		return oldtb;

	local_tb = fib_trie_table(RT_TABLE_LOCAL, NULL);
	if (!local_tb)
		return NULL;

	lt = (struct trie *)local_tb->tb_data;

	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
		struct key_vector *local_l = NULL, *local_tp;

		hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
			struct fib_alias *new_fa;

			if (local_tb->tb_id != fa->tb_id)
				continue;

			/* clone fa for new local table */
			new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
			if (!new_fa)
				goto out;

			memcpy(new_fa, fa, sizeof(*fa));

			/* insert clone into table */
			if (!local_l)
				local_l = fib_find_node(lt, &local_tp, l->key);

			if (fib_insert_alias(lt, local_tp, local_l, new_fa,
					     NULL, l->key))
				goto out;
		}

		/* stop loop if key wrapped back to 0 */
		key = l->key + 1;
		if (key < l->key)
			break;
	}

	return local_tb;
out:
	fib_trie_free(local_tb);

	return NULL;
}

/* Caller must hold RTNL */
void fib_table_flush_external(struct fib_table *tb)
{
	struct trie *t = (struct trie *)tb->tb_data;
	struct key_vector *pn = t->kv;
	unsigned long cindex = 1;
	struct hlist_node *tmp;
	struct fib_alias *fa;

	/* walk trie in reverse order */
	for (;;) {
		unsigned char slen = 0;
		struct key_vector *n;

		if (!(cindex--)) {
			t_key pkey = pn->key;

			/* cannot resize the trie vector */
			if (IS_TRIE(pn))
				break;

			/* resize completed node */
			pn = resize(t, pn);
			cindex = get_index(pkey, pn);

			continue;
		}

		/* grab the next available node */
		n = get_child(pn, cindex);
		if (!n)
			continue;

		if (IS_TNODE(n)) {
			/* record pn and cindex for leaf walking */
			pn = n;
			cindex = 1ul << n->bits;

			continue;
		}

		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
			struct fib_info *fi = fa->fa_info;

			/* if alias was cloned to local then we just
			 * need to remove the local copy from main
			 */
			if (tb->tb_id != fa->tb_id) {
				hlist_del_rcu(&fa->fa_list);
				alias_free_mem_rcu(fa);
				continue;
			}

			/* record local slen */
			slen = fa->fa_slen;

			if (!fi || !(fi->fib_flags & RTNH_F_OFFLOAD))
				continue;

			netdev_switch_fib_ipv4_del(n->key,
						   KEYLENGTH - fa->fa_slen,
						   fi, fa->fa_tos,
						   fa->fa_type, tb->tb_id);
		}

		/* update leaf slen */
		n->slen = slen;

		if (hlist_empty(&n->leaf)) {
			put_child_root(pn, n->key, NULL);
			node_free(n);
		} else {
			leaf_pull_suffix(pn, n);
		}
	}
}

/* Caller must hold RTNL. */
int fib_table_flush(struct fib_table *tb)
{
	struct trie *t = (struct trie *)tb->tb_data;
	struct key_vector *pn = t->kv;
	unsigned long cindex = 1;
	struct hlist_node *tmp;
	struct fib_alias *fa;
	int found = 0;

	/* walk trie in reverse order */
	for (;;) {
		unsigned char slen = 0;
		struct key_vector *n;

		if (!(cindex--)) {
			t_key pkey = pn->key;

			/* cannot resize the trie vector */
			if (IS_TRIE(pn))
				break;

			/* resize completed node */
			pn = resize(t, pn);
			cindex = get_index(pkey, pn);

			continue;
		}

		/* grab the next available node */
		n = get_child(pn, cindex);
		if (!n)
			continue;

		if (IS_TNODE(n)) {
			/* record pn and cindex for leaf walking */
			pn = n;
			cindex = 1ul << n->bits;

			continue;
		}

		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {
			struct fib_info *fi = fa->fa_info;

			if (!fi || !(fi->fib_flags & RTNH_F_DEAD)) {
				slen = fa->fa_slen;
				continue;
			}

			netdev_switch_fib_ipv4_del(n->key,
						   KEYLENGTH - fa->fa_slen,
						   fi, fa->fa_tos,
						   fa->fa_type, tb->tb_id);
			hlist_del_rcu(&fa->fa_list);
			fib_release_info(fa->fa_info);
			alias_free_mem_rcu(fa);
			found++;
		}

		/* update leaf slen */
		n->slen = slen;

		if (hlist_empty(&n->leaf)) {
			put_child_root(pn, n->key, NULL);
			node_free(n);
		} else {
			leaf_pull_suffix(pn, n);
		}
	}

	pr_debug("trie_flush found=%d\n", found);
	return found;
}

static void __trie_free_rcu(struct rcu_head *head)
{
	struct fib_table *tb = container_of(head, struct fib_table, rcu);
#ifdef CONFIG_IP_FIB_TRIE_STATS
	struct trie *t = (struct trie *)tb->tb_data;

	if (tb->tb_data == tb->__data)
		free_percpu(t->stats);
#endif /* CONFIG_IP_FIB_TRIE_STATS */
	kfree(tb);
}

void fib_free_table(struct fib_table *tb)
{
	call_rcu(&tb->rcu, __trie_free_rcu);
}

static int fn_trie_dump_leaf(struct key_vector *l, struct fib_table *tb,
			     struct sk_buff *skb, struct netlink_callback *cb)
{
	__be32 xkey = htonl(l->key);
	struct fib_alias *fa;
	int i, s_i;

	s_i = cb->args[4];
	i = 0;

	/* rcu_read_lock is hold by caller */
	hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) {
		if (i < s_i) {
			i++;
			continue;
		}

		if (tb->tb_id != fa->tb_id) {
			i++;
			continue;
		}

		if (fib_dump_info(skb, NETLINK_CB(cb->skb).portid,
				  cb->nlh->nlmsg_seq,
				  RTM_NEWROUTE,
				  tb->tb_id,
				  fa->fa_type,
				  xkey,
				  KEYLENGTH - fa->fa_slen,
				  fa->fa_tos,
				  fa->fa_info, NLM_F_MULTI) < 0) {
			cb->args[4] = i;
			return -1;
		}
		i++;
	}

	cb->args[4] = i;
	return skb->len;
}

/* rcu_read_lock needs to be hold by caller from readside */
int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
		   struct netlink_callback *cb)
{
	struct trie *t = (struct trie *)tb->tb_data;
	struct key_vector *l, *tp = t->kv;
	/* Dump starting at last key.
	 * Note: 0.0.0.0/0 (ie default) is first key.
	 */
	int count = cb->args[2];
	t_key key = cb->args[3];

	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
		if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
			cb->args[3] = key;
			cb->args[2] = count;
			return -1;
		}

		++count;
		key = l->key + 1;

		memset(&cb->args[4], 0,
		       sizeof(cb->args) - 4*sizeof(cb->args[0]));

		/* stop loop if key wrapped back to 0 */
		if (key < l->key)
			break;
	}

	cb->args[3] = key;
	cb->args[2] = count;

	return skb->len;
}

void __init fib_trie_init(void)
{
	fn_alias_kmem = kmem_cache_create("ip_fib_alias",
					  sizeof(struct fib_alias),
					  0, SLAB_PANIC, NULL);

	trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
					   LEAF_SIZE,
					   0, SLAB_PANIC, NULL);
}

struct fib_table *fib_trie_table(u32 id, struct fib_table *alias)
{
	struct fib_table *tb;
	struct trie *t;
	size_t sz = sizeof(*tb);

	if (!alias)
		sz += sizeof(struct trie);

	tb = kzalloc(sz, GFP_KERNEL);
	if (!tb)
		return NULL;

	tb->tb_id = id;
	tb->tb_default = -1;
	tb->tb_num_default = 0;
	tb->tb_data = (alias ? alias->__data : tb->__data);

	if (alias)
		return tb;

	t = (struct trie *) tb->tb_data;
	t->kv[0].pos = KEYLENGTH;
	t->kv[0].slen = KEYLENGTH;
#ifdef CONFIG_IP_FIB_TRIE_STATS
	t->stats = alloc_percpu(struct trie_use_stats);
	if (!t->stats) {
		kfree(tb);
		tb = NULL;
	}
#endif

	return tb;
}

#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
	struct seq_net_private p;
	struct fib_table *tb;
	struct key_vector *tnode;
	unsigned int index;
	unsigned int depth;
};

static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter)
{
	unsigned long cindex = iter->index;
	struct key_vector *pn = iter->tnode;
	t_key pkey;

	pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
		 iter->tnode, iter->index, iter->depth);

	while (!IS_TRIE(pn)) {
		while (cindex < child_length(pn)) {
			struct key_vector *n = get_child_rcu(pn, cindex++);

			if (!n)
				continue;

			if (IS_LEAF(n)) {
				iter->tnode = pn;
				iter->index = cindex;
			} else {
				/* push down one level */
				iter->tnode = n;
				iter->index = 0;
				++iter->depth;
			}

			return n;
		}

		/* Current node exhausted, pop back up */
		pkey = pn->key;
		pn = node_parent_rcu(pn);
		cindex = get_index(pkey, pn) + 1;
		--iter->depth;
	}

	/* record root node so further searches know we are done */
	iter->tnode = pn;
	iter->index = 0;

	return NULL;
}

static struct key_vector *fib_trie_get_first(struct fib_trie_iter *iter,
					     struct trie *t)
{
	struct key_vector *n, *pn = t->kv;

	if (!t)
		return NULL;

	n = rcu_dereference(pn->tnode[0]);
	if (!n)
		return NULL;

	if (IS_TNODE(n)) {
		iter->tnode = n;
		iter->index = 0;
		iter->depth = 1;
	} else {
		iter->tnode = pn;
		iter->index = 0;
		iter->depth = 0;
	}

	return n;
}

static void trie_collect_stats(struct trie *t, struct trie_stat *s)
{
	struct key_vector *n;
	struct fib_trie_iter iter;

	memset(s, 0, sizeof(*s));

	rcu_read_lock();
	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
		if (IS_LEAF(n)) {
			struct fib_alias *fa;

			s->leaves++;
			s->totdepth += iter.depth;
			if (iter.depth > s->maxdepth)
				s->maxdepth = iter.depth;

			hlist_for_each_entry_rcu(fa, &n->leaf, fa_list)
				++s->prefixes;
		} else {
			s->tnodes++;
			if (n->bits < MAX_STAT_DEPTH)
				s->nodesizes[n->bits]++;
			s->nullpointers += tn_info(n)->empty_children;
		}
	}
	rcu_read_unlock();
}

/*
 *	This outputs /proc/net/fib_triestats
 */
static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
{
	unsigned int i, max, pointers, bytes, avdepth;

	if (stat->leaves)
		avdepth = stat->totdepth*100 / stat->leaves;
	else
		avdepth = 0;

	seq_printf(seq, "\tAver depth:     %u.%02d\n",