• Alexei Starovoitov's avatar
    bpf: improve verifier branch analysis · 4f7b3e82
    Alexei Starovoitov authored
    pathological bpf programs may try to force verifier to explode in
    the number of branch states:
      20: (d5) if r1 s<= 0x24000028 goto pc+0
      21: (b5) if r0 <= 0xe1fa20 goto pc+2
      22: (d5) if r1 s<= 0x7e goto pc+0
      23: (b5) if r0 <= 0xe880e000 goto pc+0
      24: (c5) if r0 s< 0x2100ecf4 goto pc+0
      25: (d5) if r1 s<= 0xe880e000 goto pc+1
      26: (c5) if r0 s< 0xf4041810 goto pc+0
      27: (d5) if r1 s<= 0x1e007e goto pc+0
      28: (b5) if r0 <= 0xe86be000 goto pc+0
      29: (07) r0 += 16614
      30: (c5) if r0 s< 0x6d0020da goto pc+0
      31: (35) if r0 >= 0x2100ecf4 goto pc+0
    
    Teach verifier to recognize always taken and always not taken branches.
    This analysis is already done for == and != comparison.
    Expand it to all other branches.
    
    It also helps real bpf programs to be verified faster:
                           before  after
    bpf_lb-DLB_L3.o         2003    1940
    bpf_lb-DLB_L4.o         3173    3089
    bpf_lb-DUNKNOWN.o       1080    1065
    bpf_lxc-DDROP_ALL.o     29584   28052
    bpf_lxc-DUNKNOWN.o      36916   35487
    bpf_netdev.o            11188   10864
    bpf_overlay.o           6679    6643
    bpf_lcx_jit.o           39555   38437
    Reported-by: default avatarAnatoly Trosinenko <anatoly.trosinenko@gmail.com>
    Signed-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    Acked-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    Acked-by: default avatarEdward Cree <ecree@solarflare.com>
    Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    4f7b3e82
verifier.c 188 KB