cls_u32.c 17.3 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
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
/*
 * net/sched/cls_u32.c	Ugly (or Universal) 32bit key Packet Classifier.
 *
 *		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>
 *
 *	The filters are packed to hash tables of key nodes
 *	with a set of 32bit key/mask pairs at every node.
 *	Nodes reference next level hash tables etc.
 *
 *	This scheme is the best universal classifier I managed to
 *	invent; it is not super-fast, but it is not slow (provided you
 *	program it correctly), and general enough.  And its relative
 *	speed grows as the number of rules becomes larger.
 *
 *	It seems that it represents the best middle point between
 *	speed and manageability both by human and by machine.
 *
 *	It is especially useful for link sharing combined with QoS;
 *	pure RSVP doesn't need such a general approach and can use
 *	much simpler (and faster) schemes, sort of cls_rsvp.c.
26 27 28 29
 *
 *	JHS: We should remove the CONFIG_NET_CLS_IND from here
 *	eventually when the meta match extension is made available
 *
Linus Torvalds's avatar
Linus Torvalds committed
30 31 32 33
 */

#include <asm/uaccess.h>
#include <asm/system.h>
34
#include <linux/bitops.h>
Linus Torvalds's avatar
Linus Torvalds committed
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
#include <linux/config.h>
#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/interrupt.h>
#include <linux/if_ether.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/etherdevice.h>
#include <linux/notifier.h>
#include <linux/rtnetlink.h>
#include <net/ip.h>
#include <net/route.h>
#include <linux/skbuff.h>
#include <net/sock.h>
57 58
#include <net/act_api.h>
#include <net/pkt_cls.h>
Linus Torvalds's avatar
Linus Torvalds committed
59 60 61 62 63 64 65


struct tc_u_knode
{
	struct tc_u_knode	*next;
	u32			handle;
	struct tc_u_hnode	*ht_up;
66 67 68
#ifdef CONFIG_NET_CLS_ACT
	struct tc_action	*action;
#else
Linus Torvalds's avatar
Linus Torvalds committed
69 70
#ifdef CONFIG_NET_CLS_POLICE
	struct tcf_police	*police;
71
#endif
72 73 74
#endif
#ifdef CONFIG_NET_CLS_IND
	char                     indev[IFNAMSIZ];
Linus Torvalds's avatar
Linus Torvalds committed
75
#endif
76
	u8			fshift;
Linus Torvalds's avatar
Linus Torvalds committed
77 78
	struct tcf_result	res;
	struct tc_u_hnode	*ht_down;
79 80 81
#ifdef CONFIG_CLS_U32_PERF
	struct tc_u32_pcnt	*pf;
#endif
Linus Torvalds's avatar
Linus Torvalds committed
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
	struct tc_u32_sel	sel;
};

struct tc_u_hnode
{
	struct tc_u_hnode	*next;
	u32			handle;
	struct tc_u_common	*tp_c;
	int			refcnt;
	unsigned		divisor;
	struct tc_u_knode	*ht[1];
};

struct tc_u_common
{
	struct tc_u_common	*next;
	struct tc_u_hnode	*hlist;
	struct Qdisc		*q;
	int			refcnt;
	u32			hgenerator;
};

static struct tc_u_common *u32_list;

106
static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fshift)
Linus Torvalds's avatar
Linus Torvalds committed
107
{
108
	unsigned h = (key & sel->hmask)>>fshift;
Linus Torvalds's avatar
Linus Torvalds committed
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

	return h;
}

