I’m currently working on a Unity3d project, and often find myself in need of 3rd party DLLs. Unity supports .Net 3.5 libraries through an old version of Mono. Most libraries these days are distributed via Nuget packages and usually only with the latest version of the .Net framework. I’ve found myself having to find or create back-ports of those libraries. Unity isn’t the only framework I’ve had this problem with and portable class libraries are on attempt to solve this (but sadly they’re not supported on Unity). 

Most of the time, this is actually really simple. Add a reference to System.Threading, the TPL back port and there are no other changes required.

Recently, I’ve been focused on performance and I’ve needed to back port Distruptor-net and Microsoft.Io.RecyclableMemoryStream. These libraries are small; I only need to use maybe one public class from each, yet I have to include a DLL each time. For just these two public classes I’ve needed to add three DLLs. I could ILMerge them with my assemblies; but that can cause other problems.

I’d rather get a source. I’ll probably not need to upgrade these libraries, given their simplicity I’d like to be able to just get a single source file and drop that into my project. This is a work flow that works anywhere; even in doesn’t support Nuget. I wouldn’t have had to create back ports, the source just compiles (you could even use the preprocessor macros to hide some of the compile time differences).

There are actual performance reasons for not having lots of libraries; most people don’t care but the JIT can’t work across assembly boundaries (although to be honest this level of performance doesn’t bother me too much, but why deliberately slow your program down?).

The Javascript world there are plenty of libraries that are designed to be single file. NPM supports links directly to git repositories.

Nuget actually supports distribution of sources; when you install a package it will automatically add them to your csproj. I’d even commit these files into version control. This will save you from having to do a package restore too.

People often want to share snippets of code. Sometimes they do this by creating a misc/util library; usually I don’t want all the baggage. I’ve written about that before here.

Next time you want to create a new library, ask yourself, what is better; one cs file or another DLL to manage and version?

This is the third part of my brain dump about my work on Second Life. One of the main projects that I worked on during my time at Linden Lab was implementing User Scripts on Mono

LSL2 VM is Second Life’s original VM for executing user code. Internally, Scripts were actor-like; they had a queue for messages and could communicate with other Scripts via messages. However, they can generate side effects on the world via library calls.

Each Sim was associated with a particular region and the objects that contained the Scripts could roam from one region to another. The VM provided transparent migration of Scripts as they moved between Sims.

Migration is described as transparent if the program can be written in the same way as non-mobile code. When the code is migrated it should resume in exactly the same state as before. LSL Scripts did not require any knowledge of where they were being executed.

To achieve this the full state of the Script is stored. This includes: the program code, heap objects, the message queue, the stack and program counter. As I said in my previous post, the LSL2 VM achieved this by putting all this state into a 16K block of memory. By storing everything is this block, this made migration simple because there was no serialisation step. When the Script is suspended, these blocks can just be shipped around and interpreted by any Sim.

Under Mono we wanted to provide the same quality of transparent migration. CLR (.Net) code is portable; write once, run anywhere, objects can be serialised, but the stack or program counter can not be accessed from user code.

The CLR stack is pretty conventional; it is composed of frames. A new frame is created each time a method is called and destroyed when a method exits. Each frame holds local variables and a stack for operands, arguments and return values.

To be able to migrate a Script, we need to suspend it and capture its state. Scripts are written by users and are not trusted. They can not be relied on to cooperatively yield. You can suspend CLR threads, but you have know way of knowing exactly what its doing and it can cause deadlocks.

The Script’s code is stored in an immutable asset. This is loaded by the Sim by fetching the asset via HTTP on demand. Multiple copies of the same Script will reused the same program code.

Classes can not be unloaded in the CLR, however, AppDomains can be destroyed. A Script was defined as live if it is inside an object rooted in the region or on an Avatar. When a new Script is instantiated, it is placed in the nursery AppDomain. If more than half the Scripts in a the nursery AppDomain are dead, the live Scripts are moved to the long lived domain. The long lived AppDomain has a similar scheme but it is replaced with a new domain. Migration was used to move Scripts between AppDomains.

