가상 머신 작성 방법 (2022)

 (jmeiners.com)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 컴퓨터 내부 동작과 프로그래밍 언어 실행 방식을 이해하기 위해, LC-3 교육용 아키텍처 위에서 어셈블리 프로그램을 실행하는 약 250줄 C 기반 VM을 직접 구현함
  • 구현 대상은 65,536개의 16비트 메모리 위치, 10개 레지스터, 16개 opcode, 조건 플래그, trap routine, 메모리 매핑 레지스터를 갖춘 작은 컴퓨터 모델임
  • 실행 루프는 PC가 가리키는 명령을 읽고 증가시킨 뒤 opcode를 해석해 ADD, LDI, BR, JMP, TRAP 같은 명령을 수행하는 fetch-decode-execute 구조로 동작함
  • 프로그램 로딩은 객체 파일의 첫 16비트 origin을 읽어 메모리에 배치하고, LC-3의 big-endian 형식을 대부분의 현대 컴퓨터에서 쓰는 little-endian 형식에 맞게 바이트 스왑함
  • 키보드 입력과 콘솔 출력은 trap routine과 KBSR/KBDR 메모리 매핑 레지스터로 처리하며, Unix/macOS와 Windows마다 다른 터미널 입력 버퍼링 코드가 필요함

튜토리얼의 목표와 전제

  • LC-3 가상 머신을 직접 구현해 어셈블리 언어 프로그램을 실행하는 과정을 따라감
  • 최종 코드는 C 기준 약 250줄이며, Unix용 lc3.c와 Windows용 lc3-win.c가 제공됨
  • 필요한 전제 지식은 기본적인 C 또는 C++ 읽기와 이진 산술임
  • 전체 코드는 GitHub repo에 있으며, 튜토리얼 자체는 literate program 형식이라 코드 블록을 엮어 최종 소스를 만듦

가상 머신이 하는 일

  • VM은 CPU와 일부 하드웨어 구성요소처럼 동작하는 프로그램임
    • 산술 연산을 수행함
    • 메모리를 읽고 씀
    • I/O 장치와 상호작용함
    • 자체 기계어를 이해해 프로그램을 실행함
  • VM의 목적에 따라 실제 하드웨어를 충실히 재현할 수도 있고, 소프트웨어 개발 편의를 위해 새 가상 아키텍처를 제공할 수도 있음
  • JVM은 표준 실행 플랫폼을 제공하는 VM의 대표 사례이며, JVM이 구현된 장치에서는 Java, Kotlin, Clojure 프로그램을 수정 없이 실행할 수 있음
  • 격리 실행도 VM의 중요한 용도임
    • 가비지 컬렉션에서는 VM이 실행 중인 프로그램 바깥에서 스택과 메모리 참조를 관찰할 수 있음
    • Ethereum smart contract는 파일 시스템, 네트워크, 디스크 등에 접근하지 못하는 VM 안에서 실행됨

LC-3 아키텍처 구성

  • 구현 대상은 대학 컴퓨터 구조와 어셈블리 교육에 쓰이는 LC-3임
  • LC-3 메모리는 65,536개 위치를 가지며, 각 위치는 16비트 값을 저장함
    • 전체 저장 용량은 128KB임
    • C 구현에서는 uint16_t memory[MEMORY_MAX] 배열로 표현함
  • 레지스터는 총 10개임
    • R0~R7: 범용 레지스터 8개
    • PC: 다음에 실행할 명령의 메모리 주소
    • COND: 직전 계산 결과의 조건 플래그
  • LC-3 명령은 모두 16비트이며, 왼쪽 4비트가 opcode임
    • opcode는 16개로 정의됨
    • OP_BR, OP_ADD, OP_LD, OP_ST, OP_JSR, OP_AND, OP_LDR, OP_STR, OP_RTI, OP_NOT, OP_LDI, OP_STI, OP_JMP, OP_RES, OP_LEA, OP_TRAP가 포함됨
  • 조건 플래그는 직전 계산 결과의 부호를 나타냄
    • FL_POS: 양수
    • FL_ZRO: 0
    • FL_NEG: 음수

