XArray

XArray

.. SPDX-License-Identifier: GPL-2.0+

XArray

저자: Matthew Wilcox

개요

개요

XArray는 매우 큰 pointer 배열처럼 동작하는 추상 자료형입니다. Hash나 일반적인 크기 조절 가능 배열과 같은 요구를 많이 충족합니다. Hash와 달리 cache 효율적인 방식으로 다음 또는 이전 entry로 이동할 수 있습니다. 크기 조절 가능 배열과 달리 배열을 확장하기 위해 data를 복사하거나 MMU mapping을 변경할 필요가 없습니다. Doubly-linked list보다 memory 효율적이고 병렬화하기 쉬우며 cache 친화적입니다. RCU를 활용하여 lock 없이 lookup을 수행합니다.

XArray 구현은 사용하는 index가 조밀하게 모여 있을 때 효율적입니다. Object를 hashing하고 그 hash를 index로 사용하면 성능이 좋지 않습니다. XArray는 작은 index에 최적화되어 있지만 큰 index에서도 좋은 성능을 냅니다. Index가 `ULONG_MAX`보다 클 수 있다면 XArray는 적합한 자료형이 아닙니다. XArray의 가장 중요한 사용자는 page cache입니다.

일반 pointer는 XArray에 직접 저장할 수 있습니다. Pointer는 4-byte alignment를 만족해야 하며, `kmalloc()`과 `alloc_page()`가 반환하는 모든 pointer가 이에 해당합니다. 임의의 user-space pointer나 function pointer에는 이 조건이 성립하지 않습니다. 정적으로 할당한 object도 alignment가 최소 4라면 pointer를 저장할 수 있습니다.

0부터 `LONG_MAX` 사이의 integer도 XArray에 저장할 수 있습니다. 먼저 `xa_mk_value()`를 사용해 entry로 변환해야 합니다. XArray에서 entry를 가져온 뒤 `xa_is_value()`로 value entry인지 검사하고 `xa_to_value()`로 다시 integer로 변환할 수 있습니다.

XArray에 저장하는 pointer에 tag를 붙여야 하는 사용자도 있습니다. `xa_tag_pointer()`는 tag가 있는 entry를 만들고, `xa_untag_pointer()`는 tagged entry를 tag가 없는 pointer로 되돌리며, `xa_pointer_tag()`는 entry의 tag를 가져옵니다. Tagged pointer는 value entry와 일반 pointer를 구분하는 bit를 함께 사용하므로, 특정 XArray에는 value entry와 tagged pointer 중 어느 것을 저장할지 결정해야 합니다.

일부 `IS_ERR()` pointer는 value entry 또는 internal entry와 충돌하므로 XArray는 `IS_ERR()` pointer 저장을 지원하지 않습니다.

XArray의 특이한 기능 중 하나는 일정한 index 범위를 차지하는 entry를 만들 수 있다는 점입니다. 저장 후에는 범위 안의 어느 index를 lookup해도 다른 index와 같은 entry를 반환하며, 어느 index에 저장하더라도 전체 범위에 저장됩니다. Multi-index entry는 명시적으로 더 작은 entry로 분할할 수 있습니다. `xa_erase()` 또는 `NULL`을 전달한 `xa_store()`로 어느 entry든 해제하면 XArray는 그 범위 정보를 잊습니다.

일반 API

일반 API

정적으로 할당한 XArray는 `DEFINE_XARRAY()`로, 동적으로 할당한 XArray는 `xa_init()`으로 초기화합니다. 새로 초기화한 XArray의 모든 index에는 `NULL` pointer가 들어 있습니다.

`xa_store()`로 entry를 설정하고 `xa_load()`로 가져옵니다. `xa_store()`는 index의 기존 entry를 새 entry로 덮어쓰고 이전 entry를 반환합니다. `xa_erase()`를 사용하거나 `xa_store()`로 `NULL`을 저장하여 entry를 해제할 수 있습니다. 한 번도 저장하지 않은 entry, `xa_erase()`로 지운 entry, 가장 최근에 `NULL`을 저장한 entry는 동일합니다. 단, XArray를 `XA_FLAGS_ALLOC`으로 초기화한 경우는 예외입니다.

