atomic_t, atomic64_t, atomic_long_t

Atomic type의 범위

atomic_t, atomic64_t, atomic_long_t는 여러 CPU가 같은 memory location에 read-modify-write를 수행할 때 architecture가 제공하는 atomic operation을 공통 API로 노출한다.

API 분류

아래 목록에서는 간결하게 쓰기 위해 atomic64_와 atomic_long_ 접두사를 생략한다. 실제 API에는 자료형에 맞는 접두사가 붙는다.

Non-RMW operation

atomic_read(), atomic_set()
atomic_read_acquire(), atomic_set_release()

값을 읽거나 쓰기만 한다. read-modify-write가 아니며 보통 READ_ONCE(), WRITE_ONCE(), acquire load, release store로 구현된다.

산술 RMW operation

atomic_{add,sub,inc,dec}()
atomic_{add,sub,inc,dec}_return{,_relaxed,_acquire,_release}()
atomic_fetch_{add,sub,inc,dec}{,_relaxed,_acquire,_release}()

return 계열은 연산 뒤의 수정된 값을 반환하고, fetch 계열은 연산 전의 값을 반환한다. add, sub, inc, dec는 역연산이 가능하므로 두 형태를 모두 제공한다.

Bitwise RMW operation

atomic_{and,or,xor,andnot}()
atomic_fetch_{and,or,xor,andnot}{,_relaxed,_acquire,_release}()

bitwise operation은 수정된 값에서 원래 값을 역산할 수 없으므로 modified value를 돌려주는 *_return 계열은 제공하지 않는다. 원래 값이 필요하면 atomic_fetch_*를 사용한다.

Swap과 compare-and-swap

atomic_xchg{,_relaxed,_acquire,_release}()
atomic_cmpxchg{,_relaxed,_acquire,_release}()
atomic_try_cmpxchg{,_relaxed,_acquire,_release}()

Reference count 성격의 operation

atomic_add_unless(), atomic_inc_not_zero()
atomic_sub_and_test(), atomic_dec_and_test()

그 밖의 조건부 operation과 barrier

atomic_inc_and_test(), atomic_add_negative()
atomic_dec_unless_positive(), atomic_inc_unless_negative()

smp_mb__before_atomic()
smp_mb__after_atomic()

Signed type과 overflow

atomic_t, atomic_long_t, atomic64_t의 내부 값은 각각 int, long, s64다. 역사적인 이유로 signed type을 사용하지만, 커널은 -fno-strict-overflow를 사용하며 이는 -fwrapv를 포함한다.

따라서 signed overflow는 2의 보수 wraparound로 정의된다. unsigned 전용 atomic API를 별도로 둘 필요가 없고, 필요한 경우 cast해도 C의 undefined behavior가 되지 않는다.

GCC 8 이전 UBSAN에는 signed type에서 잘못된 undefined-behavior warning을 만들던 문제가 있었다. 현재 규칙은 C/C++ _Atomic의 동작과 P1236R1 같은 정리 방향에도 부합한다.

Non-RMW operation의 의미

Non-RMW operation은 일반적으로 regular load와 store다. atomic_read(), atomic_set(), atomic_read_acquire(), atomic_set_release()는 각각 READ_ONCE(), WRITE_ONCE(), smp_load_acquire(), smp_store_release()로 구현되는 것이 정석이다.

atomic_t를 사용하면서 non-RMW API만 호출한다면 atomic_t가 필요하지 않다. 그 경우에는 READ_ONCE()/WRITE_ONCE()와 필요한 ordering을 명시하는 편이 자료구조의 실제 동시성 규칙을 더 정확히 드러낸다.

atomic_set()이 RMW atomicity를 깨뜨리면 안 되는 이유

atomic_set()은 단순 store처럼 보이지만 같은 객체에 대한 atomic RMW와 경쟁할 수 있다. 이때 RMW가 중간 상태를 만들어 내도록 구현해서는 안 된다.

C Atomic-RMW-ops-are-atomic-WRT-atomic_set

{
        atomic_t v = ATOMIC_INIT(1);
}

P0(atomic_t *v)
{
        (void)atomic_add_unless(v, 1, 0);
}

P1(atomic_t *v)
{
        atomic_set(v, 0);
}

exists (v=2)

CPU 1의 atomic_set(v, 0)이 먼저 끝나면 CPU 0의 atomic_add_unless()는 조건이 맞지 않아 아무 일도 하지 않는다. atomic_add_unless()가 먼저 끝나면 CPU 1의 store가 그 결과를 0으로 덮는다. 어느 순서에서도 최종값 2는 나올 수 없다.

일반적인 architecture에서는 경쟁하는 regular store가 LL/SC reservation을 무효화하거나 CMPXCHG를 실패시키므로 이 조건을 만족한다.

문제는 atomic RMW를 lock으로 흉내 내는 구현이다. RMW가 lock 안에서 1을 읽은 뒤, 다른 CPU의 atomic_set()이 0을 쓰고, 첫 CPU가 오래된 값 1에 1을 더해 2를 쓰면 금지된 결과가 생긴다. 이런 구현에서는 atomic_set()도 atomic_xchg()로 구현해 같은 직렬화 규칙에 참여시켜야 한다.

RMW operation의 반환 형태

이 operation들은 모두 SMP atomic이다. 하나의 atomic variable에 대한 operation에는 전체 순서를 세울 수 있고, 중간 상태가 사라지거나 다른 CPU에 노출되지 않는다.

