Virtually mapped kernel stacks


Original link: http://lwn.net/Articles/692208/


Linux Kernel "Stack"은 시스템 설계에서 거의 틀림없이 약점일 것이다: Stack 의 크기는 충분하지만 작은 크기를 갖기 때문에 Kernel 개발자들은 Stack overflow 를 피하기위해 끊임없이 그들이 stack 에 무엇을 넣든 주의해야 한다. 이런 상황을 만들려는 공격자가(attacker) 없어도 overflow 의 이슈는 생기기 마련이다. 그리고, Jann Horn 의 최근 데모를 보면, 왜 attacker 가 이런 시도를 하는지에 대한 이유들이 있다. When an overflow does occur, the kernel is poorly placed to even detect the problem, much less act on it. Linux Kernel Stack은 현재까지 개발되면서 아주 적은 변화만 있었지만, 최근의 변화는 잠재적으로 kernel stack 을 더욱더 견고하게 만들어 줄 가능성이 있다.


How current kernels stack up


각 프로세스는 kernel 에서 수행될 때 자기 자신 만의 stack 을 갖고 사용한다; 현재 kernel stack 의 크기는 8KB 나 16KB (64bit system)이다. Stack 은 "Direct-Mapped Kernel Memory" 에 있고 당연히 물리적으로 연속적인 공간을 이용한다. 이 요구사항은 시스템을 오래 운영하면서 memory fragmentation 때문에 연속적인 2 개 혹은 4 개의 page을 찾는 것은 어렵기 때문에 문제가 될 수 있다. Direct-Mapped memory 영역의 사용은 stack overflow 를 막기 위해 접근허용이 안되는 memory page(guard page) 의 사용으로 실제 사용되는 메모리 page 를 낭비하는 것이다.


결과적으로, 만약 Kernel 이 overflow 되려고 하는 시점에는 어떠한 조짐을 받을 수 없다. 대신에, 하나의 stack 이 메모리으 위치가 어디가 되었던 간에 할당된 영역 아래로 계속 overwrite를 하게 된다.(stack 의 특성상 큰 주소 번지에서 작은 주소 번지로 자란다.) 그러나 만약 stack overflow 가 production system에서 검출이 된다면, 이미 알수 없는 많은 데미지를 입은 상태일 것이다.(But if a stack overflow is detected at all on a production system, it is often well after the actual event and after an unknown amount of damage has been done.)


재미난 것이 하나 더 있다면, Kernel stack 맨 바닥에는 thread_info 라는 중요한 구조체가 있다. 그래서 만약 kernel stack 이 overflow 가되면, thread_info( kernel의 모든 것이라고 할 수 있는 현재 실행되는 프로세스에 관한 것을 알수 있는 정보에 접근) 가 제일 먼저 overwrite 될 것이다. stack 의 대부분이 어떤 것이 들어가 있는지 알수 없지만, thread_info는 너무나 유명한 것이니 attacker 들이 관심있어 하는 정보일 것이다.


kernel 개발자들은, 당연한 얘기 겠지만, stack overflow 를 피하기 위해 애쓰고 있다. stack 에 할당은 일발적인 rule 에 따라 실험되고, 재귀(recursion)은 허용하지 않는다. 하지만 놀라운것은 별로 관심도 없던 변수 선언에 의해 기대하지 않았던 호출 chain 이 형성되는 경우가 발생한다. (But surprises can come in a number of forms, from a careless variable declaration to unexpectedly deep call chains.) storage system (filesystem) 과 networking code 는 독단적인 depth를 가지고 stack을 쌓을 수 있어서 이런 문제를 쉽게 가질 수 있다.(The storage subsystem, where filesystems, storage technologies, and networking code can be stacked up to arbitrary depths, is particularly prone to such problems.) 3.15 release 를 위해 x86-64 kernel 의  stack 을 16KB 로 확장 하게 이끈것도 이 때문이다. 그러나 얼마나 stack 이 더 커질수 있는지에 대한 제한은 있다. 시스템에서 모든 process를 위한 하나의 stack 이 있는 이후로, 이런 증가는 여러번 일어 날 수 있을 것입니다.


stack overflow 문제를 회피하는 문제는 여전히 kernel 개발자 들에게 도전으로 남아 있다. 하지만, 그것은 overflow가 발생했을 때, Kernel이 더 나은 응답성을 가질 수 있도록 하는 가능성이 될 수 있다. 이런 가능성을 높이기 위한 가장 중요하게 진행할 수 있는 것은 Andy Lutomirski 의 Virtual mapped stacks patch set 으로 kernel의 stack 메모리 할당 방식의 변경이 될 수 있다. 


Virtually mapped stacks


대부분의 memory 는 directly mapped memory 영역으로 kernel에 의해 직접적으로 접근이 가능하다. 그 영역은 간단하고 모든 실질적인(?) 목적을 위해 선형적으로 물리 memory 를 mapping 한 주소공간이다. 이것은 마치 물리 memory 를 갖고 kernel 이 수행하는 것처럼 보일 수 있다. 64 bit 시스템에서는 모든 메모리가 이런 방법으로 접근 가능하다. 하지만 32bit 시스템은 모든 물리 memory 를 direct 접근을 할 수가 없다.(알겠지만, 32 bit 리눅스 커널의 가상 주소 공간은 4G 이며, 대게는 kernel 의 공간으로 1G를 사용한다. 이중 16MB 는 DMA, 896MB 은 direct mapped, 128MB 는 highmem 으로 사용된다. 그래서 최대 direct access 가 가능한 영역은 896MB 이다. 하지만 64 bit system에서는 현재 H/W 에 붙일수 있는 최대 크기의 memory 를 highmem 영역없이 접근가능하다.)


