![]() | |||||||||||
Messages in this thread Complete thread (EXPERIMENTAL) |
george anzinger wrote: Andrew Morton wrote: george anzinger wrote: --- linux-2.5.50-bk7-kb/include/linux/id_reuse.h Wed Dec 31 16:00:00 1969 +++ linux/include/linux/id_reuse.h Sat Dec 7 21:37:58 2002 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. Hm... This whole thing came up to solve and issue related to having a finite number of timers. The ID layer is just a way of saving a pointer to a given "thing" (a timer structure in this case) in a way that it can be recovered quickly. It is really just a tree structure with 32 branches (or is it sizeof long branches) at each node. There is a bit map to indicate if any free slots are available and if so under which branch. This makes allocation of a new ID quite fast. The "reuse" thing is there to separate it from the original code which "attempted" to not reuse and ID for some time. Sounds a bit like the pid allocator? Is the "don't reuse an ID for some time" requirement still there? I don't see the need for the "don't reuse an ID for some time" thing and it looked like what Jim had messed up the book keeping AND it also looked like it failed to actually work. All of this convinced me that the added complexity was just not worth it. I think you can use radix trees for this. Just put the pointer to your "thing" direct into the tree. The space overhead will be about the same. radix-trees do not currently have a "find next empty slot from this offset" function but that is quite straightforward. Not quite as fast, unless an occupancy bitmap is added to the radix-tree node. That's something whcih I have done before - in fact it was an array of occupancy maps so I could do an efficient in-order gang lookup of "all dirty pages from this offset" and "all locked pages from this offset". It was before its time, and mouldered. Gosh, I think this is what I have. Is it already in the kernel tree somewhere? Oh, I found it. I will look at this, tomorrow... -g ...
A lot of the functions in this header are too large to be inlined.
Hm... What is "too large", i.e. how much code. A few lines, I suspect. Also, is it used more than once?
Don't trust the compiler too much ;) Uninlining mpage_writepage() saved a couple of hundred bytes of code, even though it has only one call site. ...
Please, just open-code the locking. This simply makes it harder to follow the
main code.
But makes it easy to change the lock method, to, for example, use irq or irqsave or "shudder" RCU. A diligent programmer would visit all sites as part of that conversion anyway. +
+static struct idr_layer *id_free; +static int id_free_cnt; hm. We seem to have a global private freelist here. Is the more SMP-friendly slab not suitable? There is a short local free list to avoid calling slab with a spinlock held. Only enough entries are kept to allocate a new node at each branch from the root to leaf, and only for this reason. Fair enough. There are similar requirements elsewhere and the plan there is to create a page reservation API, so you can ensure that the page allocator will be able to provide at least N pages. Then take the lock and go for it. I have code for that which is about to bite the bit bucket. But the new version should be in place soon. Other users will be radix tree nodes, pte_chains and mm_chains (shared pagetable patch). ...
Recursion! Yes, it is a tree after all. lib/radix_tree.c does everything iteratively. +void idr_init(struct idr *idp)
Please tell us a bit about this id layer: what problems it solves, how it solves them, why it is needed and why existing kernel facilities are unsuitable. That might cause problems with 64-bit kernel/32-bit userspace. Passing out kernel addresses in this way may have other problems.. As it is, I need a way to give
the user a handle that he can pass back that will allow me to quickly find his timer and, along the way, validate that he was not spoofing, or just plain confused. So what the ID layer does is pass back an available <id> (which I can pass to the user) while storing a pointer to the timer which is <id>ed. Later, given the <id>, it passes back the pointer, or NULL if the id is not in use. OK. As I said above, the pointers are kept in "nodes" of 32
along with a few bits of overhead, and these are arranged in
a dynamic tree which grows as the number of allocated timers
increases. The depth of the tree is 1 for up to 32 , 2 for
up to 1024, and so on. The depth can never get beyond 5, by
which time the system will, long since, be out of memory.
At this time the leaf nodes are release when empty but the
branch nodes are not. (This is an enhancement saved for
later, if it seems useful.)
I am open to a better method that solves the problem... It seems reasonable. It would be nice to be able to use radix trees, but that's a lot of work if the patch isn't going anywhere. If radix trees are unsuitable then yes, dressing this up as a new core kernel capability (documentation! separate patch!) would be appropriate. But I suspect the radix-tree _will_ suit, and it would be nice to grow the usefulness of radix-trees rather than creating similar-but-different trees. We can do whizzy things with radix-trees; more than at present. Of course, that was only a teeny part of your patch. I just happened to spy it as it flew past. Given that you're at rev 20, perhaps a splitup and more accessible presentation would help. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ -- George Anzinger george@mvista.com High-res-timers: http://sourceforge.net/projects/high-res-timers/ Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml | ||||||||||
![]() | |||||||||||
| Last update: 2005-03-22 12:31 [W:0.575 / U:0.240 seconds] ©2003-2005 Jasper Spaans | |||||||||||