This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][RFC] Unspecified behavior randomization in libcxx
ClosedPublic

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

Details

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

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 ↗(On Diff #324583)

Why are we making this a template?

3127–3132 ↗(On Diff #324583)

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.Feb 18 2021, 9:23 AM

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 ↗(On Diff #324583)

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 ↗(On Diff #324583)

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)May 15 2021, 2:05 AM

Hi, is this still going and are you interested? I see https://reviews.llvm.org/D93233 and this infrastructure will help all users to migrate and avoid Hyrum's Law dependencies if they see problems

I can remove SEED if needed.

@ldionne call of last hope, if I should continue the effort :)

Even with D113413 many users are likely to complain that new libcxx broke their tests. Yes, they should not depend on the ordering, however, there is no infrastructure to guarantee that behavior at scale. Providing an option to handle in separate builds and gradual rollout may help them to write better code overall.

It's not an ABI contract but I am pretty sure this will rise quite heavily when we decide to switch the implementation.

FWIW, I think this wouldn't be too bad. I'm also not convinced it has much benefit. But here are some minor tweaks that I think would minorly increase its minor benefit and minorly decrease its minor cost:

#if _LIBCPP_DEBUG_RANDOMIZE
 #ifdef _LIBCPP_CXX03_LANG
  #error "Randomization of unspecified behavior is available only in C++11 and later"
 #endif
 #define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last) do { if (!__libcpp_is_constant_evaluated()) _VSTD::shuffle(__first, __last, __libcpp_debug_randomizer()); } while (0)
#else
 #define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last) (void)0
#endif

This makes the changes to sort, nth_element, and partial_sort into one-line diffs.
Also, unless I'm missing something, you should apply the one-line diff also to std::partition.
I'd make the name of the macro involve DEBUG, but I wouldn't literally enable this as part of _LIBCPP_DEBUG=1 or 2 or whatever.

Anyway, as usual, I'm offering tweaks that I think should improve this PR's chances, but making these tweaks is no guarantee of future results. ldionne is still the one to decide whether this whole direction is worthwhile at all.

ldionne requested changes to this revision.Nov 15 2021, 1:25 PM

@ldionne call of last hope, if I should continue the effort :)

Sorry for dropping the ball here.

Yes, let's make this happen. I think this is useful. IMO, it would make most sense for it to be enabled unconditionally if the debug mode is enabled too instead of having a separate toggle just for it. I'm soon going to be cleaning up the debug mode (and in particular making sure it works at all), so this would become supported better. WDYT?

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst
31
32
39

Can we rename this to _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY instead, since it is tied to the debug mode (if we apply my suggestions here)?

libcxx/docs/UsingLibcxx.rst
244–250 ↗(On Diff #324677)

This should be moved to the documentation of the debug mode. In particular, I would like it if it were NOT advertised as something that can be tweaked by users. Users should only select the debug mode level.

libcxx/include/__config
861–876

What would you think of enabling this automatically when the debug mode is enabled?

#if _LIBCPP_DEBUG_LEVEL >= 2
# define _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY
#endif
864
libcxx/include/algorithm
3125 ↗(On Diff #324677)
3131–3132 ↗(On Diff #324677)
3136–3137 ↗(On Diff #324677)

We don't generally qualify types when in namespace std. Applies elsewhere.

3138 ↗(On Diff #324677)
3139 ↗(On Diff #324677)
3150–3151 ↗(On Diff #324677)
3153–3154 ↗(On Diff #324677)
This revision now requires changes to proceed.Nov 15 2021, 1:25 PM
libcxx/include/algorithm
3113 ↗(On Diff #324583)

Seems like it would be way simpler to just do the other C++ singleton trick, which is "make the thing a function-local static variable":

    _LIBCPP_ALWAYS_INLINE static result_type __seed() {
#ifdef _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED
      return _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED;
#else
      static char __x;
      return reinterpret_cast<uintptr_t>(&__x);
#endif
    }

I see no reason for any of the helper machinery here; it looks like we're just trying to generate a "random seed" from an address, so let's just do that. No global variables, no templates (not even any unnecessary casts!), nice and simple.

ldionne added inline comments.Nov 15 2021, 1:43 PM
libcxx/include/algorithm
3113 ↗(On Diff #324583)

Yeah, agreed, IMO that seems cleaner.

@danlark
Oh yeah, sorry for the spam, but can you add a release note mentioning that we added this feature in LLVM 14?

danlark updated this revision to Diff 387442.Nov 15 2021, 4:54 PM
danlark marked 7 inline comments as done.

All comments are done

I can also write a test for std::partition but maybe later

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst
39

done

libcxx/docs/UsingLibcxx.rst
244–250 ↗(On Diff #324677)

Thanks, done

libcxx/include/__config
861–876

I like it

libcxx/include/algorithm
3150–3151 ↗(On Diff #324677)

removed in favor of simpler version

3153–3154 ↗(On Diff #324677)

irrelevant, removed

danlark updated this revision to Diff 387445.Nov 15 2021, 4:56 PM
danlark updated this revision to Diff 387448.Nov 15 2021, 5:06 PM

Improve one comment

danlark updated this revision to Diff 387468.Nov 15 2021, 6:22 PM
danlark updated this revision to Diff 387585.Nov 16 2021, 5:23 AM
ldionne accepted this revision.Nov 16 2021, 6:55 AM

LGTM but we'll need to get CI to pass.

libcxx/docs/ReleaseNotes.rst
54

Let's break this line similarly to surrounding paragraphs.

libcxx/include/__algorithm/nth_element.h
16–18

Can you move this after the initial set of includes (on line 21 roughly) so that we can still keep the rest of the headers sorted easily? Applies everywhere.

libcxx/include/__config
867–874

Personally I preferred the previous version where you had these checks inlined in the algorithms. I should have said it, sorry for the churn. Anyway, feel free to do it however you prefer.

873

If you keep this, let's make it do { } while (false).

This revision is now accepted and ready to land.Nov 16 2021, 6:55 AM
danlark updated this revision to Diff 387619.Nov 16 2021, 6:55 AM

Improve the library build support

danlark updated this revision to Diff 387625.Nov 16 2021, 7:23 AM
danlark marked 3 inline comments as done.

I hope this is the last update

danlark added inline comments.Nov 16 2021, 7:24 AM
libcxx/include/__algorithm/shuffle.h
28

Question, windows DLLs were not able to build the tests without _LIBCPP_BUILDING_LIBRARY as I guess because of constructor/destructor ABI of trivial types, should I leave it like that?

Linux and MacOS seem fine without it

libcxx/include/__config
867–874

I actually prefer the macro, the change looks cleaner

ldionne added inline comments.Nov 16 2021, 7:29 AM
libcxx/include/__algorithm/shuffle.h
28

Oh, I actually meant to leave a comment here but forgot. Let's include this unconditionally, in other words remove the #if defined altogether.

When _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY is not used, this is simply going to be an unused type, which doesn't hurt. But at least we'll know it parses properly.

libcxx/include/__config
876
danlark updated this revision to Diff 387636.Nov 16 2021, 7:35 AM
danlark marked 2 inline comments as done.

Remove the ifdef for __libcpp_debug_randomizer

libcxx/include/__algorithm/shuffle.h
28

Thanks!

ldionne accepted this revision.Nov 16 2021, 7:37 AM

Let's land this once CI is passing.

I want to thank you for spending time on this issue and being patient with the long review times you experienced. We have a lot of things going on and can only focus on so many things at once, and we always have to prioritize things. I'm glad we finally finished this.

danlark updated this revision to Diff 387721.Nov 16 2021, 11:33 AM

Fix CI and linter

Feel free to revert or ask me to revert the linter changes in __config, clang-format was noisy :)

libcxx/include/__algorithm/shuffle.h
28

Btw, I hope that the long-long-term plan is to split up <random> into <__random/*.h>, and then we could just #include <__random/minstd_rand0.h> and eliminate this type altogether. If you can think of a reason we shouldn't plan on doing that, this would be a good time to mention it.
(I guess one reason is that minstd_rand0 comes with its own operator<<, which drags in <iosfwd>; but that's work-aroundable if we need to; we'd just split the operator<< stuff into its own header.)

libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp
73

This lambda is just std::less<MyType>(), right?

ldionne added inline comments.Nov 16 2021, 12:56 PM
libcxx/include/__algorithm/shuffle.h
28

Ah, so you do like the modularization of headers, then? 😄

We can address this later when we modularize <random> (yes, that is the long term goal).

libcxx/test/libcxx/algorithms/nth_element_stability.pass.cpp
19–23

Just for posterity, we try to keep includes sorted. Fixed upon committing.

73

Fixed upon committing.

This revision was landed with ongoing or failed builds.Nov 16 2021, 12:56 PM
This revision was automatically updated to reflect the committed changes.
libcxx/include/__algorithm/shuffle.h
28

If we hadn't already decided to modularize everything regardless of motivation, then this would strike me as good motivation to split out a lightweight <__random_base>, and it could have been done right in this PR instead of being a project in itself. 😉
(danlark: No action needed. :))

I guess I could volunteer to split up <random>... Once D110738 and D111514 land, I'll launch that project.

MaskRay added a subscriber: MaskRay.Feb 4 2022, 8:37 PM

I wonder whether it is useful to allocate some probability to a deterministic reorder, e.g. reversed order (see D98445 I added ld.lld --shuffle-sections=-1).

libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst
39

This and a few other works should use reST inline literals. Created D119052