1. 04 10月, 2011 1 次提交
  2. 31 8月, 2011 1 次提交
    • G
      bitops: Move find_next_bit.o from lib-y to obj-y · bd823821
      Geert Uytterhoeven 提交于
      If there are no builtin users of find_next_bit_le() and
      find_next_zero_bit_le(), these functions are not present in the kernel
      image, causing m68k allmodconfig to fail with:
      
        ERROR: "find_next_zero_bit_le" [fs/ufs/ufs.ko] undefined!
        ERROR: "find_next_bit_le" [fs/udf/udf.ko] undefined!
        ...
      
      This started to happen after commit 171d809d ("m68k: merge mmu and
      non-mmu bitops.h"), as m68k had its own inline versions before.
      
      commit 63e424c8 ("arch: remove CONFIG_GENERIC_FIND_{NEXT_BIT,
      BIT_LE, LAST_BIT}") added find_last_bit.o to obj-y (so it's always
      included), but find_next_bit.o to lib-y (so it gets removed by the
      linker if there are no builtin users).
      Signed-off-by: NGeert Uytterhoeven <geert@linux-m68k.org>
      Cc: Akinobu Mita <akinobu.mita@gmail.com>
      Cc: Greg Ungerer <gerg@uclinux.org>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      bd823821
  3. 07 8月, 2011 1 次提交
  4. 03 8月, 2011 1 次提交
    • H
      lib, Add lock-less NULL terminated single list · f49f23ab
      Huang Ying 提交于
      Cmpxchg is used to implement adding new entry to the list, deleting
      all entries from the list, deleting first entry of the list and some
      other operations.
      
      Because this is a single list, so the tail can not be accessed in O(1).
      
      If there are multiple producers and multiple consumers, llist_add can
      be used in producers and llist_del_all can be used in consumers.  They
      can work simultaneously without lock.  But llist_del_first can not be
      used here.  Because llist_del_first depends on list->first->next does
      not changed if list->first is not changed during its operation, but
      llist_del_first, llist_add, llist_add (or llist_del_all, llist_add,
      llist_add) sequence in another consumer may violate that.
      
      If there are multiple producers and one consumer, llist_add can be
      used in producers and llist_del_all or llist_del_first can be used in
      the consumer.
      
      This can be summarized as follow:
      
                 |   add    | del_first |  del_all
       add       |    -     |     -     |     -
       del_first |          |     L     |     L
       del_all   |          |           |     -
      
      Where "-" stands for no lock is needed, while "L" stands for lock is
      needed.
      
      The list entries deleted via llist_del_all can be traversed with
      traversing function such as llist_for_each etc.  But the list entries
      can not be traversed safely before deleted from the list.  The order
      of deleted entries is from the newest to the oldest added one.  If you
      want to traverse from the oldest to the newest, you must reverse the
      order by yourself before traversing.
      
      The basic atomic operation of this list is cmpxchg on long.  On
      architectures that don't have NMI-safe cmpxchg implementation, the
      list can NOT be used in NMI handler.  So code uses the list in NMI
      handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
      Signed-off-by: NHuang Ying <ying.huang@intel.com>
      Reviewed-by: NAndi Kleen <ak@linux.intel.com>
      Reviewed-by: NMathieu Desnoyers <mathieu.desnoyers@efficios.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLen Brown <len.brown@intel.com>
      f49f23ab
  5. 04 6月, 2011 2 次提交
  6. 27 5月, 2011 1 次提交
  7. 19 5月, 2011 1 次提交
  8. 24 3月, 2011 1 次提交
  9. 23 3月, 2011 1 次提交
    • A
      kstrto*: converting strings to integers done (hopefully) right · 33ee3b2e
      Alexey Dobriyan 提交于
      1. simple_strto*() do not contain overflow checks and crufty,
         libc way to indicate failure.
      2. strict_strto*() also do not have overflow checks but the name and
         comments pretend they do.
      3. Both families have only "long long" and "long" variants,
         but users want strtou8()
      4. Both "simple" and "strict" prefixes are wrong:
         Simple doesn't exactly say what's so simple, strict should not exist
         because conversion should be strict by default.
      
      The solution is to use "k" prefix and add convertors for more types.
      Enter
      	kstrtoull()
      	kstrtoll()
      	kstrtoul()
      	kstrtol()
      	kstrtouint()
      	kstrtoint()
      
      	kstrtou64()
      	kstrtos64()
      	kstrtou32()
      	kstrtos32()
      	kstrtou16()
      	kstrtos16()
      	kstrtou8()
      	kstrtos8()
      
      Include runtime testsuite (somewhat incomplete) as well.
      
      strict_strto*() become deprecated, stubbed to kstrto*() and
      eventually will be removed altogether.
      
      Use kstrto*() in code today!
      
      Note: on some archs _kstrtoul() and _kstrtol() are left in tree, even if
            they'll be unused at runtime. This is temporarily solution,
            because I don't want to hardcode list of archs where these
            functions aren't needed. Current solution with sizeof() and
            __alignof__ at least always works.
      Signed-off-by: NAlexey Dobriyan <adobriyan@gmail.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      33ee3b2e
  10. 11 3月, 2011 1 次提交
    • I
      lib: add shared BCH ECC library · 437aa565
      Ivan Djelic 提交于
      This is a new software BCH encoding/decoding library, similar to the shared
      Reed-Solomon library.
      
      Binary BCH (Bose-Chaudhuri-Hocquenghem) codes are widely used to correct
      errors in NAND flash devices requiring more than 1-bit ecc correction; they
      are generally better suited for NAND flash than RS codes because NAND bit
      errors do not occur in bursts. Latest SLC NAND devices typically require at
      least 4-bit ecc protection per 512 bytes block.
      
      This library provides software encoding/decoding, but may also be used with
      ASIC/SoC hardware BCH engines to perform error correction. It is being
      currently used for this purpose on an OMAP3630 board (4bit/8bit HW BCH). It
      has also been used to decode raw dumps of NAND devices with on-die BCH ecc
      engines (e.g. Micron 4bit ecc SLC devices).
      
      Latest NAND devices (including SLC) can exhibit high error rates (typically
      a dozen or more bitflips per hour during stress tests); in order to
      minimize the performance impact of error correction, this library
      implements recently developed algorithms for fast polynomial root finding
      (see bch.c header for details) instead of the traditional exhaustive Chien
      root search; a few performance figures are provided below:
      
      Platform: arm926ejs @ 468 MHz, 32 KiB icache, 16 KiB dcache
      BCH ecc : 4-bit per 512 bytes
      
      Encoding average throughput: 250 Mbits/s
      
      Error correction time (compared with Chien search):
      
              average   worst      average (Chien)  worst (Chien)
      ----------------------------------------------------------
      1 bit    8.5 µs   11 µs         200 µs           383 µs
      2 bit    9.7 µs   12.5 µs       477 µs           728 µs
      3 bit   18.1 µs   20.6 µs       758 µs          1010 µs
      4 bit   19.5 µs   23 µs        1028 µs          1280 µs
      
      In the above figures, "worst" is meant in terms of error pattern, not in
      terms of cache miss / page faults effects (not taken into account here).
      
      The library has been extensively tested on the following platforms: x86,
      x86_64, arm926ejs, omap3630, qemu-ppc64, qemu-mips.
      Signed-off-by: NIvan Djelic <ivan.djelic@parrot.com>
      Signed-off-by: NDavid Woodhouse <David.Woodhouse@intel.com>
      437aa565
  11. 05 3月, 2011 1 次提交
    • A
      BKL: That's all, folks · 4ba8216c
      Arnd Bergmann 提交于
      This removes the implementation of the big kernel lock,
      at last. A lot of people have worked on this in the
      past, I so the credit for this patch should be with
      everyone who participated in the hunt.
      
      The names on the Cc list are the people that were the
      most active in this, according to the recorded git
      history, in alphabetical order.
      Signed-off-by: NArnd Bergmann <arnd@arndb.de>
      Acked-by: NAlan Cox <alan@linux.intel.com>
      Cc: Alessio Igor Bogani <abogani@texware.it>
      Cc: Al Viro <viro@zeniv.linux.org.uk>
      Cc: Andrew Hendry <andrew.hendry@gmail.com>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Cc: Christoph Hellwig <hch@infradead.org>
      Cc: Eric W. Biederman <ebiederm@xmission.com>
      Cc: Frederic Weisbecker <fweisbec@gmail.com>
      Cc: Hans Verkuil <hverkuil@xs4all.nl>
      Acked-by: NIngo Molnar <mingo@elte.hu>
      Cc: Jan Blunck <jblunck@infradead.org>
      Cc: John Kacur <jkacur@redhat.com>
      Cc: Jonathan Corbet <corbet@lwn.net>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Matthew Wilcox <matthew@wil.cx>
      Cc: Oliver Neukum <oliver@neukum.org>
      Cc: Paul Menage <menage@google.com>
      Acked-by: NThomas Gleixner <tglx@linutronix.de>
      Cc: Trond Myklebust <Trond.Myklebust@netapp.com>
      4ba8216c
  12. 25 1月, 2011 1 次提交
  13. 14 1月, 2011 3 次提交
    • L
      decompressors: add boot-time XZ support · 3ebe1243
      Lasse Collin 提交于
      This implements the API defined in <linux/decompress/generic.h> which is
      used for kernel, initramfs, and initrd decompression.  This patch together
      with the first patch is enough for XZ-compressed initramfs and initrd;
      XZ-compressed kernel will need arch-specific changes.
      
      The buffering requirements described in decompress_unxz.c are stricter
      than with gzip, so the relevant changes should be done to the
      arch-specific code when adding support for XZ-compressed kernel.
      Similarly, the heap size in arch-specific pre-boot code may need to be
      increased (30 KiB is enough).
      
      The XZ decompressor needs memmove(), memeq() (memcmp() == 0), and
      memzero() (memset(ptr, 0, size)), which aren't available in all
      arch-specific pre-boot environments.  I'm including simple versions in
      decompress_unxz.c, but a cleaner solution would naturally be nicer.
      Signed-off-by: NLasse Collin <lasse.collin@tukaani.org>
      Cc: "H. Peter Anvin" <hpa@zytor.com>
      Cc: Alain Knaff <alain@knaff.lu>
      Cc: Albin Tonnerre <albin.tonnerre@free-electrons.com>
      Cc: Phillip Lougher <phillip@lougher.demon.co.uk>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      3ebe1243
    • L
      decompressors: add XZ decompressor module · 24fa0402
      Lasse Collin 提交于
      In userspace, the .lzma format has become mostly a legacy file format that
      got superseded by the .xz format.  Similarly, LZMA Utils was superseded by
      XZ Utils.
      
      These patches add support for XZ decompression into the kernel.  Most of
      the code is as is from XZ Embedded <http://tukaani.org/xz/embedded.html>.
      It was written for the Linux kernel but is usable in other projects too.
      
      Advantages of XZ over the current LZMA code in the kernel:
        - Nice API that can be used by other kernel modules; it's
          not limited to kernel, initramfs, and initrd decompression.
        - Integrity check support (CRC32)
        - BCJ filters improve compression of executable code on
          certain architectures. These together with LZMA2 can
          produce a few percent smaller kernel or Squashfs images
          than plain LZMA without making the decompression slower.
      
      This patch: Add the main decompression code (xz_dec), testing module
      (xz_dec_test), wrapper script (xz_wrap.sh) for the xz command line tool,
      and documentation.  The xz_dec module is enough to have a usable XZ
      decompressor e.g.  for Squashfs.
      Signed-off-by: NLasse Collin <lasse.collin@tukaani.org>
      Cc: "H. Peter Anvin" <hpa@zytor.com>
      Cc: Alain Knaff <alain@knaff.lu>
      Cc: Albin Tonnerre <albin.tonnerre@free-electrons.com>
      Cc: Phillip Lougher <phillip@lougher.demon.co.uk>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      24fa0402
    • D
      flex_array: export symbols to modules · 78c377d1
      David Rientjes 提交于
      Alex said:
      
        I want to use flex_array to store a sparse array of ATM cell
        re-assembly buffers for my ATM over Ethernet driver.  Using the per-vcc
        user_back structure causes problems when stacked with things like
        br2684.
      
      Add EXPORT_SYMBOL() for all publically accessible flex array functions
      and move to obj-y so that modules may use this library.
      Signed-off-by: NDavid Rientjes <rientjes@google.com>
      Cc: Dave Hansen <dave@linux.vnet.ibm.com>
      Cc: Paul Mundt <lethal@linux-sh.org>
      Reported-by: NAlex Bennee <kernel-hacker@bennee.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      78c377d1
  14. 11 12月, 2010 1 次提交
  15. 03 12月, 2010 1 次提交
    • J
      timers: Introduce timerlist infrastructure. · 87de5ac7
      John Stultz 提交于
      The timerlist infrastructure is a thin layer over the rbtree
      code that implements a simple list of timers sorted by an
      expires value, and a getnext function that provides a pointer
      to the earliest timer.
      
      This infrastructure allows drivers and other kernel infrastructure
      to easily implement timers without duplicating code.
      Signed-off-by: NJohn Stultz <john.stultz@linaro.org>
      LKML Reference: <1290136329-18291-2-git-send-email-john.stultz@linaro.org>
      Reviewed-by: NThomas Gleixner <tglx@linutronix.de>
      CC: Alessandro Zummo <a.zummo@towertech.it>
      CC: Thomas Gleixner <tglx@linutronix.de>
      CC: Richard Cochran <richardcochran@gmail.com>
      87de5ac7
  16. 19 11月, 2010 1 次提交
  17. 14 7月, 2010 1 次提交
  18. 28 5月, 2010 1 次提交
  19. 20 5月, 2010 1 次提交
    • H
      Unified UUID/GUID definition · fab1c232
      Huang Ying 提交于
      There are many different UUID/GUID definitions in kernel, such as that
      in EFI, many file systems, some drivers, etc. Every kernel components
      need UUID/GUID has its own definition. This patch provides a unified
      definition for UUID/GUID.
      
      UUID is defined via typedef. This makes that UUID appears more like a
      preliminary type, and makes the data type explicit (comparing with
      implicit "u8 uuid[16]").
      
      The binary representation of UUID/GUID can be little-endian (used by
      EFI, etc) or big-endian (defined by RFC4122), so both is defined.
      Signed-off-by: NHuang Ying <ying.huang@intel.com>
      Signed-off-by: NAndi Kleen <ak@linux.intel.com>
      Signed-off-by: NLen Brown <len.brown@intel.com>
      fab1c232
  20. 07 4月, 2010 1 次提交
    • B
      x86: Add optimized popcnt variants · d61931d8
      Borislav Petkov 提交于
      Add support for the hardware version of the Hamming weight function,
      popcnt, present in CPUs which advertize it under CPUID, Function
      0x0000_0001_ECX[23]. On CPUs which don't support it, we fallback to the
      default lib/hweight.c sw versions.
      
      A synthetic benchmark comparing popcnt with __sw_hweight64 showed almost
      a 3x speedup on a F10h machine.
      Signed-off-by: NBorislav Petkov <borislav.petkov@amd.com>
      LKML-Reference: <20100318112015.GC11152@aftab>
      Signed-off-by: NH. Peter Anvin <hpa@zytor.com>
      d61931d8
  21. 15 3月, 2010 1 次提交
  22. 08 3月, 2010 1 次提交
    • L
      Revert "lib: build list_sort() only if needed" · b8fa0571
      Linus Torvalds 提交于
      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: NAlexey 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: NLinus Torvalds <torvalds@linux-foundation.org>
      b8fa0571
  23. 07 3月, 2010 1 次提交
  24. 26 2月, 2010 1 次提交
  25. 13 1月, 2010 1 次提交
  26. 12 1月, 2010 1 次提交
  27. 21 11月, 2009 1 次提交
  28. 29 10月, 2009 1 次提交
  29. 02 10月, 2009 1 次提交
  30. 30 7月, 2009 1 次提交
    • D
      lib: flexible array implementation · 534acc05
      Dave Hansen 提交于
      Once a structure goes over PAGE_SIZE*2, we see occasional allocation
      failures.  Some people have chosen to switch over to things like vmalloc()
      that will let them keep array-like access to such a large structures.
      But, vmalloc() has plenty of downsides.
      
      Here's an alternative.  I think it's what Andrew was suggesting here:
      
      	http://lkml.org/lkml/2009/7/2/518
      
      I call it a flexible array.  It does all of its work in PAGE_SIZE bits, so
      never does an order>0 allocation.  The base level has
      PAGE_SIZE-2*sizeof(int) bytes of storage for pointers to the second level.
       So, with a 32-bit arch, you get about 4MB (4183112 bytes) of total
      storage when the objects pack nicely into a page.  It is half that on
      64-bit because the pointers are twice the size.  There's a table detailing
      this in the code.
      
      There are kerneldocs for the functions, but here's an
      overview:
      
      flex_array_alloc() - dynamically allocate a base structure
      flex_array_free() - free the array and all of the
      		    second-level pages
      flex_array_free_parts() - free the second-level pages, but
      			  not the base (for static bases)
      flex_array_put() - copy into the array at the given index
      flex_array_get() - copy out of the array at the given index
      flex_array_prealloc() - preallocate the second-level pages
      			between the given indexes to
      			guarantee no allocs will occur at
      			put() time.
      
      We could also potentially just pass the "element_size" into each of the
      API functions instead of storing it internally.  That would get us one
      more base pointer on 32-bit.
      
      I've been testing this by running it in userspace.  The header and patch
      that I've been using are here, as well as the little script I'm using to
      generate the size table which goes in the kerneldocs.
      
      	http://sr71.net/~dave/linux/flexarray/
      
      [akpm@linux-foundation.org: coding-style fixes]
      Signed-off-by: NDave Hansen <dave@linux.vnet.ibm.com>
      Reviewed-by: NKAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      534acc05
  31. 19 6月, 2009 1 次提交
    • F
      lib: add lib/gcd.c · d2829224
      Florian Fainelli 提交于
      This patch adds lib/gcd.c which contains a greatest common divider
      implementation taken from sound/core/pcm_timer.c
      
      Several usages of this new library function will be sent to subsystem
      maintainers.
      
      [akpm@linux-foundation.org: use swap() (pointed out by Joe)]
      [akpm@linux-foundation.org: just add gcd.o to obj-y, remove Kconfig changes]
      Signed-off-by: NFlorian Fainelli <florian@openwrt.org>
      Cc: Sergei Shtylyov <sshtylyov@ru.mvista.com>
      Cc: Takashi Iwai <tiwai@suse.de>
      Cc: Simon Horman <horms@verge.net.au>
      Cc: Julius Volz <juliusv@google.com>
      Cc: David S. Miller <davem@davemloft.net>
      Cc: Patrick McHardy <kaber@trash.net>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      d2829224
  32. 15 6月, 2009 1 次提交
    • P
      lib: Provide generic atomic64_t implementation · 09d4e0ed
      Paul Mackerras 提交于
      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: NPaul Mackerras <paulus@samba.org>
      Signed-off-by: NBenjamin Herrenschmidt <benh@kernel.crashing.org>
      09d4e0ed
  33. 12 6月, 2009 1 次提交
  34. 11 6月, 2009 1 次提交
  35. 25 4月, 2009 1 次提交
  36. 25 3月, 2009 1 次提交
    • J
      dynamic debug: combine dprintk and dynamic printk · e9d376f0
      Jason Baron 提交于
      This patch combines Greg Bank's dprintk() work with the existing dynamic
      printk patchset, we are now calling it 'dynamic debug'.
      
      The new feature of this patchset is a richer /debugfs control file interface,
      (an example output from my system is at the bottom), which allows fined grained
      control over the the debug output. The output can be controlled by function,
      file, module, format string, and line number.
      
      for example, enabled all debug messages in module 'nf_conntrack':
      
      echo -n 'module nf_conntrack +p' > /mnt/debugfs/dynamic_debug/control
      
      to disable them:
      
      echo -n 'module nf_conntrack -p' > /mnt/debugfs/dynamic_debug/control
      
      A further explanation can be found in the documentation patch.
      Signed-off-by: NGreg Banks <gnb@sgi.com>
      Signed-off-by: NJason Baron <jbaron@redhat.com>
      Signed-off-by: NGreg Kroah-Hartman <gregkh@suse.de>
      e9d376f0
  37. 05 3月, 2009 1 次提交