`xa_cmpxchg()`를 사용하면 index의 entry를 조건부로 교체할 수 있습니다. `cmpxchg()`와 마찬가지로 해당 entry가 `old` 값일 때만 성공합니다. 이 함수는 그 index에 있던 entry도 반환하며, 전달한 `old`와 같은 entry가 반환되면 `xa_cmpxchg()`가 성공한 것입니다.

현재 index의 entry가 `NULL`일 때만 새 entry를 저장하려면 `xa_insert()`를 사용합니다. Entry가 비어 있지 않으면 `-EBUSY`를 반환합니다.

`xa_extract()`를 호출하면 XArray의 entry를 일반 배열로 복사할 수 있습니다. `xa_for_each()`, `xa_for_each_start()`, `xa_for_each_range()`로 현재 존재하는 entry를 순회할 수도 있습니다. 다음 present entry로 이동할 때는 `xa_find()` 또는 `xa_find_after()`가 더 알맞을 수 있습니다.

`xa_store_range()`는 일정한 index 범위에 같은 entry를 저장합니다. 이때 일부 다른 operation은 다소 특이하게 동작합니다. 예를 들어 한 index의 entry에 mark를 설정하면 다른 index 중 일부에만 mark가 설정될 수 있고, 한 index에 저장하면 다른 index 중 일부에서 가져오는 entry만 바뀔 수 있습니다.

이후의 `xa_store()`가 memory를 할당하지 않도록 보장해야 할 때가 있습니다. `xa_reserve()`는 지정한 index에 reserved entry를 저장하며 일반 API 사용자는 이를 `NULL`로 봅니다. Reserved entry가 필요 없어지면 `xa_release()`로 사용하지 않은 entry를 제거합니다. 그 사이 다른 사용자가 entry에 저장했다면 `xa_release()`는 아무것도 하지 않습니다. Entry를 반드시 `NULL`로 만들려면 `xa_erase()`를 사용해야 합니다. Reserved entry에 대한 `xa_insert()`는 실패합니다.

배열의 모든 entry가 `NULL`이면 `xa_empty()`가 `true`를 반환합니다.

마지막으로 `xa_destroy()`를 호출하면 XArray의 모든 entry를 제거할 수 있습니다. Entry가 pointer라면 먼저 해제해야 할 수 있으며, `xa_for_each()` iterator로 모든 present entry를 순회하여 처리할 수 있습니다.

검색 mark

검색 mark

배열의 각 entry에는 mark라고 부르는 bit 세 개가 연결됩니다. 각 mark는 서로 독립적으로 설정하거나 지울 수 있습니다. `xa_for_each_marked()` iterator로 mark가 설정된 entry를 순회할 수 있습니다.

`xa_get_mark()`로 entry에 mark가 설정되었는지 확인합니다. Entry가 `NULL`이 아니면 `xa_set_mark()`로 mark를 설정하고 `xa_clear_mark()`로 제거할 수 있습니다. `xa_marked()`는 특정 mark가 설정된 entry가 XArray에 하나라도 있는지 확인합니다. XArray에서 entry를 지우면 그 entry와 연결된 모든 mark도 지워집니다.

Multi-index entry의 어느 index에서 mark를 설정하거나 지우더라도 그 entry가 포함하는 모든 index에 영향을 줍니다. 어느 index에서 mark를 조회해도 같은 결과가 반환됩니다.

Mark가 없는 entry를 순회하는 방법은 없습니다. 이 자료 구조로는 이를 효율적으로 구현할 수 없기 때문입니다. 현재는 `XA_MARK_1`과 `XA_MARK_2`가 모두 설정된 entry 또는 `XA_MARK_0`이나 `XA_MARK_2`가 설정된 entry처럼 bit의 논리 조합을 검색하는 iterator도 없습니다. 사용 사례가 생기면 추가할 수 있습니다.

할당형 XArray

할당형 XArray

`DEFINE_XARRAY_ALLOC()`으로 XArray를 정의하거나 `XA_FLAGS_ALLOC`을 `xa_init_flags()`에 전달해 초기화하면, XArray는 entry가 사용 중인지 추적하는 방식으로 바뀝니다.

