1 // SPDX-License-Identifier: GPL-2.0
3  * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
18 #include <linux/backing-dev.h>
25  *   - test ext4_ext_search_left() and ext4_ext_search_right()
26  *   - search for metadata in few groups
29  *   - normalization should take into account whether file is still open
30  *   - discard preallocations if no free space left (policy?)
31  *   - don't normalize tails
32  *   - quota
33  *   - reservation for superuser
36  *   - bitmap read-ahead (proposed by Oleg Drokin aka green)
37  *   - track min/max extents in each group for better group selection
38  *   - mb_mark_used() may allocate chunk right after splitting buddy
39  *   - tree of groups sorted by number of free blocks
40  *   - error handling
51  * is larger. If the size is less than sbi->s_mb_stream_request we
61  * ext4_inode_info->i_prealloc_list, which contains list of prealloc
65  * pa_lstart -> the logical start block for this prealloc space
66  * pa_pstart -> the physical start block for this prealloc space
67  * pa_len    -> length for this prealloc space (in clusters)
68  * pa_free   ->  free space available in this prealloc space (in clusters)
80  * have the group allocation flag set then we look at the locality group
85  * The reason for having a per cpu locality group is to reduce the contention
88  * The locality group prealloc space is used looking at whether we have
91  * If we can't allocate blocks via inode prealloc or/and locality group
123  * sbi->s_mb_group_prealloc.  The default value of s_mb_group_prealloc is
124  * dependent on the cluster size; for non-bigalloc file systems, it is
127  * terms of number of blocks. If we have mounted the file system with -O
129  * smallest multiple of the stripe value (sbi->s_stripe) which is
135  * 1) Array of largest free order lists (sbi->s_mb_largest_free_orders)
137  *    Locking: sbi->s_mb_largest_free_orders_locks(array of rw locks)
142  *    number of buddy bitmap orders possible) number of lists. Group-infos are
145  * 2) Average fragment size lists (sbi->s_mb_avg_fragment_size)
147  *    Locking: sbi->s_mb_avg_fragment_size_locks(array of rw locks)
149  *    This is an array of lists where in the i-th list there are groups with
151  *    is computed as ext4_group_info->bb_free / ext4_group_info->bb_fragments.
193  * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
196  * stripe size (sbi->s_stripe), we try to search for contiguous block in
198  * not, we search in the specific group using bitmap for best extents. The
211  * non-linear fashion. While that may not matter on non-rotational devices, for
226  *  - on-disk bitmap
227  *  - in-core buddy (actually includes buddy and bitmap)
228  *  - preallocation descriptors (PAs)
231  *  - inode
232  *    assiged to specific inode and can be used for this inode only.
233  *    it describes part of inode's space preallocated to specific
240  *  - locality group
241  *    assigned to specific locality group which does not translate to
247  *    in-core buddy = on-disk bitmap + preallocation descriptors
250  *  - allocated blocks (persistent)
251  *  - preallocated blocks (non-persistent)
255  * literally -- time is discrete and delimited by locks.
258  *  blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
261  *  - init buddy:			buddy = on-disk + PAs
262  *  - new PA:				buddy += N; PA = N
263  *  - use inode PA:			on-disk += N; PA -= N
264  *  - discard inode PA			buddy -= on-disk - PA; PA = 0
265  *  - use locality group PA		on-disk += N; PA -= N
266  *  - discard locality group PA		buddy -= PA; PA = 0
267  *  note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
269  *        bits from PA, only from on-disk bitmap
273  * killing performance on high-end SMP hardware. let's try to relax it using
277  *     nobody can re-allocate that block
278  *  3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
280  *     on-disk bitmap if buddy has same bit set or/and PA covers corresponded
284  *  - init buddy vs.
285  *    - new PA
288  *    - use inode PA
289  *      we need to make sure that either on-disk bitmap or PA has uptodate data
290  *      given (3) we care that PA-=N operation doesn't interfere with init
291  *    - discard inode PA
293  *    - use locality group PA
294  *      again PA-=N must be serialized with init
295  *    - discard locality group PA
297  *  - new PA vs.
298  *    - use inode PA
300  *    - discard inode PA
302  *    - use locality group PA
304  *    - discard locality group PA
306  *  - use inode PA
307  *    - use inode PA
309  *    - discard inode PA
311  *    - use locality group PA
312  *      nothing wrong here -- they're different PAs covering different blocks
313  *    - discard locality group PA
317  *  - PA is referenced and while it is no discard is possible
318  *  - PA is referenced until block isn't marked in on-disk bitmap
319  *  - PA changes only after on-disk bitmap
320  *  - discard must not compete with init. either init is done before
322  *  - buddy init as sum of on-disk bitmap and PAs is done atomically
332  *  - allocation:
335  *    mark bits in on-disk bitmap
338  *  - use preallocation:
339  *    find proper PA (per-inode or group)
341  *    mark bits in on-disk bitmap
345  *  - free:
347  *    mark bits in on-disk bitmap
350  *  - discard preallocations in group:
353  *    load on-disk bitmap
355  *    remove PA from object (inode or locality group)
356  *    mark free blocks in-core
358  *  - discard inode's preallocations:
365  *  - bitlock on a group	(group)
366  *  - object (inode/locality)	(object)
367  *  - per-pa lock		(pa)
368  *  - cr_power2_aligned lists lock	(cr_power2_aligned)
369  *  - cr_goal_len_fast lists lock	(cr_goal_len_fast)
372  *  - new pa
376  *  - find and use pa:
379  *  - release consumed pa:
384  *  - generate in-core bitmap:
388  *  - discard all for given object (inode, locality group):
393  *  - discard all for given group:
399  *  - allocation path (ext4_mb_regular_allocator)
446  * sure that all the PAs on grp->bb_prealloc_list got freed or if it's empty.
508 	ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;  in mb_find_next_zero_bit()
521 	ret = ext4_find_next_bit(addr, tmpmax, start) - fix;  in mb_find_next_bit()
531 	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);  in mb_find_buddy()
534 	if (order > e4b->bd_blkbits + 1) {  in mb_find_buddy()
541 		*max = 1 << (e4b->bd_blkbits + 3);  in mb_find_buddy()
542 		return e4b->bd_bitmap;  in mb_find_buddy()
545 	bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];  in mb_find_buddy()
546 	*max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];  in mb_find_buddy()
556 	struct super_block *sb = e4b->bd_sb;  in mb_free_blocks_double()
558 	if (unlikely(e4b->bd_info->bb_bitmap == NULL))  in mb_free_blocks_double()
560 	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));  in mb_free_blocks_double()
562 		if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {  in mb_free_blocks_double()
565 			blocknr = ext4_group_first_block_no(sb, e4b->bd_group);  in mb_free_blocks_double()
567 			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in mb_free_blocks_double()
569 			ext4_grp_locked_error(sb, e4b->bd_group,  in mb_free_blocks_double()
570 					      inode ? inode->i_ino : 0,  in mb_free_blocks_double()
576 		mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);  in mb_free_blocks_double()
584 	if (unlikely(e4b->bd_info->bb_bitmap == NULL))  in mb_mark_used_double()
586 	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));  in mb_mark_used_double()
588 		BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));  in mb_mark_used_double()
589 		mb_set_bit(first + i, e4b->bd_info->bb_bitmap);  in mb_mark_used_double()
595 	if (unlikely(e4b->bd_info->bb_bitmap == NULL))  in mb_cmp_bitmaps()
597 	if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {  in mb_cmp_bitmaps()
600 		b1 = (unsigned char *) e4b->bd_info->bb_bitmap;  in mb_cmp_bitmaps()
602 		for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {  in mb_cmp_bitmaps()
604 				ext4_msg(e4b->bd_sb, KERN_ERR,  in mb_cmp_bitmaps()
608 					 e4b->bd_group, i, i * 8, b1[i], b2[i]);  in mb_cmp_bitmaps()
620 	grp->bb_bitmap = kmalloc(sb->s_blocksize, GFP_NOFS);  in mb_group_bb_bitmap_alloc()
621 	if (!grp->bb_bitmap)  in mb_group_bb_bitmap_alloc()
626 		kfree(grp->bb_bitmap);  in mb_group_bb_bitmap_alloc()
627 		grp->bb_bitmap = NULL;  in mb_group_bb_bitmap_alloc()
631 	memcpy(grp->bb_bitmap, bh->b_data, sb->s_blocksize);  in mb_group_bb_bitmap_alloc()
637 	kfree(grp->bb_bitmap);  in mb_group_bb_bitmap_free()
683 	struct super_block *sb = e4b->bd_sb;  in __mb_check_buddy()
684 	int order = e4b->bd_blkbits + 1;  in __mb_check_buddy()
698 	if (e4b->bd_info->bb_check_counter++ % 10)  in __mb_check_buddy()
704 		buddy2 = mb_find_buddy(e4b, order - 1, &max2);  in __mb_check_buddy()
728 					!mb_test_bit(k, e4b->bd_bitmap));  in __mb_check_buddy()
732 		MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);  in __mb_check_buddy()
733 		order--;  in __mb_check_buddy()
736 	fstart = -1;  in __mb_check_buddy()
740 			MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);  in __mb_check_buddy()
741 			if (fstart == -1) {  in __mb_check_buddy()
747 		fstart = -1;  in __mb_check_buddy()
749 		for (j = 0; j < e4b->bd_blkbits + 1; j++) {  in __mb_check_buddy()
756 	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));  in __mb_check_buddy()
757 	MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);  in __mb_check_buddy()
759 	grp = ext4_get_group_info(sb, e4b->bd_group);  in __mb_check_buddy()
762 	list_for_each(cur, &grp->bb_prealloc_list) {  in __mb_check_buddy()
766 		ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);  in __mb_check_buddy()
767 		MB_CHECK_ASSERT(groupnr == e4b->bd_group);  in __mb_check_buddy()
768 		for (i = 0; i < pa->pa_len; i++)  in __mb_check_buddy()
797 	border = 2 << sb->s_blocksize_bits;  in ext4_mb_mark_free_simple()
801 		max = ffs(first | border) - 1;  in ext4_mb_mark_free_simple()
804 		min = fls(len) - 1;  in ext4_mb_mark_free_simple()
811 		grp->bb_counters[min]++;  in ext4_mb_mark_free_simple()
814 				     buddy + sbi->s_mb_offsets[min]);  in ext4_mb_mark_free_simple()
816 		len -= chunk;  in ext4_mb_mark_free_simple()
829 	order = fls(len) - 2;  in mb_avg_fragment_size_order()
833 		order--;  in mb_avg_fragment_size_order()
835 		order = MB_NUM_ORDERS(sb) - 1;  in mb_avg_fragment_size_order()
846 	if (!test_opt2(sb, MB_OPTIMIZE_SCAN) || grp->bb_fragments == 0)  in mb_update_avg_fragment_size()
850 					grp->bb_free / grp->bb_fragments);  in mb_update_avg_fragment_size()
851 	if (new_order == grp->bb_avg_fragment_size_order)  in mb_update_avg_fragment_size()
854 	if (grp->bb_avg_fragment_size_order != -1) {  in mb_update_avg_fragment_size()
855 		write_lock(&sbi->s_mb_avg_fragment_size_locks[  in mb_update_avg_fragment_size()
856 					grp->bb_avg_fragment_size_order]);  in mb_update_avg_fragment_size()
857 		list_del(&grp->bb_avg_fragment_size_node);  in mb_update_avg_fragment_size()
858 		write_unlock(&sbi->s_mb_avg_fragment_size_locks[  in mb_update_avg_fragment_size()
859 					grp->bb_avg_fragment_size_order]);  in mb_update_avg_fragment_size()
861 	grp->bb_avg_fragment_size_order = new_order;  in mb_update_avg_fragment_size()
862 	write_lock(&sbi->s_mb_avg_fragment_size_locks[  in mb_update_avg_fragment_size()
863 					grp->bb_avg_fragment_size_order]);  in mb_update_avg_fragment_size()
864 	list_add_tail(&grp->bb_avg_fragment_size_node,  in mb_update_avg_fragment_size()
865 		&sbi->s_mb_avg_fragment_size[grp->bb_avg_fragment_size_order]);  in mb_update_avg_fragment_size()
866 	write_unlock(&sbi->s_mb_avg_fragment_size_locks[  in mb_update_avg_fragment_size()
867 					grp->bb_avg_fragment_size_order]);  in mb_update_avg_fragment_size()
877 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_choose_next_group_p2_aligned()
881 	if (ac->ac_status == AC_STATUS_FOUND)  in ext4_mb_choose_next_group_p2_aligned()
884 	if (unlikely(sbi->s_mb_stats && ac->ac_flags & EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED))  in ext4_mb_choose_next_group_p2_aligned()
885 		atomic_inc(&sbi->s_bal_p2_aligned_bad_suggestions);  in ext4_mb_choose_next_group_p2_aligned()
887 	for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {  in ext4_mb_choose_next_group_p2_aligned()
888 		if (list_empty(&sbi->s_mb_largest_free_orders[i]))  in ext4_mb_choose_next_group_p2_aligned()
890 		read_lock(&sbi->s_mb_largest_free_orders_locks[i]);  in ext4_mb_choose_next_group_p2_aligned()
891 		if (list_empty(&sbi->s_mb_largest_free_orders[i])) {  in ext4_mb_choose_next_group_p2_aligned()
892 			read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);  in ext4_mb_choose_next_group_p2_aligned()
895 		list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],  in ext4_mb_choose_next_group_p2_aligned()
897 			if (sbi->s_mb_stats)  in ext4_mb_choose_next_group_p2_aligned()
898 				atomic64_inc(&sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]);  in ext4_mb_choose_next_group_p2_aligned()
899 			if (likely(ext4_mb_good_group(ac, iter->bb_group, CR_POWER2_ALIGNED))) {  in ext4_mb_choose_next_group_p2_aligned()
900 				*group = iter->bb_group;  in ext4_mb_choose_next_group_p2_aligned()
901 				ac->ac_flags |= EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED;  in ext4_mb_choose_next_group_p2_aligned()
902 				read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);  in ext4_mb_choose_next_group_p2_aligned()
906 		read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);  in ext4_mb_choose_next_group_p2_aligned()
919 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_find_good_group_avg_frag_lists()
920 	struct list_head *frag_list = &sbi->s_mb_avg_fragment_size[order];  in ext4_mb_find_good_group_avg_frag_lists()
921 	rwlock_t *frag_list_lock = &sbi->s_mb_avg_fragment_size_locks[order];  in ext4_mb_find_good_group_avg_frag_lists()
923 	enum criteria cr = ac->ac_criteria;  in ext4_mb_find_good_group_avg_frag_lists()
933 		if (sbi->s_mb_stats)  in ext4_mb_find_good_group_avg_frag_lists()
934 			atomic64_inc(&sbi->s_bal_cX_groups_considered[cr]);  in ext4_mb_find_good_group_avg_frag_lists()
935 		if (likely(ext4_mb_good_group(ac, iter->bb_group, cr))) {  in ext4_mb_find_good_group_avg_frag_lists()
951 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_choose_next_group_goal_fast()
955 	if (unlikely(ac->ac_flags & EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED)) {  in ext4_mb_choose_next_group_goal_fast()
956 		if (sbi->s_mb_stats)  in ext4_mb_choose_next_group_goal_fast()
957 			atomic_inc(&sbi->s_bal_goal_fast_bad_suggestions);  in ext4_mb_choose_next_group_goal_fast()
960 	for (i = mb_avg_fragment_size_order(ac->ac_sb, ac->ac_g_ex.fe_len);  in ext4_mb_choose_next_group_goal_fast()
961 	     i < MB_NUM_ORDERS(ac->ac_sb); i++) {  in ext4_mb_choose_next_group_goal_fast()
964 			*group = grp->bb_group;  in ext4_mb_choose_next_group_goal_fast()
965 			ac->ac_flags |= EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED;  in ext4_mb_choose_next_group_goal_fast()
974 	 * request len. However, allocation request for non-regular  in ext4_mb_choose_next_group_goal_fast()
978 	if (ac->ac_flags & EXT4_MB_HINT_DATA)  in ext4_mb_choose_next_group_goal_fast()
996 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_choose_next_group_best_avail()
1001 	if (unlikely(ac->ac_flags & EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED)) {  in ext4_mb_choose_next_group_best_avail()
1002 		if (sbi->s_mb_stats)  in ext4_mb_choose_next_group_best_avail()
1003 			atomic_inc(&sbi->s_bal_best_avail_bad_suggestions);  in ext4_mb_choose_next_group_best_avail()
1012 	order = fls(ac->ac_g_ex.fe_len) - 1;  in ext4_mb_choose_next_group_best_avail()
1013 	if (WARN_ON_ONCE(order - 1 > MB_NUM_ORDERS(ac->ac_sb)))  in ext4_mb_choose_next_group_best_avail()
1014 		order = MB_NUM_ORDERS(ac->ac_sb);  in ext4_mb_choose_next_group_best_avail()
1015 	min_order = order - sbi->s_mb_best_avail_max_trim_order;  in ext4_mb_choose_next_group_best_avail()
1019 	if (sbi->s_stripe > 0) {  in ext4_mb_choose_next_group_best_avail()
1024 		num_stripe_clusters = EXT4_NUM_B2C(sbi, sbi->s_stripe);  in ext4_mb_choose_next_group_best_avail()
1030 			min_order = fls(num_stripe_clusters) - 1;  in ext4_mb_choose_next_group_best_avail()
1033 	if (1 << min_order < ac->ac_o_ex.fe_len)  in ext4_mb_choose_next_group_best_avail()
1034 		min_order = fls(ac->ac_o_ex.fe_len);  in ext4_mb_choose_next_group_best_avail()
1036 	for (i = order; i >= min_order; i--) {  in ext4_mb_choose_next_group_best_avail()
1043 		ac->ac_g_ex.fe_len = 1 << i;  in ext4_mb_choose_next_group_best_avail()
1051 			ac->ac_g_ex.fe_len = roundup(ac->ac_g_ex.fe_len,  in ext4_mb_choose_next_group_best_avail()
1055 		frag_order = mb_avg_fragment_size_order(ac->ac_sb,  in ext4_mb_choose_next_group_best_avail()
1056 							ac->ac_g_ex.fe_len);  in ext4_mb_choose_next_group_best_avail()
1060 			*group = grp->bb_group;  in ext4_mb_choose_next_group_best_avail()
1061 			ac->ac_flags |= EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED;  in ext4_mb_choose_next_group_best_avail()
1067 	ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;  in ext4_mb_choose_next_group_best_avail()
1073 	if (unlikely(!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN)))  in should_optimize_scan()
1075 	if (ac->ac_criteria >= CR_GOAL_LEN_SLOW)  in should_optimize_scan()
1077 	if (!ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))  in should_optimize_scan()
1089 	 * Artificially restricted ngroups for non-extent  in next_linear_group()
1111 	*new_cr = ac->ac_criteria;  in ext4_mb_choose_next_group()
1123 	if (ac->ac_groups_linear_remaining) {  in ext4_mb_choose_next_group()
1125 		ac->ac_groups_linear_remaining--;  in ext4_mb_choose_next_group()
1155 	for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--)  in mb_set_largest_free_order()
1156 		if (grp->bb_counters[i] > 0)  in mb_set_largest_free_order()
1160 	    i == grp->bb_largest_free_order) {  in mb_set_largest_free_order()
1161 		grp->bb_largest_free_order = i;  in mb_set_largest_free_order()
1165 	if (grp->bb_largest_free_order >= 0) {  in mb_set_largest_free_order()
1166 		write_lock(&sbi->s_mb_largest_free_orders_locks[  in mb_set_largest_free_order()
1167 					      grp->bb_largest_free_order]);  in mb_set_largest_free_order()
1168 		list_del_init(&grp->bb_largest_free_order_node);  in mb_set_largest_free_order()
1169 		write_unlock(&sbi->s_mb_largest_free_orders_locks[  in mb_set_largest_free_order()
1170 					      grp->bb_largest_free_order]);  in mb_set_largest_free_order()
1172 	grp->bb_largest_free_order = i;  in mb_set_largest_free_order()
1173 	if (grp->bb_largest_free_order >= 0 && grp->bb_free) {  in mb_set_largest_free_order()
1174 		write_lock(&sbi->s_mb_largest_free_orders_locks[  in mb_set_largest_free_order()
1175 					      grp->bb_largest_free_order]);  in mb_set_largest_free_order()
1176 		list_add_tail(&grp->bb_largest_free_order_node,  in mb_set_largest_free_order()
1177 		      &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);  in mb_set_largest_free_order()
1178 		write_unlock(&sbi->s_mb_largest_free_orders_locks[  in mb_set_largest_free_order()
1179 					      grp->bb_largest_free_order]);  in mb_set_largest_free_order()
1198 	 * of on-disk bitmap and preallocations */  in ext4_mb_generate_buddy()
1200 	grp->bb_first_free = i;  in ext4_mb_generate_buddy()
1205 		len = i - first;  in ext4_mb_generate_buddy()
1210 			grp->bb_counters[0]++;  in ext4_mb_generate_buddy()
1214 	grp->bb_fragments = fragments;  in ext4_mb_generate_buddy()
1216 	if (free != grp->bb_free) {  in ext4_mb_generate_buddy()
1220 				      free, grp->bb_free);  in ext4_mb_generate_buddy()
1225 		grp->bb_free = free;  in ext4_mb_generate_buddy()
1232 	clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));  in ext4_mb_generate_buddy()
1234 	period = get_cycles() - period;  in ext4_mb_generate_buddy()
1235 	atomic_inc(&sbi->s_mb_buddies_generated);  in ext4_mb_generate_buddy()
1236 	atomic64_add(period, &sbi->s_mb_generation_time);  in ext4_mb_generate_buddy()
1248 	e4b->bd_info->bb_fragments = 0;  in mb_regenerate_buddy()
1249 	memset(e4b->bd_info->bb_counters, 0,  in mb_regenerate_buddy()
1250 		sizeof(*e4b->bd_info->bb_counters) *  in mb_regenerate_buddy()
1251 		(e4b->bd_sb->s_blocksize_bits + 2));  in mb_regenerate_buddy()
1253 	ext4_mb_generate_buddy(e4b->bd_sb, e4b->bd_buddy,  in mb_regenerate_buddy()
1254 		e4b->bd_bitmap, e4b->bd_group, e4b->bd_info);  in mb_regenerate_buddy()
1295 	inode = folio->mapping->host;  in ext4_mb_init_cache()
1296 	sb = inode->i_sb;  in ext4_mb_init_cache()
1301 	mb_debug(sb, "init folio %lu\n", folio->index);  in ext4_mb_init_cache()
1312 			return -ENOMEM;  in ext4_mb_init_cache()
1316 	first_group = folio->index * blocks_per_page / 2;  in ext4_mb_init_cache()
1357 	first_block = folio->index * blocks_per_page;  in ext4_mb_init_cache()
1363 		if (!bh[group - first_group])  in ext4_mb_init_cache()
1367 		if (!buffer_verified(bh[group - first_group]))  in ext4_mb_init_cache()
1379 		bitmap = bh[group - first_group]->b_data;  in ext4_mb_init_cache()
1387 			err = -EFSCORRUPTED;  in ext4_mb_init_cache()
1394 				group, folio->index, i * blocksize);  in ext4_mb_init_cache()
1396 			grinfo->bb_fragments = 0;  in ext4_mb_init_cache()
1397 			memset(grinfo->bb_counters, 0,  in ext4_mb_init_cache()
1398 			       sizeof(*grinfo->bb_counters) *  in ext4_mb_init_cache()
1413 				group, folio->index, i * blocksize);  in ext4_mb_init_cache()
1420 			/* mark all preallocated blks used in in-core bitmap */  in ext4_mb_init_cache()
1422 			WARN_ON_ONCE(!RB_EMPTY_ROOT(&grinfo->bb_free_root));  in ext4_mb_init_cache()
1447  * are on the same page e4b->bd_buddy_folio is NULL and return value is 0.
1452 	struct inode *inode = EXT4_SB(sb)->s_buddy_cache;  in ext4_mb_get_buddy_page_lock()
1457 	e4b->bd_buddy_folio = NULL;  in ext4_mb_get_buddy_page_lock()
1458 	e4b->bd_bitmap_folio = NULL;  in ext4_mb_get_buddy_page_lock()
1460 	blocks_per_page = PAGE_SIZE / sb->s_blocksize;  in ext4_mb_get_buddy_page_lock()
1469 	folio = __filemap_get_folio(inode->i_mapping, pnum,  in ext4_mb_get_buddy_page_lock()
1473 	BUG_ON(folio->mapping != inode->i_mapping);  in ext4_mb_get_buddy_page_lock()
1474 	e4b->bd_bitmap_folio = folio;  in ext4_mb_get_buddy_page_lock()
1475 	e4b->bd_bitmap = folio_address(folio) + (poff * sb->s_blocksize);  in ext4_mb_get_buddy_page_lock()
1483 	folio = __filemap_get_folio(inode->i_mapping, block + 1,  in ext4_mb_get_buddy_page_lock()
1487 	BUG_ON(folio->mapping != inode->i_mapping);  in ext4_mb_get_buddy_page_lock()
1488 	e4b->bd_buddy_folio = folio;  in ext4_mb_get_buddy_page_lock()
1494 	if (e4b->bd_bitmap_folio) {  in ext4_mb_put_buddy_page_lock()
1495 		folio_unlock(e4b->bd_bitmap_folio);  in ext4_mb_put_buddy_page_lock()
1496 		folio_put(e4b->bd_bitmap_folio);  in ext4_mb_put_buddy_page_lock()
1498 	if (e4b->bd_buddy_folio) {  in ext4_mb_put_buddy_page_lock()
1499 		folio_unlock(e4b->bd_buddy_folio);  in ext4_mb_put_buddy_page_lock()
1500 		folio_put(e4b->bd_buddy_folio);  in ext4_mb_put_buddy_page_lock()
1522 		return -EFSCORRUPTED;  in ext4_mb_init_group()
1547 		ret = -EIO;  in ext4_mb_init_group()
1566 		ret = -EIO;  in ext4_mb_init_group()
1591 	struct inode *inode = sbi->s_buddy_cache;  in ext4_mb_load_buddy_gfp()
1596 	blocks_per_page = PAGE_SIZE / sb->s_blocksize;  in ext4_mb_load_buddy_gfp()
1599 		return -EFSCORRUPTED;  in ext4_mb_load_buddy_gfp()
1601 	e4b->bd_blkbits = sb->s_blocksize_bits;  in ext4_mb_load_buddy_gfp()
1602 	e4b->bd_info = grp;  in ext4_mb_load_buddy_gfp()
1603 	e4b->bd_sb = sb;  in ext4_mb_load_buddy_gfp()
1604 	e4b->bd_group = group;  in ext4_mb_load_buddy_gfp()
1605 	e4b->bd_buddy_folio = NULL;  in ext4_mb_load_buddy_gfp()
1606 	e4b->bd_bitmap_folio = NULL;  in ext4_mb_load_buddy_gfp()
1628 	folio = __filemap_get_folio(inode->i_mapping, pnum, FGP_ACCESSED, 0);  in ext4_mb_load_buddy_gfp()
1640 		folio = __filemap_get_folio(inode->i_mapping, pnum,  in ext4_mb_load_buddy_gfp()
1643 			if (WARN_RATELIMIT(folio->mapping != inode->i_mapping,  in ext4_mb_load_buddy_gfp()
1644 	"ext4: bitmap's mapping != inode->i_mapping\n")) {  in ext4_mb_load_buddy_gfp()
1647 				ret = -EINVAL;  in ext4_mb_load_buddy_gfp()
1657 					       (poff * sb->s_blocksize));  in ext4_mb_load_buddy_gfp()
1667 		ret = -EIO;  in ext4_mb_load_buddy_gfp()
1672 	e4b->bd_bitmap_folio = folio;  in ext4_mb_load_buddy_gfp()
1673 	e4b->bd_bitmap = folio_address(folio) + (poff * sb->s_blocksize);  in ext4_mb_load_buddy_gfp()
1679 	folio = __filemap_get_folio(inode->i_mapping, pnum, FGP_ACCESSED, 0);  in ext4_mb_load_buddy_gfp()
1683 		folio = __filemap_get_folio(inode->i_mapping, pnum,  in ext4_mb_load_buddy_gfp()
1686 			if (WARN_RATELIMIT(folio->mapping != inode->i_mapping,  in ext4_mb_load_buddy_gfp()
1687 	"ext4: buddy bitmap's mapping != inode->i_mapping\n")) {  in ext4_mb_load_buddy_gfp()
1690 				ret = -EINVAL;  in ext4_mb_load_buddy_gfp()
1694 				ret = ext4_mb_init_cache(folio, e4b->bd_bitmap,  in ext4_mb_load_buddy_gfp()
1709 		ret = -EIO;  in ext4_mb_load_buddy_gfp()
1714 	e4b->bd_buddy_folio = folio;  in ext4_mb_load_buddy_gfp()
1715 	e4b->bd_buddy = folio_address(folio) + (poff * sb->s_blocksize);  in ext4_mb_load_buddy_gfp()
1722 	if (e4b->bd_bitmap_folio)  in ext4_mb_load_buddy_gfp()
1723 		folio_put(e4b->bd_bitmap_folio);  in ext4_mb_load_buddy_gfp()
1725 	e4b->bd_buddy = NULL;  in ext4_mb_load_buddy_gfp()
1726 	e4b->bd_bitmap = NULL;  in ext4_mb_load_buddy_gfp()
1738 	if (e4b->bd_bitmap_folio)  in ext4_mb_unload_buddy()
1739 		folio_put(e4b->bd_bitmap_folio);  in ext4_mb_unload_buddy()
1740 	if (e4b->bd_buddy_folio)  in ext4_mb_unload_buddy()
1741 		folio_put(e4b->bd_buddy_folio);  in ext4_mb_unload_buddy()
1750 	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);  in mb_find_order_for_block()
1751 	BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));  in mb_find_order_for_block()
1753 	while (order <= e4b->bd_blkbits + 1) {  in mb_find_order_for_block()
1770 		if ((cur & 31) == 0 && (len - cur) >= 32) {  in mb_clear_bits()
1783  * will return first found zero bit if any, -1 otherwise
1788 	int zero_bit = -1;  in mb_test_and_clear_bits()
1792 		if ((cur & 31) == 0 && (len - cur) >= 32) {  in mb_test_and_clear_bits()
1795 			if (*addr != (__u32)(-1) && zero_bit == -1)  in mb_test_and_clear_bits()
1801 		if (!mb_test_and_clear_bit(cur, bm) && zero_bit == -1)  in mb_test_and_clear_bits()
1815 		if ((cur & 31) == 0 && (len - cur) >= 32) {  in mb_set_bits()
1831 		(*bit) -= side;  in mb_buddy_adjust_border()
1837 		return -1;  in mb_buddy_adjust_border()
1860 		 * ---------------------------------  in mb_buddy_mark_free()
1862 		 * ---------------------------------  in mb_buddy_mark_free()
1864 		 * ---------------------------------  in mb_buddy_mark_free()
1880 			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&first, buddy, -1);  in mb_buddy_mark_free()
1882 			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&last, buddy, 1);  in mb_buddy_mark_free()
1889 			mb_clear_bits(buddy, first, last - first + 1);  in mb_buddy_mark_free()
1890 			e4b->bd_info->bb_counters[order - 1] += last - first + 1;  in mb_buddy_mark_free()
1905 	int last = first + count - 1;  in mb_free_blocks()
1906 	struct super_block *sb = e4b->bd_sb;  in mb_free_blocks()
1910 	BUG_ON(last >= (sb->s_blocksize << 3));  in mb_free_blocks()
1911 	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));  in mb_free_blocks()
1913 	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))  in mb_free_blocks()
1923 		left_is_free = !mb_test_bit(first - 1, e4b->bd_bitmap);  in mb_free_blocks()
1924 	block = mb_test_and_clear_bits(e4b->bd_bitmap, first, count);  in mb_free_blocks()
1925 	if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])  in mb_free_blocks()
1926 		right_is_free = !mb_test_bit(last + 1, e4b->bd_bitmap);  in mb_free_blocks()
1928 	if (unlikely(block != -1)) {  in mb_free_blocks()
1936 		if (sbi->s_mount_state & EXT4_FC_REPLAY) {  in mb_free_blocks()
1941 		blocknr = ext4_group_first_block_no(sb, e4b->bd_group);  in mb_free_blocks()
1943 		ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in mb_free_blocks()
1945 		ext4_grp_locked_error(sb, e4b->bd_group,  in mb_free_blocks()
1946 				      inode ? inode->i_ino : 0, blocknr,  in mb_free_blocks()
1953 	e4b->bd_info->bb_free += count;  in mb_free_blocks()
1954 	if (first < e4b->bd_info->bb_first_free)  in mb_free_blocks()
1955 		e4b->bd_info->bb_first_free = first;  in mb_free_blocks()
1959 		e4b->bd_info->bb_fragments--;  in mb_free_blocks()
1961 		e4b->bd_info->bb_fragments++;  in mb_free_blocks()
1971 		e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;  in mb_free_blocks()
1974 		last -= !right_is_free;  in mb_free_blocks()
1975 		e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;  in mb_free_blocks()
1981 	mb_set_largest_free_order(sb, e4b->bd_info);  in mb_free_blocks()
1982 	mb_update_avg_fragment_size(sb, e4b->bd_info);  in mb_free_blocks()
1993 	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));  in mb_find_extent()
2000 		ex->fe_len = 0;  in mb_find_extent()
2001 		ex->fe_start = 0;  in mb_find_extent()
2002 		ex->fe_group = 0;  in mb_find_extent()
2009 	ex->fe_len = (1 << order) - (block & ((1 << order) - 1));  in mb_find_extent()
2010 	ex->fe_start = block;  in mb_find_extent()
2011 	ex->fe_group = e4b->bd_group;  in mb_find_extent()
2015 	while (needed > ex->fe_len &&  in mb_find_extent()
2022 		if (mb_test_bit(next, e4b->bd_bitmap))  in mb_find_extent()
2028 		ex->fe_len += 1 << order;  in mb_find_extent()
2031 	if (ex->fe_start + ex->fe_len > EXT4_CLUSTERS_PER_GROUP(e4b->bd_sb)) {  in mb_find_extent()
2034 		ext4_grp_locked_error(e4b->bd_sb, e4b->bd_group, 0, 0,  in mb_find_extent()
2037 			block, order, needed, ex->fe_group, ex->fe_start,  in mb_find_extent()
2038 			ex->fe_len, ex->fe_logical);  in mb_find_extent()
2039 		ex->fe_len = 0;  in mb_find_extent()
2040 		ex->fe_start = 0;  in mb_find_extent()
2041 		ex->fe_group = 0;  in mb_find_extent()
2043 	return ex->fe_len;  in mb_find_extent()
2051 	int start = ex->fe_start;  in mb_mark_used()
2052 	int len = ex->fe_len;  in mb_mark_used()
2058 	BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));  in mb_mark_used()
2059 	BUG_ON(e4b->bd_group != ex->fe_group);  in mb_mark_used()
2060 	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));  in mb_mark_used()
2065 	e4b->bd_info->bb_free -= len;  in mb_mark_used()
2066 	if (e4b->bd_info->bb_first_free == start)  in mb_mark_used()
2067 		e4b->bd_info->bb_first_free += len;  in mb_mark_used()
2071 		mlen = !mb_test_bit(start - 1, e4b->bd_bitmap);  in mb_mark_used()
2072 	if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])  in mb_mark_used()
2073 		max = !mb_test_bit(start + len, e4b->bd_bitmap);  in mb_mark_used()
2075 		e4b->bd_info->bb_fragments++;  in mb_mark_used()
2077 		e4b->bd_info->bb_fragments--;  in mb_mark_used()
2089 			e4b->bd_info->bb_counters[ord]--;  in mb_mark_used()
2091 			len -= mlen;  in mb_mark_used()
2103 		e4b->bd_info->bb_counters[ord]--;  in mb_mark_used()
2109 			ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,  in mb_mark_used()
2110 						 ord_start, start - ord_start,  in mb_mark_used()
2111 						 e4b->bd_info);  in mb_mark_used()
2115 			ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,  in mb_mark_used()
2117 						 ord_end - (start + len),  in mb_mark_used()
2118 						 e4b->bd_info);  in mb_mark_used()
2121 		len = start + len - ord_end;  in mb_mark_used()
2124 	mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);  in mb_mark_used()
2126 	mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);  in mb_mark_used()
2127 	mb_set_bits(e4b->bd_bitmap, ex->fe_start, len0);  in mb_mark_used()
2139 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_use_best_found()
2142 	BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);  in ext4_mb_use_best_found()
2143 	BUG_ON(ac->ac_status == AC_STATUS_FOUND);  in ext4_mb_use_best_found()
2145 	ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);  in ext4_mb_use_best_found()
2146 	ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;  in ext4_mb_use_best_found()
2147 	ret = mb_mark_used(e4b, &ac->ac_b_ex);  in ext4_mb_use_best_found()
2151 	ac->ac_f_ex = ac->ac_b_ex;  in ext4_mb_use_best_found()
2153 	ac->ac_status = AC_STATUS_FOUND;  in ext4_mb_use_best_found()
2154 	ac->ac_tail = ret & 0xffff;  in ext4_mb_use_best_found()
2155 	ac->ac_buddy = ret >> 16;  in ext4_mb_use_best_found()
2164 	ac->ac_bitmap_folio = e4b->bd_bitmap_folio;  in ext4_mb_use_best_found()
2165 	folio_get(ac->ac_bitmap_folio);  in ext4_mb_use_best_found()
2166 	ac->ac_buddy_folio = e4b->bd_buddy_folio;  in ext4_mb_use_best_found()
2167 	folio_get(ac->ac_buddy_folio);  in ext4_mb_use_best_found()
2169 	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {  in ext4_mb_use_best_found()
2170 		spin_lock(&sbi->s_md_lock);  in ext4_mb_use_best_found()
2171 		sbi->s_mb_last_group = ac->ac_f_ex.fe_group;  in ext4_mb_use_best_found()
2172 		sbi->s_mb_last_start = ac->ac_f_ex.fe_start;  in ext4_mb_use_best_found()
2173 		spin_unlock(&sbi->s_md_lock);  in ext4_mb_use_best_found()
2180 	if (ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)  in ext4_mb_use_best_found()
2189 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_check_limits()
2190 	struct ext4_free_extent *bex = &ac->ac_b_ex;  in ext4_mb_check_limits()
2191 	struct ext4_free_extent *gex = &ac->ac_g_ex;  in ext4_mb_check_limits()
2193 	if (ac->ac_status == AC_STATUS_FOUND)  in ext4_mb_check_limits()
2198 	if (ac->ac_found > sbi->s_mb_max_to_scan &&  in ext4_mb_check_limits()
2199 			!(ac->ac_flags & EXT4_MB_HINT_FIRST)) {  in ext4_mb_check_limits()
2200 		ac->ac_status = AC_STATUS_BREAK;  in ext4_mb_check_limits()
2207 	if (bex->fe_len < gex->fe_len)  in ext4_mb_check_limits()
2210 	if (finish_group || ac->ac_found > sbi->s_mb_min_to_scan)  in ext4_mb_check_limits()
2228  *   upto a max of sbi->s_mb_max_to_scan times (default 200). After
2232  *   upto a max of sbi->s_mb_min_to_scan times (default 10) before
2242 	struct ext4_free_extent *bex = &ac->ac_b_ex;  in ext4_mb_measure_extent()
2243 	struct ext4_free_extent *gex = &ac->ac_g_ex;  in ext4_mb_measure_extent()
2245 	BUG_ON(ex->fe_len <= 0);  in ext4_mb_measure_extent()
2246 	BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));  in ext4_mb_measure_extent()
2247 	BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));  in ext4_mb_measure_extent()
2248 	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);  in ext4_mb_measure_extent()
2250 	ac->ac_found++;  in ext4_mb_measure_extent()
2251 	ac->ac_cX_found[ac->ac_criteria]++;  in ext4_mb_measure_extent()
2254 	 * The special case - take what you catch first  in ext4_mb_measure_extent()
2256 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {  in ext4_mb_measure_extent()
2265 	if (ex->fe_len == gex->fe_len) {  in ext4_mb_measure_extent()
2274 	if (bex->fe_len == 0) {  in ext4_mb_measure_extent()
2282 	if (bex->fe_len < gex->fe_len) {  in ext4_mb_measure_extent()
2285 		if (ex->fe_len > bex->fe_len)  in ext4_mb_measure_extent()
2287 	} else if (ex->fe_len > gex->fe_len) {  in ext4_mb_measure_extent()
2291 		if (ex->fe_len < bex->fe_len)  in ext4_mb_measure_extent()
2302 	struct ext4_free_extent ex = ac->ac_b_ex;  in ext4_mb_try_best_found()
2308 	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);  in ext4_mb_try_best_found()
2312 	ext4_lock_group(ac->ac_sb, group);  in ext4_mb_try_best_found()
2313 	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))  in ext4_mb_try_best_found()
2319 		ac->ac_b_ex = ex;  in ext4_mb_try_best_found()
2324 	ext4_unlock_group(ac->ac_sb, group);  in ext4_mb_try_best_found()
2332 	ext4_group_t group = ac->ac_g_ex.fe_group;  in ext4_mb_find_by_goal()
2335 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_find_by_goal()
2336 	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);  in ext4_mb_find_by_goal()
2340 		return -EFSCORRUPTED;  in ext4_mb_find_by_goal()
2341 	if (!(ac->ac_flags & (EXT4_MB_HINT_TRY_GOAL | EXT4_MB_HINT_GOAL_ONLY)))  in ext4_mb_find_by_goal()
2343 	if (grp->bb_free == 0)  in ext4_mb_find_by_goal()
2346 	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);  in ext4_mb_find_by_goal()
2350 	ext4_lock_group(ac->ac_sb, group);  in ext4_mb_find_by_goal()
2351 	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))  in ext4_mb_find_by_goal()
2354 	max = mb_find_extent(e4b, ac->ac_g_ex.fe_start,  in ext4_mb_find_by_goal()
2355 			     ac->ac_g_ex.fe_len, &ex);  in ext4_mb_find_by_goal()
2358 	if (max >= ac->ac_g_ex.fe_len &&  in ext4_mb_find_by_goal()
2359 	    ac->ac_g_ex.fe_len == EXT4_NUM_B2C(sbi, sbi->s_stripe)) {  in ext4_mb_find_by_goal()
2362 		start = ext4_grp_offs_to_block(ac->ac_sb, &ex);  in ext4_mb_find_by_goal()
2363 		/* use do_div to get remainder (would be 64-bit modulo) */  in ext4_mb_find_by_goal()
2364 		if (do_div(start, sbi->s_stripe) == 0) {  in ext4_mb_find_by_goal()
2365 			ac->ac_found++;  in ext4_mb_find_by_goal()
2366 			ac->ac_b_ex = ex;  in ext4_mb_find_by_goal()
2369 	} else if (max >= ac->ac_g_ex.fe_len) {  in ext4_mb_find_by_goal()
2371 		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);  in ext4_mb_find_by_goal()
2372 		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);  in ext4_mb_find_by_goal()
2373 		ac->ac_found++;  in ext4_mb_find_by_goal()
2374 		ac->ac_b_ex = ex;  in ext4_mb_find_by_goal()
2376 	} else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {  in ext4_mb_find_by_goal()
2380 		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);  in ext4_mb_find_by_goal()
2381 		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);  in ext4_mb_find_by_goal()
2382 		ac->ac_found++;  in ext4_mb_find_by_goal()
2383 		ac->ac_b_ex = ex;  in ext4_mb_find_by_goal()
2387 	ext4_unlock_group(ac->ac_sb, group);  in ext4_mb_find_by_goal()
2401 	struct super_block *sb = ac->ac_sb;  in ext4_mb_simple_scan_group()
2402 	struct ext4_group_info *grp = e4b->bd_info;  in ext4_mb_simple_scan_group()
2408 	BUG_ON(ac->ac_2order <= 0);  in ext4_mb_simple_scan_group()
2409 	for (i = ac->ac_2order; i < MB_NUM_ORDERS(sb); i++) {  in ext4_mb_simple_scan_group()
2410 		if (grp->bb_counters[i] == 0)  in ext4_mb_simple_scan_group()
2420 			ext4_mark_group_bitmap_corrupted(ac->ac_sb,  in ext4_mb_simple_scan_group()
2421 					e4b->bd_group,  in ext4_mb_simple_scan_group()
2423 			ext4_grp_locked_error(ac->ac_sb, e4b->bd_group, 0, 0,  in ext4_mb_simple_scan_group()
2425 				grp->bb_counters[i], i);  in ext4_mb_simple_scan_group()
2428 		ac->ac_found++;  in ext4_mb_simple_scan_group()
2429 		ac->ac_cX_found[ac->ac_criteria]++;  in ext4_mb_simple_scan_group()
2431 		ac->ac_b_ex.fe_len = 1 << i;  in ext4_mb_simple_scan_group()
2432 		ac->ac_b_ex.fe_start = k << i;  in ext4_mb_simple_scan_group()
2433 		ac->ac_b_ex.fe_group = e4b->bd_group;  in ext4_mb_simple_scan_group()
2437 		BUG_ON(ac->ac_f_ex.fe_len != ac->ac_g_ex.fe_len);  in ext4_mb_simple_scan_group()
2439 		if (EXT4_SB(sb)->s_mb_stats)  in ext4_mb_simple_scan_group()
2440 			atomic_inc(&EXT4_SB(sb)->s_bal_2orders);  in ext4_mb_simple_scan_group()
2455 	struct super_block *sb = ac->ac_sb;  in ext4_mb_complex_scan_group()
2456 	void *bitmap = e4b->bd_bitmap;  in ext4_mb_complex_scan_group()
2461 	free = e4b->bd_info->bb_free;  in ext4_mb_complex_scan_group()
2465 	i = e4b->bd_info->bb_first_free;  in ext4_mb_complex_scan_group()
2467 	while (free && ac->ac_status == AC_STATUS_CONTINUE) {  in ext4_mb_complex_scan_group()
2476 			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in ext4_mb_complex_scan_group()
2478 			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,  in ext4_mb_complex_scan_group()
2485 		if (!ext4_mb_cr_expensive(ac->ac_criteria)) {  in ext4_mb_complex_scan_group()
2494 			freelen = j - i;  in ext4_mb_complex_scan_group()
2496 			if (freelen < ac->ac_g_ex.fe_len) {  in ext4_mb_complex_scan_group()
2498 				free -= freelen;  in ext4_mb_complex_scan_group()
2503 		mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);  in ext4_mb_complex_scan_group()
2507 			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in ext4_mb_complex_scan_group()
2509 			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,  in ext4_mb_complex_scan_group()
2524 		free -= ex.fe_len;  in ext4_mb_complex_scan_group()
2532  * we try to find stripe-aligned chunks for stripe-size-multiple requests
2538 	struct super_block *sb = ac->ac_sb;  in ext4_mb_scan_aligned()
2540 	void *bitmap = e4b->bd_bitmap;  in ext4_mb_scan_aligned()
2547 	BUG_ON(sbi->s_stripe == 0);  in ext4_mb_scan_aligned()
2549 	/* find first stripe-aligned block in group */  in ext4_mb_scan_aligned()
2550 	first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);  in ext4_mb_scan_aligned()
2552 	a = first_group_block + sbi->s_stripe - 1;  in ext4_mb_scan_aligned()
2553 	do_div(a, sbi->s_stripe);  in ext4_mb_scan_aligned()
2554 	i = (a * sbi->s_stripe) - first_group_block;  in ext4_mb_scan_aligned()
2556 	stripe = EXT4_NUM_B2C(sbi, sbi->s_stripe);  in ext4_mb_scan_aligned()
2562 				ac->ac_found++;  in ext4_mb_scan_aligned()
2563 				ac->ac_cX_found[ac->ac_criteria]++;  in ext4_mb_scan_aligned()
2565 				ac->ac_b_ex = ex;  in ext4_mb_scan_aligned()
2583 	int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));  in ext4_mb_good_group()
2584 	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);  in ext4_mb_good_group()
2591 	free = grp->bb_free;  in ext4_mb_good_group()
2595 	fragments = grp->bb_fragments;  in ext4_mb_good_group()
2601 		BUG_ON(ac->ac_2order == 0);  in ext4_mb_good_group()
2604 		if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&  in ext4_mb_good_group()
2609 		if (free < ac->ac_g_ex.fe_len)  in ext4_mb_good_group()
2612 		if (ac->ac_2order >= MB_NUM_ORDERS(ac->ac_sb))  in ext4_mb_good_group()
2615 		if (grp->bb_largest_free_order < ac->ac_2order)  in ext4_mb_good_group()
2621 		if ((free / fragments) >= ac->ac_g_ex.fe_len)  in ext4_mb_good_group()
2625 		if (free >= ac->ac_g_ex.fe_len)  in ext4_mb_good_group()
2651 	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);  in ext4_mb_good_group_nolock()
2652 	struct super_block *sb = ac->ac_sb;  in ext4_mb_good_group_nolock()
2654 	bool should_lock = ac->ac_flags & EXT4_MB_STRICT_CHECK;  in ext4_mb_good_group_nolock()
2659 		return -EFSCORRUPTED;  in ext4_mb_good_group_nolock()
2660 	if (sbi->s_mb_stats)  in ext4_mb_good_group_nolock()
2661 		atomic64_inc(&sbi->s_bal_cX_groups_considered[ac->ac_criteria]);  in ext4_mb_good_group_nolock()
2666 	free = grp->bb_free;  in ext4_mb_good_group_nolock()
2674 	if (cr < CR_ANY_FREE && free < ac->ac_g_ex.fe_len)  in ext4_mb_good_group_nolock()
2699 		    (!sbi->s_log_groups_per_flex ||  in ext4_mb_good_group_nolock()
2700 		     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &&  in ext4_mb_good_group_nolock()
2702 		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))  in ext4_mb_good_group_nolock()
2734 	while (nr-- > 0) {  in ext4_mb_prefetch()
2781 	while (nr-- > 0) {  in ext4_mb_prefetch_fini()
2784 		group--;  in ext4_mb_prefetch_fini()
2808 	sb = ac->ac_sb;  in ext4_mb_regular_allocator()
2811 	/* non-extent files are limited to low blocks/groups */  in ext4_mb_regular_allocator()
2812 	if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))  in ext4_mb_regular_allocator()
2813 		ngroups = sbi->s_blockfile_groups;  in ext4_mb_regular_allocator()
2815 	BUG_ON(ac->ac_status == AC_STATUS_FOUND);  in ext4_mb_regular_allocator()
2819 	if (err || ac->ac_status == AC_STATUS_FOUND)  in ext4_mb_regular_allocator()
2822 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))  in ext4_mb_regular_allocator()
2826 	 * ac->ac_2order is set only if the fe_len is a power of 2  in ext4_mb_regular_allocator()
2827 	 * if ac->ac_2order is set we also set criteria to CR_POWER2_ALIGNED  in ext4_mb_regular_allocator()
2830 	i = fls(ac->ac_g_ex.fe_len);  in ext4_mb_regular_allocator()
2831 	ac->ac_2order = 0;  in ext4_mb_regular_allocator()
2836 	 * We also support searching for power-of-two requests only for  in ext4_mb_regular_allocator()
2839 	if (i >= sbi->s_mb_order2_reqs && i <= MB_NUM_ORDERS(sb)) {  in ext4_mb_regular_allocator()
2840 		if (is_power_of_2(ac->ac_g_ex.fe_len))  in ext4_mb_regular_allocator()
2841 			ac->ac_2order = array_index_nospec(i - 1,  in ext4_mb_regular_allocator()
2846 	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {  in ext4_mb_regular_allocator()
2848 		spin_lock(&sbi->s_md_lock);  in ext4_mb_regular_allocator()
2849 		ac->ac_g_ex.fe_group = sbi->s_mb_last_group;  in ext4_mb_regular_allocator()
2850 		ac->ac_g_ex.fe_start = sbi->s_mb_last_start;  in ext4_mb_regular_allocator()
2851 		spin_unlock(&sbi->s_md_lock);  in ext4_mb_regular_allocator()
2855 	 * Let's just scan groups to find more-less suitable blocks We  in ext4_mb_regular_allocator()
2859 	if (ac->ac_2order)  in ext4_mb_regular_allocator()
2862 	for (; cr < EXT4_MB_NUM_CRS && ac->ac_status == AC_STATUS_CONTINUE; cr++) {  in ext4_mb_regular_allocator()
2863 		ac->ac_criteria = cr;  in ext4_mb_regular_allocator()
2868 		group = ac->ac_g_ex.fe_group;  in ext4_mb_regular_allocator()
2869 		ac->ac_groups_linear_remaining = sbi->s_mb_max_linear_groups;  in ext4_mb_regular_allocator()
2891 			     prefetch_ios < sbi->s_mb_prefetch_limit)) {  in ext4_mb_regular_allocator()
2892 				nr = sbi->s_mb_prefetch;  in ext4_mb_regular_allocator()
2894 					nr = 1 << sbi->s_log_groups_per_flex;  in ext4_mb_regular_allocator()
2895 					nr -= group & (nr - 1);  in ext4_mb_regular_allocator()
2896 					nr = min(nr, sbi->s_mb_prefetch);  in ext4_mb_regular_allocator()
2927 			ac->ac_groups_scanned++;  in ext4_mb_regular_allocator()
2932 					(sbi->s_stripe >=  in ext4_mb_regular_allocator()
2933 					 sbi->s_cluster_ratio) &&  in ext4_mb_regular_allocator()
2934 					!(ac->ac_g_ex.fe_len %  in ext4_mb_regular_allocator()
2935 					  EXT4_NUM_B2C(sbi, sbi->s_stripe));  in ext4_mb_regular_allocator()
2942 				if (ac->ac_status == AC_STATUS_CONTINUE)  in ext4_mb_regular_allocator()
2949 			if (ac->ac_status != AC_STATUS_CONTINUE)  in ext4_mb_regular_allocator()
2953 		if (sbi->s_mb_stats && i == ngroups)  in ext4_mb_regular_allocator()
2954 			atomic64_inc(&sbi->s_bal_cX_failed[cr]);  in ext4_mb_regular_allocator()
2956 		if (i == ngroups && ac->ac_criteria == CR_BEST_AVAIL_LEN)  in ext4_mb_regular_allocator()
2959 			ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;  in ext4_mb_regular_allocator()
2962 	if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&  in ext4_mb_regular_allocator()
2963 	    !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {  in ext4_mb_regular_allocator()
2969 		if (ac->ac_status != AC_STATUS_FOUND) {  in ext4_mb_regular_allocator()
2975 			lost = atomic_inc_return(&sbi->s_mb_lost_chunks);  in ext4_mb_regular_allocator()
2977 				 ac->ac_b_ex.fe_group, ac->ac_b_ex.fe_start,  in ext4_mb_regular_allocator()
2978 				 ac->ac_b_ex.fe_len, lost);  in ext4_mb_regular_allocator()
2980 			ac->ac_b_ex.fe_group = 0;  in ext4_mb_regular_allocator()
2981 			ac->ac_b_ex.fe_start = 0;  in ext4_mb_regular_allocator()
2982 			ac->ac_b_ex.fe_len = 0;  in ext4_mb_regular_allocator()
2983 			ac->ac_status = AC_STATUS_CONTINUE;  in ext4_mb_regular_allocator()
2984 			ac->ac_flags |= EXT4_MB_HINT_FIRST;  in ext4_mb_regular_allocator()
2990 	if (sbi->s_mb_stats && ac->ac_status == AC_STATUS_FOUND)  in ext4_mb_regular_allocator()
2991 		atomic64_inc(&sbi->s_bal_cX_hits[ac->ac_criteria]);  in ext4_mb_regular_allocator()
2993 	if (!err && ac->ac_status != AC_STATUS_FOUND && first_err)  in ext4_mb_regular_allocator()
2997 		 ac->ac_b_ex.fe_len, ac->ac_o_ex.fe_len, ac->ac_status,  in ext4_mb_regular_allocator()
2998 		 ac->ac_flags, cr, err);  in ext4_mb_regular_allocator()
3008 	struct super_block *sb = pde_data(file_inode(seq->file));  in ext4_mb_seq_groups_start()
3019 	struct super_block *sb = pde_data(file_inode(seq->file));  in ext4_mb_seq_groups_next()
3031 	struct super_block *sb = pde_data(file_inode(seq->file));  in ext4_mb_seq_groups_show()
3038 					     sb->s_blocksize_bits,  in ext4_mb_seq_groups_show()
3045 	group--;  in ext4_mb_seq_groups_show()
3061 			seq_printf(seq, "#%-5u: %s\n", group, ext4_decode_error(NULL, err, nbuf));  in ext4_mb_seq_groups_show()
3072 	seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,  in ext4_mb_seq_groups_show()
3075 		seq_printf(seq, " %-5u", i <= blocksize_bits + 1 ?  in ext4_mb_seq_groups_show()
3097 	struct super_block *sb = seq->private;  in ext4_seq_mb_stats_show()
3101 	if (!sbi->s_mb_stats) {  in ext4_seq_mb_stats_show()
3108 	seq_printf(seq, "\treqs: %u\n", atomic_read(&sbi->s_bal_reqs));  in ext4_seq_mb_stats_show()
3109 	seq_printf(seq, "\tsuccess: %u\n", atomic_read(&sbi->s_bal_success));  in ext4_seq_mb_stats_show()
3112 		   atomic_read(&sbi->s_bal_groups_scanned));  in ext4_seq_mb_stats_show()
3117 		   atomic64_read(&sbi->s_bal_cX_hits[CR_POWER2_ALIGNED]));  in ext4_seq_mb_stats_show()
3121 			&sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]));  in ext4_seq_mb_stats_show()
3123 		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_POWER2_ALIGNED]));  in ext4_seq_mb_stats_show()
3125 		   atomic64_read(&sbi->s_bal_cX_failed[CR_POWER2_ALIGNED]));  in ext4_seq_mb_stats_show()
3127 		   atomic_read(&sbi->s_bal_p2_aligned_bad_suggestions));  in ext4_seq_mb_stats_show()
3132 		   atomic64_read(&sbi->s_bal_cX_hits[CR_GOAL_LEN_FAST]));  in ext4_seq_mb_stats_show()
3135 			   &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_FAST]));  in ext4_seq_mb_stats_show()
3137 		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_FAST]));  in ext4_seq_mb_stats_show()
3139 		   atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_FAST]));  in ext4_seq_mb_stats_show()
3141 		   atomic_read(&sbi->s_bal_goal_fast_bad_suggestions));  in ext4_seq_mb_stats_show()
3146 		   atomic64_read(&sbi->s_bal_cX_hits[CR_BEST_AVAIL_LEN]));  in ext4_seq_mb_stats_show()
3150 			&sbi->s_bal_cX_groups_considered[CR_BEST_AVAIL_LEN]));  in ext4_seq_mb_stats_show()
3152 		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_BEST_AVAIL_LEN]));  in ext4_seq_mb_stats_show()
3154 		   atomic64_read(&sbi->s_bal_cX_failed[CR_BEST_AVAIL_LEN]));  in ext4_seq_mb_stats_show()
3156 		   atomic_read(&sbi->s_bal_best_avail_bad_suggestions));  in ext4_seq_mb_stats_show()
3161 		   atomic64_read(&sbi->s_bal_cX_hits[CR_GOAL_LEN_SLOW]));  in ext4_seq_mb_stats_show()
3164 			   &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_SLOW]));  in ext4_seq_mb_stats_show()
3166 		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_SLOW]));  in ext4_seq_mb_stats_show()
3168 		   atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_SLOW]));  in ext4_seq_mb_stats_show()
3173 		   atomic64_read(&sbi->s_bal_cX_hits[CR_ANY_FREE]));  in ext4_seq_mb_stats_show()
3176 		atomic64_read(&sbi->s_bal_cX_groups_considered[CR_ANY_FREE]));  in ext4_seq_mb_stats_show()
3178 		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_ANY_FREE]));  in ext4_seq_mb_stats_show()
3180 		   atomic64_read(&sbi->s_bal_cX_failed[CR_ANY_FREE]));  in ext4_seq_mb_stats_show()
3184 		   atomic_read(&sbi->s_bal_ex_scanned));  in ext4_seq_mb_stats_show()
3185 	seq_printf(seq, "\t\tgoal_hits: %u\n", atomic_read(&sbi->s_bal_goals));  in ext4_seq_mb_stats_show()
3187 		   atomic_read(&sbi->s_bal_len_goals));  in ext4_seq_mb_stats_show()
3188 	seq_printf(seq, "\t\t2^n_hits: %u\n", atomic_read(&sbi->s_bal_2orders));  in ext4_seq_mb_stats_show()
3189 	seq_printf(seq, "\t\tbreaks: %u\n", atomic_read(&sbi->s_bal_breaks));  in ext4_seq_mb_stats_show()
3190 	seq_printf(seq, "\t\tlost: %u\n", atomic_read(&sbi->s_mb_lost_chunks));  in ext4_seq_mb_stats_show()
3192 		   atomic_read(&sbi->s_mb_buddies_generated),  in ext4_seq_mb_stats_show()
3195 		   atomic64_read(&sbi->s_mb_generation_time));  in ext4_seq_mb_stats_show()
3197 		   atomic_read(&sbi->s_mb_preallocated));  in ext4_seq_mb_stats_show()
3198 	seq_printf(seq, "\tdiscarded: %u\n", atomic_read(&sbi->s_mb_discarded));  in ext4_seq_mb_stats_show()
3204 	struct super_block *sb = pde_data(file_inode(seq->file));  in ext4_mb_seq_structs_summary_start()
3215 	struct super_block *sb = pde_data(file_inode(seq->file));  in ext4_mb_seq_structs_summary_next()
3227 	struct super_block *sb = pde_data(file_inode(seq->file));  in ext4_mb_seq_structs_summary_show()
3233 	position--;  in ext4_mb_seq_structs_summary_show()
3235 		position -= MB_NUM_ORDERS(sb);  in ext4_mb_seq_structs_summary_show()
3240 		read_lock(&sbi->s_mb_avg_fragment_size_locks[position]);  in ext4_mb_seq_structs_summary_show()
3241 		list_for_each_entry(grp, &sbi->s_mb_avg_fragment_size[position],  in ext4_mb_seq_structs_summary_show()
3244 		read_unlock(&sbi->s_mb_avg_fragment_size_locks[position]);  in ext4_mb_seq_structs_summary_show()
3256 	read_lock(&sbi->s_mb_largest_free_orders_locks[position]);  in ext4_mb_seq_structs_summary_show()
3257 	list_for_each_entry(grp, &sbi->s_mb_largest_free_orders[position],  in ext4_mb_seq_structs_summary_show()
3260 	read_unlock(&sbi->s_mb_largest_free_orders_locks[position]);  in ext4_mb_seq_structs_summary_show()
3280 	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;  in get_groupinfo_cache()
3288  * Allocate the top-level s_group_info array for the specified number
3297 	size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>  in ext4_mb_alloc_groupinfo()
3299 	if (size <= sbi->s_group_info_size)  in ext4_mb_alloc_groupinfo()
3302 	size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);  in ext4_mb_alloc_groupinfo()
3306 		return -ENOMEM;  in ext4_mb_alloc_groupinfo()
3309 	old_groupinfo = rcu_dereference(sbi->s_group_info);  in ext4_mb_alloc_groupinfo()
3312 		       sbi->s_group_info_size * sizeof(*sbi->s_group_info));  in ext4_mb_alloc_groupinfo()
3314 	rcu_assign_pointer(sbi->s_group_info, new_groupinfo);  in ext4_mb_alloc_groupinfo()
3315 	sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);  in ext4_mb_alloc_groupinfo()
3319 		   sbi->s_group_info_size);  in ext4_mb_alloc_groupinfo()
3332 	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);  in ext4_mb_add_groupinfo()
3346 			return -ENOMEM;  in ext4_mb_add_groupinfo()
3349 		rcu_dereference(sbi->s_group_info)[idx] = meta_group_info;  in ext4_mb_add_groupinfo()
3354 	i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);  in ext4_mb_add_groupinfo()
3362 		&(meta_group_info[i]->bb_state));  in ext4_mb_add_groupinfo()
3369 	    (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {  in ext4_mb_add_groupinfo()
3370 		meta_group_info[i]->bb_free =  in ext4_mb_add_groupinfo()
3373 		meta_group_info[i]->bb_free =  in ext4_mb_add_groupinfo()
3377 	INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);  in ext4_mb_add_groupinfo()
3378 	init_rwsem(&meta_group_info[i]->alloc_sem);  in ext4_mb_add_groupinfo()
3379 	meta_group_info[i]->bb_free_root = RB_ROOT;  in ext4_mb_add_groupinfo()
3380 	INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);  in ext4_mb_add_groupinfo()
3381 	INIT_LIST_HEAD(&meta_group_info[i]->bb_avg_fragment_size_node);  in ext4_mb_add_groupinfo()
3382 	meta_group_info[i]->bb_largest_free_order = -1;  /* uninit */  in ext4_mb_add_groupinfo()
3383 	meta_group_info[i]->bb_avg_fragment_size_order = -1;  /* uninit */  in ext4_mb_add_groupinfo()
3384 	meta_group_info[i]->bb_group = group;  in ext4_mb_add_groupinfo()
3395 		group_info = rcu_dereference(sbi->s_group_info);  in ext4_mb_add_groupinfo()
3400 	return -ENOMEM;  in ext4_mb_add_groupinfo()
3417 	sbi->s_buddy_cache = new_inode(sb);  in ext4_mb_init_backend()
3418 	if (sbi->s_buddy_cache == NULL) {  in ext4_mb_init_backend()
3422 	/* To avoid potentially colliding with an valid on-disk inode number,  in ext4_mb_init_backend()
3426 	sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;  in ext4_mb_init_backend()
3427 	EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;  in ext4_mb_init_backend()
3444 		if (sbi->s_es->s_log_groups_per_flex >= 32) {  in ext4_mb_init_backend()
3448 		sbi->s_mb_prefetch = min_t(uint, 1 << sbi->s_es->s_log_groups_per_flex,  in ext4_mb_init_backend()
3449 			BLK_MAX_SEGMENT_SIZE >> (sb->s_blocksize_bits - 9));  in ext4_mb_init_backend()
3450 		sbi->s_mb_prefetch *= 8; /* 8 prefetch IOs in flight at most */  in ext4_mb_init_backend()
3452 		sbi->s_mb_prefetch = 32;  in ext4_mb_init_backend()
3454 	if (sbi->s_mb_prefetch > ext4_get_groups_count(sb))  in ext4_mb_init_backend()
3455 		sbi->s_mb_prefetch = ext4_get_groups_count(sb);  in ext4_mb_init_backend()
3458 	 * CR_POWER2_ALIGNED. Given CR_POWER2_ALIGNED is an CPU-related  in ext4_mb_init_backend()
3464 	sbi->s_mb_prefetch_limit = sbi->s_mb_prefetch * 4;  in ext4_mb_init_backend()
3465 	if (sbi->s_mb_prefetch_limit > ext4_get_groups_count(sb))  in ext4_mb_init_backend()
3466 		sbi->s_mb_prefetch_limit = ext4_get_groups_count(sb);  in ext4_mb_init_backend()
3471 	cachep = get_groupinfo_cache(sb->s_blocksize_bits);  in ext4_mb_init_backend()
3472 	while (i-- > 0) {  in ext4_mb_init_backend()
3478 	i = sbi->s_group_info_size;  in ext4_mb_init_backend()
3480 	group_info = rcu_dereference(sbi->s_group_info);  in ext4_mb_init_backend()
3481 	while (i-- > 0)  in ext4_mb_init_backend()
3484 	iput(sbi->s_buddy_cache);  in ext4_mb_init_backend()
3487 	kvfree(rcu_dereference(sbi->s_group_info));  in ext4_mb_init_backend()
3489 	return -ENOMEM;  in ext4_mb_init_backend()
3507 	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;  in ext4_groupinfo_create_slab()
3511 		return -EINVAL;  in ext4_groupinfo_create_slab()
3534 		       "EXT4-fs: no memory for groupinfo slab cache\n");  in ext4_groupinfo_create_slab()
3535 		return -ENOMEM;  in ext4_groupinfo_create_slab()
3545 	struct super_block *sb = sbi->s_sb;  in ext4_discard_work()
3552 	spin_lock(&sbi->s_md_lock);  in ext4_discard_work()
3553 	list_splice_init(&sbi->s_discard_list, &discard_list);  in ext4_discard_work()
3554 	spin_unlock(&sbi->s_md_lock);  in ext4_discard_work()
3562 		if ((sb->s_flags & SB_ACTIVE) && !err &&  in ext4_discard_work()
3563 		    !atomic_read(&sbi->s_retry_alloc_pending)) {  in ext4_discard_work()
3564 			grp = fd->efd_group;  in ext4_discard_work()
3580 			ext4_try_to_trim_range(sb, &e4b, fd->efd_start_cluster,  in ext4_discard_work()
3581 						fd->efd_start_cluster + fd->efd_count - 1, 1);  in ext4_discard_work()
3599 	i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_offsets);  in ext4_mb_init()
3601 	sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);  in ext4_mb_init()
3602 	if (sbi->s_mb_offsets == NULL) {  in ext4_mb_init()
3603 		ret = -ENOMEM;  in ext4_mb_init()
3607 	i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_maxs);  in ext4_mb_init()
3608 	sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);  in ext4_mb_init()
3609 	if (sbi->s_mb_maxs == NULL) {  in ext4_mb_init()
3610 		ret = -ENOMEM;  in ext4_mb_init()
3614 	ret = ext4_groupinfo_create_slab(sb->s_blocksize);  in ext4_mb_init()
3619 	sbi->s_mb_maxs[0] = sb->s_blocksize << 3;  in ext4_mb_init()
3620 	sbi->s_mb_offsets[0] = 0;  in ext4_mb_init()
3624 	offset_incr = 1 << (sb->s_blocksize_bits - 1);  in ext4_mb_init()
3625 	max = sb->s_blocksize << 2;  in ext4_mb_init()
3627 		sbi->s_mb_offsets[i] = offset;  in ext4_mb_init()
3628 		sbi->s_mb_maxs[i] = max;  in ext4_mb_init()
3635 	sbi->s_mb_avg_fragment_size =  in ext4_mb_init()
3638 	if (!sbi->s_mb_avg_fragment_size) {  in ext4_mb_init()
3639 		ret = -ENOMEM;  in ext4_mb_init()
3642 	sbi->s_mb_avg_fragment_size_locks =  in ext4_mb_init()
3645 	if (!sbi->s_mb_avg_fragment_size_locks) {  in ext4_mb_init()
3646 		ret = -ENOMEM;  in ext4_mb_init()
3650 		INIT_LIST_HEAD(&sbi->s_mb_avg_fragment_size[i]);  in ext4_mb_init()
3651 		rwlock_init(&sbi->s_mb_avg_fragment_size_locks[i]);  in ext4_mb_init()
3653 	sbi->s_mb_largest_free_orders =  in ext4_mb_init()
3656 	if (!sbi->s_mb_largest_free_orders) {  in ext4_mb_init()
3657 		ret = -ENOMEM;  in ext4_mb_init()
3660 	sbi->s_mb_largest_free_orders_locks =  in ext4_mb_init()
3663 	if (!sbi->s_mb_largest_free_orders_locks) {  in ext4_mb_init()
3664 		ret = -ENOMEM;  in ext4_mb_init()
3668 		INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);  in ext4_mb_init()
3669 		rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);  in ext4_mb_init()
3672 	spin_lock_init(&sbi->s_md_lock);  in ext4_mb_init()
3673 	sbi->s_mb_free_pending = 0;  in ext4_mb_init()
3674 	INIT_LIST_HEAD(&sbi->s_freed_data_list[0]);  in ext4_mb_init()
3675 	INIT_LIST_HEAD(&sbi->s_freed_data_list[1]);  in ext4_mb_init()
3676 	INIT_LIST_HEAD(&sbi->s_discard_list);  in ext4_mb_init()
3677 	INIT_WORK(&sbi->s_discard_work, ext4_discard_work);  in ext4_mb_init()
3678 	atomic_set(&sbi->s_retry_alloc_pending, 0);  in ext4_mb_init()
3680 	sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;  in ext4_mb_init()
3681 	sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;  in ext4_mb_init()
3682 	sbi->s_mb_stats = MB_DEFAULT_STATS;  in ext4_mb_init()
3683 	sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;  in ext4_mb_init()
3684 	sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;  in ext4_mb_init()
3685 	sbi->s_mb_best_avail_max_trim_order = MB_DEFAULT_BEST_AVAIL_TRIM_ORDER;  in ext4_mb_init()
3699 	sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>  in ext4_mb_init()
3700 				       sbi->s_cluster_bits, 32);  in ext4_mb_init()
3709 	if (sbi->s_stripe > 1) {  in ext4_mb_init()
3710 		sbi->s_mb_group_prealloc = roundup(  in ext4_mb_init()
3711 			sbi->s_mb_group_prealloc, EXT4_NUM_B2C(sbi, sbi->s_stripe));  in ext4_mb_init()
3714 	sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);  in ext4_mb_init()
3715 	if (sbi->s_locality_groups == NULL) {  in ext4_mb_init()
3716 		ret = -ENOMEM;  in ext4_mb_init()
3721 		lg = per_cpu_ptr(sbi->s_locality_groups, i);  in ext4_mb_init()
3722 		mutex_init(&lg->lg_mutex);  in ext4_mb_init()
3724 			INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);  in ext4_mb_init()
3725 		spin_lock_init(&lg->lg_prealloc_lock);  in ext4_mb_init()
3728 	if (bdev_nonrot(sb->s_bdev))  in ext4_mb_init()
3729 		sbi->s_mb_max_linear_groups = 0;  in ext4_mb_init()
3731 		sbi->s_mb_max_linear_groups = MB_DEFAULT_LINEAR_LIMIT;  in ext4_mb_init()
3740 	free_percpu(sbi->s_locality_groups);  in ext4_mb_init()
3741 	sbi->s_locality_groups = NULL;  in ext4_mb_init()
3743 	kfree(sbi->s_mb_avg_fragment_size);  in ext4_mb_init()
3744 	kfree(sbi->s_mb_avg_fragment_size_locks);  in ext4_mb_init()
3745 	kfree(sbi->s_mb_largest_free_orders);  in ext4_mb_init()
3746 	kfree(sbi->s_mb_largest_free_orders_locks);  in ext4_mb_init()
3747 	kfree(sbi->s_mb_offsets);  in ext4_mb_init()
3748 	sbi->s_mb_offsets = NULL;  in ext4_mb_init()
3749 	kfree(sbi->s_mb_maxs);  in ext4_mb_init()
3750 	sbi->s_mb_maxs = NULL;  in ext4_mb_init()
3761 	list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {  in ext4_mb_cleanup_pa()
3763 		list_del(&pa->pa_group_list);  in ext4_mb_cleanup_pa()
3777 	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);  in ext4_mb_release()
3784 		flush_work(&sbi->s_discard_work);  in ext4_mb_release()
3785 		WARN_ON_ONCE(!list_empty(&sbi->s_discard_list));  in ext4_mb_release()
3788 	if (sbi->s_group_info) {  in ext4_mb_release()
3804 				EXT4_DESC_PER_BLOCK(sb) - 1) >>  in ext4_mb_release()
3807 		group_info = rcu_dereference(sbi->s_group_info);  in ext4_mb_release()
3813 	kfree(sbi->s_mb_avg_fragment_size);  in ext4_mb_release()
3814 	kfree(sbi->s_mb_avg_fragment_size_locks);  in ext4_mb_release()
3815 	kfree(sbi->s_mb_largest_free_orders);  in ext4_mb_release()
3816 	kfree(sbi->s_mb_largest_free_orders_locks);  in ext4_mb_release()
3817 	kfree(sbi->s_mb_offsets);  in ext4_mb_release()
3818 	kfree(sbi->s_mb_maxs);  in ext4_mb_release()
3819 	iput(sbi->s_buddy_cache);  in ext4_mb_release()
3820 	if (sbi->s_mb_stats) {  in ext4_mb_release()
3823 				atomic_read(&sbi->s_bal_allocated),  in ext4_mb_release()
3824 				atomic_read(&sbi->s_bal_reqs),  in ext4_mb_release()
3825 				atomic_read(&sbi->s_bal_success));  in ext4_mb_release()
3829 				atomic_read(&sbi->s_bal_ex_scanned),  in ext4_mb_release()
3830 				atomic_read(&sbi->s_bal_groups_scanned),  in ext4_mb_release()
3831 				atomic_read(&sbi->s_bal_goals),  in ext4_mb_release()
3832 				atomic_read(&sbi->s_bal_2orders),  in ext4_mb_release()
3833 				atomic_read(&sbi->s_bal_breaks),  in ext4_mb_release()
3834 				atomic_read(&sbi->s_mb_lost_chunks));  in ext4_mb_release()
3837 				atomic_read(&sbi->s_mb_buddies_generated),  in ext4_mb_release()
3838 				atomic64_read(&sbi->s_mb_generation_time));  in ext4_mb_release()
3841 				atomic_read(&sbi->s_mb_preallocated),  in ext4_mb_release()
3842 				atomic_read(&sbi->s_mb_discarded));  in ext4_mb_release()
3845 	free_percpu(sbi->s_locality_groups);  in ext4_mb_release()
3870 		 entry->efd_count, entry->efd_group, entry);  in ext4_free_data_in_buddy()
3872 	err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b);  in ext4_free_data_in_buddy()
3876 	spin_lock(&EXT4_SB(sb)->s_md_lock);  in ext4_free_data_in_buddy()
3877 	EXT4_SB(sb)->s_mb_free_pending -= entry->efd_count;  in ext4_free_data_in_buddy()
3878 	spin_unlock(&EXT4_SB(sb)->s_md_lock);  in ext4_free_data_in_buddy()
3882 	count += entry->efd_count;  in ext4_free_data_in_buddy()
3883 	ext4_lock_group(sb, entry->efd_group);  in ext4_free_data_in_buddy()
3885 	rb_erase(&entry->efd_node, &(db->bb_free_root));  in ext4_free_data_in_buddy()
3886 	mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count);  in ext4_free_data_in_buddy()
3894 	if (!db->bb_free_root.rb_node) {  in ext4_free_data_in_buddy()
3901 	ext4_unlock_group(sb, entry->efd_group);  in ext4_free_data_in_buddy()
3916 	struct list_head *s_freed_head = &sbi->s_freed_data_list[commit_tid & 1];  in ext4_process_freed_data()
3925 		spin_lock(&sbi->s_md_lock);  in ext4_process_freed_data()
3926 		wake = list_empty(&sbi->s_discard_list);  in ext4_process_freed_data()
3927 		list_splice_tail(&freed_data_list, &sbi->s_discard_list);  in ext4_process_freed_data()
3928 		spin_unlock(&sbi->s_md_lock);  in ext4_process_freed_data()
3930 			queue_work(system_unbound_wq, &sbi->s_discard_work);  in ext4_process_freed_data()
3961 	return -ENOMEM;  in ext4_init_mballoc()
4009 	err = -EIO;  in ext4_mb_mark_context()
4024 	    (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {  in ext4_mb_mark_context()
4025 		gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);  in ext4_mb_mark_context()
4033 			if (mb_test_bit(blkoff + i, bitmap_bh->b_data) ==  in ext4_mb_mark_context()
4036 		changed = len - already;  in ext4_mb_mark_context()
4040 		mb_set_bits(bitmap_bh->b_data, blkoff, len);  in ext4_mb_mark_context()
4042 			ext4_free_group_clusters(sb, gdp) - changed);  in ext4_mb_mark_context()
4044 		mb_clear_bits(bitmap_bh->b_data, blkoff, len);  in ext4_mb_mark_context()
4055 	if (sbi->s_log_groups_per_flex) {  in ext4_mb_mark_context()
4061 			atomic64_sub(changed, &fg->free_clusters);  in ext4_mb_mark_context()
4063 			atomic64_add(changed, &fg->free_clusters);  in ext4_mb_mark_context()
4084  * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
4099 	BUG_ON(ac->ac_status != AC_STATUS_FOUND);  in ext4_mb_mark_diskspace_used()
4100 	BUG_ON(ac->ac_b_ex.fe_len <= 0);  in ext4_mb_mark_diskspace_used()
4102 	sb = ac->ac_sb;  in ext4_mb_mark_diskspace_used()
4105 	gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, NULL);  in ext4_mb_mark_diskspace_used()
4107 		return -EIO;  in ext4_mb_mark_diskspace_used()
4108 	ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,  in ext4_mb_mark_diskspace_used()
4111 	block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_mark_diskspace_used()
4112 	len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
4113 	if (!ext4_inode_block_valid(ac->ac_inode, block, len)) {  in ext4_mb_mark_diskspace_used()
4114 		ext4_error(sb, "Allocating blocks %llu-%llu which overlap "  in ext4_mb_mark_diskspace_used()
4121 					   ac->ac_b_ex.fe_group,  in ext4_mb_mark_diskspace_used()
4122 					   ac->ac_b_ex.fe_start,  in ext4_mb_mark_diskspace_used()
4123 					   ac->ac_b_ex.fe_len,  in ext4_mb_mark_diskspace_used()
4126 			err = -EFSCORRUPTED;  in ext4_mb_mark_diskspace_used()
4133 	err = ext4_mb_mark_context(handle, sb, true, ac->ac_b_ex.fe_group,  in ext4_mb_mark_diskspace_used()
4134 				   ac->ac_b_ex.fe_start, ac->ac_b_ex.fe_len,  in ext4_mb_mark_diskspace_used()
4141 	BUG_ON(changed != ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
4143 	percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
4147 	if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))  in ext4_mb_mark_diskspace_used()
4149 		percpu_counter_sub(&sbi->s_dirtyclusters_counter,  in ext4_mb_mark_diskspace_used()
4180 			EXT4_BLOCKS_PER_GROUP(sb) - EXT4_C2B(sbi, blkoff));  in ext4_mb_mark_bb()
4184 			ext4_error(sb, "Marking blocks in system zone - "  in ext4_mb_mark_bb()
4199 		len -= thisgrp_len;  in ext4_mb_mark_bb()
4205  * here we normalize request for locality group
4215 	struct super_block *sb = ac->ac_sb;  in ext4_mb_normalize_group_request()
4216 	struct ext4_locality_group *lg = ac->ac_lg;  in ext4_mb_normalize_group_request()
4219 	ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;  in ext4_mb_normalize_group_request()
4220 	mb_debug(sb, "goal %u blocks for locality group\n", ac->ac_g_ex.fe_len);  in ext4_mb_normalize_group_request()
4226  * (ei->i_prealloc_lock)
4236 		return node->rb_left;  in ext4_mb_pa_rb_next_iter()
4238 		return node->rb_right;  in ext4_mb_pa_rb_next_iter()
4245 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_pa_assert_overlap()
4246 	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);  in ext4_mb_pa_assert_overlap()
4252 	read_lock(&ei->i_prealloc_lock);  in ext4_mb_pa_assert_overlap()
4253 	for (iter = ei->i_prealloc_node.rb_node; iter;  in ext4_mb_pa_assert_overlap()
4257 		tmp_pa_start = tmp_pa->pa_lstart;  in ext4_mb_pa_assert_overlap()
4260 		spin_lock(&tmp_pa->pa_lock);  in ext4_mb_pa_assert_overlap()
4261 		if (tmp_pa->pa_deleted == 0)  in ext4_mb_pa_assert_overlap()
4263 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_pa_assert_overlap()
4265 	read_unlock(&ei->i_prealloc_lock);  in ext4_mb_pa_assert_overlap()
4282 	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);  in ext4_mb_pa_adjust_overlap()
4283 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_pa_adjust_overlap()
4286 	ext4_lblk_t new_start, tmp_pa_start, right_pa_start = -1;  in ext4_mb_pa_adjust_overlap()
4287 	loff_t new_end, tmp_pa_end, left_pa_end = -1;  in ext4_mb_pa_adjust_overlap()
4297 	read_lock(&ei->i_prealloc_lock);  in ext4_mb_pa_adjust_overlap()
4300 	for (iter = ei->i_prealloc_node.rb_node; iter;  in ext4_mb_pa_adjust_overlap()
4301 	     iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,  in ext4_mb_pa_adjust_overlap()
4305 		tmp_pa_start = tmp_pa->pa_lstart;  in ext4_mb_pa_adjust_overlap()
4309 		spin_lock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4310 		if (tmp_pa->pa_deleted == 0)  in ext4_mb_pa_adjust_overlap()
4311 			BUG_ON(!(ac->ac_o_ex.fe_logical >= tmp_pa_end ||  in ext4_mb_pa_adjust_overlap()
4312 				 ac->ac_o_ex.fe_logical < tmp_pa_start));  in ext4_mb_pa_adjust_overlap()
4313 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4321 		if (tmp_pa->pa_lstart < ac->ac_o_ex.fe_logical) {  in ext4_mb_pa_adjust_overlap()
4325 			tmp = rb_next(&left_pa->pa_node.inode_node);  in ext4_mb_pa_adjust_overlap()
4335 			tmp = rb_prev(&right_pa->pa_node.inode_node);  in ext4_mb_pa_adjust_overlap()
4346 		for (iter = &left_pa->pa_node.inode_node;;  in ext4_mb_pa_adjust_overlap()
4356 			spin_lock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4357 			if (tmp_pa->pa_deleted == 0) {  in ext4_mb_pa_adjust_overlap()
4358 				spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4361 			spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4366 		for (iter = &right_pa->pa_node.inode_node;;  in ext4_mb_pa_adjust_overlap()
4376 			spin_lock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4377 			if (tmp_pa->pa_deleted == 0) {  in ext4_mb_pa_adjust_overlap()
4378 				spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4381 			spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_pa_adjust_overlap()
4387 		BUG_ON(left_pa_end > ac->ac_o_ex.fe_logical);  in ext4_mb_pa_adjust_overlap()
4391 		right_pa_start = right_pa->pa_lstart;  in ext4_mb_pa_adjust_overlap()
4392 		BUG_ON(right_pa_start <= ac->ac_o_ex.fe_logical);  in ext4_mb_pa_adjust_overlap()
4405 	read_unlock(&ei->i_prealloc_lock);  in ext4_mb_pa_adjust_overlap()
4422 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_normalize_request()
4423 	struct ext4_super_block *es = sbi->s_es;  in ext4_mb_normalize_request()
4431 	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))  in ext4_mb_normalize_request()
4435 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))  in ext4_mb_normalize_request()
4440 	if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)  in ext4_mb_normalize_request()
4443 	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {  in ext4_mb_normalize_request()
4448 	bsbits = ac->ac_sb->s_blocksize_bits;  in ext4_mb_normalize_request()
4452 	size = extent_logical_end(sbi, &ac->ac_o_ex);  in ext4_mb_normalize_request()
4454 	if (size < i_size_read(ac->ac_inode))  in ext4_mb_normalize_request()
4455 		size = i_size_read(ac->ac_inode);  in ext4_mb_normalize_request()
4482 		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>  in ext4_mb_normalize_request()
4483 						(21 - bsbits)) << 21;  in ext4_mb_normalize_request()
4486 		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>  in ext4_mb_normalize_request()
4487 							(22 - bsbits)) << 22;  in ext4_mb_normalize_request()
4489 	} else if (NRL_CHECK_SIZE(EXT4_C2B(sbi, ac->ac_o_ex.fe_len),  in ext4_mb_normalize_request()
4491 		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>  in ext4_mb_normalize_request()
4492 							(23 - bsbits)) << 23;  in ext4_mb_normalize_request()
4495 		start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;  in ext4_mb_normalize_request()
4497 					      ac->ac_o_ex.fe_len) << bsbits;  in ext4_mb_normalize_request()
4508 	start = max(start, rounddown(ac->ac_o_ex.fe_logical,  in ext4_mb_normalize_request()
4509 			(ext4_lblk_t)EXT4_BLOCKS_PER_GROUP(ac->ac_sb)));  in ext4_mb_normalize_request()
4513 		size = EXT_MAX_BLOCKS - start;  in ext4_mb_normalize_request()
4516 	if (ar->pleft && start <= ar->lleft) {  in ext4_mb_normalize_request()
4517 		size -= ar->lleft + 1 - start;  in ext4_mb_normalize_request()
4518 		start = ar->lleft + 1;  in ext4_mb_normalize_request()
4520 	if (ar->pright && start + size - 1 >= ar->lright)  in ext4_mb_normalize_request()
4521 		size -= start + size - ar->lright;  in ext4_mb_normalize_request()
4527 	if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))  in ext4_mb_normalize_request()
4528 		size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);  in ext4_mb_normalize_request()
4534 	size = end - start;  in ext4_mb_normalize_request()
4540 	 * ac->ac_o_ex.fe_logical & fe_len should always lie within "start" and  in ext4_mb_normalize_request()
4546 	 * [pa_pstart + fe_logical - pa_lstart, fe_len/size] from the preallocated  in ext4_mb_normalize_request()
4551 	if (start + size <= ac->ac_o_ex.fe_logical ||  in ext4_mb_normalize_request()
4552 			start > ac->ac_o_ex.fe_logical) {  in ext4_mb_normalize_request()
4553 		ext4_msg(ac->ac_sb, KERN_ERR,  in ext4_mb_normalize_request()
4556 			 (unsigned long) ac->ac_o_ex.fe_logical);  in ext4_mb_normalize_request()
4559 	BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));  in ext4_mb_normalize_request()
4565 	ac->ac_g_ex.fe_logical = start;  in ext4_mb_normalize_request()
4566 	ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);  in ext4_mb_normalize_request()
4567 	ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;  in ext4_mb_normalize_request()
4570 	if (ar->pright && (ar->lright == (start + size)) &&  in ext4_mb_normalize_request()
4571 	    ar->pright >= size &&  in ext4_mb_normalize_request()
4572 	    ar->pright - size >= le32_to_cpu(es->s_first_data_block)) {  in ext4_mb_normalize_request()
4574 		ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,  in ext4_mb_normalize_request()
4575 						&ac->ac_g_ex.fe_group,  in ext4_mb_normalize_request()
4576 						&ac->ac_g_ex.fe_start);  in ext4_mb_normalize_request()
4577 		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;  in ext4_mb_normalize_request()
4579 	if (ar->pleft && (ar->lleft + 1 == start) &&  in ext4_mb_normalize_request()
4580 	    ar->pleft + 1 < ext4_blocks_count(es)) {  in ext4_mb_normalize_request()
4582 		ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,  in ext4_mb_normalize_request()
4583 						&ac->ac_g_ex.fe_group,  in ext4_mb_normalize_request()
4584 						&ac->ac_g_ex.fe_start);  in ext4_mb_normalize_request()
4585 		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;  in ext4_mb_normalize_request()
4588 	mb_debug(ac->ac_sb, "goal: %lld(was %lld) blocks at %u\n", size,  in ext4_mb_normalize_request()
4594 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_collect_stats()
4596 	if (sbi->s_mb_stats && ac->ac_g_ex.fe_len >= 1) {  in ext4_mb_collect_stats()
4597 		atomic_inc(&sbi->s_bal_reqs);  in ext4_mb_collect_stats()
4598 		atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);  in ext4_mb_collect_stats()
4599 		if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)  in ext4_mb_collect_stats()
4600 			atomic_inc(&sbi->s_bal_success);  in ext4_mb_collect_stats()
4602 		atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);  in ext4_mb_collect_stats()
4604 			atomic_add(ac->ac_cX_found[i], &sbi->s_bal_cX_ex_scanned[i]);  in ext4_mb_collect_stats()
4607 		atomic_add(ac->ac_groups_scanned, &sbi->s_bal_groups_scanned);  in ext4_mb_collect_stats()
4608 		if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&  in ext4_mb_collect_stats()
4609 				ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)  in ext4_mb_collect_stats()
4610 			atomic_inc(&sbi->s_bal_goals);  in ext4_mb_collect_stats()
4612 		if (ac->ac_f_ex.fe_len == ac->ac_orig_goal_len)  in ext4_mb_collect_stats()
4613 			atomic_inc(&sbi->s_bal_len_goals);  in ext4_mb_collect_stats()
4615 		if (ac->ac_found > sbi->s_mb_max_to_scan)  in ext4_mb_collect_stats()
4616 			atomic_inc(&sbi->s_bal_breaks);  in ext4_mb_collect_stats()
4619 	if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)  in ext4_mb_collect_stats()
4629  * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
4633 	struct ext4_prealloc_space *pa = ac->ac_pa;  in ext4_discard_allocated_blocks()
4638 		if (ac->ac_f_ex.fe_len == 0)  in ext4_discard_allocated_blocks()
4640 		err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);  in ext4_discard_allocated_blocks()
4649 		ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);  in ext4_discard_allocated_blocks()
4650 		mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,  in ext4_discard_allocated_blocks()
4651 			       ac->ac_f_ex.fe_len);  in ext4_discard_allocated_blocks()
4652 		ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);  in ext4_discard_allocated_blocks()
4656 	if (pa->pa_type == MB_INODE_PA) {  in ext4_discard_allocated_blocks()
4657 		spin_lock(&pa->pa_lock);  in ext4_discard_allocated_blocks()
4658 		pa->pa_free += ac->ac_b_ex.fe_len;  in ext4_discard_allocated_blocks()
4659 		spin_unlock(&pa->pa_lock);  in ext4_discard_allocated_blocks()
4669 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_use_inode_pa()
4675 	start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);  in ext4_mb_use_inode_pa()
4676 	end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),  in ext4_mb_use_inode_pa()
4677 		  start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));  in ext4_mb_use_inode_pa()
4678 	len = EXT4_NUM_B2C(sbi, end - start);  in ext4_mb_use_inode_pa()
4679 	ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,  in ext4_mb_use_inode_pa()
4680 					&ac->ac_b_ex.fe_start);  in ext4_mb_use_inode_pa()
4681 	ac->ac_b_ex.fe_len = len;  in ext4_mb_use_inode_pa()
4682 	ac->ac_status = AC_STATUS_FOUND;  in ext4_mb_use_inode_pa()
4683 	ac->ac_pa = pa;  in ext4_mb_use_inode_pa()
4685 	BUG_ON(start < pa->pa_pstart);  in ext4_mb_use_inode_pa()
4686 	BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));  in ext4_mb_use_inode_pa()
4687 	BUG_ON(pa->pa_free < len);  in ext4_mb_use_inode_pa()
4688 	BUG_ON(ac->ac_b_ex.fe_len <= 0);  in ext4_mb_use_inode_pa()
4689 	pa->pa_free -= len;  in ext4_mb_use_inode_pa()
4691 	mb_debug(ac->ac_sb, "use %llu/%d from inode pa %p\n", start, len, pa);  in ext4_mb_use_inode_pa()
4695  * use blocks preallocated to locality group
4700 	unsigned int len = ac->ac_o_ex.fe_len;  in ext4_mb_use_group_pa()
4702 	ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,  in ext4_mb_use_group_pa()
4703 					&ac->ac_b_ex.fe_group,  in ext4_mb_use_group_pa()
4704 					&ac->ac_b_ex.fe_start);  in ext4_mb_use_group_pa()
4705 	ac->ac_b_ex.fe_len = len;  in ext4_mb_use_group_pa()
4706 	ac->ac_status = AC_STATUS_FOUND;  in ext4_mb_use_group_pa()
4707 	ac->ac_pa = pa;  in ext4_mb_use_group_pa()
4712 	 * in on-disk bitmap -- see ext4_mb_release_context()  in ext4_mb_use_group_pa()
4715 	mb_debug(ac->ac_sb, "use %u/%u from group pa %p\n",  in ext4_mb_use_group_pa()
4716 		 pa->pa_lstart, len, pa);  in ext4_mb_use_group_pa()
4733 		atomic_inc(&pa->pa_count);  in ext4_mb_check_group_pa()
4736 	cur_distance = abs(goal_block - cpa->pa_pstart);  in ext4_mb_check_group_pa()
4737 	new_distance = abs(goal_block - pa->pa_pstart);  in ext4_mb_check_group_pa()
4743 	atomic_dec(&cpa->pa_count);  in ext4_mb_check_group_pa()
4744 	atomic_inc(&pa->pa_count);  in ext4_mb_check_group_pa()
4755 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_pa_goal_check()
4758 	if (likely(!(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)))  in ext4_mb_pa_goal_check()
4767 	start = pa->pa_pstart +  in ext4_mb_pa_goal_check()
4768 		(ac->ac_g_ex.fe_logical - pa->pa_lstart);  in ext4_mb_pa_goal_check()
4769 	if (ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex) != start)  in ext4_mb_pa_goal_check()
4772 	if (ac->ac_g_ex.fe_len > pa->pa_len -  in ext4_mb_pa_goal_check()
4773 	    EXT4_B2C(sbi, ac->ac_g_ex.fe_logical - pa->pa_lstart))  in ext4_mb_pa_goal_check()
4785 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_use_preallocated()
4787 	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);  in ext4_mb_use_preallocated()
4794 	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))  in ext4_mb_use_preallocated()
4798 	 * first, try per-file preallocation by searching the inode pa rbtree.  in ext4_mb_use_preallocated()
4804 	read_lock(&ei->i_prealloc_lock);  in ext4_mb_use_preallocated()
4806 	if (RB_EMPTY_ROOT(&ei->i_prealloc_node)) {  in ext4_mb_use_preallocated()
4814 	 * (tmp_pa->pa_lstart never changes so we can skip locking for it).  in ext4_mb_use_preallocated()
4816 	for (iter = ei->i_prealloc_node.rb_node; iter;  in ext4_mb_use_preallocated()
4817 	     iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,  in ext4_mb_use_preallocated()
4818 					    tmp_pa->pa_lstart, iter)) {  in ext4_mb_use_preallocated()
4828 	if (tmp_pa->pa_lstart > ac->ac_o_ex.fe_logical) {  in ext4_mb_use_preallocated()
4830 		tmp = rb_prev(&tmp_pa->pa_node.inode_node);  in ext4_mb_use_preallocated()
4845 	BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));  in ext4_mb_use_preallocated()
4852 	for (iter = &tmp_pa->pa_node.inode_node;; iter = rb_prev(iter)) {  in ext4_mb_use_preallocated()
4862 		spin_lock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4863 		if (tmp_pa->pa_deleted == 0) {  in ext4_mb_use_preallocated()
4873 			spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4877 	BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));  in ext4_mb_use_preallocated()
4878 	BUG_ON(tmp_pa->pa_deleted == 1);  in ext4_mb_use_preallocated()
4885 	if (ac->ac_o_ex.fe_logical >= pa_logical_end(sbi, tmp_pa)) {  in ext4_mb_use_preallocated()
4886 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4890 	/* non-extent files can't have physical blocks past 2^32 */  in ext4_mb_use_preallocated()
4891 	if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&  in ext4_mb_use_preallocated()
4892 	    (tmp_pa->pa_pstart + EXT4_C2B(sbi, tmp_pa->pa_len) >  in ext4_mb_use_preallocated()
4898 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4902 	if (tmp_pa->pa_free && likely(ext4_mb_pa_goal_check(ac, tmp_pa))) {  in ext4_mb_use_preallocated()
4903 		atomic_inc(&tmp_pa->pa_count);  in ext4_mb_use_preallocated()
4905 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4906 		read_unlock(&ei->i_prealloc_lock);  in ext4_mb_use_preallocated()
4936 		WARN_ON_ONCE(tmp_pa->pa_free == 0);  in ext4_mb_use_preallocated()
4938 	spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4940 	read_unlock(&ei->i_prealloc_lock);  in ext4_mb_use_preallocated()
4943 	if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))  in ext4_mb_use_preallocated()
4946 	/* inode may have no locality group for some reason */  in ext4_mb_use_preallocated()
4947 	lg = ac->ac_lg;  in ext4_mb_use_preallocated()
4950 	order  = fls(ac->ac_o_ex.fe_len) - 1;  in ext4_mb_use_preallocated()
4951 	if (order > PREALLOC_TB_SIZE - 1)  in ext4_mb_use_preallocated()
4953 		order = PREALLOC_TB_SIZE - 1;  in ext4_mb_use_preallocated()
4955 	goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);  in ext4_mb_use_preallocated()
4962 		list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[i],  in ext4_mb_use_preallocated()
4964 			spin_lock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4965 			if (tmp_pa->pa_deleted == 0 &&  in ext4_mb_use_preallocated()
4966 					tmp_pa->pa_free >= ac->ac_o_ex.fe_len) {  in ext4_mb_use_preallocated()
4971 			spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_use_preallocated()
4984  * used in in-core bitmap. buddy must be generated from this bitmap
5010 	list_for_each(cur, &grp->bb_prealloc_list) {  in ext4_mb_generate_from_pa()
5012 		spin_lock(&pa->pa_lock);  in ext4_mb_generate_from_pa()
5013 		ext4_get_group_no_and_offset(sb, pa->pa_pstart,  in ext4_mb_generate_from_pa()
5015 		len = pa->pa_len;  in ext4_mb_generate_from_pa()
5016 		spin_unlock(&pa->pa_lock);  in ext4_mb_generate_from_pa()
5031 	if (pa->pa_deleted) {  in ext4_mb_mark_pa_deleted()
5033 			     pa->pa_type, pa->pa_pstart, pa->pa_lstart,  in ext4_mb_mark_pa_deleted()
5034 			     pa->pa_len);  in ext4_mb_mark_pa_deleted()
5038 	pa->pa_deleted = 1;  in ext4_mb_mark_pa_deleted()
5040 	if (pa->pa_type == MB_INODE_PA) {  in ext4_mb_mark_pa_deleted()
5041 		ei = EXT4_I(pa->pa_inode);  in ext4_mb_mark_pa_deleted()
5042 		atomic_dec(&ei->i_prealloc_active);  in ext4_mb_mark_pa_deleted()
5049 	BUG_ON(atomic_read(&pa->pa_count));  in ext4_mb_pa_free()
5050 	BUG_ON(pa->pa_deleted == 0);  in ext4_mb_pa_free()
5071 	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);  in ext4_mb_put_pa()
5074 	spin_lock(&pa->pa_lock);  in ext4_mb_put_pa()
5075 	if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {  in ext4_mb_put_pa()
5076 		spin_unlock(&pa->pa_lock);  in ext4_mb_put_pa()
5080 	if (pa->pa_deleted == 1) {  in ext4_mb_put_pa()
5081 		spin_unlock(&pa->pa_lock);  in ext4_mb_put_pa()
5086 	spin_unlock(&pa->pa_lock);  in ext4_mb_put_pa()
5088 	grp_blk = pa->pa_pstart;  in ext4_mb_put_pa()
5090 	 * If doing group-based preallocation, pa_pstart may be in the  in ext4_mb_put_pa()
5093 	if (pa->pa_type == MB_GROUP_PA)  in ext4_mb_put_pa()
5094 		grp_blk--;  in ext4_mb_put_pa()
5103 	 *  copy on-disk bitmap to buddy  in ext4_mb_put_pa()
5104 	 *  					mark B in on-disk bitmap  in ext4_mb_put_pa()
5113 	list_del(&pa->pa_group_list);  in ext4_mb_put_pa()
5116 	if (pa->pa_type == MB_INODE_PA) {  in ext4_mb_put_pa()
5117 		write_lock(pa->pa_node_lock.inode_lock);  in ext4_mb_put_pa()
5118 		rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);  in ext4_mb_put_pa()
5119 		write_unlock(pa->pa_node_lock.inode_lock);  in ext4_mb_put_pa()
5122 		spin_lock(pa->pa_node_lock.lg_lock);  in ext4_mb_put_pa()
5123 		list_del_rcu(&pa->pa_node.lg_list);  in ext4_mb_put_pa()
5124 		spin_unlock(pa->pa_node_lock.lg_lock);  in ext4_mb_put_pa()
5125 		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_mb_put_pa()
5131 	struct rb_node **iter = &root->rb_node, *parent = NULL;  in ext4_mb_pa_rb_insert()
5140 		iter_start = iter_pa->pa_lstart;  in ext4_mb_pa_rb_insert()
5141 		new_start = new_pa->pa_lstart;  in ext4_mb_pa_rb_insert()
5145 			iter = &((*iter)->rb_left);  in ext4_mb_pa_rb_insert()
5147 			iter = &((*iter)->rb_right);  in ext4_mb_pa_rb_insert()
5160 	struct super_block *sb = ac->ac_sb;  in ext4_mb_new_inode_pa()
5167 	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);  in ext4_mb_new_inode_pa()
5168 	BUG_ON(ac->ac_status != AC_STATUS_FOUND);  in ext4_mb_new_inode_pa()
5169 	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));  in ext4_mb_new_inode_pa()
5170 	BUG_ON(ac->ac_pa == NULL);  in ext4_mb_new_inode_pa()
5172 	pa = ac->ac_pa;  in ext4_mb_new_inode_pa()
5174 	if (ac->ac_b_ex.fe_len < ac->ac_orig_goal_len) {  in ext4_mb_new_inode_pa()
5176 			.fe_logical = ac->ac_g_ex.fe_logical,  in ext4_mb_new_inode_pa()
5177 			.fe_len = ac->ac_orig_goal_len,  in ext4_mb_new_inode_pa()
5180 		loff_t o_ex_end = extent_logical_end(sbi, &ac->ac_o_ex);  in ext4_mb_new_inode_pa()
5187 		 * orig_ex:2045/2055(10), isize:8417280 -> normalized:0/2048  in ext4_mb_new_inode_pa()
5188 		 * best_ex:0/200(200) -> adjusted: 1848/2048(200)  in ext4_mb_new_inode_pa()
5190 		BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);  in ext4_mb_new_inode_pa()
5191 		BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);  in ext4_mb_new_inode_pa()
5204 		ex.fe_len = ac->ac_b_ex.fe_len;  in ext4_mb_new_inode_pa()
5206 		ex.fe_logical = orig_goal_end - EXT4_C2B(sbi, ex.fe_len);  in ext4_mb_new_inode_pa()
5207 		if (ac->ac_o_ex.fe_logical >= ex.fe_logical)  in ext4_mb_new_inode_pa()
5210 		ex.fe_logical = ac->ac_g_ex.fe_logical;  in ext4_mb_new_inode_pa()
5214 		ex.fe_logical = ac->ac_o_ex.fe_logical;  in ext4_mb_new_inode_pa()
5216 		ac->ac_b_ex.fe_logical = ex.fe_logical;  in ext4_mb_new_inode_pa()
5218 		BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);  in ext4_mb_new_inode_pa()
5222 	pa->pa_lstart = ac->ac_b_ex.fe_logical;  in ext4_mb_new_inode_pa()
5223 	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_new_inode_pa()
5224 	pa->pa_len = ac->ac_b_ex.fe_len;  in ext4_mb_new_inode_pa()
5225 	pa->pa_free = pa->pa_len;  in ext4_mb_new_inode_pa()
5226 	spin_lock_init(&pa->pa_lock);  in ext4_mb_new_inode_pa()
5227 	INIT_LIST_HEAD(&pa->pa_group_list);  in ext4_mb_new_inode_pa()
5228 	pa->pa_deleted = 0;  in ext4_mb_new_inode_pa()
5229 	pa->pa_type = MB_INODE_PA;  in ext4_mb_new_inode_pa()
5231 	mb_debug(sb, "new inode pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,  in ext4_mb_new_inode_pa()
5232 		 pa->pa_len, pa->pa_lstart);  in ext4_mb_new_inode_pa()
5235 	atomic_add(pa->pa_free, &sbi->s_mb_preallocated);  in ext4_mb_new_inode_pa()
5238 	ei = EXT4_I(ac->ac_inode);  in ext4_mb_new_inode_pa()
5239 	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);  in ext4_mb_new_inode_pa()
5243 	pa->pa_node_lock.inode_lock = &ei->i_prealloc_lock;  in ext4_mb_new_inode_pa()
5244 	pa->pa_inode = ac->ac_inode;  in ext4_mb_new_inode_pa()
5246 	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);  in ext4_mb_new_inode_pa()
5248 	write_lock(pa->pa_node_lock.inode_lock);  in ext4_mb_new_inode_pa()
5249 	ext4_mb_pa_rb_insert(&ei->i_prealloc_node, &pa->pa_node.inode_node);  in ext4_mb_new_inode_pa()
5250 	write_unlock(pa->pa_node_lock.inode_lock);  in ext4_mb_new_inode_pa()
5251 	atomic_inc(&ei->i_prealloc_active);  in ext4_mb_new_inode_pa()
5255  * creates new preallocated space for locality group inodes belongs to
5260 	struct super_block *sb = ac->ac_sb;  in ext4_mb_new_group_pa()
5266 	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);  in ext4_mb_new_group_pa()
5267 	BUG_ON(ac->ac_status != AC_STATUS_FOUND);  in ext4_mb_new_group_pa()
5268 	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));  in ext4_mb_new_group_pa()
5269 	BUG_ON(ac->ac_pa == NULL);  in ext4_mb_new_group_pa()
5271 	pa = ac->ac_pa;  in ext4_mb_new_group_pa()
5273 	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_new_group_pa()
5274 	pa->pa_lstart = pa->pa_pstart;  in ext4_mb_new_group_pa()
5275 	pa->pa_len = ac->ac_b_ex.fe_len;  in ext4_mb_new_group_pa()
5276 	pa->pa_free = pa->pa_len;  in ext4_mb_new_group_pa()
5277 	spin_lock_init(&pa->pa_lock);  in ext4_mb_new_group_pa()
5278 	INIT_LIST_HEAD(&pa->pa_node.lg_list);  in ext4_mb_new_group_pa()
5279 	INIT_LIST_HEAD(&pa->pa_group_list);  in ext4_mb_new_group_pa()
5280 	pa->pa_deleted = 0;  in ext4_mb_new_group_pa()
5281 	pa->pa_type = MB_GROUP_PA;  in ext4_mb_new_group_pa()
5283 	mb_debug(sb, "new group pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,  in ext4_mb_new_group_pa()
5284 		 pa->pa_len, pa->pa_lstart);  in ext4_mb_new_group_pa()
5288 	atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);  in ext4_mb_new_group_pa()
5290 	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);  in ext4_mb_new_group_pa()
5293 	lg = ac->ac_lg;  in ext4_mb_new_group_pa()
5296 	pa->pa_node_lock.lg_lock = &lg->lg_prealloc_lock;  in ext4_mb_new_group_pa()
5297 	pa->pa_inode = NULL;  in ext4_mb_new_group_pa()
5299 	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);  in ext4_mb_new_group_pa()
5309 	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)  in ext4_mb_new_preallocation()
5316  * finds all unused blocks in on-disk bitmap, frees them in
5317  * in-core bitmap and buddy.
5321  * TODO: optimize the case when there are no in-core structures yet
5327 	struct super_block *sb = e4b->bd_sb;  in ext4_mb_release_inode_pa()
5336 	BUG_ON(pa->pa_deleted == 0);  in ext4_mb_release_inode_pa()
5337 	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);  in ext4_mb_release_inode_pa()
5338 	grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);  in ext4_mb_release_inode_pa()
5339 	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);  in ext4_mb_release_inode_pa()
5340 	end = bit + pa->pa_len;  in ext4_mb_release_inode_pa()
5343 		bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);  in ext4_mb_release_inode_pa()
5346 		next = mb_find_next_bit(bitmap_bh->b_data, end, bit);  in ext4_mb_release_inode_pa()
5349 			 (unsigned) next - bit, (unsigned) group);  in ext4_mb_release_inode_pa()
5350 		free += next - bit;  in ext4_mb_release_inode_pa()
5352 		trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);  in ext4_mb_release_inode_pa()
5355 					       next - bit);  in ext4_mb_release_inode_pa()
5356 		mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);  in ext4_mb_release_inode_pa()
5359 	if (free != pa->pa_free) {  in ext4_mb_release_inode_pa()
5360 		ext4_msg(e4b->bd_sb, KERN_CRIT,  in ext4_mb_release_inode_pa()
5362 			 pa, (unsigned long) pa->pa_lstart,  in ext4_mb_release_inode_pa()
5363 			 (unsigned long) pa->pa_pstart,  in ext4_mb_release_inode_pa()
5364 			 pa->pa_len);  in ext4_mb_release_inode_pa()
5366 					free, pa->pa_free);  in ext4_mb_release_inode_pa()
5372 	atomic_add(free, &sbi->s_mb_discarded);  in ext4_mb_release_inode_pa()
5379 	struct super_block *sb = e4b->bd_sb;  in ext4_mb_release_group_pa()
5384 	BUG_ON(pa->pa_deleted == 0);  in ext4_mb_release_group_pa()
5385 	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);  in ext4_mb_release_group_pa()
5386 	if (unlikely(group != e4b->bd_group && pa->pa_len != 0)) {  in ext4_mb_release_group_pa()
5388 			     e4b->bd_group, group, pa->pa_pstart);  in ext4_mb_release_group_pa()
5391 	mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);  in ext4_mb_release_group_pa()
5392 	atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);  in ext4_mb_release_group_pa()
5393 	trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);  in ext4_mb_release_group_pa()
5400  * - when do we discard
5402  * - how many do we discard
5421 	if (list_empty(&grp->bb_prealloc_list))  in ext4_mb_discard_group_preallocations()
5427 		ext4_error_err(sb, -err,  in ext4_mb_discard_group_preallocations()
5443 				&grp->bb_prealloc_list, pa_group_list) {  in ext4_mb_discard_group_preallocations()
5444 		spin_lock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
5445 		if (atomic_read(&pa->pa_count)) {  in ext4_mb_discard_group_preallocations()
5446 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
5450 		if (pa->pa_deleted) {  in ext4_mb_discard_group_preallocations()
5451 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
5462 		free += pa->pa_free;  in ext4_mb_discard_group_preallocations()
5464 		spin_unlock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
5466 		list_del(&pa->pa_group_list);  in ext4_mb_discard_group_preallocations()
5467 		list_add(&pa->u.pa_tmp_list, &list);  in ext4_mb_discard_group_preallocations()
5473 		/* remove from object (inode or locality group) */  in ext4_mb_discard_group_preallocations()
5474 		if (pa->pa_type == MB_GROUP_PA) {  in ext4_mb_discard_group_preallocations()
5475 			spin_lock(pa->pa_node_lock.lg_lock);  in ext4_mb_discard_group_preallocations()
5476 			list_del_rcu(&pa->pa_node.lg_list);  in ext4_mb_discard_group_preallocations()
5477 			spin_unlock(pa->pa_node_lock.lg_lock);  in ext4_mb_discard_group_preallocations()
5479 			write_lock(pa->pa_node_lock.inode_lock);  in ext4_mb_discard_group_preallocations()
5480 			ei = EXT4_I(pa->pa_inode);  in ext4_mb_discard_group_preallocations()
5481 			rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);  in ext4_mb_discard_group_preallocations()
5482 			write_unlock(pa->pa_node_lock.inode_lock);  in ext4_mb_discard_group_preallocations()
5485 		list_del(&pa->u.pa_tmp_list);  in ext4_mb_discard_group_preallocations()
5487 		if (pa->pa_type == MB_GROUP_PA) {  in ext4_mb_discard_group_preallocations()
5489 			call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_mb_discard_group_preallocations()
5501 		 free, group, grp->bb_free);  in ext4_mb_discard_group_preallocations()
5506  * releases all non-used preallocated blocks for given inode
5517 	struct super_block *sb = inode->i_sb;  in ext4_discard_preallocations()
5526 	if (!S_ISREG(inode->i_mode))  in ext4_discard_preallocations()
5529 	if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)  in ext4_discard_preallocations()
5533 		 inode->i_ino);  in ext4_discard_preallocations()
5535 			atomic_read(&ei->i_prealloc_active));  in ext4_discard_preallocations()
5539 	write_lock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
5540 	for (iter = rb_first(&ei->i_prealloc_node); iter;  in ext4_discard_preallocations()
5544 		BUG_ON(pa->pa_node_lock.inode_lock != &ei->i_prealloc_lock);  in ext4_discard_preallocations()
5546 		spin_lock(&pa->pa_lock);  in ext4_discard_preallocations()
5547 		if (atomic_read(&pa->pa_count)) {  in ext4_discard_preallocations()
5548 			/* this shouldn't happen often - nobody should  in ext4_discard_preallocations()
5550 			spin_unlock(&pa->pa_lock);  in ext4_discard_preallocations()
5551 			write_unlock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
5553 				 "uh-oh! used pa while discarding");  in ext4_discard_preallocations()
5559 		if (pa->pa_deleted == 0) {  in ext4_discard_preallocations()
5561 			spin_unlock(&pa->pa_lock);  in ext4_discard_preallocations()
5562 			rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);  in ext4_discard_preallocations()
5563 			list_add(&pa->u.pa_tmp_list, &list);  in ext4_discard_preallocations()
5568 		spin_unlock(&pa->pa_lock);  in ext4_discard_preallocations()
5569 		write_unlock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
5574 		 * ->clear_inode() the inode will get freed  in ext4_discard_preallocations()
5577 		 * freed memory, bad-bad-bad */  in ext4_discard_preallocations()
5581 		 * of ->clear_inode(), but not in case of  in ext4_discard_preallocations()
5586 	write_unlock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
5589 		BUG_ON(pa->pa_type != MB_INODE_PA);  in ext4_discard_preallocations()
5590 		group = ext4_get_group_number(sb, pa->pa_pstart);  in ext4_discard_preallocations()
5595 			ext4_error_err(sb, -err, "Error %d loading buddy information for %u",  in ext4_discard_preallocations()
5603 			ext4_error_err(sb, -err, "Error %d reading block bitmap for %u",  in ext4_discard_preallocations()
5610 		list_del(&pa->pa_group_list);  in ext4_discard_preallocations()
5617 		list_del(&pa->u.pa_tmp_list);  in ext4_discard_preallocations()
5629 		return -ENOMEM;  in ext4_mb_pa_alloc()
5630 	atomic_set(&pa->pa_count, 1);  in ext4_mb_pa_alloc()
5631 	ac->ac_pa = pa;  in ext4_mb_pa_alloc()
5637 	struct ext4_prealloc_space *pa = ac->ac_pa;  in ext4_mb_pa_put_free()
5640 	ac->ac_pa = NULL;  in ext4_mb_pa_put_free()
5641 	WARN_ON(!atomic_dec_and_test(&pa->pa_count));  in ext4_mb_pa_put_free()
5645 	 * been added to grp->bb_prealloc_list. So we don't need to lock it  in ext4_mb_pa_put_free()
5647 	pa->pa_deleted = 1;  in ext4_mb_pa_put_free()
5670 		list_for_each(cur, &grp->bb_prealloc_list) {  in ext4_mb_show_pa()
5673 			spin_lock(&pa->pa_lock);  in ext4_mb_show_pa()
5674 			ext4_get_group_no_and_offset(sb, pa->pa_pstart,  in ext4_mb_show_pa()
5676 			spin_unlock(&pa->pa_lock);  in ext4_mb_show_pa()
5678 				 pa->pa_len);  in ext4_mb_show_pa()
5681 		mb_debug(sb, "%u: %d/%d\n", i, grp->bb_free,  in ext4_mb_show_pa()
5682 			 grp->bb_fragments);  in ext4_mb_show_pa()
5688 	struct super_block *sb = ac->ac_sb;  in ext4_mb_show_ac()
5696 			ac->ac_status, ac->ac_flags);  in ext4_mb_show_ac()
5700 			(unsigned long)ac->ac_o_ex.fe_group,  in ext4_mb_show_ac()
5701 			(unsigned long)ac->ac_o_ex.fe_start,  in ext4_mb_show_ac()
5702 			(unsigned long)ac->ac_o_ex.fe_len,  in ext4_mb_show_ac()
5703 			(unsigned long)ac->ac_o_ex.fe_logical,  in ext4_mb_show_ac()
5704 			(unsigned long)ac->ac_g_ex.fe_group,  in ext4_mb_show_ac()
5705 			(unsigned long)ac->ac_g_ex.fe_start,  in ext4_mb_show_ac()
5706 			(unsigned long)ac->ac_g_ex.fe_len,  in ext4_mb_show_ac()
5707 			(unsigned long)ac->ac_g_ex.fe_logical,  in ext4_mb_show_ac()
5708 			(unsigned long)ac->ac_b_ex.fe_group,  in ext4_mb_show_ac()
5709 			(unsigned long)ac->ac_b_ex.fe_start,  in ext4_mb_show_ac()
5710 			(unsigned long)ac->ac_b_ex.fe_len,  in ext4_mb_show_ac()
5711 			(unsigned long)ac->ac_b_ex.fe_logical,  in ext4_mb_show_ac()
5712 			(int)ac->ac_criteria);  in ext4_mb_show_ac()
5713 	mb_debug(sb, "%u found", ac->ac_found);  in ext4_mb_show_ac()
5714 	mb_debug(sb, "used pa: %s, ", ac->ac_pa ? "yes" : "no");  in ext4_mb_show_ac()
5715 	if (ac->ac_pa)  in ext4_mb_show_ac()
5716 		mb_debug(sb, "pa_type %s\n", ac->ac_pa->pa_type == MB_GROUP_PA ?  in ext4_mb_show_ac()
5726 	ext4_mb_show_pa(ac->ac_sb);  in ext4_mb_show_ac()
5731  * We use locality group preallocation for small size file. The size of the
5739 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_group_or_file()
5740 	int bsbits = ac->ac_sb->s_blocksize_bits;  in ext4_mb_group_or_file()
5744 	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))  in ext4_mb_group_or_file()
5747 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))  in ext4_mb_group_or_file()
5750 	group_pa_eligible = sbi->s_mb_group_prealloc > 0;  in ext4_mb_group_or_file()
5752 	size = extent_logical_end(sbi, &ac->ac_o_ex);  in ext4_mb_group_or_file()
5753 	isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)  in ext4_mb_group_or_file()
5758 	    !inode_is_open_for_write(ac->ac_inode))  in ext4_mb_group_or_file()
5763 	if (size > sbi->s_mb_stream_request)  in ext4_mb_group_or_file()
5768 			ac->ac_flags |= EXT4_MB_STREAM_ALLOC;  in ext4_mb_group_or_file()
5770 			ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;  in ext4_mb_group_or_file()
5774 	BUG_ON(ac->ac_lg != NULL);  in ext4_mb_group_or_file()
5776 	 * locality group prealloc space are per cpu. The reason for having  in ext4_mb_group_or_file()
5777 	 * per cpu locality group is to reduce the contention between block  in ext4_mb_group_or_file()
5780 	ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);  in ext4_mb_group_or_file()
5783 	ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;  in ext4_mb_group_or_file()
5786 	mutex_lock(&ac->ac_lg->lg_mutex);  in ext4_mb_group_or_file()
5793 	struct super_block *sb = ar->inode->i_sb;  in ext4_mb_initialize_context()
5795 	struct ext4_super_block *es = sbi->s_es;  in ext4_mb_initialize_context()
5802 	len = ar->len;  in ext4_mb_initialize_context()
5809 	goal = ar->goal;  in ext4_mb_initialize_context()
5810 	if (goal < le32_to_cpu(es->s_first_data_block) ||  in ext4_mb_initialize_context()
5812 		goal = le32_to_cpu(es->s_first_data_block);  in ext4_mb_initialize_context()
5816 	ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);  in ext4_mb_initialize_context()
5817 	ac->ac_status = AC_STATUS_CONTINUE;  in ext4_mb_initialize_context()
5818 	ac->ac_sb = sb;  in ext4_mb_initialize_context()
5819 	ac->ac_inode = ar->inode;  in ext4_mb_initialize_context()
5820 	ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;  in ext4_mb_initialize_context()
5821 	ac->ac_o_ex.fe_group = group;  in ext4_mb_initialize_context()
5822 	ac->ac_o_ex.fe_start = block;  in ext4_mb_initialize_context()
5823 	ac->ac_o_ex.fe_len = len;  in ext4_mb_initialize_context()
5824 	ac->ac_g_ex = ac->ac_o_ex;  in ext4_mb_initialize_context()
5825 	ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;  in ext4_mb_initialize_context()
5826 	ac->ac_flags = ar->flags;  in ext4_mb_initialize_context()
5829 	 * locality group. this is a policy, actually */  in ext4_mb_initialize_context()
5834 			(unsigned) ar->len, (unsigned) ar->logical,  in ext4_mb_initialize_context()
5835 			(unsigned) ar->goal, ac->ac_flags, ac->ac_2order,  in ext4_mb_initialize_context()
5836 			(unsigned) ar->lleft, (unsigned) ar->pleft,  in ext4_mb_initialize_context()
5837 			(unsigned) ar->lright, (unsigned) ar->pright,  in ext4_mb_initialize_context()
5838 			inode_is_open_for_write(ar->inode) ? "" : "non-");  in ext4_mb_initialize_context()
5851 	mb_debug(sb, "discard locality group preallocation\n");  in ext4_mb_discard_lg_preallocations()
5853 	spin_lock(&lg->lg_prealloc_lock);  in ext4_mb_discard_lg_preallocations()
5854 	list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],  in ext4_mb_discard_lg_preallocations()
5856 				lockdep_is_held(&lg->lg_prealloc_lock)) {  in ext4_mb_discard_lg_preallocations()
5857 		spin_lock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
5858 		if (atomic_read(&pa->pa_count)) {  in ext4_mb_discard_lg_preallocations()
5864 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
5867 		if (pa->pa_deleted) {  in ext4_mb_discard_lg_preallocations()
5868 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
5872 		BUG_ON(pa->pa_type != MB_GROUP_PA);  in ext4_mb_discard_lg_preallocations()
5876 		spin_unlock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
5878 		list_del_rcu(&pa->pa_node.lg_list);  in ext4_mb_discard_lg_preallocations()
5879 		list_add(&pa->u.pa_tmp_list, &discard_list);  in ext4_mb_discard_lg_preallocations()
5881 		total_entries--;  in ext4_mb_discard_lg_preallocations()
5892 	spin_unlock(&lg->lg_prealloc_lock);  in ext4_mb_discard_lg_preallocations()
5897 		group = ext4_get_group_number(sb, pa->pa_pstart);  in ext4_mb_discard_lg_preallocations()
5901 			ext4_error_err(sb, -err, "Error %d loading buddy information for %u",  in ext4_mb_discard_lg_preallocations()
5906 		list_del(&pa->pa_group_list);  in ext4_mb_discard_lg_preallocations()
5911 		list_del(&pa->u.pa_tmp_list);  in ext4_mb_discard_lg_preallocations()
5912 		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_mb_discard_lg_preallocations()
5928 	struct super_block *sb = ac->ac_sb;  in ext4_mb_add_n_trim()
5929 	struct ext4_locality_group *lg = ac->ac_lg;  in ext4_mb_add_n_trim()
5930 	struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;  in ext4_mb_add_n_trim()
5932 	order = fls(pa->pa_free) - 1;  in ext4_mb_add_n_trim()
5933 	if (order > PREALLOC_TB_SIZE - 1)  in ext4_mb_add_n_trim()
5935 		order = PREALLOC_TB_SIZE - 1;  in ext4_mb_add_n_trim()
5937 	spin_lock(&lg->lg_prealloc_lock);  in ext4_mb_add_n_trim()
5938 	list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],  in ext4_mb_add_n_trim()
5940 				lockdep_is_held(&lg->lg_prealloc_lock)) {  in ext4_mb_add_n_trim()
5941 		spin_lock(&tmp_pa->pa_lock);  in ext4_mb_add_n_trim()
5942 		if (tmp_pa->pa_deleted) {  in ext4_mb_add_n_trim()
5943 			spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_add_n_trim()
5946 		if (!added && pa->pa_free < tmp_pa->pa_free) {  in ext4_mb_add_n_trim()
5948 			list_add_tail_rcu(&pa->pa_node.lg_list,  in ext4_mb_add_n_trim()
5949 						&tmp_pa->pa_node.lg_list);  in ext4_mb_add_n_trim()
5956 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_add_n_trim()
5960 		list_add_tail_rcu(&pa->pa_node.lg_list,  in ext4_mb_add_n_trim()
5961 					&lg->lg_prealloc_list[order]);  in ext4_mb_add_n_trim()
5962 	spin_unlock(&lg->lg_prealloc_lock);  in ext4_mb_add_n_trim()
5975 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_release_context()
5976 	struct ext4_prealloc_space *pa = ac->ac_pa;  in ext4_mb_release_context()
5978 		if (pa->pa_type == MB_GROUP_PA) {  in ext4_mb_release_context()
5980 			spin_lock(&pa->pa_lock);  in ext4_mb_release_context()
5981 			pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_release_context()
5982 			pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_release_context()
5983 			pa->pa_free -= ac->ac_b_ex.fe_len;  in ext4_mb_release_context()
5984 			pa->pa_len -= ac->ac_b_ex.fe_len;  in ext4_mb_release_context()
5985 			spin_unlock(&pa->pa_lock);  in ext4_mb_release_context()
5993 			if (likely(pa->pa_free)) {  in ext4_mb_release_context()
5994 				spin_lock(pa->pa_node_lock.lg_lock);  in ext4_mb_release_context()
5995 				list_del_rcu(&pa->pa_node.lg_list);  in ext4_mb_release_context()
5996 				spin_unlock(pa->pa_node_lock.lg_lock);  in ext4_mb_release_context()
6001 		ext4_mb_put_pa(ac, ac->ac_sb, pa);  in ext4_mb_release_context()
6003 	if (ac->ac_bitmap_folio)  in ext4_mb_release_context()
6004 		folio_put(ac->ac_bitmap_folio);  in ext4_mb_release_context()
6005 	if (ac->ac_buddy_folio)  in ext4_mb_release_context()
6006 		folio_put(ac->ac_buddy_folio);  in ext4_mb_release_context()
6007 	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)  in ext4_mb_release_context()
6008 		mutex_unlock(&ac->ac_lg->lg_mutex);  in ext4_mb_release_context()
6027 		needed -= ret;  in ext4_mb_discard_preallocations()
6046 	freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);  in ext4_mb_discard_preallocations_should_retry()
6052 	if (!(ac->ac_flags & EXT4_MB_STRICT_CHECK) || seq_retry != *seq) {  in ext4_mb_discard_preallocations_should_retry()
6053 		ac->ac_flags |= EXT4_MB_STRICT_CHECK;  in ext4_mb_discard_preallocations_should_retry()
6072 	struct super_block *sb = ar->inode->i_sb;  in ext4_mb_new_blocks_simple()
6079 	struct ext4_super_block *es = sbi->s_es;  in ext4_mb_new_blocks_simple()
6081 	goal = ar->goal;  in ext4_mb_new_blocks_simple()
6082 	if (goal < le32_to_cpu(es->s_first_data_block) ||  in ext4_mb_new_blocks_simple()
6084 		goal = le32_to_cpu(es->s_first_data_block);  in ext4_mb_new_blocks_simple()
6086 	ar->len = 0;  in ext4_mb_new_blocks_simple()
6088 	for (nr = ext4_get_groups_count(sb); nr > 0; nr--) {  in ext4_mb_new_blocks_simple()
6097 			i = mb_find_next_zero_bit(bitmap_bh->b_data, max,  in ext4_mb_new_blocks_simple()
6119 		*errp = -ENOSPC;  in ext4_mb_new_blocks_simple()
6125 	ar->len = 1;  in ext4_mb_new_blocks_simple()
6149 	sb = ar->inode->i_sb;  in ext4_mb_new_blocks()
6153 	if (sbi->s_mount_state & EXT4_FC_REPLAY)  in ext4_mb_new_blocks()
6157 	if (ext4_is_quota_file(ar->inode))  in ext4_mb_new_blocks()
6158 		ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;  in ext4_mb_new_blocks()
6160 	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {  in ext4_mb_new_blocks()
6165 		while (ar->len &&  in ext4_mb_new_blocks()
6166 			ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {  in ext4_mb_new_blocks()
6170 			ar->len = ar->len >> 1;  in ext4_mb_new_blocks()
6172 		if (!ar->len) {  in ext4_mb_new_blocks()
6174 			*errp = -ENOSPC;  in ext4_mb_new_blocks()
6177 		reserv_clstrs = ar->len;  in ext4_mb_new_blocks()
6178 		if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {  in ext4_mb_new_blocks()
6179 			dquot_alloc_block_nofail(ar->inode,  in ext4_mb_new_blocks()
6180 						 EXT4_C2B(sbi, ar->len));  in ext4_mb_new_blocks()
6182 			while (ar->len &&  in ext4_mb_new_blocks()
6183 				dquot_alloc_block(ar->inode,  in ext4_mb_new_blocks()
6184 						  EXT4_C2B(sbi, ar->len))) {  in ext4_mb_new_blocks()
6186 				ar->flags |= EXT4_MB_HINT_NOPREALLOC;  in ext4_mb_new_blocks()
6187 				ar->len--;  in ext4_mb_new_blocks()
6190 		inquota = ar->len;  in ext4_mb_new_blocks()
6191 		if (ar->len == 0) {  in ext4_mb_new_blocks()
6192 			*errp = -EDQUOT;  in ext4_mb_new_blocks()
6199 		ar->len = 0;  in ext4_mb_new_blocks()
6200 		*errp = -ENOMEM;  in ext4_mb_new_blocks()
6206 	ac->ac_op = EXT4_MB_HISTORY_PREALLOC;  in ext4_mb_new_blocks()
6209 		ac->ac_op = EXT4_MB_HISTORY_ALLOC;  in ext4_mb_new_blocks()
6219 		 * pa allocated above is added to grp->bb_prealloc_list only  in ext4_mb_new_blocks()
6221 		 * ac->ac_status == AC_STATUS_FOUND.  in ext4_mb_new_blocks()
6222 		 * And error from above mean ac->ac_status != AC_STATUS_FOUND  in ext4_mb_new_blocks()
6230 		if (ac->ac_status == AC_STATUS_FOUND &&  in ext4_mb_new_blocks()
6231 			ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)  in ext4_mb_new_blocks()
6234 	if (likely(ac->ac_status == AC_STATUS_FOUND)) {  in ext4_mb_new_blocks()
6240 			block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_new_blocks()
6241 			ar->len = ac->ac_b_ex.fe_len;  in ext4_mb_new_blocks()
6252 		*errp = -ENOSPC;  in ext4_mb_new_blocks()
6257 		ac->ac_b_ex.fe_len = 0;  in ext4_mb_new_blocks()
6258 		ar->len = 0;  in ext4_mb_new_blocks()
6264 	if (inquota && ar->len < inquota)  in ext4_mb_new_blocks()
6265 		dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));  in ext4_mb_new_blocks()
6266 	if (!ar->len) {  in ext4_mb_new_blocks()
6267 		if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)  in ext4_mb_new_blocks()
6269 			percpu_counter_sub(&sbi->s_dirtyclusters_counter,  in ext4_mb_new_blocks()
6288 	if ((entry->efd_tid != new_entry->efd_tid) ||  in ext4_try_merge_freed_extent()
6289 	    (entry->efd_group != new_entry->efd_group))  in ext4_try_merge_freed_extent()
6291 	if (entry->efd_start_cluster + entry->efd_count ==  in ext4_try_merge_freed_extent()
6292 	    new_entry->efd_start_cluster) {  in ext4_try_merge_freed_extent()
6293 		new_entry->efd_start_cluster = entry->efd_start_cluster;  in ext4_try_merge_freed_extent()
6294 		new_entry->efd_count += entry->efd_count;  in ext4_try_merge_freed_extent()
6295 	} else if (new_entry->efd_start_cluster + new_entry->efd_count ==  in ext4_try_merge_freed_extent()
6296 		   entry->efd_start_cluster) {  in ext4_try_merge_freed_extent()
6297 		new_entry->efd_count += entry->efd_count;  in ext4_try_merge_freed_extent()
6300 	spin_lock(&sbi->s_md_lock);  in ext4_try_merge_freed_extent()
6301 	list_del(&entry->efd_list);  in ext4_try_merge_freed_extent()
6302 	spin_unlock(&sbi->s_md_lock);  in ext4_try_merge_freed_extent()
6303 	rb_erase(&entry->efd_node, entry_rb_root);  in ext4_try_merge_freed_extent()
6311 	ext4_group_t group = e4b->bd_group;  in ext4_mb_free_metadata()
6313 	ext4_grpblk_t clusters = new_entry->efd_count;  in ext4_mb_free_metadata()
6315 	struct ext4_group_info *db = e4b->bd_info;  in ext4_mb_free_metadata()
6316 	struct super_block *sb = e4b->bd_sb;  in ext4_mb_free_metadata()
6318 	struct rb_node **n = &db->bb_free_root.rb_node, *node;  in ext4_mb_free_metadata()
6322 	BUG_ON(e4b->bd_bitmap_folio == NULL);  in ext4_mb_free_metadata()
6323 	BUG_ON(e4b->bd_buddy_folio == NULL);  in ext4_mb_free_metadata()
6325 	new_node = &new_entry->efd_node;  in ext4_mb_free_metadata()
6326 	cluster = new_entry->efd_start_cluster;  in ext4_mb_free_metadata()
6332 		 * on-disk bitmap and lose not-yet-available  in ext4_mb_free_metadata()
6334 		folio_get(e4b->bd_buddy_folio);  in ext4_mb_free_metadata()
6335 		folio_get(e4b->bd_bitmap_folio);  in ext4_mb_free_metadata()
6340 		if (cluster < entry->efd_start_cluster)  in ext4_mb_free_metadata()
6341 			n = &(*n)->rb_left;  in ext4_mb_free_metadata()
6342 		else if (cluster >= (entry->efd_start_cluster + entry->efd_count))  in ext4_mb_free_metadata()
6343 			n = &(*n)->rb_right;  in ext4_mb_free_metadata()
6348 				"Block already on to-be-freed list");  in ext4_mb_free_metadata()
6355 	rb_insert_color(new_node, &db->bb_free_root);  in ext4_mb_free_metadata()
6362 					    &(db->bb_free_root));  in ext4_mb_free_metadata()
6369 					    &(db->bb_free_root));  in ext4_mb_free_metadata()
6372 	spin_lock(&sbi->s_md_lock);  in ext4_mb_free_metadata()
6373 	list_add_tail(&new_entry->efd_list, &sbi->s_freed_data_list[new_entry->efd_tid & 1]);  in ext4_mb_free_metadata()
6374 	sbi->s_mb_free_pending += clusters;  in ext4_mb_free_metadata()
6375 	spin_unlock(&sbi->s_md_lock);  in ext4_mb_free_metadata()
6381 	struct super_block *sb = inode->i_sb;  in ext4_free_blocks_simple()
6393  * ext4_mb_clear_bb() -- helper function for freeing blocks.
6405 	struct super_block *sb = inode->i_sb;  in ext4_mb_clear_bb()
6421 		ext4_error(sb, "Freeing blocks in system zone - "  in ext4_mb_clear_bb()
6441 		overflow = EXT4_C2B(sbi, bit) + count -  in ext4_mb_clear_bb()
6443 		count -= overflow;  in ext4_mb_clear_bb()
6458 		ext4_error(sb, "Freeing blocks in system zone - "  in ext4_mb_clear_bb()
6494 		new_entry->efd_start_cluster = bit;  in ext4_mb_clear_bb()
6495 		new_entry->efd_group = block_group;  in ext4_mb_clear_bb()
6496 		new_entry->efd_count = count_clusters;  in ext4_mb_clear_bb()
6497 		new_entry->efd_tid = handle->h_transaction->t_tid;  in ext4_mb_clear_bb()
6509 			if (err == -EOPNOTSUPP)  in ext4_mb_clear_bb()
6534 		percpu_counter_add(&sbi->s_freeclusters_counter,  in ext4_mb_clear_bb()
6554  * ext4_free_blocks() -- Free given blocks and update quota
6566 	struct super_block *sb = inode->i_sb;  in ext4_free_blocks()
6574 			BUG_ON(block != bh->b_blocknr);  in ext4_free_blocks()
6576 			block = bh->b_blocknr;  in ext4_free_blocks()
6579 	if (sbi->s_mount_state & EXT4_FC_REPLAY) {  in ext4_free_blocks()
6588 		ext4_error(sb, "Freeing blocks not in datazone - "  in ext4_free_blocks()
6614 			overflow = sbi->s_cluster_ratio - overflow;  in ext4_free_blocks()
6617 				count -= overflow;  in ext4_free_blocks()
6621 			block -= overflow;  in ext4_free_blocks()
6631 				count -= overflow;  in ext4_free_blocks()
6635 			count += sbi->s_cluster_ratio - overflow;  in ext4_free_blocks()
6647 				bh = sb_find_get_block(inode->i_sb, block + i);  in ext4_free_blocks()
6656  * ext4_group_add_blocks() -- Add given blocks to an existing group
6673 	ext4_fsblk_t last_cluster = EXT4_B2C(sbi, block + count - 1);  in ext4_group_add_blocks()
6674 	unsigned long cluster_count = last_cluster - first_cluster + 1;  in ext4_group_add_blocks()
6677 	ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);  in ext4_group_add_blocks()
6690 		err = -EINVAL;  in ext4_group_add_blocks()
6699 		ext4_error(sb, "Adding blocks in system zones - "  in ext4_group_add_blocks()
6702 		err = -EINVAL;  in ext4_group_add_blocks()
6718 	percpu_counter_add(&sbi->s_freeclusters_counter,  in ext4_group_add_blocks()
6729  * ext4_trim_extent -- function to TRIM one single free extent in the group
6745 	ext4_group_t group = e4b->bd_group;  in ext4_trim_extent()
6773 	if (grp < (ext4_get_groups_count(sb) - 1))  in ext4_last_grp_cluster()
6776 		nr_clusters_in_group = (ext4_blocks_count(EXT4_SB(sb)->s_es) -  in ext4_last_grp_cluster()
6780 	return nr_clusters_in_group - 1;  in ext4_last_grp_cluster()
6791 __acquires(ext4_group_lock_ptr(sb, e4b->bd_group))  in ext4_try_to_trim_range()
6792 __releases(ext4_group_lock_ptr(sb, e4b->bd_group))  in ext4_try_to_trim_range()
6798 	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))  in ext4_try_to_trim_range()
6801 	last = ext4_last_grp_cluster(sb, e4b->bd_group);  in ext4_try_to_trim_range()
6802 	bitmap = e4b->bd_bitmap;  in ext4_try_to_trim_range()
6806 	start = max(e4b->bd_info->bb_first_free, start);  in ext4_try_to_trim_range()
6819 		if ((next - start) >= minblocks) {  in ext4_try_to_trim_range()
6820 			int ret = ext4_trim_extent(sb, start, next - start, e4b);  in ext4_try_to_trim_range()
6822 			if (ret && ret != -EOPNOTSUPP)  in ext4_try_to_trim_range()
6824 			count += next - start;  in ext4_try_to_trim_range()
6826 		free_count += next - start;  in ext4_try_to_trim_range()
6833 			ext4_unlock_group(sb, e4b->bd_group);  in ext4_try_to_trim_range()
6835 			ext4_lock_group(sb, e4b->bd_group);  in ext4_try_to_trim_range()
6838 		if ((e4b->bd_info->bb_free - free_count) < minblocks)  in ext4_try_to_trim_range()
6843 		EXT4_MB_GRP_SET_TRIMMED(e4b->bd_info);  in ext4_try_to_trim_range()
6849  * ext4_trim_all_free -- function to trim all free space in alloc. group
6881 	    minblocks < EXT4_SB(sb)->s_last_trim_minblks)  in ext4_trim_all_free()
6896  * ext4_trim_fs() -- trim ioctl handle function
6909 	unsigned int discard_granularity = bdev_discard_granularity(sb->s_bdev);  in ext4_trim_fs()
6915 			le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);  in ext4_trim_fs()
6916 	ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);  in ext4_trim_fs()
6919 	start = range->start >> sb->s_blocksize_bits;  in ext4_trim_fs()
6920 	end = start + (range->len >> sb->s_blocksize_bits) - 1;  in ext4_trim_fs()
6922 			      range->minlen >> sb->s_blocksize_bits);  in ext4_trim_fs()
6926 	    range->len < sb->s_blocksize)  in ext4_trim_fs()
6927 		return -EINVAL;  in ext4_trim_fs()
6929 	if (range->minlen < discard_granularity) {  in ext4_trim_fs()
6931 				discard_granularity >> sb->s_blocksize_bits);  in ext4_trim_fs()
6935 	if (end >= max_blks - 1)  in ext4_trim_fs()
6936 		end = max_blks - 1;  in ext4_trim_fs()
6949 	end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;  in ext4_trim_fs()
6966 		 * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to  in ext4_trim_fs()
6972 		if (grp->bb_free >= minlen) {  in ext4_trim_fs()
6990 		EXT4_SB(sb)->s_last_trim_minblks = minlen;  in ext4_trim_fs()
6993 	range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;  in ext4_trim_fs()
7019 	start = max(e4b.bd_info->bb_first_free, start);  in ext4_mballoc_query_range()
7021 		end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;  in ext4_mballoc_query_range()
7030 		error = formatter(sb, group, start, next - start, priv);  in ext4_mballoc_query_range()
7046 #include "mballoc-test.c"