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