Java Puzzle 3: Car - Solution

Mar 04, 2012

Let's see how we can get the upgraded car to break the speed limit. Take a closer look at the car:

package car;

public final class Car {
    private final int MAX_SPEED = 100;

    private int speed = 0;

    public synchronized void accelerate(int acceleration) {
        speed += acceleration;
        if (speed > MAX_SPEED)
            crash();
    }

    public synchronized void crash() {
        speed = 0;
    }

    public synchronized void vroom() {
        if (speed > MAX_SPEED * 10) {
            // The goal is to reach this line
            System.out.println("Vroom!");
        }
    }
}

Lesson to all you racers out there: We want the car to accelerate a lot (speed += acceleration must execute), but not do that thing where it hits the tree and comes to a full stop (speed = 0 must not execute).

What can happen between those two statements? The if (speed > MAX_SPEED) doesn't help us any further, because speed really needs to be higher than MAX_SPEED. So all that's left is the call to the crash() method. That one has to fail: We want crash() to crash!

We can do that by making sure there's not enough space left on the stack to be able to call any method. If the stack is almost full when we call accelerate, we get a StackOverflowError on the call to crash(). How do we get the stack to be almost full? One way is to just brute-force it: an infinitely recursing method that just keeps trying.

package driver;

import car.Car;

public class Driver {
	private static Car car = new Car();

	public static void main(String args[]) {
		try {
			recurse();
		} catch (StackOverflowError e) {
		}

		car.vroom();
	}

	public static void recurse() {
		car.accelerate(1001);
		recurse();
	}
}

And that works!... On some systems at least. A problem here is that if you're trying to accelerate so much and keep on crashing (after 1500 crashes on my system), the JVM does something no car maker ever would: it optimizes the car to ensure it can crash really fast. It in-lines the call to crash(), reducing it to essentially if (speed > MAX_SPEED) speed = 0;. That eliminates the possibility of a StackOverflowError.

We can work around that by being just a little gentler on the car: crash it a bit less, so the JVM doesn't decide to optimise that. First grow the stack until it's getting close to where it needs to be, and only then add the car into the equation. But the only way to know you're getting close to the limit is by hitting it. Therefor we recurse without the car until we hit the stack overflow, then take a few steps back, and then apply the brute-forcing solution from above:

package driver;

import car.Car;

public class Driver {
    static Car car = new Car();
    static int a = 0;

    public static void main(String args[]) {
        recurse();
        car.vroom();
    }

    static void recurse() {
        try {
            recurse(); // recurse without the car
        } catch (StackOverflowError e) {
            // when we've hit the limit of the stack, just go back out
        }
        if (a++ == 10) { // after taking 10 steps back
            recurse2(); // recurse with the car
        }
    }

    static void recurse2() {
        car.accelerate(1001);
        recurse2();
    }
}

An alternative solution is to use Thread.stop. But it's quite hard to time it right; it doesn't work that reliable across systems. At first I expected it to be impossible in practice, but I was proven wrong. You can see the code in the comments below.
You do need a special permission to call that method, but that's one of the very few things included in the default security policy file. The only other permissions in there are opening listening sockets on high ports, and reading some standard system properties.

Conclusion

Not many succeeded in solving this one. The ones who did, and their solutions can be admired below as time-travelling comments that were posted before this blog post appeared.

The fact that this hack is possible makes me wonder. Is all privileged code in Java itself really prepared to crash at any time? Including all native code? If an applet makes the loading of a class fail in this way; does that cause NoClassDefFoundErrors in other applets? How else could this be abused?...

Please, don't try this at home. Car insurance usually doesn't cover the failing of the crashing of the crash. Even if you first tried crashing without the car; running with your head straight into the tree. Blowing up the car right before it hits the tree is not appreciated either.

In the next puzzle we'll sneak some goods passed airport security, so stay tuned!

26 comments

Jarl Petter Kvalsvik wrote on 2012-03-01 16:00

The solution was quite simple - recurse util stack overflows - then the crach method will not have been called

package driver;

import car.Car;

public class Driver {

    private static void recurse(Car c)
    {
        try {
            c.accelerate(1001);
            recurse(c);
        } catch (StackOverflowError e)
        {
        }
    }

    public static void main(String args[]) {
        // TODO break the speed limit
        Car car = new Car();
        recurse(car);
        car.vroom();
    }
}

