DEV Community: Matt Warren

ASCII Art in .NET Code

Matt Warren — Wed, 17 Jul 2019 13:07:18 +0000

Who doesn't like a nice bit of 'ASCII Art'? I know I certainly do!

To see what Matt's CLR was all about you can watch the recording of my talk 'From 'dotnet run' to 'Hello World!'' (from about ~24:30 in)

So armed with a trusty regex /\*(.*?)\*/|//(.*?)\r?\n|"((\\[^\n]|[^"\n])*)"|@("[^"]*")+, I set out to find all the interesting ASCII Art used in source code comments in the following .NET related repositories:

dotnet/CoreCLR - "the runtime for .NET Core. It includes the garbage collector, JIT compiler, primitive data types and low-level classes."
Mono - "open source ECMA CLI, C# and .NET implementation."
dotnet/CoreFX - "the foundational class libraries for .NET Core. It includes types for collections, file systems, console, JSON, XML, async and many others."
dotnet/Roslyn - "provides C# and Visual Basic languages with rich code analysis APIs"
aspnet/AspNetCore - "a cross-platform .NET framework for building modern cloud-based web applications on Windows, Mac, or Linux."

Note: Yes, I shamelessly 'borrowed' this idea from John Regehr, I was motivated to write this because his excellent post 'Explaining Code using ASCII Art' didn't have any .NET related code in it!

If you've come across any interesting examples I've missed out, please let me know!

To make the examples easier to browse, I've split them up into categories:

Table of Contents
Dave Cutler
Syntax Trees
Timelines
Logic Tables
Class Hierarchies
Component Diagrams
Algorithms
Bit Packing
Data Structures
State Machines
RFC's and Specs
Dates & Times
Stack Layouts
The Rest

Dave Cutler

There's no art in this one, but it deserves it's own category as it quotes the amazing Dave Cutler who led the development of Windows NT. Therefore there's no better person to ask a deep, technical question about how Thread Suspension works on Windows, from coreclr/src/vm/threadsuspend.cpp

// Message from David Cutler
/*
    After SuspendThread returns, can the suspended thread continue to execute code in user mode?

    [David Cutler] The suspended thread cannot execute any more user code, but it might be currently "running"
    on a logical processor whose other logical processor is currently actually executing another thread.
    In this case the target thread will not suspend until the hardware switches back to executing instructions
    on its logical processor. In this case even the memory barrier would not necessarily work - a better solution
    would be to use interlocked operations on the variable itself.

    After SuspendThread returns, does the store buffer of the CPU for the suspended thread still need to drain?

    Historically, we've assumed that the answer to both questions is No.  But on one 4/8 hyper-threaded machine
    running Win2K3 SP1 build 1421, we've seen two stress failures where SuspendThread returns while writes seem to still be in flight.

    Usually after we suspend a thread, we then call GetThreadContext.  This seems to guarantee consistency.
    But there are places we would like to avoid GetThreadContext, if it's safe and legal.

    [David Cutler] Get context delivers a APC to the target thread and waits on an event that will be set
    when the target thread has delivered its context.

    Chris.
*/

For more info on Dave Cutler, see this excellent interview 'Internets of Interest #6: Dave Cutler on Dave Cutler' or 'The engineer’s engineer: Computer industry luminaries salute Dave Cutler’s five-decade-long quest for quality'

Syntax Trees

The inner workings of the .NET 'Just-in-Time' (JIT) Compiler have always been a bit of a mystery to me. But, having informative comments like this one from coreclr/src/jit/lsra.cpp go some way to showing what it's doing

// For example, for this tree (numbers are execution order, lower is earlier and higher is later):
//
//                                   +---------+----------+
//                                   |       GT_ADD (3)   |
//                                   +---------+----------+
//                                             |
//                                           /   \
//                                         /       \
//                                       /           \
//                   +-------------------+           +----------------------+
//                   |         x (1)     | "tree"    |         y (2)        |
//                   +-------------------+           +----------------------+
//
// generate this tree:
//
//                                   +---------+----------+
//                                   |       GT_ADD (4)   |
//                                   +---------+----------+
//                                             |
//                                           /   \
//                                         /       \
//                                       /           \
//                   +-------------------+           +----------------------+
//                   |  GT_RELOAD (3)    |           |         y (2)        |
//                   +-------------------+           +----------------------+
//                             |
//                   +-------------------+
//                   |         x (1)     | "tree"
//                   +-------------------+

There's also a more in-depth example in coreclr/src/jit/morph.cpp

Also from roslyn/src/Compilers/VisualBasic/Portable/Semantics/TypeInference/RequiredConversion.vb

 '// These restrictions form a partial order composed of three chains: from less strict to more strict, we have:
'//    [reverse chain] [None] < AnyReverse < ReverseReference < Identity
'//    [middle  chain] None < [Any,AnyReverse] < AnyConversionAndReverse < Identity
'//    [forward chain] [None] < Any < ArrayElement < Reference < Identity
'//
'//            =           KEY:
'//         /  |  \           =     Identity
'//        /   |   \         +r     Reference
'//      -r    |    +r       -r     ReverseReference
'//       |  +-any  |       +-any   AnyConversionAndReverse
'//       |   /|\   +arr     +arr   ArrayElement
'//       |  / | \  |        +any   Any
'//      -any  |  +any       -any   AnyReverse
'//         \  |  /           none  None
'//          \ | /
'//           none
'//

Timelines

This example from coreclr/src/vm/comwaithandle.cpp was unique! I didn't find another example of ASCII Art used to illustrate time-lines, it's a really novel approach.

// In case the CLR is paused inbetween a wait, this method calculates how much 
// the wait has to be adjusted to account for the CLR Freeze. Essentially all
// pause duration has to be considered as "time that never existed".
//
// Two cases exists, consider that 10 sec wait is issued 
// Case 1: All pauses happened before the wait completes. Hence just the 
// pause time needs to be added back at the end of wait
// 0           3                   8       10
// |-----------|###################|------>
//                 5-sec pause    
//             ....................>
//                                            Additional 5 sec wait
//                                        |=========================> 
//
// Case 2: Pauses ended after the wait completes. 
// 3 second of wait was left as the pause started at 7 so need to add that back
// 0                           7           10
// |---------------------------|###########>
//                                 5-sec pause   12
//                             ...................>
//                                            Additional 3 sec wait
//                                                |==================> 
//
// Both cases can be expressed in the same calculation
// pauseTime:   sum of all pauses that were triggered after the timer was started
// expDuration: expected duration of the wait (without any pauses) 10 in the example
// actDuration: time when the wait finished. Since the CLR is frozen during pause it's
//              max of timeout or pause-end. In case-1 it's 10, in case-2 it's 12

Logic Tables

A sweet-spot for ASCII Art seems to be tables, there are so many examples. Starting with coreclr/src/vm/methodtablebuilder.cpp (bonus points for combining comments and code together!)

//               |        Base type
// Subtype       |        mdPrivateScope  mdPrivate   mdFamANDAssem   mdAssem     mdFamily    mdFamORAssem    mdPublic
// --------------+-------------------------------------------------------------------------------------------------------
/*mdPrivateScope | */ { { e_SM,           e_NO,       e_NO,           e_NO,       e_NO,       e_NO,           e_NO    },
/*mdPrivate      | */   { e_SM,           e_YES,      e_NO,           e_NO,       e_NO,       e_NO,           e_NO    },
/*mdFamANDAssem  | */   { e_SM,           e_YES,      e_SA,           e_NO,       e_NO,       e_NO,           e_NO    },
/*mdAssem        | */   { e_SM,           e_YES,      e_SA,           e_SA,       e_NO,       e_NO,           e_NO    },
/*mdFamily       | */   { e_SM,           e_YES,      e_YES,          e_NO,       e_YES,      e_NSA,          e_NO    },
/*mdFamORAssem   | */   { e_SM,           e_YES,      e_YES,          e_SA,       e_YES,      e_YES,          e_NO    },
/*mdPublic       | */   { e_SM,           e_YES,      e_YES,          e_YES,      e_YES,      e_YES,          e_YES   } };

Also coreclr/src/jit/importer.cpp which shows how the JIT deals with boxing/un-boxing

/*
    ----------------------------------------------------------------------
    | \ helper  |                         |                              |
    |   \       |                         |                              |
    |     \     | CORINFO_HELP_UNBOX      | CORINFO_HELP_UNBOX_NULLABLE  |
    |       \   | (which returns a BYREF) | (which returns a STRUCT)     |
    | opcode  \ |                         |                              |
    |---------------------------------------------------------------------
    | UNBOX     | push the BYREF          | spill the STRUCT to a local, |
    |           |                         | push the BYREF to this local |
    |---------------------------------------------------------------------
    | UNBOX_ANY | push a GT_OBJ of        | push the STRUCT              |
    |           | the BYREF               | For Linux when the           |
    |           |                         |  struct is returned in two   |
    |           |                         |  registers create a temp     |
    |           |                         |  which address is passed to  |
    |           |                         |  the unbox_nullable helper.  |
    |---------------------------------------------------------------------
*/

Finally, there's some other nice examples showing the rules for operator overloading in the C# (Roslyn) Compiler and which .NET data-types can be converted via the System.ToXXX() functions.

Class Hierarchies

Of course, most IDE's come with tools that will generate class-hierarchies for you, but it's much nicer to see them in ASCII, from coreclr/src/vm/object.h

 * COM+ Internal Object Model
 *
 *
 * Object              - This is the common base part to all COM+ objects
 *  |                        it contains the MethodTable pointer and the
 *  |                        sync block index, which is at a negative offset
 *  |
 *  +-- code:StringObject       - String objects are specialized objects for string
 *  |                        storage/retrieval for higher performance
 *  |
 *  +-- BaseObjectWithCachedData - Object Plus one object field for caching.
 *  |       |
 *  |       +-  ReflectClassBaseObject    - The base object for the RuntimeType class
 *  |       +-  ReflectMethodObject       - The base object for the RuntimeMethodInfo class
 *  |       +-  ReflectFieldObject        - The base object for the RtFieldInfo class
 *  |
 *  +-- code:ArrayBase          - Base portion of all arrays
 *  |       |
 *  |       +-  I1Array    - Base type arrays
 *  |       |   I2Array
 *  |       |   ...
 *  |       |
 *  |       +-  PtrArray   - Array of OBJECTREFs, different than base arrays because of pObjectClass
 *  |              
 *  +-- code:AssemblyBaseObject - The base object for the class Assembly

There's also an even larger one that I stumbled across when writing "Stack Walking" in the .NET Runtime.

Component Diagrams

When you have several different components in a code-base it's always nice to see how they fit together. From coreclr/src/vm/codeman.h we can see how the top-level parts of the .NET JIT work together

                                               ExecutionManager
                                                       |
                           +-----------+---------------+---------------+-----------+--- ...
                           |           |                               |           |
                        CodeType       |                            CodeType       |
                           |           |                               |           |
                           v           v                               v           v
+---------------+      +--------+<---- R    +---------------+      +--------+<---- R
|ICorJitCompiler|<---->|IJitMan |<---- R    |ICorJitCompiler|<---->|IJitMan |<---- R
+---------------+      +--------+<---- R    +---------------+      +--------+<---- R
                           |       x   .                               |       x   .
                           |        \  .                               |        \  .
                           v         \ .                               v         \ .
                       +--------+      R                           +--------+      R
                       |ICodeMan|                                  |ICodeMan|     (RangeSections)
                       +--------+                                  +--------+

Other notable examples are:

Finally, from coreclr/src/vm/ceeload.cpp we see the inner-workings of the Native Image Generator (NGEN)

        This diagram illustrates the layout of fixups in the ngen image.
        This is the case where function foo2 has a class-restore fixup
        for class C1 in b.dll.

                                  zapBase+curTableVA+rva /         FixupList (see Fixup Encoding below)
                                  m_pFixupBlobs
                                                            +-------------------+
                  pEntry->VA +--------------------+         |     non-NULL      | foo1
                             |Handles             |         +-------------------+
ZapHeader.ImportTable        |                    |         |     non-NULL      |
                             |                    |         +-------------------+
   +------------+            +--------------------+         |     non-NULL      |
   |a.dll       |            |Class cctors        |<---+    +-------------------+
   |            |            |                    |     \   |         0         |
   |            |     p->VA/ |                    |<---+ \  +===================+
   |            |      blobs +--------------------+     \ +-------non-NULL      | foo2
   +------------+            |Class restore       |      \  +-------------------+
   |b.dll       |            |                    |       +-------non-NULL      |
   |            |            |                    |         +-------------------+
   |  token_C1  |<--------------blob(=>fixedUp/0) |<--pBlob--------index        |
   |            | \          |                    |         +-------------------+
   |            |  \         +--------------------+         |     non-NULL      |
   |            |   \        |                    |         +-------------------+
   |            |    \       |        .           |         |         0         |
   |            |     \      |        .           |         +===================+
   +------------+      \     |        .           |         |         0         | foo3
                        \    |                    |         +===================+
                         \   +--------------------+         |     non-NULL      | foo4
                          \  |Various fixups that |         +-------------------+
                           \ |need too happen     |         |         0         |
                            \|                    |         +===================+
                             |(CorCompileTokenTable)
                             |                    |
               pEntryEnd->VA +--------------------+

Algorithms

They say 'a picture paints a thousand words' and that definately applies when describing complex algorithms, from roslyn/src/Workspaces/Core/Portable/Utilities/EditDistance.cs

// If we fill out the matrix fully we'll get:
//          
//           s u n d a y <-- source
//      ----------------
//      |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
//      |∞ 0 1 2 3 4 5 6
//    s |∞ 1 0 1 2 3 4 5 
//    a |∞ 2 1 1 2 3 3 4 
//    t |∞ 3 2 2 2 3 4 4 
//    u |∞ 4 3 2 3 3 4 5 
//    r |∞ 5 4 3 3 4 4 5 
//    d |∞ 6 5 4 4 3 4 5 
//    a |∞ 7 6 5 5 4 3 4 
//    y |∞ 8 7 6 6 5 4 3 <--
//                     ^
//                     |

Next, this gem that explains how the DOS wild-card matching works, corefx/src/System.IO.FileSystem/src/System/IO/Enumeration/FileSystemName.cs

// Matching routine description
// ============================
// (copied from native impl)
//
// This routine compares a Dbcs name and an expression and tells the caller
// if the name is in the language defined by the expression.  The input name
// cannot contain wildcards, while the expression may contain wildcards.
//
// Expression wild cards are evaluated as shown in the nondeterministic
// finite automatons below.  Note that ~* and ~? are DOS_STAR and DOS_QM.
//
//        ~* is DOS_STAR, ~? is DOS_QM, and ~. is DOS_DOT
//
//                                  S
//                               <-----<
//                            X  |     |  e       Y
//        X * Y ==       (0)----->-(1)->-----(2)-----(3)
//
//                                 S-.
//                               <-----<
//                            X  |     |  e       Y
//        X ~* Y ==      (0)----->-(1)->-----(2)-----(3)
//
//                           X     S     S     Y
//        X ?? Y ==      (0)---(1)---(2)---(3)---(4)
//
//                           X     .        .      Y
//        X ~.~. Y ==    (0)---(1)----(2)------(3)---(4)
//                              |      |________|
//                              |           ^   |
//                              |_______________|
//                                 ^EOF or .^
//
//                           X     S-.     S-.     Y
//        X ~?~? Y ==    (0)---(1)-----(2)-----(3)---(4)
//                              |      |________|
//                              |           ^   |
//                              |_______________|
//                                 ^EOF or .^
//
//    where S is any single character
//          S-. is any single character except the final .
//          e is a null character transition
//          EOF is the end of the name string
//
//   In words:
//
//       * matches 0 or more characters.
//       ? matches exactly 1 character.
//       DOS_STAR matches 0 or more characters until encountering and matching
//           the final . in the name.
//       DOS_QM matches any single character, or upon encountering a period or
//           end of name string, advances the expression to the end of the
//           set of contiguous DOS_QMs.
//       DOS_DOT matches either a . or zero characters beyond name string.

Finally from roslyn/src/Workspaces/Core/Portable/Shared/Collections/IntervalTree1.Node.cs we have per-method comments with samples, this is a great idea!

// Sample:
//   1            1                  3
//  / \          / \              /     \
// a   2        a   3            1       2
//    / \   =>     / \     =>   / \     / \
//   3   d        b   2        a   b   c   d
//  / \              / \
// b   c            c   d
internal Node InnerRightOuterLeftRotation(IIntervalIntrospector<T> introspector)
{
    ...
}

// Sample:
//     1              1              3
//    / \            / \          /     \
//   2   d          3   d        2       1
//  / \     =>     / \     =>   / \     / \
// a   3          2   c        a   b   c   d
//    / \        / \
//   b   c      a   b
internal Node InnerLeftOuterRightRotation(IIntervalIntrospector<T> introspector)
{
    ...
}

Bit Packing

Maybe you can visualise which individual bits are set given a Hexadecimal value, but I can't, so I'm always grateful for comments like this one from roslyn/src/Compilers/CSharp/Portable/Symbols/Source/SourceMemberContainerSymbol.cs

// We current pack everything into two 32-bit ints; layouts for each are given below.

// First int:
//
// | |d|yy|xxxxxxxxxxxxxxxxxxxxxxx|wwwwww|
//
// w = special type.  6 bits.
// x = modifiers.  23 bits.
// y = IsManagedType.  2 bits.
// d = FieldDefinitionsNoted. 1 bit

This one from corefx/src/System.Runtime.WindowsRuntime/src/System/Threading/Tasks/TaskToAsyncInfoAdapter.cs also does a great job of showing the different bit-flags and how they interact

// ! THIS DIAGRAM ILLUSTRATES THE CONSTANTS BELOW. UPDATE THIS IF UPDATING THE CONSTANTS BELOW!:
//     3         2         1         0
//    10987654321098765432109876543210
//    X...............................   Reserved such that we can use Int32 and not worry about negative-valued state constants
//    ..X.............................   STATEFLAG_COMPLETED_SYNCHRONOUSLY
//    ...X............................   STATEFLAG_MUST_RUN_COMPLETION_HNDL_WHEN_SET
//    ....X...........................   STATEFLAG_COMPLETION_HNDL_NOT_YET_INVOKED
//    ................................   STATE_NOT_INITIALIZED
//    ...............................X   STATE_STARTED
//    ..............................X.   STATE_RUN_TO_COMPLETION
//    .............................X..   STATE_CANCELLATION_REQUESTED
//    ............................X...   STATE_CANCELLATION_COMPLETED
//    ...........................X....   STATE_ERROR
//    ..........................X.....   STATE_CLOSED
//    ..........................XXXXXX   STATEMASK_SELECT_ANY_ASYNC_STATE
//    XXXXXXXXXXXXXXXXXXXXXXXXXX......   STATEMASK_CLEAR_ALL_ASYNC_STATES
//     3         2         1         0
//    10987654321098765432109876543210

Finally, we have some helpful explanations of how different encoding work. Firstly UTF-8 from corefx//src/Common/src/CoreLib/System/Text/UTF8Encoding.cs

/*
    bytes   bits    UTF-8 representation
    -----   ----    -----------------------------------
    1        7      0vvvvvvv
    2       11      110vvvvv 10vvvvvv
    3       16      1110vvvv 10vvvvvv 10vvvvvv
    4       21      11110vvv 10vvvvvv 10vvvvvv 10vvvvvv
    -----   ----    -----------------------------------
    Surrogate:
    Real Unicode value = (HighSurrogate - 0xD800) * 0x400 + (LowSurrogate - 0xDC00) + 0x10000
*/

and then UTF-32 in corefx/src/Common/src/CoreLib/System/Text/UTF32Encoding.cs

/*
    words   bits    UTF-32 representation
    -----   ----    -----------------------------------
    1       16      00000000 00000000 xxxxxxxx xxxxxxxx
    2       21      00000000 000xxxxx hhhhhhll llllllll
    -----   ----    -----------------------------------
    Surrogate:
    Real Unicode value = (HighSurrogate - 0xD800) * 0x400 + (LowSurrogate - 0xDC00) + 0x10000
*/

Data Structures

This comment from mono/utils/dlmalloc.c does a great job of showing how chunks of memory are arranaged by malloc

  A chunk that's in use looks like:

   chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
           | Size of previous chunk (if P = 1)                             |
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
         | Size of this chunk                                         1| +-+
   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         |                                                               |
         +-                                                             -+
         |                                                               |
         +-                                                             -+
         |                                                               :
         +-      size - sizeof(size_t) available payload bytes          -+
         :                                                               |
 chunk-> +-                                                             -+
         |                                                               |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|
       | Size of next chunk (may or may not be in use)               | +-+
 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    And if it's free, it looks like this:

   chunk-> +-                                                             -+
           | User payload (must be in use, or we would have merged!)       |
           +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|
         | Size of this chunk                                         0| +-+
   mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         | Next pointer                                                  |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         | Prev pointer                                                  |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         |                                                               :
         +-      size - sizeof(struct chunk) unused bytes               -+
         :                                                               |
 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
         | Size of this chunk                                            |
         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|
       | Size of next chunk (must be in use, or we would have merged)| +-+
 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               :
       +- User payload                                                -+
       :                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                                                     |0|
                                                                    +-+

Also, from corefx/src/Common/src/CoreLib/System/MemoryExtensions.cs we can see how overlapping memory regions are detected:

//  Visually, the two sequences are located somewhere in the 32-bit
//  address space as follows:
//
//      [----------------------------------------------)                            normal address space
//      0                                             2³²
//                            [------------------)                                  first sequence
//                            xRef            xRef + xLength
//              [--------------------------)     .                                  second sequence
//              yRef          .         yRef + yLength
//              :             .            .     .
//              :             .            .     .
//                            .            .     .
//                            .            .     .
//                            .            .     .
//                            [----------------------------------------------)      relative address space
//                            0            .     .                          2³²
//                            [------------------)             :                    first sequence
//                            x1           .     x2            :
//                            -------------)                   [-------------       second sequence
//                                         y2                  y1

State Machines

This comment from mono/benchmark/zipmark.cs gives a great over-view of the implementation of RFC 1951 - DEFLATE Compressed Data Format Specification

/*
 * The Deflater can do the following state transitions:
    *
    * (1) -> INIT_STATE   ----> INIT_FINISHING_STATE ---.
    *        /  | (2)      (5)                         |
    *       /   v          (5)                         |
    *   (3)| SETDICT_STATE ---> SETDICT_FINISHING_STATE |(3)
    *       \   | (3)                 |        ,-------'
    *        |  |                     | (3)   /
    *        v  v          (5)        v      v
    * (1) -> BUSY_STATE   ----> FINISHING_STATE
    *                                | (6)
    *                                v
    *                           FINISHED_STATE
    *    \_____________________________________/
    *          | (7)
    *          v
    *        CLOSED_STATE
    *
    * (1) If we should produce a header we start in INIT_STATE, otherwise
    *     we start in BUSY_STATE.
    * (2) A dictionary may be set only when we are in INIT_STATE, then
    *     we change the state as indicated.
    * (3) Whether a dictionary is set or not, on the first call of deflate
    *     we change to BUSY_STATE.
    * (4) -- intentionally left blank -- :)
    * (5) FINISHING_STATE is entered, when flush() is called to indicate that
    *     there is no more INPUT.  There are also states indicating, that
    *     the header wasn't written yet.
    * (6) FINISHED_STATE is entered, when everything has been flushed to the
    *     internal pending output buffer.
    * (7) At any time (7)
    *
    */

This might be pushing the definition of 'state machine' a bit far, but I wanted to include it because it shows just how complex 'exception handling' can be, from coreclr/src/jit/jiteh.cpp

// fgNormalizeEH: Enforce the following invariants:
//
//   1. No block is both the first block of a handler and the first block of a try. In IL (and on entry
//      to this function), this can happen if the "try" is more nested than the handler.
//
//      For example, consider:
//
//               try1 ----------------- BB01
//               |                      BB02
//               |--------------------- BB03
//               handler1
//               |----- try2 ---------- BB04
//               |      |               BB05
//               |      handler2 ------ BB06
//               |      |               BB07
//               |      --------------- BB08
//               |--------------------- BB09
//
//      Thus, the start of handler1 and the start of try2 are the same block. We will transform this to:
//
//               try1 ----------------- BB01
//               |                      BB02
//               |--------------------- BB03
//               handler1 ------------- BB10 // empty block
//               |      try2 ---------- BB04
//               |      |               BB05
//               |      handler2 ------ BB06
//               |      |               BB07
//               |      --------------- BB08
//               |--------------------- BB09
//

RFC's and Specs

Next up, how the Kestrel web-server handles RFC 7540 - Hypertext Transfer Protocol Version 2 (HTTP/2).

Firstly, from aspnet/AspNetCore/src/Servers/Kestrel/Core/src/Internal/Http2/Http2Frame.cs

/* https://tools.ietf.org/html/rfc7540#section-4.1
    +-----------------------------------------------+
    |                 Length (24)                   |
    +---------------+---------------+---------------+
    |   Type (8)    |   Flags (8)   |
    +-+-------------+---------------+-------------------------------+
    |R|                 Stream Identifier (31)                      |
    +=+=============================================================+
    |                   Frame Payload (0...)                      ...
    +---------------------------------------------------------------+
*/

and then in aspnet/AspNetCore/src/Servers/Kestrel/Core/src/Internal/Http2/Http2Frame.Headers.cs

/* https://tools.ietf.org/html/rfc7540#section-6.2
    +---------------+
    |Pad Length? (8)|
    +-+-------------+-----------------------------------------------+
    |E|                 Stream Dependency? (31)                     |
    +-+-------------+-----------------------------------------------+
    |  Weight? (8)  |
    +-+-------------+-----------------------------------------------+
    |                   Header Block Fragment (*)                 ...
    +---------------------------------------------------------------+
    |                           Padding (*)                       ...
    +---------------------------------------------------------------+
*/

There are other notable examples in aspnet/AspNetCore/src/Servers/Kestrel/Core/src/Internal/Http2/Http2FrameReader.cs and aspnet/AspNetCore/src/Servers/Kestrel/Core/src/Internal/Http2/Http2FrameWriter.cs.

Also RFC 3986 - Uniform Resource Identifier (URI) is discussed in corefx/src/Common/src/System/Net/IPv4AddressHelper.Common.cs

Finally, RFC 7541 - HPACK: Header Compression for HTTP/2, is covered in aspnet/AspNetCore/src/Servers/Kestrel/Core/src/Internal/Http2/HPack/HPackDecoder.cs

// http://httpwg.org/specs/rfc7541.html#rfc.section.6.1
//   0   1   2   3   4   5   6   7
// +---+---+---+---+---+---+---+---+
// | 1 |        Index (7+)         |
// +---+---------------------------+
private const byte IndexedHeaderFieldMask = 0x80;
private const byte IndexedHeaderFieldRepresentation = 0x80;

// http://httpwg.org/specs/rfc7541.html#rfc.section.6.2.1
//   0   1   2   3   4   5   6   7
// +---+---+---+---+---+---+---+---+
// | 0 | 1 |      Index (6+)       |
// +---+---+-----------------------+
private const byte LiteralHeaderFieldWithIncrementalIndexingMask = 0xc0;
private const byte LiteralHeaderFieldWithIncrementalIndexingRepresentation = 0x40;

// http://httpwg.org/specs/rfc7541.html#rfc.section.6.2.2
//   0   1   2   3   4   5   6   7
// +---+---+---+---+---+---+---+---+
// | 0 | 0 | 0 | 0 |  Index (4+)   |
// +---+---+-----------------------+
private const byte LiteralHeaderFieldWithoutIndexingMask = 0xf0;
private const byte LiteralHeaderFieldWithoutIndexingRepresentation = 0x00;

// http://httpwg.org/specs/rfc7541.html#rfc.section.6.2.3
//   0   1   2   3   4   5   6   7
// +---+---+---+---+---+---+---+---+
// | 0 | 0 | 0 | 1 |  Index (4+)   |
// +---+---+-----------------------+
private const byte LiteralHeaderFieldNeverIndexedMask = 0xf0;
private const byte LiteralHeaderFieldNeverIndexedRepresentation = 0x10;

// http://httpwg.org/specs/rfc7541.html#rfc.section.6.3
//   0   1   2   3   4   5   6   7
// +---+---+---+---+---+---+---+---+
// | 0 | 0 | 1 |   Max size (5+)   |
// +---+---------------------------+
private const byte DynamicTableSizeUpdateMask = 0xe0;
private const byte DynamicTableSizeUpdateRepresentation = 0x20;

// http://httpwg.org/specs/rfc7541.html#rfc.section.5.2
//   0   1   2   3   4   5   6   7
// +---+---+---+---+---+---+---+---+
// | H |    String Length (7+)     |
// +---+---------------------------+
private const byte HuffmanMask = 0x80;

Dates & Times

It is pretty widely accepted that dates and times are hard and that's reflected in the amount of comments explaining different scenarios. For example from corefx/src/Common/src/CoreLib/System/TimeZoneInfo.cs

// startTime and endTime represent the period from either the start of DST to the end and
// ***does not include*** the potentially overlapped times
//
//         -=-=-=-=-=- Pacific Standard Time -=-=-=-=-=-=-
//    April 2, 2006                            October 29, 2006
// 2AM            3AM                        1AM              2AM
// |      +1 hr     |                        |       -1 hr      |
// | <invalid time> |                        | <ambiguous time> |
//                  [========== DST ========>)
//
//        -=-=-=-=-=- Some Weird Time Zone -=-=-=-=-=-=-
//    April 2, 2006                          October 29, 2006
// 1AM              2AM                    2AM              3AM
// |      -1 hr       |                      |       +1 hr      |
// | <ambiguous time> |                      |  <invalid time>  |
//                    [======== DST ========>)
//

Also, from corefx/src/Common/src/CoreLib/System/TimeZoneInfo.Unix.cs we see some details on how 'leap-years' are handled:

// should be n Julian day format which we don't support. 
// 
// This specifies the Julian day, with n between 0 and 365. February 29 is counted in leap years.
//
// n would be a relative number from the begining of the year. which should handle if the 
// the year is a leap year or not.
// 
// In leap year, n would be counted as:
// 
// 0                30 31              59 60              90      335            365
// |-------Jan--------|-------Feb--------|-------Mar--------|....|-------Dec--------|
//
// while in non leap year we'll have 
// 
// 0                30 31              58 59              89      334            364
// |-------Jan--------|-------Feb--------|-------Mar--------|....|-------Dec--------|
//
// 
// For example if n is specified as 60, this means in leap year the rule will start at Mar 1,
// while in non leap year the rule will start at Mar 2.
// 
// If we need to support n format, we'll have to have a floating adjustment rule support this case.

Finally, this comment from corefx/src/System.Runtime/tests/System/TimeZoneInfoTests.cs discusses invalid and ambiguous times that are covered in tests:

//    March 26, 2006                            October 29, 2006
// 2AM            3AM                        2AM              3AM
// |      +1 hr     |                        |       -1 hr      |
// | <invalid time> |                        | <ambiguous time> |
//                  *========== DST ========>*

//
// * 00:59:59 Sunday March 26, 2006 in Universal converts to
//   01:59:59 Sunday March 26, 2006 in Europe/Amsterdam (NO DST)
//
// * 01:00:00 Sunday March 26, 2006 in Universal converts to
//   03:00:00 Sunday March 26, 2006 in Europe/Amsterdam (DST)
//

Stack Layouts

To finish off, I wanted to look at 'stack layouts' because they seem to be a favourite of the .NET/Mono Runtime Engineers, there's sooo many examples!

First-up, x68 from coreclr/src/jit/lclvars.cpp (you can also see the x64, ARM and ARM64 versions).

 *  The frame is laid out as follows for x86:
 *
 *              ESP frames                
 *
 *      |                       |         
 *      |-----------------------|         
 *      |       incoming        |         
 *      |       arguments       |         
 *      |-----------------------| <---- Virtual '0'         
 *      |    return address     |         
 *      +=======================+
 *      |Callee saved registers |         
 *      |-----------------------|         
 *      |       Temps           |         
 *      |-----------------------|         
 *      |       Variables       |         
 *      |-----------------------| <---- Ambient ESP
 *      |   Arguments for the   |         
 *      ~    next function      ~ 
 *      |                       |         
 *      |       |               |         
 *      |       | Stack grows   |         
 *              | downward                
 *              V                         
 *
 *
 *              EBP frames
 *
 *      |                       |
 *      |-----------------------|
 *      |       incoming        |
 *      |       arguments       |
 *      |-----------------------| <---- Virtual '0'         
 *      |    return address     |         
 *      +=======================+
 *      |    incoming EBP       |
 *      |-----------------------| <---- EBP
 *      |Callee saved registers |         
 *      |-----------------------|         
 *      |   security object     |
 *      |-----------------------|
 *      |     ParamTypeArg      |
 *      |-----------------------|
 *      |  Last-executed-filter |
 *      |-----------------------|
 *      |                       |
 *      ~      Shadow SPs       ~
 *      |                       |
 *      |-----------------------|
 *      |                       |
 *      ~      Variables        ~
 *      |                       |
 *      ~-----------------------|
 *      |       Temps           |
 *      |-----------------------|
 *      |       localloc        |
 *      |-----------------------| <---- Ambient ESP
 *      |   Arguments for the   |
 *      |    next function      ~
 *      |                       |
 *      |       |               |
 *      |       | Stack grows   |
 *              | downward
 *              V
 *

Not to be left out, Mono has some nice examples covering MIPS (below), PPC and ARM

