03 Nov, 2011
1 commit
-
It's often convenient to be able to release resource from IRQ context.
Make ida_simple_*() use irqsave/restore spin ops so that they are IRQ
safe.Signed-off-by: Tejun Heo
Acked-by: Rusty Russell
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
01 Nov, 2011
1 commit
-
Signed-off-by: Wang Sheng-Hui
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
15 Sep, 2011
1 commit
-
Fast-forward merge with Linus to be able to merge patches
based on more recent version of the tree.
04 Aug, 2011
2 commits
-
Signed-off-by: Paul Bolle
Signed-off-by: Jiri Kosina -
The current hyper-optimized functions are overkill if you simply want to
allocate an id for a device. Create versions which use an internal
lock.In followup patches, numerous drivers are converted to use this
interface.Thanks to Tejun for feedback.
Signed-off-by: Rusty Russell
Acked-by: Tejun Heo
Acked-by: Jonathan Cameron
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
27 Oct, 2010
2 commits
-
Add idr/ida to kernel-api docbook.
Fix typos and kernel-doc notation.Signed-off-by: Randy Dunlap
Acked-by: Tejun Heo
Cc: Naohiro Aota
Cc: Jiri Kosina
Signed-off-by: Linus Torvalds -
Despite the idr_pre_get() kernel-doc, there are some cases where you can
call idr_pre_get() from within locked regions. Add a description for such
cases.See also: http://lkml.org/lkml/2010/9/16/462
[akpm@linux-foundation.org: cleanups, grammatical fixes]
Signed-off-by: Naohiro Aota
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
31 Aug, 2010
2 commits
-
It was unclear in original kernel-doc how nextidp worked in
idr_get_next(). Let's describe it.Signed-off-by: Naohiro Aota
Acked-by: Tejun Heo
Signed-off-by: Jiri Kosina -
Fix the following kernel-doc warnings.
% perl scripts/kernel-doc lib/idr.c > /dev/null
Warning(lib/idr.c:300): No description found for parameter 'starting_id'
Warning(lib/idr.c:300): Excess function parameter 'start_id' description in 'idr_get_new_above'
Warning(lib/idr.c:485): No description found for parameter 'idp'
Warning(lib/idr.c:596): No description found for parameter 'nextidp'
Warning(lib/idr.c:596): Excess function parameter 'id' description in 'idr_get_next'
Warning(lib/idr.c:774): No description found for parameter 'starting_id'
Warning(lib/idr.c:774): Excess function parameter 'staring_id' description in 'ida_get_new_above'
Warning(lib/idr.c:918): No description found for parameter 'ida'Signed-off-by: Naohiro Aota
Acked-by: Tejun Heo
Signed-off-by: Jiri Kosina
23 Jun, 2010
1 commit
-
Convert to rcu_dereference_raw() given that many callers may have many
different locking models.Located-by: Miles Lane
Tested-by: Miles Lane
Signed-off-by: Paul E. McKenney
28 May, 2010
1 commit
-
Currently idr_remove_all will fail with a use after free error if
idr::layers is bigger than 2, which on 32 bit systems corresponds to items
more than 1024. This is due to stepping back too many levels during
backtracking. For simplicity let's assume that IDR_BITS=1 -> we have 2
nodes at each level below the root node and each leaf node stores two IDs.
(In reality for 32 bit systems IDR_BITS=5, with 32 nodes at each sub-root
level and 32 IDs in each leaf node). The sequence of freeing the nodes at
the moment is as follows:layer
1 -> a(7)
2 -> b(3) c(5)
3 -> d(1) e(2) f(4) g(6)Until step 4 things go fine, but then node c is freed, whereas node g
should be freed first. Since node c contains the pointer to node g we'll
have a use after free error at step 6.How many levels we step back after visiting the leaf nodes is currently
determined by the msb of the id we are currently visiting:Step
1. node d with IDs 0,1 is freed, current ID is advanced to 2.
msb of the current ID bit 1. This means we need to step back
1 level to node b and take the next sibling, node e.
2-3. node e with IDs 2,3 is freed, current ID is 4, msb is bit 2.
This means we need to step back 2 levels to node a, freeing
node b on the way.
4-5. node f with IDs 4,5 is freed, current ID is 6, msb is still
bit 2. This means we again need to step back 2 levels to node
a and free c on the way.
6. We should visit node g, but its pointer is not available as
node c was freed.The fix changes how we determine the number of levels to step back.
Instead of deducting this merely from the msb of the current ID, we should
really check if advancing the ID causes an overflow to a bit position
corresponding to a given layer. In the above example overflow from bit 0
to bit 1 should mean stepping back 1 level. Overflow from bit 1 to bit 2
should mean stepping back 2 levels and so on.The fix was tested with IDs up to 1 << 20, which corresponds to 4 layers
on 32 bit systems.Signed-off-by: Imre Deak
Reviewed-by: Tejun Heo
Cc: Eric Paris
Cc: "Paul E. McKenney"
Cc: [2.6.34.1]
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
26 Mar, 2010
1 commit
-
Conflicts:
drivers/mtd/nand/sh_flctl.cMaxim's patch to initialise sysfs attributes depends on the patch which
actually adds sysfs_attr_init().
27 Feb, 2010
1 commit
-
The SmartMedia FTL code depends on new kfifo bits from 2.6.33
25 Feb, 2010
2 commits
-
idr_get_next() was accidentally not exported when added. It is about
to be used by mtdcore, which may be built as a module.Signed-off-by: Ben Hutchings
Acked-by: KAMEZAWA Hiroyuki
Signed-off-by: Artem Bityutskiy
Signed-off-by: David Woodhouse -
Because idr can be used with any of a number of locks or with
any flavor of RCU, just disable the lockdep-based diagnostics.
If idr needs diagnostics, the check expression will need to be
passed into the relevant idr primitives as an additional
argument.Signed-off-by: Paul E. McKenney
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: mathieu.desnoyers@polymtl.ca
Cc: josh@joshtriplett.org
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
Cc: rostedt@goodmis.org
Cc: Valdis.Kletnieks@vt.edu
Cc: dhowells@redhat.com
LKML-Reference:
Signed-off-by: Ingo Molnar
23 Feb, 2010
1 commit
-
This is retry of reverted 859ddf09743a8cc680af33f7259ccd0fd36bfe9d
("idr: fix a critical misallocation bug") which contained two bugs.* pa[idp->layers] should be cleared even if it's not used by
sub_alloc() because it's used by mark idr_mark_full().* The original condition check also assigned pa[l] to p which the new
code didn't do thus leaving p pointing at the wrong layer.Both problems have been fixed and the idr code has received good amount
testing using userland testing setup where simple bitmap allocator is
run parallel to verify the result of idr allocation.The bug this patch fixes is caused by sub_alloc() optimization path
bypassing out-of-room condition check and restarting allocation loop
with starting value higher than maximum allowed value. For detailed
description, please read commit message of 859ddf09.Signed-off-by: Tejun Heo
Based-on-patch-from: Eric Paris
Reported-by: Eric Paris
Tested-by: Stefan Lippers-Hollmann
Tested-by: Serge Hallyn
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
05 Feb, 2010
1 commit
-
Commit 859ddf09743a8cc680af33f7259ccd0fd36bfe9d tried to fix
misallocation bug but broke full bit marking by not clearing
pa[idp->layers] and also is causing X failures due to lookup failure
in drm code. The cause of the latter hasn't been found yet. Revert
the fix for now.Signed-off-by: Tejun Heo
Signed-off-by: Linus Torvalds
03 Feb, 2010
1 commit
-
Eric Paris located a bug in idr. With IDR_BITS of 6, it grows to three
layers when id 4096 is first allocated. When that happens, idr wraps
incorrectly and searches the idr array ignoring the high bits. The
following test code from Eric demonstrates the bug nicely.#include
#include
#includestatic DEFINE_IDR(test_idr);
int init_module(void)
{
int ret, forty95, forty96;
void *addr;/* add 2 entries both with 4095 as the start address */
again1:
if (!idr_pre_get(&test_idr, GFP_KERNEL))
return -ENOMEM;
ret = idr_get_new_above(&test_idr, (void *)4095, 4095, &forty95);
if (ret) {
if (ret == -EAGAIN)
goto again1;
return ret;
}
if (forty95 != 4095)
printk(KERN_ERR "hmmm, forty95=%d\n", forty95);again2:
if (!idr_pre_get(&test_idr, GFP_KERNEL))
return -ENOMEM;
ret = idr_get_new_above(&test_idr, (void *)4096, 4095, &forty96);
if (ret) {
if (ret == -EAGAIN)
goto again2;
return ret;
}
if (forty96 != 4096)
printk(KERN_ERR "hmmm, forty96=%d\n", forty96);/* try to find the 2 entries, noticing that 4096 broke */
addr = idr_find(&test_idr, forty95);
if ((int)addr != forty95)
printk(KERN_ERR "hmmm, after find forty95=%d addr=%d\n", forty95, (int)addr);
addr = idr_find(&test_idr, forty96);
if ((int)addr != forty96)
printk(KERN_ERR "hmmm, after find forty96=%d addr=%d\n", forty96, (int)addr);
/* really weird, the entry which should be at 4096 is actually at 0!! */
addr = idr_find(&test_idr, 0);
if ((int)addr)
printk(KERN_ERR "found an entry at id=0 for addr=%d\n", (int)addr);idr_remove(&test_idr, forty95);
idr_remove(&test_idr, forty96);return 0;
}void cleanup_module(void)
{
}MODULE_AUTHOR("Eric Paris ");
MODULE_DESCRIPTION("Simple idr test");
MODULE_LICENSE("GPL");This happens because when sub_alloc() back tracks it doesn't always do it
step-by-step while the over-the-limit detection assumes step-by-step
backtracking. The logic in sub_alloc() looks like the following.restart:
clear pa[top level + 1] for end cond detection
l = top level
while (true) {
search for empty slot at this level
if (not found) {
push id to the next possible value
l++
A: if (pa[l] is clear)
failed, return asking caller to grow the tree
if (going up 1 level gives more slots to search)
continue the while loop above with the incremented l
else
C: goto restart
}
adjust id accordingly to the found slot
if (l == 0)
return found id;
create lower level if not there yet
record pa[l] and l--
}Test A is the fail exit condition but this assumes that failure is
propagated upwared one level at a time but the B optimization path breaks
the assumption and restarts the whole thing with a start value which is
above the possible limit with the current layers. sub_alloc() assumes the
start id value is inside the limit when called and test A is the only exit
condition check, so it ends up searching for empty slot while ignoring
high set bit.So, for 4095->4096 test, level0 search fails but pa[1] contains a valid
pointer. However, going up 1 level wouldn't give any more empty slot so
it takes C and when the whole thing restarts nobody notices the high bit
set beyond the top level.This patch fixes the bug by changing the fail exit condition check to full
id limit check.Based-on-patch-from: Eric Paris
Reported-by: Eric Paris
Signed-off-by: Tejun Heo
Cc:
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
04 Dec, 2009
1 commit
-
fix some typos and punctuation in comments
Signed-off-by: Thadeu Lima de Souza Cascardo
Signed-off-by: Jiri Kosina
03 Apr, 2009
1 commit
-
Patch for Per-CSS(Cgroup Subsys State) ID and private hierarchy code.
This patch attaches unique ID to each css and provides following.
- css_lookup(subsys, id)
returns pointer to struct cgroup_subysys_state of id.
- css_get_next(subsys, id, rootid, depth, foundid)
returns the next css under "root" by scanningWhen cgroup_subsys->use_id is set, an id for css is maintained.
The cgroup framework only parepares
- css_id of root css for subsys
- id is automatically attached at creation of css.
- id is *not* freed automatically. Because the cgroup framework
don't know lifetime of cgroup_subsys_state.
free_css_id() function is provided. This must be called by subsys.There are several reasons to develop this.
- Saving space .... For example, memcg's swap_cgroup is array of
pointers to cgroup. But it is not necessary to be very fast.
By replacing pointers(8bytes per ent) to ID (2byes per ent), we can
reduce much amount of memory usage.- Scanning without lock.
CSS_ID provides "scan id under this ROOT" function. By this, scanning
css under root can be written without locks.
ex)
do {
rcu_read_lock();
next = cgroup_get_next(subsys, id, root, &found);
/* check sanity of next here */
css_tryget();
rcu_read_unlock();
id = found + 1
} while(...)Characteristics:
- Each css has unique ID under subsys.
- Lifetime of ID is controlled by subsys.
- css ID contains "ID" and "Depth in hierarchy" and stack of hierarchy
- Allowed ID is 1-65535, ID 0 is UNUSED ID.Design Choices:
- scan-by-ID v.s. scan-by-tree-walk.
As /proc's pid scan does, scan-by-ID is robust when scanning is done
by following kind of routine.
scan -> rest a while(release a lock) -> conitunue from interrupted
memcg's hierarchical reclaim does this.- When subsys->use_id is set, # of css in the system is limited to
65535.[bharata@linux.vnet.ibm.com: remove rcu_read_lock() from css_get_next()]
Signed-off-by: KAMEZAWA Hiroyuki
Acked-by: Paul Menage
Cc: Li Zefan
Cc: Balbir Singh
Cc: Daisuke Nishimura
Signed-off-by: Bharata B Rao
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
11 Mar, 2009
1 commit
-
Fix a problem in the IDR system, where an idr_remove_all() hands a data
element to call_rcu() (via free_layer()) before making that data element
inaccessible to new readers. This is very bad, and results in readers
still having a reference to this data element at the end of the grace
period.Tests on large machines that concurrently map and unmap user-space memory
within the same multithreaded process result in crashes within about five
minutes. Applying this patch increases the kernel's longevity to the
three-to-eight-hour range.There appear to be other similar problems in idr_get_empty_slot() and
sub_remove(), but I fixed the easy one in idr_remove_all() first. It is
therefore no surprise that failures still occur.Located-by: Milton Miller II
Tested-by: Milton Miller II
Signed-off-by: Paul E. McKenney
Cc: Manfred Spraul
Cc: Ingo Molnar
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
16 Jan, 2009
2 commits
-
David points out that the idr_remove_all() function returns unused slabs
to the kmem cache, but needs to zero them first or else they will be
uninitialized upon next use. This causes crashes which have been observed
in the firewire subsystem.He fixed this by zeroing the object before freeing it in idr_remove_all().
But we agree that simply removing the constructor and zeroing the object
at allocation time is simpler than relying upon slab constructor machinery
and might even be faster.This problem was introduced by "idr: make idr_remove rcu-safe" (commit
cf481c20c476ad2c0febdace9ce23f5a4db19582), which was first released in
2.6.27.There are no known codesites which trigger this bug in 2.6.27 or 2.6.28.
The post-2.6.28 firewire changes are the only known triggerer.There might of course be not-yet-discovered triggerers in 2.6.27 and
2.6.28, and there might be out-of-tree triggerers which are added to those
kernel versions. I'll let the -stable guys decide whether they want to
backport this fix.Reported-by: David Moore
Cc: Stefan Richter
Cc: Nadia Derbey
Cc: Paul E. McKenney
Cc: Manfred Spraul
Cc: Kristian Hgsberg
Acked-by: Pekka Enberg
Cc:
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
idr_get_new_above() and ida_get_new_above() return an id in the range of
@staring_id ... 0x7fffffff, not 0 ... 0x7fffffff.Signed-off-by: Li Zefan
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
11 Dec, 2008
1 commit
-
The last patch to lib/idr.c caused a bug if idr_get_new_above() was
called on an empty idr.Usually, nodes stay on the same layer. New layers are added to the top
of the tree.The exception is idr_get_new_above() on an empty tree: In this case, the
new root node is first added on layer 0, then moved upwards. p->layer
was not updated.As usual: You shall never rely on the source code comments, they will
only mislead you.Signed-off-by: Manfred Spraul
Signed-off-by: Linus Torvalds
02 Dec, 2008
1 commit
-
2nd part of the fixes needed for
http://bugzilla.kernel.org/show_bug.cgi?id=11796.When the idr tree is either grown or shrunk, then the update to the number
of layers and the top pointer were not atomic. This race caused crashes.The attached patch fixes that by replicating the layers counter in each
layer, thus idr_find doesn't need idp->layers anymore.Signed-off-by: Manfred Spraul
Cc: Clement Calmels
Cc: Nadia Derbey
Cc: Pierre Peiffer
Cc:
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
27 Jul, 2008
1 commit
-
Kmem cache passed to constructor is only needed for constructors that are
themselves multiplexeres. Nobody uses this "feature", nor does anybody uses
passed kmem cache in non-trivial way, so pass only pointer to object.Non-trivial places are:
arch/powerpc/mm/init_64.c
arch/powerpc/mm/hugetlbpage.cThis is flag day, yes.
Signed-off-by: Alexey Dobriyan
Acked-by: Pekka Enberg
Acked-by: Christoph Lameter
Cc: Jon Tollefson
Cc: Nick Piggin
Cc: Matt Mackall
[akpm@linux-foundation.org: fix arch/powerpc/mm/hugetlbpage.c]
[akpm@linux-foundation.org: fix mm/slab.c]
[akpm@linux-foundation.org: fix ubifs]
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
26 Jul, 2008
6 commits
-
Introduce the free_layer() routine: it is the one that actually frees memory
after a grace period has elapsed.Signed-off-by: Nadia Derbey
Reviewed-by: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Cc: Pierre Peiffer
Acked-by: Rik van Riel
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Make idr_find rcu-safe: it can now be called inside an rcu_read critical
section.Signed-off-by: Nadia Derbey
Reviewed-by: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Cc: Pierre Peiffer
Acked-by: Rik van Riel
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Make the idr_get_new* routines rcu-safe.
Signed-off-by: Nadia Derbey
Reviewed-by: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Cc: Pierre Peiffer
Acked-by: Rik van Riel
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Do some code factorization in the return code analysis.
Signed-off-by: Nadia Derbey
Cc: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Cc: Pierre Peiffer
Acked-by: Rik van Riel
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
Fix the incomplete printk call.
Signed-off-by: Nadia Derbey
Reviewed-by: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Cc: Pierre Peiffer
Acked-by: Rik van Riel
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
This is a trivial patch that renames:
. alloc_layer to get_from_free_list since it idr_pre_get that actually
allocates memory.
. free_layer to move_to_free_list since memory is not actually freed there.This makes things more clear for the next patches.
Signed-off-by: Nadia Derbey
Reviewed-by: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Cc: Pierre Peiffer
Acked-by: Rik van Riel
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
01 May, 2008
1 commit
-
The return inside the loop makes us free only a single layer.
Signed-off-by: Nadia Derbey
Cc: "Paul E. McKenney"
Cc: Manfred Spraul
Cc: Jim Houston
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
29 Apr, 2008
1 commit
-
Avoid a possible kmem_cache_create() failure by creating idr_layer_cache
unconditionary at boot time rather than creating it on-demand when idr_init()
is called the first time.This change also enables us to eliminate the check every time idr_init() is
called.[akpm@linux-foundation.org: rename init_id_cache() to idr_init_cache()]
[akpm@linux-foundation.org: fix alpha build]
Signed-off-by: Akinobu Mita
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
17 Oct, 2007
1 commit
-
Slab constructors currently have a flags parameter that is never used. And
the order of the arguments is opposite to other slab functions. The object
pointer is placed before the kmem_cache pointer.Convert
ctor(void *object, struct kmem_cache *s, unsigned long flags)
to
ctor(struct kmem_cache *s, void *object)
throughout the kernel
[akpm@linux-foundation.org: coupla fixes]
Signed-off-by: Christoph Lameter
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
15 Oct, 2007
1 commit
-
Signed-off-by: Al Viro
Signed-off-by: Linus Torvalds
01 Aug, 2007
1 commit
-
"error" is always equal to 0.
Signed-off-by: Oleg Nesterov
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
20 Jul, 2007
1 commit
-
Slab destructors were no longer supported after Christoph's
c59def9f222d44bb7e2f0a559f2906191a0862d7 change. They've been
BUGs for both slab and slub, and slob never supported them
either.This rips out support for the dtor pointer from kmem_cache_create()
completely and fixes up every single callsite in the kernel (there were
about 224, not including the slab allocator definitions themselves,
or the documentation references).Signed-off-by: Paul Mundt
17 Jul, 2007
2 commits
-
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
Cc: Tejun Heo
Cc: Dave Airlie
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
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
Cc: Tejun Heo
Cc: Dave Airlie
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
