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