Changeset a33f0a6 in mainline for uspace/lib/c/generic/malloc.c
- Timestamp:
- 2011-08-03T17:34:57Z (13 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 1940326
- Parents:
- 52a79081 (diff), 3fab770 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - File:
-
- 1 edited
-
uspace/lib/c/generic/malloc.c (modified) (30 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
r52a79081 ra33f0a6 65 65 #define BASE_ALIGN 16 66 66 67 /** Heap shrink granularity 68 * 69 * Try not to pump and stress the heap to much 70 * by shrinking and enlarging it too often. 71 * A heap area won't shrunk if it the released 72 * free block is smaller than this constant. 73 * 74 */ 75 #define SHRINK_GRANULARITY (64 * PAGE_SIZE) 76 67 77 /** Overhead of each heap block. */ 68 78 #define STRUCT_OVERHEAD \ 69 79 (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 70 80 81 /** Overhead of each area. */ 82 #define AREA_OVERHEAD(size) \ 83 (ALIGN_UP(size + sizeof(heap_area_t), BASE_ALIGN)) 84 71 85 /** Calculate real size of a heap block. 72 86 * … … 86 100 * 87 101 */ 88 #define AREA_FIRST_BLOCK (area) \102 #define AREA_FIRST_BLOCK_HEAD(area) \ 89 103 (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)) 90 117 91 118 /** Get footer in heap block. … … 94 121 #define BLOCK_FOOT(head) \ 95 122 ((heap_block_foot_t *) \ 96 (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t)))123 (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t))) 97 124 98 125 /** Heap area. … … 115 142 void *end; 116 143 144 /** Previous heap area */ 145 struct heap_area *prev; 146 117 147 /** Next heap area */ 118 148 struct heap_area *next; … … 157 187 158 188 /** Next heap block to examine (next fit algorithm) */ 159 static heap_block_head_t *next = NULL;189 static heap_block_head_t *next_fit = NULL; 160 190 161 191 /** Futex for thread-safe heap manipulation */ 162 192 static futex_t malloc_futex = FUTEX_INITIALIZER; 193 194 #ifndef NDEBUG 195 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 */ 163 209 164 210 /** Initialize a heap block … … 202 248 heap_block_head_t *head = (heap_block_head_t *) addr; 203 249 204 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);250 malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 205 251 206 252 heap_block_foot_t *foot = BLOCK_FOOT(head); 207 253 208 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);209 assert(head->size == foot->size);254 malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 255 malloc_assert(head->size == foot->size); 210 256 } 211 257 212 258 /** Check a heap area structure 213 259 * 260 * Should be called only inside the critical section. 261 * 214 262 * @param addr Address of the heap area. 215 263 * … … 219 267 heap_area_t *area = (heap_area_t *) addr; 220 268 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); 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); 225 274 } 226 275 227 276 /** Create new heap area 228 277 * 229 * @param start Preffered starting address of the new area. 230 * @param size Size of the area. 278 * Should be called only inside the critical section. 279 * 280 * @param size Size of the area. 231 281 * 232 282 */ … … 248 298 249 299 area->start = astart; 250 area->end = (void *) 251 ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN);300 area->end = (void *) ((uintptr_t) astart + asize); 301 area->prev = NULL; 252 302 area->next = NULL; 253 303 area->magic = HEAP_AREA_MAGIC; 254 304 255 void *block = (void *) AREA_FIRST_BLOCK (area);305 void *block = (void *) AREA_FIRST_BLOCK_HEAD(area); 256 306 size_t bsize = (size_t) (area->end - block); 257 307 … … 262 312 last_heap_area = area; 263 313 } else { 314 area->prev = last_heap_area; 264 315 last_heap_area->next = area; 265 316 last_heap_area = area; … … 271 322 /** Try to enlarge a heap area 272 323 * 324 * Should be called only inside the critical section. 325 * 273 326 * @param area Heap area to grow. 274 * @param size Gross size of item to allocate (bytes). 327 * @param size Gross size to grow (bytes). 328 * 329 * @return True if successful. 275 330 * 276 331 */ … … 282 337 area_check(area); 283 338 284 size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size,285 PAGE_SIZE);286 287 339 /* New heap area size */ 288 void *end = (void *) 289 ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN); 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); 290 343 291 344 /* Check for overflow */ … … 299 352 300 353 /* Add new free block */ 301 block_init(area->end, (size_t) (end - area->end), true, area); 354 size_t net_size = (size_t) (end - area->end); 355 if (net_size > 0) 356 block_init(area->end, net_size, true, area); 302 357 303 358 /* Update heap area parameters */ … … 309 364 /** Try to enlarge any of the heap areas 310 365 * 366 * Should be called only inside the critical section. 367 * 311 368 * @param size Gross size of item to allocate (bytes). 312 369 * … … 318 375 319 376 /* First try to enlarge some existing area */ 320 heap_area_t *area;321 for (area = first_heap_area; area != NULL;area = area->next) {377 for (heap_area_t *area = first_heap_area; area != NULL; 378 area = area->next) { 322 379 if (area_grow(area, size)) 323 380 return true; … … 325 382 326 383 /* Eventually try to create a new area */ 327 return area_create(AREA_FIRST_BLOCK(size)); 328 } 329 330 /** Try to shrink heap space 331 * 384 return area_create(AREA_OVERHEAD(size)); 385 } 386 387 /** Try to shrink heap 388 * 389 * Should be called only inside the critical section. 332 390 * In all cases the next pointer is reset. 333 391 * 334 */ 335 static void heap_shrink(void) 336 { 337 next = NULL; 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; 338 490 } 339 491 … … 362 514 static void split_mark(heap_block_head_t *cur, const size_t size) 363 515 { 364 assert(cur->size >= size);516 malloc_assert(cur->size >= size); 365 517 366 518 /* See if we should split the block. */ … … 398 550 { 399 551 area_check((void *) area); 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; 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; 405 556 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 406 557 block_check(cur); … … 425 576 split_mark(cur, real_size); 426 577 427 next = cur;578 next_fit = cur; 428 579 return addr; 429 580 } else { … … 436 587 * data in (including alignment). 437 588 */ 438 if ((void *) cur > (void *) AREA_FIRST_BLOCK (area)) {589 if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 439 590 /* 440 591 * There is a block before the current block. … … 477 628 split_mark(next_head, real_size); 478 629 479 next = next_head;630 next_fit = next_head; 480 631 return aligned; 481 632 } else { … … 496 647 size_t reduced_size = cur->size - excess; 497 648 cur = (heap_block_head_t *) 498 (AREA_FIRST_BLOCK (area) + excess);649 (AREA_FIRST_BLOCK_HEAD(area) + excess); 499 650 500 block_init((void *) AREA_FIRST_BLOCK (area), excess,501 true, area);651 block_init((void *) AREA_FIRST_BLOCK_HEAD(area), 652 excess, true, area); 502 653 block_init(cur, reduced_size, true, area); 503 654 split_mark(cur, real_size); 504 655 505 next = cur;656 next_fit = cur; 506 657 return aligned; 507 658 } … … 527 678 static void *malloc_internal(const size_t size, const size_t align) 528 679 { 529 assert(first_heap_area != NULL);680 malloc_assert(first_heap_area != NULL); 530 681 531 682 if (align == 0) … … 541 692 542 693 /* Try the next fit approach */ 543 split = next ;694 split = next_fit; 544 695 545 696 if (split != NULL) { … … 552 703 553 704 /* Search the entire heap */ 554 heap_area_t *area;555 for (area = first_heap_area; area != NULL;area = area->next) {705 for (heap_area_t *area = first_heap_area; area != NULL; 706 area = area->next) { 556 707 heap_block_head_t *first = (heap_block_head_t *) 557 AREA_FIRST_BLOCK (area);708 AREA_FIRST_BLOCK_HEAD(area); 558 709 559 710 void *addr = malloc_area(area, first, split, real_size, … … 652 803 653 804 block_check(head); 654 assert(!head->free);805 malloc_assert(!head->free); 655 806 656 807 heap_area_t *area = head->area; 657 808 658 809 area_check(area); 659 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));660 assert((void *) head < area->end);810 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 811 malloc_assert((void *) head < area->end); 661 812 662 813 void *ptr = NULL; … … 675 826 block_init((void *) head + real_size, 676 827 orig_size - real_size, true, area); 677 heap_shrink( );828 heap_shrink(area); 678 829 } 679 830 … … 697 848 698 849 ptr = ((void *) head) + sizeof(heap_block_head_t); 699 next = NULL;850 next_fit = NULL; 700 851 } else 701 852 reloc = true; … … 729 880 730 881 block_check(head); 731 assert(!head->free);882 malloc_assert(!head->free); 732 883 733 884 heap_area_t *area = head->area; 734 885 735 886 area_check(area); 736 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));737 assert((void *) head < area->end);887 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 888 malloc_assert((void *) head < area->end); 738 889 739 890 /* Mark the block itself as free. */ … … 751 902 752 903 /* Look at the previous block. If it is free, merge the two. */ 753 if ((void *) head > (void *) AREA_FIRST_BLOCK (area)) {904 if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 754 905 heap_block_foot_t *prev_foot = 755 906 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 765 916 } 766 917 767 heap_shrink( );918 heap_shrink(area); 768 919 769 920 futex_up(&malloc_futex); 770 921 } 771 922 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 772 972 /** @} 773 973 */
Note:
See TracChangeset
for help on using the changeset viewer.
