title: Is it possible to get a deadlock with ConcurrentHashMap in this circumstance?
body: <p>I'm reading the source code of <code>ConcurrentHashMap</code> in JDK8, notice that <code>TreeBin</code> uses a 'read-write' lock to prevent concurrent read and write. </p>
  
  <p>Read threads will go through TreeNodes if there's no concurrent write thread trying to modify the tree structure. When the 'find' operation is done, read thread may:</p>
  
  <p>(1)'CAS' the <code>lockState</code> and 'unpark' the waiter(writer) thread if it exists. </p>
  
  <p>Following is the 'find()' method in source code. </p>
  
  <pre class="lang-java prettyprint-override"><code>final Node&lt;K,V&gt; find(int h, Object k) {
              if (k != null) {
                  for (Node&lt;K,V&gt; e = first; e != null; ) {
                      int s; K ek;
                      if (((s = lockState) &amp; (WAITER|WRITER)) != 0) {
                          if (e.hash == h &amp;&amp;
                              ((ek = e.key) == k || (ek != null &amp;&amp; k.equals(ek))))
                              return e;
                          e = e.next;
                      }
                      else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                   s + READER)) {
                          TreeNode&lt;K,V&gt; r, p;
                          try {
                              p = ((r = root) == null ? null :
                                   r.findTreeNode(h, k, null));
                          } finally {
                              Thread w;
                              // (1)if no more readers, try to unpark the waiter if it exists
                              if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                                  (READER|WAITER) &amp;&amp; (w = waiter) != null)
                                  LockSupport.unpark(w);
                          }
                          return p;
                      }
                  }
              }
              return null;
          }
  </code></pre>
  
  <p>on the other hand, writer thread may:</p>
  
  <ul>
  <li><p>(2) adding the <code>WAITER</code> state to <code>lockState</code> with 'CAS' operation.</p></li>
  <li><p>(3) set itself to <code>waiter</code> variable.</p></li>
  <li><p>(4) 'park' itself.</p></li>
  </ul>
  
  <p>here's the writer's code:</p>
  
  <pre class="lang-java prettyprint-override"><code>        private final void contendedLock() {
              boolean waiting = false;
              for (int s;;) {
                  if (((s = lockState) &amp; ~WAITER) == 0) {
                      if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                          if (waiting)
                              waiter = null;
                          return;
                      }
                  }
                  else if ((s &amp; WAITER) == 0) {
                      if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                          waiting = true;
                          waiter = Thread.currentThread();
                      }
                  }
                  else if (waiting)
                      LockSupport.park(this);
              }
          }
  </code></pre>
  
  <p>HERE IS MY CONFUSION: </p>
  
  <p>If the four operation above run in this order (2) (1) (3) (4), the operation (1) won't unpark anything because 'waiter' was null at that moment. </p>
  
  <p>Then the waiter will park forever without anyone who can unpark it.</p>
  
  <p>The subsequent writes will be all blocked on the intrinsic lock held by the 'parked' thread.</p>
  
  <p>IS THIS A CHANCE OF DEADLOCK ?</p>
  
  <p>I'm really confused about this. I think perhaps I've missed something in the source code. Need your help if you are familiar with it.</p>