{"id":110738,"date":"2025-01-09T07:00:00","date_gmt":"2025-01-09T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110738"},"modified":"2025-01-13T13:08:00","modified_gmt":"2025-01-13T21:08:00","slug":"20250109-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20250109-00\/?p=110738","title":{"rendered":"Inside STL: Waiting for a std::atomic<std::shared_ptr<T>><\/CODE> to change, part 2"},"content":{"rendered":"

Last time, we looked at how the Microsoft C++ standard library implements wait<\/code> and notify_*<\/code> for std::atomic<std::shared_ptr<T>><\/code><\/a>. Today, we’ll look at the other library that (as of this writing) implements std::atomic<std::shared_ptr<T>><\/code>: libstdc++.<\/p>\n

The first thing to note is that the traditional “wait for a value to change” mechanism on unix is the futex, but futexes (futexen<\/a>?) are limited to 4-byte values, which is insufficient for a 64-bit pointer, much less the two<\/i> pointers inside a shared_ptr<\/code>.<\/p>\n

At this point, I will refer you to learn about how libstdc++ implements waits on atomic values<\/a>, particularly the section on how it handles types that do not fit in a __platform_wait_t<\/code><\/a>. The remainder of this discussion will treat that as an already-solved problem and focus on the shared pointer part.<\/p>\n

Okay, back to atomic<shared_ptr<T>>::wait()<\/code><\/a>:<\/p>\n

\/\/ atomic<shared_ptr<T>>::wait\r\nvoid\r\nwait(value_type __old,\r\n     memory_order __o = memory_order_seq_cst) const noexcept\r\n{\r\n    _M_impl.wait(std::move(__old), __o);\r\n}\r\n<\/pre>\n
When you wait on a shared_ptr<\/code>, the work is done by  _Sp_atomic::wait<\/code><\/a>:<\/p>\n
\/\/ _Sp_atomic<shared_ptr<T>>::wait\r\nvoid\r\nwait(value_type __old, memory_order __o) const noexcept\r\n{\r\n    auto __pi = _M_refcount.lock(memory_order_acquire);\r\n    if (_M_ptr == __old._M_ptr && __pi == __old._M_refcount._M_pi)\r\n      _M_refcount._M_wait_unlock(__o);\r\n    else\r\n      _M_refcount.unlock(memory_order_relaxed);\r\n}\r\n<\/pre>\n
The code locks the shared_ptr<\/code> (by  setting the bottom bit of the control block pointer<\/a>, as we discussed earlier<\/a>), then checks whether the stored pointer and control block pointer both match. If not, then the wait is satisfied, and we release the lock and return. Otherwise, we ask  _Atomic_count::_M_wait_unlock<\/code><\/a> to finish the wait.<\/p>\n
\/\/ _Atomic_count::_M_wait_unlock\r\nvoid\r\n_M_wait_unlock(memory_order __o) const noexcept\r\n{\r\n    auto __v = _M_val.fetch_sub(1, memory_order_relaxed);\r\n    _M_val.wait(__v & ~_S_lock_bit, __o);\r\n}\r\n\r\nmutable __atomic_base<uintptr_t> _M_val{0};\r\n<\/pre>\n
As the name suggests, _M_wait_unlock<\/code> clears the lock bit (thereby unlocking the shared pointer) and then waits for value to change from its current value.<\/p>\n
Meanwhile,  the notify_*<\/code> methods<\/a> do something similar:<\/p>\n
\/\/ atomic<shared_ptr<T>>::notify_*\r\nvoid\r\nnotify_one() noexcept\r\n{\r\n    _M_impl.notify_one();\r\n}\r\n\r\nvoid\r\nnotify_all() noexcept\r\n{\r\n    _M_impl.notify_all();\r\n}\r\n<\/pre>\n
They forward to  _Sp_atomic::notify_*<\/code><\/a>:<\/p>\n
\/\/ _Sp_atomic<shared_ptr<T>>::notify_*\r\nvoid\r\nnotify_one() noexcept\r\n{\r\n    _M_refcount.notify_one();\r\n}\r\n\r\nvoid\r\nnotify_all() noexcept\r\n{\r\n    _M_refcount.notify_all();\r\n}\r\n<\/pre>\n
And those forward to  _Atomic_count::notify_*<\/code><\/a>:<\/p>\n
\/\/ _Atomic_count::notify_*\r\nvoid\r\nnotify_one() noexcept\r\n{\r\n    _M_val.notify_one();\r\n}\r\n\r\nvoid\r\nnotify_all() noexcept\r\n{\r\n    _M_val.notify_all();\r\n}\r\n\r\nmutable __atomic_base<uintptr_t> _M_val{0};\r\n<\/pre>\n
which forward the notify to the atomic value.<\/p>\n
So at the end of the day, waiting on and notifying an atomic shared pointer boils down to waiting on and notifying its control block pointer.<\/p>\n
But hang on a second. The language specification says that a wait on an atomic shared pointer is satisfied when either<\/i> the stored pointer or<\/i> the control block pointer changes. But this code waits only for the control block pointer to change. Do we have a bug?<\/p>\n
Let’s write a test program to see whether our theory holds up, or whether there’s something else (like msvc’s exponential backoff) that saves us.<\/p>\n
#include <memory>\r\n#include <chrono>\r\n#include <thread>\r\n\r\nstd::shared_ptr<int> q = std::make_shared<int>(42);\r\nstd::atomic<std::shared_ptr<int>> p = q;\r\n\r\nvoid signaler()\r\n{\r\n    std::this_thread::sleep_for(std::chrono::seconds(1));\r\n    p.store({ q, nullptr });\r\n    p.notify_one();\r\n    std::this_thread::sleep_for(std::chrono::seconds(1));\r\n    std::terminate();\r\n}\r\n\r\nint main(int, char**)\r\n{\r\n    std::thread(signaler).detach();\r\n    p.wait(q);\r\n    return 0;\r\n}\r\n<\/pre>\n
This program starts a thread that waits one second to give the main thread a chance to reach p.wait()<\/code>. It then changes the atomic shared pointer by modifying only the stored pointer and reusing the control block, and then notifies the main thread. If the program is still running after one second, then the wait was not woken, and we terminate the program.<\/p>\n
Meanwhile, after starting the signaler thread, the main thread waits on the atomic shared pointer, and when the wait is satisfied, it exits the program.<\/p>\n
You expect this program to exit cleanly. The signaling thread modifies the atomic shared pointer, which satisfies the wait. (Even if we didn’t sleep one second before modifying the atomic shared pointer, the wait would still be satisfied because the value in the atomic shared pointer no longer matches q<\/code>.)<\/p>\n
In practice, this program crashes at the std::terminate<\/code>.<\/p>\n
So it looks like we found a bug in libstdc++. (-dumpversion<\/code> says 14.2.0.) Waiting on an atomic shared pointer does not notify if the the shared pointer changed only its stored pointer and not its control block. The atomic wait should be a 16-byte wait that covers both the stored pointer and the control block pointer.<\/p>\n
Bonus chatter<\/b>: I find it interesting that the language specification  added wait\/notify support to atomic shared pointers<\/a> as an afterthought, with barely any discussion or contemplation, as if it had been deemed too trivial to be worth worrying about. And two of the three major implementations messed it up. (What about the third major implementation, clang’s libc++? Oh,  they haven’t implemented it yet<\/a>!)<\/p>\n
I was curious about this topic because the first thing that struck me about notify\/wait on atomic shared pointers was “Gosh, shared pointers are twice the size of regular pointers. I wonder how the implementations manage to wait atomically on something that is larger than a register?” And when I dug into the implementations, I found that the answer was “not correctly.”<\/p>\n","protected":false},"excerpt":{"rendered":"
Digging into the libstdc++ implementation.<\/p>\n","protected":false},"author":1069,"featured_media":110434,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-110738","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Digging into the libstdc++ implementation.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110738","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=110738"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110738\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/110434"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=110738"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110738"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110738"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}