cls_u32.c 16.7 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
/*
 * 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.
 *
 *	JHS: We should remove the CONFIG_NET_CLS_IND from here
 *	eventually when the meta match extension is made available
 *
 *	nfmark match added by Catalin(ux aka Dino) BOIE <catab at umbrella.ro>
 */

#include <linux/module.h>
34
#include <linux/slab.h>
L
Linus Torvalds 已提交
35 36 37 38 39 40
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/rtnetlink.h>
#include <linux/skbuff.h>
41
#include <net/netlink.h>
L
Linus Torvalds 已提交
42 43 44
#include <net/act_api.h>
#include <net/pkt_cls.h>

E
Eric Dumazet 已提交
45
struct tc_u_knode {
L
Linus Torvalds 已提交
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
	struct tc_u_knode	*next;
	u32			handle;
	struct tc_u_hnode	*ht_up;
	struct tcf_exts		exts;
#ifdef CONFIG_NET_CLS_IND
	char                     indev[IFNAMSIZ];
#endif
	u8			fshift;
	struct tcf_result	res;
	struct tc_u_hnode	*ht_down;
#ifdef CONFIG_CLS_U32_PERF
	struct tc_u32_pcnt	*pf;
#endif
#ifdef CONFIG_CLS_U32_MARK
	struct tc_u32_mark	mark;
#endif
	struct tc_u32_sel	sel;
};

E
Eric Dumazet 已提交
65
struct tc_u_hnode {
L
Linus Torvalds 已提交
66 67 68 69 70
	struct tc_u_hnode	*next;
	u32			handle;
	u32			prio;
	struct tc_u_common	*tp_c;
	int			refcnt;
E
Eric Dumazet 已提交
71
	unsigned int		divisor;
L
Linus Torvalds 已提交
72 73 74
	struct tc_u_knode	*ht[1];
};

E
Eric Dumazet 已提交
75
struct tc_u_common {
L
Linus Torvalds 已提交
76 77 78 79 80 81
	struct tc_u_hnode	*hlist;
	struct Qdisc		*q;
	int			refcnt;
	u32			hgenerator;
};

82
static const struct tcf_ext_map u32_ext_map = {
L
Linus Torvalds 已提交
83 84 85 86
	.action = TCA_U32_ACT,
	.police = TCA_U32_POLICE
};

E
Eric Dumazet 已提交
87 88 89
static inline unsigned int u32_hash_fold(__be32 key,
					 const struct tc_u32_sel *sel,
					 u8 fshift)
L
Linus Torvalds 已提交
90
{
E
Eric Dumazet 已提交
91
	unsigned int h = ntohl(key & sel->hmask) >> fshift;
L
Linus Torvalds 已提交
92 93 94 95 96 97 98 99

	return h;
}

