1 /* 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that: (1) source code distributions 7 * retain the above copyright notice and this paragraph in its entirety, (2) 8 * distributions including binary code include the above copyright notice and 9 * this paragraph in its entirety in the documentation or other materials 10 * provided with the distribution, and (3) all advertising materials mentioning 11 * features or use of this software display the following acknowledgement: 12 * ``This product includes software developed by the University of California, 13 * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of 14 * the University nor the names of its contributors may be used to endorse 15 * or promote products derived from this software without specific prior 16 * written permission. 17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 18 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 20 */ 21 #ifndef lint 22 static char rcsid[] = 23 "@(#) $Header: gencode.c,v 1.26 91/06/06 22:36:19 mccanne Exp $ (LBL)"; 24 #endif 25 26 #ifdef __STDC__ 27 #include <stdlib.h> 28 #endif 29 #include <sys/types.h> 30 #include <sys/socket.h> 31 #include <net/if.h> 32 #include <netinet/in.h> 33 #include <netinet/if_ether.h> 34 35 #include <sys/time.h> 36 #include <net/bpf.h> 37 38 #include "interface.h" 39 #include "gencode.h" 40 #include "nametoaddr.h" 41 #include "extract.h" 42 43 #define JMP(c) ((c)|BPF_JMP|BPF_K) 44 45 extern struct bpf_insn *icode_to_fcode(); 46 extern u_long net_mask(); 47 static void init_linktype(); 48 49 static int alloc_reg(); 50 static void free_reg(); 51 52 static struct block *root; 53 54 /* 55 * We divy out chunks of memory rather than call malloc each time so 56 * we don't have to worry about leaking memory. It's probably 57 * not a big deal if all this memory was wasted but it this ever 58 * goes into a library that would probably not be a good idea. 59 */ 60 #define NCHUNKS 16 61 #define CHUNK0SIZE 1024 62 struct chunk { 63 u_int n_left; 64 void *m; 65 }; 66 67 static struct chunk chunks[NCHUNKS]; 68 static int cur_chunk; 69 70 static void * 71 newchunk(n) 72 u_int n; 73 { 74 struct chunk *cp; 75 int k, size; 76 77 /* XXX Round up to nearest long. */ 78 n = (n + sizeof(long) - 1) & ~(sizeof(long) - 1); 79 80 cp = &chunks[cur_chunk]; 81 if (n > cp->n_left) { 82 ++cp, k = ++cur_chunk; 83 if (k >= NCHUNKS) 84 error("newchunk: out of chunks"); 85 size = CHUNK0SIZE << k; 86 cp->m = (void *)malloc(size); 87 bzero((char *)cp->m, size); 88 cp->n_left = size; 89 if (n > size) 90 error("newchunk: request too big"); 91 } 92 cp->n_left -= n; 93 return (void *)((char *)cp->m + cp->n_left); 94 } 95 96 static void 97 freechunks() 98 { 99 int i; 100 101 for (i = 0; i < NCHUNKS; ++i) 102 if (chunks[i].m) 103 free(chunks[i].m); 104 } 105 106 static inline struct block * 107 new_block(code) 108 int code; 109 { 110 struct block *p; 111 112 p = (struct block *)newchunk(sizeof(*p)); 113 p->s.code = code; 114 p->head = p; 115 116 return p; 117 } 118 119 static inline struct slist * 120 new_stmt(code) 121 int code; 122 { 123 struct slist *p; 124 125 p = (struct slist *)newchunk(sizeof(*p)); 126 p->s.code = code; 127 128 return p; 129 } 130 131 static struct block * 132 gen_retblk(v) 133 int v; 134 { 135 struct block *b = new_block(BPF_RET|BPF_K); 136 137 b->s.k = v; 138 return b; 139 } 140 141 struct bpf_program * 142 parse(buf, Oflag, linktype) 143 char *buf; 144 int Oflag; 145 int linktype; 146 { 147 extern int n_errors; 148 static struct bpf_program F; 149 struct bpf_insn *p; 150 int len; 151 152 F.bf_insns = 0; 153 F.bf_len = 0; 154 155 lex_init(buf ? buf : ""); 156 init_linktype(linktype); 157 yyparse(); 158 159 if (n_errors) 160 error("expression syntax error"); 161 162 if (root == 0) 163 root = gen_retblk(snaplen); 164 165 if (Oflag) { 166 optimize(&root); 167 if (root == 0 || 168 (root->s.code == (BPF_RET|BPF_K) && root->s.k == 0)) 169 error("expression rejects all packets"); 170 } 171 p = icode_to_fcode(root, &len); 172 F.bf_insns = p; 173 F.bf_len = len; 174 175 freechunks(); 176 return &F; 177 } 178 179 /* 180 * Backpatch the blocks in 'list' to 'target'. The 'sense' field indicates 181 * which of the jt and jf fields has been resolved and which is a pointer 182 * back to another unresolved block (or nil). At least one of the fields 183 * in each block is already resolved. 184 */ 185 static void 186 backpatch(list, target) 187 struct block *list, *target; 188 { 189 struct block *next; 190 191 while (list) { 192 if (!list->sense) { 193 next = JT(list); 194 JT(list) = target; 195 } else { 196 next = JF(list); 197 JF(list) = target; 198 } 199 list = next; 200 } 201 } 202 203 /* 204 * Merge the lists in b0 and b1, using the 'sense' field to indicate 205 * which of jt and jf is the link. 206 */ 207 static void 208 merge(b0, b1) 209 struct block *b0, *b1; 210 { 211 register struct block **p = &b0; 212 213 /* Find end of list. */ 214 while (*p) 215 p = !((*p)->sense) ? &JT(*p) : &JF(*p); 216 217 /* Concatenate the lists. */ 218 *p = b1; 219 } 220 221 void 222 finish_parse(p) 223 struct block *p; 224 { 225 backpatch(p, gen_retblk(snaplen)); 226 p->sense = !p->sense; 227 backpatch(p, gen_retblk(0)); 228 root = p->head; 229 } 230 231 void 232 gen_and(b0, b1) 233 struct block *b0, *b1; 234 { 235 backpatch(b0, b1->head); 236 b0->sense = !b0->sense; 237 b1->sense = !b1->sense; 238 merge(b1, b0); 239 b1->sense = !b1->sense; 240 b1->head = b0->head; 241 } 242 243 void 244 gen_or(b0, b1) 245 struct block *b0, *b1; 246 { 247 b0->sense = !b0->sense; 248 backpatch(b0, b1->head); 249 b0->sense = !b0->sense; 250 merge(b1, b0); 251 b1->head = b0->head; 252 } 253 254 void 255 gen_not(b) 256 struct block *b; 257 { 258 b->sense = !b->sense; 259 } 260 261 static struct block * 262 gen_cmp(offset, size, v) 263 u_int offset, size; 264 long v; 265 { 266 struct slist *s; 267 struct block *b; 268 269 s = new_stmt(BPF_LD|BPF_ABS|size); 270 s->s.k = offset; 271 272 b = new_block(JMP(BPF_JEQ)); 273 b->stmts = s; 274 b->s.k = v; 275 276 return b; 277 } 278 279 struct block * 280 gen_mcmp(offset, size, v, mask) 281 u_int offset, size; 282 long v; 283 u_long mask; 284 { 285 struct block *b = gen_cmp(offset, size, v); 286 struct slist *s; 287 288 if (mask != 0xffffffff) { 289 s = new_stmt(BPF_ALU|BPF_AND|BPF_K); 290 s->s.k = mask; 291 b->stmts->next = s; 292 } 293 return b; 294 } 295 296 struct block * 297 gen_bcmp(offset, size, v) 298 u_int offset; 299 u_int size; 300 u_char *v; 301 { 302 struct block *b, *tmp; 303 int k; 304 305 b = 0; 306 while (size >= 4) { 307 k = size - 4; 308 tmp = gen_cmp(offset + k, BPF_W, EXTRACT_LONG(&v[k])); 309 if (b != 0) 310 gen_and(b, tmp); 311 b = tmp; 312 size -= 4; 313 } 314 while (size >= 2) { 315 k = size - 2; 316 tmp = gen_cmp(offset + k, BPF_H, (long)EXTRACT_SHORT(&v[k])); 317 if (b != 0) 318 gen_and(b, tmp); 319 b = tmp; 320 size -= 2; 321 } 322 if (size > 0) { 323 tmp = gen_cmp(offset, BPF_B, (long)v[0]); 324 if (b != 0) 325 gen_and(b, tmp); 326 b = tmp; 327 } 328 return b; 329 } 330 331 /* 332 * Various code contructs need to know the layout of the data link 333 * layer. These variables give the necessary offsets. 334 */ 335 static u_int off_linktype; 336 static u_int off_nl; 337 static int linktype; 338 339 static void 340 init_linktype(type) 341 int type; 342 { 343 linktype = type; 344 345 switch (type) { 346 case DLT_EN10MB: 347 off_linktype = 12; 348 off_nl = 14; 349 return; 350 351 case DLT_SLIP: 352 /* 353 * SLIP doesn't have a link level type. The 16 byte 354 * header is hacked into our SLIP driver. 355 */ 356 off_linktype = -1; 357 off_nl = 16; 358 return; 359 360 case DLT_PPP: 361 off_linktype = 2; 362 off_nl = 4; 363 return; 364 } 365 error("unknown data link type %x", linktype); 366 /* NOTREACHED */ 367 } 368 369 static struct block * 370 gen_uncond(rsense) 371 int rsense; 372 { 373 struct block *b; 374 struct slist *s; 375 376 s = new_stmt(BPF_LD|BPF_IMM); 377 s->s.k = !rsense; 378 b = new_block(JMP(BPF_JEQ)); 379 b->stmts = s; 380 381 return b; 382 } 383 384 static inline struct block * 385 gen_true() 386 { 387 return gen_uncond(1); 388 } 389 390 static inline struct block * 391 gen_false() 392 { 393 return gen_uncond(0); 394 } 395 396 struct block * 397 gen_linktype(proto) 398 int proto; 399 { 400 switch (linktype) { 401 case DLT_SLIP: 402 if (proto == ETHERTYPE_IP) 403 return gen_true(); 404 else 405 return gen_false(); 406 407 case DLT_PPP: 408 if (proto == ETHERTYPE_IP) 409 proto = 0x0021; /* XXX - need ppp.h defs */ 410 break; 411 } 412 return gen_cmp(off_linktype, BPF_H, (long)proto); 413 } 414 415 static struct block * 416 gen_hostop(addr, mask, dir, proto, src_off, dst_off) 417 u_long addr; 418 u_long mask; 419 int dir, proto; 420 u_int src_off, dst_off; 421 { 422 struct block *b0, *b1; 423 u_int offset; 424 425 switch (dir) { 426 427 case Q_SRC: 428 offset = src_off; 429 break; 430 431 case Q_DST: 432 offset = dst_off; 433 break; 434 435 case Q_AND: 436 b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off); 437 b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off); 438 gen_and(b0, b1); 439 return b1; 440 441 case Q_OR: 442 case Q_DEFAULT: 443 b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off); 444 b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off); 445 gen_or(b0, b1); 446 return b1; 447 448 default: 449 abort(); 450 } 451 b0 = gen_linktype(proto); 452 b1 = gen_mcmp(offset, BPF_W, (long)addr, mask); 453 gen_and(b0, b1); 454 return b1; 455 } 456 457 static struct block * 458 gen_ehostop(eaddr, dir) 459 u_char *eaddr; 460 int dir; 461 { 462 struct block *b0, *b1; 463 464 switch (dir) { 465 case Q_SRC: 466 return gen_bcmp(6, 6, eaddr); 467 468 case Q_DST: 469 return gen_bcmp(0, 6, eaddr); 470 471 case Q_AND: 472 b0 = gen_ehostop(eaddr, Q_SRC); 473 b1 = gen_ehostop(eaddr, Q_DST); 474 gen_and(b0, b1); 475 return b1; 476 477 case Q_DEFAULT: 478 case Q_OR: 479 b0 = gen_ehostop(eaddr, Q_SRC); 480 b1 = gen_ehostop(eaddr, Q_DST); 481 gen_or(b0, b1); 482 return b1; 483 } 484 abort(); 485 /* NOTREACHED */ 486 } 487 488 static struct block * 489 gen_host(addr, mask, proto, dir) 490 u_long addr; 491 u_long mask; 492 int proto; 493 int dir; 494 { 495 struct block *b0, *b1; 496 497 switch (proto) { 498 499 case Q_DEFAULT: 500 b0 = gen_host(addr, mask, Q_IP, dir); 501 b1 = gen_host(addr, mask, Q_ARP, dir); 502 gen_or(b0, b1); 503 b0 = gen_host(addr, mask, Q_RARP, dir); 504 gen_or(b1, b0); 505 return b0; 506 507 case Q_IP: 508 return gen_hostop(addr, mask, dir, ETHERTYPE_IP, 509 off_nl + 12, off_nl + 16); 510 511 case Q_RARP: 512 return gen_hostop(addr, mask, dir, ETHERTYPE_REVARP, 513 off_nl + 14, off_nl + 24); 514 515 case Q_ARP: 516 return gen_hostop(addr, mask, dir, ETHERTYPE_ARP, 517 off_nl + 14, off_nl + 24); 518 519 case Q_TCP: 520 error("'tcp' modifier applied to host"); 521 522 case Q_UDP: 523 error("'udp' modifier applied to host"); 524 525 case Q_ICMP: 526 error("'icmp' modifier applied to host"); 527 } 528 abort(); 529 /* NOTREACHED */ 530 } 531 532 static struct block * 533 gen_gateway(eaddr, alist, proto, dir) 534 u_char *eaddr; 535 u_long **alist; 536 int proto; 537 int dir; 538 { 539 struct block *b0, *b1, *tmp; 540 541 if (dir != 0) 542 error("direction applied to 'gateway'"); 543 544 switch (proto) { 545 case Q_DEFAULT: 546 case Q_IP: 547 case Q_ARP: 548 case Q_RARP: 549 b0 = gen_ehostop(eaddr, Q_OR); 550 b1 = gen_host(**alist++, 0xffffffffL, proto, Q_OR); 551 while (*alist) { 552 tmp = gen_host(**alist++, 0xffffffffL, proto, Q_OR); 553 gen_or(b1, tmp); 554 b1 = tmp; 555 } 556 gen_not(b1); 557 gen_and(b0, b1); 558 return b1; 559 } 560 error("illegal modifier of 'gateway'"); 561 /* NOTREACHED */ 562 } 563 564 struct block * 565 gen_proto_abbrev(proto) 566 int proto; 567 { 568 struct block *b0, *b1; 569 570 switch (proto) { 571 572 case Q_TCP: 573 b0 = gen_linktype(ETHERTYPE_IP); 574 b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_TCP); 575 gen_and(b0, b1); 576 break; 577 578 case Q_UDP: 579 b0 = gen_linktype(ETHERTYPE_IP); 580 b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_UDP); 581 gen_and(b0, b1); 582 break; 583 584 case Q_ICMP: 585 b0 = gen_linktype(ETHERTYPE_IP); 586 b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_ICMP); 587 gen_and(b0, b1); 588 break; 589 590 case Q_IP: 591 b1 = gen_linktype(ETHERTYPE_IP); 592 break; 593 594 case Q_ARP: 595 b1 = gen_linktype(ETHERTYPE_ARP); 596 break; 597 598 case Q_RARP: 599 b1 = gen_linktype(ETHERTYPE_REVARP); 600 break; 601 602 case Q_ETHER: 603 error("'ether' keyword used incorrectly"); 604 605 default: 606 abort(); 607 } 608 return b1; 609 } 610 611 static struct block * 612 gen_ipfrag() 613 { 614 struct slist *s; 615 struct block *b; 616 617 /* not ip frag */ 618 s = new_stmt(BPF_LD|BPF_H|BPF_ABS); 619 s->s.k = off_nl + 6; 620 b = new_block(JMP(BPF_JSET)); 621 b->s.k = 0x1fff; 622 b->stmts = s; 623 gen_not(b); 624 625 return b; 626 } 627 628 static struct block * 629 gen_portatom(off, v) 630 int off; 631 long v; 632 { 633 struct slist *s; 634 struct block *b; 635 636 s = new_stmt(BPF_LDX|BPF_MSH|BPF_B); 637 s->s.k = off_nl; 638 639 s->next = new_stmt(BPF_LD|BPF_IND|BPF_H); 640 s->next->s.k = off_nl + off; 641 642 b = new_block(JMP(BPF_JEQ)); 643 b->stmts = s; 644 b->s.k = v; 645 646 return b; 647 } 648 649 struct block * 650 gen_portop(port, proto, dir) 651 int port; 652 int proto; 653 int dir; 654 { 655 struct block *b0, *b1, *tmp; 656 657 /* ip proto 'proto' */ 658 tmp = gen_cmp(off_nl + 9, BPF_B, (long)proto); 659 b0 = gen_ipfrag(); 660 gen_and(tmp, b0); 661 662 switch (dir) { 663 case Q_SRC: 664 b1 = gen_portatom(0, (long)port); 665 break; 666 667 case Q_DST: 668 b1 = gen_portatom(2, (long)port); 669 break; 670 671 case Q_OR: 672 case Q_DEFAULT: 673 tmp = gen_portatom(0, (long)port); 674 b1 = gen_portatom(2, (long)port); 675 gen_or(tmp, b1); 676 break; 677 678 case Q_AND: 679 tmp = gen_portatom(0, (long)port); 680 b1 = gen_portatom(2, (long)port); 681 gen_and(tmp, b1); 682 break; 683 684 default: 685 abort(); 686 } 687 gen_and(b0, b1); 688 689 return b1; 690 } 691 692 static struct block * 693 gen_port(port, ip_proto, dir) 694 int port; 695 int ip_proto; 696 int dir; 697 { 698 struct block *b0, *b1, *tmp; 699 700 /* ether proto ip */ 701 b0 = gen_linktype(ETHERTYPE_IP); 702 703 switch (ip_proto) { 704 case IPPROTO_UDP: 705 case IPPROTO_TCP: 706 b1 = gen_portop(port, ip_proto, dir); 707 break; 708 709 case PROTO_UNDEF: 710 tmp = gen_portop(port, IPPROTO_TCP, dir); 711 b1 = gen_portop(port, IPPROTO_UDP, dir); 712 gen_or(tmp, b1); 713 break; 714 715 default: 716 abort(); 717 } 718 gen_and(b0, b1); 719 return b1; 720 } 721 722 int 723 lookup_proto(name, proto) 724 char *name; 725 int proto; 726 { 727 int v; 728 729 switch (proto) { 730 case Q_DEFAULT: 731 case Q_IP: 732 v = s_nametoproto(name); 733 if (v == PROTO_UNDEF) 734 error("unknown ip proto '%s'", name); 735 break; 736 737 case Q_ETHER: 738 v = s_nametoeproto(name); 739 if (v == PROTO_UNDEF) 740 error("unknown ether proto '%s'", name); 741 break; 742 743 default: 744 v = PROTO_UNDEF; 745 break; 746 } 747 return v; 748 } 749 750 struct block * 751 gen_proto(v, proto, dir) 752 int v; 753 int proto; 754 int dir; 755 { 756 struct block *b0, *b1; 757 758 if (dir != Q_DEFAULT) 759 error("direction applied to 'proto'"); 760 761 switch (proto) { 762 case Q_DEFAULT: 763 case Q_IP: 764 b0 = gen_linktype(ETHERTYPE_IP); 765 b1 = gen_cmp(off_nl + 9, BPF_B, (long)v); 766 gen_and(b0, b1); 767 return b1; 768 769 case Q_ARP: 770 error("arp does not encapsulate another protocol"); 771 /* NOTREACHED */ 772 773 case Q_RARP: 774 error("rarp does not encapsulate another protocol"); 775 /* NOTREACHED */ 776 777 case Q_ETHER: 778 return gen_linktype(v); 779 780 case Q_UDP: 781 error("'udp proto' is bogus"); 782 783 case Q_TCP: 784 error("'tcp proto' is bogus"); 785 786 case Q_ICMP: 787 error("'icmp proto' is bogus"); 788 } 789 abort(); 790 /* NOTREACHED */ 791 } 792 793 struct block * 794 gen_scode(name, q) 795 char *name; 796 struct qual q; 797 { 798 int proto = q.protocol; 799 int dir = q.dir; 800 u_char *eaddr; 801 u_long mask, addr, **alist; 802 struct block *b, *tmp; 803 int port, real_proto; 804 805 switch (q.primary) { 806 807 case Q_NET: 808 addr = s_nametonetaddr(name); 809 if (addr == 0) 810 error("unknown network '%s'", name); 811 mask = net_mask(&addr); 812 return gen_host(addr, mask, proto, dir); 813 814 case Q_DEFAULT: 815 case Q_HOST: 816 if (proto == Q_ETHER) { 817 eaddr = ETHER_hostton(name); 818 if (eaddr == 0) 819 error("unknown ether host '%s'", name); 820 return gen_ehostop(eaddr, dir); 821 822 } else { 823 alist = s_nametoaddr(name); 824 if (alist == 0 || *alist == 0) 825 error("uknown host '%s'", name); 826 b = gen_host(**alist++, 0xffffffffL, proto, dir); 827 while (*alist) { 828 tmp = gen_host(**alist++, 0xffffffffL, 829 proto, dir); 830 gen_or(b, tmp); 831 b = tmp; 832 } 833 return b; 834 } 835 836 case Q_PORT: 837 if (proto != Q_DEFAULT && proto != Q_UDP && proto != Q_TCP) 838 error("illegal qualifier of 'port'"); 839 if (s_nametoport(name, &port, &real_proto) == 0) 840 error("unknown port '%s'", name); 841 if (proto == Q_UDP) { 842 if (real_proto == IPPROTO_TCP) 843 error("port '%s' is tcp", name); 844 else 845 /* override PROTO_UNDEF */ 846 real_proto = IPPROTO_UDP; 847 } 848 if (proto == Q_TCP) { 849 if (real_proto == IPPROTO_UDP) 850 error("port '%s' is udp", name); 851 else 852 /* override PROTO_UNDEF */ 853 real_proto = IPPROTO_TCP; 854 } 855 return gen_port(port, real_proto, dir); 856 857 case Q_GATEWAY: 858 eaddr = ETHER_hostton(name); 859 if (eaddr == 0) 860 error("unknown ether host: %s", name); 861 862 alist = s_nametoaddr(name); 863 if (alist == 0 || *alist == 0) 864 error("uknown host '%s'", name); 865 return gen_gateway(eaddr, alist, proto, dir); 866 867 case Q_PROTO: 868 real_proto = lookup_proto(name, proto); 869 if (real_proto >= 0) 870 return gen_proto(real_proto, proto, dir); 871 else 872 error("unknown protocol: %s", name); 873 } 874 abort(); 875 /* NOTREACHED */ 876 } 877 878 struct block * 879 gen_ncode(v, q) 880 u_long v; 881 struct qual q; 882 { 883 u_long mask; 884 int proto = q.protocol; 885 int dir = q.dir; 886 887 switch (q.primary) { 888 889 case Q_DEFAULT: 890 case Q_HOST: 891 case Q_NET: 892 mask = net_mask(&v); 893 return gen_host(v, mask, proto, dir); 894 895 case Q_PORT: 896 if (proto == Q_UDP) 897 proto = IPPROTO_UDP; 898 else if (proto == Q_TCP) 899 proto = IPPROTO_TCP; 900 else if (proto == Q_DEFAULT) 901 proto = PROTO_UNDEF; 902 else 903 error("illegal qualifier of 'port'"); 904 905 return gen_port((int)v, proto, dir); 906 907 case Q_GATEWAY: 908 error("'gateway' requires a name"); 909 /* NOTREACHED */ 910 911 case Q_PROTO: 912 return gen_proto((int)v, proto, dir); 913 } 914 abort(); 915 /* NOTREACHED */ 916 } 917 918 struct block * 919 gen_ecode(eaddr, q) 920 u_char *eaddr; 921 struct qual q; 922 { 923 if ((q.primary == Q_HOST || q.primary == Q_DEFAULT) 924 && q.protocol == Q_ETHER) 925 return gen_ehostop(eaddr, (int)q.dir); 926 else 927 error("ethernet address used in non-ether expression"); 928 /* NOTREACHED */ 929 } 930 931 void 932 sappend(s0, s1) 933 struct slist *s0, *s1; 934 { 935 /* 936 * This is definitely not the best way to do this, but the 937 * lists will rarely get long. 938 */ 939 while (s0->next) 940 s0 = s0->next; 941 s0->next = s1; 942 } 943 944 struct slist * 945 xfer_to_x(a) 946 struct arth *a; 947 { 948 struct slist *s; 949 950 s = new_stmt(BPF_LDX|BPF_MEM); 951 s->s.k = a->regno; 952 return s; 953 } 954 955 struct slist * 956 xfer_to_a(a) 957 struct arth *a; 958 { 959 struct slist *s; 960 961 s = new_stmt(BPF_LD|BPF_MEM); 962 s->s.k = a->regno; 963 return s; 964 } 965 966 struct arth * 967 gen_load(proto, index, size) 968 int proto; 969 struct arth *index; 970 int size; 971 { 972 struct slist *s, *tmp; 973 struct block *b; 974 int regno = alloc_reg(); 975 976 free_reg(index->regno); 977 switch (size) { 978 979 default: 980 error("data size must be 1, 2, or 4"); 981 982 case 1: 983 size = BPF_B; 984 break; 985 986 case 2: 987 size = BPF_H; 988 break; 989 990 case 4: 991 size = BPF_W; 992 break; 993 } 994 switch (proto) { 995 default: 996 error("unsupported index operation"); 997 998 case Q_ETHER: 999 s = xfer_to_x(index); 1000 tmp = new_stmt(BPF_LD|BPF_IND|size); 1001 sappend(s, tmp); 1002 sappend(index->s, s); 1003 break; 1004 1005 case Q_IP: 1006 case Q_ARP: 1007 case Q_RARP: 1008 s = xfer_to_x(index); 1009 tmp = new_stmt(BPF_LD|BPF_IND|size); 1010 tmp->s.k = off_nl; 1011 sappend(s, tmp); 1012 sappend(index->s, s); 1013 1014 b = gen_proto_abbrev(proto); 1015 if (index->b) 1016 gen_and(index->b, b); 1017 index->b = b; 1018 break; 1019 1020 case Q_TCP: 1021 case Q_UDP: 1022 case Q_ICMP: 1023 s = new_stmt(BPF_LDX|BPF_MSH|BPF_B); 1024 s->s.k = off_nl; 1025 sappend(s, xfer_to_a(index)); 1026 sappend(s, new_stmt(BPF_ALU|BPF_ADD|BPF_X)); 1027 sappend(s, new_stmt(BPF_MISC|BPF_TAX)); 1028 sappend(s, tmp = new_stmt(BPF_LD|BPF_IND|size)); 1029 tmp->s.k = off_nl; 1030 sappend(index->s, s); 1031 1032 gen_and(gen_proto_abbrev(proto), b = gen_ipfrag()); 1033 if (index->b) 1034 gen_and(index->b, b); 1035 index->b = b; 1036 break; 1037 } 1038 index->regno = regno; 1039 s = new_stmt(BPF_ST); 1040 s->s.k = regno; 1041 sappend(index->s, s); 1042 1043 return index; 1044 } 1045 1046 struct block * 1047 gen_relation(code, a0, a1, reversed) 1048 int code; 1049 struct arth *a0, *a1; 1050 int reversed; 1051 { 1052 struct slist *s0, *s1, *s2; 1053 struct block *b, *tmp; 1054 1055 s0 = xfer_to_x(a1); 1056 s1 = xfer_to_a(a0); 1057 s2 = new_stmt(BPF_ALU|BPF_SUB|BPF_X); 1058 b = new_block(JMP(code)); 1059 if (reversed) 1060 gen_not(b); 1061 1062 sappend(s1, s2); 1063 sappend(s0, s1); 1064 sappend(a1->s, s0); 1065 sappend(a0->s, a1->s); 1066 1067 b->stmts = a0->s; 1068 1069 free_reg(a0->regno); 1070 free_reg(a1->regno); 1071 1072 /* 'and' together protocol checks */ 1073 if (a0->b) { 1074 if (a1->b) { 1075 gen_and(a0->b, tmp = a1->b); 1076 } 1077 else 1078 tmp = a0->b; 1079 } else 1080 tmp = a1->b; 1081 1082 if (tmp) 1083 gen_and(tmp, b); 1084 1085 return b; 1086 } 1087 1088 struct arth * 1089 gen_loadlen() 1090 { 1091 int regno = alloc_reg(); 1092 struct arth *a = (struct arth *)newchunk(sizeof(*a)); 1093 struct slist *s; 1094 1095 s = new_stmt(BPF_LD|BPF_LEN); 1096 s->next = new_stmt(BPF_ST); 1097 s->next->s.k = regno; 1098 a->s = s; 1099 a->regno = regno; 1100 1101 return a; 1102 } 1103 1104 struct arth * 1105 gen_loadi(val) 1106 int val; 1107 { 1108 struct arth *a; 1109 struct slist *s; 1110 int reg; 1111 1112 a = (struct arth *)newchunk(sizeof(*a)); 1113 1114 reg = alloc_reg(); 1115 1116 s = new_stmt(BPF_LD|BPF_IMM); 1117 s->s.k = val; 1118 s->next = new_stmt(BPF_ST); 1119 s->next->s.k = reg; 1120 a->s = s; 1121 a->regno = reg; 1122 1123 return a; 1124 } 1125 1126 struct arth * 1127 gen_neg(a) 1128 struct arth *a; 1129 { 1130 struct slist *s; 1131 1132 s = xfer_to_a(a); 1133 sappend(a->s, s); 1134 s = new_stmt(BPF_ALU|BPF_NEG); 1135 s->s.k = 0; 1136 sappend(a->s, s); 1137 s = new_stmt(BPF_ST); 1138 s->s.k = a->regno; 1139 sappend(a->s, s); 1140 1141 return a; 1142 } 1143 1144 struct arth * 1145 gen_arth(code, a0, a1) 1146 int code; 1147 struct arth *a0, *a1; 1148 { 1149 struct slist *s0, *s1, *s2; 1150 1151 s0 = xfer_to_x(a1); 1152 s1 = xfer_to_a(a0); 1153 s2 = new_stmt(BPF_ALU|BPF_X|code); 1154 1155 sappend(s1, s2); 1156 sappend(s0, s1); 1157 sappend(a1->s, s0); 1158 sappend(a0->s, a1->s); 1159 1160 free_reg(a1->regno); 1161 1162 s0 = new_stmt(BPF_ST); 1163 a0->regno = s0->s.k = alloc_reg(); 1164 sappend(a0->s, s0); 1165 1166 return a0; 1167 } 1168 1169 /* 1170 * Here we handle simple allocation of the scratch registers. 1171 * If too many registers are alloc'd, the allocator punts. 1172 */ 1173 static int regused[BPF_MEMWORDS]; 1174 static int curreg; 1175 1176 /* 1177 * Return the next free register. 1178 */ 1179 static int 1180 alloc_reg() 1181 { 1182 int n = BPF_MEMWORDS; 1183 1184 while (--n >= 0) { 1185 if (regused[curreg]) 1186 curreg = (curreg + 1) % BPF_MEMWORDS; 1187 else { 1188 regused[curreg] = 1; 1189 return curreg; 1190 } 1191 } 1192 error("too many registers needed to evaluate expression"); 1193 /* NOTREACHED */ 1194 } 1195 1196 /* 1197 * Return a register to the table so it can 1198 * be used later. 1199 */ 1200 static void 1201 free_reg(n) 1202 int n; 1203 { 1204 regused[n] = 0; 1205 } 1206 1207 static struct block * 1208 gen_len(jmp, n) 1209 int jmp; 1210 int n; 1211 { 1212 struct slist *s; 1213 struct block *b; 1214 1215 s = new_stmt(BPF_LD|BPF_LEN); 1216 s->next = new_stmt(BPF_SUB|BPF_IMM); 1217 s->next->s.k = n; 1218 b = new_block(JMP(jmp)); 1219 b->stmts = s; 1220 1221 return b; 1222 } 1223 1224 struct block * 1225 gen_greater(n) 1226 int n; 1227 { 1228 return gen_len(BPF_JGE, n); 1229 } 1230 1231 struct block * 1232 gen_less(n) 1233 int n; 1234 { 1235 struct block *b; 1236 1237 b = gen_len(BPF_JGT, n); 1238 gen_not(b); 1239 1240 return b; 1241 } 1242 1243 struct block * 1244 gen_byteop(op, idx, val) 1245 int op; 1246 int idx; 1247 int val; 1248 { 1249 struct block *b; 1250 struct slist *s; 1251 1252 switch (op) { 1253 default: 1254 abort(); 1255 1256 case '=': 1257 return gen_cmp((u_int)idx, BPF_B, (long)val); 1258 1259 case '<': 1260 b = gen_cmp((u_int)idx, BPF_B, (long)val); 1261 b->s.code = JMP(BPF_JGE); 1262 gen_not(b); 1263 return b; 1264 1265 case '>': 1266 b = gen_cmp((u_int)idx, BPF_B, (long)val); 1267 b->s.code = JMP(BPF_JGT); 1268 return b; 1269 1270 case '|': 1271 s = new_stmt(BPF_ALU|BPF_AND|BPF_K); 1272 break; 1273 1274 case '&': 1275 s = new_stmt(BPF_ALU|BPF_AND|BPF_K); 1276 break; 1277 } 1278 s->s.k = val; 1279 b = new_block(JMP(BPF_JEQ)); 1280 b->stmts = s; 1281 gen_not(b); 1282 1283 return b; 1284 } 1285 1286 struct block * 1287 gen_broadcast() 1288 { 1289 static u_char ebroadcast[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }; 1290 1291 return gen_ehostop(ebroadcast, Q_DST); 1292 } 1293 1294