Changeset 96606fe in mainline for uspace/lib/ext4/libext4_extent.c


Ignore:
Timestamp:
2012-07-06T14:50:43Z (12 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
cc51c27
Parents:
d802671d
Message:

completely recoded splitting function

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/libext4_extent.c

    rd802671d r96606fe  
    751751
    752752        /* Trivial way - no splitting */
    753         if (entries < limit) {
    754 
    755                 ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
    756                 path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
    757                 ext4_extent_set_block_count(path_ptr->extent, 0);
    758                 ext4_extent_set_first_block(path_ptr->extent, iblock);
    759                 ext4_extent_set_start(path_ptr->extent, 0);
    760                 path_ptr->block->dirty = true;
    761 
    762                 return EOK;
    763         }
     753//      if ((entries < limit) && (path == path_ptr)) {
     754//
     755//              ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
     756//              path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
     757//              path_ptr->block->dirty = true;
     758//
     759//              return EOK;
     760//      }
    764761
    765762        uint32_t block_size =
    766763                        ext4_superblock_get_block_size(inode_ref->fs->superblock);
    767764
    768         /* Trivial tree - grow (extents were in root node) */
    769         if (path_ptr == path) {
    770 
    771                 EXT4FS_DBG("splitting root with extents");
    772 
    773                 uint32_t new_fblock;
    774                 rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);
    775                 if (rc != EOK) {
    776                         EXT4FS_DBG("error in block allocation");
    777                         return rc;
    778                 }
    779 
    780                 EXT4FS_DBG("alllocated block \%u for new leaf", new_fblock);
    781 
    782                 block_t *block;
    783                 rc = block_get(&block, inode_ref->fs->device,
    784                                 new_fblock, BLOCK_FLAGS_NOREAD);
    785                 if (rc != EOK) {
    786                         EXT4FS_DBG("error in block_get");
    787                         return rc;
    788                 }
    789 
    790                 memset(block->data, 0, block_size);
    791 
    792                 /* Move data from root to the new block */
    793                 memcpy(block->data, inode_ref->inode->blocks,
    794                                 EXT4_INODE_BLOCKS * sizeof(uint32_t));
    795 
    796                 path_ptr++;
    797                 path_ptr->block = block;
    798                 path_ptr->header = (ext4_extent_header_t *)block->data;
    799                 path_ptr->depth = 0;
    800                 path_ptr->index = NULL;
    801 
    802                 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
    803                 path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
    804                 ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
    805                 uint16_t limit = (block_size - sizeof(ext4_extent_header_t)) /
    806                                 sizeof(ext4_extent_t);
    807                 ext4_extent_header_set_max_entries_count(path_ptr->header, limit);
    808 
    809                 /* Initialize new extent */
    810                 ext4_extent_set_block_count(path_ptr->extent, 0);
    811                 ext4_extent_set_first_block(path_ptr->extent, iblock);
    812                 ext4_extent_set_start(path_ptr->extent, 0);
    813 
    814                 /* Modify root (in inode) */
    815                 path->depth = 1;
    816                 path->extent = NULL;
    817                 path->index = EXT4_EXTENT_FIRST_INDEX(path->header);
    818 
    819                 ext4_extent_header_set_depth(path->header, 1);
    820                 ext4_extent_header_set_entries_count(path->header, 1);
    821 
    822                 ext4_extent_index_set_first_block(path->index, 0);
    823                 ext4_extent_index_set_leaf(path->index, new_fblock);
    824 
    825                 path_ptr->block->dirty = true;
    826                 path->block->dirty = true;
    827 
    828                 *last_path_item = path_ptr;
    829 
    830 
    831                 ext4_extent_header_t *tmp_root = path->header;
    832                 EXT4FS_DBG("new root: items = \%u, maximum = \%u, depth = \%u", ext4_extent_header_get_entries_count(tmp_root),
    833                                 ext4_extent_header_get_max_entries_count(tmp_root), ext4_extent_header_get_depth(tmp_root));
    834 
    835                 ext4_extent_index_t *root_idx = EXT4_EXTENT_FIRST_INDEX(path->header);
    836                 EXT4FS_DBG("first iblock = \%u, fblock = \%u", ext4_extent_index_get_first_block(root_idx),
    837                                 (uint32_t)ext4_extent_index_get_leaf(root_idx));
    838 
    839                 ext4_extent_header_t *new_leaf = path_ptr->header;
    840                 EXT4FS_DBG("new leaf: items = \%u, maximum = \%u, depth = \%u", ext4_extent_header_get_entries_count(new_leaf),
    841                                 ext4_extent_header_get_max_entries_count(new_leaf), ext4_extent_header_get_depth(new_leaf));
    842 
    843                 for (uint32_t j = 0; j < ext4_extent_header_get_entries_count(new_leaf); ++j) {
    844                         ext4_extent_t *tmp_ext = EXT4_EXTENT_FIRST(path_ptr->header) + j;
    845 
    846                         EXT4FS_DBG("item \%u, first iblock = \%u", j, ext4_extent_get_first_block(tmp_ext));
    847                 }
    848 
    849 
    850                 EXT4FS_DBG("Root block containing extents was split");
    851                 return EOK;
    852         }
     765//      /* Trivial tree - grow (extents were in root node) */
     766//      if ((path_ptr == path) && ((entries == limit))){
     767//
     768//              EXT4FS_DBG("splitting root with extents");
     769//
     770//              uint32_t new_fblock;
     771//              rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);
     772//              if (rc != EOK) {
     773//                      EXT4FS_DBG("error in block allocation");
     774//                      return rc;
     775//              }
     776//
     777////            EXT4FS_DBG("alllocated block \%u for new leaf", new_fblock);
     778//
     779//              block_t *block;
     780//              rc = block_get(&block, inode_ref->fs->device,
     781//                              new_fblock, BLOCK_FLAGS_NOREAD);
     782//              if (rc != EOK) {
     783//                      EXT4FS_DBG("error in block_get");
     784//                      return rc;
     785//              }
     786//
     787//              memset(block->data, 0, block_size);
     788//
     789//              /* Move data from root to the new block */
     790//              memcpy(block->data, inode_ref->inode->blocks,
     791//                              EXT4_INODE_BLOCKS * sizeof(uint32_t));
     792//
     793//              path_ptr++;
     794//              path_ptr->block = block;
     795//              path_ptr->header = (ext4_extent_header_t *)block->data;
     796//              path_ptr->depth = 0;
     797//              path_ptr->index = NULL;
     798//
     799//              uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
     800//              path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
     801//              ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
     802//              uint16_t limit = (block_size - sizeof(ext4_extent_header_t)) /
     803//                              sizeof(ext4_extent_t);
     804//              ext4_extent_header_set_max_entries_count(path_ptr->header, limit);
     805//
     806//              /* Modify root (in inode) */
     807//              path->depth = 1;
     808//              path->extent = NULL;
     809//              path->index = EXT4_EXTENT_FIRST_INDEX(path->header);
     810//
     811//              ext4_extent_header_set_depth(path->header, 1);
     812//              ext4_extent_header_set_entries_count(path->header, 1);
     813//
     814//              ext4_extent_index_set_first_block(path->index, 0);
     815//              ext4_extent_index_set_leaf(path->index, new_fblock);
     816//
     817//              path_ptr->block->dirty = true;
     818//              path->block->dirty = true;
     819//
     820//              *last_path_item = path_ptr;
     821//
     822////            ext4_extent_header_t *tmp_root = path->header;
     823////            EXT4FS_DBG("new root: items = \%u, maximum = \%u, depth = \%u", ext4_extent_header_get_entries_count(tmp_root),
     824////                            ext4_extent_header_get_max_entries_count(tmp_root), ext4_extent_header_get_depth(tmp_root));
     825////
     826////            ext4_extent_index_t *root_idx = EXT4_EXTENT_FIRST_INDEX(path->header);
     827////            EXT4FS_DBG("first iblock = \%u, fblock = \%u", ext4_extent_index_get_first_block(root_idx),
     828////                            (uint32_t)ext4_extent_index_get_leaf(root_idx));
     829////
     830////            ext4_extent_header_t *new_leaf = path_ptr->header;
     831////            EXT4FS_DBG("new leaf: items = \%u, maximum = \%u, depth = \%u", ext4_extent_header_get_entries_count(new_leaf),
     832////                            ext4_extent_header_get_max_entries_count(new_leaf), ext4_extent_header_get_depth(new_leaf));
     833////
     834////            for (uint32_t j = 0; j < ext4_extent_header_get_entries_count(new_leaf); ++j) {
     835////                    ext4_extent_t *tmp_ext = EXT4_EXTENT_FIRST(path_ptr->header) + j;
     836////
     837////                    EXT4FS_DBG("item \%u, first iblock = \%u", j, ext4_extent_get_first_block(tmp_ext));
     838////            }
     839//
     840//              EXT4FS_DBG("Root block containing extents was split");
     841//              return EOK;
     842//      }
    853843
    854844        // TODO !!!
    855845//      assert(false);
    856846
    857         EXT4FS_DBG("More complex splitting");
     847//      EXT4FS_DBG("More complex splitting");
    858848
    859849        /* Start splitting */
    860         uint32_t fblock = 0;
    861850        while (path_ptr > path) {
    862 
    863                 // TODO
    864 
    865                 rc = ext4_balloc_alloc_block(inode_ref, &fblock);
    866                 if (rc != EOK) {
    867                         return rc;
    868                 }
    869 
    870                 block_t *block;
    871                 rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NOREAD);
    872                 if (rc != EOK) {
    873                         ext4_balloc_free_block(inode_ref, fblock);
    874                         return rc;
    875                 }
    876 
    877                 /* Init block */
    878                 memset(block->data, 0, block_size);
    879 
    880                 /* Not modified */
    881                 block_put(path_ptr->block);
    882                 path_ptr->block = block;
    883 
    884                 path_ptr->header = block->data;
    885 
    886                 if (path_ptr->depth) {
    887                         path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header);
     851                uint32_t fblock;
     852
     853                entries = ext4_extent_header_get_entries_count(path_ptr->header);
     854                limit = ext4_extent_header_get_max_entries_count(path_ptr->header);
     855
     856                if (entries == limit) {
     857
     858                        EXT4FS_DBG("Full non-root node (\%s)", path_ptr->depth ? "index" : "extent");
     859
     860                        /* Full node */
     861                        rc = ext4_balloc_alloc_block(inode_ref, &fblock);
     862                        if (rc != EOK) {
     863                                return rc;
     864                        }
     865
     866                        block_t *block;
     867                        rc = block_get(&block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NOREAD);
     868                        if (rc != EOK) {
     869                                ext4_balloc_free_block(inode_ref, fblock);
     870                                return rc;
     871                        }
     872
     873                        /* Init block */
     874                        memset(block->data, 0, block_size);
     875
     876                        /* Not modified old block */
     877                        block_put(path_ptr->block);
     878                        path_ptr->block = block;
     879                        path_ptr->header = block->data;
     880
     881                        if (path_ptr->depth) {
     882                                path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header);
     883                                ext4_extent_index_set_first_block(path_ptr->index, iblock);
     884                                ext4_extent_index_set_leaf(path_ptr->index, (path_ptr + 1)->block->lba);
     885                                limit = (block_size - sizeof(ext4_extent_header_t)) /
     886                                                                        sizeof(ext4_extent_index_t);
     887                        } else {
     888                                path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header);
     889                                ext4_extent_set_first_block(path_ptr->extent, iblock);
     890                                limit = (block_size - sizeof(ext4_extent_header_t)) /
     891                                                                        sizeof(ext4_extent_t);
     892                        }
     893
     894                        ext4_extent_header_set_entries_count(path_ptr->header, 1);
     895                        ext4_extent_header_set_max_entries_count(path_ptr->header, limit);
     896
     897                        path_ptr->block->dirty = true;
     898
     899                        path_ptr--;
     900
    888901                } else {
    889                         path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header);
    890                 }
    891 
    892                 path_ptr--;
    893         }
    894 
    895         /* If splitting reached root node */
     902
     903//                      EXT4FS_DBG("Adding entry non-root node (\%s)", path_ptr->depth ? "index" : "extent");
     904
     905                        /* Node with free space */
     906                        if (path_ptr->depth) {
     907                                path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
     908                                ext4_extent_index_set_first_block(path_ptr->index, iblock);
     909                                ext4_extent_index_set_leaf(path_ptr->index, (path_ptr + 1)->block->lba);
     910                        } else {
     911                                path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
     912                                ext4_extent_set_first_block(path_ptr->extent, iblock);
     913                        }
     914
     915                        ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
     916                        path_ptr->block->dirty = true;
     917                        *last_path_item = path_ptr;
     918
     919                        return EOK;
     920                }
     921
     922        }
     923
     924        /* Should be the root split too? */
    896925        if (path_ptr == path) {
    897926
    898                 EXT4FS_DBG("Splitting root");
    899 
    900                 uint32_t new_fblock;
    901                 rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);
    902                 if (rc != EOK) {
    903                         EXT4FS_DBG("error in block allocation");
    904                         return rc;
    905                 }
    906 
    907                 block_t *block;
    908                 rc = block_get(&block, inode_ref->fs->device,
    909                                 new_fblock, BLOCK_FLAGS_NOREAD);
    910                 if (rc != EOK) {
    911                         EXT4FS_DBG("error in block_get");
    912                         return rc;
    913                 }
    914 
    915                 memset(block->data, 0, block_size);
    916 
    917                 /* Move data from root to the new block */
    918                 memcpy(block->data, inode_ref->inode->blocks,
    919                                 EXT4_INODE_BLOCKS * sizeof(uint32_t));
    920 
    921                 path_ptr++;
    922                 path_ptr->block = block;
    923                 path_ptr->header = (ext4_extent_header_t *)block->data;
    924                 path_ptr->depth = ext4_extent_header_get_depth(path_ptr->header);
    925                 path_ptr->index = NULL;
    926 
    927                 uint16_t entries = ext4_extent_header_get_entries_count(path_ptr->header);
    928                 path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
    929                 ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
    930                 uint16_t limit = (block_size - sizeof(ext4_extent_header_t)) /
    931                                 sizeof(ext4_extent_t);
    932                 ext4_extent_header_set_max_entries_count(path_ptr->header, limit);
    933 
    934                 /* Modify root (in inode) */
    935                 path->depth = 1;
    936                 path->extent = NULL;
    937                 path->index = EXT4_EXTENT_FIRST_INDEX(path->header);
    938 
    939                 ext4_extent_header_set_depth(path->header, path_ptr->depth + 1);
    940                 ext4_extent_header_set_entries_count(path->header, 1);
    941 
    942                 ext4_extent_index_set_first_block(path->index, 0);
    943                 ext4_extent_index_set_leaf(path->index, new_fblock);
    944 
    945                 path_ptr->block->dirty = true;
    946                 path->block->dirty = true;
    947 
    948                 *last_path_item = path_ptr;
    949 
    950         }
    951 
    952         EXT4FS_DBG("Finishing");
     927                entries = ext4_extent_header_get_entries_count(path->header);
     928                limit = ext4_extent_header_get_max_entries_count(path->header);
     929
     930                if (entries == limit) {
     931
     932                        EXT4FS_DBG("Splitting root");
     933
     934                        uint32_t new_fblock;
     935                        rc = ext4_balloc_alloc_block(inode_ref, &new_fblock);
     936                        if (rc != EOK) {
     937                                EXT4FS_DBG("error in block allocation");
     938                                return rc;
     939                        }
     940
     941                        block_t *block;
     942                        rc = block_get(&block, inode_ref->fs->device,
     943                                        new_fblock, BLOCK_FLAGS_NOREAD);
     944                        if (rc != EOK) {
     945                                EXT4FS_DBG("error in block_get");
     946                                return rc;
     947                        }
     948
     949                        memset(block->data, 0, block_size);
     950
     951                        /* Move data from root to the new block */
     952                        memcpy(block->data, inode_ref->inode->blocks,
     953                                        EXT4_INODE_BLOCKS * sizeof(uint32_t));
     954
     955                        EXT4FS_DBG("New block prepared");
     956
     957                        /* Make space for tree growing */
     958                        memmove(path + 1, path, path->depth + 1);
     959
     960                        EXT4FS_DBG("Place for new root ready");
     961
     962                        path_ptr = path + 1;
     963                        path_ptr->block = block;
     964                        path_ptr->header = (ext4_extent_header_t *)block->data;
     965
     966                        if (path_ptr->depth) {
     967                                limit = (block_size - sizeof(ext4_extent_header_t)) /
     968                                                                        sizeof(ext4_extent_index_t);
     969                                path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
     970                                ext4_extent_index_set_first_block(path_ptr->index, iblock);
     971                                ext4_extent_index_set_leaf(path_ptr->index, (path_ptr + 1)->block->lba);
     972                                path_ptr->extent = NULL;
     973                        } else {
     974                                limit = (block_size - sizeof(ext4_extent_header_t)) /
     975                                                                        sizeof(ext4_extent_t);
     976                                path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
     977                                ext4_extent_set_first_block(path_ptr->extent, iblock);
     978                                path_ptr->index = NULL;
     979                        }
     980
     981                        ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
     982                        ext4_extent_header_set_max_entries_count(path_ptr->header, limit);
     983
     984                        path_ptr->block->dirty = true;
     985
     986                        path->block = inode_ref->block;
     987                        path->depth = path_ptr->depth + 1;
     988                        path->header = (ext4_extent_header_t *)inode_ref->inode->blocks;
     989                        path->extent = NULL;
     990                        path->index = EXT4_EXTENT_FIRST_INDEX(path->header);
     991
     992
     993                        ext4_extent_header_set_entries_count(path->header, 1);
     994                        ext4_extent_header_set_depth(path->header, path->depth);
     995
     996                        ext4_extent_index_set_first_block(path->index, 0);
     997                        ext4_extent_index_set_leaf(path->index, new_fblock);
     998
     999                        path->block->dirty = true;
     1000
     1001                        *last_path_item = *last_path_item + 1;
     1002
     1003                        EXT4FS_DBG("Leaving split root");
     1004
     1005                } else {
     1006
     1007                        EXT4FS_DBG("Adding entry to root node");
     1008
     1009                        if (path_ptr->depth) {
     1010                                path_ptr->index = EXT4_EXTENT_FIRST_INDEX(path_ptr->header) + entries;
     1011                                ext4_extent_index_set_first_block(path_ptr->index, iblock);
     1012                                ext4_extent_index_set_leaf(path_ptr->index, (path_ptr + 1)->block->lba);
     1013                        } else {
     1014                                path_ptr->extent = EXT4_EXTENT_FIRST(path_ptr->header) + entries;
     1015                                ext4_extent_set_first_block(path_ptr->extent, iblock);
     1016                        }
     1017
     1018                        ext4_extent_header_set_entries_count(path_ptr->header, entries + 1);
     1019                        path->block->dirty = true;
     1020                }
     1021        }
     1022
    9531023
    9541024        return EOK;
Note: See TracChangeset for help on using the changeset viewer.