Infinite Loop in scala.collection.mutable.HashTable

[huang-hf]

scala version:2.10.4
java version: java version "1.7.0_79" (64-Bit)

When I run unit test by maven, It cause infinite loop every 3 or 4 times.
I make sure the HashMap or HashTable only visit or update in single thread.
My unit test mostly like:

val hashmap = scala.collection.mutable.HashMap[String, Double]()
hashmap("key") = 1.0 

I search others had same problem.
Also see:

• https://groups.google.com/forum/#!topic/liftweb/FAVMVoD-l74
• https://groups.google.com/forum/#!topic/liftweb/j3SO5_iOA7Y

It seems that has this problem few year ago.
It was already solved? If it was, please show the bug URL. Thank you.

Jstack info show below:
nid=0x39d9,nid=0x39a2 this two threads always had mostly 100% cpu-use in 'top' command in Linux.

2017-07-27 16:02:57
Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.72-b15 mixed mode):

"Executor task launch worker-6" #1260 daemon prio=5 os_prio=0 tid=0x00007fc8903ea000 nid=0x39d9 runnable [0x00007fc87f8f7000]
java.lang.Thread.State: RUNNABLE
at scala.collection.mutable.HashTable$class.elemEquals(HashTable.scala:347)
at scala.collection.mutable.HashMap.elemEquals(HashMap.scala:39)
at scala.collection.mutable.HashTable$class.scala$collection$mutable$HashTable$$findEntry0(HashTable.scala:134)
at scala.collection.mutable.HashTable$class.findOrAddEntry(HashTable.scala:162)
at scala.collection.mutable.HashMap.findOrAddEntry(HashMap.scala:39)
at scala.collection.mutable.HashMap.put(HashMap.scala:75)
at scala.collection.mutable.HashMap.update(HashMap.scala:80)
# business code
at scala.collection.mutable.HashMap$$anonfun$foreach$1.apply(HashMap.scala:98)
at scala.collection.mutable.HashMap$$anonfun$foreach$1.apply(HashMap.scala:98)
at scala.collection.mutable.HashTable$class.foreachEntry(HashTable.scala:226)
at scala.collection.mutable.HashMap.foreachEntry(HashMap.scala:39)
at scala.collection.mutable.HashMap.foreach(HashMap.scala:98)
# business code
at scala.collection.Iterator$class.foreach(Iterator.scala:727)
at scala.collection.AbstractIterator.foreach(Iterator.scala:1157)
# business code
at org.apache.spark.rdd.RDD$$anonfun$mapPartitions$1$$anonfun$apply$17.apply(RDD.scala:686)
at org.apache.spark.rdd.RDD$$anonfun$mapPartitions$1$$anonfun$apply$17.apply(RDD.scala:686)
at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
at org.apache.spark.scheduler.ShuffleMapTask.runTask(ShuffleMapTask.scala:70)
at org.apache.spark.scheduler.ShuffleMapTask.runTask(ShuffleMapTask.scala:41)
at org.apache.spark.scheduler.Task.run(Task.scala:70)
at org.apache.spark.executor.Executor$TaskRunner.run(Executor.scala:213)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
at java.lang.Thread.run(Thread.java:745)

