#duplicates #binary #function #determine #x86-64 #how #find

app duplicate-function-checker

Tool to determine how much of your binary is duplicate functions

1 unstable release

0.1.0 Jun 7, 2024

#304 in Debugging

MIT/Apache

20KB
268 lines

Duplicate symbol checker

This tool is intended for determining how much of a compiled Rust binary is composed of identical functions.

It relies on debug symbols to find functions, so your binary needs to not have been stripped.

It works by reading the instructions for each function, normalising them in order to accommodate differences that are only due to the base address of the function, then grouping by the resulting instruction bytes.

It currently only supports x86_64 binaries and has only been tested on Linux.

Identified duplicate functions have a few different sources:

  • Functions could be identical by chance even though they come from different parts of the codebase.
  • Generic functions, once monomorphised, could be identical despite having different generic arguments. For example, the function might only depend on the size of the generic argument, meaning that all monomorphisations with types of the same size would end up equal.
  • Generic functions might be monomorphised multiple times with the same arguments, but then not get deduplicated.

The last of these is what I'm most interested in. Unfortunately it's currently kind of hard to separate these last two cases. Rustc seems to sometimes emit symbol names that include the generic arguments, but often it emits symbol names that just have the placeholders, then uses a different hash at the end of the symbol.

Recommended usage:

cargo run --release -- --verbose --demangle /path/to/bin

Sample output

I'll now show some sample outputs from running the tool on a release build of ripgrep. I don't include all the output since it's quite long, just a few bits that warrant further discussion.

Function size: 103
Copies: 21
Excess bytes: 2060
Names:
  1x `alloc::sync::Arc<T,A>::drop_slow::hd706a4fa915b4d89`
  1x `alloc::sync::Arc<T,A>::drop_slow::h87093f1f9dea2d0e`
  1x `alloc::sync::Arc<T,A>::drop_slow::h10d0dcce72958fd8`
  1x `alloc::sync::Arc<T,A>::drop_slow::h8c617ac2d907e2aa`
  1x `alloc::sync::Arc<T,A>::drop_slow::hd71eeda01817a536`
  1x `alloc::sync::Arc<T,A>::drop_slow::he520a5dd6ca64703`
  1x `alloc::sync::Arc<T,A>::drop_slow::h628a33a33ecac575`
  1x `alloc::sync::Arc<T,A>::drop_slow::h8cec9ca0439c3711`
  1x `alloc::sync::Arc<T,A>::drop_slow::h4cd5ea407012db46`
  1x `alloc::sync::Arc<T,A>::drop_slow::h224d6f2371018a1c`
  1x `alloc::sync::Arc<T,A>::drop_slow::h990f0b7fc7e3af11`
  1x `alloc::sync::Arc<T,A>::drop_slow::h73ba588d5943ac7a`
  1x `alloc::sync::Arc<T,A>::drop_slow::h2dc0bbd1c9c62e26`
  1x `alloc::sync::Arc<T,A>::drop_slow::h517054e3fb2dbac5`
  1x `alloc::sync::Arc<T,A>::drop_slow::hdf2cd5f474fa2393`
  1x `alloc::sync::Arc<T,A>::drop_slow::h61f7d6c3b84da1e9`
  1x `alloc::sync::Arc<T,A>::drop_slow::h2487201382634f65`
  1x `alloc::sync::Arc<T,A>::drop_slow::hfd3d412a64e719d1`
  1x `alloc::sync::Arc<T,A>::drop_slow::h127b8fb68b2d8622`
  1x `alloc::sync::Arc<T,A>::drop_slow::h545a994a083aa1dc`
  1x `alloc::sync::Arc<T,A>::drop_slow::he1370168d3fba403`

Here we can see that there's 21 copies of a function for dropping an Arc. We don't know what's in the Arc. It's likely that each of these functions was created to drop an Arc<T> with a different T, but that the machine code ended up identical.

Function size: 236
Copies: 26
Excess bytes: 5900
Names:
  3x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h0ede7a90cb4e4caf`
  3x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h3dc26697a761e8f9`
  3x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h3801b4f9aaad7fc2`
  5x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h9eb8ddad156565f6`
  5x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::hc517e495ab2a88a4`
  4x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::hde4f9e64fcdf6bea`
  3x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::hd22a22559e751911`

Here we have 7 different function names, differing only in their hash. The compiler has substituted the type parameter, so we know that these are all dropping the same type. Each function name then has several copies. These extra copies of each symbol come from separate codegen units. We can determine this by rebuilding the binary with codegen-units=1, then we get the following:

Function size: 236
Copies: 7
Excess bytes: 1416
Names:
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h92c782dcb35669b7`
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h67d0912fdfd31563`
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h11e9189330999400`
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h3242a4cd1700d56b`
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h17293025138ff46d`
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h085ce04cd90a2c3f`
  1x `core::ptr::drop_in_place<regex_automata::meta::wrappers::PikeVMCache>::h419132e2cb015325`

Each of these 7 copies was monomorphised when compiling a different crate. We can verify this by running the tool without --demangle then using grep to locate the .rlib that contains that symbol. Each of these symbols shows up in a different rlib.

Typical results

For a release build of ripgrep with rustc 1.78.0, I observe the following:

Configuration % duplicate functions
Default release 5.8
Release with LTO disabled 6.4
Release with fat LTO 2.1
Release with codegen-units=1 1.9
Release with codegen-units=1 + fat LTO 1.8
Release with codegen-units=1 + fat LTO + -Zshare-generics 0.9
Default debug (-Zshare-generics on by default) 6.6
Default debug with -Zshare-generics=off 7.1

If trying to reproduce these numbers, I tested with commit 601e122e9f.

For a binary with lots more dependencies, I pick on my own crate, the Rust REPL evcxr. In its release build, 10% of executable bytes are from excess copies of duplicated functions. This drops to 1% with codegen-units=1.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in Wild by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Dependencies

~18–27MB
~468K SLoC