smalloc.c revision d24c33a479fcd68debad128da057814495f65e20 
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
24static unsigned int resize_error;
25#endif
26
27struct 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
39static struct pool mp[MAX_POOLS];
40static unsigned int nr_pools;
41static unsigned int last_pool;
42static struct fio_mutex *lock;
43
44struct mem_hdr {
45	unsigned int size;
46};
47
48static inline void pool_lock(struct pool *pool)
49{
50	if (pool->lock)
51		fio_mutex_down(pool->lock);
52}
53
54static inline void pool_unlock(struct pool *pool)
55{
56	if (pool->lock)
57		fio_mutex_up(pool->lock);
58}
59
60static inline void global_lock(void)
61{
62	if (lock)
63		fio_mutex_down(lock);
64}
65
66static 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
76static inline int ptr_valid(struct pool *pool, void *ptr)
77{
78	return (ptr >= pool->map) && (ptr < pool->map + pool->size);
79}
80
81static 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
87static inline int hdr_valid(struct pool *pool, struct mem_hdr *hdr)
88{
89	return __hdr_valid(pool, hdr, hdr_size(hdr));
90}
91
92static inline int region_free(struct mem_hdr *hdr)
93{
94	return hdr_free(hdr) || (!hdr_free(hdr) && !hdr_size(hdr));
95}
96
97static 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
108static 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
113static 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
130static 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
140static 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
164static 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;
201fail:
202	perror("resize");
203	resize_error = 1;
204#else
205	return 1;
206#endif
207}
208
209static 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;
245out_unlink:
246	if (pool->map)
247		munmap(pool->map, pool->size);
248	unlink(pool->file);
249out_close:
250	if (fd >= 0)
251		close(fd);
252	return 1;
253}
254
255void 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
265static 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
275void 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
286static 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
312void 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
332static 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);
346restart:
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;
394fail:
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
417void *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
452char *smalloc_strdup(const char *str)
453{
454	char *ptr;
455
456	ptr = smalloc(strlen(str) + 1);
457	strcpy(ptr, str);
458	return ptr;
459}
460