Linux內核搶占

主要介紹內核搶占的相關概念和具體實現，以及搶占對內核調度和內核競態和同步的一些影響。
(所用內核版本3.19.3)

---

1. 基本概念

用戶搶占和內核搶占
用戶搶占發生點
當從系統調用或者中斷上下文返回用戶態的時候，會檢查need_resched標志，如果被設置則會重新選擇用戶態task執行 內核搶占發生點
當從中斷上下文返回內核態的時候，檢查need_resched標識以及__preemp_count計數，如果標識被設置，並且可搶占，則會觸發調度程序preempt_schedule_irq() 內核代碼由於阻塞等原因直接或間接顯示調用schedule，比如preemp_disable時可能會觸發preempt_schedule() 本質上內核態中的task是共享一個內核地址空間，在同一個core上，從中斷返回的task很可能執行和被搶占的task相同的代碼，並且兩者同時等待各自的資源釋放，也可能兩者修改同一共享變量，所以會造成死鎖或者競態等；而對於用戶態搶占來說，由於每個用戶態進程都有獨立的地址空間，所以在從內核代碼(系統調用或者中斷)返回用戶態時，由於是不同地址空間的鎖或者共享變量，所以不會出現不同地址空間之間的死鎖或者競態，也就沒必要檢查__preempt_count，是安全的。__preempt_count主要負責內核搶占計數。

---

2. 內核搶占的實現

percpu變量__preempt_count

搶占計數8位, PREEMPT_MASK                     => 0x000000ff
軟中斷計數8位, SOFTIRQ_MASK                   => 0x0000ff00
硬中斷計數4位, HARDIRQ_MASK                   => 0x000f0000
不可屏蔽中斷1位, NMI_MASK                     => 0x00100000
PREEMPTIVE_ACTIVE(標識內核搶占觸發的schedule)  => 0x00200000
調度標識1位, PREEMPT_NEED_RESCHED             => 0x80000000

__preempt_count的作用

搶占計數 判斷當前所在上下文 重新調度標識

thread_info的flags

thread_info的flags中有一個是TIF_NEED_RESCHED，在系統調用返回，中斷返回，以及preempt_disable的時候會檢查是否設置，如果設置並且搶占計數為0(可搶占)，則會觸發重新調度schedule()或者preempt_schedule()或者preempt_schedule_irq()。通常在scheduler_tick中會檢查是否設置此標識(每個HZ觸發一次)，然後在下一次中斷返回時檢查，如果設置將觸發重新調度，而在schedule()中會清除此標識。

// kernel/sched/core.c
// 設置thread_info flags和__preempt_count的need_resched標識
void resched_curr(struct rq *rq)
{
    /*省略*/
    if (cpu == smp_processor_id()) {
    // 設置thread_info的need_resched標識 
        set_tsk_need_resched(curr);
    // 設置搶占計數__preempt_count裡的need_resched標識
        set_preempt_need_resched();
        return;
    }
    /*省略*/
}

//在schedule()中清除thread_info和__preempt_count中的need_resched標識
static void __sched __schedule(void)
{
    /*省略*/
need_resched:
    // 關搶占讀取percpu變量中當前cpu id，運行隊列
    preempt_disable();
    cpu = smp_processor_id(); 
    rq = cpu_rq(cpu);
    rcu_note_context_switch();
    prev = rq->curr;
    /*省略*/
    //關閉本地中斷，關閉搶占，獲取rq自旋鎖
    raw_spin_lock_irq(&rq->lock);
    switch_count = &prev->nivcsw;
  // PREEMPT_ACTIVE 0x00200000
  // preempt_count = __preempt_count & (~(0x80000000))
  // 如果進程沒有處於running的狀態或者設置了PREEMPT_ACTIVE標識
  //(即本次schedule是由於內核搶占導致)，則不會將當前進程移出隊列
  // 此處PREEMPT_ACTIVE的標識是由中斷返回內核空間時調用
  // preempt_schdule_irq或者內核空間調用preempt_schedule
  // 而設置的，表明是由於內核搶占導致的schedule，此時不會將當前
  // 進程從運行隊列取出，因為有可能其再也無法重新運行。
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
    // 如果有信號不移出run_queue
        if (unlikely(signal_pending_state(prev->state, prev))) {
            prev->state = TASK_RUNNING;
        } else { // 否則移除隊列讓其睡眠
            deactivate_task(rq, prev, DEQUEUE_SLEEP);
            prev->on_rq = 0;
            // 是否喚醒一個工作隊列內核線程
            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;
    }
    /*省略*/
    next = pick_next_task(rq, prev);
    // 清除之前task的need_resched標識
    clear_tsk_need_resched(prev);
    // 清除搶占計數的need_resched標識
    clear_preempt_need_resched();
    rq->skip_clock_update = 0;
    // 不是當前進程，切換上下文
    if (likely(prev != next)) {
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;
        rq = context_switch(rq, prev, next);
        cpu = cpu_of(rq);
    } else
        raw_spin_unlock_irq(&rq->lock);
    post_schedule(rq);
    // 重新開搶占
    sched_preempt_enable_no_resched();
    // 再次檢查need_resched
    if (need_resched())
        goto need_resched;
}

__preempt_count的相關操作

/////// need_resched標識相關 ///////

// PREEMPT_NEED_RESCHED位如果是0表示需要調度
#define PREEMPT_NEED_RESCHED 0x80000000 

static __always_inline void set_preempt_need_resched(void)
{
  // __preempt_count最高位清零表示need_resched
  raw_cpu_and_4(__preempt_count, ~PREEMPT_NEED_RESCHED);
}

static __always_inline void clear_preempt_need_resched(void)
{
  // __preempt_count最高位置位
  raw_cpu_or_4(__preempt_count, PREEMPT_NEED_RESCHED);
}

static __always_inline bool test_preempt_need_resched(void)
{
  return !(raw_cpu_read_4(__preempt_count) & PREEMPT_NEED_RESCHED);
}

// 是否需要重新調度，兩個條件：1. 搶占計數為0；2. 最高位清零
static __always_inline bool should_resched(void)
{
  return unlikely(!raw_cpu_read_4(__preempt_count));
}

////////// 搶占計數相關 ////////

#define PREEMPT_ENABLED (0 + PREEMPT_NEED_RESCHED)
#define PREEMPT_DISABLE (1 + PREEMPT_ENABLED)
// 讀取__preempt_count，忽略need_resched標識位
static __always_inline int preempt_count(void)
{
  return raw_cpu_read_4(__preempt_count) & ~PREEMPT_NEED_RESCHED;
}
static __always_inline void __preempt_count_add(int val)
{
  raw_cpu_add_4(__preempt_count, val);
}
static __always_inline void __preempt_count_sub(int val)
{
  raw_cpu_add_4(__preempt_count, -val);
}
// 搶占計數加1關閉搶占
#define preempt_disable() \
do { \
  preempt_count_inc(); \
  barrier(); \
} while (0)
// 重新開啟搶占，並測試是否需要重新調度
#define preempt_enable() \
do { \
  barrier(); \
  if (unlikely(preempt_count_dec_and_test())) \
    __preempt_schedule(); \
} while (0)

// 搶占並重新調度
// 這裡設置PREEMPT_ACTIVE會對schdule()中的行為有影響
asmlinkage __visible void __sched notrace preempt_schedule(void)
{
  // 如果搶占計數不為0或者沒有開中斷，則不調度
  if (likely(!preemptible()))
    return;
  do {
    __preempt_count_add(PREEMPT_ACTIVE);
    __schedule();
    __preempt_count_sub(PREEMPT_ACTIVE);
    barrier();
  } while (need_resched());
}
// 檢查thread_info flags
static __always_inline bool need_resched(void)
{
  return unlikely(tif_need_resched());
}

////// 中斷相關 ////////

// 硬件中斷計數
#define hardirq_count() (preempt_count() & HARDIRQ_MASK)
// 軟中斷計數
#define softirq_count() (preempt_count() & SOFTIRQ_MASK)
// 中斷計數
#define irq_count() (preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK \
         | NMI_MASK))
// 是否處於外部中斷上下文
#define in_irq()    (hardirq_count())
// 是否處於軟中斷上下文
#define in_softirq()    (softirq_count())
// 是否處於中斷上下文
#define in_interrupt()    (irq_count())
#define in_serving_softirq()  (softirq_count() & SOFTIRQ_OFFSET)

// 是否處於不可屏蔽中斷環境
#define in_nmi()  (preempt_count() & NMI_MASK)

// 是否可搶占 : 搶占計數為0並且沒有處在關閉搶占的環境中
# define preemptible()  (preempt_count() == 0 && !irqs_disabled())

---

3. 系統調用和中斷處理流程的實現以及搶占的影響

(arch/x86/kernel/entry_64.S)

系統調用入口基本流程

保存當前rsp, 並指向內核棧，保存寄存器狀態 用中斷號調用系統調用函數表中對應的處理函數 返回時檢查thread_info的flags，處理信號以及need_resched
如果沒信號和need_resched，直接恢復寄存器返回用戶空間 如果有信號處理信號，並再次檢查 如果有need_resched，重新調度，返回再次檢查

中斷入口基本流程

保存寄存器狀態 call do_IRQ 中斷返回，恢復棧，檢查是中斷了內核上下文還是用戶上下文
如果是用戶上下文，檢查thread_info flags是否需要處理信號和need_resched，如果需要，則處理信號和need_resched，再次檢查; 否則，直接中斷返回用戶空間 如果是內核上下文，檢查是否需要need_resched，如果需要，檢查__preempt_count是否為0(能否搶占)，如果為0，則call preempt_schedule_irq重新調度

// 系統調用的處理邏輯 

ENTRY(system_call)
  /* ... 省略 ... */
  // 保存當前棧頂指針到percpu變量
  movq  %rsp,PER_CPU_VAR(old_rsp)
  // 將內核棧底指針賦於rsp，即移到內核棧
  movq  PER_CPU_VAR(kernel_stack),%rsp
  /* ... 省略 ... */
system_call_fastpath:
#if __SYSCALL_MASK == ~0
  cmpq $__NR_syscall_max,%rax
#else
  andl $__SYSCALL_MASK,%eax
  cmpl $__NR_syscall_max,%eax
#endif
  ja ret_from_sys_call  /* and return regs->ax */
  movq %r10,%rcx 
  // 系統調用
  call *sys_call_table(,%rax,8)  # XXX:  rip relative
  movq %rax,RAX-ARGOFFSET(%rsp)

ret_from_sys_call:
  movl $_TIF_ALLWORK_MASK,%edi
  /* edi: flagmask */

// 返回時需要檢查thread_info的flags
sysret_check:  
  LOCKDEP_SYS_EXIT
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  movl TI_flags+THREAD_INFO(%rsp,RIP-ARGOFFSET),%edx
  andl %edi,%edx
  jnz  sysret_careful  // 如果有thread_info flags需要處理，比如need_resched
  //// 直接返回
  CFI_REMEMBER_STATE
  /*
   * sysretq will re-enable interrupts:
   */
  TRACE_IRQS_ON
  movq RIP-ARGOFFSET(%rsp),%rcx
  CFI_REGISTER  rip,rcx
  RESTORE_ARGS 1,-ARG_SKIP,0
  /*CFI_REGISTER  rflags,r11*/
  // 恢復之前保存percpu變量中的棧頂地址(rsp)
  movq  PER_CPU_VAR(old_rsp), %rsp
  // 返回用戶空間
  USERGS_SYSRET64

  CFI_RESTORE_STATE

  //// 如果thread_info的標識被設置了，則需要處理後返回
  /* Handle reschedules */
sysret_careful:
  bt $TIF_NEED_RESCHED,%edx  // 檢查是否需要重新調度
  jnc sysret_signal // 有信號
  // 沒有信號則處理need_resched
  TRACE_IRQS_ON
  ENABLE_INTERRUPTS(CLBR_NONE)
  pushq_cfi %rdi
  SCHEDULE_USER  // 調用schedule()，返回用戶態不需要檢查__preempt_count
  popq_cfi %rdi
  jmp sysret_check  // 再一次檢查

  // 如果有信號發生，則需要處理信號
sysret_signal:
  TRACE_IRQS_ON
  ENABLE_INTERRUPTS(CLBR_NONE)

  FIXUP_TOP_OF_STACK %r11, -ARGOFFSET
  // 如果有信號，無條件跳轉
  jmp int_check_syscall_exit_work

  /* ... 省略 ... */
GLOBAL(int_ret_from_sys_call)
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  movl $_TIF_ALLWORK_MASK,%edi
  /* edi: mask to check */
GLOBAL(int_with_check)
  LOCKDEP_SYS_EXIT_IRQ
  GET_THREAD_INFO(%rcx)
  movl TI_flags(%rcx),%edx
  andl %edi,%edx
  jnz   int_careful
  andl    $~TS_COMPAT,TI_status(%rcx)
  jmp   retint_swapgs

  /* Either reschedule or signal or syscall exit tracking needed. */
  /* First do a reschedule test. */
  /* edx: work, edi: workmask */
int_careful:
  bt $TIF_NEED_RESCHED,%edx
  jnc  int_very_careful  // 如果不只need_resched，跳轉
  TRACE_IRQS_ON
  ENABLE_INTERRUPTS(CLBR_NONE)
  pushq_cfi %rdi
  SCHEDULE_USER  // 調度schedule
  popq_cfi %rdi
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  jmp int_with_check  // 再次去檢查

  /* handle signals and tracing -- both require a full stack frame */
int_very_careful:
  TRACE_IRQS_ON
  ENABLE_INTERRUPTS(CLBR_NONE)
int_check_syscall_exit_work:
  SAVE_REST
  /* Check for syscall exit trace */
  testl $_TIF_WORK_SYSCALL_EXIT,%edx
  jz int_signal
  pushq_cfi %rdi
  leaq 8(%rsp),%rdi # &ptregs -> arg1
  call syscall_trace_leave
  popq_cfi %rdi
  andl $~(_TIF_WORK_SYSCALL_EXIT|_TIF_SYSCALL_EMU),%edi
  jmp int_restore_rest

int_signal:
  testl $_TIF_DO_NOTIFY_MASK,%edx
  jz 1f
  movq %rsp,%rdi    # &ptregs -> arg1
  xorl %esi,%esi    # oldset -> arg2
  call do_notify_resume
1:  movl $_TIF_WORK_MASK,%edi
int_restore_rest:
  RESTORE_REST
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  jmp int_with_check  // 再次檢查thread_info flags
  CFI_ENDPROC
END(system_call)

// 中斷入口基本流程

// 調用do_IRQ的函數wrapper
  .macro interrupt func
  subq $ORIG_RAX-RBP, %rsp
  CFI_ADJUST_CFA_OFFSET ORIG_RAX-RBP
  SAVE_ARGS_IRQ 　// 進入中斷處理上下文時保存寄存器
  call \func
  /*... 省略 ...*/

common_interrupt:
  /*... 省略 ...*/
  interrupt do_IRQ  // 調用c函數do_IRQ實際處理中斷

ret_from_intr: // 中斷返回
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  decl PER_CPU_VAR(irq_count) 　// 減少irq計數

  /* Restore saved previous stack */
  // 恢復之前的棧
  popq %rsi
  CFI_DEF_CFA rsi,SS+8-RBP  /* reg/off reset after def_cfa_expr */
  leaq ARGOFFSET-RBP(%rsi), %rsp
  CFI_DEF_CFA_REGISTER  rsp
  CFI_ADJUST_CFA_OFFSET RBP-ARGOFFSET

exit_intr:
  GET_THREAD_INFO(%rcx)
  testl $3,CS-ARGOFFSET(%rsp)  //　檢查是否中斷了內核
  je retint_kernel  // 從中斷返回內核空間

  /* Interrupt came from user space */
  /*
   * Has a correct top of stack, but a partial stack frame
   * %rcx: thread info. Interrupts off.
   */
  // 用戶空間被中斷，返回用戶空間
retint_with_reschedule:
  movl $_TIF_WORK_MASK,%edi
retint_check:
  LOCKDEP_SYS_EXIT_IRQ
  movl TI_flags(%rcx),%edx
  andl %edi,%edx
  CFI_REMEMBER_STATE
  jnz  retint_careful // 需要處理need_resched

retint_swapgs:    /* return to user-space */
  /*
   * The iretq could re-enable interrupts:
   */
  DISABLE_INTERRUPTS(CLBR_ANY)
  TRACE_IRQS_IRETQ
  SWAPGS
  jmp restore_args

retint_restore_args:  /* return to kernel space */
  DISABLE_INTERRUPTS(CLBR_ANY)
  /*
   * The iretq could re-enable interrupts:
   */
  TRACE_IRQS_IRETQ
restore_args:
  RESTORE_ARGS 1,8,1

irq_return:
  INTERRUPT_RETURN    // native_irq進入

ENTRY(native_iret)
  /*... 省略 ...*/
  /* edi: workmask, edx: work */
retint_careful:
  CFI_RESTORE_STATE
  bt    $TIF_NEED_RESCHED,%edx
  jnc   retint_signal  // 需要處理信號
  TRACE_IRQS_ON
  ENABLE_INTERRUPTS(CLBR_NONE)
  pushq_cfi %rdi
  SCHEDULE_USER  // 返回用戶空間之前調度schedule
  popq_cfi %rdi
  GET_THREAD_INFO(%rcx)
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  jmp retint_check  // 再次檢查thread_info flags

retint_signal:
  testl $_TIF_DO_NOTIFY_MASK,%edx
  jz    retint_swapgs
  TRACE_IRQS_ON
  ENABLE_INTERRUPTS(CLBR_NONE)
  SAVE_REST
  movq $-1,ORIG_RAX(%rsp)
  xorl %esi,%esi    # oldset
  movq %rsp,%rdi    # &pt_regs
  call do_notify_resume
  RESTORE_REST
  DISABLE_INTERRUPTS(CLBR_NONE)
  TRACE_IRQS_OFF
  GET_THREAD_INFO(%rcx)
  jmp retint_with_reschedule  // 處理完信號，再次跳轉處理need_resched

//// 注意，如果內核配置支持搶占，則返回內核時使用這個retint_kernel
#ifdef CONFIG_PREEMPT
  /* Returning to kernel space. Check if we need preemption */
  /* rcx:  threadinfo. interrupts off. */
ENTRY(retint_kernel)
  // 檢查__preempt_count是否為0 
  cmpl $0,PER_CPU_VAR(__preempt_count)  
  jnz  retint_restore_args // 不為0，則禁止搶占
  bt   $9,EFLAGS-ARGOFFSET(%rsp)  /* interrupts off? */
  jnc  retint_restore_args
  call preempt_schedule_irq  // 可以搶占內核
  jmp exit_intr  // 再次檢查
#endif
  CFI_ENDPROC
END(common_interrupt)

---

4. 搶占與SMP並發安全

中斷嵌套可能導致死鎖和競態，一般中斷上下文會關閉本地中斷 軟中斷 一個核上的task訪問percpu變量時可能由於內核搶占導致重新調度到另一個核上繼續訪問另一個核上同名percpu變量，從而可能發生死鎖和競態，所以訪問percpu或者共享變量時需要禁止搶占 自旋鎖需要同時關閉本地中斷和內核搶占 …

---

5. 幾個問題作為回顧

什麼時候可搶占? 什麼時候需要搶占重新調度? 自旋鎖為什麼需要同時關閉中斷和搶占？ 為什麼中斷上下文不能睡眠?關閉搶占後能否睡眠? 為什麼percpu變量的訪問需要禁止搶占? …