linux-kernel - Re: [PATCH] [patch 4a/4] ipc: sem optimise simple operations

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: <20090815045237.GC19195@wotan.suse.de>
Date:	Sat, 15 Aug 2009 06:52:37 +0200
From:	Nick Piggin <npiggin@...e.de>
To:	Manfred Spraul <manfred@...orfullife.com>
Cc:	Andrew Morton <akpm@...ux-foundation.org>,
	Nadia Derbey <Nadia.Derbey@...l.net>,
	Pierre Peiffer <peifferp@...il.com>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] [patch 4a/4] ipc: sem optimise simple operations

On Fri, Aug 14, 2009 at 09:16:00PM +0200, Manfred Spraul wrote:
> An alternative patch to Nick's proposal:
> http://lkml.org/lkml/2009/8/11/11
> The patch is based on Nick's patch.
> 
> The patch is ontop of the first three patches from Nick.
> 
> Identical with Nick's patch:
> - per semaphore list to optimize single sop semop calls:
> This avoids that the semaphore operations have to scan through all waiting
> tasks, even for the tasks that are waiting on a different semaphore from
> the same array.
> 
> Differences:
> - same code for per-semaphore and global list.
> - one list for both wait-for-zero and decrement instead of two lists.
> - unlink_queue helper function
> 
> Open points:
> - further testing
> - understand all changes. e.g. why switch from "if (alter)" to
> 	"if (alter & !error)" in update_queue
> 
> >From the diffstat, it's simpler: 50 new lines instead of 110 new lines.
> 
> Nick: What do you think? Could you try your test app?

The problem with using the same algorithm is that we don't need to
"restart scanning" the simple-op lists when one of them succeeds.
This is because if a negative op fails, then no amount of subsequent
simple negative ops will make it succeed.

With multi-ops, it can be adding and subtracting and waiting for
zero of different sems etc, so in order to try to stay strictly
FIFO, then we always have to recheck all previous failed ops after
one succeeds.

The other problem is that we have to scan all ops in the multi-op
list because we don't know what combination of sem values might
allow the op to succeed. With the single-op lists, we know if the
semval is 0, then we don't have to scan the negative list, and if
it is non-0 then we don't have to scan the zero list.

Combine these two problems and that is where the O(n^2) behaviour
comes in to the complex-op algorithm.

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