"Executor task launch worker-5" #1257 daemon prio=5 os_prio=0 tid=0x00007fc8922fc800 nid=0x39a2 runnable [0x00007fc880400000]
java.lang.Thread.State: RUNNABLE
at scala.collection.mutable.HashTable$class.elemEquals(HashTable.scala:347)
at scala.collection.mutable.HashMap.elemEquals(HashMap.scala:39)
at scala.collection.mutable.HashTable$class.scala$collection$mutable$HashTable$$findEntry0(HashTable.scala:134)
at scala.collection.mutable.HashTable$class.findOrAddEntry(HashTable.scala:162)
at scala.collection.mutable.HashMap.findOrAddEntry(HashMap.scala:39)
at scala.collection.mutable.HashMap.put(HashMap.scala:75)
at scala.collection.mutable.HashMap.update(HashMap.scala:80)
# business code
at scala.collection.mutable.HashMap$$anonfun$foreach$1.apply(HashMap.scala:98)
at scala.collection.mutable.HashMap$$anonfun$foreach$1.apply(HashMap.scala:98)
at scala.collection.mutable.HashTable$class.foreachEntry(HashTable.scala:226)
at scala.collection.mutable.HashMap.foreachEntry(HashMap.scala:39)
at scala.collection.mutable.HashMap.foreach(HashMap.scala:98)
# business code
at scala.collection.Iterator$class.foreach(Iterator.scala:727)
at scala.collection.AbstractIterator.foreach(Iterator.scala:1157)
# business code
at org.apache.spark.rdd.RDD$$anonfun$mapPartitions$1$$anonfun$apply$17.apply(RDD.scala:686)
at org.apache.spark.rdd.RDD$$anonfun$mapPartitions$1$$anonfun$apply$17.apply(RDD.scala:686)
at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
at org.apache.spark.rdd.MapPartitionsRDD.compute(MapPartitionsRDD.scala:35)
at org.apache.spark.rdd.RDD.computeOrReadCheckpoint(RDD.scala:277)
at org.apache.spark.rdd.RDD.iterator(RDD.scala:244)
at org.apache.spark.scheduler.ShuffleMapTask.runTask(ShuffleMapTask.scala:70)
at org.apache.spark.scheduler.ShuffleMapTask.runTask(ShuffleMapTask.scala:41)
at org.apache.spark.scheduler.Task.run(Task.scala:70)
at org.apache.spark.executor.Executor$TaskRunner.run(Executor.scala:213)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
at java.lang.Thread.run(Thread.java:745)

    # other info.......

JNI global references: 314

[SethTisue]

I don't see anything obvious in the git history or the ticket database on this, but maybe I missed it.

Perhaps someone else will recognize it and comment. Regardless, I am closing the ticket unless the bug can be demonstrated in a current version of Scala.

[ediweissmann]

I think I bumped into this using scala 2.12.4

Thread dump stacktrace:

java.lang.Thread.State: RUNNABLE
        at scala.collection.mutable.HashTable.findEntry0(HashTable.scala:139)
        at scala.collection.mutable.HashTable.findEntry(HashTable.scala:135)
        at scala.collection.mutable.HashTable.findEntry$(HashTable.scala:134)
        at scala.collection.mutable.HashMap.findEntry(HashMap.scala:40)
        at scala.collection.mutable.HashMap.contains(HashMap.scala:61)
        at code.util.Functions$.executeOnce(Functions.scala:12)

Relevant code snippet in Functions.scala:

import scala.collection.mutable
[...]
val executed = mutable.Map[String, Boolean]()
[...]
if(!executed.contains(key)) {
      executed.put(key, true)
      fn()
    }

I'm not sure how to reproduce this. I think it happened due to multithreading.
I've now replaced the mutable.Map with ConcurrentHashMap.keysSet() to make my code thread safe.

[SethTisue]

scala.collection.mutable.HashTable isn't threadsafe, so weird exceptions if accessed at the same time by multiple threads would be expected behavior

[bryce-anderson]

I've also run into a similar issue on 2.11.11, with an infinite loop with stack trace:

scala.collection.mutable.HashTable$class.resize(HashTable.scala:268)
scala.collection.mutable.HashTable$class.scala$collection$mutable$HashTable$$addEntry0(HashTable.scala:157)
scala.collection.mutable.HashTable$class.findOrAddEntry(HashTable.scala:169)
scala.collection.mutable.HashMap.findOrAddEntry(HashMap.scala:40)
scala.collection.mutable.HashMap.put(HashMap.scala:107)
scala.collection.mutable.HashMap.update(HashMap.scala:112)

This is likely due to concurrent use. I'd have expected and been happy with an exception being thrown.

[NthPortal]

Honestly, it is very difficult to make your collections detect concurrent modification, and may have some overhead cost as well. Just look through the source code for java.util.AbstractList for modCount, expectedModCount, and checkForComoditication - there's a lot of tracking going on behind the scenes. Combine that with the fact that Scala's collections are implemented by mixins in a significant way, and it becomes quite difficult to implement and maintain such tracking.

[SethTisue]

Agree... I kinda half-wanted to reopen this in response to Bryce's report, but I'd be reluctant to get anybody's hopes up that this is likely to change/improve; I think it isn't.

[bryce-anderson]

I think this is a known problem with a number of hash-map implementations. I haven't looked into it, but if there was an easy/performant way to not enter an infinite loop that would be great, but as already noted, it may not be trivial.
That said, for a server, an infinite loop is almost (and depending on the tolerability for corruption, may be) the worst case scenario.

[bingbai0912]

I've also run into a similar issue on 2.11.8, with an infinite loop with stack trace:

