[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	1048576	/* new pool size */
#define MAX_POOLS	32	/* maximum number of pools to setup */

unsigned int smalloc_pool_size = INITIAL_SIZE;

#ifdef ENABLE_RESIZE
#define MAX_SIZE	8 * smalloc_pool_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_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 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, 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;

	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;

	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;

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