Tiny VM in C

Discussion in 'C Programming' started by tekk.nolagi, Feb 11, 2014.

  1. tekk.nolagi

    Eric Sosman Guest

    See the slippery slope?

    Questions like "How can I do X in C?" are topical here (most
    likely; the line is ill-defined and different cartographers draw
    it in different locations). But the questions you're now asking
    are "Help me understand X," and the responses you'll get (those
    you have in fact been getting) have little to do with C -- which
    suggests that the questions aren't about C or how to apply C at
    all. Here's a useful test: Could you ask the same questions and
    get similar answers in a Fortran or Ada or Java forum? I think
    you could -- and that's why I think you're off-topic here.

    Once you've settled on a design you might well find yourself
    confronting C questions again -- but at the moment, you're not.
     
    Eric Sosman, Feb 12, 2014
    #21
    1. Advertisements

  2. [...]

    There's an adage about making telescope mirrors to the effect that
    it takes as long to make a 12-inch mirror as it takes to make a
    6-inch mirror *and then* a 12-inch mirror. The idea is that you
    learn enough from making the 6-inch mirror to make the task of
    making a 12-inch mirror that much easier.

    Simulating an x86 is the 12-inch mirror in this analogy.
     
    Keith Thompson, Feb 12, 2014
    #22
    1. Advertisements

  3. Has anyone proposed emulating the x86? If so, I have missed it.

    My comments were that the x86 has a robust developer environment, and with
    Visual Studio, a disassembly window, a register window which tracks changes
    through each assembly instruction by highlighting changed items in red. It
    is very clear to see the operation of assembly language in that environment,
    on that CPU, and this can be a very effective teaching aid.

    In addition, the books on Intel's CPU architecture go into great detail
    about what each assembly instruction does, what flags are affected, and
    a full map of the operation that takes place on the more complex operations.

    I would not propose emulating the x86. But, there is lot to learn from
    the x86.

    Best regards,
    Rick C. Hodgin
     
    Rick C. Hodgin, Feb 12, 2014
    #23
  4. (snip)
    But what is x86? Intel calls the 32 bit version IA32, but otherwise
    x86 means anything from the 8086 up to whatever they make now, and
    probably for many years to come.

    The 8086 might not be all that hard to do, but it gets a lot
    harder with the later versions.

    -- glen
     
    glen herrmannsfeldt, Feb 13, 2014
    #24
  5. x86 is the general architecture, eight registers (A*, B*, C*, D*, SI, DI, SP,
    BP), one code segment / instruction pointer combination (CS:IP) and three to
    five data segments (DS, ES, SS, FS, GS), and flags, and if you choose to go
    there, a relatively complex stack-based floating point unit with eight STx
    80-bit "registers" which support 32-bit, 64-bit, 80-bit floating point, as
    well as 16-bit, 32-bit, 64-bit, and 80-bit binary coded decimal integer
    values.

    It is actually a very easy processor to understand in those concepts. It
    becomes complex in the details of the specifics can become overwhelming
    when you get into virtual x86 modes, or any of the protected modes from
    80286 and up.

    Best regards,
    Rick C. Hodgin
     
    Rick C. Hodgin, Feb 13, 2014
    #25
  6. There is an old quotation: "If I had 6 hours to chop down a tree, I'd spend
    4 hours sharpening my axe." Sort of the same deal...
     
    Charles Richmond, Feb 13, 2014
    #26
  7. OTOH, if you started with the 8086 and then progressed through the
    various generations, you'd learn enough in the process that you'd
    probably still finish no later than if you started with the latest
    generation.

    S
     
    Stephen Sprunk, Feb 13, 2014
    #27
  8. I think I will go with my own twist on MSP430. It seems simple enough. I will add more features as I go.

    WRT branching: I have just pushed the first pass at branching. If someone wants to check out the code (still very small) please do take a look :)

    http://github.com/tekknolagi/myvm
     
    Maxwell Bernstein, Feb 13, 2014
    #28
  9. Alright, so I'm having a bit of trouble with some C. I am trying to initialize all of the elements in an array of function pointers.

    I have:

    void (*instructions[NUM_INSTRS]) (machine_state*);

    then I have:

    void instr_##x (machine_state* m);
    instructions[INSTR_##x] = instr_##x;

    (where ##x is something like HALT)

    Clang gets angry and throws:

    ../instructions.h:5:37: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
    void instr_HALT (machine_state* m); instructions[INSTR_HALT] = instr_HALT;
    ^~~~~~~~~~~~
    ../instructions.h:5:37: error: redefinition of 'instructions' with a different type: 'int [0]' vs 'void (*[20])(machine_state *)'
    ../globals.h:84:8: note: previous definition is here
    void (*instructions[NUM_INSTRS]) (machine_state*);

    What am I doing wrong?
     
    Maxwell Bernstein, Feb 13, 2014
    #29
  10. tekk.nolagi

    Kaz Kylheku Guest

    This is an array of pointers to functions that return nothing,
    and take a machine_state * pointer.
    You cannot have statements at file scope in C, only inside functions!

    There is no need here, because static initializers can refer to functions:

    void (*instructions[NUM_INSTRS]) (machine_state*) = {
    instr_whatever,
    instr_whateverelse,
    /* ... */
    };

    Starting with the C99 dialect of C, you can use designated initializers
    to specify which array element is being initialized. Like this:

    void (*instructions[NUM_INSTRS]) (machine_state*) = {
    [INSTR_foo] = instr_foo,
    // ...
    };

    these don't have to be in order. Any elements of the array that don't
    have initializers are initialized to zero or null.
    Not reading up on the language, and doing tutorials, etc.
     
    Kaz Kylheku, Feb 13, 2014
    #30
  11. tekk.nolagi

    David Brown Guest

    Please stop advising the guy to look at x86 assembly. He is not
    remotely interested in it, and it will only cause confusion. A simple
    existing assembly - such as for the msp430 - can help him understand the
    instructions needed for his virtual machine. x86 is as far from a
    sensible or useful instruction set for learning purposes as it is
    possible to get.
     
    David Brown, Feb 13, 2014
    #31
  12. tekk.nolagi

    David Brown Guest

    Please fix your quoting and attributions - your best bet is to get a
    real newsreader (Thunderbird is fine, and free) and a real newsserver
    (news.eternal-semptember.org is free), rather than the obnoxious
    mangling done by google groups.


    Instructions like "JZ" and "JNZ" are conditional branches. To be
    useful, your virtual machine needs some way to make conditional branches
    to implement loops and conditionals. Some instruction sets (virtual or
    otherwise) allow lots of types of conditional execution, but the
    simplest is conditional branches. How many and which types you
    implement is up to you - more conditions (such as "zero" and "not zero")
    lets people write more compact (and usually faster) VM code.
     
    David Brown, Feb 13, 2014
    #32
  13. tekk.nolagi

    David Brown Guest

    The msp430 /is/ pretty simple. There are processors with fewer
    instructions, but that does not make them simpler to understand or use.
    An important issue in choosing the VM's instruction set and model is
    that it needs to be easy for the OP to write code for his VM. msp430
    assembly is one of the easiest I have worked with (and I have used well
    over a dozen).

    gcc (along with binutils) is perfectly capable of producing assembly
    files rather than binary files, and files that mix the C code, the
    assembly code, and the hex code. There is no need to try and parse elf
    formats.

    And there are no hefty runtime libraries for the msp430 - the libraries
    used with gcc for it are quite compact. Of course, if you use software
    floating point, printf, etc., then that takes quite a bit of code. But
    if you avoid these, the overhead of C compiler compared to hand-written
    assembly is usually tiny. And once the OP has got his VM debugged, then
    he /can/ use larger libraries and programs if he wants.

    Have you ever used any of these, or read the data sheets? I have used
    the 6502 (I wrote a disassembler for it) and the Z80 (I had to
    hand-assembly my code for the Z80). Both of these are nice
    architectures (nicer than the 8080 or the 6800), but they are both
    complicated. The 6502 is so limited that writing VM code for it is a
    lot harder than necessary. The Z80 is more powerful, but things like
    prefix codes would make the VM more complicated.

    And of course for a core that has been out of date for some time, you
    have a lot more trouble getting datasheets or information, and certainly
    a big challenge getting assemblers, compilers, or sample code. (The Z80
    still exists as the "Rabbit" microcontroller, with a sort-of C compiler.)

    I am recommending the msp430 based on real experience here.
     
    David Brown, Feb 13, 2014
    #33
  14. tekk.nolagi

    David Brown Guest

    (You seem to have got your replies and quoting mixed up here.)

    You proposed using the debugger in VS to view and track x86 disassembly
    on a Windows system. That is crazy for someone unfamiliar with assembly
    and the details of x86 ISA - the instruction set is complicated, and you
    would be overwhelmed with the mess required to deal with Windows and
    C++. So many of the instructions involve jumps, calls, branches, and
    accesses that have several layers of indirection that even experienced
    people are easily confused. If there is not even any intention for the
    OP to implement x86 for his VM, then it is completely pointless.

    Yes, there are lots of books on programming x86. But why would anyone
    want to spend the time and money reading a dozen x86 books when you can
    learn all about the msp430 assembly and ISA in about 20 pages of datasheet?

    There are only two things that can be learned by studying x86 assembly.
    One is how to write x86 code for compilers, libraries, and occasional
    very critical code. The other is to learn how not to design a cpu core.
    The 8086 was considered a poor, old-fashioned, limited and awkward
    design when it came out - it has not improved with age. (Modern
    implementations are, of course, fantastic pieces of engineering - but
    that does not make the ISA any good.)
     
    David Brown, Feb 13, 2014
    #34
  15. Here's an example of the kind of debugger environment you get with Visual
    Studio, and edit-and-continue. I post this so people will have some frame
    of reference for why I suggest this environment. You can make code changes,
    examine things easily (because it's a native debugger with native abilities
    to the GUI, and it doesn't go through text translation as with gdb and some
    GUI, which makes it much faster, and so on).

    I demonstrate Visual Studio 2008 (39 MB, 9 minutes 40 seconds):
    http://www.visual-freepro.org/videos/2014_02_13__demonstrate_x86_debugger.ogv

    If you cannot view this video, use the VLC media player:
    https://www.videolan.org/vlc/

    Enjoy! :)

    Best regards,
    Rick C. Hodgin
     
    Rick C. Hodgin, Feb 13, 2014
    #35
  16. tekk.nolagi

    James Kuyper Guest

    My guess is that line 37 occurs at file scope (outside of any function
    definition). You're only allowed to have declarations at file scope, not
    statements. Therefore, it interpreted that line as a new declaration.
    You appear to be using C90, so it implicitly gave the second declaration
    a type of int. One alternative is to move those assignment statements to
    block scope (inside a function definition). However, if you need to do
    it at file scope, one alternative is:

    void (*instructions[NUM_INSTRS]) (machine_state*) = {
    instr_HALT, instr_ADD, ...
    };

    That loses the connection between INSTR_HALT and instr_HALT which is
    enforced by your code. You have to count manually to make sure that each
    entry in the array is in the right location.
    If you're willing to use a slightly more up-to-date version of C, such
    as C99, it has a new feature called "designated initializers" that would
    allow you to retain that connection, even at file scope:


    void (*instructions[NUM_INSTRS]) (machine_state*) = {
    [INSTR_HALT] = instr_HALT,
    [INSTR_ADD] = instr_ADD, ...
    };

    When used at block scope (inside a function definition), a declaration
    like that is equivalent to:

    void (*instructions[NUM_INSTRS]) (machine_state*);
    instructions[INSTR_HALT] = instr_HALT;
    instructions[INSTR_ADD] = instr_ADD;

    When it appears at file scope, it allows you do the same thing, even
    though, at file scope, the assignment statements that it's equivalent to
    would not be allowed.
     
    James Kuyper, Feb 13, 2014
    #36
  17. tekk.nolagi

    BGB Guest

    it can also be made easier in another way:
    if a person implements a variant which *only* does 32-bit protected mode
    with flat addressing, and ignores most OS level functionality (this can
    be viable for an interpreter which does not need to run a full OS, say
    because all the OS system calls are handled in native code).

    oddly, in this case, a large part of the opcode map is left empty as well.


    though, x86 does have a big drawback for interpreters:
    there is no real good way to really gloss over word-size / endianess /
    memory layout / ... issues, and apart from "hey, I can run C code
    compiled with GCC or similar in this interpreter", there isn't a whole
    lot of gain.

    the constraints of x86 in this sense make it not particularly viable for
    interpreters which operate in the same address space as the host program
    (and directly share data-structures, ...).

    instead, effectively, the interpreted program largely has to run off in
    its own self-contained address space which does everything as the
    compiled x86 code expects (may still be viable for some use-cases).


    and, for a plain interpreter, it is still a fair bit more hairy and
    complex than a typical bytecode format.

    if the goal is to have an interpreter, say, to run a scripting language
    or similar, a person is probably better off with a more specialized
    bytecode design.


    IME, for bytecode, stack machine designs are fairly popular and pure
    interpreters for them are generally simpler to implement (and generate
    code for).

    if performance is more the goal (for a plain C interpreter), or the
    design is more focused on JIT compilation (*), a "register machine"
    design can offer some advantages, though granted in many regards is a
    little more complicated (some added complexity in terms of the ISA
    design and compiler logic).


    *: a register machine can allow better performance for a simple/naive JIT.

    it doesn't matter as much for a more advanced JIT, but then basically
    one is climbing great walls of complexity for slight gains in performance.

    the "easy case" here is basically to use a statically-typed register
    machine as the IR, at which point one can produce output from a naive
    JIT roughly on parity with unoptimized C.

    IME, a naive JIT for a stack-machine will be about 2x-3x slower than
    unoptimized C.


    now as for dynamic types... well, this is its own big-complex issues.
    simple answer: actually using dynamic types at run-time: very expensive.
    so, there tends to be some amount of taking dynamically-typed input
    languages and compiling them into a statically-typed form at the IR level.

    though, for simple if albeit slow languages and interpreters, dynamic
    types can work well.
     
    BGB, Feb 13, 2014
    #37
  18. Absolutely. I almost suggested this idea, but I really wasn't too keen
    on the idea of emulating x86. I've been surprised Intel or AMD hasn't
    released a version of their x86 architecture at some point which is only a
    flat 32-bit protected mode chip (boots up in protected mode, cannot do
    virtual x86, real-mode, smm, no hypervisor support, or anything else),
    or something which operates more similarly to the original 80x86 with
    segment selectors, allowing for a segmented model which easily addresses
    far more memory than 32-bits.

    So many well-developed tools that would require a small amount of changes
    to work with such a chip. It would also allow a new streamlined ISA was
    introduced which was more Itanium-like in that it had explicit predicates,
    explicit temporal references, explicitly speculative execution, and more.

    Best regards,
    Rick C. Hodgin
     
    Rick C. Hodgin, Feb 13, 2014
    #38
  19. tekk.nolagi

    BartC Guest

    They tried something like that 30 years ago, with improved versions of
    8088/86, called 80188/186: some interesting new instructions, but the main
    thing was more integrated peripherals (DMA, timers, etc). However, these
    worked in an incompatible manner to an 8088 plus discrete components (as
    used for IBM PC and clones) and didn't catch on.

    Backwards compatibility seems to be important.
     
    BartC, Feb 13, 2014
    #39
  20. Here's my own debugger, called Debi (short for "Debug Intel"), which I wrote
    for my 32-bit OS back in the late 90s, early 2000s. It is a graphical
    debugger that runs on the Hercules Graphics Adapter using its 720 x 348
    video mode and unusual memory model. All graphics are drawn from my own
    algorithms within the OS, including the flashing cursor and mouse pointer.
    For this version (which is running in the Bochs emulator, running in Windows
    2000, running in Oracle VirtualBox on Linux Mint 14 LOL!), the mouse pointer
    is not displaying because I had it disabled when I integrated the mouse
    pointer intercept from the MoMo window (watch the video, you'll understand).
    For the actual version which runs on proper the HGA and native hardware, it
    has its own mouse pointer, and the timers work correctly.

    I thought you might like to see this progression. Of particular interest is
    the CFSCA (Comments, Flowchart, Source Code, Assembly), which was the idea
    of edit-and-continue from within the debugger. Each of those layers could
    be linked to the others, allowing editing at any stage, as well as stepping
    through code at any stage.

    I demonstrate the Debi debugger for Exodus (72.6 MB, 12 minutes 40 seconds):
    http://www.visual-freepro.org/videos/2014_02_13__exodus_debi_debugger.ogv

    If you cannot view this video, use the VLC media player:
    https://www.videolan.org/vlc/

    Best regards,
    Rick C. Hodgin
     
    Rick C. Hodgin, Feb 13, 2014
    #40
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.