1. 01 Feb, 2012 5 commits
  2. 19 Jan, 2012 1 commit
  3. 17 Jan, 2012 4 commits
  4. 13 Jan, 2012 2 commits
    • Sascha Hauer's avatar
      unlzo: fix input buffer free · 35f15268
      Sascha Hauer authored
      
      
      unlzo modifies the pointer to in_buf, so we have to free the original
      buffer, not the modified pointer.
      Signed-off-by: default avatarSascha Hauer <s.hauer@pengutronix.de>
      Cc: Lasse Collin <lasse.collin@tukaani.org>
      Cc: Namhyung Kim <namhyung@gmail.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      35f15268
    • Hugh Dickins's avatar
      radix_tree: take radix_tree_path off stack · e2bdb933
      Hugh Dickins authored
      
      
      Down, down in the deepest depths of GFP_NOIO page reclaim, we have
      shrink_page_list() calling __remove_mapping() calling __delete_from_
      swap_cache() or __delete_from_page_cache().
      
      You would not expect those to need much stack, but in fact they call
      radix_tree_delete(): which declares a 192-byte radix_tree_path array on
      its stack (to record the node,offsets it visits when descending, in case
      it needs to ascend to update them).  And if any tag is still set [1],
      that calls radix_tree_tag_clear(), which declares a further such
      192-byte radix_tree_path array on the stack.  (At least we have
      interrupts disabled here, so won't then be pushing registers too.)
      
      That was probably a good choice when most users were 32-bit (array of
      half the size), and adding fields to radix_tree_node would have bloated
      it unnecessarily.  But nowadays many are 64-bit, and each
      radix_tree_node contains a struct rcu_head, which is only used when
      freeing; whereas the radix_tree_path info is only used for updating the
      tree (deleting, clearing tags or setting tags if tagged) when a lock
      must be held, of no interest when accessing the tree locklessly.
      
      So add a parent pointer to the radix_tree_node, in union with the
      rcu_head, and remove all uses of the radix_tree_path.  There would be
      space in that union to save the offset when descending as before (we can
      argue that a lock must already be held to exclude other users), but
      recalculating it when ascending is both easy (a constant shift and a
      constant mask) and uncommon, so it seems better just to do that.
      
      Two little optimizations: no need to decrement height when descending,
      adjusting shift is enough; and once radix_tree_tag_if_tagged() has set
      tag on a node and its ancestors, it need not ascend from that node
      again.
      
      perf on the radix tree test harness reports radix_tree_insert() as 2%
      slower (now having to set parent), but radix_tree_delete() 24% faster.
      Surely that's an exaggeration from rtth's artificially low map shift 3,
      but forcing it back to 6 still rates radix_tree_delete() 8% faster.
      
      [1] Can a pagecache tag (dirty, writeback or towrite) actually still be
      set at the time of radix_tree_delete()? Perhaps not if the filesystem is
      well-behaved.  But although I've not tracked any stack overflow down to
      this cause, I have observed a curious case in which a dirty tag is set
      and left set on tmpfs: page migration's migrate_page_copy() happens to
      use __set_page_dirty_nobuffers() to set PageDirty on the newpage, and
      that sets PAGECACHE_TAG_DIRTY as a side-effect - harmless to a
      filesystem which doesn't use tags, except for this stack depth issue.
      Signed-off-by: default avatarHugh Dickins <hughd@google.com>
      Cc: Jan Kara <jack@suse.cz>
      Cc: Dave Chinner <david@fromorbit.com>
      Cc: Mel Gorman <mgorman@suse.de>
      Cc: Nai Xia <nai.xia@gmail.com>
      Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      e2bdb933
  5. 11 Jan, 2012 2 commits
  6. 06 Jan, 2012 1 commit
  7. 04 Jan, 2012 1 commit
  8. 21 Dec, 2011 1 commit
  9. 13 Dec, 2011 1 commit
  10. 10 Dec, 2011 1 commit
  11. 09 Dec, 2011 1 commit
    • Eric Dumazet's avatar
      sch_red: Adaptative RED AQM · 8af2a218
      Eric Dumazet authored
      Adaptative RED AQM for linux, based on paper from Sally FLoyd,
      Ramakrishna Gummadi, and Scott Shenker, August 2001 :
      
      http://icir.org/floyd/papers/adaptiveRed.pdf
      
      
      
      Goal of Adaptative RED is to make max_p a dynamic value between 1% and
      50% to reach the target average queue : (max_th - min_th) / 2
      
      Every 500 ms:
       if (avg > target and max_p <= 0.5)
        increase max_p : max_p += alpha;
       else if (avg < target and max_p >= 0.01)
        decrease max_p : max_p *= beta;
      
      target :[min_th + 0.4*(min_th - max_th),
                min_th + 0.6*(min_th - max_th)].
      alpha : min(0.01, max_p / 4)
      beta : 0.9
      max_P is a Q0.32 fixed point number (unsigned, with 32 bits mantissa)
      
      Changes against our RED implementation are :
      
      max_p is no longer a negative power of two (1/(2^Plog)), but a Q0.32
      fixed point number, to allow full range described in Adatative paper.
      
      To deliver a random number, we now use a reciprocal divide (thats really
      a multiply), but this operation is done once per marked/droped packet
      when in RED_BETWEEN_TRESH window, so added cost (compared to previous
      AND operation) is near zero.
      
      dump operation gives current max_p value in a new TCA_RED_MAX_P
      attribute.
      
      Example on a 10Mbit link :
      
      tc qdisc add dev $DEV parent 1:1 handle 10: est 1sec 8sec red \
         limit 400000 min 30000 max 90000 avpkt 1000 \
         burst 55 ecn adaptative bandwidth 10Mbit
      
      # tc -s -d qdisc show dev eth3
      ...
      qdisc red 10: parent 1:1 limit 400000b min 30000b max 90000b ecn
      adaptative ewma 5 max_p=0.113335 Scell_log 15
       Sent 50414282 bytes 34504 pkt (dropped 35, overlimits 1392 requeues 0)
       rate 9749Kbit 831pps backlog 72056b 16p requeues 0
        marked 1357 early 35 pdrop 0 other 0
      Signed-off-by: default avatarEric Dumazet <eric.dumazet@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      8af2a218
  12. 07 Dec, 2011 1 commit
  13. 06 Dec, 2011 3 commits
  14. 02 Dec, 2011 1 commit
  15. 29 Nov, 2011 1 commit
    • Tom Herbert's avatar
      dql: Dynamic queue limits · 75957ba3
      Tom Herbert authored
      
      
      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: default avatarTom Herbert <therbert@google.com>
      Acked-by: default avatarEric Dumazet <eric.dumazet@gmail.com>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      75957ba3
  16. 28 Nov, 2011 1 commit
  17. 24 Nov, 2011 1 commit
  18. 23 Nov, 2011 2 commits
  19. 21 Nov, 2011 2 commits
  20. 16 Nov, 2011 3 commits
  21. 09 Nov, 2011 5 commits
    • Dmitry Kasatkin's avatar
      crypto: digital signature verification support · 051dbb91
      Dmitry Kasatkin authored
      
      
      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: default avatarDmitry Kasatkin <dmitry.kasatkin@intel.com>
      Acked-by: default avatarMimi Zohar <zohar@us.ibm.com>
      051dbb91
    • Dmitry Kasatkin's avatar
      crypto: GnuPG based MPI lib - additional sources (part 4) · 7e8dec91
      Dmitry Kasatkin authored
      
      
      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: default avatarDmitry Kasatkin <dmitry.kasatkin@intel.com>
      7e8dec91
    • Dmitry Kasatkin's avatar
      crypto: GnuPG based MPI lib - make files (part 3) · d9c46b18
      Dmitry Kasatkin authored
      
      
      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: default avatarDmitry Kasatkin <dmitry.kasatkin@intel.com>
      d9c46b18
    • Dmitry Kasatkin's avatar
      crypto: GnuPG based MPI lib - header files (part 2) · 5ce3e312
      Dmitry Kasatkin authored
      
      
      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: default avatarDmitry Kasatkin <dmitry.kasatkin@intel.com>
      5ce3e312
    • Dmitry Kasatkin's avatar
      crypto: GnuPG based MPI lib - source files (part 1) · cdec9cb5
      Dmitry Kasatkin authored
      
      
      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: default avatarDmitry Kasatkin <dmitry.kasatkin@intel.com>
      cdec9cb5