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: Windows password security audit tool. GUI, reports in PDF.

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

Date:	Mon, 4 Jun 2007 16:27:21 +0200
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Ingo Molnar <mingo@...e.hu>
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

On Mon, 4 Jun 2007 16:12:35 +0200
Ingo Molnar <mingo@...e.hu> wrote:

> 
> * 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) ...
> 

I know who is Davide, thank you :)

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

This code took the normal path for inclusion and discussion. If you find it so horrible, 
you should complained before. Fact is that you Acked it :)

If you wanted to make a joke, I find it quite misplaced.

> > 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)...

I am talking about my suggestion to use a bitmap search limited to one page.

So I named it O(128), this clearly should be labeled O(PAGE_SIZE/L1_CACHE_BYTES)

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