Page MenuHomePhabricator

[libcxx][RFC] Unspecified behavior randomization in libcxx
Needs ReviewPublic

Authored by danlark on Feb 18 2021, 2:25 AM.

Details

Reviewers
EricWF
ldionne
jyknight
jdoerfert
Group Reviewers
Restricted Project
Summary

This effort is dedicated to deflake the tests of the users which depend
on the unspecified behavior of algorithms and containers. This also
might help updating the sorting algorithm in libcxx which has the
quadratic worst case in the future or at least create a new one under
flag.

For detailed design, please see the design doc I provide in the patch

Email: kutdanila@yandex.ru, Author: Danila Kutenin. I don't have commit
rights

Diff Detail

Unit TestsFailed

TimeTest
1,120 mslibcxx CI -fno-exceptions > libc++.libcxx/algorithms::sort_stability.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++ /home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/sort_stability.pass.cpp -v --target=x86_64-unknown-linux-gnu -include /home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-noexceptions/projects/libcxx/__config_site -include /home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/test/support/nasty_macros.h -nostdinc++ -I/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/include -I/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-noexceptions/projects/libcxx/include/c++build -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -I/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/test/support -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -std=c++2a -fno-exceptions -Werror -Wall -Wextra -Wshadow -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-user-defined-literals -Wno-noexcept-type -Wno-atomic-alignment -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fmodules-cache-path=/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-noexceptions/projects/libcxx/test/libcxx/algorithms/Output/sort_stability.pass.cpp.dir/t.tmp/ModuleCache -Wno-macro-redefined -D_LIBCPP_HAS_THREAD_API_PTHREAD -Wno-macro-redefined -D_LIBCPP_ABI_VERSION=1 -D_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY -L/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-noexceptions/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-noexceptions/./lib -nodefaultlibs -lc++ -lm -lgcc_s -lgcc -lpthread -lc…
970 mslibcxx CI ASAN > libc++.libcxx/algorithms::sort_stability.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++ /home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/sort_stability.pass.cpp -v --target=x86_64-unknown-linux-gnu -g -fno-omit-frame-pointer -fsanitize=address -include /home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-asan/projects/libcxx/__config_site -include /home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/test/support/nasty_macros.h -nostdinc++ -I/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/include -I/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-asan/projects/libcxx/include/c++build -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -I/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/test/support -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -O1 -std=c++2a -Werror -Wall -Wextra -Wshadow -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-user-defined-literals -Wno-noexcept-type -Wno-atomic-alignment -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fmodules-cache-path=/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-asan/projects/libcxx/test/libcxx/algorithms/Output/sort_stability.pass.cpp.dir/t.tmp/ModuleCache -Wno-macro-redefined -D_LIBCPP_HAS_THREAD_API_PTHREAD -Wno-macro-redefined -D_LIBCPP_ABI_VERSION=1 -D_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY -L/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-asan/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-asan/./lib -nodefaultlibs -lc++ -lm -lgcc_s -lgcc -lpthread -lc -lgcc_s…
790 mslibcxx CI C++11 > libc++.libcxx/algorithms::sort_stability.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++ /home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/sort_stability.pass.cpp -v --target=x86_64-unknown-linux-gnu -include /home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/build/generic-cxx11/projects/libcxx/__config_site -include /home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/libcxx/test/support/nasty_macros.h -nostdinc++ -I/home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/libcxx/include -I/home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/build/generic-cxx11/projects/libcxx/include/c++build -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -I/home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/libcxx/test/support -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -std=c++11 -Werror -Wall -Wextra -Wshadow -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-user-defined-literals -Wno-noexcept-type -Wno-atomic-alignment -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fmodules-cache-path=/home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/build/generic-cxx11/projects/libcxx/test/libcxx/algorithms/Output/sort_stability.pass.cpp.dir/t.tmp/ModuleCache -Wno-macro-redefined -D_LIBCPP_HAS_THREAD_API_PTHREAD -Wno-macro-redefined -D_LIBCPP_ABI_VERSION=1 -D_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY -L/home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/build/generic-cxx11/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/3f2df2acb68b-1/llvm-project/libcxx-ci/build/generic-cxx11/./lib -nodefaultlibs -lc++ -lm -lgcc_s -lgcc -lpthread -lc -lgcc_s -lgcc -latomic -lc++experimental -o /home/libcxx…
780 mslibcxx CI C++14 > libc++.libcxx/algorithms::sort_stability.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++ /home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/sort_stability.pass.cpp -v --target=x86_64-unknown-linux-gnu -include /home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-cxx14/projects/libcxx/__config_site -include /home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/test/support/nasty_macros.h -nostdinc++ -I/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/include -I/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-cxx14/projects/libcxx/include/c++build -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -I/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/libcxx/test/support -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -std=c++14 -Werror -Wall -Wextra -Wshadow -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-user-defined-literals -Wno-noexcept-type -Wno-atomic-alignment -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fmodules-cache-path=/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-cxx14/projects/libcxx/test/libcxx/algorithms/Output/sort_stability.pass.cpp.dir/t.tmp/ModuleCache -Wno-macro-redefined -D_LIBCPP_HAS_THREAD_API_PTHREAD -Wno-macro-redefined -D_LIBCPP_ABI_VERSION=1 -D_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY -L/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-cxx14/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/8211a191e230-1/llvm-project/libcxx-ci/build/generic-cxx14/./lib -nodefaultlibs -lc++ -lm -lgcc_s -lgcc -lpthread -lc -lgcc_s -lgcc -latomic -lc++experimental -o /home/libcxx…
880 mslibcxx CI C++17 > libc++.libcxx/algorithms::sort_stability.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++ /home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/sort_stability.pass.cpp -v --target=x86_64-unknown-linux-gnu -include /home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-cxx17/projects/libcxx/__config_site -include /home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/test/support/nasty_macros.h -nostdinc++ -I/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/include -I/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-cxx17/projects/libcxx/include/c++build -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROS -I/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/libcxx/test/support -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -std=c++17 -Werror -Wall -Wextra -Wshadow -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-user-defined-literals -Wno-noexcept-type -Wno-atomic-alignment -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -fmodules-cache-path=/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-cxx17/projects/libcxx/test/libcxx/algorithms/Output/sort_stability.pass.cpp.dir/t.tmp/ModuleCache -Wno-macro-redefined -D_LIBCPP_HAS_THREAD_API_PTHREAD -Wno-macro-redefined -D_LIBCPP_ABI_VERSION=1 -D_LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY -L/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-cxx17/./lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/1e3624ff42f5-1/llvm-project/libcxx-ci/build/generic-cxx17/./lib -nodefaultlibs -lc++ -lm -lgcc_s -lgcc -lpthread -lc -lgcc_s -lgcc -latomic -lc++experimental -o /home/libcxx…
View Full Test Results (17 Failed)

