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