2017 Usenix Annual Technical Conference

1. Intruduction

  • 낮은 오버헤드로 record / replay를 하려는 많은 시도가 있었다.
    • vm workstation, Simics, UndoDB, TotalView
  • 그러나 많은 한계가 존재
    • 전체 가상머신을 기록하고 재생하며 매우 무겁다
    • 커널 수정이 필요해서 보안, 안전성 문제 야기
    • 맞춤형 하드웨어 필요
  • 이러한 한계를 극복하는 RR 개발
    • 이미 알려져 있지만, 이전 기술들에서 활용되지않은 기술들을 결합
      1. ptrace를 이용한 system call, signal 기록 재생
      2. 한번에 하나의 스레드만을 실행하여 nondeterministic 데이터 경쟁 방지
      3. 비동기 신호, 정확한 순간에 context switching이 이루어지도록 어플리케이션 진행률을 계산하여 CPU 하드웨어 performance 카운터 사용

2. Design

2.1 Summary

  • 상태와 계산의 경계를 식별 후, 경계 내에서 nondeterministic한 모든 소스와 인풋을 기록하고, nondeterministic 소스와 인풋을 재생하여 경계의 모든 계산을 재실행
  • 유저 영역의 모든 세부사항을 record / replay
  • 재생중에는 최소한의 커널상태만 재생됨.
    • ex) 파일 입출력시 파일 디스크립터는 안열리고, 파일시스템 작업은 수행되지 않으며, 유저 영역에서 재생 가능한 것만 재생
  • 경계는 주로 유저 / 커널 사이의 인터페이스로, nondeterministic 인풋과 소스는 주로 시스템콜의 결과나 asynchronous 이벤트의 타이밍

2.2 Avoiding Data Races

  • 서로 다른 스레드가 동일한 메모리에 대한 접근을 경쟁하는것은 nondeterminism의 원인
  • RR은 이를 해결하기 위해 한번에 스레드 하나씩 실행
  • context switching 타이밍이 기록되어야 하는 nondeterministic element
  • parallelism이 낮은 워크로드에 효율적

2.3 System Calls

  • 시스템 콜은 레지스터와 메모리를 수정하여 유저영역으로 반환하기 때문에 기록되어야함
  • ptrace를 이용해 타겟 프로세스의 시스템 콜 모니터링
  • 타겟 스레드가 시스템 콜을 위해 커널에 들어가면 일시정지 되고, RR에 알림
  • RR은 한번에 하나씩 스레드를 실행하기 때문에 시스템 콜 출력 버퍼를 스크래치 메모리로 리다이렉션 시킴
  • 하나의 스레드가 완료되면 스크래치 버퍼의 내용을 유저영역으로 복사하여 경쟁을 제거

  • 재생될 다음 이벤트가 한번에 하나씩 실행될 스레드의 차단된 시스템 콜일때 시스템 콜 명령주소에 임시 Break Point 설정
  • ptrace를 이용해 Break Point에 도달할 때 까지 실행하고, 도달했을 때 PC를 시스템 콜을 지나도록 진행하고, 기록된 레지스터 및 메모리 내용 적용

2.4 Asynchronous Events

  • context switching과 signal 이라는 2가지 비동기 이벤트를 지원해야함
  • signal을 통해 context switching을 강제함
  • HPC를 통해 어플리케이션 진행률을 측정하고, 많은 명령이 진행되면 인터럽트 시그널 발생시킴

2.4.1 nondeterministic performance counters (register)

  • 대부분의 PC는 nondeterministic
  • 다행히 "사용 중지된 조건부 분기(RCB)" 라는 오직 하나의 deterministic한 성능 카운터가 존재
  • 이를 이용해 실행지점을 식별하고, 범용 레지스터의 완전한 상태와 쌍으로 만듦

2.4.2 late interrupt firing

  • 인터럽트 시그널이 즉시 발생하지 않을 수 있음
  • 때문에 먼저 몇가지 이벤트를 트리거 하도록 인터럽트를 프로그래밍함
  • 그 후에 도달하려는 상태에 대한 PC값에 Break Point를 설정하고, RCB 카운트와 범용 레지스터값이 기록된 값과 일치할 때 까지 BP를 반복적으로 실행

2.5 Shared Memory

  • 한번에 하나의 스레드만 스케쥴링 함으로써 RR은 recorded 프로세스가 다른 프로세스, 심지어 커널 드라이버와 메모리를 공유하는것이 가능

