[fio.git] / smalloc.c

/*
 * 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	32*1048576	/* new pool size */
#define MAX_POOLS	4		/* 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;
}
Commit	Line	Data
d24c33a4 JA	1	/*
	2	* simple memory allocator, backed by mmap() so that it hands out memory
	3	* that can be shared across processes and threads
	4	*/
	5	#include <sys/mman.h>
	6	#include <stdio.h>
	7	#include <stdlib.h>
	8	#include <assert.h>
	9	#include <string.h>
	10	#include <unistd.h>
	11	#include <sys/types.h>
	12	#include <limits.h>
	13
	14	#include "mutex.h"
	15
d24c33a4 JA	16	#define MP_SAFE /* define to made allocator thread safe */
d24c33a4 JA	17
c5dda9e3 JA	18	#define INITIAL_SIZE 321048576 / new pool size */
c5dda9e3 JA	19	#define MAX_POOLS 4 /* maximum number of pools to setup */
d24c33a4	20
2b386d25 JA	21	unsigned int smalloc_pool_size = INITIAL_SIZE;
2b386d25 JA	22
d24c33a4 JA	23	struct pool {
	24	struct fio_mutex lock; / protects this pool */
	25	void map; / map of blocks */
	26	void last; / next free block hint */
	27	unsigned int size; /* size of pool */
	28	unsigned int room; /* size left in pool */
	29	unsigned int largest_block; /* largest block free */
	30	unsigned int free_since_compact; /* sfree() since compact() */
	31	int fd; /* memory backing fd */
	32	char file[PATH_MAX]; /* filename for fd */
	33	};
	34
	35	static struct pool mp[MAX_POOLS];
	36	static unsigned int nr_pools;
	37	static unsigned int last_pool;
	38	static struct fio_mutex *lock;
	39
	40	struct mem_hdr {
	41	unsigned int size;
	42	};
	43
	44	static inline void pool_lock(struct pool *pool)
	45	{
	46	if (pool->lock)
	47	fio_mutex_down(pool->lock);
	48	}
	49
	50	static inline void pool_unlock(struct pool *pool)
	51	{
	52	if (pool->lock)
	53	fio_mutex_up(pool->lock);
	54	}
	55
