2013년 9월 14일 토요일

[Linux Kernel] 21주차(2013.09.14)

Linux Kernel 21주차 

일시 : 2013.09.14 (21주차)
모임명 : NAVER개발자커뮤니티지원_IAMROOT.ORG_10차ARM-C
장소 : 토즈 강남 타워점
장소지원: NAVER 개발자 커뮤니티 지원 프로그램
참여인원: 

스터디 진도 :

1. page_address_init()


1) _cacheline_aligned_in_smp가 뭔가요?

static struct page_address_slot {
        struct list_head lh;                    /* List of page_address_maps */ 
        spinlock_t lock;                        /* Protect this bucket's list */
} ____cacheline_aligned_in_smp page_address_htable[1<<PA_HASH_ORDER];
cache를 64byte align 시키는 attribute입니다.
#ifndef ____cacheline_aligned
#define ____cacheline_aligned __attribute__((__aligned__(SMP_CACHE_BYTES)))
#endif

2) 다음 code에서 왜 return을 할까요? 아무의미 없어 보입니다.

#define spin_lock_init(_lock)                           \
do {                                                    \
        spinlock_check(_lock);                          \
        raw_spin_lock_init(&(_lock)->rlock);            \
} while (0)
</code>
<code c>
static inline raw_spinlock_t *spinlock_check(spinlock_t *lock)
{               
        return &lock->rlock;
}
개발자가 실수하였을 때를 대비하여 warning을 출력함 실수라 함은 Linux 3.2.0에서 spin_lock 인터페이스가 변경 되었고, 그에따라 아래와 같은 warning 발생
spl/include/sys/rwlock.h:55:9: warning: passing argument 1 of ‘spinlock_check’ from incompatible pointer type [enabled by default] include/linux/spinlock.h:272:31: note: expected ‘struct spinlock_t *’ but argument is of type ‘struct raw_spinlock_t *’
Ref. Linux 3.2 spinlock compatibility

3) raw_spin_lock_init() 함수를 보면 구조체가 정의되지 않습니다. 이런경우 어떻게 될까요?

# define raw_spin_lock_init(lock)                               \
do {                                                            \
        static struct lock_class_key __key;     /* struct lock_class_key { }; */        \
                                                                \
        __raw_spin_lock_init((lock), #lock, &__key);            \
} while (0)
다음과 같은 의견이 있었고, 토론을 하였습니다.
1) 컴파일러가 최적화 하면서 해당 구문을 삭제할 것이다. 2) 구조체 member를 전부 0으로 초기화 할 것이다. (member의 size를 포함) 3) 구조체의 주소값만 가지고 있고, member는 초기화 되지 않는다.
결론은 3)의 "구조체의 주소값만 가지고 있다"가 정답입니다.
최적화 얘기가 나와서 덧붙이자면 보통 delay code를 작성할 때, 다음과 같은 code를 작성하고는 하는데
for (int i=0 ; i<LIMIT ; i++) ;
최적화를 고려하면 굉장히 위험한 code입니다. 컴파일러에서 그냥 날려버릴 수 있습니다. 따라서 위의 code를 사용하고 싶다면, volatile을 사용하면 됩니다.

4) 컴파일러 최적화 얘기가 나와서 질문합니다. 보통 O옵션을 주면 default가 몇인가요?

-O하면 보통 -O2라고 보시면 됩니다. 참고로 리눅스 커널은 -O2로 빌드합니다. 그럼 O옵션에 대해 정리해 봅시다. '-O' 또는 '-O1'의 경우, 만들어지는 오브젝트, 또는 실행 파일을 가능한 작게 하면서, 컴파일 시간이 오래걸리지 않는 범위에서 최적화를 수행합니다. '-O2'의 경우, 만들어지는 코드가 가능한 빠르게 수행되도록 하지만, 코드의 크기가 너무 커지지 않도록 하는 범위에서 최적화를 수행합니다. '-Os'의 경우, '-O2'에서 제공하는 모든 최적화 기능을 다 쓰지만, 코드의 크기를 증가시키는 최적화 기능은 빼고 나서 최적화를 수행합니다. '-O3'의 경우, 코드의 크기는 전혀 신경 쓰지 않고, 오직 빠른 코드를 만들어 내기 위해 최적화를 수행합니다. 그러나, 꼭 생각해 두어야 할 점은, '-O3'로 만들어낸 코드가 반드시 '-O2'를 써서 만들어낸 코드보다 빠르다는 보장은 없다는 것입니다. 왜냐하면, 보통 CPU가 기계어를 수행할 때, 일정한 분량만큼 먼저 CPU 내부의 cache(캐시)에 불러와서 수행하는데, '-O3'를 써서 만든 코드는 대개 크기가 커서, 이 cache에 들어갈 수 있는 명령의 양이 상대적으로 적어지기 때문에, 오히려 느려질 가능성도 있습니다.
아래표는 각 O에 대한 최적화 옵션 목록입니다.

Included in Level
Optimization-O1-O2-Os-O3
defer-popOOOO
thread-jumpsOOOO
branch-probabilitiesOOOO
cprop-registersOOOO
guess-branch-probabilityOOOO
omit-frame-pointerOOOO
merge-constantsOOOO
loop-optimizeOOOO
if-conversionOOOO
if-conversion2OOOO
align-loopsXOXO
align-jumpsXOXO
align-labelsXOXO
align-functionsXOXO
crossjumpingXOOO
prefetch-loop-array??X?
optimize-sibling-callsXOOO
cse-follow-jumpsXOOO
cse-skip-blocksXOOO
gcseXOOO
gcse-lmXOOO
gcse-smXOOO
gcse-lasXOOO
expensive-optimizationsXOOO
strength-reduceXOOO
rerun-cse-after-loopXOOO
rerun-loop-optXOOO
caller-savesXOOO
force-memXOOO
peephole2XOOO
regmoveXOOO
strict-aliasingXOOO
delete-null-pointer-checksXOOO
reorder-blocksXOOO
reorder-functionsXOOO
unit-at-a-timeXO?O
schedule-insnsXOOO
schedule-insns2XXXO
schedule-interblockXO?O
sched-specXO?O
inline-functionsXXXO
rename-registersXXXO
webXXXO
unswitch-loopsXX?O
Ref. GCC Optimization Options

5) owner_cpu에 -1을 넣은 이유는 무엇일까요?

void __raw_spin_lock_init(raw_spinlock_t *lock, const char *name,
                          struct lock_class_key *key)
{   
        lock->raw_lock = (arch_spinlock_t)__ARCH_SPIN_LOCK_UNLOCKED;// = (arch_spinlock_t){ { 0 } }
        lock->magic = SPINLOCK_MAGIC;//0xdead4ead
        lock->owner = SPINLOCK_OWNER_INIT; // ((void *)-1L) = 0xffffffff
        lock->owner_cpu = -1;
}
owner_cpu는 양수로 증가할 테니, 음수를 넣어두는 것 같습니다. 그리고 보통 리눅스에서 초기값을 선언할때, 음수를 넣어둡니다.

2. pr_notice()

1) printk의 각 인자가 무엇을 뜻하는 것일까요?

#define pr_notice(fmt, ...) \
        printk(KERN_NOTICE pr_fmt(fmt), ##__VA_ARGS__)
1) pr_fmt(fmt)는 각 device별로 다르게 출력하는 용도입니다. pr은 previous의 의미입니다. 2) ...은 가변인자를 뜻합니다. printf에서 %d, %f를 계속 받을 수 있는 것도 ...로 받기 때문입니다. 3) 전처리기의 '#', '##' 사용 코드로 한눈에 파악 하시기 바랍니다.
테스트코드
  1 #include <stdio.h>
  2
  3 #define DEFINE_USE_2SHARP( TYPE, A, B, C )      TYPE A##B##C
  4 #define T1_PRINTF( comment, fmt, ... )  printf( #comment fmt, __VA_ARGS__ )
  5 #define T2_PRINTF( comment, fmt, ... )  printf( #comment fmt, ##__VA_ARGS__ )
  6
  7 int main( int argc, char *argv[] )
  8 {
  9     DEFINE_USE_2SHARP( int, test, _is, _good );
 10
 11     T1_PRINTF( T1_PRINTF:, "머여?\n" );
 12     T1_PRINTF( T1_PRINTF:, "뭐긴 머여 %s여\n", "테스트" );
 13
 14     T2_PRINTF( T2_PRINTF:, "머여?\n" );
 15     T2_PRINTF( T2_PRINTF:, "뭐긴 머여 %s여\n", "테스트" );
 16
 17
 18     return 0;
 19 }