static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res)
{
	struct {
		struct tc_u_knode *knode;
		u8		  *ptr;
	} stack[TC_U32_MAXDEPTH];

	struct tc_u_hnode *ht = (struct tc_u_hnode*)tp->root;
	u8 *ptr = skb->nh.raw;
	struct tc_u_knode *n;
	int sdepth = 0;
	int off2 = 0;
	int sel = 0;
126 127 128
#ifdef CONFIG_CLS_U32_PERF
	int j;
#endif
Linus Torvalds's avatar
Linus Torvalds committed
129 130 131 132 133 134 135 136 137
	int i;

next_ht:
	n = ht->ht[sel];

next_knode:
	if (n) {
		struct tc_u32_key *key = n->sel.keys;

138
#ifdef CONFIG_CLS_U32_PERF
139 140
		n->pf->rcnt +=1;
		j = 0;
141
#endif
Linus Torvalds's avatar
Linus Torvalds committed
142
		for (i = n->sel.nkeys; i>0; i--, key++) {
143

Linus Torvalds's avatar
Linus Torvalds committed
144 145 146 147
			if ((*(u32*)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) {
				n = n->next;
				goto next_knode;
			}
148
#ifdef CONFIG_CLS_U32_PERF
149 150
			n->pf->kcnts[j] +=1;
			j++;
151
#endif
Linus Torvalds's avatar
Linus Torvalds committed
152 153 154 155
		}
		if (n->ht_down == NULL) {
check_terminal:
			if (n->sel.flags&TC_U32_TERMINAL) {
156

Linus Torvalds's avatar
Linus Torvalds committed
157
				*res = n->res;
158
#ifdef CONFIG_NET_CLS_IND
159 160 161
				if (!tcf_match_indev(skb, n->indev)) {
					n = n->next;
					goto next_knode;
162 163 164
				}
#endif
#ifdef CONFIG_CLS_U32_PERF
165
				n->pf->rhit +=1;
166
#endif
167
#ifdef CONFIG_NET_CLS_ACT
168
				if (n->action) {
169
					int pol_res = tcf_action_exec(skb, n->action, res);
170 171 172 173
					if (pol_res >= 0)
						return pol_res;
				} else
#else
Linus Torvalds's avatar
Linus Torvalds committed
174 175 176 177 178 179
#ifdef CONFIG_NET_CLS_POLICE
				if (n->police) {
					int pol_res = tcf_police(skb, n->police);
					if (pol_res >= 0)
						return pol_res;
				} else
180
#endif
Linus Torvalds's avatar
Linus Torvalds committed
181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
#endif
					return 0;
			}
			n = n->next;
			goto next_knode;
		}

		/* PUSH */
		if (sdepth >= TC_U32_MAXDEPTH)
			goto deadloop;
		stack[sdepth].knode = n;
		stack[sdepth].ptr = ptr;
		sdepth++;

		ht = n->ht_down;
		sel = 0;
		if (ht->divisor)
198
			sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel,n->fshift);
Linus Torvalds's avatar
Linus Torvalds committed
199 200 201 202

		if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
			goto next_ht;

Linus Torvalds's avatar
Linus Torvalds committed
203
		if (n->sel.flags&(TC_U32_OFFSET|TC_U32_VAROFFSET)) {
Linus Torvalds's avatar
Linus Torvalds committed
204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248
			off2 = n->sel.off + 3;
			if (n->sel.flags&TC_U32_VAROFFSET)
				off2 += ntohs(n->sel.offmask & *(u16*)(ptr+n->sel.offoff)) >>n->sel.offshift;
			off2 &= ~3;
		}
		if (n->sel.flags&TC_U32_EAT) {
			ptr += off2;
			off2 = 0;
		}

		if (ptr < skb->tail)
			goto next_ht;
	}

	/* POP */
	if (sdepth--) {
		n = stack[sdepth].knode;
		ht = n->ht_up;
		ptr = stack[sdepth].ptr;
		goto check_terminal;
	}
	return -1;

deadloop:
	if (net_ratelimit())
		printk("cls_u32: dead loop\n");
	return -1;
}

static __inline__ struct tc_u_hnode *
u32_lookup_ht(struct tc_u_common *tp_c, u32 handle)
{
	struct tc_u_hnode *ht;

	for (ht = tp_c->hlist; ht; ht = ht->next)
		if (ht->handle == handle)
			break;

	return ht;
}