어셈블리와 기계어

  • LC-3 VM이 실제로 실행하는 것은 사람이 읽는 어셈블리가 아니라 16비트 기계어 명령 배열임
  • 어셈블러는 텍스트로 작성된 LC-3 어셈블리를 16비트 바이너리 명령으로 변환함
  • Hello World 예시는 다음 흐름을 가짐
    • .ORIG x3000: 프로그램이 로드될 메모리 주소 지정
    • LEA R0, HELLO_STR: 문자열 주소를 R0에 적재
    • PUTS: R0이 가리키는 문자열 출력
    • HALT: 프로그램 중지
    • .STRINGZ "Hello World!": 문자열 데이터를 프로그램 안에 저장
  • .ORIG, .STRINGZ는 CPU 명령이 아니라 어셈블러 지시문임
  • 조건과 반복은 BRn LOOP처럼 goto에 가까운 분기 명령으로 구현됨

실행 루프의 핵심 절차

  • VM 실행은 같은 절차를 반복함
    • PC 레지스터 주소에서 명령을 읽음
    • PC를 증가시킴
    • 명령의 상위 4비트에서 opcode를 얻음
    • opcode에 맞는 구현 코드를 실행함
    • 다시 다음 명령을 읽음
  • 기본 시작 주소는 0x3000임
  • 일부 명령은 PC를 직접 바꿔 실행 흐름을 점프시킴
    • 분기와 점프 명령 덕분에 단순히 PC를 증가시키는 구조에서도 루프와 조건 실행이 가능함
  • main 루프는 switch (op)로 opcode별 처리 코드를 호출함
    • OP_ADD, OP_AND, OP_NOT, OP_BR, OP_JMP, OP_JSR, OP_LD, OP_LDI, OP_LDR, OP_LEA, OP_ST, OP_STI, OP_STR, OP_TRAP를 처리함
    • OP_RES, OP_RTI는 사용하지 않는 opcode로 abort() 처리 가능함

명령 구현 방식

  • ADD는 두 값을 더해 목적지 레지스터에 저장하고 조건 플래그를 갱신함
  • ADD에는 두 가지 모드가 있음
    • 레지스터 모드: 두 번째 피연산자를 다른 레지스터에서 읽음
    • 즉시값 모드: 두 번째 피연산자를 명령 하위 5비트 imm5에서 읽음
  • imm5처럼 16비트보다 짧은 값은 sign extension을 거쳐 16비트 값으로 확장해야 함
    • 양수는 0으로 채움
    • 음수는 1로 채워 원래 값을 보존함
  • 레지스터에 값을 쓰는 명령은 update_flags로 R_COND를 갱신함
    • 값이 0이면 FL_ZRO
    • 최상위 비트가 1이면 FL_NEG
    • 그 외에는 FL_POS
  • LDI는 “load indirect” 명령임
    • 명령의 PCoffset9를 sign extension함
    • 현재 PC에 더해 메모리 주소를 얻음
    • 그 위치에 저장된 값을 다시 주소로 사용해 최종 데이터를 읽음
    • 읽은 값을 목적지 레지스터에 저장하고 조건 플래그를 갱신함

주요 명령 집합

  • 산술과 비트 연산
    • ADD: 덧셈
    • AND: 비트 AND
    • NOT: 비트 NOT
  • 제어 흐름
    • BR: 조건 플래그와 명령의 조건 비트를 비교해 PC를 이동함
    • JMP: 지정 레지스터 값을 PC로 설정함
    • RET: 명세상 별도 키워드지만 JMP의 특수 사례임
    • JSR, JSRR: 현재 PC를 R7에 저장하고 서브루틴 위치로 점프함
  • 메모리 읽기
    • LD: PC 기준 offset 주소에서 읽음
    • LDI: 간접 주소를 한 번 더 따라가 읽음
    • LDR: base register와 offset으로 계산한 주소에서 읽음
    • LEA: 유효 주소 자체를 레지스터에 저장함
  • 메모리 쓰기
    • ST: PC 기준 offset 주소에 저장함
    • STI: 간접 주소를 따라가 저장함
    • STR: base register와 offset으로 계산한 주소에 저장함

