Monday, October 27, 2008

C/C++ Compile Time Asserts

Noodles

The Problem

Run time asserts are fairly commonly used in C++. As the MSDN documentation for assert states

"(assert) Evaluates an expression and, when the result is false, prints a diagnostic message and aborts the program."

There is another type of asserts which can be used to catch code issues right at the time of compilation. These are called static or compile-time asserts. These asserts can be used to do compile time validations and are very effectively used in the .NET Compact Framework code base.

E.g. you have two types Foo and Bar and your code assumes (may be for a reinterpret_cast) that they are of the same size. Now being in separate places there is always a possibility that someone modifies one without changing the other and that results in some weird bugs. How do you express this assumption in code? Obviously you can do a run-time check like

assert(sizeof(foo) == sizeof(bar));

If that code is not hit during running this assert will not get fired. This might be caught in testing later. However, if you notice carefully all of the information is available during compilation (both the type and the sizeof is resolved while compilation). So we should be able to do compile time validation, with-something to the effect

COMPILE_ASSERT(sizeof(int) == sizeof(char));

This should be tested during compilation and hence whether the code is run or not the assert should fail.


The Solution


There are many ways to get this done. I will discuss two quick ways


Array creation


You can create a MACRO expression as follows

#define COMPILE_ASSERT(x) extern int __dummy[(int)x]

This macro works as follows

// compiles fine 
COMPILE_ASSERT(sizeof(int) == sizeof(unsigned));
// error C2466: cannot allocate an array of constant size 0
COMPILE_ASSERT(sizeof(int) == sizeof(char));

The first expression gets expanded to int __dummy[1] and compiles fine, but the later expands to int __dummy[0] and fails to compile.


The advantage of this approach is that it works for both C and C++, however, the failure message is very confusing and doesn't indicate what the failure is for. It is left to the developer to visit the line of compilation failure to see that it's a COMPILE_ASSERT.


sizeof on incomplete type


This approach works using explicit-specialization of template types and the fact that sizeof of incomplete types fail to compile.


Consider the following

namespace static_assert
{
template <bool> struct STATIC_ASSERT_FAILURE;
template <> struct STATIC_ASSERT_FAILURE<true> { enum { value = 1 }; };
}

Here we defined the generic type STATIC_ASSERT_FAILURE. As you see the type is incomplete (no member definition). However we do provide a explicit-specialization of that type for the value true. However, the same for false is not provided. This means that sizeof(STATIC_ASSERT_FAILURE<true>) is valid but sizeof(STATIC_ASSERT_FAILURE<false>) is not. This can be used to create a compile time assert as follows

namespace static_assert
{
template <bool> struct STATIC_ASSERT_FAILURE;
template <> struct STATIC_ASSERT_FAILURE<true> { enum { value = 1 }; };

template<int x> struct static_assert_test{};
}

#define COMPILE_ASSERT(x) \
typedef ::static_assert::static_assert_test<\
sizeof(::static_assert::STATIC_ASSERT_FAILURE< (bool)( x ) >)>\
_static_assert_typedef_

Here the error we get is as follows

// compiles fine
COMPILE_ASSERT(sizeof(int) == sizeof(unsigned));
// error C2027: use of undefined type 'static_assert::STATIC_ASSERT_FAILURE<__formal>
COMPILE_ASSERT(sizeof(int) == sizeof(char));

So the advantage is that the STATIC_ASSERT_FAILURE is called out right at the point of failure and is more obvious to figure out


The macro expansion is as follows



  1. typedef static_assert_test< sizeof(STATIC_ASSERT_FAILURE<false>) >  _static_assert_typedef_
  2. typedef static_assert_test< sizeof(incomplete type) >  _static_assert_typedef_

Similarly for true the type is not incomplete and the expansion is



  1. typedef static_assert_test< sizeof(STATIC_ASSERT_FAILURE<true>) >  _static_assert_typedef_
  2. typedef static_assert_test< sizeof(valid type with one enum member) >  _static_assert_typedef_
  3. typedef static_assert_test< 1 > _static_assert_typedef_

Put it all together


All together the following source gives a good working point to create static or compile time assert that works for both C and C++

#ifdef __cplusplus

#define JOIN( X, Y ) JOIN2(X,Y)
#define JOIN2( X, Y ) X##Y

namespace static_assert
{
template <bool> struct STATIC_ASSERT_FAILURE;
template <> struct STATIC_ASSERT_FAILURE<true> { enum { value = 1 }; };

template<int x> struct static_assert_test{};
}

#define COMPILE_ASSERT(x) \
typedef ::static_assert::static_assert_test<\
sizeof(::static_assert::STATIC_ASSERT_FAILURE< (bool)( x ) >)>\
JOIN
(_static_assert_typedef, __LINE__)

#else // __cplusplus

#define COMPILE_ASSERT(x) extern int __dummy[(int)x]

#endif // __cplusplus

#define VERIFY_EXPLICIT_CAST(from, to) COMPILE_ASSERT(sizeof(from) == sizeof(to))

#endif // _COMPILE_ASSERT_H_

The only extra part is the JOIN macros. They just ensure that the typedef is using new names each time and doesn't give type already exists errors.


More Reading



  1. Boost static_assert has an even better implementation that takes cares of much more scenarios and compiler quirks. Head over to the source at http://www.boost.org/doc/libs/1_36_0/boost/static_assert.hpp
  2. Modern C++ Design by the famed Andrei Alexandrescu

Thursday, October 23, 2008

Taking my job more seriously

Durga puja

I generally take my work very seriously. However, the following from SICP was still my favorite quote

