{"id":5467,"date":"2018-06-27T20:21:22","date_gmt":"2018-06-27T20:21:22","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/c-core-guidelines-the-rules-to-lock-free-programming\/"},"modified":"2023-06-26T11:48:52","modified_gmt":"2023-06-26T11:48:52","slug":"c-core-guidelines-the-rules-to-lock-free-programming","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/c-core-guidelines-the-rules-to-lock-free-programming\/","title":{"rendered":"C++ Core Guidelines: The Resolution of the Riddle"},"content":{"rendered":"

Today, I will solve the riddle from my last post<\/a>. Thanks to my readers, the analysis of the ABA problem is quite accurate.<\/p>\n

<\/p>\n

 <\/p>\n

\"park<\/p>\n

Only to remind you. The rule CP., 100 from the C++ core guidelines, is the starting point of the riddle.<\/p>\n<\/p>\n

CP.100: Don\u2019t use lock-free programming unless you absolutely have to. <\/a><\/h2>\n

The challenge in the rule states that the following code snippet has a bug. The bug should be due to the ABA problem. The post ABA – A is not the same as A<\/a> gives a concise introduction to the ABA problem.<\/p>\n

\n
extern<\/span> atomic<<\/span>Link*><\/span> head;        \/\/ the shared head of a linked list<\/span>\r\n\r\nLink*<\/span> nh =<\/span> new<\/span> Link(data, nullptr);    \/\/ make a link ready for insertion<\/span>\r\nLink*<\/span> h =<\/span> head.load();                 \/\/ read the shared head of the list   <\/span>\r\n\r\ndo<\/span> {\r\n    if<\/span> (h-><\/span>data <=<\/span> data) break<\/span>;        \/\/ if so, insert elsewhere           <\/span>\r\n    nh-><\/span>next =<\/span> h;                      \/\/ next element is the previous head  <\/span>\r\n} while<\/span> (!<\/span>head.compare_exchange_weak(h, nh));    \/\/ write nh to head or to h <\/span>\r\n<\/pre>\n<\/div>\n
 <\/p>\n
Thanks a lot to anonymous readers of my German blog; here is a runnable piece of code and a deep analysis of the issue.<\/p>\n
\n
#include <atomic><\/span>\r\n\r\nclass<\/span> Link<\/span> {\r\npublic:<\/span>\r\n    Link(int<\/span> d, Link*<\/span> p) :<\/span> data(d), next(p) {}\r\n    int<\/span>     data;\r\n    Link*<\/span>   next;\r\n};\r\n\r\nvoid<\/span> foo<\/span> (int<\/span> data) {\r\n    extern<\/span> std::<\/span>atomic<<\/span>Link*><\/span> head;\r\n\r\n    Link*<\/span> nh =<\/span> new<\/span> Link(data, nullptr);            \/\/ (1)<\/span>\r\n    Link*<\/span> h  =<\/span> head.load();                        \/\/ (2)<\/span>\r\n\r\n    do<\/span> {\r\n        if<\/span> (h-><\/span>data <=<\/span> data) break<\/span>;                \/\/ (3)<\/span>\r\n        nh-><\/span>next =<\/span> h;                              \/\/ (4)<\/span>\r\n    } while<\/span> (!<\/span>head.compare_exchange_weak(h, nh));  \/\/ (5)<\/span>\r\n}\r\n<\/pre>\n<\/div>\n
 <\/p>\n
First of all, what should this piece of code do? It creates a singly linked list of nodes (Link<\/span>). Each node<\/span> has a pointer and a data field. The pointer points to the next element (node<\/span>->next), and the data field stores the value: node->data. <\/span>Each new node is inserted into the singly linked list in such a way that data is ordered in ascending order.
<\/span><\/p>\n
The following steps are performed to insert a new node into the correct position in the singly linked list.<\/p>\n
    \n
  • Line 1<\/strong>: A new node is created. This is fine because the node is locally created in each thread.<\/li>\n
  • Line 2<\/strong>: The pointer to the head is read. The read operation is atomic; therefore,  considered in isolation, the operation is also acceptable. What does isolation mean? Line 2 creates with line 5 a kind of transaction. Line 2 stores the initial state of the transaction, and line 5 publishes the transaction if nothing had changed in between.<\/li>\n
  • Line 3<\/strong>: Correspondingly to the previous lines, this line 3 has no issue. Only a value comparison takes place, which may end the function if the data of the head is smaller than the new data.<\/li>\n
  • Line 4<\/strong>: nh<\/span> is local data; therefore, the assignment of nh->next<\/span> is fine. It may happen head h<\/span> was changed in the meantime and, consequently, nh->next<\/span> does not refer to the head afterward. This is only an issue if the change is committed in the next line 5.<\/li>\n
  • Line 5<\/strong>: The instruction head.compare_exchange_weak(h, nh)<\/span> compares the head<\/span> with the stored h<\/span> in line 2 and exchanges h<\/span> and nh<\/span> in an atomic step as soon as they are the same. If the head <\/span>is not equal to h<\/span>, h<\/span> is set to head.<\/span> Line 5 ends the atomic transaction and publishes the updated singly linked list.<\/li>\n<\/ul>\n
    What is the issue with these few lines of code? The entire transaction is based on the pointer comparison in line 5. The singly linked list can be broken if the pointer comparison can be fooled.<\/p>\n
    There is a time window between the loading of the head (line 2) and then checking if the current head is the old head (line 5). This means another thread may kick in and change in the meantime head<\/span>, but the first thread is not aware of it.<\/p>\n
    Let me present a buggy sequence of events.<\/p>\n
    Breaking of the Invariant<\/h3>\n
    The invariant of the following singly linked list is that data is ordered in ascending order. The blue node is the head of the list.<\/p>\n
    This is the initial structure of the list. The head has the address 0x0815<\/span><\/strong>.<\/p>\n
    \"ABAThread1\"<\/p>\n
     <\/p>\n
    Thread 1<\/h4>\n
    \"Head42\"<\/p>\n
      \n
    • Wants to add the new node with data 42.<\/li>\n
    • 42 < 47; therefore, the new node should become the new head.<\/li>\n
    • Right before the line (5), Thread 2 kicks in.<\/li>\n<\/ul>\n
      Thread 2<\/h4>\n
        \n
      • Removes the current head 47.<\/li>\n
      • Makes the node with data 60 to the new head.<\/li>\n<\/ul>\n
        \"ABAThread2<\/p>\n
          \n
        • Wants to add the new node with data 30.<\/li>\n<\/ul>\n
          \"Head30\"<\/p>\n
            \n
          • Makes 30 the new head with address 0x0815<\/strong><\/span>; this was the former address of 47 and will often happen because of memory reuse.<\/li>\n<\/ul>\n
            \"ABAThread2<\/p>\n
             <\/p>\n
             Thread 1<\/h4>\n
              \n
            • Makes the node with the data 42 to the new head; this is fine because line 5 compares the old with the new node, and they have the same address: 0x0815.<\/strong><\/span><\/li>\n<\/ul>\n
              \"ABAThread1<\/p>\n
               Now, the singly linked list is broken because the values of the nodes are not ordered in ascending order.<\/p>\n
              What’s next?<\/h2>\n
              I’m nearly done with the rules of concurrency and lock-free programming. The remaining rules are about wrong assumptions about hardware\/compiler combinations and the infamous double-checked locking pattern. Read about it in the next post.<\/p>\n
               <\/p>\n
               <\/p><\/p>\n","protected":false},"excerpt":{"rendered":"
              Today, I will solve the riddle from my last post. Thanks to my readers, the analysis of the ABA problem is quite accurate.<\/p>\n","protected":false},"author":21,"featured_media":5460,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[372],"tags":[483],"class_list":["post-5467","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-modern-c","tag-lock-free"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5467","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5467"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5467\/revisions"}],"predecessor-version":[{"id":6821,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5467\/revisions\/6821"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5460"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5467"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5467"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5467"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}