184 ext4_ext_print_path(struct inode *ip, struct ext4_extent_path *path)  in ext4_ext_print_path()  argument
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()
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()
495 ext4_ext_binsearch_index(struct ext4_extent_path *path, int blk)  in ext4_ext_binsearch_index()  argument
500 	eh = path->ep_header;  in ext4_ext_binsearch_index()
516 	path->ep_index = l - 1;  in ext4_ext_binsearch_index()
520 ext4_ext_binsearch_ext(struct ext4_extent_path *path, int blk)  in ext4_ext_binsearch_ext()  argument
525 	eh = path->ep_header;  in ext4_ext_binsearch_ext()
544 	path->ep_ext = l - 1;  in ext4_ext_binsearch_ext()
548 ext4_ext_fill_path_bdata(struct ext4_extent_path *path,  in ext4_ext_fill_path_bdata()  argument
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()
563 ext4_ext_fill_path_buf(struct ext4_extent_path *path, struct buf *bp)  in ext4_ext_fill_path_buf()  argument
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()
573 ext4_ext_drop_refs(struct ext4_extent_path *path)  in ext4_ext_drop_refs()  argument
577 	if (!path)  in ext4_ext_drop_refs()
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()
589 ext4_ext_path_free(struct ext4_extent_path *path)  in ext4_ext_path_free()  argument
592 	if (!path)  in ext4_ext_path_free()
595 	ext4_ext_drop_refs(path);  in ext4_ext_path_free()
596 	free(path, M_EXT2EXTENTS);  in ext4_ext_path_free()
604 	struct ext4_extent_path *path;  in ext4_ext_find_extent()  local
621 	path = *ppath;  in ext4_ext_find_extent()
622 	if (path == NULL) {  in ext4_ext_find_extent()
623 		path = malloc(EXT4_EXT_DEPTH_MAX *  in ext4_ext_find_extent()
626 		*ppath = path;  in ext4_ext_find_extent()
630 	path[0].ep_header = eh;  in ext4_ext_find_extent()
631 	path[0].ep_data = NULL;  in ext4_ext_find_extent()
636 		ext4_ext_binsearch_index(&path[ppos], block);  in ext4_ext_find_extent()
637 		blk = ext4_ext_index_pblock(path[ppos].ep_index);  in ext4_ext_find_extent()
638 		path[ppos].ep_depth = i;  in ext4_ext_find_extent()
639 		path[ppos].ep_ext = NULL;  in ext4_ext_find_extent()
656 		ext4_ext_fill_path_bdata(&path[ppos], bp, blk);  in ext4_ext_find_extent()
659 		eh = ext4_ext_block_header(path[ppos].ep_data);  in ext4_ext_find_extent()
661 		    ext2_extent_blk_csum_verify(ip, path[ppos].ep_data)) {  in ext4_ext_find_extent()
666 		path[ppos].ep_header = eh;  in ext4_ext_find_extent()
676 	path[ppos].ep_depth = i;  in ext4_ext_find_extent()
677 	path[ppos].ep_header = eh;  in ext4_ext_find_extent()
678 	path[ppos].ep_ext = NULL;  in ext4_ext_find_extent()
679 	path[ppos].ep_index = NULL;  in ext4_ext_find_extent()
680 	ext4_ext_binsearch_ext(&path[ppos], block);  in ext4_ext_find_extent()
684 	ext4_ext_drop_refs(path);  in ext4_ext_find_extent()
686 		free(path, M_EXT2EXTENTS);  in ext4_ext_find_extent()
737 ext4_ext_blkpref(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_blkpref()  argument
747 	if (path) {  in ext4_ext_blkpref()
748 		depth = path->ep_depth;  in ext4_ext_blkpref()
749 		ex = path[depth].ep_ext;  in ext4_ext_blkpref()
761 		if (path[depth].ep_data)  in ext4_ext_blkpref()
762 			return (path[depth].ep_blk);  in ext4_ext_blkpref()
791 ext4_ext_next_leaf_block(struct inode *ip, struct ext4_extent_path *path)  in ext4_ext_next_leaf_block()  argument
793 	int depth = path->ep_depth;  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()
814 ext4_ext_dirty(struct inode *ip, struct ext4_extent_path *path)  in ext4_ext_dirty()  argument
823 	if (!path)  in ext4_ext_dirty()
826 	if (path->ep_data) {  in ext4_ext_dirty()
827 		blk = path->ep_blk;  in ext4_ext_dirty()
832 		ext4_ext_fill_path_buf(path, bp);  in ext4_ext_dirty()
844 ext4_ext_insert_index(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_insert_index()  argument
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()
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()
886 	return (ext4_ext_dirty(ip, path));  in ext4_ext_insert_index()
924 ext4_ext_split(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_split()  argument
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()
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()
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()
1037 		path[i].ep_index++;  in ext4_ext_split()
1038 		while (path[i].ep_index <= EXT_MAX_INDEX(path[i].ep_header)) {  in ext4_ext_split()
1039 			path[i].ep_index++;  in ext4_ext_split()
1043 			memmove(++fidx, path[i].ep_index - m,  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()
1056 			ext4_ext_dirty(ip, path + i);  in ext4_ext_split()
1062 	error = ext4_ext_insert_index(ip, path + at, border, newblk);  in ext4_ext_split()
1082 ext4_ext_grow_indepth(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_grow_indepth()  argument
1093 	curpath = path;  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()
1134 	neh->eh_depth = htole16(path->ep_depth + 1);  in ext4_ext_grow_indepth()
1143 ext4_ext_create_new_leaf(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_create_new_leaf()  argument
1153 	curpath = path + depth;  in ext4_ext_create_new_leaf()
1164 		error = ext4_ext_split(ip, path, newext, i);  in ext4_ext_create_new_leaf()
1168 		/* Refill path. */  in ext4_ext_create_new_leaf()
1169 		ext4_ext_drop_refs(path);  in ext4_ext_create_new_leaf()
1170 		error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path);  in ext4_ext_create_new_leaf()
1175 		error = ext4_ext_grow_indepth(ip, path, newext);  in ext4_ext_create_new_leaf()
1179 		/* Refill path. */  in ext4_ext_create_new_leaf()
1180 		ext4_ext_drop_refs(path);  in ext4_ext_create_new_leaf()
1181 		error = ext4_ext_find_extent(ip, le32toh(newext->e_blk), &path);  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()
1197 ext4_ext_correct_indexes(struct inode *ip, struct ext4_extent_path *path)  in ext4_ext_correct_indexes()  argument
1205 	eh = path[depth].ep_header;  in ext4_ext_correct_indexes()
1206 	ex = path[depth].ep_ext;  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()
1221 	ext4_ext_dirty(ip, path + k);  in ext4_ext_correct_indexes()
1224 		if (path[k+1].ep_index != EXT_FIRST_INDEX(path[k+1].ep_header))  in ext4_ext_correct_indexes()
1227 		path[k].ep_index->ei_blk = htole32(border);  in ext4_ext_correct_indexes()
1228 		ext4_ext_dirty(ip, path + k);  in ext4_ext_correct_indexes()
1235 ext4_ext_insert_extent(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_insert_extent()  argument
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()
1253 		eh = path[depth].ep_header;  in ext4_ext_insert_extent()
1260 	eh = path[depth].ep_header;  in ext4_ext_insert_extent()
1266 	next = ext4_ext_next_leaf_block(ip, path);  in ext4_ext_insert_extent()
1270 		    ("ext4_ext_insert_extent: bad path"));  in ext4_ext_insert_extent()
1276 		if (npath->ep_depth != path->ep_depth) {  in ext4_ext_insert_extent()
1283 			path = npath;  in ext4_ext_insert_extent()
1292 	error = ext4_ext_create_new_leaf(ip, path, newext);  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()
1311 		path[depth].ep_ext = nearex + 1;  in ext4_ext_insert_extent()
1316 		path[depth].ep_ext = nearex;  in ext4_ext_insert_extent()
1320 	nearex = path[depth].ep_ext;  in ext4_ext_insert_extent()
1350 	error = ext4_ext_correct_indexes(ip, path);  in ext4_ext_insert_extent()
1354 	ext4_ext_dirty(ip, path + depth);  in ext4_ext_insert_extent()
1400 	struct ext4_extent_path *path;  in ext4_ext_get_blocks()  local
1411 	path = NULL;  in ext4_ext_get_blocks()
1425 	error = ext4_ext_find_extent(ip, iblk, &path);  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()
1459 	bpref = ext4_ext_blkpref(ip, path, iblk);  in ext4_ext_get_blocks()
1469 	error = ext4_ext_insert_extent(ip, path, &newex);  in ext4_ext_get_blocks()
1494 	if (path) {  in ext4_ext_get_blocks()
1495 		ext4_ext_drop_refs(path);  in ext4_ext_get_blocks()
1496 		free(path, M_EXT2EXTENTS);  in ext4_ext_get_blocks()
1531 ext4_ext_rm_index(struct inode *ip, struct ext4_extent_path *path)  in ext4_ext_rm_index()  argument
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()
1542 	ext4_ext_dirty(ip, path);  in ext4_ext_rm_index()
1548 ext4_ext_rm_leaf(struct inode *ip, struct ext4_extent_path *path,  in ext4_ext_rm_leaf()  argument
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()
1581 		path[depth].ep_ext = ex;  in ext4_ext_rm_leaf()
1616 		ext4_ext_dirty(ip, path + depth);  in ext4_ext_rm_leaf()
1624 		error = ext4_ext_correct_indexes(ip, path);  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()
1674 ext4_ext_more_to_rm(struct ext4_extent_path *path)  in ext4_ext_more_to_rm()  argument
1677 	KASSERT(path->ep_index != NULL,  in ext4_ext_more_to_rm()
1678 	    ("ext4_ext_more_to_rm: bad index from path"));  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()
1695 	struct ext4_extent_path *path;  in ext4_ext_remove_space()  local
1706 	path = malloc(sizeof(struct ext4_extent_path) * (depth + 1),  in ext4_ext_remove_space()
1708 	path[0].ep_header = ehp;  in ext4_ext_remove_space()
1709 	path[0].ep_depth = depth;  in ext4_ext_remove_space()
1714 			error = ext4_ext_rm_leaf(ip, path, length);  in ext4_ext_remove_space()
1717 			free(path[i].ep_data, M_EXT2EXTENTS);  in ext4_ext_remove_space()
1718 			path[i].ep_data = NULL;  in ext4_ext_remove_space()
1724 		if (!path[i].ep_header)  in ext4_ext_remove_space()
1725 			path[i].ep_header =  in ext4_ext_remove_space()
1726 			    (struct ext4_extent_header *)path[i].ep_data;  in ext4_ext_remove_space()
1728 		if (!path[i].ep_index) {  in ext4_ext_remove_space()
1730 			path[i].ep_index = EXT_LAST_INDEX(path[i].ep_header);  in ext4_ext_remove_space()
1731 			path[i].index_count =  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()
1738 		if (ext4_ext_more_to_rm(path + i)) {  in ext4_ext_remove_space()
1739 			memset(path + i + 1, 0, sizeof(*path));  in ext4_ext_remove_space()
1741 			    ext4_ext_index_pblock(path[i].ep_index),  in ext4_ext_remove_space()
1742 			    path[0].ep_depth - (i + 1), 0);  in ext4_ext_remove_space()
1748 			ext4_ext_fill_path_bdata(&path[i+1], bp,  in ext4_ext_remove_space()
1749 			    ext4_ext_index_pblock(path[i].ep_index));  in ext4_ext_remove_space()
1751 			path[i].index_count =  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()
1757 				error = ext4_ext_rm_index(ip, path + i);  in ext4_ext_remove_space()
1759 			free(path[i].ep_data, M_EXT2EXTENTS);  in ext4_ext_remove_space()
1760 			path[i].ep_data = NULL;  in ext4_ext_remove_space()
1765 	if (path->ep_header->eh_ecount == 0) {  in ext4_ext_remove_space()
1771 		 ext4_ext_dirty(ip, path);  in ext4_ext_remove_space()
1774 	ext4_ext_drop_refs(path);  in ext4_ext_remove_space()
1775 	free(path, M_EXT2EXTENTS);  in ext4_ext_remove_space()