Changes in uspace/lib/c/generic/malloc.c [207533f:47b7006] in mainline
- File:
-
- 1 edited
-
uspace/lib/c/generic/malloc.c (modified) (18 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
r207533f r47b7006 44 44 #include <mem.h> 45 45 #include <futex.h> 46 #include <stdlib.h>47 46 #include <adt/gcdlcm.h> 48 47 #include "private/malloc.h" 49 48 50 /** Magic used in heap headers. */ 51 #define HEAP_BLOCK_HEAD_MAGIC UINT32_C(0xBEEF0101) 52 53 /** Magic used in heap footers. */ 54 #define HEAP_BLOCK_FOOT_MAGIC UINT32_C(0xBEEF0202) 55 56 /** Magic used in heap descriptor. */ 57 #define HEAP_AREA_MAGIC UINT32_C(0xBEEFCAFE) 58 59 /** Allocation alignment. 60 * 61 * This also covers the alignment of fields 62 * in the heap header and footer. 63 * 64 */ 49 /* Magic used in heap headers. */ 50 #define HEAP_BLOCK_HEAD_MAGIC 0xBEEF0101 51 52 /* Magic used in heap footers. */ 53 #define HEAP_BLOCK_FOOT_MAGIC 0xBEEF0202 54 55 /** Allocation alignment (this also covers the alignment of fields 56 in the heap header and footer) */ 65 57 #define BASE_ALIGN 16 66 58 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 77 /** Overhead of each heap block. */ 78 #define STRUCT_OVERHEAD \ 79 (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 80 81 /** Overhead of each area. */ 82 #define AREA_OVERHEAD(size) \ 83 (ALIGN_UP(size + sizeof(heap_area_t), BASE_ALIGN)) 84 85 /** Calculate real size of a heap block. 86 * 87 * Add header and footer size. 88 * 59 /** 60 * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures 61 */ 62 #define MAX_HEAP_SIZE (sizeof(uintptr_t) << 28) 63 64 /** 65 * 66 */ 67 #define STRUCT_OVERHEAD (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 68 69 /** 70 * Calculate real size of a heap block (with header and footer) 89 71 */ 90 72 #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) 91 73 92 /** Calculate net size of a heap block. 93 * 94 * Subtract header and footer size. 95 * 74 /** 75 * Calculate net size of a heap block (without header and footer) 96 76 */ 97 77 #define NET_SIZE(size) ((size) - STRUCT_OVERHEAD) 98 99 /** Get first block in heap area.100 *101 */102 #define AREA_FIRST_BLOCK_HEAD(area) \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))117 118 /** Get footer in heap block.119 *120 */121 #define BLOCK_FOOT(head) \122 ((heap_block_foot_t *) \123 (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t)))124 125 /** Heap area.126 *127 * The memory managed by the heap allocator is divided into128 * multiple discontinuous heaps. Each heap is represented129 * by a separate address space area which has this structure130 * at its very beginning.131 *132 */133 typedef struct heap_area {134 /** Start of the heap area (including this structure)135 *136 * Aligned on page boundary.137 *138 */139 void *start;140 141 /** End of the heap area (aligned on page boundary) */142 void *end;143 144 /** Previous heap area */145 struct heap_area *prev;146 147 /** Next heap area */148 struct heap_area *next;149 150 /** A magic value */151 uint32_t magic;152 } heap_area_t;153 78 154 79 /** Header of a heap block … … 162 87 bool free; 163 88 164 /** Heap area this block belongs to */165 heap_area_t *area;166 167 89 /* A magic value to detect overwrite of heap header */ 168 90 uint32_t magic; … … 180 102 } heap_block_foot_t; 181 103 182 /** First heap area */ 183 static heap_area_t *first_heap_area = NULL; 184 185 /** Last heap area */ 186 static heap_area_t *last_heap_area = NULL; 187 188 /** Next heap block to examine (next fit algorithm) */ 189 static heap_block_head_t *next_fit = NULL; 104 /** Linker heap symbol */ 105 extern char _heap; 190 106 191 107 /** Futex for thread-safe heap manipulation */ 192 108 static futex_t malloc_futex = FUTEX_INITIALIZER; 193 109 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 */ 110 /** Address of heap start */ 111 static void *heap_start = 0; 112 113 /** Address of heap end */ 114 static void *heap_end = 0; 115 116 /** Maximum heap size */ 117 static size_t max_heap_size = (size_t) -1; 118 119 /** Current number of pages of heap area */ 120 static size_t heap_pages = 0; 209 121 210 122 /** Initialize a heap block 211 123 * 212 * Fill in the structures related to a heap block.124 * Fills in the structures related to a heap block. 213 125 * Should be called only inside the critical section. 214 126 * … … 216 128 * @param size Size of the block including the header and the footer. 217 129 * @param free Indication of a free block. 218 * @param area Heap area the block belongs to. 219 * 220 */ 221 static void block_init(void *addr, size_t size, bool free, heap_area_t *area) 130 * 131 */ 132 static void block_init(void *addr, size_t size, bool free) 222 133 { 223 134 /* Calculate the position of the header and the footer */ 224 135 heap_block_head_t *head = (heap_block_head_t *) addr; 136 heap_block_foot_t *foot = 137 (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t)); 225 138 226 139 head->size = size; 227 140 head->free = free; 228 head->area = area;229 141 head->magic = HEAP_BLOCK_HEAD_MAGIC; 230 231 heap_block_foot_t *foot = BLOCK_FOOT(head);232 142 233 143 foot->size = size; … … 248 158 heap_block_head_t *head = (heap_block_head_t *) addr; 249 159 250 malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 251 252 heap_block_foot_t *foot = BLOCK_FOOT(head); 253 254 malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 255 malloc_assert(head->size == foot->size); 256 } 257 258 /** Check a heap area structure 160 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 161 162 heap_block_foot_t *foot = 163 (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); 164 165 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); 166 assert(head->size == foot->size); 167 } 168 169 /** Increase the heap area size 259 170 * 260 171 * Should be called only inside the critical section. 261 172 * 262 * @param addr Address of the heap area. 263 * 264 */ 265 static void area_check(void *addr) 266 { 267 heap_area_t *area = (heap_area_t *) addr; 268 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); 274 } 275 276 /** Create new heap area 173 * @param size Number of bytes to grow the heap by. 174 * 175 */ 176 static bool grow_heap(size_t size) 177 { 178 if (size == 0) 179 return false; 180 181 if ((heap_start + size < heap_start) || (heap_end + size < heap_end)) 182 return false; 183 184 size_t heap_size = (size_t) (heap_end - heap_start); 185 186 if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size)) 187 return false; 188 189 size_t pages = (size - 1) / PAGE_SIZE + 1; 190 191 if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0) 192 == EOK) { 193 void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) + 194 (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN); 195 block_init(heap_end, end - heap_end, true); 196 heap_pages += pages; 197 heap_end = end; 198 return true; 199 } 200 201 return false; 202 } 203 204 /** Decrease the heap area 277 205 * 278 206 * Should be called only inside the critical section. 279 207 * 280 * @param size Size of the area. 281 * 282 */ 283 static bool area_create(size_t size) 284 { 285 void *start = as_get_mappable_page(size); 286 if (start == NULL) 287 return false; 288 289 /* Align the heap area on page boundary */ 290 void *astart = (void *) ALIGN_UP((uintptr_t) start, PAGE_SIZE); 291 size_t asize = ALIGN_UP(size, PAGE_SIZE); 292 293 astart = as_area_create(astart, asize, AS_AREA_WRITE | AS_AREA_READ); 294 if (astart == (void *) -1) 295 return false; 296 297 heap_area_t *area = (heap_area_t *) astart; 298 299 area->start = astart; 300 area->end = (void *) ((uintptr_t) astart + asize); 301 area->prev = NULL; 302 area->next = NULL; 303 area->magic = HEAP_AREA_MAGIC; 304 305 void *block = (void *) AREA_FIRST_BLOCK_HEAD(area); 306 size_t bsize = (size_t) (area->end - block); 307 308 block_init(block, bsize, true, area); 309 310 if (last_heap_area == NULL) { 311 first_heap_area = area; 312 last_heap_area = area; 313 } else { 314 area->prev = last_heap_area; 315 last_heap_area->next = area; 316 last_heap_area = area; 317 } 318 319 return true; 320 } 321 322 /** Try to enlarge a heap area 323 * 324 * Should be called only inside the critical section. 325 * 326 * @param area Heap area to grow. 327 * @param size Gross size to grow (bytes). 328 * 329 * @return True if successful. 330 * 331 */ 332 static bool area_grow(heap_area_t *area, size_t size) 333 { 334 if (size == 0) 335 return true; 336 337 area_check(area); 338 339 /* New heap area size */ 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); 343 344 /* Check for overflow */ 345 if (end < area->start) 346 return false; 347 348 /* Resize the address space area */ 349 int ret = as_area_resize(area->start, asize, 0); 350 if (ret != EOK) 351 return false; 352 353 /* Add new free block */ 354 size_t net_size = (size_t) (end - area->end); 355 if (net_size > 0) 356 block_init(area->end, net_size, true, area); 357 358 /* Update heap area parameters */ 359 area->end = end; 360 361 return true; 362 } 363 364 /** Try to enlarge any of the heap areas 365 * 366 * Should be called only inside the critical section. 367 * 368 * @param size Gross size of item to allocate (bytes). 369 * 370 */ 371 static bool heap_grow(size_t size) 372 { 373 if (size == 0) 374 return true; 375 376 /* First try to enlarge some existing area */ 377 for (heap_area_t *area = first_heap_area; area != NULL; 378 area = area->next) { 379 if (area_grow(area, size)) 380 return true; 381 } 382 383 /* Eventually try to create a new area */ 384 return area_create(AREA_OVERHEAD(size)); 385 } 386 387 /** Try to shrink heap 388 * 389 * Should be called only inside the critical section. 390 * In all cases the next pointer is reset. 391 * 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; 208 * @param size Number of bytes to shrink the heap by. 209 * 210 */ 211 static void shrink_heap(void) 212 { 213 // TODO 490 214 } 491 215 … … 499 223 void __malloc_init(void) 500 224 { 501 if (!area_create(PAGE_SIZE)) 225 if (!as_area_create((void *) &_heap, PAGE_SIZE, 226 AS_AREA_WRITE | AS_AREA_READ)) 502 227 abort(); 228 229 heap_pages = 1; 230 heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN); 231 heap_end = 232 (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN); 233 234 /* Make the entire area one large block. */ 235 block_init(heap_start, heap_end - heap_start, true); 236 } 237 238 /** Get maximum heap address 239 * 240 */ 241 uintptr_t get_max_heap_addr(void) 242 { 243 futex_down(&malloc_futex); 244 245 if (max_heap_size == (size_t) -1) 246 max_heap_size = 247 max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE); 248 249 uintptr_t max_heap_addr = (uintptr_t) heap_start + max_heap_size; 250 251 futex_up(&malloc_futex); 252 253 return max_heap_addr; 503 254 } 504 255 … … 514 265 static void split_mark(heap_block_head_t *cur, const size_t size) 515 266 { 516 malloc_assert(cur->size >= size);267 assert(cur->size >= size); 517 268 518 269 /* See if we should split the block. */ … … 522 273 /* Block big enough -> split. */ 523 274 void *next = ((void *) cur) + size; 524 block_init(next, cur->size - size, true , cur->area);525 block_init(cur, size, false , cur->area);275 block_init(next, cur->size - size, true); 276 block_init(cur, size, false); 526 277 } else { 527 278 /* Block too small -> use as is. */ … … 530 281 } 531 282 532 /** Allocate memory from heap area starting from givenblock283 /** Allocate a memory block 533 284 * 534 285 * Should be called only inside the critical section. 535 * As a side effect this function also sets the current 536 * pointer on successful allocation. 537 * 538 * @param area Heap area where to allocate from. 539 * @param first_block Starting heap block. 540 * @param final_block Heap block where to finish the search 541 * (may be NULL). 542 * @param real_size Gross number of bytes to allocate. 543 * @param falign Physical alignment of the block. 544 * 545 * @return Address of the allocated block or NULL on not enough memory. 546 * 547 */ 548 static void *malloc_area(heap_area_t *area, heap_block_head_t *first_block, 549 heap_block_head_t *final_block, size_t real_size, size_t falign) 550 { 551 area_check((void *) area); 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; 556 cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { 286 * 287 * @param size The size of the block to allocate. 288 * @param align Memory address alignment. 289 * 290 * @return the address of the block or NULL when not enough memory. 291 * 292 */ 293 static void *malloc_internal(const size_t size, const size_t align) 294 { 295 if (align == 0) 296 return NULL; 297 298 size_t falign = lcm(align, BASE_ALIGN); 299 size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); 300 301 bool grown = false; 302 void *result; 303 304 loop: 305 result = NULL; 306 heap_block_head_t *cur = (heap_block_head_t *) heap_start; 307 308 while ((result == NULL) && ((void *) cur < heap_end)) { 557 309 block_check(cur); 558 559 /* Finish searching on the final block */560 if ((final_block != NULL) && (cur == final_block))561 break;562 310 563 311 /* Try to find a block that is free and large enough. */ 564 312 if ((cur->free) && (cur->size >= real_size)) { 565 /* 566 * We have found a suitable block. 567 * Check for alignment properties. 568 */ 569 void *addr = (void *) 570 ((uintptr_t) cur + sizeof(heap_block_head_t)); 571 void *aligned = (void *) 572 ALIGN_UP((uintptr_t) addr, falign); 313 /* We have found a suitable block. 314 Check for alignment properties. */ 315 void *addr = ((void *) cur) + sizeof(heap_block_head_t); 316 void *aligned = (void *) ALIGN_UP(addr, falign); 573 317 574 318 if (addr == aligned) { 575 319 /* Exact block start including alignment. */ 576 320 split_mark(cur, real_size); 577 578 next_fit = cur; 579 return addr; 321 result = addr; 580 322 } else { 581 323 /* Block start has to be aligned */ … … 583 325 584 326 if (cur->size >= real_size + excess) { 585 /* 586 * The current block is large enough to fit 587 * data in (including alignment). 588 */ 589 if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) { 590 /* 591 * There is a block before the current block. 592 * This previous block can be enlarged to 593 * compensate for the alignment excess. 594 */ 595 heap_block_foot_t *prev_foot = (heap_block_foot_t *) 596 ((void *) cur - sizeof(heap_block_foot_t)); 327 /* The current block is large enough to fit 328 data in including alignment */ 329 if ((void *) cur > heap_start) { 330 /* There is a block before the current block. 331 This previous block can be enlarged to compensate 332 for the alignment excess */ 333 heap_block_foot_t *prev_foot = 334 ((void *) cur) - sizeof(heap_block_foot_t); 597 335 598 heap_block_head_t *prev_head = (heap_block_head_t *)599 ( (void *) cur- prev_foot->size);336 heap_block_head_t *prev_head = 337 (heap_block_head_t *) (((void *) cur) - prev_foot->size); 600 338 601 339 block_check(prev_head); … … 604 342 heap_block_head_t *next_head = ((void *) cur) + excess; 605 343 606 if ((!prev_head->free) && 607 (excess >= STRUCT_OVERHEAD)) { 608 /* 609 * The previous block is not free and there 610 * is enough free space left to fill in 611 * a new free block between the previous 612 * and current block. 613 */ 614 block_init(cur, excess, true, area); 344 if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) { 345 /* The previous block is not free and there is enough 346 space to fill in a new free block between the previous 347 and current block */ 348 block_init(cur, excess, true); 615 349 } else { 616 /* 617 * The previous block is free (thus there 618 * is no need to induce additional 619 * fragmentation to the heap) or the 620 * excess is small. Therefore just enlarge 621 * the previous block. 622 */ 623 block_init(prev_head, prev_head->size + excess, 624 prev_head->free, area); 350 /* The previous block is free (thus there is no need to 351 induce additional fragmentation to the heap) or the 352 excess is small, thus just enlarge the previous block */ 353 block_init(prev_head, prev_head->size + excess, prev_head->free); 625 354 } 626 355 627 block_init(next_head, reduced_size, true , area);356 block_init(next_head, reduced_size, true); 628 357 split_mark(next_head, real_size); 629 630 next_fit = next_head; 631 return aligned; 358 result = aligned; 359 cur = next_head; 632 360 } else { 633 /* 634 * The current block is the first block 635 * in the heap area. We have to make sure 636 * that the alignment excess is large enough 637 * to fit a new free block just before the 638 * current block. 639 */ 361 /* The current block is the first block on the heap. 362 We have to make sure that the alignment excess 363 is large enough to fit a new free block just 364 before the current block */ 640 365 while (excess < STRUCT_OVERHEAD) { 641 366 aligned += falign; … … 646 371 if (cur->size >= real_size + excess) { 647 372 size_t reduced_size = cur->size - excess; 648 cur = (heap_block_head_t *) 649 (AREA_FIRST_BLOCK_HEAD(area) + excess); 373 cur = (heap_block_head_t *) (heap_start + excess); 650 374 651 block_init((void *) AREA_FIRST_BLOCK_HEAD(area), 652 excess, true, area); 653 block_init(cur, reduced_size, true, area); 375 block_init(heap_start, excess, true); 376 block_init(cur, reduced_size, true); 654 377 split_mark(cur, real_size); 655 656 next_fit = cur; 657 return aligned; 378 result = aligned; 658 379 } 659 380 } … … 661 382 } 662 383 } 663 } 664 665 return NULL; 666 } 667 668 /** Allocate a memory block 669 * 670 * Should be called only inside the critical section. 671 * 672 * @param size The size of the block to allocate. 673 * @param align Memory address alignment. 674 * 675 * @return Address of the allocated block or NULL on not enough memory. 676 * 677 */ 678 static void *malloc_internal(const size_t size, const size_t align) 679 { 680 malloc_assert(first_heap_area != NULL); 681 682 if (align == 0) 683 return NULL; 684 685 size_t falign = lcm(align, BASE_ALIGN); 686 size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); 687 688 bool retry = false; 689 heap_block_head_t *split; 690 691 loop: 692 693 /* Try the next fit approach */ 694 split = next_fit; 695 696 if (split != NULL) { 697 void *addr = malloc_area(split->area, split, NULL, real_size, 698 falign); 699 700 if (addr != NULL) 701 return addr; 702 } 703 704 /* Search the entire heap */ 705 for (heap_area_t *area = first_heap_area; area != NULL; 706 area = area->next) { 707 heap_block_head_t *first = (heap_block_head_t *) 708 AREA_FIRST_BLOCK_HEAD(area); 709 710 void *addr = malloc_area(area, first, split, real_size, 711 falign); 712 713 if (addr != NULL) 714 return addr; 715 } 716 717 if (!retry) { 718 /* Try to grow the heap space */ 719 if (heap_grow(real_size)) { 720 retry = true; 384 385 /* Advance to the next block. */ 386 cur = (heap_block_head_t *) (((void *) cur) + cur->size); 387 } 388 389 if ((result == NULL) && (!grown)) { 390 if (grow_heap(real_size)) { 391 grown = true; 721 392 goto loop; 722 393 } 723 394 } 724 395 725 return NULL;396 return result; 726 397 } 727 398 … … 802 473 (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 803 474 475 assert((void *) head >= heap_start); 476 assert((void *) head < heap_end); 477 804 478 block_check(head); 805 malloc_assert(!head->free); 806 807 heap_area_t *area = head->area; 808 809 area_check(area); 810 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 811 malloc_assert((void *) head < area->end); 479 assert(!head->free); 812 480 813 481 void *ptr = NULL; … … 819 487 /* Shrink */ 820 488 if (orig_size - real_size >= STRUCT_OVERHEAD) { 821 /* 822 * Split the original block to a full block 823 * and a trailing free block. 824 */ 825 block_init((void *) head, real_size, false, area); 489 /* Split the original block to a full block 490 and a trailing free block */ 491 block_init((void *) head, real_size, false); 826 492 block_init((void *) head + real_size, 827 orig_size - real_size, true , area);828 heap_shrink(area);493 orig_size - real_size, true); 494 shrink_heap(); 829 495 } 830 496 831 497 ptr = ((void *) head) + sizeof(heap_block_head_t); 832 498 } else { 833 /* 834 * Look at the next block. If it is free and the size is 835 * sufficient then merge the two. Otherwise just allocate 836 * a new block, copy the original data into it and 837 * free the original block. 838 */ 499 /* Look at the next block. If it is free and the size is 500 sufficient then merge the two. Otherwise just allocate 501 a new block, copy the original data into it and 502 free the original block. */ 839 503 heap_block_head_t *next_head = 840 504 (heap_block_head_t *) (((void *) head) + head->size); 841 505 842 if (((void *) next_head < area->end) &&506 if (((void *) next_head < heap_end) && 843 507 (head->size + next_head->size >= real_size) && 844 508 (next_head->free)) { 845 509 block_check(next_head); 846 block_init(head, head->size + next_head->size, false , area);510 block_init(head, head->size + next_head->size, false); 847 511 split_mark(head, real_size); 848 512 849 513 ptr = ((void *) head) + sizeof(heap_block_head_t); 850 next_fit = NULL;851 514 } else 852 515 reloc = true; … … 879 542 = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 880 543 544 assert((void *) head >= heap_start); 545 assert((void *) head < heap_end); 546 881 547 block_check(head); 882 malloc_assert(!head->free); 883 884 heap_area_t *area = head->area; 885 886 area_check(area); 887 malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area)); 888 malloc_assert((void *) head < area->end); 548 assert(!head->free); 889 549 890 550 /* Mark the block itself as free. */ … … 895 555 = (heap_block_head_t *) (((void *) head) + head->size); 896 556 897 if ((void *) next_head < area->end) {557 if ((void *) next_head < heap_end) { 898 558 block_check(next_head); 899 559 if (next_head->free) 900 block_init(head, head->size + next_head->size, true , area);560 block_init(head, head->size + next_head->size, true); 901 561 } 902 562 903 563 /* Look at the previous block. If it is free, merge the two. */ 904 if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) {564 if ((void *) head > heap_start) { 905 565 heap_block_foot_t *prev_foot = 906 566 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 912 572 913 573 if (prev_head->free) 914 block_init(prev_head, prev_head->size + head->size, true, 915 area); 916 } 917 918 heap_shrink(area); 574 block_init(prev_head, prev_head->size + head->size, true); 575 } 576 577 shrink_heap(); 919 578 920 579 futex_up(&malloc_futex); 921 580 } 922 581 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 972 582 /** @} 973 583 */
Note:
See TracChangeset
for help on using the changeset viewer.
