1. 03 Jun, 2011 2 commits
  2. 24 Mar, 2011 1 commit
  3. 11 Mar, 2011 1 commit
    • Ivan Djelic's avatar
      lib: add shared BCH ECC library · 437aa565
      Ivan Djelic authored
      
      
      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: default avatarIvan Djelic <ivan.djelic@parrot.com>
      Signed-off-by: default avatarDavid Woodhouse <David.Woodhouse@intel.com>
      437aa565
  4. 04 Mar, 2011 1 commit
  5. 24 Jan, 2011 1 commit
  6. 13 Jan, 2011 2 commits
    • Lasse Collin's avatar
      decompressors: add boot-time XZ support · 3ebe1243
      Lasse Collin authored
      
      
      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: default avatarLasse 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: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      3ebe1243
    • Lasse Collin's avatar
      decompressors: add XZ decompressor module · 24fa0402
      Lasse Collin authored
      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: default avatarLasse 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: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      24fa0402
  7. 18 Nov, 2010 1 commit
  8. 14 Jul, 2010 1 commit
  9. 07 Mar, 2010 1 commit
    • Linus Torvalds's avatar
      Revert "lib: build list_sort() only if needed" · b8fa0571
      Linus Torvalds authored
      This reverts commit a069c266
      
      .
      
      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: default avatarAlexey Dobriyan <adobriyan@gmail.com>
      Cc: Christoph Hellwig <hch@infradead.org>
      Cc: Don Mullis <don.mullis@gmail.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Cc: Dave Chinner <david@fromorbit.com>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      b8fa0571
  10. 06 Mar, 2010 1 commit
  11. 11 Jan, 2010 1 commit
  12. 20 Nov, 2009 1 commit
  13. 29 Oct, 2009 1 commit
  14. 01 Oct, 2009 1 commit
  15. 15 Jun, 2009 1 commit
    • Paul Mackerras's avatar
      lib: Provide generic atomic64_t implementation · 09d4e0ed
      Paul Mackerras authored
      
      
      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: default avatarPaul Mackerras <paulus@samba.org>
      Signed-off-by: default avatarBenjamin Herrenschmidt <benh@kernel.crashing.org>
      09d4e0ed
  16. 11 Jun, 2009 1 commit
  17. 06 Mar, 2009 1 commit
  18. 04 Mar, 2009 1 commit
  19. 16 Jan, 2009 1 commit
    • Peter Zijlstra's avatar
      sched: make plist a library facility · ceacc2c1
      Peter Zijlstra authored
      
      
      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: default avatarPeter Zijlstra <peterz@infradead.org>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      ceacc2c1
  20. 07 Jan, 2009 1 commit
  21. 05 Jan, 2009 1 commit
  22. 31 Dec, 2008 2 commits
  23. 25 Dec, 2008 2 commits
  24. 13 Dec, 2008 1 commit
  25. 16 Oct, 2008 1 commit
  26. 12 Jul, 2008 1 commit
  27. 26 Apr, 2008 1 commit
    • Alexander van Heukelum's avatar
      x86, bitops: select the generic bitmap search functions · 19870def
      Alexander van Heukelum authored
      
      
      Introduce GENERIC_FIND_FIRST_BIT and GENERIC_FIND_NEXT_BIT in
      lib/Kconfig, defaulting to off. An arch that wants to use the
      generic implementation now only has to use a select statement
      to include them.
      
      I added an always-y option (X86_CPU) to arch/x86/Kconfig.cpu
      and used that to select the generic search functions. This
      way ARCH=um SUBARCH=i386 automatically picks up the change
      too, and arch/um/Kconfig.i386 can therefore be simplified a
      bit. ARCH=um SUBARCH=x86_64 does things differently, but
      still compiles fine. It seems that a "def_bool y" always
      wins over a "def_bool n"?
      Signed-off-by: default avatarAlexander van Heukelum <heukelum@fastmail.fm>
      Signed-off-by: default avatarIngo Molnar <mingo@elte.hu>
      19870def
  28. 14 Feb, 2008 1 commit
  29. 23 Aug, 2007 1 commit
  30. 17 Jul, 2007 1 commit
  31. 11 Jul, 2007 1 commit
  32. 10 May, 2007 1 commit
  33. 07 May, 2007 1 commit
    • Heiko Carstens's avatar
      Introduce CONFIG_HAS_DMA · 411f0f3e
      Heiko Carstens authored
      
      
      Architectures that don't support DMA can say so by adding a config NO_DMA
      to their Kconfig file.  This will prevent compilation of some dma specific
      driver code.  Also dma-mapping-broken.h isn't needed anymore on at least
      s390.  This avoids compilation and linking of otherwise dead/broken code.
      
      Other architectures that include dma-mapping-broken.h are arm26, h8300,
      m68k, m68knommu and v850.  If these could be converted as well we could get
      rid of the header file.
      Signed-off-by: default avatarHeiko Carstens <heiko.carstens@de.ibm.com>
      "John W. Linville" <linville@tuxdriver.com>
      Cc: Kyle McMartin <kyle@parisc-linux.org>
      Cc: <James.Bottomley@SteelEye.com>
      Cc: Tejun Heo <htejun@gmail.com>
      Cc: Jeff Garzik <jeff@garzik.org>
      Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
      Cc: <geert@linux-m68k.org>
      Cc: <zippel@linux-m68k.org>
      Cc: <spyro@f2s.com>
      Cc: <uclinux-v850@lsi.nec.co.jp>
      Cc: <ysato@users.sourceforge.jp>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      411f0f3e
  34. 11 Feb, 2007 1 commit
    • Al Viro's avatar
      [PATCH] sort the devres mess out · 5ea81769
      Al Viro authored
      
      
      * Split the implementation-agnostic stuff in separate files.
      * Make sure that targets using non-default request_irq() pull
        kernel/irq/devres.o
      * Introduce new symbols (HAS_IOPORT and HAS_IOMEM) defaulting to positive;
        allow architectures to turn them off (we needed these symbols anyway for
        dependencies of quite a few drivers).
      * protect the ioport-related parts of lib/devres.o with CONFIG_HAS_IOPORT.
      Signed-off-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      5ea81769
  35. 13 Dec, 2006 1 commit
  36. 08 Dec, 2006 1 commit