bpf: fix precision tracking
Subsystems (4)
Alexei Starovoitov
maintainerPATCH 1/1 bpf: fix precision tracking
When equivalent state is found the current state needs to propagate precision marks. Otherwise the verifier will prune the search incorrectly.
There is a price for correctness:
before before broken fixed
cnst spill precise precise
bpf_lb-DLB_L3.o 1923 8128 1863 1898
bpf_lb-DLB_L4.o 3077 6707 2468 2666
bpf_lb-DUNKNOWN.o 1062 1062 544 544
bpf_lxc-DDROP_ALL.o 166729 380712 22629 36823
bpf_lxc-DUNKNOWN.o 174607 440652 28805 45325
bpf_netdev.o 8407 31904 6801 7002
bpf_overlay.o 5420 23569 4754 4858
bpf_lxc_jit.o 39389 359445 50925 69631Overall precision tracking is still very effective.
---
Sending the fix early w/o tests, since I'm traveling. Will add proper tests when I'm back.
--- kernel/bpf/verifier.c | 121 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 107 insertions(+), 14 deletions(-)
kernel/bpf/verifier.c +107 -14
@@ -1659,16 +1659,18 @@ static void mark_all_scalars_precise(struct bpf_verifier_env *env, } } -static int mark_chain_precision (struct bpf_verifier_env *env,int regno) +static int __mark_chain_precision (struct bpf_verifier_env *env,int regno, +int spi) {struct bpf_verifier_state *st = env->cur_state;int first_idx = st->first_insn_idx;int last_idx = env->insn_idx;struct bpf_func_state *func;struct bpf_reg_state *reg; -u32 reg_mask =1u << regno; -u64 stack_mask =0 ; +u32 reg_mask = regno >=0 ?1u << regno :0 ; +u64 stack_mask = spi >=0 ?1ull << spi :0 ;bool skip_first = true; +bool new_marks = false;int i, err;if (!env->allow_ptr_leaks)
@@ -1676,18 +1678,43 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ; func = st->frame[st->curframe]; - reg = &func->regs[regno]; -if (reg->type !=SCALAR_VALUE ) { -WARN_ONCE (1 ,"backtracing misuse" ); -return -EFAULT ; +if (regno >=0 ) { + reg = &func->regs[regno]; +if (reg->type !=SCALAR_VALUE ) { +WARN_ONCE (1 ,"backtracing misuse" ); +return -EFAULT ; + } +if (!reg->precise) + new_marks = true; +else + reg_mask =0 ; + reg->precise = true; } -if (reg->precise) -return 0 ; - func->regs[regno].precise = true; +while (spi >=0 ) { +if (func->stack[spi].slot_type[0 ] !=STACK_SPILL ) { + stack_mask =0 ; +break ; + } + reg = &func->stack[spi].spilled_ptr; +if (reg->type !=SCALAR_VALUE ) { + stack_mask =0 ; +break ; + } +if (!reg->precise) + new_marks = true; +else + stack_mask =0 ; + reg->precise = true; +break ; + } + +if (!new_marks) +return 0 ; +if (!reg_mask && !stack_mask) +return 0 ;for (;;) {DECLARE_BITMAP (mask,64 ); -bool new_marks = false;u32 history = st->jmp_history_cnt;if (env->log.level &BPF_LOG_LEVEL )
@@ -1730,12 +1757,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)if (!st)break ; + new_marks = false; func = st->frame[st->curframe];bitmap_from_u64 (mask, reg_mask);for_each_set_bit (i, mask,32 ) { reg = &func->regs[i]; -if (reg->type !=SCALAR_VALUE ) +if (reg->type !=SCALAR_VALUE ) { + reg_mask &= ~(1u << i);continue ; + }if (!reg->precise) new_marks = true; reg->precise = true;
@@ -1756,11 +1786,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return -EFAULT ; } -if (func->stack[i].slot_type[0 ] !=STACK_SPILL ) +if (func->stack[i].slot_type[0 ] !=STACK_SPILL ) { + stack_mask &= ~(1ull << i);continue ; + } reg = &func->stack[i].spilled_ptr; -if (reg->type !=SCALAR_VALUE ) +if (reg->type !=SCALAR_VALUE ) { + stack_mask &= ~(1ull << i);continue ; + }if (!reg->precise) new_marks = true; reg->precise = true;
@@ -1772,6 +1806,8 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno) reg_mask, stack_mask); } +if (!reg_mask && !stack_mask) +break ;if (!new_marks)break ;
@@ -1781,6 +1817,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ; } +static int mark_chain_precision (struct bpf_verifier_env *env,int regno) +{ +return __mark_chain_precision (env, regno,-1 ); +} + +static int mark_chain_precision_stack (struct bpf_verifier_env *env,int spi) +{ +return __mark_chain_precision (env,-1 , spi); +}static bool is_spillable_regtype (enum bpf_reg_type type) {
@@ -7114,6 +7159,46 @@ static int propagate_liveness(struct bpf_verifier_env *env,return 0 ; } +/* find precise scalars in the previous equivalent state and +* propagate them into the current state +*/ +static int propagate_precision (struct bpf_verifier_env *env, +const struct bpf_verifier_state *old) +{ +struct bpf_reg_state *state_reg; +struct bpf_func_state *state; +int i, err =0 ; + + state = old->frame[old->curframe]; + state_reg = state->regs; +for (i =0 ; i <BPF_REG_FP ; i++, state_reg++) { +if (state_reg->type !=SCALAR_VALUE || + !state_reg->precise) +continue ; +if (env->log.level &BPF_LOG_LEVEL2 ) +verbose (env,"propagating r%d\n" , i); + err =mark_chain_precision (env, i); +if (err <0 ) +return err; + } + +for (i =0 ; i < state->allocated_stack /BPF_REG_SIZE ; i++) { +if (state->stack[i].slot_type[0 ] !=STACK_SPILL ) +continue ; + state_reg = &state->stack[i].spilled_ptr; +if (state_reg->type !=SCALAR_VALUE || + !state_reg->precise) +continue ; +if (env->log.level &BPF_LOG_LEVEL2 ) +verbose (env,"propagating fp%d\n" , + (-i -1 ) *BPF_REG_SIZE ); + err =mark_chain_precision_stack (env, i); +if (err <0 ) +return err; + } +return 0 ; +} +static bool states_maybe_looping (struct bpf_verifier_state *old,struct bpf_verifier_state *cur) {
@@ -7206,6 +7291,14 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)* this state and will pop a new one. */ err =propagate_liveness (env, &sl->state, cur); + +/* if previous state reached the exit with precision and +* current state is equivalent to it (except precsion marks) +* the precision needs to be propagated back in +* the current state. +*/ + err = err ? :push_jmp_history (env, cur); + err = err ? :propagate_precision (env, &sl->state);if (err)return err;return 1 ;
Signature · 1 line
2.20.0
Quoted 15 lines · Alexei Starovoitov
When equivalent state is found the current state needs to propagate precision marks. Otherwise the verifier will prune the search incorrectly.
There is a price for correctness:
before before broken fixed cnst spill precise precise bpf_lb-DLB_L3.o 1923 8128 1863 1898 bpf_lb-DLB_L4.o 3077 6707 2468 2666 bpf_lb-DUNKNOWN.o 1062 1062 544 544 bpf_lxc-DDROP_ALL.o 166729 380712 22629 36823 bpf_lxc-DUNKNOWN.o 174607 440652 28805 45325 bpf_netdev.o 8407 31904 6801 7002 bpf_overlay.o 5420 23569 4754 4858 bpf_lxc_jit.o 39389 359445 50925 69631
Quoted 6 lines
Overall precision tracking is still very effective.
Fixes b5dc0163d8fd ("bpf: precise scalar_value tracking")Reported-by Lawrence Brakmo <[email protected]>Signed-off-by Alexei Starovoitov <[email protected]>---
Quoted 209 lines
Sending the fix early w/o tests, since I'm traveling. Will add proper tests when I'm back.
--- kernel/bpf/verifier.c | 121 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 107 insertions(+), 14 deletions(-)kernel/bpf/verifier.c +107
-15@@ -1659,16 +1659,18 @@ static void mark_all_scalars_precise(struct bpf_verifier_env *env, } } -static int mark_chain_precision (struct bpf_verifier_env *env,int regno) +static int __mark_chain_precision (struct bpf_verifier_env *env,int regno, +int spi) {struct bpf_verifier_state *st = env->cur_state;int first_idx = st->first_insn_idx;int last_idx = env->insn_idx;struct bpf_func_state *func;struct bpf_reg_state *reg; -u32 reg_mask =1u << regno; -u64 stack_mask =0 ; +u32 reg_mask = regno >=0 ?1u << regno :0 ; +u64 stack_mask = spi >=0 ?1ull << spi :0 ;bool skip_first = true; +bool new_marks = false;int i, err;if (!env->allow_ptr_leaks)@@ -1676,18 +1678,43 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ; func = st->frame[st->curframe]; - reg = &func->regs[regno]; -if (reg->type !=SCALAR_VALUE ) { -WARN_ONCE (1 ,"backtracing misuse" ); -return -EFAULT ; +if (regno >=0 ) { + reg = &func->regs[regno]; +if (reg->type !=SCALAR_VALUE ) { +WARN_ONCE (1 ,"backtracing misuse" ); +return -EFAULT ; + } +if (!reg->precise) + new_marks = true; +else + reg_mask =0 ; + reg->precise = true; } -if (reg->precise) -return 0 ; - func->regs[regno].precise = true; +while (spi >=0 ) { +if (func->stack[spi].slot_type[0 ] !=STACK_SPILL ) { + stack_mask =0 ; +break ; + } + reg = &func->stack[spi].spilled_ptr; +if (reg->type !=SCALAR_VALUE ) { + stack_mask =0 ; +break ; + } +if (!reg->precise) + new_marks = true; +else + stack_mask =0 ; + reg->precise = true; +break ; + } + +if (!new_marks) +return 0 ; +if (!reg_mask && !stack_mask) +return 0 ;for (;;) {DECLARE_BITMAP (mask,64 ); -bool new_marks = false;u32 history = st->jmp_history_cnt;if (env->log.level &BPF_LOG_LEVEL )@@ -1730,12 +1757,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)if (!st)break ; + new_marks = false; func = st->frame[st->curframe];bitmap_from_u64 (mask, reg_mask);for_each_set_bit (i, mask,32 ) { reg = &func->regs[i]; -if (reg->type !=SCALAR_VALUE ) +if (reg->type !=SCALAR_VALUE ) { + reg_mask &= ~(1u << i);continue ; + }if (!reg->precise) new_marks = true; reg->precise = true;@@ -1756,11 +1786,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return -EFAULT ; } -if (func->stack[i].slot_type[0 ] !=STACK_SPILL ) +if (func->stack[i].slot_type[0 ] !=STACK_SPILL ) { + stack_mask &= ~(1ull << i);continue ; + } reg = &func->stack[i].spilled_ptr; -if (reg->type !=SCALAR_VALUE ) +if (reg->type !=SCALAR_VALUE ) { + stack_mask &= ~(1ull << i);continue ; + }if (!reg->precise) new_marks = true; reg->precise = true;@@ -1772,6 +1806,8 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno) reg_mask, stack_mask); } +if (!reg_mask && !stack_mask) +break ;if (!new_marks)break ;@@ -1781,6 +1817,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ; } +static int mark_chain_precision (struct bpf_verifier_env *env,int regno) +{ +return __mark_chain_precision (env, regno,-1 ); +} + +static int mark_chain_precision_stack (struct bpf_verifier_env *env,int spi) +{ +return __mark_chain_precision (env,-1 , spi); +}static bool is_spillable_regtype (enum bpf_reg_type type) {@@ -7114,6 +7159,46 @@ static int propagate_liveness(struct bpf_verifier_env *env,return 0 ; } +/* find precise scalars in the previous equivalent state and +* propagate them into the current state +*/ +static int propagate_precision (struct bpf_verifier_env *env, +const struct bpf_verifier_state *old) +{ +struct bpf_reg_state *state_reg; +struct bpf_func_state *state; +int i, err =0 ; + + state = old->frame[old->curframe]; + state_reg = state->regs; +for (i =0 ; i <BPF_REG_FP ; i++, state_reg++) { +if (state_reg->type !=SCALAR_VALUE || + !state_reg->precise) +continue ; +if (env->log.level &BPF_LOG_LEVEL2 ) +verbose (env,"propagating r%d\n" , i); + err =mark_chain_precision (env, i); +if (err <0 ) +return err; + } + +for (i =0 ; i < state->allocated_stack /BPF_REG_SIZE ; i++) { +if (state->stack[i].slot_type[0 ] !=STACK_SPILL ) +continue ; + state_reg = &state->stack[i].spilled_ptr; +if (state_reg->type !=SCALAR_VALUE || + !state_reg->precise) +continue ; +if (env->log.level &BPF_LOG_LEVEL2 ) +verbose (env,"propagating fp%d\n" , + (-i -1 ) *BPF_REG_SIZE ); + err =mark_chain_precision_stack (env, i); +if (err <0 ) +return err; + } +return 0 ; +} +static bool states_maybe_looping (struct bpf_verifier_state *old,struct bpf_verifier_state *cur) {@@ -7206,6 +7291,14 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)* this state and will pop a new one. */ err =propagate_liveness (env, &sl->state, cur); + +/* if previous state reached the exit with precision and +* current state is equivalent to it (except precsion marks) +* the precision needs to be propagated back in +* the current state. +*/ + err = err ? :push_jmp_history (env, cur); + err = err ? :propagate_precision (env, &sl->state);if (err)return err;return 1 ; --2.20.0
Lawrence Brakmo
Tested-byOn 6/28/19, 12:33 PM, "[email protected] on behalf of Andrii Nakryiko" <[email protected] on behalf of [email protected]> wrote:
On Fri, Jun 28, 2019 at 9:25 AM Alexei Starovoitov <[email protected]> wrote: > > When equivalent state is found the current state needs to propagate precision marks. > Otherwise the verifier will prune the search incorrectly. > > There is a price for correctness: > before before broken fixed > cnst spill precise precise > bpf_lb-DLB_L3.o 1923 8128 1863 1898 > bpf_lb-DLB_L4.o 3077 6707 2468 2666 > bpf_lb-DUNKNOWN.o 1062 1062 544 544 > bpf_lxc-DDROP_ALL.o 166729 380712 22629 36823 > bpf_lxc-DUNKNOWN.o 174607 440652 28805 45325 > bpf_netdev.o 8407 31904 6801 7002 > bpf_overlay.o 5420 23569 4754 4858 > bpf_lxc_jit.o 39389 359445 50925 69631 > Overall precision tracking is still very effective. > > Fixes: b5dc0163d8fd ("bpf: precise scalar_value tracking") > Reported-by: Lawrence Brakmo <[email protected]> > Signed-off-by: Alexei Starovoitov <[email protected]> > --- Acked-by: Andrii Nakryiko <[email protected]>
Quoted 209 lines
Sending the fix early w/o tests, since I'm traveling. Will add proper tests when I'm back.
--- kernel/bpf/verifier.c | 121 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 107 insertions(+), 14 deletions(-)kernel/bpf/verifier.c +107
-15@@ -1659,16 +1659,18 @@ static void mark_all_scalars_precise(struct bpf_verifier_env *env, } } -static int mark_chain_precision (struct bpf_verifier_env *env,int regno) +static int __mark_chain_precision (struct bpf_verifier_env *env,int regno, +int spi) {struct bpf_verifier_state *st = env->cur_state;int first_idx = st->first_insn_idx;int last_idx = env->insn_idx;struct bpf_func_state *func;struct bpf_reg_state *reg; -u32 reg_mask =1u << regno; -u64 stack_mask =0 ; +u32 reg_mask = regno >=0 ?1u << regno :0 ; +u64 stack_mask = spi >=0 ?1ull << spi :0 ;bool skip_first = true; +bool new_marks = false;int i, err;if (!env->allow_ptr_leaks)@@ -1676,18 +1678,43 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ; func = st->frame[st->curframe]; - reg = &func->regs[regno]; -if (reg->type !=SCALAR_VALUE ) { -WARN_ONCE (1 ,"backtracing misuse" ); -return -EFAULT ; +if (regno >=0 ) { + reg = &func->regs[regno]; +if (reg->type !=SCALAR_VALUE ) { +WARN_ONCE (1 ,"backtracing misuse" ); +return -EFAULT ; + } +if (!reg->precise) + new_marks = true; +else + reg_mask =0 ; + reg->precise = true; } -if (reg->precise) -return 0 ; - func->regs[regno].precise = true; +while (spi >=0 ) { +if (func->stack[spi].slot_type[0 ] !=STACK_SPILL ) { + stack_mask =0 ; +break ; + } + reg = &func->stack[spi].spilled_ptr; +if (reg->type !=SCALAR_VALUE ) { + stack_mask =0 ; +break ; + } +if (!reg->precise) + new_marks = true; +else + stack_mask =0 ; + reg->precise = true; +break ; + } + +if (!new_marks) +return 0 ; +if (!reg_mask && !stack_mask) +return 0 ;for (;;) {DECLARE_BITMAP (mask,64 ); -bool new_marks = false;u32 history = st->jmp_history_cnt;if (env->log.level &BPF_LOG_LEVEL )@@ -1730,12 +1757,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)if (!st)break ; + new_marks = false; func = st->frame[st->curframe];bitmap_from_u64 (mask, reg_mask);for_each_set_bit (i, mask,32 ) { reg = &func->regs[i]; -if (reg->type !=SCALAR_VALUE ) +if (reg->type !=SCALAR_VALUE ) { + reg_mask &= ~(1u << i);continue ; + }if (!reg->precise) new_marks = true; reg->precise = true;@@ -1756,11 +1786,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return -EFAULT ; } -if (func->stack[i].slot_type[0 ] !=STACK_SPILL ) +if (func->stack[i].slot_type[0 ] !=STACK_SPILL ) { + stack_mask &= ~(1ull << i);continue ; + } reg = &func->stack[i].spilled_ptr; -if (reg->type !=SCALAR_VALUE ) +if (reg->type !=SCALAR_VALUE ) { + stack_mask &= ~(1ull << i);continue ; + }if (!reg->precise) new_marks = true; reg->precise = true;@@ -1772,6 +1806,8 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno) reg_mask, stack_mask); } +if (!reg_mask && !stack_mask) +break ;if (!new_marks)break ;@@ -1781,6 +1817,15 @@ static int mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ; } +static int mark_chain_precision (struct bpf_verifier_env *env,int regno) +{ +return __mark_chain_precision (env, regno,-1 ); +} + +static int mark_chain_precision_stack (struct bpf_verifier_env *env,int spi) +{ +return __mark_chain_precision (env,-1 , spi); +}static bool is_spillable_regtype (enum bpf_reg_type type) {@@ -7114,6 +7159,46 @@ static int propagate_liveness(struct bpf_verifier_env *env,return 0 ; } +/* find precise scalars in the previous equivalent state and +* propagate them into the current state +*/ +static int propagate_precision (struct bpf_verifier_env *env, +const struct bpf_verifier_state *old) +{ +struct bpf_reg_state *state_reg; +struct bpf_func_state *state; +int i, err =0 ; + + state = old->frame[old->curframe]; + state_reg = state->regs; +for (i =0 ; i <BPF_REG_FP ; i++, state_reg++) { +if (state_reg->type !=SCALAR_VALUE || + !state_reg->precise) +continue ; +if (env->log.level &BPF_LOG_LEVEL2 ) +verbose (env,"propagating r%d\n" , i); + err =mark_chain_precision (env, i); +if (err <0 ) +return err; + } + +for (i =0 ; i < state->allocated_stack /BPF_REG_SIZE ; i++) { +if (state->stack[i].slot_type[0 ] !=STACK_SPILL ) +continue ; + state_reg = &state->stack[i].spilled_ptr; +if (state_reg->type !=SCALAR_VALUE || + !state_reg->precise) +continue ; +if (env->log.level &BPF_LOG_LEVEL2 ) +verbose (env,"propagating fp%d\n" , + (-i -1 ) *BPF_REG_SIZE ); + err =mark_chain_precision_stack (env, i); +if (err <0 ) +return err; + } +return 0 ; +} +static bool states_maybe_looping (struct bpf_verifier_state *old,struct bpf_verifier_state *cur) {@@ -7206,6 +7291,14 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)* this state and will pop a new one. */ err =propagate_liveness (env, &sl->state, cur); + +/* if previous state reached the exit with precision and +* current state is equivalent to it (except precsion marks) +* the precision needs to be propagated back in +* the current state. +*/ + err = err ? :push_jmp_history (env, cur); + err = err ? :propagate_precision (env, &sl->state);if (err)return err;return 1 ; --2.20.0
Quoted 14 lines · Alexei Starovoitov
When equivalent state is found the current state needs to propagate precision marks. Otherwise the verifier will prune the search incorrectly.
There is a price for correctness:
before before broken fixed cnst spill precise precise bpf_lb-DLB_L3.o 1923 8128 1863 1898 bpf_lb-DLB_L4.o 3077 6707 2468 2666 bpf_lb-DUNKNOWN.o 1062 1062 544 544 bpf_lxc-DDROP_ALL.o 166729 380712 22629 36823 bpf_lxc-DUNKNOWN.o 174607 440652 28805 45325 bpf_netdev.o 8407 31904 6801 7002 bpf_overlay.o 5420 23569 4754 4858 bpf_lxc_jit.o 39389 359445 50925 69631
Quoted 5 lines
Overall precision tracking is still very effective.
Fixes b5dc0163d8fd ("bpf: precise scalar_value tracking")Reported-by Lawrence Brakmo <[email protected]>Signed-off-by Alexei Starovoitov <[email protected]>
Applied, thanks!