2.6 Nondeterministic Instructions

  • RDTSC 명령어는 타임스탬프 카운터를 읽는데, prctl API를 통해 트랩, 에뮬레이션이 가능해 상대적으로 처리하기 용이
  • RDRAND 명령어는 난수를 생성하기 때문에 처리하기 까다롭지만, libstdc++에서도 한곳에서만 사용하기 때문에 명시적으로 패치해서 해결
  • XBEGIN 명령어는 CPU 캐시 상태에 따라 하드웨어 트랜잭션이 성공하거나 실패할 수 있기 때문에 nondeterministic, 다행히 pthreads에서만 사용하기 때문에 사용자 지정 패치를 동적으로 적용
  • CPUID는 실행중인 코어의 인덱스를 반환하는데, glibc의 깊은 동작에 영향을 미침. sched.setaffinity API를 통해 모든 스레드가 특정한 고정코어에서 실행되도록 해서 해결

2.7 Reducing Trace Sizes

  • 메모리 매핑된 파일을 모든 실행파일과 라이브러리에 대해 복사하면 상당한 오버헤드가 발생하기 때문에 RR은 복사대신 하드링크를 사용
  • 이러한 하드링크 복제 작업은 원본이 수정 / 삭제 되지 않는한 본질적으로 시공간에서 자유로움
  • RR은 zlib을 이용해 복제된 파일 및 블록을 제외한 모든 추적데이터를 압축

3. In-process System-call Interception

  • a novel in-process system call interception technique
  • 이전 섹션에서 설명한 시스템 콜 접근 방식은 효과가 있지만 오버헤드가 존재
  • Figure 1과 같이 4가지 context switching 때문
  • 오버헤드를 줄이려면 공통적인 시스템콜을 처리할때 context switching을 피해야함
  • RR에서 공통 시스템 콜을 가로채서, ptrace 트랩을 트리거 하지않고 시스템콜을 수행하고, RR과 공유하는 전용 버퍼에 결과를 기록하는 라이브러리를 타겟 프로세스에 삽입.

3.1 Intercepting System Calls

  • RR은 ptrace 트랩을 통해 알림을 받고 시스템콜을 다시 작성하여 intercept 라이브러리를 호출
  • intercept 라이브러리에서는 시스템 콜 명령과 stub code(5byte)로 대체
  • stub code는 많은 시스템 콜에서 호출 후 결과를 테스트 하는 cmpl $0xfffff001, %eax
  • 공통적인 시스템 콜만 intercept 라이브러리로 리다이렉션 하고 나머지는 일반 ptrace - trapping 시스템 콜을 수행하는것으로 대체

3.2 Selectively Trapping System Calls

  • what is trap?
    • 소프트웨어엥서 발생시키는 인터럽트 (devide by zero, Segmentation Fault)
  • seccomp-bpf를 통해 선택적으로 ptrace 트랩 생성을 회피하는 필터링 생성

  • read 시스템 콜의 예제로 solid border는 intercept 라이브러리, gray box는 커널 코드
  • RR은 모든 시스템 콜에 대해 ptrace 트랩을 트리거하는 프로세스를 대상으로 seccomp-bpf 필터링 적용

3.3 Detecting Blocked System Calls

  • 시스템콜은 때때로 차단될 수 있는데 RR에서 하나씩 실행하는 스레드가 RR에게 알리지 않고 차단되면 전체 recording이 교착상태에 빠질 수 있음
  • 때문에 시스템 콜이 차단될 경우 커널이 RR에게 알리고 스레드를 일시정지 해야함
  • what is perf?
    • 스레드 스케쥴링이 취소될 때 마다 커널이 발생시키는 이벤트
  • intercept 라이브러리에서 perf를 이용해 PERF_COUNT_SW_CONTEXT_SWITCHES를 모니터링 하며 커널이 차단된 스레드에 signal을 보내도록 요청

  • Figure 3은 차단된 시스템 콜 read()를 기록하는 모습
  • 커널은 스레드 스케쥴을 취소하고, perf 이벤트를 트리거하고 스케쥴 재설정, 시스템 콜 block, recorder에 ptrace 알림을 보냄

