Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

[Boqun Feng <boqun.feng@gmail.com>]

On Tue, May 20, 2025 at 05:55:47PM +0200, Jann Horn wrote:
> On Tue, May 20, 2025 at 3:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > On Tue, May 20, 2025 at 06:05:52AM -0700, Alice Ryhl wrote:
> > > On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> > > > > On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > >
> > > > > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > > > > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > > > >
> > > > > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > > > > > > This is a port of the Binder data structure introduced in commit
> > > > > > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > > > > > > Rust.
> > > > > > > > >
> > > > > > > > > Stupid high-level side comment:
> > > > > > > > >
> > > > > > > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > > > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > > > > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > > > > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > > > > > > >
> > > > > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > > > > > >
> > > > > > > We need the smallest ID without a value, not the smallest ID in use.
> > > > > > >
> > > > > >
> > > > > > Ok, but it shouldn't be hard to write a Rust function that search that,
> > > > > > right? My point was mostly the Rust rbtree binding can do O(log n)
> > > > > > search. I have no idea about "even so, should we try something like Jann
> > > > > > suggested". And I think your other reply basically says no.
> > > > >
> > > > > We would need to store additional data in the r/b tree to know whether
> > > > > to go left or right, so it would be somewhat tricky. We don't have an
> > > >
> > > > Hmm... I'm confused, I thought you can implement a search like that by
> > > > doing what RBTree::raw_entry() does except that when Ordering::Equal you
> > > > always go left or right (depending on whether you want to get an unused
> > > > ID less or greater than a key value), i.e. you always search until you
> > > > get an Vacant entry. Why do you need store additional data for that?
> > > > Maybe I'm missing something here?
> > >
> > > Let's say you're at the root node of an r/b tree, and you see that the
> > > root node has id 17, the left node has id 8, and the right node has id
> > > 25. Do you go left or right?
> > >
> >
> > I went to check what commit 15d9da3f818c actually did and I understand
> > what you mean now ;-) In your case, the rbtree cannot have nodes with
> > the same key. If Jann can provide the O(log n) search that could help in
> > this case, I'm happy to learn about it ;-)
> 
> Linux has the concept of an "augmented rbtree", where you can stuff
> extra information into the rbtree to keep track of things like "how
> big is the biggest gap between objects in this subtree". This is how
> the MM subsystem used to find free space in the virtual address space
> before the maple tree refactor, a complicated example is here:
> 
> finding a free region (by looking at vm_area_struct::rb_subtree_gap to
> decide whether to go left or right; this is made complicated here
> because they have more search constraints):
> https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L1841
> 
> But that requires an "augmented rbtree" where the rbtree code calls
> back into callbacks for updating the subtree gap; the MM code has its
> gap update here:
> https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L261
> 

I see. I was missing this part.

> And associates that with VMA trees through this macro magic that would
> probably be a terrible fit for Rust code:
> https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L400
> 

Well, not sure that's true implementation-wise, I mean it's just
function callbacks while you insert or erase nodes from rbtree, which
could probably be described by a trait like:

    pub trait RBTreeAugmented<K, V> {
        fn compute(node: &Node<K, V, Self>) -> Self;
    }

    impl<K, V> RBTreeAugmented<K, V> for () {
        fn compute(_node: &Node<K, V, Self>) -> Self {
	    ()
	}
    }
and we change the Node type into:

    pub struct Node<K, V, A: RBTreeAugmented<K, V> = ()> 
    {
        links: bindings::rb_node,
        key: K,
        value: V,
	augmented: A
    }

and _propagate() can be something like:

   unsafe fn augmented_propagate<K, V, A: RBTreeAugmented<K, V>>(
       mut node: *mut rb_node, stop: *mut rb_node
   ) {
       	while !ptr::eq(node, stop) {
            let rbnode = unsafe { container_of!(node, Node<K, V, A>, links) }.cast_mut();
	    let rbnode: &mut Node<K,V,A> = unsafe { &mut *rbnode };

	    let new_augmented = A::compute(rbnode);

	    if rbnode.aurmented == new_augmented {
	        break;
	    }
		if (node->rbaugmented == augmented)			\
			break;						\
	    rbnode.augmented = augmented;				\

	    node = rb_parent(node);
	}
   }

probably works? However I guess we don't need to do that right now given
Alice's point on xarray or maple tree.

Regards,
Boqun

> As Alice said, this is probably not a great fit for Rust code. As she
> said, an xarray or maple tree would have this kind of gap search
> built-in, which would be nicer here. But if you're trying to do
> insertions while holding your own outer spinlocks, I think they would
> be hard (or impossible?) to use.
> 
> If you managed to avoid broad use of spinlocks, that might make it
> much easier to use xarrays or maple trees (and that would also allow
> you to make the bitmap API much simpler).