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