47 	struct extent_map *em;  in btrfs_alloc_extent_map()  local
48 	em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);  in btrfs_alloc_extent_map()
49 	if (!em)  in btrfs_alloc_extent_map()
51 	RB_CLEAR_NODE(&em->rb_node);  in btrfs_alloc_extent_map()
52 	refcount_set(&em->refs, 1);  in btrfs_alloc_extent_map()
53 	INIT_LIST_HEAD(&em->list);  in btrfs_alloc_extent_map()
54 	return em;  in btrfs_alloc_extent_map()
58  * Drop the reference out on @em by one and free the structure if the reference
61 void btrfs_free_extent_map(struct extent_map *em)  in btrfs_free_extent_map()  argument
63 	if (!em)  in btrfs_free_extent_map()
65 	if (refcount_dec_and_test(&em->refs)) {  in btrfs_free_extent_map()
66 		WARN_ON(btrfs_extent_map_in_tree(em));  in btrfs_free_extent_map()
67 		WARN_ON(!list_empty(&em->list));  in btrfs_free_extent_map()
68 		kmem_cache_free(extent_map_cache, em);  in btrfs_free_extent_map()
80 static void remove_em(struct btrfs_inode *inode, struct extent_map *em)  in remove_em()  argument
84 	rb_erase(&em->rb_node, &inode->extent_tree.root);  in remove_em()
85 	RB_CLEAR_NODE(&em->rb_node);  in remove_em()
91 static int tree_insert(struct rb_root *root, struct extent_map *em)  in tree_insert()  argument
97 	u64 end = range_end(em->start, em->len);  in tree_insert()
103 		if (em->start < entry->start)  in tree_insert()
105 		else if (em->start >= btrfs_extent_map_end(entry))  in tree_insert()
112 	while (parent && em->start >= btrfs_extent_map_end(entry)) {  in tree_insert()
117 		if (end > entry->start && em->start < btrfs_extent_map_end(entry))  in tree_insert()
122 	while (parent && em->start < entry->start) {  in tree_insert()
127 		if (end > entry->start && em->start < btrfs_extent_map_end(entry))  in tree_insert()
130 	rb_link_node(&em->rb_node, orig_parent, p);  in tree_insert()
131 	rb_insert_color(&em->rb_node, root);  in tree_insert()
189 static inline u64 extent_map_block_len(const struct extent_map *em)  in extent_map_block_len()  argument
191 	if (btrfs_extent_map_is_compressed(em))  in extent_map_block_len()
192 		return em->disk_num_bytes;  in extent_map_block_len()
193 	return em->len;  in extent_map_block_len()
196 static inline u64 extent_map_block_end(const struct extent_map *em)  in extent_map_block_end()  argument
198 	const u64 block_start = btrfs_extent_map_block_start(em);  in extent_map_block_end()
199 	const u64 block_end = block_start + extent_map_block_len(em);  in extent_map_block_end()
207 static bool can_merge_extent_map(const struct extent_map *em)  in can_merge_extent_map()  argument
209 	if (em->flags & EXTENT_FLAG_PINNED)  in can_merge_extent_map()
213 	if (btrfs_extent_map_is_compressed(em))  in can_merge_extent_map()
216 	if (em->flags & EXTENT_FLAG_LOGGING)  in can_merge_extent_map()
224 	if (!list_empty(&em->list))  in can_merge_extent_map()
308 			    struct extent_map *em)  in dump_extent_map()  argument
314 		prefix, em->start, em->len, em->disk_bytenr, em->disk_num_bytes,  in dump_extent_map()
315 		em->ram_bytes, em->offset, em->flags);  in dump_extent_map()
320 static void validate_extent_map(struct btrfs_fs_info *fs_info, struct extent_map *em)  in validate_extent_map()  argument
324 	if (em->disk_bytenr < EXTENT_MAP_LAST_BYTE) {  in validate_extent_map()
325 		if (em->disk_num_bytes == 0)  in validate_extent_map()
326 			dump_extent_map(fs_info, "zero disk_num_bytes", em);  in validate_extent_map()
327 		if (em->offset + em->len > em->ram_bytes)  in validate_extent_map()
328 			dump_extent_map(fs_info, "ram_bytes too small", em);  in validate_extent_map()
329 		if (em->offset + em->len > em->disk_num_bytes &&  in validate_extent_map()
330 		    !btrfs_extent_map_is_compressed(em))  in validate_extent_map()
331 			dump_extent_map(fs_info, "disk_num_bytes too small", em);  in validate_extent_map()
332 		if (!btrfs_extent_map_is_compressed(em) &&  in validate_extent_map()
333 		    em->ram_bytes != em->disk_num_bytes)  in validate_extent_map()
335 		"ram_bytes mismatch with disk_num_bytes for non-compressed em",  in validate_extent_map()
336 					em);  in validate_extent_map()
337 	} else if (em->offset) {  in validate_extent_map()
338 		dump_extent_map(fs_info, "non-zero offset for hole/inline", em);  in validate_extent_map()
342 static void try_merge_map(struct btrfs_inode *inode, struct extent_map *em)  in try_merge_map()  argument
356 	if (refcount_read(&em->refs) > 2)  in try_merge_map()
359 	if (!can_merge_extent_map(em))  in try_merge_map()
362 	if (em->start != 0) {  in try_merge_map()
363 		rb = rb_prev(&em->rb_node);  in try_merge_map()
366 		if (rb && can_merge_extent_map(merge) && mergeable_maps(merge, em)) {  in try_merge_map()
367 			em->start = merge->start;  in try_merge_map()
368 			em->len += merge->len;  in try_merge_map()
369 			em->generation = max(em->generation, merge->generation);  in try_merge_map()
371 			if (em->disk_bytenr < EXTENT_MAP_LAST_BYTE)  in try_merge_map()
372 				merge_ondisk_extents(merge, em, em);  in try_merge_map()
373 			em->flags |= EXTENT_FLAG_MERGED;  in try_merge_map()
375 			validate_extent_map(fs_info, em);  in try_merge_map()
381 	rb = rb_next(&em->rb_node);  in try_merge_map()
384 	if (rb && can_merge_extent_map(merge) && mergeable_maps(em, merge)) {  in try_merge_map()
385 		em->len += merge->len;  in try_merge_map()
386 		if (em->disk_bytenr < EXTENT_MAP_LAST_BYTE)  in try_merge_map()
387 			merge_ondisk_extents(em, merge, em);  in try_merge_map()
388 		validate_extent_map(fs_info, em);  in try_merge_map()
389 		em->generation = max(em->generation, merge->generation);  in try_merge_map()
390 		em->flags |= EXTENT_FLAG_MERGED;  in try_merge_map()
417 	struct extent_map *em;  in btrfs_unpin_extent_cache()  local
420 	em = btrfs_lookup_extent_mapping(tree, start, len);  in btrfs_unpin_extent_cache()
422 	if (WARN_ON(!em)) {  in btrfs_unpin_extent_cache()
431 	if (WARN_ON(em->start != start)) {  in btrfs_unpin_extent_cache()
435 			   em->start, start, start + len, gen);  in btrfs_unpin_extent_cache()
440 	em->generation = gen;  in btrfs_unpin_extent_cache()
441 	em->flags &= ~EXTENT_FLAG_PINNED;  in btrfs_unpin_extent_cache()
443 	try_merge_map(inode, em);  in btrfs_unpin_extent_cache()
447 	btrfs_free_extent_map(em);  in btrfs_unpin_extent_cache()
452 void btrfs_clear_em_logging(struct btrfs_inode *inode, struct extent_map *em)  in btrfs_clear_em_logging()  argument
456 	em->flags &= ~EXTENT_FLAG_LOGGING;  in btrfs_clear_em_logging()
457 	if (btrfs_extent_map_in_tree(em))  in btrfs_clear_em_logging()
458 		try_merge_map(inode, em);  in btrfs_clear_em_logging()
462 					struct extent_map *em,  in setup_extent_mapping()  argument
465 	refcount_inc(&em->refs);  in setup_extent_mapping()
467 	ASSERT(list_empty(&em->list));  in setup_extent_mapping()
470 		list_add(&em->list, &inode->extent_tree.modified_extents);  in setup_extent_mapping()
472 		try_merge_map(inode, em);  in setup_extent_mapping()
479  * @em:		map to insert
480  * @modified:	indicate whether the given @em should be added to the
483  * Insert @em into the @inode's extent map tree or perform a simple
489 			      struct extent_map *em, bool modified)  in add_extent_mapping()  argument
498 	validate_extent_map(fs_info, em);  in add_extent_mapping()
499 	ret = tree_insert(&tree->root, em);  in add_extent_mapping()
503 	setup_extent_mapping(inode, em, modified);  in add_extent_mapping()
514 	struct extent_map *em;  in lookup_extent_mapping()  local
527 	em = rb_entry(rb_node, struct extent_map, rb_node);  in lookup_extent_mapping()
529 	if (strict && !(end > em->start && start < btrfs_extent_map_end(em)))  in lookup_extent_mapping()
532 	refcount_inc(&em->refs);  in lookup_extent_mapping()
533 	return em;  in lookup_extent_mapping()
576  * @em:		extent map being removed
578  * Remove @em from the extent tree of @inode.  No reference counts are dropped,
581 void btrfs_remove_extent_mapping(struct btrfs_inode *inode, struct extent_map *em)  in btrfs_remove_extent_mapping()  argument
587 	WARN_ON(em->flags & EXTENT_FLAG_PINNED);  in btrfs_remove_extent_mapping()
588 	if (!(em->flags & EXTENT_FLAG_LOGGING))  in btrfs_remove_extent_mapping()
589 		list_del_init(&em->list);  in btrfs_remove_extent_mapping()
591 	remove_em(inode, em);  in btrfs_remove_extent_mapping()
616 static struct extent_map *next_extent_map(const struct extent_map *em)  in next_extent_map()  argument
620 	next = rb_next(&em->rb_node);  in next_extent_map()
626 static struct extent_map *prev_extent_map(struct extent_map *em)  in prev_extent_map()  argument
630 	prev = rb_prev(&em->rb_node);  in prev_extent_map()
644 					 struct extent_map *em,  in merge_extent_mapping()  argument
653 	if (map_start < em->start || map_start >= btrfs_extent_map_end(em))  in merge_extent_mapping()
664 	start = prev ? btrfs_extent_map_end(prev) : em->start;  in merge_extent_mapping()
665 	start = max_t(u64, start, em->start);  in merge_extent_mapping()
666 	end = next ? next->start : btrfs_extent_map_end(em);  in merge_extent_mapping()
667 	end = min_t(u64, end, btrfs_extent_map_end(em));  in merge_extent_mapping()
668 	start_diff = start - em->start;  in merge_extent_mapping()
669 	em->start = start;  in merge_extent_mapping()
670 	em->len = end - start;  in merge_extent_mapping()
671 	if (em->disk_bytenr < EXTENT_MAP_LAST_BYTE)  in merge_extent_mapping()
672 		em->offset += start_diff;  in merge_extent_mapping()
673 	return add_extent_mapping(inode, em, false);  in merge_extent_mapping()
690  *    existing em.
700 	struct extent_map *em = *em_in;  in btrfs_add_extent_mapping()  local
707 	if (em->disk_bytenr == EXTENT_MAP_INLINE)  in btrfs_add_extent_mapping()
708 		ASSERT(em->start == 0);  in btrfs_add_extent_mapping()
710 	ret = add_extent_mapping(inode, em, false);  in btrfs_add_extent_mapping()
720 		trace_btrfs_handle_em_exist(fs_info, existing, em, start, len);  in btrfs_add_extent_mapping()
728 			btrfs_free_extent_map(em);  in btrfs_add_extent_mapping()
732 			u64 orig_start = em->start;  in btrfs_add_extent_mapping()
733 			u64 orig_len = em->len;  in btrfs_add_extent_mapping()
739 			ret = merge_extent_mapping(inode, existing, em, start);  in btrfs_add_extent_mapping()
741 				btrfs_free_extent_map(em);  in btrfs_add_extent_mapping()
744 "extent map merge error existing [%llu, %llu) with em [%llu, %llu) start %llu",  in btrfs_add_extent_mapping()
769 		struct extent_map *em;  in drop_all_extent_maps_fast()  local
772 		em = rb_entry(node, struct extent_map, rb_node);  in drop_all_extent_maps_fast()
773 		em->flags &= ~(EXTENT_FLAG_PINNED | EXTENT_FLAG_LOGGING);  in drop_all_extent_maps_fast()
774 		btrfs_remove_extent_mapping(inode, em);  in drop_all_extent_maps_fast()
775 		btrfs_free_extent_map(em);  in drop_all_extent_maps_fast()
804 	struct extent_map *em;  in btrfs_drop_extent_map_range()  local
832 	em = btrfs_lookup_extent_mapping(em_tree, start, len);  in btrfs_drop_extent_map_range()
834 	while (em) {  in btrfs_drop_extent_map_range()
836 		const u64 em_end = btrfs_extent_map_end(em);  in btrfs_drop_extent_map_range()
843 			next_em = next_extent_map(em);  in btrfs_drop_extent_map_range()
852 		if (skip_pinned && (em->flags & EXTENT_FLAG_PINNED)) {  in btrfs_drop_extent_map_range()
857 		flags = em->flags;  in btrfs_drop_extent_map_range()
863 		em->flags &= ~(EXTENT_FLAG_PINNED | EXTENT_FLAG_LOGGING);  in btrfs_drop_extent_map_range()
864 		modified = !list_empty(&em->list);  in btrfs_drop_extent_map_range()
870 		if (em->start >= start && em_end <= end)  in btrfs_drop_extent_map_range()
873 		gen = em->generation;  in btrfs_drop_extent_map_range()
875 		if (em->start < start) {  in btrfs_drop_extent_map_range()
882 			split->start = em->start;  in btrfs_drop_extent_map_range()
883 			split->len = start - em->start;  in btrfs_drop_extent_map_range()
885 			if (em->disk_bytenr < EXTENT_MAP_LAST_BYTE) {  in btrfs_drop_extent_map_range()
886 				split->disk_bytenr = em->disk_bytenr;  in btrfs_drop_extent_map_range()
887 				split->disk_num_bytes = em->disk_num_bytes;  in btrfs_drop_extent_map_range()
888 				split->offset = em->offset;  in btrfs_drop_extent_map_range()
889 				split->ram_bytes = em->ram_bytes;  in btrfs_drop_extent_map_range()
891 				split->disk_bytenr = em->disk_bytenr;  in btrfs_drop_extent_map_range()
899 			replace_extent_mapping(inode, em, split, modified);  in btrfs_drop_extent_map_range()
913 			split->disk_bytenr = em->disk_bytenr;  in btrfs_drop_extent_map_range()
917 			if (em->disk_bytenr < EXTENT_MAP_LAST_BYTE) {  in btrfs_drop_extent_map_range()
918 				split->disk_num_bytes = em->disk_num_bytes;  in btrfs_drop_extent_map_range()
919 				split->offset = em->offset + end - em->start;  in btrfs_drop_extent_map_range()
920 				split->ram_bytes = em->ram_bytes;  in btrfs_drop_extent_map_range()
927 			if (btrfs_extent_map_in_tree(em)) {  in btrfs_drop_extent_map_range()
928 				replace_extent_mapping(inode, em, split, modified);  in btrfs_drop_extent_map_range()
942 		if (btrfs_extent_map_in_tree(em)) {  in btrfs_drop_extent_map_range()
963 			if ((em->start < start || em_end > end) && modified) {  in btrfs_drop_extent_map_range()
967 			btrfs_remove_extent_mapping(inode, em);  in btrfs_drop_extent_map_range()
974 		btrfs_free_extent_map(em);  in btrfs_drop_extent_map_range()
977 		btrfs_free_extent_map(em);  in btrfs_drop_extent_map_range()
979 		em = next_em;  in btrfs_drop_extent_map_range()
1039 	struct extent_map *em;  in btrfs_split_extent_map()  local
1059 	em = btrfs_lookup_extent_mapping(em_tree, start, len);  in btrfs_split_extent_map()
1060 	if (unlikely(!em)) {  in btrfs_split_extent_map()
1065 	ASSERT(em->len == len);  in btrfs_split_extent_map()
1066 	ASSERT(!btrfs_extent_map_is_compressed(em));  in btrfs_split_extent_map()
1067 	ASSERT(em->disk_bytenr < EXTENT_MAP_LAST_BYTE);  in btrfs_split_extent_map()
1068 	ASSERT(em->flags & EXTENT_FLAG_PINNED);  in btrfs_split_extent_map()
1069 	ASSERT(!(em->flags & EXTENT_FLAG_LOGGING));  in btrfs_split_extent_map()
1070 	ASSERT(!list_empty(&em->list));  in btrfs_split_extent_map()
1072 	flags = em->flags;  in btrfs_split_extent_map()
1073 	em->flags &= ~EXTENT_FLAG_PINNED;  in btrfs_split_extent_map()
1075 	/* First, replace the em with a new extent_map starting from * em->start */  in btrfs_split_extent_map()
1076 	split_pre->start = em->start;  in btrfs_split_extent_map()
1083 	split_pre->generation = em->generation;  in btrfs_split_extent_map()
1085 	replace_extent_mapping(inode, em, split_pre, true);  in btrfs_split_extent_map()
1089 	 *     [em->start, em->start + pre]  in btrfs_split_extent_map()
1093 	split_mid->start = em->start + pre;  in btrfs_split_extent_map()
1094 	split_mid->len = em->len - pre;  in btrfs_split_extent_map()
1095 	split_mid->disk_bytenr = btrfs_extent_map_block_start(em) + pre;  in btrfs_split_extent_map()
1100 	split_mid->generation = em->generation;  in btrfs_split_extent_map()
1104 	btrfs_free_extent_map(em);  in btrfs_split_extent_map()
1106 	btrfs_free_extent_map(em);  in btrfs_split_extent_map()
1152 		struct extent_map *em;  in btrfs_scan_inode()  local
1154 		em = rb_entry(node, struct extent_map, rb_node);  in btrfs_scan_inode()
1157 		if (em->flags & EXTENT_FLAG_PINNED)  in btrfs_scan_inode()
1167 		if (!list_empty(&em->list) && em->generation >= cur_fs_gen)  in btrfs_scan_inode()
1170 		btrfs_remove_extent_mapping(inode, em);  in btrfs_scan_inode()
1171 		trace_btrfs_extent_map_shrinker_remove_em(inode, em);  in btrfs_scan_inode()
1173 		btrfs_free_extent_map(em);  in btrfs_scan_inode()