[linux-2.6-block.git] / net / sched / cls_rsvp.h

/*
 * net/sched/cls_rsvp.h	Template file for RSVPv[46] classifiers.
 *
 *		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.
 *
 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 */

/*
   Comparing to general packet classification problem,
   RSVP needs only sevaral relatively simple rules:

   * (dst, protocol) are always specified,
     so that we are able to hash them.
   * src may be exact, or may be wildcard, so that
     we can keep a hash table plus one wildcard entry.
   * source port (or flow label) is important only if src is given.

   IMPLEMENTATION.

   We use a two level hash table: The top level is keyed by
   destination address and protocol ID, every bucket contains a list
   of "rsvp sessions", identified by destination address, protocol and
   DPI(="Destination Port ID"): triple (key, mask, offset).

   Every bucket has a smaller hash table keyed by source address
   (cf. RSVP flowspec) and one wildcard entry for wildcard reservations.
   Every bucket is again a list of "RSVP flows", selected by
   source address and SPI(="Source Port ID" here rather than
   "security parameter index"): triple (key, mask, offset).


   NOTE 1. All the packets with IPv6 extension headers (but AH and ESP)
   and all fragmented packets go to the best-effort traffic class.


   NOTE 2. Two "port id"'s seems to be redundant, rfc2207 requires
   only one "Generalized Port Identifier". So that for classic
   ah, esp (and udp,tcp) both *pi should coincide or one of them
   should be wildcard.

   At first sight, this redundancy is just a waste of CPU
   resources. But DPI and SPI add the possibility to assign different
   priorities to GPIs. Look also at note 4 about tunnels below.


   NOTE 3. One complication is the case of tunneled packets.
   We implement it as following: if the first lookup
   matches a special session with "tunnelhdr" value not zero,
   flowid doesn't contain the true flow ID, but the tunnel ID (1...255).
   In this case, we pull tunnelhdr bytes and restart lookup
   with tunnel ID added to the list of keys. Simple and stupid 8)8)
   It's enough for PIMREG and IPIP.


   NOTE 4. Two GPIs make it possible to parse even GRE packets.
   F.e. DPI can select ETH_P_IP (and necessary flags to make
   tunnelhdr correct) in GRE protocol field and SPI matches
   GRE key. Is it not nice? 8)8)


   Well, as result, despite its simplicity, we get a pretty
   powerful classification engine.  */


struct rsvp_head
{
	u32			tmap[256/32];
	u32			hgenerator;
	u8			tgenerator;
	struct rsvp_session	*ht[256];
};

struct rsvp_session
{
	struct rsvp_session	*next;
	__be32			dst[RSVP_DST_LEN];
	struct tc_rsvp_gpi 	dpi;
	u8			protocol;
	u8			tunnelid;
	/* 16 (src,sport) hash slots, and one wildcard source slot */
	struct rsvp_filter	*ht[16+1];
};


struct rsvp_filter
{
	struct rsvp_filter	*next;
	__be32			src[RSVP_DST_LEN];
	struct tc_rsvp_gpi	spi;
	u8			tunnelhdr;

	struct tcf_result	res;
	struct tcf_exts		exts;

	u32			handle;
	struct rsvp_session	*sess;
};

static __inline__ unsigned hash_dst(__be32 *dst, u8 protocol, u8 tunnelid)
{
	unsigned h = (__force __u32)dst[RSVP_DST_LEN-1];
	h ^= h>>16;
	h ^= h>>8;
	return (h ^ protocol ^ tunnelid) & 0xFF;
}

static __inline__ unsigned hash_src(__be32 *src)
{
	unsigned h = (__force __u32)src[RSVP_DST_LEN-1];
	h ^= h>>16;
	h ^= h>>8;
	h ^= h>>4;
	return h & 0xF;
}

static struct tcf_ext_map rsvp_ext_map = {
	.police = TCA_RSVP_POLICE,
	.action = TCA_RSVP_ACT
};

#define RSVP_APPLY_RESULT()				\
{							\
	int r = tcf_exts_exec(skb, &f->exts, res);	\
	if (r < 0)					\
		continue;				\
	else if (r > 0)					\
		return r;				\
}

static int rsvp_classify(struct sk_buff *skb, struct tcf_proto *tp,
			 struct tcf_result *res)
{
	struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
	struct rsvp_session *s;
	struct rsvp_filter *f;
	unsigned h1, h2;
	__be32 *dst, *src;
	u8 protocol;
	u8 tunnelid = 0;
	u8 *xprt;
#if RSVP_DST_LEN == 4
	struct ipv6hdr *nhptr = ipv6_hdr(skb);
#else
	struct iphdr *nhptr = ip_hdr(skb);
#endif

restart:

#if RSVP_DST_LEN == 4
	src = &nhptr->saddr.s6_addr32[0];
	dst = &nhptr->daddr.s6_addr32[0];
	protocol = nhptr->nexthdr;
	xprt = ((u8*)nhptr) + sizeof(struct ipv6hdr);
#else
	src = &nhptr->saddr;
	dst = &nhptr->daddr;
	protocol = nhptr->protocol;
	xprt = ((u8*)nhptr) + (nhptr->ihl<<2);
	if (nhptr->frag_off & htons(IP_MF|IP_OFFSET))
		return -1;
#endif

	h1 = hash_dst(dst, protocol, tunnelid);
	h2 = hash_src(src);

