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]

Date:	Mon, 4 Jun 2007 06:33:23 -0700 (PDT)
From:	Davide Libenzi <davidel@...ilserver.org>
To:	Eric Dumazet <dada1@...mosbay.com>
cc:	Andrew Morton <akpm@...ux-foundation.org>,
	Ingo Molnar <mingo@...e.hu>,
	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, Eric Dumazet wrote:

> Bitmaps are already there, you didnt zap them.
> 
> Your proposal is going to double size taken by file table, since you need two long words
> per file instead of one pointer.
> 
> 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) )
> 
> O(1) lookup doesnt imply it needs to be super-fast. You make a confusion about this.
> 
> 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.
> 
> Instead of adding complexity and a pile of new bugs  (see how long it takes to bring RCU on files to a stable state), we can take a safe path. Then if it happens to still be a problem, we can consider the painfull way.
> 
> I probably can code a < 100 lines patch, later this evening after my day job.

fdmap.c is 300 lines of code, w/out comments. You're trying to fit the 
wrong structure. It is *that* simple.


- Davide


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