summaryrefslogtreecommitdiff
path: root/lib
AgeCommit message (Collapse)Author
2010-04-15Merge branch 'x86-fixes-for-linus' of ↵Linus Torvalds
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip * 'x86-fixes-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip: x86/gart: Disable GART explicitly before initialization dma-debug: Cleanup for copy-loop in filter_write() x86/amd-iommu: Remove obsolete parameter documentation x86/amd-iommu: use for_each_pci_dev Revert "x86: disable IOMMUs on kernel crash" x86/amd-iommu: warn when issuing command to uninitialized cmd buffer x86/amd-iommu: enable iommu before attaching devices x86/amd-iommu: Use helper function to destroy domain x86/amd-iommu: Report errors in acpi parsing functions upstream x86/amd-iommu: Pt mode fix for domain_destroy x86/amd-iommu: Protect IOMMU-API map/unmap path x86/amd-iommu: Remove double NULL check in check_device
2010-04-14vsprintf: Change struct printf_spec.precision from s8 to s16Joe Perches
Commit ef0658f3de484bf9b173639cd47544584e01efa5 changed precision from int to s8. There is existing kernel code that uses a larger precision. An example from the audit code: vsnprintf(...,..., " msg='%.1024s'", (char *)data); which overflows precision and truncates to nothing. Extending precision size fixes the audit system issue. Other changes: Change the size of the struct printf_spec.type from u16 to u8 so sizeof(struct printf_spec) stays as small as possible. Reorder the struct members so sizeof(struct printf_spec) remains 64 bits without alignment holes. Document the struct members a bit more. Original-patch-by: Eric Paris <eparis@redhat.com> Signed-off-by: Joe Perches <joe@perches.com> Tested-by: Justin P. Mattock <justinmattock@gmail.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-04-13Merge branch 'iommu/fixes' of ↵Ingo Molnar
git://git.kernel.org/pub/scm/linux/kernel/git/joro/linux-2.6-iommu into x86/urgent
2010-04-13Merge branch 'master' of /home/davem/src/GIT/linux-2.6/David S. Miller
Conflicts: lib/Kconfig.debug
2010-04-12sparc64: Support kmemleak.David S. Miller
Only missing thing was an _sdata marker in vmlinux.lds.S Signed-off-by: David S. Miller <davem@davemloft.net>
2010-04-09Merge branch 'for-linus' of git://git.kernel.dk/linux-2.6-blockLinus Torvalds
* 'for-linus' of git://git.kernel.dk/linux-2.6-block: (34 commits) cfq-iosched: Fix the incorrect timeslice accounting with forced_dispatch loop: Update mtime when writing using aops block: expose the statistics in blkio.time and blkio.sectors for the root cgroup backing-dev: Handle class_create() failure Block: Fix block/elevator.c elevator_get() off-by-one error drbd: lc_element_by_index() never returns NULL cciss: unlock on error path cfq-iosched: Do not merge queues of BE and IDLE classes cfq-iosched: Add additional blktrace log messages in CFQ for easier debugging i2o: Remove the dangerous kobj_to_i2o_device macro block: remove 16 bytes of padding from struct request on 64bits cfq-iosched: fix a kbuild regression block: make CONFIG_BLK_CGROUP visible Remove GENHD_FL_DRIVERFS block: Export max number of segments and max segment size in sysfs block: Finalize conversion of block limits functions block: Fix overrun in lcm() and move it to lib vfs: improve writeback_inodes_wb() paride: fix off-by-one test drbd: fix al-to-on-disk-bitmap for 4k logical_block_size ...
2010-04-09radix_tree_tag_get() is not as safe as the docs make out [ver #2]David Howells
radix_tree_tag_get() is not safe to use concurrently with radix_tree_tag_set() or radix_tree_tag_clear(). The problem is that the double tag_get() in radix_tree_tag_get(): if (!tag_get(node, tag, offset)) saw_unset_tag = 1; if (height == 1) { int ret = tag_get(node, tag, offset); may see the value change due to the action of set/clear. RCU is no protection against this as no pointers are being changed, no nodes are being replaced according to a COW protocol - set/clear alter the node directly. The documentation in linux/radix-tree.h, however, says that radix_tree_tag_get() is an exception to the rule that "any function modifying the tree or tags (...) must exclude other modifications, and exclude any functions reading the tree". The problem is that the next statement in radix_tree_tag_get() checks that the tag doesn't vary over time: BUG_ON(ret && saw_unset_tag); This has been seen happening in FS-Cache: https://www.redhat.com/archives/linux-cachefs/2010-April/msg00013.html To this end, remove the BUG_ON() from radix_tree_tag_get() and note in various comments that the value of the tag may change whilst the RCU read lock is held, and thus that the return value of radix_tree_tag_get() may not be relied upon unless radix_tree_tag_set/clear() and radix_tree_delete() are excluded from running concurrently with it. Reported-by: Romain DEGEZ <romain.degez@smartjog.com> Signed-off-by: David Howells <dhowells@redhat.com> Acked-by: Nick Piggin <npiggin@suse.de> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-04-07rwsem generic spinlock: use IRQ save/restore spinlocksKevin Hilman
rwsems can be used with IRQs disabled, particularily in early boot before IRQs are enabled. Currently the spin_unlock_irq() usage in the slow-patch will unconditionally enable interrupts and cause problems since interrupts are not yet initialized or enabled. This patch uses save/restore versions of IRQ spinlocks in the slowpath to ensure interrupts are not unintentionally disabled. Signed-off-by: Kevin Hilman <khilman@deeprootsystems.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-04-07Merge branch 'for-linus' of git://git.monstr.eu/linux-2.6-microblazeLinus Torvalds
* 'for-linus' of git://git.monstr.eu/linux-2.6-microblaze: microblaze: Remove unused variable from ptrace microblaze: io.h: Add io big-endian function microblaze: Enable memory leak detector microblaze: Fix futex code microblaze: Fix ftrace_update_ftrace_func panic
2010-04-07ratelimit: fix the return value when __ratelimit() fails to acquire the lockYong Zhang
The log of commit edaac8e3167501cda336231d00611bf59c164346 ("ratelimit: Fix/allow use in atomic contexts"), indicates that we want to suppress the callback when the trylock fails. Signed-off-by: Yong Zhang <yong.zhang@windriver.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: Christian Borntraeger <borntraeger@de.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-04-07ratelimit: annotate ___ratelimit()Yong Zhang
To prevent from wrongly using the return value. [akpm@linux-foundation.org: fix spello] Signed-off-by: Yong Zhang <yong.zhang@windriver.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: Dave Young <hidave.darkstar@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-04-07dma-debug: Cleanup for copy-loop in filter_write()Dan Carpenter
Earlier in this function we set the last byte of "buf" to NULL so we always hit the break statement and "i" is never equal to NAME_MAX_LEN. This patch doesn't change how the driver works but it silences a Smatch warning and it makes it clearer that we don't write past the end of the array. Signed-off-by: Dan Carpenter <error27@gmail.com> Signed-off-by: Joerg Roedel <joerg.roedel@amd.com>
2010-04-07microblaze: Enable memory leak detectorMichal Simek
Enable DEBUG_KMEMLEAK for microblaze Signed-off-by: Michal Simek <monstr@monstr.eu>
2010-03-30include cleanup: Update gfp.h and slab.h includes to prepare for breaking ↵Tejun Heo
implicit slab.h inclusion from percpu.h percpu.h is included by sched.h and module.h and thus ends up being included when building most .c files. percpu.h includes slab.h which in turn includes gfp.h making everything defined by the two files universally available and complicating inclusion dependencies. percpu.h -> slab.h dependency is about to be removed. Prepare for this change by updating users of gfp and slab facilities include those headers directly instead of assuming availability. As this conversion needs to touch large number of source files, the following script is used as the basis of conversion. http://userweb.kernel.org/~tj/misc/slabh-sweep.py The script does the followings. * Scan files for gfp and slab usages and update includes such that only the necessary includes are there. ie. if only gfp is used, gfp.h, if slab is used, slab.h. * When the script inserts a new include, it looks at the include blocks and try to put the new include such that its order conforms to its surrounding. It's put in the include block which contains core kernel includes, in the same order that the rest are ordered - alphabetical, Christmas tree, rev-Xmas-tree or at the end if there doesn't seem to be any matching order. * If the script can't find a place to put a new include (mostly because the file doesn't have fitting include block), it prints out an error message indicating which .h file needs to be added to the file. The conversion was done in the following steps. 1. The initial automatic conversion of all .c files updated slightly over 4000 files, deleting around 700 includes and adding ~480 gfp.h and ~3000 slab.h inclusions. The script emitted errors for ~400 files. 2. Each error was manually checked. Some didn't need the inclusion, some needed manual addition while adding it to implementation .h or embedding .c file was more appropriate for others. This step added inclusions to around 150 files. 3. The script was run again and the output was compared to the edits from #2 to make sure no file was left behind. 4. Several build tests were done and a couple of problems were fixed. e.g. lib/decompress_*.c used malloc/free() wrappers around slab APIs requiring slab.h to be added manually. 5. The script was run on all .h files but without automatically editing them as sprinkling gfp.h and slab.h inclusions around .h files could easily lead to inclusion dependency hell. Most gfp.h inclusion directives were ignored as stuff from gfp.h was usually wildly available and often used in preprocessor macros. Each slab.h inclusion directive was examined and added manually as necessary. 6. percpu.h was updated not to include slab.h. 7. Build test were done on the following configurations and failures were fixed. CONFIG_GCOV_KERNEL was turned off for all tests (as my distributed build env didn't work with gcov compiles) and a few more options had to be turned off depending on archs to make things build (like ipr on powerpc/64 which failed due to missing writeq). * x86 and x86_64 UP and SMP allmodconfig and a custom test config. * powerpc and powerpc64 SMP allmodconfig * sparc and sparc64 SMP allmodconfig * ia64 SMP allmodconfig * s390 SMP allmodconfig * alpha SMP allmodconfig * um on x86_64 SMP allmodconfig 8. percpu.h modifications were reverted so that it could be applied as a separate patch and serve as bisection point. Given the fact that I had only a couple of failures from tests on step 6, I'm fairly confident about the coverage of this conversion patch. If there is a breakage, it's likely to be something in one of the arch headers which should be easily discoverable easily on most builds of the specific arch. Signed-off-by: Tejun Heo <tj@kernel.org> Guess-its-ok-by: Christoph Lameter <cl@linux-foundation.org> Cc: Ingo Molnar <mingo@redhat.com> Cc: Lee Schermerhorn <Lee.Schermerhorn@hp.com>
2010-03-24blackfin: enable DEBUG_SECTION_MISMATCHMike Frysinger
We see only one section mismatch now after thousands of randconfigs, and a bug has been filed about that one. Signed-off-by: Mike Frysinger <vapier@gentoo.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-19Merge branch 'master' into for-linusJens Axboe
Conflicts: block/Kconfig Signed-off-by: Jens Axboe <jens.axboe@oracle.com>
2010-03-15block: Fix overrun in lcm() and move it to libMartin K. Petersen
lcm() was defined to take integer-sized arguments. The supplied arguments are multiplied, however, causing us to overflow given sufficiently large input. That in turn led to incorrect optimal I/O size reporting in some cases (RAID over RAID). Switch lcm() over to unsigned long similar to gcd() and move the function from blk-settings.c to lib. Signed-off-by: Martin K. Petersen <martin.petersen@oracle.com> Signed-off-by: Jens Axboe <jens.axboe@oracle.com>
2010-03-14Merge branches 'battery-2.6.34', 'bugzilla-10805', 'bugzilla-14668', ↵Len Brown
'bugzilla-531916-power-state', 'ht-warn-2.6.34', 'pnp', 'processor-rename', 'sony-2.6.34', 'suse-bugzilla-531547', 'tz-check', 'video' and 'misc-2.6.34' into release
2010-03-14resource: add window supportBjorn Helgaas
Add support for resource windows. This is for bridge resources, i.e., regions where a bridge forwards transactions from the primary to the secondary side. Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: Len Brown <len.brown@intel.com>
2010-03-14resource: add bus number supportBjorn Helgaas
Add support for bus number resources. This is for bridges with a range of bus numbers behind them. Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: Len Brown <len.brown@intel.com>
2010-03-13Merge branch 'perf-fixes-for-linus' of ↵Linus Torvalds
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip * 'perf-fixes-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip: perf: Provide generic perf_sample_data initialization MAINTAINERS: Add Arnaldo as tools/perf/ co-maintainer perf trace: Don't use pager if scripting perf trace/scripting: Remove extraneous header read perf, ARM: Modify kuser rmb() call to compile for Thumb-2 x86/stacktrace: Don't dereference bad frame pointers perf archive: Don't try to collect files without a build-id perf_events, x86: Fixup fixed counter constraints perf, x86: Restrict the ANY flag perf, x86: rename macro in ARCH_PERFMON_EVENTSEL_ENABLE perf, x86: add some IBS macros to perf_event.h perf, x86: make IBS macros available in perf_event.h hw-breakpoints: Remove stub unthrottle callback x86/hw-breakpoints: Remove the name field perf: Remove pointless breakpoint union perf lock: Drop the buffers multiplexing dependency perf lock: Fix and add misc documentally things percpu: Add __percpu sparse annotations to hw_breakpoint
2010-03-12inflate_fast: sout is already a short so ptr arith was off by one.Joakim Tjernlund
inflate_fast() can do either POST INC or PRE INC on its pointers walking the memory to decompress. Default is PRE INC. The sout pointer offset was miscalculated in one case as the calculation assumed sout was a char * This breaks inflate_fast() iff configured to do POST INC. Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-12zlib: make new optimized inflate endian independentJoakim Tjernlund
Commit 6846ee5ca68d81e6baccf0d56221d7a00c1be18b ("zlib: Fix build of powerpc boot wrapper") made the new optimized inflate only available on arch's that define CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS. This patch will again enable the optimization for all arch's by defining our own endian independent version of unaligned access. As an added bonus, arch's that define CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS do a plain load instead. Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Cc: Anton Blanchard <anton@samba.org> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Kumar Gala <galak@kernel.crashing.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-09Merge commit 'v2.6.34-rc1' into perf/urgentIngo Molnar
Conflicts: tools/perf/util/probe-event.c Merge reason: Pick up -rc1 and resolve the conflict as well. Signed-off-by: Ingo Molnar <mingo@elte.hu>
2010-03-07Driver core: Constify struct sysfs_ops in struct kobj_typeEmese Revfy
Constify struct sysfs_ops. This is part of the ops structure constification effort started by Arjan van de Ven et al. Benefits of this constification: * prevents modification of data that is shared (referenced) by many other structure instances at runtime * detects/prevents accidental (but not intentional) modification attempts on archs that enforce read-only kernel data at runtime * potentially better optimized code as the compiler can assume that the const data cannot be changed * the compiler/linker move const data into .rodata and therefore exclude them from false sharing Signed-off-by: Emese Revfy <re.emese@gmail.com> Acked-by: David Teigland <teigland@redhat.com> Acked-by: Matt Domsch <Matt_Domsch@dell.com> Acked-by: Maciej Sosnowski <maciej.sosnowski@intel.com> Acked-by: Hans J. Koch <hjk@linutronix.de> Acked-by: Pekka Enberg <penberg@cs.helsinki.fi> Acked-by: Jens Axboe <jens.axboe@oracle.com> Acked-by: Stephen Hemminger <shemminger@vyatta.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2010-03-07kobject: Constify struct kset_uevent_opsEmese Revfy
Constify struct kset_uevent_ops. This is part of the ops structure constification effort started by Arjan van de Ven et al. Benefits of this constification: * prevents modification of data that is shared (referenced) by many other structure instances at runtime * detects/prevents accidental (but not intentional) modification attempts on archs that enforce read-only kernel data at runtime * potentially better optimized code as the compiler can assume that the const data cannot be changed * the compiler/linker move const data into .rodata and therefore exclude them from false sharing Signed-off-by: Emese Revfy <re.emese@gmail.com> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
2010-03-07Revert "lib: build list_sort() only if needed"Linus Torvalds
This reverts commit a069c266ae5fdfbf5b4aecf2c672413aa33b2504. It turns ou that not only was it missing a case (XFS) that needed it, but perhaps more importantly, people sometimes want to enable new modules that they hadn't had enabled before, and if such a module uses list_sort(), it can't easily be inserted any more. So rather than add a "select LIST_SORT" to the XFS case, just leave it compiled in. It's not all _that_ big, after all, and the inconvenience isn't worth it. Requested-by: Alexey Dobriyan <adobriyan@gmail.com> Cc: Christoph Hellwig <hch@infradead.org> Cc: Don Mullis <don.mullis@gmail.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Dave Chinner <david@fromorbit.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06vsprintf: move %pR resource printf_specs off the stackBjorn Helgaas
This adds separate I/O and memory specs, so we don't have to change the field width in a shared spec, which then lets us make all the specs const and static, since they never change. Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06vsprintf: clarify comments for printf_spec flagsBjorn Helgaas
Add clues about what the SMALL and SPECIAL flags do. Signed-off-by: Bjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06vsprintf.c: Reduce sizeof struct printf_spec from 24 to 8 bytesJoe Perches
Reducing the size of struct printf_spec is a good thing because multiple instances are commonly passed on stack. It's possible for type to be u8 and field_width to be s8, but this is likely small enough for now. Signed-off-by: Joe Perches <joe@perches.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06Merge git://git.kernel.org/pub/scm/linux/kernel/git/joern/logfsLinus Torvalds
* git://git.kernel.org/pub/scm/linux/kernel/git/joern/logfs: [LogFS] Change magic number [LogFS] Remove h_version field [LogFS] Check feature flags [LogFS] Only write journal if dirty [LogFS] Fix bdev erases [LogFS] Silence gcc [LogFS] Prevent 64bit divisions in hash_index [LogFS] Plug memory leak on error paths [LogFS] Add MAINTAINERS entry [LogFS] add new flash file system Fixed up trivial conflict in lib/Kconfig, and a semantic conflict in fs/logfs/inode.c introduced by write_inode() being changed to use writeback_control' by commit a9185b41a4f84971b930c519f0c63bd450c4810d ("pass writeback_control to ->write_inode")
2010-03-06crc32: some minor cleanupsJoakim Tjernlund
Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06bitmap: use for_each_set_bit()Akinobu Mita
Replace open-coded loop with for_each_set_bit(). Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lib: fix first line of kernel-doc for a few functionsBen Hutchings
The function name must be followed by a space, hypen, space, and a short description. Signed-off-by: Ben Hutchings <ben@decadent.org.uk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lib: build list_sort() only if neededDon Mullis
Build list_sort() only for configs that need it -- those that don't save ~581 bytes (i386). Signed-off-by: Don Mullis <don.mullis@gmail.com> Cc: Dave Airlie <airlied@redhat.com> Cc: Andi Kleen <andi@firstfloor.org> Cc: Dave Chinner <david@fromorbit.com> Cc: Artem Bityutskiy <dedekind@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lib: revise list_sort() header commentDon Mullis
Clarify and correct header comment of list_sort(). Signed-off-by: Don Mullis <don.mullis@gmail.com> Cc: Dave Airlie <airlied@redhat.com> Cc: Andi Kleen <andi@firstfloor.org> Cc: Dave Chinner <david@fromorbit.com> Cc: Artem Bityutskiy <dedekind@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lib: more scalable list_sort()Don Mullis
XFS and UBIFS can pass long lists to list_sort(); this alternative implementation scales better, reaching ~3x performance gain when list length exceeds the L2 cache size. Stand-alone program timings were run on a Core 2 duo L1=32KB L2=4MB, gcc-4.4, with flags extracted from an Ubuntu kernel build. Object size is 581 bytes compared to 455 for Mark J. Roberts' code. Worst case for either implementation is a list length just over a power of two, and to roughly the same degree, so here are timing results for a range of 2^N+1 lengths. List elements were 16 bytes each including malloc overhead; initial order was random. time (msec) Tatham-Roberts | generic-Mullis-v2 loop_count length | | ratio 4000000 2 206 294 1.427 2000000 3 176 227 1.289 1000000 5 199 172 0.864 500000 9 235 178 0.757 250000 17 243 182 0.748 125000 33 261 196 0.750 62500 65 277 209 0.754 31250 129 292 219 0.75 15625 257 317 235 0.741 7812 513 340 252 0.741 3906 1025 362 267 0.737 1953 2049 388 283 0.729 ~ L1 size 976 4097 556 323 0.580 488 8193 678 361 0.532 244 16385 773 395 0.510 122 32769 844 418 0.495 61 65537 917 454 0.495 30 131073 1128 543 0.481 15 262145 2355 869 0.369 ~ L2 size 7 524289 5597 1714 0.306 3 1048577 6218 2022 0.325 Mark's code does not actually implement the usual or generic mergesort, but rather a variant from Simon Tatham described here: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Simon's algorithm performs O(log N) passes over the entire input list, doing merges of sublists that double in size on each pass. The generic algorithm instead merges pairs of equal length lists as early as possible, in recursive order. For either algorithm, the elements that extend the list beyond power-of-two length are a special case, handled as nearly as possible as a "rounding-up" to a full POT. Some intuition for the locality of reference implications of merge order may be gotten by watching this animation: http://www.sorting-algorithms.com/merge-sort Simon's algorithm requires only O(1) extra space rather than the generic algorithm's O(log N), but in my non-recursive implementation the actual O(log N) data is merely a vector of ~20 pointers, which I've put on the stack. Long-running list_sort() calls: If the list passed in may be long, or the client's cmp() callback function is slow, the client's cmp() may periodically invoke cond_resched() to voluntarily yield the CPU. All inner loops of list_sort() call back to cmp(). Stability of the sort: distinct elements that compare equal emerge from the sort in the same order as with Mark's code, for simple test cases. A boot-time test is provided to verify this and other correctness requirements. A kernel that uses drm.ko appears to run normally with this change; I have no suitable hardware to similarly test the use by UBIFS. [akpm@linux-foundation.org: style tweaks, fix comment, make list_sort_test __init] Signed-off-by: Don Mullis <don.mullis@gmail.com> Cc: Dave Airlie <airlied@redhat.com> Cc: Andi Kleen <andi@firstfloor.org> Cc: Dave Chinner <david@fromorbit.com> Cc: Artem Bityutskiy <dedekind@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lib/string.c: simplify strnstr()André Goddard Rosa
Signed-off-by: André Goddard Rosa <andre.goddard@gmail.com> Cc: Li Zefan <lizf@cn.fujitsu.com> Cc: Joe Perches <joe@perches.com> Cc: Frederic Weisbecker <fweisbec@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lib/string.c: simplify stricmp()André Goddard Rosa
Removes 32 bytes on core2 with gcc 4.4.1: text data bss dec hex filename 3196 0 0 3196 c7c lib/string-BEFORE.o 3164 0 0 3164 c5c lib/string-AFTER.o Signed-off-by: André Goddard Rosa <andre.goddard@gmail.com> Cc: Joe Perches <joe@perches.com> Cc: Frederic Weisbecker <fweisbec@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06lkdtm: add debugfs access and loosen KPROBE tiesSimon Kagstrom
Add adds a debugfs interface and additional failure modes to LKDTM to provide similar functionality to the provoke-crash driver submitted here: http://lwn.net/Articles/371208/ Crashes can now be induced either through module parameters (as before) or through the debugfs interface as in provoke-crash. The patch also provides a new "direct" interface, where KPROBES are not used, i.e., the crash is invoked directly upon write to the debugfs file. When built without KPROBES configured, only this mode is available. Signed-off-by: Simon Kagstrom <simon.kagstrom@netinsight.net> Cc: M. Mohan Kumar <mohan@in.ibm.com> Cc: Americo Wang <xiyou.wangcong@gmail.com> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Ingo Molnar <mingo@elte.hu> Cc: "Eric W. Biederman" <ebiederm@xmission.com>, Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-03-06mm: use the same log level for show_mem()Amerigo Wang
Use the same log level for printk's in show_mem(), so that those messages can be shown completely when using log level 6. Signed-off-by: WANG Cong <amwang@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-02-28Merge branch 'master' of /home/davem/src/GIT/linux-2.6/David S. Miller
Conflicts: drivers/firmware/iscsi_ibft.c
2010-02-28Merge branch 'x86-asm-for-linus' of ↵Linus Torvalds
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip * 'x86-asm-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip: x86: Mark atomic irq ops raw for 32bit legacy x86: Merge show_regs() x86: Macroise x86 cache descriptors x86-32: clean up rwsem inline asm statements x86: Merge asm/atomic_{32,64}.h x86: Sync asm/atomic_32.h and asm/atomic_64.h x86: Split atomic64_t functions into seperate headers x86-64: Modify memcpy()/memset() alternatives mechanism x86-64: Modify copy_user_generic() alternatives mechanism x86: Lift restriction on the location of FIX_BTMAP_* x86, core: Optimize hweight32()
2010-02-28Merge branch 'core-rcu-for-linus' of ↵Linus Torvalds
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip * 'core-rcu-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip: (44 commits) rcu: Fix accelerated GPs for last non-dynticked CPU rcu: Make non-RCU_PROVE_LOCKING rcu_read_lock_sched_held() understand boot rcu: Fix accelerated grace periods for last non-dynticked CPU rcu: Export rcu_scheduler_active rcu: Make rcu_read_lock_sched_held() take boot time into account rcu: Make lockdep_rcu_dereference() message less alarmist sched, cgroups: Fix module export rcu: Add RCU_CPU_STALL_VERBOSE to dump detailed per-task information rcu: Fix rcutorture mod_timer argument to delay one jiffy rcu: Fix deadlock in TREE_PREEMPT_RCU CPU stall detection rcu: Convert to raw_spinlocks rcu: Stop overflowing signed integers rcu: Use canonical URL for Mathieu's dissertation rcu: Accelerate grace period if last non-dynticked CPU rcu: Fix citation of Mathieu's dissertation rcu: Documentation update for CONFIG_PROVE_RCU security: Apply lockdep-based checking to rcu_dereference() uses idr: Apply lockdep-based diagnostics to rcu_dereference() uses radix-tree: Disable RCU lockdep checking in radix tree vfs: Abstract rcu_dereference_check for files-fdtable use ...
2010-02-27Merge branch 'next' of ↵Linus Torvalds
git://git.kernel.org/pub/scm/linux/kernel/git/benh/powerpc * 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/benh/powerpc: (88 commits) powerpc: Fix lwsync feature fixup vs. modules on 64-bit powerpc: Convert pmc_owner_lock to raw_spinlock powerpc: Convert die.lock to raw_spinlock powerpc: Convert tlbivax_lock to raw_spinlock powerpc: Convert mpic locks to raw_spinlock powerpc: Convert pmac_pic_lock to raw_spinlock powerpc: Convert big_irq_lock to raw_spinlock powerpc: Convert feature_lock to raw_spinlock powerpc: Convert i8259_lock to raw_spinlock powerpc: Convert beat_htab_lock to raw_spinlock powerpc: Convert confirm_error_lock to raw_spinlock powerpc: Convert ipic_lock to raw_spinlock powerpc: Convert native_tlbie_lock to raw_spinlock powerpc: Convert beatic_irq_mask_lock to raw_spinlock powerpc: Convert nv_lock to raw_spinlock powerpc: Convert context_lock to raw_spinlock powerpc/85xx: Add NOR, LEDs and PIB support for MPC8568E-MDS boards powerpc/86xx: Enable VME driver on the GE SBC610 powerpc/86xx: Enable VME driver on the GE PPC9A powerpc/86xx: Add MSI section to GE PPC9A DTS ...
2010-02-27perf: Remove pointless breakpoint unionFrederic Weisbecker
Remove pointless union in the breakpoint field of hw_perf_event. Signed-off-by: Frederic Weisbecker <fweisbec@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Paul Mackerras <paulus@samba.org>
2010-02-27perf lock: Fix and add misc documentally thingsHitoshi Mitake
I've forgot to add 'perf lock' line to command-list.txt, so users of perf could not find perf lock when they type 'perf'. Fixing command-list.txt requires document (tools/perf/Documentation/perf-lock.txt). But perf lock is too much "under construction" to write a stable document, so this is something like pseudo document for now. And I wrote description of perf lock at help section of CONFIG_LOCK_STAT, this will navigate users of lock trace events. Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Paul Mackerras <paulus@samba.org> Cc: Arnaldo Carvalho de Melo <acme@ghostprotocols.net> LKML-Reference: <1265267295-8388-1-git-send-email-mitake@dcl.info.waseda.ac.jp> Signed-off-by: Frederic Weisbecker <fweisbec@gmail.com>
2010-02-26Merge git://git.kernel.org/pub/scm/linux/kernel/git/lethal/sh-2.6Linus Torvalds
* git://git.kernel.org/pub/scm/linux/kernel/git/lethal/sh-2.6: (187 commits) sh: remove dead LED code for migo-r and ms7724se sh: ecovec build fix for CONFIG_I2C=n sh: ecovec r-standby support sh: ms7724se r-standby support sh: SH-Mobile R-standby register save/restore clocksource: Fix up a registration/IRQ race in the sh drivers. sh: ms7724: modify scan_timing for KEYSC sh: ms7724: Add sh_sir support sh: mach-ecovec24: Add sh_sir support sh: wire up SET/GET_UNALIGN_CTL. sh: allow alignment fault mode to be configured at kernel boot. sh: sh7724: Update FSI/SPU2 clock sh: always enable sh7724 vpu_clk and set to 166MHz on Ecovec sh: add sh7724 kick callback to clk_div4_table sh: introduce struct clk_div4_table sh: clock-cpg div4 set_rate() shift fix sh: Turn on speculative return for SH7785 and SH7786 sh: Merge legacy and dynamic PMB modes. sh: Use uncached I/O helpers in PMB setup. sh: Provide uncached I/O helpers. ...
2010-02-26Merge commit 'origin/master' into nextBenjamin Herrenschmidt
Manual merge of: drivers/char/hvc_console.c drivers/char/hvc_console.h
2010-02-25rcu: Add RCU_CPU_STALL_VERBOSE to dump detailed per-task informationPaul E. McKenney
When RCU detects a grace-period stall, it currently just prints out the PID of any tasks doing the stalling. This patch adds RCU_CPU_STALL_VERBOSE, which enables the more-verbose reporting from sched_show_task(). Suggested-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> 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: <1266887105-1528-21-git-send-email-paulmck@linux.vnet.ibm.com> Signed-off-by: Ingo Molnar <mingo@elte.hu>