linux-kernel - Re: [RFC PATCH 3/4] rust/drm: Add DRM Jobqueue

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <aYygDtrcQjwamJIJ@google.com>
Date: Wed, 11 Feb 2026 15:28:14 +0000
From: Alice Ryhl <aliceryhl@...gle.com>
To: phasta@...nel.org
Cc: Boris Brezillon <boris.brezillon@...labora.com>, David Airlie <airlied@...il.com>, 
	Simona Vetter <simona@...ll.ch>, Danilo Krummrich <dakr@...nel.org>, Gary Guo <gary@...yguo.net>, 
	Benno Lossin <lossin@...nel.org>, 
	"Christian König" <christian.koenig@....com>, Daniel Almeida <daniel.almeida@...labora.com>, 
	Joel Fernandes <joelagnelf@...dia.com>, linux-kernel@...r.kernel.org, 
	dri-devel@...ts.freedesktop.org, rust-for-linux@...r.kernel.org
Subject: Re: [RFC PATCH 3/4] rust/drm: Add DRM Jobqueue

On Wed, Feb 11, 2026 at 02:53:49PM +0100, Philipp Stanner wrote:
> On Wed, 2026-02-11 at 12:52 +0000, Alice Ryhl wrote:
> > 
> > Yes, many people assume "list widely used in kernel" implies "list is a
> > good idea". Unfortunately it is not the case.
> > 
> > > > This applies to the red/black tree too, by the way.
> > > 
> > > Can't fully follow, you mean that RB trees are supposedly overused,
> > > too?
> > 
> > When I first suggested adding red/black tree abstractions in Rust
> > several years ago I was told by Greg that I couldn't do it because the
> > red/black tree was deprecated and no new users should be added.
> 
> Do you have a link or sth?

I could not easily find it again, sorry. It's been several years now
since that discussion.

> First time in my life that I hear that RB trees shouldn't be used. If
> something is deprecated for good one would hope that's obvious.

I'm not sure what the current status is ... it may have been somewhat
walked back and is now a "some people do not like rb trees" rather than
a deprecation.

> What's the justification? Should everyone use the B-Tree?
> RB trees are super widely used in CS. 

The justification is that every time you follow a pointer, it costs a
cache miss which is really expensive. Using an xarray or hashtable or
vector is much cheaper under most circumstances.

RB trees are used widely in CS because they are one of the simplest data
structures that provide O(log n) lookup. Such analysis usually does not
care about constant factors.

Alice