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>
23  *   - test ext4_ext_search_left() and ext4_ext_search_right()
24  *   - search for metadata in few groups
27  *   - normalization should take into account whether file is still open
28  *   - discard preallocations if no free space left (policy?)
29  *   - don't normalize tails
30  *   - quota
31  *   - reservation for superuser
34  *   - bitmap read-ahead (proposed by Oleg Drokin aka green)
35  *   - track min/max extents in each group for better group selection
36  *   - mb_mark_used() may allocate chunk right after splitting buddy
37  *   - tree of groups sorted by number of free blocks
38  *   - error handling
49  * is larger. If the size is less than sbi->s_mb_stream_request we
59  * ext4_inode_info->i_prealloc_list, which contains list of prealloc
63  * pa_lstart -> the logical start block for this prealloc space
64  * pa_pstart -> the physical start block for this prealloc space
65  * pa_len    -> length for this prealloc space (in clusters)
66  * pa_free   ->  free space available in this prealloc space (in clusters)
78  * have the group allocation flag set then we look at the locality group
83  * The reason for having a per cpu locality group is to reduce the contention
86  * The locality group prealloc space is used looking at whether we have
89  * If we can't allocate blocks via inode prealloc or/and locality group
121  * sbi->s_mb_group_prealloc.  The default value of s_mb_group_prealloc is
122  * dependent on the cluster size; for non-bigalloc file systems, it is
125  * terms of number of blocks. If we have mounted the file system with -O
127  * smallest multiple of the stripe value (sbi->s_stripe) which is
137  * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
140  * stripe size (sbi->s_stripe), we try to search for contiguous block in
142  * not, we search in the specific group using bitmap for best extents. The
160  *  - on-disk bitmap
161  *  - in-core buddy (actually includes buddy and bitmap)
162  *  - preallocation descriptors (PAs)
165  *  - inode
166  *    assiged to specific inode and can be used for this inode only.
167  *    it describes part of inode's space preallocated to specific
174  *  - locality group
175  *    assigned to specific locality group which does not translate to
181  *    in-core buddy = on-disk bitmap + preallocation descriptors
184  *  - allocated blocks (persistent)
185  *  - preallocated blocks (non-persistent)
189  * literally -- time is discrete and delimited by locks.
192  *  blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
195  *  - init buddy:			buddy = on-disk + PAs
196  *  - new PA:				buddy += N; PA = N
197  *  - use inode PA:			on-disk += N; PA -= N
198  *  - discard inode PA			buddy -= on-disk - PA; PA = 0
199  *  - use locality group PA		on-disk += N; PA -= N
200  *  - discard locality group PA		buddy -= PA; PA = 0
201  *  note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
203  *        bits from PA, only from on-disk bitmap
207  * killing performance on high-end SMP hardware. let's try to relax it using
211  *     nobody can re-allocate that block
212  *  3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
214  *     on-disk bitmap if buddy has same bit set or/and PA covers corresponded
218  *  - init buddy vs.
219  *    - new PA
222  *    - use inode PA
223  *      we need to make sure that either on-disk bitmap or PA has uptodate data
224  *      given (3) we care that PA-=N operation doesn't interfere with init
225  *    - discard inode PA
227  *    - use locality group PA
228  *      again PA-=N must be serialized with init
229  *    - discard locality group PA
231  *  - new PA vs.
232  *    - use inode PA
234  *    - discard inode PA
236  *    - use locality group PA
238  *    - discard locality group PA
240  *  - use inode PA
241  *    - use inode PA
243  *    - discard inode PA
245  *    - use locality group PA
246  *      nothing wrong here -- they're different PAs covering different blocks
247  *    - discard locality group PA
251  *  - PA is referenced and while it is no discard is possible
252  *  - PA is referenced until block isn't marked in on-disk bitmap
253  *  - PA changes only after on-disk bitmap
254  *  - discard must not compete with init. either init is done before
256  *  - buddy init as sum of on-disk bitmap and PAs is done atomically
266  *  - allocation:
269  *    mark bits in on-disk bitmap
272  *  - use preallocation:
273  *    find proper PA (per-inode or group)
275  *    mark bits in on-disk bitmap
279  *  - free:
281  *    mark bits in on-disk bitmap
284  *  - discard preallocations in group:
287  *    load on-disk bitmap
289  *    remove PA from object (inode or locality group)
290  *    mark free blocks in-core
292  *  - discard inode's preallocations:
299  *  - bitlock on a group	(group)
300  *  - object (inode/locality)	(object)
301  *  - per-pa lock		(pa)
304  *  - new pa
308  *  - find and use pa:
311  *  - release consumed pa:
316  *  - generate in-core bitmap:
320  *  - discard all for given object (inode, locality group):
325  *  - discard all for given group:
370  * sure that all the PAs on grp->bb_prealloc_list got freed or if it's empty.
432 	ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;  in mb_find_next_zero_bit()
445 	ret = ext4_find_next_bit(addr, tmpmax, start) - fix;  in mb_find_next_bit()
455 	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);  in mb_find_buddy()
458 	if (order > e4b->bd_blkbits + 1) {  in mb_find_buddy()
465 		*max = 1 << (e4b->bd_blkbits + 3);  in mb_find_buddy()
466 		return e4b->bd_bitmap;  in mb_find_buddy()
469 	bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];  in mb_find_buddy()
470 	*max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];  in mb_find_buddy()
480 	struct super_block *sb = e4b->bd_sb;  in mb_free_blocks_double()
482 	if (unlikely(e4b->bd_info->bb_bitmap == NULL))  in mb_free_blocks_double()
484 	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));  in mb_free_blocks_double()
486 		if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {  in mb_free_blocks_double()
489 			blocknr = ext4_group_first_block_no(sb, e4b->bd_group);  in mb_free_blocks_double()
491 			ext4_grp_locked_error(sb, e4b->bd_group,  in mb_free_blocks_double()
492 					      inode ? inode->i_ino : 0,  in mb_free_blocks_double()
497 			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in mb_free_blocks_double()
500 		mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);  in mb_free_blocks_double()
508 	if (unlikely(e4b->bd_info->bb_bitmap == NULL))  in mb_mark_used_double()
510 	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));  in mb_mark_used_double()
512 		BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));  in mb_mark_used_double()
513 		mb_set_bit(first + i, e4b->bd_info->bb_bitmap);  in mb_mark_used_double()
519 	if (unlikely(e4b->bd_info->bb_bitmap == NULL))  in mb_cmp_bitmaps()
521 	if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {  in mb_cmp_bitmaps()
524 		b1 = (unsigned char *) e4b->bd_info->bb_bitmap;  in mb_cmp_bitmaps()
526 		for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {  in mb_cmp_bitmaps()
528 				ext4_msg(e4b->bd_sb, KERN_ERR,  in mb_cmp_bitmaps()
532 					 e4b->bd_group, i, i * 8, b1[i], b2[i]);  in mb_cmp_bitmaps()
544 	grp->bb_bitmap = kmalloc(sb->s_blocksize, GFP_NOFS);  in mb_group_bb_bitmap_alloc()
545 	if (!grp->bb_bitmap)  in mb_group_bb_bitmap_alloc()
550 		kfree(grp->bb_bitmap);  in mb_group_bb_bitmap_alloc()
551 		grp->bb_bitmap = NULL;  in mb_group_bb_bitmap_alloc()
555 	memcpy(grp->bb_bitmap, bh->b_data, sb->s_blocksize);  in mb_group_bb_bitmap_alloc()
561 	kfree(grp->bb_bitmap);  in mb_group_bb_bitmap_free()
607 	struct super_block *sb = e4b->bd_sb;  in __mb_check_buddy()
608 	int order = e4b->bd_blkbits + 1;  in __mb_check_buddy()
622 	if (e4b->bd_info->bb_check_counter++ % 10)  in __mb_check_buddy()
628 		buddy2 = mb_find_buddy(e4b, order - 1, &max2);  in __mb_check_buddy()
655 					!mb_test_bit(k, e4b->bd_bitmap));  in __mb_check_buddy()
659 		MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);  in __mb_check_buddy()
660 		order--;  in __mb_check_buddy()
663 	fstart = -1;  in __mb_check_buddy()
667 			MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);  in __mb_check_buddy()
668 			if (fstart == -1) {  in __mb_check_buddy()
674 		fstart = -1;  in __mb_check_buddy()
676 		for (j = 0; j < e4b->bd_blkbits + 1; j++) {  in __mb_check_buddy()
683 	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));  in __mb_check_buddy()
684 	MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);  in __mb_check_buddy()
686 	grp = ext4_get_group_info(sb, e4b->bd_group);  in __mb_check_buddy()
687 	list_for_each(cur, &grp->bb_prealloc_list) {  in __mb_check_buddy()
691 		ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);  in __mb_check_buddy()
692 		MB_CHECK_ASSERT(groupnr == e4b->bd_group);  in __mb_check_buddy()
693 		for (i = 0; i < pa->pa_len; i++)  in __mb_check_buddy()
723 	border = 2 << sb->s_blocksize_bits;  in ext4_mb_mark_free_simple()
727 		max = ffs(first | border) - 1;  in ext4_mb_mark_free_simple()
730 		min = fls(len) - 1;  in ext4_mb_mark_free_simple()
737 		grp->bb_counters[min]++;  in ext4_mb_mark_free_simple()
740 				     buddy + sbi->s_mb_offsets[min]);  in ext4_mb_mark_free_simple()
742 		len -= chunk;  in ext4_mb_mark_free_simple()
757 	grp->bb_largest_free_order = -1; /* uninit */  in mb_set_largest_free_order()
759 	bits = sb->s_blocksize_bits + 1;  in mb_set_largest_free_order()
760 	for (i = bits; i >= 0; i--) {  in mb_set_largest_free_order()
761 		if (grp->bb_counters[i] > 0) {  in mb_set_largest_free_order()
762 			grp->bb_largest_free_order = i;  in mb_set_largest_free_order()
783 	 * of on-disk bitmap and preallocations */  in ext4_mb_generate_buddy()
785 	grp->bb_first_free = i;  in ext4_mb_generate_buddy()
790 		len = i - first;  in ext4_mb_generate_buddy()
795 			grp->bb_counters[0]++;  in ext4_mb_generate_buddy()
799 	grp->bb_fragments = fragments;  in ext4_mb_generate_buddy()
801 	if (free != grp->bb_free) {  in ext4_mb_generate_buddy()
805 				      free, grp->bb_free);  in ext4_mb_generate_buddy()
810 		grp->bb_free = free;  in ext4_mb_generate_buddy()
816 	clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));  in ext4_mb_generate_buddy()
818 	period = get_cycles() - period;  in ext4_mb_generate_buddy()
819 	spin_lock(&sbi->s_bal_lock);  in ext4_mb_generate_buddy()
820 	sbi->s_mb_buddies_generated++;  in ext4_mb_generate_buddy()
821 	sbi->s_mb_generation_time += period;  in ext4_mb_generate_buddy()
822 	spin_unlock(&sbi->s_bal_lock);  in ext4_mb_generate_buddy()
834 	e4b->bd_info->bb_fragments = 0;  in mb_regenerate_buddy()
835 	memset(e4b->bd_info->bb_counters, 0,  in mb_regenerate_buddy()
836 		sizeof(*e4b->bd_info->bb_counters) *  in mb_regenerate_buddy()
837 		(e4b->bd_sb->s_blocksize_bits + 2));  in mb_regenerate_buddy()
839 	ext4_mb_generate_buddy(e4b->bd_sb, e4b->bd_buddy,  in mb_regenerate_buddy()
840 		e4b->bd_bitmap, e4b->bd_group);  in mb_regenerate_buddy()
881 	inode = page->mapping->host;  in ext4_mb_init_cache()
882 	sb = inode->i_sb;  in ext4_mb_init_cache()
887 	mb_debug(sb, "init page %lu\n", page->index);  in ext4_mb_init_cache()
898 			err = -ENOMEM;  in ext4_mb_init_cache()
904 	first_group = page->index * blocks_per_page / 2;  in ext4_mb_init_cache()
942 	first_block = page->index * blocks_per_page;  in ext4_mb_init_cache()
948 		if (!bh[group - first_group])  in ext4_mb_init_cache()
952 		if (!buffer_verified(bh[group - first_group]))  in ext4_mb_init_cache()
964 		bitmap = bh[group - first_group]->b_data;  in ext4_mb_init_cache()
974 				group, page->index, i * blocksize);  in ext4_mb_init_cache()
977 			grinfo->bb_fragments = 0;  in ext4_mb_init_cache()
978 			memset(grinfo->bb_counters, 0,  in ext4_mb_init_cache()
979 			       sizeof(*grinfo->bb_counters) *  in ext4_mb_init_cache()
980 				(sb->s_blocksize_bits+2));  in ext4_mb_init_cache()
994 				group, page->index, i * blocksize);  in ext4_mb_init_cache()
1001 			/* mark all preallocated blks used in in-core bitmap */  in ext4_mb_init_cache()
1028  * are on the same page e4b->bd_buddy_page is NULL and return value is 0.
1033 	struct inode *inode = EXT4_SB(sb)->s_buddy_cache;  in ext4_mb_get_buddy_page_lock()
1038 	e4b->bd_buddy_page = NULL;  in ext4_mb_get_buddy_page_lock()
1039 	e4b->bd_bitmap_page = NULL;  in ext4_mb_get_buddy_page_lock()
1041 	blocks_per_page = PAGE_SIZE / sb->s_blocksize;  in ext4_mb_get_buddy_page_lock()
1050 	page = find_or_create_page(inode->i_mapping, pnum, gfp);  in ext4_mb_get_buddy_page_lock()
1052 		return -ENOMEM;  in ext4_mb_get_buddy_page_lock()
1053 	BUG_ON(page->mapping != inode->i_mapping);  in ext4_mb_get_buddy_page_lock()
1054 	e4b->bd_bitmap_page = page;  in ext4_mb_get_buddy_page_lock()
1055 	e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);  in ext4_mb_get_buddy_page_lock()
1064 	page = find_or_create_page(inode->i_mapping, pnum, gfp);  in ext4_mb_get_buddy_page_lock()
1066 		return -ENOMEM;  in ext4_mb_get_buddy_page_lock()
1067 	BUG_ON(page->mapping != inode->i_mapping);  in ext4_mb_get_buddy_page_lock()
1068 	e4b->bd_buddy_page = page;  in ext4_mb_get_buddy_page_lock()
1074 	if (e4b->bd_bitmap_page) {  in ext4_mb_put_buddy_page_lock()
1075 		unlock_page(e4b->bd_bitmap_page);  in ext4_mb_put_buddy_page_lock()
1076 		put_page(e4b->bd_bitmap_page);  in ext4_mb_put_buddy_page_lock()
1078 	if (e4b->bd_buddy_page) {  in ext4_mb_put_buddy_page_lock()
1079 		unlock_page(e4b->bd_buddy_page);  in ext4_mb_put_buddy_page_lock()
1080 		put_page(e4b->bd_buddy_page);  in ext4_mb_put_buddy_page_lock()
1124 		ret = -EIO;  in ext4_mb_init_group()
1143 		ret = -EIO;  in ext4_mb_init_group()
1168 	struct inode *inode = sbi->s_buddy_cache;  in ext4_mb_load_buddy_gfp()
1173 	blocks_per_page = PAGE_SIZE / sb->s_blocksize;  in ext4_mb_load_buddy_gfp()
1176 	e4b->bd_blkbits = sb->s_blocksize_bits;  in ext4_mb_load_buddy_gfp()
1177 	e4b->bd_info = grp;  in ext4_mb_load_buddy_gfp()
1178 	e4b->bd_sb = sb;  in ext4_mb_load_buddy_gfp()
1179 	e4b->bd_group = group;  in ext4_mb_load_buddy_gfp()
1180 	e4b->bd_buddy_page = NULL;  in ext4_mb_load_buddy_gfp()
1181 	e4b->bd_bitmap_page = NULL;  in ext4_mb_load_buddy_gfp()
1204 	page = find_get_page_flags(inode->i_mapping, pnum, FGP_ACCESSED);  in ext4_mb_load_buddy_gfp()
1216 		page = find_or_create_page(inode->i_mapping, pnum, gfp);  in ext4_mb_load_buddy_gfp()
1218 			BUG_ON(page->mapping != inode->i_mapping);  in ext4_mb_load_buddy_gfp()
1226 					       (poff * sb->s_blocksize));  in ext4_mb_load_buddy_gfp()
1232 		ret = -ENOMEM;  in ext4_mb_load_buddy_gfp()
1236 		ret = -EIO;  in ext4_mb_load_buddy_gfp()
1241 	e4b->bd_bitmap_page = page;  in ext4_mb_load_buddy_gfp()
1242 	e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);  in ext4_mb_load_buddy_gfp()
1248 	page = find_get_page_flags(inode->i_mapping, pnum, FGP_ACCESSED);  in ext4_mb_load_buddy_gfp()
1252 		page = find_or_create_page(inode->i_mapping, pnum, gfp);  in ext4_mb_load_buddy_gfp()
1254 			BUG_ON(page->mapping != inode->i_mapping);  in ext4_mb_load_buddy_gfp()
1256 				ret = ext4_mb_init_cache(page, e4b->bd_bitmap,  in ext4_mb_load_buddy_gfp()
1267 		ret = -ENOMEM;  in ext4_mb_load_buddy_gfp()
1271 		ret = -EIO;  in ext4_mb_load_buddy_gfp()
1276 	e4b->bd_buddy_page = page;  in ext4_mb_load_buddy_gfp()
1277 	e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);  in ext4_mb_load_buddy_gfp()
1284 	if (e4b->bd_bitmap_page)  in ext4_mb_load_buddy_gfp()
1285 		put_page(e4b->bd_bitmap_page);  in ext4_mb_load_buddy_gfp()
1286 	if (e4b->bd_buddy_page)  in ext4_mb_load_buddy_gfp()
1287 		put_page(e4b->bd_buddy_page);  in ext4_mb_load_buddy_gfp()
1288 	e4b->bd_buddy = NULL;  in ext4_mb_load_buddy_gfp()
1289 	e4b->bd_bitmap = NULL;  in ext4_mb_load_buddy_gfp()
1301 	if (e4b->bd_bitmap_page)  in ext4_mb_unload_buddy()
1302 		put_page(e4b->bd_bitmap_page);  in ext4_mb_unload_buddy()
1303 	if (e4b->bd_buddy_page)  in ext4_mb_unload_buddy()
1304 		put_page(e4b->bd_buddy_page);  in ext4_mb_unload_buddy()
1311 	int bb_incr = 1 << (e4b->bd_blkbits - 1);  in mb_find_order_for_block()
1314 	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);  in mb_find_order_for_block()
1315 	BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));  in mb_find_order_for_block()
1317 	bb = e4b->bd_buddy;  in mb_find_order_for_block()
1318 	while (order <= e4b->bd_blkbits + 1) {  in mb_find_order_for_block()
1337 		if ((cur & 31) == 0 && (len - cur) >= 32) {  in mb_clear_bits()
1350  * will return first found zero bit if any, -1 otherwise
1355 	int zero_bit = -1;  in mb_test_and_clear_bits()
1359 		if ((cur & 31) == 0 && (len - cur) >= 32) {  in mb_test_and_clear_bits()
1362 			if (*addr != (__u32)(-1) && zero_bit == -1)  in mb_test_and_clear_bits()
1368 		if (!mb_test_and_clear_bit(cur, bm) && zero_bit == -1)  in mb_test_and_clear_bits()
1382 		if ((cur & 31) == 0 && (len - cur) >= 32) {  in ext4_set_bits()
1398 		(*bit) -= side;  in mb_buddy_adjust_border()
1404 		return -1;  in mb_buddy_adjust_border()
1427 		 * ---------------------------------  in mb_buddy_mark_free()
1429 		 * ---------------------------------  in mb_buddy_mark_free()
1431 		 * ---------------------------------  in mb_buddy_mark_free()
1447 			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&first, buddy, -1);  in mb_buddy_mark_free()
1449 			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&last, buddy, 1);  in mb_buddy_mark_free()
1455 			mb_clear_bits(buddy, first, last - first + 1);  in mb_buddy_mark_free()
1456 			e4b->bd_info->bb_counters[order - 1] += last - first + 1;  in mb_buddy_mark_free()
1471 	int last = first + count - 1;  in mb_free_blocks()
1472 	struct super_block *sb = e4b->bd_sb;  in mb_free_blocks()
1476 	BUG_ON(last >= (sb->s_blocksize << 3));  in mb_free_blocks()
1477 	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));  in mb_free_blocks()
1479 	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))  in mb_free_blocks()
1486 	e4b->bd_info->bb_free += count;  in mb_free_blocks()
1487 	if (first < e4b->bd_info->bb_first_free)  in mb_free_blocks()
1488 		e4b->bd_info->bb_first_free = first;  in mb_free_blocks()
1494 		left_is_free = !mb_test_bit(first - 1, e4b->bd_bitmap);  in mb_free_blocks()
1495 	block = mb_test_and_clear_bits(e4b->bd_bitmap, first, count);  in mb_free_blocks()
1496 	if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])  in mb_free_blocks()
1497 		right_is_free = !mb_test_bit(last + 1, e4b->bd_bitmap);  in mb_free_blocks()
1499 	if (unlikely(block != -1)) {  in mb_free_blocks()
1503 		blocknr = ext4_group_first_block_no(sb, e4b->bd_group);  in mb_free_blocks()
1505 		if (!(sbi->s_mount_state & EXT4_FC_REPLAY)) {  in mb_free_blocks()
1506 			ext4_grp_locked_error(sb, e4b->bd_group,  in mb_free_blocks()
1507 					      inode ? inode->i_ino : 0,  in mb_free_blocks()
1512 				sb, e4b->bd_group,  in mb_free_blocks()
1521 		e4b->bd_info->bb_fragments--;  in mb_free_blocks()
1523 		e4b->bd_info->bb_fragments++;  in mb_free_blocks()
1533 		e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;  in mb_free_blocks()
1536 		last -= !right_is_free;  in mb_free_blocks()
1537 		e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;  in mb_free_blocks()
1544 	mb_set_largest_free_order(sb, e4b->bd_info);  in mb_free_blocks()
1555 	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));  in mb_find_extent()
1562 		ex->fe_len = 0;  in mb_find_extent()
1563 		ex->fe_start = 0;  in mb_find_extent()
1564 		ex->fe_group = 0;  in mb_find_extent()
1572 	ex->fe_len = 1 << order;  in mb_find_extent()
1573 	ex->fe_start = block << order;  in mb_find_extent()
1574 	ex->fe_group = e4b->bd_group;  in mb_find_extent()
1577 	next = next - ex->fe_start;  in mb_find_extent()
1578 	ex->fe_len -= next;  in mb_find_extent()
1579 	ex->fe_start += next;  in mb_find_extent()
1581 	while (needed > ex->fe_len &&  in mb_find_extent()
1588 		if (mb_test_bit(next, e4b->bd_bitmap))  in mb_find_extent()
1594 		ex->fe_len += 1 << order;  in mb_find_extent()
1597 	if (ex->fe_start + ex->fe_len > EXT4_CLUSTERS_PER_GROUP(e4b->bd_sb)) {  in mb_find_extent()
1600 		ext4_error(e4b->bd_sb, "corruption or bug in mb_find_extent "  in mb_find_extent()
1602 			   block, order, needed, ex->fe_group, ex->fe_start,  in mb_find_extent()
1603 			   ex->fe_len, ex->fe_logical);  in mb_find_extent()
1604 		ex->fe_len = 0;  in mb_find_extent()
1605 		ex->fe_start = 0;  in mb_find_extent()
1606 		ex->fe_group = 0;  in mb_find_extent()
1608 	return ex->fe_len;  in mb_find_extent()
1617 	int start = ex->fe_start;  in mb_mark_used()
1618 	int len = ex->fe_len;  in mb_mark_used()
1623 	BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));  in mb_mark_used()
1624 	BUG_ON(e4b->bd_group != ex->fe_group);  in mb_mark_used()
1625 	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));  in mb_mark_used()
1630 	e4b->bd_info->bb_free -= len;  in mb_mark_used()
1631 	if (e4b->bd_info->bb_first_free == start)  in mb_mark_used()
1632 		e4b->bd_info->bb_first_free += len;  in mb_mark_used()
1636 		mlen = !mb_test_bit(start - 1, e4b->bd_bitmap);  in mb_mark_used()
1637 	if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])  in mb_mark_used()
1638 		max = !mb_test_bit(start + len, e4b->bd_bitmap);  in mb_mark_used()
1640 		e4b->bd_info->bb_fragments++;  in mb_mark_used()
1642 		e4b->bd_info->bb_fragments--;  in mb_mark_used()
1654 			e4b->bd_info->bb_counters[ord]--;  in mb_mark_used()
1656 			len -= mlen;  in mb_mark_used()
1669 		e4b->bd_info->bb_counters[ord]--;  in mb_mark_used()
1671 		ord--;  in mb_mark_used()
1676 		e4b->bd_info->bb_counters[ord]++;  in mb_mark_used()
1677 		e4b->bd_info->bb_counters[ord]++;  in mb_mark_used()
1679 	mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);  in mb_mark_used()
1681 	ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);  in mb_mark_used()
1693 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_use_best_found()
1696 	BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);  in ext4_mb_use_best_found()
1697 	BUG_ON(ac->ac_status == AC_STATUS_FOUND);  in ext4_mb_use_best_found()
1699 	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()
1700 	ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;  in ext4_mb_use_best_found()
1701 	ret = mb_mark_used(e4b, &ac->ac_b_ex);  in ext4_mb_use_best_found()
1705 	ac->ac_f_ex = ac->ac_b_ex;  in ext4_mb_use_best_found()
1707 	ac->ac_status = AC_STATUS_FOUND;  in ext4_mb_use_best_found()
1708 	ac->ac_tail = ret & 0xffff;  in ext4_mb_use_best_found()
1709 	ac->ac_buddy = ret >> 16;  in ext4_mb_use_best_found()
1718 	ac->ac_bitmap_page = e4b->bd_bitmap_page;  in ext4_mb_use_best_found()
1719 	get_page(ac->ac_bitmap_page);  in ext4_mb_use_best_found()
1720 	ac->ac_buddy_page = e4b->bd_buddy_page;  in ext4_mb_use_best_found()
1721 	get_page(ac->ac_buddy_page);  in ext4_mb_use_best_found()
1723 	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {  in ext4_mb_use_best_found()
1724 		spin_lock(&sbi->s_md_lock);  in ext4_mb_use_best_found()
1725 		sbi->s_mb_last_group = ac->ac_f_ex.fe_group;  in ext4_mb_use_best_found()
1726 		sbi->s_mb_last_start = ac->ac_f_ex.fe_start;  in ext4_mb_use_best_found()
1727 		spin_unlock(&sbi->s_md_lock);  in ext4_mb_use_best_found()
1734 	if (ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)  in ext4_mb_use_best_found()
1743 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_check_limits()
1744 	struct ext4_free_extent *bex = &ac->ac_b_ex;  in ext4_mb_check_limits()
1745 	struct ext4_free_extent *gex = &ac->ac_g_ex;  in ext4_mb_check_limits()
1749 	if (ac->ac_status == AC_STATUS_FOUND)  in ext4_mb_check_limits()
1754 	if (ac->ac_found > sbi->s_mb_max_to_scan &&  in ext4_mb_check_limits()
1755 			!(ac->ac_flags & EXT4_MB_HINT_FIRST)) {  in ext4_mb_check_limits()
1756 		ac->ac_status = AC_STATUS_BREAK;  in ext4_mb_check_limits()
1763 	if (bex->fe_len < gex->fe_len)  in ext4_mb_check_limits()
1766 	if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)  in ext4_mb_check_limits()
1767 			&& bex->fe_group == e4b->bd_group) {  in ext4_mb_check_limits()
1768 		/* recheck chunk's availability - we don't know  in ext4_mb_check_limits()
1769 		 * when it was found (within this lock-unlock  in ext4_mb_check_limits()
1771 		max = mb_find_extent(e4b, bex->fe_start, gex->fe_len, &ex);  in ext4_mb_check_limits()
1772 		if (max >= gex->fe_len) {  in ext4_mb_check_limits()
1793 	struct ext4_free_extent *bex = &ac->ac_b_ex;  in ext4_mb_measure_extent()
1794 	struct ext4_free_extent *gex = &ac->ac_g_ex;  in ext4_mb_measure_extent()
1796 	BUG_ON(ex->fe_len <= 0);  in ext4_mb_measure_extent()
1797 	BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));  in ext4_mb_measure_extent()
1798 	BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));  in ext4_mb_measure_extent()
1799 	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);  in ext4_mb_measure_extent()
1801 	ac->ac_found++;  in ext4_mb_measure_extent()
1804 	 * The special case - take what you catch first  in ext4_mb_measure_extent()
1806 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {  in ext4_mb_measure_extent()
1815 	if (ex->fe_len == gex->fe_len) {  in ext4_mb_measure_extent()
1824 	if (bex->fe_len == 0) {  in ext4_mb_measure_extent()
1832 	if (bex->fe_len < gex->fe_len) {  in ext4_mb_measure_extent()
1835 		if (ex->fe_len > bex->fe_len)  in ext4_mb_measure_extent()
1837 	} else if (ex->fe_len > gex->fe_len) {  in ext4_mb_measure_extent()
1841 		if (ex->fe_len < bex->fe_len)  in ext4_mb_measure_extent()
1852 	struct ext4_free_extent ex = ac->ac_b_ex;  in ext4_mb_try_best_found()
1858 	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);  in ext4_mb_try_best_found()
1862 	ext4_lock_group(ac->ac_sb, group);  in ext4_mb_try_best_found()
1866 		ac->ac_b_ex = ex;  in ext4_mb_try_best_found()
1870 	ext4_unlock_group(ac->ac_sb, group);  in ext4_mb_try_best_found()
1880 	ext4_group_t group = ac->ac_g_ex.fe_group;  in ext4_mb_find_by_goal()
1883 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_find_by_goal()
1884 	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);  in ext4_mb_find_by_goal()
1887 	if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))  in ext4_mb_find_by_goal()
1889 	if (grp->bb_free == 0)  in ext4_mb_find_by_goal()
1892 	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);  in ext4_mb_find_by_goal()
1896 	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info))) {  in ext4_mb_find_by_goal()
1901 	ext4_lock_group(ac->ac_sb, group);  in ext4_mb_find_by_goal()
1902 	max = mb_find_extent(e4b, ac->ac_g_ex.fe_start,  in ext4_mb_find_by_goal()
1903 			     ac->ac_g_ex.fe_len, &ex);  in ext4_mb_find_by_goal()
1906 	if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {  in ext4_mb_find_by_goal()
1909 		start = ext4_group_first_block_no(ac->ac_sb, e4b->bd_group) +  in ext4_mb_find_by_goal()
1911 		/* use do_div to get remainder (would be 64-bit modulo) */  in ext4_mb_find_by_goal()
1912 		if (do_div(start, sbi->s_stripe) == 0) {  in ext4_mb_find_by_goal()
1913 			ac->ac_found++;  in ext4_mb_find_by_goal()
1914 			ac->ac_b_ex = ex;  in ext4_mb_find_by_goal()
1917 	} else if (max >= ac->ac_g_ex.fe_len) {  in ext4_mb_find_by_goal()
1919 		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);  in ext4_mb_find_by_goal()
1920 		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);  in ext4_mb_find_by_goal()
1921 		ac->ac_found++;  in ext4_mb_find_by_goal()
1922 		ac->ac_b_ex = ex;  in ext4_mb_find_by_goal()
1924 	} else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {  in ext4_mb_find_by_goal()
1928 		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);  in ext4_mb_find_by_goal()
1929 		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);  in ext4_mb_find_by_goal()
1930 		ac->ac_found++;  in ext4_mb_find_by_goal()
1931 		ac->ac_b_ex = ex;  in ext4_mb_find_by_goal()
1934 	ext4_unlock_group(ac->ac_sb, group);  in ext4_mb_find_by_goal()
1948 	struct super_block *sb = ac->ac_sb;  in ext4_mb_simple_scan_group()
1949 	struct ext4_group_info *grp = e4b->bd_info;  in ext4_mb_simple_scan_group()
1955 	BUG_ON(ac->ac_2order <= 0);  in ext4_mb_simple_scan_group()
1956 	for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {  in ext4_mb_simple_scan_group()
1957 		if (grp->bb_counters[i] == 0)  in ext4_mb_simple_scan_group()
1965 			ext4_grp_locked_error(ac->ac_sb, e4b->bd_group, 0, 0,  in ext4_mb_simple_scan_group()
1967 				grp->bb_counters[i], i);  in ext4_mb_simple_scan_group()
1968 			ext4_mark_group_bitmap_corrupted(ac->ac_sb,  in ext4_mb_simple_scan_group()
1969 					 e4b->bd_group,  in ext4_mb_simple_scan_group()
1973 		ac->ac_found++;  in ext4_mb_simple_scan_group()
1975 		ac->ac_b_ex.fe_len = 1 << i;  in ext4_mb_simple_scan_group()
1976 		ac->ac_b_ex.fe_start = k << i;  in ext4_mb_simple_scan_group()
1977 		ac->ac_b_ex.fe_group = e4b->bd_group;  in ext4_mb_simple_scan_group()
1981 		BUG_ON(ac->ac_f_ex.fe_len != ac->ac_g_ex.fe_len);  in ext4_mb_simple_scan_group()
1983 		if (EXT4_SB(sb)->s_mb_stats)  in ext4_mb_simple_scan_group()
1984 			atomic_inc(&EXT4_SB(sb)->s_bal_2orders);  in ext4_mb_simple_scan_group()
1999 	struct super_block *sb = ac->ac_sb;  in ext4_mb_complex_scan_group()
2000 	void *bitmap = e4b->bd_bitmap;  in ext4_mb_complex_scan_group()
2005 	free = e4b->bd_info->bb_free;  in ext4_mb_complex_scan_group()
2009 	i = e4b->bd_info->bb_first_free;  in ext4_mb_complex_scan_group()
2011 	while (free && ac->ac_status == AC_STATUS_CONTINUE) {  in ext4_mb_complex_scan_group()
2020 			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,  in ext4_mb_complex_scan_group()
2024 			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in ext4_mb_complex_scan_group()
2029 		mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);  in ext4_mb_complex_scan_group()
2033 			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,  in ext4_mb_complex_scan_group()
2037 			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,  in ext4_mb_complex_scan_group()
2050 		free -= ex.fe_len;  in ext4_mb_complex_scan_group()
2058  * we try to find stripe-aligned chunks for stripe-size-multiple requests
2064 	struct super_block *sb = ac->ac_sb;  in ext4_mb_scan_aligned()
2066 	void *bitmap = e4b->bd_bitmap;  in ext4_mb_scan_aligned()
2073 	BUG_ON(sbi->s_stripe == 0);  in ext4_mb_scan_aligned()
2075 	/* find first stripe-aligned block in group */  in ext4_mb_scan_aligned()
2076 	first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);  in ext4_mb_scan_aligned()
2078 	a = first_group_block + sbi->s_stripe - 1;  in ext4_mb_scan_aligned()
2079 	do_div(a, sbi->s_stripe);  in ext4_mb_scan_aligned()
2080 	i = (a * sbi->s_stripe) - first_group_block;  in ext4_mb_scan_aligned()
2084 			max = mb_find_extent(e4b, i, sbi->s_stripe, &ex);  in ext4_mb_scan_aligned()
2085 			if (max >= sbi->s_stripe) {  in ext4_mb_scan_aligned()
2086 				ac->ac_found++;  in ext4_mb_scan_aligned()
2088 				ac->ac_b_ex = ex;  in ext4_mb_scan_aligned()
2093 		i += sbi->s_stripe;  in ext4_mb_scan_aligned()
2106 	int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));  in ext4_mb_good_group()
2107 	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);  in ext4_mb_good_group()
2114 	free = grp->bb_free;  in ext4_mb_good_group()
2118 	fragments = grp->bb_fragments;  in ext4_mb_good_group()
2124 		BUG_ON(ac->ac_2order == 0);  in ext4_mb_good_group()
2127 		if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&  in ext4_mb_good_group()
2132 		if (free < ac->ac_g_ex.fe_len)  in ext4_mb_good_group()
2135 		if (ac->ac_2order > ac->ac_sb->s_blocksize_bits+1)  in ext4_mb_good_group()
2138 		if (grp->bb_largest_free_order < ac->ac_2order)  in ext4_mb_good_group()
2143 		if ((free / fragments) >= ac->ac_g_ex.fe_len)  in ext4_mb_good_group()
2147 		if (free >= ac->ac_g_ex.fe_len)  in ext4_mb_good_group()
2167 	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);  in ext4_mb_good_group_nolock()
2168 	struct super_block *sb = ac->ac_sb;  in ext4_mb_good_group_nolock()
2170 	bool should_lock = ac->ac_flags & EXT4_MB_STRICT_CHECK;  in ext4_mb_good_group_nolock()
2176 	free = grp->bb_free;  in ext4_mb_good_group_nolock()
2179 	if (cr <= 2 && free < ac->ac_g_ex.fe_len)  in ext4_mb_good_group_nolock()
2201 		    (!sbi->s_log_groups_per_flex ||  in ext4_mb_good_group_nolock()
2202 		     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &&  in ext4_mb_good_group_nolock()
2204 		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))  in ext4_mb_good_group_nolock()
2232 	while (nr-- > 0) {  in ext4_mb_prefetch()
2248 		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)))) {  in ext4_mb_prefetch()
2278 	while (nr-- > 0) {  in ext4_mb_prefetch_fini()
2285 		group--;  in ext4_mb_prefetch_fini()
2291 		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)))) {  in ext4_mb_prefetch_fini()
2302 	int cr = -1;  in ext4_mb_regular_allocator()
2310 	sb = ac->ac_sb;  in ext4_mb_regular_allocator()
2313 	/* non-extent files are limited to low blocks/groups */  in ext4_mb_regular_allocator()
2314 	if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))  in ext4_mb_regular_allocator()
2315 		ngroups = sbi->s_blockfile_groups;  in ext4_mb_regular_allocator()
2317 	BUG_ON(ac->ac_status == AC_STATUS_FOUND);  in ext4_mb_regular_allocator()
2321 	if (err || ac->ac_status == AC_STATUS_FOUND)  in ext4_mb_regular_allocator()
2324 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))  in ext4_mb_regular_allocator()
2328 	 * ac->ac_2order is set only if the fe_len is a power of 2  in ext4_mb_regular_allocator()
2329 	 * if ac->ac_2order is set we also set criteria to 0 so that we  in ext4_mb_regular_allocator()
2332 	i = fls(ac->ac_g_ex.fe_len);  in ext4_mb_regular_allocator()
2333 	ac->ac_2order = 0;  in ext4_mb_regular_allocator()
2338 	 * We also support searching for power-of-two requests only for  in ext4_mb_regular_allocator()
2341 	if (i >= sbi->s_mb_order2_reqs && i <= sb->s_blocksize_bits + 2) {  in ext4_mb_regular_allocator()
2345 		if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)  in ext4_mb_regular_allocator()
2346 			ac->ac_2order = array_index_nospec(i - 1,  in ext4_mb_regular_allocator()
2347 							   sb->s_blocksize_bits + 2);  in ext4_mb_regular_allocator()
2351 	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {  in ext4_mb_regular_allocator()
2353 		spin_lock(&sbi->s_md_lock);  in ext4_mb_regular_allocator()
2354 		ac->ac_g_ex.fe_group = sbi->s_mb_last_group;  in ext4_mb_regular_allocator()
2355 		ac->ac_g_ex.fe_start = sbi->s_mb_last_start;  in ext4_mb_regular_allocator()
2356 		spin_unlock(&sbi->s_md_lock);  in ext4_mb_regular_allocator()
2359 	/* Let's just scan groups to find more-less suitable blocks */  in ext4_mb_regular_allocator()
2360 	cr = ac->ac_2order ? 0 : 1;  in ext4_mb_regular_allocator()
2366 	for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {  in ext4_mb_regular_allocator()
2367 		ac->ac_criteria = cr;  in ext4_mb_regular_allocator()
2372 		group = ac->ac_g_ex.fe_group;  in ext4_mb_regular_allocator()
2379 			 * Artificially restricted ngroups for non-extent  in ext4_mb_regular_allocator()
2393 			     prefetch_ios < sbi->s_mb_prefetch_limit)) {  in ext4_mb_regular_allocator()
2396 				nr = sbi->s_mb_prefetch;  in ext4_mb_regular_allocator()
2398 					nr = (group / sbi->s_mb_prefetch) *  in ext4_mb_regular_allocator()
2399 						sbi->s_mb_prefetch;  in ext4_mb_regular_allocator()
2400 					nr = nr + sbi->s_mb_prefetch - group;  in ext4_mb_regular_allocator()
2433 			ac->ac_groups_scanned++;  in ext4_mb_regular_allocator()
2436 			else if (cr == 1 && sbi->s_stripe &&  in ext4_mb_regular_allocator()
2437 					!(ac->ac_g_ex.fe_len % sbi->s_stripe))  in ext4_mb_regular_allocator()
2445 			if (ac->ac_status != AC_STATUS_CONTINUE)  in ext4_mb_regular_allocator()
2450 	if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&  in ext4_mb_regular_allocator()
2451 	    !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {  in ext4_mb_regular_allocator()
2457 		if (ac->ac_status != AC_STATUS_FOUND) {  in ext4_mb_regular_allocator()
2463 			lost = atomic_inc_return(&sbi->s_mb_lost_chunks);  in ext4_mb_regular_allocator()
2465 				 ac->ac_b_ex.fe_group, ac->ac_b_ex.fe_start,  in ext4_mb_regular_allocator()
2466 				 ac->ac_b_ex.fe_len, lost);  in ext4_mb_regular_allocator()
2468 			ac->ac_b_ex.fe_group = 0;  in ext4_mb_regular_allocator()
2469 			ac->ac_b_ex.fe_start = 0;  in ext4_mb_regular_allocator()
2470 			ac->ac_b_ex.fe_len = 0;  in ext4_mb_regular_allocator()
2471 			ac->ac_status = AC_STATUS_CONTINUE;  in ext4_mb_regular_allocator()
2472 			ac->ac_flags |= EXT4_MB_HINT_FIRST;  in ext4_mb_regular_allocator()
2478 	if (!err && ac->ac_status != AC_STATUS_FOUND && first_err)  in ext4_mb_regular_allocator()
2482 		 ac->ac_b_ex.fe_len, ac->ac_o_ex.fe_len, ac->ac_status,  in ext4_mb_regular_allocator()
2483 		 ac->ac_flags, cr, err);  in ext4_mb_regular_allocator()
2493 	struct super_block *sb = PDE_DATA(file_inode(seq->file));  in ext4_mb_seq_groups_start()
2504 	struct super_block *sb = PDE_DATA(file_inode(seq->file));  in ext4_mb_seq_groups_next()
2516 	struct super_block *sb = PDE_DATA(file_inode(seq->file));  in ext4_mb_seq_groups_show()
2523 					     sb->s_blocksize_bits,  in ext4_mb_seq_groups_show()
2530 	group--;  in ext4_mb_seq_groups_show()
2544 			seq_printf(seq, "#%-5u: I/O error\n", group);  in ext4_mb_seq_groups_show()
2555 	seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,  in ext4_mb_seq_groups_show()
2558 		seq_printf(seq, " %-5u", i <= blocksize_bits + 1 ?  in ext4_mb_seq_groups_show()
2578 	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;  in get_groupinfo_cache()
2586  * Allocate the top-level s_group_info array for the specified number
2595 	size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>  in ext4_mb_alloc_groupinfo()
2597 	if (size <= sbi->s_group_info_size)  in ext4_mb_alloc_groupinfo()
2600 	size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);  in ext4_mb_alloc_groupinfo()
2604 		return -ENOMEM;  in ext4_mb_alloc_groupinfo()
2607 	old_groupinfo = rcu_dereference(sbi->s_group_info);  in ext4_mb_alloc_groupinfo()
2610 		       sbi->s_group_info_size * sizeof(*sbi->s_group_info));  in ext4_mb_alloc_groupinfo()
2612 	rcu_assign_pointer(sbi->s_group_info, new_groupinfo);  in ext4_mb_alloc_groupinfo()
2613 	sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);  in ext4_mb_alloc_groupinfo()
2617 		   sbi->s_group_info_size);  in ext4_mb_alloc_groupinfo()
2630 	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);  in ext4_mb_add_groupinfo()
2647 		rcu_dereference(sbi->s_group_info)[idx] = meta_group_info;  in ext4_mb_add_groupinfo()
2652 	i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);  in ext4_mb_add_groupinfo()
2660 		&(meta_group_info[i]->bb_state));  in ext4_mb_add_groupinfo()
2667 	    (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {  in ext4_mb_add_groupinfo()
2668 		meta_group_info[i]->bb_free =  in ext4_mb_add_groupinfo()
2671 		meta_group_info[i]->bb_free =  in ext4_mb_add_groupinfo()
2675 	INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);  in ext4_mb_add_groupinfo()
2676 	init_rwsem(&meta_group_info[i]->alloc_sem);  in ext4_mb_add_groupinfo()
2677 	meta_group_info[i]->bb_free_root = RB_ROOT;  in ext4_mb_add_groupinfo()
2678 	meta_group_info[i]->bb_largest_free_order = -1;  /* uninit */  in ext4_mb_add_groupinfo()
2689 		group_info = rcu_dereference(sbi->s_group_info);  in ext4_mb_add_groupinfo()
2695 	return -ENOMEM;  in ext4_mb_add_groupinfo()
2712 	sbi->s_buddy_cache = new_inode(sb);  in ext4_mb_init_backend()
2713 	if (sbi->s_buddy_cache == NULL) {  in ext4_mb_init_backend()
2717 	/* To avoid potentially colliding with an valid on-disk inode number,  in ext4_mb_init_backend()
2721 	sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;  in ext4_mb_init_backend()
2722 	EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;  in ext4_mb_init_backend()
2736 		sbi->s_mb_prefetch = 1 << sbi->s_es->s_log_groups_per_flex;  in ext4_mb_init_backend()
2737 		sbi->s_mb_prefetch *= 8; /* 8 prefetch IOs in flight at most */  in ext4_mb_init_backend()
2739 		sbi->s_mb_prefetch = 32;  in ext4_mb_init_backend()
2741 	if (sbi->s_mb_prefetch > ext4_get_groups_count(sb))  in ext4_mb_init_backend()
2742 		sbi->s_mb_prefetch = ext4_get_groups_count(sb);  in ext4_mb_init_backend()
2744 	 * given cr=0 is an CPU-related optimization we shouldn't try to  in ext4_mb_init_backend()
2750 	sbi->s_mb_prefetch_limit = sbi->s_mb_prefetch * 4;  in ext4_mb_init_backend()
2751 	if (sbi->s_mb_prefetch_limit > ext4_get_groups_count(sb))  in ext4_mb_init_backend()
2752 		sbi->s_mb_prefetch_limit = ext4_get_groups_count(sb);  in ext4_mb_init_backend()
2757 	cachep = get_groupinfo_cache(sb->s_blocksize_bits);  in ext4_mb_init_backend()
2758 	while (i-- > 0)  in ext4_mb_init_backend()
2760 	i = sbi->s_group_info_size;  in ext4_mb_init_backend()
2762 	group_info = rcu_dereference(sbi->s_group_info);  in ext4_mb_init_backend()
2763 	while (i-- > 0)  in ext4_mb_init_backend()
2766 	iput(sbi->s_buddy_cache);  in ext4_mb_init_backend()
2769 	kvfree(rcu_dereference(sbi->s_group_info));  in ext4_mb_init_backend()
2771 	return -ENOMEM;  in ext4_mb_init_backend()
2789 	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;  in ext4_groupinfo_create_slab()
2793 		return -EINVAL;  in ext4_groupinfo_create_slab()
2816 		       "EXT4-fs: no memory for groupinfo slab cache\n");  in ext4_groupinfo_create_slab()
2817 		return -ENOMEM;  in ext4_groupinfo_create_slab()
2831 	i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_offsets);  in ext4_mb_init()
2833 	sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);  in ext4_mb_init()
2834 	if (sbi->s_mb_offsets == NULL) {  in ext4_mb_init()
2835 		ret = -ENOMEM;  in ext4_mb_init()
2839 	i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_maxs);  in ext4_mb_init()
2840 	sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);  in ext4_mb_init()
2841 	if (sbi->s_mb_maxs == NULL) {  in ext4_mb_init()
2842 		ret = -ENOMEM;  in ext4_mb_init()
2846 	ret = ext4_groupinfo_create_slab(sb->s_blocksize);  in ext4_mb_init()
2851 	sbi->s_mb_maxs[0] = sb->s_blocksize << 3;  in ext4_mb_init()
2852 	sbi->s_mb_offsets[0] = 0;  in ext4_mb_init()
2856 	offset_incr = 1 << (sb->s_blocksize_bits - 1);  in ext4_mb_init()
2857 	max = sb->s_blocksize << 2;  in ext4_mb_init()
2859 		sbi->s_mb_offsets[i] = offset;  in ext4_mb_init()
2860 		sbi->s_mb_maxs[i] = max;  in ext4_mb_init()
2865 	} while (i <= sb->s_blocksize_bits + 1);  in ext4_mb_init()
2867 	spin_lock_init(&sbi->s_md_lock);  in ext4_mb_init()
2868 	spin_lock_init(&sbi->s_bal_lock);  in ext4_mb_init()
2869 	sbi->s_mb_free_pending = 0;  in ext4_mb_init()
2870 	INIT_LIST_HEAD(&sbi->s_freed_data_list);  in ext4_mb_init()
2872 	sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;  in ext4_mb_init()
2873 	sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;  in ext4_mb_init()
2874 	sbi->s_mb_stats = MB_DEFAULT_STATS;  in ext4_mb_init()
2875 	sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;  in ext4_mb_init()
2876 	sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;  in ext4_mb_init()
2877 	sbi->s_mb_max_inode_prealloc = MB_DEFAULT_MAX_INODE_PREALLOC;  in ext4_mb_init()
2890 	sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>  in ext4_mb_init()
2891 				       sbi->s_cluster_bits, 32);  in ext4_mb_init()
2900 	if (sbi->s_stripe > 1) {  in ext4_mb_init()
2901 		sbi->s_mb_group_prealloc = roundup(  in ext4_mb_init()
2902 			sbi->s_mb_group_prealloc, sbi->s_stripe);  in ext4_mb_init()
2905 	sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);  in ext4_mb_init()
2906 	if (sbi->s_locality_groups == NULL) {  in ext4_mb_init()
2907 		ret = -ENOMEM;  in ext4_mb_init()
2912 		lg = per_cpu_ptr(sbi->s_locality_groups, i);  in ext4_mb_init()
2913 		mutex_init(&lg->lg_mutex);  in ext4_mb_init()
2915 			INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);  in ext4_mb_init()
2916 		spin_lock_init(&lg->lg_prealloc_lock);  in ext4_mb_init()
2927 	free_percpu(sbi->s_locality_groups);  in ext4_mb_init()
2928 	sbi->s_locality_groups = NULL;  in ext4_mb_init()
2930 	kfree(sbi->s_mb_offsets);  in ext4_mb_init()
2931 	sbi->s_mb_offsets = NULL;  in ext4_mb_init()
2932 	kfree(sbi->s_mb_maxs);  in ext4_mb_init()
2933 	sbi->s_mb_maxs = NULL;  in ext4_mb_init()
2944 	list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {  in ext4_mb_cleanup_pa()
2946 		list_del(&pa->pa_group_list);  in ext4_mb_cleanup_pa()
2960 	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);  in ext4_mb_release()
2963 	if (sbi->s_group_info) {  in ext4_mb_release()
2977 				EXT4_DESC_PER_BLOCK(sb) - 1) >>  in ext4_mb_release()
2980 		group_info = rcu_dereference(sbi->s_group_info);  in ext4_mb_release()
2986 	kfree(sbi->s_mb_offsets);  in ext4_mb_release()
2987 	kfree(sbi->s_mb_maxs);  in ext4_mb_release()
2988 	iput(sbi->s_buddy_cache);  in ext4_mb_release()
2989 	if (sbi->s_mb_stats) {  in ext4_mb_release()
2992 				atomic_read(&sbi->s_bal_allocated),  in ext4_mb_release()
2993 				atomic_read(&sbi->s_bal_reqs),  in ext4_mb_release()
2994 				atomic_read(&sbi->s_bal_success));  in ext4_mb_release()
2998 				atomic_read(&sbi->s_bal_ex_scanned),  in ext4_mb_release()
2999 				atomic_read(&sbi->s_bal_goals),  in ext4_mb_release()
3000 				atomic_read(&sbi->s_bal_2orders),  in ext4_mb_release()
3001 				atomic_read(&sbi->s_bal_breaks),  in ext4_mb_release()
3002 				atomic_read(&sbi->s_mb_lost_chunks));  in ext4_mb_release()
3005 				sbi->s_mb_buddies_generated,  in ext4_mb_release()
3006 				sbi->s_mb_generation_time);  in ext4_mb_release()
3009 				atomic_read(&sbi->s_mb_preallocated),  in ext4_mb_release()
3010 				atomic_read(&sbi->s_mb_discarded));  in ext4_mb_release()
3013 	free_percpu(sbi->s_locality_groups);  in ext4_mb_release()
3030 		return __blkdev_issue_discard(sb->s_bdev,  in ext4_issue_discard()
3031 			(sector_t)discard_block << (sb->s_blocksize_bits - 9),  in ext4_issue_discard()
3032 			(sector_t)count << (sb->s_blocksize_bits - 9),  in ext4_issue_discard()
3046 		 entry->efd_count, entry->efd_group, entry);  in ext4_free_data_in_buddy()
3048 	err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b);  in ext4_free_data_in_buddy()
3052 	spin_lock(&EXT4_SB(sb)->s_md_lock);  in ext4_free_data_in_buddy()
3053 	EXT4_SB(sb)->s_mb_free_pending -= entry->efd_count;  in ext4_free_data_in_buddy()
3054 	spin_unlock(&EXT4_SB(sb)->s_md_lock);  in ext4_free_data_in_buddy()
3058 	count += entry->efd_count;  in ext4_free_data_in_buddy()
3060 	ext4_lock_group(sb, entry->efd_group);  in ext4_free_data_in_buddy()
3062 	rb_erase(&entry->efd_node, &(db->bb_free_root));  in ext4_free_data_in_buddy()
3063 	mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count);  in ext4_free_data_in_buddy()
3068 	 * If the volume is mounted with -o discard, online discard  in ext4_free_data_in_buddy()
3074 	if (!db->bb_free_root.rb_node) {  in ext4_free_data_in_buddy()
3081 	ext4_unlock_group(sb, entry->efd_group);  in ext4_free_data_in_buddy()
3104 	spin_lock(&sbi->s_md_lock);  in ext4_process_freed_data()
3105 	list_for_each_entry(entry, &sbi->s_freed_data_list, efd_list) {  in ext4_process_freed_data()
3106 		if (entry->efd_tid != commit_tid)  in ext4_process_freed_data()
3108 		cut_pos = &entry->efd_list;  in ext4_process_freed_data()
3111 		list_cut_position(&freed_data_list, &sbi->s_freed_data_list,  in ext4_process_freed_data()
3113 	spin_unlock(&sbi->s_md_lock);  in ext4_process_freed_data()
3117 			err = ext4_issue_discard(sb, entry->efd_group,  in ext4_process_freed_data()
3118 						 entry->efd_start_cluster,  in ext4_process_freed_data()
3119 						 entry->efd_count,  in ext4_process_freed_data()
3121 			if (err && err != -EOPNOTSUPP) {  in ext4_process_freed_data()
3124 					 " with %d", entry->efd_group,  in ext4_process_freed_data()
3125 					 entry->efd_start_cluster,  in ext4_process_freed_data()
3126 					 entry->efd_count, err);  in ext4_process_freed_data()
3127 			} else if (err == -EOPNOTSUPP)  in ext4_process_freed_data()
3165 	return -ENOMEM;  in ext4_init_mballoc()
3183  * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
3198 	BUG_ON(ac->ac_status != AC_STATUS_FOUND);  in ext4_mb_mark_diskspace_used()
3199 	BUG_ON(ac->ac_b_ex.fe_len <= 0);  in ext4_mb_mark_diskspace_used()
3201 	sb = ac->ac_sb;  in ext4_mb_mark_diskspace_used()
3204 	bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);  in ext4_mb_mark_diskspace_used()
3216 	err = -EIO;  in ext4_mb_mark_diskspace_used()
3217 	gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);  in ext4_mb_mark_diskspace_used()
3221 	ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,  in ext4_mb_mark_diskspace_used()
3229 	block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_mark_diskspace_used()
3231 	len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
3232 	if (!ext4_inode_block_valid(ac->ac_inode, block, len)) {  in ext4_mb_mark_diskspace_used()
3233 		ext4_error(sb, "Allocating blocks %llu-%llu which overlap "  in ext4_mb_mark_diskspace_used()
3239 		ext4_lock_group(sb, ac->ac_b_ex.fe_group);  in ext4_mb_mark_diskspace_used()
3240 		ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,  in ext4_mb_mark_diskspace_used()
3241 			      ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
3242 		ext4_unlock_group(sb, ac->ac_b_ex.fe_group);  in ext4_mb_mark_diskspace_used()
3245 			err = -EFSCORRUPTED;  in ext4_mb_mark_diskspace_used()
3249 	ext4_lock_group(sb, ac->ac_b_ex.fe_group);  in ext4_mb_mark_diskspace_used()
3253 		for (i = 0; i < ac->ac_b_ex.fe_len; i++) {  in ext4_mb_mark_diskspace_used()
3254 			BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,  in ext4_mb_mark_diskspace_used()
3255 						bitmap_bh->b_data));  in ext4_mb_mark_diskspace_used()
3259 	ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,  in ext4_mb_mark_diskspace_used()
3260 		      ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
3262 	    (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {  in ext4_mb_mark_diskspace_used()
3263 		gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);  in ext4_mb_mark_diskspace_used()
3266 						ac->ac_b_ex.fe_group, gdp));  in ext4_mb_mark_diskspace_used()
3268 	len = ext4_free_group_clusters(sb, gdp) - ac->ac_b_ex.fe_len;  in ext4_mb_mark_diskspace_used()
3270 	ext4_block_bitmap_csum_set(sb, ac->ac_b_ex.fe_group, gdp, bitmap_bh);  in ext4_mb_mark_diskspace_used()
3271 	ext4_group_desc_csum_set(sb, ac->ac_b_ex.fe_group, gdp);  in ext4_mb_mark_diskspace_used()
3273 	ext4_unlock_group(sb, ac->ac_b_ex.fe_group);  in ext4_mb_mark_diskspace_used()
3274 	percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);  in ext4_mb_mark_diskspace_used()
3278 	if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))  in ext4_mb_mark_diskspace_used()
3280 		percpu_counter_sub(&sbi->s_dirtyclusters_counter,  in ext4_mb_mark_diskspace_used()
3283 	if (sbi->s_log_groups_per_flex) {  in ext4_mb_mark_diskspace_used()
3285 							  ac->ac_b_ex.fe_group);  in ext4_mb_mark_diskspace_used()
3286 		atomic64_sub(ac->ac_b_ex.fe_len,  in ext4_mb_mark_diskspace_used()
3288 						  flex_group)->free_clusters);  in ext4_mb_mark_diskspace_used()
3327 	err = -EIO;  in ext4_mb_mark_bb()
3335 		if (!mb_test_bit(blkoff + i, bitmap_bh->b_data) == !state)  in ext4_mb_mark_bb()
3339 		ext4_set_bits(bitmap_bh->b_data, blkoff, clen);  in ext4_mb_mark_bb()
3341 		mb_test_and_clear_bits(bitmap_bh->b_data, blkoff, clen);  in ext4_mb_mark_bb()
3343 	    (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {  in ext4_mb_mark_bb()
3344 		gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);  in ext4_mb_mark_bb()
3350 		clen = ext4_free_group_clusters(sb, gdp) - clen + already;  in ext4_mb_mark_bb()
3352 		clen = ext4_free_group_clusters(sb, gdp) + clen - already;  in ext4_mb_mark_bb()
3360 	if (sbi->s_log_groups_per_flex) {  in ext4_mb_mark_bb()
3365 						  flex_group)->free_clusters);  in ext4_mb_mark_bb()
3380  * here we normalize request for locality group
3390 	struct super_block *sb = ac->ac_sb;  in ext4_mb_normalize_group_request()
3391 	struct ext4_locality_group *lg = ac->ac_lg;  in ext4_mb_normalize_group_request()
3394 	ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;  in ext4_mb_normalize_group_request()
3395 	mb_debug(sb, "goal %u blocks for locality group\n", ac->ac_g_ex.fe_len);  in ext4_mb_normalize_group_request()
3406 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_normalize_request()
3412 	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);  in ext4_mb_normalize_request()
3417 	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))  in ext4_mb_normalize_request()
3421 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))  in ext4_mb_normalize_request()
3426 	if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)  in ext4_mb_normalize_request()
3429 	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {  in ext4_mb_normalize_request()
3434 	bsbits = ac->ac_sb->s_blocksize_bits;  in ext4_mb_normalize_request()
3438 	size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);  in ext4_mb_normalize_request()
3440 	if (size < i_size_read(ac->ac_inode))  in ext4_mb_normalize_request()
3441 		size = i_size_read(ac->ac_inode);  in ext4_mb_normalize_request()
3468 		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>  in ext4_mb_normalize_request()
3469 						(21 - bsbits)) << 21;  in ext4_mb_normalize_request()
3472 		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>  in ext4_mb_normalize_request()
3473 							(22 - bsbits)) << 22;  in ext4_mb_normalize_request()
3475 	} else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,  in ext4_mb_normalize_request()
3477 		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>  in ext4_mb_normalize_request()
3478 							(23 - bsbits)) << 23;  in ext4_mb_normalize_request()
3481 		start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;  in ext4_mb_normalize_request()
3482 		size	  = (loff_t) EXT4_C2B(EXT4_SB(ac->ac_sb),  in ext4_mb_normalize_request()
3483 					      ac->ac_o_ex.fe_len) << bsbits;  in ext4_mb_normalize_request()
3489 	if (ar->pleft && start <= ar->lleft) {  in ext4_mb_normalize_request()
3490 		size -= ar->lleft + 1 - start;  in ext4_mb_normalize_request()
3491 		start = ar->lleft + 1;  in ext4_mb_normalize_request()
3493 	if (ar->pright && start + size - 1 >= ar->lright)  in ext4_mb_normalize_request()
3494 		size -= start + size - ar->lright;  in ext4_mb_normalize_request()
3500 	if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))  in ext4_mb_normalize_request()
3501 		size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);  in ext4_mb_normalize_request()
3507 	list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {  in ext4_mb_normalize_request()
3510 		if (pa->pa_deleted)  in ext4_mb_normalize_request()
3512 		spin_lock(&pa->pa_lock);  in ext4_mb_normalize_request()
3513 		if (pa->pa_deleted) {  in ext4_mb_normalize_request()
3514 			spin_unlock(&pa->pa_lock);  in ext4_mb_normalize_request()
3518 		pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),  in ext4_mb_normalize_request()
3519 						  pa->pa_len);  in ext4_mb_normalize_request()
3522 		BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||  in ext4_mb_normalize_request()
3523 			ac->ac_o_ex.fe_logical < pa->pa_lstart));  in ext4_mb_normalize_request()
3526 		if (pa->pa_lstart >= end || pa_end <= start) {  in ext4_mb_normalize_request()
3527 			spin_unlock(&pa->pa_lock);  in ext4_mb_normalize_request()
3530 		BUG_ON(pa->pa_lstart <= start && pa_end >= end);  in ext4_mb_normalize_request()
3533 		if (pa_end <= ac->ac_o_ex.fe_logical) {  in ext4_mb_normalize_request()
3536 		} else if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {  in ext4_mb_normalize_request()
3537 			BUG_ON(pa->pa_lstart > end);  in ext4_mb_normalize_request()
3538 			end = pa->pa_lstart;  in ext4_mb_normalize_request()
3540 		spin_unlock(&pa->pa_lock);  in ext4_mb_normalize_request()
3543 	size = end - start;  in ext4_mb_normalize_request()
3547 	list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {  in ext4_mb_normalize_request()
3550 		spin_lock(&pa->pa_lock);  in ext4_mb_normalize_request()
3551 		if (pa->pa_deleted == 0) {  in ext4_mb_normalize_request()
3552 			pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),  in ext4_mb_normalize_request()
3553 							  pa->pa_len);  in ext4_mb_normalize_request()
3554 			BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));  in ext4_mb_normalize_request()
3556 		spin_unlock(&pa->pa_lock);  in ext4_mb_normalize_request()
3560 	if (start + size <= ac->ac_o_ex.fe_logical &&  in ext4_mb_normalize_request()
3561 			start > ac->ac_o_ex.fe_logical) {  in ext4_mb_normalize_request()
3562 		ext4_msg(ac->ac_sb, KERN_ERR,  in ext4_mb_normalize_request()
3565 			 (unsigned long) ac->ac_o_ex.fe_logical);  in ext4_mb_normalize_request()
3568 	BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));  in ext4_mb_normalize_request()
3574 	ac->ac_g_ex.fe_logical = start;  in ext4_mb_normalize_request()
3575 	ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);  in ext4_mb_normalize_request()
3578 	if (ar->pright && (ar->lright == (start + size))) {  in ext4_mb_normalize_request()
3580 		ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,  in ext4_mb_normalize_request()
3581 						&ac->ac_f_ex.fe_group,  in ext4_mb_normalize_request()
3582 						&ac->ac_f_ex.fe_start);  in ext4_mb_normalize_request()
3583 		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;  in ext4_mb_normalize_request()
3585 	if (ar->pleft && (ar->lleft + 1 == start)) {  in ext4_mb_normalize_request()
3587 		ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,  in ext4_mb_normalize_request()
3588 						&ac->ac_f_ex.fe_group,  in ext4_mb_normalize_request()
3589 						&ac->ac_f_ex.fe_start);  in ext4_mb_normalize_request()
3590 		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;  in ext4_mb_normalize_request()
3593 	mb_debug(ac->ac_sb, "goal: %lld(was %lld) blocks at %u\n", size,  in ext4_mb_normalize_request()
3599 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_collect_stats()
3601 	if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {  in ext4_mb_collect_stats()
3602 		atomic_inc(&sbi->s_bal_reqs);  in ext4_mb_collect_stats()
3603 		atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);  in ext4_mb_collect_stats()
3604 		if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)  in ext4_mb_collect_stats()
3605 			atomic_inc(&sbi->s_bal_success);  in ext4_mb_collect_stats()
3606 		atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);  in ext4_mb_collect_stats()
3607 		if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&  in ext4_mb_collect_stats()
3608 				ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)  in ext4_mb_collect_stats()
3609 			atomic_inc(&sbi->s_bal_goals);  in ext4_mb_collect_stats()
3610 		if (ac->ac_found > sbi->s_mb_max_to_scan)  in ext4_mb_collect_stats()
3611 			atomic_inc(&sbi->s_bal_breaks);  in ext4_mb_collect_stats()
3614 	if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)  in ext4_mb_collect_stats()
3624  * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
3628 	struct ext4_prealloc_space *pa = ac->ac_pa;  in ext4_discard_allocated_blocks()
3633 		if (ac->ac_f_ex.fe_len == 0)  in ext4_discard_allocated_blocks()
3635 		err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);  in ext4_discard_allocated_blocks()
3645 		ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);  in ext4_discard_allocated_blocks()
3646 		mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,  in ext4_discard_allocated_blocks()
3647 			       ac->ac_f_ex.fe_len);  in ext4_discard_allocated_blocks()
3648 		ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);  in ext4_discard_allocated_blocks()
3652 	if (pa->pa_type == MB_INODE_PA)  in ext4_discard_allocated_blocks()
3653 		pa->pa_free += ac->ac_b_ex.fe_len;  in ext4_discard_allocated_blocks()
3662 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_use_inode_pa()
3668 	start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);  in ext4_mb_use_inode_pa()
3669 	end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),  in ext4_mb_use_inode_pa()
3670 		  start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));  in ext4_mb_use_inode_pa()
3671 	len = EXT4_NUM_B2C(sbi, end - start);  in ext4_mb_use_inode_pa()
3672 	ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,  in ext4_mb_use_inode_pa()
3673 					&ac->ac_b_ex.fe_start);  in ext4_mb_use_inode_pa()
3674 	ac->ac_b_ex.fe_len = len;  in ext4_mb_use_inode_pa()
3675 	ac->ac_status = AC_STATUS_FOUND;  in ext4_mb_use_inode_pa()
3676 	ac->ac_pa = pa;  in ext4_mb_use_inode_pa()
3678 	BUG_ON(start < pa->pa_pstart);  in ext4_mb_use_inode_pa()
3679 	BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));  in ext4_mb_use_inode_pa()
3680 	BUG_ON(pa->pa_free < len);  in ext4_mb_use_inode_pa()
3681 	pa->pa_free -= len;  in ext4_mb_use_inode_pa()
3683 	mb_debug(ac->ac_sb, "use %llu/%d from inode pa %p\n", start, len, pa);  in ext4_mb_use_inode_pa()
3687  * use blocks preallocated to locality group
3692 	unsigned int len = ac->ac_o_ex.fe_len;  in ext4_mb_use_group_pa()
3694 	ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,  in ext4_mb_use_group_pa()
3695 					&ac->ac_b_ex.fe_group,  in ext4_mb_use_group_pa()
3696 					&ac->ac_b_ex.fe_start);  in ext4_mb_use_group_pa()
3697 	ac->ac_b_ex.fe_len = len;  in ext4_mb_use_group_pa()
3698 	ac->ac_status = AC_STATUS_FOUND;  in ext4_mb_use_group_pa()
3699 	ac->ac_pa = pa;  in ext4_mb_use_group_pa()
3704 	 * in on-disk bitmap -- see ext4_mb_release_context()  in ext4_mb_use_group_pa()
3707 	mb_debug(ac->ac_sb, "use %u/%u from group pa %p\n",  in ext4_mb_use_group_pa()
3708 		 pa->pa_lstart-len, len, pa);  in ext4_mb_use_group_pa()
3725 		atomic_inc(&pa->pa_count);  in ext4_mb_check_group_pa()
3728 	cur_distance = abs(goal_block - cpa->pa_pstart);  in ext4_mb_check_group_pa()
3729 	new_distance = abs(goal_block - pa->pa_pstart);  in ext4_mb_check_group_pa()
3735 	atomic_dec(&cpa->pa_count);  in ext4_mb_check_group_pa()
3736 	atomic_inc(&pa->pa_count);  in ext4_mb_check_group_pa()
3746 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_use_preallocated()
3748 	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);  in ext4_mb_use_preallocated()
3754 	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))  in ext4_mb_use_preallocated()
3757 	/* first, try per-file preallocation */  in ext4_mb_use_preallocated()
3759 	list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {  in ext4_mb_use_preallocated()
3763 		if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||  in ext4_mb_use_preallocated()
3764 		    ac->ac_o_ex.fe_logical >= (pa->pa_lstart +  in ext4_mb_use_preallocated()
3765 					       EXT4_C2B(sbi, pa->pa_len)))  in ext4_mb_use_preallocated()
3768 		/* non-extent files can't have physical blocks past 2^32 */  in ext4_mb_use_preallocated()
3769 		if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&  in ext4_mb_use_preallocated()
3770 		    (pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len) >  in ext4_mb_use_preallocated()
3775 		spin_lock(&pa->pa_lock);  in ext4_mb_use_preallocated()
3776 		if (pa->pa_deleted == 0 && pa->pa_free) {  in ext4_mb_use_preallocated()
3777 			atomic_inc(&pa->pa_count);  in ext4_mb_use_preallocated()
3779 			spin_unlock(&pa->pa_lock);  in ext4_mb_use_preallocated()
3780 			ac->ac_criteria = 10;  in ext4_mb_use_preallocated()
3784 		spin_unlock(&pa->pa_lock);  in ext4_mb_use_preallocated()
3789 	if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))  in ext4_mb_use_preallocated()
3792 	/* inode may have no locality group for some reason */  in ext4_mb_use_preallocated()
3793 	lg = ac->ac_lg;  in ext4_mb_use_preallocated()
3796 	order  = fls(ac->ac_o_ex.fe_len) - 1;  in ext4_mb_use_preallocated()
3797 	if (order > PREALLOC_TB_SIZE - 1)  in ext4_mb_use_preallocated()
3799 		order = PREALLOC_TB_SIZE - 1;  in ext4_mb_use_preallocated()
3801 	goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);  in ext4_mb_use_preallocated()
3808 		list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],  in ext4_mb_use_preallocated()
3810 			spin_lock(&pa->pa_lock);  in ext4_mb_use_preallocated()
3811 			if (pa->pa_deleted == 0 &&  in ext4_mb_use_preallocated()
3812 					pa->pa_free >= ac->ac_o_ex.fe_len) {  in ext4_mb_use_preallocated()
3817 			spin_unlock(&pa->pa_lock);  in ext4_mb_use_preallocated()
3823 		ac->ac_criteria = 20;  in ext4_mb_use_preallocated()
3831  * but not yet committed and marks them used in in-core bitmap.
3843 	n = rb_first(&(grp->bb_free_root));  in ext4_mb_generate_from_freelist()
3847 		ext4_set_bits(bitmap, entry->efd_start_cluster, entry->efd_count);  in ext4_mb_generate_from_freelist()
3855  * used in in-core bitmap. buddy must be generated from this bitmap
3878 	list_for_each(cur, &grp->bb_prealloc_list) {  in ext4_mb_generate_from_pa()
3880 		spin_lock(&pa->pa_lock);  in ext4_mb_generate_from_pa()
3881 		ext4_get_group_no_and_offset(sb, pa->pa_pstart,  in ext4_mb_generate_from_pa()
3883 		len = pa->pa_len;  in ext4_mb_generate_from_pa()
3884 		spin_unlock(&pa->pa_lock);  in ext4_mb_generate_from_pa()
3899 	if (pa->pa_deleted) {  in ext4_mb_mark_pa_deleted()
3901 			     pa->pa_type, pa->pa_pstart, pa->pa_lstart,  in ext4_mb_mark_pa_deleted()
3902 			     pa->pa_len);  in ext4_mb_mark_pa_deleted()
3906 	pa->pa_deleted = 1;  in ext4_mb_mark_pa_deleted()
3908 	if (pa->pa_type == MB_INODE_PA) {  in ext4_mb_mark_pa_deleted()
3909 		ei = EXT4_I(pa->pa_inode);  in ext4_mb_mark_pa_deleted()
3910 		atomic_dec(&ei->i_prealloc_active);  in ext4_mb_mark_pa_deleted()
3919 	BUG_ON(atomic_read(&pa->pa_count));  in ext4_mb_pa_callback()
3920 	BUG_ON(pa->pa_deleted == 0);  in ext4_mb_pa_callback()
3935 	spin_lock(&pa->pa_lock);  in ext4_mb_put_pa()
3936 	if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {  in ext4_mb_put_pa()
3937 		spin_unlock(&pa->pa_lock);  in ext4_mb_put_pa()
3941 	if (pa->pa_deleted == 1) {  in ext4_mb_put_pa()
3942 		spin_unlock(&pa->pa_lock);  in ext4_mb_put_pa()
3947 	spin_unlock(&pa->pa_lock);  in ext4_mb_put_pa()
3949 	grp_blk = pa->pa_pstart;  in ext4_mb_put_pa()
3951 	 * If doing group-based preallocation, pa_pstart may be in the  in ext4_mb_put_pa()
3954 	if (pa->pa_type == MB_GROUP_PA)  in ext4_mb_put_pa()
3955 		grp_blk--;  in ext4_mb_put_pa()
3964 	 *  copy on-disk bitmap to buddy  in ext4_mb_put_pa()
3965 	 *  					mark B in on-disk bitmap  in ext4_mb_put_pa()
3974 	list_del(&pa->pa_group_list);  in ext4_mb_put_pa()
3977 	spin_lock(pa->pa_obj_lock);  in ext4_mb_put_pa()
3978 	list_del_rcu(&pa->pa_inode_list);  in ext4_mb_put_pa()
3979 	spin_unlock(pa->pa_obj_lock);  in ext4_mb_put_pa()
3981 	call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_mb_put_pa()
3990 	struct super_block *sb = ac->ac_sb;  in ext4_mb_new_inode_pa()
3997 	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);  in ext4_mb_new_inode_pa()
3998 	BUG_ON(ac->ac_status != AC_STATUS_FOUND);  in ext4_mb_new_inode_pa()
3999 	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));  in ext4_mb_new_inode_pa()
4000 	BUG_ON(ac->ac_pa == NULL);  in ext4_mb_new_inode_pa()
4002 	pa = ac->ac_pa;  in ext4_mb_new_inode_pa()
4004 	if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {  in ext4_mb_new_inode_pa()
4013 		BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);  in ext4_mb_new_inode_pa()
4014 		BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);  in ext4_mb_new_inode_pa()
4019 		winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;  in ext4_mb_new_inode_pa()
4022 		wins = EXT4_C2B(sbi, ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len);  in ext4_mb_new_inode_pa()
4027 		offs = ac->ac_o_ex.fe_logical %  in ext4_mb_new_inode_pa()
4028 			EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_new_inode_pa()
4032 		ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical -  in ext4_mb_new_inode_pa()
4034 		BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);  in ext4_mb_new_inode_pa()
4035 		BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);  in ext4_mb_new_inode_pa()
4040 	ac->ac_f_ex = ac->ac_b_ex;  in ext4_mb_new_inode_pa()
4042 	pa->pa_lstart = ac->ac_b_ex.fe_logical;  in ext4_mb_new_inode_pa()
4043 	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_new_inode_pa()
4044 	pa->pa_len = ac->ac_b_ex.fe_len;  in ext4_mb_new_inode_pa()
4045 	pa->pa_free = pa->pa_len;  in ext4_mb_new_inode_pa()
4046 	spin_lock_init(&pa->pa_lock);  in ext4_mb_new_inode_pa()
4047 	INIT_LIST_HEAD(&pa->pa_inode_list);  in ext4_mb_new_inode_pa()
4048 	INIT_LIST_HEAD(&pa->pa_group_list);  in ext4_mb_new_inode_pa()
4049 	pa->pa_deleted = 0;  in ext4_mb_new_inode_pa()
4050 	pa->pa_type = MB_INODE_PA;  in ext4_mb_new_inode_pa()
4052 	mb_debug(sb, "new inode pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,  in ext4_mb_new_inode_pa()
4053 		 pa->pa_len, pa->pa_lstart);  in ext4_mb_new_inode_pa()
4057 	atomic_add(pa->pa_free, &sbi->s_mb_preallocated);  in ext4_mb_new_inode_pa()
4059 	ei = EXT4_I(ac->ac_inode);  in ext4_mb_new_inode_pa()
4060 	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);  in ext4_mb_new_inode_pa()
4062 	pa->pa_obj_lock = &ei->i_prealloc_lock;  in ext4_mb_new_inode_pa()
4063 	pa->pa_inode = ac->ac_inode;  in ext4_mb_new_inode_pa()
4065 	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);  in ext4_mb_new_inode_pa()
4067 	spin_lock(pa->pa_obj_lock);  in ext4_mb_new_inode_pa()
4068 	list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);  in ext4_mb_new_inode_pa()
4069 	spin_unlock(pa->pa_obj_lock);  in ext4_mb_new_inode_pa()
4070 	atomic_inc(&ei->i_prealloc_active);  in ext4_mb_new_inode_pa()
4074  * creates new preallocated space for locality group inodes belongs to
4079 	struct super_block *sb = ac->ac_sb;  in ext4_mb_new_group_pa()
4085 	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);  in ext4_mb_new_group_pa()
4086 	BUG_ON(ac->ac_status != AC_STATUS_FOUND);  in ext4_mb_new_group_pa()
4087 	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));  in ext4_mb_new_group_pa()
4088 	BUG_ON(ac->ac_pa == NULL);  in ext4_mb_new_group_pa()
4090 	pa = ac->ac_pa;  in ext4_mb_new_group_pa()
4094 	ac->ac_f_ex = ac->ac_b_ex;  in ext4_mb_new_group_pa()
4096 	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_new_group_pa()
4097 	pa->pa_lstart = pa->pa_pstart;  in ext4_mb_new_group_pa()
4098 	pa->pa_len = ac->ac_b_ex.fe_len;  in ext4_mb_new_group_pa()
4099 	pa->pa_free = pa->pa_len;  in ext4_mb_new_group_pa()
4100 	spin_lock_init(&pa->pa_lock);  in ext4_mb_new_group_pa()
4101 	INIT_LIST_HEAD(&pa->pa_inode_list);  in ext4_mb_new_group_pa()
4102 	INIT_LIST_HEAD(&pa->pa_group_list);  in ext4_mb_new_group_pa()
4103 	pa->pa_deleted = 0;  in ext4_mb_new_group_pa()
4104 	pa->pa_type = MB_GROUP_PA;  in ext4_mb_new_group_pa()
4106 	mb_debug(sb, "new group pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,  in ext4_mb_new_group_pa()
4107 		 pa->pa_len, pa->pa_lstart);  in ext4_mb_new_group_pa()
4111 	atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);  in ext4_mb_new_group_pa()
4113 	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);  in ext4_mb_new_group_pa()
4114 	lg = ac->ac_lg;  in ext4_mb_new_group_pa()
4117 	pa->pa_obj_lock = &lg->lg_prealloc_lock;  in ext4_mb_new_group_pa()
4118 	pa->pa_inode = NULL;  in ext4_mb_new_group_pa()
4120 	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);  in ext4_mb_new_group_pa()
4130 	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)  in ext4_mb_new_preallocation()
4137  * finds all unused blocks in on-disk bitmap, frees them in
4138  * in-core bitmap and buddy.
4142  * TODO: optimize the case when there are no in-core structures yet
4148 	struct super_block *sb = e4b->bd_sb;  in ext4_mb_release_inode_pa()
4157 	BUG_ON(pa->pa_deleted == 0);  in ext4_mb_release_inode_pa()
4158 	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);  in ext4_mb_release_inode_pa()
4159 	grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);  in ext4_mb_release_inode_pa()
4160 	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);  in ext4_mb_release_inode_pa()
4161 	end = bit + pa->pa_len;  in ext4_mb_release_inode_pa()
4164 		bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);  in ext4_mb_release_inode_pa()
4167 		next = mb_find_next_bit(bitmap_bh->b_data, end, bit);  in ext4_mb_release_inode_pa()
4170 			 (unsigned) next - bit, (unsigned) group);  in ext4_mb_release_inode_pa()
4171 		free += next - bit;  in ext4_mb_release_inode_pa()
4173 		trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);  in ext4_mb_release_inode_pa()
4176 					       next - bit);  in ext4_mb_release_inode_pa()
4177 		mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);  in ext4_mb_release_inode_pa()
4180 	if (free != pa->pa_free) {  in ext4_mb_release_inode_pa()
4181 		ext4_msg(e4b->bd_sb, KERN_CRIT,  in ext4_mb_release_inode_pa()
4183 			 pa, (unsigned long) pa->pa_lstart,  in ext4_mb_release_inode_pa()
4184 			 (unsigned long) pa->pa_pstart,  in ext4_mb_release_inode_pa()
4185 			 pa->pa_len);  in ext4_mb_release_inode_pa()
4187 					free, pa->pa_free);  in ext4_mb_release_inode_pa()
4193 	atomic_add(free, &sbi->s_mb_discarded);  in ext4_mb_release_inode_pa()
4202 	struct super_block *sb = e4b->bd_sb;  in ext4_mb_release_group_pa()
4207 	BUG_ON(pa->pa_deleted == 0);  in ext4_mb_release_group_pa()
4208 	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);  in ext4_mb_release_group_pa()
4209 	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);  in ext4_mb_release_group_pa()
4210 	mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);  in ext4_mb_release_group_pa()
4211 	atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);  in ext4_mb_release_group_pa()
4212 	trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);  in ext4_mb_release_group_pa()
4221  * - when do we discard
4223  * - how many do we discard
4240 	if (list_empty(&grp->bb_prealloc_list))  in ext4_mb_discard_group_preallocations()
4246 		ext4_error_err(sb, -err,  in ext4_mb_discard_group_preallocations()
4268 				&grp->bb_prealloc_list, pa_group_list) {  in ext4_mb_discard_group_preallocations()
4269 		spin_lock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
4270 		if (atomic_read(&pa->pa_count)) {  in ext4_mb_discard_group_preallocations()
4271 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
4275 		if (pa->pa_deleted) {  in ext4_mb_discard_group_preallocations()
4276 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
4287 		free += pa->pa_free;  in ext4_mb_discard_group_preallocations()
4289 		spin_unlock(&pa->pa_lock);  in ext4_mb_discard_group_preallocations()
4291 		list_del(&pa->pa_group_list);  in ext4_mb_discard_group_preallocations()
4292 		list_add(&pa->u.pa_tmp_list, &list);  in ext4_mb_discard_group_preallocations()
4298 		/* remove from object (inode or locality group) */  in ext4_mb_discard_group_preallocations()
4299 		spin_lock(pa->pa_obj_lock);  in ext4_mb_discard_group_preallocations()
4300 		list_del_rcu(&pa->pa_inode_list);  in ext4_mb_discard_group_preallocations()
4301 		spin_unlock(pa->pa_obj_lock);  in ext4_mb_discard_group_preallocations()
4303 		if (pa->pa_type == MB_GROUP_PA)  in ext4_mb_discard_group_preallocations()
4308 		list_del(&pa->u.pa_tmp_list);  in ext4_mb_discard_group_preallocations()
4309 		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_mb_discard_group_preallocations()
4326 		 free_total, group, grp->bb_free);  in ext4_mb_discard_group_preallocations()
4331  * releases all non-used preallocated blocks for given inode
4342 	struct super_block *sb = inode->i_sb;  in ext4_discard_preallocations()
4350 	if (!S_ISREG(inode->i_mode)) {  in ext4_discard_preallocations()
4351 		/*BUG_ON(!list_empty(&ei->i_prealloc_list));*/  in ext4_discard_preallocations()
4355 	if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)  in ext4_discard_preallocations()
4359 		 inode->i_ino);  in ext4_discard_preallocations()
4361 			atomic_read(&ei->i_prealloc_active), needed);  in ext4_discard_preallocations()
4370 	spin_lock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
4371 	while (!list_empty(&ei->i_prealloc_list) && needed) {  in ext4_discard_preallocations()
4372 		pa = list_entry(ei->i_prealloc_list.prev,  in ext4_discard_preallocations()
4374 		BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);  in ext4_discard_preallocations()
4375 		spin_lock(&pa->pa_lock);  in ext4_discard_preallocations()
4376 		if (atomic_read(&pa->pa_count)) {  in ext4_discard_preallocations()
4377 			/* this shouldn't happen often - nobody should  in ext4_discard_preallocations()
4379 			spin_unlock(&pa->pa_lock);  in ext4_discard_preallocations()
4380 			spin_unlock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
4382 				 "uh-oh! used pa while discarding");  in ext4_discard_preallocations()
4388 		if (pa->pa_deleted == 0) {  in ext4_discard_preallocations()
4390 			spin_unlock(&pa->pa_lock);  in ext4_discard_preallocations()
4391 			list_del_rcu(&pa->pa_inode_list);  in ext4_discard_preallocations()
4392 			list_add(&pa->u.pa_tmp_list, &list);  in ext4_discard_preallocations()
4393 			needed--;  in ext4_discard_preallocations()
4398 		spin_unlock(&pa->pa_lock);  in ext4_discard_preallocations()
4399 		spin_unlock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
4404 		 * ->clear_inode() the inode will get freed  in ext4_discard_preallocations()
4407 		 * freed memory, bad-bad-bad */  in ext4_discard_preallocations()
4411 		 * of ->clear_inode(), but not in case of  in ext4_discard_preallocations()
4416 	spin_unlock(&ei->i_prealloc_lock);  in ext4_discard_preallocations()
4419 		BUG_ON(pa->pa_type != MB_INODE_PA);  in ext4_discard_preallocations()
4420 		group = ext4_get_group_number(sb, pa->pa_pstart);  in ext4_discard_preallocations()
4425 			ext4_error_err(sb, -err, "Error %d loading buddy information for %u",  in ext4_discard_preallocations()
4433 			ext4_error_err(sb, -err, "Error %d reading block bitmap for %u",  in ext4_discard_preallocations()
4440 		list_del(&pa->pa_group_list);  in ext4_discard_preallocations()
4447 		list_del(&pa->u.pa_tmp_list);  in ext4_discard_preallocations()
4448 		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_discard_preallocations()
4459 		return -ENOMEM;  in ext4_mb_pa_alloc()
4460 	atomic_set(&pa->pa_count, 1);  in ext4_mb_pa_alloc()
4461 	ac->ac_pa = pa;  in ext4_mb_pa_alloc()
4467 	struct ext4_prealloc_space *pa = ac->ac_pa;  in ext4_mb_pa_free()
4470 	ac->ac_pa = NULL;  in ext4_mb_pa_free()
4471 	WARN_ON(!atomic_dec_and_test(&pa->pa_count));  in ext4_mb_pa_free()
4491 		list_for_each(cur, &grp->bb_prealloc_list) {  in ext4_mb_show_pa()
4494 			spin_lock(&pa->pa_lock);  in ext4_mb_show_pa()
4495 			ext4_get_group_no_and_offset(sb, pa->pa_pstart,  in ext4_mb_show_pa()
4497 			spin_unlock(&pa->pa_lock);  in ext4_mb_show_pa()
4499 				 pa->pa_len);  in ext4_mb_show_pa()
4502 		mb_debug(sb, "%u: %d/%d\n", i, grp->bb_free,  in ext4_mb_show_pa()
4503 			 grp->bb_fragments);  in ext4_mb_show_pa()
4509 	struct super_block *sb = ac->ac_sb;  in ext4_mb_show_ac()
4517 			ac->ac_status, ac->ac_flags);  in ext4_mb_show_ac()
4521 			(unsigned long)ac->ac_o_ex.fe_group,  in ext4_mb_show_ac()
4522 			(unsigned long)ac->ac_o_ex.fe_start,  in ext4_mb_show_ac()
4523 			(unsigned long)ac->ac_o_ex.fe_len,  in ext4_mb_show_ac()
4524 			(unsigned long)ac->ac_o_ex.fe_logical,  in ext4_mb_show_ac()
4525 			(unsigned long)ac->ac_g_ex.fe_group,  in ext4_mb_show_ac()
4526 			(unsigned long)ac->ac_g_ex.fe_start,  in ext4_mb_show_ac()
4527 			(unsigned long)ac->ac_g_ex.fe_len,  in ext4_mb_show_ac()
4528 			(unsigned long)ac->ac_g_ex.fe_logical,  in ext4_mb_show_ac()
4529 			(unsigned long)ac->ac_b_ex.fe_group,  in ext4_mb_show_ac()
4530 			(unsigned long)ac->ac_b_ex.fe_start,  in ext4_mb_show_ac()
4531 			(unsigned long)ac->ac_b_ex.fe_len,  in ext4_mb_show_ac()
4532 			(unsigned long)ac->ac_b_ex.fe_logical,  in ext4_mb_show_ac()
4533 			(int)ac->ac_criteria);  in ext4_mb_show_ac()
4534 	mb_debug(sb, "%u found", ac->ac_found);  in ext4_mb_show_ac()
4544 	ext4_mb_show_pa(ac->ac_sb);  in ext4_mb_show_ac()
4550  * We use locality group preallocation for small size file. The size of the
4558 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_group_or_file()
4559 	int bsbits = ac->ac_sb->s_blocksize_bits;  in ext4_mb_group_or_file()
4562 	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))  in ext4_mb_group_or_file()
4565 	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))  in ext4_mb_group_or_file()
4568 	size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);  in ext4_mb_group_or_file()
4569 	isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)  in ext4_mb_group_or_file()
4573 	    !inode_is_open_for_write(ac->ac_inode)) {  in ext4_mb_group_or_file()
4574 		ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;  in ext4_mb_group_or_file()
4578 	if (sbi->s_mb_group_prealloc <= 0) {  in ext4_mb_group_or_file()
4579 		ac->ac_flags |= EXT4_MB_STREAM_ALLOC;  in ext4_mb_group_or_file()
4585 	if (size > sbi->s_mb_stream_request) {  in ext4_mb_group_or_file()
4586 		ac->ac_flags |= EXT4_MB_STREAM_ALLOC;  in ext4_mb_group_or_file()
4590 	BUG_ON(ac->ac_lg != NULL);  in ext4_mb_group_or_file()
4592 	 * locality group prealloc space are per cpu. The reason for having  in ext4_mb_group_or_file()
4593 	 * per cpu locality group is to reduce the contention between block  in ext4_mb_group_or_file()
4596 	ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);  in ext4_mb_group_or_file()
4599 	ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;  in ext4_mb_group_or_file()
4602 	mutex_lock(&ac->ac_lg->lg_mutex);  in ext4_mb_group_or_file()
4609 	struct super_block *sb = ar->inode->i_sb;  in ext4_mb_initialize_context()
4611 	struct ext4_super_block *es = sbi->s_es;  in ext4_mb_initialize_context()
4618 	len = ar->len;  in ext4_mb_initialize_context()
4625 	goal = ar->goal;  in ext4_mb_initialize_context()
4626 	if (goal < le32_to_cpu(es->s_first_data_block) ||  in ext4_mb_initialize_context()
4628 		goal = le32_to_cpu(es->s_first_data_block);  in ext4_mb_initialize_context()
4632 	ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);  in ext4_mb_initialize_context()
4633 	ac->ac_status = AC_STATUS_CONTINUE;  in ext4_mb_initialize_context()
4634 	ac->ac_sb = sb;  in ext4_mb_initialize_context()
4635 	ac->ac_inode = ar->inode;  in ext4_mb_initialize_context()
4636 	ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;  in ext4_mb_initialize_context()
4637 	ac->ac_o_ex.fe_group = group;  in ext4_mb_initialize_context()
4638 	ac->ac_o_ex.fe_start = block;  in ext4_mb_initialize_context()
4639 	ac->ac_o_ex.fe_len = len;  in ext4_mb_initialize_context()
4640 	ac->ac_g_ex = ac->ac_o_ex;  in ext4_mb_initialize_context()
4641 	ac->ac_flags = ar->flags;  in ext4_mb_initialize_context()
4644 	 * locality group. this is a policy, actually */  in ext4_mb_initialize_context()
4649 			(unsigned) ar->len, (unsigned) ar->logical,  in ext4_mb_initialize_context()
4650 			(unsigned) ar->goal, ac->ac_flags, ac->ac_2order,  in ext4_mb_initialize_context()
4651 			(unsigned) ar->lleft, (unsigned) ar->pleft,  in ext4_mb_initialize_context()
4652 			(unsigned) ar->lright, (unsigned) ar->pright,  in ext4_mb_initialize_context()
4653 			inode_is_open_for_write(ar->inode) ? "" : "non-");  in ext4_mb_initialize_context()
4668 	mb_debug(sb, "discard locality group preallocation\n");  in ext4_mb_discard_lg_preallocations()
4672 	spin_lock(&lg->lg_prealloc_lock);  in ext4_mb_discard_lg_preallocations()
4673 	list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],  in ext4_mb_discard_lg_preallocations()
4675 				lockdep_is_held(&lg->lg_prealloc_lock)) {  in ext4_mb_discard_lg_preallocations()
4676 		spin_lock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
4677 		if (atomic_read(&pa->pa_count)) {  in ext4_mb_discard_lg_preallocations()
4683 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
4686 		if (pa->pa_deleted) {  in ext4_mb_discard_lg_preallocations()
4687 			spin_unlock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
4691 		BUG_ON(pa->pa_type != MB_GROUP_PA);  in ext4_mb_discard_lg_preallocations()
4695 		spin_unlock(&pa->pa_lock);  in ext4_mb_discard_lg_preallocations()
4697 		list_del_rcu(&pa->pa_inode_list);  in ext4_mb_discard_lg_preallocations()
4698 		list_add(&pa->u.pa_tmp_list, &discard_list);  in ext4_mb_discard_lg_preallocations()
4700 		total_entries--;  in ext4_mb_discard_lg_preallocations()
4711 	spin_unlock(&lg->lg_prealloc_lock);  in ext4_mb_discard_lg_preallocations()
4716 		group = ext4_get_group_number(sb, pa->pa_pstart);  in ext4_mb_discard_lg_preallocations()
4720 			ext4_error_err(sb, -err, "Error %d loading buddy information for %u",  in ext4_mb_discard_lg_preallocations()
4725 		list_del(&pa->pa_group_list);  in ext4_mb_discard_lg_preallocations()
4730 		list_del(&pa->u.pa_tmp_list);  in ext4_mb_discard_lg_preallocations()
4731 		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);  in ext4_mb_discard_lg_preallocations()
4747 	struct super_block *sb = ac->ac_sb;  in ext4_mb_add_n_trim()
4748 	struct ext4_locality_group *lg = ac->ac_lg;  in ext4_mb_add_n_trim()
4749 	struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;  in ext4_mb_add_n_trim()
4751 	order = fls(pa->pa_free) - 1;  in ext4_mb_add_n_trim()
4752 	if (order > PREALLOC_TB_SIZE - 1)  in ext4_mb_add_n_trim()
4754 		order = PREALLOC_TB_SIZE - 1;  in ext4_mb_add_n_trim()
4756 	spin_lock(&lg->lg_prealloc_lock);  in ext4_mb_add_n_trim()
4757 	list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],  in ext4_mb_add_n_trim()
4759 				lockdep_is_held(&lg->lg_prealloc_lock)) {  in ext4_mb_add_n_trim()
4760 		spin_lock(&tmp_pa->pa_lock);  in ext4_mb_add_n_trim()
4761 		if (tmp_pa->pa_deleted) {  in ext4_mb_add_n_trim()
4762 			spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_add_n_trim()
4765 		if (!added && pa->pa_free < tmp_pa->pa_free) {  in ext4_mb_add_n_trim()
4767 			list_add_tail_rcu(&pa->pa_inode_list,  in ext4_mb_add_n_trim()
4768 						&tmp_pa->pa_inode_list);  in ext4_mb_add_n_trim()
4775 		spin_unlock(&tmp_pa->pa_lock);  in ext4_mb_add_n_trim()
4779 		list_add_tail_rcu(&pa->pa_inode_list,  in ext4_mb_add_n_trim()
4780 					&lg->lg_prealloc_list[order]);  in ext4_mb_add_n_trim()
4781 	spin_unlock(&lg->lg_prealloc_lock);  in ext4_mb_add_n_trim()
4793  * if per-inode prealloc list is too long, trim some PA
4798 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);  in ext4_mb_trim_inode_pa()
4801 	count = atomic_read(&ei->i_prealloc_active);  in ext4_mb_trim_inode_pa()
4802 	delta = (sbi->s_mb_max_inode_prealloc >> 2) + 1;  in ext4_mb_trim_inode_pa()
4803 	if (count > sbi->s_mb_max_inode_prealloc + delta) {  in ext4_mb_trim_inode_pa()
4804 		count -= sbi->s_mb_max_inode_prealloc;  in ext4_mb_trim_inode_pa()
4814 	struct inode *inode = ac->ac_inode;  in ext4_mb_release_context()
4816 	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);  in ext4_mb_release_context()
4817 	struct ext4_prealloc_space *pa = ac->ac_pa;  in ext4_mb_release_context()
4819 		if (pa->pa_type == MB_GROUP_PA) {  in ext4_mb_release_context()
4821 			spin_lock(&pa->pa_lock);  in ext4_mb_release_context()
4822 			pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_release_context()
4823 			pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);  in ext4_mb_release_context()
4824 			pa->pa_free -= ac->ac_b_ex.fe_len;  in ext4_mb_release_context()
4825 			pa->pa_len -= ac->ac_b_ex.fe_len;  in ext4_mb_release_context()
4826 			spin_unlock(&pa->pa_lock);  in ext4_mb_release_context()
4834 			if (likely(pa->pa_free)) {  in ext4_mb_release_context()
4835 				spin_lock(pa->pa_obj_lock);  in ext4_mb_release_context()
4836 				list_del_rcu(&pa->pa_inode_list);  in ext4_mb_release_context()
4837 				spin_unlock(pa->pa_obj_lock);  in ext4_mb_release_context()
4842 		if (pa->pa_type == MB_INODE_PA) {  in ext4_mb_release_context()
4844 			 * treat per-inode prealloc list as a lru list, then try  in ext4_mb_release_context()
4847 			spin_lock(pa->pa_obj_lock);  in ext4_mb_release_context()
4848 			list_move(&pa->pa_inode_list, &ei->i_prealloc_list);  in ext4_mb_release_context()
4849 			spin_unlock(pa->pa_obj_lock);  in ext4_mb_release_context()
4852 		ext4_mb_put_pa(ac, ac->ac_sb, pa);  in ext4_mb_release_context()
4854 	if (ac->ac_bitmap_page)  in ext4_mb_release_context()
4855 		put_page(ac->ac_bitmap_page);  in ext4_mb_release_context()
4856 	if (ac->ac_buddy_page)  in ext4_mb_release_context()
4857 		put_page(ac->ac_buddy_page);  in ext4_mb_release_context()
4858 	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)  in ext4_mb_release_context()
4859 		mutex_unlock(&ac->ac_lg->lg_mutex);  in ext4_mb_release_context()
4875 		needed -= ret;  in ext4_mb_discard_preallocations()
4888 	freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);  in ext4_mb_discard_preallocations_should_retry()
4894 	if (!(ac->ac_flags & EXT4_MB_STRICT_CHECK) || seq_retry != *seq) {  in ext4_mb_discard_preallocations_should_retry()
4895 		ac->ac_flags |= EXT4_MB_STRICT_CHECK;  in ext4_mb_discard_preallocations_should_retry()
4925 	sb = ar->inode->i_sb;  in ext4_mb_new_blocks()
4929 	if (sbi->s_mount_state & EXT4_FC_REPLAY)  in ext4_mb_new_blocks()
4933 	if (ext4_is_quota_file(ar->inode))  in ext4_mb_new_blocks()
4934 		ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;  in ext4_mb_new_blocks()
4936 	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {  in ext4_mb_new_blocks()
4941 		while (ar->len &&  in ext4_mb_new_blocks()
4942 			ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {  in ext4_mb_new_blocks()
4946 			ar->len = ar->len >> 1;  in ext4_mb_new_blocks()
4948 		if (!ar->len) {  in ext4_mb_new_blocks()
4950 			*errp = -ENOSPC;  in ext4_mb_new_blocks()
4953 		reserv_clstrs = ar->len;  in ext4_mb_new_blocks()
4954 		if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {  in ext4_mb_new_blocks()
4955 			dquot_alloc_block_nofail(ar->inode,  in ext4_mb_new_blocks()
4956 						 EXT4_C2B(sbi, ar->len));  in ext4_mb_new_blocks()
4958 			while (ar->len &&  in ext4_mb_new_blocks()
4959 				dquot_alloc_block(ar->inode,  in ext4_mb_new_blocks()
4960 						  EXT4_C2B(sbi, ar->len))) {  in ext4_mb_new_blocks()
4962 				ar->flags |= EXT4_MB_HINT_NOPREALLOC;  in ext4_mb_new_blocks()
4963 				ar->len--;  in ext4_mb_new_blocks()
4966 		inquota = ar->len;  in ext4_mb_new_blocks()
4967 		if (ar->len == 0) {  in ext4_mb_new_blocks()
4968 			*errp = -EDQUOT;  in ext4_mb_new_blocks()
4975 		ar->len = 0;  in ext4_mb_new_blocks()
4976 		*errp = -ENOMEM;  in ext4_mb_new_blocks()
4982 		ar->len = 0;  in ext4_mb_new_blocks()
4986 	ac->ac_op = EXT4_MB_HISTORY_PREALLOC;  in ext4_mb_new_blocks()
4989 		ac->ac_op = EXT4_MB_HISTORY_ALLOC;  in ext4_mb_new_blocks()
4999 		 * pa allocated above is added to grp->bb_prealloc_list only  in ext4_mb_new_blocks()
5001 		 * ac->ac_status == AC_STATUS_FOUND.  in ext4_mb_new_blocks()
5002 		 * And error from above mean ac->ac_status != AC_STATUS_FOUND  in ext4_mb_new_blocks()
5010 		if (ac->ac_status == AC_STATUS_FOUND &&  in ext4_mb_new_blocks()
5011 			ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)  in ext4_mb_new_blocks()
5014 	if (likely(ac->ac_status == AC_STATUS_FOUND)) {  in ext4_mb_new_blocks()
5020 			block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);  in ext4_mb_new_blocks()
5021 			ar->len = ac->ac_b_ex.fe_len;  in ext4_mb_new_blocks()
5031 		*errp = -ENOSPC;  in ext4_mb_new_blocks()
5036 		ac->ac_b_ex.fe_len = 0;  in ext4_mb_new_blocks()
5037 		ar->len = 0;  in ext4_mb_new_blocks()
5044 	if (inquota && ar->len < inquota)  in ext4_mb_new_blocks()
5045 		dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));  in ext4_mb_new_blocks()
5046 	if (!ar->len) {  in ext4_mb_new_blocks()
5047 		if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)  in ext4_mb_new_blocks()
5049 			percpu_counter_sub(&sbi->s_dirtyclusters_counter,  in ext4_mb_new_blocks()
5068 	if ((entry->efd_tid != new_entry->efd_tid) ||  in ext4_try_merge_freed_extent()
5069 	    (entry->efd_group != new_entry->efd_group))  in ext4_try_merge_freed_extent()
5071 	if (entry->efd_start_cluster + entry->efd_count ==  in ext4_try_merge_freed_extent()
5072 	    new_entry->efd_start_cluster) {  in ext4_try_merge_freed_extent()
5073 		new_entry->efd_start_cluster = entry->efd_start_cluster;  in ext4_try_merge_freed_extent()
5074 		new_entry->efd_count += entry->efd_count;  in ext4_try_merge_freed_extent()
5075 	} else if (new_entry->efd_start_cluster + new_entry->efd_count ==  in ext4_try_merge_freed_extent()
5076 		   entry->efd_start_cluster) {  in ext4_try_merge_freed_extent()
5077 		new_entry->efd_count += entry->efd_count;  in ext4_try_merge_freed_extent()
5080 	spin_lock(&sbi->s_md_lock);  in ext4_try_merge_freed_extent()
5081 	list_del(&entry->efd_list);  in ext4_try_merge_freed_extent()
5082 	spin_unlock(&sbi->s_md_lock);  in ext4_try_merge_freed_extent()
5083 	rb_erase(&entry->efd_node, entry_rb_root);  in ext4_try_merge_freed_extent()
5091 	ext4_group_t group = e4b->bd_group;  in ext4_mb_free_metadata()
5093 	ext4_grpblk_t clusters = new_entry->efd_count;  in ext4_mb_free_metadata()
5095 	struct ext4_group_info *db = e4b->bd_info;  in ext4_mb_free_metadata()
5096 	struct super_block *sb = e4b->bd_sb;  in ext4_mb_free_metadata()
5098 	struct rb_node **n = &db->bb_free_root.rb_node, *node;  in ext4_mb_free_metadata()
5102 	BUG_ON(e4b->bd_bitmap_page == NULL);  in ext4_mb_free_metadata()
5103 	BUG_ON(e4b->bd_buddy_page == NULL);  in ext4_mb_free_metadata()
5105 	new_node = &new_entry->efd_node;  in ext4_mb_free_metadata()
5106 	cluster = new_entry->efd_start_cluster;  in ext4_mb_free_metadata()
5112 		 * on-disk bitmap and lose not-yet-available  in ext4_mb_free_metadata()
5114 		get_page(e4b->bd_buddy_page);  in ext4_mb_free_metadata()
5115 		get_page(e4b->bd_bitmap_page);  in ext4_mb_free_metadata()
5120 		if (cluster < entry->efd_start_cluster)  in ext4_mb_free_metadata()
5121 			n = &(*n)->rb_left;  in ext4_mb_free_metadata()
5122 		else if (cluster >= (entry->efd_start_cluster + entry->efd_count))  in ext4_mb_free_metadata()
5123 			n = &(*n)->rb_right;  in ext4_mb_free_metadata()
5128 				"Block already on to-be-freed list");  in ext4_mb_free_metadata()
5134 	rb_insert_color(new_node, &db->bb_free_root);  in ext4_mb_free_metadata()
5141 					    &(db->bb_free_root));  in ext4_mb_free_metadata()
5148 					    &(db->bb_free_root));  in ext4_mb_free_metadata()
5151 	spin_lock(&sbi->s_md_lock);  in ext4_mb_free_metadata()
5152 	list_add_tail(&new_entry->efd_list, &sbi->s_freed_data_list);  in ext4_mb_free_metadata()
5153 	sbi->s_mb_free_pending += clusters;  in ext4_mb_free_metadata()
5154 	spin_unlock(&sbi->s_md_lock);  in ext4_mb_free_metadata()
5167 	struct super_block *sb = ar->inode->i_sb;  in ext4_mb_new_blocks_simple()
5170 	int i = sb->s_blocksize;  in ext4_mb_new_blocks_simple()
5172 	struct ext4_super_block *es = EXT4_SB(sb)->s_es;  in ext4_mb_new_blocks_simple()
5174 	goal = ar->goal;  in ext4_mb_new_blocks_simple()
5175 	if (goal < le32_to_cpu(es->s_first_data_block) ||  in ext4_mb_new_blocks_simple()
5177 		goal = le32_to_cpu(es->s_first_data_block);  in ext4_mb_new_blocks_simple()
5179 	ar->len = 0;  in ext4_mb_new_blocks_simple()
5192 		i = mb_find_next_zero_bit(bitmap_bh->b_data, sb->s_blocksize,  in ext4_mb_new_blocks_simple()
5195 		if (i >= sb->s_blocksize)  in ext4_mb_new_blocks_simple()
5203 	if (group >= ext4_get_groups_count(sb) && i >= sb->s_blocksize)  in ext4_mb_new_blocks_simple()
5208 	ar->len = 1;  in ext4_mb_new_blocks_simple()
5217 	struct super_block *sb = inode->i_sb;  in ext4_free_blocks_simple()
5236 		if (!mb_test_bit(blkoff + i, bitmap_bh->b_data))  in ext4_free_blocks_simple()
5239 	mb_clear_bits(bitmap_bh->b_data, blkoff, count);  in ext4_free_blocks_simple()
5245 		count - already_freed);  in ext4_free_blocks_simple()
5255  * ext4_free_blocks() -- Free given blocks and update quota
5268 	struct super_block *sb = inode->i_sb;  in ext4_free_blocks()
5282 	if (sbi->s_mount_state & EXT4_FC_REPLAY) {  in ext4_free_blocks()
5290 			BUG_ON(block != bh->b_blocknr);  in ext4_free_blocks()
5292 			block = bh->b_blocknr;  in ext4_free_blocks()
5297 		ext4_error(sb, "Freeing blocks not in datazone - "  in ext4_free_blocks()
5322 			overflow = sbi->s_cluster_ratio - overflow;  in ext4_free_blocks()
5325 				count -= overflow;  in ext4_free_blocks()
5329 			block -= overflow;  in ext4_free_blocks()
5337 				count -= overflow;  in ext4_free_blocks()
5341 			count += sbi->s_cluster_ratio - overflow;  in ext4_free_blocks()
5351 				bh = sb_find_get_block(inode->i_sb, block + i);  in ext4_free_blocks()
5369 		overflow = EXT4_C2B(sbi, bit) + count -  in ext4_free_blocks()
5371 		count -= overflow;  in ext4_free_blocks()
5382 		err = -EIO;  in ext4_free_blocks()
5389 		     sbi->s_itb_per_group) ||  in ext4_free_blocks()
5390 	    in_range(block + count - 1, ext4_inode_table(sb, gdp),  in ext4_free_blocks()
5391 		     sbi->s_itb_per_group)) {  in ext4_free_blocks()
5393 		ext4_error(sb, "Freeing blocks in system zone - "  in ext4_free_blocks()
5406 	 * to unshare ->b_data if a currently-committing transaction is  in ext4_free_blocks()
5417 			BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));  in ext4_free_blocks()
5444 		new_entry->efd_start_cluster = bit;  in ext4_free_blocks()
5445 		new_entry->efd_group = block_group;  in ext4_free_blocks()
5446 		new_entry->efd_count = count_clusters;  in ext4_free_blocks()
5447 		new_entry->efd_tid = handle->h_transaction->t_tid;  in ext4_free_blocks()
5450 		mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);  in ext4_free_blocks()
5453 		/* need to update group_info->bb_free and bitmap  in ext4_free_blocks()
5460 			if (err && err != -EOPNOTSUPP)  in ext4_free_blocks()
5469 		mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);  in ext4_free_blocks()
5479 	if (sbi->s_log_groups_per_flex) {  in ext4_free_blocks()
5483 						  flex_group)->free_clusters);  in ext4_free_blocks()
5494 		percpu_counter_add(&sbi->s_freeclusters_counter,  in ext4_free_blocks()
5523  * ext4_group_add_blocks() -- Add given blocks to an existing group
5545 	ext4_fsblk_t last_cluster = EXT4_B2C(sbi, block + count - 1);  in ext4_group_add_blocks()
5546 	unsigned long cluster_count = last_cluster - first_cluster + 1;  in ext4_group_add_blocks()
5548 	ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);  in ext4_group_add_blocks()
5561 		err = -EINVAL;  in ext4_group_add_blocks()
5574 		err = -EIO;  in ext4_group_add_blocks()
5580 	    in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||  in ext4_group_add_blocks()
5581 	    in_range(block + count - 1, ext4_inode_table(sb, desc),  in ext4_group_add_blocks()
5582 		     sbi->s_itb_per_group)) {  in ext4_group_add_blocks()
5583 		ext4_error(sb, "Adding blocks in system zones - "  in ext4_group_add_blocks()
5586 		err = -EINVAL;  in ext4_group_add_blocks()
5597 	 * to unshare ->b_data if a currently-committing transaction is  in ext4_group_add_blocks()
5607 		if (!mb_test_bit(bit + i, bitmap_bh->b_data)) {  in ext4_group_add_blocks()
5621 	 * need to update group_info->bb_free and bitmap  in ext4_group_add_blocks()
5626 	mb_clear_bits(bitmap_bh->b_data, bit, cluster_count);  in ext4_group_add_blocks()
5634 	percpu_counter_add(&sbi->s_freeclusters_counter,  in ext4_group_add_blocks()
5637 	if (sbi->s_log_groups_per_flex) {  in ext4_group_add_blocks()
5641 						  flex_group)->free_clusters);  in ext4_group_add_blocks()
5663  * ext4_trim_extent -- function to TRIM one single free extent in the group
5703  * ext4_trim_all_free -- function to trim all free space in alloc. group
5742 	    minblocks >= atomic_read(&EXT4_SB(sb)->s_last_trim_minblks))  in ext4_trim_all_free()
5745 	start = (e4b.bd_info->bb_first_free > start) ?  in ext4_trim_all_free()
5746 		e4b.bd_info->bb_first_free : start;  in ext4_trim_all_free()
5754 		if ((next - start) >= minblocks) {  in ext4_trim_all_free()
5756 					       next - start, group, &e4b);  in ext4_trim_all_free()
5757 			if (ret && ret != -EOPNOTSUPP)  in ext4_trim_all_free()
5760 			count += next - start;  in ext4_trim_all_free()
5762 		free_count += next - start;  in ext4_trim_all_free()
5766 			count = -ERESTARTSYS;  in ext4_trim_all_free()
5776 		if ((e4b.bd_info->bb_free - free_count) < minblocks)  in ext4_trim_all_free()
5795  * ext4_trim_fs() -- trim ioctl handle function
5813 			le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);  in ext4_trim_fs()
5814 	ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);  in ext4_trim_fs()
5817 	start = range->start >> sb->s_blocksize_bits;  in ext4_trim_fs()
5818 	end = start + (range->len >> sb->s_blocksize_bits) - 1;  in ext4_trim_fs()
5820 			      range->minlen >> sb->s_blocksize_bits);  in ext4_trim_fs()
5824 	    range->len < sb->s_blocksize)  in ext4_trim_fs()
5825 		return -EINVAL;  in ext4_trim_fs()
5827 		end = max_blks - 1;  in ext4_trim_fs()
5840 	end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;  in ext4_trim_fs()
5853 		 * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to  in ext4_trim_fs()
5860 		if (grp->bb_free >= minlen) {  in ext4_trim_fs()
5878 		atomic_set(&EXT4_SB(sb)->s_last_trim_minblks, minlen);  in ext4_trim_fs()
5881 	range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;  in ext4_trim_fs()
5907 	start = (e4b.bd_info->bb_first_free > start) ?  in ext4_mballoc_query_range()
5908 		e4b.bd_info->bb_first_free : start;  in ext4_mballoc_query_range()
5910 		end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;  in ext4_mballoc_query_range()
5919 		error = formatter(sb, group, start, next - start, priv);  in ext4_mballoc_query_range()