04 Oct, 2011
1 commit
-
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
Acked-by: Mathieu Desnoyers
Signed-off-by: Peter Zijlstra
Link: http://lkml.kernel.org/r/1315461646-1379-2-git-send-email-ying.huang@intel.com
Signed-off-by: Ingo Molnar
03 Aug, 2011
2 commits
-
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/MakefileSigned-off-by: Len Brown
-
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
Reviewed-by: Andi Kleen
Reviewed-by: Mathieu Desnoyers
Cc: Andrew Morton
Signed-off-by: Len Brown
09 Jun, 2011
1 commit
-
…wireless-next-2.6 into for-davem
04 Jun, 2011
2 commits
-
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"
Cc: Greg Kroah-Hartman
Cc: Dan Carpenter
Cc: Randy Dunlap
Cc: Larry Finger
Reviewed-by: Roland Vossen
Reviewed-by: Henry Ptasinski
Reviewed-by: Franky (Zhenhui) Lin
Signed-off-by: Arend van Spriel
Signed-off-by: John W. Linville -
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
Cc: George Spelvin
Cc: Randy Dunlap
Reviewed-by: Henry Ptasinski
Reviewed-by: Roland Vossen
Reviewed-by: "Franky (Zhenhui) Lin"
Signed-off-by: Arend van Spriel
Signed-off-by: John W. Linville
27 May, 2011
1 commit
-
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
Acked-by: Greg Ungerer
Cc: Arnd Bergmann
Cc: Russell King
Cc: Martin Schwidefsky
Cc: Heiko Carstens
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
25 Mar, 2011
1 commit
-
…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.
24 Mar, 2011
1 commit
-
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
Cc: Greg Ungerer
Cc: Arnd Bergmann
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
12 Mar, 2011
1 commit
-
…wireless-next-2.6 into for-davem
11 Mar, 2011
1 commit
-
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 bytesEncoding 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 µsIn 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
Signed-off-by: David Woodhouse
05 Mar, 2011
1 commit
-
Make CONFIG_AVERAGE selectable for out-of-tree users
such as compat-wireless.Signed-off-by: Michael Buesch
Signed-off-by: John W. Linville
25 Jan, 2011
1 commit
-
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
Signed-off-by: David S. Miller
14 Jan, 2011
2 commits
-
This implements the API defined in 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
Cc: "H. Peter Anvin"
Cc: Alain Knaff
Cc: Albin Tonnerre
Cc: Phillip Lougher
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
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 .
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
Cc: "H. Peter Anvin"
Cc: Alain Knaff
Cc: Albin Tonnerre
Cc: Phillip Lougher
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
19 Nov, 2010
1 commit
-
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
Reviewed-by: KOSAKI Motohiro
Signed-off-by: John W. Linville
09 Aug, 2010
1 commit
-
Conflicts:
drivers/md/Makefile
lib/raid6/unroll.pl
14 Jul, 2010
1 commit
-
via following scripts
FILES=$(find * -type f | grep -vE 'oprofile|[^K]config')
sed -i \
-e 's/lmb/memblock/g' \
-e 's/LMB/MEMBLOCK/g' \
$FILESfor N in $(find . -name lmb.[ch]); do
M=$(echo $N | sed 's/lmb/memblock/g')
mv $N $M
doneand remove some wrong change like lmbench and dlmb etc.
also move memblock.c from lib/ to mm/
Suggested-by: Ingo Molnar
Acked-by: "H. Peter Anvin"
Acked-by: Benjamin Herrenschmidt
Acked-by: Linus Torvalds
Signed-off-by: Yinghai Lu
Signed-off-by: Benjamin Herrenschmidt
08 Mar, 2010
1 commit
-
This reverts commit a069c266ae5fdfbf5b4aecf2c672413aa33b2504.
It turns ou that not only was it missing a case (XFS) that needed it,
but perhaps more importantly, people sometimes want to enable new
modules that they hadn't had enabled before, and if such a module uses
list_sort(), it can't easily be inserted any more.So rather than add a "select LIST_SORT" to the XFS case, just leave it
compiled in. It's not all _that_ big, after all, and the inconvenience
isn't worth it.Requested-by: Alexey Dobriyan
Cc: Christoph Hellwig
Cc: Don Mullis
Cc: Andrew Morton
Cc: Dave Chinner
Signed-off-by: Linus Torvalds
07 Mar, 2010
2 commits
-
* git://git.kernel.org/pub/scm/linux/kernel/git/joern/logfs:
[LogFS] Change magic number
[LogFS] Remove h_version field
[LogFS] Check feature flags
[LogFS] Only write journal if dirty
[LogFS] Fix bdev erases
[LogFS] Silence gcc
[LogFS] Prevent 64bit divisions in hash_index
[LogFS] Plug memory leak on error paths
[LogFS] Add MAINTAINERS entry
[LogFS] add new flash file systemFixed up trivial conflict in lib/Kconfig, and a semantic conflict in
fs/logfs/inode.c introduced by write_inode() being changed to use
writeback_control' by commit a9185b41a4f84971b930c519f0c63bd450c4810d
("pass writeback_control to ->write_inode") -
Build list_sort() only for configs that need it -- those that don't save
~581 bytes (i386).Signed-off-by: Don Mullis
Cc: Dave Airlie
Cc: Andi Kleen
Cc: Dave Chinner
Cc: Artem Bityutskiy
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
12 Jan, 2010
1 commit
-
Signed-off-by: Albin Tonnerre
Tested-by: Wu Zhangjin
Acked-by: "H. Peter Anvin"
Cc: Ingo Molnar
Cc: Thomas Gleixner
Tested-by: Russell King
Acked-by: Russell King
Cc: Ralf Baechle
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
21 Nov, 2009
1 commit
-
This is a new flash file system. See
Documentation/filesystems/logfs.txtSigned-off-by: Joern Engel
29 Oct, 2009
1 commit
-
We'll want to use these in btrfs too.
Signed-off-by: David Woodhouse
02 Oct, 2009
1 commit
-
Signed-off-by: Philipp Reisner
Signed-off-by: Lars Ellenberg
15 Jun, 2009
1 commit
-
Many processor architectures have no 64-bit atomic instructions, but
we need atomic64_t in order to support the perf_counter subsystem.This adds an implementation of 64-bit atomic operations using hashed
spinlocks to provide atomicity. For each atomic operation, the address
of the atomic64_t variable is hashed to an index into an array of 16
spinlocks. That spinlock is taken (with interrupts disabled) around the
operation, which can then be coded non-atomically within the lock.On UP, all the spinlock manipulation goes away and we simply disable
interrupts around each operation. In fact gcc eliminates the whole
atomic64_lock variable as well.Signed-off-by: Paul Mackerras
Signed-off-by: Benjamin Herrenschmidt
11 Jun, 2009
1 commit
-
Provide a helper function to determine optimum numerator
denominator value pairs taking into account restricted
register size. Useful especially with PLL and other clock
configurations.Signed-off-by: Oskar Schirmer
Signed-off-by: Alan Cox
Signed-off-by: Linus Torvalds
29 Mar, 2009
1 commit
28 Mar, 2009
1 commit
-
Conflicts:
arch/parisc/kernel/irq.c
arch/x86/include/asm/fixmap_64.h
arch/x86/include/asm/setup.h
kernel/irq/handle.cSemantic merge:
arch/x86/include/asm/fixmap.hSigned-off-by: Ingo Molnar
27 Mar, 2009
1 commit
-
* 'sched-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip: (46 commits)
sched: Add comments to find_busiest_group() function
sched: Refactor the power savings balance code
sched: Optimize the !power_savings_balance during fbg()
sched: Create a helper function to calculate imbalance
sched: Create helper to calculate small_imbalance in fbg()
sched: Create a helper function to calculate sched_domain stats for fbg()
sched: Define structure to store the sched_domain statistics for fbg()
sched: Create a helper function to calculate sched_group stats for fbg()
sched: Define structure to store the sched_group statistics for fbg()
sched: Fix indentations in find_busiest_group() using gotos
sched: Simple helper functions for find_busiest_group()
sched: remove unused fields from struct rq
sched: jiffies not printed per CPU
sched: small optimisation of can_migrate_task()
sched: fix typos in documentation
sched: add avg_overlap decay
x86, sched_clock(): mark variables read-mostly
sched: optimize ttwu vs group scheduling
sched: TIF_NEED_RESCHED -> need_reshed() cleanup
sched: don't rebalance if attached on NULL domain
...
07 Mar, 2009
1 commit
-
Impact: add new APIs for binary trace printk infrastructure
vbin_printf(): write args to binary buffer, string is copied
when "%s" is occurred.bstr_printf(): read from binary buffer for args and format a string
[fweisbec@gmail.com: rebase]
Signed-off-by: Lai Jiangshan
Signed-off-by: Frederic Weisbecker
Cc: Linus Torvalds
LKML-Reference:
Signed-off-by: Ingo Molnar
04 Mar, 2009
1 commit
-
Netlink attribute parsing may be used even if CONFIG_NET is not set.
Move it from net/netlink to lib and control its inclusion based on the new
config symbol CONFIG_NLATTR, which is selected by CONFIG_NET.Signed-off-by: Geert Uytterhoeven
Acked-by: David S. Miller
Signed-off-by: Herbert Xu
16 Jan, 2009
1 commit
-
Ingo Molnar wrote:
> here's a new build failure with tip/sched/rt:
>
> LD .tmp_vmlinux1
> kernel/built-in.o: In function `set_curr_task_rt':
> sched.c:(.text+0x3675): undefined reference to `plist_del'
> kernel/built-in.o: In function `pick_next_task_rt':
> sched.c:(.text+0x37ce): undefined reference to `plist_del'
> kernel/built-in.o: In function `enqueue_pushable_task':
> sched.c:(.text+0x381c): undefined reference to `plist_del'Eliminate the plist library kconfig and make it available
unconditionally.Signed-off-by: Peter Zijlstra
Signed-off-by: Ingo Molnar
07 Jan, 2009
1 commit
-
Impact: Partial resolution of build failure
DECOMPRESS_GZIP is just a common-interface wrapper around the
zlib_inflate code; it thus need to select it.Signed-off-by: H. Peter Anvin
06 Jan, 2009
1 commit
-
Impact: Partial resolution of build failure
Make all the compression algorithms properly configurable, and make
sure the ramdisk options pull in the proper compression algorithms, as
they should.Signed-off-by: H. Peter Anvin
01 Jan, 2009
2 commits
-
Impact: new debug CONFIG options
This helps find unconverted code. It currently breaks compile horribly,
but we never wanted a flag day so that's expected.Signed-off-by: Rusty Russell
-
Impact: New API
As the name suggests. For the moment everyone uses the generic one.
Signed-off-by: Rusty Russell
30 Dec, 2008
1 commit
25 Dec, 2008
2 commits
-
Selecting CRYPTO_CRC32C is not enough as CRYPTO which CRYPTO_CRC32C
depends on may be disabled. This patch adds the select on CRYPTO.Signed-off-by: Herbert Xu
-
This patch swaps the role of libcrc32c and crc32c. Previously
the implementation was in libcrc32c and crc32c was a wrapper.
Now the code is in crc32c and libcrc32c just calls the crypto
layer.The reason for the change is to tap into the algorithm selection
capability of the crypto API so that optimised implementations
such as the one utilising Intel's CRC32C instruction can be
used where available.Signed-off-by: Herbert Xu