static __inline__ struct tc_u_knode *
u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
{
	unsigned sel;
249
	struct tc_u_knode *n = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
250 251 252

	sel = TC_U32_HASH(handle);
	if (sel > ht->divisor)
253
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
254 255 256

	for (n = ht->ht[sel]; n; n = n->next)
		if (n->handle == handle)
257 258 259
			break;
out:
	return n;
Linus Torvalds's avatar
Linus Torvalds committed
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
}


static unsigned long u32_get(struct tcf_proto *tp, u32 handle)
{
	struct tc_u_hnode *ht;
	struct tc_u_common *tp_c = tp->data;

	if (TC_U32_HTID(handle) == TC_U32_ROOT)
		ht = tp->root;
	else
		ht = u32_lookup_ht(tp_c, TC_U32_HTID(handle));

	if (!ht)
		return 0;

	if (TC_U32_KEY(handle) == 0)
		return (unsigned long)ht;

	return (unsigned long)u32_lookup_key(ht, handle);
}

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

static u32 gen_new_htid(struct tc_u_common *tp_c)
{
	int i = 0x800;

	do {
		if (++tp_c->hgenerator == 0x7FF)
			tp_c->hgenerator = 1;
Linus Torvalds's avatar
Linus Torvalds committed
293
	} while (--i>0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
Linus Torvalds's avatar
Linus Torvalds committed
294 295 296 297 298 299 300 301 302 303 304 305 306 307

	return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0;
}

static int u32_init(struct tcf_proto *tp)
{
	struct tc_u_hnode *root_ht;
	struct tc_u_common *tp_c;

	for (tp_c = u32_list; tp_c; tp_c = tp_c->next)
		if (tp_c->q == tp->q)
			break;

	root_ht = kmalloc(sizeof(*root_ht), GFP_KERNEL);
308
	if (root_ht == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
309
		return -ENOBUFS;
310

Linus Torvalds's avatar
Linus Torvalds committed
311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339
	memset(root_ht, 0, sizeof(*root_ht));
	root_ht->divisor = 0;
	root_ht->refcnt++;
	root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;

	if (tp_c == NULL) {
		tp_c = kmalloc(sizeof(*tp_c), GFP_KERNEL);
		if (tp_c == NULL) {
			kfree(root_ht);
			return -ENOBUFS;
		}
		memset(tp_c, 0, sizeof(*tp_c));
		tp_c->q = tp->q;
		tp_c->next = u32_list;
		u32_list = tp_c;
	}

	tp_c->refcnt++;
	root_ht->next = tp_c->hlist;
	tp_c->hlist = root_ht;
	root_ht->tp_c = tp_c;

	tp->root = root_ht;
	tp->data = tp_c;
	return 0;
}

static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n)
{
340
	tcf_unbind_filter(tp, &n->res);
341 342 343 344 345
#ifdef CONFIG_NET_CLS_ACT
	if (n->action) {
		tcf_action_destroy(n->action, TCA_ACT_UNBIND);
	}
#else
Linus Torvalds's avatar
Linus Torvalds committed
346
#ifdef CONFIG_NET_CLS_POLICE
347 348
	tcf_police_release(n->police, TCA_ACT_UNBIND);
#endif
Linus Torvalds's avatar
Linus Torvalds committed
349 350 351
#endif
	if (n->ht_down)
		n->ht_down->refcnt--;
352 353 354 355
#ifdef CONFIG_CLS_U32_PERF
	if (n && (NULL != n->pf))
		kfree(n->pf);
#endif
Linus Torvalds's avatar
Linus Torvalds committed
356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
	kfree(n);
	return 0;
}

static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode* key)
{
	struct tc_u_knode **kp;
	struct tc_u_hnode *ht = key->ht_up;

	if (ht) {
		for (kp = &ht->ht[TC_U32_HASH(key->handle)]; *kp; kp = &(*kp)->next) {
			if (*kp == key) {
				tcf_tree_lock(tp);
				*kp = key->next;
				tcf_tree_unlock(tp);

				u32_destroy_key(tp, key);
				return 0;
			}
		}
	}
	BUG_TRAP(0);
	return 0;
}

