aboutsummaryrefslogtreecommitdiff
path: root/lib
AgeCommit message (Collapse)AuthorFilesLines
2007-12-23lib: proportion: fix underflow in prop_norm_percpu()Peter Zijlstra1-21/+16
Zhe Jiang noticed that its possible to underflow pl->events in prop_norm_percpu() when the value returned by percpu_counter_read() is less than the error on that read and the period delay > 1. In that case half might not trigger the batch increment and the value will be identical on the next iteration, causing the same half to be subtracted again and again. Fix this by rewriting the division as a single subtraction instead of a subtraction loop and using percpu_counter_sum() when the value returned by percpu_counter_read() is smaller than the error. The latter is still needed if we want pl->events to shrink properly in the error region. [[email protected]: cleanups] Signed-off-by: Peter Zijlstra <[email protected]> Reviewed-by: Jiang Zhe <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-12-18sched: mark rwsem functions as __sched for wchan/profilingLivio Soares1-1/+1
This following commit http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=fdf8cb0909b531f9ae8f9b9d7e4eb35ba3505f07 un-inlined a low-level rwsem function, but did not mark it as __sched. The result is that it now shows up as thread wchan (which also affects /proc/profile stats). The following simple patch fixes this by properly marking rwsem_down_failed_common() as a __sched function. Also in this patch, which is up for discussion, marks down_read() and down_write() proper as __sched. For profiling, it is pretty much useless to know that a semaphore is beig help - it is necessary to know _which_ one. By going up another frame on the stack, the information becomes much more useful. In summary, the below change to lib/rwsem.c should be applied; the changes to kernel/rwsem.c could be applied if other kernel hackers agree with my proposal that down_read()/down_write() in the profile is not enough. [ [email protected]: build fix ] Signed-off-by: Livio Soares <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Ingo Molnar <[email protected]>
2007-12-17kobject: fix the documentation of how kobject_set_name worksGreg Kroah-Hartman1-6/+6
Thanks to Dave Young <[email protected]> for pointing out that I forgot to update the comment when I rewrote kobject_set_name. Cc: Dave Young <[email protected]> Signed-off-by: Greg Kroah-Hartman <[email protected]>
2007-12-03Merge git://git.kernel.org/pub/scm/linux/kernel/git/herbert/net-2.6Linus Torvalds1-2/+6
* git://git.kernel.org/pub/scm/linux/kernel/git/herbert/net-2.6: (27 commits) [INET]: Fix inet_diag dead-lock regression [NETNS]: Fix /proc/net breakage [TEXTSEARCH]: Do not allow zero length patterns in the textsearch infrastructure [NETFILTER]: fix forgotten module release in xt_CONNMARK and xt_CONNSECMARK [NETFILTER]: xt_TCPMSS: remove network triggerable WARN_ON [DECNET]: dn_nl_deladdr() almost always returns no error [IPV6]: Restore IPv6 when MTU is big enough [RXRPC]: Add missing select on CRYPTO mac80211: rate limit wep decrypt failed messages rfkill: fix double-mutex-locking mac80211: drop unencrypted frames if encryption is expected mac80211: Fix behavior of ieee80211_open and ieee80211_close ieee80211: fix unaligned access in ieee80211_copy_snap mac80211: free ifsta->extra_ie and clear IEEE80211_STA_PRIVACY_INVOKED SCTP: Fix build issues with SCTP AUTH. SCTP: Fix chunk acceptance when no authenticated chunks were listed. SCTP: Fix the supported extensions paramter SCTP: Fix SCTP-AUTH to correctly add HMACS paramter. SCTP: Fix the number of HB transmissions. [TCP] illinois: Incorrect beta usage ...
2007-12-01[TEXTSEARCH]: Do not allow zero length patterns in the textsearch infrastructurePablo Neira Ayuso1-2/+6
If a zero length pattern is passed then return EINVAL. Avoids infinite loops (bm) or invalid memory accesses (kmp). Signed-off-by: Pablo Neira Ayuso <[email protected]> Signed-off-by: Patrick McHardy <[email protected]> Signed-off-by: Herbert Xu <[email protected]>
2007-11-29hexdump: don't print bytes with bit 7 setRandy Dunlap1-1/+2
As Herbert Xu pointed out, bytes (chars) with bit 7 (0x80) set are true with isprint() but they may not be isascii() but be Unicode instead, so don't try to print them in hex dumps. Signed-off-by: Randy Dunlap <[email protected]> Cc: Herbert Xu <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-11-28kobject: two typo fixesJohannes Berg1-2/+2
This fixes two typos from commit 34358c26a2c96b2a068dc44e0ac602106a466bce. Signed-off-by: Johannes Berg <[email protected]> Signed-off-by: Greg Kroah-Hartman <[email protected]>
2007-11-23Blackfin arch: punt CONFIG_BFIN -- we already have CONFIG_BLACKFINMike Frysinger1-2/+2
Signed-off-by: Mike Frysinger <[email protected]> Signed-off-by: Bryan Wu <[email protected]>
2007-11-14lib: move bitmap.o from lib-y to obj-y.Paul Mundt1-2/+2
mac80211 has a reference to __bitmap_empty() via bitmap_empty(). In lib/bitmap.c this is flagged with an EXPORT_SYMBOL(), but this is ultimately ineffective due to bitmap.o being linked in lib-y, resulting in: ERROR: "__bitmap_empty" [net/mac80211/mac80211.ko] undefined! Moving bitmap.o to obj-y fixes this up. Signed-off-by: Paul Mundt <[email protected]> Cc: "John W. Linville" <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-11-08[LIB] crc32c: Keep intermediate crc state in cpu orderBenny Halevy1-5/+2
crypto/crc32.c:chksum_final() is computing the digest as *(__le32 *)out = ~cpu_to_le32(mctx->crc); so the low-level crc32c_le routines should just keep the crc in cpu order, otherwise it is getting swabbed one too many times on big-endian machines. Signed-off-by: Benny Halevy <[email protected]> Signed-off-by: Herbert Xu <[email protected]>
2007-11-05Fix bitmap_scnlistprintf for empty masksAndi Kleen1-0/+4
When a bitmap is empty bitmap_scnlistprintf() would leave the buffer uninitialized. Set it to an empty string in this case. I didn't see any in normal kernel callers hitting this, but some custom debug code of mine did. Signed-off-by: Andi Kleen <[email protected]> Acked-by: Paul Jackson <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-30kobject: check for duplicate names in kobject_renameGreg Kroah-Hartman1-0/+13
This should catch any duplicate names before we try to tell sysfs to rename the object. This happens a lot with older versions of udev and the network rename scripts. Cc: David Miller <[email protected]> Cc: Kay Sievers <[email protected]> Cc: Rafael J. Wysocki <[email protected]> Cc: Tejun Heo <[email protected]> Signed-off-by: Greg Kroah-Hartman <[email protected]>
2007-10-25Permit silencing of __deprecated warnings.Jeff Garzik1-0/+8
The __deprecated marker is quite useful in highlighting the remnants of old APIs that want removing. However, it is quite normal for one or more years to pass, before the (usually ancient, bitrotten) code in question is either updated or deleted. Thus, like __must_check, add a Kconfig option that permits the silencing of this compiler warning. This change mimics the ifdef-ery and Kconfig defaults of MUST_CHECK as closely as possible. Signed-off-by: Jeff Garzik <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-23Merge git://git.infradead.org/mtd-2.6Linus Torvalds2-3/+4
* git://git.infradead.org/mtd-2.6: [MTD] [NOR] Fix deadlock in Intel chip driver caused by get_chip recursion [JFFS2] Fix return value from jffs2_write_end() [MTD] [OneNAND] Fix wrong free the static address in onenand_sim [MTD] [NAND] Replace -1 with -EBADMSG in nand error correction code [RSLIB] BUG() when passing illegal parameters to decode_rs8() or decode_rs16() [MTD] [NAND] treat any negative return value from correct() as an error [MTD] [NAND] nandsim: bugfix in initialization [MTD] Fix typo in Alauda config option help text. [MTD] [NAND] add s3c2440-specific read_buf/write_buf [MTD] [OneNAND] onenand-sim: fix kernel-doc and typos [JFFS2] Tidy up fix for ACL/permissions problem.
2007-10-22Add CONFIG_DEBUG_SG sg validationJens Axboe1-0/+10
Add a Kconfig entry which will toggle some sanity checks on the sg entry and tables. Signed-off-by: Jens Axboe <[email protected]>
2007-10-22Update swiotlb to use sg helpersJens Axboe1-1/+1
Signed-off-by: Jens Axboe <[email protected]>
2007-10-20[MTD] [NAND] Replace -1 with -EBADMSG in nand error correction codeJörn Engel2-1/+3
Magic numerical values are just bad style. Particularly so when undocumented. Signed-off-by: Jörn Engel <[email protected]> Signed-off-by: David Woodhouse <[email protected]>
2007-10-20[RSLIB] BUG() when passing illegal parameters to decode_rs8() or decode_rs16()Jörn Engel1-2/+1
Returning -ERANGE should never happen. Signed-off-by: Jörn Engel <[email protected]> Signed-off-by: David Woodhouse <[email protected]>
2007-10-20spelling fixes: lib/Simon Arlott1-1/+1
Spelling fix in lib/. Signed-off-by: Simon Arlott <[email protected]> Signed-off-by: Adrian Bunk <[email protected]>
2007-10-20LIB: Replace inappropriate include of <linux/bug.h>Robert P. J. Day1-1/+2
Replace an irrelevant include of bug.h with the more appropriate includes of slab.h and module.h. it's not as if the original inclusion is an error, it's simply not related to the contents of that source file, while the other two are. compile-tested on i386. Signed-off-by: Robert P. J. Day <[email protected]> Signed-off-by: Adrian Bunk <[email protected]>
2007-10-19Fix misspellings of "system", "controller", "interrupt" and "necessary".Robert P. J. Day1-1/+1
Fix the various misspellings of "system", controller", "interrupt" and "[un]necessary". Signed-off-by: Robert P. J. Day <[email protected]> Signed-off-by: Adrian Bunk <[email protected]>
2007-10-19markers: Add samples subdirMathieu Desnoyers1-0/+2
Begin infrastructure for kernel code samples in the samples/ directory. Add its Kconfig and Kbuild files. Source its Kconfig file in all arch/ Kconfigs. Signed-off-by: Randy Dunlap <[email protected]> Signed-off-by: Mathieu Desnoyers <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-19Add irq protection in the percpu-counters cpu-hotplug-callback pathGautham R Shenoy1-2/+3
Some of the per-cpu counters and thus their locks are accessed from IRQ contexts. This can cause a deadlock if it interrupts a cpu-offline thread which is transferring a dead-cpu's counts to the global counter. Add appropriate IRQ protection in the cpu-hotplug callback path. Signed-off-by: Gautham R Shenoy <[email protected]> Cc: KAMEZAWA Hiroyuki <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-19Use helpers to obtain task pid in printksPavel Emelyanov1-4/+4
The task_struct->pid member is going to be deprecated, so start using the helpers (task_pid_nr/task_pid_vnr/task_pid_nr_ns) in the kernel. The first thing to start with is the pid, printed to dmesg - in this case we may safely use task_pid_nr(). Besides, printks produce more (much more) than a half of all the explicit pid usage. [[email protected]: git-drm went and changed lots of stuff] Signed-off-by: Pavel Emelyanov <[email protected]> Cc: Dave Airlie <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-19remove asm/bitops.h includesJiri Slaby1-1/+1
remove asm/bitops.h includes including asm/bitops directly may cause compile errors. don't include it and include linux/bitops instead. next patch will deny including asm header directly. Cc: Adrian Bunk <[email protected]> Signed-off-by: Jiri Slaby <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-19Fix cpusets update_cpumaskPaul Menage2-1/+71
Cause writes to cpuset "cpus" file to update cpus_allowed for member tasks: - collect batches of tasks under tasklist_lock and then call set_cpus_allowed() on them outside the lock (since this can sleep). - add a simple generic priority heap type to allow efficient collection of batches of tasks to be processed without duplicating or missing any tasks in subsequent batches. - make "cpus" file update a no-op if the mask hasn't changed - fix race between update_cpumask() and sched_setaffinity() by making sched_setaffinity() post-check that it's not running on any cpus outside cpuset_cpus_allowed(). [[email protected]: coding-style fixes] Signed-off-by: Paul Menage <[email protected]> Cc: Paul Jackson <[email protected]> Cc: David Rientjes <[email protected]> Cc: Nick Piggin <[email protected]> Cc: Peter Zijlstra <[email protected]> Cc: Balbir Singh <[email protected]> Cc: Cedric Le Goater <[email protected]> Cc: "Eric W. Biederman" <[email protected]> Cc: Serge Hallyn <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-18Replace __attribute_pure__ with __pureRalf Baechle2-9/+9
To be consistent with the use of attributes in the rest of the kernel replace all use of __attribute_pure__ with __pure and delete the definition of __attribute_pure__. Signed-off-by: Ralf Baechle <[email protected]> Cc: Russell King <[email protected]> Acked-by: Mauro Carvalho Chehab <[email protected]> Cc: Bryan Wu <[email protected]> Cc: Paul Mackerras <[email protected]> Cc: Benjamin Herrenschmidt <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17Merge branch 'for-linus' of git://git.kernel.dk/data/git/linux-2.6-blockLinus Torvalds1-1/+1
* 'for-linus' of git://git.kernel.dk/data/git/linux-2.6-block: [SCSI] Remove full sg table memset() [SCSI] ide-scsi: remove usage of sg_last() Fix loop terminating conditions in fill_sg(). [BLOCK] Clear sg entry before filling in blk_rq_map_sg() IA64: iommu uses sg_next with an invalid sg element cciss: disable DMA refetch on Smart Array P600 swiotlb: fix map_sg failure handling SPARC64: fix iommu sg chaining [SCSI] ide-scsi: use scsi_sg_count() instead of ->use_sg
2007-10-17lib/iomap.c:bad_io_access(): print 0x hex prefixRene Herman1-1/+1
Be explicit about printing hex. Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17avoid negative (and full-width) shifts in radix-tree.cPeter Lund1-6/+8
Negative shifts are not allowed in C (the result is undefined). Same thing with full-width shifts. It works on most platforms but not on the VAX with gcc 4.0.1 (it results in an "operand reserved" fault). Shifting by more than the width of the value on the left is also not allowed. I think the extra '>> 1' tacked on at the end in the original code was an attempt to work around that. Getting rid of that is an extra feature of this patch. Here's the chapter and verse, taken from the final draft of the C99 standard ("6.5.7 Bitwise shift operators", paragraph 3): "The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined." Thank you to Jan-Benedict Glaw, Christoph Hellwig, Maciej Rozycki, Pekka Enberg, Andreas Schwab, and Christoph Lameter for review. Special thanks to Andreas for spotting that my fix only removed half the undefined behaviour. Signed-off-by: Peter Lund <[email protected]> Christoph Lameter <[email protected]> Cc: Christoph Hellwig <[email protected]> Cc: "Maciej W. Rozycki" <[email protected]> Cc: Pekka Enberg <[email protected]> Cc: Andreas Schwab <[email protected]> Cc: Nick Piggin <[email protected]> Cc: WU Fengguang <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17handle recursive calls to bust_spinlocks()Jan Beulich1-3/+3
Various architectures may call bust_spinlocks() recursively; the function itself, however, doesn't appear to be meant to be called in this manner. Nevertheless, this doesn't appear to be a problem as long as bust_spinlocks(0) doesn't get called twice in a row (otherwise, unblank_screen() may enter the scheduler). However, at least on i386 die() has been capable of returning (and on other architectures this should really be that way, too) when notify_die() returns NOTIFY_STOP. Short of getting a reply to a respective query, this patch makes bust_spinlocks() increment/decrement oops_in_progress, and wake klogd only when the count drops back to zero. Signed-off-by: Jan Beulich <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib/sort.c optimizationSubbaiah Venkata1-1/+1
Hello, I fixed and tested a small bug in lib/sort.c file, heap sort function. The fix avoids unnecessary swap of contents when i is 0 (saves few loads and stores), which happens every time sort function is called. I felt the fix is worth bringing it to your attention given the importance and frequent use of the sort function. Acked-by: Matt Mackall <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib/ioremap.c should #include <linux/io.h>Adrian Bunk1-0/+1
Every file should include the headers containing the prototypes for its global functions (in this case ioremap_page_range()). Signed-off-by: Adrian Bunk <[email protected]> Acked-by: Haavard Skinnemoen <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17argv_split: allow argv_split to handle NULL pointer in argcp parameter ↵Neil Horman1-1/+3
gracefully It would be nice if the argv_split library function could gracefully handle a NULL pointer in the argcp parameter, so as to allow functions using it that did not care about the value of argc to not have to declare a useless variable. This patch accomplishes that. Tested by me, with successful results. Signed-off-by: Neil Horman <[email protected]> Acked-by: Jeremy Fitzhardinge <[email protected]> Cc: Satyam Sharma <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17Slab API: remove useless ctor parameter and reorder parametersChristoph Lameter2-3/+2
Slab constructors currently have a flags parameter that is never used. And the order of the arguments is opposite to other slab functions. The object pointer is placed before the kmem_cache pointer. Convert ctor(void *object, struct kmem_cache *s, unsigned long flags) to ctor(struct kmem_cache *s, void *object) throughout the kernel [[email protected]: coupla fixes] Signed-off-by: Christoph Lameter <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: floating proportionsPeter Zijlstra2-1/+386
Given a set of objects, floating proportions aims to efficiently give the proportional 'activity' of a single item as compared to the whole set. Where 'activity' is a measure of a temporal property of the items. It is efficient in that it need not inspect any other items of the set in order to provide the answer. It is not even needed to know how many other items there are. It has one parameter, and that is the period of 'time' over which the 'activity' is measured. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_counter_init_irqPeter Zijlstra1-0/+12
provide a way to tell lockdep about percpu_counters that are supposed to be used from irq safe contexts. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_counter_init error handlingPeter Zijlstra1-1/+7
alloc_percpu can fail, propagate that error. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_count_sum()Peter Zijlstra1-3/+3
Provide an accurate version of percpu_counter_read. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_counter_sum_positivePeter Zijlstra1-2/+2
s/percpu_counter_sum/&_positive/ Because its consitent with percpu_counter_read* Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_counter_setPeter Zijlstra1-0/+14
Provide a method to set a percpu counter to a specified value. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: make percpu_counter_add take s64Peter Zijlstra1-2/+2
percpu_counter is a s64 counter, make _add consitent. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_counter variable batchPeter Zijlstra1-3/+3
Because the current batch setup has an quadric error bound on the counter, allow for an alternative setup. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17lib: percpu_counter_addPeter Zijlstra1-2/+2
s/percpu_counter_mod/percpu_counter_add/ Because its a better name, _mod implies modulo. Signed-off-by: Peter Zijlstra <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-17swiotlb: fix map_sg failure handlingFUJITA Tomonori1-1/+1
sg list elements might not be continuous. Signed-off-by: FUJITA Tomonori <[email protected]> Signed-off-by: Jens Axboe <[email protected]>
2007-10-16Merge branch 'for-linus' of git://git.kernel.dk/data/git/linux-2.6-blockLinus Torvalds1-7/+12
* 'for-linus' of git://git.kernel.dk/data/git/linux-2.6-block: (63 commits) Fix memory leak in dm-crypt SPARC64: sg chaining support SPARC: sg chaining support PPC: sg chaining support PS3: sg chaining support IA64: sg chaining support x86-64: enable sg chaining x86-64: update pci-gart iommu to sg helpers x86-64: update nommu to sg helpers x86-64: update calgary iommu to sg helpers swiotlb: sg chaining support i386: enable sg chaining i386 dma_map_sg: convert to using sg helpers mmc: need to zero sglist on init Panic in blk_rq_map_sg() from CCISS driver remove sglist_len remove blk_queue_max_phys_segments in libata revert sg segment size ifdefs Fixup u14-34f ENABLE_SG_CHAINING qla1280: enable use_sg_chaining option ...
2007-10-16Group short-lived and reclaimable kernel allocationsMel Gorman1-2/+4
This patch marks a number of allocations that are either short-lived such as network buffers or are reclaimable such as inode allocations. When something like updatedb is called, long-lived and unmovable kernel allocations tend to be spread throughout the address space which increases fragmentation. This patch groups these allocations together as much as possible by adding a new MIGRATE_TYPE. The MIGRATE_RECLAIMABLE type is for allocations that can be reclaimed on demand, but not moved. i.e. they can be migrated by deleting them and re-reading the information from elsewhere. Signed-off-by: Mel Gorman <[email protected]> Cc: Andy Whitcroft <[email protected]> Cc: Christoph Lameter <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-16fix the max path calculation in radix-tree.cJeff Moyer1-4/+17
A while back, Nick Piggin introduced a patch to reduce the node memory usage for small files (commit cfd9b7df4abd3257c9e381b0e445817b26a51c0c): -#define RADIX_TREE_MAP_SHIFT 6 +#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) Unfortunately, he didn't take into account the fact that the calculation of the maximum path was based on an assumption of having to round up: #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) So, if CONFIG_BASE_SMALL is set, you will end up with a RADIX_TREE_MAX_PATH that is one greater than necessary. The practical upshot of this is just a bit of wasted memory (one long in the height_to_maxindex array, an extra pre-allocated radix tree node per cpu, and extra stack usage in a couple of functions), but it seems worth getting right. It's also worth noting that I never build with CONFIG_BASE_SMALL. What I did to test this was duplicate the code in a small user-space program and check the results of the calculations for max path and the contents of the height_to_maxindex array. Signed-off-by: Jeff Moyer <[email protected]> Acked-by: Nick Piggin <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-16radix-tree: use indirect bitNick Piggin1-26/+43
Rather than sign direct radix-tree pointers with a special bit, sign the indirect one that hangs off the root. This means that, given a lookup_slot operation, the invalid result will be differentiated from the valid (previously, valid results could have the bit either set or clear). This does not affect slot lookups which occur under lock -- they can never return an invalid result. Is needed in future for lockless pagecache. Signed-off-by: Nick Piggin <[email protected]> Acked-by: Peter Zijlstra <[email protected]> Cc: Hugh Dickins <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
2007-10-16radixtree: introduce radix_tree_next_hole()Fengguang Wu1-0/+36
Introduce radix_tree_next_hole(root, index, max_scan) to scan radix tree for the first hole. It will be used in interleaved readahead. The implementation is dumb and obviously correct. It can help debug(and document) the possible smart one in future. Cc: Nick Piggin <[email protected]> Signed-off-by: Fengguang Wu <[email protected]> Cc: Rusty Russell <[email protected]> Signed-off-by: Andrew Morton <[email protected]> Signed-off-by: Linus Torvalds <[email protected]>
Powered by cgit, Gruvboxed by Blaster4385.