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 */
013 package org.jikesrvm.mm.mmtk;
014
015 import org.jikesrvm.VM;
016
017 import org.vmmagic.unboxed.*;
018 import org.vmmagic.pragma.*;
019
020 import org.jikesrvm.runtime.Entrypoints;
021 import org.jikesrvm.runtime.Magic;
022 import org.jikesrvm.scheduler.RVMThread;
023 import 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 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 public void setName(String str) {
087 name = str;
088 }
089 public void acquire() {
090 RVMThread me = RVMThread.getCurrentThread();
091 Offset offset=Entrypoints.lockStateField.getOffset();
092 boolean acquired=false;
093 for (int i=0;i<SPIN_LIMIT;++i) {
094 int oldState=Magic.prepareInt(this,offset);
095 // NOTE: we could be smart here and break out of the spin if we see
096 // that the state is CLEAR_QUEUED or LOCKED_QUEUED, or we could even
097 // check the queue directly and see if there is anything on it; this
098 // would make the lock slightly more fair.
099 if ((oldState==CLEAR &&
100 Magic.attemptInt(this,offset,CLEAR,LOCKED)) ||
101 (oldState==CLEAR_QUEUED &&
102 Magic.attemptInt(this,offset,CLEAR_QUEUED,LOCKED_QUEUED))) {
103 acquired=true;
104 break;
105 }
106 }
107 if (!acquired) {
108 for (;;) {
109 int oldState=Magic.prepareInt(this,offset);
110 if ((oldState==CLEAR &&
111 Magic.attemptInt(this,offset,CLEAR,LOCKED)) ||
112 (oldState==CLEAR_QUEUED &&
113 Magic.attemptInt(this,offset,CLEAR_QUEUED,LOCKED_QUEUED))) {
114 break;
115 } else if ((oldState==LOCKED &&
116 Magic.attemptInt(this,offset,LOCKED,QUEUEING)) ||
117 (oldState==LOCKED_QUEUED &&
118 Magic.attemptInt(this,offset,LOCKED_QUEUED,QUEUEING))) {
119 queue.enqueue(me);
120 Magic.sync();
121 state=LOCKED_QUEUED;
122 me.monitor().lockNoHandshake();
123 while (queue.isQueued(me)) {
124 // use await instead of waitNicely because this is NOT a GC point!
125 me.monitor().waitNoHandshake();
126 }
127 me.monitor().unlock();
128 }
129 }
130 }
131 thread = me;
132 where = -1;
133 Magic.isync();
134 }
135
136 public void check(int w) {
137 if (VM.VerifyAssertions) VM._assert(RVMThread.getCurrentThread() == thread);
138 where = w;
139 }
140
141 public void release() {
142 where=-1;
143 thread=null;
144 Magic.sync();
145 Offset offset=Entrypoints.lockStateField.getOffset();
146 for (;;) {
147 int oldState=Magic.prepareInt(this,offset);
148 if (VM.VerifyAssertions) VM._assert(oldState==LOCKED ||
149 oldState==LOCKED_QUEUED ||
150 oldState==QUEUEING);
151 if (oldState==LOCKED &&
152 Magic.attemptInt(this,offset,LOCKED,CLEAR)) {
153 break;
154 } else if (oldState==LOCKED_QUEUED &&
155 Magic.attemptInt(this,offset,LOCKED_QUEUED,QUEUEING)) {
156 RVMThread toAwaken=queue.dequeue();
157 if (VM.VerifyAssertions) VM._assert(toAwaken!=null);
158 boolean queueEmpty=queue.isEmpty();
159 Magic.sync();
160 if (queueEmpty) {
161 state=CLEAR;
162 } else {
163 state=CLEAR_QUEUED;
164 }
165 toAwaken.monitor().lockedBroadcastNoHandshake();
166 break;
167 }
168 }
169 }
170 }