Linux 는 directly mapped 공간 뿐만 아니라 실제 physical memory 에 접근하기 위해 가상 주소를 사용하는 virtual memory system 이 있다. 그런 접근이 발생하면, Kernel은 가상으로 mapped 된 memory 를 위한 주소공간을 만든다. 이 공간은 vmalloc() 이 호출되었을 때 생기며, 이를 "vmalloc range"라 부른다. 실제 가상 주소 공간은 연속적이지만 물리적으로는 연속적이지 않다. 전통적으로 이 영역의 사용은 아주 큰 공간이 필요할 때 사용되며 가상적으로 연속적이지만 물리적으로 흩어져 있는 것을 허용할 때 이용된다.


Kernel stack 은 물리적으로 연속적일 이유가 하나도 없다. 각각의 page들이 vmalloc 영역에 mapping 되어 사용될 수 있다는 것이다. vmalloc 영역을 이용하는 것은 kernel 내에서 물리적으로 연속적인 큰 공간을 할당받아 사용하는 것 중에 하나를 제거할 수 있다는 것이고, memory fragmentation 이 많이 생겼을 때, 시스템을 안정적으로 만들 수 있다는 것이 장점이다. 이것은 또한 할당된 stack 을 보호하기 위해 낭비되는 메모리 없이 접근 불가능한 영역을 만들 수 있고, 만약 할당된 stack 영역을 넘어서는 접근이 있을 경우 Kernel이 즉각적으로 반응하여 처리 할 수 있다는 것이다. Andy 의 patch는 단지 kernel stack을 vmalloc 영역으로 부터 할당 받는 것이다. 또한 그는 이 patch 를 만들면서, 멋진 overflow handler 를 추가했다. 이는 oops 메세지 없이 overflow 를 만든 process를 죽이도록 하는 것이다.


이 patch set 자체는 아주 간단하다. 물론 architecture 의존적인 부분이 있긴 하지만, 이는 kernel의 안정성을 향상 시키며 reviewer 들도 긍정적으로 검토 중이다. 


Inconvenient details


vmalloc 영역에서 할당받은 stack 은 약간은 성능의 문제가 있다. Andy의 말에 따르면, clone()으로 생성되는 새로운 process 만드들때, 1.5µs 정도 더 걸린다. process-creation overhead 와 같은 작업들은 이 변경으로 인해 고통(?)받는 민감한 작업이다, 그래서 Linus 는 "이 변경이 적용이 되기전에 이 문제는 고쳐질 필요가 있다." 라고 했다. Andy는 이와 같은 문제는 vmalloc() 을 성능개선하여 고쳐질 수 있다고 생각한다.(vmalloc() 여지껏 성능에 관련해서 최적화하는 작업이 거의 이루어지지 않았다). 대신, Linus는 이것을 작게 유지하고 미리할당된 stack의 per-CPU cache 를 유지할 것을 제안했다. 그는 변경이 적용되기 전에 성능에 대한 regression 은 명확히 짚고 넘어가야 한다고 말했다.


다른 잠재적인 비용은 "translation miss" 증가에 대한 측정이 이루지지 않았다는 것이다.(page fault?) Direct mapped 영역을 사용하는 것은 huge-page mapping을 사용하는 것인데, 이는 전체 커널이(code, data 그리고 stack 을 포함하여) single TLB(Translation lookaside buffer) entry 로 맞춰 질 수 있다는 것이다. 하지만, vmalloc 의 경우 single-page mapping 을 이용하여 메모리내에 다른 window(?)를 생성한다. 그래서 kernel stack(direct mapped)의 접근은 일반적인 것이기 때문에, stack 이 만약 vmalloc 영역을 통해 접근한다면, TLB miss 의 증가의 가능성을 가질 수 있다.


또 다른 중요한 작은 세부사항은 guard page 를 포함한(물론 이 page 들은 할당 이후에 생성) vmalloc area 로 부터 받는 것이다. 일반적인 heap memory 는 쉽게 overrun이 발생할 수 있다. 하지만 stack은 작은 주소 방향으로 자란다는 것이고, overrun은 앞서 할당된 영역에 덮어쓰기를 한다는 것이다. 실제로는, vmalloc 영역의 앞부분에 guard page 가 위치 할 수만 있다면, 현재의 변경되는 코드는 overrun에 대한 guard page 로 부터 앞뒤로 잘 사용될 수 있도록 보장될 수 있을 것이다. 하지만 이와 같은 guard page 는 이 patch set 의 주요한 목표 중 하나이다. 


vmalloc 범위안에서 memory mapped 는 명확한 제약사항이 있다. 그것을 Direct Memory Access(DMA) I/O를 위해 쉽게 사용되어 질 수 없다. 이런 I/O는 메모리가 물리적으로 연속적이길 기대하고 있으며, 그리고 virtual-to-physical mapping address 함수는 이런 기대를 맞춰줄 수 없다. Kernel에서 stack로 부터 DMA를 수행하는 시도를 위한 코드는 없기 때문에 이것은 문제가 되지 않는다. stack 으로 부터 DMA 운영은 다른 이유들로 문제가 있다. 하지만 그런 코드들이 커널내에 어째든 운영이 된다는 것이다.(? - 이런 시도는 없다고 하지 않았나?) virtually mapped stack patch가 널리 이용이 된다면 정리되어야 하는 코드가 될 것이다.


