Linux2.4でのメモリ管理機構

Size: px

Start display at page:

Download "Linux2.4でのメモリ管理機構"

あかりののした
5 years ago
Views:

1 Linux2.2 on x86 Dec 2001

2 x86 Linux Linux (demand paging, copy on write ) (buddy system, slab allocator)

3 x86 x86 ( ) (required) (= ) ( ) (optional)

4 x86 Physical address( ) Linear address( ) Logical address( ) 16bit 32bit Segmentation Unit Paging Unit

5 Segmentation Segment selector Logical address offset Paging Linear address Directory Table offset Segment Descriptor Linear Address Page Directory Entry Page Table Entry Physical address Global Descriptor Table Linear Address Space CR3 Page Directory Page Table Page

6 x86

7 Linux Linux RISC 1

8 Linux

9 Linux

11 Linux (32bit) 0x x xc text data text bss data bss heap heap *.so *.so mapped mapped stack stack kernel stack File System Swap stack High mem kernel stack 0xc stack vmalloc space 0xffffffff

12 2 (x86) Directory Linear Address Table Offset Page Directory Page Table Page CR3

13 3 (Linux) Linear Address Global Dir Middle Dir Table Offset Page Page Global Directory Page Middle Directory Page Table CR3 x86 Linux PMD (PGD PT )

14 task_struct mm mm_struct mmap pgd vm_area_struct vm_next vm_file vm_start vm_end vm_area_struct vm_next vm_file vm_start vm_end NULL NULL PTE virtual address space PGD PTE PMD Physical memory File system Page cache Swap cache Swap device

15 struct task_struct UNIX u struct mm_struct task_struct struct vm_area_struct (vm_area_struct) AVL mm_struct

16 fork(2) init (kernel/fork.c) 1) mm_struct{} (copy_ mm()) 2) (dup_mmap()) PTE ReadOnly Read : Write : Page Fault

17 execve(2) (fs/exec.c) 1) mm_struct (exec_mmap()) 2) mmap vm_area_struct mmap (do_mmap()) ( ) exit(2) (kernel/exit.c) 1) mm_struct (exit_mm())

18 Page fault Does the address belong to the process address space? Does the access type match the memory Did the exception occur in User Mode? region access right? Legal access: Allocate a new Page frame handle_mm_fault() Illegal access: Send a SIGSEGV signal Kernel bug: Kill the process

19 Write access Address in Memory region In interrupt or kernel thread Page fault Address could Belong to user Mode stack Region is writable Page is present In user mode Region is readable or executable Address is a wrong system call parameter Copy on write Demand Paging Send SIGSEGV Kernel process And kernel Oops Fixup code (typically send SIGSEGV)

20 (1) Is the PTE present? Demand paging invoke do_no_page() Have a file already mapped? invoke do_anonymous_page() Write access? Is the PTE empty? invoke do_swap_page() invoke 2 vma->vm_ops->no_page() 1 3 Allocate a page & 0 clear & Set PTE as writable Mapped ZERO_PAGE & Set PTE as ReadOnly

21 (2) Demand paging 1 invoke page_cache_read() Found the page in page cache? Is the cache valid? Allocate a page & Set PTE & load the file load the file Allocate a page & Set PTE & load the file Is the page to be shared? Set PTE as shared page

22 (3) Demand paging 2 invoke swap_in() Is present vm_ops->swapin? Is swap cache present? Is read access or shared? Make a swap cache Set PTE with Writable&dirty Set PTE

23 (4) 3 Set PTE & aging Is write access? Do nothing Is writable page? invoke do_wp_page() Set PTE with dirty flag 4 Copy on write

24 (5) Copy on write 4 Set PTE as writable &dirty (copy no page) Does multiple Processes refer the page? Allocate a page & Set PTE as writable & Copy data from old page

25 (Demand Paging) CPU Page fault CPU page fault Linux PTE NULL page fault

26 (Copy on Write) CPU Page fault CPU Linux ReadOnly page fault -> Copy on Write

27 (Swapping) CPU Linux CPU

28 LRU (Least Recently Used) LRU x86 ( ) Linux x86 aging ( )

29 The page fault handler must swap in a page swapin_readahead() do_swap_page() swap_in() read_swap_cache_async() A page must be swapped out swap_out() swap_out_process() swap_out_vma() swap_out_pgd() swap_out_pmd() try_to_swap_out() rw_swap_page() brw_page() Low-level swapping function Block device driver function

30 (1) do_try_to_free_pages() try_to_free_pages() -> do_try_to_free_pages() kswapd for (priority = 6;priority; priority--) { while (shrink_mmap(priority,gfp_mask)) { /* */ if ( ) return; } while (shm_swap(priority,gfp_mask)) { /* */ if ( ) return; } while (swap_out(priority,gfp_mask)) { /* */ if ( ) return; } shrink_dcache_memory();/* */ }

31 swap_out() (2) for (counter=nr_tasks/(priority+1);counter;counter--) { int max_cnt=0; struct task_struct *pbest; for (init ) { if ( && > max_cnt) { max_cnt = ; pbest = ; } } swap_out_process(pbest,gfp_mask); }

32 (3) try_to_swap_out() swap_out_process() try_to_swap_out() if ( ) { return;} if ( ) { PTE ; page ; return; } if ( ) { ; PTE ; free_page (); return; } if ( ) { PTE ; free_page (); return; } if ( swapout ) { PTE ; swapout ; free_page(); return; } ; PTE ; ; free_page(); return;

33 kswapd (1 / ) 256*3 while (1) { while ( ) { if (do_try_to_free_pages(gfp_kswapd) { if ( ) { schedule(); } } schedule_timeout(10*hz); } }

34 (1) Buddy system *2 split, coalescing *2 1 (split) 1 (coalescing) External Fragmentation Linux x86 2^0 2^9 10

35 (1) Buddy system 10 kbytes pager Free area list (n *page/block) n= 2^0 n= 2^1 Buddy system 1page 2page 1page 2page merge 2^2page*1 n= 2^2 n= 2^3 4page 8page 4page 8page split

36 (2) Slab allocator Internal Fragmentation e.g.) /etc/slabinfo i-node cache, socket buffer,

37 N page vnode cache active vnodes (2) Slab allocator Page-level allocator (buddy system) coloring area proc cache active procs back end front end unused file cache Slab allocator active files free active free active active NULL Slab data Linked list

38 (2) Slab allocator Linux slab structure 2^{5,6,7,8,9,10,11,12,13,14,15,16,17}bytes DMA /proc/slabinfo

39 Understanding Linux Kernel Daniel P. Bovet & Marco Cesati, O reilly, 2001 UNIX Internals: The New Frontiers Uresh Vahalia, Prentice Hall, 1996 Intel Architecture Developers Manual Vol1,2,3 Intel Corp., 1999

-- Home TOC Slide 1 of 32?? (zone, page), Home TOC Slide 1 of 32

Home TOC -- Date: 2003-10-10, VA Linux Systems Japan Title - Slide Home TOC Title - Slide -- Home TOC Slide 1 of 32?? (zone, page), Home TOC Slide 1 of 32 -- Home TOC Slide 2 of 32 OS alloc_page Home TOC