Paul Martin wrote on 2012-03-01 16:37

Had me stumped for a while (and made me look in Thread Javadoc for some clues).

package driver;

import car.Car;

public class Driver {
    public static void main(String args[]) {
        final Car car = new Car();
        new Thread(null, new Runnable() {
            int depth = 0;
            @Override
            public void run() {
                try {    // Count number of stack frames available
                    calcStackDepth(depth);
                } catch (StackOverflowError e) { ; }
                try {    // Then almost fill up the stack before calling accelerate
                    fillStackThenAccelerate(depth);
                } catch (StackOverflowError e) { ; }
                car.vroom();
            }

            private void calcStackDepth(int i) {    // Ignore parameter, but means same arg size as accelerate
                depth++;
                calcStackDepth(depth);
            }
            private void fillStackThenAccelerate(int i) {
                i--;
                if (i > 1) {
                    fillStackThenAccelerate(i);
                } else {
                    car.accelerate(Integer.MAX_VALUE);
                }
            }
        }, "test", 128L).run();
    }
}

Wouter wrote on 2012-03-04 21:34

Looking at this with javap (javap -c -v -private 'driver.Driver$1') shows that calcStackDepth has a stack size of 3, but fillStackThenAccelerate only 2. That’s because it keeps “this”, “depth” and “1” (to increment depth++ by one) on the stack at the same time. So it doesn’t predict the stack depth entirely correctly. I’m not sure it’s off by enough to make a difference, but Heinz told me your solution didn’t work on his system (while my version did), so I guess it does matter.

Barry V wrote on 2012-03-01 18:23

package driver;

import car.Car;

public class Driver {

    private static Car car = new Car();

    public static void recursiveAcceleration(int depth) {
        car.accelerate(1001);
        recursiveAcceleration(depth);
    }

    public static void main(String args[]) {
        try {
            recursiveAcceleration(0);
        } catch (StackOverflowError soe) {
            car.vroom();
        }
    }
}

Heinz Kabutz wrote on 2012-03-01 20:17

Ok, this one was tough. I did not manage to solve it before, so this is a new one for me too. I’ve solved it, as you can see in the log, but this does not always run. Another way I thought might work would be to almost exhaust the stack space and then call the accelerate method, making it crash when it is about to call crash(). But that did not work.

package driver;

import car.*;

import java.util.*;

public class Driver {
  static volatile boolean running = true;

  public static void main(String args[]) throws InterruptedException {
    Timer timer = new Timer(true);
    timer.schedule(new TimerTask() {
      public void run() {
        running = false;
      }
    }, 9000);

    final long time = System.currentTimeMillis();

    final Throwable ex = new ThreadDeath();
    final Car car = new Car();
    for (int i = 0; i < 10; i++) {
      Thread vroomThread = new Thread() {
        public void run() {
          while (running) {
            car.vroom();
          }
        }
      };
      vroomThread.start();
    }

    while (running) {
      Thread thread = new Thread() {
        public void run() {
          while (running) {
            try {
              final Thread thread = Thread.currentThread();
              while (running) {
                try {
                  while (running) {
                    car.accelerate(10000);
                  }
                } catch (Throwable ex) {
                  synchronized (thread) {
                    System.out.println("bust");
                  }
                }
              }
            } catch (Throwable e) {
            }
          }
        }
      };

      System.out.println(thread);
      thread.start();

      while (thread.isAlive()) {
        synchronized (thread) {
          while (thread.isAlive() && thread.getState() != Thread.State.BLOCKED) {
            thread.stop(ex);
          }
          car.vroom();
        }
      }
      thread.join();
    }

    System.out.println("Goodbye");
  }
}

mihi wrote on 2012-03-01 22:55

Nice one :)

This one works reliably on my machine (gives me between 2 and 7 Vroom! on every execution), but does not work at all on your server (tried it a few times). But I guess it just needs some more tweaking :-)

BTW I was surprised that Thread#stop() is not blocked by the security manager.

package driver;

import car.Car;

