Linux kernel physical memory allocator (Buddy) - Part 1

Linux Kernel 에서 physical memory 를 할당/해제 관리하는 code를 분석해 보려고 한다. Linux kernel 은 physical memory를 page 단위로 (내가 아는 system 에서는 4KB 단위) 관리하는데 이런 단위로 할당 해제하다보면 system memory 의 단편화가 발생한다.(연속적인 큰 chunk 의 메모리 부재 등) 이런 단편화를 줄이기 위해 사용하는 memory 할당/해제 알고리즘으로 Buddy를 이용한다. Buddy를 통해 연속적인 page(block) 단위의 관리가 가능하기 때문이다.

간단히 Buddy 알고리즘으로 할당/해제 하는 방식만을 알아보고 Part 1 에서는 시스템이 부팅하는 과정에서 memory를 사용한 뒤(bootmem) 시스템이 사용가능한 메모리를  physical memory allocator로 전달하기 까지 과정의 code를 분석한다.

Buddy 는 free_area 라는 구조체로 관리가 되며, 이 구조체는 zone 이라는 구조체 내부에 MAX_ORDER 크기의 배열로 선언되어 있다. MAX_ORDER 는 강제 설정이 아니라면 11 로 사용하게 된다. 

free_area 구조체를 보면

  현재 상태는 5, 10, 12, 13, 14, 15 번의 page 가 free 하다. 이와 중에 2page 를 요청하게 되면, 

  a. order 1번(2^1=2) 에서 찾는다.

  b. order 1번에 없으니 상위 order 인 2번에 가서 확인한다. 

  c. 12번 부터 연속적으로 4개가 free하덴다.

  d. 그렇다면 12번을 order 1 두개로 쪼개자.

  e. 11번 부터 요청한 2개의 page를 할당 해준다.

  f. 남은 14, 15 번은 order 1번에 가서 매달리게 된다. 

2. Memory de-allocation.

  처음 system memory 상태로 다시 돌아가서, 0 번 page 가 할당 해제 요청이 오면

  a. 0번이 해제되고 order 0 의 free_list 로 가서 붙는다.

  다시 1번의 page 가 해제 요청이 들어오면,

  a. 1번이 해제되고 order 0의 free_list 로 가서 붙는다.

  b. 해제하고 나서 buddy를 찾는다. 바로 0번 page 가 buddy가 되고(buddy 찾는 방법은 나중에...)

      두 녀석이 합쳐서 상위 order 로 가서 붙게 된다. 

  c. 결과적으로 order 0에 있던 0,1 번 page는 없어지고, order 1에 0번의 page가 붙게 되는 것이다.

여기까지 간단히 buddy 알고리즘으로 할당 해제 하는 것을 살펴 보았다. 더 상세한 내용은 코드를 분석하면서 다시 다루어 볼예정이다. 이번 part는 간략하게만 정리하고 시스템 부팅 time에 free_area로 메모리가 등록되는 과정까지 다루어 볼것이다.

Linux 가 부팅하는 일련의 과정이 start_kernel() 이라는 함수에서 시작한다.

그 중 mem_init() 함수에서 free_area 설정하는 과정까지만 살펴보도록 하자. (현재 분석하려는 소스에는 크게 상관이 없지만, ARM 기준으로 설명한다.)

<linux kernel 3.4.39 version ARM 기준>

mem_init() 은 기본적으로 memory zone 에 있는 free page 를 찾고, memory 정보를 출력한다. 

위의 소스에서 free_all_bootmem() 내부만 살펴 볼 예정이다.

free_all_bootmem() - arch/arm/mm/init.c ==> free_all_bootmem_core() - mm/bootmem.c ==> __free_pages_bootmem() - mm/bootmem.c ==> __free_pages() - mm/page_alloc.c ==> __free_pages_ok() - mm/page_alloc.c ==> free_one_page() - mm/page_alloc.c 

위의 call flow 만 보면, 실제 system 가용한  page 들을 buddy allocator 로 전달하는 과정으로 볼 수 있다.

여기서 free_all_bootmem_core() 함수를 살펴 보자.

line 9, 10 start 는 0 이 되고(아닐수도 있다.), end는 total page 개수가 된다(start 가 0 이라면) 

line 15 에서 start 에서 end 까지 loop 을 돌면서, (시스템이 부팅하면서 모든 page 는 reserved 상태였다.)

__free_pages_bootmem() 을 호출하고 마지막 단계로 free_one_page() 에서 page 들을 buddy로 넘겨 주게된다.

line 27 node_bootmem_map 은 bitmap 변수로써 page 들을 사용중인지 아닌지를 bit 로 mapping 해놓았는데, 0이면 이미 사용가능한 상태여서 free해줄 필요가 없고 1인 경우에만 free_pages_bootmem으로 넘겨주면 된다. 

(대부분이 reserved 상태이므로 1일 듯.) 예전 2.6.XX code를 봤을 때는 page 하나씩 bitmap을 비교하여 시도하지만 이 line 에서 보는 바와 같이 32bit system 이면 bit 비교 연산을 통해 한꺼번에 free를 시도하는 것이다.

예를 들어 bitmap 앞쪽 32bit가 모두 1이라면 if 문 내로 들어갈 것이며, 이는 32개의 page들이 free가능하다는 의미이므로 order 를 5로 넘겨주면 된다.(ilog2() 함수는 밑을 2로 하는 log 함수. 즉 5가된다) 

이렇게 하면 한꺼번에 free 시켜주게 된다. 

line 31 count 는 현재 free되는 page의 개수를 counting 하는 것이다.

line 33 현재 검사하는 32bit 내부에 0 이 있으면 그 32개의 bitmap은 하나씩 검사하여 free 하도록 하는 code임.

line 52 bootmem 에서 사용했던 bitmap 의 virtual address로 page 를 얻어온다. 

line 53 은 total page 개수를 계산 한 것이다.

line 54 는 전체 page 를 관리하기 위한 bitmap으로 node_bootmem_map 이라는 것을 할당 했을 것인데, 이 bitmap이 이제 사용되지 않으니 이를 위해 할당한 page 들도 해제 해준다. 만약 total page 가 4096 * 8 개 였다면 bitmap 변수는 한 page 를 차지 했을 것이고, 이를 line 56~57 에서 해제 해주는 것이다. 

이 과정이 모두 완료 된다면 buddy 에서 system memory의 형태는 대략, 

