वर्चुअल मशीन बनाने का तरीका (2022)

 (jmeiners.com)
3 पॉइंट द्वारा GN⁺ 2024-12-28 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • कंप्यूटर के अंदरूनी कामकाज और programming language execution को समझने के लिए, LC-3 educational architecture पर assembly programs चलाने वाली लगभग 250 lines की C-based VM खुद implement की गई
  • implementation target एक छोटा computer model है जिसमें 65,536 16-bit memory locations, 10 registers, 16 opcodes, condition flags, trap routines, और memory-mapped registers हैं
  • execution loop PC द्वारा point की गई instruction को read और increment करता है, फिर opcode interpret करके ADD, LDI, BR, JMP, TRAP जैसी instructions execute करता है; यह fetch-decode-execute structure में काम करता है
  • program loading object file के पहले 16-bit origin को पढ़कर उसे memory में place करता है, और LC-3 के big-endian format को ज़्यादातर modern computers में इस्तेमाल होने वाले little-endian format के अनुसार byte-swap करता है
  • keyboard input और console output trap routines और KBSR/KBDR memory-mapped registers से handle होते हैं, और Unix/macOS व Windows के लिए अलग-अलग terminal input buffering code चाहिए

ट्यूटोरियल का लक्ष्य और पूर्वधारणाएँ

  • LC-3 virtual machine खुद implement करके assembly language programs execute करने की प्रक्रिया को follow करता है
  • final code C के आधार पर लगभग 250 lines का है, और Unix के लिए lc3.c तथा Windows के लिए lc3-win.c दिए गए हैं
  • जरूरी prior knowledge basic C या C++ पढ़ना और binary arithmetic है
  • पूरा code GitHub repo में है, और tutorial खुद literate program format में है, यानी code blocks को जोड़कर final source बनाया जाता है

Virtual machine क्या करती है

  • VM ऐसा program है जो CPU और कुछ hardware components की तरह काम करता है
    • arithmetic operations करती है
    • memory पढ़ती और लिखती है
    • I/O devices से interact करती है
    • अपनी machine language समझकर programs execute करती है
  • VM के purpose के अनुसार यह actual hardware को faithfully reproduce कर सकती है, या software development की सुविधा के लिए नया virtual architecture दे सकती है
  • JVM standard execution platform देने वाली VM का prominent example है, और जिन devices पर JVM implement है, वहाँ Java, Kotlin, Clojure programs बिना modification चल सकते हैं
  • isolated execution भी VM का important use है
    • garbage collection में VM running program के बाहर से stack और memory references observe कर सकती है
    • Ethereum smart contracts ऐसी VM के अंदर execute होते हैं जिसे file system, network, disk आदि तक access नहीं होता

LC-3 architecture की संरचना

  • implementation target LC-3 है, जिसका इस्तेमाल university computer architecture और assembly education में होता है
  • LC-3 memory में 65,536 locations होते हैं, और हर location 16-bit value store करता है
    • total storage capacity 128KB है
    • C implementation में इसे uint16_t memory[MEMORY_MAX] array से represent किया जाता है
  • registers कुल 10 हैं
    • R0~R7: 8 general-purpose registers
    • PC: अगली execute होने वाली instruction का memory address
    • COND: पिछली calculation result का condition flag
  • LC-3 instructions सभी 16-bit होती हैं, और left 4 bits opcode होते हैं
    • 16 opcodes define किए गए हैं
    • इनमें 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 शामिल हैं
  • condition flags पिछली calculation result का sign बताते हैं
    • FL_POS: positive
    • FL_ZRO: 0
    • FL_NEG: negative

