ClassCastException in Lincheck

[bbrockbernd]

Lincheck version 2.34

Trace:

Wow! You've caught a bug in Lincheck.
We kindly ask to provide an issue here: https://github.com/JetBrains/lincheck/issues,
attaching a stack trace printed below and the code that causes the error.

Exception stacktrace:
java.lang.ClassCastException

org.jetbrains.kotlinx.lincheck.LincheckAssertionError: 
Wow! You've caught a bug in Lincheck.
We kindly ask to provide an issue here: https://github.com/JetBrains/lincheck/issues,
attaching a stack trace printed below and the code that causes the error.

Exception stacktrace:
java.lang.ClassCastException

	at org.jetbrains.kotlinx.lincheck.LinChecker$check$1.invoke(LinChecker.kt:48)
	at org.jetbrains.kotlinx.lincheck.LinChecker$check$1.invoke(LinChecker.kt:47)
	at org.jetbrains.kotlinx.lincheck.LinChecker.checkImpl$lincheck(LinChecker.kt:67)
	at org.jetbrains.kotlinx.lincheck.LinChecker.check(LinChecker.kt:47)
	at org.jetbrains.kotlinx.lincheck.LinChecker$Companion.check(LinChecker.kt:195)
	at org.jetbrains.kotlinx.lincheck.LinCheckerKt.check(LinChecker.kt:295)
	at reproClassCast.LinCheckTest.stressTest(Unknown Source)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:568)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:59)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:56)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
	at org.junit.runners.BlockJUnit4ClassRunner$1.evaluate(BlockJUnit4ClassRunner.java:100)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:366)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:103)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:63)
	at org.junit.runners.ParentRunner$4.run(ParentRunner.java:331)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:79)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:329)
	at org.junit.runners.ParentRunner.access$100(ParentRunner.java:66)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:293)
	at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:413)
	at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecutor.runTestClass(JUnitTestClassExecutor.java:112)
	at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecutor.execute(JUnitTestClassExecutor.java:58)
	at org.gradle.api.internal.tasks.testing.junit.JUnitTestClassExecutor.execute(JUnitTestClassExecutor.java:40)
	at org.gradle.api.internal.tasks.testing.junit.AbstractJUnitTestClassProcessor.processTestClass(AbstractJUnitTestClassProcessor.java:60)
	at org.gradle.api.internal.tasks.testing.SuiteTestClassProcessor.processTestClass(SuiteTestClassProcessor.java:52)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
	at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.base/java.lang.reflect.Method.invoke(Method.java:568)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:36)
	at org.gradle.internal.dispatch.ReflectionDispatch.dispatch(ReflectionDispatch.java:24)
	at org.gradle.internal.dispatch.ContextClassLoaderDispatch.dispatch(ContextClassLoaderDispatch.java:33)
	at org.gradle.internal.dispatch.ProxyDispatchAdapter$DispatchingInvocationHandler.invoke(ProxyDispatchAdapter.java:94)
	at jdk.proxy1/jdk.proxy1.$Proxy2.processTestClass(Unknown Source)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker$2.run(TestWorker.java:176)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.executeAndMaintainThreadName(TestWorker.java:129)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.execute(TestWorker.java:100)
	at org.gradle.api.internal.tasks.testing.worker.TestWorker.execute(TestWorker.java:60)
	at org.gradle.process.internal.worker.child.ActionExecutionWorker.execute(ActionExecutionWorker.java:56)
	at org.gradle.process.internal.worker.child.SystemApplicationClassLoaderWorker.call(SystemApplicationClassLoaderWorker.java:119)
	at org.gradle.process.internal.worker.child.SystemApplicationClassLoaderWorker.call(SystemApplicationClassLoaderWorker.java:66)
	at worker.org.gradle.process.internal.worker.GradleWorkerMain.run(GradleWorkerMain.java:69)
	at worker.org.gradle.process.internal.worker.GradleWorkerMain.main(GradleWorkerMain.java:74)

DS under test:

package reproClassCast

import java.util.concurrent.atomic.*
import kotlin.math.absoluteValue

class ConcurrentHashTable<K : Any, V : Any>(initialCapacity: Int) {
    private val table = AtomicReference(Table(initialCapacity))

    fun put(key: K, value: V): V? {
        return table.get().put(key, value)
    }

    fun get(key: K): V? {
        return table.get().get(key)
    }

    fun remove(key: K): V? {
        return table.get().remove(key)
    }

    data class Fixed(val value: Any)

