1. 09 10月, 2012 3 次提交
    • M
      prio_tree: remove · 147e615f
      Michel Lespinasse 提交于
      After both prio_tree users have been converted to use red-black trees,
      there is no need to keep around the prio tree library anymore.
      Signed-off-by: NMichel Lespinasse <walken@google.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Hillf Danton <dhillf@gmail.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Catalin Marinas <catalin.marinas@arm.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      147e615f
    • M
      rbtree: add prio tree and interval tree tests · fff3fd8a
      Michel Lespinasse 提交于
      Patch 1 implements support for interval trees, on top of the augmented
      rbtree API. It also adds synthetic tests to compare the performance of
      interval trees vs prio trees. Short answers is that interval trees are
      slightly faster (~25%) on insert/erase, and much faster (~2.4 - 3x)
      on search. It is debatable how realistic the synthetic test is, and I have
      not made such measurements yet, but my impression is that interval trees
      would still come out faster.
      
      Patch 2 uses a preprocessor template to make the interval tree generic,
      and uses it as a replacement for the vma prio_tree.
      
      Patch 3 takes the other prio_tree user, kmemleak, and converts it to use
      a basic rbtree. We don't actually need the augmented rbtree support here
      because the intervals are always non-overlapping.
      
      Patch 4 removes the now-unused prio tree library.
      
      Patch 5 proposes an additional optimization to rb_erase_augmented, now
      providing it as an inline function so that the augmented callbacks can be
      inlined in. This provides an additional 5-10% performance improvement
      for the interval tree insert/erase benchmark. There is a maintainance cost
      as it exposes augmented rbtree users to some of the rbtree library internals;
      however I think this cost shouldn't be too high as I expect the augmented
      rbtree will always have much less users than the base rbtree.
      
      I should probably add a quick summary of why I think it makes sense to
      replace prio trees with augmented rbtree based interval trees now.  One of
      the drivers is that we need augmented rbtrees for Rik's vma gap finding
      code, and once you have them, it just makes sense to use them for interval
      trees as well, as this is the simpler and more well known algorithm.  prio
      trees, in comparison, seem *too* clever: they impose an additional 'heap'
      constraint on the tree, which they use to guarantee a faster worst-case
      complexity of O(k+log N) for stabbing queries in a well-balanced prio
      tree, vs O(k*log N) for interval trees (where k=number of matches,
      N=number of intervals).  Now this sounds great, but in practice prio trees
      don't realize this theorical benefit.  First, the additional constraint
      makes them harder to update, so that the kernel implementation has to
      simplify things by balancing them like a radix tree, which is not always
      ideal.  Second, the fact that there are both index and heap properties
      makes both tree manipulation and search more complex, which results in a
      higher multiplicative time constant.  As it turns out, the simple interval
      tree algorithm ends up running faster than the more clever prio tree.
      
      This patch:
      
      Add two test modules:
      
      - prio_tree_test measures the performance of lib/prio_tree.c, both for
        insertion/removal and for stabbing searches
      
      - interval_tree_test measures the performance of a library of equivalent
        functionality, built using the augmented rbtree support.
      
      In order to support the second test module, lib/interval_tree.c is
      introduced. It is kept separate from the interval_tree_test main file
      for two reasons: first we don't want to provide an unfair advantage
      over prio_tree_test by having everything in a single compilation unit,
      and second there is the possibility that the interval tree functionality
      could get some non-test users in kernel over time.
      Signed-off-by: NMichel Lespinasse <walken@google.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Hillf Danton <dhillf@gmail.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Catalin Marinas <catalin.marinas@arm.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      fff3fd8a
    • M
      rbtree: performance and correctness test · 910a742d
      Michel Lespinasse 提交于
      This small module helps measure the performance of rbtree insert and
      erase.
      
      Additionally, we run a few correctness tests to check that the rbtrees
      have all desired properties:
      
      - contains the right number of nodes in the order desired,
      - never two consecutive red nodes on any path,
      - all paths to leaf nodes have the same number of black nodes,
      - root node is black
      
      [akpm@linux-foundation.org: fix printk warning: sparc64 cycles_t is unsigned long]
      Signed-off-by: NMichel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: NDavid Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      910a742d
  2. 08 10月, 2012 2 次提交
    • D
      X.509: Add an ASN.1 decoder · 42d5ec27
      David Howells 提交于
      Add an ASN.1 BER/DER/CER decoder.  This uses the bytecode from the ASN.1
      compiler in the previous patch to inform it as to what to expect to find in the
      encoded byte stream.  The output from the compiler also tells it what functions
      to call on what tags, thus allowing the caller to retrieve information.
      
      The decoder is called as follows:
      
      	int asn1_decoder(const struct asn1_decoder *decoder,
      			 void *context,
      			 const unsigned char *data,
      			 size_t datalen);
      
      The decoder argument points to the bytecode from the ASN.1 compiler.  context
      is the caller's context and is passed to the action functions.  data and
      datalen define the byte stream to be decoded.
      
      Note that the decoder is currently limited to datalen being less than 64K.
      This reduces the amount of stack space used by the decoder because ASN.1 is a
      nested construct.  Similarly, the decoder is limited to a maximum of 10 levels
      of constructed data outside of a leaf node also in an effort to keep stack
      usage down.
      
      These restrictions can be raised if necessary.
      Signed-off-by: NDavid Howells <dhowells@redhat.com>
      Signed-off-by: NRusty Russell <rusty@rustcorp.com.au>
      42d5ec27
    • D
      X.509: Implement simple static OID registry · a77ad6ea
      David Howells 提交于
      Implement a simple static OID registry that allows the mapping of an encoded
      OID to an enum value for ease of use.
      
      The OID registry index enum appears in the:
      
      	linux/oid_registry.h
      
      header file.  A script generates the registry from lines in the header file
      that look like:
      
      	<sp*>OID_foo,<sp*>/*<sp*>1.2.3.4<sp*>*/
      
      The actual OID is taken to be represented by the numbers with interpolated
      dots in the comment.
      
      All other lines in the header are ignored.
      
      The registry is queries by calling:
      
      	OID look_up_oid(const void *data, size_t datasize);
      
      This returns a number from the registry enum representing the OID if found or
      OID__NR if not.
      Signed-off-by: NDavid Howells <dhowells@redhat.com>
      Signed-off-by: NRusty Russell <rusty@rustcorp.com.au>
      a77ad6ea
  3. 31 7月, 2012 5 次提交
    • A
      powerpc: pSeries reconfig notifier error injection module · 08dfb4dd
      Akinobu Mita 提交于
      This provides the ability to inject artifical errors to pSeries reconfig
      notifier chain callbacks.  It is controlled through debugfs interface
      under /sys/kernel/debug/notifier-error-inject/pSeries-reconfig
      
      If the notifier call chain should be failed with some events
      notified, write the error code to "actions/<notifier event>/error".
      Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com>
      Cc: Pavel Machek <pavel@ucw.cz>
      Cc: "Rafael J. Wysocki" <rjw@sisk.pl>
      Cc: Greg KH <greg@kroah.com>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Cc: Dave Jones <davej@redhat.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      08dfb4dd
    • A
      memory: memory notifier error injection module · 9579f5bd
      Akinobu Mita 提交于
      This provides the ability to inject artifical errors to memory hotplug
      notifier chain callbacks.  It is controlled through debugfs interface
      under /sys/kernel/debug/notifier-error-inject/memory
      
      If the notifier call chain should be failed with some events notified,
      write the error code to "actions/<notifier event>/error".
      
      Example: Inject memory hotplug offline error (-12 == -ENOMEM)
      
      	# cd /sys/kernel/debug/notifier-error-inject/memory
      	# echo -12 > actions/MEM_GOING_OFFLINE/error
      	# echo offline > /sys/devices/system/memory/memoryXXX/state
      	bash: echo: write error: Cannot allocate memory
      Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com>
      Cc: Pavel Machek <pavel@ucw.cz>
      Cc: "Rafael J. Wysocki" <rjw@sisk.pl>
      Cc: Greg KH <greg@kroah.com>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Cc: Dave Jones <davej@redhat.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      9579f5bd
    • A
      PM: PM notifier error injection module · 048b9c35
      Akinobu Mita 提交于
      This provides the ability to inject artifical errors to PM notifier chain
      callbacks.  It is controlled through debugfs interface under
      /sys/kernel/debug/notifier-error-inject/pm
      
      Each of the files in "error" directory represents an event which can be
      failed and contains the error code.  If the notifier call chain should be
      failed with some events notified, write the error code to the files.
      
      If the notifier call chain should be failed with some events notified,
      write the error code to "actions/<notifier event>/error".
      
      Example: Inject PM suspend error (-12 = -ENOMEM)
      
      	# cd /sys/kernel/debug/notifier-error-inject/pm
      	# echo -12 > actions/PM_SUSPEND_PREPARE/error
      	# echo mem > /sys/power/state
      	bash: echo: write error: Cannot allocate memory
      Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com>
      Acked-by: N"Rafael J. Wysocki" <rjw@sisk.pl>
      Cc: Pavel Machek <pavel@ucw.cz>
      Cc: Greg KH <greg@kroah.com>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Cc: Dave Jones <davej@redhat.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      048b9c35
    • A
      fault-injection: notifier error injection · 8d438288
      Akinobu Mita 提交于
      This patchset provides kernel modules that can be used to test the error
      handling of notifier call chain failures by injecting artifical errors to
      the following notifier chain callbacks.
      
       * CPU notifier
       * PM notifier
       * memory hotplug notifier
       * powerpc pSeries reconfig notifier
      
      Example: Inject CPU offline error (-1 == -EPERM)
      
        # cd /sys/kernel/debug/notifier-error-inject/cpu
        # echo -1 > actions/CPU_DOWN_PREPARE/error
        # echo 0 > /sys/devices/system/cpu/cpu1/online
        bash: echo: write error: Operation not permitted
      
      The patchset also adds cpu and memory hotplug tests to
      tools/testing/selftests These tests first do simple online and offline
      test and then do fault injection tests if notifier error injection
      module is available.
      
      This patch:
      
      The notifier error injection provides the ability to inject artifical
      errors to specified notifier chain callbacks.  It is useful to test the
      error handling of notifier call chain failures.
      
      This adds common basic functions to define which type of events can be
      fail and to initialize the debugfs interface to control what error code
      should be returned and which event should be failed.
      Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com>
      Cc: Pavel Machek <pavel@ucw.cz>
      Cc: "Rafael J. Wysocki" <rjw@sisk.pl>
      Cc: Greg KH <greg@kroah.com>
      Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
      Cc: Paul Mackerras <paulus@samba.org>
      Cc: Michael Ellerman <michael@ellerman.id.au>
      Cc: Dave Jones <davej@redhat.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      8d438288
    • A
      string: introduce memweight() · 639b9e34
      Akinobu Mita 提交于
      memweight() is the function that counts the total number of bits set in
      memory area.  Unlike bitmap_weight(), memweight() takes pointer and size
      in bytes to specify a memory area which does not need to be aligned to
      long-word boundary.
      
      [akpm@linux-foundation.org: rename `w' to `ret']
      Signed-off-by: NAkinobu Mita <akinobu.mita@gmail.com>
      Cc: Anders Larsen <al@alarsen.net>
      Cc: Alasdair Kergon <agk@redhat.com>
      Cc: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
      Cc: Mark Fasheh <mfasheh@suse.com>
      Cc: Joel Becker <jlbec@evilplan.org>
      Cc: Jan Kara <jack@suse.cz>
      Cc: Andreas Dilger <adilger.kernel@dilger.ca>
      Cc: "Theodore Ts'o" <tytso@mit.edu>
      Cc: Matthew Wilcox <matthew@wil.cx>
      Cc: Mauro Carvalho Chehab <mchehab@infradead.org>
      Cc: Tony Luck <tony.luck@gmail.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      639b9e34
  4. 23 7月, 2012 1 次提交
    • D
      of/lib: Allow scripts/dtc/libfdt to be used from kernel code · ab253839
      David Daney 提交于
      libfdt is part of the device tree support in scripts/dtc/libfdt.  For
      some platforms that use the Device Tree, we want to be able to edit
      the flattened device tree form.
      
      We don't want to burden kernel builds that do not require it, so we
      gate compilation of libfdt files with CONFIG_LIBFDT.  So if it is
      needed, you need to do this in your Kconfig:
      
      	select LIBFDT
      
      And in the Makefile of the code using libfdt something like:
      
      ccflags-y := -I$(src)/../../../scripts/dtc/libfdt
      Signed-off-by: NDavid Daney <david.daney@cavium.com>
      Cc: linux-mips@linux-mips.org
      Cc: devicetree-discuss@lists.ozlabs.org
      Cc: Grant Likely <grant.likely@secretlab.ca>
      Cc: linux-kernel@vger.kernel.org
      Acked-by: NRob Herring <rob.herring@calxeda.com>
      Signed-off-by: NRalf Baechle <ralf@linux-mips.org>
      ab253839
  5. 09 6月, 2012 1 次提交
    • J
      lib: Proportions with flexible period · f3109a51
      Jan Kara 提交于
      Implement code computing proportions of events of different type (like code in
      lib/proportions.c) but allowing periods to have different lengths. This allows
      us to have aging periods of fixed wallclock time which gives better proportion
      estimates given the hugely varying throughput of different devices - previous
      measuring of aging period by number of events has the problem that a reasonable
      period length for a system with low-end USB stick is not a reasonable period
      length for a system with high-end storage array resulting either in too slow
      proportion updates or too fluctuating proportion updates.
      Acked-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Signed-off-by: NJan Kara <jack@suse.cz>
      Signed-off-by: NFengguang Wu <fengguang.wu@intel.com>
      f3109a51
  6. 27 5月, 2012 1 次提交
    • L
      lib: add generic strnlen_user() function · a08c5356
      Linus Torvalds 提交于
      This adds a new generic optimized strnlen_user() function that uses the
      <asm/word-at-a-time.h> infrastructure to portably do efficient string
      handling.
      
      In many ways, strnlen is much simpler than strncpy, and in particular we
      can always pre-align the words we load from memory.  That means that all
      the worries about alignment etc are a non-issue, so this one can easily
      be used on any architecture.  You obviously do have to do the
      appropriate word-at-a-time.h macros.
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      a08c5356
  7. 25 5月, 2012 1 次提交
  8. 02 5月, 2012 1 次提交
  9. 21 4月, 2012 1 次提交
    • W
      lib: add support for stmp-style devices · 4ccf4bea
      Wolfram Sang 提交于
      MX23/28 use IP cores which follow a register layout I have first seen on
      STMP3xxx SoCs. In this layout, every register actually has four u32:
      
       1.) to store a value directly
       2.) a SET register where every 1-bit sets the corresponding bit,
           others are unaffected
       3.) same with a CLR register
       4.) same with a TOG (toggle) register
      
      Also, the 2 MSBs in register 0 are always the same and can be used to reset
      the IP core.
      
      All this is strictly speaking not mach-specific (but IP core specific) and,
      thus, doesn't need to be in mach-mxs/include. At least mx6 also uses IP cores
      following this stmp-style. So:
      
      Introduce a stmp-style device, put the code and defines for that in a public
      place (lib/), and let drivers for stmp-style devices select that code.
      To avoid regressions and ease reviewing, the actual code is simply copied from
      mach-mxs. It definately wants updates, but those need a seperate patch series.
      
      Voila, mach dependency gone, reusable code introduced. Note that I didn't
      remove the duplicated code from mach-mxs yet, first the drivers have to be
      converted.
      Signed-off-by: NWolfram Sang <w.sang@pengutronix.de>
      Acked-by: NShawn Guo <shawn.guo@linaro.org>
      Acked-by: NDong Aisheng <dong.aisheng@linaro.org>
      4ccf4bea
  10. 02 2月, 2012 1 次提交
  11. 18 1月, 2012 1 次提交
  12. 14 12月, 2011 1 次提交
  13. 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
  14. 29 11月, 2011 1 次提交
  15. 09 11月, 2011 2 次提交
    • 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 - 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
  16. 04 10月, 2011 1 次提交
  17. 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
  18. 07 8月, 2011 1 次提交
  19. 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
  20. 04 6月, 2011 2 次提交
  21. 27 5月, 2011 1 次提交
  22. 19 5月, 2011 1 次提交
  23. 24 3月, 2011 1 次提交
  24. 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
  25. 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
  26. 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
  27. 25 1月, 2011 1 次提交
  28. 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
  29. 11 12月, 2010 1 次提交