This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Fix an exception safety issue in `forward_list` and add tests.
ClosedPublic

Authored by var-const on Jun 6 2023, 6:20 PM.

Details

Summary

When inserting nodes into a forward list, each new node is allocated but
not constructed. The constructor was being called explicitly on the node
value_ but the next_ pointer remained uninitialized rather than
being set to null. This bug is only triggered in the cleanup code if an
exception is thrown -- upon successful creation of new nodes, the last
incorrect "next" value is overwritten to a correct pointer.

This issue was found due to new tests added in
https://reviews.llvm.org/D149830.

Diff Detail

Event Timeline

var-const created this revision.Jun 6 2023, 6:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 6 2023, 6:20 PM
var-const requested review of this revision.Jun 6 2023, 6:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 6 2023, 6:20 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Thanks a lot for fixing this and adding test coverage! I suspected it was indeed a "silly" mistake in the current code. I have a few comments below.

libcxx/include/forward_list
1254–1256 ↗(On Diff #529115)

This makes me wonder whether we should instead be constructing this with e.g. make_unique. Why don't we have a proper constructor for __node and call that instead, it would make sure that we never forget to initialize some of its members. Do you have thoughts about this?

libcxx/test/std/containers/exception_safety_helpers.h
14

<cstddef> is missing, there is a reference to std::size_t below.

16

You need to include test_macros.h.

libcxx/test/std/containers/sequences/forwardlist/robust_against_exceptions.pass.cpp
71

The fact that ThrowingCopy will throw after 3 copies is hardcoded inside test_exception_safety_throwing_copy_iterator_pair, making this a false abstraction IMO. Like I can't understand this test without immediately reading what test_exception_safety_throwing_copy_iterator_pair does and understanding that I need to construct at least 3 elements below to make this test work as expected. This makes me wonder whether this is a good candidate for a function.

ldionne added inline comments.Jun 7 2023, 1:19 PM
libcxx/include/forward_list
1254–1256 ↗(On Diff #529115)

This is what I had in mind:

unique_ptr<__node, _Dp> __h = std::make_unique<__node>(__node(__v, __next=nullptr) _Dp(__a, 1));

Now we need to allocate using the right allocator, so we might need to use something like __allocation_guard instead:

__allocation_guard<__node_allocator> __h(__a, 1);
std::construct_at(__h.__get(), __v, /*next*/nullptr); // this is nicer here cause we call the node's constructor for real
__node_pointer __first = __h.__release();

Nice catch! Thanks for working on this.

libcxx/test/std/containers/exception_safety_helpers.h
37

Would deleting the function have the same effect?

76–77

Alternatively there is the TEST_VALIDATE_EXCEPTION macro which I use in the formatting tests
libcxx//data/src/llvm/libcxx/test/std/utilities/format/format.functions/vformat.pass.cpp for example.

var-const updated this revision to Diff 537577.Jul 5 2023, 9:34 PM
var-const marked 4 inline comments as done.

Address feedback

libcxx/include/forward_list
1254–1256 ↗(On Diff #529115)

Unfortunately, construct_at doesn't work because it expects the argument to be a raw pointer whereas the allocator might define the pointer type to be a class. We could avoid using construct_at but I'm not sure this is worth pursuing -- what do you think?

libcxx/test/std/containers/exception_safety_helpers.h
37

No, operator= is still used within instantiated code (even if it's not invoked at runtime), and the compiler complains about overload resolution choosing a deleted function.

76–77

Hmm, is having an assert(false) preferable to just letting the wrong exception escape and crash the test?

libcxx/test/std/containers/sequences/forwardlist/robust_against_exceptions.pass.cpp
71

Reworked the function to take the total number of elements created and the number of the throwing copy as template parameters. I also reduced the number of these functions to just two, removing some of the convenience ones (the _container one is a bit more difficult to remove because creating the container inside the user callback means the container would get destroyed when the exception is thrown, increasing the number of destroyed elements; then it becomes harder to check how many elements were destroyed inside the helper function).

ldionne added inline comments.Jul 6 2023, 11:37 AM
libcxx/include/forward_list
1254–1256 ↗(On Diff #529115)

This is what we do in other places with the same pattern:

(void*)std::addressof(*__guard.__get()));

You can see this at play for example in libcxx/include/__memory/shared_ptr.h around shared_ptr<_Tp> allocate_shared(const _Alloc& __a, _Args&& ...__args).

ldionne accepted this revision.Jul 6 2023, 11:55 AM

LGTM w/ comments and passing CI, thanks!

libcxx/test/std/containers/exception_safety_helpers.h
12

#include <functional> for hash

77
libcxx/test/std/containers/sequences/forwardlist/robust_against_exceptions.pass.cpp
1

Let's call this something like exception_safety.pass.cpp since robust_against_foo has a different meaning in the test suite (usually it means it's something we do across a large number of types).

This revision is now accepted and ready to land.Jul 6 2023, 11:55 AM
var-const updated this revision to Diff 537944.Jul 6 2023, 6:02 PM
var-const marked 3 inline comments as done.

Partially address feedback, fix accidental revertal

var-const updated this revision to Diff 537949.Jul 6 2023, 6:48 PM
var-const marked 3 inline comments as done.

Address feedback

var-const added inline comments.Jul 6 2023, 7:10 PM
libcxx/include/forward_list
1254–1256 ↗(On Diff #529115)

Done. I've had to make __allocation_guard follow the rule of 5.

var-const updated this revision to Diff 538204.Jul 7 2023, 10:48 AM

Fixing CI.

ldionne requested changes to this revision.Jul 7 2023, 12:32 PM
ldionne added inline comments.
libcxx/include/__memory/allocation_guard.h
48 ↗(On Diff #538204)

I feel bad for not doing this when I wrote the class (IIRC), but we should add a few basic libcxx/test/libcxx tests for basic functionality. Don't go crazy, but at least basic usage. If I had done that, I wouldn't have written a class that has 4x incorrectly defined special members. 🤦🏼‍♂️

libcxx/include/forward_list
1264–1266 ↗(On Diff #538204)

Here, I might put these three lines into a scope of their own. That way, we end the lifetime of the guard so we can easily understand it's not needed anymore. Then, within the for loop below, you can just create a new guard variable every time.

1265 ↗(On Diff #538204)

You're bypassing any allocator's ::construct method in the new patch. I think you want to keep using _node_traits::construct instead.

It should be easy to add a test with a simple custom allocator where you can check that its construct method has been called.

1275 ↗(On Diff #538204)

Same about ::construct.

This revision now requires changes to proceed.Jul 7 2023, 12:32 PM
var-const updated this revision to Diff 538300.Jul 7 2023, 5:16 PM
var-const marked 3 inline comments as done.

Partially address feedback.

var-const updated this revision to Diff 538307.Jul 7 2023, 7:04 PM
var-const marked an inline comment as done.

Address feedback.

var-const marked an inline comment as done.Jul 7 2023, 7:05 PM
var-const added inline comments.
libcxx/include/__memory/allocation_guard.h
48 ↗(On Diff #538204)

Added some tests, please let me know what you think.

libcxx/include/forward_list
1264–1266 ↗(On Diff #538204)

Done. I think it's cleaner that way as well, it's more obvious what exactly the guard is protecting.

1265 ↗(On Diff #538204)

Switched back to using __node_traits::construct.

Re. testing -- it seems like this would mean adding tests to all the functions that might allocate (IMO conceptually there's no reason to add the test only to insert_after), which I think is a bit overkill for this patch. In the future, I'd be happy to add a suite of tests like allocator_aware.pass.cpp to check all the allocator-related requirements in one place.

ldionne accepted this revision.Jul 10 2023, 12:22 PM

LGTM w/ green CI. I think it's failing because your allocation_guard test isn't C++11/C++03 friendly.

This revision is now accepted and ready to land.Jul 10 2023, 12:22 PM
var-const updated this revision to Diff 538877.Jul 10 2023, 5:13 PM
var-const marked an inline comment as done.

Fix the CI.

var-const updated this revision to Diff 539356.Jul 11 2023, 6:26 PM

Fix the CI.

It looks like the back-deployment test failed due to a configuration issue unrelated to the patch:

# command stderr:
ld: file not found: /Library/Developer/CommandLineTools/usr/lib/arc/libarclite_macosx.a
clang: error: linker command failed with exit code 1 (use -v to see invocation)

I'll go ahead and merge this patch now.

This revision was landed with ongoing or failed builds.Jul 12 2023, 10:11 AM
This revision was automatically updated to reflect the committed changes.