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-pop | O | O | O | O |
| thread-jumps | O | O | O | O |
| branch-probabilities | O | O | O | O |
| cprop-registers | O | O | O | O |
| guess-branch-probability | O | O | O | O |
| omit-frame-pointer | O | O | O | O |
| merge-constants | O | O | O | O |
| loop-optimize | O | O | O | O |
| if-conversion | O | O | O | O |
| if-conversion2 | O | O | O | O |
| align-loops | X | O | X | O |
| align-jumps | X | O | X | O |
| align-labels | X | O | X | O |
| align-functions | X | O | X | O |
| crossjumping | X | O | O | O |
| prefetch-loop-array | ? | ? | X | ? |
| optimize-sibling-calls | X | O | O | O |
| cse-follow-jumps | X | O | O | O |
| cse-skip-blocks | X | O | O | O |
| gcse | X | O | O | O |
| gcse-lm | X | O | O | O |
| gcse-sm | X | O | O | O |
| gcse-las | X | O | O | O |
| expensive-optimizations | X | O | O | O |
| strength-reduce | X | O | O | O |
| rerun-cse-after-loop | X | O | O | O |
| rerun-loop-opt | X | O | O | O |
| caller-saves | X | O | O | O |
| force-mem | X | O | O | O |
| peephole2 | X | O | O | O |
| regmove | X | O | O | O |
| strict-aliasing | X | O | O | O |
| delete-null-pointer-checks | X | O | O | O |
| reorder-blocks | X | O | O | O |
| reorder-functions | X | O | O | O |
| unit-at-a-time | X | O | ? | O |
| schedule-insns | X | O | O | O |
| schedule-insns2 | X | X | X | O |
| schedule-interblock | X | O | ? | O |
| sched-spec | X | O | ? | O |
| inline-functions | X | X | X | O |
| rename-registers | X | X | X | O |
| web | X | X | X | O |
| unswitch-loops | X | X | ? | 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속성은 특징은 다음과 같습니다.
동일한 매개변수를 사용하여 여러번 호출하는 경우 매번 같은 값이 반환되어야 함.
설사 동일한 값이 반환되더라도, 내부적으로 어떤 값을 변화시켜서는 안됨. (정적 변수라던지, 포인터 매개 변수를 통해 포인터가 가리키는 값을 수정한다던지.... 전역 변수를 수정한다던지...)
당연히 내부적으로 순수하지 않는 함수를 호출하면 안됨. 특히 수학 함수 같은 경우가 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한 함수에 동일한 인자값이 전달되는 경우 여러 곳에서 다수로 호출될지라도 그 결과값은 동일할 거구요. 결국, 컴파일러는 내부적으로 그 함수를 한번만 호출하고 결과값을 재사용하도록 코드 최적화를 하는 것입니다.
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가지 경우가 있다.
- 4 way 16kB cache의 경우: 즉 1 way가 4kB. 4kB는 page frame 단위로 그 범위 안에서는 PA=VA이다. 즉 virtual index와 Physical index가 동일하므로 PIPT와 동일하게 동작한다.
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가지가 문제다.
- 일반적인 2 level 혹은 3 level descriptor의 경우 2단게 혹은 3단계의 lookup을 반복
- TLB hite rate
해결방안은 아래와 같다. 1A. 1.은 보통 최종단계의 translation 결과를 저장하여 해결한다. 2A. TLB miss의 경우 memory read로 인해 latency가 길어지므로 TLB의 크기를 늘려 hit rate를 증가
1A는 2A의 필요성을 더 크게 한다. 문제는 물리적인 제약상 메모리는 크기가 클수록 접근시간이 느려진다는 점이다.
이를 극복하기 위해 L2상위에 L1 캐시를 도입한 것 처럼 full TLB 앞단에 uTLB를 도입하여 latency를 최소화한다.
