pppd/gencode.c

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