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