GetHashCode inside CLR: Reference types

.NET internals
Page content

GetHashCode, a part of the Object class, is one of the key method present in every class instance. Its main purpose is to calculate and return a number associated with the specified object, which will be used as hash (a very good example is Dictionary class). This article will be split into two parts: the first one will focus on the reference types and the second one on the value types. We will focus on the internal implementation of CLR and try to figure out how exactly the hash code for reference and value types is generated.

Theory

Let’s start from the beginning: what characteristics should have a hash function to be useful for programmers. According to documentation of GetHashCode method, we can point three the most important:

  • If instance X is equal to the instance Y, then hash code returned from the X must be equal to the hash code returned from the Y. It doesn’t work backward! If instance X returns hash code HX and instance Y returns hash code HY, where HX and HY are the same, then it doesn’t mean that both instances are equal.
  • Hash code should be even distribution, which means that small change in one of the instance fields should produce a big change in the number generated by GetHashCode method.
  • Hash function should be inexpensive (in terms of performance) and don’t throw any exceptions.

Every class inherits (implicit or explicit) from Object class, which guarantees that you will have a set of methods (GetHashCode, Equals, GetType and ToString) available in every instance. What’s more, .NET provides a default implementation for all of them, which means that you can use them without overriding and making custom algorithms.

The theory shown above sounds cool, but things are going to be a little complicated. In .NET, we can distinguish two basic types which determine how an object behaves: reference and value types. Let’s talk about reference types first.

Inside CLR

