From patchwork Thu Mar 29 22:44:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Edward Cree X-Patchwork-Id: 893054 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=solarflare.com Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 40C0Db3m50z9s25 for ; Fri, 30 Mar 2018 09:44:31 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751199AbeC2WoY (ORCPT ); Thu, 29 Mar 2018 18:44:24 -0400 Received: from dispatch1-us1.ppe-hosted.com ([67.231.154.164]:44108 "EHLO dispatch1-us1.ppe-hosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750735AbeC2WoX (ORCPT ); Thu, 29 Mar 2018 18:44:23 -0400 X-Virus-Scanned: Proofpoint Essentials engine Received: from webmail.solarflare.com (webmail.solarflare.com [12.187.104.26]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1-us1.ppe-hosted.com (Proofpoint Essentials ESMTP Server) with ESMTPS id 56D5978005A; Thu, 29 Mar 2018 22:44:22 +0000 (UTC) Received: from ec-desktop.uk.solarflarecom.com (10.17.20.45) by ocex03.SolarFlarecom.com (10.20.40.36) with Microsoft SMTP Server (TLS) id 15.0.1044.25; Thu, 29 Mar 2018 15:44:19 -0700 From: Edward Cree Subject: [PATCH v2 bpf-next 0/3] bpf/verifier: subprog/func_call simplifications To: Alexei Starovoitov , Daniel Borkmann CC: Message-ID: Date: Thu, 29 Mar 2018 23:44:17 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.2 MIME-Version: 1.0 Content-Language: en-GB X-Originating-IP: [10.17.20.45] X-MDID: 1522363463-McqPhawDNF2M Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org By storing subprog boundaries as a subprogno mark on each insn, rather than a start (and implicit end) for each subprog, we collect a number of gains: * More efficient determination of which subprog contains a given insn, and thus of find_subprog (which subprog begins at a given insn). * Number of verifier "full recursive walk" passes is reduced, since most of the work is done in the main insn walk (do_check()). Leftover work in other passes is mostly linear scans (O(insn_cnt)) or, in the case of check_max_stack_depth(), a topological sort (O(subprog_cnt)). Some other changes were also included to support this: * Per-subprog info is stored in env->subprog_info, an array of structs, rather than several arrays with a common index. * Call graph is now stored in the new bpf_subprog_info struct; used here for check_max_stack_depth() but may have other uses too. Along with this, patch #3 puts parent pointers (used by liveness analysis) in the registers instead of the func_state or verifier_state, so that we don't need skip_callee() machinery. This also does the right thing for stack slots, so they don't need their own special handling for liveness marking either. Edward Cree (3): bpf/verifier: validate func_calls by marking at do_check() time bpf/verifier: update selftests bpf/verifier: per-register parent pointers include/linux/bpf_verifier.h | 32 +- kernel/bpf/verifier.c | 631 +++++++++++++--------------- tools/testing/selftests/bpf/test_verifier.c | 51 ++- 3 files changed, 344 insertions(+), 370 deletions(-)