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 <assert.h>
   7 #include <string.h>
   8
   9 #include "fio.h"
  10 #include "fio_sem.h"
  11 #include "os/os.h"
  12 #include "smalloc.h"
  13 #include "log.h"
  14
  15 #define SMALLOC_REDZONE         /* define to detect memory corruption */
  16
  17 #define SMALLOC_BPB     32      /* block size, bytes-per-bit in bitmap */
  18 #define SMALLOC_BPI     (sizeof(unsigned int) * 8)
  19 #define SMALLOC_BPL     (SMALLOC_BPB * SMALLOC_BPI)
  20
  21 #define INITIAL_SIZE    16*1024*1024    /* new pool size */
  22 #define INITIAL_POOLS   8               /* maximum number of pools to setup */
  23
  24 #define MAX_POOLS       16
  25
  26 #define SMALLOC_PRE_RED         0xdeadbeefU
  27 #define SMALLOC_POST_RED        0x5aa55aa5U
  28
  29 unsigned int smalloc_pool_size = INITIAL_SIZE;
  30 #ifdef SMALLOC_REDZONE
  31 static const int int_mask = sizeof(int) - 1;
  32 #endif
  33
  34 struct pool {
  35         struct fio_sem *lock;                   /* protects this pool */
  36         void *map;                              /* map of blocks */
  37         unsigned int *bitmap;                   /* blocks free/busy map */
  38         size_t free_blocks;             /* free blocks */
  39         size_t nr_blocks;                       /* total blocks */
  40         size_t next_non_full;
  41         size_t mmap_size;
  42 };
  43
  44 struct block_hdr {
  45         size_t size;
  46 #ifdef SMALLOC_REDZONE
  47         unsigned int prered;
  48 #endif
  49 };
  50
  51 static struct pool mp[MAX_POOLS];
  52 static unsigned int nr_pools;
  53 static unsigned int last_pool;
  54
  55 static inline int ptr_valid(struct pool *pool, void *ptr)
  56 {
  57         unsigned int pool_size = pool->nr_blocks * SMALLOC_BPL;
  58
  59         return (ptr >= pool->map) && (ptr < pool->map + pool_size);
  60 }
  61
  62 static inline size_t size_to_blocks(size_t size)
  63 {
  64         return (size + SMALLOC_BPB - 1) / SMALLOC_BPB;
  65 }
  66
  67 static int blocks_iter(struct pool *pool, unsigned int pool_idx,
  68                        unsigned int idx, size_t nr_blocks,
  69                        int (*func)(unsigned int *map, unsigned int mask))
  70 {
  71
  72         while (nr_blocks) {
  73                 unsigned int this_blocks, mask;
  74                 unsigned int *map;
  75
  76                 if (pool_idx >= pool->nr_blocks)
  77                         return 0;
  78
  79                 map = &pool->bitmap[pool_idx];
  80
  81                 this_blocks = nr_blocks;
  82                 if (this_blocks + idx > SMALLOC_BPI) {
  83                         this_blocks = SMALLOC_BPI - idx;
  84                         idx = SMALLOC_BPI - this_blocks;
  85                 }
  86
  87                 if (this_blocks == SMALLOC_BPI)
  88                         mask = -1U;
  89                 else
  90                         mask = ((1U << this_blocks) - 1) << idx;
  91
  92                 if (!func(map, mask))
  93                         return 0;
  94
  95                 nr_blocks -= this_blocks;
  96                 idx = 0;
  97                 pool_idx++;
  98         }
  99
 100         return 1;
 101 }
 102
 103 static int mask_cmp(unsigned int *map, unsigned int mask)
 104 {
 105         return !(*map & mask);
 106 }
 107
 108 static int mask_clear(unsigned int *map, unsigned int mask)
 109 {
 110         assert((*map & mask) == mask);
 111         *map &= ~mask;
 112         return 1;
 113 }
 114
 115 static int mask_set(unsigned int *map, unsigned int mask)
 116 {
 117         assert(!(*map & mask));
 118         *map |= mask;
 119         return 1;
 120 }
 121
 122 static int blocks_free(struct pool *pool, unsigned int pool_idx,
 123                        unsigned int idx, size_t nr_blocks)
 124 {
 125         return blocks_iter(pool, pool_idx, idx, nr_blocks, mask_cmp);
 126 }
 127
 128 static void set_blocks(struct pool *pool, unsigned int pool_idx,
 129                        unsigned int idx, size_t nr_blocks)
 130 {
 131         blocks_iter(pool, pool_idx, idx, nr_blocks, mask_set);
 132 }
 133
 134 static void clear_blocks(struct pool *pool, unsigned int pool_idx,
 135                          unsigned int idx, size_t nr_blocks)
 136 {
 137         blocks_iter(pool, pool_idx, idx, nr_blocks, mask_clear);
 138 }
 139
 140 static int find_next_zero(int word, int start)
 141 {
 142         assert(word != -1U);
 143         word >>= start;
 144         return ffz(word) + start;
 145 }
 146
 147 static bool add_pool(struct pool *pool, unsigned int alloc_size)
 148 {
 149         int bitmap_blocks;
 150         int mmap_flags;
 151         void *ptr;
 152
 153         if (nr_pools == MAX_POOLS)
 154                 return false;
 155
 156 #ifdef SMALLOC_REDZONE
 157         alloc_size += sizeof(unsigned int);
 158 #endif
 159         alloc_size += sizeof(struct block_hdr);
 160         if (alloc_size < INITIAL_SIZE)
 161                 alloc_size = INITIAL_SIZE;
 162
 163         /* round up to nearest full number of blocks */
 164         alloc_size = (alloc_size + SMALLOC_BPL - 1) & ~(SMALLOC_BPL - 1);
 165         bitmap_blocks = alloc_size / SMALLOC_BPL;
 166         alloc_size += bitmap_blocks * sizeof(unsigned int);
 167         pool->mmap_size = alloc_size;
 168
 169         pool->nr_blocks = bitmap_blocks;
 170         pool->free_blocks = bitmap_blocks * SMALLOC_BPB;
 171
 172         mmap_flags = OS_MAP_ANON;
 173 #ifdef CONFIG_ESX
 174         mmap_flags |= MAP_PRIVATE;
 175 #else
 176         mmap_flags |= MAP_SHARED;
 177 #endif
 178         ptr = mmap(NULL, alloc_size, PROT_READ|PROT_WRITE, mmap_flags, -1, 0);
 179
 180         if (ptr == MAP_FAILED)
 181                 goto out_fail;
 182
 183         pool->map = ptr;
 184         pool->bitmap = (unsigned int *)((char *) ptr + (pool->nr_blocks * SMALLOC_BPL));
 185         memset(pool->bitmap, 0, bitmap_blocks * sizeof(unsigned int));
 186
 187         pool->lock = fio_sem_init(FIO_SEM_UNLOCKED);
 188         if (!pool->lock)
 189                 goto out_fail;
 190
 191         nr_pools++;
 192         return true;
 193 out_fail:
 194         log_err("smalloc: failed adding pool\n");
 195         if (pool->map)
 196                 munmap(pool->map, pool->mmap_size);
 197         return false;
 198 }
 199
 200 void sinit(void)
 201 {
 202         bool ret;
 203         int i;
 204
 205         for (i = 0; i < INITIAL_POOLS; i++) {
 206                 ret = add_pool(&mp[nr_pools], smalloc_pool_size);
 207                 if (!ret)
 208                         break;
 209         }
 210
 211         /*
 212          * If we added at least one pool, we should be OK for most
 213          * cases.
 214          */
 215         assert(i);
 216 }
 217
 218 static void cleanup_pool(struct pool *pool)
 219 {
 220         /*
 221          * This will also remove the temporary file we used as a backing
 222          * store, it was already unlinked
 223          */
 224         munmap(pool->map, pool->mmap_size);
 225
 226         if (pool->lock)
 227                 fio_sem_remove(pool->lock);
 228 }
 229
 230 void scleanup(void)
 231 {
 232         unsigned int i;
 233
 234         for (i = 0; i < nr_pools; i++)
 235                 cleanup_pool(&mp[i]);
 236 }
 237
 238 #ifdef SMALLOC_REDZONE
 239 static void *postred_ptr(struct block_hdr *hdr)
 240 {
 241         uintptr_t ptr;
 242
 243         ptr = (uintptr_t) hdr + hdr->size - sizeof(unsigned int);
 244         ptr = (uintptr_t) PTR_ALIGN(ptr, int_mask);
 245
 246         return (void *) ptr;
 247 }
 248
 249 static void fill_redzone(struct block_hdr *hdr)
 250 {
 251         unsigned int *postred = postred_ptr(hdr);
 252
 253         hdr->prered = SMALLOC_PRE_RED;
 254         *postred = SMALLOC_POST_RED;
 255 }
 256
 257 static void sfree_check_redzone(struct block_hdr *hdr)
 258 {
 259         unsigned int *postred = postred_ptr(hdr);
 260
 261         if (hdr->prered != SMALLOC_PRE_RED) {
 262                 log_err("smalloc pre redzone destroyed!\n"
 263                         " ptr=%p, prered=%x, expected %x\n",
 264                                 hdr, hdr->prered, SMALLOC_PRE_RED);
 265                 assert(0);
 266         }
 267         if (*postred != SMALLOC_POST_RED) {
 268                 log_err("smalloc post redzone destroyed!\n"
 269                         "  ptr=%p, postred=%x, expected %x\n",
 270                                 hdr, *postred, SMALLOC_POST_RED);
 271                 assert(0);
 272         }
 273 }
 274 #else
 275 static void fill_redzone(struct block_hdr *hdr)
 276 {
 277 }
 278
 279 static void sfree_check_redzone(struct block_hdr *hdr)
 280 {
 281 }
 282 #endif
 283
 284 static void sfree_pool(struct pool *pool, void *ptr)
 285 {
 286         struct block_hdr *hdr;
 287         unsigned int i, idx;
 288         unsigned long offset;
 289
 290         if (!ptr)
 291                 return;
 292
 293         ptr -= sizeof(*hdr);
 294         hdr = ptr;
 295
 296         assert(ptr_valid(pool, ptr));
 297
 298         sfree_check_redzone(hdr);
 299
 300         offset = ptr - pool->map;
 301         i = offset / SMALLOC_BPL;
 302         idx = (offset % SMALLOC_BPL) / SMALLOC_BPB;
 303
 304         fio_sem_down(pool->lock);
 305         clear_blocks(pool, i, idx, size_to_blocks(hdr->size));
 306         if (i < pool->next_non_full)
 307                 pool->next_non_full = i;
 308         pool->free_blocks += size_to_blocks(hdr->size);
 309         fio_sem_up(pool->lock);
 310 }
 311
 312 void sfree(void *ptr)
 313 {
 314         struct pool *pool = NULL;
 315         unsigned int i;
 316
 317         if (!ptr)
 318                 return;
 319
 320         for (i = 0; i < nr_pools; i++) {
 321                 if (ptr_valid(&mp[i], ptr)) {
 322                         pool = &mp[i];
 323                         break;
 324                 }
 325         }
 326
 327         if (pool) {
 328                 sfree_pool(pool, ptr);
 329                 return;
 330         }
 331
 332         log_err("smalloc: ptr %p not from smalloc pool\n", ptr);
 333 }
 334
 335 static void *__smalloc_pool(struct pool *pool, size_t size)
 336 {
 337         size_t nr_blocks;
 338         unsigned int i;
 339         unsigned int offset;
 340         unsigned int last_idx;
 341         void *ret = NULL;
 342
 343         fio_sem_down(pool->lock);
 344
 345         nr_blocks = size_to_blocks(size);
 346         if (nr_blocks > pool->free_blocks)
 347                 goto fail;
 348
 349         i = pool->next_non_full;
 350         last_idx = 0;
 351         offset = -1U;
 352         while (i < pool->nr_blocks) {
 353                 unsigned int idx;
 354
 355                 if (pool->bitmap[i] == -1U) {
 356                         i++;
 357                         pool->next_non_full = i;
 358                         last_idx = 0;
 359                         continue;
 360                 }
 361
 362                 idx = find_next_zero(pool->bitmap[i], last_idx);
 363                 if (!blocks_free(pool, i, idx, nr_blocks)) {
 364                         idx += nr_blocks;
 365                         if (idx < SMALLOC_BPI)
 366                                 last_idx = idx;
 367                         else {
 368                                 last_idx = 0;
 369                                 while (idx >= SMALLOC_BPI) {
 370                                         i++;
 371                                         idx -= SMALLOC_BPI;
 372                                 }
 373                         }
 374                         continue;
 375                 }
 376                 set_blocks(pool, i, idx, nr_blocks);
 377                 offset = i * SMALLOC_BPL + idx * SMALLOC_BPB;
 378                 break;
 379         }
 380
 381         if (i < pool->nr_blocks) {
 382                 pool->free_blocks -= nr_blocks;
 383                 ret = pool->map + offset;
 384         }
 385 fail:
 386         fio_sem_up(pool->lock);
 387         return ret;
 388 }
 389
 390 static void *smalloc_pool(struct pool *pool, size_t size)
 391 {
 392         size_t alloc_size = size + sizeof(struct block_hdr);
 393         void *ptr;
 394
 395         /*
 396          * Round to int alignment, so that the postred pointer will
 397          * be naturally aligned as well.
 398          */
 399 #ifdef SMALLOC_REDZONE
 400         alloc_size += sizeof(unsigned int);
 401         alloc_size = (alloc_size + int_mask) & ~int_mask;
 402 #endif
 403
 404         ptr = __smalloc_pool(pool, alloc_size);
 405         if (ptr) {
 406                 struct block_hdr *hdr = ptr;
 407
 408                 hdr->size = alloc_size;
 409                 fill_redzone(hdr);
 410
 411                 ptr += sizeof(*hdr);
 412                 memset(ptr, 0, size);
 413         }
 414
 415         return ptr;
 416 }
 417
 418 void *smalloc(size_t size)
 419 {
 420         unsigned int i, end_pool;
 421
 422         if (size != (unsigned int) size)
 423                 return NULL;
 424
 425         i = last_pool;
 426         end_pool = nr_pools;
 427
 428         do {
 429                 for (; i < end_pool; i++) {
 430                         void *ptr = smalloc_pool(&mp[i], size);
 431
 432                         if (ptr) {
 433                                 last_pool = i;
 434                                 return ptr;
 435                         }
 436                 }
 437                 if (last_pool) {
 438                         end_pool = last_pool;
 439                         last_pool = i = 0;
 440                         continue;
 441                 }
 442
 443                 break;
 444         } while (1);
 445
 446         log_err("smalloc: OOM. Consider using --alloc-size to increase the "
 447                 "shared memory available.\n");
 448         return NULL;
 449 }
 450
 451 void *scalloc(size_t nmemb, size_t size)
 452 {
 453         return smalloc(nmemb * size);
 454 }
 455
 456 char *smalloc_strdup(const char *str)
 457 {
 458         char *ptr = NULL;
 459
 460         ptr = smalloc(strlen(str) + 1);
 461         if (ptr)
 462                 strcpy(ptr, str);
 463         return ptr;
 464 }