On 7/28/22 3:04 AM, Yonghong Song 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));
>
> 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?
>
Summarizing our VC convo: the intent here is to have the lock live separately
from the tree, meaning it'd be separately initialized and passed into the tree
instead of current state where it's a bpf_rbtree field.
If the tree still keeps a pointer to the lock - ideally passed in when rbtree
map is instantiated - it'll be possible to move to a cleaner API as you
describe. The very explicit way it's done in this series is not the end state
I'd like either.
>>
>> 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.
>>
> [...]