마지막으로, 이 패치를 적용한 커널은 kernel stack 의 overflow 를 검출할 수 있도록 할 수 있다. 하지만 그것은 각 kernel stack의 맨 아래에 살고(?) 있는 thread_info에 작은 문제가 여전히 있다. 전체 stack을 overrun 하지 않는 선에서 이 구조체를 덮어쓰는 overrun은 발견되지 않을 것이다. 이것에 대한 알맞은 해결잭은 thread_info 구조체를 kernel stack으로 부터 멀리 떨어뜨려 이동해야 하는 것이다. 현재 이 패치를 그렇게 하지 않았는데, Andy 는 현재 이 패치가 적용되고 나면 생각해 본다고 말했다.


이 패치는 적용은 현재 문제들을 적절히 처리 할 수 있을 것 같아보인다. kernel은 stack overrrun에 대한 처리 및 발견이 가능하고 Linux system을 더욱더 견고하게 할 것이다.

'Linux Kernel Study > Linux Weekly News - 번역' 카테고리의 다른 글

Extended system call error reporting  (0) 2015.11.27
[LWN] A taste of Rust  (0) 2013.04.27
[LWN 번역] Memory Compaction  (0) 2012.11.01

Extended system call error reporting


the original link : https://lwn.net/Articles/657341


Kernel 과 User 영역 사이에 Interface 의 복잡도는 굉장이 높다. H/W 설정, 프로세스 상태 등의 자세한 정보를 어느 방향으로든 전달해주는 많은 task 들이 있다. 그런 task 들이 많기는 하지만, 뭔가 잘못 진행되는 경우 단지 integer 의 error code 만을 보여주기 때문에 종종 개발자들이 그것이 무엇이 잘못된 것인지 알아내기가 어렵다. 과거에도 그런 error-reporting 을 위해 다양한 제안히 있었다; 마지막 제안은(Alexander Shishkin) 이전 제안에 비해 많이 나아지질 않았으나 이 문제에 대해 나아가야 할 만한 포인트를 보여줬다.


