From patchwork Sun Jan 17 04:22:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cong Wang X-Patchwork-Id: 12025183 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 61D9FC433DB for ; Sun, 17 Jan 2021 04:24:31 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 33952225AB for ; Sun, 17 Jan 2021 04:24:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727407AbhAQEX4 (ORCPT ); Sat, 16 Jan 2021 23:23:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40930 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727090AbhAQEXU (ORCPT ); Sat, 16 Jan 2021 23:23:20 -0500 Received: from mail-ot1-x333.google.com (mail-ot1-x333.google.com [IPv6:2607:f8b0:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 20C31C061574; Sat, 16 Jan 2021 20:22:40 -0800 (PST) Received: by mail-ot1-x333.google.com with SMTP id 36so1415770otp.2; Sat, 16 Jan 2021 20:22:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=FilOqU2/8IEPlywLXYh9C2/8g/8mluZH29uqfe7Haic=; b=ChZk8agQsrKToBCTAwGLlTos25BscQVwIGkYSJpQr+5P9Mm/IwuqCwPym4kv9chlht xE+2uuScSfp8q+QazswDFtM3p5LUtXhCcbRcJKn9lM8uWex+3/U2Qchi3e7D+tpz6gw5 pIxulfrL4ZhEHtTx4hN8JA/eerSD3+oAaTdcIvrEyQacm+8QGbOqR5RR64HJeBroc83V BSziPyYFlB0L7rm1A7Fg6JC589Jv3zVeR3yV013oUp99EUXemsHbgnjCd4Hvkgz94jaW 2kmcXGArq+Edyr5kljvSNkhF5S/ltbdWRN4KgvSAf0synUCQn/aag+awqBvln+Pnbo// D8uA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=FilOqU2/8IEPlywLXYh9C2/8g/8mluZH29uqfe7Haic=; b=rTkE0kaKey8QxhOQCSahdm6AkgKVYU4A3c3Fnfls96SOrUyAtX1H3YqE8GWRk6WtBv s2nY4qzKuHOMiqf1h9KMbbrEJHqWIuVA//pHPbq4+KhF/snJJrxKAojLE4OHdHyHdebV psMNi8hsTZfUvhJjeAOWuD5s7gKxP3mEhOmTmf6Pb8RXnpJTjBmy7bdDoqTSyterAtE/ AawsEvedeJ0woUI41LZjeX5H/r9yd3JWQkBxXWrZBvTawUnZYN0N45d/3Db7eeGOuDWa KzmqjLmUGrvo/offvIVRbdEyflb51jRI5HtQoiuvNqr8na86XgFFc/Lzx12A1pKDBQLl Tn6A== X-Gm-Message-State: AOAM531id0opJNR0M5ASsOZaaxDbRhnUIqcdDTLzhhlXMTE8OF2owmhV QgkBRdTcvStCCsK7WL5KGjZG3jMX42sREw== X-Google-Smtp-Source: ABdhPJyvsbCM4+CcYv6YoySWqeva2yQUMNiOAhxmiZH8Tfh7o5P6aX5N6yJCC7+arJm9LxG+8sQdTw== X-Received: by 2002:a9d:3ef6:: with SMTP id b109mr13989477otc.288.1610857359178; Sat, 16 Jan 2021 20:22:39 -0800 (PST) Received: from unknown.attlocal.net ([2600:1700:65a0:ab60:1c14:d05:b7d:917b]) by smtp.gmail.com with ESMTPSA id l8sm537444ota.9.2021.01.16.20.22.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 16 Jan 2021 20:22:38 -0800 (PST) From: Cong Wang To: netdev@vger.kernel.org Cc: bpf@vger.kernel.org, Cong Wang , Andrii Nakryiko , Alexei Starovoitov , Daniel Borkmann , Dongdong Wang Subject: [Patch bpf-next v4 1/3] bpf: introduce timeout hash map Date: Sat, 16 Jan 2021 20:22:22 -0800 Message-Id: <20210117042224.17839-2-xiyou.wangcong@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210117042224.17839-1-xiyou.wangcong@gmail.com> References: <20210117042224.17839-1-xiyou.wangcong@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net From: Cong Wang This borrows the idea from conntrack and will be used for conntrack in ebpf too. Each element in a timeout map has a user-specified timeout in msecs, after it expires it will be automatically removed from the map. Cilium already does the same thing, it uses a regular map or LRU map to track connections and has its own GC in user-space. This does not scale well when we have millions of connections, as each removal needs a syscall. Even if we could batch the operations, it still needs to copy a lot of data between kernel and user space. There are two cases to consider here: 1. When the timeout map is idle, i.e. no one updates or accesses it, we rely on the delayed work to scan the whole hash table and remove these expired. The delayed work is scheduled every 1 sec when idle, which is also what conntrack uses. It is fine to scan the whole table as we do not actually remove elements during this scan, instead we simply queue them to the lockless list and defer all the removals to the next schedule. 2. When the timeout map is actively accessed, we could reach expired elements before the idle work automatically scans them, we can simply skip them and schedule the delayed work immediately to do the actual removals. We have to avoid taking locks on fast path. The timeout of an element can be set or updated via bpf_map_update_elem() and we reuse the upper 32-bit of the 64-bit flag for the timeout value, as there are only a few bits are used currently. Note, a zero timeout means to expire immediately. To avoid adding memory overhead to regular map, we have to reuse some field in struct htab_elem, that is, lru_node. Otherwise we would have to rewrite a lot of code. For now, batch ops is not supported, we can add it later if needed. Cc: Andrii Nakryiko Cc: Alexei Starovoitov Cc: Daniel Borkmann Cc: Dongdong Wang Signed-off-by: Cong Wang --- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 5 +- kernel/bpf/hashtab.c | 239 ++++++++++++++++++++++++++++++++- kernel/bpf/syscall.c | 3 +- tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 240 insertions(+), 9 deletions(-) diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h index 99f7fd657d87..00a3b17b6af2 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_TIMEOUT_HASH, htab_timeout_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 c001766adcbc..9c9d8c194b39 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -164,6 +164,7 @@ enum bpf_map_type { BPF_MAP_TYPE_RINGBUF, BPF_MAP_TYPE_INODE_STORAGE, BPF_MAP_TYPE_TASK_STORAGE, + BPF_MAP_TYPE_TIMEOUT_HASH, }; /* Note that tracing related programs such as @@ -399,7 +400,9 @@ enum bpf_link_type { */ #define BPF_PSEUDO_CALL 1 -/* flags for BPF_MAP_UPDATE_ELEM command */ +/* flags for BPF_MAP_UPDATE_ELEM command, upper 32 bits are timeout for + * BPF_MAP_TYPE_TIMEOUT_HASH (in milliseconds). + */ enum { BPF_ANY = 0, /* create new element or update existing */ BPF_NOEXIST = 1, /* create new element if it didn't exist */ diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index c1ac7f964bc9..1347d782eb1d 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -8,6 +8,8 @@ #include #include #include +#include +#include #include #include #include "percpu_freelist.h" @@ -104,6 +106,8 @@ struct bpf_htab { u32 hashrnd; struct lock_class_key lockdep_key; int __percpu *map_locked[HASHTAB_MAP_LOCK_COUNT]; + struct llist_head gc_list; + struct delayed_work gc_work; }; /* each htab element is struct htab_elem + key + value */ @@ -122,6 +126,11 @@ struct htab_elem { union { struct rcu_head rcu; struct bpf_lru_node lru_node; + struct { + u64 expires; /* in jiffies64 */ + struct llist_node gc_node; + atomic_t pending; + }; }; u32 hash; char key[] __aligned(8); @@ -429,6 +438,31 @@ static int htab_map_alloc_check(union bpf_attr *attr) return 0; } +static bool htab_elem_expired(struct htab_elem *e) +{ + return time_after_eq64(get_jiffies_64(), e->expires); +} + +/* Schedule GC to remove an expired element, unless it is already pending. */ +static void htab_gc_elem(struct bpf_htab *htab, struct htab_elem *e) +{ + if (atomic_xchg(&e->pending, 1)) + return; + llist_add(&e->gc_node, &htab->gc_list); + queue_delayed_work(system_unbound_wq, &htab->gc_work, 0); +} + +/* GC an element if it has been expired, return whether the element is expired + * or not. + */ +static bool htab_expire_elem(struct bpf_htab *htab, struct htab_elem *e) +{ + if (!htab_elem_expired(e)) + return false; + htab_gc_elem(htab, e); + return true; +} + static struct bpf_map *htab_map_alloc(union bpf_attr *attr) { bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH || @@ -730,6 +764,7 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node) 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); + bool is_timeout = map->map_type == BPF_MAP_TYPE_TIMEOUT_HASH; struct hlist_nulls_head *head; struct htab_elem *l, *next_l; u32 hash, key_size; @@ -757,6 +792,8 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) struct htab_elem, hash_node); if (next_l) { + if (is_timeout && htab_expire_elem(htab, next_l)) + goto find_first_elem; /* if next elem in this hash list is non-zero, just return it */ memcpy(next_key, next_l->key, key_size); return 0; @@ -775,6 +812,8 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_first_rcu(head)), struct htab_elem, hash_node); if (next_l) { + if (is_timeout && htab_expire_elem(htab, next_l)) + continue; /* if it's not empty, just return it */ memcpy(next_key, next_l->key, key_size); return 0; @@ -877,6 +916,7 @@ static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab) static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, void *value, u32 key_size, u32 hash, bool percpu, bool onallcpus, + bool timeout_map, struct htab_elem *old_elem) { u32 size = htab->map.value_size; @@ -952,6 +992,8 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, value); } + if (timeout_map) + atomic_set(&l_new->pending, 0); l_new->hash = hash; return l_new; dec_count: @@ -973,18 +1015,37 @@ static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old, return 0; } +static u64 msecs_to_expire(u32 ms) +{ + u64 tmp = ms * NSEC_PER_MSEC; + + return nsecs_to_jiffies64(tmp) + get_jiffies_64(); +} + +static u32 fetch_timeout(u64 *map_flags) +{ + u32 timeout = (*map_flags) >> 32; + + *map_flags = (*map_flags) & 0xffffffff; + return timeout; +} + /* Called from syscall or from eBPF program */ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags) { struct bpf_htab *htab = container_of(map, struct bpf_htab, map); + bool timeout_map = map->map_type == BPF_MAP_TYPE_TIMEOUT_HASH; struct htab_elem *l_new = NULL, *l_old; struct hlist_nulls_head *head; unsigned long flags; struct bucket *b; u32 key_size, hash; + u32 timeout; int ret; + timeout = fetch_timeout(&map_flags); + if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST)) /* unknown flags */ return -EINVAL; @@ -1012,6 +1073,8 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, copy_map_value_locked(map, l_old->key + round_up(key_size, 8), value, false); + if (timeout_map) + l_old->expires = msecs_to_expire(timeout); return 0; } /* fall through, grab the bucket lock and lookup again. @@ -1040,26 +1103,35 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, copy_map_value_locked(map, l_old->key + round_up(key_size, 8), value, false); + if (timeout_map) + l_old->expires = msecs_to_expire(timeout); ret = 0; goto err; } l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false, - l_old); + timeout_map, l_old); if (IS_ERR(l_new)) { /* all pre-allocated elements are in use or memory exhausted */ ret = PTR_ERR(l_new); goto err; } + if (timeout_map) + l_new->expires = msecs_to_expire(timeout); + /* add new element to the head of the list, so that * concurrent search will find it before old elem */ hlist_nulls_add_head_rcu(&l_new->hash_node, head); if (l_old) { - hlist_nulls_del_rcu(&l_old->hash_node); - if (!htab_is_prealloc(htab)) - free_htab_elem(htab, l_old); + if (timeout_map) { + htab_gc_elem(htab, l_old); + } else { + hlist_nulls_del_rcu(&l_old->hash_node); + if (!htab_is_prealloc(htab)) + free_htab_elem(htab, l_old); + } } ret = 0; err: @@ -1173,7 +1245,7 @@ static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key, value, onallcpus); } else { l_new = alloc_htab_elem(htab, key, value, key_size, - hash, true, onallcpus, NULL); + hash, true, onallcpus, false, NULL); if (IS_ERR(l_new)) { ret = PTR_ERR(l_new); goto err; @@ -1269,6 +1341,7 @@ static int htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key, static int htab_map_delete_elem(struct bpf_map *map, void *key) { struct bpf_htab *htab = container_of(map, struct bpf_htab, map); + bool is_timeout = map->map_type == BPF_MAP_TYPE_TIMEOUT_HASH; struct hlist_nulls_head *head; struct bucket *b; struct htab_elem *l; @@ -1291,8 +1364,14 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key) l = lookup_elem_raw(head, hash, key, key_size); if (l) { - hlist_nulls_del_rcu(&l->hash_node); - free_htab_elem(htab, l); + if (is_timeout) { + if (htab_elem_expired(l)) + ret = -ENOENT; + htab_gc_elem(htab, l); + } else { + hlist_nulls_del_rcu(&l->hash_node); + free_htab_elem(htab, l); + } } else { ret = -ENOENT; } @@ -2178,3 +2257,149 @@ const struct bpf_map_ops htab_of_maps_map_ops = { .map_btf_name = "bpf_htab", .map_btf_id = &htab_of_maps_map_btf_id, }; + +#define HTAB_GC_INTERVAL HZ + +static void htab_gc(struct work_struct *work) +{ + struct htab_elem *e, *tmp; + struct llist_node *lhead; + struct bpf_htab *htab; + int i, count; + + htab = container_of(work, struct bpf_htab, gc_work.work); + lhead = llist_del_all(&htab->gc_list); + + llist_for_each_entry_safe(e, tmp, lhead, gc_node) { + unsigned long flags; + struct bucket *b; + u32 hash; + + hash = e->hash; + b = __select_bucket(htab, hash); + if (htab_lock_bucket(htab, b, hash, &flags)) + continue; + hlist_nulls_del_rcu(&e->hash_node); + atomic_set(&e->pending, 0); + free_htab_elem(htab, e); + htab_unlock_bucket(htab, b, hash, flags); + + cond_resched(); + } + + for (count = 0, i = 0; i < htab->n_buckets; i++) { + struct hlist_nulls_head *head; + struct hlist_nulls_node *n; + struct htab_elem *l; + + rcu_read_lock(); + head = select_bucket(htab, i); + hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) + if (htab_expire_elem(htab, l)) + count++; + rcu_read_unlock(); + + cond_resched(); + } + + queue_delayed_work(system_unbound_wq, &htab->gc_work, + count ? 0 : HTAB_GC_INTERVAL); +} + +static void *__htab_timeout_map_lookup_elem(struct bpf_map *map, void *key) +{ + struct bpf_htab *htab = container_of(map, struct bpf_htab, map); + struct htab_elem *l; + + l = __htab_map_lookup_elem(map, key); + if (l && htab_expire_elem(htab, l)) + l = NULL; + + return l; +} + +static void *htab_timeout_map_lookup_elem(struct bpf_map *map, void *key) +{ + struct htab_elem *l = __htab_timeout_map_lookup_elem(map, key); + + if (l) + return l->key + round_up(map->key_size, 8); + return NULL; +} + +static int htab_timeout_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) +{ + struct bpf_insn *insn = insn_buf; + const int ret = BPF_REG_0; + + BUILD_BUG_ON(!__same_type(&__htab_timeout_map_lookup_elem, + (void *(*)(struct bpf_map *map, void *key))NULL)); + *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_timeout_map_lookup_elem)); + *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1); + *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, + offsetof(struct htab_elem, key) + + round_up(map->key_size, 8)); + return insn - insn_buf; +} + +static void htab_timeout_map_seq_show_elem(struct bpf_map *map, void *key, + struct seq_file *m) +{ + void *value; + + rcu_read_lock(); + + value = htab_timeout_map_lookup_elem(map, key); + if (!value) { + rcu_read_unlock(); + return; + } + + btf_type_seq_show(map->btf, map->btf_key_type_id, key, m); + seq_puts(m, ": "); + btf_type_seq_show(map->btf, map->btf_value_type_id, value, m); + seq_puts(m, "\n"); + + rcu_read_unlock(); +} + +static struct bpf_map *htab_timeout_map_alloc(union bpf_attr *attr) +{ + struct bpf_map *map = htab_map_alloc(attr); + struct bpf_htab *htab; + + if (!IS_ERR(map)) { + htab = container_of(map, struct bpf_htab, map); + init_llist_head(&htab->gc_list); + INIT_DEFERRABLE_WORK(&htab->gc_work, htab_gc); + queue_delayed_work(system_unbound_wq, &htab->gc_work, + HTAB_GC_INTERVAL); + } + + return map; +} + +static void htab_timeout_map_free(struct bpf_map *map) +{ + struct bpf_htab *htab = container_of(map, struct bpf_htab, map); + + cancel_delayed_work_sync(&htab->gc_work); + htab_map_free(map); +} + +static int htab_timeout_map_btf_id; +const struct bpf_map_ops htab_timeout_map_ops = { + .map_meta_equal = bpf_map_meta_equal, + .map_alloc_check = htab_map_alloc_check, + .map_alloc = htab_timeout_map_alloc, + .map_free = htab_timeout_map_free, + .map_get_next_key = htab_map_get_next_key, + .map_lookup_elem = htab_timeout_map_lookup_elem, + .map_update_elem = htab_map_update_elem, + .map_delete_elem = htab_map_delete_elem, + .map_gen_lookup = htab_timeout_map_gen_lookup, + .map_seq_show_elem = htab_timeout_map_seq_show_elem, + .map_btf_name = "bpf_htab", + .map_btf_id = &htab_timeout_map_btf_id, + .iter_seq_info = &iter_seq_info, +}; diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index c3bb03c8371f..2df15535895a 100644 --- a/kernel/bpf/syscall.c +++ b/kernel/bpf/syscall.c @@ -777,7 +777,8 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf, map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE && map->map_type != BPF_MAP_TYPE_SK_STORAGE && map->map_type != BPF_MAP_TYPE_INODE_STORAGE && - map->map_type != BPF_MAP_TYPE_TASK_STORAGE) + map->map_type != BPF_MAP_TYPE_TASK_STORAGE && + map->map_type != BPF_MAP_TYPE_TIMEOUT_HASH) return -ENOTSUPP; if (map->spin_lock_off + sizeof(struct bpf_spin_lock) > map->value_size) { diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h index c001766adcbc..ac6ddfd7bddc 100644 --- a/tools/include/uapi/linux/bpf.h +++ b/tools/include/uapi/linux/bpf.h @@ -164,6 +164,7 @@ enum bpf_map_type { BPF_MAP_TYPE_RINGBUF, BPF_MAP_TYPE_INODE_STORAGE, BPF_MAP_TYPE_TASK_STORAGE, + BPF_MAP_TYPE_TIMEOUT_HASH, }; /* Note that tracing related programs such as From patchwork Sun Jan 17 04:22:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cong Wang X-Patchwork-Id: 12025181 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1AE5FC433E9 for ; Sun, 17 Jan 2021 04:23:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DE73122597 for ; Sun, 17 Jan 2021 04:23:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727992AbhAQEXf (ORCPT ); Sat, 16 Jan 2021 23:23:35 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40936 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727407AbhAQEXV (ORCPT ); Sat, 16 Jan 2021 23:23:21 -0500 Received: from mail-ot1-x32b.google.com (mail-ot1-x32b.google.com [IPv6:2607:f8b0:4864:20::32b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 257F3C061575; Sat, 16 Jan 2021 20:22:41 -0800 (PST) Received: by mail-ot1-x32b.google.com with SMTP id 34so2106661otd.5; Sat, 16 Jan 2021 20:22:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=wM+spvP29mz4ZWD9AjIFNRY5IWLk+XxdpQKy6IXwsy4=; b=Efz4ZMFSW16RIsCIQxz/wNM5l1r2HB4rc2niPTQBOYcV16lgfHr2KZcEpem0elc77w gB4IS/aX+0s3L6lvOBEukuUlt6/zh8X85Yz1hLAvvSg4CjjAluxIIxj0eexQmTOYieeR mXFVKqBgHx6m7kBhPCRBLYH8hHT1C9TnqDjOwOHIx5/q9RktHUQtS3ZzaAfjrdMjk5s6 1xCfXcpHZvwylfBACwrwlHFDwNgtFYSg2xZWxiHvBzo+onunZjedjPxDQYjguuSWRHE+ RpGNvAXDujQGYmSIdzdMZCkr2ZU/Z8qJ4gV8OngwkBI2Crqsc6Ye9mfyoXFsUd1T5cAv ANww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=wM+spvP29mz4ZWD9AjIFNRY5IWLk+XxdpQKy6IXwsy4=; b=UgfyqdBhHS8oDiqmnxW8RcRRwzaHa9xO6DQT0DB3Uqs3+qKkwt0uKT6Q1jbICimoWU UYnrIBvjtriq96juDtAEf4CkRt+PoqB+4dCxeLUi82P5rfULuCbeMhsDOc7PpLXJrU77 vngC9HJHowhXXBfDaF1W0MRZasxtY9A+0/qJvKWIWSSemCGGrFcM7tmLPemrko4QX/Ue U4pcr7nlAqp3jcGCEfQ2/Nfqie8JiF5+XL7NHyJ78zz+aSPwNRuhGM+AwECwiWbXbSpv IuWGY6Pn+DPiliDbIlgKl4Bm5Xs8hqjqHTtIJNaglBKxnEPAA6tie+FO3Lumd3PD5V+N ZwOg== X-Gm-Message-State: AOAM532MKZTDdqb6Fn00wngdcStOStKc/HMgBwXF+BwmKR4ePUVElJ58 hOJhllzd923+GBwXQEKY3rUc7mq4k+tKhw== X-Google-Smtp-Source: ABdhPJxVwxiNgcdyUhTQNBu4r8E/7uJYyYSzJisMT1mcUbeGD3GOfBSLhMd7CX263EsmVRzpoaV3EQ== X-Received: by 2002:a9d:372:: with SMTP id 105mr13386480otv.118.1610857360407; Sat, 16 Jan 2021 20:22:40 -0800 (PST) Received: from unknown.attlocal.net ([2600:1700:65a0:ab60:1c14:d05:b7d:917b]) by smtp.gmail.com with ESMTPSA id l8sm537444ota.9.2021.01.16.20.22.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 16 Jan 2021 20:22:39 -0800 (PST) From: Cong Wang To: netdev@vger.kernel.org Cc: bpf@vger.kernel.org, Cong Wang , Alexei Starovoitov , Daniel Borkmann , Dongdong Wang Subject: [Patch bpf-next v4 2/3] selftests/bpf: add test cases for bpf timeout map Date: Sat, 16 Jan 2021 20:22:23 -0800 Message-Id: <20210117042224.17839-3-xiyou.wangcong@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210117042224.17839-1-xiyou.wangcong@gmail.com> References: <20210117042224.17839-1-xiyou.wangcong@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net From: Cong Wang Add some test cases in test_maps.c for timeout map, which focus on testing timeout. Cc: Alexei Starovoitov Cc: Daniel Borkmann Cc: Dongdong Wang Signed-off-by: Cong Wang --- tools/testing/selftests/bpf/test_maps.c | 47 +++++++++++++++++++++++++ 1 file changed, 47 insertions(+) diff --git a/tools/testing/selftests/bpf/test_maps.c b/tools/testing/selftests/bpf/test_maps.c index 51adc42b2b40..5e443d76512b 100644 --- a/tools/testing/selftests/bpf/test_maps.c +++ b/tools/testing/selftests/bpf/test_maps.c @@ -639,6 +639,52 @@ static void test_stackmap(unsigned int task, void *data) close(fd); } +static void test_timeout_map(unsigned int task, void *data) +{ + int val1 = 1, val2 = 2, val3 = 3; + int key1 = 1, key2 = 2, key3 = 3; + int fd; + + fd = bpf_create_map(BPF_MAP_TYPE_TIMEOUT_HASH, sizeof(int), sizeof(int), + 3, map_flags); + if (fd < 0) { + printf("Failed to create timeout map '%s'!\n", strerror(errno)); + exit(1); + } + + /* Timeout after 1 secs */ + assert(bpf_map_update_elem(fd, &key1, &val1, (u64)1000<<32) == 0); + /* Timeout after 2 secs */ + assert(bpf_map_update_elem(fd, &key2, &val2, (u64)2000<<32) == 0); + /* Timeout after 10 secs */ + assert(bpf_map_update_elem(fd, &key3, &val3, (u64)10000<<32) == 0); + + sleep(1); + assert(bpf_map_lookup_elem(fd, &key1, &val1) != 0); + val2 = 0; + assert(bpf_map_lookup_elem(fd, &key2, &val2) == 0 && val2 == 2); + + sleep(1); + assert(bpf_map_lookup_elem(fd, &key1, &val1) != 0); + assert(bpf_map_lookup_elem(fd, &key2, &val2) != 0); + + /* Modify timeout to expire it earlier */ + val3 = 0; + assert(bpf_map_lookup_elem(fd, &key3, &val3) == 0 && val3 == 3); + assert(bpf_map_update_elem(fd, &key3, &val3, (u64)1000<<32) == 0); + sleep(1); + assert(bpf_map_lookup_elem(fd, &key3, &val3) != 0); + + /* Add one elem expired immediately and try to delete this expired */ + assert(bpf_map_update_elem(fd, &key3, &val3, 0) == 0); + assert(bpf_map_delete_elem(fd, &key3) == -1 && errno == ENOENT); + + /* Add one elem and let the map removal clean up */ + assert(bpf_map_update_elem(fd, &key3, &val3, (u64)10000<<32) == 0); + + close(fd); +} + #include #include #include @@ -1305,6 +1351,7 @@ static void test_map_stress(void) run_parallel(100, test_arraymap, NULL); run_parallel(100, test_arraymap_percpu, NULL); + run_parallel(100, test_timeout_map, NULL); } #define TASKS 1024 From patchwork Sun Jan 17 04:22:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cong Wang X-Patchwork-Id: 12025179 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 28A66C433E0 for ; Sun, 17 Jan 2021 04:23:47 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 05A3822581 for ; Sun, 17 Jan 2021 04:23:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727087AbhAQEXe (ORCPT ); Sat, 16 Jan 2021 23:23:34 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40944 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727629AbhAQEXX (ORCPT ); Sat, 16 Jan 2021 23:23:23 -0500 Received: from mail-oi1-x230.google.com (mail-oi1-x230.google.com [IPv6:2607:f8b0:4864:20::230]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 99AB4C061757; Sat, 16 Jan 2021 20:22:42 -0800 (PST) Received: by mail-oi1-x230.google.com with SMTP id d203so14205904oia.0; Sat, 16 Jan 2021 20:22:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=6cUrGuJbAAzbmOZxLUmIXIAt0gGPRKf0H8ukS5QNZuo=; b=Jd2EBia9tnghecfC5Dbu+OMDe9c8JNmsik+oPtczPwrpfvS8Dfhj2xkPzojPoAXlYv ZoDP9AxxK3r7N/qX8VrHYJ7rFrIypWuI7/nLxovXDiTdTgn2JvYoDHgdPutTAxxdOe9m 02wPjrSeRYhqVYc6Aurt/ANHE5FOZv5/kvNhlQipqHHkbTIBlWgICXZo2aP5jcWuPCz+ EAA2CsIYYzBUTfx5oGVtg9wZMLoxwGUwPgxtSJ1pNUI2ZlbtBfc31CnN7HD6Dh8HIoqY 75fE1SQQKA2LPjXrFCYNI4U1RpKwZaVlitS9hY5K8OUy4FQKIZeayh8z8FkD697Q8YD0 kKPA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=6cUrGuJbAAzbmOZxLUmIXIAt0gGPRKf0H8ukS5QNZuo=; b=DncPz+C2XTP14/wCA+GJU5i4pVV5xiDLRccfIQJ9YiJL/O0LfXL/SL2qkxC1kBzX3X 4ZTiVu3ieIA/IAhxlPebnnplTGUlRcFsgBDu/upk9jb6qoGVO/p1tfYQ7DT+lhVc4ITy 2wyoobP7Tjsel7CPtxgMAfhhyAkE+tXXHGgHPlJBcsZNNFbgsURQRVJpr+NWt24vYLG6 ASOrLe9+NOFg+u3Vf+IdI2oRntYq72vMAXLyxjnW7E4IAxRhcdz91brF6yrcUqfAm0IX bzkotI4qSgXijbzzk3LsZNqhWqJkEeVBGxzoyj90tAt5X4PAOgfIcX8TeTSo4rwpcWml a2MA== X-Gm-Message-State: AOAM532+CO4+nVaxc0QU6ZSpFG9tPEtAs+JUmwAd2ncwszihMhCjAtup yWBpvJX3++qPD7rWnhygOrVMXsguYyECMA== X-Google-Smtp-Source: ABdhPJxkieVF8AWr9ff/GYSZamkS5xJ/OoIXpsYP/hMerLx95TLPHXfu2zkKsF2ursROiaA3J0NFBQ== X-Received: by 2002:aca:5f07:: with SMTP id t7mr9475748oib.39.1610857361782; Sat, 16 Jan 2021 20:22:41 -0800 (PST) Received: from unknown.attlocal.net ([2600:1700:65a0:ab60:1c14:d05:b7d:917b]) by smtp.gmail.com with ESMTPSA id l8sm537444ota.9.2021.01.16.20.22.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 16 Jan 2021 20:22:41 -0800 (PST) From: Cong Wang To: netdev@vger.kernel.org Cc: bpf@vger.kernel.org, Cong Wang , Andrey Ignatov , Alexei Starovoitov , Daniel Borkmann , Dongdong Wang Subject: [Patch bpf-next v4 3/3] selftests/bpf: add timeout map check in map_ptr tests Date: Sat, 16 Jan 2021 20:22:24 -0800 Message-Id: <20210117042224.17839-4-xiyou.wangcong@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20210117042224.17839-1-xiyou.wangcong@gmail.com> References: <20210117042224.17839-1-xiyou.wangcong@gmail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net From: Cong Wang Similar to regular hashmap test. Acked-by: Andrey Ignatov Cc: Alexei Starovoitov Cc: Daniel Borkmann Cc: Dongdong Wang Signed-off-by: Cong Wang --- .../selftests/bpf/progs/map_ptr_kern.c | 20 +++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/map_ptr_kern.c b/tools/testing/selftests/bpf/progs/map_ptr_kern.c index d8850bc6a9f1..424a9e76c93f 100644 --- a/tools/testing/selftests/bpf/progs/map_ptr_kern.c +++ b/tools/testing/selftests/bpf/progs/map_ptr_kern.c @@ -648,6 +648,25 @@ static inline int check_ringbuf(void) return 1; } +struct { + __uint(type, BPF_MAP_TYPE_TIMEOUT_HASH); + __uint(max_entries, MAX_ENTRIES); + __type(key, __u32); + __type(value, __u32); +} m_timeout SEC(".maps"); + +static inline int check_timeout_hash(void) +{ + struct bpf_htab *timeout_hash = (struct bpf_htab *)&m_timeout; + struct bpf_map *map = (struct bpf_map *)&m_timeout; + + VERIFY(check_default(&timeout_hash->map, map)); + VERIFY(timeout_hash->n_buckets == MAX_ENTRIES); + VERIFY(timeout_hash->elem_size == 64); + + return 1; +} + SEC("cgroup_skb/egress") int cg_skb(void *ctx) { @@ -679,6 +698,7 @@ int cg_skb(void *ctx) VERIFY_TYPE(BPF_MAP_TYPE_SK_STORAGE, check_sk_storage); VERIFY_TYPE(BPF_MAP_TYPE_DEVMAP_HASH, check_devmap_hash); VERIFY_TYPE(BPF_MAP_TYPE_RINGBUF, check_ringbuf); + VERIFY_TYPE(BPF_MAP_TYPE_TIMEOUT_HASH, check_timeout_hash); return 1; }