Lines Matching +full:- +full:- +full:depth
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
74 fs = ip->i_e2fs;
76 if (blk < fs->e2fs->e2fs_first_dblock || blk >= fs->e2fs_bcount)
83 ext4_ext_walk_index(struct inode *ip, struct ext4_extent_index *ex, int depth,
91 fs = ip->i_e2fs;
95 le32toh(ex->ei_blk),
96 (uint64_t)le16toh(ex->ei_leaf_hi) << 32 |
97 le32toh(ex->ei_leaf_lo));
107 if ((error = bread(ip->i_devvp,
108 fsbtodb(fs, blk), (int)fs->e2fs_bsize, NOCRED, &bp)) != 0) {
114 (struct ext4_extent_header *)bp->b_data, depth);
134 ep, le32toh(ep->e_blk), le16toh(ep->e_len),
141 ext4_ext_walk_header(struct inode *ip, struct ext4_extent_header *eh, int depth)
145 error = ext4_ext_check_header(ip, eh, depth);
150 printf("header %p => (entries %d max %d depth %d gen %d)\n",
151 eh, le16toh(eh->eh_ecount),
152 le16toh(eh->eh_max), le16toh(eh->eh_depth),
153 le32toh(eh->eh_gen));
155 for (i = 0; i < le16toh(eh->eh_ecount) && error == 0; i++)
156 if (eh->eh_depth != 0)
158 (struct ext4_extent_index *)(eh + 1 + i), depth - 1,
172 ehp = (struct ext4_extent_header *)ip->i_db;
175 printf("Extent status:ip=%ju\n", ip->i_number);
177 if (!(ip->i_flag & IN_E4EXTENTS))
186 int k, depth, error = 0;
188 depth = path->ep_depth;
191 printf("ip=%ju, Path:\n", ip->i_number);
193 for (k = 0; k <= depth && error == 0; k++, path++) {
194 if (path->ep_index) {
195 error = ext4_ext_walk_index(ip, path->ep_index,
196 depth - 1, false);
197 } else if (path->ep_ext) {
198 error = ext4_ext_walk_extent(ip, path->ep_ext);
210 return ((struct ext4_extent_header *)ip->i_db);
225 ehp = (struct ext4_extent_header *)ip->i_data;
226 return (le16toh(ehp->eh_depth));
234 blk = le32toh(index->ei_leaf_lo);
235 blk |= (e4fs_daddr_t)le16toh(index->ei_leaf_hi) << 32;
244 index->ei_leaf_lo = htole32(pb & 0xffffffff);
245 index->ei_leaf_hi = htole16((pb >> 32) & 0xffff);
253 blk = le32toh(extent->e_start_lo);
254 blk |= (e4fs_daddr_t)le16toh(extent->e_start_hi) << 32;
263 ex->e_start_lo = htole32(pb & 0xffffffff);
264 ex->e_start_hi = htole16((pb >> 32) & 0xffff);
273 ecp = &ip->i_ext_cache;
274 if (ecp->ec_type == EXT4_EXT_CACHE_NO)
277 if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
278 ep->e_blk = htole32(ecp->ec_blk);
279 ep->e_start_lo = htole32(ecp->ec_start & 0xffffffff);
280 ep->e_start_hi = htole16(ecp->ec_start >> 32 & 0xffff);
281 ep->e_len = htole16(ecp->ec_len);
282 ret = ecp->ec_type;
292 size = sizeof(ip->i_data);
293 size -= sizeof(struct ext4_extent_header);
305 fs = ip->i_e2fs;
307 size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
318 size = sizeof(ip->i_data);
319 size -= sizeof(struct ext4_extent_header);
331 fs = ip->i_e2fs;
333 size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
340 ext4_ext_max_entries(struct inode *ip, int depth)
343 if (depth == ext4_ext_inode_depth(ip)) {
344 if (depth == 0)
349 if (depth == 0)
360 return (le16toh(ext->e_len) <= EXT_INIT_MAX_LEN ?
361 le16toh(ext->e_len) : (le16toh(ext->e_len) - EXT_INIT_MAX_LEN));
371 fs = ip->i_e2fs;
373 if ((start_blk <= le32toh(fs->e2fs->e2fs_first_dblock)) ||
375 (start_blk + count > fs->e2fs_bcount))
385 uint32_t lblk = le32toh(ext->e_blk);
404 int depth)
408 count = le16toh(eh->eh_ecount);
412 if (depth == 0) {
423 lblk = le32toh(ext->e_blk);
429 count--;
430 prev = lblk + len - 1;
439 count--;
448 int depth)
456 if (le16toh(eh->eh_magic) != EXT4_EXT_MAGIC) {
460 if (le16toh(eh->eh_depth) != depth ||
461 le16toh(eh->eh_depth) > EXT4_EXT_DEPTH_MAX)
466 if (eh->eh_max == 0) {
470 if (le16toh(eh->eh_max) > ext4_ext_max_entries(ip, depth)) {
474 if (le16toh(eh->eh_ecount) > le16toh(eh->eh_max)) {
478 if (le16toh(eh->eh_depth) > EXT4_EXT_DEPTH_MAX) {
482 if (ext4_validate_extent_entries(ip, eh, depth)) {
500 eh = path->ep_header;
502 KASSERT(le16toh(eh->eh_ecount) <= le16toh(eh->eh_max) &&
503 le16toh(eh->eh_ecount) > 0,
507 r = EXT_FIRST_INDEX(eh) + le16toh(eh->eh_ecount) - 1;
509 m = l + (r - l) / 2;
510 if (blk < le32toh(m->ei_blk))
511 r = m - 1;
516 path->ep_index = l - 1;
525 eh = path->ep_header;
527 KASSERT(le16toh(eh->eh_ecount) <= le16toh(eh->eh_max),
530 if (eh->eh_ecount == 0)
534 r = EXT_FIRST_EXTENT(eh) + le16toh(eh->eh_ecount) - 1;
537 m = l + (r - l) / 2;
538 if (blk < le32toh(m->e_blk))
539 r = m - 1;
544 path->ep_ext = l - 1;
552 KASSERT(path->ep_data == NULL,
555 path->ep_data = malloc(bp->b_bufsize, M_EXT2EXTENTS, M_WAITOK);
556 memcpy(path->ep_data, bp->b_data, bp->b_bufsize);
557 path->ep_blk = blk;
566 KASSERT(path->ep_data != NULL,
569 memcpy(bp->b_data, path->ep_data, bp->b_bufsize);
575 int depth, i;
580 depth = path->ep_depth;
581 for (i = 0; i <= depth; i++, path++)
582 if (path->ep_data) {
583 free(path->ep_data, M_EXT2EXTENTS);
584 path->ep_data = NULL;
607 int error, depth, i, ppos, alloc;
610 depth = ext4_ext_inode_depth(ip);
614 error = ext4_ext_check_header(ip, eh, depth);
634 i = depth;
641 error = bread(ip->i_devvp, fsbtodb(ip->i_e2fs, blk),
642 ip->i_e2fs->e2fs_bsize, NOCRED, &bp);
648 if (ppos > depth) {
650 "ppos > depth => extent corrupted");
660 if (ext4_ext_check_header(ip, eh, i - 1) ||
668 i--;
699 fs = ip->i_e2fs;
701 size = (fs->e2fs_bsize - sizeof(struct ext4_extent_header)) /
712 ip->i_flag |= IN_E4EXTENTS;
714 memset(ip->i_data, 0, sizeof(ip->i_data));
715 ehp = (struct ext4_extent_header *)ip->i_data;
716 ehp->eh_magic = htole16(EXT4_EXT_MAGIC);
717 ehp->eh_max = htole16(ext4_ext_space_root(ip));
718 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;
719 ip->i_flag |= IN_CHANGE | IN_UPDATE;
720 ext2_update(ip->i_vnode, 1);
730 ip->i_ext_cache.ec_type = type;
731 ip->i_ext_cache.ec_blk = blk;
732 ip->i_ext_cache.ec_len = len;
733 ip->i_ext_cache.ec_start = start;
743 int depth;
745 fs = ip->i_e2fs;
748 depth = path->ep_depth;
749 ex = path[depth].ep_ext;
752 e2fs_daddr_t blk = le32toh(ex->e_blk);
755 return (pblk + (block - blk));
757 return (pblk - (blk - block));
761 if (path[depth].ep_data)
762 return (path[depth].ep_blk);
766 bg_start = (ip->i_block_group * EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) +
767 le32toh(fs->e2fs->e2fs_first_dblock);
777 if (le32toh(ex1->e_blk) + le16toh(ex1->e_len) != le32toh(ex2->e_blk))
780 if (le16toh(ex1->e_len) + le16toh(ex2->e_len) > EXT4_MAX_LEN)
783 if (ext4_ext_extent_pblock(ex1) + le16toh(ex1->e_len) ==
793 int depth = path->ep_depth;
796 if (depth == 0)
800 depth--;
802 while (depth >= 0) {
803 if (path[depth].ep_index !=
804 EXT_LAST_INDEX(path[depth].ep_header))
805 return (le32toh(path[depth].ep_index[1].ei_blk));
807 depth--;
821 fs = ip->i_e2fs;
826 if (path->ep_data) {
827 blk = path->ep_blk;
828 bp = getblk(ip->i_devvp, fsbtodb(fs, blk),
829 fs->e2fs_bsize, 0, 0, 0);
833 ext2_extent_blk_csum_set(ip, bp->b_data);
836 ip->i_flag |= IN_CHANGE | IN_UPDATE;
837 error = ext2_update(ip->i_vnode, 1);
850 if (lblk == le32toh(path->ep_index->ei_blk)) {
856 if (le16toh(path->ep_header->eh_ecount) >=
857 le16toh(path->ep_header->eh_max)) {
863 if (lblk > le32toh(path->ep_index->ei_blk)) {
865 idx = path->ep_index + 1;
868 idx = path->ep_index;
871 len = EXT_LAST_INDEX(path->ep_header) - idx + 1;
875 if (idx > EXT_MAX_INDEX(path->ep_header)) {
881 idx->ei_blk = htole32(lblk);
883 path->ep_header->eh_ecount =
884 htole16(le16toh(path->ep_header->eh_ecount) + 1);
894 ip->i_blocks += btodb(ip->i_e2fs->e2fs_bsize);
895 ip->i_flag |= IN_CHANGE | IN_UPDATE;
896 ext2_update(ip->i_vnode, 1);
908 fs = ip->i_e2fs;
912 ext2_blkfree(ip, blk + i, fs->e2fs_bsize);
914 if (ip->i_blocks >= blocksreleased)
915 ip->i_blocks -= (btodb(fs->e2fs_bsize)*blocksreleased);
917 ip->i_blocks = 0;
919 ip->i_flag |= IN_CHANGE | IN_UPDATE;
920 ext2_update(ip->i_vnode, 1);
929 int depth = ext4_ext_inode_depth(ip);
939 fs = ip->i_e2fs;
945 if (path[depth].ep_ext > EXT_MAX_EXTENT(path[depth].ep_header)) {
951 if (path[depth].ep_ext != EXT_MAX_EXTENT(path[depth].ep_header))
952 border = le32toh(path[depth].ep_ext[1].e_blk);
954 border = le32toh(newext->e_blk);
957 ablks = malloc(sizeof(e4fs_daddr_t) * depth,
959 for (a = 0; a < depth - at; a++) {
966 newblk = ablks[--a];
967 bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0);
973 neh = ext4_ext_block_header(bp->b_data);
974 neh->eh_ecount = 0;
975 neh->eh_max = le16toh(ext4_ext_space_block(ip));
976 neh->eh_magic = le16toh(EXT4_EXT_MAGIC);
977 neh->eh_depth = 0;
980 if (le16toh(path[depth].ep_header->eh_ecount) !=
981 le16toh(path[depth].ep_header->eh_max)) {
990 path[depth].ep_ext++;
991 while (path[depth].ep_ext <= EXT_MAX_EXTENT(path[depth].ep_header)) {
992 path[depth].ep_ext++;
996 memmove(ex, path[depth].ep_ext - m,
998 neh->eh_ecount = htole16(le16toh(neh->eh_ecount) + m);
1001 ext2_extent_blk_csum_set(ip, bp->b_data);
1007 path[depth].ep_header->eh_ecount =
1008 htole16(le16toh(path[depth].ep_header->eh_ecount) - m);
1009 ext4_ext_dirty(ip, path + depth);
1013 k = depth - at - 1;
1017 i = depth - 1;
1018 while (k--) {
1020 newblk = ablks[--a];
1021 error = bread(ip->i_devvp, fsbtodb(fs, newblk),
1022 (int)fs->e2fs_bsize, NOCRED, &bp);
1027 neh = (struct ext4_extent_header *)bp->b_data;
1028 neh->eh_ecount = htole16(1);
1029 neh->eh_magic = htole16(EXT4_EXT_MAGIC);
1030 neh->eh_max = htole16(ext4_ext_space_block_index(ip));
1031 neh->eh_depth = htole16(depth - i);
1033 fidx->ei_blk = htole32(border);
1043 memmove(++fidx, path[i].ep_index - m,
1045 neh->eh_ecount = htole16(le16toh(neh->eh_ecount) + m);
1048 ext2_extent_blk_csum_set(ip, bp->b_data);
1054 path[i].ep_header->eh_ecount =
1055 htole16(le16toh(path[i].ep_header->eh_ecount) - m);
1059 i--;
1069 for (i = 0; i < depth; i++) {
1092 fs = ip->i_e2fs;
1099 bp = getblk(ip->i_devvp, fsbtodb(fs, newblk), fs->e2fs_bsize, 0, 0, 0);
1105 /* Move top-level index/leaf into new block. */
1106 memmove(bp->b_data, curpath->ep_header, sizeof(ip->i_data));
1109 neh = ext4_ext_block_header(bp->b_data);
1110 neh->eh_magic = htole16(EXT4_EXT_MAGIC);
1113 neh->eh_max = htole16(ext4_ext_space_block_index(ip));
1115 neh->eh_max = htole16(ext4_ext_space_block(ip));
1117 ext2_extent_blk_csum_set(ip, bp->b_data);
1126 curpath->ep_header->eh_magic = htole16(EXT4_EXT_MAGIC);
1127 curpath->ep_header->eh_max = htole16(ext4_ext_space_root(ip));
1128 curpath->ep_header->eh_ecount = htole16(1);
1129 curpath->ep_index = EXT_FIRST_INDEX(curpath->ep_header);
1130 curpath->ep_index->ei_blk = EXT_FIRST_EXTENT(path[0].ep_header)->e_blk;
1131 ext4_index_store_pblock(curpath->ep_index, newblk);
1134 neh->eh_depth = htole16(path->ep_depth + 1);
1147 int depth, i, error;
1150 i = depth = ext4_ext_inode_depth(ip);
1153 curpath = path + depth;
1155 i--;
1156 curpath--;
1170 error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path);
1174 /* Tree is full, do grow in depth. */
1181 error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path);
1186 depth = ext4_ext_inode_depth(ip);
1187 if (le16toh(path[depth].ep_header->eh_ecount) ==
1188 le16toh(path[depth].ep_header->eh_max))
1202 int depth, k;
1204 depth = ext4_ext_inode_depth(ip);
1205 eh = path[depth].ep_header;
1206 ex = path[depth].ep_ext;
1211 if (!depth)
1218 k = depth - 1;
1219 border = le32toh(path[depth].ep_ext->e_blk);
1220 path[k].ep_index->ei_blk = htole32(border);
1222 while (k--) {
1223 /* Change all left-side indexes. */
1227 path[k].ep_index->ei_blk = htole32(border);
1241 int depth, len, error, next;
1243 depth = ext4_ext_inode_depth(ip);
1244 ex = path[depth].ep_ext;
1247 if (htole16(newext->e_len) == 0 || path[depth].ep_header == NULL)
1252 ex->e_len = htole16(le16toh(ex->e_len) + le16toh(newext->e_len));
1253 eh = path[depth].ep_header;
1259 depth = ext4_ext_inode_depth(ip);
1260 eh = path[depth].ep_header;
1261 if (le16toh(eh->eh_ecount) < le16toh(eh->eh_max))
1267 if (le32toh(newext->e_blk) > le32toh(nex->e_blk) && next !=
1276 if (npath->ep_depth != path->ep_depth) {
1281 eh = npath[depth].ep_header;
1282 if (le16toh(eh->eh_ecount) < le16toh(eh->eh_max)) {
1296 depth = ext4_ext_inode_depth(ip);
1297 eh = path[depth].ep_header;
1300 nearex = path[depth].ep_ext;
1303 path[depth].ep_ext = EXT_FIRST_EXTENT(eh);
1304 } else if (le32toh(newext->e_blk) > le32toh(nearex->e_blk)) {
1306 len = EXT_MAX_EXTENT(eh) - nearex;
1307 len = (len - 1) * sizeof(struct ext4_extent);
1311 path[depth].ep_ext = nearex + 1;
1313 len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1316 path[depth].ep_ext = nearex;
1319 eh->eh_ecount = htole16(le16toh(eh->eh_ecount) + 1);
1320 nearex = path[depth].ep_ext;
1321 nearex->e_blk = newext->e_blk;
1322 nearex->e_start_lo = newext->e_start_lo;
1323 nearex->e_start_hi = newext->e_start_hi;
1324 nearex->e_len = newext->e_len;
1333 nearex->e_len = htole16(le16toh(nearex->e_len) +
1336 len = (EXT_LAST_EXTENT(eh) - nearex - 1) *
1341 eh->eh_ecount = htole16(le16toh(eh->eh_ecount) - 1);
1342 KASSERT(le16toh(eh->eh_ecount) != 0,
1354 ext4_ext_dirty(ip, path + depth);
1362 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;
1379 fs = ip->i_e2fs;
1380 EXT2_LOCK(ip->i_ump);
1381 *perror = ext2_alloc(ip, lbn, pref, (int)fs->e2fs_bsize, cred, &newblk);
1386 ip->i_flag |= IN_CHANGE | IN_UPDATE;
1387 ext2_update(ip->i_vnode, 1);
1404 int error = 0, depth;
1415 newblk = iblk - le32toh(newex.e_blk) +
1417 allocated = le16toh(newex.e_len) - (iblk - le32toh(newex.e_blk));
1430 depth = ext4_ext_inode_depth(ip);
1431 if (path[depth].ep_ext == NULL && depth != 0) {
1436 if ((ex = path[depth].ep_ext)) {
1437 uint64_t lblk = le32toh(ex->e_blk);
1438 uint16_t e_len = le16toh(ex->e_len);
1446 newblk = iblk - lblk + e_start;
1447 allocated = e_len - (iblk - lblk);
1455 if (S_ISREG(ip->i_mode) && (!ip->i_next_alloc_block)) {
1456 ip->i_next_alloc_goal = 0;
1483 fs = ip->i_e2fs;
1484 error = bread(ip->i_devvp, fsbtodb(fs, newblk),
1485 fs->e2fs_bsize, cred, &bp);
1509 return ((struct ext4_extent_header *)ip->i_db);
1518 if (from >= le32toh(ex->e_blk) &&
1519 to == le32toh(ex->e_blk) + ext4_ext_get_actual_len(ex) - 1) {
1521 num = le32toh(ex->e_blk) + ext4_ext_get_actual_len(ex) - from;
1523 ext4_ext_get_actual_len(ex) - num;
1536 path--;
1537 leaf = ext4_ext_index_pblock(path->ep_index);
1538 KASSERT(path->ep_header->eh_ecount != 0,
1540 path->ep_header->eh_ecount =
1541 htole16(le16toh(path->ep_header->eh_ecount) - 1);
1556 int depth;
1559 depth = ext4_ext_inode_depth(ip);
1560 if (!path[depth].ep_header) {
1561 if (path[depth].ep_data == NULL)
1563 path[depth].ep_header =
1564 (struct ext4_extent_header* )path[depth].ep_data;
1567 eh = path[depth].ep_header;
1575 ex_blk = le32toh(ex->e_blk);
1581 path[depth].ep_ext = ex;
1583 b = (uint64_t)ex_blk + ex_len - 1 <
1584 EXT4_MAX_BLOCKS ? ex_blk + ex_len - 1 : EXT4_MAX_BLOCKS;
1586 if (a != ex_blk && b != ex_blk + ex_len - 1)
1591 num = a - block;
1592 } else if (b != ex_blk + ex_len - 1) {
1610 eh->eh_ecount = htole16(le16toh(eh->eh_ecount) - 1);
1613 ex->e_blk = htole32(block);
1614 ex->e_len = htole16(num);
1616 ext4_ext_dirty(ip, path + depth);
1618 ex--;
1619 ex_blk = htole32(ex->e_blk);
1623 if (correct_index && le16toh(eh->eh_ecount))
1630 if (error == 0 && eh->eh_ecount == 0 &&
1631 path[depth].ep_data != NULL)
1632 error = ext4_ext_rm_index(ip, path + depth);
1640 int depth, int flags)
1647 fs = ip->i_e2fs;
1648 error = bread(ip->i_devvp, fsbtodb(fs, pblk),
1649 fs->e2fs_bsize, NOCRED, &bp);
1654 eh = ext4_ext_block_header(bp->b_data);
1655 if (le16toh(eh->eh_depth) != depth) {
1661 error = ext4_ext_check_header(ip, eh, depth);
1677 KASSERT(path->ep_index != NULL,
1680 if (path->ep_index < EXT_FIRST_INDEX(path->ep_header))
1683 if (le16toh(path->ep_header->eh_ecount) == path->index_count)
1696 int depth;
1699 ehp = (struct ext4_extent_header *)ip->i_db;
1700 depth = ext4_ext_inode_depth(ip);
1702 error = ext4_ext_check_header(ip, ehp, depth);
1706 path = malloc(sizeof(struct ext4_extent_path) * (depth + 1),
1709 path[0].ep_depth = depth;
1712 if (i == depth) {
1719 i--;
1732 le16toh(path[i].ep_header->eh_ecount) + 1;
1735 path[i].ep_index--;
1742 path[0].ep_depth - (i + 1), 0);
1752 le16toh(path[i].ep_header->eh_ecount);
1755 if (path[i].ep_header->eh_ecount == 0 && i > 0) {
1761 i--;
1765 if (path->ep_header->eh_ecount == 0) {
1769 ext4_ext_header(ip)->eh_depth = 0;
1770 ext4_ext_header(ip)->eh_max = htole16(ext4_ext_space_root(ip));
1777 ip->i_ext_cache.ec_type = EXT4_EXT_CACHE_NO;