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