2 * simple memory allocator, backed by mmap() so that it hands out memory
3 * that can be shared across processes and threads
11 #include <sys/types.h>
16 #undef ENABLE_RESIZE /* define to enable pool resizing */
17 #define MP_SAFE /* define to made allocator thread safe */
19 #define INITIAL_SIZE 65536 /* new pool size */
20 #define MAX_POOLS 32 /* maximum number of pools to setup */
23 #define MAX_SIZE 8 * INITIAL_SIZE
24 static unsigned int resize_error;
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 */
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;
48 static inline void pool_lock(struct pool *pool)
51 fio_mutex_down(pool->lock);
54 static inline void pool_unlock(struct pool *pool)
57 fio_mutex_up(pool->lock);
60 static inline void global_read_lock(void)
63 fio_mutex_down_read(lock);
66 static inline void global_read_unlock(void)
69 fio_mutex_up_read(lock);
72 static inline void global_write_lock(void)
75 fio_mutex_down_write(lock);
78 static inline void global_write_unlock(void)
81 fio_mutex_up_write(lock);
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)
88 static inline int ptr_valid(struct pool *pool, void *ptr)
90 return (ptr >= pool->map) && (ptr < pool->map + pool->size);
93 static inline int __hdr_valid(struct pool *pool, struct mem_hdr *hdr,
96 return ptr_valid(pool, hdr) && ptr_valid(pool, (void *) hdr + size - 1);
99 static inline int hdr_valid(struct pool *pool, struct mem_hdr *hdr)
101 return __hdr_valid(pool, hdr, hdr_size(hdr));
104 static inline int region_free(struct mem_hdr *hdr)
106 return hdr_free(hdr) || (!hdr_free(hdr) && !hdr_size(hdr));
109 static inline struct mem_hdr *__hdr_nxt(struct pool *pool, struct mem_hdr *hdr,
112 struct mem_hdr *nxt = (void *) hdr + size + sizeof(*hdr);
114 if (__hdr_valid(pool, nxt, size))
120 static inline struct mem_hdr *hdr_nxt(struct pool *pool, struct mem_hdr *hdr)
122 return __hdr_nxt(pool, hdr, hdr_size(hdr));
125 static void merge(struct pool *pool, struct mem_hdr *hdr, struct mem_hdr *nxt)
127 unsigned int hfree = hdr_free(hdr);
128 unsigned int nfree = hdr_free(nxt);
130 hdr->size = hdr_size(hdr) + hdr_size(nxt) + sizeof(*nxt);
138 if (pool->last == nxt)
142 static int combine(struct pool *pool, struct mem_hdr *prv, struct mem_hdr *hdr)
144 if (prv && hdr_free(prv) && hdr_free(hdr)) {
145 merge(pool, prv, hdr);
152 static int compact_pool(struct pool *pool)
154 struct mem_hdr *hdr = pool->map, *nxt;
155 unsigned int compacted = 0;
157 if (pool->free_since_compact < 50)
161 nxt = hdr_nxt(pool, hdr);
164 if (hdr_free(nxt) && hdr_free(hdr)) {
165 merge(pool, hdr, nxt);
169 hdr = hdr_nxt(pool, hdr);
172 pool->free_since_compact = 0;
176 static int resize_pool(struct pool *pool)
179 unsigned int new_size = pool->size << 1;
180 struct mem_hdr *hdr, *last_hdr;
183 if (new_size >= MAX_SIZE || resize_error)
186 if (ftruncate(pool->fd, new_size) < 0)
189 ptr = mremap(pool->map, pool->size, new_size, 0);
190 if (ptr == MAP_FAILED)
197 } while ((hdr = hdr_nxt(hdr)) != NULL);
199 if (hdr_free(last_hdr)) {
200 last_hdr->size = hdr_size(last_hdr) + new_size - pool_size;
201 hdr_mark_free(last_hdr);
205 nxt = (void *) last_hdr + hdr_size(last_hdr) + sizeof(*hdr);
206 nxt->size = new_size - pool_size - sizeof(*hdr);
210 pool_room += new_size - pool_size;
211 pool_size = new_size;
221 static int add_pool(struct pool *pool)
227 strcpy(pool->file, "/tmp/.fio_smalloc.XXXXXX");
228 fd = mkstemp(pool->file);
232 pool->size = INITIAL_SIZE;
233 if (ftruncate(fd, pool->size) < 0)
236 ptr = mmap(NULL, pool->size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
237 if (ptr == MAP_FAILED)
240 memset(ptr, 0, pool->size);
241 pool->map = pool->last = ptr;
244 pool->lock = fio_mutex_init(1);
252 pool->room = hdr->size = pool->size - sizeof(*hdr);
253 pool->largest_block = pool->room;
257 global_write_unlock();
261 munmap(pool->map, pool->size);
274 lock = fio_mutex_rw_init();
276 ret = add_pool(&mp[0]);
280 static void cleanup_pool(struct pool *pool)
284 munmap(pool->map, pool->size);
287 fio_mutex_remove(pool->lock);
294 for (i = 0; i < nr_pools; i++)
295 cleanup_pool(&mp[i]);
298 fio_mutex_remove(lock);
301 static void sfree_pool(struct pool *pool, void *ptr)
303 struct mem_hdr *hdr, *nxt;
308 assert(ptr_valid(pool, ptr));
311 hdr = ptr - sizeof(*hdr);
312 assert(!hdr_free(hdr));
314 pool->room -= hdr_size(hdr);
316 nxt = hdr_nxt(pool, hdr);
317 if (nxt && hdr_free(nxt))
318 merge(pool, hdr, nxt);
320 if (hdr_size(hdr) > pool->largest_block)
321 pool->largest_block = hdr_size(hdr);
323 pool->free_since_compact++;
327 void sfree(void *ptr)
329 struct pool *pool = NULL;
334 for (i = 0; i < nr_pools; i++) {
335 if (ptr_valid(&mp[i], ptr)) {
341 global_read_unlock();
344 sfree_pool(pool, ptr);
347 static void *smalloc_pool(struct pool *pool, unsigned int size)
349 struct mem_hdr *hdr, *prv;
354 * slight chance of race with sfree() here, but acceptable
356 if (!size || size > pool->room + sizeof(*hdr) ||
357 ((size > pool->largest_block) && pool->largest_block))
365 if (combine(pool, prv, hdr))
368 if (hdr_free(hdr) && hdr_size(hdr) >= size)
372 } while ((hdr = hdr_nxt(pool, hdr)) != NULL);
378 * more room, adjust next header if any
380 if (hdr_size(hdr) - size >= 2 * sizeof(*hdr)) {
381 struct mem_hdr *nxt = __hdr_nxt(pool, hdr, size);
384 nxt->size = hdr_size(hdr) - size - sizeof(*hdr);
385 if (hdr_size(hdr) == pool->largest_block)
386 pool->largest_block = hdr_size(nxt);
389 size = hdr_size(hdr);
391 size = hdr_size(hdr);
393 if (size == hdr_size(hdr) && size == pool->largest_block)
394 pool->largest_block = 0;
397 * also clears free bit
400 pool->last = hdr_nxt(pool, hdr);
402 pool->last = pool->map;
406 ret = (void *) hdr + sizeof(*hdr);
407 memset(ret, 0, size);
411 * if we fail to allocate, first compact the entries that we missed.
412 * if that also fails, increase the size of the pool
415 if (did_restart <= 1) {
416 if (!compact_pool(pool)) {
417 pool->last = pool->map;
422 if (did_restart <= 2) {
423 if (!resize_pool(pool)) {
424 pool->last = pool->map;
432 void *smalloc(unsigned int size)
440 for (; i < nr_pools; i++) {
441 void *ptr = smalloc_pool(&mp[i], size);
445 global_read_unlock();
454 if (nr_pools + 1 >= MAX_POOLS)
458 global_read_unlock();
459 if (add_pool(&mp[nr_pools]))
465 global_read_unlock();
470 char *smalloc_strdup(const char *str)
474 ptr = smalloc(strlen(str) + 1);