How is dynamically allocated memory kept track in C

Question

we allocate memory dynamically in C using malloc() and we receive a pointer to a location in the heap. now we use free() to deallocate the memory, passing the same pointer value as its argumnet.

the Question now is how does free() know how much to deallocate.. considering the fact that we can always resize the memory block allocated by malloc().

is there anything related to Hash Tables here?

score 5 · Answer 1 · answered May 03 '13 at 04:29

A typical implementation will store information just before the address returned by malloc. That information will include the information that realloc or free needs to know to do their work, but the details of what exactly is stored there depends on the implementation.

DigitalRoss · Accepted Answer · 2013-05-03T15:54:32.047

4

The original technique was to allocate a slightly larger block and store the size at the beginning, a part the application didn't see. 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 also create 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.

edited May 03 '13 at 15:54

answered May 03 '13 at 04:40

DigitalRoss

143,651
25
248
329

3

Storing the size at the end would be a hopelessly ineffective strategy. And I don't think of http://en.wikipedia.org/wiki/Buddy_memory_allocation as "exotic". – Jim Balter May 03 '13 at 06:00
Err, heh, I was trying to say something slightly different. Fixed! – DigitalRoss May 03 '13 at 15:55
i have seen similar technique in the Linux kernel with the Kernel memory allocation using the "struct page" stored in the beginning of the allocated memory region and the structure being used to keep state of the memory. – ArunMKumar May 03 '13 at 17:52

prehistoricpenguin · Answer 3 · 2013-05-03T07:46:14.150

A simplist implementation is the one in the famous K&R C Bible,page 186 - 188.

The memory block we get actually is more (a struct head's or a union head's size) than we apply for.The struct may be like this:

typedef long Align;

union header
{
    struct 
    {
        union header* ptr;  // next block
        unsigned size;      // size of this block , times of head size  
    }s;
    Align x;
};

A figure to demonstrate it:

enter image description here

When we call the free function, the behaviour may be like this:

void free(void* ptr)
{
    Header *bp, *p;

    bp = (Header *)ptr - 1;

    /* .....                */
    /*return the memory to the linked list  */
}

In visual studio, we have two models: release version and debug version,we could even use the head to store debug message to make debug easier.The header in debug version is called _CrtMemBlockHeader, the definition is as below :

typedef struct _CrtMemBlockHeader
{
    struct _CrtMemBlockHeader * pBlockHeaderNext;
    struct _CrtMemBlockHeader * pBlockHeaderPrev;
    char *                      szFileName;
    int                         nLine;
    size_t                      nDataSize;
    int                         nBlockUse;
    long                        lRequest;
    unsigned char               gap[nNoMansLandSize];
} _CrtMemBlockHeader;

Then the memory lalout is:

enter image description here

Thanks a lot for bringing that out.. i had the bible and missed that topic completely. Your Description makes Complete Sense — ArunMKumar, May 04 '13 at 12:00

score 1 · Answer 4 · answered May 03 '13 at 04:31

1

A memory manager uses tables to store additional data based on a pointer, sometimes right before the pointer, sometimes elsewhere. With C being very simple, the data is most likely pointer-2 or pointer-4, as int or long type. The correct details depend on the compiler.

answered May 03 '13 at 04:31

Vesper

18,599
6
39
61

2

The details depend on the C library, which is part of the language implementation. The compiler has nothing to do with it. Also, some implementations keep small sized blocks in memory pools that are identified by the address of the memory, so the size isn't kept anywhere for such blocks. – Jim Balter May 03 '13 at 05:56
Oops, actually the size is kept somewhere (and must be) ... it's kept in the data structure that describes the memory pool. – Jim Balter May 03 '13 at 20:51

score 1 · Answer 5 · answered May 03 '13 at 05:45

When we use malloc ,a block will get reserve whose size will be littile more than what we have requested and in return to this malloc we get a pointer to start of this block. AS i told you size of this block will be littile more than what exactly you needed.This extra space will be used to keep actual requested size of block,pointer to next free block and some data which checks "if you trying to access more than allocated block".

So whenever we call free using the pointer we want to deallocate, this free will search for the extra information given in the block space, Where it gets final size to deallocate.

How is dynamically allocated memory kept track in C

5 Answers5