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