[net-next-2.6.git] / net / decnet / dn_table.c

/*
 * DECnet       An implementation of the DECnet protocol suite for the LINUX
 *              operating system.  DECnet is implemented using the  BSD Socket
 *              interface as the means of communication with the user level.
 *
 *              DECnet Routing Forwarding Information Base (Routing Tables)
 *
 * Author:      Steve Whitehouse <SteveW@ACM.org>
 *              Mostly copied from the IPv4 routing code
 *
 *
 * Changes:
 *
 */
#include <linux/string.h>
#include <linux/net.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/init.h>
#include <linux/skbuff.h>
#include <linux/netlink.h>
#include <linux/rtnetlink.h>
#include <linux/proc_fs.h>
#include <linux/netdevice.h>
#include <linux/timer.h>
#include <linux/spinlock.h>
#include <asm/atomic.h>
#include <asm/uaccess.h>
#include <linux/route.h> /* RTF_xxx */
#include <net/neighbour.h>
#include <net/dst.h>
#include <net/flow.h>
#include <net/fib_rules.h>
#include <net/dn.h>
#include <net/dn_route.h>
#include <net/dn_fib.h>
#include <net/dn_neigh.h>
#include <net/dn_dev.h>

struct dn_zone
{
	struct dn_zone		*dz_next;
	struct dn_fib_node 	**dz_hash;
	int			dz_nent;
	int			dz_divisor;
	u32			dz_hashmask;
#define DZ_HASHMASK(dz)	((dz)->dz_hashmask)
	int			dz_order;
	__le16			dz_mask;
#define DZ_MASK(dz)	((dz)->dz_mask)
};

struct dn_hash
{
	struct dn_zone	*dh_zones[17];
	struct dn_zone	*dh_zone_list;
};

#define dz_key_0(key)		((key).datum = 0)
#define dz_prefix(key,dz)	((key).datum)

#define for_nexthops(fi) { int nhsel; const struct dn_fib_nh *nh;\
        for(nhsel = 0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++)

#define endfor_nexthops(fi) }

#define DN_MAX_DIVISOR 1024
#define DN_S_ZOMBIE 1
#define DN_S_ACCESSED 2

#define DN_FIB_SCAN(f, fp) \
for( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next)

#define DN_FIB_SCAN_KEY(f, fp, key) \
for( ; ((f) = *(fp)) != NULL && dn_key_eq((f)->fn_key, (key)); (fp) = &(f)->fn_next)

#define RT_TABLE_MIN 1

static DEFINE_RWLOCK(dn_fib_tables_lock);
struct dn_fib_table *dn_fib_tables[RT_TABLE_MAX + 1];

static kmem_cache_t *dn_hash_kmem __read_mostly;
static int dn_fib_hash_zombies;

static inline dn_fib_idx_t dn_hash(dn_fib_key_t key, struct dn_zone *dz)
{
	u16 h = dn_ntohs(key.datum)>>(16 - dz->dz_order);
	h ^= (h >> 10);
	h ^= (h >> 6);
	h &= DZ_HASHMASK(dz);
	return *(dn_fib_idx_t *)&h;
}

static inline dn_fib_key_t dz_key(__le16 dst, struct dn_zone *dz)
{
	dn_fib_key_t k;
	k.datum = dst & DZ_MASK(dz);
	return k;
}

static inline struct dn_fib_node **dn_chain_p(dn_fib_key_t key, struct dn_zone *dz)
{
	return &dz->dz_hash[dn_hash(key, dz).datum];
}

static inline struct dn_fib_node *dz_chain(dn_fib_key_t key, struct dn_zone *dz)
{
	return dz->dz_hash[dn_hash(key, dz).datum];
}

static inline int dn_key_eq(dn_fib_key_t a, dn_fib_key_t b)
{
	return a.datum == b.datum;
}

static inline int dn_key_leq(dn_fib_key_t a, dn_fib_key_t b)
{
	return a.datum <= b.datum;
}

static inline void dn_rebuild_zone(struct dn_zone *dz,
				   struct dn_fib_node **old_ht,
				   int old_divisor)
{
	int i;
	struct dn_fib_node *f, **fp, *next;

	for(i = 0; i < old_divisor; i++) {
		for(f = old_ht[i]; f; f = f->fn_next) {
			next = f->fn_next;
			for(fp = dn_chain_p(f->fn_key, dz);
				*fp && dn_key_leq((*fp)->fn_key, f->fn_key);
				fp = &(*fp)->fn_next)
				/* NOTHING */;
			f->fn_next = *fp;
			*fp = f;
		}
	}
}

static void dn_rehash_zone(struct dn_zone *dz)
{
	struct dn_fib_node **ht, **old_ht;
	int old_divisor, new_divisor;
	u32 new_hashmask;

	old_divisor = dz->dz_divisor;

	switch(old_divisor) {
		case 16:
			new_divisor = 256;
			new_hashmask = 0xFF;
			break;
		default:
			printk(KERN_DEBUG "DECnet: dn_rehash_zone: BUG! %d\n", old_divisor);
		case 256:
			new_divisor = 1024;
			new_hashmask = 0x3FF;
			break;
	}

	ht = kcalloc(new_divisor, sizeof(struct dn_fib_node*), GFP_KERNEL);
	if (ht == NULL)
		return;

	write_lock_bh(&dn_fib_tables_lock);
	old_ht = dz->dz_hash;
	dz->dz_hash = ht;
	dz->dz_hashmask = new_hashmask;
	dz->dz_divisor = new_divisor;
	dn_rebuild_zone(dz, old_ht, old_divisor);
	write_unlock_bh(&dn_fib_tables_lock);
	kfree(old_ht);
}

static void dn_free_node(struct dn_fib_node *f)
{
	dn_fib_release_info(DN_FIB_INFO(f));
	kmem_cache_free(dn_hash_kmem, f);
}


static struct dn_zone *dn_new_zone(struct dn_hash *table, int z)
{
	int i;
	struct dn_zone *dz = kzalloc(sizeof(struct dn_zone), GFP_KERNEL);
	if (!dz)
		return NULL;

	if (z) {
		dz->dz_divisor = 16;
		dz->dz_hashmask = 0x0F;
	} else {
		dz->dz_divisor = 1;
		dz->dz_hashmask = 0;
	}

	dz->dz_hash = kcalloc(dz->dz_divisor, sizeof(struct dn_fib_node *), GFP_KERNEL);
	if (!dz->dz_hash) {
		kfree(dz);
		return NULL;
	}

	dz->dz_order = z;
	dz->dz_mask = dnet_make_mask(z);

	for(i = z + 1; i <= 16; i++)
		if (table->dh_zones[i])
			break;

	write_lock_bh(&dn_fib_tables_lock);
	if (i>16) {
		dz->dz_next = table->dh_zone_list;
		table->dh_zone_list = dz;
	} else {
		dz->dz_next = table->dh_zones[i]->dz_next;
		table->dh_zones[i]->dz_next = dz;
	}
	table->dh_zones[z] = dz;
	write_unlock_bh(&dn_fib_tables_lock);
	return dz;
}


