Linux-Crypto Archive on lore.kernel.org
 help / color / Atom feed
From: Linus Torvalds <torvalds@linux-foundation.org>
To: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "David S. Miller" <davem@davemloft.net>,
	Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
	Linux Crypto Mailing List <linux-crypto@vger.kernel.org>
Subject: Re: Crypto Fixes for 3.3
Date: Wed, 25 Jan 2012 19:35:19 -0800
Message-ID: <CA+55aFzFecPSQverH7VQBDZY+gS7_RALwh3W4oqWLbWBcBzLqg@mail.gmail.com> (raw)
In-Reply-To: <20120126024342.GA12492@gondor.apana.org.au>

On Wed, Jan 25, 2012 at 6:43 PM, Herbert Xu <herbert@gondor.apana.org.au> wrote:
>
> This push fixes a race condition in sha512 that affects users
> who use it in process context and softirq context concurrently,
> in particular, this affects IPsec.  The result of the race is
> the production of incorrect hashes, which for IPsec leands to
> loss of connectivity.

Ugh. This once more has the crazy signed integer modulus operator,
which can be quite expensive depending on whether the compiler can
tell whether it is always positive or not.

Also, that modulus is exposed everywhere.

In git, the sha1 implementation (which has many of the same issues) does this:

  /* This "rolls" over the 512-bit array */
  #define W(x) (array[(x)&15])

which means that the modulus exists in just one place (and is the
correct binary 'and', not the possibly-expensive division).

We also avoid the problem with absolutely horrible gcc register usage
by having an arch-specific "accessor macro":

  /*
   * If you have 32 registers or more, the compiler can (and should)
   * try to change the array[] accesses into registers. However, on
   * machines with less than ~25 registers, that won't really work,
   * and at least gcc will make an unholy mess of it.
   *
   * So to avoid that mess which just slows things down, we force
   * the stores to memory to actually happen (we might be better off
   * with a 'W(t)=(val);asm("":"+m" (W(t))' there instead, as
   * suggested by Artur Skawina - that will also make gcc unable to
   * try to do the silly "optimize away loads" part because it won't
   * see what the value will be).
   *
   * Ben Herrenschmidt reports that on PPC, the C version comes close
   * to the optimized asm with this (ie on PPC you don't want that
   * 'volatile', since there are lots of registers).
   *
   * On ARM we get the best code generation by forcing a full memory barrier
   * between each SHA_ROUND, otherwise gcc happily get wild with spilling and
   * the stack frame size simply explode and performance goes down the drain.
   */

  #if defined(__i386__) || defined(__x86_64__)
    #define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))
  #elif defined(__GNUC__) && defined(__arm__)
    #define setW(x, val) do { W(x) = (val); __asm__("":::"memory"); } while (0)
  #else
    #define setW(x, val) (W(x) = (val))
  #endif

which is not pretty, but as you guys found out, the alternative can be
much worse (ie totally crazy gcc register spilling)

                    Linus

  reply index

Thread overview: 246+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-12-25  0:17 Crypto Update for 2.6.29 Herbert Xu
2008-12-25  0:20 ` Herbert Xu
2009-03-24  4:49   ` Crypto Update for 2.6.30 Herbert Xu
     [not found]   ` <20090324044932.GA18245@gondor.apana.org.au>
2009-04-02  6:14     ` Herbert Xu
2009-05-17 22:28       ` Herbert Xu
2009-05-31 13:12         ` Herbert Xu
2009-06-13  2:05     ` Crypto Update for 2.6.31 Herbert Xu
2009-06-21 14:09       ` Crypto Fixes " Herbert Xu
2009-09-02 22:03         ` Herbert Xu
2009-09-10 14:19       ` Crypto Update for 2.6.32 Herbert Xu
     [not found]       ` <20090910141905.GA17948@gondor.apana.org.au>
2009-10-20  6:54         ` Crypto Fixes " Herbert Xu
2009-10-20  7:26           ` Herbert Xu
2009-11-23 12:05             ` Herbert Xu
2009-12-30  2:12           ` Crypto Fixes for 2.6.33 Herbert Xu
2010-02-01 19:52             ` Herbert Xu
     [not found]             ` <20100201195204.GA6953@gondor.apana.org.au>
2010-03-05  7:10               ` Crypto Fixes for 2.6.34 Herbert Xu
     [not found]               ` <20100305071043.GA3548@gondor.apana.org.au>
2010-04-27 13:55                 ` Herbert Xu
2010-06-03 10:05                   ` Crypto Fixes for 2.6.35 Herbert Xu
2010-06-03 16:26                     ` Linus Torvalds
2010-06-03 21:56                       ` Herbert Xu
2010-07-16  2:26                     ` Herbert Xu
2010-07-22  5:50                       ` Herbert Xu
2010-07-23  5:17                         ` Lee Nipper
2010-07-23  7:27                           ` Herbert Xu
2010-07-23 13:17                             ` Lee Nipper
2010-09-03  6:00                         ` Herbert Xu
2010-09-03 11:07                           ` Crypto Fixes for 2.6.36 Herbert Xu
2010-12-15 11:50                             ` Crypto Fixes for 2.6.37 Herbert Xu
2010-12-15 20:40                               ` Linus Torvalds
2010-12-16  0:49                                 ` Herbert Xu
2010-12-16  0:58                                   ` Herbert Xu
2011-02-16  5:39                               ` Crypto Fixes for 2.6.38 Herbert Xu
     [not found]                               ` <20110216053911.GA10999@gondor.apana.org.au>
