aboutsummaryrefslogtreecommitdiff
path: root/lib/idr.c
AgeCommit message (Collapse)Author
2007-07-16lib: add idr_remove_allKristian Hoegsberg
Remove all ids from the given idr tree. idr_destroy() only frees up unused, cached idp_layers, but this function will remove all id mappings and leave all idp_layers unused. A typical clean-up sequence for objects stored in an idr tree, will use idr_for_each() to free all objects, if necessay, then idr_remove_all() to remove all ids, and idr_destroy() to free up the cached idr_layers. Signed-off-by: Kristian Hoegsberg <krh@redhat.com> Cc: Tejun Heo <htejun@gmail.com> Cc: Dave Airlie <airlied@linux.ie> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-07-16lib: add idr_for_each()Kristian Hoegsberg
This patch adds an iterator function for the idr data structure. Compared to just iterating through the idr with an integer and idr_find, this iterator is (almost, but not quite) linear in the number of elements, as opposed to the number of integers in the range covered by the idr. This makes a difference for sparse idrs, but more importantly, it's a nicer way to iterate through the elements. The drm subsystem is moving to idr for tracking contexts and drawables, and with this change, we can use the idr exclusively for tracking these resources. [akpm@linux-foundation.org: fix comment] Signed-off-by: Kristian Hoegsberg <krh@redhat.com> Cc: Tejun Heo <htejun@gmail.com> Cc: Dave Airlie <airlied@linux.ie> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-07-11ida: implement idr based id allocatorTejun Heo
Implement idr based id allocator. ida is used the same way idr is used but lacks id -> ptr translation and thus consumes much less memory. struct ida_bitmap is attached as leaf nodes to idr tree which is managed by the idr code. Each ida_bitmap is 128bytes long and contains slightly less than a thousand slots. ida is more aggressive with releasing extra resources acquired using ida_pre_get(). After every successful id allocation, ida frees one reserved idr_layer if possible. Reserved ida_bitmap is not freed automatically but only one ida_bitmap is reserved and it's almost always used right away. Under most circumstances, ida won't hold on to memory for too long which isn't actively used. Signed-off-by: Tejun Heo <htejun@gmail.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2007-07-11idr: separate out idr_mark_full()Tejun Heo
Separate out idr_mark_full() from sub_alloc() and make marking the allocated slot full the responsibility of idr_get_new_above_int(). Allocation part of idr_get_new_above_int() is renamed to idr_get_empty_slot(). New idr_get_new_above_int() allocates a slot using the function, install the user pointer and marks it full using idr_mark_full(). This change doesn't introduce any behavior change. This will be used by ida. Signed-off-by: Tejun Heo <htejun@gmail.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2007-07-11idr: fix obscure bug in allocation pathTejun Heo
In sub_alloc(), when bitmap search fails, it goes up one level to continue search. This is done by updating the id cursor and searching the upper level again. If the cursor was at the end of the upper level, we need to go further than that. This wasn't implemented and when that happens the part of the cursor which indexes into the upper level wraps and sub_alloc() ends up searching the wrong bitmap. It allocates id which doesn't match the actual slot. This patch fixes this by restarting from the top if the search needs to go higher than one level. Signed-off-by: Tejun Heo <htejun@gmail.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2007-02-11[PATCH] Numerous fixes to kernel-doc info in source files.Robert P. J. Day
A variety of (mostly) innocuous fixes to the embedded kernel-doc content in source files, including: * make multi-line initial descriptions single line * denote some function names, constants and structs as such * change erroneous opening '/*' to '/**' in a few places * reword some text for clarity Signed-off-by: Robert P. J. Day <rpjday@mindspring.com> Cc: "Randy.Dunlap" <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2006-12-07[PATCH] slab: remove kmem_cache_tChristoph Lameter
Replace all uses of kmem_cache_t with struct kmem_cache. The patch was generated using the following script: #!/bin/sh # # Replace one string by another in all the kernel sources. # set -e for file in `find * -name "*.c" -o -name "*.h"|xargs grep -l $1`; do quilt add $file sed -e "1,\$s/$1/$2/g" $file >/tmp/$$ mv /tmp/$$ $file quilt refresh done The script was run like this sh replace kmem_cache_t "struct kmem_cache" Signed-off-by: Christoph Lameter <clameter@sgi.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-07-14[PATCH] Convert idr's internal locking to _irqsave variantRoland Dreier
Currently, the code in lib/idr.c uses a bare spin_lock(&idp->lock) to do internal locking. This is a nasty trap for code that might call idr functions from different contexts; for example, it seems perfectly reasonable to call idr_get_new() from process context and idr_remove() from interrupt context -- but with the current locking this would lead to a potential deadlock. The simplest fix for this is to just convert the idr locking to use spin_lock_irqsave(). In particular, this fixes a very complicated locking issue detected by lockdep, involving the ib_ipoib driver's priv->lock and dev->_xmit_lock, which get involved with the ib_sa module's query_idr.lock. Cc: Arjan van de Ven <arjan@infradead.org> Cc: Ingo Molnar <mingo@elte.hu> Cc: Zach Brown <zach.brown@oracle.com>, Signed-off-by: Roland Dreier <rolandd@cisco.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-26[PATCH] lib: add idr_replaceJeff Mahoney
This patch adds idr_replace() to replace an existing pointer in a single operation. Device-mapper will use this to update the pointer it stored against a given id. Signed-off-by: Jeff Mahoney <jeffm@suse.com> Signed-off-by: Alasdair G Kergon <agk@redhat.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] fix race in idr codeSonny Rao
I ran into a bug where the kernel died in the idr code: cpu 0x1d: Vector: 300 (Data Access) at [c000000b7096f710] pc: c0000000001f8984: .idr_get_new_above_int+0x140/0x330 lr: c0000000001f89b4: .idr_get_new_above_int+0x170/0x330 sp: c000000b7096f990 msr: 800000000000b032 dar: 0 dsisr: 40010000 current = 0xc000000b70d43830 paca = 0xc000000000556900 pid = 2022, comm = hwup 1d:mon> t [c000000b7096f990] c0000000000d2ad8 .expand_files+0x2e8/0x364 (unreliable) [c000000b7096faa0] c0000000001f8bf8 .idr_get_new_above+0x18/0x68 [c000000b7096fb20] c00000000002a054 .init_new_context+0x5c/0xf0 [c000000b7096fbc0] c000000000049dc8 .copy_process+0x91c/0x1404 [c000000b7096fcd0] c00000000004a988 .do_fork+0xd8/0x224 [c000000b7096fdc0] c00000000000ebdc .sys_clone+0x5c/0x74 [c000000b7096fe30] c000000000008950 .ppc_clone+0x8/0xc
2005-10-30[PATCH] Whitespace and CodingStyle cleanup for lib/idr.cJesper Juhl
Cleanup trailing whitespace, blank lines, CodingStyle issues etc, for lib/idr.c Signed-off-by: Jesper Juhl <jesper.juhl@gmail.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-10-28[PATCH] gfp_t: lib/*Al Viro
Signed-off-by: Al Viro <viro@zeniv.linux.org.uk> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-10-23[PATCH] inotify/idr leak fixAndrew Morton
Fix a bug which was reported and diagnosed by Stefan Jones <stefan.jones@churchillrandoms.co.uk> IDR trees include a cache of idr_layer objects. There's no way to destroy this cache, so when we discard an overall idr tree we end up leaking some memory. Add and use idr_destroy() for this. v9fs and infiniband also need to use idr_destroy() to avoid leaks. Or, we make the cache global, like radix_tree_preload(). Which is probably better. Later. Cc: Eric Van Hensbergen <ericvh@ericvh.myip.org> Cc: Roland Dreier <rolandd@cisco.com> Cc: Robert Love <rml@novell.com> Cc: John McCutchan <ttb@tentacle.dhs.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-08-26[PATCH] Document idr_get_new_above() semantics, update inotifyJohn McCutchan
There is an off by one problem with idr_get_new_above. The comment and function name suggest that it will return an id > starting_id, but it actually returned an id >= starting_id, and kernel callers other than inotify treated it as such. The patch below fixes the comment, and fixes inotifys usage. The function name still doesn't match the behaviour, but it never did. Signed-off-by: John McCutchan <ttb@tentacle.dhs.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-21[PATCH] coverity: idr_get_new_above_int() overrun fixZaur Kambarov
This patch fixes overrun of array pa: 92 struct idr_layer *pa[MAX_LEVEL]; in 98 l = idp->layers; 99 pa[l--] = NULL; by passing idp->layers, set in 202 idp->layers = layers; to function sub_alloc in 203 v = sub_alloc(idp, ptr, &id); Signed-off-by: Zaur Kambarov <zkambarov@coverity.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-04-16Linux-2.6.12-rc2v2.6.12-rc2Linus Torvalds
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!