Scheduler -3- (Preemption & Context Switch)

 

멀티 태스킹

arm 아키텍처에서 각 cpu core들은 한 번에 하나의 스레드를 동작시킬 수 있다. (특정 아키텍처에서 cpu core 당 2 개 이상의 h/w 스레드를 지원하기도한다. 예: 인텔의 하이퍼스레드 등) 사용자가 요청한 여러 개의 태스크를 동시에 처리하기 위해 각 태스크들을 일정 주기 시간을 분할하여 스케줄하는 방법을 사용한다.

 

다음 그림과 같이 시간 분할하여 스케줄한 예를 보여준다. (1 core 시스템에서 디폴트 스케줄 레이턴시: 6ms)

  • cpu#0 코어에서 3개의 태스크를 구동한 예:
    • 3개의 태스크 각 A, B, C 태스크가 각자 지정된 로드 weight 비율로 6ms 스케줄링 레이튼시 간격으로 스케줄 처리하는 것으로 멀티태스킹을 수행한다.
  • cpu#1 코어에서 1개의 태스크를 구동한 예:
    • 1개의 태스크는 경쟁하는 태스크가 없으므로 계속 동작한다. sleep 하는 구간에서는 idle 태스크가 대신 동작한다.
  • cpu#2 코어에서 10개의 태스크를 구동한 예:
    • 8개를 초과하는 태스크의 경우 디폴트 스케줄링 레이튼시를 초과하므로 지정된 최소 할당 시간(0.75ms) x 태스크 수를 산출하여 스케줄링 레이턴시를 산출하여 처리한다.

 

Preemption

한 개의 태스크가 cpu 시간을 독차지하지 못하게 제어를 할 필요가 있어 다음과 같은 순간에 다른 태스크의 전환을 수행한다.

 

1) 양보

다음 그림과 같이 유저/커널 태스크의 구분 없이 모든 preemption 모드에서 schedule() 함수가 동작하는 경우 다음 수행하여야 할 태스크를 선택한다.

 

2) 유저 선점

다음 그림과 같이 유저 태스크 동작 중 인터럽트에 의해 선점 요청이 이루어진 경우 인터럽트 복귀 시 리스케줄을 수행한다.

  • 타이머 인터럽트에서 현재 태스크의 런타임이 다 소진되었거나, 기타 장치 인터럽트에서 우선 처리할 태스크가 있는 경우 요청된다.

3) 커널 선점
  • CONFIG_PREEMPT_NONE
    • 커널 스레드가 양보하지 않으면 preemption되지 않으므로, 보통 커널 스레드 내부 코드의 적절한 위치에 리스케줄 요청 플래그를 체크하여 양보를 하는 방법을 사용한다.
  • CONFIG_PREEMPT_VOLOUNTRY
    • 커널 스레드가 양보하지 않으면 preemption되지 않는 것은 동일하다. 단 커널 API의 곳곳에 preemption point를 두었고 이 곳에서 리스케줄 요청 플래그를 확인하고 직접 양보를 수행한다.
  • CONFIG_PREEMPT
    • 유저 선점과 동일하게 동작한다.

 

다음 그림은 커널 선점에 대해 3개의 preemption 모델별 처리 차이를 보여준다.

 

런타임 소진에 따른 스케줄(유저 선점 예)

유저 태스크에 주어진 로드 weight 비율만큼의 산출된 런타임이 다 소진된 경우 이를 체크하기 위해 타이머 인터럽트가 필요하다.

  • hrtick을 사용하는 시스템에서는 산출된 런타임에 맞춰 타이머 인터럽트를 생성하고 그 때마다 런타임 소진을 체크하므로 just하게 스케줄할 수 있다
  • periodic tick을 사용하는 시스템에서는 매 틱마다 런타임 소진을 체크한다.  런타임을 초과하여 사용한 런타임은 나중에 그 만큼 빼고 처리된다.
    • periodic tick은 엄밀히 런타임 소진 또는 vruntime이 가장 작은 태스크로 스케줄링이된다.

 

다음 그림은 유저 태스크들을 대상으로 hrtick과 legacy periodic 틱을 사용하는 두 개의 예를 보여준다.

 

CONFIG_PREEMPT 커널 옵션을 사용한 경우에는 커널 태스크가 동작 시 런타임 소진에 의해 선점 요청을 하면 위의 유저 태스크 상황과 동일하게 동작한다. 그러나 다른 커널 옵션을 사용하는 경우 양보 코드 및 preemption point에 의지하여 선점을 하는 것에 주의해야 한다.

 

preemption이 일어나는 것을 막아야 할 때?

  • preemption은 동기화 문제를 수반한다.
  • critical section으로 보호받는 영역에서는 preemption이 발생하면 안되기 때문에 이러한 경우 preempt_disable()을  사용한다.
  • preempt_disable() 코드에서는 단순히 preempt 카운터를 증가시킨다.
  • 인터럽트 발생 시 preempt 카운터가 0이 아니면 스케쥴링이 일어나지 않도록 즉 다른 스레드로의 context switching이 일어나지 않도록 막는다.
  • 물론 interrupt를 원천적으로 disable하는 경우도 preemption 이 일어나지 않는다.

 

리눅스 preemption 모델의 특징

리눅스는 유저 모드에서는 태스크에 할당받은 time slice에 대해 모두 소진하기 전이라도 다른 태스크에 의해 preemption 되어 현재 태스크가 sleep될 수 있다. 하지만 커널 스레드나 커널 모드에서는 다음과 같이 4가지의 preemption 모델에 따라 동작을 다르게 한다.

PREEMPT_NONE:

  • 반응 속도(latency)는 최대한 떨어뜨리되 배치 작업을 우선으로 하여 성능에 최적화 시켜 서버에 적합한 모델이다.
  • 100hz → 250/1000hz의 낮은 타이머 주기를 사용.
  • context switching을 최소화

 

PREEMPT_VOLUNTARY:

  • Voluntary Kernel Preemption (Desktop)
  • 오래 걸릴만한 api 또는 드라이버에서 중간 중간에 preemption point를 두어 리스케줄 요청한 태스크들을 먼저 수행할 수 있도록 preemption 될 수 있게 한다. (중간 중간 필요한 preemption point에서 스케줄을 변경하게 한다.)
  • 어느 정도 반응 속도(latency)를 높여 키보드, 마우스 및 멀티미디어 등의 작업이 가능하도록 하고 성능도 일정부분 보장하게 하도록한 데스크탑에 적합한 모델이다.
  • preemption points
    • 커널 모드에서 동작하는 여러 코드에 explicit preemption points를 추가하여 종종 reschedule이 필요한지 확인하여 preemption이 사용되어야 하는 빈도를 높힘으로 preemption latency를 작게하였다.
    • 이러한 preemption 포인트의 도움을 받아 급한 태스크의 기동에 필요한 latency가 100us 이내로 줄어드는 성과가 있었다.
    • preemption point는 보통 1ms(100us) 이상 소요되는 루틴에 보통 추가한다.
    • 현재 커널에 거의 천 개에 가까운 preemption point가 존재한다.

 

PREEMPT:

  • Preemptible Kernel (Low-Latency Desktop)
  • 커널 모드에서도 언제나 preemption을 허용하여(인터럽트 및 preemption disable 시 제외) 거의 대부분의 시간동안 우선 순위가 높은 태스크가 먼저 수행되도록 스케줄링 된다. 따라서 이 옵션을 사용하는 경우에는 preemption point가 필요없으므로 동작하지 않는다.
  • 반응 속도(latency) 빨라야 하는 대략 밀리세컨드의 latency가 필요한 네트웍 장치등의 임베디드 시스템에서 적합한 모델이다

 

PREEMPT_RT:

  • 아직 mainline에 등록되지 않았다.
  • 따라서 Real-tIme OS 기능이 필요한 경우 Real-time OS를 연구하는 그룹에서 유지보수하는 리눅스를 사용해야 한다. (계속되고 있는 프로젝트)
  • 사실 full preempt kernel에 대한 고민이 kernel mainliner들에게 있다. 바로 성능 저하인데 이 때문에 아직까지 mainline에 올리지 못하는 이유이기도 하다. (참고: Optimizing preemption | LWN.net)
    • 예) Linux 3,7.0-rt 과 같이 뒤에 rt가 붙어 있다.
  • 인터럽트 수행중에도 preemption이 가능하다.

 

커널 버전에 따른 preemption 기능

preempt4

  • 커널 버전 2.4까지 user mode만 선점이 가능했었다. (user mode에서 동작중인 process가 system call API를 호출하여 kernel mode로 진입하여 동작 중인 경우에는 선점 불가능)
  • 버전 2.6에 이르러 kernel mode도 선점이 가능해졌다.  (드라이버 수행 중 또는 system call API를 호출하여 kernel mode에 있는 경우에도 다른 태스크로의 선점이 가능해졌다)
    • preemption 모델 중 CONFIG_PREEMPT_NONE 제외
    • kernel mode에서 선점이 가능해졌지만 리눅스가 원래 Real-Time OS 설계가 아닌 관계로 big kernel lock(2중, 3중 critical section 등 사용)으로 인해 필요한 때 인터럽트 응답성이 빠르지 않았다. 물론 현재는 big kernel lock을 다 제거하여 사용하지 않는다.
    • 인터럽트 latency를 줄이기 위해 인터럽트 핸들러를 top-half, bottom-half 두 개의 파트로 나누었다. (Two part interrupt handler | 문c)
  • Real-time 리눅스 커널 패치 PREEMPT_RT가 적용되면서 critical section 및 인터럽트 수행중에서도 preemption이 지원되었다.
    •  SMP 환경에서는 spinlock으로 제어되는 critical section에서 CPU들의 동시 접근 효율이 떨어지면서 문제가 되므로 이를 해결하기 위해 spinlock은 RT 리눅스에서는 preempt_disable을 하지 않도록 mutex를 사용한다. 물론 반드시 preemption이 disable되어야 하는 경우를 위해 그러한 루틴을 위해 raw_spin_lock에서 처리되게 이전하였다.

 

RT(Real-Time) Linux

  • 실시간으로 스케쥴링이 필요한 업무가 생기면서 리눅스에 Real Time 기능이 필요하여 RT(Real Time) 리눅스가 구현되고 있다.
  • RT 리눅스 시스템을 지원하게 되면서 preemption이 빠르게 일어날 수 있도록 lock, interrupt 관련 함수들이 복잡하게 수정되었다.
  •  두 개의 패치
    • 1) PREEMPT_RT 패치
      • 전부는 아니지만 많은 코드가 이미 linux mainline에 통합되었다.
      • spinlocks와 local_irq_save()는 더이상 h/w interrupt를 disable하지 않는다.
      • spinlocks는 더이상 preemption을 disable하지 않는다.
      • raw_로 시작하는 spinlocks와 local_irq_save()는 기존 방식을 사용한다.
      • semaphore와 spinlocks는 priority inheritance를 승계한다.
    • 2) Linux(realtime) extensions
      • Priority Scheduling
      • Real-Time signals
      • Clocks and Timers
      • Semaphores
      • Message Passing
      • Shared Memory
      • Asynchronous and Synchronous I/O
      • Memory Locking
    • 그외
      • Threaded Interrupt
      • RT-Mutexes (based priority inheritance protocol)
      • BKL(Big Kernel Lock)-free(2.6.37)

 

RT Mutex based Priority inheritance protocol

Preemption Point 구현

CONFIG_PREEMPT_VOLUNTARY 커널 옵션을 사용하는 preemption 모델에서 사용하는 preemption point의 대표적인 함수이다.

might_sleep()

include/linux/kernel.h

# define might_sleep() do { might_resched(); } while (0)

CONFIG_PREEMPT_VOLUNTARY 커널에서 preemption point로 동작하여 리스케줄 요청이 있으면서 preemption 가능한 경우 스케줄하여 태스크 선점을 양보한다.

  • 현재 태스크는 슬립되고 다음 실행할 태스크가 선택되어 스케줄되고 실행된다.
  • 커널에서 1ms 이상 소요되는 경우 voluntary preemption 모델을 사용하는 커널을 위해 잠시 우선순위가 높은 태스크를 위해 스스로 양보하고 선점당할 수 있는 포인트를 제공하기 위해 사용된다.
#ifdef CONFIG_PREEMPT_VOLUNTARY
# define might_resched() _cond_resched()
#else
# define might_resched() do { } while (0)
#endif

CONFIG_PREEMPT_VOLUNTARY 커널에서 preemption point로 동작하여 리스케줄 요청이 있는 경우 스케줄한다.

  • CONFIG_PREEMPT_NONE preemption 모델에서는 커널 preemption을 지원하지 않으므로 preemption 포인트를 제공하지 않는다.
  • CONFIG_PREEMPT preemption 모델의 경우는 커널 preemption이 실시간으로 지원되기 떄문에 preemption 포인트가 필요없다.

다음 그림은 might_sleep()을 호출 할 때 voluntary 커널에서 스케줄 함수를 호출하는 과정을 보여준다.

 

_cond_resched()

kernel/sched/core.c

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

리스케줄 요청이 있으면서 preemption 가능한 경우 스케줄을 수행하고 true(1)를 반환한다. 리스케줄 요청이 없는 경우 false(0)를 반환한다.

 

should_resched()
/*              
 * 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 카운터가 0이어서 preemption이 가능하고 리스케줄 요청이 있는 경우 true를 반환한다.

 

tif_need_resched()

include/linux/thread_info.h

#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)

현재 스레드에 리스케줄 요청이 기록되어 있는지 여부를 반환한다. 리스케줄 요청=true(1)

include/linux/thread_info.h

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

현재 스레드에 요청 flag 비트가 설정된 경우 true(1)를 반환한다.

 

need_resched()

include/linux/sched.h

static __always_inline bool need_resched(void)
{
        return unlikely(tif_need_resched());
}

현재 스레드에 리스케줄 요청이 기록되어 있는지 여부를 반환한다. 리스케줄 요청=true(1)

 

Preempt Count

현재 스레드의 preemption 허용 여부를 nest 하여 증/감하는데 이 값이 0이 될 때 preemption 가능한 상태가 된다.

preempt_count()

include/asm-generic/preempt.h

static __always_inline int preempt_count(void)
{
        return current_thread_info()->preempt_count;
}

현재 태스크의 preempt 카운터를 반환한다.

preemption 카운터가 0이되면 preemption이 가능해진다. preemption 카운터의 각 비트를 묶어 preemption을 mask하는 용도로 나누어 구성한다. 어느 한 필드라도 비트가 존재하면 preemption되지 않는다.

 

include/linux/preempt_mask.h

/*
 * We put the hardirq and softirq counter into the preemption
 * counter. The bitmask has the following meaning:
 *
 * - bits 0-7 are the preemption count (max preemption depth: 256)
 * - bits 8-15 are the softirq count (max # of softirqs: 256)
 *
 * The hardirq count could in theory be the same as the number of
 * interrupts in the system, but we run all interrupt handlers with
 * interrupts disabled, so we cannot have nesting interrupts. Though
 * there are a few palaeontologic drivers which reenable interrupts in
 * the handler, so we need more than one bit here.
 *
 * PREEMPT_MASK:        0x000000ff
 * SOFTIRQ_MASK:        0x0000ff00
 * HARDIRQ_MASK:        0x000f0000
 *     NMI_MASK:        0x00100000
 * PREEMPT_ACTIVE:      0x00200000
 */
#define PREEMPT_BITS    8
#define SOFTIRQ_BITS    8
#define HARDIRQ_BITS    4
#define NMI_BITS        1

#define PREEMPT_SHIFT   0
#define SOFTIRQ_SHIFT   (PREEMPT_SHIFT + PREEMPT_BITS)
#define HARDIRQ_SHIFT   (SOFTIRQ_SHIFT + SOFTIRQ_BITS)
#define NMI_SHIFT       (HARDIRQ_SHIFT + HARDIRQ_BITS)

#define __IRQ_MASK(x)   ((1UL << (x))-1)

#define PREEMPT_MASK    (__IRQ_MASK(PREEMPT_BITS) << PREEMPT_SHIFT)
#define SOFTIRQ_MASK    (__IRQ_MASK(SOFTIRQ_BITS) << SOFTIRQ_SHIFT)
#define HARDIRQ_MASK    (__IRQ_MASK(HARDIRQ_BITS) << HARDIRQ_SHIFT)
#define NMI_MASK        (__IRQ_MASK(NMI_BITS)     << NMI_SHIFT)

#define PREEMPT_OFFSET  (1UL << PREEMPT_SHIFT)
#define SOFTIRQ_OFFSET  (1UL << SOFTIRQ_SHIFT)
#define HARDIRQ_OFFSET  (1UL << HARDIRQ_SHIFT)
#define NMI_OFFSET      (1UL << NMI_SHIFT)

#define SOFTIRQ_DISABLE_OFFSET  (2 * SOFTIRQ_OFFSET)

#define PREEMPT_ACTIVE_BITS     1
#define PREEMPT_ACTIVE_SHIFT    (NMI_SHIFT + NMI_BITS)
#define PREEMPT_ACTIVE  (__IRQ_MASK(PREEMPT_ACTIVE_BITS) << PREEMPT_ACTIVE_SHIFT)

다음 그림은 preempt 카운터의 각 비트에 대해 표시하였다.

 

다음 그림은 preempt_count와 관련된 조작 함수와 조회 함수 들을 보여준다.

 

Preempt Enable & Disable

preempt_enable()

include/linux/preempt.h

#ifdef CONFIG_PREEMPT_COUNT
#ifdef CONFIG_PREEMPT
#define preempt_enable() \
do { \
        barrier(); \
        if (unlikely(preempt_count_dec_and_test())) \
                __preempt_schedule(); \
} while (0)

#else
#define preempt_enable() \
do { \
        barrier(); \
        preempt_count_dec(); \
} while (0)
#define preempt_check_resched() do { } while (0)
#endif
#else
#define preempt_enable()                        barrier()
#endif

다음과 같이 preempt 카운터 및 preemption 모델에 따라 다음과 같이 동작한다.

  • CONFIG_PREEMPT_COUNT 사용 및 preemption 모델에 따른 기능
    • CONFIG_PREEMPT
      • preemption 카운터를 감소시키고 그 값이 0이되는 경우 이후부터 아무 때나 preemption을 허용가능하게 한다.
      • 호출 즉시 리스케줄 요청이 있는 경우 스케줄 호출한다.
    • CONFIG_PREEMPT_VOLUNTARY
      • preemption 카운터가 0이되면 preemption point 마다 리스케줄 요청이 있는 경우 스케줄한다.
    • CONFIG_PREEMPT_NONE 사용
      • preemption 카운터를 감소시킨다.
      • preemption 카운터가 0이되어도 preemption point에서 아무것도 수행하지 않는다.
  • CONFIG_PREEMPT_COUNT 미사용
    • preemption 기능을 사용하지 않는다.

 

다음 그림은 preempt_enable()이 preemption 모델에 따라 수행되는 경로를 보여준다.

preempt_count_dec_and_test()

include/linux/preempt.h

#define preempt_count_dec_and_test() __preempt_count_dec_and_test()

preemption 카운터를 감소시키고 그 값이 0이 되어 preemption 가능하고 리스케줄 요청이 있는 경우 true를 반환한다.

 

include/asm-generic/preempt.h

static __always_inline bool __preempt_count_dec_and_test(void)
{
        /*
         * Because of load-store architectures cannot do per-cpu atomic
         * operations; we cannot use PREEMPT_NEED_RESCHED because it might get
         * lost.
         */
        return !--*preempt_count_ptr() && tif_need_resched();
}

preempt_count_dec()

include/linux/preempt.h

#define preempt_count_dec() preempt_count_sub(1)
#define preempt_count_sub(val)  __preempt_count_sub(val)

preemption 카운터를 1 만큼 감소시킨다.

 

preempt_count_sub()

include/linux/preempt.h

#define preempt_count_sub(val)  __preempt_count_sub(val)

preemption 카운터를 val 값 만큼 감소시킨다.

 

include/asm-generic/preempt.h

static __always_inline void __preempt_count_sub(int val)
{
        *preempt_count_ptr() -= val;
}

preemption 카운터를 val 값 만큼 감소시킨다.

 

preempt_disable()

include/linux/preempt.h

#ifdef CONFIG_PREEMPT_COUNT
#define preempt_disable() \ 
do { \
        preempt_count_inc(); \
        barrier(); \
} while (0)
#else
/*
 * Even if we don't have any preemption, we need preempt disable/enable
 * to be barriers, so that we don't have things like get_user/put_user
 * that can cause faults and scheduling migrate into our preempt-protected
 * region.
 */
#define preempt_disable()                       barrier()
#endif

preempt 카운터 및 preemption 모델에 따라 다음과 같이 동작한다.

  • CONFIG_PREEMPT_COUNT 사용
    • preemption 카운터를 증가시킨다.
    • preemption 모델과 관계 없이 이후부터 preemption을 허용하지 않는다.
  • CONFIG_PREEMPT_COUNT 미사용
    • preemption 기능을 사용하지 않는다.

 

다음 그림은 preempt_disable()이 preempt 카운터 사용 여부에 따라 수행되는 경로를 보여준다.

preempt_count_inc()

include/linux/preempt.h

#define preempt_count_inc() preempt_count_add(1)

preemption 카운터를 1 만큼 증가시킨다.

 

preempt_count_add()

include/linux/preempt.h

#define preempt_count_add(val)  __preempt_count_add(val)

preemption 카운터를 val 값 만큼 증가시킨다.

 

include/asm-generic/preempt.h

static __always_inline void __preempt_count_add(int val)
{
        *preempt_count_ptr() += val;
}

preemption 카운터를 val 값 만큼 증가시킨다.

 

스케줄

schedule()

kernel/sched/core.c

asmlinkage __visible void __sched schedule(void)
{
        struct task_struct *tsk = current;

        sched_submit_work(tsk);
        do {
                __schedule();
        } while (need_resched());
}
EXPORT_SYMBOL(schedule);

현재 태스크를 sleep하고 다음 태스크를 스케줄한다. 현재 태스크가 깨어난 후 여전히 리스케줄 요청이 있는 경우 다시 루프를 돈다.

 

__preempt_schedule()

kernel/sched/core.c

#define __preempt_schedule() preempt_schedule()

 

preempt_schedule()

kernel/sched/core.c

/*
 * this is the entry point to schedule() from in-kernel preemption
 * off of preempt_enable. Kernel preemptions off return from interrupt
 * occur there and call schedule directly.
 */
asmlinkage __visible void __sched notrace preempt_schedule(void)
{
        /*
         * If there is a non-zero preempt_count or interrupts are disabled,
         * we do not want to preempt the current task. Just return..
         */
        if (likely(!preemptible()))
                return;

        preempt_schedule_common();
}
NOKPROBE_SYMBOL(preempt_schedule);
EXPORT_SYMBOL(preempt_schedule);

preemption이 가능한 경우에만 현재 태스크를 sleep하고 다른 태스크를 가져와 실행하기 위해 스케줄한다.

 

preemptible()

include/linux/preempt_mask.h

#ifdef CONFIG_PREEMPT_COUNT
# define preemptible()  (preempt_count() == 0 && !irqs_disabled())
#else
# define preemptible()  0
#endif

preemption이 가능한 상태인지 여부를 알아온다. true(1)=preemption 가능한 상태

  • CONFIG_PREEMPT_COUNT 커널 옵션을 사용하지 않는 경우에는 항상 preemption을 할 수 없다.

 

preempt_schedule_common()

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

리스케줄 요청이 있는 동안 루프를 돌며 스케줄을 수행한다.

  • 코드 라인 4에서 스케줄링을 수행하기 위해 preemption 카운터 중 가장 높은 비트를 설정하여 preemption 되지 않도록 막는다.
  • 코드 라인 5에서 현재 태스크는 preemption되어 슬립되고 리스케줄하여 다음 진행할 태스크를 pickup하여 실행시킨다.
  • 코드 라인 6에서 한동안 preemption되어 슬립되었다가 여기서 깨어나게 되면 조금 전에 증가시켰던 비트를 감소시킨다.
  • 코드 라인 13에서 리스케줄 요청이 남아 있는 경우 계속 루프를 돈다.

 

__schedule()

kernel/sched/core.c

/*
 * __schedule() is the main scheduler function.
 *
 * The main means of driving the scheduler and thus entering this function are:
 *
 *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
 *
 *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
 *      paths. For example, see arch/x86/entry_64.S.
 *
 *      To drive preemption between tasks, the scheduler sets the flag in timer
 *      interrupt handler scheduler_tick().
 *
 *   3. Wakeups don't really cause entry into schedule(). They add a
 *      task to the run-queue and that's it.
 *
 *      Now, if the new task added to the run-queue preempts the current
 *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
 *      called on the nearest possible occasion:
 *
 *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
 *
 *         - in syscall or exception context, at the next outmost
 *           preempt_enable(). (this might be as soon as the wake_up()'s
 *           spin_unlock()!)
 *
 *         - in IRQ context, return from interrupt-handler to
 *           preemptible context
 *
 *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
 *         then at the next:
 *
 *          - cond_resched() call
 *          - explicit schedule() call
 *          - return from syscall or exception to user-space
 *          - return from interrupt-handler to user-space
 *
 * WARNING: all callers must re-check need_resched() afterward and reschedule
 * accordingly in case an event triggered the need for rescheduling (such as
 * an interrupt waking up a task) while preemption was disabled in __schedule().
 */

CONFIG_PREEMPT 커널 옵션을 사용하는 preemptible 커널인 경우 커널 모드에서도 preempt가 enable 되어 있는 대부분의 경우 preemption이 가능하다. 그러나 그러한 옵션을 사용하지 않는 커널은 커널 모드에서 preemption이 가능하지 않다. 다만 다음의 경우에 한하여 preemption이 가능하다.

  • CONFIG_PREEMPT_VOLUNTARY 커널 옵션을 사용하면서 cond_resched() 호출 시
  • 명확히 지정하여 schedule() 함수를 호출 시
  • syscall 호출 후 유저 스페이스로 되돌아 갈 때
    • 유저 모드에서는 언제나 preemption이 가능하다. 때문에 syscall 호출하여 커널에서 요청한 서비스를 처리한 후 유저로 돌아갔다 preemption이 일어나면 유저 모드와 커널 모드의 왕래만 한 번 더 반복하게 되므로 overhead가 생길 따름이다. 그래서 유저 스페이스로 돌아가기 전에 preemption 처리를 하는 것이 더 빠른 처리를 할 수 있다.
  • 인터럽트 핸들러를 처리 후 다시 유저 스페이스로 되돌아 갈 때
    • 이 전 syscall 상황과 유사하게 이 상황도 유저 스페이스로 돌아가기 전에 처리해야 더 빠른 처리를 할 수 있다.

 

__schedule()

kernel/sched/core.c

static void __sched __schedule(void)
{
        struct task_struct *prev, *next;
        unsigned long *switch_count;
        struct rq *rq;
        int cpu;

        preempt_disable();
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
        rcu_note_context_switch();
        prev = rq->curr;

        schedule_debug(prev);

        if (sched_feat(HRTICK))
                hrtick_clear(rq);

        /*
         * Make sure that signal_pending_state()->signal_pending() below
         * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
         * done by the caller to avoid the race with signal_wake_up().
         */
        smp_mb__before_spinlock();
        raw_spin_lock_irq(&rq->lock);

        rq->clock_skip_update <<= 1; /* promote REQ to ACT */

        switch_count = &prev->nivcsw;
        if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
                if (unlikely(signal_pending_state(prev->state, prev))) {
                        prev->state = TASK_RUNNING;
                } else {
                        deactivate_task(rq, prev, DEQUEUE_SLEEP);
                        prev->on_rq = 0;

                        /*
                         * If a worker went to sleep, notify and ask workqueue
                         * whether it wants to wake up a task to maintain
                         * concurrency.
                         */
                        if (prev->flags & PF_WQ_WORKER) {
                                struct task_struct *to_wakeup;

                                to_wakeup = wq_worker_sleeping(prev, cpu);
                                if (to_wakeup)
                                        try_to_wake_up_local(to_wakeup);
                        }
                }
                switch_count = &prev->nvcsw;
        }

        if (task_on_rq_queued(prev))
                update_rq_clock(rq);

        next = pick_next_task(rq, prev);
        clear_tsk_need_resched(prev);
        clear_preempt_need_resched();
        rq->clock_skip_update = 0;

        if (likely(prev != next)) {
                rq->nr_switches++;
                rq->curr = next;
                ++*switch_count;

                rq = context_switch(rq, prev, next); /* unlocks the rq */
                cpu = cpu_of(rq);
        } else
                raw_spin_unlock_irq(&rq->lock);

        post_schedule(rq);

        sched_preempt_enable_no_resched();
}

현재 태스크를 슬립시키고 다음 태스크를 선택하여 스케줄한다.

  • 코드 라인 8에서 스케줄 전에 preemtion 되지 않도록 disable 한다.
  • 코드 라인 11에서 per-cpu인 rcu_sched_data.passed_quiesce에 1을 대입하여 rcu 정지 상태에 진입했음을 알린다.
  • 코드 라인 14에서 스케줄 타임에 체크할  항목과 통계를 수행한다.
  • 코드 라인 16~17에서 스케줄 클럭에 high-resolution 타이머를 사용한 경우 hrtick 타이머가 동작중이면 정지시킨다.
  • 코드 라인 27에서 런큐의 clock_skip_update는 RQCF_REQ_SKIP(1) 플래그에서 RQCF_ACT_SKIP(2) 단계로 전환한다.
  • 코드 라인 29에서 기존 태스크의 context 스위치 횟수를 알아온다.
  • 코드 라인 30에서 기존 태스크가 러닝 상태가 아니면서 preemption 카운터 비트 중 PREEMPT_ACTIVE가 설정되지 않은 경우
    • schedule() 함수가 호출되어 진입된 경우 PREEMPT_ACTIVE가 설정되지 않는다.
  • 코드 라인 31~32에서 낮은 확률로 기존 태스크의 시그널 처리가 필요한 경우 태스크 상태를 러닝 상태로 바꾼다.
    • 태스크가 SIGKILL 요청을 받았거나 인터럽터블 상태의 태스크가 시그널 처리를 요청받은 경우
  • 코드 라인 33~34에서 시그널 처리가 필요 없으면 태스크를 deactivation(dequeue) 하고 기존 태스크가 런큐에서 동작하지 않음을 표시한다.
  • 코드 라인 41~47에서 기존 태스크가 워크큐 워커인 경우 슬립시킨다. 깨어난 후 to_wakeup 태스크가 런큐에 없는 경우 엔큐 처리 한다.
  • 코드 라인 51~52에서 기존 태스크가 런큐에 있는 경우 런큐 클럭을 갱신한다.
  • 코드 라인 54~57에서 다음 처리할 태스크를 가져오고 기존 태스크의 리스케줄 요청 플래그를 클리어한다. 런큐의 clock_skip_update는 다시 클리어 단계로 전환한다.
    • x86 아키텍처에서만 clear_preempt_need_resched() 함수를 처리한다.
  • 코드 라인 59~65에서 높은 확률로 다음 처리할 태스크가 기존 태스크가 아닌 경우 런큐의 context 스위치 카운터를 증가시키고 현재 처리하는 태스크를 지정한다. 마지막으로 context 스위칭을 수행한다.
  • 코드 라인 69에서 스케줄 완료 후 처리할 일을 수행한다.
  • 코드 라인 71에서 preempt 카운터를 감소시킨다. 카운터가 0이 되면 preemption이 가능해진다.

 

schedule_debug()

kernel/sched/core.c

/*
 * Various schedule()-time debugging checks and statistics:
 */
static inline void schedule_debug(struct task_struct *prev)
{
#ifdef CONFIG_SCHED_STACK_END_CHECK
        BUG_ON(unlikely(task_stack_end_corrupted(prev)));
#endif                     
        /*
         * Test if we are atomic. Since do_exit() needs to call into
         * schedule() atomically, we ignore that path. Otherwise whine
         * if we are scheduling when we should not.
         */
        if (unlikely(in_atomic_preempt_off() && prev->state != TASK_DEAD))
                __schedule_bug(prev);
        rcu_sleep_check();

        profile_hit(SCHED_PROFILING, __builtin_return_address(0));

        schedstat_inc(this_rq(), sched_count);
}

스케줄 타임에 체크할  항목과 통계를 수행한다.

  • 코드 라인 6~8에서 스택이 손상되었는지 체크한다.
  • 코드 라인 14~15에서 preempt 카운터의 PREEMPT_ACTIVE 비트를 제외한 값이 PREEMPT_CHECK_OFFSET(1)이 아니면서 태스크가 TASK_DEAD 상태가 아니면 “BUG: scheduling while atomic:” 에러 메시지를 출력하고 디버깅을 위해 스택 덤프를 한다.
  • 코드 라인 16에서 rcu sleep을 체크한다.
  • 코드 라인 18에서 SCHED_PROFILING을 동작시킨 경우 수행한다.
  • 코드 라인 20에서 rq->sched_count를 1 증가시킨다.

 

task_stack_end_corrupted()

include/linux/sched.h

#define task_stack_end_corrupted(task) \
                (*(end_of_stack(task)) != STACK_END_MAGIC)

스택의 마지막 경계에 기록해둔 매직 넘버(0x57AC6E9D)가 깨져서 손상되었는지 여부를 알아온다. true(1)=스택 손상

 

hrtick_clear()

kernel/sched/core.c

/*
 * Use HR-timers to deliver accurate preemption points.
 */

static void hrtick_clear(struct rq *rq)
{
        if (hrtimer_active(&rq->hrtick_timer))
                hrtimer_cancel(&rq->hrtick_timer);
}

CONFIG_SCHED_HRTICK 커널 옵션을 사용하여 스케줄 클럭에 high-resolution 타이머를 사용한 경우 hrtick 타이머가 동작중이면 정지시킨다.

 

signal_pending_state()

include/linux/sched.h

static inline int signal_pending_state(long state, struct task_struct *p)
{       
        if (!(state & (TASK_INTERRUPTIBLE | TASK_WAKEKILL)))
                return 0;
        if (!signal_pending(p))
                return 0;
        
        return (state & TASK_INTERRUPTIBLE) || __fatal_signal_pending(p);
}

태스크가 SIGKILL 요청을 받았거나 인터럽터블 상태의 태스크가 시그널 처리를 요청받은 경우 true를 반환한다.

  • 상태가 인터럽터블이면서 wakekill 상태가 아닌 경우 곧바로 false를 반환한다.
  • 태스크가 시그널 펜딩 상태가 아니면 false를 반환한다.
  • 상태가 인터럽터블이거나 요청 태스크로 fatal(SIGKILL) 시그널 요청이 온경우 true를 반환한다.

 

signal_pending()

include/linux/sched.h

static inline int signal_pending(struct task_struct *p)
{       
        return unlikely(test_tsk_thread_flag(p,TIF_SIGPENDING));
}

요청 태스크의 sigpending 플래그 설정 여부를 반환한다.

 

fatal_signal_pending()

include/linux/sched.h

static inline int fatal_signal_pending(struct task_struct *p)
{
        return signal_pending(p) && __fatal_signal_pending(p);
}

요청 태스크로 fatal(SIGKILL) 시그널이 요청되었는지 여부를 반환한다.

 

__fatal_signal_pending()

include/linux/sched.h

static inline int __fatal_signal_pending(struct task_struct *p)
{
        return unlikely(sigismember(&p->pending.signal, SIGKILL));
}

요청 태스크로 SIGKILL 시그널이 요청되었는지 여부를 반환한다.

  • SIGKILL 시그널
    • 태스크를 죽일 떄 요청한다.

 

task_on_rq_queued()

kernel/sched/sched.h

static inline int task_on_rq_queued(struct task_struct *p)
{
        return p->on_rq == TASK_ON_RQ_QUEUED;
}

태스크가 현재 런큐에서 동작중인지 여부를 반환한다.

 

clear_tsk_need_resched()

include/linux/sched.h”

static inline void clear_tsk_need_resched(struct task_struct *tsk)
{
        clear_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
}

요청 태스크에서 리스케줄 요청 플래그를 클리어한다.

 

다음 스케줄할 태스크 선택

pick_next_task()

kernel/sched/core.c

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
        const struct sched_class *class = &fair_sched_class;
        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in
         * the fair class we can call that function directly:
         */
        if (likely(prev->sched_class == class &&
                   rq->nr_running == rq->cfs.h_nr_running)) {
                p = fair_sched_class.pick_next_task(rq, prev);
                if (unlikely(p == RETRY_TASK))
                        goto again;

                /* assumes fair_sched_class->next == idle_sched_class */
                if (unlikely(!p))
                        p = idle_sched_class.pick_next_task(rq, prev);

                return p;
        }

again:
        for_each_class(class) {
                p = class->pick_next_task(rq, prev);
                if (p) {
                        if (unlikely(p == RETRY_TASK))
                                goto again;
                        return p;
                }
        }

        BUG(); /* the idle class will always have a runnable task */
}

다음 스케줄할 최우선 순위의 태스크를 알아온다. (stop -> dl -> rt -> fair -> idle 스케줄러 순)

  • 코드 라인 14~15에서 기존 태스크의 스케줄러가 CFS 스케줄러이고 런큐에서 동작중인 태스크 모두가 CFS 스케줄러에서만 동작하는 경우
  • 코드 라인 16~18에서 CFS 스케줄러의 pick_next_task() 함수를 호출하여 CFS 스케줄러에서 가장 빠르게 처리해야 할 태스크를 알아온다. 만일 낮은 확률로 RETRY_TASK 결과를 가져온 경우 again 레이블로 이동한다.
  • 코드 라인 21~22에서 낮은 확률로 태스크가 선택되지 않은 경우 idle 스케줄러로 요청한다.
  • 코드 라인 24에서 선택된 태스크를 리턴한다.
  • 코드 라인 28에서 stop 스케줄러부터 idle 스케줄 클래스까지 순서대로 돌며 다음 태스크를 가져와서 반환한다. 실패하는 경우 마지막 idle 스케줄러까지 반복한다.

 

다음 그림은 런큐에서 태스크가 수행될 때의 스케줄 순서를 보여준다.

  • 마지막 idle-task 스케줄러 이전까지 수행시킬 task가 없는 경우 부트 프로세스 중에 처음 사용했던 idle 태스크가 사용된다.

 

스케줄 마무리

post_schedule()

kernel/sched/core.c

/* rq->lock is NOT held, but preemption is disabled */
static inline void post_schedule(struct rq *rq)
{
        if (rq->post_schedule) {
                unsigned long flags;

                raw_spin_lock_irqsave(&rq->lock, flags);
                if (rq->curr->sched_class->post_schedule)
                        rq->curr->sched_class->post_schedule(rq);
                raw_spin_unlock_irqrestore(&rq->lock, flags);

                rq->post_schedule = 0;
        }
}

런큐에 post 스케줄이 설정된 경우  현재 태스크에 해당하는 클래스의 post_schedule()을 호출한다.

  • 다음 2개의 스케줄러에 (*post_schedule) 후크 구현이 되어 있다.
    • post_schedule_dl()
      • 현재 런큐에서 동작중인 2개 이상의 dl 태스크들 중 현재 비실행중인 dl 태스크들을 다른 cpu에서 선점하여 실행시킬 수 있게한다.
    • post_schedule_rt()
      • 현재 런큐에서 동작중인 2개 이상의 rt 태스크들 중 현재 비실행중인 rt 태스크들을 다른 cpu에 선점하여 실행시킬 수 있게한다.

 

sched_preempt_enable_no_resched()

include/linux/preempt.h

#define sched_preempt_enable_no_resched() \
do { \
        barrier(); \
        preempt_count_dec(); \
} while (0)

preempt 카운터를 1 감소시킨다.

 

Context Switch

다음과 같은 이름으로도 불리고 동일한 동작을 의미한다. (Interrupt Context Switch는 별개)

  • Process Context Switch
  • Thread Context Switch
  • Task Context Switch
  • CPU Context Switch

 

context_switch()

kernel/sched/core.c

/*
 * context_switch - switch to the new MM and the new thread's register state.
 */
static inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
               struct task_struct *next)
{
        struct mm_struct *mm, *oldmm;

        prepare_task_switch(rq, prev, next);

        mm = next->mm;
        oldmm = prev->active_mm;
        /*
         * For paravirt, this is coupled with an exit in switch_to to
         * combine the page table reload and the switch backend into
         * one hypercall.
         */
        arch_start_context_switch(prev);

        if (!mm) {
                next->active_mm = oldmm;
                atomic_inc(&oldmm->mm_count);
                enter_lazy_tlb(oldmm, next);
        } else
                switch_mm(oldmm, mm, next);

        if (!prev->mm) {
                prev->active_mm = NULL;
                rq->prev_mm = oldmm;
        }
        /*
         * Since the runqueue lock will be released by the next
         * task (which is an invalid locking op but in the case
         * of the scheduler it's an obvious special-case), so we
         * do an early lockdep release here:
         */
        spin_release(&rq->lock.dep_map, 1, _THIS_IP_);

        context_tracking_task_switch(prev, next);
        /* Here we just switch the register state and the stack. */
        switch_to(prev, next, prev);
        barrier();

        return finish_task_switch(prev);
}

새로운 태스크로 context 스위칭한다. 만일 새로운 태스크가 유저 태스크인 경우 가상 공간을 바꾸기 위해 mm 스위칭도 한다.

  • 코드 라인 10에서 다음 태스크로 context 스위치하기 전에 할 일을 준비한다.
  • 코드 라인 19에서 context 스위치 직전에 아키텍처에서 할 일을 수행한다.
    • 현재 x86 아키텍처만 수행한다.
  • 코드 라인 21~25에서 다음 태스크의 mm이 없는 경우 즉, 다음 태스크가 커널 태스크인 경우 기존 태스크의 active_mm을 사용한다. 그런 후 기존 태스크의 mm 카운터를 1 증가시키고 lazy tlb 모드로 진입한다.
    • arm과 arm64 아키텍처는 lazy_tlb 모드를 사용하지 않는다.
  • 코드 라인 26~27에서 다음 태스크가 유저 태스크인 경우 다음 태스크가 사용하는 가상 공간을 사용하기 위해 mm 스위칭을 한다.
    • mm 스위칭을 위해 관련 CONTEXTIDR 및 TTBR0 레지스터를 새 태스크의 mm을 사용하여 설정한다. 단 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.
  • 코드 라인 29~32에서 이전 태스크의 mm이 없는 경우 즉, 이전 태스크가 커널 태스크인 경우 active_mm에 null을 대입한다. 런큐의 prev_mm에 이전 태스크의 active_mm을 대입한다.
  • 코드 라인 41에서 디버깅을 위해 context 트래킹 정보를 기록한다.
  • 코드 라인 43에서 다음 태스크로 context 스위칭을 수행한다.
  • 코드 라인 46에서 context 스위치 완료 후 할 일을 수행한다

 

다음 그림과 같이 6개의 초기 태스크가 생성되었다고 가정한다.

 

다음 그림과 같이 초기 태스크인 init_task부터 각 커널 태스크들과 유저 태스크들이 스케줄링 되면서 active_mm이 변화하는 모습과 각 별표에서 mm 스위칭이 발생하는 것을 알 수 있다.

  • 참고로  가장 주소 환경은 처음 init_task를 제외하고 항상 유저 태스크인 경우만 mm 스위칭이 발생하는데 이 때 mm을 사용한다.
  • 커널 태스크로 전환된 경우 이전에 사용했던 유저 가상 주소를 active_mm을 통해 전달받아 사용한다.
    • 처음 init_mm 제외

 

Context 스위치 전에 준비할 일과 종료 후 할 일

prepare_task_switch()

kernel/sched/core.c

/**
 * prepare_task_switch - prepare to switch tasks
 * @rq: the runqueue preparing to switch
 * @prev: the current task that is being switched out
 * @next: the task we are going to switch to.
 *
 * This is called with the rq lock held and interrupts off. It must
 * be paired with a subsequent finish_task_switch after the context
 * switch.
 *
 * prepare_task_switch sets up locking and calls architecture specific
 * hooks.
 */
static inline void 
prepare_task_switch(struct rq *rq, struct task_struct *prev,
                    struct task_struct *next)
{
        trace_sched_switch(prev, next);
        sched_info_switch(rq, prev, next);
        perf_event_task_sched_out(prev, next);
        fire_sched_out_preempt_notifiers(prev, next);
        prepare_lock_switch(rq, next);
        prepare_arch_switch(next);
}

다음 태스크로 context 스위치하기 전에 할일을 준비한다.

  • 코드 라인 19에서 디버그용 스케줄 정보를 기록한다.
  • 코드 라인 20에서 디버그용 perf 이벤트에 대한 출력을 한다. (PERF_COUNT_SW_CONTEXT_SWITCHES)
  • 코드 라인 21에서 curr->preempt_notifiers에 등록된 notifier들에 대해 ops->sched_out() 함수를 호출한다.
  • 코드 라인 22에서 다음 태스크가 런큐에서 동작함을 알린다. (next->on_cpu = 1)
  • 코드 라인 23에서 아키텍처에서 지원하는 경우 context 스위치 전에 할 일을 수행하게 한다.
    • arm, arm64 아키텍처는 해당 사항 없다.

finish_task_switch()

kernel/sched/core.c

/**
 * finish_task_switch - clean up after a task-switch
 * @prev: the thread we just switched away from.
 *
 * finish_task_switch must be called after the context switch, paired
 * with a prepare_task_switch call before the context switch.
 * finish_task_switch will reconcile locking set up by prepare_task_switch,
 * and do any other architecture-specific cleanup actions.
 *
 * Note that we may have delayed dropping an mm in context_switch(). If
 * so, we finish that here outside of the runqueue lock. (Doing it
 * with the lock held can cause deadlocks; see schedule() for
 * details.)
 *
 * The context switch have flipped the stack from under us and restored the
 * local variables which were saved when this task called schedule() in the
 * past. prev == current is still correct but we need to recalculate this_rq
 * because prev may have moved to another CPU.
 */
static struct rq *finish_task_switch(struct task_struct *prev)
        __releases(rq->lock)
{
        struct rq *rq = this_rq();
        struct mm_struct *mm = rq->prev_mm;
        long prev_state;

        rq->prev_mm = NULL;

        /*
         * A task struct has one reference for the use as "current".
         * If a task dies, then it sets TASK_DEAD in tsk->state and calls
         * schedule one last time. The schedule call will never return, and
         * the scheduled task must drop that reference.
         * The test for TASK_DEAD must occur while the runqueue locks are
         * still held, otherwise prev could be scheduled on another cpu, die
         * there before we look at prev->state, and then the reference would
         * be dropped twice.
         *              Manfred Spraul <manfred@colorfullife.com>
         */
        prev_state = prev->state;
        vtime_task_switch(prev);
        finish_arch_switch(prev);
        perf_event_task_sched_in(prev, current);
        finish_lock_switch(rq, prev);
        finish_arch_post_lock_switch();

        fire_sched_in_preempt_notifiers(current);
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
                if (prev->sched_class->task_dead)
                        prev->sched_class->task_dead(prev);

                /*
                 * Remove function-return probe instances associated with this
                 * task and put them back on the free list.
                 */
                kprobe_flush_task(prev);
                put_task_struct(prev);
        }

        tick_nohz_task_switch(current);
        return rq;
}

context 스위치 완료 후 할 일을 수행한다. (prepare_task_switch() 함수와 한 쌍을 이룬다.)

  • 코드 라인 41에서 s390 아키텍처에서만 vtime 관련하여 수행한다.
  • 코드 라인 42에서 기존 태스크의 스위칭 완료 시 아키텍처별로 수행할 일을 한다.
  • 코드 라인 43에서 디버깅을 위해 perf event 출력을 한다.
  • 코드 라인 47에서 스케줄 in 되는 경우 현재 태스크의 preempt_notifiers 체인 리스트에 등록된 notifier  함수를 호출한다.
  • 코드 라인 48~49에서 런큐의 prev_mm이 있는 경우 mm을 사용하지 않는다. (참조 카운터가 0이되면 할당 해제한다.)
  • 코드 라인 50~60에서 낮은 확률로 기존 태스크 상태가 TASK_DEAD 인 경우 기존 태스크를 사용하지 않는다. (참조 카운터가 0이되면 할당 해제한다) 만일 기존 태스크의 스케줄러에 (*task_dead)가 준비된 경우 호출한다.
    • dl 스케줄러를 사용하는 경우 task_dead_dl() 함수를 호출하여 total_bw에서 dl_bw를 감소시키고 dl 타이머를 중지시킨다.
  • 코드 라인 62에서 시스템이 nohz full이 지원되어 동작하고 있는 경우 nohz full 상태를 체크하여 필요 시 다시 tick 스케줄링을 재개한다.
/*
 * For v7 SMP cores running a preemptible kernel we may be pre-empted
 * during a TLB maintenance operation, so execute an inner-shareable dsb
 * to ensure that the maintenance completes in case we migrate to another
 * CPU.
 */
#if defined(CONFIG_PREEMPT) && defined(CONFIG_SMP) && defined(CONFIG_CPU_V7)
#define finish_arch_switch(prev)        dsb(ish)
#endif

armv7 아키텍처를 사용한 SMP 시스템이 CONFIG_PREEMPT preemption 모델을 사용하는 경우 inner-share 영역의 지연된 캐시, TLB 및 BP 조작 작업을 완료할 때까지 대기한다.

 

fire_sched_in_preempt_notifiers()

kernel/sched/core.c

static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
{
        struct preempt_notifier *notifier;

        hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
                notifier->ops->sched_in(notifier, raw_smp_processor_id());
}

스케줄 in 되는 경우 현재 태스크의 preempt_notifiers 체인 리스트에 등록된 notifier  함수를 호출한다.

다음 그림은 현재 태스크의 preempt_notifiers 체인리스트에 virt/kvm/kvm_main.c – vcpu_load() 함수가 등록되어 호출되는 것을 보여준다.

 

mmdrop()

include/linux/sched.h

/* mmdrop drops the mm and the page tables */
static inline void mmdrop(struct mm_struct * mm)
{
        if (unlikely(atomic_dec_and_test(&mm->mm_count)))
                __mmdrop(mm);
}

메모리 디스크립터 mm의 참조 카운터를 감소시키고 0인 경우 mm을 할당 해제한다.

 

__mmdrop()

kernel/fork.c

/*
 * Called when the last reference to the mm
 * is dropped: either by a lazy thread or by 
 * mmput. Free the page directory and the mm.
 */     
void __mmdrop(struct mm_struct *mm)
{
        BUG_ON(mm == &init_mm);
        mm_free_pgd(mm);
        destroy_context(mm);
        mmu_notifier_mm_destroy(mm);
        check_mm(mm);
        free_mm(mm);
}
EXPORT_SYMBOL_GPL(__mmdrop);

메모리 디스크립터 mm을 할당 해제한다.

  • 코드 라인 9에서 mm에 연결된 페이지 테이블을 할당 해제한다.
  • 코드 라인 10에서 mm의 context 정보를 해제한다.
    • arm 아키텍처는 아무것도 수행하지 않는다.
  • 코드 라인 11에서 mm->mmu_notifier_mm을 할당 해제한다.
  • 코드 라인 12에서 mm에 문제가 있는지 체크하고 문제가 있는 경우 alert 메시지를 출력한다
  • 코드 라인 13에서 mm을 할당 해제한다.

 

mm_free_pgd()

kernel/fork.c

static inline void mm_free_pgd(struct mm_struct *mm)
{
        pgd_free(mm, mm->pgd); 
}

 

check_mm()

kernel/fork.c

static void check_mm(struct mm_struct *mm)
{       
        int i;
        
        for (i = 0; i < NR_MM_COUNTERS; i++) {
                long x = atomic_long_read(&mm->rss_stat.count[i]);

                if (unlikely(x))
                        printk(KERN_ALERT "BUG: Bad rss-counter state "
                                          "mm:%p idx:%d val:%ld\n", mm, i, x);
        }

        if (atomic_long_read(&mm->nr_ptes))
                pr_alert("BUG: non-zero nr_ptes on freeing mm: %ld\n",
                                atomic_long_read(&mm->nr_ptes));
        if (mm_nr_pmds(mm))
                pr_alert("BUG: non-zero nr_pmds on freeing mm: %ld\n",
                                mm_nr_pmds(mm));

#if defined(CONFIG_TRANSPARENT_HUGEPAGE) && !USE_SPLIT_PMD_PTLOCKS
        VM_BUG_ON_MM(mm->pmd_huge_pte, mm);
#endif 
}

mm에 문제가 있는지 체크하고 문제가 있는 경우 alert 메시지를 출력한다.

  • 코드 라인 5~11에서 3개의 MM 카운터 수만큼 루프를 돌며 rss_stat 카운터 값이 0 보다 큰 경우 alert 메시지를 출력한다.
  • 코드 라인 13~15에서 mm->nr_ptes가 0 보다 큰 경우 alert 메시지를 출력한다.
  • 코드 라인 16~18에서 mm에 pmds가 0 보다 큰 경우 alert 메시지를 출력한다.
  • 코드 라인 20~22에서 mm->pmd_huge_pte 수가 0 보다 큰 경우 emergency 메시지를 덤프한다.

 

include/linux/mm_types.h

enum {
        MM_FILEPAGES,
        MM_ANONPAGES,
        MM_SWAPENTS,
        NR_MM_COUNTERS
};

 