Event Timeline

danlark created this revision.Feb 18 2021, 2:25 AM
danlark requested review of this revision.Feb 18 2021, 2:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 18 2021, 2:25 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
danlark edited the summary of this revision. (Show Details)Feb 18 2021, 2:28 AM
danlark added reviewers: EricWF, ldionne, jyknight.
danlark updated this revision to Diff 324583.Feb 18 2021, 3:27 AM

Fix unused parameters

ldionne requested changes to this revision.Feb 18 2021, 7:19 AM

First of all, thanks for writing a design document and explaining the purpose of your patch. Let me try to understand the use case a bit better.

So basically, let's say you're trying to adopt a new implementation of std::sort internally. You change that, but then you realize that a bunch of tests break because they were relying on the exact order of equal elements after std::sort, which is really unspecified. But since those tests are failing, you can't use the new std::sort implementation until all the tests have been fixed. So, in order to make that transition easier and allow fixing tests one by one, you add this feature. You then turn it on locally for some projects/tests inside your organization, and you fix them one by one. Once you're done, you can switch the algorithm implementation, and turn off the randomization. Is that the idea?

The main problem I see with this reasoning is that it doesn't really help libc++ as a project to migrate to a new algorithm. Libc++ is used by plenty of people who might be relying on the order of elements after calling std::sort, and they'll never know about this setting before we break their code. Are we comfortable with breaking such users? I mean, we're technically allowed to by the Standard, but still. I *think* I'd be fine with that, but this needs a bit of discussion.

Technically speaking, there's a few things on my mind while reviewing this:

  1. Is there a bad interaction because we instantiate some algorithms in the dylib. I checked and I don't think that's the case.
  2. Is there a way we can achieve the same with some sort of sanitizer or tool external to libc++ instead? If we could do that, I think it would certainly deliver more value in the long term, and it would certainly be more powerful than manually-added checks in libc++.
  3. How can we minimize the complexity we're adding to libc++? This is the Standard Library, and literally everybody wants to add their "very small tweak" to it. If we're not very aggressive about reducing complexity, it becomes a mess. For example, do you really need to be able to specify the seed? Can you explain why? And in case it almost always makes sense to specify a seed, can we make it mandatory instead? I'm trying to reduce the number of configurations we have to maintain.
  4. If we do this, then does it make sense to group it with other features such as the Debug mode? It seems to me that this effort, iterator invalidation checking and other similar checks kind of fall into the same bucket of "things that turn silent misuses into loud failures so you diagnose them before they hit prod". If we decide to go ahead with your patch, I think it would be useful to have a wider vision for how we handle these sorts of additions in the future.

Requesting changes so it shows up properly in the queue. Let's have a discussion.

Thanks!

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst
19

all elements in the vector

20–22

