Sunday, February 22, 2009

Reaching Closure...

A diligent reader commented on my previous post that the implementation of nested functions in D for .NET was buggy for multi-threaded programs.

Indeed, in the code below asyncWork() never returned. That's because a copy by-value of the variable go was used in the closure.

void main()
{
bool go;

void asyncWork()
{
while (!go)
{
//busy wait
}
}
Threading.Thread t = new Threading.Thread(&asyncWork);
t.Start();

go = true;
}

I am trying to avoid generating unverifiable code in this compiler project: IL does not allow managed pointers as fields in a class; ILASM accepts unmanaged pointers but that yields unverifiable code. My first instinct for closures was to use a copy for all the referenced variables, but as observed by my reader that approach did not work for multi-threaded programs.

One way to solve the problem is to use unmanaged pointers in the closure; under this implementation the example above runs correctly. There may be at least another solution: wrap each referenced variable into an object, and have both the nested function and the surrounding context share the object reference; I found it to convoluted and pursued the unmanaged pointers route instead.

This is how the generated IL looks for the D code in the example:

.module 'example'
.custom instance void [mscorlib]System.Security.UnverifiableCodeAttribute::.ctor() = ( 01 00 00 00 )


//--------------------------------------------------------------
// main program
//--------------------------------------------------------------
.method public hidebysig static void _Dmain ()
{
.entrypoint
.maxstack 3
.locals init (
[0] bool pinned 'go',
[1] class [mscorlib]System.Threading.Thread 't',
[2] class example.main.closure1 '$closure3'
)
newobj instance void example.main.closure1::.ctor()
stloc.s 2 // '$closure3'
ldloc.2 // '$closure3'
ldloca 0 // 'go'
stfld bool* 'example.main.closure1'::go2
ldloc.2 // '$closure3'
dup
ldvirtftn instance void example.main.closure1::'asyncWork' ()
newobj instance void class [mscorlib]System.Threading.ThreadStart::.ctor(object, native int)
newobj instance void [mscorlib]System.Threading.Thread::.ctor (ThreadStart)
stloc.s 1 // 't'
ldloc.1 // 't'
callvirt instance void [mscorlib]System.Threading.Thread::'Start' ()
ldc.i4 1
stloc.s 0 // 'go'
ret
}

.class private auto example.main.closure1 extends [dnetlib]core.Object
{

.method public virtual newslot hidebysig instance void 'asyncWork' ()
{
.maxstack 2
L1_example:
ldarg.0
ldfld bool* 'example.main.closure1'::go2
ldind.i1
ldc.i4 0
beq L1_example
ret
}
.field public bool* go2
// default ctor, compiler-generated
.method public hidebysig instance void .ctor()
{
ldarg.0
call instance void [dnetlib]core.Object::.ctor()
ret
}
} // end of example.main.closure1

Now there is only one more small problem to address: synchronization between threads...

Wednesday, February 11, 2009

Nested Functions and Delegates

My previous post missed one aspect of delegates in D: nested functions. Walter Bright gave me this example:

int delegate() foo(int i)
{
int bar() { return i; }
return &bar;
}

Function bar is nested inside foo; foo wraps bar into a delegate which is returned. My blog post is guilty of overlooking this use case for delegates; yet my compiler implementation is innocent: the example compiles and runs correctly.

The code example may look like a new use case at first, but is in fact similar to making a delegate from an object instance and a method:

class Foo {
int i;
int bar() { return i; }
}
...
Foo f = new Foo;
int delegate() dg = &f.bar;

The reason is that there is an invisible object in the nested function case. In the D programming language, nested functions have access to the surrounding lexical scope (note how function bar uses i which is declared as a parameter of foo); the .NET D compiler represents internally the lexical context of the nested function as an object. The fields of the context object are shallow copies of the variables in the "parent" scope. The IL class declaration for the context is synthesized by the compiler, which also instantiates the context. The context is populated on the way in (before calling the nested function) and used to update the variables in the parent scope on the way out (after the call has completed).

The constructor of a delegate object takes two parameters: an object reference and a pointer to a function; in the case of nested functions, the first parameter that the compiler passes under the hood is the context object. This is why constructing a delegate from a nested function is not different from using an object and one of its methods.

What if the nested function is declared inside of a class method (you ask). In this case there is no need to synthesize a class declaration to model the context of the nested call. The class to which the method belongs is augmented with hidden fields that shadow the variables in the parent scope.

Tuesday, February 10, 2009

Delegates in D for .NET

This past weekend I typed "Joe Newman" in Pandora and sat down for a couple of hours to implement delegates in my .NET back-end for the D compiler.

I begun by studying the documentation on MSDN and I noticed some differences in the way delegates work in .NET and D.

