몰랐거나, 알고싶지 않았던 것들

이 글에서는 캐쉬의 주소 변환 과정의 종류 그리고 각 종류의 장단점과 ARM architecture에서는 어떻게 그 단점들을 보완하고 있는지 알아보겠다.

캐쉬는 메모리 (DRam) 접근이 CPU의 속도에 비해 너무 느리기에 그 시간을 단축하기 위해서 만든 하드웨어이다. 위 그림과 같이 주소와 그에 상응하는 데이터를 저장하고 CPU의 메모리 읽기, 쓰기 처리 속도 향상에 아주 큰 1등 공식 하드웨어이다. 사실 캐쉬에 대해서 설명하려면

• Full associative, Set-way associative
• Eviction Policy (LRU)
• Data fetch algorithm (Spacial and Tempral Locality)
• etc

이와 같은 내용들을 모두 설명해야 하지만, 이 글에서는 Cache에서 주소 관리 방법에 따른 특징들에 대해서 알아보겠다.

컴퓨터에서 주소라하면 가상 주소 (Virtual Address) 와 물리주소 (physical Address)가 있다. 위 그림에서도 주소라는 말만 있을 뿐, 가상 주소와 물리 주소 중 어떤 것을 주소로 사용하고 있는 지에 대한 설명은 빠져있다. 그 이유는 사실 Cache를 만드는 사람이 원하는데로 만들면 되기 때문이다. 그러나 물론 산업에서 주로 사용하는 주소는 정해져있다. 이제부터 어떤 주소를 사용하면 어떤 특징이 있는지, 그리고 내가 주로 일하는 ARM architecture에서는 어떠한 방법으로 주소를 관리하고있는지에 대해서 알아보겠다. 

캐쉬에서 주소를 사용하는 방법은 가상주소만을 사용할 수도 있고, 물리주소를 사용할 수도 있고 또는 혼용해서 사용할 수 있다. 이 조합으로 알아보면:

• PIPT: Physical Indexed Physical Tagged
• VIVT: Virtual Indexed Virtual Tagged
• VIPT: Virtual Indexed Physical Tagged
• PIVT: Physical Indexed Virtual Tagged

이렇게 크게 4가지의 주소 변환 방법이 있다. Indexed와 Tagged는 위 그림에서 보이는 Tag와 Index를 의미하는 것으로 가상주소나 물리주소의 일부분을 가져와 Tag 또는 Index로 사용하는 것을 뜻한다.

조금 귀찮아져서 공부한 내용을 간략히 정리해보면:

• PIPT: 문제 없이 항상 사용할 수 있지만 성능이 조금 느리다
• VIVT: MMU (TLB) 접근을 하지 않아도 되서 빠르다. 하지만, synonym[1]과 homonym[2] 문제가 생긴다
• VIPT: PIPT와 VIVT의 장점을 가지고 있다. synonym과 homonym의 문제를 어느정도 해결한다
• PIVT: 성능은 PIPT 처럼 느리고, synonym과 homonym문제도 그대로 갖고 있어 사실 사용하지않는다

[1] synonym: 하나 이상의 가상 주소가 하나의 물리주소와 매핑되는 문제, 예를 들어 mmap API를 통해서 여러 가상 주소가 하나의 물리 주소에 매핑 횔 수 있게 된다.

[2] homonym: 하나의 가상 주소가 여러 물리주소와 매핑 되는 문제, 예를 들어 A 쓰레드가 context-out되고 B쓰레드가 context-in 되었을 때, A쓰레드가 사용하던 data (가상 주소 0xFFFF_0000에 해당하는)가 캐쉬에 남아있고, B 쓰레드가 0xFFFF_0000에 해당하는 data 를 사용하면 B는 원치 않는 data에 접근하게 된다. 이는 context-switch 할 때, cache clean&invalidation을 통해서 해결할 수 있다.

