From patchwork Tue Sep 21 21:02:21 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12508801 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=-20.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,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 3DD20C433F5 for ; Tue, 21 Sep 2021 21:05:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 23FA261186 for ; Tue, 21 Sep 2021 21:05:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232953AbhIUVGa (ORCPT ); Tue, 21 Sep 2021 17:06:30 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:26112 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232718AbhIUVG3 (ORCPT ); Tue, 21 Sep 2021 17:06:29 -0400 Received: from pps.filterd (m0044012.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18LHAotT009206 for ; Tue, 21 Sep 2021 14:05:01 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding : content-type; s=facebook; bh=coES2FqfLYStZd0UcRFaI47R0IoHRXFlM74fSdU0oPM=; b=fXwps4SEPrvjKdcF8XZzGp573RpKxcluOabkRMO/337lrxNAozrmFfIoopjE4YU6RMSi 0m6bHDrjZ7KkgVT19LKUV4DCkW6MgtCIjTNaJmBN9VEV4oVtvsWznHMwrqAz9LSCoj4v Yk8oTyVsc+yPalZvT2M2cxFyxESgd5CWesA= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3b7d744kbm-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Tue, 21 Sep 2021 14:05:00 -0700 Received: from intmgw001.37.frc1.facebook.com (2620:10d:c085:208::f) by mail.thefacebook.com (2620:10d:c085:11d::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Tue, 21 Sep 2021 14:04:59 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id 840362AC134F; Tue, 21 Sep 2021 14:04:50 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH v3 bpf-next 1/5] bpf: Add bloom filter map implementation Date: Tue, 21 Sep 2021 14:02:21 -0700 Message-ID: <20210921210225.4095056-2-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210921210225.4095056-1-joannekoong@fb.com> References: <20210921210225.4095056-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-ORIG-GUID: l5Omdl6EpMnd4GNb6fcyv4JELefQkeKB X-Proofpoint-GUID: l5Omdl6EpMnd4GNb6fcyv4JELefQkeKB 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-21_06,2021-09-20_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 phishscore=0 lowpriorityscore=0 spamscore=0 suspectscore=0 malwarescore=0 bulkscore=0 clxscore=1015 impostorscore=0 mlxscore=0 adultscore=0 priorityscore=1501 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109030001 definitions=main-2109210125 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Bloom filters are a space-efficient probabilistic data structure used to quickly test whether an element exists in a set. In a bloom filter, false positives are possible whereas false negatives should never be. This patch adds a bloom filter map for bpf programs. The bloom filter map supports peek (determining whether an element is present in the map) and push (adding an element to the map) operations.These operations are exposed to userspace applications through the already existing syscalls in the following way: BPF_MAP_LOOKUP_ELEM -> peek BPF_MAP_UPDATE_ELEM -> push The bloom filter map does not have keys, only values. In light of this, the bloom filter map's API matches that of queue stack maps: user applications use BPF_MAP_LOOKUP_ELEM/BPF_MAP_UPDATE_ELEM which correspond internally to bpf_map_peek_elem/bpf_map_push_elem, and bpf programs must use the bpf_map_peek_elem and bpf_map_push_elem APIs to query or add an element to the bloom filter map. When the bloom filter map is created, it must be created with a key_size of 0. For updates, the user will pass in the element to add to the map as the value, with a NULL key. For lookups, the user will pass in the element to query in the map as the value. In the verifier layer, this requires us to modify the argument type of a bloom filter's BPF_FUNC_map_peek_elem call to ARG_PTR_TO_MAP_VALUE; as well, in the syscall layer, we need to copy over the user value so that in bpf_map_peek_elem, we know which specific value to query. A few things to please take note of: * If there are any concurrent lookups + updates, the user is responsible for synchronizing this to ensure no false negative lookups occur. * The number of hashes to use for the bloom filter is configurable from userspace. If no number is specified, the default used will be 5 hash functions. The benchmarks later in this patchset can help compare the performance of using different number of hashes on different entry sizes. In general, using more hashes decreases the speed of a lookup, but increases the false positive rate of an element being detected in the bloom filter. * Deleting an element in the bloom filter map is not supported. * The bloom filter map may be used as an inner map. * The "max_entries" size that is specified at map creation time is used to approximate a reasonable bitmap size for the bloom filter, and is not otherwise strictly enforced. If the user wishes to insert more entries into the bloom filter than "max_entries", they may do so but they should be aware that this may lead to a higher false positive rate. Signed-off-by: Joanne Koong --- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 1 + kernel/bpf/Makefile | 2 +- kernel/bpf/bloom_filter.c | 185 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 14 ++- kernel/bpf/verifier.c | 19 +++- tools/include/uapi/linux/bpf.h | 1 + 7 files changed, 217 insertions(+), 6 deletions(-) create mode 100644 kernel/bpf/bloom_filter.c diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h index 9c81724e4b98..c4424ac2fa02 100644 --- a/include/linux/bpf_types.h +++ b/include/linux/bpf_types.h @@ -125,6 +125,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_STACK, stack_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_STRUCT_OPS, bpf_struct_ops_map_ops) #endif BPF_MAP_TYPE(BPF_MAP_TYPE_RINGBUF, ringbuf_map_ops) +BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops) BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint) BPF_LINK_TYPE(BPF_LINK_TYPE_TRACING, tracing) diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index 6fc59d61937a..fec9fcfe0629 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -906,6 +906,7 @@ enum bpf_map_type { BPF_MAP_TYPE_RINGBUF, BPF_MAP_TYPE_INODE_STORAGE, BPF_MAP_TYPE_TASK_STORAGE, + BPF_MAP_TYPE_BLOOM_FILTER, }; /* Note that tracing related programs such as diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile index 7f33098ca63f..cf6ca339f3cd 100644 --- a/kernel/bpf/Makefile +++ b/kernel/bpf/Makefile @@ -7,7 +7,7 @@ endif CFLAGS_core.o += $(call cc-disable-warning, override-init) $(cflags-nogcse-yy) obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o bpf_iter.o map_iter.o task_iter.o prog_iter.o -obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o +obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o obj-$(CONFIG_BPF_SYSCALL) += bpf_local_storage.o bpf_task_storage.o obj-${CONFIG_BPF_LSM} += bpf_inode_storage.o diff --git a/kernel/bpf/bloom_filter.c b/kernel/bpf/bloom_filter.c new file mode 100644 index 000000000000..72254edb24f1 --- /dev/null +++ b/kernel/bpf/bloom_filter.c @@ -0,0 +1,185 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include +#include +#include + +#define BLOOM_FILTER_CREATE_FLAG_MASK \ + (BPF_F_NUMA_NODE | BPF_F_ZERO_SEED | BPF_F_ACCESS_MASK) + +struct bpf_bloom_filter { + struct bpf_map map; + u32 bit_array_mask; + u32 hash_seed; + /* If the size of the values in the bloom filter is u32 aligned, + * then it is more performant to use jhash2 as the underlying hash + * function, else we use jhash. This tracks the number of u32s + * in an u32-aligned value size. If the value size is not u32 aligned, + * this will be 0. + */ + u32 aligned_u32_count; + u32 nr_hash_funcs; + unsigned long bit_array[]; +}; + +static inline u32 hash(struct bpf_bloom_filter *bloom_filter, void *value, + u64 value_size, u32 index) +{ + if (bloom_filter->aligned_u32_count) + return jhash2(value, bloom_filter->aligned_u32_count, + bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask; + + return jhash(value, value_size, bloom_filter->hash_seed + index) & + bloom_filter->bit_array_mask; +} + +static int bloom_filter_map_peek_elem(struct bpf_map *map, void *value) +{ + struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); + u32 i; + + for (i = 0; i < bloom_filter->nr_hash_funcs; i++) { + if (!test_bit(hash(bloom_filter, value, map->value_size, i), + bloom_filter->bit_array)) + return -ENOENT; + } + + return 0; +} + +static struct bpf_map *bloom_filter_map_alloc(union bpf_attr *attr) +{ + u32 nr_bits, bit_array_bytes, bit_array_mask; + int numa_node = bpf_map_attr_numa_node(attr); + struct bpf_bloom_filter *bloom_filter; + u32 nr_hash_funcs; + + if (!bpf_capable()) + return ERR_PTR(-EPERM); + + if (attr->key_size != 0 || attr->value_size == 0 || attr->max_entries == 0 || + attr->map_flags & ~BLOOM_FILTER_CREATE_FLAG_MASK || + !bpf_map_flags_access_ok(attr->map_flags)) + return ERR_PTR(-EINVAL); + + /* Default to 5 if no number of hash functions was specified */ + nr_hash_funcs = attr->nr_hash_funcs == 0 ? 5 : attr->nr_hash_funcs; + + /* For the bloom filter, the optimal bit array size that minimizes the + * false positive probability is n * k / ln(2) where n is the number of + * expected entries in the bloom filter and k is the number of hash + * functions. We use 7 / 5 to approximate 1 / ln(2). + * + * We round this up to the nearest power of two to enable more efficient + * hashing using bitmasks. The bitmask will be the bit array size - 1. + * + * If this overflows a u32, the bit array size will have 2^32 (4 + * GB) bits. + */ + if (check_mul_overflow(attr->max_entries, nr_hash_funcs, &nr_bits) || + check_mul_overflow(nr_bits / 5, (u32)7, &nr_bits) || + nr_bits > (1UL << 31)) { + /* The bit array size is 2^32 bits but to avoid overflowing the + * u32, we use BITS_TO_BYTES(U32_MAX), which will round up to the + * equivalent number of bytes + */ + bit_array_bytes = BITS_TO_BYTES(U32_MAX); + bit_array_mask = U32_MAX; + } else { + if (nr_bits <= BITS_PER_LONG) + nr_bits = BITS_PER_LONG; + else + nr_bits = roundup_pow_of_two(nr_bits); + bit_array_bytes = BITS_TO_BYTES(nr_bits); + bit_array_mask = nr_bits - 1; + } + + bit_array_bytes = roundup(bit_array_bytes, sizeof(unsigned long)); + bloom_filter = bpf_map_area_alloc(sizeof(*bloom_filter) + bit_array_bytes, + numa_node); + + if (!bloom_filter) + return ERR_PTR(-ENOMEM); + + bpf_map_init_from_attr(&bloom_filter->map, attr); + + bloom_filter->nr_hash_funcs = nr_hash_funcs; + bloom_filter->bit_array_mask = bit_array_mask; + if ((attr->value_size & (sizeof(u32) - 1)) == 0) + bloom_filter->aligned_u32_count = attr->value_size / sizeof(u32); + + if (!(attr->map_flags & BPF_F_ZERO_SEED)) + bloom_filter->hash_seed = get_random_int(); + + return &bloom_filter->map; +} + +static void bloom_filter_map_free(struct bpf_map *map) +{ + struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); + + bpf_map_area_free(bloom_filter); +} + +static int bloom_filter_map_push_elem(struct bpf_map *map, void *value, + u64 flags) +{ + struct bpf_bloom_filter *bloom_filter = + container_of(map, struct bpf_bloom_filter, map); + u32 i; + + if (flags != BPF_ANY) + return -EINVAL; + + for (i = 0; i < bloom_filter->nr_hash_funcs; i++) + set_bit(hash(bloom_filter, value, map->value_size, i), + bloom_filter->bit_array); + + return 0; +} + +static void *bloom_filter_map_lookup_elem(struct bpf_map *map, void *key) +{ + /* The eBPF program should use map_peek_elem instead */ + return ERR_PTR(-EINVAL); +} + +static int bloom_filter_map_update_elem(struct bpf_map *map, void *key, + void *value, u64 flags) +{ + /* The eBPF program should use map_push_elem instead */ + return -EINVAL; +} + +static int bloom_filter_map_delete_elem(struct bpf_map *map, void *key) +{ + return -EOPNOTSUPP; +} + +static int bloom_filter_map_get_next_key(struct bpf_map *map, void *key, + void *next_key) +{ + return -EOPNOTSUPP; +} + +static int bloom_filter_map_btf_id; +const struct bpf_map_ops bloom_filter_map_ops = { + .map_meta_equal = bpf_map_meta_equal, + .map_alloc = bloom_filter_map_alloc, + .map_free = bloom_filter_map_free, + .map_push_elem = bloom_filter_map_push_elem, + .map_peek_elem = bloom_filter_map_peek_elem, + .map_lookup_elem = bloom_filter_map_lookup_elem, + .map_update_elem = bloom_filter_map_update_elem, + .map_delete_elem = bloom_filter_map_delete_elem, + .map_get_next_key = bloom_filter_map_get_next_key, + .map_check_btf = map_check_no_btf, + .map_btf_name = "bpf_bloom_filter", + .map_btf_id = &bloom_filter_map_btf_id, +}; diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index 4e50c0bfdb7d..9865b5b1e667 100644 --- a/kernel/bpf/syscall.c +++ b/kernel/bpf/syscall.c @@ -199,7 +199,8 @@ static int bpf_map_update_value(struct bpf_map *map, struct fd f, void *key, err = bpf_fd_reuseport_array_update_elem(map, key, value, flags); } else if (map->map_type == BPF_MAP_TYPE_QUEUE || - map->map_type == BPF_MAP_TYPE_STACK) { + map->map_type == BPF_MAP_TYPE_STACK || + map->map_type == BPF_MAP_TYPE_BLOOM_FILTER) { err = map->ops->map_push_elem(map, value, flags); } else { rcu_read_lock(); @@ -238,7 +239,8 @@ static int bpf_map_copy_value(struct bpf_map *map, void *key, void *value, } else if (map->map_type == BPF_MAP_TYPE_REUSEPORT_SOCKARRAY) { err = bpf_fd_reuseport_array_lookup_elem(map, key, value); } else if (map->map_type == BPF_MAP_TYPE_QUEUE || - map->map_type == BPF_MAP_TYPE_STACK) { + map->map_type == BPF_MAP_TYPE_STACK || + map->map_type == BPF_MAP_TYPE_BLOOM_FILTER) { err = map->ops->map_peek_elem(map, value); } else if (map->map_type == BPF_MAP_TYPE_STRUCT_OPS) { /* struct_ops map requires directly updating "value" */ @@ -1080,6 +1082,14 @@ static int map_lookup_elem(union bpf_attr *attr) if (!value) goto free_key; + if (map->map_type == BPF_MAP_TYPE_BLOOM_FILTER) { + if (copy_from_user(value, uvalue, value_size)) + err = -EFAULT; + else + err = bpf_map_copy_value(map, key, value, attr->flags); + goto free_value; + } + err = bpf_map_copy_value(map, key, value, attr->flags); if (err) goto free_value; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index e76b55917905..fd2b7f9dccae 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -4813,7 +4813,10 @@ static int resolve_map_arg_type(struct bpf_verifier_env *env, return -EINVAL; } break; - + case BPF_MAP_TYPE_BLOOM_FILTER: + if (meta->func_id == BPF_FUNC_map_peek_elem) + *arg_type = ARG_PTR_TO_MAP_VALUE; + break; default: break; } @@ -5388,6 +5391,11 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, func_id != BPF_FUNC_task_storage_delete) goto error; break; + case BPF_MAP_TYPE_BLOOM_FILTER: + if (func_id != BPF_FUNC_map_push_elem && + func_id != BPF_FUNC_map_peek_elem) + goto error; + break; default: break; } @@ -5455,13 +5463,18 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, map->map_type != BPF_MAP_TYPE_SOCKHASH) goto error; break; - case BPF_FUNC_map_peek_elem: case BPF_FUNC_map_pop_elem: - case BPF_FUNC_map_push_elem: if (map->map_type != BPF_MAP_TYPE_QUEUE && map->map_type != BPF_MAP_TYPE_STACK) goto error; break; + case BPF_FUNC_map_push_elem: + case BPF_FUNC_map_peek_elem: + if (map->map_type != BPF_MAP_TYPE_QUEUE && + map->map_type != BPF_MAP_TYPE_STACK && + map->map_type != BPF_MAP_TYPE_BLOOM_FILTER) + goto error; + break; case BPF_FUNC_sk_storage_get: case BPF_FUNC_sk_storage_delete: if (map->map_type != BPF_MAP_TYPE_SK_STORAGE) diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index 6fc59d61937a..fec9fcfe0629 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -906,6 +906,7 @@ enum bpf_map_type { BPF_MAP_TYPE_RINGBUF, BPF_MAP_TYPE_INODE_STORAGE, BPF_MAP_TYPE_TASK_STORAGE, + BPF_MAP_TYPE_BLOOM_FILTER, }; /* Note that tracing related programs such as From patchwork Tue Sep 21 21:02:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12508803 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=-20.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,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 DC7A9C433F5 for ; Tue, 21 Sep 2021 21:05:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BD9C9611BD for ; Tue, 21 Sep 2021 21:05:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233682AbhIUVGf (ORCPT ); Tue, 21 Sep 2021 17:06:35 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:22548 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232718AbhIUVGf (ORCPT ); Tue, 21 Sep 2021 17:06:35 -0400 Received: from pps.filterd (m0044012.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18LHAuef009458 for ; Tue, 21 Sep 2021 14:05:06 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding : content-type; s=facebook; bh=cRrjDAfVQasB8VZWTfA0fXLxj2ftoQtSP0ny/Dz1LfE=; b=mxvVOEjxBRaxuz3i7rsoz6tVjYpqmrY6ysjZIjdj4ur7qm7pB4FtD6RF3C7VyAa/JDe5 daTLdFSW1guv5NVivPWwW0WIZlUUdEOt5zo2AV0AMFtEG51IRGKyjXf94B3P6RHlsRsz JEXUaOc9p/pDNf39wggM3HSTHLcqsrbCTgo= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3b7d744kc9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Tue, 21 Sep 2021 14:05:06 -0700 Received: from intmgw001.37.frc1.facebook.com (2620:10d:c085:108::4) by mail.thefacebook.com (2620:10d:c085:11d::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Tue, 21 Sep 2021 14:05:05 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id 6556C2AC13AF; Tue, 21 Sep 2021 14:05:01 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH v3 bpf-next 2/5] libbpf: Allow the number of hashes in bloom filter maps to be configurable Date: Tue, 21 Sep 2021 14:02:22 -0700 Message-ID: <20210921210225.4095056-3-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210921210225.4095056-1-joannekoong@fb.com> References: <20210921210225.4095056-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-ORIG-GUID: ky-0mTr-Jl9_DJy07ZWpR4hBHwSSLp41 X-Proofpoint-GUID: ky-0mTr-Jl9_DJy07ZWpR4hBHwSSLp41 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-21_06,2021-09-20_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 phishscore=0 lowpriorityscore=0 spamscore=0 suspectscore=0 malwarescore=0 bulkscore=0 clxscore=1015 impostorscore=0 mlxscore=0 adultscore=0 priorityscore=1501 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109030001 definitions=main-2109210125 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net This patch adds the libbpf infrastructure that will allow the user to specify a configurable number of hash functions to use for the bloom filter map. Please note that this patch does not enforce that a pinned bloom filter map may only be reused if the number of hash functions is the same. If they are not the same, the number of hash functions used will be the one that was set for the pinned map. Signed-off-by: Joanne Koong --- include/uapi/linux/bpf.h | 5 ++++- tools/include/uapi/linux/bpf.h | 5 ++++- tools/lib/bpf/bpf.c | 2 ++ tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/libbpf.c | 32 +++++++++++++++++++++++++++----- tools/lib/bpf/libbpf.h | 2 ++ tools/lib/bpf/libbpf.map | 1 + tools/lib/bpf/libbpf_internal.h | 4 +++- 8 files changed, 44 insertions(+), 8 deletions(-) diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index fec9fcfe0629..2e3048488feb 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -1262,7 +1262,10 @@ union bpf_attr { __u32 map_flags; /* BPF_MAP_CREATE related * flags defined above. */ - __u32 inner_map_fd; /* fd pointing to the inner map */ + union { + __u32 inner_map_fd; /* fd pointing to the inner map */ + __u32 nr_hash_funcs; /* or number of hash functions */ + }; __u32 numa_node; /* numa node (effective only if * BPF_F_NUMA_NODE is set). */ diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index fec9fcfe0629..2e3048488feb 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -1262,7 +1262,10 @@ union bpf_attr { __u32 map_flags; /* BPF_MAP_CREATE related * flags defined above. */ - __u32 inner_map_fd; /* fd pointing to the inner map */ + union { + __u32 inner_map_fd; /* fd pointing to the inner map */ + __u32 nr_hash_funcs; /* or number of hash functions */ + }; __u32 numa_node; /* numa node (effective only if * BPF_F_NUMA_NODE is set). */ diff --git a/tools/lib/bpf/bpf.c b/tools/lib/bpf/bpf.c index 2401fad090c5..8a9dd4f6d6c8 100644 --- a/tools/lib/bpf/bpf.c +++ b/tools/lib/bpf/bpf.c @@ -100,6 +100,8 @@ int bpf_create_map_xattr(const struct bpf_create_map_attr *create_attr) if (attr.map_type == BPF_MAP_TYPE_STRUCT_OPS) attr.btf_vmlinux_value_type_id = create_attr->btf_vmlinux_value_type_id; + else if (attr.map_type == BPF_MAP_TYPE_BLOOM_FILTER) + attr.nr_hash_funcs = create_attr->nr_hash_funcs; else attr.inner_map_fd = create_attr->inner_map_fd; diff --git a/tools/lib/bpf/bpf.h b/tools/lib/bpf/bpf.h index 6fffb3cdf39b..1194b6f01572 100644 --- a/tools/lib/bpf/bpf.h +++ b/tools/lib/bpf/bpf.h @@ -49,6 +49,7 @@ struct bpf_create_map_attr { union { __u32 inner_map_fd; __u32 btf_vmlinux_value_type_id; + __u32 nr_hash_funcs; }; }; diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c index da65a1666a5e..e51e68a07aaf 100644 --- a/tools/lib/bpf/libbpf.c +++ b/tools/lib/bpf/libbpf.c @@ -378,6 +378,7 @@ struct bpf_map { char *pin_path; bool pinned; bool reused; + __u32 nr_hash_funcs; }; enum extern_type { @@ -1291,6 +1292,11 @@ static bool bpf_map_type__is_map_in_map(enum bpf_map_type type) return false; } +static inline bool bpf_map__is_bloom_filter(const struct bpf_map *map) +{ + return map->def.type == BPF_MAP_TYPE_BLOOM_FILTER; +} + int bpf_object__section_size(const struct bpf_object *obj, const char *name, __u32 *size) { @@ -2238,6 +2244,10 @@ int parse_btf_map_def(const char *map_name, struct btf *btf, } map_def->pinning = val; map_def->parts |= MAP_DEF_PINNING; + } else if (strcmp(name, "nr_hash_funcs") == 0) { + if (!get_map_field_int(map_name, btf, m, &map_def->nr_hash_funcs)) + return -EINVAL; + map_def->parts |= MAP_DEF_NR_HASH_FUNCS; } else { if (strict) { pr_warn("map '%s': unknown field '%s'.\n", map_name, name); @@ -2266,6 +2276,7 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *def map->numa_node = def->numa_node; map->btf_key_type_id = def->key_type_id; map->btf_value_type_id = def->value_type_id; + map->nr_hash_funcs = def->nr_hash_funcs; if (def->parts & MAP_DEF_MAP_TYPE) pr_debug("map '%s': found type = %u.\n", map->name, def->map_type); @@ -2290,6 +2301,8 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *def pr_debug("map '%s': found pinning = %u.\n", map->name, def->pinning); if (def->parts & MAP_DEF_NUMA_NODE) pr_debug("map '%s': found numa_node = %u.\n", map->name, def->numa_node); + if (def->parts & MAP_DEF_NR_HASH_FUNCS) + pr_debug("map '%s': found nr_hash_funcs = %u.\n", map->name, def->nr_hash_funcs); if (def->parts & MAP_DEF_INNER_MAP) pr_debug("map '%s': found inner map definition.\n", map->name); @@ -4616,10 +4629,6 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.max_entries = def->max_entries; } - if (bpf_map__is_struct_ops(map)) - create_attr.btf_vmlinux_value_type_id = - map->btf_vmlinux_value_type_id; - create_attr.btf_fd = 0; create_attr.btf_key_type_id = 0; create_attr.btf_value_type_id = 0; @@ -4629,7 +4638,12 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.btf_value_type_id = map->btf_value_type_id; } - if (bpf_map_type__is_map_in_map(def->type)) { + if (bpf_map__is_struct_ops(map)) { + create_attr.btf_vmlinux_value_type_id = + map->btf_vmlinux_value_type_id; + } else if (bpf_map__is_bloom_filter(map)) { + create_attr.nr_hash_funcs = map->nr_hash_funcs; + } else if (bpf_map_type__is_map_in_map(def->type)) { if (map->inner_map) { err = bpf_object__create_map(obj, map->inner_map, true); if (err) { @@ -8610,6 +8624,14 @@ int bpf_map__set_value_size(struct bpf_map *map, __u32 size) return 0; } +int bpf_map__set_nr_hash_funcs(struct bpf_map *map, __u32 nr_hash_funcs) +{ + if (map->fd >= 0) + return libbpf_err(-EBUSY); + map->nr_hash_funcs = nr_hash_funcs; + return 0; +} + __u32 bpf_map__btf_key_type_id(const struct bpf_map *map) { return map ? map->btf_key_type_id : 0; diff --git a/tools/lib/bpf/libbpf.h b/tools/lib/bpf/libbpf.h index d0bedd673273..5c441744f766 100644 --- a/tools/lib/bpf/libbpf.h +++ b/tools/lib/bpf/libbpf.h @@ -550,6 +550,8 @@ LIBBPF_API __u32 bpf_map__btf_value_type_id(const struct bpf_map *map); /* get/set map if_index */ LIBBPF_API __u32 bpf_map__ifindex(const struct bpf_map *map); LIBBPF_API int bpf_map__set_ifindex(struct bpf_map *map, __u32 ifindex); +/* set nr_hash_funcs */ +LIBBPF_API int bpf_map__set_nr_hash_funcs(struct bpf_map *map, __u32 nr_hash_funcs); typedef void (*bpf_map_clear_priv_t)(struct bpf_map *, void *); LIBBPF_API int bpf_map__set_priv(struct bpf_map *map, void *priv, diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map index 9e649cf9e771..ee0e1e7648f4 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -385,6 +385,7 @@ LIBBPF_0.5.0 { btf__load_vmlinux_btf; btf_dump__dump_type_data; libbpf_set_strict_mode; + bpf_map__set_nr_hash_funcs; } LIBBPF_0.4.0; LIBBPF_0.6.0 { diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_internal.h index ceb0c98979bc..95dbbeba231f 100644 --- a/tools/lib/bpf/libbpf_internal.h +++ b/tools/lib/bpf/libbpf_internal.h @@ -186,8 +186,9 @@ enum map_def_parts { MAP_DEF_NUMA_NODE = 0x080, MAP_DEF_PINNING = 0x100, MAP_DEF_INNER_MAP = 0x200, + MAP_DEF_NR_HASH_FUNCS = 0x400, - MAP_DEF_ALL = 0x3ff, /* combination of all above */ + MAP_DEF_ALL = 0x7ff, /* combination of all above */ }; struct btf_map_def { @@ -201,6 +202,7 @@ struct btf_map_def { __u32 map_flags; __u32 numa_node; __u32 pinning; + __u32 nr_hash_funcs; }; int parse_btf_map_def(const char *map_name, struct btf *btf, From patchwork Tue Sep 21 21:02:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12508805 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=-20.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,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 07050C433F5 for ; Tue, 21 Sep 2021 21:05:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C7B6F611BD for ; Tue, 21 Sep 2021 21:05:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232982AbhIUVGx (ORCPT ); Tue, 21 Sep 2021 17:06:53 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:63428 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232718AbhIUVGx (ORCPT ); Tue, 21 Sep 2021 17:06:53 -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 18LHC7Sf011146 for ; Tue, 21 Sep 2021 14:05:24 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding : content-type; s=facebook; bh=L316+TEwRU4isDazapftaYkgLTscK323/uV8/pplwDI=; b=FT3BD0ESQOzOsi6ODhRrw2MQBPEPaX/4qLByGBPyKN/wGN6alCdcbT/qFZtEwD9Knx7S zxszYu8qnIozH7DRcCqEMsWsF2A/NlK44TS8NHpXeAntdrx6tSRCgZyHD2Cf8eiVBIU8 aRLXrH73MjHPgk6TyJAdvaXmnLF6xGRurUE= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3b6xyhh5cm-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Tue, 21 Sep 2021 14:05:24 -0700 Received: from intmgw001.37.frc1.facebook.com (2620:10d:c085:208::11) by mail.thefacebook.com (2620:10d:c085:11d::7) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Tue, 21 Sep 2021 14:05:23 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id 0FF162AC13CC; Tue, 21 Sep 2021 14:05:14 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH v3 bpf-next 3/5] selftests/bpf: Add bloom filter map test cases Date: Tue, 21 Sep 2021 14:02:23 -0700 Message-ID: <20210921210225.4095056-4-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210921210225.4095056-1-joannekoong@fb.com> References: <20210921210225.4095056-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-ORIG-GUID: qByvBt7GzB8HCERbgSLU9av1ToP3yWXf X-Proofpoint-GUID: qByvBt7GzB8HCERbgSLU9av1ToP3yWXf 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-21_06,2021-09-20_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 impostorscore=0 malwarescore=0 bulkscore=0 mlxlogscore=972 adultscore=0 priorityscore=1501 suspectscore=0 clxscore=1015 mlxscore=0 lowpriorityscore=0 phishscore=0 spamscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109030001 definitions=main-2109210125 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net This patch adds test cases for bpf bloom filter maps. They include tests checking against invalid operations by userspace, tests for using the bloom filter map as an inner map, and a bpf program that queries the bloom filter map for values added by a userspace program. Signed-off-by: Joanne Koong --- .../bpf/prog_tests/bloom_filter_map.c | 177 ++++++++++++++++++ .../selftests/bpf/progs/bloom_filter_map.c | 83 ++++++++ 2 files changed, 260 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c create mode 100644 tools/testing/selftests/bpf/progs/bloom_filter_map.c diff --git a/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c b/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c new file mode 100644 index 000000000000..134705d74a66 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/bloom_filter_map.c @@ -0,0 +1,177 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include "bloom_filter_map.skel.h" + +static void test_bloom_filter_map_fail(void) +{ + struct bpf_create_map_attr xattr = { + .name = "bloom_filter_map", + .map_type = BPF_MAP_TYPE_BLOOM_FILTER, + .max_entries = 100, + .value_size = sizeof(__u32), + .nr_hash_funcs = 3, + }; + __u32 value; + int fd, err; + + /* Invalid key size */ + xattr.key_size = 4; + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_LT(fd, 0, "bpf_create_map bloom filter invalid key size")) + close(fd); + xattr.key_size = 0; + + /* Invalid value size */ + xattr.value_size = 0; + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_LT(fd, 0, "bpf_create_map bloom filter invalid value size")) + close(fd); + xattr.value_size = sizeof(__u32); + + /* Invalid max entries size */ + xattr.max_entries = 0; + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_LT(fd, 0, "bpf_create_map bloom filter invalid max entries size")) + close(fd); + xattr.max_entries = 100; + + /* Bloom filter maps do not support BPF_F_NO_PREALLOC */ + xattr.map_flags = BPF_F_NO_PREALLOC; + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_LT(fd, 0, "bpf_create_map bloom filter invalid flags")) + close(fd); + xattr.map_flags = 0; + + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_GE(fd, 0, "bpf_create_map bloom filter")) + return; + + /* Test invalid flags */ + err = bpf_map_update_elem(fd, NULL, &value, -1); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bloom filter invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, BPF_EXIST); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bloom filter invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, BPF_F_LOCK); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bloom filter invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, BPF_NOEXIST); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bloom filter invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, 10000); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bloom filter invalid flags"); + + close(fd); +} + +static void bloom_filter_map(struct bloom_filter_map *skel) +{ + const int map_size = bpf_map__max_entries(skel->maps.map_random_data); + int err, map_random_data_fd, map_bloom_filter_fd, i; + __u64 val; + struct bpf_link *link; + + map_random_data_fd = bpf_map__fd(skel->maps.map_random_data); + map_bloom_filter_fd = bpf_map__fd(skel->maps.map_bloom_filter); + + /* Generate random values and add them to the maps */ + for (i = 0; i < map_size; i++) { + val = rand(); + err = bpf_map_update_elem(map_random_data_fd, &i, &val, BPF_ANY); + if (!ASSERT_OK(err, "Add random value to map_random_data")) + continue; + + err = bpf_map_update_elem(map_bloom_filter_fd, NULL, &val, 0); + if (!ASSERT_OK(err, "Add random value to map_bloom_filter")) + return; + } + + link = bpf_program__attach(skel->progs.prog_bloom_filter); + if (!ASSERT_OK_PTR(link, "link")) + return; + + syscall(SYS_getpgid); + + ASSERT_EQ(skel->bss->error, 0, "error"); + + bpf_link__destroy(link); +} + +static void bloom_filter_inner_map(struct bloom_filter_map *skel) +{ + const int map_size = bpf_map__max_entries(skel->maps.map_random_data); + int outer_map_fd, inner_map_fd, map_random_data_fd, err, i, key = 0; + struct bpf_create_map_attr xattr = { + .name = "bloom_filter_inner_map", + .map_type = BPF_MAP_TYPE_BLOOM_FILTER, + .max_entries = map_size, + .value_size = sizeof(__u64), + }; + struct bpf_link *link; + __u64 val; + + /* Create a bloom filter map that will be used as the inner map */ + inner_map_fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_GE(inner_map_fd, 0, "bpf_create_map bloom filter map as inner map")) + return; + + /* Generate random values and add them to the maps */ + map_random_data_fd = bpf_map__fd(skel->maps.map_random_data); + for (i = 0; i < map_size; i++) { + val = rand(); + err = bpf_map_update_elem(map_random_data_fd, &i, &val, BPF_ANY); + if (!ASSERT_OK(err, "Add random value to map_random_data")) + continue; + + err = bpf_map_update_elem(inner_map_fd, NULL, &val, 0); + if (!ASSERT_OK(err, "Add random value to inner_map_fd")) + goto done; + } + + outer_map_fd = bpf_map__fd(skel->maps.outer_map); + /* Add the bloom filter map to the outer map */ + err = bpf_map_update_elem(outer_map_fd, &key, &inner_map_fd, 0); + if (!ASSERT_OK(err, "Add bloom filter map to outer map")) + goto done; + + /* Attach the bloom_filter_inner_map prog */ + link = bpf_program__attach(skel->progs.prog_bloom_filter_inner_map); + if (!ASSERT_OK_PTR(link, "link")) + goto delete_inner_map; + + syscall(SYS_getpgid); + + ASSERT_EQ(skel->bss->error, 0, "error"); + + bpf_link__destroy(link); + +delete_inner_map: + /* Ensure the inner bloom filter map can be deleted */ + err = bpf_map_delete_elem(outer_map_fd, &key); + ASSERT_OK(err, "Delete inner bloom filter map"); + +done: + close(inner_map_fd); +} + +void test_bloom_filter_map(void) +{ + struct bloom_filter_map *skel; + + test_bloom_filter_map_fail(); + + skel = bloom_filter_map__open_and_load(); + if (!ASSERT_OK_PTR(skel, "bloom_filter_map__open_and_load")) + goto cleanup; + + bloom_filter_map(skel); + + bloom_filter_inner_map(skel); + +cleanup: + bloom_filter_map__destroy(skel); +} diff --git a/tools/testing/selftests/bpf/progs/bloom_filter_map.c b/tools/testing/selftests/bpf/progs/bloom_filter_map.c new file mode 100644 index 000000000000..5925d8dce4ec --- /dev/null +++ b/tools/testing/selftests/bpf/progs/bloom_filter_map.c @@ -0,0 +1,83 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include + +char _license[] SEC("license") = "GPL"; + +struct bpf_map; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(max_entries, 1000); + __type(key, __u32); + __type(value, __u64); +} map_random_data SEC(".maps"); + +struct map_bloom_filter_type { + __uint(type, BPF_MAP_TYPE_BLOOM_FILTER); + __uint(key_size, 0); + __uint(value_size, sizeof(__u64)); + __uint(max_entries, 1000); + __uint(nr_hash_funcs, 3); +} map_bloom_filter SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1); + __uint(key_size, sizeof(int)); + __uint(value_size, sizeof(int)); + __array(values, struct map_bloom_filter_type); +} outer_map SEC(".maps"); + +struct callback_ctx { + struct map_bloom_filter_type *map; +}; + +int error = 0; + +static __u64 +check_elem(struct bpf_map *map, __u32 *key, __u64 *val, + struct callback_ctx *data) +{ + int err; + + err = bpf_map_peek_elem(data->map, val); + if (err) { + error |= 1; + return 1; /* stop the iteration */ + } + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter(void *ctx) +{ + struct callback_ctx data; + + data.map = &map_bloom_filter; + bpf_for_each_map_elem(&map_random_data, check_elem, &data, 0); + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter_inner_map(void *ctx) +{ + struct map_bloom_filter_type *inner_map; + struct callback_ctx data; + int key = 0; + + inner_map = bpf_map_lookup_elem(&outer_map, &key); + if (!inner_map) { + error |= 2; + return 0; + } + + data.map = inner_map; + bpf_for_each_map_elem(&map_random_data, check_elem, &data, 0); + + return 0; +} From patchwork Tue Sep 21 21:02:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12508809 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=-20.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,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 5E2AAC433EF for ; Tue, 21 Sep 2021 21:05:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 43A4061186 for ; Tue, 21 Sep 2021 21:05:39 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233019AbhIUVHG (ORCPT ); Tue, 21 Sep 2021 17:07:06 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:46616 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232718AbhIUVHF (ORCPT ); Tue, 21 Sep 2021 17:07:05 -0400 Received: from pps.filterd (m0148460.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 18LHA1HE020969 for ; Tue, 21 Sep 2021 14:05:36 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type : content-transfer-encoding; s=facebook; bh=5HVJEwo66xu+zWR8lCIY6ChIZrvLlxsIoelrdGhVTCc=; b=Sf8qZEJ+hDFtC9KFy+Ul7M8PQ7t+KxAuCzmSEt6tpcs9WpSx9cgGrNIK+Y1xTCUU8pnB TWq1SsbrVoVf7JTV4mKn6SScD9ekI2bhsbYEuEuownTj6i7+wbUXMAjhAfralpT1CPbz i9l58iY2Lr5rDSGKPrn4qaN2vLHozCEl7eQ= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3b79q5nc32-15 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Tue, 21 Sep 2021 14:05:35 -0700 Received: from intmgw001.37.frc1.facebook.com (2620:10d:c085:208::11) 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; Tue, 21 Sep 2021 14:05:24 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id 285F32AC13D7; Tue, 21 Sep 2021 14:05:18 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH v3 bpf-next 4/5] bpf/benchs: Add benchmark test for bloom filter maps Date: Tue, 21 Sep 2021 14:02:24 -0700 Message-ID: <20210921210225.4095056-5-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210921210225.4095056-1-joannekoong@fb.com> References: <20210921210225.4095056-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: _9ICv0xQ7jaEysOxWzzfvqsUY1wizhQz X-Proofpoint-ORIG-GUID: _9ICv0xQ7jaEysOxWzzfvqsUY1wizhQz 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-21_06,2021-09-20_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 priorityscore=1501 impostorscore=0 bulkscore=0 phishscore=0 mlxlogscore=999 clxscore=1015 spamscore=0 mlxscore=0 suspectscore=0 malwarescore=0 adultscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109030001 definitions=main-2109210125 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net This patch adds benchmark tests for the throughput and false positive rate of bloom filter map lookups for a given number of entries and a given number of hash functions. These benchmarks show that as the number of hash functions increases, the throughput and the false positive rate of the bloom filter map decreases. From the benchmark data, the approximate average false-positive rates are roughly as follows: 1 hash function = ~30% 2 hash functions = ~15% 3 hash functions = ~5% 4 hash functions = ~2.5% 5 hash functions = ~1% 6 hash functions = ~0.5% 7 hash functions = ~0.35% 8 hash functions = ~0.15% 9 hash functions = ~0.1% 10 hash functions = ~0% Signed-off-by: Joanne Koong --- tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/bench.c | 35 ++ tools/testing/selftests/bpf/bench.h | 3 + .../bpf/benchs/bench_bloom_filter_map.c | 345 ++++++++++++++++++ .../bpf/benchs/run_bench_bloom_filter_map.sh | 28 ++ .../bpf/benchs/run_bench_ringbufs.sh | 30 +- .../selftests/bpf/benchs/run_common.sh | 48 +++ .../selftests/bpf/progs/bloom_filter_map.c | 74 ++++ 8 files changed, 538 insertions(+), 29 deletions(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh create mode 100644 tools/testing/selftests/bpf/benchs/run_common.sh diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index 326ea75ce99e..5dbaf7f512fd 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -520,13 +520,15 @@ $(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 \ $(OUTPUT)/perfbuf_bench.skel.h +$(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_map.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o $(OUTPUT)/testing_helpers.o \ $(OUTPUT)/bench_count.o \ $(OUTPUT)/bench_rename.o \ $(OUTPUT)/bench_trigger.o \ - $(OUTPUT)/bench_ringbufs.o + $(OUTPUT)/bench_ringbufs.o \ + $(OUTPUT)/bench_bloom_filter_map.o $(call msg,BINARY,,$@) $(Q)$(CC) $(LDFLAGS) -o $@ $(filter %.a %.o,$^) $(LDLIBS) diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index 6ea15b93a2f8..0bcbdb4405a3 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -51,6 +51,35 @@ void setup_libbpf() fprintf(stderr, "failed to increase RLIMIT_MEMLOCK: %d", err); } +void false_hits_report_progress(int iter, struct bench_res *res, long delta_ns) +{ + long total = res->false_hits + res->hits + res->drops; + + printf("Iter %3d (%7.3lfus): ", + iter, (delta_ns - 1000000000) / 1000.0); + + printf("%ld false hits of %ld total operations. Percentage = %2.2f %%\n", + res->false_hits, total, ((float)res->false_hits / total) * 100); +} + +void false_hits_report_final(struct bench_res res[], int res_cnt) +{ + long total_hits = 0, total_drops = 0, total_false_hits = 0, total_ops = 0; + int i; + + for (i = 0; i < res_cnt; i++) { + total_hits += res[i].hits; + total_false_hits += res[i].false_hits; + total_drops += res[i].drops; + } + total_ops = total_hits + total_false_hits + total_drops; + + printf("Summary: %ld false hits of %ld total operations. ", + total_false_hits, total_ops); + printf("Percentage = %2.2f %%\n", + ((float)total_false_hits / total_ops) * 100); +} + void hits_drops_report_progress(int iter, struct bench_res *res, long delta_ns) { double hits_per_sec, drops_per_sec; @@ -132,9 +161,11 @@ static const struct argp_option opts[] = { }; extern struct argp bench_ringbufs_argp; +extern struct argp bench_bloom_filter_map_argp; static const struct argp_child bench_parsers[] = { { &bench_ringbufs_argp, 0, "Ring buffers benchmark", 0 }, + { &bench_bloom_filter_map_argp, 0, "Bloom filter map benchmark", 0 }, {}, }; @@ -323,6 +354,8 @@ extern const struct bench bench_rb_libbpf; 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_bloom_filter_false_positive; static const struct bench *benchs[] = { &bench_count_global, @@ -344,6 +377,8 @@ static const struct bench *benchs[] = { &bench_rb_custom, &bench_pb_libbpf, &bench_pb_custom, + &bench_bloom_filter_map, + &bench_bloom_filter_false_positive, }; static void setup_benchmark() diff --git a/tools/testing/selftests/bpf/bench.h b/tools/testing/selftests/bpf/bench.h index c1f48a473b02..624c6b11501f 100644 --- a/tools/testing/selftests/bpf/bench.h +++ b/tools/testing/selftests/bpf/bench.h @@ -33,6 +33,7 @@ struct env { struct bench_res { long hits; long drops; + long false_hits; }; struct bench { @@ -56,6 +57,8 @@ extern const struct bench *bench; void setup_libbpf(); void hits_drops_report_progress(int iter, struct bench_res *res, long delta_ns); void hits_drops_report_final(struct bench_res res[], int res_cnt); +void false_hits_report_progress(int iter, struct bench_res *res, long delta_ns); +void false_hits_report_final(struct bench_res res[], int res_cnt); static inline __u64 get_time_ns() { struct timespec t; diff --git a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c new file mode 100644 index 000000000000..8b4cd9a52a88 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c @@ -0,0 +1,345 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include +#include "bench.h" +#include "bloom_filter_map.skel.h" +#include "bpf_util.h" + +static struct ctx { + struct bloom_filter_map *skel; + pthread_mutex_t map_done_mtx; + pthread_cond_t map_done; + bool map_prepare_err; + __u32 next_map_idx; +} ctx = { + .map_done_mtx = PTHREAD_MUTEX_INITIALIZER, + .map_done = PTHREAD_COND_INITIALIZER, +}; + +static struct { + __u32 nr_entries; + __u8 nr_hash_funcs; +} args = { + .nr_entries = 1000, + .nr_hash_funcs = 3, +}; + +enum { + ARG_NR_ENTRIES = 3000, + ARG_NR_HASH_FUNCS = 3001, +}; + +static const struct argp_option opts[] = { + { "nr_entries", ARG_NR_ENTRIES, "NR_ENTRIES", 0, + "Set number of entries in the bloom filter map"}, + { "nr_hash_funcs", ARG_NR_HASH_FUNCS, "NR_HASH_FUNCS", 0, + "Set number of hashes in the bloom filter map"}, + {}, +}; + +static error_t parse_arg(int key, char *arg, struct argp_state *state) +{ + switch (key) { + case ARG_NR_ENTRIES: + args.nr_entries = strtol(arg, NULL, 10); + if (args.nr_entries == 0) { + fprintf(stderr, "Invalid nr_entries count."); + argp_usage(state); + } + break; + case ARG_NR_HASH_FUNCS: + args.nr_hash_funcs = strtol(arg, NULL, 10); + if (args.nr_hash_funcs == 0) { + fprintf(stderr, "Cannot specify a bloom filter map with 0 hashes."); + argp_usage(state); + } + break; + default: + return ARGP_ERR_UNKNOWN; + } + + return 0; +} + +/* exported into benchmark runner */ +const struct argp bench_bloom_filter_map_argp = { + .options = opts, + .parser = parse_arg, +}; + +static void validate(void) +{ + if (env.consumer_cnt != 1) { + fprintf(stderr, "bloom filter map benchmark doesn't support multi-consumer!\n"); + exit(1); + } +} + +static inline void trigger_bpf_program(void) +{ + syscall(__NR_getpgid); +} + +static void *producer(void *input) +{ + while (true) + trigger_bpf_program(); + + return NULL; +} + +static void *map_prepare_thread(void *arg) +{ + int err, random_data_fd, bloom_filter_fd, hashmap_fd; + __u64 i, val; + + 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); + + while (true) { + i = __atomic_add_fetch(&ctx.next_map_idx, 1, __ATOMIC_RELAXED); + if (i > args.nr_entries) + break; +again: + err = syscall(__NR_getrandom, &val, sizeof(val), 0); + if (err != sizeof(val)) { + ctx.map_prepare_err = true; + fprintf(stderr, "failed to get random value\n"); + break; + } + err = bpf_map_update_elem(hashmap_fd, &val, &val, BPF_NOEXIST); + if (err) { + if (err != -EEXIST) { + ctx.map_prepare_err = true; + fprintf(stderr, "failed to add elem to hashmap: %d\n", -errno); + break; + } + goto again; + } + + i--; + err = bpf_map_update_elem(random_data_fd, &i, &val, 0); + if (err) { + ctx.map_prepare_err = true; + fprintf(stderr, "failed to add elem to array: %d\n", -errno); + break; + } + + err = bpf_map_update_elem(bloom_filter_fd, NULL, &val, 0); + if (err) { + ctx.map_prepare_err = true; + fprintf(stderr, "failed to add elem to bloom_filter: %d\n", -errno); + break; + } + } + + pthread_mutex_lock(&ctx.map_done_mtx); + pthread_cond_signal(&ctx.map_done); + pthread_mutex_unlock(&ctx.map_done_mtx); + + return NULL; +} + +static void populate_maps(void) +{ + unsigned int nr_cpus = bpf_num_possible_cpus(); + pthread_t map_thread; + int i, err; + + for (i = 0; i < nr_cpus; i++) { + err = pthread_create(&map_thread, NULL, map_prepare_thread, + NULL); + if (err) { + fprintf(stderr, "failed to create pthread: %d\n", -errno); + exit(1); + } + } + + pthread_mutex_lock(&ctx.map_done_mtx); + pthread_cond_wait(&ctx.map_done, &ctx.map_done_mtx); + pthread_mutex_unlock(&ctx.map_done_mtx); + + if (ctx.map_prepare_err) + exit(1); +} + +static struct bloom_filter_map *setup_skeleton(void) +{ + struct bloom_filter_map *skel; + int err; + + setup_libbpf(); + + skel = bloom_filter_map__open(); + if (!skel) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + err = bpf_map__resize(skel->maps.map_random_data, args.nr_entries); + if (err) { + fprintf(stderr, "failed to resize map_random_data\n"); + exit(1); + } + + err = bpf_map__resize(skel->maps.hashmap, args.nr_entries); + if (err) { + fprintf(stderr, "failed to resize hashmap\n"); + exit(1); + } + + err = bpf_map__resize(skel->maps.map_bloom_filter, args.nr_entries); + if (err) { + fprintf(stderr, "failed to resize bloom filter\n"); + exit(1); + } + + err = bpf_map__set_nr_hash_funcs(skel->maps.map_bloom_filter, args.nr_hash_funcs); + if (err) { + fprintf(stderr, "failed to set %u hashes\n", args.nr_hash_funcs); + exit(1); + } + + if (bloom_filter_map__load(skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + + return skel; +} + +static void bloom_filter_map_setup(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(); + + populate_maps(); + + link = bpf_program__attach(ctx.skel->progs.prog_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(); + + 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 measure(struct bench_res *res) +{ + 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; + + if (ctx.skel->bss->error != 0) { + fprintf(stderr, "error (%d) when searching the bloom filter\n", + ctx.skel->bss->error); + 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); + if (err) { + fprintf(stderr, "lookup in the percpu array for 'hits' failed: %d\n", + -errno); + exit(1); + } + + key = ctx.skel->rodata->drop_key; + err = bpf_map_lookup_elem(percpu_array_fd, &key, drops); + if (err) { + fprintf(stderr, "lookup in the percpu array for 'drops' failed: %d\n", + -errno); + exit(1); + } + + key = ctx.skel->rodata->false_hit_key; + err = bpf_map_lookup_elem(percpu_array_fd, &key, false_hits); + if (err) { + fprintf(stderr, "lookup in the percpu array for 'false hits' failed: %d\n", + -errno); + exit(1); + } + + for (i = 0; i < nr_cpus; i++) { + total_hits += bpf_percpu(hits, i); + total_drops += bpf_percpu(drops, i); + total_false_hits += bpf_percpu(false_hits, i); + } + + 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) { + fprintf(stderr, "zeroing the percpu array failed: %d\n", -errno); + exit(1); + } + key = ctx.skel->rodata->drop_key; + err = bpf_map_update_elem(percpu_array_fd, &key, zeroed_values, BPF_ANY); + if (err) { + fprintf(stderr, "zeroing the percpu array failed: %d\n", -errno); + exit(1); + } + key = ctx.skel->rodata->false_hit_key; + err = bpf_map_update_elem(percpu_array_fd, &key, zeroed_values, BPF_ANY); + if (err) { + fprintf(stderr, "zeroing the percpu array failed: %d\n", -errno); + exit(1); + } +} + +static void *consumer(void *input) +{ + return NULL; +} + +const struct bench bench_bloom_filter_map = { + .name = "bloom-filter-map", + .validate = validate, + .setup = 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, + .setup = hashmap_lookup_setup, + .producer_thread = producer, + .consumer_thread = consumer, + .measure = measure, + .report_progress = false_hits_report_progress, + .report_final = false_hits_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 new file mode 100755 index 000000000000..0dbbd85937e3 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/run_bench_bloom_filter_map.sh @@ -0,0 +1,28 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +header "Bloom filter map" +for t in 1 4 8; do +for h in {1..10}; do +subtitle "# threads: $t, # hashes: $h" + for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + printf "%'d entries -\n" $e + printf "\t" + summarize "Total operations: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e bloom-filter-map)" + printf "\t" + summarize_percentage "False positive rate: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e 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 diff --git a/tools/testing/selftests/bpf/benchs/run_bench_ringbufs.sh b/tools/testing/selftests/bpf/benchs/run_bench_ringbufs.sh index af4aa04caba6..ada028aa9007 100755 --- a/tools/testing/selftests/bpf/benchs/run_bench_ringbufs.sh +++ b/tools/testing/selftests/bpf/benchs/run_bench_ringbufs.sh @@ -1,34 +1,8 @@ #!/bin/bash -set -eufo pipefail - -RUN_BENCH="sudo ./bench -w3 -d10 -a" - -function hits() -{ - echo "$*" | sed -E "s/.*hits\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" -} - -function drops() -{ - echo "$*" | sed -E "s/.*drops\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" -} +source ./benchs/run_common.sh -function header() -{ - local len=${#1} - - printf "\n%s\n" "$1" - for i in $(seq 1 $len); do printf '='; done - printf '\n' -} - -function summarize() -{ - bench="$1" - summary=$(echo $2 | tail -n1) - printf "%-20s %s (drops %s)\n" "$bench" "$(hits $summary)" "$(drops $summary)" -} +set -eufo pipefail header "Single-producer, parallel producer" for b in rb-libbpf rb-custom pb-libbpf pb-custom; do diff --git a/tools/testing/selftests/bpf/benchs/run_common.sh b/tools/testing/selftests/bpf/benchs/run_common.sh new file mode 100644 index 000000000000..670f23b037c4 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/run_common.sh @@ -0,0 +1,48 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +RUN_BENCH="sudo ./bench -w3 -d10 -a" + +function header() +{ + local len=${#1} + + printf "\n%s\n" "$1" + for i in $(seq 1 $len); do printf '='; done + printf '\n' +} + +function subtitle() +{ + local len=${#1} + printf "\t%s\n" "$1" +} + +function hits() +{ + echo "$*" | sed -E "s/.*hits\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" +} + +function drops() +{ + echo "$*" | sed -E "s/.*drops\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" +} + +function percentage() +{ + echo "$*" | sed -E "s/.*Percentage\s=\s+([0-9]+\.[0-9]+).*/\1/" +} + +function summarize() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s (drops %s)\n" "$bench" "$(hits $summary)" "$(drops $summary)" +} + +function summarize_percentage() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s%%\n" "$bench" "$(percentage $summary)" +} diff --git a/tools/testing/selftests/bpf/progs/bloom_filter_map.c b/tools/testing/selftests/bpf/progs/bloom_filter_map.c index 5925d8dce4ec..05f9706a5ba6 100644 --- a/tools/testing/selftests/bpf/progs/bloom_filter_map.c +++ b/tools/testing/selftests/bpf/progs/bloom_filter_map.c @@ -1,7 +1,9 @@ // SPDX-License-Identifier: GPL-2.0 /* Copyright (c) 2021 Facebook */ +#include #include +#include #include char _license[] SEC("license") = "GPL"; @@ -35,8 +37,38 @@ struct callback_ctx { struct map_bloom_filter_type *map; }; +/* 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); + __uint(max_entries, 1000); + __type(key, __u64); + __type(value, __u64); +} hashmap SEC(".maps"); + +const __u32 hit_key = 0; +const __u32 drop_key = 1; +const __u32 false_hit_key = 2; + +bool hashmap_use_bloom_filter = true; + int error = 0; +static __always_inline void log_result(__u32 key) +{ + __u64 *count; + + count = bpf_map_lookup_elem(&percpu_array, &key); + if (count) + *count += 1; +} + static __u64 check_elem(struct bpf_map *map, __u32 *key, __u64 *val, struct callback_ctx *data) @@ -49,6 +81,8 @@ check_elem(struct bpf_map *map, __u32 *key, __u64 *val, return 1; /* stop the iteration */ } + log_result(hit_key); + return 0; } @@ -81,3 +115,43 @@ int prog_bloom_filter_inner_map(void *ctx) return 0; } + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter_hashmap_lookup(void *ctx) +{ + __u64 *result; + int i, err; + + union { + __u64 data64; + __u32 data32[2]; + } val; + + for (i = 0; i < 512; i++) { + val.data32[0] = bpf_get_prandom_u32(); + val.data32[1] = bpf_get_prandom_u32(); + + 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); + continue; + } + } + + result = bpf_map_lookup_elem(&hashmap, &val); + if (result) { + log_result(hit_key); + } else { + if (hashmap_use_bloom_filter) + log_result(false_hit_key); + log_result(drop_key); + } + } + + return 0; +} From patchwork Tue Sep 21 21:02:25 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12508811 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=-20.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,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 B273FC433F5 for ; Tue, 21 Sep 2021 21:07:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8F63A61214 for ; Tue, 21 Sep 2021 21:07:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235249AbhIUVJF (ORCPT ); Tue, 21 Sep 2021 17:09:05 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:15012 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235238AbhIUVJB (ORCPT ); Tue, 21 Sep 2021 17:09:01 -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 18LH9Akj029333 for ; Tue, 21 Sep 2021 14:07:32 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type : content-transfer-encoding; s=facebook; bh=EmzeAtdo76ZMDdi5RwkS7uQbxOLfRUYvIGZKKypOvXQ=; b=GmmfjbNzq4W54t+zQdtjjDiikDtXBGI58ClfEe+nCtdCHbZO2jUTY/OVFsYaOHaAllw9 UTp/DPCTLqEEn3YCMv/+dEhM/BvhPQAsJhAku3KoCr2cjSDl75+2GUWV4VqIG+Sc8pJW FatjZL020UENjzaEtRIZ6/cDqQsIAw5vpM0= Received: from maileast.thefacebook.com ([163.114.130.16]) by mx0a-00082601.pphosted.com with ESMTP id 3b7eygkq04-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Tue, 21 Sep 2021 14:07:32 -0700 Received: from intmgw002.25.frc3.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:82::e) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Tue, 21 Sep 2021 14:05:30 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id A69202AC13DB; Tue, 21 Sep 2021 14:05:20 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH v3 bpf-next 5/5] bpf/benchs: Add benchmarks for comparing hashmap lookups with vs. without bloom filter Date: Tue, 21 Sep 2021 14:02:25 -0700 Message-ID: <20210921210225.4095056-6-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20210921210225.4095056-1-joannekoong@fb.com> References: <20210921210225.4095056-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: iTay5s5KwyY_owLcR9QKe8NGWVnhsmrQ X-Proofpoint-ORIG-GUID: iTay5s5KwyY_owLcR9QKe8NGWVnhsmrQ 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-21_06,2021-09-20_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 adultscore=0 clxscore=1015 bulkscore=0 suspectscore=0 mlxscore=0 lowpriorityscore=0 malwarescore=0 priorityscore=1501 impostorscore=0 mlxlogscore=999 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109030001 definitions=main-2109210125 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net This patch adds benchmark tests for comparing the performance of hashmap lookups without the bloom filter vs. hashmap lookups with the bloom filter. Checking the bloom filter first for whether the element exists should overall enable a higher throughput for hashmap lookups, since if the element does not exist in the bloom filter, we can avoid a costly lookup in the hashmap. On average, using 5 hash functions in the bloom filter tended to perform the best across the widest range of different entry sizes. The benchmark results using 5 hash functions (running on 8 threads on a machine with one numa node, and taking the average of 3 runs) were roughly as follows: value_size = 4 bytes - 10k entries: 30% faster 50k entries: 50% faster 100k entries: 55% faster 500k entres: 80% faster 1 million entries: 120% faster 5 million entries: 135% faster value_size = 8 bytes - 10k entries: 35% faster 50k entries: 55% faster 100k entries: 70% faster 500k entres: 110% faster 1 million entries: 215% faster 5 million entries: 215% faster value_size = 16 bytes - 10k entries: 5% slower 50k entries: 25% faster 100k entries: 35% faster 500k entres: 105% faster 1 million entries: 130% faster 5 million entries: 105% faster value_size = 40 bytes - 10k entries: 5% slower 50k entries: 10% faster 100k entries: 20% faster 500k entres: 45% faster 1 million entries: 60% faster 5 million entries: 75% faster Signed-off-by: Joanne Koong --- tools/testing/selftests/bpf/bench.c | 22 ++++++++--- .../bpf/benchs/bench_bloom_filter_map.c | 39 +++++++++++++++++++ .../bpf/benchs/run_bench_bloom_filter_map.sh | 15 +++++++ .../selftests/bpf/benchs/run_common.sh | 12 ++++++ 4 files changed, 83 insertions(+), 5 deletions(-) diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index 0bcbdb4405a3..7da1589a9fe0 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -92,20 +92,21 @@ void hits_drops_report_progress(int iter, struct bench_res *res, long delta_ns) printf("Iter %3d (%7.3lfus): ", iter, (delta_ns - 1000000000) / 1000.0); - printf("hits %8.3lfM/s (%7.3lfM/prod), drops %8.3lfM/s\n", - hits_per_sec, hits_per_prod, drops_per_sec); + printf("hits %8.3lfM/s (%7.3lfM/prod), drops %8.3lfM/s, total operations %8.3lfM/s\n", + hits_per_sec, hits_per_prod, drops_per_sec, hits_per_sec + drops_per_sec); } void hits_drops_report_final(struct bench_res res[], int res_cnt) { int i; - double hits_mean = 0.0, drops_mean = 0.0; - double hits_stddev = 0.0, drops_stddev = 0.0; + double hits_mean = 0.0, drops_mean = 0.0, total_ops_mean = 0.0; + double hits_stddev = 0.0, drops_stddev = 0.0, total_ops_stddev = 0.0; for (i = 0; i < res_cnt; i++) { hits_mean += res[i].hits / 1000000.0 / (0.0 + res_cnt); drops_mean += res[i].drops / 1000000.0 / (0.0 + res_cnt); } + total_ops_mean = hits_mean + drops_mean; if (res_cnt > 1) { for (i = 0; i < res_cnt; i++) { @@ -115,14 +116,21 @@ void hits_drops_report_final(struct bench_res res[], int res_cnt) drops_stddev += (drops_mean - res[i].drops / 1000000.0) * (drops_mean - res[i].drops / 1000000.0) / (res_cnt - 1.0); + total_ops_stddev += (total_ops_mean - + (res[i].hits + res[i].drops) / 1000000.0) * + (total_ops_mean - (res[i].hits + res[i].drops) / 1000000.0) + / (res_cnt - 1.0); } hits_stddev = sqrt(hits_stddev); drops_stddev = sqrt(drops_stddev); + total_ops_stddev = sqrt(total_ops_stddev); } printf("Summary: hits %8.3lf \u00B1 %5.3lfM/s (%7.3lfM/prod), ", hits_mean, hits_stddev, hits_mean / env.producer_cnt); - printf("drops %8.3lf \u00B1 %5.3lfM/s\n", + printf("drops %8.3lf \u00B1 %5.3lfM/s, ", drops_mean, drops_stddev); + printf("total operations %8.3lf \u00B1 %5.3lfM/s\n", + total_ops_mean, total_ops_stddev); } const char *argp_program_version = "benchmark"; @@ -356,6 +364,8 @@ 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_bloom_filter_false_positive; +extern const struct bench bench_hashmap_without_bloom_filter; +extern const struct bench bench_hashmap_with_bloom_filter; static const struct bench *benchs[] = { &bench_count_global, @@ -379,6 +389,8 @@ static const struct bench *benchs[] = { &bench_pb_custom, &bench_bloom_filter_map, &bench_bloom_filter_false_positive, + &bench_hashmap_without_bloom_filter, + &bench_hashmap_with_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 8b4cd9a52a88..7adf80be7292 100644 --- a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +++ b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c @@ -242,6 +242,23 @@ static void hashmap_lookup_setup(void) } } +static void hashmap_no_bloom_filter_setup(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(); + + ctx.skel->data->hashmap_use_bloom_filter = false; + + 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 measure(struct bench_res *res) { long total_hits = 0, total_drops = 0, total_false_hits = 0; @@ -343,3 +360,25 @@ const struct bench bench_bloom_filter_false_positive = { .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, + .setup = hashmap_no_bloom_filter_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_hashmap_with_bloom_filter = { + .name = "hashmap-with-bloom-filter", + .validate = validate, + .setup = hashmap_lookup_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 0dbbd85937e3..239c040b7aaa 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 @@ -26,3 +26,18 @@ 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 +subtitle "# hashes: $h" + for e in 10000 50000 75000 100000 250000 500000 750000 1000000 2500000 5000000; do + printf "%'d entries -\n" $e + printf "\t" + summarize_total "Hashmap without bloom filter: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-without-bloom-filter)" + printf "\t" + summarize_total "Hashmap with bloom filter: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e -p 8 hashmap-with-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 670f23b037c4..9a16be78b180 100644 --- a/tools/testing/selftests/bpf/benchs/run_common.sh +++ b/tools/testing/selftests/bpf/benchs/run_common.sh @@ -33,6 +33,11 @@ function percentage() echo "$*" | sed -E "s/.*Percentage\s=\s+([0-9]+\.[0-9]+).*/\1/" } +function total() +{ + echo "$*" | sed -E "s/.*total operations\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/" +} + function summarize() { bench="$1" @@ -46,3 +51,10 @@ function summarize_percentage() summary=$(echo $2 | tail -n1) printf "%-20s %s%%\n" "$bench" "$(percentage $summary)" } + +function summarize_total() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s\n" "$bench" "$(total $summary)" +}