smalloc.c - fp2-dev/platform/external/fio - Gitiles

 /*
  * simple memory allocator, backed by mmap() so that it hands out memory
  * that can be shared across processes and threads
  */
 #include <sys/mman.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
 #include <string.h>
 #include <unistd.h>
 #include <sys/types.h>
 #include <limits.h>

 #include "mutex.h"

 #define MP_SAFE			/* define to made allocator thread safe */

 #define INITIAL_SIZE	1048576	/* new pool size */
 #define MAX_POOLS	32	/* maximum number of pools to setup */

 unsigned int smalloc_pool_size = INITIAL_SIZE;

 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_read_lock(void)
 {
 	if (lock)
 		fio_mutex_down_read(lock);
 }

 static inline void global_read_unlock(void)
 {
 	if (lock)
 		fio_mutex_up_read(lock);
 }

 static inline void global_write_lock(void)
 {
 	if (lock)
 		fio_mutex_down_write(lock);
 }

 static inline void global_write_unlock(void)
 {
 	if (lock)
 		fio_mutex_up_write(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 add_pool(struct pool *pool, unsigned int alloc_size)
 {
 	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;

 	alloc_size += sizeof(*hdr);
 	if (alloc_size > smalloc_pool_size)
 		pool->size = alloc_size;
 	else
 		pool->size = smalloc_pool_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);
 	global_write_lock();
 	nr_pools++;
 	global_write_unlock();
 	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;

 #ifdef MP_SAFE
 	lock = fio_mutex_rw_init();
 #endif
 	ret = add_pool(&mp[0], INITIAL_SIZE);
 	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;

 	if (!ptr)
 		return;

 	global_read_lock();

 	for (i = 0; i < nr_pools; i++) {
 		if (ptr_valid(&mp[i], ptr)) {
 			pool = &mp[i];
 			break;
 		}
 	}

 	global_read_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;

 	if (!size)
 		return NULL;

 	pool_lock(pool);
 	if (size > pool->room + sizeof(*hdr))
 		goto fail;
 	if ((size > pool->largest_block) && pool->largest_block)
 		goto fail;
 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
 	 */
 	if (++did_restart <= 1) {
 		if (!compact_pool(pool)) {
 			pool->last = pool->map;
 			goto restart;
 		}
 	}
 	pool_unlock(pool);
 	return NULL;
 }

 void *smalloc(unsigned int size)
 {
 	unsigned int i;

 	global_read_lock();
 	i = last_pool;

 	do {
 		for (; i < nr_pools; i++) {
 			void *ptr = smalloc_pool(&mp[i], size);

 			if (ptr) {
 				last_pool = i;
 				global_read_unlock();
 				return ptr;
 			}
 		}
 		if (last_pool) {
 			last_pool = 0;
 			continue;
 		}

 		if (nr_pools + 1 >= MAX_POOLS)
 			break;
 		else {
 			i = nr_pools;
 			global_read_unlock();
 			if (add_pool(&mp[nr_pools], size))
 				goto out;
 			global_read_lock();
 		}
 	} while (1);

 	global_read_unlock();
 out:
 	return NULL;
 }

 char *smalloc_strdup(const char *str)
 {
 	char *ptr;

 	ptr = smalloc(strlen(str) + 1);
 	strcpy(ptr, str);
 	return ptr;
 }
	/*
	* simple memory allocator, backed by mmap() so that it hands out memory
	* that can be shared across processes and threads
	*/
	#include <sys/mman.h>
	#include <stdio.h>
	#include <stdlib.h>
	#include <assert.h>
	#include <string.h>
	#include <unistd.h>
	#include <sys/types.h>
	#include <limits.h>

	#include "mutex.h"

	#define MP_SAFE /* define to made allocator thread safe */

	#define INITIAL_SIZE 1048576 /* new pool size */
	#define MAX_POOLS 32 /* maximum number of pools to setup */

	unsigned int smalloc_pool_size = INITIAL_SIZE;

	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_read_lock(void)
	{
	if (lock)
	fio_mutex_down_read(lock);
	}

	static inline void global_read_unlock(void)
	{
	if (lock)
	fio_mutex_up_read(lock);
	}

	static inline void global_write_lock(void)
	{
	if (lock)
	fio_mutex_down_write(lock);
	}

	static inline void global_write_unlock(void)
	{
	if (lock)
	fio_mutex_up_write(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 add_pool(struct pool *pool, unsigned int alloc_size)
	{
	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;

	alloc_size += sizeof(*hdr);
	if (alloc_size > smalloc_pool_size)
	pool->size = alloc_size;
	else
	pool->size = smalloc_pool_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);
	global_write_lock();
	nr_pools++;
	global_write_unlock();
	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;

	#ifdef MP_SAFE
	lock = fio_mutex_rw_init();
	#endif
	ret = add_pool(&mp[0], INITIAL_SIZE);
	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;

	if (!ptr)
	return;

	global_read_lock();

	for (i = 0; i < nr_pools; i++) {
	if (ptr_valid(&mp[i], ptr)) {
	pool = &mp[i];
	break;
	}
	}

	global_read_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;

	if (!size)
	return NULL;

	pool_lock(pool);
	if (size > pool->room + sizeof(*hdr))
	goto fail;
	if ((size > pool->largest_block) && pool->largest_block)
	goto fail;
	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
	*/
	if (++did_restart <= 1) {
	if (!compact_pool(pool)) {
	pool->last = pool->map;
	goto restart;
	}
	}
	pool_unlock(pool);
	return NULL;
	}

	void *smalloc(unsigned int size)
	{
	unsigned int i;

	global_read_lock();
	i = last_pool;

	do {
	for (; i < nr_pools; i++) {
	void *ptr = smalloc_pool(&mp[i], size);

	if (ptr) {
	last_pool = i;
	global_read_unlock();
	return ptr;
	}
	}
	if (last_pool) {
	last_pool = 0;
	continue;
	}

	if (nr_pools + 1 >= MAX_POOLS)
	break;
	else {
	i = nr_pools;
	global_read_unlock();
	if (add_pool(&mp[nr_pools], size))
	goto out;
	global_read_lock();
	}
	} while (1);

	global_read_unlock();
	out:
	return NULL;
	}

	char smalloc_strdup(const char str)
	{
	char *ptr;

	ptr = smalloc(strlen(str) + 1);
	strcpy(ptr, str);
	return ptr;
	}