#include <asm/uaccess.h>
#include <asm/system.h>
-#include <asm/bitops.h>
+#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/netlink.h>
#include <linux/init.h>
#include <linux/list.h>
+#include <net/net_namespace.h>
#include <net/ip.h>
#include <net/protocol.h>
#include <net/route.h>
#define MAX_STAT_DEPTH 32
#define KEYLENGTH (8*sizeof(t_key))
-#define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
-#define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
typedef unsigned int t_key;
#define T_TNODE 0
#define T_LEAF 1
#define NODE_TYPE_MASK 0x1UL
-#define NODE_PARENT(node) \
- ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
-
#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
-#define NODE_SET_PARENT(node, ptr) \
- rcu_assign_pointer((node)->parent, \
- ((unsigned long)(ptr)) | NODE_TYPE(node))
-
#define IS_TNODE(n) (!(n->parent & T_LEAF))
#define IS_LEAF(n) (n->parent & T_LEAF)
static void tnode_free(struct tnode *tn);
static struct kmem_cache *fn_alias_kmem __read_mostly;
-static struct trie *trie_local = NULL, *trie_main = NULL;
+static inline struct tnode *node_parent(struct node *node)
+{
+ struct tnode *ret;
+
+ ret = (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
+ return rcu_dereference(ret);
+}
+
+static inline void node_set_parent(struct node *node, struct tnode *ptr)
+{
+ rcu_assign_pointer(node->parent,
+ (unsigned long)ptr | NODE_TYPE(node));
+}
/* rcu_read_lock needs to be hold by caller from readside */
return 1 << tn->bits;
}
+static inline t_key mask_pfx(t_key k, unsigned short l)
+{
+ return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
+}
+
static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
{
if (offset < KEYLENGTH)
tn->full_children++;
if (n)
- NODE_SET_PARENT(n, tn);
+ node_set_parent(n, tn);
rcu_assign_pointer(tn->child[i], n);
}
continue;
/* compress one level */
- NODE_SET_PARENT(n, NULL);
+ node_set_parent(n, NULL);
tnode_free(tn);
return n;
}
/* compress one level */
- NODE_SET_PARENT(n, NULL);
+ node_set_parent(n, NULL);
tnode_free(tn);
return n;
}
inode->pos == oldtnode->pos + oldtnode->bits &&
inode->bits > 1) {
struct tnode *left, *right;
- t_key m = TKEY_GET_MASK(inode->pos, 1);
+ t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
left = tnode_new(inode->key&(~m), inode->pos + 1,
inode->bits - 1);
static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
{
int wasfull;
- t_key cindex, key;
- struct tnode *tp = NULL;
-
- key = tn->key;
-
- while (tn != NULL && NODE_PARENT(tn) != NULL) {
+ t_key cindex, key = tn->key;
+ struct tnode *tp;
- tp = NODE_PARENT(tn);
+ while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
cindex = tkey_extract_bits(key, tp->pos, tp->bits);
wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
tn = (struct tnode *) resize (t, (struct tnode *)tn);
tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
- if (!NODE_PARENT(tn))
+ tp = node_parent((struct node *) tn);
+ if (!tp)
break;
-
- tn = NODE_PARENT(tn);
+ tn = tp;
}
+
/* Handle last (top) tnode */
if (IS_TNODE(tn))
tn = (struct tnode*) resize(t, (struct tnode *)tn);
pos = tn->pos + tn->bits;
n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
- BUG_ON(n && NODE_PARENT(n) != tn);
+ BUG_ON(n && node_parent(n) != tn);
} else
break;
}
if (t->trie && n == NULL) {
/* Case 2: n is NULL, and will just insert a new leaf */
- NODE_SET_PARENT(l, tp);
+ node_set_parent((struct node *)l, tp);
cindex = tkey_extract_bits(key, tp->pos, tp->bits);
put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
goto err;
}
- NODE_SET_PARENT(tn, tp);
+ node_set_parent((struct node *)tn, tp);
missbit = tkey_extract_bits(key, newpos, 1);
put_child(t, tn, missbit, (struct node *)l);
struct fib_info *fi_drop;
u8 state;
+ if (fi->fib_treeref > 1)
+ goto out;
+
err = -ENOBUFS;
new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);
if (new_fa == NULL)
bits = pn->bits;
if (!chopped_off)
- cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);
+ cindex = tkey_extract_bits(mask_pfx(key, current_prefix_length),
+ pos, bits);
n = tnode_get_child(pn, cindex);
* to find a matching prefix.
*/
- node_prefix = MASK_PFX(cn->key, cn->pos);
- key_prefix = MASK_PFX(key, cn->pos);
+ node_prefix = mask_pfx(cn->key, cn->pos);
+ key_prefix = mask_pfx(key, cn->pos);
pref_mismatch = key_prefix^node_prefix;
mp = 0;
if (chopped_off <= pn->bits) {
cindex &= ~(1 << (chopped_off-1));
} else {
- if (NODE_PARENT(pn) == NULL)
+ struct tnode *parent = node_parent((struct node *) pn);
+ if (!parent)
goto failed;
/* Get Child's index */
- cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
- pn = NODE_PARENT(pn);
+ cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
+ pn = parent;
chopped_off = 0;
#ifdef CONFIG_IP_FIB_TRIE_STATS
check_tnode(tn);
n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
- BUG_ON(n && NODE_PARENT(n) != tn);
+ BUG_ON(n && node_parent(n) != tn);
}
l = (struct leaf *) n;
t->revision++;
t->size--;
- tp = NODE_PARENT(n);
+ tp = node_parent(n);
tnode_free((struct tnode *) n);
if (tp) {
p = (struct tnode*) trie; /* Start */
} else
- p = (struct tnode *) NODE_PARENT(c);
+ p = node_parent(c);
while (p) {
int pos, last;
up:
/* No more children go up one step */
c = (struct node *) p;
- p = (struct tnode *) NODE_PARENT(p);
+ p = node_parent(c);
}
return NULL; /* Ready. Root of trie */
}
trie_init(t);
- if (id == RT_TABLE_LOCAL)
- trie_local = t;
- else if (id == RT_TABLE_MAIN)
- trie_main = t;
-
if (id == RT_TABLE_LOCAL)
printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
#ifdef CONFIG_PROC_FS
/* Depth first Trie walk iterator */
struct fib_trie_iter {
+ struct trie *trie_local, *trie_main;
struct tnode *tnode;
struct trie *trie;
unsigned index;
}
/* Current node exhausted, pop back up */
- p = NODE_PARENT(tn);
+ p = node_parent((struct node *)tn);
if (p) {
cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
tn = p;
static int fib_triestat_seq_show(struct seq_file *seq, void *v)
{
+ struct trie *trie_local, *trie_main;
struct trie_stat *stat;
+ struct fib_table *tb;
+
+ trie_local = NULL;
+ tb = fib_get_table(RT_TABLE_LOCAL);
+ if (tb)
+ trie_local = (struct trie *) tb->tb_data;
+
+ trie_main = NULL;
+ tb = fib_get_table(RT_TABLE_MAIN);
+ if (tb)
+ trie_main = (struct trie *) tb->tb_data;
+
stat = kmalloc(sizeof(*stat), GFP_KERNEL);
if (!stat)
loff_t idx = 0;
struct node *n;
- for (n = fib_trie_get_first(iter, trie_local);
+ for (n = fib_trie_get_first(iter, iter->trie_local);
n; ++idx, n = fib_trie_get_next(iter)) {
if (pos == idx)
return n;
}
- for (n = fib_trie_get_first(iter, trie_main);
+ for (n = fib_trie_get_first(iter, iter->trie_main);
n; ++idx, n = fib_trie_get_next(iter)) {
if (pos == idx)
return n;
static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
{
+ struct fib_trie_iter *iter = seq->private;
+ struct fib_table *tb;
+
+ if (!iter->trie_local) {
+ tb = fib_get_table(RT_TABLE_LOCAL);
+ if (tb)
+ iter->trie_local = (struct trie *) tb->tb_data;
+ }
+ if (!iter->trie_main) {
+ tb = fib_get_table(RT_TABLE_MAIN);
+ if (tb)
+ iter->trie_main = (struct trie *) tb->tb_data;
+ }
rcu_read_lock();
if (*pos == 0)
return SEQ_START_TOKEN;
- return fib_trie_get_idx(seq->private, *pos - 1);
+ return fib_trie_get_idx(iter, *pos - 1);
}
static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
return v;
/* continue scan in next trie */
- if (iter->trie == trie_local)
- return fib_trie_get_first(iter, trie_main);
+ if (iter->trie == iter->trie_local)
+ return fib_trie_get_first(iter, iter->trie_main);
return NULL;
}
if (v == SEQ_START_TOKEN)
return 0;
- if (!NODE_PARENT(n)) {
- if (iter->trie == trie_local)
+ if (!node_parent(n)) {
+ if (iter->trie == iter->trie_local)
seq_puts(seq, "<local>:\n");
else
seq_puts(seq, "<main>:\n");
if (IS_TNODE(n)) {
struct tnode *tn = (struct tnode *) n;
- __be32 prf = htonl(MASK_PFX(tn->key, tn->pos));
+ __be32 prf = htonl(mask_pfx(tn->key, tn->pos));
seq_indent(seq, iter->depth-1);
seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
static int fib_trie_seq_open(struct inode *inode, struct file *file)
{
- struct seq_file *seq;
- int rc = -ENOMEM;
- struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
-
- if (!s)
- goto out;
-
- rc = seq_open(file, &fib_trie_seq_ops);
- if (rc)
- goto out_kfree;
-
- seq = file->private_data;
- seq->private = s;
- memset(s, 0, sizeof(*s));
-out:
- return rc;
-out_kfree:
- kfree(s);
- goto out;
+ return seq_open_private(file, &fib_trie_seq_ops,
+ sizeof(struct fib_trie_iter));
}
static const struct file_operations fib_trie_fops = {
return 0;
}
- if (iter->trie == trie_local)
+ if (iter->trie == iter->trie_local)
return 0;
if (IS_TNODE(l))
return 0;
static int fib_route_seq_open(struct inode *inode, struct file *file)
{
- struct seq_file *seq;
- int rc = -ENOMEM;
- struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
-
- if (!s)
- goto out;
-
- rc = seq_open(file, &fib_route_seq_ops);
- if (rc)
- goto out_kfree;
-
- seq = file->private_data;
- seq->private = s;
- memset(s, 0, sizeof(*s));
-out:
- return rc;
-out_kfree:
- kfree(s);
- goto out;
+ return seq_open_private(file, &fib_route_seq_ops,
+ sizeof(struct fib_trie_iter));
}
static const struct file_operations fib_route_fops = {
int __init fib_proc_init(void)
{
- if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops))
+ if (!proc_net_fops_create(&init_net, "fib_trie", S_IRUGO, &fib_trie_fops))
goto out1;
- if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops))
+ if (!proc_net_fops_create(&init_net, "fib_triestat", S_IRUGO, &fib_triestat_fops))
goto out2;
- if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops))
+ if (!proc_net_fops_create(&init_net, "route", S_IRUGO, &fib_route_fops))
goto out3;
return 0;
out3:
- proc_net_remove("fib_triestat");
+ proc_net_remove(&init_net, "fib_triestat");
out2:
- proc_net_remove("fib_trie");
+ proc_net_remove(&init_net, "fib_trie");
out1:
return -ENOMEM;
}
void __init fib_proc_exit(void)
{
- proc_net_remove("fib_trie");
- proc_net_remove("fib_triestat");
- proc_net_remove("route");
+ proc_net_remove(&init_net, "fib_trie");
+ proc_net_remove(&init_net, "fib_triestat");
+ proc_net_remove(&init_net, "route");
}
#endif /* CONFIG_PROC_FS */
projects / linux-2.6-omap-h63xx.git / blobdiff