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