From patchwork Thu Sep 1 16:15:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexei Starovoitov X-Patchwork-Id: 12962883 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 EEE07ECAAD1 for ; Thu, 1 Sep 2022 16:15:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7B30D6B0092; Thu, 1 Sep 2022 12:15:53 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 73B0D940009; Thu, 1 Sep 2022 12:15:53 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 603EC940008; Thu, 1 Sep 2022 12:15:53 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 4A7296B0092 for ; Thu, 1 Sep 2022 12:15:53 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 1A16CA9753 for ; Thu, 1 Sep 2022 16:15:53 +0000 (UTC) X-FDA: 79864017786.19.39617A5 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) by imf17.hostedemail.com (Postfix) with ESMTP id AEA0E40044 for ; Thu, 1 Sep 2022 16:15:52 +0000 (UTC) Received: by mail-pj1-f46.google.com with SMTP id w88-20020a17090a6be100b001fbb0f0b013so3119542pjj.5 for ; Thu, 01 Sep 2022 09:15:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc; bh=I0zzBiCghT7bwa1INgy+ajatlkYqLStYBAGSsh2QGUg=; b=pUoVG+hDVirJbhVl6NE7ufWSXXiDEA72kNyZ5IjiAFZa8wZ7XpS5EkwLfeAowlUd8b KT7LUb75zs3r0YGHXcVBck8AaVk91rH8KU8b6ftiuVwf8GMIeIepQ7uvsyan+dk7UsGq APRdBlL42shs19hKUhwG051Y/H1RRrlJZ9xhAFXLQijDi73Zb7Xv4q1xW4tUedjdZJSG k6lbYXuwwukQMhsd8rSAWz5VuZBqUma3gTRMNeXjdb7S7FuEKwtoMyBj0by+XIZv8Tcn pxzks3QySovZqRxO32ggkcuvk+lO5XFKqosiUiXnKF72/mpNbViN6YU/GzzR428RK9WO yYqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc; bh=I0zzBiCghT7bwa1INgy+ajatlkYqLStYBAGSsh2QGUg=; b=ADdqGvAFeS0Gl87exoiOmUJ9aGEzwLmf5FU6g+T1CdT7ANEcBzNFTk5RtygLbHypVP a/UoFyrsz6VlYjO1BCW2jxyPbIvG6GfpmOZXo+e2shqWFSz9EqsAe2L6noPaUyuuYeUy l6YcElDWiFUxjlT1vgDwN5xldXLVFeVjV9akmxipV5IEARuqw15kQN9+QewUeGGeenPE u9Cgzpw0RJenruNsbAGPY5ZYU+TQmXVrUczZfqmzcyZCfp6LWoFlkSMgl4Qxc/EFmck2 uMwjdecU3MjzOULl8/x3YvB+lJdaFGxe+FVPz7r5v1Hks1B2c3bq6Lcvtw2/8QplVRAI ll+A== X-Gm-Message-State: ACgBeo3W6VPeoXGcrbfFVFJtLnBgJ4dWlZ3gMop7HiQmNvR4ttTs3ww4 CJvM5ZzVmziau/mie8CQsz0= X-Google-Smtp-Source: AA6agR4inzFCgYr4/1hRPNkUP0p2nwhLoBKPvzHfxZMWrL6wBECEwmjB5RTrHb60lzYa7IIz9Cr+cQ== X-Received: by 2002:a17:90b:4c52:b0:1f5:5129:af1a with SMTP id np18-20020a17090b4c5200b001f55129af1amr9241632pjb.202.1662048951512; Thu, 01 Sep 2022 09:15:51 -0700 (PDT) Received: from localhost.localdomain ([2620:10d:c090:500::3:4dc5]) by smtp.gmail.com with ESMTPSA id p7-20020a170902e74700b00172bf229dfdsm14186623plf.97.2022.09.01.09.15.49 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 01 Sep 2022 09:15:50 -0700 (PDT) From: Alexei Starovoitov To: davem@davemloft.net Cc: daniel@iogearbox.net, andrii@kernel.org, tj@kernel.org, memxor@gmail.com, delyank@fb.com, linux-mm@kvack.org, bpf@vger.kernel.org, kernel-team@fb.com Subject: [PATCH v5 bpf-next 00/15] bpf: BPF specific memory allocator. Date: Thu, 1 Sep 2022 09:15:32 -0700 Message-Id: <20220901161547.57722-1-alexei.starovoitov@gmail.com> X-Mailer: git-send-email 2.36.1 MIME-Version: 1.0 ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1662048952; a=rsa-sha256; cv=none; b=Dycwb2ql4lT4S5gS+SIudLFSs+hThq3G0Dpi0VChoURF2ktS77rqTNw8G9U2iaGodm0PAr KjBxhcnTBtdH5LckkVAdAdx6YM9pV89e6YcxW8AkZnziyRsh0/diSZ8t7fcN6+PFk9+PYl rh8GkWnuiFvmHayCJbXRXTgV9IXZMj0= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=pUoVG+hD; spf=pass (imf17.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.216.46 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1662048952; 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=I0zzBiCghT7bwa1INgy+ajatlkYqLStYBAGSsh2QGUg=; b=G7PIhzK4OxFAuCeO9s1kyAAdD3dKWULxUCJX8uNZ2Cm8CtsBXfnEHtcxqVb9OGP/C7rytQ WjIX7Dfak0UMnGRrXVzx1SBAubi5TEUQBfO4cSYsANaCLtEAs/f2Uj4qi1H9UILE3wAQQv xkaN2g8wSf6Uwbf+8lTxU9UnGrqsH0k= X-Rspamd-Queue-Id: AEA0E40044 Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=pUoVG+hD; spf=pass (imf17.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.216.46 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-Rspam-User: X-Rspamd-Server: rspam01 X-Stat-Signature: fdnc9i7cuk65cupm7nhix87enmuaubja X-HE-Tag: 1662048952-326749 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: From: Alexei Starovoitov Introduce any context BPF specific memory allocator. Tracing BPF programs can attach to kprobe and fentry. Hence they run in unknown context where calling plain kmalloc() might not be safe. Front-end kmalloc() with per-cpu cache of free elements. Refill this cache asynchronously from irq_work. Major achievements enabled by bpf_mem_alloc: - Dynamically allocated hash maps used to be 10 times slower than fully preallocated. With bpf_mem_alloc and subsequent optimizations the speed of dynamic maps is equal to full prealloc. - Tracing bpf programs can use dynamically allocated hash maps. Potentially saving lots of memory. Typical hash map is sparsely populated. - Sleepable bpf programs can used dynamically allocated hash maps. v4->v5: - Fixed missing migrate_disable in hash tab free path (Daniel) - Replaced impossible "memory leak" with WARN_ON_ONCE (Martin) - Dropped sysctl kernel.bpf_force_dyn_alloc patch (Daniel) - Added Andrii's ack - Added new patch 15 that removes kmem_cache usage from bpf_mem_alloc. It saves memory, speeds up map create/destroy operations while maintains hash map update/delete performance. v3->v4: - fix build issue due to missing local.h on 32-bit arch - add Kumar's ack - proposal for next steps from Delyan: https://lore.kernel.org/bpf/d3f76b27f4e55ec9e400ae8dcaecbb702a4932e8.camel@fb.com/ v2->v3: - Rewrote the free_list algorithm based on discussions with Kumar. Patch 1. - Allowed sleepable bpf progs use dynamically allocated maps. Patches 13 and 14. - Added sysctl to force bpf_mem_alloc in hash map even if pre-alloc is requested to reduce memory consumption. Patch 15. - Fix: zero-fill percpu allocation - Single rcu_barrier at the end instead of each cpu during bpf_mem_alloc destruction v2 thread: https://lore.kernel.org/bpf/20220817210419.95560-1-alexei.starovoitov@gmail.com/ v1->v2: - Moved unsafe direct call_rcu() from hash map into safe place inside bpf_mem_alloc. Patches 7 and 9. - Optimized atomic_inc/dec in hash map with percpu_counter. Patch 6. - Tuned watermarks per allocation size. Patch 8 - Adopted this approach to per-cpu allocation. Patch 10. - Fully converted hash map to bpf_mem_alloc. Patch 11. - Removed tracing prog restriction on map types. Combination of all patches and final patch 12. v1 thread: https://lore.kernel.org/bpf/20220623003230.37497-1-alexei.starovoitov@gmail.com/ LWN article: https://lwn.net/Articles/899274/ Future work: - expose bpf_mem_alloc as uapi FD to be used in dynptr_alloc, kptr_alloc - convert lru map to bpf_mem_alloc Alexei Starovoitov (15): bpf: Introduce any context BPF specific memory allocator. bpf: Convert hash map to bpf_mem_alloc. selftests/bpf: Improve test coverage of test_maps samples/bpf: Reduce syscall overhead in map_perf_test. bpf: Relax the requirement to use preallocated hash maps in tracing progs. bpf: Optimize element count in non-preallocated hash map. bpf: Optimize call_rcu in non-preallocated hash map. bpf: Adjust low/high watermarks in bpf_mem_cache bpf: Batch call_rcu callbacks instead of SLAB_TYPESAFE_BY_RCU. bpf: Add percpu allocation support to bpf_mem_alloc. bpf: Convert percpu hash map to per-cpu bpf_mem_alloc. bpf: Remove tracing program restriction on map types bpf: Prepare bpf_mem_alloc to be used by sleepable bpf programs. bpf: Remove prealloc-only restriction for sleepable bpf programs. bpf: Remove usage of kmem_cache from bpf_mem_cache. include/linux/bpf_mem_alloc.h | 26 + kernel/bpf/Makefile | 2 +- kernel/bpf/hashtab.c | 132 +++-- kernel/bpf/memalloc.c | 584 ++++++++++++++++++++++ kernel/bpf/syscall.c | 5 +- kernel/bpf/verifier.c | 52 -- samples/bpf/map_perf_test_kern.c | 44 +- samples/bpf/map_perf_test_user.c | 2 +- tools/testing/selftests/bpf/progs/timer.c | 11 - tools/testing/selftests/bpf/test_maps.c | 38 +- 10 files changed, 765 insertions(+), 131 deletions(-) create mode 100644 include/linux/bpf_mem_alloc.h create mode 100644 kernel/bpf/memalloc.c