static int dn_fib_nh_match(struct rtmsg *r, struct nlmsghdr *nlh, struct dn_kern_rta *rta, struct dn_fib_info *fi)
{
	struct rtnexthop *nhp;
	int nhlen;

	if (rta->rta_priority && *rta->rta_priority != fi->fib_priority)
		return 1;

	if (rta->rta_oif || rta->rta_gw) {
		if ((!rta->rta_oif || *rta->rta_oif == fi->fib_nh->nh_oif) &&
		    (!rta->rta_gw  || memcmp(rta->rta_gw, &fi->fib_nh->nh_gw, 2) == 0))
			return 0;
		return 1;
	}

	if (rta->rta_mp == NULL)
		return 0;

	nhp = RTA_DATA(rta->rta_mp);
	nhlen = RTA_PAYLOAD(rta->rta_mp);

	for_nexthops(fi) {
		int attrlen = nhlen - sizeof(struct rtnexthop);
		__le16 gw;

		if (attrlen < 0 || (nhlen -= nhp->rtnh_len) < 0)
			return -EINVAL;
		if (nhp->rtnh_ifindex && nhp->rtnh_ifindex != nh->nh_oif)
			return 1;
		if (attrlen) {
			gw = dn_fib_get_attr16(RTNH_DATA(nhp), attrlen, RTA_GATEWAY);

			if (gw && gw != nh->nh_gw)
				return 1;
		}
		nhp = RTNH_NEXT(nhp);
	} endfor_nexthops(fi);

	return 0;
}

static int dn_fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
                        u32 tb_id, u8 type, u8 scope, void *dst, int dst_len,
                        struct dn_fib_info *fi, unsigned int flags)
{
        struct rtmsg *rtm;
        struct nlmsghdr *nlh;
        unsigned char *b = skb->tail;

        nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*rtm), flags);
        rtm = NLMSG_DATA(nlh);
        rtm->rtm_family = AF_DECnet;
        rtm->rtm_dst_len = dst_len;
        rtm->rtm_src_len = 0;
        rtm->rtm_tos = 0;
        rtm->rtm_table = tb_id;
	RTA_PUT_U32(skb, RTA_TABLE, tb_id);
        rtm->rtm_flags = fi->fib_flags;
        rtm->rtm_scope = scope;
	rtm->rtm_type  = type;
        if (rtm->rtm_dst_len)
                RTA_PUT(skb, RTA_DST, 2, dst);
        rtm->rtm_protocol = fi->fib_protocol;
        if (fi->fib_priority)
                RTA_PUT(skb, RTA_PRIORITY, 4, &fi->fib_priority);
	if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0)
		goto rtattr_failure;
        if (fi->fib_nhs == 1) {
                if (fi->fib_nh->nh_gw)
                        RTA_PUT(skb, RTA_GATEWAY, 2, &fi->fib_nh->nh_gw);
                if (fi->fib_nh->nh_oif)
                        RTA_PUT(skb, RTA_OIF, sizeof(int), &fi->fib_nh->nh_oif);
        }
        if (fi->fib_nhs > 1) {
                struct rtnexthop *nhp;
                struct rtattr *mp_head;
                if (skb_tailroom(skb) <= RTA_SPACE(0))
                        goto rtattr_failure;
                mp_head = (struct rtattr *)skb_put(skb, RTA_SPACE(0));

                for_nexthops(fi) {
                        if (skb_tailroom(skb) < RTA_ALIGN(RTA_ALIGN(sizeof(*nhp)) + 4))
                                goto rtattr_failure;
                        nhp = (struct rtnexthop *)skb_put(skb, RTA_ALIGN(sizeof(*nhp)));
                        nhp->rtnh_flags = nh->nh_flags & 0xFF;
                        nhp->rtnh_hops = nh->nh_weight - 1;
                        nhp->rtnh_ifindex = nh->nh_oif;
                        if (nh->nh_gw)
                                RTA_PUT(skb, RTA_GATEWAY, 2, &nh->nh_gw);
                        nhp->rtnh_len = skb->tail - (unsigned char *)nhp;
                } endfor_nexthops(fi);
                mp_head->rta_type = RTA_MULTIPATH;
                mp_head->rta_len = skb->tail - (u8*)mp_head;
        }

        nlh->nlmsg_len = skb->tail - b;
        return skb->len;


nlmsg_failure:
rtattr_failure:
        skb_trim(skb, b - skb->data);
        return -1;
}


static void dn_rtmsg_fib(int event, struct dn_fib_node *f, int z, u32 tb_id,
                        struct nlmsghdr *nlh, struct netlink_skb_parms *req)
{
        struct sk_buff *skb;
        u32 pid = req ? req->pid : 0;
        int size = NLMSG_SPACE(sizeof(struct rtmsg) + 256);

        skb = alloc_skb(size, GFP_KERNEL);
        if (!skb)
                return;

        if (dn_fib_dump_info(skb, pid, nlh->nlmsg_seq, event, tb_id, 
                                f->fn_type, f->fn_scope, &f->fn_key, z, 
                                DN_FIB_INFO(f), 0) < 0) {
                kfree_skb(skb);
                return;
        }
        NETLINK_CB(skb).dst_group = RTNLGRP_DECnet_ROUTE;
        if (nlh->nlmsg_flags & NLM_F_ECHO)
                atomic_inc(&skb->users);
        netlink_broadcast(rtnl, skb, pid, RTNLGRP_DECnet_ROUTE, GFP_KERNEL);
        if (nlh->nlmsg_flags & NLM_F_ECHO)
                netlink_unicast(rtnl, skb, pid, MSG_DONTWAIT);
}

static __inline__ int dn_hash_dump_bucket(struct sk_buff *skb, 
				struct netlink_callback *cb,
				struct dn_fib_table *tb,
				struct dn_zone *dz,
				struct dn_fib_node *f)
{
	int i, s_i;

	s_i = cb->args[3];
	for(i = 0; f; i++, f = f->fn_next) {
		if (i < s_i)
			continue;
		if (f->fn_state & DN_S_ZOMBIE)
			continue;
		if (dn_fib_dump_info(skb, NETLINK_CB(cb->skb).pid, 
				cb->nlh->nlmsg_seq,
				RTM_NEWROUTE,
				tb->n, 
				(f->fn_state & DN_S_ZOMBIE) ? 0 : f->fn_type,
				f->fn_scope, &f->fn_key, dz->dz_order, 
				f->fn_info, NLM_F_MULTI) < 0) {
			cb->args[3] = i;
			return -1;
		}
	}
	cb->args[3] = i;
	return skb->len;
}

static __inline__ int dn_hash_dump_zone(struct sk_buff *skb, 
				struct netlink_callback *cb,
				struct dn_fib_table *tb,
				struct dn_zone *dz)
{
	int h, s_h;

	s_h = cb->args[2];
	for(h = 0; h < dz->dz_divisor; h++) {
		if (h < s_h)
			continue;
		if (h > s_h)
			memset(&cb->args[3], 0, sizeof(cb->args) - 3*sizeof(cb->args[0]));
		if (dz->dz_hash == NULL || dz->dz_hash[h] == NULL)
			continue;
		if (dn_hash_dump_bucket(skb, cb, tb, dz, dz->dz_hash[h]) < 0) {
			cb->args[2] = h;
			return -1;
		}
	}
	cb->args[2] = h;
	return skb->len;
}

static int dn_fib_table_dump(struct dn_fib_table *tb, struct sk_buff *skb, 
                                struct netlink_callback *cb)
{
        int m, s_m;
	struct dn_zone *dz;
	struct dn_hash *table = (struct dn_hash *)tb->data;

