The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/net/bpf_filter.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: b8f551e5362103ba504b3a6e00ef2528


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.