Changes in uspace/lib/c/generic/malloc.c [47b7006:d161715] 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 rd161715 44 44 #include <mem.h> 45 45 #include <futex.h> 46 #include <stdlib.h> 46 47 #include <adt/gcdlcm.h> 47 48 #include "private/malloc.h" 48 49 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) */ 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 */ 57 65 #define BASE_ALIGN 16 58 66 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) 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 * 71 75 */ 72 76 #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) 73 77 74 /** 75 * Calculate net size of a heap block (without header and footer) 78 /** Calculate net size of a heap block. 79 * 80 * Subtract header and footer size. 81 * 76 82 */ 77 83 #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 into 101 * multiple discontinuous heaps. Each heap is represented 102 * by a separate address space area which has this structure 103 * 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; 78 123 79 124 /** Header of a heap block … … 87 132 bool free; 88 133 134 /** Heap area this block belongs to */ 135 heap_area_t *area; 136 89 137 /* A magic value to detect overwrite of heap header */ 90 138 uint32_t magic; … … 102 150 } heap_block_foot_t; 103 151 104 /** Linker heap symbol */ 105 extern char _heap; 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; 106 160 107 161 /** Futex for thread-safe heap manipulation */ 108 162 static futex_t malloc_futex = FUTEX_INITIALIZER; 109 163 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 164 /** Initialize a heap block 123 165 * 124 * Fill sin the structures related to a heap block.166 * Fill in the structures related to a heap block. 125 167 * Should be called only inside the critical section. 126 168 * … … 128 170 * @param size Size of the block including the header and the footer. 129 171 * @param free Indication of a free block. 130 * 131 */ 132 static void block_init(void *addr, size_t size, bool free) 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) 133 176 { 134 177 /* Calculate the position of the header and the footer */ 135 178 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 179 139 180 head->size = size; 140 181 head->free = free; 182 head->area = area; 141 183 head->magic = HEAP_BLOCK_HEAD_MAGIC; 184 185 heap_block_foot_t *foot = BLOCK_FOOT(head); 142 186 143 187 foot->size = size; … … 160 204 assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); 161 205 162 heap_block_foot_t *foot = 163 (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); 206 heap_block_foot_t *foot = BLOCK_FOOT(head); 164 207 165 208 assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); … … 167 210 } 168 211 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) 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) 237 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) 245 return false; 246 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) 177 278 { 178 279 if (size == 0) 280 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) 179 293 return false; 180 181 if ((heap_start + size < heap_start) || (heap_end + size < heap_end)) 294 295 /* Resize the address space area */ 296 int ret = as_area_resize(area->start, asize, 0); 297 if (ret != EOK) 182 298 return false; 183 299 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; 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) 198 317 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 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; 214 338 } 215 339 … … 223 347 void __malloc_init(void) 224 348 { 225 if (!as_area_create((void *) &_heap, PAGE_SIZE, 226 AS_AREA_WRITE | AS_AREA_READ)) 349 if (!area_create(PAGE_SIZE)) 227 350 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 351 } 255 352 … … 273 370 /* Block big enough -> split. */ 274 371 void *next = ((void *) cur) + size; 275 block_init(next, cur->size - size, true );276 block_init(cur, size, false );372 block_init(next, cur->size - size, true, cur->area); 373 block_init(cur, size, false, cur->area); 277 374 } else { 278 375 /* Block too small -> use as is. */ … … 281 378 } 282 379 283 /** Allocate a memoryblock380 /** Allocate memory from heap area starting from given block 284 381 * 285 382 * 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)) {383 * As a side effect this function also sets the current 384 * 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 search 389 * (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)) { 309 406 block_check(cur); 407 408 /* Finish searching on the final block */ 409 if ((final_block != NULL) && (cur == final_block)) 410 break; 310 411 311 412 /* Try to find a block that is free and large enough. */ 312 413 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); 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); 317 422 318 423 if (addr == aligned) { 319 424 /* Exact block start including alignment. */ 320 425 split_mark(cur, real_size); 321 result = addr; 426 427 next = cur; 428 return addr; 322 429 } else { 323 430 /* Block start has to be aligned */ … … 325 432 326 433 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); 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)); 335 446 336 heap_block_head_t *prev_head = 337 ( heap_block_head_t *) (((void *) cur)- prev_foot->size);447 heap_block_head_t *prev_head = (heap_block_head_t *) 448 ((void *) cur - prev_foot->size); 338 449 339 450 block_check(prev_head); … … 342 453 heap_block_head_t *next_head = ((void *) cur) + excess; 343 454 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); 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); 349 464 } 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); 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); 354 474 } 355 475 356 block_init(next_head, reduced_size, true );476 block_init(next_head, reduced_size, true, area); 357 477 split_mark(next_head, real_size); 358 result = aligned; 359 cur = next_head; 478 479 next = next_head; 480 return aligned; 360 481 } 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 */ 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 */ 365 489 while (excess < STRUCT_OVERHEAD) { 366 490 aligned += falign; … … 371 495 if (cur->size >= real_size + excess) { 372 496 size_t reduced_size = cur->size - excess; 373 cur = (heap_block_head_t *) (heap_start + excess); 497 cur = (heap_block_head_t *) 498 (AREA_FIRST_BLOCK(area) + excess); 374 499 375 block_init(heap_start, excess, true); 376 block_init(cur, reduced_size, true); 500 block_init((void *) AREA_FIRST_BLOCK(area), excess, 501 true, area); 502 block_init(cur, reduced_size, true, area); 377 503 split_mark(cur, real_size); 378 result = aligned; 504 505 next = cur; 506 return aligned; 379 507 } 380 508 } … … 382 510 } 383 511 } 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; 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; 392 570 goto loop; 393 571 } 394 572 } 395 573 396 return result;574 return NULL; 397 575 } 398 576 … … 473 651 (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 474 652 475 assert((void *) head >= heap_start);476 assert((void *) head < heap_end);477 478 653 block_check(head); 479 654 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); 480 661 481 662 void *ptr = NULL; … … 487 668 /* Shrink */ 488 669 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); 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); 492 675 block_init((void *) head + real_size, 493 orig_size - real_size, true );494 shrink_heap();676 orig_size - real_size, true, area); 677 heap_shrink(); 495 678 } 496 679 497 680 ptr = ((void *) head) + sizeof(heap_block_head_t); 498 681 } 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. */ 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 */ 503 688 heap_block_head_t *next_head = 504 689 (heap_block_head_t *) (((void *) head) + head->size); 505 690 506 if (((void *) next_head < heap_end) &&691 if (((void *) next_head < area->end) && 507 692 (head->size + next_head->size >= real_size) && 508 693 (next_head->free)) { 509 694 block_check(next_head); 510 block_init(head, head->size + next_head->size, false );695 block_init(head, head->size + next_head->size, false, area); 511 696 split_mark(head, real_size); 512 697 513 698 ptr = ((void *) head) + sizeof(heap_block_head_t); 699 next = NULL; 514 700 } else 515 701 reloc = true; … … 542 728 = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); 543 729 544 assert((void *) head >= heap_start);545 assert((void *) head < heap_end);546 547 730 block_check(head); 548 731 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); 549 738 550 739 /* Mark the block itself as free. */ … … 555 744 = (heap_block_head_t *) (((void *) head) + head->size); 556 745 557 if ((void *) next_head < heap_end) {746 if ((void *) next_head < area->end) { 558 747 block_check(next_head); 559 748 if (next_head->free) 560 block_init(head, head->size + next_head->size, true );749 block_init(head, head->size + next_head->size, true, area); 561 750 } 562 751 563 752 /* Look at the previous block. If it is free, merge the two. */ 564 if ((void *) head > heap_start) {753 if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) { 565 754 heap_block_foot_t *prev_foot = 566 755 (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); … … 572 761 573 762 if (prev_head->free) 574 block_init(prev_head, prev_head->size + head->size, true); 575 } 576 577 shrink_heap(); 763 block_init(prev_head, prev_head->size + head->size, true, 764 area); 765 } 766 767 heap_shrink(); 578 768 579 769 futex_up(&malloc_futex);
Note:
See TracChangeset
for help on using the changeset viewer.