public class Driver {
    public static void main(String args[]) throws Throwable {
        Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
        final Car car = new Car();
        for (int j = 0; j < 1000; j++) {
            final boolean[] flag = new boolean[1];
            Thread t = new Thread(new Runnable() {
                public void run() {
                    synchronized(car) {
                        try {
                            flag[0] = true;
                            car.notifyAll();
                            car.wait();
                            while(true) {
                                car.accelerate(1001);
                            }
                        } catch (InterruptedException ex) {
                            ex.printStackTrace();
                        }
                    }
                }
            });
            t.start();
            synchronized(car) {
                while (!flag[0])
                    car.wait();
                car.notifyAll();
                t.stop();
            }
            t.join();
            car.vroom();
            Thread.yield();
        }
    }
}

deadalnix wrote on 2012-03-04 19:56

I had a similar solution, but it wasn’t very reliable.

t.stop() is known to be a misfeature that most should not use. The posted solution is way smarter and more reliable. I didn’t thought about it.

I didn’t consider I had a solution either with that one, as it rely on luck.

mihi wrote on 2012-03-05 19:42

Most things here in the Java puzzlers is about exploiting misfeatures (like recursing in hashCode() or calling wait() without a loop. And maybe the reason I posted it anyway was (1) that hint on the webpage that it might not be possible to do this reliably on some environments, and (2) the fact that I am too much involved in information security, where you are “the hero” if you find an exploit that exploits a memory corruption vulnerability or a race condition like this one in 10% of the cases (although that depends on luck too) - even if there is another way to exploit it with 100% reliability like in this case …

The other problem might be that once I find a solution I usually don’t try to find a better one and since the security manager allowed me to stop() that thread, I submitted it like this.

Just to make it clear, I also believe that Wouter’s solution is far superior to this one.

Martin wrote on 2012-03-02 01:39

Works on mine machine and on test page. Pretty sure it won’t work somewhere else, though by using initial probe and minimum count of iterations it could work on couple of other machines too ;)

package driver;

import car.Car;

public class Driver {
    private static Car car;
    private static int probeResult;

    public static void callRecursiveProbe(int recursionLevel) {
        probeResult = recursionLevel + 1;
        callRecursiveProbe(recursionLevel + 1);
    }

    public static void callRecursive(int recursionLevel) {
        if (recursionLevel > 1) {
            callRecursive(recursionLevel - 1);
        } else  {
            car.accelerate(1001);
        }
    }

    public static void main(String args[]) {
        car = new Car();
        try {
            callRecursiveProbe(1);
        } catch (StackOverflowError soe) {}
        int recursionLevel = probeResult - 3;
        while (true) {
            try {
                callRecursive(recursionLevel);
                recursionLevel++;
            } catch (StackOverflowError ser) {
                break;
            }
        }

        car.vroom();
    }
}

Martin wrote on 2012-03-02 01:49

To be more specific, we want to avoid crash() being inlined by JIT, so it should not be called many times, ideally just once and have stackoverflow exactly at that point.. though that is most likely really platform specific so getting exactly the point is not so easy that’s why we have the second iteration there with hope we’re +/- around the right depth and hence we can hit SOE before JIT.

Solf wrote on 2012-03-02 11:31

The below works pretty reliable on my box. But of course it’s kind of ‘luck based’ and your sandbox puts limit on duration so can’t increase iterations.

The obvious idea is to stop thread after it increases the speed, but before it does crash().

It probably can be finessed more (with putting high load on CPU via other threads and setting low priority on executing thread and introducing some waits and stuff). But overall this solution is still luck-based and silly.

I’ll wait and see if someone’ll come with non-luck-based solution :)

package driver;

import car.Car;

public class Driver {
    public static void main(String args[]) {
        // TODO break the speed limit
        final Car car = new Car();
        for (int i = 0; i < 100000; i++)
        {
            Thread t = new Thread()
            {
                /* (non-Javadoc)
                 * @see java.lang.Thread#run()
                 */
                @Override
                public void run()
                {
                    car.accelerate(100000);
                }
            };
            t.start();
            t.stop();
            car.vroom();
        }
    }
}

Alexander Rathai wrote on 2012-03-02 17:10

Couldn’t get it to work reliably on my machine But this could work because of Thread.stop() releasing the monitors… The trick is to stop the thread right after adding to speed but before crash() beeing invoked.

package driver;

import car.*;

