Priority Inversion & Priority Inheritance

Priority Inversion

realtime 스케줄러는 우선 순위에 따라 태스크가 먼저 수행되어야 하는데 lock 리소스를 획득한 후 우선 순위 원칙에 위배

  • 문제점
    • cpu#1의 A 스레드는 cpu#0 C의 작업이 끝날때 까지 lock을 얻지 못해 기다리는데 C 작업 중 B에 의해 선점당하면서 A는 더 오랜 시간을 기다려야 한다.
    • A 스레드가 B 스레드보다 우선 순위가 높은 상황인데도 위와 같은 상황에서 우선 순위가 더 낮은 B 스레드가 먼저 처리되는 불합리한 상황이 벌어진다.
  • 해결 방법
    • 이러한 점을 보강하기 위하여 Priority Inheritance Protocol이 개발되었고, 리눅스 커널은 priority가 중요한 RT 태스크들 사이에서 사용된다.

 

다음 그림과 같이 A의 lock 획득이 느려지는 상황을 보여준다.

 

Priority Inheritance

  • Priority Inversion 상황과 다르게 A 스레드가 lock을 얻다 실패하는 경우 현재 해당 리소스 lock을 얻어 동작하는 스레드 C의 우선 순위를 A 스레드와 같이 높은 우선 순위로 상속시키면서 그 보다 낮은 우선 순위의 B 스레드에게 선점되지 않게 막는다. 결국 A 스레드는 보다 빠르게 공유된 S 자원의 할당을 받아 처리할 수 있다.
  • 리눅스 커널은 RT 태스크들 사이에서 사용되며 RT Mutex API를 통해 구현되었다.

 

다음 그림은 C 스레드가 lock을 잡고 있는 동안 priority가 A 스레드 처럼 잠시 높아져서 lock을 해제할 때까지 preempt 되지 않고 빠르게 처리하여, 결국 A 스레드 역시 빠르게 처리되는 것을 보여준다.

 

참고

Lock Problem(Dead-Lock)

Lock이 의도되지 않은 상태에 빠져 나오지 못하는 상태가 여러 가지 있는데 그 중 대표적인 3가지를 알아본다.

Dead-Lock

  • 두 개의 태스크간에 자원을 하나 씩 소유하고 상대방의 자원에 접근하려 하는 경우 교착 상태에 빠져 나올 수 없는 상태가 된다.

lock_problem1

Circular Lock Dependency

  • 같은 lock을 두 번 사용하는 경우 두 번째 lock 호출 시 무한 대기 상태가 된다.

lock_problem2

Interrupt Safety

  • 루틴에서 같은 lock을 두 번 호출하지 않았는데도 불구하고 인터럽트 루틴에 의해 같은 lock이 호출되어 결국 두 번 사용되어지는 경우가 발생하는 경우에 두 번째 lock 호출에서 무한 대기 상태가 된다.

lock_problem3

  • 인터럽트 루틴에 의해 우선 순위가 더 높은 태스크로 스케쥴 되어 이미 호출된 lock을 또 사용하게 되는 경우에도 같은 상황이 발생한다.

lock_problem4a

참고

 

User stack vs Kernel stack

user task가 생성될때마다 스택이 각각 유저 스택과 커널 스택이 하나씩 만들어진다.

user stack

  • 유저 스택의 크기는 스레드 생성 시 지정될 수 있고, default 크기는 역시 아키텍처마다 다른다. 최대 사이즈 확인 방법은 “ulimit -a”를 사용한다.(32bit ARM은 8MB)
$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 14846
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 14846
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

 

kernel stack

  • task 생성 시 마다 kernel stack이 생성된다.
    • 사이즈는 유저 스택보다 훨씬 적으며 커널 버전 및 커널 옵션에 따라 조금씩 다르며 보통 1 ~ 4 페이지를 사용한다.
    • 예)
      • arm: 2 page (8K)
      • 4K 페이지를 사용하는 arm64: 4 page (16K)
      • 16K 페이지를 사용하는 arm64: 1 page (16K)

 

