It’s actually become quite entertaining to me how multiple threads can make silly things happen. Like when a piece of code that you would never assume could go wrong suddenly develops amazing ways to surprise you by breaking code that is absolutely no where near it and in ways that are almost perfectly random. This is actually a little related to networking code in QubeKwest because it is the first piece of the software that is actually multi-threaded, but I’m sure it won’t be the last as I try to squeeze every little bit of power out of whatever system I end up on.
In an attempt to prevent multi-threaded problems I spent a solid week walking around with printed out pages of source code and a pen. I was marking every line of code with little letters that indicated which threads I thought could get to it, and “playing computer” in an attempt to figure out how something could go wrong. The end result of this effort was that I found and likely fixed several potential problems and then located and purchased a tool called ThreadSafe by Contemplate. It was a very big hit on my meager indie development tool budget, but it found a problem I hadn’t considered. Actually, I’m fairly proud that it only found one issue considering how many things it looks for and how big my codebase has become.
A new rule I made up and call “the core rule of multithreaded code” can be summarized as “If multiple threads can run the lines of code in a method in an inconvenient order, they will be run in the most inconvenient way possible.”
Consider this code for a moment, but pretend that all of the parts of it are actually using fancy or correctly named versions from the java.util.concurrent package as an attempt to make this work as well as possible without synchronization blocks. I just didn’t want to use their longer names for this example because that would make things more complex for no reason.
private HashMap<Integer, List<String>> hash =
new HashMap<Integer, List<String>>();
public void addToList( Integer inKey, String inData )
{
List<String> list = hash.get( inKey );
if( list == null )
{
list = new List<String>();
hash.put( inKey, list );
}
list.add( inData );
}
This code manages a collection of lists and was based on the idea of “a list of stuff to do for this thing” but was simplified to just a list of strings associated with an integer key. First, I’m going to explain what this code does when you call it in a purely single threaded way.
Let’s say you call it with the parameters 1, “Taco”. First it attempts to load the list of strings for key 1. If there wasn’t one yet, it makes a new list and puts it into the hash map associated with key 1. Afterwards, it adds “Taco” to the list and ends. If you call it a second time later with the parameters 1, “Burrito” it tries to get the list associated with key 1 and succeeds. That means the if block that sets up a new list never happens and it moves on to add “Burrito” to the list and ends. This all flows nicely and covers your various edge cases and generally makes good sense.
Now, imagine you call it twice at the same time in two different threads. (Which is actually possible in my network code.) The first thread uses the parameters 1, “Taco” and the second thread uses 1, “Burrito” just like the two separate calls in the example above, except they happen at the same time. Following the rule that inconvenient things must occur in the most inconvenient way possible, we’ll also assume that there is no list attached to key 1 yet. Thus, both threads enter the method, both threads attempt to get the list for key 1, neither thread gets a list (because they are both the first). Next, both threads check for a null list (which they both have), both threads make a new list, and both threads put their list into the hash map for key 1. This is something that succeeds in both cases, but only one at a time, and where the problems really start.
Let’s say that the thread trying to add “Taco” goes first. Now the hash map has a list that was successfully put into the spot for key 1. Immediately afterwards, the thread trying to add “Burrito” puts its brand new list into the hash map for key 1 too. This also succeeds, but replaces the list that was in the spot already from when the thread trying to add “Taco” put its there.
Consider the state of the local variables in each thread after this has occurred. Both threads have a variable called “list” that refers to a perfectly valid new list, but only one thread has its list set in the hash map. (But they both think their list is the one in the hash map.) Finally, both threads add their new value to their own reference to a list, and exit. What really happened though? The thread putting “Taco” into a list did so to a list that is only known to the local list variable, and the thread putting “Burrito” actually puts it into a list that the hash map knows about. That means that both calls to the function completed successfully, but the result is that in the hash map, there is a list that only has “Burrito” in it. The “Taco” data is simply gone the moment the local variable “list” goes out of scope when the function ends.
This demonstrates how multithreaded code can blow up, but now let’s think about the side effect of this event. Later on, code is going to grab the list for key 1 out of the hash map to do things with the list of strings in it. It will also probably just be missing values (like “Taco” for example) and have no idea that they are even missing. The end user expects the results to be shown for multiple items of food, but some of the ones it figured should be there simply aren’t. Now a developer attempts to figure out why.
The bug report talks about code misbehaving code somewhere no where near the place where the problem actually occurred, and it is random which data is missing so they can’t even reliably reproduce the problem. There is nothing that requires the “Taco” thread put its list in first, so it could be “Burrito” that’s missing just as easily, and completely randomly.
Better still, attempting to walk through the code with a debugger shows the function completing successfully twice, and in a lot of cases, the use of the debugger itself is enough to cause the problem to not occur at all. After all, a breakpoint that causes a delay long enough for one path through the function to already see the other list in the hash map would make the problem vanish.
The solution is to use a special method on the concurrent form of a hash map that atomically puts something into the hash map only if there isn’t already something there. This would make the code above look like this.
private HashMap<Integer, List<String>> hash =
new HashMap<Integer, List<String>>();
public void addToList( Integer inKey, String inData )
{
List<String> list = hash.get( inKey );
if( list == null )
{
list = new List<String>();
List<String> tempList = hash.putIfAbscent( inKey, list );
if( tempList != null )
list = tempList;
}
list.add( inData );
}
This should look really familiar, but the attempt to set the list to the hash map is now protected by the use of putIfAbscent() and there is a second if block to adjust things based on how that went. The putIfAbscent() method internally protects against things happening at the exact same time, so they are forced to get in line and happen one after another. Which order that happens is still random, but they at least there is a little bit of sanity instead of none at all. Using the same multithreaded example as before, the new flow has been changed to this:
The first thread uses the parameters 1, “Taco” and the second thread uses 1, “Burrito”, and as before they happen at the same time. We will also repeat the scenario where both threads are attempting to be the first attempt to set a value associated with key 1. Thus, both threads enter the method, both threads attempt to get the list for key 1, neither thread gets a list (because they are both the first). Next, both threads check for a null list (which they both have), both threads make a new list, and both threads attempt to put their list into the hash map for key 1. This time however, either thread can only put their list into the hashmap if there isn’t one already there. The putIfAbscent() method returns null if there was no list already set to the key, or if there was a list, it returns the one that was there instead of actually putting the new one there.
This gives us the opportunity to behave in a way that makes more sense. Now, when we try to insert a new list into the hashmap and there wasn’t one there, we succeed and move on to add our string to the list without any trouble. When we try to insert our new list and there is already one there, we get the one that was there back from the attempt. If that happens, we simply replace our new list with the one we got back. That means we have a new list that will be garbage collected, and that both threads actually have a reference to the exact same list.
As before, let’s say that the thread trying to add “Taco” goes first. Now the hash map has a list that was successfully put into the spot for key 1. Immediately afterwards, the thread trying to add “Burrito” tries to put its brand new list into the hash map for key 1 too. Instead of blowing away the list put there by the thread trying to add “Taco”, it actually returns the list the “Taco” thread put there. After that, we simply check to see if there was some list returned by the putIfAbscent() call, and if there was, we use it as our local list. That means when “Taco” gets added to the list, that works fine. It also means when “Burrito” is added to the list, it’s actually doing it to the same list the “Taco” thread used instead of using the one it initially created for the job. That means both strings are in the same list, and that list is correctly stored in the hash map. That in turn means the code actually worked, even when the most inconvenient way possible was used, and that is a reason to be happy. I like reasons to be happy.