The Scripts heap state is either referred to by a frame or the Script object itself contains a reference. The queue of messages is just an object on the Script base class. These objects are serialised and then restored at the destination.

The stack serialisation was achieved by modifying the program’s byte code that inserted blocks do the capture and restore of the current threads state. Doing it at the code level meant that we did not have to modify Mono and the code could also be ported to a standard Windows .Net VM.

The assembly rewriter was implemented using RAIL, which is similar to Mono Cecil (which was released part way through the project).

Each method on the Script object is modified. At the start of each method, a block of code is injected to do the restore. It get the saved frame and restores the local variables and the state of the stack. It then jumps to the part of the method that was previously executed. At the end of the method it inserts code to do the save which populates a stack frame. At various points within the method, it injects yield points where the program can be potentially suspended.

Here is a pseudo-code example of the the kind of thing the assembly re-writing did.
Original:

void method(int a)
{
    var result = 2;
    while (result < a)
    {
       result <<= 1;
    } 
}

Re-written:

void method()
{
   if (IsRestoring)
   {
      var frame = PopFrame();
      switch(frame.pc)
      {
      case 0:
        // instructions to restore locals and stack frame
        goto PC0;
      case 1:
        // instructions to restore locals and stack frame
        goto PC1;
        // ...
      }
    }
    // snip

  var result = 2;
  while (result < a)
  {
    result <<= 1;
    // Backwards jump is one of the places to insert a yield
    if(IsYieldDue)
    {
       frame.pc = 1;
       frame.locals = ...
       frame.stack = ...
       goto Yield;
    }
  PC1:
  }
Yield:
  if (IsSaving)
  {
    PushFrame(frame);
  }
   // return normally
}

Despite all the overhead injected into the methods, Mono still performed several orders of magnitude faster than the original VM.

We would have liked to allow other languages, like C#, however, supporting all of the instructions in the CIL was a challenge; there are hundreds. We controlled the LSL compiler and knew it only used a subset of the CIL instruction set.

The techniques I’ve described for code re-writing were influenced by some Java implementations of mobile agents. See Brakes and JavaGoX (I’m unable to find the original material, but I think this is the original paper)

For those who are really keen, you can also find the actual test suite I wrote for the LSL language here: LSL Language Tests (I was Scouse Linden, for those who look at the page history). We had to break it up into two parts because of the arbitrary 16K limit on program size of LSL; the basic tests were too big! If you look at the tests, you can see some of the quirks of the LSL language, from the assignment of variables in while loops, to rendering of negative zero floating point numbers.

Also here is the source to the LSL compiler but sadly it looks like they spelled my name wrong when they migrated to Git.

I’m not intending to write any more on the topic of Scripting in Second Life unless there is any specific interest in other areas. I hope you’ve found it interesting or useful.

I’ve had some positive feedback from the last post I wrote, so I thought I’d write up some information about how User Scripting functioned in Second Life from the time when I worked on it. This post covers the background of scripting, the LSL language and a bit about how the legacy LSL2 VM works.

One of the unique features of Second Life is the way users can create content. Using the Editor in the Viewer (the name for the client), they can place and combine basic shapes (known as Prims) to make more complex objects. Prims can be nested inside another prim or joined together with static or physical joints. They can also be attached to the user’s Avatar (guess what the most popular “attachment” was?).

To give an object behaviour, Prims can have any number of scripts placed inside them. A script is effectively an independent program that can execute concurrently with all the other scripts. There is a large library of hundreds of functions they can call to interact with the world, other objects and avatars. A script can do a wide variety of things, for example; it can react to being clicked, give users items or even send an email.