위코드는 컴파일 하면 에러가 납니다. 여기서는 VA_ARGS 앞에 '##'의 유무에 따라 코드가 어떻게 치환되는지 보기위해 '-E' 옵션을 사용하여 전처리기 적용 완료 코드를 보실수 있습니다.
gcc -E va_args_test.c
결과코드
.
.
.
849
850 # 2 "va_args_test.c" 2
851
852
853
854
855
856 int main( int argc, char *argv[] )
857 {
858     int test_is_good;
859
860     printf( "T1_PRINTF:" "머여?\n", );
861     printf( "T1_PRINTF:" "뭐긴 머여 %s여\n", "테스트" );
862
863     printf( "T2_PRINTF:" "머여?\n" );
864     printf( "T2_PRINTF:" "뭐긴 머여 %s여\n", "테스트" );
865
866
867     return 0;
868 }
'#'의 용도는 코드 그대로 '해당 인자를 문자열로 바꾸어 준다' 정도로 아시면 될것 같습니다.
'##'의 용도는 두가지 정도 인 것 같은데요. 첫째, 해당 인자를 붙여서 써준다. 이건 걍 테스트코드 9줄 -> 결과코드 858줄 을 보시면 알 것 같습니다. 둘째, 가변인자 사용시 가변인자가 없을경우 ','를 제거하기 위해서 테스트코드 11줄 -> 결과코드 860줄, 테스트코드 14줄 -> 결과코드 863줄로 각각 치환됩니다.
여기서 결과코드 860줄 끝에는 그대로 ','가 남아 있고, 결과코드 863줄 끝에는 ','가 없어지는 것을 알 수 있습니다. 사실 두번째 사용법에서 왜 그렇게 되는지는 명확하지 않지만, 걍 저는 아~ 그런갑다 하고 넘어가겠습니다.ㅎㅎ

2) printk를 분석하지는 않겠지만, 조금만 더 들어가봅시다. KERN_NOTICE를 따라왔더니 아스키 헤더가 보이네요. 이건 무엇일까요?

#define KERN_SOH        "\001"          /* ASCII Start Of Header */
#define KERN_SOH_ASCII  '\001'

#define KERN_EMERG      KERN_SOH "0"    /* system is unusable */
#define KERN_ALERT      KERN_SOH "1"    /* action must be taken immediately */
#define KERN_CRIT       KERN_SOH "2"    /* critical conditions */
#define KERN_ERR        KERN_SOH "3"    /* error conditions */
#define KERN_WARNING    KERN_SOH "4"    /* warning conditions */
#define KERN_NOTICE     KERN_SOH "5"    /* normal but significant condition */
#define KERN_INFO       KERN_SOH "6"    /* informational */
#define KERN_DEBUG      KERN_SOH "7"    /* debug-level messages */
001이 들어간것은 default이고, 이런거 이미 보셨을 겁니다. 터미널 옵션에서 색상지정 같은것 할때, 사용합니다.
초기 터미널에서 지원하는 문자가 제한되어 있던 시절이 있었습니다. 예를 들면 대문자만 사용가능한 경우 소문자를 대문자로 바꾸는 처리등이 필요했었고, 이러한 처리를 제어 문자를 이용해서 제한된 기능을 보완했었습니다. ASCII 0x01 은 START OF HEADING을 나타내고, 전송된 문자열에서 제어 헤더라는 것을 알려줍니다.
ASCII 제어 문자 예시 0x01 SOH : Start Of Heading 전송이 시작됨을 나타냄 0x04 EOT : End Of Transmission 전송이 끝난 것을 나타냄 0x08 BS : Back Space 1문자 소거 0x0d CR : Carriage Return 동일 행에 맨 처음 시작으로 이동시킴 0x1b ESC : Escape Sequence 특수 문자나 제어 변환을 의미함.
키보드의 "엔터키"에 해당하는 "Escape 문자"는, \n 입니다. 즉, "백슬래쉬+소문자n" 입니다. 각종 프로그래밍 언어에서나, 편집기 등에서 \n 을 엔터키 대신에 사용할 수 있습니다. 유닉스나 리눅스에서는 엔터키를 "\n"을 사용하지만, 윈도우나 도스(MS-DOS)에서는 엔터키를 "\r\n" 이렇게 표현해 주어야 합니다. 이런 변환은 편집기에서 자동으로 해주지만, 그렇지 않은 경우 변환이 필요하게 됩니다.

3) 좋습니다. 그런데 왜 건드리지 말라고 써 놓았을까요? 건~~~방지게!

/* FIXED STRINGS! Don't touch! */
const char linux_banner[] =
        "Linux version " UTS_RELEASE " (" LINUX_COMPILE_BY "@"
        LINUX_COMPILE_HOST ") (" LINUX_COMPILER ") " UTS_VERSION "\n";

이제 커널 코드좀 봤다고.... 깊은 분노가 느껴지는군요!
아마 저 정보를 그대로 어디선가 사용하는가 싶지 않습니다. 그렇기에 수정하면, 다 어긋나겠지요?

3. setup_arch()->setup_processor()


1) KERNEL이 정의되었는지 어떻게 확인할 수 있나요?

#ifdef __KERNEL__

struct proc_info_list {
        unsigned int            cpu_val;
        unsigned int            cpu_mask;
        unsigned long           __cpu_mm_mmu_flags;     /* used by head.S */
        unsigned long           __cpu_io_mmu_flags;     /* used by head.S */
        unsigned long           __cpu_flush;            /* used by head.S */
        const char              *arch_name;
        const char              *elf_name;
        unsigned int            elf_hwcap;
        const char              *cpu_name;
        struct processor        *proc;
        struct cpu_tlb_fns      *tlb;
        struct cpu_user_fns     *user;
        struct cpu_cache_fns    *cache;
};
kernel make를 하면 init/main.o.cmd에 보면 option을 확인할 수 있습니다.
build 후, arch/arm/kernel/.topology.o.cmd를 열어보시면 아래와 같이 KERNEL이 선언되어 있음을 확인할 수 있습니다.
cmd_arch/arm/kernel/topology.o := ...

-D__KERNEL__ -mlittle-endian -Iarch/arm/mach-exynos/include -Iarch/arm/plat-samsung/include
-Wall -Wundef -Wstric t-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common
-Werror-implicit-function-declaration -Wno-format-security -fno-delete-null-pointer-checks
-O2 -fno-dwarf2-cfi-asm -mabi=aapcs-linux -mno-thumb-interwork -funwind-tables
-m arm -D__LINUX_ARM_ARCH__=7 -march=armv7-a -msoft-float -Uarm -Wframe-larger-than=1024 
-fno-stack-protector -Wno-unused-but-set-variable -fomit-frame-pointer -g -Wdeclaration-after-statement 
-Wno-pointer-sign -fno-strict-overflow -fco    nserve-stack -DCC_HAVE_ASM_GOTO    
    ...

2) 어떻게 어셈블리 함수에서, 값을 찾아올 수 있나요?

list = lookup_processor_type(read_cpuid_id());
ENTRY(lookup_processor_type)
        stmfd   sp!, {r4 - r6, r9, lr}
        mov     r9, r0
        bl      __lookup_processor_type
        mov     r0, r5
        ldmfd   sp!, {r4 - r6, r9, pc}
ENDPROC(lookup_processor_type)  
예전 어셈 진행할때 보았던 코드이며, CPU에 해당하는 구조체값을 가져온 것입니다. 이 함수가 수행하는 역할은, 구조체가 어느 주소에 있는지 알 수 있으며, 그 포인터 값을 찾아옵니다.

3) 아래 code와 같이 _read_mostly는 section으로 구분되는데, 왜 cache hit율이 높은건가요?