	s_m = cb->args[1];
	read_lock(&dn_fib_tables_lock);
	for(dz = table->dh_zone_list, m = 0; dz; dz = dz->dz_next, m++) {
		if (m < s_m)
			continue;
		if (m > s_m)
			memset(&cb->args[2], 0, sizeof(cb->args) - 2*sizeof(cb->args[0]));

		if (dn_hash_dump_zone(skb, cb, tb, dz) < 0) {
			cb->args[1] = m;
			read_unlock(&dn_fib_tables_lock);
			return -1;
		}
	}
	read_unlock(&dn_fib_tables_lock);
	cb->args[1] = m;

        return skb->len;
}

static int dn_fib_table_insert(struct dn_fib_table *tb, struct rtmsg *r, struct dn_kern_rta *rta, struct nlmsghdr *n, struct netlink_skb_parms *req)
{
	struct dn_hash *table = (struct dn_hash *)tb->data;
	struct dn_fib_node *new_f, *f, **fp, **del_fp;
	struct dn_zone *dz;
	struct dn_fib_info *fi;
        int z = r->rtm_dst_len;
	int type = r->rtm_type;
	dn_fib_key_t key;
        int err;

        if (z > 16)
                return -EINVAL;

	dz = table->dh_zones[z];
	if (!dz && !(dz = dn_new_zone(table, z)))
		return -ENOBUFS;

	dz_key_0(key);
	if (rta->rta_dst) {
		__le16 dst;
		memcpy(&dst, rta->rta_dst, 2);
		if (dst & ~DZ_MASK(dz))
			return -EINVAL;
		key = dz_key(dst, dz);
	}

        if ((fi = dn_fib_create_info(r, rta, n, &err)) == NULL)
                return err;

	if (dz->dz_nent > (dz->dz_divisor << 2) &&
			dz->dz_divisor > DN_MAX_DIVISOR &&
			(z==16 || (1<<z) > dz->dz_divisor))
		dn_rehash_zone(dz);

	fp = dn_chain_p(key, dz);

	DN_FIB_SCAN(f, fp) {
		if (dn_key_leq(key, f->fn_key))
			break;
	}

	del_fp = NULL;

	if (f && (f->fn_state & DN_S_ZOMBIE) &&
			dn_key_eq(f->fn_key, key)) {
		del_fp = fp;
		fp = &f->fn_next;
		f = *fp;
		goto create;
	}

	DN_FIB_SCAN_KEY(f, fp, key) {
		if (fi->fib_priority <= DN_FIB_INFO(f)->fib_priority)
			break;
	}

	if (f && dn_key_eq(f->fn_key, key) &&
			fi->fib_priority == DN_FIB_INFO(f)->fib_priority) {
		struct dn_fib_node **ins_fp;

		err = -EEXIST;
		if (n->nlmsg_flags & NLM_F_EXCL)
			goto out;

		if (n->nlmsg_flags & NLM_F_REPLACE) {
			del_fp = fp;
			fp = &f->fn_next;
			f = *fp;
			goto replace;
		}

		ins_fp = fp;
		err = -EEXIST;

		DN_FIB_SCAN_KEY(f, fp, key) {
			if (fi->fib_priority != DN_FIB_INFO(f)->fib_priority)
				break;
			if (f->fn_type == type && f->fn_scope == r->rtm_scope
					&& DN_FIB_INFO(f) == fi)
				goto out;
		}

		if (!(n->nlmsg_flags & NLM_F_APPEND)) {
			fp = ins_fp;
			f = *fp;
		}
	}

create:
	err = -ENOENT;
	if (!(n->nlmsg_flags & NLM_F_CREATE))
		goto out;

replace:
	err = -ENOBUFS;
	new_f = kmem_cache_alloc(dn_hash_kmem, SLAB_KERNEL);
	if (new_f == NULL)
		goto out;

	memset(new_f, 0, sizeof(struct dn_fib_node));

	new_f->fn_key = key;
	new_f->fn_type = type;
	new_f->fn_scope = r->rtm_scope;
	DN_FIB_INFO(new_f) = fi;

	new_f->fn_next = f;
	write_lock_bh(&dn_fib_tables_lock);
	*fp = new_f;
	write_unlock_bh(&dn_fib_tables_lock);
	dz->dz_nent++;

	if (del_fp) {
		f = *del_fp;
		write_lock_bh(&dn_fib_tables_lock);
		*del_fp = f->fn_next;
		write_unlock_bh(&dn_fib_tables_lock);

		if (!(f->fn_state & DN_S_ZOMBIE))
			dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req);
		if (f->fn_state & DN_S_ACCESSED)
			dn_rt_cache_flush(-1);
		dn_free_node(f);
		dz->dz_nent--;
	} else {
		dn_rt_cache_flush(-1);
	}

        dn_rtmsg_fib(RTM_NEWROUTE, new_f, z, tb->n, n, req);

        return 0;
out:
	dn_fib_release_info(fi);
	return err;
}


static int dn_fib_table_delete(struct dn_fib_table *tb, struct rtmsg *r, struct dn_kern_rta *rta, struct nlmsghdr *n, struct netlink_skb_parms *req)
{
	struct dn_hash *table = (struct dn_hash*)tb->data;
	struct dn_fib_node **fp, **del_fp, *f;
        int z = r->rtm_dst_len;
	struct dn_zone *dz;
	dn_fib_key_t key;
	int matched;


        if (z > 16)
                return -EINVAL;

	if ((dz = table->dh_zones[z]) == NULL)
		return -ESRCH;

	dz_key_0(key);
	if (rta->rta_dst) {
		__le16 dst;
		memcpy(&dst, rta->rta_dst, 2);
		if (dst & ~DZ_MASK(dz))
			return -EINVAL;
		key = dz_key(dst, dz);
	}

	fp = dn_chain_p(key, dz);

	DN_FIB_SCAN(f, fp) {
		if (dn_key_eq(f->fn_key, key))
			break;
		if (dn_key_leq(key, f->fn_key))
			return -ESRCH;
	}

	matched = 0;
	del_fp = NULL;
	DN_FIB_SCAN_KEY(f, fp, key) {
		struct dn_fib_info *fi = DN_FIB_INFO(f);

		if (f->fn_state & DN_S_ZOMBIE)
			return -ESRCH;

		matched++;

		if (del_fp == NULL &&
				(!r->rtm_type || f->fn_type == r->rtm_type) &&
				(r->rtm_scope == RT_SCOPE_NOWHERE || f->fn_scope == r->rtm_scope) &&
				(!r->rtm_protocol || 
					fi->fib_protocol == r->rtm_protocol) &&
				dn_fib_nh_match(r, n, rta, fi) == 0)
			del_fp = fp;
	}

	if (del_fp) {
		f = *del_fp;
        	dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req);

		if (matched != 1) {
			write_lock_bh(&dn_fib_tables_lock);
			*del_fp = f->fn_next;
			write_unlock_bh(&dn_fib_tables_lock);

			if (f->fn_state & DN_S_ACCESSED)
				dn_rt_cache_flush(-1);
			dn_free_node(f);
			dz->dz_nent--;
		} else {
			f->fn_state |= DN_S_ZOMBIE;
			if (f->fn_state & DN_S_ACCESSED) {
				f->fn_state &= ~DN_S_ACCESSED;
				dn_rt_cache_flush(-1);
			}
			if (++dn_fib_hash_zombies > 128)
				dn_fib_flush();
		}

		return 0;
	}

        return -ESRCH;
}

