01: //
02: // Copyright (C) 2005 United States Government as represented by the
03: // Administrator of the National Aeronautics and Space Administration
04: // (NASA). All Rights Reserved.
05: //
06: // This software is distributed under the NASA Open Source Agreement
07: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
08: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
09: // 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.search.heuristic;
20:
21: import gov.nasa.jpf.Config;
22: import gov.nasa.jpf.VM;
23: import gov.nasa.jpf.jvm.TrailInfo;
24:
25: /**
26: * Heuristic to maximize thread interleavings. It is particularly good at
27: * flushing out concurrency errors, since it schedules different threads
28: * as much as possible.
29: *
30: */
31: public class Interleaving implements Heuristic {
32: private int[] threads;
33: HeuristicSearch search;
34: VM vm;
35: int threadHistoryLimit;
36:
37: public Interleaving(Config config, HeuristicSearch hSearch) {
38: vm = hSearch.getVM();
39: search = hSearch;
40:
41: threadHistoryLimit = config.getInt(
42: "search.heuristic.thread_history_limit", -1);
43: }
44:
45: public int heuristicValue() {
46: int aliveThreads = vm.getAliveThreadCount();
47:
48: int lastRun = ((TrailInfo) vm.getLastTransition()).getThread();
49: int h_value = 0;
50:
51: if (aliveThreads > 1) {
52: for (int i = 0; i < threads.length; i++) {
53: if (lastRun == threads[i]) {
54: h_value += ((threads.length - i) * aliveThreads);
55: }
56: }
57: }
58:
59: int newSize = threads.length + 1;
60:
61: if ((threadHistoryLimit > 0) && (newSize > threadHistoryLimit)) {
62: newSize = threadHistoryLimit;
63: }
64:
65: int[] newThreads = new int[newSize];
66: newThreads[0] = lastRun;
67:
68: for (int i = 1; i < newSize; i++) {
69: newThreads[i] = threads[i - 1];
70: }
71:
72: search.getNew().otherData = newThreads;
73:
74: return h_value;
75: }
76:
77: public void processParent() {
78: Object oldValue = search.getOld().otherData;
79:
80: if (oldValue == null) {
81: threads = new int[0];
82: } else {
83: threads = (int[]) oldValue;
84: }
85: }
86: }
|