1

https://ivoanjo.me/blog/2018/07/21/writing-to-a-java-treemap-concurrently-can-lead-to-an-infinite-loop-during-reads/ demonstrates how multiple concurrent writers may corrupt a TreeMap in such a way that cycles are created, and iterating the structure becomes an infinite loop.

Is it also possible to get in an infinite loop when concurrently iterating and writing with at most one concurrent writer? If not can anything other than skipping elements, processing elements twice, or throwing a ConcurrentModificationException happen?

Martijn
  • 11,964
  • 12
  • 50
  • 96
  • 4
    It's not really relevant whether you can get infinite loops (specifically) under these conditions: you're not using the class correctly (["If multiple threads access a map concurrently, and **at least one** of the threads modifies the map structurally, it must be synchronized externally"](https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html)), so the behavior is undefined. – Andy Turner Oct 18 '19 at 09:03
  • [`ConcurrentModificationException` is not guaranteed to be thrown](https://stackoverflow.com/a/55141359/545127). What happens if you misuse a `TreeMap` is not specified. But in practice, I would expect implementations would *try* to prevent infinite loops. – Raedwald Oct 18 '19 at 09:08
  • @AndyTurner we're going to have to disagree on whether it's relevant whether you can get infinite loops specifically under these conditions. – Martijn Oct 18 '19 at 09:10
  • 2
    @Martijn Can you explain why you think it's relevant? An infinite loop is just one possible consequence of the larger issue—improperly synchronized code. Without a _happens-before_ relationship there's no guarantee the reading threads will see the updates made by the writing thread; in fact, each reading thread could see different state than every other reading thread. This state isn't just the externally visible state (i.e. present keys, key-value mappings, etc.) but all the state the map uses internally to store the data. – Slaw Oct 18 '19 at 09:27
  • @Martijn It is in fact irrelevant. Why? You already need to take measures that would prevent infinite loops anyway regardless of if they would actually happen or not without those measures in place. – Fildor Oct 18 '19 at 09:29
  • @Slaw in this particular example it's library code that *should* be externally synchronized, but shouldn't lead to infinite loops or hangs when used incorrectly. The *best* outcome here would be a ConcurrentModificationException, but that can't be guaranteed. – Martijn Oct 18 '19 at 09:59
  • 3
    @Martijn there is no point in the authors of TreeMap the effort into preventing infinite loops (specifically) when used incorrectly: if they're going to do that, they may as well just make the data structure work concurrently. – Andy Turner Oct 18 '19 at 10:09
  • It seems much more difficult to me to make a nonblocking datastructure than to prevent loops from forming in the datastructure when the datastructure isn't structurally changed concurrently by more than one entity (in fact, I can't even see how loops could be created in the first place with no concurrent writers). Why is this not the case? – Martijn Oct 18 '19 at 10:19
  • @Martijn the loops occur because conflicting updates are made, but without necessarily being visible to the other mutating threads. If the threads could see the updates, sure, they might be able to prevent them. But then how do you guarantee the visibility? – Andy Turner Oct 18 '19 at 10:34
  • 1
    @Martijn It's not the responsibility of a non-thread-safe class to handle the case where it's used by multiple threads concurrently—especially when said class is explicitly documented to not be thread-safe. If a class which is not thread-safe must be used in a concurrent context then it is the responsibility of _the developer using the class_ to synchronize access. Without proper synchronization there's a good chance the state of the class will be corrupted which can lead to all sorts of _unspecified behavior_, such as infinite loops and unexpected exceptions. – Slaw Oct 18 '19 at 11:15
  • 2
    @Slaw "such as infinite loops and unexpected exceptions" at best - at worst, you get silently incorrect data. – Andy Turner Oct 18 '19 at 11:21
  • @AndyTurner if a user fails to synchronize between reading and writing, they will not be able to order what happens first, and reading becomes meaningless anyway. What the user needs is a clear indication something is wrong. Infinite loops are almost impossible to correctly diagnose. If I offload a synchronization requirement to the end-developer, they should at least be provided with an error. – Martijn Oct 18 '19 at 12:28
  • @Martijn "What the user needs is a clear indication something is wrong" sure. How do you determine that something is wrong without visibility guarantees? – Andy Turner Oct 18 '19 at 12:31
  • @AndyTurner you can't order such guarantees for a single run, you can just guarantee that a visible exception arises once every now and then, and that you don't within a single thread modify a structure in such a way that iteration would loop. You *have* visibility guarantees on the single thread, and also in this scenario that there is only one concurrently writing thread. – Martijn Oct 18 '19 at 12:41
  • 1
    What you should take away from this is that if you use non-thread-safe code in a concurrent context without external synchronization then all bets are off. You can no longer rely on anything being correct nor can you reliably predict what will happen. That may not answer your actual question, but Andy (who I suspect has much greater experience than I) gave an answer, or at least an educated guess. – Slaw Oct 18 '19 at 13:48
  • I don't need to reliably detect improper use. Reliability of detection can't be guaranteed. I'll settle for unreliable detection of improper use. – Martijn Oct 18 '19 at 14:12
  • @Fildor I think you are wrong, to investigate infinite loop cause, will give you next time a hint when there is a hang. In fact I personally did not know that concurrency problems can cause infinite loop until I came accross a case like in here. Yes,concurrency can cause all problems, but nobody say what exactly those problems are. Granted it can be false data, crash etc, but what are the possibilities? which one is more likely to happen? This is also an interesting question, because the case I have here is a hidden bug for years but nobody complains until recently it has a hang. – Dexter May 01 '21 at 15:08
  • @Dexter I think you profoundly misunderstood, what I was trying to say. – Fildor May 01 '21 at 15:17

2 Answers2

3

Is it also possible to get in an infinite loop when concurrently iterating and writing with at most one concurrent writer?

I would say a cautious no: these infinite loops occur because multiple threads are re-wiring the relationships between the nodes, and so may make conflicting updates. A single thread won't conflict with itself, so such a re-wiring mixup would not occur.

However, I am not confident in this - but I don't need to be: such a usage of a TreeMap is in violation of the documentation:

If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

If you don't externally synchronize, the behavior is undefined. Implementors of the class are free to implement the class in any way that meets the specification; and it is possible that one way might result in an infinite loop.

If you are encountering an infinite loop in a TreeMap, that's a symptom, not the root cause - namely, unsynchronized access to mutable data. This means that there is no guarantee that the values being read by the only-reading threads are correct either.

Andy Turner
  • 137,514
  • 11
  • 162
  • 243
0

If you need to concurrently access a map, you'll have to use Collections.synchronizedMap. Otherwise, donc expect it to work correctly.

Maurice Perry
  • 9,261
  • 2
  • 12
  • 24