contributing to fbsd

[David Schultz]

On Fri, Mar 25, 2005, Andriy Tkachuk wrote:
> As I see now there is for example O(n) algorithm for
> process IDs allocation... In linux it is addressed
> using bit-mapping (as far as i understand).
> In Oct 2003 there was topic in this list:
> "Some mmap observations compared to Linux 2.6/OpenBSD"
> in which allocation in mmap was discussed.
> As it was appeared that fbsd use O(n) algorithm here compared
> to Linux and OpenBSD. I don't know the presend state of this.

tjr has some patches to do O(1) pid allocation, although I believe
he's been busy with work recently.  Jun Su ported NetBSD's O(1)
pid allocator, although that allocator is significantly more
complicated, and not measurably faster.  So basically this is
already done; someone just needs to get around to integrating it.

pids are hard to do generically because of the special rules about
allocating them.  You don't want to recycle them too quickly, for
instance.

> Anyway as for me it looks very attractive to have
> universal O(1) facility for allocation of any kernel resources
> as well as on smp-configurations than using differend
> adhoc's in different parts of kernel.
> I seems to me, that Linux doesn't also use some
> universal allocation approach but O(1) adhocs instead.
> I may mistaken in this.

You should also take a look at FreeBSD's kern/subr_unit.c.  It
isn't as fast as vmem, but perhaps it's fast enough.  The first
thing to do would be to do some profiling on current and potential
applications of the allocator to see where your time would be best
spent.