why size is not provided in free statement

Question

Possible Duplicate:
C programming : How does free know how much to free?

Hello All,

How OS will come to know how much size i have to free when we define free(pointer). I mean we are not providing any size , only pointer to free statement. How's internally handle the size ?

Thanks, Neel

Answer 1

The OS won't have a clue, as free is not a system call. However, your C libraries memory allocation system will have recorded the size in some way when the memory was originally allocated by malloc(), so it knows how much to free.

Answer 2

The size is stored internally in the allocator, and the pointer you pass to free is used to reach that data. A very basic approach is to store the size 4 bytes before the pointer, so substracting 4 from the pointer gives you a pointer to it's size.

Notice that the OS doesn't handle this directly, it's implemented by your C/C++ runtime allocator.

Answer 3

When you call malloc, the C library will automatically carve a space out for you on the heap. Because things created on the heap are created dynamically, what is on the heap at any given point in time is not known as it is for the stack. So the library will keep track of all the memory that you have allocated on the heap.

At some point your heap might look like this:

              p---+
                  V
    ---------------------------------------
... |  used (4) | used (10) | used (8)    | ...
    ---------------------------------------

The library will keep track of how much memory is allocated for each block. In this case, the pointer p points to the start of the middle block.

If we do the following call:

free(p);

then the library will free this space for you on the heap, like so...

              p---+
                  V
    ----------------------------------------
... |  used (4) | unused(10) | used (8)    | ...
    ---------------------------------------- 

Now, the next time that you are looking for some space, say with a call like:

void* ptr = malloc(10);

The newly unused space may be allocated to your program again, which will allow us to reduce the overall amount of memory our program uses.

            ptr---+
                  V
    ----------------------------------------
...  |  used (4) | used(10) | used (8)    | ...
    ---------------------------------------- 

The way your library might handle internally managing the sizes is different. A simple way to implement this, would be to just add an additional amount of bytes (we'll say 1 for the example) at the beginning of each block allocated to hold the size of each block. So our previous block of heap memory would look like this:

bytes: 1   4    1    10   1   8
     --------------------------------
 ...  |4| used |10| used |8| used | ...
     -------------------------------- 
                   ^
                   +---ptr

Now, if we say that block sizes will be rounded up to be divisible by 2, they we have an extra bit at the end of the size (because we can always assume it to be 0, which we can conveniently use to check whether the corresponding block is used or unused.

When we pass a pointer in free:

free(ptr);

The library would move the pointer given back one byte, and change the used/unused bit to unused. In this specific case, we don't even have to actually know the size of the block in order to free it. It only becomes an issue when we try to reallocate the same amount of data. Then, the malloc call would go down the line, checking to see if the next block was free. If it is free, then if it is the right size that block will be returned back to the user, otherwise a new block will be cut at the end of the heap, and more space allocated from the OS if necessary.