위와 같은 모양을 하게 될 것이다. 이 그림과 같이 이 시점에서는 사용하는 메모리가 거의 없으므로, 2^10(1024) page block 에 대부분 묶여 있을 것이고, 자잘하게 align 이 맞지 않거나 실제 쓰고 있는 메모리를 하위 order 에 매달아 놓게 된다. 시스템이 만약 128MB 라면(물론 kernel image가 올라가는 1M~XM, page table이 사용하는 메모리 등등 앞부분에 필요한 메모리를 빼게되면 128MB가 정확이 안떨어진다. 정말 가정인 것이다.) 

10 order free_list 에 32 개의 page 가 매달려 있을 것이다.

다음 part 에서는 실제 memory allocation 과 free 하는 code를 중심으로 분석을 해볼 예정이다.

kernel source 에 보면 free_list 에 type 이 5가지가 있는데 그것은 고려하지 않은 분석임.

Beginner Guide to Linux Kernel Hacking

막상 kernel 에 관련된 책도 보고 어떻게 개발에 참여할 수 있는지 고민만 많이 하지 딱히 문제가 있는 부분을 찾는 것도 수정하는 것도 어렵다.(다 잘되어 있는 code 처럼 보이기도 하고 ^^)

이래 저래 초보자(?)를 위한 blog 나 site 를 찾아봤지만 뭘 해야하는지 콕 찝어 얘기해주는 것도 아니고..

암튼, 이 제목을 가진 글은 조금 쉬운 접근 방법인 것 같기도 하고 번역도 쉬울 듯 하여 시작해본다.

시작.

Linux kernel 은 굉장히 복잡한 software 이며 누구나 참여가능하지만 hacking 을 쉽게 하고 개발에 기여하기는 어렵다. 다른게 얘기하면 하루 이틀만에 시작하여 hacking 할 수 있는 것은 아니라는 것이다. 개발자는 kernel 에 대한 지식이 필요한데 모든 kernel 내부는 배울 수 있다는 점이 장점이다.

간단한 kernel 에 대한 note 가 있는데 The workings of the Linux kernel 를 참조하면 된다.(이부분도 번역을..)

개발자 스스로 질문을 해보자, kernel 이 나에게 있어 완벽하게 동작하고 내가 고칠 수 있는 부분은 있는 것인가?

(내가 하고 싶었던 질문이다.) 여기 blog 에서는 이런 부분에 대해서는 미리 단념할 필요가 없다고 한다. 커널 개발자들은 도움이 필요한 상세한 list(정리가 필요한 무수한 code들) 를 갖고 있다. 예를 들어, 이런 code들은 /drivers/staging 디렉토리 내부에서 찾을 수 있다. 이 디렉토리 내부에 있는 driver 들은 일반적인 linux kernel coding guideline 을 만족하지 못하는 code 들이 많다. 여기에 위치한 code들은 다른 개발자들에 의해 mainline 에 merge 되기 전에 정리를 도움받고자 하는 것이다. staging 디렉토리 하위에 있는 모든 driver 는 TODO list를 갖고 있는 것도 참고하면 좋다고 한다.

여기 driver 들의 대부분이 그것들의 TODO list 에 다음과 같은 line을 갖고 있다:

- fix checkpatch.pl issues

이것은 어떤 의미를 가지며 어떻게 해야 하는지에 대한 의문이 있을 것이다. 모든 큰 code 의 내용은 여러 개발자들이 참여하여 개발하기 위한 일정한 coding rule 을 갖고 있다. 어떤 kernel 개발자의 목표는 다른 개발자들에게 code의 error를 찾도록 도움을 받고 싶어 한다. 이런 coding rule 은 이런 error를 찾는 것에 도움을 줄 수 잇다는 것이다. 그래서 kernel 에 code가 들어가기 전에 적어도 두명의 개발자가 code에 대한 review 를 하기 때문에 이런 coding style guildline 은 매우 중요한 덕목(?)이다. 그리고 개발자는 kernel source tree 에 Documentation/CodingStyle 에서 관련 사항을 볼 수 있다. coding style 및 error를 빨리 찾기 위해 scripts/checkpatch.pl 이라는 것이 개발되어 졌고, 기본적이 coding style 이 지켜지지 않아 다른 개발자들의 시간을 낭비하는 일을 줄여주는 역할을 해준다.

암튼, drivers/staging 에 위치하는 driver 들은 거의 항상 styling issue 를 갖고 있을 것이다.(guildline 에 익숙치 않은 개발자가 개발하는 경우가 있기 때문이다.) 일단 처음으로 해볼 것이 이런 것들을 kernel coding style guildline 에 맞춰 수정해주는 것이다. 그래서 처음 시작하는 kernel 개발자는 checkpatch.pl 을 수행하고 관련사항을 수정해주므로 해서 도움을 줄 수 있다는 것이다.

Specific Coding Rules

Documentation/CodingStyle 에 모두 나와있지만 개발자가 시작하는데 있어 간략한 부분을 overview 한다.

Whitespace

대부분이 code를 개발함에 있어 indentation(들여쓰기)를 space 가 아닌 tab 을 사용한다. tab은 대게 8 의 길이의 space 를 갖는다. (kernel code 는 tab 을 space 가 아닌 하나의 tab 문자-4 or 8길이의-를 사용한다.) 커널 code를 보고 tab 이 어떻게 되어 있는지 맞춰 주면 될 듯 하다. 또한 한 line 을 80자 이상 넘겨서는 안된다. 80자는 개발자들이 logic을 더 작고 쉽게 인지 할 수 있도록 도와준다.

Braces

Brace 의 사용에 대한 rule 은 꾀 까다롭다. brace를 여는 것은 한 문장의 마지막에 붙여서 쓰고, brace를 닫는 것은 마지막 문장의 다음 line 으로 넘어가서 사용한다. 예제를 보자    if (error != -ENODEV) { foo(); foo2(); }

만약 if else 문의 구조라면 다음고 같이 한다.

위와 같이 수정 가능하다.

그럼 제대로 수정이 되었는지 확인하면,

$ ./scripts/checkpatch.pl --file --terse drivers/staging/bcm/Qos.c | grep 821

해서 아무런 message 도 나오지 않으면 성공한 것이다.

수정 후, build 해서 확인 해야 한다.

빌드 방법은 다른 site 에서 찾아 보면 된다.

