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.
[...]
