My intention for this blog is not only to display some of the work that InWorldz has done to our grid, but also to share some of what we’ve learned and hopefully get aspiring geeks, junior geeks, and certified geeks excited about virtual worlds and all the possibilities they bring. These articles will be long but I hope they can be of some value to you.
Along with the technical challenges we have to meet comes a lot of hard work, but also a lot of fun, and a lot of learning. This article is the beginning of a multi part series on the construction of the Phlox script engine. I’m hoping that by presenting this material it can spark an interest in software technology and how it can be applied to something fun like a virtual world, to something serious like a domain specific language for bank transactions.
Normally with a series on script engines I would start from the bottom at the parser and lexer. However, I think that starting at the end in this case will give some perspective on what the lower components are trying to accomplish. Therefore I’d like to introduce you to the component called the virtual machine. Let’s break down those two words:
Virtual: Existing in essence or effect though not in actual fact
Machine: A device having parts that perform or assist in performing any type of work
So by definition a virtual machine in the context of computing is a machine that performs the work of a physical computer but doesn’t actually exist. Much like a virtual world, a virtual machine has a lot in common with the real thing. It is expected that if you feed a virtual machine instructions it will perform operations in a similar manner to a real, silicon based, honest to goodness computer.
You may not know it, but you probably use a virtual machine somewhere in your everyday life. If you utilize InWorldz as your virtual world host, you have actually been using two different virtual machines to work and play, even before phlox was ever released.
At the first level, our software and OpenSim proper runs on top of one of the flavors of the CLR or Common Language Runtime. Originally developed by Microsoft and then also implemented as an open source product called Mono, this platform powers a great deal of software available today. The virtual machine behind both of these runtimes understands a language called CIL or Common Intermediate Language (more information here). The CIL bytecodes are the instructions that tell the machine how to run the OpenSim software.
Running below the InWorldz server software is actually another virtual machine that pretends to be real hardware to the operating system. This allows InWorldz to easily change server configurations, add and remove RAM and even processor cores. These virtual machines are out of the scope of this article but are related in many ways to the types of VMs we’ll talk about.
Outside the realm of InWorldz, virtual machines are also used in portable devices. If you happen to have an android powered phone in your pocket, you are also using a virtual machine called Dalvik (really geeky stuff here) which efficiently runs all the apps you’ve decided to download this week.
Dalvik, Phlox, and the CLR all mirror their physical counterparts not only in function, but also in design. In your desktop computer at the lowest levels your CPU has support for storing data in registers and on something called the stack. Likewise, there are two types of virtual machine designs. The first is a stack machine, and the second is a register machine. Each of the two designs comes with trade offs in runtime performance, and implementation complexity. Registers.. Stacks.. what are these things and what do we need them for?
In a virtual machine, (as well as a real machine) registers and the stack are used to store temporary results that are needed while we complete a problem. Though both stack and register machines can do the same types of work, we’re going to concentrate on stack based machine examples, since Phlox is a stack machine.
Each problem given to a machine is reduced to it’s simplest form and then the machine solves and combines the results of many small problems into a solution for the whole thing. A very simple example follows:
You need to design a machine and can add an unlimited amount of numbers together. Work with the sample 1 + 2 + 3 + 4 to come up with a solution.
The first thing we’ll notice is that there is no limit to the number of terms we might need to deal with. We cant just design a machine that can only add exactly four numbers. We need to deal with any amount. If we were to design this adding machine, we would have to add two of the numbers together at a time, and then put the result somewhere. Then we would need to add that result with the next term and store that result somewhere and so on until the addition problem was completely solved and we had a final answer.
[1 + 2] + 3 + 4
1 + 2 = (3)
[(3) + 3] + 4
3 + 3 = (6)
[(6) + 4]
6 + 4 = (10)
Using this method and a stack to complete the example problem above would look something like this:
Push the number 1 onto the stack (stack: )
Push the number 2 onto the stack (stack: [1, 2])
Pop the first two numbers off of the stack and add them [1 + 2]. Push the result of the addition (3) onto the stack (stack: )
Push the next number 3 onto the stack (stack: [3, 3])
Pop the first two numbers off of the stack and add them [(3) + 3]. Push the result of the addition (6) onto the stack (stack: )
Push the next number 4 onto the stack (stack: [6, 4])
Pop the first two numbers off of the stack and add them [(6) + 4]. Push the result of the addition (10) onto the stack (stack: )
The result of the entire operation remains at the top of the stack. (10)
As we can see, a simple adding stack machine would need instructions for pushing variables and constants onto the stack, and adding stack members together. Each instruction we added to the machine would be given a unique number. This number would allow the machine to read through the stream of instructions and perform the simple operations. When defining these numbers, which we call bytecodes we may also give them a name that makes sense to us as people. Instead of referring to the add instruction as instruction #1, we might simply call it “ADD”. Likewise for pushing an operand onto the stack, we wouldn’t want to say “use instruction #2” we would simply want to say “use PUSH”. This leads us to a representation of our source code where instructions can be listed out in the lowest level human readable form before actually being assembled into the raw numbers the virtual machine will use.
The bytecode for our simple adding machine example above could be:
The Phlox virtual machine has an instruction set very similar to this, but with a lot more operations to be able to deal with all the features of LSL and general purpose programming languages. When you input LSL source code into the text editor on InWorldz and press save, a lot of really neat things happen. First the lexer and parser makes sure that the source code is formed correctly and is grammatically correct. Then Phlox performs semantic checks to make sure you’ve not mixed up types, that you haven’t passed the wrong number of arguments to a function, and other similar mistakes. Once these tests pass, the compiler will compile your script into Phlox bytecode some of which we can see below:
Everything above the ^Z in the image is the LSL source code. Below it is the byte compiler output for the simple program that adds 4, 5 and 6 together. The form of the phlox bytecode is very similar to our simple adding machine in this case, but we can also see that Phlox has additional responsibilities over and above the adding machine.
- .globals Tells the Phlox VM how much space we need for global variables. In this case there is one global variable, i, hence the line .globals 1
- .statedef Defines all the states that are in this LSL script. If there were more states, there would be more .statedef lines
- iconst Pushes an integer constant onto the top of the stack
- iadd Adds the top two integers on the stack together
- gstore Removes the top operand on the stack and stores it in globals memory (in this case, the variable i)
- halt Tells the machine that this script is suspended until it receives another event
- .evt Tells the Phlox VM about an event present in this script. In this case we only have one, which is state_entry and it is part of the default state. It takes no arguments (args=0) and there are no local variables defined inside of the event handler (locals=0)
- ret Returns to the caller. When called from an event, the script is suspended until another event is triggered.
Every time you press save on a script, this intermediate form is generated before finally compiling down to the machine level bytecode.
InWorldz chose to design a virtual machine for many reasons, but the biggest one comes down to control. The first problem when you compile a script to native code as was being done before Phlox, you lose all scheduling control to the operating system. You can not choose how many instructions will be executed for each script and scripts can run forever in a loop consuming an entire operating system thread. This is bad because each of those threads also comes with a memory penalty that is equivalent to it’s stack size (usually around 1 MB) and too many threads trying to run at the same time will cause the processor to make tons of context switches and eat up valuable CPU time that you would really rather be using for the rest of the simulation than your avatar’s animation override.
If compiling to C# (as was done on InWorldz pre-phlox) your best bet for ensuring a script does not run too long is to generate a yield return trampoline that emulates coroutines (http://www.replicator.org/node/80). Essentially you’re adding in the C# yield return keyword at specified points in the program, say after every few lines of code. This solution would mostly work for allowing you to better control the scheduling of your scripts and would prevent a script from eating up an operating system thread, but it makes the design of the script engine very cumbersome. Every function now needs to return an enumerator type instead of its normal return type, all the compiled code needs to be able to deal with these and other changes, and you still haven’t solved all the requirements of an LSL environment.
A big part of LSL is that your scripts need to be able to have their state retrieved and saved no matter what code they’re currently running. Even if your AO is in a tight loop selecting various animations and recursively calling functions, this must not interfere with the ability to retrieve the script’s state for a save. At any time we need to be able to pause a script, grab the values of all the global as well as local variables in the script, and preserve the current call stack no matter how deep into a recursive call you are. When you compile down to C# and run the code through the CLR, your access to this information has been revoked. Your script could be JIT compiled and be running native code. Even if you could retrieve and fully save it, the native callstack from one machine’s scripts will not translate to another machine. You’ve lost control of very important information and an incomplete state save here will break the script. The only options here are to wait for the script to exit any events before taking a state save which could take an arbitrary amount of time, or insert some voodoo magic into the runtime you’re using, and hope that it’s Mono where you have the source and can add these changes. This also puts you in a position to have to continuously update your voodoo whenever Mono makes changes leading to extra burden on development.
The design of Phlox separates the runtime state and the compiled script code into separate independent pieces. Using a custom built virtual machine, we always have everything we need to do a complete state save available to us. Even if your script is in an infinite loop calling functions we can suspend it at any time and know that the current state of the script will be entirely preserved. That makes region crossings with active scripts smooth and straightforward. This design also enables bytecode sharing, whereby loading the same script 40 times in 40 separate objects only results in one copy of the script in memory.
The virtual machine also allows us to easily track the amount of memory being used by a script, and kill it if it goes over it’s quota (currently 32kb). Memory usage for each script is minimized by small bytecode since we don’t add features we don’t need. State saves are compact and quick.
Phlox and virtual machines have allowed us the freedom we needed to create an LSL environment that is fully compliant with your expectations. We can easily add features in the future and quickly fix bugs due to the architecture and can expand the runtime environment to make sure our residents can make their dreams come to life. All of this thanks to a machine that thinks it is, but isn’t actually a machine.