From patchwork Tue Jan 1 01:37:34 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019727 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="pmk/JSk1"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43TGzJ0BMMz9s9h for ; Tue, 1 Jan 2019 12:38:20 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728186AbfAABiE (ORCPT ); Mon, 31 Dec 2018 20:38:04 -0500 Received: from mail-qk1-f195.google.com ([209.85.222.195]:38839 "EHLO mail-qk1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727302AbfAABiD (ORCPT ); Mon, 31 Dec 2018 20:38:03 -0500 Received: by mail-qk1-f195.google.com with SMTP id a1so16295440qkc.5 for ; Mon, 31 Dec 2018 17:38:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=sTnxxIpEip0vgI1VfRIW0JRR4EcsGIc8GFIDwCV73BQ=; b=pmk/JSk1ALNbmsjzaD6cyk6Z5TsBeqNiaTzDmhXoIcYlFJX0sjzW5hh2DeKFaaFk6t JIXfLEfeo7ti86zgw0VCk9z7cMm2yP1MsPQ69UXC7XDP0ORl/9+xJfeqe1neqzClfacu 956a9zRxHSLIHugm3yiCz6iLUKfQOAMiSWXGINuwlXsi41dcJ2P5QVLAK/FGGLS3nvJt ir/4o80uGbyk0KvwD1cW9xjIKcgrqTuKU2xCPwqF7f4guBMm1/Bn0x+aKGJrBTTBtEGj f1Z/uZt9f5McZy6Z1+1irHc+mS93YDNOJriORnzW9EPYDMTyVpMFpVe4KHPVCcL50tvN Onzw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=sTnxxIpEip0vgI1VfRIW0JRR4EcsGIc8GFIDwCV73BQ=; b=GeK6+N42vv7xZ5KLsTG/I5S1mTEAAIy4sMGRZatEqdYezthJH7BlQrgIKgsEZu/ZNu hTWieVpPZd+Ff4A/eWmuatdKTsCbpEGD3aQX8YTR1fcSNiTFl/jnlxiaMNRvktFvuGXl 6q0HOF8HSM+vOaGa0mRscPnz3SHkb0uCXapHdLKLz4JvQTE2xgpxZ0DarttjTrF4JVM3 ZkO+Emr5D+6uHIEEPijVb1oFUFLHvjg4z/xs3CD95y31ANplCdoinXOiCg/mUMp+Xs/o IAEgnac7tz6jANEphu1v78FtmsgvJwHRMlVdAlmu7dZIsPizj11Y3RTh4bzKfRxvrV+j oeTg== X-Gm-Message-State: AJcUukcwdnAbS7D5ppU1jRNwU1fb/McWIBz9sVJGBXGLU1wCsyumo0ew V3hSrBic+9/cp8vvDeKFzs+jpqo0WVc= X-Google-Smtp-Source: ALg8bN7GLrPC9PPa8Zt28QQxV20cEf2AzC1tH6jhMXPI8bcYkKrdCactxTRjDm7+9KEbQMQ72hrxMw== X-Received: by 2002:a37:2fc2:: with SMTP id v185mr37110895qkh.168.1546306681886; Mon, 31 Dec 2018 17:38:01 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id p72sm19707544qke.87.2018.12.31.17.38.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 31 Dec 2018 17:38:01 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net, yhs@fb.com Cc: netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v4 03/12] bpf: verifier: remove dead code Date: Mon, 31 Dec 2018 17:37:34 -0800 Message-Id: <20190101013743.23935-4-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20190101013743.23935-1-jakub.kicinski@netronome.com> References: <20190101013743.23935-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Instead of overwriting dead code with jmp -1 instructions remove it completely for root. Adjust verifier state and line info appropriately. v2: - adjust func_info (Alexei); - make sure first instruction retains line info (Alexei). v4: (Yonghong) - remove unnecessary if (!insn to remove) checks; - always keep last line info if first live instruction lacks one. Signed-off-by: Jakub Kicinski Acked-by: Yonghong Song --- include/linux/filter.h | 1 + kernel/bpf/core.c | 12 +++ kernel/bpf/verifier.c | 167 ++++++++++++++++++++++++++++++++++++++++- 3 files changed, 177 insertions(+), 3 deletions(-) diff --git a/include/linux/filter.h b/include/linux/filter.h index 8c8544b375eb..2cdb50bbf867 100644 --- a/include/linux/filter.h +++ b/include/linux/filter.h @@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void) struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, const struct bpf_insn *patch, u32 len); +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt); void bpf_clear_redirect_map(struct bpf_map *map); diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index a40057b2c556..cc6fa754627c 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, return prog_adj; } +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt) +{ + /* Branch offsets can't overflow when program is shrinking, no need + * to call bpf_adj_branches(..., true) here + */ + memmove(prog->insnsi + off, prog->insnsi + off + cnt, + sizeof(struct bpf_insn) * (prog->len - off - cnt)); + prog->len -= cnt; + + return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false)); +} + void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp) { int i; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 30e2cd399b4a..2f786acb65ce 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6233,6 +6233,141 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of return new_prog; } +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env, + u32 off, u32 cnt) +{ + int i, j; + + /* find first prog starting at or after off (first to remove) */ + for (i = 0; i < env->subprog_cnt; i++) + if (env->subprog_info[i].start >= off) + break; + /* find first prog starting at or after off + cnt (first to stay) */ + for (j = i; j < env->subprog_cnt; j++) + if (env->subprog_info[j].start >= off + cnt) + break; + /* if j doesn't start exactly at off + cnt, we are just removing + * the front of previous prog + */ + if (env->subprog_info[j].start != off + cnt) + j--; + + if (j > i) { + struct bpf_prog_aux *aux = env->prog->aux; + int move; + + /* move fake 'exit' subprog as well */ + move = env->subprog_cnt + 1 - j; + + memmove(env->subprog_info + i, + env->subprog_info + j, + sizeof(*env->subprog_info) * move); + env->subprog_cnt -= j - i; + + /* remove func_info */ + if (aux->func_info) { + move = aux->func_info_cnt - j; + + memmove(aux->func_info + i, + aux->func_info + j, + sizeof(*aux->func_info) * move); + aux->func_info_cnt -= j - i; + } + } else { + /* convert i from "first prog to remove" to "first to adjust" */ + if (env->subprog_info[i].start == off) + i++; + } + + /* update fake 'exit' subprog as well */ + for (; i <= env->subprog_cnt; i++) + env->subprog_info[i].start -= cnt; + + return 0; +} + +static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off, + u32 cnt) +{ + struct bpf_prog *prog = env->prog; + u32 i, l_off, l_cnt, nr_linfo; + struct bpf_line_info *linfo; + + nr_linfo = prog->aux->nr_linfo; + if (!nr_linfo) + return 0; + + linfo = prog->aux->linfo; + + /* find first line info to remove, count lines to be removed */ + for (i = 0; i < nr_linfo; i++) + if (linfo[i].insn_off >= off) + break; + + l_off = i; + l_cnt = 0; + for (; i < nr_linfo; i++) + if (linfo[i].insn_off < off + cnt) + l_cnt++; + else + break; + + /* first live insn doesn't match first live linfo, inherit */ + if (prog->len != off && l_cnt && + (i == nr_linfo || linfo[i].insn_off != off + cnt)) { + l_cnt--; + linfo[--i].insn_off = off + cnt; + } + + /* remove the line info which refers to the removed instructions */ + if (l_cnt) { + memmove(linfo + l_off, linfo + i, + sizeof(*linfo) * (nr_linfo - i)); + + prog->aux->nr_linfo -= l_cnt; + nr_linfo = prog->aux->nr_linfo; + } + + /* pull all linfo[i].insn_off >= off + cnt in by cnt */ + for (i = l_off; i < nr_linfo; i++) + linfo[i].insn_off -= cnt; + + /* fix up all subprogs (incl. 'exit') which start >= off */ + for (i = 0; i <= env->subprog_cnt; i++) + if (env->subprog_info[i].linfo_idx > l_off) { + if (env->subprog_info[i].linfo_idx >= l_off + l_cnt) + env->subprog_info[i].linfo_idx -= l_cnt; + else + env->subprog_info[i].linfo_idx = l_off; + } + + return 0; +} + +static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt) +{ + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + unsigned int orig_prog_len = env->prog->len; + int err; + + err = bpf_remove_insns(env->prog, off, cnt); + if (err) + return err; + + err = adjust_subprog_starts_after_remove(env, off, cnt); + if (err) + return err; + + err = bpf_adj_linfo_after_remove(env, off, cnt); + if (err) + return err; + + memmove(aux_data + off, aux_data + off + cnt, + sizeof(*aux_data) * (orig_prog_len - off - cnt)); + + return 0; +} + /* The verifier does more data flow analysis than llvm and will not * explore branches that are dead at run time. Malicious programs can * have dead code too. Therefore replace all dead at-run-time code @@ -6293,6 +6428,30 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env) } } +static int opt_remove_dead_code(struct bpf_verifier_env *env) +{ + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + int insn_cnt = env->prog->len; + int i, err; + + for (i = 0; i < insn_cnt; i++) { + int j; + + j = 0; + while (i + j < insn_cnt && !aux_data[i + j].seen) + j++; + if (!j) + continue; + + err = verifier_remove_insns(env, i, j); + if (err) + return err; + insn_cnt = env->prog->len; + } + + 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 @@ -7032,11 +7191,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, if (is_priv) { if (ret == 0) opt_hard_wire_dead_code_branches(env); + if (ret == 0) + ret = opt_remove_dead_code(env); + } else { + if (ret == 0) + sanitize_dead_code(env); } - if (ret == 0) - sanitize_dead_code(env); - if (ret == 0) /* program is valid, convert *(u32*)(ctx + off) accesses */ ret = convert_ctx_accesses(env);