static inline int dn_flush_list(struct dn_fib_node **fp, int z, struct dn_hash *table)
{
	int found = 0;
	struct dn_fib_node *f;

	while((f = *fp) != NULL) {
		struct dn_fib_info *fi = DN_FIB_INFO(f);

		if (fi && ((f->fn_state & DN_S_ZOMBIE) || (fi->fib_flags & RTNH_F_DEAD))) {
			write_lock_bh(&dn_fib_tables_lock);
			*fp = f->fn_next;
			write_unlock_bh(&dn_fib_tables_lock);

			dn_free_node(f);
			found++;
			continue;
		}
		fp = &f->fn_next;
	}

	return found;
}

static int dn_fib_table_flush(struct dn_fib_table *tb)
{
	struct dn_hash *table = (struct dn_hash *)tb->data;
	struct dn_zone *dz;
	int found = 0;

	dn_fib_hash_zombies = 0;
	for(dz = table->dh_zone_list; dz; dz = dz->dz_next) {
		int i;
		int tmp = 0;
		for(i = dz->dz_divisor-1; i >= 0; i--)
			tmp += dn_flush_list(&dz->dz_hash[i], dz->dz_order, table);
		dz->dz_nent -= tmp;
		found += tmp;
	}

	return found;
}

static int dn_fib_table_lookup(struct dn_fib_table *tb, const struct flowi *flp, struct dn_fib_res *res)
{
        int err;
	struct dn_zone *dz;
	struct dn_hash *t = (struct dn_hash *)tb->data;

	read_lock(&dn_fib_tables_lock);
	for(dz = t->dh_zone_list; dz; dz = dz->dz_next) {
		struct dn_fib_node *f;
		dn_fib_key_t k = dz_key(flp->fld_dst, dz);

		for(f = dz_chain(k, dz); f; f = f->fn_next) {
			if (!dn_key_eq(k, f->fn_key)) {
				if (dn_key_leq(k, f->fn_key))
					break;
				else
					continue;
			}

			f->fn_state |= DN_S_ACCESSED;

			if (f->fn_state&DN_S_ZOMBIE)
				continue;

			if (f->fn_scope < flp->fld_scope)
				continue;

			err = dn_fib_semantic_match(f->fn_type, DN_FIB_INFO(f), flp, res);

			if (err == 0) {
				res->type = f->fn_type;
				res->scope = f->fn_scope; 
				res->prefixlen = dz->dz_order;
				goto out;
			}
			if (err < 0)
				goto out;
		}
	}
	err = 1;
out:
	read_unlock(&dn_fib_tables_lock);
        return err;
}


struct dn_fib_table *dn_fib_get_table(u32 n, int create)
{
        struct dn_fib_table *t;

        if (n < RT_TABLE_MIN)
                return NULL;

        if (n > RT_TABLE_MAX)
                return NULL;

        if (dn_fib_tables[n]) 
                return dn_fib_tables[n];

        if (!create)
                return NULL;

        if (in_interrupt() && net_ratelimit()) {
                printk(KERN_DEBUG "DECnet: BUG! Attempt to create routing table from interrupt\n"); 
                return NULL;
        }
        if ((t = kmalloc(sizeof(struct dn_fib_table) + sizeof(struct dn_hash), GFP_KERNEL)) == NULL)
                return NULL;

        memset(t, 0, sizeof(struct dn_fib_table));

        t->n = n;
        t->insert = dn_fib_table_insert;
        t->delete = dn_fib_table_delete;
        t->lookup = dn_fib_table_lookup;
        t->flush  = dn_fib_table_flush;
        t->dump = dn_fib_table_dump;
	memset(t->data, 0, sizeof(struct dn_hash));
        dn_fib_tables[n] = t;

        return t;
}

static void dn_fib_del_tree(u32 n)
{
	struct dn_fib_table *t;

	write_lock(&dn_fib_tables_lock);
	t = dn_fib_tables[n];
	dn_fib_tables[n] = NULL;
	write_unlock(&dn_fib_tables_lock);

	kfree(t);
}

struct dn_fib_table *dn_fib_empty_table(void)
{
        u32 id;

        for(id = RT_TABLE_MIN; id <= RT_TABLE_MAX; id++)
                if (dn_fib_tables[id] == NULL)
                        return dn_fib_get_table(id, 1);
        return NULL;
}

void __init dn_fib_table_init(void)
{
	dn_hash_kmem = kmem_cache_create("dn_fib_info_cache",
					sizeof(struct dn_fib_info),
					0, SLAB_HWCACHE_ALIGN,
					NULL, NULL);
}

