Cache and buffer management

Size: px

Start display at page:

Download "Cache and buffer management"

영학 신
6 years ago
Views:

1 1 IO-Lite: A unified I/O buffering and caching system By Pai, Druschel, and Zwaenepoel (OSDI, 1999) Presented by Eunsoo Park Operating System Design, Spring 2016

2 Introduction 2 Motivation 범용 OS à 서버의성능악화 à 서버 HW 비용증가 원인 : 다양한 I/O subsystem 들에대한통합부재 결과 à 여러 I/O subsystem 들에서다음과같은문제발생 Redundant data copying Multiple buffering Lack of cross-subsystem optimization Idea 통합된 Buffer Interface 를제공 = IO-Lite 커널의각 I/O Subsystem ( IPC, Filesystem, Network ) 에삽입 Application 에 IO-Lite Library 제공 à 선택적으로사용 효과 freebsd 에구현하여성능측정 àreal Workload 에서 40~80% 성능향상

3 Redundant Data Copying 3 I/O Data path 를따라데이터가이동하면서 Data 복사가여러번발생하는현상 원인 : System 의구조체 & Interface 를사용하기때문에발생 문제 : 성능저하 ( 불필요한 Copy Operation ) User User buffer User User buffer Kernel File Cache Data Copy write Kernel Data Copy Network Buffer write Storage File A Network Interface

4 Multiple Buffering 4 Buffering / Caching 불완전한통합으로인해같은 Data Object 의여러사본이 Memory 에존재하는현상 원인 : 여러 I/O Subsystem 들간의소통부재 영향 : 메모리낭비 à 다른파일캐시의 Hit rate 감소 Web Server Example ( When server sends a file ) File A File Cache File A Web server s buffer File A Network Buffers for one or more connections

5 Lack of cross-subsystem optimizations 5 개별적인 Buffering 방식을사용하여각 I/O subsystem 의최적화기회를잃는현상발생 File A + Checksum File A Network File A + Checksum

6 Original Solution POSIX I/O 6 일반 read() / write() 파일연산 Double Buffering 문제발생 Redundant Page Copying 및 Multiple Buffering mmap() 연산 File Cache 를직접메모리연산으로접근하므로 Copy 발생 X Network Interface 에적용불가 à General 한솔루션필요 Page-aligned 연산 User Sharing Buffer No Copy! Kernel File Cache Storage File A Network

7 Design of IO-Lite 7 I/O Data 에대한자료구조설계 buffer_aggregate + Immutable buffer ( Read-only buffer ) 위추상화로다음과같은시스템일부수정 ( 최대효과 ) Inter-process Communication Applications Filesystem Network Cache Replacement and Paging Subsystem 간최적화기법설계

8 buffer_aggregate 8 모든 OS subsystem 들은 buffer_aggregate 를통해 I/O data 에접근 고성능을요하는 Application 도 buffer_aggregate 를통해 I/O data 에접근하도록선택가능 I/O Subsystem I/O Subsystem I/O I/O Subsystem Subsystem Application buffer_aggregate buffer_aggregate buffer_aggregate I/O data buffer I/O data buffer I/O data buffer I/O data buffer I/O data buffer Non-contiguous Contiguous

9 Immutable Buffer 9 buffer_aggregate 는각 I/O Data buffer 로이루어짐 Buffer 는 Data content 에처음접근할때 Read-only 로할당 각 I/O Susbsytem ( Application 포함 ) 들간의 Synchronization / Protection / Consistency / Fault Isolation 문제들을해결 à Just share! COW! 각 buffer_aggregate 의 buffer 들은 <pointer, length> Tuple 로정렬 File Cache of a file A File A 에접근하는 Application Buffer File A 의일부에접근하는 Network File Cache User Buffer Network Buffer by value buffer_aggregate buffer_aggregate buffer_aggregate by reference File A Buffer

