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