{"id":110320,"date":"2024-09-27T07:00:00","date_gmt":"2024-09-27T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=110320"},"modified":"2024-09-27T09:04:04","modified_gmt":"2024-09-27T16:04:04","slug":"20240927-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20240927-00\/?p=110320","title":{"rendered":"The case of the crash when destructing a <CODE>std::map<\/CODE>"},"content":{"rendered":"<p>A customer reported that they were getting crashes while destructing a <code>std::map<\/code>.<\/p>\n<p>Here&#8217;s the point of the crash:<\/p>\n<pre>eax=245bd25c ebx=00004d33 ecx=31feece4 edx=00c40000 esi=00000000 edi=31feece4\r\neip=563397db esp=245bd250 ebp=245bd268 iopl=0         nv up ei ng nz na pe nc\r\ncs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010286\r\ncontoso!std::_Tree&lt;\u27e6...\u27e7&gt;::~_Tree+0x2b:\r\n563397db cmp     byte ptr [esi+0Dh],0                       ds:002b:0000000d=??\r\n\r\n0:054&gt; k9\r\nChildEBP RetAddr      \r\n(Inline) --------     contoso!std::_Tree_val&lt;\u27e6...\u27e7&gt;::_Erase_tree [xtree @ 1073]\r\n(Inline) --------     contoso!std::_Tree_val&lt;\u27e6...\u27e7&gt;::_Erase_head+0x5 [xtree @ 1073]\r\n245bd268 56338313     contoso!std::_Tree&lt;\u27e6...\u27e7&gt;::~_Tree+0x2b [xtree @ 1073]\r\n245bd290 56362695     contoso!Contoso::IdCollection::~IdCollection+0x163\r\n245bd2b4 564c8510     contoso!Contoso::LogEntry::~LogEntry+0xd5\r\n245bd2e0 5691a999     contoso!Contoso::LogEntries::Cleanup+0x90\r\n(Inline) --------     contoso!Contoso::Log::Flush+0x8\r\n245be134 56916406     contoso!Contoso::TaskRunner::RunTasks+0x3949\r\n<\/pre>\n<p>Okay, so we are trying to destruct a <code>_Tree<\/code>, which is the internal class that acts as the basis for <code>map<\/code>, <code>multimap<\/code>, <code>set<\/code>, and <code>multiset<\/code>. In this case, we are destructing a <code>std::map<\/code>.<\/p>\n<p>I <span style=\"text-decoration: line-through;\">wasted<\/span> invested a good amount of time reading the STL source code in order to figure out <a title=\"Inside STL: The map, set, multimap, and multiset\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230807-00\/?p=108562\"> the internal structure of <code>std::map<\/code><\/a>. You can read the linked article for the details, but the short version is that the map consists of a sentinel node where<\/p>\n<ul>\n<li>sentinel.left = first node in the tree<\/li>\n<li>sentinel.right = last node in the tree<\/li>\n<li>sentinel.parent = root node of the tree<\/li>\n<\/ul>\n<p>For the root node and other nodes of the tree, the left, right, and parent have their normal meanings.<\/p>\n<p>If there is no root node, left subtree, or right subtree, then the corresponding member contains a pointer to the sentinel node. (The use of a sentinel node is a standard computer science trick which removes the need to add null pointer checks everywhere.)<\/p>\n<p>We can read the STL code to see how tree destruction occurs.<\/p>\n<p>We start with <a href=\"https:\/\/github.com\/microsoft\/STL\/blob\/8dc4faadafb52e3e0a627e046b41258032d9bc6a\/stl\/inc\/xtree#L1071\"> the <code>_Tree<\/code> destructor<\/a>:<\/p>\n<pre>    ~_Tree() noexcept {\r\n        const auto _Scary = _Get_scary();\r\n        _Scary-&gt;_Erase_head(_Getal());\r\n    }\r\n<\/pre>\n<p>The <code>Scary<\/code> stuff is just to scare you. It&#8217;s just getting a value from the tree.<\/p>\n<pre>    _Scary_val* _Get_scary() noexcept {\r\n        return _STD addressof(_Mypair._Myval2._Myval2);\r\n    }\r\n<\/pre>\n<p>Meanwhile, <a href=\"https:\/\/github.com\/microsoft\/STL\/blob\/8dc4faadafb52e3e0a627e046b41258032d9bc6a\/stl\/inc\/xtree#L751\"> <code>_Erase_head<\/code> goes like this<\/a>:<\/p>\n<pre>    template &lt;class _Alnode&gt;\r\n    void _Erase_head(_Alnode&amp; _Al) noexcept {\r\n        this-&gt;_Orphan_all();\r\n        _Erase_tree(_Al, _Myhead-&gt;_Parent);\r\n        _Alnode::value_type::_Freenode0(_Al, _Myhead);\r\n    }\r\n<\/pre>\n<p>This just erases the tree and then frees the sentinel node. So <a href=\"https:\/\/github.com\/microsoft\/STL\/blob\/8dc4faadafb52e3e0a627e046b41258032d9bc6a\/stl\/inc\/xtree#L742\"> the real excitement is in _Erase_tree<\/a>:<\/p>\n<pre>    template &lt;class _Alnode&gt;\r\n    void _Erase_tree(_Alnode&amp; _Al, _Nodeptr _Rootnode) noexcept {\r\n        while (!_Rootnode-&gt;_Isnil) { \/\/ free subtrees, then node\r\n            _Erase_tree(_Al, _Rootnode-&gt;_Right);\r\n            _Alnode::value_type::_Freenode(_Al,\r\n                _STD exchange(_Rootnode, _Rootnode-&gt;_Left));\r\n        }\r\n    }\r\n<\/pre>\n<p>Erasing the tree consists of recursively erasing the right node, freeing the node, and tail recursing on the left node.<\/p>\n<p>Now, the crashing instruction is cmp byte ptr [esi+0Dh],0, which is obviously the <code>_Rootnode-&gt;_Isnil<\/code>. &#8220;Obviously&#8221; because it is the only place we check a byte. All other operations are on pointers.<\/p>\n<p>But let&#8217;s look at the crash in the context of the whole function just to make sure, and see what else we can learn.<\/p>\n<pre>\/\/ Function prologue nonsense\r\n\r\ncontoso!std::_Tree&lt;\u27e6...\u27e7&gt;::~_Tree\r\n563397b0 push    ebp\r\n563397b1 mov     ebp,esp\r\n563397b3 push    0FFFFFFFFh\r\n563397b5 push    offset contoso!___guard_check_icall_thunk+0x25d0 (56d0e690)\r\n563397ba mov     eax,dword ptr fs:[00000000h]\r\n563397c0 push    eax\r\n563397c1 push    esi\r\n563397c2 push    edi\r\n563397c3 mov     eax,dword ptr [contoso!__security_cookie (5427c040)]\r\n563397c8 xor     eax,ebp\r\n563397ca push    eax\r\n563397cb lea     eax,[ebp-0Ch]\r\n563397ce mov     dword ptr fs:[00000000h],eax\r\n\r\n\/\/ inlined _Erase_head\r\n\r\n563397d4 mov     edi,ecx                ; edi = this\r\n563397d6 mov     esi,dword ptr [edi]    ; esi = _Myhead\r\n563397d8 mov     esi,dword ptr [esi+4]  ; esi = _Myhead.Parent\r\n\r\n\/\/ inlined _Erase_tree (esi = _Rootnode)\r\n\r\n563397db cmp     byte ptr [esi+0Dh],0   ; while (!_Rootnode-&gt;_Isnil) \u2190 CRASHED HERE\r\n563397df jne     contoso!std::_Tree&lt;\u27e6...\u27e7&gt;::~_Tree+0x51 (56339801) ; break out of loop\r\n\r\nloop:\r\n\/\/ Recursive call to _Erase_tree\r\n563397e1 push    dword ptr [esi+8]      ; _Rootnode-&gt;_Right\r\n563397e4 mov     ecx,edi                ; outbound this = inbound this\r\n563397e6 push    edi                    ; allocator\r\n563397e7 call    contoso!std::_Tree_val&lt;\u27e6...\u27e7&gt;::_Erase_tree (5633b450) ; erase the subtree\r\n\r\n563397ec mov     eax,esi                ; delete the old _Rootnode\r\n563397ee mov     esi,dword ptr [esi]    ; fetch _Rootnode-&gt;_Left for tail recursion\r\n563397f0 push    18h\r\n563397f2 push    eax\r\n563397f3 call    contoso!operator delete (56d08334) ; free the old _Rootnode\r\n563397f8 add     esp,8\r\n\r\n563397fb cmp     byte ptr [esi+0Dh],0   ; while (!_Rootnode-&gt;_Isnil)\r\n563397ff je      contoso!std::_Tree&lt;\u27e6...\u27e7&gt;::~_Tree+0x31 (563397e1)\r\n\r\n\/\/ end of _Erase_head, now free the sentinel node\r\n\r\n56339801 push    18h\r\n56339803 push    dword ptr [edi]\r\n56339805 call    contoso!operator delete (56d08334)\r\n5633980a add     esp,8\r\n\r\n5633980d mov     ecx,dword ptr [ebp-0Ch]\r\n56339810 mov     dword ptr fs:[0],ecx\r\n56339817 pop     ecx\r\n56339818 pop     edi\r\n56339819 pop     esi\r\n5633981a mov     esp,ebp\r\n5633981c pop     ebp\r\n5633981d ret\r\n<\/pre>\n<p>Okay, so we were right that the crash was on the test of <code>_Rootnode-&gt;_Isnil<\/code>, but we also learned that this is the test that occurs before entering the loop body for the first time. (The tests that occur on subsequent iterations come later in the function.)<\/p>\n<p>This is great, because it tells us that no changes to the tree have been made yet. We aren&#8217;t looking at a tree in a temporarily invalid state because the destructor is messing with it. Instead, the tree is still its originally-corrupted state.<\/p>\n<p>The crash is on a null <code>_Rootnode<\/code>, and that came from <code>_Myhead._Parent<\/code>, so our tree must have a null <code>_Myhead._Parent<\/code>, which is not allowed. (An empty tree has a <code>_Myhead._Parent<\/code> that points back to the sentinel node.)<\/p>\n<p>Let&#8217;s see what we have in the tree.<\/p>\n<pre>0:054&gt; ?? this-&gt;_Mypair._Myval2._Myval2\r\nclass std::_Tree_val&lt;\u27e6...\u27e7&gt;\r\n   +0x000 _Myhead          : 0x1ca4f280 std::_Tree_node&lt;\u27e6...\u27e7&gt;\r\n   +0x004 _Mysize          : 0\r\n<\/pre>\n<p>Okay, so this tree is empty (_Mysize is zero).<\/p>\n<pre>0:054&gt; ?? this-&gt;_Mypair._Myval2._Myval2._Myhead\r\nstruct std::_Tree_node&lt;\u27e6...\u27e7&gt; * 0x1ca4f280\r\n   +0x000 _Left            : 0xc00000b0 std::_Tree_node&lt;\u27e6...\u27e7&gt;\r\n   +0x004 _Parent          : (null) \r\n   +0x008 _Right           : 0x1ca4f280 std::_Tree_node&lt;\u27e6...\u27e7&gt;\r\n   +0x00c _Color           : 1 ''\r\n   +0x00d _Isnil           : 1 ''\r\n   +0x010 _Myval           : std::pair&lt;int const, enum ChannelType&gt;\r\n<\/pre>\n<p>As expected, this is the sentinel node, (_Isnil is 1). What&#8217;s not expected is that the <code>_Parent<\/code> is null, and the <code>_Left<\/code> is corrupted. The <code>_Right<\/code> is okay: It points back to the sentinel node.<\/p>\n<p>That corrupted value for <code>_Left<\/code> looks really suspicious: It is of the form <code>0xc000nnnn<\/code>, which is the range used by <code>NTSTATUS<\/code> codes. And if we dump the node as bytes, we can see that the corruption is restricted to just those first two dwords.<\/p>\n<pre>0:054&gt; dc 1ca4f280 L10\r\n1ca4f280  c00000b0 00000000 1ca4f280 00000101  ................\r\n          ^^^^^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^^^^^\r\n         corrupted corrupted    okay     okay\r\n<\/pre>\n<p>What is the <code>NTSTATUS<\/code> code that got written?<\/p>\n<pre>C:\\&gt;certutil \/error 0xc00000b0\r\n0xc00000b0 (NT: 0xc00000b0 STATUS_PIPE_DISCONNECTED) -- 3221225648 (-1073741648)\r\nError message text: The specified named pipe is in the disconnected state.\r\nCertUtil: -error command completed successfully.\r\n<\/pre>\n<p>To me, this looks like what happens when an overlapped I\/O completes. The first two fields of the <code>OVERLAPPED<\/code> structure are updated by the kernel at the completion of the I\/O, and the two things it writes are the status code and the number of bytes transferred (which is unsurprisingly zero seeing as an error occurred).<\/p>\n<p>My theory was that this program at some point issued an overlapped I\/O and freed the <code>OVERLAPPED<\/code> structure associated with the I\/O before the I\/O completed. That memory then got reused to hold the <code>std::map<\/code> sentinel node, and then the I\/O completed, and the kernel wrote the I\/O result into what it thought was the <code>OVERLAPPED<\/code> structure (but is now the <code>std::map<\/code> sentinel node), thereby corrupting the sentinel node.<\/p>\n<p>The customer said, &#8220;We don&#8217;t use overlapped I\/O, but maybe one of the libraries we use does.&#8221;<\/p>\n<p>They provided their source code in the form of a massive 5 gigabyte ZIP file. Thankfully, they also gave me access to their online repo, so I could use the search functionality in their repo hosting provider.<\/p>\n<p>I searched their code for <code>OVERLAPPED<\/code> and found a few references. A lot of them were just the word &#8220;overlapped&#8221; being used in a comment, but it wasn&#8217;t long before I found an actual <code>OVERLAPPED<\/code> structure, and here it is.<\/p>\n<pre>void Channel::ReadData(\u27e6...\u27e7)\r\n{\r\n    \u27e6...\u27e7\r\n\r\n    OVERLAPPED o{};\r\n    o.hEvent = m_readCompleteEvent;\r\n\r\n    if (ReadFile(m_file, m_buffer, m_bufferSize, &amp;actual, &amp;o)) {\r\n        \/\/ completed synchronously\r\n        \u27e6...\u27e7\r\n    } else if (GetLastError() != ERROR_IO_PENDING) {\r\n        \u27e6 handle various error conditions \u27e7\r\n    } else {\r\n        \/\/ Wait for I\/O to complete.\r\n        switch (WaitForSingleObject(o.hEvent, IO_TIMEOUT)) {\r\n        case WAIT_OBJECT_0:\r\n            \u27e6... process the results ...\u27e7\r\n            break;\r\n\r\n        case WAIT_ABANDONED:\r\n            \u27e6... deal with the error ...\u27e7\r\n            break;\r\n\r\n        case WAIT_TIMEOUT:\r\n            break;\r\n\r\n        default:\r\n            \u27e6... unexpected error ...\u27e7\r\n            break;\r\n        }\r\n    }\r\n}\r\n<\/pre>\n<p>After they issue the overlapped read, they wait up to <code>IO_TIMEOUT<\/code> (1000) milliseconds for an answer. If there is no answer after that time, they just give up and return.\u00b9<\/p>\n<p>Do you see the problem?<\/p>\n<p>They never cancel the I\/O and wait for it complete. They just abandon the I\/O and return immediately.<\/p>\n<p>When the function returns, the <code>OVERLAPPED<\/code> structure on the stack becomes available for reuse, and then when the I\/O finally does complete, the kernel writes the I\/O status to memory that has since been repurposed for something else. (It also writes the data to the original <code>m_buffer<\/code> which might also have been freed by the time the I\/O completes.)<\/p>\n<p>I&#8217;m not sure what they were thinking here. They started an I\/O and just walked away. How does the kernel know that it should stop executing the I\/O and stop writing the I\/O results back into application memory?<\/p>\n<p>It&#8217;s like booking a demolition company to knock down your house, and they say, &#8220;We&#8217;re really busy right now, but we&#8217;ve added you to our schedule. We can&#8217;t promise an exact date, but trust us, we&#8217;ll show up to knock down your house when it&#8217;s your turn.&#8221; You get tired of waiting for them and just sell the house and move somewhere else. Eventually, that demolition company will show up and knock down that house, even though it now belongs to somebody else.<\/p>\n<p>When I discussed this bug investigation with some colleagues, one of them remarked, &#8220;Wow, how lucky you were! The very first hit was the memory corruption bug you were looking for.&#8221;<\/p>\n<p>I replied, &#8220;As it turns out, it wasn&#8217;t luck.&#8221; This code base was a target-rich environment. Every single overlapped I\/O had this same bug: Nobody ever cancelled I\/O before abandoning it! If the I\/O didn&#8217;t complete within a specified timeout, the code always simply walked away from it.<\/p>\n<p>(Note that this code is really lucky that the I\/O eventually failed. If it had succeeded, they would also have corrupted whatever object was placed in the memory formerly used as the I\/O output buffer!)<\/p>\n<p>But wait, this is stack corruption. The original problem was heap corruption. Even though this is bad, it&#8217;s not the bug that caused the crash.<\/p>\n<p>I found two places that performed asynchronous I\/O into an <code>OVERLAPPED<\/code> structure on the heap. Here&#8217;s one of them:<\/p>\n<pre>class Writer\r\n{\r\n    \u27e6...\u27e7\r\n\r\n    OVERLAPPED m_overlapped;\r\n\r\n    \u27e6...\u27e7\r\n};\r\n\r\nErrorCode Writer::Write(void* buffer, unsigned size)\r\n{\r\n    \u27e6...\u27e7\r\n    \r\n    if (!WriteFile(m_target, buffer, size,\r\n                &amp;actual, &amp;m_overlapped)) {\r\n        return ErrorCode::WriteFailed;\r\n    }\r\n\r\n    if (GetLastError() != ERROR_IO_PENDING) {\r\n        return ErrorCode::WriteFailed;\r\n    }\r\n\r\n    if (WaitForSingleObject(o.hEvent, 5000)\r\n            == WAIT_TIMEOUT) {\r\n        return ErrorCode::WriteTimeout;\r\n    }\r\n}\r\n<\/pre>\n<p>This issues an overlapped write to the <code>m_target<\/code> and waits 5 seconds for the write to complete. if it doesn&#8217;t complete, then it just abandons the operation and returns a failure code.<\/p>\n<p>What&#8217;s happening is that if this write operation takes more than five seconds, the failure code propagates up the call stack, and I guess it destructs the <code>Writer<\/code>, allowing the memory for <code>m_overlapped<\/code> to be reused by the <code>IdCollection<\/code>, which then gets corrupted when the I\/O finally completes.<\/p>\n<p>Notice that the crash is in the logging code, and the log entry is probably created immediately after the <code>Writer<\/code> is freed, so it ends up reusing that memory. And then the overlapped I\/O completes and updates what it thought was an <code>OVERLAPPED<\/code> structure but which is now the map sentinel node.<\/p>\n<p>The fix is to make sure that when we decide to abandon an I\/O operation, we cancel it and wait for the I\/O to complete. (It will probably complete with <code>ERROR_<wbr \/>CANCELLED<\/code>.)<\/p>\n<p>For example, we could do this:<\/p>\n<pre>ErrorCode Writer::Write(void* buffer, unsigned size)\r\n{\r\n    \u27e6...\u27e7\r\n    \r\n    if (!WriteFile(m_target, buffer, size,\r\n                &amp;actual, &amp;m_overlapped)) {\r\n        return ErrorCode::WriteFailed;\r\n    }\r\n\r\n    if (GetLastError() != ERROR_IO_PENDING) {\r\n        return ErrorCode::WriteFailed;\r\n    }\r\n\r\n    if (WaitForSingleObject(o.hEvent, 5000)\r\n            == WAIT_TIMEOUT) {\r\n        <span style=\"border: solid 1px currentcolor; border-bottom: none;\">CancelIoEx(m_target, &amp;m_overlapped);        <\/span>\r\n        <span style=\"border: 1px currentcolor; border-style: none solid;\">GetOverlappedResult(m_target, &amp;m_overlapped,<\/span>\r\n        <span style=\"border: solid 1px currentcolor; border-top: none;\">    &amp;actual, TRUE);                         <\/span>\r\n        return ErrorCode::WriteTimeout;\r\n    }\r\n}\r\n<\/pre>\n<p>\u00b9 Yes, this code tests for <code>WAIT_<wbr \/>ABANDONED<\/code>, even though that error code will never be returned when waiting on event. The <code>WAIT_<wbr \/>ABANDONED<\/code> error code is used only by mutexes.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Who is corrupting the map?<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-110320","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Who is corrupting the map?<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110320","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=110320"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/110320\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=110320"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=110320"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=110320"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}