)]}'
{
  "commit": "cc4c8247b39e33778a599dcbfbd1d249a40e4b83",
  "tree": "edee0125cdf37fe0ee58258cdf871fc0f5b68595",
  "parents": [
    "195d94b885363a74b96e1851aa101ef27d53f3b7"
  ],
  "author": {
    "name": "Alexei Starovoitov",
    "email": "ast@kernel.org",
    "time": "Tue Jun 04 19:29:08 2019 -0700"
  },
  "committer": {
    "name": "Alexei Starovoitov",
    "email": "ast@kernel.org",
    "time": "Sat Jun 15 12:06:04 2019 -0700"
  },
  "message": "bpf: precise scalar_value tracking\n\nIntroduce precision tracking logic that\nhelps cilium programs the most:\n                  old clang  old clang    new clang  new clang\n                          with all patches         with all patches\nbpf_lb-DLB_L3.o      1838     2283         1923       1863\nbpf_lb-DLB_L4.o      3218     2657         3077       2468\nbpf_lb-DUNKNOWN.o    1064     545          1062       544\nbpf_lxc-DDROP_ALL.o  26935    23045        166729     22629\nbpf_lxc-DUNKNOWN.o   34439    35240        174607     28805\nbpf_netdev.o         9721     8753         8407       6801\nbpf_overlay.o        6184     7901         5420       4754\nbpf_lxc_jit.o        39389    50925        39389      50925\n\nConsider code:\n654: (85) call bpf_get_hash_recalc#34\n655: (bf) r7 \u003d r0\n656: (15) if r8 \u003d\u003d 0x0 goto pc+29\n657: (bf) r2 \u003d r10\n658: (07) r2 +\u003d -48\n659: (18) r1 \u003d 0xffff8881e41e1b00\n661: (85) call bpf_map_lookup_elem#1\n662: (15) if r0 \u003d\u003d 0x0 goto pc+23\n663: (69) r1 \u003d *(u16 *)(r0 +0)\n664: (15) if r1 \u003d\u003d 0x0 goto pc+21\n665: (bf) r8 \u003d r7\n666: (57) r8 \u0026\u003d 65535\n667: (bf) r2 \u003d r8\n668: (3f) r2 /\u003d r1\n669: (2f) r2 *\u003d r1\n670: (bf) r1 \u003d r8\n671: (1f) r1 -\u003d r2\n672: (57) r1 \u0026\u003d 255\n673: (25) if r1 \u003e 0x1e goto pc+12\n R0\u003dmap_value(id\u003d0,off\u003d0,ks\u003d20,vs\u003d64,imm\u003d0) R1_w\u003dinv(id\u003d0,umax_value\u003d30,var_off\u003d(0x0; 0x1f))\n674: (67) r1 \u003c\u003c\u003d 1\n675: (0f) r0 +\u003d r1\n\nAt this point the verifier will notice that scalar R1 is used in map pointer adjustment.\nR1 has to be precise for later operations on R0 to be validated properly.\n\nThe verifier will backtrack the above code in the following way:\nlast_idx 675 first_idx 664\nregs\u003d2 stack\u003d0 before 675: (0f) r0 +\u003d r1         // started backtracking R1 regs\u003d2 is a bitmask\nregs\u003d2 stack\u003d0 before 674: (67) r1 \u003c\u003c\u003d 1\nregs\u003d2 stack\u003d0 before 673: (25) if r1 \u003e 0x1e goto pc+12\nregs\u003d2 stack\u003d0 before 672: (57) r1 \u0026\u003d 255\nregs\u003d2 stack\u003d0 before 671: (1f) r1 -\u003d r2         // now both R1 and R2 has to be precise -\u003e regs\u003d6 mask\nregs\u003d6 stack\u003d0 before 670: (bf) r1 \u003d r8          // after this insn R8 and R2 has to be precise\nregs\u003d104 stack\u003d0 before 669: (2f) r2 *\u003d r1       // after this one R8, R2, and R1\nregs\u003d106 stack\u003d0 before 668: (3f) r2 /\u003d r1\nregs\u003d106 stack\u003d0 before 667: (bf) r2 \u003d r8\nregs\u003d102 stack\u003d0 before 666: (57) r8 \u0026\u003d 65535\nregs\u003d102 stack\u003d0 before 665: (bf) r8 \u003d r7\nregs\u003d82 stack\u003d0 before 664: (15) if r1 \u003d\u003d 0x0 goto pc+21\n // this is the end of verifier state. The following regs will be marked precised:\n R1_rw\u003dinvP(id\u003d0,umax_value\u003d65535,var_off\u003d(0x0; 0xffff)) R7_rw\u003dinvP(id\u003d0)\nparent didn\u0027t have regs\u003d82 stack\u003d0 marks         // so backtracking continues into parent state\nlast_idx 663 first_idx 655\nregs\u003d82 stack\u003d0 before 663: (69) r1 \u003d *(u16 *)(r0 +0)   // R1 was assigned no need to track it further\nregs\u003d80 stack\u003d0 before 662: (15) if r0 \u003d\u003d 0x0 goto pc+23    // keep tracking R7\nregs\u003d80 stack\u003d0 before 661: (85) call bpf_map_lookup_elem#1  // keep tracking R7\nregs\u003d80 stack\u003d0 before 659: (18) r1 \u003d 0xffff8881e41e1b00\nregs\u003d80 stack\u003d0 before 658: (07) r2 +\u003d -48\nregs\u003d80 stack\u003d0 before 657: (bf) r2 \u003d r10\nregs\u003d80 stack\u003d0 before 656: (15) if r8 \u003d\u003d 0x0 goto pc+29\nregs\u003d80 stack\u003d0 before 655: (bf) r7 \u003d r0                // here the assignment into R7\n // mark R0 to be precise:\n R0_rw\u003dinvP(id\u003d0)\nparent didn\u0027t have regs\u003d1 stack\u003d0 marks                 // regs\u003d1 -\u003e tracking R0\nlast_idx 654 first_idx 644\nregs\u003d1 stack\u003d0 before 654: (85) call bpf_get_hash_recalc#34 // and in the parent frame it was a return value\n  // nothing further to backtrack\n\nTwo scalar registers not marked precise are equivalent from state pruning point of view.\nMore details in the patch comments.\n\nIt doesn\u0027t support bpf2bpf calls yet and enabled for root only.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "03037373b447c696e58584cd60acc6e4678b56c4",
      "old_mode": 33188,
      "old_path": "include/linux/bpf_verifier.h",
      "new_id": "19393b0964a8bb0a15457d63ecbcb7daac639701",
      "new_mode": 33188,
      "new_path": "include/linux/bpf_verifier.h"
    },
    {
      "type": "modify",
      "old_id": "870c8f19ce80643b9bf8ac99df63f4f638e7f540",
      "old_mode": 33188,
      "old_path": "kernel/bpf/verifier.c",
      "new_id": "709ce4cef8ba2dec72de1add0b35e9430f5c4204",
      "new_mode": 33188,
      "new_path": "kernel/bpf/verifier.c"
    }
  ]
}