I have a question regarding the free(ptr) function and how it deallocates memory. From my understanding, malloc, calloc, and realloc are used to dynamically allocate memory, and free(ptr) is used to release that memory once it is no longer needed. I am interested in understanding how free(ptr) manages to deallocate the memory, However, I would appreciate a more detailed explanation of the actual process behind free(ptr)

#include<stdio.h>
#include<stdlib.h>

int main()
{
    // Allocate memory for an integer array of size 5
    int *ptr = malloc(5 * sizeof(ptr));

    // Check if memory allocation was successful
    if (ptr != NULL)
    {
        // Assign values to the elements of the allocated array
        ptr[0] = 10;
        ptr[1] = 20;
        ptr[2] = 30;
        ptr[3] = 40;
        ptr[4] = 50;
    }

    // Free the dynamically allocated memory
    free(ptr);

    // Return 0 to indicate successful execution
    return 0;
}

 

There are many possible ways to do this, but they all boil down to creating and managing a list of free blocks of memory. When memory is allocated, you get a pointer to the beginning of a block. When that pointer is used to free a block, that block goes back on the list of free blocks. So, at any point in time the list allows you to determine which blocks of memory have been allocated and which blocks are free. The other thing you should research is the process known as garbage collection; it may provide some insight on your original question.

Garbage collection (computer science) - Wikipedia

 

As @Papabravo says, there are several ways to do this and how it is done is NOT part of the C language specification -- the implementer of the compiler provides function such as malloc() and free() that exhibit language-defined behaviors, but how those behaviors work is completely up to them.

A common way of doing this is to use a linked-list where each block of memory contains information, usually prepended to the block, that specifies how big the block is. This also contains space to store a pointer to the next (and possibly previous) block of free memory when it is deallocated.

If you work your way through the Nand-2-Tetris project, you will have a good idea of one way to implement a memory manager because you will write it.

 

As @Papabravo says, there are several ways to do this and how it is done is NOT part of the C language specification -- the implementer of the compiler provides function such as malloc() and free() that exhibit language-defined behaviors, but how those behaviors work is completely up to them.

A common way of doing this is to use a linked-list where each block of memory contains information, usually prepended to the block, that specifies how big the block is. This also contains space to store a pointer to the next (and possibly previous) block of free memory when it is deallocated.

If you work your way through the Nand-2-Tetris project, you will have a good idea of one way to implement a memory manager because you will write it.

The actual choice of a "list" implementation has enormous implications concerning which operations are fast and efficient and which ones are less so. There is also a tradeoff between how much overhead space is required to maintain the list and how much time it takes to do garbage collection to avoid the problem of having lots of small blocks of unusable memory. This is not a sandbox for beginners, you can look but you should probably avoid the temptation to touch.

 

Another completely different way to do it to use a bit map.

The bit map has 1 bit for each unit of memory. The size of the unit could be anything. 32 bits (4 bytes) would be a reasonable compromise size on most architectures.

So you start with the bit map all zeros. When you do a malloc, the code looks through the bitmap for the first string of zeros long enough for the allocation. For example, if you malloc(16) then we need 16 / 4, or 4 consecutive free blocks. So the code looks for the first 4 consecutive zeros in the bitmap. It then translates that offset to the address of the corresponding memory, and sets the 4 bits to 1.

A free would locate the 4 bits from the address and set them back to zero.

Actually, it is a little more complicated, because free has to know the size of the block. One way to do that is to always allocate 1 extra 32-bit unit and store the length of the block in that word. So, in ,my previous example, you would reserve 5 units and set five bits when the malloc(16) was done.

The linked list scheme is typically preferred because scanning a bit map to find free blocks would be less efficient for a large amount of memory.

 

One of the biggest drawbacks of table-based approaches (which include bitmaps) are the memory requirements for the table. If the program has a 32-bit address space, that's 4 GB of memory. In the case of a bitmap approach, if it is allocated in 4 B chunks, then that 1 Gchunks. With one bit per chunk in the map, that's 128 MB just for the map. In fact, with 4 B chunks, your map is going to consume at least 1/32 (~3%) of your available memory. Not very appealing. You would have to go to much larger chunks to get that to something more reasonable, But larger chunks mean less granularity and the potential for a lot of unusable memory. Aside from that, you are having to do a lot of bit-banging to manipulate the map.

This is not to say that table-based approaches don't have their advantages. Like most things, the fact that there are multiple approaches used means that no single approach has all pros and no cons.

 

