Stack cognition - Introduction to heap

Reference resources ：Linux note – Reactor introduction
Address ：https://qingmu.blog.csdn.net/article/details/119510863

1、 Preface

At present, there are mainly the following heap memory management mechanisms for major platforms ：

platform	Heap management mechanism
dlmalloc	General purpose allocator
ptmalloc2	glibc
jemalloc	FreeBSD and Firefox
tcmalloc	Google
libumem	Solaris

In this article, we mainly talk about Linux in glibc Heap management mechanism .

2、 The origin of the heap

• Linux Heap allocation and recycling in the middle and early stage were carried out by Doug Lea Realization . But when it's dealing with multithreading in parallel , Will share the heap memory space of the process . therefore , For safety reasons , When a thread uses the heap , Will lock .

• However , meanwhile , Locking will prevent other threads from using the heap , Reduce the efficiency of memory allocation and recycling . meanwhile , If multithreading is used , Failed to properly control , It may also cause the correctness of memory allocation and recycling .

• Wolfram Gloger stay Doug Lea It is improved to support multithreading , This heap allocator is ptmalloc. stay glibc-2.3.x. after ,glibc Integration of the ptmalloc2.

1、 Only when you actually visit an address , The system will establish the mapping relationship between virtual pages and physical pages .

2、 So although the operating system has allocated a large piece of memory to the program ,
 But this memory is actually just virtual memory . Only when the user uses the corresponding memory ,
 The system will really allocate physical memory to users .

3、Linux Introduction to zhongdui

• at present Linux The heap allocator used in the standard distribution is glibc Heap allocator in ：ptmalloc2.ptmalloc2 Mainly through malloc/free Function to allocate and free memory blocks .

• It should be noted that , In the process of memory allocation and use ,Linux There is such a basic memory management idea ：

4、 Heap classification

4.1、 Request heap

The memory request of the corresponding user , Request memory from the operating system , And then return it to the user program . meanwhile , In order to maintain the efficiency of memory management , Memory generally allocates a large continuous memory in advance ( This large memory is called top_chunk), Then let the heap manager manage this memory through some algorithm . Only when there is insufficient heap space , The heap manager will interact with the operating system again .

Generally speaking, it is our malloc perhaps new Wait for the operation function of applying for memory .

4.2、 Release pile

Manage the memory released by users . Generally speaking , The memory released by the user is not directly returned to the operating system , Instead, it is managed by the heap manager . The released memory can be used to respond to the user's request for newly applied memory .
Generally speaking, it is our free perhaps delete Wait for the operation function to release memory .

5、 The system call behind memory allocation

• In the function of applying and freeing memory , Whether it's malloc still free function , It is often used , But they are not really functions that interact with the system .

• The system calls behind these functions are mainly (s)brk Function and mmap,unmmap function .

The specific process is shown in the figure below ：

• For heap operations , The operating system provides brk function , We can increase brk To request memory from the operating system .

• At the beginning , The starting address of the heap start_brk And the current end of the heap brk Address to . Depending on whether it's on ALSR（ Address randomization ） When protecting , The specific location of the two will be different .

• Don't open ALSR When protecting ,start_brk as well as brk Will point to data/bss The end of the paragraph .

• Turn on ALSR When protecting ,start_brk as well as brk Will also point to the same location , It's just that this position is data/bss Random offset after the end of the segment .

Please refer to the figure below ：

6、 Heap related data structures

The operation of heap is very complex , So in glibc There must be well-designed internal data structure （ Linked list ） To manage it , The data structures corresponding to the heap are mainly divided into ：

 Macro structure ：
	1、 Contains macro information about the heap , These data structures can be used to index the basic information of the heap 
	2、 Mainly the links between heap blocks 
	
 Microstructure ：
	1、 A block of memory used to handle heap allocation and reclamation 
	2、 Mainly how to deal with the memory blocks in heap allocation and recycling 
	3、malloc & free

7、 Heap of applications

• In the execution of the program , We have malloc The requested memory is called chunk. There is ptmalloc For internal use malloc_chunk Structure to represent . When the program applies chunk By free after , Will be added to the idle management list , This list is called binlist.

