1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /*

    26  * This file is available under and governed by the GNU General Public

    27  * License version 2 only, as published by the Free Software Foundation.

    28  * However, the following notice accompanied the original version of this

    29  * file:

    30  *

    31  * Written by Doug Lea with assistance from members of JCP JSR-166

    32  * Expert Group and released to the public domain, as explained at

    33  * http://creativecommons.org/publicdomain/zero/1.0/

    34  */

    35 

    36 package java.util.concurrent.locks;

    37 

    38 import java.util.concurrent.TimeUnit;

    39 import java.util.concurrent.locks.Lock;

    40 import java.util.concurrent.locks.Condition;

    41 import java.util.concurrent.locks.ReadWriteLock;

    42 import java.util.concurrent.locks.LockSupport;

    43 

    44 /**

    45  * A capability-based lock with three modes for controlling read/write

    46  * access.  The state of a StampedLock consists of a version and mode.

    47  * Lock acquisition methods return a stamp that represents and

    48  * controls access with respect to a lock state; "try" versions of

    49  * these methods may instead return the special value zero to

    50  * represent failure to acquire access. Lock release and conversion

    51  * methods require stamps as arguments, and fail if they do not match

    52  * the state of the lock. The three modes are:

    53  *

    54  * <ul>

    55  *

    56  *  <li><b>Writing.</b> Method {@link #writeLock} possibly blocks

    57  *   waiting for exclusive access, returning a stamp that can be used

    58  *   in method {@link #unlockWrite} to release the lock. Untimed and

    59  *   timed versions of {@code tryWriteLock} are also provided. When

    60  *   the lock is held in write mode, no read locks may be obtained,

    61  *   and all optimistic read validations will fail.  </li>

    62  *

    63  *  <li><b>Reading.</b> Method {@link #readLock} possibly blocks

    64  *   waiting for non-exclusive access, returning a stamp that can be

    65  *   used in method {@link #unlockRead} to release the lock. Untimed

    66  *   and timed versions of {@code tryReadLock} are also provided. </li>

    67  *

    68  *  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}

    69  *   returns a non-zero stamp only if the lock is not currently held

    70  *   in write mode. Method {@link #validate} returns true if the lock

    71  *   has not been acquired in write mode since obtaining a given

    72  *   stamp.  This mode can be thought of as an extremely weak version

    73  *   of a read-lock, that can be broken by a writer at any time.  The

    74  *   use of optimistic mode for short read-only code segments often

    75  *   reduces contention and improves throughput.  However, its use is

    76  *   inherently fragile.  Optimistic read sections should only read

    77  *   fields and hold them in local variables for later use after

    78  *   validation. Fields read while in optimistic mode may be wildly

    79  *   inconsistent, so usage applies only when you are familiar enough

    80  *   with data representations to check consistency and/or repeatedly

    81  *   invoke method {@code validate()}.  For example, such steps are

    82  *   typically required when first reading an object or array

    83  *   reference, and then accessing one of its fields, elements or

    84  *   methods. </li>

    85  *

    86  * </ul>

    87  *

    88  * <p>This class also supports methods that conditionally provide

    89  * conversions across the three modes. For example, method {@link

    90  * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning

    91  * a valid write stamp if (1) already in writing mode (2) in reading

    92  * mode and there are no other readers or (3) in optimistic mode and

    93  * the lock is available. The forms of these methods are designed to

    94  * help reduce some of the code bloat that otherwise occurs in

    95  * retry-based designs.

    96  *

    97  * <p>StampedLocks are designed for use as internal utilities in the

    98  * development of thread-safe components. Their use relies on

    99  * knowledge of the internal properties of the data, objects, and

   100  * methods they are protecting.  They are not reentrant, so locked

   101  * bodies should not call other unknown methods that may try to

   102  * re-acquire locks (although you may pass a stamp to other methods

   103  * that can use or convert it).  The use of read lock modes relies on

   104  * the associated code sections being side-effect-free.  Unvalidated

   105  * optimistic read sections cannot call methods that are not known to

   106  * tolerate potential inconsistencies.  Stamps use finite

   107  * representations, and are not cryptographically secure (i.e., a

   108  * valid stamp may be guessable). Stamp values may recycle after (no

   109  * sooner than) one year of continuous operation. A stamp held without

   110  * use or validation for longer than this period may fail to validate

   111  * correctly.  StampedLocks are serializable, but always deserialize

   112  * into initial unlocked state, so they are not useful for remote

   113  * locking.

   114  *

   115  * <p>The scheduling policy of StampedLock does not consistently

   116  * prefer readers over writers or vice versa.  All "try" methods are

   117  * best-effort and do not necessarily conform to any scheduling or

   118  * fairness policy. A zero return from any "try" method for acquiring

   119  * or converting locks does not carry any information about the state

   120  * of the lock; a subsequent invocation may succeed.

   121  *

   122  * <p>Because it supports coordinated usage across multiple lock

   123  * modes, this class does not directly implement the {@link Lock} or

   124  * {@link ReadWriteLock} interfaces. However, a StampedLock may be

   125  * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link

   126  * #asReadWriteLock()} in applications requiring only the associated

   127  * set of functionality.

   128  *

   129  * <p><b>Sample Usage.</b> The following illustrates some usage idioms

   130  * in a class that maintains simple two-dimensional points. The sample

   131  * code illustrates some try/catch conventions even though they are

   132  * not strictly needed here because no exceptions can occur in their

   133  * bodies.<br>

   134  *

   135  *  <pre>{@code

   136  * class Point {

   137  *   private double x, y;

   138  *   private final StampedLock sl = new StampedLock();

   139  *

   140  *   void move(double deltaX, double deltaY) { // an exclusively locked method

   141  *     long stamp = sl.writeLock();

   142  *     try {

   143  *       x += deltaX;

   144  *       y += deltaY;

   145  *     } finally {

   146  *       sl.unlockWrite(stamp);

   147  *     }

   148  *   }

   149  *

   150  *   double distanceFromOrigin() { // A read-only method

   151  *     long stamp = sl.tryOptimisticRead();

   152  *     double currentX = x, currentY = y;

   153  *     if (!sl.validate(stamp)) {

   154  *        stamp = sl.readLock();

   155  *        try {

   156  *          currentX = x;

   157  *          currentY = y;

   158  *        } finally {

   159  *           sl.unlockRead(stamp);

   160  *        }

   161  *     }

   162  *     return Math.sqrt(currentX * currentX + currentY * currentY);

   163  *   }

   164  *

   165  *   void moveIfAtOrigin(double newX, double newY) { // upgrade

   166  *     // Could instead start with optimistic, not read mode

   167  *     long stamp = sl.readLock();

   168  *     try {

   169  *       while (x == 0.0 && y == 0.0) {

   170  *         long ws = sl.tryConvertToWriteLock(stamp);

   171  *         if (ws != 0L) {

   172  *           stamp = ws;

   173  *           x = newX;

   174  *           y = newY;

   175  *           break;

   176  *         }

   177  *         else {

   178  *           sl.unlockRead(stamp);

   179  *           stamp = sl.writeLock();

   180  *         }

   181  *       }

   182  *     } finally {

   183  *       sl.unlock(stamp);

   184  *     }

   185  *   }

   186  * }}</pre>

   187  *

   188  * @since 1.8

   189  * @author Doug Lea

   190  */

   191 public class StampedLock implements java.io.Serializable {

   192     /*

   193      * Algorithmic notes:

   194      *

   195      * The design employs elements of Sequence locks

   196      * (as used in linux kernels; see Lameter's

   197      * http://www.lameter.com/gelato2005.pdf

   198      * and elsewhere; see

   199      * Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)

   200      * and Ordered RW locks (see Shirako et al

   201      * http://dl.acm.org/citation.cfm?id=2312015)

   202      *

   203      * Conceptually, the primary state of the lock includes a sequence

   204      * number that is odd when write-locked and even otherwise.

   205      * However, this is offset by a reader count that is non-zero when

   206      * read-locked.  The read count is ignored when validating

   207      * "optimistic" seqlock-reader-style stamps.  Because we must use

   208      * a small finite number of bits (currently 7) for readers, a

   209      * supplementary reader overflow word is used when the number of

   210      * readers exceeds the count field. We do this by treating the max

   211      * reader count value (RBITS) as a spinlock protecting overflow

   212      * updates.

   213      *

   214      * Waiters use a modified form of CLH lock used in

   215      * AbstractQueuedSynchronizer (see its internal documentation for

   216      * a fuller account), where each node is tagged (field mode) as

   217      * either a reader or writer. Sets of waiting readers are grouped

   218      * (linked) under a common node (field cowait) so act as a single

   219      * node with respect to most CLH mechanics.  By virtue of the

   220      * queue structure, wait nodes need not actually carry sequence

   221      * numbers; we know each is greater than its predecessor.  This

   222      * simplifies the scheduling policy to a mainly-FIFO scheme that

   223      * incorporates elements of Phase-Fair locks (see Brandenburg &

   224      * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In

   225      * particular, we use the phase-fair anti-barging rule: If an

   226      * incoming reader arrives while read lock is held but there is a

   227      * queued writer, this incoming reader is queued.  (This rule is

   228      * responsible for some of the complexity of method acquireRead,

   229      * but without it, the lock becomes highly unfair.) Method release

   230      * does not (and sometimes cannot) itself wake up cowaiters. This

   231      * is done by the primary thread, but helped by any other threads

   232      * with nothing better to do in methods acquireRead and

   233      * acquireWrite.

   234      *

   235      * These rules apply to threads actually queued. All tryLock forms

   236      * opportunistically try to acquire locks regardless of preference

   237      * rules, and so may "barge" their way in.  Randomized spinning is

   238      * used in the acquire methods to reduce (increasingly expensive)

   239      * context switching while also avoiding sustained memory

   240      * thrashing among many threads.  We limit spins to the head of

   241      * queue. A thread spin-waits up to SPINS times (where each

   242      * iteration decreases spin count with 50% probability) before

   243      * blocking. If, upon wakening it fails to obtain lock, and is

   244      * still (or becomes) the first waiting thread (which indicates

   245      * that some other thread barged and obtained lock), it escalates

   246      * spins (up to MAX_HEAD_SPINS) to reduce the likelihood of

   247      * continually losing to barging threads.

   248      *

   249      * Nearly all of these mechanics are carried out in methods

   250      * acquireWrite and acquireRead, that, as typical of such code,

   251      * sprawl out because actions and retries rely on consistent sets

   252      * of locally cached reads.

   253      *

   254      * As noted in Boehm's paper (above), sequence validation (mainly

   255      * method validate()) requires stricter ordering rules than apply

   256      * to normal volatile reads (of "state").  To force orderings of

   257      * reads before a validation and the validation itself in those

   258      * cases where this is not already forced, we use

   259      * Unsafe.loadFence.

   260      *

   261      * The memory layout keeps lock state and queue pointers together

   262      * (normally on the same cache line). This usually works well for

   263      * read-mostly loads. In most other cases, the natural tendency of

   264      * adaptive-spin CLH locks to reduce memory contention lessens

   265      * motivation to further spread out contended locations, but might

   266      * be subject to future improvements.

   267      */

   268 

   269     private static final long serialVersionUID = -6001602636862214147L;

   270 

   271     /** Number of processors, for spin control */

   272     private static final int NCPU = Runtime.getRuntime().availableProcessors();

   273 

   274     /** Maximum number of retries before enqueuing on acquisition */

   275     private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;

   276 

   277     /** Maximum number of retries before blocking at head on acquisition */

   278     private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;

   279 

   280     /** Maximum number of retries before re-blocking */

   281     private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;

   282 

   283     /** The period for yielding when waiting for overflow spinlock */

   284     private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1

   285 

   286     /** The number of bits to use for reader count before overflowing */

   287     private static final int LG_READERS = 7;

   288 

   289     // Values for lock state and stamp operations

   290     private static final long RUNIT = 1L;

   291     private static final long WBIT  = 1L << LG_READERS;

   292     private static final long RBITS = WBIT - 1L;

   293     private static final long RFULL = RBITS - 1L;

   294     private static final long ABITS = RBITS | WBIT;

   295     private static final long SBITS = ~RBITS; // note overlap with ABITS

   296 

   297     // Initial value for lock state; avoid failure value zero

   298     private static final long ORIGIN = WBIT << 1;

   299 

   300     // Special value from cancelled acquire methods so caller can throw IE

   301     private static final long INTERRUPTED = 1L;

   302 

   303     // Values for node status; order matters

   304     private static final int WAITING   = -1;

   305     private static final int CANCELLED =  1;

   306 

   307     // Modes for nodes (int not boolean to allow arithmetic)

   308     private static final int RMODE = 0;

   309     private static final int WMODE = 1;

   310 

   311     /** Wait nodes */

   312     static final class WNode {

   313         volatile WNode prev;

   314         volatile WNode next;

   315         volatile WNode cowait;    // list of linked readers

   316         volatile Thread thread;   // non-null while possibly parked

   317         volatile int status;      // 0, WAITING, or CANCELLED

   318         final int mode;           // RMODE or WMODE

   319         WNode(int m, WNode p) { mode = m; prev = p; }

   320     }

   321 

   322     /** Head of CLH queue */

   323     private transient volatile WNode whead;

   324     /** Tail (last) of CLH queue */

   325     private transient volatile WNode wtail;

   326 

   327     // views

   328     transient ReadLockView readLockView;

   329     transient WriteLockView writeLockView;

   330     transient ReadWriteLockView readWriteLockView;

   331 

   332     /** Lock sequence/state */

   333     private transient volatile long state;

   334     /** extra reader count when state read count saturated */

   335     private transient int readerOverflow;

   336 

   337     /**

   338      * Creates a new lock, initially in unlocked state.

   339      */

   340     public StampedLock() {

   341         state = ORIGIN;

   342     }

   343 

   344     /**

   345      * Exclusively acquires the lock, blocking if necessary

   346      * until available.

   347      *

   348      * @return a stamp that can be used to unlock or convert mode

   349      */

   350     public long writeLock() {

   351         long s, next;  // bypass acquireWrite in fully unlocked case only

   352         return ((((s = state) & ABITS) == 0L &&

   353                  U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?

   354                 next : acquireWrite(false, 0L));

   355     }

   356 

   357     /**

   358      * Exclusively acquires the lock if it is immediately available.

   359      *

   360      * @return a stamp that can be used to unlock or convert mode,

   361      * or zero if the lock is not available

   362      */

   363     public long tryWriteLock() {

   364         long s, next;

   365         return ((((s = state) & ABITS) == 0L &&

   366                  U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?

   367                 next : 0L);

   368     }

   369 

   370     /**

   371      * Exclusively acquires the lock if it is available within the

   372      * given time and the current thread has not been interrupted.

   373      * Behavior under timeout and interruption matches that specified

   374      * for method {@link Lock#tryLock(long,TimeUnit)}.

   375      *

   376      * @param time the maximum time to wait for the lock

   377      * @param unit the time unit of the {@code time} argument

   378      * @return a stamp that can be used to unlock or convert mode,

   379      * or zero if the lock is not available

   380      * @throws InterruptedException if the current thread is interrupted

   381      * before acquiring the lock

   382      */

   383     public long tryWriteLock(long time, TimeUnit unit)

   384         throws InterruptedException {

   385         long nanos = unit.toNanos(time);

   386         if (!Thread.interrupted()) {

   387             long next, deadline;

   388             if ((next = tryWriteLock()) != 0L)

   389                 return next;

   390             if (nanos <= 0L)

   391                 return 0L;

   392             if ((deadline = System.nanoTime() + nanos) == 0L)

   393                 deadline = 1L;

   394             if ((next = acquireWrite(true, deadline)) != INTERRUPTED)

   395                 return next;

   396         }

   397         throw new InterruptedException();

   398     }

   399 

   400     /**

   401      * Exclusively acquires the lock, blocking if necessary

   402      * until available or the current thread is interrupted.

   403      * Behavior under interruption matches that specified

   404      * for method {@link Lock#lockInterruptibly()}.

   405      *

   406      * @return a stamp that can be used to unlock or convert mode

   407      * @throws InterruptedException if the current thread is interrupted

   408      * before acquiring the lock

   409      */

   410     public long writeLockInterruptibly() throws InterruptedException {

   411         long next;

   412         if (!Thread.interrupted() &&

   413             (next = acquireWrite(true, 0L)) != INTERRUPTED)

   414             return next;

   415         throw new InterruptedException();

   416     }

   417 

   418     /**

   419      * Non-exclusively acquires the lock, blocking if necessary

   420      * until available.

   421      *

   422      * @return a stamp that can be used to unlock or convert mode

   423      */

   424     public long readLock() {

   425         long s = state, next;  // bypass acquireRead on common uncontended case

   426         return ((whead == wtail && (s & ABITS) < RFULL &&

   427                  U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?

   428                 next : acquireRead(false, 0L));

   429     }

   430 

   431     /**

   432      * Non-exclusively acquires the lock if it is immediately available.

   433      *

   434      * @return a stamp that can be used to unlock or convert mode,

   435      * or zero if the lock is not available

   436      */

   437     public long tryReadLock() {

   438         for (;;) {

   439             long s, m, next;

   440             if ((m = (s = state) & ABITS) == WBIT)

   441                 return 0L;

   442             else if (m < RFULL) {

   443                 if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))

   444                     return next;

   445             }

   446             else if ((next = tryIncReaderOverflow(s)) != 0L)

   447                 return next;

   448         }

   449     }

   450 

   451     /**

   452      * Non-exclusively acquires the lock if it is available within the

   453      * given time and the current thread has not been interrupted.

   454      * Behavior under timeout and interruption matches that specified

   455      * for method {@link Lock#tryLock(long,TimeUnit)}.

   456      *

   457      * @param time the maximum time to wait for the lock

   458      * @param unit the time unit of the {@code time} argument

   459      * @return a stamp that can be used to unlock or convert mode,

   460      * or zero if the lock is not available

   461      * @throws InterruptedException if the current thread is interrupted

   462      * before acquiring the lock

   463      */

   464     public long tryReadLock(long time, TimeUnit unit)

   465         throws InterruptedException {

   466         long s, m, next, deadline;

   467         long nanos = unit.toNanos(time);

   468         if (!Thread.interrupted()) {

   469             if ((m = (s = state) & ABITS) != WBIT) {

   470                 if (m < RFULL) {

   471                     if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))

   472                         return next;

   473                 }

   474                 else if ((next = tryIncReaderOverflow(s)) != 0L)

   475                     return next;

   476             }

   477             if (nanos <= 0L)

   478                 return 0L;

   479             if ((deadline = System.nanoTime() + nanos) == 0L)

   480                 deadline = 1L;

   481             if ((next = acquireRead(true, deadline)) != INTERRUPTED)

   482                 return next;

   483         }

   484         throw new InterruptedException();

   485     }

   486 

   487     /**

   488      * Non-exclusively acquires the lock, blocking if necessary

   489      * until available or the current thread is interrupted.

   490      * Behavior under interruption matches that specified

   491      * for method {@link Lock#lockInterruptibly()}.

   492      *

   493      * @return a stamp that can be used to unlock or convert mode

   494      * @throws InterruptedException if the current thread is interrupted

   495      * before acquiring the lock

   496      */

   497     public long readLockInterruptibly() throws InterruptedException {

   498         long next;

   499         if (!Thread.interrupted() &&

   500             (next = acquireRead(true, 0L)) != INTERRUPTED)

   501             return next;

   502         throw new InterruptedException();

   503     }

   504 

   505     /**

   506      * Returns a stamp that can later be validated, or zero

   507      * if exclusively locked.

   508      *

   509      * @return a stamp, or zero if exclusively locked

   510      */

   511     public long tryOptimisticRead() {

   512         long s;

   513         return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;

   514     }

   515 

   516     /**

   517      * Returns true if the lock has not been exclusively acquired

   518      * since issuance of the given stamp. Always returns false if the

   519      * stamp is zero. Always returns true if the stamp represents a

   520      * currently held lock. Invoking this method with a value not

   521      * obtained from {@link #tryOptimisticRead} or a locking method

   522      * for this lock has no defined effect or result.

   523      *

   524      * @param stamp a stamp

   525      * @return {@code true} if the lock has not been exclusively acquired

   526      * since issuance of the given stamp; else false

   527      */

   528     public boolean validate(long stamp) {

   529         U.loadFence();

   530         return (stamp & SBITS) == (state & SBITS);

   531     }

   532 

   533     /**

   534      * If the lock state matches the given stamp, releases the

   535      * exclusive lock.

   536      *

   537      * @param stamp a stamp returned by a write-lock operation

   538      * @throws IllegalMonitorStateException if the stamp does

   539      * not match the current state of this lock

   540      */

   541     public void unlockWrite(long stamp) {

   542         WNode h;

   543         if (state != stamp || (stamp & WBIT) == 0L)

   544             throw new IllegalMonitorStateException();

   545         state = (stamp += WBIT) == 0L ? ORIGIN : stamp;

   546         if ((h = whead) != null && h.status != 0)

   547             release(h);

   548     }

   549 

   550     /**

   551      * If the lock state matches the given stamp, releases the

   552      * non-exclusive lock.

   553      *

   554      * @param stamp a stamp returned by a read-lock operation

   555      * @throws IllegalMonitorStateException if the stamp does

   556      * not match the current state of this lock

   557      */

   558     public void unlockRead(long stamp) {

   559         long s, m; WNode h;

   560         for (;;) {

   561             if (((s = state) & SBITS) != (stamp & SBITS) ||

   562                 (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)

   563                 throw new IllegalMonitorStateException();

   564             if (m < RFULL) {

   565                 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {

   566                     if (m == RUNIT && (h = whead) != null && h.status != 0)

   567                         release(h);

   568                     break;

   569                 }

   570             }

   571             else if (tryDecReaderOverflow(s) != 0L)

   572                 break;

   573         }

   574     }

   575 

   576     /**

   577      * If the lock state matches the given stamp, releases the

   578      * corresponding mode of the lock.

   579      *

   580      * @param stamp a stamp returned by a lock operation

   581      * @throws IllegalMonitorStateException if the stamp does

   582      * not match the current state of this lock

   583      */

   584     public void unlock(long stamp) {

   585         long a = stamp & ABITS, m, s; WNode h;

   586         while (((s = state) & SBITS) == (stamp & SBITS)) {

   587             if ((m = s & ABITS) == 0L)

   588                 break;

   589             else if (m == WBIT) {

   590                 if (a != m)

   591                     break;

   592                 state = (s += WBIT) == 0L ? ORIGIN : s;

   593                 if ((h = whead) != null && h.status != 0)

   594                     release(h);

   595                 return;

   596             }

   597             else if (a == 0L || a >= WBIT)

   598                 break;

   599             else if (m < RFULL) {

   600                 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {

   601                     if (m == RUNIT && (h = whead) != null && h.status != 0)

   602                         release(h);

   603                     return;

   604                 }

   605             }

   606             else if (tryDecReaderOverflow(s) != 0L)

   607                 return;

   608         }

   609         throw new IllegalMonitorStateException();

   610     }

   611 

   612     /**

   613      * If the lock state matches the given stamp, performs one of

   614      * the following actions. If the stamp represents holding a write

   615      * lock, returns it.  Or, if a read lock, if the write lock is

   616      * available, releases the read lock and returns a write stamp.

   617      * Or, if an optimistic read, returns a write stamp only if

   618      * immediately available. This method returns zero in all other

   619      * cases.

   620      *

   621      * @param stamp a stamp

   622      * @return a valid write stamp, or zero on failure

   623      */

   624     public long tryConvertToWriteLock(long stamp) {

   625         long a = stamp & ABITS, m, s, next;

   626         while (((s = state) & SBITS) == (stamp & SBITS)) {

   627             if ((m = s & ABITS) == 0L) {

   628                 if (a != 0L)

   629                     break;

   630                 if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))

   631                     return next;

   632             }

   633             else if (m == WBIT) {

   634                 if (a != m)

   635                     break;

   636                 return stamp;

   637             }

   638             else if (m == RUNIT && a != 0L) {

   639                 if (U.compareAndSwapLong(this, STATE, s,

   640                                          next = s - RUNIT + WBIT))

   641                     return next;

   642             }

   643             else

   644                 break;

   645         }

   646         return 0L;

   647     }

   648 

   649     /**

   650      * If the lock state matches the given stamp, performs one of

   651      * the following actions. If the stamp represents holding a write

   652      * lock, releases it and obtains a read lock.  Or, if a read lock,

   653      * returns it. Or, if an optimistic read, acquires a read lock and

   654      * returns a read stamp only if immediately available. This method

   655      * returns zero in all other cases.

   656      *

   657      * @param stamp a stamp

   658      * @return a valid read stamp, or zero on failure

   659      */

   660     public long tryConvertToReadLock(long stamp) {

   661         long a = stamp & ABITS, m, s, next; WNode h;

   662         while (((s = state) & SBITS) == (stamp & SBITS)) {

   663             if ((m = s & ABITS) == 0L) {

   664                 if (a != 0L)

   665                     break;

   666                 else if (m < RFULL) {

   667                     if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))

   668                         return next;

   669                 }

   670                 else if ((next = tryIncReaderOverflow(s)) != 0L)

   671                     return next;

   672             }

   673             else if (m == WBIT) {

   674                 if (a != m)

   675                     break;

   676                 state = next = s + (WBIT + RUNIT);

   677                 if ((h = whead) != null && h.status != 0)

   678                     release(h);

   679                 return next;

   680             }

   681             else if (a != 0L && a < WBIT)

   682                 return stamp;

   683             else

   684                 break;

   685         }

   686         return 0L;

   687     }

   688 

   689     /**

   690      * If the lock state matches the given stamp then, if the stamp

   691      * represents holding a lock, releases it and returns an

   692      * observation stamp.  Or, if an optimistic read, returns it if

   693      * validated. This method returns zero in all other cases, and so

   694      * may be useful as a form of "tryUnlock".

   695      *

   696      * @param stamp a stamp

   697      * @return a valid optimistic read stamp, or zero on failure

   698      */

   699     public long tryConvertToOptimisticRead(long stamp) {

   700         long a = stamp & ABITS, m, s, next; WNode h;

   701         U.loadFence();

   702         for (;;) {

   703             if (((s = state) & SBITS) != (stamp & SBITS))

   704                 break;

   705             if ((m = s & ABITS) == 0L) {

   706                 if (a != 0L)

   707                     break;

   708                 return s;

   709             }

   710             else if (m == WBIT) {

   711                 if (a != m)

   712                     break;

   713                 state = next = (s += WBIT) == 0L ? ORIGIN : s;

   714                 if ((h = whead) != null && h.status != 0)

   715                     release(h);

   716                 return next;

   717             }

   718             else if (a == 0L || a >= WBIT)

   719                 break;

   720             else if (m < RFULL) {

   721                 if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {

   722                     if (m == RUNIT && (h = whead) != null && h.status != 0)

   723                         release(h);

   724                     return next & SBITS;

   725                 }

   726             }

   727             else if ((next = tryDecReaderOverflow(s)) != 0L)

   728                 return next & SBITS;

   729         }

   730         return 0L;

   731     }

   732 

   733     /**

   734      * Releases the write lock if it is held, without requiring a

   735      * stamp value. This method may be useful for recovery after

   736      * errors.

   737      *

   738      * @return {@code true} if the lock was held, else false

   739      */

   740     public boolean tryUnlockWrite() {

   741         long s; WNode h;

   742         if (((s = state) & WBIT) != 0L) {

   743             state = (s += WBIT) == 0L ? ORIGIN : s;

   744             if ((h = whead) != null && h.status != 0)

   745                 release(h);

   746             return true;

   747         }

   748         return false;

   749     }

   750 

   751     /**

   752      * Releases one hold of the read lock if it is held, without

   753      * requiring a stamp value. This method may be useful for recovery

   754      * after errors.

   755      *

   756      * @return {@code true} if the read lock was held, else false

   757      */

   758     public boolean tryUnlockRead() {

   759         long s, m; WNode h;

   760         while ((m = (s = state) & ABITS) != 0L && m < WBIT) {

   761             if (m < RFULL) {

   762                 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {

   763                     if (m == RUNIT && (h = whead) != null && h.status != 0)

   764                         release(h);

   765                     return true;

   766                 }

   767             }

   768             else if (tryDecReaderOverflow(s) != 0L)

   769                 return true;

   770         }

   771         return false;

   772     }

   773 

   774     // status monitoring methods

   775 

   776     /**

   777      * Returns combined state-held and overflow read count for given

   778      * state s.

   779      */

   780     private int getReadLockCount(long s) {

   781         long readers;

   782         if ((readers = s & RBITS) >= RFULL)

   783             readers = RFULL + readerOverflow;

   784         return (int) readers;

   785     }

   786 

   787     /**

   788      * Returns {@code true} if the lock is currently held exclusively.

   789      *

   790      * @return {@code true} if the lock is currently held exclusively

   791      */

   792     public boolean isWriteLocked() {

   793         return (state & WBIT) != 0L;

   794     }

   795 

   796     /**

   797      * Returns {@code true} if the lock is currently held non-exclusively.

   798      *

   799      * @return {@code true} if the lock is currently held non-exclusively

   800      */

   801     public boolean isReadLocked() {

   802         return (state & RBITS) != 0L;

   803     }

   804 

   805     /**

   806      * Queries the number of read locks held for this lock. This

   807      * method is designed for use in monitoring system state, not for

   808      * synchronization control.

   809      * @return the number of read locks held

   810      */

   811     public int getReadLockCount() {

   812         return getReadLockCount(state);

   813     }

   814 

   815     /**

   816      * Returns a string identifying this lock, as well as its lock

   817      * state.  The state, in brackets, includes the String {@code

   818      * "Unlocked"} or the String {@code "Write-locked"} or the String

   819      * {@code "Read-locks:"} followed by the current number of

   820      * read-locks held.

   821      *

   822      * @return a string identifying this lock, as well as its lock state

   823      */

   824     public String toString() {

   825         long s = state;

   826         return super.toString() +

   827             ((s & ABITS) == 0L ? "[Unlocked]" :

   828              (s & WBIT) != 0L ? "[Write-locked]" :

   829              "[Read-locks:" + getReadLockCount(s) + "]");

   830     }

   831 

   832     // views

   833 

   834     /**

   835      * Returns a plain {@link Lock} view of this StampedLock in which

   836      * the {@link Lock#lock} method is mapped to {@link #readLock},

   837      * and similarly for other methods. The returned Lock does not

   838      * support a {@link Condition}; method {@link

   839      * Lock#newCondition()} throws {@code

   840      * UnsupportedOperationException}.

   841      *

   842      * @return the lock

   843      */

   844     public Lock asReadLock() {

   845         ReadLockView v;

   846         return ((v = readLockView) != null ? v :

   847                 (readLockView = new ReadLockView()));

   848     }

   849 

   850     /**

   851      * Returns a plain {@link Lock} view of this StampedLock in which

   852      * the {@link Lock#lock} method is mapped to {@link #writeLock},

   853      * and similarly for other methods. The returned Lock does not

   854      * support a {@link Condition}; method {@link

   855      * Lock#newCondition()} throws {@code

   856      * UnsupportedOperationException}.

   857      *

   858      * @return the lock

   859      */

   860     public Lock asWriteLock() {

   861         WriteLockView v;

   862         return ((v = writeLockView) != null ? v :

   863                 (writeLockView = new WriteLockView()));

   864     }

   865 

   866     /**

   867      * Returns a {@link ReadWriteLock} view of this StampedLock in

   868      * which the {@link ReadWriteLock#readLock()} method is mapped to

   869      * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to

   870      * {@link #asWriteLock()}.

   871      *

   872      * @return the lock

   873      */

   874     public ReadWriteLock asReadWriteLock() {

   875         ReadWriteLockView v;

   876         return ((v = readWriteLockView) != null ? v :

   877                 (readWriteLockView = new ReadWriteLockView()));

   878     }

   879 

   880     // view classes

   881 

   882     final class ReadLockView implements Lock {

   883         public void lock() { readLock(); }

   884         public void lockInterruptibly() throws InterruptedException {

   885             readLockInterruptibly();

   886         }

   887         public boolean tryLock() { return tryReadLock() != 0L; }

   888         public boolean tryLock(long time, TimeUnit unit)

   889             throws InterruptedException {

   890             return tryReadLock(time, unit) != 0L;

   891         }

   892         public void unlock() { unstampedUnlockRead(); }

   893         public Condition newCondition() {

   894             throw new UnsupportedOperationException();

   895         }

   896     }

   897 

   898     final class WriteLockView implements Lock {

   899         public void lock() { writeLock(); }

   900         public void lockInterruptibly() throws InterruptedException {

   901             writeLockInterruptibly();

   902         }

   903         public boolean tryLock() { return tryWriteLock() != 0L; }

   904         public boolean tryLock(long time, TimeUnit unit)

   905             throws InterruptedException {

   906             return tryWriteLock(time, unit) != 0L;

   907         }

   908         public void unlock() { unstampedUnlockWrite(); }

   909         public Condition newCondition() {

   910             throw new UnsupportedOperationException();

   911         }

   912     }

   913 

   914     final class ReadWriteLockView implements ReadWriteLock {

   915         public Lock readLock() { return asReadLock(); }

   916         public Lock writeLock() { return asWriteLock(); }

   917     }

   918 

   919     // Unlock methods without stamp argument checks for view classes.

   920     // Needed because view-class lock methods throw away stamps.

   921 

   922     final void unstampedUnlockWrite() {

   923         WNode h; long s;

   924         if (((s = state) & WBIT) == 0L)

   925             throw new IllegalMonitorStateException();

   926         state = (s += WBIT) == 0L ? ORIGIN : s;

   927         if ((h = whead) != null && h.status != 0)

   928             release(h);

   929     }

   930 

   931     final void unstampedUnlockRead() {

   932         for (;;) {

   933             long s, m; WNode h;

   934             if ((m = (s = state) & ABITS) == 0L || m >= WBIT)

   935                 throw new IllegalMonitorStateException();

   936             else if (m < RFULL) {

   937                 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {

   938                     if (m == RUNIT && (h = whead) != null && h.status != 0)

   939                         release(h);

   940                     break;

   941                 }

   942             }

   943             else if (tryDecReaderOverflow(s) != 0L)

   944                 break;

   945         }

   946     }

   947 

   948     private void readObject(java.io.ObjectInputStream s)

   949         throws java.io.IOException, ClassNotFoundException {

   950         s.defaultReadObject();

   951         state = ORIGIN; // reset to unlocked state

   952     }

   953 

   954     // internals

   955 

   956     /**

   957      * Tries to increment readerOverflow by first setting state

   958      * access bits value to RBITS, indicating hold of spinlock,

   959      * then updating, then releasing.

   960      *

   961      * @param s a reader overflow stamp: (s & ABITS) >= RFULL

   962      * @return new stamp on success, else zero

   963      */

   964     private long tryIncReaderOverflow(long s) {

   965         // assert (s & ABITS) >= RFULL;

   966         if ((s & ABITS) == RFULL) {

   967             if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {

   968                 ++readerOverflow;

   969                 state = s;

   970                 return s;

   971             }

   972         }

   973         else if ((LockSupport.nextSecondarySeed() &

   974                   OVERFLOW_YIELD_RATE) == 0)

   975             Thread.yield();

   976         return 0L;

   977     }

   978 

   979     /**

   980      * Tries to decrement readerOverflow.

   981      *

   982      * @param s a reader overflow stamp: (s & ABITS) >= RFULL

   983      * @return new stamp on success, else zero

   984      */

   985     private long tryDecReaderOverflow(long s) {

   986         // assert (s & ABITS) >= RFULL;

   987         if ((s & ABITS) == RFULL) {

   988             if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {

   989                 int r; long next;

   990                 if ((r = readerOverflow) > 0) {

   991                     readerOverflow = r - 1;

   992                     next = s;

   993                 }

   994                 else

   995                     next = s - RUNIT;

   996                  state = next;

   997                  return next;

   998             }

   999         }

  1000         else if ((LockSupport.nextSecondarySeed() &

  1001                   OVERFLOW_YIELD_RATE) == 0)

  1002             Thread.yield();

  1003         return 0L;

  1004     }

  1005 

  1006     /**

  1007      * Wakes up the successor of h (normally whead). This is normally

  1008      * just h.next, but may require traversal from wtail if next

  1009      * pointers are lagging. This may fail to wake up an acquiring

  1010      * thread when one or more have been cancelled, but the cancel

  1011      * methods themselves provide extra safeguards to ensure liveness.

  1012      */

  1013     private void release(WNode h) {

  1014         if (h != null) {

  1015             WNode q; Thread w;

  1016             U.compareAndSwapInt(h, WSTATUS, WAITING, 0);

  1017             if ((q = h.next) == null || q.status == CANCELLED) {

  1018                 for (WNode t = wtail; t != null && t != h; t = t.prev)

  1019                     if (t.status <= 0)

  1020                         q = t;

  1021             }

  1022             if (q != null && (w = q.thread) != null)

  1023                 U.unpark(w);

  1024         }

  1025     }

  1026 

  1027     /**

  1028      * See above for explanation.

  1029      *

  1030      * @param interruptible true if should check interrupts and if so

  1031      * return INTERRUPTED

  1032      * @param deadline if nonzero, the System.nanoTime value to timeout

  1033      * at (and return zero)

  1034      * @return next state, or INTERRUPTED

  1035      */

  1036     private long acquireWrite(boolean interruptible, long deadline) {

  1037         WNode node = null, p;

  1038         for (int spins = -1;;) { // spin while enqueuing

  1039             long m, s, ns;

  1040             if ((m = (s = state) & ABITS) == 0L) {

  1041                 if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))

  1042                     return ns;

  1043             }

  1044             else if (spins < 0)

  1045                 spins = (m == WBIT && wtail == whead) ? SPINS : 0;

  1046             else if (spins > 0) {

  1047                 if (LockSupport.nextSecondarySeed() >= 0)

  1048                     --spins;

  1049             }

  1050             else if ((p = wtail) == null) { // initialize queue

  1051                 WNode hd = new WNode(WMODE, null);

  1052                 if (U.compareAndSwapObject(this, WHEAD, null, hd))

  1053                     wtail = hd;

  1054             }

  1055             else if (node == null)

  1056                 node = new WNode(WMODE, p);

  1057             else if (node.prev != p)

  1058                 node.prev = p;

  1059             else if (U.compareAndSwapObject(this, WTAIL, p, node)) {

  1060                 p.next = node;

  1061                 break;

  1062             }

  1063         }

  1064 

  1065         for (int spins = -1;;) {

  1066             WNode h, np, pp; int ps;

  1067             if ((h = whead) == p) {

  1068                 if (spins < 0)

  1069                     spins = HEAD_SPINS;

  1070                 else if (spins < MAX_HEAD_SPINS)

  1071                     spins <<= 1;

  1072                 for (int k = spins;;) { // spin at head

  1073                     long s, ns;

  1074                     if (((s = state) & ABITS) == 0L) {

  1075                         if (U.compareAndSwapLong(this, STATE, s,

  1076                                                  ns = s + WBIT)) {

  1077                             whead = node;

  1078                             node.prev = null;

  1079                             return ns;

  1080                         }

  1081                     }

  1082                     else if (LockSupport.nextSecondarySeed() >= 0 &&

  1083                              --k <= 0)

  1084                         break;

  1085                 }

  1086             }

  1087             else if (h != null) { // help release stale waiters

  1088                 WNode c; Thread w;

  1089                 while ((c = h.cowait) != null) {

  1090                     if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&

  1091                         (w = c.thread) != null)

  1092                         U.unpark(w);

  1093                 }

  1094             }

  1095             if (whead == h) {

  1096                 if ((np = node.prev) != p) {

  1097                     if (np != null)

  1098                         (p = np).next = node;   // stale

  1099                 }

  1100                 else if ((ps = p.status) == 0)

  1101                     U.compareAndSwapInt(p, WSTATUS, 0, WAITING);

  1102                 else if (ps == CANCELLED) {

  1103                     if ((pp = p.prev) != null) {

  1104                         node.prev = pp;

  1105                         pp.next = node;

  1106                     }

  1107                 }

  1108                 else {

  1109                     long time; // 0 argument to park means no timeout

  1110                     if (deadline == 0L)

  1111                         time = 0L;

  1112                     else if ((time = deadline - System.nanoTime()) <= 0L)

  1113                         return cancelWaiter(node, node, false);

  1114                     Thread wt = Thread.currentThread();

  1115                     U.putObject(wt, PARKBLOCKER, this);

  1116                     node.thread = wt;

  1117                     if (p.status < 0 && (p != h || (state & ABITS) != 0L) &&

  1118                         whead == h && node.prev == p)

  1119                         U.park(false, time);  // emulate LockSupport.park

  1120                     node.thread = null;

  1121                     U.putObject(wt, PARKBLOCKER, null);

  1122                     if (interruptible && Thread.interrupted())

  1123                         return cancelWaiter(node, node, true);

  1124                 }

  1125             }

  1126         }

  1127     }

  1128 

  1129     /**

  1130      * See above for explanation.

  1131      *

  1132      * @param interruptible true if should check interrupts and if so

  1133      * return INTERRUPTED

  1134      * @param deadline if nonzero, the System.nanoTime value to timeout