Changeset 9d47440 in mainline for uspace/lib/c/generic/malloc.c
- Timestamp:
- 2011-05-21T16:23:17Z (13 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 0ff03f3
- Parents:
- 8d308b9 (diff), 13f2461 (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
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
r8d308b9 r9d47440 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 \ … … 86 96 * 87 97 */ 88 #define AREA_FIRST_BLOCK (area) \98 #define AREA_FIRST_BLOCK_HEAD(area) \ 89 99 (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN)) 100 101 /** Get last block in heap area. 102 * 103 */ 104 #define AREA_LAST_BLOCK_FOOT(area) \ 105 (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t)) 106 107 /** Get header in heap block. 108 * 109 */ 110 #define BLOCK_HEAD(foot) \ 111 ((heap_block_head_t *) \ 112 (((uintptr_t) (foot)) + sizeof(heap_block_foot_t) - (foot)->size)) 90 113 91 114 /** Get footer in heap block. … … 94 117 #define BLOCK_FOOT(head) \ 95 118 ((heap_block_foot_t *) \ 96 (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t)))119 (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t))) 97 120 98 121 /** Heap area. … … 115 138 void *end; 116 139 140 /** Previous heap area */ 141 struct heap_area *prev; 142 117 143 /** Next heap area */ 118 144 struct heap_area *next; … … 161 187 /** Futex for thread-safe heap manipulation */ 162 188 static futex_t malloc_futex = FUTEX_INITIALIZER; 189 190 #ifndef NDEBUG 191 192 #define malloc_assert(expr) \ 193 do { \ 194 if (!(expr)) {\ 195 futex_up(&malloc_futex); \ 196 assert_abort(#expr, __FILE__, STR2(__LINE__)); \ 197 } \ 198 } while (0) 199 200 #else /* NDEBUG */ 201 202 #define malloc_assert(expr) 203 204 #endif /* NDEBUG */ 163 205 164 206 /** Initialize a heap block … … 202 244 heap_block_head_t *head = (heap_block_head_t *) addr; 203 245 204 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);246 malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 205 247 206 248 heap_block_foot_t *foot = BLOCK_FOOT(head); 207 249 208 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);209 assert(head->size == foot->size);250 malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 251 malloc_assert(head->size == foot->size); 210 252 } 211 253 212 254 /** Check a heap area structure 213 255 * 256 * Should be called only inside the critical section. 257 * 214 258 * @param addr Address of the heap area. 215 259 * … … 219 263 heap_area_t *area = (heap_area_t *) addr; 220 264 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); 265 malloc_assert(area->magic == HEAP_AREA_MAGIC); 266 malloc_assert(addr == area->start); 267 malloc_assert(area->start < area->end); 268 malloc_assert(((uintptr_t) area->start % PAGE_SIZE) == 0); 269 malloc_assert(((uintptr_t) area->end % PAGE_SIZE) == 0); 225 270 } 226 271 227 272 /** Create new heap area 228 273 * 229 * @param start Preffered starting address of the new area. 230 * @param size Size of the area. 274 * Should be called only inside the critical section. 275 * 276 * @param size Size of the area. 231 277 * 232 278 */ … … 248 294 249 295 area->start = astart; 250 area->end = (void *) 251 ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN);296 area->end = (void *) ((uintptr_t) astart + asize); 297 area->prev = NULL; 252 298 area->next = NULL; 253 299 area->magic = HEAP_AREA_MAGIC; 254 300 255 void *block = (void *) AREA_FIRST_BLOCK (area);301 void *block = (void *) AREA_FIRST_BLOCK_HEAD(area); 256 302 size_t bsize = (size_t) (area->end - block); 257 303 … … 262 308 last_heap_area = area; 263 309 } else { 310 area->prev = last_heap_area; 264 311 last_heap_area->next = area; 265 312 last_heap_area = area; … … 271 318 /** Try to enlarge a heap area 272 319 * 320 * Should be called only inside the critical section. 321 * 273 322 * @param area Heap area to grow. 274 * @param size Gross size of item to allocate (bytes). 323 * @param size Gross size to grow (bytes). 324 * 325 * @return True if successful. 275 326 * 276 327 */ … … 282 333 area_check(area); 283 334 284 size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size,285 PAGE_SIZE);286 287 335 /* New heap area size */ 288 void *end = (void *) 289 ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN); 336 size_t gross_size = (size_t) (area->end - area->start) + size; 337 size_t asize = ALIGN_UP(gross_size, PAGE_SIZE); 338 void *end = (void *) ((uintptr_t) area->start + asize); 290 339 291 340 /* Check for overflow */ … … 299 348 300 349 /* Add new free block */ 301 block_init(area->end, (size_t) (end - area->end), true, area); 350 size_t net_size = (size_t) (end - area->end); 351 if (net_size > 0) 352 block_init(area->end, net_size, true, area); 302 353 303 354 /* Update heap area parameters */ … … 309 360 /** Try to enlarge any of the heap areas 310 361 * 362 * Should be called only inside the critical section. 363 * 311 364 * @param size Gross size of item to allocate (bytes). 312 365 * … … 318 371 319 372 /* First try to enlarge some existing area */ 320 heap_area_t *area;321 for (area = first_heap_area; area != NULL;area = area->next) {373 for (heap_area_t *area = first_heap_area; area != NULL; 374 area = area->next) { 322 375 if (area_grow(area, size)) 323 376 return true; … … 325 378 326 379 /* Eventually try to create a new area */ 327 return area_create(AREA_FIRST_BLOCK(size)); 328 } 329 330 /** Try to shrink heap space 331 * 380 return area_create(AREA_FIRST_BLOCK_HEAD(size)); 381 } 382 383 /** Try to shrink heap 384 * 385 * Should be called only inside the critical section. 332 386 * In all cases the next pointer is reset. 333 387 * 334 */ 335 static void heap_shrink(void) 336 { 388 * @param area Last modified heap area. 389 * 390 */ 391 static void heap_shrink(heap_area_t *area) 392 { 393 area_check(area); 394 395 heap_block_foot_t *last_foot = 396 (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area); 397 heap_block_head_t *last_head = BLOCK_HEAD(last_foot); 398 399 block_check((void *) last_head); 400 malloc_assert(last_head->area == area); 401 402 if (last_head->free) { 403 /* 404 * The last block of the heap area is 405 * unused. The area might be potentially 406 * shrunk. 407 */ 408 409 heap_block_head_t *first_head = 410 (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area); 411 412 block_check((void *) first_head); 413 malloc_assert(first_head->area == area); 414 415 size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE); 416 417 if (first_head == last_head) { 418 /* 419 * The entire heap area consists of a single 420 * free heap block. This means we can get rid 421 * of it entirely. 422 */ 423 424 heap_area_t *prev = area->prev; 425 heap_area_t *next = area->next; 426 427 if (prev != NULL) { 428 area_check(prev); 429 prev->next = next; 430 } else 431 first_heap_area = next; 432 433 if (next != NULL) { 434 area_check(next); 435 next->prev = prev; 436 } else 437 last_heap_area = prev; 438 439 as_area_destroy(area->start); 440 } else if (shrink_size >= SHRINK_GRANULARITY) { 441 /* 442 * Make sure that we always shrink the area 443 * by a multiple of page size and update 444 * the block layout accordingly. 445 */ 446 447 size_t asize = (size_t) (area->end - area->start) - shrink_size; 448 void *end = (void *) ((uintptr_t) area->start + asize); 449 450 /* Resize the address space area */ 451 int ret = as_area_resize(area->start, asize, 0); 452 if (ret != EOK) 453 abort(); 454 455 /* Update heap area parameters */ 456 area->end = end; 457 458 /* Update block layout */ 459 void *last = (void *) last_head; 460 size_t excess = (size_t) (area->end - last); 461 462 if (excess > 0) { 463 if (excess >= STRUCT_OVERHEAD) { 464 /* 465 * The previous block cannot be free and there 466 * is enough free space left in the area to 467 * create a new free block. 468 */ 469 block_init(last, excess, true, area); 470 } else { 471 /* 472 * The excess is small. Therefore just enlarge 473 * the previous block. 474 */ 475 heap_block_foot_t *prev_foot = (heap_block_foot_t *) 476 (((uintptr_t) last_head) - sizeof(heap_block_foot_t)); 477 heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot); 478 479 block_check((void *) prev_head); 480 481 block_init(prev_head, prev_head->size + excess, 482 prev_head->free, area); 483 } 484 } 485 } 486 } 487 337 488 next = NULL; 338 489 } … … 362 513 static void split_mark(heap_block_head_t *cur, const size_t size) 363 514 { 364 assert(cur->size >= size);515 malloc_assert(cur->size >= size); 365 516 366 517 /* See if we should split the block. */ … … 398 549 { 399 550 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; 551 malloc_assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 552 malloc_assert((void *) first_block < area->end); 553 554 for (heap_block_head_t *cur = first_block; (void *) cur < area->end; 405 555 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 406 556 block_check(cur); … … 436 586 * data in (including alignment). 437 587 */ 438 if ((void *) cur > (void *) AREA_FIRST_BLOCK (area)) {588 if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 439 589 /* 440 590 * There is a block before the current block. … … 496 646 size_t reduced_size = cur->size - excess; 497 647 cur = (heap_block_head_t *) 498 (AREA_FIRST_BLOCK (area) + excess);648 (AREA_FIRST_BLOCK_HEAD(area) + excess); 499 649 500 block_init((void *) AREA_FIRST_BLOCK (area), excess,501 true, area);650 block_init((void *) AREA_FIRST_BLOCK_HEAD(area), 651 excess, true, area); 502 652 block_init(cur, reduced_size, true, area); 503 653 split_mark(cur, real_size); … … 527 677 static void *malloc_internal(const size_t size, const size_t align) 528 678 { 529 assert(first_heap_area != NULL);679 malloc_assert(first_heap_area != NULL); 530 680 531 681 if (align == 0) … … 552 702 553 703 /* Search the entire heap */ 554 heap_area_t *area;555 for (area = first_heap_area; area != NULL;area = area->next) {704 for (heap_area_t *area = first_heap_area; area != NULL; 705 area = area->next) { 556 706 heap_block_head_t *first = (heap_block_head_t *) 557 AREA_FIRST_BLOCK (area);707 AREA_FIRST_BLOCK_HEAD(area); 558 708 559 709 void *addr = malloc_area(area, first, split, real_size, … … 652 802 653 803 block_check(head); 654 assert(!head->free);804 malloc_assert(!head->free); 655 805 656 806 heap_area_t *area = head->area; 657 807 658 808 area_check(area); 659 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));660 assert((void *) head < area->end);809 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 810 malloc_assert((void *) head < area->end); 661 811 662 812 void *ptr = NULL; … … 675 825 block_init((void *) head + real_size, 676 826 orig_size - real_size, true, area); 677 heap_shrink( );827 heap_shrink(area); 678 828 } 679 829 … … 729 879 730 880 block_check(head); 731 assert(!head->free);881 malloc_assert(!head->free); 732 882 733 883 heap_area_t *area = head->area; 734 884 735 885 area_check(area); 736 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));737 assert((void *) head < area->end);886 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 887 malloc_assert((void *) head < area->end); 738 888 739 889 /* Mark the block itself as free. */ … … 751 901 752 902 /* Look at the previous block. If it is free, merge the two. */ 753 if ((void *) head > (void *) AREA_FIRST_BLOCK (area)) {903 if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 754 904 heap_block_foot_t *prev_foot = 755 905 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 765 915 } 766 916 767 heap_shrink( );917 heap_shrink(area); 768 918 769 919 futex_up(&malloc_futex); 770 920 } 771 921 922 void *heap_check(void) 923 { 924 futex_down(&malloc_futex); 925 926 if (first_heap_area == NULL) { 927 futex_up(&malloc_futex); 928 return (void *) -1; 929 } 930 931 /* Walk all heap areas */ 932 for (heap_area_t *area = first_heap_area; area != NULL; 933 area = area->next) { 934 935 /* Check heap area consistency */ 936 if ((area->magic != HEAP_AREA_MAGIC) || 937 ((void *) area != area->start) || 938 (area->start >= area->end) || 939 (((uintptr_t) area->start % PAGE_SIZE) != 0) || 940 (((uintptr_t) area->end % PAGE_SIZE) != 0)) { 941 futex_up(&malloc_futex); 942 return (void *) area; 943 } 944 945 /* Walk all heap blocks */ 946 for (heap_block_head_t *head = (heap_block_head_t *) 947 AREA_FIRST_BLOCK_HEAD(area); (void *) head < area->end; 948 head = (heap_block_head_t *) (((void *) head) + head->size)) { 949 950 /* Check heap block consistency */ 951 if (head->magic != HEAP_BLOCK_HEAD_MAGIC) { 952 futex_up(&malloc_futex); 953 return (void *) head; 954 } 955 956 heap_block_foot_t *foot = BLOCK_FOOT(head); 957 958 if ((foot->magic != HEAP_BLOCK_FOOT_MAGIC) || 959 (head->size != foot->size)) { 960 futex_up(&malloc_futex); 961 return (void *) foot; 962 } 963 } 964 } 965 966 futex_up(&malloc_futex); 967 968 return NULL; 969 } 970 772 971 /** @} 773 972 */
Note:
See TracChangeset
for help on using the changeset viewer.