In .NET (and C#) delegates are objects that wrap pointers to functions so that they can be manipulated and invoked safely. The functions may be either standalone or members of a class. In D, the concept of delegates applies only to member functions. Delegates may be called asynchronously in .NET (I am not aware of a similar feature in the D programming language). The concept of delegates is thus simpler in D.

The implementation that I came up with is straight-forward: classes that derive from [mscorlib]System.MulticastDelegate are generated for each delegate type. The classes are sealed and each have a virtual Invoke method that matches the signature of the D delegate.

For the following D code snippet

class Test
{
void fun(int i)
{ ...
...
}
}
Test t = new Test;
void delegate(int) dg = &t.fun;

the generated IL looks like this:

.class sealed $Delegate_1 extends [mscorlib]System.MulticastDelegate
{
.method public instance void .ctor(object, native int) runtime managed {}
.method public virtual void Invoke(int32) runtime managed {}
}
...
...
.locals init (
[0] class Test 't',
[1] class $Delegate_1 'dg'
)
newobj instance void delegate.Test::.ctor ()
stloc.s 0 // 't'

ldloc.0 // 't'
dup
ldvirtftn instance void delegate.Test::'print' (int32 'i')
newobj instance void class $Delegate_1::.ctor(object, native int)
stloc.1

One small (and annoying) surprise that I had was that although the IL standard contains code samples with user-defined classes derived directly from [mscorlib]System.Delegate, such code did not pass PEVERIFY and, more tragically, crashed at run-time. The error message ("Unable to resolve token", or something like that) was not helpful; but the ngen utility dispelled the confusion by stating bluntly that my class could not inherit System.Delegate directly. Replacing System.Delegate with System.MulticastDelegate closed the issue.

Once I got delegates to work for class methods, I realized that the code can be reused to support D pointers to functions as well. In D pointers to functions are a different concept from delegates; in .NET however, a delegate can be constructed from a standalone function by simply passing a null for the object in the constructor. It is trivial for the compiler to generate code that instantiates .NET delegates in lieu of function pointers.

One nice side-effect of representing pointers to functions as delegates is that they can be aggregated as class members, unlike pointers to other data types that cannot be aggregated as struct or class fields (an IL-imposed restriction for managed pointers).

I hope that one day D decides to support asynchronous delegate calls. I have yet to imagine the possibilities for asynchronous, pure methods.

Until then, the .NET back-end is moving along getting closer and closer to a public release.

Sunday, February 08, 2009

D-elegating Constructors

The D programming language allows a constructor of a class to call another constructor of the same class, for the purpose of sharing initialization code. This feature is called "delegating constructors"; it is also present in C# and in the emerging C++ 0x.

C#'s syntax for delegating constructors resembles the initializer lists in C++, and strictly enforces that the delegated constructor is called before any other code in the body of the caller constructor; the feature is masterfully explained in More Effective C#: 50 Specific Ways to Improve Your C# (Effective Software Development Series).

D is more flexible, a constructor can be called from another constructor's body pretty much like any other "regular" method, provided that some simple rules are observed (for example, it is not permitted to call a constructor from within a loop).

A D compiler must detect constructor delegation and ensure that some initialization code is not executed more than once. Let's consider an example:

class Example
{
int foo = 42;
int bar;

this()
{
bar = 13;
}
this(int i)
{
foo = i;
this();
}
}

In the first constructor, before the field bar is assigned the value 13, some "invisible" code executes: first, the constructor of the base class is invoked. The Example class does not have an explicit base; but in D, similar to Java and C#, all classes have an implicit root Object base. It is as if we wrote:

class Example : Object
{ ...
}

After generating the call to Object's constructor, the compiler generates the code that initializes foo to 42. The explicit assignment as written by the programmer executes after wards.

The compiler must be careful so that the initializations steps described above happen only once in the second constructor. This is not simply a matter of efficiency; it is more importantly, a matter of correctness. If calling the base Object constructor and the initialization of foo where generated blindly inside the body of each constructor, then the following would happen in the second constructor's case:

  1. Object's ctor is invoked (compiler generated)

  2. foo = 42 (compiler generated)

  3. foo = i (programmer's code)

  4. constructor delegation occurs (programmer's code), which means that:

  5. Object's ctor is invoked

  6. foo = 42 (compiler generated)


This is obviously incorrect, since it leaves the Example object in a different state than the programmer intended.

Such scenario is very easily avoided by a native compiler. Object creation is translated to several distinct steps:

  1. memory for the object is allocated

  2. invocation of base ctor is generated

  3. initializers are generated (this is where foo = 42 happens)

  4. constructor as written by programmer is invoked


The important thing to note is that in the native compiler's case the compiler leaves the constructors alone, as written by the programmer, and inserts its magic "pre-initializaton" steps in between the memory allocation and constructor invocation.

When writing a compiler back-end for .NET things are slightly different: the creation of an object is expressed in one compact, single line of MSIL (Microsoft Intermediary Language) assembly code:

newobj <constructor call>

In our example, that would be

newobj void class Example::.ctor()

and

newobj void class Example::.ctor(int32)

respectively. So the compiler-generated magic steps of calling the base constructor, etc have to happen inside the constructor body. To prevent the erroneous scenario of double-initialization from happening, I had to generate a hidden, "guard" Boolean field for classes that use constructor delegation. The variable is set when entering a constructor's body; it is checked inside each constructor before calling the base constructor and stuff. Here's how the generated IL code looks like:

//--------------------------------------------------------------
// ctor.d compiled: Sun Feb 08 23:04:49 2009
//--------------------------------------------------------------
.assembly extern mscorlib {}
.assembly extern dnetlib {}
.assembly 'ctor' {}

.module 'ctor'


.class public auto ctor.Example extends [dnetlib]core.Object
{
.field public int32 foo
.field public int32 bar
.method public hidebysig instance void .ctor ()
{
.maxstack 3
ldarg.0
ldfld bool 'ctor.Example'::$in_ctor
brtrue L0_ctor
ldarg.0
call instance void [dnetlib]core.Object::.ctor()
ldarg.0
ldc.i4 42
stfld int32 'ctor.Example'::foo
L0_ctor:
ldarg.0 // 'this'
ldc.i4 13
stfld int32 'ctor.Example'::bar
ret
}
.method public hidebysig instance void .ctor (int32 'i')
{
.maxstack 3
ldarg.0
call instance void [dnetlib]core.Object::.ctor()
ldarg.0
ldc.i4 42
stfld int32 'ctor.Example'::foo
ldarg.0 // 'this'
ldarg.1 // 'i'
stfld int32 'ctor.Example'::foo
ldarg.0 // 'this'
ldc.i4 1
stfld bool 'ctor.Example'::$in_ctor
ldarg.0
call instance void ctor.Example::.ctor ()
ret
}
.field bool $in_ctor
} // end of ctor.Example

As a side note, in the second constructor's case a small redundancy still exists: foo is assigned to 42 only to be set to another value right away. I am hoping that this isn't much of an issue if the JIT engine detects it and optimizes it out. I'd be happy to hear any informed opinions.

Sunday, February 01, 2009

Stepping Over STL Code



When debugging C++ code written using the Standard Template Library (STL) it is not unusual to find yourself stepping through STL code. Most of the time, this is not very useful: The STL implementation typically comes bundled with the C++ compiler, and it has been thoroughly tested by the vendor; it is unlikely that the bug you are after is caused by the STL.

So when a statement such as myVector.push_back(x) is encountered while tracing with the debugger, you normally want to step over it, not into it. Most debuggers offer a "step over" and a "step into" function. So you would chose "step over".

But how about this? You want to debug a routine named my_func(size_t containerSize) and want to step into the body of my_func when this statement is hit: my_func(myVector.size()). If you select "step into", the debugger will first take you into the guts of STL's vector<T>::size() implementation before stepping into my_func.

The ZeroBUGS debugger allows you to avoid such annoyances. Once inside size(), you can right click, and select to "Always step over..." that function, all functions in that file, or all files in the same directory. The debugger will remember your option, and you don't have to see the guts of size(), or any other vector function, or any other STL function, respectively.

The functionality can be used not just with the STL but any code. If you later change your mind, the "Manage" menu allows you to remove functions, files or directories from the step-into blacklist.

To Destruct a D Struct

I wrote a while ago about similarities between D and .NET (and implicitly C#). My interest in mapping D features to .NET is driven by a research project that I took on a few months ago: a D 2.0 language compiler for .NET (D 2.0 is a branch version of D that includes experimental features). I was mentioning how in both D and C# structs are lightweight, value types.

After working on struct support in more detail, I have come to the realization that D structs cannot be implemented as .NET value type classes. Rather, they have to be implemented as reference type classes.

The short explanation is that while in IL value classes do not participate in garbage collection, D expects the GC to reap structs after they are no longer in use.

Interestingly enough, value types may be newobj-ed (not just created on the stack).

We can use a simple example to demonstrate the difference between value classes and reference classes. If we compile the following program using the IL assembler (ILASM) and run it, nothing gets printed on the screen:

.assembly extern mscorlib {}
.assembly 'test' {}

.class public value auto Test
{
.field public int32 i

.method public void .ctor()
{
ret
}
.method virtual family void Finalize()
{
ldstr "finalizing..."
call void [mscorlib]System.Console::WriteLine(string)
ret
}
}
//--------------------------------------------------------------
// main program
//--------------------------------------------------------------
.method public static void main ()
{
.entrypoint
.locals init (
class Test t
)
newobj instance void Test::.ctor()
stloc 't'
ret
}


But if we changed the declaration of the Test class from a value type to class, like this:

.class public auto Test

we could see "finalizing..." printed, a confirmation that the destructor (the Finalize method) is being invoked by the garbage collector. All it takes is removing "value" from the declaration.

In IL, value types have no self-describing type information attached. I suspect that the reason for not having them being garbage collected is that, without type information, the system cannot possibly know which (virtual) Finalize method to call (note that although C# struct are implemented as sealed value classes, "sealed" and "value" are orthogonal).

D supports the contract programming paradigm, and class invariants is one of its core concepts.

The idea is that the user can write a special method named "invariant", which tests that certain properties of a class or struct hold. In debug mode, the D compiler inserts "probing points" throughout the lifetime of the class (or struct), ensuring that this function is automatically called: after construction, before and after execution of public methods, and before destruction.

The natural mechanism for implementing the last statement is to generate a call to the invariant method at the top the destructor function body. But if the destructor is never called then we've got a problem.

So having destructors work correctly is not just a matter of collecting memory after the struct expires, but it is also crucial to contract programming in D.

Assignment to structs and passing in and to functions may become heavier weight in D.NET than in the native, Digital Mars D compiler (albeit this is something that I have to measure) by implementing structs as reference type classes, but it is necessary in order to support important D language features.

Thursday, January 22, 2009

42

Yesterday night, at the monthly NWCPP meeting Walter Bright gave a presentation on meta-programming using the D language. Once again, D put C++ to shame.

Because of transportation arrangements I could not accompany Walter et. Co to the watering hole after the lecture. Instead I went home and decided to test how my D.NET work-in-progress compiler handles templates, and what kind of code it generates.

I picked a variadic template for my test, which computes the maximum of an arbitrarily long list of numbers (adapted from a version written by Andrei Alexandrescu) :

import System;

auto max(T1, T2, Tail...)(T1 first, T2 second, Tail args)
{
auto r = second > first ? second : first;
static if (Tail.length == 0) {
return r;
}
else {
return max(r, args);
}
}

void main()
{
uint k = 42;
auto i = max(3, 2, k, 2.5);
Console.WriteLine(i);
}


The program above prints 42 (of course), and here's how the generated IL looks like:


//--------------------------------------------------------------
// max.d compiled: Thu Jan 22 19:38:26 2009
//--------------------------------------------------------------
.assembly extern mscorlib {}
.assembly extern dnetlib {}
.assembly 'max' {}

.module 'max'

//--------------------------------------------------------------
// main program
//--------------------------------------------------------------
.method public hidebysig static void _Dmain ()
{
.entrypoint
.maxstack 4
.locals init (
[0] unsigned int32 'k',
[1] float64 'i'
)
ldc.i4 42
stloc.s 0 // 'k'
ldc.i4 3
ldc.i4 2
ldloc.0 // 'k'
ldc.r8 2.5
call float64 _D3max16__T3maxTiTiTkTdZ3maxFiikdZd (
int32 'first', int32 'second', unsigned int32, float64)
stloc.s 1 // 'i'
ldloc.1 // 'i'
call void [mscorlib]System.Console::'WriteLine' (float64)
ret
}
.method public hidebysig static float64 _D3max16__T3maxTiTiTkTdZ3maxFiikdZd (
int32 'first', int32 'second', unsigned int32, float64)
{
.maxstack 4
.locals init (
[0] int32 'r'
)
ldarg.1 // 'second'
ldarg.0 // 'first'
bgt L0_max
ldarg.0 // 'first'
br L1_max
L0_max:
ldarg.1 // 'second'
L1_max:
stloc.s 0 // 'r'
ldloc.0 // 'r'
ldarg.2 // '_args_field_0'
ldarg.3 // '_args_field_1'
call float64 _D3max14__T3maxTiTkTdZ3maxFikdZd (
int32 'first', unsigned int32 'second', float64)
ret
}
.method public hidebysig static float64 _D3max14__T3maxTiTkTdZ3maxFikdZd (
int32 'first', unsigned int32 'second', float64)
{
.maxstack 3
.locals init (
[0] unsigned int32 'r'
)
ldarg.1 // 'second'
ldarg.0 // 'first'
conv.u4
bgt L2_max
ldarg.0 // 'first'
conv.u4
br L3_max
L2_max:
ldarg.1 // 'second'
L3_max:
stloc.s 0 // 'r'
ldloc.0 // 'r'
ldarg.2 // '_args_field_0'
call float64 _D3max12__T3maxTkTdZ3maxFkdZd (unsigned int32 'first', float64 'second')
ret
}
.method public hidebysig static float64 _D3max12__T3maxTkTdZ3maxFkdZd (
unsigned int32 'first', float64 'second')
{
.maxstack 2
.locals init (
[0] float64 'r'
)
ldarg.1 // 'second'
ldarg.0 // 'first'
conv.r8
bgt L4_max
ldarg.0 // 'first'
conv.r8
br L5_max
L4_max:
ldarg.1 // 'second'
L5_max:
stloc.s 0 // 'r'
ldloc.0 // 'r'
ret
}

Edit: One more reason for loving D templates: pasting D code into HTML does not require replacing angular brackets with &lt; and &gt; respectively!

Friday, January 16, 2009

Deeper and D-per

I am very excited about the D for .NET compiler project because of all the things I am learning. Books on my lab's desk these days are: Compiling for the .NET Common Language Runtime (CLR), Distributed Virtual Machines: Inside the Rotor CLI, Concepts of Programming Languages (8th Edition), The Dragon Book.

As I am digging deeper and deeper I am discovering interesting design challenges.

1. Enum

In .NET, the base class for enumerated types is System.Enum, which does not allow non-integral- (nor char-) based types.

D allows strings in enumerated types, like so:

enum : string
{
A = "hello",
B = "betty"
}

Possible solutions: make D.NET's enums based on [mscorlib]System.Enum and forbid non integrals (current implementation), or make my own [dnetlib]core.Enum base class. The problem with the latter is that it would preclude inter-operation with other languages. Walter Bright's suggestion (it is so clever that I wish I came up with it myself) is to use a combination of both solutions: generate structures derived from System.Enum when possible, and base them off a custom class when not. The D .NET compiler will split enums into two groups - those that are integral types, and those that are not, plus the "char" case. This allows interoperability without crippling language features.

2. Strings

D strings are UTF8, System.String is Unicode 16. My attempt to cleverly use System.String under the hood (rather than represent D strings as byte arrays) created way more complications than I initially thought, and prompted a major re-factoring effort that ate up almost my entire week-end.

An interesting wrinkle is that in D.NET associative arrays are implemented using Dictionary objects under the hood, which use the Equals method to compare keys. For System.String, Equals does a lexicographical comparison as one would normally expect; for System.Array, the implementation of Equals simply compares object references.

D strings are now represented as arrays of bytes; in order to make associative arrays work correctly, extra work had to be done.

3. Pointers

Can't do pointers as members of classes or elements in an array.

This stems from a restriction in the IL: cannot have managed pointers as class fields or array elements.

Interesting consequences:
3.a) in D.NET a nested method cannot access variables of pointer type in the surrounding lexical context (because the implementation constructs a delegate under the hood, and the object part has all the accessed variables copied as its members)

3.b) can't pass pointers to variadic functions (because I send in the variable argument list in as an array -- for compatibility with System.Console.WriteLine)

How severe are these limitations? Are there any reasonable workarounds? I guess I'll have to dig D-per to find out.

Tuesday, December 30, 2008

Jagging Away

The D programming language does not support multi-dimensional arrays.

Instead, multi-dimensional matrices can be implemented with arrays of arrays (aka jagged arrays), same as in C and C++.

When a static, multidimensional array needs to be initialized, in a statement such as:

int foo[3][4][5][6];

the native compiler back-end implicitly initializes the array by reserving the memory and filling it with zeros.

In the .NET back-end for the D compiler that I am working on, things are different: explicit newarr calls are required, in conjunction with navigating the data structure and initializing the individual elements.

And this is where it gets interesting. The array may have any arbitrary rank, and thus the compiler needs to figure out the types of the nested arrays; for the example above, they are:

int32 [][][][]
int32 [][][]
int32 [][]
int32 []

My implementation uses a runtime helper function in the dnetlib.dll assembly; rather than trying to determine the rank of the array and the types involved, the compiler back-end simply generates a call to the runtime helper, which does the heavy lifting. This solution works for jagged arrays of any rank.

The helper code itself is written in C# and uses generic recursion; it appends square brackets [] to the generic parameter at each recursion level, like shown below.

namespace runtime
{
public class Array
{
//helper for initalizing jagged array
static public void Init<T>(System.Array a, uint[] sizes, int start, int length)
{
if (length == 2)
{
uint n = sizes[start];
uint m = sizes[start + 1];
for (uint i = 0; i != n; ++i)
{
a.SetValue(new T[m], i);
}
}
else
{
--length;
//call recursively, changing template parameter from T to T[]
Init<T[]>(a, sizes, start, length);
uint n = sizes[start];
for (uint i = 0; i != n; ++i)
{
Init
<T>((System.Array)a.GetValue(i), sizes, start + 1, length);
}
}
}

//called at runtime
static public void Init<T>(System.Array a, uint[] sizes)
{
Init<T>(a, sizes, 0, sizes.Length);
}
}
} //namespace runtime

Sunday, December 28, 2008

Is There A Point in Using Pointers?

A few people wrote back in response to a previous blog post on the D for .NET project, some asking, well, why .NET?

Part of the answer is that .NET and D seem to be made for each other:

A common fragrance imbues both designs; for example, in D structs are not objects, but value types -- same as in C#. In D all objects inherit from a root object, which has methods such as toString , toHash and opEquals; in .NET, [mscorlib]System.Object sports ToString, GetHashCode, and Equals.

Still not convinced? How about array properties, then? In D there are properties such as sort, reverse, and dup; in .NET we have System.Array.Sort(), System.Array.Reverse(), and (tadaaa) System.Array.Clone(). Coincidence? Perhaps. Or maybe powerful memes where floating free in the air and found propitious hosts in both .NET and D (not unlike the idea of Python-scripting a debugger, which was pioneered by ZeroBUGS, and it is now being adopted by GDB).

But the cute metaphors have to stop somewhere (no honeymoon lasts forever) and so we come upon the thorny issue of pointers. D allows pointers, albeit does not encourage them. But unmanaged pointers (and even managed pointers arithmetic) does not yield verifiable code in .NET. I have experimented with both managed and unmanaged pointers, and generated textual IL that compiles and runs; PEVERIFY however refuses to put the seal of approval on such code.

And so I am very tempted to disallow pointers in class and struct members (in D, as in .NET objects are manipulated via references anyway, so what's the point of a pointer, anyway?)

A Good Idea is Worth Stealing

As always, the freetards in the Open Source community are stealing good ideas. Scripting the debugger with Python, pioneered by my work in ZeroBUGS is now copied by GDB: http://sourceware.org/ml/gdb/2008-02/msg00140.html

Too bad their implementation is awfully buggy.

And too bad that back in 2006 I did not think the idea was patentable :)

Sunday, December 21, 2008

Hello .NET, D Here Calling

A piece of advice from someone who spent fifteen years writing software professionally: if some "experts" ever say "printf debugging" is a poor technique, tell them to get out of town.

Printf debugging is helpful in a many great deal of situations, for example when you are writing a compiler. The debugger cannot be trusted, because the work-in-progress compiler may not output complete debug information just yet. But you can trust what's printed white on black on the screen.

There is a chicken and egg problem with printf though: how does one compile the implementation of printf (or writefln, as it is the case with the D programming language) if the compiler itself is not there?

Luckily, in my implementation of D for .NET (a project that I plan to release under the BSD in 2009) I was able to completely circumvent the problem. See, .NET already has a rich set of libraries and services. As a matter of fact, the very purpose of D.NET is to enable D programmers to take advantage of this state-of-the-art computing platform.

The obvious choice is to use one of the System.Console.WriteLine overloads instead of writefln. In order to do that, the front-end needs to know about System.Console. The good news is that Walter Bright's implementation of the D compiler front-end (which I am using) already handles imports.

In order to get this code to work

import System;

void main() {
System.Console.WriteLine("hello D.NET");
}

I wrote a System.d file, containing the D version of the Console class declaration (not complete, but good enough to get me going):

public class Console
{
static public void WriteLine();
static public void WriteLine(string);
static public void WriteLine(string, ...);

static public void WriteLine(char);
static public void WriteLine(bool);
static public void WriteLine(int);
static public void WriteLine(uint);
static public void WriteLine(long);
static public void WriteLine(float);
static public void WriteLine(double);

static public void Write(char);
static public void Write(string);
static public void Write(string, ...);

static public void Write(bool);
static public void Write(int);
static public void Write(long);
static public void Write(float);
static public void Write(double);
}

In the future, I plan to write a program that produces this kind of declaration automatically from .NET assemblies, using reflection.

Okay, so at this point the front-end compiles the "hello D.NET" code happily, but ILASM cannot resolve the System.Console::WriteLine symbol. This is because in IL the class names need to be qualified by assembly name, so what ILASM expects is a statement like:

call void class [mscorlib]System.Console::WriteLine(string)

One of my design guide lines for this project is to modify the front-end as least as possible, if at all. So then how do I get the imports to be fully qualified by assembly names?

With a clever hack, of course. I added these lines at the top of System.d:

class mscorlib { }
class assembly : mscorlib { }

Then I tweaked my back-end to recognize the "class assembly" construct and prefix the imported module names with whatever the name of the base class of the assembly class is.

Sunday, December 07, 2008

Dee Dot

It does not seem that long ago when I thought .NET and C# were mere toys compared to "real" languages such as C++. Oh well. One always lives to learn!

A couple of months ago I was tasked (at my day job) with making a legacy piece of C++ business logic inter-operate with another team's C# code. It was a small, one week project, but it forced me to pick up some .NET stuff along the way. Long story short, I was so intrigued with the maturity and elegance of the technology that I decided to push the exploration further, on my own time.

A friend and colleague of mine expressed interest in the past in writing a compiler back-end for the D language, that would generate .NET assemblies. So we met and re-discussed the project and decided to give it a go. The D language features map onto .NET quite well: there's no multiple inheritance of implementation, but one class can implement any number of interfaces; structs are value types, the D language is garbage-collected with provisions for explicit destructors (just implement IDisposable), and there are static constructors (.cctors in .NET).

D has static destructors also, which I found really easy to implement by generating code that registers a ProcessExit handler, like this:

// register static dtor as ProcessExit event handler
call class [mscorlib]System.AppDomain [mscorlib]System.AppDomain::get_CurrentDomain()
ldnull
ldftn void dtor.Base::'_staticDtor1'(object, class [mscorlib]System.EventArgs)
newobj instance void [mscorlib]System.EventHandler::.ctor(object, native int)
callvirt instance void [mscorlib]System.AppDomain::add_ProcessExit(class [mscorlib]System.EventHandler)
ret

Our approach so far is to generate IL assembly code, and then invoke ILASM. This way we are portable (the code so far works on Windows as well as with Novell's mono) and easy to debug.

We got some basic flow control working, and exception handling and assertions are also supported. But there's a long way to a fully-working compiler.

We intend to make the project open source (as soon as we decide upon the license -- I kind of hate the GPL for being anti-business and anti-profit, but the jury is still out on this one).

I think this is not just a great opportunity to bring the D language to the .NET family's table, but also give D programmers access to the wealth of libraries and utilities written for .NET to date.

Wednesday, September 24, 2008

Symbol Caches

OK, here I am back from a blogging sabbatical (summer in Seattle is so precious that it is sacrilegious not to spend it outside).

And the past few months have been quite eventful. I thought that everything out here in the blogosphere was going to be overshadowed by Real Life (kind of like Michael Phelps steeling the center stage away from Liam Tancock, a guy with a lot of bronze under his belt). Watching the news was a bit of a distraction I must admit...

But I spent the few rainy summer nights working on a ZeroBUGS new exciting feature: caching symbol tables and other debug information from one session to another.

This allows the debugger to start up faster, and use lesser memory (since the cached info is already indexed on disk, there is no need to build maps and hashes in memory).

I have deprecated an older implementation for caching symbol tables, that was based on memory-mapped files. The new code is built upon SQLite, and ensures data integrity with triggers that enforce foreign key constraints.

For the sake of stability, the commercial release does not feature the SQLite-based caches yet. The plan is to slowly burn in the new code through the beta builds, and have it officially released later this fall.

Thursday, July 10, 2008

RTFM

A number of people wrote to complain about ZeroBUGS not working properly, for example not stopping at main().

Guys, have you heard the phrase "the user is always wrong"? RTFM!

This is a known issue: http://www.zero-bugs.com/2.0/known_issues.html

And see:
http://www.granneman.com/blog/2006/06/13/how-virtual-machines-work/
and http://www.softpanorama.org/VM/index.shtml

as well as the wikipedia entry on VMware. You will find that "One must always rewrite; performing a simulation of the current program counter in the original location when necessary and (notably) remapping hardware code breakpoints".

Wednesday, June 25, 2008

Remote Attachment

In addition to being able to execute programs on a remote system from within the ZeroBUGS debugger, it is also possible to attach to remote processes.

When the remote proxy plug-in is detected, the UI automatically adds a "Target Parameters" field at the bottom of the "Attach to Process" dialog box.

After you type in the protocol ("remote://") followed by either the name or the IP address of the target system, and press the "Refresh" button the box will be populated with a list of processes running on the remote machine. Just select the desired process and click "Ok".

Sunday, June 22, 2008

May I Have the Remote, Please?

This past weekend I put the final touch on supporting remote debugging in my favorite C/C++ debugger for Linux, ZeroBUGS.

It is under test and will ship in the commercial version within the next five to ten days.

Currently, the remote debugger is not a cross-debugger, that is to say it only works between systems of the same architecture (adding support for cross-debugging is not terribly hard, I just do not want to spend rare Seattle summer days working on a feature, unless users ask for it).

"Well, then what's the point in supporting remote debugging", some may ask. "Can't we just ssh -X into the remote target and run the debugger there?"

Installing a full-fledged debugger, with a UI-module that depends heavily on Gnome may not be a feasible option for small (possibly embedded) systems where resources are scarce.

My solution for remote debugging is to install a thin, lightweight server on the target system, and have the debugger on a Linux workstation do the heavy lifting of building symbol tables, managing breakpoints, and so on.

In order to read debug information, the debugger needs access to the executable and shared objects on the target system. One possible solution is to copy them over to the workstation where the debugger runs, but it is not very practical. The amount of files to be copied can quickly go out of control, by ways of shared library dependencies.

I found that it is simpler to just mount the remote target onto the machine where the debugger runs. SSHFS is ideal for this job. Because the debug info may contain references to absolute path, ZeroBUGS provides the ZERO_REMOTE_PATH environmental variable, which creates an internal mapping between the mount point and the original paths.

Here are the steps for a remote debugging sessions, with examples from my own lab. The debugger runs on a 64 bit system (zulu) running Ubuntu 7.10, and the target executable(s) reside on another 64 bit machine (arnold) running Ubuntu 8.04.

1) Mount the filesystem of the target computer onto the debugger system. Example:

cristiv@zulu:~/workspace/sandbox$ sudo chown cristiv /dev/fuse
[sudo] password for cristiv:
cristiv@zulu:~/workspace/sandbox$ sshfs root@10.0.1.10:/ ~/workspace/remote/
root@10.0.1.10's password:
cristiv@zulu:~/workspace/sandbox$

2) Add mount point to remote map. Example:

export ZERO_REMOTE_MAP="10.0.1.10:/home/cristiv/workspace/remote;"

Note that each entry must be ended with a semicolon (even when there is only one entry in the map).

3) Start the ZeroBUGS server on the remote (debug target) system:

cristiv@arnold:~/workspace/zero$ zserver
*** ZeroBUGS Remote Debug Server V. 1.0 ***
*** Copyright (c) 2008 Zero Systems LLC ***
cristiv@arnold:~/workspace/zero$

To debug remotely programs running on host 10.0.1.10:
4) Run a remote program and debug it, using the command line:

