B# - A programming language for small footprint embedded systems applications: Part 2

It therefore provides a uniform mechanism to access device registers, create threads, and handle interrupts that would otherwise change from one hardware platform to another.

This uniformity promotes the development of reusable components (expressed in terms of binary code) that can migrate from one architecture to another as long as the B#EVM is available.

The memory devoted to the B#EVM is divided into two fundamental, but mutually dependent components: the data memory space and the code memory space as illustrated in Figure 1 below.

The data memory space stores the binary (virtual) code of an application along with the necessary descriptors, stacks, objects, and other data structures that are required to support its execution. The descriptors for threads, objects, stacks, console buffers, partitions, byte maps, the ready queue, and segments (both code and data) are preallocated when the virtual machine is compiled.

Other memory that is not preallocated, commonly referred to as the heap, is allocated dynamically either at load time (for literals and application code) or at run time (for objects and operand stacks).

Figure 1: Architecture of the B# Embedded Virtual Machine.

The code memory space of the B#EVM consists of those subsystems that actually execute the application. These systems provide the B# language with the low-level support to access device registers, create threads, and handle interrupts. In the three subsections that follow, we take a more detailed look at the memory manager, the stack machine, and the multi-thread kernel.

Memory Manager. The memory manager allocates and deallocates space for objects, stacks, and other structures within the virtual machine.T o efficiently allocate this space and to diminish fragmentation, the memory manager of the B#EVM uses a hybrid of static and dynamic allocations.

By default, three partitions of fixed-size blocks are created when the B#EVM is compiled:

1. Small blocks of 8 bytes each, mainly used for non-preallocated descriptors (arrays, strings, and so on).
2. Medium blocks of 32 bytes each, mainly used for default capacity buffers for composite types such as arrays and strings.
3. Large blocks of 128 bytes each, mainly used for large buffers.

The partition sizes, however, are configurable, but require the recompilation of the virtual machine.

To help satisfy the bounded time constraints of embedded systems, a byte map is also used to manage the allocation, deallocation and search for free blocks. The main advantage of this approach is its relative simplicity and efficiency in finding the first free block of N consecutive free blocks.

Each partition has a byte map and each byte map is implemented as a linked list. Because the linked list has a maximum fixed length, the search for available memory is also deterministic. For example, a request for 256 bytes will prompt the memory manager to examine the byte map associated with the large blocks, to select two consecutive available segments (if any), and to return the address of the first one.

Stack Machine. The design of most microcontrollers is based on the von Neumann model: a classic hardware architecture that includes a central processing unit (CPU) with registers for executing instructions, main and secondary memories, and input/output devices.

Such models are implemented for general register machines that have a set of numbered registers within the CPU and for accumulator machines that have a limited number of data accumulators, often just one.

On the other hand, the stack-machine model is an alternative architecture where the operand (runtime) stack of the current thread replaces the accumulator and other CPU registers used for temporary data storage. The stack therefore is used to load and store variables, arguments, and addresses.

Although some compiler optimization may be more difficult with a stack architecture, no register numbers or addressing modes need be specified in an instruction. Therefore, the number of instructions and their opcode size can be reduced, an important advantage for small footprint embedded systems.

In short, the B#EVM is a stack-machine interpreter that executes virtual code generated by the B# assembler. Values are pushed onto the stack, operations take values from the stack, and the results are pushed back where they are available for future calculations.

Multi-Thread Kernel. Because the B#EVM supports multithreading, a kernel or small operating system is needed to create, schedule, synchronize, and reschedule threads. When a thread is created, preallocated thread and stack descriptors are initialized to control access to the binary code of the thread and its operand (runtime) stack, respectively.

The operand stack is a collection of stack frames where each frame maintains the context of a method execution. This context includes local variables, temporary results, parameters, and return addresses. Therefore, each time a method is invoked, a stack frame is created.As the thread executes, the stack grows from low to high addresses to accommodate temporary results.

The stack descriptor contains the base (frame) address bp of the current frame, the address of the bottom of the stack stackBase, and the address of the top of the stack sp.