	for (s = sht[h1]; s; s = s->next) {
		if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
		    protocol == s->protocol &&
		    !(s->dpi.mask & (*(u32*)(xprt+s->dpi.offset)^s->dpi.key))
#if RSVP_DST_LEN == 4
		    && dst[0] == s->dst[0]
		    && dst[1] == s->dst[1]
		    && dst[2] == s->dst[2]
#endif
		    && tunnelid == s->tunnelid) {

			for (f = s->ht[h2]; f; f = f->next) {
				if (src[RSVP_DST_LEN-1] == f->src[RSVP_DST_LEN-1] &&
				    !(f->spi.mask & (*(u32*)(xprt+f->spi.offset)^f->spi.key))
#if RSVP_DST_LEN == 4
				    && src[0] == f->src[0]
				    && src[1] == f->src[1]
				    && src[2] == f->src[2]
#endif
				    ) {
					*res = f->res;
					RSVP_APPLY_RESULT();

matched:
					if (f->tunnelhdr == 0)
						return 0;

					tunnelid = f->res.classid;
					nhptr = (void*)(xprt + f->tunnelhdr - sizeof(*nhptr));
					goto restart;
				}
			}

			/* And wildcard bucket... */
			for (f = s->ht[16]; f; f = f->next) {
				*res = f->res;
				RSVP_APPLY_RESULT();
				goto matched;
			}
			return -1;
		}
	}
	return -1;
}

static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
{
	struct rsvp_session **sht = ((struct rsvp_head*)tp->root)->ht;
	struct rsvp_session *s;
	struct rsvp_filter *f;
	unsigned h1 = handle&0xFF;
	unsigned h2 = (handle>>8)&0xFF;

	if (h2 > 16)
		return 0;

	for (s = sht[h1]; s; s = s->next) {
		for (f = s->ht[h2]; f; f = f->next) {
			if (f->handle == handle)
				return (unsigned long)f;
		}
	}
	return 0;
}

static void rsvp_put(struct tcf_proto *tp, unsigned long f)
{
}

static int rsvp_init(struct tcf_proto *tp)
{
	struct rsvp_head *data;

	data = kzalloc(sizeof(struct rsvp_head), GFP_KERNEL);
	if (data) {
		tp->root = data;
		return 0;
	}
	return -ENOBUFS;
}

static inline void
rsvp_delete_filter(struct tcf_proto *tp, struct rsvp_filter *f)
{
	tcf_unbind_filter(tp, &f->res);
	tcf_exts_destroy(tp, &f->exts);
	kfree(f);
}

static void rsvp_destroy(struct tcf_proto *tp)
{
	struct rsvp_head *data = xchg(&tp->root, NULL);
	struct rsvp_session **sht;
	int h1, h2;

	if (data == NULL)
		return;

	sht = data->ht;

	for (h1=0; h1<256; h1++) {
		struct rsvp_session *s;

		while ((s = sht[h1]) != NULL) {
			sht[h1] = s->next;

			for (h2=0; h2<=16; h2++) {
				struct rsvp_filter *f;

				while ((f = s->ht[h2]) != NULL) {
					s->ht[h2] = f->next;
					rsvp_delete_filter(tp, f);
				}
			}
			kfree(s);
		}
	}
	kfree(data);
}

static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
{
	struct rsvp_filter **fp, *f = (struct rsvp_filter*)arg;
	unsigned h = f->handle;
	struct rsvp_session **sp;
	struct rsvp_session *s = f->sess;
	int i;

	for (fp = &s->ht[(h>>8)&0xFF]; *fp; fp = &(*fp)->next) {
		if (*fp == f) {
			tcf_tree_lock(tp);
			*fp = f->next;
			tcf_tree_unlock(tp);
			rsvp_delete_filter(tp, f);

			/* Strip tree */

			for (i=0; i<=16; i++)
				if (s->ht[i])
					return 0;

			/* OK, session has no flows */
			for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
			     *sp; sp = &(*sp)->next) {
				if (*sp == s) {
					tcf_tree_lock(tp);
					*sp = s->next;
					tcf_tree_unlock(tp);

					kfree(s);
					return 0;
				}
			}

			return 0;
		}
	}
	return 0;
}

static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
{
	struct rsvp_head *data = tp->root;
	int i = 0xFFFF;

	while (i-- > 0) {
		u32 h;
		if ((data->hgenerator += 0x10000) == 0)
			data->hgenerator = 0x10000;
		h = data->hgenerator|salt;
		if (rsvp_get(tp, h) == 0)
			return h;
	}
	return 0;
}

static int tunnel_bts(struct rsvp_head *data)
{
	int n = data->tgenerator>>5;
	u32 b = 1<<(data->tgenerator&0x1F);

	if (data->tmap[n]&b)
		return 0;
	data->tmap[n] |= b;
	return 1;
}

static void tunnel_recycle(struct rsvp_head *data)
{
	struct rsvp_session **sht = data->ht;
	u32 tmap[256/32];
	int h1, h2;

	memset(tmap, 0, sizeof(tmap));

	for (h1=0; h1<256; h1++) {
		struct rsvp_session *s;
		for (s = sht[h1]; s; s = s->next) {
			for (h2=0; h2<=16; h2++) {
				struct rsvp_filter *f;

				for (f = s->ht[h2]; f; f = f->next) {
					if (f->tunnelhdr == 0)
						continue;
					data->tgenerator = f->res.classid;
					tunnel_bts(data);
				}
			}
		}
	}

	memcpy(data->tmap, tmap, sizeof(tmap));
}

static u32 gen_tunnel(struct rsvp_head *data)
{
	int i, k;

	for (k=0; k<2; k++) {
		for (i=255; i>0; i--) {
			if (++data->tgenerator == 0)
				data->tgenerator = 1;
			if (tunnel_bts(data))
				return data->tgenerator;
		}
		tunnel_recycle(data);
	}
	return 0;
}

