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

    Huang Ying
     

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/Makefile

    Signed-off-by: Len Brown

    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

    Huang Ying
     

09 Jun, 2011

1 commit


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

    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
    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

    Arend van Spriel
     

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

    Akinobu Mita
     

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.

    Artem Bityutskiy
     

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

    Akinobu Mita
     

12 Mar, 2011

1 commit


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 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
    Signed-off-by: David Woodhouse

    Ivan Djelic
     

05 Mar, 2011

1 commit


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

    Ben Hutchings
     

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

    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 .
    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

    Lasse Collin
     

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

    Bruno Randolf
     

09 Aug, 2010

1 commit


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' \
    $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: 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

    Yinghai Lu
     

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

    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 system

    Fixed 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")

    Linus Torvalds
     
  • 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

    Don Mullis
     

12 Jan, 2010

1 commit


21 Nov, 2009

1 commit


29 Oct, 2009

1 commit


02 Oct, 2009

1 commit


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

    Paul Mackerras
     

11 Jun, 2009

1 commit


29 Mar, 2009

1 commit


28 Mar, 2009

1 commit


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
    ...

    Linus Torvalds
     

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

    Lai Jiangshan
     

04 Mar, 2009

1 commit


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

    Peter Zijlstra
     

07 Jan, 2009

1 commit


06 Jan, 2009

1 commit


01 Jan, 2009

2 commits


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

    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

    Herbert Xu