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;
21 import gov.nasa.jpf.Config;
22 import gov.nasa.jpf.util.HashData;
23 import gov.nasa.jpf.util.Predicate;
25 import java.util.ArrayList;
26 import java.util.BitSet;
27 import java.util.Iterator;
28 import java.util.List;
29 import java.util.NoSuchElementException;
32 * Contains the list of all ThreadInfos for live java.lang.Thread objects
34 * We add a thread upon creation (within the ThreadInfo ctor), and remove it
35 * when the corresponding java.lang.Thread object gets recycled by JPF. This means
37 * * the thread list can contain terminated threads
38 * * terminated and recycled threads are (eventually) removed from the list
39 * * the list can shrink along a given path
40 * * thread ids don't have to correspond with storing order !!
41 * * thread ids can be re-used
43 * Per default, thread ids are re-used in order to be packed (which is required to efficiently
44 * keep track of referencing threads in ElementInfo reftids). If there is a need
45 * to avoid recycled thread ids, set 'vm.reuse_tid=false'.
47 * NOTE - this ThreadList implementation doubles up as a thread object -> ThreadInfo
48 * map, which is for instance heavily used by the JPF_java_lang_Thread peer.
50 * This implies that ThreadList is still not fully re-organized in case something
51 * keeps terminated thread objects alive. We could avoid this by having a separate
52 * map for live threads<->ThreadInfos, but this would also have to be a backrackable
53 * container that is highly redundant to ThreadList (the only difference being
54 * that terminated threads could be removed from ThreadList).
57 public class ThreadList implements Cloneable, Iterable<ThreadInfo>, Restorable<ThreadList> {
59 public static class Count {
60 public final int alive;
61 public final int runnableNonDaemons;
62 public final int runnableDaemons;
63 public final int blocked;
65 Count (int alive, int runnableNonDaemons, int runnableDaemons, int blocked){
67 this.runnableNonDaemons = runnableNonDaemons;
68 this.runnableDaemons = runnableDaemons;
69 this.blocked = blocked;
73 protected boolean reuseTid;
75 // ThreadInfos for all created but not terminated threads
76 protected ThreadInfo[] threads;
78 // the highest ID created so far along this path
82 static class TListMemento implements Memento<ThreadList> {
83 // note that we don't clone/deepcopy ThreadInfos
84 Memento<ThreadInfo>[] tiMementos;
87 TListMemento(ThreadList tl) {
88 ThreadInfo[] threads = tl.threads;
89 int len = threads.length;
92 tiMementos = new Memento[len];
93 for (int i=0; i<len; i++){
94 ThreadInfo ti = threads[i];
95 Memento<ThreadInfo> m = null;
97 if (!ti.hasChanged()){
102 ti.cachedMemento = m;
109 public ThreadList restore(ThreadList tl){
110 int len = tiMementos.length;
111 ThreadInfo[] threads = new ThreadInfo[len];
112 for (int i=0; i<len; i++){
113 Memento<ThreadInfo> m = tiMementos[i];
114 ThreadInfo ti = m.restore(null);
115 ti.cachedMemento = m;
119 tl.threads = threads;
127 protected ThreadList() {
132 * Creates a new empty thread list.
134 public ThreadList (Config config, KernelState ks) {
135 threads = new ThreadInfo[0];
137 reuseTid = config.getBoolean("vm.reuse_tid", false);
141 public Memento<ThreadList> getMemento(MementoFactory factory) {
142 return factory.getMemento(this);
144 public Memento<ThreadList> getMemento(){
145 return new TListMemento(this);
149 public Object clone() {
150 ThreadList other = new ThreadList();
151 other.threads = new ThreadInfo[threads.length];
153 for (int i=0; i<threads.length; i++) {
154 other.threads[i] = (ThreadInfo) threads[i].clone();
161 * add a new ThreadInfo if it isn't already in the list.
162 * Note: the returned id is NOT our internal storage index
164 * @return (path specific) Thread id
166 public int add (ThreadInfo ti) {
167 int n = threads.length;
169 BitSet ids = new BitSet();
170 for (int i=0; i<n; i++) {
171 ThreadInfo t = threads[i];
180 ThreadInfo[] newThreads = new ThreadInfo[n+1];
181 System.arraycopy(threads, 0, newThreads, 0, n);
186 threads = newThreads;
189 return ids.nextClearBit(0);
195 public boolean remove (ThreadInfo ti){
196 int n = threads.length;
198 for (int i=0; i<n; i++) {
199 if (ti == threads[i]){
201 ThreadInfo[] newThreads = new ThreadInfo[n1];
203 System.arraycopy(threads, 0, newThreads, 0, i);
206 System.arraycopy(threads, i+1, newThreads, i, (n1-i));
208 // update the tlIdx values
209 for (int j=i; j<n1; j++){
210 ThreadInfo t = threads[j];
217 threads = newThreads;
226 * Returns the array of threads.
228 public ThreadInfo[] getThreads() {
229 return threads.clone();
232 public void hash (HashData hd) {
233 for (int i=0; i<threads.length; i++){
238 public ThreadInfo getThreadInfoForId (int tid){
239 for (int i=0; i<threads.length; i++){
240 ThreadInfo ti = threads[i];
241 if (ti.getId() == tid){
249 public ThreadInfo getThreadInfoForObjRef (int objRef){
250 for (int i=0; i<threads.length; i++){
251 ThreadInfo ti = threads[i];
252 if (ti.getThreadObjectRef() == objRef){
260 public boolean contains (ThreadInfo ti){
263 if (idx < threads.length){
264 return threads[idx] == ti;
271 * Returns the length of the list.
273 public int length () {
274 return threads.length;
278 * Replaces the array of ThreadInfos.
280 public void setAll(ThreadInfo[] threads) {
281 this.threads = threads;
284 public ThreadInfo locate (int objref) {
285 for (int i = 0, l = threads.length; i < l; i++) {
286 if (threads[i].getThreadObjectRef() == objref) {
294 public void markRoots (Heap heap) {
295 for (int i = 0, l = threads.length; i < l; i++) {
296 if (threads[i].isAlive()) {
297 threads[i].markRoots(heap);
302 public boolean hasProcessTimeoutRunnables (ApplicationContext appCtx){
303 for (int i = 0; i < threads.length; i++) {
304 ThreadInfo ti = threads[i];
305 if (ti.isTimeoutRunnable() && ti.getApplicationContext() == appCtx) {
312 public ThreadInfo[] getProcessTimeoutRunnables (ApplicationContext appCtx){
313 ArrayList<ThreadInfo> list = new ArrayList<ThreadInfo>();
315 for (int i = 0; i < threads.length; i++) {
316 ThreadInfo ti = threads[i];
317 if (ti.isTimeoutRunnable() && ti.getApplicationContext() == appCtx) {
322 return list.toArray( new ThreadInfo[list.size()]);
325 public boolean hasLiveThreads(){
326 for (int i = 0; i < threads.length; i++) {
327 if (threads[i].isAlive()) {
334 public boolean hasTimeoutRunnables (){
335 for (int i = 0; i < threads.length; i++) {
336 if (threads[i].isRunnable()) {
343 public boolean hasUnblockedThreads(){
344 for (int i = 0; i < threads.length; i++) {
345 if (threads[i].isUnblocked()) {
352 public ThreadInfo[] getTimeoutRunnables (){
353 ArrayList<ThreadInfo> list = new ArrayList<ThreadInfo>();
355 for (int i = 0; i < threads.length; i++) {
356 ThreadInfo ti = threads[i];
357 if (ti.isTimeoutRunnable()) {
362 return list.toArray( new ThreadInfo[list.size()]);
367 public boolean hasAnyMatching(Predicate<ThreadInfo> predicate) {
368 for (int i = 0, l = threads.length; i < l; i++) {
369 if (predicate.isTrue(threads[i])) {
377 public boolean hasAnyMatchingOtherThan(ThreadInfo ti, Predicate<ThreadInfo> predicate) {
378 for (int i = 0, l = threads.length; i < l; i++) {
379 if(ti != threads[i]) {
380 if (predicate.isTrue(threads[i])) {
389 public boolean hasOnlyMatching(Predicate<ThreadInfo> predicate) {
390 for (int i = 0, l = threads.length; i < l; i++) {
391 if (!predicate.isTrue(threads[i])) {
399 public boolean hasOnlyMatchingOtherThan(ThreadInfo ti, Predicate<ThreadInfo> predicate) {
401 for (int i = 0, l = threads.length; i < l; i++) {
402 if(ti != threads[i]) {
403 if (!predicate.isTrue(threads[i])) {
414 public ThreadInfo[] getAllMatching(Predicate<ThreadInfo> predicate) {
415 List<ThreadInfo> list = new ArrayList<ThreadInfo>();
418 for (int i = 0, l = threads.length; i < l; i++) {
419 ThreadInfo ti = threads[i];
420 if (predicate.isTrue(ti)) {
426 return list.toArray(new ThreadInfo[n]);
429 public ThreadInfo[] getAllMatchingWith(final ThreadInfo ti, Predicate<ThreadInfo> predicate) {
430 List<ThreadInfo> list = new ArrayList<ThreadInfo>();
433 for (int i = 0, l = threads.length; i < l; i++) {
434 ThreadInfo t = threads[i];
435 if (predicate.isTrue(t) || (ti==t)) {
441 return list.toArray(new ThreadInfo[n]);
444 public ThreadInfo[] getAllMatchingWithout(final ThreadInfo ti, Predicate<ThreadInfo> predicate) {
445 List<ThreadInfo> list = new ArrayList<ThreadInfo>();
448 for (int i = 0, l = threads.length; i < l; i++) {
449 ThreadInfo t = threads[i];
450 if (predicate.isTrue(t) && (ti != t)) {
456 return list.toArray(new ThreadInfo[n]);
459 public int getMatchingCount(Predicate<ThreadInfo> predicate) {
461 for (int i = 0, l = threads.length; i < l; i++) {
462 ThreadInfo ti = threads[i];
463 if (predicate.isTrue(ti)) {
471 public ThreadInfo getFirstMatching(Predicate<ThreadInfo> predicate) {
472 for (int i = 0, l = threads.length; i < l; i++) {
473 ThreadInfo t = threads[i];
474 if (predicate.isTrue(t)) {
482 public Count getCountWithout (ThreadInfo tiExclude){
483 int alive=0, runnableNonDaemons=0, runnableDaemons=0, blocked=0;
485 for (int i = 0; i < threads.length; i++) {
486 ThreadInfo ti = threads[i];
488 if (ti != tiExclude){
492 if (ti.isRunnable()) {
496 runnableNonDaemons++;
505 return new Count(alive, runnableNonDaemons, runnableDaemons, blocked);
508 public Count getCount(){
509 return getCountWithout(null);
512 public void dump () {
514 for (ThreadInfo t : threads) {
515 System.err.println("[" + i++ + "] " + t);
520 public Iterator<ThreadInfo> iterator() {
521 return new Iterator<ThreadInfo>() {
525 public boolean hasNext() {
526 return threads != null && threads.length>0 && i<threads.length;
530 public ThreadInfo next() {
531 if (threads != null && threads.length>0 && i<threads.length){
534 throw new NoSuchElementException();
539 public void remove() {
540 throw new UnsupportedOperationException("Iterator<ThreadInfo>.remove()");
546 class CanonicalLiveIterator implements Iterator<ThreadInfo> {
551 CanonicalLiveIterator(){
555 // <2do> not overly efficient, but we assume small thread lists anyways
557 int lastGid = nextGid;
558 int nextGid = Integer.MAX_VALUE;
561 for (int i=0; i<threads.length; i++){
562 ThreadInfo ti = threads[i];
564 int gid = ti.getGlobalId();
565 if ((gid > lastGid) && (gid < nextGid)){
572 CanonicalLiveIterator.this.nextGid = nextGid;
573 CanonicalLiveIterator.this.nextIdx = nextIdx;
577 public boolean hasNext() {
578 return (nextIdx >= 0);
582 public ThreadInfo next() {
584 ThreadInfo tiNext = threads[nextIdx];
589 throw new NoSuchElementException();
594 public void remove() {
595 throw new UnsupportedOperationException("Iterator<ThreadInfo>.remove()");
600 * an iterator for a canonical order over all live threads
602 public Iterator<ThreadInfo> canonicalLiveIterator(){
603 return new CanonicalLiveIterator();
608 * only for debugging purposes, this is expensive
610 public void checkConsistency(boolean isStore) {
611 for (int i = 0; i < threads.length; i++) {
612 ThreadInfo ti = threads[i];
614 ti.checkConsistency(isStore);