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