Changes in uspace/lib/c/generic/malloc.c [d161715:47b7006] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
rd161715 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 /** Overhead of each heap block. */ 68 #define STRUCT_OVERHEAD \ 69 (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 70 71 /** Calculate real size of a heap block. 72 * 73 * Add header and footer size. 74 * 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) 75 71 */ 76 72 #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) 77 73 78 /** Calculate net size of a heap block. 79 * 80 * Subtract header and footer size. 81 * 74 /** 75 * Calculate net size of a heap block (without header and footer) 82 76 */ 83 77 #define NET_SIZE(size) ((size) - STRUCT_OVERHEAD) 84 85 /** Get first block in heap area.86 *87 */88 #define AREA_FIRST_BLOCK(area) \89 (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN))90 91 /** Get footer in heap block.92 *93 */94 #define BLOCK_FOOT(head) \95 ((heap_block_foot_t *) \96 (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t)))97 98 /** Heap area.99 *100 * The memory managed by the heap allocator is divided into101 * multiple discontinuous heaps. Each heap is represented102 * by a separate address space area which has this structure103 * at its very beginning.104 *105 */106 typedef struct heap_area {107 /** Start of the heap area (including this structure)108 *109 * Aligned on page boundary.110 *111 */112 void *start;113 114 /** End of the heap area (aligned on page boundary) */115 void *end;116 117 /** Next heap area */118 struct heap_area *next;119 120 /** A magic value */121 uint32_t magic;122 } heap_area_t;123 78 124 79 /** Header of a heap block … … 132 87 bool free; 133 88 134 /** Heap area this block belongs to */135 heap_area_t *area;136 137 89 /* A magic value to detect overwrite of heap header */ 138 90 uint32_t magic; … … 150 102 } heap_block_foot_t; 151 103 152 /** First heap area */ 153 static heap_area_t *first_heap_area = NULL; 154 155 /** Last heap area */ 156 static heap_area_t *last_heap_area = NULL; 157 158 /** Next heap block to examine (next fit algorithm) */ 159 static heap_block_head_t *next = NULL; 104 /** Linker heap symbol */ 105 extern char _heap; 160 106 161 107 /** Futex for thread-safe heap manipulation */ 162 108 static futex_t malloc_futex = FUTEX_INITIALIZER; 163 109 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; 121 164 122 /** Initialize a heap block 165 123 * 166 * Fill in the structures related to a heap block.124 * Fills in the structures related to a heap block. 167 125 * Should be called only inside the critical section. 168 126 * … … 170 128 * @param size Size of the block including the header and the footer. 171 129 * @param free Indication of a free block. 172 * @param area Heap area the block belongs to. 173 * 174 */ 175 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) 176 133 { 177 134 /* Calculate the position of the header and the footer */ 178 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)); 179 138 180 139 head->size = size; 181 140 head->free = free; 182 head->area = area;183 141 head->magic = HEAP_BLOCK_HEAD_MAGIC; 184 185 heap_block_foot_t *foot = BLOCK_FOOT(head);186 142 187 143 foot->size = size; … … 204 160 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 205 161 206 heap_block_foot_t *foot = BLOCK_FOOT(head); 162 heap_block_foot_t *foot = 163 (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); 207 164 208 165 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); … … 210 167 } 211 168 212 /** Check a heap area structure 213 * 214 * @param addr Address of the heap area. 215 * 216 */ 217 static void area_check(void *addr) 218 { 219 heap_area_t *area = (heap_area_t *) addr; 220 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); 225 } 226 227 /** Create new heap area 228 * 229 * @param start Preffered starting address of the new area. 230 * @param size Size of the area. 231 * 232 */ 233 static bool area_create(size_t size) 234 { 235 void *start = as_get_mappable_page(size); 236 if (start == NULL) 169 /** Increase the heap area size 170 * 171 * Should be called only inside the critical section. 172 * 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) 237 179 return false; 238 239 /* Align the heap area on page boundary */ 240 void *astart = (void *) ALIGN_UP((uintptr_t) start, PAGE_SIZE); 241 size_t asize = ALIGN_UP(size, PAGE_SIZE); 242 243 astart = as_area_create(astart, asize, AS_AREA_WRITE | AS_AREA_READ); 244 if (astart == (void *) -1) 180 181 if ((heap_start + size < heap_start) || (heap_end + size < heap_end)) 245 182 return false; 246 183 247 heap_area_t *area = (heap_area_t *) astart; 248 249 area->start = astart; 250 area->end = (void *) 251 ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN); 252 area->next = NULL; 253 area->magic = HEAP_AREA_MAGIC; 254 255 void *block = (void *) AREA_FIRST_BLOCK(area); 256 size_t bsize = (size_t) (area->end - block); 257 258 block_init(block, bsize, true, area); 259 260 if (last_heap_area == NULL) { 261 first_heap_area = area; 262 last_heap_area = area; 263 } else { 264 last_heap_area->next = area; 265 last_heap_area = area; 266 } 267 268 return true; 269 } 270 271 /** Try to enlarge a heap area 272 * 273 * @param area Heap area to grow. 274 * @param size Gross size of item to allocate (bytes). 275 * 276 */ 277 static bool area_grow(heap_area_t *area, size_t size) 278 { 279 if (size == 0) 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; 280 198 return true; 281 282 area_check(area); 283 284 size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size, 285 PAGE_SIZE); 286 287 /* New heap area size */ 288 void *end = (void *) 289 ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN); 290 291 /* Check for overflow */ 292 if (end < area->start) 293 return false; 294 295 /* Resize the address space area */ 296 int ret = as_area_resize(area->start, asize, 0); 297 if (ret != EOK) 298 return false; 299 300 /* Add new free block */ 301 block_init(area->end, (size_t) (end - area->end), true, area); 302 303 /* Update heap area parameters */ 304 area->end = end; 305 306 return true; 307 } 308 309 /** Try to enlarge any of the heap areas 310 * 311 * @param size Gross size of item to allocate (bytes). 312 * 313 */ 314 static bool heap_grow(size_t size) 315 { 316 if (size == 0) 317 return true; 318 319 /* First try to enlarge some existing area */ 320 heap_area_t *area; 321 for (area = first_heap_area; area != NULL; area = area->next) { 322 if (area_grow(area, size)) 323 return true; 324 } 325 326 /* Eventually try to create a new area */ 327 return area_create(AREA_FIRST_BLOCK(size)); 328 } 329 330 /** Try to shrink heap space 331 * 332 * In all cases the next pointer is reset. 333 * 334 */ 335 static void heap_shrink(void) 336 { 337 next = NULL; 199 } 200 201 return false; 202 } 203 204 /** Decrease the heap area 205 * 206 * Should be called only inside the critical section. 207 * 208 * @param size Number of bytes to shrink the heap by. 209 * 210 */ 211 static void shrink_heap(void) 212 { 213 // TODO 338 214 } 339 215 … … 347 223 void __malloc_init(void) 348 224 { 349 if (!area_create(PAGE_SIZE)) 225 if (!as_area_create((void *) &_heap, PAGE_SIZE, 226 AS_AREA_WRITE | AS_AREA_READ)) 350 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; 351 254 } 352 255 … … 370 273 /* Block big enough -> split. */ 371 274 void *next = ((void *) cur) + size; 372 block_init(next, cur->size - size, true , cur->area);373 block_init(cur, size, false , cur->area);275 block_init(next, cur->size - size, true); 276 block_init(cur, size, false); 374 277 } else { 375 278 /* Block too small -> use as is. */ … … 378 281 } 379 282 380 /** Allocate memory from heap area starting from givenblock283 /** Allocate a memory block 381 284 * 382 285 * Should be called only inside the critical section. 383 * As a side effect this function also sets the current384 * pointer on successful allocation.385 * 386 * @param area Heap area where to allocate from.387 * @ param first_block Starting heap block.388 * @param final_block Heap block where to finish the search389 * (may be NULL).390 * @param real_size Gross number of bytes to allocate. 391 * @param falign Physical alignment of the block. 392 * 393 * @return Address of the allocated block or NULL on not enough memory. 394 * 395 */ 396 static void *malloc_area(heap_area_t *area, heap_block_head_t *first_block, 397 heap_block_head_t *final_block, size_t real_size, size_t falign) 398 { 399 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;405 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)) { 406 309 block_check(cur); 407 408 /* Finish searching on the final block */409 if ((final_block != NULL) && (cur == final_block))410 break;411 310 412 311 /* Try to find a block that is free and large enough. */ 413 312 if ((cur->free) && (cur->size >= real_size)) { 414 /* 415 * We have found a suitable block. 416 * Check for alignment properties. 417 */ 418 void *addr = (void *) 419 ((uintptr_t) cur + sizeof(heap_block_head_t)); 420 void *aligned = (void *) 421 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); 422 317 423 318 if (addr == aligned) { 424 319 /* Exact block start including alignment. */ 425 320 split_mark(cur, real_size); 426 427 next = cur; 428 return addr; 321 result = addr; 429 322 } else { 430 323 /* Block start has to be aligned */ … … 432 325 433 326 if (cur->size >= real_size + excess) { 434 /* 435 * The current block is large enough to fit 436 * data in (including alignment). 437 */ 438 if ((void *) cur > (void *) AREA_FIRST_BLOCK(area)) { 439 /* 440 * There is a block before the current block. 441 * This previous block can be enlarged to 442 * compensate for the alignment excess. 443 */ 444 heap_block_foot_t *prev_foot = (heap_block_foot_t *) 445 ((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); 446 335 447 heap_block_head_t *prev_head = (heap_block_head_t *)448 ( (void *) cur- prev_foot->size);336 heap_block_head_t *prev_head = 337 (heap_block_head_t *) (((void *) cur) - prev_foot->size); 449 338 450 339 block_check(prev_head); … … 453 342 heap_block_head_t *next_head = ((void *) cur) + excess; 454 343 455 if ((!prev_head->free) && 456 (excess >= STRUCT_OVERHEAD)) { 457 /* 458 * The previous block is not free and there 459 * is enough free space left to fill in 460 * a new free block between the previous 461 * and current block. 462 */ 463 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); 464 349 } else { 465 /* 466 * The previous block is free (thus there 467 * is no need to induce additional 468 * fragmentation to the heap) or the 469 * excess is small. Therefore just enlarge 470 * the previous block. 471 */ 472 block_init(prev_head, prev_head->size + excess, 473 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); 474 354 } 475 355 476 block_init(next_head, reduced_size, true , area);356 block_init(next_head, reduced_size, true); 477 357 split_mark(next_head, real_size); 478 479 next = next_head; 480 return aligned; 358 result = aligned; 359 cur = next_head; 481 360 } else { 482 /* 483 * The current block is the first block 484 * in the heap area. We have to make sure 485 * that the alignment excess is large enough 486 * to fit a new free block just before the 487 * current block. 488 */ 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 */ 489 365 while (excess < STRUCT_OVERHEAD) { 490 366 aligned += falign; … … 495 371 if (cur->size >= real_size + excess) { 496 372 size_t reduced_size = cur->size - excess; 497 cur = (heap_block_head_t *) 498 (AREA_FIRST_BLOCK(area) + excess); 373 cur = (heap_block_head_t *) (heap_start + excess); 499 374 500 block_init((void *) AREA_FIRST_BLOCK(area), excess, 501 true, area); 502 block_init(cur, reduced_size, true, area); 375 block_init(heap_start, excess, true); 376 block_init(cur, reduced_size, true); 503 377 split_mark(cur, real_size); 504 505 next = cur; 506 return aligned; 378 result = aligned; 507 379 } 508 380 } … … 510 382 } 511 383 } 512 } 513 514 return NULL; 515 } 516 517 /** Allocate a memory block 518 * 519 * Should be called only inside the critical section. 520 * 521 * @param size The size of the block to allocate. 522 * @param align Memory address alignment. 523 * 524 * @return Address of the allocated block or NULL on not enough memory. 525 * 526 */ 527 static void *malloc_internal(const size_t size, const size_t align) 528 { 529 assert(first_heap_area != NULL); 530 531 if (align == 0) 532 return NULL; 533 534 size_t falign = lcm(align, BASE_ALIGN); 535 size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); 536 537 bool retry = false; 538 heap_block_head_t *split; 539 540 loop: 541 542 /* Try the next fit approach */ 543 split = next; 544 545 if (split != NULL) { 546 void *addr = malloc_area(split->area, split, NULL, real_size, 547 falign); 548 549 if (addr != NULL) 550 return addr; 551 } 552 553 /* Search the entire heap */ 554 heap_area_t *area; 555 for (area = first_heap_area; area != NULL; area = area->next) { 556 heap_block_head_t *first = (heap_block_head_t *) 557 AREA_FIRST_BLOCK(area); 558 559 void *addr = malloc_area(area, first, split, real_size, 560 falign); 561 562 if (addr != NULL) 563 return addr; 564 } 565 566 if (!retry) { 567 /* Try to grow the heap space */ 568 if (heap_grow(real_size)) { 569 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; 570 392 goto loop; 571 393 } 572 394 } 573 395 574 return NULL;396 return result; 575 397 } 576 398 … … 651 473 (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 652 474 475 assert((void *) head >= heap_start); 476 assert((void *) head < heap_end); 477 653 478 block_check(head); 654 479 assert(!head->free); 655 656 heap_area_t *area = head->area;657 658 area_check(area);659 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));660 assert((void *) head < area->end);661 480 662 481 void *ptr = NULL; … … 668 487 /* Shrink */ 669 488 if (orig_size - real_size >= STRUCT_OVERHEAD) { 670 /* 671 * Split the original block to a full block 672 * and a trailing free block. 673 */ 674 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); 675 492 block_init((void *) head + real_size, 676 orig_size - real_size, true , area);677 heap_shrink();493 orig_size - real_size, true); 494 shrink_heap(); 678 495 } 679 496 680 497 ptr = ((void *) head) + sizeof(heap_block_head_t); 681 498 } else { 682 /* 683 * Look at the next block. If it is free and the size is 684 * sufficient then merge the two. Otherwise just allocate 685 * a new block, copy the original data into it and 686 * free the original block. 687 */ 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. */ 688 503 heap_block_head_t *next_head = 689 504 (heap_block_head_t *) (((void *) head) + head->size); 690 505 691 if (((void *) next_head < area->end) &&506 if (((void *) next_head < heap_end) && 692 507 (head->size + next_head->size >= real_size) && 693 508 (next_head->free)) { 694 509 block_check(next_head); 695 block_init(head, head->size + next_head->size, false , area);510 block_init(head, head->size + next_head->size, false); 696 511 split_mark(head, real_size); 697 512 698 513 ptr = ((void *) head) + sizeof(heap_block_head_t); 699 next = NULL;700 514 } else 701 515 reloc = true; … … 728 542 = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 729 543 544 assert((void *) head >= heap_start); 545 assert((void *) head < heap_end); 546 730 547 block_check(head); 731 548 assert(!head->free); 732 733 heap_area_t *area = head->area;734 735 area_check(area);736 assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));737 assert((void *) head < area->end);738 549 739 550 /* Mark the block itself as free. */ … … 744 555 = (heap_block_head_t *) (((void *) head) + head->size); 745 556 746 if ((void *) next_head < area->end) {557 if ((void *) next_head < heap_end) { 747 558 block_check(next_head); 748 559 if (next_head->free) 749 block_init(head, head->size + next_head->size, true , area);560 block_init(head, head->size + next_head->size, true); 750 561 } 751 562 752 563 /* Look at the previous block. If it is free, merge the two. */ 753 if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) {564 if ((void *) head > heap_start) { 754 565 heap_block_foot_t *prev_foot = 755 566 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 761 572 762 573 if (prev_head->free) 763 block_init(prev_head, prev_head->size + head->size, true, 764 area); 765 } 766 767 heap_shrink(); 574 block_init(prev_head, prev_head->size + head->size, true); 575 } 576 577 shrink_heap(); 768 578 769 579 futex_up(&malloc_futex);
Note:
See TracChangeset
for help on using the changeset viewer.