"I think that it's extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don't think we are. I think we're responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don't become missionaries. Don't feel as if you're Bible salesmen. The world has too many of those already. What you know about computing other people will learn. Don't feel as if the key to successful computing is only in your hands. What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.''

However, couple of days back I was lying in a cold room with a doctor probing my Thyroid gland with ultrasound beams. She went on explaining the details of the tumor that I had, pointing to the screen. In my mind I was thinking about folks who have to code for these things and how careful they need to be.

The first thing I did when I came out of the room is search for whether .NET Compact Framework gets used for these kinds of equipment. Of the hundreds of pages I hit the one titled "Control System for Lung Ventilation Equipment with Windows CE , Microsoft .Net Compact Framework and Visual Studio Team System" struck me. Mostly because it had two products I personally coded for (NETCF and VSTS). There were even more life saving equipment listed on the search page.

It was a very humbling experience. I made a little vow, I'll be more careful when I code from tomorrow.

Wednesday, October 22, 2008

Silverlight on Nokia S60 devices

Frustrated?

In many of my blog posts (e.g.here and here) I refer to .NET Compact Framework and Symbian OS (S60) and obviously folks keep asking me via comments (or assume) that we are porting .NETCF on S60 devices. So I thought it's time to clarify :)

The short answer is that we are not porting .NETCF to S60 devices, but we are porting the Silverlight on S60 devices. This was jointly announced by Microsoft and Nokia, read Nokia's press release here.

We are in very early stage of development and it is very hard to tell how much will be in it (e.g. will it be SL v1.0 or v2.0). However, we are working hard and as and when more details emerge I will share it out from this blog. So keep reading.

Monday, October 20, 2008

Who halted the code

Fisher men

Today a bed time story involving un-initialized variable access and a weird coincidence.

Couple of weeks back I was kind of baffled with a weird issue I was facing with the .NET Compact Framework Jitter. We were making the Jitter work for Symbian OS (S60) emulator. The S60 emulator is a Windows process and hence we needed to bring up the i386 Jitter in our code base. After running some JITted code the application would stop executing with the message "Execution halted" in the stack trace.

Now obviously the user didn't halt anything and the program was a simple hello world.

After some debugging I found an interesting thing. For the debug build the Symbian C compiler memsets un-initialized variables to 0xcccc. This is fairly standard and is used to catch un-initialized variable access.

However, our Jit code had a bug such that in some scenario it was not emitting function call/returns correctly. So instead of returning we were executing arbitrary memory. But instead of some sort of access violation (or some thing equally bad) the execution was actually halting.

The reason was we started executing un-initialized data. Now this data is 0xcccc. The S60 debugger uses interrupt 3 (INT 3) for inserting breakpoints and the following line reveals the rest of the story

For i386 the instruction used for inserting breakpoint and the pattern used for un-initialized data matched and the debugger thought that it hit a breakpoint.

Friday, October 17, 2008

Hex signatures

Tooth paste advertisement

Frequently in code we need to add bit patterns or magic numbers. Since hex numbers have the alphabets A-F folks become creative and create all kinds of interesting words. Typical being 0xDEAD, 0xBEEF, 0xFEED or various combination of these like 0xFEEDBEEF. However, someone actually used the following in a sample

0xbed1babe

No naming the guilty :)

Thursday, October 16, 2008

Back To Basics: Finding your stack usage

Beads

Handling stack overflow is a critical requirement for most Virtual Machines. For .NET Compact framework (NETCF) it is more important because it runs on embedded devices with very little memory and hence little stack space.

The .NETCF Execution Engine (EE) needs to detect stack overflows and report it via StackOverflowException. To do this it uses some logic which we internally refer to as StackCheck (that will be covered in a later post). The algorithm needs fair prediction of stack usage for system APIs (e.g. Win32 APIs or for Symbian OS, S60 APIs).

Each time we target a new platform we do some measurements in addition to referring to specs :) to find it's stack characteristics. As we are currently making the NETCF work on Symbian OS we are doing these measurements again. So I thought of sharing how we are going about measuring stack usage using simple watermarking.

The technique

Step:1

On method Entry store the two current and max stack values. This typically available via system APIs which in case of Symbian is available over the TThreadStackInfo class (iBase, iLimit and other members).

                       +---------------+
| |
| |
| |
current stack ------> +---------------+
| |
| Available |
| Stack |
| |
| |
| |
| |
Stack limit ---------> +---------------+
| |
| |
. .
. .
. .

Step :2


Get a pointer on to the current stack pointer. How to get the pointer will vary based on the target platform. Options include system APIs, de-referencing stack pointer register (e.g. ESP register on x86) or simply creating a local variable on the stack and getting it's pointer.


Then Memset the whole region from current stack to the total available with some known pattern, e.g. 0xDEAD (a larger signature is a better approach to ensure there is no accidental match)

                       +---------------+
| |
| |
| |
current stack ------> +---------------+
| DEAD |
| DEAD |
| DEAD |
| DEAD |
| DEAD |
| DEAD |
| DEAD |
| DEAD |
Stack limit ---------> +---------------+
| |
| |
. .
. .
. .

Step: 3

Make an OS or whatever call you want to measure.

                       +---------------+
| |
| |
| |
current stack ------> +---------------+
| 1231 | --+
| 1231 | |
| D433 | +--> Stack usage
| D324 | |
| 3453 | --+
| DEAD |
| DEAD |
| DEAD |
Stack limit ---------> +---------------+
| |
| |
. .
. .
. .

Step 4:


When the call returns the stack will get modified. Iterate through the memory starting from the current stack pointer looking for the first occurrence of the pattern you’ve set in Step:2. This is the water mark and is the point till which the stack got used by the OS call. Subtract the water mark from the original entry point saved in Step 1 and you have the stack usage.