linux/lib, branch v2.6.26-rc7

radix-tree: fix small lockless radix-tree bug

2008-06-13T01:05:41Z

We shrink a radix tree when its root node has only one child, in the left most slot. The child becomes the new root node. To perform this operation in a manner compatible with concurrent lockless lookups, we atomically switch the root pointer from the parent to its child. However a concurrent lockless lookup may now have loaded a pointer to the parent (and is presently deciding what to do next). For this reason, we also have to keep the parent node in a valid state after shrinking the tree, until the next RCU grace period -- otherwise this lookup with the parent pointer may not do the right thing. Notably, we need to keep the child in the left most slot there in case that is requested by the lookup. This is all pretty standard RCU stuff. It is worth repeating because in my eagerness to obey the radix tree node constructor scheme, I had broken it by zeroing the radix tree node before the grace period. What could happen is that a lookup can load the parent pointer, then decide it wants to follow the left most child slot, only to find the slot contained NULL due to the concurrent shrinker having zeroed the parent node before waiting for a grace period. The lookup would return a false negative as a result. Fix it by doing that clearing in the RCU callback. I would normally want to rip out the constructor entirely, but radix tree nodes are one of those places where they make sense (only few cachelines will be touched soon after allocation). This was never actually found in any lockless pagecache testing or by the test harness, but by seeing the odd problem with my scalable vmap rewrite. I have not tickled the test harness into reproducing it yet, but I'll keep working at it. Fortunately, it is not a problem anywhere lockless pagecache is used in mainline kernels (pagecache probe is not a guarantee, and brd does not have concurrent lookups and deletes). Signed-off-by: Nick Piggin Acked-by: Peter Zijlstra Cc: "Paul E. McKenney" Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

add an inlined version of iter_div_u64_rem

2008-06-12T08:47:58Z

iter_div_u64_rem is used in the x86-64 vdso, which cannot call other kernel code. For this case, provide the always_inlined version, __iter_div_u64_rem. Signed-off-by: Jeremy Fitzhardinge Signed-off-by: Ingo Molnar

common implementation of iterative div/mod

2008-06-12T08:47:56Z

We have a few instances of the open-coded iterative div/mod loop, used when we don't expcet the dividend to be much bigger than the divisor. Unfortunately modern gcc's have the tendency to strength "reduce" this into a full mod operation, which isn't necessarily any faster, and even if it were, doesn't exist if gcc implements it in libgcc. The workaround is to put a dummy asm statement in the loop to prevent gcc from performing the transformation. This patch creates a single implementation of this loop, and uses it to replace the open-coded versions I know about. Signed-off-by: Jeremy Fitzhardinge Cc: Andrew Morton Cc: john stultz Cc: Segher Boessenkool Cc: Christian Kujau Cc: Robert Hancock Signed-off-by: Ingo Molnar

lib: export bitrev16

2008-06-06T18:29:10Z

Bluetooth will be able to use this. Signed-off-by: Harvey Harrison Cc: Marcel Holtmann Cc: Dave Young Cc: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lmb: Fix compile warning

2008-05-19T04:35:43Z

lib/lmb.c: In function 'lmb_dump_all': lib/lmb.c:51: warning: format '%lx' expects type 'long unsigned int', but argument 2 has type 'u64' Signed-off-by: Kumar Gala

Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/ericvh/v9fs

2008-05-15T02:30:51Z

* 'for-linus' of ssh://master.kernel.org/pub/scm/linux/kernel/git/ericvh/v9fs: 9p: fix error path during early mount 9p: make cryptic unknown error from server less scary 9p: fix flags length in net 9p: Correct fidpool creation failure in p9_client_create 9p: use struct mutex instead of struct semaphore 9p: propagate parse_option changes to client and transports fs/9p/v9fs.c (v9fs_parse_options): Handle kstrdup and match_strdup failure. 9p: Documentation updates add match_strlcpy() us it to make v9fs make uname and remotename parsing more robust

Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparc-2.6

2008-05-15T02:11:36Z

* git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparc-2.6: sparc64: Use a TS_RESTORE_SIGMASK lmb: Make lmb debugging more useful. lmb: Fix inconsistent alignment of size argument. sparc: Fix mremap address range validation.

lib: create common ascii hex array

2008-05-15T02:11:14Z

Add a common hex array in hexdump.c so everyone can use it. Add a common hi/lo helper to avoid the shifting masking that is done to get the upper and lower nibbles of a byte value. Pull the pack_hex_byte helper from kgdb as it is opencoded many places in the tree that will be consolidated. Signed-off-by: Harvey Harrison Acked-by: Paul Mundt Cc: Jason Wessel Cc: Ingo Molnar Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

add match_strlcpy() us it to make v9fs make uname and remotename parsing more robust

2008-05-15T00:23:25Z

match_strcpy() is a somewhat creepy function: the caller needs to make sure that the destination buffer is big enough, and when he screws up or forgets, match_strcpy() happily overruns the buffer. There's exactly one customer: v9fs_parse_options(). I believe it currently can't overflow its buffer, but that's not exactly obvious. The source string is a substing of the mount options. The kernel silently truncates those to PAGE_SIZE bytes, including the terminating zero. See compat_sys_mount() and do_mount(). The destination buffer is obtained from __getname(), which allocates from name_cachep, which is initialized by vfs_caches_init() for size PATH_MAX. We're safe as long as PATH_MAX <= PAGE_SIZE. PATH_MAX is 4096. As far as I know, the smallest PAGE_SIZE is also 4096. Here's a patch that makes the code a bit more obviously correct. It doesn't depend on PATH_MAX <= PAGE_SIZE. Signed-off-by: Markus Armbruster Cc: Latchesar Ionkov Cc: Jim Meyering Cc: "Randy.Dunlap" Signed-off-by: Andrew Morton Signed-off-by: Eric Van Hensbergen

cpumask: remove bitmap_scnprintf_len and cpumask_scnprintf_len

2008-05-13T15:02:25Z

They aren't used. They were briefly used as part of some other patches to provide an alternative format for displaying some /proc and /sys cpumasks. They probably should have been removed when those other patches were dropped, in favor of a different solution. Signed-off-by: Paul Jackson Cc: "Mike Travis" Cc: "Bert Wesarg" Cc: Alexey Dobriyan Cc: WANG Cong Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds