Tiny VM in C

[Eric Sosman]

I am not asking *directly* about C; I am asking advice for an implementation IN C.

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.

 

[Keith Thompson]

Avoid looking at anything remotely "x86" - it is a hideous architecture.
You don't want anything nearly that complicated.

[...]

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.

 

[Rick C. Hodgin]

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

 

[glen herrmannsfeldt]

(snip)

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.

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

 

[Rick C. Hodgin]

But what is x86?

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

 

[Charles Richmond]

Avoid looking at anything remotely "x86" - it is a hideous architecture.
You don't want anything nearly that complicated.

[...]

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.

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...

 

[Stephen Sprunk]

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.

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

 

[Maxwell Bernstein]

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]

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?

 

[Kaz Kylheku]

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*);

This is an array of pointers to functions that return nothing,
and take a machine_state * pointer.

then I have:

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

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.

What am I doing wrong?

Not reading up on the language, and doing tutorials, etc.

 

[David Brown]

If you have an x86 box with Windows, and can download Visual Studio express,
you'll find it very helpful. You can email me offline if you'd like some
assistance on stepping through x86 assembly. But, seeing the practical
results in a real, graphical debugger, which shows the register and flag
states change as you step through assembly instructions ... for the task
you're on about it would be most beneficial in my estimation.

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]

So I am looking at the instruction set (on Wikipedia) and seeing JZ
and JNZ. What advice should I take about implementing those?

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]

These will work on condition flags usually, set by a previous
instruction (such as CMP).

If the condition is true, jump to the label (set the PC to value
specified as the operand). Otherwise carry on with the next instruction
(set PC to PC+1 for example).


It's not that simple! And even if gcc might generate code for it, the
challenge then is disentangling the object, binary or executable file
formats. There might also be a hefty runtime library to emulate and debug.

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.

For emulating a real processor as an exercise, probably an 8-bit cpu
from the late 70s would be simplest (eg. 8080 or Z80, 6800, 6502). There
is little peripheral stuff to worry about, and the data sheets might be
a dozen pages. (And any emulation would likely run considerably faster
than the real thing!)

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]

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

(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.)

 

[Rick C. Hodgin]

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

 

[James Kuyper]

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*);

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.

 

[BGB]

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.

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.

 

[Rick C. Hodgin]

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).

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

 

[BartC]

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.

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.

 

[Rick C. Hodgin]

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...

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

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