Skip to contentSkip to conversation

High-res-timers part 3 (posix to hrposix) take 20

PATCH Jim Houston 2 participants 5 messages Dec 9, 2002 – Dec 10, 2002

lore
Share & tools
lore

Jim Houston

author
#0 lore raw
Quoted 4 lines · Andrew Morton

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.

#1 lore raw
Quoted 6 lines · Jim Houston

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 kernel.org, 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.

Bill

author
#2 lore raw
Quoted 19 lines · William Lee Irwin III
Quoted 6 lines · Jim Houston

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 kernel.org, which puts it sometime before May (obviously I spent time writing & testing before dropping it onto an ftp site).

Quoted 5 lines

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.

Bill

Hi Bill,

Gee Bill, what can I say? I'm sorry I misattributed your work to Ingo.

I'm curious about the reaction to recursion. I use the obvious loop for the lookup path, but the allocate and remove cases start getting ugly as an iterative solution.

Jim Houston - Concurrent Computer Corp.

#3 lore raw
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines

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.

Quoted 1 line · Jim Houston

Gee Bill, what can I say? I'm sorry I misattributed your work to Ingo.

Ingo did a large bit of work wrt. mergeability, the for_each_task_pid() macro, folded the separately allocated idtag structures into the task_t, redid the pid allocator to handle thelarger spaces, and fixed several severe bugs, so he should be given due credit. I'd say it was a collaborative effort, though separated somewhat by the times we actually worked on it.

Quoted 3 lines · Jim Houston

I'm curious about the reaction to recursion. I use the obvious loop for the lookup path, but the allocate and remove cases start getting ugly as an iterative solution.

Deep call stacks are not cheap on all arches, ISTR SPARC(64?) and S/390 having some relatively obscene overheads. Going iterative didn't actually look that bad here, but sleeping etc. for memory weren't in the picture for me.

Bill