Changes in uspace/lib/ext4/src/extent.c [5a6cc679:a35b458] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/ext4/src/extent.c
r5a6cc679 ra35b458 295 295 ext4_extent_index_t *l; 296 296 ext4_extent_index_t *m; 297 297 298 298 uint16_t entries_count = 299 299 ext4_extent_header_get_entries_count(header); 300 300 301 301 /* Initialize bounds */ 302 302 l = EXT4_EXTENT_FIRST_INDEX(header) + 1; 303 303 r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1; 304 304 305 305 /* Do binary search */ 306 306 while (l <= r) { 307 307 m = l + (r - l) / 2; 308 308 uint32_t first_block = ext4_extent_index_get_first_block(m); 309 309 310 310 if (iblock < first_block) 311 311 r = m - 1; … … 313 313 l = m + 1; 314 314 } 315 315 316 316 /* Set output value */ 317 317 *index = l - 1; … … 332 332 ext4_extent_t *l; 333 333 ext4_extent_t *m; 334 334 335 335 uint16_t entries_count = 336 336 ext4_extent_header_get_entries_count(header); 337 337 338 338 if (entries_count == 0) { 339 339 /* this leaf is empty */ … … 341 341 return; 342 342 } 343 343 344 344 /* Initialize bounds */ 345 345 l = EXT4_EXTENT_FIRST(header) + 1; 346 346 r = EXT4_EXTENT_FIRST(header) + entries_count - 1; 347 347 348 348 /* Do binary search */ 349 349 while (l <= r) { 350 350 m = l + (r - l) / 2; 351 351 uint32_t first_block = ext4_extent_get_first_block(m); 352 352 353 353 if (iblock < first_block) 354 354 r = m - 1; … … 356 356 l = m + 1; 357 357 } 358 358 359 359 /* Set output value */ 360 360 *extent = l - 1; … … 379 379 uint64_t inode_size = 380 380 ext4_inode_get_size(inode_ref->fs->superblock, inode_ref->inode); 381 381 382 382 uint32_t block_size = 383 383 ext4_superblock_get_block_size(inode_ref->fs->superblock); 384 384 385 385 uint32_t last_idx = (inode_size - 1) / block_size; 386 386 387 387 /* Check if requested iblock is not over size of i-node */ 388 388 if (iblock > last_idx) { … … 390 390 return EOK; 391 391 } 392 392 393 393 block_t *block = NULL; 394 394 395 395 /* Walk through extent tree */ 396 396 ext4_extent_header_t *header = 397 397 ext4_inode_get_extent_header(inode_ref->inode); 398 398 399 399 while (ext4_extent_header_get_depth(header) != 0) { 400 400 /* Search index in node */ 401 401 ext4_extent_index_t *index; 402 402 ext4_extent_binsearch_idx(header, &index, iblock); 403 403 404 404 /* Load child node and set values for the next iteration */ 405 405 uint64_t child = ext4_extent_index_get_leaf(index); 406 406 407 407 if (block != NULL) { 408 408 rc = block_put(block); … … 410 410 return rc; 411 411 } 412 412 413 413 rc = block_get(&block, inode_ref->fs->device, child, 414 414 BLOCK_FLAGS_NONE); 415 415 if (rc != EOK) 416 416 return rc; 417 417 418 418 header = (ext4_extent_header_t *)block->data; 419 419 } 420 420 421 421 /* Search extent in the leaf block */ 422 422 ext4_extent_t* extent = NULL; 423 423 ext4_extent_binsearch(header, &extent, iblock); 424 424 425 425 /* Prevent empty leaf */ 426 426 if (extent == NULL) { … … 431 431 uint32_t first = ext4_extent_get_first_block(extent); 432 432 phys_block = ext4_extent_get_start(extent) + iblock - first; 433 433 434 434 *fblock = phys_block; 435 435 } 436 436 437 437 /* Cleanup */ 438 438 if (block != NULL) 439 439 rc = block_put(block); 440 440 441 441 return rc; 442 442 } … … 459 459 ext4_extent_header_t *eh = 460 460 ext4_inode_get_extent_header(inode_ref->inode); 461 461 462 462 uint16_t depth = ext4_extent_header_get_depth(eh); 463 463 464 464 ext4_extent_path_t *tmp_path; 465 465 466 466 /* Added 2 for possible tree growing */ 467 467 tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2)); 468 468 if (tmp_path == NULL) 469 469 return ENOMEM; 470 470 471 471 /* Initialize structure for algorithm start */ 472 472 tmp_path[0].block = inode_ref->block; 473 473 tmp_path[0].header = eh; 474 474 475 475 /* Walk through the extent tree */ 476 476 uint16_t pos = 0; … … 480 480 ext4_extent_binsearch_idx(tmp_path[pos].header, 481 481 &tmp_path[pos].index, iblock); 482 482 483 483 tmp_path[pos].depth = depth; 484 484 tmp_path[pos].extent = NULL; 485 485 486 486 assert(tmp_path[pos].index != NULL); 487 487 488 488 /* Load information for the next iteration */ 489 489 uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index); 490 490 491 491 block_t *block; 492 492 rc = block_get(&block, inode_ref->fs->device, fblock, … … 494 494 if (rc != EOK) 495 495 goto cleanup; 496 496 497 497 pos++; 498 498 499 499 eh = (ext4_extent_header_t *)block->data; 500 500 tmp_path[pos].block = block; 501 501 tmp_path[pos].header = eh; 502 502 } 503 503 504 504 tmp_path[pos].depth = 0; 505 505 tmp_path[pos].extent = NULL; 506 506 tmp_path[pos].index = NULL; 507 507 508 508 /* Find extent in the leaf node */ 509 509 ext4_extent_binsearch(tmp_path[pos].header, &tmp_path[pos].extent, iblock); 510 510 *ret_path = tmp_path; 511 511 512 512 return EOK; 513 513 514 514 cleanup: 515 515 ; … … 528 528 } 529 529 } 530 530 531 531 /* Destroy temporary data structure */ 532 532 free(tmp_path); 533 533 534 534 return rc; 535 535 } … … 549 549 uint64_t start = ext4_extent_get_start(extent); 550 550 uint16_t block_count = ext4_extent_get_block_count(extent); 551 551 552 552 return ext4_balloc_free_blocks(inode_ref, start, block_count); 553 553 } … … 569 569 { 570 570 uint32_t fblock = ext4_extent_index_get_leaf(index); 571 571 572 572 block_t* block; 573 573 errno_t rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE); 574 574 if (rc != EOK) 575 575 return rc; 576 576 577 577 ext4_extent_header_t *header = block->data; 578 578 579 579 if (ext4_extent_header_get_depth(header)) { 580 580 /* The node is non-leaf, do recursion */ 581 581 ext4_extent_index_t *idx = EXT4_EXTENT_FIRST_INDEX(header); 582 582 583 583 /* Release all subbranches */ 584 584 for (uint32_t i = 0; … … 592 592 /* Leaf node reached */ 593 593 ext4_extent_t *ext = EXT4_EXTENT_FIRST(header); 594 594 595 595 /* Release all extents and stop recursion */ 596 596 for (uint32_t i = 0; … … 602 602 } 603 603 } 604 604 605 605 /* Release data block where the node was stored */ 606 606 607 607 rc = block_put(block); 608 608 if (rc != EOK) 609 609 return rc; 610 610 611 611 return ext4_balloc_free_block(inode_ref, fblock); 612 612 } … … 626 626 if (rc != EOK) 627 627 return rc; 628 628 629 629 /* Jump to last item of the path (extent) */ 630 630 ext4_extent_path_t *path_ptr = path; 631 631 while (path_ptr->depth != 0) 632 632 path_ptr++; 633 633 634 634 assert(path_ptr->extent != NULL); 635 635 636 636 /* First extent maybe released partially */ 637 637 uint32_t first_iblock = … … 639 639 uint32_t first_fblock = 640 640 ext4_extent_get_start(path_ptr->extent) + iblock_from - first_iblock; 641 641 642 642 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent); 643 643 644 644 uint16_t delete_count = block_count - 645 645 (ext4_extent_get_start(path_ptr->extent) - first_fblock); 646 646 647 647 /* Release all blocks */ 648 648 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count); 649 649 if (rc != EOK) 650 650 goto cleanup; 651 651 652 652 /* Correct counter */ 653 653 block_count -= delete_count; 654 654 ext4_extent_set_block_count(path_ptr->extent, block_count); 655 655 656 656 /* Initialize the following loop */ 657 657 uint16_t entries = … … 659 659 ext4_extent_t *tmp_ext = path_ptr->extent + 1; 660 660 ext4_extent_t *stop_ext = EXT4_EXTENT_FIRST(path_ptr->header) + entries; 661 661 662 662 /* If first extent empty, release it */ 663 663 if (block_count == 0) 664 664 entries--; 665 665 666 666 /* Release all successors of the first extent in the same node */ 667 667 while (tmp_ext < stop_ext) { 668 668 first_fblock = ext4_extent_get_start(tmp_ext); 669 669 delete_count = ext4_extent_get_block_count(tmp_ext); 670 670 671 671 rc = ext4_balloc_free_blocks(inode_ref, first_fblock, delete_count); 672 672 if (rc != EOK) 673 673 goto cleanup; 674 674 675 675 entries--; 676 676 tmp_ext++; 677 677 } 678 678 679 679 ext4_extent_header_set_entries_count(path_ptr->header, entries); 680 680 path_ptr->block->dirty = true; 681 681 682 682 /* If leaf node is empty, parent entry must be modified */ 683 683 bool remove_parent_record = false; 684 684 685 685 /* Don't release root block (including inode data) !!! */ 686 686 if ((path_ptr != path) && (entries == 0)) { … … 688 688 if (rc != EOK) 689 689 goto cleanup; 690 690 691 691 remove_parent_record = true; 692 692 } 693 693 694 694 /* Jump to the parent */ 695 695 --path_ptr; 696 696 697 697 /* Release all successors in all tree levels */ 698 698 while (path_ptr >= path) { … … 701 701 ext4_extent_index_t *stop = 702 702 EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries; 703 703 704 704 /* Correct entries count because of changes in the previous iteration */ 705 705 if (remove_parent_record) 706 706 entries--; 707 707 708 708 /* Iterate over all entries and release the whole subtrees */ 709 709 while (index < stop) { … … 711 711 if (rc != EOK) 712 712 goto cleanup; 713 713 714 714 ++index; 715 715 --entries; 716 716 } 717 717 718 718 ext4_extent_header_set_entries_count(path_ptr->header, entries); 719 719 path_ptr->block->dirty = true; 720 720 721 721 /* Free the node if it is empty */ 722 722 if ((entries == 0) && (path_ptr != path)) { … … 724 724 if (rc != EOK) 725 725 goto cleanup; 726 726 727 727 /* Mark parent to be checked */ 728 728 remove_parent_record = true; 729 729 } else 730 730 remove_parent_record = false; 731 731 732 732 --path_ptr; 733 733 } 734 734 735 735 cleanup: 736 736 ; … … 749 749 } 750 750 } 751 751 752 752 /* Destroy temporary data structure */ 753 753 free(path); 754 754 755 755 return rc; 756 756 } … … 771 771 { 772 772 ext4_extent_path_t *path_ptr = path + path->depth; 773 773 774 774 uint32_t block_size = 775 775 ext4_superblock_get_block_size(inode_ref->fs->superblock); 776 776 777 777 /* Start splitting */ 778 778 while (path_ptr > path) { … … 781 781 uint16_t limit = 782 782 ext4_extent_header_get_max_entries_count(path_ptr->header); 783 783 784 784 if (entries == limit) { 785 785 /* Full node - allocate block for new one */ … … 788 788 if (rc != EOK) 789 789 return rc; 790 790 791 791 block_t *block; 792 792 rc = block_get(&block, inode_ref->fs->device, fblock, … … 796 796 return rc; 797 797 } 798 798 799 799 /* Put back not modified old block */ 800 800 rc = block_put(path_ptr->block); … … 804 804 return rc; 805 805 } 806 806 807 807 /* Initialize newly allocated block and remember it */ 808 808 memset(block->data, 0, block_size); 809 809 path_ptr->block = block; 810 810 811 811 /* Update pointers in extent path structure */ 812 812 path_ptr->header = block->data; … … 823 823 sizeof(ext4_extent_t); 824 824 } 825 825 826 826 /* Initialize on-disk structure (header) */ 827 827 ext4_extent_header_set_entries_count(path_ptr->header, 1); … … 830 830 ext4_extent_header_set_depth(path_ptr->header, path_ptr->depth); 831 831 ext4_extent_header_set_generation(path_ptr->header, 0); 832 832 833 833 path_ptr->block->dirty = true; 834 834 835 835 /* Jump to the preceeding item */ 836 836 path_ptr--; … … 845 845 ext4_extent_set_first_block(path_ptr->extent, iblock); 846 846 } 847 847 848 848 ext4_extent_header_set_entries_count(path_ptr->header, entries + 1); 849 849 path_ptr->block->dirty = true; 850 850 851 851 /* No more splitting needed */ 852 852 return EOK; 853 853 } 854 854 } 855 855 856 856 assert(path_ptr == path); 857 857 858 858 /* Should be the root split too? */ 859 859 860 860 uint16_t entries = ext4_extent_header_get_entries_count(path->header); 861 861 uint16_t limit = ext4_extent_header_get_max_entries_count(path->header); 862 862 863 863 if (entries == limit) { 864 864 uint32_t new_fblock; … … 866 866 if (rc != EOK) 867 867 return rc; 868 868 869 869 block_t *block; 870 870 rc = block_get(&block, inode_ref->fs->device, new_fblock, … … 872 872 if (rc != EOK) 873 873 return rc; 874 874 875 875 /* Initialize newly allocated block */ 876 876 memset(block->data, 0, block_size); 877 877 878 878 /* Move data from root to the new block */ 879 879 memcpy(block->data, inode_ref->inode->blocks, 880 880 EXT4_INODE_BLOCKS * sizeof(uint32_t)); 881 881 882 882 /* Data block is initialized */ 883 883 884 884 block_t *root_block = path->block; 885 885 uint16_t root_depth = path->depth; 886 886 ext4_extent_header_t *root_header = path->header; 887 887 888 888 /* Make space for tree growing */ 889 889 ext4_extent_path_t *new_root = path; 890 890 ext4_extent_path_t *old_root = path + 1; 891 891 892 892 size_t nbytes = sizeof(ext4_extent_path_t) * (path->depth + 1); 893 893 memmove(old_root, new_root, nbytes); 894 894 memset(new_root, 0, sizeof(ext4_extent_path_t)); 895 895 896 896 /* Update old root structure */ 897 897 old_root->block = block; 898 898 old_root->header = (ext4_extent_header_t *)block->data; 899 899 900 900 /* Add new entry and update limit for entries */ 901 901 if (old_root->depth) { … … 913 913 old_root->index = NULL; 914 914 } 915 915 916 916 ext4_extent_header_set_entries_count(old_root->header, entries + 1); 917 917 ext4_extent_header_set_max_entries_count(old_root->header, limit); 918 918 919 919 old_root->block->dirty = true; 920 920 921 921 /* Re-initialize new root metadata */ 922 922 new_root->depth = root_depth + 1; … … 925 925 new_root->extent = NULL; 926 926 new_root->index = EXT4_EXTENT_FIRST_INDEX(new_root->header); 927 927 928 928 ext4_extent_header_set_depth(new_root->header, new_root->depth); 929 929 930 930 /* Create new entry in root */ 931 931 ext4_extent_header_set_entries_count(new_root->header, 1); 932 932 ext4_extent_index_set_first_block(new_root->index, 0); 933 933 ext4_extent_index_set_leaf(new_root->index, new_fblock); 934 934 935 935 new_root->block->dirty = true; 936 936 } else { … … 943 943 ext4_extent_set_first_block(path->extent, iblock); 944 944 } 945 945 946 946 ext4_extent_header_set_entries_count(path->header, entries + 1); 947 947 path->block->dirty = true; 948 948 } 949 949 950 950 return EOK; 951 951 } … … 970 970 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode); 971 971 uint32_t block_size = ext4_superblock_get_block_size(sb); 972 972 973 973 /* Calculate number of new logical block */ 974 974 uint32_t new_block_idx = 0; … … 976 976 if ((inode_size % block_size) != 0) 977 977 inode_size += block_size - (inode_size % block_size); 978 978 979 979 new_block_idx = inode_size / block_size; 980 980 } 981 981 982 982 /* Load the nearest leaf (with extent) */ 983 983 ext4_extent_path_t *path; … … 985 985 if (rc != EOK) 986 986 return rc; 987 987 988 988 /* Jump to last item of the path (extent) */ 989 989 ext4_extent_path_t *path_ptr = path; 990 990 while (path_ptr->depth != 0) 991 991 path_ptr++; 992 992 993 993 /* Add new extent to the node if not present */ 994 994 if (path_ptr->extent == NULL) 995 995 goto append_extent; 996 996 997 997 uint16_t block_count = ext4_extent_get_block_count(path_ptr->extent); 998 998 uint16_t block_limit = (1 << 15); 999 999 1000 1000 uint32_t phys_block = 0; 1001 1001 if (block_count < block_limit) { … … 1006 1006 if (rc != EOK) 1007 1007 goto finish; 1008 1008 1009 1009 /* Initialize extent */ 1010 1010 ext4_extent_set_first_block(path_ptr->extent, new_block_idx); 1011 1011 ext4_extent_set_start(path_ptr->extent, phys_block); 1012 1012 ext4_extent_set_block_count(path_ptr->extent, 1); 1013 1013 1014 1014 /* Update i-node */ 1015 1015 if (update_size) { … … 1017 1017 inode_ref->dirty = true; 1018 1018 } 1019 1019 1020 1020 path_ptr->block->dirty = true; 1021 1021 1022 1022 goto finish; 1023 1023 } else { … … 1025 1025 phys_block = ext4_extent_get_start(path_ptr->extent); 1026 1026 phys_block += ext4_extent_get_block_count(path_ptr->extent); 1027 1027 1028 1028 /* Check if the following block is free for allocation */ 1029 1029 bool free; … … 1031 1031 if (rc != EOK) 1032 1032 goto finish; 1033 1033 1034 1034 if (!free) { 1035 1035 /* Target is not free, new block must be appended to new extent */ 1036 1036 goto append_extent; 1037 1037 } 1038 1038 1039 1039 /* Update extent */ 1040 1040 ext4_extent_set_block_count(path_ptr->extent, block_count + 1); 1041 1041 1042 1042 /* Update i-node */ 1043 1043 if (update_size) { … … 1045 1045 inode_ref->dirty = true; 1046 1046 } 1047 1047 1048 1048 path_ptr->block->dirty = true; 1049 1049 1050 1050 goto finish; 1051 1051 } 1052 1052 } 1053 1054 1053 1054 1055 1055 append_extent: 1056 1056 /* Append new extent to the tree */ 1057 1057 phys_block = 0; 1058 1058 1059 1059 /* Allocate new data block */ 1060 1060 rc = ext4_balloc_alloc_block(inode_ref, &phys_block); 1061 1061 if (rc != EOK) 1062 1062 goto finish; 1063 1063 1064 1064 /* Append extent for new block (includes tree splitting if needed) */ 1065 1065 rc = ext4_extent_append_extent(inode_ref, path, new_block_idx); … … 1068 1068 goto finish; 1069 1069 } 1070 1070 1071 1071 uint32_t tree_depth = ext4_extent_header_get_depth(path->header); 1072 1072 path_ptr = path + tree_depth; 1073 1073 1074 1074 /* Initialize newly created extent */ 1075 1075 ext4_extent_set_block_count(path_ptr->extent, 1); 1076 1076 ext4_extent_set_first_block(path_ptr->extent, new_block_idx); 1077 1077 ext4_extent_set_start(path_ptr->extent, phys_block); 1078 1078 1079 1079 /* Update i-node */ 1080 1080 if (update_size) { … … 1082 1082 inode_ref->dirty = true; 1083 1083 } 1084 1084 1085 1085 path_ptr->block->dirty = true; 1086 1086 1087 1087 finish: 1088 1088 ; … … 1093 1093 *iblock = new_block_idx; 1094 1094 *fblock = phys_block; 1095 1095 1096 1096 /* 1097 1097 * Put loaded blocks … … 1105 1105 } 1106 1106 } 1107 1107 1108 1108 /* Destroy temporary data structure */ 1109 1109 free(path); 1110 1110 1111 1111 return rc; 1112 1112 }
Note:
See TracChangeset
for help on using the changeset viewer.