I know the answer (it's 42)

A blog on coding, .NET, .NET Compact Framework and life in general....

October, 2008

Posts
  • I know the answer (it's 42)

    C/C++ Compile Time Asserts

    • 5 Comments
    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
  • I know the answer (it's 42)

    Taking my job more seriously

    • 3 Comments
    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.

  • I know the answer (it's 42)

    Silverlight on Nokia S60 devices

    • 1 Comments
    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.

  • I know the answer (it's 42)

    Who halted the code

    • 3 Comments
    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

    image

    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.

  • I know the answer (it's 42)

    Hex signatures

    • 0 Comments
    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 :)

  • I know the answer (it's 42)

    Back To Basics: Finding your stack usage

    • 2 Comments
    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.

Page 1 of 1 (6 items)