How does free know how much to free?

Question

In C programming, you can pass any kind of pointer you like as an argument to free, how does it know the size of the allocated memory to free? Whenever I pass a pointer to some function, I have to also pass the size (ie an array of 10 elements needs to receive 10 as a parameter to know the size of the array), but I do not have to pass the size to the free function. Why not, and can I use this same technique in my own functions to save me from needing to cart around the extra variable of the array's length?

A similar question: http://stackoverflow.com/questions/851958/where-do-malloc-free-store-allocated-sizes-and-addresses (though I'd say it's not quite duplicate) — John Carter, Oct 05 '09 at 11:34
The [buddy system](http://en.wikipedia.org/wiki/Buddy_memory_allocation) is another way to do it that can figure out based on the pointer, without overhead in each block. — EvilTeach, Mar 09 '14 at 16:34
This post explains it well: http://stackoverflow.com/questions/1957099/how-do-free-and-malloc-work-in-c — Zeeshan, Dec 02 '16 at 07:23

score 455 · Accepted Answer · edited Jun 18 '14 at 06:32

455

When you call malloc(), you specify the amount of memory to allocate. The amount of memory actually used is slightly more than this, and includes extra information that records (at least) how big the block is. You can't (reliably) access that other information - and nor should you :-).

When you call free(), it simply looks at the extra information to find out how big the block is.

edited Jun 18 '14 at 06:32

inspector-g

4,146
2
24
33

answered Oct 05 '09 at 07:49

Gary McGill

26,400
25
118
202

58

FYI, for example BSD has `malloc_size()` to reliably access the block size from an `malloc()`ed pointer. But there's no reliable, portable way. – laalto Oct 05 '09 at 07:53
71

I think it's important to say that this extra information block is situated before the returned pointer. – Georg Schölly Oct 05 '09 at 08:28
51

@gs Well that's implementation-dependent. But, yes, that's where it usually is. – Falaina Oct 05 '09 at 11:20
so if you `malloc`'d two pieces of memory, and overwrote the first one, the second block would be un-`free`-able? – Carson Myers Oct 05 '09 at 19:58
8

@Carson: No, of course `malloc` will not overlap data required for its own memory management with memory that the user has requested. However, if you write beyond the boundaries of what you have requested from `malloc`, you may scribble over memory that doesn't "belong" to you and cause mysterious future failures. – ephemient Oct 06 '09 at 02:00
47

Can you imagine the horror if `free()` required the programmer to accurately report how big the `malloc()` block was? The memory leaks are bad enough as it is. – MusiGenesis Apr 07 '10 at 13:45
5

The `malloc` cannot hold, it is too late. – detly Jun 21 '10 at 08:17
63

Why is that information available to `malloc()` and `free()`, but you have to store the size of an array? Why wouldn't they make it possible to do something like `blockSize(ptr)` if they're storing the information anyway? – corsiKa Jun 14 '14 at 01:12
1

@MusiGenesis You may be interested in [this new question](http://stackoverflow.com/questions/24203940/why-does-free-in-c-not-take-the-number-of-bytes-to-be-freed) ;) – Bob Jun 14 '14 at 15:45
2

How is free() able to look up the header information? does it get the address of the pointer, subtract header size from it and cast that header size address to the header object and access the required information related to size? – bsobaid Dec 14 '14 at 22:13
6

@bsobaid: *probably*, yes - but it's implementation-dependent. The code for `malloc` and `free` obviously need to be in sync, so that `free` looks for the information wherever `malloc` stores it. In theory, the information could be anywhere (not necessarily adjacent to the allocated memory). – Gary McGill Dec 15 '14 at 09:31
@MusiGenesis: Having `malloc` record the information about allocation will be more efficient than requiring the application store it, in cases where the application would otherwise neither know nor care about the allocation size. Requiring the application to tell `free` how big the allocated block was would allow more efficient malloc/free in some cases [e.g. if allocations are aligned on 16-byte boundaries, requiring malloc to store the size could double the cost of small allocations]. Each approach is better in different circumstances. – supercat Feb 25 '15 at 20:21
So, this "extra information" is not stored with the pointer but at the beginning (or end?) of the allocated block? – Geremia Feb 05 '16 at 02:37
4

@Geremia: It could well be that often required sizes have their own memory pools, and the address passed in is enough for the memory manager to know from which pool a memory block was returned, and therefore which size it is. Whether this is done that way, or if blocks are part of some kind of linked list with "free" flags, or if such info is stored elsewhere, is all implementation dependent. – Rudy Velthuis Jul 31 '16 at 04:32
3

then why compiler vendors/language standard or O/S vendors unable to provide a functionality to get the number of elements which were dynamically allocated with related array name,since as you already mentioned it's maintaining `big block` to hold that record,why they couldn't extract data and provide to us? here number of elements... because it has already been recorded w.r.t array alias I think. – Buddhika Chaturanga Jan 19 '18 at 12:52
@Icebone1000 If its position is implementation dependent, the property of alignedness is impl.dep. as well. – glglgl Nov 16 '18 at 10:55
5

This is a non answer. The question is exactly this: why can free reliably look up the size of the block, but yet there is no function available to the programmer that does that? – Bananach Jan 04 '19 at 11:51
1

I've collected a lot of information about this and, so far, the only answer I found is that there is no answer – Christian Vincenzo Traina Jan 15 '21 at 16:48
@MusiGenesis: That's how it used to work. There was no `free` there was only `mfree` for which you had to tell it how much. But having `malloc` and the new `free` be in cahoots was so much better nobody looked back. – Joshua Mar 29 '21 at 19:46
1

@GeorgSchölly On MacOS / iOS the block size hasn't been stored near the pointer for a long time. Instead the OS uses one 4K block to store malloc blocks up to 16 bytes, one 4K block for malloc blocks up to 32 bytes, and so on. So you know the size of the malloc block from the block that contains it. Allocating / deallocating is just setting a single bit. This makes it easy to have all the malloc blocks nicely aligned, and the size information doesn't pollute your caches. – gnasher729 Mar 28 '23 at 12:02

paxdiablo · Answer 2 · 2016-02-17T02:00:59.103

Most implementations of C memory allocation functions will store accounting information for each block, either in-line or separately.

One typical way (in-line) is to actually allocate both a header and the memory you asked for, padded out to some minimum size. So for example, if you asked for 20 bytes, the system may allocate a 48-byte block:

16-byte header containing size, special marker, checksum, pointers to next/previous block and so on.
32 bytes data area (your 20 bytes padded out to a multiple of 16).

The address then given to you is the address of the data area. Then, when you free the block, free will simply take the address you give it and, assuming you haven't stuffed up that address or the memory around it, check the accounting information immediately before it. Graphically, that would be along the lines of:

 ____ The allocated block ____
/                             \
+--------+--------------------+
| Header | Your data area ... |
+--------+--------------------+
          ^
          |
          +-- The address you are given

Keep in mind the size of the header and the padding are totally implementation defined (actually, the entire thing is implementation-defined ^(a) but the in-line accounting option is a common one).

The checksums and special markers that exist in the accounting information are often the cause of errors like "Memory arena corrupted" or "Double free" if you overwrite them or free them twice.

The padding (to make allocation more efficient) is why you can sometimes write a little bit beyond the end of your requested space without causing problems (still, don't do that, it's undefined behaviour and, just because it works sometimes, doesn't mean it's okay to do it).

^(a) I've written implementations of malloc in embedded systems where you got 128 bytes no matter what you asked for (that was the size of the largest structure in the system), assuming you asked for 128 bytes or less (requests for more would be met with a NULL return value). A very simple bit-mask (i.e., not in-line) was used to decide whether a 128-byte chunk was allocated or not.

Others I've developed had different pools for 16-byte chunks, 64-bytes chunks, 256-byte chunks and 1K chunks, again using a bit-mask to decide what blocks were used or available.

Both these options managed to reduce the overhead of the accounting information and to increase the speed of malloc and free (no need to coalesce adjacent blocks when freeing), particularly important in the environment we were working in.

@paxdiablo Does that mean malloc doesn't allocate contiguous blocks of memory? — user10678, Nov 05 '17 at 08:20
@user10678, the only real requirement of `malloc` is that it give you, for the successful case, a block of memory at least as large as what you asked for. Individual blocks are contiguous in terms of how you access elements within them, but there's no requirement that the arenas the blocks come from are contiguous. — paxdiablo, Nov 05 '17 at 08:29
Related question: Why is there no variation of malloc/free, where you specify the size when freeing and so it doesn't have to store the size? — user253751, Dec 04 '19 at 14:57
@user253751, because then theer's one *more* thing you need to keep track of, over and above the pointer itself. It's both unnecessary *and* dangerous: `void *x = malloc(200); free(x, 500);` is *not* going to end well :-) In any case, for efficiency, the *actual* size of the buffer may be larger (you just can't rely on this). — paxdiablo, Dec 05 '19 at 02:30
Is the implementation of free directly in the exe files of compilers? I am asking especially in embded systems like avr-gcc. Or can I find it somewhere in the libraries? — Gen0me, Sep 13 '21 at 09:42
Much better to let the system remember the size than relying on the developer. It would be impossible to check that the right size is passed to free(). — gnasher729, Jul 08 '23 at 06:59

jdehaan · Answer 3 · 2009-10-21T10:47:56.073

52

From the comp.lang.c FAQ list: How does free know how many bytes to free?

The malloc/free implementation remembers the size of each block as it is allocated, so it is not necessary to remind it of the size when freeing. (Typically, the size is stored adjacent to the allocated block, which is why things usually break badly if the bounds of the allocated block are even slightly overstepped)

edited Oct 21 '09 at 10:47

answered Oct 05 '09 at 07:53

jdehaan

19,700
6
57
97

8

This is a non answer. The question is exactly this: why can free reliably look up the size of the block, but yet there is no function available to the programmer that does that? – Bananach Jan 04 '19 at 11:54
This is indeed an implementation detail for the malloc api and there is no api to get this info back in a standard way (to my knowledge). The "system" records it and uses that on `free`. Maybe the answer is not satisfying you but I do not think you'll get one with more generically applicable info :-) – jdehaan Jan 20 '19 at 18:32

score 9 · Answer 4 · edited May 23 '17 at 12:10

This answer is relocated from How does free() know how much memory to deallocate? where I was abrubtly prevented from answering by an apparent duplicate question. This answer then should be relevant to this duplicate:

For the case of malloc, the heap allocator stores a mapping of the original returned pointer, to relevant details needed for freeing the memory later. This typically involves storing the size of the memory region in whatever form relevant to the allocator in use, for example raw size, or a node in a binary tree used to track allocations, or a count of memory "units" in use.

free will not fail if you "rename" the pointer, or duplicate it in any way. It is not however reference counted, and only the first free will be correct. Additional frees are "double free" errors.

Attempting to free any pointer with a value different to those returned by previous mallocs, and as yet unfreed is an error. It is not possible to partially free memory regions returned from malloc.

I changed the value of a pointer returned by a malloc call. And I freed it without an error. Why? See here:http://stackoverflow.com/questions/42618390/how-does-the-free-function-know-the-memory-size-to-free — smwikipedia, Mar 06 '17 at 06:03

score 4 · Answer 5 · answered Oct 05 '09 at 08:07

4

On a related note GLib library has memory allocation functions which do not save implicit size - and then you just pass the size parameter to free. This can eliminate part of the overhead.

answered Oct 05 '09 at 08:07

EFraim

12,811
4
46
62

score 3 · Answer 6 · answered Oct 05 '09 at 07:48

3

The heap manager stored the amount of memory belonging to the allocated block somewhere when you called malloc.

I never implemented one myself, but I guess the memory right in front of the allocated block might contain the meta information.

answered Oct 05 '09 at 07:48

Timbo

27,472
11
50
75

5

That's one possible implementation, but one could devise a system where all memory is tracked in a single table in a totally different page, not necessarily anywhere close to the memory pool being allocated from. – ephemient Oct 06 '09 at 02:01

score 3 · Answer 7 · answered May 03 '13 at 20:38

The original technique was to allocate a slightly larger block and store the size at the beginning, then give the application the rest of the blog. The extra space holds a size and possibly links to thread the free blocks together for reuse.

There are certain issues with those tricks, however, such as poor cache and memory management behavior. Using memory right in the block tends to page things in unnecessarily and it also creates dirty pages which complicate sharing and copy-on-write.

So a more advanced technique is to keep a separate directory. Exotic approaches have also been developed where areas of memory use the same power-of-two sizes.

In general, the answer is: a separate data structure is allocated to keep state.

Typically on MacOS you have large blocks for 16 byte mallocs, for 32 byte mallocs, for 48 byte mallocs etc. For malloc/free you just set or clear a single bit for each block. Very cache friendly because the bits for say 128 malloc blocks are all in a single cache line. — gnasher729, Jul 08 '23 at 07:03

score 2 · Answer 8 · edited May 23 '17 at 12:18

2

malloc() and free() are system/compiler dependent so it's hard to give a specific answer.

More information on this other question.

edited May 23 '17 at 12:18

Community

1
1

answered Oct 05 '09 at 07:49

LiraNuna

64,916
15
117
140

2

They're really library-dependent (typically the C library, which is usually very closely linked to the OS). To the compiler, they're just functions. – Donal Fellows Jun 21 '10 at 08:19

score 2 · Answer 9 · answered Oct 05 '09 at 08:02

2

To answer the second half of your question: yes, you can, and a fairly common pattern in C is the following:

typedef struct {
    size_t numElements
    int elements[1]; /* but enough space malloced for numElements at runtime */
} IntArray_t;

#define SIZE 10
IntArray_t* myArray = malloc(sizeof(intArray_t) + SIZE * sizeof(int));
myArray->numElements = SIZE;

answered Oct 05 '09 at 08:02

MSalters

173,980
10
155
350

That's a completely different technique to the one BSD malloc uses for small objects ( though it's a perfectly good technique for creating Pascal style arrays ) – Pete Kirkham Oct 05 '09 at 16:34

score 1 · Answer 10 · answered Apr 10 '20 at 10:32

1

to answer the second question, yes you could (kind of) use the same technique as malloc() by simply assigning the first cell inside every array to the size of the array. that lets you send the array without sending an additional size argument.

answered Apr 10 '20 at 10:32

avish

48
6

score 0 · Answer 11 · answered Jun 18 '13 at 16:15

When we call malloc it's simply consume more byte from it's requirement. This more byte consumption contain information like check sum,size and other additional information. When we call free at that time it directly go to that additional information where it's find the address and also find how much block will be free.

How does free know how much to free?

11 Answers11

Linked

Related