Changes in uspace/lib/c/generic/malloc.c [207533f:d161715] in mainline
- File:
-
- 1 edited
-
uspace/lib/c/generic/malloc.c (modified) (30 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
r207533f rd161715 65 65 #define BASE_ALIGN 16 66 66 67 /** Heap shrink granularity68 *69 * Try not to pump and stress the heap to much70 * by shrinking and enlarging it too often.71 * A heap area won't shrunk if it the released72 * free block is smaller than this constant.73 *74 */75 #define SHRINK_GRANULARITY (64 * PAGE_SIZE)76 77 67 /** Overhead of each heap block. */ 78 68 #define STRUCT_OVERHEAD \ 79 69 (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 80 70 81 /** Overhead of each area. */82 #define AREA_OVERHEAD(size) \83 (ALIGN_UP(size + sizeof(heap_area_t), BASE_ALIGN))84 85 71 /** Calculate real size of a heap block. 86 72 * … … 100 86 * 101 87 */ 102 #define AREA_FIRST_BLOCK _HEAD(area) \88 #define AREA_FIRST_BLOCK(area) \ 103 89 (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN)) 104 105 /** Get last block in heap area.106 *107 */108 #define AREA_LAST_BLOCK_FOOT(area) \109 (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t))110 111 /** Get header in heap block.112 *113 */114 #define BLOCK_HEAD(foot) \115 ((heap_block_head_t *) \116 (((uintptr_t) (foot)) + sizeof(heap_block_foot_t) - (foot)->size))117 90 118 91 /** Get footer in heap block. … … 121 94 #define BLOCK_FOOT(head) \ 122 95 ((heap_block_foot_t *) \ 123 (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t)))96 (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t))) 124 97 125 98 /** Heap area. … … 142 115 void *end; 143 116 144 /** Previous heap area */145 struct heap_area *prev;146 147 117 /** Next heap area */ 148 118 struct heap_area *next; … … 187 157 188 158 /** Next heap block to examine (next fit algorithm) */ 189 static heap_block_head_t *next _fit= NULL;159 static heap_block_head_t *next = NULL; 190 160 191 161 /** Futex for thread-safe heap manipulation */ 192 162 static futex_t malloc_futex = FUTEX_INITIALIZER; 193 194 #ifndef NDEBUG195 196 #define malloc_assert(expr) \197 do { \198 if (!(expr)) {\199 futex_up(&malloc_futex); \200 assert_abort(#expr, __FILE__, __LINE__); \201 } \202 } while (0)203 204 #else /* NDEBUG */205 206 #define malloc_assert(expr)207 208 #endif /* NDEBUG */209 163 210 164 /** Initialize a heap block … … 248 202 heap_block_head_t *head = (heap_block_head_t *) addr; 249 203 250 malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);204 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 251 205 252 206 heap_block_foot_t *foot = BLOCK_FOOT(head); 253 207 254 malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);255 malloc_assert(head->size == foot->size);208 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 209 assert(head->size == foot->size); 256 210 } 257 211 258 212 /** Check a heap area structure 259 213 * 260 * Should be called only inside the critical section.261 *262 214 * @param addr Address of the heap area. 263 215 * … … 267 219 heap_area_t *area = (heap_area_t *) addr; 268 220 269 malloc_assert(area->magic == HEAP_AREA_MAGIC); 270 malloc_assert(addr == area->start); 271 malloc_assert(area->start < area->end); 272 malloc_assert(((uintptr_t) area->start % PAGE_SIZE) == 0); 273 malloc_assert(((uintptr_t) area->end % PAGE_SIZE) == 0); 221 assert(area->magic == HEAP_AREA_MAGIC); 222 assert(area->start < area->end); 223 assert(((uintptr_t) area->start % PAGE_SIZE) == 0); 224 assert(((uintptr_t) area->end % PAGE_SIZE) == 0); 274 225 } 275 226 276 227 /** Create new heap area 277 228 * 278 * Should be called only inside the critical section. 279 * 280 * @param size Size of the area. 229 * @param start Preffered starting address of the new area. 230 * @param size Size of the area. 281 231 * 282 232 */ … … 298 248 299 249 area->start = astart; 300 area->end = (void *) ((uintptr_t) astart + asize);301 area->prev = NULL;250 area->end = (void *) 251 ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN); 302 252 area->next = NULL; 303 253 area->magic = HEAP_AREA_MAGIC; 304 254 305 void *block = (void *) AREA_FIRST_BLOCK _HEAD(area);255 void *block = (void *) AREA_FIRST_BLOCK(area); 306 256 size_t bsize = (size_t) (area->end - block); 307 257 … … 312 262 last_heap_area = area; 313 263 } else { 314 area->prev = last_heap_area;315 264 last_heap_area->next = area; 316 265 last_heap_area = area; … … 322 271 /** Try to enlarge a heap area 323 272 * 324 * Should be called only inside the critical section.325 *326 273 * @param area Heap area to grow. 327 * @param size Gross size to grow (bytes). 328 * 329 * @return True if successful. 274 * @param size Gross size of item to allocate (bytes). 330 275 * 331 276 */ … … 337 282 area_check(area); 338 283 284 size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size, 285 PAGE_SIZE); 286 339 287 /* New heap area size */ 340 size_t gross_size = (size_t) (area->end - area->start) + size; 341 size_t asize = ALIGN_UP(gross_size, PAGE_SIZE); 342 void *end = (void *) ((uintptr_t) area->start + asize); 288 void *end = (void *) 289 ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN); 343 290 344 291 /* Check for overflow */ … … 352 299 353 300 /* Add new free block */ 354 size_t net_size = (size_t) (end - area->end); 355 if (net_size > 0) 356 block_init(area->end, net_size, true, area); 301 block_init(area->end, (size_t) (end - area->end), true, area); 357 302 358 303 /* Update heap area parameters */ … … 364 309 /** Try to enlarge any of the heap areas 365 310 * 366 * Should be called only inside the critical section.367 *368 311 * @param size Gross size of item to allocate (bytes). 369 312 * … … 375 318 376 319 /* First try to enlarge some existing area */ 377 for (heap_area_t *area = first_heap_area; area != NULL;378 320 heap_area_t *area; 321 for (area = first_heap_area; area != NULL; area = area->next) { 379 322 if (area_grow(area, size)) 380 323 return true; … … 382 325 383 326 /* Eventually try to create a new area */ 384 return area_create(AREA_OVERHEAD(size)); 385 } 386 387 /** Try to shrink heap 388 * 389 * Should be called only inside the critical section. 327 return area_create(AREA_FIRST_BLOCK(size)); 328 } 329 330 /** Try to shrink heap space 331 * 390 332 * In all cases the next pointer is reset. 391 333 * 392 * @param area Last modified heap area. 393 * 394 */ 395 static void heap_shrink(heap_area_t *area) 396 { 397 area_check(area); 398 399 heap_block_foot_t *last_foot = 400 (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area); 401 heap_block_head_t *last_head = BLOCK_HEAD(last_foot); 402 403 block_check((void *) last_head); 404 malloc_assert(last_head->area == area); 405 406 if (last_head->free) { 407 /* 408 * The last block of the heap area is 409 * unused. The area might be potentially 410 * shrunk. 411 */ 412 413 heap_block_head_t *first_head = 414 (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area); 415 416 block_check((void *) first_head); 417 malloc_assert(first_head->area == area); 418 419 size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE); 420 421 if (first_head == last_head) { 422 /* 423 * The entire heap area consists of a single 424 * free heap block. This means we can get rid 425 * of it entirely. 426 */ 427 428 heap_area_t *prev = area->prev; 429 heap_area_t *next = area->next; 430 431 if (prev != NULL) { 432 area_check(prev); 433 prev->next = next; 434 } else 435 first_heap_area = next; 436 437 if (next != NULL) { 438 area_check(next); 439 next->prev = prev; 440 } else 441 last_heap_area = prev; 442 443 as_area_destroy(area->start); 444 } else if (shrink_size >= SHRINK_GRANULARITY) { 445 /* 446 * Make sure that we always shrink the area 447 * by a multiple of page size and update 448 * the block layout accordingly. 449 */ 450 451 size_t asize = (size_t) (area->end - area->start) - shrink_size; 452 void *end = (void *) ((uintptr_t) area->start + asize); 453 454 /* Resize the address space area */ 455 int ret = as_area_resize(area->start, asize, 0); 456 if (ret != EOK) 457 abort(); 458 459 /* Update heap area parameters */ 460 area->end = end; 461 size_t excess = ((size_t) area->end) - ((size_t) last_head); 462 463 if (excess > 0) { 464 if (excess >= STRUCT_OVERHEAD) { 465 /* 466 * The previous block cannot be free and there 467 * is enough free space left in the area to 468 * create a new free block. 469 */ 470 block_init((void *) last_head, excess, true, area); 471 } else { 472 /* 473 * The excess is small. Therefore just enlarge 474 * the previous block. 475 */ 476 heap_block_foot_t *prev_foot = (heap_block_foot_t *) 477 (((uintptr_t) last_head) - sizeof(heap_block_foot_t)); 478 heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot); 479 480 block_check((void *) prev_head); 481 482 block_init(prev_head, prev_head->size + excess, 483 prev_head->free, area); 484 } 485 } 486 } 487 } 488 489 next_fit = NULL; 334 */ 335 static void heap_shrink(void) 336 { 337 next = NULL; 490 338 } 491 339 … … 514 362 static void split_mark(heap_block_head_t *cur, const size_t size) 515 363 { 516 malloc_assert(cur->size >= size);364 assert(cur->size >= size); 517 365 518 366 /* See if we should split the block. */ … … 550 398 { 551 399 area_check((void *) area); 552 malloc_assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 553 malloc_assert((void *) first_block < area->end); 554 555 for (heap_block_head_t *cur = first_block; (void *) cur < area->end; 400 assert((void *) first_block >= (void *) AREA_FIRST_BLOCK(area)); 401 assert((void *) first_block < area->end); 402 403 heap_block_head_t *cur; 404 for (cur = first_block; (void *) cur < area->end; 556 405 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 557 406 block_check(cur); … … 576 425 split_mark(cur, real_size); 577 426 578 next _fit= cur;427 next = cur; 579 428 return addr; 580 429 } else { … … 587 436 * data in (including alignment). 588 437 */ 589 if ((void *) cur > (void *) AREA_FIRST_BLOCK _HEAD(area)) {438 if ((void *) cur > (void *) AREA_FIRST_BLOCK(area)) { 590 439 /* 591 440 * There is a block before the current block. … … 628 477 split_mark(next_head, real_size); 629 478 630 next _fit= next_head;479 next = next_head; 631 480 return aligned; 632 481 } else { … … 647 496 size_t reduced_size = cur->size - excess; 648 497 cur = (heap_block_head_t *) 649 (AREA_FIRST_BLOCK _HEAD(area) + excess);498 (AREA_FIRST_BLOCK(area) + excess); 650 499 651 block_init((void *) AREA_FIRST_BLOCK _HEAD(area),652 excess,true, area);500 block_init((void *) AREA_FIRST_BLOCK(area), excess, 501 true, area); 653 502 block_init(cur, reduced_size, true, area); 654 503 split_mark(cur, real_size); 655 504 656 next _fit= cur;505 next = cur; 657 506 return aligned; 658 507 } … … 678 527 static void *malloc_internal(const size_t size, const size_t align) 679 528 { 680 malloc_assert(first_heap_area != NULL);529 assert(first_heap_area != NULL); 681 530 682 531 if (align == 0) … … 692 541 693 542 /* Try the next fit approach */ 694 split = next _fit;543 split = next; 695 544 696 545 if (split != NULL) { … … 703 552 704 553 /* Search the entire heap */ 705 for (heap_area_t *area = first_heap_area; area != NULL;706 554 heap_area_t *area; 555 for (area = first_heap_area; area != NULL; area = area->next) { 707 556 heap_block_head_t *first = (heap_block_head_t *) 708 AREA_FIRST_BLOCK _HEAD(area);557 AREA_FIRST_BLOCK(area); 709 558 710 559 void *addr = malloc_area(area, first, split, real_size, … … 803 652 804 653 block_check(head); 805 malloc_assert(!head->free);654 assert(!head->free); 806 655 807 656 heap_area_t *area = head->area; 808 657 809 658 area_check(area); 810 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));811 malloc_assert((void *) head < area->end);659 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area)); 660 assert((void *) head < area->end); 812 661 813 662 void *ptr = NULL; … … 826 675 block_init((void *) head + real_size, 827 676 orig_size - real_size, true, area); 828 heap_shrink( area);677 heap_shrink(); 829 678 } 830 679 … … 848 697 849 698 ptr = ((void *) head) + sizeof(heap_block_head_t); 850 next _fit= NULL;699 next = NULL; 851 700 } else 852 701 reloc = true; … … 880 729 881 730 block_check(head); 882 malloc_assert(!head->free);731 assert(!head->free); 883 732 884 733 heap_area_t *area = head->area; 885 734 886 735 area_check(area); 887 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));888 malloc_assert((void *) head < area->end);736 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area)); 737 assert((void *) head < area->end); 889 738 890 739 /* Mark the block itself as free. */ … … 902 751 903 752 /* Look at the previous block. If it is free, merge the two. */ 904 if ((void *) head > (void *) AREA_FIRST_BLOCK _HEAD(area)) {753 if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) { 905 754 heap_block_foot_t *prev_foot = 906 755 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 916 765 } 917 766 918 heap_shrink( area);767 heap_shrink(); 919 768 920 769 futex_up(&malloc_futex); 921 770 } 922 771 923 void *heap_check(void)924 {925 futex_down(&malloc_futex);926 927 if (first_heap_area == NULL) {928 futex_up(&malloc_futex);929 return (void *) -1;930 }931 932 /* Walk all heap areas */933 for (heap_area_t *area = first_heap_area; area != NULL;934 area = area->next) {935 936 /* Check heap area consistency */937 if ((area->magic != HEAP_AREA_MAGIC) ||938 ((void *) area != area->start) ||939 (area->start >= area->end) ||940 (((uintptr_t) area->start % PAGE_SIZE) != 0) ||941 (((uintptr_t) area->end % PAGE_SIZE) != 0)) {942 futex_up(&malloc_futex);943 return (void *) area;944 }945 946 /* Walk all heap blocks */947 for (heap_block_head_t *head = (heap_block_head_t *)948 AREA_FIRST_BLOCK_HEAD(area); (void *) head < area->end;949 head = (heap_block_head_t *) (((void *) head) + head->size)) {950 951 /* Check heap block consistency */952 if (head->magic != HEAP_BLOCK_HEAD_MAGIC) {953 futex_up(&malloc_futex);954 return (void *) head;955 }956 957 heap_block_foot_t *foot = BLOCK_FOOT(head);958 959 if ((foot->magic != HEAP_BLOCK_FOOT_MAGIC) ||960 (head->size != foot->size)) {961 futex_up(&malloc_futex);962 return (void *) foot;963 }964 }965 }966 967 futex_up(&malloc_futex);968 969 return NULL;970 }971 972 772 /** @} 973 773 */
Note:
See TracChangeset
for help on using the changeset viewer.
