Skip to contentSkip to conversation

bpf: Call cond_resched() to avoid soft lockup in trie_free()

PATCH In review Matt Fleming 5 participants 14 messages Jun 16, 2025 – Jul 3, 2025 BPF

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: Call cond_resched() to avoid soft lockup in trie_free()

From: Matt Fleming <[email protected]>

Calls to kfree() in trie_free() can be expensive for KASAN-enabled kernels. This can cause soft lockup warnings when traversing large maps,

  watchdog: BUG: soft lockup - CPU#41 stuck for 76s! [kworker/u518:14:1158211]

Avoid an unbounded loop and periodically check whether we should reschedule.

---
 kernel/bpf/lpm_trie.c | 2 ++
 1 file changed, 2 insertions(+)
kernel/bpf/lpm_trie.c +2 -0
index be66d7e520e0..a35619cd99f6 100644
@@ -646,6 +646,8 @@ static void trie_free(struct bpf_map *map)
 			RCU_INIT_POINTER(*slot, NULL);
 			break;
 		}
+
+		cond_resched();
 	}
 
 out:
Signature · 1 line
2.34.1
reviewer Acked-by on v1 1/1
#1 lore raw
Quoted 5 lines · Matt Fleming

From: Matt Fleming <[email protected]>

Calls to kfree() in trie_free() can be expensive for KASAN-enabled kernels. This can cause soft lockup warnings when traversing large maps,

I think this could also happen to KASAN-disabled kernels, so the commit log is a bit misleading.

Quoted 6 lines
  watchdog: BUG: soft lockup - CPU#41 stuck for 76s! [kworker/u518:14:1158211]

Avoid an unbounded loop and periodically check whether we should reschedule.

Other than that:

Quoted 20 lines
---
 kernel/bpf/lpm_trie.c | 2 ++
 1 file changed, 2 insertions(+)
kernel/bpf/lpm_trie.c +2 -1
index be66d7e520e0..a35619cd99f6 100644
@@ -646,6 +646,8 @@ static void trie_free(struct bpf_map *map)
                        RCU_INIT_POINTER(*slot, NULL);
                        break;
                }
+
+               cond_resched();
        }
 
 out:
--

2.34.1

#2 lore raw
Quoted 10 lines · Song Liu
Quoted 5 lines · Matt Fleming

From: Matt Fleming <[email protected]>

Calls to kfree() in trie_free() can be expensive for KASAN-enabled kernels. This can cause soft lockup warnings when traversing large maps,

I think this could also happen to KASAN-disabled kernels, so the commit log is a bit misleading.

This issue can definitely affect KASAN-disabled kernels.

I mentioned KASAN to give context and explain why I saw this and nobody else seems to have reported it. I'm happy to reword this part of the commit message if needed but I still think it should mention KASAN somewhere because that's the reason I discovered it.

Thanks,
Matt

#3 lore raw
Quoted 13 lines · Matt Fleming
Quoted 10 lines · Song Liu
Quoted 5 lines · Matt Fleming

From: Matt Fleming <[email protected]>

Calls to kfree() in trie_free() can be expensive for KASAN-enabled kernels. This can cause soft lockup warnings when traversing large maps,

I think this could also happen to KASAN-disabled kernels, so the commit log is a bit misleading.

Quoted 6 lines

This issue can definitely affect KASAN-disabled kernels.

I mentioned KASAN to give context and explain why I saw this and nobody else seems to have reported it. I'm happy to reword this part of the commit message if needed but I still think it should mention KASAN somewhere because that's the reason I discovered it.

kfree is so slow that it triggers softlock up ?

Quoted 1 line

soft lockup - CPU#41 stuck for 76s

How many elements are in the trie that it takes 76 seconds??

I feel the issue is different.
It seems the trie_free() algorithm doesn't scale.
Pls share a full reproducer.

pw-bot: cr

#4 lore raw
Quoted 7 lines · Alexei Starovoitov
Quoted 3 lines · Matt Fleming

soft lockup - CPU#41 stuck for 76s

How many elements are in the trie that it takes 76 seconds??

We run our maps with potentially millions of entries, so it's the size of the map plus the fact that kfree() does more work with KASAN that triggers this for us.

Quoted 3 lines

I feel the issue is different.
It seems the trie_free() algorithm doesn't scale.
Pls share a full reproducer.

