This is the first part of the Custom memory allocation series. For your convenience you can find other parts using the links below :
Part 1 — Allocating object on a stack
Part 2 — List copying objects
Part 3 — Hijacking new operator
Part 4 — Invoking constructor for uninitialized object
Part 5 — Inlining method by hand
Part 6 — Memory errors

If you are interested in the topic, I gave talk at 101. KGD.NET and at Studencki Festiwal Informatyczny which you can find here. I also discussed the topic at dotNetConfPL 2017

Hi! Today we start a new series of posts in which we will see details of memory allocation in .NET. In this part we will allocate managed object of reference type on a stack. Let’s go!

Introduction

It is a common interview question: where are stored value types and where are stored reference types in .NET. Common answer says that value types are stored on the stack whereas reference types are stored on the heap. More inquiring recruiter might ask: what happens with value types inside reference types, and should hear that they are stored on the heap as well (since they are part of the reference type). However, is it possible to store reference type on a stack?

These questions are odd. First, there is no hard definition of stack and heap in .NET standard, so asking about it pointless. However, without this knowledge it might be hard to track memory problems in real applications so it is worth knowing the internal implementation. So in order to ask these questions correctly, we should specify the version of the .NET we are talking about, processor architecture, operating system, and so on. Only doing that the question makes sense.

So let’s do that. Let’s assume that we have Microsoft .NET Framework 4.5 version 4.5.50709 and Windows 10 x64 running on Intel Core i7-4700 processor. Is it possible to allocate reference type on a stack using application compiled as Any CPU? And the answer is: it depends.

So what is the answer?

It depends on what do we understand by “allocate”. If we simply mean that we want to have an object on a stack, than the answer is “yes”. If we want CLR to call constructor and initialize object in a place which we specify, then answer is still “yes”. If we want to do that without unsafe, marshalling, and not especially clean hacks, then the answer is “no”. So it is up to you which answer you choose.

Today we are going to copy existing object from a heap to a stack. In one of the next parts we will see how to modify CLR in runtime in order to hijack the allocation mechanism and be able to implement allocator in C#. Let’s start.

Allocation process

In order to allocate a new managed object we usually use new operator. This is compiled to newobj MSIL instruction, which does the following (see MSDN):

  • allocates a new instance of the class associated with ctor
  • initializes all the fields in the new instance to zero (of the proper type) or null references as appropriate
  • calls the constructor ctor with the given arguments along with the newly created instance
  • after the constructor has been called, the now initialized object reference (type O) is pushed on the stack

So there are three important parts of allocation. First, we allocates some memory and set its content to zeros (the latter is done by the operating system usually). Next, we call the constructor so the object has an opportunity to initialize itself. Finally, we store reference to the object on a stack. Since we will be mangling with the memory, let’s leave the high-level nomenclature and call it a pointer (yes, old and dirty pointer like in C++ language).

In order to allocate object on a stack we might try to modify the first part of this process and point CLR to other place in memory. However, this would be too deep water for the first time, so today we will ask .NET to allocate object on a heap, and then we will copy it on a stack. Next, we will verify that the object is usable, so we should be able to do the following:

  • access object’s fields
  • call object’s methods (and also properties)
  • call object’s virtual methods
  • lock on object
  • check in which GC generation the object is stored

Let’s see how objects are stored internally.

Memory structure

Value types are stored very easy: they are just a bunch of bytes representing the value:
Value type in the memory. Source: CodeProject
Pointer points directly to the object memory so we are basically not able to tell anything about it without knowing its type. As a side note: this also explains why we need to specify method table address when using !dumpvc command in WinDBG.

Reference types are completely different. We have a thing called reflection which allows us to inspect object’s methods, fields, properties etc. In order to do that, we need to know the object’s type. All the magic becomes obvious when we check the memory structure:
Refernce type in the memory. Source: CodeProject
As we can see, pointer points to the thing called Method table address. This is a pointer point to the Method table, which describes the object. It contains all the information about methods, fields, inheritance hierarchy etc so we are able to inspect the object with reflection. After the method table address there are fields of the object. It is also important, that the object does not contain any methods. Object is just a bunch of fields, all of the other stuff is stored somewhere else. From the internal point of view, all instance methods are static and they accept one additional parameter: pointer to the object.

It is also worth noting that there is a thing before the object called Sync block address. This is used to lock objects with lock construct.

Now our task is a bit more clear: in order to copy object, we need to know its size, copy all the fields, sync block address, and method table address. This should allow use to do all the things we would like to do.

__makeref and __refvalue

In order to read and write memory we will use two undocumented C# keywords: __makeref and __refvalue. The former allows use to create a Typed Reference from a reference, the latter allows use to reverse the process. Typed reference is a some kind of a pointer which allows us to directly access memory. It is sometimes used to speed up code using value types in order to avoid boxing. We can also get its address and end up with the following indirection:
Indirection
So we basically have a bunch of bytes and a pointer to it (called reference in .NET language), then we have Typed reference pointing to reference, and finally we have an IntPtr pointing to Typed reference. Since we end up with pointer to integer, we can dereference it a few times and get a direct access to the object.

Having that, we will be able to copy memory to the stack. In order to use the object, we will need to create a reference to it, and here is the time when we use __refvalue keyword.

To sum up: we allocate the object on a heap. We allocate some memory on a stack (using stackalloc keyword or simply by allocating a structure with a few integers). Next, we get a pointer to pointer to pointer to object and copy it’s content to the stack. We need to store method table address so the object will be recognizable for .NET, we also need a sync block pointer in order to be able to lock the object. Finally, we create a reference to the object and we are done.