free_mm()

kernel/fork.c

#define free_mm(mm)     (kmem_cache_free(mm_cachep, (mm)))

mm 슬랩 캐시에 메모리 디스크립터 mm을 할당 해제 한다.

 

mm 스위칭

switch_mm()

arch/arm/include/asm/mmu_context.h

/*
 * This is the actual mm switch as far as the scheduler
 * is concerned.  No registers are touched.  We avoid
 * calling the CPU specific function when the mm hasn't
 * actually changed.
 */
static inline void
switch_mm(struct mm_struct *prev, struct mm_struct *next,
          struct task_struct *tsk)
{
#ifdef CONFIG_MMU
        unsigned int cpu = smp_processor_id();

        /*
         * __sync_icache_dcache doesn't broadcast the I-cache invalidation,
         * so check for possible thread migration and invalidate the I-cache
         * if we're new to this CPU.
         */
        if (cache_ops_need_broadcast() &&
            !cpumask_empty(mm_cpumask(next)) &&
            !cpumask_test_cpu(cpu, mm_cpumask(next)))
                __flush_icache_all();

        if (!cpumask_test_and_set_cpu(cpu, mm_cpumask(next)) || prev != next) {
                check_and_switch_context(next, tsk);
                if (cache_is_vivt())
                        cpumask_clear_cpu(cpu, mm_cpumask(prev));
        }
#endif
}

지정한 태스크의 가상 주소로 전환하기 위해 mm 스위치한다.

  • 코드 라인 19~22에서 캐시 작업에 브로드캐스트가 필요한 아키텍처이고 태스크에 대한 cpu 비트맵이 비어 있지 않고 해당 cpu 비트만 클리어 되어 있는 경우 명령 캐시 전체를 flush 한다.
    • arm 아키텍처에서 UP 시스템이나 armv7 이상인 경우 해당 사항 없다.
  • 코드 라인 24~25에서 태스크에 대한 cpu 비트맵이 클리어된 상태이거나 다음 태스크에 사용할 mm이 기존 태스크의 mm과 동일하지 않은 경우 mm 스위칭을 수행한다.
  • 코드 라인 26~27에서 캐시가 vivt 타입인 경우 기존 태스크에 대한 cpu 비트맵에서 현재 cpu 비트를 클리어한다.

 

cache_ops_need_broadcast()

arch/arm/include/asm/smp_plat.h

#if !defined(CONFIG_SMP) || __LINUX_ARM_ARCH__ >= 7
#define cache_ops_need_broadcast()      0
#else
static inline int cache_ops_need_broadcast(void)
{
        if (!is_smp())
                return 0;

        return ((read_cpuid_ext(CPUID_EXT_MMFR3) >> 12) & 0xf) < 1;
}
#endif

캐시 작업에 브로드캐스트가 필요한 아키텍처인지 여부를 알아온다. true(1)=브로드캐스트 필요

  • 다음과 같이 armv6 이하 SMP 아키텍처에서 브로드캐스트가 필요한 SMP 아키텍처가 있다.
  • MMFR3.Maintenance broadcast가  레지스터는 다음과 같다.
    • 0b0000: 캐시, TLB 및 BP 조작 모두 local cpu에만 적용된다.
    • 0b0001: 캐시, BP 조작은 명령에 따라 share cpu들에 적용되지만 TLB는 local cpu에만 적용된다.
    • 0b0010: 캐시, TLB 및 BP 조작 모두 명령에 따라 share cpu들에 적용된다.

 

check_and_switch_context()

arch/arm/include/asm/mmu_context.h

static inline void check_and_switch_context(struct mm_struct *mm,
                                            struct task_struct *tsk)
{
        if (unlikely(mm->context.vmalloc_seq != init_mm.context.vmalloc_seq))
                __check_vmalloc_seq(mm);

        if (irqs_disabled())
                /*
                 * cpu_switch_mm() needs to flush the VIVT caches. To avoid
                 * high interrupt latencies, defer the call and continue
                 * running with the old mm. Since we only support UP systems
                 * on non-ASID CPUs, the old mm will remain valid until the
                 * finish_arch_post_lock_switch() call.
                 */
                mm->context.switch_pending = 1;
        else
                cpu_switch_mm(mm->pgd, mm);
}

mm 스위칭을 위해 관련 CONTEXTIDR 및 TTBR0 레지스터를 새 태스크의 mm을 사용하여 설정한다. 단 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.

  • 코드 라인 4~5에서 init_mm의 vmalloc 정보가 갱신되어 현재 태스크의 vmalloc 시퀀스와 다른 경우 init_mm의 페이지 테이블 중 vmalloc 주소 공간에 해당하는 매핑 테이블 엔트리들만 현재 태스크의 vmalloc 영역을 가리키는 엔트리에 복사한다.
  • 코드 라인 7~15에서 인터럽트 처리 중인 경우 mm 스위칭을 지연시킨다.
  • 코드 라인 16~17에서 mm 스위칭을 위해 관련 CONTEXTIDR 및 TTBR0 레지스터를 새 태스크의 mm을 사용하여 설정한다

 

cpu_switch_mm()

arch/arm/include/asm/proc-fns.h

#define cpu_switch_mm(pgd,mm) cpu_do_switch_mm(virt_to_phys(pgd),mm)

 

cpu_do_switch_mm()

arch/arm/include/asm/proc-fns.h & arch/arm/include/asm/glue-proc.h

#ifdef MULTI_CPU
#define cpu_do_switch_mm                processor.switch_mm
#else
#define cpu_do_switch_mm                __glue(CPU_NAME,_switch_mm)
#endif
  • armV7 아키텍처는 MULTI_CPU를 사용하고 processor.switch_mm 후크는 cpu_v7_switch_mm() 함수를 가리킨다.

 

cpu_v7_switch_mm()

arch/arm/mm/proc-v7-2level.S

/*
 *      cpu_v7_switch_mm(pgd_phys, tsk)
 *
 *      Set the translation table base pointer to be pgd_phys
 *
 *      - pgd_phys - physical address of new TTB
 *
 *      It is assumed that:
 *      - we are not using split page tables
 */
ENTRY(cpu_v7_switch_mm)
#ifdef CONFIG_MMU
        mov     r2, #0
        mmid    r1, r1                          @ get mm->context.id
        ALT_SMP(orr     r0, r0, #TTB_FLAGS_SMP)
        ALT_UP(orr      r0, r0, #TTB_FLAGS_UP)
#ifdef CONFIG_ARM_ERRATA_430973
        mcr     p15, 0, r2, c7, c5, 6           @ flush BTAC/BTB
#endif
#ifdef CONFIG_PID_IN_CONTEXTIDR
        mrc     p15, 0, r2, c13, c0, 1          @ read current context ID
        lsr     r2, r2, #8                      @ extract the PID 
        bfi     r1, r2, #8, #24                 @ insert into new context ID
#endif
#ifdef CONFIG_ARM_ERRATA_754322
        dsb     
#endif
        mcr     p15, 0, r1, c13, c0, 1          @ set context ID
        isb
        mcr     p15, 0, r0, c2, c0, 0           @ set TTB 0
        isb
#endif
        bx      lr
ENDPROC(cpu_v7_switch_mm)

mm 스위칭을 위해 CONTEXTIDR.ASID를 mm->context.id로 갱신하고 TTBR0 레지스터에는 pgd_phys + TTB 플래그를 기록한다.

  • 코드 라인 14에서 mm->context.id 값을 읽어 r1에 대입한다.
  • 코드 라인 15에서 pgd 물리 주소가 담긴 r0에 TTB 플래그를 추가한다.
  • 코드 라인 16~18에서 Cortex-A8 (r1p0..r1p2) 칩의 erratum을 위해 BP(Branch Prediction)를 flush한다.
  • 코드 라인 19~23에서 CONTEXTIDR 레지스터값 >> 8 비트한 값이 PROCID이고 이 값을 r1의 상위 24비트에 대입한다.
    • r1 bits[31:8] <- CONTEXTIDR.PROCID
  • 코드 라인 24~26에서 ARMv7 아키텍처에서 ASID 스위칭을 하는 경우 잘못된 MMU 변환이 가능하여 erratum을 위해 dsb 명령을 수행한다.
  • 코드 라인 27~28에서 CONTEXTIDR에서 ASID 값이 교체된 r1 값을 CONTEXTIDR에 기록하고 isb 명령을 통해 명령 파이프를 비운다.
  • 코드 라인 29~30에서 TTBR0 레지스터에 pgd 주소 및 TTB 플래그가 담긴 r0 레지스터를 기록하고 isb 명령을 통해 명령 파이프를 비운다.

 

arch/arm/mm/proc-v7-2level.S

/* PTWs cacheable, inner WB not shareable, outer WB not shareable */
#define TTB_FLAGS_UP    TTB_IRGN_WB|TTB_RGN_OC_WB
          
/* PTWs cacheable, inner WBWA shareable, outer WBWA not shareable */
#define TTB_FLAGS_SMP   TTB_IRGN_WBWA|TTB_S|TTB_NOS|TTB_RGN_OC_WBWA
  • TTBR0 레지스터에 pgd 물리 주소를 지정할 때 위의 플래그와 같이 지정하여 사용한다.

 

#define TTB_S           (1 << 1)
#define TTB_RGN_NC      (0 << 3)
#define TTB_RGN_OC_WBWA (1 << 3)
#define TTB_RGN_OC_WT   (2 << 3)
#define TTB_RGN_OC_WB   (3 << 3)
#define TTB_NOS         (1 << 5)
#define TTB_IRGN_NC     ((0 << 0) | (0 << 6))
#define TTB_IRGN_WBWA   ((0 << 0) | (1 << 6))
#define TTB_IRGN_WT     ((1 << 0) | (0 << 6))
#define TTB_IRGN_WB     ((1 << 0) | (1 << 6)) 

 

다음 그림은 context 스위칭 시 CONTEXTIDR 레지스터와 TTBR0 레지스터가 변경되는 모습을 보여준다.

 

mmid 매크로

arch/arm/mm/proc-macros.S

/*
 * mmid - get context id from mm pointer (mm->context.id)
 * note, this field is 64bit, so in big-endian the two words are swapped too.
 */
        .macro  mmid, rd, rn
#ifdef __ARMEB__
        ldr     \rd, [\rn, #MM_CONTEXT_ID + 4 ]
#else
        ldr     \rd, [\rn, #MM_CONTEXT_ID]
#endif
        .endm

mm->context.id를 rd에 반환한다. (rn에 mm)

 

mm 스위칭 전 vmalloc 복제

__check_vmalloc_seq()

arch/arm/mm/ioremap.c

void __check_vmalloc_seq(struct mm_struct *mm) 
{
        unsigned int seq;

        do {
                seq = init_mm.context.vmalloc_seq;
                memcpy(pgd_offset(mm, VMALLOC_START),
                       pgd_offset_k(VMALLOC_START),
                       sizeof(pgd_t) * (pgd_index(VMALLOC_END) -
                                        pgd_index(VMALLOC_START)));
                mm->context.vmalloc_seq = seq;
        } while (seq != init_mm.context.vmalloc_seq);
}

init_mm의 vmalloc 정보가 갱신되었기 때문에 다음 태스크로 스위칭 되기 전에 init_mm->pgd의 vmalloc 엔트리들을 mm->pgd로 갱신한다.

  • 코드 라인 5에서 init_mm의 vmalloc 시퀀스 번호를 알아온다.
  • 코드 라인 6~9에서 vmalloc address space에 해당하는 init_mm의 페이지 테이블 엔트리들을 mm의 페이지 테이블로 복사한다.
  • 코드 라인 10~11에서 vmalloc 시퀀스 번호도 갱신한다. 이렇게 갱신하는 동안 또 변경이 일어나면 루프를 돌며 다시 갱신한다.

 

다음 그림은 갱신된 커널의 vmalloc 엔트리들을 내 태스크의 페이지 테이블로 갱신하는 모습을 보여준다.

 

context 스위칭

switch_to()

arch/arm/include/asm/switch_to.h

/*
 * switch_to(prev, next) should switch from task `prev' to `next'
 * `prev' will never be the same as `next'.  schedule() itself
 * contains the memory barrier to tell GCC not to cache `current'.
 */
#define switch_to(prev,next,last)                                       \
do {                                                                    \
        last = __switch_to(prev,task_thread_info(prev), task_thread_info(next));        \
} while (0)

cpu context 스위칭을 통해 다음 스레드로 전환한다.

 

다음 그림과 같이 태스크가 생성되는 경우 할당되는 context 관련된 컴포넌트들을 알아본다.

 

__switch_to()

arch/arm/kernel/entry-armv.S

/*
 * Register switch for ARMv3 and ARMv4 processors
 * r0 = previous task_struct, r1 = previous thread_info, r2 = next thread_info
 * previous and next are guaranteed not to be the same.
 */
ENTRY(__switch_to)
 UNWIND(.fnstart        )
 UNWIND(.cantunwind     )
        add     ip, r1, #TI_CPU_SAVE
 ARM(   stmia   ip!, {r4 - sl, fp, sp, lr} )    @ Store most regs on stack
 THUMB( stmia   ip!, {r4 - sl, fp}         )    @ Store most regs on stack
 THUMB( str     sp, [ip], #4               )
 THUMB( str     lr, [ip], #4               )
        ldr     r4, [r2, #TI_TP_VALUE]
        ldr     r5, [r2, #TI_TP_VALUE + 4]
#ifdef CONFIG_CPU_USE_DOMAINS
        ldr     r6, [r2, #TI_CPU_DOMAIN]
#endif
        switch_tls r1, r4, r5, r3, r7
#if defined(CONFIG_CC_STACKPROTECTOR) && !defined(CONFIG_SMP)
        ldr     r7, [r2, #TI_TASK]
        ldr     r8, =__stack_chk_guard
        ldr     r7, [r7, #TSK_STACK_CANARY]
#endif
#ifdef CONFIG_CPU_USE_DOMAINS
        mcr     p15, 0, r6, c3, c0, 0           @ Set domain register
#endif
        mov     r5, r0
        add     r4, r2, #TI_CPU_SAVE
        ldr     r0, =thread_notify_head
        mov     r1, #THREAD_NOTIFY_SWITCH
        bl      atomic_notifier_call_chain
#if defined(CONFIG_CC_STACKPROTECTOR) && !defined(CONFIG_SMP)
        str     r7, [r8]
#endif
 THUMB( mov     ip, r4                     )
        mov     r0, r5
 ARM(   ldmia   r4, {r4 - sl, fp, sp, pc}  )    @ Load all regs saved previously
 THUMB( ldmia   ip!, {r4 - sl, fp}         )    @ Load all regs saved previously
 THUMB( ldr     sp, [ip], #4               )
 THUMB( ldr     pc, [ip]                   )
 UNWIND(.fnend          )
ENDPROC(__switch_to)

cpu context 스위칭을 통해 다음 스레드로 전환한다.

  • 코드 라인 9~10에서 기존 thread_info->cpu_context에 r4 레지스터 부터 대부분의 레지스터들을 백업한다.
  • 코드 라인 14~18에서 레지스터 r4, r5, r6에 순서대로 thread_info의 tp_value[0], tp_value[1] 및 cpu_domain 값을 가져온다.
  • 코드 라인 19에서 process context 스위칭을 위해 TLS 스위칭을 한다.
  • 코드 라인 20~24에서 SMP가 아닌 시스템에서 CONFIG_CC_STACKPROTECTOR 커널 옵션을 사용하는 경우 다음 thread_info->task->stack_canary 값을 r7 레지스터에 읽어오고 r8 레지스터에는 __stack_chk_guard 주소 값을 읽어온다.
  • 코드 라인 25~27에서 도메인 레지스터에 cpu_domain 값을 설정한다.
  • 코드 라인 28에서 r5 레지스터에 이전 태스크를 가리키는 r0 레지스터를 잠시 백업해둔다.
  • 코드 라인 29에서 r4 레지스터에 다음 thread_info->cpu_context 값을 대입한다.
  • 코드 라인 30~32에서  thread_notify_head 리스트에 등록된 notify 블럭의 모든 함수들을 호출한다. 호출 시 THREAD_NOTIFY_SWITCH 명령과 다음 thread_info 포인터 값을 전달한다.
  • 코드 라인 33~35에서 다음 태스크의 stack_canary 값을 __stack_chk_guard 전역 변수에 저장한다.
  • 코드 라인 37에서 r5에 보관해둔 이전 태스크 포인터 값을 다시 r0에 대입한다.
  • 코드 라인 38에서 다음 thread_info->cpu_context 값을 가리키는 r4를 통해서 r4 레지스터 부터 대부분의 레지스터들을 회복한다.
    • 마지막에 읽은 pc 레지스터로 점프하게 된다.

 

arch/arm/include/asm/tls.h

#define switch_tls      switch_tls_v6k

armv6 및 armv7 아키텍처 이상의 경우 tls 레지스터를 가지고 있고 switch_tls_v68 매크로 함수를 호출한다.

 

switch_tls_v6k 매크로

arch/arm/include/asm/tls.h

.       .macro switch_tls_v6k, base, tp, tpuser, tmp1, tmp2
        mrc     p15, 0, \tmp2, c13, c0, 2       @ get the user r/w register
        mcr     p15, 0, \tp, c13, c0, 3         @ set TLS register
        mcr     p15, 0, \tpuser, c13, c0, 2     @ and the user r/w register
        str     \tmp2, [\base, #TI_TP_VALUE + 4] @ save it
        .endm

process context 스위칭을 위해 TLS 스위칭을 한다.

  • Thread ID 레지스터를 읽어서 이전 thread_info.tp_value[1]에 백업하고 TLS 레지스터에 tp 값과 Thread ID 레지스터에 tpuser 값을 설정한다.
  • 코드 라인 2에서 Thread ID 레지스터 용도의 TPIDRURW(User 읽기/쓰기) 레지스터 값을 tmp2에 대입한다. (tmp2 <- ThreadID)
  • 코드 라인 3에서 TLS 레지스터 용도의 TPIDRURO(User 읽기 전용) 레지스터에 tp 값을 저장한다. (TLS <- tp)
  • 코드 라인 4에서 Thread ID 레지스터 용도의 TPIDRURW(User 읽기/쓰기) 레지스터에 tpuser 값을 저장한다. (ThreadID <- tpuser)
  • 코드 라인 5에서 기존 Thread ID 값을 thread_info->tp_value[1]에 저장한다.

 

다음 그림은 process context 스위칭을 위해 TLS를 스위칭하는 모습을 보여준다.

 

스레드 Notifier

atomic_notifier_call_chain()

kernel/notifier.c

int atomic_notifier_call_chain(struct atomic_notifier_head *nh,
                               unsigned long val, void *v)
{
        return __atomic_notifier_call_chain(nh, val, v, -1, NULL);
}
EXPORT_SYMBOL_GPL(atomic_notifier_call_chain);
NOKPROBE_SYMBOL(atomic_notifier_call_chain);

notify 체인 리스트에 등록된 notify 블럭의 모든 함수들을 호출한다.

/**
 *      __atomic_notifier_call_chain - Call functions in an atomic notifier chain
 *      @nh: Pointer to head of the atomic notifier chain
 *      @val: Value passed unmodified to notifier function
 *      @v: Pointer passed unmodified to notifier function
 *      @nr_to_call: See the comment for notifier_call_chain.
 *      @nr_calls: See the comment for notifier_call_chain.
 *
 *      Calls each function in a notifier chain in turn.  The functions
 *      run in an atomic context, so they must not block.
 *      This routine uses RCU to synchronize with changes to the chain.
 *
 *      If the return value of the notifier can be and'ed
 *      with %NOTIFY_STOP_MASK then atomic_notifier_call_chain()
 *      will return immediately, with the return value of
 *      the notifier function which halted execution.
 *      Otherwise the return value is the return value
 *      of the last notifier function called.
 */
int __atomic_notifier_call_chain(struct atomic_notifier_head *nh,
                                 unsigned long val, void *v,
                                 int nr_to_call, int *nr_calls) 
{
        int ret;

        rcu_read_lock();
        ret = notifier_call_chain(&nh->head, val, v, nr_to_call, nr_calls);
        rcu_read_unlock();
        return ret;
}
EXPORT_SYMBOL_GPL(__atomic_notifier_call_chain);
NOKPROBE_SYMBOL(__atomic_notifier_call_chain);

rcu로 보호받으며 notify 체인 리스트에 등록된 notify 블럭의 모든 함수들을 nr_to_call  수 만큼 호출하고 성공적으로 호출된 횟수를 출력 인수 nr_calls에 저장한다.

  • val 값과 v 포인터 값이 notifier_call 함수에 전달된다.

 

contextidr_notifier_init()

arch/arm/mm/context.c

static int __init contextidr_notifier_init(void)
{
        return thread_register_notifier(&contextidr_notifier_block);
}
arch_initcall(contextidr_notifier_init);

Context 스위치마다 CONTEXTID.ASID 레지스터에 pid 값을 알아와서 기록하게 하도록 notify 블럭을 등록한다.

 

thread_register_notifier()

arch/arm/include/asm/thread_notify.h

static inline int thread_register_notifier(struct notifier_block *n)
{
        extern struct atomic_notifier_head thread_notify_head;
        return atomic_notifier_chain_register(&thread_notify_head, n);
}

스레드 notify 체인 블럭에 notify 블럭을 등록한다.

  • 다음 커널 코드에서 notify 블럭을 등록하여 사용하고 있다.
    • mm/context.c – contextidr_notifier_init() <- THREAD_NOTIFY_SWITCH 명령
    • arch/arm/nwfpe/fpmodule.c – fpe_init() <- THREAD_NOTIFY_FLUSH 명령
    • vfp/vfpmodule.c – vfp_init() <- THREAD_NOTIFY_SWITCH, FLUSH, EXIT, COPY 명령
    • 그 외 xscale 아키텍처 및 thumbee에서도 사용한다.

 

arch/arm/mm/context.c

static struct notifier_block contextidr_notifier_block = {
        .notifier_call = contextidr_notifier,
};

 

contextidr_notifier()

arch/arm/mm/context.c

#ifdef CONFIG_PID_IN_CONTEXTIDR
static int contextidr_notifier(struct notifier_block *unused, unsigned long cmd,
                               void *t)
{
        u32 contextidr;
        pid_t pid;
        struct thread_info *thread = t;

        if (cmd != THREAD_NOTIFY_SWITCH)
                return NOTIFY_DONE;

        pid = task_pid_nr(thread->task) << ASID_BITS;
        asm volatile(
        "       mrc     p15, 0, %0, c13, c0, 1\n"
        "       and     %0, %0, %2\n"
        "       orr     %0, %0, %1\n"
        "       mcr     p15, 0, %0, c13, c0, 1\n"
        : "=r" (contextidr), "+r" (pid)
        : "I" (~ASID_MASK)); 
        isb();

        return NOTIFY_OK;
}
#endif

커널에서 하드웨어 트레이스 툴을 사용할 때 사용되며 CONTEXTID.ASID 레지스터에 pid 값을 알아와서 기록한다.

  • 코드 라인 9~10에서 THREAD_NOTIFY_SWITCH 명령이 아니면 이 루틴과는 해당 사항이 없으므로 NOTIFY_DONE을 반환한다.
  • 코드 라인 12에서 두 번째 인수로 받은 t 값을 사용하여 thread_info->task->pid 값을 읽어온다.
  • 코드 라인 13~19에서 CONTEXTID 레지스터의 ASID 필드(bits[7:0])만 클리어하고 pid 값을 더해 기록한다.

 

/*      
 * These are the reason codes for the thread notifier.
 */
#define THREAD_NOTIFY_FLUSH     0
#define THREAD_NOTIFY_EXIT      1
#define THREAD_NOTIFY_SWITCH    2
#define THREAD_NOTIFY_COPY      3

 

task_pid_nr()

include/linux/sched.h

static inline pid_t task_pid_nr(struct task_struct *tsk)
{
        return tsk->pid;
}

태스크의 pid 값을 반환한다.

 

#ifdef CONFIG_CPU_HAS_ASID
#define ASID_BITS       8
#define ASID_MASK       ((~0ULL) << ASID_BITS)
#define ASID(mm)        ((unsigned int)((mm)->context.id.counter & ~ASID_MASK))
#else   
#define ASID(mm)        (0)
#endif
  • ASID_MASK=0xffff_ff00

 

activate & deactivate 태스크

activate_task()

kernel/sched/core.c

void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_contributes_to_load(p))
                rq->nr_uninterruptible--;

        enqueue_task(rq, p, flags);
}

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 런큐의 nr_uninterrtible 카운터를 감소시키고 태스크를 런큐에 추가한다.

 

task_contributes_to_load()

include/linux/sched.h

#define task_contributes_to_load(task)  \
                                ((task->state & TASK_UNINTERRUPTIBLE) != 0 && \
                                 (task->flags & PF_FROZEN) == 0)

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 true를 반환한다. (active 태스크가 cpu load에 기여한다)

  • 시스템 suspend 시 frozen 플래그가 설정된다.

 

enqueue_task()

kernel/sched/core.c

static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
{
        update_rq_clock(rq);
        sched_info_queued(rq, p);
        p->sched_class->enqueue_task(rq, p, flags);
}

런큐 클럭을 갱신시키고 요청 태스크의 스케줄러에 있는 (*enqueue_task) 후크에 연결된 함수를 호출하여 런큐에 추가한다.

  • 각 스케줄러마다 다음의 함수를 호출한다.
    • stop 스케줄러 – enqueue_task_stop()
    • deadline 스케줄러 – enqueue_task_dl()
    • rt 스케줄러 – enqueue_task_rt()
    • cfs 스케줄러 – enqueue_task_fair()
    • idle 스케줄러 – enqueue_task_idle()

 

deactivate_task()

kernel/sched/core.c

void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_contributes_to_load(p))
                rq->nr_uninterruptible++;

        dequeue_task(rq, p, flags);
}

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 런큐의 nr_uninterrtible 카운터를 증가시킨 후 태스크를 런큐에 내린다.

 

dequeue_task()

kernel/sched/core.c

static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
{
        update_rq_clock(rq);
        sched_info_dequeued(rq, p);
        p->sched_class->dequeue_task(rq, p, flags);
}

런큐 클럭을 갱신시키고 요청 태스크의 스케줄러에 있는 (*dequeue_task) 후크에 연결된 함수를 호출한다.

  • 각 스케줄러마다 다음의 함수를 호출한다.
    • stop 스케줄러 – dequeue_task_stop()
    • deadline 스케줄러 – dequeue_task_dl()
    • rt 스케줄러 – dequeue_task_rt()
    • cfs 스케줄러 – dequeue_task_fair()
    • idle 스케줄러 – dequeue_task_idle()

 

TTWU(Try To Wake-Up) Local

try_to_wake_up_local()

kernel/sched/core.c

/**
 * try_to_wake_up_local - try to wake up a local task with rq lock held
 * @p: the thread to be awakened
 *
 * Put @p on the run-queue if it's not already there. The caller must
 * ensure that this_rq() is locked, @p is bound to this_rq() and not
 * the current task.
 */
static void try_to_wake_up_local(struct task_struct *p)
{
        struct rq *rq = task_rq(p);

        if (WARN_ON_ONCE(rq != this_rq()) ||
            WARN_ON_ONCE(p == current))
                return;

        lockdep_assert_held(&rq->lock);

        if (!raw_spin_trylock(&p->pi_lock)) {
                raw_spin_unlock(&rq->lock);
                raw_spin_lock(&p->pi_lock);
                raw_spin_lock(&rq->lock);
        }

        if (!(p->state & TASK_NORMAL))
                goto out;

        if (!task_on_rq_queued(p))
                ttwu_activate(rq, p, ENQUEUE_WAKEUP);

        ttwu_do_wakeup(rq, p, 0);
        ttwu_stat(p, smp_processor_id(), 0);
out:
        raw_spin_unlock(&p->pi_lock);
}

 

ttwu_do_wakeup()

kernel/sched/core.c

/*
 * Mark the task runnable and perform wakeup-preemption.
 */
static void
ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
        check_preempt_curr(rq, p, wake_flags);
        trace_sched_wakeup(p, true);

        p->state = TASK_RUNNING;
#ifdef CONFIG_SMP
        if (p->sched_class->task_woken)
                p->sched_class->task_woken(rq, p);

        if (rq->idle_stamp) {
                u64 delta = rq_clock(rq) - rq->idle_stamp;
                u64 max = 2*rq->max_idle_balance_cost;

                update_avg(&rq->avg_idle, delta);

                if (rq->avg_idle > max)
                        rq->avg_idle = max;

                rq->idle_stamp = 0;
        }
#endif
}

 

check_preempt_curr()

kernel/sched/core.c

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
        const struct sched_class *class;

        if (p->sched_class == rq->curr->sched_class) {
                rq->curr->sched_class->check_preempt_curr(rq, p, flags);
        } else {
                for_each_class(class) {
                        if (class == rq->curr->sched_class)
                                break;
                        if (class == p->sched_class) {
                                resched_curr(rq);
                                break;
                        }
                }
        }

        /*
         * A queue event has occurred, and we're going to schedule.  In
         * this case, we can save a useless back to back clock update.
         */
        if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr))
                rq_clock_skip_update(rq, true);
}

 

구조체

thread_info 구조체

arch/arm/include/asm/thread_info.h

/*
 * low level task data that entry.S needs immediate access to.
 * __switch_to() assumes cpu_context follows immediately after cpu_domain.
 */
struct thread_info {
        unsigned long           flags;          /* low level flags */
        int                     preempt_count;  /* 0 => preemptable, <0 => bug */
        mm_segment_t            addr_limit;     /* address limit */
        struct task_struct      *task;          /* main task structure */
        struct exec_domain      *exec_domain;   /* execution domain */
        __u32                   cpu;            /* cpu */
        __u32                   cpu_domain;     /* cpu domain */
        struct cpu_context_save cpu_context;    /* cpu context */
        __u32                   syscall;        /* syscall number */
        __u8                    used_cp[16];    /* thread used copro */
        unsigned long           tp_value[2];    /* TLS registers */
#ifdef CONFIG_CRUNCH
        struct crunch_state     crunchstate;
#endif
        union fp_state          fpstate __attribute__((aligned(8)));
        union vfp_state         vfpstate;
#ifdef CONFIG_ARM_THUMBEE
        unsigned long           thumbee_state;  /* ThumbEE Handler Base register */
#endif
};
  • flags
    • 플래그들
  • preempt_count
    • preemption 카운터로 이 값이 0일 경우에만 preemption이 가능하다.
    • 본문 참고
  • addr_limit
    • 접근 제한 주소
  • task
    • 현재 태스크
  • exec_domain
    • 실행 도메인
  • cpu
    • 동작 중인 cpu 번호
  • cpu_domain
    • cpu 도메인
    • DACR 레지스터 참고
    • 0=no access, 1=user, 3=manager
  • cpu_context
    • cpu context 시 사용하는 cpu 레지스터 정보 저장 장소
  • syscall
    • 시스템 콜(swi) 시 사용하는 syscall 번호
  • used_cp[]
    • 코프로세서 인스트럭션 체크 시 사용
  • tp_value[]
    • TLS 주소 저장
  • fpstate
    • undefined 명령 처리 시 사용하는 fp(부동 소숫점 처리기) 상태
    • 이 값을 사용하여 FP 모듈의 USR 시작 주소로 진입할 수 있게한다.
  • vfpstate
    • undefined 명령 처리 시 사용하는 vfp(부동소숫점 연산 처리기) 상태
    • 이 값을 사용하여 VFP 모듈의 USR 시작 주소로 진입할 수 있게한다.

 

cpu_context_save 구조체

arch/arm/include/asm/thread_info.h

struct cpu_context_save {
        __u32   r4;
        __u32   r5;
        __u32   r6;
        __u32   r7;
        __u32   r8;
        __u32   r9;
        __u32   sl;
        __u32   fp;
        __u32   sp;
        __u32   pc;
        __u32   extra[2];               /* Xscale 'acc' register, etc */
};

cpu context 스위치시 레지스터가 저장되는 장소

참고

 

답글 남기기

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