간단히 그 파일만 빌드 하는 방법을 보면, 물론 full build 가 되어있다는 것을 가정하는 것이다.

$ make drivers/staging/bcm/Qos.o

만약 위와 같이 해서 error 발생하지 않는다면, 변경사항을 patch로 만들고 적용가능한 상황까지 만든 것이다.

일단 이것까지 해왔다면 kernel을 download 받았다는 것이지만, 간략하게 kernel 을 받고 patch를 만들고 전달하는 과정을 적어본다.

// 참고로 /path/to/linux/kernel은 아무대나 kernel이라는 directory를 만들면 된다.

$ mkdir /path/to/linux/kernel

$ cd /path/to/linux/kernel

$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git

준비 되었다면 다음 단계로 넘어간다.

수정을 한 상태라면 git 을 이용해 local commit 을 만들고 그것을 patch set 으로 변환한 뒤, 관계자(?) 에게 review 메일을 보내면 된다.

commit 을 어떻게 했는지 확인해 보자.

$ cd drivers/staging/bcm

$ git log Qos.c

맨 위의 commit 을 보자

patch 만드는 방법은, 

수정 완료 후,

$ git add drivers/staging/bcm/Qos.c

$ git commit 

하면 당신의 editor로 comment 를 입력받는 화면이 나온다.

// image

위에 처럼 comment 를 달고(영어를 못하니 일단 대충..) 저장하면 된다.

첫번째 line은 수정사항에 대한 제목 같은 것을 적고 추가적으로 적으려면 새 line(엔터)을 두개 넣고

적으면 된다. 참고하여 위의 commit 처럼 만든다.

Signed-off-by : Your Name <youremail@email.com> 을 추가한뒤 저장.(저는 안했음. 지금 보낼것이 아니라서..)

이제 당신의 첫번째 patch를 완성했다.

Getting Your Change into the Kernel Tree

위에서 수정한 사항을 patch로 만들어 커널 개발자에게 review 및 전달을 요청해야 한다. 일단 patch를 일단 만들어 보자.

$ git log

당신의 commit 이 제일 위에 있을 것이다.

바로 밑에 있는 commit 의 hashid 를 parameter 로 넣어준다.

$ git format-patch <hashid> -o ~/

이렇게 하면 만들어진 commit 이 0001-XXX.patch라는 이름으로 만들어 진다.

이것을 다시한번 checkpatch.pl 을 수행해서 정상적으로 반영가능한지 확인을 해보자.

내가 위에서 했던 수정했던 것은 또다른 문제를 갖고 있어 error를 출력했지만 정상적으로 되었다면

total :0 errors, 0 warnnings, XX lines checked 가 보일 것이다.

이제 메일을 보내보자.

Now to Send it Off

이제 완정된 patch를 누구에게 보내야 하는지 알아야 한다. 커널 개발자들은 script 로 누구에게 알려야 되는지 쉽게 알수 있다. 그 script는 get_maintainer.pl 이고 이것은 scripts directory에 위치한다. 이 script는 파일을 확인하고 내가 수정한 파일이 kernel source tree의 maintainer 들에 대한 정보를 알려준다. 

$ ./scripts/get_maintainer.pl /path/to/0001-your-patch.patch

devel@driverdev.osuosl.org (open list:STAGING SUBSYSTEM)

linux-kernel@vger.kernel.org (open list)

위와 같이 나오더라.

이것은 일반적인 e-mail client 로 전송하면 patch format에 space및 tab 등 변형이 되기 때문에 Documentation/email-clients.txt 를 확인하여 그 email client 를 이용하여 전송하면 된다. 하지만 git commit 로도 지원이 되는데, 그 방법은,

$ git send-email -to email@email.com -to email2@email.com -cc devel@driverdev.osuosl.org -cc linux-kernel@vger.kernel.org 0001-your-patch.patch 하면 된다.

사실 to 를 누구로 해야하는지는 안나와 있어서 나중에 내가 용기가 나면 시도 해보고 다시 알려주겠다.

또 한가지 git send-email command 가 없다고 나오는 경우도 있는데, 그 때는

// ubuntu 의 경우

$ sudo apt-get install git-email

하면된다.

이렇게 해서 적절한 CC로 메일이 일단 전달되면 몇일 내로 개발자에게 답변이 온다고 한다. 답변은 accept 해주거나 comment 를 포함해서 온다고 한다. (comment 가 날아오면 그것을 해결하고 다시 보내면 될 듯.)

이상 여기까지 초보 개발자가 kernel 에 contribution을 하는 방법을 알리는 blog 를 나름 번역을 해봤다.

원문 : http://lotphelp.com/lotp/beginner-guide-linux-kernel-hacking

CodeChef

Alogrithm 연습을 위한 site 를 소개하려 한다.