static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
{
	struct tc_u_knode *n;
	unsigned h;

	for (h=0; h<=ht->divisor; h++) {
		while ((n = ht->ht[h]) != NULL) {
			ht->ht[h] = n->next;

			u32_destroy_key(tp, n);
		}
	}
}

static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
{
	struct tc_u_common *tp_c = tp->data;
	struct tc_u_hnode **hn;

	BUG_TRAP(!ht->refcnt);

	u32_clear_hnode(tp, ht);

	for (hn = &tp_c->hlist; *hn; hn = &(*hn)->next) {
		if (*hn == ht) {
			*hn = ht->next;
			kfree(ht);
			return 0;
		}
	}

	BUG_TRAP(0);
	return -ENOENT;
}

static void u32_destroy(struct tcf_proto *tp)
{
	struct tc_u_common *tp_c = tp->data;
	struct tc_u_hnode *root_ht = xchg(&tp->root, NULL);

	BUG_TRAP(root_ht != NULL);

	if (root_ht && --root_ht->refcnt == 0)
		u32_destroy_hnode(tp, root_ht);

	if (--tp_c->refcnt == 0) {
		struct tc_u_hnode *ht;
		struct tc_u_common **tp_cp;

		for (tp_cp = &u32_list; *tp_cp; tp_cp = &(*tp_cp)->next) {
			if (*tp_cp == tp_c) {
				*tp_cp = tp_c->next;
				break;
			}
		}

		for (ht=tp_c->hlist; ht; ht = ht->next)
			u32_clear_hnode(tp, ht);

		while ((ht = tp_c->hlist) != NULL) {
			tp_c->hlist = ht->next;

			BUG_TRAP(ht->refcnt == 0);

			kfree(ht);
		};

		kfree(tp_c);
	}

	tp->data = NULL;
}

static int u32_delete(struct tcf_proto *tp, unsigned long arg)
{
	struct tc_u_hnode *ht = (struct tc_u_hnode*)arg;

	if (ht == NULL)
		return 0;

	if (TC_U32_KEY(ht->handle))
		return u32_delete_key(tp, (struct tc_u_knode*)ht);

	if (tp->root == ht)
		return -EINVAL;

	if (--ht->refcnt == 0)
		u32_destroy_hnode(tp, ht);

	return 0;
}

static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
{
	struct tc_u_knode *n;
	unsigned i = 0x7FF;

	for (n=ht->ht[TC_U32_HASH(handle)]; n; n = n->next)
		if (i < TC_U32_NODE(n->handle))
			i = TC_U32_NODE(n->handle);
	i++;

	return handle|(i>0xFFF ? 0xFFF : i);
}

486
static int u32_set_parms(struct tcf_proto *tp, unsigned long base,
Linus Torvalds's avatar
Linus Torvalds committed
487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
			 struct tc_u_hnode *ht,
			 struct tc_u_knode *n, struct rtattr **tb,
			 struct rtattr *est)
{
	if (tb[TCA_U32_LINK-1]) {
		u32 handle = *(u32*)RTA_DATA(tb[TCA_U32_LINK-1]);
		struct tc_u_hnode *ht_down = NULL;

		if (TC_U32_KEY(handle))
			return -EINVAL;

		if (handle) {
			ht_down = u32_lookup_ht(ht->tp_c, handle);

			if (ht_down == NULL)
				return -EINVAL;
			ht_down->refcnt++;
		}

506
		tcf_tree_lock(tp);
Linus Torvalds's avatar
Linus Torvalds committed
507
		ht_down = xchg(&n->ht_down, ht_down);
508
		tcf_tree_unlock(tp);
Linus Torvalds's avatar
Linus Torvalds committed
509 510 511 512 513 514

		if (ht_down)
			ht_down->refcnt--;
	}
	if (tb[TCA_U32_CLASSID-1]) {
		n->res.classid = *(u32*)RTA_DATA(tb[TCA_U32_CLASSID-1]);
515
		tcf_bind_filter(tp, &n->res, base);
Linus Torvalds's avatar
Linus Torvalds committed
516
	}
517
#ifdef CONFIG_NET_CLS_ACT
518 519 520 521
	if (tb[TCA_U32_POLICE-1]) {
		int err = tcf_change_act_police(tp, &n->action, tb[TCA_U32_POLICE-1], est);
		if (err < 0)
			return err;
522 523
	}

524 525 526 527
	if (tb[TCA_U32_ACT-1]) {
		int err = tcf_change_act(tp, &n->action, tb[TCA_U32_ACT-1], est);
		if (err < 0)
			return err;
528 529
	}
#else
Linus Torvalds's avatar
Linus Torvalds committed
530 531
#ifdef CONFIG_NET_CLS_POLICE
	if (tb[TCA_U32_POLICE-1]) {
532 533 534
		int err = tcf_change_police(tp, &n->police, tb[TCA_U32_POLICE-1], est);
		if (err < 0)
			return err;
Linus Torvalds's avatar
Linus Torvalds committed
535 536
	}
#endif
537 538
#endif
#ifdef CONFIG_NET_CLS_IND
539 540 541 542
	if (tb[TCA_U32_INDEV-1]) {
		int err = tcf_change_indev(tp, n->indev, tb[TCA_U32_INDEV-1]);
		if (err < 0)
			return err;
543
	}
544 545
#endif

Linus Torvalds's avatar
Linus Torvalds committed
546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571
	return 0;
}

