지밍이 블로그

이번주 주말 아침메뉴, 순두부찌개

원래 고추기름만 내다가, 백종원 레시피처럼 파기름도 내봤는데 정말 맛있다..!

하지만 파 시원한 맛을 너무 좋아해서.. 마지막에서 한움큼 넣어주면

내가 좋아하는 칼칼하고 고소한 순두부찌개 캬~!

원래 우리집에는 마싰다 조리료같은게 없지만 항상 파는 것보다 좋은 맛이난다.

어디가서 당당하게 취미가 요리라고 말 할 수 있을 듯 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

# 가상메모리

# SMP (Symmetric Multiprocessing)

: 모든 CPU가 메모리와 입출력 버스 등을 공유하는 구조

=> 병목현상 발생

# NUMA (Non-Uniform Memory Access)

: SMP 구조에서 병목현상이 발생하여 CPU들을 몇개의 그룹으로 나누고 각 그룹에게 별도의 지역 메모리를 할당

<-> UMA (Uniform Memory Access)

# Node 

: 리눅스에서 뱅크를 표현하는 구조

- bank : 리눅스에서 접근 속도가 같은 메모리의 집합을 부르는 말

- ~/include/linux/mmzone.h

- UMA구조에서는 뱅크가 한개, NUMA 구조에서는 뱅크가 여러개

- 리눅스의 전역변수인 contig_page_data변수로 뱅크에 접근 가능

- NUMA처럼 뱅크가 복수개인 경우, pgdat_list라는 배열을 통해 뱅크에 접근이 가능

=> 리눅스에서는 하드웨어 시스템에 관계없이 노드라는 일관되 자료구조를 통하여 전체 물리메모리에 접근이 가능

# pg_data_t 자료구조

: UMA구조에서 단일노드를 contig_page_data변수로, NUMA구조에서 복수노드를 pgdat_list 배열로 가리켜도

 두 변수는 pg_data_t 구조체를 통해 표현

------------------------------------------------------------------------------------------------------------------------------------------------------------

typedef struct pglist_data {

struct zone node_zones[MAX_NR_ZONES];        // zone 구조체를 담기위한 배열

struct zonelist node_zonelists[GFP_ZONETYPES];    

int nr_zones;        // zone의 개수를 저장

...

unsigned log node_start_pfn;        // 해당 물리메모리가 메모리 맵의 번지수를 저장하는 변수

unsigned long node_present_pages;    // 해당 노드에 속해있는 물리메모리의 실제 양을 저장하는 변수

unsigned log 

...

} pg_data_t;

------------------------------------------------------------------------------------------------------------------------------------------------------------

* 물리메모리 할당 요청시 태스크가 수행되고있는 CPU와 가까운 노드에서 메모리 할당을 시도

# zone

: 일부 ISA 버스 기반의 디바이스를 지원하기위해, node의 일부분(16MB이하 부분)을 따로 관리할 수 있도록 자료구조를 만듬

(물리메모리 중 반드시 16MB 이하 부분을 할당해 주어야 했음)

- ~/include/linux/mmzone.h

- 동일한 속성을 가짐

- 다른 zone의 메모리와는 별도로 관리되는 메모리 집합

- ZONE_DMA, ZONE_DMA31 : 특별히 관리되는 16MB 이하의 메모리

(16MB 이상의 메모리는 ZONE_NORMAL이라고 함)

- ZONE_HIGHMEN : 1GB이상의 메모리를 필요로하는 경우 바로 커널의 가상주소공간과 1:1로 연결해주는 것은 비효율 적이라고 판단하여 

896MB의 물리메모리만 커널의 가상주소공간과 1:1로 연결하고, 나머지 부분은 필요할 때 동적으로 할당하는데,

이때 896MB 이상의 메모리 영역을 일컫는 용어

- 모든 시스템에서 언제나 DMA. NORMAL, HIGHMEN이라는 세개의 zone이 존재하는 것은 아님

- 각각의 zone은 자신에게 할당된 물리메모리의 관리를 위해 zone 구조체를 사용

해당 zone에 속해있는 물리 메모리의 시작주소, 크기

버디할당자가 사용할 free_area 구조체를 담는 변수 등등

- watermark와 vm_stat를 통해 남아있는 빈 공간이 부족한 경우 적절한 메모리 정책을 결정

- page가 부족하여 메모리 할당 요청에 대하여 실패한 경우 프로세스들을 wait_queue에 넣고 hashing을 수행하여 wait_table변수가 가리키게 함

- cat /proc/zoneinfo 명령어를 통해 확인

