How dynamically allocated memory is stored in C

Question

dynamically allocate memory in C using malloc (), and we get a pointer to a location on the heap. now we use free () to free memory by passing the same pointer value as its argument.

Now the question is how free () knows how much can be freed .. given the fact that we can always change the size of the memory block allocated by malloc ().

is there anything related to hash tables here?

Answer 1

The original technique was to select a slightly larger block and keep the size at the beginning, the part that the application did not see. The extra space contains the size and possibly links for streaming free blocks for reuse.

However, there are some problems with these tricks, such as poor cache and memory management. Using memory directly in the block results in a redundant page, and also creates dirty pages that make sharing and copying difficult when recording.

So a more advanced way is to keep a separate directory. Exotic approaches have also been developed in which memory areas use the same power size twice.

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

Answer 2

A typical implementation will store information immediately before the address returned by malloc. This information will include information that realloc or free needs need to know to do their job, but the details of what is stored there are implementation dependent.

Answer 3

The simplest implementation is one of the famous K & RC Bible , p. 186 - 188.

The memory block that we actually get is larger (the structure head or the size of the union head) than we apply. The structure may be as follows:

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

Figure to demonstrate this:

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

 void free(void* ptr) { Header *bp, *p; bp = (Header *)ptr - 1; /* ..... */ /*return the memory to the linked list */ } 

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

 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 lalout memory:

Answer 4

The memory manager uses tables to store additional data based on the pointer, sometimes right in front of the pointer, sometimes elsewhere. With very simple C, the data is most likely pointer-2 or pointer-4 , like int or long . The correct information depends on the compiler.

Answer 5

When we use malloc, the block will receive a reserve, the size of which will be smaller than we requested, and in response to this malloc we will get a pointer to the beginning of this block. AS, I said that the size of this block will be larger than what you need. This extra space will be used to save the actual requested block size, a pointer to the next free block, and some data that checks "if you are trying to access more than the allocated block".

Therefore, whenever we call for free use of the pointer that we want to free, this free will look for additional information specified in the block space, where it receives the final size for release.