cls_u32.c 18.2 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 <linux/bitmap.h>
42
#include <net/netlink.h>
L
Linus Torvalds 已提交
43 44 45
#include <net/act_api.h>
#include <net/pkt_cls.h>

E
Eric Dumazet 已提交
46
struct tc_u_knode {
L
Linus Torvalds 已提交
47 48 49 50 51
	struct tc_u_knode	*next;
	u32			handle;
	struct tc_u_hnode	*ht_up;
	struct tcf_exts		exts;
#ifdef CONFIG_NET_CLS_IND
52
	int			ifindex;
L
Linus Torvalds 已提交
53 54 55 56 57
#endif
	u8			fshift;
	struct tcf_result	res;
	struct tc_u_hnode	*ht_down;
#ifdef CONFIG_CLS_U32_PERF
58
	struct tc_u32_pcnt __percpu *pf;
L
Linus Torvalds 已提交
59 60
#endif
#ifdef CONFIG_CLS_U32_MARK
61 62 63
	u32			val;
	u32			mask;
	u32 __percpu		*pcpu_success;
L
Linus Torvalds 已提交
64 65 66 67
#endif
	struct tc_u32_sel	sel;
};

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

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

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

	return h;
}

94
static int u32_classify(struct sk_buff *skb, const struct tcf_proto *tp, struct tcf_result *res)
L
Linus Torvalds 已提交
95 96 97
{
	struct {
		struct tc_u_knode *knode;
98
		unsigned int	  off;
L
Linus Torvalds 已提交
99 100
	} stack[TC_U32_MAXDEPTH];

101
	struct tc_u_hnode *ht = tp->root;
102
	unsigned int off = skb_network_offset(skb);
L
Linus Torvalds 已提交
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
	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
120
		__this_cpu_inc(n->pf->rcnt);
L
Linus Torvalds 已提交
121 122 123 124
		j = 0;
#endif

#ifdef CONFIG_CLS_U32_MARK
125
		if ((skb->mark & n->mask) != n->val) {
L
Linus Torvalds 已提交
126 127 128
			n = n->next;
			goto next_knode;
		} else {
129
			__this_cpu_inc(*n->pcpu_success);
L
Linus Torvalds 已提交
130 131 132
		}
#endif

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

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

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

				*res = n->res;
#ifdef CONFIG_NET_CLS_IND
158
				if (!tcf_match_indev(skb, n->ifindex)) {
L
Linus Torvalds 已提交
159 160 161 162 163
					n = n->next;
					goto next_knode;
				}
#endif
#ifdef CONFIG_CLS_U32_PERF
164
				__this_cpu_inc(n->pf->rhit);
L
Linus Torvalds 已提交
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
#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;
182
		stack[sdepth].off = off;
L
Linus Torvalds 已提交
183 184 185 186
		sdepth++;

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

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

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

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

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

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

deadloop:
235
	net_warn_ratelimited("cls_u32: dead loop\n");
L
Linus Torvalds 已提交
236 237 238
	return -1;
}

E
Eric Dumazet 已提交
239
static struct tc_u_hnode *
L
Linus Torvalds 已提交
240 241 242 243 244 245 246 247 248 249 250
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 已提交
251
static struct tc_u_knode *
L
Linus Torvalds 已提交
252 253
u32_lookup_key(struct tc_u_hnode *ht, u32 handle)
{
E
Eric Dumazet 已提交
254
	unsigned int sel;
L
Linus Torvalds 已提交
255 256 257 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
	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 已提交
299
	} while (--i > 0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20));
L
Linus Torvalds 已提交
300 301 302 303 304 305 306 307 308

	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;

309
	tp_c = tp->q->u32_node;
L
Linus Torvalds 已提交
310

311
	root_ht = kzalloc(sizeof(*root_ht), GFP_KERNEL);
L
Linus Torvalds 已提交
312 313 314 315 316 317 318 319 320
	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) {
321
		tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL);
L
Linus Torvalds 已提交
322 323 324 325 326
		if (tp_c == NULL) {
			kfree(root_ht);
			return -ENOBUFS;
		}
		tp_c->q = tp->q;
327
		tp->q->u32_node = tp_c;
L
Linus Torvalds 已提交
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
	}

	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
347
	free_percpu(n->pf);
L
Linus Torvalds 已提交
348 349 350 351 352
#endif
	kfree(n);
	return 0;
}

353
static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode *key)
L
Linus Torvalds 已提交
354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
{
	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;
			}
		}
	}
370
	WARN_ON(1);
L
Linus Torvalds 已提交
371 372 373 374 375 376
	return 0;
}

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

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

393
	WARN_ON(ht->refcnt);
