Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +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 | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 3 | */ |
| 4 | |
| 5 | package kotlinx.coroutines.experimental.internal |
| 6 | |
| 7 | import kotlinx.atomicfu.LockFreedomTestEnvironment |
| 8 | import kotlinx.coroutines.experimental.TestBase |
| 9 | import org.junit.Assert.* |
| 10 | import org.junit.Test |
| 11 | import java.util.* |
| 12 | import java.util.concurrent.atomic.AtomicLong |
| 13 | import java.util.concurrent.atomic.AtomicReference |
| 14 | |
| 15 | /** |
| 16 | * This stress test has 4 threads adding randomly to the list and them immediately undoing |
| 17 | * this addition by remove, and 4 threads trying to remove nodes from two lists simultaneously (atomically). |
| 18 | */ |
| 19 | class LockFreeLinkedListAtomicStressLFTest : TestBase() { |
| 20 | private val env = LockFreedomTestEnvironment("LockFreeLinkedListAtomicStressLFTest") |
| 21 | |
| 22 | data class IntNode(val i: Int) : LockFreeLinkedListNode() |
| 23 | |
Roman Elizarov | e7f9b5f | 2017-08-16 23:24:07 +0300 | [diff] [blame] | 24 | private val TEST_DURATION_SEC = 5 * stressTestMultiplier |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 25 | |
| 26 | val nLists = 4 |
| 27 | val nAdderThreads = 4 |
| 28 | val nRemoverThreads = 4 |
| 29 | |
| 30 | val lists = Array(nLists) { LockFreeLinkedListHead() } |
| 31 | |
| 32 | val undone = AtomicLong() |
| 33 | val missed = AtomicLong() |
| 34 | val removed = AtomicLong() |
| 35 | val error = AtomicReference<Throwable>() |
| 36 | |
| 37 | @Test |
| 38 | fun testStress() { |
| 39 | repeat(nAdderThreads) { threadId -> |
| 40 | val rnd = Random() |
| 41 | env.testThread(name = "adder-$threadId") { |
| 42 | when (rnd.nextInt(4)) { |
| 43 | 0 -> { |
| 44 | val list = lists[rnd.nextInt(nLists)] |
| 45 | val node = IntNode(threadId) |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 46 | addLastOp(list, node) |
Roman Elizarov | 4ecd46b | 2017-08-15 11:15:08 +0300 | [diff] [blame] | 47 | randomSpinWaitIntermission() |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 48 | tryRemoveOp(node) |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 49 | } |
| 50 | 1 -> { |
| 51 | // just to test conditional add |
| 52 | val list = lists[rnd.nextInt(nLists)] |
| 53 | val node = IntNode(threadId) |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 54 | addLastIfTrueOp(list, node) |
Roman Elizarov | 4ecd46b | 2017-08-15 11:15:08 +0300 | [diff] [blame] | 55 | randomSpinWaitIntermission() |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 56 | tryRemoveOp(node) |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 57 | } |
| 58 | 2 -> { |
| 59 | // just to test failed conditional add and burn some time |
| 60 | val list = lists[rnd.nextInt(nLists)] |
| 61 | val node = IntNode(threadId) |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 62 | addLastIfFalseOp(list, node) |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 63 | } |
| 64 | 3 -> { |
| 65 | // add two atomically |
| 66 | val idx1 = rnd.nextInt(nLists - 1) |
| 67 | val idx2 = idx1 + 1 + rnd.nextInt(nLists - idx1 - 1) |
| 68 | check(idx1 < idx2) // that is our global order |
| 69 | val list1 = lists[idx1] |
| 70 | val list2 = lists[idx2] |
| 71 | val node1 = IntNode(threadId) |
| 72 | val node2 = IntNode(-threadId - 1) |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 73 | addTwoOp(list1, node1, list2, node2) |
Roman Elizarov | 4ecd46b | 2017-08-15 11:15:08 +0300 | [diff] [blame] | 74 | randomSpinWaitIntermission() |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 75 | tryRemoveOp(node1) |
Roman Elizarov | 4ecd46b | 2017-08-15 11:15:08 +0300 | [diff] [blame] | 76 | randomSpinWaitIntermission() |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 77 | tryRemoveOp(node2) |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 78 | } |
| 79 | else -> error("Cannot happen") |
| 80 | } |
| 81 | } |
| 82 | } |
| 83 | repeat(nRemoverThreads) { threadId -> |
| 84 | val rnd = Random() |
| 85 | env.testThread(name = "remover-$threadId") { |
| 86 | val idx1 = rnd.nextInt(nLists - 1) |
| 87 | val idx2 = idx1 + 1 + rnd.nextInt(nLists - idx1 - 1) |
| 88 | check(idx1 < idx2) // that is our global order |
| 89 | val list1 = lists[idx1] |
| 90 | val list2 = lists[idx2] |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 91 | removeTwoOp(list1, list2) |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 92 | } |
| 93 | } |
| 94 | env.performTest(TEST_DURATION_SEC) { |
| 95 | val _undone = undone.get() |
| 96 | val _missed = missed.get() |
| 97 | val _removed = removed.get() |
| 98 | println(" Adders undone $_undone node additions") |
| 99 | println(" Adders missed $_missed nodes") |
| 100 | println("Remover removed $_removed nodes") |
| 101 | } |
| 102 | error.get()?.let { throw it } |
| 103 | assertEquals(missed.get(), removed.get()) |
| 104 | assertTrue(undone.get() > 0) |
| 105 | assertTrue(missed.get() > 0) |
| 106 | lists.forEach { it.validate() } |
| 107 | } |
| 108 | |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 109 | private fun addLastOp(list: LockFreeLinkedListHead, node: IntNode) { |
| 110 | list.addLast(node) |
| 111 | } |
| 112 | |
| 113 | private fun addLastIfTrueOp(list: LockFreeLinkedListHead, node: IntNode) { |
| 114 | assertTrue(list.addLastIf(node, { true })) |
| 115 | } |
| 116 | |
| 117 | private fun addLastIfFalseOp(list: LockFreeLinkedListHead, node: IntNode) { |
| 118 | assertFalse(list.addLastIf(node, { false })) |
| 119 | } |
| 120 | |
| 121 | private fun addTwoOp(list1: LockFreeLinkedListHead, node1: IntNode, list2: LockFreeLinkedListHead, node2: IntNode) { |
| 122 | val add1 = list1.describeAddLast(node1) |
| 123 | val add2 = list2.describeAddLast(node2) |
| 124 | val op = object : AtomicOp<Any?>() { |
| 125 | override fun prepare(affected: Any?): Any? = |
| 126 | add1.prepare(this) ?: |
| 127 | add2.prepare(this) |
| 128 | |
| 129 | override fun complete(affected: Any?, failure: Any?) { |
| 130 | add1.complete(this, failure) |
| 131 | add2.complete(this, failure) |
| 132 | } |
| 133 | } |
| 134 | assertTrue(op.perform(null) == null) |
| 135 | } |
| 136 | |
| 137 | private fun tryRemoveOp(node: IntNode) { |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 138 | if (node.remove()) |
| 139 | undone.incrementAndGet() |
| 140 | else |
| 141 | missed.incrementAndGet() |
| 142 | } |
Roman Elizarov | e1f89db | 2017-08-16 15:08:30 +0300 | [diff] [blame] | 143 | |
| 144 | private fun removeTwoOp(list1: LockFreeLinkedListHead, list2: LockFreeLinkedListHead) { |
| 145 | val remove1 = list1.describeRemoveFirst() |
| 146 | val remove2 = list2.describeRemoveFirst() |
| 147 | val op = object : AtomicOp<Any?>() { |
| 148 | override fun prepare(affected: Any?): Any? = |
| 149 | remove1.prepare(this) ?: |
| 150 | remove2.prepare(this) |
| 151 | |
| 152 | override fun complete(affected: Any?, failure: Any?) { |
| 153 | remove1.complete(this, failure) |
| 154 | remove2.complete(this, failure) |
| 155 | } |
| 156 | } |
| 157 | val success = op.perform(null) == null |
| 158 | if (success) removed.addAndGet(2) |
| 159 | } |
| 160 | |
Roman Elizarov | 7eb41ef | 2017-08-10 21:09:26 +0300 | [diff] [blame] | 161 | } |