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