src/main/gov/nasa/jpf/vm/Monitor.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.vm;
  19
  20 import gov.nasa.jpf.util.HashData;
  21
  22 import java.io.PrintWriter;
  23 import java.util.Arrays;
  24
  25 /**
  26  * Represents the variable, hash-collapsed pooled data associated with an object
  27  * that is not related to the object values (->Fields), but to the use of the
  28  * object for synchronization purposes (locks and signals).
  29  *
  30  */
  31 public class Monitor implements Cloneable {
  32
  33   static ThreadInfo[] emptySet = new ThreadInfo[0];
  34
  35   /** the thread owning the lock */
  36   private ThreadInfo lockingThread;
  37
  38   /** the nesting level for recursive lock acquisition */
  39   private int lockCount;
  40
  41   /**
  42    * the list of threads that try to acquire the lock (can be in blocked, waiting,
  43    * interrupted or running state).
  44    */
  45   ThreadInfo[] lockedThreads;
  46
  47   /**
  48    * Creates a new empty monitor.
  49    */
  50   public Monitor () {
  51     lockingThread = null;
  52     lockCount = 0;
  53     lockedThreads = emptySet;
  54   }
  55
  56   private Monitor (ThreadInfo locking, int count, ThreadInfo[] locked) {
  57     lockingThread = locking;
  58     lockCount = count;
  59     lockedThreads = locked.clone();
  60     Arrays.sort(lockedThreads);
  61   }
  62
  63   public void printFields (PrintWriter pw) {
  64     int i;
  65
  66     pw.print(this);
  67     pw.print(" [");
  68     if (lockingThread != null) {
  69       pw.print( "locked by: ");
  70       pw.print( lockingThread.getName());
  71     } else {
  72       pw.print( "unlocked");
  73     }
  74
  75     pw.print(", lockCount: ");
  76     pw.print( lockCount);
  77
  78     pw.print(", locked: {");
  79     for (i=0; i<lockedThreads.length; i++) {
  80       if (i > 0) pw.print(',');
  81       pw.print(lockedThreads[i].getName());
  82       pw.print(':');
  83       pw.print(lockedThreads[i].getStateName());
  84     }
  85     pw.println("}]");
  86   }
  87
  88   // for debugging purposes
  89   public void dump() {
  90     PrintWriter pw = new PrintWriter(System.out);
  91     printFields(pw);
  92     pw.flush();
  93   }
  94
  95   Monitor cloneWithLocked (ThreadInfo ti) {
  96     return new Monitor(lockingThread, lockCount, add(lockedThreads, ti));
  97   }
  98
  99   Monitor cloneWithoutLocked (ThreadInfo ti) {
 100     return new Monitor(lockingThread, lockCount, remove(lockedThreads, ti));
 101   }
 102
 103   @Override
 104   public Monitor clone () {
 105     try {
 106       // no need to clone the empty set (which should be the majority of cases)
 107       Monitor m = (Monitor) super.clone();
 108       if (lockedThreads != emptySet) {
 109         m.lockedThreads = lockedThreads.clone();
 110       }
 111       return m;
 112
 113     } catch (CloneNotSupportedException cnsx) {
 114       throw new InternalError("should not happen");
 115     }
 116   }
 117
 118
 119   /**
 120    * Compares to another object.
 121    */
 122   @Override
 123   public boolean equals (Object o) {
 124     if (o == null) {
 125       return false;
 126     }
 127
 128     if (!(o instanceof Monitor)) {
 129       return false;
 130     }
 131
 132     Monitor m = (Monitor) o;
 133
 134     if (lockingThread != m.getLockingThread()) {
 135       return false;
 136     }
 137
 138     if (lockCount != m.getLockCount()) {
 139       return false;
 140     }
 141
 142     ThreadInfo[] list = m.lockedThreads;
 143     if (lockedThreads.length != list.length) {
 144       return false;
 145     }
 146
 147     for (int i = 0; i < lockedThreads.length; i++) {
 148       if (lockedThreads[i] != list[i]) {
 149         return false;
 150       }
 151     }
 152
 153     return true;
 154   }
 155
 156
 157   public void hash (HashData hd) {
 158     if (lockingThread != null) {
 159       hd.add(lockingThread.getId());
 160     }
 161
 162     hd.add(lockCount);
 163
 164     for (int i = 0; i < lockedThreads.length; i++) {
 165       hd.add(lockedThreads[i].getId());
 166     }
 167   }
 168
 169
 170   @Override
 171   public int hashCode () {
 172     HashData hd = new HashData();
 173     hash(hd);
 174     return hd.getValue();
 175   }
 176
 177
 178   /**
 179    * Returns the number of nested locks acquired.
 180    */
 181   public int getLockCount () {
 182     return lockCount;
 183   }
 184
 185
 186   /**
 187    * Returns the identifier of the thread holding the lock.
 188    */
 189   public ThreadInfo getLockingThread () {
 190     return lockingThread;
 191   }
 192
 193
 194   /**
 195    * Returns the list of locked threads
 196    */
 197   public ThreadInfo[] getLockedThreads() {
 198     return lockedThreads;
 199   }
 200
 201
 202   public boolean hasLockedThreads () {
 203     return (lockedThreads.length > 0);
 204   }
 205
 206   public boolean hasWaitingThreads () {
 207     for (int i=0; i<lockedThreads.length; i++) {
 208       if (lockedThreads[i].isWaiting()) {
 209         return true;
 210       }
 211     }
 212
 213     return false;
 214   }
 215
 216   public int getNumberOfWaitingThreads() {
 217     int n=0;
 218
 219     for (ThreadInfo ti : lockedThreads){
 220       if (ti.isWaiting()){
 221         n++;
 222       }
 223     }
 224
 225     return n;
 226   }
 227
 228
 229   public ThreadInfo[] getWaitingThreads() {
 230     int n = getNumberOfWaitingThreads();
 231
 232     if (n > 0){
 233       ThreadInfo[] list = new ThreadInfo[n];
 234       int i=0;
 235       for (int j=0; j<lockedThreads.length && i<n; j++){
 236         ThreadInfo ti = lockedThreads[j];
 237         if (ti.isWaiting()){
 238           list[i++] = ti;
 239         }
 240       }
 241
 242       return list;
 243
 244     } else {
 245       return emptySet;
 246     }
 247   }
 248
 249   public int getNumberOfBlockedThreads() {
 250     int n=0;
 251
 252     for (ThreadInfo ti : lockedThreads){
 253       if (ti.isBlocked()){
 254         n++;
 255       }
 256     }
 257
 258     return n;
 259   }
 260
 261
 262   public ThreadInfo[] getBlockedThreads() {
 263     int n = getNumberOfBlockedThreads();
 264
 265     if (n > 0){
 266       ThreadInfo[] list = new ThreadInfo[n];
 267       int i=0;
 268       for (int j=0; j<lockedThreads.length && i<n; j++){
 269         ThreadInfo ti = lockedThreads[j];
 270         if (ti.isBlocked()){
 271           list[i++] = ti;
 272         }
 273       }
 274
 275       return list;
 276
 277     } else {
 278       return emptySet;
 279     }
 280   }
 281
 282
 283   public int getNumberOfBlockedOrWaitingThreads() {
 284     int n=0;
 285
 286     for (ThreadInfo ti : lockedThreads){
 287       if (ti.isBlocked() || ti.isWaiting()){
 288         n++;
 289       }
 290     }
 291
 292     return n;
 293   }
 294
 295
 296   public ThreadInfo[] getBlockedOrWaitingThreads() {
 297     int n = getNumberOfBlockedThreads();
 298
 299     if (n > 0){
 300       ThreadInfo[] list = new ThreadInfo[n];
 301       int i=0;
 302       for (int j=0; j<lockedThreads.length && i<n; j++){
 303         ThreadInfo ti = lockedThreads[j];
 304         if (ti.isBlocked() || ti.isWaiting()){
 305           list[i++] = ti;
 306         }
 307       }
 308
 309       return list;
 310
 311     } else {
 312       return emptySet;
 313     }
 314   }
 315
 316
 317   /**
 318    * Returns true if it is possible to lock the monitor.
 319    */
 320   public boolean canLock (ThreadInfo th) {
 321     if (lockingThread == null) {
 322       return true;
 323     }
 324
 325     return (lockingThread == th);
 326   }
 327
 328
 329   void setLockingThread (ThreadInfo ti) {
 330     lockingThread = ti;
 331   }
 332
 333
 334   void incLockCount () {
 335     lockCount++;
 336   }
 337
 338
 339   void decLockCount () {
 340     assert lockCount > 0 : "negative lockCount";
 341     lockCount--;
 342   }
 343
 344
 345   void setLockCount (int lc) {
 346     assert lc >= 0 : "attempt to set negative lockCount";
 347     lockCount = lc;
 348   }
 349
 350   public int objectHashCode () {
 351     return super.hashCode();
 352   }
 353
 354   void resetLockedThreads () {
 355     lockedThreads = emptySet;
 356   }
 357
 358   public boolean isLocking(ThreadInfo ti){
 359     if (lockedThreads != null){
 360       for (ThreadInfo lti : lockedThreads){
 361         if (lti == ti){
 362           return true;
 363         }
 364       }
 365     }
 366
 367     return false;
 368   }
 369
 370
 371   static boolean containsLocked(ThreadInfo[] list, ThreadInfo ti){
 372     int len = list.length;
 373
 374     for (int i=0; i<len; i++){
 375       if (list[i] == ti){
 376         return true;
 377       }
 378     }
 379
 380     return false;
 381   }
 382
 383   static ThreadInfo[] add (ThreadInfo[] list, ThreadInfo ti) {
 384     int len = list.length;
 385
 386     //--- first, check if its already there
 387     if (containsLocked(list, ti)){
 388       // this is required because interrupted parks/joins can try to
 389       // re-park/join from their respective handlers (they don't hold locks)
 390       return list;
 391     }
 392
 393     ThreadInfo[] newList = new ThreadInfo[len+1];
 394
 395     int pos = 0;
 396     for (; pos < len && ti.compareTo(list[pos]) > 0; pos++) {
 397       newList[pos] = list[pos];
 398     }
 399
 400     newList[pos] = ti;
 401     for (; pos < len; pos++) {
 402       newList[pos+1] = list[pos];
 403     }
 404
 405     return newList;
 406   }
 407
 408   void addLocked (ThreadInfo ti) {
 409     lockedThreads = add(lockedThreads, ti);
 410   }
 411
 412   static ThreadInfo[] remove (ThreadInfo[] list, ThreadInfo ti) {
 413     int len = list.length;
 414
 415     if (len == 0) { // nothing to remove from
 416       return list;
 417
 418     } else if (len == 1) {  // one element list optimization
 419       if (list[0] == ti) {
 420         return emptySet;
 421       } else {
 422         return list;
 423       }
 424     } else {
 425
 426       //--- first, check if its already there
 427       if (!containsLocked(list, ti)) {
 428         // no known case yet, but we keep it symmetric
 429         // <2do> maybe worth a warning
 430         return list;
 431       }
 432
 433       for (int i=0; i<len; i++) {
 434         if (list[i] == ti) {
 435           int newLen = len-1;
 436           ThreadInfo[] newList = new ThreadInfo[newLen];
 437           if (i > 0) {
 438             System.arraycopy(list, 0, newList, 0, i);
 439           }
 440           if (i < newLen) {
 441             System.arraycopy(list, i+1, newList, i, newLen-i);
 442           }
 443           return newList;
 444         }
 445       }
 446       // else, not in list:
 447       return list;
 448     }
 449   }
 450
 451   void removeLocked (ThreadInfo ti) {
 452     lockedThreads = remove(lockedThreads, ti);
 453   }
 454 }