int __cpu_architecture __read_mostly = CPU_ARCH_UNKNOWN;
#define __read_mostly __attribute__((__section__(".data..read_mostly")))
read_mostly로 지정한 section이 따로 cache에 들어가는 것은 아니고, cache hit가 자주될 것으로 예상되는 지점을 하나의 section으로 묶어서 효율을 높이는 것입니다.

4) UNDEF를 사용하는 이유는 무엇인가요?

#ifdef CONFIG_CPU_V7
# ifdef CPU_NAME
#  undef  MULTI_CPU
#  define MULTI_CPU
# else
#  define CPU_NAME cpu_v7
# endif
#endif
중복 선언을 피함으로써 컴파일 시 warning을 나오지 않게 합니다. 간단히 중복선언 후 컴파일 해보면 다음과 같이 에러 메세지가 발생 합니다.
  - define.h             |           - define.c
#define JAY 9            |        #include "define.h"
                         |        #define JAY
                         |        int main(int argc, const char *argv[])
                         |        {
                         |             return 0;
                         |        }

--------------------------------------------------------------------------
root@ubuntu:/define# arm-linux-gnueabihf-gcc define.c                          
define.c:4:0: warning: "JAY" redefined [enabled by default]
define.h:1:0: note: this is the location of the previous definition
root@ubuntu:/define#

5) MULTI_CPU 같이 정의된 이름이 많은경우 찾기가 힘든데, 어떻게 한파일내에서 정의된 위치를 알 수 있나요?

해당 위치에서, 1) "[" 누르시고, 2) "I" 를 누르시면 확인할 수 있습니다.
glue-proc.h
  1:   19 #undef MULTI_CPU
  2:   28 #  undef  MULTI_CPU
  3:   29 #  define MULTI_CPU
  4:   37 #  undef  MULTI_CPU
  5:   38 #  define MULTI_CPU
  6:   46 #  undef  MULTI_CPU
  7:   47 #  define MULTI_CPU
  8:   55 #  undef  MULTI_CPU
  9:   56 #  define MULTI_CPU
 10:   64 #  undef  MULTI_CPU
 11:   65 #  define MULTI_CPU
 12:   73 #  undef  MULTI_CPU
 13:   74 #  define MULTI_CPU
 14:   82 #  undef  MULTI_CPU
 15:   83 #  define MULTI_CPU
 16:   91 #  undef  MULTI_CPU
 17:   92 #  define MULTI_CPU
 18:  100 #  undef  MULTI_CPU

6) printk() 에서 cr_alignment값이 나오는데, 이게 무엇인가요?

CPU: ARMv7 Processor [413fc082] revision 2 (ARMv7), cr=10c53c7f
먼저 위에서 나오는 cr값은 SCTLR 값입니다. 이 값은 어셈분석할때 설정하였고, 여기서 우리는 alignment와 no-alignment만 공부합시다.

alignment는 무엇인가?

  • ARM은 기본적으로 4바이트로 align되어 있습니다. 그런데 예를들어 우리가 주소값을 0x02를 읽었다고 가정해 봅시다. 이런 경우 ARM은 abort를 발생합니다. 하지만 v6부터 하드웨어 적으로 no-align인 경우에도 읽을 수 있도록 지원합니다. 지원할경우 SCTLR.A 비트를 설정하면 됩니다.
    자 그럼 이제 우리가 어떻게 값을 셋팅하였고, 위에 cr값이 어떻게 나왔는지 봅시다. start_kernel 점프 전, 'A' bit를 SCTLR 레지스터에 설정하였습니다. (head-common.S:120)
        cmp     r7, #0         
        bicne   r4, r0, #CR_A                   @ Clear 'A' bit
        stmneia r7, {r0, r4}                    @ Save control register values  
        b       start_kernel   
그렇다면 A비트는 설정이 되어있어야 겠죠? 위의 cr값은 '10c53c7f' 여기서 하위비트만 보면 f로 1111입니다. 

레지스터와 비교해보면 A비트가 설정되었음을 확인할 수 있습니다.

7) hwcap이라고 네이밍한 이유가 있을까요? 그리고 하드웨어 divider가 무엇인가요?

static void __init cpuid_init_hwcaps(void)
{
...

        divide_instrs = (read_cpuid_ext(CPUID_EXT_ISAR0) & 0x0f000000) >> 24;

        // divide instruction을 지원하는지 검사하여 elf hwcap을 업데이트
        switch (divide_instrs) {
        case 2:
                elf_hwcap |= HWCAP_IDIVA;
        case 1:
                elf_hwcap |= HWCAP_IDIVT;
        }    
...        
}

hwcap(Hardware Capability)은 말 그대로 하드웨어 지원사항을 나타내는 것입니다.
divider는 정수형 나눗셈을 지원하는 명령어로, 하드웨어적으로 divider를 지원하는 것인지 체크하는 것입니다. 보통 하드웨어 divider는 10사이클 정도가 걸리며, 소프트웨어는 100사이클 이상 걸린다고 보면 됩니다.

8) _pure 속성은 무엇일까요?

int __pure cpu_architecture(void)
{               
        BUG_ON(__cpu_architecture == CPU_ARCH_UNKNOWN);

        return __cpu_architecture;
}

pure는 const 속성과 같이 알아두어야 편합니다. 결론부터 얘기하면, const가 조금 더 강하고, pure는 조금 약한 느낌이라고 보면 될 것 같습니다.
pure속성은 특징은 다음과 같습니다.
  1. 동일한 매개변수를 사용하여 여러번 호출하는 경우 매번 같은 값이 반환되어야 함.
  2. 설사 동일한 값이 반환되더라도, 내부적으로 어떤 값을 변화시켜서는 안됨. (정적 변수라던지, 포인터 매개 변수를 통해 포인터가 가리키는 값을 수정한다던지.... 전역 변수를 수정한다던지...)
  3. 당연히 내부적으로 순수하지 않는 함수를 호출하면 안됨. 특히 수학 함수 같은 경우가 pure 함수에 많이 해당됩니다.
int square(int) __attribute__((pure));
어떠한 횟수든, 어디에서든지 동일한 인자 값만 넘기면 동일한 결과값을 받을 수 있으며, 리턴값을 제외하곤 함수는 다른 어떤 곳에도 영향을 주지 않죠. 좀 더 구체적인 예제 소스를 보겠습니다.
int factr(int n) __attribute__((pure))
{
    int f = 1;
    while(n> 0)
        f *= n--;
    return f;
}
pure를 명시하는 이유는 컴파일러가 좀 더 aggresive한 최적화에 몰두할 수 있도록 개발자가 알려 주는 것입니다. pure한 함수에 동일한 인자값이 전달되는 경우 여러 곳에서 다수로 호출될지라도 그 결과값은 동일할 거구요. 결국, 컴파일러는 내부적으로 그 함수를 한번만 호출하고 결과값을 재사용하도록 코드 최적화를 하는 것입니다.
참조 백창우님 글 링크 : http://www.iamroot.org/xe/Hypervisor_1_Xen/7536
attribute ((pure)) 가 붙은 function은 strlen' 또는memcmp'와 같이 내부 상태는 변화 시키지 않고 단순히 결과만 리턴하기 때문에 CSE나 loop 최적화시 호출되는 횟수가 바뀌어도 상관이 없다는 의미인것 같습니다.
결국 한번만 호출하고 loop 내에서 그 결과를 계속 사용해도 되는 함수등을 의미하는것 같습니다.
volatile memory 즉 하드웨어 레지스트를 읽는 함수 같은 경우에는 매번 그 값이 변경될수 있기에 매번 호출해야 되지만 그렇지 않고 특정 메모리 영역을 읽는 함수 같은 경우에 DMA 영역이 아니면 그 값은 저절로 바뀌는 일이 없기 때문에 1번만 호출하고 그 결과를 계속 사용해도 무방하다는 의미 인것 같네요.
결국 pure 타입의 함수에 대해 attribute ((pure)) 를 붙이면 컴파일러가 최적화를 할때 이를 고려해서 좀 더 최적화하는데 용이하겠네요.

