crypto/aes: add assembly for non-AES-NI machines

[alexbrainman]

golang https server described in https://golang.org/issue/4073?c=8
and tested with

siege --benchmark --concurrent=100 "https://localhost:8082";

command gives

Lifting the server siege...      done.
Transactions:                    779 hits
Availability:                 100.00 %
Elapsed time:                  40.56 secs
Data transferred:               0.02 MB
Response time:                  4.85 secs
Transaction rate:              19.21 trans/sec
Throughput:                     0.00 MB/sec
Concurrency:                   93.11
Successful transactions:         779
Failed transactions:               0
Longest transaction:           10.22
Shortest transaction:           0.34

But nginx does better:

Transactions:                   5120 hits
Availability:                 100.00 %
Elapsed time:                  53.87 secs
Data transferred:               0.74 MB
Response time:                  1.04 secs
Transaction rate:              95.04 trans/sec
Throughput:                     0.01 MB/sec
Concurrency:                   98.92
Successful transactions:        5120
Failed transactions:               0
Longest transaction:            1.08
Shortest transaction:           0.15

hg id is 8e87cb8dca7d. windows/386.

linux/386 golang server does about the same:

Lifting the server siege...      done.
Transactions:                   1867 hits
Availability:                 100.00 %
Elapsed time:                 118.75 secs
Data transferred:               0.05 MB
Response time:                  6.23 secs
Transaction rate:              15.72 trans/sec
Throughput:                     0.00 MB/sec
Concurrency:                   97.89
Successful transactions:        1867
Failed transactions:               0
Longest transaction:           13.59
Shortest transaction:           0.32

https://golang.org/issue/4073?c=6 claims similar results comparing to
"hello world node.js app".

I would investigate more, but I know nothing about SSL.

Alex

[alexbrainman]

Comment 1:

Issue #4073 has been merged into this issue.

[agl]

Comment 2:

nginx is probably doing a less computationally intensive ciphersuite and it's using
OpenSSL rather than math/big.
If anyone is keen on improving things, a constant time modexp in math/big would go a
long way, but it's very complex. We could also likely reduce the cost of RSA blinding by
squaring the same manner as OpenSSL rather than generating a new blind each time.
Lastly, a high-speed, constant time P-256 would also help.

Labels changed: added priority-later, removed priority-triage.

Status changed to LongTerm.

[rsc]

Comment 3:

Labels changed: added go1.1maybe, removed go1.1.

[robpike]

Comment 4:

Labels changed: removed go1.1maybe.

[gopherbot]

Comment 5 by jlmoiron:

I was running into this from another direction, downloading over https, and wrote a
program that demonstrates the issue, not through lower footprint but increased CPU
utilization.  The program is on the playground here:
http://play.golang.org/p/chCbgqS_ls
It is almost certainly possible to create a more straightforward example that passes
data straight through the crypto functions without relying on the network, but I was
trying to see if the issue was related to fetching multiple ssl streams at once or not
and wanted to isolate this anyway.
A sample pprof topN output on a linux-64bit machine:
Total: 953 samples
     472  49.5%  49.5%      472  49.5% crypto/aes.decryptBlockGo
     302  31.7%  81.2%      785  82.4% crypto/cipher.(*cbcDecrypter).CryptBlocks
      85   8.9%  90.1%       85   8.9% crypto/sha1.block
      36   3.8%  93.9%       36   3.8% runtime.memmove
       9   0.9%  94.9%      479  50.3% crypto/aes.decryptBlock
       5   0.5%  95.4%      483  50.7% crypto/aes.(*aesCipher).Decrypt
       4   0.4%  95.8%        4   0.4% runtime.futex
       3   0.3%  96.1%        3   0.3% ifaceeq1
       3   0.3%  96.4%        9   0.9% syscall.read
       2   0.2%  96.6%        2   0.2% crypto/hmac.(*hmac).tmpPad
       2   0.2%  96.9%        5   0.5% crypto/sha1.(*digest).Sum
       2   0.2%  97.1%        2   0.2% netpollblock
