[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAG48ez2WdxXVCzVsAPeQWgso3ZBQS_Xm+9D1FLBx6UHFV1bGHQ@mail.gmail.com>
Date: Tue, 20 May 2025 00:51:07 +0200
From: Jann Horn <jannh@...gle.com>
To: Burak Emir <bqe@...gle.com>
Cc: 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>,
Boqun Feng <boqun.feng@...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>,
Alice Ryhl <aliceryhl@...gle.com>, 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 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
used to work in MM code... That would let you drop that ID pool bitmap
entirely. But I guess actually wiring up an augmented rbtree into Rust
would be very annoying too.
Powered by blists - more mailing lists