`xa_alloc()`은 XArray의 사용하지 않는 index에 entry를 저장합니다. Interrupt context에서 배열을 수정해야 한다면 ID를 할당하는 동안 interrupt를 비활성화하는 `xa_alloc_bh()` 또는 `xa_alloc_irq()`를 사용할 수 있습니다.

`xa_store()`, `xa_cmpxchg()`, `xa_insert()`도 entry를 allocated 상태로 표시합니다. 일반 XArray와 달리 `NULL` 저장도 `xa_reserve()`처럼 entry를 사용 중으로 표시합니다. Entry를 해제하려면 `xa_erase()`를 사용하고, entry가 `NULL`인 경우에만 해제하려면 `xa_release()`를 사용합니다.

기본적으로 가장 낮은 free entry를 0부터 할당합니다. 1부터 할당하려면 `DEFINE_XARRAY_ALLOC1()` 또는 `XA_FLAGS_ALLOC1`을 사용하는 편이 효율적입니다. 최대값까지 ID를 할당한 뒤 가장 낮은 free ID로 되돌아가려면 `xa_alloc_cyclic()`을 사용합니다.

할당형 XArray에서는 `XA_MARK_0`이 entry의 free 여부를 추적하는 데 사용되므로 사용자가 쓸 수 없습니다. 나머지 mark는 사용할 수 있습니다.

Memory 할당

Memory 할당

`xa_store()`, `xa_cmpxchg()`, `xa_alloc()`, `xa_reserve()`, `xa_insert()`는 entry 저장에 memory가 필요할 때를 위해 `gfp_t` parameter를 받습니다. Entry를 삭제하는 경우에는 memory를 할당할 필요가 없으므로 지정한 GFP flag를 무시합니다.

특히 제한적인 GFP flag를 전달하면 memory를 전혀 할당할 수 없을 수 있습니다. 이때 함수들은 `xa_err()`로 errno로 변환할 수 있는 특별한 값을 반환합니다. 정확히 어떤 error인지 알 필요가 없다면 `xa_is_err()`가 조금 더 효율적입니다.

Locking 분류

Locking

일반 API를 사용할 때는 locking을 직접 처리할 필요가 없습니다. XArray는 RCU와 내부 spinlock으로 access를 동기화합니다.

Lock이 필요 없는 함수:

• xa_empty()
• xa_marked()

RCU read lock을 획득하는 함수와 iterator:

• xa_load()
• xa_for_each()
• xa_for_each_start()
• xa_for_each_range()
• xa_find()
• xa_find_after()
• xa_extract()
• xa_get_mark()

내부에서 `xa_lock`을 획득하는 함수:

• xa_store()
• xa_store_bh()
• xa_store_irq()
• xa_insert()
• xa_insert_bh()
• xa_insert_irq()
• xa_erase()
• xa_erase_bh()
• xa_erase_irq()
• xa_cmpxchg()
• xa_cmpxchg_bh()
• xa_cmpxchg_irq()
• xa_store_range()
• xa_alloc()
• xa_alloc_bh()
• xa_alloc_irq()
• xa_reserve()
• xa_reserve_bh()
• xa_reserve_irq()
• xa_destroy()
• xa_set_mark()
• xa_clear_mark()

진입 시 `xa_lock`이 이미 잡혀 있다고 가정하는 함수:

• __xa_store()
• __xa_insert()
• __xa_erase()
• __xa_cmpxchg()
• __xa_alloc()
• __xa_set_mark()
• __xa_clear_mark()

Locking 사용 방법

XArray에 저장한 자료 구조까지 lock으로 보호하려면 `xa_load()` 전에 `xa_lock()`을 호출하고, 찾은 object의 reference count를 획득한 뒤 `xa_unlock()`을 호출할 수 있습니다. 그러면 object lookup과 refcount 증가 사이에 store가 배열에서 object를 제거하지 못합니다. RCU로 해제된 memory의 dereference를 피할 수도 있지만 이는 이 문서의 범위를 벗어납니다.

XArray는 배열을 수정하는 동안 interrupt나 softirq를 비활성화하지 않습니다. RCU lock이 충분한 보호를 제공하므로 interrupt 또는 softirq context에서 XArray를 읽어도 안전합니다.

