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
Part 7 — Stack allocation once again
Part 8 — Unsafe list in .NET Core x64
Part 9 – Hijacking new in x64
Part 10 – Hijacking new in .NET Core
Part 11 — Benchmarking UnsafeList
Part 12 — Hiding objects from GC
Part 13 — In-place serialization
Part 14 — Unsafe code without unsafe keyword
Part 15 — Allocating object on a stack without unsafe
Part 16 — Hijacking new on Linux with .NET 5
Part 17 — Hijacking methods on .NET 5 with modifying metadata curious thing
Part 18 — Hijacking methods on .NET 5 with modifying machine code
If you are interested in the topic see the talk page
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!
Table of Contents
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
ctorwith 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:
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:
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:
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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:
|
1 |
.loadby sos clr |
Select proper thread:
|
1 2 3 4 5 6 |
0:000> ~0s eax=00000000 ebx=00000094 ecx=00000000 edx=00000000 esi=006fee80 edi=00000000 eip=77db265c esp=006fed68 ebp=006fedc8 iopl=0 nv up ei pl nz na po nc cs=0023 ss=002b ds=002b es=002b fs=0053 gs=002b efl=00000202 ntdll!NtReadFile+0xc: 77db265c c22400 ret 24h |
Present all values:
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
0:000> !clrstack -i -a Loaded C:\tmp\mscordbi.dll\5B5541F311f000\mscordbi.dll Loaded C:\Windows\Microsoft.NET\Framework\v4.0.30319\mscordacwks.dll Dumping managed stack and managed variables using ICorDebug. ============================================================================= Child SP IP Call Site 008feb18 77db265c [NativeStackFrame] 008feb94 73001b4f 008feb98 (null) [Managed to Unmanaged transition: 008feb98] 008febfc 7373cdd3 [DEFAULT] I4 System.IO.__ConsoleStream.ReadFileNative(Class Microsoft.Win32.SafeHandles.SafeFileHandle,SZArray UI1,I4,I4,Boolean,Boolean,ByRef I4) (C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll) PARAMETERS: + (Error 0x80131304 retrieving parameter 'hFile') + (Error 0x80131304 retrieving parameter 'bytes') + (Error 0x80131304 retrieving parameter 'offset') + (Error 0x80131304 retrieving parameter 'count') + (Error 0x80131304 retrieving parameter 'useFileAPIs') + (Error 0x80131304 retrieving parameter 'isPipe') + (Error 0x80131304 retrieving parameter 'bytesRead') LOCALS: + (Error 0x80004005 retrieving local variable 'local_0') + (Error 0x80004005 retrieving local variable 'local_1') + (Error 0x80004005 retrieving local variable 'local_2') + (Error 0x80004005 retrieving local variable 'local_3') + (Error 0x80004005 retrieving local variable 'local_4') + (Error 0x80004005 retrieving local variable 'local_5') 008fec30 7373cce2 [DEFAULT] [hasThis] I4 System.IO.__ConsoleStream.Read(SZArray UI1,I4,I4) (C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll) PARAMETERS: + (Error 0x80131304 retrieving parameter 'this') + (Error 0x80131304 retrieving parameter 'buffer') + (Error 0x80131304 retrieving parameter 'offset') + (Error 0x80131304 retrieving parameter 'count') LOCALS: + (Error 0x80004005 retrieving local variable 'local_0') + (Error 0x80004005 retrieving local variable 'local_1') 008fec50 72f34df7 [DEFAULT] [hasThis] I4 System.IO.StreamReader.ReadBuffer() (C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll) PARAMETERS: + System.IO.StreamReader this @ 0x2ae4a5c LOCALS: + (Error 0x80004005 retrieving local variable 'local_0') + (Error 0x80004005 retrieving local variable 'local_1') 008fec60 72fb442c [DEFAULT] [hasThis] String System.IO.StreamReader.ReadLine() (C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll) PARAMETERS: + System.IO.StreamReader this @ 0x2ae4a5c LOCALS: + (Error 0x80004005 retrieving local variable 'local_0') + (Error 0x80004005 retrieving local variable 'local_1') + (Error 0x80004005 retrieving local variable 'local_2') + (Error 0x80004005 retrieving local variable 'local_3') 008fec7c 7387e791 [DEFAULT] [hasThis] String System.IO.TextReader+SyncTextReader.ReadLine() (C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll) PARAMETERS: + System.IO.TextReader+SyncTextReader this @ 0x2ae4ddc LOCALS: (none) 008fec8c 736e50f0 [DEFAULT] String System.Console.ReadLine() (C:\WINDOWS\Microsoft.Net\assembly\GAC_32\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll) PARAMETERS: (none) LOCALS: (none) 008fec94 00b405c0 [DEFAULT] Void Makeref.Program.Main() (C:\app\Makeref.exe) PARAMETERS: (none) LOCALS: + Makeref.Poco heapPoco @ 0x2ae2848 + Makeref.Poco originalPoco @ 0x2ae2848 + Makeref.Program+c__DisplayClass0_0 CS$8__locals0 @ 0x2ae2854 + int* space = 195948557 + typedbyref typedReference @ 0x2ae2848 + int* pocoAddress = 0 + int i = 10 + (Error 0x80004005 retrieving local variable 'local_7') + (Error 0x80004005 retrieving local variable 'local_8') + int i = 0 + (Error 0x80004005 retrieving local variable 'local_10') + (Error 0x80004005 retrieving local variable 'local_11') + (Error 0x80004005 retrieving local variable 'local_12') 008fedf0 7402eaf6 [NativeStackFrame] Stack walk complete. ============================================================================= |
Next, dump the memory on a stack with dd and observe that indeed we have bad food on a stack.
|
1 2 3 4 5 6 7 8 9 |
0:000> dd 008fec94 008fec94 0badf00d 0badf00d 0badf00d 0badf00d 008feca4 0badf00d 0badf00d 0badf00d 0badf00d 008fecb4 0badf00d 0badf00d fe370dde 00000000 008fecc4 00000000 00000000 00000000 00000000 008fecd4 00000000 00000000 00000000 00000000 008fece4 00000000 00000000 00000000 00000000 008fecf4 00000000 00000000 00000000 00000000 008fed04 00000000 00000000 00000000 00000000 |
Now, let’s get a pointer to the object:
|
1 2 |
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:
|
1 2 3 4 5 6 |
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?).
Let’s see the stack:
|
1 2 3 4 5 6 7 8 9 |
0:008> dd 008fec94 008fec94 00000000 00ac4dd4 00000005 0badf00d 008feca4 0badf00d 0badf00d 0badf00d 0badf00d 008fecb4 0badf00d 0badf00d fe370dde 00000000 008fecc4 00000000 00000000 00000000 00000000 008fecd4 00000000 00000000 00000000 00000000 008fece4 00000000 00000000 00000000 00000000 008fecf4 00000000 00000000 00000000 00000000 008fed04 00000000 00000000 00000000 00000000 |
We now have our object on the stack. Let’s create a reference to it.
|
1 2 |
*((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
|
1 2 3 4 5 |
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:
|
1 2 3 4 5 6 7 |
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):
|
1 2 3 4 5 6 |
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:
|
1 2 3 |
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:
|
1 2 3 |
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):
|
1 2 3 4 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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.