어쩌다 Google Codejam 을 알게 되었는데, 문제를 몇개 열어 풀어보려고 시도를 했지만 어떻게 접근을 해야 하는지 조차 생각해내지 못해 좌절(?)을 맞게 되었다. 그래서 여기저기 Community 도 돌아다녀보며 사람들이 어떻게 이런 Competition을 준비하는지에 대한 내용을 보게 되었다. 그 중 TopCoder 라는 곳을 먼저 알게되었는데, 오래동안 준비해왔던 단체라 볼 수 있는 자료도 많고 java applet 을 통해 Web 환경에서  algorithm test 를 할 수 있도록 만들어 놓았다.(나중에 posting 하겠다.) 하지만 단점이라고 굳이 짚자면 지원되는 language 가 4개 밖엔 없었고(C++, java, C#, Visual basic) 내가 하고 싶어한 python은 아직 준비중이 었던 것이다. 또 하나는 algorithm 문제를 쉬운 것, 혹은 어려운 것만 모아 두지 않아 찾아보고 할만한 것(?)만 시도 해봐야 하는 것이다. 이 사이트도 나중에 도전을 해봐야 겠지만 지금은 조금 무리인 듯 해서 다른 site 를 찾던 중에 CodeChef를 찾은 것이다.

URL : http://ww2.codechef.com

이 사이트의 가장 큰 장점은 다양한 language 를 지원하는 것과 나이도별(easy, medium, hard, challenge, peer) 문제를 모아둔 것이다. 물론 Algorithm test 중 과정에서 실패한 항목에 대한 출력을 안해준다는 것이다. 그래서 내가 어떤 input 값에 대한 output 이 잘못되었는지 스스로 확인해봐야 하는 것이 문제이다.(TopCoder 는 이런 것들을 확인해준다)

하는 방법은 간단하다.

1. Site 에 접속하여 가입을 한다.

   - 가입 후 확인 메일이 오는데, 확인 메일에서 link를 따라가면 password 를 설정 할 수 있다.

   - 또한 facebook 계정과 연동이 되어 그냥 해도 될 듯 했지만 연동하지 않았다.

가입이 완료 되었다면,

2. Practice ==> Easy 문제를 보자

위 그림에서 박스로 되어 있는 부분으로 가서 "Easy" 클릭

3. 진입

이와 같이 문제와 Sucessful Submission 개수 및 정확도 등을 보여준다. 맨 위에 있는 문제는 "Easy" 중에서도 어려운 문제인 듯 하다. 푼사람이 많지 않으니.. ㅎㅎ

그래서 맨 아래에서 부터 풀어 올라와면 좋을 듯!!!

4. 한문제를 풀어보자.(미리 풀어봤으니)

Holes in the Text 라는 주제의 문제를 풀어보자(아래에서 7번째에 있다. )

물론 영어라는 압박(?) 있지만 걱정말자 Example 만 잘 보면 그냥 문제의 의도를 알수도 있다. 아니면 이 문제의 답변글을 살펴 보셔도.. 

암튼 문제를 간단히 요약하면 주어진 문자열에 영문자(대문자만)에 있는 구멍(?)의 개수가 몇개인지 찾는 문제이다. 

(예를 들어 "A" 는 구멍이 1개, "B" 는 2개, C, E, F 이런 녀석은 구멍이 없는 문자다)

Example로 나온 "CODECHEF" 는 구멍이 "O"와 "D" 에 하나씩 2개가 있는 것이다. 

사실 이런 문제는 문자가 구멍이 몇개 있을 것이라는 규칙 같은 것이 없다.(Table 을 만들어 줘야 할 것이다.)

5. 내 개인 컴퓨터로 문제를 열심히 풀어 Example에 나온 input 과 output 에 맞도록 작성한다.

(Python으로)

alphaHoles에 A~Z 순서로 hole의 개수를 미리 적어 놓는다.

그리고 input으로 들어오는 문자열에서 문자를 하나씩 꺼내 'A' ascii 값을 빼준다.(65) 그렇게 되면 정확히 alphaholes table에 각 문자에 맞는 hole 개수 값을 갖고 올 수 있다. 그리고 다 더 해서 출력해주면 끝~

6. code를 만들었으니 확인해봐야 겠다.

문제 아래를 보면, "SUBMIT" 이라는 버튼이 있다. 클릭하자

(SUBMIT 버튼 위에 보면 지원되는 language 와 Time limit 같은 것은 확인하자.)

SUBMIT 을 click 하면,

위에서 처럼 창이 뜬다 여기에 code를 넣고 맨아래 Submit 을 클릭하면 되는데 그전에 자신이 사용할 language를 선택해야 한다. python을 선택하고 code를 넣겠다.

위에 처럼 code를 붙여 놓고 맨아래의 submit button을 클릭하면 된다. 그럼 progressbar 가 나오고 정상적으로 완료되면 Accept 가 되는 것이다.(이미 submit을 한번 했으므로 이 화면은 제외하겠다.)

그리고 나중에 나의 Code를 다시 보려면,

문제 제목 옆에 보면 "MY SUBMISSIONS" 라는 버튼이 있다. 클릭하면 내가 했던 Submit 을 모두 볼수 있다(한번에 성공했다면 하나밖에 없겠지만 여러번 했던 경우에 모두 볼 수 있을 것이다.)

미리 code test를 local에서 하고 넣는 것이라 compile 오류는 없겠지만 대게 Time limitation에서 걸린다. 시간을 짧게 요하는데 빨리 끊내지 못하고 시간을 끌면 Fail 난다.

이런 식으로 하나씩 하면 된다. 물론 막히거나 어려운 점이 있을 것으로 예상된다. 그렇다면 다른 사람이 이미 성공한 소스를 참조를 해보자. 다른 사람 소스에 너무 의존하는 것보다 자신이 하는 것이 좋지만 너무 어렵다면 참조를 하는 것도 좋을 듯하다. 문제가 많으니 처음엔 참조하더라도 나중에는 그냥 쉽게 풀수 있지않을까 한다. 

내가 10개정도 풀었는데 Easy 문제는 10~20분정도면 충분히 풀수 있을 것으로 본다. 하나씩 풀고 공유할 알고리즘이 있다면 써보도록 하겠다.

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에 관한 것을 느낄 수 있지 않을까하는 것과 아직 개발 진행중이라는 얘긴 듯하다. 

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

Anatomy of a Program in Memory

Original url : http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory

Memory 관리는 OS 의 중요한 feature 이다. 같은 사이트를 번역한 글은 모두 x86 기반으로 분석된 글이며 다른 architecture은 다른 방식을 채택했을 수 있다. 

Multi-tasking OS 는 각 process 가 자신 만의 memory sandbox를 갖고 실행된다. 이 sandbox는 virtual address space 이며 32bit system에서는 4GB 를 cover 할 수 있다. 이 virtual address 는 physical memory 를 page table에 의해 mapping 된다. 조금 더 추가하자면 process가 virtual address를 통해 read/write 하게되면 physical memory에 disk 등에서 부터 memory로 읽어온 physical address로 mapping 및 접근 가능하도록 만들어주고 사용 할 수 있도록 한다. 아래의 그림은 Intel architecture(32bit)을 사용하는 machine의 process address space(virtual address space)를 그린 그림이다.

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

Process Address Space(Virtual)

User 영역에서 page-falut 가 나면 kernel 이 physical 영역에 사용허가(?) 를 내어주고 그 virtual address와 mapping 시켜 준다. kernel space 모든 process 의 virtual address 상에 똑같이 존재한다. kernel code와 data는 항상 addressable 하며 interrupt 처리와 system call을 언제든지 실행 하능하도록 준비되어 있다. 반대로 user made의 mapping은 process가 변경될 때마다 address space는 변경되며 사용되는 address도 다를 수 있다. 참고로 intel x86 architecture는 TLB(Translation lookable buffer)라 불리는 곳에 virtual to physical 을 기록하게 된다. 한번의 page fault 로 user address 와 physical address가 MMU 에 의해 연결이 되면 TLB 에 관련된 내용을 쓰고 다음 같은 virtual address를 접근 시 virtual to physical address 변환 과정(이 변환 과정은 비싼 명령이라고 함)이 필요 없이 바로 가져다 쓸수있도록 하는 cache인 것이다. 근데 이 x86은 TLB 에 특별한 tag 같은 것이 없어 공통으로 쓰는 TLB cache에 모든 process 가 사용한다. 그래서 process 간 TLB를 쓰더라도 구별할 방법이 없으며, context switch 와 동시에 모두 flush 를 하게된다. (서로 다른 process 가 같은 virtual address를 이용할 때 실제 physical memory를 다를 수 있기 때문임.)

실제 Context Switch 시 많은 일들이 일어나지만 일부만 기록한다.

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

Context Switching

짙은 녹색 부분이 physical memory 로 mapping된 virtual address 영역이다. 위에서 보듯이 FireFox 는 메모리를 엄청 쓰는 application 중에 하나이다.(물론 그림 상으로는 많이 쓴다 안쓴다 하긴 어렵지만) 분리된 메모리 영역은 heap, stack 등으로 나뉘어지는 segment  가 될 것이다. 아래의 그림은 linux process 가 일반적으로 사용하는 segment layout이다.

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

Process Virtual address space

모든 process는 위의 그림와 같은 방법으로 virtual address space를 운영한다.  process의 top 에서는 stack 이 사용한다. 이는 local 변수나 function parameter 등을 위해 사용된다. 함수나 method를 호출 할 때마다 stack 영역에 새로운 stack frame을 넣게 된다. 새로 넣는다기 보다는 stack base pointer를 새로운 함수에 맞추는 것이라고 보면 된다. function 수행이 완료되고 난 뒤에 생성된 stack frame은 제거된다. 이것은 Stack 은 LIFO(Last In, First Out)에 따라 simple 하게 동작한다. 또한  지속적인 stack 영역의 사용은 cpu cache 내부의 활성화된 stack memory 를 접근/사용 가능하니 performance가 좋다고 한다. 각 process의 thread 들은 자신만의 stack을 갖는다. 

만약 지정된 size 보다 많은 data를 pushing 하는 것이 가능하다. 이것은 expand_stack() 함수 호출로 linux 내부에서 page fault handling 할 때 진행될 수 있다. 그 뒤에 acct_stack_growth() 로 stack 이 알맞게 키워질 수 있는지 확인한다.  만약 stack size 가 RLIMIT_STACK(보통 8MB)보다 작으면 stack 를 키우고 program은 그냥 진행하면 된다. 요구하는 정도에 따라 stack을 키우고 줄일 수 있기 때문이다. 하지만 stack size가 최대치가 된다면, stack overflow가 발생하고 program은 segment fault 를 받게된다. 

stack 의 동적 증가는 unmapped memory region 인(위의 그림에서 stack 아래에 있는 흰 부분) memory를 access 하고 그 공간을 사용할 수 있을 때만 동작한다. 어떤 unmapped memory 의 모든 접근은 일단 segment falut 이 후에 page fault handling을 통해 memory map 이후에 사용하도록 하는 것이다. 어떤 경우에 이 map된 영역은 read-only가 될 수 있고 write operation이 허용되지 않을 수 있다. 

위의 그림에서 memory mapping segment 를 살펴보자. kernel 은 file의 내용을 direct mapping을 이 영역으로 map 해준다. 어떤 application이든 linux 의 mmap() system call을 통해 이와 같은 mapping을 kernel에게 요청할 수 있다. 이런 memory mapping은 file I/O를 위한 방법으로 편리하고 고성능의 방법이 된다. 그래서 shared libary 는 이와 같은 방법으로 user address space에 필요시 mapping하여 사용한다. 또한 anonymous memory mapping 을 사용하여 file을 mapping 하지는 않지만 program data를 위한 영역으로 사용할 수 있다. (Android 에서 property를 저장하는 공간으로 사용되는 ashmem이 대표적인 예라고 할 수 있을 듯.) linux 에서 malloc()을 통해 큰 block의 memory를 요청하면 C library는 heap 영역을 사용하는 대신 anonymous mapping 공간을 사용하여 확보한다. 여기서 "큰 block" 이라고 하면, M_MMAP_THRESHOLD 로 define된 값보다 큰 경우라고 보면된다.(default 128KB, 이것은 mallopt()를 통해 조절가능하다)

이제 heap 영역으로 넘어가자. heap은 stack 처럼 program이 runtime에 제공받을 수 있도록 만들어놓은 영역이다. 하지만 stack과는 다르게 명시적으로 해제를 시켜주지 않는한 만들어진 function 밖에서도 사용될 수 있다. 거의 모든 언어들은 heap memory management를 program에게 제공한다. memory 요청을 만족시키기 위해 kernel 과 code runtime 사이에 동기화(?) 같은 것이 필요하다. C 에서는 heap 할당은 malloc()을 사용하고 C++, C#과 같은 gabage-collected 언어에서는 new keyword를 사용한다. 

만약 memory 요청에 heap에 공간이 충분하다면 보통의 언어들은 kernel의 개입없이 handling 이 가능하다. 하지만 heap의 영역을 확장이 필요한 경우 brk() system call(kernel 구현 부)을 이용하여 요청된 block을 위한 공간을 만들어야 한다. Heap management는 복잡하며, program의 무질서한 할당 요청 및 해제등을 효휼적이며 빠르게 하기 위해서는 정교한 알고리즘이 요구된다. 

마지막으로 memory 가장 아래에 있는 BSS, data, program text 를 살펴보자. BSS 와 data의 영역은 C 언어에서는 static(global) 변수를 위한 곳이다. BSS와 data의 차이점은 BSS는 초기화 되지 않은 static 변수를 갖는다는 것이다. BSS memory는 anonymous : 어떤 파일과 mapping되어 있지 않다는 의미. 만약 static int A; 라고 code에서 사용하면 A라는 변수는 BSS 영역에 들어 있다는 것이다. 

data segment는 초기화된 static 변수를 갖게 된다. 이 memory는 anonymous 영역이 아니다. source code에서 주어진 초기화된 static 값을 포함하는 program의 binary image의 일부를 mapping 하게 되는 것이다. 예를 들어 static int B = 10; 이라고 선언하면 B은 data segment에 있는 것이며 10이라는 값으로 초기화 된다는 것이다. data segment가 file의 일부(program의 binary 이미지) mapping 하여 사용하지만 private memory mapping type으로 변수의 값이 변하더라도 실제 file(binary image)에 반영이 되진 않는다.

아래 그림에서 특별한 예제를 살펴본다. (pointer 변수 사용 경우) 이 경우 pointer 라는 변수에 address 를 갖고 초기화하는 것을 만든다.(32bit 이니 4byte memory address를 가짐, 이는 초기화 되는 global 변수이니 data segment 에 들어간다). 이 point는 실제 string이 있는 address를 갖고 있는데 이 address는 text segment에 있는 것이다. test segment는 read-only 이며 이미지화(?)된 code모두를 mapping 하고 있는 것으므로 write operation일 경우 segment fault 를 받게 될 것이다. 이런 segment falut 는 pointer bug로 부터 보호하기 위해 있다. 이 단락의 내용을 diagram으로 표현하면,

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

segment falut with address pointer

테스트를 해본다면 linux 에서는 /proc/<pid>/maps file을 읽어보면 memory 영역을 알수가 있다. segment 내에서도 여러개의 영역을 포함할 수 있다는 것을 기억해두자. 예를 들어 각 일반적인 memory mapped file은 mmap segment 에 자신만의 영역을 가진다. 그리고 동적 library는 BSS 와 data 영역과 비슷한 추가적인 공간을 가지고도 있다.

nm 이나 objdump 로 binary 의 symbol 들을 살펴 볼 수 있으며 그 symbol들의 address 또한 알수 있다. 마지막으로 linux 32bit system에서의 classic 한 virtual memory layout을 살펴 본다.

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

Sharing a buffer between kernel-space and user-space

ION memory allocator 관련 글은 LWN 를 번역한 The Android ION memory allocator 참조.

이번에는 user-space 에서 할당한 메모리를 kernel driver 에서 공유하여 write 를 하고 user에서 write 한 데이터가 잘 들어가 있는지 확인하는 수준(?)으로 진행한다.

% 모바일이나 특정 브라우저에서는 syntex highlight 가 지원이 안되어 textbox 에 소스가 나올 수도 있음.

Scenario

1. User 에서 ion("/dev/ion")을 open ==> alloc ==>  share 순으로 진행하여 공유할 ion buffer 를 생성 및 공유 준비

2. User application 에서 공유하려는 kernel driver("/dev/vion_dev")를 open : 여기서 vion_dev 는 내가 만든 device driver 이다. 

3. User 에서 만들어진 shared_fd 를 vion_dev driver 로 전달.

4. Kernel driver 에서 받은 shared_fd 를 이용해 import 하여 메모리를 공유할 준비.

5. User 영역에서 특정 string("ion buffer test magic string") 을 vion_dev driver 에 write 를 요청

6. Kernel driver 에서 shared buffer 에 magic string을 write

7. User 에서 mmap 으로 shared buffer 의 내용 확인.

먼저 User application을 살펴 보면,

아래의 ion_XXX interface 들은 https://android.googlesource.com/platform/system/core/+/android-4.1.2_r1/libion/ion.c 를 살펴 보면 내용을 볼 수 있다. 

  - User-space application

주석을 참조하고 Android ION 에 대한 내용의 글을 보면 이해가 쉬울 듯 한데..

  - Kernel-space driver#include <linux/device.h> #include <linux/module.h> #include <linux/kernel.h> #include <linux/init.h> #include <linux/cdev.h> #include <linux/fs.h> #include <asm/uaccess.h> #include <linux/export.h> #include <asm/io.h> #include <linux/ion.h> #include "ion_test_module.h" #define DEVICE_NAME "vion" static int major = 0, minor = 0; static struct cdev vion_cdev; static struct class *cl; static struct ion_client *m_client; static struct ion_handle *m_handle; static int device_opened = 0; extern struct ion_device *lg115x_dev; void *kernel_vaddr = NULL; static int vion_open(struct inode *inode, struct file *filp) { #ifdef DEBUG printk(KERN_INFO "vion device open\n"); #endif if (device_opened > 0) return -EBUSY; device_opened++; return 0; } static int vion_release(struct inode *inode, struct file *filp) { // Already open? if (device_opened <= 0) return 0; device_opened--; return 0; } static long vion_ioctl(struct file *f, unsigned int cmd, unsigned long arg) { int result = 0; switch(cmd) { case VION_REGISTER_ION: { int ion_register; if (copy_from_user(&ion_register, (int *)arg, sizeof(int))) { printk(KERN_ERR "cmd %d : Error get data from ion\n", cmd); result = -EFAULT; goto exit; } if (m_client == NULL) { // lg115x_dev is exported from driver/gpu/ion/lg115x/lg115x_ion.c m_client = ion_client_create(lg115x_dev, ION_HEAP_TYPE_SYSTEM_CONTIG, "vion"); } if (m_client == NULL) { printk(KERN_ERR "Failed to create ion client with lg115x interface\n"); result = -EFAULT; goto exit; } // get handle by ion_import_dma_buf() call. m_handle = ion_import_dma_buf(m_client, ion_register); return 0; } // 아직 필요하진 않지만(ion buffer는 user level에서 free해주니까) register와 pair로 // 작성됨. case VION_UNREGISTER_ION: { int ion_register; if (copy_from_user(&ion_register, (int *)arg, sizeof(int))) { printk(KERN_ERR "cmd %d : Error get data from ion\n", cmd); result = -EFAULT; goto exit; } if (m_client == NULL) { printk(KERN_ERR "Failed to free with ion client\n"); result = -EFAULT; goto exit; } ion_free(m_client, m_handle); return 0; } } exit: return result; } size_t get_vaddr_from_ion_buffer(void) { ion_phys_addr_t phyaddr = 0; size_t len = 0; int ret_val = 0; if (m_client == NULL || m_handle == NULL) { printk(KERN_ERR "Can't get client or handle in read operation\n"); return 0; } // get physical address and length from handle. ret_val = ion_phys(m_client, m_handle, &phyaddr, &len); if (ret_val || !phyaddr) { printk(KERN_ERR "Error get physical address from ion\n"); return 0; } else { printk(KERN_INFO "Read : physaddr 0x%x, len 0x%x\n", (unsigned long)phyaddr, (unsigned int)len); } // ION_HEAP_TYPE_SYSTEM_CONTIG 은 map 할 필요가 없을 듯. // virtual address를 바로 얻어와 copy 하도록 함. // kernel_vaddr = ion_map_kernel(m_client, m_handle); kernel_vaddr = phys_to_virt(phyaddr); printk(KERN_INFO "phys to virt 0x%x\n", kernel_vaddr); return len; } // read 도 작성되었지만 사용할 필요는 없습니다. 테스트 용도로 만들어짐. static ssize_t vion_read(struct file *f, char __user *buf, size_t len, loff_t *off) { size_t size = 0; if ((size = get_vaddr_from_ion_buffer()) < 1) { printk(KERN_ERR "Need to ready buffer for read\n"); return 0; } if (size < len) len = size; if (copy_to_user((char*)kernel_vaddr, buf, len) < 0) return 0; return len; } static ssize_t vion_write(struct file *f, const char __user *buf, size_t len, loff_t *off) { size_t size = 0; #ifdef DEBUG printk(KERN_INFO "write data %s\n", buf); #endif if ((size = get_vaddr_from_ion_buffer()) < 1) { printk(KERN_ERR "Need to ready buffer for read\n"); return 0; } if (size < len) { printk(KERN_ERR "Not enough buffer, set to MAX 0x%x\n", size); len = size; } if (kernel_vaddr != NULL) strncpy((char*)kernel_vaddr, buf, len); else printk(KERN_ERR "virtual address is NULL \n"); return len; } static struct file_operations vion_fops = { .open = vion_open, .release = vion_release, .read = vion_read, .write = vion_write, .unlocked_ioctl = vion_ioctl }; static int __init verify_iondev_init(void) { int ret_val; dev_t dev; // Get a number of device node dynamically. ret_val = alloc_chrdev_region(&dev, minor, 1, DEVICE_NAME); major = MAJOR(dev); if (ret_val < 0) { printk(KERN_ERR "Error allocating charater device region\n"); ret_val = -ENODEV; return ret_val; } // Register the character device. if ((cl = class_create(THIS_MODULE, "chardrv")) == NULL) { printk(KERN_ERR "class_create failed\n"); unregister_chrdev_region(dev, 1); return -1; } if (device_create(cl, NULL, dev, NULL, "vion_dev") == NULL) { printk(KERN_ERR "device_create failed\n"); class_destroy(cl); unregister_chrdev_region(dev, 1); return -1; } cdev_init(&vion_cdev, &vion_fops); if (cdev_add(&vion_cdev, dev, 1) == -1) { printk(KERN_ERR "cdev_failed failed\n"); class_destroy(cl); unregister_chrdev_region(dev, 1); } // Initialize ion client m_client = NULL; #ifdef DEBUG printk(KERN_INFO "vion driver : major %d, minor %d\n", MAJOR(dev), MINOR(dev)); #endif return 0; } static void __exit verify_iondev_exit(void) { dev_t dev = MKDEV(major, minor); device_destory(cl, dev); class_destory(cl); cdev_del(&vion_cdev); unregister_chrdev_region(dev, 1); return; } module_init(verify_iondev_init); module_exit(verify_iondev_exit);

참고 할 정도의 code는 되지 않을까? ^^

The Android ION memory allocator

   struct ion_heap_ops {
	int (*allocate) (struct ion_heap *heap,
			 struct ion_buffer *buffer, unsigned long len,
			 unsigned long align, unsigned long flags);
	void (*free) (struct ion_buffer *buffer);
	int (*phys) (struct ion_heap *heap, struct ion_buffer *buffer,
		     ion_phys_addr_t *addr, size_t *len);
	struct scatterlist *(*map_dma) (struct ion_heap *heap,
			 struct ion_buffer *buffer);
	void (*unmap_dma) (struct ion_heap *heap, 
	         struct ion_buffer *buffer);
	void * (*map_kernel) (struct ion_heap *heap, 
	         struct ion_buffer *buffer);
	void (*unmap_kernel) (struct ion_heap *heap, 
	         struct ion_buffer *buffer);
	int (*map_user) (struct ion_heap *heap, struct ion_buffer *buffer,
			 struct vm_area_struct *vma); 

   struct ion_allocation_data {
        size_t len;
        size_t align;
        unsigned int flags;
        struct ion_handle *handle; 

        struct ion_handle *handle;
        int fd;
   }

	     struct ion_handle *handle;
     }

                   unsigned int heap_mask, const char *debug_name)

	       ion_phys_addr_t *addr, size_t *len)