void __exit dn_fib_table_cleanup(void)
{
	int i;

	for (i = RT_TABLE_MIN; i <= RT_TABLE_MAX; ++i)
		dn_fib_del_tree(i);

	return;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* DECnet An implementation of the DECnet protocol suite for the LINUX
	3	* operating system. DECnet is implemented using the BSD Socket
	4	* interface as the means of communication with the user level.
	5	*
	6	* DECnet Routing Forwarding Information Base (Routing Tables)
	7	*
	8	* Author: Steve Whitehouse <SteveW@ACM.org>
	9	* Mostly copied from the IPv4 routing code
	10	*
	11	*
	12	* Changes:
	13	*
	14	*/
1da177e4 LT	15	#include <linux/string.h>
	16	#include <linux/net.h>
	17	#include <linux/socket.h>
	18	#include <linux/sockios.h>
	19	#include <linux/init.h>
	20	#include <linux/skbuff.h>
	21	#include <linux/netlink.h>
	22	#include <linux/rtnetlink.h>
	23	#include <linux/proc_fs.h>
	24	#include <linux/netdevice.h>
	25	#include <linux/timer.h>
	26	#include <linux/spinlock.h>
	27	#include <asm/atomic.h>
	28	#include <asm/uaccess.h>
	29	#include <linux/route.h> /* RTF_xxx */
	30	#include <net/neighbour.h>
	31	#include <net/dst.h>
	32	#include <net/flow.h>
a8731cbf	33	#include <net/fib_rules.h>
1da177e4 LT	34	#include <net/dn.h>
	35	#include <net/dn_route.h>
	36	#include <net/dn_fib.h>
	37	#include <net/dn_neigh.h>
	38	#include <net/dn_dev.h>
	39
	40	struct dn_zone
	41	{
	42	struct dn_zone *dz_next;
	43	struct dn_fib_node **dz_hash;
	44	int dz_nent;
	45	int dz_divisor;
	46	u32 dz_hashmask;
	47	#define DZ_HASHMASK(dz) ((dz)->dz_hashmask)
	48	int dz_order;
c4ea94ab	49	__le16 dz_mask;
1da177e4 LT	50	#define DZ_MASK(dz) ((dz)->dz_mask)
	51	};
	52
	53	struct dn_hash
	54	{
	55	struct dn_zone *dh_zones[17];
	56	struct dn_zone *dh_zone_list;
	57	};
	58
	59	#define dz_key_0(key) ((key).datum = 0)
	60	#define dz_prefix(key,dz) ((key).datum)
	61
	62	#define for_nexthops(fi) { int nhsel; const struct dn_fib_nh *nh;\
	63	for(nhsel = 0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++)
	64
	65	#define endfor_nexthops(fi) }
	66
	67	#define DN_MAX_DIVISOR 1024
	68	#define DN_S_ZOMBIE 1
	69	#define DN_S_ACCESSED 2
	70
	71	#define DN_FIB_SCAN(f, fp) \
	72	for( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next)
	73
	74	#define DN_FIB_SCAN_KEY(f, fp, key) \
	75	for( ; ((f) = *(fp)) != NULL && dn_key_eq((f)->fn_key, (key)); (fp) = &(f)->fn_next)
	76
	77	#define RT_TABLE_MIN 1
	78
	79	static DEFINE_RWLOCK(dn_fib_tables_lock);
	80	struct dn_fib_table *dn_fib_tables[RT_TABLE_MAX + 1];
	81
ba89966c	82	static kmem_cache_t *dn_hash_kmem __read_mostly;
1da177e4 LT	83	static int dn_fib_hash_zombies;
	84
	85	static inline dn_fib_idx_t dn_hash(dn_fib_key_t key, struct dn_zone *dz)
	86	{
c4ea94ab	87	u16 h = dn_ntohs(key.datum)>>(16 - dz->dz_order);
1da177e4 LT	88	h ^= (h >> 10);
	89	h ^= (h >> 6);
	90	h &= DZ_HASHMASK(dz);
	91	return (dn_fib_idx_t )&h;
	92	}
	93
c4ea94ab	94	static inline dn_fib_key_t dz_key(__le16 dst, struct dn_zone *dz)
1da177e4 LT	95	{
	96	dn_fib_key_t k;
	97	k.datum = dst & DZ_MASK(dz);
	98	return k;
	99	}
	100
	101	static inline struct dn_fib_node *dn_chain_p(dn_fib_key_t key, struct dn_zone dz)
	102	{
	103	return &dz->dz_hash[dn_hash(key, dz).datum];
	104	}
	105
	106	static inline struct dn_fib_node dz_chain(dn_fib_key_t key, struct dn_zone dz)
	107	{
	108	return dz->dz_hash[dn_hash(key, dz).datum];
	109	}
	110
	111	static inline int dn_key_eq(dn_fib_key_t a, dn_fib_key_t b)
	112	{
	113	return a.datum == b.datum;
	114	}
	115
	116	static inline int dn_key_leq(dn_fib_key_t a, dn_fib_key_t b)
	117	{
	118	return a.datum <= b.datum;
	119	}
	120
	121	static inline void dn_rebuild_zone(struct dn_zone *dz,
	122	struct dn_fib_node **old_ht,
	123	int old_divisor)
	124	{
	125	int i;
	126	struct dn_fib_node f, fp, next;
	127
	128	for(i = 0; i < old_divisor; i++) {
	129	for(f = old_ht[i]; f; f = f->fn_next) {
	130	next = f->fn_next;
	131	for(fp = dn_chain_p(f->fn_key, dz);
	132	fp && dn_key_leq((fp)->fn_key, f->fn_key);
	133	fp = &(*fp)->fn_next)
	134	/* NOTHING */;
	135	f->fn_next = *fp;
	136	*fp = f;
	137	}
	138	}
	139	}
	140
	141	static void dn_rehash_zone(struct dn_zone *dz)
	142	{
	143	struct dn_fib_node ht, old_ht;
	144	int old_divisor, new_divisor;
	145	u32 new_hashmask;
	146
	147	old_divisor = dz->dz_divisor;
	148
	149	switch(old_divisor) {
	150	case 16:
	151	new_divisor = 256;
	152	new_hashmask = 0xFF;
	153	break;
	154	default:
	155	printk(KERN_DEBUG "DECnet: dn_rehash_zone: BUG! %d\n", old_divisor);
	156	case 256:
	157	new_divisor = 1024;
	158	new_hashmask = 0x3FF;
159	break;
160	}
161
0da974f4	162	ht = kcalloc(new_divisor, sizeof(struct dn_fib_node*), GFP_KERNEL);
1da177e4 LT	163	if (ht == NULL)
	164	return;
	165
1da177e4 LT	166	write_lock_bh(&dn_fib_tables_lock);
	167	old_ht = dz->dz_hash;
	168	dz->dz_hash = ht;
	169	dz->dz_hashmask = new_hashmask;
	170	dz->dz_divisor = new_divisor;
	171	dn_rebuild_zone(dz, old_ht, old_divisor);
	172	write_unlock_bh(&dn_fib_tables_lock);
	173	kfree(old_ht);
	174	}
	175
	176	static void dn_free_node(struct dn_fib_node *f)
	177	{
	178	dn_fib_release_info(DN_FIB_INFO(f));
	179	kmem_cache_free(dn_hash_kmem, f);
	180	}
	181
	182
	183	static struct dn_zone dn_new_zone(struct dn_hash table, int z)
	184	{
	185	int i;
0da974f4	186	struct dn_zone *dz = kzalloc(sizeof(struct dn_zone), GFP_KERNEL);
1da177e4 LT	187	if (!dz)
	188	return NULL;
	189
1da177e4 LT	190	if (z) {
	191	dz->dz_divisor = 16;
	192	dz->dz_hashmask = 0x0F;
	193	} else {
	194	dz->dz_divisor = 1;
	195	dz->dz_hashmask = 0;
	196	}
	197
0da974f4	198	dz->dz_hash = kcalloc(dz->dz_divisor, sizeof(struct dn_fib_node *), GFP_KERNEL);
1da177e4 LT	199	if (!dz->dz_hash) {
	200	kfree(dz);
	201	return NULL;
	202	}
	203
1da177e4 LT	204	dz->dz_order = z;
	205	dz->dz_mask = dnet_make_mask(z);
	206
	207	for(i = z + 1; i <= 16; i++)
	208	if (table->dh_zones[i])
	209	break;
	210
	211	write_lock_bh(&dn_fib_tables_lock);
	212	if (i>16) {
	213	dz->dz_next = table->dh_zone_list;
	214	table->dh_zone_list = dz;
	215	} else {
	216	dz->dz_next = table->dh_zones[i]->dz_next;
	217	table->dh_zones[i]->dz_next = dz;
	218	}
	219	table->dh_zones[z] = dz;
	220	write_unlock_bh(&dn_fib_tables_lock);
	221	return dz;
	222	}
	223
	224
	225	static int dn_fib_nh_match(struct rtmsg r, struct nlmsghdr nlh, struct dn_kern_rta rta, struct dn_fib_info fi)
	226	{
	227	struct rtnexthop *nhp;
	228	int nhlen;
	229
	230	if (rta->rta_priority && *rta->rta_priority != fi->fib_priority)
	231	return 1;
	232
	233	if (rta->rta_oif \|\| rta->rta_gw) {
	234	if ((!rta->rta_oif \|\| *rta->rta_oif == fi->fib_nh->nh_oif) &&
	235	(!rta->rta_gw \|\| memcmp(rta->rta_gw, &fi->fib_nh->nh_gw, 2) == 0))
	236	return 0;
	237	return 1;
	238	}
	239
	240	if (rta->rta_mp == NULL)
	241	return 0;
	242
	243	nhp = RTA_DATA(rta->rta_mp);
	244	nhlen = RTA_PAYLOAD(rta->rta_mp);
	245
	246	for_nexthops(fi) {
	247	int attrlen = nhlen - sizeof(struct rtnexthop);
c4ea94ab	248	__le16 gw;
1da177e4 LT	249
	250	if (attrlen < 0 \|\| (nhlen -= nhp->rtnh_len) < 0)
	251	return -EINVAL;
	252	if (nhp->rtnh_ifindex && nhp->rtnh_ifindex != nh->nh_oif)
	253	return 1;
	254	if (attrlen) {
	255	gw = dn_fib_get_attr16(RTNH_DATA(nhp), attrlen, RTA_GATEWAY);
	256
	257	if (gw && gw != nh->nh_gw)
	258	return 1;
	259	}
	260	nhp = RTNH_NEXT(nhp);
	261	} endfor_nexthops(fi);
	262
	263	return 0;
	264	}
	265
	266	static int dn_fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
2dfe55b4	267	u32 tb_id, u8 type, u8 scope, void *dst, int dst_len,
b6544c0b	268	struct dn_fib_info *fi, unsigned int flags)
1da177e4 LT	269	{
	270	struct rtmsg *rtm;
	271	struct nlmsghdr *nlh;
	272	unsigned char *b = skb->tail;
	273
b6544c0b	274	nlh = NLMSG_NEW(skb, pid, seq, event, sizeof(*rtm), flags);
1da177e4 LT	275	rtm = NLMSG_DATA(nlh);
	276	rtm->rtm_family = AF_DECnet;
	277	rtm->rtm_dst_len = dst_len;
	278	rtm->rtm_src_len = 0;
	279	rtm->rtm_tos = 0;
	280	rtm->rtm_table = tb_id;
9e762a4a	281	RTA_PUT_U32(skb, RTA_TABLE, tb_id);
1da177e4 LT	282	rtm->rtm_flags = fi->fib_flags;
	283	rtm->rtm_scope = scope;
	284	rtm->rtm_type = type;
	285	if (rtm->rtm_dst_len)
	286	RTA_PUT(skb, RTA_DST, 2, dst);
	287	rtm->rtm_protocol = fi->fib_protocol;
	288	if (fi->fib_priority)
	289	RTA_PUT(skb, RTA_PRIORITY, 4, &fi->fib_priority);
	290	if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0)
	291	goto rtattr_failure;
	292	if (fi->fib_nhs == 1) {
	293	if (fi->fib_nh->nh_gw)
	294	RTA_PUT(skb, RTA_GATEWAY, 2, &fi->fib_nh->nh_gw);
	295	if (fi->fib_nh->nh_oif)
	296	RTA_PUT(skb, RTA_OIF, sizeof(int), &fi->fib_nh->nh_oif);
	297	}
	298	if (fi->fib_nhs > 1) {
	299	struct rtnexthop *nhp;
	300	struct rtattr *mp_head;
	301	if (skb_tailroom(skb) <= RTA_SPACE(0))
	302	goto rtattr_failure;
	303	mp_head = (struct rtattr *)skb_put(skb, RTA_SPACE(0));
	304
	305	for_nexthops(fi) {
	306	if (skb_tailroom(skb) < RTA_ALIGN(RTA_ALIGN(sizeof(*nhp)) + 4))
	307	goto rtattr_failure;
	308	nhp = (struct rtnexthop )skb_put(skb, RTA_ALIGN(sizeof(nhp)));
	309	nhp->rtnh_flags = nh->nh_flags & 0xFF;
	310	nhp->rtnh_hops = nh->nh_weight - 1;
	311	nhp->rtnh_ifindex = nh->nh_oif;
	312	if (nh->nh_gw)
	313	RTA_PUT(skb, RTA_GATEWAY, 2, &nh->nh_gw);
	314	nhp->rtnh_len = skb->tail - (unsigned char *)nhp;
	315	} endfor_nexthops(fi);
	316	mp_head->rta_type = RTA_MULTIPATH;
	317	mp_head->rta_len = skb->tail - (u8*)mp_head;
	318	}
	319
	320	nlh->nlmsg_len = skb->tail - b;
	321	return skb->len;
	322
	323
	324	nlmsg_failure:
	325	rtattr_failure:
	326	skb_trim(skb, b - skb->data);
	327	return -1;
	328	}
	329
	330
