Roman Elizarov | f16fd27 | 2017-02-07 11:26:00 +0300 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2016-2017 JetBrains s.r.o. |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Roman Elizarov | a567659 | 2017-01-19 10:31:13 +0300 | [diff] [blame] | 17 | package kotlinx.coroutines.experimental.internal |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 18 | |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 19 | import kotlinx.coroutines.experimental.TestBase |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 20 | import org.junit.Test |
| 21 | import java.util.* |
| 22 | import java.util.concurrent.atomic.AtomicInteger |
| 23 | import kotlin.concurrent.thread |
Roman Elizarov | ea4a51b | 2017-01-31 12:01:25 +0300 | [diff] [blame] | 24 | import kotlin.coroutines.experimental.buildIterator |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 25 | |
Roman Elizarov | fa612f9 | 2017-02-07 12:11:16 +0300 | [diff] [blame] | 26 | /** |
| 27 | * This stress test has 2 threads adding on one side on list, 2 more threads adding on the other, |
| 28 | * and 6 threads iterating and concurrently removing items. The resulting list that is being |
| 29 | * stressed is long. |
| 30 | */ |
Roman Elizarov | ebe18b4 | 2017-02-28 17:50:55 +0300 | [diff] [blame] | 31 | class LockFreeLinkedListLongStressTest : TestBase() { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 32 | data class IntNode(val i: Int) : LockFreeLinkedListNode() |
| 33 | val list = LockFreeLinkedListHead() |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 34 | |
| 35 | val threads = mutableListOf<Thread>() |
Roman Elizarov | 43604bd | 2017-03-02 23:19:59 +0300 | [diff] [blame] | 36 | val nAdded = 10_000_000 // should not stress more, because that'll run out of memory |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 37 | val nAddThreads = 4 // must be power of 2 (!!!) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 38 | val nRemoveThreads = 6 |
| 39 | val removeProbability = 0.2 |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 40 | val workingAdders = AtomicInteger(nAddThreads) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 41 | |
| 42 | fun shallRemove(i: Int) = i and 63 != 42 |
| 43 | |
| 44 | @Test |
| 45 | fun testStress() { |
Roman Elizarov | d3d335b | 2017-10-21 17:43:53 +0300 | [diff] [blame] | 46 | println("--- LockFreeLinkedListLongStressTest") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 47 | for (j in 0 until nAddThreads) |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 48 | threads += thread(start = false, name = "adder-$j") { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 49 | for (i in j until nAdded step nAddThreads) { |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 50 | list.addLast(IntNode(i)) |
| 51 | } |
Roman Elizarov | 12f961d | 2017-02-06 15:44:03 +0300 | [diff] [blame] | 52 | println("${Thread.currentThread().name} completed") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 53 | workingAdders.decrementAndGet() |
| 54 | } |
| 55 | for (j in 0 until nRemoveThreads) |
| 56 | threads += thread(start = false, name = "remover-$j") { |
| 57 | val rnd = Random() |
| 58 | do { |
| 59 | val lastTurn = workingAdders.get() == 0 |
| 60 | list.forEach<IntNode> { node -> |
| 61 | if (shallRemove(node.i) && (lastTurn || rnd.nextDouble() < removeProbability)) |
| 62 | node.remove() |
| 63 | } |
| 64 | } while (!lastTurn) |
Roman Elizarov | 12f961d | 2017-02-06 15:44:03 +0300 | [diff] [blame] | 65 | println("${Thread.currentThread().name} completed") |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 66 | } |
| 67 | println("Starting ${threads.size} threads") |
| 68 | for (thread in threads) |
| 69 | thread.start() |
| 70 | println("Joining threads") |
| 71 | for (thread in threads) |
| 72 | thread.join() |
| 73 | // verification |
| 74 | println("Verify result") |
| 75 | list.validate() |
| 76 | val expected = buildIterator { |
Roman Elizarov | ee7c0eb | 2017-02-16 15:29:28 +0300 | [diff] [blame] | 77 | for (i in 0 until nAdded) |
Roman Elizarov | 3754f95 | 2017-01-18 20:47:54 +0300 | [diff] [blame] | 78 | if (!shallRemove(i)) |
| 79 | yield(i) |
| 80 | } |
| 81 | list.forEach<IntNode> { node -> |
| 82 | require(node.i == expected.next()) |
| 83 | } |
| 84 | require(!expected.hasNext()) |
| 85 | } |
| 86 | } |