1 files changed, 345 insertions, 52 deletions

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 95f9354495ad..5c2cb5bd84ce 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -176,7 +176,7 @@ struct bpf_verifier_stack_elem {
         struct bpf_verifier_stack_elem *next;
 };
 
-#define BPF_COMPLEXITY_LIMIT_STACK      1024
+#define BPF_COMPLEXITY_LIMIT_JMP_SEQ    8192
 #define BPF_COMPLEXITY_LIMIT_STATES     64
 
 #define BPF_MAP_PTR_UNPRIV      1UL
@@ -782,8 +782,9 @@ static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env,
         if (err)
                 goto err;
         elem->st.speculative |= speculative;
-        if (env->stack_size > BPF_COMPLEXITY_LIMIT_STACK) {
-                verbose(env, "BPF program is too complex\n");
+        if (env->stack_size > BPF_COMPLEXITY_LIMIT_JMP_SEQ) {
+                verbose(env, "The sequence of %d jumps is too complex.\n",
+                        env->stack_size);
                 goto err;
         }
         return &elem->st;
@@ -981,6 +982,7 @@ static void mark_reg_not_init(struct bpf_verifier_env *env,
         __mark_reg_not_init(regs + regno);
 }
 
+#define DEF_NOT_SUBREG  (0)
 static void init_reg_state(struct bpf_verifier_env *env,
                            struct bpf_func_state *state)
 {
@@ -991,6 +993,7 @@ static void init_reg_state(struct bpf_verifier_env *env,
                 mark_reg_not_init(env, regs, i);
                 regs[i].live = REG_LIVE_NONE;
                 regs[i].parent = NULL;
+                regs[i].subreg_def = DEF_NOT_SUBREG;
         }
 
         /* frame pointer */
@@ -1136,7 +1139,7 @@ next:
  */
 static int mark_reg_read(struct bpf_verifier_env *env,
                          const struct bpf_reg_state *state,
-                         struct bpf_reg_state *parent)
+                         struct bpf_reg_state *parent, u8 flag)
 {
         bool writes = parent == state->parent; /* Observe write marks */
         int cnt = 0;
@@ -1151,17 +1154,26 @@ static int mark_reg_read(struct bpf_verifier_env *env,
                                 parent->var_off.value, parent->off);
                         return -EFAULT;
                 }
-                if (parent->live & REG_LIVE_READ)
+                /* The first condition is more likely to be true than the
+                 * second, checked it first.
+                 */
+                if ((parent->live & REG_LIVE_READ) == flag ||
+                    parent->live & REG_LIVE_READ64)
                         /* The parentage chain never changes and
                          * this parent was already marked as LIVE_READ.
                          * There is no need to keep walking the chain again and
                          * keep re-marking all parents as LIVE_READ.
                          * This case happens when the same register is read
                          * multiple times without writes into it in-between.
+                         * Also, if parent has the stronger REG_LIVE_READ64 set,
+                         * then no need to set the weak REG_LIVE_READ32.
                          */
                         break;
                 /* ... then we depend on parent's value */
-                parent->live |= REG_LIVE_READ;
+                parent->live |= flag;
+                /* REG_LIVE_READ64 overrides REG_LIVE_READ32. */
+                if (flag == REG_LIVE_READ64)
+                        parent->live &= ~REG_LIVE_READ32;
                 state = parent;
                 parent = state->parent;
                 writes = true;
@@ -1173,12 +1185,129 @@ static int mark_reg_read(struct bpf_verifier_env *env,
         return 0;
 }
 
+/* This function is supposed to be used by the following 32-bit optimization
+ * code only. It returns TRUE if the source or destination register operates
+ * on 64-bit, otherwise return FALSE.
+ */
+static bool is_reg64(struct bpf_verifier_env *env, struct bpf_insn *insn,
+                     u32 regno, struct bpf_reg_state *reg, enum reg_arg_type t)
+{
+        u8 code, class, op;
+
+        code = insn->code;
+        class = BPF_CLASS(code);
+        op = BPF_OP(code);
+        if (class == BPF_JMP) {
+                /* BPF_EXIT for "main" will reach here. Return TRUE
+                 * conservatively.
+                 */
+                if (op == BPF_EXIT)
+                        return true;
+                if (op == BPF_CALL) {
+                        /* BPF to BPF call will reach here because of marking
+                         * caller saved clobber with DST_OP_NO_MARK for which we
+                         * don't care the register def because they are anyway
+                         * marked as NOT_INIT already.
+                         */
+                        if (insn->src_reg == BPF_PSEUDO_CALL)
+                                return false;
+                        /* Helper call will reach here because of arg type
+                         * check, conservatively return TRUE.
+                         */
+                        if (t == SRC_OP)
+                                return true;
+
+                        return false;
+                }
+        }
+
+        if (class == BPF_ALU64 || class == BPF_JMP ||
+            /* BPF_END always use BPF_ALU class. */
+            (class == BPF_ALU && op == BPF_END && insn->imm == 64))
+                return true;
+
+        if (class == BPF_ALU || class == BPF_JMP32)
+                return false;
+
+        if (class == BPF_LDX) {
+                if (t != SRC_OP)
+                        return BPF_SIZE(code) == BPF_DW;
+                /* LDX source must be ptr. */
+                return true;
+        }
+
+        if (class == BPF_STX) {
+                if (reg->type != SCALAR_VALUE)
+                        return true;
+                return BPF_SIZE(code) == BPF_DW;
+        }
+
+        if (class == BPF_LD) {
+                u8 mode = BPF_MODE(code);
+
+                /* LD_IMM64 */
+                if (mode == BPF_IMM)
+                        return true;
+
+                /* Both LD_IND and LD_ABS return 32-bit data. */
+                if (t != SRC_OP)
+                        return  false;
+
+                /* Implicit ctx ptr. */
+                if (regno == BPF_REG_6)
+                        return true;
+
+                /* Explicit source could be any width. */
+                return true;
+        }
+
+        if (class == BPF_ST)
+                /* The only source register for BPF_ST is a ptr. */
+                return true;
+
+        /* Conservatively return true at default. */
+        return true;
+}
+
+/* Return TRUE if INSN doesn't have explicit value define. */
+static bool insn_no_def(struct bpf_insn *insn)
+{
+        u8 class = BPF_CLASS(insn->code);
+
+        return (class == BPF_JMP || class == BPF_JMP32 ||
+                class == BPF_STX || class == BPF_ST);
+}
+
+/* Return TRUE if INSN has defined any 32-bit value explicitly. */
+static bool insn_has_def32(struct bpf_verifier_env *env, struct bpf_insn *insn)
+{
+        if (insn_no_def(insn))
+                return false;
+
+        return !is_reg64(env, insn, insn->dst_reg, NULL, DST_OP);
+}
+
+static void mark_insn_zext(struct bpf_verifier_env *env,
+                           struct bpf_reg_state *reg)
+{
+        s32 def_idx = reg->subreg_def;
+
+        if (def_idx == DEF_NOT_SUBREG)
+                return;
+
+        env->insn_aux_data[def_idx - 1].zext_dst = true;
+        /* The dst will be zero extended, so won't be sub-register anymore. */
+        reg->subreg_def = DEF_NOT_SUBREG;
+}
+
 static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
                          enum reg_arg_type t)
 {
         struct bpf_verifier_state *vstate = env->cur_state;
         struct bpf_func_state *state = vstate->frame[vstate->curframe];
+        struct bpf_insn *insn = env->prog->insnsi + env->insn_idx;
         struct bpf_reg_state *reg, *regs = state->regs;
+        bool rw64;
 
         if (regno >= MAX_BPF_REG) {
                 verbose(env, "R%d is invalid\n", regno);
@@ -1186,6 +1315,7 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
         }
 
         reg = &regs[regno];
+        rw64 = is_reg64(env, insn, regno, reg, t);
         if (t == SRC_OP) {
                 /* check whether register used as source operand can be read */
                 if (reg->type == NOT_INIT) {
@@ -1196,7 +1326,11 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
                 if (regno == BPF_REG_FP)
                         return 0;
 
-                return mark_reg_read(env, reg, reg->parent);
+                if (rw64)
+                        mark_insn_zext(env, reg);
+
+                return mark_reg_read(env, reg, reg->parent,
+                                     rw64 ? REG_LIVE_READ64 : REG_LIVE_READ32);
         } else {
                 /* check whether register used as dest operand can be written to */
                 if (regno == BPF_REG_FP) {
@@ -1204,6 +1338,7 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
                         return -EACCES;
                 }
                 reg->live |= REG_LIVE_WRITTEN;
+                reg->subreg_def = rw64 ? DEF_NOT_SUBREG : env->insn_idx + 1;
                 if (t == DST_OP)
                         mark_reg_unknown(env, regs, regno);
         }
@@ -1383,7 +1518,8 @@ static int check_stack_read(struct bpf_verifier_env *env,
                         state->regs[value_regno].live |= REG_LIVE_WRITTEN;
                 }
                 mark_reg_read(env, &reg_state->stack[spi].spilled_ptr,
-                              reg_state->stack[spi].spilled_ptr.parent);
+                              reg_state->stack[spi].spilled_ptr.parent,
+                              REG_LIVE_READ64);
                 return 0;
         } else {
                 int zeros = 0;
@@ -1400,7 +1536,8 @@ static int check_stack_read(struct bpf_verifier_env *env,
                         return -EACCES;
                 }
                 mark_reg_read(env, &reg_state->stack[spi].spilled_ptr,
-                              reg_state->stack[spi].spilled_ptr.parent);
+                              reg_state->stack[spi].spilled_ptr.parent,
+                              REG_LIVE_READ64);
                 if (value_regno >= 0) {
                         if (zeros == size) {
                                 /* any size read into register is zero extended,
@@ -2109,6 +2246,12 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
                                                     value_regno);
                                 if (reg_type_may_be_null(reg_type))
                                         regs[value_regno].id = ++env->id_gen;
+                                /* A load of ctx field could have different
+                                 * actual load size with the one encoded in the
+                                 * insn. When the dst is PTR, it is for sure not
+                                 * a sub-register.
+                                 */
+                                regs[value_regno].subreg_def = DEF_NOT_SUBREG;
                         }
                         regs[value_regno].type = reg_type;
                 }
