facebookarchive / BOLT

Binary Optimization and Layout Tool - A linux command-line utility used for optimizing performance of binaries
2.51k stars 177 forks source link

[ASM] Problem when BOLT on libcrypto #54

Open PierreRamoin-1A opened 5 years ago

PierreRamoin-1A commented 5 years ago

Hi,

I tried to apply BOLT on a binary (C++) which use the crypto library of OpenSSL (v1.1.1b). This library generate a lot of WARNING in BOLT before to fail on relocations (No fail but still warnings with -relocs=0).

I tried to apply BOLT directly on libcrypto.so (I use the static lib on my binary but it was for the test), it don't fail but I still have all the warnings.

Here is the output:

 % llvm-bolt libcrypto.so -o libcrypto.so.bolt
BOLT-INFO: Target architecture: x86_64
BOLT-INFO: shared object or position-independent executable detected
BOLT-INFO: first alloc address is 0x0
BOLT-INFO: creating new program header table at address 0x400000, offset 0x400000
BOLT-INFO: disabling -align-macro-fusion in non-relocation mode
BOLT-WARNING: sizes differ for function aesni_set_encrypt_key/1. FDE : 1173; symbol table : 1374. Using max size.
BOLT-WARNING: sizes differ for function poly1305_blocks_avx/1. FDE : 420; symbol table : 2842. Using max size.
BOLT-WARNING: sizes differ for function poly1305_blocks_avx2/1. FDE : 420; symbol table : 2008. Using max size.
BOLT-WARNING: sizes differ for function sha1_block_data_order_shaext/1. FDE : 627; symbol table : 629. Using max size.
BOLT-WARNING: FDE [0x1af540, 0x1af61e) conflicts with function poly1305_blocks_avx/crypto/poly1305/poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1af620, 0x1afe9a) conflicts with function poly1305_blocks_avx/crypto/poly1305/poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1b0100, 0x1b01f7) conflicts with function poly1305_blocks_avx2/crypto/poly1305/poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1b0200, 0x1b0718) conflicts with function poly1305_blocks_avx2/crypto/poly1305/poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1ba007, 0x1ba65f) conflicts with function RC4
BOLT-WARNING: reference in the middle of instruction detected in function _x86_64_AES_encrypt_compact/crypto/aes/aes-x86_64.o/1(*2) at offset 0x270
BOLT-WARNING: function AES_cbc_encrypt has an object detected in a padding region at address 0x78e40
BOLT-WARNING: reference in the middle of instruction detected in function _x86_64_AES_decrypt_compact/crypto/aes/aes-x86_64.o/1(*2) at offset 0x2f0
BOLT-WARNING: function AES_cbc_encrypt has an object detected in a padding region at address 0x78640
BOLT-WARNING: reference in the middle of instruction detected in function AES_set_decrypt_key at offset 0x220
BOLT-WARNING: reference in the middle of instruction detected in function aesni_multi_cbc_decrypt/1 at offset 0xb00
BOLT-WARNING: reference in the middle of instruction detected in function aesni_multi_cbc_decrypt/1 at offset 0x3e0
BOLT-WARNING: reference in the middle of instruction detected in function aesni_multi_cbc_encrypt_avx/crypto/aes/aesni-mb-x86_64.o/1(*2) at offset 0x720
BOLT-WARNING: reference in the middle of instruction detected in function aesni_cbc_sha1_enc_avx/crypto/aes/aesni-sha1-x86_64.o/1(*2) at offset 0x1140
BOLT-WARNING: unable to disassemble instruction at offset 0x30 (address 0x7e770) in function K_XX_XX/crypto/aes/aesni-sha1-x86_64.o/1(*2)
BOLT-WARNING: unable to disassemble instruction at offset 0x1 (address 0x7edc1) in function K256/crypto/aes/aesni-sha256-x86_64.o/1(*2)
BOLT-WARNING: function aesni_set_encrypt_key/1 has an object detected in a padding region at address 0x87500
BOLT-WARNING: reference in the middle of instruction detected in function aesni_set_decrypt_key/1 at offset 0x70
BOLT-WARNING: unable to disassemble instruction at offset 0x4 (address 0x8a104) in function _bsaes_const/crypto/aes/bsaes-x86_64.o/1(*2)
BOLT-WARNING: reference in the middle of instruction detected in function _bsaes_const/crypto/aes/bsaes-x86_64.o/1(*2) at offset 0x130
BOLT-WARNING: reference in the middle of instruction detected in function _bsaes_const/crypto/aes/bsaes-x86_64.o/1(*2) at offset 0xb0
BOLT-WARNING: reference in the middle of instruction detected in function _bsaes_const/crypto/aes/bsaes-x86_64.o/1(*2) at offset 0x140
BOLT-WARNING: reference in the middle of instruction detected in function _bsaes_const/crypto/aes/bsaes-x86_64.o/1(*2) at offset 0x30
BOLT-WARNING: unable to disassemble instruction at offset 0x11 (address 0x8ab11) in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2)
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x1d0
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0xb0
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x20
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x190
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x30
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x1b0
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x40
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0xe0
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x250
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0xf0
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x260
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x290
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x130
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x170
BOLT-WARNING: reference in the middle of instruction detected in function _vpaes_consts/crypto/aes/vpaes-x86_64.o/1(*2) at offset 0x180
BOLT-INFO: forcing -jump-tables=move as PIC jump table was detected in function asn1_time_to_tm/1
BOLT-WARNING: function rsaz_avx2_eligible/1 has an object detected in a padding region at address 0xd26c0
BOLT-WARNING: function rsaz_512_gather4/1 has an object detected in a padding region at address 0xd4240
BOLT-WARNING: function bn_gather5/1 has an object detected in a padding region at address 0xd9340
BOLT-WARNING: reference in the middle of instruction detected in function bn_power5/1 at offset 0x6d9
BOLT-WARNING: reference in the middle of instruction detected in function bn_power5/1 at offset 0x160
BOLT-WARNING: reference in the middle of instruction detected in function bn_powerx5/crypto/bn/x86_64-mont5.o/1(*2) at offset 0xac0
BOLT-WARNING: reference in the middle of instruction detected in function bn_powerx5/crypto/bn/x86_64-mont5.o/1(*2) at offset 0x797
BOLT-WARNING: reference in the middle of instruction detected in function bn_powerx5/crypto/bn/x86_64-mont5.o/1(*2) at offset 0x160
BOLT-WARNING: reference in the middle of instruction detected in function bn_sqrx8x_internal/1 at offset 0x960
BOLT-WARNING: function Camellia_Ekeygen/1 has an object detected in a padding region at address 0xda740
BOLT-WARNING: function Camellia_Ekeygen/1 has an object detected in a padding region at address 0xda700
BOLT-WARNING: function CAST_set_key has an object detected in a padding region at address 0xdd850
BOLT-WARNING: unable to disassemble instruction at offset 0x1a (address 0x12701a) in function ecp_nistz256_precomputed/1
BOLT-WARNING: function EC_GFp_nist_method has an object detected in a padding region at address 0x126fdf
BOLT-WARNING: function aesni_gcm_encrypt/1 has an object detected in a padding region at address 0x18bac0
BOLT-WARNING: function gcm_ghash_avx/1 has an object detected in a padding region at address 0x194480
BOLT-WARNING: function gcm_ghash_avx/1 has an object detected in a padding region at address 0x194450
BOLT-WARNING: function gcm_ghash_avx/1 has an object detected in a padding region at address 0x194440
BOLT-WARNING: function poly1305_emit_base2_44/crypto/poly1305/poly1305-x86_64.o/1(*2) has an object detected in a padding region at address 0x1b20c0
BOLT-WARNING: reference in the middle of instruction detected in function poly1305_blocks_vpmadd52_4x/crypto/poly1305/poly1305-x86_64.o/1(*2) at offset 0x12
BOLT-WARNING: unable to disassemble instruction at offset 0x73 (address 0x1ba793) in function RC4_options
BOLT-WARNING: unable to disassemble instruction at offset 0x8 (address 0x1cac48) in function iotas/crypto/sha/keccak1600-x86_64.o/1(*2)
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block/1 at offset 0x7620
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block/1 at offset 0x5260
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block/1 at offset 0x3100
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block/1 at offset 0x2ac0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block_shaext/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x4b60
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block_shaext/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x27a0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block_shaext/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x640
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block_avx/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x4520
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block_avx/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x2160
BOLT-WARNING: reference in the middle of instruction detected in function sha1_multi_block_avx2/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x23c0
BOLT-WARNING: unable to disassemble instruction at offset 0x33 (address 0x1d2453) in function K_XX_XX/crypto/sha/sha1-mb-x86_64.o/1(*2)
BOLT-WARNING: reference in the middle of instruction detected in function K_XX_XX/crypto/sha/sha1-mb-x86_64.o/1(*2) at offset 0x80
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order/1 at offset 0x4840
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order/1 at offset 0x2ef0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order/1 at offset 0x2160
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order/1 at offset 0x1320
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order/1 at offset 0x10a0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_shaext/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x37a0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_shaext/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x1e50
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_shaext/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x10c0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_shaext/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x280
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_ssse3/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x3520
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_ssse3/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x1bd0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_ssse3/crypto/sha/sha1-x86_64.o/1(*2) at offset 0xe40
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_avx/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x26e0
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_avx/crypto/sha/sha1-x86_64.o/1(*2) at offset 0xd90
BOLT-WARNING: reference in the middle of instruction detected in function sha1_block_data_order_avx2/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x1950
BOLT-WARNING: unable to disassemble instruction at offset 0x53 (address 0x1d6d93) in function K_XX_XX/crypto/sha/sha1-x86_64.o/1(*2)
BOLT-WARNING: reference in the middle of instruction detected in function K_XX_XX/crypto/sha/sha1-x86_64.o/1(*2) at offset 0x40
BOLT-WARNING: reference in the middle of instruction detected in function K_XX_XX/crypto/sha/sha1-x86_64.o/1(*2) at offset 0xa0
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block/1 at offset 0x7e20
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block/1 at offset 0x7600
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block/1 at offset 0x51a0
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block/1 at offset 0x30a0
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block/1 at offset 0x2800
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_shaext/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x5620
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_shaext/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x4e00
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_shaext/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x29a0
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_shaext/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x8a0
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_avx/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x4d80
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_avx/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x4560
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_avx/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x2100
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_avx2/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x2c80
BOLT-WARNING: reference in the middle of instruction detected in function sha256_multi_block_avx2/crypto/sha/sha256-mb-x86_64.o/1(*2) at offset 0x2460
BOLT-WARNING: unable to disassemble instruction at offset 0x15 (address 0x1e5515) in function K512/crypto/sha/sha512-x86_64.o/1(*2)
BOLT-WARNING: function whirlpool_block/1 has an object detected in a padding region at address 0x201fc0
BOLT-WARNING: unable to disassemble instruction at offset 0x32 (address 0x22a122) in function padlock_sha512_blocks/1
BOLT-WARNING: unable to fill CFI for function aesni_set_encrypt_key/1. Skipping.
BOLT-WARNING: unable to fill CFI for function poly1305_blocks_avx/crypto/poly1305/poly1305-x86_64.o/1(*2). Skipping.
BOLT-WARNING: unable to fill CFI for function poly1305_blocks_avx2/crypto/poly1305/poly1305-x86_64.o/1(*2). Skipping.
BOLT-INFO: 0 functions out of 6028 simple functions (0.0%) have non-empty execution profile.
BOLT-INFO: the input contains 366 (dynamic count : 0) missed opportunities for macro-fusion optimization. Use -align-macro-fusion to fix.
BOLT-INFO: removed 206 'repz' prefixes with estimated execution count of 0 times.
BOLT-INFO: UCE removed 3 blocks and 11 bytes of code.
BOLT-INFO: SCTC: patched 85 tail calls (85 forward) tail calls (0 backward) from a total of 85 while removing 1 double jumps and removing 82 basic blocks totalling 410 bytes of code. CTCs total execution count is 0 and the number of times CTCs are taken is 0.
BOLT: 6028 out of 6196 functions were overwritten.
BOLT-INFO: patched build-id (flipped last bit)