static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res)
{
	struct {
		struct tc_u_knode *knode;
100
		unsigned int	  off;
L
Linus Torvalds 已提交
101 102
	} stack[TC_U32_MAXDEPTH];

E
Eric Dumazet 已提交
103
	struct tc_u_hnode *ht = (struct tc_u_hnode *)tp->root;
104
	unsigned int off = skb_network_offset(skb);
L
Linus Torvalds 已提交
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
	struct tc_u_knode *n;
	int sdepth = 0;
	int off2 = 0;
	int sel = 0;
#ifdef CONFIG_CLS_U32_PERF
	int j;
#endif
	int i, r;

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

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

#ifdef CONFIG_CLS_U32_PERF
E
Eric Dumazet 已提交
122
		n->pf->rcnt += 1;
L
Linus Torvalds 已提交
123 124 125 126
		j = 0;
#endif

#ifdef CONFIG_CLS_U32_MARK
T
Thomas Graf 已提交
127
		if ((skb->mark & n->mark.mask) != n->mark.val) {
L
Linus Torvalds 已提交
128 129 130 131 132 133 134
			n = n->next;
			goto next_knode;
		} else {
			n->mark.success++;
		}
#endif

E
Eric Dumazet 已提交
135
		for (i = n->sel.nkeys; i > 0; i--, key++) {
S
stephen hemminger 已提交
136
			int toff = off + key->off + (off2 & key->offmask);
S
stephen hemminger 已提交
137
			__be32 *data, hdata;
138

D
Dan Carpenter 已提交
139
			if (skb_headroom(skb) + toff > INT_MAX)
S
stephen hemminger 已提交
140 141
				goto out;

S
stephen hemminger 已提交
142
			data = skb_header_pointer(skb, toff, 4, &hdata);
143 144 145
			if (!data)
				goto out;
			if ((*data ^ key->val) & key->mask) {
L
Linus Torvalds 已提交
146 147 148 149
				n = n->next;
				goto next_knode;
			}
#ifdef CONFIG_CLS_U32_PERF
E
Eric Dumazet 已提交
150
			n->pf->kcnts[j] += 1;
L
Linus Torvalds 已提交
151 152 153 154 155
			j++;
#endif
		}
		if (n->ht_down == NULL) {
check_terminal:
E
Eric Dumazet 已提交
156
			if (n->sel.flags & TC_U32_TERMINAL) {
L
Linus Torvalds 已提交
157 158 159 160 161 162 163 164 165

				*res = n->res;
#ifdef CONFIG_NET_CLS_IND
				if (!tcf_match_indev(skb, n->indev)) {
					n = n->next;
					goto next_knode;
				}
#endif
#ifdef CONFIG_CLS_U32_PERF
E
Eric Dumazet 已提交
166
				n->pf->rhit += 1;
L
Linus Torvalds 已提交
167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183
#endif
				r = tcf_exts_exec(skb, &n->exts, res);
				if (r < 0) {
					n = n->next;
					goto next_knode;
				}

				return r;
			}
			n = n->next;
			goto next_knode;
		}

		/* PUSH */
		if (sdepth >= TC_U32_MAXDEPTH)
			goto deadloop;
		stack[sdepth].knode = n;
184
		stack[sdepth].off = off;
L
Linus Torvalds 已提交
185 186 187 188
		sdepth++;

		ht = n->ht_down;
		sel = 0;
189
		if (ht->divisor) {
S
stephen hemminger 已提交
190
			__be32 *data, hdata;
191 192

			data = skb_header_pointer(skb, off + n->sel.hoff, 4,
S
stephen hemminger 已提交
193
						  &hdata);
194 195 196 197 198
			if (!data)
				goto out;
			sel = ht->divisor & u32_hash_fold(*data, &n->sel,
							  n->fshift);
		}
E
Eric Dumazet 已提交
199
		if (!(n->sel.flags & (TC_U32_VAROFFSET | TC_U32_OFFSET | TC_U32_EAT)))
L
Linus Torvalds 已提交
200 201
			goto next_ht;

E
Eric Dumazet 已提交
202
		if (n->sel.flags & (TC_U32_OFFSET | TC_U32_VAROFFSET)) {
L
Linus Torvalds 已提交
203
			off2 = n->sel.off + 3;
204
			if (n->sel.flags & TC_U32_VAROFFSET) {
S
stephen hemminger 已提交
205
				__be16 *data, hdata;
206 207 208

				data = skb_header_pointer(skb,
							  off + n->sel.offoff,
S
stephen hemminger 已提交
209
							  2, &hdata);
210 211 212 213 214
				if (!data)
					goto out;
				off2 += ntohs(n->sel.offmask & *data) >>
					n->sel.offshift;
			}
L
Linus Torvalds 已提交
215 216
			off2 &= ~3;
		}
E
Eric Dumazet 已提交
217
		if (n->sel.flags & TC_U32_EAT) {
218
			off += off2;
L
Linus Torvalds 已提交
219 220 221
			off2 = 0;
		}

222
		if (off < skb->len)
L
Linus Torvalds 已提交
223 224 225 226 227 228 229
			goto next_ht;
	}

	/* POP */
	if (sdepth--) {
		n = stack[sdepth].knode;
		ht = n->ht_up;
230
		off = stack[sdepth].off;
L
Linus Torvalds 已提交
231 232
		goto check_terminal;
	}
233
out:
L
Linus Torvalds 已提交
234 235 236 237
	return -1;

deadloop:
	if (net_ratelimit())
E
Eric Dumazet 已提交
238
		pr_warning("cls_u32: dead loop\n");
L
Linus Torvalds 已提交
239 240 241
	return -1;
}