9) VIPT, PIPT 개념이 나옵니다. remind가 필요합니다.

static void __init cacheid_init(void)
{       
...
        } else if (arch >= CPU_ARCH_ARMv6) {
                // T.R.M: 4.3.2 Cache Type Register
                unsigned int cachetype = read_cpuid_cachetype();
                if ((cachetype & (7 << 29)) == 4 << 29) {
                        /* ARMv7 register format */
                        arch = CPU_ARCH_ARMv7;
                        cacheid = CACHEID_VIPT_NONALIASING;

                        // L1ip: b11, (Physical index, physical tag)
                        switch (cachetype & (3 << 14)) {
                        case (1 << 14):
                                cacheid |= CACHEID_ASID_TAGGED;
                                break;
                        case (3 << 14): // this
                                cacheid |= CACHEID_PIPT;
                                break;
                        }
...                        

스터디 시간에 논의되었던 이슈는 다음과 같습니다.
  • PIPT가 나오기 전까지의 history [VIVT -> VIPT -> PIPT]
  • 기존 시스템이 점점 바뀔수 밖에 없는 이유 (cache의 way size 측면)
  • 덩달아서 생겨난 micro TLB의 개념
    깁니다. 매우 깁니다. 글로 적기는 하였지만 그림도 없고 이해가 힘드실 겁니다. (그림 그릴 정성이 없습니다.ㅡㅡ;;) 이 글보다 컴퓨터 구조를 공부하시는게 이롭습니다. 잡설이 길고 시작합니다.
    cache lookup은 2단계로 이루어진다.
  • index 계산 (cache way에서 해당 entry의 위치)
  • tag 비교 (index에 해당하는 여러 set에서 나머지 주소 비교
    여기서 VA->PA 전환이 가능한 3가지 지점에 따라 PIPT, VIPT, VIVT로 나누어진다.
     |       step1       |      step2        |
     |-------------------|-------------------|
     |     index 연산    |    tag비교        |
     1                   2                   3
     PIPT              PIVT                VIVT
VA<--------------------------------------------->PA
1(PIPT): index도 비교하기전에 VA->PA변환이 이루어진다. 따라서 index, tag모두 PA기준으로 동작한다. Physically Indexed, Physically Tagged
2(VIPT): index 연산 이후 VA->PA로 변환된다. 따라서 index 연산까지는 VA로 tag비교는 PA로 동작한다. Virtually Indexed, Physically Tagged
3(VIVT): 모든 cache lookup 이후 VA->PA로 변환된다. 따라서 index 연산과 tag비교 모두 VA로 동작한다. Virtually Indexed, Virtually Tagged
여기서 aliasing 문제를 생각해보자
   VA      PA
 0x1000--0x2000
        /
 0x3000/
현재 위와 같이 서로다른 VA가 동일한 PA에 매핑되는 경우라 하자 P1 태스크가 초기화후 P2태스크가 update하기를 기다리는 다음의 코드가 있다. P1: write(0x1000, 0x1111); P2: write(0x3000, 0x2222); P1: repeat until read(0x1000) = 0x1111;
PIPT의 경우: 0x3000, 0x1000모두 0x2000으로 바뀐 후 cache에 적재 aliasing문제 없다.
VIVT의 경우 cache에 0x1000, 0x3000번지가 동시에 들어가 있을 가능성이 있다. 이경우 cache에서 서로 다른 entry을 write하므로 P1은 P2의 write를 볼 수 없다.
VIPT의 경우 2가지 경우가 있다.
  1. 4 way 16kB cache의 경우: 즉 1 way가 4kB. 4kB는 page frame 단위로 그 범위 안에서는 PA=VA이다. 즉 virtual index와 Physical index가 동일하므로 PIPT와 동일하게 동작한다.
  2. 4 way 32kB cache의 경우: 1 way가 8kB 1과 달리 MMU에 의해 index가 바뀐다. VIVT와 마찬가지로 aliasing 가능성 존재
    aliasing 문제를 풀기위해서는 PIPT가 좋다. 나머지의 경우 SW관리가 필요하다. 그런데 PIPT의 경우 latency문제가 있다. pipeline stall등을 벌기 위해 cache를 도입하고 그중에서도 더 속도를 빠르게 하기 위해 작은 size의 L1 cache를 도입했는데 TLB lookup 시간을 허비하는 것이다. 다음의 2가지가 문제다.
    1. 일반적인 2 level 혹은 3 level descriptor의 경우 2단게 혹은 3단계의 lookup을 반복
    2. TLB hite rate
    해결방안은 아래와 같다. 1A. 1.은 보통 최종단계의 translation 결과를 저장하여 해결한다. 2A. TLB miss의 경우 memory read로 인해 latency가 길어지므로 TLB의 크기를 늘려 hit rate를 증가
    1A는 2A의 필요성을 더 크게 한다. 문제는 물리적인 제약상 메모리는 크기가 클수록 접근시간이 느려진다는 점이다.
    이를 극복하기 위해 L2상위에 L1 캐시를 도입한 것 처럼 full TLB 앞단에 uTLB를 도입하여 latency를 최소화한다.

2013년 9월 7일 토요일

[Linux Kernel] 20주차(2013.09.07) 후기

10차 ARM 리눅스 커널 스터디 20주차(2013.09.07) 후기입니다.

# 일시 : 2013.09.07 (20주차)
# 모임명 : NIPA지원_IAMROOT.ORG_10차ARM-C
# 장소 : 토즈 타워점
# 장소지원 : NIPA지원
# 참여인원 : 9명
# 스터디 진도 :
 - start_kernel()-> boot_cpu_init();
// 현재 cpu(core id)를 얻어서 cpu_XXX_bits[] 의 cpu를 셋한다.

# if (!printk_ratelimit()) goto out_enable;

<code> :: printk.h
#define printk_ratelimit() __printk_ratelimit(__func__)
</code>

## 1) 아래 code에서 _func_이 의미하는 것이 무엇인가요?

현재 호출한 함수를 의미합니다. 여기서는 debug_smp_processor_id() 입니다.

## 2) SPINLOCK을 우리가 공부했었던가요? 개념의 이해가 필요합니다.

간단하게 언급하면, 멀티코어가 되면서 나온것이 spinlock입니다.
기존의 mutex가 시간이 오래 걸리기 때문에, 나오게 되었습니다.

spinlock에 대해 각자 공부하고 토론하면 좋을 것 같습니다.

spinlock이 single core에서 의미없는 이유만 기재하겠습니다.
1. Lock을 얻을 수 없다면, 계속해서 Lock을 확인하며 얻을 때까지 기다린다.
이른바 바쁘게 기다리는 busy waiting이다.
2. 바쁘게 기다린다는 것은 루프를 돌면서 최대한 다른 스레드에게 CPU를
양보하지 않는 것이다.
3. Lock이 곧 사용가능해질 경우 컨텍스트 스위치를 줄여 CPU의 부담을
덜어준다. 하지만, 만약 어떤 스레드가 Lock을 오랫동안 유지한다면
오히려 CPU 시간을 많이 소모할 가능성이 있다.
4. 하나의 CPU나 하나의 코어만 있는 경우에는 유용하지 않다.
그 이유는 만약 다른 스레드가 Lock을 가지고 있고
그 스레드가 Lock을 풀어주려면 싱글 CPU 시스템에서는 어차피
컨텍스트 스위치가 일어나야 하기 때문이다.

## 3) ratelimit함수를 보면 interval과 burst로 제한을 걸고 있다.
왜 그런걸까요?

실제로 사운드카드 같은 것은 printk를 이용해서 디버깅을 하다보면,
많이 끊기는 현상이 발생합니다. 따라서 제한을 둔것이 아닌가 싶습니다.

## 4) rs→interval이 timer를 통해서 값이 변하는 것같다.
하지만 어디서 값이 변경되는지 확인이 필요하다.

<code>
int __ratelimit(struct ratelimit_state *rs, const char *func)
{
        unsigned long flags;
        int ret;

        // 5s 가 지났는지 검사 수행
        if (!rs->interval)
                return 1;
...
}
</code>

## 5) 아래 strexeq 구문이 이해가 안간다.

<code>
static inline int arch_spin_trylock(arch_spinlock_t *lock)
{
        unsigned long tmp;
        u32 slock;

        // lock->slock이0 이면 unlocked
        // lock->slock이0x10000 이면 locked

//"     ldrex   slock, lock->slock\n"
//"     subs    tmp,   slock, slock, ror #16\n"         : tmp = slock - (slock >> 16)
//"     addeq   slock, slock, (1 << TICKET_SHIFT)\n"    : slock = 0x10000
//"     strexeq tmp,   slock, lock->slock"              : tmp는 strexeq의 수행 결과 값
        _asm_ _volatile_(
"       ldrex   %0, [%2]\n"
"       subs    %1, %0, %0, ror #16\n"
"       addeq   %0, %0, %3\n"
"       strexeq %1, %0, [%2]"
        : "=&r" (slock), "=&r" (tmp)
        : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
        : "cc");

        if (tmp == 0) {
                smp_mb();
                return 1;
        } else {
                return 0;
        }
}
</code>

- LDREX (배타적인 로드)는 메모리로 부터 데이터를 읽고,
동시에 메모리 주소에 태그합니다.
- STREX (배타적인 스토어는 데이터를 메모리에 저장하는데,
태그가 여전히 유효한 경우만 저장합니다.
- 그외의 경우에는 메모리는 수정되지 않습니다.

참조 링크 : [Ref.] http://www.iamroot.org/xe/Kernel_8_ARM/65971

## 6) 위 code에서 그러면 LDREX와 STREX는 쌍(pair)으로 구동이 되는 건가요?

 멀티 프로세서가 도입되면서 SWP 명령이 성능 이슈를 회피하기 위해,
ARM v6 이후의 아키텍쳐에서 SWP는 폐기되었습니다.
멀티 프로세서 환경에서 프로세서들 사이에 동일한 공유 메모리 접근을
동기화 하기 위해서는 global exclusive monitor를 사용합니다.
global exclusive monitor는 각 프로세서가 베타적으로 접근하는 주소를
태그해 놓습니다.
LDREX를 통해 베타적 상태를 태그해 둔 메모리에 다른 프로세서가
단순 str 연산이나 strex를 수행하면,global exclusive monitor는
해당 태그 상태를 open으로 변경하게되어 베타적 접근이 실패된 것을
알려 주게 됩니다.

참조링크 : [Ref.] http://www.iamroot.org/xe/Kernel_8_ARM/66152

## printk_ratelimit() -> __printk_ratelimit(__func__) -> __ratelimit(&printk_ratelimit_state, func);


<code>
int ___ratelimit(struct ratelimit_state *rs, const char *func)
{
        unsigned long flags;
        int ret;

        // 5s 가 지났는지 검사 수행
        if (!rs->interval)
                return 1;
        if (!raw_spin_trylock_irqsave(&rs->lock, flags))
                return 0;

        if (!rs->begin)
                rs->begin = jiffies;

        // ARM10C 20130907 rs->interval = 5 * HZ
        // 시간 만료가 되었나?
        if (time_is_before_jiffies(rs->begin + rs->interval)) {
                if (rs->missed)
                        printk(KERN_WARNING "%s: %d callbacks suppressed\n",
                                func, rs->missed);
                rs->begin   = 0;
                rs->printed = 0;
                rs->missed  = 0;
        }
        // ARM10C 20130907 rs->burst = 10
        if (rs->burst && rs->burst > rs->printed) {
                rs->printed++;
                ret = 1;
        } else {
                rs->missed++;
                ret = 0;
        }
        raw_spin_unlock_irqrestore(&rs->lock, flags);

        return ret;
}
</code>

### raw_spin_trylock_irqsave(&rs->lock, flags)

<code>
#define raw_spin_trylock_irqsave(lock, flags) \
({ \
        local_irq_save(flags); \
        raw_spin_trylock(lock) ? \
        1 : ({ local_irq_restore(flags); 0; }); \
})
</code>

#### local_irq_save(flags);

<code> ::irqflags.h
#define local_irq_save(flags)                           \
        do {                                            \
                raw_local_irq_save(flags);              \
                trace_hardirqs_off();                   \
        } while (0)
</code>

##### raw_local_irq_save(flags)
// 현재 CPSR을 flag로 가져옴

<code>
#define raw_local_irq_save(flags)                       \
        do {                                            \
                typecheck(unsigned long, flags);        \
                flags = arch_local_irq_save();          \
                /*ARM10C 현재 cpsr을 flag로가져옴*/     \
        } while (0)
</code>

##### trace_hardirqs_off();

<code> ::irqflags.h
# define trace_hardirqs_off()           do { } while (0)    // ARM10C this
</code>

Q: 왜 함수의 네이밍을 hardirq라고 했을까요? hard의 의미가 있을까요?
A: hard의 의미는 processor상의 irq를 on/off라고 지칭하는 것입니다.
   soft는 변수를 가지고 제어하는 것입니다.

#### raw_spin_trylock(lock) ? 1 : ({ local_irq_restore(flags); 0; });

<code> :: spinlock.h
#define raw_spin_trylock(lock) __cond_lock(lock, _raw_spin_trylock(lock))
</code>

##### _raw_spin_trylock(lock)

<code> :: spinlock.h
int _lockfunc _raw_spin_trylock(raw_spinlock_t *lock)
{
        return __raw_spin_trylock(lock);
}
</code>

###### Q: _lockfunc은 무엇일까요?
attribute이고, 열어보시면 다음과 같이 정의되어 있습니다. spinlock section 이라고 보시면 됩니다.

#define __lockfunc __attribute__((section(".spinlock.text")))

하지만 18주차때 elf보시면 그런 section은 없습니다.

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .head.text        PROGBITS        c0008000 008000 0001c0 00  AX  0   0  4
  [ 2] .text             PROGBITS        c00081c0 0081c0 35c32c 00  AX  0   0 64
  [ 3] .rodata           PROGBITS        c0365000 365000 0e2ef0 00   A  0   0 64
  [ 4] __bug_table       PROGBITS        c0447ef0 447ef0 005b20 00   A  0   0  1
  [ 5] __ksymtab         PROGBITS        c044da10 44da10 0060b0 00   A  0   0  4
  [ 6] __ksymtab_gpl     PROGBITS        c0453ac0 453ac0 003640 00   A  0   0  4
  [ 7] __ksymtab_strings PROGBITS        c0457100 457100 01522c 00   A  0   0  1
  [ 8] __param           PROGBITS        c046c32c 46c32c 000750 00   A  0   0  4
  [ 9] __modver          PROGBITS        c046ca7c 46ca7c 000584 00   A  0   0  4
  [10] __ex_table        PROGBITS        c046d000 46d000 000fc8 00   A  0   0  8
  [11] .ARM.unwind_idx   ARM_EXIDX       c046dfc8 46dfc8 019e20 00  AL 16   0  4
  [12] .ARM.unwind_tab   PROGBITS        c0487de8 487de8 0024a8 00   A  0   0  4
  [13] .notes            NOTE            c048a290 48a290 000024 00  AX  0   0  4
  [14] .vectors          PROGBITS        00000000 490000 000020 00  AX  0   0  4
  [15] .stubs            PROGBITS        00001000 491000 000240 00  AX  0   0 32
  [16] .init.text        PROGBITS        c048b260 493260 01d4fc 00  AX  0   0 32
  [17] .exit.text        PROGBITS        c04a875c 4b075c 000c30 00  AX  0   0  4
  [18] .init.arch.info   PROGBITS        c04a938c 4b138c 000054 00   A  0   0  4
  [19] .init.tagtable    PROGBITS        c04a93e0 4b13e0 000048 00   A  0   0  4
  [20] .init.smpalt      PROGBITS        c04a9428 4b1428 0001f0 00   A  0   0  4
  [21] .init.pv_table    PROGBITS        c04a9618 4b1618 0002f4 00   A  0   0  1
  [22] .init.data        PROGBITS        c04a9910 4b1910 00ba4c 00  WA  0   0  8
  [23] .data..percpu     PROGBITS        c04b6000 4be000 001d00 00  WA  0   0 64
  [24] .data             PROGBITS        c04b8000 4c0000 035100 00  WA  0   0 64
  [25] .bss              NOBITS          c04ed100 4f5100 041ae0 00  WA  0   0 64

이 현상은 vmlinux.lds파일을 확인해 보시면, .text section에 spinlock.text가 포함된 것을 볼 수 있습니다.

.text : { /* Real text segment         */
 _stext = .; /* Text and read-only data        */
   __exception_text_start = .;
   *(.exception.text)
   __exception_text_end = .;
 
   . = ALIGN(8); *(.text.hot) *(.text) *(.ref.text) *(.devinit.text) *(.devexit.text) *(.cpuinit.text) *(.cpuexit.text) *(.text.unlikely)
   . = ALIGN(8); __sched_text_start = .; *(.sched.text) __sched_text_end = .;
   . = ALIGN(8); __lock_text_start = .; *(.spinlock.text) __lock_text_end = .;
   . = ALIGN(8); __kprobes_text_start = .; *(.kprobes.text) __kprobes_text_end = .;
   . = ALIGN(8); __idmap_text_start = .; *(.idmap.text) __idmap_text_end = .; . = ALIGN(32); __hyp_idmap_text_start = .; *(.hyp.idmap.text) __hyp_idmap_text_end = .;

###### __raw_spin_trylock(lock)

<code> ::spinklock_api_smp.h
static inline int __raw_spin_trylock(raw_spinlock_t *lock)
{
preempt_disable();
if (do_raw_spin_trylock(lock)) {
spin_acquire(&lock->dep_map, 0, 1, _RET_IP_);
return 1;
}
preempt_enable();
return 0;
}
</code>

####### preempt_disable();

<code> :: preempt_disable()
#define preempt_disable()/*ARM10C this*/ \
do { \
inc_preempt_count(); \
barrier(); \
} while (0)
</code>

######## inc_preempt_count();

<code> ::preempt.h
#define inc_preempt_count() add_preempt_count(1)
</code>

######### add_preempt_count(1)

<code> ::core.c
void __kprobes add_preempt_count(int val)
{
#ifdef CONFIG_DEBUG_PREEMPT // ARM10C Y 
        /*
         * Underflow?
         */
        // ARM10C 20130907 preempt_count()가  0 보다 작은 경우는 bug이다.
        if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
                return;
#endif
        preempt_count() += val;
        // ARM10C 20130907 0x40000001 + 1(val)
#ifdef CONFIG_DEBUG_PREEMPT
        /*
         * Spinlock count overflowing soon?
         */
        DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
                                PREEMPT_MASK - 10);             
#endif                    
        // ARM10C 20130907 preempt_count = 0x40000002
       if (preempt_count() == val)     
                trace_preempt_off(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
}
</code>

Q: _kprobes가 나오는데 무엇일까요?
A: 커널 코드에 원하는 작업을 동적으로 추가할 수 있는 강력한 디버깅 기법이다.
Ref. Kprobes 동작 방식 #1
http://www.chunghwan.com/ko/systems/how-kprobes-works-1/

Q: 계속 preempt count를 통하여 preemption을 막는다고 하는데 어떻게 할까요?
A: interrupt Handler에서 count를 이용하여 0이상이면
   preempt가 발생하지 못하게 할것이다.

Q: 그럼 숫자를 조금만 추가하면 될것인데, 왜 0x4000_0001가 들어갔을까요?
A: 지금은 충분한 숫자를 미리 넣어두었을 뿐이다.
   향후에 start_kernel()→sched_init()→init_idle() 함수에
   의해 다시 재조정 될 것이다.

Q: preempt_count()+=val이 가능한 문법인가? 함수에 어떻게 값을 더할 수 있나요?
A: 따라가보면 preempt_count()는 함수가 아니라 구조체 값입니다.
   그래서 가능합니다.

Q: 그래도 혼란스럽다. 지금은 scheduler가 off상태인데,
   preempt 자체가 필요가 있을까?
A: 말씀하신것처럼, 현재는 의미가 없을수도 있습니다.
   하지만 이 함수는 나중에 계속 사용하는 함수입니다.

####### do_raw_spin_trylock(raw_spinlock_t *lock)

<code>
static inline int do_raw_spin_trylock(raw_spinlock_t *lock)
{
return arch_spin_trylock(&(lock)->raw_lock);
}
</code>

######## arch_spin_lock()
원래는 arch_spin_trylock 코드를 봐야 하지만,
이해를 돕기 위해 arch_spin_lock 코드를 봤습니다.

<code>
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
        unsigned long tmp;
        u32 newval;//다음 next 값
        arch_spinlock_t lockval;//현재 next 값
//ARM10C 20130907 
//"1:   ldrex   lockval, &lock->slock\n"
//현재 next(lockval)는 받아 놓고,
//"     add     newval, lockval, (1<<TICKET_SHIFT)\n" tickets.next += 1
//다음 next(newval) 는 += 1하고 저장 한다.
//"     strex   tmp, newval, &lock->slock\n"
//"     teq     tmp, #0\n"
//"     bne     1b"
        // lock->slock에서 실제 데이터를 쓸때(next+=1) 까지 루프
        // next+=1 의 의미는 표를 받기위해 번호표발행
        __asm__ __volatile__(
"1:     ldrex   %0, [%3]\n"
"       add     %1, %0, %4\n"
"       strex   %2, %1, [%3]\n"
"       teq     %2, #0\n"
"       bne     1b"
        : "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
        : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
        : "cc");
 
        // 실재 lock을 걸기 위해 busylock 한다.
        // 받은 번호표의 순을 기다린다.(unlock에서 owner을 증가 시켜서)
        while (lockval.tickets.next != lockval.tickets.owner) {
                wfe();  // ARM10C 이벤트대기(irq,frq,부정확한 중단 또는 디버그 시작 요청 대기. 구현되지 않은 경우 NOP
               // arch_spin_unlock()의 dsb_sev();가 호출될때 깨어남
                lockval.tickets.owner = ACCESS_ONCE(lock->tickets.owner);
                // ARM10C local owner값 업데이트
        }   
 
        smp_mb();
}
</code>

######## LDREX, STREX에 대해서 다시 정리하겠습니다.

STREX는 swap결과에 따라 성공하면 tmp에 0을넣고, 실패하면 1을 넣는 구문입니다.

이 명령어들 자체가 예전 아키텍처에서 swp명령이 cost가(속도가 느림) 많이
발생하기 때문에, 나오게된 명령들입니다.해당 명령어가 추가되었다는 의미는,
AMBA 버스에 원래 기존 load signal이 존재하였는데, 속도문제로 transaction이
따로 추가되어 이 명령어들은 독립적으로 signal이 나옵니다.

그리고 혼란스러워 하시는것 같은데, spinlock은 atomic lock을 하기위한 수단일
뿐입니다.

상위 관점에서 STREX와 LDREX를 설명하면 아래와 같다.
일단 비교대상인 SWP는 당연히 Rn 주소에서 값을 읽어오고(Rt) 전달된 값(Rt2)을
write합니다.

LDREX는 항상 동작하며 Rn주소에서 읽은 값을 Rt에 저장함과 동시에
메모리 상태를 exclusive access상태로 변경

STREX는 메모리 상태에 따라 STR 실행 여부를 결정.
(실행 여부는 Rd(위의 tmp변수)값으로 확인)

※ STREX 실행 여부를 결정하는 메모리 상태는 CLREX 실행 여부,
다른 agent에 의한 STREX/STR 실행 여부 등에 의해 변경.


- 주의 -
LDREX/STREX는 HW 제약으로 정확하게 동일 어드레스가 아닌
비슷한 range에 들어도 동작하므로 SW작성에 주의가 필요.
또한 1코어내의 서로 다른 thread에서 수행하는 LDREX, STREX를 구분할수
없으므로 (정확하게는IMPLEMENTATION DEFINED)
※ 8차 스터디 글에서 나타낸 바와 같이 context switching시에 dummy STREX
 또는 CLREX의 수행이 필요.


HW적인 관점에서 STREX와 LDREX를 설명하면 아래와 같다. (SWP vs. STREX/LDREX)
1) 먼저 SWP은 bus가 lock된 (bus arbiter가 다른 master들이 해당 slave로
접근하지 못하도록 제어) 상태에서 ldr&str가 순차적으로 수행되는 단순한 구조



2) LDREX와 STREX의 경우 최근에 access한 agent, 값 등에 대한 정보를
local monitor와 global monitor에 저장하고, STREX의 수행여부를 결정



따라서 LDREX, STREX의 경우 Core 또는 memory IF에 monitor를 구현하기 위한
tag memory와 FSM이 필요하다.
monitor관련 자세한 내용은 AARM v7의 A3.4절 참조, Figure A3-3,4에
local, global monitor의 state machine이 나타나 있다.

SWP를 Exclusive access(LDREX, STREX)로 대체한 이유에 대한 ARM사의 설명입니다.
Ref.: ARM Synchronization Primitives, A1.2 Limitations of SWP and SWPB

요약하면,
1. SWP의 (LOAD+STORE)를 LDREX, STREX로 분리하여 Pipeline stall 및
interrupt latency 향상

2. Multicore등의 환경에서 memory lock으로 인한 메모리 성능 저하 방지
(bus상에서 하나의 master가 lock하고 있는 slave에 다른 master는 lock 해제시까지
 대기해야함)

3. SWP은 LOCK만 구현가능하지만(swap만으로는 increment/decrement가 불가),
LDREX,STREX는 세마포어 구현이 가능하다.(물론 lock이 구현된다면 lock으로
semaphore구현은 가능, 다만 여기서는 직접 구현 가능 여부를 말함)

※ SWP은 AXI4(ACE) 이후부터 지원되지 않음(관련 시그널이 삭제되었음)

관련한 학술적 내용은 Computer Architecture 교재나 강의 자료의 synchronization을
읽어보시는 것도 좋습니다.
fetch and add/compare and swap(CAS)/load linked & store conditional(LLSC)로
분류하여 설명한 자료들이 있네요.

######## SPINLOCK에 대해서 다시한번 짚고 넘어가야 할 것 같습니다.

spin lock은 mutiprocessor system에서 여러 processor가
동시에 critical section에 진입하지 못하도록 하는 synchronization 기법이다.
한 processor가 lock을 가지고 있으면 다른 processor들은 unlock될 때까지
busy-wait하다가 lock을 차지하기 위해 동시에 lock 변수에 접근(write)한다.

기존의 spin lock은 2가지 문제점이 존재하였습니다.
1) 각 processor간에 lock을 획득하는 순서 보장 못함
2) 한 processor가 lock 변수에 write를 하면 다른 processor의 cache line이
invalidate되어 성능이 악화

