ubsan: sub-overflow in gcd after #77747

[hiraditya]

With #77747 one of the tests failed with ubsanitized binary.

Original stack trace

Revision: 'MP1.0' 
 ABI: 'arm64' 
 Timestamp: 2024-11-21 18:06:46.362693790+0000 
 Process uptime: 4s 
 Cmdline: system_server 
 pid: 10110, tid: 10299, name: StorageManagerS  >>> system_server <<< 
 uid: 1000 
 tagged_addr_ctrl: 0000000000000001 (PR_TAGGED_ADDR_ENABLE) 
 pac_enabled_keys: 000000000000000f (PR_PAC_APIAKEY, PR_PAC_APIBKEY, PR_PAC_APDAKEY, PR_PAC_APDBKEY) 
 signal 6 (SIGABRT), code -1 (SI_QUEUE), fault addr -------- 
 Abort message: 'ubsan: sub-overflow by 0x00000077deea71e8' 
     x0  0000000000000000  x1  000000000000283b  x2  0000000000000006  x3  0000007384bc6e30 
     x4  362f2f2f2f2f2f77  x5  362f2f2f2f2f2f77  x6  362f2f2f2f2f2f77  x7  7f7f7f7f7f7f7f7f 
     x8  00000000000000f0  x9  4c34f981a6e2fcab  x10 0000000000000001  x11 00000077cbb60390 
     x12 0000000000000001  x13 0000000000000012  x14 0000000000000010  x15 000000000000001e 
     x16 00000077cbbca068  x17 00000077cbbb3ec0  x18 0000007379284000  x19 000000000000277e 
     x20 000000000000283b  x21 00000000ffffffff  x22 0000000000002e68  x23 0000000000000016 
     x24 0000000000002e68  x25 b400007596f395f0  x26 0000000000000000  x27 00000000001f4000 
     x28 0000000000000016  x29 0000007384bc6eb0 
     lr  00000077cbb49358  sp  0000007384bc6e30  pc  00000077cbb4937c  pst 0000000000001000 
 37 total frames 
 backtrace: 
       #00 pc 000000000005e37c  /apex/com.android.runtime/lib64/bionic/libc.so (abort+156) (BuildId: a0aadb8b9a435cba80682f8ec11369be) 
       #01 pc 000000000000c208  /system/lib64/libmedia_codeclist_capabilities.so (__ubsan_handle_sub_overflow_minimal_abort+112) (BuildId: 95fc54602b3701495fdf8d22ac7c0587) 
       #02 pc 00000000000271e4  /system/lib64/libmedia_codeclist_capabilities.so (android::VideoCapabilities::applyLevelLimits()+7668) (BuildId: 95fc54602b3701495fdf8d22ac7c0587) 
       #03 pc 00000000000253c0  /system/lib64/libmedia_codeclist_capabilities.so (android::VideoCapabilities::init(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>, std::__1::vector<android::ProfileLevel, std::__1::allocator<android::ProfileLevel>>, android::sp<android::AMessage> const&)+272) (BuildId: 95fc54602b3701495fdf8d22ac7c0587) 
       #04 pc 000000000002523c  /system/lib64/libmedia_codeclist_capabilities.so (android::VideoCapabilities::Create(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>, std::__1::vector<android::ProfileLevel, std::__1::allocator<android::ProfileLevel>>, android::sp<android::AMessage> const&) (.cfi)+268) (BuildId: 95fc54602b3701495fdf8d22ac7c0587) 
       #05 pc 0000000000020d5c  /system/lib64/libmedia_codeclist_capabilities.so (android::CodecCapabilities::init(std::__1::vector<android::ProfileLevel, std::__1::allocator<android::ProfileLevel>>, std::__1::vector<unsigned int, std::__1::allocator<unsigned int>>, bool, android::sp<android::AMessage>&, android::sp<android::AMessage>&, int)+908) (BuildId: 95fc54602b3701495fdf8d22ac7c0587) 
       #06 pc 000000000000ee9c  /system/lib64/libmedia_codeclist.so (android::MediaCodecInfoWriter::BuildCodecCapabilities(char const*, android::sp<android::MediaCodecInfo::Capabilities>, bool, int) (.cfi)+1212) (BuildId: a0f243d4bccfcd7d288db72bc3e3500d) 

Symbolicated trace

Revision: 'MP1.0'
ABI: 'arm64'
pid: 10110, tid: 10299, name: StorageManagerS  >>> system_server <<<
signal 6 (SIGABRT), code -1 (SI_QUEUE), fault addr --------
Abort message: 'ubsan: sub-overflow by 0x00000077deea71e8'

