Changeset 013a5d7 in mainline for uspace/lib/c/generic/malloc.c
- Timestamp:
- 2011-05-17T15:13:00Z (13 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 38c773e7
- Parents:
- f414851
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
rf414851 r013a5d7 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; … … 212 238 /** Check a heap area structure 213 239 * 240 * Should be called only inside the critical section. 241 * 214 242 * @param addr Address of the heap area. 215 243 * … … 220 248 221 249 assert(area->magic == HEAP_AREA_MAGIC); 250 assert(addr == area->start); 222 251 assert(area->start < area->end); 223 252 assert(((uintptr_t) area->start % PAGE_SIZE) == 0); … … 227 256 /** Create new heap area 228 257 * 229 * @param start Preffered starting address of the new area. 230 * @param size Size of the area. 258 * Should be called only inside the critical section. 259 * 260 * @param size Size of the area. 231 261 * 232 262 */ … … 248 278 249 279 area->start = astart; 250 area->end = (void *) 251 ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN);280 area->end = (void *) ((uintptr_t) astart + asize); 281 area->prev = NULL; 252 282 area->next = NULL; 253 283 area->magic = HEAP_AREA_MAGIC; 254 284 255 void *block = (void *) AREA_FIRST_BLOCK (area);285 void *block = (void *) AREA_FIRST_BLOCK_HEAD(area); 256 286 size_t bsize = (size_t) (area->end - block); 257 287 … … 262 292 last_heap_area = area; 263 293 } else { 294 area->prev = last_heap_area; 264 295 last_heap_area->next = area; 265 296 last_heap_area = area; … … 271 302 /** Try to enlarge a heap area 272 303 * 304 * Should be called only inside the critical section. 305 * 273 306 * @param area Heap area to grow. 274 * @param size Gross size of item to allocate (bytes). 307 * @param size Gross size to grow (bytes). 308 * 309 * @return True if successful. 275 310 * 276 311 */ … … 282 317 area_check(area); 283 318 284 size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size,285 PAGE_SIZE);286 287 319 /* New heap area size */ 288 void *end = (void *) 289 ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN); 320 size_t gross_size = (size_t) (area->end - area->start) + size; 321 size_t asize = ALIGN_UP(gross_size, PAGE_SIZE); 322 void *end = (void *) ((uintptr_t) area->start + asize); 290 323 291 324 /* Check for overflow */ … … 299 332 300 333 /* Add new free block */ 301 block_init(area->end, (size_t) (end - area->end), true, area); 334 size_t net_size = (size_t) (end - area->end); 335 if (net_size > 0) 336 block_init(area->end, net_size, true, area); 302 337 303 338 /* Update heap area parameters */ … … 309 344 /** Try to enlarge any of the heap areas 310 345 * 346 * Should be called only inside the critical section. 347 * 311 348 * @param size Gross size of item to allocate (bytes). 312 349 * … … 318 355 319 356 /* First try to enlarge some existing area */ 320 heap_area_t *area;321 for (area = first_heap_area; area != NULL;area = area->next) {357 for (heap_area_t *area = first_heap_area; area != NULL; 358 area = area->next) { 322 359 if (area_grow(area, size)) 323 360 return true; … … 325 362 326 363 /* Eventually try to create a new area */ 327 return area_create(AREA_FIRST_BLOCK(size)); 328 } 329 330 /** Try to shrink heap space 331 * 364 return area_create(AREA_FIRST_BLOCK_HEAD(size)); 365 } 366 367 /** Try to shrink heap 368 * 369 * Should be called only inside the critical section. 332 370 * In all cases the next pointer is reset. 333 371 * 334 */ 335 static void heap_shrink(void) 336 { 372 * @param area Last modified heap area. 373 * 374 */ 375 static void heap_shrink(heap_area_t *area) 376 { 377 area_check(area); 378 379 heap_block_foot_t *last_foot = 380 (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area); 381 heap_block_head_t *last_head = BLOCK_HEAD(last_foot); 382 383 block_check((void *) last_head); 384 assert(last_head->area == area); 385 386 if (last_head->free) { 387 /* 388 * The last block of the heap area is 389 * unused. The area might be potentially 390 * shrunk. 391 */ 392 393 heap_block_head_t *first_head = 394 (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area); 395 396 block_check((void *) first_head); 397 assert(first_head->area == area); 398 399 if (first_head == last_head) { 400 /* 401 * The entire heap area consists of a single 402 * free heap block. This means we can get rid 403 * of it entirely. 404 */ 405 406 heap_area_t *prev = area->prev; 407 heap_area_t *next = area->next; 408 409 if (prev != NULL) { 410 area_check(prev); 411 prev->next = next; 412 } else 413 first_heap_area = next; 414 415 if (next != NULL) { 416 area_check(next); 417 next->prev = prev; 418 } else 419 last_heap_area = prev; 420 421 as_area_destroy(area->start); 422 } else if (last_head->size >= SHRINK_GRANULARITY) { 423 /* 424 * Make sure that we always shrink the area 425 * by a multiple of page size and update 426 * the block layout accordingly. 427 */ 428 429 size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE); 430 size_t asize = (size_t) (area->end - area->start) - shrink_size; 431 void *end = (void *) ((uintptr_t) area->start + asize); 432 433 /* Resize the address space area */ 434 int ret = as_area_resize(area->start, asize, 0); 435 if (ret != EOK) 436 abort(); 437 438 /* Update heap area parameters */ 439 area->end = end; 440 441 /* Update block layout */ 442 void *last = (void *) last_head; 443 size_t excess = (size_t) (area->end - last); 444 445 if (excess > 0) { 446 if (excess >= STRUCT_OVERHEAD) { 447 /* 448 * The previous block cannot be free and there 449 * is enough free space left in the area to 450 * create a new free block. 451 */ 452 block_init(last, excess, true, area); 453 } else { 454 /* 455 * The excess is small. Therefore just enlarge 456 * the previous block. 457 */ 458 heap_block_foot_t *prev_foot = (heap_block_foot_t *) 459 (((uintptr_t) last_head) - sizeof(heap_block_foot_t)); 460 heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot); 461 462 block_check((void *) prev_head); 463 464 block_init(prev_head, prev_head->size + excess, 465 prev_head->free, area); 466 } 467 } 468 469 470 } 471 } 472 337 473 next = NULL; 338 474 } … … 398 534 { 399 535 area_check((void *) area); 400 assert((void *) first_block >= (void *) AREA_FIRST_BLOCK (area));536 assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 401 537 assert((void *) first_block < area->end); 402 538 403 heap_block_head_t *cur; 404 for (cur = first_block; (void *) cur < area->end; 539 for (heap_block_head_t *cur = first_block; (void *) cur < area->end; 405 540 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 406 541 block_check(cur); … … 436 571 * data in (including alignment). 437 572 */ 438 if ((void *) cur > (void *) AREA_FIRST_BLOCK (area)) {573 if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 439 574 /* 440 575 * There is a block before the current block. … … 496 631 size_t reduced_size = cur->size - excess; 497 632 cur = (heap_block_head_t *) 498 (AREA_FIRST_BLOCK (area) + excess);633 (AREA_FIRST_BLOCK_HEAD(area) + excess); 499 634 500 block_init((void *) AREA_FIRST_BLOCK (area), excess,501 true, area);635 block_init((void *) AREA_FIRST_BLOCK_HEAD(area), 636 excess, true, area); 502 637 block_init(cur, reduced_size, true, area); 503 638 split_mark(cur, real_size); … … 552 687 553 688 /* Search the entire heap */ 554 heap_area_t *area;555 for (area = first_heap_area; area != NULL;area = area->next) {689 for (heap_area_t *area = first_heap_area; area != NULL; 690 area = area->next) { 556 691 heap_block_head_t *first = (heap_block_head_t *) 557 AREA_FIRST_BLOCK (area);692 AREA_FIRST_BLOCK_HEAD(area); 558 693 559 694 void *addr = malloc_area(area, first, split, real_size, … … 657 792 658 793 area_check(area); 659 assert((void *) head >= (void *) AREA_FIRST_BLOCK (area));794 assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 660 795 assert((void *) head < area->end); 661 796 … … 675 810 block_init((void *) head + real_size, 676 811 orig_size - real_size, true, area); 677 heap_shrink( );812 heap_shrink(area); 678 813 } 679 814 … … 734 869 735 870 area_check(area); 736 assert((void *) head >= (void *) AREA_FIRST_BLOCK (area));871 assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 737 872 assert((void *) head < area->end); 738 873 … … 751 886 752 887 /* Look at the previous block. If it is free, merge the two. */ 753 if ((void *) head > (void *) AREA_FIRST_BLOCK (area)) {888 if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 754 889 heap_block_foot_t *prev_foot = 755 890 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 765 900 } 766 901 767 heap_shrink( );902 heap_shrink(area); 768 903 769 904 futex_up(&malloc_futex);
Note:
See TracChangeset
for help on using the changeset viewer.