예를 들어 process context에서 XArray에 entry를 저장하고 softirq context에서 지우려면 다음과 같이 구현할 수 있습니다.

void foo_init(struct foo *foo)
{
    xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
}

int foo_store(struct foo *foo, unsigned long index, void *entry)
{
    int err;

    xa_lock_bh(&foo->array);
    err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
    if (!err)
        foo->count++;
    xa_unlock_bh(&foo->array);
    return err;
}

/* foo_erase() is only called from softirq context */
void foo_erase(struct foo *foo, unsigned long index)
{
    xa_lock(&foo->array);
    __xa_erase(&foo->array, index);
    foo->count--;
    xa_unlock(&foo->array);
}

Interrupt 또는 softirq context에서 XArray를 수정한다면 `xa_init_flags()`에 `XA_FLAGS_LOCK_IRQ` 또는 `XA_FLAGS_LOCK_BH`를 전달하여 배열을 초기화해야 합니다.

위 예제는 배열과 연결된 통계를 보호하기 위해 store 쪽에서 `xa_lock`의 보호 범위를 확장하는 일반적인 pattern도 보여 줍니다.

XArray를 interrupt context와 공유할 수도 있습니다. Interrupt handler와 process context 양쪽에서 `xa_lock_irqsave()`를 사용하거나, process context에서 `xa_lock_irq()`를 사용하고 interrupt handler에서 `xa_lock()`을 사용합니다. 흔한 pattern에는 `xa_store_bh()`, `xa_store_irq()`, `xa_erase_bh()`, `xa_erase_irq()`, `xa_cmpxchg_bh()`, `xa_cmpxchg_irq()` 같은 helper가 제공됩니다.

Locking hierarchy에서 다른 mutex 위에 있는 lock 때문에 mutex로 XArray access를 보호해야 할 때도 있습니다. 그렇더라도 `xa_lock` 없이 `__xa_erase()` 같은 함수를 사용할 수 있는 것은 아닙니다. `xa_lock`은 lockdep validation에 쓰이며 앞으로 다른 목적으로도 사용될 예정입니다.

`__xa_set_mark()`와 `__xa_clear_mark()`는 entry를 lookup한 뒤 mark를 원자적으로 설정하거나 지울 때도 사용할 수 있습니다. 이 경우 advanced API를 사용하면 tree를 두 번 순회하지 않아도 되어 더 효율적일 수 있습니다.

고급 API

고급 API

고급 API는 사용하기 더 어렵고 보호 장치가 적은 대신 더 높은 유연성과 성능을 제공합니다. 고급 API는 locking을 대신 수행하지 않으므로 배열을 수정할 때 `xa_lock`을 사용해야 합니다. Read-only operation에는 `xa_lock` 또는 RCU lock 중 하나를 선택할 수 있습니다. 같은 배열에서 고급 operation과 일반 operation을 섞어 쓸 수 있으며 실제로 일반 API는 고급 API로 구현됩니다. 고급 API는 GPL-compatible license를 가진 module에만 제공됩니다.

고급 API는 `xa_state`를 중심으로 구성됩니다. 이는 `XA_STATE()` macro를 사용해 stack에 선언하는 opaque 자료 구조입니다. Macro는 XArray 순회를 시작할 준비가 된 `xa_state`를 초기화합니다. `xa_state`는 XArray 안의 위치를 유지하는 cursor로 사용되므로 매번 root부터 다시 시작하지 않고 여러 operation을 조합할 수 있습니다. 내용은 `rcu_read_lock()` 또는 `xas_lock()`으로 보호합니다. State와 tree를 보호하는 lock을 내려놓아야 한다면, 이후 호출이 보호되지 않은 state 부분에 의존하지 않도록 `xas_pause()`를 호출해야 합니다.

`xa_state`는 error 저장에도 사용됩니다. `xas_error()`로 error를 가져옵니다. 모든 operation은 진행 전에 `xa_state`의 error 상태를 검사하므로 호출마다 error를 확인할 필요 없이 여러 호출을 연속 수행한 뒤 편리한 지점에서 한 번 검사할 수 있습니다. 현재 XArray code가 직접 생성하는 error는 `ENOMEM`과 `EINVAL`뿐이지만, 사용자가 `xas_set_err()`를 호출하는 경우를 위해 임의의 error를 지원합니다.