Assembly और machine language

  • LC-3 VM असल में human-readable assembly नहीं, बल्कि 16-bit machine instruction array execute करती है
  • assembler text में लिखी LC-3 assembly को 16-bit binary instructions में convert करता है
  • Hello World example का flow इस प्रकार है
    • .ORIG x3000: program load होने वाला memory address specify करता है
    • LEA R0, HELLO_STR: string address को R0 में load करता है
    • PUTS: R0 जिस string को point करता है उसे output करता है
    • HALT: program रोकता है
    • .STRINGZ "Hello World!": string data को program के अंदर store करता है
  • .ORIG, .STRINGZ CPU instructions नहीं, बल्कि assembler directives हैं
  • conditions और loops BRn LOOP जैसी goto के करीब branch instructions से implement होते हैं

Execution loop की core procedure

  • VM execution वही procedure repeat करता है
    • PC register address से instruction पढ़ता है
    • PC increment करता है
    • instruction के upper 4 bits से opcode निकालता है
    • opcode के अनुसार implementation code execute करता है
    • फिर अगली instruction पढ़ता है
  • default start address 0x3000 है
  • कुछ instructions PC को सीधे बदलकर execution flow jump कराती हैं
    • branch और jump instructions की वजह से केवल PC increment करने वाले structure में भी loops और conditional execution possible हैं
  • main loop switch (op) से opcode-wise handling code call करता है
    • 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 handle करता है
    • OP_RES, OP_RTI unused opcodes हैं और इन्हें abort() से handle किया जा सकता है

Instructions implement करने का तरीका

  • ADD दो values जोड़कर destination register में store करता है और condition flags update करता है
  • ADD के दो modes हैं
    • register mode: दूसरा operand किसी दूसरे register से पढ़ता है
    • immediate mode: दूसरा operand instruction के lower 5 bits imm5 से पढ़ता है
  • imm5 जैसी 16-bit से छोटी values को sign extension के जरिए 16-bit value में extend करना होता है
    • positive values 0 से fill होती हैं
    • negative values 1 से fill होती हैं ताकि original value preserve रहे
  • register में value लिखने वाली instructions update_flags से R_COND update करती हैं
    • value 0 हो तो FL_ZRO
    • most significant bit 1 हो तो FL_NEG
    • बाकी cases में FL_POS
  • LDI “load indirect” instruction है
    • instruction के PCoffset9 को sign-extend करता है
    • current PC में जोड़कर memory address निकालता है
    • उस location में stored value को फिर address की तरह इस्तेमाल करके final data पढ़ता है
    • read value को destination register में store करता है और condition flags update करता है

मुख्य instruction set

  • arithmetic और bit operations
    • ADD: addition
    • AND: bitwise AND
    • NOT: bitwise NOT
  • control flow
    • BR: condition flags और instruction के condition bits compare करके PC move करता है
    • JMP: specified register value को PC के रूप में set करता है
    • RET: specification में अलग keyword है, लेकिन JMP का special case है
    • JSR, JSRR: current PC को R7 में store करके subroutine location पर jump करता है
  • memory read
    • LD: PC-relative offset address से read करता है
    • LDI: indirect address को एक बार और follow करके read करता है
    • LDR: base register और offset से calculated address से read करता है
    • LEA: effective address खुद register में store करता है
  • memory write
    • ST: PC-relative offset address में store करता है
    • STI: indirect address follow करके store करता है
    • STR: base register और offset से calculated address में store करता है

Trap routine और I/O

  • LC-3 common tasks और I/O device access के लिए trap routines provide करता है
  • trap routines को LC-3 के operating system या API की तरह देखा जा सकता है
  • trap codes इस तरह define किए गए हैं
    • TRAP_GETC = 0x20: keyboard से character input, terminal में echo नहीं करता
    • TRAP_OUT = 0x21: character output
    • TRAP_PUTS = 0x22: word string output
    • TRAP_IN = 0x23: character input के बाद terminal में echo
    • TRAP_PUTSP = 0x24: byte string output
    • TRAP_HALT = 0x25: program stop
  • official LC-3 simulator में trap routines assembly में लिखे जाते हैं, लेकिन इस VM में इन्हें C functions से implement किया गया है
  • PUTS R0 में stored address से शुरू करके x0000 मिलने तक characters output करता है
    • LC-3 strings C strings की तरह 1-byte units में नहीं, बल्कि एक memory location में एक character store करती हैं
    • हर memory location 16-bit की होती है, इसलिए C output के समय char में convert करके output करता है
  • HALT trap "HALT" output करता है और execution flag को 0 में बदलकर VM loop समाप्त करता है