Memory ordering 기본 규칙

성공한 operation에 _relaxed가 붙으면 다른 memory location에 대해 unordered다. _acquire는 RMW의 read 부분을 ACQUIRE로 만들고, _release는 write 부분을 RELEASE로 만든다. conditional operation은 실패하면 여전히 unordered다.

unordered라도 address dependency를 없애지는 않는다. fully ordered primitive는 앞의 모든 access와 뒤의 모든 access 사이에 순서를 세우므로, 개념상 operation 앞뒤에 smp_mb()가 하나씩 있는 것과 같다.

smp_mb__before_atomic()과 smp_mb__after_atomic()

두 helper barrier는 RMW atomic operation에만 적용한다. operation이 원래 제공하는 ordering을 더 강하게 만들 때 사용한다.

smp_mb__before_atomic()은 그보다 앞선 모든 access를 RMW 자체와 그 뒤의 access보다 먼저 오게 한다. smp_mb__after_atomic()은 뒤의 모든 access를 RMW 자체와 그 앞의 access보다 나중에 오게 한다.

다만 barrier와 RMW 사이에 다른 access를 끼워 넣으면 그 access까지 기대한 방식으로 정렬되지 않는다. 가능한 한 barrier를 대상 atomic operation 바로 옆에 둬야 한다.

architecture마다 SMP atomic instruction이 암묵적으로 제공하는 ordering이 다르기 때문에 helper가 필요하다. TSO architecture의 fully ordered atomic에서는 helper가 no-op일 수 있다. fully ordered atomic RMW는 compiler barrier도 포함해야 한다.

atomic_fetch_add();

/* ordering 관점에서 다음과 동등하다. */
smp_mb__before_atomic();
atomic_fetch_add_relaxed();
smp_mb__after_atomic();

동등한 의미라도 architecture는 atomic_fetch_add()를 더 효율적으로 구현할 수 있으므로, 불필요하게 세 operation으로 풀어 쓰지 않는다.

Helper barrier는 단순 ACQUIRE·RELEASE보다 강하다

smp_mb__before_atomic(); atomic_dec(&X);는 흔히 RELEASE 모양으로 쓰이지만 RELEASE보다 강하다. 앞선 instruction을 atomic_dec()의 read와 write 양쪽, 그리고 뒤따르는 모든 instruction보다 앞에 둔다.

atomic_inc(&X); smp_mb__after_atomic();도 ACQUIRE보다 강하다. ACQUIRE는 RMW의 read 부분 뒤에 오는 access만 제한하지만, after helper는 RMW의 write 부분과 뒤의 access 사이에도 순서를 세운다.

P0(int *x, atomic_t *y)
{
        r0 = READ_ONCE(*x);
        smp_rmb();
        r1 = atomic_read(y);
}

P1(int *x, atomic_t *y)
{
        atomic_inc(y);
        smp_mb__after_atomic();
        WRITE_ONCE(*x, 1);
}

exists (0:r0=1 /\ 0:r1=0)

위 결과는 허용되지 않아야 한다. 가상의 atomic_inc_acquire()는 RMW write와 뒤의 WRITE_ONCE(*x, 1) 사이를 정렬하지 않으므로 같은 결과를 허용할 수 있다. 이것이 after helper를 단순 ACQUIRE로 치환할 수 없는 이유다.

CMPXCHG와 TRY_CMPXCHG

int atomic_cmpxchg(atomic_t *ptr, int old, int new);
bool atomic_try_cmpxchg(atomic_t *ptr, int *oldp, int new);

두 함수의 기능은 같다. cmpxchg는 실제로 관측한 old value를 반환한다. try_cmpxchg는 성공 여부를 bool로 반환하고, 실패하면 *oldp를 실제 관측값으로 갱신한다.

old = atomic_read(&v);
do {
        new = func(old);
} while (!atomic_try_cmpxchg(&v, &old, new));

실패할 때 old가 자동으로 최신 관측값으로 바뀌므로 별도의 tmp와 비교, 대입이 필요 없다. 특히 x86에서는 try_cmpxchg 형태가 hardware instruction의 operand와 더 잘 맞아 더 작은 코드를 만들 수 있다.

Forward progress

산술·bitwise operation과 xchg 같은 unconditional atomic operation에는 일반적으로 강한 forward progress가 기대된다. 커널의 상당한 코드는 conditional atomic operation에도 일정 수준의 progress를 요구한다.

특히 단순한 cmpxchg loop들이 서로를 영원히 굶기지 않아야 한다. 하지만 LL/SC architecture에서 이 보장은 자동으로 따라오지 않는다. architecture가 경쟁하는 LL/SC section 자체의 progress를 보장하더라도, C loop 전체를 포함하는 cmpxchg 구현까지 같은 보장이 확장되지는 않는다.

failed compare 뒤의 forward branch만으로도 LL/SC reservation이 실패하는 architecture가 있고, compiler가 loop body에 만든 instruction은 reservation 유지 가능성을 더 낮춘다. 그 결과 v가 들어 있는 cache line이 local CPU에 머물고 loop가 진전된다는 보장이 사라진다.

native CAS architecture도 primitive의 forward progress를 보장하지 못할 수 있으며 Sparc64가 그 예다.

영향을 받는 구현은 CAS 실패 뒤 exponential backoff를 넣어 progress 가능성을 높이는 것이 강하게 권장된다. architecture maintainer는 generic atomic fallback, refcount_t와 locking primitive도 함께 점검해야 한다.