might_sleep()

기능

  • CONFIG_PREEMPT_VOLUNTARY 옵션이 동작할 때에만 동작하는 Preemption 포인트
  • 현재 태스크보다 더 높은 우선 순위의 태스크를 빨리 처리할 수 있도록 중간에 리스케쥴링을 허용한다.
  • 리스케쥴링하는 경우 현재 태스크가 preemption되며 이 때 sleep이 일어나게 된다.
  • Preemption Points
    • 리눅스커널은 이렇게 preemption 포인트를 커널의 여러 곳에 뿌려(?) 놓았다.
    • preemption 포인트의 도움을 받아 급한 태스크의 가동에 필요한 latency가 100us 이내로 줄어드는 성과가 있었다.
    • preemption 포인트는 보통 1ms(100us) 이상 소요되는 루틴에는 보통 추가하여 놓는다.

소스 분석

might_sleep()

might_sleep

아래 소스에서 CONFIG_DEBUG_ATOMIC_SLEEP 옵션이 있는 경우에만 디버그를 위해 __might_sleep()루틴을 호출한다.

#ifdef CONFIG_DEBUG_ATOMIC_SLEEP
/**
* might_sleep - annotation for functions that can sleep
*
* this macro will print a stack trace if it is executed in an atomic
* context (spinlock, irq-handler, ...).
*
* This is a useful debugging help to be able to catch problems early and not
* be bitten later when the calling function happens to sleep when it is not
* supposed to.
*/
# define might_sleep() \
        do { __might_sleep(__FILE__, __LINE__, 0); might_resched(); } while (0)
#else
# define might_sleep() do { might_resched(); } while (0)
#endif

might_resched()는 CONFIG_PREEMPT_VOLUNTARY 옵션이 있는 경우에만 _cond_resched()루틴을 호출하고 없는 경우 아무것도 하지 않는다.

include/linux/kernel.h

#ifdef CONFIG_PREEMPT_VOLUNTARY
# define might_resched() _cond_resched()
#else
# define might_resched() do { } while (0)
#endif
_cond_resched() 함수에서는 preemption이 필요한 상황인 경우 preemption 되며 sleep 한다.
  • should_resched()함수는 preemption 가능한 상태(preempt count가 0)이면서 현재 태스크보다 더 높은 우선 순위를 갖은 태스크가 있는 경우에 true
  • preempt_schedule_commoon() 함수는 태스크의 스케쥴링을 다시 한다.

include/linux/kernel.h

int __sched _cond_resched(void)
{
        if (should_resched()) {
                preempt_schedule_common();
                return 1;
        }
        return 0;
}

should_resched()

should_resched 함수는 리스케쥴이 필요한 상황에서 true로 리턴한다.
  • preemption이 enable(preempt_count()가 0) 이면서
  • 리스케쥴 요청이 있는 경우(tif_need_resched()가 true)

include/asm-generic/preempt.h

/*
 * Returns true when we need to resched and can (barring IRQ state).
 */
static __always_inline bool should_resched(void)
{
        return unlikely(!preempt_count() && tif_need_resched());
}
preempt_count()는 현재 스레드 정보(thread_info 구조체)에서 preempt_count를 리턴.
  • preempt_count 값은 preempt_enable() 호출 시 감소되며 preempt_disable() 호출 시 증가된다.
  • preempt_count 값이 0인 경우 preemption이 가능한 상태가 된다.

include/asm-generic/preempt.h

static __always_inline int preempt_count(void)
{
        return current_thread_info()->preempt_count;
}
tif_need_resched() 매크로는 -> test_thread_flag() 매크로를 호출하고 -> 다시 test_ti_thread_flag() 함수를 호출한다.
  • test_bit() 함수는 비트 operation에 사용되는 함수로 해당 비트가 설정되어 있는지를 체크하여 리턴한다.
  • 스레드 플래그
    • 여러 개의 많은 비트로 구성되어 있는데 그 중 TIF_NEED_RESCHED 비트는 리스케쥴이 필요한 경우 세트된다.

include/linux/thread_info.h

static inline int test_ti_thread_flag(struct thread_info *ti, int flag)
{
        return test_bit(flag, (unsigned long *)&ti->flags);
}

#define test_thread_flag(flag) \
        test_ti_thread_flag(current_thread_info(), flag)