After some investigation, it looks like the problem come along with the ASM part of crypto.

Indeed, if I compile the lib with the -no-asm flag, everything is working as expected and these warnings disappears (my binary is BOLTED successfully with relocations).

nolanl commented 5 years ago

I ran into the same problem. The openssl asm puts constants (rodata, essentially) in the .text segment, which confuses BOLT. I worked around it by putting the constants into .rodata. I was working in the context of "ring" which is a Rust crypto library that includes the openssl code. I'll try to get this all upstreamed soon, though given how many projects embed random copies of subsets of openssl, it may take a while...

nolanl commented 5 years ago

Actually, the "reference in the middle of instruction detected" warning is a new regression in BOLT since 71e5fc4a6734869bee50b6f2430c30d8a155e9d. I just tried with an up to date BOLT and am now seeing it as well.

nolanl commented 5 years ago

Since I'm running BOLT on a shared library, this actually fails instead of just printing warnings: BOLT-WARNING: conditional tail call detected in function GFp_bn_power5/1 at 0xf129c. BOLT-WARNING: reference in the middle of instruction detected in function GFp_bn_power5/1 at offset 0x6f9 BOLT-ERROR: unable to keep processing in relocation mode

PierreRamoin-1A commented 5 years ago

Hi @nolanl Thanks for your investigation / work! For the shared library, it's my bad. It was not running relocs as I didn't add --emit-relocations flag at link time. If I add the flag, it fails with this output:

