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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAH5fLgjqj7binVaLDh7Pc7SVKDM-XrYDEDj7GYBX_MnjHgufFg@mail.gmail.com>
Date: Tue, 20 May 2025 06:05:52 -0700
From: Alice Ryhl <aliceryhl@...gle.com>
To: Boqun Feng <boqun.feng@...il.com>
Cc: Jann Horn <jannh@...gle.com>, Burak Emir <bqe@...gle.com>, Yury Norov <yury.norov@...il.com>, 
	Kees Cook <kees@...nel.org>, Rasmus Villemoes <linux@...musvillemoes.dk>, 
	Viresh Kumar <viresh.kumar@...aro.org>, Miguel Ojeda <ojeda@...nel.org>, 
	Alex Gaynor <alex.gaynor@...il.com>, Gary Guo <gary@...yguo.net>, 
	Björn Roy Baron <bjorn3_gh@...tonmail.com>, 
	Benno Lossin <benno.lossin@...ton.me>, Andreas Hindborg <a.hindborg@...nel.org>, 
	Trevor Gross <tmgross@...ch.edu>, "Gustavo A . R . Silva" <gustavoars@...nel.org>, 
	rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org, 
	linux-hardening@...r.kernel.org
Subject: Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@...il.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@...il.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@...il.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@...gle.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?

Alice