Mu - subx/010---vm.cc

From 6e1eeeebfb453fa7c871869c19375ce60fbd7413 Mon Sep 17 00:00:00 2001 From: Kartik Agaram Date: Sat, 27 Jul 2019 16:01:55 -0700 Subject: 5485 - promote SubX to top-level --- html/010---vm.cc.html | 477 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 477 insertions(+) create mode 100644 html/010---vm.cc.html (limited to 'html/010---vm.cc.html') diff --git a/html/010---vm.cc.html b/html/010---vm.cc.html new file mode 100644 index 00000000..5266d5ab --- /dev/null +++ b/html/010---vm.cc.html @@ -0,0 +1,477 @@ + + + + +Mu - subx/010---vm.cc + + + + + + + + + + +https://github.com/akkartik/mu/blob/master/subx/010---vm.cc +
+  1 //: Core data structures for simulating the SubX VM (subset of an x86 processor)
+  2 //:
+  3 //: At the lowest level ("level 1") of abstraction, SubX executes x86
+  4 //: instructions provided in the form of an array of bytes, loaded into memory
+  5 //: starting at a specific address.
+  6 
+  7 //:: registers
+  8 //: assume segment registers are hard-coded to 0
+  9 //: no floating-point, MMX, etc. yet
+ 10 
+ 11 :(before "End Types")
+ 12 enum {
+ 13   EAX,
+ 14   ECX,
+ 15   EDX,
+ 16   EBX,
+ 17   ESP,
+ 18   EBP,
+ 19   ESI,
+ 20   EDI,
+ 21   NUM_INT_REGISTERS,
+ 22 };
+ 23 union reg {
+ 24   int32_t i;
+ 25   uint32_t u;
+ 26 };
+ 27 :(before "End Globals")
+ 28 reg Reg[NUM_INT_REGISTERS] = { {0} };
+ 29 uint32_t EIP = 1;  // preserve null pointer
+ 30 :(before "End Reset")
+ 31 bzero(Reg, sizeof(Reg));
+ 32 EIP = 1;  // preserve null pointer
+ 33 
+ 34 :(before "End Help Contents")
+ 35 cerr << "  registers\n";
+ 36 :(before "End Help Texts")
+ 37 put_new(Help, "registers",
+ 38   "SubX currently supports eight 32-bit integer registers. From 0 to 7, they are:\n"
+ 39   "  EAX ECX EDX EBX ESP EBP ESI EDI\n"
+ 40   "ESP contains the top of the stack.\n"
+ 41   "\n"
+ 42   "-- 8-bit registers\n"
+ 43   "Some instructions operate on eight *overlapping* 8-bit registers.\n"
+ 44   "From 0 to 7, they are:\n"
+ 45   "  AL CL DL BL AH CH DH BH\n"
+ 46   "The 8-bit registers overlap with the 32-bit ones. AL is the lowest signicant byte\n"
+ 47   "of EAX, AH is the second lowest significant byte, and so on.\n"
+ 48   "\n"
+ 49   "For example, if EBX contains 0x11223344, then BL contains 0x44, and BH contains 0x33.\n"
+ 50   "\n"
+ 51   "There is no way to access bytes within ESP, EBP, ESI or EDI.\n"
+ 52   "\n"
+ 53   "For complete details consult the IA-32 software developer's manual, volume 2,\n"
+ 54   "table 2-2, \"32-bit addressing forms with the ModR/M byte\".\n"
+ 55   "It is included in this repository as 'modrm.pdf'.\n"
+ 56   "The register encodings are described in the top row of the table, but you'll need\n"
+ 57   "to spend some time with it.\n"
+ 58   "\n"
+ 59   "-- flag registers\n"
+ 60   "Various instructions (particularly 'compare') modify one or more of three 1-bit 'flag'\n"
+ 61   "registers, as a side-effect:\n"
+ 62   "- the sign flag (SF): usually set if an arithmetic result is negative, or\n"
+ 63   "  reset if not.\n"
+ 64   "- the zero flag (ZF): usually set if a result is zero, or reset if not.\n"
+ 65   "- the carry flag (CF): usually set if an arithmetic result overflows by just one bit.\n"
+ 66   "  Useful for operating on unsigned numbers.\n"
+ 67   "- the overflow flag (OF): usually set if an arithmetic result overflows by more than one bit.\n"
+ 68   "  Useful for operating on signed numbers.\n"
+ 69   "The flag bits are read by conditional jumps.\n"
+ 70   "\n"
+ 71   "For complete details on how different instructions update the flags, consult the IA-32\n"
+ 72   "manual (volume 2). There's various versions of it online, such as https://c9x.me/x86,\n"
+ 73   "though of course you'll need to be careful to ignore instructions and flag registers\n"
+ 74   "that SubX doesn't support.\n"
+ 75   "\n"
+ 76   "It isn't simple, but if this is the processor you have running on your computer,\n"
+ 77   "might as well get good at it.\n"
+ 78 );
+ 79 
+ 80 :(before "End Globals")
+ 81 // the subset of x86 flag registers we care about
+ 82 bool SF = false;  // sign flag
+ 83 bool ZF = false;  // zero flag
+ 84 bool CF = false;  // carry flag
+ 85 bool OF = false;  // overflow flag
+ 86 :(before "End Reset")
+ 87 SF = ZF = CF = OF = false;
+ 88 
+ 89 //:: simulated RAM
+ 90 
+ 91 :(before "End Types")
+ 92 const uint32_t SEGMENT_ALIGNMENT = 0x1000000;  // 16MB
+ 93 inline uint32_t align_upwards(uint32_t x, uint32_t align) {
+ 94   return (x+align-1) & -(align);
+ 95 }
+ 96 
+ 97 // Like in real-world Linux, we'll allocate RAM for our programs in disjoint
+ 98 // slabs called VMAs or Virtual Memory Areas.
+ 99 struct vma {
+100   uint32_t start;  // inclusive
+101   uint32_t end;  // exclusive
+102   vector<uint8_t> _data;
+103   vma(uint32_t s, uint32_t e) :start(s), end(e) {}
+104   vma(uint32_t s) :start(s), end(align_upwards(s+1, SEGMENT_ALIGNMENT)) {}
+105   bool match(uint32_t a) {
+106     return a >= start && a < end;
+107   }
+108   bool match32(uint32_t a) {
+109     return a >= start && a+4 <= end;
+110   }
+111   uint8_t& data(uint32_t a) {
+112     assert(match(a));
+113     uint32_t result_index = a-start;
+114     if (_data.size() <= result_index) {
+115       const int align = 0x1000;
+116       uint32_t result_size = result_index + 1;  // size needed for result_index to be valid
+117       uint32_t new_size = align_upwards(result_size, align);
+118       // grow at least 2x to maintain some amortized complexity guarantees
+119       if (new_size < _data.size() * 2)
+120         new_size = _data.size() * 2;
+121       // never grow past the stated limit
+122       if (new_size > end-start)
+123         new_size = end-start;
+124       _data.resize(new_size);
+125     }
+126     return _data.at(result_index);
+127   }
+128   void grow_until(uint32_t new_end_address) {
+129     if (new_end_address < end) return;
+130     // Ugly: vma knows about the global Memory list of vmas
+131     void sanity_check(uint32_t start, uint32_t end);
+132     sanity_check(start, new_end_address);
+133     end = new_end_address;
+134   }
+135   // End vma Methods
+136 };
+137 :(code)
+138 void sanity_check(uint32_t start, uint32_t end) {
+139   bool dup_found = false;
+140   for (int i = 0;  i < SIZE(Mem);  ++i) {
+141     const vma& curr = Mem.at(i);
+142     if (curr.start == start) {
+143       assert(!dup_found);
+144       dup_found = true;
+145     }
+146     else if (curr.start > start) {
+147       assert(curr.start > end);
+148     }
+149     else if (curr.start < start) {
+150       assert(curr.end < start);
+151     }
+152   }
+153 }
+154 
+155 :(before "End Globals")
+156 // RAM is made of VMAs.
+157 vector<vma> Mem;
+158 :(code)
+159 // The first 3 VMAs are special. When loading ELF binaries in later layers,
+160 // we'll assume that the first VMA is for code, the second is for data
+161 // (including the heap), and the third for the stack.
+162 void grow_code_segment(uint32_t new_end_address) {
+163   assert(!Mem.empty());
+164   Mem.at(0).grow_until(new_end_address);
+165 }
+166 void grow_data_segment(uint32_t new_end_address) {
+167   assert(SIZE(Mem) > 1);
+168   Mem.at(1).grow_until(new_end_address);
+169 }
+170 :(before "End Globals")
+171 uint32_t End_of_program = 0;  // when the program executes past this address in tests we'll stop the test
+172 // The stack grows downward. Can't increase its size for now.
+173 :(before "End Reset")
+174 Mem.clear();
+175 End_of_program = 0;
+176 :(code)
+177 // These helpers depend on Mem being laid out contiguously (so you can't use a
+178 // map, etc.) and on the host also being little-endian.
+179 inline uint8_t read_mem_u8(uint32_t addr) {
+180   uint8_t* handle = mem_addr_u8(addr);  // error messages get printed here
+181   return handle ? *handle : 0;
+182 }
+183 inline int8_t read_mem_i8(uint32_t addr) {
+184   return static_cast<int8_t>(read_mem_u8(addr));
+185 }
+186 inline uint32_t read_mem_u32(uint32_t addr) {
+187   uint32_t* handle = mem_addr_u32(addr);  // error messages get printed here
+188   return handle ? *handle : 0;
+189 }
+190 inline int32_t read_mem_i32(uint32_t addr) {
+191   return static_cast<int32_t>(read_mem_u32(addr));
+192 }
+193 
+194 inline uint8_t* mem_addr_u8(uint32_t addr) {
+195   uint8_t* result = NULL;
+196   for (int i = 0;  i < SIZE(Mem);  ++i) {
+197     if (Mem.at(i).match(addr)) {
+198       if (result)
+199         raise << "address 0x" << HEXWORD << addr << " is in two segments\n" << end();
+200       result = &Mem.at(i).data(addr);
+201     }
+202   }
+203   if (result == NULL) {
+204     if (Trace_file) Trace_file.flush();
+205     raise << "Tried to access uninitialized memory at address 0x" << HEXWORD << addr << '\n' << end();
+206     exit(1);
+207   }
+208   return result;
+209 }
+210 inline int8_t* mem_addr_i8(uint32_t addr) {
+211   return reinterpret_cast<int8_t*>(mem_addr_u8(addr));
+212 }
+213 inline uint32_t* mem_addr_u32(uint32_t addr) {
+214   uint32_t* result = NULL;
+215   for (int i = 0;  i < SIZE(Mem);  ++i) {
+216     if (Mem.at(i).match32(addr)) {
+217       if (result)
+218         raise << "address 0x" << HEXWORD << addr << " is in two segments\n" << end();
+219       result = reinterpret_cast<uint32_t*>(&Mem.at(i).data(addr));
+220     }
+221   }
+222   if (result == NULL) {
+223     if (Trace_file) Trace_file.flush();
+224     raise << "Tried to access uninitialized memory at address 0x" << HEXWORD << addr << '\n' << end();
+225     raise << "The entire 4-byte word should be initialized and lie in a single segment.\n" << end();
+226     exit(1);
+227   }
+228   return result;
+229 }
+230 inline int32_t* mem_addr_i32(uint32_t addr) {
+231   return reinterpret_cast<int32_t*>(mem_addr_u32(addr));
+232 }
+233 // helper for some syscalls. But read-only.
+234 inline const char* mem_addr_kernel_string(uint32_t addr) {
+235   return reinterpret_cast<const char*>(mem_addr_u8(addr));
+236 }
+237 inline string mem_addr_string(uint32_t addr, uint32_t size) {
+238   ostringstream out;
+239   for (size_t i = 0;  i < size;  ++i)
+240     out << read_mem_u8(addr+i);
+241   return out.str();
+242 }
+243 
+244 
+245 inline void write_mem_u8(uint32_t addr, uint8_t val) {
+246   uint8_t* handle = mem_addr_u8(addr);
+247   if (handle != NULL) *handle = val;
+248 }
+249 inline void write_mem_i8(uint32_t addr, int8_t val) {
+250   int8_t* handle = mem_addr_i8(addr);
+251   if (handle != NULL) *handle = val;
+252 }
+253 inline void write_mem_u32(uint32_t addr, uint32_t val) {
+254   uint32_t* handle = mem_addr_u32(addr);
+255   if (handle != NULL) *handle = val;
+256 }
+257 inline void write_mem_i32(uint32_t addr, int32_t val) {
+258   int32_t* handle = mem_addr_i32(addr);
+259   if (handle != NULL) *handle = val;
+260 }
+261 
+262 inline bool already_allocated(uint32_t addr) {
+263   bool result = false;
+264   for (int i = 0;  i < SIZE(Mem);  ++i) {
+265     if (Mem.at(i).match(addr)) {
+266       if (result)
+267         raise << "address 0x" << HEXWORD << addr << " is in two segments\n" << end();
+268       result = true;
+269     }
+270   }
+271   return result;
+272 }
+273 
+274 //:: core interpreter loop
+275 
+276 :(code)
+277 // skeleton of how x86 instructions are decoded
+278 void run_one_instruction() {
+279   uint8_t op=0, op2=0, op3=0;
+280   // Run One Instruction
+281   if (Trace_file) {
+282     dump_registers();
+283     // End Dump Info for Instruction
+284   }
+285   uint32_t inst_start_address = EIP;
+286   op = next();
+287   trace(Callstack_depth+1, "run") << "0x" << HEXWORD << inst_start_address << " opcode: " << HEXBYTE << NUM(op) << end();
+288   switch (op) {
+289   case 0xf4:  // hlt
+290     EIP = End_of_program;
+291     break;
+292   // End Single-Byte Opcodes
+293   case 0x0f:
+294     switch(op2 = next()) {
+295     // End Two-Byte Opcodes Starting With 0f
+296     default:
+297       cerr << "unrecognized second opcode after 0f: " << HEXBYTE << NUM(op2) << '\n';
+298       exit(1);
+299     }
+300     break;
+301   case 0xf2:
+302     switch(op2 = next()) {
+303     // End Two-Byte Opcodes Starting With f2
+304     case 0x0f:
+305       switch(op3 = next()) {
+306       // End Three-Byte Opcodes Starting With f2 0f
+307       default:
+308         cerr << "unrecognized third opcode after f2 0f: " << HEXBYTE << NUM(op3) << '\n';
+309         exit(1);
+310       }
+311       break;
+312     default:
+313       cerr << "unrecognized second opcode after f2: " << HEXBYTE << NUM(op2) << '\n';
+314       exit(1);
+315     }
+316     break;
+317   case 0xf3:
+318     switch(op2 = next()) {
+319     // End Two-Byte Opcodes Starting With f3
+320     case 0x0f:
+321       switch(op3 = next()) {
+322       // End Three-Byte Opcodes Starting With f3 0f
+323       default:
+324         cerr << "unrecognized third opcode after f3 0f: " << HEXBYTE << NUM(op3) << '\n';
+325         exit(1);
+326       }
+327       break;
+328     default:
+329       cerr << "unrecognized second opcode after f3: " << HEXBYTE << NUM(op2) << '\n';
+330       exit(1);
+331     }
+332     break;
+333   default:
+334     cerr << "unrecognized opcode: " << HEXBYTE << NUM(op) << '\n';
+335     exit(1);
+336   }
+337 }
+338 
+339 inline uint8_t next() {
+340   return read_mem_u8(EIP++);
+341 }
+342 
+343 void dump_registers() {
+344   ostringstream out;
+345   out << "registers before: ";
+346   for (int i = 0;  i < NUM_INT_REGISTERS;  ++i) {
+347     if (i > 0) out << "; ";
+348     out << "  " << i << ": " << std::hex << std::setw(8) << std::setfill('_') << Reg[i].u;
+349   }
+350   out << " -- SF: " << SF << "; ZF: " << ZF << "; CF: " << CF << "; OF: " << OF;
+351   trace(Callstack_depth+1, "run") << out.str() << end();
+352 }
+353 
+354 //: start tracking supported opcodes
+355 :(before "End Globals")
+356 map</*op*/string, string> Name;
+357 map</*op*/string, string> Name_0f;
+358 map</*op*/string, string> Name_f3;
+359 map</*op*/string, string> Name_f3_0f;
+360 :(before "End One-time Setup")
+361 init_op_names();
+362 :(code)
+363 void init_op_names() {
+364   put(Name, "f4", "halt (hlt)");
+365   // End Initialize Op Names
+366 }
+367 
+368 :(before "End Help Special-cases(key)")
+369 if (key == "opcodes") {
+370   cerr << "Opcodes currently supported by SubX:\n";
+371   for (map<string, string>::iterator p = Name.begin();  p != Name.end();  ++p)
+372     cerr << "  " << p->first << ": " << p->second << '\n';
+373   for (map<string, string>::iterator p = Name_0f.begin();  p != Name_0f.end();  ++p)
+374     cerr << "  0f " << p->first << ": " << p->second << '\n';
+375   for (map<string, string>::iterator p = Name_f3.begin();  p != Name_f3.end();  ++p)
+376     cerr << "  f3 " << p->first << ": " << p->second << '\n';
+377   for (map<string, string>::iterator p = Name_f3_0f.begin();  p != Name_f3_0f.end();  ++p)
+378     cerr << "  f3 0f " << p->first << ": " << p->second << '\n';
+379   cerr << "Run `subx help instructions` for details on words like 'r32' and 'disp8'.\n"
+380           "For complete details on these instructions, consult the IA-32 manual (volume 2).\n"
+381           "There's various versions of it online, such as https://c9x.me/x86.\n"
+382           "The mnemonics in brackets will help you locate each instruction.\n";
+383   return 0;
+384 }
+385 :(before "End Help Contents")
+386 cerr << "  opcodes\n";
+387 
+388 //: Helpers for managing trace depths
+389 //:
+390 //: We're going to use trace depths primarily to segment code running at
+391 //: different frames of the call stack. This will make it easy for the trace
+392 //: browser to collapse over entire calls.
+393 //:
+394 //: Errors will be at depth 0.
+395 //: Warnings will be at depth 1.
+396 //: SubX instructions will occupy depth 2 and up to Max_depth, organized by
+397 //: stack frames. Each instruction's internal details will be one level deeper
+398 //: than its 'main' depth. So 'call' instruction details will be at the same
+399 //: depth as the instructions of the function it calls.
+400 :(before "End Globals")
+401 extern const int Initial_callstack_depth = 2;
+402 int Callstack_depth = Initial_callstack_depth;
+403 :(before "End Reset")
+404 Callstack_depth = Initial_callstack_depth;
+405 
+406 :(before "End Includes")
+407 #include <iomanip>
+408 #define HEXBYTE  std::hex << std::setw(2) << std::setfill('0')
+409 #define HEXWORD  std::hex << std::setw(8) << std::setfill('0')
+410 // ugly that iostream doesn't print uint8_t as an integer
+411 #define NUM(X) static_cast<int>(X)
+412 #include <stdint.h>
+
+ + + -- cgit 1.4.1-2-gfad0