smalloc.c revision e43606c2b13ad7fc1af2bbe4a61cf8480ee3a532 
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 <inttypes.h>
12#include <sys/types.h>
13#include <limits.h>
14#include <fcntl.h>
15
16#include "mutex.h"
17#include "arch/arch.h"
18#include "os/os.h"
19
20#define SMALLOC_REDZONE		/* define to detect memory corruption */
21
22#define SMALLOC_BPB	32	/* block size, bytes-per-bit in bitmap */
23#define SMALLOC_BPI	(sizeof(unsigned int) * 8)
24#define SMALLOC_BPL	(SMALLOC_BPB * SMALLOC_BPI)
25
26#define INITIAL_SIZE	8192*1024	/* new pool size */
27#define MAX_POOLS	128		/* maximum number of pools to setup */
28
29#define SMALLOC_PRE_RED		0xdeadbeefU
30#define SMALLOC_POST_RED	0x5aa55aa5U
31
32unsigned int smalloc_pool_size = INITIAL_SIZE;
33const int int_mask = sizeof(int) - 1;
34
35struct pool {
36	struct fio_mutex *lock;			/* protects this pool */
37	void *map;				/* map of blocks */
38	unsigned int *bitmap;			/* blocks free/busy map */
39	unsigned int free_blocks;		/* free blocks */
40	unsigned int nr_blocks;			/* total blocks */
41	unsigned int next_non_full;
42	unsigned int mmap_size;
43};
44
45struct block_hdr {
46	unsigned int size;
47#ifdef SMALLOC_REDZONE
48	unsigned int prered;
49#endif
50};
51
52static struct pool mp[MAX_POOLS];
53static unsigned int nr_pools;
54static unsigned int last_pool;
55static struct fio_mutex *lock;
56
57static inline void pool_lock(struct pool *pool)
58{
59	fio_mutex_down(pool->lock);
60}
61
62static inline void pool_unlock(struct pool *pool)
63{
64	fio_mutex_up(pool->lock);
65}
66
67static inline void global_read_lock(void)
68{
69	fio_mutex_down_read(lock);
70}
71
72static inline void global_read_unlock(void)
73{
74	fio_mutex_up_read(lock);
75}
76
77static inline void global_write_lock(void)
78{
79	fio_mutex_down_write(lock);
80}
81
82static inline void global_write_unlock(void)
83{
84	fio_mutex_up_write(lock);
85}
86
87static inline int ptr_valid(struct pool *pool, void *ptr)
88{
89	unsigned int pool_size = pool->nr_blocks * SMALLOC_BPL;
90
91	return (ptr >= pool->map) && (ptr < pool->map + pool_size);
92}
93
94static inline unsigned int size_to_blocks(unsigned int size)
95{
96	return (size + SMALLOC_BPB - 1) / SMALLOC_BPB;
97}
98
99static int blocks_iter(struct pool *pool, unsigned int pool_idx,
100		       unsigned int idx, unsigned int nr_blocks,
101		       int (*func)(unsigned int *map, unsigned int mask))
102{
103
104	while (nr_blocks) {
105		unsigned int this_blocks, mask;
106		unsigned int *map;
107
108		if (pool_idx >= pool->nr_blocks)
109			return 0;
110
111		map = &pool->bitmap[pool_idx];
112
113		this_blocks = nr_blocks;
114		if (this_blocks + idx > SMALLOC_BPI) {
115			this_blocks = SMALLOC_BPI - idx;
116			idx = SMALLOC_BPI - this_blocks;
117		}
118
119		if (this_blocks == SMALLOC_BPI)
120			mask = -1U;
121		else
122			mask = ((1U << this_blocks) - 1) << idx;
123
124		if (!func(map, mask))
125			return 0;
126
127		nr_blocks -= this_blocks;
128		idx = 0;
129		pool_idx++;
130	}
131
132	return 1;
133}
134
135static int mask_cmp(unsigned int *map, unsigned int mask)
136{
137	return !(*map & mask);
138}
139
140static int mask_clear(unsigned int *map, unsigned int mask)
141{
142	assert((*map & mask) == mask);
143	*map &= ~mask;
144	return 1;
145}
146
147static int mask_set(unsigned int *map, unsigned int mask)
148{
149	assert(!(*map & mask));
150	*map |= mask;
151	return 1;
152}
153
154static int blocks_free(struct pool *pool, unsigned int pool_idx,
155		       unsigned int idx, unsigned int nr_blocks)
156{
157	return blocks_iter(pool, pool_idx, idx, nr_blocks, mask_cmp);
158}
159
160static void set_blocks(struct pool *pool, unsigned int pool_idx,
161		       unsigned int idx, unsigned int nr_blocks)
162{
163	blocks_iter(pool, pool_idx, idx, nr_blocks, mask_set);
164}
165
166static void clear_blocks(struct pool *pool, unsigned int pool_idx,
167			 unsigned int idx, unsigned int nr_blocks)
168{
169	blocks_iter(pool, pool_idx, idx, nr_blocks, mask_clear);
170}
171
172static int find_next_zero(int word, int start)
173{
174	assert(word != -1U);
175	word >>= start;
176	return ffz(word) + start;
177}
178
179static int add_pool(struct pool *pool, unsigned int alloc_size)
180{
181	int bitmap_blocks;
182	void *ptr;
183
184#ifdef SMALLOC_REDZONE
185	alloc_size += sizeof(unsigned int);
186#endif
187	alloc_size += sizeof(struct block_hdr);
188	if (alloc_size < INITIAL_SIZE)
189		alloc_size = INITIAL_SIZE;
190
191	/* round up to nearest full number of blocks */
192	alloc_size = (alloc_size + SMALLOC_BPL - 1) & ~(SMALLOC_BPL - 1);
193	bitmap_blocks = alloc_size / SMALLOC_BPL;
194	alloc_size += bitmap_blocks * sizeof(unsigned int);
195	pool->mmap_size = alloc_size;
196
197	pool->nr_blocks = bitmap_blocks;
198	pool->free_blocks = bitmap_blocks * SMALLOC_BPB;
199
200	ptr = mmap(NULL, alloc_size, PROT_READ|PROT_WRITE,
201			MAP_SHARED | OS_MAP_ANON, -1, 0);
202	if (ptr == MAP_FAILED)
203		goto out_fail;
204
205	memset(ptr, 0, alloc_size);
206	pool->map = ptr;
207	pool->bitmap = (void *) ptr + (pool->nr_blocks * SMALLOC_BPL);
208
209	pool->lock = fio_mutex_init(1);
210	if (!pool->lock)
211		goto out_fail;
212
213	nr_pools++;
214	return 0;
215out_fail:
216	fprintf(stderr, "smalloc: failed adding pool\n");
217	if (pool->map)
218		munmap(pool->map, pool->mmap_size);
219	return 1;
220}
221
222void sinit(void)
223{
224	int ret;
225
226	lock = fio_mutex_rw_init();
227	ret = add_pool(&mp[0], INITIAL_SIZE);
228	assert(!ret);
229}
230
231static void cleanup_pool(struct pool *pool)
232{
233	/*
234	 * This will also remove the temporary file we used as a backing
235	 * store, it was already unlinked
236	 */
237	munmap(pool->map, pool->mmap_size);
238
239	if (pool->lock)
240		fio_mutex_remove(pool->lock);
241}
242
243void scleanup(void)
244{
245	unsigned int i;
246
247	for (i = 0; i < nr_pools; i++)
248		cleanup_pool(&mp[i]);
249
250	if (lock)
251		fio_mutex_remove(lock);
252}
253
254#ifdef SMALLOC_REDZONE
255static void *postred_ptr(struct block_hdr *hdr)
256{
257	uintptr_t ptr;
258
259	ptr = (uintptr_t) hdr + hdr->size - sizeof(unsigned int);
260	ptr = (ptr + int_mask) & ~int_mask;
261
262	return (void *) ptr;
263}
264
265static void fill_redzone(struct block_hdr *hdr)
266{
267	unsigned int *postred = postred_ptr(hdr);
268
269	hdr->prered = SMALLOC_PRE_RED;
270	*postred = SMALLOC_POST_RED;
271}
272
273static void sfree_check_redzone(struct block_hdr *hdr)
274{
275	unsigned int *postred = postred_ptr(hdr);
276
277	if (hdr->prered != SMALLOC_PRE_RED) {
278		fprintf(stderr, "smalloc pre redzone destroyed!\n");
279		fprintf(stderr, "  ptr=%p, prered=%x, expected %x\n",
280				hdr, hdr->prered, SMALLOC_PRE_RED);
281		assert(0);
282	}
283	if (*postred != SMALLOC_POST_RED) {
284		fprintf(stderr, "smalloc post redzone destroyed!\n");
285		fprintf(stderr, "  ptr=%p, postred=%x, expected %x\n",
286				hdr, *postred, SMALLOC_POST_RED);
287		assert(0);
288	}
289}
290#else
291static void fill_redzone(struct block_hdr *hdr)
292{
293}
294
295static void sfree_check_redzone(struct block_hdr *hdr)
296{
297}
298#endif
299
300static void sfree_pool(struct pool *pool, void *ptr)
301{
302	struct block_hdr *hdr;
303	unsigned int i, idx;
304	unsigned long offset;
305
306	if (!ptr)
307		return;
308
309	ptr -= sizeof(*hdr);
310	hdr = ptr;
311
312	assert(ptr_valid(pool, ptr));
313
314	sfree_check_redzone(hdr);
315
316	offset = ptr - pool->map;
317	i = offset / SMALLOC_BPL;
318	idx = (offset % SMALLOC_BPL) / SMALLOC_BPB;
319
320	pool_lock(pool);
321	clear_blocks(pool, i, idx, size_to_blocks(hdr->size));
322	if (i < pool->next_non_full)
323		pool->next_non_full = i;
324	pool->free_blocks += size_to_blocks(hdr->size);
325	pool_unlock(pool);
326}
327
328void sfree(void *ptr)
329{
330	struct pool *pool = NULL;
331	unsigned int i;
332
333	if (!ptr)
334		return;
335
336	global_read_lock();
337
338	for (i = 0; i < nr_pools; i++) {
339		if (ptr_valid(&mp[i], ptr)) {
340			pool = &mp[i];
341			break;
342		}
343	}
344
345	global_read_unlock();
346
347	assert(pool);
348	sfree_pool(pool, ptr);
349}
350
351static void *__smalloc_pool(struct pool *pool, unsigned int size)
352{
353	unsigned int nr_blocks;
354	unsigned int i;
355	unsigned int offset;
356	unsigned int last_idx;
357	void *ret = NULL;
358
359	pool_lock(pool);
360
361	nr_blocks = size_to_blocks(size);
362	if (nr_blocks > pool->free_blocks)
363		goto fail;
364
365	i = pool->next_non_full;
366	last_idx = 0;
367	offset = -1U;
368	while (i < pool->nr_blocks) {
369		unsigned int idx;
370
371		if (pool->bitmap[i] == -1U) {
372			i++;
373			pool->next_non_full = i;
374			last_idx = 0;
375			continue;
376		}
377
378		idx = find_next_zero(pool->bitmap[i], last_idx);
379		if (!blocks_free(pool, i, idx, nr_blocks)) {
380			idx += nr_blocks;
381			if (idx < SMALLOC_BPI)
382				last_idx = idx;
383			else {
384				last_idx = 0;
385				while (idx >= SMALLOC_BPI) {
386					i++;
387					idx -= SMALLOC_BPI;
388				}
389			}
390			continue;
391		}
392		set_blocks(pool, i, idx, nr_blocks);
393		offset = i * SMALLOC_BPL + idx * SMALLOC_BPB;
394		break;
395	}
396
397	if (i < pool->nr_blocks) {
398		pool->free_blocks -= nr_blocks;
399		ret = pool->map + offset;
400	}
401fail:
402	pool_unlock(pool);
403	return ret;
404}
405
406static void *smalloc_pool(struct pool *pool, unsigned int size)
407{
408	unsigned int alloc_size = size + sizeof(struct block_hdr);
409	void *ptr;
410
411	/*
412	 * Round to int alignment, so that the postred pointer will
413	 * be naturally aligned as well.
414	 */
415#ifdef SMALLOC_REDZONE
416	alloc_size += sizeof(unsigned int);
417	alloc_size = (alloc_size + int_mask) & ~int_mask;
418#endif
419
420	ptr = __smalloc_pool(pool, alloc_size);
421	if (ptr) {
422		struct block_hdr *hdr = ptr;
423
424		hdr->size = alloc_size;
425		fill_redzone(hdr);
426
427		ptr += sizeof(*hdr);
428		memset(ptr, 0, size);
429	}
430
431	return ptr;
432}
433
434void *smalloc(unsigned int size)
435{
436	unsigned int i;
437
438	global_write_lock();
439	i = last_pool;
440
441	do {
442		for (; i < nr_pools; i++) {
443			void *ptr = smalloc_pool(&mp[i], size);
444
445			if (ptr) {
446				last_pool = i;
447				global_write_unlock();
448				return ptr;
449			}
450		}
451		if (last_pool) {
452			last_pool = 0;
453			continue;
454		}
455
456		if (nr_pools + 1 > MAX_POOLS)
457			break;
458		else {
459			i = nr_pools;
460			if (add_pool(&mp[nr_pools], size))
461				goto out;
462		}
463	} while (1);
464
465out:
466	global_write_unlock();
467	return NULL;
468}
469
470char *smalloc_strdup(const char *str)
471{
472	char *ptr;
473
474	ptr = smalloc(strlen(str) + 1);
475	strcpy(ptr, str);
476	return ptr;
477}
478