Re: [PATCH 3/3] High-res-timers part 3 (posix to hrposix) take 20

From: William Lee Irwin III (
Date: Mon Dec 09 2002 - 17:35:15 EST

On Mon, Dec 09, 2002 at 10:24:49AM -0500, Jim Houston wrote:
> I got started on this before Ingo did his magic for hashing
> pids. I prototyped in user space and did a quick hack to
> make it work in the kernel. Yes, it uses a recursive approach
> for the allocate and remove path. The recursion is limited
> to only a few levels and the stack frame is tiny. For example
> if there are 1000000 ids it will have 6 levels of recursion.

I'm not Ingo but you'll figure it out.

Recursion is unnecessary; the depths are bounded by BITS_PER_LONG
divided by the log of the branch factor and looping over levels
directly suffices.

I started somewhat before the first for_each_task-* patches are
dated on, which puts it sometime before May (obviously
I spent time writing & testing before dropping it onto an ftp site).

My original allocator(s) used a radix tree structured bitmap like this
in order to provide hard constant time bounds, but statically-allocated
them. Static allocation didn't fit in with larger pid space, though.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Sun Dec 15 2002 - 22:00:15 EST