@@ -2368,7 +2511,8 @@ mark:
                  * the whole slot to be marked as 'read'
                  */
                 mark_reg_read(env, &state->stack[spi].spilled_ptr,
-                              state->stack[spi].spilled_ptr.parent);
+                              state->stack[spi].spilled_ptr.parent,
+                              REG_LIVE_READ64);
         }
         return update_stack_depth(env, state, min_off);
 }
@@ -3332,6 +3476,9 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
                 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
         }
 
+        /* helper call returns 64-bit value. */
+        regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
+
         /* update return register (already marked as written above) */
         if (fn->ret_type == RET_INTEGER) {
                 /* sets type to SCALAR_VALUE */
@@ -4263,6 +4410,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
                                  */
                                 *dst_reg = *src_reg;
                                 dst_reg->live |= REG_LIVE_WRITTEN;
+                                dst_reg->subreg_def = DEF_NOT_SUBREG;
                         } else {
                                 /* R1 = (u32) R2 */
                                 if (is_pointer_value(env, insn->src_reg)) {
@@ -4273,6 +4421,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
                                 } else if (src_reg->type == SCALAR_VALUE) {
                                         *dst_reg = *src_reg;
                                         dst_reg->live |= REG_LIVE_WRITTEN;
+                                        dst_reg->subreg_def = env->insn_idx + 1;
                                 } else {
                                         mark_reg_unknown(env, regs,
                                                          insn->dst_reg);
@@ -5352,16 +5501,23 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
          * Already marked as written above.
          */
         mark_reg_unknown(env, regs, BPF_REG_0);
+        /* ld_abs load up to 32-bit skb data. */
+        regs[BPF_REG_0].subreg_def = env->insn_idx + 1;
         return 0;
 }
 
 static int check_return_code(struct bpf_verifier_env *env)
 {
+        struct tnum enforce_attach_type_range = tnum_unknown;
         struct bpf_reg_state *reg;
         struct tnum range = tnum_range(0, 1);
 
         switch (env->prog->type) {
         case BPF_PROG_TYPE_CGROUP_SKB:
+                if (env->prog->expected_attach_type == BPF_CGROUP_INET_EGRESS) {
+                        range = tnum_range(0, 3);
+                        enforce_attach_type_range = tnum_range(2, 3);
+                }
         case BPF_PROG_TYPE_CGROUP_SOCK:
         case BPF_PROG_TYPE_CGROUP_SOCK_ADDR:
         case BPF_PROG_TYPE_SOCK_OPS:
@@ -5380,18 +5536,23 @@ static int check_return_code(struct bpf_verifier_env *env)
         }
 
         if (!tnum_in(range, reg->var_off)) {
+                char tn_buf[48];
+
                 verbose(env, "At program exit the register R0 ");
                 if (!tnum_is_unknown(reg->var_off)) {
-                        char tn_buf[48];
-
                         tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
                         verbose(env, "has value %s", tn_buf);
                 } else {
                         verbose(env, "has unknown scalar value");
                 }
-                verbose(env, " should have been 0 or 1\n");
+                tnum_strn(tn_buf, sizeof(tn_buf), range);
+                verbose(env, " should have been %s\n", tn_buf);
                 return -EINVAL;
         }
+
+        if (!tnum_is_unknown(enforce_attach_type_range) &&
+            tnum_in(enforce_attach_type_range, reg->var_off))
+                env->prog->enforce_expected_attach_type = 1;
         return 0;
 }
 
@@ -5435,7 +5596,25 @@ enum {
         BRANCH = 2,
 };
 
-#define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
+static u32 state_htab_size(struct bpf_verifier_env *env)
+{
+        return env->prog->len;
+}
+
+static struct bpf_verifier_state_list **explored_state(
+                                        struct bpf_verifier_env *env,
+                                        int idx)
+{
+        struct bpf_verifier_state *cur = env->cur_state;
+        struct bpf_func_state *state = cur->frame[cur->curframe];
+
+        return &env->explored_states[(idx ^ state->callsite) % state_htab_size(env)];
+}
+
+static void init_explored_state(struct bpf_verifier_env *env, int idx)
+{
+        env->insn_aux_data[idx].prune_point = true;
+}
 
 /* t, w, e - match pseudo-code above:
  * t - index of current instruction
@@ -5461,7 +5640,7 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
 
         if (e == BRANCH)
                 /* mark branch target for state pruning */
-                env->explored_states[w] = STATE_LIST_MARK;
+                init_explored_state(env, w);
 
         if (insn_state[w] == 0) {
                 /* tree-edge */
@@ -5529,9 +5708,9 @@ peek_stack:
                         else if (ret < 0)
                                 goto err_free;
                         if (t + 1 < insn_cnt)
-                                env->explored_states[t + 1] = STATE_LIST_MARK;
+                                init_explored_state(env, t + 1);
                         if (insns[t].src_reg == BPF_PSEUDO_CALL) {
-                                env->explored_states[t] = STATE_LIST_MARK;
+                                init_explored_state(env, t);
                                 ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env);
                                 if (ret == 1)
                                         goto peek_stack;
@@ -5554,10 +5733,10 @@ peek_stack:
                          * after every call and jump
                          */
                         if (t + 1 < insn_cnt)
-                                env->explored_states[t + 1] = STATE_LIST_MARK;
+                                init_explored_state(env, t + 1);
                 } else {
                         /* conditional jump with two edges */
-                        env->explored_states[t] = STATE_LIST_MARK;
+                        init_explored_state(env, t);
                         ret = push_insn(t, t + 1, FALLTHROUGH, env);
                         if (ret == 1)
                                 goto peek_stack;
@@ -6005,12 +6184,10 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
         struct bpf_verifier_state_list *sl;
         int i;
 
-        sl = env->explored_states[insn];
-        if (!sl)
-                return;
-
-        while (sl != STATE_LIST_MARK) {
-                if (sl->state.curframe != cur->curframe)
+        sl = *explored_state(env, insn);
+        while (sl) {
+                if (sl->state.insn_idx != insn ||
+                    sl->state.curframe != cur->curframe)
                         goto next;
                 for (i = 0; i <= cur->curframe; i++)
                         if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
@@ -6292,20 +6469,33 @@ static bool states_equal(struct bpf_verifier_env *env,
         return true;
 }
 
+/* Return 0 if no propagation happened. Return negative error code if error
+ * happened. Otherwise, return the propagated bit.
+ */
 static int propagate_liveness_reg(struct bpf_verifier_env *env,
                                   struct bpf_reg_state *reg,
                                   struct bpf_reg_state *parent_reg)
 {
+        u8 parent_flag = parent_reg->live & REG_LIVE_READ;
+        u8 flag = reg->live & REG_LIVE_READ;
         int err;
 
-        if (parent_reg->live & REG_LIVE_READ || !(reg->live & REG_LIVE_READ))
+        /* When comes here, read flags of PARENT_REG or REG could be any of
+         * REG_LIVE_READ64, REG_LIVE_READ32, REG_LIVE_NONE. There is no need
+         * of propagation if PARENT_REG has strongest REG_LIVE_READ64.
+         */
+        if (parent_flag == REG_LIVE_READ64 ||
+            /* Or if there is no read flag from REG. */
+            !flag ||
+            /* Or if the read flag from REG is the same as PARENT_REG. */
+            parent_flag == flag)
                 return 0;
 
-        err = mark_reg_read(env, reg, parent_reg);
+        err = mark_reg_read(env, reg, parent_reg, flag);
         if (err)
                 return err;
 
-        return 0;
+        return flag;
 }
 
 /* A write screens off any subsequent reads; but write marks come from the
@@ -6339,8 +6529,10 @@ static int propagate_liveness(struct bpf_verifier_env *env,
                 for (i = frame < vstate->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++) {
                         err = propagate_liveness_reg(env, &state_reg[i],
                                                      &parent_reg[i]);
-                        if (err)
+                        if (err < 0)
                                 return err;
+                        if (err == REG_LIVE_READ64)
+                                mark_insn_zext(env, &parent_reg[i]);
                 }
 
                 /* Propagate stack slots. */
@@ -6350,11 +6542,11 @@ static int propagate_liveness(struct bpf_verifier_env *env,
                         state_reg = &state->stack[i].spilled_ptr;
                         err = propagate_liveness_reg(env, state_reg,
                                                      parent_reg);
-                        if (err)
+                        if (err < 0)
                                 return err;
                 }
         }
-        return err;
+        return 0;
 }
 
 static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
@@ -6364,18 +6556,21 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
         struct bpf_verifier_state *cur = env->cur_state, *new;
         int i, j, err, states_cnt = 0;
 
-        pprev = &env->explored_states[insn_idx];
-        sl = *pprev;
-
-        if (!sl)
+        if (!env->insn_aux_data[insn_idx].prune_point)
                 /* this 'insn_idx' instruction wasn't marked, so we will not
                  * be doing state search here
                  */
                 return 0;
 
+        pprev = explored_state(env, insn_idx);
+        sl = *pprev;
+
         clean_live_states(env, insn_idx, cur);
 
-        while (sl != STATE_LIST_MARK) {
+        while (sl) {
+                states_cnt++;
+                if (sl->state.insn_idx != insn_idx)
+                        goto next;
                 if (states_equal(env, &sl->state, cur)) {
                         sl->hit_cnt++;
                         /* reached equivalent register/stack state,
@@ -6393,7 +6588,6 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
                                 return err;
                         return 1;
                 }
-                states_cnt++;
                 sl->miss_cnt++;
                 /* heuristic to determine whether this state is beneficial
                  * to keep checking from state equivalence point of view.
@@ -6420,6 +6614,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
                         sl = *pprev;
                         continue;
                 }
+next:
                 pprev = &sl->next;
                 sl = *pprev;
         }
@@ -6451,8 +6646,9 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
                 kfree(new_sl);
                 return err;
         }
-        new_sl->next = env->explored_states[insn_idx];
-        env->explored_states[insn_idx] = new_sl;
+        new->insn_idx = insn_idx;
+        new_sl->next = *explored_state(env, insn_idx);
+        *explored_state(env, insn_idx) = new_sl;
         /* connect new state to parentage chain. Current frame needs all
          * registers connected. Only r6 - r9 of the callers are alive (pushed
          * to the stack implicitly by JITs) so in callers' frames connect just
@@ -7130,14 +7326,23 @@ static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env)
  * insni[off, off + cnt).  Adjust corresponding insn_aux_data by copying
  * [0, off) and [off, end) to new locations, so the patched range stays zero
  */
-static int adjust_insn_aux_data(struct bpf_verifier_env *env, u32 prog_len,
-                                u32 off, u32 cnt)
+static int adjust_insn_aux_data(struct bpf_verifier_env *env,
+                                struct bpf_prog *new_prog, u32 off, u32 cnt)
 {
         struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data;
+        struct bpf_insn *insn = new_prog->insnsi;
+        u32 prog_len;
         int i;
 
+        /* aux info at OFF always needs adjustment, no matter fast path
+         * (cnt == 1) is taken or not. There is no guarantee INSN at OFF is the
+         * original insn at old prog.
+         */
+        old_data[off].zext_dst = insn_has_def32(env, insn + off + cnt - 1);
+
         if (cnt == 1)
                 return 0;
+        prog_len = new_prog->len;
         new_data = vzalloc(array_size(prog_len,
                                       sizeof(struct bpf_insn_aux_data)));
         if (!new_data)
@@ -7145,8 +7350,10 @@ static int adjust_insn_aux_data(struct bpf_verifier_env *env, u32 prog_len,
         memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off);
         memcpy(new_data + off + cnt - 1, old_data + off,
                sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
-        for (i = off; i < off + cnt - 1; i++)
+        for (i = off; i < off + cnt - 1; i++) {
                 new_data[i].seen = true;
+                new_data[i].zext_dst = insn_has_def32(env, insn + i);
+        }
         env->insn_aux_data = new_data;
         vfree(old_data);
         return 0;
@@ -7179,7 +7386,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
                                 env->insn_aux_data[off].orig_idx);
                 return NULL;
         }
-        if (adjust_insn_aux_data(env, new_prog->len, off, len))
+        if (adjust_insn_aux_data(env, new_prog, off, len))
                 return NULL;
         adjust_subprog_starts(env, off, len);
         return new_prog;
@@ -7443,6 +7650,84 @@ static int opt_remove_nops(struct bpf_verifier_env *env)
         return 0;
 }
 
+static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
+                                         const union bpf_attr *attr)
+{
+        struct bpf_insn *patch, zext_patch[2], rnd_hi32_patch[4];
+        struct bpf_insn_aux_data *aux = env->insn_aux_data;
+        int i, patch_len, delta = 0, len = env->prog->len;
+        struct bpf_insn *insns = env->prog->insnsi;
+        struct bpf_prog *new_prog;
+        bool rnd_hi32;
+
+        rnd_hi32 = attr->prog_flags & BPF_F_TEST_RND_HI32;
+        zext_patch[1] = BPF_ZEXT_REG(0);
+        rnd_hi32_patch[1] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_AX, 0);
+        rnd_hi32_patch[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
+        rnd_hi32_patch[3] = BPF_ALU64_REG(BPF_OR, 0, BPF_REG_AX);
+        for (i = 0; i < len; i++) {
+                int adj_idx = i + delta;
+                struct bpf_insn insn;
+
+                insn = insns[adj_idx];
+                if (!aux[adj_idx].zext_dst) {
+                        u8 code, class;
+                        u32 imm_rnd;
+
+                        if (!rnd_hi32)
+                                continue;
+
+                        code = insn.code;
+                        class = BPF_CLASS(code);
+                        if (insn_no_def(&insn))
+                                continue;
+
+                        /* NOTE: arg "reg" (the fourth one) is only used for
+                         *       BPF_STX which has been ruled out in above
+                         *       check, it is safe to pass NULL here.
+                         */
+                        if (is_reg64(env, &insn, insn.dst_reg, NULL, DST_OP)) {
+                                if (class == BPF_LD &&
+                                    BPF_MODE(code) == BPF_IMM)
+                                        i++;
+                                continue;
+                        }
+
+                        /* ctx load could be transformed into wider load. */
+                        if (class == BPF_LDX &&
+                            aux[adj_idx].ptr_type == PTR_TO_CTX)
+                                continue;
+
+                        imm_rnd = get_random_int();
+                        rnd_hi32_patch[0] = insn;
+                        rnd_hi32_patch[1].imm = imm_rnd;
+                        rnd_hi32_patch[3].dst_reg = insn.dst_reg;
+                        patch = rnd_hi32_patch;
+                        patch_len = 4;
+                        goto apply_patch_buffer;
+                }
+
+                if (!bpf_jit_needs_zext())
+                        continue;
+
+                zext_patch[0] = insn;
+                zext_patch[1].dst_reg = insn.dst_reg;
+                zext_patch[1].src_reg = insn.dst_reg;
+                patch = zext_patch;
+                patch_len = 2;
+apply_patch_buffer:
+                new_prog = bpf_patch_insn_data(env, adj_idx, patch, patch_len);
+                if (!new_prog)
+                        return -ENOMEM;
+                env->prog = new_prog;
+                insns = new_prog->insnsi;
+                aux = env->insn_aux_data;
+                delta += patch_len - 1;
+        }
+
+        return 0;
+}
+
 /* convert load instructions that access fields of a context type into a
  * sequence of instructions that access fields of the underlying structure:
  *     struct __sk_buff    -> struct sk_buff
@@ -8130,16 +8415,15 @@ static void free_states(struct bpf_verifier_env *env)
         if (!env->explored_states)
                 return;
 
-        for (i = 0; i < env->prog->len; i++) {
+        for (i = 0; i < state_htab_size(env); i++) {
                 sl = env->explored_states[i];
 
-                if (sl)
-                        while (sl != STATE_LIST_MARK) {
-                                sln = sl->next;
-                                free_verifier_state(&sl->state, false);
-                                kfree(sl);
-                                sl = sln;
-                        }
+                while (sl) {
+                        sln = sl->next;
+                        free_verifier_state(&sl->state, false);
+                        kfree(sl);
+                        sl = sln;
+                }
         }
 
         kvfree(env->explored_states);
@@ -8239,7 +8523,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,
                         goto skip_full_check;
         }
 
-        env->explored_states = kvcalloc(env->prog->len,
+        env->explored_states = kvcalloc(state_htab_size(env),
                                        sizeof(struct bpf_verifier_state_list *),
                                        GFP_USER);
         ret = -ENOMEM;
@@ -8294,6 +8578,15 @@ skip_full_check:
         if (ret == 0)
                 ret = fixup_bpf_calls(env);
 
+        /* do 32-bit optimization after insn patching has done so those patched
+         * insns could be handled correctly.
+         */
+        if (ret == 0 && !bpf_prog_is_dev_bound(env->prog->aux)) {
+                ret = opt_subreg_zext_lo32_rnd_hi32(env, attr);
+                env->prog->aux->verifier_zext = bpf_jit_needs_zext() ? !ret
+                                                                     : false;
+        }
+
         if (ret == 0)
                 ret = fixup_call_args(env);