1 /* 2 * net/sched/cls_route.c ROUTE4 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 12 #include <linux/module.h> 13 #include <asm/uaccess.h> 14 #include <asm/system.h> 15 #include <linux/bitops.h> 16 #include <linux/types.h> 17 #include <linux/kernel.h> 18 #include <linux/sched.h> 19 #include <linux/string.h> 20 #include <linux/mm.h> 21 #include <linux/socket.h> 22 #include <linux/sockios.h> 23 #include <linux/in.h> 24 #include <linux/errno.h> 25 #include <linux/interrupt.h> 26 #include <linux/if_ether.h> 27 #include <linux/inet.h> 28 #include <linux/netdevice.h> 29 #include <linux/etherdevice.h> 30 #include <linux/notifier.h> 31 #include <net/ip.h> 32 #include <net/route.h> 33 #include <linux/skbuff.h> 34 #include <net/sock.h> 35 #include <net/act_api.h> 36 #include <net/pkt_cls.h> 37 38 /* 39 1. For now we assume that route tags < 256. 40 It allows to use direct table lookups, instead of hash tables. 41 2. For now we assume that "from TAG" and "fromdev DEV" statements 42 are mutually exclusive. 43 3. "to TAG from ANY" has higher priority, than "to ANY from XXX" 44 */ 45 46 struct route4_fastmap 47 { 48 struct route4_filter *filter; 49 u32 id; 50 int iif; 51 }; 52 53 struct route4_head 54 { 55 struct route4_fastmap fastmap[16]; 56 struct route4_bucket *table[256+1]; 57 }; 58 59 struct route4_bucket 60 { 61 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */ 62 struct route4_filter *ht[16+16+1]; 63 }; 64 65 struct route4_filter 66 { 67 struct route4_filter *next; 68 u32 id; 69 int iif; 70 71 struct tcf_result res; 72 struct tcf_exts exts; 73 u32 handle; 74 struct route4_bucket *bkt; 75 }; 76 77 #define ROUTE4_FAILURE ((struct route4_filter*)(-1L)) 78 79 static struct tcf_ext_map route_ext_map = { 80 .police = TCA_ROUTE4_POLICE, 81 .action = TCA_ROUTE4_ACT 82 }; 83 84 static __inline__ int route4_fastmap_hash(u32 id, int iif) 85 { 86 return id&0xF; 87 } 88 89 static inline 90 void route4_reset_fastmap(struct net_device *dev, struct route4_head *head, u32 id) 91 { 92 spin_lock_bh(&dev->queue_lock); 93 memset(head->fastmap, 0, sizeof(head->fastmap)); 94 spin_unlock_bh(&dev->queue_lock); 95 } 96 97 static void __inline__ 98 route4_set_fastmap(struct route4_head *head, u32 id, int iif, 99 struct route4_filter *f) 100 { 101 int h = route4_fastmap_hash(id, iif); 102 head->fastmap[h].id = id; 103 head->fastmap[h].iif = iif; 104 head->fastmap[h].filter = f; 105 } 106 107 static __inline__ int route4_hash_to(u32 id) 108 { 109 return id&0xFF; 110 } 111 112 static __inline__ int route4_hash_from(u32 id) 113 { 114 return (id>>16)&0xF; 115 } 116 117 static __inline__ int route4_hash_iif(int iif) 118 { 119 return 16 + ((iif>>16)&0xF); 120 } 121 122 static __inline__ int route4_hash_wild(void) 123 { 124 return 32; 125 } 126 127 #define ROUTE4_APPLY_RESULT() \ 128 { \ 129 *res = f->res; \ 130 if (tcf_exts_is_available(&f->exts)) { \ 131 int r = tcf_exts_exec(skb, &f->exts, res); \ 132 if (r < 0) { \ 133 dont_cache = 1; \ 134 continue; \ 135 } \ 136 return r; \ 137 } else if (!dont_cache) \ 138 route4_set_fastmap(head, id, iif, f); \ 139 return 0; \ 140 } 141 142 static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp, 143 struct tcf_result *res) 144 { 145 struct route4_head *head = (struct route4_head*)tp->root; 146 struct dst_entry *dst; 147 struct route4_bucket *b; 148 struct route4_filter *f; 149 u32 id, h; 150 int iif, dont_cache = 0; 151 152 if ((dst = skb->dst) == NULL) 153 goto failure; 154 155 id = dst->tclassid; 156 if (head == NULL) 157 goto old_method; 158 159 iif = ((struct rtable*)dst)->fl.iif; 160 161 h = route4_fastmap_hash(id, iif); 162 if (id == head->fastmap[h].id && 163 iif == head->fastmap[h].iif && 164 (f = head->fastmap[h].filter) != NULL) { 165 if (f == ROUTE4_FAILURE) 166 goto failure; 167 168 *res = f->res; 169 return 0; 170 } 171 172 h = route4_hash_to(id); 173 174 restart: 175 if ((b = head->table[h]) != NULL) { 176 for (f = b->ht[route4_hash_from(id)]; f; f = f->next) 177 if (f->id == id) 178 ROUTE4_APPLY_RESULT(); 179 180 for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next) 181 if (f->iif == iif) 182 ROUTE4_APPLY_RESULT(); 183 184 for (f = b->ht[route4_hash_wild()]; f; f = f->next) 185 ROUTE4_APPLY_RESULT(); 186 187 } 188 if (h < 256) { 189 h = 256; 190 id &= ~0xFFFF; 191 goto restart; 192 } 193 194 if (!dont_cache) 195 route4_set_fastmap(head, id, iif, ROUTE4_FAILURE); 196 failure: 197 return -1; 198 199 old_method: 200 if (id && (TC_H_MAJ(id) == 0 || 201 !(TC_H_MAJ(id^tp->q->handle)))) { 202 res->classid = id; 203 res->class = 0; 204 return 0; 205 } 206 return -1; 207 } 208 209 static inline u32 to_hash(u32 id) 210 { 211 u32 h = id&0xFF; 212 if (id&0x8000) 213 h += 256; 214 return h; 215 } 216 217 static inline u32 from_hash(u32 id) 218 { 219 id &= 0xFFFF; 220 if (id == 0xFFFF) 221 return 32; 222 if (!(id & 0x8000)) { 223 if (id > 255) 224 return 256; 225 return id&0xF; 226 } 227 return 16 + (id&0xF); 228 } 229 230 static unsigned long route4_get(struct tcf_proto *tp, u32 handle) 231 { 232 struct route4_head *head = (struct route4_head*)tp->root; 233 struct route4_bucket *b; 234 struct route4_filter *f; 235 unsigned h1, h2; 236 237 if (!head) 238 return 0; 239 240 h1 = to_hash(handle); 241 if (h1 > 256) 242 return 0; 243 244 h2 = from_hash(handle>>16); 245 if (h2 > 32) 246 return 0; 247 248 if ((b = head->table[h1]) != NULL) { 249 for (f = b->ht[h2]; f; f = f->next) 250 if (f->handle == handle) 251 return (unsigned long)f; 252 } 253 return 0; 254 } 255 256 static void route4_put(struct tcf_proto *tp, unsigned long f) 257 { 258 } 259 260 static int route4_init(struct tcf_proto *tp) 261 { 262 return 0; 263 } 264 265 static inline void 266 route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f) 267 { 268 tcf_unbind_filter(tp, &f->res); 269 tcf_exts_destroy(tp, &f->exts); 270 kfree(f); 271 } 272 273 static void route4_destroy(struct tcf_proto *tp) 274 { 275 struct route4_head *head = xchg(&tp->root, NULL); 276 int h1, h2; 277 278 if (head == NULL) 279 return; 280 281 for (h1=0; h1<=256; h1++) { 282 struct route4_bucket *b; 283 284 if ((b = head->table[h1]) != NULL) { 285 for (h2=0; h2<=32; h2++) { 286 struct route4_filter *f; 287 288 while ((f = b->ht[h2]) != NULL) { 289 b->ht[h2] = f->next; 290 route4_delete_filter(tp, f); 291 } 292 } 293 kfree(b); 294 } 295 } 296 kfree(head); 297 } 298 299 static int route4_delete(struct tcf_proto *tp, unsigned long arg) 300 { 301 struct route4_head *head = (struct route4_head*)tp->root; 302 struct route4_filter **fp, *f = (struct route4_filter*)arg; 303 unsigned h = 0; 304 struct route4_bucket *b; 305 int i; 306 307 if (!head || !f) 308 return -EINVAL; 309 310 h = f->handle; 311 b = f->bkt; 312 313 for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) { 314 if (*fp == f) { 315 tcf_tree_lock(tp); 316 *fp = f->next; 317 tcf_tree_unlock(tp); 318 319 route4_reset_fastmap(tp->q->dev, head, f->id); 320 route4_delete_filter(tp, f); 321 322 /* Strip tree */ 323 324 for (i=0; i<=32; i++) 325 if (b->ht[i]) 326 return 0; 327 328 /* OK, session has no flows */ 329 tcf_tree_lock(tp); 330 head->table[to_hash(h)] = NULL; 331 tcf_tree_unlock(tp); 332 333 kfree(b); 334 return 0; 335 } 336 } 337 return 0; 338 } 339 340 static int route4_set_parms(struct tcf_proto *tp, unsigned long base, 341 struct route4_filter *f, u32 handle, struct route4_head *head, 342 struct rtattr **tb, struct rtattr *est, int new) 343 { 344 int err; 345 u32 id = 0, to = 0, nhandle = 0x8000; 346 struct route4_filter *fp; 347 unsigned int h1; 348 struct route4_bucket *b; 349 struct tcf_exts e; 350 351 err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map); 352 if (err < 0) 353 return err; 354 355 err = -EINVAL; 356 if (tb[TCA_ROUTE4_CLASSID-1]) 357 if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32)) 358 goto errout; 359 360 if (tb[TCA_ROUTE4_TO-1]) { 361 if (new && handle & 0x8000) 362 goto errout; 363 if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < sizeof(u32)) 364 goto errout; 365 to = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]); 366 if (to > 0xFF) 367 goto errout; 368 nhandle = to; 369 } 370 371 if (tb[TCA_ROUTE4_FROM-1]) { 372 if (tb[TCA_ROUTE4_IIF-1]) 373 goto errout; 374 if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32)) 375 goto errout; 376 id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]); 377 if (id > 0xFF) 378 goto errout; 379 nhandle |= id << 16; 380 } else if (tb[TCA_ROUTE4_IIF-1]) { 381 if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32)) 382 goto errout; 383 id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]); 384 if (id > 0x7FFF) 385 goto errout; 386 nhandle |= (id | 0x8000) << 16; 387 } else 388 nhandle |= 0xFFFF << 16; 389 390 if (handle && new) { 391 nhandle |= handle & 0x7F00; 392 if (nhandle != handle) 393 goto errout; 394 } 395 396 h1 = to_hash(nhandle); 397 if ((b = head->table[h1]) == NULL) { 398 err = -ENOBUFS; 399 b = kmalloc(sizeof(struct route4_bucket), GFP_KERNEL); 400 if (b == NULL) 401 goto errout; 402 memset(b, 0, sizeof(*b)); 403 404 tcf_tree_lock(tp); 405 head->table[h1] = b; 406 tcf_tree_unlock(tp); 407 } else { 408 unsigned int h2 = from_hash(nhandle >> 16); 409 err = -EEXIST; 410 for (fp = b->ht[h2]; fp; fp = fp->next) 411 if (fp->handle == f->handle) 412 goto errout; 413 } 414 415 tcf_tree_lock(tp); 416 if (tb[TCA_ROUTE4_TO-1]) 417 f->id = to; 418 419 if (tb[TCA_ROUTE4_FROM-1]) 420 f->id = to | id<<16; 421 else if (tb[TCA_ROUTE4_IIF-1]) 422 f->iif = id; 423 424 f->handle = nhandle; 425 f->bkt = b; 426 tcf_tree_unlock(tp); 427 428 if (tb[TCA_ROUTE4_CLASSID-1]) { 429 f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]); 430 tcf_bind_filter(tp, &f->res, base); 431 } 432 433 tcf_exts_change(tp, &f->exts, &e); 434 435 return 0; 436 errout: 437 tcf_exts_destroy(tp, &e); 438 return err; 439 } 440 441 static int route4_change(struct tcf_proto *tp, unsigned long base, 442 u32 handle, 443 struct rtattr **tca, 444 unsigned long *arg) 445 { 446 struct route4_head *head = tp->root; 447 struct route4_filter *f, *f1, **fp; 448 struct route4_bucket *b; 449 struct rtattr *opt = tca[TCA_OPTIONS-1]; 450 struct rtattr *tb[TCA_ROUTE4_MAX]; 451 unsigned int h, th; 452 u32 old_handle = 0; 453 int err; 454 455 if (opt == NULL) 456 return handle ? -EINVAL : 0; 457 458 if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0) 459 return -EINVAL; 460 461 if ((f = (struct route4_filter*)*arg) != NULL) { 462 if (f->handle != handle && handle) 463 return -EINVAL; 464 465 if (f->bkt) 466 old_handle = f->handle; 467 468 err = route4_set_parms(tp, base, f, handle, head, tb, 469 tca[TCA_RATE-1], 0); 470 if (err < 0) 471 return err; 472 473 goto reinsert; 474 } 475 476 err = -ENOBUFS; 477 if (head == NULL) { 478 head = kmalloc(sizeof(struct route4_head), GFP_KERNEL); 479 if (head == NULL) 480 goto errout; 481 memset(head, 0, sizeof(struct route4_head)); 482 483 tcf_tree_lock(tp); 484 tp->root = head; 485 tcf_tree_unlock(tp); 486 } 487 488 f = kmalloc(sizeof(struct route4_filter), GFP_KERNEL); 489 if (f == NULL) 490 goto errout; 491 memset(f, 0, sizeof(*f)); 492 493 err = route4_set_parms(tp, base, f, handle, head, tb, 494 tca[TCA_RATE-1], 1); 495 if (err < 0) 496 goto errout; 497 498 reinsert: 499 h = from_hash(f->handle >> 16); 500 for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next) 501 if (f->handle < f1->handle) 502 break; 503 504 f->next = f1; 505 tcf_tree_lock(tp); 506 *fp = f; 507 508 if (old_handle && f->handle != old_handle) { 509 th = to_hash(old_handle); 510 h = from_hash(old_handle >> 16); 511 if ((b = head->table[th]) != NULL) { 512 for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) { 513 if (*fp == f) { 514 *fp = f->next; 515 break; 516 } 517 } 518 } 519 } 520 tcf_tree_unlock(tp); 521 522 route4_reset_fastmap(tp->q->dev, head, f->id); 523 *arg = (unsigned long)f; 524 return 0; 525 526 errout: 527 kfree(f); 528 return err; 529 } 530 531 static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg) 532 { 533 struct route4_head *head = tp->root; 534 unsigned h, h1; 535 536 if (head == NULL) 537 arg->stop = 1; 538 539 if (arg->stop) 540 return; 541 542 for (h = 0; h <= 256; h++) { 543 struct route4_bucket *b = head->table[h]; 544 545 if (b) { 546 for (h1 = 0; h1 <= 32; h1++) { 547 struct route4_filter *f; 548 549 for (f = b->ht[h1]; f; f = f->next) { 550 if (arg->count < arg->skip) { 551 arg->count++; 552 continue; 553 } 554 if (arg->fn(tp, (unsigned long)f, arg) < 0) { 555 arg->stop = 1; 556 return; 557 } 558 arg->count++; 559 } 560 } 561 } 562 } 563 } 564 565 static int route4_dump(struct tcf_proto *tp, unsigned long fh, 566 struct sk_buff *skb, struct tcmsg *t) 567 { 568 struct route4_filter *f = (struct route4_filter*)fh; 569 unsigned char *b = skb->tail; 570 struct rtattr *rta; 571 u32 id; 572 573 if (f == NULL) 574 return skb->len; 575 576 t->tcm_handle = f->handle; 577 578 rta = (struct rtattr*)b; 579 RTA_PUT(skb, TCA_OPTIONS, 0, NULL); 580 581 if (!(f->handle&0x8000)) { 582 id = f->id&0xFF; 583 RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id); 584 } 585 if (f->handle&0x80000000) { 586 if ((f->handle>>16) != 0xFFFF) 587 RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif); 588 } else { 589 id = f->id>>16; 590 RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id); 591 } 592 if (f->res.classid) 593 RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid); 594 595 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0) 596 goto rtattr_failure; 597 598 rta->rta_len = skb->tail - b; 599 600 if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0) 601 goto rtattr_failure; 602 603 return skb->len; 604 605 rtattr_failure: 606 skb_trim(skb, b - skb->data); 607 return -1; 608 } 609 610 static struct tcf_proto_ops cls_route4_ops = { 611 .next = NULL, 612 .kind = "route", 613 .classify = route4_classify, 614 .init = route4_init, 615 .destroy = route4_destroy, 616 .get = route4_get, 617 .put = route4_put, 618 .change = route4_change, 619 .delete = route4_delete, 620 .walk = route4_walk, 621 .dump = route4_dump, 622 .owner = THIS_MODULE, 623 }; 624 625 static int __init init_route4(void) 626 { 627 return register_tcf_proto_ops(&cls_route4_ops); 628 } 629 630 static void __exit exit_route4(void) 631 { 632 unregister_tcf_proto_ops(&cls_route4_ops); 633 } 634 635 module_init(init_route4) 636 module_exit(exit_route4) 637 MODULE_LICENSE("GPL"); 638