- 16 5月, 2010 1 次提交
-
-
由 kirjanov@gmail.com 提交于
mempool_alloc() can return null in atomic case. Signed-off-by: NDenis Kirjanov <kirjanov@gmail.com> Cc: Joern Engel <joern@logfs.org> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 13 5月, 2010 1 次提交
-
-
由 Michel Lespinasse 提交于
If there are no active threasd using a semaphore, it is always correct to unqueue blocked threads. This seems to be what was intended in the undo code. What was done instead, was to look for a sem count of zero - this is an impossible situation, given that at least one thread is known to be queued on the semaphore. The code might be correct as written, but it's hard to reason about and it's not what was intended (otherwise the goto out would have been unconditional). Go for checking the active count - the alternative is not worth the headache. Signed-off-by: NMichel Lespinasse <walken@google.com> Signed-off-by: NDavid Howells <dhowells@redhat.com> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 11 5月, 2010 3 次提交
-
-
由 Mathieu Desnoyers 提交于
Implement a basic state machine checker in the debugobjects. This state machine checker detects races and inconsistencies within the "active" life of a debugobject. The checker only keeps track of the current state; all the state machine logic is kept at the object instance level. The checker works by adding a supplementary "unsigned int astate" field to the debug_obj structure. It keeps track of the current "active state" of the object. The only constraints that are imposed on the states by the debugobjects system is that: - activation of an object sets the current active state to 0, - deactivation of an object expects the current active state to be 0. For the rest of the states, the state mapping is determined by the specific object instance. Therefore, the logic keeping track of the state machine is within the specialized instance, without any need to know about it at the debugobject level. The current object active state is changed by calling: debug_object_active_state(addr, descr, expect, next) where "expect" is the expected state and "next" is the next state to move to if the expected state is found. A warning is generated if the expected is not found. Signed-off-by: NMathieu Desnoyers <mathieu.desnoyers@efficios.com> Reviewed-by: NThomas Gleixner <tglx@linutronix.de> Acked-by: NDavid S. Miller <davem@davemloft.net> CC: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> CC: akpm@linux-foundation.org CC: mingo@elte.hu CC: laijs@cn.fujitsu.com CC: dipankar@in.ibm.com 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 CC: eric.dumazet@gmail.com CC: Alexey Dobriyan <adobriyan@gmail.com> Signed-off-by: NPaul E. McKenney <paulmck@linux.vnet.ibm.com>
-
由 Paul E. McKenney 提交于
The CPU_STALL_VERBOSE kernel configuration parameter was added to 2.6.34 to identify any preempted/blocked tasks that were preventing the current grace period from completing when running preemptible RCU. As is conventional for new configurations parameters, this defaulted disabled. It is now time to enable it by default. Signed-off-by: NPaul E. McKenney <paulmck@linux.vnet.ibm.com>
-
由 Lai Jiangshan 提交于
There is no need to disable lockdep after an RCU lockdep splat, so remove the debug_lockdeps_off() from lockdep_rcu_dereference(). To avoid repeated lockdep splats, use a static variable in the inlined rcu_dereference_check() and rcu_dereference_protected() macros so that a given instance splats only once, but so that multiple instances can be detected per boot. This is controlled by a new config variable CONFIG_PROVE_RCU_REPEATEDLY, which is disabled by default. This provides the normal lockdep behavior by default, but permits people who want to find multiple RCU-lockdep splats per boot to easily do so. Requested-by: NEric Paris <eparis@redhat.com> Signed-off-by: NLai Jiangshan <laijs@cn.fujitsu.com> Tested-by: NEric Paris <eparis@redhat.com> Signed-off-by: NPaul E. McKenney <paulmck@linux.vnet.ibm.com>
-
- 25 4月, 2010 3 次提交
-
-
由 Hans Verkuil 提交于
Add a missing EXPORT_SYMBOL. I must be the first person that wants to use this function :-) Signed-off-by: NHans Verkuil <hverkuil@xs4all.nl> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Albin Tonnerre 提交于
This patch fixes 2 issues with the LZO decompressor: - It doesn't handle the case where a block isn't compressed at all. In this case, calling lzo1x_decompress_safe will fail, so we need to just use memcpy() instead (the upstream LZO code does something similar) - Since commit 54291362 ("initramfs: add missing decompressor error check") , the decompressor return code is checked in the init/initramfs.c The LZO decompressor didn't return the expected value, causing the initramfs code to falsely believe a decompression error occured Signed-off-by: NAlbin Tonnerre <albin.tonnerre@free-electrons.com> Tested-by: Nbert schulze <spambemyguest@googlemail.com> Cc: "H. Peter Anvin" <hpa@zytor.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Changli Gao 提交于
memset() is called with the wrong address and the kernel panics. Signed-off-by: NChangli Gao <xiaosuo@gmail.com> Cc: Patrick McHardy <kaber@trash.net> Acked-by: NDavid Rientjes <rientjes@google.com> Cc: <stable@kernel.org> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 15 4月, 2010 1 次提交
-
-
由 Joe Perches 提交于
Commit ef0658f3 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: NEric Paris <eparis@redhat.com> Signed-off-by: NJoe Perches <joe@perches.com> Tested-by: NJustin P. Mattock <justinmattock@gmail.com> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 13 4月, 2010 1 次提交
-
-
由 David S. Miller 提交于
Only missing thing was an _sdata marker in vmlinux.lds.S Signed-off-by: NDavid S. Miller <davem@davemloft.net>
-
- 10 4月, 2010 1 次提交
-
-
由 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: NRomain DEGEZ <romain.degez@smartjog.com> Signed-off-by: NDavid Howells <dhowells@redhat.com> Acked-by: NNick Piggin <npiggin@suse.de> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 08 4月, 2010 1 次提交
-
-
由 Kevin 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: NKevin Hilman <khilman@deeprootsystems.com> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 07 4月, 2010 6 次提交
-
-
由 Yong Zhang 提交于
The log of commit edaac8e3 ("ratelimit: Fix/allow use in atomic contexts"), indicates that we want to suppress the callback when the trylock fails. Signed-off-by: NYong Zhang <yong.zhang@windriver.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: Christian Borntraeger <borntraeger@de.ibm.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Yong Zhang 提交于
To prevent from wrongly using the return value. [akpm@linux-foundation.org: fix spello] Signed-off-by: NYong Zhang <yong.zhang@windriver.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: Dave Young <hidave.darkstar@gmail.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 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: NDan Carpenter <error27@gmail.com> Signed-off-by: NJoerg Roedel <joerg.roedel@amd.com>
-
由 Michal Simek 提交于
Enable DEBUG_KMEMLEAK for microblaze Signed-off-by: NMichal Simek <monstr@monstr.eu>
-
由 Borislav Petkov 提交于
Add support for the hardware version of the Hamming weight function, popcnt, present in CPUs which advertize it under CPUID, Function 0x0000_0001_ECX[23]. On CPUs which don't support it, we fallback to the default lib/hweight.c sw versions. A synthetic benchmark comparing popcnt with __sw_hweight64 showed almost a 3x speedup on a F10h machine. Signed-off-by: NBorislav Petkov <borislav.petkov@amd.com> LKML-Reference: <20100318112015.GC11152@aftab> Signed-off-by: NH. Peter Anvin <hpa@zytor.com>
-
由 Peter Zijlstra 提交于
Rename the extisting runtime hweight() implementations to __arch_hweight(), rename the compile-time versions to __const_hweight() and then have hweight() pick between them. Suggested-by: NH. Peter Anvin <hpa@zytor.com> Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl> LKML-Reference: <20100318111929.GB11152@aftab> Acked-by: NH. Peter Anvin <hpa@zytor.com> LKML-Reference: <1265028224.24455.154.camel@laptop> Signed-off-by: NH. Peter Anvin <hpa@zytor.com>
-
- 30 3月, 2010 1 次提交
-
-
由 Tejun Heo 提交于
include cleanup: Update gfp.h and slab.h includes to prepare for breaking 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: NTejun Heo <tj@kernel.org> Guess-its-ok-by: NChristoph Lameter <cl@linux-foundation.org> Cc: Ingo Molnar <mingo@redhat.com> Cc: Lee Schermerhorn <Lee.Schermerhorn@hp.com>
-
- 27 3月, 2010 1 次提交
-
-
由 Henrik Kretzschmar 提交于
This patch marks two functions, which only get called at initialization, as __init. Here is also interesting, that modpost doesn't catch here the right function name. WARNING: lib/built-in.o(.text+0x585f): Section mismatch in reference from the function T.506() to the variable .init.data:obj The function T.506() references the variable __initdata obj. This is often because T.506 lacks a __initdata annotation or the annotation of obj is wrong. Signed-off-by: NHenrik Kretzschmar <henne@nachtwindheim.de> LKML-Reference: <1269632315-19403-1-git-send-email-henne@nachtwindheim.de> Signed-off-by: NThomas Gleixner <tglx@linutronix.de>
-
- 25 3月, 2010 1 次提交
-
-
由 Mike Frysinger 提交于
We see only one section mismatch now after thousands of randconfigs, and a bug has been filed about that one. Signed-off-by: NMike Frysinger <vapier@gentoo.org> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 15 3月, 2010 3 次提交
-
-
由 Martin 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: NMartin K. Petersen <martin.petersen@oracle.com> Signed-off-by: NJens Axboe <jens.axboe@oracle.com>
-
由 Bjorn 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: NBjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: NLen Brown <len.brown@intel.com>
-
由 Bjorn Helgaas 提交于
Add support for bus number resources. This is for bridges with a range of bus numbers behind them. Signed-off-by: NBjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: NLen Brown <len.brown@intel.com>
-
- 13 3月, 2010 2 次提交
-
-
由 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: NJoakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Joakim Tjernlund 提交于
Commit 6846ee5c ("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: NJoakim 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: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 08 3月, 2010 3 次提交
-
-
由 Emese 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: NEmese Revfy <re.emese@gmail.com> Acked-by: NDavid Teigland <teigland@redhat.com> Acked-by: NMatt Domsch <Matt_Domsch@dell.com> Acked-by: NMaciej Sosnowski <maciej.sosnowski@intel.com> Acked-by: NHans J. Koch <hjk@linutronix.de> Acked-by: NPekka Enberg <penberg@cs.helsinki.fi> Acked-by: NJens Axboe <jens.axboe@oracle.com> Acked-by: NStephen Hemminger <shemminger@vyatta.com> Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>
-
由 Emese 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: NEmese Revfy <re.emese@gmail.com> Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>
-
由 Linus Torvalds 提交于
This reverts commit a069c266. 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: NAlexey 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: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 07 3月, 2010 11 次提交
-
-
由 Bjorn 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: NBjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Bjorn Helgaas 提交于
Add clues about what the SMALL and SPECIAL flags do. Signed-off-by: NBjorn Helgaas <bjorn.helgaas@hp.com> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Joe 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: NJoe Perches <joe@perches.com> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Joakim Tjernlund 提交于
Signed-off-by: NJoakim Tjernlund <Joakim.Tjernlund@transmode.se> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Akinobu Mita 提交于
Replace open-coded loop with for_each_set_bit(). Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Ben Hutchings 提交于
The function name must be followed by a space, hypen, space, and a short description. Signed-off-by: NBen Hutchings <ben@decadent.org.uk> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Don Mullis 提交于
Build list_sort() only for configs that need it -- those that don't save ~581 bytes (i386). Signed-off-by: NDon 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: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Don Mullis 提交于
Clarify and correct header comment of list_sort(). Signed-off-by: NDon 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: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 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: NDon 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: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 André Goddard Rosa 提交于
Signed-off-by: NAndré 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: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 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: NAndré Goddard Rosa <andre.goddard@gmail.com> Cc: Joe Perches <joe@perches.com> Cc: Frederic Weisbecker <fweisbec@gmail.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-