From: Jens Axboe Date: Sat, 1 Mar 2008 17:27:36 +0000 (+0100) Subject: Add a really simple allocator, backed with mmap'ed memory X-Git-Tag: fio-1.20-rc1~20 X-Git-Url: https://git.kernel.dk/?p=fio.git;a=commitdiff_plain;h=d24c33a479fcd68debad128da057814495f65e20 Add a really simple allocator, backed with mmap'ed memory We can use this simple allocator to get memory that can be safely shared across processes or threads. Signed-off-by: Jens Axboe --- diff --git a/Makefile b/Makefile index 090cf615..e0e323de 100644 --- a/Makefile +++ b/Makefile @@ -7,7 +7,7 @@ PROGS = fio SCRIPTS = fio_generate_plots OBJS = gettime.o fio.o ioengines.o init.o stat.o log.o time.o filesetup.o \ eta.o verify.o memory.o io_u.o parse.o mutex.o options.o rbtree.o \ - diskutil.o fifo.o blktrace.o + diskutil.o fifo.o blktrace.o smalloc.o OBJS += crc/crc7.o OBJS += crc/crc16.o diff --git a/smalloc.c b/smalloc.c new file mode 100644 index 00000000..0b9abad3 --- /dev/null +++ b/smalloc.c @@ -0,0 +1,459 @@ +/* + * simple memory allocator, backed by mmap() so that it hands out memory + * that can be shared across processes and threads + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include "mutex.h" + +#undef ENABLE_RESIZE /* define to enable pool resizing */ +#define MP_SAFE /* define to made allocator thread safe */ + +#define INITIAL_SIZE 65536 /* new pool size */ +#define MAX_POOLS 32 /* maximum number of pools to setup */ + +#ifdef ENABLE_RESIZE +#define MAX_SIZE 8 * INITIAL_SIZE +static unsigned int resize_error; +#endif + +struct pool { + struct fio_mutex *lock; /* protects this pool */ + void *map; /* map of blocks */ + void *last; /* next free block hint */ + unsigned int size; /* size of pool */ + unsigned int room; /* size left in pool */ + unsigned int largest_block; /* largest block free */ + unsigned int free_since_compact; /* sfree() since compact() */ + int fd; /* memory backing fd */ + char file[PATH_MAX]; /* filename for fd */ +}; + +static struct pool mp[MAX_POOLS]; +static unsigned int nr_pools; +static unsigned int last_pool; +static struct fio_mutex *lock; + +struct mem_hdr { + unsigned int size; +}; + +static inline void pool_lock(struct pool *pool) +{ + if (pool->lock) + fio_mutex_down(pool->lock); +} + +static inline void pool_unlock(struct pool *pool) +{ + if (pool->lock) + fio_mutex_up(pool->lock); +} + +static inline void global_lock(void) +{ + if (lock) + fio_mutex_down(lock); +} + +static inline void global_unlock(void) +{ + if (lock) + fio_mutex_up(lock); +} + +#define hdr_free(hdr) ((hdr)->size & 0x80000000) +#define hdr_size(hdr) ((hdr)->size & ~0x80000000) +#define hdr_mark_free(hdr) ((hdr)->size |= 0x80000000) + +static inline int ptr_valid(struct pool *pool, void *ptr) +{ + return (ptr >= pool->map) && (ptr < pool->map + pool->size); +} + +static inline int __hdr_valid(struct pool *pool, struct mem_hdr *hdr, + unsigned int size) +{ + return ptr_valid(pool, hdr) && ptr_valid(pool, (void *) hdr + size - 1); +} + +static inline int hdr_valid(struct pool *pool, struct mem_hdr *hdr) +{ + return __hdr_valid(pool, hdr, hdr_size(hdr)); +} + +static inline int region_free(struct mem_hdr *hdr) +{ + return hdr_free(hdr) || (!hdr_free(hdr) && !hdr_size(hdr)); +} + +static inline struct mem_hdr *__hdr_nxt(struct pool *pool, struct mem_hdr *hdr, + unsigned int size) +{ + struct mem_hdr *nxt = (void *) hdr + size + sizeof(*hdr); + + if (__hdr_valid(pool, nxt, size)) + return nxt; + + return NULL; +} + +static inline struct mem_hdr *hdr_nxt(struct pool *pool, struct mem_hdr *hdr) +{ + return __hdr_nxt(pool, hdr, hdr_size(hdr)); +} + +static void merge(struct pool *pool, struct mem_hdr *hdr, struct mem_hdr *nxt) +{ + unsigned int hfree = hdr_free(hdr); + unsigned int nfree = hdr_free(nxt); + + hdr->size = hdr_size(hdr) + hdr_size(nxt) + sizeof(*nxt); + nxt->size = 0; + + if (hfree) + hdr_mark_free(hdr); + if (nfree) + hdr_mark_free(nxt); + + if (pool->last == nxt) + pool->last = hdr; +} + +static int combine(struct pool *pool, struct mem_hdr *prv, struct mem_hdr *hdr) +{ + if (prv && hdr_free(prv) && hdr_free(hdr)) { + merge(pool, prv, hdr); + return 1; + } + + return 0; +} + +static int compact_pool(struct pool *pool) +{ + struct mem_hdr *hdr = pool->map, *nxt; + unsigned int compacted = 0; + + if (pool->free_since_compact < 50) + return 1; + + while (hdr) { + nxt = hdr_nxt(pool, hdr); + if (!nxt) + break; + if (hdr_free(nxt) && hdr_free(hdr)) { + merge(pool, hdr, nxt); + compacted++; + continue; + } + hdr = hdr_nxt(pool, hdr); + } + + pool->free_since_compact = 0; + return !!compacted; +} + +static int resize_pool(struct pool *pool) +{ +#ifdef ENABLE_RESIZE + unsigned int new_size = pool->size << 1; + struct mem_hdr *hdr, *last_hdr; + void *ptr; + + if (new_size >= MAX_SIZE || resize_error) + return 1; + + if (ftruncate(pool->fd, new_size) < 0) + goto fail; + + ptr = mremap(pool->map, pool->size, new_size, 0); + if (ptr == MAP_FAILED) + goto fail; + + pool->map = ptr; + hdr = pool; + do { + last_hdr = hdr; + } while ((hdr = hdr_nxt(hdr)) != NULL); + + if (hdr_free(last_hdr)) { + last_hdr->size = hdr_size(last_hdr) + new_size - pool_size; + hdr_mark_free(last_hdr); + } else { + struct mem_hdr *nxt; + + nxt = (void *) last_hdr + hdr_size(last_hdr) + sizeof(*hdr); + nxt->size = new_size - pool_size - sizeof(*hdr); + hdr_mark_free(nxt); + } + + pool_room += new_size - pool_size; + pool_size = new_size; + return 0; +fail: + perror("resize"); + resize_error = 1; +#else + return 1; +#endif +} + +static int add_pool(struct pool *pool) +{ + struct mem_hdr *hdr; + void *ptr; + int fd; + + strcpy(pool->file, "/tmp/.fio_smalloc.XXXXXX"); + fd = mkstemp(pool->file); + if (fd < 0) + goto out_close; + + pool->size = INITIAL_SIZE; + if (ftruncate(fd, pool->size) < 0) + goto out_unlink; + + ptr = mmap(NULL, pool->size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); + if (ptr == MAP_FAILED) + goto out_unlink; + + memset(ptr, 0, pool->size); + pool->map = pool->last = ptr; + +#ifdef MP_SAFE + pool->lock = fio_mutex_init(1); + if (!pool->lock) + goto out_unlink; +#endif + + pool->fd = fd; + + hdr = pool->map; + pool->room = hdr->size = pool->size - sizeof(*hdr); + pool->largest_block = pool->room; + hdr_mark_free(hdr); + nr_pools++; + return 0; +out_unlink: + if (pool->map) + munmap(pool->map, pool->size); + unlink(pool->file); +out_close: + if (fd >= 0) + close(fd); + return 1; +} + +void sinit(void) +{ + int ret = add_pool(&mp[0]); + +#ifdef MP_SAFE + lock = fio_mutex_init(1); +#endif + assert(!ret); +} + +static void cleanup_pool(struct pool *pool) +{ + unlink(pool->file); + close(pool->fd); + munmap(pool->map, pool->size); + + if (pool->lock) + fio_mutex_remove(pool->lock); +} + +void scleanup(void) +{ + unsigned int i; + + for (i = 0; i < nr_pools; i++) + cleanup_pool(&mp[i]); + + if (lock) + fio_mutex_remove(lock); +} + +static void sfree_pool(struct pool *pool, void *ptr) +{ + struct mem_hdr *hdr, *nxt; + + if (!ptr) + return; + + assert(ptr_valid(pool, ptr)); + + pool_lock(pool); + hdr = ptr - sizeof(*hdr); + assert(!hdr_free(hdr)); + hdr_mark_free(hdr); + pool->room -= hdr_size(hdr); + + nxt = hdr_nxt(pool, hdr); + if (nxt && hdr_free(nxt)) + merge(pool, hdr, nxt); + + if (hdr_size(hdr) > pool->largest_block) + pool->largest_block = hdr_size(hdr); + + pool->free_since_compact++; + pool_unlock(pool); +} + +void sfree(void *ptr) +{ + struct pool *pool = NULL; + unsigned int i; + + global_lock(); + + for (i = 0; i < nr_pools; i++) { + if (ptr_valid(&mp[i], ptr)) { + pool = &mp[i]; + break; + } + } + + global_unlock(); + + assert(pool); + sfree_pool(pool, ptr); +} + +static void *smalloc_pool(struct pool *pool, unsigned int size) +{ + struct mem_hdr *hdr, *prv; + int did_restart = 0; + void *ret; + + /* + * slight chance of race with sfree() here, but acceptable + */ + if (!size || size > pool->room + sizeof(*hdr) || + ((size > pool->largest_block) && pool->largest_block)) + return NULL; + + pool_lock(pool); +restart: + hdr = pool->last; + prv = NULL; + do { + if (combine(pool, prv, hdr)) + hdr = prv; + + if (hdr_free(hdr) && hdr_size(hdr) >= size) + break; + + prv = hdr; + } while ((hdr = hdr_nxt(pool, hdr)) != NULL); + + if (!hdr) + goto fail; + + /* + * more room, adjust next header if any + */ + if (hdr_size(hdr) - size >= 2 * sizeof(*hdr)) { + struct mem_hdr *nxt = __hdr_nxt(pool, hdr, size); + + if (nxt) { + nxt->size = hdr_size(hdr) - size - sizeof(*hdr); + if (hdr_size(hdr) == pool->largest_block) + pool->largest_block = hdr_size(nxt); + hdr_mark_free(nxt); + } else + size = hdr_size(hdr); + } else + size = hdr_size(hdr); + + if (size == hdr_size(hdr) && size == pool->largest_block) + pool->largest_block = 0; + + /* + * also clears free bit + */ + hdr->size = size; + pool->last = hdr_nxt(pool, hdr); + if (!pool->last) + pool->last = pool->map; + pool->room -= size; + pool_unlock(pool); + + ret = (void *) hdr + sizeof(*hdr); + memset(ret, 0, size); + return ret; +fail: + /* + * if we fail to allocate, first compact the entries that we missed. + * if that also fails, increase the size of the pool + */ + ++did_restart; + if (did_restart <= 1) { + if (!compact_pool(pool)) { + pool->last = pool->map; + goto restart; + } + } + ++did_restart; + if (did_restart <= 2) { + if (!resize_pool(pool)) { + pool->last = pool->map; + goto restart; + } + } + pool_unlock(pool); + return NULL; +} + +void *smalloc(unsigned int size) +{ + unsigned int i; + + global_lock(); + i = last_pool; + + do { + for (; i < nr_pools; i++) { + void *ptr = smalloc_pool(&mp[i], size); + + if (ptr) { + last_pool = i; + global_unlock(); + return ptr; + } + } + if (last_pool) { + last_pool = 0; + continue; + } + + if (nr_pools + 1 >= MAX_POOLS) + break; + else { + i = nr_pools; + if (add_pool(&mp[nr_pools])) + break; + } + } while (1); + + global_unlock(); + return NULL; +} + +char *smalloc_strdup(const char *str) +{ + char *ptr; + + ptr = smalloc(strlen(str) + 1); + strcpy(ptr, str); + return ptr; +} diff --git a/smalloc.h b/smalloc.h new file mode 100644 index 00000000..d5d4557e --- /dev/null +++ b/smalloc.h @@ -0,0 +1,10 @@ +#ifndef FIO_SMALLOC_H +#define FIO_SMALLOC_H + +extern void *smalloc(unsigned int); +extern void sfree(void *); +extern char *smalloc_strdup(const char *); +extern void sinit(void); +extern void scleanup(void); + +#endif