3.4 Handling Replay

  • record / replay를 동일한 코드를 실행해야 하기 때문에 문제가 생길 수 있음
  • 이를 해결하기 위해 intercept 라이브러리는 시스템 콜이 trace buffer를 직접 쓰도록 리다이렉션
  • 재생하는 동안 추적되지 않은 시스템 콜은 nop로 대체
  • 결과는 이미 trace buffer에 있으므로 post 시스템 콜이 trace buffer에서 output buffer로의 필요한 작업을 수행
  • replay는 trace buffer의 결과를 레지스터에서 읽어야함
  • 제어 흐름이 record /replay간에 완벽히 일치되도록 조건부 이동 명령을 사용
  • 조건은 is_replay 전역변수로 판단
  • 시스템 콜에서 인자를 포인터로 처리하는것은 까다로움
    1. 입력버퍼를 추적버퍼로 복사
    2. 시스템 콜의 인자로 추적버퍼의 포인터 전달
    3. 추적버퍼의 내용을 다시 입력버퍼에 복사

4. Results

4.1 Workloads

  • All tests run on a Dell XPS15 laptop with a quad-core Intel Skylake CPU (8 SMT threads), 16GB RAM and a 512GB SSD using Btrfs in Fedora Core 23 Linux.
  • cp를 제외한 모든 테스팅 타겟은 30초간 실행
  • cp는 단일 스레드 이므로 synchronous한 읽기 및 파일시스템 관련 시스템 콜을 집중적으로 사용
  • make는 dynamoRio를 빌드하여 -j8 옵션을 통해 병렬 테스트
  • octane은 CPU를 많이 사용하는 코드 성능 테스트
  • htmltest는 Firefox html 양식을 테스트
  • sambatest는 UDP 에코 테스트

4.2 Overhead

  • single core : taskset 명령어로 모든 스레드를 single core로 제한하는 오버헤드
  • Record / Replay no intercept : 시스템 콜 차단이 비활성화된 오버헤드
  • Record no cloning : 블록 복제가 비활성화된 오버헤드
  • DynamoRio-null : Dynamic Code Instrumentation 오버헤드 하한 추정치

4.3 Observations

  • make의 오버헤드는 상대적으로 높은데, 2430개의 단기 프로세스를 fork / exec 하기 때문
  • In-process system call interception은 intercept 라이브러리가 로드된 이후에 작업을 시작하지만, 로드가 완료되기전 최소 80개 이상의 system call이 수행되기 때문에 make가 실행하는 단기 프로세스들에는 제한적

  • make 이외의 다른 workload는 매우 안정적인 모습을 보여줌
  • make 이외의 다른 workload에서는 record / replay는 2배도 되지않음
  • cp의 경우 시스템 콜이 더 작은 작업을 수행하기 때문에 일반실행보다 replay가 더 빠를 수 있음
  • octane은 유일하게 멀티코어를 사용하기 때문에 octane의 오버헤드가 RR 전체 오버헤드의 대부분을 차지

  • DynamoRio를 통해 code instrumentation을 한것과 RR의 record를 비교
  • cp는 유저레벨에서 코드를 실행하지 않아서 오버헤드 거의 없음
  • make와 sambatest는 오버헤드가 얼추 유사
  • htmltest의 경우 테스트가 동적으로 생성되기 때문에 DynamoRio의 오버헤드가 현저히 높음

4.4 Storage Space Usage

RR Record List

  1. 메모리 맵 작업에 사용된 복제(또는 하드링크) 파일 (주로 executable 또는 library로 일반적인 추가공간 차지하지 않음)
  2. 복제된 파일 블록
  3. 기타 모든 trace 데이터 (이벤트 메타데이터, 시스템 콜 결과)

  • space consumption은 실행마다 거의 변동 없음
  • workload마다 space consumption rates는 다양하지만, 최신 시스템에서 몇 MB/S 정도는 쉽게 처리 가능하기 때문에 리얼월드에서 trace storage는 문제가 아님

4.5 Memory Usage

  • 프로세스가 메모리를 차지하는 비율을 PSS로 수치화
  • RR이 사용하는 PSS는 주황색
  • cp는 메모리 사용 거의 없음
  • make는 single core 사용만으로도 메모리 사용 줄임
  • octane과 sambatest는 record시 메모리 사용 증가
  • htmltest는 메모리 사용 감소
  • 이러한 다양성은 executable의 복잡성 때문에 설명하기 어렵지만, 타이밍 이슈 또는 OS 메모리 관리 휴리스틱등의 이유 때문일 수 있음
  • replay시 htmltest를 제외하고 record와 비슷
  • htmltest는 test harness를 replay하지 않기 때문에 훨씬 낮음

