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 <assert.h>
7 #include <string.h>
8
9 #include "fio.h"
10 #include "fio_sem.h"
11 #include "os/os.h"
12 #include "smalloc.h"
13 #include "log.h"
14
15 #define SMALLOC_REDZONE /* define to detect memory corruption */
16
17 #define SMALLOC_BPB 32 /* block size, bytes-per-bit in bitmap */
18 #define SMALLOC_BPI (sizeof(unsigned int) * 8)
19 #define SMALLOC_BPL (SMALLOC_BPB * SMALLOC_BPI)
20
21 #define INITIAL_SIZE 16*1024*1024 /* new pool size */
22 #define INITIAL_POOLS 8 /* maximum number of pools to setup */
23
24 #define MAX_POOLS 16
25
26 #define SMALLOC_PRE_RED 0xdeadbeefU
27 #define SMALLOC_POST_RED 0x5aa55aa5U
28
29 unsigned int smalloc_pool_size = INITIAL_SIZE;
30 #ifdef SMALLOC_REDZONE
31 static const int int_mask = sizeof(int) - 1;
32 #endif
33
34 struct pool {
35 struct fio_sem *lock; /* protects this pool */
36 void *map; /* map of blocks */
37 unsigned int *bitmap; /* blocks free/busy map */
38 size_t free_blocks; /* free blocks */
39 size_t nr_blocks; /* total blocks */
40 size_t next_non_full;
41 size_t mmap_size;
42 };
43
44 struct block_hdr {
45 size_t size;
46 #ifdef SMALLOC_REDZONE
47 unsigned int prered;
48 #endif
49 };
50
51 /*
52 * This suppresses the voluminous potential bitmap printout when
53 * smalloc encounters an OOM error
54 */
55 static const bool enable_smalloc_debug = false;
56
57 static struct pool *mp;
58 static unsigned int nr_pools;
59 static unsigned int last_pool;
60
ptr_valid(struct pool * pool,void * ptr)61 static inline int ptr_valid(struct pool *pool, void *ptr)
62 {
63 unsigned int pool_size = pool->nr_blocks * SMALLOC_BPL;
64
65 return (ptr >= pool->map) && (ptr < pool->map + pool_size);
66 }
67
size_to_blocks(size_t size)68 static inline size_t size_to_blocks(size_t size)
69 {
70 return (size + SMALLOC_BPB - 1) / SMALLOC_BPB;
71 }
72
blocks_iter(struct pool * pool,unsigned int pool_idx,unsigned int idx,size_t nr_blocks,int (* func)(unsigned int * map,unsigned int mask))73 static int blocks_iter(struct pool *pool, unsigned int pool_idx,
74 unsigned int idx, size_t nr_blocks,
75 int (*func)(unsigned int *map, unsigned int mask))
76 {
77
78 while (nr_blocks) {
79 unsigned int this_blocks, mask;
80 unsigned int *map;
81
82 if (pool_idx >= pool->nr_blocks)
83 return 0;
84
85 map = &pool->bitmap[pool_idx];
86
87 this_blocks = nr_blocks;
88 if (this_blocks + idx > SMALLOC_BPI) {
89 this_blocks = SMALLOC_BPI - idx;
90 idx = SMALLOC_BPI - this_blocks;
91 }
92
93 if (this_blocks == SMALLOC_BPI)
94 mask = -1U;
95 else
96 mask = ((1U << this_blocks) - 1) << idx;
97
98 if (!func(map, mask))
99 return 0;
100
101 nr_blocks -= this_blocks;
102 idx = 0;
103 pool_idx++;
104 }
105
106 return 1;
107 }
108
mask_cmp(unsigned int * map,unsigned int mask)109 static int mask_cmp(unsigned int *map, unsigned int mask)
110 {
111 return !(*map & mask);
112 }
113
mask_clear(unsigned int * map,unsigned int mask)114 static int mask_clear(unsigned int *map, unsigned int mask)
115 {
116 assert((*map & mask) == mask);
117 *map &= ~mask;
118 return 1;
119 }
120
mask_set(unsigned int * map,unsigned int mask)121 static int mask_set(unsigned int *map, unsigned int mask)
122 {
123 assert(!(*map & mask));
124 *map |= mask;
125 return 1;
126 }
127
blocks_free(struct pool * pool,unsigned int pool_idx,unsigned int idx,size_t nr_blocks)128 static int blocks_free(struct pool *pool, unsigned int pool_idx,
129 unsigned int idx, size_t nr_blocks)
130 {
131 return blocks_iter(pool, pool_idx, idx, nr_blocks, mask_cmp);
132 }
133
set_blocks(struct pool * pool,unsigned int pool_idx,unsigned int idx,size_t nr_blocks)134 static void set_blocks(struct pool *pool, unsigned int pool_idx,
135 unsigned int idx, size_t nr_blocks)
136 {
137 blocks_iter(pool, pool_idx, idx, nr_blocks, mask_set);
138 }
139
clear_blocks(struct pool * pool,unsigned int pool_idx,unsigned int idx,size_t nr_blocks)140 static void clear_blocks(struct pool *pool, unsigned int pool_idx,
141 unsigned int idx, size_t nr_blocks)
142 {
143 blocks_iter(pool, pool_idx, idx, nr_blocks, mask_clear);
144 }
145
find_next_zero(int word,int start)146 static int find_next_zero(int word, int start)
147 {
148 assert(word != -1U);
149 word >>= start;
150 return ffz(word) + start;
151 }
152
add_pool(struct pool * pool,unsigned int alloc_size)153 static bool add_pool(struct pool *pool, unsigned int alloc_size)
154 {
155 int bitmap_blocks;
156 int mmap_flags;
157 void *ptr;
158
159 if (nr_pools == MAX_POOLS)
160 return false;
161
162 #ifdef SMALLOC_REDZONE
163 alloc_size += sizeof(unsigned int);
164 #endif
165 alloc_size += sizeof(struct block_hdr);
166 if (alloc_size < INITIAL_SIZE)
167 alloc_size = INITIAL_SIZE;
168
169 /* round up to nearest full number of blocks */
170 alloc_size = (alloc_size + SMALLOC_BPL - 1) & ~(SMALLOC_BPL - 1);
171 bitmap_blocks = alloc_size / SMALLOC_BPL;
172 alloc_size += bitmap_blocks * sizeof(unsigned int);
173 pool->mmap_size = alloc_size;
174
175 pool->nr_blocks = bitmap_blocks;
176 pool->free_blocks = bitmap_blocks * SMALLOC_BPI;
177
178 mmap_flags = OS_MAP_ANON;
179 #ifdef CONFIG_ESX
180 mmap_flags |= MAP_PRIVATE;
181 #else
182 mmap_flags |= MAP_SHARED;
183 #endif
184 ptr = mmap(NULL, alloc_size, PROT_READ|PROT_WRITE, mmap_flags, -1, 0);
185
186 if (ptr == MAP_FAILED)
187 goto out_fail;
188
189 pool->map = ptr;
190 pool->bitmap = (unsigned int *)((char *) ptr + (pool->nr_blocks * SMALLOC_BPL));
191 memset(pool->bitmap, 0, bitmap_blocks * sizeof(unsigned int));
192
193 pool->lock = fio_sem_init(FIO_SEM_UNLOCKED);
194 if (!pool->lock)
195 goto out_fail;
196
197 nr_pools++;
198 return true;
199 out_fail:
200 log_err("smalloc: failed adding pool\n");
201 if (pool->map)
202 munmap(pool->map, pool->mmap_size);
203 return false;
204 }
205
sinit(void)206 void sinit(void)
207 {
208 bool ret;
209 int i;
210
211 /*
212 * sinit() can be called more than once if alloc-size is
213 * set. But we want to allocate space for the struct pool
214 * instances only once.
215 */
216 if (!mp) {
217 mp = (struct pool *) mmap(NULL,
218 MAX_POOLS * sizeof(struct pool),
219 PROT_READ | PROT_WRITE,
220 OS_MAP_ANON | MAP_SHARED, -1, 0);
221
222 assert(mp != MAP_FAILED);
223 }
224
225 for (i = 0; i < INITIAL_POOLS; i++) {
226 ret = add_pool(&mp[nr_pools], smalloc_pool_size);
227 if (!ret)
228 break;
229 }
230
231 /*
232 * If we added at least one pool, we should be OK for most
233 * cases.
234 */
235 assert(i);
236 }
237
cleanup_pool(struct pool * pool)238 static void cleanup_pool(struct pool *pool)
239 {
240 /*
241 * This will also remove the temporary file we used as a backing
242 * store, it was already unlinked
243 */
244 munmap(pool->map, pool->mmap_size);
245
246 if (pool->lock)
247 fio_sem_remove(pool->lock);
248 }
249
scleanup(void)250 void scleanup(void)
251 {
252 unsigned int i;
253
254 for (i = 0; i < nr_pools; i++)
255 cleanup_pool(&mp[i]);
256
257 munmap(mp, MAX_POOLS * sizeof(struct pool));
258 }
259
260 #ifdef SMALLOC_REDZONE
postred_ptr(struct block_hdr * hdr)261 static void *postred_ptr(struct block_hdr *hdr)
262 {
263 uintptr_t ptr;
264
265 ptr = (uintptr_t) hdr + hdr->size - sizeof(unsigned int);
266 ptr = (uintptr_t) PTR_ALIGN(ptr, int_mask);
267
268 return (void *) ptr;
269 }
270
fill_redzone(struct block_hdr * hdr)271 static void fill_redzone(struct block_hdr *hdr)
272 {
273 unsigned int *postred = postred_ptr(hdr);
274
275 hdr->prered = SMALLOC_PRE_RED;
276 *postred = SMALLOC_POST_RED;
277 }
278
sfree_check_redzone(struct block_hdr * hdr)279 static void sfree_check_redzone(struct block_hdr *hdr)
280 {
281 unsigned int *postred = postred_ptr(hdr);
282
283 if (hdr->prered != SMALLOC_PRE_RED) {
284 log_err("smalloc pre redzone destroyed!\n"
285 " ptr=%p, prered=%x, expected %x\n",
286 hdr, hdr->prered, SMALLOC_PRE_RED);
287 assert(0);
288 }
289 if (*postred != SMALLOC_POST_RED) {
290 log_err("smalloc post redzone destroyed!\n"
291 " ptr=%p, postred=%x, expected %x\n",
292 hdr, *postred, SMALLOC_POST_RED);
293 assert(0);
294 }
295 }
296 #else
fill_redzone(struct block_hdr * hdr)297 static void fill_redzone(struct block_hdr *hdr)
298 {
299 }
300
sfree_check_redzone(struct block_hdr * hdr)301 static void sfree_check_redzone(struct block_hdr *hdr)
302 {
303 }
304 #endif
305
sfree_pool(struct pool * pool,void * ptr)306 static void sfree_pool(struct pool *pool, void *ptr)
307 {
308 struct block_hdr *hdr;
309 unsigned int i, idx;
310 unsigned long offset;
311
312 if (!ptr)
313 return;
314
315 ptr -= sizeof(*hdr);
316 hdr = ptr;
317
318 assert(ptr_valid(pool, ptr));
319
320 sfree_check_redzone(hdr);
321
322 offset = ptr - pool->map;
323 i = offset / SMALLOC_BPL;
324 idx = (offset % SMALLOC_BPL) / SMALLOC_BPB;
325
326 fio_sem_down(pool->lock);
327 clear_blocks(pool, i, idx, size_to_blocks(hdr->size));
328 if (i < pool->next_non_full)
329 pool->next_non_full = i;
330 pool->free_blocks += size_to_blocks(hdr->size);
331 fio_sem_up(pool->lock);
332 }
333
sfree(void * ptr)334 void sfree(void *ptr)
335 {
336 struct pool *pool = NULL;
337 unsigned int i;
338
339 if (!ptr)
340 return;
341
342 for (i = 0; i < nr_pools; i++) {
343 if (ptr_valid(&mp[i], ptr)) {
344 pool = &mp[i];
345 break;
346 }
347 }
348
349 if (pool) {
350 sfree_pool(pool, ptr);
351 return;
352 }
353
354 log_err("smalloc: ptr %p not from smalloc pool\n", ptr);
355 }
356
find_best_index(struct pool * pool)357 static unsigned int find_best_index(struct pool *pool)
358 {
359 unsigned int i;
360
361 assert(pool->free_blocks);
362
363 for (i = pool->next_non_full; pool->bitmap[i] == -1U; i++) {
364 if (i == pool->nr_blocks - 1) {
365 unsigned int j;
366
367 for (j = 0; j < pool->nr_blocks; j++)
368 if (pool->bitmap[j] != -1U)
369 return j;
370 }
371 }
372
373 return i;
374 }
375
__smalloc_pool(struct pool * pool,size_t size)376 static void *__smalloc_pool(struct pool *pool, size_t size)
377 {
378 size_t nr_blocks;
379 unsigned int i;
380 unsigned int offset;
381 unsigned int last_idx;
382 void *ret = NULL;
383
384 fio_sem_down(pool->lock);
385
386 nr_blocks = size_to_blocks(size);
387 if (nr_blocks > pool->free_blocks)
388 goto fail;
389
390 pool->next_non_full = find_best_index(pool);
391
392 last_idx = 0;
393 offset = -1U;
394 i = pool->next_non_full;
395 while (i < pool->nr_blocks) {
396 unsigned int idx;
397
398 if (pool->bitmap[i] == -1U) {
399 i++;
400 last_idx = 0;
401 continue;
402 }
403
404 idx = find_next_zero(pool->bitmap[i], last_idx);
405 if (!blocks_free(pool, i, idx, nr_blocks)) {
406 idx += nr_blocks;
407 if (idx < SMALLOC_BPI)
408 last_idx = idx;
409 else {
410 last_idx = 0;
411 while (idx >= SMALLOC_BPI) {
412 i++;
413 idx -= SMALLOC_BPI;
414 }
415 }
416 continue;
417 }
418 set_blocks(pool, i, idx, nr_blocks);
419 offset = i * SMALLOC_BPL + idx * SMALLOC_BPB;
420 break;
421 }
422
423 if (i < pool->nr_blocks) {
424 pool->free_blocks -= nr_blocks;
425 ret = pool->map + offset;
426 }
427 fail:
428 fio_sem_up(pool->lock);
429 return ret;
430 }
431
size_to_alloc_size(size_t size)432 static size_t size_to_alloc_size(size_t size)
433 {
434 size_t alloc_size = size + sizeof(struct block_hdr);
435
436 /*
437 * Round to int alignment, so that the postred pointer will
438 * be naturally aligned as well.
439 */
440 #ifdef SMALLOC_REDZONE
441 alloc_size += sizeof(unsigned int);
442 alloc_size = (alloc_size + int_mask) & ~int_mask;
443 #endif
444
445 return alloc_size;
446 }
447
smalloc_pool(struct pool * pool,size_t size)448 static void *smalloc_pool(struct pool *pool, size_t size)
449 {
450 size_t alloc_size = size_to_alloc_size(size);
451 void *ptr;
452
453 ptr = __smalloc_pool(pool, alloc_size);
454 if (ptr) {
455 struct block_hdr *hdr = ptr;
456
457 hdr->size = alloc_size;
458 fill_redzone(hdr);
459
460 ptr += sizeof(*hdr);
461 memset(ptr, 0, size);
462 }
463
464 return ptr;
465 }
466
smalloc_print_bitmap(struct pool * pool)467 static void smalloc_print_bitmap(struct pool *pool)
468 {
469 size_t nr_blocks = pool->nr_blocks;
470 unsigned int *bitmap = pool->bitmap;
471 unsigned int i, j;
472 char *buffer;
473
474 if (!enable_smalloc_debug)
475 return;
476
477 buffer = malloc(SMALLOC_BPI + 1);
478 if (!buffer)
479 return;
480 buffer[SMALLOC_BPI] = '\0';
481
482 for (i = 0; i < nr_blocks; i++) {
483 unsigned int line = bitmap[i];
484
485 /* skip completely full lines */
486 if (line == -1U)
487 continue;
488
489 for (j = 0; j < SMALLOC_BPI; j++)
490 if ((1 << j) & line)
491 buffer[SMALLOC_BPI-1-j] = '1';
492 else
493 buffer[SMALLOC_BPI-1-j] = '0';
494
495 log_err("smalloc: bitmap %5u, %s\n", i, buffer);
496 }
497
498 free(buffer);
499 }
500
smalloc_debug(size_t size)501 void smalloc_debug(size_t size)
502 {
503 unsigned int i;
504 size_t alloc_size = size_to_alloc_size(size);
505 size_t alloc_blocks;
506
507 alloc_blocks = size_to_blocks(alloc_size);
508
509 if (size)
510 log_err("smalloc: size = %lu, alloc_size = %lu, blocks = %lu\n",
511 (unsigned long) size, (unsigned long) alloc_size,
512 (unsigned long) alloc_blocks);
513 for (i = 0; i < nr_pools; i++) {
514 log_err("smalloc: pool %u, free/total blocks %u/%u\n", i,
515 (unsigned int) (mp[i].free_blocks),
516 (unsigned int) (mp[i].nr_blocks*sizeof(unsigned int)*8));
517 if (size && mp[i].free_blocks >= alloc_blocks) {
518 void *ptr = smalloc_pool(&mp[i], size);
519 if (ptr) {
520 sfree(ptr);
521 last_pool = i;
522 log_err("smalloc: smalloc_pool %u succeeded\n", i);
523 } else {
524 log_err("smalloc: smalloc_pool %u failed\n", i);
525 log_err("smalloc: next_non_full=%u, nr_blocks=%u\n",
526 (unsigned int) mp[i].next_non_full, (unsigned int) mp[i].nr_blocks);
527 smalloc_print_bitmap(&mp[i]);
528 }
529 }
530 }
531 }
532
smalloc(size_t size)533 void *smalloc(size_t size)
534 {
535 unsigned int i, end_pool;
536
537 if (size != (unsigned int) size)
538 return NULL;
539
540 i = last_pool;
541 end_pool = nr_pools;
542
543 do {
544 for (; i < end_pool; i++) {
545 void *ptr = smalloc_pool(&mp[i], size);
546
547 if (ptr) {
548 last_pool = i;
549 return ptr;
550 }
551 }
552 if (last_pool) {
553 end_pool = last_pool;
554 last_pool = i = 0;
555 continue;
556 }
557
558 break;
559 } while (1);
560
561 log_err("smalloc: OOM. Consider using --alloc-size to increase the "
562 "shared memory available.\n");
563 smalloc_debug(size);
564 return NULL;
565 }
566
scalloc(size_t nmemb,size_t size)567 void *scalloc(size_t nmemb, size_t size)
568 {
569 return smalloc(nmemb * size);
570 }
571
smalloc_strdup(const char * str)572 char *smalloc_strdup(const char *str)
573 {
574 char *ptr = NULL;
575
576 ptr = smalloc(strlen(str) + 1);
577 if (ptr)
578 strcpy(ptr, str);
579 return ptr;
580 }
581