10 Consideration 10 IPC ( Data Transfer between different Protection Domains ) 기존기법들의문제점 Page Remapping 복사보단이동 Semantic : Sender 가후에재사용불가 VM Remapping Overhead 발생 Shared Memory Protection 을따로관리해야하므로사용하는 Layer 에서 Copy 불가피 디자인 Source Intermediate Domains Destination 1. Buffer를위한 VM Area 검색및할당 2. Physical page 할당 3. Page Table 수정 4. Data 작성 5. aggregate로부터 buffer list 생성 6. Read-only 설정 7. 전송 8. VM Area 검색및할당 9. buffer list 로 page mapping 10. list 로부터 aggregate 생성 11. Data 사용 12. VM area 해지 13. Page Table 수정 14. 모든 Receiver 가해지하면 Write 권한재획득및 Buffer 재사용

11 Consideration (cont.) 11 Application fd 에사용가능한추가 API ( IOL_read, IOL_write, and etc. ) 제공 기존 UNIX API 유지 à Backward compatibility 새로운 IOL_read 는요구한 data 를가장많이포함한 buffer_aggregate 반환 à 요청한 Read 양보다덜읽게됨 IOL_write à 해당 Buffer_aggregate 정보로해당 Data object 를대체 Applicatoin Transparency 를제공할수는없으나 ANSI C standard IO library 를제공하여 Language-specific 한성능향상기대할수있음 à Domain 간 IOL_Agg 를 Passing 하는것과기존 System Call Interface 가맞지않음

12 Consideration (cont.) 12 File Sytem IO-Lite file cache Network 각 buffer_aggregate 에 <file-id, offset> 붙임 Write operation 은 Buffer 자체를수정하지않음 (Immutable) à Buffer 를교체 ( buffer_aggregate 수정 ) 특이사항없음 ( IPC 와유사 )

13 Consideration (cont.) 13 Cache Replacement Cache 의교체가발생해도 Sharing 되고있는기존 Cache 를 Eviction 할수없음 à VM Mapping 이끊겨도다른 Process 에서사용하고있을수있음 ( IOL_read, IOL_write ) 전체 VM page 의절반이해당 Cache 와관련한 I/O Data 라면해당 Cache Entry 중하나제거 Paging Cache Eviction 이필요한경우 LRU 에의해선정된 Entry 가제거되고관련된모든 Mapping 을제거 ( * 현재 Linux 에서도적용하고있는사항 ) Cache Entry 가포함하는 Page 가 Paging out 대상으로선정될경우, 위의 Cache entry eviction 이발생 ( 해당 Page 가 Eviction 된다는보장없음 )

14 Cross-subsystem Optimizations 14 각 Buffer 에 Generation number 적용 Buffer 가재할당될때마다 1 씩증가 Immutable 이므로 Generation number 로내용식별가능 File A + Checksum File A Network File A + Checksum

15 Web Server 적용 15 Web Server 동작 여러 Client 들로부터 TCP Connection 승인 HTTP Request Read / Requested Data Write Copy 1. Requested Data 가 File 인경우 File System Read Copy 2. File System Cache 에서발견되지않을경우 Disk Read 기존 Copy 문제솔루션 mmap 으로 Copy 2 해결 Copy 1 해결불가 Connection 마다 Multiple Buffering 문제여전 Third-party CGI Program 사용시 ( 다른 Applicatoin 을통해동적 Data 생성하여 Server 에전달하는 Interface ) IPC 발생 Data 의경우 File System 으로공유하는경우가많음 Copy 발생 Connection 마다이하 Copy 발생

16 Experimental Setup 16 비교군 Apache 널리사용되는 Web Server Flash ( Event-drive HTTP Server ) 저자들에의해만들어진 Server Flash-Lite ( IO-Lite API 를사용하여수정된 Flash ) Workload General : 500 bytes ~ 200 Kbytes File 에 40번의 Request Persistent Connections : Connection Overhead 를제외 CGI : 추가적인 I/O Overhead 를발생시키던 Interface Real Workloads : Rice 대학 CSCI 학부로그사용 Wide Area Network : 0 ~ 256 Slow client 연결시 Throughput 감소측정 Applications : UNIX Program 에 API 포함

