Why use memory pools
Avoid memory fragmentation
Reduce the number of system calls (brk, mmap)
Memory fragmentation
What is it?
Unavailable free memory. These memories are small and discontinuous
Cause
The starting address of memory allocation needs to be a multiple of 4 / 8 / 16 (determined by CPU architecture)
Small pieces of free memory sandwiched between large pieces of memory are not easy to use
Possible problems
-
The server program will become unresponsive after a long cycle or a large number of accesses. After investigating the reasons, it is found that the occupied memory will increase irregularly and abnormally with the increase of the number of requests. If you use valgrind and other tools to find that there is no memory leakage, it may be memory fragments.
-
Memory problems occur when the program runs for several days or even months: for example, malloc returns NULL.
How
Using the open source solution jemalloc / tcmalloc
Implement your own memory pool
Usage scenario
Global memory pool
- The life cycle is when small memory needs to be reclaimed during program operation
- You can use jemalloc / tcmalloc directly
1 connection 1 memory pool
- Short life cycle, small memory does not need to be recycled
- If a connection has only one thread, it does not need to be locked
Issues to consider in designing memory pools
- Slow search speed
- Small memory recycling trouble
- In order to avoid memory fragmentation caused by small memory blocks, the structure definition occupies memory and memory blocks need to be a continuous block of memory.
Memory layout
Code flow chart
code implementation
Following nginx, this paper implements a memory pool based on the scheme of one connection and one memory pool
- Block definition
small_trunk - Block definition
big_trunk - Memory pool definition
mempool - Create memory pool
mempool_create - Destroy memory pool
mempool_destroy - Reset memory pool
mempool_reset - Block allocation
mempool_alloc_trunk - Block allocation
mempool_alloc_big - Block allocation
mempool_alloc_small - Freeing large blocks of memory
mempool_free_trunk
Tail insertion method for small linked list
Head insertion method for large linked list
Large chunks of nodes (excluding data) are located in small chunks of memory
The size of the small memory is determined by the user: mempool_create(size_t size)
Specific code
/*
* Memory pool structure definition
* Create memory pool
* Block allocation
* Block allocation
* Block allocation
* Bulk release
* Destroy memory pool
* Reset memory pool
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define ENABLE_LOG
#define MP_ALIGNMENT 32
#define MP_MAX_SMALL_TRUNK 4096
#define MP_ MIN_ SMALL_ Trunk 16 / / guaranteed big_ The trunk structure is a small block of memory
#define ALIGN_PTR(ptr, align) (void*)(((size_t)(ptr) + ((align) - 1)) & (~((align) - 1)))
/*
* If the pointer is defined as void *, if an arithmetic operation (+ or -) is to be performed, the unit is 1, which is the same as the unsigned char *
* 6.24 Arithmetic on void- and Function-PointersIn GNU C,
* addition and subtraction operations are supported on pointers to void and on pointers to functions.
* This is done by treating the size of a void or of a function as 1.
* A consequence of this is that sizeof is also allowed on void and on function types, and returns 1.
* The option -Wpointer-arith requests a warning if these extensions are used.
*
* It is defined as unsigned char * to know more clearly that the unit is 1
*
* Note that the pointer is a structure pointer, which should be converted to unsigned char for arithmetic operation*
*/
// Small pieces
typedef struct _small_trunk {
unsigned char* last; // Unused memory header address
unsigned char* end; // Unused suffix address
struct _small_trunk* next; // Point to the next piece
size_t failed; // Number of application failures
} small_trunk;
// Chunks
typedef struct _big_trunk {
struct _big_trunk* next; // Point to next block
void* start; // Block header address
} big_trunk;
// Memory pool
typedef struct _mempool {
size_t border; // Size block boundary
small_trunk* cur_small; // Current block
big_trunk* big; // First block
small_trunk first_small[0]; // Point to the first block
} mempool;
void* mempool_alloc_trunk(mempool* pool, size_t size);
mempool* mempool_create(size_t size) {
mempool* pool;
int ret = posix_memalign((void**)&pool, MP_ALIGNMENT, sizeof(mempool) + sizeof(small_trunk) + size);
if (0 != ret) {
return NULL;
}
memset(pool, 0, sizeof(mempool) + sizeof(small_trunk) + size);
pool->border = size > MP_MAX_SMALL_TRUNK ? MP_MAX_SMALL_TRUNK : size;
pool->cur_small = pool->first_small;
pool->big = NULL;
// Align again during allocation. There is no need to align here
// fix bug: not converted to unsigned char *, resulting in error in offset calculation (24x56)
pool->first_small->last = (unsigned char *)pool + sizeof(mempool) + sizeof(small_trunk);
pool->first_small->end = pool->first_small->last + size;
pool->first_small->next = NULL;
pool->first_small->failed = 0;
#if 0
printf("pool:%p\n", pool);
printf("first_small:%p\n", pool->first_small);
printf("last:%p\n", pool->first_small->last);
printf("end:%p\n", pool->first_small->end);
printf("next:%p\n", pool->first_small->next);
printf("failed:%p\n", &pool->first_small->failed);
printf("first_small:%p, &first_small:%p, end:%p, end-first_small:%ld\n",
pool->first_small, &pool->first_small, pool->first_small->end,
pool->first_small->end - (unsigned char*)pool->first_small);
#endif
#ifdef ENABLE_LOG
printf("alloc pool addr:%p, border:%ld\n", pool, pool->border);
#endif
return pool;
}
// Only large memory is released, and the last pointer of small memory is reset
void mempool_reset(mempool* pool) {
big_trunk* cur_big = pool->big;
while (cur_big) {
if (cur_big->start) {
#ifdef ENABLE_LOG
printf("free big trunk addr:%p\n", cur_big->start);
#endif
free(cur_big->start);
cur_big->start = NULL;
}
cur_big = cur_big->next;
}
pool->big = NULL;
small_trunk* cur_small = pool->first_small;
while (cur_small) {
cur_small->last = (unsigned char*)cur_small + sizeof(small_trunk);
cur_small->failed = 0;
cur_small = cur_small->next;
}
}
// The large structure is located on the small block. Release the large block first and then the small block
void mempool_destroy(mempool* pool) {
big_trunk* cur_big = pool->big;
while (cur_big) {
#ifdef ENABLE_LOG
printf("free big trunk addr:%p\n", cur_big->start);
#endif
free(cur_big->start);
cur_big->start = NULL;
cur_big = cur_big->next;
}
small_trunk* cur_small = pool->first_small->next;
small_trunk* next_small;
while (cur_small) {
next_small = cur_small->next;
#ifdef ENABLE_LOG
printf("free small trunk addr:%p\n", cur_small);
#endif
free(cur_small);
cur_small = next_small;
}
#ifdef ENABLE_LOG
printf("free pool addr:%p\n", pool);
#endif
free(pool);
}
/*
* Allocate small structures and memory
* Insert the new block into the tail of the block linked list (tail insertion method)
* If the current block fails more than 4 times, point the current block pointer of the memory pool to the next block
* Returns the value trunk after the unused memory start address alignment_ last
*/
static void* mempool_alloc_small(mempool* pool, size_t size) {
small_trunk* new_trunk;
size_t trunk_size = pool->first_small->end - (unsigned char*)pool->first_small;
int ret = posix_memalign((void**)&new_trunk, MP_ALIGNMENT, trunk_size);
if (0 != ret) {
return NULL;
}
#ifdef ENABLE_LOG
printf("alloc small trunk addr:%p\n", new_trunk);
#endif
memset(new_trunk, 0, trunk_size);
unsigned char* trunk_start = (unsigned char*)new_trunk + sizeof(small_trunk);
unsigned char* trunk_last = ALIGN_PTR(trunk_start, MP_ALIGNMENT);
new_trunk->last = trunk_last + size;
new_trunk->end = (unsigned char*)new_trunk + trunk_size;
new_trunk->next = NULL;
new_trunk->failed = 0;
small_trunk* it;
small_trunk* cur_small = pool->cur_small;
for (it = pool->first_small; it->next; it = it->next) {
if (++it->failed > 4) {
cur_small = it->next;
}
}
it->next = new_trunk;
pool->cur_small = cur_small ? cur_small : new_trunk;
return trunk_last;
}
/*
* Allocate large blocks of memory
* Judge whether the large linked list has unused nodes. If yes, bind the large memory to the node
* If not, allocate a large node, bind a large memory, and insert the large node into the header of the large linked list (header insertion method)
* Return the first address ret of large memory
*/
static void* mempool_alloc_big(mempool* pool, size_t size) {
void* ret = malloc(size);
if (!ret) {
NULL;
}
memset(ret, 0, size);
int n = 0;
big_trunk* cur;
for (cur = pool->big; cur && ++n > 3; cur = cur->next) {
if (!cur->start) {
cur->start = ret;
return ret;
}
}
big_trunk* new_node = mempool_alloc_trunk(pool, sizeof(big_trunk));
if (!new_node) {
free(ret);
return NULL;
}
new_node->start = ret;
new_node->next = pool->big;
pool->big = new_node;
#ifdef ENABLE_LOG
printf("get big trunk %p\n", ret);
#endif
return ret;
}
/*
* size Allocate large blocks if greater than the boundary value, otherwise allocate small blocks
* When allocating small blocks, traverse the linked list of small blocks from the current small block, and return directly when finding unused space larger than size,
* If not found, create a small block and return
*/
void* mempool_alloc_trunk(mempool* pool, size_t size) {
if (size > pool->border) {
return mempool_alloc_big(pool, size);
}
small_trunk* cur;
for (cur = pool->cur_small; cur; cur = cur->next) {
cur->last = ALIGN_PTR(cur->last, MP_ALIGNMENT);
printf("end-last:%ld, last:%p, end:%p\n", cur->end - cur->last, cur->last, cur->end);
if (cur->end - cur->last >= size) {
void *ret = cur->last;
cur->last = cur->last + size;
#ifdef ENABLE_LOG
printf("get smaller trunk %p size %ld from small trunk %p\n", ret, size, cur);
#endif
return ret;
}
}
return mempool_alloc_small(pool, size);
}
// Release large blocks. Small blocks cannot be released with this function
void mempool_free_trunk(mempool* pool, void* trunk) {
big_trunk* big = pool->big;
while (big) {
if (big->start == trunk) {
#ifdef ENABLE_LOG
printf("free big trunk addr:%p\n", big->start);
#endif
free(big->start);
big->start = NULL;
return;
}
big = big->next;
}
}
int main() {
mempool* pool = mempool_create(5000);
int i;
for (i = 0; i < 10; ++i) {
void* trunk = mempool_alloc_trunk(pool, 1024);
if (!trunk) {
printf("alloc small failed\n");
return -1;
}
// printf("alloc small success\n");
}
printf("\nalloc 10 big trunk\n");
void* arr[10];
for (i = 0; i < 10; ++i) {
void* trunk = mempool_alloc_trunk(pool, 8000);
if (!trunk) {
printf("alloc big failed\n");
return -1;
}
arr[i] = trunk;
}
printf("\nfree 10 big trunk\n");
for (i = 0; i < 10; ++i) {
mempool_free_trunk(pool, arr[i]);
}
printf("\nreset pool\n");
mempool_reset(pool);
for (i = 0; i < 10; ++i) {
void* trunk = mempool_alloc_trunk(pool, 1024);
if (!trunk) {
printf("2 alloc small failed\n");
return -1;
}
}
printf("\ndestory pool\n");
mempool_destroy(pool);
pool = NULL;
return 0;
}