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: <20090817064446.GD9962@wotan.suse.de>
Date:	Mon, 17 Aug 2009 08:44:46 +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 Sun, Aug 16, 2009 at 01:29:23PM +0200, Manfred Spraul wrote:
> On 08/16/2009 12:31 PM, Nick Piggin wrote:
> >On Sat, Aug 15, 2009 at 06:32:14PM +0200, Manfred Spraul wrote:
> >   
> >>It depends. After disabling inlining, including all helper functions
> >>that differ:
> >>
> >>My proposal: 301 bytes for update_queue.
> >>
> >>"simple", only negv: 226 bytes
> >>"simple, negv+zero: 354 bytes
> >>simple+complex: 526 bytes.
> >>
> >>Thus with only +-1 simple ops, your version uses less icache. If both
> >>+-1 and 0 ops are used, your version uses more icache.
> >>     
> >Don't forget that in that case, your version is badly suboptimal
> >due to the algorithmic complexity.
> >   
> I know, I mentioned it in the change log:
> Waking up one "decrement by one" task is O(1) with your code and 
> O(1+<number of waiting-for-zero tasks>) with my code.
> 
> This is the price paid for saving memory:
> Your version keeps three pointers per semaphore (waiting-for-zero, 
> oldest decrement, newest decrement)
> My version keeps only two pointers (newest decrement, waiting-for-zero). 
> The "oldest decrement" is reconstructed on the fly, and that operation 
> is O(<number of waiting-for-zero tasks>).

OK, well let's just get something in.

I kind of liked to optimise both cases because it took this long to
uncover this suboptimal behaviour (and the problem isn't even
completely due to suboptimal semaphore but also userspace contention),
so even if there are some workloads with a little problem I don't know
if they will ever get reported/diagnosed.

That said, I'm not too unhappy with your version if you feel strongly
about it.

Thanks for reviewing the other patches too.

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