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