From patchwork Thu Apr 29 13:46:54 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lorenz Bauer X-Patchwork-Id: 12231325 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-18.8 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D1BA2C433B4 for ; Thu, 29 Apr 2021 13:47:13 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 9E73C6144B for ; Thu, 29 Apr 2021 13:47:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237605AbhD2Nr7 (ORCPT ); Thu, 29 Apr 2021 09:47:59 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59058 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237384AbhD2Nr6 (ORCPT ); Thu, 29 Apr 2021 09:47:58 -0400 Received: from mail-wr1-x435.google.com (mail-wr1-x435.google.com [IPv6:2a00:1450:4864:20::435]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 67BF4C06138C for ; Thu, 29 Apr 2021 06:47:11 -0700 (PDT) Received: by mail-wr1-x435.google.com with SMTP id e5so38370382wrg.7 for ; Thu, 29 Apr 2021 06:47:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=xuRhzqKQieIT1ODprczAwmVtjBChKg2B72Ii/9rZYuo=; b=mb+38Lrf9QSlQEtF3RsuAnTvMklUYvlX2ZWo6zRuvrBMrWA5JruXFCP7ADqZ5lJUKg 2FBfDBVuILT0dRe155ErPHPZ5CQJR+0owuML2B0IB8vJX6iLri9bbb5bxacVPHJaF10c n+pyPLMvj5PQtTa/ywEI48+nh/q5Bq3y+FMR8= 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=xuRhzqKQieIT1ODprczAwmVtjBChKg2B72Ii/9rZYuo=; b=QYYGmX4UW0jXP8DfHfyVzp1p/pXoSRyXr//kZ+DBMBiHp5ugkG7kmzWrtrGbtaiwN+ wurCqkONbPP2whqkSEjBqTlV6fnnAvx6HWjwOvFNnjlp6sRTLYeUIZqbr3z6qFQkSBZa 4EUeHKHv8+fRd0I5uXjVB+/tyhGggyMBP8wnfgCjg+ueTUa02wdDWP1iCRXpHvQp2vJ9 KRI4vjMUBZDo8GddwEw/DrXQUOJZEsMGNEOb/SB0tkVIwsfpabINA3b8S77nsnJsllRL F9p2ie86pg0rsKl+0wvdQlZJ26fejrd6U/b3Gsxyc62B+o0O2UzbNGJTfes1M5zhOXp1 1Tvw== X-Gm-Message-State: AOAM530GD98HlgJ/uitmFKv5i6sEks1GTlLGtoWsDmHZZ7EJ30Gwd6Qo +d/YUtPNd0jmXANSOmu3G4GJvbiGYpmyzg== X-Google-Smtp-Source: ABdhPJyYOwOAOQa4RTbnNWTD2m1DK4J8zLfa5DXnAbONdWGd5OI5jv+LWuI3uVJvoTg2H53uQ2jNfw== X-Received: by 2002:a5d:51ce:: with SMTP id n14mr29094253wrv.239.1619704029983; Thu, 29 Apr 2021 06:47:09 -0700 (PDT) Received: from localhost.localdomain (8.7.1.e.3.2.9.3.e.a.2.1.c.2.e.4.f.f.6.2.a.5.a.7.0.b.8.0.1.0.0.2.ip6.arpa. [2001:8b0:7a5a:26ff:4e2c:12ae:3923:e178]) by smtp.gmail.com with ESMTPSA id x8sm5105592wru.70.2021.04.29.06.47.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Apr 2021 06:47:09 -0700 (PDT) From: Lorenz Bauer To: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko Cc: kernel-team@cloudflare.com, Lorenz Bauer , netdev@vger.kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH bpf-next 1/3] bpf: verifier: improve function state reallocation Date: Thu, 29 Apr 2021 14:46:54 +0100 Message-Id: <20210429134656.122225-2-lmb@cloudflare.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20210429134656.122225-1-lmb@cloudflare.com> References: <20210429134656.122225-1-lmb@cloudflare.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Resizing and copying stack and reference tracking state currently does a lot of kfree / kmalloc when the size of the tracked set changes. The logic in copy_*_state and realloc_*_state is also hard to follow. Refactor this into two core functions. copy_array copies from a source into a destination. It avoids reallocation by taking the allocated size of the destination into account via ksize(). The function is essentially krealloc_array, with the difference that the contents of dst are not preserved. realloc_array changes the size of an array and zeroes newly allocated items. Contrary to krealloc both functions don't free the destination if the size is zero. Instead we rely on free_func_state to clean up. realloc_stack_state is renamed to grow_stack_state to better convey that it never shrinks the stack state. Signed-off-by: Lorenz Bauer --- kernel/bpf/verifier.c | 195 ++++++++++++++++++++++-------------------- 1 file changed, 100 insertions(+), 95 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8fd552c16763..67d914b26a39 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -737,81 +737,104 @@ static void print_verifier_state(struct bpf_verifier_env *env, verbose(env, "\n"); } -#define COPY_STATE_FN(NAME, COUNT, FIELD, SIZE) \ -static int copy_##NAME##_state(struct bpf_func_state *dst, \ - const struct bpf_func_state *src) \ -{ \ - if (!src->FIELD) \ - return 0; \ - if (WARN_ON_ONCE(dst->COUNT < src->COUNT)) { \ - /* internal bug, make state invalid to reject the program */ \ - memset(dst, 0, sizeof(*dst)); \ - return -EFAULT; \ - } \ - memcpy(dst->FIELD, src->FIELD, \ - sizeof(*src->FIELD) * (src->COUNT / SIZE)); \ - return 0; \ -} -/* copy_reference_state() */ -COPY_STATE_FN(reference, acquired_refs, refs, 1) -/* copy_stack_state() */ -COPY_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE) -#undef COPY_STATE_FN - -#define REALLOC_STATE_FN(NAME, COUNT, FIELD, SIZE) \ -static int realloc_##NAME##_state(struct bpf_func_state *state, int size, \ - bool copy_old) \ -{ \ - u32 old_size = state->COUNT; \ - struct bpf_##NAME##_state *new_##FIELD; \ - int slot = size / SIZE; \ - \ - if (size <= old_size || !size) { \ - if (copy_old) \ - return 0; \ - state->COUNT = slot * SIZE; \ - if (!size && old_size) { \ - kfree(state->FIELD); \ - state->FIELD = NULL; \ - } \ - return 0; \ - } \ - new_##FIELD = kmalloc_array(slot, sizeof(struct bpf_##NAME##_state), \ - GFP_KERNEL); \ - if (!new_##FIELD) \ - return -ENOMEM; \ - if (copy_old) { \ - if (state->FIELD) \ - memcpy(new_##FIELD, state->FIELD, \ - sizeof(*new_##FIELD) * (old_size / SIZE)); \ - memset(new_##FIELD + old_size / SIZE, 0, \ - sizeof(*new_##FIELD) * (size - old_size) / SIZE); \ - } \ - state->COUNT = slot * SIZE; \ - kfree(state->FIELD); \ - state->FIELD = new_##FIELD; \ - return 0; \ +/* copy array src of length n * size bytes to dst. dst is reallocated if it's too + * small to hold src. This is different from krealloc since we don't want to preserve + * the contents of dst. + * + * Leaves dst untouched if src is NULL or length is zero. Returns NULL if memory could + * not be allocated. + */ +static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t flags) +{ + size_t bytes; + + if (ZERO_OR_NULL_PTR(src)) + goto out; + + if (unlikely(check_mul_overflow(n, size, &bytes))) + return NULL; + + if (ksize(dst) < bytes) { + kfree(dst); + dst = kmalloc_track_caller(bytes, flags); + if (!dst) + return NULL; + } + + memcpy(dst, src, bytes); +out: + return dst ? dst : ZERO_SIZE_PTR; } -/* realloc_reference_state() */ -REALLOC_STATE_FN(reference, acquired_refs, refs, 1) -/* realloc_stack_state() */ -REALLOC_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE) -#undef REALLOC_STATE_FN - -/* do_check() starts with zero-sized stack in struct bpf_verifier_state to - * make it consume minimal amount of memory. check_stack_write() access from - * the program calls into realloc_func_state() to grow the stack size. - * Note there is a non-zero 'parent' pointer inside bpf_verifier_state - * which realloc_stack_state() copies over. It points to previous - * bpf_verifier_state which is never reallocated. + +/* resize an array from old_n items to new_n items. the array is reallocated if it's too + * small to hold new_n items. new items are zeroed out if the array grows. + * + * Contrary to krealloc_array, does not free arr if new_n is zero. */ -static int realloc_func_state(struct bpf_func_state *state, int stack_size, - int refs_size, bool copy_old) +static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size) +{ + if (!new_n || old_n == new_n) + goto out; + + arr = krealloc_array(arr, new_n, size, GFP_KERNEL); + if (!arr) + return NULL; + + if (new_n > old_n) + memset(arr + old_n * size, 0, (new_n - old_n) * size); + +out: + return arr ? arr : ZERO_SIZE_PTR; +} + +static int copy_reference_state(struct bpf_func_state *dst, const struct bpf_func_state *src) +{ + dst->refs = copy_array(dst->refs, src->refs, src->acquired_refs, + sizeof(struct bpf_reference_state), GFP_KERNEL); + if (!dst->refs) + return -ENOMEM; + + dst->acquired_refs = src->acquired_refs; + return 0; +} + +static int copy_stack_state(struct bpf_func_state *dst, const struct bpf_func_state *src) +{ + size_t n = src->allocated_stack / BPF_REG_SIZE; + + dst->stack = copy_array(dst->stack, src->stack, n, sizeof(struct bpf_stack_state), + GFP_KERNEL); + if (!dst->stack) + return -ENOMEM; + + dst->allocated_stack = src->allocated_stack; + return 0; +} + +static int resize_reference_state(struct bpf_func_state *state, size_t n) { - int err = realloc_reference_state(state, refs_size, copy_old); - if (err) - return err; - return realloc_stack_state(state, stack_size, copy_old); + state->refs = realloc_array(state->refs, state->acquired_refs, n, + sizeof(struct bpf_reference_state)); + if (!state->refs) + return -ENOMEM; + + state->acquired_refs = n; + return 0; +} + +static int grow_stack_state(struct bpf_func_state *state, int size) +{ + size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE; + + if (old_n >= n) + return 0; + + state->stack = realloc_array(state->stack, old_n, n, sizeof(struct bpf_stack_state)); + if (!state->stack) + return -ENOMEM; + + state->allocated_stack = size; + return 0; } /* Acquire a pointer id from the env and update the state->refs to include @@ -825,7 +848,7 @@ static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx) int new_ofs = state->acquired_refs; int id, err; - err = realloc_reference_state(state, state->acquired_refs + 1, true); + err = resize_reference_state(state, state->acquired_refs + 1); if (err) return err; id = ++env->id_gen; @@ -854,18 +877,6 @@ static int release_reference_state(struct bpf_func_state *state, int ptr_id) return -EINVAL; } -static int transfer_reference_state(struct bpf_func_state *dst, - struct bpf_func_state *src) -{ - int err = realloc_reference_state(dst, src->acquired_refs, false); - if (err) - return err; - err = copy_reference_state(dst, src); - if (err) - return err; - return 0; -} - static void free_func_state(struct bpf_func_state *state) { if (!state) @@ -904,10 +915,6 @@ static int copy_func_state(struct bpf_func_state *dst, { int err; - err = realloc_func_state(dst, src->allocated_stack, src->acquired_refs, - false); - if (err) - return err; memcpy(dst, src, offsetof(struct bpf_func_state, acquired_refs)); err = copy_reference_state(dst, src); if (err) @@ -2590,8 +2597,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env, u32 dst_reg = env->prog->insnsi[insn_idx].dst_reg; struct bpf_reg_state *reg = NULL; - err = realloc_func_state(state, round_up(slot + 1, BPF_REG_SIZE), - state->acquired_refs, true); + err = grow_stack_state(state, round_up(slot + 1, BPF_REG_SIZE)); if (err) return err; /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0, @@ -2753,8 +2759,7 @@ static int check_stack_write_var_off(struct bpf_verifier_env *env, if (value_reg && register_is_null(value_reg)) writing_zero = true; - err = realloc_func_state(state, round_up(-min_off, BPF_REG_SIZE), - state->acquired_refs, true); + err = grow_stack_state(state, round_up(-min_off, BPF_REG_SIZE)); if (err) return err; @@ -5629,7 +5634,7 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn subprog /* subprog number within this prog */); /* Transfer references to the callee */ - err = transfer_reference_state(callee, caller); + err = copy_reference_state(callee, caller); if (err) return err; @@ -5780,7 +5785,7 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) } /* Transfer references to the caller */ - err = transfer_reference_state(caller, callee); + err = copy_reference_state(caller, callee); if (err) return err; From patchwork Thu Apr 29 13:46:55 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lorenz Bauer X-Patchwork-Id: 12231329 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-18.8 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2F24DC43460 for ; Thu, 29 Apr 2021 13:47:22 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F120B6143B for ; Thu, 29 Apr 2021 13:47:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239269AbhD2NsF (ORCPT ); Thu, 29 Apr 2021 09:48:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59070 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237712AbhD2Nr7 (ORCPT ); Thu, 29 Apr 2021 09:47:59 -0400 Received: from mail-wr1-x434.google.com (mail-wr1-x434.google.com [IPv6:2a00:1450:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 44507C06138F for ; Thu, 29 Apr 2021 06:47:12 -0700 (PDT) Received: by mail-wr1-x434.google.com with SMTP id m9so54289356wrx.3 for ; Thu, 29 Apr 2021 06:47:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=QdgOqG3N8NoAcJADfF2z8B9NTKycDIqg1ia12c/fZYc=; b=UM68g7XYs5/gTZCOix9BtmchrVRoD1W+BgHLFEdn+Bf0VCGZSDISCR92YwvXcpfT9x aRdyyRGPlnrZHZU8RICPPOWu9nMGeVObKXmwTRBEVt6ad5J/Mu09rNUtb7MAYof+IJ9s QST+TLqItfgbywCFCeyTuWufaYLmfFgA4mq/A= 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=QdgOqG3N8NoAcJADfF2z8B9NTKycDIqg1ia12c/fZYc=; b=kuOQ/Bm/LoX0Y5VlH9MS3hzPQQCbSZVyZVlw/7K/GB2rnJF3xHj5kzBuN/NRYjTNuI YCjUy5qnRx6BYpESx1ZExSuEWlgrl8fr+vivVSIGP0SMCxMq0cpnfF3xhGZZ5UzWKkxg cGvUCHRhtq/dpOLlfHfL9SVb2Wl+ihhtfh9WuUSjK7yrB1ngKetLg0K4Ze3H7mLozjDL H3ULwNeYHLT8+qTKJ2KKf/7skEihl0q0o89VafyygTmzkouFOHQZVo2dFIDmn8hLPzfK IDM+w37yApbi2KDmGGGO+YNE9LZrjt85LfcS9xu+uhijBfRNPoyMiEN3IV5bL03ZMC/S d5xQ== X-Gm-Message-State: AOAM531Ld+xjcs8xxDu+7T2tLMwY1xi6iCgZlkP1JEOx8CBVNe5BJDVd UKf2/56gb6zMshRAXCYLzwyuLg== X-Google-Smtp-Source: ABdhPJzBNsKBTsNJidzrYzujh6W7/cmshdmEYtoyNxbD0YWX9LTkIAo6uG3NbjdcyeeRsISHpgeg8g== X-Received: by 2002:a5d:59a9:: with SMTP id p9mr3796298wrr.289.1619704031046; Thu, 29 Apr 2021 06:47:11 -0700 (PDT) Received: from localhost.localdomain (8.7.1.e.3.2.9.3.e.a.2.1.c.2.e.4.f.f.6.2.a.5.a.7.0.b.8.0.1.0.0.2.ip6.arpa. [2001:8b0:7a5a:26ff:4e2c:12ae:3923:e178]) by smtp.gmail.com with ESMTPSA id x8sm5105592wru.70.2021.04.29.06.47.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Apr 2021 06:47:10 -0700 (PDT) From: Lorenz Bauer To: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko Cc: kernel-team@cloudflare.com, Lorenz Bauer , netdev@vger.kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH bpf-next 2/3] bpf: verifier: use copy_array for jmp_history Date: Thu, 29 Apr 2021 14:46:55 +0100 Message-Id: <20210429134656.122225-3-lmb@cloudflare.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20210429134656.122225-1-lmb@cloudflare.com> References: <20210429134656.122225-1-lmb@cloudflare.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Eliminate a couple needless kfree / kmalloc cycles by using copy_array for jmp_history. Signed-off-by: Lorenz Bauer --- kernel/bpf/verifier.c | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 67d914b26a39..2b9623ac9288 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -926,16 +926,13 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state, const struct bpf_verifier_state *src) { struct bpf_func_state *dst; - u32 jmp_sz = sizeof(struct bpf_idx_pair) * src->jmp_history_cnt; int i, err; - if (dst_state->jmp_history_cnt < src->jmp_history_cnt) { - kfree(dst_state->jmp_history); - dst_state->jmp_history = kmalloc(jmp_sz, GFP_USER); - if (!dst_state->jmp_history) - return -ENOMEM; - } - memcpy(dst_state->jmp_history, src->jmp_history, jmp_sz); + dst_state->jmp_history = copy_array(dst_state->jmp_history, src->jmp_history, + src->jmp_history_cnt, sizeof(struct bpf_idx_pair), + GFP_USER); + if (!dst_state->jmp_history) + return -ENOMEM; dst_state->jmp_history_cnt = src->jmp_history_cnt; /* if dst has more stack frames then src frame, free them */ From patchwork Thu Apr 29 13:46:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lorenz Bauer X-Patchwork-Id: 12231327 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-18.8 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 92177C433B4 for ; Thu, 29 Apr 2021 13:47:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 536E86144B for ; Thu, 29 Apr 2021 13:47:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238960AbhD2NsB (ORCPT ); Thu, 29 Apr 2021 09:48:01 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59078 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238629AbhD2NsA (ORCPT ); Thu, 29 Apr 2021 09:48:00 -0400 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6B1B8C06138D for ; Thu, 29 Apr 2021 06:47:13 -0700 (PDT) Received: by mail-wr1-x42b.google.com with SMTP id h15so14775186wre.11 for ; Thu, 29 Apr 2021 06:47:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=cclXdLP22V8eZQOTypKMrwFQ0CzgP0dJouQ4GLcb3wg=; b=baizyMXjXngHFguaCs3eYVLB3u2xkTKFDKS05vlop/A1N3z1adqRQNJ0LGpYG31DxV 5jYrypkkz4FmEYC5zISvh5Yo9CAg7kjZvaGoi5V9dzHsmW6bCKvfrmrgBc7xa/3ACZN8 TsldlkbjunGZVUh4eHkkU4YKmvKupQFWgSmTc= 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=cclXdLP22V8eZQOTypKMrwFQ0CzgP0dJouQ4GLcb3wg=; b=eLoBdV19+1ARg1zJku1GHzt9nT5nZMI0auAbjRHQ3tk5tn6Ss5CnmpU9sxP1FR0AiQ eI8dEFF2KUAOfv3IDli36f3d2RyQjJoc6O6qEF0UwLKTWsHFAjlRur5RPfBsrFA2TYu5 Ylb552qVn2RAqgB2OGYUciPfmp17h2Eypd3JkZF7zbZC1sO3SsdrK3V0w+DCGAeptwrj VFN+1Z3G5XCzSNUvyNP8/FVKTtkO6ks1Oc84NhcZhxzjiyNADbVyQc3WrxJYL0ITa+4s 9WgrvwCpfVlj1Nf59HS/dqLJpSXNBZ4/tkmwMTu5XSQ2GMchzUGw0exotYELuPz5WmZD dBMQ== X-Gm-Message-State: AOAM532LaKMnT/Wi9eJ07xRqXX/w79VY2fsQPyRNS35Ap/O4C2F+86/M Zoh0ZY6D1jrLWbIFhXxKZiEVug== X-Google-Smtp-Source: ABdhPJz7MqotNNcA3lHfLygXy0+EcQm+B1R0UoNPYWx4zmd/ZOlzbR2xy1qN/cyJL/TQ92dRp+u2ug== X-Received: by 2002:a5d:45cb:: with SMTP id b11mr16892767wrs.343.1619704032199; Thu, 29 Apr 2021 06:47:12 -0700 (PDT) Received: from localhost.localdomain (8.7.1.e.3.2.9.3.e.a.2.1.c.2.e.4.f.f.6.2.a.5.a.7.0.b.8.0.1.0.0.2.ip6.arpa. [2001:8b0:7a5a:26ff:4e2c:12ae:3923:e178]) by smtp.gmail.com with ESMTPSA id x8sm5105592wru.70.2021.04.29.06.47.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Apr 2021 06:47:11 -0700 (PDT) From: Lorenz Bauer To: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko Cc: kernel-team@cloudflare.com, Lorenz Bauer , netdev@vger.kernel.org, bpf@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH bpf-next 3/3] bpf: verifier: allocate idmap scratch in verifier env Date: Thu, 29 Apr 2021 14:46:56 +0100 Message-Id: <20210429134656.122225-4-lmb@cloudflare.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20210429134656.122225-1-lmb@cloudflare.com> References: <20210429134656.122225-1-lmb@cloudflare.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net func_states_equal makes a very short lived allocation for idmap, probably because it's too large to fit on the stack. However the function is called quite often, leading to a lot of alloc / free churn. Replace the temporary allocation with dedicated scratch space in struct bpf_verifier_env. Signed-off-by: Lorenz Bauer Acked-by: Edward Cree --- include/linux/bpf_verifier.h | 8 +++++++ kernel/bpf/verifier.c | 46 ++++++++++++------------------------ 2 files changed, 23 insertions(+), 31 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 6023a1367853..9e794f8b1df9 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -215,6 +215,13 @@ struct bpf_idx_pair { u32 idx; }; +struct bpf_id_pair { + u32 old; + u32 cur; +}; + +/* Maximum number of register states that can exist at once */ +#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) #define MAX_CALL_FRAMES 8 struct bpf_verifier_state { /* call stack tracking */ @@ -417,6 +424,7 @@ struct bpf_verifier_env { const struct bpf_line_info *prev_linfo; struct bpf_verifier_log log; struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1]; + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; struct { int *insn_state; int *insn_stack; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 2b9623ac9288..fbcfdae05c39 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -9746,13 +9746,6 @@ static bool range_within(struct bpf_reg_state *old, old->s32_max_value >= cur->s32_max_value; } -/* Maximum number of register states that can exist at once */ -#define ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) -struct idpair { - u32 old; - u32 cur; -}; - /* If in the old state two registers had the same id, then they need to have * the same id in the new state as well. But that id could be different from * the old state, so we need to track the mapping from old to new ids. @@ -9763,11 +9756,11 @@ struct idpair { * So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */ -static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap) +static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap) { unsigned int i; - for (i = 0; i < ID_MAP_SIZE; i++) { + for (i = 0; i < BPF_ID_MAP_SIZE; i++) { if (!idmap[i].old) { /* Reached an empty slot; haven't seen this id before */ idmap[i].old = old_id; @@ -9880,7 +9873,7 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn, /* Returns true if (rold safe implies rcur safe) */ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, - struct idpair *idmap) + struct bpf_id_pair *idmap) { bool equal; @@ -9998,7 +9991,7 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur, static bool stacksafe(struct bpf_func_state *old, struct bpf_func_state *cur, - struct idpair *idmap) + struct bpf_id_pair *idmap) { int i, spi; @@ -10095,32 +10088,23 @@ static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur) * whereas register type in current state is meaningful, it means that * the current state will reach 'bpf_exit' instruction safely */ -static bool func_states_equal(struct bpf_func_state *old, +static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old, struct bpf_func_state *cur) { - struct idpair *idmap; - bool ret = false; int i; - idmap = kcalloc(ID_MAP_SIZE, sizeof(struct idpair), GFP_KERNEL); - /* If we failed to allocate the idmap, just say it's not safe */ - if (!idmap) + memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch)); + for (i = 0; i < MAX_BPF_REG; i++) + if (!regsafe(&old->regs[i], &cur->regs[i], env->idmap_scratch)) + return false; + + if (!stacksafe(old, cur, env->idmap_scratch)) return false; - for (i = 0; i < MAX_BPF_REG; i++) { - if (!regsafe(&old->regs[i], &cur->regs[i], idmap)) - goto out_free; - } - - if (!stacksafe(old, cur, idmap)) - goto out_free; - if (!refsafe(old, cur)) - goto out_free; - ret = true; -out_free: - kfree(idmap); - return ret; + return false; + + return true; } static bool states_equal(struct bpf_verifier_env *env, @@ -10147,7 +10131,7 @@ static bool states_equal(struct bpf_verifier_env *env, for (i = 0; i <= old->curframe; i++) { if (old->frame[i]->callsite != cur->frame[i]->callsite) return false; - if (!func_states_equal(old->frame[i], cur->frame[i])) + if (!func_states_equal(env, old->frame[i], cur->frame[i])) return false; } return true;