E
Eric Dumazet 已提交
242
static struct tc_u_hnode *
L
Linus Torvalds 已提交
243 244 245 246 247 248 249 250 251 252 253
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;
}

E
Eric Dumazet 已提交
254
static struct tc_u_knode *
L
Linus Torvalds 已提交
255 256
u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
{
E
Eric Dumazet 已提交
257
	unsigned int sel;
L
Linus Torvalds 已提交
258 259 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 293 294 295 296 297 298 299 300 301
	struct tc_u_knode *n = NULL;

	sel = TC_U32_HASH(handle);
	if (sel > ht->divisor)
		goto out;

	for (n = ht->ht[sel]; n; n = n->next)
		if (n->handle == handle)
			break;
out:
	return n;
}


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;
E
Eric Dumazet 已提交
302
	} while (--i > 0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
L
Linus Torvalds 已提交
303 304 305 306 307 308 309 310 311

	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;

312
	tp_c = tp->q->u32_node;
L
Linus Torvalds 已提交
313

314
	root_ht = kzalloc(sizeof(*root_ht), GFP_KERNEL);
L
Linus Torvalds 已提交
315 316 317 318 319 320 321 322 323
	if (root_ht == NULL)
		return -ENOBUFS;

	root_ht->divisor = 0;
	root_ht->refcnt++;
	root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000;
	root_ht->prio = tp->prio;

	if (tp_c == NULL) {
324
		tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
L
Linus Torvalds 已提交
325 326 327 328 329
		if (tp_c == NULL) {
			kfree(root_ht);
			return -ENOBUFS;
		}
		tp_c->q = tp->q;
330
		tp->q->u32_node = tp_c;
L
Linus Torvalds 已提交
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349
	}

	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)
{
	tcf_unbind_filter(tp, &n->res);
	tcf_exts_destroy(tp, &n->exts);
	if (n->ht_down)
		n->ht_down->refcnt--;
#ifdef CONFIG_CLS_U32_PERF
350
	kfree(n->pf);
L
Linus Torvalds 已提交
351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
#endif
	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;
			}
		}
	}
373
	WARN_ON(1);
L
Linus Torvalds 已提交
374 375 376 377 378 379
	return 0;
}

static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht)
{
	struct tc_u_knode *n;
E
Eric Dumazet 已提交
380
	unsigned int h;
L
Linus Torvalds 已提交
381

E
Eric Dumazet 已提交
382
	for (h = 0; h <= ht->divisor; h++) {
L
Linus Torvalds 已提交
383 384 385 386 387 388 389 390 391 392 393 394 395
		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;

396
	WARN_ON(ht->refcnt);
L
Linus Torvalds 已提交
397 398 399 400 401 402 403 404 405 406 407

	u32_clear_hnode(tp, ht);

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

408
	WARN_ON(1);
L
Linus Torvalds 已提交
409 410 411 412 413 414
	return -ENOENT;
}

static void u32_destroy(struct tcf_proto *tp)
{
	struct tc_u_common *tp_c = tp->data;
415
	struct tc_u_hnode *root_ht = tp->root;
L
Linus Torvalds 已提交
416

417
	WARN_ON(root_ht == NULL);
L
Linus Torvalds 已提交
418 419 420 421 422 423 424

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

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

425
		tp->q->u32_node = NULL;
L
Linus Torvalds 已提交
426

427 428
		for (ht = tp_c->hlist; ht; ht = ht->next) {
			ht->refcnt--;
L
Linus Torvalds 已提交
429
			u32_clear_hnode(tp, ht);
430
		}
L
Linus Torvalds 已提交
431 432 433 434

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

435
			WARN_ON(ht->refcnt != 0);
L
Linus Torvalds 已提交
436 437

			kfree(ht);
438
		}
L
Linus Torvalds 已提交
439 440 441 442 443 444 445 446 447

		kfree(tp_c);
	}

	tp->data = NULL;
}