System Boot Up 을 Power-Button 을 누르는 시점부터 써 놓은 글을 번역합니다.

site URL : http://duartes.org/gustavo/blog/post/how-computers-boot-up

아래에 그린 image들은 원본을 참고로 새로 그린 것입니다. 물론 원본 작성자에게 허락을 맡고 쓰는 것이니 오해하지 마시길 바랍니다. 

잘못 번역으로 인한 전달된 지식에 대해 책임지지 않습니다. ^^ 모르는 부분은 대충 넘어가서 빠져있는 부분이 있을 수도.. 

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

<An outline of the boot sequence>

Power Button 을 누르면 mainboard 에서는 자신만의 firmware 를 초기화 하고 CPU를 running 한다. 만약 실패 한다면 여러가지(beep 음 등) 실패의 알림을 해줄 것이다. CPU가 정상 동작했다면, Multi-core 또는 Multi-processor 시스템에서 하나의 CPU 만이 BSP(Bootstrap processor) 가 되어 BIOS 및 kernel 초기화를 수행한다. 남은 core 및 processor는 AP(Application Processor)라고 불리며 kernel에서 명시적으로 살려주지 않는 이상 "halt" state 로 유지된다. Intel CPU 들은 backwards compatibility 를 완전히 지원하기 위해 현대에 개발되는 CPU 들도 초기 부팅시에는 마치 1978년대의 intel 8086 처럼 동작을 한다. 이를 real mode 라고 부르며 이 시점에는 paging 이 disable 되어 있는 상태이다. 이 상태에서는 전체 memory의 1MB 영역까지만 접근이 되며 1MB 내의 memory 어디든 read/write 가 가능하다. 이 시점에는 protection 및 privilege 는 의미가 없다. 

