summaryrefslogtreecommitdiffstats
path: root/lib/Kconfig
Commit message (Collapse)AuthorAgeFilesLines
* Merge branch 'generic-string-functions'Linus Torvalds2012-05-261-0/+3
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This makes <asm/word-at-a-time.h> actually live up to its promise of allowing architectures to help tune the string functions that do their work a word at a time. David had already taken the x86 strncpy_from_user() function, modified it to work on sparc, and then done the extra work to make it generically useful. This then expands on that work by making x86 use that generic version, completing the circle. But more importantly, it fixes up the word-at-a-time interfaces so that it's now easy to also support things like strnlen_user(), and pretty much most random string functions. David reports that it all works fine on sparc, and Jonas Bonn reported that an earlier version of this worked on OpenRISC too. It's pretty easy for architectures to add support for this and just replace their private versions with the generic code. * generic-string-functions: sparc: use the new generic strnlen_user() function x86: use the new generic strnlen_user() function lib: add generic strnlen_user() function word-at-a-time: make the interfaces truly generic x86: use generic strncpy_from_user routine
| * lib: add generic strnlen_user() functionLinus Torvalds2012-05-261-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Linus Torvalds <torvalds@linux-foundation.org>
* | Merge tag 'stmp-dev' of ↵Linus Torvalds2012-05-261-0/+3
|\ \ | |/ |/| | | | | | | | | | | | | | | | | | | | | | | | | | | git://git.kernel.org/pub/scm/linux/kernel/git/arm/arm-soc Pull arm-soc stmp-dev library code from Olof Johansson: "A number of devices are using a common register layout, this adds support code for it in lib/stmp_device.c so we do not need to duplicate it in each driver." Fix up trivial conflicts in drivers/i2c/busses/i2c-mxs.c and lib/Makefile * tag 'stmp-dev' of git://git.kernel.org/pub/scm/linux/kernel/git/arm/arm-soc: i2c: mxs: use global reset function lib: add support for stmp-style devices
| * lib: add support for stmp-style devicesWolfram Sang2012-04-201-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Wolfram Sang <w.sang@pengutronix.de> Acked-by: Shawn Guo <shawn.guo@linaro.org> Acked-by: Dong Aisheng <dong.aisheng@linaro.org>
* | Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparcLinus Torvalds2012-05-241-0/+3
|\ \ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Pull sparc changes from David S. Miller: "This has the generic strncpy_from_user() implementation architectures can now use, which we've been developing on linux-arch over the past few days. For good measure I ran both a 32-bit and a 64-bit glibc testsuite run, and the latter of which pointed out an adjustment I needed to make to sparc's user_addr_max() definition. Linus, you were right, STACK_TOP was not the right thing to use, even on sparc itself :-) From Sam Ravnborg, we have a conversion of sparc32 over to the common alloc_thread_info_node(), since the aspect which originally blocked our doing so (sun4c) has been removed." Fix up trivial arch/sparc/Kconfig and lib/Makefile conflicts. * git://git.kernel.org/pub/scm/linux/kernel/git/davem/sparc: sparc: Fix user_addr_max() definition. lib: Sparc's strncpy_from_user is generic enough, move under lib/ kernel: Move REPEAT_BYTE definition into linux/kernel.h sparc: Increase portability of strncpy_from_user() implementation. sparc: Optimize strncpy_from_user() zero byte search. sparc: Add full proper error handling to strncpy_from_user(). sparc32: use the common implementation of alloc_thread_info_node()
| * | lib: Sparc's strncpy_from_user is generic enough, move under lib/David S. Miller2012-05-241-0/+3
| |/ | | | | | | | | | | | | | | | | | | | | | | | | | | 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: David S. Miller <davem@davemloft.net> Acked-by: David Howells <dhowells@redhat.com>
* | ddr: add LPDDR2 data from JESD209-2Aneesh V2012-05-021-0/+8
|/ | | | | | | | | | | | | | | | | | | | | 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: Aneesh V <aneesh@ti.com> Reviewed-by: Santosh Shilimkar <santosh.shilimkar@ti.com> Reviewed-by: Benoit Cousson <b-cousson@ti.com> [santosh.shilimkar@ti.com: Moved to drivers/memory from drivers/misc] Signed-off-by: Santosh Shilimkar <santosh.shilimkar@ti.com> Tested-by: Lokesh Vutla <lokeshvutla@ti.com> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
* crc32: add help text for the algorithm select optionDarrick J. Wong2012-03-281-0/+4
| | | | | | | | | Add help text to the crc32 algorithm selection option in Kconfig. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Reported-by: Stefan Richter <stefanr@s5r6.in-berlin.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* Merge branch 'for-linus-3.4-rc1' of ↵Linus Torvalds2012-03-271-0/+5
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | git://git.kernel.org/pub/scm/linux/kernel/git/rw/uml Pull UML changes from Richard Weinberger: "Mostly bug fixes and cleanups" * 'for-linus-3.4-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/rw/uml: (35 commits) um: Update defconfig um: Switch to large mcmodel on x86_64 MTD: Relax dependencies um: Wire CONFIG_GENERIC_IO up um: Serve io_remap_pfn_range() Introduce CONFIG_GENERIC_IO um: allow SUBARCH=x86 um: most of the SUBARCH uses can be killed um: deadlock in line_write_interrupt() um: don't bother trying to rebuild CHECKFLAGS for USER_OBJS um: use the right ifdef around exports in user_syms.c um: a bunch of headers can be killed by using generic-y um: ptrace-generic.h doesn't need user.h um: kill HOST_TASK_PID um: remove pointless include of asm/fixmap.h from asm/pgtable.h um: asm-offsets.h might as well come from underlying arch... um: merge processor_{32,64}.h a bit... um: switch close_chan() to struct line um: race fix: initialize delayed_work *before* registering IRQ um: line->have_irq is never checked... ...
| * Introduce CONFIG_GENERIC_IORichard Weinberger2012-03-251-0/+5
| | | | | | | | | | | | | | | | | | | | There are situations where CONFIG_HAS_IOMEM is too restrictive. For example CONFIG_MTD_NAND_NANDSIM depends on CONFIG_HAS_IOMEM but it works perfectly fine if an architecture without io memory just includes asm-generic/io.h or implements everything defined in it. UML is such a corner case. Signed-off-by: Richard Weinberger <richard@nod.at>
* | crc32: select an algorithm via KconfigDarrick J. Wong2012-03-231-0/+43
| | | | | | | | | | | | | | | | | | Allow the kernel builder to choose a crc32* algorithm for the kernel. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Cc: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* | crc32: bolt on crc32cDarrick J. Wong2012-03-231-4/+4
| | | | | | | | | | | | | | | | | | | | | | Reuse the existing crc32 code to stamp out a crc32c implementation. Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Cc: Herbert Xu <herbert@gondor.apana.org.au> Cc: Bob Pearson <rpearson@systemfabricworks.com> Cc: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* | crc32: simplify unit test codeBob Pearson2012-03-231-0/+10
|/ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Replace the unit test provided in crc32.c, which doesn't have a makefile and doesn't compile with current headers, with a simpler self test routine that also gives a measure of performance and runs at module init time. The self test option can be enabled through a configuration option CONFIG_CRC32_SELFTEST. The test stresses the pre and post loops and is thus not very realistic since actual uses will likely have addresses and lengths that are at least 4 byte aligned. However, the main loop is long enough so that the performance is dominated by that loop. The expected values for crc32_le and crc32_be were generated with the original version of crc32.c using CRC_BITS_LE = 8 and CRC_BITS_BE = 8. These values were then used to check all the values of the BITS parameters in both the original and new versions. The performance results show some variability from run to run in spite of attempts to both warm the cache and reduce the amount of OS noise by limiting interrutps during the test. To get comparable results and to analyse options wrt performance the best time reported over a small sample of runs has been taken. [djwong@us.ibm.com: Minor changelog tweaks] Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com> Signed-off-by: Darrick J. Wong <djwong@us.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* Merge tag 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mst/vhostLinus Torvalds2012-02-071-0/+3
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | arch: fix ioport mapping on mips,sh Kevin Cernekee reported that recent cleanup that replaced pci_iomap with a generic function failed to take into account the differences in io port handling on mips and sh architectures. Rather than revert the changes reintroducing the code duplication, this patchset fixes this by adding ability for architectures to override ioport mapping for pci devices. Signed-off-by: Michael S. Tsirkin <mst@redhat.com> * tag 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mst/vhost: sh: use the the PCI channels's io_map_base mips: use the the PCI controller's io_map_base lib: add NO_GENERIC_PCI_IOPORT_MAP
| * lib: add NO_GENERIC_PCI_IOPORT_MAPMichael S. Tsirkin2012-01-311-0/+3
| | | | | | | | | | | | | | | | | | | | | | Some architectures need to override the way IO port mapping is done on PCI devices. Supply a generic macro that calls ioport_map, and make it possible for architectures to override. Signed-off-by: Michael S. Tsirkin <mst@redhat.com> Acked-by: Arnd Bergmann <arnd@arndb.de>
* | lib: Fix multiple definitions of clz_tabDavid Miller2012-02-021-0/+4
|/ | | | | | | | | | | | 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: Al Viro <viro@ZenIV.linux.org.uk> Signed-off-by: David S. Miller <davem@davemloft.net> Signed-off-by: James Morris <jmorris@namei.org>
* lib: Removed MPILIB, MPILIB_EXTRA, and SIGNATURE promptsDmitry Kasatkin2012-01-181-3/+3
| | | | | | | | | As modules are expected to select MPILIB, MPILIB_EXTRA, and SIGNATURE, removed Kconfig prompts. Requested-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com> Signed-off-by: James Morris <jmorris@namei.org>
* lib: MPILIB Kconfig description updateDmitry Kasatkin2012-01-181-5/+3
| | | | | | | | | It was reported that description of the MPILIB_EXTRA is confusing. Indeed it was copy-paste typo. It is fixed here. Reported-by: Valdis Kletnieks <Valdis.Kletnieks@vt.edu> Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com> Signed-off-by: James Morris <jmorris@namei.org>
* lib: digital signature dependency fixDmitry Kasatkin2012-01-181-1/+2
| | | | | | | | | | | | | | | Randy Dunlap reported build break: ERROR: "crypto_alloc_shash" [lib/digsig.ko] undefined! ERROR: "crypto_shash_final" [lib/digsig.ko] undefined! ERROR: "crypto_shash_update" [lib/digsig.ko] undefined! ERROR: "crypto_destroy_tfm" [lib/digsig.ko] undefined! Added CRYPTO dependency and selected SHA1 algorithm. Reported-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com> Signed-off-by: James Morris <jmorris@namei.org>
* lib: digital signature config option name changeDmitry Kasatkin2012-01-181-1/+1
| | | | | | | | | | It was reported that DIGSIG is confusing name for digital signature module. It was suggested to rename DIGSIG to SIGNATURE. Requested-by: Linus Torvalds <torvalds@linux-foundation.org> Suggested-by: Pavel Machek <pavel@ucw.cz> Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com> Signed-off-by: James Morris <jmorris@namei.org>
* Merge branch 'for-linus' of git://selinuxproject.org/~jmorris/linux-securityLinus Torvalds2012-01-101-0/+25
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 'for-linus' of git://selinuxproject.org/~jmorris/linux-security: (32 commits) ima: fix invalid memory reference ima: free duplicate measurement memory security: update security_file_mmap() docs selinux: Casting (void *) value returned by kmalloc is useless apparmor: fix module parameter handling Security: tomoyo: add .gitignore file tomoyo: add missing rcu_dereference() apparmor: add missing rcu_dereference() evm: prevent racing during tfm allocation evm: key must be set once during initialization mpi/mpi-mpow: NULL dereference on allocation failure digsig: build dependency fix KEYS: Give key types their own lockdep class for key->sem TPM: fix transmit_cmd error logic TPM: NSC and TIS drivers X86 dependency fix TPM: Export wait_for_stat for other vendor specific drivers TPM: Use vendor specific function for status probe tpm_tis: add delay after aborting command tpm_tis: Check return code from getting timeouts/durations tpm: Introduce function to poll for result of self test ... Fix up trivial conflict in lib/Makefile due to addition of CONFIG_MPI and SIGSIG next to CONFIG_DQL addition.
| * digsig: build dependency fixDmitry Kasatkin2011-11-221-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fix build errors by adding Kconfig dependency on KEYS. CRYPTO dependency removed. CC security/integrity/digsig.o security/integrity/digsig.c: In function ?integrity_digsig_verify?: security/integrity/digsig.c:38:4: error: implicit declaration of function ?request_key? security/integrity/digsig.c:38:17: error: ?key_type_keyring? undeclared (first use in this function) security/integrity/digsig.c:38:17: note: each undeclared identifier is reported only once for each function it appears in make[2]: *** [security/integrity/digsig.o] Error 1 Reported-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com> Signed-off-by: James Morris <jmorris@namei.org>
| * crypto: digital signature verification supportDmitry Kasatkin2011-11-091-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Dmitry Kasatkin <dmitry.kasatkin@intel.com> Acked-by: Mimi Zohar <zohar@us.ibm.com>
| * crypto: GnuPG based MPI lib - additional sources (part 4)Dmitry Kasatkin2011-11-091-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. This code is unnecessary for RSA digital signature verification, but for completeness it is included here and can be compiled, if CONFIG_MPILIB_EXTRA is enabled. Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
| * crypto: GnuPG based MPI lib - make files (part 3)Dmitry Kasatkin2011-11-091-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
* | Merge tag 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mst/vhostLinus Torvalds2012-01-101-0/+7
|\ \ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | lib: use generic pci_iomap on all architectures Many architectures don't want to pull in iomap.c, so they ended up duplicating pci_iomap from that file. That function isn't trivial, and we are going to modify it https://lkml.org/lkml/2011/11/14/183 so the duplication hurts. This reduces the scope of the problem significantly, by moving pci_iomap to a separate file and referencing that from all architectures. * tag 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/mst/vhost: alpha: drop pci_iomap/pci_iounmap from pci-noop.c mn10300: switch to GENERIC_PCI_IOMAP mn10300: add missing __iomap markers frv: switch to GENERIC_PCI_IOMAP tile: switch to GENERIC_PCI_IOMAP tile: don't panic on iomap sparc: switch to GENERIC_PCI_IOMAP sh: switch to GENERIC_PCI_IOMAP powerpc: switch to GENERIC_PCI_IOMAP parisc: switch to GENERIC_PCI_IOMAP mips: switch to GENERIC_PCI_IOMAP microblaze: switch to GENERIC_PCI_IOMAP arm: switch to GENERIC_PCI_IOMAP alpha: switch to GENERIC_PCI_IOMAP lib: add GENERIC_PCI_IOMAP lib: move GENERIC_IOMAP to lib/Kconfig Fix up trivial conflicts due to changes nearby in arch/{m68k,score}/Kconfig
| * | lib: add GENERIC_PCI_IOMAPMichael S. Tsirkin2011-11-281-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Michael S. Tsirkin <mst@redhat.com>
| * | lib: move GENERIC_IOMAP to lib/KconfigMichael S. Tsirkin2011-11-241-0/+3
| |/ | | | | | | | | | | | | | | | | define GENERIC_IOMAP in a central location instead of all architectures. This will be helpful for the follow-up patch which makes it select other configs. Code is also a bit shorter this way. Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
* | Merge branch 'for-linus' of ↵Linus Torvalds2012-01-081-4/+3
|\ \ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | git://git.kernel.org/pub/scm/linux/kernel/git/jikos/trivial * 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/jikos/trivial: (53 commits) Kconfig: acpi: Fix typo in comment. misc latin1 to utf8 conversions devres: Fix a typo in devm_kfree comment btrfs: free-space-cache.c: remove extra semicolon. fat: Spelling s/obsolate/obsolete/g SCSI, pmcraid: Fix spelling error in a pmcraid_err() call tools/power turbostat: update fields in manpage mac80211: drop spelling fix types.h: fix comment spelling for 'architectures' typo fixes: aera -> area, exntension -> extension devices.txt: Fix typo of 'VMware'. sis900: Fix enum typo 'sis900_rx_bufer_status' decompress_bunzip2: remove invalid vi modeline treewide: Fix comment and string typo 'bufer' hyper-v: Update MAINTAINERS treewide: Fix typos in various parts of the kernel, and fix some comments. clockevents: drop unknown Kconfig symbol GENERIC_CLOCKEVENTS_MIGR gpio: Kconfig: drop unknown symbol 'CS5535_GPIO' leds: Kconfig: Fix typo 'D2NET_V2' sound: Kconfig: drop unknown symbol ARCH_CLPS7500 ... Fix up trivial conflicts in arch/powerpc/platforms/40x/Kconfig (some new kconfig additions, close to removed commented-out old ones)
| * \ Merge branch 'master' into for-nextJiri Kosina2011-11-131-3/+0
| |\ \ | | |/ | | | | | | | | | Sync with Linus tree to have 157550ff ("mtd: add GPMI-NAND driver in the config and Makefile") as I have patch depending on that one.
| * | Docs: Kconfig: CORDIC descriptionMichael Witten2011-10-291-3/+2
| | | | | | | | | | | | | | | | | | | | | This is just some copyediting. Signed-off-by: Michael Witten <mfwitten@gmail.com> Signed-off-by: Jiri Kosina <jkosina@suse.cz>
| * | Docs: wording: functions -> algorithmMichael Witten2011-10-291-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | The code seems to provide a single function that implements the CORDIC algorithm. Signed-off-by: Michael Witten <mfwitten@gmail.com> Signed-off-by: Jiri Kosina <jkosina@suse.cz>
| * | Docs: Pedantry: [Cc]ordic -> CORDICMichael Witten2011-10-291-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | According to: http://en.wikipedia.org/wiki/CORDIC it stands for: *CO*ordinate *R*otation *DI*gital *C*omputer Signed-off-by: Michael Witten <mfwitten@gmail.com> Signed-off-by: Jiri Kosina <jkosina@suse.cz>
* | | dql: Dynamic queue limitsTom Herbert2011-11-291-0/+3
| |/ |/| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Tom Herbert <therbert@google.com> Acked-by: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* | llist: Make some llist functions inlineHuang Ying2011-10-041-3/+0
|/ | | | | | | | | | | | 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: Huang Ying <ying.huang@intel.com> Acked-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Link: http://lkml.kernel.org/r/1315461646-1379-2-git-send-email-ying.huang@intel.com Signed-off-by: Ingo Molnar <mingo@elte.hu>
* Merge branch 'apei' into apei-releaseLen Brown2011-08-031-0/+3
|\ | | | | | | | | | | | | | | | | | | | | | | | | Some trivial conflicts due to other various merges adding to the end of common lists sooner than this one. arch/ia64/Kconfig arch/powerpc/Kconfig arch/x86/Kconfig lib/Kconfig lib/Makefile Signed-off-by: Len Brown <len.brown@intel.com>
| * lib, Add lock-less NULL terminated single listHuang Ying2011-08-031-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Huang Ying <ying.huang@intel.com> Reviewed-by: Andi Kleen <ak@linux.intel.com> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Cc: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Len Brown <len.brown@intel.com>
* | Merge branch 'master' of ↵John W. Linville2011-06-081-0/+14
|\ \ | |/ |/| | | git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-next-2.6 into for-davem
| * lib: cordic: add library module providing cordic angle calculationArend van Spriel2011-06-031-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Roland Vossen <rvossen@broadcom.com> Reviewed-by: Henry Ptasinski <henryp@broadcom.com> Reviewed-by: Franky (Zhenhui) Lin <frankyl@broadcom.com> Signed-off-by: Arend van Spriel <arend@broadcom.com> Signed-off-by: John W. Linville <linville@tuxdriver.com>
| * lib: crc8: add new library module providing crc8 algorithmArend van Spriel2011-06-031-0/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Henry Ptasinski <henryp@broadcom.com> Reviewed-by: Roland Vossen <rvossen@broadcom.com> Reviewed-by: "Franky (Zhenhui) Lin" <frankyl@broadcom.com> Signed-off-by: Arend van Spriel <arend@broadcom.com> Signed-off-by: John W. Linville <linville@tuxdriver.com>
* | arch: remove CONFIG_GENERIC_FIND_{NEXT_BIT,BIT_LE,LAST_BIT}Akinobu Mita2011-05-261-10/+0
|/ | | | | | | | | | | | | | | 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: Akinobu Mita <akinobu.mita@gmail.com> Acked-by: Greg 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: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* Merge branch 'master' of ↵Artem Bityutskiy2011-03-251-1/+15
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6 into for-linus-1 * 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6: (9356 commits) [media] rc: update for bitop name changes fs: simplify iget & friends fs: pull inode->i_lock up out of writeback_single_inode fs: rename inode_lock to inode_hash_lock fs: move i_wb_list out from under inode_lock fs: move i_sb_list out from under inode_lock fs: remove inode_lock from iput_final and prune_icache fs: Lock the inode LRU list separately fs: factor inode disposal fs: protect inode->i_state with inode->i_lock lib, arch: add filter argument to show_mem and fix private implementations SLUB: Write to per cpu data when allocating it slub: Fix debugobjects with lockless fastpath autofs4: Do not potentially dereference NULL pointer returned by fget() in autofs_dev_ioctl_setpipefd() autofs4 - remove autofs4_lock autofs4 - fix d_manage() return on rcu-walk autofs4 - fix autofs4_expire_indirect() traversal autofs4 - fix dentry leak in autofs4_expire_direct() autofs4 - reinstate last used update on access vfs - check non-mountpoint dentry might block in __follow_mount_rcu() ... NOTE! This merge commit was created to fix compilation error. The block tree was merged upstream and removed the 'elv_queue_empty()' function which the new 'mtdswap' driver is using. So a simple merge of the mtd tree with upstream does not compile. And the mtd tree has already be published, so re-basing it is not an option. To fix this unfortunate situation, I had to merge upstream into the mtd-2.6.git tree without committing, put the fixup patch on top of this, and then commit this. The result is that we do not have commits which do not compile. In other words, this merge commit "merges" 3 things: the MTD tree, the upstream tree, and the fixup patch.
| * bitops: introduce CONFIG_GENERIC_FIND_BIT_LEAkinobu Mita2011-03-231-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Akinobu Mita <akinobu.mita@gmail.com> Cc: Greg Ungerer <gerg@uclinux.org> Cc: Arnd Bergmann <arnd@arndb.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
| * Merge branch 'master' of ↵John W. Linville2011-03-111-1/+8
| |\ | | | | | | | | | git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-next-2.6 into for-davem
| | * lib-average: Make config option selectableMichael Buesch2011-03-041-1/+8
| | | | | | | | | | | | | | | | | | | | | | | | Make CONFIG_AVERAGE selectable for out-of-tree users such as compat-wireless. Signed-off-by: Michael Buesch <mb@bu3sch.de> Signed-off-by: John W. Linville <linville@tuxdriver.com>
| * | lib: cpu_rmap: CPU affinity reverse-mappingBen Hutchings2011-01-241-0/+4
| |/ | | | | | | | | | | | | | | | | | | | | | | 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: Ben Hutchings <bhutchings@solarflare.com> Signed-off-by: David S. Miller <davem@davemloft.net>
* | lib: add shared BCH ECC libraryIvan Djelic2011-03-111-0/+39
|/ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Ivan Djelic <ivan.djelic@parrot.com> Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
* decompressors: add boot-time XZ supportLasse Collin2011-01-131-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | 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: Lasse 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: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* decompressors: add XZ decompressor moduleLasse Collin2011-01-131-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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: Lasse 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: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
* lib: Add generic exponentially weighted moving average (EWMA) functionBruno Randolf2010-11-181-0/+3
| | | | | | | | | | | | | | | 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: Bruno Randolf <br1@einfach.org> Reviewed-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Signed-off-by: John W. Linville <linville@tuxdriver.com>
OpenPOWER on IntegriCloud