From patchwork Wed Sep 22 20:32:21 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 12511355 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.0 required=3.0 tests=BAYES_00,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D6A06C433EF for ; Wed, 22 Sep 2021 20:32:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B1DA560FC1 for ; Wed, 22 Sep 2021 20:32:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237487AbhIVUeE convert rfc822-to-8bit (ORCPT ); Wed, 22 Sep 2021 16:34:04 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:58480 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237309AbhIVUeD (ORCPT ); Wed, 22 Sep 2021 16:34:03 -0400 Received: from pps.filterd (m0109331.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18MIlSj2000986 for ; Wed, 22 Sep 2021 13:32:33 -0700 Received: from maileast.thefacebook.com ([163.114.130.16]) by mx0a-00082601.pphosted.com with ESMTP id 3b7q54fx69-4 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 22 Sep 2021 13:32:32 -0700 Received: from intmgw001.25.frc3.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:83::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 22 Sep 2021 13:32:31 -0700 Received: by devbig019.vll3.facebook.com (Postfix, from userid 137359) id AF72E4B04EBA; Wed, 22 Sep 2021 13:32:29 -0700 (PDT) From: Andrii Nakryiko To: , , CC: , , Andrii Nakryiko Subject: [PATCH RFC bpf-next 1/4] bpf: add bpf_jhash_mem BPF helper Date: Wed, 22 Sep 2021 13:32:21 -0700 Message-ID: <20210922203224.912809-2-andrii@kernel.org> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210922203224.912809-1-andrii@kernel.org> References: <20210922203224.912809-1-andrii@kernel.org> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-ORIG-GUID: lJNo1WsJZ0JEjsMC1cwgmHaj00D1dhNh X-Proofpoint-GUID: lJNo1WsJZ0JEjsMC1cwgmHaj00D1dhNh X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-22_08,2021-09-22_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 spamscore=0 mlxlogscore=999 priorityscore=1501 adultscore=0 clxscore=1015 phishscore=0 malwarescore=0 bulkscore=0 suspectscore=0 impostorscore=0 mlxscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109200000 definitions=main-2109220133 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC Add BPF helper that allows to calculate jhash of arbitrary (initialized) memory slice. Signed-off-by: Andrii Nakryiko --- include/uapi/linux/bpf.h | 8 ++++++++ kernel/bpf/helpers.c | 23 +++++++++++++++++++++++ tools/include/uapi/linux/bpf.h | 8 ++++++++ 3 files changed, 39 insertions(+) diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index 2e3048488feb..7b17e46b0be2 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -4913,6 +4913,13 @@ union bpf_attr { * Return * The number of bytes written to the buffer, or a negative error * in case of failure. + * + * u64 bpf_jhash_mem(const void *data, u32 sz, u32 seed) + * Description + * Calculate jhash of a given memory slice. + * + * Return + * Calculated hash value. */ #define __BPF_FUNC_MAPPER(FN) \ FN(unspec), \ @@ -5093,6 +5100,7 @@ union bpf_attr { FN(task_pt_regs), \ FN(get_branch_snapshot), \ FN(trace_vprintk), \ + FN(jhash_mem), \ /* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index 2c604ff8c7fb..00fb1b69595c 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -15,9 +15,30 @@ #include #include #include +#include #include "../../lib/kstrtox.h" +BPF_CALL_3(bpf_jhash_mem, const void *, data, u32, sz, u32, seed) +{ + if (unlikely((uintptr_t)data % 4 || sz % 4)) + return jhash(data, sz, seed); + + /* optimized 4-byte version */ + return jhash2(data, sz / 4, seed); +} + + +static const struct bpf_func_proto bpf_jhash_mem_proto = { + .func = bpf_jhash_mem, + .gpl_only = false, + .ret_type = RET_INTEGER, + .arg1_type = ARG_PTR_TO_MEM, + .arg2_type = ARG_CONST_SIZE_OR_ZERO, + .arg3_type = ARG_ANYTHING, +}; + + /* If kernel subsystem is allowing eBPF programs to call this function, * inside its own verifier_ops->get_func_proto() callback it should return * bpf_map_lookup_elem_proto, so that verifier can properly check the arguments @@ -1341,6 +1362,8 @@ const struct bpf_func_proto * bpf_base_func_proto(enum bpf_func_id func_id) { switch (func_id) { + case BPF_FUNC_jhash_mem: + return &bpf_jhash_mem_proto; case BPF_FUNC_map_lookup_elem: return &bpf_map_lookup_elem_proto; case BPF_FUNC_map_update_elem: diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index 2e3048488feb..7b17e46b0be2 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -4913,6 +4913,13 @@ union bpf_attr { * Return * The number of bytes written to the buffer, or a negative error * in case of failure. + * + * u64 bpf_jhash_mem(const void *data, u32 sz, u32 seed) + * Description + * Calculate jhash of a given memory slice. + * + * Return + * Calculated hash value. */ #define __BPF_FUNC_MAPPER(FN) \ FN(unspec), \ @@ -5093,6 +5100,7 @@ union bpf_attr { FN(task_pt_regs), \ FN(get_branch_snapshot), \ FN(trace_vprintk), \ + FN(jhash_mem), \ /* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper From patchwork Wed Sep 22 20:32:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 12511357 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.0 required=3.0 tests=BAYES_00,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id DFD05C433EF for ; Wed, 22 Sep 2021 20:32:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BB246611C9 for ; Wed, 22 Sep 2021 20:32:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237599AbhIVUeG convert rfc822-to-8bit (ORCPT ); Wed, 22 Sep 2021 16:34:06 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:12944 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S237309AbhIVUeF (ORCPT ); Wed, 22 Sep 2021 16:34:05 -0400 Received: from pps.filterd (m0001303.ppops.net [127.0.0.1]) by m0001303.ppops.net (8.16.1.2/8.16.1.2) with SMTP id 18MIlIEl025899 for ; Wed, 22 Sep 2021 13:32:35 -0700 Received: from mail.thefacebook.com ([163.114.132.120]) by m0001303.ppops.net with ESMTP id 3b7q4nyxmx-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 22 Sep 2021 13:32:35 -0700 Received: from intmgw001.38.frc1.facebook.com (2620:10d:c085:108::4) by mail.thefacebook.com (2620:10d:c085:21d::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 22 Sep 2021 13:32:32 -0700 Received: by devbig019.vll3.facebook.com (Postfix, from userid 137359) id BBD314B04EBE; Wed, 22 Sep 2021 13:32:31 -0700 (PDT) From: Andrii Nakryiko To: , , CC: , , Andrii Nakryiko Subject: [PATCH RFC bpf-next 2/4] selftests/bpf: fix and optimize bloom filter bench Date: Wed, 22 Sep 2021 13:32:22 -0700 Message-ID: <20210922203224.912809-3-andrii@kernel.org> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210922203224.912809-1-andrii@kernel.org> References: <20210922203224.912809-1-andrii@kernel.org> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: MX5_nYSIGaUVH_DznNsptsVR9jaXwPmP X-Proofpoint-ORIG-GUID: MX5_nYSIGaUVH_DznNsptsVR9jaXwPmP X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-22_08,2021-09-22_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 adultscore=0 priorityscore=1501 suspectscore=0 malwarescore=0 phishscore=0 impostorscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 clxscore=1015 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109200000 definitions=main-2109220133 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC Fix inconsistent and highly-variable measurement logic by using always increasing counters. Also reduce the amount of accounting by doing increment once after the entire loop. Also use rodata for bloom filter flag. And build bench files in optimized mode. Signed-off-by: Andrii Nakryiko --- tools/testing/selftests/bpf/Makefile | 2 +- .../bpf/benchs/bench_bloom_filter_map.c | 32 +++++++++++++- .../selftests/bpf/progs/bloom_filter_map.c | 44 ++++++++++++++----- 3 files changed, 63 insertions(+), 15 deletions(-) diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index 5dbaf7f512fd..f36f49e4d0f2 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -515,7 +515,7 @@ $(OUTPUT)/test_cpp: test_cpp.cpp $(OUTPUT)/test_core_extern.skel.h $(BPFOBJ) # Benchmark runner $(OUTPUT)/bench_%.o: benchs/bench_%.c bench.h $(BPFOBJ) $(call msg,CC,,$@) - $(Q)$(CC) $(CFLAGS) -c $(filter %.c,$^) $(LDLIBS) -o $@ + $(Q)$(CC) $(CFLAGS) -O2 -c $(filter %.c,$^) $(LDLIBS) -o $@ $(OUTPUT)/bench_rename.o: $(OUTPUT)/test_overhead.skel.h $(OUTPUT)/bench_trigger.o: $(OUTPUT)/trigger_bench.skel.h $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ diff --git a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c index 7adf80be7292..4f53cd9fb099 100644 --- a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +++ b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c @@ -248,7 +248,7 @@ static void hashmap_no_bloom_filter_setup(void) ctx.skel = setup_skeleton(); - ctx.skel->data->hashmap_use_bloom_filter = false; + ctx.skel->rodata->hashmap_use_bloom_filter = false; populate_maps(); @@ -259,16 +259,26 @@ static void hashmap_no_bloom_filter_setup(void) } } +struct stat { __u32 stats[3]; }; + static void measure(struct bench_res *res) { + static long last_hits, last_drops, last_false_hits; long total_hits = 0, total_drops = 0, total_false_hits = 0; unsigned int nr_cpus = bpf_num_possible_cpus(); + /* BPF_DECLARE_PERCPU(__u64, zeroed_values); BPF_DECLARE_PERCPU(__u64, false_hits); BPF_DECLARE_PERCPU(__u64, drops); BPF_DECLARE_PERCPU(__u64, hits); int err, i, percpu_array_fd; __u32 key; + */ + int i; + int hit_key, drop_key, false_hit_key; + hit_key = ctx.skel->rodata->hit_key; + drop_key = ctx.skel->rodata->drop_key; + false_hit_key = ctx.skel->rodata->false_hit_key; if (ctx.skel->bss->error != 0) { fprintf(stderr, "error (%d) when searching the bloom filter\n", @@ -276,6 +286,7 @@ static void measure(struct bench_res *res) exit(1); } + /* key = ctx.skel->rodata->hit_key; percpu_array_fd = bpf_map__fd(ctx.skel->maps.percpu_array); err = bpf_map_lookup_elem(percpu_array_fd, &key, hits); @@ -300,20 +311,36 @@ static void measure(struct bench_res *res) -errno); exit(1); } + */ for (i = 0; i < nr_cpus; i++) { + struct stat *s = (void *)&ctx.skel->bss->percpu_stats[i]; + + total_hits += s->stats[hit_key]; + total_drops += s->stats[drop_key]; + total_false_hits += s->stats[false_hit_key]; + /* total_hits += bpf_percpu(hits, i); total_drops += bpf_percpu(drops, i); total_false_hits += bpf_percpu(false_hits, i); + */ } + res->hits = total_hits - last_hits; + res->drops = total_drops - last_drops; + res->false_hits = total_false_hits - last_false_hits; + + last_hits = total_hits; + last_drops = total_drops; + last_false_hits = total_false_hits; + + /* res->hits = total_hits; res->drops = total_drops; res->false_hits = total_false_hits; memset(zeroed_values, 0, sizeof(zeroed_values)); - /* zero out the percpu array */ key = ctx.skel->rodata->hit_key; err = bpf_map_update_elem(percpu_array_fd, &key, zeroed_values, BPF_ANY); if (err) { @@ -332,6 +359,7 @@ static void measure(struct bench_res *res) fprintf(stderr, "zeroing the percpu array failed: %d\n", -errno); exit(1); } + */ } static void *consumer(void *input) diff --git a/tools/testing/selftests/bpf/progs/bloom_filter_map.c b/tools/testing/selftests/bpf/progs/bloom_filter_map.c index 05f9706a5ba6..3ae2f9bb5968 100644 --- a/tools/testing/selftests/bpf/progs/bloom_filter_map.c +++ b/tools/testing/selftests/bpf/progs/bloom_filter_map.c @@ -23,6 +23,7 @@ struct map_bloom_filter_type { __uint(value_size, sizeof(__u64)); __uint(max_entries, 1000); __uint(nr_hash_funcs, 3); +// __uint(map_flags, BPF_F_ZERO_SEED); } map_bloom_filter SEC(".maps"); struct { @@ -37,13 +38,19 @@ struct callback_ctx { struct map_bloom_filter_type *map; }; +struct { + __u32 stats[3]; +} __attribute__((aligned(256))) percpu_stats[256]; + /* Tracks the number of hits, drops, and false hits */ +/* struct { __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY); __uint(max_entries, 3); __type(key, __u32); __type(value, __u64); } percpu_array SEC(".maps"); +*/ struct { __uint(type, BPF_MAP_TYPE_HASH); @@ -56,17 +63,23 @@ const __u32 hit_key = 0; const __u32 drop_key = 1; const __u32 false_hit_key = 2; -bool hashmap_use_bloom_filter = true; +const volatile bool hashmap_use_bloom_filter = true; int error = 0; -static __always_inline void log_result(__u32 key) +static __always_inline void log_result(__u32 key, __u32 val) { + __u32 cpu = bpf_get_smp_processor_id(); + + percpu_stats[cpu & 255].stats[key] += val; + + /* __u64 *count; count = bpf_map_lookup_elem(&percpu_array, &key); if (count) - *count += 1; + *count += val; + */ } static __u64 @@ -81,7 +94,7 @@ check_elem(struct bpf_map *map, __u32 *key, __u64 *val, return 1; /* stop the iteration */ } - log_result(hit_key); + log_result(hit_key, 1); return 0; } @@ -121,37 +134,44 @@ int prog_bloom_filter_hashmap_lookup(void *ctx) { __u64 *result; int i, err; - union { __u64 data64; __u32 data32[2]; } val; + int hits = 0, drops = 0, false_hits = 0; + //bool custom_hit = false, noncustom_hit = false; for (i = 0; i < 512; i++) { - val.data32[0] = bpf_get_prandom_u32(); - val.data32[1] = bpf_get_prandom_u32(); + val.data32[0] = /*i; */ bpf_get_prandom_u32(); + val.data32[1] = /*i + 1;*/ bpf_get_prandom_u32(); - if (hashmap_use_bloom_filter) { + if (hashmap_use_bloom_filter) + { err = bpf_map_peek_elem(&map_bloom_filter, &val); if (err) { if (err != -ENOENT) { error |= 3; return 0; } - log_result(drop_key); + hits++; + //noncustom_hit = true; + //__sync_fetch_and_add(&bloom_noncustom_hit, 1); continue; } } result = bpf_map_lookup_elem(&hashmap, &val); if (result) { - log_result(hit_key); + hits++; } else { if (hashmap_use_bloom_filter) - log_result(false_hit_key); - log_result(drop_key); + false_hits++; + drops++; } } + log_result(hit_key, hits); + log_result(drop_key, drops); + log_result(false_hit_key, false_hits); return 0; } From patchwork Wed Sep 22 20:32:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 12511359 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.0 required=3.0 tests=BAYES_00,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id EC3D7C433FE for ; Wed, 22 Sep 2021 20:32:38 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id CF9B9611C9 for ; Wed, 22 Sep 2021 20:32:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237640AbhIVUeI convert rfc822-to-8bit (ORCPT ); Wed, 22 Sep 2021 16:34:08 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:29832 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237309AbhIVUeH (ORCPT ); Wed, 22 Sep 2021 16:34:07 -0400 Received: from pps.filterd (m0109332.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18MIlSm5003616 for ; Wed, 22 Sep 2021 13:32:37 -0700 Received: from maileast.thefacebook.com ([163.114.130.16]) by mx0a-00082601.pphosted.com with ESMTP id 3b7q5br02y-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 22 Sep 2021 13:32:36 -0700 Received: from intmgw003.48.prn1.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:82::c) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 22 Sep 2021 13:32:35 -0700 Received: by devbig019.vll3.facebook.com (Postfix, from userid 137359) id C617A4B04ECA; Wed, 22 Sep 2021 13:32:33 -0700 (PDT) From: Andrii Nakryiko To: , , CC: , , Andrii Nakryiko Subject: [PATCH RFC bpf-next 3/4] selftests/bpf: implement custom Bloom filter purely in BPF Date: Wed, 22 Sep 2021 13:32:23 -0700 Message-ID: <20210922203224.912809-4-andrii@kernel.org> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210922203224.912809-1-andrii@kernel.org> References: <20210922203224.912809-1-andrii@kernel.org> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-ORIG-GUID: kqBTFsT_bb6c4lPOpzDZPyVVO6vMy0JF X-Proofpoint-GUID: kqBTFsT_bb6c4lPOpzDZPyVVO6vMy0JF X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-22_08,2021-09-22_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 mlxlogscore=905 lowpriorityscore=0 adultscore=0 phishscore=0 bulkscore=0 suspectscore=0 mlxscore=0 clxscore=1015 impostorscore=0 malwarescore=0 priorityscore=1501 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109200000 definitions=main-2109220133 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC And integrate it into existing benchmarks (on BPF side). Posting this separately from user-space benchmark to emphasize how little code is necessary on BPF side to make this work. Signed-off-by: Andrii Nakryiko --- .../selftests/bpf/progs/bloom_filter_map.c | 81 ++++++++++++++++++- 1 file changed, 80 insertions(+), 1 deletion(-) diff --git a/tools/testing/selftests/bpf/progs/bloom_filter_map.c b/tools/testing/selftests/bpf/progs/bloom_filter_map.c index 3ae2f9bb5968..ee7bbde1af45 100644 --- a/tools/testing/selftests/bpf/progs/bloom_filter_map.c +++ b/tools/testing/selftests/bpf/progs/bloom_filter_map.c @@ -64,9 +64,43 @@ const __u32 drop_key = 1; const __u32 false_hit_key = 2; const volatile bool hashmap_use_bloom_filter = true; +const volatile bool hashmap_use_custom_bloom_filter = false; + + +__u64 bloom_val = 0; +static __u64 bloom_arr[256 * 1024]; /* enough for 1mln max_elems w/ 10 hash funcs */ +const volatile __u32 bloom_mask; +const volatile __u32 bloom_hash_cnt; +const volatile __u32 bloom_seed; int error = 0; +static void bloom_add(const void *data, __u32 sz) +{ + __u32 i = 0, h; + + for (i = 0; i < bloom_hash_cnt; i++) { + h = bpf_jhash_mem(data, sz, bloom_seed + i); + __sync_fetch_and_or(&bloom_arr[(h / 64) & bloom_mask], 1ULL << (h % 64)); + } +} + +bool bloom_contains(__u64 val) +{ + __u32 i = 0, h; + __u32 seed = bloom_seed, msk = bloom_mask; + __u64 v, *arr = bloom_arr; + + for (i = bloom_hash_cnt; i > 0; i--) { + h = bpf_jhash_mem(&val, sizeof(val), seed); + v = arr[(h / 64) & msk]; + if (!((v >> (h % 64)) & 1)) + return false; + seed++; + } + return true; +} + static __always_inline void log_result(__u32 key, __u32 val) { __u32 cpu = bpf_get_smp_processor_id(); @@ -99,6 +133,20 @@ check_elem(struct bpf_map *map, __u32 *key, __u64 *val, return 0; } +static __u64 +check_elem_custom(struct bpf_map *map, __u32 *key, __u64 *val, + struct callback_ctx *data) +{ + if (!bloom_contains(*val)) { + error |= 1; + return 1; /* stop the iteration */ + } + + log_result(hit_key, 1); + + return 0; +} + SEC("fentry/__x64_sys_getpgid") int prog_bloom_filter(void *ctx) { @@ -110,6 +158,26 @@ int prog_bloom_filter(void *ctx) return 0; } +SEC("fentry/__x64_sys_getpgid") +int prog_custom_bloom_filter(void *ctx) +{ + bpf_for_each_map_elem(&map_random_data, check_elem_custom, NULL, 0); + + return 0; +} + +__u32 bloom_err = 0; +__u32 bloom_custom_hit = 0; +__u32 bloom_noncustom_hit = 0; + +SEC("fentry/__x64_sys_getpgid") +int prog_custom_bloom_filter_add(void *ctx) +{ + bloom_add(&bloom_val, sizeof(bloom_val)); + + return 0; +} + SEC("fentry/__x64_sys_getpgid") int prog_bloom_filter_inner_map(void *ctx) { @@ -145,6 +213,15 @@ int prog_bloom_filter_hashmap_lookup(void *ctx) val.data32[0] = /*i; */ bpf_get_prandom_u32(); val.data32[1] = /*i + 1;*/ bpf_get_prandom_u32(); + if (hashmap_use_custom_bloom_filter) + { + if (!bloom_contains(val.data64)) { + hits++; + //custom_hit = true; + //__sync_fetch_and_add(&bloom_custom_hit, 1); + continue; + } + } if (hashmap_use_bloom_filter) { err = bpf_map_peek_elem(&map_bloom_filter, &val); @@ -160,11 +237,13 @@ int prog_bloom_filter_hashmap_lookup(void *ctx) } } + //bloom_err += (custom_hit != noncustom_hit); + result = bpf_map_lookup_elem(&hashmap, &val); if (result) { hits++; } else { - if (hashmap_use_bloom_filter) + if (hashmap_use_custom_bloom_filter || hashmap_use_bloom_filter) false_hits++; drops++; } From patchwork Wed Sep 22 20:32:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrii Nakryiko X-Patchwork-Id: 12511363 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-17.0 required=3.0 tests=BAYES_00,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id D477CC433F5 for ; Wed, 22 Sep 2021 20:32:42 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BF0AC61019 for ; Wed, 22 Sep 2021 20:32:42 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237626AbhIVUeM convert rfc822-to-8bit (ORCPT ); Wed, 22 Sep 2021 16:34:12 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:38890 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237309AbhIVUeM (ORCPT ); Wed, 22 Sep 2021 16:34:12 -0400 Received: from pps.filterd (m0109333.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18MIlMSh022555 for ; Wed, 22 Sep 2021 13:32:41 -0700 Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3b86h0tj2d-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 22 Sep 2021 13:32:41 -0700 Received: from intmgw002.25.frc3.facebook.com (2620:10d:c085:208::f) by mail.thefacebook.com (2620:10d:c085:11d::5) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 22 Sep 2021 13:32:40 -0700 Received: by devbig019.vll3.facebook.com (Postfix, from userid 137359) id D691A4B04ECE; Wed, 22 Sep 2021 13:32:35 -0700 (PDT) From: Andrii Nakryiko To: , , CC: , , Andrii Nakryiko Subject: [PATCH RFC bpf-next 4/4] selftests/bpf: integrate custom Bloom filter impl into benchs Date: Wed, 22 Sep 2021 13:32:24 -0700 Message-ID: <20210922203224.912809-5-andrii@kernel.org> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210922203224.912809-1-andrii@kernel.org> References: <20210922203224.912809-1-andrii@kernel.org> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: 00hB6rqB0fh8-Bg6Vb5JCJuWIKML8LPU X-Proofpoint-ORIG-GUID: 00hB6rqB0fh8-Bg6Vb5JCJuWIKML8LPU X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.790,Hydra:6.0.391,FMLib:17.0.607.475 definitions=2021-09-22_08,2021-09-22_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 clxscore=1015 mlxscore=0 spamscore=0 lowpriorityscore=0 phishscore=0 priorityscore=1501 mlxlogscore=999 adultscore=0 bulkscore=0 impostorscore=0 suspectscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109200000 definitions=main-2109220133 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC Add user-space integration parts. Signed-off-by: Andrii Nakryiko --- tools/testing/selftests/bpf/bench.c | 6 + .../bpf/benchs/bench_bloom_filter_map.c | 121 +++++++++++++++++- .../bpf/benchs/run_bench_bloom_filter_map.sh | 22 ++-- .../selftests/bpf/benchs/run_common.sh | 2 +- 4 files changed, 135 insertions(+), 16 deletions(-) diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index 7da1589a9fe0..ab03b259b76f 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -363,9 +363,12 @@ extern const struct bench bench_rb_custom; extern const struct bench bench_pb_libbpf; extern const struct bench bench_pb_custom; extern const struct bench bench_bloom_filter_map; +extern const struct bench bench_custom_bloom_filter_map; extern const struct bench bench_bloom_filter_false_positive; +extern const struct bench bench_custom_bloom_filter_false_positive; extern const struct bench bench_hashmap_without_bloom_filter; extern const struct bench bench_hashmap_with_bloom_filter; +extern const struct bench bench_hashmap_with_custom_bloom_filter; static const struct bench *benchs[] = { &bench_count_global, @@ -388,9 +391,12 @@ static const struct bench *benchs[] = { &bench_pb_libbpf, &bench_pb_custom, &bench_bloom_filter_map, + &bench_custom_bloom_filter_map, &bench_bloom_filter_false_positive, + &bench_custom_bloom_filter_false_positive, &bench_hashmap_without_bloom_filter, &bench_hashmap_with_bloom_filter, + &bench_hashmap_with_custom_bloom_filter, }; static void setup_benchmark() diff --git a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c index 4f53cd9fb099..c0ccfbaacef7 100644 --- a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +++ b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c @@ -95,11 +95,18 @@ static void *map_prepare_thread(void *arg) { int err, random_data_fd, bloom_filter_fd, hashmap_fd; __u64 i, val; + struct bpf_link *link; bloom_filter_fd = bpf_map__fd(ctx.skel->maps.map_bloom_filter); random_data_fd = bpf_map__fd(ctx.skel->maps.map_random_data); hashmap_fd = bpf_map__fd(ctx.skel->maps.hashmap); + link = bpf_program__attach(ctx.skel->progs.prog_custom_bloom_filter_add); + if (libbpf_get_error(link)) { + fprintf(stderr, "failed to attach program!\n"); + exit(1); + } + while (true) { i = __atomic_add_fetch(&ctx.next_map_idx, 1, __ATOMIC_RELAXED); if (i > args.nr_entries) @@ -135,8 +142,13 @@ static void *map_prepare_thread(void *arg) fprintf(stderr, "failed to add elem to bloom_filter: %d\n", -errno); break; } + + ctx.skel->bss->bloom_val = val; + trigger_bpf_program(); } + bpf_link__destroy(link); + pthread_mutex_lock(&ctx.map_done_mtx); pthread_cond_signal(&ctx.map_done); pthread_mutex_unlock(&ctx.map_done_mtx); @@ -146,7 +158,7 @@ static void *map_prepare_thread(void *arg) static void populate_maps(void) { - unsigned int nr_cpus = bpf_num_possible_cpus(); + unsigned int nr_cpus = 1; // bpf_num_possible_cpus(); pthread_t map_thread; int i, err; @@ -167,10 +179,10 @@ static void populate_maps(void) exit(1); } -static struct bloom_filter_map *setup_skeleton(void) +static struct bloom_filter_map *setup_skeleton() { struct bloom_filter_map *skel; - int err; + int err, i, bloom_sz; setup_libbpf(); @@ -204,10 +216,17 @@ static struct bloom_filter_map *setup_skeleton(void) exit(1); } - if (bloom_filter_map__load(skel)) { - fprintf(stderr, "failed to load skeleton\n"); - exit(1); + skel->rodata->bloom_hash_cnt = args.nr_hash_funcs; + skel->rodata->bloom_seed = /* 0; */ rand(); + + bloom_sz = (long)args.nr_hash_funcs * args.nr_entries / 5 * 7; + for (i = 64; i < bloom_sz; i *= 2) { } + bloom_sz = i / 64; + skel->rodata->bloom_mask = bloom_sz - 1; + + //printf("SET BLOOM SZ TO %d NR_ENTRIES %d HASH CNT %d \n", bloom_sz, args.nr_entries, args.nr_hash_funcs); + return skel; } @@ -218,6 +237,11 @@ static void bloom_filter_map_setup(void) ctx.skel = setup_skeleton(); + if (bloom_filter_map__load(ctx.skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + populate_maps(); link = bpf_program__attach(ctx.skel->progs.prog_bloom_filter); @@ -227,12 +251,59 @@ static void bloom_filter_map_setup(void) } } +static void custom_bloom_filter_map_setup(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(); + + if (bloom_filter_map__load(ctx.skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + + populate_maps(); + + link = bpf_program__attach(ctx.skel->progs.prog_custom_bloom_filter); + if (!link) { + fprintf(stderr, "failed to attach program!\n"); + exit(1); + } +} + static void hashmap_lookup_setup(void) { struct bpf_link *link; ctx.skel = setup_skeleton(); + if (bloom_filter_map__load(ctx.skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + + populate_maps(); + + link = bpf_program__attach(ctx.skel->progs.prog_bloom_filter_hashmap_lookup); + if (!link) { + fprintf(stderr, "failed to attach program!\n"); + exit(1); + } +} +static void hashmap_lookup_custom_setup(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(); + + ctx.skel->rodata->hashmap_use_bloom_filter = false; + ctx.skel->rodata->hashmap_use_custom_bloom_filter = true; + + if (bloom_filter_map__load(ctx.skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + populate_maps(); link = bpf_program__attach(ctx.skel->progs.prog_bloom_filter_hashmap_lookup); @@ -250,6 +321,11 @@ static void hashmap_no_bloom_filter_setup(void) ctx.skel->rodata->hashmap_use_bloom_filter = false; + if (bloom_filter_map__load(ctx.skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + populate_maps(); link = bpf_program__attach(ctx.skel->progs.prog_bloom_filter_hashmap_lookup); @@ -378,6 +454,17 @@ const struct bench bench_bloom_filter_map = { .report_final = hits_drops_report_final, }; +const struct bench bench_custom_bloom_filter_map = { + .name = "custom-bloom-filter-map", + .validate = validate, + .setup = custom_bloom_filter_map_setup, + .producer_thread = producer, + .consumer_thread = consumer, + .measure = measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + const struct bench bench_bloom_filter_false_positive = { .name = "bloom-filter-false-positive", .validate = validate, @@ -389,6 +476,17 @@ const struct bench bench_bloom_filter_false_positive = { .report_final = false_hits_report_final, }; +const struct bench bench_custom_bloom_filter_false_positive = { + .name = "custom-bloom-filter-false-positive", + .validate = validate, + .setup = hashmap_lookup_custom_setup, + .producer_thread = producer, + .consumer_thread = consumer, + .measure = measure, + .report_progress = false_hits_report_progress, + .report_final = false_hits_report_final, +}; + const struct bench bench_hashmap_without_bloom_filter = { .name = "hashmap-without-bloom-filter", .validate = validate, @@ -410,3 +508,14 @@ const struct bench bench_hashmap_with_bloom_filter = { .report_progress = hits_drops_report_progress, .report_final = hits_drops_report_final, }; + +const struct bench bench_hashmap_with_custom_bloom_filter = { + .name = "hashmap-with-custom-bloom-filter", + .validate = validate, + .setup = hashmap_lookup_custom_setup, + .producer_thread = producer, + .consumer_thread = consumer, + .measure = measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; diff --git a/tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh b/tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh index 239c040b7aaa..ea2c2fff3f40 100755 --- a/tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh +++ b/tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh @@ -7,9 +7,9 @@ set -eufo pipefail header "Bloom filter map" for t in 1 4 8; do -for h in {1..10}; do +for h in 1 3 5 10; do subtitle "# threads: $t, # hashes: $h" - for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + for e in 10000 100000 1000000; do printf "%'d entries -\n" $e printf "\t" summarize "Total operations: " \ @@ -17,20 +17,21 @@ subtitle "# threads: $t, # hashes: $h" printf "\t" summarize_percentage "False positive rate: " \ "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e bloom-filter-false-positive)" + printf "\t" + summarize "[CUSTOM] Total operations: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e custom-bloom-filter-map)" + printf "\t" + summarize_percentage "[CUSTOM] False positive rate: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e custom-bloom-filter-false-positive)" done printf "\n" done done -header "Bloom filter map, multi-producer contention" -for t in 1 2 3 4 8 12 16 20 24 28 32 36 40 44 48 52; do - summarize "$t threads - " "$($RUN_BENCH -p $t bloom-filter-map)" -done - header "Hashmap without bloom filter vs. hashmap with bloom filter (throughput, 8 threads)" -for h in {1..10}; do +for h in 1 3 5 10; do subtitle "# hashes: $h" - for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + for e in 10000 100000 1000000; do printf "%'d entries -\n" $e printf "\t" summarize_total "Hashmap without bloom filter: " \ @@ -38,6 +39,9 @@ subtitle "# hashes: $h" printf "\t" summarize_total "Hashmap with bloom filter: " \ "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-with-bloom-filter)" + printf "\t" + summarize_total "[CUSTOM] Hashmap with bloom filter: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-with-custom-bloom-filter)" done printf "\n" done diff --git a/tools/testing/selftests/bpf/benchs/run_common.sh b/tools/testing/selftests/bpf/benchs/run_common.sh index 9a16be78b180..961d25374150 100644 --- a/tools/testing/selftests/bpf/benchs/run_common.sh +++ b/tools/testing/selftests/bpf/benchs/run_common.sh @@ -1,7 +1,7 @@ #!/bin/bash # SPDX-License-Identifier: GPL-2.0 -RUN_BENCH="sudo ./bench -w3 -d10 -a" +RUN_BENCH="sudo ./bench -w1 -d5 -a" function header() {