Object-Oriented WebAssembly

Today, I want to write a little bit about object orientation and WebAssembly. For starters, what is WebAssembly? WebAssembly is a new portable, size and load-time efficient format suitable for compilation to the web. It is an open standard by a W3C community group and is currently integrated into all major browsers such as Firefox, Chrome, Edge and WebKit. WebAssembly aims to keep download speed and parsing time of program code low and execute at native speed by taking advance of common hardware capabilities available on a wide range of platforms. WebAssembly is basically bytecode for the Web.

As you might have noticed, WebAssembly is a very low level language, very next to the hardware. It is meant to be a compile target for high level languages such as C++ or Java. You can if course write WebAssembly by yourself. For this purpose, WebAssembly comes in two flavours of code, a binary representation which is meant to be distributed, and a textual representation, which is meant for debugging in a human readable form.

WebAssembly has a very reduced set of data types available. Version 1.0 as it is currently implemented in all browsers supports four! data types, which are:

  • i32 and i64 classify 32 and 64 bit integers, respectively. Integers are not inherently signed or unsigned, their interpretation is determined by individual operations.

  • f32 and f64 classify 32 and 64 bit floating-point data, respectively. They correspond to the respective binary floating-point representations, also known as single and double precision, as defined by the IEEE 754-2008 standard (Section 3.3).

Beside the limited set of data types available, WebAssembly also does not have support high level language structures such as arrays, structs and classes.

Given all these limitations, how could a compiler translate a high level language into such a efficient, but low level format? Now I want to show you an example how I did this in my Bytecoder transpiler!

Say hello world by doing some calculus

Lets start with a very simple example. A class with a main method doing some very simple calculus. We have the following Java code:

public class HelloWorld {

    public static int compute() {
        int a = 10;
        int b = 20;
        return a + b;
    }

    public static void main(String[] args) {
        int result = compute();
    }
}

How, lets take a look at the compile result in its WebAssembly textual representation with added comments by myself:

   ;;
   ;; Here we are doing some computation by adding two integers and returning them.
   ;;
   (func $HelloWorld_INTcompute (param $UNUSED i32) (result i32) (1)
         (local $var0 i32)  (2)
         (local $var1 i32)
         (set_local $var0
             (i32.const 10)
         )
         (set_local $var1
             (i32.const 20)
         )
         (return
             (i32.add     (3)
                 (get_local $var0)
                 (get_local $var1)
             )

         )
   )

   ;;
   ;; This is the original main method, which basically just calls the static compute method
   ;;
   (func $HelloWorld_VOIDmainA1TString (param $UNUSED i32) (param $p1 i32) (4)
         (local $var0 i32)
         (set_local $var0
             (call $HelloWorld_INTcompute (i32.const 0))
         )
         (return)
   )
1This is an example how static methods are translated into WebAssembly functions. Function names are derived from the class name and the function name including the full method signature to avoid naming conflicts in case of method overloading. Every method and also constructors or class initializers are compiled into such functions.
2Here we see some local variables needed for computation. Every variable must be declared at the beginning. WebAssembly does not have scoping rules for variables. They are visible for the whole function body.
3This shows a simple add operation and returning its value.
4Another static method. I will come to the exact rules later in this post.

Diving deeper into the rabbit hole

That seems to be quite easy, We can clearly see the low-level nature of WebAssembly, but we can also see that it is possible to compile high level language code into this format. But there is some subtle magic used to make this possible. Lets take a look!

