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