Handwritten memory pool and principle code analysis [C language]

Memory pool is to manage the heap

When the process executes , The operating system will separate 0~4G Virtual memory space for the process , Programmers can manage （ Distribute 、 Release ） The most important part is mmap Mapping area 、heap Heap area , The part of memory pool management is the heap of user processes .

Why use a memory pool ？

Memory pool is used to avoid fragmentation of heap area

• Avoid frequently allocating and freeing memory （ Prevent fragmentation in the heap area ）

When the client connects to the server , The server will prepare part of the heap for message retention . When a connection succeeds , The server will allocate a section of memory belonging to this connection in the heap , When the connection is closed , The allocated memory is also released . But when the number of connections is large and too frequent , Inevitably, memory is allocated and released frequently . This will cause small windows in the heap area , That is, heap fragmentation .

What happens if there is fragmentation in the heap area ？

• Working for a long time will lead to undetectable BUG

• Unable to allocate large and whole block of memory ,malloc Returns the NULL

Memory pool design

scene ： In a very clean pile area , How to implement a memory pool that can avoid memory fragmentation ？

First of all ： Use linked list to manage memory

Use the linked list to connect the allocated memory in the heap area one by one , Set up flag( Is it used ), Let each segment of memory on the linked list node expand slowly .

What problems will occur when using the linked list alone ？

• Memory blocks will be divided smaller and smaller , The linked list will become longer and longer , Know you can't partition out much more memory .

So the design with the idea of fixed memory

For allocating small segments of memory , Divide small segments of memory into fixed segments , as follows

1. 16bytes

2. 32bytes

3. 64bytes

4. 128bytes

5. 256byts

6. 512bytes

However, different fixed small memory allocation will lead to the following problems :

1. Search slow

Find when allocating

Find when releasing

2. There will also be gaps between blocks

Cannot merge blocks

It's troublesome to recycle small pieces

So finally, we get the memory pool model of custom fixed block and random block

Memory pool

Memory pool workflow

​

Memory pool structure

// Memory pool 
struct mp_pool_s{

	size_t max;					
	
	struct mp_node_s *current;		// The small memory area currently pointed to , Chain table structure 
	struct mp_large_s *large; 		// Big memory 

	struct mp_node_s *head[0];		// The head of a small piece of memory 
};

Small pieces of memory are linked by a one-way linked list

// Small memory 
struct mp_node_s{

	unsigned char *last;    // Current 
	unsigned char *end;   // Last 

	struct mp_node_s *next; // next 4k
	size_t failed;
	
};

Large blocks of memory are also linked by one-way linked lists

// Big memory 
struct mp_large_s{

	struct mp_large_s *next;
	void *alloc;
	
};

​API

Create a memory pool

1. Make sure to size Size is the fixed size of small memory

2. One is last Point to the first byte of the node

3. end Point to the last

// Create a memory pool 
struct mp_pool_s *mp_create_pool(int size){
	
	struct mp_pool_s *pool;
	
	int ret = posix_memalign((void**)&pool, ALIGNMENT, size + sizeof(struct mp_pool_s) + sizeof(struct mp_node_s));
	if(ret)return NULL;

	pool->max = (size<MP_MAX_ALLOC_FORM_POOL) ? size : MP_MAX_ALLOC_FORM_POOL;
	
	pool->current = pool->head;
	
	pool->head->last = (unsigned char*)pool + sizeof(struct mp_pool_s) + sizeof(struct mp_node_s);
	pool->head->end = pool->head->last + size;
	pool->head->failed = 0;
	
	pool->large = NULL;

	return pool;
}

Destroy the memory pool

1. Free a large block of memory first , Traversing the linked list

2. Then release the small pieces , Traversing the linked list

// Destroy the memory pool 
void mp_destroy_pool(struct mp_pool_s *pool){
	
	struct mp_large_s *large;
	
	for(large = pool->large; large!=NULL; large = large->next){ // Release chunk 
		if(large->alloc)free(large->alloc);
	}
	
	struct mp_node_s *h = pool->head->next;
	
	while(h){	// Release small pieces 
		struct mp_pool_s *next = h->next;
		free(h);
		h = h->next;
	}

	free(pool);
}

Reset memory pool

1. Free a large block of memory first

2. Then put a small piece of memory last Point to the first location of memory

// Reset memory pool 
void mp_reset_pool(struct mp_pool_s *pool){

	struct mp_node_s *head;
	struct mp_large_s *large;

	for(large = pool->large; large; large=large->next){ // Will release large chunks 
		if(large->alloc)free(large->alloc);
	}

	pool->large = NULL;

	for(head = pool->head; head; head = head->next){	// Point the head position of each node to the position just created 
		head->last = (unsigned char*)head + sizeof(struct mp_node_s);
	}
}

Allocate a small amount of memory to the memory pool

1. First allocate a whole block （ The size is psize） Small memory , And create a node to point to this memory

2. Memory alignment , Use the tail insertion method to insert the last position of the linked list

3. Readjust the memory pool current The direction of

