writing to a java treemap concurrently can lead to an infinite loop during reads
The java.util.TreeMap documentation warns that the underlying implementation for this Map is not synchronized — and thus it is not thread-safe.
But have you ever wondered what happens if you ignore that warning and you write an application that concurrently writes to the map from different threads? Intuitively, I’d probably expect some entries to be lost, or to sometimes get a NullPointerException.
But did you know that — at least with the current implementation shipped on OpenJDK — you can actually corrupt the TreeMap in such a way that attempts to read the map will result in your code getting stuck on an infinite loop?
This happens because the TreeMap is implemented as a red-black tree, a self-balancing tree algorithm. As new elements are inserted into the tree, the tree is rebalanced — elements are moved around so that the tree is kept height-balanced. (See the Wikipedia article for details, as they explain a lot better than I do!)
When several threads are adding new entries to a TreeMap at the same time, those threads also compete to rebalance the tree concurrently. And because rebalancing entails changing several pointers, the result is that the tree may form internal loops — thus no longer being a tree.
The following application is able to show this issue. It repeatedly creates a new TreeMap, writes to it using two different concurrent threads, and then navigates the internal map structure using reflection to check if the TreeMap formed a loop. When it finds a loop, it prints it.
import java.util.*;
import java.lang.reflect.*;
import java.util.Map.Entry;
@SuppressWarnings("unchecked")
public class ConcurrentTreeMapLoopReproducer {
public static void main(String ... args) throws Exception {
System.out.println("Running on Java " + System.getProperty("java.version"));
int insertUpTo = 20;
if (args.length > 0) {
insertUpTo = Integer.parseInt(args[0]);
}
System.out.println("Using insertUpTo=" + insertUpTo);
new ConcurrentTreeMapLoopReproducer(insertUpTo).call();
}
TreeMap<Integer,Integer> brokenMap = null;
int insertUpTo;
ConcurrentTreeMapLoopReproducer(int insertUpTo) {
this.insertUpTo = insertUpTo;
}
static class LoopStep {
Entry<Integer,Integer> entry;
String direction;
LoopStep next;
LoopStep(Entry<Integer,Integer> entry) { this(entry, null, null); }
LoopStep(Entry<Integer,Integer> entry, String direction, LoopStep next) {
this.entry = entry;
this.direction = direction;
this.next = next;
}
public String toString() {
if (next != null) {
return "" + entry.getKey() + " --" + direction + "--> " + next;
} else {
return entry.getKey().toString();
}
}
}
public void call() throws Exception {
LoopStep loopPath = null;
System.out.print("Attempting to trigger looping TreeMap");
for (int attempts = 1; loopPath == null; attempts++) {
System.out.print(".");
System.out.flush();
brokenMap = tryToTriggerLoopingTreeMap();
loopPath = findLoop(brokenMap);
}
System.out.println("\nWas able to reproduce loop in map: " + loopPath);
// Uncomment this to see the loop in action: This will never finish
//brokenMap.values().toArray();
}
static TreeMap<Integer,Integer> tryToTriggerLoopingTreeMap() throws Exception {
TreeMap<Integer,Integer> map = new TreeMap<>();
Thread t1 = new Thread(() -> { for (int i = 0; i < 20; i += 2) try { map.put(i, i); } catch (Exception e) { } });
Thread t2 = new Thread(() -> { for (int i = 1; i < 20; i += 2) try { map.put(i, i); } catch (Exception e) { } });
t1.start();
t2.start();
t1.join();
t2.join();
return map;
}
static LoopStep findLoop(TreeMap<Integer,Integer> map) throws Exception {
Field rootField = TreeMap.class.getDeclaredField("root");
rootField.setAccessible(true);
Entry<Integer,Integer> rootEntry = (Entry<Integer,Integer>) rootField.get(map);
return findLoopRecursive(new ArrayList<>(), rootEntry);
}
static LoopStep findLoopRecursive(List<Entry<Integer,Integer>> currentPath, Entry<Integer,Integer> entry) throws Exception {
if (entry == null) return null;
if (currentPath.contains(entry)) {
currentPath.add(entry);
return new LoopStep(entry);
}
currentPath.add(entry);
LoopStep result = null;
result = findLoopRecursive(currentPath, get("left", entry));
if (result != null) return new LoopStep(entry, "left", result);
result = findLoopRecursive(currentPath, get("right", entry));
if (result != null) return new LoopStep(entry, "right", result);
currentPath.remove(entry);
return null;
}
static Entry<Integer,Integer> get(String direction, Entry<Integer,Integer> parent) throws Exception {
Field field = parent.getClass().getDeclaredField(direction);
field.setAccessible(true);
return (Entry<Integer,Integer>) field.get(parent);
}
}(Ufff. Java can get so verbose!)
Because this is a concurrency issue, this code is not always successful in triggering an issue.[1]
On other runs, you may get an infinite loop during a put() operation.
But in most cases you’ll get something like this:
$ java ConcurrentTreeMapLoopReproducer Running on Java 10 Using insertUpTo=20 Attempting to trigger looping TreeMap.WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by ConcurrentTreeMapLoopReproducer (file:/home/knuckles/projects/treemap-blog/) to field java.util.TreeMap.root WARNING: Please consider reporting this to the maintainers of ConcurrentTreeMapLoopReproducer WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release .............. Was able to reproduce loop in map: 10 --left--> 5 --right--> 14 --left--> 10
What does this mean? It means that internally, the tree has formed a loop.[2] Here’s how this one specifically looks like:
And here’s a very simple animation of what would happen if you were to call get(9) on such a tree:[3]
Another way to cause an infinite loop is to uncomment the line containing //brokenMap.values().toArray();. This operation attempts to iterate the map, and gets stuck on the loop forever.
As always, be careful when combining concurrency and mutation. And thanks to my awesome colleague Oli for the really interesting debugging session.
insertUpTo parameter or adding more threads if you’re having trouble reproducing the issue on your own machine. k such that get(k) generates a loop. I leave as an exercise to the reader to discover why 😁.