public class Driver {
    public static void main(String args[]) {
        // TODO break the speed limit
        final Car car = new Car();
        new Thread(){
            /**
             * @see java.lang.Thread#run()
             */
            @Override
            public void run() {
                /*
                 * end the misery after 10 seconds of pain : )
                 */
                try {
                    Thread.sleep(10000L);
                }
                catch( InterruptedException e ) {
                }
                System.exit(0);
            }
        }.start();
        int i = 0;
        Thread[] threads = new Thread[11];
        while(true){
            threads[i++] = new Thread(){
                @Override
                public void run() {
                    try {
                        Thread.sleep(10L);
                    }
                    catch( InterruptedException e ) {
                    }
                    car.accelerate(100);
                }
            };
            if( i % threads.length == 0 ) {
                synchronized( car ) {
                    for( int j = 0; j < threads.length; j++ ) {
                        threads[j].start();
                    }
                    car.notifyAll();
                }
                for( int j = 0; j < threads.length; j++ ) {
                    threads[j].stop();
                }
                car.vroom();
                i = 0;
            }
        }
    }
}

Dirk wrote on 2012-03-02 21:44

Not really nice and reliable, but seems to work better with you server:

package driver;

import car.Car;

public class Driver {

    private final static Car car = new Car();
    private final static Object trigger = new Object();
    private static Thread t1;
    private static int i = 0;

    public static void main(String args[]) {

        Thread killer = new Thread() {
            @Override
            public void run() {
                while (true)
                    synchronized (trigger) {
                        try {
                            trigger.wait(0, i);
                        } catch (InterruptedException e) {
                            // TODO Auto-generated catch block
                            e.printStackTrace();
                        }
                        t1.stop();
                        t1.interrupt();
                    }
            }
        };
        killer.setDaemon(true);
        killer.start();

        for (i = 1; i < 100; i++) {

            t1 = new Thread() {
                @Override
                public void run() {
                    while (true) {
                        car.accelerate(-1);
                        car.accelerate(Integer.MIN_VALUE);
                    }
                }
            };
            t1.setPriority(Thread.MIN_PRIORITY);
            t1.start();

            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }

            try {
                t1.join();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            car.vroom();
        }
    }
}

mbartmann wrote on 2012-03-02 22:42

package driver;

import car.Car;

public class Driver {

    private static Car car;

    public static void main(String args[]) {
        // TODO break the speed limit
        car = new Car();
        deepAccelerate();
        car.vroom();
    }

    private static void deepAccelerate() {
        try {
            car.accelerate(1001);
            deepAccelerate();
        } catch (StackOverflowError e) {
        }
    }
}

Algirdas wrote on 2012-03-02 23:48

package driver;

import java.util.concurrent.CountDownLatch;

import car.Car;

public class Driver {
  public static void main(String args[]) throws InterruptedException {
    for (int i = 0; i < 500; i++) {
      final CountDownLatch latch = new CountDownLatch(1);
      final Car car = new Car();

      Thread thread = new Thread() {
        public void run() {
          latch.countDown();
          while (true) {
            car.accelerate(1001);
          }
        }
      };
      thread.start();

      latch.await();
      thread.stop();

      thread.join();
      car.vroom();
    }
  }
}

David Shay wrote on 2012-03-03 09:20

Here is my solution. It works only if you disable all optimization from the JVM, by using the -Xint parameter:

package driver;

import car.Car;

public class Driver {
    private static final Car car = new Car();
    public static void main(String args[]) {
        try {
            new Driver().circuitRun();
        }
        catch (StackOverflowError e) {}
        car.vroom();
    }

    private void circuitRun() {
        car.accelerate(1001);
        circuitRun();
    }
}

Booboo wrote on 2012-03-03 13:29

Here is my solution. You may have to change T and N depending on the machine to get better success rate :).

import java.util.ArrayList;
import java.util.List;

import car.Car;

public class Driver {

    private static final int T = 1000;
    private static final int N = 20;

    /**
     * @param args
     * @throws InterruptedException
     */
    public static void main(String[] args) {
        Car car = new Car();
        CarThread carThread = new CarThread(car);

        for (int i = 0; i < T; i++) {
            List<Thread> threads = new ArrayList<Thread>();

            for (int j = 0; j < N; j++) {
                threads.add(new Thread(carThread));
            }

            for (int j = 0; j < N; j++) {
                threads.get(j).start();
            }

            for (int j = 0; j < N; j++) {
                threads.get(j).stop();
                car.vroom();
            }
        }
    }