예를 들어, Media subsystem 에 의해 제공되는 VIDIOC_S_FMT ioctl() 을 고려해보자. VIDIOC_S_FMT 는 capture 장치(카메라와 같은)로 부터 user 영역으로 Image 들의 포멧 정보를 설정하는 ioctl 이다. (http://linuxtv.org/downloads/v4l-dvb-apis/vidioc-g-fmt.html) 이런 가능한 이미지 포멧정보는 놀랍도록 다양하고 User 영역에서 연관된 파라미터와 함께 Kernel 로 포멧 디스크립션을 넘기도록 하고 있다. 이런 디스크립션 정보의 조합에 의한 문제가 발생할 수 있는데 이때, User 는 단지 VIDIOC_S_FMT 실패로 EINVAL 의 error code 만을 받게 될 것이다. 물론, kernel 은 무슨일 있었는지 알고 있지만, user 영역과 그 지식(?)을 공유하는 방법은 없었던 것이다.


이 문제는 고치는 것은 쉽지 않다; errno 매커니즘은 명백히 부족함을 느낀다. 그렇지만 Unix 전통적으로 오랫동안 사용되어 왔고 이것을 바꾸기엔 쉽지 않을 것이다. 그래서 어떤 확장된 error 정보를 잘 넘겨줄 수 있는 새로운 채널이 있어야 할 것이다. error 정보를 자세히 하여 전달하도록 kernel 에 추가하는 작업은 조심스럽게 이루어져야 한다. 이유는, kernel 의 중요한 기능을 느리게 한다던가 과도한 error 메시지 설정으로 소스의 흐름을 방해하는 것 등이다. Alexander 의 패치는 이런 두가지의 경우를 모두 만족하도록 설계되었다. 


error reporting 의 매커니즘을 잘 설명한 예제가 있다. Alexander 의 패치는 perf_event_open() 시스템 콜을 목표로 삼았다. 그것은 파라미터로 perf_event_attr 구조체를 받는데, 이 구조체는 event 캡쳐를 위해 설정해야 하는 파라미터 셋 들이 엄청나게 많이 있다. 이로 인해 이 system call의 운영은 잘못될 가능성을 갖고 있게 된다.


Describing errors


첫번째로는 error site 를 표현하는 구조체를 만들어야 한다. 그 구조체는 error 가 발견되고 user 영역으로 넘겨줄 수 있는 위치어야 한다. 그 구조체는 ext_err_site 구조체인 site 변수를 갖고 있어야 한다. 이 변수는 error 에 대한 전체적인 사항을 보고 할 수 있도록 어떤 정보든지 갖고 있을 수 있다. perf 의 경우에 이 구조체는 아래와 같이 생겼다.

    #include <linux/exterr.h>

    struct perf_ext_err_site {
	struct ext_err_site	site;
	const char		*attr_field;
    };

attr_field 멤버 변수는 error 가 생긴 struct perf_event_attr 내부의 field 의 이름을 갖고 있도록 한다.


그리고 나서, user 영역으로 넘겨질 이 구조체의 어떤 추가적인 정보를 담는 문자열을 넘겨줄 수 있는 함수를 정의할 필요가 있다. perf 버전에서는 :

    static char *perf_exterr_format(void *site)
    {
	struct perf_ext_err_site *psite = site;

	return kasprintf(GFP_KERNEL, "\t\"attr_field\": \"%s\"\n",
			 psite->attr_field);
    }

이 함수는 동적으로 할당된 문자열을 반환한다; 확장된 error reporting 구조에서 이 문자열이 더이상 필요없을때 할당 해제를 자동으로 한다.


이 두 코드 조각을 적절히 위치 시키면, 특정 error class 를 처리할 수 있는 "error domain"을 정의할 수 있게 된다. perf 의 경우를 보자

    DECLARE_EXTERR_DOMAIN(perf, perf_exterr_format);

error 정보를 실질적으로 보고하는 것은 ext_err() macro를 통해 완성된다. 실제 사용자는 wrapper 를 통해 사용할 수 있을 것이다. 어떻게 만들어 졌는지 perf code를 보자:

    #define perf_err(__code, __attr, __msg)				\
	({ /* make sure it's a real field before stringifying it */	\
	    struct perf_event_attr __x; (void)__x.__attr;		\
	    ext_err(perf, __code, __msg, 				\
	        .attr_field = __stringify(__attr));			\
	})

ext_err() 의 파라미터 들은 위에서 정의된 domain (error code, user 영역에 전달될 메시지)이다. 그리고 error-site 구조체의 나머지를 초기화된 문자열을 설정(set)한다. 이 경우, ext_err() 의 마지막 파라미터는 잘못된 속성으로 설정된 perf_ext_err_site 구조체의 이름을 attr_field 에 넣는다. 이 패치를 보면 peft_err() 매크로가 어떻게 실행되는지 볼 수 있다.


또 다른 중요한 세부 내용이 있다. 하나는 EXTERR_MODNAME 심볼인데 이것은 ext_err() 이 불리기 전에 반드시 set되어 있어야 한다.

    #define EXTERR_MODNAME	"perf"

다른 하나는 ext_err() 는 함수 파라미터로 넘어온 error 코드를 변경하여 값을 반환한다. 이 코든는 kernel 이 알고있는 모든 확장된 error 에 대한 설명이 되어 있는 ext_err_site 구조체의 index 라 보면 된다. 일반적인 방법으로는 user 영역에 반환하기 위해서 아래와 같이 사용한다.

    return ext_err_errno(code);

ext_err() 가 변환한 코드는 application 이 무슨 의미인지 알수 없기 때문에 user 영역에 직접적으로 전달되지는 않는다. 그래서 원래 error code 는 ext_err_errno() 를 호출하지 않고 반환되어서는 안된다. 이런 호출은 확장된 error 정보를 kernel 이 다 기억을 해야한다는 조건이 성립해야 한다. 간략하게 말하면, 새로운 ext_err_code 라 불리는 field 를 새로운 task_struct 내부에 있도록 해야 한다. 그래서 ext_err_errno() 의 호출은 그 field 에 위치한 특별한 error code를 바라보도록 해야 한다는 것이다. 만약 확장되기 이전 error code를 ext_err_errno() 에 넘기게 되더라도 정상동작할 것이며 그것은 안전하게 기존과 확장된 error code 모두를 지원할 것이다.


The user-space side


kernel은 user 영역에 확장된 error 메시지를 알려줄 준비가 다 되어 있지만, system call 로 부터 반환된 값을 여전히 예전 errno를 사용하는 경우가 많을 것이다. 만약 application 에서 더 많은 정보를 원한다면, 아래 처럼 사용하면 된다.

    char message[SIZE];

    len = prctl(PR_GET_ERR_DESC, message, SIZE);

반환 값을 기존 메시지와는 다를 것이다. JSON 포멧으로 에러가 발생된 곳의 file 과 line, error 코드, 모듈 이름, 실제 메시지 그리고 앞서 설명한 domain format 함수에 의해 추가된 정보를 줄 것이다. 이 변경으로 user 영역에 perf tool 에 JSON parser 를 사용하여 메시를 잘 분리하여 적절히 분석 가능할 것이다. prctl() 호출은 kernel 영역에서 error 정보를 지울 것이며, 다시 호출한다면 아무런 data를 받을 수 없을 것이다.


이 패치는 review 커멘트가 많이 보이지는 않는다. 끝으로 error 보고 문제는 많은 개발자가 인지하고 있으며, 이것을 고치기 위해 몇몇은 노력까지 한다. 그리고 커널로 부터 error-reporting 채널을 넓히는 시도를 하여 성공하는지는 알수 없지만, 전통적으로 누군가가 고민하고 변경을 시도한다면 언젠가는 누군가가 성공으로 이끌 것이다.


'Linux Kernel Study > Linux Weekly News - 번역' 카테고리의 다른 글

Virtually mapped kernel stacks  (0) 2016.07.06
[LWN] A taste of Rust  (0) 2013.04.27
[LWN 번역] Memory Compaction  (0) 2012.11.01

A taste of Rust

orignal URL : http://lwn.net/Articles/547145/

 

Rust, Mozilla project 에서 여러가지 새로운 feature들을 추가한 새로운 언어이다. 새로운 feature 중에 "safety"에 중점을 맞추었다. compiler level에서 감지하고 예방할 수 있는 error의 범위를 증가시키는 노력을 하여 최종 product code에서 error 가 감소하도록 했다.


"safety" 를 증가시켜주기 위한 언어들의 디자인의 방법에는 일반적으로 두가지가 있다. 하나는 좋은 code를 쉽게 만들수 있도록 지원하는 것이고, 다른 하나는 나쁜 code 만드는 것을 어렵게 하는 것이다. 전자는 여지껏 구조적 programming, 다양한 type, 향상된 encapsulation(high-level 개념으로 개발자의 목표를 쉽게 표현할 수 있도록 하는) 통해 많은 성공을 거두었다. 후자의 접근은 전자와 같이 널리 발전하지도, 성공하지도 못한 상태인데 나쁜 code를 만들게 되는 기능을 제거하는 것이 필요하기 때문이다. 물론 잠재적으로 위험한(?) 기능들은 대게 매우 쓸모있다. 전형적인 예제로는 goto 문이 있는데, 알려진 error를 내포할 수도 있는 것이지만 아직가지 절차적 program 언어에서 사용되고 있다. 


어째든 Rust 언어는 두 번째 접근 방법을 이룰 수 있도록 한 언어이다. C 언어나 java 같은 언어에서 제공하는 몇개의 feature를 사용하지 않거나 매우 제약적으로 Rust 에서는 사용된다. Rust는 이와 같은 feature를 사용하지 않는 것을 보완하기 위해 충분히 지원하도록 노력했다. 이 중 한 방법으로 Rust 에서는 다른 언어에서 Runtime 에 발생할 법한 문제를 compile time에서 발견할 수 있도록 노력했다. 이 것은 Runtime debugging의 비용을 줄일 뿐만 아니라 고객으로 부터 지원 요청의 횟수를 줄일 수도 있다. 


다른 언어에서 사용하는(structures, arrays, pointers 등) type을 Rust 에서도 지원한다 하지만 대게 제한적으로 운영이 된다. 개발자가 진정으로 말하기 원하는 것과 유사하게 모양을 갖추고, type의 확장 및 control 방법등 다양한 방법이 있다. 


Rigidly defined areas of doubt and uncertainty


low-level 기능의 접근을 제공하는 Modular-2 언어에서 system module을 반영하는 움직임으로 Rust 는 "unsafe" 로 선언하여 사용되는 함수와 code를 허용한다.  (있긴 하지만 safety한 code를 위해 반영에 조심하는 듯)


이것은 진정으로 safe 한 언어를 제공하는데 실패라고 볼 수 있지만 그것은 너무 단순하게 생각한 것이다. 

우선, Gödel's incompleteness theorem에서는 어떤 programming 언어서든 많이 충분히 기능을 제공해야 한다. 그것이 비록 "safe"한 것을 고려하지 못하더라도. 그러나 경험적인 level에서 볼때, code가 compiler에 의해 생성된 program context 가 "unsafe" 한 것을 갖고 있다는 것을 볼 수 있다. bug는 compliler 가 발견할 수 있다는 어떤 희망도 없을 때 잘못된 행동을 할 수 있는 가능성이 높을 것이다. 사실 완벽하게 safety 한 것은 불가능하다.


"unsafe" 한 code가 있는 것은 피할 수 없다고 볼때, compiler 가 target program에 unsafe 했던 부분을 나타내게 하던가 target language 의 library 에 구현을 하는 것으로 하는 것이 가능하다. 이러한 선택은 "unchecked" 괸 code 가 허용되는 부분에 명백히 표시를 해두게 되면 다른 부분은 굉장히 "safe"한 영역이 될 수 있다는 것이다. 또한 code reviewer에 의해 주의깊게 볼 수 있도록 표시를 해두는 것이며 이로 인해 개발의 편의성을 더 둘 수 있다는 것이다.


만약 Rust compiler(rust 로 만들어졌다)를 보게 된다면, 우리는 111 개의 소스 code가 있는 것을 알 것이고 그 중에 33개의 "unsafe"한 것을 포함한다는 것도 알 수 있다. 30%는 잠재적인 안전하지 않는 것을 포함하지만 70%는 특정 error 를 확실히 포함하지 않는 것을 보장 하고 이것은 좋은 code 이다라고 생각할 수 있다.


Safer defaults


Rust 가 어떻게 safety를 증가시켰는지 살펴 보도록 하자.


다른 언어에서 "const"(C, Go) 나 "final"(Java)와 같은 keyword 를 가지고 한번의 생성으로 같은 값을 항상 참조할 수 있도록 만들었는데 Rust 는 반대로 접근했다. 바꿀 수 없는(like const)를 default로 가지고 수정할 수 있는 변수에는 "mut" keyword 를 쓰게 했다. 

예제)

     let pi = 3.1415926535;

