linux-kernel - Re: [PATCH] lib/list_sort: fix function type mismatches

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]

Message-Id: <202001111144.00BBiXEq002960@sdf.org>
Date:   Sat, 11 Jan 2020 11:44:33 GMT
From:   George Spelvin <lkml@....org>
To:     andy.shevchenko@...il.com, keith.busch@...el.com, lkml@....org
Cc:     akpm@...ux-foundation.org, andriy.shevchenko@...ux.intel.com,
        keescook@...omium.org, linux-kernel@...r.kernel.org,
        linux@...musvillemoes.dk, mchehab+samsung@...nel.org,
        samitolvanen@...gle.com, st5pub@...dex.ru
Subject: Re: [PATCH] lib/list_sort: fix function type mismatches

On Sat, 11 Jan 2020 at 12:35, Andy Shevchenko <andy.shevchenko@...il.com> wrote:
> Hint: When you post Message-Id you may prefix them with
> https://lore.kernel.org/r/ which makes search a bit more convenient
> and faster.

I just learned that https://marc.info/?i= also works, so
https://lore.kernel.org/r/20191007135656.37734-1-andriy.shevchenko@linux.intel.com
https://marc.info/?i=20191007135656.37734-1-andriy.shevchenko@linux.intel.com

https://lore.kernel.org/r/20190416154522.65aaa348161fc581181b56d9@linux-foundation.org
https://marc.info/?i=20190416154522.65aaa348161fc581181b56d9@linux-foundation.org

> For the record, I have just checked users of list_sort() in regard to
> constify of priv parameter and only ACPI HMAT is using it as not
> const. UBIFS and XFS do not change the data (if I didn't miss
> anything).

Yes, that initiator_cmp() at drivers/acpi/hmat/hmat.c:526 is... interesting.

Basically, it wants to fill in a bitmap of all of the processor_pxm
identifiers, so it avoids having a separate list traversal by
setting bits in the compare function (which is guaranteed to visit
each list element at least once).

It ends up setting each bit 2*log2(n) times (since there are an
average of log2(n) compares per element and each compare sets two
bits), but it makes the code smaller.  And although it make the
aggressive performance optimizer in me cringe, I have to agree this
is not performance-critical code and so it's a reasonable thing to do.

I do note, however, that the list_sort is almost immediately followed
by a list_for_each_entry() loop and maybe the bitmap computation
could be folded in there.  Basically start the loop with:

	unsigned int pxm = -1u;	/* Invalid sentinel value */
	list_for_each_entry(initiator, &initiators, node) {
		u32 value;

		if (initiator->processor_pxm != pxm) {
			pxm = initiator->processor_pxm;
			set_bit(pxm, p_nodes);
		} else if (!test_bit(pxm, p_nodes)) {
			continue;
		}

... but oh, whoops, that won't work.  The "almost immediately"
glosses over a second loop, so there are multiple passes over the
initiators list, while we want the bitmap set up only once.

Cc: to Keith Busch <keith.busch@...el.com>, who wrote that code.
Keith, is there a way we could avoid the non-const priv parameter,
just for the sake of code cleanliness in <list_sort.h>?