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