/*
 * Stack frame layout:
 * 
 *   ------------------- sp + cfg->stack_usage + cfg->param_area
 *      param area      incoming
 *   ------------------- sp + cfg->stack_usage + MIPS_STACK_PARAM_OFFSET
 *      a0-a3           incoming
 *   ------------------- sp + cfg->stack_usage
 *  ra
 *   ------------------- sp + cfg->stack_usage-4
 *      spilled regs
 *   ------------------- sp + 
 *      MonoLMF structure   optional
 *   ------------------- sp + cfg->arch.lmf_offset
 *      saved registers     s0-s8
 *   ------------------- sp + cfg->arch.iregs_offset
 *      locals
 *   ------------------- sp + cfg->param_area
 *      param area      outgoing
 *   ------------------- sp + MIPS_STACK_PARAM_OFFSET
 *      a0-a3           outgoing
 *   ------------------- sp
 *      red zone
 */

Finally, there's another example covering [DLLImport] callbacks and one more involving funclet frames in ARM64, I told you there were lots!!

The Rest

If you aren't sick of 'ASCII Art' by now, here's a few more examples for you to look at!!

How does .NET JIT a method? (also featuring 'Tiered Compilation')

Matt Warren — Sat, 16 Dec 2017 09:40:57 +0000

The .NET runtime (CLR) has predominantly used a just-in-time (JIT) compiler to convert your executable into machine code (leaving aside ahead-of-time (AOT) scenarios for the time being), as the official Microsoft docs say:

At execution time, a just-in-time (JIT) compiler translates the MSIL into native code. During this compilation, code must pass a verification process that examines the MSIL and metadata to find out whether the code can be determined to be type safe.

But how does that process actually work?

The same docs give us a bit more info:

JIT compilation takes into account the possibility that some code might never be called during execution. Instead of using time and memory to convert all the MSIL in a PE file to native code, it converts the MSIL as needed during execution and stores the resulting native code in memory so that it is accessible for subsequent calls in the context of that process. The loader creates and attaches a stub to each method in a type when the type is loaded and initialized. When a method is called for the first time, the stub passes control to the JIT compiler, which converts the MSIL for that method into native code and modifies the stub to point directly to the generated native code. Therefore, subsequent calls to the JIT-compiled method go directly to the native code.

Simple really!! However if you want to know more, the rest of this post will explore this process in detail.

In addition, we will look at a new feature that is making its way into the Core CLR, called 'Tiered Compilation'. This is a big change for the CLR, up till now .NET methods have only been JIT compiled once, on their first usage. Tiered compilation is looking to change that, allowing methods to be re-compiled into a more optimised version much like the Java Hotspot compiler.

How it works

But before we look at future plans, how does the current CLR allow the JIT to transform a method from IL to native code? Well, they say 'a pictures speaks a thousand words'

Before the method is JITed

After the method has been JITed

The main things to note are:

The CLR has put in a 'precode' and 'stub' to divert the initial method call to the PreStubWorker() method (which ultimately calls the JIT). These are hand-written assembly code fragments consisting of only a few instructions.
Once the method had been JITed into 'native code', a stable entry point it created. For the rest of the life-time of the method the CLR guarantees that this won't change, so the rest of the run-time can depend on it remaining stable.
The 'temporary entry point' doesn't go away, it's still available because there may be other methods that are expecting to call it. However the associated 'precode fixup' has been re-written or 'back patched' to point to the newly created 'native code' instead of PreStubWorker().
The CLR doesn't change the address of the call instruction in the method that called the method being JITted, it only changes the address inside the 'precode'. But because all method calls in the CLR go via a precode, the 2nd time the newly JITed method is called, the call will end up at the 'native code'.

For reference, the 'stable entry point' is the same memory location as the IntPtr that is returned when you call the RuntimeMethodHandle.GetFunctionPointer() method.

If you want to see this process in action for yourself, you can either re-compile the CoreCLR source and add the relevant debug information as I did or just use WinDbg and follow the steps in this excellent blog post.

Finally, the different parts of the Core CLR source code that are involved are listed below:

Note: this post isn't going to look at how the JIT itself works, if you are interested in that take a look as this excellent overview written by one of the main developers.

JIT and Execution Engine (EE) Interaction

The make all this work the JIT and the EE have to work together, to get an idea of what is involved, take a look at this comment describing the rules that determine which type of precode the JIT can use. All this info is stored in the EE as it's the only place that has the full knowledge of what a method does, so the JIT has to ask which mode to work in.

In addition, the JIT has to ask the EE what the address of a functions entry point is, this is done via the following methods:

Precode and Stubs

There are different types or 'precode' available, 'FIXUP', 'REMOTING' or 'STUB', you can see the rules for which one is used in MethodDesc::GetPrecodeType(). In addition, because they are such a low-level mechanism, they are implemented differently across CPU architectures, from a comment in the code:

There two implementation options for temporary entrypoints:

(1) Compact entrypoints. They provide as dense entrypoints as possible, but can't be patched to point to the final code. The call to unjitted method is indirect call via slot.

(2) Precodes. The precode will be patched to point to the final code eventually, thus the temporary entrypoint can be embedded in the code.
The call to unjitted method is direct call to direct jump.

We use (1) for x86 and (2) for 64-bit to get the best performance on each platform. For ARM (1) is used.

There's also a whole lot more information about 'precode' available in the BOTR.

Finally, it turns out that you can't go very far into the internals of the CLR without coming across 'stubs' (or 'trampolines', 'thunks', etc), for instance they're used in

Tiered Compilation

Before we go any further I want to point out that Tiered Compilation is very much work-in-progress. As an indication, to get it working you currently have to set an environment variable called COMPLUS_EXPERIMENTAL_TieredCompilation. It appears that the current work is focussed on the infrastructure to make it possible (i.e. CLR changes), then I assume that there has to be a fair amount of testing and performance analysis before it's enabled by default.

If you want to learn about the goals of the feature and how it fits into the wider process of 'code versioning', I recommend reading the excellent design docs, including the future roadmap possibilities.

To give an indications of what has been involved so far, there has been work going on in the:

Debugger (e.g. Breakpoints aren't hit if tiered jitting recompiled the method before the debugger was attached and Source line breakpoints stop working when tiered jitting replaces the code)
Profiling APIs - e.g. Tiered jitting: Implement additional profiler APIs
Diagnostics - (all tracked via Tiered jitting: Design/Implement appropriate diagnostics, e.g. Tiered Jitting: Fix IL to native mapping for ETW)
Interpreter - yes the CLR has a built-in Interpreter
Many other places

If you want to follow along you can take a look at the related issues/PRs, here are the main ones to get you started:

Tiered Compilation step 1
WIP - Tiered Jitting Part Deux
All PRs by Noah Falk (main Microsoft Developer working on the feature)

There is also some nice background information available in Introduce a tiered JIT and if you want to understand how it will eventually makes use of changes in the JIT ('MinOpts'), take a look at Low Tier Back-Off and JIT: enable aggressive inline policy for Tier1.

History - ReJIT

As an quick historical aside, you have previously been able to get the CLR to re-JIT a method for you, but it only worked with the Profiling APIs, which meant you had to write some C/C++ COM code to make it happen! In addition ReJIT only allowed the method to be re-compiled at the same level, so it wouldn't ever produce more optimised code. It was mostly meant to help monitoring or profiling tools.

How it works

Finally, how does it work, again lets look at some diagrams. Firstly, as a recap, lets take a look at how things ends up once a method had been JITed, with tiered compilation turned off (the same diagram as above):

Now, as a comparison, here's what the same stage looks like with tiered compilation enabled:

The main difference is that tiered compilation has forced the method call to go through another level of indirection, the 'pre stub'. This is to make it possible to count the number of times the method is called, then once it has hit the threshold (currently 30), the 'pre stub' is re-written to point to the 'optimised native code' instead:

Note that the original 'native code' is still available, so if needed the changes can be reverted and the method call can go back to the unoptimised version.

Using a counter

We can see a bit more details about the counter in this comments from prestub.cpp:

    /***************************   CALL COUNTER    ***********************/
    // If we are counting calls for tiered compilation, leave the prestub
    // in place so that we can continue intercepting method invocations.
    // When the TieredCompilationManager has received enough call notifications
    // for this method only then do we back-patch it.
    BOOL fCanBackpatchPrestub = TRUE;
#ifdef FEATURE_TIERED_COMPILATION
    BOOL fEligibleForTieredCompilation = IsEligibleForTieredCompilation();
    if (fEligibleForTieredCompilation)
    {
        CallCounter * pCallCounter = GetCallCounter();
        fCanBackpatchPrestub = pCallCounter->OnMethodCalled(this);
    }
#endif

In essence the 'stub' calls back into the TieredCompilationManager until the 'tiered compilation' is triggered, once that happens the 'stub' is 'back-patched' to stop it being called any more.

Why not 'Interpreted'?

If you're wondering why tiered compilation doesn't have an interpreted mode, you're not alone, I asked the same question (for more info see my previous post on the .NET Interpreter)

And the answer I got was:

There's already an Interpreter available, or is it not considered suitable for production code?

Its a fine question, but you guessed correctly - the interpreter is not in good enough shape to run production code as-is. There are also some significant issues if you want debugging and profiling tools to work (which we do). Given enough time and effort it is all solvable, it just isn't the easiest place to start.

How different is the overhead between non-optimised and optimised JITting?

On my machine non-optimized jitting used about ~65% of the time that optimized jitting took for similar IL input sizes, but of course I expect results will vary by workload and hardware. Getting this first step checked in should make it easier to collect better measurements.

But that's from a few months ago, maybe Mono's New .NET Interpreter will change things, who knows?

Why not LLVM?

Finally, why aren't they using a LLVM to compile the code, from Introduce a tiered JIT (comment)

There were (and likely still are) significant differences in the LLVM support needed for the CLR versus what is needed for Java, both in GC and in EH, and in the restrictions one must place on the optimizer. To cite just one example: the CLRs GC currently cannot tolerate managed pointers that point off the end of objects. Java handles this via a base/derived paired reporting mechanism. We'd either need to plumb support for this kind of paired reporting into the CLR or restrict LLVM's optimizer passes to never create these kinds of pointers. On top of that, the LLILC jit was slow and we weren't sure ultimately what kind of code quality it might produce.

So, figuring out how LLILC might fit into a potential multi-tier approach that did not yet exist seemed (and still seems) premature. The idea for
now is to get tiering into the framework and use RyuJit for the second-tier jit. As we learn more, we may discover there is indeed room for higher tier jits, or, at least, understand better what else we need to do before such things make sense.

There is more background info in Introduce a tiered JIT

Summary

One of my favourite side-effects of Microsoft making .NET Open Source and developing out in the open is that we can follow along with work-in-progress features. It's great being able to download the latest code, try them out and see how they work under-the-hood, yay for OSS!!

Exploring the BBC micro:bit software stack and OS

Matt Warren — Thu, 30 Nov 2017 10:19:09 +0000

This post first appeared on my blog

If you grew up in the UK and went to school during the 1980's or 1990's there's a good chance that this picture brings back fond memories:

(image courtesy of Classic Acorn)

I'd imagine that for a large amount of computer programmers (currently in their 30's) the BBC Micro was their first experience of programming. If this applies to you and you want a trip down memory lane, have a read of Remembering: The BBC Micro and The BBC Micro in my education.

Programming the classic Turtle was done in Logo, with code like this:

FORWARD 100
LEFT 90
FORWARD 100
LEFT 90
FORWARD 100
LEFT 90
FORWARD 100
LEFT 90

Of course, once you knew what you were doing, you would re-write it like so:

REPEAT 4 [FORWARD 100 LEFT 90]

BBC micro:bit

The original Micro was launched as an education tool, as part of the BBC’s Computer Literacy Project and by most accounts was a big success. As a follow-up, in March 2016 the micro:bit was launched as part of the BBC's 'Make it Digital' initiative and 1 million devices were given out to schools and libraries in the UK to 'help develop a new generation of digital pioneers' (i.e. get them into programming!)

Aside: I love the difference in branding across 30 years, 'BBC Micro' became 'BBC micro:bit' (you must include the colon) and 'Computer Literacy Project' changed to the 'Make it Digital Initiative'.

A few weeks ago I walked into my local library, picked up a nice starter kit and then spent a fun few hours watching my son play around with it (I'm worried about how quickly he picked up the basics of programming, I think I might be out of a job in a few years time!!)

However once he'd gone to bed it was all mine! The result of my 'playing around' is this post, in it I will be exploring the software stack that makes up the micro:bit, what's in it, what it does and how it all fits together.

If you want to learn about how to program the micro:bit, its hardware or anything else, take a look at this excellent list of resources.

Slightly off-topic, but if you enjoy reading source code you might like these other posts:

BBC micro:bit Software Stack

If we take a high-level view at the stack, it divides up into 3 discrete software components that all sit on top of the hardware itself:

If you would like to build this stack for yourself take a look at the Building with Yotta guide. I also found this post describing The First Video Game on the BBC micro:bit [probably] very helpful.

Runtimes

There are several high-level runtimes available, these are useful because they let you write code in a language other than C/C++ or even create programs by dragging blocks around on a screen. The main ones that I've come across are below (see 'Programming' for a full list):

Python via MicroPython
JavaScript with Microsoft Programming Experience Toolkit (PXT)
- well actually it's TypeScript, which is good, we wouldn't want to rot the brains of impressionable young children with the horrors of Javascript - Wat!!

They both work in a similar way, the users code (Python or TypeScript) is bundled up along with the C/C++ code of the runtime itself and then the entire binary (hex) file is deployed to the micro:bit. When the device starts up, the runtime then looks for the users code at a known location in memory and starts interpreting it.

Update It turns out that I was wrong about the Microsoft PXT, it actually compiles your TypeScript program to native code, very cool! Interestingly, they did it that way because:

Compared to a typical dynamic JavaScript engine, PXT compiles code statically, giving rise to significant time and space performance improvements:

user programs are compiled directly to machine code, and are never in any byte-code form that needs to be interpreted; this results in much faster execution than a typical JS interpreter

there is no RAM overhead for user-code - all code sits in flash; in a dynamic VM there are usually some data-structures representing code

due to lack of boxing for small integers and static class layout the memory consumption for objects is around half the one you get in a dynamic VM (not counting the user-code structures mentioned above)

while there is some runtime support code in PXT, it’s typically around 100KB smaller than a dynamic VM, bringing down flash consumption and leaving more space for user code

The execution time, RAM and flash consumption of PXT code is as a rule of thumb 2x of compiled C code, making it competitive to write drivers and other user-space libraries.

Memory Layout

Just before we go onto the other parts of the software stack I want to take a deeper look at the memory layout. This is important because memory is so constrained on the micro:bit, there is only 16KB of RAM. To put that into perspective, we'll use the calculation from this StackOverflow question How many bytes of memory is a tweet?

Twitter uses UTF-8 encoded messages. UTF-8 code points can be up to six four octets long, making the maximum message size 140 x 4 = 560 8-bit bytes.

If we re-calculate for the newer, longer tweets 280 x 4 = 1,120 bytes. So we could only fit 10 tweets into the available RAM on the micro:bit (it turns out that only ~11K out of the total 16K is available for general use). Which is why it's worth using a custom version of atoi() to save 350 bytes of RAM!

The memory layout is specified by the linker at compile-time using NRF51822.ld, there is a sample output available if you want to take a look. Because it's done at compile-time you run into build errors such as "region RAM overflowed with stack" if you configure it incorrectly.

The table below shows the memory layout from the 'no SD' version of a 'Hello World' app, i.e. with the maximum amount of RAM available as the Bluetooth (BLE) Soft-Device (SD) support has been removed. By comparison with BLE enabled, you instantly have 8K less RAM available, so things start to get tight!

Name	Start Address	End Address	Size	Percentage
.data	0x20000000	0x20000098	152 bytes	0.93%
.bss	0x20000098	0x20000338	672 bytes	4.10%
Heap (mbed)	0x20000338	0x20000b38	2,048 bytes	12.50%
Empty	0x20000b38	0x20003800	11,464 bytes	69.97%
Stack	0x20003800	0x20004000	2,048 bytes	12.50%

For more info on the column names see the Wikipedia pages for .data and .bss as well as text, data and bss: Code and Data Size Explained

As a comparison there is a nice image of the micro:bit RAM Layout in this article. It shows what things look like when running MicroPython and you can clearly see the main Python heap in the centre taking up all the remaining space.

microbit-dal

Sitting in the stack below the high-level runtime is the device abstraction layer (DAL), created at Lancaster University in the UK, it's made up of 4 main components:

core
- High-level components, such as Device, Font, HeapAllocator, Listener and Fiber, often implemented on-top of 1 or more driver classes
types
- Helper types such as ManagedString, Image, Event and PacketBuffer
drivers
- For control of a specific hardware component, such as Accelerometer, Button, Compass, Display, Flash, IO, Serial and Pin
bluetooth
- All the code for the Bluetooth Low Energy (BLE) stack that is shipped with the micro:bit
asm
- Just 4 functions are implemented in assembly, they are swap_context, save_context, save_register_context and restore_register_context. As the names suggest, they handle the 'context switching' necessary to make the MicroBit Fiber scheduler work

The image below shows the distribution of 'Lines of Code' (LOC), as you can see the majority of the code is in the drivers and bluetooth components.

In addition to providing nice helper classes for working with the underlying devices, the DAL provides the Fiber abstraction to allows asynchronous functions to work. This is useful because you can asynchronously display text on the LED display and your code won't block whilst it's scrolling across the screen. In addition the Fiber class is used to handle the interrupts that signal when the buttons on the micro:bit are pushed. This comment from the code clearly lays out what the Fiber scheduler does:

This lightweight, non-preemptive scheduler provides a simple threading mechanism for two main purposes:

1) To provide a clean abstraction for application languages to use when building async behaviour (callbacks).
2) To provide ISR decoupling for EventModel events generated in an ISR context.

