linux-kernel - Re: [PATCH 0/5] simple sort swap function usage improvements

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] [day] [month] [year] [list]

Date:   Mon, 1 Apr 2019 23:08:12 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     George Spelvin <lkml@....org>
Cc:     Andrey Abramov <st5pub@...dex.ru>,
        Andy Shevchenko <andy.shevchenko@...il.com>,
        LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 0/5] simple sort swap function usage improvements

[trimming cc list]

On 30/03/2019 18.16, George Spelvin wrote:
> Great work; that is indeed a logical follow-on.
> 
> Reviewed by: George Spelvin <lkml@....org>
> 
> I you feel even more ambitious, you could try impementing Rasmus
> Villemoes' idea of having generic *compare* functions.  (It's on
> my to-do list, but I haven't made meaningful progress yet, and I'm
> happy to pawn it off.)
> 
> A significant fraction of the time, the sort key is a 4- or 8-byte
> integer field in a structure at a small offset from the base or
> list_head.
> 
> A function pointer < 4096 could be interpreted as encoding:
> - Key size (1 bit)
> - Key signedness (1 bit)
> - Sort direction (1 bit)
> - Offset (9 bits; +/-256 words = +/-1024 bytes, or 0..511 words from start)
> 
> With the correct level of preprocessor hackery,
> SIMPLE_CMP_ASCENDING(struct type, key_field)
> SIMPLE_LIST_CMP_ASCENDING(struct type, list_field, key_field)
> SIMPLE_CMP_DESCENDING(struct type, key_field)
> SIMPLE_LIST_CMP_DESCENDING(struct type, list_field, key_field)

So, first of all, I don't think there's any reason to do the descending
thing, at least until there's a (or better, a handful) of potential users.

Second, I don't think the user should be concerned with the encoding,
and I'd avoid the shouting, even if it happens to be implemented as
macros because of the need to do type inspection. So I'd do

  sort_by_key(base, count, key)

where base must be of type "struct foo *" and key must be the name of a
member of struct foo. [I think most would be just fine with the default
swap - if not, that could be added, or we could add another macro also
taking a swap argument.] So this would expand to

  sort(base, count, sizeof(*base), the-encoding-stuff, NULL)

Similarly, for list_sort, I'd do

  list_sort_by_key(head, type, list-member, key-member)

which would expand to

  list_sort((long)offset_diff, head, encode typeof(type->key));

The latter is the easier one to do because we have the context argument
that goes unused in the case of a trivial comparison function. The
former would be just as easy if we decide that we only care about the
majority which are happy with the default swap function, because in that
case the offsetof(type, key) could go in the swap argument, and the cmp
argument would just be the same as for list_sort. Having the two share
the logic for "key is one of the types we support, or build bug" would
be good. Perhaps the two tiny list_sort.h and sort.h headers should be
squashed.

Rasmus