zero remote://10.0.1.10/home/cristiv/workspace/zero/a.out

The UI can also be used to execute remote targets:


As a final note, please remember that the debug server opens a security whole on the target systems, since the client debugger can execute any program that the user who started the server can.

Monday, June 02, 2008

Take the Fork in the Road

A friend of mine (let's call him Andrei) who works on the D Programming Language sent me a bug report the other day. He was having trouble debugging this piece of D code with ZeroBUGS:

import std.stdio, std.process, std.string;
void main(string[] args)
{
writeln("Started on ", chomp(shell("hostname --short")));
}

After a brief investigation, I figured out what was going on: the shell call (equivalent to system in C) was triggering a fork(), followd by an exec() call. The debugger automatically attached to the spawned shell. After which point, every time my friend was trying to step through the code, control would jump from one process to the other in an apparent indeterministic fashion (I say apparent because the behavior is actually determined by how the kernel schedules the main, forked, and debugger processes).

I replied to the bug report with an explanation of what was going on, suggesting that the --no-trace-fork switch be passed in the command line (and thus avoid attaching to the forked shell).

My friend argued that this option should be more obvious (i.e. accessible from the graphical user interface) and while you are at it, he said, why not add a "spawn on fork" option, so that the two processes can be debugged in separate windows that do not interfere which each other?

I thought that was a great suggestion, and added (albeit only in the commercially-supported version) two new check-buttons to the Language tab in the Options dialog.

Caveat: Currently, the buttons are grayed out while a program is being debugged (i.e. are enabled only when no target is loaded in the debugger).

(This shortcoming has to do with setting ptrace options down a tree of attached threads, and I hope to address in a future release).


New releases of ZeroBUGS will be available later this week, when I launch the revamped website.

Thursday, May 22, 2008

Any Updates?

The zero-bugs.com site is about to be revamped, and the side picture should give you a sense of the new look and feel.

I had tremendous fun indulging my artistic side and created the new design using Inkscape 0.45 and Gimp (except for the product box).

The new site's main goal is to better manage software releases. A new back end component allows users to check for software updates (the debugger UI now has a new menu entry: Help --> Check for Updates).

I have improved my uploading script (which I have been using for pushing the software to the site); meta information is updated on the server side each time a binary is uploaded. The meta information is used by the "check for updates" feature; it is also used by a CGI to dynamically generate the download pages, so that users always download the most up-to-date code.

The debugger program connects to the server every time a user clicks on the "check for update" menu, and consults the meta information. Because the format of the server files containing software meta information is dictated by my uploading script, I did not want to hard-code the way these are read. Instead, I created a new client-side Python program.

I wanted the update mechanism to be as generic as possible, and allow for plug-ins to be updated independently, should such a need arise (for example when plug-ins from third-parties are included in the distribution).

To this end, I added a couple of new interfaces which look something like this:

struct Update : public ZObject
{
/**
* URL of the package (DEB, RPM, etc.) that contains an update.
*/
virtual const char* url() const = 0;

/**
* Description of changes in this update.
*/
virtual const char* description() const = 0;

virtual void apply() = 0;

virtual Update* copy() const = 0;
};


struct Updateable : public ZObject
{
virtual size_t check_for_updates(Enumerator<update*>*) = 0;
};
(The ZObject and the Enumerator are building blocks from my ZDK -- Zero Developer Toolkit -- on which the ZeroBUGS is built. They are not essential for the purpose of this post).

The way the update works is very simple: the engine queries each plugin for the Updateable interface. If the interface is detected, the check_for_updates method is invoked; the Enumerator then populates a container of pointers to Update objects, and the URL of each update is displayed in a UI HTML control.

With this simple, generic mechanism, each pluggable component can implement the details for its own update.

My concrete implementation lives in the Python scripting module which acts as a gateway between the bulk of the debugger code, written in C++, and extension written in Python.

The client-side script is ridiculously simple:

from datetime import datetime
import httplib
import urllib
import zero

server="www.zero-bugs.com"
published_dir="/8001/published/"

def check_for_updates(sysid, date):
print "checking updates for:", sysid, date
conn = httplib.HTTPConnection(server)
url = urllib.quote(published_dir + sysid)
conn.request("GET", url)
r = conn.getresponse()
info = r.read().split("\n")
conn.close()
my_build_date = datetime.strptime(date, "%Y-%m-%d")
build_date = datetime.strptime(info[0], "%Y-%m-%d")

if my_build_date < build_date:
url = "http://" + server + info[1]
info.pop(0) #pop the date
info.pop(0) #pop the url
info[0] = info[0] + "<br/>"
desc = "\n".join(info)
#
# functions returns a list of available updates
#
return [ zero.Update(url, desc) ]


I plan to launch the new site after Memorial Day. And after that I plan to release a new feature: support for remote debugging. I have written a minimalistic server and a companion plug-in that will allow users to debug machines where resources scarcity does not permit a full-fledged ZeroBUGS installation (you did not think that I took a three week hiatus from my blog just to re-write a website, heh).

Sunday, April 27, 2008

Super! Delegates

I have added support for D programming language delegates to the ZeroBUGS debugger!

And I am in the process of rolling out beta binaries, and a new release for Ubuntu 8.04 (Hardy Heron).

Happy (Eastern Orthodox) Easter!