static const struct nla_policy rsvp_policy[TCA_RSVP_MAX + 1] = {
	[TCA_RSVP_CLASSID]	= { .type = NLA_U32 },
	[TCA_RSVP_DST]		= { .type = NLA_BINARY,
				    .len = RSVP_DST_LEN * sizeof(u32) },
	[TCA_RSVP_SRC]		= { .type = NLA_BINARY,
				    .len = RSVP_DST_LEN * sizeof(u32) },
	[TCA_RSVP_PINFO]	= { .len = sizeof(struct tc_rsvp_pinfo) },
};

static int rsvp_change(struct tcf_proto *tp, unsigned long base,
		       u32 handle,
		       struct nlattr **tca,
		       unsigned long *arg)
{
	struct rsvp_head *data = tp->root;
	struct rsvp_filter *f, **fp;
	struct rsvp_session *s, **sp;
	struct tc_rsvp_pinfo *pinfo = NULL;
	struct nlattr *opt = tca[TCA_OPTIONS-1];
	struct nlattr *tb[TCA_RSVP_MAX + 1];
	struct tcf_exts e;
	unsigned h1, h2;
	__be32 *dst;
	int err;

	if (opt == NULL)
		return handle ? -EINVAL : 0;

	err = nla_parse_nested(tb, TCA_RSVP_MAX, opt, rsvp_policy);
	if (err < 0)
		return err;

	err = tcf_exts_validate(tp, tb, tca[TCA_RATE-1], &e, &rsvp_ext_map);
	if (err < 0)
		return err;

	if ((f = (struct rsvp_filter*)*arg) != NULL) {
		/* Node exists: adjust only classid */

		if (f->handle != handle && handle)
			goto errout2;
		if (tb[TCA_RSVP_CLASSID-1]) {
			f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
			tcf_bind_filter(tp, &f->res, base);
		}

		tcf_exts_change(tp, &f->exts, &e);
		return 0;
	}

	/* Now more serious part... */
	err = -EINVAL;
	if (handle)
		goto errout2;
	if (tb[TCA_RSVP_DST-1] == NULL)
		goto errout2;

	err = -ENOBUFS;
	f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
	if (f == NULL)
		goto errout2;

	h2 = 16;
	if (tb[TCA_RSVP_SRC-1]) {
		memcpy(f->src, nla_data(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
		h2 = hash_src(f->src);
	}
	if (tb[TCA_RSVP_PINFO-1]) {
		pinfo = nla_data(tb[TCA_RSVP_PINFO-1]);
		f->spi = pinfo->spi;
		f->tunnelhdr = pinfo->tunnelhdr;
	}
	if (tb[TCA_RSVP_CLASSID-1])
		f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);

	dst = nla_data(tb[TCA_RSVP_DST-1]);
	h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);

	err = -ENOMEM;
	if ((f->handle = gen_handle(tp, h1 | (h2<<8))) == 0)
		goto errout;

	if (f->tunnelhdr) {
		err = -EINVAL;
		if (f->res.classid > 255)
			goto errout;

		err = -ENOMEM;
		if (f->res.classid == 0 &&
		    (f->res.classid = gen_tunnel(data)) == 0)
			goto errout;
	}

	for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
		if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
		    pinfo && pinfo->protocol == s->protocol &&
		    memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
#if RSVP_DST_LEN == 4
		    && dst[0] == s->dst[0]
		    && dst[1] == s->dst[1]
		    && dst[2] == s->dst[2]
#endif
		    && pinfo->tunnelid == s->tunnelid) {

insert:
			/* OK, we found appropriate session */

			fp = &s->ht[h2];

			f->sess = s;
			if (f->tunnelhdr == 0)
				tcf_bind_filter(tp, &f->res, base);

			tcf_exts_change(tp, &f->exts, &e);

			for (fp = &s->ht[h2]; *fp; fp = &(*fp)->next)
				if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
					break;
			f->next = *fp;
			wmb();
			*fp = f;

			*arg = (unsigned long)f;
			return 0;
		}
	}

	/* No session found. Create new one. */

	err = -ENOBUFS;
	s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
	if (s == NULL)
		goto errout;
	memcpy(s->dst, dst, sizeof(s->dst));

	if (pinfo) {
		s->dpi = pinfo->dpi;
		s->protocol = pinfo->protocol;
		s->tunnelid = pinfo->tunnelid;
	}
	for (sp = &data->ht[h1]; *sp; sp = &(*sp)->next) {
		if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
			break;
	}
	s->next = *sp;
	wmb();
	*sp = s;

	goto insert;

errout:
	kfree(f);
errout2:
	tcf_exts_destroy(tp, &e);
	return err;
}

static void rsvp_walk(struct tcf_proto *tp, struct tcf_walker *arg)
{
	struct rsvp_head *head = tp->root;
	unsigned h, h1;

	if (arg->stop)
		return;

	for (h = 0; h < 256; h++) {
		struct rsvp_session *s;

		for (s = head->ht[h]; s; s = s->next) {
			for (h1 = 0; h1 <= 16; h1++) {
				struct rsvp_filter *f;

				for (f = s->ht[h1]; f; f = f->next) {
					if (arg->count < arg->skip) {
						arg->count++;
						continue;
					}
					if (arg->fn(tp, (unsigned long)f, arg) < 0) {
						arg->stop = 1;
						return;
					}
					arg->count++;
				}
			}
		}
	}
}

