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

[Dave Marchevsky <davemarchevsky@fb.com>]

On 8/1/22 5:27 PM, Alexei Starovoitov wrote:   
> 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));
>>
>>    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?
> 
> Overall it seems to be on the right track.
> The two main issue to resolve are locks and iterators.
> The rest needs work too, but it's getting close :)
> Will reply in individual patches.

I generally agree with the comments on individual patches. We talked about the
whole series over VC quite a bit, I will summarize the larger points below.

* It's worth experimenting with statically verifying correct locking instead
of current dynamic approach where helpers that really shouldn't fail - e.g.
adding / removing from tree - can fail if lock isn't held. If it's possible
to get it working we can get rid of CONDITIONAL_RELEASE concept since failing
add operation is the only thing that needs it.

* You're not sold on the need for OBJ_NON_OWNING_REF flag in verifier, and
feel that it makes the API more confusing to work with. Worth experimenting
with a 'valid use-after-free' (really use-after-release here) concept that
doesn't require new type flag, or just accepting "racy, but safe".

* Open-coded iteration will take a long time to do correctly and
should be dropped for now.