Changeset a35b458 in mainline for uspace/lib/c/generic/malloc.c
- Timestamp:
- 2018-03-02T20:10:49Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- f1380b7
- Parents:
- 3061bc1
- git-author:
- Jiří Zárevúcky <zarevucky.jiri@…> (2018-02-28 17:38:31)
- git-committer:
- Jiří Zárevúcky <zarevucky.jiri@…> (2018-03-02 20:10:49)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
r3061bc1 ra35b458 142 142 */ 143 143 void *start; 144 144 145 145 /** End of the heap area (aligned on page boundary) */ 146 146 void *end; 147 147 148 148 /** Previous heap area */ 149 149 struct heap_area *prev; 150 150 151 151 /** Next heap area */ 152 152 struct heap_area *next; 153 153 154 154 /** A magic value */ 155 155 uint32_t magic; … … 162 162 /* Size of the block (including header and footer) */ 163 163 size_t size; 164 164 165 165 /* Indication of a free block */ 166 166 bool free; 167 167 168 168 /** Heap area this block belongs to */ 169 169 heap_area_t *area; 170 170 171 171 /* A magic value to detect overwrite of heap header */ 172 172 uint32_t magic; … … 179 179 /* Size of the block (including header and footer) */ 180 180 size_t size; 181 181 182 182 /* A magic value to detect overwrite of heap footer */ 183 183 uint32_t magic; … … 277 277 /* Calculate the position of the header and the footer */ 278 278 heap_block_head_t *head = (heap_block_head_t *) addr; 279 279 280 280 head->size = size; 281 281 head->free = free; 282 282 head->area = area; 283 283 head->magic = HEAP_BLOCK_HEAD_MAGIC; 284 284 285 285 heap_block_foot_t *foot = BLOCK_FOOT(head); 286 286 287 287 foot->size = size; 288 288 foot->magic = HEAP_BLOCK_FOOT_MAGIC; … … 301 301 { 302 302 heap_block_head_t *head = (heap_block_head_t *) addr; 303 303 304 304 malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 305 305 306 306 heap_block_foot_t *foot = BLOCK_FOOT(head); 307 307 308 308 malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 309 309 malloc_assert(head->size == foot->size); … … 320 320 { 321 321 heap_area_t *area = (heap_area_t *) addr; 322 322 323 323 malloc_assert(area->magic == HEAP_AREA_MAGIC); 324 324 malloc_assert(addr == area->start); … … 343 343 if (astart == AS_MAP_FAILED) 344 344 return false; 345 345 346 346 heap_area_t *area = (heap_area_t *) astart; 347 347 348 348 area->start = astart; 349 349 area->end = (void *) ((uintptr_t) astart + asize); … … 351 351 area->next = NULL; 352 352 area->magic = HEAP_AREA_MAGIC; 353 353 354 354 void *block = (void *) AREA_FIRST_BLOCK_HEAD(area); 355 355 size_t bsize = (size_t) (area->end - block); 356 356 357 357 block_init(block, bsize, true, area); 358 358 359 359 if (last_heap_area == NULL) { 360 360 first_heap_area = area; … … 365 365 last_heap_area = area; 366 366 } 367 367 368 368 return true; 369 369 } … … 383 383 if (size == 0) 384 384 return true; 385 385 386 386 area_check(area); 387 387 388 388 /* New heap area size */ 389 389 size_t gross_size = (size_t) (area->end - area->start) + size; 390 390 size_t asize = ALIGN_UP(gross_size, PAGE_SIZE); 391 391 void *end = (void *) ((uintptr_t) area->start + asize); 392 392 393 393 /* Check for overflow */ 394 394 if (end < area->start) 395 395 return false; 396 396 397 397 /* Resize the address space area */ 398 398 errno_t ret = as_area_resize(area->start, asize, 0); 399 399 if (ret != EOK) 400 400 return false; 401 401 402 402 heap_block_head_t *last_head = 403 403 (heap_block_head_t *) AREA_LAST_BLOCK_HEAD(area); 404 404 405 405 if (last_head->free) { 406 406 /* Add the new space to the last block. */ … … 414 414 block_init(area->end, net_size, true, area); 415 415 } 416 416 417 417 /* Update heap area parameters */ 418 418 area->end = end; 419 419 420 420 return true; 421 421 } … … 432 432 { 433 433 area_check(area); 434 434 435 435 heap_block_foot_t *last_foot = 436 436 (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area); 437 437 heap_block_head_t *last_head = BLOCK_HEAD(last_foot); 438 438 439 439 block_check((void *) last_head); 440 440 malloc_assert(last_head->area == area); 441 441 442 442 if (last_head->free) { 443 443 /* … … 446 446 * shrunk. 447 447 */ 448 448 449 449 heap_block_head_t *first_head = 450 450 (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area); 451 451 452 452 block_check((void *) first_head); 453 453 malloc_assert(first_head->area == area); 454 454 455 455 size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE); 456 456 457 457 if (first_head == last_head) { 458 458 /* … … 461 461 * of it entirely. 462 462 */ 463 463 464 464 heap_area_t *prev = area->prev; 465 465 heap_area_t *next = area->next; 466 466 467 467 if (prev != NULL) { 468 468 area_check(prev); … … 470 470 } else 471 471 first_heap_area = next; 472 472 473 473 if (next != NULL) { 474 474 area_check(next); … … 476 476 } else 477 477 last_heap_area = prev; 478 478 479 479 as_area_destroy(area->start); 480 480 } else if (shrink_size >= SHRINK_GRANULARITY) { … … 484 484 * the block layout accordingly. 485 485 */ 486 486 487 487 size_t asize = (size_t) (area->end - area->start) - shrink_size; 488 488 void *end = (void *) ((uintptr_t) area->start + asize); 489 489 490 490 /* Resize the address space area */ 491 491 errno_t ret = as_area_resize(area->start, asize, 0); 492 492 if (ret != EOK) 493 493 abort(); 494 494 495 495 /* Update heap area parameters */ 496 496 area->end = end; 497 497 size_t excess = ((size_t) area->end) - ((size_t) last_head); 498 498 499 499 if (excess > 0) { 500 500 if (excess >= STRUCT_OVERHEAD) { … … 513 513 (((uintptr_t) last_head) - sizeof(heap_block_foot_t)); 514 514 heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot); 515 515 516 516 block_check((void *) prev_head); 517 517 518 518 block_init(prev_head, prev_head->size + excess, 519 519 prev_head->free, area); … … 522 522 } 523 523 } 524 524 525 525 next_fit = NULL; 526 526 } … … 551 551 { 552 552 malloc_assert(cur->size >= size); 553 553 554 554 /* See if we should split the block. */ 555 555 size_t split_limit = GROSS_SIZE(size); 556 556 557 557 if (cur->size > split_limit) { 558 558 /* Block big enough -> split. */ … … 588 588 malloc_assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 589 589 malloc_assert((void *) first_block < area->end); 590 590 591 591 for (heap_block_head_t *cur = first_block; (void *) cur < area->end; 592 592 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 593 593 block_check(cur); 594 594 595 595 /* Finish searching on the final block */ 596 596 if ((final_block != NULL) && (cur == final_block)) 597 597 break; 598 598 599 599 /* Try to find a block that is free and large enough. */ 600 600 if ((cur->free) && (cur->size >= real_size)) { … … 607 607 void *aligned = (void *) 608 608 ALIGN_UP((uintptr_t) addr, falign); 609 609 610 610 if (addr == aligned) { 611 611 /* Exact block start including alignment. */ 612 612 split_mark(cur, real_size); 613 613 614 614 next_fit = cur; 615 615 return addr; … … 617 617 /* Block start has to be aligned */ 618 618 size_t excess = (size_t) (aligned - addr); 619 619 620 620 if (cur->size >= real_size + excess) { 621 621 /* … … 631 631 heap_block_foot_t *prev_foot = (heap_block_foot_t *) 632 632 ((void *) cur - sizeof(heap_block_foot_t)); 633 633 634 634 heap_block_head_t *prev_head = (heap_block_head_t *) 635 635 ((void *) cur - prev_foot->size); 636 636 637 637 block_check(prev_head); 638 638 639 639 size_t reduced_size = cur->size - excess; 640 640 heap_block_head_t *next_head = ((void *) cur) + excess; 641 641 642 642 if ((!prev_head->free) && 643 643 (excess >= STRUCT_OVERHEAD)) { … … 660 660 prev_head->free, area); 661 661 } 662 662 663 663 block_init(next_head, reduced_size, true, area); 664 664 split_mark(next_head, real_size); 665 665 666 666 next_fit = next_head; 667 667 return aligned; … … 678 678 excess += falign; 679 679 } 680 680 681 681 /* Check for current block size again */ 682 682 if (cur->size >= real_size + excess) { … … 684 684 cur = (heap_block_head_t *) 685 685 (AREA_FIRST_BLOCK_HEAD(area) + excess); 686 686 687 687 block_init((void *) AREA_FIRST_BLOCK_HEAD(area), 688 688 excess, true, area); 689 689 block_init(cur, reduced_size, true, area); 690 690 split_mark(cur, real_size); 691 691 692 692 next_fit = cur; 693 693 return aligned; … … 698 698 } 699 699 } 700 700 701 701 return NULL; 702 702 } … … 718 718 if (size == 0) 719 719 return NULL; 720 720 721 721 /* First try to enlarge some existing area */ 722 722 for (heap_area_t *area = first_heap_area; area != NULL; 723 723 area = area->next) { 724 724 725 725 if (area_grow(area, size + align)) { 726 726 heap_block_head_t *first = 727 727 (heap_block_head_t *) AREA_LAST_BLOCK_HEAD(area); 728 728 729 729 void *addr = 730 730 malloc_area(area, first, NULL, size, align); … … 733 733 } 734 734 } 735 735 736 736 /* Eventually try to create a new area */ 737 737 if (area_create(AREA_OVERHEAD(size + align))) { 738 738 heap_block_head_t *first = 739 739 (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(last_heap_area); 740 740 741 741 void *addr = 742 742 malloc_area(last_heap_area, first, NULL, size, align); … … 744 744 return addr; 745 745 } 746 746 747 747 return NULL; 748 748 } … … 761 761 { 762 762 malloc_assert(first_heap_area != NULL); 763 763 764 764 if (align == 0) 765 765 return NULL; 766 766 767 767 size_t falign = lcm(align, BASE_ALIGN); 768 768 769 769 /* Check for integer overflow. */ 770 770 if (falign < align) 771 771 return NULL; 772 772 773 773 /* 774 774 * The size of the allocated block needs to be naturally … … 778 778 */ 779 779 size_t gross_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN)); 780 780 781 781 /* Try the next fit approach */ 782 782 heap_block_head_t *split = next_fit; 783 783 784 784 if (split != NULL) { 785 785 void *addr = malloc_area(split->area, split, NULL, gross_size, 786 786 falign); 787 787 788 788 if (addr != NULL) 789 789 return addr; 790 790 } 791 791 792 792 /* Search the entire heap */ 793 793 for (heap_area_t *area = first_heap_area; area != NULL; … … 795 795 heap_block_head_t *first = (heap_block_head_t *) 796 796 AREA_FIRST_BLOCK_HEAD(area); 797 797 798 798 void *addr = malloc_area(area, first, split, gross_size, 799 799 falign); 800 800 801 801 if (addr != NULL) 802 802 return addr; 803 803 } 804 804 805 805 /* Finally, try to grow heap space and allocate in the new area. */ 806 806 return heap_grow_and_alloc(gross_size, falign); … … 818 818 { 819 819 // FIXME: Check for overflow 820 820 821 821 void *block = malloc(nmemb * size); 822 822 if (block == NULL) 823 823 return NULL; 824 824 825 825 memset(block, 0, nmemb * size); 826 826 return block; … … 855 855 if (align == 0) 856 856 return NULL; 857 857 858 858 size_t palign = 859 859 1 << (fnzb(max(sizeof(void *), align) - 1) + 1); … … 883 883 if (addr == NULL) 884 884 return malloc(size); 885 885 886 886 heap_lock(); 887 887 888 888 /* Calculate the position of the header. */ 889 889 heap_block_head_t *head = 890 890 (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 891 891 892 892 block_check(head); 893 893 malloc_assert(!head->free); 894 894 895 895 heap_area_t *area = head->area; 896 896 897 897 area_check(area); 898 898 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 899 899 malloc_assert((void *) head < area->end); 900 900 901 901 void *ptr = NULL; 902 902 bool reloc = false; 903 903 size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN)); 904 904 size_t orig_size = head->size; 905 905 906 906 if (orig_size > real_size) { 907 907 /* Shrink */ … … 916 916 heap_shrink(area); 917 917 } 918 918 919 919 ptr = ((void *) head) + sizeof(heap_block_head_t); 920 920 } else { … … 948 948 } 949 949 } 950 950 951 951 /* 952 952 * Look at the next block. If it is free and the size is … … 962 962 area); 963 963 split_mark(head, real_size); 964 964 965 965 ptr = ((void *) head) + sizeof(heap_block_head_t); 966 966 next_fit = NULL; … … 969 969 } 970 970 } 971 971 972 972 heap_unlock(); 973 973 974 974 if (reloc) { 975 975 ptr = malloc(size); … … 979 979 } 980 980 } 981 981 982 982 return ptr; 983 983 } … … 992 992 if (addr == NULL) 993 993 return; 994 994 995 995 heap_lock(); 996 996 997 997 /* Calculate the position of the header. */ 998 998 heap_block_head_t *head 999 999 = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 1000 1000 1001 1001 block_check(head); 1002 1002 malloc_assert(!head->free); 1003 1003 1004 1004 heap_area_t *area = head->area; 1005 1005 1006 1006 area_check(area); 1007 1007 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 1008 1008 malloc_assert((void *) head < area->end); 1009 1009 1010 1010 /* Mark the block itself as free. */ 1011 1011 head->free = true; 1012 1012 1013 1013 /* Look at the next block. If it is free, merge the two. */ 1014 1014 heap_block_head_t *next_head 1015 1015 = (heap_block_head_t *) (((void *) head) + head->size); 1016 1016 1017 1017 if ((void *) next_head < area->end) { 1018 1018 block_check(next_head); … … 1020 1020 block_init(head, head->size + next_head->size, true, area); 1021 1021 } 1022 1022 1023 1023 /* Look at the previous block. If it is free, merge the two. */ 1024 1024 if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 1025 1025 heap_block_foot_t *prev_foot = 1026 1026 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); 1027 1027 1028 1028 heap_block_head_t *prev_head = 1029 1029 (heap_block_head_t *) (((void *) head) - prev_foot->size); 1030 1030 1031 1031 block_check(prev_head); 1032 1032 1033 1033 if (prev_head->free) 1034 1034 block_init(prev_head, prev_head->size + head->size, true, 1035 1035 area); 1036 1036 } 1037 1037 1038 1038 heap_shrink(area); 1039 1039 1040 1040 heap_unlock(); 1041 1041 } … … 1044 1044 { 1045 1045 heap_lock(); 1046 1046 1047 1047 if (first_heap_area == NULL) { 1048 1048 heap_unlock(); 1049 1049 return (void *) -1; 1050 1050 } 1051 1051 1052 1052 /* Walk all heap areas */ 1053 1053 for (heap_area_t *area = first_heap_area; area != NULL; 1054 1054 area = area->next) { 1055 1055 1056 1056 /* Check heap area consistency */ 1057 1057 if ((area->magic != HEAP_AREA_MAGIC) || … … 1063 1063 return (void *) area; 1064 1064 } 1065 1065 1066 1066 /* Walk all heap blocks */ 1067 1067 for (heap_block_head_t *head = (heap_block_head_t *) 1068 1068 AREA_FIRST_BLOCK_HEAD(area); (void *) head < area->end; 1069 1069 head = (heap_block_head_t *) (((void *) head) + head->size)) { 1070 1070 1071 1071 /* Check heap block consistency */ 1072 1072 if (head->magic != HEAP_BLOCK_HEAD_MAGIC) { … … 1074 1074 return (void *) head; 1075 1075 } 1076 1076 1077 1077 heap_block_foot_t *foot = BLOCK_FOOT(head); 1078 1078 1079 1079 if ((foot->magic != HEAP_BLOCK_FOOT_MAGIC) || 1080 1080 (head->size != foot->size)) { … … 1084 1084 } 1085 1085 } 1086 1086 1087 1087 heap_unlock(); 1088 1088 1089 1089 return NULL; 1090 1090 }
Note:
See TracChangeset
for help on using the changeset viewer.