Exception 처리용 stack

  • arm 아키텍처에서는 각 exception에 대해 하나씩 있는 mini 스택을 사용한다.
    • exception이 발생되어 해당 exception 핸들러에 진입한 경우에는 각 exception에서 사용하는 3 word의 mini 스택을 이용하고 곧바로 svc 모드로 바꾼 후에는 svc용 스택(커널 스택)을 이용해 처리를 계속한다.

 

context switch시 스택 사용

  • user mode에서 task(thread)가 수행되고 있을 때 syscall을 하여 kernel mode로 jump하고 context switching을 하게되는데 이 때 부터는 해당 유저 task(thread)가 소유한 kernel stack을 사용한다.
  • 다시 kernel mode에서 user mode로 context switching을 하여 돌아가게 되면 task(thread)용 user stack을 사용한다.
  • 참고로 arm에서 sp 레지스터는 각 모드에서 각각 운영되며 arm64에서는 exception level별로 각각 운영된다.
    • arm: sp_usr, sp_svc, sp_irq, …
    • arm64: el0_sp, el1_sp, el2_sp

stack2

 

인터럽트 발생 시 스택

  • 유저 모드에서 swi나 인터럽트 등이 발생하는 경우는 조금 전 설명한 것과 같이 해당 태스크가 소유한 커널 스택을 이용한다.
    • arm 커널은 유저 모드에서 irq 모드를 통해 svc 모드로 전환될 때 irq 모드용 12바이트의 미니 스택을 운용하는데 이의 설명은 생략한다
  • 커널 모드에서 인터럽트 등이 발생하는 경우는 다음과 같이 2개로 분리된다.
    • 커널 스레드 동작 중 인터럽트가 발생한 경우
      • arm: 커널 스레드가 소유한 스택을 그대로 사용한다.
      • arm64: 인터럽트 스택을 사용한다.
    • 인터럽트 context 수행 중 더 높은 우선 순위 등의 인터럽트가 nest 된 경우
      • arm: 현재 사용하고 있는 상태의 커널 스택을 사용한다.
      • arm64: 인터럽트 스택을 사용한다.
  • 아키텍처에 따라 hardirq, softirq용 스택을 분리하여 운용하기도 한다.
    • arm의 경우 hardirq는 위에서 설명한 조건에 따라 적절한 커널 스택을 사용하고 softirq는 ksoftirqd가 소유한 커널 스택을 사용한다.
    • arm64의 경우 hardirq는 인터럽트용 스택을 사용하고 softirq는 커널옵션에 따라 ksoftirqd가 소유한 커널 스택을 사용하게 할 수 있다.

 

예) arm 시스템, 어떠한 태스크도 스케줄되지 않은 cpu에서 인터럽트 발생하는 경우?

  • 이미 커널 스레드인 idle 태스크가  스케줄링되어 동작하고 있다. arm의 경우 wfi등이 수행되어 절전 모드로 내부 클럭이 정지된 상태이다.
    • 인터럽트가 발생하는 경우 wfi에 의해 멈춘 cpu가 계속 동작하고 idle 태스크가 소유한 커널 스택을 사용하여 인터럽트 context가 진행된다.
  • idle 태스크는 커널 부트업 시  각 cpu별로 초기화 수행 후 idle 태스크로 이름이 바뀌어 idle 스케줄러에 등록되어 어떠한 태스크도 스케줄되지 않을 때에만 동작하는 특수한 태스크이다.
    • idle 태스크의 pid는 모든 cpu에서 공통으로 0이다.
  • idle 태스크는 부트업시 사용하던 init_task가 나중에 변경된 태스크이므로 인터럽트가 발생하면 레지스터 백업은 이 스택을 사용한다.

참고

lockdep

lockdep

  • 커널이 사용하는 lock(spinlock, mutex, semaphore)을 디버깅하기 위해 사용
  • Lock Problem(Dead-Lock)발생 시 경고 출력을 한다. (dmesg로 볼 수 있다.)
  • ww-mutex를 사용하면 deadlock도 회피할 수 있다.
  • 현재 커널은 userspace에서 사용하는 lock도 디버깅할 수 있다.
  • 커널 빌드 시 락 디버깅 옵션을 enable하여 사용한다.

커널 메뉴 설정 방법

Kernel hacking  --->
	Lock Debugging (spinlocks, mutexes, etc...)  --->
		[*] RT Mutex debugging, deadlock detection
		-*- Spinlock and rw-lock debugging: basic checks
		-*- Mutex debugging: basic checks
		[*] Wait/wound mutex debugging: Slowpath testing
		-*- Lock debugging: detect incorrect freeing of live locks
		[*] Lock debugging: prove locking correctness
		[*] Lock usage statistics
		[*] Lock dependency engine debugging
		[*] Sleep inside atomic section checking
		[*] Locking API boot-time self-tests
		<M> torture tests for locking

/proc 디렉토리에 생성되는 항목들

/proc/lockdep
/proc/lockdep_chains
/proc/lockdep_stat
/proc/locks
/proc/lock_stats

/proc/lockdep

all lock classes:
80a1c55c OPS:      19 FD:   50 BD:    2 +.+...: cgroup_mutex
 -> [80a1c6b0] cgroup_idr_lock
 -> [80a1c5b0] css_set_rwsem
 -> [80a30a74] devcgroup_mutex
 -> [80a1cf3c] freezer_mutex
 -> [80a274ac] kernfs_mutex
(...)

/proc/lockdep_chains

all lock chains:
irq_context: 0
[80a1c55c] cgroup_mutex

irq_context: 0
[80a16a3c] resource_lock
(...)

/proc/lockdep_stat

lock-classes:                         1212 [max: 8191]
 direct dependencies:                  4230 [max: 32768]
 indirect dependencies:               13035
 all direct dependencies:             63105
 dependency chains:                    6166 [max: 65536]
 dependency chain hlocks:             18187 [max: 327680]
 in-hardirq chains:                      29
 in-softirq chains:                     261
 in-process chains:                    4580
 stack-trace entries:                 60133 [max: 524288]
 combined max dependencies:        36006660
 hardirq-safe locks:                     28
 hardirq-unsafe locks:                  471
 softirq-safe locks:                     91
 softirq-unsafe locks:                  415
 irq-safe locks:                         97
 irq-unsafe locks:                      471
 hardirq-read-safe locks:                 3
 hardirq-read-unsafe locks:              80
 softirq-read-safe locks:                 9
 softirq-read-unsafe locks:              77
 irq-read-safe locks:                    10
 irq-read-unsafe locks:                  80
 uncategorized locks:                   130
 unused locks:                            1
 max locking depth:                      15
 max bfs queue depth:                   159
 chain lookup misses:                  6175
 chain lookup hits:                10136672
 cyclic checks:                        4705
 find-mask forwards checks:            1593
 find-mask backwards checks:          31551
 hardirq on events:                 8784803
 hardirq off events:                8784808
 redundant hardirq ons:              356471
 redundant hardirq offs:            6574108
 softirq on events:                  116537
 softirq off events:                 116565
 redundant softirq ons:                   0
 redundant softirq offs:                  0
 debug_locks:                             1

/proc/locks

1: FLOCK  ADVISORY  WRITE 2057 00:0e:7200 0 EOF
2: FLOCK  ADVISORY  WRITE 2246 00:0e:7097 0 EOF

/proc/lock_stat

lock_stat version 0.4
-----------------------------------------------------------------------------------------------------
               class name    con-bounces    contentions   waittime-min   waittime-max waittime-total 
-----------------------------------------------------------------------------------------------------

 &mapping->i_mmap_rwsem-W:          1630           2186           0.99       64477.45      988876.13 
 &mapping->i_mmap_rwsem-R:             0              0           0.00           0.00           0.00 
 ------------------------
   &mapping->i_mmap_rwsem           1017         [<801343b0>] unlink_file_vma+0x34/0x50
   &mapping->i_mmap_rwsem            319         [<8013448c>] vma_link+0x44/0xbc
   &mapping->i_mmap_rwsem            327         [<80024244>] copy_process.part.44+0x1440/0x17e4
   &mapping->i_mmap_rwsem            523         [<801347cc>] vma_adjust+0x2c8/0x604
 ------------------------
   &mapping->i_mmap_rwsem            274         [<8013448c>] vma_link+0x44/0xbc
   &mapping->i_mmap_rwsem            320         [<80024244>] copy_process.part.44+0x1440/0x17e4
   &mapping->i_mmap_rwsem            603         [<801347cc>] vma_adjust+0x2c8/0x604
   &mapping->i_mmap_rwsem            989         [<801343b0>] unlink_file_vma+0x34/0x50

......................................................................................................
---------------------------------------------------------------------------------------------------------
 waittime-avg    acq-bounces   acquisitions   holdtime-min   holdtime-max holdtime-total   holdtime-avg
---------------------------------------------------------------------------------------------------------

       452.37          37732         174127           2.19       66922.50     2247589.89          12.91
         0.00             12            727          10.57        3269.64       36358.60          50.01










  
.........................................................................................................

참고자료:

set_task_stack_end_magic()

<kernel v5.10>

set_task_stack_end_magic()

  • start_kernel()이 커널 초기화 과정을 수행하는 동안 사용할 최초 커널 스택의 마지막에 magic value를 기록한다. 이후에 만들어지는 커널 스택은 메모리를 할당 받아 생성되어 사용되며 태스크가 종료되는 경우 메모리를 회수한다.
  • 기록된 magic value(STACK_END_MAGIC: 0x57AC6E9D)를 통해 kernel stack overflow를 감지하는데 사용된다.
void set_task_stack_end_magic(struct task_struct *tsk)
{
        unsigned long *stackend;

        stackend = end_of_stack(tsk);
        *stackend = STACK_END_MAGIC;    /* for overflow detection */
}
  • STACK_END_MAGIC=0x57AC_6E9D

 

end_of_stack()

CONFIG_THREAD_INFO_IN_TASK 사용 케이스 (ARM64 must)

include/linux/sched/task_stack.h

static inline unsigned long *end_of_stack(const struct task_struct *task)
{
        return task->stack;
}

태스크에 해당하는 stack의 끝 주소를 반환한다. 스택의 마지막 위치에는 스택 마지막을 표시하는 매직 값이 위치한다.

 

ARM32 에서 CONFIG_THREAD_INFO_IN_TASK를 사용하지 않는 케이스

include/linux/sched/task_stack.h

/*
 * Return the address of the last usable long on the stack.
 *
 * When the stack grows down, this is just above the thread
 * info struct. Going any lower will corrupt the threadinfo.
 *
 * When the stack grows up, this is the highest address.
 * Beyond that position, we corrupt data on the next page.
 */
static inline unsigned long *end_of_stack(struct task_struct *p)
{
#ifdef CONFIG_STACK_GROWSUP
        return (unsigned long *)((unsigned long)task_thread_info(p) + THREAD_SIZE) - 1; 
#else
        return (unsigned long *)(task_thread_info(p) + 1);
#endif
}

요청한 태스크에 해당하는 스택의 마지막 unsigned long 값을 반환한다. 스택의 마지막 위치에는 스택 마지막을 표시하는 매직 값이 위치한다.

  •  CONFIG_STACK_GROWSUP
    • 스택이 상향으로 push되는 경우에 사용
    • arm, arm64 default: 하향으로 스택이 push된다.
  • task가 가지고 있는 kernel stack의 마지막 주소를 리턴한다.
    • task는 kernel stack과 user stack를 각각 하나씩 가진다.
    • kernel stack은 kernel이 자신의 코드를 수행할 때 사용하는 코드이다.
    • 예를 들어, user application이 요청한 시스템 콜을 수행할 때 kernel stack이 사용될 수 있다.
    • 참고: kernel stack

 


kernel stack 구조

  • 아키텍처마다 커널 스택 크기가 다르다.
    •  arm32
      • 8K (2 페이지)
      • 1개 페이지로 돌아가려고 노력하고 있으므로, 나중에 변경될 수도 있다.
    • arm64
      • 16K (default)
      • 64K (1페이지=64K 이면서 vmap stack 사용시)

 

아래 그림은 커널 스택에서의 스택 보호용 매직 번호가 있는 위치를 보여준다.

  • arm64의 경우 thread_info가 스택에서 제거되어 task_struct의  안으로 들어가므로 매직 번호는 가장 하단에 위치하게 된다.

thread_union

include/linux/sched.h

union thread_union {
#ifndef CONFIG_ARCH_TASK_STRUCT_ON_STACK
        struct task_struct task;
#endif
#ifndef CONFIG_THREAD_INFO_IN_TASK
        struct thread_info thread_info;
#endif
        unsigned long stack[THREAD_SIZE/sizeof(long)];
};
  • CONFIG_ARCH_TASK_STRUCT_ON_STACK
    • ia64 아키텍처만 이 커널 옵션을 사용한다.
  • CONFIG_THREAD_INFO_IN_TASK
    • 커널 v4.9-rc1에 추가된 기능으로 이 커널 옵션을 사용하는 경우 보안을 위해 스택의 아래에 존재하던 thread_info를 제거하여 task_struct의 첫 엔트리로 옮겼다. 이렇게 첫 부분에 옮겨 놓았으므로 task_struct 구조체도 thread_union의 thread_info를 통해 접근이 가능하다.
    • arm은 사용하지 않는 옵션이지만 arm64의 경우는 적용되었다.
    • 참고: sched/core: Allow putting thread_info into task_struct

 

task_struct 구조체 (처음 부분만)

include/linux/sched.h

struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
        /*
         * For reasons of header soup (see current_thread_info()), this
         * must be the first element of task_struct.
         */
        struct thread_info              thread_info;
#endif
        volatile long                   state;

        /*
         * This begins the randomizable portion of task_struct. Only
         * scheduling-critical items should be added above here.
         */
        randomized_struct_fields_start

        void                            *stack;
        ...
}

CONFIG_THREAD_INFO_IN_TASK 커널 옵션을 사용한 경우 가장 처음에 스레드 정보가 위치함을 알 수 있다.

 

thread_info – ARM

arch/arm/include/asm/thread_info.h

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 */
        __u32                   cpu;            /* cpu */
        __u32                   cpu_domain;     /* cpu domain */
#ifdef CONFIG_STACKPROTECTOR_PER_TASK
        unsigned long           stack_canary;
#endif
        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
};

 

thread_info – ARM64

arch/arm64/include/asm/thread_info.h

struct thread_info {
        unsigned long           flags;          /* low level flags */
        mm_segment_t            addr_limit;     /* address limit */
#ifdef CONFIG_ARM64_SW_TTBR0_PAN
        u64                     ttbr0;          /* saved TTBR0_EL1 */
#endif
        union {
                u64             preempt_count;  /* 0 => preemptible, <0 => bug */
                struct {
#ifdef CONFIG_CPU_BIG_ENDIAN
                        u32     need_resched;
                        u32     count;
#else
                        u32     count;
                        u32     need_resched;
#endif
                } preempt;
        };
};

 

task_thread_info()

include/linux/sched.h

#ifdef CONFIG_THREAD_INFO_IN_TASK
static inline struct thread_info *task_thread_info(struct task_struct *task)
{
        return &task->thread_info;
}
#elif !defined(__HAVE_THREAD_FUNCTIONS)
# define task_thread_info(task) ((struct thread_info *)(task)->stack)
#endif

요청한 태스크에 해당하는 스레드 정보(thread_info 구조체)를 반환한다.

  • CONFIG_THREAD_INFO_IN_TASK 커널 옵션을 사용한 여부와 관련하여
    • 사용한 경우 task 디스크립터에 위치한 스레드 정보를 가져온다.
    • 사용하지 않은 경우 스택에서 스레드 정보를 가져온다.

 

thread_union

include/linux/sched.h

union thread_union {
#ifndef CONFIG_ARCH_TASK_STRUCT_ON_STACK
        struct task_struct task;
#endif
#ifndef CONFIG_THREAD_INFO_IN_TASK
        struct thread_info thread_info;
#endif
        unsigned long stack[THREAD_SIZE/sizeof(long)];
};

스택과 같은 주소를 공유하는 구조체들이다.

 

다음 그림은 CONFIG_THREAD_INFO_IN_TASK 커널 옵션 사용에 따른 변화를 보여준다.

  • ARM64의 경우 이 커널 옵션은 항상 선택되어 thread_info가 스택에서 분리하여 태스크 디스크립터에 포함된다.

 

다음 그림은 CONFIG_ARCH_TASK_STRUCT_ON_STACK 커널 옵션 사용에 따른 변화를 보여준다.

  • 이 커널 옵션을 사용하는 경우 vmlinux.lds.h가 지정하는 섹션을 통해 들어가다보면 init_task가 init_stack 내에 포함되는 것을 알 수 있다.

 

INIT_TASK_DATA()

include/asm-generic/vmlinux.lds.h

#define INIT_TASK_DATA(align)                                           \
        . = ALIGN(align);                                               \
        __start_init_task = .;                                          \
        init_thread_union = .;                                          \
        init_stack = .;                                                 \
        KEEP(*(.data..init_task))                                       \
        KEEP(*(.data..init_thread_info))                                \
        . = __start_init_task + THREAD_SIZE;                            \
        __end_init_task = .;

init_stack을 만들때 __start_init_task, init_thread_union 심볼등도 같은 주소로 생성한다.

  • init_task의 경우 CONFIG_ARCH_TASK_STRUCT_ON_STACK  커널 옵션을 사용하는 경우 아래의 __init_task_data 섹션 지시 매크로를 통해 .data..init_task 섹션에 포함시킨다.
  • init_thread_info의 경우 CONFIG_THREAD_INFO_IN_TASK 커널 옵션을 사용지 않는 경우 .data..init_task 섹션에 포함시킨다. (ARM64의 경우 이 옵션을 사용하지 않으므로 해당 섹션 위치를 사용하지 않는다.)

 

__init_task_data

include/linux/init_task.h

/* Attach to the init_task data structure for proper alignment */
#ifdef CONFIG_ARCH_TASK_STRUCT_ON_STACK
#define __init_task_data __section(".data..init_task")
#else
#define __init_task_data /**/
#endif

init_task 생성 시 이 섹션 지시 매크로를 통해 .data..init_task 섹션에 포함시키도록 한다.

 

get_current()

arch/arm64/include/asm/current.h

/*
 * We don't use read_sysreg() as we want the compiler to cache the value where
 * possible.
 */
static __always_inline struct task_struct *get_current(void)
{
        unsigned long sp_el0;

        asm ("mrs %0, sp_el0" : "=r" (sp_el0));

        return (struct task_struct *)sp_el0;
}

현재 태스크를 반환한다.

  • 커널(el1)에서는 사용하지 않는 sp_el0 레지스터를 사용하여 태스크를 가리키도록 하여 사용하고 있다.

 

참고