이를 해결하기 위해서 2.6.25버전부터 ticker spin lock이 도입되어,
각 processor들은 자신만의 ticket을 부여받고
자기 차례가 돌아오는 경우에만 write를 시도하여,
순서대로 lock을 얻고 전체적으로 cache miss 횟수를 줄입니다.
(Ref. [Linux] ticket spin lock)

라고는 하지만, 역시 이해하기에는 그림이 짱짱이죠?
ticket spin lock은 은행 or 영화관의 티켓 발권기로 보시면 됩니다.


위와같이 티켓을 뽑았습니다.
번호는 79번이네요. 앞에 8명이나 있으니 계속 대기해야 합니다.



당연히 창구를 이용하고 있다면,
다른 사람은 대기 해야 겠죠?
그러다가 창구번호(tickets.owner)가 자신의 번호표(tickets.next)와 같아지면,
그때 이용 가능합니다.

Q: 그런데 이런경우 spin lock의 단점이 보입니다.
   자료형이 U16으로 선언되어 있는데,
   이 숫자를 넘어가면 overflow가 일어날 수 있겠네요.
A: 프로세서의 개수라서 16비트면 2^16개 입니다.
   임베디드에서 그럴 확률은 아직 머나먼 미래의 얘기일 것 같습니다.

Q: wfe()는 무슨 기능을 하나요?
A: event가(irq, fiq등) 들어오기 전까지 sleep이라고 보시면 됩니다.
   보통은 interrupt가 들어와야 깨어 납니다.
   여기서는 다른 프로세서가 시그널을 보낼것 입니다.

