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 }