    static class CarThread implements Runnable {
        private Car car;

        CarThread(Car car) {
            this.car = car;
        }

        public void run() {
            car.accelerate(1001);
        }
    }
}

mbartmann wrote on 2012-03-03 17:53

// This one tunes the stack more reliably

package driver;

import car.Car;

public class Driver {

    private static Car car;

    public static void main(String args[]) {
        // TODO break the speed limit
        car = new Car();
        car.crash();
        try {
            deepAccelerate();
        } catch (Error e) {
            //e.printStackTrace();
        }
        car.vroom();
    }

    private static void accelerate0() {
        car.accelerate(1001);
        deepAccelerate();
    }
    private static void accelerate1(int i1) {
        car.accelerate(1001);
        deepAccelerate();
    }
    private static void accelerate2(int i1, int i2) {
        car.accelerate(1001);
        deepAccelerate();
    }
    private static void accelerate3(int i1, int i2, int i3) {
        car.accelerate(1001);
        deepAccelerate();
    }
    private static void deepAccelerate() {
        accelerate0();
        accelerate1(0);
        accelerate2(0,0);
        accelerate3(0,0,0);
        deepAccelerate();
    }
}

Wouter wrote on 2012-03-05 18:22

It looks to me like this is mostly dead code: deepAccelerate first calls accelerate0 and that calls deepAccelerate again and so on until it hits the StackOverFlowError. accelerate0() never returns normally (only with the error). so the part after that in deepAccelerate (accelerate1, accelerate2 and accelerate3) will never be called.

mbartmann wrote on 2012-03-06 11:17

My fault. This is funny: my first solution never crashed my machine, whereas this solution always does. I’ll have to investigate. Could be that the larger number of methods somehow makes the JVM inline the crash() method too late?.

What I really wanted to achieve here is what you get when you remove the superfluous “deepAccelerate()” from the accelerate0-3 methods: using only one word more on the stack for each invocation of crash(). My assumption was that if we fill the stack too fast, it might overflow the call to accelerate instead of the inner call to crash(). Because this worked immediately for me, I did not find the buggy superfluous recursive call.

Kay Huber wrote on 2012-03-03 23:22

Found a solution that bets on a race condition which will only occur in multi-core cpu systems and also there not reliably (sigh).

package driver;

import java.util.concurrent.CountDownLatch;

import car.Car;


/**
 * Crazy stunt driver implementation.
 *
 * Will drive same car in two parallel threads killing the one where acceleration is
 * in progress in the hope, that acceleration was executed, but crashing not just yet.
 *
 * Unfortunately, this doesn't predictably work - it's betting on race conditions...
 *
 * @author Kay Huber
 */
public class Driver {
    private static CountDownLatch latch;

    private static class Harakiri extends Thread {
        private Car car;
        public Harakiri(Car car) {
            this.car = car;
        }

        public void run() {
            try {
                latch.await();
            } catch (InterruptedException e) {
                return;
            }

            while (true) {
                car.accelerate(1001);
            }
        }
    }

    @SuppressWarnings("deprecation")
    public static void main(String args[]) {
        // preparation of our stock car
        final Car stockCar = new Car();

        // loop until we tried some various sleep steps - hopefully, at least one of them succeeded
        int nanos = 0;
        do {
            nanos += 100;
            latch = new CountDownLatch(1);

            try {
                // start new stunt in separate harakiri thread
                Harakiri harakiri = new Harakiri(stockCar);
                harakiri.start();
                latch.countDown();

                // wait a little in our thread
                Thread.sleep(0, nanos);

                // now stop / kill the harakiri thread
                harakiri.stop();

                // wait until it's done dying
                harakiri.join();
            } catch (InterruptedException e) {
            }

            // vroom it
            stockCar.vroom();
        } while (nanos < 10000);
    }
}

Gerrit van Brakel wrote on 2012-03-04 18:07

This one was hard. First thought of stopping a tread using stop(), but that was too hard to time. The solution below works, but still have to find out why it cannot be done simpler. I could not remove the array that is not used at all. It will probably stop the stack from expanding or so. Well, fine. Having a solution, but still no clue…

Thanks for the fun!

Gerrit

package driver;

import car.Car;

public class Driver {

    static Car car = new Car();

