1. 12 5月, 2014 1 次提交
  2. 05 5月, 2014 1 次提交
    • C
      lib: Export interval_tree · a88cc108
      Chris Wilson 提交于
      lib/interval_tree.c provides a simple interface for an interval-tree
      (an augmented red-black tree) but is only built when testing the generic
      macros for building interval-trees. For drivers with modest needs,
      export the simple interval-tree library as is.
      
      v2: Lots of help from Michel Lespinasse to only compile the code
          as required:
          - make INTERVAL_TREE a config option
          - make INTERVAL_TREE_TEST select the library functions
            and sanitize the filenames & Makefile
          - prepare interval_tree for being built as a module if required
      Signed-off-by: NChris Wilson <chris@chris-wilson.co.uk>
      Cc: Michel Lespinasse <walken@google.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Reviewed-by: NMichel Lespinasse <walken@google.com>
      [Acked for inclusion via drm/i915 by Andrew Morton.]
      [danvet: switch to _GPL as per the mailing list discussion.]
      Signed-off-by: NDaniel Vetter <daniel.vetter@ffwll.ch>
      a88cc108
  3. 01 5月, 2014 1 次提交
  4. 20 3月, 2014 1 次提交
  5. 06 2月, 2014 1 次提交
  6. 24 1月, 2014 2 次提交
    • K
      test: check copy_to/from_user boundary validation · 3e2a4c18
      Kees Cook 提交于
      To help avoid an architecture failing to correctly check kernel/user
      boundaries when handling copy_to_user, copy_from_user, put_user, or
      get_user, perform some simple tests and fail to load if any of them
      behave unexpectedly.
      
      Specifically, this is to make sure there is a way to notice if things
      like what was fixed in commit 8404663f ("ARM: 7527/1: uaccess:
      explicitly check __user pointer when !CPU_USE_DOMAINS") ever regresses
      again, for any architecture.
      
      Additionally, adds new "user" selftest target, which loads this module.
      Signed-off-by: NKees Cook <keescook@chromium.org>
      Cc: Rusty Russell <rusty@rustcorp.com.au>
      Cc: Joe Perches <joe@perches.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      3e2a4c18
    • K
      test: add minimal module for verification testing · 93e9ef83
      Kees Cook 提交于
      This is a pair of test modules I'd like to see in the tree.  Instead of
      putting these in lkdtm, where I've been adding various tests that trigger
      crashes, these don't make sense there since they need to be either
      distinctly separate, or their pass/fail state don't need to crash the
      machine.
      
      These live in lib/ for now, along with a few other in-kernel test modules,
      and use the slightly more common "test_" naming convention, instead of
      "test-".  We should likely standardize on the former:
      
      $ find . -name 'test_*.c' | grep -v /tools/ | wc -l
      4
      $ find . -name 'test-*.c' | grep -v /tools/ | wc -l
      2
      
      The first is entirely a no-op module, designed to allow simple testing of
      the module loading and verification interface.  It's useful to have a
      module that has no other uses or dependencies so it can be reliably used
      for just testing module loading and verification.
      
      The second is a module that exercises the user memory access functions, in
      an effort to make sure that we can quickly catch any regressions in
      boundary checking (e.g.  like what was recently fixed on ARM).
      
      This patch (of 2):
      
      When doing module loading verification tests (for example, with module
      signing, or LSM hooks), it is very handy to have a module that can be
      built on all systems under test, isn't auto-loaded at boot, and has no
      device or similar dependencies.  This creates the "test_module.ko" module
      for that purpose, which only reports its load and unload to printk.
      Signed-off-by: NKees Cook <keescook@chromium.org>
      Acked-by: NRusty Russell <rusty@rustcorp.com.au>
      Cc: Joe Perches <joe@perches.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      93e9ef83
  7. 18 12月, 2013 1 次提交
    • F
      lib: introduce arch optimized hash library · 71ae8aac
      Francesco Fusco 提交于
      We introduce a new hashing library that is meant to be used in
      the contexts where speed is more important than uniformity of the
      hashed values. The hash library leverages architecture specific
      implementation to achieve high performance and fall backs to
      jhash() for the generic case.
      
      On Intel-based x86 architectures, the library can exploit the crc32l
      instruction, part of the Intel SSE4.2 instruction set, if the
      instruction is supported by the processor. This implementation
      is twice as fast as the jhash() implementation on an i7 processor.
      
      Additional architectures, such as Arm64 provide instructions for
      accelerating the computation of CRC, so they could be added as well
      in follow-up work.
      Signed-off-by: NFrancesco Fusco <ffusco@redhat.com>
      Signed-off-by: NDaniel Borkmann <dborkman@redhat.com>
      Signed-off-by: NThomas Graf <tgraf@redhat.com>
      Cc: linux-kernel@vger.kernel.org
      Signed-off-by: NDavid S. Miller <davem@davemloft.net>
      71ae8aac
  8. 20 11月, 2013 1 次提交
  9. 13 11月, 2013 1 次提交
  10. 06 11月, 2013 3 次提交
  11. 24 9月, 2013 1 次提交
    • D
      Add a generic associative array implementation. · 3cb98950
      David Howells 提交于
      Add a generic associative array implementation that can be used as the
      container for keyrings, thereby massively increasing the capacity available
      whilst also speeding up searching in keyrings that contain a lot of keys.
      
      This may also be useful in FS-Cache for tracking cookies.
      
      Documentation is added into Documentation/associative_array.txt
      
      Some of the properties of the implementation are:
      
       (1) Objects are opaque pointers.  The implementation does not care where they
           point (if anywhere) or what they point to (if anything).
      
           [!] NOTE: Pointers to objects _must_ be zero in the two least significant
           	       bits.
      
       (2) Objects do not need to contain linkage blocks for use by the array.  This
           permits an object to be located in multiple arrays simultaneously.
           Rather, the array is made up of metadata blocks that point to objects.
      
       (3) Objects are labelled as being one of two types (the type is a bool value).
           This information is stored in the array, but has no consequence to the
           array itself or its algorithms.
      
       (4) Objects require index keys to locate them within the array.
      
       (5) Index keys must be unique.  Inserting an object with the same key as one
           already in the array will replace the old object.
      
       (6) Index keys can be of any length and can be of different lengths.
      
       (7) Index keys should encode the length early on, before any variation due to
           length is seen.
      
       (8) Index keys can include a hash to scatter objects throughout the array.
      
       (9) The array can iterated over.  The objects will not necessarily come out in
           key order.
      
      (10) The array can be iterated whilst it is being modified, provided the RCU
           readlock is being held by the iterator.  Note, however, under these
           circumstances, some objects may be seen more than once.  If this is a
           problem, the iterator should lock against modification.  Objects will not
           be missed, however, unless deleted.
      
      (11) Objects in the array can be looked up by means of their index key.
      
      (12) Objects can be looked up whilst the array is being modified, provided the
           RCU readlock is being held by the thread doing the look up.
      
      The implementation uses a tree of 16-pointer nodes internally that are indexed
      on each level by nibbles from the index key.  To improve memory efficiency,
      shortcuts can be emplaced to skip over what would otherwise be a series of
      single-occupancy nodes.  Further, nodes pack leaf object pointers into spare
      space in the node rather than making an extra branch until as such time an
      object needs to be added to a full node.
      Signed-off-by: NDavid Howells <dhowells@redhat.com>
      3cb98950
  12. 10 9月, 2013 1 次提交
    • K
      idr: Percpu ida · 798ab48e
      Kent Overstreet 提交于
      Percpu frontend for allocating ids. With percpu allocation (that works),
      it's impossible to guarantee it will always be possible to allocate all
      nr_tags - typically, some will be stuck on a remote percpu freelist
      where the current job can't get to them.
      
      We do guarantee that it will always be possible to allocate at least
      (nr_tags / 2) tags - this is done by keeping track of which and how many
      cpus have tags on their percpu freelists. On allocation failure if
      enough cpus have tags that there could potentially be (nr_tags / 2) tags
      stuck on remote percpu freelists, we then pick a remote cpu at random to
      steal from.
      
      Note that there's no cpu hotplug notifier - we don't care, because
      steal_tags() will eventually get the down cpu's tags. We _could_ satisfy
      more allocations if we had a notifier - but we'll still meet our
      guarantees and it's absolutely not a correctness issue, so I don't think
      it's worth the extra code.
      
      From akpm:
      
          "It looks OK to me (that's as close as I get to an ack :))
      
      v6 changes:
        - Add #include <linux/cpumask.h> to include/linux/percpu_ida.h to
          make alpha/arc builds happy (Fengguang)
        - Move second (cpu >= nr_cpu_ids) check inside of first check scope
          in steal_tags() (akpm + nab)
      
      v5 changes:
        - Change percpu_ida->cpus_have_tags to cpumask_t (kmo + akpm)
        - Add comment for percpu_ida_cpu->lock + ->nr_free (kmo + akpm)
        - Convert steal_tags() to use cpumask_weight() + cpumask_next() +
          cpumask_first() + cpumask_clear_cpu() (kmo + akpm)
        - Add comment for alloc_global_tags() (kmo + akpm)
        - Convert percpu_ida_alloc() to use cpumask_set_cpu() (kmo + akpm)
        - Convert percpu_ida_free() to use cpumask_set_cpu() (kmo + akpm)
        - Drop percpu_ida->cpus_have_tags allocation in percpu_ida_init()
          (kmo + akpm)
        - Drop percpu_ida->cpus_have_tags kfree in percpu_ida_destroy()
          (kmo + akpm)
        - Add comment for percpu_ida_alloc @ gfp (kmo + akpm)
        - Move to percpu_ida.c + percpu_ida.h (kmo + akpm + nab)
      
      v4 changes:
      
        - Fix tags.c reference in percpu_ida_init (akpm)
      Signed-off-by: NKent Overstreet <kmo@daterainc.com>
      Cc: Tejun Heo <tj@kernel.org>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: Christoph Lameter <cl@linux-foundation.org>
      Cc: Ingo Molnar <mingo@redhat.com>
      Cc: Andi Kleen <andi@firstfloor.org>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Nicholas A. Bellinger" <nab@linux-iscsi.org>
      Signed-off-by: NNicholas Bellinger <nab@linux-iscsi.org>
      798ab48e
  13. 03 9月, 2013 1 次提交
  14. 10 7月, 2013 3 次提交
    • C
      lib: add lz4 compressor module · c72ac7a1
      Chanho Min 提交于
      This patchset is for supporting LZ4 compression and the crypto API using
      it.
      
      As shown below, the size of data is a little bit bigger but compressing
      speed is faster under the enabled unaligned memory access.  We can use
      lz4 de/compression through crypto API as well.  Also, It will be useful
      for another potential user of lz4 compression.
      
      lz4 Compression Benchmark:
      Compiler: ARM gcc 4.6.4
      ARMv7, 1 GHz based board
         Kernel: linux 3.4
         Uncompressed data Size: 101 MB
               Compressed Size  compression Speed
         LZO   72.1MB		  32.1MB/s, 33.0MB/s(UA)
         LZ4   75.1MB		  30.4MB/s, 35.9MB/s(UA)
         LZ4HC 59.8MB		   2.4MB/s,  2.5MB/s(UA)
      - UA: Unaligned memory Access support
      - Latest patch set for LZO applied
      
      This patch:
      
      Add support for LZ4 compression in the Linux Kernel.  LZ4 Compression APIs
      for kernel are based on LZ4 implementation by Yann Collet and were changed
      for kernel coding style.
      
      LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
      LZ4 source repository : http://code.google.com/p/lz4/
      svn revision : r90
      
      Two APIs are added:
      
      lz4_compress() support basic lz4 compression whereas lz4hc_compress()
      support high compression or CPU performance get lower but compression
      ratio get higher.  Also, we require the pre-allocated working memory with
      the defined size and destination buffer must be allocated with the size of
      lz4_compressbound.
      
      [akpm@linux-foundation.org: make lz4_compresshcctx() static]
      Signed-off-by: NChanho Min <chanho.min@lge.com>
      Cc: "Darrick J. Wong" <djwong@us.ibm.com>
      Cc: Bob Pearson <rpearson@systemfabricworks.com>
      Cc: Richard Weinberger <richard@nod.at>
      Cc: Herbert Xu <herbert@gondor.hengli.com.au>
      Cc: Yann Collet <yann.collet.73@gmail.com>
      Cc: Kyungsik Lee <kyungsik.lee@lge.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      c72ac7a1
    • K
      lib: add support for LZ4-compressed kernel · e76e1fdf
      Kyungsik Lee 提交于
      Add support for extracting LZ4-compressed kernel images, as well as
      LZ4-compressed ramdisk images in the kernel boot process.
      Signed-off-by: NKyungsik Lee <kyungsik.lee@lge.com>
      Cc: "H. Peter Anvin" <hpa@zytor.com>
      Cc: Ingo Molnar <mingo@elte.hu>
      Cc: Thomas Gleixner <tglx@linutronix.de>
      Cc: Russell King <rmk@arm.linux.org.uk>
      Cc: Borislav Petkov <bp@alien8.de>
      Cc: Florian Fainelli <florian@openwrt.org>
      Cc: Yann Collet <yann.collet.73@gmail.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      e76e1fdf
    • C
      lib: add weak clz/ctz functions · 4df87bb7
      Chanho Min 提交于
      Some architectures need __c[lt]z[sd]i2() for __builtin_c[lt]z[ll] and
      that causes a build failure.  They can be implemented using the
      fls()/__ffs() and overridden by linking arch-specific versions may not
      be implemented yet.
      
      This is required by "lib: add lz4 compressor module".
      
      Reference: https://lkml.org/lkml/2013/4/18/603Signed-off-by: NChanho Min <chanho.min@lge.com>
      Reported-by: NGeert Uytterhoeven <geert@linux-m68k.org>
      Cc: "Darrick J. Wong" <djwong@us.ibm.com>
      Cc: Bob Pearson <rpearson@systemfabricworks.com>
      Cc: Richard Weinberger <richard@nod.at>
      Cc: Herbert Xu <herbert@gondor.hengli.com.au>
      Cc: Yann Collet <yann.collet.73@gmail.com>
      Cc: Kyungsik Lee <kyungsik.lee@lge.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      4df87bb7
  15. 28 6月, 2013 1 次提交
    • G
      lib: Move fonts from drivers/video/console/ to lib/fonts/ · ee89bd6b
      Geert Uytterhoeven 提交于
      Several drivers need font support independent of CONFIG_VT, cfr. commit
      9cbce8d7e1dae0744ca4f68d62aa7de18196b6f4, "console/font: Refactor font
      support code selection logic").
      Hence move the fonts and their support logic from drivers/video/console/ to
      its own library directory lib/fonts/.
      This also allows to limit processing of drivers/video/console/Makefile to
      CONFIG_VT=y again.
      
      [Kevin Hilman <khilman@linaro.org>: Update arch/arm/boot/compressed/Makefile]
      Signed-off-by: NGeert Uytterhoeven <geert@linux-m68k.org>
      ee89bd6b
  16. 06 6月, 2013 1 次提交
  17. 04 6月, 2013 1 次提交
    • K
      percpu: implement generic percpu refcounting · 215e262f
      Kent Overstreet 提交于
      This implements a refcount with similar semantics to
      atomic_get()/atomic_dec_and_test() - but percpu.
      
      It also implements two stage shutdown, as we need it to tear down the
      percpu counts.  Before dropping the initial refcount, you must call
      percpu_ref_kill(); this puts the refcount in "shutting down mode" and
      switches back to a single atomic refcount with the appropriate
      barriers (synchronize_rcu()).
      
      It's also legal to call percpu_ref_kill() multiple times - it only
      returns true once, so callers don't have to reimplement shutdown
      synchronization.
      
      [akpm@linux-foundation.org: fix build]
      [akpm@linux-foundation.org: coding-style tweak]
      Signed-off-by: NKent Overstreet <koverstreet@google.com>
      Cc: Zach Brown <zab@redhat.com>
      Cc: Felipe Balbi <balbi@ti.com>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Mark Fasheh <mfasheh@suse.com>
      Cc: Joel Becker <jlbec@evilplan.org>
      Cc: Rusty Russell <rusty@rustcorp.com.au>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: Asai Thambi S P <asamymuthupa@micron.com>
      Cc: Selvan Mani <smani@micron.com>
      Cc: Sam Bradshaw <sbradshaw@micron.com>
      Cc: Jeff Moyer <jmoyer@redhat.com>
      Cc: Al Viro <viro@zeniv.linux.org.uk>
      Cc: Benjamin LaHaise <bcrl@kvack.org>
      Cc: Tejun Heo <tj@kernel.org>
      Cc: Oleg Nesterov <oleg@redhat.com>
      Cc: Christoph Lameter <cl@linux-foundation.org>
      Cc: Ingo Molnar <mingo@redhat.com>
      Reviewed-by: N"Theodore Ts'o" <tytso@mit.edu>
      Signed-off-by: NTejun Heo <tj@kernel.org>
      215e262f
  18. 24 5月, 2013 1 次提交
  19. 20 5月, 2013 1 次提交
  20. 01 5月, 2013 2 次提交
    • S
      Kconfig: consolidate CONFIG_DEBUG_STRICT_USER_COPY_CHECKS · 446f24d1
      Stephen Boyd 提交于
      The help text for this config is duplicated across the x86, parisc, and
      s390 Kconfig.debug files.  Arnd Bergman noted that the help text was
      slightly misleading and should be fixed to state that enabling this
      option isn't a problem when using pre 4.4 gcc.
      
      To simplify the rewording, consolidate the text into lib/Kconfig.debug
      and modify it there to be more explicit about when you should say N to
      this config.
      
      Also, make the text a bit more generic by stating that this option
      enables compile time checks so we can cover architectures which emit
      warnings vs.  ones which emit errors.  The details of how an
      architecture decided to implement the checks isn't as important as the
      concept of compile time checking of copy_from_user() calls.
      
      While we're doing this, remove all the copy_from_user_overflow() code
      that's duplicated many times and place it into lib/ so that any
      architecture supporting this option can get the function for free.
      Signed-off-by: NStephen Boyd <sboyd@codeaurora.org>
      Acked-by: NArnd Bergmann <arnd@arndb.de>
      Acked-by: NIngo Molnar <mingo@kernel.org>
      Acked-by: NH. Peter Anvin <hpa@zytor.com>
      Cc: Arjan van de Ven <arjan@linux.intel.com>
      Acked-by: NHelge Deller <deller@gmx.de>
      Cc: Heiko Carstens <heiko.carstens@de.ibm.com>
      Cc: Stephen Rothwell <sfr@canb.auug.org.au>
      Cc: Chris Metcalf <cmetcalf@tilera.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      446f24d1
    • A
      lib/string_helpers: introduce generic string_unescape · 16c7fa05
      Andy Shevchenko 提交于
      There are several places in kernel where modules unescapes input to convert
      C-Style Escape Sequences into byte codes.
      
      The patch provides generic implementation of such approach. Test cases are
      also included into the patch.
      
      [akpm@linux-foundation.org: clarify comment]
      [akpm@linux-foundation.org: export get_random_int() to modules]
      Signed-off-by: NAndy Shevchenko <andriy.shevchenko@linux.intel.com>
      Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>
      Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
      Cc: Jason Baron <jbaron@redhat.com>
      Cc: Alexander Viro <viro@zeniv.linux.org.uk>
      Cc: William Hubbs <w.d.hubbs@gmail.com>
      Cc: Chris Brannon <chris@the-brannons.com>
      Cc: Kirk Reiser <kirk@braille.uwo.ca>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      16c7fa05
  21. 16 4月, 2013 1 次提交
  22. 28 2月, 2013 1 次提交
  23. 18 12月, 2012 2 次提交
    • O
      percpu_rw_semaphore: introduce CONFIG_PERCPU_RWSEM · 22b361d1
      Oleg Nesterov 提交于
      Currently only block_dev and uprobes use percpu_rw_semaphore,
      add the config option selected by BLOCK || UPROBES.
      Signed-off-by: NOleg Nesterov <oleg@redhat.com>
      Cc: Anton Arapov <anton@redhat.com>
      Cc: Ingo Molnar <mingo@elte.hu>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Michal Marek <mmarek@suse.cz>
      Cc: Mikulas Patocka <mpatocka@redhat.com>
      Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      22b361d1
    • O
      percpu_rw_semaphore: reimplement to not block the readers unnecessarily · a1fd3e24
      Oleg Nesterov 提交于
      Currently the writer does msleep() plus synchronize_sched() 3 times to
      acquire/release the semaphore, and during this time the readers are
      blocked completely.  Even if the "write" section was not actually started
      or if it was already finished.
      
      With this patch down_write/up_write does synchronize_sched() twice and
      down_read/up_read are still possible during this time, just they use the
      slow path.
      
      percpu_down_write() first forces the readers to use rw_semaphore and
      increment the "slow" counter to take the lock for reading, then it
      takes that rw_semaphore for writing and blocks the readers.
      
      Also.  With this patch the code relies on the documented behaviour of
      synchronize_sched(), it doesn't try to pair synchronize_sched() with
      barrier.
      Signed-off-by: NOleg Nesterov <oleg@redhat.com>
      Reviewed-by: NPaul E. McKenney <paulmck@linux.vnet.ibm.com>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Cc: Mikulas Patocka <mpatocka@redhat.com>
      Cc: Peter Zijlstra <peterz@infradead.org>
      Cc: Ingo Molnar <mingo@elte.hu>
      Cc: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
      Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
      Cc: Anton Arapov <anton@redhat.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      a1fd3e24
  24. 14 12月, 2012 1 次提交
  25. 06 12月, 2012 1 次提交
    • T
      lib/Makefile: Fix oid_registry build dependency · 527897cc
      Tim Gardner 提交于
      It is $(obj)/oid_registry.o that is dependent on $(obj)/oid_registry_data.c.
      The object file cannot be built until $(obj)/oid_registry_data.c has been
      generated.
      
      A periodic and hard to reproduce parallel build failure is due to
      this incorrect lib/Makefile dependency. The compile error is completely
      disingenuous.
      
        GEN     lib/oid_registry_data.c
      Compiling 49 OIDs
        CC      lib/oid_registry.o
      gcc: error: lib/oid_registry.c: No such file or directory
      gcc: fatal error: no input files
      compilation terminated.
      make[3]: *** [lib/oid_registry.o] Error 4
      
      Cc: Andrew Morton <akpm@linux-foundation.org>
      Cc: Akinobu Mita <akinobu.mita@gmail.com>
      Cc: Michel Lespinasse <walken@google.com>
      Cc: David Howells <dhowells@redhat.com>
      Cc: "David S. Miller" <davem@davemloft.net>
      Signed-off-by: NTim Gardner <tim.gardner@canonical.com>
      Signed-off-by: NRusty Russell <rusty@rustcorp.com.au>
      527897cc
  26. 29 11月, 2012 1 次提交
  27. 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
  28. 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
  29. 01 10月, 2012 1 次提交
  30. 31 7月, 2012 1 次提交