데이터 구조 테스트하기

Lincheck는 동시성 데이터 구조를 테스트하기 위한 선언적 인터페이스를 제공합니다. 테스트를 어떻게 수행할지 설명하는 대신, 테스트할 모든 작업을 선언하면 Lincheck가 동시성 실행 시나리오를 생성하고 실행한 뒤 결과를 분석합니다.

이 Counter 데이터 구조를 Lincheck로 테스트해 볼게요:

class Counter {
    var value = 0

    fun inc(): Int = ++value
    fun dec(): Int = --value
}

테스트 클래스를 만듭니다:
```
class CounterTest {
}
```
구조의 인스턴스를 담는 클래스 프로퍼티를 만듭니다:
```
private val c = Counter()
```
테스트할 작업을 멤버 함수로 선언하고 @Operation 어노테이션을 붙입니다:

이 어노테이션은 실행 시나리오를 생성할 때 Lincheck에 어떤 메서드를 포함할지 알려줍니다.
```
    @Operation
    fun inc() = c.inc()

    @Operation
    fun dec() = c.dec()
```
ModelCheckingOptions() 또는 StressOptions()를 사용해 테스트 함수를 멤버 함수로 선언하고 @Test 어노테이션을 붙입니다:

테스트 전략 문서에서 모델 체킹과 스트레스 테스트의 차이점을 배워 보세요.
```
    @Test
    fun test() = ModelCheckingOptions().check(this::class)
```
테스트를 실행합니다. 실패하면 Lincheck는 잘못된 동작을 유발한 시나리오와 실행 트레이스를 담은 오류 리포트를 생성합니다:
```
= Invalid execution results =
| -------------------- |
| Thread 1  | Thread 2 |
| -------------------- |
| dec(): -1 | inc(): 1 |
| -------------------- |
```

출처: How to test data structures

본문

테스트 과정

데이터 구조를 테스트할 때 Lincheck는 실행 시나리오 목록을 생성하고, 이를 실행한 뒤 결과를 분석합니다.

이 Counter 데이터 구조를 생각해 볼게요:

테스트를 위해 Lincheck는 다음 단계를 수행합니다:

선언된 작업을 여러 스레드에 무작위로 배치하여 무작위 실행 시나리오 목록을 생성합니다:

구성 옵션으로 스레드 수와 스레드당 작업 수를 지정할 수 있어요.
지정된 테스트 전략(모델 체킹 또는 스트레스 테스트)으로 생성된 시나리오를 실행합니다. 생성된 각 시나리오는 서로 다른 실행 스케줄을 검사하기 위해 여러 번 실행됩니다:
실행 결과를 정확성(correctness) 속성과 대조해 검증합니다. 기본값은 선형화 가능성(linearizability)입니다.

이 단계에서 검증 함수를 제공하면 Lincheck가 구조를 검증할 수도 있습니다.

예제: Treiber 스택 구조 구현 테스트

이 Treiber Stack의 잘못된 구현을 살펴보겠습니다:

class TreiberStack<E> {
    private val top = AtomicReference<Node<E>?>(null)

    fun push(item: E) {
        val newHead = Node(item)
        var oldHead: Node<E>?

        do {
            oldHead = top.get()
            newHead.next = oldHead
        } while (!top.compareAndSet(oldHead, newHead))
    }

    fun pop(): E? {
        val oldHead = top.get()

        if (oldHead == null) {
            return null
        }

        val newHead = oldHead.next
        top.compareAndSet(oldHead, newHead)

        // Bug: by the time `pop()` finishes execution,
        // another thread might have already popped this item.
        return oldHead.item
    }

    private class Node<E>(
        val item: E,
        var next: Node<E>? = null
    )
}

이 구조를 Lincheck로 테스트해서 주입된 버그가 프로그램의 동작에 어떤 영향을 주는지 살펴볼 수 있어요:

테스트 구조를 만듭니다:

class TreiberStackTest {
    private val stack = TreiberStack<Int>()

    @Operation
    fun push(value: Int) = stack.push(value)

    @Operation
    fun pop(): Int? = stack.pop()

    @Test
    fun modelCheckingTest() = ModelCheckingOptions()
        .check(this::class)
}

테스트를 실행합니다. Lincheck는 오류 리포트를 생성하고 잘못된 동작을 유발하는 실행 시나리오를 제공합니다:

이 다이어그램은 작업이 여러 스레드에 어떻게 배치되는지와 각 작업의 반환값을 보여줍니다. Lincheck는 잘못된 결과를 유발하는 특정 스레드 인터리빙도 제공합니다:

구현이 다른 스레드가 pop() 함수를 중단시키는 상황을 고려하지 않기 때문에, pop()이 1을 두 번 반환하게 되며 이는 가능하면 안 되는 상황입니다.

| ------------------------------ |
|   Thread 1    |    Thread 2    |
| ------------------------------ |
| push(1): void |                |
| ------------------------------ |
| pop(): 1      | push(-1): void |
| ------------------------------ |
| pop(): -1     |                |
| pop(): 1      |                |
| ------------------------------ |

| ----------------------------------------------------- |
|                  Thread 1                  | Thread 2 |
| ----------------------------------------------------- |
| push(1)                                    |          |
| ----------------------------------------------------- |
| pop(): 1                                   |          |
|   stack.pop(): 1                           |          |
|     top.get(): Node#1                      |          |
|     switch                                 |          |
|                                            | push(-1) |
|     oldHead.getNext(): null                |          |
|     top.compareAndSet(Node#1, null): false |          |
|     oldHead.getItem(): 1                   |          |
|   result: 1                                |          |
| ----------------------------------------------------- |
| pop(): -1                                  |          |
| pop(): 1                                   |          |
| ----------------------------------------------------- |

데이터 구조를 수정합니다. 올바른 구현은 결과를 반환하기 전에 oldHead 변수를 가장 최근 값으로 갱신합니다:

    fun pop(): E? {
        var oldHead: Node<E>?
        var newHead: Node<E>?

        do {
            oldHead = top.get()
            if (oldHead == null) return null
            newHead = oldHead.next
        } while (!top.compareAndSet(oldHead, newHead))

        return oldHead.item
     }

데이터 구조 테스트하기