sys/net/bpf_filter.c

   1 /*
   2  * Copyright (c) 1990, 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from the Stanford/CMU enet packet filter,
   6  * (net/enet.c) distributed as part of 4.3BSD, and code contributed
   7  * to Berkeley by Steven McCanne and Van Jacobson both of Lawrence
   8  * Berkeley Laboratory.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      @(#)bpf_filter.c        8.1 (Berkeley) 6/10/93
  39  *
  40  * $FreeBSD: src/sys/net/bpf_filter.c,v 1.17 1999/12/29 04:38:31 peter Exp $
  41  * $DragonFly: src/sys/net/bpf_filter.c,v 1.4 2003/08/26 20:49:47 rob Exp $
  42  */
  43
  44 #include <sys/param.h>
  45
  46 #ifdef sun
  47 #include <netinet/in.h>
  48 #endif
  49
  50 #if defined(sparc) || defined(mips) || defined(ibm032) || defined(__alpha__)
  51 #define BPF_ALIGN
  52 #endif
  53
  54 #ifndef BPF_ALIGN
  55 #define EXTRACT_SHORT(p)        ((u_int16_t)ntohs(*(u_int16_t *)p))
  56 #define EXTRACT_LONG(p)         (ntohl(*(u_int32_t *)p))
  57 #else
  58 #define EXTRACT_SHORT(p)\
  59         ((u_int16_t)\
  60                 ((u_int16_t)*((u_char *)p+0)<<8|\
  61                  (u_int16_t)*((u_char *)p+1)<<0))
  62 #define EXTRACT_LONG(p)\
  63                 ((u_int32_t)*((u_char *)p+0)<<24|\
  64                  (u_int32_t)*((u_char *)p+1)<<16|\
  65                  (u_int32_t)*((u_char *)p+2)<<8|\
  66                  (u_int32_t)*((u_char *)p+3)<<0)
  67 #endif
  68
  69 #ifdef _KERNEL
  70 #include <sys/mbuf.h>
  71 #endif
  72 #include <net/bpf.h>
  73 #ifdef _KERNEL
  74 #define MINDEX(m, k) \
  75 { \
  76         int len = m->m_len; \
  77  \
  78         while (k >= len) { \
  79                 k -= len; \
  80                 m = m->m_next; \
  81                 if (m == 0) \
  82                         return 0; \
  83                 len = m->m_len; \
  84         } \
  85 }
  86
  87 static u_int16_t        m_xhalf (struct mbuf *m, bpf_u_int32 k, int *err);
  88 static u_int32_t        m_xword (struct mbuf *m, bpf_u_int32 k, int *err);
  89
  90 static u_int32_t
  91 m_xword(m, k, err)
  92         struct mbuf *m;
  93         bpf_u_int32 k;
  94         int *err;
  95 {
  96         size_t len;
  97         u_char *cp, *np;
  98         struct mbuf *m0;
  99
 100         len = m->m_len;
 101         while (k >= len) {
 102                 k -= len;
 103                 m = m->m_next;
 104                 if (m == 0)
 105                         goto bad;
 106                 len = m->m_len;
 107         }
 108         cp = mtod(m, u_char *) + k;
 109         if (len - k >= 4) {
 110                 *err = 0;
 111                 return EXTRACT_LONG(cp);
 112         }
 113         m0 = m->m_next;
 114         if (m0 == 0 || m0->m_len + len - k < 4)
 115                 goto bad;
 116         *err = 0;
 117         np = mtod(m0, u_char *);
 118         switch (len - k) {
 119
 120         case 1:
 121                 return
 122                     ((u_int32_t)cp[0] << 24) |
 123                     ((u_int32_t)np[0] << 16) |
 124                     ((u_int32_t)np[1] << 8)  |
 125                     (u_int32_t)np[2];
 126
 127         case 2:
 128                 return
 129                     ((u_int32_t)cp[0] << 24) |
 130                     ((u_int32_t)cp[1] << 16) |
 131                     ((u_int32_t)np[0] << 8) |
 132                     (u_int32_t)np[1];
 133
 134         default:
 135                 return
 136                     ((u_int32_t)cp[0] << 24) |
 137                     ((u_int32_t)cp[1] << 16) |
 138                     ((u_int32_t)cp[2] << 8) |
 139                     (u_int32_t)np[0];
 140         }
 141     bad:
 142         *err = 1;
 143         return 0;
 144 }
 145
 146 static u_int16_t
 147 m_xhalf(m, k, err)
 148         struct mbuf *m;
 149         bpf_u_int32 k;
 150         int *err;
 151 {
 152         size_t len;
 153         u_char *cp;
 154         struct mbuf *m0;
 155
 156         len = m->m_len;
 157         while (k >= len) {
 158                 k -= len;
 159                 m = m->m_next;
 160                 if (m == 0)
 161                         goto bad;
 162                 len = m->m_len;
 163         }
 164         cp = mtod(m, u_char *) + k;
 165         if (len - k >= 2) {
 166                 *err = 0;
 167                 return EXTRACT_SHORT(cp);
 168         }
 169         m0 = m->m_next;
 170         if (m0 == 0)
 171                 goto bad;
 172         *err = 0;
 173         return (cp[0] << 8) | mtod(m0, u_char *)[0];
 174  bad:
 175         *err = 1;
 176         return 0;
 177 }
 178 #endif
 179
 180 /*
 181  * Execute the filter program starting at pc on the packet p
 182  * wirelen is the length of the original packet
 183  * buflen is the amount of data present
 184  */
 185 u_int
 186 bpf_filter(pc, p, wirelen, buflen)
 187         const struct bpf_insn *pc;
 188         u_char *p;
 189         u_int wirelen;
 190         u_int buflen;
 191 {
 192         u_int32_t A = 0, X = 0;
 193         bpf_u_int32 k;
 194         int32_t mem[BPF_MEMWORDS];
 195
 196         if (pc == 0)
 197                 /*
 198                  * No filter means accept all.
 199                  */
 200                 return (u_int)-1;
 201
 202         --pc;
 203         while (1) {
 204                 ++pc;
 205                 switch (pc->code) {
 206
 207                 default:
 208 #ifdef _KERNEL
 209                         return 0;
 210 #else
 211                         abort();
 212 #endif
 213                 case BPF_RET|BPF_K:
 214                         return (u_int)pc->k;
 215
 216                 case BPF_RET|BPF_A:
 217                         return (u_int)A;
 218
 219                 case BPF_LD|BPF_W|BPF_ABS:
 220                         k = pc->k;
 221                         if (k > buflen || sizeof(int32_t) > buflen - k) {
 222 #ifdef _KERNEL
 223                                 int merr;
 224
 225                                 if (buflen != 0)
 226                                         return 0;
 227                                 A = m_xword((struct mbuf *)p, k, &merr);
 228                                 if (merr != 0)
 229                                         return 0;
 230                                 continue;
 231 #else
 232                                 return 0;
 233 #endif
 234                         }
 235 #ifdef BPF_ALIGN
 236                         if (((intptr_t)(p + k) & 3) != 0)
 237                                 A = EXTRACT_LONG(&p[k]);
 238                         else
 239 #endif
 240                                 A = ntohl(*(int32_t *)(p + k));
 241                         continue;
 242
 243                 case BPF_LD|BPF_H|BPF_ABS:
 244                         k = pc->k;
 245                         if (k > buflen || sizeof(int16_t) > buflen - k) {
 246 #ifdef _KERNEL
 247                                 int merr;
 248
 249                                 if (buflen != 0)
 250                                         return 0;
 251                                 A = m_xhalf((struct mbuf *)p, k, &merr);
 252                                 continue;
 253 #else
 254                                 return 0;
 255 #endif
 256                         }
 257                         A = EXTRACT_SHORT(&p[k]);
 258                         continue;
 259
 260                 case BPF_LD|BPF_B|BPF_ABS:
 261                         k = pc->k;
 262                         if (k >= buflen) {
 263 #ifdef _KERNEL
 264                                 struct mbuf *m;
 265
 266                                 if (buflen != 0)
 267                                         return 0;
 268                                 m = (struct mbuf *)p;
 269                                 MINDEX(m, k);
 270                                 A = mtod(m, u_char *)[k];
 271                                 continue;
 272 #else
 273                                 return 0;
 274 #endif
 275                         }
 276                         A = p[k];
 277                         continue;
 278
 279                 case BPF_LD|BPF_W|BPF_LEN:
 280                         A = wirelen;
 281                         continue;
 282
 283                 case BPF_LDX|BPF_W|BPF_LEN:
 284                         X = wirelen;
 285                         continue;
 286
 287                 case BPF_LD|BPF_W|BPF_IND:
 288                         k = X + pc->k;
 289                         if (pc->k > buflen || X > buflen - pc->k ||
 290                             sizeof(int32_t) > buflen - k) {
 291 #ifdef _KERNEL
 292                                 int merr;
 293
 294                                 if (buflen != 0)
 295                                         return 0;
 296                                 A = m_xword((struct mbuf *)p, k, &merr);
 297                                 if (merr != 0)
 298                                         return 0;
 299                                 continue;
 300 #else
 301                                 return 0;
 302 #endif
 303                         }
 304 #ifdef BPF_ALIGN
 305                         if (((intptr_t)(p + k) & 3) != 0)
 306                                 A = EXTRACT_LONG(&p[k]);
 307                         else
 308 #endif
 309                                 A = ntohl(*(int32_t *)(p + k));
 310                         continue;
 311
 312                 case BPF_LD|BPF_H|BPF_IND:
 313                         k = X + pc->k;
 314                         if (X > buflen || pc->k > buflen - X ||
 315                             sizeof(int16_t) > buflen - k) {
 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 (pc->k >= buflen || X >= buflen - pc->k) {
 335 #ifdef _KERNEL
 336                                 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                                 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  *
 517  * The kernel needs to be able to verify an application's filter code.
 518  * Otherwise, a bogus program could easily crash the system.
 519  */
 520 int
 521 bpf_validate(f, len)
 522         const struct bpf_insn *f;
 523         int len;
 524 {
 525         int i;
 526         const struct bpf_insn *p;
 527
 528         for (i = 0; i < len; ++i) {
 529                 /*
 530                  * Check that that jumps are forward, and within
 531                  * the code block.
 532                  */
 533                 p = &f[i];
 534                 if (BPF_CLASS(p->code) == BPF_JMP) {
 535                         int from = i + 1;
 536
 537                         if (BPF_OP(p->code) == BPF_JA) {
 538                                 if (from >= len || p->k >= len - from)
 539                                         return 0;
 540                         }
 541                         else if (from >= len || p->jt >= len - from ||
 542                                  p->jf >= len - from)
 543                                 return 0;
 544                 }
 545                 /*
 546                  * Check that memory operations use valid addresses.
 547                  */
 548                 if ((BPF_CLASS(p->code) == BPF_ST ||
 549                      (BPF_CLASS(p->code) == BPF_LD &&
 550                       (p->code & 0xe0) == BPF_MEM)) &&
 551                     p->k >= BPF_MEMWORDS)
 552                         return 0;
 553                 /*
 554                  * Check for constant division by 0.
 555                  */
 556                 if (p->code == (BPF_ALU|BPF_DIV|BPF_K) && p->k == 0)
 557                         return 0;
 558         }
 559         return BPF_CLASS(f[len - 1].code) == BPF_RET;
 560 }
 561 #endif