#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)

preempt_schedule_common()

preempt_schedule_common() 함수는 실제 리스케쥴을 수행하는 함수이므로 preemption되는 경우 sleep이 일어나는 장소다.
이 함수는 리눅스 커널의 scheduler에 해당하는 주요 함수이므로 scheduler 부분을 분석해야 하므로 이 파트에서는 자세한 분석은 생략한다.
kernel/sched/core.c
static void __sched notrace preempt_schedule_common(void)
{
        do {
                __preempt_count_add(PREEMPT_ACTIVE);
                __schedule();
                __preempt_count_sub(PREEMPT_ACTIVE);

                /*
                 * Check again in case we missed a preemption opportunity
                 * between schedule and now.
                 */
                barrier();
        } while (need_resched());
}

참고

likely() & unlikely()

커널에서 사용되는 매크로로 다음과 같다.

include/linux/compiler.h

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)
  • likely()는 true가 될 확률이 높은 조건문에서 사용하여 성능을 높이고자 사용한다.
  • unlikely()는 false가 될 확률이 높은 조건문에서 사용하여 성능을 높이고자 사용한다.

__builtin_expect()

Built-in Function: long __builtin_expect (long exp, long c)
  • gcc 내장 함수로서 컴파일러에게 branch prediction 정보를 주고자하는 함수이다.
  • 자주 사용되지 않는 문장을 함수의 뒷 부분에 배치하여 메모리 캐시나 brach prediction cache에 영향을 주어 성능을 최적화 시키려할 때 사용한다.
  • likely/unlikely와 다르게 userspace에서도 사용할 수 있다.

디버그 추적용

디버그 추적 옵션이 동작하는 경우 사용되는 likely() 및 unlikely() 매크로의 소스는 다음과 같다.

include/linux/compiler.h

#if defined(CONFIG_TRACE_BRANCH_PROFILING) \
    && !defined(DISABLE_BRANCH_PROFILING) && !defined(__CHECKER__)
void ftrace_likely_update(struct ftrace_branch_data *f, int val, int expect);

#define likely_notrace(x)       __builtin_expect(!!(x), 1)
#define unlikely_notrace(x)     __builtin_expect(!!(x), 0)

#define __branch_check__(x, expect) ({                                  \
                        int ______r;                                    \
                        static struct ftrace_branch_data                \
                                __attribute__((__aligned__(4)))         \
                                __attribute__((section("_ftrace_annotated_branch"))) \
                                ______f = {                             \
                                .func = __func__,                       \
                                .file = __FILE__,                       \
                                .line = __LINE__,                       \
                        };                                              \
                        ______r = likely_notrace(x);                    \
                        ftrace_likely_update(&______f, ______r, expect); \
                        ______r;                                        \
                })

/*
 * Using __builtin_constant_p(x) to ignore cases where the return
 * value is always the same.  This idea is taken from a similar patch
 * written by Daniel Walker.
 */
# ifndef likely
#  define likely(x)     (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 1))
# endif
# ifndef unlikely
#  define unlikely(x)   (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 0))
# endif

__builtin_constant_p()

__builtin_constant_p는 인수가 컴파일 시 상수로 알려져 있으면 정수 1을 반환하고 그렇지 않으면 0을 반환합니다.

참고

 

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()

참고

RCU(Read Copy Update) -1-

RCU History

  • RCU는 읽기 동작에서 블러킹 되지 않는 read/write 동기화 메커니즘
  • 2002년 커널 버전 2.5.43에서 소개됨
  • 2005년 PREEMPT_RCU가 추가됨
  • 2009년 user-level RCU도 소개됨

 

기능

  • RCU는 read-side overhead를 최소화하는데 목적이 있기 때문에 동기화 로직이 읽기 동작에 더 많은 비율로 사용되는 경우에만 사용한다. 수정 동작이 10%이상인 경우 오히려 성능이 떨어지므로 다른 동기화 기법을 선택해야 한다.
  • RCU는 writing 동작에서는 기존과 같은 동기화 기법을 사용하고 있다. 즉 같은 자료에 동시에 접근하는 여러 개의 writer 들끼리는 내부적으로 rcu가 아닌 다른 lock으로 보호하고 있다.
  • weakly ordered CPU(out of order execution)를 위해 메모리 접근에 대한 order를 적절히 관리해야 하는데 rcu_dereference()를 사용하면 이를 완벽히 수행할 수 있다.
  • PREEMPT_RCU
    • 이 옵션을 사용하면 read-side critical section에서 preemption 될 수 있다.
    • read-side critical section에서 sleep 기능이 필요한 경우가 아니면 SRCU 대신 RCU를 사용하는 것이 더 빠르고 사용하기 쉽다.
    • 참고로 tree RCU와 tiny RCU는 non-preemtable로 구현되어 있다.

 

