Changeset 3a0a4d8 in mainline for kernel/generic/src/mm/frame.c
- Timestamp:
- 2013-09-12T07:54:05Z (11 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 95027b5
- Parents:
- 47f5a77 (diff), 64f3d3b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - File:
-
- 1 edited
-
kernel/generic/src/mm/frame.c (modified) (52 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/mm/frame.c
r47f5a77 r3a0a4d8 38 38 * 39 39 * This file contains the physical frame allocator and memory zone management. 40 * The frame allocator is built on top of the buddy allocator. 41 * 42 * @see buddy.c 40 * The frame allocator is built on top of the two-level bitmap structure. 41 * 43 42 */ 44 43 … … 62 61 #include <str.h> 63 62 63 #define BITMAP_BLOCK_SIZE 128 64 64 65 zones_t zones; 65 66 … … 92 93 } 93 94 94 NO_TRACE static inline size_t make_frame_index(zone_t *zone, frame_t *frame)95 {96 return (frame - zone->frames);97 }98 99 95 /** Initialize frame structure. 100 96 * … … 104 100 NO_TRACE static void frame_initialize(frame_t *frame) 105 101 { 106 frame->refcount = 1;107 frame-> buddy_order = 0;102 frame->refcount = 0; 103 frame->parent = NULL; 108 104 } 109 105 … … 161 157 162 158 /* Move other zones up */ 163 size_t j; 164 for (j = zones.count; j > i; j--) { 159 for (size_t j = zones.count; j > i; j--) 165 160 zones.info[j] = zones.info[j - 1]; 166 if (zones.info[j].buddy_system != NULL)167 zones.info[j].buddy_system->data =168 (void *) &zones.info[j];169 }170 161 171 162 zones.count++; … … 237 228 } 238 229 239 /** @return True if zone can allocate specified order */ 240 NO_TRACE static bool zone_can_alloc(zone_t *zone, uint8_t order) 241 { 230 /** @return True if zone can allocate specified number of frames */ 231 NO_TRACE static bool zone_can_alloc(zone_t *zone, size_t count, 232 pfn_t constraint) 233 { 234 /* 235 * The function bitmap_allocate_range() does not modify 236 * the bitmap if the last argument is NULL. 237 */ 242 238 return ((zone->flags & ZONE_AVAILABLE) && 243 buddy_system_can_alloc(zone->buddy_system, order)); 244 } 245 246 /** Find a zone that can allocate order frames. 239 bitmap_allocate_range(&zone->bitmap, count, zone->base, 240 constraint, NULL)); 241 } 242 243 /** Find a zone that can allocate specified number of frames 247 244 * 248 245 * Assume interrupts are disabled and zones lock is 249 246 * locked. 250 247 * 251 * @param order Size (2^order) of free space we are trying to find. 252 * @param flags Required flags of the target zone. 253 * @param hind Preferred zone. 254 * 255 */ 256 NO_TRACE static size_t find_free_zone(uint8_t order, zone_flags_t flags, 257 size_t hint) 248 * @param count Number of free frames we are trying to find. 249 * @param flags Required flags of the target zone. 250 * @param constraint Indication of bits that cannot be set in the 251 * physical frame number of the first allocated frame. 252 * @param hind Preferred zone. 253 * 254 */ 255 NO_TRACE static size_t find_free_zone(size_t count, zone_flags_t flags, 256 pfn_t constraint, size_t hint) 258 257 { 259 258 if (hint >= zones.count) … … 267 266 if (ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) { 268 267 /* 269 * Check if the zone has 2^order frames area available.268 * Check if the zone can satisfy the allocation request. 270 269 */ 271 if (zone_can_alloc(&zones.info[i], order))270 if (zone_can_alloc(&zones.info[i], count, constraint)) 272 271 return i; 273 272 } … … 282 281 } 283 282 284 /**************************/285 /* Buddy system functions */286 /**************************/287 288 /** Buddy system find_block implementation.289 *290 * Find block that is parent of current list.291 * That means go to lower addresses, until such block is found292 *293 * @param order Order of parent must be different then this294 * parameter!!295 *296 */297 NO_TRACE static link_t *zone_buddy_find_block(buddy_system_t *buddy,298 link_t *child, uint8_t order)299 {300 frame_t *frame = list_get_instance(child, frame_t, buddy_link);301 zone_t *zone = (zone_t *) buddy->data;302 303 size_t index = frame_index(zone, frame);304 do {305 if (zone->frames[index].buddy_order != order)306 return &zone->frames[index].buddy_link;307 } while (index-- > 0);308 309 return NULL;310 }311 312 /** Buddy system find_buddy implementation.313 *314 * @param buddy Buddy system.315 * @param block Block for which buddy should be found.316 *317 * @return Buddy for given block if found.318 *319 */320 NO_TRACE static link_t *zone_buddy_find_buddy(buddy_system_t *buddy,321 link_t *block)322 {323 frame_t *frame = list_get_instance(block, frame_t, buddy_link);324 zone_t *zone = (zone_t *) buddy->data;325 ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),326 frame->buddy_order));327 328 bool is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);329 330 size_t index;331 if (is_left) {332 index = (frame_index(zone, frame)) +333 (1 << frame->buddy_order);334 } else { /* is_right */335 index = (frame_index(zone, frame)) -336 (1 << frame->buddy_order);337 }338 339 if (frame_index_valid(zone, index)) {340 if ((zone->frames[index].buddy_order == frame->buddy_order) &&341 (zone->frames[index].refcount == 0)) {342 return &zone->frames[index].buddy_link;343 }344 }345 346 return NULL;347 }348 349 /** Buddy system bisect implementation.350 *351 * @param buddy Buddy system.352 * @param block Block to bisect.353 *354 * @return Right block.355 *356 */357 NO_TRACE static link_t *zone_buddy_bisect(buddy_system_t *buddy, link_t *block)358 {359 frame_t *frame_l = list_get_instance(block, frame_t, buddy_link);360 frame_t *frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));361 362 return &frame_r->buddy_link;363 }364 365 /** Buddy system coalesce implementation.366 *367 * @param buddy Buddy system.368 * @param block_1 First block.369 * @param block_2 First block's buddy.370 *371 * @return Coalesced block (actually block that represents lower372 * address).373 *374 */375 NO_TRACE static link_t *zone_buddy_coalesce(buddy_system_t *buddy,376 link_t *block_1, link_t *block_2)377 {378 frame_t *frame1 = list_get_instance(block_1, frame_t, buddy_link);379 frame_t *frame2 = list_get_instance(block_2, frame_t, buddy_link);380 381 return ((frame1 < frame2) ? block_1 : block_2);382 }383 384 /** Buddy system set_order implementation.385 *386 * @param buddy Buddy system.387 * @param block Buddy system block.388 * @param order Order to set.389 *390 */391 NO_TRACE static void zone_buddy_set_order(buddy_system_t *buddy, link_t *block,392 uint8_t order)393 {394 list_get_instance(block, frame_t, buddy_link)->buddy_order = order;395 }396 397 /** Buddy system get_order implementation.398 *399 * @param buddy Buddy system.400 * @param block Buddy system block.401 *402 * @return Order of block.403 *404 */405 NO_TRACE static uint8_t zone_buddy_get_order(buddy_system_t *buddy,406 link_t *block)407 {408 return list_get_instance(block, frame_t, buddy_link)->buddy_order;409 }410 411 /** Buddy system mark_busy implementation.412 *413 * @param buddy Buddy system.414 * @param block Buddy system block.415 *416 */417 NO_TRACE static void zone_buddy_mark_busy(buddy_system_t *buddy, link_t *block)418 {419 list_get_instance(block, frame_t, buddy_link)->refcount = 1;420 }421 422 /** Buddy system mark_available implementation.423 *424 * @param buddy Buddy system.425 * @param block Buddy system block.426 *427 */428 NO_TRACE static void zone_buddy_mark_available(buddy_system_t *buddy,429 link_t *block)430 {431 list_get_instance(block, frame_t, buddy_link)->refcount = 0;432 }433 434 static buddy_system_operations_t zone_buddy_system_operations = {435 .find_buddy = zone_buddy_find_buddy,436 .bisect = zone_buddy_bisect,437 .coalesce = zone_buddy_coalesce,438 .set_order = zone_buddy_set_order,439 .get_order = zone_buddy_get_order,440 .mark_busy = zone_buddy_mark_busy,441 .mark_available = zone_buddy_mark_available,442 .find_block = zone_buddy_find_block443 };444 445 283 /******************/ 446 284 /* Zone functions */ 447 285 /******************/ 448 286 287 /** Return frame from zone. */ 288 NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t index) 289 { 290 ASSERT(index < zone->count); 291 292 return &zone->frames[index]; 293 } 294 449 295 /** Allocate frame in particular zone. 450 296 * … … 452 298 * Panics if allocation is impossible. 453 299 * 454 * @param zone Zone to allocate from. 455 * @param order Allocate exactly 2^order frames. 300 * @param zone Zone to allocate from. 301 * @param count Number of frames to allocate 302 * @param constraint Indication of bits that cannot be set in the 303 * physical frame number of the first allocated frame. 456 304 * 457 305 * @return Frame index in zone. 458 306 * 459 307 */ 460 NO_TRACE static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order) 308 NO_TRACE static size_t zone_frame_alloc(zone_t *zone, size_t count, 309 pfn_t constraint) 461 310 { 462 311 ASSERT(zone->flags & ZONE_AVAILABLE); 463 312 464 /* Allocate frames from zone buddy system */ 465 link_t *link = buddy_system_alloc(zone->buddy_system, order); 466 467 ASSERT(link); 313 /* Allocate frames from zone */ 314 size_t index; 315 int avail = bitmap_allocate_range(&zone->bitmap, count, zone->base, 316 constraint, &index); 317 318 ASSERT(avail); 319 320 /* Update frame reference count */ 321 for (size_t i = 0; i < count; i++) { 322 frame_t *frame = zone_get_frame(zone, index + i); 323 324 ASSERT(frame->refcount == 0); 325 frame->refcount = 1; 326 } 468 327 469 328 /* Update zone information. */ 470 zone->free_count -= (1 << order); 471 zone->busy_count += (1 << order); 472 473 /* Frame will be actually a first frame of the block. */ 474 frame_t *frame = list_get_instance(link, frame_t, buddy_link); 475 476 /* Get frame address */ 477 return make_frame_index(zone, frame); 329 zone->free_count -= count; 330 zone->busy_count += count; 331 332 return index; 478 333 } 479 334 … … 482 337 * Assume zone is locked and is available for deallocation. 483 338 * 484 * @param zone 485 * @param frame_idx Frame index relative to zone.486 * 487 * @return 488 * 489 */ 490 NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t frame_idx)339 * @param zone Pointer to zone from which the frame is to be freed. 340 * @param index Frame index relative to zone. 341 * 342 * @return Number of freed frames. 343 * 344 */ 345 NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t index) 491 346 { 492 347 ASSERT(zone->flags & ZONE_AVAILABLE); 493 348 494 frame_t *frame = &zone->frames[frame_idx]; 495 size_t size = 0; 496 497 ASSERT(frame->refcount); 349 frame_t *frame = zone_get_frame(zone, index); 350 351 ASSERT(frame->refcount > 0); 498 352 499 353 if (!--frame->refcount) { 500 size = 1 << frame->buddy_order;501 buddy_system_free(zone->buddy_system, &frame->buddy_link);354 bitmap_set(&zone->bitmap, index, 0); 355 502 356 /* Update zone information. */ 503 zone->free_count += size; 504 zone->busy_count -= size; 505 } 506 507 return size; 508 } 509 510 /** Return frame from zone. */ 511 NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t frame_idx) 512 { 513 ASSERT(frame_idx < zone->count); 514 return &zone->frames[frame_idx]; 357 zone->free_count++; 358 zone->busy_count--; 359 360 return 1; 361 } 362 363 return 0; 515 364 } 516 365 517 366 /** Mark frame in zone unavailable to allocation. */ 518 NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t frame_idx) 519 { 520 ASSERT(zone->flags & ZONE_AVAILABLE); 521 522 frame_t *frame = zone_get_frame(zone, frame_idx); 523 if (frame->refcount) 367 NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t index) 368 { 369 if (!(zone->flags & ZONE_AVAILABLE)) 524 370 return; 525 371 526 link_t *link __attribute__ ((unused)); 527 528 link = buddy_system_alloc_block(zone->buddy_system, 529 &frame->buddy_link); 530 531 ASSERT(link); 372 frame_t *frame = zone_get_frame(zone, index); 373 if (frame->refcount > 0) 374 return; 375 376 frame->refcount = 1; 377 bitmap_set_range(&zone->bitmap, index, 1); 378 532 379 zone->free_count--; 533 380 reserve_force_alloc(1); … … 536 383 /** Merge two zones. 537 384 * 538 * Expect buddy to point to space at least zone_conf_size large.539 385 * Assume z1 & z2 are locked and compatible and zones lock is 540 386 * locked. 541 387 * 542 * @param z1 First zone to merge.543 * @param z2 Second zone to merge.544 * @param old_z1 Original dateof the first zone.545 * @param buddy Merged zone buddy.388 * @param z1 First zone to merge. 389 * @param z2 Second zone to merge. 390 * @param old_z1 Original data of the first zone. 391 * @param confdata Merged zone configuration data. 546 392 * 547 393 */ 548 394 NO_TRACE static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1, 549 buddy_system_t *buddy)395 void *confdata) 550 396 { 551 397 ASSERT(zones.info[z1].flags & ZONE_AVAILABLE); … … 562 408 zones.info[z1].free_count += zones.info[z2].free_count; 563 409 zones.info[z1].busy_count += zones.info[z2].busy_count; 564 zones.info[z1].buddy_system = buddy; 565 566 uint8_t order = fnzb(zones.info[z1].count); 567 buddy_system_create(zones.info[z1].buddy_system, order, 568 &zone_buddy_system_operations, (void *) &zones.info[z1]); 569 570 zones.info[z1].frames = 571 (frame_t *) ((uint8_t *) zones.info[z1].buddy_system 572 + buddy_conf_size(order)); 573 574 /* This marks all frames busy */ 575 size_t i; 576 for (i = 0; i < zones.info[z1].count; i++) 577 frame_initialize(&zones.info[z1].frames[i]); 578 579 /* Copy frames from both zones to preserve full frame orders, 580 * parents etc. Set all free frames with refcount = 0 to 1, because 581 * we add all free frames to buddy allocator later again, clearing 582 * order to 0. Don't set busy frames with refcount = 0, as they 583 * will not be reallocated during merge and it would make later 584 * problems with allocation/free. 410 411 bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count, 412 BITMAP_BLOCK_SIZE, confdata + 413 (sizeof(frame_t) * zones.info[z1].count)); 414 bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count); 415 416 zones.info[z1].frames = (frame_t *) confdata; 417 418 /* 419 * Copy frames and bits from both zones to preserve parents, etc. 585 420 */ 586 for (i = 0; i < old_z1->count; i++) 421 422 for (size_t i = 0; i < old_z1->count; i++) { 423 bitmap_set(&zones.info[z1].bitmap, i, 424 bitmap_get(&old_z1->bitmap, i)); 587 425 zones.info[z1].frames[i] = old_z1->frames[i]; 588 589 for (i = 0; i < zones.info[z2].count; i++) 590 zones.info[z1].frames[base_diff + i] 591 = zones.info[z2].frames[i]; 592 593 i = 0; 594 while (i < zones.info[z1].count) { 595 if (zones.info[z1].frames[i].refcount) { 596 /* Skip busy frames */ 597 i += 1 << zones.info[z1].frames[i].buddy_order; 598 } else { 599 /* Free frames, set refcount = 1 600 * (all free frames have refcount == 0, we need not 601 * to check the order) 602 */ 603 zones.info[z1].frames[i].refcount = 1; 604 zones.info[z1].frames[i].buddy_order = 0; 605 i++; 606 } 607 } 608 609 /* Add free blocks from the original zone z1 */ 610 while (zone_can_alloc(old_z1, 0)) { 611 /* Allocate from the original zone */ 612 pfn_t frame_idx = zone_frame_alloc(old_z1, 0); 613 614 /* Free the frame from the merged zone */ 615 frame_t *frame = &zones.info[z1].frames[frame_idx]; 616 frame->refcount = 0; 617 buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link); 618 } 619 620 /* Add free blocks from the original zone z2 */ 621 while (zone_can_alloc(&zones.info[z2], 0)) { 622 /* Allocate from the original zone */ 623 pfn_t frame_idx = zone_frame_alloc(&zones.info[z2], 0); 624 625 /* Free the frame from the merged zone */ 626 frame_t *frame = &zones.info[z1].frames[base_diff + frame_idx]; 627 frame->refcount = 0; 628 buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link); 426 } 427 428 for (size_t i = 0; i < zones.info[z2].count; i++) { 429 bitmap_set(&zones.info[z1].bitmap, base_diff + i, 430 bitmap_get(&zones.info[z2].bitmap, i)); 431 zones.info[z1].frames[base_diff + i] = 432 zones.info[z2].frames[i]; 629 433 } 630 434 } … … 649 453 size_t cframes = SIZE2FRAMES(zone_conf_size(count)); 650 454 651 if ((pfn < zones.info[znum].base) 652 ||(pfn >= zones.info[znum].base + zones.info[znum].count))455 if ((pfn < zones.info[znum].base) || 456 (pfn >= zones.info[znum].base + zones.info[znum].count)) 653 457 return; 654 458 655 frame_t *frame __attribute__ ((unused)); 656 657 frame = &zones.info[znum].frames[pfn - zones.info[znum].base]; 658 ASSERT(!frame->buddy_order); 659 660 size_t i; 661 for (i = 0; i < cframes; i++) { 662 zones.info[znum].busy_count++; 459 for (size_t i = 0; i < cframes; i++) 663 460 (void) zone_frame_free(&zones.info[znum], 664 461 pfn - zones.info[znum].base + i); 665 }666 }667 668 /** Reduce allocated block to count of order 0 frames.669 *670 * The allocated block needs 2^order frames. Reduce all frames671 * in the block to order 0 and free the unneeded frames. This means that672 * when freeing the previously allocated block starting with frame_idx,673 * you have to free every frame.674 *675 * @param znum Zone.676 * @param frame_idx Index the first frame of the block.677 * @param count Allocated frames in block.678 *679 */680 NO_TRACE static void zone_reduce_region(size_t znum, pfn_t frame_idx,681 size_t count)682 {683 ASSERT(zones.info[znum].flags & ZONE_AVAILABLE);684 ASSERT(frame_idx + count < zones.info[znum].count);685 686 uint8_t order = zones.info[znum].frames[frame_idx].buddy_order;687 ASSERT((size_t) (1 << order) >= count);688 689 /* Reduce all blocks to order 0 */690 size_t i;691 for (i = 0; i < (size_t) (1 << order); i++) {692 frame_t *frame = &zones.info[znum].frames[i + frame_idx];693 frame->buddy_order = 0;694 if (!frame->refcount)695 frame->refcount = 1;696 ASSERT(frame->refcount == 1);697 }698 699 /* Free unneeded frames */700 for (i = count; i < (size_t) (1 << order); i++)701 (void) zone_frame_free(&zones.info[znum], i + frame_idx);702 462 } 703 463 … … 719 479 bool ret = true; 720 480 721 /* We can join only 2 zones with none existing inbetween, 481 /* 482 * We can join only 2 zones with none existing inbetween, 722 483 * the zones have to be available and with the same 723 484 * set of flags … … 733 494 + zones.info[z2].count)); 734 495 735 uint8_t order;736 if (cframes == 1)737 order = 0;738 else739 order = fnzb(cframes - 1) + 1;740 741 496 /* Allocate merged zone data inside one of the zones */ 742 497 pfn_t pfn; 743 if (zone_can_alloc(&zones.info[z1], order)) { 744 pfn = zones.info[z1].base + zone_frame_alloc(&zones.info[z1], order); 745 } else if (zone_can_alloc(&zones.info[z2], order)) { 746 pfn = zones.info[z2].base + zone_frame_alloc(&zones.info[z2], order); 498 if (zone_can_alloc(&zones.info[z1], cframes, 0)) { 499 pfn = zones.info[z1].base + 500 zone_frame_alloc(&zones.info[z1], cframes, 0); 501 } else if (zone_can_alloc(&zones.info[z2], cframes, 0)) { 502 pfn = zones.info[z2].base + 503 zone_frame_alloc(&zones.info[z2], cframes, 0); 747 504 } else { 748 505 ret = false; … … 752 509 /* Preserve original data from z1 */ 753 510 zone_t old_z1 = zones.info[z1]; 754 old_z1.buddy_system->data = (void *) &old_z1;755 511 756 512 /* Do zone merging */ 757 buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(pfn)); 758 zone_merge_internal(z1, z2, &old_z1, buddy); 759 760 /* Free unneeded config frames */ 761 zone_reduce_region(z1, pfn - zones.info[z1].base, cframes); 513 zone_merge_internal(z1, z2, &old_z1, (void *) PA2KA(PFN2ADDR(pfn))); 762 514 763 515 /* Subtract zone information from busy frames */ … … 772 524 773 525 /* Move zones down */ 774 size_t i; 775 for (i = z2 + 1; i < zones.count; i++) { 526 for (size_t i = z2 + 1; i < zones.count; i++) 776 527 zones.info[i - 1] = zones.info[i]; 777 if (zones.info[i - 1].buddy_system != NULL)778 zones.info[i - 1].buddy_system->data =779 (void *) &zones.info[i - 1];780 }781 528 782 529 zones.count--; … … 797 544 void zone_merge_all(void) 798 545 { 799 size_t i = 0; 546 size_t i = 1; 547 800 548 while (i < zones.count) { 801 if (!zone_merge(i , i + 1))549 if (!zone_merge(i - 1, i)) 802 550 i++; 803 551 } … … 806 554 /** Create new frame zone. 807 555 * 808 * @param zone Zone to construct.809 * @param buddy Address of buddy system configuration information.810 * @param start Physical address of the first frame within thezone.811 * @param count Count of frames in zone.812 * @param flags Zone flags.556 * @param zone Zone to construct. 557 * @param start Physical address of the first frame within the zone. 558 * @param count Count of frames in zone. 559 * @param flags Zone flags. 560 * @param confdata Configuration data of the zone. 813 561 * 814 562 * @return Initialized zone. 815 563 * 816 564 */ 817 NO_TRACE static void zone_construct(zone_t *zone, buddy_system_t *buddy,818 pfn_t start, size_t count, zone_flags_t flags)565 NO_TRACE static void zone_construct(zone_t *zone, pfn_t start, size_t count, 566 zone_flags_t flags, void *confdata) 819 567 { 820 568 zone->base = start; … … 823 571 zone->free_count = count; 824 572 zone->busy_count = 0; 825 zone->buddy_system = buddy;826 573 827 574 if (flags & ZONE_AVAILABLE) { 828 575 /* 829 * Compute order for buddy system and initialize 576 * Initialize frame bitmap (located after the array of 577 * frame_t structures in the configuration space). 830 578 */ 831 uint8_t order = fnzb(count);832 b uddy_system_create(zone->buddy_system, order,833 &zone_buddy_system_operations, (void *) zone);834 835 /* Allocate frames _after_ the confframe */836 837 /* Check sizes */838 zone->frames = (frame_t *) ((uint8_t *) zone->buddy_system +839 buddy_conf_size(order));840 841 size_t i;842 for ( i = 0; i < count; i++)579 580 bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE, 581 confdata + (sizeof(frame_t) * count)); 582 bitmap_clear_range(&zone->bitmap, 0, count); 583 584 /* 585 * Initialize the array of frame_t structures. 586 */ 587 588 zone->frames = (frame_t *) confdata; 589 590 for (size_t i = 0; i < count; i++) 843 591 frame_initialize(&zone->frames[i]); 844 845 /* Stuffing frames */ 846 for (i = 0; i < count; i++) { 847 zone->frames[i].refcount = 0; 848 buddy_system_free(zone->buddy_system, &zone->frames[i].buddy_link); 849 } 850 } else 592 } else { 593 bitmap_initialize(&zone->bitmap, 0, 0, NULL); 851 594 zone->frames = NULL; 595 } 852 596 } 853 597 … … 861 605 size_t zone_conf_size(size_t count) 862 606 { 863 return (count * sizeof(frame_t) + buddy_conf_size(fnzb(count))); 607 return (count * sizeof(frame_t) + 608 bitmap_size(count, BITMAP_BLOCK_SIZE)); 864 609 } 865 610 … … 867 612 pfn_t zone_external_conf_alloc(size_t count) 868 613 { 869 size_t size = zone_conf_size(count); 870 size_t order = ispwr2(size) ? fnzb(size) : (fnzb(size) + 1); 871 872 return ADDR2PFN((uintptr_t) frame_alloc(order - FRAME_WIDTH, 873 FRAME_LOWMEM | FRAME_ATOMIC)); 614 size_t frames = SIZE2FRAMES(zone_conf_size(count)); 615 616 return ADDR2PFN((uintptr_t) 617 frame_alloc(frames, FRAME_LOWMEM | FRAME_ATOMIC, 0)); 874 618 } 875 619 … … 879 623 * @param count Size of zone in frames. 880 624 * @param confframe Where configuration frames are supposed to be. 881 * Automatically checks ,that we will not disturb the625 * Automatically checks that we will not disturb the 882 626 * kernel and possibly init. If confframe is given 883 627 * _outside_ this zone, it is expected, that the area is … … 896 640 897 641 if (flags & ZONE_AVAILABLE) { /* Create available zone */ 898 /* Theoretically we could have NULL here, practically make sure 642 /* 643 * Theoretically we could have NULL here, practically make sure 899 644 * nobody tries to do that. If some platform requires, remove 900 645 * the assert 901 646 */ 902 647 ASSERT(confframe != ADDR2PFN((uintptr_t ) NULL)); 903 648 904 649 /* Update the known end of physical memory. */ 905 650 config.physmem_end = max(config.physmem_end, PFN2ADDR(start + count)); 906 651 907 /* If confframe is supposed to be inside our zone, then make sure 652 /* 653 * If confframe is supposed to be inside our zone, then make sure 908 654 * it does not span kernel & init 909 655 */ 910 656 size_t confcount = SIZE2FRAMES(zone_conf_size(count)); 657 911 658 if ((confframe >= start) && (confframe < start + count)) { 912 659 for (; confframe < start + count; confframe++) { … … 921 668 922 669 bool overlap = false; 923 size_t i; 924 for (i = 0; i < init.cnt; i++) 670 for (size_t i = 0; i < init.cnt; i++) { 925 671 if (overlaps(addr, PFN2ADDR(confcount), 926 672 init.tasks[i].paddr, … … 929 675 break; 930 676 } 677 } 678 931 679 if (overlap) 932 680 continue; … … 945 693 } 946 694 947 buddy_system_t *buddy = (buddy_system_t*) PA2KA(PFN2ADDR(confframe));948 zone_construct(&zones.info[znum], buddy, start, count, flags);695 void *confdata = (void *) PA2KA(PFN2ADDR(confframe)); 696 zone_construct(&zones.info[znum], start, count, flags, confdata); 949 697 950 698 /* If confdata in zone, mark as unavailable */ 951 699 if ((confframe >= start) && (confframe < start + count)) { 952 size_t i; 953 for (i = confframe; i < confframe + confcount; i++) 700 for (size_t i = confframe; i < confframe + confcount; i++) 954 701 zone_mark_unavailable(&zones.info[znum], 955 702 i - zones.info[znum].base); … … 967 714 return (size_t) -1; 968 715 } 969 zone_construct(&zones.info[znum], NULL, start, count, flags); 716 717 zone_construct(&zones.info[znum], start, count, flags, NULL); 970 718 971 719 irq_spinlock_unlock(&zones.lock, true); … … 1009 757 } 1010 758 1011 /** Allocate power-of-two frames of physical memory. 1012 * 1013 * @param order Allocate exactly 2^order frames. 1014 * @param flags Flags for host zone selection and address processing. 1015 * @param pzone Preferred zone. 759 /** Allocate frames of physical memory. 760 * 761 * @param count Number of continuous frames to allocate. 762 * @param flags Flags for host zone selection and address processing. 763 * @param constraint Indication of physical address bits that cannot be 764 * set in the address of the first allocated frame. 765 * @param pzone Preferred zone. 1016 766 * 1017 767 * @return Physical address of the allocated frame. 1018 768 * 1019 769 */ 1020 void *frame_alloc_generic(uint8_t order, frame_flags_t flags, size_t *pzone) 1021 { 1022 size_t size = ((size_t) 1) << order; 770 uintptr_t frame_alloc_generic(size_t count, frame_flags_t flags, 771 uintptr_t constraint, size_t *pzone) 772 { 773 ASSERT(count > 0); 774 1023 775 size_t hint = pzone ? (*pzone) : 0; 776 pfn_t frame_constraint = ADDR2PFN(constraint); 1024 777 1025 778 /* 1026 779 * If not told otherwise, we must first reserve the memory. 1027 780 */ 1028 if (!(flags & FRAME_NO_RESERVE)) 1029 reserve_force_alloc( size);1030 781 if (!(flags & FRAME_NO_RESERVE)) 782 reserve_force_alloc(count); 783 1031 784 loop: 1032 785 irq_spinlock_lock(&zones.lock, true); … … 1035 788 * First, find suitable frame zone. 1036 789 */ 1037 size_t znum = find_free_zone(order, 1038 FRAME_TO_ZONE_FLAGS(flags), hint); 1039 1040 /* If no memory, reclaim some slab memory, 1041 if it does not help, reclaim all */ 790 size_t znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags), 791 frame_constraint, hint); 792 793 /* 794 * If no memory, reclaim some slab memory, 795 * if it does not help, reclaim all. 796 */ 1042 797 if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) { 1043 798 irq_spinlock_unlock(&zones.lock, true); … … 1046 801 1047 802 if (freed > 0) 1048 znum = find_free_zone( order,1049 FRAME_TO_ZONE_FLAGS(flags), hint);803 znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags), 804 frame_constraint, hint); 1050 805 1051 806 if (znum == (size_t) -1) { … … 1055 810 1056 811 if (freed > 0) 1057 znum = find_free_zone( order,1058 FRAME_TO_ZONE_FLAGS(flags), hint);812 znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags), 813 frame_constraint, hint); 1059 814 } 1060 815 } … … 1063 818 if (flags & FRAME_ATOMIC) { 1064 819 irq_spinlock_unlock(&zones.lock, true); 820 1065 821 if (!(flags & FRAME_NO_RESERVE)) 1066 reserve_free(size); 1067 return NULL; 822 reserve_free(count); 823 824 return 0; 1068 825 } 1069 826 … … 1075 832 1076 833 if (!THREAD) 1077 panic("Cannot wait for memory to become available."); 834 panic("Cannot wait for %zu frames to become available " 835 "(%zu available).", count, avail); 1078 836 1079 837 /* … … 1082 840 1083 841 #ifdef CONFIG_DEBUG 1084 printf("Thread %" PRIu64 " waiting for %zu frames ,"1085 " %zu available.\n", THREAD->tid, size, avail);842 printf("Thread %" PRIu64 " waiting for %zu frames " 843 "(%zu available).\n", THREAD->tid, count, avail); 1086 844 #endif 1087 845 1088 846 /* 1089 * Since the mem_avail_mtx is an active mutex, we need to disable interrupts1090 * to prevent deadlock with TLB shootdown.847 * Since the mem_avail_mtx is an active mutex, we need to 848 * disable interrupts to prevent deadlock with TLB shootdown. 1091 849 */ 1092 850 ipl_t ipl = interrupts_disable(); … … 1094 852 1095 853 if (mem_avail_req > 0) 1096 mem_avail_req = min(mem_avail_req, size);854 mem_avail_req = min(mem_avail_req, count); 1097 855 else 1098 mem_avail_req = size; 856 mem_avail_req = count; 857 1099 858 size_t gen = mem_avail_gen; 1100 859 … … 1112 871 } 1113 872 1114 pfn_t pfn = zone_frame_alloc(&zones.info[znum], order)1115 + zones.info[znum].base;873 pfn_t pfn = zone_frame_alloc(&zones.info[znum], count, 874 frame_constraint) + zones.info[znum].base; 1116 875 1117 876 irq_spinlock_unlock(&zones.lock, true); … … 1120 879 *pzone = znum; 1121 880 1122 if (flags & FRAME_KA)1123 return (void *) PA2KA(PFN2ADDR(pfn)); 1124 1125 return (void *) PFN2ADDR(pfn); 1126 } 1127 1128 void *frame_alloc(uint8_t order, frame_flags_t flags) 1129 { 1130 return frame_alloc_generic(order, flags, NULL); 1131 } 1132 1133 void *frame_alloc_noreserve(uint8_t order, frame_flags_t flags) 1134 { 1135 return frame_alloc_generic(order, flags | FRAME_NO_RESERVE, NULL); 1136 } 1137 1138 /** Free a frame. 1139 * 1140 * Find respective frame structure for supplied physical frame address.1141 * Decrement frame reference count. If it drops to zero, move the frame1142 * structure to free list.1143 * 1144 * @param frame Physical Address of of the frame to be freed.881 return PFN2ADDR(pfn); 882 } 883 884 uintptr_t frame_alloc(size_t count, frame_flags_t flags, uintptr_t constraint) 885 { 886 return frame_alloc_generic(count, flags, constraint, NULL); 887 } 888 889 uintptr_t frame_alloc_noreserve(size_t count, frame_flags_t flags, 890 uintptr_t constraint) 891 { 892 return frame_alloc_generic(count, flags | FRAME_NO_RESERVE, constraint, 893 NULL); 894 } 895 896 /** Free frames of physical memory. 897 * 898 * Find respective frame structures for supplied physical frames. 899 * Decrement each frame reference count. If it drops to zero, mark 900 * the frames as available. 901 * 902 * @param start Physical Address of the first frame to be freed. 903 * @param count Number of frames to free. 1145 904 * @param flags Flags to control memory reservation. 1146 905 * 1147 906 */ 1148 void frame_free_generic(uintptr_t frame, frame_flags_t flags)1149 { 1150 size_t size;907 void frame_free_generic(uintptr_t start, size_t count, frame_flags_t flags) 908 { 909 size_t freed = 0; 1151 910 1152 911 irq_spinlock_lock(&zones.lock, true); 1153 912 1154 /* 1155 * First, find host frame zone for addr. 1156 */ 1157 pfn_t pfn = ADDR2PFN(frame); 1158 size_t znum = find_zone(pfn, 1, 0); 1159 1160 ASSERT(znum != (size_t) -1); 1161 1162 size = zone_frame_free(&zones.info[znum], pfn - zones.info[znum].base); 913 for (size_t i = 0; i < count; i++) { 914 /* 915 * First, find host frame zone for addr. 916 */ 917 pfn_t pfn = ADDR2PFN(start) + i; 918 size_t znum = find_zone(pfn, 1, 0); 919 920 ASSERT(znum != (size_t) -1); 921 922 freed += zone_frame_free(&zones.info[znum], 923 pfn - zones.info[znum].base); 924 } 1163 925 1164 926 irq_spinlock_unlock(&zones.lock, true); … … 1166 928 /* 1167 929 * Signal that some memory has been freed. 930 * Since the mem_avail_mtx is an active mutex, 931 * we need to disable interruptsto prevent deadlock 932 * with TLB shootdown. 1168 933 */ 1169 1170 1171 /* 1172 * Since the mem_avail_mtx is an active mutex, we need to disable interrupts 1173 * to prevent deadlock with TLB shootdown. 1174 */ 934 1175 935 ipl_t ipl = interrupts_disable(); 1176 936 mutex_lock(&mem_avail_mtx); 937 1177 938 if (mem_avail_req > 0) 1178 mem_avail_req -= min(mem_avail_req, size);939 mem_avail_req -= min(mem_avail_req, freed); 1179 940 1180 941 if (mem_avail_req == 0) { … … 1182 943 condvar_broadcast(&mem_avail_cv); 1183 944 } 945 1184 946 mutex_unlock(&mem_avail_mtx); 1185 947 interrupts_restore(ipl); 1186 948 1187 949 if (!(flags & FRAME_NO_RESERVE)) 1188 reserve_free( size);1189 } 1190 1191 void frame_free(uintptr_t frame )1192 { 1193 frame_free_generic(frame, 0);1194 } 1195 1196 void frame_free_noreserve(uintptr_t frame )1197 { 1198 frame_free_generic(frame, FRAME_NO_RESERVE);950 reserve_free(freed); 951 } 952 953 void frame_free(uintptr_t frame, size_t count) 954 { 955 frame_free_generic(frame, count, 0); 956 } 957 958 void frame_free_noreserve(uintptr_t frame, size_t count) 959 { 960 frame_free_generic(frame, count, FRAME_NO_RESERVE); 1199 961 } 1200 962 … … 1230 992 irq_spinlock_lock(&zones.lock, true); 1231 993 1232 size_t i; 1233 for (i = 0; i < count; i++) { 994 for (size_t i = 0; i < count; i++) { 1234 995 size_t znum = find_zone(start + i, 1, 0); 996 1235 997 if (znum == (size_t) -1) /* PFN not found */ 1236 998 continue; … … 1257 1019 /* Tell the architecture to create some memory */ 1258 1020 frame_low_arch_init(); 1021 1259 1022 if (config.cpu_active == 1) { 1260 1023 frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)), … … 1263 1026 SIZE2FRAMES(config.stack_size)); 1264 1027 1265 size_t i; 1266 for (i = 0; i < init.cnt; i++) { 1267 pfn_t pfn = ADDR2PFN(init.tasks[i].paddr); 1268 frame_mark_unavailable(pfn, 1028 for (size_t i = 0; i < init.cnt; i++) 1029 frame_mark_unavailable(ADDR2PFN(init.tasks[i].paddr), 1269 1030 SIZE2FRAMES(init.tasks[i].size)); 1270 }1271 1031 1272 1032 if (ballocs.size) … … 1274 1034 SIZE2FRAMES(ballocs.size)); 1275 1035 1276 /* Black list first frame, as allocating NULL would 1036 /* 1037 * Blacklist first frame, as allocating NULL would 1277 1038 * fail in some places 1278 1039 */ 1279 1040 frame_mark_unavailable(0, 1); 1280 1041 } 1042 1281 1043 frame_high_arch_init(); 1282 1044 } … … 1284 1046 /** Adjust bounds of physical memory region according to low/high memory split. 1285 1047 * 1286 * @param low[in] If true, the adjustment is performed to make the region 1287 * fit in the low memory. Otherwise the adjustment is 1288 * performed to make the region fit in the high memory. 1289 * @param basep[inout] Pointer to a variable which contains the region's base 1290 * address and which may receive the adjusted base address. 1291 * @param sizep[inout] Pointer to a variable which contains the region's size 1292 * and which may receive the adjusted size. 1293 * @retun True if the region still exists even after the 1294 * adjustment, false otherwise. 1048 * @param low[in] If true, the adjustment is performed to make the region 1049 * fit in the low memory. Otherwise the adjustment is 1050 * performed to make the region fit in the high memory. 1051 * @param basep[inout] Pointer to a variable which contains the region's base 1052 * address and which may receive the adjusted base address. 1053 * @param sizep[inout] Pointer to a variable which contains the region's size 1054 * and which may receive the adjusted size. 1055 * 1056 * @return True if the region still exists even after the adjustment. 1057 * @return False otherwise. 1058 * 1295 1059 */ 1296 1060 bool frame_adjust_zone_bounds(bool low, uintptr_t *basep, size_t *sizep) 1297 1061 { 1298 1062 uintptr_t limit = KA2PA(config.identity_base) + config.identity_size; 1299 1063 1300 1064 if (low) { 1301 1065 if (*basep > limit) 1302 1066 return false; 1067 1303 1068 if (*basep + *sizep > limit) 1304 1069 *sizep = limit - *basep; … … 1306 1071 if (*basep + *sizep <= limit) 1307 1072 return false; 1073 1308 1074 if (*basep <= limit) { 1309 1075 *sizep -= limit - *basep; … … 1311 1077 } 1312 1078 } 1079 1313 1080 return true; 1314 1081 } … … 1322 1089 1323 1090 uint64_t total = 0; 1324 size_t i;1325 for ( i = 0; i < zones.count; i++)1091 1092 for (size_t i = 0; i < zones.count; i++) 1326 1093 total += (uint64_t) FRAMES2SIZE(zones.info[i].count); 1327 1094 … … 1346 1113 *free = 0; 1347 1114 1348 size_t i; 1349 for (i = 0; i < zones.count; i++) { 1115 for (size_t i = 0; i < zones.count; i++) { 1350 1116 *total += (uint64_t) FRAMES2SIZE(zones.info[i].count); 1351 1117 … … 1384 1150 */ 1385 1151 1386 size_t i; 1387 for (i = 0;; i++) { 1152 for (size_t i = 0;; i++) { 1388 1153 irq_spinlock_lock(&zones.lock, true); 1389 1154 … … 1438 1203 size_t znum = (size_t) -1; 1439 1204 1440 size_t i; 1441 for (i = 0; i < zones.count; i++) { 1205 for (size_t i = 0; i < zones.count; i++) { 1442 1206 if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) { 1443 1207 znum = i; … … 1452 1216 } 1453 1217 1454 uintptr_t base = PFN2ADDR(zones.info[ i].base);1455 zone_flags_t flags = zones.info[ i].flags;1456 size_t count = zones.info[ i].count;1457 size_t free_count = zones.info[ i].free_count;1458 size_t busy_count = zones.info[ i].busy_count;1218 uintptr_t base = PFN2ADDR(zones.info[znum].base); 1219 zone_flags_t flags = zones.info[znum].flags; 1220 size_t count = zones.info[znum].count; 1221 size_t free_count = zones.info[znum].free_count; 1222 size_t busy_count = zones.info[znum].busy_count; 1459 1223 1460 1224 irq_spinlock_unlock(&zones.lock, true);
Note:
See TracChangeset
for help on using the changeset viewer.
