1 /*
2  * Copyright (C) 2011 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 import java.util.ArrayList;
18 import java.util.List;
19 import java.util.concurrent.BrokenBarrierException;
20 import java.util.concurrent.CyclicBarrier;
21 import java.util.concurrent.SynchronousQueue;
22 import java.util.concurrent.TimeUnit;
23 import java.util.concurrent.TimeoutException;
24 
25 public class Main implements Runnable {
26 
27     public final static long TIMEOUT_VALUE = 5;  // Timeout in minutes.
28     public final static long MAX_SIZE = 1000;  // Maximum size of array-list to allocate.
29 
main(String[] args)30     public static void main(String[] args) throws Exception {
31         Thread[] threads = new Thread[16];
32 
33         // Use a cyclic system of synchronous queues to pass a boolean token around.
34         //
35         // The combinations are:
36         //
37         // Worker receives:    true     false    false    true
38         // Worker has OOM:     false    false    true     true
39         //    |
40         //    v
41         // Value to pass:      true     false    false    false
42         // Exit out of loop:   false    true     true     true
43         // Wait on in queue:   true     false    false    true
44         //
45         // Finally, the workers are supposed to wait on the barrier to synchronize the GC run.
46 
47         CyclicBarrier barrier = new CyclicBarrier(threads.length);
48         List<SynchronousQueue<Boolean>> queues = new ArrayList<SynchronousQueue<Boolean>>(
49             threads.length);
50         for (int i = 0; i < threads.length; i++) {
51             queues.add(new SynchronousQueue<Boolean>());
52         }
53 
54         for (int i = 0; i < threads.length; i++) {
55             threads[i] = new Thread(new Main(i, queues.get(i), queues.get((i + 1) % threads.length),
56                                              barrier));
57         }
58         for (Thread thread : threads) {
59             thread.start();
60         }
61 
62         // Push off the cycle.
63         checkTimeout(queues.get(0).offer(Boolean.TRUE, TIMEOUT_VALUE, TimeUnit.MINUTES));
64 
65         // Wait for the threads to finish.
66         for (Thread thread : threads) {
67             thread.join();
68         }
69 
70         // Allocate objects to definitely run GC before quitting.
71         try {
72             for (int i = 0; i < 1000; i++) {
73                 new ArrayList<Object>(i);
74             }
75         } catch (OutOfMemoryError oom) {
76         }
77     }
78 
checkTimeout(Object o)79     private static void checkTimeout(Object o) {
80         checkTimeout(o != null);
81     }
82 
checkTimeout(boolean b)83     private static void checkTimeout(boolean b) {
84         if (!b) {
85             // Something went wrong.
86             System.out.println("Bad things happened, timeout.");
87             System.exit(1);
88         }
89     }
90 
91     private final int id;
92     private final SynchronousQueue<Boolean> waitOn;
93     private final SynchronousQueue<Boolean> pushTo;
94     private final CyclicBarrier finalBarrier;
95 
Main(int id, SynchronousQueue<Boolean> waitOn, SynchronousQueue<Boolean> pushTo, CyclicBarrier finalBarrier)96     private Main(int id, SynchronousQueue<Boolean> waitOn, SynchronousQueue<Boolean> pushTo,
97         CyclicBarrier finalBarrier) {
98         this.id = id;
99         this.waitOn = waitOn;
100         this.pushTo = pushTo;
101         this.finalBarrier = finalBarrier;
102     }
103 
run()104     public void run() {
105         try {
106             work();
107         } catch (Exception exc) {
108             // Any exception is bad.
109             exc.printStackTrace(System.err);
110             System.exit(1);
111         }
112     }
113 
work()114     public void work() throws BrokenBarrierException, InterruptedException, TimeoutException {
115         ArrayList<Object> l = new ArrayList<Object>();
116 
117         // Main loop.
118         for (int i = 0; ; i++) {
119           Boolean receivedB = waitOn.poll(TIMEOUT_VALUE, TimeUnit.MINUTES);
120           checkTimeout(receivedB);
121           boolean received = receivedB;
122 
123           // This is the first stage, try to allocate up till MAX_SIZE.
124           boolean oom = i >= MAX_SIZE;
125           try {
126             l.add(new ArrayList<Object>(i));
127           } catch (OutOfMemoryError oome) {
128             oom = true;
129           }
130 
131           if (!received || oom) {
132             // First stage, always push false.
133             checkTimeout(pushTo.offer(Boolean.FALSE, TIMEOUT_VALUE, TimeUnit.MINUTES));
134 
135             // If we received true, wait for the false to come around.
136             if (received) {
137               checkTimeout(waitOn.poll(TIMEOUT_VALUE, TimeUnit.MINUTES));
138             }
139 
140             // Break out of the loop.
141             break;
142           } else {
143             // Pass on true.
144             checkTimeout(pushTo.offer(Boolean.TRUE, TIMEOUT_VALUE, TimeUnit.MINUTES));
145           }
146         }
147 
148         // We have reached the final point. Wait on the barrier, but at most a minute.
149         finalBarrier.await(TIMEOUT_VALUE, TimeUnit.MINUTES);
150 
151         // Done.
152     }
153 }
154