| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 22 Nov 2022 12:01:23 +0800
From: Hou Tao <houtao1@...wei.com>
To: Tonghao Zhang <xiangxia.m.yue@...il.com>
CC: <netdev@...r.kernel.org>, Alexei Starovoitov <ast@...nel.org>,
Daniel Borkmann <daniel@...earbox.net>,
Andrii Nakryiko <andrii@...nel.org>,
Martin KaFai Lau <martin.lau@...ux.dev>,
Song Liu <song@...nel.org>, Yonghong Song <yhs@...com>,
John Fastabend <john.fastabend@...il.com>,
KP Singh <kpsingh@...nel.org>,
Stanislav Fomichev <sdf@...gle.com>,
Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>,
bpf <bpf@...r.kernel.org>
Subject: Re: [net-next] bpf: avoid hashtab deadlock with try_lock
Hi,
On 11/22/2022 11:12 AM, Tonghao Zhang wrote:
> .
>
> On Tue, Nov 22, 2022 at 9:16 AM Hou Tao <houtao1@...wei.com> wrote:
>> Hi,
>>
>> On 11/21/2022 6:05 PM, xiangxia.m.yue@...il.com wrote:
>>> From: Tonghao Zhang <xiangxia.m.yue@...il.com>
>>>
>>> The commit 20b6cc34ea74 ("bpf: Avoid hashtab deadlock with map_locked"),
>>> try to fix deadlock, but in some case, the deadlock occurs:
>>>
>>> * CPUn in task context with K1, and taking lock.
>>> * CPUn interrupted by NMI context, with K2.
>>> * They are using the same bucket, but different map_locked.
>> It is possible when n_buckets is less than HASHTAB_MAP_LOCK_COUNT (e.g.,
>> n_bucket=4). If using hash & min(HASHTAB_MAP_LOCK_MASK, n_bucket - 1) as the
>> index of map_locked, I think the deadlock will be gone.
> Yes, but for saving memory, HASHTAB_MAP_LOCK_MASK should not be too
> large(now this value is 8-1).
> if user define n_bucket ,e.g 8192, the part of bucket only are
> selected via hash & min(HASHTAB_MAP_LOCK_MASK, n_bucket - 1).
SNIP
>
>>> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
>>> index 22855d6ff6d3..429acd97c869 100644
>>> --- a/kernel/bpf/hashtab.c
>>> +++ b/kernel/bpf/hashtab.c
>>> @@ -80,9 +80,6 @@ struct bucket {
>>> raw_spinlock_t raw_lock;
>>> };
>>>
>>> -#define HASHTAB_MAP_LOCK_COUNT 8
>>> -#define HASHTAB_MAP_LOCK_MASK (HASHTAB_MAP_LOCK_COUNT - 1)
>>> -
>>> struct bpf_htab {
>>> struct bpf_map map;
>>> struct bpf_mem_alloc ma;
>>> @@ -104,7 +101,6 @@ struct bpf_htab {
>>> u32 elem_size; /* size of each element in bytes */
>>> u32 hashrnd;
>>> struct lock_class_key lockdep_key;
>>> - int __percpu *map_locked[HASHTAB_MAP_LOCK_COUNT];
>>> };
>>>
>>> /* each htab element is struct htab_elem + key + value */
>>> @@ -146,35 +142,26 @@ static void htab_init_buckets(struct bpf_htab *htab)
>>> }
>>> }
>>>
>>> -static inline int htab_lock_bucket(const struct bpf_htab *htab,
>>> - struct bucket *b, u32 hash,
>>> +static inline int htab_lock_bucket(struct bucket *b,
>>> unsigned long *pflags)
>>> {
>>> unsigned long flags;
>>>
>>> - hash = hash & HASHTAB_MAP_LOCK_MASK;
>>> -
>>> - preempt_disable();
>>> - if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
>>> - __this_cpu_dec(*(htab->map_locked[hash]));
>>> - preempt_enable();
>>> - return -EBUSY;
>>> + if (in_nmi()) {
>>> + if (!raw_spin_trylock_irqsave(&b->raw_lock, flags))
>>> + return -EBUSY;
>>> + } else {
>>> + raw_spin_lock_irqsave(&b->raw_lock, flags);
>>> }
>>>
>>> - raw_spin_lock_irqsave(&b->raw_lock, flags);
>>> *pflags = flags;
>>> -
>>> return 0;
>>> }
>> map_locked is also used to prevent the re-entrance of htab_lock_bucket() on the
>> same CPU, so only check in_nmi() is not enough.
> NMI, IRQ, and preempt may interrupt the task context.
> In htab_lock_bucket, raw_spin_lock_irqsave disable the preempt and
> irq. so only NMI may interrupt the codes, right ?
The re-entrance here means the nesting of bpf programs as show below:
bpf_prog A
update map X
htab_lock_bucket
raw_spin_lock_irqsave()
lookup_elem_raw()
// bpf prog B is attached on lookup_elem_raw()
bpf prog B
update map X again and update the element
htab_lock_bucket()
// dead-lock
raw_spinlock_irqsave()
.
>>> -static inline void htab_unlock_bucket(const struct bpf_htab *htab,
>>> - struct bucket *b, u32 hash,
>>> +static inline void htab_unlock_bucket(struct bucket *b,
>>> unsigned long flags)
>>> {
>>> - hash = hash & HASHTAB_MAP_LOCK_MASK;
>>> raw_spin_unlock_irqrestore(&b->raw_lock, flags);
>>> - __this_cpu_dec(*(htab->map_locked[hash]));
>>> - preempt_enable();
>>> }
>>>
>>> static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node);
>>> @@ -467,7 +454,7 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>> bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU);
>>> bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC);
>>> struct bpf_htab *htab;
>>> - int err, i;
>>> + int err;
>>>
>>> htab = bpf_map_area_alloc(sizeof(*htab), NUMA_NO_NODE);
>>> if (!htab)
>>> @@ -513,15 +500,6 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>> if (!htab->buckets)
>>> goto free_htab;
>>>
>>> - for (i = 0; i < HASHTAB_MAP_LOCK_COUNT; i++) {
>>> - htab->map_locked[i] = bpf_map_alloc_percpu(&htab->map,
>>> - sizeof(int),
>>> - sizeof(int),
>>> - GFP_USER);
>>> - if (!htab->map_locked[i])
>>> - goto free_map_locked;
>>> - }
>>> -
>>> if (htab->map.map_flags & BPF_F_ZERO_SEED)
>>> htab->hashrnd = 0;
>>> else
>>> @@ -549,13 +527,13 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>> if (htab->use_percpu_counter) {
>>> err = percpu_counter_init(&htab->pcount, 0, GFP_KERNEL);
>>> if (err)
>>> - goto free_map_locked;
>>> + goto free_buckets;
>>> }
>>>
>>> if (prealloc) {
>>> err = prealloc_init(htab);
>>> if (err)
>>> - goto free_map_locked;
>>> + goto free_buckets;
>>>
>>> if (!percpu && !lru) {
>>> /* lru itself can remove the least used element, so
>>> @@ -568,12 +546,12 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>> } else {
>>> err = bpf_mem_alloc_init(&htab->ma, htab->elem_size, false);
>>> if (err)
>>> - goto free_map_locked;
>>> + goto free_buckets;
>>> if (percpu) {
>>> err = bpf_mem_alloc_init(&htab->pcpu_ma,
>>> round_up(htab->map.value_size, 8), true);
>>> if (err)
>>> - goto free_map_locked;
>>> + goto free_buckets;
>>> }
>>> }
>>>
>>> @@ -581,11 +559,10 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
>>>
>>> free_prealloc:
>>> prealloc_destroy(htab);
>>> -free_map_locked:
>>> +free_buckets:
>>> if (htab->use_percpu_counter)
>>> percpu_counter_destroy(&htab->pcount);
>>> - for (i = 0; i < HASHTAB_MAP_LOCK_COUNT; i++)
>>> - free_percpu(htab->map_locked[i]);
>>> +
>>> bpf_map_area_free(htab->buckets);
>>> bpf_mem_alloc_destroy(&htab->pcpu_ma);
>>> bpf_mem_alloc_destroy(&htab->ma);
>>> @@ -782,7 +759,7 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
>>> b = __select_bucket(htab, tgt_l->hash);
>>> head = &b->head;
>>>
>>> - ret = htab_lock_bucket(htab, b, tgt_l->hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return false;
>>>
>>> @@ -793,7 +770,7 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
>>> break;
>>> }
>>>
>>> - htab_unlock_bucket(htab, b, tgt_l->hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>>
>>> return l == tgt_l;
>>> }
>>> @@ -1107,7 +1084,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
>>> */
>>> }
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1152,7 +1129,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
>>> }
>>> ret = 0;
>>> err:
>>> - htab_unlock_bucket(htab, b, hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>> return ret;
>>> }
>>>
>>> @@ -1198,7 +1175,7 @@ static int htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value,
>>> copy_map_value(&htab->map,
>>> l_new->key + round_up(map->key_size, 8), value);
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1219,7 +1196,7 @@ static int htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value,
>>> ret = 0;
>>>
>>> err:
>>> - htab_unlock_bucket(htab, b, hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>>
>>> if (ret)
>>> htab_lru_push_free(htab, l_new);
>>> @@ -1255,7 +1232,7 @@ static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key,
>>> b = __select_bucket(htab, hash);
>>> head = &b->head;
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1280,7 +1257,7 @@ static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key,
>>> }
>>> ret = 0;
>>> err:
>>> - htab_unlock_bucket(htab, b, hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>> return ret;
>>> }
>>>
>>> @@ -1321,7 +1298,7 @@ static int __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key,
>>> return -ENOMEM;
>>> }
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1345,7 +1322,7 @@ static int __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key,
>>> }
>>> ret = 0;
>>> err:
>>> - htab_unlock_bucket(htab, b, hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>> if (l_new)
>>> bpf_lru_push_free(&htab->lru, &l_new->lru_node);
>>> return ret;
>>> @@ -1384,7 +1361,7 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key)
>>> b = __select_bucket(htab, hash);
>>> head = &b->head;
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1397,7 +1374,7 @@ static int htab_map_delete_elem(struct bpf_map *map, void *key)
>>> ret = -ENOENT;
>>> }
>>>
>>> - htab_unlock_bucket(htab, b, hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>> return ret;
>>> }
>>>
>>> @@ -1420,7 +1397,7 @@ static int htab_lru_map_delete_elem(struct bpf_map *map, void *key)
>>> b = __select_bucket(htab, hash);
>>> head = &b->head;
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1431,7 +1408,7 @@ static int htab_lru_map_delete_elem(struct bpf_map *map, void *key)
>>> else
>>> ret = -ENOENT;
>>>
>>> - htab_unlock_bucket(htab, b, hash, flags);
>>> + htab_unlock_bucket(b, flags);
>>> if (l)
>>> htab_lru_push_free(htab, l);
>>> return ret;
>>> @@ -1494,7 +1471,6 @@ static void htab_map_free_timers(struct bpf_map *map)
>>> static void htab_map_free(struct bpf_map *map)
>>> {
>>> struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
>>> - int i;
>>>
>>> /* bpf_free_used_maps() or close(map_fd) will trigger this map_free callback.
>>> * bpf_free_used_maps() is called after bpf prog is no longer executing.
>>> @@ -1517,10 +1493,10 @@ static void htab_map_free(struct bpf_map *map)
>>> bpf_map_area_free(htab->buckets);
>>> bpf_mem_alloc_destroy(&htab->pcpu_ma);
>>> bpf_mem_alloc_destroy(&htab->ma);
>>> +
>>> if (htab->use_percpu_counter)
>>> percpu_counter_destroy(&htab->pcount);
>>> - for (i = 0; i < HASHTAB_MAP_LOCK_COUNT; i++)
>>> - free_percpu(htab->map_locked[i]);
>>> +
>>> lockdep_unregister_key(&htab->lockdep_key);
>>> bpf_map_area_free(htab);
>>> }
>>> @@ -1564,7 +1540,7 @@ static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
>>> b = __select_bucket(htab, hash);
>>> head = &b->head;
>>>
>>> - ret = htab_lock_bucket(htab, b, hash, &bflags);
>>> + ret = htab_lock_bucket(b, &bflags);
>>> if (ret)
>>> return ret;
>>>
>>> @@ -1602,7 +1578,7 @@ static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
>>> free_htab_elem(htab, l);
>>> }
>>>
>>> - htab_unlock_bucket(htab, b, hash, bflags);
>>> + htab_unlock_bucket(b, bflags);
>>>
>>> if (is_lru_map && l)
>>> htab_lru_push_free(htab, l);
>>> @@ -1720,7 +1696,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
>>> head = &b->head;
>>> /* do not grab the lock unless need it (bucket_cnt > 0). */
>>> if (locked) {
>>> - ret = htab_lock_bucket(htab, b, batch, &flags);
>>> + ret = htab_lock_bucket(b, &flags);
>>> if (ret) {
>>> rcu_read_unlock();
>>> bpf_enable_instrumentation();
>>> @@ -1743,7 +1719,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
>>> /* Note that since bucket_cnt > 0 here, it is implicit
>>> * that the locked was grabbed, so release it.
>>> */
>>> - htab_unlock_bucket(htab, b, batch, flags);
>>> + htab_unlock_bucket(b, flags);
>>> rcu_read_unlock();
>>> bpf_enable_instrumentation();
>>> goto after_loop;
>>> @@ -1754,7 +1730,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
>>> /* Note that since bucket_cnt > 0 here, it is implicit
>>> * that the locked was grabbed, so release it.
>>> */
>>> - htab_unlock_bucket(htab, b, batch, flags);
>>> + htab_unlock_bucket(b, flags);
>>> rcu_read_unlock();
>>> bpf_enable_instrumentation();
>>> kvfree(keys);
>>> @@ -1815,7 +1791,7 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
>>> dst_val += value_size;
>>> }
>>>
>>> - htab_unlock_bucket(htab, b, batch, flags);
>>> + htab_unlock_bucket(b, flags);
>>> locked = false;
>>>
>>> while (node_to_free) {
>
Powered by blists - more mailing lists