L
Linus Torvalds 已提交
394 395 396 397 398 399 400 401 402 403 404

	u32_clear_hnode(tp, ht);

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

405
	WARN_ON(1);
L
Linus Torvalds 已提交
406 407 408 409 410 411
	return -ENOENT;
}

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

414
	WARN_ON(root_ht == NULL);
L
Linus Torvalds 已提交
415 416 417 418 419 420 421

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

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

422
		tp->q->u32_node = NULL;
L
Linus Torvalds 已提交
423

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

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

432
			WARN_ON(ht->refcnt != 0);
L
Linus Torvalds 已提交
433 434

			kfree(ht);
435
		}
L
Linus Torvalds 已提交
436 437 438 439 440 441 442 443 444

		kfree(tp_c);
	}

	tp->data = NULL;
}

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

	if (ht == NULL)
		return 0;

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

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

456 457
	if (ht->refcnt == 1) {
		ht->refcnt--;
L
Linus Torvalds 已提交
458
		u32_destroy_hnode(tp, ht);
459 460 461
	} else {
		return -EBUSY;
	}
L
Linus Torvalds 已提交
462 463 464 465

	return 0;
}

466
#define NR_U32_NODE (1<<12)
L
Linus Torvalds 已提交
467 468 469
static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle)
{
	struct tc_u_knode *n;
470 471 472 473 474
	unsigned long i;
	unsigned long *bitmap = kzalloc(BITS_TO_LONGS(NR_U32_NODE) * sizeof(unsigned long),
					GFP_KERNEL);
	if (!bitmap)
		return handle | 0xFFF;
L
Linus Torvalds 已提交
475

E
Eric Dumazet 已提交
476
	for (n = ht->ht[TC_U32_HASH(handle)]; n; n = n->next)
477
		set_bit(TC_U32_NODE(n->handle), bitmap);
L
Linus Torvalds 已提交
478

479 480 481 482 483 484
	i = find_next_zero_bit(bitmap, NR_U32_NODE, 0x800);
	if (i >= NR_U32_NODE)
		i = find_next_zero_bit(bitmap, NR_U32_NODE, 1);

	kfree(bitmap);
	return handle | (i >= NR_U32_NODE ? 0xFFF : i);
L
Linus Torvalds 已提交
485 486
}

487 488 489 490 491 492 493 494 495 496
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) },
};

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

505
	tcf_exts_init(&e, TCA_U32_ACT, TCA_U32_POLICE);
506
	err = tcf_exts_validate(net, tp, tb, est, &e, ovr);
L
Linus Torvalds 已提交
507 508 509 510
	if (err < 0)
		return err;

	err = -EINVAL;
511
	if (tb[TCA_U32_LINK]) {
512
		u32 handle = nla_get_u32(tb[TCA_U32_LINK]);
513
		struct tc_u_hnode *ht_down = NULL, *ht_old;
L
Linus Torvalds 已提交
514 515 516 517 518 519 520 521 522 523 524 525 526

		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);
527 528
		ht_old = n->ht_down;
		n->ht_down = ht_down;
L
Linus Torvalds 已提交
529 530
		tcf_tree_unlock(tp);

531 532
		if (ht_old)
			ht_old->refcnt--;
L
Linus Torvalds 已提交
533
	}
534
	if (tb[TCA_U32_CLASSID]) {
535
		n->res.classid = nla_get_u32(tb[TCA_U32_CLASSID]);
L
Linus Torvalds 已提交
536 537 538 539
		tcf_bind_filter(tp, &n->res, base);
	}

#ifdef CONFIG_NET_CLS_IND
540
	if (tb[TCA_U32_INDEV]) {
541 542 543
		int ret;
		ret = tcf_change_indev(net, tb[TCA_U32_INDEV]);
		if (ret < 0)
L
Linus Torvalds 已提交
544
			goto errout;
545
		n->ifindex = ret;
L
Linus Torvalds 已提交
546 547 548 549 550 551 552 553 554 555
	}
#endif
	tcf_exts_change(tp, &n->exts, &e);

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

556
static int u32_change(struct net *net, struct sk_buff *in_skb,
557
		      struct tcf_proto *tp, unsigned long base, u32 handle,
558
		      struct nlattr **tca,
559
		      unsigned long *arg, bool ovr)
