bsd/net/bpf_filter.c

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