Monday 26 January 2009

operator->() ad infinitum

Short version:

In C++, if an implementation of operator->() returns something different than a raw pointer, operator->() will be invoked on that return value; this will happen again and again until at some point a raw pointer is returned.


Lil' longer version:

One of the operators C++ allows to be overloaded is "->" . This enables syntactic constructions that mimic pointer usage, like smart pointers, which look like this...


template <typename T>
class MySmartPointer {
public:
MySmartPointer(T* pointee) : pointee_(pointee) {}

T* operator->() { return pointee_; }

/* some magic here... */

private:
T* pointee_;
};


Thus, you can use MySmartPointer with the same syntax as a plain T* :


MyClass* x (new MyClass);
x->doStuff();

MySmartPointer <MyClass> y (new MyClass);
y->doStuff();


However, if we declare operator->() to return something that is not a raw pointer, the compiler will generate code to invoke operator-> on that object, and so on:


struct Baz {
void sayHello() { cout << "hello" <<>() { return baz_; }
};
struct Bar {
Baz* baz_;
Baz* operator->() { return baz_; }
};
struct Foo {
Bar bar_;
Bar operator->() { return bar_; }
};

void doStuff () {
Foo foo;
foo->sayHello();
}



'doStuff' is equivalent to this:

void doStuff () {
Foo foo;
Bar bar (foo.operator->());
Baz* baz = bar.operator->();
baz->sayHello();
}


Bjarne Stroustrup used this language feature -plus a stack allocated auxiliary object- in a proposal for a C++ idiom for wrapping calls to member functions, enabling to perform stuff just before and just after any method call (i.e. intercept it). Let's see it in an example:


template<typename T>
class LockSmartPtrAux {
public:
LockSmartPtrAux(T* t, Lock& lock)
: t_(t), lock_(lock) {
lock_.lock(); /* lock at creation */
}
~LockSmartPtrAux() {
lock_.unlock(); /* unlock at destruction */
}
T* operator->() { return t_; }
private:
T* t_;
Lock& lock_;
};

template<typename T>
class LockSmartPtr {
public:
LockSmartPtr(T* t) : t_(t) {}
LockSmartPtrAux<T> operator->() {
return LockSmartPtrAux<T>(t_, lock_);
}
private:
T* t_;
Lock lock_;
};
// LockSmartPtrAux should be declared inside LockSmartPtr to enhance symbol locality


With the class templates above, you can "wrap" any class so that every invocation to its member functions is guarded by a lock, thus achieving some degree of transparent thread safety:


map<string, MyClass> cache;
/* fill cache with useful and hard to build stuff... */
LockSmartPtr<map<string,MyClass> > threadsafeCache(&cache);
doSomethingInAnotherThread1 (threadsafeCache);
doSomethingInAnotherThread2 (threadsafeCache);


Here follow some more details about the implementation...

  • To just perform some action (e.g. lock_.lock() ) BEFORE the "intercepted" call, you don't need an extra auxiliary object (e.g. LockSmartPtrAux), but only to invoke it before returning the pointee.