# Page Frame

: 물리메모리의 최소 단위

- zone은 자신에게 속한 물리메모리를 관리

- 각각의 페이지 프레임은 page 구조체로 관리 (~/include/linux/mm_types.h)

- 페이지 프레임 당 하나의 page 구조체가 존재. (모든 물리메모리에 접근이 가능해야하므로)

- page frame : 하나의 페이지로 관리

- zone : 복수개의 페이지 프레임으로 구성

- node : 하나 또는 복수개의 node로 구성

- 리눅스의 전체 물리 메모리 : 하나 또는 복수개의 node 

# Buddy와 Slab

- 내부 단편화문제를 해결하기 위해 슬랩할당자 사용

- 메모리관리의 부하와 외부 단편화의 해결을 위해 버디할당자 사용

* 물리메모리는 설정한 페이지프레임의 최소단위로 할당

(기본 4KB, 8KB와 2MB 등으로도 설정이 가능)

# Buddy Allocator

- 페이지프레임이 4KB의 경우 10KB를 할당하려할 때 3개의 페이지프레임으로 할당하지 않고 16KB를 할당        

=> 메모리관리의 부하를 줄이고 외부 단편화를 방지

* 커널 2.6.19버전 이전에서 사용되던 버디 

- zone 구조체에 존재하는 free_area[]배열을 통해 구축

- zone 당 하나의 버디가 존재

- free_area[] 배열의 각 엔트리는 free_area 구조체

- free_area 구조체는 free_list와 map이라는 필드를 가짐

------------------------------------------------------------------------------------------------------------------------------------------------------------  

/* ~/include/linux/mmzone.h  */

#define    MAX_ORDER    10        // 10개의 엔트리를 가짐. 0~9의 각 숫자는 해당 엔트리의 free_area가 관리하는 할당의 크기를 나타냄

// 0인경우 2^0으로 1개의 페이지프레임 할당, 1인경우 2^1이므로 2개의 페이지프레임 할당 

// 4KB, 8KB, 16KB... 4MB(2^10 * 4KB) ---> 이 단위들로 메모리 할당이 가능

struct zone {

...

struct free_area    free_area[MAX_ORDER];    // 

...

};

struct free_area {                

struct list_head    free_list;      // 자신에게 할당된 free 페이지 프레임을 list로 관리

// ex. free_list[1]에 free상태의 연속된 2개의 페이지 프레임들이 free_list로 연결

unsinged long     *map;         // 자신이 관리하는 수준에서 페이지의 상태를 bitmap으로 관리

// ex. 전체 물리메모리를 2개의 페이지 프레임 단위로 봤을 때의 상태를 map이라는 bitmap에 저장

};

------------------------------------------------------------------------------------------------------------------------------------------------------------  

그림 출처. https://lwn.net/Articles/121618/

* order(0) -> free_area[0]

  order(1) -> free_area[1]

  ...

* 버디할당자 동작방식

Linux kernel physical memory allocator (Buddy) - Part 2-1

http://woodz.tistory.com/57

http://woodz.tistory.com/58

http://woodz.tistory.com/59

http://woodz.tistory.com/60

# Lazy Buddy

- 커널 2.6.19부터는 free_area 구조와 버디 할당자의 구현이 조금 바뀐

- 프레임에 할당하거나 해제하는 작업에서 페이지를 쪼개거나 합치는데 이럴 때 비트맵 수정도 필요함

- 반복 과정에서 오버헤드가 발생

- 페이지프레임에 대한 작업을 조금 미루자!

 *변경된 free_area 구조체

------------------------------------------------------------------------------------------------------------------------------------------------------------

/* ~/include/linux/mmzone.h  */

#define    MAX_ORDER    11

struct zone {

...

struct free_area    free_area[MAX_ORDER];    // 

...

};

struct free_area {                

struct list_head    free_list;      

unsinged long    nr_free;    // 기존의 비트맵 포인터에서 자신이 관리하는 zone내에서 비사용중인 페이지 프레임의 갯수를 저장하는 변수로 바뀜

};

------------------------------------------------------------------------------------------------------------------------------------------------------------

- zone 마다 유지되고 있는 watermark(high, low, min)값과 현재 사용가능한 페이지 수를 비교

- zone에 가용 메모리가 충분한 경우 해제된 페이지의 병합 작업을 최대한 뒤로 미룸

- 가용 메모리가 부족해지는 경우 병합작업을 수행

* 병합작업

- __free_pages(), 버디에 메모리를 반납하는 함수

- __free_pages()함수는 내부적으로 __free_one_page()라는 함수를 호출

