linux-kernel - Re: [PATCH 1/2] lib: more scalable list

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: <87vdeu96bo.fsf@gmail.com>
Date:	Thu, 21 Jan 2010 19:17:15 -0800
From:	Don Mullis <don.mullis@...il.com>
To:	Andi Kleen <andi@...stfloor.org>
Cc:	linux-kernel@...r.kernel.org, airlied@...hat.com,
	david@...morbit.com, dedekind@...radead.org
Subject: Re: [PATCH 1/2] lib: more scalable list_sort()

Andi Kleen <andi@...stfloor.org> writes:

> On Wed, Jan 20, 2010 at 08:51:26PM -0800, Don Mullis wrote:
>> The use of list_sort() by UBIFS looks like it could generate long
>> lists; this alternative implementation scales better, reaching ~3x
>> performance gain as list length approaches the L2 cache size.
>
> If this can really be called with long lists 
> the function likely needs (optional) need_resched()s
> Otherwise it could ruin scheduling latencies.
>
> -Andi

Being just a dumb library routine, list_sort() has no idea what context
it's been called in, how long a list a particular client could pass in,
nor how expensive the client's cmp() callback might be.

The cmp() callback already passes back a client-private pointer.
Hanging off of this could be a count of calls, or timing information,
maintained by the client.  Whenever some threshold is reached, the
client's cmp() could do whatever good CPU-sharing citizenship required.

This doesn't address the final O(n) pass over the list to restore the
back links.  So the cost of that pass would dictate the upper limit on
list length for a client already using the cmp() call-counting/timing
trick to break up the earlier compare-and-merge passes.

If that's not good enough, a more complicated solution would be
required.  But I'm hoping we don't need to go there yet.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/