이미지 무단도용 안되요~ 열심히 만들었음...ㅠ_ㅠ
페이징 이론의 일반성 이해하자!
8086 기반으로 이해하고 다른 플랫폼 구현을 어떻게 이해할지 생각하자!
▷ Memory addresses
80x86 기반에서는 3가지 주소 체계 존재
1) logical address : segment + offset(displacement)
(offset : 세그먼트 시작점부터 실제 주소까지 떨어진 정도 또는 거리)
2) linear address (virtual address) :
single 32-bit unsigned integer =>4GB(2^32 memory cell)까지 주소로 나타낼 수있음.
주로 16진수로 표현하여 0x00000000 ~ 0xffffffff 범위가 됨
3) physical address : 메모리 칩의 memory cell의 주소에 쓰임.
메모리 버스를 통해 마이크로프로세서의 주소 핀을 따라 전송된 전기 신호와 상응됨.
이 주소는 32-bit 또는 36-bit unsigned integer 으로 나타냄
* Memory Management Unit (MMU)
logical ---[segmentation unit]---> linear ---[paging unit]---> physical
- 멀티 프로세서 경우 보통 모든 cpu가 같은 메모리를 공유 : 독립된 CPU들이 동시에 RAM에 접근 가능
- RAM에서 read/write 연산은 반드시 순차적으로 해야하기 때문에, memory arbiter 회로가 bus와 RAM 사이에 삽입
- memory arbiter 회로 : RAM이 free-> CPU가 접근 가능, 다른 CPU의 요청을 수행하느라 busy-> delay to access
- memory arbiter 에 DMA(Direct Memory Access) 컨트롤러가 존재함(그래서 단일 프로세서에서도 arbiter 사용)
(회로는 하드웨어에서 관장. not s/w)
▷ Segmentation in Hardware
※ intel 경우 주소 변환에서 2가지 방법 : (1) real mode, (2) protected mode
+ 대부분은 real mode : 호환성 유지 및 OS 부트스트랩 때문
- segment selectors and segmentation registers
logical address = segment identifier + offset
--> segment identifier : 16-bit field : segment selector
--> offset : 32-bit field
+ segment selector 필드
(1) index : GDT나 LDT에서 Segment descriptor entry 식별
(2) Table Indicator(TI) : GDT인지 LDT인지 구별 (GDT: TI=0, LDT:TI=1)
(3) Request Privilege Level(RPL) :Segment selector를 cs 레지스터에 로드할 때 CPU의 CPL을 명시
+ segment selector 정보를 빠르게 가져오기 위해, 프로세서는 selector 정보를 갖고있을
segmentation registers 제공 : cs, ss, ds, es, fs, gs
+ 아래 3개의 레지스터는 특별한 용도 (나머지는 범용. 다른 데이터 세그먼트 가리키는 등 재활용)
cs : code segment register ...program instruction 가리킴
+ 2-bit field : Current Privilege Level(CPL) : 3->lowest(user) , 0->highest(kernel)
ss : stack segment register ... 현재 program stack 가리킴
ds : data segment register ... global & static data 가리킴
- segment descriptor
segment의 특징은 8bit의 segment descriptor를 통해 표현.
segment descriptor는 Global Descriptor Table(GDT) 또는 Local Descriptor Table(LDT)에 저장
GDT는 단 하나만 정의되는 반면에, 모든 프로세스는 각자의 LDT를 가짐. 추가로 필요한 segment는 GDT에 저장
gdtr control register : 주 메모리에서의 GDT 사이즈 및 주소 저장
ldtr control register : 현재 사용된 LDT의 사이즈 및 주소 저장
field name | description |
Base | segment의 첫 번째 byte의 linear address |
G | Granularity flag; 0 (clear) -> byte 단위 표시 / 1 ->4096 byte의 배수로 표시 |
Limit | segment의 마지막 memory cell의 offset. 즉, segment length. G=0이면, segment 크기는 1byte~1MB G=1이면, segment 크기는 4KB ~ 4GB |
S | System flag; 0(clear)->system segment 역할... 중요한 자료구조 저장 |
Type | segment type 및 접근 권한 |
DPL | Descriptor Privilege Level; segment의 접근을 제한. segment에 접근하기 위한 최소의 CPU Privilege level을 나타냄. DPL이 0이면 CPL이 0 (Kernel mode)일 때 접근 가능. 반면 DPL이 3이면 모든 CPL 값이 접근가능. |
P | Segment-Present flag; 0 : main memory에 세그먼트 존재하지 않음 Linux에서는 전체 segment를 disk로 swap out하지 않기 때문에 항상 1로 설정 (flag 47). |
D or B | segment가 code 또는 data를 담느냐에 따라 D 또는 B로 부름. segment offset으로 쓰인 주소가 32bits 길이이면 기본적으로 1로 설정. 16bits 길이이면 0으로 설정 |
AVL | Linux에서는 무시 |
+ 여러 종류의 segment에 따라 segment descriptor 존재
+ 리눅스에서 널리쓰이는 타입들 ↓
▶ Code Segment Descriptor : S flag set. GDT or LDT 존재 가능
▶ Data Segment Descriptor : S flag set. GDT or LDT 존재 가능. Stack segment는 범용 data segment로 구현
▶ Task State Segment Descriptor : GDT에서만 존재. S flag set 0.
현재 프로세스가 CPU 상에 동작중인지에 따라 Type 필드가 11 또는 9.
▶ Local Descriptor Table Descriptor : GDT에서만 존재. Type = 2. S flag = 0.
+ 대표적 형식
Data Segment Descriptor
Code Segment Descriptor
System Segment Descriptor
- fast access to segment descriptor
: logical->linear로 변환 시 더 빠르게 하기 위해 80x86 processor는 추가로 nonprogrammable register 제공.
GDT나 LDT에 접근하지 않고 주소 변환 가능. GDT/LDT는 segmentation register 내용이 변경될 때만 접근
segment selector는 8bytes 길이라서, GDT/LDT 에 존재하는 상대주소를 얻기 위해서는
segment selector의 13-bit index 필드의 값에 8을 곱하여야 함.
(ex) GDT가 0x00020000에 있고, segment selector의 index 필드에 값2가 있으면,
Segment descriptor에 대응되는 주소는 0x00020010이 됨. (0x00020000 + 0x10(=2*8의 hex))
* GDT의 첫 엔트리는 항상 0으로 설정. null segment selector의 logical address가 유효하지 않다 판단되고
이로서 프로세서 exception 발생.
- segmentation unit
역할:
* Segment selector의 TI 필드를 조사하여 어느 Descriptor Table이 Segment Descriptor를 저장하는지 결정
* Segment Selector의 index 필드를 바탕으로 Segment Descriptor의 주소를 계산
* Segment Selector의 Base 필드 값에 logical address의 offset을 더하여 linear address 값 구함
▷ Segmentation in Linux
segmentation: 프로세스마다 다른 linear address 할당
paging : 다른 physical address space에 대해 같은 linear address 매핑 (리눅스 선호)
-> 모든 프로세스가 같은 segment register value를 사용하는것이 메모리 관리하기가 더 단순함
(linear address 공유)
-> RISC 구조에서는 세그멘테이션에 대한 지원이 제한적
*
User Mode ~ user code segment, user data segment
Kernel Mode ~ kernel code segment, kernel data segment
Segment | MACRO | Base | G | Limit | S | Typee | DPL | D/B | P |
user code | __USER_CS | 0x00000000 | 1 | 0xfffff | 1 | 10 | 3 | 1 | 1 |
user data | __USER_DS | 0x00000000 | 1 | 0xfffff | 1 | 2 | 3 | 1 | 1 |
kernel code | __KERNEL_CS | 0x00000000 | 1 | 0xfffff | 1 | 10 | 0 | 1 | 1 |
kernel data | __KERNEL_DS | 0x00000000 | 1 | 0xfffff | 1 | 2 | 0 | 1 | 1 |
segment와 관련된 linear address는 모두 0에서 시작해서 (2^32)-1까지 있음.
-> 모든 프로세스가 커널모드든 유저모드든 같은 logical address를 사용
-> logical address는 linear address와 일치...논리주소의 offset 필드는 선형주소의 값과 일치
CPL이 변경되면 segmentation register 반드시 갱신되어야 함
- the Linux GDT
: 프로세서 개수만큼 GDT 존재하며 모든 GDT는 cpu_gdt_table 배열에 저장 (GDT 주소값과 크기는 cpu_gdt_descr 배열에 저장)
GDT는 18개의 segment descriptor, 14개의 null이나 unused, reserved entries를 갖는다.
(unused는 H/W cache의 32 byte 맞춤)
: 각각의 GDT에 포함된 18개의 segment에는 다음이 존재
-> user code seg, user data seg, kernel code seg, kernel data seg (4)
-> TSS(task state segment)(1)
※TSS에 대응하는 선형주소공간은 kernel data segment에 대응하는 선형주소공간의 작은 부분집합
-> LDT (1) : 보통 모든 프로세스가 공유
-> TLS(Thread-Local Storage)(3) : 멀티쓰레드 응용프로그램에서 로컬 데이터를 각 쓰레드에게 담고자
최대 3개까지 segment 사용하는 메커니즘
-> APM(Advanced Power Management)(3)
-> related to PnP(5)
-> special TSS(1) : for handliing "double fault" exception.
- the Linux LDT
: LDT는 default_ldt 배열에 저장. 5개의 엔트리가 있지만 실질적으로 2개만 커널에 의해 효율적으로 사용됨.
-> call gate for iBCS executable and for Solaris/x86 executables
=> call gate : predefined함수를 불러올 때 CPU의 권한 레벨을 변경하기 위해 8086 마이크로프로세서에서 제공하는 메커니즘
▷ Paging in Hardware
" linear address --[paging unit]--> physical address "
paging unit의 주된 작업 : 선형주소의 접근권한에 관하여 요청받은 접근 타입 확인
page : linear address를 고정 길이 간격으로 그룹화 --> 페이지에서 연속되는 선형주소는 연속되는 물리주소와 매핑
paging unit : RAM을 고정길이로 나뉘어진 page frame(또는 physical page)으로 봄.
page frame: page를 담음. 주 메모리의 구성요소로서 저장영역임.
page table : 선형주소와 물리주소를 매핑하는 자료구조. 주 메모리에 저장되며 paging unit의 동작전에 커널에 의해 초기화
(80386부터 80x86 프로세서들이 paging 지원 ....
control register cr0 의 PG flag --> PG=0이면 선형 주소는 물리주소로 변환됨.)
- regular paging
80386부터 인텔 프로세서의 paging unit은 4KB 페이지를 다룸.
32bit의 선형 주소공간은 3가지 필드로 구성
(1) Directory (2) Table (3) Offset
선형 주소의 변환은 2단계로 구성됨. 각 단계는 변환 테이블을 바탕으로 수행
(1) Page Directory (2) Page Table
==> 2단계 구성...프로세스별로 Page Table에서 요구하는 RAM의 양을 줄이기 위함...
가상메모리 영역이 실제로 프로세스에 의해 사용될 때만 Page Table을 요구하므로 메모리를 줄일 수 있다.
cf. 1단계구성...각 프로세스의 Page Table을 나타내려면 최대 2^20 엔트리가 필요하다. (엔트리가 4바이트면 램이 4MB가 필요)
Page Directory의 물리 주소는 control register cr3에 저장.
Directory 필드는 Page Directory의 진입점을 결정하고, Table 필드는 Page Table의 진입점을 결정.
Offset은 page frame 내에서 상대적인 위치를 결정
+ page directory와 page table은 같은 구조.
Present flag
Access flag : 선택된 페이지가 swapped out 되었을 때 사용. paging unit이 아닌 OS에서 관장
Dirty flag : Page Table에서만 적용...page frame이 쓰기 연산이 수행 시 set
.... Access flag처럼 선택된 페이지가 swapped out 되었을 때 사용
Read/Write flag
User/Supervisor flag
PCD and PWT flags
Page Size flag
Global flag
Field containing the 20 most significant bits of a page frame physical address
- extended paging
확장된 페이징...page frame의 크기를 4KB 대신 4MB로... 큰 규모의 연속된 선형 주소를 연속된 물리 주소로 한번에 변환
커널은 중간 단계의 Page table 없이 변환할 수 있어서 메모리를 절약할 수 있고, TLB 엔트리를 보존할 수 있음.
Page directory 엔트리의 Size 플래그를 설정할 수 있다
--> 32bit의 선형 주소는 2 필드로 구분 :: (1) Directory (2)Offset
Page Directory 엔트리는 일반 페이징에서와 동일
다음은 예외)
- Page Size 반드시 set.
- 20bit 물리주소 필드의 최상위 10비트만 중요함. 물리주소가 4MB기준으로 정렬되기때문에 주소의 나머지 하위 22비트는 0임
* extened paging은 regular paging과 함께 존재 ...cr4 레지스터의 PSE flag를 이용
- hardware protection scheme
: paging unit은 segmentation unit과 다른 보호 정책
: 80x86은 4개의 권한 레벨을 제공하지만 2개의 권한 레벨이 page랑 page table에 연관된다.
(앞서 regular paging의 User/Supervisor 플래그로 권한이 제어되기 때문)
ex. User/Supervisor 플래그가 0 이면, CPL이 3 미만일 때(Kernel mode) 접근 가능. flag가 1 이면 항상 가능
+ book의 example of regular paging
- the physical address extension (PAE) Paging mecharnism
프로세서가 지원하는 RAM의 크기는 주소 버스에 연결된 주소 핀의 수에 의해 제한된다.
80386~팬티엄: 32비트 주소체제
-> 이론상 최대 4GB RAM까지 가능하지만, 실제로 User Mode 프로세스에서 요구되는 선형주소공간때문에 1GB 이상 불가
대형 서버 경우 4GB RAM 이상을 요구-> 팬티엄 Pro부터...Intel 에서 주소 핀(address pin)의 수를 32에서 36으로 증가.
2^36=64GB까지 가능. 그러나, 늘어난 물리 주소는 새롭게 도입된 페이지 매커니즘에서만 이용 가능.
그래서, 팬티엄 Pro 프로세서에서 Intel은 PAE 매커니즘을 도입
(팬티엄3에서 PSE-36 매커니즘을 도입하였으나 리눅스에선 사용안함)
*PAE는 cr4 레지스터의 PAE 플래그를 설정하여 사용할 수 있음
Page Directory의 Page Size(PS) 플래그를 통해 큰 페이지를 설정할 수 있음. (PAE 가능할 때 2MB)
*PAE를 지원하기 위해 페이징 메커니즘이 변경
: 64GB RAM은 2^24개의 page frame으로 구분.
: Page Table 엔트리의 물리 주소 필드는 20->24로 확장.
: PAE page table은 플래그를 위한 12 bit 를 갖고 물리 주소를 위한 24 bit.
: Page Table 엔트리 크기가 32 bit에서 64bit로 됨.
: 4KB의 PAE Page Table 은 1024개가 아닌 512개의 엔트리를 포함.
: 새로운 단계의 Page table 도입 -> Page Directory Pointer Table(PDPT) : 4개의 64bit 엔트리 도입
: cr3 레지스터가 27bit의 PDPT base address 필드를 담고있음.
(PDPT는 RAM의 첫 4GB에 저장되어 32byte 배수로 정렬되기 때문에, 27bit는 테이블의 base address를 나타내기에 충분)
: 선형주소를 4KB 페이지와 매핑할 때(Page Table의 PS는 clear), 32bit의 선형주소는 다음 방법으로 해석됨.
cr3 : PDPT 가리킴
31~30 : PDPT의 4개개의 가능한 엔트리 중 1개 가리킴
29~21 : Page Directory의 512개의 가능한 엔트리 중 1개 가리킴
20~12 : Page Table의 512개의 가능한 엔트리 중 1개 가리킴
11~0 : 4KB page의 offset
: 선형주소를 2MB페이지에 매핑할 때, 32bit의 선형주소는 다음 방법으로 해석됨.
cr3 : PDPT 가리킴
31~30 : PDPT의 4개개의 가능한 엔트리 중 1개 가리킴
29~21 : Page Directory의 512개의 가능한 엔트리 중 1개 가리킴
20~0: 2MB page의 offset
=> cr3가 설정 되면, 4GB RAM 까지 주소 가능. 더 많은 RAM을 주소화하고자 할 땐 cr3에 새로운 값을 넣거나 PDPT의 내용을 바꿔야 한다. 그러나 , PAE의 큰 문제점은 선형 주소가 여전히 32비트이기 때무문에 커널 프로그래머가 RAM의 다른 영역에 매핑하려면 같은 선형 주소를 재사용해야한다는 점이다. 명백하게, PAE는 단지 물리 주소를 처리하는 것이기에 프로세스의 선형 주소 공간을 확장시킨것이 아니다. 또한, 커널만 프로세스의 page table만을 수정할 수 있기때문에, User mode는 4GB이상의 물리 주소 공간을 이용할 수 없다. 반면에, PAE는 커널이 최대 64GB의 RAM을 이용할수 있도록 하기에, 시스템 상의 프로세스의 수를 훨씬 증가시킬 수 있다.
- paging for 64-bit architectures
32bit의 microprocessor에서는 2단계 페이징이 일반적이었으나 64bit 구조에 적합하지 않음 => 추가적인 페이징 레벨 도입 필요
(왜냐하면, 기본 4KB로 페이지 사이즈를 잡으면,2^12 주소를 커버할 수 있으니까 offset은 12bit를 쓰고, 남은 52비트의 선형 주소를 가지고 Table과 Directory 필드를 나눈다고 봐야함. 만약에 64비트 중에 48비트를 주소에 쓰면(2^48=256TB), 48비트-오프셋12비트 = 36비트를 가지고 Table과 Directory 필드를 나눠야함. 두 필드에 각각 18비트씩 두면, 각 프로세스의 Table과 Directory는 반드시 2^18개의 엔트리를 가져야하고 이것은 256000 개 이상의 엔트리가 필요함)
->64비트 플랫폼에서는 추가적인 페이지 단계가 필요하며, 프로세서의 타입에 따라 레벨의 수는 달라질 수 있음.
platform | page size | # of addr bits used | # of paging levels | linear address spliting |
alpha | 8KB | 43 | 3 | 10 + 10 + 10 + 13 |
ia64 | 4KB | 39 | 3 | 9 + 9 + 9 + 12 |
ppc64 | 4KB | 41 | 3 | 10 + 10 + 9 + 12 |
sh86 | 4KB | 41 | 3 | 10 + 10 + 9 + 12 |
x86_64 | 4KB | 48 | 4 | 9 + 9 + 9 + 9 + 12 |
- hardware cache
CPU와 RAM 사이의 속도 불일치를 줄이고자 도입됨. Locality Principle 을 기반.
8086 구조에서 line 이라는 단위를 도입. DRAM과 SRAM 사이 전송.
cache는 라인의 부분집합으로 세분화됨.
direct mapped : 극단적. 주메모리에는 line은 항상 cache의 같은 위치에 저장.
fully associative :메모리에 있는 어떤 라인은 cache 상의 어떤 위치에 저장될수 있음.
N-way set associative : 주 메모리의 어떤 line은 캐시상의 어떤 N line 중 하나에 저장될 수 있음
(ex) 메모리 상의 한 line은 2-way set associative cache의 두개의 다른 라인에 저장될 수 있음
cache unit : paging unit과 main memory 사이에 삽입. hardware cache memory와 cache controller를 포함
> cache memory : memory의 실제 라인을 저장
> cache controller : entry의 배열 ... 한 entry는 cache memory의 한 라인.
entry는 tag와 몇개의 flag로 cache line의 상태를 나타냄.
tag : cache controller가 현재 매핑된 라인의 메모리 위치를 파악할 수 있도록 bits로 구성
메모리 물리주소의 비트는 보통 세 그룹으로 나뉨 : 최상위쪽은 tag, 중간은 cache ctrllr subset index, 최하위는 line의 offset
(controller 너무 길어서 제멋대로 축약... ctrllr)
RAM 메모리 셀에 접근할 때, CPU는 subset index를 물리주소로부터 추출해서, 부분 집합의 모든 라인의 tag과 비교한다.
동일한 tag가 있는 line이 존재하면, CPU는 cache hit을 하고, 그렇지 않은 경우에는 cache miss이다.
cache hit> access type에 따라 cache controller가 취하는 방식이 다름.
(1) read op : ctrllr는 cache line에서 data를 취하여 CPU 레지스터로 전송 (RAM접근ㄴㄴ,CPU는 시간절약)
(2) write op : ctrllr는 두가지 기본 방식 중 하나를 따름
ㄱ. write-through : ctrllr는 write 연산을 위해 효율적으로 cache를 껐다켜며 항상 RAM과 cache line에 write
ㄴ. write-back : cache line만 갱신하고, RAM의 내용은 변경하지 않은 채 유지. write-back 후에 RAM 갱신.
cache ctrllr는 FLUSH 하드웨어 시그널이 발생(대부분 cache miss)하였거나, cache entry의 flushing이
요구되는 명령어를 실행할 때만 cache를 업데이트.
cache miss> 필요에 따라 cache line을 memory에 쓰고, 올바른 line은 RAM에서 cache entry로 가져옴.
멀티프로세서에서는 각 프로세서마다 hardware cache 존재... ~~cache snooping ... hardware 선에서 끝남.
- translation lookaside buffers (TLB)
: 선형 주소 변환을 빠르게 하기 위함
: 선형 주소 처음 사용시, 대응되는 물리주소는 RAM의 Page Table로 느리게 접근함.
물리적 주소는 TLB 엔트리에 저장되고 추후 같은 선형 주소로 참조시 빠르게 변환이 가능함.
: 멀티 프로세서 시스템에서 각 CPU는 고유의 TLB를 갖고 있고, 이를 local TLB라고 함.
Hardware cache에 비해, TLB에 대응되는 엔트리들이 동기화될 필요가 없다.
(∵ CPU에서 동작중인 프로세스는 다른 물리주소의 같은 선형 주소를 결합할 수 있기 때문) ..이상하다..이해...
: CPU의 control register cr3가 수정되면, hardware는 local TLB의 모든 엔트리를 자동적으로 유효화하지않게한다.
(새로운 page table 집합이 쓰이고 TLB는 옛날 데이터를 가리키고 있기 때문)
▷ Paging in Linux
kernel 2.6.10 버전까지는 Linux paging은 3단계 페이징 레벨.
kernel 2.6.11 버전부터는 4단계 페이징 모델이 채택... 4가지 타입의 page table.
-> page global directory / page upper directory / page middle directory / page table
각 부분의 size는 computer architecture에 따라 달라질 수 있음. (dependable)
* 물리주소 확장없는 32비트 구조 : 2단계 페이징이 충분. 이 때, Linux는 page upper와 page middle을 0으로 채워 없앰.
실제로 없애는 것이 아니라 위치를 유지하여, 32비트와 64비트 구조에서 같은 코드가 동작할수 있도록 함.
커널은 upper, middle의 엔트리의 개수를 1개로 설정하고 두 엔트리를 Page Global Directory의 적절한 엔트리와 매핑하도록 함
* 물리주소 확장이 가능한 32비트 구조 : 3단계 페이징.
Linux | 80x86 |
Page Global Directory | Page Diretory Pointer Table |
|
|
Page Middle Directory | Page Directory |
Page Table | Page Table |
* 64비트 구조 : 3단계 또는 4단계 페이징 ... 하드웨어의 선형주소 구분 정도에 따라 단계가 결정됨
+ 리눅스의 프로세스 처리에 페이징이 중요... 선형주소에서 물리주소로의 자동변환은 다음과 같은 설계 목표를 실형가능하도록 함
>각 프로세스에게 다른 물리 주소공간을 할당. 주소공간 에러에 대해 효율적인 보호를 보장.
> page frame(main memory의 물리주소들)으로부터 page(데이터 그룹)를 구분... 페이지 프레임에 동일한 페이지를 저장
... 디스크 절약하고 후에 다른 페이지 프레임을 reload... (virtual machine의 기본 메커니즘)
- the Linear Address Fields
Page Table 핸들링을 쉽게 해주는 매크로들 :
PAGE_SHIFT : OFFSET 필드 길이. PAGE_SIZE 매크로가 페이지 크기 얻고자할 때 쓰임.
PAGE_SIZE = 2^(PAGE_SHIFT). PAGE_SIZE 고려하여 PAGE_MASK 생성.
(EX. PAGE_SHIFT=12 ... PAGE_SIZE=2^12=16^3 ... PAGE_MASK=0XFFFFF000)
PMD_SHIFT : 선형 주소에서의 OFFSET+TABLE 필드의 총 길이. Page Middle Directory Table 엔트리 크기의 로그값과 같음.
PMD_SIZE : Page Middle Directory Table의 하나의 엔트리를 매핑한 영역의 크기.
PMD_MASK : Offset과 Table 필드의 총 비트를 마스킹.
(+. PAE 불가능 ... PMD_SHIFT = 10(table) + 12(offset) = 22
... PMD_SIZE = 2^22 (4MB) ... PMD_MASK=0xffc00000
PAE 가능 ... PMD_SHIFT = 9(table) + 12(offset) = 21
... PMD_SIZE = 2^21 (2MB) ... PMD_MASK=0xffe00000 )
※ 큰 페이지는 마지막 단계의 page table 사용안함 ... LARGE_PAGE_SIZE = PMD_SIZE = 2^(PMD_SHIFT)
PUD_SHIFT : Page Upper Directory 엔트리 크기의 로그값.
PUD_SIZE : Page Upper Directory Table의 하나의 엔트리를 매핑한 영역의 크기.
PUD_MASK : Offset, Table, Middle Air 필드의 총 비트를 마스킹.
※ 8086 에서 PUD_SHIFT = PMD_SHIFT. PUD_SIZE는 4MB 또는 2MB
PGDIR_SHIFT : Page Global Directory 엔트리 크기의 로그값
PGDIR_SIZE : Page Global Directory Table의 하나의 엔트리를 매핑한 영역의 크기.
PGDIR_MASK : Offset, Table, Middle Air, Global Air 필드의 총 비트를 마스킹.
(+. PAE 불가능 ... PGDIR_SHIFT = PMD_SHIFT = PUD_SHIFT = 22
... PMD_SIZE = 2^22 (4MB) ... PMD_MASK=0xffc00000
PAE 가능 ... PMD_SHIFT = 9(middle air) + 9(table) + 12(offset) = 30
... PMD_SIZE = 2^30 (1GB) ... PMD_MASK=0xc0000000)
PTRS_PER_PTE, PTRS_PER_PMD, PTRS_PER_PUD, PTRS_PER_PGD :
각각 entry의 수를 계산.
매크로별 값:
| PAE diabled | PAE enabled |
PTRS_PER_PTE | 1024 | 512 |
PTRS_PER_PMD | 1 | 512 |
PTRS_PER_PUD | 1 | 1 |
PTRS_PER_PGD | 1024 | 4 |
- Page Table Handling
<macro...>
pte_t, pmd_t, pud_t, pgd_t: 각 해당하는 각 테이블의 엔트리의 형식을 나타냄.
PAE가 가능하면 64비트, 그렇지않으면 32비트 데이터 타입.
pgprot_t : PAE가 가능하면 64비트, 그렇지않으면 32비트 데이터 타입. 단일 엔트리에 대해 protection 플래그를 표시.
__pte, __pmd, __pud, __pgd, __pgprot : unsigned integer 타입을 요청받은 타입으로 cast 함.
pte_val, pmd_val, pud_val, pgd_val, pgprot_val : 앞의 4가지 특수한 타입에서 unsigned integer로 cast 함.
※ 커널에서 추가로 제공하는 매크로와 함수 ... page table entry를 read하거나 modify하기 위함.
pte_none, pmd_none, pud_none, pgd_none : 대응된 엔트리 값이 0 이면 1, 아니면 0.
pte_clear, pmd_clear, pud_clear, pgd_clear : 대응된 엔트리를 clear하여 프로세스는 엔트리가 매핑한 선형주소 사용불가
ptep_get_and_clear() : page table entry를 clear하고 이전 값을 반환
set_pte, set_pmd, set_pud, set_pgd : 주어진 값을 page table entry에 write.
set_pte_atomic = set pte. 하지만, PAE가 enable 할 때는 자동적으로 64비트 값이 write.
pte_same(a,b) : 두 페이지 테이블 a,b가 같은 페이지를 가리키면서 같은 접근 권한을 명시하면 1. 아니면 0.
pmd_large(e) : Page Middle Directory entry e가 큰 페이지(2MB 또는 4MB)를 가리키면 1, 아니면 0.
pmd_bad : Page Middle Directory entry가 함수의 입력파라미터로 쓰였는지 확인할 때 사용.
entry가 bad Page Table을 가리킬 때
=> 1) page가 main memory에 있지 않을 때 (present flag cleared)
=> 2) page가 read 만 허가할 때 (read/write flag cleared)
=> 3) accessed 또는 dirty 가 clear 되었을 때
(리눅스에서는 존재하는 모든 pg table이 이 플래그를 설정하도록 함)
pud_bad, pgd bad : 항상 0으로 설정.
(※pte_bad 매크로는 없음. 메인메모리에 존재하지 않거나 접근할 수 없거나 쓸수 없는 페이지를 pg table이 가리키는것도 가능하기 때문.)
pte_present : Present 플래그 또는 Page Size 플래그가 1이면 1.
pmd_present : 대응하는 entry의 present 플래그가 1이면(대응하는 페이지 테이블이 main memory에 load된 상태) 1.
pud_present 와 pgd_present 는 항상 1.
[표] page flag reading functions
function name | description |
pte_user() | reads the User/Supervisor flag |
pte_read() | reads the User/Supervisor flag |
pte_write() | reads the Read/Write flag |
pte_exec() | reads the User/Supervisor flag |
pte_dirty() | reads the Dirty flag |
pte_young() | reads the Accessed flag |
pte_file() | reads the Dirty flag (when the Present flag is cleared and the Dirty flag is set, the page belongs to a non-linear disk file mapping) |
[표] page flag setting functions
function name | description |
mk_pte_huge() | sets the PageSize and Present flags of a page table entry |
pte_wrprotect() | clears the read/write flag |
pte_rdprotect() | clears the user/supervisor flag |
pte_exprotect() | clears the user/supervisor flag |
pte_mkwrite() | sets the read/write flag |
pte_mkread() | sets the user/supervisor flag |
pte_mkexec() | sets the user/supervisor flag |
pte_mkclean() | clears the dirty flag |
pte_mkdirty() | sets the dirty flag |
pte_mkold() | clears the accessed flag (makes the page old) |
pte_mkyoung() | sets the accessed flag (makes the page young) |
pte_modify(p,v) | sets all access rights in a page table entry p to a specified value v |
ptep_set_wrprotect() | like pte_wrprotect(), but acts on a pointer to a page table entry |
ptep_set_access_flags() | if the dirty flag is set, sets the page’s access rights to a specified value and invokes flush_tlb_page() |
ptep_mkdirty() | like pte_mkdirty(), but acts on a pointer to a page table entry |
ptep_test_and_clear_dirty() | like pte_mkclean(), but acts on a pointer to a page table entry and returns the old value of the flag |
ptep_test_and_clear_young() | like pte_mkold(), but acts on a pointer to a page table entry and returns the old value of the flag |
[표] macros acting on page table entries
Macro Name | Description |
pgd_index(addr) | yields the index(relative position) of the entry in the page global directory that maps the linear address addr. |
pgd_offset(mm, addr) | receives as a parameters the address of a memory descriptor cw and a linear address addr. the macro yields the linear address of the entry in a page global directory that corresponds to the address addr; the page global directory is found through a pointer within the memory descriptor. |
pgd_offset_k(addr) | Yields the linear address of the entry in the master kernel Page Global Directory that corresponds to the address addr |
pgd_page(pgd) | Yields the page descriptor address of the page frame containing the PageUpper Directory referred to by the Page Global Directory entry pgd. ln a two-or three-level paging system, this macro is equivalent to pud page() applied to the folded Page Upper Directory entry. |
pud_offset(pgd,addr) | Receives as parameters a pointer pgd to a Page Global Directory entry and a linear address addr. The macro yields the linear address of the entry in a Page Upper Directory that corresponds to addr. ln a two- or three-level paging system, this macro yields pgd, the address of a Page Global Directory entry. |
pud_page(pud) | Yields the linear address of the Page Middle Directory referred to by the Page Upper Directory entry pud. ln a two-level paging system, this macro is equivalent to pmd_page() applied to the folded Page Middle Directory entry. |
pmd_index(addr) | Yields the index (relative position) of the entry in the Page Middle Directory that maps the linear address addr. |
pmd_offset(pud, addr) | Receives as parameters a pointer pud to a Page Upper Directory entry and a linear address addr. The macro yields the address of the entry in a Page Middle Directory that corresponds to addr. ln a two-level paging system, it yields pud, the address of a Page Global Directory entry. |
pmd_page(pmd) | Yields the page descriptor address of the Page Table referred to by the Page Middle Directory entry pmd. ln a trrvo-level paging system, pmd rs actually an entry of a Page Global Directory. |
mk_pte(p, prot) | Receives as parameters the address of a page descriptor p and a group of access rights prot, and builds the corresponding Page Table entry. |
pte_index(addr) | Yields the index (relative position) of the entry in the Page Table that maps the linear address addr. |
pte_offset_kernel(dir, addr) | Yields the linear address of the Page Table that corresponds to the linear address addr mapped by the Page Middle Directory dir. Used only on the master kernel page tables |
pte_offset_map(dir, addr) | Receives as parameters a pointer dir to a Page Middle Directory entry and a Iinear address addr; it yields the linear address of the entry in the Page Table that corresponds to the linear address addr. If the Page Table is kept in high memory, the kernel establishes a temporary kernel mapping, to be released by means of pte_unmap. The macros pte_offset_map_nested and pte_unmap_nested are identical, but they use a different temporary kernel mapping. |
pte_page(x) | Returns the page descriptor address of the page referenced by the Page Table entry x. |
pte_to_pgoff(pte) | Returns the page descriptor address of the page referenced by the Page Table entry x. |
pgoff_to_pte(offset) | Sets up the content of a Page Table entry for a page belonging to a non-linear file memory mapping. |
[표] page allocation functions
function name | description |
pgd_alloc(mm) | Allocates a new Page Global Directory; if PAE is enabled, it also allocates the three children Page Middle Directories that map the User Mode linear addresses. The argument mm (the address of a memory descriptor) IS ignored on the 80x86 architecture. |
pgd_free(pgd) | Releases the Page Global Directory at address pgd; if PE is enabled, it also releases the three Page Middle Directories that map the User Mode linear addresses. |
pud_alloc(mm, pgd, addr) | ln a two- or three-level paging system, this function does nothing: it simply returns the linear address of the Page Global Directory entry pgd. |
pud_free(x) | ln a two- or three-level paging system, this macro does nothing |
pmd_alloc(mm,pud,addr) | Defined so generic three-level paging systems can allocate a new Page Middle Directory for the linear address addr. lf PAE is not enabled, the function simply returns the input parameter pud —that is, the address of the entry in the Page Global Directory. lf PAE is enabled, the function returns the linear address of the Page Middle Directory entry that maps the linear address addr. The argument cw is ignored. |
pmd_free(x) | Does nothing, because Page Middle Directories are allocated and deallocated together with their parent Page Global Directory. |
pte_alloc_map(mm, pmd, addr) | Receives as parameters the address of a Page Middle Directory entry pmd and a linear address addr, and retums the address of the Page Table entry corresponding to addr. If the Page Middle Directory entry is null, the function allocates a new Page Table by invoking pte__al1oc_one( ). If a new Page Table is allocated, the entry corresponding to addr is initialized and the User/Supervisor flag is set. If the Page Table is kept in high memory, the kernel establishes a temporary kernel mapping, to be released by pte_unmap. |
pte_alloc_kernel(mm, pmd, adr) | If the Page Middle Directory entry pmd associated with the address addr is null, the function allocates a new Page Table. It then returns the linear address of the Page Table entry associated with addr. Used only for master kemel page tables. |
pte_free(x) | Releases the Page Table associated with the pte page descriptor pointer. |
pte_free_kernel(pte) | Equivalent to pte_free( ), but used for master kernel page tables. |
clear_page_range(mmu, start, end) | Clears the contents of the page tables of a process from linear address start to end by iteratively releasing its Page Tables and clearing the Page Middle Directory entries |
- physical memory layout
초기화 단계동안 커널은 반드시 physical addresses map 을 만들어야 함.
physical addresses map : 커널이 어느 물리 주소 범위는 사용가능하고, 어느 범위가 사용할 수 없는지 파악
(하드웨어 devices' I/O shared memory 때문이거나 대응되는 page frame이 BIOS 데이터를 갖고 있기 때문)
커널은 다음과 같은 page frame을 reserved 로 봐야 함 :
ㄱ. 사용할수 없는 물리 주소 범위에 있는 것들 ㄴ. 커널 코드와 커널 초기 자료구조를 갖고 있는 것들
-> reserved page를 갖고 있는 page는 절대로 동적으로 할당되거나 disk로 swapped될 수 없음!
Linux kernel ... RAM의 물리주소 0x00100000에서 부터 시작
페이지 프레임의 총 개수는 커널이 어떻게 설정있나에 따라 다름.
대표적 설정은 커널이 3MB RAM 이하로 로드될수 있도록 하는 것.
PC 구조에서 고려해야할 사항들
> page frame 0은 BIOS가 사용
> 물리주소 0x000a0000 ~ 0x000fffff는 보통 BIOS 루틴과 ISA 그래픽 카드의 내부 메모리 매핑 용도로 쓰임.
> 특정 컴퓨터 모델의 경우 추가적인 페이지 프레임을 추가로 사용하기도 함.
부팅 초기 단계에, 커널은 BIOS에게 물리메모리 크기를 질의하여 얻어옴.
요즘엔 커널은 BIOS 절차를 수행하여, 물리주소범위 목록과 대응되는 메모리 타입을 설정.
후에, 커널은 machine_specific_memory_setup() 함수를 수행, 물리 메모리 맵을 만듬.
물론, 커널은 가능한 한 BIOS 리스트 기반으로 맵을 만듬. 가능하지 않을경우, 커널은 관습적인 기본 설정을 따라 만듬
( 기본설정 ... 0x9f (LOWMEMSIZE()) ~ 0x100(HIGH_MEMORY) 범위 내의 모든 page frame은 reserved로 표시 )
128MB RAM 컴퓨터의 대표 설정은 다음 표와 같다.
Start | End | Type |
0x00000000 | 0x0009ffff | usable |
0x000f0000 | 0x000fffff | reserved |
0x00100000 | 0x07feffff | usable |
0x07ff0000 | 0x07ff2fff | ACPI data |
0x07ff3000 | 0x07ffffff | ACPI NVS |
0xffff0000 | 0xffffffff | reserved |
ACPI data 영역 : POST 단계에 BIOS에 의해 쓰여지는 시스템 하드웨어 장치에 관한 정보를 저장.
=> kernel은 이러한 정보를 적절한 커널 자료구조에 복사하고 page frame을 사용가능하도록 한다.
ACPI NVS 영역 : 하드웨어 장치의 ROM 칩과 맵핑.
reserved 영역 : 하드웨어에 의해 BIOS의 ROM 칩에 매핑될 것으로 reserved.
※ BIOS는 몇 몇의 물리 주소 범위 (ex.위 테이블 0x000a0000 ~ 0x000effff)에 대해서는 어떤 정보도 제공하지 않을 수도 있음.
=> 안전하게 하기 위해 이러한 범위를 not usable로 함
machine_specfic_memory_setup() 수행 후 이어서 setup_memory() 수행...
=> 물리 메모리 영역 테이블 분석 및 커널의 물리 메모리 배치를 초기화
[표] 커널의 물리 메모리 배치에 관한 variables
variable name | description |
num_physpages | page frame number of the highest usable page frame |
totalram_pages | total # of usable page frames |
min_low_pfn | page frame number of the 1st usable page frame after the kernel image in RAM |
max_pfn | page frame number of the last usable page frame |
max_low_pfn | page frame number of the last page frame directly mapped by the kernel (low memory) |
totalhigh_pages | total # of page frames not directly mapped by the kernel (high memory) |
highstart_pfn | page frame number of the first page frame not directly mapped by the kernel |
highend_pfn | page frame number of the last page frame not directly mapped by the kernel |
RAM의 첫 1 mega byte를 skip함으로써 kernel이 비연속적인 page frame에 로딩되는 것을 막을 수 있음.
위 그림은 첫 3MB RAM이 어떻게 채워지는지 나타낸것이다. 커널이 3MB 이하의 RAM을 요구한다고 가정.
_text : 물리주소 0x00100000 : 커널 코드의 첫 바이트에 해당하는 주소
_etext : 커널 코드의 마지막과 거의 동일.
커널 데이터는 (1) 초기화 된 것 과 (2) 초기화되지 않은 것으로 구분.
(1) 초기화 된 것 : _etext ~ _edata (2) 초기화 되지 않은 것 : _edata ~ _end
- process page table
0x00000000 ~ 0xbfffffff : User mode 및 kernel mode 둘다 접근 가능
0xc0000000 ~ 0xffffffff : kernel mode에서만 접근 가능
user mode에서는 0xc0000000보다 작은 선형 주소를 사용하고, kernel mode에서는 0xc0000000이상의 선형 주소를 사용하지만, 때에 따라 커널이 데이터를 가져오거나 저장하기 위해 user mode의 선형주소에도 접근해야 함
PAGE_OFFSET 매크로 : 0xc0000000 : 프로세스의 선형 주소 공간에서의 커널이 위치하는 오프셋.
0xc0000000 이하의 선형 주소를 매핑하는 Page Global Directory의 첫 엔트리들의 내용은 프로세스마다 다름.
그러나 나머지 엔트리는 모든 프로세스들이 동일해야하며, master kernel global directory에 있는 해당 엔트리와 동일.
(참고... PAE 사용시 엔트리가 3개, 사용하지 않을 시 엔트리가 768개)
- kernel page table
커널 자신이 사용하기 위한 Page table ... Master kernel global directory
시스템 초기화 후, master kernel global directory의 최상위 entry들이,
시스템 상의 모든 정규 프로세스들의 page global directory에서 대응되는 entry에게 reference model이 됨.
+ 커널이 어떻게 자신의 page table을 초기화 하는가?
1단계. 커널의 code와 data segment가 포함된 제한된 주소 공간(초기 page table)을 만듬.
그리고, 동적 자료 구조를 위해 128KB를 둠.
최소한의 주소 공간은 RAM에 커널을 구동하여 핵심 자료구조를 초기화하기에 충분함
2단계. 커널으 존재하는 모든 RAM을 활용하여 page table을 적절하게 구성한다.
* provisional(임시) kernel page tables
이 단계에서는 PAE 지원 ㄴㄴ
provisional page global directory
... kernel 컴파일 동안 정적으로 초기화
... swapper_pg_dir 변수에 저장
provisional page table
... 어셈블리언어 함수인 startup_32()에서 초기화 (arch/i386/kernel/head.s)
... pg0 부터 시작해서 초기화되지않은 data segment까지(_end)에 저장
커널의 세그먼트들과 임시 커널 테이블, 그리고 128KB 메모리 영역이 8MB의 RAM에 맞다고 가정하면 2개의 페이지테이블 필요
(8MB RAM에 매핑하려면 2개의 pg table이 요구됨)
페이징의 첫단계의 목표 : real mode와 protection mode에서 8MB RAM이 쉽게 주소화할 수 있도록 하는것.
-> 커널은 반드시 0x00000000 ~ 0x007fffff, 0xc0000000 ~ 0xc07fffff 의 선형 주소를
0x00000000~ 0x007fffff에 매핑해야함
->즉, 첫단계의 초기화동안 커널은 선형주소와 물리주소를 같게 주소화하거나,
0xc0000000부터 시작해서 8MB 만큼의 선형주소를 주소화하는 것이다.
커널은 swapper_pg_dir엔트리에 매핑하기 위해 0 으로 모두 채울려고 함.
그러나 0, 1, 0x300(10진수 768), 0x301(10진수 769)는 예외. ->0x300, 0x301 엔트리는 0xc0000000 ~ 0xc07fffff
예외는 다음의 문장들 대로 초기화됨:
> 0, 0x300의 주소필드는 물리주소의 pg0으로 설정
> 1, 0x301의 주소필드는 물리주소의 pg0 다음의 페이지 프레임으로 설정
> Present, Read/Write, User/Supervisor 플래그는 위 예외 모두 set.
> Dirty, PCD, PWD, Page Size 플래그는 위 예외 모두 clear.
startup_32() : paging unit을 가능하게 함.
swapper_pg_dir 을 cr3 제어 레지스터로 불러오고, cr0 레지스터의 PC 플래그를 set함으로써 가능.
* final kernel page table when RAM size is less than 896MB
128MB RAM의 선형주소의 최상위 주소는 여러 가지 매핑이 가능하도록 남겨져있음.
매핑을 위해 남겨진 커널 주소 공간은 1GB-128MB = 896MB
0xc0000000 부터 시작되는 선형주소는 반드시 0부터 시작되는 물리주소로 변환되어야함.
__pa 매크로는 PAGE_OFFSET부터 시작되는 선형주소를 물리 주소로 변환할 때 사용. __va는 반대 경우
master kernel Page Global Directory는 swapper_pg_dir에 저장되어 있고, paging_init()을 통해 초기화
(1) paging_init() : pagetable_init()을 호출하여 page table 엔트리를 적절하게 setup
(2) cr3 레지스터 내의 swapper_pg_dir에 저장
(3) CPU가 PAE를 지원하고 커널이 PAE 지원하면 cr4 레지스터내의 PAE 플래그도 설정
(4) __flush_tlb_all()을 수행하여 모든 TLB 엔트리를 무효화함.
pagetable_init() 수행은 현재의 RAM의 크기와 CPU 모델에 따라 다름.
* final kernel page table when RAM size is between 896MB and 4096MB
이 경우, 커널의 선형 주소 공간에 RAM이 완전히 매핑할 수 없음.
초기화 단계에서 896 MB 만큼을 커널 선형 주소 공간에 매핑하고, 프로그램이 RAM의 다른 부분을 필요로 하면,
다른 선형 주소가 필요로 되는 RAM과 반드시 매핑해야함. -> page table의 값이 변경됨
* final kernel page table when RAM size is more than 4096MB
CPU가 PAE를 지원. RAM이 4GB 초과. 커널이 PAE 지원.
PAE가 36비트 물리주소까지 지원해도 선형주소는 32비트, 3단계 페이징 필요.
- fix-mapped linear addresses
고정 매핑 선형 주소 : (상수) 0xffffc000
고정 매핑 선형 주소는 개념적으론 896MB 이하 때의 kernel page table 방법과 유사하나, 어떤 물리 주소와도 매핑이 가능함
변수 포인터에 관해서 더 효율적 ... 역참조시 메모리를 더 참조해야했던 것과 역참조 전 값 확인을 해야하는 것이 필요 없음
선형주소의 마지막 1GB의 끝에 고정 매핑 선형 주소가 위치.
- handling the Hardware Cache and the TLB
커널이 하드웨어 캐시를 어떻게 최적으로 쓸까?
* handling the hardware cache
캐시는 cache line으로 주소화...
L1_CACHE_BYTES: cache line의 크기를 byte로 줌. 팬티엄 4 전까진 32였으나,이후엔 128
cache의 hit rate를 높이기 위해... + 자료구조에서 가장 자주 쓰이는 필드는 low offset에 위치하여 같은 line에서 cache되게
+ 큰 집합의 자료구조 할당 시, 커널은 메모리에 저장하여 cache line이 균일하게 사용되게
cache synchronization : 8086에선 자동...이러한 프로세서에서 리눅스커널은 하드웨어 cache flushing 수행 ㄴㄴ
그러나, 캐시 동기화를 하지 않는 프로세서에게 cache flushing interface 제공
* handling the TLB
프로세서의 TLB cache의 동기화는 선형주소와 물리주소간의 매핑이 유효하지 않음을 커널이 결정.
커널에서 TLB를 비우지 않는 경우
1) 같은 페이지 테이블을 사용하는 두개의 프로세스 간의 프로세스 전환 시
2) 프로세스와 커널 스레드 사이의 프로세스 전환 시, kernel thread memory descriptor에서 커널 스레드는
자신의 page table을 갖지 않고 직전에 수행된 프로세스의 page table 사용
TLB의 일부를 비워야 하는 경우
1) User mode 프로세스에게 페이지를 할당하고 page table 엔트리에 물리주소를 지정할 때,
해당하는 선형주소의 TLB 엔트리를 비워야 함.
2)multi processor 시스템에서, 같은 페이지 테이블을 사용하는 TLB 엔트리가 여러 CPU에 존재할 때 비워야 함
+ lazy TLB mode : multi-processor에서 쓸데없는 TLB flushing을 피하기 위한 테크닉.
여러 CPU가 동일한 page table을 사용하고, TLB 엔트리가 전부 flush 되야한다면,
TLB flush을 CPU에서 동작중인 커널 스레드를 통해 연기시킬 수도 있음.
==> 구현에 필요한 추가 자료구조 : cpu_tlbstate / cpu_vm_mask
==> lazy mode 동안은 다른프로세스가 TLB를 비우라는 인터럽트를 받지 않음
==> CPU가 커널 스레드를 실행하다가 같은 page table을 사용하는 다른 프로세스로 전환하면 커널은
__flush_tlb를 호출해서 CPU에 있는 비전역 TLB 엔트리를 비움
'NOWS > ULK' 카테고리의 다른 글
| ulk-ch3. processes (0) | 2014.01.29 |
|---|---|
| ulk-ch1. introduction (0) | 2014.01.13 |