Roman Elizarov | f16fd27 | 2017-02-07 11:26:00 +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 | f16fd27 | 2017-02-07 11:26:00 +0300 | [diff] [blame] | 3 | */ |
| 4 | |
Roman Elizarov | 0950dfa | 2018-07-13 10:33:25 +0300 | [diff] [blame] | 5 | package kotlinx.coroutines.internal |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 6 | |
Roman Elizarov | 0950dfa | 2018-07-13 10:33:25 +0300 | [diff] [blame] | 7 | import kotlinx.coroutines.TestBase |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 8 | import org.junit.Test |
| 9 | import java.util.* |
| 10 | import java.util.concurrent.atomic.AtomicInteger |
| 11 | import kotlin.concurrent.thread |
Roman Elizarov | 0950dfa | 2018-07-13 10:33:25 +0300 | [diff] [blame] | 12 | import kotlin.sequences.buildIterator |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 13 | |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 14 | /** |
| 15 | * This stress test has 2 threads adding on one side on list, 2 more threads adding on the other, |
| 16 | * and 6 threads iterating and concurrently removing items. The resulting list that is being |
| 17 | * stressed is long. |
| 18 | */ |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 19 | class LockFreeLinkedListLongStressTest : 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 | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 22 | |
| 23 | val threads = mutableListOf<Thread>() |
Vsevolod Tolstopyatov | a2d8088 | 2018-09-24 19:51:49 +0300 | [diff] [blame] | 24 | private val nAdded = 10_000_000 // should not stress more, because that'll run out of memory |
| 25 | private val nAddThreads = 4 // must be power of 2 (!!!) |
| 26 | private val nRemoveThreads = 6 |
| 27 | private val removeProbability = 0.2 |
| 28 | private val workingAdders = AtomicInteger(nAddThreads) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 29 | |
Vsevolod Tolstopyatov | a2d8088 | 2018-09-24 19:51:49 +0300 | [diff] [blame] | 30 | private fun shallRemove(i: Int) = i and 63 != 42 |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 31 | |
| 32 | @Test |
| 33 | fun testStress() { |
Roman Elizarov | d3d335b | 2017-10-21 17:43:53 +0300 | [diff] [blame] | 34 | println("--- LockFreeLinkedListLongStressTest") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 35 | for (j in 0 until nAddThreads) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 36 | threads += thread(start = false, name = "adder-$j") { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 37 | for (i in j until nAdded step nAddThreads) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 38 | list.addLast(IntNode(i)) |
| 39 | } |
Roman Elizarov | 12f961d | 2017-02-06 15:44:03 +0300 | [diff] [blame] | 40 | println("${Thread.currentThread().name} completed") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 41 | workingAdders.decrementAndGet() |
| 42 | } |
| 43 | for (j in 0 until nRemoveThreads) |
| 44 | threads += thread(start = false, name = "remover-$j") { |
| 45 | val rnd = Random() |
| 46 | do { |
| 47 | val lastTurn = workingAdders.get() == 0 |
| 48 | list.forEach<IntNode> { node -> |
| 49 | if (shallRemove(node.i) && (lastTurn || rnd.nextDouble() < removeProbability)) |
| 50 | node.remove() |
| 51 | } |
| 52 | } while (!lastTurn) |
Roman Elizarov | 12f961d | 2017-02-06 15:44:03 +0300 | [diff] [blame] | 53 | println("${Thread.currentThread().name} completed") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 54 | } |
| 55 | println("Starting ${threads.size} threads") |
| 56 | for (thread in threads) |
| 57 | thread.start() |
| 58 | println("Joining threads") |
| 59 | for (thread in threads) |
| 60 | thread.join() |
| 61 | // verification |
| 62 | println("Verify result") |
| 63 | list.validate() |
Roman Elizarov | 0950dfa | 2018-07-13 10:33:25 +0300 | [diff] [blame] | 64 | val expected = iterator { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 65 | for (i in 0 until nAdded) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 66 | if (!shallRemove(i)) |
| 67 | yield(i) |
| 68 | } |
| 69 | list.forEach<IntNode> { node -> |
| 70 | require(node.i == expected.next()) |
| 71 | } |
| 72 | require(!expected.hasNext()) |
| 73 | } |
| 74 | } |