static int u32_delete(struct tcf_proto *tp, unsigned long arg)
{
E
Eric Dumazet 已提交
448
	struct tc_u_hnode *ht = (struct tc_u_hnode *)arg;
L
Linus Torvalds 已提交
449 450 451 452 453

	if (ht == NULL)
		return 0;

	if (TC_U32_KEY(ht->handle))
E
Eric Dumazet 已提交
454
		return u32_delete_key(tp, (struct tc_u_knode *)ht);
L
Linus Torvalds 已提交
455 456 457 458

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

459 460
	if (ht->refcnt == 1) {
		ht->refcnt--;
L
Linus Torvalds 已提交
461
		u32_destroy_hnode(tp, ht);
462 463 464
	} else {
		return -EBUSY;
	}
L
Linus Torvalds 已提交
465 466 467 468 469 470 471

	return 0;
}

static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
{
	struct tc_u_knode *n;
E
Eric Dumazet 已提交
472
	unsigned int i = 0x7FF;
L
Linus Torvalds 已提交
473

E
Eric Dumazet 已提交
474
	for (n = ht->ht[TC_U32_HASH(handle)]; n; n = n->next)
L
Linus Torvalds 已提交
475 476 477 478
		if (i < TC_U32_NODE(n->handle))
			i = TC_U32_NODE(n->handle);
	i++;

E
Eric Dumazet 已提交
479
	return handle | (i > 0xFFF ? 0xFFF : i);
L
Linus Torvalds 已提交
480 481
}

482 483 484 485 486 487 488 489 490 491
static const struct nla_policy u32_policy[TCA_U32_MAX + 1] = {
	[TCA_U32_CLASSID]	= { .type = NLA_U32 },
	[TCA_U32_HASH]		= { .type = NLA_U32 },
	[TCA_U32_LINK]		= { .type = NLA_U32 },
	[TCA_U32_DIVISOR]	= { .type = NLA_U32 },
	[TCA_U32_SEL]		= { .len = sizeof(struct tc_u32_sel) },
	[TCA_U32_INDEV]		= { .type = NLA_STRING, .len = IFNAMSIZ },
	[TCA_U32_MARK]		= { .len = sizeof(struct tc_u32_mark) },
};

L
Linus Torvalds 已提交
492 493
static int u32_set_parms(struct tcf_proto *tp, unsigned long base,
			 struct tc_u_hnode *ht,
494 495
			 struct tc_u_knode *n, struct nlattr **tb,
			 struct nlattr *est)
L
Linus Torvalds 已提交
496 497 498 499 500 501 502 503 504
{
	int err;
	struct tcf_exts e;

	err = tcf_exts_validate(tp, tb, est, &e, &u32_ext_map);
	if (err < 0)
		return err;

	err = -EINVAL;
505
	if (tb[TCA_U32_LINK]) {
506
		u32 handle = nla_get_u32(tb[TCA_U32_LINK]);
507
		struct tc_u_hnode *ht_down = NULL, *ht_old;
L
Linus Torvalds 已提交
508 509 510 511 512 513 514 515 516 517 518 519 520

		if (TC_U32_KEY(handle))
			goto errout;

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

			if (ht_down == NULL)
				goto errout;
			ht_down->refcnt++;
		}

		tcf_tree_lock(tp);
521 522
		ht_old = n->ht_down;
		n->ht_down = ht_down;
L
Linus Torvalds 已提交
523 524
		tcf_tree_unlock(tp);

525 526
		if (ht_old)
			ht_old->refcnt--;
L
Linus Torvalds 已提交
527
	}
528
	if (tb[TCA_U32_CLASSID]) {
529
		n->res.classid = nla_get_u32(tb[TCA_U32_CLASSID]);
L
Linus Torvalds 已提交
530 531 532 533
		tcf_bind_filter(tp, &n->res, base);
	}

#ifdef CONFIG_NET_CLS_IND
534 535
	if (tb[TCA_U32_INDEV]) {
		err = tcf_change_indev(tp, n->indev, tb[TCA_U32_INDEV]);
L
Linus Torvalds 已提交
536 537 538 539 540 541 542 543 544 545 546 547 548
		if (err < 0)
			goto errout;
	}
#endif
	tcf_exts_change(tp, &n->exts, &e);

	return 0;
errout:
	tcf_exts_destroy(tp, &e);
	return err;
}

static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
549
		      struct nlattr **tca,
L
Linus Torvalds 已提交
550 551 552 553 554 555
		      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;
556 557
	struct nlattr *opt = tca[TCA_OPTIONS];
	struct nlattr *tb[TCA_U32_MAX + 1];
