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