From patchwork Wed Oct 6 22:20:59 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12540675 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 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2C323C433FE for ; Wed, 6 Oct 2021 22:21:38 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 10FBD60F6D for ; Wed, 6 Oct 2021 22:21:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230236AbhJFWX3 (ORCPT ); Wed, 6 Oct 2021 18:23:29 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:38098 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232093AbhJFWX1 (ORCPT ); Wed, 6 Oct 2021 18:23:27 -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 196K2B72031837 for ; Wed, 6 Oct 2021 15:21:35 -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=zIqCMU8tZ795WjfVpccUB57ruS3PHFhfs2t/8PLpCDg=; b=FYB7BCX9dJYSMwWchSMhJuYBuoLlBrHPVFS4U8AUGeIT3nkapuPjYNZlK8aUEbVvKoiI 35Y186P6/lYeuM+nloK0b/5whfyWoBC6b4hU2nAl3E7ibd6J7Ak8RmtumTTAZb0zvGMF ZsfbCuRD4thkNsgL0WFbJ4vE/MIBXCUDSIU= Received: from maileast.thefacebook.com ([163.114.130.16]) by mx0a-00082601.pphosted.com with ESMTP id 3bhetfawgr-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 06 Oct 2021 15:21:34 -0700 Received: from intmgw001.38.frc1.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:83::5) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 6 Oct 2021 15:21:33 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id 9CC5D345188D; Wed, 6 Oct 2021 15:21:29 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH bpf-next v4 1/5] bpf: Add bitset map with bloom filter capabilities Date: Wed, 6 Oct 2021 15:20:59 -0700 Message-ID: <20211006222103.3631981-2-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211006222103.3631981-1-joannekoong@fb.com> References: <20211006222103.3631981-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: f1Cg-fYPXBdOwHyDylG3UnWVugngH1LT X-Proofpoint-ORIG-GUID: f1Cg-fYPXBdOwHyDylG3UnWVugngH1LT 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-10-06_04,2021-10-06_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 lowpriorityscore=0 bulkscore=0 phishscore=0 clxscore=1015 impostorscore=0 malwarescore=0 suspectscore=0 mlxscore=0 priorityscore=1501 adultscore=0 spamscore=0 mlxlogscore=999 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2110060139 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 kernel-side changes for the implementation of a bitset map with bloom filter capabilities. The bitset map does not have keys, only values since it is a non-associative data type. When the bitset map is created, it must be created with a key_size of 0, and the max_entries value should be the desired size of the bitset, in number of bits. The bitset map supports peek (determining whether a bit is set in the map), push (setting a bit in the map), and pop (clearing a bit in the map) operations. These operations are exposed to userspace applications through the already existing syscalls in the following way: BPF_MAP_UPDATE_ELEM -> bpf_map_push_elem BPF_MAP_LOOKUP_ELEM -> bpf_map_peek_elem BPF_MAP_LOOKUP_AND_DELETE_ELEM -> bpf_map_pop_elem For updates, the user will pass in a NULL key and the index of the bit to set in the bitmap as the value. For lookups, the user will pass in the index of the bit to check as the value. If the bit is set, 0 will be returned, else -ENOENT. For clearing the bit, the user will pass in the index of the bit to clear as the value. Since we need to pass in the index of the bit to set/clear in the bitmap whenever we do a lookup/clear, in the verifier layer this requires us to modify the argument type of a bitset's BPF_FUNC_map_peek_elem and BPF_FUNC_map_pop_elem calls to ARG_PTR_TO_MAP_VALUE; correspondingly, in the syscall layer, we need to copy over the user value so that in bpf_map_peek_elem and bpf_map_pop_elem, we have the specific value to check. The bitset map may be used as an inner map. The bitset map may also have additional bloom filter capabilities. The lower 4 bits of the map_extra flags for the bitset map denote how many hash functions to use. If more than 0 hash functions is specified, the bitset map will operate as a bloom filter where a set of bits are set/checked where the bits are the results from the bloom filter functions. Right now, jhash is function used; in the future, this can be expanded to use map_extra to specify which hash function to use. A few things to additionally please take note of: * If there are any concurrent lookups + updates in the bloom filter, the user is responsible for synchronizing this to ensure no false negative lookups occur. * Deleting an element in the bloom filter map is not supported. * 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 increases the false positive rate of an element being detected in the bloom filter but decreases the speed of a lookup. Signed-off-by: Joanne Koong --- include/linux/bpf.h | 2 + include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 9 ++ kernel/bpf/Makefile | 2 +- kernel/bpf/bitset.c | 256 +++++++++++++++++++++++++++++++++ kernel/bpf/syscall.c | 25 +++- kernel/bpf/verifier.c | 10 +- tools/include/uapi/linux/bpf.h | 9 ++ 8 files changed, 308 insertions(+), 6 deletions(-) create mode 100644 kernel/bpf/bitset.c diff --git a/include/linux/bpf.h b/include/linux/bpf.h index d604c8251d88..eac5bcecc6a7 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -193,6 +193,8 @@ struct bpf_map { struct work_struct work; struct mutex freeze_mutex; u64 writecnt; /* writable mmap cnt; protected by freeze_mutex */ + + u32 map_extra; /* any per-map-type extra fields */ }; static inline bool map_value_has_spin_lock(const struct bpf_map *map) diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h index 9c81724e4b98..85339faeca71 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_BITSET, bitset_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..b40fa1a72a75 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_BITSET, }; /* Note that tracing related programs such as @@ -1252,6 +1253,13 @@ struct bpf_stack_build_id { #define BPF_OBJ_NAME_LEN 16U +/* map_extra flags for bitset maps + * + * The lowest 4 bits are reserved for indicating the number of hash functions. + * If the number of hash functions is greater than 0, the bitset map will + * be used as a bloom filter. + */ + union bpf_attr { struct { /* anonymous struct used by BPF_MAP_CREATE command */ __u32 map_type; /* one of enum bpf_map_type */ @@ -1274,6 +1282,7 @@ union bpf_attr { * struct stored as the * map value */ + __u32 map_extra; /* any per-map-type extra fields */ }; struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */ diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile index 7f33098ca63f..72e381adc708 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 bitset.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/bitset.c b/kernel/bpf/bitset.c new file mode 100644 index 000000000000..a5fca0ebb520 --- /dev/null +++ b/kernel/bpf/bitset.c @@ -0,0 +1,256 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include +#include +#include +#include + +#define BITSET_MAP_CREATE_FLAG_MASK \ + (BPF_F_NUMA_NODE | BPF_F_ZERO_SEED | BPF_F_ACCESS_MASK) + +struct bpf_bitset_map { + struct bpf_map map; + + /* If the number of hash functions at map creation time is greater + * than 0, the bitset map will function as a bloom filter and the fields + * in the struct below will be initialized accordingly. + */ + struct { + u32 nr_hash_funcs; + u32 bitset_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; + } bloom_filter; + + unsigned long bitset[]; +}; + +static inline bool use_bloom_filter(struct bpf_bitset_map *map) +{ + return map->bloom_filter.nr_hash_funcs > 0; +} + +static u32 hash(struct bpf_bitset_map *map, void *value, + u64 value_size, u32 index) +{ + u32 h; + + if (map->bloom_filter.aligned_u32_count) + h = jhash2(value, map->bloom_filter.aligned_u32_count, + map->bloom_filter.hash_seed + index); + else + h = jhash(value, value_size, map->bloom_filter.hash_seed + index); + + return h & map->bloom_filter.bitset_mask; +} + +static int bitset_map_push_elem(struct bpf_map *map, void *value, + u64 flags) +{ + struct bpf_bitset_map *bitset_map = + container_of(map, struct bpf_bitset_map, map); + u32 i, h, bitset_index; + + if (flags != BPF_ANY) + return -EINVAL; + + if (use_bloom_filter(bitset_map)) { + for (i = 0; i < bitset_map->bloom_filter.nr_hash_funcs; i++) { + h = hash(bitset_map, value, map->value_size, i); + set_bit(h, bitset_map->bitset); + } + } else { + bitset_index = *(u32 *)value; + + if (bitset_index >= map->max_entries) + return -EINVAL; + + set_bit(bitset_index, bitset_map->bitset); + } + + return 0; +} + +static int bitset_map_peek_elem(struct bpf_map *map, void *value) +{ + struct bpf_bitset_map *bitset_map = + container_of(map, struct bpf_bitset_map, map); + u32 i, h, bitset_index; + + if (use_bloom_filter(bitset_map)) { + for (i = 0; i < bitset_map->bloom_filter.nr_hash_funcs; i++) { + h = hash(bitset_map, value, map->value_size, i); + if (!test_bit(h, bitset_map->bitset)) + return -ENOENT; + } + } else { + bitset_index = *(u32 *)value; + if (bitset_index >= map->max_entries) + return -EINVAL; + + if (!test_bit(bitset_index, bitset_map->bitset)) + return -ENOENT; + } + + return 0; +} + +static int bitset_map_pop_elem(struct bpf_map *map, void *value) +{ + struct bpf_bitset_map *bitset_map = + container_of(map, struct bpf_bitset_map, map); + u32 bitset_index; + + if (use_bloom_filter(bitset_map)) + return -EOPNOTSUPP; + + bitset_index = *(u32 *)value; + + if (!test_and_clear_bit(bitset_index, bitset_map->bitset)) + return -EINVAL; + + return 0; +} + +static void init_bloom_filter(struct bpf_bitset_map *bitset_map, union bpf_attr *attr, + u32 nr_hash_funcs, u32 bitset_mask) +{ + bitset_map->bloom_filter.nr_hash_funcs = nr_hash_funcs; + bitset_map->bloom_filter.bitset_mask = bitset_mask; + + /* Check whether the value size is u32-aligned */ + if ((attr->value_size & (sizeof(u32) - 1)) == 0) + bitset_map->bloom_filter.aligned_u32_count = + attr->value_size / sizeof(u32); + + if (!(attr->map_flags & BPF_F_ZERO_SEED)) + bitset_map->bloom_filter.hash_seed = get_random_int(); +} + +static struct bpf_map *bitset_map_alloc(union bpf_attr *attr) +{ + int numa_node = bpf_map_attr_numa_node(attr); + u32 bitset_bytes, bitset_mask, nr_hash_funcs; + struct bpf_bitset_map *bitset_map; + u64 nr_bits_roundup_pow2; + + if (!bpf_capable()) + return ERR_PTR(-EPERM); + + if (attr->key_size != 0 || attr->max_entries == 0 || + attr->map_flags & ~BITSET_MAP_CREATE_FLAG_MASK || + !bpf_map_flags_access_ok(attr->map_flags)) + return ERR_PTR(-EINVAL); + + if (attr->map_extra & ~0xF) + return ERR_PTR(-EINVAL); + + /* The lower 4 bits of map_extra specify the number of hash functions */ + nr_hash_funcs = attr->map_extra & 0xF; + + if (!nr_hash_funcs) { + if (attr->value_size != sizeof(u32)) + return ERR_PTR(-EINVAL); + + /* Round up to the size of an unsigned long since a bit gets set + * at the granularity of an unsigned long. + */ + bitset_bytes = roundup(BITS_TO_BYTES(attr->max_entries), + sizeof(unsigned long)); + } else { + /* If the number of hash functions > 0, then the map will + * function as a bloom filter + */ + + if (attr->value_size == 0) + return ERR_PTR(-EINVAL); + + /* We round up the size of the bitset to the nearest power of two to + * enable more efficient hashing using a bitmask. The bitmask will be + * the bitset size - 1. + */ + nr_bits_roundup_pow2 = roundup_pow_of_two(attr->max_entries); + bitset_mask = nr_bits_roundup_pow2 - 1; + + bitset_bytes = roundup(BITS_TO_BYTES(nr_bits_roundup_pow2), + sizeof(unsigned long)); + } + + bitset_map = bpf_map_area_alloc(sizeof(*bitset_map) + bitset_bytes, + numa_node); + if (!bitset_map) + return ERR_PTR(-ENOMEM); + + bpf_map_init_from_attr(&bitset_map->map, attr); + + if (nr_hash_funcs) + init_bloom_filter(bitset_map, attr, nr_hash_funcs, bitset_mask); + + return &bitset_map->map; +} + +static void bitset_map_free(struct bpf_map *map) +{ + struct bpf_bitset_map *bitset_map = + container_of(map, struct bpf_bitset_map, map); + + bpf_map_area_free(bitset_map); +} + +static void *bitset_map_lookup_elem(struct bpf_map *map, void *key) +{ + /* The eBPF program should use map_peek_elem instead */ + return ERR_PTR(-EINVAL); +} + +static int bitset_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 bitset_map_delete_elem(struct bpf_map *map, void *key) +{ + return -EOPNOTSUPP; +} + +static int bitset_map_get_next_key(struct bpf_map *map, void *key, + void *next_key) +{ + return -EOPNOTSUPP; +} + +static int bitset_map_check_btf(const struct bpf_map *map, const struct btf *btf, + const struct btf_type *key_type, + const struct btf_type *value_type) +{ + /* Bitset maps are keyless */ + return btf_type_is_void(key_type) ? 0 : -EINVAL; +} + +static int bpf_bitset_map_btf_id; +const struct bpf_map_ops bitset_map_ops = { + .map_meta_equal = bpf_map_meta_equal, + .map_alloc = bitset_map_alloc, + .map_free = bitset_map_free, + .map_push_elem = bitset_map_push_elem, + .map_peek_elem = bitset_map_peek_elem, + .map_pop_elem = bitset_map_pop_elem, + .map_lookup_elem = bitset_map_lookup_elem, + .map_update_elem = bitset_map_update_elem, + .map_delete_elem = bitset_map_delete_elem, + .map_get_next_key = bitset_map_get_next_key, + .map_check_btf = bitset_map_check_btf, + .map_btf_name = "bpf_bitset_map", + .map_btf_id = &bpf_bitset_map_btf_id, +}; diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index 4e50c0bfdb7d..7726774d972a 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_BITSET) { 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_BITSET) { 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" */ @@ -348,6 +350,7 @@ void bpf_map_init_from_attr(struct bpf_map *map, union bpf_attr *attr) map->max_entries = attr->max_entries; map->map_flags = bpf_map_flags_retain_permanent(attr->map_flags); map->numa_node = bpf_map_attr_numa_node(attr); + map->map_extra = attr->map_extra; } static int bpf_map_alloc_id(struct bpf_map *map) @@ -553,6 +556,7 @@ static void bpf_map_show_fdinfo(struct seq_file *m, struct file *filp) "value_size:\t%u\n" "max_entries:\t%u\n" "map_flags:\t%#x\n" + "map_extra:\t%#x\n" "memlock:\t%lu\n" "map_id:\t%u\n" "frozen:\t%u\n", @@ -561,6 +565,7 @@ static void bpf_map_show_fdinfo(struct seq_file *m, struct file *filp) map->value_size, map->max_entries, map->map_flags, + map->map_extra, bpf_map_memory_footprint(map), map->id, READ_ONCE(map->frozen)); @@ -810,7 +815,7 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf, return ret; } -#define BPF_MAP_CREATE_LAST_FIELD btf_vmlinux_value_type_id +#define BPF_MAP_CREATE_LAST_FIELD map_extra /* called via syscall */ static int map_create(union bpf_attr *attr) { @@ -1080,6 +1085,14 @@ static int map_lookup_elem(union bpf_attr *attr) if (!value) goto free_key; + if (map->map_type == BPF_MAP_TYPE_BITSET) { + 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; @@ -1549,6 +1562,12 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) if (map->map_type == BPF_MAP_TYPE_QUEUE || map->map_type == BPF_MAP_TYPE_STACK) { err = map->ops->map_pop_elem(map, value); + } else if (map->map_type == BPF_MAP_TYPE_BITSET) { + if (copy_from_user(value, uvalue, value_size)) + err = -EFAULT; + else + err = map->ops->map_pop_elem(map, value); + goto free_value; } else if (map->map_type == BPF_MAP_TYPE_HASH || map->map_type == BPF_MAP_TYPE_PERCPU_HASH || map->map_type == BPF_MAP_TYPE_LRU_HASH || diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 20900a1bac12..731cc90b6e98 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5007,7 +5007,11 @@ static int resolve_map_arg_type(struct bpf_verifier_env *env, return -EINVAL; } break; - + case BPF_MAP_TYPE_BITSET: + if (meta->func_id == BPF_FUNC_map_peek_elem || + meta->func_id == BPF_FUNC_map_pop_elem) + *arg_type = ARG_PTR_TO_MAP_VALUE; + break; default: break; } @@ -5562,6 +5566,7 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, break; case BPF_MAP_TYPE_QUEUE: case BPF_MAP_TYPE_STACK: + case BPF_MAP_TYPE_BITSET: if (func_id != BPF_FUNC_map_peek_elem && func_id != BPF_FUNC_map_pop_elem && func_id != BPF_FUNC_map_push_elem) @@ -5653,7 +5658,8 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env, 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) + map->map_type != BPF_MAP_TYPE_STACK && + map->map_type != BPF_MAP_TYPE_BITSET) goto error; break; case BPF_FUNC_sk_storage_get: diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index 6fc59d61937a..b40fa1a72a75 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_BITSET, }; /* Note that tracing related programs such as @@ -1252,6 +1253,13 @@ struct bpf_stack_build_id { #define BPF_OBJ_NAME_LEN 16U +/* map_extra flags for bitset maps + * + * The lowest 4 bits are reserved for indicating the number of hash functions. + * If the number of hash functions is greater than 0, the bitset map will + * be used as a bloom filter. + */ + union bpf_attr { struct { /* anonymous struct used by BPF_MAP_CREATE command */ __u32 map_type; /* one of enum bpf_map_type */ @@ -1274,6 +1282,7 @@ union bpf_attr { * struct stored as the * map value */ + __u32 map_extra; /* any per-map-type extra fields */ }; struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */ From patchwork Wed Oct 6 22:21:00 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12540671 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 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E3839C433EF for ; Wed, 6 Oct 2021 22:21:32 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C352C610A0 for ; Wed, 6 Oct 2021 22:21:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230292AbhJFWXY (ORCPT ); Wed, 6 Oct 2021 18:23:24 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:37920 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S230236AbhJFWXY (ORCPT ); Wed, 6 Oct 2021 18:23:24 -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 196M3cmV027614 for ; Wed, 6 Oct 2021 15:21:31 -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=tpvrmC9X0utdZCbHTTYba8Xu1YZ66mzNHmJWWZpyfak=; b=JfjWvooHVbDpRSdoUt/BkSPg9vrNm+eVs37HDo/nNY1F2R+vDltcxgLQN+Q0zTIkwN5D DYhQvD0OrjWq+ZRhU+ZRm4E7sB0U2Bevxq6T/hR0QKd1AOsSHD14o9r98cLfo2EPO97v 3ylaWU8FaJuZqtck8Cxyad4SFwbPLMHf0bw= Received: from maileast.thefacebook.com ([163.114.130.16]) by m0001303.ppops.net with ESMTP id 3bhfn52fa3-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 06 Oct 2021 15:21:31 -0700 Received: from intmgw001.37.frc1.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:83::4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 6 Oct 2021 15:21:30 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id B3230345188F; Wed, 6 Oct 2021 15:21:29 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH bpf-next v4 2/5] libbpf: Add "map_extra" as a per-map-type extra flag Date: Wed, 6 Oct 2021 15:21:00 -0700 Message-ID: <20211006222103.3631981-3-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211006222103.3631981-1-joannekoong@fb.com> References: <20211006222103.3631981-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: zbXo7tx_ot9QlfdsnPnFXsQjI2lOHLC_ X-Proofpoint-ORIG-GUID: zbXo7tx_ot9QlfdsnPnFXsQjI2lOHLC_ 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-10-06_04,2021-10-06_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 lowpriorityscore=0 spamscore=0 phishscore=0 adultscore=0 mlxscore=0 suspectscore=0 bulkscore=0 clxscore=1015 mlxlogscore=999 priorityscore=1501 malwarescore=0 impostorscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2110060139 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 for supporting a per-map-type "map_extra" field, whose definition will be idiosyncratic depending on map type. For example, for the bitset map, the lower 4 bits of map_extra is used to denote the number of hash functions. Signed-off-by: Joanne Koong --- include/uapi/linux/bpf.h | 1 + tools/include/uapi/linux/bpf.h | 1 + tools/lib/bpf/bpf.c | 1 + tools/lib/bpf/bpf.h | 1 + tools/lib/bpf/bpf_helpers.h | 1 + tools/lib/bpf/libbpf.c | 25 ++++++++++++++++++++++++- tools/lib/bpf/libbpf.h | 4 ++++ tools/lib/bpf/libbpf.map | 2 ++ tools/lib/bpf/libbpf_internal.h | 4 +++- 9 files changed, 38 insertions(+), 2 deletions(-) diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index b40fa1a72a75..a6f225e9c95a 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -5639,6 +5639,7 @@ struct bpf_map_info { __u32 btf_id; __u32 btf_key_type_id; __u32 btf_value_type_id; + __u32 map_extra; } __attribute__((aligned(8))); struct bpf_btf_info { diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index b40fa1a72a75..a6f225e9c95a 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -5639,6 +5639,7 @@ struct bpf_map_info { __u32 btf_id; __u32 btf_key_type_id; __u32 btf_value_type_id; + __u32 map_extra; } __attribute__((aligned(8))); struct bpf_btf_info { diff --git a/tools/lib/bpf/bpf.c b/tools/lib/bpf/bpf.c index 7d1741ceaa32..41e3e85e7789 100644 --- a/tools/lib/bpf/bpf.c +++ b/tools/lib/bpf/bpf.c @@ -97,6 +97,7 @@ int bpf_create_map_xattr(const struct bpf_create_map_attr *create_attr) attr.btf_key_type_id = create_attr->btf_key_type_id; attr.btf_value_type_id = create_attr->btf_value_type_id; attr.map_ifindex = create_attr->map_ifindex; + attr.map_extra = create_attr->map_extra; if (attr.map_type == BPF_MAP_TYPE_STRUCT_OPS) attr.btf_vmlinux_value_type_id = create_attr->btf_vmlinux_value_type_id; diff --git a/tools/lib/bpf/bpf.h b/tools/lib/bpf/bpf.h index 6fffb3cdf39b..c4049f2d63cc 100644 --- a/tools/lib/bpf/bpf.h +++ b/tools/lib/bpf/bpf.h @@ -50,6 +50,7 @@ struct bpf_create_map_attr { __u32 inner_map_fd; __u32 btf_vmlinux_value_type_id; }; + __u32 map_extra; }; LIBBPF_API int diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h index 963b1060d944..bce5a0090f3f 100644 --- a/tools/lib/bpf/bpf_helpers.h +++ b/tools/lib/bpf/bpf_helpers.h @@ -133,6 +133,7 @@ struct bpf_map_def { unsigned int value_size; unsigned int max_entries; unsigned int map_flags; + unsigned int map_extra; }; enum libbpf_pin_type { diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c index ed313fd491bd..12a9ecd45a78 100644 --- a/tools/lib/bpf/libbpf.c +++ b/tools/lib/bpf/libbpf.c @@ -2274,6 +2274,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, "map_extra") == 0) { + if (!get_map_field_int(map_name, btf, m, &map_def->map_extra)) + return -EINVAL; + map_def->parts |= MAP_DEF_MAP_EXTRA; } else { if (strict) { pr_warn("map '%s': unknown field '%s'.\n", map_name, name); @@ -2298,6 +2302,7 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *def map->def.value_size = def->value_size; map->def.max_entries = def->max_entries; map->def.map_flags = def->map_flags; + map->def.map_extra = def->map_extra; map->numa_node = def->numa_node; map->btf_key_type_id = def->key_type_id; @@ -2322,6 +2327,8 @@ static void fill_map_from_def(struct bpf_map *map, const struct btf_map_def *def pr_debug("map '%s': found max_entries = %u.\n", map->name, def->max_entries); if (def->parts & MAP_DEF_MAP_FLAGS) pr_debug("map '%s': found map_flags = %u.\n", map->name, def->map_flags); + if (def->parts & MAP_DEF_MAP_EXTRA) + pr_debug("map '%s': found map_extra = %u.\n", map->name, def->map_extra); if (def->parts & MAP_DEF_PINNING) pr_debug("map '%s': found pinning = %u.\n", map->name, def->pinning); if (def->parts & MAP_DEF_NUMA_NODE) @@ -4017,6 +4024,7 @@ int bpf_map__reuse_fd(struct bpf_map *map, int fd) map->def.value_size = info.value_size; map->def.max_entries = info.max_entries; map->def.map_flags = info.map_flags; + map->def.map_extra = info.map_extra; map->btf_key_type_id = info.btf_key_type_id; map->btf_value_type_id = info.btf_value_type_id; map->reused = true; @@ -4534,7 +4542,8 @@ static bool map_is_reuse_compat(const struct bpf_map *map, int map_fd) map_info.key_size == map->def.key_size && map_info.value_size == map->def.value_size && map_info.max_entries == map->def.max_entries && - map_info.map_flags == map->def.map_flags); + map_info.map_flags == map->def.map_flags && + map_info.map_extra == map->def.map_extra); } static int @@ -4631,6 +4640,7 @@ static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, b create_attr.key_size = def->key_size; create_attr.value_size = def->value_size; create_attr.numa_node = map->numa_node; + create_attr.map_extra = def->map_extra; if (def->type == BPF_MAP_TYPE_PERF_EVENT_ARRAY && !def->max_entries) { int nr_cpus; @@ -8637,6 +8647,19 @@ int bpf_map__set_map_flags(struct bpf_map *map, __u32 flags) return 0; } +__u32 bpf_map__map_extra(const struct bpf_map *map) +{ + return map->def.map_extra; +} + +int bpf_map__set_map_extra(struct bpf_map *map, __u32 map_extra) +{ + if (map->fd >= 0) + return libbpf_err(-EBUSY); + map->def.map_extra = map_extra; + return 0; +} + __u32 bpf_map__numa_node(const struct bpf_map *map) { return map->numa_node; diff --git a/tools/lib/bpf/libbpf.h b/tools/lib/bpf/libbpf.h index 89ca9c83ed4e..55e8dfe6f3e1 100644 --- a/tools/lib/bpf/libbpf.h +++ b/tools/lib/bpf/libbpf.h @@ -486,6 +486,7 @@ struct bpf_map_def { unsigned int value_size; unsigned int max_entries; unsigned int map_flags; + unsigned int map_extra; }; /** @@ -562,6 +563,9 @@ 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); +/* get/set map map_extra flags */ +LIBBPF_API __u32 bpf_map__map_extra(const struct bpf_map *map); +LIBBPF_API int bpf_map__set_map_extra(struct bpf_map *map, __u32 map_extra); 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 f270d25e4af3..308378b3f20b 100644 --- a/tools/lib/bpf/libbpf.map +++ b/tools/lib/bpf/libbpf.map @@ -395,4 +395,6 @@ LIBBPF_0.6.0 { bpf_object__prev_program; btf__add_btf; btf__add_tag; + bpf_map__map_extra; + bpf_map__set_map_extra; } LIBBPF_0.5.0; diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_internal.h index f7fd3944d46d..188db854d9c2 100644 --- a/tools/lib/bpf/libbpf_internal.h +++ b/tools/lib/bpf/libbpf_internal.h @@ -193,8 +193,9 @@ enum map_def_parts { MAP_DEF_NUMA_NODE = 0x080, MAP_DEF_PINNING = 0x100, MAP_DEF_INNER_MAP = 0x200, + MAP_DEF_MAP_EXTRA = 0x400, - MAP_DEF_ALL = 0x3ff, /* combination of all above */ + MAP_DEF_ALL = 0x7ff, /* combination of all above */ }; struct btf_map_def { @@ -208,6 +209,7 @@ struct btf_map_def { __u32 map_flags; __u32 numa_node; __u32 pinning; + __u32 map_extra; }; int parse_btf_map_def(const char *map_name, struct btf *btf, From patchwork Wed Oct 6 22:21:01 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12540677 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 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 13F68C433EF for ; Wed, 6 Oct 2021 22:21:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F223660F41 for ; Wed, 6 Oct 2021 22:21:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239454AbhJFWXa (ORCPT ); Wed, 6 Oct 2021 18:23:30 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:62484 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239547AbhJFWX3 (ORCPT ); Wed, 6 Oct 2021 18:23:29 -0400 Received: from pps.filterd (m0148461.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 196Ksxit023994 for ; Wed, 6 Oct 2021 15:21:37 -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=anDzD/iblmNmbfeM1SYA2DgeBKoMdZK8weQQt8f3O8U=; b=W8CAFySa9HLL96FR+u77D+2bn3YnJVu4FEW+PaKN/Qt27MXyHtuH2+TDFWMzz4RDxZ5v qgykhKn7bLnSs7zqByOP/DlGXsk+iUj5jDJw/8o94U9Fulh6hQz3+/18U4SzRoza9RKa mpHU6r0uIw3PqSyGPJjgUfb7IRB9GmIlFHI= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3bhk8eghgv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 06 Oct 2021 15:21:36 -0700 Received: from intmgw002.25.frc3.facebook.com (2620:10d:c085:208::11) 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; Wed, 6 Oct 2021 15:21:35 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id BD5143451891; Wed, 6 Oct 2021 15:21:29 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH bpf-next v4 3/5] selftests/bpf: Add bitset map test cases Date: Wed, 6 Oct 2021 15:21:01 -0700 Message-ID: <20211006222103.3631981-4-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211006222103.3631981-1-joannekoong@fb.com> References: <20211006222103.3631981-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: xS6XNt1b610lGTu-8sllD1OaiHyts9zZ X-Proofpoint-ORIG-GUID: xS6XNt1b610lGTu-8sllD1OaiHyts9zZ 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-10-06_04,2021-10-06_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 mlxscore=0 bulkscore=0 spamscore=0 impostorscore=0 suspectscore=0 phishscore=0 priorityscore=1501 lowpriorityscore=0 mlxlogscore=999 malwarescore=0 adultscore=0 clxscore=1015 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2110060139 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 bitset maps. They include tests checking against invalid operations by userspace, tests for using the bitset map as an inner map, a bpf program that queries the bitset map for values added by userspace, and well as tests for the bloom filter capabilities of the bitset map. Signed-off-by: Joanne Koong --- .../selftests/bpf/prog_tests/bitset_map.c | 279 ++++++++++++++++++ .../testing/selftests/bpf/progs/bitset_map.c | 115 ++++++++ 2 files changed, 394 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/bitset_map.c create mode 100644 tools/testing/selftests/bpf/progs/bitset_map.c diff --git a/tools/testing/selftests/bpf/prog_tests/bitset_map.c b/tools/testing/selftests/bpf/prog_tests/bitset_map.c new file mode 100644 index 000000000000..8929cc598b9d --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/bitset_map.c @@ -0,0 +1,279 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include "bitset_map.skel.h" + +static void test_bitset_map_fail(bool bloom_filter) +{ + struct bpf_create_map_attr xattr = { + .name = "bitset_map", + .map_type = BPF_MAP_TYPE_BITSET, + .max_entries = 100, + .value_size = bloom_filter ? 11 : sizeof(__u32), + .map_extra = bloom_filter ? 5 : 0, + }; + __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 bitset 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 bitset invalid value size 0")) + close(fd); + if (!bloom_filter) { + /* For bitset maps that are not bloom filters, the value size must + * be a __u32. + */ + xattr.value_size = sizeof(__u64); + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_LT(fd, 0, "bpf_create_map bitset invalid value size u64")) + close(fd); + } + xattr.value_size = bloom_filter ? 11 : sizeof(__u32); + + /* Invalid max entries size */ + xattr.max_entries = 0; + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_LT(fd, 0, "bpf_create_map bitset invalid max entries size")) + close(fd); + xattr.max_entries = 100; + + /* bitset 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 bitset invalid flags")) + close(fd); + xattr.map_flags = 0; + + fd = bpf_create_map_xattr(&xattr); + if (!ASSERT_GE(fd, 0, "bpf_create_map bitset")) + return; + + /* Test invalid flags */ + err = bpf_map_update_elem(fd, NULL, &value, -1); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bitset invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, BPF_EXIST); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bitset invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, BPF_F_LOCK); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bitset invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, BPF_NOEXIST); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bitset invalid flags"); + + err = bpf_map_update_elem(fd, NULL, &value, 10000); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bitset invalid flags"); + + if (bloom_filter) { + err = bpf_map_update_elem(fd, NULL, &value, 0); + ASSERT_OK(err, "bpf_map_update_elem bitset invalid flags"); + + /* Clearing a bit is not allowed */ + err = bpf_map_lookup_and_delete_elem(fd, NULL, &value); + ASSERT_EQ(err, -EOPNOTSUPP, "bpf_map_lookup_and_delete invalid"); + } else { + /* Try clearing a bit that wasn't set */ + err = bpf_map_lookup_and_delete_elem(fd, NULL, &value); + ASSERT_EQ(err, -EINVAL, "bpf_map_lookup_and_delete invalid bit"); + + /* Try setting a bit that is outside the bitset range */ + value = xattr.max_entries; + err = bpf_map_update_elem(fd, NULL, &value, 0); + ASSERT_EQ(err, -EINVAL, "bpf_map_update_elem bitset out of range"); + } + + /* bpf_map_delete is not supported. Only use bpf_map_lookup_and_delete */ + err = bpf_map_delete_elem(fd, &value); + ASSERT_EQ(err, -EINVAL, "bpf_map_delete_elem"); + + close(fd); +} + +static void test_bitset_map_clear(void) +{ + int fd, err; + __u32 val; + + fd = bpf_create_map(BPF_MAP_TYPE_BITSET, 0, sizeof(__u32), 10, 0); + if (!ASSERT_GE(fd, 0, "bpf_create_map")) + return; + + val = 3; + err = bpf_map_update_elem(fd, NULL, &val, 0); + if (!ASSERT_OK(err, "Set bit in bitmap")) + goto done; + + err = bpf_map_lookup_elem(fd, NULL, &val); + if (!ASSERT_OK(err, "Check bit in bitmap")) + goto done; + + err = bpf_map_lookup_and_delete_elem(fd, NULL, &val); + if (!ASSERT_OK(err, "Clear bit in bitmap")) + goto done; + + err = bpf_map_lookup_elem(fd, NULL, &val); + if (!ASSERT_EQ(err, -ENOENT, "Check cleared bit in bitmap")) + goto done; + +done: + close(fd); +} + +static void bitset_map(struct bitset_map *skel, struct bpf_program *prog) +{ + struct bpf_link *link; + + link = bpf_program__attach(prog); + if (!ASSERT_OK_PTR(link, "link")) + return; + + syscall(SYS_getpgid); + + ASSERT_EQ(skel->bss->error, 0, "error"); + + bpf_link__destroy(link); +} + +static void bitset_inner_map(struct bitset_map *skel, const __u32 *rand_vals, + __u32 nr_rand_vals) +{ + int outer_map_fd, inner_map_fd, err, i, key = 0; + struct bpf_create_map_attr xattr = { + .name = "bitset_inner_map", + .map_type = BPF_MAP_TYPE_BITSET, + .value_size = sizeof(__u32), + .max_entries = 1 << 16, + }; + struct bpf_link *link; + + /* Create a bitset 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 bitset map as inner map")) + return; + + for (i = 0; i < nr_rand_vals; i++) { + err = bpf_map_update_elem(inner_map_fd, NULL, rand_vals + i, BPF_ANY); + if (!ASSERT_OK(err, "Add random value to inner_map_fd")) + goto done; + } + + /* Add the bitset map to the outer map */ + outer_map_fd = bpf_map__fd(skel->maps.outer_map); + err = bpf_map_update_elem(outer_map_fd, &key, &inner_map_fd, BPF_ANY); + if (!ASSERT_OK(err, "Add bitset map to outer map")) + goto done; + + /* Attach the bitset_inner_map prog */ + link = bpf_program__attach(skel->progs.prog_bitset_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 bitset map can be deleted */ + err = bpf_map_delete_elem(outer_map_fd, &key); + ASSERT_OK(err, "Delete inner bitset map"); + +done: + close(inner_map_fd); +} + +static int setup_bitset_progs(struct bitset_map **out_skel, __u32 **out_rand_vals, + __u32 *out_nr_rand_vals) +{ + int random_data_fd, bitset_fd, bloom_filter_fd; + struct bitset_map *skel; + __u32 *rand_vals = NULL; + __u32 map_size; + __u32 val; + int err, i; + + /* Set up a bitset map skeleton */ + skel = bitset_map__open_and_load(); + if (!ASSERT_OK_PTR(skel, "bitset_map__open_and_load")) + return -EINVAL; + + /* Set up rand_vals */ + map_size = bpf_map__max_entries(skel->maps.map_random_data); + rand_vals = malloc(sizeof(*rand_vals) * map_size); + if (!rand_vals) { + err = -ENOMEM; + goto error; + } + + /* Generate random values and populate both skeletons */ + random_data_fd = bpf_map__fd(skel->maps.map_random_data); + bitset_fd = bpf_map__fd(skel->maps.map_bitset); + bloom_filter_fd = bpf_map__fd(skel->maps.map_bloom_filter); + for (i = 0; i < map_size; i++) { + val = rand(); + + err = bpf_map_update_elem(random_data_fd, &i, &val, BPF_ANY); + if (!ASSERT_OK(err, "Add random value to map_random_data")) + goto error; + + err = bpf_map_update_elem(bloom_filter_fd, NULL, &val, BPF_ANY); + if (!ASSERT_OK(err, "Add random value to map_bloom_filter")) + goto error; + + /* Take the lower 16 bits */ + val &= 0xFFFF; + + rand_vals[i] = val; + + err = bpf_map_update_elem(bitset_fd, NULL, &val, BPF_ANY); + if (!ASSERT_OK(err, "Add random value to map_bitset")) + goto error; + } + + *out_skel = skel; + *out_rand_vals = rand_vals; + *out_nr_rand_vals = map_size; + + return 0; + +error: + bitset_map__destroy(skel); + if (rand_vals) + free(rand_vals); + return err; +} + +void test_bitset_map(void) +{ + __u32 *rand_vals, nr_rand_vals; + struct bitset_map *skel; + int err; + + test_bitset_map_fail(false); + test_bitset_map_fail(true); + + test_bitset_map_clear(); + + err = setup_bitset_progs(&skel, &rand_vals, &nr_rand_vals); + if (err) + return; + + bitset_inner_map(skel, rand_vals, nr_rand_vals); + free(rand_vals); + + bitset_map(skel, skel->progs.prog_bitset); + bitset_map(skel, skel->progs.prog_bloom_filter); + + bitset_map__destroy(skel); +} diff --git a/tools/testing/selftests/bpf/progs/bitset_map.c b/tools/testing/selftests/bpf/progs/bitset_map.c new file mode 100644 index 000000000000..c284ade37db1 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/bitset_map.c @@ -0,0 +1,115 @@ +// 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, __u32); +} map_random_data SEC(".maps"); + +struct map_bitset_type { + __uint(type, BPF_MAP_TYPE_BITSET); + __uint(value_size, sizeof(__u32)); + __uint(max_entries, 1 << 16); +} map_bitset SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_BITSET); + __uint(value_size, sizeof(__u32)); + __uint(max_entries, 10000); + __uint(map_extra, 5); +} 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_bitset_type); +} outer_map SEC(".maps"); + +struct callback_ctx { + struct bpf_map *map; +}; + +int error = 0; + +static __u64 +check_bit(struct bpf_map *map, __u32 *key, __u32 *val, + struct callback_ctx *data) +{ + __u32 index = *val & 0xFFFF; + int err; + + err = bpf_map_peek_elem(data->map, &index); + if (err) { + error |= 1; + return 1; /* stop the iteration */ + } + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bitset(void *ctx) +{ + struct callback_ctx data; + + data.map = (struct bpf_map *)&map_bitset; + bpf_for_each_map_elem(&map_random_data, check_bit, &data, 0); + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bitset_inner_map(void *ctx) +{ + struct bpf_map *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_bit, &data, 0); + + return 0; +} + +static __u64 +check_elem(struct bpf_map *map, __u32 *key, __u32 *val, + struct callback_ctx *data) +{ + int err; + + err = bpf_map_peek_elem(data->map, val); + if (err) { + error |= 3; + return 1; /* stop the iteration */ + } + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter(void *ctx) +{ + struct callback_ctx data; + + data.map = (struct bpf_map *)&map_bloom_filter; + bpf_for_each_map_elem(&map_random_data, check_elem, &data, 0); + + return 0; +} From patchwork Wed Oct 6 22:21:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12540679 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 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 95CDCC4332F for ; Wed, 6 Oct 2021 22:21:38 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 797CF60F44 for ; Wed, 6 Oct 2021 22:21:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232093AbhJFWXa (ORCPT ); Wed, 6 Oct 2021 18:23:30 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:50874 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239454AbhJFWX3 (ORCPT ); Wed, 6 Oct 2021 18:23:29 -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 196K30f1007897 for ; Wed, 6 Oct 2021 15:21: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=+tdyaVXCZfvr8PslnsthQoFtEXfiETh44oegeoGrKXU=; b=TMERuqTr+U+ycOGQNU1QU9TOZAeI1OH2Wu8/V7Eu++znx5LjiszvtCgYtCAZ+KmDBd8i 7FSyCdh7Ur7Bx5R2ljiv02J79DtHypR/XFAr+Ge6LSQ/99ZWgsOGwIZdLEDM+6KkLLOk tfCI6YLeCUeMg/PaHholcC+vt/5cyaR3db8= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3bhc1bmnva-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 06 Oct 2021 15:21:36 -0700 Received: from intmgw001.25.frc3.facebook.com (2620:10d:c085:208::11) by mail.thefacebook.com (2620:10d:c085:21d::4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.14; Wed, 6 Oct 2021 15:21:34 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id D3B6B3451894; Wed, 6 Oct 2021 15:21:29 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH bpf-next v4 4/5] bpf/benchs: Add benchmark tests for bloom filter throughput + false positive Date: Wed, 6 Oct 2021 15:21:02 -0700 Message-ID: <20211006222103.3631981-5-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211006222103.3631981-1-joannekoong@fb.com> References: <20211006222103.3631981-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-ORIG-GUID: aJfIarBLqzmuo5RdaCACWyRr7b9Y2wI5 X-Proofpoint-GUID: aJfIarBLqzmuo5RdaCACWyRr7b9Y2wI5 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-10-06_04,2021-10-06_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 malwarescore=0 priorityscore=1501 adultscore=0 spamscore=0 impostorscore=0 mlxscore=0 phishscore=0 clxscore=1015 mlxlogscore=999 bulkscore=0 lowpriorityscore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2110060139 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 (for lookups + updates) and the false positive rate of bloom filter lookups, as well as some minor refactoring of the bash script for running the benchmarks. These benchmarks show that as the number of hash functions increases, the throughput and the false positive rate of the bloom filter decreases. From the benchmark data, the approximate average false-positive rates for 8-byte values 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 | 6 +- tools/testing/selftests/bpf/bench.c | 37 ++ tools/testing/selftests/bpf/bench.h | 3 + .../bpf/benchs/bench_bloom_filter_map.c | 411 ++++++++++++++++++ .../bpf/benchs/run_bench_bloom_filter_map.sh | 28 ++ .../bpf/benchs/run_bench_ringbufs.sh | 30 +- .../selftests/bpf/benchs/run_common.sh | 48 ++ tools/testing/selftests/bpf/bpf_util.h | 11 + .../selftests/bpf/progs/bloom_filter_bench.c | 146 +++++++ 9 files changed, 690 insertions(+), 30 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 create mode 100644 tools/testing/selftests/bpf/progs/bloom_filter_bench.c diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index c5c9a9f50d8d..66e1ad17acef 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -517,18 +517,20 @@ $(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 \ $(OUTPUT)/perfbuf_bench.skel.h +$(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.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..e836bacd6f9d 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,9 @@ 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_lookup; +extern const struct bench bench_bloom_filter_update; +extern const struct bench bench_bloom_filter_false_positive; static const struct bench *benchs[] = { &bench_count_global, @@ -344,6 +378,9 @@ static const struct bench *benchs[] = { &bench_rb_custom, &bench_pb_libbpf, &bench_pb_custom, + &bench_bloom_filter_lookup, + &bench_bloom_filter_update, + &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..25d6b8179c8e --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c @@ -0,0 +1,411 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include +#include "bench.h" +#include "bloom_filter_bench.skel.h" +#include "bpf_util.h" + +static struct ctx { + struct bloom_filter_bench *skel; + + int bloom_filter_fd; + int hashmap_fd; + int array_map_fd; + + 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, +}; + +struct stat { + __u32 stats[3]; +}; + +static struct { + __u32 nr_entries; + __u8 nr_hash_funcs; + __u32 value_size; +} args = { + .nr_entries = 1000, + .nr_hash_funcs = 3, + .value_size = 8, +}; + +enum { + ARG_NR_ENTRIES = 3000, + ARG_NR_HASH_FUNCS = 3001, + ARG_VALUE_SIZE = 3002, +}; + +static const struct argp_option opts[] = { + { "nr_entries", ARG_NR_ENTRIES, "NR_ENTRIES", 0, + "Set number of expected unique entries in the bloom filter"}, + { "nr_hash_funcs", ARG_NR_HASH_FUNCS, "NR_HASH_FUNCS", 0, + "Set number of hash functions in the bloom filter"}, + { "value_size", ARG_VALUE_SIZE, "VALUE_SIZE", 0, + "Set value size (in bytes) of bloom filter entries"}, + {}, +}; + +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 || args.nr_hash_funcs > 15) { + fprintf(stderr, + "The bloom filter must use 1 to 15 hash functions."); + argp_usage(state); + } + break; + case ARG_VALUE_SIZE: + args.value_size = strtol(arg, NULL, 10); + if (args.value_size < 2 || args.value_size > 256) { + fprintf(stderr, + "Invalid value size. Must be between 2 and 256 bytes"); + 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, + "The bloom filter benchmarks do not support multi-consumer use\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) +{ + __u32 val_size, i; + void *val = NULL; + int err; + + val_size = args.value_size; + val = malloc(val_size); + if (!val) { + ctx.map_prepare_err = true; + goto done; + } + + while (true) { + i = __atomic_add_fetch(&ctx.next_map_idx, 1, __ATOMIC_RELAXED); + if (i > args.nr_entries) + break; + +again: + /* Populate hashmap, bloom filter map, and array map with the same + * random values + */ + err = syscall(__NR_getrandom, val, val_size, 0); + if (err != val_size) { + ctx.map_prepare_err = true; + fprintf(stderr, "failed to get random value: %d\n", -errno); + break; + } + + err = bpf_map_update_elem(ctx.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(ctx.array_map_fd, &i, val, 0); + if (err) { + ctx.map_prepare_err = true; + fprintf(stderr, "failed to add elem to array map: %d\n", -errno); + break; + } + + err = bpf_map_update_elem(ctx.bloom_filter_fd, NULL, val, 0); + if (err) { + ctx.map_prepare_err = true; + fprintf(stderr, + "failed to add elem to bloom filter map: %d\n", -errno); + break; + } + } +done: + pthread_mutex_lock(&ctx.map_done_mtx); + pthread_cond_signal(&ctx.map_done); + pthread_mutex_unlock(&ctx.map_done_mtx); + + if (val) + free(val); + + return NULL; +} + +static void populate_maps(void) +{ + unsigned int nr_cpus = bpf_num_possible_cpus(); + pthread_t map_thread; + int i, err; + + ctx.bloom_filter_fd = bpf_map__fd(ctx.skel->maps.bloom_filter_map); + ctx.hashmap_fd = bpf_map__fd(ctx.skel->maps.hashmap); + ctx.array_map_fd = bpf_map__fd(ctx.skel->maps.array_map); + + 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_bench *setup_skeleton(bool hashmap_use_bloom_filter) +{ + struct bloom_filter_bench *skel; + int err; + + setup_libbpf(); + + skel = bloom_filter_bench__open(); + if (!skel) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + skel->rodata->hashmap_use_bloom_filter = hashmap_use_bloom_filter; + + /* Resize number of entries */ + 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.array_map, args.nr_entries); + if (err) { + fprintf(stderr, "failed to resize array map\n"); + exit(1); + } + + err = bpf_map__resize(skel->maps.bloom_filter_map, + BPF_BLOOM_FILTER_BITSET_SZ(args.nr_entries, + args.nr_hash_funcs)); + if (err) { + fprintf(stderr, "failed to resize bloom filter\n"); + exit(1); + } + + /* Set value size */ + err = bpf_map__set_value_size(skel->maps.array_map, args.value_size); + if (err) { + fprintf(stderr, "failed to set array map value size\n"); + exit(1); + } + + err = bpf_map__set_value_size(skel->maps.bloom_filter_map, args.value_size); + if (err) { + fprintf(stderr, "failed to set bloom filter map value size\n"); + exit(1); + } + + err = bpf_map__set_value_size(skel->maps.hashmap, args.value_size); + if (err) { + fprintf(stderr, "failed to set hashmap value size\n"); + exit(1); + } + /* For the hashmap, we use the value as the key as well */ + err = bpf_map__set_key_size(skel->maps.hashmap, args.value_size); + if (err) { + fprintf(stderr, "failed to set hashmap value size\n"); + exit(1); + } + + skel->bss->value_sz_nr_u32s = (args.value_size + sizeof(__u32) - 1) + / sizeof(__u32); + + /* Set number of hash functions */ + err = bpf_map__set_map_extra(skel->maps.bloom_filter_map, + args.nr_hash_funcs); + if (err) { + fprintf(stderr, "failed to set bloom filter nr_hash_funcs\n"); + exit(1); + } + + if (bloom_filter_bench__load(skel)) { + fprintf(stderr, "failed to load skeleton\n"); + exit(1); + } + + return skel; +} + +static void bench_setup_lookup(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(true); + + populate_maps(); + + link = bpf_program__attach(ctx.skel->progs.prog_bloom_filter_lookup); + if (!link) { + fprintf(stderr, "failed to attach program!\n"); + exit(1); + } +} + +static void bench_setup_update(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(true); + + populate_maps(); + + link = bpf_program__attach(ctx.skel->progs.prog_bloom_filter_update); + 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(true); + + 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; + static long last_hits, last_drops, last_false_hits; + unsigned int nr_cpus = bpf_num_possible_cpus(); + int hit_key, drop_key, false_hit_key; + int i; + + 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 bitset\n", + ctx.skel->bss->error); + 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]; + } + + 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; +} + +static void *consumer(void *input) +{ + return NULL; +} + +const struct bench bench_bloom_filter_lookup = { + .name = "bloom-filter-lookup", + .validate = validate, + .setup = bench_setup_lookup, + .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_update = { + .name = "bloom-filter-update", + .validate = validate, + .setup = bench_setup_update, + .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..5d4f84ad9973 --- /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 "Bitset map" +for v in 2, 4, 8, 16, 40; do +for t in 1 4 8 12 16; do +for h in {1..10}; do +subtitle "value_size: $v bytes, # 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 "Lookups, total operations: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e --value_size $v bloom-filter-lookup)" + printf "\t" + summarize "Updates, total operations: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e --value_size $v bloom-filter-update)" + printf "\t" + summarize_percentage "False positive rate: " \ + "$($RUN_BENCH -p $t --nr_hash_funcs $h --nr_entries $e --value_size $v bloom-filter-false-positive)" + done + printf "\n" +done +done +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/bpf_util.h b/tools/testing/selftests/bpf/bpf_util.h index a3352a64c067..a260a963efda 100644 --- a/tools/testing/selftests/bpf/bpf_util.h +++ b/tools/testing/selftests/bpf/bpf_util.h @@ -40,4 +40,15 @@ static inline unsigned int bpf_num_possible_cpus(void) (offsetof(TYPE, MEMBER) + sizeof_field(TYPE, MEMBER)) #endif +/* Helper macro for computing the optimal number of bits for a + * bloom filter map. + * + * Mathematically, the optimal bitset size that minimizes the + * false positive probability is n * k / ln(2) where n is the expected + * number of unique entries in the bloom filter and k is the number of + * hash functions. We use 7 / 5 to approximate 1 / ln(2). + */ +#define BPF_BLOOM_FILTER_BITSET_SZ(nr_uniq_entries, nr_hash_funcs) \ + ((nr_uniq_entries) * (nr_hash_funcs) / 5 * 7) + #endif /* __BPF_UTIL__ */ diff --git a/tools/testing/selftests/bpf/progs/bloom_filter_bench.c b/tools/testing/selftests/bpf/progs/bloom_filter_bench.c new file mode 100644 index 000000000000..a44a47ddc4d7 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/bloom_filter_bench.c @@ -0,0 +1,146 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include +#include +#include +#include + +char _license[] SEC("license") = "GPL"; + +struct bpf_map; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(key_size, sizeof(__u32)); + /* max entries and value_size will be set programmatically. + * They are configurable from the userspace bench program. + */ +} array_map SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_BITSET); + /* max entries, value_size, and # of hash functions will be set + * programmatically. They are configurable from the userspace + * bench program. + */ +} bloom_filter_map SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + /* max entries, key_size, and value_size, will be set + * programmatically. They are configurable from the userspace + * bench program. + */ +} hashmap SEC(".maps"); + +struct callback_ctx { + struct bpf_map *map; + bool update; +}; + +/* Tracks the number of hits, drops, and false hits */ +struct { + __u32 stats[3]; +} __attribute__((__aligned__(256))) percpu_stats[256]; + +__u8 value_sz_nr_u32s; + +const __u32 hit_key = 0; +const __u32 drop_key = 1; +const __u32 false_hit_key = 2; + +const volatile bool hashmap_use_bloom_filter = true; + +int error = 0; + +static __always_inline void log_result(__u32 key) +{ + __u32 cpu = bpf_get_smp_processor_id(); + + percpu_stats[cpu & 255].stats[key]++; +} + +static __u64 +bloom_filter_callback(struct bpf_map *map, __u32 *key, void *val, + struct callback_ctx *data) +{ + int err; + + if (data->update) + err = bpf_map_push_elem(data->map, val, 0); + else + err = bpf_map_peek_elem(data->map, val); + + if (err) { + error |= 1; + return 1; /* stop the iteration */ + } + + log_result(hit_key); + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter_lookup(void *ctx) +{ + struct callback_ctx data; + + data.map = (struct bpf_map *)&bloom_filter_map; + data.update = false; + + bpf_for_each_map_elem(&array_map, bloom_filter_callback, &data, 0); + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter_update(void *ctx) +{ + struct callback_ctx data; + + data.map = (struct bpf_map *)&bloom_filter_map; + data.update = true; + + bpf_for_each_map_elem(&array_map, bloom_filter_callback, &data, 0); + + return 0; +} + +SEC("fentry/__x64_sys_getpgid") +int prog_bloom_filter_hashmap_lookup(void *ctx) +{ + __u64 *result; + int i, j, err; + + __u32 val[64] = {0}; + + for (i = 0; i < 1024; i++) { + for (j = 0; j < value_sz_nr_u32s && j < 64; j++) + val[j] = bpf_get_prandom_u32(); + + if (hashmap_use_bloom_filter) { + err = bpf_map_peek_elem(&bloom_filter_map, val); + if (err) { + if (err != -ENOENT) { + error |= 3; + return 0; + } + log_result(hit_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 Wed Oct 6 22:21:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12540699 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 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id EBB1CC433EF for ; Wed, 6 Oct 2021 22:24:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BB58260F6D for ; Wed, 6 Oct 2021 22:24:01 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239547AbhJFWXb (ORCPT ); Wed, 6 Oct 2021 18:23:31 -0400 Received: from mx0a-00082601.pphosted.com ([67.231.145.42]:55978 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S239223AbhJFWX3 (ORCPT ); Wed, 6 Oct 2021 18:23:29 -0400 Received: from pps.filterd (m0148461.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.1.2/8.16.1.2) with SMTP id 196Ksxiu023994 for ; Wed, 6 Oct 2021 15:21:37 -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=tE1gh+cDMstjNrOoX7wS2SwzPIWV0vjMmBRZHLFeCLk=; b=VvQpxn8EXlhhjZ/MQT7qsgKhKA3rksXupHJqjzQh19ogdkcaDAYg5In8tf7zr+P2wBGt QmQ2BBDMED8APSWyh0qisLnCocR6/wanJJXMJDi9g5WDrzn8R1BGqgHYs+Qo6e0NdO8T 6n1cQrpIYTpKLVJJ7PXg9xPIiM2vsVTuygk= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com with ESMTP id 3bhk8eghgv-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 06 Oct 2021 15:21:37 -0700 Received: from intmgw001.25.frc3.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; Wed, 6 Oct 2021 15:21:36 -0700 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id EC1A23451896; Wed, 6 Oct 2021 15:21:29 -0700 (PDT) From: Joanne Koong To: CC: , Joanne Koong Subject: [PATCH bpf-next v4 5/5] bpf/benchs: Add benchmarks for comparing hashmap lookups w/ vs. w/out bloom filter Date: Wed, 6 Oct 2021 15:21:03 -0700 Message-ID: <20211006222103.3631981-6-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20211006222103.3631981-1-joannekoong@fb.com> References: <20211006222103.3631981-1-joannekoong@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: Vk4Ce5_62UDBt9dG-cfaOdC1eNzLz30S X-Proofpoint-ORIG-GUID: Vk4Ce5_62UDBt9dG-cfaOdC1eNzLz30S 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-10-06_04,2021-10-06_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 mlxscore=0 bulkscore=0 spamscore=0 impostorscore=0 suspectscore=0 phishscore=0 priorityscore=1501 lowpriorityscore=0 mlxlogscore=999 malwarescore=0 adultscore=0 clxscore=1015 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109230001 definitions=main-2110060139 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 | 37 +++++++++++++++++++ .../bpf/benchs/run_bench_bloom_filter_map.sh | 17 +++++++++ .../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 e836bacd6f9d..d9661f343556 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"; @@ -357,6 +365,8 @@ extern const struct bench bench_pb_custom; extern const struct bench bench_bloom_filter_lookup; extern const struct bench bench_bloom_filter_update; 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, @@ -381,6 +391,8 @@ static const struct bench *benchs[] = { &bench_bloom_filter_lookup, &bench_bloom_filter_update, &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 25d6b8179c8e..7af8fd455dc0 100644 --- a/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c +++ b/tools/testing/selftests/bpf/benchs/bench_bloom_filter_map.c @@ -337,6 +337,21 @@ static void hashmap_lookup_setup(void) } } +static void hashmap_no_bloom_filter_setup(void) +{ + struct bpf_link *link; + + ctx.skel = setup_skeleton(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; @@ -409,3 +424,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 5d4f84ad9973..a8cff64d0492 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,20 @@ subtitle "value_size: $v bytes, # threads: $t, # hashes: $h" done done done + +header "Hashmap without bitset vs. hashmap with bitset (throughput, 8 threads)" +for v in 2, 4, 8, 16, 40; do +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 bitset: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e --value_size $v -p 8 hashmap-without-bloom-filter)" + printf "\t" + summarize_total "Hashmap with bitset: " \ + "$($RUN_BENCH --nr_hash_funcs $h --nr_entries $e --value_size $v -p 8 hashmap-with-bloom-filter)" + done + printf "\n" +done +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)" +}