Finally the high-level classes MicroBit.cpp and MicroBit.h are housed in the microbit repository. These classes define the API of the MicroBit runtime and setup the default configuration, as shown in the Constructor of MicroBit.cpp:

/**
  * Constructor.
  *
  * Create a representation of a MicroBit device, which includes member variables
  * that represent various device drivers used to control aspects of the micro:bit.
  */
MicroBit::MicroBit() :
    serial(USBTX, USBRX),
    resetButton(MICROBIT_PIN_BUTTON_RESET),
    storage(),
    i2c(I2C_SDA0, I2C_SCL0),
    messageBus(),
    display(),
    buttonA(MICROBIT_PIN_BUTTON_A, MICROBIT_ID_BUTTON_A),
    buttonB(MICROBIT_PIN_BUTTON_B, MICROBIT_ID_BUTTON_B),
    buttonAB(MICROBIT_ID_BUTTON_A,MICROBIT_ID_BUTTON_B, MICROBIT_ID_BUTTON_AB),
    accelerometer(i2c),
    compass(i2c, accelerometer, storage),
    compassCalibrator(compass, accelerometer, display),
    thermometer(storage),
    io(MICROBIT_ID_IO_P0,MICROBIT_ID_IO_P1,MICROBIT_ID_IO_P2,
       MICROBIT_ID_IO_P3,MICROBIT_ID_IO_P4,MICROBIT_ID_IO_P5,
       MICROBIT_ID_IO_P6,MICROBIT_ID_IO_P7,MICROBIT_ID_IO_P8,
       MICROBIT_ID_IO_P9,MICROBIT_ID_IO_P10,MICROBIT_ID_IO_P11,
       MICROBIT_ID_IO_P12,MICROBIT_ID_IO_P13,MICROBIT_ID_IO_P14,
       MICROBIT_ID_IO_P15,MICROBIT_ID_IO_P16,MICROBIT_ID_IO_P19,
       MICROBIT_ID_IO_P20),
    bleManager(storage),
    radio(),
    ble(NULL)
{
...
}

mbed-classic

The software at the bottom of the stack is making use of the ARM mbed OS which is:

.. an open-source embedded operating system designed for the "things" in the Internet of Things (IoT). mbed OS includes the features you need to develop a connected product using an ARM Cortex-M microcontroller.

mbed OS provides a platform that includes:

Security foundations.

Cloud management services.

Drivers for sensors, I/O devices and connectivity.

mbed OS is modular, configurable software that you can customize it to your device and to reduce memory requirements by excluding unused software.

We can see this from the layout of it's source, it's based around common components, which can be combined with a hal (Hardware Abstraction Layers) and a target specific to the hardware you are running on.

More specifically the micro:bit uses the yotta target bbc-microbit-classic-gcc, but it can also use others targets as needed.

For reference, here are the files from the common section of mbed that are used by the micro:bit-dal:

And here are the hardware specific files, targeting the NORDIC - MCU NRF51822:

End-to-end (or top-to-bottom)

Finally, lets look a few examples of how the different components within the stack are used in specific scenarios

Writing to the Display

microbit-dal
- MicroBitDisplay.cpp, handles scrolling, asynchronous updates and other high-level tasks, before handing off to:
- MicroBitFont.cpp
- MicroBitImage.cpp
- MicroBitMatrixMaps.h
mbed-classic
- void port_write(port_t *obj, int value) in port_api.c ('NORDIC NRF51822' version), via a call to void write(int value) in PortOut.h, using info from PinNames.h

Storing files on the Flash memory

microbit-dal
- Provides the high-level abstractions, such as:
- FileSystem
- File
- Flash
mbed-classic
- Allows low-level control of the hardware, such as writing to the flash itself either directly or via the SoftDevice (SD) layer

In addition, this comment from MicroBitStorage.h gives a nice overview of how the file system is implemented on-top of the raw flash storage:

* The first 8 bytes are reserved for the KeyValueStore struct which gives core
* information such as the number of KeyValuePairs in the store, and whether the
* store has been initialised.
*
* After the KeyValueStore struct, KeyValuePairs are arranged contiguously until
* the end of the block used as persistent storage.
*
* |-------8-------|--------48-------|-----|---------48--------|
* | KeyValueStore | KeyValuePair[0] | ... | KeyValuePair[N-1] |
* |---------------|-----------------|-----|-------------------|

Summary

All-in-all the micro:bit is a very nice piece of kit and hopefully will achieve its goal 'to help develop a new generation of digital pioneers'. However, it also has a really nice software stack, one that is easy to understand and find your way around.

Best technology-related, non-fiction books

Matt Warren — Mon, 27 Nov 2017 14:15:33 +0000

It appears that most developers really like reading books, but this is a specific ask.

What are the best, technology-related, non-fiction books you've ever read?

To get things started, here's my Top 5:

The Soul of A New Machine by Tracy Kidder
Where Wizards Stay Up Late: The Origins of the Internet by Katie Hafner and Matthew Lyon
The Cuckoo's Egg by Cliff Stoll
Show Stopper! The Breakneck Race to Create Windows NT and the Next Generation at Microsoft by G. Pascal Zachary
Masters Of Doom: How two guys created an empire and transformed pop culture by David Kushner

What are your favourites?

Punishment Driven Development?

Matt Warren — Fri, 17 Nov 2017 15:34:44 +0000

In a previous job I developed 'Industrial Monitoring Systems', otherwise known as a PC, a Camera and Image Processing Software to analyse products moving down a production line.

If everything was fine the keg of cider, pizza box or carrot would be sent out to a shop, otherwise it would be diverted to the reject pile! The systems looked something like this:

But why Punishment Driven Development, well because when my software stopped working the entire production line would grind to a halt and some poor 'volunteer' would have to stand there and inspect the parts manually, clicking a red or a green button for each one.

(Fun fact: I was once told that allegedly some factory workers would mess with the PC until it broke, hitting the same key 100 times in a row, endlessly restarting it, etc, etc. They did this because whilst the production line was down, they got to go on an extended tea-break 😊)

Needless to say, if things went wrong the 'Head of Production' would soon be on the phone and because they had a support contract, it was my job to answer it and fix the problem.

During the 5 years that I worked this job, I discovered the following:

Most industrial systems are located far away from the office where there is a phone and internet access
People don't like being repeatedly asked 'can you just try this?' if each time it involves a 10 minute walk
All sorts of things can go wrong with software running on a PC mounted to the side of a production line, inside a noisy, dirty factory
If the problem can't be solved over the phone, someone (me), has to drive to the factory and stay till it's fixed

Not surprisingly it is the last lesson that caused me the most problems!! Turns out, most factories are in the middle-of-nowhere. In addition, you have limited access to the machine you're fixing and there's no chance you'll get a nice comfy desk and a chair to sit on.

However, it also forced me to implement reliable and useful diagnostics in my software and make it easy to extract them from the PC. Also I made it possible for the software to update itself from the contents of a USB stick, so no more evenings in a factory for me!!

All in all I learnt:

Having useful diagnostics doesn't happen by accident, you have to design it into your product
Spending time thinking about what information to log pays off (I always assumed that one day I'd be relying on it)
Be nice to the person using your software, so that when you visit their factory, they'll want to help you out
Having a motivation to make your software better really helps, hence Punishment Driven Development

Otherwise you end up being sent to Coventry (literally in my case!!)

What about you, do you have a similar story?

Have you ever learnt a valuable lesson about software development, due to an external motivation?

A DoS Attack against the C# Compiler

Matt Warren — Thu, 09 Nov 2017 10:20:16 +0000

This post first appeared on my blog

Generics in C# are certainly very useful and I find it amazing that we almost didn't get them:

What would the cost of inaction have been? What would the cost of failure have been? No generics in C# 2.0? No LINQ in C# 3.0? No TPL in C# 4.0? No Async in C# 5.0? No F#? Ultimately, an erasure model of generics would have been adopted, as for Java, since the CLR team would never have pursued a in-the-VM generics design without external help.

So a big thanks is due to Don Syme and the rest of the team at Microsoft Research in Cambridge!

But as well as being useful, I also find some usages of generics mind-bending, for instance I'm still not sure what this code actually means or how to explain it in words:

class Blah<T> where T : Blah<T>

As always, reading an Eric Lippert post helps a lot, but even he recommends against using this specific 'circular' pattern.

Recently I spoke at the CORESTART 2.0 conference in Prague, giving a talk on 'Microsoft and Open-Source – A 'Brave New World'. Whilst I was there I met the very knowledgeable Jiri Cincura, who blogs at tabs â†¹ over â£ â£ â£ spaces. He was giving a great talk on 'C# 7.1 and 7.2 features', but also shared with me an excellent code snippet that he called 'Crazy Class':

class Class<A, B, C, D, E, F>
{
    class Inner : Class<Inner, Inner, Inner, Inner, Inner, Inner>
    {
        Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner inner;
    }
}

He said:

this is the class that takes crazy amount of time to compile. You can add more Inner.Inner.Inner... to make it even longer (and also generic parameters).

After a big of digging around I found that someone else had noticed this, see the StackOverflow question Why does field declaration with duplicated nested type in generic class results in huge source code increase? Helpfully the 'accepted answer' explains what is going on:

When you combine these two, the way you have done, something interesting happens. The type Outer<T>.Inner is not the same type as Outer<T>.Inner.Inner. Outer<T>.Inner is a subclass of Outer<Outer<T>.Inner> while Outer<T>.Inner.Inner is a subclass of Outer<Outer<Outer<T>.Inner>.Inner>, which we established before as being different from Outer<T>.Inner. So Outer<T>.Inner.Inner and Outer<T>.Inner are referring to different types.

When generating IL, the compiler always uses fully qualified names for types. You have cleverly found a way to refer to types with names whose lengths that grow at exponential rates. That is why as you increase the generic arity of Outer or add additional levels .Y to the field field in Inner the output IL size and compile time grow so quickly.

Clear? Good!!

You probably have to be Jon Skeet, Eric Lippert or a member of the C# Language Design Team (yay, 'Matt Warren') to really understand what's going on here, but that doesn't stop the rest of us having fun with the code!!

I can't think of any reason why you'd actually want to write code like this, so please don't!! (or at least if you do, don't blame me!!)

For a simple idea of what's actually happening, lets take this code (with only 2 'Levels'):

class Class<A, B, C, D, E, F>
{
    class Inner : Class<Inner, Inner, Inner, Inner, Inner, Inner>
    {
        Inner.Inner inner;
    }
}

The 'decompiled' version actually looks like this:

internal class Class<A, B, C, D, E, F>
{
    private class Inner : Class<Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner>
    {
        private Class<Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner>.Inner inner;
    }
}

Wow, no wonder things go wrong quickly!!

Exponential Growth

Firstly let's check the claim of exponential growth, if you don't remember your Big O notation you can also think of this as O(very, very bad)!!

To test this out, I'm going to compile the code above, but vary the 'level' each time by adding a new .Inner, so 'Level 5' looks like this:

Inner.Inner.Inner.Inner.Inner inner;

'Level 6' like this, and so on

Inner.Inner.Inner.Inner.Inner.Inner inner;

We then get the following results:

Level	Compile Time (secs)	Working set (KB)	Binary Size (Bytes)
5	1.15	54,288	135,680
6	1.22	59,500	788,992
7	2.00	70,728	4,707,840
8	6.43	121,852	28,222,464
9	33.23	405,472	169,310,208
10	202.10	2,141,272	CRASH

If we look at these results in graphical form, it's very obvious what's going on

(the dotted lines are a 'best fit' trend-line and they are exponential)

If I compile the code with dotnet build (version 2.0.0), things go really wrong at 'Level 10' and the compiler throws an error (full stack trace):

System.ArgumentOutOfRangeException: Specified argument was out of the range of valid values.

However your mileage may vary, when I ran the code in Visual Studio 2015 it threw an OutOfMemoryException instead and then promptly restarted itself!! I assume this is because VS is a 32-bit application and it runs out of memory before it can go really wrong!

Profiling the Compiler

Finally, I want to look at just where the compiler is spending all it's time. From the results above we saw that it was taking over 3 minutes to compile a simple program, with a peak memory usage of 2.14 GB, so what was it actually doing??

Well clearly there's lots of Types involved and the Compiler seems happy for you to write this code, so I guess it needs to figure it all out. Once it's done that, it then needs to write all this Type metadata out to a .dll or .exe, which can be 100's of MB in size.

At a high-level the profiling summary produce by VS looks like this (click for full-size image):

However if we take a bit of a close look, we can see the 'hot-path' is inside the SerializeTypeReference(..) method in Compilers/Core/Portable/PEWriter/MetadataWriter.cs

Summary

I'm a bit torn about this, it is clearly an 'abuse' of generics!!

In some ways I think that it shouldn't be fixed, it seems better that the compiler encourages you to not write code like this, rather than making is possible!!

So if it takes 3 mins to compile your code, allocates 2GB of memory and then crashes, take that as a warning!!

DotNetAnywhere: An Alternative .NET Runtime

Matt Warren — Fri, 20 Oct 2017 11:27:01 +0000

This post originally appeared on my blog

Recently I was listening to the excellent DotNetRocks podcast and they had Steven Sanderson (of Knockout.js fame) talking about 'WebAssembly and Blazor'.

In case you haven't heard about it, Blazor is an attempt to bring .NET to the browser, using the magic of WebAssembly. If you want more info, Scott Hanselmen has done a nice write-up of the various .NET/WebAssembly projects.

However, as much as the mention of WebAssembly was pretty cool, what interested me even more how Blazor was using DotNetAnywhere as the underlying .NET runtime. This post will look at what DotNetAnywhere is, what you can do with it and how it compares to the full .NET framework.

DotNetAnywhere

Firstly it's worth pointing out that DotNetAnywhere (DNA) is designed to be a fully compliant .NET runtime, which means that it can run .NET dlls/exes that have been compiled to run against the full framework. On top of that (at least in theory) it supports all the following .NET runtime features, which is a pretty impressive list!

Generics

Garbage collection and finalization

Weak references

Full exception handling - try/catch/finally

PInvoke

Interfaces

Delegates

Events

Nullable types

Single-dimensional arrays

Multi-threading

In addition there is some partial support for Reflection

Very limited read-only reflection

typeof(), .GetType(), Type.Name, Type.Namespace, Type.IsEnum(), <object>.ToString() only

Finally, there are a few features that are currently unsupported:

Attributes

Most reflection

Multi-dimensional arrays

Unsafe code

There are various bugs or missing functionality that might prevent your code running under DotNetAnywhere, however several of these have been fixed since Blazor came along, so it's worth checking against the Blazor version of DotNetAnywhere.

At this point in time the original DotNetAnywhere repo is no longer active (the last sustained activity was in Jan 2012), so it seems that any future development or bugs fixes will likely happen in the Blazor repo. If you have ever fixed something in DotNetAnywhere, consider sending a P.R there, to help the effort.

Update: In addition there are other forks with various bug fixes and enhancements:

Source Code Layout

What I find most impressive about the DotNetAnywhere runtime is that it was developed by one person and is less that 40,000 lines of code!! For a comparison the .NET framework Garbage Collector is almost 37,000 lines on it's own (more info available in my previous post A Hitchhikers Guide to the CoreCLR Source Code).

This makes DotNetAnywhere an ideal learning resource!

Firstly, lets take a look at the Top-10 largest source files, to see where the complexity is:

Native Code - 17,710 lines in total

LOC	File
3,164	JIT_Execute.c
1,778	JIT.c
1,109	PInvoke_CaseCode.h
630	Heap.c
618	MetaData.c
563	MetaDataTables.h
517	Type.c
491	MetaData_Fill.c
467	MetaData_Search.c
452	JIT_OpCodes.h

Managed Code - 28,783 lines in total

LOC	File
2393	corlib/System.Globalization/CalendricalCalculations.cs
2314	corlib/System/NumberFormatter.cs
1582	System.Drawing/System.Drawing/Pens.cs
1443	System.Drawing/System.Drawing/Brushes.cs
1405	System.Core/System.Linq/Enumerable.cs
745	corlib/System/DateTime.cs
693	corlib/System.IO/Path.cs
632	corlib/System.Collections.Generic/Dictionary.cs
598	corlib/System/String.cs
467	corlib/System.Text/StringBuilder.cs

Main areas of functionality