Trap routine과 I/O

  • LC-3는 공통 작업과 I/O 장치 접근을 위해 trap routine을 제공함
  • trap routine은 LC-3의 운영체제 또는 API처럼 볼 수 있음
  • trap code는 다음처럼 정의됨
    • TRAP_GETC = 0x20: 키보드에서 문자 입력, 터미널에 echo하지 않음
    • TRAP_OUT = 0x21: 문자 출력
    • TRAP_PUTS = 0x22: word string 출력
    • TRAP_IN = 0x23: 문자 입력 후 터미널에 echo
    • TRAP_PUTSP = 0x24: byte string 출력
    • TRAP_HALT = 0x25: 프로그램 중지
  • 공식 LC-3 시뮬레이터에서는 trap routine이 어셈블리로 작성되지만, 이 VM에서는 C 함수로 구현함
  • PUTS는 R0에 저장된 주소부터 시작해 x0000을 만날 때까지 문자를 출력함
    • LC-3 문자열은 C 문자열처럼 1바이트 단위가 아니라 메모리 위치 하나당 문자 하나를 저장함
    • 각 메모리 위치는 16비트이므로 C 출력 시 char로 변환해 출력함
  • HALT trap은 "HALT"를 출력하고 실행 플래그를 0으로 바꿔 VM 루프를 종료함

프로그램 이미지 로딩

  • LC-3 어셈블리 프로그램을 기계어로 변환하면 명령과 데이터 배열을 담은 파일이 만들어짐
  • 객체 파일의 첫 16비트는 프로그램을 메모리 어디에 놓을지 나타내는 origin임
  • 로더는 origin을 먼저 읽고, 나머지 데이터를 origin 주소부터 메모리에 복사함
  • LC-3 프로그램은 big-endian 형식임
    • 대부분의 현대 컴퓨터는 little-endian이므로 로딩한 각 uint16_t에 swap16을 적용함
    • 오래된 PPC Mac 같은 big-endian 컴퓨터에서는 스왑하지 않아야 함
  • read_image는 파일을 바이너리 모드로 열고 read_image_file을 호출한 뒤 파일을 닫음

메모리 매핑 레지스터

  • 일반 레지스터 테이블로 접근하지 않는 특수 레지스터는 특정 메모리 주소에 매핑됨
  • LC-3에서 구현해야 하는 메모리 매핑 레지스터는 두 개임
    • MR_KBSR = 0xFE00: keyboard status register
    • MR_KBDR = 0xFE02: keyboard data register
  • KBSR은 키가 눌렸는지 나타내고, KBDR은 어떤 키가 눌렸는지 저장함
  • GETC는 입력이 들어올 때까지 실행을 막지만, KBSR과 KBDR은 장치 상태를 polling해 입력 대기 중에도 프로그램이 계속 반응할 수 있게 함
  • 메모리 읽기는 직접 배열을 읽지 않고 mem_read를 거침
    • 주소가 MR_KBSR이면 check_key()로 키보드 상태를 확인함
    • 키가 있으면 KBSR의 최상위 비트를 세우고 KBDR에 getchar() 값을 저장함
    • 키가 없으면 KBSR을 0으로 설정함

플랫폼별 터미널 처리

  • 키보드 입력과 터미널 동작을 제대로 처리하려면 플랫폼별 입력 버퍼링 설정이 필요함
  • Linux/macOS/UNIX 구현은 termios, select 등을 사용함
    • canonical mode와 echo를 비활성화함
    • select로 입력 가능 여부를 확인함
  • Windows 구현은 GetStdHandle, GetConsoleMode, SetConsoleMode, _kbhit 등을 사용함
    • echo와 line input을 조정함
    • WaitForSingleObject와 _kbhit으로 키 입력을 확인함
  • 프로그램 시작 시 disable_input_buffering()을 호출하고, 종료 시 restore_input_buffering()을 호출함
  • SIGINT를 받으면 터미널 설정을 복구하고 줄바꿈을 출력한 뒤 종료함

VM 실행과 디버깅

  • VM 빌드 예시는 다음과 같음
gcc lc3.c -o lc3-vm
  • 실행하려면 조립된 LC-3 객체 파일을 인자로 넘김