17 General Test & Persistent Connections 17 General Flash 에비해 43%, Apache 에비해 137% Bandwidth 증가 5KB 미만 File 접근에대해서는 Flash 와동일성능 Persistent Persistent Connection 에서는 50KB 미만 File 에대해 Flash 와 Flash-Lite 에서성능향상 à Apache 에서는 Connection 을유지했을때의최적화 X

18 기타 Workload 18

19 Discussion 19 mmap 에대해 99 년당시 mmap 은저자의주장대로 Network subsystem 에사용불가? 현재는 Sniff 모드라하여 PACKET_MMAP 가능 à User Buffer 를 Socket buffer 로활용 buffer_aggregate 등추가구현으로인해발생하는 Memory Overhead 미기재 à Cache Policy 등에서도 Memory 사용량이많다는내용은있었으나실험이없음 최신 OS 에서도 IPC Buffer Copy 를없애기위한노력들이존재 à General 하지않고특정 Interface 를위해서만존재 à 굳이 General Solution 이필요한가? KDBus à D-Bus 의 User-Kernel-User-Kernel-User Memory Copy 를 User-Kernel-User 로변경

20 20 Utilizing the IOMMU Scalably ATC 15 Usenix Annual Technical Conference (ATC 15) Presented by Hyemin Lee Operating System Design, Spring 2016

DMA (Direct Memory Access) 21 DMA 는 CPU 의개입없이 I/O Device 로부터데이터의 Read, Write 의기능을제공한다. Physically Contiguous memory 영역을 Mapping 하여 Read, Write 에대한작업을수행한다.

21 DMA (Direct Memory Access) 21 DMA 는 CPU 의개입없이 I/O Device 로부터데이터의 Read, Write 의기능을제공한다. Physically Contiguous memory 영역을 Mapping 하여 Read, Write 에대한작업을수행한다. Operation 이완료시 Interrupt 를발생하여 Transaction 의완료에대한정보를 CPU 에게제공한다. DMA Descriptor : {Address, Size} Physical Map Physically Contiguous Ring Buffer Rx (DMA Read) Ring Buffer Tx (DMA Write) I/O Device Driver Main Memory I/O Device

Block Device DMA Operation 22 DMA transfer 오로지 Physically Contiguous 영역에대한접근만을제공 Block Device(Disk, Etc..) 에서 Physically Non-Contiguous 영역에대한 DMA Operation 이필요시?

22 Block Device DMA Operation 22 DMA transfer 오로지 Physically Contiguous 영역에대한접근만을제공 Block Device(Disk, Etc..) 에서 Physically Non-Contiguous 영역에대한 DMA Operation 이필요시? Physically Non-Contiguous 영역을 Mapping 한 List 를 Scatter-gather DMA Operation 을통해수행 (e.g. Block Device Driver) Scatter-gather DMA bio_vec bio_vec bio_vec bi_sector bi_sector bv_page bv_page bv_page bi_next bi_io_vec bi_size bi_next bi_io_vec bi_size bv_len bv_offset bv_len bv_offset bv_len bv_offset <Block Device Driver>

23 Problem of DMA 23 오로지 Physically contiguous 한영역의 Mapping 만을지원 I/O Device Register 의접근범위로 Host Memory 의 Address Space 가제한됨 (32bit I/O Register - Host 64bit Memory Range) Malicious Device, Buggy Device 에서 Physical Memory 에대한 Direct Access 는 System Security 에문제가발생가능하다. VM 에서 Guest OS 가 Device 에대한접근을직접통제하면안됨 ( 중재자가필요 )

Address) 를 Host 에서할당하여 DMA Operation 으로사용 OS 에서직접관리하므로 Memory

