From patchwork Fri Aug 19 21:42:17 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexei Starovoitov X-Patchwork-Id: 12949267 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 60EC4C32771 for ; Fri, 19 Aug 2022 21:42:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 947A16B0073; Fri, 19 Aug 2022 17:42:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8AC816B0074; Fri, 19 Aug 2022 17:42:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6FBE48D0001; Fri, 19 Aug 2022 17:42:37 -0400 (EDT) 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 5ADA46B0073 for ; Fri, 19 Aug 2022 17:42:37 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 2E1DB41A64 for ; Fri, 19 Aug 2022 21:42:37 +0000 (UTC) X-FDA: 79817666754.16.596C503 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) by imf28.hostedemail.com (Postfix) with ESMTP id D3F22C0035 for ; Fri, 19 Aug 2022 21:42:36 +0000 (UTC) Received: by mail-pj1-f46.google.com with SMTP id o14-20020a17090a0a0e00b001fabfd3369cso6006622pjo.5 for ; Fri, 19 Aug 2022 14:42:36 -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=7jTncCP3gpKHpe57rhmgpXAMVQKK9cKnka9R7CTzW2g=; b=QHPjB8vDaUiTYmuDa8xTiCrnplv95FKWpcW6k3WiVSmilGkLZMb3wEb58UfpBCf66E 0aWDxosl7WO0QGu7dsBU4dyoOX8OOo7BFMQlxEHHpNk6W4oTCj9K0gMRtXL5TT/Wpibf eITb8JGOQsV5q7hj/H3LSa3nDgQBNtQtUdiBRrDoRywR8uXouXybbd/jCgc18smBYeQr 13PnXK37i7EJgsiY857PSosrvSsuaiip4dAOhGTRlMAiAR3oB0+Ny+1KN5KPRSoSgphO r5gicpBhVigX+F/kKTUHLjIDiacSaFHOtE7/OOtGkktP/3MuBuD38JokyfzeBdrRNhb4 uSaA== 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=7jTncCP3gpKHpe57rhmgpXAMVQKK9cKnka9R7CTzW2g=; b=YqLH9V0mFmJUoM4lLmUm/CdY9E5f+PCL643+FT4plqFBPKoHxp9HkGc3RHIaSquhPD 2PCpW3QQng7cNGLsSCag6WnIatcJyu7XbE/O3UGH6LEVTY0nZmZGmaAZbazm5DW7lX+h ZWTsCN8KwPBsJP8vYUS4Lyd+JAmNtdUpXuY7DjYDXkNgVk6u8p1jOWjC6Rgv99QmVrM3 LdvqrJbnyAOIiOkzgY8fcgh+9dlAxN4b2X+9n13b5R7wpzk/lP3eKF/f4+LOU/y+ih9+ bLPV+i1O6l/Ic4/KH60Y/XXERDJPKWqlUf1gcBCc6X28Go5gmTMVhTMZZVwJPjRYH5CA smqA== X-Gm-Message-State: ACgBeo1UdsxJmNzvMwNpaCLpe4XJ/RGvSHnN7F1E4FEJlt/RZZVW6KKT k+rjh1Xp7XRtS/oVMdRl0aI= X-Google-Smtp-Source: AA6agR6UdhvPRirGbZJ6jl4RZSLcjjAZ3qP2kz39Lpe5AKQUtOVK57dDRLoRK7mvMZP0V+Jq9T+LpA== X-Received: by 2002:a17:903:4ce:b0:171:2cbb:ba27 with SMTP id jm14-20020a17090304ce00b001712cbbba27mr9308071plb.72.1660945355566; Fri, 19 Aug 2022 14:42:35 -0700 (PDT) Received: from localhost.localdomain ([2620:10d:c090:500::1:c4b1]) by smtp.gmail.com with ESMTPSA id g29-20020aa796bd000000b00535e46171c1sm3227303pfk.117.2022.08.19.14.42.34 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 19 Aug 2022 14:42:35 -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 v3 bpf-next 00/15] bpf: BPF specific memory allocator. Date: Fri, 19 Aug 2022 14:42:17 -0700 Message-Id: <20220819214232.18784-1-alexei.starovoitov@gmail.com> X-Mailer: git-send-email 2.36.1 MIME-Version: 1.0 ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1660945356; 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=7jTncCP3gpKHpe57rhmgpXAMVQKK9cKnka9R7CTzW2g=; b=CvxM9CUlUIUtOyBg9kXX3ciKiG17acxcDNCDaAUzuxMdeKDYR7ICrhyUTiEVcowkZJIVd0 PPgZ0Ogqck+vjdc8g9dvaDFjpstdoZ/BxiuJLWTEUPDXSFcNhDLuD+A440enh3T/hzS9XH rMIx3XRxJnbxl4fgoAxd7dEBnBfqwp0= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=QHPjB8vD; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf28.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.216.46 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1660945356; a=rsa-sha256; cv=none; b=Hnw94soiG8WG5JDWzDO4CphDHLfKCN45cmn/OYfYavy9Vn9EUjARazxClrfpA2UiAzRAeh pqWP/A2evQ9zCvWjAVrQRf5FyOFh/Twd5HN/lILQOSOpkBLlrrQqHUKcGuj2q6YH7WUkbu R0uJbY4+htJ1mex0vWPe+bufBc28SAM= Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=QHPjB8vD; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf28.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.216.46 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: D3F22C0035 X-Stat-Signature: pzqgmn3y9w4yk91que78p5na53bqth9i X-Rspam-User: X-HE-Tag: 1660945356-3158 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. 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: Introduce sysctl kernel.bpf_force_dyn_alloc. include/linux/bpf_mem_alloc.h | 26 + include/linux/filter.h | 2 + kernel/bpf/Makefile | 2 +- kernel/bpf/core.c | 2 + kernel/bpf/hashtab.c | 132 +++-- kernel/bpf/memalloc.c | 601 ++++++++++++++++++++++ kernel/bpf/syscall.c | 14 +- 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 +- 12 files changed, 795 insertions(+), 131 deletions(-) create mode 100644 include/linux/bpf_mem_alloc.h create mode 100644 kernel/bpf/memalloc.c Acked-by: Kumar Kartikeya Dwivedi