Dynamic arrays size and dynamic arrays allocators in VC++

Question

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?

Answer 1

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.