- 09 10月, 2012 2 次提交
-
-
由 Michel Lespinasse 提交于
Patch 1 implements support for interval trees, on top of the augmented rbtree API. It also adds synthetic tests to compare the performance of interval trees vs prio trees. Short answers is that interval trees are slightly faster (~25%) on insert/erase, and much faster (~2.4 - 3x) on search. It is debatable how realistic the synthetic test is, and I have not made such measurements yet, but my impression is that interval trees would still come out faster. Patch 2 uses a preprocessor template to make the interval tree generic, and uses it as a replacement for the vma prio_tree. Patch 3 takes the other prio_tree user, kmemleak, and converts it to use a basic rbtree. We don't actually need the augmented rbtree support here because the intervals are always non-overlapping. Patch 4 removes the now-unused prio tree library. Patch 5 proposes an additional optimization to rb_erase_augmented, now providing it as an inline function so that the augmented callbacks can be inlined in. This provides an additional 5-10% performance improvement for the interval tree insert/erase benchmark. There is a maintainance cost as it exposes augmented rbtree users to some of the rbtree library internals; however I think this cost shouldn't be too high as I expect the augmented rbtree will always have much less users than the base rbtree. I should probably add a quick summary of why I think it makes sense to replace prio trees with augmented rbtree based interval trees now. One of the drivers is that we need augmented rbtrees for Rik's vma gap finding code, and once you have them, it just makes sense to use them for interval trees as well, as this is the simpler and more well known algorithm. prio trees, in comparison, seem *too* clever: they impose an additional 'heap' constraint on the tree, which they use to guarantee a faster worst-case complexity of O(k+log N) for stabbing queries in a well-balanced prio tree, vs O(k*log N) for interval trees (where k=number of matches, N=number of intervals). Now this sounds great, but in practice prio trees don't realize this theorical benefit. First, the additional constraint makes them harder to update, so that the kernel implementation has to simplify things by balancing them like a radix tree, which is not always ideal. Second, the fact that there are both index and heap properties makes both tree manipulation and search more complex, which results in a higher multiplicative time constant. As it turns out, the simple interval tree algorithm ends up running faster than the more clever prio tree. This patch: Add two test modules: - prio_tree_test measures the performance of lib/prio_tree.c, both for insertion/removal and for stabbing searches - interval_tree_test measures the performance of a library of equivalent functionality, built using the augmented rbtree support. In order to support the second test module, lib/interval_tree.c is introduced. It is kept separate from the interval_tree_test main file for two reasons: first we don't want to provide an unfair advantage over prio_tree_test by having everything in a single compilation unit, and second there is the possibility that the interval tree functionality could get some non-test users in kernel over time. Signed-off-by: NMichel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Michel Lespinasse 提交于
This small module helps measure the performance of rbtree insert and erase. Additionally, we run a few correctness tests to check that the rbtrees have all desired properties: - contains the right number of nodes in the order desired, - never two consecutive red nodes on any path, - all paths to leaf nodes have the same number of black nodes, - root node is black [akpm@linux-foundation.org: fix printk warning: sparc64 cycles_t is unsigned long] Signed-off-by: NMichel Lespinasse <walken@google.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Acked-by: NDavid Woodhouse <David.Woodhouse@intel.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Daniel Santos <daniel.santos@pobox.com> Cc: Jens Axboe <axboe@kernel.dk> Cc: "Eric W. Biederman" <ebiederm@xmission.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 31 7月, 2012 5 次提交
-
-
由 Akinobu Mita 提交于
This provides the ability to inject artifical errors to pSeries reconfig notifier chain callbacks. It is controlled through debugfs interface under /sys/kernel/debug/notifier-error-inject/pSeries-reconfig If the notifier call chain should be failed with some events notified, write the error code to "actions/<notifier event>/error". Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Cc: Pavel Machek <pavel@ucw.cz> Cc: "Rafael J. Wysocki" <rjw@sisk.pl> Cc: Greg KH <greg@kroah.com> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org> Cc: Paul Mackerras <paulus@samba.org> Cc: Michael Ellerman <michael@ellerman.id.au> Cc: Dave Jones <davej@redhat.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Akinobu Mita 提交于
This provides the ability to inject artifical errors to memory hotplug notifier chain callbacks. It is controlled through debugfs interface under /sys/kernel/debug/notifier-error-inject/memory If the notifier call chain should be failed with some events notified, write the error code to "actions/<notifier event>/error". Example: Inject memory hotplug offline error (-12 == -ENOMEM) # cd /sys/kernel/debug/notifier-error-inject/memory # echo -12 > actions/MEM_GOING_OFFLINE/error # echo offline > /sys/devices/system/memory/memoryXXX/state bash: echo: write error: Cannot allocate memory Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Cc: Pavel Machek <pavel@ucw.cz> Cc: "Rafael J. Wysocki" <rjw@sisk.pl> Cc: Greg KH <greg@kroah.com> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org> Cc: Paul Mackerras <paulus@samba.org> Cc: Michael Ellerman <michael@ellerman.id.au> Cc: Dave Jones <davej@redhat.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Akinobu Mita 提交于
This provides the ability to inject artifical errors to PM notifier chain callbacks. It is controlled through debugfs interface under /sys/kernel/debug/notifier-error-inject/pm Each of the files in "error" directory represents an event which can be failed and contains the error code. If the notifier call chain should be failed with some events notified, write the error code to the files. If the notifier call chain should be failed with some events notified, write the error code to "actions/<notifier event>/error". Example: Inject PM suspend error (-12 = -ENOMEM) # cd /sys/kernel/debug/notifier-error-inject/pm # echo -12 > actions/PM_SUSPEND_PREPARE/error # echo mem > /sys/power/state bash: echo: write error: Cannot allocate memory Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Acked-by: N"Rafael J. Wysocki" <rjw@sisk.pl> Cc: Pavel Machek <pavel@ucw.cz> Cc: Greg KH <greg@kroah.com> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org> Cc: Paul Mackerras <paulus@samba.org> Cc: Michael Ellerman <michael@ellerman.id.au> Cc: Dave Jones <davej@redhat.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Akinobu Mita 提交于
This patchset provides kernel modules that can be used to test the error handling of notifier call chain failures by injecting artifical errors to the following notifier chain callbacks. * CPU notifier * PM notifier * memory hotplug notifier * powerpc pSeries reconfig notifier Example: Inject CPU offline error (-1 == -EPERM) # cd /sys/kernel/debug/notifier-error-inject/cpu # echo -1 > actions/CPU_DOWN_PREPARE/error # echo 0 > /sys/devices/system/cpu/cpu1/online bash: echo: write error: Operation not permitted The patchset also adds cpu and memory hotplug tests to tools/testing/selftests These tests first do simple online and offline test and then do fault injection tests if notifier error injection module is available. This patch: The notifier error injection provides the ability to inject artifical errors to specified notifier chain callbacks. It is useful to test the error handling of notifier call chain failures. This adds common basic functions to define which type of events can be fail and to initialize the debugfs interface to control what error code should be returned and which event should be failed. Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Cc: Pavel Machek <pavel@ucw.cz> Cc: "Rafael J. Wysocki" <rjw@sisk.pl> Cc: Greg KH <greg@kroah.com> Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org> Cc: Paul Mackerras <paulus@samba.org> Cc: Michael Ellerman <michael@ellerman.id.au> Cc: Dave Jones <davej@redhat.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Akinobu Mita 提交于
memweight() is the function that counts the total number of bits set in memory area. Unlike bitmap_weight(), memweight() takes pointer and size in bytes to specify a memory area which does not need to be aligned to long-word boundary. [akpm@linux-foundation.org: rename `w' to `ret'] Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Cc: Anders Larsen <al@alarsen.net> Cc: Alasdair Kergon <agk@redhat.com> Cc: Laurent Pinchart <laurent.pinchart@ideasonboard.com> Cc: Mark Fasheh <mfasheh@suse.com> Cc: Joel Becker <jlbec@evilplan.org> Cc: Jan Kara <jack@suse.cz> Cc: Andreas Dilger <adilger.kernel@dilger.ca> Cc: "Theodore Ts'o" <tytso@mit.edu> Cc: Matthew Wilcox <matthew@wil.cx> Cc: Mauro Carvalho Chehab <mchehab@infradead.org> Cc: Tony Luck <tony.luck@gmail.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 23 7月, 2012 1 次提交
-
-
由 David Daney 提交于
libfdt is part of the device tree support in scripts/dtc/libfdt. For some platforms that use the Device Tree, we want to be able to edit the flattened device tree form. We don't want to burden kernel builds that do not require it, so we gate compilation of libfdt files with CONFIG_LIBFDT. So if it is needed, you need to do this in your Kconfig: select LIBFDT And in the Makefile of the code using libfdt something like: ccflags-y := -I$(src)/../../../scripts/dtc/libfdt Signed-off-by: NDavid Daney <david.daney@cavium.com> Cc: linux-mips@linux-mips.org Cc: devicetree-discuss@lists.ozlabs.org Cc: Grant Likely <grant.likely@secretlab.ca> Cc: linux-kernel@vger.kernel.org Acked-by: NRob Herring <rob.herring@calxeda.com> Signed-off-by: NRalf Baechle <ralf@linux-mips.org>
-
- 09 6月, 2012 1 次提交
-
-
由 Jan Kara 提交于
Implement code computing proportions of events of different type (like code in lib/proportions.c) but allowing periods to have different lengths. This allows us to have aging periods of fixed wallclock time which gives better proportion estimates given the hugely varying throughput of different devices - previous measuring of aging period by number of events has the problem that a reasonable period length for a system with low-end USB stick is not a reasonable period length for a system with high-end storage array resulting either in too slow proportion updates or too fluctuating proportion updates. Acked-by: NPeter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: NJan Kara <jack@suse.cz> Signed-off-by: NFengguang Wu <fengguang.wu@intel.com>
-
- 27 5月, 2012 1 次提交
-
-
由 Linus Torvalds 提交于
This adds a new generic optimized strnlen_user() function that uses the <asm/word-at-a-time.h> infrastructure to portably do efficient string handling. In many ways, strnlen is much simpler than strncpy, and in particular we can always pre-align the words we load from memory. That means that all the worries about alignment etc are a non-issue, so this one can easily be used on any architecture. You obviously do have to do the appropriate word-at-a-time.h macros. Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 25 5月, 2012 1 次提交
-
-
由 David S. Miller 提交于
To use this, an architecture simply needs to: 1) Provide a user_addr_max() implementation via asm/uaccess.h 2) Add "select GENERIC_STRNCPY_FROM_USER" to their arch Kcnfig 3) Remove the existing strncpy_from_user() implementation and symbol exports their architecture had. Signed-off-by: NDavid S. Miller <davem@davemloft.net> Acked-by: NDavid Howells <dhowells@redhat.com>
-
- 02 5月, 2012 1 次提交
-
-
由 Aneesh V 提交于
add LPDDR2 data from the JEDEC spec JESD209-2. The data includes: 1. Addressing information for LPDDR2 memories of different densities and types(S2/S4) 2. AC timing data. This data will useful for memory controller device drivers. Right now this is used by the TI EMIF SDRAM controller driver. Signed-off-by: NAneesh V <aneesh@ti.com> Reviewed-by: NSantosh Shilimkar <santosh.shilimkar@ti.com> Reviewed-by: NBenoit Cousson <b-cousson@ti.com> [santosh.shilimkar@ti.com: Moved to drivers/memory from drivers/misc] Signed-off-by: NSantosh Shilimkar <santosh.shilimkar@ti.com> Tested-by: NLokesh Vutla <lokeshvutla@ti.com> Signed-off-by: NGreg Kroah-Hartman <gregkh@linuxfoundation.org>
-
- 21 4月, 2012 1 次提交
-
-
由 Wolfram Sang 提交于
MX23/28 use IP cores which follow a register layout I have first seen on STMP3xxx SoCs. In this layout, every register actually has four u32: 1.) to store a value directly 2.) a SET register where every 1-bit sets the corresponding bit, others are unaffected 3.) same with a CLR register 4.) same with a TOG (toggle) register Also, the 2 MSBs in register 0 are always the same and can be used to reset the IP core. All this is strictly speaking not mach-specific (but IP core specific) and, thus, doesn't need to be in mach-mxs/include. At least mx6 also uses IP cores following this stmp-style. So: Introduce a stmp-style device, put the code and defines for that in a public place (lib/), and let drivers for stmp-style devices select that code. To avoid regressions and ease reviewing, the actual code is simply copied from mach-mxs. It definately wants updates, but those need a seperate patch series. Voila, mach dependency gone, reusable code introduced. Note that I didn't remove the duplicated code from mach-mxs yet, first the drivers have to be converted. Signed-off-by: NWolfram Sang <w.sang@pengutronix.de> Acked-by: NShawn Guo <shawn.guo@linaro.org> Acked-by: NDong Aisheng <dong.aisheng@linaro.org>
-
- 02 2月, 2012 1 次提交
-
-
由 David Miller 提交于
Both sparc 32-bit's software divide assembler and MPILIB provide clz_tab[] with identical contents. Break it out into a seperate object file and select it when SPARC32 or MPILIB is set. Reported-by: NAl Viro <viro@ZenIV.linux.org.uk> Signed-off-by: NDavid S. Miller <davem@davemloft.net> Signed-off-by: NJames Morris <jmorris@namei.org>
-
- 18 1月, 2012 1 次提交
-
-
由 Dmitry Kasatkin 提交于
It was reported that DIGSIG is confusing name for digital signature module. It was suggested to rename DIGSIG to SIGNATURE. Requested-by: NLinus Torvalds <torvalds@linux-foundation.org> Suggested-by: NPavel Machek <pavel@ucw.cz> Signed-off-by: NDmitry Kasatkin <dmitry.kasatkin@intel.com> Signed-off-by: NJames Morris <jmorris@namei.org>
-
- 14 12月, 2011 1 次提交
-
-
由 Peter Zijlstra 提交于
These are tiny functions, there's no point in having them out-of-line. Cc: Alexey Dobriyan <adobriyan@gmail.com> Cc: Eric Dumazet <eric.dumazet@gmail.com> Cc: Ingo Molnar <mingo@elte.hu> Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl> Link: http://lkml.kernel.org/n/tip-8eccvi2ur2fzgi00xdjlbf5z@git.kernel.orgSigned-off-by: NGreg Kroah-Hartman <gregkh@suse.de>
-
- 30 11月, 2011 1 次提交
-
-
由 Tom Herbert 提交于
Implementation of dynamic queue limits (dql). This is a libary which allows a queue limit to be dynamically managed. The goal of dql is to set the queue limit, number of objects to the queue, to be minimized without allowing the queue to be starved. dql would be used with a queue which has these properties: 1) Objects are queued up to some limit which can be expressed as a count of objects. 2) Periodically a completion process executes which retires consumed objects. 3) Starvation occurs when limit has been reached, all queued data has actually been consumed but completion processing has not yet run, so queuing new data is blocked. 4) Minimizing the amount of queued data is desirable. A canonical example of such a queue would be a NIC HW transmit queue. The queue limit is dynamic, it will increase or decrease over time depending on the workload. The queue limit is recalculated each time completion processing is done. Increases occur when the queue is starved and can exponentially increase over successive intervals. Decreases occur when more data is being maintained in the queue than needed to prevent starvation. The number of extra objects, or "slack", is measured over successive intervals, and to avoid hysteresis the limit is only reduced by the miminum slack seen over a configurable time period. dql API provides routines to manage the queue: - dql_init is called to intialize the dql structure - dql_reset is called to reset dynamic values - dql_queued called when objects are being enqueued - dql_avail returns availability in the queue - dql_completed is called when objects have be consumed in the queue Configuration consists of: - max_limit, maximum limit - min_limit, minimum limit - slack_hold_time, time to measure instances of slack before reducing queue limit Signed-off-by: NTom Herbert <therbert@google.com> Acked-by: NEric Dumazet <eric.dumazet@gmail.com> Signed-off-by: NDavid S. Miller <davem@davemloft.net>
-
- 29 11月, 2011 1 次提交
-
-
由 Michael S. Tsirkin 提交于
Many architectures want a generic pci_iomap but not the rest of iomap.c. Split that to a separate .c file and add a new config symbol. select automatically by GENERIC_IOMAP. Signed-off-by: NMichael S. Tsirkin <mst@redhat.com>
-
- 09 11月, 2011 2 次提交
-
-
由 Dmitry Kasatkin 提交于
This patch implements RSA digital signature verification using GnuPG library. The format of the signature and the public key is defined by their respective headers. The signature header contains version information, algorithm, and keyid, which was used to generate the signature. The key header contains version and algorythim type. The payload of the signature and the key are multi-precision integers. The signing and key management utilities evm-utils provide functionality to generate signatures and load keys into the kernel keyring. When the key is added to the kernel keyring, the keyid defines the name of the key. Signed-off-by: NDmitry Kasatkin <dmitry.kasatkin@intel.com> Acked-by: NMimi Zohar <zohar@us.ibm.com>
-
由 Dmitry Kasatkin 提交于
Adds the multi-precision-integer maths library which was originally taken from GnuPG and ported to the kernel by (among others) David Howells. This version is taken from Fedora kernel 2.6.32-71.14.1.el6. The difference is that checkpatch reported errors and warnings have been fixed. This library is used to implemenet RSA digital signature verification used in IMA/EVM integrity protection subsystem. Due to patch size limitation, the patch is divided into 4 parts. Signed-off-by: NDmitry Kasatkin <dmitry.kasatkin@intel.com>
-
- 04 10月, 2011 1 次提交
-
-
由 Huang Ying 提交于
Because llist code will be used in performance critical scheduler code path, make llist_add() and llist_del_all() inline to avoid function calling overhead and related 'glue' overhead. Signed-off-by: NHuang Ying <ying.huang@intel.com> Acked-by: NMathieu Desnoyers <mathieu.desnoyers@efficios.com> Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl> Link: http://lkml.kernel.org/r/1315461646-1379-2-git-send-email-ying.huang@intel.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
-
- 31 8月, 2011 1 次提交
-
-
由 Geert Uytterhoeven 提交于
If there are no builtin users of find_next_bit_le() and find_next_zero_bit_le(), these functions are not present in the kernel image, causing m68k allmodconfig to fail with: ERROR: "find_next_zero_bit_le" [fs/ufs/ufs.ko] undefined! ERROR: "find_next_bit_le" [fs/udf/udf.ko] undefined! ... This started to happen after commit 171d809d ("m68k: merge mmu and non-mmu bitops.h"), as m68k had its own inline versions before. commit 63e424c8 ("arch: remove CONFIG_GENERIC_FIND_{NEXT_BIT, BIT_LE, LAST_BIT}") added find_last_bit.o to obj-y (so it's always included), but find_next_bit.o to lib-y (so it gets removed by the linker if there are no builtin users). Signed-off-by: NGeert Uytterhoeven <geert@linux-m68k.org> Cc: Akinobu Mita <akinobu.mita@gmail.com> Cc: Greg Ungerer <gerg@uclinux.org> Cc: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 07 8月, 2011 1 次提交
-
-
由 David S. Miller 提交于
We are going to use this for TCP/IP sequence number and fragment ID generation. Signed-off-by: NDavid S. Miller <davem@davemloft.net>
-
- 03 8月, 2011 1 次提交
-
-
由 Huang Ying 提交于
Cmpxchg is used to implement adding new entry to the list, deleting all entries from the list, deleting first entry of the list and some other operations. Because this is a single list, so the tail can not be accessed in O(1). If there are multiple producers and multiple consumers, llist_add can be used in producers and llist_del_all can be used in consumers. They can work simultaneously without lock. But llist_del_first can not be used here. Because llist_del_first depends on list->first->next does not changed if list->first is not changed during its operation, but llist_del_first, llist_add, llist_add (or llist_del_all, llist_add, llist_add) sequence in another consumer may violate that. If there are multiple producers and one consumer, llist_add can be used in producers and llist_del_all or llist_del_first can be used in the consumer. This can be summarized as follow: | add | del_first | del_all add | - | - | - del_first | | L | L del_all | | | - Where "-" stands for no lock is needed, while "L" stands for lock is needed. The list entries deleted via llist_del_all can be traversed with traversing function such as llist_for_each etc. But the list entries can not be traversed safely before deleted from the list. The order of deleted entries is from the newest to the oldest added one. If you want to traverse from the oldest to the newest, you must reverse the order by yourself before traversing. The basic atomic operation of this list is cmpxchg on long. On architectures that don't have NMI-safe cmpxchg implementation, the list can NOT be used in NMI handler. So code uses the list in NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. Signed-off-by: NHuang Ying <ying.huang@intel.com> Reviewed-by: NAndi Kleen <ak@linux.intel.com> Reviewed-by: NMathieu Desnoyers <mathieu.desnoyers@efficios.com> Cc: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: NLen Brown <len.brown@intel.com>
-
- 04 6月, 2011 2 次提交
-
-
由 Arend van Spriel 提交于
The brcm80211 driver in the staging tree has a cordic function to determine cosine and sine for a given angle. Feedback received from John Linville suggested that these kind of functions should be made available to others as a library function in the kernel tree. The b43 driver also has a cordic angle calculation implemented. Cc: linux-kernel@vger.kernel.org Cc: linux-wireless@vger.kernel.org Cc: "John W. Linville" <linville@tuxdriver.com> Cc: Greg Kroah-Hartman <gregkh@suse.de> Cc: Dan Carpenter <error27@gmail.com> Cc: Randy Dunlap <rdunlap@xenotime.net> Cc: Larry Finger <Larry.Finger@lwfinger.net> Reviewed-by: NRoland Vossen <rvossen@broadcom.com> Reviewed-by: NHenry Ptasinski <henryp@broadcom.com> Reviewed-by: NFranky (Zhenhui) Lin <frankyl@broadcom.com> Signed-off-by: NArend van Spriel <arend@broadcom.com> Signed-off-by: NJohn W. Linville <linville@tuxdriver.com>
-
由 Arend van Spriel 提交于
The brcm80211 driver in staging tree uses a crc8 function. Based on feedback from John Linville to move this to lib directory, the linux source has been searched. Although there is currently only one other kernel driver using this algorithm (ie. drivers/ssb) we are providing this as a library function for others to use. Cc: linux-kernel@vger.kernel.org Cc: linux-wireless@vger.kernel.org Cc: Dan Carpenter <error27@gmail.com> Cc: George Spelvin <linux@horizon.com> Cc: Randy Dunlap <rdunlap@xenotime.net> Reviewed-by: NHenry Ptasinski <henryp@broadcom.com> Reviewed-by: NRoland Vossen <rvossen@broadcom.com> Reviewed-by: N"Franky (Zhenhui) Lin" <frankyl@broadcom.com> Signed-off-by: NArend van Spriel <arend@broadcom.com> Signed-off-by: NJohn W. Linville <linville@tuxdriver.com>
-
- 27 5月, 2011 1 次提交
-
-
由 Akinobu Mita 提交于
By the previous style change, CONFIG_GENERIC_FIND_NEXT_BIT, CONFIG_GENERIC_FIND_BIT_LE, and CONFIG_GENERIC_FIND_LAST_BIT are not used to test for existence of find bitops anymore. Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Acked-by: NGreg Ungerer <gerg@uclinux.org> Cc: Arnd Bergmann <arnd@arndb.de> Cc: Russell King <linux@arm.linux.org.uk> Cc: Martin Schwidefsky <schwidefsky@de.ibm.com> Cc: Heiko Carstens <heiko.carstens@de.ibm.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 19 5月, 2011 1 次提交
-
-
由 Tim Abbott 提交于
There a large number hand-coded binary searches in the kernel (run "git grep search | grep binary" to find many of them). Since in my experience, hand-coding binary searches can be error-prone, it seems worth cleaning this up by providing a generic binary search function. This generic binary search implementation comes from Ksplice. It has the same basic API as the C library bsearch() function. Ksplice uses it in half a dozen places with 4 different comparison functions, and I think our code is substantially cleaner because of this. Signed-off-by: NTim Abbott <tabbott@ksplice.com> Extra-bikeshedding-by: NAlan Jenkins <alan-jenkins@tuffmail.co.uk> Extra-bikeshedding-by: NAndré Goddard Rosa <andre.goddard@gmail.com> Extra-bikeshedding-by: NRusty Russell <rusty@rustcorp.com.au> Signed-off-by: NRusty Russell <rusty@rustcorp.com.au> Signed-off-by: NAlessio Igor Bogani <abogani@kernel.org> Signed-off-by: NRusty Russell <rusty@rustcorp.com.au>
-
- 24 3月, 2011 1 次提交
-
-
由 Akinobu Mita 提交于
This introduces CONFIG_GENERIC_FIND_BIT_LE to tell whether to use generic implementation of find_*_bit_le() in lib/find_next_bit.c or not. For now we select CONFIG_GENERIC_FIND_BIT_LE for all architectures which enable CONFIG_GENERIC_FIND_NEXT_BIT. But m68knommu wants to define own faster find_next_zero_bit_le() and continues using generic find_next_{,zero_}bit(). (CONFIG_GENERIC_FIND_NEXT_BIT and !CONFIG_GENERIC_FIND_BIT_LE) Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com> Cc: Greg Ungerer <gerg@uclinux.org> Cc: Arnd Bergmann <arnd@arndb.de> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 23 3月, 2011 1 次提交
-
-
由 Alexey Dobriyan 提交于
1. simple_strto*() do not contain overflow checks and crufty, libc way to indicate failure. 2. strict_strto*() also do not have overflow checks but the name and comments pretend they do. 3. Both families have only "long long" and "long" variants, but users want strtou8() 4. Both "simple" and "strict" prefixes are wrong: Simple doesn't exactly say what's so simple, strict should not exist because conversion should be strict by default. The solution is to use "k" prefix and add convertors for more types. Enter kstrtoull() kstrtoll() kstrtoul() kstrtol() kstrtouint() kstrtoint() kstrtou64() kstrtos64() kstrtou32() kstrtos32() kstrtou16() kstrtos16() kstrtou8() kstrtos8() Include runtime testsuite (somewhat incomplete) as well. strict_strto*() become deprecated, stubbed to kstrto*() and eventually will be removed altogether. Use kstrto*() in code today! Note: on some archs _kstrtoul() and _kstrtol() are left in tree, even if they'll be unused at runtime. This is temporarily solution, because I don't want to hardcode list of archs where these functions aren't needed. Current solution with sizeof() and __alignof__ at least always works. Signed-off-by: NAlexey Dobriyan <adobriyan@gmail.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 11 3月, 2011 1 次提交
-
-
由 Ivan Djelic 提交于
This is a new software BCH encoding/decoding library, similar to the shared Reed-Solomon library. Binary BCH (Bose-Chaudhuri-Hocquenghem) codes are widely used to correct errors in NAND flash devices requiring more than 1-bit ecc correction; they are generally better suited for NAND flash than RS codes because NAND bit errors do not occur in bursts. Latest SLC NAND devices typically require at least 4-bit ecc protection per 512 bytes block. This library provides software encoding/decoding, but may also be used with ASIC/SoC hardware BCH engines to perform error correction. It is being currently used for this purpose on an OMAP3630 board (4bit/8bit HW BCH). It has also been used to decode raw dumps of NAND devices with on-die BCH ecc engines (e.g. Micron 4bit ecc SLC devices). Latest NAND devices (including SLC) can exhibit high error rates (typically a dozen or more bitflips per hour during stress tests); in order to minimize the performance impact of error correction, this library implements recently developed algorithms for fast polynomial root finding (see bch.c header for details) instead of the traditional exhaustive Chien root search; a few performance figures are provided below: Platform: arm926ejs @ 468 MHz, 32 KiB icache, 16 KiB dcache BCH ecc : 4-bit per 512 bytes Encoding average throughput: 250 Mbits/s Error correction time (compared with Chien search): average worst average (Chien) worst (Chien) ---------------------------------------------------------- 1 bit 8.5 µs 11 µs 200 µs 383 µs 2 bit 9.7 µs 12.5 µs 477 µs 728 µs 3 bit 18.1 µs 20.6 µs 758 µs 1010 µs 4 bit 19.5 µs 23 µs 1028 µs 1280 µs In the above figures, "worst" is meant in terms of error pattern, not in terms of cache miss / page faults effects (not taken into account here). The library has been extensively tested on the following platforms: x86, x86_64, arm926ejs, omap3630, qemu-ppc64, qemu-mips. Signed-off-by: NIvan Djelic <ivan.djelic@parrot.com> Signed-off-by: NDavid Woodhouse <David.Woodhouse@intel.com>
-
- 05 3月, 2011 1 次提交
-
-
由 Arnd Bergmann 提交于
This removes the implementation of the big kernel lock, at last. A lot of people have worked on this in the past, I so the credit for this patch should be with everyone who participated in the hunt. The names on the Cc list are the people that were the most active in this, according to the recorded git history, in alphabetical order. Signed-off-by: NArnd Bergmann <arnd@arndb.de> Acked-by: NAlan Cox <alan@linux.intel.com> Cc: Alessio Igor Bogani <abogani@texware.it> Cc: Al Viro <viro@zeniv.linux.org.uk> Cc: Andrew Hendry <andrew.hendry@gmail.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Christoph Hellwig <hch@infradead.org> Cc: Eric W. Biederman <ebiederm@xmission.com> Cc: Frederic Weisbecker <fweisbec@gmail.com> Cc: Hans Verkuil <hverkuil@xs4all.nl> Acked-by: NIngo Molnar <mingo@elte.hu> Cc: Jan Blunck <jblunck@infradead.org> Cc: John Kacur <jkacur@redhat.com> Cc: Jonathan Corbet <corbet@lwn.net> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Matthew Wilcox <matthew@wil.cx> Cc: Oliver Neukum <oliver@neukum.org> Cc: Paul Menage <menage@google.com> Acked-by: NThomas Gleixner <tglx@linutronix.de> Cc: Trond Myklebust <Trond.Myklebust@netapp.com>
-
- 25 1月, 2011 1 次提交
-
-
由 Ben Hutchings 提交于
When initiating I/O on a multiqueue and multi-IRQ device, we may want to select a queue for which the response will be handled on the same or a nearby CPU. This requires a reverse-map of IRQ affinity. Add library functions to support a generic reverse-mapping from CPUs to objects with affinity and the specific case where the objects are IRQs. Signed-off-by: NBen Hutchings <bhutchings@solarflare.com> Signed-off-by: NDavid S. Miller <davem@davemloft.net>
-
- 14 1月, 2011 3 次提交
-
-
由 Lasse Collin 提交于
This implements the API defined in <linux/decompress/generic.h> which is used for kernel, initramfs, and initrd decompression. This patch together with the first patch is enough for XZ-compressed initramfs and initrd; XZ-compressed kernel will need arch-specific changes. The buffering requirements described in decompress_unxz.c are stricter than with gzip, so the relevant changes should be done to the arch-specific code when adding support for XZ-compressed kernel. Similarly, the heap size in arch-specific pre-boot code may need to be increased (30 KiB is enough). The XZ decompressor needs memmove(), memeq() (memcmp() == 0), and memzero() (memset(ptr, 0, size)), which aren't available in all arch-specific pre-boot environments. I'm including simple versions in decompress_unxz.c, but a cleaner solution would naturally be nicer. Signed-off-by: NLasse Collin <lasse.collin@tukaani.org> Cc: "H. Peter Anvin" <hpa@zytor.com> Cc: Alain Knaff <alain@knaff.lu> Cc: Albin Tonnerre <albin.tonnerre@free-electrons.com> Cc: Phillip Lougher <phillip@lougher.demon.co.uk> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 Lasse Collin 提交于
In userspace, the .lzma format has become mostly a legacy file format that got superseded by the .xz format. Similarly, LZMA Utils was superseded by XZ Utils. These patches add support for XZ decompression into the kernel. Most of the code is as is from XZ Embedded <http://tukaani.org/xz/embedded.html>. It was written for the Linux kernel but is usable in other projects too. Advantages of XZ over the current LZMA code in the kernel: - Nice API that can be used by other kernel modules; it's not limited to kernel, initramfs, and initrd decompression. - Integrity check support (CRC32) - BCJ filters improve compression of executable code on certain architectures. These together with LZMA2 can produce a few percent smaller kernel or Squashfs images than plain LZMA without making the decompression slower. This patch: Add the main decompression code (xz_dec), testing module (xz_dec_test), wrapper script (xz_wrap.sh) for the xz command line tool, and documentation. The xz_dec module is enough to have a usable XZ decompressor e.g. for Squashfs. Signed-off-by: NLasse Collin <lasse.collin@tukaani.org> Cc: "H. Peter Anvin" <hpa@zytor.com> Cc: Alain Knaff <alain@knaff.lu> Cc: Albin Tonnerre <albin.tonnerre@free-electrons.com> Cc: Phillip Lougher <phillip@lougher.demon.co.uk> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
由 David Rientjes 提交于
Alex said: I want to use flex_array to store a sparse array of ATM cell re-assembly buffers for my ATM over Ethernet driver. Using the per-vcc user_back structure causes problems when stacked with things like br2684. Add EXPORT_SYMBOL() for all publically accessible flex array functions and move to obj-y so that modules may use this library. Signed-off-by: NDavid Rientjes <rientjes@google.com> Cc: Dave Hansen <dave@linux.vnet.ibm.com> Cc: Paul Mundt <lethal@linux-sh.org> Reported-by: NAlex Bennee <kernel-hacker@bennee.com> Signed-off-by: NAndrew Morton <akpm@linux-foundation.org> Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
-
- 11 12月, 2010 1 次提交
-
-
由 John Stultz 提交于
Thomas pointed out a namespace collision between the new timerlist infrastructure I introduced and the existing timer_list.c So to avoid confusion, I've renamed the timerlist infrastructure to timerqueue. Reported-by: NThomas Gleixner <tglx@linutronix.de> Signed-off-by: NJohn Stultz <john.stultz@linaro.org>
-
- 03 12月, 2010 1 次提交
-
-
由 John Stultz 提交于
The timerlist infrastructure is a thin layer over the rbtree code that implements a simple list of timers sorted by an expires value, and a getnext function that provides a pointer to the earliest timer. This infrastructure allows drivers and other kernel infrastructure to easily implement timers without duplicating code. Signed-off-by: NJohn Stultz <john.stultz@linaro.org> LKML Reference: <1290136329-18291-2-git-send-email-john.stultz@linaro.org> Reviewed-by: NThomas Gleixner <tglx@linutronix.de> CC: Alessandro Zummo <a.zummo@towertech.it> CC: Thomas Gleixner <tglx@linutronix.de> CC: Richard Cochran <richardcochran@gmail.com>
-
- 19 11月, 2010 1 次提交
-
-
由 Bruno Randolf 提交于
This adds generic functions for calculating Exponentially Weighted Moving Averages (EWMA). This implementation makes use of a structure which keeps the EWMA parameters and a scaled up internal representation to reduce rounding errors. The original idea for this implementation came from the rt2x00 driver (rt2x00link.c). I would like to use it in several places in the mac80211 and ath5k code and I hope it can be useful in many other places in the kernel code. Signed-off-by: NBruno Randolf <br1@einfach.org> Reviewed-by: NKOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Signed-off-by: NJohn W. Linville <linville@tuxdriver.com>
-
- 14 7月, 2010 1 次提交
-
-
由 Yinghai Lu 提交于
via following scripts FILES=$(find * -type f | grep -vE 'oprofile|[^K]config') sed -i \ -e 's/lmb/memblock/g' \ -e 's/LMB/MEMBLOCK/g' \ $FILES for N in $(find . -name lmb.[ch]); do M=$(echo $N | sed 's/lmb/memblock/g') mv $N $M done and remove some wrong change like lmbench and dlmb etc. also move memblock.c from lib/ to mm/ Suggested-by: NIngo Molnar <mingo@elte.hu> Acked-by: N"H. Peter Anvin" <hpa@zytor.com> Acked-by: NBenjamin Herrenschmidt <benh@kernel.crashing.org> Acked-by: NLinus Torvalds <torvalds@linux-foundation.org> Signed-off-by: NYinghai Lu <yinghai@kernel.org> Signed-off-by: NBenjamin Herrenschmidt <benh@kernel.crashing.org>
-