From patchwork Fri Mar 8 01:08:12 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexei Starovoitov X-Patchwork-Id: 13586420 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 9E86CC54798 for ; Fri, 8 Mar 2024 01:09:09 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 318C86B030B; Thu, 7 Mar 2024 20:09:09 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 2C9A06B030D; Thu, 7 Mar 2024 20:09:09 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0F5346B030E; Thu, 7 Mar 2024 20:09:09 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id EE5046B030B for ; Thu, 7 Mar 2024 20:09:08 -0500 (EST) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id C4F4D120AF1 for ; Fri, 8 Mar 2024 01:09:08 +0000 (UTC) X-FDA: 81872087976.01.BC102F8 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) by imf21.hostedemail.com (Postfix) with ESMTP id EE4F21C000D for ; Fri, 8 Mar 2024 01:09:06 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=bx1gKsfr; spf=pass (imf21.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.214.178 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=1709860147; 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:in-reply-to:references:references:dkim-signature; bh=vpi4QqlrH6Gb27ghrZwkx18ctzPDyLw0H9dN/ovouKs=; b=G728iBMoZ0t+4y3+Iiw4SlqEG7DZoO/CXcgCoTH11r68ZV4Hnrc6ctl0skOVTzTp2HiF9m xoIjcHn4w6qg+d5WWTZGk1bIsHcuijUWte6QPmEHdp8rfekN2+kfaQOj5djyYM9cGpYsgn KWnvvsvMC4Kpbedg9FMOlOn2uucTudw= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=bx1gKsfr; spf=pass (imf21.hostedemail.com: domain of alexei.starovoitov@gmail.com designates 209.85.214.178 as permitted sender) smtp.mailfrom=alexei.starovoitov@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1709860147; a=rsa-sha256; cv=none; b=SqmoWfgI+wkIqh7QX2sO4LetKtUmCqerBIelZC3gGVGy9ESB6frsrdmItf7PpQgbsK4ga4 aYMxTJ3+D60xo33AJ60GLQryAueLizplIsp0Zdbr7A+eFH7NNXRp5ghoioQbj9aYrBHzdn Jp+6vnaBsyX4+Q1t/5ZgVobkump9Y5U= Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1dd6198c4e2so6912695ad.2 for ; Thu, 07 Mar 2024 17:09:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1709860146; x=1710464946; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vpi4QqlrH6Gb27ghrZwkx18ctzPDyLw0H9dN/ovouKs=; b=bx1gKsfr2ZJOGWHSAe8S3YNSafL7XDDAYYPFiVSLsQ8qn23DJ6JEJSSDgLXfIY/F0Z qlfCgCsTqCwtAT82PYOAyp7t8wh1c9pYmanVrvHkan11p/FXer2ddMP4UembsooGNe6z lkgINuKMmBQVoNXuspWAOvBO7gjrYHFNb/DkEJkY5mMDveVpVopSfIJAAfmdnOEMTOPf 2LN7NDB1nzx14ut3+51fLGIWlSPHKncmAK+AseLk2FCDxGVGoGoIzJ6yYRWtTdVu/qZh YaR4tMOrlriTigXTX8kR19MLeUosdguTOGlOo4NQkrXb/EO+pXsZuj78NYDqiF0ZR/nY Sj1Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709860146; x=1710464946; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vpi4QqlrH6Gb27ghrZwkx18ctzPDyLw0H9dN/ovouKs=; b=AF+HSN6LmuzLgTnWpwkW24FXVMxFELyTkHx6A8PESH3Co80SUb6ikGUhLllAKgzki9 Eic6AbLW2osJqII+1EiI+VRZWnVtuUhVGX+7e1q8uxheRFVu/N4mWJUfGniD+H9NcWmt +NU5jW+y79ME4IziJga0AaCVu0PTMc9GArsWl+rBQMlDF8+aJiebMbKmvL7g5cfgRPZj IwR7D5dCsDFd5tLuNZrXhV6+h4P+xtEDVPdFf6NJ+HWp6iIYzlp5ilBmVGJqcxULvdDN rioJFR4/dOE8CB0D0I3xF7PkYIBfdWBqIohtOmcbJXCk8Tk6YFcBnBR16GAhN7Jpqyp0 xs+A== X-Forwarded-Encrypted: i=1; AJvYcCX3/kaxIZ9Myk+xXhalD6ZBNVd4Q5+xZY1iyFtmgN+G7ayafQwzQTZ/OGrxuBIYbDqPeXr2Ocdc8YdZXxyVFucjHrY= X-Gm-Message-State: AOJu0YzymJcL0ml1n2SvUZMv+w83hYmOxcVaL8VCdgMHSWKknthed7sA Mu99oGNa66Z7e5wKyKMDDPRWw8u7I/X+QOpObeUjZNMdN9Fw6E9u X-Google-Smtp-Source: AGHT+IGdZhV5bxBeeUmmwgSlzXQMYoimx5PGXPGrr8Ve7jtmllA3H42p0lrX2YJCWZIhgzqDqaeLuw== X-Received: by 2002:a17:903:11c3:b0:1dc:d8de:5664 with SMTP id q3-20020a17090311c300b001dcd8de5664mr11335910plh.33.1709860145857; Thu, 07 Mar 2024 17:09:05 -0800 (PST) Received: from localhost.localdomain ([2620:10d:c090:400::5:428c]) by smtp.gmail.com with ESMTPSA id n14-20020a170902e54e00b001d9641003cfsm14286578plf.142.2024.03.07.17.09.04 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 07 Mar 2024 17:09:05 -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 14/14] selftests/bpf: Add bpf_arena_htab test. Date: Thu, 7 Mar 2024 17:08:12 -0800 Message-Id: <20240308010812.89848-15-alexei.starovoitov@gmail.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20240308010812.89848-1-alexei.starovoitov@gmail.com> References: <20240308010812.89848-1-alexei.starovoitov@gmail.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: EE4F21C000D X-Rspam-User: X-Stat-Signature: mg7hj8hmubx9d3o7cpdpthuqt5hx8mkg X-Rspamd-Server: rspam01 X-HE-Tag: 1709860146-481729 X-HE-Meta: U2FsdGVkX19Ly7JhiXddODAIpLU19PhSGBkJI8bja+6lv2h7GdapE4RCZr/2FWdElsoKlqgm+EvgaipbAyY+D9YsA32L/JPvRKk+ApmYqSBT/X8WmXPV6Isb/aZFff4BHdWF3/z+KYgWtd8OEHEWb9arRp0rDQPLjjT9bEWVfpwKhQrheQY/Mmp5lq+8XxSLB1eMoZIYUrTDhrlhyPv4Fn+uaPpiN6MkGm+h2K9vPDxKcPwnrcpPJOZxfd1l5w+3GNId3xA/zasVZ7AOq4UsFAdAaWi7VsT0l1D+wdLhM6w9PTUKWREFr238L63lkj23g+7gaBrIQaMhc/juyvbEFU8UB+emC8fZuTHP0X6MPgMi3Va2nJMElSIHsvpe0XHJSpsgO8OoRxa5lzmqjOxZul24BtJCkthTZpMLZqwGpat28Xx0ySF/k7MJV/qf9rdqXE1RzUgTnurrJzIYT8GNcnIl0JNm6FyBsC8vvPw/v6tW0K82UUErx+ACbNCJQ6wpkp8UFGI4TnARpuKXiVbpGaY/vXAZz5FwzSxjQQZ0GHkLnW/+QLcw41Cymkiw7qscIq9IywyRDTYkoHczkJz83km9eqixCcv2VsqDMKkEhJyWnnoz77/wvl2tp/L5UGuSvBXX1J1arYkLdaWlpRBI89asaCWmn+xjtqbhx0AMDtGY1Pkjo9Fa8jcK7gtq8giHU4lrpraZ9QMN/fv1IxiRa9Glu3SJ6/MQ7U2f65My3pW938YvJlc+IiLQrdG+6RxObqnA3xuEgQDNq9RY7rjsh4IFYF+nfJXR2gh1hudAng6bJ25NTqQFMei3AOrWUU66Aejn+SyueLqmBmXEbCiQe+AutvIVe+uRvLb2zhuy2Wc13D2HnjzhrqQjnaCgszml4EbYZvo+ucolb7oOIvR3LOue3rlP36htvGMt/GxRqnHhY5boMpx1rHXZID+L8/arnST1v+l2s51hqzSrIdV E3BH+aux xfrGuR+4grxWoA7PUDftsCYhAWzgwWfyWco15m6bUxsP7Nqf+BL3oZwJHNG58ZTlbJySwvsmkqgYGvDVX6KrW78l0edyB4iCAEsiehvW0Ci7u1KGYNynvs0jm4IsT93/w+OEerWAHwkIgD+Q8EPRmAih3tDQ6iW2/0HogoTyqxLSq3NmKrZVn0iqOauYuxrMdIRHwEe8kTSFddAZt0At98VEKvJEcmUp39bUU8huhfxLQgZqhV1alM+IsyUQsu6NJSu0K7fY4TD7lwL8x2LXUDOc0o7I3NO+ZD4mwewcbofAYCp2OwBIR2emHSg17iIvFqskcnzjYLuyCcghiCaTXpr0plE+xdUIUnYDuKBWNb+bzUcWnokpk3bo6k6m40t0znn7sAxoEMQsn0BGJZW3ZpcA39qPHu0cmcoRBjGL8+AyrDEDA+FzLnwcvGEXbmLwfl/U28DOcUxKaz5G1L6745mderca35YPGLWBMGK/xDVQewOJj/bFLWOsqeVit79pOpKSa1uEhDhhp5Io0m4Xcf+ngdUc8MBByxXE0J72AoeDITTBySueVVL1VQPbZwQY7PPnonNwootNNf9JeOznrJY1Qdpf9FcrE4pLV 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 bpf_arena_htab.h - hash table implemented as bpf program Signed-off-by: Alexei Starovoitov --- tools/testing/selftests/bpf/DENYLIST.aarch64 | 1 + tools/testing/selftests/bpf/DENYLIST.s390x | 1 + tools/testing/selftests/bpf/bpf_arena_htab.h | 100 ++++++++++++++++++ .../selftests/bpf/prog_tests/arena_htab.c | 88 +++++++++++++++ .../testing/selftests/bpf/progs/arena_htab.c | 48 +++++++++ .../selftests/bpf/progs/arena_htab_asm.c | 5 + 6 files changed, 243 insertions(+) create mode 100644 tools/testing/selftests/bpf/bpf_arena_htab.h create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_htab.c create mode 100644 tools/testing/selftests/bpf/progs/arena_htab.c create mode 100644 tools/testing/selftests/bpf/progs/arena_htab_asm.c diff --git a/tools/testing/selftests/bpf/DENYLIST.aarch64 b/tools/testing/selftests/bpf/DENYLIST.aarch64 index f9101651747b..d8ade15e2789 100644 --- a/tools/testing/selftests/bpf/DENYLIST.aarch64 +++ b/tools/testing/selftests/bpf/DENYLIST.aarch64 @@ -11,3 +11,4 @@ fill_link_info/kretprobe_multi_link_info # bpf_program__attach_kprobe_mu fill_link_info/kprobe_multi_invalid_ubuff # bpf_program__attach_kprobe_multi_opts unexpected error: -95 missed/kprobe_recursion # missed_kprobe_recursion__attach unexpected error: -95 (errno 95) verifier_arena # JIT does not support arena +arena_htab # JIT does not support arena diff --git a/tools/testing/selftests/bpf/DENYLIST.s390x b/tools/testing/selftests/bpf/DENYLIST.s390x index aa8a620f3318..f4a2f66a683d 100644 --- a/tools/testing/selftests/bpf/DENYLIST.s390x +++ b/tools/testing/selftests/bpf/DENYLIST.s390x @@ -5,3 +5,4 @@ get_stack_raw_tp # user_stack corrupted user stack stacktrace_build_id # compare_map_keys stackid_hmap vs. stackmap err -2 errno 2 (?) verifier_iterating_callbacks verifier_arena # JIT does not support arena +arena_htab # JIT does not support arena diff --git a/tools/testing/selftests/bpf/bpf_arena_htab.h b/tools/testing/selftests/bpf/bpf_arena_htab.h new file mode 100644 index 000000000000..acc01a876668 --- /dev/null +++ b/tools/testing/selftests/bpf/bpf_arena_htab.h @@ -0,0 +1,100 @@ +/* SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause) */ +/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */ +#pragma once +#include +#include "bpf_arena_alloc.h" +#include "bpf_arena_list.h" + +struct htab_bucket { + struct arena_list_head head; +}; +typedef struct htab_bucket __arena htab_bucket_t; + +struct htab { + htab_bucket_t *buckets; + int n_buckets; +}; +typedef struct htab __arena htab_t; + +static inline htab_bucket_t *__select_bucket(htab_t *htab, __u32 hash) +{ + htab_bucket_t *b = htab->buckets; + + cast_kern(b); + return &b[hash & (htab->n_buckets - 1)]; +} + +static inline arena_list_head_t *select_bucket(htab_t *htab, __u32 hash) +{ + return &__select_bucket(htab, hash)->head; +} + +struct hashtab_elem { + int hash; + int key; + int value; + struct arena_list_node hash_node; +}; +typedef struct hashtab_elem __arena hashtab_elem_t; + +static hashtab_elem_t *lookup_elem_raw(arena_list_head_t *head, __u32 hash, int key) +{ + hashtab_elem_t *l; + + list_for_each_entry(l, head, hash_node) + if (l->hash == hash && l->key == key) + return l; + + return NULL; +} + +static int htab_hash(int key) +{ + return key; +} + +__weak int htab_lookup_elem(htab_t *htab __arg_arena, int key) +{ + hashtab_elem_t *l_old; + arena_list_head_t *head; + + cast_kern(htab); + head = select_bucket(htab, key); + l_old = lookup_elem_raw(head, htab_hash(key), key); + if (l_old) + return l_old->value; + return 0; +} + +__weak int htab_update_elem(htab_t *htab __arg_arena, int key, int value) +{ + hashtab_elem_t *l_new = NULL, *l_old; + arena_list_head_t *head; + + cast_kern(htab); + head = select_bucket(htab, key); + l_old = lookup_elem_raw(head, htab_hash(key), key); + + l_new = bpf_alloc(sizeof(*l_new)); + if (!l_new) + return -ENOMEM; + l_new->key = key; + l_new->hash = htab_hash(key); + l_new->value = value; + + list_add_head(&l_new->hash_node, head); + if (l_old) { + list_del(&l_old->hash_node); + bpf_free(l_old); + } + return 0; +} + +void htab_init(htab_t *htab) +{ + void __arena *buckets = bpf_arena_alloc_pages(&arena, NULL, 2, NUMA_NO_NODE, 0); + + cast_user(buckets); + htab->buckets = buckets; + htab->n_buckets = 2 * PAGE_SIZE / sizeof(struct htab_bucket); +} diff --git a/tools/testing/selftests/bpf/prog_tests/arena_htab.c b/tools/testing/selftests/bpf/prog_tests/arena_htab.c new file mode 100644 index 000000000000..0766702de846 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/arena_htab.c @@ -0,0 +1,88 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */ +#include +#include +#include + +#include "arena_htab_asm.skel.h" +#include "arena_htab.skel.h" + +#define PAGE_SIZE 4096 + +#include "bpf_arena_htab.h" + +static void test_arena_htab_common(struct htab *htab) +{ + int i; + + printf("htab %p buckets %p n_buckets %d\n", htab, htab->buckets, htab->n_buckets); + ASSERT_OK_PTR(htab->buckets, "htab->buckets shouldn't be NULL"); + for (i = 0; htab->buckets && i < 16; i += 4) { + /* + * Walk htab buckets and link lists since all pointers are correct, + * though they were written by bpf program. + */ + int val = htab_lookup_elem(htab, i); + + ASSERT_EQ(i, val, "key == value"); + } +} + +static void test_arena_htab_llvm(void) +{ + LIBBPF_OPTS(bpf_test_run_opts, opts); + struct arena_htab *skel; + struct htab *htab; + size_t arena_sz; + void *area; + int ret; + + skel = arena_htab__open_and_load(); + if (!ASSERT_OK_PTR(skel, "arena_htab__open_and_load")) + return; + + area = bpf_map__initial_value(skel->maps.arena, &arena_sz); + /* fault-in a page with pgoff == 0 as sanity check */ + *(volatile int *)area = 0x55aa; + + /* bpf prog will allocate more pages */ + ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arena_htab_llvm), &opts); + ASSERT_OK(ret, "ret"); + ASSERT_OK(opts.retval, "retval"); + if (skel->bss->skip) { + printf("%s:SKIP:compiler doesn't support arena_cast\n", __func__); + test__skip(); + goto out; + } + htab = skel->bss->htab_for_user; + test_arena_htab_common(htab); +out: + arena_htab__destroy(skel); +} + +static void test_arena_htab_asm(void) +{ + LIBBPF_OPTS(bpf_test_run_opts, opts); + struct arena_htab_asm *skel; + struct htab *htab; + int ret; + + skel = arena_htab_asm__open_and_load(); + if (!ASSERT_OK_PTR(skel, "arena_htab_asm__open_and_load")) + return; + + ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arena_htab_asm), &opts); + ASSERT_OK(ret, "ret"); + ASSERT_OK(opts.retval, "retval"); + htab = skel->bss->htab_for_user; + test_arena_htab_common(htab); + arena_htab_asm__destroy(skel); +} + +void test_arena_htab(void) +{ + if (test__start_subtest("arena_htab_llvm")) + test_arena_htab_llvm(); + if (test__start_subtest("arena_htab_asm")) + test_arena_htab_asm(); +} diff --git a/tools/testing/selftests/bpf/progs/arena_htab.c b/tools/testing/selftests/bpf/progs/arena_htab.c new file mode 100644 index 000000000000..b7bb712cacfd --- /dev/null +++ b/tools/testing/selftests/bpf/progs/arena_htab.c @@ -0,0 +1,48 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */ +#include +#include +#include +#include +#include "bpf_experimental.h" + +struct { + __uint(type, BPF_MAP_TYPE_ARENA); + __uint(map_flags, BPF_F_MMAPABLE); + __uint(max_entries, 100); /* number of pages */ +} arena SEC(".maps"); + +#include "bpf_arena_htab.h" + +void __arena *htab_for_user; +bool skip = false; + +int zero = 0; + +SEC("syscall") +int arena_htab_llvm(void *ctx) +{ +#if defined(__BPF_FEATURE_ARENA_CAST) || defined(BPF_ARENA_FORCE_ASM) + struct htab __arena *htab; + __u64 i; + + htab = bpf_alloc(sizeof(*htab)); + cast_kern(htab); + htab_init(htab); + + /* first run. No old elems in the table */ + for (i = zero; i < 1000; i++) + htab_update_elem(htab, i, i); + + /* should replace all elems with new ones */ + for (i = zero; i < 1000; i++) + htab_update_elem(htab, i, i); + cast_user(htab); + htab_for_user = htab; +#else + skip = true; +#endif + return 0; +} + +char _license[] SEC("license") = "GPL"; diff --git a/tools/testing/selftests/bpf/progs/arena_htab_asm.c b/tools/testing/selftests/bpf/progs/arena_htab_asm.c new file mode 100644 index 000000000000..6cd70ea12f0d --- /dev/null +++ b/tools/testing/selftests/bpf/progs/arena_htab_asm.c @@ -0,0 +1,5 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */ +#define BPF_ARENA_FORCE_ASM +#define arena_htab_llvm arena_htab_asm +#include "arena_htab.c"