- __free_one_page(), MAX_ORDER만큼 루프를 돌면서 현재 해제하는 페이지가 버디와 합쳐져서 상위 order에서 관리될 수 있는지 확인

- 가능하면 현재 order의 nr_free를 감소시킴

, 상위로 페이지를 이동 후 상위 order의 nr_free를 증가  

=> 해당 작업을 반복하여 전체 order의 버디를 동작

- __alloc_pages() : 버디 할당자로부터 페이지를 할당받는 커널 내부 함수 중 가장 저수준의 함수

- __free_page() : 페이지를 해제하는 함수

- 2의 승수의 크기 단위로 관리하므로 함수 호출시에도 메모리의 크기를 2의 승수로 지정

- 복수개의 zone에 각각의 버디 할당자가 동작할 수 있는 상황에서는 어느 zone에서 메모리를 할당 받았는지 같은 몇몇 속성을 지정해 주어야 함

- 현재 시스템의 버디 할당자 관련 정보 조회 : "$ cat /proc/buddyinfo"

# Slab Allocator

: 일종의 캐시의 집합을 통하여 메모리를 관리하는 정책

- 페이지 프레임의 크기가 요청되는 메모리의 크기와의 차이가 상대적으로 많이 날 수록 내부 단편화로 낭비되는 공간이 증가

- 미리 페이지 프레임을 할당 받은 후 일정한 크기로 분할 해 둔 뒤 사용자가 메모리를 요청하면 버디할당자가 아닌 미리 할당받아 분할한 이 공간(일종의 캐시)에서 공간을 받아옴

- 해제 역시 중간의 이 공간에 이루어짐

- 현재 시스템의 slab 할당자와 관련된 정보조회 : "$ cat /proc/slabinfo"

출처. http://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html

- 캐시의 크기? 

# 인터럽트 

: 주변장치나 CPU가 자신에게 발생한 사건을 리눅스 커널에 알리는 매커니즘

- 외부 인터럽트. 하드웨어적 인터럽트 (인터럽트)

- 소프트웨어적 인터럽트 (트랩, 예외처리라고도 함)

# 인터럽트 핸들러의 수행

- 인터럽트 발생

- PC(or instruction pointer) 레지스터값을 미리 정해진 특정 번지로 설정

ex. ARM 

0x00000000 + offset로 점프

- reset interrupt : offset은 0

- undefined instruction : offset은 4

- software interrupt : offset은 8

# 인터럽트 백터 테이블

: 인터럽트는 간결히 작성해도 4Byte를 넘기때문에 다른위치에 인터럽트 핸들러를 작성하고 0x00000000에는 인터럽트 핸들러로 점프하는 명령어만 기록

ex. ARM CPU의 인터럽트 백터 테이블

--------------------------------------------------------------

0x00000000    _start :        b        reset

b        undefined_instruction

b        software_interrupt

b        prefetch_abort

b        data_abort

b        not_used

b        IRQ

b        FRQ        

--------------------------------------------------------------

- 보통 IDT(Interrupt Descriptor Table) 또는 IVT(Interrupt Vector Table)이라고 부름

# 인터럽트/트랩의 처리

: 문맥저장->인터럽트처리->문맥복원

- 리눅스에서는 인터럽트와 트랩을 동일한 방법으로 처리

- 외부인터럽트/트랩을 처리하기 위한 루틴을 함수로 구현

- 각 함수의 시작주소를 리눅스의 IDT인 idt_table이라는 이름의 배열에 기록

- 다양한 CPU를 지원하기위해 idt_table의 0~31까지 32개를 트랩핸들러를 위해 할당, 그 외의 엔트리는 전부 외부 인터럽트 핸들러를 위해 사용

- 외부 인터럽트를 발생할 수 있는 주변장치는 하드웨어적으로 PIC(Program-mable Interrupt Controller)라는 칩의 각 핀에 연결

- PIC는 CPU의 한 핀에 연결

- x86 CPU의 경우, idt_table의 32번 부터  PIC로 사용이 가능(31까지는 트랩이 사용하므로)

- 리눅스 커널 부팅중에 설정

ex. idt_table의 32번 엔트리에 timer 인터럽트 발생 (가정)

- timer는 PIC와 연결된 선에 펄스를 보냄

- PIC는 수신한 펄스를 적절한 번호로 변환

- I/O 포트에 저장하여 CPU가 버스를 통해 읽을 수 있도록 함

- CPU와 연결된 라인에 펄스를 보내 외부인터럽트 발생을 알림

