run queue와 thread_resched

QUESTION

run queue와 thread_resched 단계에서 실제로 바뀌는 상태는 무엇인가?

STRUCTURE

객체와 주소가 놓이는 구조

CALL PATH

실행 흐름

STATE LEDGER

단계별 입력과 출력

각 단계의 입력과 처리 후 바뀌는 상태를 정리한 표다. 사용 중인 소스 버전에서 다른 필드를 변경한다면 그에 맞춰 표도 수정한다.

분석 범위의 전제와 비교해, 다음 단계에 잘못된 입력을 넘긴 부분부터 조사한다.

VISUAL WALKTHROUGH

주소와 객체의 이동을 그림으로 읽기

아래 그림은 주소, 객체를 사용하는 기간, 제어권을 넘기는 시점을 중심으로 정리했다. 실제 주소와 크기는 사용 중인 보드의 bdinfo, 맵 파일과 링커 심벌로 확인한다.

UPSTREAM SOURCE

원본 코드

아래 코드는 LK upstream 1eb9917의 kernel/thread.c에서 46-134줄을 그대로 가져온 것이다. 설명을 위해 실제 코드를 가짜 의사 코드로 바꾸지 않았다.

46
47/* global thread list */
48static struct list_node thread_list;
49
50/* master thread spinlock */
51spin_lock_t thread_lock = SPIN_LOCK_INITIAL_VALUE;
52
53/* the run queue */
54static struct list_node run_queue[NUM_PRIORITIES];
55static uint32_t run_queue_bitmap;
56
57/* make sure the bitmap is large enough to cover our number of priorities */
58STATIC_ASSERT(NUM_PRIORITIES <= sizeof(run_queue_bitmap) * 8);
59
60/* the idle thread(s) (statically allocated) */
61#if WITH_SMP
62static thread_t _idle_threads[SMP_MAX_CPUS];
63#define idle_thread(cpu) (&_idle_threads[cpu])
64#else
65static thread_t _idle_thread;
66#define idle_thread(cpu) (&_idle_thread)
67#endif
68
69/* local routines */
70static void thread_resched(void);
71static void idle_thread_routine(void) __NO_RETURN;
72
73#if PLATFORM_HAS_DYNAMIC_TIMER
74/* preemption timer */
75static timer_t preempt_timer[SMP_MAX_CPUS];
76#endif
77
78/* run queue manipulation */
79static void insert_in_run_queue_head(thread_t *t) {
80    DEBUG_ASSERT(t->magic == THREAD_MAGIC);
81    DEBUG_ASSERT(t->state == THREAD_READY);
82    DEBUG_ASSERT(!list_in_list(&t->queue_node));
83    DEBUG_ASSERT(arch_ints_disabled());
84    DEBUG_ASSERT(spin_lock_held(&thread_lock));
85
86    list_add_head(&run_queue[t->priority], &t->queue_node);
87    run_queue_bitmap |= (1<<t->priority);
88}
89
90static void insert_in_run_queue_tail(thread_t *t) {
91    DEBUG_ASSERT(t->magic == THREAD_MAGIC);
92    DEBUG_ASSERT(t->state == THREAD_READY);
93    DEBUG_ASSERT(!list_in_list(&t->queue_node));
94    DEBUG_ASSERT(arch_ints_disabled());
95    DEBUG_ASSERT(spin_lock_held(&thread_lock));
96
97    list_add_tail(&run_queue[t->priority], &t->queue_node);
98    run_queue_bitmap |= (1<<t->priority);
99}
100
101static void wakeup_cpu_for_thread(thread_t *t)
102{
103    /* Wake up the core to which this thread is pinned
104     * or wake up all if thread is unpinned */
105    int pinned_cpu = thread_pinned_cpu(t);
106    if (pinned_cpu < 0)
107        mp_reschedule(MP_CPU_ALL_BUT_LOCAL, 0);
108    else
109        mp_reschedule(1U << pinned_cpu, 0);
110}
111
112static void init_thread_struct(thread_t *t, const char *name) {
113    memset(t, 0, sizeof(thread_t));
114    t->magic = THREAD_MAGIC;
115    thread_set_pinned_cpu(t, -1);
116    strlcpy(t->name, name, sizeof(t->name));
117}
118
119/**
120 * @brief  Create a new thread
121 *
122 * This function creates a new thread.  The thread is initially suspended, so you
123 * need to call thread_resume() to execute it.
124 *
125 * @param  name        Name of thread
126 * @param  entry       Entry point of thread
127 * @param  arg         Arbitrary argument passed to entry()
128 * @param  priority    Execution priority for the thread.
129 * @param  stack_size  Stack size for the thread.
130 *
131 * Thread priority is an integer from 0 (lowest) to 31 (highest).  Some standard
132 * prioritys are defined in <kernel/thread.h>:
133 *
134 *  HIGHEST_PRIORITY

READING CONTRACT

발췌 범위와 읽기 기준

원문 46-134줄에는 앞뒤 문맥이 포함됩니다. 기준 구문 void thread_resched(void)은 L70에 있습니다. 발췌 첫 줄을 함수 정의의 시작으로 해석하지 않습니다.

호출 이유가 yield인지 block인지 preemption인지에 따라 현재 thread를 다시 enqueue하는 조건이 달라진다. interrupt disable 구간도 함께 본다.

RELATED SOURCE

함께 읽어야 하는 원본 코드

첫 코드 조각만으로 동작이 완성되지 않는 경우 호출 매크로, 객체 정의와 실제 실행 목록을 같은 페이지에 묶었다. 각 조각은 같은 기준 commit에서 가져왔다.

421    thread_resched();
422
423    panic("somehow fell through thread_exit()\n");
424}
425
426static void idle_thread_routine(void) {
427    for (;;)
428        arch_idle();
429}
430
431static thread_t *get_top_thread(int cpu) {
432    thread_t *newthread;
433    uint32_t local_run_queue_bitmap = run_queue_bitmap;
434
435    while (local_run_queue_bitmap) {
436        /* find the first (remaining) queue with a thread in it */
437        uint next_queue = sizeof(run_queue_bitmap) * 8 - 1 - __builtin_clz(local_run_queue_bitmap);
438
439        list_for_every_entry(&run_queue[next_queue], newthread, thread_t, queue_node) {
440#if WITH_SMP
441            if (newthread->pinned_cpu < 0 || newthread->pinned_cpu == cpu)
442#endif
443            {
444                list_delete(&newthread->queue_node);
445
446                if (list_is_empty(&run_queue[next_queue]))
447                    run_queue_bitmap &= ~(1<<next_queue);
448
449                return newthread;
450            }
451        }
452
453        local_run_queue_bitmap &= ~(1<<next_queue);
454    }
455    /* no threads to run, select the idle thread for this cpu */
456    return idle_thread(cpu);
457}
458
459/**
460 * @brief  Cause another thread to be executed.
461 *
462 * Internal reschedule routine. The current thread needs to already be in whatever
463 * state and queues it needs to be in. This routine simply picks the next thread and
464 * switches to it.
465 *
466 * This is probably not the function you're looking for. See
467 * thread_yield() instead.
468 */
469void thread_resched(void) {
470    thread_t *oldthread;
471    thread_t *newthread;
472
473    thread_t *current_thread = get_current_thread();
474    uint cpu = arch_curr_cpu_num();
475
476    DEBUG_ASSERT(arch_ints_disabled());
477    DEBUG_ASSERT(spin_lock_held(&thread_lock));
478    DEBUG_ASSERT(current_thread->state != THREAD_RUNNING);
479

DETAILS

내부 동작을 더 깊게 읽기

IMPLEMENTATION NOTES

구현을 읽을 때 놓치기 쉬운 부분

OBJECT LIFETIME

객체와 수명

FAILURE PATH

실패 지점과 증상

로그가 끊긴 함수뿐 아니라 그 함수에 주소, 크기, 플래그를 전달한 앞 단계도 조사한다. 오류 처리 후 등록된 객체나 하드웨어 설정이 그대로 남아 있는지도 확인한다.

EVIDENCE

소스 밖에서 확인할 증거

소스에서 파악한 동작을 실제 빌드 결과와 대상 보드의 로그로 확인한다. 아래 명령의 보드 이름과 툴체인 접두사는 사용 중인 빌드 환경에 맞게 바꾼다.

LAB

직접 확인할 실험

1. 01
   context switch마다 old/new priority 기록

   scheduler lock 진입 전후에 priority queues의 주소·크기·반환값과 timestamp를 함께 남긴다.

2. 02
   run queue bitmap과 list 일관성 검사

   run queue pick 진입 전후에 current_thread의 주소·크기·반환값과 timestamp를 함께 남긴다.

3. 03
   timer tick과 explicit yield의 call stack 비교

   arch context switch 진입 전후에 saved registers의 주소·크기·반환값과 timestamp를 함께 남긴다.

PRIMARY REFERENCES

원문과 다음 글