/* Distribute psize Small chunks of memory , Where to start pointing head->last = memblk + size, List tail insertion method */
static void *mp_alloc_block(struct mp_pool_s *pool, size_t size){

	unsigned char *memblk;
	struct mp_node_s *head = pool->head;
	size_t psize = (size_t)(head->end - (unsigned char*)head);  //psize ==  Parameters entered when creating memory pool 
	
	int ret = posix_memalign((void*)&memblk, ALIGNMENT, psize);  // Allocate memory      24 Byte alignment 
	if(ret)return NULL;

	struct mp_node_s *p, *new_node, *current;
	new_node = (struct mp_node_s*)memblk;

	new_node->end = memblk + psize;
	new_node->next = NULL;
	new_node->failed = 0;

	memblk += sizeof(struct mp_node_s); 				// Skip node structure for memory alignment 
	memblk = mp_align_ptr(memblk, ALIGNMENT);			// Memory alignment 
	new_node->last = memblk + size;

	current = pool->current;

	for(p = current; p->next; p = p->next){ 			// The tail interpolation 
		if(p->failed++>4)current = p->next;
	}

	p->next = new_node;							

	pool->current = current ? current : new_node;

	return memblk;
}

Take out a piece of memory size Size of memory （ No byte alignment ）

1. First, get the small block of memory pointed to by the current memory pool

2. Follow one node by one to find out whether there is enough memory in the small memory size Size of memory allocation

3. If so, byte align the memory and return

4. If there is no suitable small block of memory, allocate an extra small block of memory

5. If the small memory allocation fails , To create a large block of memory size Distribute

// Take a block from a small memory area size Size of memory 
void *mp_nalloc(struct mp_pool_s *pool, size_t size){

	unsigned char *m;
	struct mp_node_s  *p;

	if(size<=pool->max){
		p = pool->current;  // The current block points to 

		do{
			m = p->last;		
			if((size_t)(p->end - m)>=size){ // If the remaining memory ratio of the current node size If it is large, it will be allocated at this node 
				p->last = m + size;
				return m;
			}
			p = p->last;
			// If the remaining size of no section is greater than size Just reassign one block
		}while(p);

		return mp_alloc_block(pool, size);
	}
	// If this size Exceeded the limit of small memory , It is distributed in the way of large block content distribution 
	return mp_alloc_large(pool, size);
}

Take out a piece of memory size Size of memory （ Do byte alignment ）

// Take a block from a small memory area size Size of memory    Byte alignment 
void *mp_alloc(struct mp_pool_s *pool, size_t size){

	unsigned char *memblk;
	struct mp_pool_s *p;

	if(size<=pool->max){
		p = pool->current; 		// The current block points to 

		do{
			memblk = mp_align_ptr(p->last, ALIGNMENT);// Do byte alignment 
			if((size_t)(p->end-memblk) >= size){  // If the remaining memory ratio of the current node size If it is large, it will be allocated at this node 
				p->last = memblk + size;
				return memblk;
			}
			p = p->next;			
		}while(p);
		// If the remaining size of no section is greater than size Just reassign one block
		return mp_alloc_block(pool, size);
	}
	// If this size Exceeded the limit of small memory , It is distributed in the way of large block content distribution 
	return mp_alloc_large(pool, size);
}

Take out a piece of memory size Size of memory and initialize to 0

// Allocate memory and initialize to 0
void *mp_calloc(struct mp_pool_s *pool, size_t size){

	void *p = mp_alloc(pool, size);
	if(p){
		memset(p, 0 , size);
	}
	return p;
}

Distribute size Large chunks of memory （ Large memory nodes are placed in small memory ）

1. First malloc Get the first memory address , Then hang the large memory on the memory pool , If the structure of large memory is not created, it will be created in small memory

2. After creation, hook up and return the first address of large memory

// Create large blocks of memory 
static void *mp_alloc_large(struct mp_pool_s *pool, size_t size){

	void *p = malloc(size);				// Distribute 
	if(p==NULL)return NULL;

	size_t n = 0;
	struct mp_large_s  *large;
	for(large=pool->large; large; large = large->next){
		if(large->alloc == NULL){  
			large->alloc = p;
			return p;
		}
		if(n++>3)break;
	}

	// The memory is not large 
	large = mp_alloc(pool, sizeof(struct mp_large_s));
	if(large==NULL){
		free(large);
		return NULL;
	}

	large->alloc = p;
	large->next = pool->large;
	pool->large = large;

	return p;
}

Free a specified chunk of memory p

• Find and then release

// Free memory p
void mp_free(struct mp_pool_s *pool, void *p){

	struct mp_large_s * large;
	for(large = pool->large; large; large = large->next){

		if(p==large->alloc){
			free(large->alloc);
			large->alloc = NULL;	
			return;
		}
	}

heavy load posix_memalign

// restructure mem_memalign
void *mp_memalign(struct mp_pool_s *pool, size_t size, size_t alignment){

	void *p;

	int ret = posix_memalign(&p, alignment, size);
	if(ret){
		return NULL;
	}

	struct mp_large_s *large = mp_alloc(pool, sizeof(struct mp_large_s ));
	if(ret)return NULL;

	struct mp_large_s *large = mp_alloc(pool, sizeof(struct mp_large_s));
	if(large==NULL){
		free(p);
		return NULL;
	}

	large->alloc = p;
	large->next = pool->large;
	pool->large = large;

	return p;
}

Memory alignment formula

#define MP_ALIGNMENT       		32
#define MP_PAGE_SIZE			4096
#define MP_MAX_ALLOC_FROM_POOL	(MP_PAGE_SIZE-1)

#define mp_align(n, alignment) (((n)+(alignment-1)) & ~(alignment-1))
#define mp_align_ptr(p, alignment) (void *)((((size_t)p)+(alignment-1)) & ~(alignment-1))

thus , All the contents of the memory pool are here

Recommend to see nginx The memory pool of , Of this memory pool demo and nginx It's very similar