net/core/filter.c

   1 /*
   2  * Linux Socket Filter - Kernel level socket filtering
   3  *
   4  * Based on the design of the Berkeley Packet Filter. The new
   5  * internal format has been designed by PLUMgrid:
   6  *
   7  *      Copyright (c) 2011 - 2014 PLUMgrid, http://plumgrid.com
   8  *
   9  * Authors:
  10  *
  11  *      Jay Schulist <jschlst@samba.org>
  12  *      Alexei Starovoitov <ast@plumgrid.com>
  13  *      Daniel Borkmann <dborkman@redhat.com>
  14  *
  15  * This program is free software; you can redistribute it and/or
  16  * modify it under the terms of the GNU General Public License
  17  * as published by the Free Software Foundation; either version
  18  * 2 of the License, or (at your option) any later version.
  19  *
  20  * Andi Kleen - Fix a few bad bugs and races.
  21  * Kris Katterjohn - Added many additional checks in sk_chk_filter()
  22  */
  23
  24 #include <linux/module.h>
  25 #include <linux/types.h>
  26 #include <linux/mm.h>
  27 #include <linux/fcntl.h>
  28 #include <linux/socket.h>
  29 #include <linux/in.h>
  30 #include <linux/inet.h>
  31 #include <linux/netdevice.h>
  32 #include <linux/if_packet.h>
  33 #include <linux/gfp.h>
  34 #include <net/ip.h>
  35 #include <net/protocol.h>
  36 #include <net/netlink.h>
  37 #include <linux/skbuff.h>
  38 #include <net/sock.h>
  39 #include <linux/errno.h>
  40 #include <linux/timer.h>
  41 #include <asm/uaccess.h>
  42 #include <asm/unaligned.h>
  43 #include <linux/filter.h>
  44 #include <linux/ratelimit.h>
  45 #include <linux/seccomp.h>
  46 #include <linux/if_vlan.h>
  47
  48 /* Registers */
  49 #define BPF_R0  regs[BPF_REG_0]
  50 #define BPF_R1  regs[BPF_REG_1]
  51 #define BPF_R2  regs[BPF_REG_2]
  52 #define BPF_R3  regs[BPF_REG_3]
  53 #define BPF_R4  regs[BPF_REG_4]
  54 #define BPF_R5  regs[BPF_REG_5]
  55 #define BPF_R6  regs[BPF_REG_6]
  56 #define BPF_R7  regs[BPF_REG_7]
  57 #define BPF_R8  regs[BPF_REG_8]
  58 #define BPF_R9  regs[BPF_REG_9]
  59 #define BPF_R10 regs[BPF_REG_10]
  60
  61 /* Named registers */
  62 #define A       regs[insn->a_reg]
  63 #define X       regs[insn->x_reg]
  64 #define FP      regs[BPF_REG_FP]
  65 #define ARG1    regs[BPF_REG_ARG1]
  66 #define CTX     regs[BPF_REG_CTX]
  67 #define K       insn->imm
  68
  69 /* No hurry in this branch
  70  *
  71  * Exported for the bpf jit load helper.
  72  */
  73 void *bpf_internal_load_pointer_neg_helper(const struct sk_buff *skb, int k, unsigned int size)
  74 {
  75         u8 *ptr = NULL;
  76
  77         if (k >= SKF_NET_OFF)
  78                 ptr = skb_network_header(skb) + k - SKF_NET_OFF;
  79         else if (k >= SKF_LL_OFF)
  80                 ptr = skb_mac_header(skb) + k - SKF_LL_OFF;
  81         if (ptr >= skb->head && ptr + size <= skb_tail_pointer(skb))
  82                 return ptr;
  83
  84         return NULL;
  85 }
  86
  87 static inline void *load_pointer(const struct sk_buff *skb, int k,
  88                                  unsigned int size, void *buffer)
  89 {
  90         if (k >= 0)
  91                 return skb_header_pointer(skb, k, size, buffer);
  92
  93         return bpf_internal_load_pointer_neg_helper(skb, k, size);
  94 }
  95
  96 /**
  97  *      sk_filter - run a packet through a socket filter
  98  *      @sk: sock associated with &sk_buff
  99  *      @skb: buffer to filter
 100  *
 101  * Run the filter code and then cut skb->data to correct size returned by
 102  * sk_run_filter. If pkt_len is 0 we toss packet. If skb->len is smaller
 103  * than pkt_len we keep whole skb->data. This is the socket level
 104  * wrapper to sk_run_filter. It returns 0 if the packet should
 105  * be accepted or -EPERM if the packet should be tossed.
 106  *
 107  */
 108 int sk_filter(struct sock *sk, struct sk_buff *skb)
 109 {
 110         int err;
 111         struct sk_filter *filter;
 112
 113         /*
 114          * If the skb was allocated from pfmemalloc reserves, only
 115          * allow SOCK_MEMALLOC sockets to use it as this socket is
 116          * helping free memory
 117          */
 118         if (skb_pfmemalloc(skb) && !sock_flag(sk, SOCK_MEMALLOC))
 119                 return -ENOMEM;
 120
 121         err = security_sock_rcv_skb(sk, skb);
 122         if (err)
 123                 return err;
 124
 125         rcu_read_lock();
 126         filter = rcu_dereference(sk->sk_filter);
 127         if (filter) {
 128                 unsigned int pkt_len = SK_RUN_FILTER(filter, skb);
 129
 130                 err = pkt_len ? pskb_trim(skb, pkt_len) : -EPERM;
 131         }
 132         rcu_read_unlock();
 133
 134         return err;
 135 }
 136 EXPORT_SYMBOL(sk_filter);
 137
 138 /* Base function for offset calculation. Needs to go into .text section,
 139  * therefore keeping it non-static as well; will also be used by JITs
 140  * anyway later on, so do not let the compiler omit it.
 141  */
 142 noinline u64 __bpf_call_base(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
 143 {
 144         return 0;
 145 }
 146
 147 /**
 148  *      __sk_run_filter - run a filter on a given context
 149  *      @ctx: buffer to run the filter on
 150  *      @insn: filter to apply
 151  *
 152  * Decode and apply filter instructions to the skb->data. Return length to
 153  * keep, 0 for none. @ctx is the data we are operating on, @insn is the
 154  * array of filter instructions.
 155  */
 156 static unsigned int __sk_run_filter(void *ctx, const struct sock_filter_int *insn)
 157 {
 158         u64 stack[MAX_BPF_STACK / sizeof(u64)];
 159         u64 regs[MAX_BPF_REG], tmp;
 160         static const void *jumptable[256] = {
 161                 [0 ... 255] = &&default_label,
 162                 /* Now overwrite non-defaults ... */
 163                 /* 32 bit ALU operations */
 164                 [BPF_ALU | BPF_ADD | BPF_X] = &&ALU_ADD_X,
 165                 [BPF_ALU | BPF_ADD | BPF_K] = &&ALU_ADD_K,
 166                 [BPF_ALU | BPF_SUB | BPF_X] = &&ALU_SUB_X,
 167                 [BPF_ALU | BPF_SUB | BPF_K] = &&ALU_SUB_K,
 168                 [BPF_ALU | BPF_AND | BPF_X] = &&ALU_AND_X,
 169                 [BPF_ALU | BPF_AND | BPF_K] = &&ALU_AND_K,
 170                 [BPF_ALU | BPF_OR | BPF_X]  = &&ALU_OR_X,
 171                 [BPF_ALU | BPF_OR | BPF_K]  = &&ALU_OR_K,
 172                 [BPF_ALU | BPF_LSH | BPF_X] = &&ALU_LSH_X,
 173                 [BPF_ALU | BPF_LSH | BPF_K] = &&ALU_LSH_K,
 174                 [BPF_ALU | BPF_RSH | BPF_X] = &&ALU_RSH_X,
 175                 [BPF_ALU | BPF_RSH | BPF_K] = &&ALU_RSH_K,
 176                 [BPF_ALU | BPF_XOR | BPF_X] = &&ALU_XOR_X,
 177                 [BPF_ALU | BPF_XOR | BPF_K] = &&ALU_XOR_K,
 178                 [BPF_ALU | BPF_MUL | BPF_X] = &&ALU_MUL_X,
 179                 [BPF_ALU | BPF_MUL | BPF_K] = &&ALU_MUL_K,
 180                 [BPF_ALU | BPF_MOV | BPF_X] = &&ALU_MOV_X,
 181                 [BPF_ALU | BPF_MOV | BPF_K] = &&ALU_MOV_K,
 182                 [BPF_ALU | BPF_DIV | BPF_X] = &&ALU_DIV_X,
 183                 [BPF_ALU | BPF_DIV | BPF_K] = &&ALU_DIV_K,
 184                 [BPF_ALU | BPF_MOD | BPF_X] = &&ALU_MOD_X,
 185                 [BPF_ALU | BPF_MOD | BPF_K] = &&ALU_MOD_K,
 186                 [BPF_ALU | BPF_NEG] = &&ALU_NEG,
 187                 [BPF_ALU | BPF_END | BPF_TO_BE] = &&ALU_END_TO_BE,
 188                 [BPF_ALU | BPF_END | BPF_TO_LE] = &&ALU_END_TO_LE,
 189                 /* 64 bit ALU operations */
 190                 [BPF_ALU64 | BPF_ADD | BPF_X] = &&ALU64_ADD_X,
 191                 [BPF_ALU64 | BPF_ADD | BPF_K] = &&ALU64_ADD_K,
 192                 [BPF_ALU64 | BPF_SUB | BPF_X] = &&ALU64_SUB_X,
 193                 [BPF_ALU64 | BPF_SUB | BPF_K] = &&ALU64_SUB_K,
 194                 [BPF_ALU64 | BPF_AND | BPF_X] = &&ALU64_AND_X,
 195                 [BPF_ALU64 | BPF_AND | BPF_K] = &&ALU64_AND_K,
 196                 [BPF_ALU64 | BPF_OR | BPF_X] = &&ALU64_OR_X,
 197                 [BPF_ALU64 | BPF_OR | BPF_K] = &&ALU64_OR_K,
 198                 [BPF_ALU64 | BPF_LSH | BPF_X] = &&ALU64_LSH_X,
 199                 [BPF_ALU64 | BPF_LSH | BPF_K] = &&ALU64_LSH_K,
 200                 [BPF_ALU64 | BPF_RSH | BPF_X] = &&ALU64_RSH_X,
 201                 [BPF_ALU64 | BPF_RSH | BPF_K] = &&ALU64_RSH_K,
 202                 [BPF_ALU64 | BPF_XOR | BPF_X] = &&ALU64_XOR_X,
 203                 [BPF_ALU64 | BPF_XOR | BPF_K] = &&ALU64_XOR_K,
 204                 [BPF_ALU64 | BPF_MUL | BPF_X] = &&ALU64_MUL_X,
 205                 [BPF_ALU64 | BPF_MUL | BPF_K] = &&ALU64_MUL_K,
 206                 [BPF_ALU64 | BPF_MOV | BPF_X] = &&ALU64_MOV_X,
 207                 [BPF_ALU64 | BPF_MOV | BPF_K] = &&ALU64_MOV_K,
 208                 [BPF_ALU64 | BPF_ARSH | BPF_X] = &&ALU64_ARSH_X,
 209                 [BPF_ALU64 | BPF_ARSH | BPF_K] = &&ALU64_ARSH_K,
 210                 [BPF_ALU64 | BPF_DIV | BPF_X] = &&ALU64_DIV_X,
 211                 [BPF_ALU64 | BPF_DIV | BPF_K] = &&ALU64_DIV_K,
 212                 [BPF_ALU64 | BPF_MOD | BPF_X] = &&ALU64_MOD_X,
 213                 [BPF_ALU64 | BPF_MOD | BPF_K] = &&ALU64_MOD_K,
 214                 [BPF_ALU64 | BPF_NEG] = &&ALU64_NEG,
 215                 /* Call instruction */
 216                 [BPF_JMP | BPF_CALL] = &&JMP_CALL,
 217                 /* Jumps */
 218                 [BPF_JMP | BPF_JA] = &&JMP_JA,
 219                 [BPF_JMP | BPF_JEQ | BPF_X] = &&JMP_JEQ_X,
 220                 [BPF_JMP | BPF_JEQ | BPF_K] = &&JMP_JEQ_K,
 221                 [BPF_JMP | BPF_JNE | BPF_X] = &&JMP_JNE_X,
 222                 [BPF_JMP | BPF_JNE | BPF_K] = &&JMP_JNE_K,
 223                 [BPF_JMP | BPF_JGT | BPF_X] = &&JMP_JGT_X,
 224                 [BPF_JMP | BPF_JGT | BPF_K] = &&JMP_JGT_K,
 225                 [BPF_JMP | BPF_JGE | BPF_X] = &&JMP_JGE_X,
 226                 [BPF_JMP | BPF_JGE | BPF_K] = &&JMP_JGE_K,
 227                 [BPF_JMP | BPF_JSGT | BPF_X] = &&JMP_JSGT_X,
 228                 [BPF_JMP | BPF_JSGT | BPF_K] = &&JMP_JSGT_K,
 229                 [BPF_JMP | BPF_JSGE | BPF_X] = &&JMP_JSGE_X,
 230                 [BPF_JMP | BPF_JSGE | BPF_K] = &&JMP_JSGE_K,
 231                 [BPF_JMP | BPF_JSET | BPF_X] = &&JMP_JSET_X,
 232                 [BPF_JMP | BPF_JSET | BPF_K] = &&JMP_JSET_K,
 233                 /* Program return */
 234                 [BPF_JMP | BPF_EXIT] = &&JMP_EXIT,
 235                 /* Store instructions */
 236                 [BPF_STX | BPF_MEM | BPF_B] = &&STX_MEM_B,
 237                 [BPF_STX | BPF_MEM | BPF_H] = &&STX_MEM_H,
 238                 [BPF_STX | BPF_MEM | BPF_W] = &&STX_MEM_W,
 239                 [BPF_STX | BPF_MEM | BPF_DW] = &&STX_MEM_DW,
 240                 [BPF_STX | BPF_XADD | BPF_W] = &&STX_XADD_W,
 241                 [BPF_STX | BPF_XADD | BPF_DW] = &&STX_XADD_DW,
 242                 [BPF_ST | BPF_MEM | BPF_B] = &&ST_MEM_B,
 243                 [BPF_ST | BPF_MEM | BPF_H] = &&ST_MEM_H,
 244                 [BPF_ST | BPF_MEM | BPF_W] = &&ST_MEM_W,
 245                 [BPF_ST | BPF_MEM | BPF_DW] = &&ST_MEM_DW,
 246                 /* Load instructions */
 247                 [BPF_LDX | BPF_MEM | BPF_B] = &&LDX_MEM_B,
 248                 [BPF_LDX | BPF_MEM | BPF_H] = &&LDX_MEM_H,
 249                 [BPF_LDX | BPF_MEM | BPF_W] = &&LDX_MEM_W,
 250                 [BPF_LDX | BPF_MEM | BPF_DW] = &&LDX_MEM_DW,
 251                 [BPF_LD | BPF_ABS | BPF_W] = &&LD_ABS_W,
 252                 [BPF_LD | BPF_ABS | BPF_H] = &&LD_ABS_H,
 253                 [BPF_LD | BPF_ABS | BPF_B] = &&LD_ABS_B,
 254                 [BPF_LD | BPF_IND | BPF_W] = &&LD_IND_W,
 255                 [BPF_LD | BPF_IND | BPF_H] = &&LD_IND_H,
 256                 [BPF_LD | BPF_IND | BPF_B] = &&LD_IND_B,
 257         };
 258         void *ptr;
 259         int off;
 260
 261 #define CONT     ({ insn++; goto select_insn; })
 262 #define CONT_JMP ({ insn++; goto select_insn; })
 263
 264         FP = (u64) (unsigned long) &stack[ARRAY_SIZE(stack)];
 265         ARG1 = (u64) (unsigned long) ctx;
 266
 267         /* Register for user BPF programs need to be reset first. */
 268         regs[BPF_REG_A] = 0;
 269         regs[BPF_REG_X] = 0;
 270
 271 select_insn:
 272         goto *jumptable[insn->code];
 273
 274         /* ALU */
 275 #define ALU(OPCODE, OP)                 \
 276         ALU64_##OPCODE##_X:             \
 277                 A = A OP X;             \
 278                 CONT;                   \
 279         ALU_##OPCODE##_X:               \
 280                 A = (u32) A OP (u32) X; \
 281                 CONT;                   \
 282         ALU64_##OPCODE##_K:             \
 283                 A = A OP K;             \
 284                 CONT;                   \
 285         ALU_##OPCODE##_K:               \
 286                 A = (u32) A OP (u32) K; \
 287                 CONT;
 288
 289         ALU(ADD,  +)
 290         ALU(SUB,  -)
 291         ALU(AND,  &)
 292         ALU(OR,   |)
 293         ALU(LSH, <<)
 294         ALU(RSH, >>)
 295         ALU(XOR,  ^)
 296         ALU(MUL,  *)
 297 #undef ALU
 298         ALU_NEG:
 299                 A = (u32) -A;
 300                 CONT;
 301         ALU64_NEG:
 302                 A = -A;
 303                 CONT;
 304         ALU_MOV_X:
 305                 A = (u32) X;
 306                 CONT;
 307         ALU_MOV_K:
 308                 A = (u32) K;
 309                 CONT;
 310         ALU64_MOV_X:
 311                 A = X;
 312                 CONT;
 313         ALU64_MOV_K:
 314                 A = K;
 315                 CONT;
 316         ALU64_ARSH_X:
 317                 (*(s64 *) &A) >>= X;
 318                 CONT;
 319         ALU64_ARSH_K:
 320                 (*(s64 *) &A) >>= K;
 321                 CONT;
 322         ALU64_MOD_X:
 323                 if (unlikely(X == 0))
 324                         return 0;
 325                 tmp = A;
 326                 A = do_div(tmp, X);
 327                 CONT;
 328         ALU_MOD_X:
 329                 if (unlikely(X == 0))
 330                         return 0;
 331                 tmp = (u32) A;
 332                 A = do_div(tmp, (u32) X);
 333                 CONT;
 334         ALU64_MOD_K:
 335                 tmp = A;
 336                 A = do_div(tmp, K);
 337                 CONT;
 338         ALU_MOD_K:
 339                 tmp = (u32) A;
 340                 A = do_div(tmp, (u32) K);
 341                 CONT;
 342         ALU64_DIV_X:
 343                 if (unlikely(X == 0))
 344                         return 0;
 345                 do_div(A, X);
 346                 CONT;
 347         ALU_DIV_X:
 348                 if (unlikely(X == 0))
 349                         return 0;
 350                 tmp = (u32) A;
 351                 do_div(tmp, (u32) X);
 352                 A = (u32) tmp;
 353                 CONT;
 354         ALU64_DIV_K:
 355                 do_div(A, K);
 356                 CONT;
 357         ALU_DIV_K:
 358                 tmp = (u32) A;
 359                 do_div(tmp, (u32) K);
 360                 A = (u32) tmp;
 361                 CONT;
 362         ALU_END_TO_BE:
 363                 switch (K) {
 364                 case 16:
 365                         A = (__force u16) cpu_to_be16(A);
 366                         break;
 367                 case 32:
 368                         A = (__force u32) cpu_to_be32(A);
 369                         break;
 370                 case 64:
 371                         A = (__force u64) cpu_to_be64(A);
 372                         break;
 373                 }
 374                 CONT;
 375         ALU_END_TO_LE:
 376                 switch (K) {
 377                 case 16:
 378                         A = (__force u16) cpu_to_le16(A);
 379                         break;
 380                 case 32:
 381                         A = (__force u32) cpu_to_le32(A);
 382                         break;
 383                 case 64:
 384                         A = (__force u64) cpu_to_le64(A);
 385                         break;
 386                 }
 387                 CONT;
 388
 389         /* CALL */
 390         JMP_CALL:
 391                 /* Function call scratches BPF_R1-BPF_R5 registers,
 392                  * preserves BPF_R6-BPF_R9, and stores return value
 393                  * into BPF_R0.
 394                  */
 395                 BPF_R0 = (__bpf_call_base + insn->imm)(BPF_R1, BPF_R2, BPF_R3,
 396                                                        BPF_R4, BPF_R5);
 397                 CONT;
 398
 399         /* JMP */
 400         JMP_JA:
 401                 insn += insn->off;
 402                 CONT;
 403         JMP_JEQ_X:
 404                 if (A == X) {
 405                         insn += insn->off;
 406                         CONT_JMP;
 407                 }
 408                 CONT;
 409         JMP_JEQ_K:
 410                 if (A == K) {
 411                         insn += insn->off;
 412                         CONT_JMP;
 413                 }
 414                 CONT;
 415         JMP_JNE_X:
 416                 if (A != X) {
 417                         insn += insn->off;
 418                         CONT_JMP;
 419                 }
 420                 CONT;
 421         JMP_JNE_K:
 422                 if (A != K) {
 423                         insn += insn->off;
 424                         CONT_JMP;
 425                 }
 426                 CONT;
 427         JMP_JGT_X:
 428                 if (A > X) {
 429                         insn += insn->off;
 430                         CONT_JMP;
 431                 }
 432                 CONT;
 433         JMP_JGT_K:
 434                 if (A > K) {
 435                         insn += insn->off;
 436                         CONT_JMP;
 437                 }
 438                 CONT;
 439         JMP_JGE_X:
 440                 if (A >= X) {
 441                         insn += insn->off;
 442                         CONT_JMP;
 443                 }
 444                 CONT;
 445         JMP_JGE_K:
 446                 if (A >= K) {
 447                         insn += insn->off;
 448                         CONT_JMP;
 449                 }
 450                 CONT;
 451         JMP_JSGT_X:
 452                 if (((s64) A) > ((s64) X)) {
 453                         insn += insn->off;
 454                         CONT_JMP;
 455                 }
 456                 CONT;
 457         JMP_JSGT_K:
 458                 if (((s64) A) > ((s64) K)) {
 459                         insn += insn->off;
 460                         CONT_JMP;
 461                 }
 462                 CONT;
 463         JMP_JSGE_X:
 464                 if (((s64) A) >= ((s64) X)) {
 465                         insn += insn->off;
 466                         CONT_JMP;
 467                 }
 468                 CONT;
 469         JMP_JSGE_K:
 470                 if (((s64) A) >= ((s64) K)) {
 471                         insn += insn->off;
 472                         CONT_JMP;
 473                 }
 474                 CONT;
 475         JMP_JSET_X:
 476                 if (A & X) {
 477                         insn += insn->off;
 478                         CONT_JMP;
 479                 }
 480                 CONT;
 481         JMP_JSET_K:
 482                 if (A & K) {
 483                         insn += insn->off;
 484                         CONT_JMP;
 485                 }
 486                 CONT;
 487         JMP_EXIT:
 488                 return BPF_R0;
 489
 490         /* STX and ST and LDX*/
 491 #define LDST(SIZEOP, SIZE)                                      \
 492         STX_MEM_##SIZEOP:                                       \
 493                 *(SIZE *)(unsigned long) (A + insn->off) = X;   \
 494                 CONT;                                           \
 495         ST_MEM_##SIZEOP:                                        \
 496                 *(SIZE *)(unsigned long) (A + insn->off) = K;   \
 497                 CONT;                                           \
 498         LDX_MEM_##SIZEOP:                                       \
 499                 A = *(SIZE *)(unsigned long) (X + insn->off);   \
 500                 CONT;
 501
 502         LDST(B,   u8)
 503         LDST(H,  u16)
 504         LDST(W,  u32)
 505         LDST(DW, u64)
 506 #undef LDST
 507         STX_XADD_W: /* lock xadd *(u32 *)(A + insn->off) += X */
 508                 atomic_add((u32) X, (atomic_t *)(unsigned long)
 509                            (A + insn->off));
 510                 CONT;
 511         STX_XADD_DW: /* lock xadd *(u64 *)(A + insn->off) += X */
 512                 atomic64_add((u64) X, (atomic64_t *)(unsigned long)
 513                              (A + insn->off));
 514                 CONT;
 515         LD_ABS_W: /* BPF_R0 = ntohl(*(u32 *) (skb->data + K)) */
 516                 off = K;
 517 load_word:
 518                 /* BPF_LD + BPD_ABS and BPF_LD + BPF_IND insns are
 519                  * only appearing in the programs where ctx ==
 520                  * skb. All programs keep 'ctx' in regs[BPF_REG_CTX]
 521                  * == BPF_R6, sk_convert_filter() saves it in BPF_R6,
 522                  * internal BPF verifier will check that BPF_R6 ==
 523                  * ctx.
 524                  *
 525                  * BPF_ABS and BPF_IND are wrappers of function calls,
 526                  * so they scratch BPF_R1-BPF_R5 registers, preserve
 527                  * BPF_R6-BPF_R9, and store return value into BPF_R0.
 528                  *
 529                  * Implicit input:
 530                  *   ctx
 531                  *
 532                  * Explicit input:
 533                  *   X == any register
 534                  *   K == 32-bit immediate
 535                  *
 536                  * Output:
 537                  *   BPF_R0 - 8/16/32-bit skb data converted to cpu endianness
 538                  */
 539
 540                 ptr = load_pointer((struct sk_buff *) ctx, off, 4, &tmp);
 541                 if (likely(ptr != NULL)) {
 542                         BPF_R0 = get_unaligned_be32(ptr);
 543                         CONT;
 544                 }
 545
 546                 return 0;
 547         LD_ABS_H: /* BPF_R0 = ntohs(*(u16 *) (skb->data + K)) */
 548                 off = K;
 549 load_half:
 550                 ptr = load_pointer((struct sk_buff *) ctx, off, 2, &tmp);
 551                 if (likely(ptr != NULL)) {
 552                         BPF_R0 = get_unaligned_be16(ptr);
 553                         CONT;
 554                 }
 555
 556                 return 0;
 557         LD_ABS_B: /* BPF_R0 = *(u8 *) (ctx + K) */
 558                 off = K;
 559 load_byte:
 560                 ptr = load_pointer((struct sk_buff *) ctx, off, 1, &tmp);
 561                 if (likely(ptr != NULL)) {
 562                         BPF_R0 = *(u8 *)ptr;
 563                         CONT;
 564                 }
 565
 566                 return 0;
 567         LD_IND_W: /* BPF_R0 = ntohl(*(u32 *) (skb->data + X + K)) */
 568                 off = K + X;
 569                 goto load_word;
 570         LD_IND_H: /* BPF_R0 = ntohs(*(u16 *) (skb->data + X + K)) */
 571                 off = K + X;
 572                 goto load_half;
 573         LD_IND_B: /* BPF_R0 = *(u8 *) (skb->data + X + K) */
 574                 off = K + X;
 575                 goto load_byte;
 576
 577         default_label:
 578                 /* If we ever reach this, we have a bug somewhere. */
 579                 WARN_RATELIMIT(1, "unknown opcode %02x\n", insn->code);
 580                 return 0;
 581 }
 582
 583 /* Helper to find the offset of pkt_type in sk_buff structure. We want
 584  * to make sure its still a 3bit field starting at a byte boundary;
 585  * taken from arch/x86/net/bpf_jit_comp.c.
 586  */
 587 #define PKT_TYPE_MAX    7
 588 static unsigned int pkt_type_offset(void)
 589 {
 590         struct sk_buff skb_probe = { .pkt_type = ~0, };
 591         u8 *ct = (u8 *) &skb_probe;
 592         unsigned int off;
 593
 594         for (off = 0; off < sizeof(struct sk_buff); off++) {
 595                 if (ct[off] == PKT_TYPE_MAX)
 596                         return off;
 597         }
 598
 599         pr_err_once("Please fix %s, as pkt_type couldn't be found!\n", __func__);
 600         return -1;
 601 }
 602
 603 static u64 __skb_get_pay_offset(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 604 {
 605         return __skb_get_poff((struct sk_buff *)(unsigned long) ctx);
 606 }
 607
 608 static u64 __skb_get_nlattr(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 609 {
 610         struct sk_buff *skb = (struct sk_buff *)(unsigned long) ctx;
 611         struct nlattr *nla;
 612
 613         if (skb_is_nonlinear(skb))
 614                 return 0;
 615
 616         if (skb->len < sizeof(struct nlattr))
 617                 return 0;
 618
 619         if (a > skb->len - sizeof(struct nlattr))
 620                 return 0;
 621
 622         nla = nla_find((struct nlattr *) &skb->data[a], skb->len - a, x);
 623         if (nla)
 624                 return (void *) nla - (void *) skb->data;
 625
 626         return 0;
 627 }
 628
 629 static u64 __skb_get_nlattr_nest(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 630 {
 631         struct sk_buff *skb = (struct sk_buff *)(unsigned long) ctx;
 632         struct nlattr *nla;
 633
 634         if (skb_is_nonlinear(skb))
 635                 return 0;
 636
 637         if (skb->len < sizeof(struct nlattr))
 638                 return 0;
 639
 640         if (a > skb->len - sizeof(struct nlattr))
 641                 return 0;
 642
 643         nla = (struct nlattr *) &skb->data[a];
 644         if (nla->nla_len > skb->len - a)
 645                 return 0;
 646
 647         nla = nla_find_nested(nla, x);
 648         if (nla)
 649                 return (void *) nla - (void *) skb->data;
 650
 651         return 0;
 652 }
 653
 654 static u64 __get_raw_cpu_id(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 655 {
 656         return raw_smp_processor_id();
 657 }
 658
 659 /* note that this only generates 32-bit random numbers */
 660 static u64 __get_random_u32(u64 ctx, u64 a, u64 x, u64 r4, u64 r5)
 661 {
 662         return prandom_u32();
 663 }
 664
 665 static bool convert_bpf_extensions(struct sock_filter *fp,
 666                                    struct sock_filter_int **insnp)
 667 {
 668         struct sock_filter_int *insn = *insnp;
 669
 670         switch (fp->k) {
 671         case SKF_AD_OFF + SKF_AD_PROTOCOL:
 672                 BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, protocol) != 2);
 673
 674                 /* A = *(u16 *) (ctx + offsetof(protocol)) */
 675                 *insn++ = BPF_LDX_MEM(BPF_H, BPF_REG_A, BPF_REG_CTX,
 676                                       offsetof(struct sk_buff, protocol));
 677                 /* A = ntohs(A) [emitting a nop or swap16] */
 678                 *insn = BPF_ENDIAN(BPF_FROM_BE, BPF_REG_A, 16);
 679                 break;
 680
 681         case SKF_AD_OFF + SKF_AD_PKTTYPE:
 682                 *insn = BPF_LDX_MEM(BPF_B, BPF_REG_A, BPF_REG_CTX,
 683                                     pkt_type_offset());
 684                 if (insn->off < 0)
 685                         return false;
 686                 insn++;
 687                 *insn = BPF_ALU32_IMM(BPF_AND, BPF_REG_A, PKT_TYPE_MAX);
 688                 break;
 689
 690         case SKF_AD_OFF + SKF_AD_IFINDEX:
 691         case SKF_AD_OFF + SKF_AD_HATYPE:
 692                 BUILD_BUG_ON(FIELD_SIZEOF(struct net_device, ifindex) != 4);
 693                 BUILD_BUG_ON(FIELD_SIZEOF(struct net_device, type) != 2);
 694                 BUILD_BUG_ON(bytes_to_bpf_size(FIELD_SIZEOF(struct sk_buff, dev)) < 0);
 695
 696                 *insn++ = BPF_LDX_MEM(bytes_to_bpf_size(FIELD_SIZEOF(struct sk_buff, dev)),
 697                                       BPF_REG_TMP, BPF_REG_CTX,
 698                                       offsetof(struct sk_buff, dev));
 699                 /* if (tmp != 0) goto pc + 1 */
 700                 *insn++ = BPF_JMP_IMM(BPF_JNE, BPF_REG_TMP, 0, 1);
 701                 *insn++ = BPF_EXIT_INSN();
 702                 if (fp->k == SKF_AD_OFF + SKF_AD_IFINDEX)
 703                         *insn = BPF_LDX_MEM(BPF_W, BPF_REG_A, BPF_REG_TMP,
 704                                             offsetof(struct net_device, ifindex));
 705                 else
 706                         *insn = BPF_LDX_MEM(BPF_H, BPF_REG_A, BPF_REG_TMP,
 707                                             offsetof(struct net_device, type));
 708                 break;
 709
 710         case SKF_AD_OFF + SKF_AD_MARK:
 711                 BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, mark) != 4);
 712
 713                 *insn = BPF_LDX_MEM(BPF_W, BPF_REG_A, BPF_REG_CTX,
 714                                     offsetof(struct sk_buff, mark));
 715                 break;
 716
 717         case SKF_AD_OFF + SKF_AD_RXHASH:
 718                 BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, hash) != 4);
 719
 720                 *insn = BPF_LDX_MEM(BPF_W, BPF_REG_A, BPF_REG_CTX,
 721                                     offsetof(struct sk_buff, hash));
 722                 break;
 723
 724         case SKF_AD_OFF + SKF_AD_QUEUE:
 725                 BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, queue_mapping) != 2);
 726
 727                 *insn = BPF_LDX_MEM(BPF_H, BPF_REG_A, BPF_REG_CTX,
 728                                     offsetof(struct sk_buff, queue_mapping));
 729                 break;
 730
 731         case SKF_AD_OFF + SKF_AD_VLAN_TAG:
 732         case SKF_AD_OFF + SKF_AD_VLAN_TAG_PRESENT:
 733                 BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, vlan_tci) != 2);
 734                 BUILD_BUG_ON(VLAN_TAG_PRESENT != 0x1000);
 735
 736                 /* A = *(u16 *) (ctx + offsetof(vlan_tci)) */
 737                 *insn++ = BPF_LDX_MEM(BPF_H, BPF_REG_A, BPF_REG_CTX,
 738                                       offsetof(struct sk_buff, vlan_tci));
 739                 if (fp->k == SKF_AD_OFF + SKF_AD_VLAN_TAG) {
 740                         *insn = BPF_ALU32_IMM(BPF_AND, BPF_REG_A,
 741                                               ~VLAN_TAG_PRESENT);
 742                 } else {
 743                         /* A >>= 12 */
 744                         *insn++ = BPF_ALU32_IMM(BPF_RSH, BPF_REG_A, 12);
 745                         /* A &= 1 */
 746                         *insn = BPF_ALU32_IMM(BPF_AND, BPF_REG_A, 1);
 747                 }
 748                 break;
 749
 750         case SKF_AD_OFF + SKF_AD_PAY_OFFSET:
 751         case SKF_AD_OFF + SKF_AD_NLATTR:
 752         case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
 753         case SKF_AD_OFF + SKF_AD_CPU:
 754         case SKF_AD_OFF + SKF_AD_RANDOM:
 755                 /* arg1 = ctx */
 756                 *insn++ = BPF_MOV64_REG(BPF_REG_ARG1, BPF_REG_CTX);
 757                 /* arg2 = A */
 758                 *insn++ = BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_A);
 759                 /* arg3 = X */
 760                 *insn++ = BPF_MOV64_REG(BPF_REG_ARG3, BPF_REG_X);
 761                 /* Emit call(ctx, arg2=A, arg3=X) */
 762                 switch (fp->k) {
 763                 case SKF_AD_OFF + SKF_AD_PAY_OFFSET:
 764                         *insn = BPF_EMIT_CALL(__skb_get_pay_offset);
 765                         break;
 766                 case SKF_AD_OFF + SKF_AD_NLATTR:
 767                         *insn = BPF_EMIT_CALL(__skb_get_nlattr);
 768                         break;
 769                 case SKF_AD_OFF + SKF_AD_NLATTR_NEST:
 770                         *insn = BPF_EMIT_CALL(__skb_get_nlattr_nest);
 771                         break;
 772                 case SKF_AD_OFF + SKF_AD_CPU:
 773                         *insn = BPF_EMIT_CALL(__get_raw_cpu_id);
 774                         break;
 775                 case SKF_AD_OFF + SKF_AD_RANDOM:
 776                         *insn = BPF_EMIT_CALL(__get_random_u32);
 777                         break;
 778                 }
 779                 break;
 780
 781         case SKF_AD_OFF + SKF_AD_ALU_XOR_X:
 782                 /* A ^= X */
 783                 *insn = BPF_ALU32_REG(BPF_XOR, BPF_REG_A, BPF_REG_X);
 784                 break;
 785
 786         default:
 787                 /* This is just a dummy call to avoid letting the compiler
 788                  * evict __bpf_call_base() as an optimization. Placed here
 789                  * where no-one bothers.
 790                  */
 791                 BUG_ON(__bpf_call_base(0, 0, 0, 0, 0) != 0);
 792                 return false;
 793         }
 794
 795         *insnp = insn;
 796         return true;
 797 }
 798
 799 /**
 800  *      sk_convert_filter - convert filter program
 801  *      @prog: the user passed filter program
 802  *      @len: the length of the user passed filter program
 803  *      @new_prog: buffer where converted program will be stored
 804  *      @new_len: pointer to store length of converted program
 805  *
 806  * Remap 'sock_filter' style BPF instruction set to 'sock_filter_ext' style.
 807  * Conversion workflow:
 808  *
 809  * 1) First pass for calculating the new program length:
 810  *   sk_convert_filter(old_prog, old_len, NULL, &new_len)
 811  *
 812  * 2) 2nd pass to remap in two passes: 1st pass finds new
 813  *    jump offsets, 2nd pass remapping:
 814  *   new_prog = kmalloc(sizeof(struct sock_filter_int) * new_len);
 815  *   sk_convert_filter(old_prog, old_len, new_prog, &new_len);
 816  *
 817  * User BPF's register A is mapped to our BPF register 6, user BPF
 818  * register X is mapped to BPF register 7; frame pointer is always
 819  * register 10; Context 'void *ctx' is stored in register 1, that is,
 820  * for socket filters: ctx == 'struct sk_buff *', for seccomp:
 821  * ctx == 'struct seccomp_data *'.
 822  */
 823 int sk_convert_filter(struct sock_filter *prog, int len,
 824                       struct sock_filter_int *new_prog, int *new_len)
 825 {
 826         int new_flen = 0, pass = 0, target, i;
 827         struct sock_filter_int *new_insn;
 828         struct sock_filter *fp;
 829         int *addrs = NULL;
 830         u8 bpf_src;
 831
 832         BUILD_BUG_ON(BPF_MEMWORDS * sizeof(u32) > MAX_BPF_STACK);
 833         BUILD_BUG_ON(BPF_REG_FP + 1 != MAX_BPF_REG);
 834
 835         if (len <= 0 || len >= BPF_MAXINSNS)
 836                 return -EINVAL;
 837
 838         if (new_prog) {
 839                 addrs = kzalloc(len * sizeof(*addrs), GFP_KERNEL);
 840                 if (!addrs)
 841                         return -ENOMEM;
 842         }
 843
 844 do_pass:
 845         new_insn = new_prog;
 846         fp = prog;
 847
 848         if (new_insn)
 849                 *new_insn = BPF_MOV64_REG(BPF_REG_CTX, BPF_REG_ARG1);
 850         new_insn++;
 851
 852         for (i = 0; i < len; fp++, i++) {
 853                 struct sock_filter_int tmp_insns[6] = { };
 854                 struct sock_filter_int *insn = tmp_insns;
 855
 856                 if (addrs)
 857                         addrs[i] = new_insn - new_prog;
 858
 859                 switch (fp->code) {
 860                 /* All arithmetic insns and skb loads map as-is. */
 861                 case BPF_ALU | BPF_ADD | BPF_X:
 862                 case BPF_ALU | BPF_ADD | BPF_K:
 863                 case BPF_ALU | BPF_SUB | BPF_X:
 864                 case BPF_ALU | BPF_SUB | BPF_K:
 865                 case BPF_ALU | BPF_AND | BPF_X:
 866                 case BPF_ALU | BPF_AND | BPF_K:
 867                 case BPF_ALU | BPF_OR | BPF_X:
 868                 case BPF_ALU | BPF_OR | BPF_K:
 869                 case BPF_ALU | BPF_LSH | BPF_X:
 870                 case BPF_ALU | BPF_LSH | BPF_K:
 871                 case BPF_ALU | BPF_RSH | BPF_X:
 872                 case BPF_ALU | BPF_RSH | BPF_K:
 873                 case BPF_ALU | BPF_XOR | BPF_X:
 874                 case BPF_ALU | BPF_XOR | BPF_K:
 875                 case BPF_ALU | BPF_MUL | BPF_X:
 876                 case BPF_ALU | BPF_MUL | BPF_K:
 877                 case BPF_ALU | BPF_DIV | BPF_X:
 878                 case BPF_ALU | BPF_DIV | BPF_K:
 879                 case BPF_ALU | BPF_MOD | BPF_X:
 880                 case BPF_ALU | BPF_MOD | BPF_K:
 881                 case BPF_ALU | BPF_NEG:
 882                 case BPF_LD | BPF_ABS | BPF_W:
 883                 case BPF_LD | BPF_ABS | BPF_H:
 884                 case BPF_LD | BPF_ABS | BPF_B:
 885                 case BPF_LD | BPF_IND | BPF_W:
 886                 case BPF_LD | BPF_IND | BPF_H:
 887                 case BPF_LD | BPF_IND | BPF_B:
 888                         /* Check for overloaded BPF extension and
 889                          * directly convert it if found, otherwise
 890                          * just move on with mapping.
 891                          */
 892                         if (BPF_CLASS(fp->code) == BPF_LD &&
 893                             BPF_MODE(fp->code) == BPF_ABS &&
 894                             convert_bpf_extensions(fp, &insn))
 895                                 break;
 896
 897                         *insn = BPF_RAW_INSN(fp->code, BPF_REG_A, BPF_REG_X, 0, fp->k);
 898                         break;
 899
 900                 /* Jump transformation cannot use BPF block macros
 901                  * everywhere as offset calculation and target updates
 902                  * require a bit more work than the rest, i.e. jump
 903                  * opcodes map as-is, but offsets need adjustment.
 904                  */
 905
 906 #define BPF_EMIT_JMP                                                    \
 907         do {                                                            \
 908                 if (target >= len || target < 0)                        \
 909                         goto err;                                       \
 910                 insn->off = addrs ? addrs[target] - addrs[i] - 1 : 0;   \
 911                 /* Adjust pc relative offset for 2nd or 3rd insn. */    \
 912                 insn->off -= insn - tmp_insns;                          \
 913         } while (0)
 914
 915                 case BPF_JMP | BPF_JA:
 916                         target = i + fp->k + 1;
 917                         insn->code = fp->code;
 918                         BPF_EMIT_JMP;
 919                         break;
 920
 921                 case BPF_JMP | BPF_JEQ | BPF_K:
 922                 case BPF_JMP | BPF_JEQ | BPF_X:
 923                 case BPF_JMP | BPF_JSET | BPF_K:
 924                 case BPF_JMP | BPF_JSET | BPF_X:
 925                 case BPF_JMP | BPF_JGT | BPF_K:
 926                 case BPF_JMP | BPF_JGT | BPF_X:
 927                 case BPF_JMP | BPF_JGE | BPF_K:
 928                 case BPF_JMP | BPF_JGE | BPF_X:
 929                         if (BPF_SRC(fp->code) == BPF_K && (int) fp->k < 0) {
 930                                 /* BPF immediates are signed, zero extend
 931                                  * immediate into tmp register and use it
 932                                  * in compare insn.
 933                                  */
 934                                 *insn++ = BPF_MOV32_IMM(BPF_REG_TMP, fp->k);
 935
 936                                 insn->a_reg = BPF_REG_A;
 937                                 insn->x_reg = BPF_REG_TMP;
 938                                 bpf_src = BPF_X;
 939                         } else {
 940                                 insn->a_reg = BPF_REG_A;
 941                                 insn->x_reg = BPF_REG_X;
 942                                 insn->imm = fp->k;
 943                                 bpf_src = BPF_SRC(fp->code);
 944                         }
 945
 946                         /* Common case where 'jump_false' is next insn. */
 947                         if (fp->jf == 0) {
 948                                 insn->code = BPF_JMP | BPF_OP(fp->code) | bpf_src;
 949                                 target = i + fp->jt + 1;
 950                                 BPF_EMIT_JMP;
 951                                 break;
 952                         }
 953
 954                         /* Convert JEQ into JNE when 'jump_true' is next insn. */
 955                         if (fp->jt == 0 && BPF_OP(fp->code) == BPF_JEQ) {
 956                                 insn->code = BPF_JMP | BPF_JNE | bpf_src;
 957                                 target = i + fp->jf + 1;
 958                                 BPF_EMIT_JMP;
 959                                 break;
 960                         }
 961
 962                         /* Other jumps are mapped into two insns: Jxx and JA. */
 963                         target = i + fp->jt + 1;
 964                         insn->code = BPF_JMP | BPF_OP(fp->code) | bpf_src;
 965                         BPF_EMIT_JMP;
 966                         insn++;
 967
 968                         insn->code = BPF_JMP | BPF_JA;
 969                         target = i + fp->jf + 1;
 970                         BPF_EMIT_JMP;
 971                         break;
 972
 973                 /* ldxb 4 * ([14] & 0xf) is remaped into 6 insns. */
 974                 case BPF_LDX | BPF_MSH | BPF_B:
 975                         /* tmp = A */
 976                         *insn++ = BPF_MOV64_REG(BPF_REG_TMP, BPF_REG_A);
 977                         /* A = BPF_R0 = *(u8 *) (skb->data + K) */
 978                         *insn++ = BPF_LD_ABS(BPF_B, fp->k);
 979                         /* A &= 0xf */
 980                         *insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_A, 0xf);
 981                         /* A <<= 2 */
 982                         *insn++ = BPF_ALU32_IMM(BPF_LSH, BPF_REG_A, 2);
 983                         /* X = A */
 984                         *insn++ = BPF_MOV64_REG(BPF_REG_X, BPF_REG_A);
 985                         /* A = tmp */
 986                         *insn = BPF_MOV64_REG(BPF_REG_A, BPF_REG_TMP);
 987                         break;
 988
 989                 /* RET_K, RET_A are remaped into 2 insns. */
 990                 case BPF_RET | BPF_A:
 991                 case BPF_RET | BPF_K:
 992                         *insn++ = BPF_MOV32_RAW(BPF_RVAL(fp->code) == BPF_K ?
 993                                                 BPF_K : BPF_X, BPF_REG_0,
 994                                                 BPF_REG_A, fp->k);
 995                         *insn = BPF_EXIT_INSN();
 996                         break;
 997
 998                 /* Store to stack. */
 999                 case BPF_ST:
1000                 case BPF_STX:
1001                         *insn = BPF_STX_MEM(BPF_W, BPF_REG_FP, BPF_CLASS(fp->code) ==
1002                                             BPF_ST ? BPF_REG_A : BPF_REG_X,
1003                                             -(BPF_MEMWORDS - fp->k) * 4);
1004                         break;
1005
1006                 /* Load from stack. */
1007                 case BPF_LD | BPF_MEM:
1008                 case BPF_LDX | BPF_MEM:
1009                         *insn = BPF_LDX_MEM(BPF_W, BPF_CLASS(fp->code) == BPF_LD  ?
1010                                             BPF_REG_A : BPF_REG_X, BPF_REG_FP,
1011                                             -(BPF_MEMWORDS - fp->k) * 4);
1012                         break;
1013
1014                 /* A = K or X = K */
1015                 case BPF_LD | BPF_IMM:
1016                 case BPF_LDX | BPF_IMM:
1017                         *insn = BPF_MOV32_IMM(BPF_CLASS(fp->code) == BPF_LD ?
1018                                               BPF_REG_A : BPF_REG_X, fp->k);
1019                         break;
1020
1021                 /* X = A */
1022                 case BPF_MISC | BPF_TAX:
1023                         *insn = BPF_MOV64_REG(BPF_REG_X, BPF_REG_A);
1024                         break;
1025
1026                 /* A = X */
1027                 case BPF_MISC | BPF_TXA:
1028                         *insn = BPF_MOV64_REG(BPF_REG_A, BPF_REG_X);
1029                         break;
1030
1031                 /* A = skb->len or X = skb->len */
1032                 case BPF_LD | BPF_W | BPF_LEN:
1033                 case BPF_LDX | BPF_W | BPF_LEN:
1034                         *insn = BPF_LDX_MEM(BPF_W, BPF_CLASS(fp->code) == BPF_LD ?
1035                                             BPF_REG_A : BPF_REG_X, BPF_REG_CTX,
1036                                             offsetof(struct sk_buff, len));
1037                         break;
1038
1039                 /* Access seccomp_data fields. */
1040                 case BPF_LDX | BPF_ABS | BPF_W:
1041                         /* A = *(u32 *) (ctx + K) */
1042                         *insn = BPF_LDX_MEM(BPF_W, BPF_REG_A, BPF_REG_CTX, fp->k);
1043                         break;
1044
1045                 /* Unkown instruction. */
1046                 default:
1047                         goto err;
1048                 }
1049
1050                 insn++;
1051                 if (new_prog)
1052                         memcpy(new_insn, tmp_insns,
1053                                sizeof(*insn) * (insn - tmp_insns));
1054                 new_insn += insn - tmp_insns;
1055         }
1056
1057         if (!new_prog) {
1058                 /* Only calculating new length. */
1059                 *new_len = new_insn - new_prog;
1060                 return 0;
1061         }
1062
1063         pass++;
1064         if (new_flen != new_insn - new_prog) {
1065                 new_flen = new_insn - new_prog;
1066                 if (pass > 2)
1067                         goto err;
1068                 goto do_pass;
1069         }
1070
1071         kfree(addrs);
1072         BUG_ON(*new_len != new_flen);
1073         return 0;
1074 err:
1075         kfree(addrs);
1076         return -EINVAL;
1077 }
1078
1079 /* Security:
1080  *
1081  * A BPF program is able to use 16 cells of memory to store intermediate
1082  * values (check u32 mem[BPF_MEMWORDS] in sk_run_filter()).
1083  *
1084  * As we dont want to clear mem[] array for each packet going through
1085  * sk_run_filter(), we check that filter loaded by user never try to read
1086  * a cell if not previously written, and we check all branches to be sure
1087  * a malicious user doesn't try to abuse us.
1088  */
1089 static int check_load_and_stores(struct sock_filter *filter, int flen)
1090 {
1091         u16 *masks, memvalid = 0; /* One bit per cell, 16 cells */
1092         int pc, ret = 0;
1093
1094         BUILD_BUG_ON(BPF_MEMWORDS > 16);
1095
1096         masks = kmalloc(flen * sizeof(*masks), GFP_KERNEL);
1097         if (!masks)
1098                 return -ENOMEM;
1099
1100         memset(masks, 0xff, flen * sizeof(*masks));
1101
1102         for (pc = 0; pc < flen; pc++) {
1103                 memvalid &= masks[pc];
1104
1105                 switch (filter[pc].code) {
1106                 case BPF_ST:
1107                 case BPF_STX:
1108                         memvalid |= (1 << filter[pc].k);
1109                         break;
1110                 case BPF_LD | BPF_MEM:
1111                 case BPF_LDX | BPF_MEM:
1112                         if (!(memvalid & (1 << filter[pc].k))) {
1113                                 ret = -EINVAL;
1114                                 goto error;
1115                         }
1116                         break;
1117                 case BPF_JMP | BPF_JA:
1118                         /* A jump must set masks on target */
1119                         masks[pc + 1 + filter[pc].k] &= memvalid;
1120                         memvalid = ~0;
1121                         break;
1122                 case BPF_JMP | BPF_JEQ | BPF_K:
1123                 case BPF_JMP | BPF_JEQ | BPF_X:
1124                 case BPF_JMP | BPF_JGE | BPF_K:
1125                 case BPF_JMP | BPF_JGE | BPF_X:
1126                 case BPF_JMP | BPF_JGT | BPF_K:
1127                 case BPF_JMP | BPF_JGT | BPF_X:
1128                 case BPF_JMP | BPF_JSET | BPF_K:
1129                 case BPF_JMP | BPF_JSET | BPF_X:
1130                         /* A jump must set masks on targets */
1131                         masks[pc + 1 + filter[pc].jt] &= memvalid;
1132                         masks[pc + 1 + filter[pc].jf] &= memvalid;
1133                         memvalid = ~0;
1134                         break;
1135                 }
1136         }
1137 error:
1138         kfree(masks);
1139         return ret;
1140 }
1141
1142 static bool chk_code_allowed(u16 code_to_probe)
1143 {
1144         static const bool codes[] = {
1145                 /* 32 bit ALU operations */
1146                 [BPF_ALU | BPF_ADD | BPF_K] = true,
1147                 [BPF_ALU | BPF_ADD | BPF_X] = true,
1148                 [BPF_ALU | BPF_SUB | BPF_K] = true,
1149                 [BPF_ALU | BPF_SUB | BPF_X] = true,
1150                 [BPF_ALU | BPF_MUL | BPF_K] = true,
1151                 [BPF_ALU | BPF_MUL | BPF_X] = true,
1152                 [BPF_ALU | BPF_DIV | BPF_K] = true,
1153                 [BPF_ALU | BPF_DIV | BPF_X] = true,
1154                 [BPF_ALU | BPF_MOD | BPF_K] = true,
1155                 [BPF_ALU | BPF_MOD | BPF_X] = true,
1156                 [BPF_ALU | BPF_AND | BPF_K] = true,
1157                 [BPF_ALU | BPF_AND | BPF_X] = true,
1158                 [BPF_ALU | BPF_OR | BPF_K] = true,
1159                 [BPF_ALU | BPF_OR | BPF_X] = true,
1160                 [BPF_ALU | BPF_XOR | BPF_K] = true,
1161                 [BPF_ALU | BPF_XOR | BPF_X] = true,
1162                 [BPF_ALU | BPF_LSH | BPF_K] = true,
1163                 [BPF_ALU | BPF_LSH | BPF_X] = true,
1164                 [BPF_ALU | BPF_RSH | BPF_K] = true,
1165                 [BPF_ALU | BPF_RSH | BPF_X] = true,
1166                 [BPF_ALU | BPF_NEG] = true,
1167                 /* Load instructions */
1168                 [BPF_LD | BPF_W | BPF_ABS] = true,
1169                 [BPF_LD | BPF_H | BPF_ABS] = true,
1170                 [BPF_LD | BPF_B | BPF_ABS] = true,
1171                 [BPF_LD | BPF_W | BPF_LEN] = true,
1172                 [BPF_LD | BPF_W | BPF_IND] = true,
1173                 [BPF_LD | BPF_H | BPF_IND] = true,
1174                 [BPF_LD | BPF_B | BPF_IND] = true,
1175                 [BPF_LD | BPF_IMM] = true,
1176                 [BPF_LD | BPF_MEM] = true,
1177                 [BPF_LDX | BPF_W | BPF_LEN] = true,
1178                 [BPF_LDX | BPF_B | BPF_MSH] = true,
1179                 [BPF_LDX | BPF_IMM] = true,
1180                 [BPF_LDX | BPF_MEM] = true,
1181                 /* Store instructions */
1182                 [BPF_ST] = true,
1183                 [BPF_STX] = true,
1184                 /* Misc instructions */
1185                 [BPF_MISC | BPF_TAX] = true,
1186                 [BPF_MISC | BPF_TXA] = true,
1187                 /* Return instructions */
1188                 [BPF_RET | BPF_K] = true,
1189                 [BPF_RET | BPF_A] = true,
1190                 /* Jump instructions */
1191                 [BPF_JMP | BPF_JA] = true,
1192                 [BPF_JMP | BPF_JEQ | BPF_K] = true,
1193                 [BPF_JMP | BPF_JEQ | BPF_X] = true,
1194                 [BPF_JMP | BPF_JGE | BPF_K] = true,
1195                 [BPF_JMP | BPF_JGE | BPF_X] = true,
1196                 [BPF_JMP | BPF_JGT | BPF_K] = true,
1197                 [BPF_JMP | BPF_JGT | BPF_X] = true,
1198                 [BPF_JMP | BPF_JSET | BPF_K] = true,
1199                 [BPF_JMP | BPF_JSET | BPF_X] = true,
1200         };
1201
1202         if (code_to_probe >= ARRAY_SIZE(codes))
1203                 return false;
1204
1205         return codes[code_to_probe];
1206 }
1207
1208 /**
1209  *      sk_chk_filter - verify socket filter code
1210  *      @filter: filter to verify
1211  *      @flen: length of filter
1212  *
1213  * Check the user's filter code. If we let some ugly
1214  * filter code slip through kaboom! The filter must contain
1215  * no references or jumps that are out of range, no illegal
1216  * instructions, and must end with a RET instruction.
1217  *
1218  * All jumps are forward as they are not signed.
1219  *
1220  * Returns 0 if the rule set is legal or -EINVAL if not.
1221  */
1222 int sk_chk_filter(struct sock_filter *filter, unsigned int flen)
1223 {
1224         bool anc_found;
1225         int pc;
1226
1227         if (flen == 0 || flen > BPF_MAXINSNS)
1228                 return -EINVAL;
1229
1230         /* Check the filter code now */
1231         for (pc = 0; pc < flen; pc++) {
1232                 struct sock_filter *ftest = &filter[pc];
1233
1234                 /* May we actually operate on this code? */
1235                 if (!chk_code_allowed(ftest->code))
1236                         return -EINVAL;
1237
1238                 /* Some instructions need special checks */
1239                 switch (ftest->code) {
1240                 case BPF_ALU | BPF_DIV | BPF_K:
1241                 case BPF_ALU | BPF_MOD | BPF_K:
1242                         /* Check for division by zero */
1243                         if (ftest->k == 0)
1244                                 return -EINVAL;
1245                         break;
1246                 case BPF_LD | BPF_MEM:
1247                 case BPF_LDX | BPF_MEM:
1248                 case BPF_ST:
1249                 case BPF_STX:
1250                         /* Check for invalid memory addresses */
1251                         if (ftest->k >= BPF_MEMWORDS)
1252                                 return -EINVAL;
1253                         break;
1254                 case BPF_JMP | BPF_JA:
1255                         /* Note, the large ftest->k might cause loops.
1256                          * Compare this with conditional jumps below,
1257                          * where offsets are limited. --ANK (981016)
1258                          */
1259                         if (ftest->k >= (unsigned int)(flen - pc - 1))
1260                                 return -EINVAL;
1261                         break;
1262                 case BPF_JMP | BPF_JEQ | BPF_K:
1263                 case BPF_JMP | BPF_JEQ | BPF_X:
1264                 case BPF_JMP | BPF_JGE | BPF_K:
1265                 case BPF_JMP | BPF_JGE | BPF_X:
1266                 case BPF_JMP | BPF_JGT | BPF_K:
1267                 case BPF_JMP | BPF_JGT | BPF_X:
1268                 case BPF_JMP | BPF_JSET | BPF_K:
1269                 case BPF_JMP | BPF_JSET | BPF_X:
1270                         /* Both conditionals must be safe */
1271                         if (pc + ftest->jt + 1 >= flen ||
1272                             pc + ftest->jf + 1 >= flen)
1273                                 return -EINVAL;
1274                         break;
1275                 case BPF_LD | BPF_W | BPF_ABS:
1276                 case BPF_LD | BPF_H | BPF_ABS:
1277                 case BPF_LD | BPF_B | BPF_ABS:
1278                         anc_found = false;
1279                         if (bpf_anc_helper(ftest) & BPF_ANC)
1280                                 anc_found = true;
1281                         /* Ancillary operation unknown or unsupported */
1282                         if (anc_found == false && ftest->k >= SKF_AD_OFF)
1283                                 return -EINVAL;
1284                 }
1285         }
1286
1287         /* Last instruction must be a RET code */
1288         switch (filter[flen - 1].code) {
1289         case BPF_RET | BPF_K:
1290         case BPF_RET | BPF_A:
1291                 return check_load_and_stores(filter, flen);
1292         }
1293
1294         return -EINVAL;
1295 }
1296 EXPORT_SYMBOL(sk_chk_filter);
1297
1298 static int sk_store_orig_filter(struct sk_filter *fp,
1299                                 const struct sock_fprog *fprog)
1300 {
1301         unsigned int fsize = sk_filter_proglen(fprog);
1302         struct sock_fprog_kern *fkprog;
1303
1304         fp->orig_prog = kmalloc(sizeof(*fkprog), GFP_KERNEL);
1305         if (!fp->orig_prog)
1306                 return -ENOMEM;
1307
1308         fkprog = fp->orig_prog;
1309         fkprog->len = fprog->len;
1310         fkprog->filter = kmemdup(fp->insns, fsize, GFP_KERNEL);
1311         if (!fkprog->filter) {
1312                 kfree(fp->orig_prog);
1313                 return -ENOMEM;
1314         }
1315
1316         return 0;
1317 }
1318
1319 static void sk_release_orig_filter(struct sk_filter *fp)
1320 {
1321         struct sock_fprog_kern *fprog = fp->orig_prog;
1322
1323         if (fprog) {
1324                 kfree(fprog->filter);
1325                 kfree(fprog);
1326         }
1327 }
1328
1329 /**
1330  *      sk_filter_release_rcu - Release a socket filter by rcu_head
1331  *      @rcu: rcu_head that contains the sk_filter to free
1332  */
1333 static void sk_filter_release_rcu(struct rcu_head *rcu)
1334 {
1335         struct sk_filter *fp = container_of(rcu, struct sk_filter, rcu);
1336
1337         sk_release_orig_filter(fp);
1338         sk_filter_free(fp);
1339 }
1340
1341 /**
1342  *      sk_filter_release - release a socket filter
1343  *      @fp: filter to remove
1344  *
1345  *      Remove a filter from a socket and release its resources.
1346  */
1347 static void sk_filter_release(struct sk_filter *fp)
1348 {
1349         if (atomic_dec_and_test(&fp->refcnt))
1350                 call_rcu(&fp->rcu, sk_filter_release_rcu);
1351 }
1352
1353 void sk_filter_uncharge(struct sock *sk, struct sk_filter *fp)
1354 {
1355         atomic_sub(sk_filter_size(fp->len), &sk->sk_omem_alloc);
1356         sk_filter_release(fp);
1357 }
1358
1359 void sk_filter_charge(struct sock *sk, struct sk_filter *fp)
1360 {
1361         atomic_inc(&fp->refcnt);
1362         atomic_add(sk_filter_size(fp->len), &sk->sk_omem_alloc);
1363 }
1364
1365 static struct sk_filter *__sk_migrate_realloc(struct sk_filter *fp,
1366                                               struct sock *sk,
1367                                               unsigned int len)
1368 {
1369         struct sk_filter *fp_new;
1370
1371         if (sk == NULL)
1372                 return krealloc(fp, len, GFP_KERNEL);
1373
1374         fp_new = sock_kmalloc(sk, len, GFP_KERNEL);
1375         if (fp_new) {
1376                 *fp_new = *fp;
1377                 /* As we're kepping orig_prog in fp_new along,
1378                  * we need to make sure we're not evicting it
1379                  * from the old fp.
1380                  */
1381                 fp->orig_prog = NULL;
1382                 sk_filter_uncharge(sk, fp);
1383         }
1384
1385         return fp_new;
1386 }
1387
1388 static struct sk_filter *__sk_migrate_filter(struct sk_filter *fp,
1389                                              struct sock *sk)
1390 {
1391         struct sock_filter *old_prog;
1392         struct sk_filter *old_fp;
1393         int err, new_len, old_len = fp->len;
1394
1395         /* We are free to overwrite insns et al right here as it
1396          * won't be used at this point in time anymore internally
1397          * after the migration to the internal BPF instruction
1398          * representation.
1399          */
1400         BUILD_BUG_ON(sizeof(struct sock_filter) !=
1401                      sizeof(struct sock_filter_int));
1402
1403         /* Conversion cannot happen on overlapping memory areas,
1404          * so we need to keep the user BPF around until the 2nd
1405          * pass. At this time, the user BPF is stored in fp->insns.
1406          */
1407         old_prog = kmemdup(fp->insns, old_len * sizeof(struct sock_filter),
1408                            GFP_KERNEL);
1409         if (!old_prog) {
1410                 err = -ENOMEM;
1411                 goto out_err;
1412         }
1413
1414         /* 1st pass: calculate the new program length. */
1415         err = sk_convert_filter(old_prog, old_len, NULL, &new_len);
1416         if (err)
1417                 goto out_err_free;
1418
1419         /* Expand fp for appending the new filter representation. */
1420         old_fp = fp;
1421         fp = __sk_migrate_realloc(old_fp, sk, sk_filter_size(new_len));
1422         if (!fp) {
1423                 /* The old_fp is still around in case we couldn't
1424                  * allocate new memory, so uncharge on that one.
1425                  */
1426                 fp = old_fp;
1427                 err = -ENOMEM;
1428                 goto out_err_free;
1429         }
1430
1431         fp->len = new_len;
1432
1433         /* 2nd pass: remap sock_filter insns into sock_filter_int insns. */
1434         err = sk_convert_filter(old_prog, old_len, fp->insnsi, &new_len);
1435         if (err)
1436                 /* 2nd sk_convert_filter() can fail only if it fails
1437                  * to allocate memory, remapping must succeed. Note,
1438                  * that at this time old_fp has already been released
1439                  * by __sk_migrate_realloc().
1440                  */
1441                 goto out_err_free;
1442
1443         sk_filter_select_runtime(fp);
1444
1445         kfree(old_prog);
1446         return fp;
1447
1448 out_err_free:
1449         kfree(old_prog);
1450 out_err:
1451         /* Rollback filter setup. */
1452         if (sk != NULL)
1453                 sk_filter_uncharge(sk, fp);
1454         else
1455                 kfree(fp);
1456         return ERR_PTR(err);
1457 }
1458
1459 void __weak bpf_int_jit_compile(struct sk_filter *prog)
1460 {
1461 }
1462
1463 /**
1464  *      sk_filter_select_runtime - select execution runtime for BPF program
1465  *      @fp: sk_filter populated with internal BPF program
1466  *
1467  * try to JIT internal BPF program, if JIT is not available select interpreter
1468  * BPF program will be executed via SK_RUN_FILTER() macro
1469  */
1470 void sk_filter_select_runtime(struct sk_filter *fp)
1471 {
1472         fp->bpf_func = (void *) __sk_run_filter;
1473
1474         /* Probe if internal BPF can be JITed */
1475         bpf_int_jit_compile(fp);
1476 }
1477 EXPORT_SYMBOL_GPL(sk_filter_select_runtime);
1478
1479 /* free internal BPF program */
1480 void sk_filter_free(struct sk_filter *fp)
1481 {
1482         bpf_jit_free(fp);
1483 }
1484 EXPORT_SYMBOL_GPL(sk_filter_free);
1485
1486 static struct sk_filter *__sk_prepare_filter(struct sk_filter *fp,
1487                                              struct sock *sk)
1488 {
1489         int err;
1490
1491         fp->bpf_func = NULL;
1492         fp->jited = 0;
1493
1494         err = sk_chk_filter(fp->insns, fp->len);
1495         if (err)
1496                 return ERR_PTR(err);
1497
1498         /* Probe if we can JIT compile the filter and if so, do
1499          * the compilation of the filter.
1500          */
1501         bpf_jit_compile(fp);
1502
1503         /* JIT compiler couldn't process this filter, so do the
1504          * internal BPF translation for the optimized interpreter.
1505          */
1506         if (!fp->jited)
1507                 fp = __sk_migrate_filter(fp, sk);
1508
1509         return fp;
1510 }
1511
1512 /**
1513  *      sk_unattached_filter_create - create an unattached filter
1514  *      @fprog: the filter program
1515  *      @pfp: the unattached filter that is created
1516  *
1517  * Create a filter independent of any socket. We first run some
1518  * sanity checks on it to make sure it does not explode on us later.
1519  * If an error occurs or there is insufficient memory for the filter
1520  * a negative errno code is returned. On success the return is zero.
1521  */
1522 int sk_unattached_filter_create(struct sk_filter **pfp,
1523                                 struct sock_fprog_kern *fprog)
1524 {
1525         unsigned int fsize = sk_filter_proglen(fprog);
1526         struct sk_filter *fp;
1527
1528         /* Make sure new filter is there and in the right amounts. */
1529         if (fprog->filter == NULL)
1530                 return -EINVAL;
1531
1532         fp = kmalloc(sk_filter_size(fprog->len), GFP_KERNEL);
1533         if (!fp)
1534                 return -ENOMEM;
1535
1536         memcpy(fp->insns, fprog->filter, fsize);
1537
1538         atomic_set(&fp->refcnt, 1);
1539         fp->len = fprog->len;
1540         /* Since unattached filters are not copied back to user
1541          * space through sk_get_filter(), we do not need to hold
1542          * a copy here, and can spare us the work.
1543          */
1544         fp->orig_prog = NULL;
1545
1546         /* __sk_prepare_filter() already takes care of uncharging
1547          * memory in case something goes wrong.
1548          */
1549         fp = __sk_prepare_filter(fp, NULL);
1550         if (IS_ERR(fp))
1551                 return PTR_ERR(fp);
1552
1553         *pfp = fp;
1554         return 0;
1555 }
1556 EXPORT_SYMBOL_GPL(sk_unattached_filter_create);
1557
1558 void sk_unattached_filter_destroy(struct sk_filter *fp)
1559 {
1560         sk_filter_release(fp);
1561 }
1562 EXPORT_SYMBOL_GPL(sk_unattached_filter_destroy);
1563
1564 /**
1565  *      sk_attach_filter - attach a socket filter
1566  *      @fprog: the filter program
1567  *      @sk: the socket to use
1568  *
1569  * Attach the user's filter code. We first run some sanity checks on
1570  * it to make sure it does not explode on us later. If an error
1571  * occurs or there is insufficient memory for the filter a negative
1572  * errno code is returned. On success the return is zero.
1573  */
1574 int sk_attach_filter(struct sock_fprog *fprog, struct sock *sk)
1575 {
1576         struct sk_filter *fp, *old_fp;
1577         unsigned int fsize = sk_filter_proglen(fprog);
1578         unsigned int sk_fsize = sk_filter_size(fprog->len);
1579         int err;
1580
1581         if (sock_flag(sk, SOCK_FILTER_LOCKED))
1582                 return -EPERM;
1583
1584         /* Make sure new filter is there and in the right amounts. */
1585         if (fprog->filter == NULL)
1586                 return -EINVAL;
1587
1588         fp = sock_kmalloc(sk, sk_fsize, GFP_KERNEL);
1589         if (!fp)
1590                 return -ENOMEM;
1591
1592         if (copy_from_user(fp->insns, fprog->filter, fsize)) {
1593                 sock_kfree_s(sk, fp, sk_fsize);
1594                 return -EFAULT;
1595         }
1596
1597         atomic_set(&fp->refcnt, 1);
1598         fp->len = fprog->len;
1599
1600         err = sk_store_orig_filter(fp, fprog);
1601         if (err) {
1602                 sk_filter_uncharge(sk, fp);
1603                 return -ENOMEM;
1604         }
1605
1606         /* __sk_prepare_filter() already takes care of uncharging
1607          * memory in case something goes wrong.
1608          */
1609         fp = __sk_prepare_filter(fp, sk);
1610         if (IS_ERR(fp))
1611                 return PTR_ERR(fp);
1612
1613         old_fp = rcu_dereference_protected(sk->sk_filter,
1614                                            sock_owned_by_user(sk));
1615         rcu_assign_pointer(sk->sk_filter, fp);
1616
1617         if (old_fp)
1618                 sk_filter_uncharge(sk, old_fp);
1619
1620         return 0;
1621 }
1622 EXPORT_SYMBOL_GPL(sk_attach_filter);
1623
1624 int sk_detach_filter(struct sock *sk)
1625 {
1626         int ret = -ENOENT;
1627         struct sk_filter *filter;
1628
1629         if (sock_flag(sk, SOCK_FILTER_LOCKED))
1630                 return -EPERM;
1631
1632         filter = rcu_dereference_protected(sk->sk_filter,
1633                                            sock_owned_by_user(sk));
1634         if (filter) {
1635                 RCU_INIT_POINTER(sk->sk_filter, NULL);
1636                 sk_filter_uncharge(sk, filter);
1637                 ret = 0;
1638         }
1639
1640         return ret;
1641 }
1642 EXPORT_SYMBOL_GPL(sk_detach_filter);
1643
1644 int sk_get_filter(struct sock *sk, struct sock_filter __user *ubuf,
1645                   unsigned int len)
1646 {
1647         struct sock_fprog_kern *fprog;
1648         struct sk_filter *filter;
1649         int ret = 0;
1650
1651         lock_sock(sk);
1652         filter = rcu_dereference_protected(sk->sk_filter,
1653                                            sock_owned_by_user(sk));
1654         if (!filter)
1655                 goto out;
1656
1657         /* We're copying the filter that has been originally attached,
1658          * so no conversion/decode needed anymore.
1659          */
1660         fprog = filter->orig_prog;
1661
1662         ret = fprog->len;
1663         if (!len)
1664                 /* User space only enquires number of filter blocks. */
1665                 goto out;
1666
1667         ret = -EINVAL;
1668         if (len < fprog->len)
1669                 goto out;
1670
1671         ret = -EFAULT;
1672         if (copy_to_user(ubuf, fprog->filter, sk_filter_proglen(fprog)))
1673                 goto out;
1674
1675         /* Instead of bytes, the API requests to return the number
1676          * of filter blocks.
1677          */
1678         ret = fprog->len;
1679 out:
1680         release_sock(sk);
1681         return ret;
1682 }