bsd/net/bpf_filter.c

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