title: Can we do something atomically with 2 or more lock-free containers without locking both?
body: <p>I'm looking for <a href="https://en.wikipedia.org/wiki/Software_transactional_memory#Composable_operations" rel="nofollow"><strong>Composable operations</strong></a> - it fairly easily to do using transactional memory. (Thanks to Ami Tavory) </p>
  
  <p>And it easily to do using locks (mutex/spinlock) - but it can lead to deadlocks - so lock-based algorithms composable only with manual tuning.</p>
  
  <p>Lock-free algorithms do not have the problem of deadlocks, but it is not composable. Required to designed 2 or more containers as a single composed lock-free data structure.</p>
  
  <p>Is there any approach, helper-implementation or some lock-free algorithms - to <strong>atomically</strong> work with several lock-free containers to maintain consistency?</p>
  
  <ul>
  <li>To check if if an item is in both containers at once</li>
  <li>To move element from one container to another <strong>atomically</strong></li>
  </ul>
  
  <p>...</p>
  
  <p>Or can RCU or hazard-pointers help to do this?</p>
  
  <p>As known, we can use lock-free containers, which is difficult in its implementations, for example from Concurrent Data Structures (CDS) library: <a href="http://libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html" rel="nofollow">http://libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html</a></p>
  
  <p>And for example we can use <strong>lock-free</strong> ordered-map like <a href="http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_skip_list_map_3_01cds_1_1urcu_1_1gc_3_01_r_c_u_01_4_00_01_key_00_01_t_00_01_traits_01_4.html" rel="nofollow">SkipList CDS-lib</a></p>
  
  <p>But even simple lock-free algorithm is not lock-free for any cases:</p>
  
  <ol>
  <li><strong>Iterators</strong> <a href="http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_skip_list_map_3_01cds_1_1urcu_1_1gc_3_01_r_c_u_01_4_00_01_key_00_01_t_00_01_traits_01_4.html#details" rel="nofollow">documentation-link</a></li>
  </ol>
  
  <blockquote>
    <p>You may iterate over skip-list set items <strong>only under RCU lock</strong>. Only in
    this case the iterator is thread-safe since while RCU is locked any
    set's item cannot be reclaimed. The requirement of RCU lock during
    iterating means that deletion of the elements (i.e. erase) is not
    possible.</p>
  </blockquote>
  
  <ol start="2">
  <li><strong><code>::contains(K const &amp;key)</code></strong> - <a href="http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_skip_list_map_3_01cds_1_1urcu_1_1gc_3_01_r_c_u_01_4_00_01_key_00_01_t_00_01_traits_01_4.html#a80c988c8df76dae5e99390c1600dcd99" rel="nofollow">documentation-link</a></li>
  </ol>
  
  <blockquote>
    <p>The function applies RCU lock internally.</p>
  </blockquote>
  
  <ol start="3">
  <li>To <strong><code>::get(K const &amp;key)</code></strong> and update element which we got, we <strong>should use lock</strong>: <a href="http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_skip_list_map_3_01cds_1_1urcu_1_1gc_3_01_r_c_u_01_4_00_01_key_00_01_t_00_01_traits_01_4.html#a4f720be58b42f25432176750a6534029" rel="nofollow">documentation-link</a></li>
  </ol>
  
  <p>Example:</p>
  
  <pre><code>typedef cds::container::SkipListMap&lt; cds::urcu::gc&lt; cds::urcu::general_buffered&lt;&gt; &gt;, int, foo, my_traits &gt; skip_list;
  skip_list theList;
  // ...
  typename skip_list::raw_ptr pVal;
  {
      // Lock RCU
      skip_list::rcu_lock lock;
      pVal = theList.get( 5 );
      if ( pVal ) {
          // Deal with pVal
          //...
      }
  }
  // You can manually release pVal after RCU-locked section
  pVal.release();
  </code></pre>
  
  <p>But if we use 2 lock-free containers instead of 1, and if we use only methods wich is always lock-free, or one of it lock-free, then can we do it without locking both containers?</p>
  
  <pre><code>typedef cds::urcu::gc&lt; cds::urcu::general_buffered&lt;&gt; &gt;  rcu_gpb;
  cds::container::SkipListMap&lt; rcu_gpb, int, int &gt; map_1;
  cds::container::SkipListMap&lt; rcu_gpb, int, int &gt; map_2;
  </code></pre>
  
  <p>Can we atomically move 1 element from <code>map_1</code> to <code>map_2</code> <strong>without locking both containers</strong> - i.e. <a href="http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_skip_list_map_3_01cds_1_1urcu_1_1gc_3_01_r_c_u_01_4_00_01_key_00_01_t_00_01_traits_01_4.html#a33830c59e1a27dc4f04c106ba7f148d6" rel="nofollow"><code>map_1.erase(K const &amp;key)</code></a> and <a href="http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_skip_list_map_3_01cds_1_1urcu_1_1gc_3_01_r_c_u_01_4_00_01_key_00_01_t_00_01_traits_01_4.html#a3f9036ea2f2b5cf943bac33fc367afda" rel="nofollow"><code>map_2.insert(K const &amp;key, V const &amp;val)</code></a> if we want to maintain atomicity and consistency: </p>
  
  <ul>
  <li><p>that other threads do not see that there is no element in the first container, and he still had not appear in the second</p></li>
  <li><p>that other threads do not see that there is element in the first container, and the same element already in the second</p></li>
  </ul>
  
  <p>Can we do something atomically with 2 or more lock-free containers without locking both - if we want to maintain atomicity and consistency?</p>
  
  <p><strong>ANSWER:</strong> We can't do any atomically operations with two or more lock-free containers at once without locks by using simply its usual functions. </p>
  
  <p>Only if we do 1 simply operation provided by lock-free algorithm in containers-API then for 2 lock-free containers it is enough 1 lock, exclude 3 cases described above when even in lock-free containers uses locks.</p>
  
  <p>Also "but maybe something with a bunch of extra overhead" if you made complicated custom improvements of lock-free algorithms then you can provide some composable, for example, as "the two queues know about each other, and the code looking at them is carefully designed" as Peter Cordes noted. </p>