[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 SMALLOC_REDZONE		/* define to detect memory corruption */

#define INITIAL_SIZE	32768	/* new pool size */
#define MAX_POOLS	4		/* maximum number of pools to setup */

#define SMALLOC_PRE_RED		0xdeadbeefU
#define SMALLOC_POST_RED	0x5aa55aa5U
#define SMALLOC_REDZONE_SZ	(2 * sizeof(unsigned int))

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);
#ifdef SMALLOC_REDZONE
	alloc_size += SMALLOC_REDZONE_SZ;
#endif
	
	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_check_redzone(struct mem_hdr *hdr, void *ptr)
{
#ifdef SMALLOC_REDZONE
	unsigned int *prered, *postred;

	prered = (unsigned int *) ptr;
	postred = (unsigned int *) (ptr + hdr_size(hdr) - sizeof(unsigned int));

	if (*prered != SMALLOC_PRE_RED) {
		fprintf(stderr, "smalloc pre redzone destroyed!\n");
		fprintf(stderr, "  ptr=%p, prered=%x, expected %x\n",
				ptr, *prered, SMALLOC_PRE_RED);
		assert(0);
	}
	if (*postred != SMALLOC_POST_RED) {
		fprintf(stderr, "smalloc post redzone destroyed!\n");
		fprintf(stderr, "  ptr=%p, postred=%x, expected %x\n",
				ptr, *postred, SMALLOC_POST_RED);
		assert(0);
	}
#endif
}

static void sfree_pool(struct pool *pool, void *ptr)
{
	struct mem_hdr *hdr, *nxt;

	if (!ptr)
		return;

#ifdef SMALLOC_REDZONE
	ptr -= sizeof(unsigned int);
#endif

	assert(ptr_valid(pool, ptr));

	pool_lock(pool);
	hdr = ptr - sizeof(*hdr);
	sfree_check_redzone(hdr, ptr);
	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;
}

static void *smalloc_pool(struct pool *pool, unsigned int size)
{
#ifdef SMALLOC_REDZONE
	unsigned int *prered, *postred;
	void *ptr;

	ptr = __smalloc_pool(pool, size + 2 * sizeof(unsigned int));
	if (!ptr)
		return NULL;

	prered = ptr;
	*prered = SMALLOC_PRE_RED;
	ptr += sizeof(unsigned int);
	postred = ptr + size;
	*postred = SMALLOC_POST_RED;

	return ptr;
#else
	return __smalloc_pool(pool, size);
#endif
}

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