장/단점

  • 장점
    • 성능 향상(특히 read) – zero wait, zero overhead
    • 확장성 좋음
    • deadlock 이슈 없음
    • priority inversion 이슈 없음 (priority inversion & priority inheritance)
    • unbounded latency 이슈 없음
    • 메모리 leak hazard 이슈 없음
  • 단점
    • 사용이 약간 복잡
    • 쓰기 동작에서는 다른 동기화 기법보다 조금 더 느리다.

 

RCU 구현

  • Classical RCU – a.k.a tiny RCU
    • CONFIG_TINY_RCU 커널 옵션
    • single 데이터 스트럭처
    • CPU가 많아지는 경우 성능 떨어짐
      • 현재 커널에서 UP이고 non-preempt-able일때 디폴트로 선택된다.
  • Hierarchical RCU – a.k.a tree RCU
    • CONFIG_TREE_RCU 커널 옵션
    • tree 확장된 RCU 구현
    • 현재 커널에서 SMP이고 non-preempt-able일때 디폴트로 선택된다.
  • Preemptible tree-based hierarchical RCU
    • preempt-able(CONFIG_PREEMPT_RCU 커널 옵션)을 사용하는 최근 linux kernel의 기본 RCU이다.
    • tree 확장된 RCU 구현
    • read-side critical section에서 preemption이 지원
    • SRCU
      • CONFIG_SRCU 커널 옵션
      • read-side critical section에서 sleep 가능
  • URCU
    • Userspace RCU (liburcu)

 RCU 구현 선택

RCU를 선택하여 사용할 때 일반적으로 다음과 같이 나누어 선택할 수 있다.

  • CONFIG_TINY_RCU
    • CONFIG_PREEMPT=n, CONFIG_SMP=n
    • footprint가 작은 UP 시스템에서 운영할 때 적절하다.
  • CONFIG_TREE_RCU
    • CONFIG_PREEMPT=n, CONFIG_SMP=y
    • SMP 시스템이고 서버로 운영할 때 적절하다.
  • CONFIG_TREE_PREEMPT=y
    • CONFIG_PREEMPT=y
    • 빠른 응답을 요구하는 임베디드 시스템에서 운영할 때 적절하다.

 

추가적으로 절전을 요구하는 시스템에서 다음과 같은 설정을 사용한다.

  • CONFIG_RCU_FAST_NO_HZ=y
  • CONFIG_RCU_NOCB_CPU=y

 

더 자세한 커널 파라메터 설정은 다음 문서를 참고한다.

 

RCU 성능

reader-side에서의 성능 비교 (rwlock vs RCU)

rcu2

(통계: lwn.net 참고)

리눅스 커널에서의 사용율 증가

rcu3

일반 lock 획득시의 나쁜 성능

  • lock 획득하는데 소요하는 자원이 critical section을 수행하는 것에 비해 수백배 이상 over-head가 발생한다.

rcu4

 

RCU  기본 요소