L
Linus Torvalds 已提交
558 559 560 561 562 563
	u32 htid;
	int err;

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

564
	err = nla_parse_nested(tb, TCA_U32_MAX, opt, u32_policy);
565 566
	if (err < 0)
		return err;
L
Linus Torvalds 已提交
567

E
Eric Dumazet 已提交
568 569
	n = (struct tc_u_knode *)*arg;
	if (n) {
L
Linus Torvalds 已提交
570 571 572
		if (TC_U32_KEY(n->handle) == 0)
			return -EINVAL;

573
		return u32_set_parms(tp, base, n->ht_up, n, tb, tca[TCA_RATE]);
L
Linus Torvalds 已提交
574 575
	}

576
	if (tb[TCA_U32_DIVISOR]) {
E
Eric Dumazet 已提交
577
		unsigned int divisor = nla_get_u32(tb[TCA_U32_DIVISOR]);
L
Linus Torvalds 已提交
578 579 580 581 582 583 584 585 586 587

		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;
		}
E
Eric Dumazet 已提交
588
		ht = kzalloc(sizeof(*ht) + divisor*sizeof(void *), GFP_KERNEL);
L
Linus Torvalds 已提交
589 590 591
		if (ht == NULL)
			return -ENOBUFS;
		ht->tp_c = tp_c;
592
		ht->refcnt = 1;
L
Linus Torvalds 已提交
593 594 595 596 597 598 599 600 601
		ht->divisor = divisor;
		ht->handle = handle;
		ht->prio = tp->prio;
		ht->next = tp_c->hlist;
		tp_c->hlist = ht;
		*arg = (unsigned long)ht;
		return 0;
	}

602
	if (tb[TCA_U32_HASH]) {
603
		htid = nla_get_u32(tb[TCA_U32_HASH]);
L
Linus Torvalds 已提交
604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626
		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);

627
	if (tb[TCA_U32_SEL] == NULL)
L
Linus Torvalds 已提交
628 629
		return -EINVAL;

630
	s = nla_data(tb[TCA_U32_SEL]);
L
Linus Torvalds 已提交
631

632
	n = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
L
Linus Torvalds 已提交
633 634 635 636
	if (n == NULL)
		return -ENOBUFS;

#ifdef CONFIG_CLS_U32_PERF
637
	n->pf = kzalloc(sizeof(struct tc_u32_pcnt) + s->nkeys*sizeof(u64), GFP_KERNEL);
L
Linus Torvalds 已提交
638 639 640 641 642 643 644 645 646
	if (n->pf == NULL) {
		kfree(n);
		return -ENOBUFS;
	}
#endif

	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
	n->ht_up = ht;
	n->handle = handle;
647
	n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
L
Linus Torvalds 已提交
648 649

#ifdef CONFIG_CLS_U32_MARK
650
	if (tb[TCA_U32_MARK]) {
L
Linus Torvalds 已提交
651 652
		struct tc_u32_mark *mark;

653
		mark = nla_data(tb[TCA_U32_MARK]);
L
Linus Torvalds 已提交
654 655 656 657 658
		memcpy(&n->mark, mark, sizeof(struct tc_u32_mark));
		n->mark.success = 0;
	}
#endif

659
	err = u32_set_parms(tp, base, ht, n, tb, tca[TCA_RATE]);
L
Linus Torvalds 已提交
660 661 662 663 664 665 666
	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;
667
		tcf_tree_lock(tp);
L
Linus Torvalds 已提交
668
		*ins = n;
669
		tcf_tree_unlock(tp);
L
Linus Torvalds 已提交
670 671 672 673 674

		*arg = (unsigned long)n;
		return 0;
	}
#ifdef CONFIG_CLS_U32_PERF
675
	kfree(n->pf);
L
Linus Torvalds 已提交
676 677 678 679 680 681 682 683 684 685
#endif
	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;
E
Eric Dumazet 已提交
686
	unsigned int h;
