1. 18 1月, 2012 4 次提交
  2. 30 11月, 2011 1 次提交
    • T
      dql: Dynamic queue limits · 75957ba3
      Tom Herbert 提交于
      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: NTom Herbert <therbert@google.com>
      Acked-by: NEric Dumazet <eric.dumazet@gmail.com>
      Signed-off-by: NDavid S. Miller <davem@davemloft.net>
      75957ba3
  3. 29 11月, 2011 1 次提交
  4. 25 11月, 2011 1 次提交
  5. 22 11月, 2011 1 次提交
    • D
      digsig: build dependency fix · de353533
      Dmitry Kasatkin 提交于
      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: NRandy Dunlap <rdunlap@xenotime.net>
      Signed-off-by: NDmitry Kasatkin <dmitry.kasatkin@intel.com>
      Signed-off-by: NJames Morris <jmorris@namei.org>
      de353533
  6. 09 11月, 2011 3 次提交
    • D
      crypto: digital signature verification support · 051dbb91
      Dmitry Kasatkin 提交于
      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: NDmitry Kasatkin <dmitry.kasatkin@intel.com>
      Acked-by: NMimi Zohar <zohar@us.ibm.com>
      051dbb91
    • D
      crypto: GnuPG based MPI lib - additional sources (part 4) · 7e8dec91
      Dmitry Kasatkin 提交于
      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: NDmitry Kasatkin <dmitry.kasatkin@intel.com>
      7e8dec91
    • D
      crypto: GnuPG based MPI lib - make files (part 3) · d9c46b18
      Dmitry Kasatkin 提交于
      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: NDmitry Kasatkin <dmitry.kasatkin@intel.com>
      d9c46b18
  7. 30 10月, 2011 3 次提交
  8. 04 10月, 2011 1 次提交
  9. 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
  10. 04 6月, 2011 2 次提交
  11. 27 5月, 2011 1 次提交
  12. 24 3月, 2011 1 次提交
  13. 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
  14. 05 3月, 2011 1 次提交
  15. 25 1月, 2011 1 次提交
  16. 14 1月, 2011 2 次提交
    • 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
  17. 19 11月, 2010 1 次提交
  18. 14 7月, 2010 1 次提交
  19. 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
  20. 07 3月, 2010 1 次提交
  21. 12 1月, 2010 1 次提交
  22. 21 11月, 2009 1 次提交
  23. 29 10月, 2009 1 次提交
  24. 02 10月, 2009 1 次提交
  25. 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
  26. 11 6月, 2009 1 次提交
  27. 07 3月, 2009 1 次提交
  28. 04 3月, 2009 1 次提交
  29. 16 1月, 2009 1 次提交
    • P
      sched: make plist a library facility · ceacc2c1
      Peter Zijlstra 提交于
      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: NPeter Zijlstra <peterz@infradead.org>
      Signed-off-by: NIngo Molnar <mingo@elte.hu>
      ceacc2c1
  30. 07 1月, 2009 1 次提交
  31. 06 1月, 2009 1 次提交