26 	int level = NILFS_BTREE_LEVEL_DATA;  in nilfs_btree_alloc_path()  local
32 	for (; level < NILFS_BTREE_LEVEL_MAX; level++) {  in nilfs_btree_alloc_path()
33 		path[level].bp_bh = NULL;  in nilfs_btree_alloc_path()
34 		path[level].bp_sib_bh = NULL;  in nilfs_btree_alloc_path()
35 		path[level].bp_index = 0;  in nilfs_btree_alloc_path()
36 		path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;  in nilfs_btree_alloc_path()
37 		path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;  in nilfs_btree_alloc_path()
38 		path[level].bp_op = NULL;  in nilfs_btree_alloc_path()
47 	int level = NILFS_BTREE_LEVEL_DATA;  in nilfs_btree_free_path()  local
49 	for (; level < NILFS_BTREE_LEVEL_MAX; level++)  in nilfs_btree_free_path()
50 		brelse(path[level].bp_bh);  in nilfs_btree_free_path()
96 nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)  in nilfs_btree_node_set_level()  argument
98 	node->bn_level = level;  in nilfs_btree_node_set_level()
163 				  int level, int nchildren, int ncmax,  in nilfs_btree_node_init()  argument
171 	nilfs_btree_node_set_level(node, level);  in nilfs_btree_node_init()
343 	int level, flags, nchildren;  in nilfs_btree_node_broken()  local
346 	level = nilfs_btree_node_get_level(node);  in nilfs_btree_node_broken()
350 	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||  in nilfs_btree_node_broken()
351 		     level >= NILFS_BTREE_LEVEL_MAX ||  in nilfs_btree_node_broken()
356 			   "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",  in nilfs_btree_node_broken()
357 			   inode->i_ino, (unsigned long long)blocknr, level,  in nilfs_btree_node_broken()
374 	int level, flags, nchildren;  in nilfs_btree_root_broken()  local
377 	level = nilfs_btree_node_get_level(node);  in nilfs_btree_root_broken()
381 	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||  in nilfs_btree_root_broken()
382 		     level >= NILFS_BTREE_LEVEL_MAX ||  in nilfs_btree_root_broken()
385 		     (nchildren == 0 && level > NILFS_BTREE_LEVEL_NODE_MIN))) {  in nilfs_btree_root_broken()
387 			   "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",  in nilfs_btree_root_broken()
388 			   inode->i_ino, level, flags, nchildren);  in nilfs_btree_root_broken()
417 nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)  in nilfs_btree_get_nonroot_node()  argument
419 	return (struct nilfs_btree_node *)path[level].bp_bh->b_data;  in nilfs_btree_get_nonroot_node()
423 nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)  in nilfs_btree_get_sib_node()  argument
425 	return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;  in nilfs_btree_get_sib_node()
436 		     int level, int *ncmaxp)  in nilfs_btree_get_node()  argument
440 	if (level == nilfs_btree_height(btree) - 1) {  in nilfs_btree_get_node()
444 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_get_node()
451 				struct nilfs_btree_node *node, int level)  in nilfs_btree_bad_node()  argument
453 	if (unlikely(nilfs_btree_node_get_level(node) != level)) {  in nilfs_btree_bad_node()
456 			   "btree level mismatch (ino=%lu): %d != %d",  in nilfs_btree_bad_node()
458 			   nilfs_btree_node_get_level(node), level);  in nilfs_btree_bad_node()
555 	int level, index, found, ncmax, ret;  in nilfs_btree_do_lookup()  local
558 	level = nilfs_btree_node_get_level(node);  in nilfs_btree_do_lookup()
559 	if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)  in nilfs_btree_do_lookup()
565 	path[level].bp_bh = NULL;  in nilfs_btree_do_lookup()
566 	path[level].bp_index = index;  in nilfs_btree_do_lookup()
570 	while (--level >= minlevel) {  in nilfs_btree_do_lookup()
572 		if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {  in nilfs_btree_do_lookup()
573 			p.node = nilfs_btree_get_node(btree, path, level + 1,  in nilfs_btree_do_lookup()
579 		ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,  in nilfs_btree_do_lookup()
584 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_do_lookup()
585 		if (nilfs_btree_bad_node(btree, node, level))  in nilfs_btree_do_lookup()
594 			WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);  in nilfs_btree_do_lookup()
598 		path[level].bp_index = index;  in nilfs_btree_do_lookup()
615 	int index, level, ncmax, ret;  in nilfs_btree_do_lookup_last()  local
621 	level = nilfs_btree_node_get_level(node);  in nilfs_btree_do_lookup_last()
624 	path[level].bp_bh = NULL;  in nilfs_btree_do_lookup_last()
625 	path[level].bp_index = index;  in nilfs_btree_do_lookup_last()
628 	for (level--; level > 0; level--) {  in nilfs_btree_do_lookup_last()
629 		ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);  in nilfs_btree_do_lookup_last()
632 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_do_lookup_last()
633 		if (nilfs_btree_bad_node(btree, node, level))  in nilfs_btree_do_lookup_last()
637 		path[level].bp_index = index;  in nilfs_btree_do_lookup_last()
652  * @minlevel: start level
663 	int index, next_adj, level;  in nilfs_btree_get_next_key()  local
667 	for (level = minlevel; level <= maxlevel; level++) {  in nilfs_btree_get_next_key()
668 		if (level == maxlevel)  in nilfs_btree_get_next_key()
671 			node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_get_next_key()
673 		index = path[level].bp_index + next_adj;  in nilfs_btree_get_next_key()
686 			      __u64 key, int level, __u64 *ptrp)  in nilfs_btree_lookup()  argument
695 	ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);  in nilfs_btree_lookup()
711 	int level = NILFS_BTREE_LEVEL_NODE_MIN;  in nilfs_btree_lookup_contig()  local
719 	ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);  in nilfs_btree_lookup_contig()
735 	node = nilfs_btree_get_node(btree, path, level, &ncmax);  in nilfs_btree_lookup_contig()
736 	index = path[level].bp_index + 1;  in nilfs_btree_lookup_contig()
753 		if (level == maxlevel)  in nilfs_btree_lookup_contig()
757 		p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);  in nilfs_btree_lookup_contig()
758 		p.index = path[level + 1].bp_index + 1;  in nilfs_btree_lookup_contig()
764 		path[level + 1].bp_index = p.index;  in nilfs_btree_lookup_contig()
766 		brelse(path[level].bp_bh);  in nilfs_btree_lookup_contig()
767 		path[level].bp_bh = NULL;  in nilfs_btree_lookup_contig()
769 		ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,  in nilfs_btree_lookup_contig()
773 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_lookup_contig()
776 		path[level].bp_index = index;  in nilfs_btree_lookup_contig()
793 				    int level, __u64 key)  in nilfs_btree_promote_key()  argument
795 	if (level < nilfs_btree_height(btree) - 1) {  in nilfs_btree_promote_key()
798 				nilfs_btree_get_nonroot_node(path, level),  in nilfs_btree_promote_key()
799 				path[level].bp_index, key);  in nilfs_btree_promote_key()
800 			if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_promote_key()
801 				mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_promote_key()
802 		} while ((path[level].bp_index == 0) &&  in nilfs_btree_promote_key()
803 			 (++level < nilfs_btree_height(btree) - 1));  in nilfs_btree_promote_key()
807 	if (level == nilfs_btree_height(btree) - 1) {  in nilfs_btree_promote_key()
809 					 path[level].bp_index, key);  in nilfs_btree_promote_key()
815 				  int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_do_insert()  argument
820 	if (level < nilfs_btree_height(btree) - 1) {  in nilfs_btree_do_insert()
821 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_do_insert()
823 		nilfs_btree_node_insert(node, path[level].bp_index,  in nilfs_btree_do_insert()
825 		if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_do_insert()
826 			mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_do_insert()
828 		if (path[level].bp_index == 0)  in nilfs_btree_do_insert()
829 			nilfs_btree_promote_key(btree, path, level + 1,  in nilfs_btree_do_insert()
834 		nilfs_btree_node_insert(node, path[level].bp_index,  in nilfs_btree_do_insert()
842 				   int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_carry_left()  argument
847 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_carry_left()
848 	left = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_carry_left()
855 	if (n > path[level].bp_index) {  in nilfs_btree_carry_left()
863 	if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_carry_left()
864 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_carry_left()
865 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_carry_left()
866 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_carry_left()
868 	nilfs_btree_promote_key(btree, path, level + 1,  in nilfs_btree_carry_left()
872 		brelse(path[level].bp_bh);  in nilfs_btree_carry_left()
873 		path[level].bp_bh = path[level].bp_sib_bh;  in nilfs_btree_carry_left()
874 		path[level].bp_sib_bh = NULL;  in nilfs_btree_carry_left()
875 		path[level].bp_index += lnchildren;  in nilfs_btree_carry_left()
876 		path[level + 1].bp_index--;  in nilfs_btree_carry_left()
878 		brelse(path[level].bp_sib_bh);  in nilfs_btree_carry_left()
879 		path[level].bp_sib_bh = NULL;  in nilfs_btree_carry_left()
880 		path[level].bp_index -= n;  in nilfs_btree_carry_left()
883 	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);  in nilfs_btree_carry_left()
888 				    int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_carry_right()  argument
893 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_carry_right()
894 	right = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_carry_right()
901 	if (n > nchildren - path[level].bp_index) {  in nilfs_btree_carry_right()
909 	if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_carry_right()
910 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_carry_right()
911 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_carry_right()
912 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_carry_right()
914 	path[level + 1].bp_index++;  in nilfs_btree_carry_right()
915 	nilfs_btree_promote_key(btree, path, level + 1,  in nilfs_btree_carry_right()
917 	path[level + 1].bp_index--;  in nilfs_btree_carry_right()
920 		brelse(path[level].bp_bh);  in nilfs_btree_carry_right()
921 		path[level].bp_bh = path[level].bp_sib_bh;  in nilfs_btree_carry_right()
922 		path[level].bp_sib_bh = NULL;  in nilfs_btree_carry_right()
923 		path[level].bp_index -= nilfs_btree_node_get_nchildren(node);  in nilfs_btree_carry_right()
924 		path[level + 1].bp_index++;  in nilfs_btree_carry_right()
926 		brelse(path[level].bp_sib_bh);  in nilfs_btree_carry_right()
927 		path[level].bp_sib_bh = NULL;  in nilfs_btree_carry_right()
930 	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);  in nilfs_btree_carry_right()
935 			      int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_split()  argument
940 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_split()
941 	right = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_split()
947 	if (n > nchildren - path[level].bp_index) {  in nilfs_btree_split()
954 	if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_split()
955 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_split()
956 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_split()
957 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_split()
960 		path[level].bp_index -= nilfs_btree_node_get_nchildren(node);  in nilfs_btree_split()
961 		nilfs_btree_node_insert(right, path[level].bp_index,  in nilfs_btree_split()
965 		*ptrp = path[level].bp_newreq.bpr_ptr;  in nilfs_btree_split()
967 		brelse(path[level].bp_bh);  in nilfs_btree_split()
968 		path[level].bp_bh = path[level].bp_sib_bh;  in nilfs_btree_split()
969 		path[level].bp_sib_bh = NULL;  in nilfs_btree_split()
971 		nilfs_btree_do_insert(btree, path, level, keyp, ptrp);  in nilfs_btree_split()
974 		*ptrp = path[level].bp_newreq.bpr_ptr;  in nilfs_btree_split()
976 		brelse(path[level].bp_sib_bh);  in nilfs_btree_split()
977 		path[level].bp_sib_bh = NULL;  in nilfs_btree_split()
980 	path[level + 1].bp_index++;  in nilfs_btree_split()
985 			     int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_grow()  argument
991 	child = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_grow()
998 	nilfs_btree_node_set_level(root, level + 1);  in nilfs_btree_grow()
1000 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_grow()
1001 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_grow()
1003 	path[level].bp_bh = path[level].bp_sib_bh;  in nilfs_btree_grow()
1004 	path[level].bp_sib_bh = NULL;  in nilfs_btree_grow()
1006 	nilfs_btree_do_insert(btree, path, level, keyp, ptrp);  in nilfs_btree_grow()
1009 	*ptrp = path[level].bp_newreq.bpr_ptr;  in nilfs_btree_grow()
1016 	int level, ncmax;  in nilfs_btree_find_near()  local
1022 	level = NILFS_BTREE_LEVEL_NODE_MIN;  in nilfs_btree_find_near()
1023 	if (path[level].bp_index > 0) {  in nilfs_btree_find_near()
1024 		node = nilfs_btree_get_node(btree, path, level, &ncmax);  in nilfs_btree_find_near()
1026 						path[level].bp_index - 1,  in nilfs_btree_find_near()
1031 	level = NILFS_BTREE_LEVEL_NODE_MIN + 1;  in nilfs_btree_find_near()
1032 	if (level <= nilfs_btree_height(btree) - 1) {  in nilfs_btree_find_near()
1033 		node = nilfs_btree_get_node(btree, path, level, &ncmax);  in nilfs_btree_find_near()
1034 		return nilfs_btree_node_get_ptr(node, path[level].bp_index,  in nilfs_btree_find_near()
1069 	int pindex, level, ncmax, ncblk, ret;  in nilfs_btree_prepare_insert()  local
1073 	level = NILFS_BTREE_LEVEL_DATA;  in nilfs_btree_prepare_insert()
1077 		path[level].bp_newreq.bpr_ptr =  in nilfs_btree_prepare_insert()
1082 	ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);  in nilfs_btree_prepare_insert()
1088 	for (level = NILFS_BTREE_LEVEL_NODE_MIN;  in nilfs_btree_prepare_insert()
1089 	     level < nilfs_btree_height(btree) - 1;  in nilfs_btree_prepare_insert()
1090 	     level++) {  in nilfs_btree_prepare_insert()
1091 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_prepare_insert()
1093 			path[level].bp_op = nilfs_btree_do_insert;  in nilfs_btree_prepare_insert()
1098 		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_prepare_insert()
1099 		pindex = path[level + 1].bp_index;  in nilfs_btree_prepare_insert()
1110 				path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_insert()
1111 				path[level].bp_op = nilfs_btree_carry_left;  in nilfs_btree_prepare_insert()
1128 				path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_insert()
1129 				path[level].bp_op = nilfs_btree_carry_right;  in nilfs_btree_prepare_insert()
1138 		path[level].bp_newreq.bpr_ptr =  in nilfs_btree_prepare_insert()
1139 			path[level - 1].bp_newreq.bpr_ptr + 1;  in nilfs_btree_prepare_insert()
1141 						   &path[level].bp_newreq, dat);  in nilfs_btree_prepare_insert()
1145 						path[level].bp_newreq.bpr_ptr,  in nilfs_btree_prepare_insert()
1153 		nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);  in nilfs_btree_prepare_insert()
1154 		path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_insert()
1155 		path[level].bp_op = nilfs_btree_split;  in nilfs_btree_prepare_insert()
1162 		path[level].bp_op = nilfs_btree_do_insert;  in nilfs_btree_prepare_insert()
1168 	path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;  in nilfs_btree_prepare_insert()
1169 	ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);  in nilfs_btree_prepare_insert()
1172 	ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,  in nilfs_btree_prepare_insert()
1178 			      0, level, 0, ncblk, NULL, NULL);  in nilfs_btree_prepare_insert()
1179 	path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_insert()
1180 	path[level].bp_op = nilfs_btree_grow;  in nilfs_btree_prepare_insert()
1182 	level++;  in nilfs_btree_prepare_insert()
1183 	path[level].bp_op = nilfs_btree_do_insert;  in nilfs_btree_prepare_insert()
1190 	*levelp = level;  in nilfs_btree_prepare_insert()
1195 	nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);  in nilfs_btree_prepare_insert()
1197 	for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {  in nilfs_btree_prepare_insert()
1198 		nilfs_btnode_delete(path[level].bp_sib_bh);  in nilfs_btree_prepare_insert()
1199 		nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);  in nilfs_btree_prepare_insert()
1203 	nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);  in nilfs_btree_prepare_insert()
1205 	*levelp = level;  in nilfs_btree_prepare_insert()
1215 	int level;  in nilfs_btree_commit_insert()  local
1224 	for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {  in nilfs_btree_commit_insert()
1226 					    &path[level - 1].bp_newreq, dat);  in nilfs_btree_commit_insert()
1227 		path[level].bp_op(btree, path, level, &key, &ptr);  in nilfs_btree_commit_insert()
1238 	int level, ret;  in nilfs_btree_insert()  local
1252 	ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);  in nilfs_btree_insert()
1255 	nilfs_btree_commit_insert(btree, path, level, key, ptr);  in nilfs_btree_insert()
1265 				  int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_do_delete()  argument
1270 	if (level < nilfs_btree_height(btree) - 1) {  in nilfs_btree_do_delete()
1271 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_do_delete()
1273 		nilfs_btree_node_delete(node, path[level].bp_index,  in nilfs_btree_do_delete()
1275 		if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_do_delete()
1276 			mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_do_delete()
1277 		if (path[level].bp_index == 0)  in nilfs_btree_do_delete()
1278 			nilfs_btree_promote_key(btree, path, level + 1,  in nilfs_btree_do_delete()
1282 		nilfs_btree_node_delete(node, path[level].bp_index,  in nilfs_btree_do_delete()
1290 				    int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_borrow_left()  argument
1295 	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);  in nilfs_btree_borrow_left()
1297 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_borrow_left()
1298 	left = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_borrow_left()
1307 	if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_borrow_left()
1308 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_borrow_left()
1309 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_borrow_left()
1310 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_borrow_left()
1312 	nilfs_btree_promote_key(btree, path, level + 1,  in nilfs_btree_borrow_left()
1315 	brelse(path[level].bp_sib_bh);  in nilfs_btree_borrow_left()
1316 	path[level].bp_sib_bh = NULL;  in nilfs_btree_borrow_left()
1317 	path[level].bp_index += n;  in nilfs_btree_borrow_left()
1322 				     int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_borrow_right()  argument
1327 	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);  in nilfs_btree_borrow_right()
1329 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_borrow_right()
1330 	right = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_borrow_right()
1339 	if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_borrow_right()
1340 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_borrow_right()
1341 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_borrow_right()
1342 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_borrow_right()
1344 	path[level + 1].bp_index++;  in nilfs_btree_borrow_right()
1345 	nilfs_btree_promote_key(btree, path, level + 1,  in nilfs_btree_borrow_right()
1347 	path[level + 1].bp_index--;  in nilfs_btree_borrow_right()
1349 	brelse(path[level].bp_sib_bh);  in nilfs_btree_borrow_right()
1350 	path[level].bp_sib_bh = NULL;  in nilfs_btree_borrow_right()
1355 				    int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_concat_left()  argument
1360 	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);  in nilfs_btree_concat_left()
1362 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_concat_left()
1363 	left = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_concat_left()
1370 	if (!buffer_dirty(path[level].bp_sib_bh))  in nilfs_btree_concat_left()
1371 		mark_buffer_dirty(path[level].bp_sib_bh);  in nilfs_btree_concat_left()
1373 	nilfs_btnode_delete(path[level].bp_bh);  in nilfs_btree_concat_left()
1374 	path[level].bp_bh = path[level].bp_sib_bh;  in nilfs_btree_concat_left()
1375 	path[level].bp_sib_bh = NULL;  in nilfs_btree_concat_left()
1376 	path[level].bp_index += nilfs_btree_node_get_nchildren(left);  in nilfs_btree_concat_left()
1381 				     int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_concat_right()  argument
1386 	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);  in nilfs_btree_concat_right()
1388 	node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_concat_right()
1389 	right = nilfs_btree_get_sib_node(path, level);  in nilfs_btree_concat_right()
1396 	if (!buffer_dirty(path[level].bp_bh))  in nilfs_btree_concat_right()
1397 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_concat_right()
1399 	nilfs_btnode_delete(path[level].bp_sib_bh);  in nilfs_btree_concat_right()
1400 	path[level].bp_sib_bh = NULL;  in nilfs_btree_concat_right()
1401 	path[level + 1].bp_index++;  in nilfs_btree_concat_right()
1406 			       int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_shrink()  argument
1411 	nilfs_btree_do_delete(btree, path, level, keyp, ptrp);  in nilfs_btree_shrink()
1414 	child = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_shrink()
1419 	nilfs_btree_node_set_level(root, level);  in nilfs_btree_shrink()
1424 	nilfs_btnode_delete(path[level].bp_bh);  in nilfs_btree_shrink()
1425 	path[level].bp_bh = NULL;  in nilfs_btree_shrink()
1430 			    int level, __u64 *keyp, __u64 *ptrp)  in nilfs_btree_nop()  argument
1443 	int pindex, dindex, level, ncmin, ncmax, ncblk, ret;  in nilfs_btree_prepare_delete()  local
1450 	for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;  in nilfs_btree_prepare_delete()
1451 	     level < nilfs_btree_height(btree) - 1;  in nilfs_btree_prepare_delete()
1452 	     level++) {  in nilfs_btree_prepare_delete()
1453 		node = nilfs_btree_get_nonroot_node(path, level);  in nilfs_btree_prepare_delete()
1454 		path[level].bp_oldreq.bpr_ptr =  in nilfs_btree_prepare_delete()
1457 						 &path[level].bp_oldreq, dat);  in nilfs_btree_prepare_delete()
1462 			path[level].bp_op = nilfs_btree_do_delete;  in nilfs_btree_prepare_delete()
1467 		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_prepare_delete()
1468 		pindex = path[level + 1].bp_index;  in nilfs_btree_prepare_delete()
1480 				path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_delete()
1481 				path[level].bp_op = nilfs_btree_borrow_left;  in nilfs_btree_prepare_delete()
1485 				path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_delete()
1486 				path[level].bp_op = nilfs_btree_concat_left;  in nilfs_btree_prepare_delete()
1500 				path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_delete()
1501 				path[level].bp_op = nilfs_btree_borrow_right;  in nilfs_btree_prepare_delete()
1505 				path[level].bp_sib_bh = bh;  in nilfs_btree_prepare_delete()
1506 				path[level].bp_op = nilfs_btree_concat_right;  in nilfs_btree_prepare_delete()
1521 			WARN_ON(level != nilfs_btree_height(btree) - 2);  in nilfs_btree_prepare_delete()
1524 				path[level].bp_op = nilfs_btree_shrink;  in nilfs_btree_prepare_delete()
1526 				level++;  in nilfs_btree_prepare_delete()
1527 				path[level].bp_op = nilfs_btree_nop;  in nilfs_btree_prepare_delete()
1530 				path[level].bp_op = nilfs_btree_do_delete;  in nilfs_btree_prepare_delete()
1538 	path[level].bp_op = nilfs_btree_do_delete;  in nilfs_btree_prepare_delete()
1543 	path[level].bp_oldreq.bpr_ptr =  in nilfs_btree_prepare_delete()
1547 	ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);  in nilfs_btree_prepare_delete()
1553 	*levelp = level;  in nilfs_btree_prepare_delete()
1558 	nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);  in nilfs_btree_prepare_delete()
1560 	for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {  in nilfs_btree_prepare_delete()
1561 		brelse(path[level].bp_sib_bh);  in nilfs_btree_prepare_delete()
1562 		nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);  in nilfs_btree_prepare_delete()
1564 	*levelp = level;  in nilfs_btree_prepare_delete()
1573 	int level;  in nilfs_btree_commit_delete()  local
1575 	for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {  in nilfs_btree_commit_delete()
1576 		nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);  in nilfs_btree_commit_delete()
1577 		path[level].bp_op(btree, path, level, NULL, NULL);  in nilfs_btree_commit_delete()
1590 	int level, ret;  in nilfs_btree_delete()  local
1604 	ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);  in nilfs_btree_delete()
1607 	nilfs_btree_commit_delete(btree, path, level, dat);  in nilfs_btree_delete()
1826 		/* create child node at level 1 */  in nilfs_btree_commit_convert_and_insert()
1838 		/* create root node at level 2 */  in nilfs_btree_commit_convert_and_insert()
1847 		/* create root node at level 1 */  in nilfs_btree_commit_convert_and_insert()
1914 				   int level,  in nilfs_btree_propagate_p()  argument
1917 	while ((++level < nilfs_btree_height(btree) - 1) &&  in nilfs_btree_propagate_p()
1918 	       !buffer_dirty(path[level].bp_bh))  in nilfs_btree_propagate_p()
1919 		mark_buffer_dirty(path[level].bp_bh);  in nilfs_btree_propagate_p()
1926 					int level, struct inode *dat)  in nilfs_btree_prepare_update_v()  argument
1931 	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_prepare_update_v()
1932 	path[level].bp_oldreq.bpr_ptr =  in nilfs_btree_prepare_update_v()
1933 		nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,  in nilfs_btree_prepare_update_v()
1935 	path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;  in nilfs_btree_prepare_update_v()
1936 	ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,  in nilfs_btree_prepare_update_v()
1937 				       &path[level].bp_newreq.bpr_req);  in nilfs_btree_prepare_update_v()
1941 	if (buffer_nilfs_node(path[level].bp_bh)) {  in nilfs_btree_prepare_update_v()
1942 		path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;  in nilfs_btree_prepare_update_v()
1943 		path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;  in nilfs_btree_prepare_update_v()
1944 		path[level].bp_ctxt.bh = path[level].bp_bh;  in nilfs_btree_prepare_update_v()
1947 			&path[level].bp_ctxt);  in nilfs_btree_prepare_update_v()
1950 					       &path[level].bp_oldreq.bpr_req,  in nilfs_btree_prepare_update_v()
1951 					       &path[level].bp_newreq.bpr_req);  in nilfs_btree_prepare_update_v()
1961 					int level, struct inode *dat)  in nilfs_btree_commit_update_v()  argument
1966 	nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,  in nilfs_btree_commit_update_v()
1967 				&path[level].bp_newreq.bpr_req,  in nilfs_btree_commit_update_v()
1970 	if (buffer_nilfs_node(path[level].bp_bh)) {  in nilfs_btree_commit_update_v()
1973 			&path[level].bp_ctxt);  in nilfs_btree_commit_update_v()
1974 		path[level].bp_bh = path[level].bp_ctxt.bh;  in nilfs_btree_commit_update_v()
1976 	set_buffer_nilfs_volatile(path[level].bp_bh);  in nilfs_btree_commit_update_v()
1978 	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_commit_update_v()
1979 	nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,  in nilfs_btree_commit_update_v()
1980 				 path[level].bp_newreq.bpr_ptr, ncmax);  in nilfs_btree_commit_update_v()
1985 				       int level, struct inode *dat)  in nilfs_btree_abort_update_v()  argument
1987 	nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,  in nilfs_btree_abort_update_v()
1988 			       &path[level].bp_newreq.bpr_req);  in nilfs_btree_abort_update_v()
1989 	if (buffer_nilfs_node(path[level].bp_bh))  in nilfs_btree_abort_update_v()
1992 			&path[level].bp_ctxt);  in nilfs_btree_abort_update_v()
2000 	int level, ret;  in nilfs_btree_prepare_propagate_v()  local
2002 	level = minlevel;  in nilfs_btree_prepare_propagate_v()
2003 	if (!buffer_nilfs_volatile(path[level].bp_bh)) {  in nilfs_btree_prepare_propagate_v()
2004 		ret = nilfs_btree_prepare_update_v(btree, path, level, dat);  in nilfs_btree_prepare_propagate_v()
2008 	while ((++level < nilfs_btree_height(btree) - 1) &&  in nilfs_btree_prepare_propagate_v()
2009 	       !buffer_dirty(path[level].bp_bh)) {  in nilfs_btree_prepare_propagate_v()
2011 		WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));  in nilfs_btree_prepare_propagate_v()
2012 		ret = nilfs_btree_prepare_update_v(btree, path, level, dat);  in nilfs_btree_prepare_propagate_v()
2018 	*maxlevelp = level - 1;  in nilfs_btree_prepare_propagate_v()
2023 	while (--level > minlevel)  in nilfs_btree_prepare_propagate_v()
2024 		nilfs_btree_abort_update_v(btree, path, level, dat);  in nilfs_btree_prepare_propagate_v()
2025 	if (!buffer_nilfs_volatile(path[level].bp_bh))  in nilfs_btree_prepare_propagate_v()
2026 		nilfs_btree_abort_update_v(btree, path, level, dat);  in nilfs_btree_prepare_propagate_v()
2036 	int level;  in nilfs_btree_commit_propagate_v()  local
2041 	for (level = minlevel + 1; level <= maxlevel; level++)  in nilfs_btree_commit_propagate_v()
2042 		nilfs_btree_commit_update_v(btree, path, level, dat);  in nilfs_btree_commit_propagate_v()
2047 				   int level, struct buffer_head *bh)  in nilfs_btree_propagate_v()  argument
2056 	path[level].bp_bh = bh;  in nilfs_btree_propagate_v()
2057 	ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,  in nilfs_btree_propagate_v()
2062 	if (buffer_nilfs_volatile(path[level].bp_bh)) {  in nilfs_btree_propagate_v()
2063 		parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_propagate_v()
2065 					       path[level + 1].bp_index,  in nilfs_btree_propagate_v()
2072 	nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);  in nilfs_btree_propagate_v()
2075 	brelse(path[level].bp_bh);  in nilfs_btree_propagate_v()
2076 	path[level].bp_bh = NULL;  in nilfs_btree_propagate_v()
2086 	int level, ret;  in nilfs_btree_propagate()  local
2097 		level = nilfs_btree_node_get_level(node);  in nilfs_btree_propagate()
2100 		level = NILFS_BTREE_LEVEL_DATA;  in nilfs_btree_propagate()
2103 	ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);  in nilfs_btree_propagate()
2107 				   "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d",  in nilfs_btree_propagate()
2109 				   (unsigned long long)key, level);  in nilfs_btree_propagate()
2114 		nilfs_btree_propagate_v(btree, path, level, bh) :  in nilfs_btree_propagate()
2115 		nilfs_btree_propagate_p(btree, path, level, bh);  in nilfs_btree_propagate()
2137 	int level;  in nilfs_btree_add_dirty_buffer()  local
2142 	level = nilfs_btree_node_get_level(node);  in nilfs_btree_add_dirty_buffer()
2143 	if (level < NILFS_BTREE_LEVEL_NODE_MIN ||  in nilfs_btree_add_dirty_buffer()
2144 	    level >= NILFS_BTREE_LEVEL_MAX) {  in nilfs_btree_add_dirty_buffer()
2147 			   "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",  in nilfs_btree_add_dirty_buffer()
2148 			   level, (unsigned long long)key,  in nilfs_btree_add_dirty_buffer()
2154 	list_for_each(head, &lists[level]) {  in nilfs_btree_add_dirty_buffer()
2173 	int level, i;  in nilfs_btree_lookup_dirty_buffers()  local
2175 	for (level = NILFS_BTREE_LEVEL_NODE_MIN;  in nilfs_btree_lookup_dirty_buffers()
2176 	     level < NILFS_BTREE_LEVEL_MAX;  in nilfs_btree_lookup_dirty_buffers()
2177 	     level++)  in nilfs_btree_lookup_dirty_buffers()
2178 		INIT_LIST_HEAD(&lists[level]);  in nilfs_btree_lookup_dirty_buffers()
2196 	for (level = NILFS_BTREE_LEVEL_NODE_MIN;  in nilfs_btree_lookup_dirty_buffers()
2197 	     level < NILFS_BTREE_LEVEL_MAX;  in nilfs_btree_lookup_dirty_buffers()
2198 	     level++)  in nilfs_btree_lookup_dirty_buffers()
2199 		list_splice_tail(&lists[level], listp);  in nilfs_btree_lookup_dirty_buffers()
2204 				int level,  in nilfs_btree_assign_p()  argument
2214 	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_assign_p()
2215 	ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,  in nilfs_btree_assign_p()
2218 		path[level].bp_ctxt.oldkey = ptr;  in nilfs_btree_assign_p()
2219 		path[level].bp_ctxt.newkey = blocknr;  in nilfs_btree_assign_p()
2220 		path[level].bp_ctxt.bh = *bh;  in nilfs_btree_assign_p()
2223 			&path[level].bp_ctxt);  in nilfs_btree_assign_p()
2228 			&path[level].bp_ctxt);  in nilfs_btree_assign_p()
2229 		*bh = path[level].bp_ctxt.bh;  in nilfs_btree_assign_p()
2232 	nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,  in nilfs_btree_assign_p()
2235 	key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);  in nilfs_btree_assign_p()
2238 	binfo->bi_dat.bi_level = level;  in nilfs_btree_assign_p()
2246 				int level,  in nilfs_btree_assign_v()  argument
2258 	parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);  in nilfs_btree_assign_v()
2259 	ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,  in nilfs_btree_assign_v()
2267 	key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);  in nilfs_btree_assign_v()
2283 	int level, ret;  in nilfs_btree_assign()  local
2292 		level = nilfs_btree_node_get_level(node);  in nilfs_btree_assign()
2295 		level = NILFS_BTREE_LEVEL_DATA;  in nilfs_btree_assign()
2298 	ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);  in nilfs_btree_assign()
2305 		nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :  in nilfs_btree_assign()
2306 		nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);  in nilfs_btree_assign()
2341 static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)  in nilfs_btree_mark()  argument
2352 	ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);  in nilfs_btree_mark()