This doesn't appear to be limited to aes, as downloading from a different source
(unfortunately an internal server) gave me this pprof output:
Total: 1210 samples
     813  67.2%  67.2%      813  67.2% crypto/des.permuteBlock
     280  23.1%  90.3%     1016  84.0% crypto/des.feistel
      31   2.6%  92.9%       67   5.5% compress/flate.(*compressor).deflate
      21   1.7%  94.6%     1118  92.4% crypto/des.cryptBlock
       8   0.7%  95.3%     1125  93.0% crypto/cipher.(*cbcDecrypter).CryptBlocks
       6   0.5%  95.8%        6   0.5% compress/flate.(*compressor).findMatch
       6   0.5%  96.3%        6   0.5% encoding/binary.bigEndian.PutUint64
       5   0.4%  96.7%       19   1.6% compress/flate.(*huffmanEncoder).bitCounts
       5   0.4%  97.1%       10   0.8% runtime.mallocgc
       5   0.4%  97.5%        5   0.4% runtime.settype_flush
This was with `go version devel +98b396da54db Sun Apr 28 00:18:11 2013 +1000 linux/amd64`

[agl]

Comment 6:

jlmoiron: it's certainly true that the ciphers take CPU time. DES (in the second trace)
is well known to be a terrible CPU hog. AES (the first trace) isn't quite so bad.
Unfortunately your machine doesn't appear to have AES-NI support in the CPU so the AES
code is pure Go and somewhat slow. I'd be happy to have optimised versions for various
other CPUs but I'm afraid that we don't, yet.

[gopherbot]

Comment 8:

Is this fixed by https://code.google.com/p/go/source/detail?r=57503accfdc7 now?

[alexbrainman]

Comment 9:

Yes, go is much faster then before:
go (go version devel +d2cb80eac1ac Sat Oct 05 14:15:02 2013 +1000 linux/386):
Lifting the server siege...      done.
Transactions:                    837 hits
Availability:                 100.00 %
Elapsed time:                  16.95 secs
Data transferred:               0.02 MB
Response time:                  1.90 secs
Transaction rate:              49.38 trans/sec
Throughput:                     0.00 MB/sec
Concurrency:                   94.06
Successful transactions:         837
Failed transactions:               0
Longest transaction:            4.01
Shortest transaction:           0.50
but still not as fast as nginx
nginx:
Lifting the server siege...      done.
Transactions:                   1336 hits
Availability:                 100.00 %
Elapsed time:                  14.16 secs
Data transferred:               0.19 MB
Response time:                  1.02 secs
Transaction rate:              94.35 trans/sec
Throughput:                     0.01 MB/sec
Concurrency:                   96.06
Successful transactions:        1336
Failed transactions:               0
Longest transaction:            1.07
Shortest transaction:           0.12
Feel free to close this, if you think nothing else we can do here.
Alex

[minux]

Comment 10:

Re #8, no, that commit implements AESNI based AES for amd64 only.
we still need to implement AES in assembly for non-AESNI machines and
esp. for 386.

[minux]

Comment 11:

Re #9, is AES operation the bottleneck here?
if not, perhaps we can close this issue.
(i might one day get time to write AES in assembly for ARM, but I don't bother
to do that for 386; and I believe AES-NI machines will be more widespread
before Go 1.3 is released)

[alexbrainman]

Comment 12:

I don't know. Does this
U:\>go tool pprof main.exe c:\tmp\a.pprof
Welcome to pprof!  For help, type 'help'.
(pprof) top10
Total: 6211 samples
    5461  87.9%  87.9%     5461  87.9% etext
     135   2.2%  90.1%      135   2.2% math/big.addMulVVW
     133   2.1%  92.2%      133   2.1% math/big.subVV
      98   1.6%  93.8%       98   1.6% math/big.mulAddVWW
      45   0.7%  94.5%      327   5.3% math/big.nat.divLarge
      43   0.7%  95.2%       43   0.7% addroots
      31   0.5%  95.7%       31   0.5% crypto/elliptic.p256ReduceDegree
      23   0.4%  96.1%       23   0.4% runtime.settype_flush
      21   0.3%  96.4%       21   0.3% markonly
      20   0.3%  96.8%       34   0.5% crypto/elliptic.p256Mul
(pprof)
tell you anything?
Alex

[minux]

Comment 13:

so the bottleneck is ECC/RSA part?

[alexbrainman]

Comment 14:

How can I tell?
Alex

[minux]

Comment 15:

should be the ECC part. RSA shouldn't use math/big.nat.
let's leave this issue to agl to decide.

[agl]

Comment 16:

Why wouldn't RSA use math/big.nat? In this case it's using P256 ECC, which is
implemented specially and *that* won't use math/big.