Yes, the scalability of the algorithm is also an issue. Jesper (CC'd) had some thoughts on this.

But regardless, it seems like a bad idea to have an unbounded loop inside the kernel that processes user-controlled data.

Thanks,
Matt

#5 lore raw
Quoted 19 lines · Matt Fleming
Quoted 7 lines · Alexei Starovoitov
Quoted 3 lines · Matt Fleming

soft lockup - CPU#41 stuck for 76s

How many elements are in the trie that it takes 76 seconds??

We run our maps with potentially millions of entries, so it's the size of the map plus the fact that kfree() does more work with KASAN that triggers this for us.

Quoted 3 lines

I feel the issue is different.
It seems the trie_free() algorithm doesn't scale.
Pls share a full reproducer.

Quoted 5 lines

Yes, the scalability of the algorithm is also an issue. Jesper (CC'd) had some thoughts on this.

But regardless, it seems like a bad idea to have an unbounded loop inside the kernel that processes user-controlled data.

1M kfree should still be very fast even with kasan, lockdep, etc. 76 seconds is an algorithm problem. Address the root cause.

#6 lore raw
Quoted 21 lines · Alexei Starovoitov
Quoted 19 lines · Matt Fleming
Quoted 7 lines · Alexei Starovoitov
Quoted 3 lines · Matt Fleming

soft lockup - CPU#41 stuck for 76s

How many elements are in the trie that it takes 76 seconds??

We run our maps with potentially millions of entries, so it's the size of the map plus the fact that kfree() does more work with KASAN that triggers this for us.

Quoted 3 lines

I feel the issue is different.
It seems the trie_free() algorithm doesn't scale.
Pls share a full reproducer.

Quoted 8 lines
Quoted 5 lines

Yes, the scalability of the algorithm is also an issue. Jesper (CC'd) had some thoughts on this.

But regardless, it seems like a bad idea to have an unbounded loop inside the kernel that processes user-controlled data.

1M kfree should still be very fast even with kasan, lockdep, etc. 76 seconds is an algorithm problem. Address the root cause.

What if later we have 1G? 100G? Apart from the root cause we still have "scalability concerns" unless we can somehow reimplement this as O(1)

Ignat

#7 lore raw
Quoted 30 lines · Ignat Korchagin
Quoted 27 lines · Alexei Starovoitov
Quoted 24 lines · Matt Fleming
Quoted 7 lines · Alexei Starovoitov
Quoted 3 lines · Matt Fleming

soft lockup - CPU#41 stuck for 76s

How many elements are in the trie that it takes 76 seconds??

We run our maps with potentially millions of entries, so it's the size of the map plus the fact that kfree() does more work with KASAN that triggers this for us.

Quoted 3 lines

I feel the issue is different.
It seems the trie_free() algorithm doesn't scale.
Pls share a full reproducer.

Yes, the scalability of the algorithm is also an issue. Jesper (CC'd) had some thoughts on this.

But regardless, it seems like a bad idea to have an unbounded loop inside the kernel that processes user-controlled data.

Quoted 6 lines
Quoted 2 lines

1M kfree should still be very fast even with kasan, lockdep, etc. 76 seconds is an algorithm problem. Address the root cause.

What if later we have 1G? 100G? Apart from the root cause we still have "scalability concerns" unless we can somehow reimplement this as O(1)

Do your homework pls.
Set max_entries to 100G and report back.
Then set max_entries to 1G _with_ cond_rescehd() hack and report back.

#8 lore raw
Quoted 4 lines · Alexei Starovoitov

Do your homework pls.
Set max_entries to 100G and report back.
Then set max_entries to 1G _with_ cond_rescehd() hack and report back.

Hi,

I put together a small reproducer
https://github.com/xdp-project/bpf-examples/pull/130 which gives the following results on an AMD EPYC 9684X 96-Core machine:

| Num of map entries | Linux 6.12.32 |  KASAN  | cond_resched |
|--------------------|---------------|---------|--------------|
| 1K                 | 0ms           | 4ms     | 0ms          |
| 10K                | 2ms           | 50ms    | 2ms          |
| 100K               | 32ms          | 511ms   | 32ms         |
| 1M                 | 427ms         | 5478ms  | 420ms        |
| 10M                | 5056ms        | 55714ms | 5040ms       |
| 100M               | 67253ms       | *       | 62630ms      |

* - I gave up waiting after 11.5 hours

Enabling KASAN makes the durations an order of magnitude bigger. The cond_resched() patch eliminates the soft lockups with no effect on the times.

Thanks,
Matt

#9 lore raw
Quoted 23 lines · Matt Fleming
Quoted 4 lines · Alexei Starovoitov

Do your homework pls.
Set max_entries to 100G and report back.
Then set max_entries to 1G _with_ cond_rescehd() hack and report back.

Hi,

I put together a small reproducer
https://github.com/xdp-project/bpf-examples/pull/130 which gives the following results on an AMD EPYC 9684X 96-Core machine:

| Num of map entries | Linux 6.12.32 |  KASAN  | cond_resched |
|--------------------|---------------|---------|--------------|
| 1K                 | 0ms           | 4ms     | 0ms          |
| 10K                | 2ms           | 50ms    | 2ms          |
| 100K               | 32ms          | 511ms   | 32ms         |
| 1M                 | 427ms         | 5478ms  | 420ms        |
| 10M                | 5056ms        | 55714ms | 5040ms       |
| 100M               | 67253ms       | *       | 62630ms      |
Quoted 5 lines

* - I gave up waiting after 11.5 hours

Enabling KASAN makes the durations an order of magnitude bigger. The cond_resched() patch eliminates the soft lockups with no effect on the times.

Good. Now you see my point, right?
The cond_resched() doesn't fix the issue.
1hr to free a trie of 100M elements is horrible. Try 100M kmalloc/kfree to see that slab is not the issue. trie_free() algorithm is to blame. It doesn't need to start from the root for every element. Fix the root cause.

#10 lore raw
Quoted 7 lines · Alexei Starovoitov

Good. Now you see my point, right?
The cond_resched() doesn't fix the issue.
1hr to free a trie of 100M elements is horrible. Try 100M kmalloc/kfree to see that slab is not the issue. trie_free() algorithm is to blame. It doesn't need to start from the root for every element. Fix the root cause.

It doesn't take an hour to free 100M entries, the table showed it takes about a minute (67 or 62 seconds).

I never claimed that kmalloc/kfree was at fault. I said that the loop in trie_free() has no preemption, and that's a problem with tries with millions of entries.

Of course, rewriting the algorithm used in the lpm trie code would make this less of an issue. But this would require a major rework. It's not as simple as improving trie_free() alone. FWIW I tried using a recursive algorithm in trie_free() and the results are slightly better, but it still takes multiple seconds to free 10M entries (4.3s) and under a minute for 100M (56.7s). To fix this properly it's necessary to use more than two children per node to reduce the height of the trie. And in the meantime, anyone who uses maps with millions of entries is gonna have the kthread spin in a loop without preemption.

Thanks,
Matt

#11 lore raw
Quoted 11 lines · Matt Fleming
Quoted 7 lines · Alexei Starovoitov

Good. Now you see my point, right?
The cond_resched() doesn't fix the issue.
1hr to free a trie of 100M elements is horrible. Try 100M kmalloc/kfree to see that slab is not the issue. trie_free() algorithm is to blame. It doesn't need to start from the root for every element. Fix the root cause.

Quoted 2 lines

It doesn't take an hour to free 100M entries, the table showed it takes about a minute (67 or 62 seconds).

yeah. I misread the numbers.

Quoted 4 lines

I never claimed that kmalloc/kfree was at fault. I said that the loop in trie_free() has no preemption, and that's a problem with tries with millions of entries.

Quoted 8 lines

Of course, rewriting the algorithm used in the lpm trie code would make this less of an issue. But this would require a major rework. It's not as simple as improving trie_free() alone. FWIW I tried using a recursive algorithm in trie_free() and the results are slightly better, but it still takes multiple seconds to free 10M entries (4.3s) and under a minute for 100M (56.7s). To fix this properly it's necessary to use more than two children per node to reduce the height of the trie.

What is the height of 100m tree ?

What kind of "recursive algo" you have in mind?
Could you try to keep a stack of nodes visited and once leaf is freed pop a node and continue walking.
Then total height won't be a factor.
The stack would need to be kmalloc-ed, of course,
but still should be faster than walking from the root.

Quoted 3 lines

And in the meantime, anyone who uses maps with millions of entries is gonna have the kthread spin in a loop without preemption.

Yes, because judging by this thread I don't believe you'll come back and fix it properly.
I'd rather have this acute pain bothering somebody to fix it for good instead of papering over.

#12 lore raw
Quoted 40 lines · Alexei Starovoitov
Quoted 11 lines · Matt Fleming
Quoted 7 lines · Alexei Starovoitov

Good. Now you see my point, right?
The cond_resched() doesn't fix the issue.
1hr to free a trie of 100M elements is horrible. Try 100M kmalloc/kfree to see that slab is not the issue. trie_free() algorithm is to blame. It doesn't need to start from the root for every element. Fix the root cause.

Quoted 2 lines

It doesn't take an hour to free 100M entries, the table showed it takes about a minute (67 or 62 seconds).

yeah. I misread the numbers.

Quoted 4 lines

I never claimed that kmalloc/kfree was at fault. I said that the loop in trie_free() has no preemption, and that's a problem with tries with millions of entries.

Quoted 8 lines

Of course, rewriting the algorithm used in the lpm trie code would make this less of an issue. But this would require a major rework. It's not as simple as improving trie_free() alone. FWIW I tried using a recursive algorithm in trie_free() and the results are slightly better, but it still takes multiple seconds to free 10M entries (4.3s) and under a minute for 100M (56.7s). To fix this properly it's necessary to use more than two children per node to reduce the height of the trie.

What is the height of 100m tree ?

What kind of "recursive algo" you have in mind?
Could you try to keep a stack of nodes visited and once leaf is freed pop a node and continue walking.
Then total height won't be a factor.
The stack would need to be kmalloc-ed, of course,
but still should be faster than walking from the root.

Quoted 8 lines
Quoted 3 lines

And in the meantime, anyone who uses maps with millions of entries is gonna have the kthread spin in a loop without preemption.

Yes, because judging by this thread I don't believe you'll come back and fix it properly.
I'd rather have this acute pain bothering somebody to fix it for good instead of papering over.

I think we need both anyway just for the reason we need something to backport to stable. A full re-implementation of trie might be viewed as a new feature, but older kernels need to be "fixed" as well.

#13 lore raw
In reply to Alexei Starovoitov
Quoted 2 lines · Alexei Starovoitov

What is the height of 100m tree ?

Because this trie implementation is essentially a binary tree the height is given by log2(100m) = 26.

Quoted 1 line

What kind of "recursive algo" you have in mind?

Something like this:

---
 kernel/bpf/lpm_trie.c | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)
kernel/bpf/lpm_trie.c +38 -0
index 010e91ac978e..f4b07920a321 100644
@@ -33,7 +33,13 @@ struct lpm_trie {
  struct bpf_map map;
  struct lpm_trie_node __rcu *root;
  size_t n_entries;
+ /* Maximum prefix length permitted */
  size_t max_prefixlen;
+ /* Largest prefix length of any node ever inserted. Used for an
+ * optimisation in trie_free() and is not updated on node
+ * deletion.
+ */
+ size_t largest_prefixlen;
  size_t data_size;
  spinlock_t lock;
 };
@@ -450,6 +456,10 @@ static long trie_update_elem(struct bpf_map *map,
 out:
  if (ret)
  kfree(new_node);
+ else
+ trie->largest_prefixlen = max(trie->largest_prefixlen,
+ key->prefixlen);
+
  spin_unlock_irqrestore(&trie->lock, irq_flags);
  kfree_rcu(free_node, rcu);
 
@@ -599,12 +609,40 @@ static struct bpf_map *trie_alloc(union bpf_attr *attr)
  return &trie->map;
 }
 
+static void __trie_free(struct lpm_trie_node __rcu **slot)
+{
+ struct lpm_trie_node *node;
+
+ node = rcu_dereference_protected(*slot, 1);
+ if (!node)
+ return;
+
+ if (rcu_access_pointer(node->child[0]))
+ __trie_free(&node->child[0]);
+
+ if (rcu_access_pointer(node->child[1]))
+ __trie_free(&node->child[1]);
+
+ kfree(node);
+ RCU_INIT_POINTER(*slot, NULL);
+}
+
 static void trie_free(struct bpf_map *map)
 {
  struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
  struct lpm_trie_node __rcu **slot;
  struct lpm_trie_node *node;
 
+ /* When we know the largest prefixlen used by any node is <= 32
+ * we're guaranteed that the height of the trie is at most 32.
+ * And in that case, we can use a faster recursive freeing
+ * algorithm without worrying about blowing the stack.
+ */
+ if (trie->largest_prefixlen <= 32) {
+ __trie_free(&trie->root);
+ goto out;
+ }
+
  /* Always start at the root and walk down to a node that has no
  * children. Then free that node, nullify its reference in the parent
  * and start over.
Quoted 5 lines

Could you try to keep a stack of nodes visited and once leaf is freed pop a node and continue walking.
Then total height won't be a factor.
The stack would need to be kmalloc-ed, of course,
but still should be faster than walking from the root.

Sure, I can give this a shot. Plus we won't need to guard against blowing up the stack.