Thread 9756: (state = IN_JAVA)
 - Thread 9756: (state = IN_JAVA)
 - scala.collection.mutable.HashTable$class.scala$collection$mutable$HashTable$$findEntry0(scala.collection.mutable.HashTable, java.lang.Object, int) @bci=41, line=136 (Compiled frame; information may be imprecise)
 - scala.collection.mutable.HashTable$class.findEntry(scala.collection.mutable.HashTable, java.lang.Object) @bci=15, line=132 (Interpreted frame)
 - scala.collection.mutable.HashMap.findEntry(java.lang.Object) @bci=2, line=40 (Interpreted frame)
 - scala.collection.mutable.HashMap.get(java.lang.Object) @bci=2, line=70 (Interpreted frame)
 - scala.collection.mutable.MapLike$class.getOrElseUpdate(scala.collection.mutable.MapLike, java.lang.Object, scala.Function0) @bci=2, line=192 (Interpreted frame)
 - scala.collection.mutable.AbstractMap.getOrElseUpdate(java.lang.Object, scala.Function0) @bci=3, line=80 (Interpreted frame)
 - scala.util.parsing.combinator.syntactical.StdTokenParsers$class.keyword(scala.util.parsing.combinator.syntactical.StdTokenParsers, java.lang.String) @bci=16, line=37 (Interpreted frame)
 - scala.util.parsing.json.Parser.keyword(java.lang.String) @bci=2, line=113 (Interpreted frame)
 - scala.util.parsing.json.Parser$$anonfun$jsonObj$2.apply() @bci=6, line=135 (Interpreted frame)
 - scala.util.parsing.json.Parser$$anonfun$jsonObj$2.apply() @bci=1, line=135 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser.p$lzycompute$4(scala.Function0, scala.runtime.ObjectRef, scala.runtime.VolatileByteRef) @bci=18, line=295 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser.scala$util$parsing$combinator$Parsers$Parser$$p$5(scala.Function0, scala.runtime.ObjectRef, scala.runtime.VolatileByteRef) @bci=15, line=295 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$$less$tilde$1.apply(java.lang.Object) @bci=16, line=296 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$$less$tilde$1.apply(java.lang.Object) @bci=2, line=296 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Success.flatMapWithNext(scala.Function1) @bci=5, line=143 (Compiled frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(scala.util.parsing.input.Reader) @bci=12, line=234 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$flatMap$1.apply(java.lang.Object) @bci=5, line=234 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$$anon$3.apply(scala.util.parsing.input.Reader) @bci=5, line=217 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(scala.util.parsing.input.Reader) @bci=5, line=237 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$map$1.apply(java.lang.Object) @bci=5, line=237 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$$anon$3.apply(scala.util.parsing.input.Reader) @bci=5, line=217 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(scala.util.parsing.input.Reader) @bci=5, line=249 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$Parser$$anonfun$append$1.apply(java.lang.Object) @bci=5, line=249 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$$anon$3.apply(scala.util.parsing.input.Reader) @bci=5, line=217 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$$anon$2$$anonfun$apply$14.apply() @bci=11, line=882 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$$anon$2$$anonfun$apply$14.apply() @bci=1, line=882 (Interpreted frame)
 - scala.util.DynamicVariable.withValue(java.lang.Object, scala.Function0) @bci=14, line=58 (Interpreted frame)
 - scala.util.parsing.combinator.Parsers$$anon$2.apply(scala.util.parsing.input.Reader) @bci=21, line=881 (Interpreted frame)
 - scala.util.parsing.json.JSON$.parseRaw(java.lang.String) @bci=20, line=51 (Interpreted frame)
 - scala.util.parsing.json.JSON$.parseFull(java.lang.String) @bci=2, line=65 (Interpreted frame)

with the code in Spark

val readFromLzo = (path: String) => {sc.textFile(path)
    .map{ row =>
JSON.parseFull(row).getOrElse(Map()).asInstanceOf[Map[String,Any]]}}

[Jasper-M]

@bingbai0912 You're using, in a distributed and multi threaded environment, a class that is both deprecated and doesn't pretend to be thread safe. I think that's the issue you need to solve. You'd have to at least make sure that the same parser isn't shared between threads, and probably best to use a JSON parser that's not deprecated.

[SethTisue]

@bingbai0912 background on scala.util.parsing.combinator being deprecated: scala/scala-parser-combinators#99