static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
		     struct sk_buff *skb, struct tcmsg *t)
{
	struct rsvp_filter *f = (struct rsvp_filter*)fh;
	struct rsvp_session *s;
	unsigned char *b = skb_tail_pointer(skb);
	struct nlattr *nest;
	struct tc_rsvp_pinfo pinfo;

	if (f == NULL)
		return skb->len;
	s = f->sess;

	t->tcm_handle = f->handle;

	nest = nla_nest_start(skb, TCA_OPTIONS);
	if (nest == NULL)
		goto nla_put_failure;

	NLA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
	pinfo.dpi = s->dpi;
	pinfo.spi = f->spi;
	pinfo.protocol = s->protocol;
	pinfo.tunnelid = s->tunnelid;
	pinfo.tunnelhdr = f->tunnelhdr;
	pinfo.pad = 0;
	NLA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
	if (f->res.classid)
		NLA_PUT_U32(skb, TCA_RSVP_CLASSID, f->res.classid);
	if (((f->handle>>8)&0xFF) != 16)
		NLA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);

	if (tcf_exts_dump(skb, &f->exts, &rsvp_ext_map) < 0)
		goto nla_put_failure;

	nla_nest_end(skb, nest);

	if (tcf_exts_dump_stats(skb, &f->exts, &rsvp_ext_map) < 0)
		goto nla_put_failure;
	return skb->len;

nla_put_failure:
	nlmsg_trim(skb, b);
	return -1;
}

static struct tcf_proto_ops RSVP_OPS = {
	.next		=	NULL,
	.kind		=	RSVP_ID,
	.classify	=	rsvp_classify,
	.init		=	rsvp_init,
	.destroy	=	rsvp_destroy,
	.get		=	rsvp_get,
	.put		=	rsvp_put,
	.change		=	rsvp_change,
	.delete		=	rsvp_delete,
	.walk		=	rsvp_walk,
	.dump		=	rsvp_dump,
	.owner		=	THIS_MODULE,
};

static int __init init_rsvp(void)
{
	return register_tcf_proto_ops(&RSVP_OPS);
}

static void __exit exit_rsvp(void)
{
	unregister_tcf_proto_ops(&RSVP_OPS);
}

module_init(init_rsvp)
module_exit(exit_rsvp)
Commit	Line	Data
1da177e4 LT	1	/*
	2	* net/sched/cls_rsvp.h Template file for RSVPv[46] classifiers.
	3	*
	4	* This program is free software; you can redistribute it and/or
	5	* modify it under the terms of the GNU General Public License
	6	* as published by the Free Software Foundation; either version
	7	* 2 of the License, or (at your option) any later version.
	8	*
	9	* Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
	10	*/
	11
	12	/*
	13	Comparing to general packet classification problem,
	14	RSVP needs only sevaral relatively simple rules:
	15
	16	* (dst, protocol) are always specified,
	17	so that we are able to hash them.
	18	* src may be exact, or may be wildcard, so that
	19	we can keep a hash table plus one wildcard entry.
	20	* source port (or flow label) is important only if src is given.
	21
	22	IMPLEMENTATION.
	23
	24	We use a two level hash table: The top level is keyed by
	25	destination address and protocol ID, every bucket contains a list
	26	of "rsvp sessions", identified by destination address, protocol and
	27	DPI(="Destination Port ID"): triple (key, mask, offset).
	28
	29	Every bucket has a smaller hash table keyed by source address
	30	(cf. RSVP flowspec) and one wildcard entry for wildcard reservations.
	31	Every bucket is again a list of "RSVP flows", selected by
	32	source address and SPI(="Source Port ID" here rather than
	33	"security parameter index"): triple (key, mask, offset).
	34
	35
	36	NOTE 1. All the packets with IPv6 extension headers (but AH and ESP)
	37	and all fragmented packets go to the best-effort traffic class.
	38
	39
	40	NOTE 2. Two "port id"'s seems to be redundant, rfc2207 requires
	41	only one "Generalized Port Identifier". So that for classic
	42	ah, esp (and udp,tcp) both *pi should coincide or one of them
	43	should be wildcard.
	44
	45	At first sight, this redundancy is just a waste of CPU
	46	resources. But DPI and SPI add the possibility to assign different
	47	priorities to GPIs. Look also at note 4 about tunnels below.
	48
	49
	50	NOTE 3. One complication is the case of tunneled packets.
	51	We implement it as following: if the first lookup
	52	matches a special session with "tunnelhdr" value not zero,
	53	flowid doesn't contain the true flow ID, but the tunnel ID (1...255).
	54	In this case, we pull tunnelhdr bytes and restart lookup
	55	with tunnel ID added to the list of keys. Simple and stupid 8)8)
	56	It's enough for PIMREG and IPIP.
	57
	58
	59	NOTE 4. Two GPIs make it possible to parse even GRE packets.
	60	F.e. DPI can select ETH_P_IP (and necessary flags to make
	61	tunnelhdr correct) in GRE protocol field and SPI matches
	62	GRE key. Is it not nice? 8)8)
	63
	64
65	Well, as result, despite its simplicity, we get a pretty
66	powerful classification engine. */
67
1da177e4 LT	68
	69	struct rsvp_head
	70	{
	71	u32 tmap[256/32];
	72	u32 hgenerator;
	73	u8 tgenerator;
	74	struct rsvp_session *ht[256];
	75	};
	76
	77	struct rsvp_session
	78	{
	79	struct rsvp_session *next;
66c6f529	80	__be32 dst[RSVP_DST_LEN];
1da177e4 LT	81	struct tc_rsvp_gpi dpi;
	82	u8 protocol;
	83	u8 tunnelid;
	84	/* 16 (src,sport) hash slots, and one wildcard source slot */
	85	struct rsvp_filter *ht[16+1];
	86	};
	87
	88
	89	struct rsvp_filter
	90	{
	91	struct rsvp_filter *next;
66c6f529	92	__be32 src[RSVP_DST_LEN];
1da177e4 LT	93	struct tc_rsvp_gpi spi;
	94	u8 tunnelhdr;
	95
	96	struct tcf_result res;
	97	struct tcf_exts exts;
	98
	99	u32 handle;
	100	struct rsvp_session *sess;
	101	};
	102
