tools/testing/selftests/bpf/test_align.c

   1 #include <asm/types.h>
   2 #include <linux/types.h>
   3 #include <stdint.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <unistd.h>
   7 #include <errno.h>
   8 #include <string.h>
   9 #include <stddef.h>
  10 #include <stdbool.h>
  11
  12 #include <linux/unistd.h>
  13 #include <linux/filter.h>
  14 #include <linux/bpf_perf_event.h>
  15 #include <linux/bpf.h>
  16
  17 #include <bpf/bpf.h>
  18
  19 #include "../../../include/linux/filter.h"
  20 #include "bpf_rlimit.h"
  21 #include "bpf_util.h"
  22
  23 #define MAX_INSNS       512
  24 #define MAX_MATCHES     16
  25
  26 struct bpf_reg_match {
  27         unsigned int line;
  28         const char *match;
  29 };
  30
  31 struct bpf_align_test {
  32         const char *descr;
  33         struct bpf_insn insns[MAX_INSNS];
  34         enum {
  35                 UNDEF,
  36                 ACCEPT,
  37                 REJECT
  38         } result;
  39         enum bpf_prog_type prog_type;
  40         /* Matches must be in order of increasing line */
  41         struct bpf_reg_match matches[MAX_MATCHES];
  42 };
  43
  44 static struct bpf_align_test tests[] = {
  45         /* Four tests of known constants.  These aren't staggeringly
  46          * interesting since we track exact values now.
  47          */
  48         {
  49                 .descr = "mov",
  50                 .insns = {
  51                         BPF_MOV64_IMM(BPF_REG_3, 2),
  52                         BPF_MOV64_IMM(BPF_REG_3, 4),
  53                         BPF_MOV64_IMM(BPF_REG_3, 8),
  54                         BPF_MOV64_IMM(BPF_REG_3, 16),
  55                         BPF_MOV64_IMM(BPF_REG_3, 32),
  56                         BPF_MOV64_IMM(BPF_REG_0, 0),
  57                         BPF_EXIT_INSN(),
  58                 },
  59                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
  60                 .matches = {
  61                         {1, "R1=ctx(id=0,off=0,imm=0)"},
  62                         {1, "R10=fp0"},
  63                         {1, "R3_w=inv2"},
  64                         {2, "R3_w=inv4"},
  65                         {3, "R3_w=inv8"},
  66                         {4, "R3_w=inv16"},
  67                         {5, "R3_w=inv32"},
  68                 },
  69         },
  70         {
  71                 .descr = "shift",
  72                 .insns = {
  73                         BPF_MOV64_IMM(BPF_REG_3, 1),
  74                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
  75                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
  76                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
  77                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
  78                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_3, 4),
  79                         BPF_MOV64_IMM(BPF_REG_4, 32),
  80                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
  81                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
  82                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
  83                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
  84                         BPF_MOV64_IMM(BPF_REG_0, 0),
  85                         BPF_EXIT_INSN(),
  86                 },
  87                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
  88                 .matches = {
  89                         {1, "R1=ctx(id=0,off=0,imm=0)"},
  90                         {1, "R10=fp0"},
  91                         {1, "R3_w=inv1"},
  92                         {2, "R3_w=inv2"},
  93                         {3, "R3_w=inv4"},
  94                         {4, "R3_w=inv8"},
  95                         {5, "R3_w=inv16"},
  96                         {6, "R3_w=inv1"},
  97                         {7, "R4_w=inv32"},
  98                         {8, "R4_w=inv16"},
  99                         {9, "R4_w=inv8"},
 100                         {10, "R4_w=inv4"},
 101                         {11, "R4_w=inv2"},
 102                 },
 103         },
 104         {
 105                 .descr = "addsub",
 106                 .insns = {
 107                         BPF_MOV64_IMM(BPF_REG_3, 4),
 108                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 4),
 109                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 2),
 110                         BPF_MOV64_IMM(BPF_REG_4, 8),
 111                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 112                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 2),
 113                         BPF_MOV64_IMM(BPF_REG_0, 0),
 114                         BPF_EXIT_INSN(),
 115                 },
 116                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 117                 .matches = {
 118                         {1, "R1=ctx(id=0,off=0,imm=0)"},
 119                         {1, "R10=fp0"},
 120                         {1, "R3_w=inv4"},
 121                         {2, "R3_w=inv8"},
 122                         {3, "R3_w=inv10"},
 123                         {4, "R4_w=inv8"},
 124                         {5, "R4_w=inv12"},
 125                         {6, "R4_w=inv14"},
 126                 },
 127         },
 128         {
 129                 .descr = "mul",
 130                 .insns = {
 131                         BPF_MOV64_IMM(BPF_REG_3, 7),
 132                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 1),
 133                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 2),
 134                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 4),
 135                         BPF_MOV64_IMM(BPF_REG_0, 0),
 136                         BPF_EXIT_INSN(),
 137                 },
 138                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 139                 .matches = {
 140                         {1, "R1=ctx(id=0,off=0,imm=0)"},
 141                         {1, "R10=fp0"},
 142                         {1, "R3_w=inv7"},
 143                         {2, "R3_w=inv7"},
 144                         {3, "R3_w=inv14"},
 145                         {4, "R3_w=inv56"},
 146                 },
 147         },
 148
 149         /* Tests using unknown values */
 150 #define PREP_PKT_POINTERS \
 151         BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, \
 152                     offsetof(struct __sk_buff, data)), \
 153         BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, \
 154                     offsetof(struct __sk_buff, data_end))
 155
 156 #define LOAD_UNKNOWN(DST_REG) \
 157         PREP_PKT_POINTERS, \
 158         BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), \
 159         BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 8), \
 160         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_0, 1), \
 161         BPF_EXIT_INSN(), \
 162         BPF_LDX_MEM(BPF_B, DST_REG, BPF_REG_2, 0)
 163
 164         {
 165                 .descr = "unknown shift",
 166                 .insns = {
 167                         LOAD_UNKNOWN(BPF_REG_3),
 168                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 169                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 170                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 171                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 172                         LOAD_UNKNOWN(BPF_REG_4),
 173                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_4, 5),
 174                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 175                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 176                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 177                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 178                         BPF_MOV64_IMM(BPF_REG_0, 0),
 179                         BPF_EXIT_INSN(),
 180                 },
 181                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 182                 .matches = {
 183                         {7, "R0=pkt(id=0,off=8,r=8,imm=0)"},
 184                         {7, "R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 185                         {8, "R3_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
 186                         {9, "R3_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 187                         {10, "R3_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
 188                         {11, "R3_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
 189                         {18, "R3=pkt_end(id=0,off=0,imm=0)"},
 190                         {18, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 191                         {19, "R4_w=inv(id=0,umax_value=8160,var_off=(0x0; 0x1fe0))"},
 192                         {20, "R4_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
 193                         {21, "R4_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
 194                         {22, "R4_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 195                         {23, "R4_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
 196                 },
 197         },
 198         {
 199                 .descr = "unknown mul",
 200                 .insns = {
 201                         LOAD_UNKNOWN(BPF_REG_3),
 202                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
 203                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 1),
 204                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
 205                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 2),
 206                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
 207                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 4),
 208                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
 209                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 8),
 210                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 2),
 211                         BPF_MOV64_IMM(BPF_REG_0, 0),
 212                         BPF_EXIT_INSN(),
 213                 },
 214                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 215                 .matches = {
 216                         {7, "R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 217                         {8, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 218                         {9, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 219                         {10, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 220                         {11, "R4_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
 221                         {12, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 222                         {13, "R4_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 223                         {14, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 224                         {15, "R4_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
 225                         {16, "R4_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
 226                 },
 227         },
 228         {
 229                 .descr = "packet const offset",
 230                 .insns = {
 231                         PREP_PKT_POINTERS,
 232                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 233
 234                         BPF_MOV64_IMM(BPF_REG_0, 0),
 235
 236                         /* Skip over ethernet header.  */
 237                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
 238                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 239                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 240                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 241                         BPF_EXIT_INSN(),
 242
 243                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 0),
 244                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 1),
 245                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 2),
 246                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 3),
 247                         BPF_LDX_MEM(BPF_H, BPF_REG_4, BPF_REG_5, 0),
 248                         BPF_LDX_MEM(BPF_H, BPF_REG_4, BPF_REG_5, 2),
 249                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
 250
 251                         BPF_MOV64_IMM(BPF_REG_0, 0),
 252                         BPF_EXIT_INSN(),
 253                 },
 254                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 255                 .matches = {
 256                         {4, "R5_w=pkt(id=0,off=0,r=0,imm=0)"},
 257                         {5, "R5_w=pkt(id=0,off=14,r=0,imm=0)"},
 258                         {6, "R4_w=pkt(id=0,off=14,r=0,imm=0)"},
 259                         {10, "R2=pkt(id=0,off=0,r=18,imm=0)"},
 260                         {10, "R5=pkt(id=0,off=14,r=18,imm=0)"},
 261                         {10, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
 262                         {14, "R4_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
 263                         {15, "R4_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
 264                 },
 265         },
 266         {
 267                 .descr = "packet variable offset",
 268                 .insns = {
 269                         LOAD_UNKNOWN(BPF_REG_6),
 270                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
 271
 272                         /* First, add a constant to the R5 packet pointer,
 273                          * then a variable with a known alignment.
 274                          */
 275                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 276                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
 277                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 278                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 279                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 280                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 281                         BPF_EXIT_INSN(),
 282                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
 283
 284                         /* Now, test in the other direction.  Adding first
 285                          * the variable offset to R5, then the constant.
 286                          */
 287                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 288                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 289                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
 290                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 291                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 292                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 293                         BPF_EXIT_INSN(),
 294                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
 295
 296                         /* Test multiple accumulations of unknown values
 297                          * into a packet pointer.
 298                          */
 299                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 300                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
 301                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 302                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 4),
 303                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 304                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 305                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 306                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 307                         BPF_EXIT_INSN(),
 308                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
 309
 310                         BPF_MOV64_IMM(BPF_REG_0, 0),
 311                         BPF_EXIT_INSN(),
 312                 },
 313                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 314                 .matches = {
 315                         /* Calculated offset in R6 has unknown value, but known
 316                          * alignment of 4.
 317                          */
 318                         {8, "R2=pkt(id=0,off=0,r=8,imm=0)"},
 319                         {8, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 320                         /* Offset is added to packet pointer R5, resulting in
 321                          * known fixed offset, and variable offset from R6.
 322                          */
 323                         {11, "R5_w=pkt(id=1,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 324                         /* At the time the word size load is performed from R5,
 325                          * it's total offset is NET_IP_ALIGN + reg->off (0) +
 326                          * reg->aux_off (14) which is 16.  Then the variable
 327                          * offset is considered using reg->aux_off_align which
 328                          * is 4 and meets the load's requirements.
 329                          */
 330                         {15, "R4=pkt(id=1,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
 331                         {15, "R5=pkt(id=1,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
 332                         /* Variable offset is added to R5 packet pointer,
 333                          * resulting in auxiliary alignment of 4.
 334                          */
 335                         {18, "R5_w=pkt(id=2,off=0,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 336                         /* Constant offset is added to R5, resulting in
 337                          * reg->off of 14.
 338                          */
 339                         {19, "R5_w=pkt(id=2,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 340                         /* At the time the word size load is performed from R5,
 341                          * its total fixed offset is NET_IP_ALIGN + reg->off
 342                          * (14) which is 16.  Then the variable offset is 4-byte
 343                          * aligned, so the total offset is 4-byte aligned and
 344                          * meets the load's requirements.
 345                          */
 346                         {23, "R4=pkt(id=2,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
 347                         {23, "R5=pkt(id=2,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
 348                         /* Constant offset is added to R5 packet pointer,
 349                          * resulting in reg->off value of 14.
 350                          */
 351                         {26, "R5_w=pkt(id=0,off=14,r=8"},
 352                         /* Variable offset is added to R5, resulting in a
 353                          * variable offset of (4n).
 354                          */
 355                         {27, "R5_w=pkt(id=3,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 356                         /* Constant is added to R5 again, setting reg->off to 18. */
 357                         {28, "R5_w=pkt(id=3,off=18,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 358                         /* And once more we add a variable; resulting var_off
 359                          * is still (4n), fixed offset is not changed.
 360                          * Also, we create a new reg->id.
 361                          */
 362                         {29, "R5_w=pkt(id=4,off=18,r=0,umax_value=2040,var_off=(0x0; 0x7fc)"},
 363                         /* At the time the word size load is performed from R5,
 364                          * its total fixed offset is NET_IP_ALIGN + reg->off (18)
 365                          * which is 20.  Then the variable offset is (4n), so
 366                          * the total offset is 4-byte aligned and meets the
 367                          * load's requirements.
 368                          */
 369                         {33, "R4=pkt(id=4,off=22,r=22,umax_value=2040,var_off=(0x0; 0x7fc)"},
 370                         {33, "R5=pkt(id=4,off=18,r=22,umax_value=2040,var_off=(0x0; 0x7fc)"},
 371                 },
 372         },
 373         {
 374                 .descr = "packet variable offset 2",
 375                 .insns = {
 376                         /* Create an unknown offset, (4n+2)-aligned */
 377                         LOAD_UNKNOWN(BPF_REG_6),
 378                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
 379                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
 380                         /* Add it to the packet pointer */
 381                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 382                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 383                         /* Check bounds and perform a read */
 384                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 385                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 386                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 387                         BPF_EXIT_INSN(),
 388                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
 389                         /* Make a (4n) offset from the value we just read */
 390                         BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xff),
 391                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
 392                         /* Add it to the packet pointer */
 393                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 394                         /* Check bounds and perform a read */
 395                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 396                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 397                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 398                         BPF_EXIT_INSN(),
 399                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
 400                         BPF_MOV64_IMM(BPF_REG_0, 0),
 401                         BPF_EXIT_INSN(),
 402                 },
 403                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 404                 .matches = {
 405                         /* Calculated offset in R6 has unknown value, but known
 406                          * alignment of 4.
 407                          */
 408                         {8, "R2=pkt(id=0,off=0,r=8,imm=0)"},
 409                         {8, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 410                         /* Adding 14 makes R6 be (4n+2) */
 411                         {9, "R6_w=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
 412                         /* Packet pointer has (4n+2) offset */
 413                         {11, "R5_w=pkt(id=1,off=0,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc)"},
 414                         {13, "R4=pkt(id=1,off=4,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc)"},
 415                         /* At the time the word size load is performed from R5,
 416                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
 417                          * which is 2.  Then the variable offset is (4n+2), so
 418                          * the total offset is 4-byte aligned and meets the
 419                          * load's requirements.
 420                          */
 421                         {15, "R5=pkt(id=1,off=0,r=4,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc)"},
 422                         /* Newly read value in R6 was shifted left by 2, so has
 423                          * known alignment of 4.
 424                          */
 425                         {18, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 426                         /* Added (4n) to packet pointer's (4n+2) var_off, giving
 427                          * another (4n+2).
 428                          */
 429                         {19, "R5_w=pkt(id=2,off=0,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc)"},
 430                         {21, "R4=pkt(id=2,off=4,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc)"},
 431                         /* At the time the word size load is performed from R5,
 432                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
 433                          * which is 2.  Then the variable offset is (4n+2), so
 434                          * the total offset is 4-byte aligned and meets the
 435                          * load's requirements.
 436                          */
 437                         {23, "R5=pkt(id=2,off=0,r=4,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc)"},
 438                 },
 439         },
 440         {
 441                 .descr = "dubious pointer arithmetic",
 442                 .insns = {
 443                         PREP_PKT_POINTERS,
 444                         BPF_MOV64_IMM(BPF_REG_0, 0),
 445                         /* (ptr - ptr) << 2 */
 446                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_3),
 447                         BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_2),
 448                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_5, 2),
 449                         /* We have a (4n) value.  Let's make a packet offset
 450                          * out of it.  First add 14, to make it a (4n+2)
 451                          */
 452                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
 453                         /* Then make sure it's nonnegative */
 454                         BPF_JMP_IMM(BPF_JSGE, BPF_REG_5, 0, 1),
 455                         BPF_EXIT_INSN(),
 456                         /* Add it to packet pointer */
 457                         BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
 458                         BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
 459                         /* Check bounds and perform a read */
 460                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_6),
 461                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 462                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 463                         BPF_EXIT_INSN(),
 464                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_6, 0),
 465                         BPF_EXIT_INSN(),
 466                 },
 467                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 468                 .result = REJECT,
 469                 .matches = {
 470                         {4, "R5_w=pkt_end(id=0,off=0,imm=0)"},
 471                         /* (ptr - ptr) << 2 == unknown, (4n) */
 472                         {6, "R5_w=inv(id=0,smax_value=9223372036854775804,umax_value=18446744073709551612,var_off=(0x0; 0xfffffffffffffffc)"},
 473                         /* (4n) + 14 == (4n+2).  We blow our bounds, because
 474                          * the add could overflow.
 475                          */
 476                         {7, "R5=inv(id=0,smin_value=-9223372036854775806,smax_value=9223372036854775806,umin_value=2,umax_value=18446744073709551614,var_off=(0x2; 0xfffffffffffffffc)"},
 477                         /* Checked s>=0 */
 478                         {9, "R5=inv(id=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
 479                         /* packet pointer + nonnegative (4n+2) */
 480                         {11, "R6_w=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
 481                         {13, "R4=pkt(id=1,off=4,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
 482                         /* NET_IP_ALIGN + (4n+2) == (4n), alignment is fine.
 483                          * We checked the bounds, but it might have been able
 484                          * to overflow if the packet pointer started in the
 485                          * upper half of the address space.
 486                          * So we did not get a 'range' on R6, and the access
 487                          * attempt will fail.
 488                          */
 489                         {15, "R6=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
 490                 }
 491         },
 492         {
 493                 .descr = "variable subtraction",
 494                 .insns = {
 495                         /* Create an unknown offset, (4n+2)-aligned */
 496                         LOAD_UNKNOWN(BPF_REG_6),
 497                         BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
 498                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
 499                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
 500                         /* Create another unknown, (4n)-aligned, and subtract
 501                          * it from the first one
 502                          */
 503                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
 504                         BPF_ALU64_REG(BPF_SUB, BPF_REG_6, BPF_REG_7),
 505                         /* Bounds-check the result */
 506                         BPF_JMP_IMM(BPF_JSGE, BPF_REG_6, 0, 1),
 507                         BPF_EXIT_INSN(),
 508                         /* Add it to the packet pointer */
 509                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 510                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
 511                         /* Check bounds and perform a read */
 512                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 513                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 514                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 515                         BPF_EXIT_INSN(),
 516                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
 517                         BPF_EXIT_INSN(),
 518                 },
 519                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 520                 .matches = {
 521                         /* Calculated offset in R6 has unknown value, but known
 522                          * alignment of 4.
 523                          */
 524                         {7, "R2=pkt(id=0,off=0,r=8,imm=0)"},
 525                         {9, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 526                         /* Adding 14 makes R6 be (4n+2) */
 527                         {10, "R6_w=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
 528                         /* New unknown value in R7 is (4n) */
 529                         {11, "R7_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
 530                         /* Subtracting it from R6 blows our unsigned bounds */
 531                         {12, "R6=inv(id=0,smin_value=-1006,smax_value=1034,umin_value=2,umax_value=18446744073709551614,var_off=(0x2; 0xfffffffffffffffc)"},
 532                         /* Checked s>= 0 */
 533                         {14, "R6=inv(id=0,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc))"},
 534                         /* At the time the word size load is performed from R5,
 535                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
 536                          * which is 2.  Then the variable offset is (4n+2), so
 537                          * the total offset is 4-byte aligned and meets the
 538                          * load's requirements.
 539                          */
 540                         {20, "R5=pkt(id=1,off=0,r=4,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc)"},
 541
 542                 },
 543         },
 544         {
 545                 .descr = "pointer variable subtraction",
 546                 .insns = {
 547                         /* Create an unknown offset, (4n+2)-aligned and bounded
 548                          * to [14,74]
 549                          */
 550                         LOAD_UNKNOWN(BPF_REG_6),
 551                         BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
 552                         BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xf),
 553                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
 554                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
 555                         /* Subtract it from the packet pointer */
 556                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
 557                         BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_6),
 558                         /* Create another unknown, (4n)-aligned and >= 74.
 559                          * That in fact means >= 76, since 74 % 4 == 2
 560                          */
 561                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
 562                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_7, 76),
 563                         /* Add it to the packet pointer */
 564                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_7),
 565                         /* Check bounds and perform a read */
 566                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
 567                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
 568                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
 569                         BPF_EXIT_INSN(),
 570                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
 571                         BPF_EXIT_INSN(),
 572                 },
 573                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 574                 .matches = {
 575                         /* Calculated offset in R6 has unknown value, but known
 576                          * alignment of 4.
 577                          */
 578                         {7, "R2=pkt(id=0,off=0,r=8,imm=0)"},
 579                         {10, "R6_w=inv(id=0,umax_value=60,var_off=(0x0; 0x3c))"},
 580                         /* Adding 14 makes R6 be (4n+2) */
 581                         {11, "R6_w=inv(id=0,umin_value=14,umax_value=74,var_off=(0x2; 0x7c))"},
 582                         /* Subtracting from packet pointer overflows ubounds */
 583                         {13, "R5_w=pkt(id=1,off=0,r=8,umin_value=18446744073709551542,umax_value=18446744073709551602,var_off=(0xffffffffffffff82; 0x7c))"},
 584                         /* New unknown value in R7 is (4n), >= 76 */
 585                         {15, "R7_w=inv(id=0,umin_value=76,umax_value=1096,var_off=(0x0; 0x7fc))"},
 586                         /* Adding it to packet pointer gives nice bounds again */
 587                         {16, "R5_w=pkt(id=2,off=0,r=0,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
 588                         /* At the time the word size load is performed from R5,
 589                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
 590                          * which is 2.  Then the variable offset is (4n+2), so
 591                          * the total offset is 4-byte aligned and meets the
 592                          * load's requirements.
 593                          */
 594                         {20, "R5=pkt(id=2,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
 595                 },
 596         },
 597 };
 598
 599 static int probe_filter_length(const struct bpf_insn *fp)
 600 {
 601         int len;
 602
 603         for (len = MAX_INSNS - 1; len > 0; --len)
 604                 if (fp[len].code != 0 || fp[len].imm != 0)
 605                         break;
 606         return len + 1;
 607 }
 608
 609 static char bpf_vlog[32768];
 610
 611 static int do_test_single(struct bpf_align_test *test)
 612 {
 613         struct bpf_insn *prog = test->insns;
 614         int prog_type = test->prog_type;
 615         char bpf_vlog_copy[32768];
 616         const char *line_ptr;
 617         int cur_line = -1;
 618         int prog_len, i;
 619         int fd_prog;
 620         int ret;
 621
 622         prog_len = probe_filter_length(prog);
 623         fd_prog = bpf_verify_program(prog_type ? : BPF_PROG_TYPE_SOCKET_FILTER,
 624                                      prog, prog_len, BPF_F_STRICT_ALIGNMENT,
 625                                      "GPL", 0, bpf_vlog, sizeof(bpf_vlog), 2);
 626         if (fd_prog < 0 && test->result != REJECT) {
 627                 printf("Failed to load program.\n");
 628                 printf("%s", bpf_vlog);
 629                 ret = 1;
 630         } else if (fd_prog >= 0 && test->result == REJECT) {
 631                 printf("Unexpected success to load!\n");
 632                 printf("%s", bpf_vlog);
 633                 ret = 1;
 634                 close(fd_prog);
 635         } else {
 636                 ret = 0;
 637                 /* We make a local copy so that we can strtok() it */
 638                 strncpy(bpf_vlog_copy, bpf_vlog, sizeof(bpf_vlog_copy));
 639                 line_ptr = strtok(bpf_vlog_copy, "\n");
 640                 for (i = 0; i < MAX_MATCHES; i++) {
 641                         struct bpf_reg_match m = test->matches[i];
 642
 643                         if (!m.match)
 644                                 break;
 645                         while (line_ptr) {
 646                                 cur_line = -1;
 647                                 sscanf(line_ptr, "%u: ", &cur_line);
 648                                 if (cur_line == m.line)
 649                                         break;
 650                                 line_ptr = strtok(NULL, "\n");
 651                         }
 652                         if (!line_ptr) {
 653                                 printf("Failed to find line %u for match: %s\n",
 654                                        m.line, m.match);
 655                                 ret = 1;
 656                                 printf("%s", bpf_vlog);
 657                                 break;
 658                         }
 659                         if (!strstr(line_ptr, m.match)) {
 660                                 printf("Failed to find match %u: %s\n",
 661                                        m.line, m.match);
 662                                 ret = 1;
 663                                 printf("%s", bpf_vlog);
 664                                 break;
 665                         }
 666                 }
 667                 if (fd_prog >= 0)
 668                         close(fd_prog);
 669         }
 670         return ret;
 671 }
 672
 673 static int do_test(unsigned int from, unsigned int to)
 674 {
 675         int all_pass = 0;
 676         int all_fail = 0;
 677         unsigned int i;
 678
 679         for (i = from; i < to; i++) {
 680                 struct bpf_align_test *test = &tests[i];
 681                 int fail;
 682
 683                 printf("Test %3d: %s ... ",
 684                        i, test->descr);
 685                 fail = do_test_single(test);
 686                 if (fail) {
 687                         all_fail++;
 688                         printf("FAIL\n");
 689                 } else {
 690                         all_pass++;
 691                         printf("PASS\n");
 692                 }
 693         }
 694         printf("Results: %d pass %d fail\n",
 695                all_pass, all_fail);
 696         return all_fail ? EXIT_FAILURE : EXIT_SUCCESS;
 697 }
 698
 699 int main(int argc, char **argv)
 700 {
 701         unsigned int from = 0, to = ARRAY_SIZE(tests);
 702
 703         if (argc == 3) {
 704                 unsigned int l = atoi(argv[argc - 2]);
 705                 unsigned int u = atoi(argv[argc - 1]);
 706
 707                 if (l < to && u < to) {
 708                         from = l;
 709                         to   = u + 1;
 710                 }
 711         } else if (argc == 2) {
 712                 unsigned int t = atoi(argv[argc - 1]);
 713
 714                 if (t < to) {
 715                         from = t;
 716                         to   = t + 1;
 717                 }
 718         }
 719         return do_test(from, to);
 720 }