Changes in uspace/lib/c/generic/malloc.c [d161715:3292623] in mainline
- File:
-
- 1 edited
-
uspace/lib/c/generic/malloc.c (modified) (17 diffs)
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/c/generic/malloc.c
rd161715 r3292623 44 44 #include <mem.h> 45 45 #include <futex.h> 46 #include <stdlib.h>47 46 #include <adt/gcdlcm.h> 48 #include "private/malloc.h" 49 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 */ 47 48 /* Magic used in heap headers. */ 49 #define HEAP_BLOCK_HEAD_MAGIC 0xBEEF0101 50 51 /* Magic used in heap footers. */ 52 #define HEAP_BLOCK_FOOT_MAGIC 0xBEEF0202 53 54 /** Allocation alignment (this also covers the alignment of fields 55 in the heap header and footer) */ 65 56 #define BASE_ALIGN 16 66 57 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 * 58 /** 59 * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures 60 */ 61 #define MAX_HEAP_SIZE (sizeof(uintptr_t) << 28) 62 63 /** 64 * 65 */ 66 #define STRUCT_OVERHEAD (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) 67 68 /** 69 * Calculate real size of a heap block (with header and footer) 75 70 */ 76 71 #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) 77 72 78 /** Calculate net size of a heap block. 79 * 80 * Subtract header and footer size. 81 * 73 /** 74 * Calculate net size of a heap block (without header and footer) 82 75 */ 83 76 #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 77 124 78 /** Header of a heap block … … 132 86 bool free; 133 87 134 /** Heap area this block belongs to */135 heap_area_t *area;136 137 88 /* A magic value to detect overwrite of heap header */ 138 89 uint32_t magic; … … 150 101 } heap_block_foot_t; 151 102 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; 103 /** Linker heap symbol */ 104 extern char _heap; 160 105 161 106 /** Futex for thread-safe heap manipulation */ 162 107 static futex_t malloc_futex = FUTEX_INITIALIZER; 163 108 109 /** Address of heap start */ 110 static void *heap_start = 0; 111 112 /** Address of heap end */ 113 static void *heap_end = 0; 114 115 /** Maximum heap size */ 116 static size_t max_heap_size = (size_t) -1; 117 118 /** Current number of pages of heap area */ 119 static size_t heap_pages = 0; 120 164 121 /** Initialize a heap block 165 122 * 166 * Fill in the structures related to a heap block.123 * Fills in the structures related to a heap block. 167 124 * Should be called only inside the critical section. 168 125 * … … 170 127 * @param size Size of the block including the header and the footer. 171 128 * @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) 129 * 130 */ 131 static void block_init(void *addr, size_t size, bool free) 176 132 { 177 133 /* Calculate the position of the header and the footer */ 178 134 heap_block_head_t *head = (heap_block_head_t *) addr; 135 heap_block_foot_t *foot = 136 (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t)); 179 137 180 138 head->size = size; 181 139 head->free = free; 182 head->area = area;183 140 head->magic = HEAP_BLOCK_HEAD_MAGIC; 184 185 heap_block_foot_t *foot = BLOCK_FOOT(head);186 141 187 142 foot->size = size; … … 204 159 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 205 160 206 heap_block_foot_t *foot = BLOCK_FOOT(head); 161 heap_block_foot_t *foot = 162 (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); 207 163 208 164 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); … … 210 166 } 211 167 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) 168 /** Increase the heap area size 169 * 170 * Should be called only inside the critical section. 171 * 172 * @param size Number of bytes to grow the heap by. 173 * 174 */ 175 static bool grow_heap(size_t size) 176 { 177 if (size == 0) 237 178 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) 179 180 if ((heap_start + size < heap_start) || (heap_end + size < heap_end)) 245 181 return false; 246 182 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) 183 size_t heap_size = (size_t) (heap_end - heap_start); 184 185 if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size)) 186 return false; 187 188 size_t pages = (size - 1) / PAGE_SIZE + 1; 189 190 if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0) 191 == EOK) { 192 void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) + 193 (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN); 194 block_init(heap_end, end - heap_end, true); 195 heap_pages += pages; 196 heap_end = end; 280 197 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; 198 } 199 200 return false; 201 } 202 203 /** Decrease the heap area 204 * 205 * Should be called only inside the critical section. 206 * 207 * @param size Number of bytes to shrink the heap by. 208 * 209 */ 210 static void shrink_heap(void) 211 { 212 // TODO 338 213 } 339 214 340 215 /** Initialize the heap allocator 341 216 * 342 * Create initial heap memory area. This routine is 343 * only called from libc initialization, thus we do not 344 * take any locks. 345 * 346 */ 347 void __malloc_init(void) 348 { 349 if (!area_create(PAGE_SIZE)) 350 abort(); 217 * Find how much physical memory we have and create 218 * the heap management structures that mark the whole 219 * physical memory as a single free block. 220 * 221 */ 222 void __heap_init(void) 223 { 224 futex_down(&malloc_futex); 225 226 if (as_area_create((void *) &_heap, PAGE_SIZE, 227 AS_AREA_WRITE | AS_AREA_READ)) { 228 heap_pages = 1; 229 heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN); 230 heap_end = 231 (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN); 232 233 /* Make the entire area one large block. */ 234 block_init(heap_start, heap_end - heap_start, true); 235 } 236 237 futex_up(&malloc_futex); 238 } 239 240 /** Get maximum heap address 241 * 242 */ 243 uintptr_t get_max_heap_addr(void) 244 { 245 futex_down(&malloc_futex); 246 247 if (max_heap_size == (size_t) -1) 248 max_heap_size = 249 max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE); 250 251 uintptr_t max_heap_addr = (uintptr_t) heap_start + max_heap_size; 252 253 futex_up(&malloc_futex); 254 255 return max_heap_addr; 351 256 } 352 257 … … 370 275 /* Block big enough -> split. */ 371 276 void *next = ((void *) cur) + size; 372 block_init(next, cur->size - size, true , cur->area);373 block_init(cur, size, false , cur->area);277 block_init(next, cur->size - size, true); 278 block_init(cur, size, false); 374 279 } else { 375 280 /* Block too small -> use as is. */ … … 378 283 } 379 284 380 /** Allocate memory from heap area starting from givenblock285 /** Allocate a memory block 381 286 * 382 287 * 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)) {288 * 289 * @param size The size of the block to allocate. 290 * @param align Memory address alignment. 291 * 292 * @return the address of the block or NULL when not enough memory. 293 * 294 */ 295 static void *malloc_internal(const size_t size, const size_t align) 296 { 297 if (align == 0) 298 return NULL; 299 300 size_t falign = lcm(align, BASE_ALIGN); 301 size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); 302 303 bool grown = false; 304 void *result; 305 306 loop: 307 result = NULL; 308 heap_block_head_t *cur = (heap_block_head_t *) heap_start; 309 310 while ((result == NULL) && ((void *) cur < heap_end)) { 406 311 block_check(cur); 407 408 /* Finish searching on the final block */409 if ((final_block != NULL) && (cur == final_block))410 break;411 312 412 313 /* Try to find a block that is free and large enough. */ 413 314 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); 315 /* We have found a suitable block. 316 Check for alignment properties. */ 317 void *addr = ((void *) cur) + sizeof(heap_block_head_t); 318 void *aligned = (void *) ALIGN_UP(addr, falign); 422 319 423 320 if (addr == aligned) { 424 321 /* Exact block start including alignment. */ 425 322 split_mark(cur, real_size); 426 427 next = cur; 428 return addr; 323 result = addr; 429 324 } else { 430 325 /* Block start has to be aligned */ … … 432 327 433 328 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)); 329 /* The current block is large enough to fit 330 data in including alignment */ 331 if ((void *) cur > heap_start) { 332 /* There is a block before the current block. 333 This previous block can be enlarged to compensate 334 for the alignment excess */ 335 heap_block_foot_t *prev_foot = 336 ((void *) cur) - sizeof(heap_block_foot_t); 446 337 447 heap_block_head_t *prev_head = (heap_block_head_t *)448 ( (void *) cur- prev_foot->size);338 heap_block_head_t *prev_head = 339 (heap_block_head_t *) (((void *) cur) - prev_foot->size); 449 340 450 341 block_check(prev_head); … … 453 344 heap_block_head_t *next_head = ((void *) cur) + excess; 454 345 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); 346 if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) { 347 /* The previous block is not free and there is enough 348 space to fill in a new free block between the previous 349 and current block */ 350 block_init(cur, excess, true); 464 351 } 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); 352 /* The previous block is free (thus there is no need to 353 induce additional fragmentation to the heap) or the 354 excess is small, thus just enlarge the previous block */ 355 block_init(prev_head, prev_head->size + excess, prev_head->free); 474 356 } 475 357 476 block_init(next_head, reduced_size, true , area);358 block_init(next_head, reduced_size, true); 477 359 split_mark(next_head, real_size); 478 479 next = next_head; 480 return aligned; 360 result = aligned; 361 cur = next_head; 481 362 } 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 */ 363 /* The current block is the first block on the heap. 364 We have to make sure that the alignment excess 365 is large enough to fit a new free block just 366 before the current block */ 489 367 while (excess < STRUCT_OVERHEAD) { 490 368 aligned += falign; … … 495 373 if (cur->size >= real_size + excess) { 496 374 size_t reduced_size = cur->size - excess; 497 cur = (heap_block_head_t *) 498 (AREA_FIRST_BLOCK(area) + excess); 375 cur = (heap_block_head_t *) (heap_start + excess); 499 376 500 block_init((void *) AREA_FIRST_BLOCK(area), excess, 501 true, area); 502 block_init(cur, reduced_size, true, area); 377 block_init(heap_start, excess, true); 378 block_init(cur, reduced_size, true); 503 379 split_mark(cur, real_size); 504 505 next = cur; 506 return aligned; 380 result = aligned; 507 381 } 508 382 } … … 510 384 } 511 385 } 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; 386 387 /* Advance to the next block. */ 388 cur = (heap_block_head_t *) (((void *) cur) + cur->size); 389 } 390 391 if ((result == NULL) && (!grown)) { 392 if (grow_heap(real_size)) { 393 grown = true; 570 394 goto loop; 571 395 } 572 396 } 573 397 574 return NULL;398 return result; 575 399 } 576 400 … … 651 475 (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 652 476 477 assert((void *) head >= heap_start); 478 assert((void *) head < heap_end); 479 653 480 block_check(head); 654 481 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 482 662 483 void *ptr = NULL; … … 668 489 /* Shrink */ 669 490 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); 491 /* Split the original block to a full block 492 and a trailing free block */ 493 block_init((void *) head, real_size, false); 675 494 block_init((void *) head + real_size, 676 orig_size - real_size, true , area);677 heap_shrink();495 orig_size - real_size, true); 496 shrink_heap(); 678 497 } 679 498 680 499 ptr = ((void *) head) + sizeof(heap_block_head_t); 681 500 } 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 */ 501 /* Look at the next block. If it is free and the size is 502 sufficient then merge the two. Otherwise just allocate 503 a new block, copy the original data into it and 504 free the original block. */ 688 505 heap_block_head_t *next_head = 689 506 (heap_block_head_t *) (((void *) head) + head->size); 690 507 691 if (((void *) next_head < area->end) &&508 if (((void *) next_head < heap_end) && 692 509 (head->size + next_head->size >= real_size) && 693 510 (next_head->free)) { 694 511 block_check(next_head); 695 block_init(head, head->size + next_head->size, false , area);512 block_init(head, head->size + next_head->size, false); 696 513 split_mark(head, real_size); 697 514 698 515 ptr = ((void *) head) + sizeof(heap_block_head_t); 699 next = NULL;700 516 } else 701 517 reloc = true; … … 728 544 = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 729 545 546 assert((void *) head >= heap_start); 547 assert((void *) head < heap_end); 548 730 549 block_check(head); 731 550 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 551 739 552 /* Mark the block itself as free. */ … … 744 557 = (heap_block_head_t *) (((void *) head) + head->size); 745 558 746 if ((void *) next_head < area->end) {559 if ((void *) next_head < heap_end) { 747 560 block_check(next_head); 748 561 if (next_head->free) 749 block_init(head, head->size + next_head->size, true , area);562 block_init(head, head->size + next_head->size, true); 750 563 } 751 564 752 565 /* Look at the previous block. If it is free, merge the two. */ 753 if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) {566 if ((void *) head > heap_start) { 754 567 heap_block_foot_t *prev_foot = 755 568 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 761 574 762 575 if (prev_head->free) 763 block_init(prev_head, prev_head->size + head->size, true, 764 area); 765 } 766 767 heap_shrink(); 576 block_init(prev_head, prev_head->size + head->size, true); 577 } 578 579 shrink_heap(); 768 580 769 581 futex_up(&malloc_futex);
Note:
See TracChangeset
for help on using the changeset viewer.
