Re: [RFC PATCH bpf-next 00/11] bpf: Introduce rbtree map

[Yonghong Song <yhs@fb.com>]

On 7/22/22 11:34 AM, Dave Marchevsky wrote:
> Introduce bpf_rbtree map data structure. As the name implies, rbtree map
> allows bpf programs to use red-black trees similarly to kernel code.
> Programs interact with rbtree maps in a much more open-coded way than
> more classic map implementations. Some example code to demonstrate:
> 
>    node = bpf_rbtree_alloc_node(&rbtree, sizeof(struct node_data));
>    if (!node)
>      return 0;
> 
>    node->one = calls;
>    node->two = 6;
>    bpf_rbtree_lock(bpf_rbtree_get_lock(&rbtree));

Can we just do
      bpf_rbtree_lock(&rbtree)
      bpf_rbtree_unlock(&rbtree)
? Looks like the only places bpf_rbtree_get_lock() used are
as arguments of bpf_rbtree_lock/unlock or bpf_spin_lock/unlock?

> 
>    ret = (struct node_data *)bpf_rbtree_add(&rbtree, node, less);
>    if (!ret) {
>      bpf_rbtree_free_node(&rbtree, node);
>      goto unlock_ret;
>    }
> 
> unlock_ret:
>    bpf_rbtree_unlock(bpf_rbtree_get_lock(&rbtree));
>    return 0;
> 
> 
> This series is in a heavy RFC state, with some added verifier semantics
> needing improvement before they can be considered safe. I am sending
> early to gather feedback on approach:
> 
>    * Does the API seem reasonable and might it be useful for others?
> 
>    * Do new verifier semantics added in this series make logical sense?
>      Are there any glaring safety holes aside from those called out in
>      individual patches?
> 
> Please see individual patches for more in-depth explanation. A quick
> summary of patches follows:
> 
> 
> Patches 1-3 extend verifier and BTF searching logic in minor ways to
> prepare for rbtree implementation patch.
>    bpf: Pull repeated reg access bounds check into helper fn
>    bpf: Add verifier support for custom callback return range
>    bpf: Add rb_node_off to bpf_map
> 
> 
> Patch 4 adds basic rbtree map implementation.
>    bpf: Add rbtree map
> 
> Note that 'complete' implementation requires concepts and changes
> introduced in further patches in the series. The series is currently
> arranged in this way to ease RFC review.
> 
> 
> Patches 5-7 add a spinlock to the rbtree map, with some differing
> semantics from existing verifier spinlock handling.
>    bpf: Add bpf_spin_lock member to rbtree
>    bpf: Add bpf_rbtree_{lock,unlock} helpers
>    bpf: Enforce spinlock hold for bpf_rbtree_{add,remove,find}
> 
> Notably, rbtree's bpf_spin_lock must be held while manipulating the tree
> via helpers, while existing spinlock verifier logic prevents any helper
> calls while lock is held. In current state this is worked around by not
> having the verifier treat rbtree's lock specially in any way. This
> needs to be improved before leaving RFC state as it's unsafe.
> 
[...]