From mboxrd@z Thu Jan 1 00:00:00 1970 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=-3.1 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_PASS,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 806A8C282C4 for ; Tue, 5 Feb 2019 01:30:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 4A5892083B for ; Tue, 5 Feb 2019 01:30:12 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=fb.com header.i=@fb.com header.b="FEyWUETT" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728467AbfBEBaK (ORCPT ); Mon, 4 Feb 2019 20:30:10 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:48658 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725965AbfBEBaK (ORCPT ); Mon, 4 Feb 2019 20:30:10 -0500 Received: from pps.filterd (m0109332.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x151SKuM015410 for ; Mon, 4 Feb 2019 17:30:09 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : mime-version : content-type; s=facebook; bh=uTzGRYjpSMPlwIATwO58vEC1mUdIVWbZkQug0C+84x4=; b=FEyWUETTkVY3QhbdHF+IgCeG0vc32CrOvIY4FT4MHXx5Lxu8LyT6oNHZbE14fgytSQLU /cZ9G2ZiBu/E/2h9jJPHszTWbsRbqqvf4l5r9t77yK/L5JuQVeZuKPIZfPw3KGs4Jwdx m59vj4yaYNAIJFOhAsW3wvbiaYjwkhmdgLY= Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2qeyvp059e-6 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Mon, 04 Feb 2019 17:30:09 -0800 Received: from mx-out.facebook.com (2620:10d:c081:10::13) by mail.thefacebook.com (2620:10d:c081:35::130) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA) id 15.1.1531.3; Mon, 4 Feb 2019 17:30:07 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id 2A3129F5570E; Mon, 4 Feb 2019 17:30:04 -0800 (PST) Smtp-Origin-Hostprefix: devvm From: Andrii Nakryiko Smtp-Origin-Hostname: devvm7221.prn2.facebook.com To: , , , , , , , , CC: Andrii Nakryiko Smtp-Origin-Cluster: prn2c23 Subject: [PATCH btf v2 0/3] Add BTF types deduplication algorithm Date: Mon, 4 Feb 2019 17:29:43 -0800 Message-ID: <20190205012946.1590917-1-andriin@fb.com> X-Mailer: git-send-email 2.17.1 X-FB-Internal: Safe MIME-Version: 1.0 Content-Type: text/plain X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-02-04_15:,, signatures=0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org This patch series adds BTF deduplication algorithm to libbpf. This algorithm allows to take BTF type information containing duplicate per-compilation unit information and reduce it to equivalent set of BTF types with no duplication without loss of information. It also deduplicates strings and removes those strings that are not referenced from any BTF type (and line information in .BTF.ext section, if any). Algorithm also resolves struct/union forward declarations into concrete BTF types across multiple compilation units to facilitate better deduplication ratio. If undesired, this resolution can be disabled through specifying corresponding options. When applied to BTF data emitted by pahole's DWARF->BTF converter, it reduces the overall size of .BTF section by about 65x, from about 112MB to 1.75MB, leaving only 29247 out of initial 3073497 BTF type descriptors. Algorithm with minor differences and preliminary results before FUNC/FUNC_PROTO support is also described more verbosely at: https://facebookmicrosites.github.io/bpf/blog/2018/11/14/btf-enhancement.html v1->v2: - rebase on latest bpf-next - err_log/elog -> pr_debug - btf__dedup, btf__get_strings, btf__get_nr_types listed under 0.0.2 version Andrii Nakryiko (3): btf: extract BTF type size calculation btf: add BTF types deduplication algorithm selftests/btf: add initial BTF dedup tests tools/lib/bpf/btf.c | 1851 +++++++++++++++++++++++- tools/lib/bpf/btf.h | 10 + tools/lib/bpf/libbpf.map | 3 + tools/testing/selftests/bpf/test_btf.c | 535 ++++++- 4 files changed, 2332 insertions(+), 67 deletions(-) -- 2.17.1