Stack Trace:
  RELADDR           FUNCTION                                                                                                                                                                                                                                                                                                               FILE:LINE
  000000000005e37c  abort (BuildId: a0aadb8b9a435cba80682f8ec11369be)                                                                                                                                                                                                                                                                      bionic/libc/bionic/abort.cpp:52:3
         (inlined)  abort_with_message (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                                                                                                                                                                                                                                                         out/lib/compiler-rt-aarch64/out/llvm-project/compiler-rt/lib/ubsan_minimal/ubsan_minimal_handlers.cpp:71:3
  000000000000c208  __ubsan_handle_sub_overflow_minimal_abort (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                                                                                                                                                                                                                                  out/lib/compiler-rt-aarch64/out/llvm-project/compiler-rt/lib/ubsan_minimal/ubsan_minimal_handlers.cpp:123:1
         (inlined)  unsigned int std::__1::__gcd<unsigned int>(unsigned int, unsigned int) (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                                                                                                                                                                                                     prebuilts/clang/host/linux-x86/clang-r536225/include/c++/v1/__numeric/gcd_lcm.h:85:22
         (inlined)  std::__1::common_type<int, int>::type std::__1::gcd[abi:nn190000]<int, int>(int, int) (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                                                                                                                                                                                      prebuilts/clang/host/linux-x86/clang-r536225/include/c++/v1/__numeric/gcd_lcm.h:106:7
         (inlined)  android::Rational::Rational(int, int) (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                                                                                                                                                                                                                                      frameworks/av/media/libmedia/include/media/CodecCapabilitiesUtils.h:404:23
  00000000000271e4  android::VideoCapabilities::applyLevelLimits() (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                                                                                                                                                                                                                             frameworks/av/media/libmedia/VideoCapabilities.cpp:1392:0
  00000000000253c0  android::VideoCapabilities::init(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>, std::__1::vector<android::ProfileLevel, std::__1::allocator<android::ProfileLevel>>, android::sp<android::AMessage> const&) (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                         frameworks/av/media/libmedia/VideoCapabilities.cpp:444:5
  000000000002523c  android::VideoCapabilities::Create(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>, std::__1::vector<android::ProfileLevel, std::__1::allocator<android::ProfileLevel>>, android::sp<android::AMessage> const&) (.cfi) (BuildId: 95fc54602b3701495fdf8d22ac7c0587)                frameworks/av/media/libmedia/VideoCapabilities.cpp:433:11
  0000000000020d5c  android::CodecCapabilities::init(std::__1::vector<android::ProfileLevel, std::__1::allocator<android::ProfileLevel>>, std::__1::vector<unsigned int, std::__1::allocator<unsigned int>>, bool, android::sp<android::AMessage>&, android::sp<android::AMessage>&, int) (BuildId: 95fc54602b3701495fdf8d22ac7c0587)      frameworks/av/media/libmedia/CodecCapabilities.cpp:398:22

[ldionne]

@serge-sans-paille Do you think you could have a look?

[hiraditya]

I believe the bug is in the subtraction

do {
    _Tp __diff = __a - __b;                             // When __a < __b 
    if (__a > __b) {
      __a = __b;
      __b = __diff;
    } else {
      __b = __b - __a;
    }
    if (__diff != 0)
      __b >>= std::__countr_zero(__diff); // We are passing that value here. Is this okay?
  } while (__b != 0);

[serge-sans-paille]

there are two subtraction in this algorithm, and the other one is guarded by a condition that ensures it never underflows. /me checking that aspect.

[serge-sans-paille]

https://lemire.me/blog/2024/04/13/greatest-common-divisor-the-extended-euclidean-algorithm-and-speed/ has a version of the algorithm without sub-overflow, checking if it's satisfying.

[ldionne]

@hiraditya How did you encounter this issue? We do have a build with ubsan enabled but it never triggered this issue. Is it for a specific input? I'd like to add a test case to #117984

[hiraditya]

@hiraditya How did you encounter this issue? We do have a build with ubsan enabled but it never triggered this issue. Is it for a specific input? I'd like to add a test case to #117984

it is probably a lot of work to get the exact inputs but I'll share with the folks who mentioned this to me.

[ldionne]

@hiraditya How did you encounter this issue? We do have a build with ubsan enabled but it never triggered this issue. Is it for a specific input? I'd like to add a test case to #117984

it is probably a lot of work to get the exact inputs but I'll share with the folks who mentioned this to me.

This is a really simple function though, I assume there's two integer inputs that lead to this crash. So as long as we know the two numbers in question, we should be able to reproduce?