Q: subs %1, %0, %0, ror #16\n”에서 ror연산의 의미가 무엇일까요?
<code>
static inline int arch_spin_trylock(arch_spinlock_t *lock)
{
        unsigned long tmp;
        u32 slock;
 
        __asm__ __volatile__(
"       ldrex   %0, [%2]\n"
"       subs    %1, %0, %0, ror #16\n"
"       addeq   %0, %0, %3\n"
"       strexeq %1, %0, [%2]"
        : "=&r" (slock), "=&r" (tmp)
        : "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
        : "cc");
...
</code>

A: ror연산은 shift연산과 비슷하지만, 오른쪽으로 회전하라는 의미입니다.

   따라서, 위 구문은 next와 owner의 값이 같은지 체크하는 구문입니다.

Q: 우리는 lock과 try-lock 함수를 보았는데, 무엇이 틀린가요?
A: lock을 획득할 때까지 기다리는 것입니다. (block)
   try-lock은 시도하다가 안되면 그냥 넘어가는 lock입니다. (non-block)

Q: lock 전후로 dmb, dsb명령을 수행합니다. 왜 이렇게 사용할까요?
<code>
static inline void arch_spin_unlock(arch_spinlock_t *lock)
{ 
        smp_mb();   
        lock->tickets.owner++;
        dsb_sev(); // ARM10C 이벤트발생 
} 
</code>
A: 앞의 dmb 명령은 미리 정리를 해서 안섞이게 할려고 하는 것이다.
   중요한 키가 존재하고, 내가 작업을 하고 있는데
   owner를 미리 바꾸면 값이 이상해 진다.

   owner를 추가하고 dsb 명령을 수행하는 이유는 memory까지 확실히 전달되어야,
   다음에 다른 프로세서가 깨어나서 공유자원을 보더라도 확실할 것이다.
   결국 owner값을 보호하기 위해서 하는 것이다.

Q: _CHECKER_가 의미하는 바가 무엇일까요?
<code>
#ifdef __CHECKER__
  # define __user         __attribute__((noderef, address_space(1)))
  # define __kernel       __attribute__((address_space(0)))
  # define __safe         __attribute__((safe))
         ...
  # define __cond_lock(x,c)       ((c) ? ({ __acquire(x); 1; }) : 0)
 
#else
  # define __user
  # define __kernel          
  # define __safe            
         ...
  # define __cond_lock(x,c) (c) //ARM10C this
#endif
</code>
A: Sparse에 관한 설정으로 리눅스용 코드 정적 분석 툴입니다.
    Sparse is a computer software tool designed to find possible coding faults
   in the Linux kernel
   상세 정보는 /documentation/sparse.txt에 정의되어 있습니다.
 
   __CHECKER__는 compiler.h에 있습니다. raw_spin_trylock -> __cond_lock 매크로를
   호출할 때 __CHECKER__에 따라서 __cond_lock이 선택됩니다.
   그림에서 노란색을 참조하세요.

compiler_h.png
## printf_ratelimit()-> time_is_before_jiffies()

<code> __ratelimit():: ratelimit.c
...
if (time_is_before_jiffies(rs->begin + rs->interval)) {
if (rs->missed)
printk(KERN_WARNING "%s: %d callbacks suppressed\n",
func, rs->missed);
rs->begin   = 0;
rs->printed = 0;
rs->missed  = 0;

}
...
</code>

Q1): jiffies가 무엇인가요?
A  : time tick이 발생할때 마다 추가되는 변수입니다. type은 long입니다.

