Dynamic arrays size and dynamic arrays allocators in VC++
https://stackoverflow.com/questions/1598673
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I'm confused a little while writing own tiny discovering program to clear up how Visual C++ allocates the memory for dynamic arrays. I must note, I have never met technical documents that describe this question on new[]/delete[] operators for any C++ implementation.
Initially I thought that new[] and delete[] are something similar to the following if it is interpreted as simple C:
void fake_int_ctor(int _this) {
printf("borns with 0x%08X in the heap\n", _this);
}
void fake_int_dtor(int _this) {
printf("dies with %d\n", _this);
}
void *new_array(unsigned int single_item_size, unsigned int count, void (*ctor)()) {
unsigned int i;
unsigned int *p = malloc(sizeof(single_item_size) + sizeof(count) + single_item_size * count);
p[0] = single_item_size; // keep single item size for delete_array
p[1] = count; // and then keep items count for delete_array
p += 2;
for ( i = 0; i < count; i++ ) {
ctor(p[i]); // simulate constructor calling
}
return p;
}
void delete_array(void *p, void (*dtor)()) {
unsigned int *casted_p = p;
unsigned int single_item_size = casted_p[-2];
unsigned int count = casted_p[-1];
unsigned int i;
for ( i = 0; i < count; i++ ) {
dtor(casted_p[i]); // simulate destructor
}
free(casted_p - 2);
}
void test_allocators(void) {
unsigned int count = 10;
unsigned int i;
int *p = new_array(sizeof(int), count, fake_int_ctor); // allocate 10 ints and simulate constructors
for ( i = 0; i < count; i++ ) {
p[i] = i + i; // do something
}
delete_array(p, fake_int_dtor); // deletes the array printing death-agony-values from 0 to 19 stepping 2
}
This code implies the following structure for dynamic arrays:
-2..-1..0.....|.....|.....|.....
^ ^ ^
| | +-- start of user data, slots may have variable size
| | depending on "single item size" slot
| +------ "items count" slot
+---------- "single item size" slot
My VC++ compiler generated the program that produces the following output:
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
borns with 0xCDCDCDCD in the heap
dies with 0
dies with 2
dies with 4
dies with 6
dies with 8
dies with 10
dies with 12
dies with 14
dies with 16
dies with 18
Obviously, everything is fine in this case. But now when I was trying to discover the nature of "native" VC++ dynamic arrays allocators, I understand that I'm wrong (at least for VC++). So I've got several questions. Where the values of dynamic array sizes are stored in? How do the dynamic arrays allocators work? Which byte-by-byte structure do they use for dynamic arrays? Or... Or could you provide any links that would clarify this for me (VC++ has the highest priority), please?
Solution
I'm not sure what you are looking for here but fake_int_ctor(int) is printing uninitialized memory in the allocated array. Try something like this instead:
void fake_int_ctor(int& _this) {
printf("born at %p\n", (void*)&_this);
}
void fake_int_dtor(int& _this) {
printf("dies at %p\n", (void*)&_this);
}
This should print out the addresses. I'm guessing that this is more along the lines of what you want to see.
This little program isn't really showing anything since you are just allocating a chunk of contiguous storage (ala malloc) and printing out the range of addresses. Nothing really surprising there. The actual storage of arrays is implementation defined. The only thing that is guaranteed is that when you do something like C *p = new C[10], p will point to enough contiguous storage for 10 C objects. How the environment keeps track of what was allocated so that delete [] p calls the destructors for each allocated element is completely implementation defined.
If you really want to dig into this, then start with something like the following snippet. Compile it with assembly listings enabled and look at the generated assembly code.
struct C {
C(): x(0) {}
int x;
};
int main() {
C *p = new C[10];
for (int i=0; i<10; ++i) {
p[i].x = i;
}
delete [] p;
return 0;
}
You should be able to figure out how the compiler represents arrays as long as you turn off all of the optimizations.
OTHER TIPS
It's implement defined. Scott meyer also pointed out that in reality many C++ compiler save the number of elements just before the returned address. I've checked with VC2010 and g++ 3.4.2(mingw). Both compilers implement operator new[]/delete[] in this way:
+--------------------+-------------------------+
| Num of elems(4byte)| Your Object or Array |
+--------------------+-------------------------+
#include <stdio.h>
#include <stdlib.h>
struct X {
int i;
~X() {
puts("a");
}
};
int main()
{
volatile int s = 3;
printf("input a size: ");
fflush(stdout);
scanf("%d", &s);
X * px = reinterpret_cast<X *>(new X[s]);
printf("%d\n", *( (int*)px - 1));
delete[] px;
return 0;
}
I've followed the assembly instruction in VC2010, which is not so hard to read provided you compile the code with debug symbol:
cl /MTd /Zi array_test.cpp
Note the purpose of fflush is to make sure "input a size: " being outputed to the screen before you actually input a size and press enter.
Using scanf to get the size has two reasons: 1. Give you a chance to attach the process to VS debugger 2. Make sure the size will not be optimized to an immediate value.
You'd better input a small number such as 5, which make you life easier when you follow up the assembly instruction, because you can verify the result of some instruction meets your expectation or not.
The following is a line-by-line comments on the actual assembly instruction:
X * px = reinterpret_cast<X *>(new X[s]); ; assume s = 5
00401070 mov ecx,dword ptr [s] ; the number of element is saved to ecx
00401073 mov dword ptr [ebp-0Ch],ecx ; save it to somewhere on the stack
00401076 xor ecx,ecx
00401078 mov eax,dword ptr [ebp-0Ch] ; trace it! now it's in eax
0040107B mov edx,4 ; because sizeof(X) == 4
00401080 mul eax,edx ; Get the total bytes needed for the whole array
00401082 seto cl ; handle the scenario: big size which overflow
00401085 neg ecx ; typically not, so cl = 0, and ecx = 0
00401087 or ecx,eax ; now ecx = eax = 4 * 5 = 20
00401089 xor eax,eax ; clear eax, now eax = 0
0040108B add ecx,4 ; add 4 to ecx, why 4? for save the overhead array size
0040108E setb al ; set al to 1 if carry flag is set, typically 0
00401091 neg eax ; eax = 0, neg eax also result 0
00401093 or eax,ecx ; eax = ecx = 24
00401095 push eax ;
00401096 call operator new (40122Ch) ; same as scalar new
0040109B add esp,4 ; balance the stack
0040109E mov dword ptr [ebp-10h],eax ; function's return value typically saved in EAX
; [ebp-10h] is somewhere on stack, used to save the
; returned raw memory pointer
004010A1 cmp dword ptr [ebp-10h],0 ; check whether returned NULL pointer
004010A5 je main+8Ah (4010BAh)
004010A7 mov ecx,dword ptr [ebp-10h] ; now ECX point to 24 bytes raw memory
004010AA mov edx,dword ptr [ebp-0Ch] ; Check address 00401073, edx is 5 now
004010AD mov dword ptr [ecx],edx ; !!!! 5 saved to the start of the 24 bytes raw memory
004010AF mov eax,dword ptr [ebp-10h] ; load start address of the 24 raw memory to EAX
004010B2 add eax,4 ; advance the EAX with 4 bytes, now EAX point to the
; start address of your first object in the array
004010B5 mov dword ptr [ebp-1Ch],eax ; Save this address to somewhere on the stack
004010B8 jmp main+91h (4010C1h) ; not NULL pointer, so skip it
004010BA mov dword ptr [ebp-1Ch],0 ; See address 004010A5
004010C1 mov ecx,dword ptr [ebp-1Ch] ; Load the address to ECX
004010C4 mov dword ptr [px],ecx ; Load the address in ECX to px. -The End-
The delete[] part:
delete[] px;
004010DC mov ecx,dword ptr [px] ; the address of the first object
004010DF mov dword ptr [ebp-18h],ecx ; save to somewhereon the stack
004010E2 mov edx,dword ptr [ebp-18h] ; save it again to edx
004010E5 mov dword ptr [ebp-14h],edx ; move around
004010E8 cmp dword ptr [ebp-14h],0 ; Check NULL pointer
004010EC je main+0CDh (4010FDh)
004010EE push 3 ; Looks silly, just because I init it to 3?
004010F0 mov ecx,dword ptr [ebp-14h] ; again, ECX is just the address of first object
; [px] -> ecx -> [ebp-18h] -> edx -> [ebp-14h] -> ecx
004010F3 call X::`vector deleting destructor' (401014h) ; A good function name, lets follow it!
X::`vector deleting destructor':
00401014 jmp X::`vector deleting destructor' (401140h)
X::`vector deleting destructor':
00401140 push ebp
00401141 mov ebp,esp
00401143 push ecx ; Address of the first object
00401144 mov dword ptr [ebp-4],ecx ; save it to somewhere on stack
00401147 mov eax,dword ptr [ebp+8] ; See address 004010EE, it's 3
0040114A and eax,2 ; ??
0040114D je X::`vector deleting destructor'+45h (401185h)
0040114F push offset X::~X (401005h) ; (S1) Put address of the descructor to stack
00401154 mov ecx,dword ptr [this] ; Address of first object
00401157 mov edx,dword ptr [ecx-4] ; !! important, ECX - 4 to get the
; address of the 24-bytes raw memory
; The value in it is the number of the elements
; Save it to EDX(=5, see 004010AD)
0040115A push edx ; (S2) Put it on stack
0040115B push 4 ; (S3) Put the sizeof(X) on stack
0040115D mov eax,dword ptr [this] ; save the address of the first object to EAX
00401160 push eax ; (S4) Put it on stack
00401161 call `vector destructor iterator' (40100Ah) ; Good function name, follow it
`vector destructor iterator':
0040100A jmp `vector destructor iterator' (4011F0h)
`vector destructor iterator':
004011F0 push ebp
004011F1 mov ebp,esp
004011F3 mov eax,dword ptr [__s] ; Some tricks here, by inspecting the value and
; some guess work, __s = 4(S3)
004011F6 imul eax,dword ptr [__n] ; __n = 5 (S2)
004011FA add eax,dword ptr [__t] ; __t = (S4), add it to EAX, now point to end
; of the array
004011FD mov dword ptr [__t],eax ; __t point to end of array
00401200 mov ecx,dword ptr [__n] ; loop counter
00401203 sub ecx,1
00401206 mov dword ptr [__n],ecx
00401209 js `vector destructor iterator'+2Ch (40121Ch) ; jump out of loop if value less than 0
0040120B mov edx,dword ptr [__t] ; Load addr: 1-byte passed the end of the array
0040120E sub edx,dword ptr [__s] ; Now point to the address of last element
00401211 mov dword ptr [__t],edx ; Update this address to __t
00401214 mov ecx,dword ptr [__t] ; save the address to ECX
00401217 call dword ptr [__f] ; __f is the address of destructor function
0040121A jmp `vector destructor iterator'+10h (401200h)
0040121C pop ebp
0040121D ret 10h ; Because we have S1, S2, S3, S4
; 4 pushes
struct X {
int i;
~X() {
004011D0 push ebp
004011D1 mov ebp,esp
004011D3 push ecx ; the address of current object: this in C++
004011D4 mov dword ptr [ebp-4],ecx ; save this to [ebp-4], although not used it
puts("a"); ;
004011D7 push offset string "a" (403758h)
004011DC call dword ptr [__imp__puts (406240h)]
004011E2 add esp,4
}
004011E5 mov esp,ebp
004011E7 pop ebp
004011E8 ret
It's implementation defined.
Thus the implementation is (and often does) change with different makes/versions of the compiler (on some systems it differs between release and debug versions)
But saying that you are on the correct lines, thou usually there is more information like the actuall size of the block (if an exact fit was not found) sometimes there is an end block linking back to the startblock so that you can follow chains backwards. Etc...
Share some information w/ you, though it's about GNU C/++, but many C/C++ compilers have something which is similar with each other:
When new() implementing code (the lib code exactly) was executed to allocate a dynamic object or array. The allocated memory in which the object and array placed is a part of a memory buffer which lib code real uses, and the structure looks like the figure below:
+--------------------+-------------------------+
| Overhead Area | Your Object or Array |
+--------------------+-------------------------+
^
|
CObject *pArray ---+
of course you will only use the right area, and cannot overwrite the left area, the Overhead. The pArray returned by "new CObject[]" points to the right area (as shown in above figure) so in general a user will not notice the Overhead (again, the user cannot use the Overhead area).
The size of dynamic allocated array was stored in the Overhead area. When delete[] is called, the lib code will know the array size from the information of the Overhead area.
Lots of things other than the allocated size will be stored in the overhead too.
If you are using low level malloc()/free()/brk() etc to implement new() and delete(), you may reserve an overhead area and return the followed right usable area to the user too, just as GNU C/++.
