Re: Syslets, Threadlets, generic AIO support, v6

[William Lee Irwin III <wli@holomorphy.com>]

On Wed, May 30, 2007 at 02:27:52PM -0700, Linus Torvalds wrote:
> Well, don't think of it as a special case at all: think of bit 30 as a 
> "the user asked for a non-linear fd".
> In fact, to make it effective, I'd suggest literally scrambling the low 
> bits (using, for example, some silly per-boot xor value to to actually 
> generate the "true" index - the equivalent of a really stupid randomizer). 
> That way you'd have the legacy "linear" space, and a separate "non-linear 
> space" where people simply *cannot* make assumptions about contiguous fd 
> allocations. There's no special case there - it's just an extension which 
> explicitly allows us to say "if you do that, your fd's won't be allocated 
> the traditional way any more, but you *can* mix the traditional and the 
> non-linear allocation".

One could always stuff a seed or per-cpu seeds in the files_struct and
use a PRNG. The only trick would be cacheline bounces and/or space
consumption of seeds. Another possibility would be bitreversed
contiguity or otherwise a bit permutation of some contiguous range,
modulo (of course) the high bit used to tag the randomized range.

With "truly" random/sparse fd numbers it may be meaningful to use a
different data structure from a bitmap to track them in-kernel, though
xor and other easily-computed mappings to/from contiguous ranges won't
need such in earnest.


-- wli