linux-kernel - Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions

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: <xb2gihmastm3wjn2o2sufvtglvjkelhiiwhnlzoiz4qncywyga@txf4vvnyxhvu>
Date: Wed, 16 Oct 2024 23:26:30 -0400
From: Kent Overstreet <kent.overstreet@...ux.dev>
To: Kuan-Wei Chiu <visitorckw@...il.com>
Cc: Peter Zijlstra <peterz@...radead.org>, colyli@...e.de, 
	msakai@...hat.com, corbet@....net, mingo@...hat.com, acme@...nel.org, 
	namhyung@...nel.org, akpm@...ux-foundation.org, mark.rutland@....com, 
	alexander.shishkin@...ux.intel.com, jolsa@...nel.org, irogers@...gle.com, adrian.hunter@...el.com, 
	kan.liang@...ux.intel.com, jserv@...s.ncku.edu.tw, linux-kernel@...r.kernel.org, 
	linux-bcache@...r.kernel.org, dm-devel@...ts.linux.dev, linux-bcachefs@...r.kernel.org, 
	linux-perf-users@...r.kernel.org, linux-doc@...r.kernel.org
Subject: Re: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min
 heap API functions

On Mon, Oct 14, 2024 at 05:41:23PM +0800, Kuan-Wei Chiu wrote:
> On Mon, Oct 14, 2024 at 10:13:58AM +0200, Peter Zijlstra wrote:
> > On Mon, Oct 14, 2024 at 02:47:01AM +0800, Kuan-Wei Chiu wrote:
> > > All current min heap API functions are marked with '__always_inline'.
> > > However, as the number of users increases, inlining these functions
> > > everywhere leads to a significant increase in kernel size.
> > > 
> > > In performance-critical paths, such as when perf events are enabled and
> > > min heap functions are called on every context switch, it is important
> > > to retain the inline versions for optimal performance. To balance this,
> > > the original inline functions are kept, and additional non-inline
> > > versions of the functions have been added in lib/min_heap.c.
> > 
> > The reason it is all __always_inline is because then the whole
> > min_heap_callbacks thing can be constant propagated and the func->less()
> > etc calls become direct calls.
> > 
> > Doing out of line for this stuff, makes them indirect calls, and
> > indirect calls are super retarded expensive ever since spectre. But also
> > things like kCFI add significant cost to indirect calls.
> > 
> > Something that would be a trivial subtract instruction becomes this
> > giant mess of an indirect function call.
> >
> Yes, I also learned from reading the lib/sort.c git log that indirect
> function calls can become especially expensive when
> CONFIG_MITIGATION_RETPOLINE is enabled.
> 
> I'm not an expert in bcache, bcachefs, or dm-vdo, but when Andrew
> previously suggested moving these functions to lib/min_heap, Kent
> expressed his support. This led me to believe that in bcache and
> bcachefs (which are the primary users of min_heap), these indirect
> function calls are considered acceptable. However, that's just my
> assumption — I'll wait for Kent to chime in on this.

yeah, I think we would prefer smaller codesize, by default.

it'd be well worth checking the code size difference on inlined vs. not,
and then the really think to do would be to provide optional _inlined()
helpers that we can switch to if/when a particular codepath shows up in
a profile