`xa_state`가 `ENOMEM` error를 보유하고 있을 때 `xas_nomem()`을 호출하면 지정한 GFP flag로 memory를 더 할당하여 다음 시도를 위해 `xa_state`에 cache합니다. 의도한 흐름은 `xa_lock`을 잡고 operation을 시도한 뒤 lock을 내려놓는 것입니다. Lock을 잡은 채 memory 할당을 시도하면 실패하기 쉽지만, lock을 내려놓은 뒤 `xas_nomem()`은 더 적극적으로 할당할 수 있습니다. Memory error가 있었고 추가 memory를 할당하여 재시도할 가치가 있으면 `true`를 반환합니다. 이전에 할당한 memory가 사용되지 않았고 error가 없거나 `ENOMEM`이 아닌 error라면 그 memory를 해제합니다.

내부 entry

내부 entry

XArray는 자체 용도를 위해 일부 entry를 예약합니다. 일반 API에는 노출되지 않지만 고급 API를 사용하면 볼 수 있습니다. 보통은 이를 `xas_retry()`에 전달하고, 함수가 `true`를 반환하면 operation을 재시도하는 방식이 가장 좋습니다.

앞으로 다른 internal entry가 추가될 수 있습니다. 가능한 한 `xas_retry()`가 이를 처리할 것입니다.

추가 기능

추가 기능

`xas_create_range()`는 범위의 모든 entry를 저장하는 데 필요한 memory를 할당합니다. Memory를 할당할 수 없으면 `xa_state`에 `ENOMEM`을 설정합니다.

`xas_init_marks()`는 entry의 mark를 기본 상태로 reset합니다. 보통 모든 mark가 clear된 상태이지만 XArray에 `XA_FLAGS_TRACK_FREE`가 설정되어 있으면 mark 0은 set되고 나머지는 clear됩니다. `xas_store()`로 entry를 교체해도 mark가 reset되지 않으므로 필요하다면 명시적으로 reset해야 합니다.

`xas_load()`는 가능한 한 entry에 가까운 위치까지 `xa_state`를 순회합니다. 이미 해당 entry까지 순회했고 entry가 바뀌지 않았는지 확인해야 한다면 `xas_reload()`로 function call 하나를 줄일 수 있습니다.

XArray의 다른 index로 이동하려면 `xas_set()`을 호출합니다. 이 함수는 cursor를 tree root로 reset하며 보통 다음 operation이 원하는 위치까지 cursor를 순회하게 합니다. 다음 또는 이전 index로 이동하려면 `xas_next()` 또는 `xas_prev()`를 호출합니다. Index 설정 자체는 cursor를 순회하지 않아 lock이 필요 없지만 다음이나 이전 index로 이동할 때는 lock이 필요합니다.

`xas_find()`로 다음 present entry를 검색할 수 있습니다. 이는 `xa_find()`와 `xa_find_after()`의 역할을 모두 수행합니다. Cursor가 이미 entry까지 순회했다면 현재 참조하는 entry 다음의 entry를 찾고, 그렇지 않으면 `xa_state`의 index에 있는 entry를 반환합니다. `xas_find()` 대신 `xas_next_entry()`로 다음 present entry로 이동하면 inline code가 늘어나는 대신 대부분의 경우 function call 하나를 줄일 수 있습니다.

`xas_find_marked()`도 비슷합니다. `xa_state`가 아직 순회되지 않았고 해당 index의 entry에 mark가 있으면 그 entry를 반환합니다. 이미 순회했다면 현재 참조하는 entry 다음의 첫 marked entry를 반환합니다. `xas_next_marked()`는 `xas_next_entry()`에 대응합니다.

`xas_for_each()` 또는 `xas_for_each_marked()`로 XArray 범위를 순회할 때 일시적으로 순회를 멈춰야 할 수 있습니다. 이를 위해 `xas_pause()`를 사용합니다. 필요한 작업을 마치고 재개하면 `xa_state`는 마지막으로 처리한 entry 다음부터 계속할 수 있는 상태입니다. Interrupt를 비활성화한 채 순회한다면 `XA_CHECK_SCHED`개 entry마다 순회를 멈추고 interrupt를 다시 활성화하는 것이 좋습니다.