24 IOMMU Concept 24 앞서말했던 DMA 의문제점을해결하기위해 IOMMU (MMU 와비슷한 ) 를제공 Device 에게 Virtually Contiguous 한 Mapping 을제공 IOVA(I/O Virtual Address) 를 Host 에서할당하여 DMA Operation 으로사용 OS 에서직접관리하므로 Memory Protection 기능이나, Inter-OS(Guest OS) 간 isolation 을쉽게보장 IOVA 0xAB32C IOTLB PA 0x5324

Host PM DMA Operation can Corrupt <without IOMMU> Guest VM IOMMU Hypervisor Device Remapping

25 IOMMU in Virtualization 25 Paravirtualization 에서는 Guest 가 Host 의 Physical Memory 를알지못하여 DMA 가어려운문제발생 Guest VM - Guest PM(Corruption 발생가능 ) - Host VM - Host PM Guest VM Guest PM Host VM Host PM DMA Operation can Corrupt <without IOMMU> Guest VM IOMMU Hypervisor Device Remapping <with IOMMU> Device 특정 Guest OS 에게 Device 에대한 DMA 를반드시중재해야된다. Security 문제발생 (inter-os Protection Issue)

(Intra-OS Protection) 따라서, 매번 IOVA 에대한정보가 DMA Transaction 단위로 Invalidation 과 Reallocation 이되어야한다.

26 Motivation 26 High-throughput I/O workloads 에서 Intra-OS Protection 을위한기법에서발생하는병목현상이더욱두드러진다. DMA Transaction 단위로 IOVA 를 Invalidation 하여 Mapping 정보를 Transaction 단위로제공해야한다.(Intra-OS Protection) 따라서, 매번 IOVA 에대한정보가 DMA Transaction 단위로 Invalidation 과 Reallocation 이되어야한다. (transient IOMMU Mapping) Allocate IOVA Global Lock IOVA map physical memory For one DMA Transaction Let driver know IOVA Destroy Mapping Global Lock <Intra-OS Protection>

27 Problem 1. Linux IOTLB Invalidation 27 매 Transaction 당 IOVA 를 Invalidation 할때 IOTLB(Cache for V to P Mapping) 또한 Invalidation 해야할필요가있다. IOTLB 를 Invalidation 하기위해매번 Global Lock 을통한접근이필요하다. (Scalability 를떨어뜨림 ) 현재 Linux System 은 IOVA 에대한 Invalidation 에대한방법으로 Batching 기법을통한 Invalidation 을진행한다 (every 10ms, 250 invalidation requests) 이또한, Global lock 에대한접근에서 21.7% 에 Cycle 소비가일어난다. IOVA3 : Global Lock IOVA0 IOVA1 IOVA2 Core #1 Core #2 Core #3 IOVA4 Invalidation Queue Solution : Batching invalidation requests 를각각 Per-Core 마다수행하도록변경

28 Problem 2. Linux IOVA Allocation 28 In Linux, IOVA Allocator 를통해 IOVA Allocation 을수행 첫번째, 매 DMA Transaction 당 allocation 과 deallocation 을할때 IOVA Allocator 를위한 Global Lock 의획득이필요 (Core 간 Contention 발생 ) 이러한 Global Lock 을통한할당이 Core 간 Contention 을유발해평균 31.7% 의 Cycle 을소비 IOVA 는 Virtual Address Space 내가능한 Packing 하여할당 (Searching Overhead 증가 ) 가능한가장최소의 Page Table 와 PDE 를할당 Why?? 따라서, Top Virtual Address 에서 First Fit 을찾아서할당하게됨 Start Address, Size : Allocated Virtual I/O Address Space : Freed EiovaR : Efficient IOMMU Intra-Operating System Protection Usenix FAST 15 -Find first fit from top of virtual space in constant time

29 Linux Page Table Management 29 왜 Virtual Address 에대한 Packing 이필요한지? IOMMU translation 을위한 Page Table 구조는 4-level radix tree 를사용 Inner Node : page directory Leaf Node : page table Page reclamation requires some kind of synchronization to atomically Determine that the page table is empty Remove the pointer from the parent PDE to it Costly Prevent other cores from creating new entries Invalidating IOTLB 따라서, Linux 는 IOVA 로사용되는 Page Table 에대한 Reclamation 을하지않도록제한따라서, 이로써발생하는 Memory Overhead 를줄이고자 Packing 기법을제안