(func $HelloWorld_INTcompute (param $UNUSED i32) (result i32) (1)
(func $HelloWorld_VOIDmainA1TString (param $UNUSED i32) (param $p1 i32) (2)
1There is an $UNUSED function argument! Basically, every function needs a context, its owning object. As static methods do not have an owning context, this argument is unused, as the name suggests. Of course we could leave this out, but I will show you why this is needed to implement high level structures such as lambdas later.
2The original main method take an array reference as an input, but this is mapped to an int32 data type? Why? Because references are basically pointers to an allocated memory area. All references are mapped to an int32 pointer in WebAssembly output!

More objects to come

Now, what if we instantiate an object and call methods on it? Given the following Java class, what would be the WebAssembly output?

public class HelloWorld {

    public int compute() {
        int a = 10;
        int b = 20;
        return a + b;
    }

    public static void main(String[] args) {
        HelloWorld world = new HelloWorld();
        int result = world.compute();
    }
}

Here we go:

   ;;
   ;; This is the constructor of the Object class
   ;;
   (func $TObject_VOIDinit (param $thisRef i32) (1)
         (return)
   )

   ;;
   ;; This is the constructor of the HelloWorld class
   ;;
   (func $HelloWorld_VOIDinit (param $thisRef i32)
         (call $TObject_VOIDinit (get_local $thisRef)) (2)
         (return)
   )

   ;;
   ;; Now we have an instance method, ho ho ho :-)
   ;;
   (func $HelloWorld_INTcompute (param $thisRef i32) (result i32) (3)
         (local $var0 i32) ;; INT
         (local $var1 i32) ;; INT
         (set_local $var0
             (i32.const 10)
         )
         (set_local $var1
             (i32.const 20)
         )
         (return
             (i32.add
                 (get_local $var0)
                 (get_local $var1)
             )
         )
   )

   ;;
   ;; The main method
   ;;
   (func $HelloWorld_VOIDmainA1TString (param $UNUSED i32) (param $p1 i32)
         (local $var0 i32) ;; INT
         (local $var1 i32) ;; INT

         (set_local $var0 (4)
             (call $MemoryManager_AddressnewObjectINTINTINT
                (i32.const 0)
                (i32.const 8)
                (get_global $HelloWorld__runtimeClass)
                (i32.const 48))
         )
         (call $HelloWorld_VOIDinit (get_local $var0)) (5)

         (set_local $var1
             (call $HelloWorld_INTcompute (get_local $var0)) (6)
         )
         (return)
   )
1Here we see an example of a compiled constructor. It only takes one argument, the pointer to the allocated memory area.
2Here we see the implicit super() call, a Java specific language feature.
3This is same code as the static version of compute. There is only one difference. There is no more $UNUSED argument, now we have $thisRef, which is basically the same as the this reference in Java.
4Ok, this is heavy. It is a new operation, which allocates a given amount of memory from the WebAssembly linear memory. We will take a look at memory management later.
5Here we invoke the object constructor, which fills the allocated memory with life. We can see that the new operation and constructor invocation are different steps.
6Here we call the compute method. Now we pass in the reference to the allocated and constructed object.

Virtual function tables

So far, we have seen classes, instances and methods. Now, what happens if we override methods in a subclass? How can we handle something like this in WebAssembly? Compilers build so called virtual function tables to perform a lookup to find the right method for a given object instance. WebAssembly itself has the concept of tables, where we can assign an index with a function pointer. Ok, but how do we do the method lookup? Lets take a look at the WebAssembly code:

   (table 67 anyfunc)
   ;; left out for clarity
   (elem (i32.const 48) $HelloWorld__resolvevtableindex) (1)
   (elem (i32.const 52) $HelloWorld_INTcompute) (2)
   ;; left out for clarity
1This is the hidden ingredient, we hide the method lookup inside a function, which can be called. It has index 48.
2This is the reference to the implementation of the compute method in the HelloWorld class. It has index 52.

So what does our $HelloWorld__resolvevtableindex method do? We dive deeper:

   (func $HelloWorld__resolvevtableindex (param $thisRef i32) (param $p1 i32) (result i32) (1)
         (block $b
             (br_if $b (i32.ne (get_local $p1) (i32.const 3)))  (2)
             (return (i32.const 52)) (3)
         )
         (unreachable)
   )
1We have as inputs $thisRef as the object reference and $p1, which is the id of the method to be resolved.
2If method id is 3, we return index 52, which is the pointer to the $HelloWorld_INTcompute method as seen in the virtual function table. The method ids are assigned at compile time. Every method with the same name and signature gets the same id for itself and all its overridden variants.
352 is the index to $HelloWorld_INTcompute.

Ok, we can now lookup for a method implementation. How is this combined with a method call? We take a look at the main method in out HelloWorld example, but now we do an indirect call using the virtual function table:

   (type $t_INT_THISREF (func (param i32) (result i32))) (1)
   (type $t_RESOLVEMETHOD (func (param i32) (param i32) (result i32)))

   (func $HelloWorld_VOIDmainA1TString (param $UNUSED i32) (param $p1 i32)
         (local $var0 i32) ;; INT
         (local $var1 i32) ;; INT

         (set_local $var0 (2)
             (call $MemoryManager_AddressnewObjectINTINTINT
                (i32.const 0)
                (i32.const 8)
                (get_global $HelloWorld__runtimeClass)
                (i32.const 48))
         )

         (call $HelloWorld_VOIDinit (get_local $var0)) (3)

         (set_local $var1
             (call_indirect $t_INT_THISREF  (4)
                 (get_local $var0)
                 (call_indirect $t_RESOLVEMETHOD (5)
                     (get_local $var0)
                     (i32.const 3) (6)
                     (i32.load offset=4 (get_local $var0)) (7)
                 )
             )
         )
         (return)
   )
1For the WebAssembly call indirect functionality, we need typed function signatures. They are declared here. We basically need two types, one for the virtual function table resolve function and a second one for the implementation method itself.
2Our memory allocation
3Constructor invocation as usual
4Now it is getting interesting, we are calling a method of type $t_INT_THISREF, which takes $var0 as an argument(thisref), But we need also an index into the table to get the right function pointer. This index is resolved using the second call_indirect
5Here we are resolving the function index by calling the resolvevtableindex function for our newly created object
6We are trying to find the implementation for method id 3
7The resolvevtableindex for a given object is stored in the allocated object for this object. Here it is stored at offset=4

Interestingly, we are storing the index of the resolvevtableindex function for every object inside of the allocated memory for this object. So we have to pass in the right index at allocation time. We take a look at the memory allocation:

(call $MemoryManager_AddressnewObjectINTINTINT
    (i32.const 0) (1)
    (i32.const 8)  (2)
    (get_global $HelloWorld__runtimeClass) (3)
    (i32.const 48)) (4)
1This is a static method, so this is the $UNUSED argument, which defaults to 0.
2This is the size of the object. It has no fields, but a header of 8 bytes. So we allocated 8 bytes here.
3This is the type of the object. Types are our RuntimeClasses. RuntimeClasses are stored in global variables.
4This is the index of the virtual function resolver function, which is 48 as seen above.

Memory management

WebAssembly has a linear memory, which is sandboxed and can be freely accessed from WebAssembly as long as we keep the memory limits in mind. For our HelloWorld example, we need some kind of memory layout for the generated objects and other data that must be store during computation. We have to divide the linear memory into areas, which are basically a reserved area used by the memory manager and other runtime code, a Heap which hosts all allocated objects, and a Stack, which keeps local variables for every method invocation. There is a reasoning for keeping these areas distinguish. The heap can be very fragmented, as new objects are created or destroyed. On the other side, the Stack grows at precomputed rates which are determined at compile time. The compiler knows the exact number of local variables. Also the stack cannot fragment, as it is a FILO stack.

memorylayout

Now comes a limitation of the current WebAssembly specification: there is no memory manager! We have to do everything by hand. Even the garbage collector! Adding garbage collection is planned by the community group, but for now we have to implement a memory manager including a simple Mark-And-Sweep garbage collector. This is done by runtime classes which are included in the Bytecoder project. There are some tiny difficult bits here. First of all, why do we need a stack? There are local variables, why do I need an additional area in the linear memory? Well, for efficient garbage collection, the GC must crawl the Heap for dead objects, but this would also include newly created objects which are stored in local variables what are not used elsewhere. For security reasons, where is no way to introspect all live local variables in WebAssembly. To get around this issue, Bytecoder keeps primitive data types such as int and long in local variables, and but all variables of type reference on the stack and are visible to the garbage collector. Maybe I will write a second post about this topic later.

Accessing objects

Now, we can create new objects by allocating memory from the WebAssembly linear memory. How can we access those objects? Reading and writing to object fields is just simple memory access. We know the reference of the object, so we have a pointer to its allocated linear memory segment. We just need to assign a memory offset to every field of the object. This assignment can be done at compile time. Every instance field gets its own offset.

But what about static fields? Well, static fields are mapped as fields of a RuntimeClass. RuntimeClasses are global singletons, so they are a great place to store static data!

Arrays are a different beast. They are basically object instances, but their length cannot determined at compile time in every case. This dynamic nature is mapped to two components. A member attribute storing the actual length of the array instance, and a data attribute which stores the data for every array element. Since we can determine the exact size of a single typed array element at compile time, we just have to consider the variable length at runtime.

Here is an annotated example of a simple field access:

public class InstanceAccessTest {

    public static class StaticClassWithStuffInside {

        public int member;
    }

    @Test
    public void testInstanceGetAndSet() {
        StaticClassWithStuffInside theInstance = new StaticClassWithStuffInside();
        theInstance.member = 12;
    }
}

Written in WebAssembly:

(func $InstanceAccessTest_VOIDtestInstanceGetAndSet (param $thisRef i32)
     (local $SP i32)
     (local $OLD_SP i32)
     (set_local $OLD_SP (get_global $STACKTOP))
     (set_global $STACKTOP (i32.sub (get_global $STACKTOP) (i32.const 4))) (1)
     (set_local $SP (get_global $STACKTOP))

     (i32.store offset=0 (get_local $SP)
         (call $MemoryManager_AddressnewObjectINTINTINT
            (i32.const 0)
            (i32.const 12)
            (get_global $InstanceAccessTest$StaticClassWithStuffInside__runtimeClass)
            (i32.const 33))   (2)
     )
     (call $InstanceAccessTest$StaticClassWithStuffInside_VOIDinit
        (i32.load offset=0 (get_local $SP))) (3)

     (i32.store offset=8 (4)
         (i32.load offset=0 (get_local $SP)) (5)
         (i32.const 12) (6)
     )

     (set_global $STACKTOP (get_local $OLD_SP))
     (return)
)
1This reserves a place on the stack for a local object reference.
2Memory allocation as seen before.
3Constructor invocation, also nothing new now.
4offset=8 is computed at compile time referencing the field offset.
5We reference the instance using the stack.
6We store the integer constant 12 in the instance field.

Finalization and things I have left out

There are a lot of other features in modern high level programming languages available such as Enums, Exception handling, Lambda expressions or Reflections. Their implementation is far beyond the scope of this short WebAssembly introduction. If you want to dive deeper into how they can or cannot be implemented in WebAssembly, I suggest to take a look at my Bytecoder transpiler.

For now, I just have to say: thank your for reading!

Loading comments...