You can use them for efficient allocation of large amount of small memory blocks. You can use them to allocate many blocks and free them all at once. They allow storing and restoring state of what is allocated, growing and shrinking the last block and other tricks.
Definitions
struct mempool_state {
size_t free[2];
void *last[2];
struct mempool_state *next;
};
Memory pool state (see mp_push(), …). You should use this one as an opaque handle only, the insides are internal.
struct mempool {
struct ucw_allocator allocator; // This must be the first element
struct mempool_state state;
void *unused, *last_big;
size_t chunk_size, threshold;
uint idx;
u64 total_size;
};
Memory pool. You should use this one as an opaque handle only, the insides are internal.
struct mempool_stats {
u64 total_size; /* Real allocated size in bytes */
u64 used_size; /* Estimated size allocated from mempool to application */
uint chain_count[3]; /* Number of allocated chunks in small/big/unused chains */
u64 chain_size[3]; /* Size of allocated chunks in small/big/unused chains */
};
Mempool statistics. See mp_stats().
Basic manipulation
void mp_init(struct mempool *pool, size_t chunk_size);
Initialize a given mempool structure. chunk_size must be in the interval [1, SIZE_MAX / 2]. It will allocate memory by this large chunks and take memory to satisfy requests from them.
Memory pools can be treated as resources, see res_mempool().
struct mempool *mp_new(size_t chunk_size);
Allocate and initialize a new memory pool. See mp_init() for chunk_size limitations.
The new mempool structure is allocated on the new mempool.
Memory pools can be treated as resources, see res_mempool().
void mp_delete(struct mempool *pool);
Cleanup mempool initialized by mp_init or mp_new. Frees all the memory allocated by this mempool and, if created by mp_new(), the pool itself.
void mp_flush(struct mempool *pool);
Frees all data on a memory pool, but leaves it working. It can keep some of the chunks allocated to serve further allocation requests. Leaves the pool alive, even if it was created with mp_new().
void mp_stats(struct mempool *pool, struct mempool_stats *stats);
Compute some statistics for debug purposes. See the definition of the mempool_stats structure. This function scans the chunk list, so it can be slow. If you are interested in total memory consumption only, mp_total_size() is faster.
u64 mp_total_size(struct mempool *pool);
Return how many bytes were allocated by the pool, including unused parts of chunks. This function runs in constant time.
void mp_shrink(struct mempool *pool, u64 min_total_size);
Release unused chunks of memory reserved for further allocation requests, but stop if mp_total_size() would drop below min_total_size.
Allocation routines
void *mp_alloc(struct mempool *pool, size_t size);
The function allocates new size bytes on a given memory pool. If the size is zero, the resulting pointer is undefined, but it may be safely reallocated or used as the parameter to other functions below.
The resulting pointer is always aligned to a multiple of CPU_STRUCT_ALIGN bytes and this condition remains true also after future reallocations.
void *mp_alloc_noalign(struct mempool *pool, size_t size);
The same as mp_alloc(), but the result may be unaligned.
void *mp_alloc_zero(struct mempool *pool, size_t size);
The same as mp_alloc(), but fills the newly allocated memory with zeroes.
static inline void *mp_alloc_fast(struct mempool *pool, size_t size);
Inlined version of mp_alloc().
static inline void *mp_alloc_fast_noalign(struct mempool *pool, size_t size);
Inlined version of mp_alloc_noalign().
static inline struct ucw_allocator *mp_get_allocator(struct mempool *mp);
Return a generic allocator representing the given mempool.
Growing buffers
You do not need to know, how a buffer will need to be large, you can grow it incrementally to needed size. You can grow only one buffer at a time on a given mempool.
Similar functionality is provided by growing buffes module.
void *mp_start(struct mempool *pool, size_t size);
Open a new growing buffer (at least size bytes long). If the size is zero, the resulting pointer is undefined, but it may be safely reallocated or used as the parameter to other functions below.
The resulting pointer is always aligned to a multiple of CPU_STRUCT_ALIGN bytes and this condition remains true also after future reallocations. There is an unaligned version as well.
Keep in mind that you can’t make any other pool allocations before you "close" the growing buffer with mp_end().
static inline void *mp_start_fast(struct mempool *pool, size_t size);
Inlined version of mp_start().
static inline void *mp_start_fast_noalign(struct mempool *pool, size_t size);
Inlined version of mp_start_noalign().
static inline void *mp_ptr(struct mempool *pool);
Return start pointer of the growing buffer allocated by latest mp_start() or a similar function.
static inline size_t mp_avail(struct mempool *pool);
Return the number of bytes available for extending the growing buffer. (Before a reallocation will be needed).
static inline void *mp_grow(struct mempool *pool, size_t size);
Grow the buffer allocated by mp_start() to be at least size bytes long (size may be less than mp_avail(), even zero). Reallocated buffer may change its starting position. The content will be unchanged to the minimum of the old and new sizes; newly allocated memory will be uninitialized.
static inline void *mp_expand(struct mempool *pool);
Grow the buffer by at least one byte — equivalent to mp_grow(@pool, @mp_avail(pool) + 1).
static inline void *mp_spread(struct mempool *pool, void *p, size_t size);
Ensure that there is at least size bytes free after p, if not, reallocate and adjust p.
static inline char *mp_append_char(struct mempool *pool, char *p, uint c);
Append a character to the growing buffer. Called with p pointing after the last byte in the buffer, returns a pointer after the last byte of the new (possibly reallocated) buffer.
static inline void *mp_append_block(struct mempool *pool, void *p, const void *block, size_t size);
Append a memory block to the growing buffer. Called with p pointing after the last byte in the buffer, returns a pointer after the last byte of the new (possibly reallocated) buffer.
static inline void *mp_append_string(struct mempool *pool, void *p, const char *str);
Append a string to the growing buffer. Called with p pointing after the last byte in the buffer, returns a pointer after the last byte of the new (possibly reallocated) buffer.
void *mp_append_utf8_32(struct mempool *pool, void *p, uint c);
Append an UTF-8 character to the growing buffer. Called with p pointing after the last byte in the buffer, returns a pointer after the last byte of the new (possibly reallocated) buffer.
static inline void *mp_end(struct mempool *pool, void *end);
Close the growing buffer. The end must point just behind the data, you want to keep allocated (so it can be in the interval [@mp_ptr(@pool), @mp_ptr(@pool) + @mp_avail(@pool)]). Returns a pointer to the beginning of the just closed block.
static inline char *mp_end_string(struct mempool *pool, void *end);
Close the growing buffer as a string. That is, append a zero byte and call mp_end().
static inline size_t mp_size(struct mempool *pool, void *ptr);
Return size in bytes of the last allocated memory block (with mp_alloc() or mp_end()).
size_t mp_open(struct mempool *pool, void *ptr);
Open the last memory block (allocated with mp_alloc() or mp_end()) for growing and return its size in bytes. The contents and the start pointer remain unchanged. Do not forget to call mp_end() to close it.
static inline size_t mp_open_fast(struct mempool *pool, void *ptr);
Inlined version of mp_open().
void *mp_realloc(struct mempool *pool, void *ptr, size_t size);
Reallocate the last memory block (allocated with mp_alloc() or mp_end()) to the new size. Behavior is similar to mp_grow(), but the resulting block is closed.
void *mp_realloc_zero(struct mempool *pool, void *ptr, size_t size);
The same as mp_realloc(), but fills the additional bytes (if any) with zeroes.
static inline void *mp_realloc_fast(struct mempool *pool, void *ptr, size_t size);
Inlined version of mp_realloc().
Storing and restoring state
Mempools can remember history of what was allocated and return back in time.
static inline void mp_save(struct mempool *pool, struct mempool_state *state);
Save the current state of a memory pool. Do not call this function with an opened growing buffer.
struct mempool_state *mp_push(struct mempool *pool);
Save the current state to a newly allocated mempool_state structure. Do not call this function with an opened growing buffer.
void mp_restore(struct mempool *pool, struct mempool_state *state);
Restore the state saved by mp_save() or mp_push() and free all data allocated after that point (including the state structure itself). You can’t reallocate the last memory block from the saved state.
static inline void mp_restore_fast(struct mempool *pool, struct mempool_state *state);
Inlined version of mp_restore().
void mp_pop(struct mempool *pool);
String operations
char *mp_strdup(struct mempool *, const char *) LIKE_MALLOC;
Makes a copy of a string on a mempool. Returns NULL for NULL string.
void *mp_memdup(struct mempool *, const void *, size_t) LIKE_MALLOC;
Makes a copy of a memory block on a mempool.
char *mp_multicat(struct mempool *, ...) LIKE_MALLOC SENTINEL_CHECK;
Concatenates all passed strings. The last parameter must be NULL. This will concatenate two strings:
char *message = mp_multicat(pool, "hello ", "world", NULL);
static inline char *LIKE_MALLOC mp_strcat(struct mempool *mp, const char *x, const char *y);
Concatenates two strings and stores result on mp.
char *mp_strjoin(struct mempool *p, char **a, uint n, uint sep) LIKE_MALLOC;
Join strings and place sep between each two neighboring. p is the mempool to provide memory, a is array of strings and n tells how many there is of them.
char *mp_str_from_mem(struct mempool *p, const void *mem, size_t len) LIKE_MALLOC;
Convert memory block to a string. Makes a copy of the given memory block in the mempool p, adding an extra terminating zero byte at the end.
Formatted output
char *mp_printf(struct mempool *mp, const char *fmt, ...) FORMAT_CHECK(printf,2,3) LIKE_MALLOC;
printf() into a in-memory string, allocated on the memory pool.
char *mp_vprintf(struct mempool *mp, const char *fmt, va_list args) LIKE_MALLOC;
Like mp_printf(), but uses va_list for parameters.
char *mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) FORMAT_CHECK(printf,3,4);
Like mp_printf(), but it appends the data at the end of string pointed to by ptr. The string is mp_open()ed, so you have to provide something that can be.
Returns pointer to the beginning of the string (the pointer may have changed due to reallocation).
In some versions of LibUCW, this function was called mp_append_printf(). However, this name turned out to be confusing — unlike other appending functions, this one is not called on an opened growing buffer. The old name will be preserved for backward compatibility for the time being.
char *mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args);
Like mp_printf_append(), but uses va_list for parameters.
In some versions of LibUCW, this function was called mp_append_vprintf(). However, this name turned out to be confusing — unlike other appending functions, this one is not called on an opened growing buffer. The old name will be preserved for backward compatibility for the time being.
Examples
You can find few examples of mempools use. But their actual use is limited only by your fantasy.
String trie
There are two advantages for a trie to use a mempool. One, it has less overhead than malloc (with the cost you can not free the blocks one by one as you allocated them). Second is freeing the whole trie, you do not need to walk trough it and free each node, you just flush the whole mempool.
struct trie_node {
struct trie_node *subs[256];
bool present;
};
struct trie {
struct trie_node root;
struct mempool *pool;
};
struct trie *trie_new(void) {
struct mempool *pool = mn_new(4096);
struct trie *result = mp_alloc_zero(pool, sizeof(*result));
result->pool = pool;
return result;
}
void trie_insert_internal(struct trie_node *where, struct mempool *pool, const char *string) {
if(*string) {
if(!where->subs[*string])
where->subs[*string] = mp_alloc_zero(pool, sizeof(*where->subs[*string]));
trie_insert_internal(where->subs[*string], pool, string + 1);
} else {
where->present = 1;
}
}
void trie_insert(struct trie *trie, const char *string) {
trie_insert_internal(&trie->root, trie->pool, string);
}
void trie_delete(struct trie *trie) {
mp_delete(trie->pool); //Free everything, including the trie structure
}
Action which may fail
Imagine a situation where you want to load information from few files. Loading of each file consists of list of actions, each can allocate some memory and each can fail. If an action fails, the whole file is considered invalid, you want to ignore that file and keep loading the others.
The problem with memory is you want to return the already allocated amount for the file which failed. You can use storing of mempool state.
void load_file(struct mempool *pool, const char *file) {
struct mempool_state state;
mp_save(pool, &state); // Store the current state
struct file_data *data = mp_alloc_zero(pool, sizeof(*data));
if(!(
file_open(file, data, pool) && // Load the file
header_load(data, pool) &&
part1_load(data, pool) &&
part2_load(data, pool) &&
file_close(data) &&
data_link(data, pool))) // Link the loaded data into global state
mp_restore(pool, &state); // Failed -> return all used memory
}
Load all data from stdin
You may want to load all data from stdin into a memory buffer. But there is the problem you do not know how many of them there is. You may use mempool and it’s growing buffer feature.
This example uses libucw’s own IO system, fastbufs.
void *stdin_data(struct mempool *pool) {
struct fastbuf *fb = bopen_fd(0, NULL); // Read from stdin
size_t amount;
char *ptr = mp_start(pool, 1024);
while(amount = bread(fb, ptr, 1024)) { // Read a block
ptr += amount; // Move after it
ptr = mp_spread(pool, ptr, 1024); // Get space for the next block
}
bclose(fb);
return mp_end(pool, ptr);
}