Next, lets look at the key components in DotNetAnywhere as this gives us a really good idea about what you need to implement a .NET compatible runtime. Along the way, we will also see how they differ from the implementation found in Microsoft's .NET Framework.

Reading .NET dlls

The first thing DotNetAnywhere has to do is read/understand/parse the .NET Metadata and Code that's contained in a .dll/.exe. This all takes place in MetaData.c, primarily within the LoadSingleTable(..) function. By adding some debugging code, I was able to get a summary of all the different types of Metadata that are read in from a typical .NET dll, it's quite an interesting list:

MetaData contains     1 Assemblies (MD_TABLE_ASSEMBLY)
MetaData contains     1 Assembly References (MD_TABLE_ASSEMBLYREF)
MetaData contains     0 Module References (MD_TABLE_MODULEREF)

MetaData contains    40 Type References (MD_TABLE_TYPEREF)
MetaData contains    13 Type Definitions (MD_TABLE_TYPEDEF)
MetaData contains    14 Type Specifications (MD_TABLE_TYPESPEC)
MetaData contains     5 Nested Classes (MD_TABLE_NESTEDCLASS)

MetaData contains    11 Field Definitions (MD_TABLE_FIELDDEF)
MetaData contains     0 Field RVA's (MD_TABLE_FIELDRVA)
MetaData contains     2 Propeties (MD_TABLE_PROPERTY)
MetaData contains    59 Member References (MD_TABLE_MEMBERREF)
MetaData contains     2 Constants (MD_TABLE_CONSTANT)

MetaData contains    35 Method Definitions (MD_TABLE_METHODDEF)
MetaData contains     5 Method Specifications (MD_TABLE_METHODSPEC)
MetaData contains     4 Method Semantics (MD_TABLE_PROPERTY)
MetaData contains     0 Method Implementations (MD_TABLE_METHODIMPL)
MetaData contains    22 Parameters (MD_TABLE_PARAM)

MetaData contains     2 Interface Implementations (MD_TABLE_INTERFACEIMPL)
MetaData contains     0 Implementation Maps? (MD_TABLE_IMPLMAP)

MetaData contains     2 Generic Parameters (MD_TABLE_GENERICPARAM)
MetaData contains     1 Generic Parameter Constraints (MD_TABLE_GENERICPARAMCONSTRAINT)

MetaData contains    22 Custom Attributes (MD_TABLE_CUSTOMATTRIBUTE)
MetaData contains     0 Security Info Items? (MD_TABLE_DECLSECURITY)

For more information on the Metadata see Introduction to CLR metadata, Anatomy of a .NET Assembly – PE Headers and the ECMA specification itself.

Executing .NET IL

Another large piece of functionality within DotNetAnywhere is the 'Just-in-Time' Compiler (JIT), i.e. the code that is responsible for executing the IL, this takes place initially in JIT_Execute.c and then JIT.c. The main 'execution loop' is in the JITit(..) function which contains an impressive 1,374 lines of code and over 200 case statements within a single switch!!

Taking a higher level view, the overall process that it goes through looks like this:

Where the .NET IL Op-Codes (CIL_XXX) are defined in CIL_OpCodes.h and the DotNetAnywhere JIT Op-Codes (JIT_XXX) are defined in JIT_OpCodes.h

Interesting enough, the JIT is the only place in DotNetAnywhere that uses assembly code and even then it's only for win32. It is used to allow a 'jump' or a goto to labels in the C source code, so as IL instructions are executed it never actually leaves the JITit(..) function, control is just moved around without having to make a full method call.

#ifdef __GNUC__

#define GET_LABEL(var, label) var = &&label

#define GO_NEXT() goto **(void**)(pCurOp++)

#else
#ifdef WIN32

#define GET_LABEL(var, label) \
    { __asm mov edi, label \
    __asm mov var, edi }

#define GO_NEXT() \
    { __asm mov edi, pCurOp \
    __asm add edi, 4 \
    __asm mov pCurOp, edi \
    __asm jmp DWORD PTR [edi - 4] }

#endif

Differences with the .NET Framework

In the full .NET framework all IL code is turned into machine code by the Just-in-Time Compiler (JIT) before being executed by the CPU.

However as we've already seen, DotNetAnywhere 'interprets' the IL, instruction-by-instruction and even through it's done in a file called JIT.c no machine code is emitted, so the naming seems strange!?

Maybe it's just a difference of perspective, but it's not clear to me at what point you move from 'interpreting' code to 'JITting' it, even after reading the following links I'm not sure!! (can someone enlighten me?)

Garbage Collector

All the code for the DotNetAnywhere Garbage Collector (GC) is contained in Heap.c and is a very readable 600 lines of code. To give you an overview of what it does, here is the list of functions that it exposes:

void Heap_Init();
void Heap_SetRoots(tHeapRoots *pHeapRoots, void *pRoots, U32 sizeInBytes);
void Heap_UnmarkFinalizer(HEAP_PTR heapPtr);
void Heap_GarbageCollect();
U32 Heap_NumCollections();
U32 Heap_GetTotalMemory();

HEAP_PTR Heap_Alloc(tMD_TypeDef *pTypeDef, U32 size);
HEAP_PTR Heap_AllocType(tMD_TypeDef *pTypeDef);
void Heap_MakeUndeletable(HEAP_PTR heapEntry);
void Heap_MakeDeletable(HEAP_PTR heapEntry);

tMD_TypeDef* Heap_GetType(HEAP_PTR heapEntry);

HEAP_PTR Heap_Box(tMD_TypeDef *pType, PTR pMem);
HEAP_PTR Heap_Clone(HEAP_PTR obj);

U32 Heap_SyncTryEnter(HEAP_PTR obj);
U32 Heap_SyncExit(HEAP_PTR obj);

HEAP_PTR Heap_SetWeakRefTarget(HEAP_PTR target, HEAP_PTR weakRef);
HEAP_PTR* Heap_GetWeakRefAddress(HEAP_PTR target);
void Heap_RemovedWeakRefTarget(HEAP_PTR target);

Differences with the .NET Framework

However, like the JIT/Interpreter, the GC has some fundamental differences when compared to the .NET Framework

Conservative Garbage Collection

Firstly DotNetAnywhere implements what is knows as a Conservative GC. In simple terms this means that is does not know (for sure) which areas of memory are actually references/pointers to objects and which are just a random number (that looks like a memory address). In the Microsoft .NET Framework the JIT calculates this information and stores it in the GCInfo structure so the GC can make use of it. But DotNetAnywhere doesn't do this.

Instead, during the Mark phase the GC gets all the available 'roots', but it will consider all memory addresses within an object as 'potential' references (hence it is 'conservative'). It then has to lookup each possible reference, to see if it really points to an 'object reference'. It does this by keeping track of all memory/heap references in a balanced binary search tree (ordered by memory address), which looks something like this:

However, this means that all objects references have to be stored in the binary tree when they are allocated, which adds some overhead to allocation. In addition extra memory is needed, 20 bytes per heap entry. We can see this by looking at the tHeapEntry data structure (all pointers are 4 bytes, U8 = 1 byte and padding is ignored), tHeapEntry *pLink[2] is the extra data that is needed just to enable the binary tree lookup.

struct tHeapEntry_ {
    // Left/right links in the heap binary tree
    tHeapEntry *pLink[2];
    // The 'level' of this node. Leaf nodes have lowest level
    U8 level;
    // Used to mark that this node is still in use.
    // If this is set to 0xff, then this heap entry is undeletable.
    U8 marked;
    // Set to 1 if the Finalizer needs to be run.
    // Set to 2 if this has been added to the Finalizer queue
    // Set to 0 when the Finalizer has been run (or there is no Finalizer in the first place)
    // Only set on types that have a Finalizer
    U8 needToFinalize;

    // unused
    U8 padding;

    // The type in this heap entry
    tMD_TypeDef *pTypeDef;

    // Used for locking sync, and tracking WeakReference that point to this object
    tSync *pSync;

    // The user memory
    U8 memory[0];
};

But why does DotNetAnywhere work like this? Fortunately Chris Bacon the author of DotNetAnywhere explains

Mind you, the whole heap code really needs a rewrite to reduce per-object memory overhead, and to remove the need for the binary tree of allocations. Not really thinking of a generational GC, that would probably add to much code. This was something I vaguely intended to do, but never got around to.
The current heap code was just the simplest thing to get GC working quickly. The very initial implementation did no GC at all. It was beautifully fast, but ran out of memory rather too quickly.

For more info on 'Conservative' and 'Precise' GCs see:

GC only does 'Mark-Sweep', it doesn't Compact

Another area in which the GC behaviour differs is that it doesn't do any Compaction of memory after it's cleaned up, as Steve Sanderson found out when working on Blazor

.. During server-side execution we don't actually need to pin anything, because there's no interop outside .NET. During client-side execution, everything is (in effect) pinned regardless, because DNA's GC only does mark-sweep - it doesn't have any compaction phase.

In addition, when an object is allocated DotNetAnywhere just makes a call to malloc(), see the code that does this is in the Heap_Alloc(..) function. So there is no concept of 'Generations' or 'Segments' that you have in the .NET Framework GC, i.e. no 'Gen 0', 'Gen 1', or 'Large Object Heap'.

Threading Model

Finally, lets take a look at the threading model, which is fundamentally different from the one found in the .NET Framework.

Differences with the .NET Framework

Whilst DotNetAnywhere will happily create new threads and execute them for you, it's only providing the illusion of true multi-threading. In reality it only runs on one thread, but context switches between the different threads that your program creates:

You can see this in action in the code below, (from the Thread_Execute() function), note the call to JIT_Execute(..) with numInst set to 100:

for (;;) {
    U32 minSleepTime = 0xffffffff;
    I32 threadExitValue;

    status = JIT_Execute(pThread, 100);
    switch (status) {
        ....
    }
}

An interesting side-effect is that the threading code in the DotNetAnywhere corlib implementation is really simple. For instance the internal implementation of the Interlocked.CompareExchange() function looks like the following, note the lack of synchronisation that you would normally expect:

tAsyncCall* System_Threading_Interlocked_CompareExchange_Int32(
            PTR pThis_, PTR pParams, PTR pReturnValue) {
    U32 *pLoc = INTERNALCALL_PARAM(0, U32*);
    U32 value = INTERNALCALL_PARAM(4, U32);
    U32 comparand = INTERNALCALL_PARAM(8, U32);

    *(U32*)pReturnValue = *pLoc;
    if (*pLoc == comparand) {
        *pLoc = value;
    }

    return NULL;
}

Benchmarks

As a simple test, I ran some benchmarks from The Computer Language Benchmarks Game - binary-trees, using the simplest C# version

Note: DotNetAnywhere was designed to run on low-memory devices, so it was not meant to have the same performance as the full .NET Framework. Please bear that in mind when looking at the results!!

.NET Framework, 4.6.1 - 0.36 seconds

Invoked=TestApp.exe 15
stretch tree of depth 16         check: 131071
32768    trees of depth 4        check: 1015808
8192     trees of depth 6        check: 1040384
2048     trees of depth 8        check: 1046528
512      trees of depth 10       check: 1048064
128      trees of depth 12       check: 1048448
32       trees of depth 14       check: 1048544
long lived tree of depth 15      check: 65535

Exit code      : 0
Elapsed time   : 0.36
Kernel time    : 0.06 (17.2%)
User time      : 0.16 (43.1%)
page fault #   : 6604
Working set    : 25720 KB
Paged pool     : 187 KB
Non-paged pool : 24 KB
Page file size : 31160 KB

DotNetAnywhere - 54.39 seconds

Invoked=dna TestApp.exe 15
stretch tree of depth 16         check: 131071
32768    trees of depth 4        check: 1015808
8192     trees of depth 6        check: 1040384
2048     trees of depth 8        check: 1046528
512      trees of depth 10       check: 1048064
128      trees of depth 12       check: 1048448
32       trees of depth 14       check: 1048544
long lived tree of depth 15      check: 65535

Total execution time = 54288.33 ms
Total GC time = 36857.03 ms
Exit code      : 0
Elapsed time   : 54.39
Kernel time    : 0.02 (0.0%)
User time      : 54.15 (99.6%)
page fault #   : 5699
Working set    : 15548 KB
Paged pool     : 105 KB
Non-paged pool : 8 KB
Page file size : 13144 KB

So clearly DotNetAnywhere doesn't work as fast in this benchmark (0.36 seconds v 54 seconds). However if we look at other benchmarks from the same site, it performs a lot better. It seems that DotNetAnywhere has a significant overhead when allocating objects (a class), which is less obvious when using structs.

	Benchmark 1 (using `classes`)	Benchmark 2 (using `structs`)
Elapsed Time (secs)	3.1	2.0
GC Collections	96	67
Total GC time (msecs)	983.59	439.73

Finally, I really want to thank Chris Bacon, DotNetAnywhere is a great code base and gives a fantastic insight into what needs to happen for a .NET runtime to work.

Analysing C# code on GitHub with BigQuery

Matt Warren — Fri, 13 Oct 2017 08:50:12 +0000

Just over a year ago Google made all the open source code on GitHub available for querying within BigQuery and as if that wasn't enough you can run a terabyte of queries each month for free!

So in this post I am going to be looking at all the C# source code on GitHub and what we can find out from it. Handily a smaller, C# only, dataset has been made available (in BigQuery you are charged per byte read), called fh-bigquery:github_extracts.contents_net_cs and has

5,885,933 unique '.cs' files
792,166,632 lines of code (LOC)
37.17 GB (37,174,783,891 bytes) of data

Which is a pretty comprehensive set of C# source code!

The rest of this post will attempt to answer the following questions:

Tabs or Spaces?
regions: 'should be banned' or 'okay in some cases'?
'K&R' or 'Allman', where do C# devs like to put their braces?
Do C# developers like writing functional code?

Then moving onto some less controversial C# topics:

Which using statements are most widely used?
What NuGet packages are most often included in a .NET project
How many lines of code (LOC) are in a typical C# file?
What is the most widely thrown Exception?
'async/await all the things' or not?
Do C# developers like using the var keyword?

Before we end up looking at repositories, not just individual C# files:

What is the most popular repository with C# code in it?
Just how many files should you have in a repository?
What are the most popular C# class names?
'Foo.cs', 'Program.cs' or something else, what's the most common file name?

If you want to try the queries for yourself (or find my mistakes), all of them are available in this gist. There's a good chance that my regular expressions miss out some edge-cases, after all Regular Expressions: Now You Have Two Problems!!

Tabs or Spaces?

In the entire data-set there are 5,885,933 files, but here we only include ones that have more than 10 lines starting with a tab or a space

Tabs	Tabs %	Spaces	Spaces %	Total
799,055	17.15%	3,859,528	82.85%	4,658,583

Clearly, C# developers (on GitHub) prefer Spaces over Tabs, let the endless debates continue!! (I think some of this can be explained by the fact that Visual Studio uses 'spaces' by default)

If you want to see how C# compares to other programming languages, take a look at 400,000 GitHub repositories, 1 billion files, 14 terabytes of code: Spaces or Tabs?.

`regions`: 'should be banned' or 'okay in some cases'?

It turns out that there are an impressive 712,498 C# files (out of 5.8 million) that contain at least one #region statement (query used), that's just over 12%. (I'm hoping that a lot of those files have been auto-generated by a tool!)

'K&R' or 'Allman', where do C# devs like to put their braces?

C# developers overwhelmingly prefer putting an opening brace { on it's own line (query used)

separate line	same line	same line (initializer)		total (with brace)	total (all code)
81,306,320 (67%)	40,044,603 (33%)	3,631,947 (2.99%)		121,350,923 (15.32%)	792,166,632

('same line initializers' include code like new { Name = "", .. }, new [] { 1, 2, 3.. })

Do C# developers like writing functional code?

This is slightly unscientific, but I wanted to see how widely the Lambda Operator => is used in C# code (query). Yes, I know, if you want to write functional code on .NET you really should use F#, but C# has become more 'functional' over the years and I wanted to see how much code was taking advantage of that.

Here's the raw percentiles:

Percentile	% of lines using lambdas
10	0.51
25	1.14
50	2.50
75	5.26
90	9.95
95	14.29
99	28.00

So we can say that:

50% of all the C# code on GitHub uses => on 2.44% (or less) of their lines.
10% of all C# files have lambdas on almost 1 in 10 of their lines
5% use => on 1 in 7 lines (14.29%)
1% of files have lambdas on over 1 in 3 lines (28%) of their lines of code, that's pretty impressive!

Which `using` statements are most widely used?

Now on to some a bit more substantial, what are the most widely used using statements in C# code?

The top 10 looks like this (the full results are available):

using statement	count
using System.Collections.Generic;	1,780,646
using System;	1,477,019
using System.Linq;	1,319,830
using System.Text;	902,165
using System.Threading.Tasks;	628,195
using System.Runtime.InteropServices;	431,867
using System.IO;	407,848
using System.Runtime.CompilerServices;	338,686
using System.Collections;	289,867
using System.Reflection;	218,369

