| Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* | 
 | 2 |  * net/sched/cls_u32.c	Ugly (or Universal) 32bit key Packet Classifier. | 
 | 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 |  *	The filters are packed to hash tables of key nodes | 
 | 12 |  *	with a set of 32bit key/mask pairs at every node. | 
 | 13 |  *	Nodes reference next level hash tables etc. | 
 | 14 |  * | 
 | 15 |  *	This scheme is the best universal classifier I managed to | 
 | 16 |  *	invent; it is not super-fast, but it is not slow (provided you | 
 | 17 |  *	program it correctly), and general enough.  And its relative | 
 | 18 |  *	speed grows as the number of rules becomes larger. | 
 | 19 |  * | 
 | 20 |  *	It seems that it represents the best middle point between | 
 | 21 |  *	speed and manageability both by human and by machine. | 
 | 22 |  * | 
 | 23 |  *	It is especially useful for link sharing combined with QoS; | 
 | 24 |  *	pure RSVP doesn't need such a general approach and can use | 
 | 25 |  *	much simpler (and faster) schemes, sort of cls_rsvp.c. | 
 | 26 |  * | 
 | 27 |  *	JHS: We should remove the CONFIG_NET_CLS_IND from here | 
 | 28 |  *	eventually when the meta match extension is made available | 
 | 29 |  * | 
 | 30 |  *	nfmark match added by Catalin(ux aka Dino) BOIE <catab at umbrella.ro> | 
 | 31 |  */ | 
 | 32 |  | 
 | 33 | #include <asm/uaccess.h> | 
 | 34 | #include <asm/system.h> | 
 | 35 | #include <linux/bitops.h> | 
 | 36 | #include <linux/config.h> | 
 | 37 | #include <linux/module.h> | 
 | 38 | #include <linux/types.h> | 
 | 39 | #include <linux/kernel.h> | 
 | 40 | #include <linux/sched.h> | 
 | 41 | #include <linux/string.h> | 
 | 42 | #include <linux/mm.h> | 
 | 43 | #include <linux/socket.h> | 
 | 44 | #include <linux/sockios.h> | 
 | 45 | #include <linux/in.h> | 
 | 46 | #include <linux/errno.h> | 
 | 47 | #include <linux/interrupt.h> | 
 | 48 | #include <linux/if_ether.h> | 
 | 49 | #include <linux/inet.h> | 
 | 50 | #include <linux/netdevice.h> | 
 | 51 | #include <linux/etherdevice.h> | 
 | 52 | #include <linux/notifier.h> | 
 | 53 | #include <linux/rtnetlink.h> | 
 | 54 | #include <net/ip.h> | 
 | 55 | #include <net/route.h> | 
 | 56 | #include <linux/skbuff.h> | 
 | 57 | #include <net/sock.h> | 
 | 58 | #include <net/act_api.h> | 
 | 59 | #include <net/pkt_cls.h> | 
 | 60 |  | 
 | 61 | struct tc_u_knode | 
 | 62 | { | 
 | 63 | 	struct tc_u_knode	*next; | 
 | 64 | 	u32			handle; | 
 | 65 | 	struct tc_u_hnode	*ht_up; | 
 | 66 | 	struct tcf_exts		exts; | 
 | 67 | #ifdef CONFIG_NET_CLS_IND | 
 | 68 | 	char                     indev[IFNAMSIZ]; | 
 | 69 | #endif | 
 | 70 | 	u8			fshift; | 
 | 71 | 	struct tcf_result	res; | 
 | 72 | 	struct tc_u_hnode	*ht_down; | 
 | 73 | #ifdef CONFIG_CLS_U32_PERF | 
 | 74 | 	struct tc_u32_pcnt	*pf; | 
 | 75 | #endif | 
 | 76 | #ifdef CONFIG_CLS_U32_MARK | 
 | 77 | 	struct tc_u32_mark	mark; | 
 | 78 | #endif | 
 | 79 | 	struct tc_u32_sel	sel; | 
 | 80 | }; | 
 | 81 |  | 
 | 82 | struct tc_u_hnode | 
 | 83 | { | 
 | 84 | 	struct tc_u_hnode	*next; | 
 | 85 | 	u32			handle; | 
 | 86 | 	u32			prio; | 
 | 87 | 	struct tc_u_common	*tp_c; | 
 | 88 | 	int			refcnt; | 
 | 89 | 	unsigned		divisor; | 
 | 90 | 	struct tc_u_knode	*ht[1]; | 
 | 91 | }; | 
 | 92 |  | 
 | 93 | struct tc_u_common | 
 | 94 | { | 
 | 95 | 	struct tc_u_common	*next; | 
 | 96 | 	struct tc_u_hnode	*hlist; | 
 | 97 | 	struct Qdisc		*q; | 
 | 98 | 	int			refcnt; | 
 | 99 | 	u32			hgenerator; | 
 | 100 | }; | 
 | 101 |  | 
 | 102 | static struct tcf_ext_map u32_ext_map = { | 
 | 103 | 	.action = TCA_U32_ACT, | 
 | 104 | 	.police = TCA_U32_POLICE | 
 | 105 | }; | 
 | 106 |  | 
 | 107 | static struct tc_u_common *u32_list; | 
 | 108 |  | 
 | 109 | static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fshift) | 
 | 110 | { | 
 | 111 | 	unsigned h = (key & sel->hmask)>>fshift; | 
 | 112 |  | 
 | 113 | 	return h; | 
 | 114 | } | 
 | 115 |  | 
 | 116 | static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res) | 
 | 117 | { | 
 | 118 | 	struct { | 
 | 119 | 		struct tc_u_knode *knode; | 
 | 120 | 		u8		  *ptr; | 
 | 121 | 	} stack[TC_U32_MAXDEPTH]; | 
 | 122 |  | 
 | 123 | 	struct tc_u_hnode *ht = (struct tc_u_hnode*)tp->root; | 
 | 124 | 	u8 *ptr = skb->nh.raw; | 
 | 125 | 	struct tc_u_knode *n; | 
 | 126 | 	int sdepth = 0; | 
 | 127 | 	int off2 = 0; | 
 | 128 | 	int sel = 0; | 
 | 129 | #ifdef CONFIG_CLS_U32_PERF | 
 | 130 | 	int j; | 
 | 131 | #endif | 
 | 132 | 	int i, r; | 
 | 133 |  | 
 | 134 | next_ht: | 
 | 135 | 	n = ht->ht[sel]; | 
 | 136 |  | 
 | 137 | next_knode: | 
 | 138 | 	if (n) { | 
 | 139 | 		struct tc_u32_key *key = n->sel.keys; | 
 | 140 |  | 
 | 141 | #ifdef CONFIG_CLS_U32_PERF | 
 | 142 | 		n->pf->rcnt +=1; | 
 | 143 | 		j = 0; | 
 | 144 | #endif | 
 | 145 |  | 
 | 146 | #ifdef CONFIG_CLS_U32_MARK | 
 | 147 | 		if ((skb->nfmark & n->mark.mask) != n->mark.val) { | 
 | 148 | 			n = n->next; | 
 | 149 | 			goto next_knode; | 
 | 150 | 		} else { | 
 | 151 | 			n->mark.success++; | 
 | 152 | 		} | 
 | 153 | #endif | 
 | 154 |  | 
 | 155 | 		for (i = n->sel.nkeys; i>0; i--, key++) { | 
 | 156 |  | 
 | 157 | 			if ((*(u32*)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) { | 
 | 158 | 				n = n->next; | 
 | 159 | 				goto next_knode; | 
 | 160 | 			} | 
 | 161 | #ifdef CONFIG_CLS_U32_PERF | 
 | 162 | 			n->pf->kcnts[j] +=1; | 
 | 163 | 			j++; | 
 | 164 | #endif | 
 | 165 | 		} | 
 | 166 | 		if (n->ht_down == NULL) { | 
 | 167 | check_terminal: | 
 | 168 | 			if (n->sel.flags&TC_U32_TERMINAL) { | 
 | 169 |  | 
 | 170 | 				*res = n->res; | 
 | 171 | #ifdef CONFIG_NET_CLS_IND | 
 | 172 | 				if (!tcf_match_indev(skb, n->indev)) { | 
 | 173 | 					n = n->next; | 
 | 174 | 					goto next_knode; | 
 | 175 | 				} | 
 | 176 | #endif | 
 | 177 | #ifdef CONFIG_CLS_U32_PERF | 
 | 178 | 				n->pf->rhit +=1; | 
 | 179 | #endif | 
 | 180 | 				r = tcf_exts_exec(skb, &n->exts, res); | 
 | 181 | 				if (r < 0) { | 
 | 182 | 					n = n->next; | 
 | 183 | 					goto next_knode; | 
 | 184 | 				} | 
 | 185 |  | 
 | 186 | 				return r; | 
 | 187 | 			} | 
 | 188 | 			n = n->next; | 
 | 189 | 			goto next_knode; | 
 | 190 | 		} | 
 | 191 |  | 
 | 192 | 		/* PUSH */ | 
 | 193 | 		if (sdepth >= TC_U32_MAXDEPTH) | 
 | 194 | 			goto deadloop; | 
 | 195 | 		stack[sdepth].knode = n; | 
 | 196 | 		stack[sdepth].ptr = ptr; | 
 | 197 | 		sdepth++; | 
 | 198 |  | 
 | 199 | 		ht = n->ht_down; | 
 | 200 | 		sel = 0; | 
 | 201 | 		if (ht->divisor) | 
 | 202 | 			sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel,n->fshift); | 
 | 203 |  | 
 | 204 | 		if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT))) | 
 | 205 | 			goto next_ht; | 
 | 206 |  | 
 | 207 | 		if (n->sel.flags&(TC_U32_OFFSET|TC_U32_VAROFFSET)) { | 
 | 208 | 			off2 = n->sel.off + 3; | 
 | 209 | 			if (n->sel.flags&TC_U32_VAROFFSET) | 
 | 210 | 				off2 += ntohs(n->sel.offmask & *(u16*)(ptr+n->sel.offoff)) >>n->sel.offshift; | 
 | 211 | 			off2 &= ~3; | 
 | 212 | 		} | 
 | 213 | 		if (n->sel.flags&TC_U32_EAT) { | 
 | 214 | 			ptr += off2; | 
 | 215 | 			off2 = 0; | 
 | 216 | 		} | 
 | 217 |  | 
 | 218 | 		if (ptr < skb->tail) | 
 | 219 | 			goto next_ht; | 
 | 220 | 	} | 
 | 221 |  | 
 | 222 | 	/* POP */ | 
 | 223 | 	if (sdepth--) { | 
 | 224 | 		n = stack[sdepth].knode; | 
 | 225 | 		ht = n->ht_up; | 
 | 226 | 		ptr = stack[sdepth].ptr; | 
 | 227 | 		goto check_terminal; | 
 | 228 | 	} | 
 | 229 | 	return -1; | 
 | 230 |  | 
 | 231 | deadloop: | 
 | 232 | 	if (net_ratelimit()) | 
 | 233 | 		printk("cls_u32: dead loop\n"); | 
 | 234 | 	return -1; | 
 | 235 | } | 
 | 236 |  | 
 | 237 | static __inline__ struct tc_u_hnode * | 
 | 238 | u32_lookup_ht(struct tc_u_common *tp_c, u32 handle) | 
 | 239 | { | 
 | 240 | 	struct tc_u_hnode *ht; | 
 | 241 |  | 
 | 242 | 	for (ht = tp_c->hlist; ht; ht = ht->next) | 
 | 243 | 		if (ht->handle == handle) | 
 | 244 | 			break; | 
 | 245 |  | 
 | 246 | 	return ht; | 
 | 247 | } | 
 | 248 |  | 
 | 249 | static __inline__ struct tc_u_knode * | 
 | 250 | u32_lookup_key(struct tc_u_hnode *ht, u32 handle) | 
 | 251 | { | 
 | 252 | 	unsigned sel; | 
 | 253 | 	struct tc_u_knode *n = NULL; | 
 | 254 |  | 
 | 255 | 	sel = TC_U32_HASH(handle); | 
 | 256 | 	if (sel > ht->divisor) | 
 | 257 | 		goto out; | 
 | 258 |  | 
 | 259 | 	for (n = ht->ht[sel]; n; n = n->next) | 
 | 260 | 		if (n->handle == handle) | 
 | 261 | 			break; | 
 | 262 | out: | 
 | 263 | 	return n; | 
 | 264 | } | 
 | 265 |  | 
 | 266 |  | 
 | 267 | static unsigned long u32_get(struct tcf_proto *tp, u32 handle) | 
 | 268 | { | 
 | 269 | 	struct tc_u_hnode *ht; | 
 | 270 | 	struct tc_u_common *tp_c = tp->data; | 
 | 271 |  | 
 | 272 | 	if (TC_U32_HTID(handle) == TC_U32_ROOT) | 
 | 273 | 		ht = tp->root; | 
 | 274 | 	else | 
 | 275 | 		ht = u32_lookup_ht(tp_c, TC_U32_HTID(handle)); | 
 | 276 |  | 
 | 277 | 	if (!ht) | 
 | 278 | 		return 0; | 
 | 279 |  | 
 | 280 | 	if (TC_U32_KEY(handle) == 0) | 
 | 281 | 		return (unsigned long)ht; | 
 | 282 |  | 
 | 283 | 	return (unsigned long)u32_lookup_key(ht, handle); | 
 | 284 | } | 
 | 285 |  | 
 | 286 | static void u32_put(struct tcf_proto *tp, unsigned long f) | 
 | 287 | { | 
 | 288 | } | 
 | 289 |  | 
 | 290 | static u32 gen_new_htid(struct tc_u_common *tp_c) | 
 | 291 | { | 
 | 292 | 	int i = 0x800; | 
 | 293 |  | 
 | 294 | 	do { | 
 | 295 | 		if (++tp_c->hgenerator == 0x7FF) | 
 | 296 | 			tp_c->hgenerator = 1; | 
 | 297 | 	} while (--i>0 && u32_lookup_ht(tp_c, (tp_c->hgenerator|0x800)<<20)); | 
 | 298 |  | 
 | 299 | 	return i > 0 ? (tp_c->hgenerator|0x800)<<20 : 0; | 
 | 300 | } | 
 | 301 |  | 
 | 302 | static int u32_init(struct tcf_proto *tp) | 
 | 303 | { | 
 | 304 | 	struct tc_u_hnode *root_ht; | 
 | 305 | 	struct tc_u_common *tp_c; | 
 | 306 |  | 
 | 307 | 	for (tp_c = u32_list; tp_c; tp_c = tp_c->next) | 
 | 308 | 		if (tp_c->q == tp->q) | 
 | 309 | 			break; | 
 | 310 |  | 
 | 311 | 	root_ht = kmalloc(sizeof(*root_ht), GFP_KERNEL); | 
 | 312 | 	if (root_ht == NULL) | 
 | 313 | 		return -ENOBUFS; | 
 | 314 |  | 
 | 315 | 	memset(root_ht, 0, sizeof(*root_ht)); | 
 | 316 | 	root_ht->divisor = 0; | 
 | 317 | 	root_ht->refcnt++; | 
 | 318 | 	root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000; | 
 | 319 | 	root_ht->prio = tp->prio; | 
 | 320 |  | 
 | 321 | 	if (tp_c == NULL) { | 
 | 322 | 		tp_c = kmalloc(sizeof(*tp_c), GFP_KERNEL); | 
 | 323 | 		if (tp_c == NULL) { | 
 | 324 | 			kfree(root_ht); | 
 | 325 | 			return -ENOBUFS; | 
 | 326 | 		} | 
 | 327 | 		memset(tp_c, 0, sizeof(*tp_c)); | 
 | 328 | 		tp_c->q = tp->q; | 
 | 329 | 		tp_c->next = u32_list; | 
 | 330 | 		u32_list = tp_c; | 
 | 331 | 	} | 
 | 332 |  | 
 | 333 | 	tp_c->refcnt++; | 
 | 334 | 	root_ht->next = tp_c->hlist; | 
 | 335 | 	tp_c->hlist = root_ht; | 
 | 336 | 	root_ht->tp_c = tp_c; | 
 | 337 |  | 
 | 338 | 	tp->root = root_ht; | 
 | 339 | 	tp->data = tp_c; | 
 | 340 | 	return 0; | 
 | 341 | } | 
 | 342 |  | 
 | 343 | static int u32_destroy_key(struct tcf_proto *tp, struct tc_u_knode *n) | 
 | 344 | { | 
 | 345 | 	tcf_unbind_filter(tp, &n->res); | 
 | 346 | 	tcf_exts_destroy(tp, &n->exts); | 
 | 347 | 	if (n->ht_down) | 
 | 348 | 		n->ht_down->refcnt--; | 
 | 349 | #ifdef CONFIG_CLS_U32_PERF | 
| Patrick McHardy | 1ae39a4 | 2006-03-23 01:16:48 -0800 | [diff] [blame] | 350 | 	kfree(n->pf); | 
| Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 351 | #endif | 
 | 352 | 	kfree(n); | 
 | 353 | 	return 0; | 
 | 354 | } | 
 | 355 |  | 
 | 356 | static int u32_delete_key(struct tcf_proto *tp, struct tc_u_knode* key) | 
 | 357 | { | 
 | 358 | 	struct tc_u_knode **kp; | 
 | 359 | 	struct tc_u_hnode *ht = key->ht_up; | 
 | 360 |  | 
 | 361 | 	if (ht) { | 
 | 362 | 		for (kp = &ht->ht[TC_U32_HASH(key->handle)]; *kp; kp = &(*kp)->next) { | 
 | 363 | 			if (*kp == key) { | 
 | 364 | 				tcf_tree_lock(tp); | 
 | 365 | 				*kp = key->next; | 
 | 366 | 				tcf_tree_unlock(tp); | 
 | 367 |  | 
 | 368 | 				u32_destroy_key(tp, key); | 
 | 369 | 				return 0; | 
 | 370 | 			} | 
 | 371 | 		} | 
 | 372 | 	} | 
 | 373 | 	BUG_TRAP(0); | 
 | 374 | 	return 0; | 
 | 375 | } | 
 | 376 |  | 
 | 377 | static void u32_clear_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht) | 
 | 378 | { | 
 | 379 | 	struct tc_u_knode *n; | 
 | 380 | 	unsigned h; | 
 | 381 |  | 
 | 382 | 	for (h=0; h<=ht->divisor; h++) { | 
 | 383 | 		while ((n = ht->ht[h]) != NULL) { | 
 | 384 | 			ht->ht[h] = n->next; | 
 | 385 |  | 
 | 386 | 			u32_destroy_key(tp, n); | 
 | 387 | 		} | 
 | 388 | 	} | 
 | 389 | } | 
 | 390 |  | 
 | 391 | static int u32_destroy_hnode(struct tcf_proto *tp, struct tc_u_hnode *ht) | 
 | 392 | { | 
 | 393 | 	struct tc_u_common *tp_c = tp->data; | 
 | 394 | 	struct tc_u_hnode **hn; | 
 | 395 |  | 
 | 396 | 	BUG_TRAP(!ht->refcnt); | 
 | 397 |  | 
 | 398 | 	u32_clear_hnode(tp, ht); | 
 | 399 |  | 
 | 400 | 	for (hn = &tp_c->hlist; *hn; hn = &(*hn)->next) { | 
 | 401 | 		if (*hn == ht) { | 
 | 402 | 			*hn = ht->next; | 
 | 403 | 			kfree(ht); | 
 | 404 | 			return 0; | 
 | 405 | 		} | 
 | 406 | 	} | 
 | 407 |  | 
 | 408 | 	BUG_TRAP(0); | 
 | 409 | 	return -ENOENT; | 
 | 410 | } | 
 | 411 |  | 
 | 412 | static void u32_destroy(struct tcf_proto *tp) | 
 | 413 | { | 
 | 414 | 	struct tc_u_common *tp_c = tp->data; | 
 | 415 | 	struct tc_u_hnode *root_ht = xchg(&tp->root, NULL); | 
 | 416 |  | 
 | 417 | 	BUG_TRAP(root_ht != NULL); | 
 | 418 |  | 
 | 419 | 	if (root_ht && --root_ht->refcnt == 0) | 
 | 420 | 		u32_destroy_hnode(tp, root_ht); | 
 | 421 |  | 
 | 422 | 	if (--tp_c->refcnt == 0) { | 
 | 423 | 		struct tc_u_hnode *ht; | 
 | 424 | 		struct tc_u_common **tp_cp; | 
 | 425 |  | 
 | 426 | 		for (tp_cp = &u32_list; *tp_cp; tp_cp = &(*tp_cp)->next) { | 
 | 427 | 			if (*tp_cp == tp_c) { | 
 | 428 | 				*tp_cp = tp_c->next; | 
 | 429 | 				break; | 
 | 430 | 			} | 
 | 431 | 		} | 
 | 432 |  | 
 | 433 | 		for (ht=tp_c->hlist; ht; ht = ht->next) | 
 | 434 | 			u32_clear_hnode(tp, ht); | 
 | 435 |  | 
 | 436 | 		while ((ht = tp_c->hlist) != NULL) { | 
 | 437 | 			tp_c->hlist = ht->next; | 
 | 438 |  | 
 | 439 | 			BUG_TRAP(ht->refcnt == 0); | 
 | 440 |  | 
 | 441 | 			kfree(ht); | 
 | 442 | 		}; | 
 | 443 |  | 
 | 444 | 		kfree(tp_c); | 
 | 445 | 	} | 
 | 446 |  | 
 | 447 | 	tp->data = NULL; | 
 | 448 | } | 
 | 449 |  | 
 | 450 | static int u32_delete(struct tcf_proto *tp, unsigned long arg) | 
 | 451 | { | 
 | 452 | 	struct tc_u_hnode *ht = (struct tc_u_hnode*)arg; | 
 | 453 |  | 
 | 454 | 	if (ht == NULL) | 
 | 455 | 		return 0; | 
 | 456 |  | 
 | 457 | 	if (TC_U32_KEY(ht->handle)) | 
 | 458 | 		return u32_delete_key(tp, (struct tc_u_knode*)ht); | 
 | 459 |  | 
 | 460 | 	if (tp->root == ht) | 
 | 461 | 		return -EINVAL; | 
 | 462 |  | 
 | 463 | 	if (--ht->refcnt == 0) | 
 | 464 | 		u32_destroy_hnode(tp, ht); | 
 | 465 |  | 
 | 466 | 	return 0; | 
 | 467 | } | 
 | 468 |  | 
 | 469 | static u32 gen_new_kid(struct tc_u_hnode *ht, u32 handle) | 
 | 470 | { | 
 | 471 | 	struct tc_u_knode *n; | 
 | 472 | 	unsigned i = 0x7FF; | 
 | 473 |  | 
 | 474 | 	for (n=ht->ht[TC_U32_HASH(handle)]; n; n = n->next) | 
 | 475 | 		if (i < TC_U32_NODE(n->handle)) | 
 | 476 | 			i = TC_U32_NODE(n->handle); | 
 | 477 | 	i++; | 
 | 478 |  | 
 | 479 | 	return handle|(i>0xFFF ? 0xFFF : i); | 
 | 480 | } | 
 | 481 |  | 
 | 482 | static int u32_set_parms(struct tcf_proto *tp, unsigned long base, | 
 | 483 | 			 struct tc_u_hnode *ht, | 
 | 484 | 			 struct tc_u_knode *n, struct rtattr **tb, | 
 | 485 | 			 struct rtattr *est) | 
 | 486 | { | 
 | 487 | 	int err; | 
 | 488 | 	struct tcf_exts e; | 
 | 489 |  | 
 | 490 | 	err = tcf_exts_validate(tp, tb, est, &e, &u32_ext_map); | 
 | 491 | 	if (err < 0) | 
 | 492 | 		return err; | 
 | 493 |  | 
 | 494 | 	err = -EINVAL; | 
 | 495 | 	if (tb[TCA_U32_LINK-1]) { | 
 | 496 | 		u32 handle = *(u32*)RTA_DATA(tb[TCA_U32_LINK-1]); | 
 | 497 | 		struct tc_u_hnode *ht_down = NULL; | 
 | 498 |  | 
 | 499 | 		if (TC_U32_KEY(handle)) | 
 | 500 | 			goto errout; | 
 | 501 |  | 
 | 502 | 		if (handle) { | 
 | 503 | 			ht_down = u32_lookup_ht(ht->tp_c, handle); | 
 | 504 |  | 
 | 505 | 			if (ht_down == NULL) | 
 | 506 | 				goto errout; | 
 | 507 | 			ht_down->refcnt++; | 
 | 508 | 		} | 
 | 509 |  | 
 | 510 | 		tcf_tree_lock(tp); | 
 | 511 | 		ht_down = xchg(&n->ht_down, ht_down); | 
 | 512 | 		tcf_tree_unlock(tp); | 
 | 513 |  | 
 | 514 | 		if (ht_down) | 
 | 515 | 			ht_down->refcnt--; | 
 | 516 | 	} | 
 | 517 | 	if (tb[TCA_U32_CLASSID-1]) { | 
 | 518 | 		n->res.classid = *(u32*)RTA_DATA(tb[TCA_U32_CLASSID-1]); | 
 | 519 | 		tcf_bind_filter(tp, &n->res, base); | 
 | 520 | 	} | 
 | 521 |  | 
 | 522 | #ifdef CONFIG_NET_CLS_IND | 
 | 523 | 	if (tb[TCA_U32_INDEV-1]) { | 
 | 524 | 		int err = tcf_change_indev(tp, n->indev, tb[TCA_U32_INDEV-1]); | 
 | 525 | 		if (err < 0) | 
 | 526 | 			goto errout; | 
 | 527 | 	} | 
 | 528 | #endif | 
 | 529 | 	tcf_exts_change(tp, &n->exts, &e); | 
 | 530 |  | 
 | 531 | 	return 0; | 
 | 532 | errout: | 
 | 533 | 	tcf_exts_destroy(tp, &e); | 
 | 534 | 	return err; | 
 | 535 | } | 
 | 536 |  | 
 | 537 | static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle, | 
 | 538 | 		      struct rtattr **tca, | 
 | 539 | 		      unsigned long *arg) | 
 | 540 | { | 
 | 541 | 	struct tc_u_common *tp_c = tp->data; | 
 | 542 | 	struct tc_u_hnode *ht; | 
 | 543 | 	struct tc_u_knode *n; | 
 | 544 | 	struct tc_u32_sel *s; | 
 | 545 | 	struct rtattr *opt = tca[TCA_OPTIONS-1]; | 
 | 546 | 	struct rtattr *tb[TCA_U32_MAX]; | 
 | 547 | 	u32 htid; | 
 | 548 | 	int err; | 
 | 549 |  | 
 | 550 | 	if (opt == NULL) | 
 | 551 | 		return handle ? -EINVAL : 0; | 
 | 552 |  | 
 | 553 | 	if (rtattr_parse_nested(tb, TCA_U32_MAX, opt) < 0) | 
 | 554 | 		return -EINVAL; | 
 | 555 |  | 
 | 556 | 	if ((n = (struct tc_u_knode*)*arg) != NULL) { | 
 | 557 | 		if (TC_U32_KEY(n->handle) == 0) | 
 | 558 | 			return -EINVAL; | 
 | 559 |  | 
 | 560 | 		return u32_set_parms(tp, base, n->ht_up, n, tb, tca[TCA_RATE-1]); | 
 | 561 | 	} | 
 | 562 |  | 
 | 563 | 	if (tb[TCA_U32_DIVISOR-1]) { | 
 | 564 | 		unsigned divisor = *(unsigned*)RTA_DATA(tb[TCA_U32_DIVISOR-1]); | 
 | 565 |  | 
 | 566 | 		if (--divisor > 0x100) | 
 | 567 | 			return -EINVAL; | 
 | 568 | 		if (TC_U32_KEY(handle)) | 
 | 569 | 			return -EINVAL; | 
 | 570 | 		if (handle == 0) { | 
 | 571 | 			handle = gen_new_htid(tp->data); | 
 | 572 | 			if (handle == 0) | 
 | 573 | 				return -ENOMEM; | 
 | 574 | 		} | 
 | 575 | 		ht = kmalloc(sizeof(*ht) + divisor*sizeof(void*), GFP_KERNEL); | 
 | 576 | 		if (ht == NULL) | 
 | 577 | 			return -ENOBUFS; | 
 | 578 | 		memset(ht, 0, sizeof(*ht) + divisor*sizeof(void*)); | 
 | 579 | 		ht->tp_c = tp_c; | 
 | 580 | 		ht->refcnt = 0; | 
 | 581 | 		ht->divisor = divisor; | 
 | 582 | 		ht->handle = handle; | 
 | 583 | 		ht->prio = tp->prio; | 
 | 584 | 		ht->next = tp_c->hlist; | 
 | 585 | 		tp_c->hlist = ht; | 
 | 586 | 		*arg = (unsigned long)ht; | 
 | 587 | 		return 0; | 
 | 588 | 	} | 
 | 589 |  | 
 | 590 | 	if (tb[TCA_U32_HASH-1]) { | 
 | 591 | 		htid = *(unsigned*)RTA_DATA(tb[TCA_U32_HASH-1]); | 
 | 592 | 		if (TC_U32_HTID(htid) == TC_U32_ROOT) { | 
 | 593 | 			ht = tp->root; | 
 | 594 | 			htid = ht->handle; | 
 | 595 | 		} else { | 
 | 596 | 			ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid)); | 
 | 597 | 			if (ht == NULL) | 
 | 598 | 				return -EINVAL; | 
 | 599 | 		} | 
 | 600 | 	} else { | 
 | 601 | 		ht = tp->root; | 
 | 602 | 		htid = ht->handle; | 
 | 603 | 	} | 
 | 604 |  | 
 | 605 | 	if (ht->divisor < TC_U32_HASH(htid)) | 
 | 606 | 		return -EINVAL; | 
 | 607 |  | 
 | 608 | 	if (handle) { | 
 | 609 | 		if (TC_U32_HTID(handle) && TC_U32_HTID(handle^htid)) | 
 | 610 | 			return -EINVAL; | 
 | 611 | 		handle = htid | TC_U32_NODE(handle); | 
 | 612 | 	} else | 
 | 613 | 		handle = gen_new_kid(ht, htid); | 
 | 614 |  | 
 | 615 | 	if (tb[TCA_U32_SEL-1] == 0 || | 
 | 616 | 	    RTA_PAYLOAD(tb[TCA_U32_SEL-1]) < sizeof(struct tc_u32_sel)) | 
 | 617 | 		return -EINVAL; | 
 | 618 |  | 
 | 619 | 	s = RTA_DATA(tb[TCA_U32_SEL-1]); | 
 | 620 |  | 
 | 621 | 	n = kmalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL); | 
 | 622 | 	if (n == NULL) | 
 | 623 | 		return -ENOBUFS; | 
 | 624 |  | 
 | 625 | 	memset(n, 0, sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key)); | 
 | 626 | #ifdef CONFIG_CLS_U32_PERF | 
 | 627 | 	n->pf = kmalloc(sizeof(struct tc_u32_pcnt) + s->nkeys*sizeof(u64), GFP_KERNEL); | 
 | 628 | 	if (n->pf == NULL) { | 
 | 629 | 		kfree(n); | 
 | 630 | 		return -ENOBUFS; | 
 | 631 | 	} | 
 | 632 | 	memset(n->pf, 0, sizeof(struct tc_u32_pcnt) + s->nkeys*sizeof(u64)); | 
 | 633 | #endif | 
 | 634 |  | 
 | 635 | 	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key)); | 
 | 636 | 	n->ht_up = ht; | 
 | 637 | 	n->handle = handle; | 
 | 638 | { | 
 | 639 | 	u8 i = 0; | 
 | 640 | 	u32 mask = s->hmask; | 
 | 641 | 	if (mask) { | 
 | 642 | 		while (!(mask & 1)) { | 
 | 643 | 			i++; | 
 | 644 | 			mask>>=1; | 
 | 645 | 		} | 
 | 646 | 	} | 
 | 647 | 	n->fshift = i; | 
 | 648 | } | 
 | 649 |  | 
 | 650 | #ifdef CONFIG_CLS_U32_MARK | 
 | 651 | 	if (tb[TCA_U32_MARK-1]) { | 
 | 652 | 		struct tc_u32_mark *mark; | 
 | 653 |  | 
 | 654 | 		if (RTA_PAYLOAD(tb[TCA_U32_MARK-1]) < sizeof(struct tc_u32_mark)) { | 
 | 655 | #ifdef CONFIG_CLS_U32_PERF | 
 | 656 | 			kfree(n->pf); | 
 | 657 | #endif | 
 | 658 | 			kfree(n); | 
 | 659 | 			return -EINVAL; | 
 | 660 | 		} | 
 | 661 | 		mark = RTA_DATA(tb[TCA_U32_MARK-1]); | 
 | 662 | 		memcpy(&n->mark, mark, sizeof(struct tc_u32_mark)); | 
 | 663 | 		n->mark.success = 0; | 
 | 664 | 	} | 
 | 665 | #endif | 
 | 666 |  | 
 | 667 | 	err = u32_set_parms(tp, base, ht, n, tb, tca[TCA_RATE-1]); | 
 | 668 | 	if (err == 0) { | 
 | 669 | 		struct tc_u_knode **ins; | 
 | 670 | 		for (ins = &ht->ht[TC_U32_HASH(handle)]; *ins; ins = &(*ins)->next) | 
 | 671 | 			if (TC_U32_NODE(handle) < TC_U32_NODE((*ins)->handle)) | 
 | 672 | 				break; | 
 | 673 |  | 
 | 674 | 		n->next = *ins; | 
 | 675 | 		wmb(); | 
 | 676 | 		*ins = n; | 
 | 677 |  | 
 | 678 | 		*arg = (unsigned long)n; | 
 | 679 | 		return 0; | 
 | 680 | 	} | 
 | 681 | #ifdef CONFIG_CLS_U32_PERF | 
