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