- CPU가 인터럽트 발생을 알게되어 PIC의 I/O 포트를 읽어 발생한 외부인터럽트의 벡터번호를 확인

- 인터럽트 선을 원래대로 복원시켜 PIC가 다른 인터럽트를 받을 수 있게 함

- 리눅스 커널은 발생한 인터럽트의 번호를 확인

- 이 번호로 idt_table에 인덱싱을 하여 엔트리에 있는 핸들러를 실행

- x86 CPU에서의 idt_table

그림 출처. http://duksoo.tistory.com/entry/System-call-%EB%93%B1%EB%A1%9D-%EC%88%9C%EC%84%9C

# irq_desc table

: 외부 인터럽트가 발생되어 들어오는 라인은 한정되어 있으며, 디바이스 드라이버들은 동적으로 인터럽를 동적으로 할당받거나 해제할 수 있음.

따라서 별도의 관리 매커니즘이 필요. 

- idt_table의 32~255까지(128번 제외, 시스템 호출이 사용)를 같은 인터럽트 핸들러 함수가 등록

- 해당 함수들은 do_IRQ()를 호출

- do_IRQ() : 외부 인터럽트 번호로 irq_des 테이블을 인덱싱하여, 해당 인터럽트 번호와 관련한 irq_desc_t자료구조를 탐색

- irq_desc_t : 하나의 인터럽트를 공유할 수 있도록 action이라는 자료구조의ㅏ 리스트를 유지

- action : 이 리스트를 통해 단일 인터럽트 라인의 공유가 가능

# 문맥저장

- idt_table에 등록되어있는 common_interrupt (외부 이너럽트를 위한 공통 핸들러)

-----------------------------------------------------------------------------------------------------------------------------------

# define  SAVE_ALL     \

cld;    \

pushl    %es;    \

pushl    %ds;    \

pushl    %eax;    \

pushl    %ebp;    \

pushl    %edi;    \

pushl    %esi;    \

pushl    %edx;    \

pushl    %ecx;    \

pushl    %ebx;    \

novl    $(___USER_DS),    %edx;    \

novl    %edx,    %ds;    \

novl    %edx,    %es;

common_interrupt:

SAVE_ALL                    // 인터럽트가 발생한 시점에 수행중이던 태스크의 문맥 저장

call    do_IRQ                // do_IRQ() 함수를 호출하여 실제 인터럽트 서비스가 수행

jmp ret_from_intr         // 인터럽트 처리가  종료되면 SAVE_ALL 매크로로 저장했던 문맥을 RESTORE_ALL 매크로를 통해 복원

-----------------------------------------------------------------------------------------------------------------------------------

# 리눅스에서 트랩의 처리

- 트랩은 구분이 필요함

1. fault : fault를 일으킨 명령어 주소를 eip에 저장 후 해당 핸들러 종료 후 eip에 저장되어있는 주소부터 다시 수행

2. trap : trap을 일으킨 명령어의 다음 주소를 eip에 저장 후 해당 핸들러 종료후 다시 수행

3. abort : 심각한 에러. eip에 값을 저장할 필요가 없고 현재 태스크를 강제 종료

-  ret_from_exception()

: 시스템 콜을 제외한 트랩의 경우 ret_from_exception()을 호출하여 이전 문맥으로 돌아감

- ret_from_intr()

: 일반적인 외부 인터럽트의 경우 해당함수를 호출하여 이전 문맥으로 돌아감

- ret_from_sys_call()

: 0x80 인터럽트, 즉 시스템 콜의 경우

- ret_from_fork() 

: 시스템콜 중 fork(), vfork(), clone()의 경우

# 시스템 호출 처리과정 (intel CPU의 경우로 가정)

그림 출처. http://duksoo.tistory.com/entry/System-call-%EB%93%B1%EB%A1%9D-%EC%88%9C%EC%84%9C

- fork() 시스템 콜 호출

- /usr/lib/libc.a 표준 C 라이브러리에 구현되어있는 fork() 라이브러리 함수 호출

- CPU내의 범용 레지스터 중 eax 레지스터(ARM CPU의 경우 r7 레지스터)에 fork() 함수에 할당되어 있는 고유한 번호인 2를 저장

- 0x80인자(시스템콜)로 int명령으로 트랩을 발생시킴. (ARM CPU의 경우 swi 명령어)

- 트랩 발생 후 커널로 제어 이동

- 문맥저장 후 트랩의 번호(0x80으로 가정)에 대응되는 엔트리에 등록되어있는 함수(0x80이므로 sys_call())를 호출