CPU 내부 대부분의 register 들은 부팅 이후에 명확한 값을 갖게 되는데 이중 Instruction pointer(EIP)라고 불리는 register에는 CPU 가 실행해야 하는 instruction의 memory address를 갖고 있다. Intel CPU들은 초기 부팅 때 1MB 밖에 접근 하지 못함에도 불구하고 hack을 이용하여 EIP 에 처음 수행하여야 할 instruction이 존재하는 hidden address를 적용한다. (0xFFFF FFF0 : 4GB - 16byte 영역이며 reset vector 라 불리고 현재의 CPU-32bit의 경우에만- 들은 이것을 갖고 있다.)

mainboard 는 reset vector 에 있는 instruction이 BIOS entry point 로 mapping 되는 memory location으로 jump 하도록 되어 있다. 이 jump 는 이 숨겨진 address(0xFFFF FFF0) 가 전원을 켰을 때, 항상 그자리에 있음을 암시한다. 또한 32bit 의 cpu vendor 들은 memory 에 정상적인 contents(BIOS, reset vector 등)이 memory map에 맞도록 유지하고 있어 변경될 수 없다. 대략적인 memory map은 다음과 같다.

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

<Important memory regions during boot>

reset vector를 통해 CPU는 BIOS code 를 수행한다. BIOS는 machine 내부의 일부 hardware를 초기화 하고 바로 POST(Power-on Self Test)를 수행한다. 이는 computer에 있는 다양한 component들을 테스트 하는데 그 중 video card의 테스트가 실패하면 beep 및 다양한 방법으로 알린 후, system이 멈춘다.(물론 아무것도 안되겠지). 만약 video card의 테스트가 정상적이었다면 제조사의 logo 를 출력한다. 다음으로 memory, keyboard 등을 POST로 테스트 한다. 예전 pentium까지는 내기억으론 keyboard가 설치되어 있지 않다면 beep 음을 내고 error를 내놓았던 것 같은데 지금은 그런지는 모르겠다. 결과적으로 POST는 모든 PIC 디바이스를 위한 resource(interrups, memory ranges, I/O ports)를 초기화 및 테스트를 진행한다. 또한 근대의(?) BIOS 들은 ACPI(Advanced Configuration and Power Interface)를 이용하여 컴퓨터 내부에 있는 device를 표현하는 data를 기록해두고 향후 kernel에서 사용할 수 있도록 준비한다. 

