void __init arm64_memblock_init(void)
{
const s64 linear_region_size = BIT(vabits_actual - 1);
/* Handle linux,usable-memory-range property */
fdt_enforce_memory_region();
/* Remove memory above our supported physical address size */
memblock_remove(1ULL << PHYS_MASK_SHIFT, ULLONG_MAX);
/*
* Select a suitable value for the base of physical memory.
*/
memstart_addr = round_down(memblock_start_of_DRAM(),
ARM64_MEMSTART_ALIGN);
physvirt_offset = PHYS_OFFSET - PAGE_OFFSET;
vmemmap = ((struct page *)VMEMMAP_START - (memstart_addr >> PAGE_SHIFT));
/*
* If we are running with a 52-bit kernel VA config on a system that
* does not support it, we have to offset our vmemmap and physvirt_offset
* s.t. we avoid the 52-bit portion of the direct linear map
*/
if (IS_ENABLED(CONFIG_ARM64_VA_BITS_52) && (vabits_actual != 52)) {
vmemmap += (_PAGE_OFFSET(48) - _PAGE_OFFSET(52)) >> PAGE_SHIFT;
physvirt_offset = PHYS_OFFSET - _PAGE_OFFSET(48);
}
/*
* Remove the memory that we will not be able to cover with the
* linear mapping. Take care not to clip the kernel which may be
* high in memory.
*/
memblock_remove(max_t(u64, memstart_addr + linear_region_size,
__pa_symbol(_end)), ULLONG_MAX);
if (memstart_addr + linear_region_size < memblock_end_of_DRAM()) {
/* ensure that memstart_addr remains sufficiently aligned */
memstart_addr = round_up(memblock_end_of_DRAM() - linear_region_size,
ARM64_MEMSTART_ALIGN);
memblock_remove(0, memstart_addr);
}
/*
* Apply the memory limit if it was set. Since the kernel may be loaded
* high up in memory, add back the kernel region that must be accessible
* via the linear mapping.
*/
if (memory_limit != PHYS_ADDR_MAX) {
memblock_mem_limit_remove_map(memory_limit);
memblock_add(__pa_symbol(_text), (u64)(_end - _text));
}
if (IS_ENABLED(CONFIG_BLK_DEV_INITRD) && phys_initrd_size) {
/*
* Add back the memory we just removed if it results in the
* initrd to become inaccessible via the linear mapping.
* Otherwise, this is a no-op
*/
u64 base = phys_initrd_start & PAGE_MASK;
u64 size = PAGE_ALIGN(phys_initrd_start + phys_initrd_size) - base;
/*
* We can only add back the initrd memory if we don't end up
* with more memory than we can address via the linear mapping.
* It is up to the bootloader to position the kernel and the
* initrd reasonably close to each other (i.e., within 32 GB of
* each other) so that all granule/#levels combinations can
* always access both.
*/
if (WARN(base < memblock_start_of_DRAM() ||
base + size > memblock_start_of_DRAM() +
linear_region_size,
"initrd not fully accessible via the linear mapping -- please check your bootloader ...\n")) {
phys_initrd_size = 0;
} else {
memblock_remove(base, size); /* clear MEMBLOCK_ flags */
memblock_add(base, size);
memblock_reserve(base, size);
}
}
if (IS_ENABLED(CONFIG_RANDOMIZE_BASE)) {
extern u16 memstart_offset_seed;
u64 range = linear_region_size -
(memblock_end_of_DRAM() - memblock_start_of_DRAM());
/*
* If the size of the linear region exceeds, by a sufficient
* margin, the size of the region that the available physical
* memory spans, randomize the linear region as well.
*/
if (memstart_offset_seed > 0 && range >= ARM64_MEMSTART_ALIGN) {
range /= ARM64_MEMSTART_ALIGN;
memstart_addr -= ARM64_MEMSTART_ALIGN *
((range * memstart_offset_seed) >> 16);
}
}
/*
* Register the kernel text, kernel data, initrd, and initial
* pagetables with memblock.
*/
memblock_reserve(__pa_symbol(_text), _end - _text);
if (IS_ENABLED(CONFIG_BLK_DEV_INITRD) && phys_initrd_size) {
/* the generic initrd code expects virtual addresses */
initrd_start = __phys_to_virt(phys_initrd_start);
initrd_end = initrd_start + phys_initrd_size;
}
early_init_fdt_scan_reserved_mem();
if (IS_ENABLED(CONFIG_ZONE_DMA)) {
zone_dma_bits = ARM64_ZONE_DMA_BITS;
arm64_dma_phys_limit = max_zone_phys(ARM64_ZONE_DMA_BITS);
}
if (IS_ENABLED(CONFIG_ZONE_DMA32))
arm64_dma32_phys_limit = max_zone_phys(32);
else
arm64_dma32_phys_limit = PHYS_MASK + 1;
reserve_crashkernel();
reserve_elfcorehdr();
high_memory = __va(memblock_end_of_DRAM() - 1) + 1;
dma_contiguous_reserve(arm64_dma32_phys_limit);
}
캐쉬는 메모리 (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 현상이 발생할 수 있다.
64bit architecture address format in cache
이러한 문제가 있음에도 불구하고 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
