On Wed, Dec 07, 2022 at 04:39:47AM IST, Dave Marchevsky wrote: > This series adds a rbtree datastructure following the "next-gen > datastructure" precedent set by recently-added linked-list [0]. This is > a reimplementation of previous rbtree RFC [1] to use kfunc + kptr > instead of adding a new map type. This series adds a smaller set of API > functions than that RFC - just the minimum needed to support current > cgfifo example scheduler in ongoing sched_ext effort [2], namely: > > bpf_rbtree_add > bpf_rbtree_remove > bpf_rbtree_first > > [...] > > Future work: > Enabling writes to release_on_unlock refs should be done before the > functionality of BPF rbtree can truly be considered complete. > Implementing this proved more complex than expected so it's been > pushed off to a future patch. > TBH, I think we need to revisit whether there's a strong need for this. I would even argue that we should simply make the release semantics of rbtree_add, list_push helpers stronger and remove release_on_unlock logic entirely, releasing the node immediately. I don't see why it is so critical to have read, and more importantly, write access to nodes after losing their ownership. And that too is only available until the lock is unlocked. I think this relaxed release logic and write support is the wrong direction to take, as it has a direct bearing on what can be done with a node inside the critical section. There's already the problem with not being able to do bpf_obj_drop easily inside the critical section with this. That might be useful for draining operations while holding the lock. Semantically in other languages, once you move an object, accessing it is usually a bug, and in most of the cases it is sufficient to prepare it before insertion. We are certainly in the same territory here with these APIs. Can you elaborate on actual use cases where immediate release or not having write support makes it hard or impossible to support a certain use case, so that it is easier to understand the requirements and design things accordingly?