  • However, to perform some action (e.g. lock_.unlock() ) just AFTER the intercepted call and before the return, you have to place that action in the destructor of an auxiliary object and use operator-> trick.



This technique can be used to implement a rudimentary form of Aspect Oriented Programming in C++ by expressing cross-cutting concerns in these "wrapper" classes.

That's all the C++ trickery for today, hope you liked it.

NOTE: my implementation of LockSmartPtr assumes your compiler implements the name return value optimization (NRVO); if this does not hold true and you use non recursive locks, you will probably get a nasty deadlock due to temporary copies of LockSmartPtrAux locking an already locked mutex from the same thread. Check out Stroutstrup's paper to see how (managing lock ownership, forbidding assignment) he tackles this and other issues.

Sunday 4 January 2009

Embedding values in C++ pointers

Short version:

Read, compile and run the following piece of C++ source code:

#include <iostream>

class Smi {
public:
static Smi* fromInt(int value) {
return reinterpret_cast<Smi*>(value);
}
int value() {
return reinterpret_cast<int>(this);
}
void sayHello() {
std::cout << "Hello, my value is "
<< this->value() << "."
<< std::endl;
}
};

int main(void) {
Smi* five = Smi::fromInt(5);
Smi* seven = Smi::fromInt(7);
five->sayHello();
seven->sayHello();
return 0;
}


Notice the only state class Smi has is the integer value "embedded" in "this" pointer.

Lil' longer version:

C++ allows you to do pure magic. From time to time I see a piece of C++ code that makes me think: "Does this even compile?". A few days ago I discovered one of those "gems" within V8 (google chrome's javascript engine) source code.

Let's begin with a quiz: what do you think the following code could be for?

reinterpret_cast<int>(this)


Now with some more context...

int Smi::value() {
return reinterpret_cast<int>(this) >> kSmiTagSize;
}


Ummmm..... :|
Well, let's unveil the mystery...

V8 models every representable entity available in javascript (ECMAscript), all deriving from class Object, as comments in file objects.h sugest:

//
// All object types in the V8 JavaScript are described in this file.
//
// Inheritance hierarchy:
// - Object
// - Smi (immediate small integer)
// - Failure (immediate for marking failed operation)
// - HeapObject (superclass for everything allocated in the heap)
// - JSObject
// - JSArray
// - JSRegExp
// - JSFunction
...


Every instance of such entities is allocated and managed by class Heap, V8's runtime memory manager. When Heap is asked to allocate an Object, it returns an Object*, but such pointer carries a hidden surprise, as comments in objects.h depict:


// Formats of Object*:
// Smi: [31 bit signed int] 0
// HeapObject: [32 bit direct pointer] (4 byte aligned) | 01
// Failure: [30 bit signed int] 11


Such comments state three things (apart from the obvious one: what Heap returns as pointers to Object are not such...):
  • the least significant bits of the "pointer" carry a "tag" to indicate the kind of Object.

  • In the case of Smi* and Failure*, the bits remaining are not used to store any kind of pointer, but a numeric value (31 and 30 bits long respectively). This is the way to create an Smi*...

    Smi* Smi::FromInt(int value) {
    ASSERT(Smi::IsValid(value));
    return reinterpret_cast<Smi*>((value << kSmiTagSize) | kSmiTag);
    }

    ...and this is how to retrieve the value...

    int Smi::value() {
    return reinterpret_cast<int>(this) >> kSmiTagSize;
    }

    Thus they avoid the "overhead" of storing the pointer and the pointee, as both are the same.

  • When the "pointer" "points" to a HeapObject instance, the 30 most significant bits carry an actual pointer to a HeapObject that is aligned to 4 bytes, thus the two other bits are always zero, space which is used for the tag. To illustrate this, the following piece of code is the one that, from a true object address, makes up the tagged pointer:

    HeapObject* HeapObject::FromAddress(Address address) {
    ASSERT_TAG_ALIGNED(address);
    return reinterpret_cast(address + kHeapObjectTag);
    }



The trick works as long as you don't try to dereference one of those Object*...

Like some stuff in V8 native code generators I blogged about some time ago, this "tagged" "pointer" trick is not new but can also be found in StrongTalk and SelfVM (respectively Smalltalk an Self virtual machines that share creators with V8 :p)

Hope you enjoyed this curious trick!

My bugs love defensive programming

Short version:
Some forms of defensive programming hide bugs, YOUR bugs.
Other forms enforce design-by-contract style enhancing both quality and maintainability of the software.
Choose wisely...

Lil' longer version:
Of course you know what "defensive programming" is, but perhaps you haven't heard it being called so until now; let's see it in code:


public class NetworkFoo {
/**
* Performs connection.
* @param host Machine where server is running. Must not be null.
* @param port Port server is listening to. Must be in the range 1-65535.
*/
public void connect (String host, int port) {
if (host == null) {
return;
}
if (port < 1 || port > 65535) {
return;
}
...
}
...
}


Sure you have seen -or written- code like that, and that is just a form of defensive programming. The purpose of the techniques named under such term aim at making software robust against unexpected situations.

That sounds quite reasonable, however, many times the programmer does not fully understand the implications of how she chose to address the checks she wanted to be performed. To understand that, let's see a variant of the code above:


public class NetworkFoo {
/**
* Performs connection.
* @param host Machine where server is running. Must not be null.
* @param port Port server is listening to. Must be in the range 1-65535.
*/
public void connect (String host, int port) {
assert host != null;
assert (port > 0 && port <= 65535);
...
}
...
}


Here we have replaced 'if' blocks with assertions, so now instead of silently returning upon malformed parameters, the execution simply stops, as one of the preconditions is not matched.

What is the difference in method 'connect' of these two pieces of code? its preconditions and postconditions are NOT the same in both cases:
  • In the later, preconditions are: 'host' shall not be null and 'port' shall be between 1 and 65535.
  • In the former, although specified in the method header, there are no preconditions regarding parameters, but instead there is an extra implicit postcondition which states that when 'host' is null or 'port' is not between 1 and 65535, the method simply does nothing.

Thus, both ways of implementing such "guards" have different impact in our code and so we should be careful when choosing which approach we use in each case.

As stated at the beginning, defensive programming techniques try to shield code against unexpected [dangerous] situations that might break our logic; the most frequent checks are performed on method parameters or return values after invocations. When choosing how we protect the code, we have to take into account the origin of the "potentially malicious" data:
  • if such data comes directly from user input (or any other untrusted external interface), sure our logic should take into account malformed data,
  • but if we do the same checks on data coming from another method within our own code, we are hiding the fact that we were passed unproper parameters by our very selves!! and thus hiding our own bugs.

And what if we directly remove our "silently return" 'if' blocks and just rely on the caller meeting the preconditions we specified in the method header? If the method is called from our own code, there should be no problem, as long as we always wrote bug-free code, which for sure is not the case, so the behaviour of our method would be undefined for malformed input data, which means a hypothetical invocation to our method with unproper parameters could lead or not to a noticeable effect.

The following table summarizes the consequences of applying or not defensive programming to our methods:






Source of the "potentially dangerous" data
External source
Our own code
No defensive programming at all
Fragile code against malformed input
Undefined behaviour upon caller bugs
Silently return
Robust code against malformed input
Hide our own bugs
Assertions
Our code breaks upon malformed input
Design-by-contract style


[Ask google about design-by-contract to know more about it.]

One common thing is to disable assertions when a system goes into production, my opinion is that if it's tolerable for the system to crash (sporadically) then they should remain enabled, to detect bugs that escaped development and validation phases.

In the development of mission critical systems, it is not uncommon to enforce the 'silently do nothing' flavour of defensive programming in order to avoid [unexpected] crashes. I have no formed opinion about this topic...what is the most acceptable choice in these cases? I suppose a system crash is unacceptable, but is it to enable silent bugs?

Summing up, we can say defensive programming is a useful tool for chasing software quality and maintainability, but we should be wise when choosing the way we "protect" our code to assure we achieve code robustness without hiding our own bugs.