pi 는 바꿀 수 없는 변수이다. 하지만, 

     let mut radius = 1.496e11;

은 나중에 변경 가능한 변수가 된다. mut 의 선택은 mutable의 모음만을 기록한 것이다. 개발자가 변경가능한 변수에 대해 현명하게 사용할 수 있도록 한번 더 생각하게 하는 그런 취지(?) 인듯 하다.


Pointers are never NULL


C 에서 대게 pointer의 error 는 pointer 연산이  제한적이고 하지 말아야 하는 행동에 의해 생긴다. Rust 는 NULL pointer 를 허가하지 않고 dereference pointer 로 의 접근은 유효한 object 를 찾아내서 결과를 return 할 것이다. 만약 정말로 없는, 유효하지 않는 pointer를 사용하려고 하면 compile-time에 찾아낼 수 있다.


유효하거나 NULL 인지를 판단함으로써 linked list나 이진 트리에서 data 의 입력이나 검색으로 사용하는 경우가 많다. 이를 위해 Rust library 에서는 "Option' 이라는 parameter type을 제공한다.


만약 T 가 어떤 type이라면, Option<T> 는 type T 에 연관된  Some tag 와 None tag을 포함하는 variant record 이다. 

Rust 는 "match" 문을 제공한다.(다른 언어의 "case" 나 "typecase"의 일반화한 것이다.) 