Users can write scripts in LSL; a custom language, which has first class concepts for states and event handlers. A script can consist of variables, function definitions, and one or more named states. A state is a collection of event handlers, only one state can be active at any one time.

The Second Life viewer contained a compiler which converted scripts into program bytecode for its bespoke instruction set and layout.

default
{
  state_entry()
  {
    llSay(0, "Hello, Avatar!");
  }

  touch_start(integer total_number)
  {
    llSay(0, "Touched.");
  }
}

Above shows the default script, created when you add a new script to an object. When created or reset it will print, “Hello, Avatar!” to the chat in the region. When clicked it will print “Touched.”.

LSL has a limited number of data types. It is limited to integer, float, string, list (a heterogeneous list), vector (a 3d floating point vector) and key (a UUID).

The approach of treating each script as an independent program lead to many regions containing thousands of individual scripts within them. To give the effect of concurrency (in the single threaded Simulator), each script would get a timeslice of the main loop to execute a number of instructions before control was passed to the next.

The individual scripts within the original LSL VM, are quite limited. They are only allocated 16KB for program code, stack and heap. This fixed program size made managing memory limits simple; the heap and stack would grow towards each other in address space, and when they collided, the script threw an out of memory exception.

With LSL2, when a Prim moves between regions, migrating the executing script to the destination server is required. Migration of scripts between servers is relatively simple, all the program state was stored in a contiguous block of memory. The running form is identical to the serialized form. This can simply be sent directly over the wire and execution would continue the next time it was scheduled. No explicit serialization required. Unfortunately, this simple design VM lead to poor performance. The code was interpreted; there was no JIT compiler, it did not generate any native instructions.

In an attempt to rate limit particular actions that scripts could do, some library calls would cause the script to sleep for a given time. For example, calling llSay (the method to print some chat text) would cause the script to yield control for 0.1 seconds. Users worked around this limitation pretty easily; users would create a Prim containing multiple scripts. They could farm out the rate-limited work to multiple scripts using message passing. There was no limit to the number of scripts a user could have so this meant they’d effectively have unlimited calls to the restricted function.

For later features, we replace these sleeps were with per Sim rate limits. The rate limit was fixed for scripts that were attached to an avatar and proportional to the quantity of land owned within a region. For example, own 10% of the land, get 10% of the budget. This same style of limit was applied to the number of Prims within a region. This means that the rate limit was now, at least somewhat, tied to actual resource usage.

The users applied similar techniques to give more storage to their objects. Again by placing multiple scripts in a single object, users could distribute the values to be stored to multiple scripts. To retrieve it, they could broadcast a message to all their scripts and the relevant one would respond.

On the Sim, scheduling of scripts is effectively round-robin, however, there are some differences in the way events are scheduled. These differences were discovered and exploited by the users; for example, the users would craft scripts that could get more CPU, they would creating a loop using the colour system. A user could add a handler to the colour changed event and then within the handler change the colour. This short circuited the scheduling and allowed the script to jump the queue.

Like any thing in SL, users created scripts within the Viewer. There is an editor window with basic autocomplete which users can write or paste in any code. The code is then compiled on the client and uploaded like any other asset. This service was a simple, Apache hosted, CGI perl script. The upload process did no validation of the bytecode and users would occasionally try to exploit this by uploading garbage (or deliberately malicious) bytecode.

Users want to be able to use a mainstream programming language; the professionals wanted to be able to hire normal programmers with language experience and the amateurs wanted a transferable skill. The language and runtime often got in the way of adding new functionality, the lack of any data types made some methods very inefficient.

Second Life is fundamentally about user created content and User Scripting was one of the main tools used for this. It suffered many serious flaws and limitations including the problems I’ve described above. We wanted better performance, fewer limitations and new programming languages. To that end we replaced the legacy VM with Mono and the compiler backend with one that could generate CIL instructions. However, this wasn’t a simple swap; it we had to solve many complex problems. The implementation of this is going to be the topic of my next post.