L
Linus Torvalds 已提交
560 561 562 563 564
{
	struct tc_u_common *tp_c = tp->data;
	struct tc_u_hnode *ht;
	struct tc_u_knode *n;
	struct tc_u32_sel *s;
565 566
	struct nlattr *opt = tca[TCA_OPTIONS];
	struct nlattr *tb[TCA_U32_MAX + 1];
L
Linus Torvalds 已提交
567 568
	u32 htid;
	int err;
569 570 571
#ifdef CONFIG_CLS_U32_PERF
	size_t size;
#endif
L
Linus Torvalds 已提交
572 573 574 575

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

576
	err = nla_parse_nested(tb, TCA_U32_MAX, opt, u32_policy);
577 578
	if (err < 0)
		return err;
L
Linus Torvalds 已提交
579

E
Eric Dumazet 已提交
580 581
	n = (struct tc_u_knode *)*arg;
	if (n) {
L
Linus Torvalds 已提交
582 583 584
		if (TC_U32_KEY(n->handle) == 0)
			return -EINVAL;

585
		return u32_set_parms(net, tp, base, n->ht_up, n, tb,
586
				     tca[TCA_RATE], ovr);
L
Linus Torvalds 已提交
587 588
	}

589
	if (tb[TCA_U32_DIVISOR]) {
E
Eric Dumazet 已提交
590
		unsigned int divisor = nla_get_u32(tb[TCA_U32_DIVISOR]);
L
Linus Torvalds 已提交
591 592 593 594 595 596 597 598 599 600

		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 已提交
601
		ht = kzalloc(sizeof(*ht) + divisor*sizeof(void *), GFP_KERNEL);
L
Linus Torvalds 已提交
602 603 604
		if (ht == NULL)
			return -ENOBUFS;
		ht->tp_c = tp_c;
605
		ht->refcnt = 1;
L
Linus Torvalds 已提交
606 607 608 609 610 611 612 613 614
		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;
	}

615
	if (tb[TCA_U32_HASH]) {
616
		htid = nla_get_u32(tb[TCA_U32_HASH]);
L
Linus Torvalds 已提交
617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639
		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);

640
	if (tb[TCA_U32_SEL] == NULL)
L
Linus Torvalds 已提交
641 642
		return -EINVAL;

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

645
	n = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
L
Linus Torvalds 已提交
646 647 648 649
	if (n == NULL)
		return -ENOBUFS;

#ifdef CONFIG_CLS_U32_PERF
650 651 652
	size = sizeof(struct tc_u32_pcnt) + s->nkeys * sizeof(u64);
	n->pf = __alloc_percpu(size, __alignof__(struct tc_u32_pcnt));
	if (!n->pf) {
L
Linus Torvalds 已提交
653 654 655 656 657 658 659 660
		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;
661
	n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
662
	tcf_exts_init(&n->exts, TCA_U32_ACT, TCA_U32_POLICE);
L
Linus Torvalds 已提交
663 664

#ifdef CONFIG_CLS_U32_MARK
665 666
	n->pcpu_success = alloc_percpu(u32);

667
	if (tb[TCA_U32_MARK]) {
L
Linus Torvalds 已提交
668 669
		struct tc_u32_mark *mark;

670
		mark = nla_data(tb[TCA_U32_MARK]);
671 672
		n->val = mark->val;
		n->mask = mark->mask;
L
Linus Torvalds 已提交
673 674 675
	}
#endif

676
	err = u32_set_parms(net, tp, base, ht, n, tb, tca[TCA_RATE], ovr);
L
Linus Torvalds 已提交
677 678 679 680 681 682 683
	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;
684
		tcf_tree_lock(tp);
L
Linus Torvalds 已提交
685
		*ins = n;
686
		tcf_tree_unlock(tp);
L
Linus Torvalds 已提交
687 688 689 690 691

		*arg = (unsigned long)n;
		return 0;
	}
#ifdef CONFIG_CLS_U32_PERF
692
	kfree(n->pf);
L
Linus Torvalds 已提交
693 694 695 696 697 698 699 700 701 702
#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 已提交
703
	unsigned int h;
L
Linus Torvalds 已提交
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

	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++;
			}
		}
	}
}

734
static int u32_dump(struct net *net, struct tcf_proto *tp, unsigned long fh,
L
Linus Torvalds 已提交
735 736
		     struct sk_buff *skb, struct tcmsg *t)
{
E
Eric Dumazet 已提交
737
	struct tc_u_knode *n = (struct tc_u_knode *)fh;
738
	struct nlattr *nest;
L
Linus Torvalds 已提交
739 740 741 742 743 744

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