The thread descriptor, on the other hand, contains information on the base address of the code codeBase, its instruction pointer ip, and location of the corresponding stack descriptor.

Figure 2 below presents a typical memory model of the B# multi-thread kernel. In this case, the kernel is pointing to the thread descriptor that is currently running.

Although a single-thread application may contain several namespaces and classes, only one class contains the main entry method and implicitly becomes the main thread. In a multi-thread application, each object (instance of a class) with its own block of code may potentially become a thread (i.e. an active object) and therefore, requires a stack for saving its own context. Any object that does not become a thread shares the stack of the thread to which it belongs.

Figure 2. Memory Model of the Running Thread in B#.

Type Representation. The operand stack of B#EVM represents all values as 32-bit elements, regardless of their type. Therefore, to convert from one type to another is quite simply a question of “tagging” the stack element with a particular type.No descriptors are required since the type is set when the value or the reference is allocated on the stack.

To store this information, an additional stack within the B#EVM maintains the type information of the corresponding elements in the operand (runtime) stack. In this way, we eliminate the cost of wrappers (in terms of space, access, and allocation time) and avoid the definition of an hybrid type system that requires a clear distinction between value types (bool, char, int, uint, and float) and reference types (ioregs, arrays, strings, and delegates).

Another important reason for maintaining type information in this way is to reduce the size of the instruction set.Other virtual machines, such as the Sun JVM and Microsoft IL, have polluted their instruction sets with instructions that embed their information type.

An example of such proliferation is the add instruction which has a variation for each type of information: badd for byte addition, sadd for short addition, iadd for integer addition, and so on.

Seven instructions are required where only one instruction is required in B# since arithmetic operations are all promoted to 32 bits. Also, the type conversion instructions that are required before doing any arithmetic calculations are reduced since the add instruction in B#EVM is done within the instruction while checking and promoting (if necessary) the operand types. Although there is additional overhead, the instruction set and the generated code size are reduced.

Conclusion
In summary, the key and unique  (+) features of B# as a language for embedded systems applications are:
1) + Tiny (simple and minimal) in both its language definition (syntax [3] and semantics) and its code generation
2)     Familiar syntax
3) + Full support for object-orientation
* Fields and methods (static, instance, virtual, override, and abstract)
* Constructors (static and instance) and destructors
* +Memory defragmenter (deterministic and minimalist garbage collector)
* Field properties (getters, setters, and readonly fields)
* Delegates (callbacks)
*  + Device addressing (ISO/IEC Standard)
*  + Interrupt handlers
4) + Simplified, optimized, and unified type system
5) + Portable multi-threaded kernel (included in the virtual machine)

The toolset will be available for download at the BSharpLanguage.org, but in the meantime please contact the first author directly at mdec@DeepObjectKnowledge.com.

To read the first part in this series on the basics of the B# language, go to “An overview of B# language features.”

Michel is chief scientist of DeepObjectKnowledge Inc., an object-oriented training/mentoring firm located in Montreal, Quebec, Canada. He is also a former associate professor in Computer Engineering at Concordia University and a regular speaker at the Embedded Systems Conference. He can be contacted at mdec@DeepObjectKnowledge.com.
Brian is an associate professor of Computer Science/Studies at Trent University located in Peterborough, Ontario, Canada. His main research interests are programming languages and parallel job scheduling. Brian can be contacted at bpatrick@trentu.ca.

References
[1] M.Barr, Is C Passing?, Embedded.com, May 2002.
[2] J.W. Grenning, Why are you still using C?, Embedded.com, April 2003.
[3] M.de Champlain, B# Grammar, presents the grammatical summary of the B# programming language. Its syntax is described in a concise fashion using the EBNF notation. www.DeepObjectKnowledge.com\BSharpProject or www.BSharpLanguage.org
[4] M.de Champlain and B.G Patrick, B# Project: Object Design for Developping Small Embedded Systems Applications, will be published by Newnes/Elsevier, Fall 2006.