Atomic Operation

Atomic Operation

  • Atomic Operation은 아키텍처마다 처리하는 명령과 방법이 조금씩 다르므로 정확한 처리 방법은 해당 아키텍처 소스를 참고하길 바라며, 이 글에서는 32비트 ARM을 우선하여 설명한다.
  • 시스템 메모리에 있는 공유 변수를 증/감시키기 위해서는 보통 한 개의 명령으로 처리되지 않고 load from memory -> increment/decrement -> store to memory 과정과 같이 여러 개의 명령이 순차적으로 수행되어야 하는데 이를 보장하는 방법을 Atomic Operation이라고 하며 시스템에서 사용할 수 있는 가장 작은 단위의 동기화 기법이기도 하다. critical section을 보호하는 각종 lock을 사용하지 않고 atomic operation을 사용하는 이유는 dead-lock 등이 없고 동기화 기법 중 가장 빠른 성능을 가지고 있다. (참고 데이터베이스의 트랜잭션과 유사)
  • 처리하는 방법이 UP 시스템과 SMP 시스템에서의 구현 방법이 다른데 ARM에서는 ARMv5(UP only)까지와 ARMv6(UP/SMP) 부터의 구현 로직을 각각 나누어 제공한다.
  • ARMv5(UP only) 까지의 아키텍처에서 Atomic operation 구현은 해당 atomic operation 수행 중 태스크의 문맥교환이 일어나거나(태스크가 preemption) 인터럽트 루틴에서 해당 메모리에 대해 동시 처리되지 않도록 아예 인터럽트를 막아서 해결한다. UP에서는 인터럽트만 막아도 태스크의 문맥교환이 일어나지 않으므로  인터럽트를 enable하기 전까지 atomic opeation을 보장하게 된다.
  • ARMv6 부터 사용되는 구현 로직은 UP이외에도 SMP 시스템까지 동시에 처리 될 수 있도록 load-link/store-conditional 이라는 새로운 테크닉을 사용하였다.  CPU에서 atomic operation을 수행하는 도중 인터럽트 또는 preemption 되는 것을 막지 않는다. 또한 다른 여러 CPU에서 atomic operation이 동시에 수행되는 것을 막지도 않는다. 다만 이렇게 수행하는 atomic opeation에서 사용하는 공유 메모리의 접근이 서로 중복되는 경우가 발생하면 해당 atomic operation을 취소하고 중복이 발생되지 않을 때 까지 retry하는 기법으로 atomic operation이 한 번에 하나만 수행되는 것을 보장한다. 이렇게 해당 공유 메모리의 접근이 중복되는 것을 알아채는 것은 하드웨어의 도움을 받아 처리하게 되는데 ARM에서는 ldrex와 strex 명령의 쌍으로 처리할 수 있다.

아키텍처 별 헤더

Atomic operation은 기본 구현 헤더 이외에도 아키텍처에 따라 전용 구현이 준비되어 있을 수도 있다.
  • include/asm-generic/atomic.h
    •  플랫폼 독립적인 코드로 구성되어 아키텍처별로 포팅을 도와주기 위한 코드
    • atomic.h는 커널 2.6.31에서 추가되었다.
    • 참고: asm-generic headers, v4 | LWN.net
  • arch/arm/include/asm/atomic.h
    •  ARM 아키텍처 전용 코드로 구성
    •  ARM 아키텍처의 경우 asm-generic 보다 이의 사용을 우선한다.

기본 Atomic operation 명령

#define atomic_xchg(v, new)      (xchg(&((v)->counter), new))
#define atomic_inc(v)            atomic_add(1, v)
#define atomic_dec(v)            atomic_sub(1, v)
#define atomic_inc_and_test(v)   (atomic_add_return(1, v) == 0)
#define atomic_dec_and_test(v)   (atomic_sub_return(1, v) == 0)
#define atomic_inc_return(v)     (atomic_add_return(1, v))
#define atomic_dec_return(v)     (atomic_sub_return(1, v))
#define atomic_add_negative(i,v) (atomic_add_return(i, v) < 0)

SW atomic operation vs HW atomic operation 지원 

1) S/W 접근 방법 (ARMv5 까지 사용)

  • 인터럽트를 막음으로 atomic operation을 수행 중 다른 태스크가 preemption 되지 않게 한다.
  • ARMv5까지는 UP(Uni Processor) 시스템이므로 현재 CPU의 인터럽트만 막아도 atomic operation이 성립한다.
  • 참고로 SDRMA에 존재하는 한 변수를 증감하려 할 때 cpu clock은 캐시 상태(hit/miss)에 따라 수 cycle ~ 수십 cycle이 소요된다.
  • 매크로로 만들어진 아래 함수를 설명하면…
    • 현재 CPU의 인터럽트 상태를 보관 하고 disable하여 인터럽트 호출을 막는다.
    • atomic operation에 필요한 add/sub 또는 xchg 연산등을 수행한다.
    • 다시 인터럽트 상태를 원래대로 돌려놓는다.