Option 의 정의

    pub enum Option<T> {

        None,

        Some(T),

   }

예제,

   struct element {

       value: int,

       next: Option<~element>,

   }

위의 element 구조체는 정수 linked list 를 만드는데 사용할 수 있다. element 의 ~ 는 구조체의 pointer를 표현한 것이며 C 에서 *를 사용하는 것과 같다. 나중에 pointer의 다른 type을 살펴 볼 것이다. ~(tilde)는 "owned" pointer 이고 @(sign)은 "managed" pointer 이다.


null-able pointer는  Rust에서 가능하지만 기본적으로 safe 하게 구현하기 위해서는 pointer는 NULL이 될 수 없다. 만약 null-able 한 포인터를 사용하기 위해서는 명시적으로 검증이 되어야 한다.

예를 들면,

   match next {

     Some(e) => io::println(fmt!("%d", next.value)),

     None      => io::println("No value here"),

  }


Rust 에서 배열("vector" 라고 부른다)은 배열의 index로 부터 접근하기 전에 range 내부에 있는지 compiler가 알수 있도록 할 필요가 없다. 그것은 추정컨데 많은 경우에 index가 범위안에 있다는 것을 type을 통해 알수 있다. (이것도 pointer와 비슷하단다) 


이와 같은 것으로 runtime 에 NULL pointer 참조는 발생하지 않을 것이다. 하지만 array 의 bound error는 runtime error로 발생할 수 있다. 그것은 고의적인지 아닌지 알수 없고, 나중에 변경 되어 수정되는 것인지도 알 수 없다.


Parameterized Generics


Rust 에서는 "void" pinter 나 down casts(예를 들면 void 에서 특정한 type으로 casting) 를 허가하지 않는다. 이런 사용을 정당화 하기 위해 parameterized type 과 함수를 사용하여 지원한다. 이것은 C++ 에서 사용되는 template와 java에서 Generic Class 와 형태가 유사하다. Rust 에서 Generic(이에 대한 정의는 여기를 참조)은 단순한 syntax를 가지고 어떤 type이든 함수든 간에 type parameter들을 가질 수 있다.


예제)

    struct Pair<t1, t2> {

      first: t1,

      second: t2,

   }


위의 구조체를 변수에 선언한다.

   let foo = Pair { first:1, second: '2'};


foo 에 대한 명시적인 type을 주진 않았지만, 초기화 변수를 넣어주었다. 이러한 선언은 Rust에서 이렇게 읽을 수 있다

   let foo:Pair<int, char> = Pair { first:1, second:'2'};

또한 특정 변수의 값을 읽어오기 위해 아래와 같이 호출할 수 있다.

   first(foo);

이렇게 하면 compiler는 int 값을 return 한다는 것을 알수 있을 것이다. 사실 int의 복사본이 반환된다(reference가 아님)


Rust는 모든 type 선언(struc, array, enum), 함수 그리고 "interfaces"나 "virtaul class" 와 같은 기본 특성들 모두 parameter 화 할 수 있다. 이 의미는 complier 는 항상 down cast에 대한 요구를 피할 수 있도록 모든 type에 관해 충분히 인지 할 수 있다는 것이다.


Keep one's memories in order


마지막으로 rust의 "safety" 에 관련 사항으로 memory allocation 과 concurrency 를 어떻게 지원하는지 확인할 것이다. 


요즘 다른 많은 언어처럼, Rust 는 할당된 memory에 대해서 명시적으로 release("free" 또는 "delete") 하도록 개발자에게 요구하지 않는다. 그 보다는 memory 해제에 관련해서는 runtime 에 제공할 수 있도록 한다.  local 변수로 stack 에 할당하는 것을 보강하는 두 가지 machanism이 제공된다. 이 두가지의 machanism은 task 에 기반한 multiprocessing mode에 연관되어 있다.


첫번째 machanism은 garbage collection의 대상이 되는 "managed" 할당이라는 것을 제공한다. 이것들은 마지막에 사용한 객체가 사용을 마무리 했다면 할당된 메모리를 해제할 것이며 소멸자가 정의되어 있다면 제거될 것이다. "Managed allocation"은 heap 영역에 할당되며 당연한 얘기겟지만 allocation을 요청한 task 에서만 접근가능할 것이다. task 가 종료되면 task에서 할당된 도느 heap memory는 해제될 것을 보장받는다. 현재 구현은 이렇게 할당된 memory의 reference count를 이용해서 관리를 하지만 나중에는 mark/sweep scheme으로 변경될 것으로 보인다.