L
Linus Torvalds 已提交
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

	if (arg->stop)
		return;

	for (ht = tp_c->hlist; ht; ht = ht->next) {
		if (ht->prio != tp->prio)
			continue;
		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)
{
E
Eric Dumazet 已提交
720
	struct tc_u_knode *n = (struct tc_u_knode *)fh;
721
	struct nlattr *nest;
L
Linus Torvalds 已提交
722 723 724 725 726 727

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

	t->tcm_handle = n->handle;

728 729 730
	nest = nla_nest_start(skb, TCA_OPTIONS);
	if (nest == NULL)
		goto nla_put_failure;
L
Linus Torvalds 已提交
731 732

	if (TC_U32_KEY(n->handle) == 0) {
E
Eric Dumazet 已提交
733 734 735
		struct tc_u_hnode *ht = (struct tc_u_hnode *)fh;
		u32 divisor = ht->divisor + 1;

736
		NLA_PUT_U32(skb, TCA_U32_DIVISOR, divisor);
L
Linus Torvalds 已提交
737
	} else {
738
		NLA_PUT(skb, TCA_U32_SEL,
L
Linus Torvalds 已提交
739 740 741 742
			sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
			&n->sel);
		if (n->ht_up) {
			u32 htid = n->handle & 0xFFFFF000;
743
			NLA_PUT_U32(skb, TCA_U32_HASH, htid);
L
Linus Torvalds 已提交
744 745
		}
		if (n->res.classid)
746
			NLA_PUT_U32(skb, TCA_U32_CLASSID, n->res.classid);
L
Linus Torvalds 已提交
747
		if (n->ht_down)
748
			NLA_PUT_U32(skb, TCA_U32_LINK, n->ht_down->handle);
L
Linus Torvalds 已提交
749 750 751

#ifdef CONFIG_CLS_U32_MARK
		if (n->mark.val || n->mark.mask)
752
			NLA_PUT(skb, TCA_U32_MARK, sizeof(n->mark), &n->mark);
L
Linus Torvalds 已提交
753 754 755
#endif

		if (tcf_exts_dump(skb, &n->exts, &u32_ext_map) < 0)
756
			goto nla_put_failure;
L
Linus Torvalds 已提交
757 758

#ifdef CONFIG_NET_CLS_IND
E
Eric Dumazet 已提交
759
		if (strlen(n->indev))
760
			NLA_PUT_STRING(skb, TCA_U32_INDEV, n->indev);
L
Linus Torvalds 已提交
761 762
#endif
#ifdef CONFIG_CLS_U32_PERF
763
		NLA_PUT(skb, TCA_U32_PCNT,
L
Linus Torvalds 已提交
764 765 766 767 768
		sizeof(struct tc_u32_pcnt) + n->sel.nkeys*sizeof(u64),
			n->pf);
#endif
	}

769 770
	nla_nest_end(skb, nest);

L
Linus Torvalds 已提交
771 772
	if (TC_U32_KEY(n->handle))
		if (tcf_exts_dump_stats(skb, &n->exts, &u32_ext_map) < 0)
773
			goto nla_put_failure;
L
Linus Torvalds 已提交
774 775
	return skb->len;

776
nla_put_failure:
777
	nla_nest_cancel(skb, nest);
L
Linus Torvalds 已提交
778 779 780
	return -1;
}

781
static struct tcf_proto_ops cls_u32_ops __read_mostly = {
L
Linus Torvalds 已提交
782 783 784 785 786 787 788 789 790 791 792 793 794 795 796
	.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,
};

static int __init init_u32(void)
{
797
	pr_info("u32 classifier\n");
L
Linus Torvalds 已提交
798
#ifdef CONFIG_CLS_U32_PERF
799
	pr_info("    Performance counters on\n");
L
Linus Torvalds 已提交
800 801
#endif
#ifdef CONFIG_NET_CLS_IND
802
	pr_info("    input device check on\n");
L
Linus Torvalds 已提交
803 804
#endif
#ifdef CONFIG_NET_CLS_ACT
805
	pr_info("    Actions configured\n");
L
Linus Torvalds 已提交
806 807 808 809
#endif
	return register_tcf_proto_ops(&cls_u32_ops);
}

810
static void __exit exit_u32(void)
L
Linus Torvalds 已提交
811 812 813 814 815 816 817
{
	unregister_tcf_proto_ops(&cls_u32_ops);
}

module_init(init_u32)
module_exit(exit_u32)
MODULE_LICENSE("GPL");