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.