However, as was pointed out, the top 5 are included by default when you add a new file in Visual Studio and many people wouldn't remove them. The same applies to 'System.Runtime.InteropServices' and 'System.Runtime.CompilerServices' which are include in 'AssemblyInfo.cs` by default.

So if we adjust the list to take account of this, the top 10 looks like so:

using statement	count
using System.IO;	407,848
using System.Collections;	289,867
using System.Reflection;	218,369
using System.Diagnostics;	201,341
using System.Threading;	179,168
using System.ComponentModel;	160,681
using System.Web;	160,323
using System.Windows.Forms;	137,003
using System.Globalization;	132,113
using System.Drawing;	127,033

Finally, an interesting list is the top 10 using statements that aren't System, Microsoft or Windows namespaces:

using statement	count
using NUnit.Framework;	119,463
using UnityEngine;	117,673
using Xunit;	99,099
using System.Web.Mvc;	87,622
using Newtonsoft.Json;	81,675
using Newtonsoft.Json.Linq;	29,416
using Moq;	23,546
using UnityEngine.UI;	20,355
using UnityEditor;	19,937
using Amazon.Runtime;	18,941

What NuGet packages are most often included in a .NET project?

It turns out that there is also a separate dataset containing all the 'packages.config' files on GitHub, it's called contents_net_packages_config and has 104,808 entries. By querying this we can see that Json.Net is the clear winner!!

package	count
Newtonsoft.Json	45,055
Microsoft.Web.Infrastructure	16,022
Microsoft.AspNet.Razor	15,109
Microsoft.AspNet.WebPages	14,495
Microsoft.AspNet.Mvc	14,236
EntityFramework	14,191
Microsoft.AspNet.WebApi.Client	13,480
Microsoft.AspNet.WebApi.Core	12,210
Microsoft.Net.Http	11,625
jQuery	10,646
Microsoft.Bcl.Build	10,641
Microsoft.Bcl	10,349
NUnit	10,341
Owin	9,681
Microsoft.Owin	9,202
Microsoft.AspNet.WebApi.WebHost	9,007
WebGrease	8,743
Microsoft.AspNet.Web.Optimization	8,721
Microsoft.AspNet.WebApi	8,179

How many lines of code (LOC) are in a typical C# file?

Are C# developers prone to creating huge files that go one for 1000's of lines? Well some are but fortunately it's the minority of us!!

Note the Y-axis is 'lines of code' and is logarithmic, the raw data is available.

Oh dear, Uncle Bob isn't going to be happy, whilst 96% of the files have 509 LOC of less, the other 4% don't!! From Clean Code:

And in case you're wondering, here's the Top 10 longest C# files!!

File	Lines
MarMot/Input/test.marmot.cs	92663
src/CodenameGenerator/WordRepos/LastNamesRepository.cs	88810
cs_inputtest/cs_02_7000.cs	63004
cs_inputtest/cs_02_6000.cs	54004
src/ML NET20/Utility/UserName.cs	52014
MWBS/Dictionary/DefaultWordDictionary.cs	48912
Sources/Accord.Math/Matrix/Matrix.Comparisons1.Generated.cs	48407
UrduProofReader/UrduLibs/Utils.cs	48255
cs_inputtest/cs_02_5000.cs	45004
css/style.cs	44366

What is the most widely thrown `Exception`?

There's a few interesting results in this query, for instance who knew that so many ApplicationExceptions were thrown and NotSupportedException being so high up the list is a bit worrying!!

Exception	count
throw new ArgumentNullException	699,526
throw new ArgumentException	361,616
throw new NotImplementedException	340,361
throw new InvalidOperationException	260,792
throw new ArgumentOutOfRangeException	160,640
throw new NotSupportedException	110,019
throw new HttpResponseException	74,498
throw new ValidationException	35,615
throw new ObjectDisposedException	31,129
throw new ApplicationException	30,849
throw new UnauthorizedException	21,133
throw new FormatException	19,510
throw new SerializationException	17,884
throw new IOException	15,779
throw new IndexOutOfRangeException	14,778
throw new NullReferenceException	12,372
throw new InvalidDataException	12,260
throw new ApiException	11,660
throw new InvalidCastException	10,510

'async/await all the things' or not?

The addition of the async and await keywords to the C# language makes writing asynchronous code much easier:

` csharp
public async Task GetDotNetCountAsync()
{
// Suspends GetDotNetCountAsync() to allow the caller (the web server)
// to accept another request, rather than blocking on this one.
var html = await _httpClient.DownloadStringAsync("http://dotnetfoundation.org");

return Regex.Matches(html, ".NET").Count;

}
`

But how much is it used? Using the query below:

SQL SELECT Count(*) count FROM [fh-bigquery:github_extracts.contents_net_cs] WHERE REGEXP_MATCH(content, r'\sasync\s|\sawait\s')

I found that there are 218,643 files (out of 5,885,933) that have at least one usage of async or await in them.

Do C# developers like using the `var` keyword?

Less that they use async and await, there are 130,590 files that have at least one usage of the var keyword

Just how many files should you have in a repository?

90% of the repositories (that have any C# files) have 95 files or less. 95% have 170 files or less and 99% have 535 files or less.

(again the Y-axis (# files) is logarithmic)

The top 10 largest repositories, by number of C# files are shown below:

Repository	# Files
https://github.com/xen2/mcs	23389
https://github.com/mater06/LEGOChimaOnlineReloaded	14241
https://github.com/Microsoft/referencesource	13051
https://github.com/dotnet/corefx	10652
https://github.com/apo-j/Projects_Working	10185
https://github.com/Microsoft/CodeContracts	9338
https://github.com/drazenzadravec/nequeo	8060
https://github.com/ClearCanvas/ClearCanvas	7946
https://github.com/mwilliamson-firefly/aws-sdk-net	7860
https://github.com/151706061/MacroMedicalSystem	7765

What is the most popular repository with C# code in it?

This time we are going to look at the most popular repositories (based on GitHub 'stars') that contain at least 50 C# files (query used):

repo	stars	files
https://github.com/grpc/grpc	11075	237
https://github.com/dotnet/coreclr	8576	6503
https://github.com/dotnet/roslyn	8422	6351
https://github.com/facebook/yoga	8046	73
https://github.com/bazelbuild/bazel	7123	132
https://github.com/dotnet/corefx	7115	10652
https://github.com/SeleniumHQ/selenium	7024	512
https://github.com/Microsoft/WinObjC	6184	81
https://github.com/qianlifeng/Wox	5674	207
https://github.com/Wox-launcher/Wox	5674	142
https://github.com/ShareX/ShareX	5336	766
https://github.com/Microsoft/Windows-universal-samples	5130	1501
https://github.com/NancyFx/Nancy	3701	957
https://github.com/chocolatey/choco	3432	248
https://github.com/JamesNK/Newtonsoft.Json	3340	650

Interesting that the top spot is a Google Repository! (the C# files in it are sample code for using the GRPC library from .NET)

What are the most popular C# `class` names?

Assuming that I got the regex correct, the most popular C# class names are the following:

Class name	Count
class C	182480
class Program	163462
class Test	50593
class Settings	40841
class Resources	39345
class A	34687
class App	28462
class B	24246
class Startup	18238
class Foo	15198

Yay for Foo, just sneaking into the Top 10!!

'Foo.cs', 'Program.cs' or something else, what's the most common file name?

Finally lets look at the different class names used, as with the using statement they are dominated by the default ones used in the Visual Studio templates:

File	Count
AssemblyInfo.cs	386822
Program.cs	105280
Resources.Designer.cs	40881
Settings.Designer.cs	35392
App.xaml.cs	21928
Global.asax.cs	16133
Startup.cs	14564
HomeController.cs	13574
RouteConfig.cs	11278
MainWindow.xaml.cs	11169

More Information

As always, if you've read this far your present is yet more blog posts to read, enjoy!!

How BigQuery Works (only put in at the end of the blog post)

BigQuery analysis of other Programming Languages

'Lowering' in the C# Compiler (and what happens when you misuse it)

Matt Warren — Fri, 26 May 2017 15:29:59 +0000

Turns out that what I'd always thought of as "Compiler magic" or "Syntactic sugar" is actually known by the technical term 'Lowering' and the C# compiler (a.k.a Roslyn) uses it extensively.

But what is it? Well this quote from So You Want To Write Your Own Language? gives us some idea:

Lowering
One semantic technique that is obvious in hindsight (but took Andrei Alexandrescu to point out to me) is called "lowering." It consists of, internally, rewriting more complex semantic constructs in terms of simpler ones. For example, while loops and foreach loops can be rewritten in terms of for loops. Then, the rest of the code only has to deal with for loops. This turned out to uncover a couple of latent bugs in how while loops were implemented in D, and so was a nice win. It's also used to rewrite scope guard statements in terms of try-finally statements, etc. Every case where this can be found in the semantic processing will be win for the implementation.

-- by Walter Bright (author of the D programming language)

But if you're still not sure what it means, have a read of Eric Lippert's post on the subject, Lowering in language design, which contains this quote:

A common technique along the way though is to have the compiler “lower from high-level language features to low-level language features in the same language.

As an aside, if you like reading about the Roslyn compiler source you may like these other posts that I've written:

What does 'Lowering' look like?

The C# compiler has used lowering for a while, one of the oldest or most recognised examples is when this code:

using System.Collections.Generic;
public class C {
    public IEnumerable<int> M() 
    {
        foreach (var value in new [] { 1, 2, 3, 4, 5 })
        {
            yield return value;
        }
    }
}

is turned into this

public class C
{
    [CompilerGenerated]
    private sealed class <M>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IDisposable, IEnumerator
    {
        private int <>1__state;
        private int <>2__current;
        private int <>l__initialThreadId;
        public C <>4__this;
        private int[] <>s__1;
        private int <>s__2;
        private int <value>5__3;
        int IEnumerator<int>.Current
        {
            [DebuggerHidden]
            get
            {
                return this.<>2__current;
            }
        }
        object IEnumerator.Current
        {
            [DebuggerHidden]
            get
            {
                return this.<>2__current;
            }
        }
        [DebuggerHidden]
        public <M>d__0(int <>1__state)
        {
            this.<>1__state = <>1__state;
            this.<>l__initialThreadId = Environment.CurrentManagedThreadId;
        }
        [DebuggerHidden]
        void IDisposable.Dispose()
        {
        }
        bool IEnumerator.MoveNext()
        {
            int num = this.<>1__state;
            if (num != 0)
            {
                if (num != 1)
                {
                    return false;
                }
                this.<>1__state = -1;
                this.<>s__2++;
            }
            else
            {
                this.<>1__state = -1;
                this.<>s__1 = new int[] { 1, 2, 3, 4, 5 };
                this.<>s__2 = 0;
            }
            if (this.<>s__2 >= this.<>s__1.Length)
            {
                this.<>s__1 = null;
                return false;
            }
            this.<value>5__3 = this.<>s__1[this.<>s__2];
            this.<>2__current = this.<value>5__3;
            this.<>1__state = 1;
            return true;
        }
        [DebuggerHidden]
        void IEnumerator.Reset()
        {
            throw new NotSupportedException();
        }
        [DebuggerHidden]
        IEnumerator<int> IEnumerable<int>.GetEnumerator()
        {
            C.<M>d__0 <M>d__;
            if (this.<>1__state == -2 && this.<>l__initialThreadId == Environment.CurrentManagedThreadId)
            {
                this.<>1__state = 0;
                <M>d__ = this;
            }
            else
            {
                <M>d__ = new C.<M>d__0(0);
                <M>d__.<>4__this = this.<>4__this;
            }
            return <M>d__;
        }
        [DebuggerHidden]
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.System.Collections.Generic.IEnumerable<System.Int32>.GetEnumerator();
        }
    }
    [IteratorStateMachine(typeof(C.<M>d__0))]
    public IEnumerable<int> M()
    {
        C.<M>d__0 expr_07 = new C.<M>d__0(-2);
        expr_07.<>4__this = this;
        return expr_07;
    }
}

Yikes, I'm glad we don't have to write that code ourselves!! There's an entire state-machine in there, built to allow our original code to be halted/resumed each time round the loop (at the 'yield' statement).

The C# compiler and 'Lowering'

But it turns out that the Roslyn compiler does a lot more 'lowering' than you might think. If you take a look at the code under '/src/Compilers/CSharp/Portable/Lowering' (VB.NET equivalent here), you see the following folders:

Which correspond to some C# language features you might be familar with, such as 'lambdas', i.e. x => x.Name > 5, 'iterators' used by yield (above) and the async keyword.

However if we look at bit deeper, under the 'LocalRewriter' folder we can see lots more scenarios that we might never have considered 'lowering', such as:

So a big thank-you is due to all the past and present C# language developers and designers, they did all this work for us. Imagine that C# didn't have all these high-level features, we'd be stuck writing them by hand.

It would be like writing Java :-)

What happens when you misuse it

But of course the real fun part is 'misusing' or outright 'abusing' the compiler. So I set up a little twitter competition just how much 'lowering' could we get the compiler to do for us (i.e the highest ratio of 'input' lines of code to 'output' lines).

It had the following rules (see this gist for more info):

You can have as many lines as you want within method M()
No single line can be longer than 100 chars
To get your score, divide the '# of expanded lines' by the '# of original line(s)'
1. Based on the default output formatting of https://sharplab.io, no re-formatting allowed!!
2. But you can format the intput however you want, i.e. make use of the full 100 chars
Must compile with no warnings on https://sharplab.io (allows C# 7 features)
1. But doesn't have to do anything sensible when run
You cannot modify the code that is already there, i.e. public class C {} and public void M()
1. Cannot just add async to public void M(), that's too easy!!
You can add new using ... declarations, these do not count towards the line count

For instance with the following code (interactive version available on sharplab.io):

using System;
public class C {
    public void M() {
        Func<string> test = () => "blah"?.ToString();
    }
}

This counts as 1 line of original code (only code inside method M() is counted)

This expands to 23 lines (again only lines of code inside the braces ({, }) of class C are counted.

Giving a total score of 23 (23 / 1)

....
public class C
{
    [CompilerGenerated]
    [Serializable]
    private sealed class <>c
    {
        public static readonly C.<>c <>9;
        public static Func<string> <>9__0_0;
        static <>c()
        {
            // Note: this type is marked as 'beforefieldinit'.
            C.<>c.<>9 = new C.<>c();
        }
        internal string <M>b__0_0()
        {
            return "blah";
        }
    }
    public void M()
    {
        if (C.<>c.<>9__0_0 == null)
        {
            C.<>c.<>9__0_0 = new Func<string>(C.<>c.<>9.<M>b__0_0);
        }
    }
}

Results

The first place entry was the following entry from Schabse Laks, which contains 9 lines-of-code inside the M() method:

using System.Linq;
using Y = System.Collections.Generic.IEnumerable<dynamic>;

public class C {
    public void M() {
((Y)null).Select(async x => await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await await
await await await await await await await await await await await await await await await x.x()());
    }
}

this expands to an impressive 7964 lines of code (yep you read that right!!) for a score of 885 (7964 / 9). The main trick he figured out was that adding more lines to the input increased the score, i.e is scales superlinearly. Although it you take things too far the compiler bails out with a pretty impressive error message:

error CS8078: An expression is too long or complex to compile

Here's the Top 6 top results:

Submitter	Entry	Score
Schabse Laks	link	885 (7964 / 9)
Andrey Dyatlov	link	778 (778 / 1)
alrz	link	755 (755 / 1)
Andy Gocke *	link	633 (633 / 1)
Jared Parsons *	link	461 (461 / 1)
Jonathan Chambers	link	384 (384 / 1)

* = member of the Roslyn compiler team (they're not disqualified, but maybe they should have some kind of handicap applied to 'even out' the playing field?)

Honourable mentions

However there were some other entries that whilst they didn't make it into the Top 6, are still worth a mention due to the ingenuity involved:

Uncovering a complier bug, kudos to @a_tessenr
- GitHub bug report and fix in the compiler that was done within a few hours!!
Hitting an internal compiler limit, nice work by @Schabse
The most elegant attempt featuring a Y combinator by @NickPalladinos
Using VB.NET (hint: it didn't end well!!), but still a valiant attempt by @AdamSpeight2008
The most astheticially pleasing entry by @leppie

The post 'Lowering' in the C# Compiler (and what happens when you misuse it) appeared first on my blog mattwarren.org

Arrays and the Common Language Runtime - a Very Special Relationship

Matt Warren — Fri, 19 May 2017 21:12:58 +0000

A while ago I wrote about the 'special relationship' that exists between Strings and the CLR, well it turns out that Arrays and the CLR have an even deeper one, the type of closeness where you hold hands on your first meeting

As an aside, if you like reading about CLR internals you may find these other posts interesting:

Fundamental to the Common Language Runtime (CLR)

Arrays are such a fundamental part of the CLR that they are included in the ECMA specification, to make it clear that the runtime has to implement them:

In addition, there are several IL (Intermediate Language) instructions that specifically deal with arrays:

newarr <etype>
- Create a new array with elements of type etype.
ldelem.ref
- Load the element at index onto the top of the stack as an O. The type of the O is the same as the element type of the array pushed on the CIL stack.
stelem <typeTok>
- Replace array element at index with the value on the stack (also stelem.i, stelem.i1, stelem.i2, stelem.r4 etc)
ldlen
- Push the length (of type native unsigned int) of array on the stack.

This makes sense because arrays are the building blocks of so many other data types, you want them to be available, well defined and efficient in a modern high-level language like C#. Without arrays you can't have lists, dictionaries, queues, stacks, trees, etc, they're all built on-top of arrays which provided low-level access to contiguous pieces of memory in a type-safe way.

Memory and Type Safety

This memory and type-safety is important because without it .NET couldn't be described as a 'managed runtime' and you'd be left having to deal with the types of issues you get when your are writing code in a more low-level language.

More specifically, the CLR provide the following protections when you are using arrays (from the section on Memory and Type Safety in the BOTR 'Intro to the CLR' page):

While a GC is necessary to ensure memory safety, it is not sufficient. The GC will not prevent the program from indexing off the end of an array or accessing a field off the end of an object (possible if you compute the field's address using a base and offset computation). However, if we do prevent these cases, then we can indeed make it impossible for a programmer to create memory-unsafe programs.

While the common intermediate language (CIL) does have operators that can fetch and set arbitrary memory (and thus violate memory safety), it also has the following memory-safe operators and the CLR strongly encourages their use in most programming:

Field-fetch operators (LDFLD, STFLD, LDFLDA) that fetch (read), set and take the address of a field by name.

Array-fetch operators (LDELEM, STELEM, LDELEMA) that fetch, set and take the address of an array element by index. All arrays include a tag specifying their length. This facilitates an automatic bounds check before each access.

Also, from the section on Verifiable Code - Enforcing Memory and Type Safety in the same BOTR page

In practice, the number of run-time checks needed is actually very small. They include the following operations:

Casting a pointer to a base type to be a pointer to a derived type (the opposite direction can be checked statically)

Array bounds checks (just as we saw for memory safety)

Assigning an element in an array of pointers to a new (pointer) value. This particular check is only required because CLR arrays have liberal casting rules (more on that later...)

However you don't get this protection for free, there's a cost to pay:

Note that the need to do these checks places requirements on the runtime. In particular:

All memory in the GC heap must be tagged with its type (so the casting operator can be implemented). This type information must be available at runtime, and it must be rich enough to determine if casts are valid (e.g., the runtime needs to know the inheritance hierarchy). In fact, the first field in every object on the GC heap points to a runtime data structure that represents its type.

All arrays must also have their size (for bounds checking).

Arrays must have complete type information about their element type.

Implementation Details

It turns out that large parts of the internal implementation of arrays is best described as magic, this Stack Overflow comment from Marc Gravell sums it up nicely

Arrays are basically voodoo. Because they pre-date generics, yet must allow on-the-fly type-creation (even in .NET 1.0), they are implemented using tricks, hacks, and sleight of hand.

Yep that's right, arrays were parametrised (i.e. generic) before generics even existed. That means you could create arrays such as int[] and string[], long before you were able to write List<int> or List<string>, which only became possible in .NET 2.0.

Special helper classes

All this magic or sleight of hand is made possible by 2 things:

The CLR breaking all the usual type-safety rules
A special array helper class called SZArrayHelper

But first the why, why were all these tricks needed? From .NET Arrays, IList<T>, Generic Algorithms, and what about STL?:

When we were designing our generic collections classes, one of the things that bothered me was how to write a generic algorithm that would work on both arrays and collections. To drive generic programming, of course we must make arrays and generic collections as seamless as possible. It felt that there should be a simple solution to this problem that meant you shouldn’t have to write the same code twice, once taking an IList<T> and again taking a T[]. The solution that dawned on me was that arrays needed to implement our generic IList. We made arrays in V1 implement the non-generic IList, which was rather simple due to the lack of strong typing with IList and our base class for all arrays (System.Array). What we needed was to do the same thing in a strongly typed way for IList<T>.

But it was only done for the common case, i.e. 'single dimensional' arrays:

There were some restrictions here though – we didn’t want to support multidimensional arrays since IList<T> only provides single dimensional accesses. Also, arrays with non-zero lower bounds are rather strange, and probably wouldn’t mesh well with IList<T>, where most people may iterate from 0 to the return from the Count property on that IList. So, instead of making System.Array implement IList<T>, we made T[] implement IList<T>. Here, T[] means a single dimensional array with 0 as its lower bound (often called an SZArray internally, but I think Brad wanted to promote the term 'vector' publically at one point in time), and the element type is T. So Int32[] implements IList<Int32>, and String[] implements IList<String>.

Also, this comment from the array source code sheds some further light on the reasons:

//----------------------------------------------------------------------------------
// Calls to (IList<T>)(array).Meth are actually implemented by SZArrayHelper.Meth<T>
// This workaround exists for two reasons:
//
//    - For working set reasons, we don't want insert these methods in the array 
//      hierachy in the normal way.
//    - For platform and devtime reasons, we still want to use the C# compiler to 
//      generate the method bodies.
//
// (Though it's questionable whether any devtime was saved.)
//
// ....
//----------------------------------------------------------------------------------

So it was done for convenience and efficiently, as they didn't want every instance of System.Array to carry around all the code for the IEnumerable<T> and IList<T> implementations.

This mapping takes places via a call to GetActualImplementationForArrayGenericIListOrIReadOnlyListMethod(..), which wins the prize for the best method name in the CoreCLR source!! It's responsible for wiring up the corresponding method from the SZArrayHelper class, i.e. IList<T>.Count -> SZArrayHelper.Count<T> or if the method is part of the IEnumerator<T> interface, the SZGenericArrayEnumerator<T> is used.

But this has the potential to cause security holes, as it breaks the normal C# type system guarantees, specifically regarding the this pointer. To illustrate the problem, here's the source code of the Count property, note the call to JitHelpers.UnsafeCast<T[]>:

internal int get_Count<T>()
{
    //! Warning: "this" is an array, not an SZArrayHelper. See comments above
    //! or you may introduce a security hole!
    T[] _this = JitHelpers.UnsafeCast<T[]>(this);
    return _this.Length;
}

Yikes, it has to remap this to be able to call Length on the correct object!!

And just in case those comments aren't enough, there is a very strongly worded comment at the top of the class that further spells out the risks!!

Generally all this magic is hidden from you, but occasionally it leaks out. For instance if you run the code below, SZArrayHelper will show up in the StackTrace and TargetSite of properties of the NotSupportedException:

try {
    int[] someInts = { 1, 2, 3, 4 };
    IList<int> collection = someInts;
    // Throws NotSupportedException 'Collection is read-only'
    collection.Clear();         
} catch (NotSupportedException nsEx) {              
    Console.WriteLine("{0} - {1}", nsEx.TargetSite.DeclaringType, nsEx.TargetSite);
    Console.WriteLine(nsEx.StackTrace);
}

Removing Bounds Checks

The runtime also provides support for arrays in more conventional ways, the first of which is related to performance. Array bounds checks are all well and good when providing memory-safety, but they have a cost, so where possible the JIT removes any checks that it knows are redundant.

It does this by calculating the range of values that a for loop access and compares those to the actual length of the array. If it determines that there is never an attempt to access an item outside the permissible bounds of the array, the run-time checks are then removed.

For more information, the links below take you to the areas of the JIT source code that deal with this:

JIT trying to remove range checks
RangeCheck::OptimizeRangeCheck(..)
- In turn calls RangeCheck::GetRange(..)
- Also call Compiler::optRemoveRangeCheck(..) to actually remove the range-check
Really informative source code comment explaining the range check removal logic

And if you are really keen, take a look at this gist that I put together to explore the scenarios where bounds checks are 'removed' and 'not removed'.

Allocating an array

Another task that the runtime helps with is allocating arrays, using hand-written assembly code so the methods are as optimised as possible, see:

Run-time treats arrays differently

Finally, because arrays are so intertwined with the CLR, there are lots of places in which they are dealt with as a special-case. For instance a search for 'IsArray()' in the CoreCLR source returns over 60 hits, including:

The method table for an array is built differently
- MethodTableBuilder::BuildInteropVTableForArray(..)
When you call ToString() on an array, you get special formatting, i.e. 'System.Int32[]' or 'MyClass[,]'
- TypeString::AppendType(..)

So yes, it's fair to say that arrays and the CLR have a Very Special Relationship

The .NET IL (bytecode) Interpreter

Matt Warren — Fri, 07 Apr 2017 09:09:34 +0000

Whilst writing a previous blog post I stumbled across the .NET Interpreter, tucked away in the source code. Although, if I'd made even the smallest amount of effort to look for it, I'd have easily found it via the GitHub 'magic' file search:

Usage Scenarios

Before we look at how to use it and what it does, it's worth pointing out that the Interpreter is not really meant for production code. As far as I can tell, its main purpose is to allow you to get the CLR up and running on a new CPU architecture. Without the interpreter you wouldn't be able to test any C# code until you had a fully functioning JIT that could emit machine code for you. For instance see '[ARM32/Linux] Initial bring up of FEATURE_INTERPRETER' and '[aarch64] Enable the interpreter on linux as well.

Also it doesn't have a few key features, most notable debugging support, that is you can't debug through C# code that has been interpreted, although you can of course debug the interpreter itself. From 'Tiered Compilation step 1':

.... - the interpreter is not in good enough shape to run production code as-is. There are also some significant issues if you want debugging and profiling tools to work (which we do).

You can see an example of this in 'Interpreter: volatile ldobj appears to have incorrect semantics?' (thanks to alexrp for telling me about this issue). There is also a fair amount of TODO comments in the code, although I haven't verified what (if any) specific C# code breaks due to the missing functionality.

However, I think another really useful scenario for the Interpreter is to help you learn about the inner workings of the CLR. It's only 8,000 lines long, but it's all in one file and most significantly it's written in C++. The code that the CLR/JIT uses when compiling for real is in multiple several files (the JIT on it's own is over 200,000 L.O.C, spread across 100's of files) and there are large amounts hand-written written in raw assembly.

In theory the Interpreter should work in the same way as the full runtime, albeit not as optimised. This means that it much simpler and those of us who aren't CLR and/or assembly experts can have a chance of working out what's going on!

Enabling the Interpreter

The Interpreter is disabled by default, so you have to build the CoreCLR from source to make it work (it used to be the fallback for ARM64 but that's no longer the case), here's the diff of the changes you need to make:

--- a/src/inc/switches.h
+++ b/src/inc/switches.h
@@ -233,5 +233,8 @@
 #define FEATURE_STACK_SAMPLING
 #endif // defined (ALLOW_SXS_JIT)

+// Let's test the .NET Interpreter!!
+#define FEATURE_INTERPRETER
+
 #endif // !defined(CROSSGEN_COMPILE)

You also need to enable some environment variables, the ones that I used are in the table below. For the full list, take a look at Host Configuration Knobs and search for 'Interpreter'.

Name	Description
Interpret	Selectively uses the interpreter to execute the specified methods
InterpreterDoLoopMethods	If set, don't check for loops, start by interpreting all methods
InterpreterPrintPostMortem	Prints summary information about the execution to the console
DumpInterpreterStubs	Prints all interpreter stubs that are created to the console
TraceInterpreterEntries	Logs entries to interpreted methods to the console
TraceInterpreterIL	Logs individual instructions of interpreted methods to the console
TraceInterpreterVerbose	Logs interpreter progress with detailed messages to the console
TraceInterpreterJITTransition	Logs when the interpreter determines a method should be JITted

To test out the Interpreter, I will be using the code below:

public static void Main(string[] args)
{
    var max = 1000 * 1000;
    if (args.Length > 0)
        int.TryParse(args[0], out max);
    var timer = Stopwatch.StartNew();
    for (int i = 1; i <= max; i++)
    {
        if (i % (1000 * 100) == 0)
            Console.WriteLine(string.Format("Completed {0,10:N0} iterations", i));
    }
    timer.Stop();
    Console.WriteLine(string.Format("Performed {0:N0} iterations, max);
    Console.WriteLine(string.Format("Took {0:N0} msecs", timer.ElapsedMilliseconds));
    Console.WriteLine();
}

which on my machine, gives the following results for 100,000 iterations:

Run	Compiled (msecs)	Interpreted (msecs)
1	11	4,393
2	11	4,089
3	9	4,416

So yeah, you don't want to be using the interpreter for any performance sensitive code!!

Diagnostic Output

In addition, a diagnostic output is produced. Note, this is from a single iteration of the loop, otherwise it becomes to verbose to read.

Generating interpretation stub (# 1 = 0x1, hash = 0x91b7d02e) for ConsoleApplication.Program:Main.
Skipping ConsoleApplication.Program:.cctor
Entering method #1 (= 0x1): ConsoleApplication.Program:Main(class).
 arguments:
         0:      class: 0x0000000002C50568 (System.String[]) [...]

START 1, ConsoleApplication.Program:Main(class)
     0: nop
   0x1: call
Skipping ConsoleApplication.Stopwatch:.cctor
Skipping DomainBoundILStubClass:IL_STUB_PInvoke
Skipping ConsoleApplication.Stopwatch:StartNew
Skipping ConsoleApplication.Stopwatch:.ctor
Skipping ConsoleApplication.Stopwatch:Reset
Skipping ConsoleApplication.Stopwatch:Start
Skipping ConsoleApplication.Stopwatch:GetTimestamp
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
   0x6: stloc.0
      loc0   :      class: 0x0000000002C50580 (ConsoleApplication.Stopwatch) [...]
      loc1   :        int: 0
      loc2   :       bool: false
   0x7: ldc.i4.1
   0x8: stloc.1
      loc0   :      class: 0x0000000002C50580 (ConsoleApplication.Stopwatch) [...]
      loc1   :        int: 1
      loc2   :       bool: false
   0x9: br.s
  0x27: ldloc.1
  0x28: ldc.i4.2
  0x29: clt
  0x2b: stloc.2
      loc0   :      class: 0x0000000002C50580 (ConsoleApplication.Stopwatch) [...]
      loc1   :        int: 1
      loc2   :       bool: true
  0x2c: ldloc.2
  0x2d: brtrue.s
   0xb: nop
   0xc: ldstr
  0x11: ldloc.1
  0x12: box
  0x17: call
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
  0x1c: call
Completed          1 iterations
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
  0x21: nop
  0x22: nop
  0x23: ldloc.1
  0x24: ldc.i4.1
  0x25: add
  0x26: stloc.1
      loc0   :      class: 0x0000000002C50580 (ConsoleApplication.Stopwatch) [...]
      loc1   :        int: 2
      loc2   :       bool: true
  0x27: ldloc.1
  0x28: ldc.i4.2
  0x29: clt
  0x2b: stloc.2
      loc0   :      class: 0x0000000002C50580 (ConsoleApplication.Stopwatch) [...]
      loc1   :        int: 2
      loc2   :       bool: false
  0x2c: ldloc.2
  0x2d: brtrue.s
  0x2f: ldloc.0
  0x30: callvirt
Skipping ConsoleApplication.Stopwatch:Stop
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
  0x35: nop
  0x36: ldstr
  0x3b: ldloc.0
  0x3c: callvirt
Skipping ConsoleApplication.Stopwatch:get_ElapsedMilliseconds
Skipping ConsoleApplication.Stopwatch:GetElapsedDateTimeTicks
Skipping ConsoleApplication.Stopwatch:GetRawElapsedTicks
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
  0x41: box
  0x46: call
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
  0x4b: call
Took 33 msecs
  Returning to method ConsoleApplication.Program:Main(class), stub num 1.
  0x50: nop
  0x51: ret

So you can clearly see the interpreter in action, executing the individual IL instructions and showing the current values of any local variables as it goes along. Then, once the entire program has run, you also get some nice summary statistics (this time from a full-run, with 100,000 iterations):

IL instruction profiling:

Instructions (24000085 total, 20000083 1-byte):
Instruction  |   execs   |       % |   cum %
-------------------------------------------
     ldloc.1 |   3000011 |  12.50% |  12.50%
         ceq |   3000001 |  12.50% |  25.00%
    ldc.i4.0 |   3000001 |  12.50% |  37.50%
         nop |   2000013 |   8.33% |  45.83%
     stloc.2 |   2000001 |   8.33% |  54.17%
      ldc.i4 |   2000001 |   8.33% |  62.50%
    brtrue.s |   2000001 |   8.33% |  70.83%
     ldloc.2 |   2000001 |   8.33% |  79.17%
    ldc.i4.1 |   1000001 |   4.17% |  83.33%
         cgt |   1000001 |   4.17% |  87.50%
     stloc.1 |   1000001 |   4.17% |  91.67%
         rem |   1000000 |   4.17% |  95.83%
         add |   1000000 |   4.17% | 100.00%
        call |        23 |   0.00% | 100.00%
       ldstr |        11 |   0.00% | 100.00%
         box |        11 |   0.00% | 100.00%
     ldloc.0 |         2 |   0.00% | 100.00%
    callvirt |         2 |   0.00% | 100.00%
        br.s |         1 |   0.00% | 100.00%
     stloc.0 |         1 |   0.00% | 100.00%
         ret |         1 |   0.00% | 100.00%

Main sections of the Interpreter code

Now we've seen it in action, let's take a look at the code within the Interpreter and see how it works

Top-level dispatcher

At the heart of the Interpreter is a giant switch statement (in Interpreter::ExecuteMethod(..)), that is almost 1,200 lines long! In it you'll find lots of code like this:

switch (*m_ILCodePtr)
{
case CEE_NOP:
    m_ILCodePtr++;
    continue;
case CEE_BREAK:     // TODO: interact with the debugger?
    m_ILCodePtr++;
    continue;
case CEE_LDARG_0:
    LdArg(0);
    break;
case CEE_LDARG_1:
    LdArg(1);
    break;
    ...
}

In total, there are 199 case statements, corresponding to all the available CLR Intermediate Language (IL) op-codes, in all their different combinations, for instance CEE_LDC_??, i.e. CEE_LDC_I4, CEE_LDC_I8, CEE_LDC_R4 and CEE_LDC_R8. The large majority of the case statements just call out to another function that does the actual work, although there are some exceptions, such as CEE_RET.

Method calls

The other task that takes up lots of code in the interpreter is handling method calls, over 2,500 L.O.C in total! This is spread across several methods, each doing a particular part of the work:

void Interpreter::DoCallWork(..)
- CALL Calls the method indicated by the passed method descriptor
- CALLVIRT Calls a late-bound method on an object, pushing the return value onto the evaluation stack.
- Also via Interpreter::NewObj(), i.e the NEWOBJ IL op-code
void Interpreter::CallI()
- CALLI Calls the method indicated on the evaluation stack (as a pointer to an entry point) with arguments described by a calling convention
CorJitResult Interpreter::GenerateInterpreterStub(..)
- The external entry point, i.e. the JIT inserts a stub to this method
- Also called via Interpreter::InterpretMethodBody(..)
- Actually emits assembly code!!
void InterpreterMethodInfo::InitArgInfo(..)
- Called via Interpreter::GenerateInterpreterStub(..)

In summary, this work involves dynamically generating stubs and ensuring that method arguments are in the right registers (hence the assembly code). It handles virtual methods, static and instance calls, delegates, intrinsics and probably a few other scenarios as well! In addition, if the method being called needs to be interpreted, it also has to make sure that happens.

Creating objects and arrays

The interpreter needs to handle some of the key functionality of a runtime, that is creating and initialising objects. To do this it has to call into the GC, before finally calling the constructor:

Boxing and Unboxing

Another large chuck of code is dedicated to boxing/unboxing, that is converting 'value types' (structs) into object references when needed. The .NET IL provides specific op-codes to handle this:

Loading and Storing data

That is, reading/writing fields in an object or elements in an array:

Other Specific IL Op Codes

There is also a significant amount of code (over 1,000 lines) that just deals with low-level operations, that is 'comparisions', 'branching' and 'basic arithmetic':

INT32 Interpreter::CompareOpRes(..)
- CEQ, CGT, CGT_UN, CLT & CLT_UN called via Interpreter::CompareOp()
- BEQ, BGE, BGT, BLE, BLT, BNE_UN, BGE_UN, BGT_UN, BLE_UN, BLT_UN called via Interpreter::BrOnComparison()
void Interpreter::BinaryArithOp()
- ADD, SUB, MUL, DIV and REM
- in turn calls Interpreter::BinaryArithOpWork(..)
void Interpreter::BinaryArithOvfOp()
- ADD_OVF, ADD_OVF_UN, MUL_OVF, MUL_OVF_UN, SUB_OVF, SUB_OVF_UN
- in turn calls Interpreter::BinaryArithOvfOpWork(..)

Working with the Garbage Collector (GC)

In addition, the interpreter has to provide the GC with the information it needs. This happens when the GC calls Interpreter::GCScanRoots(..), with additional work talking place in Interpreter::GCScanRootAtLoc(..). Very simply the interpreter has to let the GC know about any 'root' objects that are currently 'live'. This includes static variables and any local variables in the function that is currently executing.

When the interpreter locates a 'root' object, it notifies the GC via a callback (pf(..)):

void Interpreter::GCScanRootAtLoc(Object** loc, InterpreterType it, promote_func* pf, ScanContext* sc, bool pinningRef)
{
    switch (it.ToCorInfoType())
    {
    case CORINFO_TYPE_CLASS:
    case CORINFO_TYPE_STRING:
        {
            DWORD flags = 0;
            if (pinningRef) flags |= GC_CALL_PINNED;
            (*pf)(loc, sc, flags);
        }
        break;
    ....
    }
}

Integration with the Virtual Machine (VM)

Finally, whilst the Interpreter is fairly self-contained, there are times where it needs to work with the rest of the runtime

The Run-time is responsible for starting and stopping the interpreter
The JIT wires up interpreter stubs or uses them as a fall-back if JIT compilation fails. In addition the JIT 'pre-stubs' allow for interpreted methods when calling the JIT itself and when the 'pre-stub' is executed
Stack-walking takes account of interpreter frames, by utilising InterpreterFrame data structures
When looking up the MethodDesc for a given code address, the interpreter stubs are accounted for

The post 'The .NET IL (bytecode) Interpreter' appeared first on my blog mattwarren.org

How do .NET delegates work?

Matt Warren — Tue, 07 Mar 2017 15:28:24 +0000

Delegates are a fundamental part of the .NET runtime and whilst you rarely create them directly, they are there under-the-hood every time you use a lambda in LINQ (=>) or a Func<T>/Action<T> to make your code more functional. But how do they actually work and what's going in the CLR when you use them?

IL of delegates and/or lambdas


    public delegate string SimpleDelegate(int x);

    class DelegateTest
    {
        static int Main()
        {
            // create an instance of the class
            DelegateTest instance = new DelegateTest();
            instance.name = "My instance";

            // create a delegate
            SimpleDelegate d1 = new SimpleDelegate(instance.InstanceMethod);

            // call 'InstanceMethod' via the delegate (compiler turns this into 'd1.Invoke(5)')
            string result = d1(5); // returns "My instance: 5"
        }

        string InstanceMethod(int i)
        {
            return string.Format("{0}: {1}", name, i);
        }
    }

If you were to take a look at the IL of the SimpleDelegate class, the ctor and Invoke methods look like so:


    [MethodImpl(0, MethodCodeType=MethodCodeType.Runtime)]
    public SimpleDelegate(object @object, IntPtr method);

    [MethodImpl(0, MethodCodeType=MethodCodeType.Runtime)]
    public virtual string Invoke(int x);

It turns out that this behaviour is manadated by the spec, from ECMA 335 Standard - Common Language Infrastructure (CLI):

So the internal implementation of a delegate, the part responsible for calling a method, is created by the runtime. This is because there needs to be complete control over those methods, delegates are a fundamental part of the CLR, any security issues, performance overhead or other inefficiencies would be a big problem.

Methods that are created in this way are technically know as EEImpl methods, from the â€˜Book of the Runtime' (BOTR) section â€˜Method Descriptor - Kinds of MethodDescs:

EEImpl Delegate methods whose implementation is provided by the runtime (Invoke, BeginInvoke, EndInvoke). See ECMA 335 Partition II - Delegates.

There's also more information available in these two excellent articles .NET Type Internals - From a Microsoft CLR Perspective (section on â€˜Delegates') and Understanding .NET Delegates and Events, By Practice (section on â€˜Internal Delegates Representation')

How the runtime creates delegates

Inlining of delegate ctors

So we've seen that the runtime has responsibility for creating the bodies of delegate methods, but how is this done. It starts by wiring up the delegate constructor (ctor), as per the BOTR page on â€˜method descriptors'

FCall Internal methods implemented in unmanaged code. These are methods marked with MethodImplAttribute(MethodImplOptions.InternalCall) attribute, delegate constructors and tlbimp constructors.

At runtime this happens when the JIT compiles a method that contains IL code for creating a delegate. In Compiler::fgOptimizeDelegateConstructor(..), the JIT firstly obtains a reference to the correct delegate ctor, which in the simple case is CtorOpened(Object target, IntPtr methodPtr, IntPtr shuffleThunk) (link to C# code), before finally wiring up the ctor, inlining it if possible for maximum performance.

Creation of the delegate Invoke() method

But what's more interesting is the process that happens when creating the Invoke() method, using a technique involving â€˜stubs' of code (raw-assembly) that know how to locate the information about the target method and can jump control to it. These â€˜stubs' are actually used in a wide-variety of scenarios, for instance during Virtual Method Dispatch and also by the JITter (when a method is first called it hits a â€˜pre-code stub' that causes the method to be JITted, the â€˜stub' is then replaced by a call to the JITted â€˜native code').

In the particular case of delegates, these stubs are referred to as â€˜shuffle thunks'. This is because part of the work they have to do is â€˜shuffle' the arguments that are passed into the Invoke() method, so that are in the correct place (stack/register) by the time the â€˜target' method is called.

To understand what's going on, it's helpful to look at the following diagram taken from the BOTR page on Method Descriptors and Precode stubs. The â€˜shuffle thunks' we are discussing are a particular case of a â€˜stub' and sit in the corresponding box in the diagram:

How â€˜shuffle thunks' are set-up

So let's look at the code flow for the delegate we created in the sample at the beginning of this post, specifically an â€˜open' delegate, calling an instance method (if you are wondering about the difference between open and closed delegates, have a read of â€˜Open Delegates vs. Closed Delegates').

We start off in the impImportCall() method, deep inside the .NET JIT, triggered when a â€˜call' op-code for a delegate is encountered, it then goes through the following functions:

Compiler::impImportCall(..)
Compiler::fgOptimizeDelegateConstructor(..)
COMDelegate::GetDelegateCtor(..)
COMDelegate::SetupShuffleThunk
StubCacheBase::Canonicalize(..)
ShuffleThunkCache::CompileStub()
EmitShuffleThunk (specific assembly code for different CPU architectures)
- arm
- arm64
- i386

Below is the code from the arm64 version (chosen because it's the shortest one of the three!). You can see that it emits assembly code to fetch the real target address from MethodPtrAux, loops through the method arguments and puts them in the correct register (i.e. â€˜shuffles' them into place) and finally emits a tail-call jump to the target method associated with the delegate.


    VOID StubLinkerCPU::EmitShuffleThunk(ShuffleEntry *pShuffleEntryArray)
    {
      // On entry x0 holds the delegate instance. Look up the real target address stored in the MethodPtrAux
      // field and save it in x9\. Tailcall to the target method after re-arranging the arguments
      // ldr x9, [x0, #offsetof(DelegateObject, _methodPtrAux)]
      EmitLoadStoreRegImm(eLOAD, IntReg(9), IntReg(0), DelegateObject::GetOffsetOfMethodPtrAux());
      //add x11, x0, DelegateObject::GetOffsetOfMethodPtrAux() - load the indirection cell into x11 used by ResolveWorkerAsmStub
      EmitAddImm(IntReg(11), IntReg(0), DelegateObject::GetOffsetOfMethodPtrAux());

      for (ShuffleEntry* pEntry = pShuffleEntryArray; pEntry->srcofs != ShuffleEntry::SENTINEL; pEntry++)
      {
        if (pEntry->srcofs & ShuffleEntry::REGMASK)
        {
          // If source is present in register then destination must also be a register
          _ASSERTE(pEntry->dstofs & ShuffleEntry::REGMASK);

          EmitMovReg(IntReg(pEntry->dstofs & ShuffleEntry::OFSMASK), IntReg(pEntry->srcofs & ShuffleEntry::OFSMASK));
        }
        else if (pEntry->dstofs & ShuffleEntry::REGMASK)
        {
          // source must be on the stack
          _ASSERTE(!(pEntry->srcofs & ShuffleEntry::REGMASK));

          EmitLoadStoreRegImm(eLOAD, IntReg(pEntry->dstofs & ShuffleEntry::OFSMASK), RegSp, pEntry->srcofs * sizeof(void*));
        }
        else
        {
          // source must be on the stack
          _ASSERTE(!(pEntry->srcofs & ShuffleEntry::REGMASK));

          // dest must be on the stack
          _ASSERTE(!(pEntry->dstofs & ShuffleEntry::REGMASK));

          EmitLoadStoreRegImm(eLOAD, IntReg(8), RegSp, pEntry->srcofs * sizeof(void*));
          EmitLoadStoreRegImm(eSTORE, IntReg(8), RegSp, pEntry->dstofs * sizeof(void*));
        }
      }

      // Tailcall to target
      // br x9
      EmitJumpRegister(IntReg(9));
    }

Other functions that call `SetupShuffleThunk(..)`

The other places in code that also emit these â€˜shuffle thunks' are listed below. They are used in the various scenarios where a delegate is explicitly created, e.g. via `Delegate.CreateDelegate(..).