BOLT-INFO: Target architecture: x86_64
BOLT-INFO: shared object or position-independent executable detected
BOLT-INFO: first alloc address is 0x0
BOLT-INFO: creating new program header table at address 0x400000, offset 0x400000
BOLT-INFO: enabling relocation mode
BOLT-INFO: enabling -align-macro-fusion=all since no profile was specified
BOLT-WARNING: sizes differ for function aesni_set_encrypt_key/1. FDE : 1173; symbol table : 1374. Using max size.
BOLT-WARNING: sizes differ for function poly1305_blocks_avx/1. FDE : 420; symbol table : 2842. Using max size.
BOLT-WARNING: sizes differ for function poly1305_blocks_avx2/1. FDE : 420; symbol table : 2008. Using max size.
BOLT-WARNING: sizes differ for function sha1_block_data_order_shaext/1. FDE : 627; symbol table : 629. Using max size.
BOLT-WARNING: FDE [0x1ce9c0, 0x1cea9e) conflicts with function poly1305_blocks_avx/crypto/poly1305/libcrypto-shlib-poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1ceaa0, 0x1cf31a) conflicts with function poly1305_blocks_avx/crypto/poly1305/libcrypto-shlib-poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1cf580, 0x1cf677) conflicts with function poly1305_blocks_avx2/crypto/poly1305/libcrypto-shlib-poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1cf680, 0x1cfb98) conflicts with function poly1305_blocks_avx2/crypto/poly1305/libcrypto-shlib-poly1305-x86_64.o/1(*2)
BOLT-WARNING: FDE [0x1dcdc7, 0x1dd41f) conflicts with function RC4
BOLT-WARNING: split function detected on input : fd_gets.cold.3/1. The support is limited in relocation mode.
BOLT-WARNING: reference in the middle of instruction detected in function _x86_64_AES_encrypt_compact/crypto/aes/libcrypto-shlib-aes-x86_64.o/1(*2) at offset 0x270
BOLT-ERROR: unable to keep processing in relocation mode 
PierreRamoin-1A commented 5 years ago

