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

Cache object: 73a170c2ae2d60d7c9488b5f2a9b448f


[ 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.