linux-kernel - Re: [PATCH] lib/sort: Add the sort

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: <20190524170937.7ecf7fe1@collabora.com>
Date:   Fri, 24 May 2019 17:09:37 +0200
From:   Boris Brezillon <boris.brezillon@...labora.com>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:     linux-kernel@...r.kernel.org, George Spelvin <lkml@....org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Andrey Abramov <st5pub@...dex.ru>, kernel@...labora.com
Subject: Re: [PATCH] lib/sort: Add the sort_r() variant

Hello Rasmus,

On Thu, 23 May 2019 22:04:35 +0200
Rasmus Villemoes <linux@...musvillemoes.dk> wrote:

> On 22/05/2019 13.25, Boris Brezillon wrote:
> > Some users might need extra context to compare 2 elements. This patch
> > adds the sort_r() which is similar to the qsort_r() variant of qsort().
> > 
> > Signed-off-by: Boris Brezillon <boris.brezillon@...labora.com>
> > ---
> > Hello,
> > 
> > A few more details about this patch.
> > 
> > Even though I post it as a standalone patch, I do intend to use it in
> > a real driver (v4l2 driver), just didn't want to have it burried in a
> > huge patch series.
> > 
> > Note that sort() and sort_r() are now implemented as wrappers around
> > do_sort() so that most of the code can be shared. I initially went for
> > a solution that implemented sort() as a wrapper around sort_r() (which
> > basically contained the do_sort() logic without the cmp_func arg)
> > but realized this was adding one extra indirect call (the compare func
> > wrapper), which I know are being chased.  
> 
> Hm, I don't like the "pass one or the other, but not both". Yes, the
> direct way to implement sort() in terms of sort_r would be
> 
> cmp_wrapper(void *a, void *b, void *priv)
> { return ((cmp_func_t)priv)(a, b); }
> 
> void sort(...) { sort_r(...., cmp_wrapper, cmp_func); }
> 
> but it's easy enough to get rid of that extra indirect call similar to
> how the swap functions are done: pass a sentinel value, and use a single
> (highly predictable) branch to check whether we have an old-style cmp
> function.
> 
> [Are there actually any architectures where passing a third argument to
> a function just expecting two would not Just Work? I.e., could one
> simply cast a new-style comparison function to an old-style and pass
> NULL as priv? Well, we'd better not go down that road.]
> 
> So I propose this somewhat simpler (at least in terms of diffstat)
> patch, which also fits nicely with some optimizations I plan on doing to
> eliminate "trivial" comparison functions (those that just do a single
> integer comparison of some field inside the structs).

Works for me. If you plan to send changes on top (or before) would you
mind making this patch part of the series so that we don't have to deal
with merge conflicts.

Thanks,

Boris