From patchwork Mon Feb 14 11:13:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hou Tao X-Patchwork-Id: 12745410 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 24661C4332F for ; Mon, 14 Feb 2022 11:18:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1350773AbiBNLS1 (ORCPT ); Mon, 14 Feb 2022 06:18:27 -0500 Received: from mxb-00190b01.gslb.pphosted.com ([23.128.96.19]:46938 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1350685AbiBNLST (ORCPT ); Mon, 14 Feb 2022 06:18:19 -0500 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3FFBA66215; Mon, 14 Feb 2022 02:51:31 -0800 (PST) Received: from dggpeml500025.china.huawei.com (unknown [172.30.72.56]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4Jy1G845N8zccyN; Mon, 14 Feb 2022 18:50:24 +0800 (CST) Received: from huawei.com (10.175.112.60) by dggpeml500025.china.huawei.com (7.185.36.35) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.21; Mon, 14 Feb 2022 18:51:28 +0800 From: Hou Tao To: Alexei Starovoitov CC: Martin KaFai Lau , Yonghong Song , Daniel Borkmann , Andrii Nakryiko , Song Liu , John Fastabend , , , Subject: [RFC PATCH bpf-next v2 1/3] bpf: add support for string in hash table key Date: Mon, 14 Feb 2022 19:13:35 +0800 Message-ID: <20220214111337.3539-2-houtao1@huawei.com> X-Mailer: git-send-email 2.25.4 In-Reply-To: <20220214111337.3539-1-houtao1@huawei.com> References: <20220214111337.3539-1-houtao1@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.175.112.60] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpeml500025.china.huawei.com (7.185.36.35) X-CFilter-Loop: Reflected Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC In order to use string as hash-table key, key_size must be the storage size of longest string. If there are large differencies in string length, the hash distribution will be sub-optimal due to the unused zero bytes in shorter strings and the lookup will be inefficient due to unnecessary memcmp(). Also it is possible the unused part of string key returned from bpf helper (e.g. bpf_d_path) is not mem-zeroed and if using it directly as lookup key, the lookup will fail with -ENOENT. Three changes are made to support string in key. Enforce the layout of hash key struct through btf to place strings togerther and to compare the string length and string hash firstly before the comparison of string content. The layout of hash key struct needs to be as follow: >the start of hash key ... [struct bpf_str_key_desc m;] ... [struct bpf_str_key_desc n;] ... struct bpf_str_key_stor z; unsigned char raw[N]; >the end of hash key String or concatenation of strings is placed in the trailing char array. bpf_str_key_stor saves the length and hash of string. And bpf_str_key_desc describes the offset and length of string if there are multiple strings in hash key. The second change is that change the hash algorithm for string content from jhash() to full_name_hash() to reduce hash collision for string and the string hash in bpf_str_key_stor will be used in hash of the whole key when the string is not the only key in hash key. The last change is only compare the used part in the trailing char array for comparison of string content. A new flag BPF_F_STR_IN_KEY is added to enable above three changes and to support strings in hash table key. Signed-off-by: Hou Tao --- include/linux/btf.h | 3 + include/uapi/linux/bpf.h | 19 ++++ kernel/bpf/btf.c | 39 ++++++++ kernel/bpf/hashtab.c | 162 ++++++++++++++++++++++++++++----- tools/include/uapi/linux/bpf.h | 19 ++++ 5 files changed, 217 insertions(+), 25 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index 36bc09b8e890..270f5e3329bd 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -123,6 +123,9 @@ bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, u32 expected_offset, u32 expected_size); int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t); int btf_find_timer(const struct btf *btf, const struct btf_type *t); +int btf_find_str_key_stor(const struct btf *btf, const struct btf_type *t); +int btf_find_array_at(const struct btf *btf, const struct btf_type *t, + unsigned int at, unsigned int nelems); bool btf_type_is_void(const struct btf_type *t); s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind); const struct btf_type *btf_type_skip_modifiers(const struct btf *btf, diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index afe3d0d7f5f2..c764a82d79cd 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -1218,6 +1218,9 @@ enum { /* Create a map that is suitable to be an inner map with dynamic max entries */ BPF_F_INNER_MAP = (1U << 12), + +/* Flag for hash_map, there is string in hash key */ + BPF_F_STR_IN_KEY = (1U << 13), }; /* Flags for BPF_PROG_QUERY. */ @@ -6565,4 +6568,20 @@ struct bpf_core_relo { enum bpf_core_relo_kind kind; }; +struct bpf_str_key_desc { + /* the relative offset of string */ + __u32 offset; + /* the length of string (include the trailing zero) */ + __u32 len; +}; + +struct bpf_str_key_stor { + /* the total length of string */ + __u32 len; + /* the hash of string */ + __u32 hash; + /* the content of string */ + unsigned char raw[0]; +}; + #endif /* _UAPI__LINUX_BPF_H__ */ diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 11740b300de9..c57eb6c12ef2 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -3187,6 +3187,16 @@ static int btf_find_field(const struct btf *btf, const struct btf_type *t, return -EINVAL; } +int btf_find_str_key_stor(const struct btf *btf, const struct btf_type *t) +{ + if (!__btf_type_is_struct(t)) + return -EINVAL; + + return btf_find_struct_field(btf, t, "bpf_str_key_stor", + sizeof(struct bpf_str_key_stor), + __alignof__(struct bpf_str_key_stor)); +} + /* find 'struct bpf_spin_lock' in map value. * return >= 0 offset if found * and < 0 in case of error @@ -7281,3 +7291,32 @@ int bpf_core_apply(struct bpf_core_ctx *ctx, const struct bpf_core_relo *relo, } return err; } + +int btf_find_array_at(const struct btf *btf, const struct btf_type *t, + unsigned int at, unsigned int nelems) +{ + const struct btf_member *member; + u32 i, off; + + for_each_member(i, t, member) { + const struct btf_type *member_type = btf_type_by_id(btf, member->type); + const struct btf_array *array; + + if (!btf_type_is_array(member_type)) + continue; + + off = __btf_member_bit_offset(t, member); + if (off % 8) + return -EINVAL; + off /= 8; + if (off != at) + continue; + + array = btf_type_array(member_type); + if (array->nelems == nelems) + return off; + break; + } + + return -ENOENT; +} diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index d29af9988f37..ab2f95212a9c 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -16,7 +16,7 @@ #define HTAB_CREATE_FLAG_MASK \ (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE | \ - BPF_F_ACCESS_MASK | BPF_F_ZERO_SEED) + BPF_F_ACCESS_MASK | BPF_F_ZERO_SEED | BPF_F_STR_IN_KEY) #define BATCH_OPS(_name) \ .map_lookup_batch = \ @@ -93,6 +93,8 @@ struct bpf_htab { struct bpf_map map; struct bucket *buckets; void *elems; + u32 hash_key_size; + int str_stor_off; union { struct pcpu_freelist freelist; struct bpf_lru lru; @@ -137,6 +139,61 @@ static inline bool htab_use_raw_lock(const struct bpf_htab *htab) return (!IS_ENABLED(CONFIG_PREEMPT_RT) || htab_is_prealloc(htab)); } +static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd) +{ + return jhash(key, key_len, hashrnd); +} + +static inline bool htab_str_in_key(const struct bpf_htab *htab) +{ + return htab->map.map_flags & BPF_F_STR_IN_KEY; +} + +static inline bool htab_valid_str_in_key(const struct bpf_htab *htab, void *key) +{ + struct bpf_str_key_stor *str; + + if (!htab_str_in_key(htab)) + return true; + + str = key + htab->str_stor_off; + return str->len > 0 && + str->len <= htab->map.key_size - htab->hash_key_size; +} + +static inline bool htab_compared_key_size(const struct bpf_htab *htab, void *key) +{ + struct bpf_str_key_stor *str; + + if (!htab_str_in_key(htab)) + return htab->map.key_size; + + str = key + htab->str_stor_off; + return htab->hash_key_size + str->len; +} + +static inline u32 htab_map_calc_hash(const struct bpf_htab *htab, void *key) +{ + struct bpf_str_key_stor *str; + + if (!htab_str_in_key(htab)) + return htab_map_hash(key, htab->map.key_size, htab->hashrnd); + + str = key + htab->str_stor_off; + if (!str->hash) { + str->hash = full_name_hash((void *)(unsigned long)htab->hashrnd, + str->raw, str->len); + if (!str->hash) + str->hash = htab->n_buckets > 1 ? htab->n_buckets - 1 : 1; + } + + /* String key only */ + if (!htab->str_stor_off) + return str->hash; + + return htab_map_hash(key, htab->hash_key_size, htab->hashrnd); +} + static void htab_init_buckets(struct bpf_htab *htab) { unsigned i; @@ -410,6 +467,7 @@ static int htab_map_alloc_check(union bpf_attr *attr) bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU); bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC); bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED); + bool str_in_key = (attr->map_flags & BPF_F_STR_IN_KEY); int numa_node = bpf_map_attr_numa_node(attr); BUILD_BUG_ON(offsetof(struct htab_elem, htab) != @@ -440,6 +498,10 @@ static int htab_map_alloc_check(union bpf_attr *attr) if (numa_node != NUMA_NO_NODE && (percpu || percpu_lru)) return -EINVAL; + /* string in key needs key btf info */ + if (str_in_key && !attr->btf_key_type_id) + return -EINVAL; + /* check sanity of attributes. * value_size == 0 may be allowed in the future to use map as a set */ @@ -563,11 +625,6 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr) return ERR_PTR(err); } -static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd) -{ - return jhash(key, key_len, hashrnd); -} - static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash) { return &htab->buckets[hash & (htab->n_buckets - 1)]; @@ -624,18 +681,20 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key) struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct htab_elem *l; - u32 hash, key_size; + u32 hash, cmp_size; WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() && !rcu_read_lock_bh_held()); - key_size = map->key_size; + if (!htab_valid_str_in_key(htab, key)) + return NULL; - hash = htab_map_hash(key, key_size, htab->hashrnd); + hash = htab_map_calc_hash(htab, key); head = select_bucket(htab, hash); - l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets); + cmp_size = htab_compared_key_size(htab, key); + l = lookup_nulls_elem_raw(head, hash, key, cmp_size, htab->n_buckets); return l; } @@ -676,6 +735,45 @@ static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) return insn - insn_buf; } +static int htab_check_btf(const struct bpf_map *map, const struct btf *btf, + const struct btf_type *key_type, + const struct btf_type *value_type) +{ + struct bpf_htab *htab = container_of(map, struct bpf_htab, map); + int offset; + int next; + + if (!htab_str_in_key(htab)) + return 0; + + /* + * The layout of string in hash key must be as follows: + * + * >the start of hash key + * ... + * [struct bpf_str_key_desc m;] + * ... + * [struct bpf_str_key_desc n;] + * ... + * struct bpf_str_key_stor z; + * unsigned char s[N]; + * >the end of hash key + */ + offset = btf_find_str_key_stor(btf, key_type); + if (offset < 0) + return offset; + + next = offset + sizeof(struct bpf_str_key_stor); + if (next >= map->key_size || + btf_find_array_at(btf, key_type, next, map->key_size - next) < 0) + return -EINVAL; + + htab->hash_key_size = next; + htab->str_stor_off = offset; + + return 0; +} + static __always_inline void *__htab_lru_map_lookup_elem(struct bpf_map *map, void *key, const bool mark) { @@ -772,7 +870,7 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct htab_elem *l, *next_l; - u32 hash, key_size; + u32 hash, key_size, cmp_size; int i = 0; WARN_ON_ONCE(!rcu_read_lock_held()); @@ -782,12 +880,16 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) if (!key) goto find_first_elem; - hash = htab_map_hash(key, key_size, htab->hashrnd); + if (!htab_valid_str_in_key(htab, key)) + return -EINVAL; + + hash = htab_map_calc_hash(htab, key); head = select_bucket(htab, hash); /* lookup the key */ - l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets); + cmp_size = htab_compared_key_size(htab, key); + l = lookup_nulls_elem_raw(head, hash, key, cmp_size, htab->n_buckets); if (!l) goto find_first_elem; @@ -1024,19 +1126,22 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, struct hlist_nulls_head *head; unsigned long flags; struct bucket *b; - u32 key_size, hash; + u32 key_size, hash, cmp_size; int ret; if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST)) /* unknown flags */ return -EINVAL; + if (!htab_valid_str_in_key(htab, key)) + return -EINVAL; WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() && !rcu_read_lock_bh_held()); key_size = map->key_size; + cmp_size = htab_compared_key_size(htab, key); - hash = htab_map_hash(key, key_size, htab->hashrnd); + hash = htab_map_calc_hash(htab, key); b = __select_bucket(htab, hash); head = &b->head; @@ -1045,7 +1150,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, if (unlikely(!map_value_has_spin_lock(map))) return -EINVAL; /* find an element without taking the bucket lock */ - l_old = lookup_nulls_elem_raw(head, hash, key, key_size, + l_old = lookup_nulls_elem_raw(head, hash, key, cmp_size, htab->n_buckets); ret = check_flags(htab, l_old, map_flags); if (ret) @@ -1067,7 +1172,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, if (ret) return ret; - l_old = lookup_elem_raw(head, hash, key, key_size); + l_old = lookup_elem_raw(head, hash, key, cmp_size); ret = check_flags(htab, l_old, map_flags); if (ret) @@ -1328,15 +1433,16 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key) struct bucket *b; struct htab_elem *l; unsigned long flags; - u32 hash, key_size; + u32 hash, cmp_size; int ret; + if (!htab_valid_str_in_key(htab, key)) + return -EINVAL; + WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() && !rcu_read_lock_bh_held()); - key_size = map->key_size; - - hash = htab_map_hash(key, key_size, htab->hashrnd); + hash = htab_map_calc_hash(htab, key); b = __select_bucket(htab, hash); head = &b->head; @@ -1344,7 +1450,8 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key) if (ret) return ret; - l = lookup_elem_raw(head, hash, key, key_size); + cmp_size = htab_compared_key_size(htab, key); + l = lookup_elem_raw(head, hash, key, cmp_size); if (l) { hlist_nulls_del_rcu(&l->hash_node); @@ -1495,13 +1602,16 @@ static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, struct hlist_nulls_head *head; unsigned long bflags; struct htab_elem *l; - u32 hash, key_size; struct bucket *b; + u32 hash, key_size, cmp_size; int ret; + if (!htab_valid_str_in_key(htab, key)) + return -EINVAL; + key_size = map->key_size; - hash = htab_map_hash(key, key_size, htab->hashrnd); + hash = htab_map_calc_hash(htab, key); b = __select_bucket(htab, hash); head = &b->head; @@ -1509,7 +1619,8 @@ static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, if (ret) return ret; - l = lookup_elem_raw(head, hash, key, key_size); + cmp_size = htab_compared_key_size(htab, key); + l = lookup_elem_raw(head, hash, key, cmp_size); if (!l) { ret = -ENOENT; } else { @@ -2118,6 +2229,7 @@ const struct bpf_map_ops htab_map_ops = { .map_update_elem = htab_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_gen_lookup = htab_map_gen_lookup, + .map_check_btf = htab_check_btf, .map_seq_show_elem = htab_map_seq_show_elem, .map_set_for_each_callback_args = map_set_for_each_callback_args, .map_for_each_callback = bpf_for_each_hash_elem, diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index afe3d0d7f5f2..c764a82d79cd 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -1218,6 +1218,9 @@ enum { /* Create a map that is suitable to be an inner map with dynamic max entries */ BPF_F_INNER_MAP = (1U << 12), + +/* Flag for hash_map, there is string in hash key */ + BPF_F_STR_IN_KEY = (1U << 13), }; /* Flags for BPF_PROG_QUERY. */ @@ -6565,4 +6568,20 @@ struct bpf_core_relo { enum bpf_core_relo_kind kind; }; +struct bpf_str_key_desc { + /* the relative offset of string */ + __u32 offset; + /* the length of string (include the trailing zero) */ + __u32 len; +}; + +struct bpf_str_key_stor { + /* the total length of string */ + __u32 len; + /* the hash of string */ + __u32 hash; + /* the content of string */ + unsigned char raw[0]; +}; + #endif /* _UAPI__LINUX_BPF_H__ */ From patchwork Mon Feb 14 11:13:36 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hou Tao X-Patchwork-Id: 12745411 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 105FBC4167D for ; Mon, 14 Feb 2022 11:18:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1350686AbiBNLS3 (ORCPT ); Mon, 14 Feb 2022 06:18:29 -0500 Received: from mxb-00190b01.gslb.pphosted.com ([23.128.96.19]:48840 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1350676AbiBNLST (ORCPT ); Mon, 14 Feb 2022 06:18:19 -0500 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 40C7C66218; Mon, 14 Feb 2022 02:51:31 -0800 (PST) Received: from dggpeml500025.china.huawei.com (unknown [172.30.72.54]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4Jy1BQ3P6SzZfdl; Mon, 14 Feb 2022 18:47:10 +0800 (CST) Received: from huawei.com (10.175.112.60) by dggpeml500025.china.huawei.com (7.185.36.35) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.21; Mon, 14 Feb 2022 18:51:29 +0800 From: Hou Tao To: Alexei Starovoitov CC: Martin KaFai Lau , Yonghong Song , Daniel Borkmann , Andrii Nakryiko , Song Liu , John Fastabend , , , Subject: [RFC PATCH bpf-next v2 2/3] selftests/bpf: add a simple test for htab str key Date: Mon, 14 Feb 2022 19:13:36 +0800 Message-ID: <20220214111337.3539-3-houtao1@huawei.com> X-Mailer: git-send-email 2.25.4 In-Reply-To: <20220214111337.3539-1-houtao1@huawei.com> References: <20220214111337.3539-1-houtao1@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.175.112.60] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpeml500025.china.huawei.com (7.185.36.35) X-CFilter-Loop: Reflected Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC Add a test to demonstrate that str key doesn't care about the content of unused part in hash-table key. Signed-off-by: Hou Tao --- .../selftests/bpf/prog_tests/str_key.c | 71 ++++++++++++++++++ tools/testing/selftests/bpf/progs/str_key.c | 75 +++++++++++++++++++ 2 files changed, 146 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/str_key.c create mode 100644 tools/testing/selftests/bpf/progs/str_key.c diff --git a/tools/testing/selftests/bpf/prog_tests/str_key.c b/tools/testing/selftests/bpf/prog_tests/str_key.c new file mode 100644 index 000000000000..998f12f8b919 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/str_key.c @@ -0,0 +1,71 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (C) 2022. Huawei Technologies Co., Ltd */ +#include +#include +#include +#include +#include +#include "str_key.skel.h" + +#define HTAB_NAME_SIZE 64 + +struct str_htab_key { + struct bpf_str_key_stor name; + char raw[HTAB_NAME_SIZE]; +}; + +static int setup_maps(struct str_key *skel, const char *name, unsigned int value) +{ + struct str_htab_key key; + int fd, err; + + memset(&key, 0, sizeof(key)); + strncpy(key.raw, name, sizeof(key.raw) - 1); + key.name.len = strlen(name) + 1; + + fd = bpf_map__fd(skel->maps.str_htab); + err = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST); + if (!ASSERT_OK(err, "str htab add")) + return -EINVAL; + + fd = bpf_map__fd(skel->maps.byte_htab); + err = bpf_map_update_elem(fd, key.raw, &value, BPF_NOEXIST); + if (!ASSERT_OK(err, "byte htab add")) + return -EINVAL; + + return 0; +} + +void test_str_key(void) +{ + const char *name = "/tmp/str_key_test"; + struct str_key *skel; + unsigned int value; + int err, fd; + + skel = str_key__open_and_load(); + if (!ASSERT_OK_PTR(skel, "open_load str key")) + return; + + srandom(time(NULL)); + value = random(); + if (setup_maps(skel, name, value)) + goto out; + + skel->bss->pid = getpid(); + err = str_key__attach(skel); + if (!ASSERT_OK(err, "attach")) + goto out; + + fd = open(name, O_RDONLY | O_CREAT, 0644); + if (!ASSERT_GE(fd, 0, "open tmp file")) + goto out; + close(fd); + unlink(name); + + ASSERT_EQ(skel->bss->str_htab_value, value, "str htab find"); + ASSERT_EQ(skel->bss->byte_htab_value, -1, "byte htab find"); + +out: + str_key__destroy(skel); +} diff --git a/tools/testing/selftests/bpf/progs/str_key.c b/tools/testing/selftests/bpf/progs/str_key.c new file mode 100644 index 000000000000..4d5a4b7cf183 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/str_key.c @@ -0,0 +1,75 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (C) 2022. Huawei Technologies Co., Ltd */ +#include +#include +#include +#include +#include + +char _license[] SEC("license") = "GPL"; + +struct path { +} __attribute__((preserve_access_index)); + +struct file { + struct path f_path; +} __attribute__((preserve_access_index)); + +#define HTAB_NAME_SIZE 64 + +struct str_htab_key { + struct bpf_str_key_stor name; + char raw[HTAB_NAME_SIZE]; +}; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 1); + __type(key, struct str_htab_key); + __type(value, __u32); + __uint(map_flags, BPF_F_STR_IN_KEY); +} str_htab SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 1); + __uint(key_size, HTAB_NAME_SIZE); + __uint(value_size, sizeof(__u32)); +} byte_htab SEC(".maps"); + +int pid = 0; +unsigned int str_htab_value = 0; +unsigned int byte_htab_value = 0; + +SEC("fentry/filp_close") +int BPF_PROG(filp_close, struct file *filp) +{ + struct path *p = &filp->f_path; + struct str_htab_key key; + unsigned int *value; + int len; + + if (bpf_get_current_pid_tgid() >> 32 != pid) + return 0; + + __builtin_memset(key.raw, 0, sizeof(key.raw)); + len = bpf_d_path(p, key.raw, sizeof(key.raw)); + if (len < 0 || len > sizeof(key.raw)) + return 0; + + key.name.hash = 0; + key.name.len = len; + value = bpf_map_lookup_elem(&str_htab, &key); + if (value) + str_htab_value = *value; + else + str_htab_value = -1; + + value = bpf_map_lookup_elem(&byte_htab, key.raw); + if (value) + byte_htab_value = *value; + else + byte_htab_value = -1; + + return 0; +} From patchwork Mon Feb 14 11:13:37 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Hou Tao X-Patchwork-Id: 12745412 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 759C9C4332F for ; Mon, 14 Feb 2022 11:18:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1350790AbiBNLSa (ORCPT ); Mon, 14 Feb 2022 06:18:30 -0500 Received: from mxb-00190b01.gslb.pphosted.com ([23.128.96.19]:47180 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1350610AbiBNLSU (ORCPT ); Mon, 14 Feb 2022 06:18:20 -0500 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0018B66222; Mon, 14 Feb 2022 02:51:32 -0800 (PST) Received: from dggpeml500025.china.huawei.com (unknown [172.30.72.56]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4Jy1Cd0X3Sz8wZJ; Mon, 14 Feb 2022 18:48:13 +0800 (CST) Received: from huawei.com (10.175.112.60) by dggpeml500025.china.huawei.com (7.185.36.35) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.21; Mon, 14 Feb 2022 18:51:29 +0800 From: Hou Tao To: Alexei Starovoitov CC: Martin KaFai Lau , Yonghong Song , Daniel Borkmann , Andrii Nakryiko , Song Liu , John Fastabend , , , Subject: [RFC PATCH bpf-next v2 3/3] selftests/bpf: add benchmark for string-key hash table Date: Mon, 14 Feb 2022 19:13:37 +0800 Message-ID: <20220214111337.3539-4-houtao1@huawei.com> X-Mailer: git-send-email 2.25.4 In-Reply-To: <20220214111337.3539-1-houtao1@huawei.com> References: <20220214111337.3539-1-houtao1@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.175.112.60] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpeml500025.china.huawei.com (7.185.36.35) X-CFilter-Loop: Reflected Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net X-Patchwork-State: RFC Three different key types are defined to representate the typical use cases for string-key hash table: (1) string-only key (str/byte) (2) integer + string key (int-str/int-byte) (3) integer + two strings key (int-strs/int-bytes) It supports these three key types by using normal hash table and string-key hash table and compares the lookup performance between normal hash table and string-key hash table respectively. Because string-key hash table depends on btf, and have not figured out a way to setup btf for map key type dynamically, so in the benchmark the max size of string is fixed as 252 (multiplier of 12 for jhash()). The performance win comes from two aspect: (1) use full_name_hash() for string content instead of jhash(). The former calculate hash in long granularity and has better hash-distribution for string. (2) compare the string hash and length firstly before compare the string content. The win is about 180% and 170% under x86-64 and arm64 when key_size is 252 and increase to 280% and 270% when key_size is greater than 512. The detailed results follows. N-{byte|int-byte|int-bytes}: lookup on normal hash table with three different key type and N-bytes as max string size. N-{str|int-str|int-strs}: lookup on string-key hash table with three different key type and N-bytes as max string size. Under x86-64: 132-htab-byte-lookup 11.946 ± 0.005M/s (drops 0.000 ± 0.000M/s) 132-htab-str-lookup 23.762 ± 0.028M/s (drops 0.000 ± 0.000M/s) 132-htab-int-byte-lookup 11.510 ± 0.012M/s (drops 0.000 ± 0.000M/s) 132-htab-int-str-lookup 19.885 ± 0.020M/s (drops 0.000 ± 0.000M/s) 132-htab-int-bytes-lookup 11.464 ± 0.009M/s (drops 0.000 ± 0.000M/s) 132-htab-int-strs-lookup 18.183 ± 0.020M/s (drops 0.000 ± 0.000M/s) 252-htab-byte-lookup 7.092 ± 0.003M/s (drops 0.000 ± 0.000M/s) 252-htab-str-lookup 20.126 ± 0.017M/s (drops 0.000 ± 0.000M/s) 252-htab-int-byte-lookup 6.949 ± 0.002M/s (drops 0.000 ± 0.000M/s) 252-htab-int-str-lookup 17.173 ± 0.019M/s (drops 0.000 ± 0.000M/s) 252-htab-int-bytes-lookup 6.878 ± 0.001M/s (drops 0.000 ± 0.000M/s) 252-htab-int-strs-lookup 15.153 ± 0.006M/s (drops 0.000 ± 0.000M/s) 516-htab-byte-lookup 3.719 ± 0.001M/s (drops 0.000 ± 0.000M/s) 516-htab-str-lookup 14.185 ± 0.004M/s (drops 0.000 ± 0.000M/s) 516-htab-int-byte-lookup 3.675 ± 0.002M/s (drops 0.000 ± 0.000M/s) 516-htab-int-str-lookup 12.354 ± 0.005M/s (drops 0.000 ± 0.000M/s) 516-htab-int-bytes-lookup 3.673 ± 0.001M/s (drops 0.000 ± 0.000M/s) 516-htab-int-strs-lookup 11.328 ± 0.004M/s (drops 0.000 ± 0.000M/s) Under arm64: 132-htab-byte-lookup 8.680 ± 0.003M/s (drops 0.009 ± 0.000M/s) 132-htab-str-lookup 18.736 ± 0.010M/s (drops 0.000 ± 0.000M/s) 132-htab-int-byte-lookup 8.239 ± 0.004M/s (drops 0.000 ± 0.000M/s) 132-htab-int-str-lookup 16.395 ± 0.049M/s (drops 0.000 ± 0.000M/s) 132-htab-int-bytes-lookup 8.199 ± 0.008M/s (drops 0.000 ± 0.000M/s) 132-htab-int-strs-lookup 13.047 ± 0.006M/s (drops 0.000 ± 0.000M/s) 252-htab-byte-lookup 5.092 ± 0.008M/s (drops 0.000 ± 0.000M/s) 252-htab-str-lookup 14.065 ± 0.179M/s (drops 0.000 ± 0.000M/s) 252-htab-int-byte-lookup 4.939 ± 0.002M/s (drops 0.000 ± 0.000M/s) 252-htab-int-str-lookup 13.612 ± 0.009M/s (drops 0.000 ± 0.000M/s) 252-htab-int-bytes-lookup 4.953 ± 0.007M/s (drops 0.000 ± 0.000M/s) 252-htab-int-strs-lookup 11.228 ± 0.004M/s (drops 0.000 ± 0.000M/s) 516-htab-byte-lookup 2.661 ± 0.002M/s (drops 0.000 ± 0.000M/s) 516-htab-str-lookup 9.857 ± 0.012M/s (drops 0.000 ± 0.000M/s) 516-htab-int-byte-lookup 2.616 ± 0.001M/s (drops 0.000 ± 0.000M/s) 516-htab-int-str-lookup 9.143 ± 0.001M/s (drops 0.000 ± 0.000M/s) 516-htab-int-bytes-lookup 2.615 ± 0.000M/s (drops 0.000 ± 0.000M/s) 516-htab-int-strs-lookup 7.456 ± 0.002M/s (drops 0.000 ± 0.000M/s) Signed-off-by: Hou Tao --- tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/bench.c | 14 + .../selftests/bpf/benchs/bench_str_htab.c | 449 ++++++++++++++++++ .../testing/selftests/bpf/benchs/run_htab.sh | 11 + .../selftests/bpf/progs/str_htab_bench.c | 224 +++++++++ 5 files changed, 701 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_str_htab.c create mode 100755 tools/testing/selftests/bpf/benchs/run_htab.sh create mode 100644 tools/testing/selftests/bpf/progs/str_htab_bench.c diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index 91ea729990da..df174cfad8dd 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -538,6 +538,7 @@ $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h $(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h +$(OUTPUT)/bench_str_htab.o: $(OUTPUT)/str_htab_bench.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \ @@ -549,7 +550,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ - $(OUTPUT)/bench_strncmp.o + $(OUTPUT)/bench_strncmp.o \ + $(OUTPUT)/bench_str_htab.o $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@ diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index f973320e6dbf..ba241d34b0ec 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -190,12 +190,14 @@ extern struct argp bench_ringbufs_argp; extern struct argp bench_bloom_map_argp; extern struct argp bench_bpf_loop_argp; extern struct argp bench_strncmp_argp; +extern struct argp bench_str_htab_argp; static const struct argp_child bench_parsers[] = { { &bench_ringbufs_argp, 0, "Ring buffers benchmark", 0 }, { &bench_bloom_map_argp, 0, "Bloom filter map benchmark", 0 }, { &bench_bpf_loop_argp, 0, "bpf_loop helper benchmark", 0 }, { &bench_strncmp_argp, 0, "bpf_strncmp helper benchmark", 0 }, + { &bench_str_htab_argp, 0, "string htab benchmark", 0 }, {}, }; @@ -397,6 +399,12 @@ extern const struct bench bench_hashmap_with_bloom; extern const struct bench bench_bpf_loop; extern const struct bench bench_strncmp_no_helper; extern const struct bench bench_strncmp_helper; +extern const struct bench bench_htab_byte_lookup; +extern const struct bench bench_htab_str_lookup; +extern const struct bench bench_htab_int_byte_lookup; +extern const struct bench bench_htab_int_str_lookup; +extern const struct bench bench_htab_int_bytes_lookup; +extern const struct bench bench_htab_int_strs_lookup; static const struct bench *benchs[] = { &bench_count_global, @@ -431,6 +439,12 @@ static const struct bench *benchs[] = { &bench_bpf_loop, &bench_strncmp_no_helper, &bench_strncmp_helper, + &bench_htab_byte_lookup, + &bench_htab_str_lookup, + &bench_htab_int_byte_lookup, + &bench_htab_int_str_lookup, + &bench_htab_int_bytes_lookup, + &bench_htab_int_strs_lookup, }; static void setup_benchmark() diff --git a/tools/testing/selftests/bpf/benchs/bench_str_htab.c b/tools/testing/selftests/bpf/benchs/bench_str_htab.c new file mode 100644 index 000000000000..6fee5701821b --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/bench_str_htab.c @@ -0,0 +1,449 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (C) 2022. Huawei Technologies Co., Ltd */ +#include +#include "bench.h" +#include "bpf_util.h" + +#define DFT_STR_KEY_SIZE 252 + +struct htab_byte_key { + char name[DFT_STR_KEY_SIZE]; +}; + +struct htab_str_key { + struct bpf_str_key_stor name; + char raw[DFT_STR_KEY_SIZE]; +}; + +struct htab_int_byte_key { + int cookie; + char name[DFT_STR_KEY_SIZE]; +}; + +struct htab_int_str_key { + int cookie; + struct bpf_str_key_stor name; + char raw[DFT_STR_KEY_SIZE]; +}; + +struct htab_int_bytes_key { + int cookie; + char name[DFT_STR_KEY_SIZE / 2]; + char addr[DFT_STR_KEY_SIZE / 2]; +}; + +struct htab_int_strs_key { + int cookie; + struct bpf_str_key_desc name; + struct bpf_str_key_desc addr; + struct bpf_str_key_stor stor; + char raw[DFT_STR_KEY_SIZE]; +}; + +#include "str_htab_bench.skel.h" + +typedef void *(*get_nth_key)(struct str_htab_bench *skel, unsigned int i); +typedef void (*set_key)(void *key); + +static const char strs[] = +"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[]^_`{|}~ "; + +static struct str_htab_ctx { + struct str_htab_bench *skel; +} ctx; + +static struct { + bool same_len; + __u32 max_entries; +} args = { + .same_len = false, + .max_entries = 1000, +}; + +enum { + ARG_SAME_LEN = 6000, + ARG_MAX_ENTRIES = 6001, +}; + +static const struct argp_option opts[] = { + { "same-len", ARG_SAME_LEN, NULL, 0, + "Use the same length for string keys" }, + { "max-entries", ARG_MAX_ENTRIES, "MAX_ENTRIES", 0, + "Set the max entries" }, + {}, +}; + +static error_t str_htab_parse_arg(int key, char *arg, struct argp_state *state) +{ + switch (key) { + case ARG_SAME_LEN: + args.same_len = true; + break; + case ARG_MAX_ENTRIES: + args.max_entries = strtoul(arg, NULL, 10); + break; + default: + return ARGP_ERR_UNKNOWN; + } + + return 0; +} + +const struct argp bench_str_htab_argp = { + .options = opts, + .parser = str_htab_parse_arg, +}; + +static void str_htab_validate(void) +{ + if (env.consumer_cnt != 1) { + fprintf(stderr, "str_htab benchmark doesn't support multi-consumer!\n"); + exit(1); + } + + if (!args.max_entries || + args.max_entries > ARRAY_SIZE(ctx.skel->bss->byte_keys)) { + fprintf(stderr, "invalid max entries (max %zu)\n", + ARRAY_SIZE(ctx.skel->bss->byte_keys)); + exit(1); + } +} + +static void setup_max_entries(struct str_htab_bench *skel, unsigned int nr) +{ + bpf_map__set_max_entries(skel->maps.byte_htab, nr); + bpf_map__set_max_entries(skel->maps.str_htab, nr); + bpf_map__set_max_entries(skel->maps.int_byte_htab, nr); + bpf_map__set_max_entries(skel->maps.int_str_htab, nr); + bpf_map__set_max_entries(skel->maps.int_bytes_htab, nr); + bpf_map__set_max_entries(skel->maps.int_strs_htab, nr); +} + +static void random_fill_str(char *str, unsigned int max_sz, unsigned int *sz) +{ + unsigned int len; + unsigned int i; + + if (args.same_len) + len = max_sz - 1; + else + len = random() % (max_sz - 1) + 1; + if (sz) + *sz = len + 1; + + /* Generate in byte-granularity to avoid zero byte */ + for (i = 0; i < len; i++) + str[i] = strs[random() % (sizeof(strs) - 1)]; + str[i] = 0; +} + +static void setup_keys(struct str_htab_bench *skel, get_nth_key getter, set_key setter) +{ + unsigned int i; + + for (i = 0; i < args.max_entries; i++) { + void *key = getter(skel, i); + + setter(key); + } +} + +static void setup_htab(struct str_htab_bench *skel, struct bpf_map *map, + get_nth_key getter) +{ + int fd = bpf_map__fd(map); + unsigned int value; + unsigned int i; + void *key; + + for (i = 0; i < args.max_entries; i++) { + int err; + + key = getter(skel, i); + value = i; + err = bpf_map_update_elem(fd, key, &value, 0); + if (err) { + fprintf(stderr, "add #%u key on %s error %d\n", + i, bpf_map__name(map), err); + exit(1); + } + } +} + +static void *byte_get_nth_key(struct str_htab_bench *skel, unsigned int i) +{ + return &skel->bss->byte_keys[i]; +} + +static void byte_set_key(void *key) +{ + struct htab_byte_key *cur = key; + + random_fill_str(cur->name, sizeof(cur->name), NULL); +} + +static void *int_byte_get_nth_key(struct str_htab_bench *skel, unsigned int i) +{ + return &skel->bss->int_byte_keys[i]; +} + +static void int_byte_set_key(void *key) +{ + struct htab_int_byte_key *cur = key; + + cur->cookie = random(); + random_fill_str(cur->name, sizeof(cur->name), NULL); +} + +static void *int_bytes_get_nth_key(struct str_htab_bench *skel, unsigned int i) +{ + return &skel->bss->int_bytes_keys[i]; +} + +static void int_bytes_set_key(void *key) +{ + struct htab_int_bytes_key *cur = key; + + cur->cookie = random(); + random_fill_str(cur->name, sizeof(cur->name), NULL); + random_fill_str(cur->addr, sizeof(cur->addr), NULL); +} + +static void *str_get_nth_key(struct str_htab_bench *skel, unsigned int i) +{ + return &skel->bss->str_keys[i]; +} + +static void str_set_key(void *key) +{ + struct htab_str_key *cur = key; + + cur->name.hash = 0; + random_fill_str(cur->raw, sizeof(cur->raw), &cur->name.len); +} + +static void *int_str_get_nth_key(struct str_htab_bench *skel, unsigned int i) +{ + return &skel->bss->int_str_keys[i]; +} + +static void int_str_set_key(void *key) +{ + struct htab_int_str_key *cur = key; + + cur->cookie = random(); + cur->name.hash = 0; + random_fill_str(cur->raw, sizeof(cur->raw), &cur->name.len); +} + +static void *int_strs_get_nth_key(struct str_htab_bench *skel, unsigned int i) +{ + return &skel->bss->int_strs_keys[i]; +} + +static void int_strs_set_key(void *key) +{ + struct htab_int_strs_key *cur = key; + unsigned int max_sz = sizeof(cur->raw) / 2; + + cur->cookie = random(); + + cur->name.offset = cur->raw - (char *)&cur->name; + random_fill_str(cur->raw, max_sz, &cur->name.len); + + cur->addr.offset = cur->raw + cur->name.len - (char *)&cur->addr; + random_fill_str(cur->raw + cur->name.len, max_sz, &cur->addr.len); + + cur->stor.hash = 0; + cur->stor.len = cur->name.len + cur->addr.len; +} + +static void str_htab_common_setup(void) +{ + struct str_htab_bench *skel; + int err; + + srandom(time(NULL)); + + setup_libbpf(); + + skel = str_htab_bench__open(); + if (!skel) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + setup_max_entries(skel, args.max_entries); + + skel->bss->loops = args.max_entries; + + err = str_htab_bench__load(skel); + if (err) { + fprintf(stderr, "failed to load skeleton\n"); + str_htab_bench__destroy(skel); + exit(1); + } + + ctx.skel = skel; +} + +static void str_htab_attach_prog(struct bpf_program *prog) +{ + struct bpf_link *link; + + link = bpf_program__attach(prog); + if (!link) { + fprintf(stderr, "failed to attach program!\n"); + exit(1); + } +} + +static void str_htab_byte_lookup_setup(void) +{ + str_htab_common_setup(); + + setup_keys(ctx.skel, byte_get_nth_key, byte_set_key); + setup_htab(ctx.skel, ctx.skel->maps.byte_htab, byte_get_nth_key); + + ctx.skel->bss->key_type = 0; + str_htab_attach_prog(ctx.skel->progs.htab_byte_lookup); +} + +static void str_htab_int_byte_lookup_setup(void) +{ + str_htab_common_setup(); + + setup_keys(ctx.skel, int_byte_get_nth_key, int_byte_set_key); + setup_htab(ctx.skel, ctx.skel->maps.int_byte_htab, int_byte_get_nth_key); + + ctx.skel->bss->key_type = 1; + str_htab_attach_prog(ctx.skel->progs.htab_byte_lookup); +} + +static void str_htab_int_bytes_lookup_setup(void) +{ + str_htab_common_setup(); + + setup_keys(ctx.skel, int_bytes_get_nth_key, int_bytes_set_key); + setup_htab(ctx.skel, ctx.skel->maps.int_bytes_htab, int_bytes_get_nth_key); + + ctx.skel->bss->key_type = 2; + str_htab_attach_prog(ctx.skel->progs.htab_byte_lookup); +} + +static void str_htab_str_lookup_setup(void) +{ + str_htab_common_setup(); + + setup_keys(ctx.skel, str_get_nth_key, str_set_key); + setup_htab(ctx.skel, ctx.skel->maps.str_htab, str_get_nth_key); + + ctx.skel->bss->key_type = 0; + str_htab_attach_prog(ctx.skel->progs.htab_str_lookup); +} + +static void str_htab_int_str_lookup_setup(void) +{ + str_htab_common_setup(); + + setup_keys(ctx.skel, int_str_get_nth_key, int_str_set_key); + setup_htab(ctx.skel, ctx.skel->maps.int_str_htab, int_str_get_nth_key); + + ctx.skel->bss->key_type = 1; + str_htab_attach_prog(ctx.skel->progs.htab_str_lookup); +} + +static void str_htab_int_strs_lookup_setup(void) +{ + str_htab_common_setup(); + + setup_keys(ctx.skel, int_strs_get_nth_key, int_strs_set_key); + setup_htab(ctx.skel, ctx.skel->maps.int_strs_htab, int_strs_get_nth_key); + + ctx.skel->bss->key_type = 2; + str_htab_attach_prog(ctx.skel->progs.htab_str_lookup); +} + +static void *str_htab_producer(void *ctx) +{ + while (true) + (void)syscall(__NR_getpgid); + return NULL; +} + +static void *str_htab_consumer(void *ctx) +{ + return NULL; +} + +static void str_htab_measure(struct bench_res *res) +{ + res->hits = atomic_swap(&ctx.skel->bss->hits, 0); + res->drops = atomic_swap(&ctx.skel->bss->drops, 0); +} + +const struct bench bench_htab_byte_lookup = { + .name = "htab-byte-lookup", + .validate = str_htab_validate, + .setup = str_htab_byte_lookup_setup, + .producer_thread = str_htab_producer, + .consumer_thread = str_htab_consumer, + .measure = str_htab_measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + +const struct bench bench_htab_int_byte_lookup = { + .name = "htab-int-byte-lookup", + .validate = str_htab_validate, + .setup = str_htab_int_byte_lookup_setup, + .producer_thread = str_htab_producer, + .consumer_thread = str_htab_consumer, + .measure = str_htab_measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + +const struct bench bench_htab_int_bytes_lookup = { + .name = "htab-int-bytes-lookup", + .validate = str_htab_validate, + .setup = str_htab_int_bytes_lookup_setup, + .producer_thread = str_htab_producer, + .consumer_thread = str_htab_consumer, + .measure = str_htab_measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + +const struct bench bench_htab_str_lookup = { + .name = "htab-str-lookup", + .validate = str_htab_validate, + .setup = str_htab_str_lookup_setup, + .producer_thread = str_htab_producer, + .consumer_thread = str_htab_consumer, + .measure = str_htab_measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + +const struct bench bench_htab_int_str_lookup = { + .name = "htab-int-str-lookup", + .validate = str_htab_validate, + .setup = str_htab_int_str_lookup_setup, + .producer_thread = str_htab_producer, + .consumer_thread = str_htab_consumer, + .measure = str_htab_measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; + +const struct bench bench_htab_int_strs_lookup = { + .name = "htab-int-strs-lookup", + .validate = str_htab_validate, + .setup = str_htab_int_strs_lookup_setup, + .producer_thread = str_htab_producer, + .consumer_thread = str_htab_consumer, + .measure = str_htab_measure, + .report_progress = hits_drops_report_progress, + .report_final = hits_drops_report_final, +}; diff --git a/tools/testing/selftests/bpf/benchs/run_htab.sh b/tools/testing/selftests/bpf/benchs/run_htab.sh new file mode 100755 index 000000000000..c848324dd256 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/run_htab.sh @@ -0,0 +1,11 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +for tp in byte str int-byte int-str int-bytes int-strs; do + name=htab-${tp}-lookup + summarize ${name} "$($RUN_BENCH ${name})" +done diff --git a/tools/testing/selftests/bpf/progs/str_htab_bench.c b/tools/testing/selftests/bpf/progs/str_htab_bench.c new file mode 100644 index 000000000000..008c654e85cb --- /dev/null +++ b/tools/testing/selftests/bpf/progs/str_htab_bench.c @@ -0,0 +1,224 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (C) 2022. Huawei Technologies Co., Ltd */ +#include +#include +#include +#include + +#define MAX_ENTRY_NR 1000 +#define DFT_STR_KEY_SIZE 252 + +struct htab_byte_key { + char name[DFT_STR_KEY_SIZE]; +}; + +struct htab_str_key { + struct bpf_str_key_stor name; + char raw[DFT_STR_KEY_SIZE]; +}; + +struct htab_int_byte_key { + int cookie; + char name[DFT_STR_KEY_SIZE]; +}; + +struct htab_int_str_key { + int cookie; + struct bpf_str_key_stor name; + char raw[DFT_STR_KEY_SIZE]; +}; + +struct htab_int_bytes_key { + int cookie; + char name[DFT_STR_KEY_SIZE / 2]; + char addr[DFT_STR_KEY_SIZE / 2]; +}; + +struct htab_int_strs_key { + int cookie; + struct bpf_str_key_desc name; + struct bpf_str_key_desc addr; + struct bpf_str_key_stor stor; + char raw[DFT_STR_KEY_SIZE]; +}; + +/* max_entries will be set by htab benchmark */ +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __type(key, struct htab_byte_key); + __uint(value_size, 4); + __type(value, __u32); +} byte_htab SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __type(key, struct htab_int_byte_key); + __type(value, __u32); +} int_byte_htab SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __type(key, struct htab_int_bytes_key); + __type(value, __u32); +} int_bytes_htab SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __type(key, struct htab_str_key); + __type(value, __u32); + __uint(map_flags, BPF_F_STR_IN_KEY); +} str_htab SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __type(key, struct htab_int_str_key); + __type(value, __u32); + __uint(map_flags, BPF_F_STR_IN_KEY); +} int_str_htab SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __type(key, struct htab_int_strs_key); + __type(value, __u32); + __uint(map_flags, BPF_F_STR_IN_KEY); +} int_strs_htab SEC(".maps"); + +char _license[] SEC("license") = "GPL"; + +struct htab_byte_key byte_keys[MAX_ENTRY_NR]; +struct htab_str_key str_keys[MAX_ENTRY_NR]; +struct htab_int_byte_key int_byte_keys[MAX_ENTRY_NR]; +struct htab_int_str_key int_str_keys[MAX_ENTRY_NR]; +struct htab_int_bytes_key int_bytes_keys[MAX_ENTRY_NR]; +struct htab_int_strs_key int_strs_keys[MAX_ENTRY_NR]; + +unsigned int loops = 0; +unsigned int key_type = 0; +long hits = 0; +long drops = 0; + +static int lookup_byte(__u32 index, void *data) +{ + unsigned int *value; + + if (index >= MAX_ENTRY_NR) + return 1; + + value = bpf_map_lookup_elem(&byte_htab, &byte_keys[index]); + if (value && *value == index) + __sync_add_and_fetch(&hits, 1); + else + __sync_add_and_fetch(&drops, 1); + + return 0; +} + +static int lookup_int_byte(__u32 index, void *data) +{ + unsigned int *value; + + if (index >= MAX_ENTRY_NR) + return 1; + + value = bpf_map_lookup_elem(&int_byte_htab, &int_byte_keys[index]); + if (value && *value == index) + __sync_add_and_fetch(&hits, 1); + else + __sync_add_and_fetch(&drops, 1); + + return 0; +} + +static int lookup_int_bytes(__u32 index, void *data) +{ + unsigned int *value; + + if (index >= MAX_ENTRY_NR) + return 1; + + value = bpf_map_lookup_elem(&int_bytes_htab, &int_bytes_keys[index]); + if (value && *value == index) + __sync_add_and_fetch(&hits, 1); + else + __sync_add_and_fetch(&drops, 1); + + return 0; +} + +static int lookup_str(__u32 index, void *data) +{ + unsigned int *value; + + if (index >= MAX_ENTRY_NR) + return 1; + + /* Clear the hash value from previous lookup */ + str_keys[index].name.hash = 0; + value = bpf_map_lookup_elem(&str_htab, &str_keys[index]); + if (value && *value == index) + __sync_add_and_fetch(&hits, 1); + else + __sync_add_and_fetch(&drops, 1); + + return 0; +} + +static int lookup_int_str(__u32 index, void *data) +{ + unsigned int *value; + + if (index >= MAX_ENTRY_NR) + return 1; + + int_str_keys[index].name.hash = 0; + value = bpf_map_lookup_elem(&int_str_htab, &int_str_keys[index]); + if (value && *value == index) + __sync_add_and_fetch(&hits, 1); + else + __sync_add_and_fetch(&drops, 1); + + return 0; +} + +static int lookup_int_strs(__u32 index, void *data) +{ + unsigned int *value; + + if (index >= MAX_ENTRY_NR) + return 1; + + int_strs_keys[index].stor.hash = 0; + value = bpf_map_lookup_elem(&int_strs_htab, &int_strs_keys[index]); + if (value && *value == index) + __sync_add_and_fetch(&hits, 1); + else + __sync_add_and_fetch(&drops, 1); + + return 0; +} + +SEC("tp/syscalls/sys_enter_getpgid") +int htab_byte_lookup(void *ctx) +{ + if (!key_type) + bpf_loop(loops, lookup_byte, NULL, 0); + else if (key_type == 1) + bpf_loop(loops, lookup_int_byte, NULL, 0); + else + bpf_loop(loops, lookup_int_bytes, NULL, 0); + + return 0; +} + +SEC("tp/syscalls/sys_enter_getpgid") +int htab_str_lookup(void *ctx) +{ + if (!key_type) + bpf_loop(loops, lookup_str, NULL, 0); + else if (key_type == 1) + bpf_loop(loops, lookup_int_str, NULL, 0); + else + bpf_loop(loops, lookup_int_strs, NULL, 0); + + return 0; +}