COMDelegate::BindToMethod(..) - actual call to SetupShuffleThunk(..)
COMDelegate::DelegateConstruct(..) (ECall impl) - actual call to SetupShuffleThunk(..)
COMDelegate::GetDelegateCtor(..) - actual call to SetupShuffleThunk(..)

Different types of delegates

Now that we've looked at how one type of delegate works (#2 â€˜Instance open non-virt' in the table below), it will be helpful to see the other different types that the runtime deals with. From the very informative DELEGATE KINDS TABLE in the CLR source:

#	delegate type	_target	_methodPtr	_methodPtrAux
1	Instance closed	â€˜this' ptr	target method	null
2	Instance open non-virt	delegate	shuffle thunk	target method
3	Instance open virtual	delegate	Virtual-stub dispatch	method id
4	Static closed	first arg	target method	null
5	Static closed (special sig)	delegate	specialSig thunk	target method
6	Static opened	delegate	shuffle thunk	target method
7	Secure	delegate	call thunk	MethodDesc (frame)

Note: The columns map to the internal fields of a delegate (from System.Delegate)

So we've (deliberately) looked at the simple case, but the more complex scenarios all work along similar lines, just using different and more stubs/thunks as needed e.g. â€˜virtual-stub dispatch' or â€˜call thunk'.