66c6f529	103	static __inline__ unsigned hash_dst(__be32 *dst, u8 protocol, u8 tunnelid)
1da177e4	104	{
66c6f529	105	unsigned h = (__force __u32)dst[RSVP_DST_LEN-1];
1da177e4 LT	106	h ^= h>>16;
	107	h ^= h>>8;
	108	return (h ^ protocol ^ tunnelid) & 0xFF;
	109	}
	110
66c6f529	111	static __inline__ unsigned hash_src(__be32 *src)
1da177e4	112	{
66c6f529	113	unsigned h = (__force __u32)src[RSVP_DST_LEN-1];
1da177e4 LT	114	h ^= h>>16;
	115	h ^= h>>8;
	116	h ^= h>>4;
	117	return h & 0xF;
	118	}
	119
	120	static struct tcf_ext_map rsvp_ext_map = {
	121	.police = TCA_RSVP_POLICE,
	122	.action = TCA_RSVP_ACT
	123	};
	124
	125	#define RSVP_APPLY_RESULT() \
	126	{ \
	127	int r = tcf_exts_exec(skb, &f->exts, res); \
	128	if (r < 0) \
	129	continue; \
	130	else if (r > 0) \
	131	return r; \
	132	}
10297b99	133
1da177e4 LT	134	static int rsvp_classify(struct sk_buff skb, struct tcf_proto tp,
	135	struct tcf_result *res)
	136	{
	137	struct rsvp_session *sht = ((struct rsvp_head)tp->root)->ht;
	138	struct rsvp_session *s;
	139	struct rsvp_filter *f;
	140	unsigned h1, h2;
66c6f529	141	__be32 dst, src;
1da177e4 LT	142	u8 protocol;
	143	u8 tunnelid = 0;
	144	u8 *xprt;
	145	#if RSVP_DST_LEN == 4
0660e03f	146	struct ipv6hdr *nhptr = ipv6_hdr(skb);
1da177e4	147	#else
eddc9ec5	148	struct iphdr *nhptr = ip_hdr(skb);
1da177e4 LT	149	#endif
	150
	151	restart:
	152
	153	#if RSVP_DST_LEN == 4
	154	src = &nhptr->saddr.s6_addr32[0];
	155	dst = &nhptr->daddr.s6_addr32[0];
	156	protocol = nhptr->nexthdr;
	157	xprt = ((u8*)nhptr) + sizeof(struct ipv6hdr);
	158	#else
	159	src = &nhptr->saddr;
	160	dst = &nhptr->daddr;
	161	protocol = nhptr->protocol;
	162	xprt = ((u8*)nhptr) + (nhptr->ihl<<2);
b6d9bcb0	163	if (nhptr->frag_off & htons(IP_MF\|IP_OFFSET))
1da177e4 LT	164	return -1;
	165	#endif
	166
	167	h1 = hash_dst(dst, protocol, tunnelid);
	168	h2 = hash_src(src);
	169
	170	for (s = sht[h1]; s; s = s->next) {
	171	if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
	172	protocol == s->protocol &&
	173	!(s->dpi.mask & ((u32)(xprt+s->dpi.offset)^s->dpi.key))
	174	#if RSVP_DST_LEN == 4
	175	&& dst[0] == s->dst[0]
	176	&& dst[1] == s->dst[1]
	177	&& dst[2] == s->dst[2]
	178	#endif
	179	&& tunnelid == s->tunnelid) {
	180
	181	for (f = s->ht[h2]; f; f = f->next) {
	182	if (src[RSVP_DST_LEN-1] == f->src[RSVP_DST_LEN-1] &&
	183	!(f->spi.mask & ((u32)(xprt+f->spi.offset)^f->spi.key))
	184	#if RSVP_DST_LEN == 4
	185	&& src[0] == f->src[0]
	186	&& src[1] == f->src[1]
	187	&& src[2] == f->src[2]
	188	#endif
	189	) {
	190	*res = f->res;
	191	RSVP_APPLY_RESULT();
	192
	193	matched:
	194	if (f->tunnelhdr == 0)
	195	return 0;
	196
	197	tunnelid = f->res.classid;
	198	nhptr = (void)(xprt + f->tunnelhdr - sizeof(nhptr));
	199	goto restart;
	200	}
	201	}
	202
	203	/* And wildcard bucket... */
	204	for (f = s->ht[16]; f; f = f->next) {
	205	*res = f->res;
	206	RSVP_APPLY_RESULT();
	207	goto matched;
	208	}
	209	return -1;
	210	}
	211	}
	212	return -1;
	213	}
	214
	215	static unsigned long rsvp_get(struct tcf_proto *tp, u32 handle)
	216	{
	217	struct rsvp_session *sht = ((struct rsvp_head)tp->root)->ht;
	218	struct rsvp_session *s;
	219	struct rsvp_filter *f;
	220	unsigned h1 = handle&0xFF;
	221	unsigned h2 = (handle>>8)&0xFF;
	222
	223	if (h2 > 16)
	224	return 0;
	225
	226	for (s = sht[h1]; s; s = s->next) {
	227	for (f = s->ht[h2]; f; f = f->next) {
228	if (f->handle == handle)
229	return (unsigned long)f;
230	}
231	}
232	return 0;
233	}
234
235	static void rsvp_put(struct tcf_proto *tp, unsigned long f)
236	{
237	}
238
239	static int rsvp_init(struct tcf_proto *tp)
240	{
241	struct rsvp_head *data;
242
0da974f4	243	data = kzalloc(sizeof(struct rsvp_head), GFP_KERNEL);
1da177e4	244	if (data) {
1da177e4 LT	245	tp->root = data;
	246	return 0;
	247	}
	248	return -ENOBUFS;
	249	}
	250
	251	static inline void
	252	rsvp_delete_filter(struct tcf_proto tp, struct rsvp_filter f)
	253	{
	254	tcf_unbind_filter(tp, &f->res);
	255	tcf_exts_destroy(tp, &f->exts);
	256	kfree(f);
	257	}
	258
	259	static void rsvp_destroy(struct tcf_proto *tp)
	260	{
	261	struct rsvp_head *data = xchg(&tp->root, NULL);
	262	struct rsvp_session **sht;
	263	int h1, h2;
	264
	265	if (data == NULL)
	266	return;
	267
	268	sht = data->ht;
	269
	270	for (h1=0; h1<256; h1++) {
	271	struct rsvp_session *s;
	272
	273	while ((s = sht[h1]) != NULL) {
	274	sht[h1] = s->next;
	275
	276	for (h2=0; h2<=16; h2++) {
	277	struct rsvp_filter *f;
	278
	279	while ((f = s->ht[h2]) != NULL) {
	280	s->ht[h2] = f->next;
	281	rsvp_delete_filter(tp, f);
	282	}
	283	}
	284	kfree(s);
	285	}
	286	}
	287	kfree(data);
	288	}
	289
	290	static int rsvp_delete(struct tcf_proto *tp, unsigned long arg)
	291	{
	292	struct rsvp_filter *fp, f = (struct rsvp_filter*)arg;
	293	unsigned h = f->handle;
	294	struct rsvp_session **sp;
	295	struct rsvp_session *s = f->sess;
	296	int i;
	297
	298	for (fp = &s->ht[(h>>8)&0xFF]; fp; fp = &(fp)->next) {
	299	if (*fp == f) {
	300	tcf_tree_lock(tp);
	301	*fp = f->next;
	302	tcf_tree_unlock(tp);
	303	rsvp_delete_filter(tp, f);
	304
	305	/* Strip tree */
	306
	307	for (i=0; i<=16; i++)
	308	if (s->ht[i])
309	return 0;
310
311	/* OK, session has no flows */
312	for (sp = &((struct rsvp_head*)tp->root)->ht[h&0xFF];
313	sp; sp = &(sp)->next) {
314	if (*sp == s) {
315	tcf_tree_lock(tp);
316	*sp = s->next;
317	tcf_tree_unlock(tp);
318
319	kfree(s);
320	return 0;
321	}
322	}
323
324	return 0;
325	}
326	}
327	return 0;
328	}
329
330	static unsigned gen_handle(struct tcf_proto *tp, unsigned salt)
331	{
332	struct rsvp_head *data = tp->root;
333	int i = 0xFFFF;
334
335	while (i-- > 0) {
336	u32 h;
337	if ((data->hgenerator += 0x10000) == 0)
338	data->hgenerator = 0x10000;
339	h = data->hgenerator\|salt;
340	if (rsvp_get(tp, h) == 0)
341	return h;
342	}
343	return 0;
344	}
345
346	static int tunnel_bts(struct rsvp_head *data)
347	{
348	int n = data->tgenerator>>5;
349	u32 b = 1<<(data->tgenerator&0x1F);
10297b99	350
1da177e4 LT	351	if (data->tmap[n]&b)
	352	return 0;
	353	data->tmap[n] \|= b;
	354	return 1;
	355	}
	356
	357	static void tunnel_recycle(struct rsvp_head *data)
	358	{
	359	struct rsvp_session **sht = data->ht;
	360	u32 tmap[256/32];
	361	int h1, h2;
	362
	363	memset(tmap, 0, sizeof(tmap));
	364
	365	for (h1=0; h1<256; h1++) {
	366	struct rsvp_session *s;
	367	for (s = sht[h1]; s; s = s->next) {
	368	for (h2=0; h2<=16; h2++) {
	369	struct rsvp_filter *f;
	370
	371	for (f = s->ht[h2]; f; f = f->next) {
	372	if (f->tunnelhdr == 0)
	373	continue;
	374	data->tgenerator = f->res.classid;
	375	tunnel_bts(data);
	376	}
	377	}
	378	}
	379	}
	380
	381	memcpy(data->tmap, tmap, sizeof(tmap));
	382	}
	383
	384	static u32 gen_tunnel(struct rsvp_head *data)
	385	{
	386	int i, k;
	387
	388	for (k=0; k<2; k++) {
	389	for (i=255; i>0; i--) {
	390	if (++data->tgenerator == 0)
	391	data->tgenerator = 1;
	392	if (tunnel_bts(data))
	393	return data->tgenerator;
	394	}
	395	tunnel_recycle(data);
	396	}
	397	return 0;
	398	}
	399