The code

It is high time to write some code. We start with the following class:

class Poco
{
	public int Field;

	public void WriteField()
	{
		Console.WriteLine(Field);
	}

	public override string ToString()
	{
		return Field.ToString();
	}

	~Poco()
	{
		Console.WriteLine("Cleaning: " + Field);
	}
}

We simply define a structure with one integer, one non-virtual method (WriteField), one virtual method (ToString), and a destructor (or rather finalizer).

Next, we allocate some memory on a stack and an object on a heap:

static void Main(string[] args)
{
	Poco heapPoco = new Poco {Field = 5};
	Poco originalPoco = heapPoco;
	unsafe
	{
		var space = stackalloc int[10];
		for (int i = 0; i < 10; ++i)
		{
			space[i] = 0xBADF00D;
		}
		// ...
	}
}

As we can see, we have an object on a heap with its field initialized to five, we also have ten integers on a stack allocated with stackalloc. We set these integers to BADF00D in order to be able to find them on a stack. Compile this code (don't forget to allow using of unsafe keyword in build options), run it with WinDBG and execute the following commands:

Load SOS:

.loadby sos clr

Select proper thread:

~0s

Present all values:

!clrstack -i -a

Next, dump the memory on a stack with dd and observe that indeed we have bad food on a stack.
Now, let's get a pointer to the object:

TypedReference typedReference = __makeref(heapPoco);
int* poco1Address = (int*)(*(int*)(*(int*)(&typedReference)) - 4);

We create a TypedReference using mentioned keyword. Next, we get an address of it, then we cast it to int pointer (so we have a pointer to TypedReference to reference to object), we dereference it and cast it to int pointer (so we have a pointer to reference to object), dereference it (so we have an address of an object), finally we subtract 4 (so we point to the sync block) and cast it to the int pointer. Remember, that we compile as AnyCPU, so we basically run as x86 and the pointer has four bytes. You can verify that we have a correct pointer with WinDBG (by dumping the object from the heap).

Now, we copy the memory:

for (int i = 0; i < 3; ++i)
{
	space[i] = *poco1Address;
	poco1Address = poco1Address + 1;
}
Console.WriteLine("Rewritten values");

We need to copy exactly three integers (sync block, method table pointer, one field). You can now verify that we wrote some bytes on the stack (remember the bad food pattern?).

We now have our object on the stack. Let's create a reference to it.

*((int*)*((int*)&typedReference)) = (int)(&(space[1]));
Poco stackPoco = __refvalue(typedReference, Poco);

We take our TypedReference, once again gets its address, dereference it a few times and cast to int pointers. We do all these things just to get a pointer to the reference pointing to the object on a heap and modify it. Now, our reference points to object on the stack. We did not modify the object, we modified the pointer (reference) pointing to it! Finally, we create a reference from TypedReference.

Cool, let's now verify that everything is fine. First, let's write a field's content using non-virtual method

Console.WriteLine("Got poco on stack. Displaying values:");
Console.Write("Heap: ");
originalPoco.WriteField();
Console.Write("Stack: ");
stackPoco.WriteField();

You should get the same two values (five in both cases) since we copied the object.

Next, let's modify the values:

Console.WriteLine("Modifying values using references. Displaying values:");
originalPoco.Field = 555;
stackPoco.Field = 444;
Console.Write("Heap: ");
originalPoco.WriteField();
Console.Write("Stack: ");
stackPoco.WriteField();

Now you should get two different values.

We can also modify our object using the int array we declared at the beginning (since the object is in the same area):

Console.WriteLine("Modifying value using array on a stack. Displaying values:");
space[2] = 333;
Console.Write("Heap: ");
originalPoco.WriteField();
Console.Write("Stack: ");
stackPoco.WriteField();

We can call virtual methods:

Console.WriteLine("Calling virtual method:");
Console.WriteLine("Heap: " + originalPoco.ToString());
Console.WriteLine("Stack: " + stackPoco.ToString());

We can also verify that our object is correctly recognized:

Console.WriteLine("Displaying object types:");
Console.WriteLine(originalPoco.GetType());
Console.WriteLine(stackPoco.GetType());

We can check GC generations. Heap object should be in generation zero (since it is a pretty new object), stack object should be in generation two (probably because it is not in generation zero and not in generation one so the GC assumes that it is in generation two):

Console.WriteLine("Displaying GC generations:");
Console.WriteLine(GC.GetGeneration(originalPoco));
Console.WriteLine(GC.GetGeneration(stackPoco));
//GC.ReRegisterForFinalize(stackPoco); - bad idea

You can also try to register object for finalization — its destructor should be called when the next collection occurs. However, please don't do that!

We can also try to lock the object:

Console.WriteLine("Threading:");
Console.WriteLine(string.Format("Taking lock in base: {0}", DateTime.Now));
lock (stackPoco)
{
	Console.WriteLine(string.Format("Lock in base aquired: {0}", DateTime.Now));
	Task.Factory.StartNew(() =>
	{  
		Console.WriteLine(string.Format("Taking lock in child: {0}", DateTime.Now));
		lock (stackPoco)
		{
			Console.WriteLine(string.Format("Lock in child aquired: {0}", DateTime.Now));
		}
		Console.WriteLine(string.Format("Lock in child released: {0}", DateTime.Now));
	});
	Thread.Sleep(2000);
}
Console.WriteLine(string.Format("Lock in base released: {0}", DateTime.Now));

Cool. You can see the whole code here.

Summary

As we can see, it is possible to allocate object on a stack. In the next part we will examine this idea to implement list which stores objects instead of references to them. Stay tuned.