Changeset 544a2e4 in mainline for uspace/lib/c/generic/malloc.c
- Timestamp:
- 2011-05-30T21:37:43Z (14 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 7b712b60
- Parents:
- 18ba2e4f (diff), 0743493a (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) (32 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
r18ba2e4f r544a2e4 44 44 #include <mem.h> 45 45 #include <futex.h> 46 #include <stdlib.h> 46 47 #include <adt/gcdlcm.h> 47 48 #include "private/malloc.h" … … 63 64 */ 64 65 #define BASE_ALIGN 16 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) 65 76 66 77 /** Overhead of each heap block. */ … … 68 79 (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 69 80 81 /** Overhead of each area. */ 82 #define AREA_OVERHEAD(size) \ 83 (ALIGN_UP(size + sizeof(heap_area_t), BASE_ALIGN)) 84 70 85 /** Calculate real size of a heap block. 71 86 * … … 85 100 * 86 101 */ 87 #define AREA_FIRST_BLOCK (area) \102 #define AREA_FIRST_BLOCK_HEAD(area) \ 88 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)) 89 117 90 118 /** Get footer in heap block. … … 93 121 #define BLOCK_FOOT(head) \ 94 122 ((heap_block_foot_t *) \ 95 (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t)))123 (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t))) 96 124 97 125 /** Heap area. … … 114 142 void *end; 115 143 144 /** Previous heap area */ 145 struct heap_area *prev; 146 116 147 /** Next heap area */ 117 148 struct heap_area *next; … … 156 187 157 188 /** Next heap block to examine (next fit algorithm) */ 158 static heap_block_head_t *next = NULL;189 static heap_block_head_t *next_fit = NULL; 159 190 160 191 /** Futex for thread-safe heap manipulation */ 161 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 */ 162 209 163 210 /** Initialize a heap block … … 201 248 heap_block_head_t *head = (heap_block_head_t *) addr; 202 249 203 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);250 malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 204 251 205 252 heap_block_foot_t *foot = BLOCK_FOOT(head); 206 253 207 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);208 assert(head->size == foot->size);254 malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 255 malloc_assert(head->size == foot->size); 209 256 } 210 257 211 258 /** Check a heap area structure 212 259 * 260 * Should be called only inside the critical section. 261 * 213 262 * @param addr Address of the heap area. 214 263 * … … 218 267 heap_area_t *area = (heap_area_t *) addr; 219 268 220 assert(area->magic == HEAP_AREA_MAGIC); 221 assert(area->start < area->end); 222 assert(((uintptr_t) area->start % PAGE_SIZE) == 0); 223 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); 224 274 } 225 275 226 276 /** Create new heap area 227 277 * 228 * @param start Preffered starting address of the new area. 229 * @param size Size of the area. 278 * Should be called only inside the critical section. 279 * 280 * @param size Size of the area. 230 281 * 231 282 */ … … 247 298 248 299 area->start = astart; 249 area->end = (void *) 250 ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN);300 area->end = (void *) ((uintptr_t) astart + asize); 301 area->prev = NULL; 251 302 area->next = NULL; 252 303 area->magic = HEAP_AREA_MAGIC; 253 304 254 void *block = (void *) AREA_FIRST_BLOCK (area);305 void *block = (void *) AREA_FIRST_BLOCK_HEAD(area); 255 306 size_t bsize = (size_t) (area->end - block); 256 307 … … 261 312 last_heap_area = area; 262 313 } else { 314 area->prev = last_heap_area; 263 315 last_heap_area->next = area; 264 316 last_heap_area = area; … … 270 322 /** Try to enlarge a heap area 271 323 * 324 * Should be called only inside the critical section. 325 * 272 326 * @param area Heap area to grow. 273 * @param size Gross size of item to allocate (bytes). 327 * @param size Gross size to grow (bytes). 328 * 329 * @return True if successful. 274 330 * 275 331 */ … … 281 337 area_check(area); 282 338 283 size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size,284 PAGE_SIZE);285 286 339 /* New heap area size */ 287 void *end = (void *) 288 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); 289 343 290 344 /* Check for overflow */ … … 298 352 299 353 /* Add new free block */ 300 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); 301 357 302 358 /* Update heap area parameters */ … … 308 364 /** Try to enlarge any of the heap areas 309 365 * 366 * Should be called only inside the critical section. 367 * 310 368 * @param size Gross size of item to allocate (bytes). 311 369 * … … 317 375 318 376 /* First try to enlarge some existing area */ 319 heap_area_t *area;320 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) { 321 379 if (area_grow(area, size)) 322 380 return true; … … 324 382 325 383 /* Eventually try to create a new area */ 326 return area_create(AREA_FIRST_BLOCK(size)); 327 } 328 329 /** Try to shrink heap space 330 * 384 return area_create(AREA_OVERHEAD(size)); 385 } 386 387 /** Try to shrink heap 388 * 389 * Should be called only inside the critical section. 331 390 * In all cases the next pointer is reset. 332 391 * 333 */ 334 static void heap_shrink(void) 335 { 336 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; 337 490 } 338 491 … … 361 514 static void split_mark(heap_block_head_t *cur, const size_t size) 362 515 { 363 assert(cur->size >= size);516 malloc_assert(cur->size >= size); 364 517 365 518 /* See if we should split the block. */ … … 397 550 { 398 551 area_check((void *) area); 399 assert((void *) first_block >= (void *) AREA_FIRST_BLOCK(area)); 400 assert((void *) first_block < area->end); 401 402 heap_block_head_t *cur; 403 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; 404 556 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 405 557 block_check(cur); … … 424 576 split_mark(cur, real_size); 425 577 426 next = cur;578 next_fit = cur; 427 579 return addr; 428 580 } else { … … 435 587 * data in (including alignment). 436 588 */ 437 if ((void *) cur > (void *) AREA_FIRST_BLOCK (area)) {589 if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 438 590 /* 439 591 * There is a block before the current block. … … 476 628 split_mark(next_head, real_size); 477 629 478 next = next_head;630 next_fit = next_head; 479 631 return aligned; 480 632 } else { … … 495 647 size_t reduced_size = cur->size - excess; 496 648 cur = (heap_block_head_t *) 497 (AREA_FIRST_BLOCK (area) + excess);649 (AREA_FIRST_BLOCK_HEAD(area) + excess); 498 650 499 block_init((void *) AREA_FIRST_BLOCK (area), excess,500 true, area);651 block_init((void *) AREA_FIRST_BLOCK_HEAD(area), 652 excess, true, area); 501 653 block_init(cur, reduced_size, true, area); 502 654 split_mark(cur, real_size); 503 655 504 next = cur;656 next_fit = cur; 505 657 return aligned; 506 658 } … … 526 678 static void *malloc_internal(const size_t size, const size_t align) 527 679 { 528 assert(first_heap_area != NULL);680 malloc_assert(first_heap_area != NULL); 529 681 530 682 if (align == 0) … … 540 692 541 693 /* Try the next fit approach */ 542 split = next ;694 split = next_fit; 543 695 544 696 if (split != NULL) { … … 551 703 552 704 /* Search the entire heap */ 553 heap_area_t *area;554 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) { 555 707 heap_block_head_t *first = (heap_block_head_t *) 556 AREA_FIRST_BLOCK (area);708 AREA_FIRST_BLOCK_HEAD(area); 557 709 558 710 void *addr = malloc_area(area, first, split, real_size, … … 651 803 652 804 block_check(head); 653 assert(!head->free);805 malloc_assert(!head->free); 654 806 655 807 heap_area_t *area = head->area; 656 808 657 809 area_check(area); 658 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));659 assert((void *) head < area->end);810 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 811 malloc_assert((void *) head < area->end); 660 812 661 813 void *ptr = NULL; … … 674 826 block_init((void *) head + real_size, 675 827 orig_size - real_size, true, area); 676 heap_shrink( );828 heap_shrink(area); 677 829 } 678 830 … … 696 848 697 849 ptr = ((void *) head) + sizeof(heap_block_head_t); 698 next = NULL;850 next_fit = NULL; 699 851 } else 700 852 reloc = true; … … 728 880 729 881 block_check(head); 730 assert(!head->free);882 malloc_assert(!head->free); 731 883 732 884 heap_area_t *area = head->area; 733 885 734 886 area_check(area); 735 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));736 assert((void *) head < area->end);887 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 888 malloc_assert((void *) head < area->end); 737 889 738 890 /* Mark the block itself as free. */ … … 750 902 751 903 /* Look at the previous block. If it is free, merge the two. */ 752 if ((void *) head > (void *) AREA_FIRST_BLOCK (area)) {904 if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 753 905 heap_block_foot_t *prev_foot = 754 906 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 764 916 } 765 917 766 heap_shrink( );918 heap_shrink(area); 767 919 768 920 futex_up(&malloc_futex); 769 921 } 770 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 771 972 /** @} 772 973 */
Note:
See TracChangeset
for help on using the changeset viewer.