| Patrick McHardy | 1ae39a4 | 2006-03-23 01:16:48 -0800 | [diff] [blame] | 682 | 	kfree(n->pf); | 
| Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 683 | #endif | 
 | 684 | 	kfree(n); | 
 | 685 | 	return err; | 
 | 686 | } | 
 | 687 |  | 
 | 688 | static void u32_walk(struct tcf_proto *tp, struct tcf_walker *arg) | 
 | 689 | { | 
 | 690 | 	struct tc_u_common *tp_c = tp->data; | 
 | 691 | 	struct tc_u_hnode *ht; | 
 | 692 | 	struct tc_u_knode *n; | 
 | 693 | 	unsigned h; | 
 | 694 |  | 
 | 695 | 	if (arg->stop) | 
 | 696 | 		return; | 
 | 697 |  | 
 | 698 | 	for (ht = tp_c->hlist; ht; ht = ht->next) { | 
 | 699 | 		if (ht->prio != tp->prio) | 
 | 700 | 			continue; | 
 | 701 | 		if (arg->count >= arg->skip) { | 
 | 702 | 			if (arg->fn(tp, (unsigned long)ht, arg) < 0) { | 
 | 703 | 				arg->stop = 1; | 
 | 704 | 				return; | 
 | 705 | 			} | 
 | 706 | 		} | 
 | 707 | 		arg->count++; | 
 | 708 | 		for (h = 0; h <= ht->divisor; h++) { | 
 | 709 | 			for (n = ht->ht[h]; n; n = n->next) { | 
 | 710 | 				if (arg->count < arg->skip) { | 
 | 711 | 					arg->count++; | 
 | 712 | 					continue; | 
 | 713 | 				} | 
 | 714 | 				if (arg->fn(tp, (unsigned long)n, arg) < 0) { | 
 | 715 | 					arg->stop = 1; | 
 | 716 | 					return; | 
 | 717 | 				} | 
 | 718 | 				arg->count++; | 
 | 719 | 			} | 
 | 720 | 		} | 
 | 721 | 	} | 
 | 722 | } | 
 | 723 |  | 
 | 724 | static int u32_dump(struct tcf_proto *tp, unsigned long fh, | 
 | 725 | 		     struct sk_buff *skb, struct tcmsg *t) | 
 | 726 | { | 
 | 727 | 	struct tc_u_knode *n = (struct tc_u_knode*)fh; | 
 | 728 | 	unsigned char	 *b = skb->tail; | 
 | 729 | 	struct rtattr *rta; | 
 | 730 |  | 
 | 731 | 	if (n == NULL) | 
 | 732 | 		return skb->len; | 
 | 733 |  | 
 | 734 | 	t->tcm_handle = n->handle; | 
 | 735 |  | 
 | 736 | 	rta = (struct rtattr*)b; | 
 | 737 | 	RTA_PUT(skb, TCA_OPTIONS, 0, NULL); | 
 | 738 |  | 
 | 739 | 	if (TC_U32_KEY(n->handle) == 0) { | 
 | 740 | 		struct tc_u_hnode *ht = (struct tc_u_hnode*)fh; | 
 | 741 | 		u32 divisor = ht->divisor+1; | 
 | 742 | 		RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor); | 
 | 743 | 	} else { | 
 | 744 | 		RTA_PUT(skb, TCA_U32_SEL, | 
 | 745 | 			sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key), | 
 | 746 | 			&n->sel); | 
 | 747 | 		if (n->ht_up) { | 
 | 748 | 			u32 htid = n->handle & 0xFFFFF000; | 
 | 749 | 			RTA_PUT(skb, TCA_U32_HASH, 4, &htid); | 
 | 750 | 		} | 
 | 751 | 		if (n->res.classid) | 
 | 752 | 			RTA_PUT(skb, TCA_U32_CLASSID, 4, &n->res.classid); | 
 | 753 | 		if (n->ht_down) | 
 | 754 | 			RTA_PUT(skb, TCA_U32_LINK, 4, &n->ht_down->handle); | 
 | 755 |  | 
 | 756 | #ifdef CONFIG_CLS_U32_MARK | 
 | 757 | 		if (n->mark.val || n->mark.mask) | 
 | 758 | 			RTA_PUT(skb, TCA_U32_MARK, sizeof(n->mark), &n->mark); | 
 | 759 | #endif | 
 | 760 |  | 
 | 761 | 		if (tcf_exts_dump(skb, &n->exts, &u32_ext_map) < 0) | 
 | 762 | 			goto rtattr_failure; | 
 | 763 |  | 
 | 764 | #ifdef CONFIG_NET_CLS_IND | 
 | 765 | 		if(strlen(n->indev)) | 
 | 766 | 			RTA_PUT(skb, TCA_U32_INDEV, IFNAMSIZ, n->indev); | 
 | 767 | #endif | 
 | 768 | #ifdef CONFIG_CLS_U32_PERF | 
 | 769 | 		RTA_PUT(skb, TCA_U32_PCNT,  | 
 | 770 | 		sizeof(struct tc_u32_pcnt) + n->sel.nkeys*sizeof(u64), | 
 | 771 | 			n->pf); | 
 | 772 | #endif | 
 | 773 | 	} | 
 | 774 |  | 
 | 775 | 	rta->rta_len = skb->tail - b; | 
 | 776 | 	if (TC_U32_KEY(n->handle)) | 
 | 777 | 		if (tcf_exts_dump_stats(skb, &n->exts, &u32_ext_map) < 0) | 
 | 778 | 			goto rtattr_failure; | 
 | 779 | 	return skb->len; | 
 | 780 |  | 
 | 781 | rtattr_failure: | 
 | 782 | 	skb_trim(skb, b - skb->data); | 
 | 783 | 	return -1; | 
 | 784 | } | 
 | 785 |  | 
 | 786 | static struct tcf_proto_ops cls_u32_ops = { | 
 | 787 | 	.next		=	NULL, | 
 | 788 | 	.kind		=	"u32", | 
 | 789 | 	.classify	=	u32_classify, | 
 | 790 | 	.init		=	u32_init, | 
 | 791 | 	.destroy	=	u32_destroy, | 
 | 792 | 	.get		=	u32_get, | 
 | 793 | 	.put		=	u32_put, | 
 | 794 | 	.change		=	u32_change, | 
 | 795 | 	.delete		=	u32_delete, | 
 | 796 | 	.walk		=	u32_walk, | 
 | 797 | 	.dump		=	u32_dump, | 
 | 798 | 	.owner		=	THIS_MODULE, | 
 | 799 | }; | 
 | 800 |  | 
 | 801 | static int __init init_u32(void) | 
 | 802 | { | 
 | 803 | 	printk("u32 classifier\n"); | 
 | 804 | #ifdef CONFIG_CLS_U32_PERF | 
 | 805 | 	printk("    Perfomance counters on\n"); | 
 | 806 | #endif | 
 | 807 | #ifdef CONFIG_NET_CLS_POLICE | 
 | 808 | 	printk("    OLD policer on \n"); | 
 | 809 | #endif | 
 | 810 | #ifdef CONFIG_NET_CLS_IND | 
 | 811 | 	printk("    input device check on \n"); | 
 | 812 | #endif | 
 | 813 | #ifdef CONFIG_NET_CLS_ACT | 
 | 814 | 	printk("    Actions configured \n"); | 
 | 815 | #endif | 
 | 816 | 	return register_tcf_proto_ops(&cls_u32_ops); | 
 | 817 | } | 
 | 818 |  | 
 | 819 | static void __exit exit_u32(void)  | 
 | 820 | { | 
 | 821 | 	unregister_tcf_proto_ops(&cls_u32_ops); | 
 | 822 | } | 
 | 823 |  | 
 | 824 | module_init(init_u32) | 
 | 825 | module_exit(exit_u32) | 
 | 826 | MODULE_LICENSE("GPL"); |