[libc++] Implement `stop_token`

[huixie90]

Summary

Implement stop_token
http://eel.is/c++draft/thread.stoptoken

[Mordante]

I mainly glanced over the patch and didn't look at the wording.

libcxx/docs/Status/Cxx20Papers.csv

107

After this patch it's partial :-) Can you document which parts are still missing?

We have multiple partial done papers, without any information what is and what is not done. That makes it hard to finish these papers.

libcxx/include/__stop_token/stop_source.h

34

I miss _LIBCPP_HIDE_FROM_ABI on most (all?) functions.

libcxx/include/__stop_token/stop_state.h

48

maybe move constants __stop_requested_bit here too, that makes it clear they belong together.

191

Did you consider using RAII based locking?

[huixie90]

add tests

[huixie90]

add tests. addressed feedback

[huixie90]

hidden from abi

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[huixie90]

CI

[huixie90]

try again

[huixie90]

next try

[ldionne]

Geez, this is more complicated than I expected. Thanks a lot for working on this, we'll get through the whole thing.

libcxx/include/__stop_token/stop_state.h

54

Would it make sense to try to extract this into a more general utility? It's really tricky to review, as we both just discussed it for a while, and I think trying to extract it into its own utility would help us make gradual progress on the review.

65–66

Are we ever calling this with __is_locked == false? If so, it seems like this class is kind of like an optional<__lock_guard>. I would have expected that this constructor instead takes something like a __already_locked_t tag to express that the lock has already been taken.

131

Maybe we should look into extracting the intrusive linked-list related functionality into something reusable? Would that be doable, and if so would it make the code simpler?

[Mordante]

Thanks a lot for working on this!

I looked at the header code and did some reviewing, but not completely.

This code is quite hard to understand and the Standard gives implementers a lot of freedom how to implement this. So I really would like more documentation regarding the design and some of the libc++ specific pre and post conditions. Without this information it will very hard to review and maintain this code.

libcxx/docs/Status/Cxx20Papers.csv

107

Since you implement this feature using eelis instead of a paper you get
LWG3254 (https://wg21.link/LWG3254 Strike stop_token's operator!=) for free, can you mark this issue as done too?

107

Can you use a not to mark the status. Look at the line above P0645 for an example.

libcxx/include/__stop_token/stop_callback.h

88

We're already in the private section.

libcxx/include/__stop_token/stop_state.h

41

Can you add more documentation regarding what these fields mean.

Looking at the loop in
LIBCPP_HIDE_FROM_ABI bool __add_callback(__stop_callback_base* __cb) noexcept
I see several flag tested and the lock is the latest to be tested.

I would expect the lock the first to be tested.

86

Please don't use auto. This makes it hard to review the code or use it without and IDE. I need to look at load to see the type. (Note that the LLVM coding style also discourage auto.)

185

Can you explain why this relaxed it the right order?

190

How do you prevent calling the callback multiple times.

297

312

Note my atomics knowledge is a bit rusty.
Why is this memory_order_relaxed instead of memory_order_release?

AFAIK the current increment may not be visible in a different thread doing a decrement.
Which may cause use-after-free and double-free issues of the __state.

libcxx/include/stop_token

35–38

I assume the feature will get a FTM once done.

[huixie90]

libcxx/include/__stop_token/stop_state.h

41

yeah I will refactor/rename the code and add more comments. the lock bit is for locking the linked-list. The reason why it was not locked first is that the spec specified that if the requested bit was set, we won't go through the linked-list and instead directly invoke the callback on the current thread.

185

will add comments. all the atomic operations here won't need any memory ordering except the one actually does the lock.

190

once it is called, the next line would return.

312

Note that this is the same case for shared_ptr where increment is relaxed and decrement is acq_rel
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__memory/shared_ptr.h#L105

The memory ordering controls the visibility of the write operations (including non-atomic operations) prio to current atomic operation, and read operations after the current atomic operation.

For increment, we don't need to do anything before and afterwards, so memory_order_relaxed is enough.
For decrement, we are potentially evaluating the destructor of underlying type T. We need to make sure that there are no other threads that are still poking around the underlying object through a different shared_ptr instance. i.e. any operations on the underlying object on any thread should be "finished" before evaluating the destructor.

We need release to tell other threads that we are done with the underlying object and all the writes to the underlying object should be visible now. (suppose you are writing to the underlying object before the shared_ptr goes out of scope, so that in case a different thread which has the last shared_ptr calls the destructor, it needs to see this write)
In case we are calling the destructor, we need acquire to see other threads write (see above).
So decrement needs both.

The way I understand is that:
acquire is git pull. All the read operations after it would see the latest.
release is git push. All the write operations before it would be visible by other threads which pulls.

please also note that shared_ptr (similarly here) does not protect you from incorrect use. When used properly, the copy operations would either copy from a nullptr or a shared_ptr which ref count is at least 1.. if you invoke a copy constructor and spawn a thread to assign the copied-from instance to nullptr. it is plain UB because you are writing and reading to the same shared_ptr object (data race)

libcxx/include/stop_token

35–38

yes there is only one FTM for stop_token and jthread. will get the FTM once jthread is done

[huixie90]

refactoring:
spliting the lock and the linked list into separate classes

[huixie90]

libcxx/include/__stop_token/stop_state.h

312

Adding to my previous explanation. I think you might mix the visibility of other operations prior/after the atomic operations, with the visibility of the atomic operation itself. I think we never talk about the visibility of atomic operation itself when we talk about memory_order. The question of memory_order is, when atomic load sees another atomic store, what other operations are guaranteed to be seen. for example

int a = 0;
atomic<int> b = 0;

// thread A
a = 5;
b.store(3, std::memory_order_release);

// thread B
auto tmp = b.load(std::memory_order_acquire);
assert(tmp!=3 || a==5);

what the memory ordering concerns is that when thread B loads b and the value is 3, the release/acquire memory order ensures that thread B can also see that a has value 5.
Whether or not thread B sees b is 3 is not memory order problem. It is just a timing issue,

[huixie90]

CI

[huixie90]

address comments

[huixie90]

libcxx/include/__stop_token/stop_state.h

54

extracted the locking logic into atomic_unique_lock.h

65–66

refactor the class. Instead of constructing with boolean, now the class has a constructor that takes early-fail-return predicate

[huixie90]

CI

[huixie90]

CI

[huixie90]

try again

[huixie90]

next try

[huixie90]

Fix typo as pointed out by Arthur

[Mordante]

Thanks for the additional information and the additional documentation. I see the CI is still red, so I prefer to review it with a green CI. (Especially the thread sanitizer.) Feel free to ping me when the CI is green.

libcxx/include/__stop_token/stop_state.h

312

Thanks for the additional information. I also reread some parts of Anthony Williams book.