linux-kernel - Re: [PATCH 5/5] lib/list_sort: Optimize number of calls to comparison function

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]

Date:   Sat, 22 Jun 2019 01:12:01 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     George Spelvin <lkml@....org>, linux-kernel@...r.kernel.org
Cc:     akpm@...ux-foundation.org, andriy.shevchenko@...ux.intel.com,
        daniel.wagner@...mens.com, dchinner@...hat.com,
        don.mullis@...il.com, geert@...ux-m68k.org, st5pub@...dex.ru
Subject: Re: [PATCH 5/5] lib/list_sort: Optimize number of calls to comparison
 function

On 14/03/2019 02.58, George Spelvin wrote:
> On Thu, 14 Mar 2019 at 00:28:16 +0100, Rasmus Villemoes wrote:

>> Similarly one could do a SORT_SIMPLE_CMP() for when sorting an array of
>> structs according to a single numeric member. That sort is not stable,
>> so the comparison functions would have to do a full -1,0,1 return, of
>> course, but we'd still avoid indirect calls.
> 
> Actually, while some sorts (notably fat-pivot quicksort) require
> a 3-way return to avoid O(n^2) performance, heapsort is just fine
> with a boolean return value. 

Hi George

So I tried starting to implement this, and the timing results look
promising. However, currently I'm doing

  (*(u32*)ka > *(u32*)kb) - (*(u32*)ka < *(u32*)kb);

in my do_cmp. Both existing invocations of the comparison function in
sort.c compare its return value >= 0, which is always true if I just
return the boolean (*(u32*)ka > *(u32*)kb). So it seems the algorithm
would have to be changed to allow the cmp function to return a bool.
Perhaps it's as simple as changing the two >= to >, but can I get you to
check that that would be ok? (Quick testing seems to suggest so, but
it's possible there are some corner cases where it would break.)

Thanks,
Rasmus