StatisticFieldLockInfo


1   //
2   // Copyright (C) 2005 United States Government as represented by the
3   // Administrator of the National Aeronautics and Space Administration
4   // (NASA).  All Rights Reserved.
5   // 
6   // This software is distributed under the NASA Open Source Agreement
7   // (NOSA), version 1.3.  The NOSA has been approved by the Open Source
8   // Initiative.  See the file NOSA-1.3-JPF at the top of the distribution
9   // directory tree for the complete NOSA document.
10  // 
11  // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
12  // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
13  // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
14  // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
15  // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
16  // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
17  // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
18  //
19  package gov.nasa.jpf.jvm;
20  import java.util.List  ;
21  import gov.nasa.jpf.util.Debug;
22  import java.util.BitSet  ;
23  
24  /**
25   * a FieldLockSet implementation with the following strategy
26   *   - at each check, store the intersection of the current threads lock set
27   *     with the previous field lock set
28   *   - if the access was checked less than CHECK_THRESHOLD times, report the
29   *     field as unprotected
30   *   - if the field lock set doesn't become empty after CHECK_THRESHOLD, report
31   *     the field as protected
32   *
33   *   - as an optimization, raise the check level above the threshold if we
34   *     have a good probability that a current lock is a protection lock for this
35   *     field
36   */
37  
38  public class StatisticFieldLockInfo extends FieldLockInfo {
39    final static int CHECK_THRESHOLD = 5;
40    
41    int[] lset;
42    int checkLevel;
43    
44    // just a debugging tool
45    static String   printLocks (int[] lockSet) {
46      DynamicArea heap = DynamicArea.getHeap();
47      
48      if ((lockSet == null) || (lockSet.length == 0)) {
49        return "{}";
50      } else {
51        StringBuffer   sb = new StringBuffer  ();
52        sb.append("{");
53        for (int i=0; i<lockSet.length;) {
54          int ref = lockSet[i];
55          if (ref != -1) {
56            ElementInfo ei = heap.get(ref);
57            if (ei != null) {
58              sb.append(ei);
59            } else {
60              sb.append("?@");
61              sb.append(lockSet[i]);
62            }
63          }
64          i++;
65          if (i<lockSet.length) sb.append(',');
66        }
67        sb.append("}");
68        return sb.toString();
69      }
70    }
71    
72    void lockAssumptionFailed (ElementInfo ei, FieldInfo fi, ThreadInfo ti) {
73      String   src = ti.getMethod().getClassInfo().getSourceFileName();
74      int line = ti.getLine();
75      
76      Debug.println(Debug.ERROR,"MESSAGE: unprotected field access of: " +
77                      ei + "." + fi.getName() + " in thread:"
78                      + " \"" + ti.getName() + "\" " + src+  ":" + line);
79      Debug.println(Debug.ERROR,"   sync-detection assumed to be protected by: "
80                      + printLocks(lset));
81      Debug.println(Debug.ERROR,"   found to be protected by: "
82                      + printLocks(ti.getLockedObjectReferences()));
83      Debug.println(Debug.ERROR,"   >>> re-run without '-sync-detection' <<<");
84    }
85    
86    /**
87     * check if the current thread lockset contains a lock with a high probability
88     * that it is a protection lock for this field. We need this to avoid
89     * state explosion due to the number of fields to check. Note that we don't
90     * necessarily have to answer/decide which one is the best match in case of
91     * several candidates (if we don't use this to reduce to StatisticFieldLockInfo1)
92     *
93     * For instance fields, this would be a lock with a distance <= 1.
94     * For static fields, the corresponding class object is a good candidate.
95     */
96    static ElementInfo strongProtectionCandidate (ElementInfo ei, FieldInfo fi, ThreadInfo ti) {
97      List   currentLocks = ti.getLockedObjects();
98      int n = currentLocks.size();
99      
100     if (fi.isStatic()) { // static field, check for class object locking
101       ClassInfo ci = fi.getClassInfo();
102       int cref = ci.getClassObjectRef();
103       
104       for (int i=0; i<n; i++) {
105         ElementInfo e = (ElementInfo)currentLocks.get(i); // the locked object
106         if (e.getIndex() == cref) {
107           Debug.print(Debug.MESSAGE, "sync-detection: ");
108           Debug.print(Debug.MESSAGE, ei);
109           Debug.print(Debug.MESSAGE, " assumed to be synced on class object: ");
110           Debug.println(Debug.MESSAGE, e);
111           return e;
112         }
113       }
114       
115     } else { // instance field, use lock distance as a heuristic
116       for (int i=0; i<n; i++) {
117         ElementInfo e = (ElementInfo)currentLocks.get(i); // the locked object
118         int eidx = e.getIndex();
119         
120         // case 1: synchronization on field owner itself
121         if (ei == e) {
122           Debug.print(Debug.MESSAGE, "sync-detection: ");
123           Debug.print(Debug.MESSAGE, ei);
124           Debug.println(Debug.MESSAGE, " assumed to be synced on itself");
125           return e;
126         }
127         
128         // case 2: synchronization on owner of object holding field (sync wrapper)
129         if (e.hasRefField(ei.getIndex())) {
130           Debug.print(Debug.MESSAGE, "sync-detection: ");
131           Debug.print(Debug.MESSAGE, ei);
132           Debug.print(Debug.MESSAGE, " assumed to be synced on object wrapper: ");
133           Debug.println(Debug.MESSAGE, e);
134           return e;
135         }
136         
137         // case 3: synchronization on sibling field that is a private lock object
138         if (ei.hasRefField(eidx)) {
139           Debug.print(Debug.MESSAGE, "sync-detection: ");
140           Debug.print(Debug.MESSAGE, ei);
141           Debug.print(Debug.MESSAGE, " assumed to be synced on sibling: ");
142           Debug.println(Debug.MESSAGE, e);
143           return e;
144         }
145       }
146     }
147     
148     return null;
149   }
150   
151   public FieldLockInfo checkProtection (ElementInfo ei, FieldInfo fi, ThreadInfo ti) {
152     List   currentLocks = ti.getLockedObjects();
153     int n = currentLocks.size();
154     
155     checkLevel++;
156     if (checkLevel == 1) { // first time, not checked before
157       if (n == 0) {
158 //System.out.println("@ no lock active: " + ei);
159         return empty;
160       } else {
161         ElementInfo lcei = strongProtectionCandidate(ei,fi,ti);
162         if (lcei != null) {
163 //System.out.println("@ strong prot-lock candidate for: " + ei + " is: " + lcei);
164           // we could also turn it into a StaticFieldLockInfo1 here
165           checkLevel = CHECK_THRESHOLD;
166         }
167 
168         if (n == 1) {
169           // Ok, let's simplify this, no need to waste all the memory
170           return new StatisticFieldLockInfo1(ei, fi, ti, checkLevel);
171         }
172       
173         lset = new int[n];
174         for (int i=0; i<n; i++) {
175           ElementInfo lei = (ElementInfo) currentLocks.get(i);
176           lset[i] = lei.getIndex();
177         }
178       }
179 
180     } else {  // already checked this before
181       if (n == 0) {
182         lockAssumptionFailed(ei, fi, ti);
183         return empty;
184       } else {
185         int i, j;
186         BitSet   active = new BitSet  (lset.length);
187         
188         for (i=0; i<n; i++) {
189           ElementInfo lei = (ElementInfo)currentLocks.get(i);
190           int leidx = lei.getIndex();
191           
192           // unfortunately, we can't shortcut since we have to nullify all
193           // lock refs that are not in the current intersection (which has
194           // to be accumulative)
195           for (j=0; j<lset.length; j++) {
196             if (lset[j] == leidx) {
197               active.set(j);
198             }
199           }
200           
201           int nActive = active.size();
202           if (nActive == 0) {
203             lockAssumptionFailed(ei, fi, ti);
204             return empty;
205           } else {
206             for (j=0; j<lset.length; j++) {
207               if (!active.get(j)) {
208                 lset[j] = -1;
209               }
210             }
211           }
212         }
213       }
214     }
215     
216     return this;
217   }
218   
219   public boolean isProtected () {
220 //System.out.println("@ isProtected: " + (checkLevel >= CHECK_THRESHOLD));
221     return (checkLevel >= CHECK_THRESHOLD);
222   }
223 }
224 
225 /**
226  * private optimization for the trivial case of single locks. We definitely don't
227  * want to allocate int[] and long[] (BitSet) objects to store a single ref!
228  */
229 class StatisticFieldLockInfo1 extends FieldLockInfo {
230   int lock;
231   boolean active;
232   int checkLevel;
233   
234   StatisticFieldLockInfo1 (ElementInfo ei, FieldInfo fi, ThreadInfo ti, int nChecks) {
235     List   currentLocks = ti.getLockedObjects();
236     
237     lock = ((ElementInfo)currentLocks.get(0)).getIndex();
238     active = true;
239     this.checkLevel = nChecks;
240   }
241   
242   void lockAssumptionFailed (ElementInfo ei, FieldInfo fi, ThreadInfo ti) {
243     String   src = ti.getMethod().getClassInfo().getSourceFileName();
244     int line = ti.getLine();
245     
246     Debug.println(Debug.ERROR,"Warning: unprotected field access of: " +
247                     ei + "." + fi.getName() + " in thread:"
248                     + " \"" + ti.getName() + "\" " + src+  ":" + line);
249     Debug.println(Debug.ERROR,"   sync-detection assumed to be protected by: "
250                     + DynamicArea.getHeap().get(lock));
251     Debug.println(Debug.ERROR,"   found to be protected by: "
252                     + StatisticFieldLockInfo.printLocks(ti.getLockedObjectReferences()));
253     Debug.println(Debug.ERROR,"   >>> re-run without '-sync-detection' <<<");
254   }
255   
256   public FieldLockInfo checkProtection (ElementInfo ei, FieldInfo fi, ThreadInfo ti) {
257     List   currentLocks = ti.getLockedObjects();
258     int n = currentLocks.size();
259     
260     checkLevel++;
261     active = false;
262     for (int i=0; i<n; i++) {
263       ElementInfo lei = (ElementInfo)currentLocks.get(i);
264       if (lei.getIndex() == lock) {
265         active = true;
266         break;
267       }
268     }
269     
270     if (!active) {
271       if (checkLevel > StatisticFieldLockInfo.CHECK_THRESHOLD) {
272         lockAssumptionFailed(ei, fi, ti);
273       }
274       return empty;
275     }
276     
277     return this;
278   }
279   
280   public boolean isProtected () {
281 //System.out.println("@ isProtected1: " + (checkLevel >= StatisticFieldLockInfo.CHECK_THRESHOLD));
282     return (checkLevel >= StatisticFieldLockInfo.CHECK_THRESHOLD);
283   }
284 }
285
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags