월: 2015 11월

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










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

참고자료:

• Runtime locking correctness validator | kernel.org
• How to use lockdep feature in linux kernel for deadlock detection | stackoverflow.com
• Userspace Lockdep | LWN.net
• [Linux] lockdep: 런타임 락 의존성 검사 | F/OSS study

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

/*
 * 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
}

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

 

kernel stack 구조

• 아키텍처마다 커널 스택 크기가 다르다. (라즈베리파이2: 8KB)
• 커널 버전마다 커졌다 작아졌다 하지만 최근엔 커널 스택 다이어트로 줄여나가는 중(8K → 4K)

thread_union

union thread_union {
    struct thread_info thread_info;
    unsigned long stack[THREAD_SIZE/sizeof(long)];
};

thread_info

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 */
    union fp_state      fpstate __attribute__((aligned(8)));
    union vfp_state     vfpstate;
};

task_thread_info()

#define task_thread_info(task)  ((struct thread_info *)(task)->stack)

참고

• User stack vs Kernel stack | 문c
• Kernel Small Stacks | elinux.org
• 커널 최초의 스택은 어떻게 설정하나요?  | 박문식

__init

• __section(.init.text) __cold notrace
  • __section(S) __attribute__ ((__section__(#S)))
• init.text 섹션에 해당 코드를 배치한다.

__cold

• __attribute__((__cold__))
• 호출될 가능성이 희박한 함수를 뜻함.
• 속도보다 사이즈에 더 최적화를 수행한다.
• unlikely()의 사용을 줄일 수 있게 된다. unlikely() 함수들은 old compiler 호환성을 위해 그냥같이  사용한다.
• text 섹션의 한 쪽에 __cold 펑션들을 모아두는 지역성(locality)도 있다. 당연히 이로 인한 cache 효율성도 좋아진다.

notrace

• __attribute__((no_instrument_function))
• 컴파일러에서 -finstrument-functions 컴파일 옵션을 사용할 때에도 해당 함수에 대한 profiling을 비활성한다.
• 참고:
  • Trace and profile function calls with GCC
  • 함수 호출 시각화 하기 | JaPa2
  • Profiling | 문c

__weak

• __attribute__((weak))
• 해당 심볼을 weak symbol로 만든다.
• 링커가 링크를 수행 시 다른곳에 같은 이름으로 만든 strong symbol이 존재하면 weak symbol 대신 strong symbol을 사용한다.
• 참고: GCC Weak Function Attributes

__attribute_const__

• __attribute__((__const__))
• 전달 받은 인수외에 global 변수에 접근할 수 없다.
• side effect가 생기지 않는다.
• 참고: Implications of pure and constant functions | LWN.net

__pure

•  __attribute__((pure)
• 전달 받은 인수외에 global 변수로의 access는 읽기만 가능한다.
• side effect가 생기지 않는다.

 

__read_mostly

• __attribute__((__section__(“.data.read_mostly”)))
• 읽기 위주의 데이터들만을 위한 섹션으로 캐시 라인 바운싱을 회피하기 위한 솔루션
  • SMP 머신에서 cache eviction이 최소화될 수 있는 데이터들끼리 모여있도록 함으로 성능향상을 목표로 하였다.
  • 캐시 라인 바운싱 참고: Exclusive loads and store | 문c
• 참고: Short subjects: kerneloops, read-mostly, and port 80 | LWN.net
• .data.read_mostly 섹션은 RO_DATA_SECTION 다음에 위치한 RW_DATA_SECTION 에 정의되어 있다.

include/asm-generic/vmlinux.lds.h

/*
 * Helper macros to support writing architecture specific
 * linker scripts.
 *
 * A minimal linker scripts has following content:
 * [This is a sample, architectures may have special requiriements]
 *
 * OUTPUT_FORMAT(...)
 * OUTPUT_ARCH(...)
 * ENTRY(...)
 * SECTIONS
 * {
 *      . = START;
 *      __init_begin = .;
 *      HEAD_TEXT_SECTION
 *      INIT_TEXT_SECTION(PAGE_SIZE)
 *      INIT_DATA_SECTION(...)
 *      PERCPU_SECTION(CACHELINE_SIZE)
 *      __init_end = .;
 *
 *      _stext = .;
 *      TEXT_SECTION = 0
 *      _etext = .;
 *
 *      _sdata = .;
 *      RO_DATA_SECTION(PAGE_SIZE)
 *      RW_DATA_SECTION(...)
 *      _edata = .;
 *
 *      EXCEPTION_TABLE(...)
 *      NOTES
 *
 *      BSS_SECTION(0, 0, 0)
 *      _end = .;
 *
 *      STABS_DEBUG
 *      DWARF_DEBUG
 *
 *      DISCARDS                // must be the last
 * }
 *
 * [__init_begin, __init_end] is the init section that may be freed after init
 *      // __init_begin and __init_end should be page aligned, so that we can
 *      // free the whole .init memory
 * [_stext, _etext] is the text section
 * [_sdata, _edata] is the data section
 *
 * Some of the included output section have their own set of constants.
 * Examples are: [__initramfs_start, __initramfs_end] for initramfs and
 *               [__nosave_begin, __nosave_end] for the nosave data
 */

 

/*
 * Writeable data.
 * All sections are combined in a single .data section.
 * The sections following CONSTRUCTORS are arranged so their
 * typical alignment matches.
 * A cacheline is typical/always less than a PAGE_SIZE so
 * the sections that has this restriction (or similar)
 * is located before the ones requiring PAGE_SIZE alignment.
 * NOSAVE_DATA starts and ends with a PAGE_SIZE alignment which
 * matches the requirement of PAGE_ALIGNED_DATA.
 *
 * use 0 as page_align if page_aligned data is not used */
#define RW_DATA_SECTION(cacheline, pagealigned, inittask)               \
        . = ALIGN(PAGE_SIZE);                                           \
        .data : AT(ADDR(.data) - LOAD_OFFSET) {                         \
                INIT_TASK_DATA(inittask)                                \
                NOSAVE_DATA                                             \
                PAGE_ALIGNED_DATA(pagealigned)                          \
                CACHELINE_ALIGNED_DATA(cacheline)                       \
                READ_MOSTLY_DATA(cacheline)                             \
                DATA_DATA                                               \
                CONSTRUCTORS                                            \
        }

 

#define READ_MOSTLY_DATA(align)                                         \
        . = ALIGN(align);                                               \
        *(.data..read_mostly)                                           \
        . = ALIGN(align);

 

__used

• __attribute__((used))
• 해당 객체 또는 함수가 참조되지 않아도 사용하는 것처럼 컴파일러로 하여금 삭제되지 않도록 한다.

__visible

• __attribute__((externally_visible))
• LTO(Link Time Optimization) 기능을 사용하는 경우 caller(호출측)와 callee(피호출측)의 관계에서 링커가 callee가 한 번만 사용된다고 판단되는 경우 caller에 callee를 inline화 하여 집어 넣는다.
• externally_visible 속성을 사용하는 경우 LTO 옵션을 사용하여 링크를 하는 경우에도 하나의 완전한 함수나 객체로 외부에 보여질 수 있도록 심볼화하여 해당 함수나 객체가 inline화 되지 않도록 막는다.
• -flto 또는 -whole-program을 사용하여 LTO 기능을 동작시킨다.
• 참고: Enable link-time optimization (after switching to avr-gcc 4.5 or greater) 

 

asmlinkage

• 어셈블리 코드에서 C 함수를 호출할 때 함수 인자의 전달을 레지스터가 아닌 스택을 이용하도록 해주는 속성지정 매크로이다.
• extern “C”로 정의되어 있다.
• 참고: [Linux] asmlinkage – F/OSS

 

참고

• Declaring Attributes of Functions | gcc.gnu.org
• Options That Control Optimization | gcc.gnu.org

lockdep_init()

• lockdep
  • lock dependency의 약자로 커널이 lock을 모니터링하고 디버깅하기 위한 것으로 dead-lock 검출도 한다.

void lockdep_init(void)
{
        int i;

        /*   
         * Some architectures have their own start_kernel()
         * code which calls lockdep_init(), while we also
         * call lockdep_init() from the start_kernel() itself,
         * and we want to initialize the hashes only once:
         */

        if (lockdep_initialized)
                return;

        for (i = 0; i < CLASSHASH_SIZE; i++) 
                INIT_LIST_HEAD(classhash_table + i);

        for (i = 0; i < CHAINHASH_SIZE; i++) 
                INIT_LIST_HEAD(chainhash_table + i);

        lockdep_initialized = 1;
}

• if (lockdep_initialized)
  • lockdep_initialized는 lockdep_init() 함수가 이미 초기화되었음을 의미한다. 따라서 lockdep_initialized가 true(1)일 경우에는 초기화 코드를 수행하지 않는다.
•  INIT_LIST_HEAD(classhash_table + i);
  • lockdep에 사용될 class마다 hash table을 만든다.
  • lockdep에 사용되는 class는 4096개(CLASSHASH_SIZE)이다.
  • classhash_table을 CLASSHASH_SIZE(4096)개 만큼 초기화한다.
• INIT_LIST_HEAD(chainhash_table + i);
  • chainhash_table을 CHAINHASH_SIZE(32768)개 만큼 초기화한다.

 

classhash_table & chainhash_table

/*
 * The lockdep classes are in a hash-table as well, for fast lookup:
 */
static struct list_head classhash_table[CLASSHASH_SIZE];

/*
 * We put the lock dependency chains into a hash-table as well, to cache
 * their existence:
 */
static struct list_head chainhash_table[CHAINHASH_SIZE];

 

list_head의 구조

struct list_head {
    struct list_head *next, *prev;
};

 

INIT_LIST_HEAD()

static inline void INIT_LIST_HEAD(struct list_head *list)
{
        list->next = list;
        list->prev = list;
}

 

참고

• Lockdep | 문c