두번째 machanism은 하나의 reference(strong reference)만 갖도록 보장하는 것이다. 만약 하나의 reference 가 떨어져 나갔다면 그 객첵은 해제된다. 이것은 system이 알아서 하나의 참조만 있다고 추측하는 것이 아니라 Rust 에서 제공하는 "once" 와 "owned" keyword를 사용해서 명시적으로 알려줘야 한다. 


이 single-reference(하나의 참조만 허가하는) 할당은 common heap에 할당되며 task간 전달이 가능하다. 하나의 reference만 가질 수 있기 때문에 , 다른 task가 접근 사용하여 race condition에 빠지는 것은 불가능하다. 


May I borrow your reference?


"Owned" 값은 "borrowed" 참조를 통해 추가적인 접근이 가능하다. "Borrowed 참조"는 특정 strong 참조의 문맥내에서 사용되어 질수 있다. 이 의미는 borrowed 된 참조의 원본(?)이 제거되나 범위 밖에서 사용되어 질 때는 borrowed 참조는 유효하지 않는 영역으로 바뀌며 그것을 사용하려고 드는 곳이 있다면 compile time의 error를 낼것이다.


위의 사항은 borrowed 참조를 다른 함수로 전달하거나 함수의 반환값으로 사용되질 때 용의하게 사용되어 질 수 있다. allocation type(owned, managed, on-stack 참조) 에 모두 적용될 수 있으며 borrowed 참조가 되어 전달되어 진후 각 할당 type에 맞게  사용할 수 있다.


borrowed 참조 전달은 함수 인자의 type으로 표시하여 쉽게 관리 될 수 있다. compiler가 안전한지 확인할 필요가 없을 것이다. 


borrowed 참조를 반환하는 것은 compiler가 이 참조가 borrowed 된것인지 혹은 이 참조의 유지해야하는 시간을 알 필요가 있는 부분을 약간의 trick을 이용한다. 그렇지 않으면 원본이 언제 제거되어 borrowed 참조가 사용되어 질 수 없는지 compiler가 알수 없기 때문이다. 