Another completely different way to do it to use a bit map.

The bit map has 1 bit for each unit of memory. The size of the unit could be anything. 32 bits (4 bytes) would be a reasonable compromise size on most architectures.

So you start with the bit map all zeros. When you do a malloc, the code looks through the bitmap for the first string of zeros long enough for the allocation. For example, if you malloc(16) then we need 16 / 4, or 4 consecutive free blocks. So the code looks for the first 4 consecutive zeros in the bitmap. It then translates that offset to the address of the corresponding memory, and sets the 4 bits to 1.

A free would locate the 4 bits from the address and set them back to zero.

Actually, it is a little more complicated, because free has to know the size of the block. One way to do that is to always allocate 1 extra 32-bit unit and store the length of the block in that word. So, in ,my previous example, you would reserve 5 units and set five bits when the malloc(16) was done.

The linked list scheme is typically preferred because scanning a bit map to find free blocks would be less efficient for a large amount of memory.

I anticipated this by talking about lists in general as opposed to particular kinds of lists, eg. liked lists. A bit map is after all a rudimentary list – is it not?

 

I anticipated this by talking about lists in general as opposed to particular kinds of lists, eg. liked lists. A bit map is after all a rudimentary list – is it not?

As opposed to loved-lists or despised-lists?

 

As opposed to loved-lists or despised-lists?

Please, not to forget the D-list!

 

Please, not to forget the D-list!

Yep -- completely forget to D-clare that one.

 

I have a question regarding the free(ptr) function and how it deallocates memory. From my understanding, malloc, calloc, and realloc are used to dynamically allocate memory, and free(ptr) is used to release that memory once it is no longer needed. I am interested in understanding how free(ptr) manages to deallocate the memory, However, I would appreciate a more detailed explanation of the actual process behind free(ptr)

#include<stdio.h>
#include<stdlib.h>

int main()
{
    // Allocate memory for an integer array of size 5
    int *ptr = malloc(5 * sizeof(ptr));

    // Check if memory allocation was successful
    if (ptr != NULL)
    {
        // Assign values to the elements of the allocated array
        ptr[0] = 10;
        ptr[1] = 20;
        ptr[2] = 30;
        ptr[3] = 40;
        ptr[4] = 50;
    }

    // Free the dynamically allocated memory
    free(ptr);

    // Return 0 to indicate successful execution
    return 0;
}

I've had the pleasure of designing a heap manager, a concurrent 64-bit heap manger that we used on Windows for special purposes, this was coded in C.

Conceptually you begin by getting an address for a large contiguous block of memory, you have its address and size.

Then you have a basic function CreateHeap that takes that address and overlays a structure on it that represents a heap header, a descriptor that has things like pointer(s) to free list(s), virgin address, free space, first allocation address and so on.

Internally you simply define structures that represent headers, every block we allocate will have a leading header, the caller sees the address of header + header size. The header describes the actual number of bytes in the allocation as well as offsets to the adjacent block before and adjacent block after, it also contains a status (FREE or BUSY).

When a block is freed we set its state to FREE and examine the two physically adjacent blocks, if either or both of these are free we basically "merge" them (unthreading each from their respective free list) and end up with a single larger block that we the add to a list of free blocks (the pointer to the start of the list is held in the heap header) if after doing this the final block is found to be adjacent to the virgin space, we effectively increase the virgin size in the header and decrement the virgin ptr accordingly.

When we allocate we scan the list(s) looking for a big enough block, then remove it from the list, tag it as BUSY and return that address to the caller, if we can't find a big enough block we try to allocate from the virgin if that too fails we return NULL.

The heap I had had multiple free lists ordered by size, say 16, 32, 64, 128 that kind of thing. So if the caller wants a block > 32 bytes we don't bother scanning the list for 16 bytes blocks (that list contains blocks 16 thru 31 bytes in size).

The stress test for this was gruelling, we basically loop randomly over an array of pointers, if a slot was NULL we'd allocate from the heap and put the address into that slot, if the slot was not NULL we'd free that address and put NULL back into the slot. The loop allocated random sized blocks and when the heap was full the code would iterate the array and free everything that was still allocated and the order it would do that was also random.

At the end of the test the heap header had to be identical to what it was before the start of the test, if it was not we knew we had a bug.

I've wanted to rewrite this entirely in C# but there's still a final bug in .Net that they haven't yet fixed.