From patchwork Thu Jan 31 06:58:34 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 1033939 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=pass (p=none dis=none) header.from=fb.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=fb.com header.i=@fb.com header.b="pO4BCJso"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43qrgT26hXz9sDB for ; Thu, 31 Jan 2019 17:59:01 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730383AbfAaG6p (ORCPT ); Thu, 31 Jan 2019 01:58:45 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:38662 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1725963AbfAaG6o (ORCPT ); Thu, 31 Jan 2019 01:58:44 -0500 Received: from pps.filterd (m0001255.ppops.net [127.0.0.1]) by mx0b-00082601.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x0V6qNc0026314 for ; Wed, 30 Jan 2019 22:58:43 -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=qP06fKrh/ClALux2i8O4ETB3gd8Wy6Yr92Dw+/x9LMc=; b=pO4BCJso/i8rVEkEgoHbzYpiYVRbw8ugAVA+hFAJkcNqQN0T5MVIMwUJRT5Vi4OJVsOS LDPL29YU3YbtOIeoELV/hXyq2RmGc+uA4nCiSbyJIsTJNCbcF3Ttd9KHbpSJu4bL1NpE boN7zw8Dm3zcIyCH8CRmp1462uf+jzQxXxk= Received: from mail.thefacebook.com ([199.201.64.23]) by mx0b-00082601.pphosted.com with ESMTP id 2qbnb6h2ya-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT) for ; Wed, 30 Jan 2019 22:58:43 -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; Wed, 30 Jan 2019 22:58:42 -0800 Received: by devvm7221.prn2.facebook.com (Postfix, from userid 137359) id 584349A30839; Wed, 30 Jan 2019 22:58:42 -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 0/3] Add BTF types deduplication algorithm Date: Wed, 30 Jan 2019 22:58:34 -0800 Message-ID: <20190131065837.3380288-1-andriin@fb.com> X-Mailer: git-send-email 2.17.1 X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-01-31_03:, , 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 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 | 11 + tools/lib/bpf/libbpf.map | 3 + tools/testing/selftests/bpf/test_btf.c | 535 ++++++- 4 files changed, 2333 insertions(+), 67 deletions(-)