Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 1 | /* |
Roman Elizarov | 1f74a2d | 2018-06-29 19:19:45 +0300 | [diff] [blame^] | 2 | * Copyright 2016-2018 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license. |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 3 | */ |
| 4 | |
| 5 | package kotlinx.coroutines.experimental.internal |
| 6 | |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 7 | import kotlinx.coroutines.experimental.TestBase |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 8 | import org.junit.Assert.* |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 9 | import org.junit.Test |
| 10 | import java.util.* |
| 11 | import java.util.concurrent.atomic.AtomicInteger |
| 12 | import kotlin.concurrent.thread |
| 13 | |
| 14 | /** |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 15 | * This stress test has 6 threads adding randomly first to the list and them immediately undoing |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 16 | * this addition by remove, and 4 threads removing first node. The resulting list that is being |
| 17 | * stressed is very short. |
| 18 | */ |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 19 | class LockFreeLinkedListShortStressTest : TestBase() { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 20 | data class IntNode(val i: Int) : LockFreeLinkedListNode() |
| 21 | val list = LockFreeLinkedListHead() |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 22 | |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 23 | val TEST_DURATION = 5000L * stressTestMultiplier |
| 24 | |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 25 | val threads = mutableListOf<Thread>() |
| 26 | val nAdderThreads = 6 |
| 27 | val nRemoverThreads = 4 |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 28 | val completedAdder = AtomicInteger() |
| 29 | val completedRemover = AtomicInteger() |
| 30 | |
| 31 | val undone = AtomicInteger() |
| 32 | val missed = AtomicInteger() |
| 33 | val removed = AtomicInteger() |
| 34 | |
| 35 | @Test |
| 36 | fun testStress() { |
Roman Elizarov | d3d335b | 2017-10-21 17:43:53 +0300 | [diff] [blame] | 37 | println("--- LockFreeLinkedListShortStressTest") |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 38 | val deadline = System.currentTimeMillis() + TEST_DURATION |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 39 | repeat(nAdderThreads) { threadId -> |
| 40 | threads += thread(start = false, name = "adder-$threadId") { |
| 41 | val rnd = Random() |
| 42 | while (System.currentTimeMillis() < deadline) { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 43 | var node: IntNode? = IntNode(threadId) |
| 44 | when (rnd.nextInt(3)) { |
| 45 | 0 -> list.addLast(node!!) |
| 46 | 1 -> assertTrue(list.addLastIf(node!!, { true })) // just to test conditional add |
| 47 | 2 -> { // just to test failed conditional add |
| 48 | assertFalse(list.addLastIf(node!!, { false })) |
| 49 | node = null |
| 50 | } |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 51 | } |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 52 | if (node != null) { |
| 53 | if (node.remove()) |
| 54 | undone.incrementAndGet() |
| 55 | else |
| 56 | missed.incrementAndGet() |
| 57 | } |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 58 | } |
| 59 | completedAdder.incrementAndGet() |
| 60 | } |
| 61 | } |
| 62 | repeat(nRemoverThreads) { threadId -> |
| 63 | threads += thread(start = false, name = "remover-$threadId") { |
| 64 | while (System.currentTimeMillis() < deadline) { |
| 65 | val node = list.removeFirstOrNull() |
| 66 | if (node != null) removed.incrementAndGet() |
| 67 | |
| 68 | } |
| 69 | completedRemover.incrementAndGet() |
| 70 | } |
| 71 | } |
| 72 | threads.forEach { it.start() } |
| 73 | threads.forEach { it.join() } |
| 74 | println("Completed successfully ${completedAdder.get()} adder threads") |
| 75 | println("Completed successfully ${completedRemover.get()} remover threads") |
| 76 | println(" Adders undone ${undone.get()} node additions") |
| 77 | println(" Adders missed ${missed.get()} nodes") |
| 78 | println("Remover removed ${removed.get()} nodes") |
| 79 | assertEquals(nAdderThreads, completedAdder.get()) |
| 80 | assertEquals(nRemoverThreads, completedRemover.get()) |
| 81 | assertEquals(missed.get(), removed.get()) |
| 82 | assertTrue(undone.get() > 0) |
| 83 | assertTrue(missed.get() > 0) |
| 84 | list.validate() |
| 85 | } |
| 86 | } |