[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"

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