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

[Jim Houston <jim.houston@attbi.com>]

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.