RCU는 다음과 같이 3가지의 기본 요소와 특징이 있다.

  • Reader
    • rcu_read_lock()과 rcu_read_unlock() 코드 범위의 Read-side critical section이다.
    • 접근에 대한 주의
      • 가장 주의 할 것으로 보호 받아야 할 데이터(protected rcu data)에 접근할 때 항상 이 영역내에서만 접근하여야 한다.
      • 이 영역을 벗어난 사용은 RCU 규칙을 벗어나는 것이며 존재하지 않는 자료 또는 잘못된 데이터로의 접근이될 수 있다.
      • 실제 보호 받아야 할 데이터에 접근하기 전에 메모리 배리어를 사용한 후에 참조하여야 한다.
    • 구현에 따른 차이
      • non-preemptable RCU 커널을 사용하는 경우에는 read_rcu_lock() 내부에서 preemption을 금지하는 코드만 적용된다. sleep하는 blocked api를 사용하면 안되고 가급적 빨리 빠져나와야 한다.
      • preemptable RCU 커널을 사용하는 경우에는 read_rcu_lock() 내부에서 로컬 카운터를 증가시키고 read_rcu_unlock() 내부에서 로컬 카운터를 감소시킨다. 이 때에는 sleep 가능한 blocked api의 사용도 가능한다.
  • Updater
    • 기존의 여러 가지 락 중 하나를 사용하여 데이터를 보호하고 수정한다.
    • 실제 보호 받아야 할 데이터에 접근하기 전에 메모리 배리어를 사용한 후에 참조하여야 한다.
    • 보호 받을 자료를 복사하여 수정한 후 비동기 또는 동기 rcu 호출을 요청한다.
  • Reclaimer
    • Update에서 수정한 작업이 새로운 Reader에서 접근할 수 있도록 실제 데이터에 반영된다.
    • 안전하게 업데이트되도록 지난 데이터에 접근하는 Reader 들이 없음을 보장하는 Grace period가 지난 후에 반영한다.

rcu1

 

기본 구조체 노드에서의 RCU 사용

Reader: RCU node를 사용할 때

  • Read side critical section의 시작은 rcu_read_lock()으로 시작한다.
    • non-preemptable RCU 커널을 사용하는 경우에는 이 구간에서 preemption을 금지시킨다.
      • 이 영역에서는 sleep하는 blocked api를 사용하면 안되고 가급적 빨리 빠져나와야 한다.
    • preemptable RCU 커널을 사용하는 경우에는 로컬 카운터를 증가시킨다.
      • 이 영역에서도 sleep 가능하다.
  • 실제 보호 받아야 할 데이터에 접근하기 전에 메모리 배리어를 사용한 후에 참조하여야 하는데 이를 쉽게 할 수 있도록 rcu_dereference()와 같은 매크로 함수를 사용하면 편리하다. 이를 사용하여 안전하게 dereference된 RCU-protected pointer 값을 얻어온다.
    • read critical section을 완료하면 더 이상 dereference된 pointer를 사용할 수 없으므로 이 포인터를 이용하여 얻어올 해당 자료의 l-value 값 들을 읽어온다.(구조체 전체를 복사하여 가져오거나…)
  • Read side critical section의 끝은 read_rcu_unlock() 함수로 완료한다.
    • non-preemptable RCU 커널을 사용하는 경우에는 preemption를 다시 허용시킨다.
    • preemptable RCU 커널을 사용하는 경우에는 로컬 카운터를 감소시킨다.

 

다음 동기화되어 보호받아야 할 데이터의 멤버 a를 얻어오는 코드를 확인한다.

rcu5b

int foo_get_a(void)
{
	int retval;
	rcu_read_lock();
	retval = rcu_dereference(gbl_foo)->a;
	rcu_read_unlock();
	return retval;
}

 

Updater: RCU node의 수정

  • 기존 노드 데이터를 곧바로 수정하지 않고 복사(Read-Copy)한 후 그 복사한 자료를 수정(Update)해야 하므로 준비 과정으로 새로운 노드 데이터를 먼저 할당한다.
  • Write side critical section의 시작은 기존 lock 중 적절한 하나를 사용한다.
  • rcu_dereference_protected() 매크로 함수를 사용하여 매모리 배리어를 사용한 후 안전하게 노드를 가리키는 포인터를 얻어온다.
  • 기존 노드 데이터에 대한 직접 수정은 금지된다. 곧바로 수정하지 않고 복사한 후에 수정 작업을 진행해야 다른 Reader 들이 안전하게 기존 노드 데이터를 사용할 수 있다.
  • rcu_assign_pointer()를 사용하여 먼저 매모리 배리어를 사용한 후 안전하게 노드 포인터를 교체한다.
  • 교체가 완료되었으면 Write side critical section의 끝으로 사용한 lock을 닫는다.
  • 마지막으로 기존 노드 메모리 삭제를 위해 다른 Reader 들이 접근하지 않는 것이 보장되는 시간에 기존 노드 메모리를 삭제할 수 있도록 rcu 동기 또는 비동기 호출을 한다.
    • call_rcu:
      • rcu 비동기 호출로 non-blocking 함수이다.
      • 모든 기존 RCU read-side critical sections들이 끝나면 인수로 요청한 함수를 호출한다.
    • synchronize_rcu():
      • rcu 동기 호출로 blocking 함수이다.
      • 모든 기존 RCU read-side critical sections들이 끝날 때까지 이 함수내에서 기다리며 그 후 인수로 요청한 함수를 호출한다.

 