One of the popular myths says that hash code in reference types is directly related to its address in memory. It’s false! Yes, it doesn’t depend from the fields within instance due to performance and practical reasons - if you have Person class with Age, then changing this member won’t change hash code unless you provide your implementation of GetHashCode. It’s really important to remember, that garbage collector not only deletes unused objects but also compacts rest of the entries reduce holes between them - which means that there is always a chance that object will change its address (C# provides a fixed keyword which locks object’s position in memory). In this situation, basing on this during generating hash code would be pointless.

Most of the articles don’t explain how exactly hash code is generated, and what formula is used - we will try to find out this. First, let’s check what is the implementation of RuntimeHelpers.GetHashCode method (used directly by default in Object.GetHashCode):

1
2

[MethodImplAttribute(MethodImplOptions.InternalCall)]
public static extern int GetHashCode(object o);

The MethodImplAttribute attribute indicates that the implementation can be found inside CLR - to find out how hash code is generated for reference types, we will dig into CLR source code. First, let’s check how the internal method is mapped into the C++ source. We can find it in /src/coreclr/src/vm/ecalllist.h file, which can be described as the bridge between C# internal calls and C++ functions. Let’s find our method:

1

FCFuncElement("GetHashCode", ObjectNative::GetHashCode)

This line indicates, that the GetHashCode is mapped into ObjectNative::GetHashCode function. We can find it in /src/coreclr/src/classlibnative/bcltype/objectnative.cpp:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// Note that we obtain a sync block index without actually building a sync block.
// That's because a lot of objects are hashed, without requiring support for
FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {

    CONTRACTL
    {
        FCALL_CHECK;
        INJECT_FAULT(FCThrow(kOutOfMemoryException););
    }
    CONTRACTL_END;

    VALIDATEOBJECT(obj);

    if (obj == 0)
        return 0;

    OBJECTREF objRef(obj);

    {
        DWORD bits = objRef->GetHeader()->GetBits();

        if (bits & BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX)
        {
            if (bits & BIT_SBLK_IS_HASHCODE)
            {
                // Common case: the object already has a hash code
                return  bits & MASK_HASHCODE;
            }
            else
            {
                // We have a sync block index. This means if we already have a hash code,
                // it is in the sync block, otherwise we generate a new one and store it there
                SyncBlock *psb = objRef->PassiveGetSyncBlock();
                if (psb != NULL)
                {
                    DWORD hashCode = psb->GetHashCode();
                    if (hashCode != 0)
                        return  hashCode;
                }
            }
        }
    }

    FC_INNER_RETURN(INT32, GetHashCodeHelper(objRef));
}
FCIMPLEND

This is quite a nice piece of code, so let’s stop for a moment. First, we need to know that every instance in .NET contains an internal field called “SyncBlock Index” - this is the index of the entry in internal CLR array, which contains things required for proper work in a multithread environment. By default, “SyncBlock Index” is set to -1 which means that the object isn’t used for synchronization. If we will use Monitor.Enter with some object as a parameter, then a proper entry in the SyncBlock list will be created and associated.

Now, look at the code above. First, the CLR reads the header of instance and checks (bits & BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX) if the value of SyncBlock index targets entry in SyncBlock list or contains hashcode. The second one can be a bit misleading, but it’s a smart optimization which allows reducing memory usage by using this field to store hash code if there is no any SyncBlock associated with an object.

The second condition (bits & BIT_SBLK_IS_HASHCODE) is more specific and checks if the SyncBlock index contains proper hash code. If yes, we can just return the value (because it means that something earlier generated and stored it). Otherwise, it means that there is already some SyncBlock entry created and associated with an object, so we can’t read or store hash code here. In this case, hash code is stored inside SyncBlock entry to avoid conflict and that’s why CLR reads entry using SyncBlock *psb = objRef->PassiveGetSyncBlock();. Then, hash code is read with psb->GetHashCode() and returned.

If the first condition (bits & BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX) is false, then it means that hash code doesn’t exist for the particular object and has to be generated. This is done by FC_INNER_RETURN(INT32, GetHashCodeHelper(objRef)); line, where we can spot the GetHashCodeHelper call. Let’s see what’s inside:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

NOINLINE static INT32 GetHashCodeHelper(OBJECTREF objRef)
{
    DWORD idx = 0;

    FC_INNER_PROLOG(ObjectNative::GetHashCode);

    HELPER_METHOD_FRAME_BEGIN_RET_ATTRIB_1(Frame::FRAME_ATTR_EXACT_DEPTH|Frame::FRAME_ATTR_CAPTURE_DEPTH_2, objRef);

    idx = objRef->GetHashCodeEx();

    HELPER_METHOD_FRAME_END();
    FC_INNER_EPILOG();
    return idx;
}

This function is in fact just a objRef->GetHashCodeEx() call - rest of the code is used by internal CLR mechanisms. We can found it in /src/vm/object.cpp:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

INT32 Object::GetHashCodeEx()
{
    CONTRACTL
    {
        MODE_COOPERATIVE;
        THROWS;
        GC_NOTRIGGER;
    }
    CONTRACTL_END

    // This loop exists because we're inspecting the header dword of the object
    // and it may change under us because of races with other threads.
    // On top of that, it may have the spin lock bit set, in which case we're
    // not supposed to change it.
    // In all of these case, we need to retry the operation.
    DWORD iter = 0;
    DWORD dwSwitchCount = 0;
    while (true)
    {
        DWORD bits = GetHeader()->GetBits();

        if (bits & BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX)
        {
            if (bits & BIT_SBLK_IS_HASHCODE)
            {
                // Common case: the object already has a hash code
                return  bits & MASK_HASHCODE;
            }
            else
            {
                // We have a sync block index. This means if we already have a hash code,
                // it is in the sync block, otherwise we generate a new one and store it there
                SyncBlock *psb = GetSyncBlock();
                DWORD hashCode = psb->GetHashCode();
                if (hashCode != 0)
                    return  hashCode;

                hashCode = ComputeHashCode();

                return psb->SetHashCode(hashCode);
            }
        }
        else
        {
            // If a thread is holding the thin lock we need a syncblock
            if ((bits & (SBLK_MASK_LOCK_THREADID)) != 0)
            {
                GetSyncBlock();
                // No need to replicate the above code dealing with sync blocks
                // here - in the next iteration of the loop, we'll realize
                // we have a syncblock, and we'll do the right thing.
            }
            else
            {
                // We want to change the header in this case, so we have to check the BIT_SBLK_SPIN_LOCK bit first
                if (bits & BIT_SBLK_SPIN_LOCK)
                {
                    iter++;
                    if ((iter % 1024) != 0 && g_SystemInfo.dwNumberOfProcessors > 1)
                    {
                        YieldProcessorNormalized(); // indicate to the processor that we are spinning
                    }
                    else
                    {
                        __SwitchToThread(0, ++dwSwitchCount);
                    }
                    continue;
                }

                DWORD hashCode = ComputeHashCode();

                DWORD newBits = bits | BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX | BIT_SBLK_IS_HASHCODE | hashCode;

                if (GetHeader()->SetBits(newBits, bits) == bits)
                    return hashCode;
                // Header changed under us - let's restart this whole thing.
            }
        }
    }
}

This is in fact just an extended version of the previously described ObjectNative::GetHashCode, with more checks to ensure thread safety. The most interesting line is hashCode = ComputeHashCode();, which calls the function to calculate new hash code - the part we are looking for.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// follow the necessary rules to get a new valid hashcode for an object
DWORD Object::ComputeHashCode()
{
    DWORD hashCode;

    // note that this algorithm now uses at most HASHCODE_BITS so that it will
    // fit into the objheader if the hashcode has to be moved back into the objheader
    // such as for an object that is being frozen
    do
    {
        // we use the high order bits in this case because they're more random
        hashCode = GetThread()->GetNewHashCode() >> (32-HASHCODE_BITS);
    }
    while (hashCode == 0);   // need to enforce hashCode != 0

    // verify that it really fits into HASHCODE_BITS
     _ASSERTE((hashCode & ((1<<HASHCODE_BITS)-1)) == hashCode);

    return hashCode;
}

Let’s anaylze what does hashCode = GetThread()->GetNewHashCode() >> (32-HASHCODE_BITS); mean. First, we see that hash code is generated using the specified thread - which means that instance X will have different hash code depending on thread which generated it. Second, there is some misterious bit shift using HASHCODE_BITS constant, defined in /src/vm/syncblk.h

1

#define HASHCODE_BITS                   26

Authors of CLR decided that 26-bit hash code will be even distribution, which is one of the key hash code features. GetNewHashCode is a part of the Thread class and can be found in /src/coreclr/src/vm/threads.h:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

inline DWORD GetNewHashCode()
{
    LIMITED_METHOD_CONTRACT;
    // Every thread has its own generator for hash codes so that we won't get into a situation
    // where two threads consistently give out the same hash codes.
    // Choice of multiplier guarantees period of 2**32 - see Knuth Vol 2 p16 (3.2.1.2 Theorem A).
    DWORD multiplier = GetThreadId()*4 + 5;
    m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
    return m_dwHashCodeSeed;
}

And here it is! Our final formula is quite simple - just a multiplication of thread ID with a random number (thanks to linear congruential generator). It’s very effective and fast algorithm to generate new hash codes, thus ensuring even distribution. m_dwHashCodeSeed is initialized in /src/vm/threads.cpp and looks as follows:

1
2
3
4

// Initialize this variable to a very different start value for each thread
// Using linear congruential generator from Knuth Vol. 2, p. 102, line 24
dwHashCodeSeed = dwHashCodeSeed * 1566083941 + 1;
m_dwHashCodeSeed = dwHashCodeSeed;

The last unknown, dwHashCodeSeed is a static variable that contains the constant seed for linear congruential generator.

1

static  DWORD dwHashCodeSeed = 123456789;

Summary

Here, our short journey ends. We saw how a simple GetHashCode call runs whole CLR mechanisms to generate a hash code for a reference type. Next time, we will try to do the same thing but for value types - they are much more complex and use a set of algorithms to calculate hash code, depending on the object type or fields inside a structure.