BIOS의 POST 작업이 끝나면 OS 를 boot up 하기를 원한다. OS는 hard disk, CD-ROM 등에 저장되어 있는데, user 가 설정한 boot device를 찾는다. 찾은 device 첫번째 512byte의 sector(sector 0)를 읽는다. 이 부분을 MBR(Master Boot Record)라고 하는데 일반적으로 두 가지 중요한 component를 갖고 있다. 하나는 아주 작은(?) OS specific 한 bootstrapping 프로그램이 MBR 의 제일 처음에 들었다.  이 프로그램이 어떤 것인지는 상관없이 BIOS는 0x7c00 의 메모리에 올리고 Jump 한다. jump 와 동시에 memory에 올려진 MBR code 를 수행한다. 

I confirmed to re-use of image with gustavo-web@duartes.org, If you want to see a original image, just click this image

<Master Boot Record>

MBR 은 window의 MBR loader가 될수도 있고, Linux의 LILO나 GRUB 가 될 수도 있다. 중요한 component의 다른 하나는 partition table이다. 이는 얼마나 많은 disk partition이 있는지 기록을 해두는 공간이다. 전통적인 window MBR은 partition table을 뒤져서 active인 것을 찾고 boot sector를 active한 디스크에서 loading하여 code 수행한다. 그 boot sector는 partition의 first sector가 될 것이며, 전체 disk의 first sector와는 다른 내용인 것이다. 만약 boot sector loading하는 것이 실패한다면, "Invalid Partition Table"또는 "Missing Operating System" 이라는 message를 만나게 될 것이다. (이 message는 BIOS가 아니라 MBR에서 출력하는 것임)