Delegates are special!!

As well as being responsible for creating delegates, the runtime also treats delegate specially, to enforce security and/or type-safety. You can see how this is implemented in the links below

In MethodTableBuilder.cpp:

In ClassCompat.cpp:

Discuss this post in /r/programming and /r/csharp

DEV Community: Matt Warren

ASCII Art in .NET Code

Table of Contents

Dave Cutler

Syntax Trees

Timelines

Logic Tables

Class Hierarchies

Component Diagrams

Algorithms

Bit Packing

Data Structures

State Machines

RFC's and Specs

Dates & Times

Stack Layouts

The Rest

How does .NET JIT a method? (also featuring 'Tiered Compilation')

How it works

Before the method is JITed

After the method has been JITed

JIT and Execution Engine (EE) Interaction

Precode and Stubs

Tiered Compilation

History - ReJIT

How it works

Using a counter

Why not 'Interpreted'?

Why not LLVM?

Summary

Exploring the BBC micro:bit software stack and OS

BBC micro:bit

BBC micro:bit Software Stack

Runtimes

Memory Layout

microbit-dal

mbed-classic

End-to-end (or top-to-bottom)

Writing to the Display

Storing files on the Flash memory

Summary

Further Reading

Best technology-related, non-fiction books

What are the best, technology-related, non-fiction books you've ever read?

What are your favourites?

Punishment Driven Development?

A DoS Attack against the C# Compiler

Exponential Growth

Profiling the Compiler

Summary

DotNetAnywhere: An Alternative .NET Runtime

DotNetAnywhere

Source Code Layout

Native Code - 17,710 lines in total

Managed Code - 28,783 lines in total

Main areas of functionality

Reading .NET dlls

Executing .NET IL

Garbage Collector

Conservative Garbage Collection

GC only does 'Mark-Sweep', it doesn't Compact

Threading Model

Benchmarks

.NET Framework, 4.6.1 - 0.36 seconds

DotNetAnywhere - 54.39 seconds

Analysing C# code on GitHub with BigQuery

Tabs or Spaces?

regions: 'should be banned' or 'okay in some cases'?

'K&R' or 'Allman', where do C# devs like to put their braces?

Do C# developers like writing functional code?

Which using statements are most widely used?

What NuGet packages are most often included in a .NET project?

How many lines of code (LOC) are in a typical C# file?

What is the most widely thrown Exception?

'async/await all the things' or not?

Do C# developers like using the var keyword?

Just how many files should you have in a repository?

What is the most popular repository with C# code in it?

What are the most popular C# class names?

'Foo.cs', 'Program.cs' or something else, what's the most common file name?

`regions`: 'should be banned' or 'okay in some cases'?

Which `using` statements are most widely used?

What is the most widely thrown `Exception`?

Do C# developers like using the `var` keyword?

What are the most popular C# `class` names?

Other functions that call `SetupShuffleThunk(..)`