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 unsigned 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(struct mbuf *m, bpf_u_int32 k, int *err);
 108 static u_int32_t        m_xword(struct mbuf *m, bpf_u_int32 k, int *err);
 109
 110 static u_int32_t
 111 m_xword(struct mbuf *m, bpf_u_int32 k, int *err)
 112 {
 113         register size_t len;
 114         register u_char *cp, *np;
 115         register struct mbuf *m0;
 116
 117         len = m->m_len;
 118         while (k >= len) {
 119                 k -= len;
 120                 m = m->m_next;
 121                 if (m == 0)
 122                         goto bad;
 123                 len = m->m_len;
 124         }
 125         cp = mtod(m, u_char *) + k;
 126         if (len - k >= 4) {
 127                 *err = 0;
 128                 return EXTRACT_LONG(cp);
 129         }
 130         m0 = m->m_next;
 131         if (m0 == 0 || m0->m_len + len - k < 4)
 132                 goto bad;
 133         *err = 0;
 134         np = mtod(m0, u_char *);
 135         switch (len - k) {
 136
 137         case 1:
 138                 return
 139                     ((u_int32_t)cp[0] << 24) |
 140                     ((u_int32_t)np[0] << 16) |
 141                     ((u_int32_t)np[1] << 8)  |
 142                     (u_int32_t)np[2];
 143
 144         case 2:
 145                 return
 146                     ((u_int32_t)cp[0] << 24) |
 147                     ((u_int32_t)cp[1] << 16) |
 148                     ((u_int32_t)np[0] << 8) |
 149                     (u_int32_t)np[1];
 150
 151         default:
 152                 return
 153                     ((u_int32_t)cp[0] << 24) |
 154                     ((u_int32_t)cp[1] << 16) |
 155                     ((u_int32_t)cp[2] << 8) |
 156                     (u_int32_t)np[0];
 157         }
 158     bad:
 159         *err = 1;
 160         return 0;
 161 }
 162
 163 static u_int16_t
 164 m_xhalf(struct mbuf *m, bpf_u_int32 k, int *err)
 165 {
 166         register size_t len;
 167         register u_char *cp;
 168         register struct mbuf *m0;
 169
 170         len = m->m_len;
 171         while (k >= len) {
 172                 k -= len;
 173                 m = m->m_next;
 174                 if (m == 0)
 175                         goto bad;
 176                 len = m->m_len;
 177         }
 178         cp = mtod(m, u_char *) + k;
 179         if (len - k >= 2) {
 180                 *err = 0;
 181                 return EXTRACT_SHORT(cp);
 182         }
 183         m0 = m->m_next;
 184         if (m0 == 0)
 185                 goto bad;
 186         *err = 0;
 187         return (cp[0] << 8) | mtod(m0, u_char *)[0];
 188  bad:
 189         *err = 1;
 190         return 0;
 191 }
 192 #endif
 193
 194 /*
 195  * Execute the filter program starting at pc on the packet p
 196  * wirelen is the length of the original packet
 197  * buflen is the amount of data present
 198  */
 199 u_int
 200 bpf_filter(const struct bpf_insn *pc, u_char *p, u_int wirelen, u_int buflen)
 201 {
 202         register u_int32_t A = 0, X = 0;
 203         register bpf_u_int32 k;
 204         int32_t mem[BPF_MEMWORDS];
 205
 206         if (pc == 0)
 207                 /*
 208                  * No filter means accept all.
 209                  */
 210                 return (u_int)-1;
 211
 212         --pc;
 213         while (1) {
 214                 ++pc;
 215                 switch (pc->code) {
 216
 217                 default:
 218 #ifdef KERNEL
 219                         return 0;
 220 #else
 221                         abort();
 222 #endif
 223                 case BPF_RET|BPF_K:
 224                         return (u_int)pc->k;
 225
 226                 case BPF_RET|BPF_A:
 227                         return (u_int)A;
 228
 229                 case BPF_LD|BPF_W|BPF_ABS:
 230                         k = pc->k;
 231                         if (k > buflen || sizeof(int32_t) > buflen - k) {
 232 #ifdef KERNEL
 233                                 int merr;
 234
 235                                 if (buflen != 0)
 236                                         return 0;
 237                                 A = m_xword((struct mbuf *)p, k, &merr);
 238                                 if (merr != 0)
 239                                         return 0;
 240                                 continue;
 241 #else
 242                                 return 0;
 243 #endif
 244                         }
 245 #if BPF_ALIGN
 246                         if (((intptr_t)(p + k) & 3) != 0)
 247                                 A = EXTRACT_LONG(&p[k]);
 248                         else
 249 #endif
 250                                 A = ntohl(*(int32_t *)(p + k));
 251                         continue;
 252
 253                 case BPF_LD|BPF_H|BPF_ABS:
 254                         k = pc->k;
 255                         if (k > buflen || sizeof(int16_t) > buflen - k) {
 256 #ifdef KERNEL
 257                                 int merr;
 258
 259                                 if (buflen != 0)
 260                                         return 0;
 261                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 262                                 continue;
 263 #else
 264                                 return 0;
 265 #endif
 266                         }
 267                         A = EXTRACT_SHORT(&p[k]);
 268                         continue;
 269
 270                 case BPF_LD|BPF_B|BPF_ABS:
 271                         k = pc->k;
 272                         if (k >= buflen) {
 273 #ifdef KERNEL
 274                                 register struct mbuf *m;
 275
 276                                 if (buflen != 0)
 277                                         return 0;
 278                                 m = (struct mbuf *)p;
 279                                 MINDEX(m, k);
 280                                 A = mtod(m, u_char *)[k];
 281                                 continue;
 282 #else
 283                                 return 0;
 284 #endif
 285                         }
 286                         A = p[k];
 287                         continue;
 288
 289                 case BPF_LD|BPF_W|BPF_LEN:
 290                         A = wirelen;
 291                         continue;
 292
 293                 case BPF_LDX|BPF_W|BPF_LEN:
 294                         X = wirelen;
 295                         continue;
 296
 297                 case BPF_LD|BPF_W|BPF_IND:
 298                         k = X + pc->k;
 299                         if (pc->k > buflen || X > buflen - pc->k ||
 300                             sizeof(int32_t) > buflen - k) {
 301 #ifdef KERNEL
 302                                 int merr;
 303
 304                                 if (buflen != 0)
 305                                         return 0;
 306                                 A = m_xword((struct mbuf *)p, k, &merr);
 307                                 if (merr != 0)
 308                                         return 0;
 309                                 continue;
 310 #else
 311                                 return 0;
 312 #endif
 313                         }
 314 #if BPF_ALIGN
 315                         if (((intptr_t)(p + k) & 3) != 0)
 316                                 A = EXTRACT_LONG(&p[k]);
 317                         else
 318 #endif
 319                                 A = ntohl(*(int32_t *)(p + k));
 320                         continue;
 321
 322                 case BPF_LD|BPF_H|BPF_IND:
 323                         k = X + pc->k;
 324                         if (X > buflen || pc->k > buflen - X ||
 325                             sizeof(int16_t) > buflen - k) {
 326 #ifdef KERNEL
 327                                 int merr;
 328
 329                                 if (buflen != 0)
 330                                         return 0;
 331                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 332                                 if (merr != 0)
 333                                         return 0;
 334                                 continue;
 335 #else
 336                                 return 0;
 337 #endif
 338                         }
 339                         A = EXTRACT_SHORT(&p[k]);
 340                         continue;
 341
 342                 case BPF_LD|BPF_B|BPF_IND:
 343                         k = X + pc->k;
 344                         if (pc->k >= buflen || X >= buflen - pc->k) {
 345 #ifdef KERNEL
 346                                 register struct mbuf *m;
 347
 348                                 if (buflen != 0)
 349                                         return 0;
 350                                 m = (struct mbuf *)p;
 351                                 MINDEX(m, k);
 352                                 A = mtod(m, char *)[k];
 353                                 continue;
 354 #else
 355                                 return 0;
 356 #endif
 357                         }
 358                         A = p[k];
 359                         continue;
 360
 361                 case BPF_LDX|BPF_MSH|BPF_B:
 362                         k = pc->k;
 363                         if (k >= buflen) {
 364 #ifdef KERNEL
 365                                 register struct mbuf *m;
 366
 367                                 if (buflen != 0)
 368                                         return 0;
 369                                 m = (struct mbuf *)p;
 370                                 MINDEX(m, k);
 371                                 X = (mtod(m, char *)[k] & 0xf) << 2;
 372                                 continue;
 373 #else
 374                                 return 0;
 375 #endif
 376                         }
 377                         X = (p[pc->k] & 0xf) << 2;
 378                         continue;
 379
 380                 case BPF_LD|BPF_IMM:
 381                         A = pc->k;
 382                         continue;
 383
 384                 case BPF_LDX|BPF_IMM:
 385                         X = pc->k;
 386                         continue;
 387
 388                 case BPF_LD|BPF_MEM:
 389                         A = mem[pc->k];
 390                         continue;
 391
 392                 case BPF_LDX|BPF_MEM:
 393                         X = mem[pc->k];
 394                         continue;
 395
 396                 case BPF_ST:
 397                         mem[pc->k] = A;
 398                         continue;
 399
 400                 case BPF_STX:
 401                         mem[pc->k] = X;
 402                         continue;
 403
 404                 case BPF_JMP|BPF_JA:
 405                         pc += pc->k;
 406                         continue;
 407
 408                 case BPF_JMP|BPF_JGT|BPF_K:
 409                         pc += (A > pc->k) ? pc->jt : pc->jf;
 410                         continue;
 411
 412                 case BPF_JMP|BPF_JGE|BPF_K:
 413                         pc += (A >= pc->k) ? pc->jt : pc->jf;
 414                         continue;
 415
 416                 case BPF_JMP|BPF_JEQ|BPF_K:
 417                         pc += (A == pc->k) ? pc->jt : pc->jf;
 418                         continue;
 419
 420                 case BPF_JMP|BPF_JSET|BPF_K:
 421                         pc += (A & pc->k) ? pc->jt : pc->jf;
 422                         continue;
 423
 424                 case BPF_JMP|BPF_JGT|BPF_X:
 425                         pc += (A > X) ? pc->jt : pc->jf;
 426                         continue;
 427
 428                 case BPF_JMP|BPF_JGE|BPF_X:
 429                         pc += (A >= X) ? pc->jt : pc->jf;
 430                         continue;
 431
 432                 case BPF_JMP|BPF_JEQ|BPF_X:
 433                         pc += (A == X) ? pc->jt : pc->jf;
 434                         continue;
 435
 436                 case BPF_JMP|BPF_JSET|BPF_X:
 437                         pc += (A & X) ? pc->jt : pc->jf;
 438                         continue;
 439
 440                 case BPF_ALU|BPF_ADD|BPF_X:
 441                         A += X;
 442                         continue;
 443
 444                 case BPF_ALU|BPF_SUB|BPF_X:
 445                         A -= X;
 446                         continue;
 447
 448                 case BPF_ALU|BPF_MUL|BPF_X:
 449                         A *= X;
 450                         continue;
 451
 452                 case BPF_ALU|BPF_DIV|BPF_X:
 453                         if (X == 0)
 454                                 return 0;
 455                         A /= X;
 456                         continue;
 457
 458                 case BPF_ALU|BPF_AND|BPF_X:
 459                         A &= X;
 460                         continue;
 461
 462                 case BPF_ALU|BPF_OR|BPF_X:
 463                         A |= X;
 464                         continue;
 465
 466                 case BPF_ALU|BPF_LSH|BPF_X:
 467                         A <<= X;
 468                         continue;
 469
 470                 case BPF_ALU|BPF_RSH|BPF_X:
 471                         A >>= X;
 472                         continue;
 473
 474                 case BPF_ALU|BPF_ADD|BPF_K:
 475                         A += pc->k;
 476                         continue;
 477
 478                 case BPF_ALU|BPF_SUB|BPF_K:
 479                         A -= pc->k;
 480                         continue;
 481
 482                 case BPF_ALU|BPF_MUL|BPF_K:
 483                         A *= pc->k;
 484                         continue;
 485
 486                 case BPF_ALU|BPF_DIV|BPF_K:
 487                         A /= pc->k;
 488                         continue;
 489
 490                 case BPF_ALU|BPF_AND|BPF_K:
 491                         A &= pc->k;
 492                         continue;
 493
 494                 case BPF_ALU|BPF_OR|BPF_K:
 495                         A |= pc->k;
 496                         continue;
 497
 498                 case BPF_ALU|BPF_LSH|BPF_K:
 499                         A <<= pc->k;
 500                         continue;
 501
 502                 case BPF_ALU|BPF_RSH|BPF_K:
 503                         A >>= pc->k;
 504                         continue;
 505
 506                 case BPF_ALU|BPF_NEG:
 507                         A = -A;
 508                         continue;
 509
 510                 case BPF_MISC|BPF_TAX:
 511                         X = A;
 512                         continue;
 513
 514                 case BPF_MISC|BPF_TXA:
 515                         A = X;
 516                         continue;
 517                 }
 518         }
 519 }
 520
 521 #ifdef KERNEL
 522 /*
 523  * Return true if the 'fcode' is a valid filter program.
 524  * The constraints are that each jump be forward and to a valid
 525  * code.  The code must terminate with either an accept or reject.
 526  * 'valid' is an array for use by the routine (it must be at least
 527  * 'len' bytes long).
 528  *
 529  * The kernel needs to be able to verify an application's filter code.
 530  * Otherwise, a bogus program could easily crash the system.
 531  */
 532 int
 533 bpf_validate(const struct bpf_insn *f, int len)
 534 {
 535         register int i;
 536         const struct bpf_insn *p;
 537
 538         for (i = 0; i < len; ++i) {
 539                 /*
 540                  * Check that that jumps are forward, and within
 541                  * the code block.
 542                  */
 543                 p = &f[i];
 544                 if (BPF_CLASS(p->code) == BPF_JMP) {
 545                         register int from = i + 1;
 546
 547                         if (BPF_OP(p->code) == BPF_JA) {
 548                                 if (from >= len || p->k >= (bpf_u_int32)(len - from))
 549                                         return 0;
 550                         }
 551                         else if (from >= len || p->jt >= len - from ||
 552                                  p->jf >= len - from)
 553                                 return 0;
 554                 }
 555                 /*
 556                  * Check that memory operations use valid addresses.
 557                  */
 558                 if ((BPF_CLASS(p->code) == BPF_ST ||
 559                      (BPF_CLASS(p->code) == BPF_LD &&
 560                       (p->code & 0xe0) == BPF_MEM)) &&
 561                     p->k >= BPF_MEMWORDS)
 562                         return 0;
 563                 /*
 564                  * Check for constant division by 0.
 565                  */
 566                 if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
 567                         return 0;
 568         }
 569         return BPF_CLASS(f[len - 1].code) == BPF_RET;
 570 }
 571 #endif