Boot 의 loading은 전반적으로 더 정교하고 유연한 작업니다. Linux Bootloader 인 Lilo 와 GRUB는 다양한 OS, file system, boot configuration들을 조종(handle) 할 수 있다. 전통적인 window MBR과는 다르게 "active partition" 찾아 가지 않고 다음과 같이 수행된다. 

   1. MBR 자체에 first stage bootloader를 내장하고 있다. GRUB에서는 stage 1이라 한다.

   2.  disk로 부터 추가적인 bootstrap을 갖고 오기엔 MBR의 size가 작다. 첫번째 sector는 partition 정보와 hard-coded 된 MBR code들이 있는 곳이다. 

   3. MBR code는 step 2 에서 Bootloader 의 second stage 를 포함하는 file 하나를 읽는다. GRUB에서는 stage 2라고 불리며 grub.conf 라는 file을 읽는다. 이 시점에서 user는 booting 할 kernel을 선택하거나 default 로 부팅한다. 

   4. 이제 bootloader  는 kernel을 실행 시켜야 한다. boot partition으로 부터 kernel을 읽기 위한 file system 에 대한 정보를 갖고 있어야 한다. Linux에서는 "vmlinuz-x.x.x-version"과 같은 binary를 disk로 부터 읽어온다. 그리고 메모리로 loading하고 kernel bootstrap code로 jump 를 하며 bootloader에서 하는 모든 일들을 마무리한다. 

현재 kernel image를 만들면(압축을 하더라도) 2MB 가량된다. 이는 real mode에서 사용가능한 640KB 보다 많이 큰 상황이다. 이를 위해 앞서 써놓은 내용의 "hack" 이용한다는 점이 중요하다. Bootloader는 BIOS call을 통해 disk 로 부터 data를 읽어야 하기 때문에 꼭 real mode 로 수행되어야 한다.(kernel을 아직 못올린 상태이니..) kernel image 를 memory 에 올리려면 real mode 에서 cover하지 못하는 1MB 상위의 메모리를 사용할 수 있게 하는 방법이 있다. unreal mode 라고 불리며 이것은 BIOS에서 1MB 상위를 쓰기 위해 real mode 와 protected mode를 왔다갔다 변경할 수 있도록 한 방법이다. GRUB source를 본다면 이와 같은 Transition을 확인할 수 있다고 한다. 

Boot Loader에서 "Early Kernel Initialization"까지 살펴본 내용이다. 

다음 article은 "Kernel Boot process" 이다.