• No matter one chunk What's the size of , Is it allocated or released , They all use a unified structure .

• Although they all use the same data structure , But depending on whether they were released , Their forms of expression will be different .

malloc_chunk The concrete form of the paper is as follows ：

struct malloc_chunk
{
    
	INTERNAL_SIZE_T  prev_size;
	INTERNAL_SIZE_T  size;
	struct malloc_chunk *fd;
	struct malloc_chunk *bk;
	struct malloc_chunk *fd_nextsize;
	struct malloc_chunk *bk_nextsize;
}

We have malloc Apply for a piece of 0x100 When you need more memory , There is ptmalloc For internal use malloc_chunk To express , But his size is not 0x100 Size , Plus what we can't do prev_size and size size , It's usually 0x10.

Parameters, ：

size

1、 He is a sign bit 

2、 The lower three bit pairs of this field chunk The size of does not affect , They mean from low to high NON_MAIN_ARENA, Record 
    At present chunk Whether it does not belong to the main thread ,1 Does not belong to ,0 Indicates belonging to .
   
3、IS_MAPPED , Record the current chunk Is there a mmap The distribution of .

4、PREV_INUSE, Record the previous chunk Whether the block is allocated . Generally speaking , Of the first allocated memory block in the heap size Field P position 
    It's all set 1, In order to prevent access to the previous illegal memory . When one chunk Of size Of P Position as 0 when , We can get through pre_size word 
    Get the last paragraph chunk Size and address . It's also convenient for idle chunk A merger between .
   A|M|P

fd,bk

1、chunk When in allocation status , from fd The field starts with user data .chunk Idle , Will be added to the free management list （binlist）, The meaning of its field is to point to the next （ Non physical adjacency ） Idle chunk.

2、bk Point to previous （ Non physical adjacency ） Free chunk

3、 adopt fd and bk You can put your spare chunk Add blocks to free chunk Block linked list for unified management 

fd_nextsize bk_nextsize

1、 Also, only chunk Only when you are free can you use , However, it is used for larger chunk（large chunk）

2、fd_nextsize Point to the previous and current chunk The first free block of unused size , It doesn't contain bin The head pointer of 

3、bk_nextsize Point to the latter and the current chunk The first free block of unused size , contain bin The head pointer of 

4、 Generally free large chunk  stay fd In the traversal order of, it is arranged in order from large to small . This can avoid looking for the right 
  chunk Go through it one by one 

8、 Debugging verification

We use gdb Debug and verify

Debugging C The code is as follows ：

#include<stdio.h>
#include<malloc.h>
#include<unistd.h>
#include<string.h>
int main(){
    
	int size = 0x100;
	void *p = malloc(size);
	void *junk = malloc(size);
	void *q = malloc(size);
	void *r = malloc(size);
	printf("p:0x%x\n",p);
	printf("q:0x%x\n",q);
	printf("r:0x%x\n",r);
	strcpy(p,"aaaaaaaabbbbbbbb");
	strcpy(q,"ccccccccdddddddd");
	strcpy(r,"eeeeeeeeffffffff");
	sleep(0);
	free(p);
	sleep(0);
	free(q);
	sleep(0);
// q = malloc(0x600);
// sleep(0);
	return 0;
}

You can see that after the program is up, there is no heap of any information , We didn't apply either , Let's move on

Let it finish a malloc Walk the , Have a look ：

Here we apply for 0x100 Size , It's really big and small, but 273（0x111）, Because we can't operate prev_size and size Size .

So let's look down , Walk the printf：

We found that printf Heap blocks will also be created , In order to store standard input and standard output , Let's go on down , To give p,q,r After the assignment ：

Heap fd and bk All assigned for what we assigned .

Then we free fall p, Let's take another look at the heap ：

His fd and bk Has been changed , Its value is libc Address in , We are in the q to free fall ：

We will find that q Of bk It has pointed to q The address of this heap , and q This pile fd It becomes p The address of this pile , They were ptmalloc Form a linked list to form bin chain .