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

From: Jim Houston (
Date: Mon Dec 09 2002 - 10:24:49 EST

Andrew Morton wrote:

> Maybe I'm thick, but this whole id_resue layer seems rather obscure.
> As it is being positioned as a general-purpose utility it needs
> API documentation as well as a general description.

Hi Andrew, George, Everyone,

This is derived from my "alternate Posix timers" patch. It
was intended to be a general purpose allocator and lookup
for user space ids (e.g. pids, timer_ids, msg_ids).
It uses a radix tree as a sparse array to map a user id value
to a kernel pointer. In my version it did pid style allocation
avoiding immediate reuse of the same id values. The goals
were to avoid hardwired limits, be memory efficient and fast.

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.

Here is my version of this interface:

void *id2ptr_lookup(struct id *idp, int id)

        This looks up the user id value in the idp name space
        and returns the associated kernel pointer.

int id2ptr_new(struct id *idp, void *ptr)

        This allocates and returns a new id and stores the
        ptr value in the sparse array

void id2ptr_remove(struct id *idp, int id)

        removes the id from the idp name space.

void id2ptr_init(struct id *idp, int min_wrap)

        Initializes the idp name space. The min_wrap value
        determines when to start reusing id values.

I think what I have done is useful and useable. If/when I do
this again I would separate growing the tree from the id
allocation. I think this would avoid needing to keep
the free list of preallocated memory.

Jim Houston - Concurrent Computer Corp.
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:14 EST