linux-kernel - Re: [PATCH bpf-next v3 4/5] bpf: lru: Fix unintended eviction when updating lru hash maps

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <3d4287e5-0564-4933-83ee-c2dcbfe993f4@linux.dev>
Date: Thu, 15 Jan 2026 11:25:46 +0800
From: Leon Hwang <leon.hwang@...ux.dev>
To: Martin KaFai Lau <martin.lau@...ux.dev>
Cc: Alexei Starovoitov <ast@...nel.org>,
 Daniel Borkmann <daniel@...earbox.net>, Andrii Nakryiko <andrii@...nel.org>,
 Eduard Zingerman <eddyz87@...il.com>, Song Liu <song@...nel.org>,
 Yonghong Song <yonghong.song@...ux.dev>,
 John Fastabend <john.fastabend@...il.com>, KP Singh <kpsingh@...nel.org>,
 Stanislav Fomichev <sdf@...ichev.me>, Hao Luo <haoluo@...gle.com>,
 Jiri Olsa <jolsa@...nel.org>, Shuah Khan <shuah@...nel.org>,
 Saket Kumar Bhaskar <skb99@...ux.ibm.com>,
 "David S . Miller" <davem@...emloft.net>, linux-kernel@...r.kernel.org,
 linux-kselftest@...r.kernel.org, kernel-patches-bot@...com,
 bpf@...r.kernel.org
Subject: Re: [PATCH bpf-next v3 4/5] bpf: lru: Fix unintended eviction when
 updating lru hash maps

On 15/1/26 03:39, Martin KaFai Lau wrote:
> 
> 
> On 1/7/26 7:14 AM, Leon Hwang wrote:
>> When updating an existing element in lru_[percpu_,]hash maps, the current
>> implementation always calls prealloc_lru_pop() to get a new node before
>> checking if the key already exists. If the map is full, this triggers
>> LRU eviction and removes an existing element, even though the update
>> operation only needs to modify the value of an existing key in-place.
>>
>> This is problematic because:
>> 1. Users may unexpectedly lose entries when doing simple value updates
>> 2. The eviction overhead is unnecessary for existing key updates
> 
> This is not the common LRU map use case. The bpf prog usually does a
> lookup first, finds the entry, and then directly updates the value in-
> place in the bpf prog itself. If the lookup fails, it will insert a
> _new_ element.
> 
> When the map is full, eviction should actually be triggered regardless.
> For an LRU map that is too small to fit the working set, it is asking
> for trouble.
> 
> From the syscall update, if the use case is always updating an existing
> element, the regular hashmap should be used instead.
> 

Thanks for the explanation.

While the common use case is indeed to update values in place after a
lookup, small-capacity LRU maps are not forbidden today, so the
unexpected eviction behavior can still be observed in practice.

I have been asked about data loss with a 110-entry LRU map before, and
in that case my recommendation was also to use a regular hash map instead.

>> Fix this by first checking if the key exists before allocating a new
>> node. If the key is found, update the value using the extra lru node
>> without triggering any eviction.
> 
> This will instead add overhead for the common use case described above.
> The patch is mostly for getting a selftest case to work in a small LRU
> map. I don't think it is worth the added complexity either.
> 

Given this, instead of pursuing this change, I will update the selftests
in 'tools/testing/selftests/bpf/prog_tests/percpu_alloc.c' to make them
more robust and avoid CI failures.

> Patch 2 and 3 look ok, but they also only make marginal improvements on
> the existing code.
> 
> pw-bot: cr
> 
>> +static int htab_lru_map_update_elem_in_place(struct bpf_htab *htab,
>> void *key, void *value,
>> +                         u64 map_flags, struct bucket *b,
>> +                         struct hlist_nulls_head *head, u32 hash,
>> +                         bool percpu, bool onallcpus)
>> +{

[...]

>> +err:
>> +    htab_unlock_bucket(b, flags);
>> +
>> +err_lock_bucket:
>> +    if (ret) {
>> +        bpf_lru_push_free(&htab->lru, node);
>> +    } else {
>> +        if (l_old && !percpu)
>> +            bpf_obj_free_fields(map->record, htab_elem_value(l_old,
>> key_size));
> 
> Does htab_lru_map_update_elem() have an existing bug that is missing the
> bpf_obj_free_fields() on l_old?
> 

No.

htab_lru_push_free() would free the special fields.

Thanks,
Leon

[...]