linux-stable.git/lib/idr.c, branch v2.6.30

cgroup: CSS ID support

2009-04-03T02:04:53+00:00

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 scanning

When 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

idr: make idr_remove_all() do removal -before- free_layer()

2009-03-10T22:55:11+00:00

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

lib/idr.c: use kmem_cache_zalloc() for the idr_layer cache

2009-01-16T00:39:40+00:00

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: fix wrong kernel-doc

2009-01-16T00:39:37+00:00

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

lib/idr.c: Fix bug introduced by RCU fix

2008-12-10T21:34:33+00:00

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

lib/idr.c: fix rcu related race with idr_find

2008-12-02T03:55:25+00:00

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

SL*B: drop kmem cache argument from constructor

2008-07-26T19:00:07+00:00

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.c

This 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

idr: make idr_remove rcu-safe

2008-07-25T17:53:42+00:00

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

idr: make idr_find rcu-safe

2008-07-25T17:53:42+00:00

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

idr: make idr_get_new* rcu-safe

2008-07-25T17:53:42+00:00

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