1. 10 Oct, 2013 12 commits
    • Theodore Ts'o's avatar
      random: drop trickle mode · 95b709b6
      Theodore Ts'o authored
      The add_timer_randomness() used to drop into trickle mode when entropy
      pool was estimated to be 87.5% full.  This was important when
      add_timer_randomness() was used to sample interrupts.  It's not used
      for this any more --- add_interrupt_randomness() now uses fast_mix()
      instead.  By elimitating trickle mode, it allows us to fully utilize
      entropy provided by add_input_randomness() and add_disk_randomness()
      even when the input pool is above the old trickle threshold of 87.5%.
      
      This helps to answer the criticism in [1] in their hypothetical
      scenario where our entropy estimator was inaccurate, even though the
      measurements in [2] seem to indicate that our entropy estimator given
      real-life entropy collection is actually pretty good, albeit on the
      conservative side (which was as it was designed).
      
      [1] http://eprint.iacr.org/2013/338.pdf
      [2] http://eprint.iacr.org/2012/251.pdfSigned-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      95b709b6
    • Theodore Ts'o's avatar
      random: adjust the generator polynomials in the mixing function slightly · 6e9fa2c8
      Theodore Ts'o authored
      Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
      Videau in their paper, "The Linux Pseudorandom Number Generator
      Revisited" (see: http://eprint.iacr.org/2012/251.pdf).
      
      They suggested a slight change to improve our mixing functions
      slightly.  I also adjusted the comments to better explain what is
      going on, and to document why the polynomials were changed.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      6e9fa2c8
    • Theodore Ts'o's avatar
      random: speed up the fast_mix function by a factor of four · 655b2264
      Theodore Ts'o authored
      By mixing the entropy in chunks of 32-bit words instead of byte by
      byte, we can speed up the fast_mix function significantly.  Since it
      is called on every single interrupt, on systems with a very heavy
      interrupt load, this can make a noticeable difference.
      
      Also fix a compilation warning in add_interrupt_randomness() and avoid
      xor'ing cycles and jiffies together just in case we have an
      architecture which tries to define random_get_entropy() by returning
      jiffies.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      Reported-by: default avatarJörn Engel <joern@logfs.org>
      655b2264
    • Theodore Ts'o's avatar
      random: cap the rate which the /dev/urandom pool gets reseeded · f5c2742c
      Theodore Ts'o authored
      In order to avoid draining the input pool of its entropy at too high
      of a rate, enforce a minimum time interval between reseedings of the
      urandom pool.  This is set to 60 seconds by default.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      f5c2742c
    • Theodore Ts'o's avatar
      random: optimize the entropy_store structure · c59974ae
      Theodore Ts'o authored
      Use smaller types to slightly shrink the size of the entropy store
      structure.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      c59974ae
    • Theodore Ts'o's avatar
      random: optimize spinlock use in add_device_randomness() · 3ef4cb2d
      Theodore Ts'o authored
      The add_device_randomness() function calls mix_pool_bytes() twice for
      the input pool and the non-blocking pool, for a total of four times.
      By using _mix_pool_byte() and taking the spinlock in
      add_device_randomness(), we can halve the number of times we need
      take each pool's spinlock.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      3ef4cb2d
    • Theodore Ts'o's avatar
      random: fix the tracepoint for get_random_bytes(_arch) · 5910895f
      Theodore Ts'o authored
      Fix a problem where get_random_bytes_arch() was calling the tracepoint
      get_random_bytes().  So add a new tracepoint for
      get_random_bytes_arch(), and make get_random_bytes() and
      get_random_bytes_arch() call their correct tracepoint.
      
      Also, add a new tracepoint for add_device_randomness()
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      5910895f
    • H. Peter Anvin's avatar
      random: account for entropy loss due to overwrites · 30e37ec5
      H. Peter Anvin authored
      When we write entropy into a non-empty pool, we currently don't
      account at all for the fact that we will probabilistically overwrite
      some of the entropy in that pool.  This means that unless the pool is
      fully empty, we are currently *guaranteed* to overestimate the amount
      of entropy in the pool!
      
      Assuming Shannon entropy with zero correlations we end up with an
      exponentally decaying value of new entropy added:
      
      	entropy <- entropy + (pool_size - entropy) *
      		(1 - exp(-add_entropy/pool_size))
      
      However, calculations involving fractional exponentials are not
      practical in the kernel, so apply a piecewise linearization:
      
      	  For add_entropy <= pool_size/2 then
      
      	  (1 - exp(-add_entropy/pool_size)) >= (add_entropy/pool_size)*0.7869...
      
      	  ... so we can approximate the exponential with
      	  3/4*add_entropy/pool_size and still be on the
      	  safe side by adding at most pool_size/2 at a time.
      
      In order for the loop not to take arbitrary amounts of time if a bad
      ioctl is received, terminate if we are within one bit of full.  This
      way the loop is guaranteed to terminate after no more than
      log2(poolsize) iterations, no matter what the input value is.  The
      vast majority of the time the loop will be executed exactly once.
      
      The piecewise linearization is very conservative, approaching 3/4 of
      the usable input value for small inputs, however, our entropy
      estimation is pretty weak at best, especially for small values; we
      have no handle on correlation; and the Shannon entropy measure (Rényi
      entropy of order 1) is not the correct one to use in the first place,
      but rather the correct entropy measure is the min-entropy, the Rényi
      entropy of infinite order.
      
      As such, this conservatism seems more than justified.
      
      This does introduce fractional bit values.  I have left it to have 3
      bits of fraction, so that with a pool of 2^12 bits the multiply in
      credit_entropy_bits() can still fit into an int, as 2*(3+12) < 31.  It
      is definitely possible to allow for more fractional accounting, but
      that multiply then would have to be turned into a 32*32 -> 64 multiply.
      Signed-off-by: default avatarH. Peter Anvin <hpa@linux.intel.com>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      Cc: DJ Johnston <dj.johnston@intel.com>
      30e37ec5
    • H. Peter Anvin's avatar
      random: allow fractional bits to be tracked · a283b5c4
      H. Peter Anvin authored
      Allow fractional bits of entropy to be tracked by scaling the entropy
      counter (fixed point).  This will be used in a subsequent patch that
      accounts for entropy lost due to overwrites.
      
      [ Modified by tytso to fix up a few missing places where the
        entropy_count wasn't properly converted from fractional bits to
        bits. ]
      Signed-off-by: default avatarH. Peter Anvin <hpa@linux.intel.com>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      a283b5c4
    • H. Peter Anvin's avatar
      random: statically compute poolbitshift, poolbytes, poolbits · 9ed17b70
      H. Peter Anvin authored
      Use a macro to statically compute poolbitshift (will be used in a
      subsequent patch), poolbytes, and poolbits.  On virtually all
      architectures the cost of a memory load with an offset is the same as
      the one of a memory load.
      
      It is still possible for this to generate worse code since the C
      compiler doesn't know the fixed relationship between these fields, but
      that is somewhat unlikely.
      Signed-off-by: default avatarH. Peter Anvin <hpa@linux.intel.com>
      Signed-off-by: default avatarTheodore Ts'o <tytso@mit.edu>
      9ed17b70
    • Theodore Ts'o's avatar
      random: mix in architectural randomness earlier in extract_buf() · 85a1f777
      Theodore Ts'o authored
      Previously if CPU chip had a built-in random number generator (i.e.,
      RDRAND on newer x86 chips), we mixed it in at the very end of
      extract_buf() using an XOR operation.
      
      We now mix it in right after the calculate a hash across the entire
      pool.  This has the advantage that any contribution of entropy from
      the CPU's HWRNG will get mixed back into the pool.  In addition, it
      means that if the HWRNG has any defects (either accidentally or
      maliciously introduced), this will be mitigated via the non-linear
      transform of the SHA-1 hash function before we hand out generated
      output.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      85a1f777
    • Theodore Ts'o's avatar
      random: allow architectures to optionally define random_get_entropy() · 61875f30
      Theodore Ts'o authored
      Allow architectures which have a disabled get_cycles() function to
      provide a random_get_entropy() function which provides a fine-grained,
      rapidly changing counter that can be used by the /dev/random driver.
      
      For example, an architecture might have a rapidly changing register
      used to control random TLB cache eviction, or DRAM refresh that
      doesn't meet the requirements of get_cycles(), but which is good
      enough for the needs of the random driver.
      Signed-off-by: default avatar"Theodore Ts'o" <tytso@mit.edu>
      Cc: stable@vger.kernel.org
      61875f30
  2. 23 Sep, 2013 1 commit
  3. 02 Sep, 2013 4 commits
  4. 31 Aug, 2013 3 commits
    • Linus Torvalds's avatar
      Merge git://git.kernel.org/pub/scm/linux/kernel/git/davem/net · a8787645
      Linus Torvalds authored
      Pull networking fixes from David Miller:
      
       1) There was a simplification in the ipv6 ndisc packet sending
          attempted here, which avoided using memory accounting on the
          per-netns ndisc socket for sending NDISC packets.  It did fix some
          important issues, but it causes regressions so it gets reverted here
          too.  Specifically, the problem with this change is that the IPV6
          output path really depends upon there being a valid skb->sk
          attached.
      
          The reason we want to do this change in some form when we figure out
          how to do it right, is that if a device goes down the ndisc_sk
          socket send queue will fill up and block NDISC packets that we want
          to send to other devices too.  That's really bad behavior.
      
          Hopefully Thomas can come up with a better version of this change.
      
       2) Fix a severe TCP performance regression by reverting a change made
          to dev_pick_tx() quite some time ago.  From Eric Dumazet.
      
       3) TIPC returns wrongly signed error codes, fix from Erik Hugne.
      
       4) Fix OOPS when doing IPSEC over ipv4 tunnels due to orphaning the
          skb->sk too early.  Fix from Li Hongjun.
      
       5) RAW ipv4 sockets can use the wrong routing key during lookup, from
          Chris Clark.
      
       6) Similar to #1 revert an older change that tried to use plain
          alloc_skb() for SYN/ACK TCP packets, this broke the netfilter owner
          mark which needs to see the skb->sk for such frames.  From Phil
          Oester.
      
       7) BNX2x driver bug fixes from Ariel Elior and Yuval Mintz,
          specifically in the handling of virtual functions.
      
       8) IPSEC path error propagations to sockets is not done properly when
          we have v4 in v6, and v6 in v4 type rules.  Fix from Hannes Frederic
          Sowa.
      
       9) Fix missing channel context release in mac80211, from Johannes Berg.
      
      10) Fix network namespace handing wrt.  SCM_RIGHTS, from Andy
          Lutomirski.
      
      11) Fix usage of bogus NAPI weight in jme, netxen, and ps3_gelic
          drivers.  From Michal Schmidt.
      
      12) Hopefully a complete and correct fix for the genetlink dump locking
          and module reference counting.  From Pravin B Shelar.
      
      13) sk_busy_loop() must do a cpu_relax(), from Eliezer Tamir.
      
      14) Fix handling of timestamp offset when restoring a snapshotted TCP
          socket.  From Andrew Vagin.
      
      * git://git.kernel.org/pub/scm/linux/kernel/git/davem/net: (44 commits)
        net: fec: fix time stamping logic after napi conversion
        net: bridge: convert MLDv2 Query MRC into msecs_to_jiffies for max_delay
        mISDN: return -EINVAL on error in dsp_control_req()
        net: revert 8728c544 ("net: dev_pick_tx() fix")
        Revert "ipv6: Don't depend on per socket memory for neighbour discovery messages"
        ipv4 tunnels: fix an oops when using ipip/sit with IPsec
        tipc: set sk_err correctly when connection fails
        tcp: tcp_make_synack() should use sock_wmalloc
        bridge: separate querier and query timer into IGMP/IPv4 and MLD/IPv6 ones
        ipv6: Don't depend on per socket memory for neighbour discovery messages
        ipv4: sendto/hdrincl: don't use destination address found in header
        tcp: don't apply tsoffset if rcv_tsecr is zero
        tcp: initialize rcv_tstamp for restored sockets
        net: xilinx: fix memleak
        net: usb: Add HP hs2434 device to ZLP exception table
        net: add cpu_relax to busy poll loop
        net: stmmac: fixed the pbl setting with DT
        genl: Hold reference on correct module while netlink-dump.
        genl: Fix genl dumpit() locking.
        xfrm: Fix potential null pointer dereference in xdst_queue_output
        ...
      a8787645
    • Ian Campbell's avatar
      MAINTAINERS: change my DT related maintainer address · de80963e
      Ian Campbell authored
      Filtering capabilities on my work email are pretty much non-existent and this
      has turned out to be something of a firehose...
      
      Cc: Stephen Warren <swarren@wwwdotorg.org>
      Cc: Rob Herring <rob.herring@calxeda.com>
      Cc: Olof Johansson <olof@lixom.net>
      Cc: Linus Walleij <linus.walleij@linaro.org>
      Signed-off-by: default avatarIan Campbell <ian.campbell@citrix.com>
      Acked-by: default avatarPawel Moll <pawel.moll@arm.com>
      Acked-by: default avatarMark Rutland <mark.rutland@arm.com>
      Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
      de80963e
    • Linus Torvalds's avatar
      Merge tag 'sound-3.11' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound · 936dbcc3
      Linus Torvalds authored
      Pull sound fixes from Takashi Iwai:
       "This contains two Oops fixes (opti9xx and HD-audio) and a simple fixup
        for an Acer laptop.  All marked as stable patches"
      
      * tag 'sound-3.11' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound:
        ALSA: opti9xx: Fix conflicting driver object name
        ALSA: hda - Fix NULL dereference with CONFIG_SND_DYNAMIC_MINORS=n
        ALSA: hda - Add inverted digital mic fixup for Acer Aspire One
      936dbcc3
  5. 30 Aug, 2013 15 commits
  6. 29 Aug, 2013 5 commits