사실 homonym 문제는 context-switch 할 때 cache operation을 통해서 극복이 가능하므로 문제가 없다. 하지만 synonym의 경우는 cache operation을 통해서 극복이 불가하다.

VIPT 에서 synonym 문제와 그에 해결 방법

64비트 아키택쳐를 기준으로 가상 주소는 64비트를 가지고 있고 아래와 같은 형식으 캐쉬에서 사용된다고 해보자.

이 때, Tag (물리주소로 부터 가져온) 와 Index (가상주소로 부터 가져온) 사이에 겹치는 비트들이 있으면, 그 비트의 2제곱승 만큼 synonym 현상이 발생할 수 있다.

이러한 문제가 있음에도 불구하고 index 비트를 Tag와 겹치면서 까지도 늘리고 싶은 이유는 cache의 총 크기를 늘리기 위해서이다 (cache total size = Page size * # of associatives). 따라서 synonym 현상을 피하기 위해서 운영체제에게 cache coloring [3] 을 통해 극복하게 하거나 Tag와 Index간의 겹치는 부분을 없애므로써 해결할 수 있다.

[3] 간단히 말해, overlapped 된 비트에 대해서 가상 주소와 물리 주소를 같에 할당하는 것이다.

ARM 아키택쳐에서는 Hardware 내부적으로 해결하는 모습을 보이고 있다. 사실 어떻게 이 문제를 해결하는지는 모르지만, Manual 에서 찾아보면 어떤 cache type이든 간에 PIPT의 동작이 똑같음을 보장해 준다고 한다. 뇌피셜로는 아마 Cache access할 때 다른 cache-line간의 look-up을 통해 해결하고 있을 것 같다 (그게 아니면 사실 해결 방법이 따로 있어 보이지는 않는다).

Computer Science에서 atomic operation 이라는 용어는 상당히 자주 접한다.

Wikipedia 에서 atomic [1] 을 찾아보면  Linearizability [2] 이라는 페이지로 redirection 해준다.

그리고 [2] 에서 내용을 (내 마음대로) 해석해보자면:

Multiprocessor system에서 여러 CPU들이 공유자원 (특히 메모리)에 접근 할 때, 접근 순서를 의도적 또는 비 의도적으로 직렬화하여 의도치 않는 결과를 피하는 operation 을 atomic operation이라 한다.

사실 atomic 이라는 뜻만 보면 원자처럼 쪼개질 수 없는 연산 또는 수행 이라고 할 수 있지만 Computer science에서는 단순히 원자처럼 작은 단위라는 뜻 말고도 Mutual Exclusive 의 의미도 포함하고 있는 것이다.

이 글에서는 ARM architecture에서 어떻게 atmoic operation을 지원해주고 있는지 알아볼 것이다.

ARMv8에서는 아래와 같은 방법으로 atmoic operation을 지원하고 있다.

• Load-Exclusive/Store-Exclusive instructions

• Atomic instructions

  • Atomic memory operation

  • Swap

  • Compare-and-Swap

Load-Exclusive/Store-Exclusive instructions

Load-Exclusive/Store-Exclusive 명령어는 ARMv8 Reference Manual [3] [4] 에 이렇게 설명되어 있다:

The Load-Exclusive instructions mark the physical address being accessed as an exclusive access. This exclusive access mark is checked by the Store-Exclusive instruction, permitting the construction of atomic read-modify-write operations on shared memory variables, semaphores, mutexes, and spinlocks.

해석해보자면, LDREX 명령어를 통해 메모리에서 Register로 data를 읽어오면, 해당 메모리 block (block의 size는 implementation defined이지만 B.2.9.3, Marking and the size of the marked memory block 에 설명 되어 있다)은

mutual exclusive하게 access 되어야 하는 메모리이다" 라고 표시가 되고, 정말 mutual exclusive하게 access가 되었는지는 STREX 명령어를 실행 할 때, 검증된다는 내용이다.

사실 우리가 메모리에서 어떤 주소의 값을 읽어오는 이유는 그냥 값을 확인할 수도 있겠지만, 대부분 읽어와서 그 값을 수정하여 다시 그 메모리에 쓰는 경우가 많고 그 행위를, read-modify-write operation 이라고 부른다. 이 때, read-modify-write 이 3개의 operation을 하나의 atomic하게 수행할 수가 없으니, write할 때, 이 모든 수행이 atmoic (다르게 말하면 mutual exclusive) operation 으로 성공했는지 아니면 실패 했는지 알려준다는 것이다. 그러므로 LDREX 와 STREX 명령어 두개는 항상 하나의 쌍으로 불려야 한다.

이 때, LDREX 명령어에 대해서 좀만 자세히 말하자면, LDREX 는 해당 메모리 블럭에 기존에 있는 TAG를 지우고 새로운 TAG (다른 CPU에서 만들어 놓은 TAG는 지우고, 지금 LDREX 명령어를 수행하고 있는 CPU만을 위한 TAG)를 남겨 놓는다. 따라서 LDREX를 마지막에 수행하는 CPU가 결국 해당 STREX를 성공할 수 있고, 전에 TAG를 만들어 놓은 CPU에서는 STREX 명령어를 실패 하게 되는것이다.

위 그림을 보면, CPU0가 먼저 LDREX 명령어를 수행해서 해당 메모리 block에 TAG를 생성해 놓았다. 그 다음에 CPU1에서 TAG를 생성하면서 기존에 다른 CPU를 위한 TAG는 지운다. 따라서 CPU0 의 STREX 명령어는 실패하고, CPU1의 STREX명령어만 성공하게 되어 shared object (memory)를 여러 CPU들로부터 atomic operation을 보장 할 수 있게 된다. 그러면 CPU0 입장에서는 STREX 명령어가 실패했음을 알고, 다시 LDREX부터 수행하거나, 나중에 하거나 등 결정 하면 된다 (소프트웨어를 어떻게 디자인했느냐에 따라 달라질 것).

그리고 ARMv8 Manual에서도 이러한 atmoic operation support를 통해 아래와 같은 simple lock sample code를 제공하고 있다:

<LOCK>

Px
	SEVL
 	; invalidates the WFE on the first loop iteration
	PRFM PSTL1KEEP, [X1]
 	; allocate into cache in unique state
Loop
	WFE
	LDAXR W5, [X1] 	; read lock with acquire
	CBNZ W5, Loop 	; check if 0
	STXR W5, W0, [X1] 	; attempt to store new value
	CBNZ W5, Loop 	; test if store succeeded and retry if not
	; loads and stores in the critical region can now be performed
    
<UNLOCK>
Px
	; loads and stores in the critical region
	STLR WZR, [X1] ; clear the lock

Atomic instructions

ARMv8.1 버전부터는 FEAT_LSE2, Large System Extensions v2 이라는 기능이 추가되었고, ID_AA64MMFR2_EL1.AT register를 통해 이 기능이 구현되어있는지 확인 할 수 있다. 이 기능으로 Hardware 적으로 Atomic operation을 지원하게 되었다. 일단 이 기능의 원리를 이해하려면 Load-Acquire 그리고 Store-Release 라는 ARMv8의 메모리 접근 Concpet에 대해서 이해할 필요가 있다.

• Load-Acquire
• Store-Release

간략히 설명하면, LDR 또는 STR 명령어를 수행하면서 자동적으로 memory barrier를 수행하여, 개발자로 하여금 DMB instruction을 고려하지 않아도 되도록 만든 개념이다.

또한 기존에 atomic operation을 구현하기 위해 등작하였던 Read-Modify-Write operation을 하나의 명령어로 만들었다는 것을 알고 있어야 한다.

Atomic memory operation

• LDADD: atomic add instruction w/o Acquire nor Release
• LDADDA: atomic add instruction with Acquire
• LDADDAL: atomic add instruction with Acquire and Release
• LDADDL: atomic add instruction with Release

Swap

• SWP: swap instruction w/o Acquire nor Release
• SWPA: swap instruction with Acquire
• SWPAL: swap instruction with Acquire and Release
• SWPL: swap instruction with Release

CAS (Compare-and-Swap)

• CAS: CAS w/o Acquire nor Release
• CASA: CAS with Acquire
• CASAL: CAS with Acquire and Release
• CASL

[1] en.wikipedia.org/w/index.php?title=Atomic_(computer_science)&redirect=no

[2] en.wikipedia.org/wiki/Linearizability

[3] ARM DDI 0487F.c, ID072120, C.3.2.5, Load/Store unprivileged

이번에는 primary_entry함수 안에 있는 set_cpu_boot_mode_flag 함수에 대해서 알아보겠다.

/*
 * Sets the __boot_cpu_mode flag depending on the CPU boot mode passed
 * in w0. See arch/arm64/include/asm/virt.h for more info.
 */
SYM_FUNC_START_LOCAL(set_cpu_boot_mode_flag)
	adr_l	x1, __boot_cpu_mode
	cmp	w0, #BOOT_CPU_MODE_EL2
	b.ne	1f
	add	x1, x1, #4
1:	str	w0, [x1]			// This CPU has booted in EL1
	dmb	sy
	dc	ivac, x1			// Invalidate potentially stale cache line
	ret
SYM_FUNC_END(set_cpu_boot_mode_flag)

일단 이 함수는 w0에 (첫번째 register를 의미하며, 32bit만 읽고 싶을때는 w0, 64bit를 모두 읽고 싶을 때는 x0로 읽어 올 수 있다.) 현재 CPU에서 동작하는 Exception Level이 인자로 전달되었다고 가정한다.

결론 부터 이야기 하면 이 함수의 목적은, 커널이 소유하고있는 CPU들이 같은 Exception Level에서 부팅되었음을 확인하고자 만들어졌으며, 알고리즘은 쓰고 같은지 확인 이다.

__boot_cpu_mode 배열은 아래와 같이 선언되었다고 했을 때, 이 함수를 수행하고 있는 CPU가 EL1에서 booting되었다고 한다면, 함수는 아래 배열에서 첫번째 index에 BOOT_CPU_MODE_EL1 값을 쓸 것이며, 결과로는 배열의 element들이 모두 같은 값을 갖게 될 것이다. 반대로 CPU가 EL2에서 booting되었다고 한다면, 함수는 아래 배열에서 두 번째 index에 BOOT_CPU_MODE_EL2 값을 쓸것이고, 배열의 모든 element들이 모두 같은 값을 갖게된다.

/*
 * We need to find out the CPU boot mode long after boot, so we need to
 * store it in a writable variable.
 *
 * This is not in .bss, because we set it sufficiently early that the boot-time
 * zeroing of .bss would clobber it.
 */
SYM_DATA_START(__boot_cpu_mode)
	.long	BOOT_CPU_MODE_EL2
	.long	BOOT_CPU_MODE_EL1
SYM_DATA_END(__boot_cpu_mode)

이는 boot CPU 이후에 secondary CPU들에 대해서도 booting exception level에 따라 배열의 element에 값을 쓰고 배열의 element들이 같은 값을 유지하고 있는지 여부에 따라 모든 CPU들의 booting exception level들이 같은 level에서 부팅되었는지 다른 level을 갖고 부팅 되었는지를 확인할 수 있게 된다.

• dc ivac, x1:이 함수가 호출 되었을 때는 아직 CPU의 dcache가 활성화 되어있지 않은 상태로써, dcache에 배열의 주소에 해당하는 data가 있다면 나중에 예기치 못한 상황이 생길 수도있어서, 해당 배열에 대해서 dcache invalidation operation을 해주고 있다.