Atomic bit operation

개요

일반적인 bitmap_{}() 함수는 atomic하지 않다. 반면 bitmap 안의 단일 bit를 대상으로 하는 일부 함수는 다른 CPU와 경쟁해도 갱신이 분리되지 않도록 atomic operation을 제공한다.

여기서 atomic은 단순히 compiler가 한 명령으로 만든다는 뜻이 아니다. 같은 memory location을 갱신하는 CPU 사이에서 read-modify-write가 하나의 분리 불가능한 동작으로 관측되어야 한다는 뜻이다.

API

단일 bit API는 값을 읽기만 하는 non-RMW operation, bit를 읽고 수정하는 RMW operation, ordering을 보강하는 barrier로 나뉜다.

Non-RMW operation

test_bit()

test_bit()는 대상 bit를 읽지만 그 값을 변경하지 않는다. 따라서 read-modify-write가 아니며, 그 자체만으로 다른 memory access의 순서를 강제하지 않는다.

반환값이 없는 RMW atomic operation

{set,clear,change}_bit()
clear_bit_unlock()

set_bit(), clear_bit(), change_bit()는 각각 bit를 1로 설정하고, 0으로 지우고, 현재 값을 반전한다. clear_bit_unlock()은 bit를 지우는 동작에 RELEASE ordering을 결합한 unlock 전용 operation이다.

원래 값을 반환하는 RMW atomic operation

test_and_{set,clear,change}_bit()
test_and_set_bit_lock()

test_and_* 함수는 bit를 변경하면서 변경 전 값을 반환한다. 호출자는 반환값으로 자신이 처음 상태를 바꾼 CPU인지 판단할 수 있다. test_and_set_bit_lock()은 lock 획득에 맞춘 ACQUIRE operation이다.

Barrier

smp_mb__before_atomic()
smp_mb__after_atomic()

__ 접두사가 붙는 non-atomic variant

모든 RMW atomic bit operation에는 이름 앞에 __가 붙는 non-atomic variant가 있다. 예를 들어 set_bit()에 대응하는 __set_bit()가 있다. 이 함수들은 caller가 이미 lock이나 CPU-local 조건으로 동시 접근을 막았을 때만 사용해야 한다.

동작 의미

__clear_bit_unlock()에는 atomic_set()과 같은 종류의 문제가 있다. 다른 CPU의 atomic RMW와 경쟁할 때 단순 store가 RMW의 atomicity를 깨뜨려서는 안 된다. 그래서 generic implementation은 atomic한 clear_bit_unlock()으로 연결된다. 자세한 배경은 atomic_t.txt가 설명한다.

test_and_{}_bit() 계열의 반환값은 operation이 끝난 뒤의 값이 아니라 변경하기 전 bit 값이다. 예를 들어 test_and_set_bit()가 0을 반환했다면 이 호출이 0에서 1로 바꾼 호출이다.

Memory ordering

atomic_t와 같은 기본 규칙을 적용한다. 여기서 unordered는 대상 bit 자체의 atomicity가 없다는 뜻이 아니라, 다른 memory location에 대한 load/store 순서를 추가로 보장하지 않는다는 뜻이다.

예외가 세 가지 있다. 성공한 test_and_set_bit_lock()과 test_bit_acquire()는 ACQUIRE semantics를 가지며, clear_bit_unlock()은 RELEASE semantics를 가진다.

architecture는 보통 atomic operation을 구현하는 공통 하드웨어 수단을 사용하므로 atomic_t와 같은 smp_mb__before_atomic(), smp_mb__after_atomic() barrier를 사용한다.

Lock bit에서 ACQUIRE와 RELEASE가 필요한 이유

/* CPU 0: lock을 얻은 뒤 protected data를 읽는다. */
while (test_and_set_bit_lock(LOCKED, &state))
        cpu_relax();
value = READ_ONCE(shared_data);

/* CPU 1: data 갱신을 먼저 공개하고 lock bit를 지운다. */
WRITE_ONCE(shared_data, new_value);
clear_bit_unlock(LOCKED, &state);

CPU 1의 RELEASE는 shared_data store가 lock 해제 뒤로 밀리지 않게 한다. CPU 0의 ACQUIRE는 lock 획득 뒤의 shared_data load가 lock 획득 앞으로 당겨지지 않게 한다. 이 쌍으로 임계 구역 안의 값이 다음 lock 소유자에게 전달된다.