- sys_call()에서 eax의 값을 인덱스(여기에서는 2)로 sys_call_table을 탐색하여 sys_fork()함수의 포인터를 얻어옴

sys_call() : arch/x86/kernel/의 entry_32.S 또는 entry_64.S에 구현

sys_call_table : arch/x86/kernel/의 syscall_32.c 또는 sysscall_64.c에 구현

=> 사용자 응용단에서 fork() 시스템 콜 호출 후 IDT 테이블과 sys_call_table을 이용해 커널에서 구현된 sys_fork()함수 호출

# 시스템 콜에 할당되어있는 고유번호 찾기(Intel CPU 기준)

- 리눅스 커널에서 제공하는 모든 시스템콜은 고유한 번호를 가짐

- ~/arch/x86/syscalls/syscall_64.tbl 또는 syscall_32.tbl에 정의

- 총 317개

- read()는 0, write()는 1, open()는 2

# 시스템 호출 함수 구현

1. 사전 등록처리, 시스템 호출 번호 할당

- ~/arch/x86/kernel/syscalls/syscall_64_tbl 파일에 새로운 번호를 할당

- 시스템 호출 테이블에 새로운 시스템 호출 처리 함수를 등록

- 할당한 번호를 인자로 sys_call_table이 접근될 때 호출할 함수를 등록

- ~/include/linux/syscalls.h파일에 sys_newsyscall 함수 원형을 등록

2. 시스템 호출 함수 구현

- 태스크관리관련 : kernel/ 디렉터리, 파일시스템 관련 : fs/ 디렉터리

- sys_ 접두어 사용

- asmlinkage : C로 구현된 함수가 어셈블리 언어로 구현된 함수에서 호출 할 수 있도록 해주는 키워드 

  -> 인텔 CPU에서는 특별한 기능은 없으며 알파 CPU의 경우 어셈블리 언어에서 C로 구현된 함수를 호출할 때 몇가지 전처리 작업을 수행함

- 커널에서 수행되는 함수이므로 표준 C라이브리를 사용할 수 없음

3. 커널컴파일 수행

4. 재부팅

* 시스템 호출 함수를 kernel/newfile.c 이라는 새로운 파일에 구현하였으면, 

make 명령이 컴파일 할 때 이 파일도 함께 컴파일할 수 있도록 해야함.

-> kernel/Makefile 아래에 해당 내용을 추가

* syscall() : 인자로 시스템콜의 번호를 받아 해당 시스템콜을 호출해주는 매크로

* 라이브러리를 이용한 시스템 호출 함수 구현 : ar 명령어를 사용하여 라이브러리 만들 수 있음.

* Glibc 라이브러리 ?

- 리눅스 배포판이 설치될 때 기본적으로 설치되는 라이브러리 중 하나

- fork(), open() 등의 함수를 호출하게 해주는 라이브러리

- 위에서 말한 syscall()도 해당 라이브러리에 구현되어 있음

# 인자를 전달하는 시스템 호출

--------------------------------------------------------------------------------------------------------------------------------------

// system call 번호를 318로 등록

#include<linux/unistd.h>

#include<linux/kernel.h>

#include<asm/uaccess.h>

asmlinkage int sys_show_mult(int x, int y, int* res)     // 앞의 2개의 인자를 곱하여 결과를 3번째 인자로 넘김

{

int error, comute;

int i;

error = access_ok(VERIFY_WRITE,res,sizeof(*res));    // access_ok() : res라는 사용자 공간에 쓰기가 가능한지 체크

if(error < 0)

{

printk("error in cdang \n");

printk("error is %d \n", error);

return error;

}

compute = x*y;        // current 포인터 변수 : 현재 실행중인 task_struct

printk("compute is %d \n", compute);

i = copy_to_user(res,&compute,sizoeof(int));    // copy_to_user() 매크로 : 

return 0;                                                    //     include/asm/uaccess.h에 정의. 값을 사용자 수준 공간에 전달하기위해 복사

}

// 호출

int main(void) 

{

...

i=syscall(318,x,y,&mult_ret);

...

}

--------------------------------------------------------------------------------------------------------------------------------------

- 시스템 콜의 매개변수는 레지스터의 크기인 32 혹은 64 bit을 넘을 수 없음

- 레지스터의 개수가 제한적임(인텔 CPU의 경우 6개를 넘을 수 없음)

=> 구조체 사용

- kmalloc() : C 라이브러리 함수인 malloc()과 유사하며 커널 내부함수로써 할당 받는 공간은 물리적으로 연속된 공간을 보장

참고. 

리눅스 커널 내부구조(책)