static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
		      struct rtattr **tca,
		      unsigned long *arg)
{
	struct tc_u_common *tp_c = tp->data;
	struct tc_u_hnode *ht;
	struct tc_u_knode *n;
	struct tc_u32_sel *s;
	struct rtattr *opt = tca[TCA_OPTIONS-1];
	struct rtattr *tb[TCA_U32_MAX];
	u32 htid;
	int err;

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

	if (rtattr_parse(tb, TCA_U32_MAX, RTA_DATA(opt), RTA_PAYLOAD(opt)) < 0)
		return -EINVAL;

	if ((n = (struct tc_u_knode*)*arg) != NULL) {
		if (TC_U32_KEY(n->handle) == 0)
			return -EINVAL;

572
		return u32_set_parms(tp, base, n->ht_up, n, tb, tca[TCA_RATE-1]);
Linus Torvalds's avatar
Linus Torvalds committed
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630
	}

	if (tb[TCA_U32_DIVISOR-1]) {
		unsigned divisor = *(unsigned*)RTA_DATA(tb[TCA_U32_DIVISOR-1]);

		if (--divisor > 0x100)
			return -EINVAL;
		if (TC_U32_KEY(handle))
			return -EINVAL;
		if (handle == 0) {
			handle = gen_new_htid(tp->data);
			if (handle == 0)
				return -ENOMEM;
		}
		ht = kmalloc(sizeof(*ht) + divisor*sizeof(void*), GFP_KERNEL);
		if (ht == NULL)
			return -ENOBUFS;
		memset(ht, 0, sizeof(*ht) + divisor*sizeof(void*));
		ht->tp_c = tp_c;
		ht->refcnt = 0;
		ht->divisor = divisor;
		ht->handle = handle;
		ht->next = tp_c->hlist;
		tp_c->hlist = ht;
		*arg = (unsigned long)ht;
		return 0;
	}

	if (tb[TCA_U32_HASH-1]) {
		htid = *(unsigned*)RTA_DATA(tb[TCA_U32_HASH-1]);
		if (TC_U32_HTID(htid) == TC_U32_ROOT) {
			ht = tp->root;
			htid = ht->handle;
		} else {
			ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid));
			if (ht == NULL)
				return -EINVAL;
		}
	} else {
		ht = tp->root;
		htid = ht->handle;
	}

	if (ht->divisor < TC_U32_HASH(htid))
		return -EINVAL;

	if (handle) {
		if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid))
			return -EINVAL;
		handle = htid | TC_U32_NODE(handle);
	} else
		handle = gen_new_kid(ht, htid);

	if (tb[TCA_U32_SEL-1] == 0 ||
	    RTA_PAYLOAD(tb[TCA_U32_SEL-1]) < sizeof(struct tc_u32_sel))
		return -EINVAL;

	s = RTA_DATA(tb[TCA_U32_SEL-1]);
