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.