30 Solution 1. Dynamic Identity Mappings 30 Physical Address 의 Direct Mapping(1:1) 된 Virtual Address 로사용하자 (make use of kernel s V to P mapping) Simple 한 Approach 로 Reusability 를높히고 ( 재할당 Cost 감소 ) Intra-OS 유사기법제공 Re-allocable IOVA 에대해 Same Physical Page 를 Mapping 하여 Reusability 를향상 Map(A) Map(A) Unmap(A) Reference Count :1 Reference Count : 2 Reference Count : 1 Unmap(A) Reference Count : 0 Device cannot access A DIM(dynamic identity mappings) 은 Intra-OS 마다의 Protection 을제공해야된다. 매 Transaction 당 V To P mapping 에대한권한을유지할수있도록제공 1bit : Write bit 제공 Unmapping 시해당권한의 bit 을이전값에맞추어변환 Map(A,R) Map(A,W) Unmap(A,W) A is readable A is readable and writable A is only readable

31 Solution 2. IOVA-kmalloc 31 만약 Kmalloc 과같이 Efficient Confilct-free Allocation 기법을사용하여 IOVA 를할당하면어떨까? IOVA 는 virtual page numbers 의 Range 로서할당을하게된다. (Allocating unique range of integers) 하지만, 일방적인 (Kmalloc, etc..)byte 단위로할당하게된다. For a K page range : kmalloc(k) k 라는 Metric 을통해 PFN 의 Range 로할당받을수있도록변경 Kmalloc(k) k = Range/4096; IOVA Range = [4086B, 4096(B+[R/4096])]

32 Solution 3. Scalable IOVA allocation 32 IOVA 할당에서발생하는 Global Lock 을 Scalable Allocator Mechanism 으로사용한다면? 이전에 IOVA 가 Deallocation 된영역에대한 Per-Core Cache 를적용해보자 다음의내용을반드시고려해야된다 하나의 Core 가 IOVA 를계속할당하고, 다른 core 가이를지속적으로 free 한다면?( unbalance in cache à non-scalable allocator will be invoked ) Magazine* 이라는기법이이에적합한 Solution 을이미제시한다. *Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources (ATC 01)

33 Evaluation 33 실험환경 Client and Server : Dual Intel Xeon E v3 2.4GHz 8-core with 32GB memory Server NIC : NetXtream 2 BCM Gb/s Client NIC : Intel Gb/s Server : Linux Client : Linux Unmodified Kernel Server and Client directly connect to avoid network interference

Evaluation 34 3 - IOVA allocation and IOTLB

34 Evaluation IOVA allocation and IOTLB invalidation technique perform at 93%~95% of No-IOMMU

35 Conclusion & Discussion IOMMU 의장점인 Memory Protection 기능이오히려성능의병목현상을일으킴 Ø 잦은 invalidation 과 IOVA Reallocation 의문제점을정확히지적 Ø Global Lock 으로인한 Host CPU 간 Scalability 문제에대한지적은 Ø 이러한문제를 Simple 한기법을통해해결 High Throughput 을지향하는 I/O Device 에대해서 IOMMU 가과연최선인지? ( 높은오버헤드및비효율적인 Intra-OS Technique)

6.24-9년 6월

6.24-9년 6월 리눅스 환경에서Solid-State Disk 성능 최적화를 위한 디스크 입출력요구 변환 계층 김태웅 류준길 박찬익 Taewoong Kim Junkil Ryu Chanik Park 포항공과대학교 컴퓨터공학과 {ehoto, lancer, cipark}@postech.ac.kr 요약 SSD(Solid-State Disk)는 여러 개의 낸드 플래시 메모리들로 구성된