1556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom/* 2556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * Copyright (C) 2011 The Android Open Source Project 3556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * 4556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * Licensed under the Apache License, Version 2.0 (the "License"); 5556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * you may not use this file except in compliance with the License. 6556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * You may obtain a copy of the License at 7556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * 8556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * http://www.apache.org/licenses/LICENSE-2.0 9556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * 10556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * Unless required by applicable law or agreed to in writing, software 11556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * distributed under the License is distributed on an "AS IS" BASIS, 12556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * See the License for the specific language governing permissions and 14556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom * limitations under the License. 15556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom */ 16556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom 17556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstromimport java.util.ArrayList; 18556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstromimport java.util.List; 1993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampeimport java.util.concurrent.BrokenBarrierException; 2093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampeimport java.util.concurrent.CyclicBarrier; 2193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampeimport java.util.concurrent.SynchronousQueue; 2293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampeimport java.util.concurrent.TimeUnit; 2393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampeimport java.util.concurrent.TimeoutException; 24556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom 251c83cbc4a817acbd7f9abb5b29a2d418a958e6a1Andreas Gampepublic class Main implements Runnable { 2693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 2793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe public final static long TIMEOUT_VALUE = 5; // Timeout in minutes. 2893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe public final static long MAX_SIZE = 1000; // Maximum size of array-list to allocate. 2993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 30556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom public static void main(String[] args) throws Exception { 31556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom Thread[] threads = new Thread[16]; 3293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 3393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Use a cyclic system of synchronous queues to pass a boolean token around. 3493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // 3593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // The combinations are: 3693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // 3793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Worker receives: true false false true 3893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Worker has OOM: false false true true 3993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // | 4093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // v 4193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Value to pass: true false false false 4293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Exit out of loop: false true true true 4393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Wait on in queue: true false false true 4493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // 4593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Finally, the workers are supposed to wait on the barrier to synchronize the GC run. 4693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 4793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe CyclicBarrier barrier = new CyclicBarrier(threads.length); 4893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe List<SynchronousQueue<Boolean>> queues = new ArrayList<SynchronousQueue<Boolean>>( 4993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe threads.length); 5093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe for (int i = 0; i < threads.length; i++) { 5193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe queues.add(new SynchronousQueue<Boolean>()); 5293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 5393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 54556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom for (int i = 0; i < threads.length; i++) { 5593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe threads[i] = new Thread(new Main(i, queues.get(i), queues.get((i + 1) % threads.length), 5693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe barrier)); 57556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 58556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom for (Thread thread : threads) { 59556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom thread.start(); 60556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 6193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 6293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Push off the cycle. 6393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe checkTimeout(queues.get(0).offer(Boolean.TRUE, TIMEOUT_VALUE, TimeUnit.MINUTES)); 6493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 6593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Wait for the threads to finish. 66556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom for (Thread thread : threads) { 67556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom thread.join(); 68556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 6993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 7093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Allocate objects to definitely run GC before quitting. 7193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe try { 7293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe for (int i = 0; i < 1000; i++) { 7393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe new ArrayList<Object>(i); 7493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 7593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } catch (OutOfMemoryError oom) { 7693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 7793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 7893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 7993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe private static void checkTimeout(Object o) { 8093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe checkTimeout(o != null); 8193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 8293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 8393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe private static void checkTimeout(boolean b) { 8493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe if (!b) { 8593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Something went wrong. 8693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe System.out.println("Bad things happened, timeout."); 8793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe System.exit(1); 8893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 89556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 90556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom 91556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom private final int id; 9293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe private final SynchronousQueue<Boolean> waitOn; 9393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe private final SynchronousQueue<Boolean> pushTo; 9493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe private final CyclicBarrier finalBarrier; 95556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom 9693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe private Main(int id, SynchronousQueue<Boolean> waitOn, SynchronousQueue<Boolean> pushTo, 9793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe CyclicBarrier finalBarrier) { 98556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom this.id = id; 9993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe this.waitOn = waitOn; 10093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe this.pushTo = pushTo; 10193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe this.finalBarrier = finalBarrier; 102556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 103556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom 104556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom public void run() { 10593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe try { 10693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe work(); 10793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } catch (Exception exc) { 10893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Any exception is bad. 10993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe exc.printStackTrace(System.err); 11093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe System.exit(1); 111556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 112556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom } 11321b4bf89b4454d2af88762200e5d8b42e0d36cf4Andreas Gampe 11493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe public void work() throws BrokenBarrierException, InterruptedException, TimeoutException { 11593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe ArrayList<Object> l = new ArrayList<Object>(); 11693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 11793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Main loop. 11893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe for (int i = 0; ; i++) { 11993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe Boolean receivedB = waitOn.poll(TIMEOUT_VALUE, TimeUnit.MINUTES); 12093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe checkTimeout(receivedB); 12193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe boolean received = receivedB; 12293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 12393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // This is the first stage, try to allocate up till MAX_SIZE. 12493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe boolean oom = i >= MAX_SIZE; 12593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe try { 12693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe l.add(new ArrayList<Object>(i)); 12793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } catch (OutOfMemoryError oome) { 12893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe oom = true; 12993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 13093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 13193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe if (!received || oom) { 13293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // First stage, always push false. 13393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe checkTimeout(pushTo.offer(Boolean.FALSE, TIMEOUT_VALUE, TimeUnit.MINUTES)); 13493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 13593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // If we received true, wait for the false to come around. 13693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe if (received) { 13793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe checkTimeout(waitOn.poll(TIMEOUT_VALUE, TimeUnit.MINUTES)); 13893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 13993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 14093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Break out of the loop. 14193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe break; 14293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } else { 14393f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Pass on true. 14493f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe checkTimeout(pushTo.offer(Boolean.TRUE, TIMEOUT_VALUE, TimeUnit.MINUTES)); 14593f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 14693f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 14793f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 14893f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // We have reached the final point. Wait on the barrier, but at most a minute. 14993f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe finalBarrier.await(TIMEOUT_VALUE, TimeUnit.MINUTES); 15093f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe 15193f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe // Done. 15293f3da1578bf25d3bc8cf1d121477bf29b4d760aAndreas Gampe } 153556217477768af1b2abf6768f007c09f226bbe7eBrian Carlstrom} 154