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] [day] [month] [year] [list]

Date:	Wed, 06 Jun 2007 00:29:15 +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>,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: [patch 1/2] ufd v1 - unsequential O(1) fdmap core

Ingo Molnar a écrit :
> 
> no, i just wanted to make a demonstration that one can be pretty nasty 
> in on-lkml replies while being technically correct :-) I think you went 
> a bit overboard in your replies to Davide. Lets move this back into 
> constructive channels, ok? :)

In any case, here is one preliminary patch to show what I had in mind.

I only had time to compile it (its very late here), not even boot tested, so 
dont try it !

[PATCH] reduce max latency of get_unused_fd().

Goal is to scan at most 4096 bytes (or 32768 bits) in the open_fds bitmap.

Processes that have many file descriptors might have to scan 128 KB of ram to 
find a zero bit. Thats about 100 us on modern machines.

This patch introduces an array of counters. Each counter gives the number of 
'one' bits in a 4 KB section of the open_fds bitmap.

I chose to statically allocate this array of counters, being very small (64 
bytes), so a dynamic allocation would only add complexity.

As a result, max latency is 4 us (same latency on x86 when vm gives you a new 
page)

Signed-off-by: Eric Dumazet <dada1@...mosbay.com>
---
  fs/fcntl.c                |   18 +++++++++++++++---
  fs/file.c                 |    6 +++---
  fs/open.c                 |   13 +++++++++++++
  include/linux/file.h      |   11 +++++++++++
  include/linux/fs.h        |    2 --
  include/linux/init_task.h |    1 +
  kernel/fork.c             |    1 +
  7 files changed, 44 insertions(+), 8 deletions(-)

View attachment "fds_counter.patch" of type "text/plain" (5357 bytes)