An impossible race condition

[westnordost]

I got this crash report recently:

java.util.NoSuchElementException: Key
       nodes, ways, relations with
         historic = wayside_shrine
         and !religion
         and access !~ private|no
    is missing in the map.
at kotlin.collections.MapsKt__MapWithDefaultKt.getOrImplicitDefaultNullable(MapWithDefault.kt:24)
at kotlin.collections.MapsKt__MapsKt.getValue(Maps.kt:346)
at kotlin.collections.MapsKt.getValue(Unknown Source:0)
at de.westnordost.streetcomplete.data.osm.mapdata.MapDataXtKt.getElementFilterExpression(MapDataXt.kt:30)

But the code in qestion is

private val filterExpCache: MutableMap<String, ElementFilterExpression> = HashMap()

private fun getElementFilterExpression(expr: String): ElementFilterExpression {
    if (!filterExpCache.containsKey(expr)) {
        synchronized(filterExpCache) {
            if (!filterExpCache.containsKey(expr)) {
                filterExpCache[expr] = expr.toElementFilterExpression()
            }
        }
    }
    return filterExpCache.getValue(expr)
}

Anyone, any idea how this is possible? I.e. how it is possible that the key does not exist in the map at the return statement? (String.toElementFilterExpression() returns an ElementFilterExpression, not nullable)

[kmpoppe]

Could this be some weird threading issue? Would it help to put the whole if-block into synchronized?

[westnordost]

I think it must be, but the synchronized should prevent this. And the whole if block is already in the synchronized block, i fyou look closely.

[kmpoppe]

Well the first line of getElementFilterExpression is if (!filterExpCache.containsKey(expr)) {.
I see that the very same line is within synchronized again, but I wonder if the first access to the Cache being outside of synchronized causes the issue (because it checks for the contents of the Map before the sync gets initialized)?

[westnordost]

Why/how? This could only be a potential problem if elements from the filterExpCache are ever removed (but they are not), the way I see it.

[tapetis]

As far as I understand the code of Java's HashMap, the insertion of a new element into the map is a complex process that can result in a rearranging of the map's internal tree structure. This rearranging process is only started after the new element is added to an empty position in the tree. At this time, containsKey returns true.

During rearranging, however, elements may be temporarily removed from the tree. This can result in previously inserted keys not being in the map during the iteration of the map's nodes and thus in getValue returning null.

[kmpoppe]

That sound like a damn good explanation of the problem @tapetis 👍

[westnordost]

Oh wow, I never thought of that. One lives and learns. Makes me wonder what would happen if one adds another value (in another thread) while the rearranging process is being done. Anyway, so either I have to use synchronized everywhere when accessing a HashMap or use ConcurrentHashMap.

[westnordost]

I've used this pattern in 2 more places, they should be fixed now. Thank you @tapetis !