Revamp file locking
[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 <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
14 #include "mutex.h"
15
16 #undef ENABLE_RESIZE            /* define to enable pool resizing */
17 #define MP_SAFE                 /* define to made allocator thread safe */
18
19 #define INITIAL_SIZE    65536   /* new pool size */
20 #define MAX_POOLS       32      /* maximum number of pools to setup */
21
22 #ifdef ENABLE_RESIZE
23 #define MAX_SIZE        8 * INITIAL_SIZE
24 static unsigned int resize_error;
25 #endif
26
27 struct pool {
28         struct fio_mutex *lock;                 /* protects this pool */
29         void *map;                              /* map of blocks */
30         void *last;                             /* next free block hint */
31         unsigned int size;                      /* size of pool */
32         unsigned int room;                      /* size left in pool */
33         unsigned int largest_block;             /* largest block free */
34         unsigned int free_since_compact;        /* sfree() since compact() */
35         int fd;                                 /* memory backing fd */
36         char file[PATH_MAX];                    /* filename for fd */
37 };
38
39 static struct pool mp[MAX_POOLS];
40 static unsigned int nr_pools;
41 static unsigned int last_pool;
42 static struct fio_mutex *lock;
43
44 struct mem_hdr {
45         unsigned int size;
46 };
47
48 static inline void pool_lock(struct pool *pool)
49 {
50         if (pool->lock)
51                 fio_mutex_down(pool->lock);
52 }
53
54 static inline void pool_unlock(struct pool *pool)
55 {
56         if (pool->lock)
57                 fio_mutex_up(pool->lock);
58 }
59
60 static inline void global_read_lock(void)
61 {
62         if (lock)
63                 fio_mutex_down_read(lock);
64 }
65
66 static inline void global_read_unlock(void)
67 {
68         if (lock)
69                 fio_mutex_up_read(lock);
70 }
71
72 static inline void global_write_lock(void)
73 {
74         if (lock)
75                 fio_mutex_down_write(lock);
76 }
77
78 static inline void global_write_unlock(void)
79 {
80         if (lock)
81                 fio_mutex_up_write(lock);
82 }
83
84 #define hdr_free(hdr)           ((hdr)->size & 0x80000000)
85 #define hdr_size(hdr)           ((hdr)->size & ~0x80000000)
86 #define hdr_mark_free(hdr)      ((hdr)->size |= 0x80000000)
87
88 static inline int ptr_valid(struct pool *pool, void *ptr)
89 {
90         return (ptr >= pool->map) && (ptr < pool->map + pool->size);
91 }
92
93 static inline int __hdr_valid(struct pool *pool, struct mem_hdr *hdr,
94                               unsigned int size)
95 {
96         return ptr_valid(pool, hdr) && ptr_valid(pool, (void *) hdr + size - 1);
97 }
98
99 static inline int hdr_valid(struct pool *pool, struct mem_hdr *hdr)
100 {
101         return __hdr_valid(pool, hdr, hdr_size(hdr));
102 }
103
104 static inline int region_free(struct mem_hdr *hdr)
105 {
106         return hdr_free(hdr) || (!hdr_free(hdr) && !hdr_size(hdr));
107 }
108
109 static inline struct mem_hdr *__hdr_nxt(struct pool *pool, struct mem_hdr *hdr,
110                                         unsigned int size)
111 {
112         struct mem_hdr *nxt = (void *) hdr + size + sizeof(*hdr);
113
114         if (__hdr_valid(pool, nxt, size))
115                 return nxt;
116
117         return NULL;
118 }
119
120 static inline struct mem_hdr *hdr_nxt(struct pool *pool, struct mem_hdr *hdr)
121 {
122         return __hdr_nxt(pool, hdr, hdr_size(hdr));
123 }
124
125 static void merge(struct pool *pool, struct mem_hdr *hdr, struct mem_hdr *nxt)
126 {
127         unsigned int hfree = hdr_free(hdr);
128         unsigned int nfree = hdr_free(nxt);
129
130         hdr->size = hdr_size(hdr) + hdr_size(nxt) + sizeof(*nxt);
131         nxt->size = 0;
132
133         if (hfree)
134                 hdr_mark_free(hdr);
135         if (nfree)
136                 hdr_mark_free(nxt);
137
138         if (pool->last == nxt)
139                 pool->last = hdr;
140 }
141
142 static int combine(struct pool *pool, struct mem_hdr *prv, struct mem_hdr *hdr)
143 {
144         if (prv && hdr_free(prv) && hdr_free(hdr)) {
145                 merge(pool, prv, hdr);
146                 return 1;
147         }
148
149         return 0;
150 }
151
152 static int compact_pool(struct pool *pool)
153 {
154         struct mem_hdr *hdr = pool->map, *nxt;
155         unsigned int compacted = 0;
156
157         if (pool->free_since_compact < 50)
158                 return 1;
159
160         while (hdr) {
161                 nxt = hdr_nxt(pool, hdr);
162                 if (!nxt)
163                         break;
164                 if (hdr_free(nxt) && hdr_free(hdr)) {
165                         merge(pool, hdr, nxt);
166                         compacted++;
167                         continue;
168                 }
169                 hdr = hdr_nxt(pool, hdr);
170         }
171
172         pool->free_since_compact = 0;
173         return !!compacted;
174 }
175
176 static int resize_pool(struct pool *pool)
177 {
178 #ifdef ENABLE_RESIZE
179         unsigned int new_size = pool->size << 1;
180         struct mem_hdr *hdr, *last_hdr;
181         void *ptr;
182
183         if (new_size >= MAX_SIZE || resize_error)
184                 return 1;
185
186         if (ftruncate(pool->fd, new_size) < 0)
187                 goto fail;
188
189         ptr = mremap(pool->map, pool->size, new_size, 0);
190         if (ptr == MAP_FAILED)
191                 goto fail;
192
193         pool->map = ptr;
194         hdr = pool;
195         do {
196                 last_hdr = hdr;
197         } while ((hdr = hdr_nxt(hdr)) != NULL);
198
199         if (hdr_free(last_hdr)) {
200                 last_hdr->size = hdr_size(last_hdr) + new_size - pool_size;
201                 hdr_mark_free(last_hdr);
202         } else {
203                 struct mem_hdr *nxt;
204
205                 nxt = (void *) last_hdr + hdr_size(last_hdr) + sizeof(*hdr);
206                 nxt->size = new_size - pool_size - sizeof(*hdr);
207                 hdr_mark_free(nxt);
208         }
209
210         pool_room += new_size - pool_size;
211         pool_size = new_size;
212         return 0;
213 fail:
214         perror("resize");
215         resize_error = 1;
216 #else
217         return 1;
218 #endif
219 }
220
221 static int add_pool(struct pool *pool)
222 {
223         struct mem_hdr *hdr;
224         void *ptr;
225         int fd;
226
227         strcpy(pool->file, "/tmp/.fio_smalloc.XXXXXX");
228         fd = mkstemp(pool->file);
229         if (fd < 0)
230                 goto out_close;
231
232         pool->size = INITIAL_SIZE;
233         if (ftruncate(fd, pool->size) < 0)
234                 goto out_unlink;
235
236         ptr = mmap(NULL, pool->size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
237         if (ptr == MAP_FAILED)
238                 goto out_unlink;
239
240         memset(ptr, 0, pool->size);
241         pool->map = pool->last = ptr;
242
243 #ifdef MP_SAFE
244         pool->lock = fio_mutex_init(1);
245         if (!pool->lock)
246                 goto out_unlink;
247 #endif
248
249         pool->fd = fd;
250
251         hdr = pool->map;
252         pool->room = hdr->size = pool->size - sizeof(*hdr);
253         pool->largest_block = pool->room;
254         hdr_mark_free(hdr);
255         global_write_lock();
256         nr_pools++;
257         global_write_unlock();
258         return 0;
259 out_unlink:
260         if (pool->map)
261                 munmap(pool->map, pool->size);
262         unlink(pool->file);
263 out_close:
264         if (fd >= 0)
265                 close(fd);
266         return 1;
267 }
268
269 void sinit(void)
270 {
271         int ret;
272
273 #ifdef MP_SAFE
274         lock = fio_mutex_rw_init();
275 #endif
276         ret = add_pool(&mp[0]);
277         assert(!ret);
278 }
279
280 static void cleanup_pool(struct pool *pool)
281 {
282         unlink(pool->file);
283         close(pool->fd);
284         munmap(pool->map, pool->size);
285
286         if (pool->lock)
287                 fio_mutex_remove(pool->lock);
288 }
289
290 void scleanup(void)
291 {
292         unsigned int i;
293
294         for (i = 0; i < nr_pools; i++)
295                 cleanup_pool(&mp[i]);
296
297         if (lock)
298                 fio_mutex_remove(lock);
299 }
300
301 static void sfree_pool(struct pool *pool, void *ptr)
302 {
303         struct mem_hdr *hdr, *nxt;
304
305         if (!ptr)
306                 return;
307
308         assert(ptr_valid(pool, ptr));
309
310         pool_lock(pool);
311         hdr = ptr - sizeof(*hdr);
312         assert(!hdr_free(hdr));
313         hdr_mark_free(hdr);
314         pool->room -= hdr_size(hdr);
315
316         nxt = hdr_nxt(pool, hdr);
317         if (nxt && hdr_free(nxt))
318                 merge(pool, hdr, nxt);
319
320         if (hdr_size(hdr) > pool->largest_block)
321                 pool->largest_block = hdr_size(hdr);
322
323         pool->free_since_compact++;
324         pool_unlock(pool);
325 }
326
327 void sfree(void *ptr)
328 {
329         struct pool *pool = NULL;
330         unsigned int i;
331
332         global_read_lock();
333
334         for (i = 0; i < nr_pools; i++) {
335                 if (ptr_valid(&mp[i], ptr)) {
336                         pool = &mp[i];
337                         break;
338                 }
339         }
340
341         global_read_unlock();
342
343         assert(pool);
344         sfree_pool(pool, ptr);
345 }
346
347 static void *smalloc_pool(struct pool *pool, unsigned int size)
348 {
349         struct mem_hdr *hdr, *prv;
350         int did_restart = 0;
351         void *ret;
352
353         /*
354          * slight chance of race with sfree() here, but acceptable
355          */
356         if (!size || size > pool->room + sizeof(*hdr) ||
357             ((size > pool->largest_block) && pool->largest_block))
358                 return NULL;
359
360         pool_lock(pool);
361 restart:
362         hdr = pool->last;
363         prv = NULL;
364         do {
365                 if (combine(pool, prv, hdr))
366                         hdr = prv;
367                         
368                 if (hdr_free(hdr) && hdr_size(hdr) >= size)
369                         break;
370
371                 prv = hdr;
372         } while ((hdr = hdr_nxt(pool, hdr)) != NULL);
373
374         if (!hdr)
375                 goto fail;
376
377         /*
378          * more room, adjust next header if any
379          */
380         if (hdr_size(hdr) - size >= 2 * sizeof(*hdr)) {
381                 struct mem_hdr *nxt = __hdr_nxt(pool, hdr, size);
382
383                 if (nxt) {
384                         nxt->size = hdr_size(hdr) - size - sizeof(*hdr);
385                         if (hdr_size(hdr) == pool->largest_block)
386                                 pool->largest_block = hdr_size(nxt);
387                         hdr_mark_free(nxt);
388                 } else
389                         size = hdr_size(hdr);
390         } else
391                 size = hdr_size(hdr);
392
393         if (size == hdr_size(hdr) && size == pool->largest_block)
394                 pool->largest_block = 0;
395
396         /*
397          * also clears free bit
398          */
399         hdr->size = size;
400         pool->last = hdr_nxt(pool, hdr);
401         if (!pool->last)
402                 pool->last = pool->map;
403         pool->room -= size;
404         pool_unlock(pool);
405
406         ret = (void *) hdr + sizeof(*hdr);
407         memset(ret, 0, size);
408         return ret;
409 fail:
410         /*
411          * if we fail to allocate, first compact the entries that we missed.
412          * if that also fails, increase the size of the pool
413          */
414         ++did_restart;
415         if (did_restart <= 1) {
416                 if (!compact_pool(pool)) {
417                         pool->last = pool->map;
418                         goto restart;
419                 }
420         }
421         ++did_restart;
422         if (did_restart <= 2) {
423                 if (!resize_pool(pool)) {
424                         pool->last = pool->map;
425                         goto restart;
426                 }
427         }
428         pool_unlock(pool);
429         return NULL;
430 }
431
432 void *smalloc(unsigned int size)
433 {
434         unsigned int i;
435
436         global_read_lock();
437         i = last_pool;
438
439         do {
440                 for (; i < nr_pools; i++) {
441                         void *ptr = smalloc_pool(&mp[i], size);
442
443                         if (ptr) {
444                                 last_pool = i;
445                                 global_read_unlock();
446                                 return ptr;
447                         }
448                 }
449                 if (last_pool) {
450                         last_pool = 0;
451                         continue;
452                 }
453
454                 if (nr_pools + 1 >= MAX_POOLS)
455                         break;
456                 else {
457                         i = nr_pools;
458                         global_read_unlock();
459                         if (add_pool(&mp[nr_pools]))
460                                 goto out;
461                         global_read_lock();
462                 }
463         } while (1);
464
465         global_read_unlock();
466 out:
467         return NULL;
468 }
469
470 char *smalloc_strdup(const char *str)
471 {
472         char *ptr;
473
474         ptr = smalloc(strlen(str) + 1);
475         strcpy(ptr, str);
476         return ptr;
477 }