if two threads put vals into one tree at same time

private final void contendedLock() {
        boolean waiting = false;
        for (int s;;) {
            if (((s = lockState) & ~WAITER) == 0) {
                if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                    if (waiting)
                        waiter = null;
                    return;
                }
            }
            else if ((s & WAITER) == 0) {
                if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                    waiting = true;
                    waiter = Thread.currentThread();
                }
            }
            else if (waiting)
                LockSupport.park(this);
        }
    }

Thread1:CAS the lockstate to WRITER

Thread2:CAS the lockstate to (WRITER|WAITER)

Thread2:LockSupport.park(this)

Thread1:unlockRoot

private final void unlockRoot() {
        lockState = 0;
    }

then who can unpark the Thread2?

the finally part of find() method need to be done in strict conditions

finally {
                        Thread w;
                        if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                            (READER|WAITER) && (w = waiter) != null)
                            LockSupport.unpark(w);
                    }

can somebody tell me if I was thinking wrong?

CodePudding user response：

Your reasoning is based on the assumption that 2 writer-threads could potentially enter the contendedLock() method and the second writer would be parked indefinitely by itself which is, of course, impossible as the putVal is synchronized on the root node of the tree in question.

In fact, the lockState is only used to orchestrate readers vs writers through CAS and only if both reader and writer try to access the same RB-tree (i.e. they both operate on a key with identical hash).

In that case the writer-thread would park itself once it found lockState=READER (and then added the WAITER bit to the lockState through OR (s | WAITER). This value (00000110) will later be used in the finally block by the reader to unpark the writer-thread (once it clears the reading state by adding -READER, that is -4, and sees the previous value was also 00000110)