65864cf7	56	static inline void global_read_lock(void)
d24c33a4 JA	57	{
d24c33a4 JA	58	if (lock)
65864cf7	59	fio_mutex_down_read(lock);
d24c33a4 JA	60	}
d24c33a4 JA	61
65864cf7	62	static inline void global_read_unlock(void)
d24c33a4 JA	63	{
d24c33a4 JA	64	if (lock)
65864cf7 JA	65	fio_mutex_up_read(lock);
	66	}
	67
	68	static inline void global_write_lock(void)
	69	{
	70	if (lock)
	71	fio_mutex_down_write(lock);
	72	}
	73
	74	static inline void global_write_unlock(void)
	75	{
	76	if (lock)
	77	fio_mutex_up_write(lock);
d24c33a4 JA	78	}
	79
	80	#define hdr_free(hdr) ((hdr)->size & 0x80000000)
	81	#define hdr_size(hdr) ((hdr)->size & ~0x80000000)
	82	#define hdr_mark_free(hdr) ((hdr)->size \|= 0x80000000)
	83
	84	static inline int ptr_valid(struct pool pool, void ptr)
	85	{
	86	return (ptr >= pool->map) && (ptr < pool->map + pool->size);
	87	}
	88
	89	static inline int __hdr_valid(struct pool pool, struct mem_hdr hdr,
	90	unsigned int size)
	91	{
	92	return ptr_valid(pool, hdr) && ptr_valid(pool, (void *) hdr + size - 1);
	93	}
	94
	95	static inline int hdr_valid(struct pool pool, struct mem_hdr hdr)
	96	{
	97	return __hdr_valid(pool, hdr, hdr_size(hdr));
	98	}
	99
	100	static inline int region_free(struct mem_hdr *hdr)
	101	{
	102	return hdr_free(hdr) \|\| (!hdr_free(hdr) && !hdr_size(hdr));
	103	}
	104
	105	static inline struct mem_hdr __hdr_nxt(struct pool pool, struct mem_hdr *hdr,
	106	unsigned int size)
	107	{
	108	struct mem_hdr nxt = (void ) hdr + size + sizeof(*hdr);
	109
	110	if (__hdr_valid(pool, nxt, size))
	111	return nxt;
	112
	113	return NULL;
	114	}
	115
	116	static inline struct mem_hdr hdr_nxt(struct pool pool, struct mem_hdr *hdr)
	117	{
	118	return __hdr_nxt(pool, hdr, hdr_size(hdr));
	119	}
	120
	121	static void merge(struct pool pool, struct mem_hdr hdr, struct mem_hdr *nxt)
	122	{
	123	unsigned int hfree = hdr_free(hdr);
	124	unsigned int nfree = hdr_free(nxt);
	125
	126	hdr->size = hdr_size(hdr) + hdr_size(nxt) + sizeof(*nxt);
	127	nxt->size = 0;
	128
	129	if (hfree)
	130	hdr_mark_free(hdr);
	131	if (nfree)
	132	hdr_mark_free(nxt);
	133
	134	if (pool->last == nxt)
	135	pool->last = hdr;
	136	}
	137
	138	static int combine(struct pool pool, struct mem_hdr prv, struct mem_hdr *hdr)
	139	{
	140	if (prv && hdr_free(prv) && hdr_free(hdr)) {
	141	merge(pool, prv, hdr);
142	return 1;
143	}
144
145	return 0;
146	}
147
148	static int compact_pool(struct pool *pool)
149	{
150	struct mem_hdr hdr = pool->map, nxt;
151	unsigned int compacted = 0;
152
153	if (pool->free_since_compact < 50)
154	return 1;
155
156	while (hdr) {
157	nxt = hdr_nxt(pool, hdr);
158	if (!nxt)
159	break;
160	if (hdr_free(nxt) && hdr_free(hdr)) {
161	merge(pool, hdr, nxt);
162	compacted++;
163	continue;
164	}
165	hdr = hdr_nxt(pool, hdr);
166	}
167
168	pool->free_since_compact = 0;
169	return !!compacted;
170	}
171
adf57099	172	static int add_pool(struct pool *pool, unsigned int alloc_size)
d24c33a4 JA	173	{
	174	struct mem_hdr *hdr;
	175	void *ptr;
	176	int fd;
	177
	178	strcpy(pool->file, "/tmp/.fio_smalloc.XXXXXX");
	179	fd = mkstemp(pool->file);
	180	if (fd < 0)
	181	goto out_close;
	182
c08e194d	183	alloc_size += sizeof(*hdr);
adf57099 JA	184	if (alloc_size > smalloc_pool_size)
	185	pool->size = alloc_size;
	186	else
	187	pool->size = smalloc_pool_size;
	188
d24c33a4 JA	189	if (ftruncate(fd, pool->size) < 0)
	190	goto out_unlink;
	191
	192	ptr = mmap(NULL, pool->size, PROT_READ\|PROT_WRITE, MAP_SHARED, fd, 0);
	193	if (ptr == MAP_FAILED)
	194	goto out_unlink;
	195
	196	memset(ptr, 0, pool->size);
	197	pool->map = pool->last = ptr;
	198
	199	#ifdef MP_SAFE
	200	pool->lock = fio_mutex_init(1);
	201	if (!pool->lock)
	202	goto out_unlink;
	203	#endif
	204
	205	pool->fd = fd;
	206
	207	hdr = pool->map;
	208	pool->room = hdr->size = pool->size - sizeof(*hdr);
	209	pool->largest_block = pool->room;
	210	hdr_mark_free(hdr);
65864cf7	211	global_write_lock();
d24c33a4	212	nr_pools++;
65864cf7	213	global_write_unlock();
d24c33a4 JA	214	return 0;
	215	out_unlink:
	216	if (pool->map)
	217	munmap(pool->map, pool->size);
	218	unlink(pool->file);
	219	out_close:
	220	if (fd >= 0)
	221	close(fd);
	222	return 1;
	223	}
	224
	225	void sinit(void)
	226	{
4d4e80f2	227	int ret;
d24c33a4 JA	228
d24c33a4 JA	229	#ifdef MP_SAFE
9c5b5290	230	lock = fio_mutex_rw_init();
d24c33a4	231	#endif
adf57099	232	ret = add_pool(&mp[0], INITIAL_SIZE);
d24c33a4 JA	233	assert(!ret);
	234	}
	235
	236	static void cleanup_pool(struct pool *pool)
	237	{
	238	unlink(pool->file);
	239	close(pool->fd);
	240	munmap(pool->map, pool->size);
	241
	242	if (pool->lock)
	243	fio_mutex_remove(pool->lock);
	244	}
	245
	246	void scleanup(void)
	247	{
	248	unsigned int i;
	249
	250	for (i = 0; i < nr_pools; i++)
	251	cleanup_pool(&mp[i]);
	252
	253	if (lock)
	254	fio_mutex_remove(lock);
	255	}
	256
	257	static void sfree_pool(struct pool pool, void ptr)
	258	{
	259	struct mem_hdr hdr, nxt;
	260
	261	if (!ptr)
	262	return;
	263
	264	assert(ptr_valid(pool, ptr));
	265
	266	pool_lock(pool);
	267	hdr = ptr - sizeof(*hdr);
	268	assert(!hdr_free(hdr));
	269	hdr_mark_free(hdr);
	270	pool->room -= hdr_size(hdr);
	271
	272	nxt = hdr_nxt(pool, hdr);
	273	if (nxt && hdr_free(nxt))
	274	merge(pool, hdr, nxt);
	275
	276	if (hdr_size(hdr) > pool->largest_block)
	277	pool->largest_block = hdr_size(hdr);
	278
	279	pool->free_since_compact++;
	280	pool_unlock(pool);
	281	}
	282
	283	void sfree(void *ptr)
	284	{
	285	struct pool *pool = NULL;
	286	unsigned int i;
	287
8e5732e5 JA	288	if (!ptr)
	289	return;
	290
65864cf7	291	global_read_lock();
d24c33a4 JA	292
	293	for (i = 0; i < nr_pools; i++) {
	294	if (ptr_valid(&mp[i], ptr)) {
	295	pool = &mp[i];
	296	break;
	297	}
	298	}
	299
65864cf7	300	global_read_unlock();
d24c33a4 JA	301
	302	assert(pool);
	303	sfree_pool(pool, ptr);
	304	}
	305
	306	static void smalloc_pool(struct pool pool, unsigned int size)
	307	{
	308	struct mem_hdr hdr, prv;
	309	int did_restart = 0;
	310	void *ret;
	311
8e5732e5	312	if (!size)
d24c33a4 JA	313	return NULL;
	314
	315	pool_lock(pool);
8e5732e5 JA	316	if (size > pool->room + sizeof(*hdr))
	317	goto fail;
	318	if ((size > pool->largest_block) && pool->largest_block)
	319	goto fail;
d24c33a4 JA	320	restart:
	321	hdr = pool->last;
	322	prv = NULL;
	323	do {
	324	if (combine(pool, prv, hdr))
	325	hdr = prv;
5ec10eaa	326
d24c33a4 JA	327	if (hdr_free(hdr) && hdr_size(hdr) >= size)
	328	break;
	329
	330	prv = hdr;
	331	} while ((hdr = hdr_nxt(pool, hdr)) != NULL);
	332
	333	if (!hdr)
	334	goto fail;
	335
	336	/*
	337	* more room, adjust next header if any
	338	*/
	339	if (hdr_size(hdr) - size >= 2 * sizeof(*hdr)) {
	340	struct mem_hdr *nxt = __hdr_nxt(pool, hdr, size);
	341
	342	if (nxt) {
	343	nxt->size = hdr_size(hdr) - size - sizeof(*hdr);
	344	if (hdr_size(hdr) == pool->largest_block)
	345	pool->largest_block = hdr_size(nxt);
	346	hdr_mark_free(nxt);
	347	} else
	348	size = hdr_size(hdr);
	349	} else
	350	size = hdr_size(hdr);
	351
	352	if (size == hdr_size(hdr) && size == pool->largest_block)
	353	pool->largest_block = 0;
	354
	355	/*
	356	* also clears free bit
	357	*/
	358	hdr->size = size;
	359	pool->last = hdr_nxt(pool, hdr);
	360	if (!pool->last)
	361	pool->last = pool->map;
	362	pool->room -= size;
	363	pool_unlock(pool);
	364
	365	ret = (void ) hdr + sizeof(hdr);
	366	memset(ret, 0, size);
	367	return ret;
	368	fail:
	369	/*
	370	* if we fail to allocate, first compact the entries that we missed.
	371	* if that also fails, increase the size of the pool
	372	*/
136f6b79	373	if (++did_restart <= 1) {
d24c33a4 JA	374	if (!compact_pool(pool)) {
	375	pool->last = pool->map;
	376	goto restart;
	377	}
	378	}
d24c33a4 JA	379	pool_unlock(pool);
	380	return NULL;
	381	}
	382
	383	void *smalloc(unsigned int size)
	384	{
	385	unsigned int i;
	386
65864cf7	387	global_read_lock();
d24c33a4 JA	388	i = last_pool;
	389
	390	do {
	391	for (; i < nr_pools; i++) {
	392	void *ptr = smalloc_pool(&mp[i], size);
	393
	394	if (ptr) {
	395	last_pool = i;
65864cf7	396	global_read_unlock();
d24c33a4 JA	397	return ptr;
	398	}
	399	}
	400	if (last_pool) {
	401	last_pool = 0;
	402	continue;
	403	}
	404
	405	if (nr_pools + 1 >= MAX_POOLS)
	406	break;
	407	else {
	408	i = nr_pools;
65864cf7	409	global_read_unlock();
adf57099	410	if (add_pool(&mp[nr_pools], size))
65864cf7 JA	411	goto out;
65864cf7 JA	412	global_read_lock();
d24c33a4 JA	413	}
	414	} while (1);
	415
65864cf7 JA	416	global_read_unlock();
65864cf7 JA	417	out:
d24c33a4 JA	418	return NULL;
	419	}
	420
	421	char smalloc_strdup(const char str)
	422	{
	423	char *ptr;
	424
	425	ptr = smalloc(strlen(str) + 1);
	426	strcpy(ptr, str);
	427	return ptr;
	428	}