631

Linus Torvalds's avatar
Linus Torvalds committed
632 633 634
	n = kmalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
	if (n == NULL)
		return -ENOBUFS;
635

Linus Torvalds's avatar
Linus Torvalds committed
636
	memset(n, 0, sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key));
637 638 639 640 641 642 643 644 645
#ifdef CONFIG_CLS_U32_PERF
	n->pf = kmalloc(sizeof(struct tc_u32_pcnt) + s->nkeys*sizeof(__u64), GFP_KERNEL);
	if (n->pf == NULL) {
		kfree(n);
		return -ENOBUFS;
	}
	memset(n->pf, 0, sizeof(struct tc_u32_pcnt) + s->nkeys*sizeof(__u64));
#endif

Linus Torvalds's avatar
Linus Torvalds committed
646 647 648
	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
	n->ht_up = ht;
	n->handle = handle;
649 650 651 652 653 654 655 656 657 658 659
{
	u8 i = 0;
	u32 mask = s->hmask;
	if (mask) {
		while (!(mask & 1)) {
			i++;
			mask>>=1;
		}
	}
	n->fshift = i;
}
660
	err = u32_set_parms(tp, base, ht, n, tb, tca[TCA_RATE-1]);
Linus Torvalds's avatar
Linus Torvalds committed
661 662 663 664 665 666 667 668 669 670 671 672 673
	if (err == 0) {
		struct tc_u_knode **ins;
		for (ins = &ht->ht[TC_U32_HASH(handle)]; *ins; ins = &(*ins)->next)
			if (TC_U32_NODE(handle) < TC_U32_NODE((*ins)->handle))
				break;

		n->next = *ins;
		wmb();
		*ins = n;

		*arg = (unsigned long)n;
		return 0;
	}
674 675 676 677
#ifdef CONFIG_CLS_U32_PERF
	if (n && (NULL != n->pf))
		kfree(n->pf);
#endif
Linus Torvalds's avatar
Linus Torvalds committed
678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746
	kfree(n);
	return err;
}

static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg)
{
	struct tc_u_common *tp_c = tp->data;
	struct tc_u_hnode *ht;
	struct tc_u_knode *n;
	unsigned h;

	if (arg->stop)
		return;

	for (ht = tp_c->hlist; ht; ht = ht->next) {
		if (arg->count >= arg->skip) {
			if (arg->fn(tp, (unsigned long)ht, arg) < 0) {
				arg->stop = 1;
				return;
			}
		}
		arg->count++;
		for (h = 0; h <= ht->divisor; h++) {
			for (n = ht->ht[h]; n; n = n->next) {
				if (arg->count < arg->skip) {
					arg->count++;
					continue;
				}
				if (arg->fn(tp, (unsigned long)n, arg) < 0) {
					arg->stop = 1;
					return;
				}
				arg->count++;
			}
		}
	}
}

static int u32_dump(struct tcf_proto *tp, unsigned long fh,
		     struct sk_buff *skb, struct tcmsg *t)
{
	struct tc_u_knode *n = (struct tc_u_knode*)fh;
	unsigned char	 *b = skb->tail;
	struct rtattr *rta;

	if (n == NULL)
		return skb->len;

	t->tcm_handle = n->handle;

	rta = (struct rtattr*)b;
	RTA_PUT(skb, TCA_OPTIONS, 0, NULL);