If you have a working patch, can you share it in the mean time it get upstreamed?

nolanl commented 5 years ago

I have a patch that makes it work with 71e5fc4a6734869bee50b6f2430c30d8a155e9d BOLT. I'll ask about posting it, I am working on a contract at the moment.

nolanl commented 5 years ago

I've attached the patches, sorry for the delay.

Two caveats:

  1. These are patches against "ring", which is a rust library than embeds parts of boringssl, which is a fork of openssl. The asm files (asm embedded in perl, really) they touch are copied from openssl verbatim, so if you fix up the paths, it should all just work with either boringssl or openssl.
  2. With these patches, it works for me with BOLT as of 71e5fc4a6734869bee50b6f2430c30d8a155e9d, but it does not work with the current head BOLT.

openssl_bolt.zip

Romain-Geissler-1A commented 5 years ago

Hi,

@nolanl Do you have any plan to upsteam these fixes in OpenSSL in anyway. The .rodata one seems fine to me, the other one exposing labels as global symbol seems stranger, maybe we should look at what a compiler generates for static functions and try to copy that behavior.

Cheers, Romain

nolanl commented 5 years ago

I plan to upstream them to ring, and will probably also submit them to boringssl and openssl.

The global symbol thing is just a hack, but I didn't worry about it because it is way less hacky than the rest of the function.

Romain-Geissler-1A commented 4 years ago

Hi,

It looks like the asm files in OpenSSL were recently udpated to patch the CFI annotations in it. It might be worth checking if latest releases are working fine now.

Cheers, Romain