From patchwork Fri Mar 8 01:07:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexei Starovoitov X-Patchwork-Id: 13586406 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 36423C54E49 for ; Fri, 8 Mar 2024 01:08:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BCA7E6B02EF; Thu, 7 Mar 2024 20:08:19 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B79E36B02F0; Thu, 7 Mar 2024 20:08:19 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A41516B02F1; Thu, 7 Mar 2024 20:08:19 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 94B2E6B02EF for ; Thu, 7 Mar 2024 20:08:19 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 68AF1161260 for ; Fri, 8 Mar 2024 01:08:19 +0000 (UTC) X-FDA: 81872085918.19.28091FD Received: from mail-pg1-f171.google.com (mail-pg1-f171.google.com [209.85.215.171]) by imf09.hostedemail.com (Postfix) with ESMTP id A30D8140013 for ; Fri, 8 Mar 2024 01:08:17 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=SR61LUNj; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf09.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1709860097; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=EI2QShqdFcXiHl5u5EKsbNDVVgl4AIdTHHFtnNkvCoY=; b=sbBzGWrFXNpRaVIhRyddYag0E3U+iHoYva05LOCBfmKF08tSmS5SnWEtQ6jUL/Co8/iJ6N HGGznXlNgsJmLUb5WYurjVbfgCtNDZctdnGUduHsZr9ztt1rzuBXfakTWJye1pbyRW2h+2 9Ienos07PxP5Yi2Gnvutax3XckH9J6k= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=SR61LUNj; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf09.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1709860097; a=rsa-sha256; cv=none; b=VEPpU8/vmFJyLHh5Z4IGSUdIs8fjD5z3Ihil0ooV6md1yOfn5vBmFeUwNhzTrchNqM2bMG r1MkBsUb7ReqQp8h3W/avKePW/b/R1XTuRozTbWHsngrCGr/lW2NPRp41GPUx7jmIQkK9/ CgT56Md/J9hQZl3qFBjXF0AmpeDdIug= Received: by mail-pg1-f171.google.com with SMTP id 41be03b00d2f7-5d42e7ab8a9so1051100a12.3 for ; Thu, 07 Mar 2024 17:08:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1709860096; x=1710464896; darn=kvack.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=EI2QShqdFcXiHl5u5EKsbNDVVgl4AIdTHHFtnNkvCoY=; b=SR61LUNjKyLb8rPgZWRa6tdJiLDabY9pWJZZbczX1ZddoGjEPi6lXu+Q84wpktCN+J po+6qQINb/jldZ0y73aevRCu9bjx4QH8YVlkTV+JH48A+n6yvMfCcp84PXuMtM3N8BgD uZjrq99zNIVTICI0hoPCZm09VelEk3b1VQCbQSEuOLnMy+NrYeRteGseWdzKfJJjwwbw pjsRwV1XF7n5wjtm3UEIU6bqlOBt+PUBCJlP9XpJipjFxZQrJjilroVhFPcycrR8Tjwp I26wgemVf0TvvQp3S6djc8kk1ClW4hG0uwa+jGl9TmATybbQqlQbdTbpFqnZLlncg6YH v8IQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709860096; x=1710464896; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=EI2QShqdFcXiHl5u5EKsbNDVVgl4AIdTHHFtnNkvCoY=; b=OEYM4NEuKxovBIPUL3+WqfEqWtD61UUiUOBwoSa8G2ThTl4Pt0J00hVEfA2YwFlq1m PVbeSwLmCV6XaDEo0O18DqH2pus2QbiwKXbFnC7P1ssYAIplEqKBycODj04OdPKcv0yR 9Jj4DCin2JVMkUxaxDK44t+2VmdURc5Ukat2yhoDJf7qKspF0dQn6sSt8hKLrzurz7ZP hydVkDNyrFiepFqqA+HZRGzMnEdM6he7ofyrLHgDPXramOUwzF55kuaR4TJQwqquwW5d FnbacbTXZvldX57pHm4JEuHKnZUFOpvmkdsDto38RibZDcjj8uhBFd/GeaIcuXOJUvVi 5mLw== X-Forwarded-Encrypted: i=1; AJvYcCWtFJx3p4g6D7c2Ty3W2zHhWU39TABV3FOqOkOO3E75TmnuJBYzfBkKWiaFVzZJFM0b6iHYCeTp6NxyfoeIF7JMeSs= X-Gm-Message-State: AOJu0YxyAy47q8fXwZo8uSbj+RwPgWaQm7mP/ShX0Wz28+l8FkrKAGCc CP5PabOHhRxYwO+JqMyzBYJbkuY5yYTtwUffNsOVsx7VDiDbVOqD X-Google-Smtp-Source: AGHT+IHFzE8C3rcxRA/gDOYTjs8IvvLOGOaLMt5TUXLgWVuJqOBe4ezPITt4Y6mvt/NGvlPiGP2/+A== X-Received: by 2002:a05:6a20:7488:b0:1a1:83be:8187 with SMTP id p8-20020a056a20748800b001a183be8187mr64431pzd.5.1709860096269; Thu, 07 Mar 2024 17:08:16 -0800 (PST) Received: from localhost.localdomain ([2620:10d:c090:400::5:428c]) by smtp.gmail.com with ESMTPSA id f4-20020a056a0022c400b006e510c61d49sm511287pfj.183.2024.03.07.17.08.14 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 07 Mar 2024 17:08:15 -0800 (PST) From: Alexei Starovoitov To: bpf@vger.kernel.org Cc: daniel@iogearbox.net, andrii@kernel.org, torvalds@linux-foundation.org, brho@google.com, hannes@cmpxchg.org, akpm@linux-foundation.org, urezki@gmail.com, hch@infradead.org, linux-mm@kvack.org, kernel-team@fb.com Subject: [PATCH v3 bpf-next 00/14] bpf: Introduce BPF arena. Date: Thu, 7 Mar 2024 17:07:58 -0800 Message-Id: <20240308010812.89848-1-alexei.starovoitov@gmail.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: A30D8140013 X-Stat-Signature: mqys78bgsyfm4cb7bfkrkmgiy6jfdchp X-Rspam-User: X-HE-Tag: 1709860097-297825 X-HE-Meta: U2FsdGVkX182S2a2Vmj7BSXh25ynOd7wP0yFqIz4YpMOzjtblAcTRrdwa4rwOwmsP6+mf2CCS5A+i/LiIn7wlDcLbOvxMXr0ssmR33u+jz0XosZ/5OOJb2tlM2TXR+NV2IUOBcvBMm3H/fGz2GIRTBxi+Dvz44o0jgG7SmyDfNBoC8bELQlsaiCc4a2goxJ8+MIERYLP6k7LsmpReyDxBTNcLC9DevEf9kWmBfdm5DugEmbVcaBib1OFU574d8+tsNZwYuvRkY9rTvBNez818iX7vSRlBtls9LL/z7ZQrMm1siqZjzKuy9vP+CDP76eGPfw09H7od3tj4MxFAZlR/K7CdsoA8PZyWPajSOqq6XBR2WtJrZjw2ZZVIWO9LI/PyG2BVTp/gKyk3WlWJ2fL0z9+bWBUUvb32YxdHeh9QltUeYIpmcs6SG01e9dChbbF1XlOr1yXAuBPkZuxoe0dmXKjzvv3N9pungKkkxqO7AwPPXoOnMCymS/Hn0AbfszPUONZjgVsyb3NDRIfC+fGgTrnyfZyyPNwgS1iwTBBakP8e8XnU/2J6eujzdTDxFbWcg978ND0PidLVpC/PEdmoKpc332nFl80MuVPqemsGHKKvE9Cq2tnyQexT4lcY8osy0RhxQAv1UnhWCsE0pMZ15ChGzP2qI09jlD8eMVukLg2BUr2sFd+mL+K/EpQ8xNOJPOx9YiCu+JSC2jo7TnFAj+nuDUjBMDTG3OgwQvBQIlhtpmEKrdwascERmYJzE9+84VXTWi9t6TRngggwGiXsKqj5EF7gEThNJvRDiCIJzl8vsCJGSIxewnByqW1kWhEsTHBKmClK8hDsj42hhkHsEdiRABDt7CdbusLQWWwwsg8okobmIipcDZvCLSDjY9QNE0KIJNZkFB/YsgQtI0nZJcfhcPf70GqHySQgo9L2t/ZoFZ5NOrMAnOd6Hk8pnFTn+Z+JOlPgVLMdMWLqJY iV+Wvmql PYakiZODJpY/kuzbPGhR+PvD82M/qBiVY+qY5smwM+HAUWymy+IvPQglqt4hbQt6Ai6oB5gxT1KQOAGUk7yUtaGVjPTgbE6XqNwzutFyHmiwHIHQ6424nPchPCDd0GCNbVPMGBhpODiAo3Kfc9+IlyHaOcyx2U/MA6EXdPcWD42Jc/4OdJhCqvUGbZegiC0+ZN7LPjunVArC8K/A2gLdaaMPSBSHJB2IeEA7R3mNoSBbGETEZPca83L64kBn2/XytjePd0rxUqd4dR/ZC9XrtIbaRdfCcymFdWY0xJfRveBag9pMnXpamwGsvlqqZYPS+4H22FRLKligK5TmNMTiBkOhL1HF6D0MB6Q/z+3dRe5fMRz3qZ7kmuuPUHWHvopLt7hHls1DMlGJYWApFvep9tbMwStDIIT3ksFGeuj7+F6NKONfH2jDmohlzkaR6uBOx5YhOZaDBcEMQLb0Pk7be/+HwClN4ydIxaEXw6bIhW6mOGhAhYoyGzfR7BC4OJ+MjTJOB4ZdA04AT8c5NfUj28O9v087TcK4Vhijx/LocHhL6cvWVm9HfRp0ED61OJQJODTvHvGr7kRcD2os= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: From: Alexei Starovoitov v2->v3: - contains bpf bits only, but cc-ing past audience for continuity - since prerequisite patches landed, this series focus on the main functionality of bpf_arena. - adopted Andrii's approach to support arena in libbpf. - simplified LLVM support. Instead of two instructions it's now only one. - switched to cond_break (instead of open coded iters) in selftests - implemented several follow-ups that will be sent after this set . remember first IP and bpf insn that faulted in arena. report to user space via bpftool . copy paste and tweak glob_match() aka mini-regex as a selftests/bpf - see patch 1 for detailed description of bpf_arena v1->v2: - Improved commit log with reasons for using vmap_pages_range() in arena. Thanks to Johannes - Added support for __arena global variables in bpf programs - Fixed race conditions spotted by Barret - Fixed wrap32 issue spotted by Barret - Fixed bpf_map_mmap_sz() the way Andrii suggested The work on bpf_arena was inspired by Barret's work: https://github.com/google/ghost-userspace/blob/main/lib/queue.bpf.h that implements queues, lists and AVL trees completely as bpf programs using giant bpf array map and integer indices instead of pointers. bpf_arena is a sparse array that allows to use normal C pointers to build such data structures. Last few patches implement page_frag allocator, link list and hash table as bpf programs. v1: bpf programs have multiple options to communicate with user space: - Various ring buffers (perf, ftrace, bpf): The data is streamed unidirectionally from bpf to user space. - Hash map: The bpf program populates elements, and user space consumes them via bpf syscall. - mmap()-ed array map: Libbpf creates an array map that is directly accessed by the bpf program and mmap-ed to user space. It's the fastest way. Its disadvantage is that memory for the whole array is reserved at the start. Alexei Starovoitov (13): bpf: Introduce bpf_arena. bpf: Disasm support for addr_space_cast instruction. bpf: Add x86-64 JIT support for PROBE_MEM32 pseudo instructions. bpf: Add x86-64 JIT support for bpf_addr_space_cast instruction. bpf: Recognize addr_space_cast instruction in the verifier. bpf: Recognize btf_decl_tag("arg:arena") as PTR_TO_ARENA. libbpf: Add __arg_arena to bpf_helpers.h libbpf: Add support for bpf_arena. bpftool: Recognize arena map type bpf: Add helper macro bpf_addr_space_cast() selftests/bpf: Add unit tests for bpf_arena_alloc/free_pages selftests/bpf: Add bpf_arena_list test. selftests/bpf: Add bpf_arena_htab test. Andrii Nakryiko (1): libbpf: Recognize __arena global varaibles. arch/x86/net/bpf_jit_comp.c | 231 +++++++- include/linux/bpf.h | 10 +- include/linux/bpf_types.h | 1 + include/linux/bpf_verifier.h | 1 + include/linux/filter.h | 4 + include/uapi/linux/bpf.h | 14 + kernel/bpf/Makefile | 3 + kernel/bpf/arena.c | 558 ++++++++++++++++++ kernel/bpf/btf.c | 19 +- kernel/bpf/core.c | 16 + kernel/bpf/disasm.c | 10 + kernel/bpf/log.c | 3 + kernel/bpf/syscall.c | 42 ++ kernel/bpf/verifier.c | 123 +++- .../bpf/bpftool/Documentation/bpftool-map.rst | 2 +- tools/bpf/bpftool/gen.c | 13 + tools/bpf/bpftool/map.c | 2 +- tools/include/uapi/linux/bpf.h | 14 + tools/lib/bpf/bpf_helpers.h | 1 + tools/lib/bpf/libbpf.c | 163 ++++- tools/lib/bpf/libbpf.h | 2 +- tools/lib/bpf/libbpf_probes.c | 7 + tools/testing/selftests/bpf/DENYLIST.aarch64 | 2 + tools/testing/selftests/bpf/DENYLIST.s390x | 2 + tools/testing/selftests/bpf/bpf_arena_alloc.h | 67 +++ .../testing/selftests/bpf/bpf_arena_common.h | 70 +++ tools/testing/selftests/bpf/bpf_arena_htab.h | 100 ++++ tools/testing/selftests/bpf/bpf_arena_list.h | 92 +++ .../testing/selftests/bpf/bpf_experimental.h | 43 ++ .../selftests/bpf/prog_tests/arena_htab.c | 88 +++ .../selftests/bpf/prog_tests/arena_list.c | 68 +++ .../selftests/bpf/prog_tests/verifier.c | 2 + .../testing/selftests/bpf/progs/arena_htab.c | 48 ++ .../selftests/bpf/progs/arena_htab_asm.c | 5 + .../testing/selftests/bpf/progs/arena_list.c | 87 +++ .../selftests/bpf/progs/verifier_arena.c | 146 +++++ tools/testing/selftests/bpf/test_loader.c | 9 +- 37 files changed, 2028 insertions(+), 40 deletions(-) create mode 100644 kernel/bpf/arena.c create mode 100644 tools/testing/selftests/bpf/bpf_arena_alloc.h create mode 100644 tools/testing/selftests/bpf/bpf_arena_common.h create mode 100644 tools/testing/selftests/bpf/bpf_arena_htab.h create mode 100644 tools/testing/selftests/bpf/bpf_arena_list.h create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_htab.c create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_list.c create mode 100644 tools/testing/selftests/bpf/progs/arena_htab.c create mode 100644 tools/testing/selftests/bpf/progs/arena_htab_asm.c create mode 100644 tools/testing/selftests/bpf/progs/arena_list.c create mode 100644 tools/testing/selftests/bpf/progs/verifier_arena.c