302
Foo* set = new Foo[100];
// ...
delete [] set;

You don't pass the array's boundaries to delete[]. But where is that information stored? Is it standardised?

BartoszKP
  • 34,786
  • 15
  • 102
  • 130
VolkerK
  • 95,432
  • 20
  • 163
  • 226
  • http://sourceforge.net/projects/fastmm/ is open source and replaces the memory-manager. Here you can find out how memory management works and where the informations are come from for allocate and delete memories. –  Feb 02 '16 at 15:46
  • 1
    Note that FastMM is specific to the Delphi/C++Builder compilers only, it is not a general-purpose memory manager for C++. It is not even written in C++. – Remy Lebeau Oct 26 '16 at 23:18

9 Answers9

228

When you allocate memory on the heap, your allocator will keep track of how much memory you have allocated. This is usually stored in a "head" segment just before the memory that you get allocated. That way when it's time to free the memory, the de-allocator knows exactly how much memory to free.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
Peter Kühne
  • 3,224
  • 1
  • 20
  • 24
  • 5
    Note that this only applies to array allocations in C++. All other allocations rely on the size of the type. Some libraries do store all allocation sizes, usually only in debugging mode. – Zan Lynx Oct 13 '08 at 14:30
  • 112
    There is absolutely no reason why this information should not be available to the programmer. I can pass a pointer to a function and free it, but to get the size myself in that same function I have to pass around an extra parameter. Does that make any sense? – Mark Ruzon Jun 11 '09 at 00:16
  • 32
    @Mark, it makes a *small* amount of sense, because in theory it does free the allocator to always store the size of the *allocated* block (which may differ from the size of the *requested* block). Certain allocator designs may need this information for their own purposes, or may not be sophisticated enough to use type information to track the size of non-array heap allocations, etc. Forcing the allocator to store the requested size (so that you wouldn't need to pass the array size yourself) might be a small encumbrance, but it could have performance impacts on conceivable allocator designs. – Doug McClean Oct 24 '09 at 04:27
  • 40
    Sorry, but this answer misses the point. What QuantumPete described is basically "How `free` knows how much memory to deallocate". Yes, the memory block size is stored "somewhere" by `malloc` (normally in the block itself), so that's how `free` knows. However, `new[]`/`delete[]` is a different story. The latter basically work on top of `malloc`/`free`. `new[]` also stores the number of elements it created in the memory block (independently of `malloc`), so that later `delete[]` can retrieve and use that number to call the proper number of destructors. – AnT stands with Russia Oct 24 '09 at 04:35
  • 36
    I.e. physically two counters are stored in the block: block size (by `malloc`) and element count (by `new[]`). Note, that the former cannot be used to calculate the latter, since in general case the size of the memory block can be larger than really necessary for the array of requested size. Also note that the array element counter is only needed for types with non-trivial destructor. For types with trivial destructor the counter is not stored by `new[]` and, of course, not retrieved by `delete[]`. – AnT stands with Russia Oct 24 '09 at 04:38
  • 4
    Mark's point stands though. Since this information must be stored, there's no reason we shouldn't be able to access it as well. If it overallocates, vector could have used that to it's advantage, but as it is, vector must do pointless extra allocations and copies. If it doesn't overallocate, then we can get the array size of dynamic arrays. Either or both would be useful information. – Mooing Duck Apr 30 '12 at 05:52
  • @Mark, if you use `A* = new B(); delete A;` how does compiler know what size of memory to free? – sasha.sochka Aug 14 '13 at 15:09
  • 3
    @sasha.sochka: The *compiler* doesn't know. `delete A` simply calls the `A` destructor (if it is virtual, polymorphism calls the `B` destructor), and then passes the memory block pointed to by `A` to the *memory manager* for freeing. The *memory manager* knows how much memory it allocated to satisfy the `new B()` call. – Remy Lebeau Oct 26 '16 at 23:22
  • 1
    @MooingDuck It's not true that it "must" be stored. There are allocators that cannot determine the size of every block at all times. For example, buddy allocators may be designed such that they are unable to tell the size of an "odd" block unless its corresponding "even" block is free. – David Schwartz Dec 09 '16 at 07:26
  • 2
    @DavidSchwartz fair enough for things with trivial destructors. For nontrivial destructors, the allocator needs to store the item count. – Mooing Duck Dec 10 '16 at 02:26
  • 1
    @MooingDuck Only for an array allocator, otherwise the item count is always one. – David Schwartz Dec 10 '16 at 04:26
  • 2
    Downvoted because, as AnT noted, it completely misses the point and doesn't answer the question. This really should be deleted (heh), or fixed to give the correct answer (as given in AnT's second comment). – Jim Balter Oct 16 '17 at 06:51
  • Where is the "head" segment? – choxsword Apr 30 '18 at 02:37
  • @AnT Would it be possible for an implementation to use an allocator that _always_ allocates blocks in such a way that the array size can be calculated from the block size, though? I.e. for `T[]` the amount of "extra" space in the block would always be less than `sizeof(T)`, which would let the runtime compute the array size using truncated division. Or is the implementation not able to require such a property of the allocator? – Kyle Strand Aug 15 '19 at 22:26
  • 1
    @Kyle Strand: It is probably quite possible. Let's say, an implementation aligns each block size on `W`-byte boundary. Then for an `T[N]` array (`S = sizeof(T[N])`) it can allocate the properly aligned number of bytes `B = (S + W - 1) / W * W`, but store in the block header the actually requested number of bytes `S`. Then the array size will be correctly deducible from the stored value of `S`. The actual aligned block size `B` is also easily deducible from `S`. – AnT stands with Russia Aug 15 '19 at 22:47
  • 1
    @AnT I talked to an LLVM dev the other day who confirmed that indeed this is how `new[]` and `delete[]` are implemented by default. – Kyle Strand Aug 26 '19 at 18:36
  • @RemyLebeau Your explanation makes sense! But some questions: Is the *'memory manager'* a part of the OS? According to AnT's comment, the size of the array is recorded in the memory block, so it seems that the compiler knows the size of the array. (It depends on the implementation, but I mean a typical implementation) – starriet Jul 29 '22 at 01:21
  • 1
    @starriet "*Is the 'memory manager' a part of the OS?*" - no, it is part of the compiler and runtime library (but may use the OS' memory API internally). When your code calls `new`/`new[]`, the compiler gens code to ask the MM to allocate space for the object/array (which internally tracks how much was allocated), and then calls the type's constructor(s) on that memory. When your code calls `delete`/`delete[]`, the compiler gens code to call the type's destructor(s) on the memory, and then give the memory to the MM to free (which will refer to the tracking to know how much to free)... – Remy Lebeau Jul 29 '22 at 01:32
  • 1
    @starriet ... how the MM tracks the size of the allocation is indeed an *implementation* detail. Storing the size inside the allocated memory itself is a common implementation, but not a required one, or the only way. – Remy Lebeau Jul 29 '22 at 01:34
35

ONE OF THE approaches for compilers is to allocate a little more memory and to store a count of elements in a head element.

Example how it could be done:

Here

int* i = new int[4];

compiler will allocate sizeof(int)*5 bytes.

int *temp = malloc(sizeof(int)*5)

Will store "4" in the first sizeof(int) bytes

*temp = 4;

and set i

i = temp + 1;

So i will points to an array of 4 elements, not 5.

And deletion

delete[] i;

will be processed in the following way:

int *temp = i - 1;
int numbers_of_element = *temp; // = 4
... call destructor for numbers_of_element elements
... that are stored in temp + 1, temp + 2, ... temp + 4 if needed
free (temp)
Avt
  • 16,927
  • 4
  • 52
  • 72
13

The information is not standardised. However in the platforms that I have worked on this information is stored in memory just before the first element. Therefore you could theoretically access it and inspect it, however it's not worth it.

Also this is why you must use delete [] when you allocated memory with new [], as the array version of delete knows that (and where) it needs to look to free the right amount of memory - and call the appropriate number of destructors for the objects.

Dominik Grabiec
  • 10,315
  • 5
  • 39
  • 45
8

It's defined in the C++ standard to be compiler specific. Which means compiler magic. It can break with non-trivial alignment restrictions on at least one major platform.

You can think about possible implementations by realizing that delete[] is only defined for pointers returned by new[], which may not be the same pointer as returned by operator new[]. One implementation in the wild is to store the array count in the first int returned by operator new[], and have new[] return a pointer offset past that. (This is why non-trivial alignments can break new[].)

Keep in mind that operator new[]/operator delete[]!=new[]/delete[].

Plus, this is orthogonal to how C knows the size of memory allocated by malloc.

MSN
  • 53,214
  • 7
  • 75
  • 105
5

Basically its arranged in memory as:

[info][mem you asked for...]

Where info is the structure used by your compiler to store the amount of memory allocated, and what not.

This is implementation dependent though.

Francisco Soto
  • 10,277
  • 2
  • 37
  • 46
4

This isn't something that's in the spec -- it's implementation dependent.

jeffm
  • 3,120
  • 1
  • 34
  • 57
2

Because the array to be 'deleted' should have been created with a single use of the 'new' operator. The 'new' operation should have put that information on the heap. Otherwise, how would additional uses of new know where the heap ends?

Joel Coehoorn
  • 399,467
  • 113
  • 570
  • 794
1

This is a more interesting problem than you might think at first. This reply is about one possible implementation.

Firstly, while at some level your system has to know how to 'free' the memory block, the underlying malloc/free (which new/delete/new[]/delete[] generally call) don't always remember exactly how much memory you ask for, it can get rounded up (for example, once you are above 4K it is often rounded up to the next 4K-sized block).

Therefore, even if could get the size of the memory block, that doesn't tell us how many values are in the new[]ed memory, as it can be smaller. Therefore, we do have to store an extra integer telling us how many values there are.

EXCEPT, if the type being constructed doesn't have a destructor, then delete[] doesn't have to do anything except free the memory block, and therefore doesn't have to store anything!

Chris Jefferson
  • 7,225
  • 11
  • 43
  • 66
-1

It is not standardized. In Microsoft's runtime the new operator uses malloc() and the delete operator uses free(). So, in this setting your question is equivalent to the following: How does free() know the size of the block?

There is some bookkeeping going on behind the scenes, i.e. in the C runtime.

Andre
  • 1,577
  • 1
  • 13
  • 25
  • 7
    Not true. Before calling free, the delete[] needs to call destructors first. For this knowing total allocations size is not enough. Actually new[] and delete[] works different for plain and destructed types in VC++. – Suma Oct 13 '08 at 14:25