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