5. Hardware / Software Design Constraints

5.1 Hardware

  • RR은 deterministic한 하드웨어 performance 카운터 필요
  • 유저 영역에서 관찰된대로 정확한 retired 명령어 수를 계산할 수 있어야 함
  • 일부 X86 CPU 명령어는 nondeterministic한데 이들 중 CPUID, XBEGIN과 같은 명령어들은 패치를 통해 해결
  • ARM에서는 nondeterministic한 "load-linked / store-conditional" 접근 방식을 사용하기 때문에 RR을 ARM으로 포팅 실패
  • X86에서는 유저영역의 상태관점에서 deterministic하기 때문에 문제 없음

5.2 Software

  • RR은 기록되지 않은 프로세스와의 메모리 공유를 하지 않도록 함
  • 시스템 콜을 선택적으로 trap 하기위해 seccomp-bpf 활용
  • 효율적으로 record / replay 하기위해 deterministic 하게 replay되는 경계를 명확히 식별하고, 해당 경계에서 모든 입력 타이밍과 같은 내용을 record / replay하는게 중요
  • RR에서 그 답은 user - kernel 영역 사이의 인터페이스인데 이는 Linux에 적합
  • Windows에서는 user - kernel 영역 사이의 인터페이스가 공개되어있지 않기 때문에 적용이 힘듦

6. Related Works

6.1 Whole System Replay

  • ReVirt는 전체 가상머신을 실행하고 기록하는 초기 프로젝트
  • Vmware Workstation에서 record / replay를 지원했으나 기능 중단
  • QEMU / Xen에서도 일부 record / replay 시도
  • 전체 시스템을 replay 하는것은 비용문제가 큼

6.2 Replaying User-Space with Kernel Support

  • Scribe, dOS, Arnold는 record / replay 기능으로 커널을 확장하여 프로세스 재생
  • 커널에 새 기능을 추가하는것은 위험이 있으므로 record / replay를 커널로 옮기는것은 바람직하지 않음

6.3 Pure User-Space Replay

  • 유저 레벨에서의 record / replay는 MEC, Jockey, liblog등이 존재
  • 이들은 asynchronous 이벤트 타이밍 및 기타 OS 기능을 처리하지 않음
  • PinPlay, iDNA, UndoDB 등은 Code Instrumentation을 이용해 asynchronous 이벤트 타이밍을 record / replay
  • 이들은 Code Instrumentation을 통해 모든 로드를 측정하기 때문에 병렬기록을 지원하지만 오버헤드가 높음

6.4 Higher-Level Replay

  • 언어 레벨에서의 record / replay
  • Dejavu는 JVM에 record / replay 기능 추가
  • Microsoft IntelliTrace는 CLR 바이트 코드를 Instrumentation하여 매개변수 / 함수 리턴값을 record
  • 일반적인 유저레벨에서의 실행을 replay하는것 보다 기능의 범위가 좁음

6.5 Parallel Replay

  • 애초에 매우 어려운 문제
  • PinPlay, iDNA / Nirvana, SMP-ReVirt, QuickRec등이 있지만 오버헤드가 낮은 parallel record에 대한 최고의 방식은 하드웨어 지원으로 보임

7. Future Work

  • 모든 스레드를 single core로 강제 실행하기 때문에 RR 외부에서 나타나는 버그는 재현 불가
  • 커널에서 record / replay 하는것은 context swtiching을 기록하는 비용 절감 가능
  • 유저레벨에서의 record / replay 성능 향상을 위해 커널영역에서 추가할 수 있는 기본 요소를 찾아야함
  • 병렬 프로세스를 기록하는것은 기존 기술에서 영감을 받아 적용 가능해 보임

8. Conclusion

  • Code Instrumentation 없이 낮은 오버헤드로 single core 유저레벨 record / replay 실현
  • 의도된 목적이 아닌 다른 이유로써 sw / hw 기능들을 통해 구현
  • 기존에 없었고 최근에 나타난 seccomp-bpf, Linux 파일 복사 API 이용
  • record / replay가 용이한 프레임워크 Mozilla RR을 오픈소스로 공개
저작자표시

'논문' 카테고리의 다른 글

Processor-Peripheral Interface Modeling  (0) 2021.04.22
kvm: the Linux Virtual Machine Monitor  (1) 2021.01.22

+ Recent posts

티스토리툴바