2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
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
10 * http://www.apache.org/licenses/LICENSE-2.0.
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.
18 package gov.nasa.jpf.vm;
20 // see mixinJPFStack() comments
21 import sun.misc.SharedSecrets;
22 import sun.misc.JavaLangAccess;
24 import gov.nasa.jpf.Config;
25 import static gov.nasa.jpf.util.OATHash.*;
28 * an AllocationContext that uses a hash value for comparison. This is
29 * lossy - heap implementations using this class have to check/handle
32 * However, given that we have very good hash data (search global object
33 * references), the probability of collisions is low enough that heap
34 * implementations might simply report this as a problem requiring a
35 * non-lossy AllocationContext.
37 * Ideally, we would like to hash the host VM thread context too (esp.
38 * for system allocations), but host VM stack traces are expensive, and it is
39 * arguable if would be too strict (e.g. when using a dedicated allocator
40 * method called from alternative branches of the caller)
42 * note - this is a HashMap key type which has to obey the hashCode/equals contract
44 public class HashedAllocationContext implements AllocationContext {
46 static final Throwable throwable = new Throwable(); // to avoid frequent allocations
48 static int mixinSUTStack (int h, ThreadInfo ti) {
49 h = hashMixin( h, ti.getId());
51 // we don't want to mixin the stack slots (locals and operands) because this would
52 // cause state leaks (different hash) if there are changed slot values that do not
53 // relate to the allocation
55 for (StackFrame frame = ti.getTopFrame(); frame != null; frame = frame.getPrevious() ) {
56 if (!(frame instanceof DirectCallStackFrame)) {
57 Instruction insn = frame.getPC();
59 //h = hashMixin(h, insn.hashCode()); // this is the Instruction object system hash - not reproducible between runs
61 h = hashMixin( h, insn.getMethodInfo().getGlobalId()); // the method
62 h = hashMixin( h, insn.getInstructionIndex()); // the position within the method code
63 h = hashMixin( h, insn.getByteCode()); // the instruction type
71 * this is an optimization to cut down on host VM StackTrace acquisition, since we just need one
74 * NOTE: this is more fragile than Throwable.getStackTrace() and String.equals() since it assumes
75 * availability of the sun.misc.JavaLangAccess SharedSecret and invariance of classname strings.
77 * The robust version would be
79 * throwable.fillInStackTrace();
80 * StackTraceElement[] ste = throwable.getStackTrace();
81 * StackTraceElement e = ste[4];
82 * if (e.getClassName().equals("gov.nasa.jpf.vm.MJIEnv") && e.getMethodName().startsWith("new")){ ..
85 static final JavaLangAccess JLA = SharedSecrets.getJavaLangAccess();
86 static final String ENV_CLSNAME = MJIEnv.class.getName();
88 // <2do> this method is problematic - we should not assume a fixed stack position
89 // but we can't just mixin the whole stack since this would cause different class object
90 // allocation contexts (registerClass can happen from lots of locations).
91 // At the other end of the spectrum, MJIEnv.newXX() is not differentiating enough since
92 // those are convenience methods used from a gazillion of places that might share
94 static int mixinJPFStack (int h) {
95 throwable.fillInStackTrace();
97 // we know the callstack is at least 4 levels deep:
99 // 1: getXAllocationContext
100 // 2: heap.getXAllocationContext
101 // 3: heap.newObject/newArray/newString
102 // 4: <allocating method>
105 // note that it is not advisable to mixin more than the immediate newX() caller since
106 // this would create state leaks for allocations that are triggered by SUT threads and
107 // have different native paths (e.g. Class object creation caused by different SUT thread context)
109 StackTraceElement e = JLA.getStackTraceElement(throwable, 4); // see note below regarding fixed call depth fragility
110 // <2do> this sucks - MJIEnv.newObject/newArray/newString are used from a gazillion of places that might not differ in SUT state
111 if (e.getClassName() == ENV_CLSNAME && e.getMethodName().startsWith("new")){
112 // there is not much use to loop, since we don't have a good end condition
113 e = JLA.getStackTraceElement(throwable, 5);
116 // NOTE - this is fragile since it is implementation dependent and differs
118 // the names are interned string from the class object
119 // h = hashMixin( h, System.identityHashCode(e.getClassName()));
120 // h = hashMixin( h, System.identityHashCode(e.getMethodName()));
122 // this should be reproducible, but the string hash is bad
123 h = hashMixin(h, e.getClassName().hashCode());
124 h = hashMixin(h, e.getMethodName().hashCode());
125 h = hashMixin(h, e.getLineNumber());
131 * !! NOTE: these always have to be at a fixed call distance of the respective Heap.newX() call:
133 * ConcreteHeap.newX()
134 * ConcreteHeap.getXAllocationContext()
135 * ConcreteAllocationContext.getXAllocationContext()
137 * that means the allocation site is at stack depth 4. This is not nice, but there is no
138 * good heuristic we could use instead, other than assuming there is a newObject/newArray/newString
143 * this one is for allocations that should depend on the SUT thread context (such as all
144 * explicit NEW executions)
146 public static AllocationContext getSUTAllocationContext (ClassInfo ci, ThreadInfo ti) {
149 //--- the type that gets allocated
150 h = hashMixin(h, ci.getUniqueId()); // ClassInfo instances can change upon backtrack
152 //--- the SUT execution context (allocating ThreadInfo and its stack)
153 h = mixinSUTStack( h, ti);
155 //--- the JPF execution context (from where in the JPF code the allocation happens)
156 h = mixinJPFStack( h);
159 HashedAllocationContext ctx = new HashedAllocationContext(h);
165 * this one is for allocations that should NOT depend on the SUT thread context (such as
166 * automatic allocation of java.lang.Class objects by the VM)
168 * @param anchor a value that can be used to provide a context that is heap graph specific (such as
169 * a classloader or class object reference)
171 public static AllocationContext getSystemAllocationContext (ClassInfo ci, ThreadInfo ti, int anchor) {
174 h = hashMixin(h, ci.getUniqueId()); // ClassInfo instances can change upon backtrack
176 // in lieu of the SUT stack, add some magic salt and the anchor
177 h = hashMixin(h, 0x14040118);
178 h = hashMixin(h, anchor);
180 //--- the JPF execution context (from where in the JPF code the allocation happens)
181 h = mixinJPFStack( h);
184 HashedAllocationContext ctx = new HashedAllocationContext(h);
189 public static boolean init (Config conf) {
190 //pool = new SparseObjVector<HashedAllocationContext>();
196 // rolled up hash value for all context components
197 protected final int id;
200 //--- instance methods
202 protected HashedAllocationContext (int id) {
207 public boolean equals (Object o) {
208 if (o instanceof HashedAllocationContext) {
209 HashedAllocationContext other = (HashedAllocationContext)o;
210 return id == other.id;
217 * @pre: must be the same for two objects that result in equals() returning true
220 public int hashCode() {
224 // for automatic field init allocations
226 public AllocationContext extend (ClassInfo ci, int anchor) {
227 //int h = hash( id, anchor, ci.hashCode());
228 int h = hashMixin(id, anchor);
229 h = hashMixin(h, ci.getUniqueId());
232 return new HashedAllocationContext(h);