001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.mm.mmtk;
014
015import org.jikesrvm.VM;
016
017import org.vmmagic.unboxed.*;
018import org.vmmagic.pragma.*;
019
020import org.jikesrvm.runtime.Entrypoints;
021import org.jikesrvm.runtime.Magic;
022import org.jikesrvm.scheduler.RVMThread;
023import org.jikesrvm.scheduler.ThreadQueue;
024
025/**
026 * Adaptive mutex with a spinlock fast path.  Designed for good performance
027 * on native threaded systems.  This implementation has the following specific
028 * properties:
029 * <ul>
030 * <li>It behaves like a spinlock on the fast path (one CAS to lock, one CAS
031 *     to unlock, if there is no contention).</li>
032 * <li>It has the ability to spin for some predetermined number of cycles
033 *     (see <code>SPIN_LIMIT</code>).</li>
034 * <li>Adapts to contention by eventually placing contending threads on a
035 *     queue and parking them.</li>
036 * <li>Has a weak fairness guarantee: contenders follow queue discipline,
037 *     except that new contenders may "beat" the thread at the head of the
038 *     queue if they arrive just as the lock becomes available and the thread
039 *     at the head of the queue just got scheduled.</li>
040 * </ul>
041 * @author Filip Pizlo
042 */
043@Uninterruptible public class Lock extends org.mmtk.vm.Lock {
044
045  // Core Instance fields
046  private String name;        // logical name of lock
047  private final int id;       // lock id (based on a non-resetting counter)
048  private static int lockCount;
049  private static final int SPIN_LIMIT = 1000;
050  /** Lock is not held and the queue is empty.  When the lock is in this
051   * state, there <i>may</i> be a thread that just got dequeued and is
052   * about to enter into contention on the lock. */
053  private static final int CLEAR = 0;
054  /** Lock is held and the queue is empty. */
055  private static final int LOCKED = 1;
056  /** Lock is not held but the queue is non-empty.  This state guarantees
057   * that there is a thread that got dequeued and is about to contend on
058   * the lock. */
059  private static final int CLEAR_QUEUED = 2;
060  /** Lock is held and the queue is non-empty. */
061  private static final int LOCKED_QUEUED = 3;
062  /** Some thread is currently engaged in an enqueue or dequeue operation,
063   * and will return the lock to whatever it was in previously once that
064   * operation is done.  During this states any lock/unlock attempts will
065   * spin until the lock reverts to some other state. */
066  private static final int QUEUEING = 4;
067  private final ThreadQueue queue;
068  @Entrypoint
069  private int state;
070
071  // Diagnosis Instance fields
072  @Untraced
073  private RVMThread thread;   // if locked, who locked it?
074  private int where = -1;     // how far along has the lock owner progressed?
075  public Lock(String name) {
076    this();
077    this.name = name;
078  }
079
080  public Lock() {
081    id = lockCount++;
082    queue = new ThreadQueue();
083    state = CLEAR;
084  }
085
086  @Override
087  public void setName(String str) {
088    name = str;
089  }
090  @Override
091  public void acquire() {
092    RVMThread me = RVMThread.getCurrentThread();
093    Offset offset = Entrypoints.lockStateField.getOffset();
094    boolean acquired = false;
095    for (int i = 0; me.isOnQueue() || i < SPIN_LIMIT;++i) {
096      int oldState = Magic.prepareInt(this,offset);
097      // NOTE: we could be smart here and break out of the spin if we see
098      // that the state is CLEAR_QUEUED or LOCKED_QUEUED, or we could even
099      // check the queue directly and see if there is anything on it; this
100      // would make the lock slightly more fair.
101      if ((oldState == CLEAR &&
102           Magic.attemptInt(this,offset,CLEAR,LOCKED)) ||
103          (oldState == CLEAR_QUEUED &&
104           Magic.attemptInt(this,offset,CLEAR_QUEUED,LOCKED_QUEUED))) {
105        acquired = true;
106        break;
107      }
108    }
109    if (!acquired) {
110      for (;;) {
111        int oldState = Magic.prepareInt(this,offset);
112        if ((oldState == CLEAR &&
113             Magic.attemptInt(this,offset,CLEAR,LOCKED)) ||
114            (oldState == CLEAR_QUEUED &&
115             Magic.attemptInt(this,offset,CLEAR_QUEUED,LOCKED_QUEUED))) {
116          break;
117        } else if ((oldState == LOCKED &&
118                    Magic.attemptInt(this,offset,LOCKED,QUEUEING)) ||
119                   (oldState == LOCKED_QUEUED &&
120                    Magic.attemptInt(this,offset,LOCKED_QUEUED,QUEUEING))) {
121          Magic.sync();
122          queue.enqueue(me);
123          Magic.sync();
124          state = LOCKED_QUEUED;
125          me.monitor().lockNoHandshake();
126          while (queue.isQueued(me)) {
127            // use waitNoHandshake instead of waitWithHandshake because this is NOT a GC point!
128            me.monitor().waitNoHandshake();
129          }
130          me.monitor().unlock();
131        }
132      }
133    }
134    thread = me;
135    where = -1;
136    Magic.isync();
137  }
138
139  @Override
140  public void check(int w) {
141    if (VM.VerifyAssertions) VM._assert(RVMThread.getCurrentThread() == thread);
142    where = w;
143  }
144
145  @Override
146  public void release() {
147    where = -1;
148    thread = null;
149    Magic.sync();
150    Offset offset = Entrypoints.lockStateField.getOffset();
151    for (;;) {
152      int oldState = Magic.prepareInt(this,offset);
153      if (VM.VerifyAssertions) VM._assert(oldState == LOCKED ||
154                                          oldState == LOCKED_QUEUED ||
155                                          oldState == QUEUEING);
156      if (oldState == LOCKED &&
157          Magic.attemptInt(this,offset,LOCKED,CLEAR)) {
158        break;
159      } else if (oldState == LOCKED_QUEUED &&
160                 Magic.attemptInt(this,offset,LOCKED_QUEUED,QUEUEING)) {
161        Magic.sync();
162        RVMThread toAwaken = queue.dequeue();
163        if (VM.VerifyAssertions) VM._assert(toAwaken != null);
164        boolean queueEmpty = queue.isEmpty();
165        Magic.sync();
166        if (queueEmpty) {
167          state = CLEAR;
168        } else {
169          state = CLEAR_QUEUED;
170        }
171        toAwaken.monitor().lockedBroadcastNoHandshake();
172        break;
173      }
174    }
175  }
176}