    public static void main(String args[]) {
        // TODO break the speed limit
        accelerate();
        car.vroom();
    }

    private static Object dummy[] = new Throwable[1];

    private static int catches = 0;

    private static boolean caughtException = false;

    private static void accelerate() {
        try {
            accelerate();
            if (caughtException) {
                catches++;
                if (catches == 1) {
                    car.accelerate(1001);
                }
                caughtException = false;
            }
        } catch (Throwable t) {
            caughtException = true;
        }
    }
}

Wouter wrote on 2012-03-04 18:40

================================================== Comments above this one were added on the original puzzle. Comments below when the solution was already available

Oleg Šelajev wrote on 2012-03-04 20:28

This gets the result pretty reliably on my machine, though needs tweaking for other environments. Basic principle is as with the other Thread.stop() solutions, but also, it exhausts CPU with auxiliary threads and provides multiple stoppers.

package driver;

import car.Car;

public class Driver {

  private static final int ACCELERATOR_PRIORITY = Thread.NORM_PRIORITY;
  private static final int STOPPER_PRIORITY = Thread.NORM_PRIORITY;

  private static final int STOPPERS_COUNT = 50;
  private static final int ITERATION_COUNT = 400;
  private static final int CPU_LOADER_COUNT = 2;

  private static int earlyCount = ITERATION_COUNT;
  private static int lateCount = 0;

  @SuppressWarnings("deprecation")
  public static void main(String args[]) throws InterruptedException {
    Thread[] workers = new Thread[CPU_LOADER_COUNT];
    for (int i = 0; i < workers.length; i++) {
      workers[i] = new Thread(new HardWork());
      workers[i].start();
    }
    try {
      final Car car = new Car();
      final Object lock = new Object();
      for (int i = 0; i < ITERATION_COUNT; i++) {
        final Thread accelerator = new Accelerator(lock, car);
        accelerator.setPriority(ACCELERATOR_PRIORITY);

        Thread[] vroommers = new Thread[STOPPERS_COUNT];
        for (int j = 0; j < vroommers.length; j++) {
          vroommers[j] = new Stopper(accelerator, lock, car);
          vroommers[j].setPriority(STOPPER_PRIORITY);
          vroommers[j].start();
        }
        accelerator.start();
        car.vroom();
        accelerator.join();
        for (int j = 0; j < vroommers.length; j++) {
          vroommers[j].stop();
        }
      }
    }
    finally {
      for (int i = 0; i < workers.length; i++) {
        workers[i].stop();
      }
    }
  }

  static class HardWork implements Runnable {
    private double PI = 1.0 / Math.sqrt(3);

    @Override
    public void run() {
      while (true) {
        PI = (Math.sqrt(PI * PI + 1) - 1) / PI;
      }
    }

    public double getPI() {
      return PI;
    }
  }

  static class Stopper extends Thread {
    private final Thread accelerator;
    private final Object lock;
    private final Car car;

    public Stopper(Thread accelerator, Object lock, Car car) {
      this.accelerator = accelerator;
      this.lock = lock;
      this.car = car;
    }

    public void run() {
      synchronized (lock) {
        try {
          lock.wait();
        }
        catch (InterruptedException e) {
          e.printStackTrace();
        }
      }
      accelerator.stop();
      car.vroom();
    }
  }

  static class Accelerator extends Thread {

    private final Car car;
    private final Object lock;

    public Accelerator(Object lock, Car car) {
      this.lock = lock;
      this.car = car;
    }

    public void run() {
        synchronized (lock) {
          lock.notifyAll();
        }
        earlyCount--;
        car.accelerate(10001);
        lateCount++;
    }
  }
}

mihi wrote on 2012-03-04 21:46

That “including all native code” comment puzzles me. As far as I know, a switch to native code will switch the stack to a “native stack” (that has its own fixed size), and then switch the stack back on exit. That way, errors in native methods cannot that easily unintentionally corrupt the Java stack, and make the hs_err log files that are created on a SIGSEGV in native code (or on a SEH exception on Windows) more reliable. But the last time I really debugged a native method I did not check if that is still the case (in all cases - maybe it gets switched of when the execution counter of a method reaches a certain limit or when the calling method is JITed?). If it is, stack overflow in native methods should not be triggerable this way.

Wouter wrote on 2012-03-04 22:32