Program image loading

  • LC-3 assembly program को machine language में convert करने पर instructions और data array वाली file बनती है
  • object file के पहले 16 bits बताते हैं कि program को memory में कहाँ रखना है; यह origin है
  • loader पहले origin पढ़ता है, फिर बाकी data को origin address से memory में copy करता है
  • LC-3 programs big-endian format में होते हैं
    • ज्यादातर modern computers little-endian होते हैं, इसलिए loaded हर uint16_t पर swap16 apply किया जाता है
    • पुराने PPC Mac जैसे big-endian computers में swap नहीं करना चाहिए
  • read_image file को binary mode में खोलता है, read_image_file call करता है, फिर file close करता है

Memory-mapped registers

  • special registers जिन्हें general register table से access नहीं किया जाता, वे specific memory addresses पर mapped होते हैं
  • LC-3 में implement करने वाले memory-mapped registers दो हैं
    • MR_KBSR = 0xFE00: keyboard status register
    • MR_KBDR = 0xFE02: keyboard data register
  • KBSR बताता है कि key press हुई है या नहीं, और KBDR store करता है कि कौन-सी key press हुई
  • GETC input आने तक execution block करता है, लेकिन KBSR और KBDR device state polling करके program को input wait के दौरान भी responsive रहने देते हैं
  • memory read direct array पढ़कर नहीं, बल्कि mem_read से होता है
    • address MR_KBSR हो तो check_key() से keyboard state check करता है
    • key हो तो KBSR का most significant bit set करता है और KBDR में getchar() value store करता है
    • key न हो तो KBSR को 0 set करता है

Platform-specific terminal handling

  • keyboard input और terminal behavior ठीक से handle करने के लिए platform-specific input buffering settings चाहिए
  • Linux/macOS/UNIX implementation termios, select आदि use करता है
    • canonical mode और echo disable करता है
    • select से input available है या नहीं check करता है
  • Windows implementation GetStdHandle, GetConsoleMode, SetConsoleMode, _kbhit आदि use करता है
    • echo और line input adjust करता है
    • WaitForSingleObject और _kbhit से key input check करता है
  • program start पर disable_input_buffering() call किया जाता है, और exit पर restore_input_buffering() call किया जाता है
  • SIGINT मिलने पर terminal settings restore करता है, newline output करता है, फिर exit करता है

VM execution और debugging

  • VM build example इस प्रकार है
gcc lc3.c -o lc3-vm
  • execute करने के लिए assembled LC-3 object file को argument के रूप में pass करें
lc3-vm path/to/2048.obj
  • examples में दिए object files 2048.obj और rogue.obj हैं
  • 2048 example WASD keys से operate होता है
  • program सही से काम न करे तो instruction implementation error होने की संभावना ज्यादा है
    • LC-3 assembly source पढ़ते हुए debugger से VM instructions को step-by-step execute करना recommended है
    • अगर कोई point expected instruction पर move नहीं करता, तो उस instruction की specification और implementation फिर से check करें

Optional: C++ generics-based implementation

  • shorter C++ implementation technique भी optional रूप में cover की गई है
  • कई instructions sign extension, PC-relative offset, indirect address calculation जैसे repeated tasks share करती हैं, इसलिए instruction execution को छोटे processing stages की pipeline की तरह देखा जा सकता है
  • C++ templates और bit flags का इस्तेमाल करके opcode-wise सिर्फ जरूरी processing stages compile time पर include किए जाते हैं
  • यह तरीका code duplication कम करता है, और हर processing stage के chip में physical space लेने वाली real hardware wiring style के ज्यादा करीब है
  • idea source के रूप में Bisqwit’s NES emulator का उल्लेख है