lc3-vm path/to/2048.obj
  • 예제로 제공되는 객체 파일은 2048.obj와 rogue.obj임
  • 2048 예제는 WASD 키로 조작함
  • 프로그램이 올바르게 동작하지 않으면 명령 구현 오류일 가능성이 큼
    • LC-3 어셈블리 소스를 읽으면서 디버거로 VM 명령을 한 단계씩 실행하는 방식이 권장됨
    • 예상한 명령으로 이동하지 않는 지점이 있으면 해당 명령의 명세와 구현을 다시 확인함

선택 사항: C++ 제네릭 기반 구현

  • 더 짧은 C++ 구현 기법도 선택 사항으로 다룸
  • 여러 명령이 sign extension, PC 기준 offset, 간접 주소 계산 같은 반복 작업을 공유하므로, 명령 실행을 작은 처리 단계들의 파이프라인으로 볼 수 있음
  • C++ 템플릿과 비트 플래그를 사용해 opcode별로 필요한 처리 단계만 컴파일 시 포함함
  • 이 방식은 코드 중복을 줄이고, 각 처리 단계가 칩의 물리적 공간을 차지하는 실제 하드웨어 배선 방식에 더 가까움
  • 아이디어 출처로 Bisqwit’s NES emulator가 언급됨

자료와 기여

  • atul-g가 전체 시스템 동작을 요약하는 reference card를 기여함
  • 다양한 언어 구현은 GitHub topic lc3로 정리됨
    • C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig 등이 포함됨
  • 자신의 구현을 목록에 보이게 하려면 GitHub topic lc3를 붙이면 됨
  • Windows 플랫폼 지원은 inkydragon이 기여함
  • 프로젝트에는 통합 테스트 관련 good first issue가 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 10대 때 커뮤니티 칼리지의 컴퓨터과학 입문 수업에서 간단한 CPU 명령어 집합을 설계하고, 직접 가상 머신과 어셈블러를 만들어 어셈블리 프로그램을 작성·실행해 봤음
    놀랄 만큼 쉬웠고, 컴퓨터가 훨씬 덜 신비롭게 느껴졌음
    FPGA용 실제 CPU 설계부터 간단한 운영체제와 그 위에서 도는 프로그램 작성까지, 이런 방식으로 컴퓨팅의 모든 계층을 배울 수 있을 것 같음
    현대 컴퓨팅이 요구하는 성능과 보안을 빼고 “동작만 하면 된다”는 목표라면 이 분야는 의외로 단순함

    • 재미있는 수업 같고, https://www.nand2tetris.org/나 Charles Petzold의 책 Code와 매우 비슷해 보임
    • 초기의 상상 속 CPU에서 80286 같은 실제 양산 초기 CPU로 넘어가는 순간 복잡도가 급격히 올라감
      기억이 맞다면 최소한 메모리 세그멘테이션과 보호 모드, MMU가 들어감
    • CS 101 수업에도 그런 시스템이 있었음
      PDP에서 BASIC으로 작성된 간단한 컴퓨터/어셈블러였고, 과제 중 하나는 반복문으로 더하기를 해서 단순 곱셈을 구현하는 것이었음
      친구는 그 대신 프로그램을 고쳐서 새 MUL 명령을 만들었고, 선생님은 전혀 좋아하지 않았음
    • 단순한 구성 요소 자체는 정말 쉽지만, 실제 사용자가 컴퓨터에서 보고 만지는 상용 수준 결과물까지는 수백 계층이나 떨어져 있음
      호기심이 있고 배우려는 사람은 이런 기초 계층을 쉽게 익힐 수 있지만, “빨리 돈 벌고 최대한 빨리 취업 가능해지기”를 원하는 사람에게는 그렇지 않음
    • nand2tetris 과정이 바로 그런 걸 하는 것 같음

  • 추천받은 책들:

    1. Smith와 Nair의 Virtual Machines: Versatile Platforms for Systems and Processes — 주제를 포괄적으로 훑는 책처럼 보임
    2. Iain Craig의 Virtual Machines — 언어와 가상 머신을 다루는 좀 더 실습형 책처럼 보임
    3. Bill Blunden의 Virtual Machine Design and Implementation in C/C++ — 구현 중심의 실습서처럼 보임
      위 책들을 읽어 본 사람이 코멘트를 더해 주면 모두에게 도움이 될 듯함
    • 이 주제가 책 한 권으로 개관할 만큼 좁은지 잘 모르겠음
      Nintendo 에뮬레이터, VT-x를 쓰는 하이퍼바이저, 전통적인 멀티태스킹 운영체제, 새 스크립팅 언어의 인터프리터, SQL 질의 최적화기, 정규식 매처, 게임 서버에서 신뢰할 수 없는 플레이어 코드를 돌리는 보안 감시기 등은 고려사항이 거의 겹치지 않아 보이지만 모두 가상 머신임
      문자 셀 터미널 이스케이프 시퀀스를 지정하는 terminfo 형식 안에도 스택 기반 가상 머신이 있음
      깊게 보면 오늘날의 의미에서 컴퓨터를 컴퓨터답게 만드는 것이 가상 머신이고, 튜링의 1936년 Entscheidungsproblem 논문도 가상 머신들이 서로를 흉내 낼 수 있다는 데 걸려 있었음

  • Ben Eater의 브레드보드 CPU 시리즈를 보고 나니, 직접 CPU를 설계하고 에뮬레이트해 보고 싶은 마음뿐임
    앉아서 그걸 설계할 시간을 찾을 수 있으면 좋겠음

  • Brookshear Machine이나 Little Computer 같은 교육용 아키텍처는 실제 아키텍처와 전혀 닮지 않아서 쓸모없음을 넘어 해롭다고 봄
    그런 걸 쓰는 수업을 들은 학생들이, 아무 수업도 듣지 않은 사람보다 컴퓨터를 더 왜곡해서 이해하게 되는 경우를 봤음
    자기 컴퓨터가 어떻게 동작하는지 조금 배우고 싶은 대부분의 사람에게는 운영체제 수업이 더 낫고, 여기서도 짧은 튜토리얼 하나만 할 시간이 있다면 “Writing my own bootloader”를 추천함
    https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
    이 말은 “Write your own VM” 튜토리얼이 나쁘다는 뜻이 아니라, 내 경험상 그걸 할 사람들 대부분에게는 다른 주제가 더 도움이 된다는 뜻임

    • 방금 LC-3를 해 봤고, 현재 프로젝트에서는 LC-3를 부적절한 대상 머신으로 삼아 동적 재컴파일을 조금 배워 보려 함
      컴퓨터 아키텍처를 공부하는 데 LC-3가 왜 나쁜지 더 설명해 줄 수 있을까
      실제 하드웨어와 완전히 다르고 지나치게 단순하다는 건 이해하지만, CPU 에뮬레이터를 작성한다는 관점에서도 나쁜지 궁금함
    • Knuth의 오래된 MIX가 떠오름
      1960년대라면 만들어졌을 법한 10진수 기계였지만 1970년대 이후로는 아무도 만들지 않은 형태임
      그런 시스템은 많은 기본기를 가르칠 수 있지만, https://en.wikipedia.org/wiki/Hacker%27s_Delight에 나오는 기법들은 주로 일반적인 수 표현 방식에 의존하므로 배우기 어려움
    • LC-3의 어떤 점이 특히 마음에 들지 않는지 궁금함
      잘 몰라서 Wikipedia를 잠깐 봤는데, 만화를 보고는 이상한 걸 예상했지만 얼핏 보기에는 그렇게 충격적이지 않았음
      s/360, 약간의 x86, 아주 조금의 ARM 또는 다른 RISC 계열 아키텍처가 섞인 느낌이고, 생략된 부분과 이상한 부분은 많지만 목표는 빠르게 동작하는 구현까지 가는 것으로 보임
      무엇 때문에 교육용으로 “쓸모없음을 넘어 해롭다”고 보는지 알고 싶음
    • 오래된 8비트 아키텍처인 6502나 Z80을 쓰는 걸 추천함
      인도의 많은 컴퓨터과학 수업에서는 아직도 8086/8088을 쓰는 듯함
    • LC-3는 주소 지정 방식이 꽤 특이함
      특히 중간에 있는 PC 상대 워드를 통해 이중 간접 로드를 할 수 있음
      그런데도 뺄셈은 부정에서 만들고, 부정은 NOT과 ADD ,,#-1에서 만들어야 함
      제한된 명령어 인코딩 공간을 생각하면 NOT d,s = XOR d,s,#-1이 더 나은 사용처였을 것 같음

  • 굳이 따지자면 이건 가상 머신이 아니라 에뮬레이터임
    설명적 의미로는 그 용어가 적용될 수 있고, 하드웨어 가상화 이전 시대에는 어느 정도 모호함도 있었지만, 현대에서 “Virtual Machine”의 압도적으로 흔한 용법은 VT-x 같은 하드웨어 가상화 기능을 쓰는 환경을 가리킴

    • 그 용어가 “압도적으로 흔하다”는 데 동의하지 않고, 완전히 맞는 구분이라고도 보기 어려움
      JVM은 널리 배포되어 있고, Ethereum VM은 EVM이라고 불리며, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat...도 BPF와 eBPF를 반복해서 “virtual machines”라고 설명하고, https://webassembly.org/는 “WebAssembly(abbreviated Wasm)는 스택 기반 가상 머신을 위한 이진 명령어 형식”이라고 시작함
      “가상 머신”은 여전히 가상의 기계를 부르는 가장 흔한 말임
      개인적으로는 “fictive machine”, “fictious machine”, “imaginary computer”, “fantastic automaton” 같은 표현이 더 마음에 들지만 채택될 것 같지는 않음
      “가상 머신” 대신 항상 “에뮬레이터”를 쓸 수는 없음
      wasmtime은 에뮬레이터라고 부를 수 있을지 몰라도 WebAssembly 자체를 에뮬레이터라고 하는 건 정확하지 않고, WebAssembly는 wasmtime이 에뮬레이트하는 가상 머신임
      에뮬레이터를 가상 머신이라고 부르는 것도 흔하며, 실행 중인 에뮬레이터 인스턴스 역시 다른 의미의 가상 머신임
      하드웨어 가상화 환경을 “가상 머신”이라고 부르는 것도 타당하고, 이 마지막 의미와 어느 정도 겹침
      현재 환경에서는 그 용법이 압도적으로 흔할 수 있지만, 다른 곳에서도 반드시 그렇지는 않음
    • 정중히 동의하기 어렵음
      가장 순수한 의미에서 가상 머신은 만들어낸 컴퓨터일 뿐이며, 무엇에 쓰일지나 어떻게 동작하는지까지 함의하지 않음
      글에서도 고전 콘솔 에뮬레이션을 예로 들지만, 제시한 정의상 가능한 가상 머신은 훨씬 많다는 점이 분명함
      핵심은 가상 머신이 추상적 개념이고 종류가 아주 많다는 것임
      시뮬레이터, 에뮬레이터, 하이퍼바이저 등이 모두 가상 머신이고, 아직 이름이 붙지 않은 이상한 형태의 가상 머신도 있음
      무례하게 말하려는 게 아니라 오히려 존중하려는 것이고, 배우려는 사람들에게 이 용어를 명확히 하고 싶음
    • 옹호하는 구분은 실제로 존재하지 않는다고 봄
      “가상 머신”은 이유와 무관하게 기계어 또는 바이트코드를 실행하는 모든 소프트웨어에 흔히 쓰임
      가상화를 포함할 수 있지만, Java의 JVM이나 Ruby의 YARV(Yet Another Ruby VM)처럼 언어 런타임에도 자주 쓰임
      오히려 이 용어를 그다지 자주 듣지 않는 영역은 에뮬레이션인데, 이는 현대 에뮬레이터 대부분이 전체 시스템을 에뮬레이트하기보다 에뮬레이트 대상 소프트웨어를 동적 재컴파일하는 기법으로 기울었기 때문이기도 함
    • 이건 JVM, 즉 Java Virtual Machine에서 말하는 의미의 VM임
      Java 정도면 “압도적으로 흔한 용법”에 해당한다고 볼 수 있을 것임
답변달기