2011-03-28  7:13                                 ` Crypto Fixes for 2.6.39 Herbert Xu
2011-06-29 23:51                                   ` Crypto Fixes for 3.0 Herbert Xu
2011-10-21  8:22                                     ` Crypto Fixes for 3.1 Herbert Xu
2011-10-21  9:41                                       ` David Rientjes
2011-10-21 11:35                                         ` Herbert Xu
2011-11-10 23:00                                       ` Crypto Fixes for 3.2 Herbert Xu
2011-11-26  2:34                                         ` Herbert Xu
2012-01-26  2:43                                     ` Crypto Fixes for 3.3 Herbert Xu
2012-01-26  3:35                                       ` Linus Torvalds [this message]
2012-01-26  4:07                                         ` Herbert Xu
2012-01-26  4:16                                           ` Linus Torvalds
2012-02-14  3:35                                       ` Herbert Xu
2012-02-16  5:32                                         ` Herbert Xu
2012-03-03  5:36                                           ` Herbert Xu
2012-03-22  1:20                                       ` Crypto Fixes for 3.4 Herbert Xu
2012-04-02  9:45                                         ` Herbert Xu
2012-04-20 14:16                                           ` Herbert Xu
2012-06-11 13:00                                         ` Crypto Fixes for 3.5 Herbert Xu
2012-06-18  8:24                                           ` Herbert Xu
2012-08-23  8:32                                       ` Crypto Fixes for 3.6 Herbert Xu
2012-09-11  4:10                                         ` Herbert Xu
2012-11-09  9:30                                         ` Crypto Fixes for 3.7 Herbert Xu
2013-03-28  8:28                                           ` Crypto Fixes for 3.9 Herbert Xu
2013-03-28 13:05                                             ` Chaoxing Lin
2013-03-28 13:52                                               ` Herbert Xu
2013-04-10  2:21                                             ` Herbert Xu
2013-04-22  0:34                                               ` Herbert Xu
2013-05-28  5:52                                             ` Crypto Fixes for 3.10 Herbert Xu
2013-06-10  9:05                                               ` Herbert Xu
2013-06-20 13:29                                                 ` Herbert Xu
2013-06-27 13:02                                                   ` Herbert Xu
2013-07-24  7:23                                             ` Crypto Fixes for 3.11 Herbert Xu
2013-09-13 11:30                                             ` Crypto Fixes for 3.12 Herbert Xu
2013-09-13 14:22                                               ` Linus Torvalds
2013-09-13 14:39                                                 ` Herbert Xu
2013-12-03 12:41                                             ` Crypto Fixes for 3.13 Herbert Xu
2013-12-09 11:57                                               ` Herbert Xu
2014-01-01  6:10                                                 ` Herbert Xu
2014-02-03 12:59                                                   ` Crypto Fixes for 3.14 Herbert Xu
2014-04-13 23:34                                                     ` Crypto Fixes for 3.15 Herbert Xu
2014-05-13 11:02                                                       ` Herbert Xu
2014-05-21 12:22                                                         ` Herbert Xu
2014-07-10  9:03                                                     ` Crypto Fixes for 3.16 Herbert Xu
2014-07-18 10:57                                                       ` Herbert Xu
2014-07-28 14:05                                                         ` Herbert Xu
2014-07-31 13:59                                                           ` Herbert Xu
2014-09-15 11:35                                                       ` Crypto Fixes for 3.17 Herbert Xu
2014-09-24 13:27                                                         ` Herbert Xu
2014-11-10  8:57                                                           ` Crypto Fixes for 3.18 Herbert Xu
2014-12-31  3:32                                                     ` Crypto Fixes for 3.19 Herbert Xu
2015-01-07  2:17                                                       ` Herbert Xu
2015-01-20  0:52                                                         ` Herbert Xu
2015-03-09  5:19                                                         ` Crypto Fixes for 4.0 Herbert Xu
2015-03-18  5:25                                                           ` Herbert Xu
2015-03-18 18:12                                                             ` Linus Torvalds
2015-04-25  8:03                                                         ` Crypto Fixes for 4.1 Herbert Xu
2015-05-05 10:06                                                           ` Herbert Xu
2015-05-11  5:56                                                             ` Herbert Xu
2015-05-20  6:54                                                               ` Herbert Xu
2015-05-22  4:05                                                                 ` Herbert Xu
2015-05-22 21:29                                                                   ` Linus Torvalds
2015-05-22 21:39                                                                     ` Herbert Xu
2015-05-26  8:43                                                                   ` Herbert Xu
2015-06-18  3:43                                                                     ` Herbert Xu
2010-09-04 10:45                           ` Crypto Fixes for 2.6.35 Chuck Ebbert
2010-09-04 12:22                             ` Herbert Xu
2010-11-13 12:59               ` Crypto Fixes for 2.6.37 Herbert Xu
2009-12-04 13:55     ` Crypto Update for 2.6.33 Herbert Xu
2010-02-26  0:49       ` Crypto Update for 2.6.34 Herbert Xu
2010-03-01  7:50         ` tip: origin tree boot crash Ingo Molnar
2010-03-01 14:55           ` Steffen Klassert
2010-03-03 14:42             ` Herbert Xu
2010-03-04  3:00               ` Ingo Molnar
2010-03-04  5:31                 ` Herbert Xu
2010-05-19  2:06         ` Crypto Update for 2.6.35 Herbert Xu
2010-05-21 10:44           ` Herbert Xu
2010-08-04 14:04             ` Crypto Update for 2.6.36 Herbert Xu
2010-10-24  6:16               ` Crypto Update for 2.6.37 Herbert Xu
     [not found]               ` <20101024061625.GA23715@gondor.apana.org.au>
2011-01-06  0:01                 ` Crypto Update for 2.6.38 Herbert Xu
2011-01-06 18:05                   ` Linus Torvalds
2011-01-06 21:16                     ` Herbert Xu
2011-01-06 21:23                       ` Linus Torvalds
2011-01-06 21:39                         ` Herbert Xu
2011-01-06 22:13                           ` Linus Torvalds
2011-01-06 22:30                             ` Herbert Xu
2011-01-06 22:33                               ` David Miller
2011-01-06 22:43                               ` Linus Torvalds
2011-01-06 22:53                                 ` Herbert Xu
2011-01-06 23:25                                   ` Linus Torvalds
2011-01-07  0:14                                     ` Herbert Xu
2011-01-07  2:43                                       ` David Miller
2011-01-07  3:04                                         ` Herbert Xu
2011-01-07  2:39                                   ` Pavel Roskin
2011-01-07  3:03                                     ` Herbert Xu
2011-01-07 12:04                             ` Neil Horman
2011-01-08 13:23                               ` Nikos Mavrogiannopoulos
2011-01-10 12:03                                 ` Neil Horman
2011-01-10 19:05                                   ` Dag Arne Osvik
2011-01-06 21:46                       ` Pavel Roskin
2011-01-06 21:49                         ` Herbert Xu
2011-01-06 23:02                         ` Mihai Donțu
2011-01-13  1:44                   ` Herbert Xu
2011-03-15 14:59                   ` Crypto Update for 2.6.39 Herbert Xu
2011-05-20 23:54                     ` Crypto Update for 2.6.40 Herbert Xu
2011-07-24  1:17                       ` Crypto Update for 3.1 Herbert Xu
2011-10-31  4:09                         ` Crypto Update for 3.2 Herbert Xu
2011-10-31 16:42                           ` Randy Dunlap
2011-10-31 17:16                             ` Linus Torvalds
2011-11-01  3:48                               ` Herbert Xu
2012-01-06  4:12                           ` Crypto Update for 3.3 Herbert Xu
2012-01-11 22:19                             ` Herbert Xu
2012-03-20  3:27                             ` Herbert Xu
2012-05-23  1:35                               ` Crypto Update for 3.5 Herbert Xu
2012-05-23 23:06                                 ` Linus Torvalds
2012-05-24  0:21                                   ` Herbert Xu
2012-05-24  8:36                                     ` Arnd Bergmann
2012-05-24  7:03                                   ` Linus Walleij
2012-07-25  8:41                                 ` Crypto Update for 3.6 Herbert Xu
2012-10-04  9:53                             ` Crypto Update for 3.7 Herbert Xu
2012-12-14 10:31                               ` Crypto Update for 3.8 Herbert Xu
2013-02-23  2:33                                 ` Crypto Update for 3.9 Herbert Xu
2013-05-02  1:47                                   ` Crypto Update for 3.10 Herbert Xu
2013-07-05  9:52                                     ` Crypto Update for 3.11 Herbert Xu
2013-09-07  3:55                                   ` Crypto Update for 3.12 Herbert Xu
2013-11-07  8:01                                     ` Crypto Update for 3.13 Herbert Xu
2013-11-12 16:41                                       ` Herbert Xu
2013-11-12 16:59                                         ` Borislav Petkov
2013-11-12 18:27                                           ` Herbert Xu
2013-11-19  2:21                                         ` [GIT] " Herbert Xu
2013-11-23  1:34                                         ` Herbert Xu
2013-11-23  1:40                                           ` Herbert Xu
2014-01-23 11:53                                       ` Crypto Update for 3.14 Herbert Xu
2014-04-01 10:00                                         ` Crypto Update for 3.15 Herbert Xu
2014-06-05  6:23                                           ` Crypto Update for 3.16 Herbert Xu
2014-06-08  2:56                                             ` Linus Torvalds
2014-06-08  4:55                                               ` Herbert Xu
2014-06-09  1:47                                               ` Steven Miao
2014-08-04 13:03                                             ` Crypto Update for 3.17 Herbert Xu
2014-10-07 13:18                                               ` Crypto Update for 3.18 Herbert Xu
2014-12-11 12:51                                                 ` Crypto Update for 3.19 Herbert Xu
2014-12-12 11:54                                                   ` Herbert Xu
2015-02-14  9:43                                                   ` Crypto Update for 3.20 Herbert Xu
2015-04-15  3:39                                                     ` Crypto Update for 4.1 Herbert Xu
2015-04-16  1:58                                                       ` Linus Torvalds
2015-04-16  2:37                                                         ` Linus Torvalds
2015-04-16  2:38                                                           ` Linus Torvalds
2015-04-16  2:42                                                             ` Herbert Xu
2015-04-16  2:49                                                               ` Linus Torvalds
2015-04-16  3:07                                                                 ` Herbert Xu
2015-04-16  3:34                                                                   ` Linus Torvalds
2015-04-23 19:27                                                                     ` Bobby Powers
2015-04-23 20:10                                                                       ` Ard Biesheuvel
2015-04-23 21:35                                                                         ` Bobby Powers
2015-04-24  6:37                                                                           ` [PATCH] crypto: x86/sha512_ssse3 - fixup for asm function prototype change Ard Biesheuvel
2015-04-24 12:20                                                                             ` Herbert Xu
2015-06-22  8:44                                                       ` Crypto Update for 4.2 Herbert Xu
2015-06-23  4:26                                                         ` Linus Torvalds
2015-06-23  4:32                                                           ` Herbert Xu
2015-06-24  2:11                                                         ` Linus Torvalds
2015-06-24 13:29                                                           ` Herbert Xu
2015-08-31 13:56                                                         ` Crypto Update for 4.3 Herbert Xu
2015-11-02  8:04                                                           ` Crypto Update for 4.4 Herbert Xu
2016-01-11 10:14                                                             ` Crypto Update for 4.5 Herbert Xu
2016-01-22 10:18                                                               ` Crypto Fixes " Herbert Xu
2016-02-01  8:31                                                                 ` Herbert Xu
2016-02-09 17:54                                                                 ` Herbert Xu
2016-03-23 13:09                                                                 ` Crypto Fixes for 4.6 Herbert Xu
2016-03-30  9:11                                                                 ` Herbert Xu
2016-04-14  6:25                                                                   ` Herbert Xu
2016-04-25 11:12                                                                     ` Herbert Xu
2016-04-20  9:49                                                                   ` Herbert Xu
2016-05-09  8:46                                                                   ` Herbert Xu
2016-05-13  5:59                                                                 ` Herbert Xu
2016-05-20  8:41                                                                   ` Crypto Fixes for 4.7 Herbert Xu
2016-05-30  6:31                                                                     ` Herbert Xu
2016-06-27  6:28                                                                     ` Herbert Xu
2016-08-16  8:48                                                                       ` Crypto Fixes for 4.8 Herbert Xu
2016-07-22  3:39                                                                     ` Crypto Fixes for 4.7 Herbert Xu
2016-07-23  3:10                                                                       ` Herbert Xu
2016-08-01  9:58                                                                 ` Crypto Fixes for 4.8 Herbert Xu
2016-08-23  9:51                                                                   ` Herbert Xu
2016-08-31 14:19                                                                     ` Herbert Xu
2016-09-05  9:33                                                                   ` Herbert Xu
2016-09-13 10:35                                                                     ` Herbert Xu
2016-09-19 11:21                                                                     ` Herbert Xu
2016-09-23 14:48                                                                     ` Herbert Xu
2016-10-25  2:34                                                                   ` Crypto Fixes for 4.9 Herbert Xu
2016-03-15  7:20                                                               ` Crypto Update for 4.6 Herbert Xu
2016-05-16  7:16                                                                 ` Crypto Update for 4.7 Herbert Xu
2016-07-25 10:53                                                                   ` Crypto Update for 4.8 Herbert Xu
2016-10-10  3:34                                                                     ` Crypto Update for 4.9 Herbert Xu
2015-06-26 10:22                                                     ` Crypto Fixes for 4.2 Herbert Xu
2015-06-26 20:07                                                       ` Linus Torvalds
2015-06-27  6:56                                                         ` Herbert Xu
2015-06-27 16:40                                                           ` Linus Torvalds
2015-06-29  7:32                                                             ` Herbert Xu
2015-06-30 13:51                                                       ` Herbert Xu
2015-07-13  4:08                                                         ` Herbert Xu
2015-08-03  7:16                                                           ` Herbert Xu
2015-08-17  8:27                                                             ` Herbert Xu
2015-09-08  9:25                                                       ` Crypto Fixes for 4.3 Herbert Xu
2015-09-16 10:30                                                         ` Herbert Xu
2015-09-26 20:01                                                           ` Herbert Xu
2015-10-13 12:17                                                             ` Herbert Xu
2015-10-13 17:23                                                               ` Linus Torvalds
2015-10-14  1:03                                                                 ` Herbert Xu
2015-10-14  2:00                                                                   ` Linus Torvalds
2015-10-14  2:38                                                                     ` Herbert Xu
2015-10-26 11:02                                                         ` Herbert Xu
2015-11-11  7:08                                                           ` Crypto Fixes for 4.4 Herbert Xu
2015-11-17  9:41                                                             ` Herbert Xu
2015-12-05  1:04                                                             ` Herbert Xu
2015-12-14  9:29                                                               ` Herbert Xu
2015-12-28 13:26                                                             ` Herbert Xu

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CA+55aFzFecPSQverH7VQBDZY+gS7_RALwh3W4oqWLbWBcBzLqg@mail.gmail.com \
    --to=torvalds@linux-foundation.org \
    --cc=davem@davemloft.net \
    --cc=herbert@gondor.apana.org.au \
    --cc=linux-crypto@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-Crypto Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-crypto/0 linux-crypto/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-crypto linux-crypto/ https://lore.kernel.org/linux-crypto \
		linux-crypto@vger.kernel.org
	public-inbox-index linux-crypto

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-crypto


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git