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]

Message-ID: <46633047.1020707@cosmosbay.com>
Date:	Sun, 03 Jun 2007 23:19:03 +0200
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Davide Libenzi <davidel@...ilserver.org>
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

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 ?

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.

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