Dis Virtual Machine

For simplicity, this section uses the term thread to describe a thread of control created by the Limbo spawn statement. The terms process and OS process are used for Inferno processes and, in a hosted environment, host operating system processes. There are separate schedulers for Inferno processes and Limbo threads.

Memory Organization

All modules and threads share a single data heap. Program module instances and stack frames are allocated from the heap. Each heap object is associated with a type descriptor that contains its size and the location of pointers to other heap objects. Memory location information is transmitted in the form of type descriptors that are generated automatically by the Limbo compiler and the built-in module Loader.

When a new object is allocated, all of its pointers are initialized to nil, a value guaranteed to cause an exception if de-referenced. Memory protection is enforced by cooperation between the compiler and the virtual machine.

Memory is addressed as bytes. Words are stored in the native representation of the host CPU. Data types larger than a byte must be stored at aligned addresses.

Memory for a thread of execution is divided into several separate regions.

• The code segment stores either a decoded virtual machine instruction stream suitable for execution by the interpreter or native machine code that is compiled on-the-fly for the host CPU. Neither type of code segment is addressable from the Dis instruction set.
• A thread executing a module has access to two regions of data memory:
  • A module pointer (mp) defines a region of global storage for a particular module
  • A frame pointer (fp) defines the current frame activation record for the thread Frames are allocated dynamically from a stack by internal call and return instructions. The stack is extended automatically from the heap. The mp and fp registers cannot be addressed directly and can be modified only by call and return instructions.

• Memory can be allocated from the heap using various forms of new instructions and can subsequently be addressed using a double indirect addressing mode with the pointer stored in either fp or mp.

Garbage Collection

• Reference counting
• Real time mark-and-sweep for cyclic structures

Data structures that are cyclic are detected by the garbage collector running as an independent background process in the virtual machine. Cyclic structures are collected by a real time mark-and-sweep process using a four-color algorithm to ensure efficient deallocation. Since the mark-and-sweep collection only involves cyclic structures, it runs only for small quanta during the idle loop so it has little impact on system performance.

Program Execution

Execution continues for a given thread until one of the following conditions is met:

• The thread is completed and assigned an exiting state by Dis (Figure 1-2, Step A). A thread will also be released from the virtual machine if it is broken.

• The thread completes its quantum. When a thread executes a specified number of instructions, it is removed from virtual machine execution and placed on the Limbo thread ready queue (Figure 1-2, Step B). The ready queue is a linked list of threads that are waiting for access to the CPU.

• The thread must send a message to, or receive a message from, another thread. A send state (Figure 1-2, Step C) requires a receive message from another thread (Figure 1-2, Step D) to place it back into the ready queue. When a thread is placed into a send state, it will not be placed back on to the queue until the thread that is to receive its message accepts it. Similarly, a thread in a receive state is not placed back on to the queue until it has received the message and acknowledged it to the sender.

  The alt state exists when multiple messages must be exchanged among threads. The thread is removed from the ready queue and the alt routine coordinates multiple send and receive states across multiple channels.

• The thread is blocked (Figure 1-2, Step E). A thread is blocked when a file manipulation operation or a network access instruction is encountered. A sleep also blocks a thread. Threads are removed from contention when a release( ) request is issued. The operation that caused the block condition is then scheduled by the operating system.

  On completion of the blocking operation, the operating system process issues an acquire( ) call to signal Dis that the Limbo thread is ready to continue execution. When acquired, the thread is placed at the front of the ready queue.