이 참조의 lifetime은 함수를 위한 type 인자의 machanism을 사용한다. 하나의 함수는 single quote(')를 사용하여 하나 혹은 그이상의 lifetime 인자를 선언할 수 있고 다양한 argument와 반환 값을 tagging 할 수 있다. Rust는 이런 parameter들의 실제 변수를 결정하기 위한 것과 반환값의 lifetime을 type 추정을 통해 알수 있다. 예를 들면,


   fn choose_one<'r>(first: &'r Foo, second: &'r Foo) -> &'r Foo

이 함수는 하나의 parameter(r)로 두 개의 argument와 반환값으로 적용된다.(first, second, return value). &는 borrowed 참조라는 의미.


실제 사용 방법은,

   baz = choose_one(bar, bat);

compiler는 r의 lifetime은 bar와 bat의 lifetime을 고려하여 효율적인 상호 유지를 할 수 있도록 해야한다. 반환값인 baz 또한 lifetime이 연관되어 있다. 이 lifetime을 벗어나서 사용되는 어떤 시도든 간에 compiler-time에서 error로 확인 가능하다. 이와 관련해서 다양한 예제는 "Borrowed Pointers Tutorial"을 참조


Time for that loophole


Stack, per-task heap, common heap 에 할당되는 object를 허용하는 것은 multi task 환경에서 race condition을 막을 수 있지만 높은 비용이 든다.


"unsafe" 한 영역을 사용하는 것은 위에서 얘기했다. Unsafe code는 "raw" memory 영역(즉 특별한 관리가 가능하지 않는) 할당이나 다른 type의 pointer로 casting 이 가능하다. 


예를 들어 두 개의 owned reference 가 접근하는 queue를 만들었는데, 하나는 queue에 add하는 것이고 다른 하나는 제거하는 것이 있다고 하자. 이 queue의 구현은 적당한 양의 "unsafe"한 code가 필요할 것이다. 하지만 queue의 모든 client는 전적으로 safe하다. 그래서 task간의 owned 참조를 옮기는 것이 가능하고 특정 data struct를 저장 할 수도 있어야 겠다. queue에서 마지막 참조가 없어졌을 때 알수 있어야 하고 적절히 응답을 해줘야 한다. 


Rust 의 standard library에 "pipe" 라 불리는 data 구조체가 구현되어 있다. 그리고 다른 더 복잡한 data 구조체도 구현이 되어 있으며 이는 owned 와 managed 참조만으로 구성되어 있다는 것을 보장하여 예기치 않은 concurrent 접근 및 잘못된 pointer의 사용으로 부터 안전하게 했다.


Reference

Rust Tutorial

Rust Refernece Manual

Blog post about Rust memory management


마지막 단락은 생략했다. Rust 로 큰 덩치의 project를 만들어봐야 safety에 관한 것을 느낄 수 있지 않을까하는 것과 아직 개발 진행중이라는 얘긴 듯하다. 


전반적으로 파악하기 어려운 문장들이 많아 번역이 자연스레 되지 못했던 것 같다. 


예전부터 memory 단편화 문제는 여기서(LWN) 많이 다루어져왔다. 요약하면, system 이 수행되며 memory page 들은 흩어지는 경향이 있으며 이로 인해 물리적으로 연속적인 page 들을 할당하기가 어려워진다. 가능한 한 higher-order(multi-page)을 위한 요구를 피하기 위한 많은 작업들이 kernel 에 있었기에 대부분의 kernel 기능들은 page 단편화에 의해 문제가 발생하지 않았다. 하지만 아직까지 high-order page 할당이 요구되고 있으며, 이와 같은 code의 할당 요청은 단편화된 memory에 의해 실패하는 것이다. 


어떤 경우에는 이 같은 노력이 악화될 수도 있었다. 요즘 processor 는 4K page 로 제한을 두지 않고 더 큰 page(huge page) 를 process 의 address space에서 운영이 가능하다. huge page 사용을 통해 실제 성능향상을 얻을 수 있기 때문이다.(큰 page 로 운영되기 때문에 page fault 가 줄고-한번 fault 날때 크게 가져오기 때문-, 시스템 전체에 page 개수 운영이 많지 않아 TLB 를 통한 address변환이 빠르게 되어 성능향상이 있다.

참조:https://lwn.net/Articles/423584/) Huge page 를 사용할 경우 시스템에서는 충분히 크고 잘 정렬된 메모리 영역을 찾을 수 있어야 한다. 어느 시대에 수행되던 시스템이든 이런 영역을 찾는 것에 대해 고민이 많았을 것이다. 


몇년동안 커널 개발자들은 이런 메모리 단편화를 완화하기 위해 많은 시도를 해왔다. 그 결과로 ZONE_MOVABLE, lumpy reclaim 같은 기술이 나왔다. 


Mel Gorman 아저씨(?)가 memory comaction을 commit 했는데, 그 내용을 살펴 본다.

간략하게 시스템 메모리의 page 가 16개라고 가정하고 시작한다. 


 0

10

 11 12  13  14  15 

시스템 운영 후 위와 같이 메모리를 사용하고 있다면(빨간색 블럭이 현재 사용되고 있는 메모리다) 실제 buddy 입장에서 보면 연속적인 2개의 page 조차도 할당 할 수 없다. buddy는 항상 블럭을 쌍으로 관리하고 있으며 앞에서 부터 0과 1을 상위 order page 로 보기 때문에 쌍을 맞춰 보면, 7번과 8번을 연속적으로 할당 해줄 수 있는 것처럼 보이지만 buddy 입장에서는 7번의 쌍은 6번이고 8번의 쌍은 9번 page 가 되므로 연속적으로 두개의 page를 할당 할 수 없는 상태이다. 


이런 상태에서 2개의 page 요청이 들어왔다면, memory compaction을 시도하게 된다. 알고리즘을 살펴보자


먼저 0(맨 하위)에서 부터 scan을 시작한다. scan하여 옮길수 있는 page를 찾는다.


Movable pages ----->  1  -----> 3, 4 ----> 5


10  11  12  13  14  15 

반면에 15(상위)에서 역으로 free 상태의 page(migration 를 수행할) 들을 검색한다


Movable pages ----->  1  -----> 3, 4 ----> 5


10 11 12 13 14 

15 


                                                                                                                           7, 8 <----- 11, 12 <----- 14 <-- free pages


이렇게 하여 가운데 쯤에서 두 가지의 scan은 맞나게 되면 page migration을 시도한다. 사용되는 page 들은 뒷쪽으로 free한 page들은 앞쪽으로 모은다. 결과적으로,


10 11 12 13 14 

15 


위의 그림과 같이 8개의 연속적인 page 를 얻을 수 있다. 이로 인해 high order 의 page를 필요하다면 얻을 수 있게 된다. 


위의 그림은 간략하게 memory compaction을 표현한 것이다. 실제 시스템에서는 메모리도 크고 compaction이 하는 일이 많다. 그로 인해 큰 chunk의 연속적인 메모리를 확보할 수 있게 된다.


하지만 모든 page 들이 옮길 수 있는 것은 아니다!!! 퉤! 거의 모든 user space page 들은 옮길 수 있고, 옮겨진 page 로 인해 page table entry 들도 같이 수정이 필요하다. 그리고 kernel 이 direct 로 접근하는 메모리 영역의 page들은 옮길 수 없다. 하지만 이로 인해 kernel 이 접근하고 있는 non-movable page 들 때문에 연속적인 memory segment 를 가지지 못하는 경우가 발생하니, kernel 에서도 movable, non-movable page 들을 가질 수 있도록 하고 있다. 하지만 여기에도 문제가 있다고는 하는데 자세한 내용이 없어서 pass.


compaction은 언제 수행되는지 확인하면, 

   1. /proc/sys/vm/compact_node 에 node number 를 write 하면 compaction 이 수행된다. (NUMA system 이 아니라면 0인가?)

    2. system 이 high-order page 를 요청했는데 실패 한다면 수행된다. 실제 할당할 수 있는 memory 는 있지만 연속적인 공간의 부재로 memory allocation 이 실패하는 경우가 될 것이다. 


이런 경우가 아니라면 memory page migration은 시스템에게 많은 비용을 지불 하는 것으므로 compaction은 idle 상태로 유지한다. 사실 compaction을 피할 수 있다면 더 좋다고 한다. 

'Linux Kernel Study > Linux Weekly News - 번역' 카테고리의 다른 글

Virtually mapped kernel stacks  (0) 2016.07.06
Extended system call error reporting  (0) 2015.11.27
[LWN] A taste of Rust  (0) 2013.04.27

+ Recent posts