	t->tcm_handle = n->handle;

745 746 747
	nest = nla_nest_start(skb, TCA_OPTIONS);
	if (nest == NULL)
		goto nla_put_failure;
L
Linus Torvalds 已提交
748 749

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

753 754
		if (nla_put_u32(skb, TCA_U32_DIVISOR, divisor))
			goto nla_put_failure;
L
Linus Torvalds 已提交
755
	} else {
756 757 758 759 760
#ifdef CONFIG_CLS_U32_PERF
		struct tc_u32_pcnt *gpf;
#endif
		int cpu;

761 762 763 764
		if (nla_put(skb, TCA_U32_SEL,
			    sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
			    &n->sel))
			goto nla_put_failure;
L
Linus Torvalds 已提交
765 766
		if (n->ht_up) {
			u32 htid = n->handle & 0xFFFFF000;
767 768
			if (nla_put_u32(skb, TCA_U32_HASH, htid))
				goto nla_put_failure;
L
Linus Torvalds 已提交
769
		}
770 771 772 773 774 775
		if (n->res.classid &&
		    nla_put_u32(skb, TCA_U32_CLASSID, n->res.classid))
			goto nla_put_failure;
		if (n->ht_down &&
		    nla_put_u32(skb, TCA_U32_LINK, n->ht_down->handle))
			goto nla_put_failure;
L
Linus Torvalds 已提交
776 777

#ifdef CONFIG_CLS_U32_MARK
778 779 780 781 782 783 784 785 786 787 788 789 790 791
		if ((n->val || n->mask)) {
			struct tc_u32_mark mark = {.val = n->val,
						   .mask = n->mask,
						   .success = 0};

			for_each_possible_cpu(cpu) {
				__u32 cnt = *per_cpu_ptr(n->pcpu_success, cpu);

				mark.success += cnt;
			}

			if (nla_put(skb, TCA_U32_MARK, sizeof(mark), &mark))
				goto nla_put_failure;
		}
L
Linus Torvalds 已提交
792 793
#endif

794
		if (tcf_exts_dump(skb, &n->exts) < 0)
795
			goto nla_put_failure;
L
Linus Torvalds 已提交
796 797

#ifdef CONFIG_NET_CLS_IND
798 799 800 801 802 803
		if (n->ifindex) {
			struct net_device *dev;
			dev = __dev_get_by_index(net, n->ifindex);
			if (dev && nla_put_string(skb, TCA_U32_INDEV, dev->name))
				goto nla_put_failure;
		}
L
Linus Torvalds 已提交
804 805
#endif
#ifdef CONFIG_CLS_U32_PERF
806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821
		gpf = kzalloc(sizeof(struct tc_u32_pcnt) +
			      n->sel.nkeys * sizeof(u64),
			      GFP_KERNEL);
		if (!gpf)
			goto nla_put_failure;

		for_each_possible_cpu(cpu) {
			int i;
			struct tc_u32_pcnt *pf = per_cpu_ptr(n->pf, cpu);

			gpf->rcnt += pf->rcnt;
			gpf->rhit += pf->rhit;
			for (i = 0; i < n->sel.nkeys; i++)
				gpf->kcnts[i] += pf->kcnts[i];
		}

822 823
		if (nla_put(skb, TCA_U32_PCNT,
			    sizeof(struct tc_u32_pcnt) + n->sel.nkeys*sizeof(u64),
824 825
			    gpf)) {
			kfree(gpf);
826
			goto nla_put_failure;
827 828
		}
		kfree(gpf);
L
Linus Torvalds 已提交
829 830 831
#endif
	}

832 833
	nla_nest_end(skb, nest);

L
Linus Torvalds 已提交
834
	if (TC_U32_KEY(n->handle))
835
		if (tcf_exts_dump_stats(skb, &n->exts) < 0)
836
			goto nla_put_failure;
L
Linus Torvalds 已提交
837 838
	return skb->len;

839
nla_put_failure:
840
	nla_nest_cancel(skb, nest);
L
Linus Torvalds 已提交
841 842 843
	return -1;
}

844
static struct tcf_proto_ops cls_u32_ops __read_mostly = {
L
Linus Torvalds 已提交
845 846 847 848 849 850 851 852 853 854 855 856 857 858 859
	.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)
{
860
	pr_info("u32 classifier\n");
L
Linus Torvalds 已提交
861
#ifdef CONFIG_CLS_U32_PERF
862
	pr_info("    Performance counters on\n");
L
Linus Torvalds 已提交
863 864
#endif
#ifdef CONFIG_NET_CLS_IND
865
	pr_info("    input device check on\n");
L
Linus Torvalds 已提交
866 867
#endif
#ifdef CONFIG_NET_CLS_ACT
868
	pr_info("    Actions configured\n");
L
Linus Torvalds 已提交
869 870 871 872
#endif
	return register_tcf_proto_ops(&cls_u32_ops);
}

873
static void __exit exit_u32(void)
L
Linus Torvalds 已提交
874 875 876 877 878 879 880
{
	unregister_tcf_proto_ops(&cls_u32_ops);
}

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