static inline void atomic_add(int i, atomic_t *v)
{
        unsigned long flags;                
        raw_local_irq_save(flags);
        v->counter += i;
        raw_local_irq_restore(flags);
}

2) H/W 접근 방법 (ARMv6 부터 사용)

  • ldrex/strex 사용: UP에서의 멀티스레드에서의 preemption 이외에도 SMP 시스템에서는 메모리 access가 여러 개의 CPU에서 동시 처리될 수 있기 때문에 데이터에 대해 Atomic operation(load – operation – store, 읽고 연산하고 기록) 수행 시 다른 CPU가 끼어들면 실패를 감지할 수 있어야 한다. 따라서 ARM 아키텍처에서는 이를 위해 ldr과 str 대신 별도로 ldrex와 strex 명령을 사용하여 처리하게 하였다.
  • pld(pldw) 사용:
    • ldrex와 strex 사이에 처리되어야 하는 메모리가 캐시 미스되어 ldrex 부터 strex 까지의 처리에 CPU clock의 지연을 일으키므로 이를 막기 위해 사용하려는 메모리를 ldrex로 로드하기 전에 미리 캐시에 사전 로드하는 방법을 사용하기 위해 ARM 아키텍처 전용 명령인 pld(pldw) 명령을 사용하여 지정된 메모리의 데이터가 캐시에 없는 경우 이를 캐시에 미리로드(linefill)하라고 지시한다.
    • 처음 사용 시 critical section을 최소화 시키는 것과 유사한 효과를 보이므로 strex에서 실패할 확률을 줄여준다.
  • Out of order execution 및 Out of order access memory 기능을 가지고 있는 ARM 아키텍처를 위해 atomic_xxx_return() 및 atomic_cmpxchg_relaxed() 명령의 경우 smp_mb() 베리어를 추가 사용한다.
  • “Qo” memory constraints
static inline void atomic_add(int i, atomic_t *v)
{
        unsigned long tmp;
        int result;
        prefetchw(&v->counter);
        __asm__ __volatile__("@ atomic_add \n"
"1:     ldrex   %0, [%3]\n"
"       add     %0, %0, %4\n"
"       strex   %1, %0, [%3]\n"
"       teq     %1, #0\n"
"       bne     1b"
        : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)
        : "r" (&v->counter), "Ir" (i)
        : "cc");
}

atomic_inc() 

atomic_inc_return(), atomic_sub() 및 atomic_sub_return() 역시 같은 매크로로 만들어진다.
arch/arm/include/asm/atomic.h
#define atomic_inc(v)          atomic_add(1, v)
#define atomic_dec(v)          atomic_sub(1, v)
ARMv6 아키텍처 이상인 atomic_add()가 선언되어 있는 곳은 다음과 같다.
  • add가 있는 ATOMIC_OPS() 매크로는 각각 ATOMIC_OP()와 ATOMIC_OP_RETURN() 매크로를 호출한다.
  • 이를 통해 만들어지는 함수는 atomic_add(), atomic_add_return()을 만들어낸다.

arch/arm/include/asm/atomic.h

/*
 * ARMv6 UP and SMP safe atomic ops.  We use load exclusive and
 * store exclusive to ensure that these are atomic.  We may loop
 * to ensure that the update happens.
 */

#define ATOMIC_OP(op, c_op, asm_op)                                     \
static inline void atomic_##op(int i, atomic_t *v)                      \
{                                                                       \
        unsigned long tmp;                                              \
        int result;                                                     \
                                                                        \
        prefetchw(&v->counter);                                         \
        __asm__ __volatile__("@ atomic_" #op "\n"                       \
"1:     ldrex   %0, [%3]\n"                                             \
"       " #asm_op "     %0, %0, %4\n"                                   \
"       strex   %1, %0, [%3]\n"                                         \
"       teq     %1, #0\n"                                               \
"       bne     1b"                                                     \
        : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)               \
        : "r" (&v->counter), "Ir" (i)                                   \
        : "cc");                                                        \
} 

#define ATOMIC_OP_RETURN(op, c_op, asm_op)                              \
static inline int atomic_##op##_return(int i, atomic_t *v)              \
{                                                                       \
        unsigned long tmp;                                              \
        int result;                                                     \
                                                                        \
        smp_mb();                                                       \
        prefetchw(&v->counter);                                         \
                                                                        \
        __asm__ __volatile__("@ atomic_" #op "_return\n"                \
"1:     ldrex   %0, [%3]\n"                                             \
"       " #asm_op "     %0, %0, %4\n"                                   \
"       strex   %1, %0, [%3]\n"                                         \
"       teq     %1, #0\n"                                               \
"       bne     1b"                                                     \
        : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)               \
        : "r" (&v->counter), "Ir" (i)                                   \
        : "cc");                                                        \
                                                                        \
        smp_mb();                                                       \
                                                                        \
        return result;                                                  \
}