아래 그림과 같이 기존 노드를 안전하게 수정하기 위해 복제 후 수정하고 기존 노드는 삭제 요청한다.

rcu7b

void foo_update_a(int new_a)
{
	struct foo *new_fp;
	struct foo *old_fp;
	new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
	spin_lock(&foo_mutex);
	old_fp = rcu_dereference_protected(gbl_foo,
		 lockdep_is_held(&foo_mutex));
	*new_fp = *old_fp;
	new_fp->a = new_a;
	rcu_assign_pointer(gbl_foo, new_fp);
	spin_unlock(&foo_mutex);
	call_rcu(&old_fp->rcu, foo_reclaim); 
}

 

Reclaimer: RCU node 사용 완료 후 폐기

  • 기존 데이터의 다른 Reader 들에 의해 사용되지 않음이 확인되면 grace periods 이후에 삭제하여 메모리를 회수한다.
  • 참조 카운터가 0이되면 삭제하는 것은 conceptual한 것이다. 글로벌 참조 카운터를 atomic하게 업데이트하는 구조(spin-lock)의 동기화를 사용하지 않아야 하므로 실제 구현은 더 복잡한다.

rcu6b

void foo_reclaim(struct rcu_head *rp)
{
	struct foo *fp = container_of(rp, struct foo, rcu);
	foo_cleanup(fp->a);
	kfree(fp);
} 

 

리스트에서의 RCU 사용

Reader: RCU node를 사용할 때

rcu13

void disp_foo(void)
{
	rcu_read_lock();
	list_for_each_entry_rcu(p, head, list) {
		disp_foo();
	}
	rcu_read_unlock();
}

 

Updater: RCU node의 수정

  • list_replace_rcu()를 수행한 순간 역방향 연결은 끊어진 반면 순방향 연결은 계속 살아있다.

rcu14

void foo_update_a(int new_a)
{
	struct foo *new_fp;
	struct foo *old_fp = search(head, key);
	if (old_fp == NULL) {
	/* Take appropriate action, unlock, and return. */
	}
	new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
	*new_fp = *old_fp;
	new_fp->a = new_a;
	list_replace_rcu(&old_fp->list, &new_fp->list);
	call_rcu(&old_fp->rcu, foo_reclaim); 
}
static inline void list_replace_rcu(struct list_head *old,
                                struct list_head *new)
{
        new->next = old->next;
        new->prev = old->prev;
        rcu_assign_pointer(list_next_rcu(new->prev), new);
        new->next->prev = new;
        old->prev = LIST_POISON2;
}

 

Reclaimer: RCU node 사용 완료 후 폐기

  • Grace periods를 지난 후 삭제 대상 노드를 모두 clean-up한다.

rcu15

void foo_reclaim(struct rcu_head *rp)
{
	struct foo *fp = container_of(rp, struct foo, rcu);
	foo_cleanup(fp->a);
	kfree(fp);
}

 

GP(Grace Period)

사용자는 특정 자료의 동기화를 위해 두 가지의 관점에서 처리한다.

  • 읽기 처리만 수행하는 read-side critical section이 있고 이를 Reader로 부른다.
  • 변경 처리가 포함된 write-side critical section이 있고 이를 Updater 또는 Writer로 부른다.

 