	if (TC_U32_KEY(n->handle) == 0) {
		struct tc_u_hnode *ht = (struct tc_u_hnode*)fh;
		u32 divisor = ht->divisor+1;
		RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor);
	} else {
		RTA_PUT(skb, TCA_U32_SEL,
			sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
			&n->sel);
		if (n->ht_up) {
			u32 htid = n->handle & 0xFFFFF000;
			RTA_PUT(skb, TCA_U32_HASH, 4, &htid);
		}
		if (n->res.classid)
			RTA_PUT(skb, TCA_U32_CLASSID, 4, &n->res.classid);
		if (n->ht_down)
			RTA_PUT(skb, TCA_U32_LINK, 4, &n->ht_down->handle);
747
#ifdef CONFIG_NET_CLS_ACT
748 749
		if (tcf_dump_act(skb, n->action, TCA_U32_ACT, TCA_U32_POLICE) < 0)
			goto rtattr_failure;
750
#else
Linus Torvalds's avatar
Linus Torvalds committed
751
#ifdef CONFIG_NET_CLS_POLICE
752 753
		if (tcf_dump_police(skb, n->police, TCA_U32_POLICE) < 0)
			goto rtattr_failure;
754
#endif
755 756 757
#endif

#ifdef CONFIG_NET_CLS_IND
758
		if(strlen(n->indev))
759 760 761 762 763 764
			RTA_PUT(skb, TCA_U32_INDEV, IFNAMSIZ, n->indev);
#endif
#ifdef CONFIG_CLS_U32_PERF
		RTA_PUT(skb, TCA_U32_PCNT, 
		sizeof(struct tc_u32_pcnt) + n->sel.nkeys*sizeof(__u64),
			n->pf);
Linus Torvalds's avatar
Linus Torvalds committed
765 766 767 768
#endif
	}

	rta->rta_len = skb->tail - b;
769
#ifdef CONFIG_NET_CLS_ACT
770 771 772 773 774
	if (TC_U32_KEY(n->handle) != 0) {
		if (TC_U32_KEY(n->handle) && n->action && n->action->type == TCA_OLD_COMPAT) {
			if (tcf_action_copy_stats(skb,n->action))
				goto rtattr_failure;
		}
775 776
	}
#else
Linus Torvalds's avatar
Linus Torvalds committed
777 778
#ifdef CONFIG_NET_CLS_POLICE
	if (TC_U32_KEY(n->handle) && n->police) {
779 780
		if (qdisc_copy_stats(skb, &n->police->stats,
				     n->police->stats_lock))
Linus Torvalds's avatar
Linus Torvalds committed
781 782
			goto rtattr_failure;
	}
783
#endif
Linus Torvalds's avatar
Linus Torvalds committed
784 785 786 787 788 789 790 791
#endif
	return skb->len;

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

792
static struct tcf_proto_ops cls_u32_ops = {
793 794 795 796 797 798 799 800 801 802 803 804
	.next		=	NULL,
	.kind		=	"u32",
	.classify	=	u32_classify,
	.init		=	u32_init,
	.destroy	=	u32_destroy,
	.get		=	u32_get,
	.put		=	u32_put,
	.change		=	u32_change,
	.delete		=	u32_delete,
	.walk		=	u32_walk,
	.dump		=	u32_dump,
	.owner		=	THIS_MODULE,
Linus Torvalds's avatar
Linus Torvalds committed
805 806
};

807
static int __init init_u32(void)
Linus Torvalds's avatar
Linus Torvalds committed
808
{
809 810 811 812 813 814 815 816 817 818 819 820 821
	printk("u32 classifier\n");
#ifdef CONFIG_CLS_U32_PERF
	printk("    Perfomance counters on\n");
#endif
#ifdef CONFIG_NET_CLS_POLICE
	printk("    OLD policer on \n");
#endif
#ifdef CONFIG_NET_CLS_IND
	printk("    input device check on \n");
#endif
#ifdef CONFIG_NET_CLS_ACT
	printk("    Actions configured \n");
#endif
Linus Torvalds's avatar
Linus Torvalds committed
822 823 824
	return register_tcf_proto_ops(&cls_u32_ops);
}

825
static void __exit exit_u32(void) 
Linus Torvalds's avatar
Linus Torvalds committed
826 827 828
{
	unregister_tcf_proto_ops(&cls_u32_ops);
}
829 830 831

module_init(init_u32)
module_exit(exit_u32)
Linus Torvalds's avatar
Linus Torvalds committed
832
MODULE_LICENSE("GPL");