6fa8c014 PM	400	static const struct nla_policy rsvp_policy[TCA_RSVP_MAX + 1] = {
	401	[TCA_RSVP_CLASSID] = { .type = NLA_U32 },
	402	[TCA_RSVP_DST] = { .type = NLA_BINARY,
	403	.len = RSVP_DST_LEN * sizeof(u32) },
	404	[TCA_RSVP_SRC] = { .type = NLA_BINARY,
	405	.len = RSVP_DST_LEN * sizeof(u32) },
	406	[TCA_RSVP_PINFO] = { .len = sizeof(struct tc_rsvp_pinfo) },
	407	};
	408
1da177e4 LT	409	static int rsvp_change(struct tcf_proto *tp, unsigned long base,
1da177e4 LT	410	u32 handle,
add93b61	411	struct nlattr **tca,
1da177e4 LT	412	unsigned long *arg)
	413	{
	414	struct rsvp_head *data = tp->root;
	415	struct rsvp_filter f, *fp;
	416	struct rsvp_session s, *sp;
	417	struct tc_rsvp_pinfo *pinfo = NULL;
add93b61 PM	418	struct nlattr *opt = tca[TCA_OPTIONS-1];
add93b61 PM	419	struct nlattr *tb[TCA_RSVP_MAX + 1];
1da177e4 LT	420	struct tcf_exts e;
1da177e4 LT	421	unsigned h1, h2;
66c6f529	422	__be32 *dst;
1da177e4 LT	423	int err;
	424
	425	if (opt == NULL)
	426	return handle ? -EINVAL : 0;
	427
6fa8c014	428	err = nla_parse_nested(tb, TCA_RSVP_MAX, opt, rsvp_policy);
cee63723 PM	429	if (err < 0)
cee63723 PM	430	return err;
1da177e4 LT	431
	432	err = tcf_exts_validate(tp, tb, tca[TCA_RATE-1], &e, &rsvp_ext_map);
	433	if (err < 0)
	434	return err;
	435
	436	if ((f = (struct rsvp_filter)arg) != NULL) {
	437	/* Node exists: adjust only classid */
	438
	439	if (f->handle != handle && handle)
	440	goto errout2;
	441	if (tb[TCA_RSVP_CLASSID-1]) {
1587bac4	442	f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
1da177e4 LT	443	tcf_bind_filter(tp, &f->res, base);
	444	}
	445
	446	tcf_exts_change(tp, &f->exts, &e);
	447	return 0;
	448	}
	449
	450	/* Now more serious part... */
	451	err = -EINVAL;
	452	if (handle)
	453	goto errout2;
	454	if (tb[TCA_RSVP_DST-1] == NULL)
	455	goto errout2;
	456
	457	err = -ENOBUFS;
0da974f4	458	f = kzalloc(sizeof(struct rsvp_filter), GFP_KERNEL);
1da177e4 LT	459	if (f == NULL)
	460	goto errout2;
	461
1da177e4 LT	462	h2 = 16;
1da177e4 LT	463	if (tb[TCA_RSVP_SRC-1]) {
add93b61	464	memcpy(f->src, nla_data(tb[TCA_RSVP_SRC-1]), sizeof(f->src));
1da177e4 LT	465	h2 = hash_src(f->src);
	466	}
	467	if (tb[TCA_RSVP_PINFO-1]) {
add93b61	468	pinfo = nla_data(tb[TCA_RSVP_PINFO-1]);
1da177e4 LT	469	f->spi = pinfo->spi;
	470	f->tunnelhdr = pinfo->tunnelhdr;
	471	}
6fa8c014	472	if (tb[TCA_RSVP_CLASSID-1])
1587bac4	473	f->res.classid = nla_get_u32(tb[TCA_RSVP_CLASSID-1]);
1da177e4	474
add93b61	475	dst = nla_data(tb[TCA_RSVP_DST-1]);
1da177e4 LT	476	h1 = hash_dst(dst, pinfo ? pinfo->protocol : 0, pinfo ? pinfo->tunnelid : 0);
	477
	478	err = -ENOMEM;
	479	if ((f->handle = gen_handle(tp, h1 \| (h2<<8))) == 0)
	480	goto errout;
	481
	482	if (f->tunnelhdr) {
	483	err = -EINVAL;
	484	if (f->res.classid > 255)
	485	goto errout;
	486
	487	err = -ENOMEM;
	488	if (f->res.classid == 0 &&
	489	(f->res.classid = gen_tunnel(data)) == 0)
	490	goto errout;
	491	}
	492
	493	for (sp = &data->ht[h1]; (s=*sp) != NULL; sp = &s->next) {
	494	if (dst[RSVP_DST_LEN-1] == s->dst[RSVP_DST_LEN-1] &&
	495	pinfo && pinfo->protocol == s->protocol &&
	496	memcmp(&pinfo->dpi, &s->dpi, sizeof(s->dpi)) == 0
	497	#if RSVP_DST_LEN == 4
	498	&& dst[0] == s->dst[0]
	499	&& dst[1] == s->dst[1]
	500	&& dst[2] == s->dst[2]
	501	#endif
	502	&& pinfo->tunnelid == s->tunnelid) {
	503
	504	insert:
	505	/* OK, we found appropriate session */
	506
	507	fp = &s->ht[h2];
	508
	509	f->sess = s;
	510	if (f->tunnelhdr == 0)
	511	tcf_bind_filter(tp, &f->res, base);
	512
	513	tcf_exts_change(tp, &f->exts, &e);
	514
	515	for (fp = &s->ht[h2]; fp; fp = &(fp)->next)
	516	if (((*fp)->spi.mask&f->spi.mask) != f->spi.mask)
	517	break;
	518	f->next = *fp;
	519	wmb();
	520	*fp = f;
	521
	522	*arg = (unsigned long)f;
	523	return 0;
	524	}
	525	}
	526
	527	/* No session found. Create new one. */
	528
	529	err = -ENOBUFS;
0da974f4	530	s = kzalloc(sizeof(struct rsvp_session), GFP_KERNEL);
1da177e4 LT	531	if (s == NULL)
1da177e4 LT	532	goto errout;
1da177e4 LT	533	memcpy(s->dst, dst, sizeof(s->dst));
	534
	535	if (pinfo) {
	536	s->dpi = pinfo->dpi;
	537	s->protocol = pinfo->protocol;
	538	s->tunnelid = pinfo->tunnelid;
	539	}
	540	for (sp = &data->ht[h1]; sp; sp = &(sp)->next) {
	541	if (((*sp)->dpi.mask&s->dpi.mask) != s->dpi.mask)
	542	break;
	543	}
	544	s->next = *sp;
	545	wmb();
	546	*sp = s;
10297b99	547
1da177e4 LT	548	goto insert;
	549
	550	errout:
a51482bd	551	kfree(f);
1da177e4 LT	552	errout2:
	553	tcf_exts_destroy(tp, &e);
	554	return err;
	555	}
	556
	557	static void rsvp_walk(struct tcf_proto tp, struct tcf_walker arg)
	558	{
	559	struct rsvp_head *head = tp->root;
	560	unsigned h, h1;
	561
	562	if (arg->stop)
	563	return;
	564
	565	for (h = 0; h < 256; h++) {
	566	struct rsvp_session *s;
	567
	568	for (s = head->ht[h]; s; s = s->next) {
	569	for (h1 = 0; h1 <= 16; h1++) {
	570	struct rsvp_filter *f;
	571
	572	for (f = s->ht[h1]; f; f = f->next) {
	573	if (arg->count < arg->skip) {
	574	arg->count++;
	575	continue;
	576	}
	577	if (arg->fn(tp, (unsigned long)f, arg) < 0) {
	578	arg->stop = 1;
	579	return;
	580	}
	581	arg->count++;
	582	}
	583	}
	584	}
	585	}
	586	}
	587
	588	static int rsvp_dump(struct tcf_proto *tp, unsigned long fh,
	589	struct sk_buff skb, struct tcmsg t)
	590	{
	591	struct rsvp_filter f = (struct rsvp_filter)fh;
	592	struct rsvp_session *s;
27a884dc	593	unsigned char *b = skb_tail_pointer(skb);
4b3550ef	594	struct nlattr *nest;
1da177e4 LT	595	struct tc_rsvp_pinfo pinfo;
	596
	597	if (f == NULL)
	598	return skb->len;
	599	s = f->sess;
	600
	601	t->tcm_handle = f->handle;
	602
4b3550ef PM	603	nest = nla_nest_start(skb, TCA_OPTIONS);
	604	if (nest == NULL)
	605	goto nla_put_failure;
1da177e4	606
add93b61	607	NLA_PUT(skb, TCA_RSVP_DST, sizeof(s->dst), &s->dst);
1da177e4 LT	608	pinfo.dpi = s->dpi;
	609	pinfo.spi = f->spi;
	610	pinfo.protocol = s->protocol;
	611	pinfo.tunnelid = s->tunnelid;
	612	pinfo.tunnelhdr = f->tunnelhdr;
8a47077a	613	pinfo.pad = 0;
add93b61	614	NLA_PUT(skb, TCA_RSVP_PINFO, sizeof(pinfo), &pinfo);
1da177e4	615	if (f->res.classid)
24beeab5	616	NLA_PUT_U32(skb, TCA_RSVP_CLASSID, f->res.classid);
1da177e4	617	if (((f->handle>>8)&0xFF) != 16)
add93b61	618	NLA_PUT(skb, TCA_RSVP_SRC, sizeof(f->src), f->src);
1da177e4 LT	619
1da177e4 LT	620	if (tcf_exts_dump(skb, &f->exts, &rsvp_ext_map) < 0)
add93b61	621	goto nla_put_failure;
1da177e4	622
4b3550ef	623	nla_nest_end(skb, nest);
1da177e4 LT	624
1da177e4 LT	625	if (tcf_exts_dump_stats(skb, &f->exts, &rsvp_ext_map) < 0)
add93b61	626	goto nla_put_failure;
1da177e4 LT	627	return skb->len;
1da177e4 LT	628
add93b61	629	nla_put_failure:
dc5fc579	630	nlmsg_trim(skb, b);
1da177e4 LT	631	return -1;
	632	}
	633
	634	static struct tcf_proto_ops RSVP_OPS = {
	635	.next = NULL,
	636	.kind = RSVP_ID,
	637	.classify = rsvp_classify,
	638	.init = rsvp_init,
	639	.destroy = rsvp_destroy,
	640	.get = rsvp_get,
	641	.put = rsvp_put,
	642	.change = rsvp_change,
	643	.delete = rsvp_delete,
	644	.walk = rsvp_walk,
	645	.dump = rsvp_dump,
	646	.owner = THIS_MODULE,
	647	};
	648
	649	static int __init init_rsvp(void)
	650	{
	651	return register_tcf_proto_ops(&RSVP_OPS);
	652	}
	653
10297b99	654	static void __exit exit_rsvp(void)
1da177e4 LT	655	{
	656	unregister_tcf_proto_ops(&RSVP_OPS);
	657	}
	658
	659	module_init(init_rsvp)
	660	module_exit(exit_rsvp)