View Javadoc

1   // Monitor.java, created Mon Feb  5 23:23:21 2001 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Runtime;
5   
6   import joeq.Allocator.DefaultHeapAllocator;
7   import joeq.Allocator.ObjectLayout;
8   import joeq.Class.PrimordialClassLoader;
9   import joeq.Class.jq_Class;
10  import joeq.Class.jq_InstanceField;
11  import joeq.Class.jq_StaticMethod;
12  import joeq.Memory.HeapAddress;
13  import joeq.Scheduler.jq_Thread;
14  import jwutil.strings.Strings;
15  import jwutil.util.Assert;
16  
17  /*
18   * @author  John Whaley <jwhaley@alum.mit.edu>
19   * @version $Id: Monitor.java 1941 2004-09-30 03:37:06Z joewhaley $
20   */
21  public class Monitor {
22  
23      public static /*final*/ boolean TRACE = false;
24      
25      private Monitor() {
26          Assert.UNREACHABLE("Monitor objects must be constructed specially.");
27      }
28      
29      int atomic_count = 0;  // -1 means no threads; 0 means one thread (monitor_owner)
30      jq_Thread monitor_owner;
31      int entry_count = 0;    // 1 means locked once.
32      int/*CPointer*/ semaphore;
33      
34      /*** Returns the depth of the lock on the given object. */
35      public static int getLockEntryCount(Object k) {
36          int lockword = HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET).peek4();
37          if (lockword < 0) {
38              Monitor m = getMonitor(lockword);
39              if (TRACE) SystemInterface.debugwriteln("Getting fat lock entry count: "+m.entry_count);
40              return m.entry_count;
41          }
42          int c = ((lockword & ObjectLayout.LOCK_COUNT_MASK) >> ObjectLayout.LOCK_COUNT_SHIFT);
43          if ((lockword & ObjectLayout.THREAD_ID_MASK) != 0) ++c;
44          if (TRACE) SystemInterface.debugwriteln("Getting thin lock entry count, lockword="+Strings.hex8(lockword)+", count="+c);
45          return c;
46      }
47      
48      /*** Monitorenter runtime routine.
49       *  Checks for thin lock usage, otherwise falls back to inflated locks.
50       */
51      public static void monitorenter(Object k) {
52          jq_Thread t = Unsafe.getThreadBlock();
53          int tid = t.getThreadId(); // pre-shifted thread id
54          
55          // attempt fast path: object is not locked.
56          HeapAddress status_address = (HeapAddress) HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET);
57          int status_flags = status_address.peek4() & ObjectLayout.STATUS_FLAGS_MASK;
58          int newlockword = status_flags | tid;
59          int oldlockword = status_address.atomicCas4(status_flags, newlockword);
60          if (Unsafe.isEQ()) {
61              // fast path: not locked
62              return;
63          }
64          
65          // object is locked or has an inflated lock.
66          int counter = oldlockword ^ newlockword; // if tid's are equal, this extracts the counter.
67          if (counter >= ObjectLayout.LOCK_COUNT_MASK) {
68              // slow path: other thread owns thin lock, or entry counter == max
69              int entrycount;
70              if (counter == ObjectLayout.LOCK_COUNT_MASK) {
71                  // thin lock entry counter == max, so we need to inflate ourselves.
72                  if (TRACE) SystemInterface.debugwriteln("Thin lock counter overflow, inflating lock...");
73                  entrycount = (ObjectLayout.LOCK_COUNT_MASK >> ObjectLayout.LOCK_COUNT_SHIFT)+2;
74                  Monitor m = allocateInflatedLock();
75                  m.monitor_owner = t;
76                  m.entry_count = entrycount;
77                  newlockword = HeapAddress.addressOf(m).to32BitValue() | ObjectLayout.LOCK_EXPANDED | status_flags;
78                  // we own the lock, so a simple write is sufficient.
79                  Assert._assert(HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET).peek4() == oldlockword);
80                  HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(newlockword);
81              } else {
82                  // thin lock owned by another thread.
83                  if (TRACE) SystemInterface.debugwriteln(t+" tid "+Strings.hex(tid)+": Lock contention with tid "+Strings.hex(oldlockword & ObjectLayout.THREAD_ID_MASK)+", inflating...");
84                  entrycount = 1;
85                  Monitor m = allocateInflatedLock();
86                  m.monitor_owner = t;
87                  m.entry_count = entrycount;
88                  // install an inflated lock.
89                  installInflatedLock(k, m);
90              }
91          } else if (counter < 0) {
92              // slow path 2: high bit of lock word is set --> inflated lock
93              Monitor m = getMonitor(oldlockword);
94              m.lock(t);
95          } else {
96              // not-quite-so-fast path: locked by current thread.  increment counter.
97              // we own the lock, so a simple write is sufficient.
98              HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(oldlockword+ObjectLayout.LOCK_COUNT_INC);
99          }
100     }
101     
102     /*** Monitorexit runtime routine.
103      *  Checks for thin lock usage, otherwise falls back to inflated locks.
104      */
105     public static void monitorexit(Object k) {
106         jq_Thread t = Unsafe.getThreadBlock();
107         int tid = t.getThreadId(); // pre-shifted
108         HeapAddress status_address = (HeapAddress) HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET);
109         int oldlockword = status_address.peek4();
110         // if not inflated and tid matches, this contains status flags and counter
111         int counter = oldlockword ^ tid;
112         if (counter < 0) {
113             // inflated lock
114             Monitor m = getMonitor(oldlockword);
115             m.unlock(t);
116         } else if (counter <= ObjectLayout.STATUS_FLAGS_MASK) {
117             // owned by us and count is zero.  clear tid field.
118             status_address.atomicAnd(ObjectLayout.STATUS_FLAGS_MASK);
119         } else if (counter <= (ObjectLayout.LOCK_COUNT_MASK | ObjectLayout.STATUS_FLAGS_MASK)) {
120             // owned by us but count is non-zero.  decrement count.
121             status_address.atomicSub(ObjectLayout.LOCK_COUNT_INC);
122         } else {
123             // lock not owned by us!
124             //if (TRACE)
125                 SystemInterface.debugwriteln("Thin lock not owned by us ("+Strings.hex8(tid)+")! lockword="+Strings.hex8(oldlockword));
126             throw new IllegalMonitorStateException();
127         }
128     }
129     
130     /*** Get the Monitor object associated with this lockword. */
131     public static Monitor getMonitor(int lockword) {
132         int word = lockword & (~ObjectLayout.LOCK_EXPANDED & ~ObjectLayout.STATUS_FLAGS_MASK);
133         HeapAddress a = HeapAddress.address32(word);
134         return (Monitor)a.asObject();
135     }
136     
137     public static Monitor allocateInflatedLock() {
138         // Monitor must be 8-byte aligned.
139         return (Monitor)DefaultHeapAllocator.allocateObjectAlign8(_class.getInstanceSize(), _class.getVTable());
140     }
141     
142     public void free() {
143         // nop. we will be garbage collected.
144     }
145     
146     /*** Installs an inflated lock on the given object.
147      *  Uses a spin-loop to wait until the object is unlocked or inflated.
148      */
149     public static void installInflatedLock(Object k, Monitor m) {
150         Assert._assert(m.monitor_owner == Unsafe.getThreadBlock());
151         Assert._assert(m.entry_count >= 1);
152         for (;;) {
153             HeapAddress status_address = (HeapAddress) HeapAddress.addressOf(k).offset(ObjectLayout.STATUS_WORD_OFFSET);
154             int oldlockword = status_address.peek4();
155             if (oldlockword < 0) {
156                 // inflated by another thread!  free our inflated lock and use that one.
157                 Assert._assert(m.entry_count == 1);
158                 m.free();
159                 Monitor m2 = getMonitor(oldlockword);
160                 if (TRACE) SystemInterface.debugwriteln("Inflated by another thread! lockword="+Strings.hex8(oldlockword)+" lock="+m2);
161                 Assert._assert(m != m2);
162                 m2.lock(Unsafe.getThreadBlock());
163                 return;
164             }
165             int status_flags = oldlockword & ObjectLayout.STATUS_FLAGS_MASK;
166             HeapAddress m_addr = HeapAddress.addressOf(m);
167             if ((m_addr.to32BitValue() & ObjectLayout.STATUS_FLAGS_MASK) != 0 ||
168                 (m_addr.to32BitValue() & ObjectLayout.LOCK_EXPANDED) != 0) {
169                 Assert.UNREACHABLE("Monitor object has address "+m_addr.stringRep());
170             }
171             int newlockword = m_addr.to32BitValue() | ObjectLayout.LOCK_EXPANDED | status_flags;
172             status_address.atomicCas4(status_flags, newlockword);
173             if (Unsafe.isEQ()) {
174                 // successfully obtained inflated lock.
175                 if (TRACE) SystemInterface.debugwriteln("Thread "+m.monitor_owner.getThreadId()+" obtained inflated lock! new lockword="+Strings.hex8(newlockword));
176                 return;
177             } else {
178                 if (TRACE) SystemInterface.debugwriteln("Thread "+m.monitor_owner.getThreadId()+" failed to obtain inflated lock, lockword was "+Strings.hex8(oldlockword));
179             }
180             // another thread has a thin lock on this object.  yield to scheduler.
181             Thread.yield();
182         }
183     }
184 
185     /*** Lock this monitor with the given thread block.
186      */
187     public void lock(jq_Thread t) {
188         jq_Thread m_t = this.monitor_owner;
189         if (m_t == t) {
190             // we own the lock.
191             Assert._assert(this.atomic_count >= 0);
192             Assert._assert(this.entry_count > 0);
193             ++this.entry_count;
194             if (TRACE) SystemInterface.debugwriteln("We ("+t+") own lock "+this+", incrementing entry count: "+this.entry_count);
195             return;
196         }
197         if (TRACE) SystemInterface.debugwriteln("We ("+t+") are attempting to obtain lock "+this);
198         // another thread or no thread owns the lock. increase atomic count.
199         HeapAddress ac_loc = (HeapAddress) HeapAddress.addressOf(this).offset(_atomic_count.getOffset());
200         ac_loc.atomicAdd(1);
201         if (!Unsafe.isEQ()) {
202             // someone else already owns the lock.
203             if (TRACE) SystemInterface.debugwriteln("Lock "+this+" cannot be obtained (owned by "+m_t+", or there are other waiters); waiting on semaphore ("+this.atomic_count+" waiters)");
204             // create a semaphore if there isn't one already, and wait on it.
205             this.waitOnSemaphore();
206             if (TRACE) SystemInterface.debugwriteln("We ("+t+") finished waiting on "+this);
207         } else {
208             if (TRACE) SystemInterface.debugwriteln(this+" is unlocked, we ("+t+") obtain it.");
209         }
210         Assert._assert(this.monitor_owner == null);
211         Assert._assert(this.entry_count == 0);
212         Assert._assert(this.atomic_count >= 0);
213         if (TRACE) SystemInterface.debugwriteln("We ("+t+") obtained lock "+this);
214         this.monitor_owner = t;
215         this.entry_count = 1;
216     }
217     
218     /*** Unlock this monitor with the given thread block.
219      */
220     public void unlock(jq_Thread t) {
221         jq_Thread m_t = this.monitor_owner;
222         if (m_t != t) {
223             // lock not owned by us!
224             //if (TRACE)
225                 SystemInterface.debugwriteln("We ("+t+") tried to unlock lock "+this+" owned by "+m_t);
226             throw new IllegalMonitorStateException();
227         }
228         if (--this.entry_count > 0) {
229             // not zero yet.
230             if (TRACE) SystemInterface.debugwriteln("Decrementing lock "+this+" entry count "+this.entry_count);
231             return;
232         }
233         if (TRACE) SystemInterface.debugwriteln("We ("+t+") are unlocking lock "+this+", current waiters="+this.atomic_count);
234         this.monitor_owner = null;
235         HeapAddress ac_loc = (HeapAddress) HeapAddress.addressOf(this).offset(_atomic_count.getOffset());
236         ac_loc.atomicSub(1);
237         if (Unsafe.isGE()) {
238             // threads are waiting on us, release the semaphore.
239             if (TRACE) SystemInterface.debugwriteln((this.atomic_count+1)+" threads are waiting on released lock "+this+", releasing semaphore.");
240             this.releaseSemaphore();
241         } else {
242             if (TRACE) SystemInterface.debugwriteln("No threads are waiting on released lock "+this+".");
243         }
244     }
245     
246     /*** Create a semaphore if there isn't one already, and wait on it.
247      */
248     public void waitOnSemaphore() {
249         if (this.semaphore == 0) {
250             this.semaphore = SystemInterface.init_semaphore();
251         }
252         // TODO: integrate waiting on a semaphore into the scheduler
253         for (;;) {
254             int rc = SystemInterface.wait_for_single_object(this.semaphore, 10); // timeout
255             if (rc == SystemInterface.WAIT_TIMEOUT) {
256                 Thread.yield();
257                 continue;
258             } else if (rc == 0) {
259                 return;
260             } else {
261                 SystemInterface.debugwriteln("Bad return value from WaitForSingleObject: "+rc);
262             }
263         }
264     }
265     /*** Create a semaphore if there isn't one already, and release it.
266      */
267     public void releaseSemaphore() {
268         if (this.semaphore == 0) {
269             this.semaphore = SystemInterface.init_semaphore();
270         }
271         SystemInterface.release_semaphore(this.semaphore, 1);
272     }
273     
274     public static final jq_Class _class;
275     public static final jq_StaticMethod _monitorenter;
276     public static final jq_StaticMethod _monitorexit;
277     public static final jq_InstanceField _atomic_count;
278     static {
279         _class = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Runtime/Monitor;");
280         _monitorenter = _class.getOrCreateStaticMethod("monitorenter", "(Ljava/lang/Object;)V");
281         _monitorexit = _class.getOrCreateStaticMethod("monitorexit", "(Ljava/lang/Object;)V");
282         _atomic_count = _class.getOrCreateInstanceField("atomic_count", "I");
283     }
284 
285 }