Malloc/free implementation

malloc/free implementation

Chunk

The basic unit of the C standard library when managing the allocated heap is chunk, chunk is just a logical concept, its data structure is as follows: Br>

struct malloc_chunk {

size_t prev_size;

size_t size;

struct malloc_chunk* fd;

struct malloc_chunk* bk;

struct malloc_chunk* fd_nextsize;

struct malloc_chunk* bk_nextsize;

};

If a chunk is free, then its fd and bk constitute A double-linked list that records the memory that has been freed by the user, so that it can be directly allocated or merged into a large free block from later on. If a chunk has been alloced, then from the size is the user's data, that is, fd, bk, etc. have no meaning, this is not difficult to see from the comments.

When a chunk is allocated, the size records the size of the memory actually allocated to the user program in the chunk, which is the value of the parameter when we call malloc, and the prev_size record is adjacent to the current chunk. The size of the previous chunk. The reason for this design is that you can quickly locate/merge adjacent chunks. For example, if the current chunk address is char *p, the addresses of the upper/next chunks are pp->prev_size and p+p->size Under the simple analysis, the following two macros can be seen at a glance:

(1) Get the user pointer from the chunk (here SIZE_SZ is sizeof(size_t))

#define chunk2mem(p) (( Void_t*)((char*)(p) + 2*SIZE_SZ))

(2) Get the chunk address from the user pointer

#define mem2chunk(mem) ((mchunkptr)(( Char*)(mem) - 2*SIZE_SZ))

When allocating memory, the unit of chunk is 8Byte, so the lower 3 bits of size are 0, then it can be used for other purposes. There are two definitions in glibc:

#define PREV_INUSE 0x1

#define IS_MMAPPED 0x2

Here PREV_INUSE records whether the last chunk was used (if assigned) 1), and IS_MMAPPED identifies whether the current chunk is obtained through mmap allocation. The following macros can deepen our understanding of chunks:

//Get the next chunk of the current chunk(p)

#define next_chunk(p) ((mchunkptr)( ((char* )(p)) + ((p)->size & ~PREV_INUSE) ))

//Get the previous chunk of the current chunk(p)

#define prev_chunk(p ) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))

//Check if the current chunk(p) is used, note: inuse of p The bit information is stored in the size of the next adjacent chunk

#define inuse(p) ((((())((())((())((()) ~PREV_INUSE)))->size) & PREV_INUSE)

//Set the current chunk(p) to be used, that is, set the lowest bit of size in the next adjacent chunk to be 1

#define set_inuse(p) ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size