atomic_xchg()

arch/arm/include/asm/atomic.h
#define atomic_xchg(v, new) (xchg(&((v)->counter), new))

arch/arm/include/asm/cmpxchg.h

#define xchg(ptr,x) \
    ((__typeof__(*(ptr)))__xchg((unsigned long)(x),(ptr),sizeof(*(ptr))))
__xchg() 함수의 소스는 __LINUX_ARM_ARCH >= 6인 경우만으로 한정한다. (길이 문제로)
arch/arm/include/asm/cmpxchg.h
static inline unsigned long __xchg(unsigned long x, volatile void *ptr, int size)
{
    extern void __bad_xchg(volatile void *, int);
    unsigned long ret;
#ifdef swp_is_buggy
    unsigned long flags;
#endif
    unsigned int tmp;

    smp_mb();
    prefetchw((const void *)ptr);

    switch (size) {
    case 1:
        asm volatile("@ __xchg1\n"
        "1: ldrexb  %0, [%3]\n"
        "   strexb  %1, %2, [%3]\n"
        "   teq %1, #0\n"
        "   bne 1b"
            : "=&r" (ret), "=&r" (tmp)
            : "r" (x), "r" (ptr)
            : "memory", "cc");
        break;
    case 4:
        asm volatile("@ __xchg4\n"
        "1: ldrex   %0, [%3]\n"
        "   strex   %1, %2, [%3]\n"
        "   teq %1, #0\n"
        "   bne 1b"
            : "=&r" (ret), "=&r" (tmp)
            : "r" (x), "r" (ptr)
            : "memory", "cc");
        break;
    default:
        __bad_xchg(ptr, size), ret = 0;
        break;
    }
    smp_mb();

    return ret;
}

 void __bad_xchg(volatile void *ptr, int size)
{
        pr_err("xchg: bad data size: pc 0x%p, ptr 0x%p, size %d\n",
               __builtin_return_address(0), ptr, size);
        BUG();
}

atomic_read() & atomic_set()

/*
 * On ARM, ordinary assignment (str instruction) doesn't clear the local
 * strex/ldrex monitor on some implementations. The reason we can use it for
 * atomic_set() is the clrex or dummy strex done on every exception return.
 */
#define atomic_read(v)  ACCESS_ONCE((v)->counter)
#define atomic_set(v,i) (((v)->counter) = (i))

 

atomic_cmpxchg()

mutex(optimistic spin lock), futex, qrwlock 등에서 사용하는 함수이다.

아래 소스도 ARMv6 이상 SMP 시스템용 코드이다.

  • 주요 어셈블리 코드는 다음과 같다.
    • ldrex   oldval <- [&ptr->counter]
    • mov     res, #0
    • teq     oldval, old
    • strexeq res, new, [&ptr->counter]
  • ptr->counter 값이 old와 같은 경우에만 new 값을 기록한다.
  • smp_mb()
    • 동기화를 위해 결과 값이 store buffer를 통해 메모리에 기록되는데 완전히 기록이 완료될 때까지 기다리고 oldval 값을 리턴한다.

arch/arm/include/asm/atomic.h

static inline int atomic_cmpxchg(atomic_t *ptr, int old, int new)
{
        int oldval;
        unsigned long res;

        smp_mb();
        prefetchw(&ptr->counter);

        do {
                __asm__ __volatile__("@ atomic_cmpxchg\n"
                "ldrex  %1, [%3]\n"
                "mov    %0, #0\n"
                "teq    %1, %4\n"
                "strexeq %0, %5, [%3]\n"
                    : "=&r" (res), "=&r" (oldval), "+Qo" (ptr->counter)
                    : "r" (&ptr->counter), "Ir" (old), "r" (new)
                    : "cc");
        } while (res);

        smp_mb();

        return oldval;
}

 

atomic 구조체 타입

 

atomic_t

include/linux/types.h

typedef struct {
        int counter;
} atomic_t;
  • 32bit counter 변수 하나로만 구성되어 있다.

 

atomic64_t

include/linux/types.h

#ifdef CONFIG_64BIT
typedef struct {
        long counter;
} atomic64_t;
#endif
  • 64bit counter 변수 하나로만 구성되어 있다.

 

기타 매크로 및 함수

atomic LPAE 및 64비트 세트 명령은 제외하였다.
  • atomic_cmpxchg()
  • atomic_inc_and_test()
  • atomic_dec_and_test()
  • atomic_sub_and_test()
  • atomic_add_negative()
  • atomic_add_unless()
  • atomic_inc_not_zero()
  • atomic_inc_not_zero_hint()
  • atomic_inc_unless_negative()
  • atomic_dec_unless_positive()
  • atomic_dec_if_positive()
  • atomic_or()

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.