2dfe55b4	331	static void dn_rtmsg_fib(int event, struct dn_fib_node *f, int z, u32 tb_id,
1da177e4 LT	332	struct nlmsghdr nlh, struct netlink_skb_parms req)
	333	{
	334	struct sk_buff *skb;
	335	u32 pid = req ? req->pid : 0;
	336	int size = NLMSG_SPACE(sizeof(struct rtmsg) + 256);
	337
	338	skb = alloc_skb(size, GFP_KERNEL);
	339	if (!skb)
	340	return;
	341
	342	if (dn_fib_dump_info(skb, pid, nlh->nlmsg_seq, event, tb_id,
	343	f->fn_type, f->fn_scope, &f->fn_key, z,
b6544c0b	344	DN_FIB_INFO(f), 0) < 0) {
1da177e4 LT	345	kfree_skb(skb);
	346	return;
	347	}
ac6d439d	348	NETLINK_CB(skb).dst_group = RTNLGRP_DECnet_ROUTE;
1da177e4 LT	349	if (nlh->nlmsg_flags & NLM_F_ECHO)
1da177e4 LT	350	atomic_inc(&skb->users);
ac6d439d	351	netlink_broadcast(rtnl, skb, pid, RTNLGRP_DECnet_ROUTE, GFP_KERNEL);
1da177e4 LT	352	if (nlh->nlmsg_flags & NLM_F_ECHO)
	353	netlink_unicast(rtnl, skb, pid, MSG_DONTWAIT);
	354	}
	355
	356	static __inline__ int dn_hash_dump_bucket(struct sk_buff *skb,
	357	struct netlink_callback *cb,
	358	struct dn_fib_table *tb,
	359	struct dn_zone *dz,
	360	struct dn_fib_node *f)
	361	{
	362	int i, s_i;
	363
	364	s_i = cb->args[3];
	365	for(i = 0; f; i++, f = f->fn_next) {
	366	if (i < s_i)
	367	continue;
	368	if (f->fn_state & DN_S_ZOMBIE)
	369	continue;
	370	if (dn_fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
	371	cb->nlh->nlmsg_seq,
	372	RTM_NEWROUTE,
	373	tb->n,
	374	(f->fn_state & DN_S_ZOMBIE) ? 0 : f->fn_type,
	375	f->fn_scope, &f->fn_key, dz->dz_order,
b6544c0b	376	f->fn_info, NLM_F_MULTI) < 0) {
1da177e4 LT	377	cb->args[3] = i;
	378	return -1;
	379	}
	380	}
	381	cb->args[3] = i;
	382	return skb->len;
	383	}
	384
	385	static __inline__ int dn_hash_dump_zone(struct sk_buff *skb,
	386	struct netlink_callback *cb,
	387	struct dn_fib_table *tb,
	388	struct dn_zone *dz)
	389	{
	390	int h, s_h;
	391
	392	s_h = cb->args[2];
	393	for(h = 0; h < dz->dz_divisor; h++) {
	394	if (h < s_h)
	395	continue;
	396	if (h > s_h)
	397	memset(&cb->args[3], 0, sizeof(cb->args) - 3*sizeof(cb->args[0]));
	398	if (dz->dz_hash == NULL \|\| dz->dz_hash[h] == NULL)
	399	continue;
	400	if (dn_hash_dump_bucket(skb, cb, tb, dz, dz->dz_hash[h]) < 0) {
	401	cb->args[2] = h;
	402	return -1;
	403	}
	404	}
	405	cb->args[2] = h;
	406	return skb->len;
	407	}
	408
	409	static int dn_fib_table_dump(struct dn_fib_table tb, struct sk_buff skb,
	410	struct netlink_callback *cb)
	411	{
	412	int m, s_m;
	413	struct dn_zone *dz;
	414	struct dn_hash table = (struct dn_hash )tb->data;
	415
	416	s_m = cb->args[1];
	417	read_lock(&dn_fib_tables_lock);
	418	for(dz = table->dh_zone_list, m = 0; dz; dz = dz->dz_next, m++) {
	419	if (m < s_m)
	420	continue;
	421	if (m > s_m)
	422	memset(&cb->args[2], 0, sizeof(cb->args) - 2*sizeof(cb->args[0]));
	423
	424	if (dn_hash_dump_zone(skb, cb, tb, dz) < 0) {
	425	cb->args[1] = m;
	426	read_unlock(&dn_fib_tables_lock);
	427	return -1;
	428	}
	429	}
	430	read_unlock(&dn_fib_tables_lock);
	431	cb->args[1] = m;
	432
	433	return skb->len;
	434	}
	435
	436	static int dn_fib_table_insert(struct dn_fib_table tb, struct rtmsg r, struct dn_kern_rta rta, struct nlmsghdr n, struct netlink_skb_parms *req)
	437	{
	438	struct dn_hash table = (struct dn_hash )tb->data;
	439	struct dn_fib_node new_f, f, fp, del_fp;
	440	struct dn_zone *dz;
441	struct dn_fib_info *fi;
442	int z = r->rtm_dst_len;
443	int type = r->rtm_type;
444	dn_fib_key_t key;
445	int err;
446
447	if (z > 16)
448	return -EINVAL;
449
450	dz = table->dh_zones[z];
451	if (!dz && !(dz = dn_new_zone(table, z)))
452	return -ENOBUFS;
453
454	dz_key_0(key);
455	if (rta->rta_dst) {
c4ea94ab	456	__le16 dst;
1da177e4 LT	457	memcpy(&dst, rta->rta_dst, 2);
	458	if (dst & ~DZ_MASK(dz))
	459	return -EINVAL;
	460	key = dz_key(dst, dz);
	461	}
	462
	463	if ((fi = dn_fib_create_info(r, rta, n, &err)) == NULL)
	464	return err;
	465
	466	if (dz->dz_nent > (dz->dz_divisor << 2) &&
	467	dz->dz_divisor > DN_MAX_DIVISOR &&
	468	(z==16 \|\| (1<<z) > dz->dz_divisor))
	469	dn_rehash_zone(dz);
	470
	471	fp = dn_chain_p(key, dz);
	472
	473	DN_FIB_SCAN(f, fp) {
	474	if (dn_key_leq(key, f->fn_key))
	475	break;
	476	}
	477
	478	del_fp = NULL;
	479
	480	if (f && (f->fn_state & DN_S_ZOMBIE) &&
	481	dn_key_eq(f->fn_key, key)) {
	482	del_fp = fp;
	483	fp = &f->fn_next;
	484	f = *fp;
	485	goto create;
	486	}
	487
	488	DN_FIB_SCAN_KEY(f, fp, key) {
	489	if (fi->fib_priority <= DN_FIB_INFO(f)->fib_priority)
	490	break;
	491	}
	492
	493	if (f && dn_key_eq(f->fn_key, key) &&
	494	fi->fib_priority == DN_FIB_INFO(f)->fib_priority) {
	495	struct dn_fib_node **ins_fp;
	496
	497	err = -EEXIST;
	498	if (n->nlmsg_flags & NLM_F_EXCL)
	499	goto out;
	500
	501	if (n->nlmsg_flags & NLM_F_REPLACE) {
	502	del_fp = fp;
	503	fp = &f->fn_next;
	504	f = *fp;
	505	goto replace;
	506	}
	507
	508	ins_fp = fp;
	509	err = -EEXIST;
	510
	511	DN_FIB_SCAN_KEY(f, fp, key) {
	512	if (fi->fib_priority != DN_FIB_INFO(f)->fib_priority)
	513	break;
	514	if (f->fn_type == type && f->fn_scope == r->rtm_scope
	515	&& DN_FIB_INFO(f) == fi)
	516	goto out;
	517	}
	518
	519	if (!(n->nlmsg_flags & NLM_F_APPEND)) {
	520	fp = ins_fp;
521	f = *fp;
522	}
523	}
524
525	create:
526	err = -ENOENT;
527	if (!(n->nlmsg_flags & NLM_F_CREATE))
528	goto out;
529
530	replace:
531	err = -ENOBUFS;
532	new_f = kmem_cache_alloc(dn_hash_kmem, SLAB_KERNEL);
533	if (new_f == NULL)
534	goto out;
535
536	memset(new_f, 0, sizeof(struct dn_fib_node));
537
538	new_f->fn_key = key;
539	new_f->fn_type = type;
540	new_f->fn_scope = r->rtm_scope;
541	DN_FIB_INFO(new_f) = fi;
542
543	new_f->fn_next = f;
544	write_lock_bh(&dn_fib_tables_lock);
545	*fp = new_f;
546	write_unlock_bh(&dn_fib_tables_lock);
547	dz->dz_nent++;
548
549	if (del_fp) {
550	f = *del_fp;
551	write_lock_bh(&dn_fib_tables_lock);
552	*del_fp = f->fn_next;
553	write_unlock_bh(&dn_fib_tables_lock);
554
555	if (!(f->fn_state & DN_S_ZOMBIE))
556	dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req);
557	if (f->fn_state & DN_S_ACCESSED)
558	dn_rt_cache_flush(-1);
559	dn_free_node(f);
560	dz->dz_nent--;
561	} else {
562	dn_rt_cache_flush(-1);
563	}
564
565	dn_rtmsg_fib(RTM_NEWROUTE, new_f, z, tb->n, n, req);
566
567	return 0;
568	out:
569	dn_fib_release_info(fi);
570	return err;
571	}
572
573
574	static int dn_fib_table_delete(struct dn_fib_table tb, struct rtmsg r, struct dn_kern_rta rta, struct nlmsghdr n, struct netlink_skb_parms *req)
575	{
576	struct dn_hash table = (struct dn_hash)tb->data;
577	struct dn_fib_node fp, del_fp, *f;
578	int z = r->rtm_dst_len;
579	struct dn_zone *dz;
580	dn_fib_key_t key;
581	int matched;
582
583
584	if (z > 16)
585	return -EINVAL;
586
587	if ((dz = table->dh_zones[z]) == NULL)
588	return -ESRCH;
589
590	dz_key_0(key);
591	if (rta->rta_dst) {
c4ea94ab	592	__le16 dst;
1da177e4 LT	593	memcpy(&dst, rta->rta_dst, 2);
	594	if (dst & ~DZ_MASK(dz))
	595	return -EINVAL;
	596	key = dz_key(dst, dz);
	597	}
	598
	599	fp = dn_chain_p(key, dz);
	600
	601	DN_FIB_SCAN(f, fp) {
	602	if (dn_key_eq(f->fn_key, key))
	603	break;
	604	if (dn_key_leq(key, f->fn_key))
	605	return -ESRCH;
	606	}
	607
	608	matched = 0;
	609	del_fp = NULL;
	610	DN_FIB_SCAN_KEY(f, fp, key) {
	611	struct dn_fib_info *fi = DN_FIB_INFO(f);
	612
	613	if (f->fn_state & DN_S_ZOMBIE)
	614	return -ESRCH;
	615
	616	matched++;
	617
	618	if (del_fp == NULL &&
	619	(!r->rtm_type \|\| f->fn_type == r->rtm_type) &&
	620	(r->rtm_scope == RT_SCOPE_NOWHERE \|\| f->fn_scope == r->rtm_scope) &&
	621	(!r->rtm_protocol \|\|
	622	fi->fib_protocol == r->rtm_protocol) &&
	623	dn_fib_nh_match(r, n, rta, fi) == 0)
	624	del_fp = fp;
	625	}
	626
	627	if (del_fp) {
	628	f = *del_fp;
	629	dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req);
	630
	631	if (matched != 1) {
	632	write_lock_bh(&dn_fib_tables_lock);
	633	*del_fp = f->fn_next;
	634	write_unlock_bh(&dn_fib_tables_lock);
	635
	636	if (f->fn_state & DN_S_ACCESSED)
	637	dn_rt_cache_flush(-1);
	638	dn_free_node(f);
	639	dz->dz_nent--;
	640	} else {
	641	f->fn_state \|= DN_S_ZOMBIE;
	642	if (f->fn_state & DN_S_ACCESSED) {
	643	f->fn_state &= ~DN_S_ACCESSED;
	644	dn_rt_cache_flush(-1);
	645	}
	646	if (++dn_fib_hash_zombies > 128)
	647	dn_fib_flush();
	648	}
	649
	650	return 0;
	651	}
	652
	653	return -ESRCH;
	654	}
	655
	656	static inline int dn_flush_list(struct dn_fib_node *fp, int z, struct dn_hash table)