Q2): 요즘 시스템은 time tick이 얼마나 되나요?
A  : 예전에는 100이었는데 요즘은 1000입니다. 즉, 1ms입니다.
     ms는 이걸로 측정하고, ns는 busy wait 해버립니다.
     실제로 개발하면 sleep을 많이 사용하는데, 시간이 정확하지는 않습니다.

     time tick과 jiffies은 timer isr에 의해 update된다.
     현재 IRQ가 disabled상태이므로 의미가 없다는 이야기.
     scheduler 얘기가 나온것은 보통 timer isr에 의해 수행되는 것이
     scheduler이기 때문에 나중에 scheduler가 enabled되는 시점에
     time tick 등이 update되어 해당 ratelimit함수가 유효해지기
     때문에 등장한 내용.

Q3): typecheck()를 실제로도 사용하나요?
<code>
#define time_after(a,b)         \
        (typecheck(unsigned long, a) && \
         typecheck(unsigned long, b) && \
         ((long)(b) - (long)(a) < 0))
</code>
A   : 실제로 본적은 없습니다.
      다만 개발할때 보통 지역변수로 flag를 기입하니까
      그 error를 체크하지 않을까 합니다.

      오늘 Computer Architecture 강의를 들으러 가서 이것저것 여쭤봤는데,
      교수님께서 이런 얘기를 해주시네요.
      그냥 참고하시기 바랍니다.

      Hardware적으로 type을 체크할 수는 없다.
      (Commercial 기준, research용 hardware는 tag를 따로 기입한다고 합니다.)
      따라서, 현재로서는 software로 type을 체크할 수 밖에 없다.