    inner class Table(val capacity: Int) {

        var resizeDone = false
        val keys = AtomicReferenceArray<Any?>(capacity)
        val values = AtomicReferenceArray<Any?>(capacity)
        val nextTable = AtomicReference<Table?>(null)

        fun put(key: K, value: V): V? {
            var index = index(key)
            repeat(MAX_PROBES) {
                while (true) {
                    val curKey = keys[index]
                    when (curKey) {
                        null -> {
                            if (!keys.compareAndSet(index, null, key)) continue
                            if (!values.compareAndSet(index, null, value)) continue
                            return null
                        }
                        key -> {
                            while (true) {
                                val currentValue = values[index]
                                if (currentValue == MOVED) {
                                    return resize { tab ->
                                        tab.put(key, value)
                                    } as V?
                                }
                                if (currentValue is Fixed) {
                                    return resize { tab ->
                                        tab.put(key, value)
                                    } as V?
                                }
                                if (!values.compareAndSet(index, currentValue, value)) continue
                                return currentValue as V?
                            }
                        }
                    }
                    index = (index + 1) % capacity
                    break
                }
            }
            return resize { tab ->
                tab.put(key, value)
            } as V?
        }

        fun get(key: K): V? {
            var index = index(key)
            repeat(MAX_PROBES) {
                val curKey = keys[index]
                when (curKey) {
                    key -> {
                        val curValue = values[index]
                        if (curValue == MOVED) {
                            resize()
                            return table.get()!!.get(key)
                        }
                        if (curValue is Fixed) {
                            return curValue.value as V?
                        }
                        return values[index] as V?
                    }
                    null -> {
                        return null
                    }
                }
                index = (index + 1) % capacity
            }
            return null
        }

        fun remove(key: K): V? {
            var index = index(key)
            repeat(MAX_PROBES) {
                val curKey = keys[index]
                when (curKey) {
                    key -> {
                        while (true) {
                            val curValue = values[index]
                            if (curValue == MOVED) {
                                return resize { tab ->
                                    tab.remove(key)
                                } as V?
                            }
                            if (curValue is Fixed) {
                                return resize { tab ->
                                    tab.remove(key)
                                } as V?
                            }
                            if (!values.compareAndSet(index, curValue, null)) continue
                            return curValue as V?
                        }
                    }
                    null -> {
                        return null
                    }
                }
                index = (index + 1) % capacity
            }
            return null
        }

        fun resize(doAfter: (Table) -> Any? = { null }): Any? {
            nextTable.compareAndSet(null, Table(capacity * 2))
            val next = nextTable.get()!!

            for (i in 0 ..< capacity) {
                while (true) {
                    val curKey = keys[i]
                    val curValue = values[i]

                    // if already moved continue
                    if (curValue == MOVED) break

                    // if empty or removed -> MOVED
                    if (curValue == null) {
                        if (!values.compareAndSet(i, null, MOVED)) continue
                        break
                    }

                    // if fixed -> put value and set MOVED
                    if (curValue is Fixed) {
                        // Set value in new table
                        next.put(curKey as K, curValue.value as V)

                        // Set value to moved in this table
                        if (!values.compareAndSet(i, curValue, MOVED)) continue
                        break
                    }

                    // if normal value -> fix
                    values.compareAndSet(i, curValue, Fixed(curValue))
                }
            }
            val resultAfter = doAfter(next)
            resizeDone = true

            //Update table reference
            while (true) {
                val currentTable = table.get()
                if (currentTable.capacity < this.capacity) break
                if (currentTable.nextTable.get() == null) break
                if (currentTable.nextTable.get() != null && !currentTable.resizeDone) {
                    currentTable.resize()
                    continue
                }
                table.compareAndSet(currentTable, currentTable.nextTable.get())
            }

            return resultAfter

        }

        private fun index(key: Any) = ((key.hashCode() * MAGIC) % capacity).absoluteValue
    }
}

private const val MAGIC = -0x61c88647 // golden ratio 
private const val MAX_PROBES = 2
private val MOVED = Any()

Test class:

package reproClassCast

import org.jetbrains.kotlinx.lincheck.annotations.Operation
import org.jetbrains.kotlinx.lincheck.check
import org.jetbrains.kotlinx.lincheck.strategy.stress.StressOptions
import kotlin.test.Test

class LinCheckTest {

    @Test
    fun stressTest() = StressOptions()
        .iterations(300)
        .invocationsPerIteration(25_000)
        .actorsBefore(1)
        .threads(3)
        .actorsPerThread(3)
        .actorsAfter(0)
        .check(this::class.java)

    
    private val hashTable = ConcurrentHashTable<Int, Int>(initialCapacity = 2)

    @Operation
    fun put(key: Int, value: Int): Int? = hashTable.put(key, value)

    @Operation
    fun get(key: Int): Int? = hashTable.get(key)

    @Operation
    fun remove(key: Int): Int? = hashTable.remove(key)

}

[eupp]

Hi @bbrockbernd !

So the issue in fact was that Lincheck incorrectly classified the exception as internal Lincheck error, but in fact it was actual exception/bug in the test. This PR should fix the related check in the Lincheck codebase #417

After the fix, the output of the test looks as follows:

= Invalid execution results =
| ------------------------------------------------------------ |
|            Thread 1            |     Thread 2     | Thread 3 |
| ------------------------------------------------------------ |
| put(-1, 2): null               |                  |          |
| put(-2, 3): null               |                  |          |
| ------------------------------------------------------------ |
| get(-2): ClassCastException #1 | put(1, -2): null |          |
| ------------------------------------------------------------ |

The problem in the test is in the following lines of the get method:

val curValue = values[index]
if (curValue == MOVED) {
    resize()
    return table.get()!!.get(key)
}
if (curValue is Fixed) {
    return curValue.value as V?
}
return values[index] as V?

The code first reads from values[index], checks if the value is instance of class Fixed, but then again reads from values[index] -- this second read may still read object of class Fixed, and then the cast to V? fails.

So the last line should be:

return curValue as V?