657	{
658	int found = 0;
659	struct dn_fib_node *f;
660
661	while((f = *fp) != NULL) {
662	struct dn_fib_info *fi = DN_FIB_INFO(f);
663
664	if (fi && ((f->fn_state & DN_S_ZOMBIE) \|\| (fi->fib_flags & RTNH_F_DEAD))) {
665	write_lock_bh(&dn_fib_tables_lock);
666	*fp = f->fn_next;
667	write_unlock_bh(&dn_fib_tables_lock);
668
669	dn_free_node(f);
670	found++;
671	continue;
672	}
673	fp = &f->fn_next;
674	}
675
676	return found;
677	}
678
679	static int dn_fib_table_flush(struct dn_fib_table *tb)
680	{
681	struct dn_hash table = (struct dn_hash )tb->data;
682	struct dn_zone *dz;
683	int found = 0;
684
685	dn_fib_hash_zombies = 0;
686	for(dz = table->dh_zone_list; dz; dz = dz->dz_next) {
687	int i;
688	int tmp = 0;
689	for(i = dz->dz_divisor-1; i >= 0; i--)
690	tmp += dn_flush_list(&dz->dz_hash[i], dz->dz_order, table);
691	dz->dz_nent -= tmp;
692	found += tmp;
693	}
694
695	return found;
696	}
697
698	static int dn_fib_table_lookup(struct dn_fib_table tb, const struct flowi flp, struct dn_fib_res *res)
699	{
700	int err;
701	struct dn_zone *dz;
702	struct dn_hash t = (struct dn_hash )tb->data;
703
704	read_lock(&dn_fib_tables_lock);
705	for(dz = t->dh_zone_list; dz; dz = dz->dz_next) {
706	struct dn_fib_node *f;
707	dn_fib_key_t k = dz_key(flp->fld_dst, dz);
708
709	for(f = dz_chain(k, dz); f; f = f->fn_next) {
710	if (!dn_key_eq(k, f->fn_key)) {
711	if (dn_key_leq(k, f->fn_key))
712	break;
713	else
714	continue;
715	}
716
717	f->fn_state \|= DN_S_ACCESSED;
718
719	if (f->fn_state&DN_S_ZOMBIE)
720	continue;
721
722	if (f->fn_scope < flp->fld_scope)
723	continue;
724
725	err = dn_fib_semantic_match(f->fn_type, DN_FIB_INFO(f), flp, res);
726
727	if (err == 0) {
728	res->type = f->fn_type;
729	res->scope = f->fn_scope;
730	res->prefixlen = dz->dz_order;
731	goto out;
732	}
733	if (err < 0)
734	goto out;
735	}
736	}
737	err = 1;
738	out:
739	read_unlock(&dn_fib_tables_lock);
740	return err;
741	}
742
743
2dfe55b4	744	struct dn_fib_table *dn_fib_get_table(u32 n, int create)
1da177e4 LT	745	{
	746	struct dn_fib_table *t;
	747
	748	if (n < RT_TABLE_MIN)
	749	return NULL;
	750
	751	if (n > RT_TABLE_MAX)
	752	return NULL;
	753
	754	if (dn_fib_tables[n])
	755	return dn_fib_tables[n];
	756
	757	if (!create)
	758	return NULL;
	759
	760	if (in_interrupt() && net_ratelimit()) {
	761	printk(KERN_DEBUG "DECnet: BUG! Attempt to create routing table from interrupt\n");
	762	return NULL;
	763	}
	764	if ((t = kmalloc(sizeof(struct dn_fib_table) + sizeof(struct dn_hash), GFP_KERNEL)) == NULL)
	765	return NULL;
	766
	767	memset(t, 0, sizeof(struct dn_fib_table));
	768
	769	t->n = n;
	770	t->insert = dn_fib_table_insert;
	771	t->delete = dn_fib_table_delete;
	772	t->lookup = dn_fib_table_lookup;
	773	t->flush = dn_fib_table_flush;
	774	t->dump = dn_fib_table_dump;
	775	memset(t->data, 0, sizeof(struct dn_hash));
	776	dn_fib_tables[n] = t;
	777
	778	return t;
	779	}
	780