# boot_cpu_init()
-> set_cpu_online(),
-> set_cpu_active(),
-> set_cpu_present(),
-> set_cpu_possible()


<code>
static void __init boot_cpu_init(void)
{
int cpu = smp_processor_id();
/* Mark the boot cpu "present", "online" etc for SMP and UP case */
set_cpu_online(cpu, true);
set_cpu_active(cpu, true);
set_cpu_present(cpu, true);
set_cpu_possible(cpu, true);
}
</code>

 시스템 상에 존재하는 CPU의 상태 정보는 다음과 같은 4개의 비트맵
 (cpumask_t)으로 관리한다.

 cpu_possible_mask - 해당 비트에 대한 CPU가 존재할 수 있다.
 cpu_present_mask - 해당 비트에 대한 CPU가 존재한다.
 cpu_online_mask - 해당 비트에 대한 CPU가 존재하며 스케줄러가 이를 관리한다.
 cpu_active_mask - 해당 비트에 대한 CPU가 존재하며 task migration 시 이를
                   이용할 수 있다.

## this_cpu 값
 this_cpu는 threadinfo에 저장된 cpuid로 logical id로 physical core id는 0이
아닐 수 있다. boot rom 등에서 MPCore중 1개의 core만 enable하고 수행하는데
이때의 core id는 선택가능하다.(physical id는 any)

 linux kernel은 초기화를 수행한 boot core를 logical ID 0로 정한다.
smp_setup_processor_id()에서 현재 수행하는 core id를 검사(MPIDR)하여
logical id 0에 mapping 한다.

 현재 threadinfo에 저장된 값은 logical ID로 0이다.
physical id가 필요한 경우 다음과 같은 코드가 사용된다.

  cpu_logical_map(smp_processor_id())

 추가적으로 확인이 필요한 부분은 일부만 초기화하는 global variable의 data를
compiler가 항상 나머지는 0으로 초기화하는 가이다.
일단 gcc에서는 일부만 초기화하는 전역 변수라도 elf상에는
전체 size가 .data 섹션에 만들어지며 초기화된 값 이외에도 0으로 저장되고 있다.

## 어셈블리로 set_bit를 하는 이유가 무엇일까요?
<code>
  .macro bitop, name, instr      
ENTRY(  \name           )
UNWIND( .fnstart        )
        ands    ip, r1, #3     
        strneb  r1, [ip]                @ assert word-aligned           
        mov     r2, #1
        and     r3, r0, #31             @ Get bit offset
        mov     r0, r0, lsr #5 
        add     r1, r1, r0, lsl #2      @ Get word offset
        mov     r3, r2, lsl r3 
1:      ldrex   r2, [r1]       
        \instr  r2, r2, r3     
        strex   r0, r2, [r1]   
        cmp     r0, #0         
        bne     1b
        bx      lr
UNWIND( .fnend          )
ENDPROC(\name           )
        .endm
</code>

함수명 그대로 atomic하게 실행하려고 하려는 것입니다.

## mov를 사용할때 상수값은 8비트만 사용하고, 로테이션 하고 그랬는데,
   실제 필드에서도 그렇게 사용하나요?

대부분의 경우 pseudo instruction을 사용한다.(예: LDR rn, =0xXXXXXXXX)
컴파일러가 알아서 MOV로 풀지 ldr로 가져올지 결정한다.
대부분의 상황에서 cache가 hit되므로 LDR등이 1cycle로 수행가능하다.
cache disabled이고 loop안에서 반복 사용되고 bottleneck이라 성능 최적화가
필요한 경우에나 고민하여 작성한다.

## 나머지 set_cpu_active(), set_cpu_present(), set_cpu_possible()는
   전부 동작이 같습니다.

시스템 상에 존재하는 CPU의 상태 정보는 다음과 같은 4개의 비트맵 (cpumask_t)으로 관리한다.

cpu_possible_mask - 해당 비트에 대한 CPU가 존재할 수 있다.
: 시스템에서 현재 핫플러그(hot plug)가 가능한 CPU들에 대한 비트맵이다.
해당 맵은 부팅시 시스템이 지원할 CPU의 수에 대한 것으로 비트가 설정되면
추가되거나 제거될 수 없다.

cpu_present_mask - 해당 비트에 대한 CPU가 존재한다.
: 시스템에 존재하는 CPU를 나타내는 비트맵이지만, CPU들이 모두 온라인상태는
 아니다. 예를들어, ACPI와 같은 서브시스템에 의해 물리적으로 핫플러그가
 처리될 때 해당 비트가 설정된다.

cpu_online_mask - 해당 비트에 대한 CPU가 존재하며 스케줄러가 이를 관리한다.
: 온라인(사용중인) 되어있는 모든 CPU에 대한 비트들을 1로 설정한 비트맵이다.
 커널 스케쥴링이나 디바이스로부터 인터럽트를 받을 준비가 되어있다면
 해당 비트가 설정된다. 인터럽트를 포함한 모든 OS 서비스가 다른 CPU로
 이동되면 해당 비트는 지워진다.

cpu_active_mask - 해당 비트에 대한 CPU가 존재하며 task migration 시
이를 이용할 수 있다.

리눅스 콘솔에서 cpu에 대한 possible, online, present의 정보는
/sys/devices/system/cpu 정보에 파일을 참조하여 알 수 있다.

drwxr-xr-x  9 root root    0 2013-09-12 15:39 ./
drwxr-xr-x 12 root root    0 2013-09-12 15:39 ../
drwxr-xr-x  7 root root    0 2013-09-12 15:53 cpu0/
drwxr-xr-x  7 root root    0 2013-09-12 15:53 cpu1/
drwxr-xr-x  7 root root    0 2013-09-12 15:53 cpu2/
drwxr-xr-x  7 root root    0 2013-09-12 15:53 cpu3/
drwxr-xr-x  3 root root    0 2013-09-12 15:53 cpufreq/
drwxr-xr-x  2 root root    0 2013-09-12 15:53 cpuidle/
-r--r--r--  1 root root 4096 2013-09-12 15:53 kernel_max
-r--r--r--  1 root root 4096 2013-09-12 15:53 offline
-r--r--r--  1 root root 4096 2013-09-12 15:53 online
drwxr-xr-x  2 root root    0 2013-09-12 15:53 perf_events/
-r--r--r--  1 root root 4096 2013-09-12 15:53 possible
-r--r--r--  1 root root 4096 2013-09-12 15:53 present
-rw-r--r--  1 root root 4096 2013-08-19 11:37 sched_mc_power_savings
 
jin@jin-desktop:/sys/devices/system/cpu$ cat possible 
0-7
jin@jin-desktop:/sys/devices/system/cpu$ cat present 
0-3
jin@jin-desktop:/sys/devices/system/cpu$ cat online
0-3
jin@jin-desktop:/sys/devices/system/cpu$ cat offline 
4-7,8-15