- 06 Mar, 2010 40 commits
-
-
Don Mullis authored
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>
-
André Goddard Rosa authored
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:
-
André Goddard Rosa authored
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:
-
Joe Perches authored
Patchwork queues show the acceptance/rejection state of submitted patches for various MAINTAINER trees. Document their existence. Signed-off-by:
Joe Perches <joe@perches.com> Signed-off-by:
-
Joe Perches authored
by commit 0234f84e Update patterns Signed-off-by:
-
Joe Perches authored
by commit 955015bbSigned-off-by:
-
Joe Perches authored
To match arch/*/kernel perf_event location changes Signed-off-by:
-
Joe Perches authored
Commit f53a2ade ("tty: esp: remove broken driver") removed it Signed-off-by:
-
Joe Perches authored
Commit c95d1e53 ("cs5535: drop the Geode-specific MFGPT/GPIO code") removed it. Signed-off-by:
-
Joe Perches authored
If MAINTAINERS section entries are misformatted, it was possible to have an infinite loop. Correct the defect by always moving the index to the end of section + 1 Also, exit check for exclude as soon as possible. Signed-off-by:
-
Stephen Hemminger authored
Picky mail systems won't accept email addresses where recipient has period in name; ie. David S. Miller <davemloft.net> will not work. Signed-off-by:
Stephen Hemminger <shemminger@vyatta.com> Acked-by:
-
Stephen Hemminger authored
perlcritic is a standard checker for Perl Best Practices. This patch fixes most of the warnings in the get_maintainer script. If kernel programmers are going to have checkpatch they should write clean scripts as well... Bareword file handle opened at line 176, column 1. See pages 202,204 of PBP. (Severity: 5) Two-argument "open" used at line 176, column 1. See page 207 of PBP. (Severity: 5) Bareword file handle opened at line 207, column 5. See pages 202,204 of PBP. (Severity: 5) Two-argument "open" used at line 207, column 5. See page 207 of PBP. (Severity: 5) Bareword file handle opened at line 246, column 6. See pages 202,204 of PBP. (Severity: 5) Two-argument "open" used at line 246, column 6. See page 207 of PBP. (Severity: 5) Bareword file handle opened at line 258, column 2. See pages 202,204 of PBP. (Severity: 5) Two-argument "open" used at line 258, column 2. See page 207 of PBP. (Severity: 5) Expression form of "eval" at line 983, column 17. See page 161 of PBP. (Severity: 5) Expression form of "eval" at line 985, column 17. See page 161 of PBP. (Severity: 5) Subroutine prototypes used at line 1186, column 1. See page 194 of PBP. (Severity: 5) Subroutine prototypes used at line 1206, column 1. See page 194 of PBP. (Severity: 5) Signed-off-by:
-
Joe Perches authored
Doesn't need or accept '-' as a trailing option to read stdin. Doesn't print usage() after bad options. Adds --usage as command line equivalent of --help Suggested-by:
Borislav Petkov <petkovbb@googlemail.com> Signed-off-by:
-
Joe Perches authored
Signed-off-by:
-
Joe Perches authored
Print the complete contents of the matched subsystems in pattern match depth order. Sample output: $ ./scripts/get_maintainer.pl --sections -f drivers/net/usb/smsc95xx.c USB SMSC95XX ETHERNET DRIVER M:Steve Glendinning <steve.glendinning@smsc.com> L:netdev@vger.kernel.org S:Supported F:drivers/net/usb/smsc95xx.* USB SUBSYSTEM M:Greg Kroah-Hartman <gregkh@suse.de> L:linux-usb@vger.kernel.org W:http://www.linux-usb.org T:quilt kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/ S:Supported F:Documentation/usb/ F:drivers/net/usb/ F:drivers/usb/ F:include/linux/usb.h F:include/linux/usb/ NETWORKING DRIVERS L:netdev@vger.kernel.org W:http://www.linuxfoundation.org/en/Net T:git git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6.git S:Odd Fixes F:drivers/net/ F:include/linux/if_* F:include/linux/*device.h THE REST M:Linus Torvalds <torvalds@linux-foundation.org> L:linux-kernel@vger.kernel.org Q:http://patchwork.kernel.org/project/LKML/list/ T:git git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git S:Buried alive in reporters F:* F:*/ Signed-off-by:
-
Joe Perches authored
Add an imperfect option to search a source file for email addresses. New option: --file-emails or --fe email addresses in files are freeform text and are nearly impossible to parse. Still, might as well try to do a somewhat acceptable job of finding them. This code should find all addresses that are in the form addr@domain.tld The code assumes that up to 3 alphabetic words along with dashes, commas, and periods that preceed the email address are a name. If 3 words are found for the name, and one of the first two words are a single letter and period, or just a single letter then the 3 words are use as name otherwise the last 2 words are used. Some variants that are shown correctly: John Smith <jksmith@domain.org> Random J. Developer <rjd@tld.com> Random J. Developer (rjd@tld.com) J. Random Developer rjd@tld.com Variants that are shown nominally correctly: Written by First Last (funny-addr@somecompany.com) is shown as: First Last <funny-addr@somecompany.com> Variants that are shown incorrectly: Some Really Long Name <srln@foo.bar> MontaVista Software, Inc. <source@mvista.com> are returned as: Long Name <srln@foo.bar> "Software, Inc" <source@mvista.com> --roles and --rolestats show "(in file)" for matches. For instance: Without -file-emails: $ ./scripts/get_maintainer.pl -f -nogit -roles net/core/netpoll.c David S. Miller <davem@davemloft.net> (maintainer:NETWORKING [GENERAL]) linux-kernel@vger.kernel.org (open list) With -fe: $ ./scripts/get_maintainer.pl -f -fe -nogit -roles net/core/netpoll.c David S. Miller <davem@davemloft.net> (maintainer:NETWORKING [GENERAL]) Matt Mackall <mpm@selenic.com> (in file) Ingo Molnar <mingo@redhat.com> (in file) linux-kernel@vger.kernel.org (open list) netdev@vger.kernel.org (open list:NETWORKING [GENERAL]) The number of email addresses in the file in not limited. Neither is the number of returned email addresses. Signed-off-by: -
Gustavo F. Padovan authored
kernel/printk.c:72: warning: `saved_console_loglevel' defined but not used Signed-off-by:
Gustavo F. Padovan <padovan@profusion.mobi> Cc: Ingo Molnar <mingo@elte.hu> Signed-off-by:
-
Michael Neuling authored
Currently we create the initial stack based on the PAGE_SIZE. This is unnecessary. This creates this initial stack independent of the PAGE_SIZE. It also bumps up the number of 4k pages allocated from 20 to 32, to align with 64K page systems. Signed-off-by:
Michael Neuling <mikey@neuling.org> Cc: Helge Deller <deller@gmx.de> Reviewed-by:
KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Cc: Americo Wang <xiyou.wangcong@gmail.com> Cc: Anton Blanchard <anton@samba.org> Signed-off-by:
-
Tetsuo Handa authored
tasklist_lock does protect the task and its pid, it can't go away. The problem is that find_pid_ns() itself is unsafe without rcu lock, it can race with copy_process()->free_pid(any_pid). Protecting copy_process()->free_pid(any_pid) with tasklist_lock would make it possible to call find_task_by_pid_ns() under tasklist safely, but we don't do so because we are trying to get rid of the read_lock sites of tasklist_lock. Signed-off-by:
Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp> Cc: Oleg Nesterov <oleg@redhat.com> Cc: "Paul E. McKenney" <paulmck@us.ibm.com> Signed-off-by:
-
Anton Blanchard authored
I've had some complaints about panic_timeout being wildly innacurate on shared processor PowerPC partitions (a 3 minute panic_timeout taking 30 minutes). The problem is we loop on mdelay(1) and with a 1ms in 10ms hypervisor timeslice each of these will take 10ms (ie 10x) longer. I expect other platforms with shared processor hypervisors will see the same issue. This patch keeps the old behaviour if we have a panic_blink (only keyboard LEDs right now) and does 1 second mdelays if we don't. Signed-off-by:
Anton Blanchard <anton@samba.org> Cc: Ingo Molnar <mingo@elte.hu> Signed-off-by:
-
Jiri Slaby authored
Make sure compiler won't do weird things with limits. E.g. fetching them twice may return 2 different values after writable limits are implemented. I.e. either use rlimit helpers added in commit 3e10e716 ("resource: add helpers for fetching rlimits") or ACCESS_ONCE if not applicable. Signed-off-by:
Jiri Slaby <jslaby@suse.cz> Cc: Ingo Molnar <mingo@elte.hu> Cc: Peter Zijlstra <peterz@infradead.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: john stultz <johnstul@us.ibm.com> Signed-off-by:
-
Jiri Slaby authored
Fetch rlimit (both hard and soft) values only once and work on them. It removes many accesses through sig structure and makes the code cleaner. Mostly a preparation for writable resource limits support. Signed-off-by:
-
Thiago Farina authored
kernel/exit.c:1183:26: warning: symbol 'status' shadows an earlier one kernel/exit.c:1173:21: originally declared here Signed-off-by:
Thiago Farina <tfransosi@gmail.com> Signed-off-by:
-
Jaswinder Singh Rajput authored
Fix the following 'make includecheck' warning: kernel/params.c: linux/string.h is included more than once. Signed-off-by:
Jaswinder Singh Rajput <jaswinderrajput@gmail.com> Cc: André Goddard Rosa <andre.goddard@gmail.com> Signed-off-by:
-
Dan Carpenter authored
"ret" needs to be signed or the error handling for splice_to_pipe() won't work correctly. Signed-off-by:
Dan Carpenter <error27@gmail.com> Cc: Tom Zanussi <zanussi@comcast.net> Cc: Jens Axboe <jens.axboe@oracle.com> Cc: Lai Jiangshan <laijs@cn.fujitsu.com> Signed-off-by:
-
Simon Kagstrom authored
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:
-
Thadeu Lima de Souza Cascardo authored
Signed-off-by:
Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com> Cc: Kay Sievers <kay.sievers@vrfy.org> Cc: Greg Kroah-Hartman <gregkh@suse.de> Cc: Alan Cox <alan@lxorguk.ukuu.org.uk> Signed-off-by:
-
Julia Lawall authored
The variable priv is initialized twice to the same (side effect-free) expression. Drop one initialization. A simplified version of the semantic match that finds this problem is: (http://coccinelle.lip6.fr/) // <smpl> @forall@ idexpression *x; identifier f!=ERR_PTR; @@ x = f(...) ... when != x ( x = f(...,<+...x...+>,...) | * x = f(...) ) // </smpl> Signed-off-by:
Julia Lawall <julia@diku.dk> Cc: Tomas Winkler <tomas.winkler@intel.com> Signed-off-by:
-
H Hartley Sweeten authored
The only in tree external users of the symbol setup_max_cpus are in arch/x86/. The files ./kernel/alternative.c, ./kernel/visws_quirks.c, and ./mm/kmemcheck/kmemcheck.c are all guarded by CONFIG_SMP being defined. For this case the symbol is an unsigned int and declared as an extern in include/linux/smp.h. When CONFIG_SMP is not defined the symbol setup_max_cpus is a constant value that is only used in init/main.c. Make the symbol static for this case. Signed-off-by:
H Hartley Sweeten <hsweeten@visionengravers.com> Signed-off-by:
-
Rakib Mullick authored
smp: Fix documentation. Fix documentation in include/linux/smp.h: smp_processor_id() Signed-off-by:
Rakib Mullick <rakib.mullick@gmail.com> Signed-off-by:
-
H Hartley Sweeten authored
The macro any_online_node() is prone to producing sparse warnings due to the local symbol 'node'. Since all the in-tree users are really requesting the first online node (the mask argument is either NODE_MASK_ALL or node_online_map) just use the first_online_node macro and remove the any_online_node macro since there are no users. Signed-off-by:
David Rientjes <rientjes@google.com> Reviewed-by:
KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com> Cc: Mel Gorman <mel@csn.ul.ie> Cc: Lee Schermerhorn <lee.schermerhorn@hp.com> Acked-by:
Benjamin Herrenschmidt <benh@kernel.crashing.org> Cc: Paul Mackerras <paulus@samba.org> Cc: Dave Hansen <dave@linux.vnet.ibm.com> Cc: Milton Miller <miltonm@bga.com> Cc: Nathan Fontenot <nfont@austin.ibm.com> Cc: Geoff Levand <geoffrey.levand@am.sony.com> Cc: Grant Likely <grant.likely@secretlab.ca> Cc: J. Bruce Fields <bfields@fieldses.org> Cc: Neil Brown <neilb@suse.de> Cc: Trond Myklebust <Trond.Myklebust@netapp.com> Cc: David S. Miller <davem@davemloft.net> Cc: Benny Halevy <bhalevy@panasas.com> Cc: Chuck Lever <chuck.lever@oracle.com> Cc: Ricardo Labiaga <Ricardo.Labiaga@netapp.com> Signed-off-by:
-
Jiri Slaby authored
Make sure compiler won't do weird things with limits. E.g. fetching them twice may return 2 different values after writable limits are implemented. I.e. either use rlimit helpers added in commit 3e10e716 ("resource: add helpers for fetching rlimits") or ACCESS_ONCE if not applicable. Signed-off-by:
-
Heiko Carstens authored
Dependent on CONFIG_SMP the num_*_cpus() functions return unsigned or signed values. Let them always return unsigned values to avoid strange casts. Fixes at least one warning: kernel/kprobes.c: In function 'register_kretprobe': kernel/kprobes.c:1038: warning: comparison of distinct pointer types lacks a cast Signed-off-by:
Heiko Carstens <heiko.carstens@de.ibm.com> Cc: Heiko Carstens <heiko.carstens@de.ibm.com> Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com> Cc: Masami Hiramatsu <mhiramat@redhat.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: Rusty Russell <rusty@rustcorp.com.au> Signed-off-by:
-
H Hartley Sweeten authored
The symbol 'count' is a local global variable in this file. The function clean_rootfs() should use a different symbol name to prevent "symbol shadows an earlier one" noise. Signed-off-by:
-
Andreas Mohr authored
- new Documentation/init.txt file describing various forms of failure trying to load the init binary after kernel bootup - extend the init/main.c init failure message to direct to Documentation/init.txt Signed-off-by:
Andreas Mohr <andi@lisas.de> Signed-off-by:
-
Chen Gong authored
Additional_cpus is only supported for IA64 now. X86_64 should not be included. Signed-off-by:
Chen Gong <gong.chen@linux.intel.com> Cc: Ingo Molnar <mingo@elte.hu> Cc: Rusty Russell <rusty@rustcorp.com.au> Signed-off-by:
-
Randy Dunlap authored
Move the CS5535 MFGPT hrtimer kconfig option to be with the other MFGPT options. This makes it easier to find and also removes it from the main "Device Drivers" menu, where it should not have been. Signed-off-by:
Randy Dunlap <randy.dunlap@oracle.com> Acked-by:
Andres Salomon <dilinger@collabora.co.uk> Signed-off-by:
-
WANG Cong authored
Tell git to ignore the generated files under um, except: include/shared/kern_constants.h include/shared/user_constants.h which will be moved to include/generated. Signed-off-by:
WANG Cong <xiyou.wangcong@gmail.com> Cc: Al Viro <viro@zeniv.linux.org.uk> Cc: Jeff Dike <jdike@addtoit.com> Signed-off-by:
-
Alexander Beregalov authored
Assign tty only if line is not NULL. [akpm@linux-foundation.org: simplification] Signed-off-by:
Alexander Beregalov <a.beregalov@gmail.com> Cc: Jeff Dike <jdike@addtoit.com> Signed-off-by:
-
Roel Kluin authored
With id 1 the wrong bp was unwatched. Signed-off-by:
Roel Kluin <roel.kluin@gmail.com> Cc: Mikael Starvik <starvik@axis.com> Cc: Jesper Nilsson <jesper.nilsson@axis.com> Signed-off-by:
-