`xas_get_mark()`, `xas_set_mark()`, `xas_clear_mark()`는 `xa_state` cursor가 XArray의 적절한 위치로 이동해 있어야 합니다. 바로 전에 `xas_pause()` 또는 `xas_set()`을 호출했다면 아무 작업도 하지 않습니다.

`xas_set_update()`를 호출하면 XArray가 node를 갱신할 때마다 callback function을 호출하게 할 수 있습니다. Page cache workingset code는 이를 사용해 shadow entry만 포함한 node 목록을 유지합니다.

Multi-index entry

Multi-index entry

XArray는 여러 index를 묶어 한 index의 operation이 모든 index에 영향을 주게 할 수 있습니다. 어느 index에 저장해도 모든 index에서 가져오는 entry 값이 바뀌며, 어느 index에서 mark를 설정하거나 지워도 묶인 모든 index의 mark가 함께 바뀝니다. 현재 구현은 alignment가 맞는 power-of-two 범위만 묶을 수 있습니다. 예를 들어 64-127은 묶을 수 있지만 2-6은 묶을 수 없습니다. 이렇게 하면 상당한 memory를 절약할 수 있으며 512개 entry를 묶으면 4kB 넘게 줄일 수 있습니다.

`XA_STATE_ORDER()`를 사용하거나 `xas_set_order()` 뒤에 `xas_store()`를 호출하여 multi-index entry를 만듭니다. Multi-index `xa_state`로 `xas_load()`를 호출하면 tree의 올바른 위치까지 이동하지만 반환값은 의미가 없으며, 범위 안에 entry가 있어도 internal entry 또는 `NULL`일 수 있습니다. `xas_find_conflict()`는 범위 안의 첫 entry를 반환하고 entry가 없으면 `NULL`을 반환합니다. `xas_for_each_conflict()` iterator는 지정 범위와 겹치는 모든 entry를 순회합니다.

`xas_load()`가 multi-index entry를 만나도 `xa_state`의 `xa_index`는 바뀌지 않습니다. XArray를 순회하거나 `xas_find()`를 호출할 때 초기 index가 multi-index entry 중간에 있으면 그대로 유지됩니다. 이후 호출이나 순회에서는 index가 범위의 첫 index로 이동합니다. Entry가 차지하는 index 수와 관계없이 각 entry는 한 번만 반환됩니다.

Multi-index `xa_state`에 `xas_next()` 또는 `xas_prev()`를 사용하는 것은 지원되지 않습니다. Multi-index entry에 이 함수를 사용하면 sibling entry가 노출되므로 호출자가 건너뛰어야 합니다.

Multi-index entry의 어느 index에든 `NULL`을 저장하면 모든 index의 entry가 `NULL`이 되고 묶음이 해제됩니다. 더 작은 범위의 entry로 나누려면 `xa_lock` 없이 `xas_split_alloc()`을 호출한 뒤 lock을 잡고 `xas_split()`을 호출하거나, `xa_lock`을 잡은 채 `xas_try_split()`을 호출합니다. 원문의 비교 대상인 `xas_split_alloc()+xas_split()`과 `xas_try_alloc()` 가운데 전자는 원래 order에서 새 order로 한 번에 균일하게 분할하고, `xas_try_split()`은 지정 index를 포함한 entry를 반복적으로 비균일 분할합니다. `XA_CHUNK_SHIFT`가 6일 때 order-9 entry는 2^(9-6)=8 slot을 차지하므로 전자는 xa_node 8개가 필요합니다. `xas_try_split()`은 order-9 entry를 order-8 두 개로 나눈 다음 지정 index에 따라 그중 하나를 order-7 두 개로 나누는 과정을 order-0까지 반복합니다. Order-6 entry 분할에 새 xa_node가 필요하면 가능한 경우 하나를 할당하므로, 결과적으로 xa_node 8개 대신 1개만 필요합니다.

함수와 구조체

함수와 구조체

XArray API와 구현의 kernel-doc reference는 다음 source에 있습니다.

.. kernel-doc:: include/linux/xarray.h

.. kernel-doc:: lib/xarray.c