Writer 발생되는 시점, 즉 write-side critical section 부터 시작되는 구간 3가지를 정리해보았다.

  • Removal 구간: write-side critical section 구간에서는 읽어서(Read() 사본(Copy)을 만들고 변경(Update) 작업을 한다.
  • Grace Period 구간: Removal을 수행하는 자료에 관련된 Reader들의 처리가 완료됨을 보장할 수 있도록 대기하는 구간이다.
  • Reclamation 구간: 기존 사본을 원본에 적용하는 구간이다.

 

Removal(Read-Copy-Update)이 진행되는 동안 해당 데이터에 접근하고 있는 Reader들을 보호하기 위해 Removal은 기존 Reader들이 접근하고 있는 자료는 곧바로 수정하지 않고 이를 먼저 Copy한 후 Update하여 사용한다. 결국 Reader들은 원본 자료에만 접근하므로 안전하게 데이터에 접근할 수 있다.

 

Removal이 완료된 후 작업된 사본을 원본에 반영해야 하는데 곧바로 반영하면 각 cpu에서 동시에 처리되고 있는 Reader들에 문제가 발생한다. 따라서 Removal 기간 동안 같은 자료에 접근한 Reader들의 처리가 모두 완료될 때까지 기다려야 하는데 이 구간을 GP라고 한다.

 

GP의 완료를 인지하면 사본을 원본에 반영하고 필요 없어진 자료는 폐기하는 Reclamation 구간이 시작된다. 이러한 처리들은 RCU의 후CB(Call-Back) 함수를 리스트에 보관해 두었다가 Reclamation 구간에서 호출하여 처리한다.

 

다음 그림을 보고 Writer에 의해 발생되는 3가지 구간을 확인한다. 아래의 Grace Period는 conceptual한 의미이고, Min Grace Period로 불린다. Removal 기간 중 관련된 Reader들의 끝 부분이 곧바로 인식되지 않으므로 Grace Period가 끝나는 지점을 감지(detection) 하는 방법을 사용한다.

 

 

Grace Period의 종료 감지

커널이 Min Grace Period가 완료됨을 곧바로 인식하지 못하므로 실제 GP가 완료된 것을 감지하는 것은 특수한 기법이 필요하다. Reader(read-side critical section) 구간에서 성능을 저하시키는 추가 작업을 하지 않는 것이 핵심이므로 이 구간이 완료됨을 알아내기 위해 모든 cpu들이 QS(Quiescent State) 상태를 지나간 경우 GP가 완료된 것으로 판정한다.

 

 

QS(Quiescent State)

QS(Quiescent State)는 Reader 간의 사이 시간 상태로 GP 구간 전 이미 진행되고 있었던 Reader의 구간이 끝난 것을 인지할 목적으로 사용한다. QS 상태가 패스되었는지 확인하는 방법은 다음과 같은 몇 가지 방법을 사용한다.

각 cpu에서 태스크와 태스크의 사이에 호출되는 스케줄 틱을 이용하여 이 인터럽트 구간을 이용하는 rcu_sched의 3가지 방법과, softirq를 사용하는 rcu_bh의 1가지 방법을 알아본다.  non-preemptable rcu에서는 context switch 진입만으로도 Q.S 상태가 지난 것으로 간주되지만 preemtable rcu에서는 nested 카운터도 읽어 0이어야 Q.S가 지난 것으로 간주한다.

    • rcu_sched
      • Context Switch
        • __schedule() 함수내에서 해당 cpu는 q.s 상태로 전환되어 해당 cpu에서 Reader의 완료를 보장한다.
      • 유저 모드 실행 후 스케줄 틱 진입
        • 커널에서 실행되는 Reader가 유저 태스크를 수행했었다는 것은 이미 context switch를 완료했다는 의미이므로 해당 cpu에서 Reader의 완료를 보장한다.
        • rcu_check_callbacks()
      • Dynticks or idle
        • 커널에서 실행되는 Reader가 Idle 태스크를 수행한다는 것은 이미 context switch를 완료했다는 의미이므로 해당 cpu에서 Reader의 완료를 보장한다.
    • rcu_bh
      • irq enable 상태이고 softirq 외부 코드

 

다음 그림과 같이 conceptual 수준에서의 QS는 Reader들 간의 시간으로 각 QS는 기존 Reader의 처리가 완료되었음을 보장하는 기간이다.

Candidate Quiescent State & Observed Quiescent State

다음 그림은 Min GP 이후 detect된 Q.S가 검정색 원으로 표시되었다. 각 cpu의 Q.S가 검출되면 실제 GP가 완료되었음을 알 수 있다.

 

조금 더 conceptual 수준을 구현 레벨로 약간 확장해보면 Write가 끝나면 GP가 시작하는데 이 때 각 cpu의 QS 상태를 모두 클리어한다. 그 후 모든 cpu의 QS가 한 번 이상 패스되면 GP가 끝나고 Reclamation이 진행된다.

 

다음 그림은 커널에서 실제 구현 레벨에서 QS 인지를 하는 과정을 보여준다. RCU Reader 이후 곧바로 cpu가 Quiescent State로 변경되는 것이 아니라 context switch 등이 일어났음을 알 수 있는 포인트에서 Quiescent State가 시작한다.

  • 구현 레벨이 상당히 복잡하므로 아래 그림만 보아서는 쉽게 이해가 가지 않을 수 있다.
  • cpu#0번의 경우를 먼저 살펴보자. conceptual 레벨과 다르게 실제 구현에서는 reader가 완료되자마자 q.s를 인식하지 못한다. 유저 태스크에 진입하면 q.s가 시작하지만 GP가 시작됨과 동시에 q.s가 모두 클리어되었었음을 기억해야 한다. 때문에 다른 태스크의 전환을 수행하는 context switch를 통해 q.s를 인지하게 된다.
  • cpu#3번을 보면 역시 reader가 끝난 후 유저 태스크에 진입하는 것으로 q.s가 시작됨을 알 수 있다. 이 또한 GP가 시작됨과 동시에 클리어되고 스케줄 틱이 발생하여 q.s를 인지하게된다.
  • cpu#5번의 경우 q.s를 인지하였고 모든 cpu의 q.s가 설정되었음을 알게되었다. 이 때 Reclamation 구간이 시작된다.

 

call_rcu() & synchronize_rcu()

  • 모든 RCU read-side critical sections들이 끝나기를 기다린다.
  • read-side critical section 사용시 규칙: 모든 read-side critical section 즉 rcu_read_lock() 과 rcu_read_unlock()사이에는 block or sleep되면 안된다.
  • 모든 CPU의 context switch가 완료되면 RCU read-side critical section period는 완전히 끝난것으로 보장할 수 있게 되므로 모든 read-side critical section들이 안전하게 끝난것을 의미
  • 삭제될 old 데이터들은 다른 Reader가 참조하고 있는 동안(Grace Period) 삭제 보류된 채로 있다가 old data를 참조하는 마지막 Reader의 사용이 끝나면 Reclamation을 진행하게 된다.

 

 read-side critical section period 보장

 

기존 rwlock 구현 소스를 rcu 구현 소스로 변경 예제

struct el {
	struct list_head list;
	long key;
	spinlock_t mutex;
	int data;
};
spinlock_t 	listmutex;                
struct 	el 	head;

 

search()

int search(long key, int *result) 
{
	struct list_head *lp;
	struct el *p;
	read_lock();
	list_for_each_entry(p, head, lp) {
		if (p->key == key) {
			*result = p->data;
			read_unlock();
			return 1;
		}
	}
	read_unlock();
	return 0;
}
int search(long key, int *result) 
{
	struct list_head *lp;
	struct el *p;
	rcu_read_lock();
	list_for_each_entry_rcu(p, head, lp) {
		if (p->key == key) {
			*result = p->data;
			rcu_read_unlock();
			return 1;
		}
	}
	rcu_read_unlock();
	return 0;
}

 

delete()

int delete(long key)
{
	struct el *p;
	write_lock(&listmutex);
	list_for_each_entry(p, head, lp) {
		if (p->key == key) {
			list_del(&p->list);
			write_unlock(&listmutex);
			kfree(p);
			return 1;
		}
	}
	write_unlock(&listmutex);
	return 0;
}
int delete(long key)
{
	struct el *p;
	spin_lock(&listmutex);
	list_for_each_entry(p, head, lp) {
		if (p->key == key) {
			list_del_rcu(&p->list);
			spin_unlock(&listmutex);
			synchronize_rcu();
			kfree(p);
			return 1;
		}
	}
	spin_unlock(&listmutex);
	return 0;
}

 

RCU API 목록

RCU list traversal:

  • list_entry_rcu
  • list_first_entry_rcu
  • list_next_rcu
  • list_for_each_entry_rcu
  • list_for_each_entry_continue_rcu
  • hlist_first_rcu
  • hlist_next_rcu
  • hlist_pprev_rcu
  • hlist_for_each_entry_rcu
  • hlist_for_each_entry_rcu_bh
  • hlist_for_each_entry_continue_rcu
  • hlist_for_each_entry_continue_rcu_bh
  • hlist_nulls_first_rcu
  • hlist_nulls_for_each_entry_rcu
  • hlist_bl_first_rcu
  • hlist_bl_for_each_entry_rcu

RCU pointer/list update:

  • rcu_assign_pointer
  • list_add_rcu
  • list_add_tail_rcu
  • list_del_rcu
  • list_replace_rcu
  • hlist_add_behind_rcu
  • hlist_add_before_rcu
  • hlist_add_head_rcu
  • hlist_del_rcu
  • hlist_del_init_rcu
  • hlist_replace_rcu
  • list_splice_init_rcu()
  • hlist_nulls_del_init_rcu
  • hlist_nulls_del_rcu
  • hlist_nulls_add_head_rcu
  • hlist_bl_add_head_rcu
  • hlist_bl_del_init_rcu
  • hlist_bl_del_rcu
  • hlist_bl_set_first_rcu

RCU:

  • rcu_read_lock
  • synchronize_net
  • rcu_barrier
  • rcu_read_unlock
  • synchronize_rcu
  • rcu_dereference
  • synchronize_rcu_expedited
  • rcu_read_lock_held
  • call_rcu
  • rcu_dereference_check
  • kfree_rcu
  • rcu_dereference_protected

bh:

  • rcu_read_lock_bh
  • call_rcu_bh
  • rcu_barrier_bh
  • rcu_read_unlock_bh
  • synchronize_rcu_bh
  • rcu_dereference_bh
  • synchronize_rcu_bh_expedited
  • rcu_dereference_bh_check
  • rcu_dereference_bh_protected
  • rcu_read_lock_bh_held

sched:

  • rcu_read_lock_sched
  • synchronize_sched
  • rcu_barrier_sched
  • rcu_read_unlock_sched
  • call_rcu_sched
  • synchronize_sched_expedited
  • rcu_read_lock_sched_notrace
  • rcu_read_unlock_sched_notrace
  • rcu_dereference_sched
  • rcu_dereference_sched_check
  • rcu_dereference_sched_protected
  • rcu_read_lock_sched_held

SRCU:

  • srcu_read_lock
  • synchronize_srcu
  • srcu_barrier
  • srcu_read_unlock
  • call_srcu
  • srcu_dereference
  • synchronize_srcu_expedited
  • srcu_dereference_check
  • srcu_read_lock_held
  • Initialization/cleanup
  • init_srcu_struct
  • cleanup_srcu_struct

All: lockdep-checked RCU-protected pointer access

  • rcu_access_pointer
  • rcu_dereference_raw
  • RCU_LOCKDEP_WARN
  • rcu_sleep_check
  • RCU_NONIDLE

 

소스 분석

rcu_dereference()

  • rcu_dereference()는 안전하게 참조(dereference)된 RCU-protected pointer 값을 얻어온다.

rcu10

 

rcu_read_lock()

  • read-side critical section 시작

rcu11

 

rcu_assign_pointer()

  • RCU로 보호되는 포인터(RCU-protecte pointer)에 새로운 값을 할당하기 위해 사용

rcu12

 

참고

 

BKL(Big Kernel Lock)

  • 커널 버전 2.0에서 SMP가 소개됨
  • BKL은 giant-lock, big-lock 또는 kernel-lock이라고 알려졌었다.
  • 2.0 커널에서는 한 번에 하나의 스레드만이 커널 모드에서 동작하기 위해 lock을 획득하여야 커널 모드로 진입이 되었고, 나머지 CPU는 lock을 획득하기 위해 대기하였다.
  • 성능 및 리얼 타임 application에 대한 latency 이슈로 BKL은 spin-lock, mutex, RCU등으로 대체되기 시작함.
  • 리눅스 초창기에 SMP를 위해 구현된 BKL은 커널 2.6에서 일부 VFS와 몇개의 file system에만 남아있고 거의 대부분 제거되었다.
  • 2011년 커널 2.6.39에서 마지막 BKL 구현이 제거되었다.

BKL Functions

  • lock_kernel(): Acquires the BKL
  • unlock_kernel(): Releases the BKL
  • kernel_locked(): Returns nonzero if the lock is held and zero otherwise (UP always returns nonzero)

Synchronization

  • BKL은 CPU가 동시에 커널에  진입을 하는 것을 막아 동기화 문제를 해결한다.

bkl