aboutsummaryrefslogtreecommitdiff
path: root/lib
AgeCommit message (Collapse)Author
2006-07-03[PATCH] lockdep: locking API self testsIngo Molnar
Introduce DEBUG_LOCKING_API_SELFTESTS, which uses the generic lock debugging code's silent-failure feature to run a matrix of testcases. There are 210 testcases currently: +----------------------- | Locking API testsuite: +------------------------------+------+------+------+------+------+------+ | spin |wlock |rlock |mutex | wsem | rsem | -------------------------------+------+------+------+------+------+------+ A-A deadlock: ok | ok | ok | ok | ok | ok | A-B-B-A deadlock: ok | ok | ok | ok | ok | ok | A-B-B-C-C-A deadlock: ok | ok | ok | ok | ok | ok | A-B-C-A-B-C deadlock: ok | ok | ok | ok | ok | ok | A-B-B-C-C-D-D-A deadlock: ok | ok | ok | ok | ok | ok | A-B-C-D-B-D-D-A deadlock: ok | ok | ok | ok | ok | ok | A-B-C-D-B-C-D-A deadlock: ok | ok | ok | ok | ok | ok | double unlock: ok | ok | ok | ok | ok | ok | bad unlock order: ok | ok | ok | ok | ok | ok | --------------------------------------+------+------+------+------+------+ recursive read-lock: | ok | | ok | --------------------------------------+------+------+------+------+------+ non-nested unlock: ok | ok | ok | ok | --------------------------------------+------+------+------+ hard-irqs-on + irq-safe-A/12: ok | ok | ok | soft-irqs-on + irq-safe-A/12: ok | ok | ok | hard-irqs-on + irq-safe-A/21: ok | ok | ok | soft-irqs-on + irq-safe-A/21: ok | ok | ok | sirq-safe-A => hirqs-on/12: ok | ok | ok | sirq-safe-A => hirqs-on/21: ok | ok | ok | hard-safe-A + irqs-on/12: ok | ok | ok | soft-safe-A + irqs-on/12: ok | ok | ok | hard-safe-A + irqs-on/21: ok | ok | ok | soft-safe-A + irqs-on/21: ok | ok | ok | hard-safe-A + unsafe-B #1/123: ok | ok | ok | soft-safe-A + unsafe-B #1/123: ok | ok | ok | hard-safe-A + unsafe-B #1/132: ok | ok | ok | soft-safe-A + unsafe-B #1/132: ok | ok | ok | hard-safe-A + unsafe-B #1/213: ok | ok | ok | soft-safe-A + unsafe-B #1/213: ok | ok | ok | hard-safe-A + unsafe-B #1/231: ok | ok | ok | soft-safe-A + unsafe-B #1/231: ok | ok | ok | hard-safe-A + unsafe-B #1/312: ok | ok | ok | soft-safe-A + unsafe-B #1/312: ok | ok | ok | hard-safe-A + unsafe-B #1/321: ok | ok | ok | soft-safe-A + unsafe-B #1/321: ok | ok | ok | hard-safe-A + unsafe-B #2/123: ok | ok | ok | soft-safe-A + unsafe-B #2/123: ok | ok | ok | hard-safe-A + unsafe-B #2/132: ok | ok | ok | soft-safe-A + unsafe-B #2/132: ok | ok | ok | hard-safe-A + unsafe-B #2/213: ok | ok | ok | soft-safe-A + unsafe-B #2/213: ok | ok | ok | hard-safe-A + unsafe-B #2/231: ok | ok | ok | soft-safe-A + unsafe-B #2/231: ok | ok | ok | hard-safe-A + unsafe-B #2/312: ok | ok | ok | soft-safe-A + unsafe-B #2/312: ok | ok | ok | hard-safe-A + unsafe-B #2/321: ok | ok | ok | soft-safe-A + unsafe-B #2/321: ok | ok | ok | hard-irq lock-inversion/123: ok | ok | ok | soft-irq lock-inversion/123: ok | ok | ok | hard-irq lock-inversion/132: ok | ok | ok | soft-irq lock-inversion/132: ok | ok | ok | hard-irq lock-inversion/213: ok | ok | ok | soft-irq lock-inversion/213: ok | ok | ok | hard-irq lock-inversion/231: ok | ok | ok | soft-irq lock-inversion/231: ok | ok | ok | hard-irq lock-inversion/312: ok | ok | ok | soft-irq lock-inversion/312: ok | ok | ok | hard-irq lock-inversion/321: ok | ok | ok | soft-irq lock-inversion/321: ok | ok | ok | hard-irq read-recursion/123: ok | soft-irq read-recursion/123: ok | hard-irq read-recursion/132: ok | soft-irq read-recursion/132: ok | hard-irq read-recursion/213: ok | soft-irq read-recursion/213: ok | hard-irq read-recursion/231: ok | soft-irq read-recursion/231: ok | hard-irq read-recursion/312: ok | soft-irq read-recursion/312: ok | hard-irq read-recursion/321: ok | soft-irq read-recursion/321: ok | --------------------------------+-----+---------------- Good, all 210 testcases passed! | --------------------------------+ Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-07-03[PATCH] lockdep: s390 CONFIG_FRAME_POINTER supportHeiko Carstens
CONFIG_FRAME_POINTER support for s390. Signed-off-by: Heiko Carstens <heiko.carstens@de.ibm.com> Acked-by: Ingo Molnar <mingo@elte.hu> Cc: Martin Schwidefsky <schwidefsky@de.ibm.com> Cc: Arjan van de Ven <arjan@infradead.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-07-03[PATCH] lockdep: stacktrace subsystem, coreIngo Molnar
Framework to generate and save stacktraces quickly, without printing anything to the console. Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-07-03[PATCH] lockdep: better lock debuggingIngo Molnar
Generic lock debugging: - generalized lock debugging framework. For example, a bug in one lock subsystem turns off debugging in all lock subsystems. - got rid of the caller address passing (__IP__/__IP_DECL__/etc.) from the mutex/rtmutex debugging code: it caused way too much prototype hackery, and lockdep will give the same information anyway. - ability to do silent tests - check lock freeing in vfree too. - more finegrained debugging options, to allow distributions to turn off more expensive debugging features. There's no separate 'held mutexes' list anymore - but there's a 'held locks' stack within lockdep, which unifies deadlock detection across all lock classes. (this is independent of the lockdep validation stuff - lockdep first checks whether we are holding a lock already) Here are the current debugging options: CONFIG_DEBUG_MUTEXES=y CONFIG_DEBUG_LOCK_ALLOC=y which do: config DEBUG_MUTEXES bool "Mutex debugging, basic checks" config DEBUG_LOCK_ALLOC bool "Detect incorrect freeing of live mutexes" Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-07-03[PATCH] lockdep: remove mutex deadlock checking codeIngo Molnar
With the lock validator we detect mutex deadlocks (and more), the mutex deadlock checking code is both redundant and slower. So remove it. Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-07-03[PATCH] lockdep: clean up rwsemsIngo Molnar
Clean up rwsems. Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-30Merge git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivialLinus Torvalds
* git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivial: Remove obsolete #include <linux/config.h> remove obsolete swsusp_encrypt arch/arm26/Kconfig typos Documentation/IPMI typos Kconfig: Typos in net/sched/Kconfig v9fs: do not include linux/version.h Documentation/DocBook/mtdnand.tmpl: typo fixes typo fixes: specfic -> specific typo fixes in Documentation/networking/pktgen.txt typo fixes: occuring -> occurring typo fixes: infomation -> information typo fixes: disadvantadge -> disadvantage typo fixes: aquire -> acquire typo fixes: mecanism -> mechanism typo fixes: bandwith -> bandwidth fix a typo in the RTC_CLASS help text smb is no longer maintained Manually merged trivial conflict in arch/um/kernel/vmlinux.lds.S
2006-06-30Remove obsolete #include <linux/config.h>Jörn Engel
Signed-off-by: Jörn Engel <joern@wohnheim.fh-wedel.de> Signed-off-by: Adrian Bunk <bunk@stusta.de>
2006-06-29merge linus into release branchLen Brown
Conflicts: drivers/acpi/acpi_memhotplug.c
2006-06-28Fix vsnprintf off-by-one bugLinus Torvalds
The recent vsnprintf() fix introduced an off-by-one, and it's now possible to overrun the target buffer by one byte. The "end" pointer points to past the end of the buffer, so if we have to truncate the result, it needs to be done though "end[-1]". [ This is just an alternate and simpler patch to one proposed by Andrew and Jeremy, who actually noticed the problem ] Acked-by: Andrew Morton <akpm@osdl.org> Acked-by: Jeremy Fitzhardinge <jeremy@goop.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-28[PATCH] Add EXPORT_UNUSED_SYMBOL and EXPORT_UNUSED_SYMBOL_GPLArjan van de Ven
Temporarily add EXPORT_UNUSED_SYMBOL and EXPORT_UNUSED_SYMBOL_GPL. These will be used as a transition measure for symbols that aren't used in the kernel and are on the way out. When a module uses such a symbol, a warning is printk'd at modprobe time. The main reason for removing unused exports is size: eacho export takes roughly between 100 and 150 bytes of kernel space in the binary. This patch gives users the option to immediately get this size gain via a config option. Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-27[PATCH] fix rt-mutex defaults and dependenciesRoman Zippel
Fix defaults and dependencies. Signed-off-by: Roman Zippel <zippel@linux-m68k.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Ingo Molnar <mingo@elte.hu> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-27[PATCH] pi-futex: rt mutex testerThomas Gleixner
RT-mutex tester: scriptable tester for rt mutexes, which allows userspace scripting of mutex unit-tests (and dynamic tests as well), using the actual rt-mutex implementation of the kernel. [akpm@osdl.org: fixlet] Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-27[PATCH] pi-futex: rt mutex debugIngo Molnar
Runtime debugging functionality for rt-mutexes. Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-27[PATCH] pi-futex: add plist implementationIngo Molnar
Add the priority-sorted list (plist) implementation. Signed-off-by: Ingo Molnar <mingo@elte.hu> Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Arjan van de Ven <arjan@linux.intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-27[PATCH] zlib inflate: fix function definitionsRandy Dunlap
Fix function definitions to be ANSI-compliant: lib/zlib_inflate/inffast.c:68:1: warning: non-ANSI definition of function 'inflate_fast' lib/zlib_inflate/inftrees.c:33:1: warning: non-ANSI definition of function 'zlib_inflate_table' Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-27KEVENT: add new uevent for dockKristen Accardi
so that userspace can be notified of dock and undock events. Signed-off-by: Kristen Carlson Accardi <kristen.c.accardi@intel.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Len Brown <len.brown@intel.com>
2006-06-26Merge git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivialLinus Torvalds
* git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivial: typo fixes Clean up 'inline is not at beginning' warnings for usb storage Storage class should be first i386: Trivial typo fixes ixj: make ixj_set_tone_off() static spelling fixes fix paniced->panicked typos Spelling fixes for Documentation/atomic_ops.txt move acknowledgment for Mark Adler to CREDITS remove the bouncing email address of David Campbell
2006-06-26Merge branch 'x86-64'Linus Torvalds
* x86-64: (83 commits) [PATCH] x86_64: x86_64 stack usage debugging [PATCH] x86_64: (resend) x86_64 stack overflow debugging [PATCH] x86_64: msi_apic.c build fix [PATCH] x86_64: i386/x86-64 Add nmi watchdog support for new Intel CPUs [PATCH] x86_64: Avoid broadcasting NMI IPIs [PATCH] x86_64: fix apic error on bootup [PATCH] x86_64: enlarge window for stack growth [PATCH] x86_64: Minor string functions optimizations [PATCH] x86_64: Move export symbols to their C functions [PATCH] x86_64: Standardize i386/x86_64 handling of NMI_VECTOR [PATCH] x86_64: Fix modular pc speaker [PATCH] x86_64: remove sys32_ni_syscall() [PATCH] x86_64: Do not use -ffunction-sections for modules [PATCH] x86_64: Add cpu_relax to apic_wait_icr_idle [PATCH] x86_64: adjust kstack_depth_to_print default [PATCH] i386/x86-64: adjust /proc/interrupts column headings [PATCH] x86_64: Fix race in cpu_local_* on preemptible kernels [PATCH] x86_64: Fix fast check in safe_smp_processor_id [PATCH] x86_64: x86_64 setup.c - printing cmp related boottime information [PATCH] i386/x86-64/ia64: Move polling flag into thread_info_status ... Manual resolve of trivial conflict in arch/i386/kernel/Makefile
2006-06-26[PATCH] i386: reliable stack trace support (i386)Jan Beulich
These are the i386-specific pieces to enable reliable stack traces. This is going to be even more useful once CFI annotations get added to he assembly code, namely to entry.S. Signed-off-by: Jan Beulich <jbeulich@novell.com> Signed-off-by: Andi Kleen <ak@suse.de> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-26[PATCH] x86_64: reliable stack trace support (x86-64)Jan Beulich
These are the x86_64-specific pieces to enable reliable stack traces. The only restriction with this is that it currently cannot unwind across the interrupt->normal stack boundary, as that transition is lacking proper annotation. Signed-off-by: Jan Beulich <jbeulich@novell.com> Signed-off-by: Andi Kleen <ak@suse.de> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-26[PATCH] x86_64: reliable stack trace supportJan Beulich
These are the generic bits needed to enable reliable stack traces based on Dwarf2-like (.eh_frame) unwind information. Subsequent patches will enable x86-64 and i386 to make use of this. Thanks to Andi Kleen and Ingo Molnar, who pointed out several possibilities for improvement. Signed-off-by: Jan Beulich <jbeulich@novell.com> Signed-off-by: Andi Kleen <ak@suse.de> 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-26spelling fixesAndreas Mohr
acquired (aquired) contiguous (contigious) successful (succesful, succesfull) surprise (suprise) whether (weather) some other misspellings Signed-off-by: Andreas Mohr <andi@lisas.de> Signed-off-by: Adrian Bunk <bunk@stusta.de>
2006-06-26move acknowledgment for Mark Adler to CREDITSAdrian Bunk
The place in the documentation of the Linux kernel to acknowledge contributions is the CREDITS file. Give Mark Adler an entry there instead of including a string in the kernel image. Signed-off-by: Adrian Bunk <bunk@stusta.de>
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
2006-06-25[PATCH] Implement kasprintfJeremy Fitzhardinge
Implement kasprintf, a kernel version of asprintf. This allocates the memory required for the formatted string, including the trailing '\0'. Returns NULL on allocation failure. Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com> Signed-off-by: Chris Wright <chrisw@sous-sol.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] Fix bounds check in vsnprintf, to allow for a 0 size and NULL bufferJeremy Fitzhardinge
This change allows callers to use a 0-byte buffer and a NULL buffer pointer with vsnprintf, so it can be used to determine how large the resulting formatted string will be. Previously the code effectively treated a size of 0 as a size of 4G (on 32-bit systems), with other checks preventing it from actually trying to emit the string - but the terminal \0 would still be written, which would crash if the buffer is NULL. This change changes the boundary check so that 'end' points to the putative location of the terminal '\0', which is only written if size > 0. vsnprintf still allows the buffer size to be set very large, to allow unbounded buffer sizes (to implement sprintf, etc). [akpm@osdl.org: fix long-vs-longlong confusion] Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com> Signed-off-by: Chris Wright <chrisw@sous-sol.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] reed-solomon: fix kernel-doc commentsRandy Dunlap
Fix kernel-doc formatting in Reed-Solomon code. Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] kernel-doc for lib/crc*.cRandy Dunlap
Make kernel-doc corrections & additions to lib/crc*.c. Add crc functions to kernel-api.tmpl in DocBook. Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] kernel-doc for lib/bitmap.cRandy Dunlap
Make corrections/fixes to kernel-doc in lib/bitmap.c and include it in DocBook template. Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] radixtree: normalize radix_tree_tag_get() return valueWu Fengguang
In radix_tree_tag_get(), return normalized value of 0/1, as indicated by its comment. Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] constify libcrc32c tableAndreas Mohr
constify a medium-large CRC code table. Signed-off-by: Andreas Mohr <andi@lisas.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] strstrip() APIPekka Enberg
Add a new strstrip() function to lib/string.c for removing leading and trailing whitespace from a string. Cc: Michael Holzheu <holzheu@de.ibm.com> Acked-by: Ingo Oeser <ioe-lkml@rameria.de> Acked-by: Joern Engel <joern@wohnheim.fh-wedel.de> Cc: Corey Minyard <minyard@acm.org> Signed-off-by: Pekka Enberg <penberg@cs.helsinki.fi> Acked-by: Michael Holzheu <HOLZHEU@de.ibm.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] percpu counter data type changes to suppport more than 2**31 ext3 ↵Mingming Cao
free blocks counter The percpu counter data type are changed in this set of patches to support more users like ext3 who need more than 32 bit to store the free blocks total in the filesystem. - Generic perpcu counters data type changes. The size of the global counter and local counter were explictly specified using s64 and s32. The global counter is changed from long to s64, while the local counter is changed from long to s32, so we could avoid doing 64 bit update in most cases. - Users of the percpu counters are updated to make use of the new percpu_counter_init() routine now taking an additional parameter to allow users to pass the initial value of the global counter. Signed-off-by: Mingming Cao <cmm@us.ibm.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] percpu_counters: create lib/percpu_counter.cRavikiran G Thirumalai
- Move percpu_counter routines from mm/swap.c to lib/percpu_counter.c Signed-off-by: Ravikiran Thirumalai <kiran@scalex86.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] buglet in radix_tree_tag_setPeter Zijlstra
The comment states: 'Setting a tag on a not-present item is a BUG.' Hence if 'index' is larger than the maxindex; the item _cannot_ be presen; it should also be a BUG. Also, this allows the following statement (assume a fresh tree): radix_tree_tag_set(root, 16, 1); to fail silently, but when preceded by: radix_tree_insert(root, 32, item); it would BUG, because the height has been extended by the insert. In neither case was 16 present. Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Acked-by: Nick Piggin <npiggin@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] radix-tree: smallNick Piggin
Reduce radix tree node memory usage by about a factor of 4 for small files (< 64K). There are pointer traversal and memory usage costs for large files with dense pagecache. Signed-off-by: Nick Piggin <npiggin@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] radix-tree: direct dataNick Piggin
The ability to have height 0 radix trees (a direct pointer to the data item rather than going through a full node->slot) quietly disappeared with old-2.6-bkcvs commit ffee171812d51652f9ba284302d9e5c5cc14bdfd. On 64-bit machines this causes nearly 600 bytes to be used for every <= 4K file in pagecache. Re-introduce this feature, root tags stored in spare ->gfp_mask bits. Simplify radix_tree_delete's complex tag clearing arrangement (which would become even more complex) by just falling back to tag clearing functions (the pagecache radix-tree never uses this path anyway, so the icache savings will mean it's actually a speedup). On my 4GB G5, this saves 8MB RAM per kernel kernel source+object tree in pagecache. Pagecache lookup, insertion, and removal speed for small files will also be improved. This makes RCU radix tree harder, but it's worth it. Signed-off-by: Nick Piggin <npiggin@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-23[PATCH] change gen_pool allocator to not touch managed memoryDean Nelson
Modify the gen_pool allocator (lib/genalloc.c) to utilize a bitmap scheme instead of the buddy scheme. The purpose of this change is to eliminate the touching of the actual memory being allocated. Since the change modifies the interface, a change to the uncached allocator (arch/ia64/kernel/uncached.c) is also required. Both Andrey Volkov and Jes Sorenson have expressed a desire that the gen_pool allocator not write to the memory being managed. See the following: http://marc.theaimsgroup.com/?l=linux-kernel&m=113518602713125&w=2 http://marc.theaimsgroup.com/?l=linux-kernel&m=113533568827916&w=2 Signed-off-by: Dean Nelson <dcn@sgi.com> Cc: Andrey Volkov <avolkov@varma-el.com> Acked-by: Jes Sorensen <jes@trained-monkey.org> Cc: "Luck, Tony" <tony.luck@intel.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-22[PATCH] zlib_inflate: Upgrade library code to a recent versionRichard Purdie
Upgrade the zlib_inflate implementation in the kernel from a patched version 1.1.3/4 to a patched 1.2.3. The code in the kernel is about seven years old and I noticed that the external zlib library's inflate performance was significantly faster (~50%) than the code in the kernel on ARM (and faster again on x86_32). For comparison the newer deflate code is 20% slower on ARM and 50% slower on x86_32 but gives an approx 1% compression ratio improvement. I don't consider this to be an improvement for kernel use so have no plans to change the zlib_deflate code. Various changes have been made to the zlib code in the kernel, the most significant being the extra functions/flush option used by ppp_deflate. This update reimplements the features PPP needs to ensure it continues to work. This code has been tested on ARM under both JFFS2 (with zlib compression enabled) and ppp_deflate and on x86_32. JFFS2 sees an approx. 10% real world file read speed improvement. This patch also removes ZLIB_VERSION as it no longer has a correct value. We don't need version checks anyway as the kernel's module handling will take care of that for us. This removal is also more in keeping with the zlib author's wishes (http://www.zlib.net/zlib_faq.html#faq24) and I've added something to the zlib.h header to note its a modified version. Signed-off-by: Richard Purdie <rpurdie@rpsys.net> Acked-by: Joern Engel <joern@wh.fh-wedel.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-21[PATCH] kobject: make people pay attention to kobject_add errorsGreg Kroah-Hartman
These really need to be fixed, shout it out to the world. Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2006-06-20[PATCH] add __iowrite64_copyBrice Goglin
Introduce __iowrite64_copy. It will be used by the Myri-10G Ethernet driver to post requests to the NIC. This driver will be submitted soon. __iowrite64_copy copies to I/O memory in units of 64 bits when possible (on 64 bit architectures). It reverts to __iowrite32_copy on 32 bit architectures. Signed-off-by: Brice Goglin <brice@myri.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-20Merge git://git.infradead.org/~dwmw2/rbtree-2.6Linus Torvalds
* git://git.infradead.org/~dwmw2/rbtree-2.6: [RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistency Update UML kernel/physmem.c to use rb_parent() accessor macro [RBTREE] Update hrtimers to use rb_parent() accessor macro. [RBTREE] Add explicit alignment to sizeof(long) for struct rb_node. [RBTREE] Merge colour and parent fields of struct rb_node. [RBTREE] Remove dead code in rb_erase() [RBTREE] Update JFFS2 to use rb_parent() accessor macro. [RBTREE] Update eventpoll.c to use rb_parent() accessor macro. [RBTREE] Update key.c to use rb_parent() accessor macro. [RBTREE] Update ext3 to use rb_parent() accessor macro. [RBTREE] Change rbtree off-tree marking in I/O schedulers. [RBTREE] Add accessor macros for colour and parent fields of rb_node
2006-06-05[RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistencyDavid Woodhouse
Since rb_insert_color() is part of the _public_ API, while the others are purely internal, switch to be consistent with that. Signed-off-by: David Woodhouse <dwmw2@infradead.org>
2006-05-21[PATCH] kobject: quiet errors in kobject_addGreg Kroah-Hartman
People don't like released kernels yelling at them, no matter how real the error might be. So only report it if CONFIG_KOBJECT_DEBUG is enabled. Sent on request of Andrew Morton. (akpm: should bring this back post-2.6.17) Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-05-12[SPARC]: Handle UNWIND_INFO properly.David S. Miller
For sparc32 we need R_SPARC_UA32 relocation support, for sparc64 we need the handle R_SPARC_DISP32 relocations. Based upon reports and initial patch by Martin Habets. Signed-off-by: David S. Miller <davem@davemloft.net>
2006-04-27[PATCH] Kobject: possible cleanupsAdrian Bunk
This patch contains the following possible cleanups: - #if 0 the following unused global function: - subsys_remove_file() - remove the following unused EXPORT_SYMBOL's: - kset_find_obj - subsystem_init - remove the following unused EXPORT_SYMBOL_GPL: - kobject_add_dir Signed-off-by: Adrian Bunk <bunk@stusta.de> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2006-04-27[PATCH] Kobject: fix build errorKay Sievers
This fixes a build error for various odd combinations of CONFIG_HOTPLUG and CONFIG_NET. Signed-off-by: Kay Sievers <kay.sievers@vrfy.org> Cc: Nigel Cunningham <ncunningham@cyclades.com> Cc: Andrew Morton <akpm@osdl.org> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2006-04-21[RBTREE] Merge colour and parent fields of struct rb_node.David Woodhouse
We only used a single bit for colour information, so having a whole machine word of space allocated for it was a bit wasteful. Instead, store it in the lowest bit of the 'parent' pointer, since that was always going to be aligned anyway. Signed-off-by: David Woodhouse <dwmw2@infradead.org>