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 @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 queue.enqueue(me);
122 Magic.sync();
123 state=LOCKED_QUEUED;
124 me.monitor().lockNoHandshake();
125 while (queue.isQueued(me)) {
126 // use await instead of waitNicely because this is NOT a GC point!
127 me.monitor().waitNoHandshake();
128 }
129 me.monitor().unlock();
130 }
131 }
132 }
133 thread = me;
134 where = -1;
135 Magic.isync();
136 }
137
138 @Override
139 public void check(int w) {
140 if (VM.VerifyAssertions) VM._assert(RVMThread.getCurrentThread() == thread);
141 where = w;
142 }
143
144 @Override
145 public void release() {
146 where=-1;
147 thread=null;
148 Magic.sync();
149 Offset offset=Entrypoints.lockStateField.getOffset();
150 for (;;) {
151 int oldState=Magic.prepareInt(this,offset);
152 if (VM.VerifyAssertions) VM._assert(oldState==LOCKED ||
153 oldState==LOCKED_QUEUED ||
154 oldState==QUEUEING);
155 if (oldState==LOCKED &&
156 Magic.attemptInt(this,offset,LOCKED,CLEAR)) {
157 break;
158 } else if (oldState==LOCKED_QUEUED &&
159 Magic.attemptInt(this,offset,LOCKED_QUEUED,QUEUEING)) {
160 RVMThread toAwaken=queue.dequeue();
161 if (VM.VerifyAssertions) VM._assert(toAwaken!=null);
162 boolean queueEmpty=queue.isEmpty();
163 Magic.sync();
164 if (queueEmpty) {
165 state=CLEAR;
166 } else {
167 state=CLEAR_QUEUED;
168 }
169 toAwaken.monitor().lockedBroadcastNoHandshake();
170 break;
171 }
172 }
173 }
174 }