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:	Sun, 3 Jun 2007 15:51:13 -0700 (PDT)
From:	Davide Libenzi <davidel@...ilserver.org>
To:	Eric Dumazet <dada1@...mosbay.com>
cc:	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Ulrich Drepper <drepper@...hat.com>,
	Ingo Molnar <mingo@...e.hu>
Subject: Re: [patch 1/2] ufd v1 - unsequential O(1) fdmap core

On Sun, 3 Jun 2007, Eric Dumazet wrote:

> Davide Libenzi a écrit :
> > Core code for the unsequential fdmap implementation. Random allocation,
> > exact allocation, de-allocation and lookup are all O(1) operations.
> > The only operation that is O(N) is the strict from-N-up kind of allocation,
> > but that only used by F_DUPFD and it's definitely not frequently used
> > (and current code is O(N) too).
> > Like the "struct fdtable", the unsequential fdmap is RCU friendly too.
> > 
> > 
> > 
> 
> Could you please provide a diffstat ?

With or w/out the comments? :)

> Me think : "Huge patch, and icache pressure for what exact gain ?"
>
> File descriptor allocation is dust compared to socket setup costs and network
> stuf. (Not speaking of close() wich is O(1) obviously)
> 
> If we want a different file descriptor allocation, why should we use a
> parallel structure, and adding one level of complexity ?
> 
> Instead of finding the first zero bit in a bitmap, we could just use a cyclic
> allocation, ie finding a zero bit from a 'last' position. Keeping fd_count
> would help not atempting a findzerobit in the case all bits are known to be
> set.

A bitmap allocator made sense because it has the property of making 
allocations compact. Once that requirement is relaxed, it does not make 
any sense to use it (and you have still to modify it in any case).
I generally agree on code re-use, but that just not the right structure. 
You can tweak it how much you like, but you're still doing a search inside 
an N-sized bitmap. It's just the *wrong* structure.
I-cache pressure? All the extra code that you see out of fdmap.c/h, comes 
from handling two "bitmaps", that you still have to have (unless you 
plan to have a single huge botmap that covers legacy and non-sequential 
areas). But with a bitmap structure, you're gonna have more D-cache 
pressure. And that's a fact.

- Davide