summaryrefslogtreecommitdiffstats
path: root/lib
Commit message (Collapse)AuthorAgeFilesLines
* spelling fixesAndreas Mohr2006-06-261-2/+2
| | | | | | | | | | | | 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>
* move acknowledgment for Mark Adler to CREDITSAdrian Bunk2006-06-261-9/+0
| | | | | | | | | | 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>
* [PATCH] fix race in idr codeSonny Rao2006-06-251-4/+12
| | | | | | | | | | | | | | | | | | | | | | | 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
* [PATCH] Implement kasprintfJeremy Fitzhardinge2006-06-251-0/+23
| | | | | | | | | | | 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>
* [PATCH] Fix bounds check in vsnprintf, to allow for a 0 size and NULL bufferJeremy Fitzhardinge2006-06-251-32/+33
| | | | | | | | | | | | | | | | | | | | | | | 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>
* [PATCH] reed-solomon: fix kernel-doc commentsRandy Dunlap2006-06-251-9/+2
| | | | | | | | 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>
* [PATCH] kernel-doc for lib/crc*.cRandy Dunlap2006-06-253-40/+30
| | | | | | | | | 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>
* [PATCH] kernel-doc for lib/bitmap.cRandy Dunlap2006-06-251-15/+16
| | | | | | | | | 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>
* [PATCH] radixtree: normalize radix_tree_tag_get() return valueWu Fengguang2006-06-251-1/+1
| | | | | | | | | 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>
* [PATCH] constify libcrc32c tableAndreas Mohr2006-06-251-1/+1
| | | | | | | | 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>
* [PATCH] strstrip() APIPekka Enberg2006-06-231-0/+30
| | | | | | | | | | | | | | 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>
* [PATCH] percpu counter data type changes to suppport more than 2**31 ext3 ↵Mingming Cao2006-06-231-5/+5
| | | | | | | | | | | | | | | | | | | | | 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>
* [PATCH] percpu_counters: create lib/percpu_counter.cRavikiran G Thirumalai2006-06-232-0/+47
| | | | | | | | - 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>
* [PATCH] buglet in radix_tree_tag_setPeter Zijlstra2006-06-231-2/+1
| | | | | | | | | | | | | | | | | | | | | | | 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>
* [PATCH] radix-tree: smallNick Piggin2006-06-231-1/+1
| | | | | | | | | | 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>
* [PATCH] radix-tree: direct dataNick Piggin2006-06-231-81/+111
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* [PATCH] change gen_pool allocator to not touch managed memoryDean Nelson2006-06-231-142/+121
| | | | | | | | | | | | | | | | | | | | | | | 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>
* [PATCH] zlib_inflate: Upgrade library code to a recent versionRichard Purdie2006-06-2218-1910/+1732
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* [PATCH] kobject: make people pay attention to kobject_add errorsGreg Kroah-Hartman2006-06-211-3/+3
| | | | | | These really need to be fixed, shout it out to the world. Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
* [PATCH] add __iowrite64_copyBrice Goglin2006-06-201-0/+28
| | | | | | | | | | | | | 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>
* Merge git://git.infradead.org/~dwmw2/rbtree-2.6Linus Torvalds2006-06-201-96/+93
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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
| * [RBTREE] Switch rb_colour() et al to en_US spelling of 'color' for consistencyDavid Woodhouse2006-06-051-5/+5
| | | | | | | | | | | | | | 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>
| * [RBTREE] Merge colour and parent fields of struct rb_node.David Woodhouse2006-04-211-88/+90
| | | | | | | | | | | | | | | | | | 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>
| * [RBTREE] Remove dead code in rb_erase()David Woodhouse2006-04-211-10/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Observe rb_erase(), when the victim node 'old' has two children so neither of the simple cases at the beginning are taken. Observe that it effectively does an 'rb_next()' operation to find the next (by value) node in the tree. That is; we go to the victim's right-hand child and then follow left-hand pointers all the way down the tree as far as we can until we find the next node 'node'. We end up with 'node' being either the same immediate right-hand child of 'old', or one of its descendants on the far left-hand side. For a start, we _know_ that 'node' has a parent. We can drop that check. We also know that if 'node's parent is 'old', then 'node' is the right-hand child of its parent. And that if 'node's parent is _not_ 'old', then 'node' is the left-hand child of its parent. So instead of checking for 'node->rb_parent == old' in one place and also checking 'node's heritage separately when we're trying to change its link from its parent, we can shuffle things around a bit and do it like this... Signed-off-by: David Woodhouse <dwmw2@infradead.org>
* | [PATCH] kobject: quiet errors in kobject_addGreg Kroah-Hartman2006-05-211-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* | [SPARC]: Handle UNWIND_INFO properly.David S. Miller2006-05-121-1/+1
| | | | | | | | | | | | | | | | | | 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>
* | [PATCH] Kobject: possible cleanupsAdrian Bunk2006-04-271-5/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* | [PATCH] Kobject: fix build errorKay Sievers2006-04-271-1/+7
|/ | | | | | | | | | 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>
* [PATCH] Kconfig.debug: Set DEBUG_MUTEX to off by defaultTim Chen2006-04-191-1/+1
| | | | | | | | | | | | | | | | | DEBUG_MUTEX flag is on by default in current kernel configuration. During performance testing, we saw mutex debug functions like mutex_debug_check_no_locks_freed (called by kfree()) is expensive as it goes through a global list of memory areas with mutex lock and do the checking. For benchmarks such as Volanomark and Hackbench, we have seen more than 40% drop in performance on some platforms. We suggest to set DEBUG_MUTEX off by default. Or at least do that later when we feel that the mutex changes in the current code have stabilized. Signed-off-by: Tim Chen <tim.c.chen@intel.com> Cc: Ingo Molnar <mingo@elte.hu> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] sysfs: Allow sysfs attribute files to be pollableNeilBrown2006-04-141-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | It works like this: Open the file Read all the contents. Call poll requesting POLLERR or POLLPRI (so select/exceptfds works) When poll returns, close the file and go to top of loop. or lseek to start of file and go back to the 'read'. Events are signaled by an object manager calling sysfs_notify(kobj, dir, attr); If the dir is non-NULL, it is used to find a subdirectory which contains the attribute (presumably created by sysfs_create_group). This has a cost of one int per attribute, one wait_queuehead per kobject, one int per open file. The name "sysfs_notify" may be confused with the inotify functionality. Maybe it would be nice to support inotify for sysfs attributes as well? This patch also uses sysfs_notify to allow /sys/block/md*/md/sync_action to be pollable Signed-off-by: Neil Brown <neilb@suse.de> Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
* [PATCH] Silence a const vs non-const warningJan-Benedict Glaw2006-04-111-1/+1
| | | | | | | | | | lib/string.c: In function 'memcpy': lib/string.c:470: warning: initialization discards qualifiers from pointer = target type Signed-off-by: Jan-Benedict Glaw <jbglaw@lug-owl.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] Clean up arch-overrides in linux/string.hKyle McMartin2006-04-111-0/+2
| | | | | | | | | | | | | | Some string functions were safely overrideable in lib/string.c, but their corresponding declarations in linux/string.h were not. Correct this, and make strcspn overrideable. Odds of someone wanting to do optimized assembly of these are small, but for the sake of cleanliness, might as well bring them into line with the rest of the file. Signed-off-by: Kyle McMartin <kyle@parisc-linux.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] No arch-specific strpbrk implementationsKyle McMartin2006-04-111-0/+1
| | | | | | | | | | | | | | | While cleaning up parisc_ksyms.c earlier, I noticed that strpbrk wasn't being exported from lib/string.c. Investigating further, I noticed a changeset that removed its export and added it to _ksyms.c on a few more architectures. The justification was that "other arches do it." I think this is wrong, since no architecture currently defines __HAVE_ARCH_STRPBRK, there's no reason for any of them to be exporting it themselves. Therefore, consolidate the export to lib/string.c. Signed-off-by: Kyle McMartin <kyle@parisc-linux.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PARISC] Remove obsolete CONFIG_DEBUG_IOREMAPHelge Deller2006-03-301-13/+0
| | | | | | | | Remove CONFIG_DEBUG_IOREMAP, it's now obsolete and won't work anyway. Remove it from lib/KConfig since it was only available on parisc. Signed-off-by: Helge Deller <deller@parisc-linux.org> Signed-off-by: Kyle McMartin <kyle@parisc-linux.org>
* [PATCH] Don't make debugfs depend on DEBUG_KERNELJens Axboe2006-03-271-1/+1
| | | | | | | We use it generally now, at least blktrace isn't a specific debug kernel feature. Signed-off-by: Jens Axboe <axboe@suse.de>
* [PATCH] bitops: hweight() speedupAkinobu Mita2006-03-261-15/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | <linux@horizon.com> wrote: This is an extremely well-known technique. You can see a similar version that uses a multiply for the last few steps at http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel whch refers to "Software Optimization Guide for AMD Athlon 64 and Opteron Processors" http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/25112.PDF It's section 8.6, "Efficient Implementation of Population-Count Function in 32-bit Mode", pages 179-180. It uses the name that I am more familiar with, "popcount" (population count), although "Hamming weight" also makes sense. Anyway, the proof of correctness proceeds as follows: b = a - ((a >> 1) & 0x55555555); c = (b & 0x33333333) + ((b >> 2) & 0x33333333); d = (c + (c >> 4)) & 0x0f0f0f0f; #if SLOW_MULTIPLY e = d + (d >> 8) f = e + (e >> 16); return f & 63; #else /* Useful if multiply takes at most 4 cycles */ return (d * 0x01010101) >> 24; #endif The input value a can be thought of as 32 1-bit fields each holding their own hamming weight. Now look at it as 16 2-bit fields. Each 2-bit field a1..a0 has the value 2*a1 + a0. This can be converted into the hamming weight of the 2-bit field a1+a0 by subtracting a1. That's what the (a >> 1) & mask subtraction does. Since there can be no borrows, you can just do it all at once. Enumerating the 4 possible cases: 0b00 = 0 -> 0 - 0 = 0 0b01 = 1 -> 1 - 0 = 1 0b10 = 2 -> 2 - 1 = 1 0b11 = 3 -> 3 - 1 = 2 The next step consists of breaking up b (made of 16 2-bir fields) into even and odd halves and adding them into 4-bit fields. Since the largest possible sum is 2+2 = 4, which will not fit into a 4-bit field, the 2-bit ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ "which will not fit into a 2-bit field" fields have to be masked before they are added. After this point, the masking can be delayed. Each 4-bit field holds a population count from 0..4, taking at most 3 bits. These numbers can be added without overflowing a 4-bit field, so we can compute c + (c >> 4), and only then mask off the unwanted bits. This produces d, a number of 4 8-bit fields, each in the range 0..8. From this point, we can shift and add d multiple times without overflowing an 8-bit field, and only do a final mask at the end. The number to mask with has to be at least 63 (so that 32 on't be truncated), but can also be 128 or 255. The x86 has a special encoding for signed immediate byte values -128..127, so the value of 255 is slower. On other processors, a special "sign extend byte" instruction might be faster. On a processor with fast integer multiplies (Athlon but not P4), you can reduce the final few serially dependent instructions to a single integer multiply. Consider d to be 3 8-bit values d3, d2, d1 and d0, each in the range 0..8. The multiply forms the partial products: d3 d2 d1 d0 d3 d2 d1 d0 d3 d2 d1 d0 + d3 d2 d1 d0 ---------------------- e3 e2 e1 e0 Where e3 = d3 + d2 + d1 + d0. e2, e1 and e0 obviously cannot generate any carries. Signed-off-by: Akinobu Mita <mita@miraclelinux.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] bitops: hweight() related cleanupAkinobu Mita2006-03-261-17/+2
| | | | | | | | | | | | | By defining generic hweight*() routines - hweight64() will be defined on all architectures - hweight_long() will use architecture optimized hweight32() or hweight64() I found two possible cleanups by these reasons. Signed-off-by: Akinobu Mita <mita@miraclelinux.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] bitops: generic ↵Akinobu Mita2006-03-261-0/+73
| | | | | | | | | | | | | | | | | | | | | | | | | ext2_{set,clear,test,find_first_zero,find_next_zero}_bit() This patch introduces the C-language equivalents of the functions below: int ext2_set_bit(int nr, volatile unsigned long *addr); int ext2_clear_bit(int nr, volatile unsigned long *addr); int ext2_test_bit(int nr, const volatile unsigned long *addr); unsigned long ext2_find_first_zero_bit(const unsigned long *addr, unsigned long size); unsinged long ext2_find_next_zero_bit(const unsigned long *addr, unsigned long size); In include/asm-generic/bitops/ext2-non-atomic.h This code largely copied from: include/asm-powerpc/bitops.h include/asm-parisc/bitops.h Signed-off-by: Akinobu Mita <mita@miraclelinux.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] bitops: generic hweight{64,32,16,8}()Akinobu Mita2006-03-262-0/+55
| | | | | | | | | | | | | | | | | This patch introduces the C-language equivalents of the functions below: unsigned int hweight32(unsigned int w); unsigned int hweight16(unsigned int w); unsigned int hweight8(unsigned int w); unsigned long hweight64(__u64 w); In include/asm-generic/bitops/hweight.h This code largely copied from: include/linux/bitops.h Signed-off-by: Akinobu Mita <mita@miraclelinux.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] bitops: generic find_{next,first}{,_zero}_bit()Akinobu Mita2006-03-261-31/+81
| | | | | | | | | | | | | | | | | | | | This patch introduces the C-language equivalents of the functions below: unsigned logn find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset); unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, unsigned long offset); unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size); unsigned long find_first_bit(const unsigned long *addr, unsigned long size); In include/asm-generic/bitops/find.h This code largely copied from: arch/powerpc/lib/bitops.c Signed-off-by: Akinobu Mita <mita@miraclelinux.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* [PATCH] x86_64: Don't enable CONFIG_UNWIND_INFO by default for DEBUG_KERNELAndi Kleen2006-03-251-1/+0
| | | | | | | | | | DEBUG_KERNEL is often enabled just for sysrq, but this doesn't mean the user wants more heavyweight debugging information. Cc: jbeulich@novell.com Signed-off-by: Andi Kleen <ak@suse.de> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* Merge git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivialLinus Torvalds2006-03-251-20/+12
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * git://git.kernel.org/pub/scm/linux/kernel/git/bunk/trivial: (21 commits) BUG_ON() Conversion in drivers/video/ BUG_ON() Conversion in drivers/parisc/ BUG_ON() Conversion in drivers/block/ BUG_ON() Conversion in sound/sparc/cs4231.c BUG_ON() Conversion in drivers/s390/block/dasd.c BUG_ON() Conversion in lib/swiotlb.c BUG_ON() Conversion in kernel/cpu.c BUG_ON() Conversion in ipc/msg.c BUG_ON() Conversion in block/elevator.c BUG_ON() Conversion in fs/coda/ BUG_ON() Conversion in fs/binfmt_elf_fdpic.c BUG_ON() Conversion in input/serio/hil_mlc.c BUG_ON() Conversion in md/dm-hw-handler.c BUG_ON() Conversion in md/bitmap.c The comment describing how MS_ASYNC works in msync.c is confusing rcu: undeclared variable used in documentation fix typos "wich" -> "which" typo patch for fs/ufs/super.c Fix simple typos tabify drivers/char/Makefile ...
| * BUG_ON() Conversion in lib/swiotlb.cEric Sesterhenn2006-03-241-20/+12
| | | | | | | | | | | | | | | | this changes if() BUG(); constructs to BUG_ON() which is cleaner, contains unlikely() and can better optimized away. Signed-off-by: Eric Sesterhenn <snakebyte@gmx.de> Signed-off-by: Adrian Bunk <bunk@stusta.de>
* | [PATCH] cpumask: uninline any_online_cpu()Andrew Morton2006-03-251-0/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | text data bss dec hex filename before: 3605597 1363528 363328 5332453 515de5 vmlinux after: 3605295 1363612 363200 5332107 515c8b vmlinux 218 bytes saved. Also, optimise any_online_cpu() out of existence on CONFIG_SMP=n. This function seems inefficient. Can't we simply AND the two masks, then use find_first_bit()? Cc: Paul Jackson <pj@sgi.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | [PATCH] cpumask: uninline highest_possible_processor_id()Andrew Morton2006-03-251-0/+17
| | | | | | | | | | | | | | | | | | | | | | Shrinks the only caller (net/bridge/netfilter/ebtables.c) by 174 bytes. Also, optimise highest_possible_processor_id() out of existence on CONFIG_SMP=n. Cc: Paul Jackson <pj@sgi.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | [PATCH] cpumask: uninline next_cpu()Andrew Morton2006-03-251-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | text data bss dec hex filename before: 3488027 1322496 360128 5170651 4ee5db vmlinux after: 3485112 1322480 359968 5167560 4ed9c8 vmlinux 2931 bytes saved Cc: Paul Jackson <pj@sgi.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | [PATCH] cpumask: uninline first_cpu()Andrew Morton2006-03-252-0/+13
| | | | | | | | | | | | | | | | | | | | text data bss dec hex filename before: 3490577 1322408 360000 5172985 4eeef9 vmlinux after: 3488027 1322496 360128 5170651 4ee5db vmlinux Cc: Paul Jackson <pj@sgi.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | [PATCH] radix-tree documentation cleanupsJonathan Corbet2006-03-251-22/+27
| | | | | | | | | | | | | | | | | | | | | | | | Documentation changes to help radix tree users avoid overrunning the tags array. RADIX_TREE_TAGS moves to linux/radix-tree.h and is now known as RADIX_TREE_MAX_TAGS (Nick Piggin's idea). Tag parameters are changed to unsigned, and some comments are updated. Signed-off-by: Jonathan Corbet <corbet@lwn.net> Cc: Nick Piggin <nickpiggin@yahoo.com.au> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | [PATCH] kconfig: clarify memory debug optionsAndrew Morton2006-03-251-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | The Kconfig text for CONFIG_DEBUG_SLAB and CONFIG_DEBUG_PAGEALLOC have always seemed a bit confusing. Change them to: CONFIG_DEBUG_SLAB: "Debug slab memory allocations" CONFIG_DEBUG_PAGEALLOC: "Debug page memory allocations" Cc: "David S. Miller" <davem@davemloft.net> Cc: Hirokazu Takata <takata@linux-m32r.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
* | [PATCH] slab: implement /proc/slab_allocatorsAl Viro2006-03-251-0/+4
|/ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Implement /proc/slab_allocators. It produces output like: idr_layer_cache: 80 idr_pre_get+0x33/0x4e buffer_head: 2555 alloc_buffer_head+0x20/0x75 mm_struct: 9 mm_alloc+0x1e/0x42 mm_struct: 20 dup_mm+0x36/0x370 vm_area_struct: 384 dup_mm+0x18f/0x370 vm_area_struct: 151 do_mmap_pgoff+0x2e0/0x7c3 vm_area_struct: 1 split_vma+0x5a/0x10e vm_area_struct: 11 do_brk+0x206/0x2e2 vm_area_struct: 2 copy_vma+0xda/0x142 vm_area_struct: 9 setup_arg_pages+0x99/0x214 fs_cache: 8 copy_fs_struct+0x21/0x133 fs_cache: 29 copy_process+0xf38/0x10e3 files_cache: 30 alloc_files+0x1b/0xcf signal_cache: 81 copy_process+0xbaa/0x10e3 sighand_cache: 77 copy_process+0xe65/0x10e3 sighand_cache: 1 de_thread+0x4d/0x5f8 anon_vma: 241 anon_vma_prepare+0xd9/0xf3 size-2048: 1 add_sect_attrs+0x5f/0x145 size-2048: 2 journal_init_revoke+0x99/0x302 size-2048: 2 journal_init_revoke+0x137/0x302 size-2048: 2 journal_init_inode+0xf9/0x1c4 Cc: Manfred Spraul <manfred@colorfullife.com> Cc: Alexander Nyberg <alexn@telia.com> Cc: Pekka Enberg <penberg@cs.helsinki.fi> Cc: Christoph Lameter <clameter@engr.sgi.com> Cc: Ravikiran Thirumalai <kiran@scalex86.org> Signed-off-by: Al Viro <viro@zeniv.linux.org.uk> DESC slab-leaks3-locking-fix EDESC From: Andrew Morton <akpm@osdl.org> Update for slab-remove-cachep-spinlock.patch Cc: Al Viro <viro@ftp.linux.org.uk> Cc: Manfred Spraul <manfred@colorfullife.com> Cc: Alexander Nyberg <alexn@telia.com> Cc: Pekka Enberg <penberg@cs.helsinki.fi> Cc: Christoph Lameter <clameter@engr.sgi.com> Cc: Ravikiran Thirumalai <kiran@scalex86.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
OpenPOWER on IntegriCloud