Re:Re: [PATCH bpf-next v4 2/3] bpf, arena: fix range_tree_set inconsistency on kmalloc_nolock failure

[chenyuan]

The two lookups answer different questions, so the second one is
not redundant:

- The pre-clear lookup only consumes the boolean result.  Nodes are
  disjoint, and a node covering both start - 1 and last + 1 would
  fully cover [start, last], which is rejected by the early return
  above.  Hence range_tree_clear() can only remove or truncate nodes
  overlapping [start, last]: a node covering start - 1 either ends
  there (untouched) or straddles start and is truncated to
  [rn_start, start - 1].  Adjacency on either side is therefore
  invariant across the clear, and "no adjacent node on either side"
  before the clear is exactly the condition for the else-branch --
  the only case needing a fresh node.  It must be evaluated before
  any tree modification to keep the -ENOMEM path side-effect free.

- The post-clear lookup fetches the node handles used by the
  merge/extend branches.  The pre-clear handles cannot be reused:
  an adjacent node may straddle the range and get truncated (e.g.
  [start - 1, start + 3] becomes [start - 1, start - 1]), so both
  its bounds and its position in the tree change.  Re-looking it up
  keeps range_tree_set() independent of how range_tree_clear()
  implements truncation, and leaves the -EFAULT checks below as a
  sanity check of the clear itself.
 
The comment indeed fails to spell this out (and "adjacent free
range" is backwards); I'll reword it in v5.


At 2026-08-27 10:56:04, "Alexei Starovoitov" <alexei.starovoitov@xxxxxxxxx> wrote:
>On Mon, Aug 24, 2026 at 6:40 AM <chenyuan_fl@xxxxxxx> wrote:
>>
>> From: Yuan Chen <chenyuan@xxxxxxxxxx>
>>
>> range_tree_set() pre-allocates the node needed for a brand-new range
>> before calling range_tree_clear(), so an allocation failure returns
>> -ENOMEM without having modified the tree (previously the overlapping
>> nodes were already removed by range_tree_clear() before the allocation
>> was attempted, permanently losing the cleared sub-ranges).
>>
>> Signed-off-by: Yuan Chen <chenyuan@xxxxxxxxxx>
>> ---
>>  kernel/bpf/range_tree.c | 45 +++++++++++++++++++++++++++++++----------
>>  1 file changed, 34 insertions(+), 11 deletions(-)
>>
>> diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
>> index 15b588377a76..54055b1fe541 100644
>> --- a/kernel/bpf/range_tree.c
>> +++ b/kernel/bpf/range_tree.c
>> @@ -199,6 +199,7 @@ int is_range_tree_set(struct range_tree *rt, u32 start, u32 len)
>>  int range_tree_set(struct range_tree *rt, u32 start, u32 len)
>>  {
>>         u32 last = start + len - 1;
>> +       struct range_node *new_rn = NULL;
>>         struct range_node *right;
>>         struct range_node *left;
>>         int err;
>> @@ -208,20 +209,40 @@ int range_tree_set(struct range_tree *rt, u32 start, u32 len)
>>         if (left && left->rn_start <= start && left->rn_last >= last)
>>                 return 0;
>>
>> +       /*
>> +        * A new node is needed only when the range has no adjacent free
>> +        * range on either side.  This is known before clearing: any range
>> +        * covering start - 1 or last + 1 survives the clear as an adjacent
>> +        * piece.
>
>If this is true, why do a 2nd call to left = range_it_iter_first() ?
>
>
>>  Allocate only in that case, before modifying the tree, so
>> +        * a failure leaves the range tree unmodified
>> +        */
>> +       left = range_it_iter_first(rt, start - 1, start - 1);
>> +       right = range_it_iter_first(rt, last + 1, last + 1);
>> +       if (!left && !right) {
>> +               new_rn = kmalloc_nolock(sizeof(struct range_node),
>> +                                       __GFP_ACCOUNT, NUMA_NO_NODE);
>> +               if (!new_rn)
>> +                       return -ENOMEM;
>> +       }
>> +
>>         /* Clear out everything in the range we want to set. */
>>         err = range_tree_clear(rt, start, len);
>>         if (err)
>> -               return err;
>> +               goto out_free_new;
>>
>>         /* Do we have a left-adjacent range ? */
>>         left = range_it_iter_first(rt, start - 1, start - 1);
>
>pw-bot: cr