> 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 email@example.com
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/