Resources और contributions

  • atul-g ने पूरे system behavior का summary देने वाला reference card contribute किया
  • अलग-अलग language implementations GitHub topic lc3 में organized हैं
    • C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig आदि शामिल हैं
  • अपनी implementation को list में दिखाना हो तो GitHub topic lc3 attach कर दें
  • Windows platform support inkydragon ने contribute किया
  • project में integration tests से जुड़ा good first issue है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-12-28
Hacker News की टिप्पणियां

  • किशोर उम्र में community college की computer science intro class में मैंने एक सरल CPU instruction set design किया था, और खुद virtual machine और assembler बनाकर assembly programs लिखे और चलाकर देखे थे
    यह हैरानी की हद तक आसान था, और कंप्यूटर बहुत कम रहस्यमय लगने लगा
    FPGA के लिए असली CPU design से लेकर एक सरल operating system और उसके ऊपर चलने वाले programs लिखने तक, लगता है इस तरीके से computing की सभी layers सीखी जा सकती हैं
    अगर आधुनिक computing की performance और security जरूरतों को छोड़कर लक्ष्य सिर्फ “चलना चाहिए” हो, तो यह क्षेत्र आश्चर्यजनक रूप से सरल है

    • मजेदार class लगती है, और https://www.nand2tetris.org/ या Charles Petzold की किताब Code से काफी मिलती-जुलती दिखती है
    • शुरुआती काल्पनिक CPU से 80286 जैसे वास्तविक, शुरुआती mass-produced CPU पर जाते ही complexity तेजी से बढ़ जाती है
      अगर मुझे सही याद है, तो कम-से-कम memory segmentation, protected mode और MMU शामिल हो जाते हैं
    • CS 101 class में भी ऐसा system था
      वह PDP पर BASIC में लिखा गया एक simple computer/assembler था, और assignments में से एक था loop से addition करके simple multiplication implement करना
      मेरे दोस्त ने इसकी बजाय program में बदलाव करके एक नया MUL instruction बना दिया, और teacher को यह बिल्कुल पसंद नहीं आया
    • सरल building blocks अपने-आप में सचमुच आसान हैं, लेकिन असली users कंप्यूटर पर जो commercial-grade output देखते और छूते हैं, उससे ये सैकड़ों layers दूर हैं
      जिज्ञासु और सीखने के इच्छुक लोग ऐसी basic layers आसानी से सीख सकते हैं, लेकिन जो लोग “जल्दी पैसा कमाना और जितनी जल्दी हो सके नौकरी के काबिल बनना” चाहते हैं, उनके लिए ऐसा नहीं है
    • लगता है nand2tetris course ठीक यही करता है

  • सुझाई गई किताबें:

    1. Smith और Nair की Virtual Machines: Versatile Platforms for Systems and Processes — विषय का व्यापक overview देने वाली किताब लगती है
    2. Iain Craig की Virtual Machines — languages और virtual machines पर थोड़ी ज्यादा hands-on किताब लगती है
    3. Bill Blunden की Virtual Machine Design and Implementation in C/C++ — implementation-focused practical book लगती है
      अगर इन किताबों को पढ़ चुके लोग comments जोड़ें, तो सबके लिए मददगार होगा
    • मुझे पक्का नहीं कि यह विषय इतना संकरा है कि एक किताब में इसका overview दिया जा सके
      Nintendo emulator, VT-x इस्तेमाल करने वाला hypervisor, traditional multitasking operating system, नई scripting language का interpreter, SQL query optimizer, regex matcher, game server में untrusted player code चलाने वाला security monitor वगैरह के considerations लगभग overlap नहीं करते दिखते, लेकिन ये सब virtual machines हैं
      character-cell terminal escape sequences specify करने वाले terminfo format के अंदर भी stack-based virtual machine है
      गहराई से देखें तो आज के अर्थ में कंप्यूटर को कंप्यूटर जैसा बनाने वाली चीज virtual machine ही है, और Turing का 1936 का Entscheidungsproblem paper भी इस बात पर टिका था कि virtual machines एक-दूसरे की नकल कर सकती हैं

  • Ben Eater की breadboard CPU series देखने के बाद, मेरा बस यही मन है कि खुद CPU design और emulate करके देखूं
    काश बैठकर इसे design करने का समय मिल पाता

  • Brookshear Machine या Little Computer जैसी educational architectures असली architectures जैसी बिल्कुल नहीं होतीं, इसलिए मुझे लगता है कि वे बेकार होने से भी आगे बढ़कर नुकसानदेह हैं
    मैंने देखा है कि ऐसी चीजें इस्तेमाल करने वाली classes लेने वाले students, कोई class न लेने वालों से भी ज्यादा विकृत तरीके से कंप्यूटर को समझने लगते हैं
    अपने computer के काम करने का तरीका थोड़ा सीखना चाहने वाले ज्यादातर लोगों के लिए operating systems class बेहतर है, और यहां भी अगर सिर्फ एक short tutorial का समय हो, तो मैं “Writing my own bootloader” recommend करूंगा
    https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
    इसका मतलब यह नहीं कि “Write your own VM” tutorial खराब है, बल्कि मेरे experience में जो ज्यादातर लोग वह करेंगे, उनके लिए कोई दूसरा topic ज्यादा helpful होगा

    • मैंने अभी-अभी LC-3 किया है, और अपने current project में dynamic recompilation थोड़ा सीखने के लिए LC-3 को एक inappropriate target machine के रूप में इस्तेमाल करने की कोशिश कर रहा हूं
      क्या आप थोड़ा और बता सकते हैं कि computer architecture पढ़ने के लिए LC-3 खराब क्यों है
      मैं समझता हूं कि यह real hardware से बिल्कुल अलग और बहुत ज्यादा simple है, लेकिन CPU emulator लिखने के नजरिए से भी क्या यह खराब है, यह जानना चाहता हूं
    • Knuth का पुराना MIX याद आता है
      यह 1960s में बनाई जा सकने वाली decimal machine थी, लेकिन 1970s के बाद से किसी ने वैसी machine नहीं बनाई
      ऐसे systems बहुत सारी basics सिखा सकते हैं, लेकिन https://en.wikipedia.org/wiki/Hacker%27s_Delight में आने वाली techniques मुख्यतः सामान्य number representation methods पर निर्भर करती हैं, इसलिए उन्हें सीखना कठिन है
    • LC-3 की कौन-सी बात आपको खास तौर पर पसंद नहीं है, यह जानना चाहूंगा
      मुझे ज्यादा जानकारी नहीं थी, इसलिए Wikipedia पर थोड़ा देखा; comic देखकर मुझे कुछ अजीब उम्मीद थी, लेकिन पहली नजर में यह इतना shocking नहीं लगा
      यह s/360, थोड़ा x86, और बहुत थोड़ा ARM या अन्य RISC-family architectures का mix जैसा लगता है; छोड़े गए हिस्से और अजीब बातें बहुत हैं, लेकिन लक्ष्य शायद जल्दी से working implementation तक पहुंचना लगता है
      किस वजह से आप इसे education के लिए “बेकार होने से भी आगे बढ़कर नुकसानदेह” मानते हैं, यह जानना चाहता हूं
    • पुरानी 8-bit architectures जैसे 6502 या Z80 इस्तेमाल करने की सलाह दूंगा
      भारत की कई computer science classes में शायद अब भी 8086/8088 इस्तेमाल होता है
    • LC-3 की addressing mode काफी अजीब है
      खासकर बीच में मौजूद PC-relative word के जरिए double indirect load किया जा सकता है
      फिर भी subtraction को negation से बनाना पड़ता है, और negation को NOT और ADD ,,#-1 से बनाना पड़ता है
      सीमित instruction encoding space को देखते हुए NOT d,s = XOR d,s,#-1 शायद बेहतर उपयोग होता

  • सख्ती से कहें तो यह virtual machine नहीं, बल्कि emulator है
    वर्णनात्मक अर्थ में यह शब्द लागू हो सकता है, और hardware virtualization से पहले के दौर में कुछ हद तक अस्पष्टता भी थी, लेकिन आज के समय में “Virtual Machine” का सबसे आम इस्तेमाल VT-x जैसी hardware virtualization सुविधाओं का उपयोग करने वाले environment के लिए होता है

    • मैं इस बात से सहमत नहीं हूं कि वह शब्द “बहुत ज्यादा आम” है, और इसे पूरी तरह सही विभाजन मानना भी मुश्किल है
      JVM व्यापक रूप से deployed है, Ethereum VM को EVM कहा जाता है, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... भी BPF और eBPF को बार-बार “virtual machines” के रूप में बताता है, और https://webassembly.org/ की शुरुआत इस तरह होती है: “WebAssembly(abbreviated Wasm) stack-based virtual machine के लिए binary instruction format है”
      “virtual machine” अभी भी किसी virtual मशीन को कहने का सबसे आम शब्द है
      निजी तौर पर मुझे “fictive machine”, “fictious machine”, “imaginary computer”, “fantastic automaton” जैसे expressions ज्यादा पसंद हैं, लेकिन उनके अपनाए जाने की संभावना नहीं लगती
      “virtual machine” की जगह हमेशा “emulator” नहीं कहा जा सकता
      wasmtime को शायद emulator कहा जा सकता है, लेकिन WebAssembly खुद को emulator कहना सही नहीं है; WebAssembly वह virtual machine है जिसे wasmtime emulate करता है
      emulator को virtual machine कहना भी आम है, और चल रहा emulator instance भी एक दूसरे अर्थ में virtual machine है
      hardware virtualization environment को “virtual machine” कहना भी सही है, और यह आखिरी अर्थ से कुछ हद तक overlap करता है
      मौजूदा environment में यह उपयोग बहुत ज्यादा आम हो सकता है, लेकिन बाकी जगहों पर जरूरी नहीं कि ऐसा ही हो
    • सम्मानपूर्वक, सहमत होना मुश्किल है
      सबसे शुद्ध अर्थ में virtual machine बस बनाई हुई computer है, और इसमें यह निहित नहीं होता कि उसका उपयोग किस लिए होगा या वह कैसे काम करेगी
      लेख में भी classic console emulation को उदाहरण के तौर पर दिया गया है, लेकिन दी गई परिभाषा के अनुसार संभव virtual machines कहीं ज्यादा हैं, यह स्पष्ट है
      मुख्य बात यह है कि virtual machine एक abstract concept है और इसके प्रकार बहुत अधिक हैं
      simulator, emulator, hypervisor आदि सभी virtual machines हैं, और virtual machines के कुछ अजीब रूप भी हैं जिन्हें अभी नाम नहीं मिला है
      यह बात बेअदबी से नहीं बल्कि सम्मान के साथ कही जा रही है, और सीखने वालों के लिए इस शब्द को स्पष्ट करना चाहता हूं
    • मुझे लगता है कि जिस विभाजन का समर्थन किया जा रहा है, वह वास्तव में मौजूद नहीं है
      “virtual machine” किसी भी ऐसे software के लिए आम तौर पर इस्तेमाल होता है जो कारण चाहे जो भी हो, machine code या bytecode execute करता है
      इसमें virtualization शामिल हो सकता है, लेकिन Java की JVM या Ruby की YARV(Yet Another Ruby VM) जैसी language runtime के लिए भी यह अक्सर इस्तेमाल होता है
      बल्कि जिस क्षेत्र में यह शब्द उतना अक्सर सुनाई नहीं देता, वह emulation है; इसकी एक वजह यह भी है कि आधुनिक emulators में से ज्यादातर पूरे system को emulate करने के बजाय emulated software को dynamic recompilation से चलाने की दिशा में झुक गए हैं
    • यह JVM, यानी Java Virtual Machine में जिस अर्थ में VM कहा जाता है, वही है
      Java जितना व्यापक है, उसे “बहुत ज्यादा आम उपयोग” माना जा सकता है