2dfe55b4	781	static void dn_fib_del_tree(u32 n)
1da177e4	782	{
a51482bd	783	struct dn_fib_table *t;
1da177e4	784
a51482bd JJ	785	write_lock(&dn_fib_tables_lock);
	786	t = dn_fib_tables[n];
	787	dn_fib_tables[n] = NULL;
	788	write_unlock(&dn_fib_tables_lock);
1da177e4	789
a51482bd	790	kfree(t);
1da177e4 LT	791	}
	792
	793	struct dn_fib_table *dn_fib_empty_table(void)
	794	{
2dfe55b4	795	u32 id;
1da177e4 LT	796
	797	for(id = RT_TABLE_MIN; id <= RT_TABLE_MAX; id++)
	798	if (dn_fib_tables[id] == NULL)
	799	return dn_fib_get_table(id, 1);
	800	return NULL;
	801	}
	802
	803	void __init dn_fib_table_init(void)
	804	{
	805	dn_hash_kmem = kmem_cache_create("dn_fib_info_cache",
	806	sizeof(struct dn_fib_info),
	807	0, SLAB_HWCACHE_ALIGN,
	808	NULL, NULL);
	809	}
	810
	811	void __exit dn_fib_table_cleanup(void)
	812	{
	813	int i;
	814
	815	for (i = RT_TABLE_MIN; i <= RT_TABLE_MAX; ++i)
	816	dn_fib_del_tree(i);
	817
	818	return;
	819	}