iokit/Drivers/network/AppleBPF/bpf_filter.c

   1 /*
   2  * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */
  23 /*
  24  * Copyright (c) 1990, 1991, 1992, 1993
  25  *      The Regents of the University of California.  All rights reserved.
  26  *
  27  * Redistribution and use in source and binary forms, with or without
  28  * modification, are permitted provided that the following conditions
  29  * are met:
  30  * 1. Redistributions of source code must retain the above copyright
  31  *    notice, this list of conditions and the following disclaimer.
  32  * 2. Redistributions in binary form must reproduce the above copyright
  33  *    notice, this list of conditions and the following disclaimer in the
  34  *    documentation and/or other materials provided with the distribution.
  35  * 3. All advertising materials mentioning features or use of this software
  36  *    must display the following acknowledgement:
  37  *      This product includes software developed by the University of
  38  *      California, Berkeley and its contributors.
  39  * 4. Neither the name of the University nor the names of its contributors
  40  *    may be used to endorse or promote products derived from this software
  41  *    without specific prior written permission.
  42  *
  43  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  44  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  45  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  46  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  47  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  48  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  49  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  50  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  51  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  52  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  53  * SUCH DAMAGE.
  54  *
  55  *      @(#)bpf_filter.c        8.1 (Berkeley) 6/10/93
  56  */
  57
  58 #define BPFDRV
  59
  60 #include <sys/param.h>
  61 #include <sys/types.h>
  62 #include <sys/time.h>
  63
  64 #if defined(sparc) || defined(hppa)
  65 #define BPF_ALIGN
  66 #endif
  67
  68 #ifndef BPF_ALIGN
  69 #define EXTRACT_SHORT(p)        ((u_short)ntohs(*(u_short *)p))
  70 #define EXTRACT_LONG(p)         (ntohl(*(u_int32_t *)p))
  71 #else
  72 #define EXTRACT_SHORT(p)\
  73         ((u_short)\
  74                 ((u_short)*((u_char *)p+0)<<8|\
  75                  (u_short)*((u_char *)p+1)<<0))
  76 #define EXTRACT_LONG(p)\
  77                 ((u_int32_t)*((u_char *)p+0)<<24|\
  78                  (u_int32_t)*((u_char *)p+1)<<16|\
  79                  (u_int32_t)*((u_char *)p+2)<<8|\
  80                  (u_int32_t)*((u_char *)p+3)<<0)
  81 #endif
  82
  83 #ifdef BPFDRV
  84 #ifdef KERNEL
  85 #include <sys/mbuf.h>
  86 #define MINDEX(m, k) \
  87 { \
  88         register int len = m->m_len; \
  89  \
  90         while (k >= len) { \
  91                 k -= len; \
  92                 m = m->m_next; \
  93                 if (m == 0) \
  94                         return 0; \
  95                 len = m->m_len; \
  96         } \
  97 }
  98
  99 static int
 100 m_xword(m, k, err)
 101         register struct mbuf *m;
 102         register int k, *err;
 103 {
 104         register int len;
 105         register u_char *cp, *np;
 106         register struct mbuf *m0;
 107
 108         len = m->m_len;
 109         while (k >= len) {
 110                 k -= len;
 111                 m = m->m_next;
 112                 if (m == 0)
 113                         goto bad;
 114                 len = m->m_len;
 115         }
 116         cp = mtod(m, u_char *) + k;
 117         if (len - k >= 4) {
 118                 *err = 0;
 119                 return EXTRACT_LONG(cp);
 120         }
 121         m0 = m->m_next;
 122         if (m0 == 0 || m0->m_len + len - k < 4)
 123                 goto bad;
 124         *err = 0;
 125         np = mtod(m0, u_char *);
 126         switch (len - k) {
 127
 128         case 1:
 129                 return (cp[k] << 24) | (np[0] << 16) | (np[1] << 8) | np[2];
 130
 131         case 2:
 132                 return (cp[k] << 24) | (cp[k + 1] << 16) | (np[0] << 8) |
 133                         np[1];
 134
 135         default:
 136                 return (cp[k] << 24) | (cp[k + 1] << 16) | (cp[k + 2] << 8) |
 137                         np[0];
 138         }
 139     bad:
 140         *err = 1;
 141         return 0;
 142 }
 143
 144 static int
 145 m_xhalf(m, k, err)
 146         register struct mbuf *m;
 147         register int k, *err;
 148 {
 149         register int len;
 150         register u_char *cp;
 151         register struct mbuf *m0;
 152
 153         len = m->m_len;
 154         while (k >= len) {
 155                 k -= len;
 156                 m = m->m_next;
 157                 if (m == 0)
 158                         goto bad;
 159                 len = m->m_len;
 160         }
 161         cp = mtod(m, u_char *) + k;
 162         if (len - k >= 2) {
 163                 *err = 0;
 164                 return EXTRACT_SHORT(cp);
 165         }
 166         m0 = m->m_next;
 167         if (m0 == 0)
 168                 goto bad;
 169         *err = 0;
 170         return (cp[k] << 8) | mtod(m0, u_char *)[0];
 171  bad:
 172         *err = 1;
 173         return 0;
 174 }
 175 #endif
 176
 177 #include <net/bpf.h>
 178
 179 /*
 180  * Execute the filter program starting at pc on the packet p
 181  * wirelen is the length of the original packet
 182  * buflen is the amount of data present
 183  */
 184 u_int
 185 bpf_filter(pc, p, wirelen, buflen)
 186         register struct bpf_insn *pc;
 187         register u_char *p;
 188         u_int wirelen;
 189         register u_int buflen;
 190 {
 191         register u_int32_t A, X;
 192         register int k;
 193         int32_t mem[BPF_MEMWORDS];
 194
 195         if (pc == 0)
 196                 /*
 197                  * No filter means accept all.
 198                  */
 199                 return (u_int)-1;
 200 #ifdef lint
 201         A = 0;
 202         X = 0;
 203 #endif
 204         --pc;
 205         while (1) {
 206                 ++pc;
 207                 switch (pc->code) {
 208
 209                 default:
 210 #ifdef KERNEL
 211                         return 0;
 212 #else
 213                         abort();
 214 #endif
 215                 case BPF_RET|BPF_K:
 216                         return (u_int)pc->k;
 217
 218                 case BPF_RET|BPF_A:
 219                         return (u_int)A;
 220
 221                 case BPF_LD|BPF_W|BPF_ABS:
 222                         k = pc->k;
 223                         if (k + sizeof(int32_t) > buflen) {
 224 #ifdef KERNEL
 225                                 int merr;
 226
 227                                 if (buflen != 0)
 228                                         return 0;
 229                                 A = m_xword((struct mbuf *)p, k, &merr);
 230                                 if (merr != 0)
 231                                         return 0;
 232                                 continue;
 233 #else
 234                                 return 0;
 235 #endif
 236                         }
 237 #ifdef BPF_ALIGN
 238                         if (((int)(p + k) & 3) != 0)
 239                                 A = EXTRACT_LONG(&p[k]);
 240                         else
 241 #endif
 242                                 A = ntohl(*(long *)(p + k));
 243                         continue;
 244
 245                 case BPF_LD|BPF_H|BPF_ABS:
 246                         k = pc->k;
 247                         if (k + sizeof(short) > buflen) {
 248 #ifdef KERNEL
 249                                 int merr;
 250
 251                                 if (buflen != 0)
 252                                         return 0;
 253                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 254                                 continue;
 255 #else
 256                                 return 0;
 257 #endif
 258                         }
 259                         A = EXTRACT_SHORT(&p[k]);
 260                         continue;
 261
 262                 case BPF_LD|BPF_B|BPF_ABS:
 263                         k = pc->k;
 264                         if (k >= buflen) {
 265 #ifdef KERNEL
 266                                 register struct mbuf *m;
 267
 268                                 if (buflen != 0)
 269                                         return 0;
 270                                 m = (struct mbuf *)p;
 271                                 MINDEX(m, k);
 272                                 A = mtod(m, u_char *)[k];
 273                                 continue;
 274 #else
 275                                 return 0;
 276 #endif
 277                         }
 278                         A = p[k];
 279                         continue;
 280
 281                 case BPF_LD|BPF_W|BPF_LEN:
 282                         A = wirelen;
 283                         continue;
 284
 285                 case BPF_LDX|BPF_W|BPF_LEN:
 286                         X = wirelen;
 287                         continue;
 288
 289                 case BPF_LD|BPF_W|BPF_IND:
 290                         k = X + pc->k;
 291                         if (k + sizeof(int32_t) > buflen) {
 292 #ifdef KERNEL
 293                                 int merr;
 294
 295                                 if (buflen != 0)
 296                                         return 0;
 297                                 A = m_xword((struct mbuf *)p, k, &merr);
 298                                 if (merr != 0)
 299                                         return 0;
 300                                 continue;
 301 #else
 302                                 return 0;
 303 #endif
 304                         }
 305 #ifdef BPF_ALIGN
 306                         if (((int)(p + k) & 3) != 0)
 307                                 A = EXTRACT_LONG(&p[k]);
 308                         else
 309 #endif
 310                                 A = ntohl(*(long *)(p + k));
 311                         continue;
 312
 313                 case BPF_LD|BPF_H|BPF_IND:
 314                         k = X + pc->k;
 315                         if (k + sizeof(short) > buflen) {
 316 #ifdef KERNEL
 317                                 int merr;
 318
 319                                 if (buflen != 0)
 320                                         return 0;
 321                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 322                                 if (merr != 0)
 323                                         return 0;
 324                                 continue;
 325 #else
 326                                 return 0;
 327 #endif
 328                         }
 329                         A = EXTRACT_SHORT(&p[k]);
 330                         continue;
 331
 332                 case BPF_LD|BPF_B|BPF_IND:
 333                         k = X + pc->k;
 334                         if (k >= buflen) {
 335 #ifdef KERNEL
 336                                 register struct mbuf *m;
 337
 338                                 if (buflen != 0)
 339                                         return 0;
 340                                 m = (struct mbuf *)p;
 341                                 MINDEX(m, k);
 342                                 A = mtod(m, char *)[k];
 343                                 continue;
 344 #else
 345                                 return 0;
 346 #endif
 347                         }
 348                         A = p[k];
 349                         continue;
 350
 351                 case BPF_LDX|BPF_MSH|BPF_B:
 352                         k = pc->k;
 353                         if (k >= buflen) {
 354 #ifdef KERNEL
 355                                 register struct mbuf *m;
 356
 357                                 if (buflen != 0)
 358                                         return 0;
 359                                 m = (struct mbuf *)p;
 360                                 MINDEX(m, k);
 361                                 X = (mtod(m, char *)[k] & 0xf) << 2;
 362                                 continue;
 363 #else
 364                                 return 0;
 365 #endif
 366                         }
 367                         X = (p[pc->k] & 0xf) << 2;
 368                         continue;
 369
 370                 case BPF_LD|BPF_IMM:
 371                         A = pc->k;
 372                         continue;
 373
 374                 case BPF_LDX|BPF_IMM:
 375                         X = pc->k;
 376                         continue;
 377
 378                 case BPF_LD|BPF_MEM:
 379                         A = mem[pc->k];
 380                         continue;
 381
 382                 case BPF_LDX|BPF_MEM:
 383                         X = mem[pc->k];
 384                         continue;
 385
 386                 case BPF_ST:
 387                         mem[pc->k] = A;
 388                         continue;
 389
 390                 case BPF_STX:
 391                         mem[pc->k] = X;
 392                         continue;
 393
 394                 case BPF_JMP|BPF_JA:
 395                         pc += pc->k;
 396                         continue;
 397
 398                 case BPF_JMP|BPF_JGT|BPF_K:
 399                         pc += (A > pc->k) ? pc->jt : pc->jf;
 400                         continue;
 401
 402                 case BPF_JMP|BPF_JGE|BPF_K:
 403                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 404                         continue;
 405
 406                 case BPF_JMP|BPF_JEQ|BPF_K:
 407                         pc += (A == pc->k) ? pc->jt : pc->jf;
 408                         continue;
 409
 410                 case BPF_JMP|BPF_JSET|BPF_K:
 411                         pc += (A & pc->k) ? pc->jt : pc->jf;
 412                         continue;
 413
 414                 case BPF_JMP|BPF_JGT|BPF_X:
 415                         pc += (A > X) ? pc->jt : pc->jf;
 416                         continue;
 417
 418                 case BPF_JMP|BPF_JGE|BPF_X:
 419                         pc += (A >= X) ? pc->jt : pc->jf;
 420                         continue;
 421
 422                 case BPF_JMP|BPF_JEQ|BPF_X:
 423                         pc += (A == X) ? pc->jt : pc->jf;
 424                         continue;
 425
 426                 case BPF_JMP|BPF_JSET|BPF_X:
 427                         pc += (A & X) ? pc->jt : pc->jf;
 428                         continue;
 429
 430                 case BPF_ALU|BPF_ADD|BPF_X:
 431                         A += X;
 432                         continue;
 433
 434                 case BPF_ALU|BPF_SUB|BPF_X:
 435                         A -= X;
 436                         continue;
 437
 438                 case BPF_ALU|BPF_MUL|BPF_X:
 439                         A *= X;
 440                         continue;
 441
 442                 case BPF_ALU|BPF_DIV|BPF_X:
 443                         if (X == 0)
 444                                 return 0;
 445                         A /= X;
 446                         continue;
 447
 448                 case BPF_ALU|BPF_AND|BPF_X:
 449                         A &= X;
 450                         continue;
 451
 452                 case BPF_ALU|BPF_OR|BPF_X:
 453                         A |= X;
 454                         continue;
 455
 456                 case BPF_ALU|BPF_LSH|BPF_X:
 457                         A <<= X;
 458                         continue;
 459
 460                 case BPF_ALU|BPF_RSH|BPF_X:
 461                         A >>= X;
 462                         continue;
 463
 464                 case BPF_ALU|BPF_ADD|BPF_K:
 465                         A += pc->k;
 466                         continue;
 467
 468                 case BPF_ALU|BPF_SUB|BPF_K:
 469                         A -= pc->k;
 470                         continue;
 471
 472                 case BPF_ALU|BPF_MUL|BPF_K:
 473                         A *= pc->k;
 474                         continue;
 475
 476                 case BPF_ALU|BPF_DIV|BPF_K:
 477                         A /= pc->k;
 478                         continue;
 479
 480                 case BPF_ALU|BPF_AND|BPF_K:
 481                         A &= pc->k;
 482                         continue;
 483
 484                 case BPF_ALU|BPF_OR|BPF_K:
 485                         A |= pc->k;
 486                         continue;
 487
 488                 case BPF_ALU|BPF_LSH|BPF_K:
 489                         A <<= pc->k;
 490                         continue;
 491
 492                 case BPF_ALU|BPF_RSH|BPF_K:
 493                         A >>= pc->k;
 494                         continue;
 495
 496                 case BPF_ALU|BPF_NEG:
 497                         A = -A;
 498                         continue;
 499
 500                 case BPF_MISC|BPF_TAX:
 501                         X = A;
 502                         continue;
 503
 504                 case BPF_MISC|BPF_TXA:
 505                         A = X;
 506                         continue;
 507                 }
 508         }
 509 }
 510
 511 #ifdef KERNEL
 512 /*
 513  * Return true if the 'fcode' is a valid filter program.
 514  * The constraints are that each jump be forward and to a valid
 515  * code.  The code must terminate with either an accept or reject.
 516  * 'valid' is an array for use by the routine (it must be at least
 517  * 'len' bytes long).
 518  *
 519  * The kernel needs to be able to verify an application's filter code.
 520  * Otherwise, a bogus program could easily crash the system.
 521  */
 522 int
 523 bpf_validate(f, len)
 524         struct bpf_insn *f;
 525         int len;
 526 {
 527         register int i;
 528         register struct bpf_insn *p;
 529
 530         for (i = 0; i < len; ++i) {
 531                 /*
 532                  * Check that that jumps are forward, and within
 533                  * the code block.
 534                  */
 535                 p = &f[i];
 536                 if (BPF_CLASS(p->code) == BPF_JMP) {
 537                         register int from = i + 1;
 538
 539                         if (BPF_OP(p->code) == BPF_JA) {
 540                                 if (from + p->k >= len)
 541                                         return 0;
 542                         }
 543                         else if (from + p->jt >= len || from + p->jf >= len)
 544                                 return 0;
 545                 }
 546                 /*
 547                  * Check that memory operations use valid addresses.
 548                  */
 549                 if ((BPF_CLASS(p->code) == BPF_ST ||
 550                      (BPF_CLASS(p->code) == BPF_LD &&
 551                       (p->code & 0xe0) == BPF_MEM)) &&
 552                     (p->k >= BPF_MEMWORDS || p->k < 0))
 553                         return 0;
 554                 /*
 555                  * Check for constant division by 0.
 556                  */
 557                 if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
 558                         return 0;
 559         }
 560         return BPF_CLASS(f[len - 1].code) == BPF_RET;
 561 }
 562 #endif
 563 #endif /* BPFDRV */