Do you mean that it prevents libc++ from changing the implementation of algorithms like std::sort? I think it's useful to try and use the term "implementation" here, because just saying "algorithm" isn't clear (std::sort is commonly referred to as an "algorithm", but you really mean the underlying implementation of it).

31

LLVM

44

turn it on, or alternatively enable it

50

within a run

libcxx/include/algorithm
3113

Why are we making this a template?

3127–3132

I'm far from being a PRNG expert - can you explain what you're doing here?

This revision now requires changes to proceed.Feb 18 2021, 7:19 AM
danlark updated this revision to Diff 324677.Feb 18 2021, 9:23 AM
danlark marked 7 inline comments as done.

Address comments

First of all, thanks for writing a design document and explaining the purpose of your patch. Let me try to understand the use case a bit better.

So basically, let's say you're trying to adopt a new implementation of std::sort internally. You change that, but then you realize that a bunch of tests break because they were relying on the exact order of equal elements after std::sort, which is really unspecified. But since those tests are failing, you can't use the new std::sort implementation until all the tests have been fixed. So, in order to make that transition easier and allow fixing tests one by one, you add this feature. You then turn it on locally for some projects/tests inside your organization, and you fix them one by one. Once you're done, you can switch the algorithm implementation, and turn off the randomization. Is that the idea?

Yes, that's a correct understanding except switching off the randomization would not happen. It should be a by default feature for us to preserve new cases of stability dependencies in some debug builds, in release builds, we are not going to do any randomization but we can guarantee that new sorting algorithm works as best as we can test.

The main problem I see with this reasoning is that it doesn't really help libc++ as a project to migrate to a new algorithm. Libc++ is used by plenty of people who might be relying on the order of elements after calling std::sort, and they'll never know about this setting before we break their code. Are we comfortable with breaking such users? I mean, we're technically allowed to by the Standard, but still. I *think* I'd be fine with that, but this needs a bit of discussion.

Technically speaking, there's a few things on my mind while reviewing this:

  1. Is there a bad interaction because we instantiate some algorithms in the dylib. I checked and I don't think that's the case.
  2. Is there a way we can achieve the same with some sort of sanitizer or tool external to libc++ instead? If we could do that, I think it would certainly deliver more value in the long term, and it would certainly be more powerful than manually-added checks in libc++.
  3. How can we minimize the complexity we're adding to libc++? This is the Standard Library, and literally everybody wants to add their "very small tweak" to it. If we're not very aggressive about reducing complexity, it becomes a mess. For example, do you really need to be able to specify the seed? Can you explain why? And in case it almost always makes sense to specify a seed, can we make it mandatory instead? I'm trying to reduce the number of configurations we have to maintain.
  4. If we do this, then does it make sense to group it with other features such as the Debug mode? It seems to me that this effort, iterator invalidation checking and other similar checks kind of fall into the same bucket of "things that turn silent misuses into loud failures so you diagnose them before they hit prod". If we decide to go ahead with your patch, I think it would be useful to have a wider vision for how we handle these sorts of additions in the future.

Requesting changes so it shows up properly in the queue. Let's have a discussion.

Thanks!

I think we should at some point break users in algorithms, for example, in sorting because we are not compliant now and new algorithms just evolve. Providing an option to migrate is possibly the best we can do

  1. No, no bad interaction
  2. That's possible for the compiler to introduce some hooks before calling std::sort, however, I thought, it would be easier just to introduce an option if they ever wonder why their tests are failing after the migration to a new version of libc++. Ideally this should be another type of sanitizer which I scared to suggest, to be honest, and patching libcxx seemed much easier and relevant
  3. The idea for seed was to have reproducible results no matter. I am fine with removing it if you feel this is an unnecessary complication. Having random seed per run was the initial idea so that the tests become flaky and the users notice
  4. I am fine with moving it under debug, I did not do it right away because DEBUG mode is deterministic currently and I thought another option is still good. If you are ok with moving it under debug, me too
libcxx/include/algorithm
3113

Because there is no algorithm.cpp and I decided not to create one because of such feature. It is needed to instantiate static const void* const __seed_static; and inline variables are only a C++17 feature, before that it was a common trick to put the static variable definition in header

See

template <class _Void>
const void* const __random_unspecified_behavior_gen_<_Void>::__seed_static =
    &__seed_static;
3127–3132

It's some very simple PCG random generator, I switched to a more simple linear congruential in order to remove complexity

Ping @ldionne

Sorry for not pinging for so long

So, overall I am ok with putting this under _LIBCPP_DEBUG 2 but separate option would be better because the users do not want unstable results until they really do.

What do you think? Given the discussions in the C++ standard committee, I think this is a reasonable approach to give the users opportunities to upgrade to something better and show how it could be done. Having std::sort from 2005 and not updating/offering something better and standard compliant feels just wrong.

danlark edited the summary of this revision. (Show Details)Sat, May 15, 2:05 AM