linux-kernel - Re: [patch 1/2] ufd v1 - unsequential O(1) fdmap core

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20070604141235.GA24352@elte.hu>
Date:	Mon, 4 Jun 2007 16:12:35 +0200
From:	Ingo Molnar <mingo@...e.hu>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	Davide Libenzi <davidel@...ilserver.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Ulrich Drepper <drepper@...hat.com>
Subject: Re: [patch 1/2] ufd v1 - unsequential O(1) fdmap core

* Eric Dumazet <dada1@...mosbay.com> wrote:

> O(1) lookup doesnt imply it needs to be super-fast. You make a 
> confusion about this.

Davide has written many good speedups for the kernel and he is one of 
the best scalability experts the Linux kernel has today. You could learn 
from Davide a thing or two, instead of lecturing him about O(1) ...

For example, the recent futex.c changes you did in commit 34f01cc1 are, 
and unfortunately there's no better word i can find: plain disgusting. 
You apparently have plopped the 'fshared' code into the existing logic 
via conditionals and have blown up the complexity of the functions for 
no good reason - instead of neatly separating them out. You have added 
_33_ (thirty-three!) new 'if' branches to futex.c! The feature you 
introduced is nice and useful, but for heaven's sake please work on 
cleanliness of your code some more and undo that colossal damage ... 
preferably before working on other areas of the kernel.

> O(128) is still O(1) for instance. Having to search a bit in a PAGE is 
> a sensible compromise, if we dont add overhead on each fget() calls.

hm, i'm not sure what you are talking about here. Look at Davide's stuff 
- it's clearly not O(128)...

> You add conditional branches on very hot spots.
>
> When you open/close a file, you need to access previous and next 
> cells, so you need 3 cache lines, exactly like current *legacy* code. 
> (one for file pointer, one on each bitmap flags(open/close_on_exec) )

the fd spaces will be separated _no matter what_, that is a physical 
inevitability of the ABI in question. Whether you hide that into 'extra 
complexity by trying to bend bitmaps in a way that the new users dont 
need' or do it explicitly like Davide, i'll go for the explicit 
separation. Davide's approach, besides being cleaner, simpler and faster 
also has the advantage of enabling the possible demoting of the 'legacy' 
fd space in the future. Or demoting the 'new' fd space in the future, if 
the interface does not take off.

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