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: <20190617155125.62da2946@collabora.com>
Date:   Mon, 17 Jun 2019 15:51:25 +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 Fri, 24 May 2019 17:09:37 +0200
Boris Brezillon <boris.brezillon@...labora.com> wrote:

> 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.

Gentle ping. How should I proceed with that patch? Do you plan to send
(or have already sent) the changes you were mentioning above?

Regards,

Boris