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