I must admit I don’t know much about how the invocation of native methods works. It made me wonder how that stuff deals with this problem, but I never really looked into that. I’m just throwing out some ideas hoping that maybe it might inspire someone else to discover something.

In short: I don’t know what I’m talking about; that’s why it’s posed as an open question.

thomas kountis wrote on 2012-03-04 23:53

That was a great puzzle, I tried this trick for the second puzzle but not for this one, very disappointed :P. Excellent work, keep it coming.

mbartmann wrote on 2012-03-05 17:16

I do not understand the reason for being “gentler” to the car. There are not so many crashes, there is only one. All other calls to car.accelerate() are performed w/o overflow, only the deepest one fails, and after that we are done. I found out that on my system it was more sensible to the exact amount of stack available. So in my second solution I played with a growing number of arguments, to raise the stack by only 1 word for each try. This one worked reliable for my, but it still only “crashes the crash” only once.

Wouter wrote on 2012-03-05 18:18

There is only one “crash of the crash” (StackOverflowError). But all other calls still “crash”: they call the crash() method setting the speed to 0. It is by calling that method so many times (and not by it throwing a StackOverflowError) that it gets in-lined.

If you have trouble reproducing that, you could add this at the start of your program:

for (int i = 0; i < 10000; i++) {
   car.accelerate(1001);
}

After doing that it will become impossible to still make it throw a StackOverflowError at the right place (unless your JVM really refuses to optimise anything).

mihi wrote on 2012-03-05 19:26

In fact, the crash() method gets inlined because accelerate() is called that often. For more details, see the documentation of the -XX:CompileThreshold JVM option (or just reduce it to 1 which means every function gets optimized when it is exited the first time). Setting –XX:CompileTHreshold=1000000 should make it much easier to reproduce, but then you can also just say -Xint and disable all optimization.

mbartmann wrote on 2012-03-06 11:10

Of course you are right. I misinterpreted “crash it a bit less, so the JVM doesn’t decide to optimise that”. I thought it meant “crash crash() less often” where you meant “crash() less often”.

Frank wrote on 2012-03-05 20:39

Very nice puzzle! I was looking at

private int speed = 0;

and kept thinking it should be

private volatile int speed = 0;

but couldn’t find a way to abuse that.

deadalnix wrote on 2012-03-07 12:48

volatile creates a memory barrier, so it doesn’t need to be synchronized.

Solf wrote on 2012-03-06 10:39

Nice one.

I’ve posted Thread.stop() ‘solution’ (which I didn’t really like), but stack overflow is really a clever one – didn’t think of it myself and hopefully will keep it in mind in the future :)

Solf wrote on 2012-03-06 10:43

Although now thinking about it – how do you make sure it runs out of stack on crash() invocation and not, say, on recurse() or accelerate() [neither of which will produce the desired result… I think…]?

Niko und Simon wrote on 2012-03-07 13:24

Our thread.stop solution

package driver;

import car.Car;

public class Driver implements Runnable {
    static Car car = new Car();
    public static void main(String args[]) throws InterruptedException {



            while(true) {
                Thread thread = new Thread(new Driver());
                Thread thread2 = new Thread(new Driver());
                Thread thread3 = new Thread(new Driver());

                thread.start();
                thread2.start();
                thread3.start();
                Thread.sleep(1);
                thread.stop();
                car.vroom();
                thread2.stop();
                car.vroom();
                thread3.stop();
                car.vroom();
            }


    }

    public void run() {
            while(true) {
                try {
                    car.accelerate(10000);
                } catch(RuntimeException re) {

                }
            }
    }
}

deadalnix wrote on 2012-03-07 13:35

It is surprising that most JVM seems not to do tail queue recursion : http://en.wikipedia.org/wiki/Tail_call

What does in means about Scala ? Anyway, we must prevent it in this exercise, so it would be nice to add a dumb instruction after recurse to be sure we prevent it.

mihi wrote on 2013-02-04 22:57

As we know now, system libraries are (or used to be) not always prepared to crash:

http://icedtea.classpath.org/hg/release/icedtea7-forest-2.3/jdk/rev/e46d557465da#l1.28

Wouter wrote on 2013-02-06 19:56

Ah, that’s an interesting one! Is there any reference to that change recognizing it as a security vulnerability?