brintos / linux-shallow public Read only

1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com4 * Written by Alex Tomas <alex@clusterfs.com>5 */6 7 8/*9 * mballoc.c contains the multiblocks allocation routines10 */11 12#include "ext4_jbd2.h"13#include "mballoc.h"14#include <linux/log2.h>15#include <linux/module.h>16#include <linux/slab.h>17#include <linux/nospec.h>18#include <linux/backing-dev.h>19#include <linux/freezer.h>20#include <trace/events/ext4.h>21#include <kunit/static_stub.h>22 23/*24 * MUSTDO:25 *   - test ext4_ext_search_left() and ext4_ext_search_right()26 *   - search for metadata in few groups27 *28 * TODO v4:29 *   - normalization should take into account whether file is still open30 *   - discard preallocations if no free space left (policy?)31 *   - don't normalize tails32 *   - quota33 *   - reservation for superuser34 *35 * TODO v3:36 *   - bitmap read-ahead (proposed by Oleg Drokin aka green)37 *   - track min/max extents in each group for better group selection38 *   - mb_mark_used() may allocate chunk right after splitting buddy39 *   - tree of groups sorted by number of free blocks40 *   - error handling41 */42 43/*44 * The allocation request involve request for multiple number of blocks45 * near to the goal(block) value specified.46 *47 * During initialization phase of the allocator we decide to use the48 * group preallocation or inode preallocation depending on the size of49 * the file. The size of the file could be the resulting file size we50 * would have after allocation, or the current file size, which ever51 * is larger. If the size is less than sbi->s_mb_stream_request we52 * select to use the group preallocation. The default value of53 * s_mb_stream_request is 16 blocks. This can also be tuned via54 * /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in55 * terms of number of blocks.56 *57 * The main motivation for having small file use group preallocation is to58 * ensure that we have small files closer together on the disk.59 *60 * First stage the allocator looks at the inode prealloc list,61 * ext4_inode_info->i_prealloc_list, which contains list of prealloc62 * spaces for this particular inode. The inode prealloc space is63 * represented as:64 *65 * pa_lstart -> the logical start block for this prealloc space66 * pa_pstart -> the physical start block for this prealloc space67 * pa_len    -> length for this prealloc space (in clusters)68 * pa_free   ->  free space available in this prealloc space (in clusters)69 *70 * The inode preallocation space is used looking at the _logical_ start71 * block. If only the logical file block falls within the range of prealloc72 * space we will consume the particular prealloc space. This makes sure that73 * we have contiguous physical blocks representing the file blocks74 *75 * The important thing to be noted in case of inode prealloc space is that76 * we don't modify the values associated to inode prealloc space except77 * pa_free.78 *79 * If we are not able to find blocks in the inode prealloc space and if we80 * have the group allocation flag set then we look at the locality group81 * prealloc space. These are per CPU prealloc list represented as82 *83 * ext4_sb_info.s_locality_groups[smp_processor_id()]84 *85 * The reason for having a per cpu locality group is to reduce the contention86 * between CPUs. It is possible to get scheduled at this point.87 *88 * The locality group prealloc space is used looking at whether we have89 * enough free space (pa_free) within the prealloc space.90 *91 * If we can't allocate blocks via inode prealloc or/and locality group92 * prealloc then we look at the buddy cache. The buddy cache is represented93 * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets94 * mapped to the buddy and bitmap information regarding different95 * groups. The buddy information is attached to buddy cache inode so that96 * we can access them through the page cache. The information regarding97 * each group is loaded via ext4_mb_load_buddy.  The information involve98 * block bitmap and buddy information. The information are stored in the99 * inode as:100 *101 *  {                        page                        }102 *  [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...103 *104 *105 * one block each for bitmap and buddy information.  So for each group we106 * take up 2 blocks. A page can contain blocks_per_page (PAGE_SIZE /107 * blocksize) blocks.  So it can have information regarding groups_per_page108 * which is blocks_per_page/2109 *110 * The buddy cache inode is not stored on disk. The inode is thrown111 * away when the filesystem is unmounted.112 *113 * We look for count number of blocks in the buddy cache. If we were able114 * to locate that many free blocks we return with additional information115 * regarding rest of the contiguous physical block available116 *117 * Before allocating blocks via buddy cache we normalize the request118 * blocks. This ensure we ask for more blocks that we needed. The extra119 * blocks that we get after allocation is added to the respective prealloc120 * list. In case of inode preallocation we follow a list of heuristics121 * based on file size. This can be found in ext4_mb_normalize_request. If122 * we are doing a group prealloc we try to normalize the request to123 * sbi->s_mb_group_prealloc.  The default value of s_mb_group_prealloc is124 * dependent on the cluster size; for non-bigalloc file systems, it is125 * 512 blocks. This can be tuned via126 * /sys/fs/ext4/<partition>/mb_group_prealloc. The value is represented in127 * terms of number of blocks. If we have mounted the file system with -O128 * stripe=<value> option the group prealloc request is normalized to the129 * smallest multiple of the stripe value (sbi->s_stripe) which is130 * greater than the default mb_group_prealloc.131 *132 * If "mb_optimize_scan" mount option is set, we maintain in memory group info133 * structures in two data structures:134 *135 * 1) Array of largest free order lists (sbi->s_mb_largest_free_orders)136 *137 *    Locking: sbi->s_mb_largest_free_orders_locks(array of rw locks)138 *139 *    This is an array of lists where the index in the array represents the140 *    largest free order in the buddy bitmap of the participating group infos of141 *    that list. So, there are exactly MB_NUM_ORDERS(sb) (which means total142 *    number of buddy bitmap orders possible) number of lists. Group-infos are143 *    placed in appropriate lists.144 *145 * 2) Average fragment size lists (sbi->s_mb_avg_fragment_size)146 *147 *    Locking: sbi->s_mb_avg_fragment_size_locks(array of rw locks)148 *149 *    This is an array of lists where in the i-th list there are groups with150 *    average fragment size >= 2^i and < 2^(i+1). The average fragment size151 *    is computed as ext4_group_info->bb_free / ext4_group_info->bb_fragments.152 *    Note that we don't bother with a special list for completely empty groups153 *    so we only have MB_NUM_ORDERS(sb) lists.154 *155 * When "mb_optimize_scan" mount option is set, mballoc consults the above data156 * structures to decide the order in which groups are to be traversed for157 * fulfilling an allocation request.158 *159 * At CR_POWER2_ALIGNED , we look for groups which have the largest_free_order160 * >= the order of the request. We directly look at the largest free order list161 * in the data structure (1) above where largest_free_order = order of the162 * request. If that list is empty, we look at remaining list in the increasing163 * order of largest_free_order. This allows us to perform CR_POWER2_ALIGNED164 * lookup in O(1) time.165 *166 * At CR_GOAL_LEN_FAST, we only consider groups where167 * average fragment size > request size. So, we lookup a group which has average168 * fragment size just above or equal to request size using our average fragment169 * size group lists (data structure 2) in O(1) time.170 *171 * At CR_BEST_AVAIL_LEN, we aim to optimize allocations which can't be satisfied172 * in CR_GOAL_LEN_FAST. The fact that we couldn't find a group in173 * CR_GOAL_LEN_FAST suggests that there is no BG that has avg174 * fragment size > goal length. So before falling to the slower175 * CR_GOAL_LEN_SLOW, in CR_BEST_AVAIL_LEN we proactively trim goal length and176 * then use the same fragment lists as CR_GOAL_LEN_FAST to find a BG with a big177 * enough average fragment size. This increases the chances of finding a178 * suitable block group in O(1) time and results in faster allocation at the179 * cost of reduced size of allocation.180 *181 * If "mb_optimize_scan" mount option is not set, mballoc traverses groups in182 * linear order which requires O(N) search time for each CR_POWER2_ALIGNED and183 * CR_GOAL_LEN_FAST phase.184 *185 * The regular allocator (using the buddy cache) supports a few tunables.186 *187 * /sys/fs/ext4/<partition>/mb_min_to_scan188 * /sys/fs/ext4/<partition>/mb_max_to_scan189 * /sys/fs/ext4/<partition>/mb_order2_req190 * /sys/fs/ext4/<partition>/mb_linear_limit191 *192 * The regular allocator uses buddy scan only if the request len is power of193 * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The194 * value of s_mb_order2_reqs can be tuned via195 * /sys/fs/ext4/<partition>/mb_order2_req.  If the request len is equal to196 * stripe size (sbi->s_stripe), we try to search for contiguous block in197 * stripe size. This should result in better allocation on RAID setups. If198 * not, we search in the specific group using bitmap for best extents. The199 * tunable min_to_scan and max_to_scan control the behaviour here.200 * min_to_scan indicate how long the mballoc __must__ look for a best201 * extent and max_to_scan indicates how long the mballoc __can__ look for a202 * best extent in the found extents. Searching for the blocks starts with203 * the group specified as the goal value in allocation context via204 * ac_g_ex. Each group is first checked based on the criteria whether it205 * can be used for allocation. ext4_mb_good_group explains how the groups are206 * checked.207 *208 * When "mb_optimize_scan" is turned on, as mentioned above, the groups may not209 * get traversed linearly. That may result in subsequent allocations being not210 * close to each other. And so, the underlying device may get filled up in a211 * non-linear fashion. While that may not matter on non-rotational devices, for212 * rotational devices that may result in higher seek times. "mb_linear_limit"213 * tells mballoc how many groups mballoc should search linearly before214 * performing consulting above data structures for more efficient lookups. For215 * non rotational devices, this value defaults to 0 and for rotational devices216 * this is set to MB_DEFAULT_LINEAR_LIMIT.217 *218 * Both the prealloc space are getting populated as above. So for the first219 * request we will hit the buddy cache which will result in this prealloc220 * space getting filled. The prealloc space is then later used for the221 * subsequent request.222 */223 224/*225 * mballoc operates on the following data:226 *  - on-disk bitmap227 *  - in-core buddy (actually includes buddy and bitmap)228 *  - preallocation descriptors (PAs)229 *230 * there are two types of preallocations:231 *  - inode232 *    assiged to specific inode and can be used for this inode only.233 *    it describes part of inode's space preallocated to specific234 *    physical blocks. any block from that preallocated can be used235 *    independent. the descriptor just tracks number of blocks left236 *    unused. so, before taking some block from descriptor, one must237 *    make sure corresponded logical block isn't allocated yet. this238 *    also means that freeing any block within descriptor's range239 *    must discard all preallocated blocks.240 *  - locality group241 *    assigned to specific locality group which does not translate to242 *    permanent set of inodes: inode can join and leave group. space243 *    from this type of preallocation can be used for any inode. thus244 *    it's consumed from the beginning to the end.245 *246 * relation between them can be expressed as:247 *    in-core buddy = on-disk bitmap + preallocation descriptors248 *249 * this mean blocks mballoc considers used are:250 *  - allocated blocks (persistent)251 *  - preallocated blocks (non-persistent)252 *253 * consistency in mballoc world means that at any time a block is either254 * free or used in ALL structures. notice: "any time" should not be read255 * literally -- time is discrete and delimited by locks.256 *257 *  to keep it simple, we don't use block numbers, instead we count number of258 *  blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.259 *260 * all operations can be expressed as:261 *  - init buddy:			buddy = on-disk + PAs262 *  - new PA:				buddy += N; PA = N263 *  - use inode PA:			on-disk += N; PA -= N264 *  - discard inode PA			buddy -= on-disk - PA; PA = 0265 *  - use locality group PA		on-disk += N; PA -= N266 *  - discard locality group PA		buddy -= PA; PA = 0267 *  note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap268 *        is used in real operation because we can't know actual used269 *        bits from PA, only from on-disk bitmap270 *271 * if we follow this strict logic, then all operations above should be atomic.272 * given some of them can block, we'd have to use something like semaphores273 * killing performance on high-end SMP hardware. let's try to relax it using274 * the following knowledge:275 *  1) if buddy is referenced, it's already initialized276 *  2) while block is used in buddy and the buddy is referenced,277 *     nobody can re-allocate that block278 *  3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has279 *     bit set and PA claims same block, it's OK. IOW, one can set bit in280 *     on-disk bitmap if buddy has same bit set or/and PA covers corresponded281 *     block282 *283 * so, now we're building a concurrency table:284 *  - init buddy vs.285 *    - new PA286 *      blocks for PA are allocated in the buddy, buddy must be referenced287 *      until PA is linked to allocation group to avoid concurrent buddy init288 *    - use inode PA289 *      we need to make sure that either on-disk bitmap or PA has uptodate data290 *      given (3) we care that PA-=N operation doesn't interfere with init291 *    - discard inode PA292 *      the simplest way would be to have buddy initialized by the discard293 *    - use locality group PA294 *      again PA-=N must be serialized with init295 *    - discard locality group PA296 *      the simplest way would be to have buddy initialized by the discard297 *  - new PA vs.298 *    - use inode PA299 *      i_data_sem serializes them300 *    - discard inode PA301 *      discard process must wait until PA isn't used by another process302 *    - use locality group PA303 *      some mutex should serialize them304 *    - discard locality group PA305 *      discard process must wait until PA isn't used by another process306 *  - use inode PA307 *    - use inode PA308 *      i_data_sem or another mutex should serializes them309 *    - discard inode PA310 *      discard process must wait until PA isn't used by another process311 *    - use locality group PA312 *      nothing wrong here -- they're different PAs covering different blocks313 *    - discard locality group PA314 *      discard process must wait until PA isn't used by another process315 *316 * now we're ready to make few consequences:317 *  - PA is referenced and while it is no discard is possible318 *  - PA is referenced until block isn't marked in on-disk bitmap319 *  - PA changes only after on-disk bitmap320 *  - discard must not compete with init. either init is done before321 *    any discard or they're serialized somehow322 *  - buddy init as sum of on-disk bitmap and PAs is done atomically323 *324 * a special case when we've used PA to emptiness. no need to modify buddy325 * in this case, but we should care about concurrent init326 *327 */328 329 /*330 * Logic in few words:331 *332 *  - allocation:333 *    load group334 *    find blocks335 *    mark bits in on-disk bitmap336 *    release group337 *338 *  - use preallocation:339 *    find proper PA (per-inode or group)340 *    load group341 *    mark bits in on-disk bitmap342 *    release group343 *    release PA344 *345 *  - free:346 *    load group347 *    mark bits in on-disk bitmap348 *    release group349 *350 *  - discard preallocations in group:351 *    mark PAs deleted352 *    move them onto local list353 *    load on-disk bitmap354 *    load group355 *    remove PA from object (inode or locality group)356 *    mark free blocks in-core357 *358 *  - discard inode's preallocations:359 */360 361/*362 * Locking rules363 *364 * Locks:365 *  - bitlock on a group	(group)366 *  - object (inode/locality)	(object)367 *  - per-pa lock		(pa)368 *  - cr_power2_aligned lists lock	(cr_power2_aligned)369 *  - cr_goal_len_fast lists lock	(cr_goal_len_fast)370 *371 * Paths:372 *  - new pa373 *    object374 *    group375 *376 *  - find and use pa:377 *    pa378 *379 *  - release consumed pa:380 *    pa381 *    group382 *    object383 *384 *  - generate in-core bitmap:385 *    group386 *        pa387 *388 *  - discard all for given object (inode, locality group):389 *    object390 *        pa391 *    group392 *393 *  - discard all for given group:394 *    group395 *        pa396 *    group397 *        object398 *399 *  - allocation path (ext4_mb_regular_allocator)400 *    group401 *    cr_power2_aligned/cr_goal_len_fast402 */403static struct kmem_cache *ext4_pspace_cachep;404static struct kmem_cache *ext4_ac_cachep;405static struct kmem_cache *ext4_free_data_cachep;406 407/* We create slab caches for groupinfo data structures based on the408 * superblock block size.  There will be one per mounted filesystem for409 * each unique s_blocksize_bits */410#define NR_GRPINFO_CACHES 8411static struct kmem_cache *ext4_groupinfo_caches[NR_GRPINFO_CACHES];412 413static const char * const ext4_groupinfo_slab_names[NR_GRPINFO_CACHES] = {414	"ext4_groupinfo_1k", "ext4_groupinfo_2k", "ext4_groupinfo_4k",415	"ext4_groupinfo_8k", "ext4_groupinfo_16k", "ext4_groupinfo_32k",416	"ext4_groupinfo_64k", "ext4_groupinfo_128k"417};418 419static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,420					ext4_group_t group);421static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);422 423static bool ext4_mb_good_group(struct ext4_allocation_context *ac,424			       ext4_group_t group, enum criteria cr);425 426static int ext4_try_to_trim_range(struct super_block *sb,427		struct ext4_buddy *e4b, ext4_grpblk_t start,428		ext4_grpblk_t max, ext4_grpblk_t minblocks);429 430/*431 * The algorithm using this percpu seq counter goes below:432 * 1. We sample the percpu discard_pa_seq counter before trying for block433 *    allocation in ext4_mb_new_blocks().434 * 2. We increment this percpu discard_pa_seq counter when we either allocate435 *    or free these blocks i.e. while marking those blocks as used/free in436 *    mb_mark_used()/mb_free_blocks().437 * 3. We also increment this percpu seq counter when we successfully identify438 *    that the bb_prealloc_list is not empty and hence proceed for discarding439 *    of those PAs inside ext4_mb_discard_group_preallocations().440 *441 * Now to make sure that the regular fast path of block allocation is not442 * affected, as a small optimization we only sample the percpu seq counter443 * on that cpu. Only when the block allocation fails and when freed blocks444 * found were 0, that is when we sample percpu seq counter for all cpus using445 * below function ext4_get_discard_pa_seq_sum(). This happens after making446 * sure that all the PAs on grp->bb_prealloc_list got freed or if it's empty.447 */448static DEFINE_PER_CPU(u64, discard_pa_seq);449static inline u64 ext4_get_discard_pa_seq_sum(void)450{451	int __cpu;452	u64 __seq = 0;453 454	for_each_possible_cpu(__cpu)455		__seq += per_cpu(discard_pa_seq, __cpu);456	return __seq;457}458 459static inline void *mb_correct_addr_and_bit(int *bit, void *addr)460{461#if BITS_PER_LONG == 64462	*bit += ((unsigned long) addr & 7UL) << 3;463	addr = (void *) ((unsigned long) addr & ~7UL);464#elif BITS_PER_LONG == 32465	*bit += ((unsigned long) addr & 3UL) << 3;466	addr = (void *) ((unsigned long) addr & ~3UL);467#else468#error "how many bits you are?!"469#endif470	return addr;471}472 473static inline int mb_test_bit(int bit, void *addr)474{475	/*476	 * ext4_test_bit on architecture like powerpc477	 * needs unsigned long aligned address478	 */479	addr = mb_correct_addr_and_bit(&bit, addr);480	return ext4_test_bit(bit, addr);481}482 483static inline void mb_set_bit(int bit, void *addr)484{485	addr = mb_correct_addr_and_bit(&bit, addr);486	ext4_set_bit(bit, addr);487}488 489static inline void mb_clear_bit(int bit, void *addr)490{491	addr = mb_correct_addr_and_bit(&bit, addr);492	ext4_clear_bit(bit, addr);493}494 495static inline int mb_test_and_clear_bit(int bit, void *addr)496{497	addr = mb_correct_addr_and_bit(&bit, addr);498	return ext4_test_and_clear_bit(bit, addr);499}500 501static inline int mb_find_next_zero_bit(void *addr, int max, int start)502{503	int fix = 0, ret, tmpmax;504	addr = mb_correct_addr_and_bit(&fix, addr);505	tmpmax = max + fix;506	start += fix;507 508	ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;509	if (ret > max)510		return max;511	return ret;512}513 514static inline int mb_find_next_bit(void *addr, int max, int start)515{516	int fix = 0, ret, tmpmax;517	addr = mb_correct_addr_and_bit(&fix, addr);518	tmpmax = max + fix;519	start += fix;520 521	ret = ext4_find_next_bit(addr, tmpmax, start) - fix;522	if (ret > max)523		return max;524	return ret;525}526 527static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)528{529	char *bb;530 531	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);532	BUG_ON(max == NULL);533 534	if (order > e4b->bd_blkbits + 1) {535		*max = 0;536		return NULL;537	}538 539	/* at order 0 we see each particular block */540	if (order == 0) {541		*max = 1 << (e4b->bd_blkbits + 3);542		return e4b->bd_bitmap;543	}544 545	bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];546	*max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];547 548	return bb;549}550 551#ifdef DOUBLE_CHECK552static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,553			   int first, int count)554{555	int i;556	struct super_block *sb = e4b->bd_sb;557 558	if (unlikely(e4b->bd_info->bb_bitmap == NULL))559		return;560	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));561	for (i = 0; i < count; i++) {562		if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {563			ext4_fsblk_t blocknr;564 565			blocknr = ext4_group_first_block_no(sb, e4b->bd_group);566			blocknr += EXT4_C2B(EXT4_SB(sb), first + i);567			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,568					EXT4_GROUP_INFO_BBITMAP_CORRUPT);569			ext4_grp_locked_error(sb, e4b->bd_group,570					      inode ? inode->i_ino : 0,571					      blocknr,572					      "freeing block already freed "573					      "(bit %u)",574					      first + i);575		}576		mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);577	}578}579 580static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)581{582	int i;583 584	if (unlikely(e4b->bd_info->bb_bitmap == NULL))585		return;586	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));587	for (i = 0; i < count; i++) {588		BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));589		mb_set_bit(first + i, e4b->bd_info->bb_bitmap);590	}591}592 593static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)594{595	if (unlikely(e4b->bd_info->bb_bitmap == NULL))596		return;597	if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {598		unsigned char *b1, *b2;599		int i;600		b1 = (unsigned char *) e4b->bd_info->bb_bitmap;601		b2 = (unsigned char *) bitmap;602		for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {603			if (b1[i] != b2[i]) {604				ext4_msg(e4b->bd_sb, KERN_ERR,605					 "corruption in group %u "606					 "at byte %u(%u): %x in copy != %x "607					 "on disk/prealloc",608					 e4b->bd_group, i, i * 8, b1[i], b2[i]);609				BUG();610			}611		}612	}613}614 615static void mb_group_bb_bitmap_alloc(struct super_block *sb,616			struct ext4_group_info *grp, ext4_group_t group)617{618	struct buffer_head *bh;619 620	grp->bb_bitmap = kmalloc(sb->s_blocksize, GFP_NOFS);621	if (!grp->bb_bitmap)622		return;623 624	bh = ext4_read_block_bitmap(sb, group);625	if (IS_ERR_OR_NULL(bh)) {626		kfree(grp->bb_bitmap);627		grp->bb_bitmap = NULL;628		return;629	}630 631	memcpy(grp->bb_bitmap, bh->b_data, sb->s_blocksize);632	put_bh(bh);633}634 635static void mb_group_bb_bitmap_free(struct ext4_group_info *grp)636{637	kfree(grp->bb_bitmap);638}639 640#else641static inline void mb_free_blocks_double(struct inode *inode,642				struct ext4_buddy *e4b, int first, int count)643{644	return;645}646static inline void mb_mark_used_double(struct ext4_buddy *e4b,647						int first, int count)648{649	return;650}651static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)652{653	return;654}655 656static inline void mb_group_bb_bitmap_alloc(struct super_block *sb,657			struct ext4_group_info *grp, ext4_group_t group)658{659	return;660}661 662static inline void mb_group_bb_bitmap_free(struct ext4_group_info *grp)663{664	return;665}666#endif667 668#ifdef AGGRESSIVE_CHECK669 670#define MB_CHECK_ASSERT(assert)						\671do {									\672	if (!(assert)) {						\673		printk(KERN_EMERG					\674			"Assertion failure in %s() at %s:%d: \"%s\"\n",	\675			function, file, line, # assert);		\676		BUG();							\677	}								\678} while (0)679 680static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,681				const char *function, int line)682{683	struct super_block *sb = e4b->bd_sb;684	int order = e4b->bd_blkbits + 1;685	int max;686	int max2;687	int i;688	int j;689	int k;690	int count;691	struct ext4_group_info *grp;692	int fragments = 0;693	int fstart;694	struct list_head *cur;695	void *buddy;696	void *buddy2;697 698	if (e4b->bd_info->bb_check_counter++ % 10)699		return;700 701	while (order > 1) {702		buddy = mb_find_buddy(e4b, order, &max);703		MB_CHECK_ASSERT(buddy);704		buddy2 = mb_find_buddy(e4b, order - 1, &max2);705		MB_CHECK_ASSERT(buddy2);706		MB_CHECK_ASSERT(buddy != buddy2);707		MB_CHECK_ASSERT(max * 2 == max2);708 709		count = 0;710		for (i = 0; i < max; i++) {711 712			if (mb_test_bit(i, buddy)) {713				/* only single bit in buddy2 may be 0 */714				if (!mb_test_bit(i << 1, buddy2)) {715					MB_CHECK_ASSERT(716						mb_test_bit((i<<1)+1, buddy2));717				}718				continue;719			}720 721			/* both bits in buddy2 must be 1 */722			MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));723			MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));724 725			for (j = 0; j < (1 << order); j++) {726				k = (i * (1 << order)) + j;727				MB_CHECK_ASSERT(728					!mb_test_bit(k, e4b->bd_bitmap));729			}730			count++;731		}732		MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);733		order--;734	}735 736	fstart = -1;737	buddy = mb_find_buddy(e4b, 0, &max);738	for (i = 0; i < max; i++) {739		if (!mb_test_bit(i, buddy)) {740			MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);741			if (fstart == -1) {742				fragments++;743				fstart = i;744			}745			continue;746		}747		fstart = -1;748		/* check used bits only */749		for (j = 0; j < e4b->bd_blkbits + 1; j++) {750			buddy2 = mb_find_buddy(e4b, j, &max2);751			k = i >> j;752			MB_CHECK_ASSERT(k < max2);753			MB_CHECK_ASSERT(mb_test_bit(k, buddy2));754		}755	}756	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));757	MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);758 759	grp = ext4_get_group_info(sb, e4b->bd_group);760	if (!grp)761		return;762	list_for_each(cur, &grp->bb_prealloc_list) {763		ext4_group_t groupnr;764		struct ext4_prealloc_space *pa;765		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);766		ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);767		MB_CHECK_ASSERT(groupnr == e4b->bd_group);768		for (i = 0; i < pa->pa_len; i++)769			MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));770	}771}772#undef MB_CHECK_ASSERT773#define mb_check_buddy(e4b) __mb_check_buddy(e4b,	\774					__FILE__, __func__, __LINE__)775#else776#define mb_check_buddy(e4b)777#endif778 779/*780 * Divide blocks started from @first with length @len into781 * smaller chunks with power of 2 blocks.782 * Clear the bits in bitmap which the blocks of the chunk(s) covered,783 * then increase bb_counters[] for corresponded chunk size.784 */785static void ext4_mb_mark_free_simple(struct super_block *sb,786				void *buddy, ext4_grpblk_t first, ext4_grpblk_t len,787					struct ext4_group_info *grp)788{789	struct ext4_sb_info *sbi = EXT4_SB(sb);790	ext4_grpblk_t min;791	ext4_grpblk_t max;792	ext4_grpblk_t chunk;793	unsigned int border;794 795	BUG_ON(len > EXT4_CLUSTERS_PER_GROUP(sb));796 797	border = 2 << sb->s_blocksize_bits;798 799	while (len > 0) {800		/* find how many blocks can be covered since this position */801		max = ffs(first | border) - 1;802 803		/* find how many blocks of power 2 we need to mark */804		min = fls(len) - 1;805 806		if (max < min)807			min = max;808		chunk = 1 << min;809 810		/* mark multiblock chunks only */811		grp->bb_counters[min]++;812		if (min > 0)813			mb_clear_bit(first >> min,814				     buddy + sbi->s_mb_offsets[min]);815 816		len -= chunk;817		first += chunk;818	}819}820 821static int mb_avg_fragment_size_order(struct super_block *sb, ext4_grpblk_t len)822{823	int order;824 825	/*826	 * We don't bother with a special lists groups with only 1 block free827	 * extents and for completely empty groups.828	 */829	order = fls(len) - 2;830	if (order < 0)831		return 0;832	if (order == MB_NUM_ORDERS(sb))833		order--;834	if (WARN_ON_ONCE(order > MB_NUM_ORDERS(sb)))835		order = MB_NUM_ORDERS(sb) - 1;836	return order;837}838 839/* Move group to appropriate avg_fragment_size list */840static void841mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)842{843	struct ext4_sb_info *sbi = EXT4_SB(sb);844	int new_order;845 846	if (!test_opt2(sb, MB_OPTIMIZE_SCAN) || grp->bb_fragments == 0)847		return;848 849	new_order = mb_avg_fragment_size_order(sb,850					grp->bb_free / grp->bb_fragments);851	if (new_order == grp->bb_avg_fragment_size_order)852		return;853 854	if (grp->bb_avg_fragment_size_order != -1) {855		write_lock(&sbi->s_mb_avg_fragment_size_locks[856					grp->bb_avg_fragment_size_order]);857		list_del(&grp->bb_avg_fragment_size_node);858		write_unlock(&sbi->s_mb_avg_fragment_size_locks[859					grp->bb_avg_fragment_size_order]);860	}861	grp->bb_avg_fragment_size_order = new_order;862	write_lock(&sbi->s_mb_avg_fragment_size_locks[863					grp->bb_avg_fragment_size_order]);864	list_add_tail(&grp->bb_avg_fragment_size_node,865		&sbi->s_mb_avg_fragment_size[grp->bb_avg_fragment_size_order]);866	write_unlock(&sbi->s_mb_avg_fragment_size_locks[867					grp->bb_avg_fragment_size_order]);868}869 870/*871 * Choose next group by traversing largest_free_order lists. Updates *new_cr if872 * cr level needs an update.873 */874static void ext4_mb_choose_next_group_p2_aligned(struct ext4_allocation_context *ac,875			enum criteria *new_cr, ext4_group_t *group)876{877	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);878	struct ext4_group_info *iter;879	int i;880 881	if (ac->ac_status == AC_STATUS_FOUND)882		return;883 884	if (unlikely(sbi->s_mb_stats && ac->ac_flags & EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED))885		atomic_inc(&sbi->s_bal_p2_aligned_bad_suggestions);886 887	for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {888		if (list_empty(&sbi->s_mb_largest_free_orders[i]))889			continue;890		read_lock(&sbi->s_mb_largest_free_orders_locks[i]);891		if (list_empty(&sbi->s_mb_largest_free_orders[i])) {892			read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);893			continue;894		}895		list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],896				    bb_largest_free_order_node) {897			if (sbi->s_mb_stats)898				atomic64_inc(&sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]);899			if (likely(ext4_mb_good_group(ac, iter->bb_group, CR_POWER2_ALIGNED))) {900				*group = iter->bb_group;901				ac->ac_flags |= EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED;902				read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);903				return;904			}905		}906		read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);907	}908 909	/* Increment cr and search again if no group is found */910	*new_cr = CR_GOAL_LEN_FAST;911}912 913/*914 * Find a suitable group of given order from the average fragments list.915 */916static struct ext4_group_info *917ext4_mb_find_good_group_avg_frag_lists(struct ext4_allocation_context *ac, int order)918{919	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);920	struct list_head *frag_list = &sbi->s_mb_avg_fragment_size[order];921	rwlock_t *frag_list_lock = &sbi->s_mb_avg_fragment_size_locks[order];922	struct ext4_group_info *grp = NULL, *iter;923	enum criteria cr = ac->ac_criteria;924 925	if (list_empty(frag_list))926		return NULL;927	read_lock(frag_list_lock);928	if (list_empty(frag_list)) {929		read_unlock(frag_list_lock);930		return NULL;931	}932	list_for_each_entry(iter, frag_list, bb_avg_fragment_size_node) {933		if (sbi->s_mb_stats)934			atomic64_inc(&sbi->s_bal_cX_groups_considered[cr]);935		if (likely(ext4_mb_good_group(ac, iter->bb_group, cr))) {936			grp = iter;937			break;938		}939	}940	read_unlock(frag_list_lock);941	return grp;942}943 944/*945 * Choose next group by traversing average fragment size list of suitable946 * order. Updates *new_cr if cr level needs an update.947 */948static void ext4_mb_choose_next_group_goal_fast(struct ext4_allocation_context *ac,949		enum criteria *new_cr, ext4_group_t *group)950{951	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);952	struct ext4_group_info *grp = NULL;953	int i;954 955	if (unlikely(ac->ac_flags & EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED)) {956		if (sbi->s_mb_stats)957			atomic_inc(&sbi->s_bal_goal_fast_bad_suggestions);958	}959 960	for (i = mb_avg_fragment_size_order(ac->ac_sb, ac->ac_g_ex.fe_len);961	     i < MB_NUM_ORDERS(ac->ac_sb); i++) {962		grp = ext4_mb_find_good_group_avg_frag_lists(ac, i);963		if (grp) {964			*group = grp->bb_group;965			ac->ac_flags |= EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED;966			return;967		}968	}969 970	/*971	 * CR_BEST_AVAIL_LEN works based on the concept that we have972	 * a larger normalized goal len request which can be trimmed to973	 * a smaller goal len such that it can still satisfy original974	 * request len. However, allocation request for non-regular975	 * files never gets normalized.976	 * See function ext4_mb_normalize_request() (EXT4_MB_HINT_DATA).977	 */978	if (ac->ac_flags & EXT4_MB_HINT_DATA)979		*new_cr = CR_BEST_AVAIL_LEN;980	else981		*new_cr = CR_GOAL_LEN_SLOW;982}983 984/*985 * We couldn't find a group in CR_GOAL_LEN_FAST so try to find the highest free fragment986 * order we have and proactively trim the goal request length to that order to987 * find a suitable group faster.988 *989 * This optimizes allocation speed at the cost of slightly reduced990 * preallocations. However, we make sure that we don't trim the request too991 * much and fall to CR_GOAL_LEN_SLOW in that case.992 */993static void ext4_mb_choose_next_group_best_avail(struct ext4_allocation_context *ac,994		enum criteria *new_cr, ext4_group_t *group)995{996	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);997	struct ext4_group_info *grp = NULL;998	int i, order, min_order;999	unsigned long num_stripe_clusters = 0;1000 1001	if (unlikely(ac->ac_flags & EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED)) {1002		if (sbi->s_mb_stats)1003			atomic_inc(&sbi->s_bal_best_avail_bad_suggestions);1004	}1005 1006	/*1007	 * mb_avg_fragment_size_order() returns order in a way that makes1008	 * retrieving back the length using (1 << order) inaccurate. Hence, use1009	 * fls() instead since we need to know the actual length while modifying1010	 * goal length.1011	 */1012	order = fls(ac->ac_g_ex.fe_len) - 1;1013	if (WARN_ON_ONCE(order - 1 > MB_NUM_ORDERS(ac->ac_sb)))1014		order = MB_NUM_ORDERS(ac->ac_sb);1015	min_order = order - sbi->s_mb_best_avail_max_trim_order;1016	if (min_order < 0)1017		min_order = 0;1018 1019	if (sbi->s_stripe > 0) {1020		/*1021		 * We are assuming that stripe size is always a multiple of1022		 * cluster ratio otherwise __ext4_fill_super exists early.1023		 */1024		num_stripe_clusters = EXT4_NUM_B2C(sbi, sbi->s_stripe);1025		if (1 << min_order < num_stripe_clusters)1026			/*1027			 * We consider 1 order less because later we round1028			 * up the goal len to num_stripe_clusters1029			 */1030			min_order = fls(num_stripe_clusters) - 1;1031	}1032 1033	if (1 << min_order < ac->ac_o_ex.fe_len)1034		min_order = fls(ac->ac_o_ex.fe_len);1035 1036	for (i = order; i >= min_order; i--) {1037		int frag_order;1038		/*1039		 * Scale down goal len to make sure we find something1040		 * in the free fragments list. Basically, reduce1041		 * preallocations.1042		 */1043		ac->ac_g_ex.fe_len = 1 << i;1044 1045		if (num_stripe_clusters > 0) {1046			/*1047			 * Try to round up the adjusted goal length to1048			 * stripe size (in cluster units) multiple for1049			 * efficiency.1050			 */1051			ac->ac_g_ex.fe_len = roundup(ac->ac_g_ex.fe_len,1052						     num_stripe_clusters);1053		}1054 1055		frag_order = mb_avg_fragment_size_order(ac->ac_sb,1056							ac->ac_g_ex.fe_len);1057 1058		grp = ext4_mb_find_good_group_avg_frag_lists(ac, frag_order);1059		if (grp) {1060			*group = grp->bb_group;1061			ac->ac_flags |= EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED;1062			return;1063		}1064	}1065 1066	/* Reset goal length to original goal length before falling into CR_GOAL_LEN_SLOW */1067	ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;1068	*new_cr = CR_GOAL_LEN_SLOW;1069}1070 1071static inline int should_optimize_scan(struct ext4_allocation_context *ac)1072{1073	if (unlikely(!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN)))1074		return 0;1075	if (ac->ac_criteria >= CR_GOAL_LEN_SLOW)1076		return 0;1077	if (!ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))1078		return 0;1079	return 1;1080}1081 1082/*1083 * Return next linear group for allocation.1084 */1085static ext4_group_t1086next_linear_group(ext4_group_t group, ext4_group_t ngroups)1087{1088	/*1089	 * Artificially restricted ngroups for non-extent1090	 * files makes group > ngroups possible on first loop.1091	 */1092	return group + 1 >= ngroups ? 0 : group + 1;1093}1094 1095/*1096 * ext4_mb_choose_next_group: choose next group for allocation.1097 *1098 * @ac        Allocation Context1099 * @new_cr    This is an output parameter. If the there is no good group1100 *            available at current CR level, this field is updated to indicate1101 *            the new cr level that should be used.1102 * @group     This is an input / output parameter. As an input it indicates the1103 *            next group that the allocator intends to use for allocation. As1104 *            output, this field indicates the next group that should be used as1105 *            determined by the optimization functions.1106 * @ngroups   Total number of groups1107 */1108static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,1109		enum criteria *new_cr, ext4_group_t *group, ext4_group_t ngroups)1110{1111	*new_cr = ac->ac_criteria;1112 1113	if (!should_optimize_scan(ac)) {1114		*group = next_linear_group(*group, ngroups);1115		return;1116	}1117 1118	/*1119	 * Optimized scanning can return non adjacent groups which can cause1120	 * seek overhead for rotational disks. So try few linear groups before1121	 * trying optimized scan.1122	 */1123	if (ac->ac_groups_linear_remaining) {1124		*group = next_linear_group(*group, ngroups);1125		ac->ac_groups_linear_remaining--;1126		return;1127	}1128 1129	if (*new_cr == CR_POWER2_ALIGNED) {1130		ext4_mb_choose_next_group_p2_aligned(ac, new_cr, group);1131	} else if (*new_cr == CR_GOAL_LEN_FAST) {1132		ext4_mb_choose_next_group_goal_fast(ac, new_cr, group);1133	} else if (*new_cr == CR_BEST_AVAIL_LEN) {1134		ext4_mb_choose_next_group_best_avail(ac, new_cr, group);1135	} else {1136		/*1137		 * TODO: For CR_GOAL_LEN_SLOW, we can arrange groups in an1138		 * rb tree sorted by bb_free. But until that happens, we should1139		 * never come here.1140		 */1141		WARN_ON(1);1142	}1143}1144 1145/*1146 * Cache the order of the largest free extent we have available in this block1147 * group.1148 */1149static void1150mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)1151{1152	struct ext4_sb_info *sbi = EXT4_SB(sb);1153	int i;1154 1155	for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--)1156		if (grp->bb_counters[i] > 0)1157			break;1158	/* No need to move between order lists? */1159	if (!test_opt2(sb, MB_OPTIMIZE_SCAN) ||1160	    i == grp->bb_largest_free_order) {1161		grp->bb_largest_free_order = i;1162		return;1163	}1164 1165	if (grp->bb_largest_free_order >= 0) {1166		write_lock(&sbi->s_mb_largest_free_orders_locks[1167					      grp->bb_largest_free_order]);1168		list_del_init(&grp->bb_largest_free_order_node);1169		write_unlock(&sbi->s_mb_largest_free_orders_locks[1170					      grp->bb_largest_free_order]);1171	}1172	grp->bb_largest_free_order = i;1173	if (grp->bb_largest_free_order >= 0 && grp->bb_free) {1174		write_lock(&sbi->s_mb_largest_free_orders_locks[1175					      grp->bb_largest_free_order]);1176		list_add_tail(&grp->bb_largest_free_order_node,1177		      &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);1178		write_unlock(&sbi->s_mb_largest_free_orders_locks[1179					      grp->bb_largest_free_order]);1180	}1181}1182 1183static noinline_for_stack1184void ext4_mb_generate_buddy(struct super_block *sb,1185			    void *buddy, void *bitmap, ext4_group_t group,1186			    struct ext4_group_info *grp)1187{1188	struct ext4_sb_info *sbi = EXT4_SB(sb);1189	ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);1190	ext4_grpblk_t i = 0;1191	ext4_grpblk_t first;1192	ext4_grpblk_t len;1193	unsigned free = 0;1194	unsigned fragments = 0;1195	unsigned long long period = get_cycles();1196 1197	/* initialize buddy from bitmap which is aggregation1198	 * of on-disk bitmap and preallocations */1199	i = mb_find_next_zero_bit(bitmap, max, 0);1200	grp->bb_first_free = i;1201	while (i < max) {1202		fragments++;1203		first = i;1204		i = mb_find_next_bit(bitmap, max, i);1205		len = i - first;1206		free += len;1207		if (len > 1)1208			ext4_mb_mark_free_simple(sb, buddy, first, len, grp);1209		else1210			grp->bb_counters[0]++;1211		if (i < max)1212			i = mb_find_next_zero_bit(bitmap, max, i);1213	}1214	grp->bb_fragments = fragments;1215 1216	if (free != grp->bb_free) {1217		ext4_grp_locked_error(sb, group, 0, 0,1218				      "block bitmap and bg descriptor "1219				      "inconsistent: %u vs %u free clusters",1220				      free, grp->bb_free);1221		/*1222		 * If we intend to continue, we consider group descriptor1223		 * corrupt and update bb_free using bitmap value1224		 */1225		grp->bb_free = free;1226		ext4_mark_group_bitmap_corrupted(sb, group,1227					EXT4_GROUP_INFO_BBITMAP_CORRUPT);1228	}1229	mb_set_largest_free_order(sb, grp);1230	mb_update_avg_fragment_size(sb, grp);1231 1232	clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));1233 1234	period = get_cycles() - period;1235	atomic_inc(&sbi->s_mb_buddies_generated);1236	atomic64_add(period, &sbi->s_mb_generation_time);1237}1238 1239static void mb_regenerate_buddy(struct ext4_buddy *e4b)1240{1241	int count;1242	int order = 1;1243	void *buddy;1244 1245	while ((buddy = mb_find_buddy(e4b, order++, &count)))1246		mb_set_bits(buddy, 0, count);1247 1248	e4b->bd_info->bb_fragments = 0;1249	memset(e4b->bd_info->bb_counters, 0,1250		sizeof(*e4b->bd_info->bb_counters) *1251		(e4b->bd_sb->s_blocksize_bits + 2));1252 1253	ext4_mb_generate_buddy(e4b->bd_sb, e4b->bd_buddy,1254		e4b->bd_bitmap, e4b->bd_group, e4b->bd_info);1255}1256 1257/* The buddy information is attached the buddy cache inode1258 * for convenience. The information regarding each group1259 * is loaded via ext4_mb_load_buddy. The information involve1260 * block bitmap and buddy information. The information are1261 * stored in the inode as1262 *1263 * {                        page                        }1264 * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...1265 *1266 *1267 * one block each for bitmap and buddy information.1268 * So for each group we take up 2 blocks. A page can1269 * contain blocks_per_page (PAGE_SIZE / blocksize)  blocks.1270 * So it can have information regarding groups_per_page which1271 * is blocks_per_page/21272 *1273 * Locking note:  This routine takes the block group lock of all groups1274 * for this page; do not hold this lock when calling this routine!1275 */1276 1277static int ext4_mb_init_cache(struct folio *folio, char *incore, gfp_t gfp)1278{1279	ext4_group_t ngroups;1280	unsigned int blocksize;1281	int blocks_per_page;1282	int groups_per_page;1283	int err = 0;1284	int i;1285	ext4_group_t first_group, group;1286	int first_block;1287	struct super_block *sb;1288	struct buffer_head *bhs;1289	struct buffer_head **bh = NULL;1290	struct inode *inode;1291	char *data;1292	char *bitmap;1293	struct ext4_group_info *grinfo;1294 1295	inode = folio->mapping->host;1296	sb = inode->i_sb;1297	ngroups = ext4_get_groups_count(sb);1298	blocksize = i_blocksize(inode);1299	blocks_per_page = PAGE_SIZE / blocksize;1300 1301	mb_debug(sb, "init folio %lu\n", folio->index);1302 1303	groups_per_page = blocks_per_page >> 1;1304	if (groups_per_page == 0)1305		groups_per_page = 1;1306 1307	/* allocate buffer_heads to read bitmaps */1308	if (groups_per_page > 1) {1309		i = sizeof(struct buffer_head *) * groups_per_page;1310		bh = kzalloc(i, gfp);1311		if (bh == NULL)1312			return -ENOMEM;1313	} else1314		bh = &bhs;1315 1316	first_group = folio->index * blocks_per_page / 2;1317 1318	/* read all groups the folio covers into the cache */1319	for (i = 0, group = first_group; i < groups_per_page; i++, group++) {1320		if (group >= ngroups)1321			break;1322 1323		grinfo = ext4_get_group_info(sb, group);1324		if (!grinfo)1325			continue;1326		/*1327		 * If page is uptodate then we came here after online resize1328		 * which added some new uninitialized group info structs, so1329		 * we must skip all initialized uptodate buddies on the folio,1330		 * which may be currently in use by an allocating task.1331		 */1332		if (folio_test_uptodate(folio) &&1333				!EXT4_MB_GRP_NEED_INIT(grinfo)) {1334			bh[i] = NULL;1335			continue;1336		}1337		bh[i] = ext4_read_block_bitmap_nowait(sb, group, false);1338		if (IS_ERR(bh[i])) {1339			err = PTR_ERR(bh[i]);1340			bh[i] = NULL;1341			goto out;1342		}1343		mb_debug(sb, "read bitmap for group %u\n", group);1344	}1345 1346	/* wait for I/O completion */1347	for (i = 0, group = first_group; i < groups_per_page; i++, group++) {1348		int err2;1349 1350		if (!bh[i])1351			continue;1352		err2 = ext4_wait_block_bitmap(sb, group, bh[i]);1353		if (!err)1354			err = err2;1355	}1356 1357	first_block = folio->index * blocks_per_page;1358	for (i = 0; i < blocks_per_page; i++) {1359		group = (first_block + i) >> 1;1360		if (group >= ngroups)1361			break;1362 1363		if (!bh[group - first_group])1364			/* skip initialized uptodate buddy */1365			continue;1366 1367		if (!buffer_verified(bh[group - first_group]))1368			/* Skip faulty bitmaps */1369			continue;1370		err = 0;1371 1372		/*1373		 * data carry information regarding this1374		 * particular group in the format specified1375		 * above1376		 *1377		 */1378		data = folio_address(folio) + (i * blocksize);1379		bitmap = bh[group - first_group]->b_data;1380 1381		/*1382		 * We place the buddy block and bitmap block1383		 * close together1384		 */1385		grinfo = ext4_get_group_info(sb, group);1386		if (!grinfo) {1387			err = -EFSCORRUPTED;1388		        goto out;1389		}1390		if ((first_block + i) & 1) {1391			/* this is block of buddy */1392			BUG_ON(incore == NULL);1393			mb_debug(sb, "put buddy for group %u in folio %lu/%x\n",1394				group, folio->index, i * blocksize);1395			trace_ext4_mb_buddy_bitmap_load(sb, group);1396			grinfo->bb_fragments = 0;1397			memset(grinfo->bb_counters, 0,1398			       sizeof(*grinfo->bb_counters) *1399			       (MB_NUM_ORDERS(sb)));1400			/*1401			 * incore got set to the group block bitmap below1402			 */1403			ext4_lock_group(sb, group);1404			/* init the buddy */1405			memset(data, 0xff, blocksize);1406			ext4_mb_generate_buddy(sb, data, incore, group, grinfo);1407			ext4_unlock_group(sb, group);1408			incore = NULL;1409		} else {1410			/* this is block of bitmap */1411			BUG_ON(incore != NULL);1412			mb_debug(sb, "put bitmap for group %u in folio %lu/%x\n",1413				group, folio->index, i * blocksize);1414			trace_ext4_mb_bitmap_load(sb, group);1415 1416			/* see comments in ext4_mb_put_pa() */1417			ext4_lock_group(sb, group);1418			memcpy(data, bitmap, blocksize);1419 1420			/* mark all preallocated blks used in in-core bitmap */1421			ext4_mb_generate_from_pa(sb, data, group);1422			WARN_ON_ONCE(!RB_EMPTY_ROOT(&grinfo->bb_free_root));1423			ext4_unlock_group(sb, group);1424 1425			/* set incore so that the buddy information can be1426			 * generated using this1427			 */1428			incore = data;1429		}1430	}1431	folio_mark_uptodate(folio);1432 1433out:1434	if (bh) {1435		for (i = 0; i < groups_per_page; i++)1436			brelse(bh[i]);1437		if (bh != &bhs)1438			kfree(bh);1439	}1440	return err;1441}1442 1443/*1444 * Lock the buddy and bitmap pages. This make sure other parallel init_group1445 * on the same buddy page doesn't happen whild holding the buddy page lock.1446 * Return locked buddy and bitmap pages on e4b struct. If buddy and bitmap1447 * are on the same page e4b->bd_buddy_folio is NULL and return value is 0.1448 */1449static int ext4_mb_get_buddy_page_lock(struct super_block *sb,1450		ext4_group_t group, struct ext4_buddy *e4b, gfp_t gfp)1451{1452	struct inode *inode = EXT4_SB(sb)->s_buddy_cache;1453	int block, pnum, poff;1454	int blocks_per_page;1455	struct folio *folio;1456 1457	e4b->bd_buddy_folio = NULL;1458	e4b->bd_bitmap_folio = NULL;1459 1460	blocks_per_page = PAGE_SIZE / sb->s_blocksize;1461	/*1462	 * the buddy cache inode stores the block bitmap1463	 * and buddy information in consecutive blocks.1464	 * So for each group we need two blocks.1465	 */1466	block = group * 2;1467	pnum = block / blocks_per_page;1468	poff = block % blocks_per_page;1469	folio = __filemap_get_folio(inode->i_mapping, pnum,1470			FGP_LOCK | FGP_ACCESSED | FGP_CREAT, gfp);1471	if (IS_ERR(folio))1472		return PTR_ERR(folio);1473	BUG_ON(folio->mapping != inode->i_mapping);1474	e4b->bd_bitmap_folio = folio;1475	e4b->bd_bitmap = folio_address(folio) + (poff * sb->s_blocksize);1476 1477	if (blocks_per_page >= 2) {1478		/* buddy and bitmap are on the same page */1479		return 0;1480	}1481 1482	/* blocks_per_page == 1, hence we need another page for the buddy */1483	folio = __filemap_get_folio(inode->i_mapping, block + 1,1484			FGP_LOCK | FGP_ACCESSED | FGP_CREAT, gfp);1485	if (IS_ERR(folio))1486		return PTR_ERR(folio);1487	BUG_ON(folio->mapping != inode->i_mapping);1488	e4b->bd_buddy_folio = folio;1489	return 0;1490}1491 1492static void ext4_mb_put_buddy_page_lock(struct ext4_buddy *e4b)1493{1494	if (e4b->bd_bitmap_folio) {1495		folio_unlock(e4b->bd_bitmap_folio);1496		folio_put(e4b->bd_bitmap_folio);1497	}1498	if (e4b->bd_buddy_folio) {1499		folio_unlock(e4b->bd_buddy_folio);1500		folio_put(e4b->bd_buddy_folio);1501	}1502}1503 1504/*1505 * Locking note:  This routine calls ext4_mb_init_cache(), which takes the1506 * block group lock of all groups for this page; do not hold the BG lock when1507 * calling this routine!1508 */1509static noinline_for_stack1510int ext4_mb_init_group(struct super_block *sb, ext4_group_t group, gfp_t gfp)1511{1512 1513	struct ext4_group_info *this_grp;1514	struct ext4_buddy e4b;1515	struct folio *folio;1516	int ret = 0;1517 1518	might_sleep();1519	mb_debug(sb, "init group %u\n", group);1520	this_grp = ext4_get_group_info(sb, group);1521	if (!this_grp)1522		return -EFSCORRUPTED;1523 1524	/*1525	 * This ensures that we don't reinit the buddy cache1526	 * page which map to the group from which we are already1527	 * allocating. If we are looking at the buddy cache we would1528	 * have taken a reference using ext4_mb_load_buddy and that1529	 * would have pinned buddy page to page cache.1530	 * The call to ext4_mb_get_buddy_page_lock will mark the1531	 * page accessed.1532	 */1533	ret = ext4_mb_get_buddy_page_lock(sb, group, &e4b, gfp);1534	if (ret || !EXT4_MB_GRP_NEED_INIT(this_grp)) {1535		/*1536		 * somebody initialized the group1537		 * return without doing anything1538		 */1539		goto err;1540	}1541 1542	folio = e4b.bd_bitmap_folio;1543	ret = ext4_mb_init_cache(folio, NULL, gfp);1544	if (ret)1545		goto err;1546	if (!folio_test_uptodate(folio)) {1547		ret = -EIO;1548		goto err;1549	}1550 1551	if (e4b.bd_buddy_folio == NULL) {1552		/*1553		 * If both the bitmap and buddy are in1554		 * the same page we don't need to force1555		 * init the buddy1556		 */1557		ret = 0;1558		goto err;1559	}1560	/* init buddy cache */1561	folio = e4b.bd_buddy_folio;1562	ret = ext4_mb_init_cache(folio, e4b.bd_bitmap, gfp);1563	if (ret)1564		goto err;1565	if (!folio_test_uptodate(folio)) {1566		ret = -EIO;1567		goto err;1568	}1569err:1570	ext4_mb_put_buddy_page_lock(&e4b);1571	return ret;1572}1573 1574/*1575 * Locking note:  This routine calls ext4_mb_init_cache(), which takes the1576 * block group lock of all groups for this page; do not hold the BG lock when1577 * calling this routine!1578 */1579static noinline_for_stack int1580ext4_mb_load_buddy_gfp(struct super_block *sb, ext4_group_t group,1581		       struct ext4_buddy *e4b, gfp_t gfp)1582{1583	int blocks_per_page;1584	int block;1585	int pnum;1586	int poff;1587	struct folio *folio;1588	int ret;1589	struct ext4_group_info *grp;1590	struct ext4_sb_info *sbi = EXT4_SB(sb);1591	struct inode *inode = sbi->s_buddy_cache;1592 1593	might_sleep();1594	mb_debug(sb, "load group %u\n", group);1595 1596	blocks_per_page = PAGE_SIZE / sb->s_blocksize;1597	grp = ext4_get_group_info(sb, group);1598	if (!grp)1599		return -EFSCORRUPTED;1600 1601	e4b->bd_blkbits = sb->s_blocksize_bits;1602	e4b->bd_info = grp;1603	e4b->bd_sb = sb;1604	e4b->bd_group = group;1605	e4b->bd_buddy_folio = NULL;1606	e4b->bd_bitmap_folio = NULL;1607 1608	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {1609		/*1610		 * we need full data about the group1611		 * to make a good selection1612		 */1613		ret = ext4_mb_init_group(sb, group, gfp);1614		if (ret)1615			return ret;1616	}1617 1618	/*1619	 * the buddy cache inode stores the block bitmap1620	 * and buddy information in consecutive blocks.1621	 * So for each group we need two blocks.1622	 */1623	block = group * 2;1624	pnum = block / blocks_per_page;1625	poff = block % blocks_per_page;1626 1627	/* Avoid locking the folio in the fast path ... */1628	folio = __filemap_get_folio(inode->i_mapping, pnum, FGP_ACCESSED, 0);1629	if (IS_ERR(folio) || !folio_test_uptodate(folio)) {1630		if (!IS_ERR(folio))1631			/*1632			 * drop the folio reference and try1633			 * to get the folio with lock. If we1634			 * are not uptodate that implies1635			 * somebody just created the folio but1636			 * is yet to initialize it. So1637			 * wait for it to initialize.1638			 */1639			folio_put(folio);1640		folio = __filemap_get_folio(inode->i_mapping, pnum,1641				FGP_LOCK | FGP_ACCESSED | FGP_CREAT, gfp);1642		if (!IS_ERR(folio)) {1643			if (WARN_RATELIMIT(folio->mapping != inode->i_mapping,1644	"ext4: bitmap's mapping != inode->i_mapping\n")) {1645				/* should never happen */1646				folio_unlock(folio);1647				ret = -EINVAL;1648				goto err;1649			}1650			if (!folio_test_uptodate(folio)) {1651				ret = ext4_mb_init_cache(folio, NULL, gfp);1652				if (ret) {1653					folio_unlock(folio);1654					goto err;1655				}1656				mb_cmp_bitmaps(e4b, folio_address(folio) +1657					       (poff * sb->s_blocksize));1658			}1659			folio_unlock(folio);1660		}1661	}1662	if (IS_ERR(folio)) {1663		ret = PTR_ERR(folio);1664		goto err;1665	}1666	if (!folio_test_uptodate(folio)) {1667		ret = -EIO;1668		goto err;1669	}1670 1671	/* Folios marked accessed already */1672	e4b->bd_bitmap_folio = folio;1673	e4b->bd_bitmap = folio_address(folio) + (poff * sb->s_blocksize);1674 1675	block++;1676	pnum = block / blocks_per_page;1677	poff = block % blocks_per_page;1678 1679	folio = __filemap_get_folio(inode->i_mapping, pnum, FGP_ACCESSED, 0);1680	if (IS_ERR(folio) || !folio_test_uptodate(folio)) {1681		if (!IS_ERR(folio))1682			folio_put(folio);1683		folio = __filemap_get_folio(inode->i_mapping, pnum,1684				FGP_LOCK | FGP_ACCESSED | FGP_CREAT, gfp);1685		if (!IS_ERR(folio)) {1686			if (WARN_RATELIMIT(folio->mapping != inode->i_mapping,1687	"ext4: buddy bitmap's mapping != inode->i_mapping\n")) {1688				/* should never happen */1689				folio_unlock(folio);1690				ret = -EINVAL;1691				goto err;1692			}1693			if (!folio_test_uptodate(folio)) {1694				ret = ext4_mb_init_cache(folio, e4b->bd_bitmap,1695							 gfp);1696				if (ret) {1697					folio_unlock(folio);1698					goto err;1699				}1700			}1701			folio_unlock(folio);1702		}1703	}1704	if (IS_ERR(folio)) {1705		ret = PTR_ERR(folio);1706		goto err;1707	}1708	if (!folio_test_uptodate(folio)) {1709		ret = -EIO;1710		goto err;1711	}1712 1713	/* Folios marked accessed already */1714	e4b->bd_buddy_folio = folio;1715	e4b->bd_buddy = folio_address(folio) + (poff * sb->s_blocksize);1716 1717	return 0;1718 1719err:1720	if (!IS_ERR_OR_NULL(folio))1721		folio_put(folio);1722	if (e4b->bd_bitmap_folio)1723		folio_put(e4b->bd_bitmap_folio);1724 1725	e4b->bd_buddy = NULL;1726	e4b->bd_bitmap = NULL;1727	return ret;1728}1729 1730static int ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,1731			      struct ext4_buddy *e4b)1732{1733	return ext4_mb_load_buddy_gfp(sb, group, e4b, GFP_NOFS);1734}1735 1736static void ext4_mb_unload_buddy(struct ext4_buddy *e4b)1737{1738	if (e4b->bd_bitmap_folio)1739		folio_put(e4b->bd_bitmap_folio);1740	if (e4b->bd_buddy_folio)1741		folio_put(e4b->bd_buddy_folio);1742}1743 1744 1745static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)1746{1747	int order = 1, max;1748	void *bb;1749 1750	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);1751	BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));1752 1753	while (order <= e4b->bd_blkbits + 1) {1754		bb = mb_find_buddy(e4b, order, &max);1755		if (!mb_test_bit(block >> order, bb)) {1756			/* this block is part of buddy of order 'order' */1757			return order;1758		}1759		order++;1760	}1761	return 0;1762}1763 1764static void mb_clear_bits(void *bm, int cur, int len)1765{1766	__u32 *addr;1767 1768	len = cur + len;1769	while (cur < len) {1770		if ((cur & 31) == 0 && (len - cur) >= 32) {1771			/* fast path: clear whole word at once */1772			addr = bm + (cur >> 3);1773			*addr = 0;1774			cur += 32;1775			continue;1776		}1777		mb_clear_bit(cur, bm);1778		cur++;1779	}1780}1781 1782/* clear bits in given range1783 * will return first found zero bit if any, -1 otherwise1784 */1785static int mb_test_and_clear_bits(void *bm, int cur, int len)1786{1787	__u32 *addr;1788	int zero_bit = -1;1789 1790	len = cur + len;1791	while (cur < len) {1792		if ((cur & 31) == 0 && (len - cur) >= 32) {1793			/* fast path: clear whole word at once */1794			addr = bm + (cur >> 3);1795			if (*addr != (__u32)(-1) && zero_bit == -1)1796				zero_bit = cur + mb_find_next_zero_bit(addr, 32, 0);1797			*addr = 0;1798			cur += 32;1799			continue;1800		}1801		if (!mb_test_and_clear_bit(cur, bm) && zero_bit == -1)1802			zero_bit = cur;1803		cur++;1804	}1805 1806	return zero_bit;1807}1808 1809void mb_set_bits(void *bm, int cur, int len)1810{1811	__u32 *addr;1812 1813	len = cur + len;1814	while (cur < len) {1815		if ((cur & 31) == 0 && (len - cur) >= 32) {1816			/* fast path: set whole word at once */1817			addr = bm + (cur >> 3);1818			*addr = 0xffffffff;1819			cur += 32;1820			continue;1821		}1822		mb_set_bit(cur, bm);1823		cur++;1824	}1825}1826 1827static inline int mb_buddy_adjust_border(int* bit, void* bitmap, int side)1828{1829	if (mb_test_bit(*bit + side, bitmap)) {1830		mb_clear_bit(*bit, bitmap);1831		(*bit) -= side;1832		return 1;1833	}1834	else {1835		(*bit) += side;1836		mb_set_bit(*bit, bitmap);1837		return -1;1838	}1839}1840 1841static void mb_buddy_mark_free(struct ext4_buddy *e4b, int first, int last)1842{1843	int max;1844	int order = 1;1845	void *buddy = mb_find_buddy(e4b, order, &max);1846 1847	while (buddy) {1848		void *buddy2;1849 1850		/* Bits in range [first; last] are known to be set since1851		 * corresponding blocks were allocated. Bits in range1852		 * (first; last) will stay set because they form buddies on1853		 * upper layer. We just deal with borders if they don't1854		 * align with upper layer and then go up.1855		 * Releasing entire group is all about clearing1856		 * single bit of highest order buddy.1857		 */1858 1859		/* Example:1860		 * ---------------------------------1861		 * |   1   |   1   |   1   |   1   |1862		 * ---------------------------------1863		 * | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |1864		 * ---------------------------------1865		 *   0   1   2   3   4   5   6   71866		 *      \_____________________/1867		 *1868		 * Neither [1] nor [6] is aligned to above layer.1869		 * Left neighbour [0] is free, so mark it busy,1870		 * decrease bb_counters and extend range to1871		 * [0; 6]1872		 * Right neighbour [7] is busy. It can't be coaleasced with [6], so1873		 * mark [6] free, increase bb_counters and shrink range to1874		 * [0; 5].1875		 * Then shift range to [0; 2], go up and do the same.1876		 */1877 1878 1879		if (first & 1)1880			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&first, buddy, -1);1881		if (!(last & 1))1882			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&last, buddy, 1);1883		if (first > last)1884			break;1885		order++;1886 1887		buddy2 = mb_find_buddy(e4b, order, &max);1888		if (!buddy2) {1889			mb_clear_bits(buddy, first, last - first + 1);1890			e4b->bd_info->bb_counters[order - 1] += last - first + 1;1891			break;1892		}1893		first >>= 1;1894		last >>= 1;1895		buddy = buddy2;1896	}1897}1898 1899static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,1900			   int first, int count)1901{1902	int left_is_free = 0;1903	int right_is_free = 0;1904	int block;1905	int last = first + count - 1;1906	struct super_block *sb = e4b->bd_sb;1907 1908	if (WARN_ON(count == 0))1909		return;1910	BUG_ON(last >= (sb->s_blocksize << 3));1911	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));1912	/* Don't bother if the block group is corrupt. */1913	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))1914		return;1915 1916	mb_check_buddy(e4b);1917	mb_free_blocks_double(inode, e4b, first, count);1918 1919	/* access memory sequentially: check left neighbour,1920	 * clear range and then check right neighbour1921	 */1922	if (first != 0)1923		left_is_free = !mb_test_bit(first - 1, e4b->bd_bitmap);1924	block = mb_test_and_clear_bits(e4b->bd_bitmap, first, count);1925	if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])1926		right_is_free = !mb_test_bit(last + 1, e4b->bd_bitmap);1927 1928	if (unlikely(block != -1)) {1929		struct ext4_sb_info *sbi = EXT4_SB(sb);1930		ext4_fsblk_t blocknr;1931 1932		/*1933		 * Fastcommit replay can free already freed blocks which1934		 * corrupts allocation info. Regenerate it.1935		 */1936		if (sbi->s_mount_state & EXT4_FC_REPLAY) {1937			mb_regenerate_buddy(e4b);1938			goto check;1939		}1940 1941		blocknr = ext4_group_first_block_no(sb, e4b->bd_group);1942		blocknr += EXT4_C2B(sbi, block);1943		ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,1944				EXT4_GROUP_INFO_BBITMAP_CORRUPT);1945		ext4_grp_locked_error(sb, e4b->bd_group,1946				      inode ? inode->i_ino : 0, blocknr,1947				      "freeing already freed block (bit %u); block bitmap corrupt.",1948				      block);1949		return;1950	}1951 1952	this_cpu_inc(discard_pa_seq);1953	e4b->bd_info->bb_free += count;1954	if (first < e4b->bd_info->bb_first_free)1955		e4b->bd_info->bb_first_free = first;1956 1957	/* let's maintain fragments counter */1958	if (left_is_free && right_is_free)1959		e4b->bd_info->bb_fragments--;1960	else if (!left_is_free && !right_is_free)1961		e4b->bd_info->bb_fragments++;1962 1963	/* buddy[0] == bd_bitmap is a special case, so handle1964	 * it right away and let mb_buddy_mark_free stay free of1965	 * zero order checks.1966	 * Check if neighbours are to be coaleasced,1967	 * adjust bitmap bb_counters and borders appropriately.1968	 */1969	if (first & 1) {1970		first += !left_is_free;1971		e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;1972	}1973	if (!(last & 1)) {1974		last -= !right_is_free;1975		e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;1976	}1977 1978	if (first <= last)1979		mb_buddy_mark_free(e4b, first >> 1, last >> 1);1980 1981	mb_set_largest_free_order(sb, e4b->bd_info);1982	mb_update_avg_fragment_size(sb, e4b->bd_info);1983check:1984	mb_check_buddy(e4b);1985}1986 1987static int mb_find_extent(struct ext4_buddy *e4b, int block,1988				int needed, struct ext4_free_extent *ex)1989{1990	int max, order, next;1991	void *buddy;1992 1993	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));1994	BUG_ON(ex == NULL);1995 1996	buddy = mb_find_buddy(e4b, 0, &max);1997	BUG_ON(buddy == NULL);1998	BUG_ON(block >= max);1999	if (mb_test_bit(block, buddy)) {2000		ex->fe_len = 0;2001		ex->fe_start = 0;2002		ex->fe_group = 0;2003		return 0;2004	}2005 2006	/* find actual order */2007	order = mb_find_order_for_block(e4b, block);2008 2009	ex->fe_len = (1 << order) - (block & ((1 << order) - 1));2010	ex->fe_start = block;2011	ex->fe_group = e4b->bd_group;2012 2013	block = block >> order;2014 2015	while (needed > ex->fe_len &&2016	       mb_find_buddy(e4b, order, &max)) {2017 2018		if (block + 1 >= max)2019			break;2020 2021		next = (block + 1) * (1 << order);2022		if (mb_test_bit(next, e4b->bd_bitmap))2023			break;2024 2025		order = mb_find_order_for_block(e4b, next);2026 2027		block = next >> order;2028		ex->fe_len += 1 << order;2029	}2030 2031	if (ex->fe_start + ex->fe_len > EXT4_CLUSTERS_PER_GROUP(e4b->bd_sb)) {2032		/* Should never happen! (but apparently sometimes does?!?) */2033		WARN_ON(1);2034		ext4_grp_locked_error(e4b->bd_sb, e4b->bd_group, 0, 0,2035			"corruption or bug in mb_find_extent "2036			"block=%d, order=%d needed=%d ex=%u/%d/%d@%u",2037			block, order, needed, ex->fe_group, ex->fe_start,2038			ex->fe_len, ex->fe_logical);2039		ex->fe_len = 0;2040		ex->fe_start = 0;2041		ex->fe_group = 0;2042	}2043	return ex->fe_len;2044}2045 2046static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)2047{2048	int ord;2049	int mlen = 0;2050	int max = 0;2051	int start = ex->fe_start;2052	int len = ex->fe_len;2053	unsigned ret = 0;2054	int len0 = len;2055	void *buddy;2056	int ord_start, ord_end;2057 2058	BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));2059	BUG_ON(e4b->bd_group != ex->fe_group);2060	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));2061	mb_check_buddy(e4b);2062	mb_mark_used_double(e4b, start, len);2063 2064	this_cpu_inc(discard_pa_seq);2065	e4b->bd_info->bb_free -= len;2066	if (e4b->bd_info->bb_first_free == start)2067		e4b->bd_info->bb_first_free += len;2068 2069	/* let's maintain fragments counter */2070	if (start != 0)2071		mlen = !mb_test_bit(start - 1, e4b->bd_bitmap);2072	if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])2073		max = !mb_test_bit(start + len, e4b->bd_bitmap);2074	if (mlen && max)2075		e4b->bd_info->bb_fragments++;2076	else if (!mlen && !max)2077		e4b->bd_info->bb_fragments--;2078 2079	/* let's maintain buddy itself */2080	while (len) {2081		ord = mb_find_order_for_block(e4b, start);2082 2083		if (((start >> ord) << ord) == start && len >= (1 << ord)) {2084			/* the whole chunk may be allocated at once! */2085			mlen = 1 << ord;2086			buddy = mb_find_buddy(e4b, ord, &max);2087			BUG_ON((start >> ord) >= max);2088			mb_set_bit(start >> ord, buddy);2089			e4b->bd_info->bb_counters[ord]--;2090			start += mlen;2091			len -= mlen;2092			BUG_ON(len < 0);2093			continue;2094		}2095 2096		/* store for history */2097		if (ret == 0)2098			ret = len | (ord << 16);2099 2100		BUG_ON(ord <= 0);2101		buddy = mb_find_buddy(e4b, ord, &max);2102		mb_set_bit(start >> ord, buddy);2103		e4b->bd_info->bb_counters[ord]--;2104 2105		ord_start = (start >> ord) << ord;2106		ord_end = ord_start + (1 << ord);2107		/* first chunk */2108		if (start > ord_start)2109			ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,2110						 ord_start, start - ord_start,2111						 e4b->bd_info);2112 2113		/* last chunk */2114		if (start + len < ord_end) {2115			ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,2116						 start + len,2117						 ord_end - (start + len),2118						 e4b->bd_info);2119			break;2120		}2121		len = start + len - ord_end;2122		start = ord_end;2123	}2124	mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);2125 2126	mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);2127	mb_set_bits(e4b->bd_bitmap, ex->fe_start, len0);2128	mb_check_buddy(e4b);2129 2130	return ret;2131}2132 2133/*2134 * Must be called under group lock!2135 */2136static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,2137					struct ext4_buddy *e4b)2138{2139	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);2140	int ret;2141 2142	BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);2143	BUG_ON(ac->ac_status == AC_STATUS_FOUND);2144 2145	ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);2146	ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;2147	ret = mb_mark_used(e4b, &ac->ac_b_ex);2148 2149	/* preallocation can change ac_b_ex, thus we store actually2150	 * allocated blocks for history */2151	ac->ac_f_ex = ac->ac_b_ex;2152 2153	ac->ac_status = AC_STATUS_FOUND;2154	ac->ac_tail = ret & 0xffff;2155	ac->ac_buddy = ret >> 16;2156 2157	/*2158	 * take the page reference. We want the page to be pinned2159	 * so that we don't get a ext4_mb_init_cache_call for this2160	 * group until we update the bitmap. That would mean we2161	 * double allocate blocks. The reference is dropped2162	 * in ext4_mb_release_context2163	 */2164	ac->ac_bitmap_folio = e4b->bd_bitmap_folio;2165	folio_get(ac->ac_bitmap_folio);2166	ac->ac_buddy_folio = e4b->bd_buddy_folio;2167	folio_get(ac->ac_buddy_folio);2168	/* store last allocated for subsequent stream allocation */2169	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {2170		spin_lock(&sbi->s_md_lock);2171		sbi->s_mb_last_group = ac->ac_f_ex.fe_group;2172		sbi->s_mb_last_start = ac->ac_f_ex.fe_start;2173		spin_unlock(&sbi->s_md_lock);2174	}2175	/*2176	 * As we've just preallocated more space than2177	 * user requested originally, we store allocated2178	 * space in a special descriptor.2179	 */2180	if (ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)2181		ext4_mb_new_preallocation(ac);2182 2183}2184 2185static void ext4_mb_check_limits(struct ext4_allocation_context *ac,2186					struct ext4_buddy *e4b,2187					int finish_group)2188{2189	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);2190	struct ext4_free_extent *bex = &ac->ac_b_ex;2191	struct ext4_free_extent *gex = &ac->ac_g_ex;2192 2193	if (ac->ac_status == AC_STATUS_FOUND)2194		return;2195	/*2196	 * We don't want to scan for a whole year2197	 */2198	if (ac->ac_found > sbi->s_mb_max_to_scan &&2199			!(ac->ac_flags & EXT4_MB_HINT_FIRST)) {2200		ac->ac_status = AC_STATUS_BREAK;2201		return;2202	}2203 2204	/*2205	 * Haven't found good chunk so far, let's continue2206	 */2207	if (bex->fe_len < gex->fe_len)2208		return;2209 2210	if (finish_group || ac->ac_found > sbi->s_mb_min_to_scan)2211		ext4_mb_use_best_found(ac, e4b);2212}2213 2214/*2215 * The routine checks whether found extent is good enough. If it is,2216 * then the extent gets marked used and flag is set to the context2217 * to stop scanning. Otherwise, the extent is compared with the2218 * previous found extent and if new one is better, then it's stored2219 * in the context. Later, the best found extent will be used, if2220 * mballoc can't find good enough extent.2221 *2222 * The algorithm used is roughly as follows:2223 *2224 * * If free extent found is exactly as big as goal, then2225 *   stop the scan and use it immediately2226 *2227 * * If free extent found is smaller than goal, then keep retrying2228 *   upto a max of sbi->s_mb_max_to_scan times (default 200). After2229 *   that stop scanning and use whatever we have.2230 *2231 * * If free extent found is bigger than goal, then keep retrying2232 *   upto a max of sbi->s_mb_min_to_scan times (default 10) before2233 *   stopping the scan and using the extent.2234 *2235 *2236 * FIXME: real allocation policy is to be designed yet!2237 */2238static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,2239					struct ext4_free_extent *ex,2240					struct ext4_buddy *e4b)2241{2242	struct ext4_free_extent *bex = &ac->ac_b_ex;2243	struct ext4_free_extent *gex = &ac->ac_g_ex;2244 2245	BUG_ON(ex->fe_len <= 0);2246	BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));2247	BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));2248	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);2249 2250	ac->ac_found++;2251	ac->ac_cX_found[ac->ac_criteria]++;2252 2253	/*2254	 * The special case - take what you catch first2255	 */2256	if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {2257		*bex = *ex;2258		ext4_mb_use_best_found(ac, e4b);2259		return;2260	}2261 2262	/*2263	 * Let's check whether the chuck is good enough2264	 */2265	if (ex->fe_len == gex->fe_len) {2266		*bex = *ex;2267		ext4_mb_use_best_found(ac, e4b);2268		return;2269	}2270 2271	/*2272	 * If this is first found extent, just store it in the context2273	 */2274	if (bex->fe_len == 0) {2275		*bex = *ex;2276		return;2277	}2278 2279	/*2280	 * If new found extent is better, store it in the context2281	 */2282	if (bex->fe_len < gex->fe_len) {2283		/* if the request isn't satisfied, any found extent2284		 * larger than previous best one is better */2285		if (ex->fe_len > bex->fe_len)2286			*bex = *ex;2287	} else if (ex->fe_len > gex->fe_len) {2288		/* if the request is satisfied, then we try to find2289		 * an extent that still satisfy the request, but is2290		 * smaller than previous one */2291		if (ex->fe_len < bex->fe_len)2292			*bex = *ex;2293	}2294 2295	ext4_mb_check_limits(ac, e4b, 0);2296}2297 2298static noinline_for_stack2299void ext4_mb_try_best_found(struct ext4_allocation_context *ac,2300					struct ext4_buddy *e4b)2301{2302	struct ext4_free_extent ex = ac->ac_b_ex;2303	ext4_group_t group = ex.fe_group;2304	int max;2305	int err;2306 2307	BUG_ON(ex.fe_len <= 0);2308	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);2309	if (err)2310		return;2311 2312	ext4_lock_group(ac->ac_sb, group);2313	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))2314		goto out;2315 2316	max = mb_find_extent(e4b, ex.fe_start, ex.fe_len, &ex);2317 2318	if (max > 0) {2319		ac->ac_b_ex = ex;2320		ext4_mb_use_best_found(ac, e4b);2321	}2322 2323out:2324	ext4_unlock_group(ac->ac_sb, group);2325	ext4_mb_unload_buddy(e4b);2326}2327 2328static noinline_for_stack2329int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,2330				struct ext4_buddy *e4b)2331{2332	ext4_group_t group = ac->ac_g_ex.fe_group;2333	int max;2334	int err;2335	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);2336	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);2337	struct ext4_free_extent ex;2338 2339	if (!grp)2340		return -EFSCORRUPTED;2341	if (!(ac->ac_flags & (EXT4_MB_HINT_TRY_GOAL | EXT4_MB_HINT_GOAL_ONLY)))2342		return 0;2343	if (grp->bb_free == 0)2344		return 0;2345 2346	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);2347	if (err)2348		return err;2349 2350	ext4_lock_group(ac->ac_sb, group);2351	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))2352		goto out;2353 2354	max = mb_find_extent(e4b, ac->ac_g_ex.fe_start,2355			     ac->ac_g_ex.fe_len, &ex);2356	ex.fe_logical = 0xDEADFA11; /* debug value */2357 2358	if (max >= ac->ac_g_ex.fe_len &&2359	    ac->ac_g_ex.fe_len == EXT4_NUM_B2C(sbi, sbi->s_stripe)) {2360		ext4_fsblk_t start;2361 2362		start = ext4_grp_offs_to_block(ac->ac_sb, &ex);2363		/* use do_div to get remainder (would be 64-bit modulo) */2364		if (do_div(start, sbi->s_stripe) == 0) {2365			ac->ac_found++;2366			ac->ac_b_ex = ex;2367			ext4_mb_use_best_found(ac, e4b);2368		}2369	} else if (max >= ac->ac_g_ex.fe_len) {2370		BUG_ON(ex.fe_len <= 0);2371		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);2372		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);2373		ac->ac_found++;2374		ac->ac_b_ex = ex;2375		ext4_mb_use_best_found(ac, e4b);2376	} else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {2377		/* Sometimes, caller may want to merge even small2378		 * number of blocks to an existing extent */2379		BUG_ON(ex.fe_len <= 0);2380		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);2381		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);2382		ac->ac_found++;2383		ac->ac_b_ex = ex;2384		ext4_mb_use_best_found(ac, e4b);2385	}2386out:2387	ext4_unlock_group(ac->ac_sb, group);2388	ext4_mb_unload_buddy(e4b);2389 2390	return 0;2391}2392 2393/*2394 * The routine scans buddy structures (not bitmap!) from given order2395 * to max order and tries to find big enough chunk to satisfy the req2396 */2397static noinline_for_stack2398void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,2399					struct ext4_buddy *e4b)2400{2401	struct super_block *sb = ac->ac_sb;2402	struct ext4_group_info *grp = e4b->bd_info;2403	void *buddy;2404	int i;2405	int k;2406	int max;2407 2408	BUG_ON(ac->ac_2order <= 0);2409	for (i = ac->ac_2order; i < MB_NUM_ORDERS(sb); i++) {2410		if (grp->bb_counters[i] == 0)2411			continue;2412 2413		buddy = mb_find_buddy(e4b, i, &max);2414		if (WARN_RATELIMIT(buddy == NULL,2415			 "ext4: mb_simple_scan_group: mb_find_buddy failed, (%d)\n", i))2416			continue;2417 2418		k = mb_find_next_zero_bit(buddy, max, 0);2419		if (k >= max) {2420			ext4_mark_group_bitmap_corrupted(ac->ac_sb,2421					e4b->bd_group,2422					EXT4_GROUP_INFO_BBITMAP_CORRUPT);2423			ext4_grp_locked_error(ac->ac_sb, e4b->bd_group, 0, 0,2424				"%d free clusters of order %d. But found 0",2425				grp->bb_counters[i], i);2426			break;2427		}2428		ac->ac_found++;2429		ac->ac_cX_found[ac->ac_criteria]++;2430 2431		ac->ac_b_ex.fe_len = 1 << i;2432		ac->ac_b_ex.fe_start = k << i;2433		ac->ac_b_ex.fe_group = e4b->bd_group;2434 2435		ext4_mb_use_best_found(ac, e4b);2436 2437		BUG_ON(ac->ac_f_ex.fe_len != ac->ac_g_ex.fe_len);2438 2439		if (EXT4_SB(sb)->s_mb_stats)2440			atomic_inc(&EXT4_SB(sb)->s_bal_2orders);2441 2442		break;2443	}2444}2445 2446/*2447 * The routine scans the group and measures all found extents.2448 * In order to optimize scanning, caller must pass number of2449 * free blocks in the group, so the routine can know upper limit.2450 */2451static noinline_for_stack2452void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,2453					struct ext4_buddy *e4b)2454{2455	struct super_block *sb = ac->ac_sb;2456	void *bitmap = e4b->bd_bitmap;2457	struct ext4_free_extent ex;2458	int i, j, freelen;2459	int free;2460 2461	free = e4b->bd_info->bb_free;2462	if (WARN_ON(free <= 0))2463		return;2464 2465	i = e4b->bd_info->bb_first_free;2466 2467	while (free && ac->ac_status == AC_STATUS_CONTINUE) {2468		i = mb_find_next_zero_bit(bitmap,2469						EXT4_CLUSTERS_PER_GROUP(sb), i);2470		if (i >= EXT4_CLUSTERS_PER_GROUP(sb)) {2471			/*2472			 * IF we have corrupt bitmap, we won't find any2473			 * free blocks even though group info says we2474			 * have free blocks2475			 */2476			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,2477					EXT4_GROUP_INFO_BBITMAP_CORRUPT);2478			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,2479					"%d free clusters as per "2480					"group info. But bitmap says 0",2481					free);2482			break;2483		}2484 2485		if (!ext4_mb_cr_expensive(ac->ac_criteria)) {2486			/*2487			 * In CR_GOAL_LEN_FAST and CR_BEST_AVAIL_LEN, we are2488			 * sure that this group will have a large enough2489			 * continuous free extent, so skip over the smaller free2490			 * extents2491			 */2492			j = mb_find_next_bit(bitmap,2493						EXT4_CLUSTERS_PER_GROUP(sb), i);2494			freelen = j - i;2495 2496			if (freelen < ac->ac_g_ex.fe_len) {2497				i = j;2498				free -= freelen;2499				continue;2500			}2501		}2502 2503		mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);2504		if (WARN_ON(ex.fe_len <= 0))2505			break;2506		if (free < ex.fe_len) {2507			ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,2508					EXT4_GROUP_INFO_BBITMAP_CORRUPT);2509			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,2510					"%d free clusters as per "2511					"group info. But got %d blocks",2512					free, ex.fe_len);2513			/*2514			 * The number of free blocks differs. This mostly2515			 * indicate that the bitmap is corrupt. So exit2516			 * without claiming the space.2517			 */2518			break;2519		}2520		ex.fe_logical = 0xDEADC0DE; /* debug value */2521		ext4_mb_measure_extent(ac, &ex, e4b);2522 2523		i += ex.fe_len;2524		free -= ex.fe_len;2525	}2526 2527	ext4_mb_check_limits(ac, e4b, 1);2528}2529 2530/*2531 * This is a special case for storages like raid52532 * we try to find stripe-aligned chunks for stripe-size-multiple requests2533 */2534static noinline_for_stack2535void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,2536				 struct ext4_buddy *e4b)2537{2538	struct super_block *sb = ac->ac_sb;2539	struct ext4_sb_info *sbi = EXT4_SB(sb);2540	void *bitmap = e4b->bd_bitmap;2541	struct ext4_free_extent ex;2542	ext4_fsblk_t first_group_block;2543	ext4_fsblk_t a;2544	ext4_grpblk_t i, stripe;2545	int max;2546 2547	BUG_ON(sbi->s_stripe == 0);2548 2549	/* find first stripe-aligned block in group */2550	first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);2551 2552	a = first_group_block + sbi->s_stripe - 1;2553	do_div(a, sbi->s_stripe);2554	i = (a * sbi->s_stripe) - first_group_block;2555 2556	stripe = EXT4_NUM_B2C(sbi, sbi->s_stripe);2557	i = EXT4_B2C(sbi, i);2558	while (i < EXT4_CLUSTERS_PER_GROUP(sb)) {2559		if (!mb_test_bit(i, bitmap)) {2560			max = mb_find_extent(e4b, i, stripe, &ex);2561			if (max >= stripe) {2562				ac->ac_found++;2563				ac->ac_cX_found[ac->ac_criteria]++;2564				ex.fe_logical = 0xDEADF00D; /* debug value */2565				ac->ac_b_ex = ex;2566				ext4_mb_use_best_found(ac, e4b);2567				break;2568			}2569		}2570		i += stripe;2571	}2572}2573 2574/*2575 * This is also called BEFORE we load the buddy bitmap.2576 * Returns either 1 or 0 indicating that the group is either suitable2577 * for the allocation or not.2578 */2579static bool ext4_mb_good_group(struct ext4_allocation_context *ac,2580				ext4_group_t group, enum criteria cr)2581{2582	ext4_grpblk_t free, fragments;2583	int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));2584	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);2585 2586	BUG_ON(cr < CR_POWER2_ALIGNED || cr >= EXT4_MB_NUM_CRS);2587 2588	if (unlikely(!grp || EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))2589		return false;2590 2591	free = grp->bb_free;2592	if (free == 0)2593		return false;2594 2595	fragments = grp->bb_fragments;2596	if (fragments == 0)2597		return false;2598 2599	switch (cr) {2600	case CR_POWER2_ALIGNED:2601		BUG_ON(ac->ac_2order == 0);2602 2603		/* Avoid using the first bg of a flexgroup for data files */2604		if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&2605		    (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) &&2606		    ((group % flex_size) == 0))2607			return false;2608 2609		if (free < ac->ac_g_ex.fe_len)2610			return false;2611 2612		if (ac->ac_2order >= MB_NUM_ORDERS(ac->ac_sb))2613			return true;2614 2615		if (grp->bb_largest_free_order < ac->ac_2order)2616			return false;2617 2618		return true;2619	case CR_GOAL_LEN_FAST:2620	case CR_BEST_AVAIL_LEN:2621		if ((free / fragments) >= ac->ac_g_ex.fe_len)2622			return true;2623		break;2624	case CR_GOAL_LEN_SLOW:2625		if (free >= ac->ac_g_ex.fe_len)2626			return true;2627		break;2628	case CR_ANY_FREE:2629		return true;2630	default:2631		BUG();2632	}2633 2634	return false;2635}2636 2637/*2638 * This could return negative error code if something goes wrong2639 * during ext4_mb_init_group(). This should not be called with2640 * ext4_lock_group() held.2641 *2642 * Note: because we are conditionally operating with the group lock in2643 * the EXT4_MB_STRICT_CHECK case, we need to fake out sparse in this2644 * function using __acquire and __release.  This means we need to be2645 * super careful before messing with the error path handling via "goto2646 * out"!2647 */2648static int ext4_mb_good_group_nolock(struct ext4_allocation_context *ac,2649				     ext4_group_t group, enum criteria cr)2650{2651	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);2652	struct super_block *sb = ac->ac_sb;2653	struct ext4_sb_info *sbi = EXT4_SB(sb);2654	bool should_lock = ac->ac_flags & EXT4_MB_STRICT_CHECK;2655	ext4_grpblk_t free;2656	int ret = 0;2657 2658	if (!grp)2659		return -EFSCORRUPTED;2660	if (sbi->s_mb_stats)2661		atomic64_inc(&sbi->s_bal_cX_groups_considered[ac->ac_criteria]);2662	if (should_lock) {2663		ext4_lock_group(sb, group);2664		__release(ext4_group_lock_ptr(sb, group));2665	}2666	free = grp->bb_free;2667	if (free == 0)2668		goto out;2669	/*2670	 * In all criterias except CR_ANY_FREE we try to avoid groups that2671	 * can't possibly satisfy the full goal request due to insufficient2672	 * free blocks.2673	 */2674	if (cr < CR_ANY_FREE && free < ac->ac_g_ex.fe_len)2675		goto out;2676	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))2677		goto out;2678	if (should_lock) {2679		__acquire(ext4_group_lock_ptr(sb, group));2680		ext4_unlock_group(sb, group);2681	}2682 2683	/* We only do this if the grp has never been initialized */2684	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {2685		struct ext4_group_desc *gdp =2686			ext4_get_group_desc(sb, group, NULL);2687		int ret;2688 2689		/*2690		 * CR_POWER2_ALIGNED/CR_GOAL_LEN_FAST is a very optimistic2691		 * search to find large good chunks almost for free. If buddy2692		 * data is not ready, then this optimization makes no sense. But2693		 * we never skip the first block group in a flex_bg, since this2694		 * gets used for metadata block allocation, and we want to make2695		 * sure we locate metadata blocks in the first block group in2696		 * the flex_bg if possible.2697		 */2698		if (!ext4_mb_cr_expensive(cr) &&2699		    (!sbi->s_log_groups_per_flex ||2700		     ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &&2701		    !(ext4_has_group_desc_csum(sb) &&2702		      (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))2703			return 0;2704		ret = ext4_mb_init_group(sb, group, GFP_NOFS);2705		if (ret)2706			return ret;2707	}2708 2709	if (should_lock) {2710		ext4_lock_group(sb, group);2711		__release(ext4_group_lock_ptr(sb, group));2712	}2713	ret = ext4_mb_good_group(ac, group, cr);2714out:2715	if (should_lock) {2716		__acquire(ext4_group_lock_ptr(sb, group));2717		ext4_unlock_group(sb, group);2718	}2719	return ret;2720}2721 2722/*2723 * Start prefetching @nr block bitmaps starting at @group.2724 * Return the next group which needs to be prefetched.2725 */2726ext4_group_t ext4_mb_prefetch(struct super_block *sb, ext4_group_t group,2727			      unsigned int nr, int *cnt)2728{2729	ext4_group_t ngroups = ext4_get_groups_count(sb);2730	struct buffer_head *bh;2731	struct blk_plug plug;2732 2733	blk_start_plug(&plug);2734	while (nr-- > 0) {2735		struct ext4_group_desc *gdp = ext4_get_group_desc(sb, group,2736								  NULL);2737		struct ext4_group_info *grp = ext4_get_group_info(sb, group);2738 2739		/*2740		 * Prefetch block groups with free blocks; but don't2741		 * bother if it is marked uninitialized on disk, since2742		 * it won't require I/O to read.  Also only try to2743		 * prefetch once, so we avoid getblk() call, which can2744		 * be expensive.2745		 */2746		if (gdp && grp && !EXT4_MB_GRP_TEST_AND_SET_READ(grp) &&2747		    EXT4_MB_GRP_NEED_INIT(grp) &&2748		    ext4_free_group_clusters(sb, gdp) > 0 ) {2749			bh = ext4_read_block_bitmap_nowait(sb, group, true);2750			if (bh && !IS_ERR(bh)) {2751				if (!buffer_uptodate(bh) && cnt)2752					(*cnt)++;2753				brelse(bh);2754			}2755		}2756		if (++group >= ngroups)2757			group = 0;2758	}2759	blk_finish_plug(&plug);2760	return group;2761}2762 2763/*2764 * Prefetching reads the block bitmap into the buffer cache; but we2765 * need to make sure that the buddy bitmap in the page cache has been2766 * initialized.  Note that ext4_mb_init_group() will block if the I/O2767 * is not yet completed, or indeed if it was not initiated by2768 * ext4_mb_prefetch did not start the I/O.2769 *2770 * TODO: We should actually kick off the buddy bitmap setup in a work2771 * queue when the buffer I/O is completed, so that we don't block2772 * waiting for the block allocation bitmap read to finish when2773 * ext4_mb_prefetch_fini is called from ext4_mb_regular_allocator().2774 */2775void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group,2776			   unsigned int nr)2777{2778	struct ext4_group_desc *gdp;2779	struct ext4_group_info *grp;2780 2781	while (nr-- > 0) {2782		if (!group)2783			group = ext4_get_groups_count(sb);2784		group--;2785		gdp = ext4_get_group_desc(sb, group, NULL);2786		grp = ext4_get_group_info(sb, group);2787 2788		if (grp && gdp && EXT4_MB_GRP_NEED_INIT(grp) &&2789		    ext4_free_group_clusters(sb, gdp) > 0) {2790			if (ext4_mb_init_group(sb, group, GFP_NOFS))2791				break;2792		}2793	}2794}2795 2796static noinline_for_stack int2797ext4_mb_regular_allocator(struct ext4_allocation_context *ac)2798{2799	ext4_group_t prefetch_grp = 0, ngroups, group, i;2800	enum criteria new_cr, cr = CR_GOAL_LEN_FAST;2801	int err = 0, first_err = 0;2802	unsigned int nr = 0, prefetch_ios = 0;2803	struct ext4_sb_info *sbi;2804	struct super_block *sb;2805	struct ext4_buddy e4b;2806	int lost;2807 2808	sb = ac->ac_sb;2809	sbi = EXT4_SB(sb);2810	ngroups = ext4_get_groups_count(sb);2811	/* non-extent files are limited to low blocks/groups */2812	if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))2813		ngroups = sbi->s_blockfile_groups;2814 2815	BUG_ON(ac->ac_status == AC_STATUS_FOUND);2816 2817	/* first, try the goal */2818	err = ext4_mb_find_by_goal(ac, &e4b);2819	if (err || ac->ac_status == AC_STATUS_FOUND)2820		goto out;2821 2822	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))2823		goto out;2824 2825	/*2826	 * ac->ac_2order is set only if the fe_len is a power of 22827	 * if ac->ac_2order is set we also set criteria to CR_POWER2_ALIGNED2828	 * so that we try exact allocation using buddy.2829	 */2830	i = fls(ac->ac_g_ex.fe_len);2831	ac->ac_2order = 0;2832	/*2833	 * We search using buddy data only if the order of the request2834	 * is greater than equal to the sbi_s_mb_order2_reqs2835	 * You can tune it via /sys/fs/ext4/<partition>/mb_order2_req2836	 * We also support searching for power-of-two requests only for2837	 * requests upto maximum buddy size we have constructed.2838	 */2839	if (i >= sbi->s_mb_order2_reqs && i <= MB_NUM_ORDERS(sb)) {2840		if (is_power_of_2(ac->ac_g_ex.fe_len))2841			ac->ac_2order = array_index_nospec(i - 1,2842							   MB_NUM_ORDERS(sb));2843	}2844 2845	/* if stream allocation is enabled, use global goal */2846	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {2847		/* TBD: may be hot point */2848		spin_lock(&sbi->s_md_lock);2849		ac->ac_g_ex.fe_group = sbi->s_mb_last_group;2850		ac->ac_g_ex.fe_start = sbi->s_mb_last_start;2851		spin_unlock(&sbi->s_md_lock);2852	}2853 2854	/*2855	 * Let's just scan groups to find more-less suitable blocks We2856	 * start with CR_GOAL_LEN_FAST, unless it is power of 22857	 * aligned, in which case let's do that faster approach first.2858	 */2859	if (ac->ac_2order)2860		cr = CR_POWER2_ALIGNED;2861repeat:2862	for (; cr < EXT4_MB_NUM_CRS && ac->ac_status == AC_STATUS_CONTINUE; cr++) {2863		ac->ac_criteria = cr;2864		/*2865		 * searching for the right group start2866		 * from the goal value specified2867		 */2868		group = ac->ac_g_ex.fe_group;2869		ac->ac_groups_linear_remaining = sbi->s_mb_max_linear_groups;2870		prefetch_grp = group;2871		nr = 0;2872 2873		for (i = 0, new_cr = cr; i < ngroups; i++,2874		     ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups)) {2875			int ret = 0;2876 2877			cond_resched();2878			if (new_cr != cr) {2879				cr = new_cr;2880				goto repeat;2881			}2882 2883			/*2884			 * Batch reads of the block allocation bitmaps2885			 * to get multiple READs in flight; limit2886			 * prefetching at inexpensive CR, otherwise mballoc2887			 * can spend a lot of time loading imperfect groups2888			 */2889			if ((prefetch_grp == group) &&2890			    (ext4_mb_cr_expensive(cr) ||2891			     prefetch_ios < sbi->s_mb_prefetch_limit)) {2892				nr = sbi->s_mb_prefetch;2893				if (ext4_has_feature_flex_bg(sb)) {2894					nr = 1 << sbi->s_log_groups_per_flex;2895					nr -= group & (nr - 1);2896					nr = min(nr, sbi->s_mb_prefetch);2897				}2898				prefetch_grp = ext4_mb_prefetch(sb, group,2899							nr, &prefetch_ios);2900			}2901 2902			/* This now checks without needing the buddy page */2903			ret = ext4_mb_good_group_nolock(ac, group, cr);2904			if (ret <= 0) {2905				if (!first_err)2906					first_err = ret;2907				continue;2908			}2909 2910			err = ext4_mb_load_buddy(sb, group, &e4b);2911			if (err)2912				goto out;2913 2914			ext4_lock_group(sb, group);2915 2916			/*2917			 * We need to check again after locking the2918			 * block group2919			 */2920			ret = ext4_mb_good_group(ac, group, cr);2921			if (ret == 0) {2922				ext4_unlock_group(sb, group);2923				ext4_mb_unload_buddy(&e4b);2924				continue;2925			}2926 2927			ac->ac_groups_scanned++;2928			if (cr == CR_POWER2_ALIGNED)2929				ext4_mb_simple_scan_group(ac, &e4b);2930			else {2931				bool is_stripe_aligned =2932					(sbi->s_stripe >=2933					 sbi->s_cluster_ratio) &&2934					!(ac->ac_g_ex.fe_len %2935					  EXT4_NUM_B2C(sbi, sbi->s_stripe));2936 2937				if ((cr == CR_GOAL_LEN_FAST ||2938				     cr == CR_BEST_AVAIL_LEN) &&2939				    is_stripe_aligned)2940					ext4_mb_scan_aligned(ac, &e4b);2941 2942				if (ac->ac_status == AC_STATUS_CONTINUE)2943					ext4_mb_complex_scan_group(ac, &e4b);2944			}2945 2946			ext4_unlock_group(sb, group);2947			ext4_mb_unload_buddy(&e4b);2948 2949			if (ac->ac_status != AC_STATUS_CONTINUE)2950				break;2951		}2952		/* Processed all groups and haven't found blocks */2953		if (sbi->s_mb_stats && i == ngroups)2954			atomic64_inc(&sbi->s_bal_cX_failed[cr]);2955 2956		if (i == ngroups && ac->ac_criteria == CR_BEST_AVAIL_LEN)2957			/* Reset goal length to original goal length before2958			 * falling into CR_GOAL_LEN_SLOW */2959			ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;2960	}2961 2962	if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&2963	    !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {2964		/*2965		 * We've been searching too long. Let's try to allocate2966		 * the best chunk we've found so far2967		 */2968		ext4_mb_try_best_found(ac, &e4b);2969		if (ac->ac_status != AC_STATUS_FOUND) {2970			/*2971			 * Someone more lucky has already allocated it.2972			 * The only thing we can do is just take first2973			 * found block(s)2974			 */2975			lost = atomic_inc_return(&sbi->s_mb_lost_chunks);2976			mb_debug(sb, "lost chunk, group: %u, start: %d, len: %d, lost: %d\n",2977				 ac->ac_b_ex.fe_group, ac->ac_b_ex.fe_start,2978				 ac->ac_b_ex.fe_len, lost);2979 2980			ac->ac_b_ex.fe_group = 0;2981			ac->ac_b_ex.fe_start = 0;2982			ac->ac_b_ex.fe_len = 0;2983			ac->ac_status = AC_STATUS_CONTINUE;2984			ac->ac_flags |= EXT4_MB_HINT_FIRST;2985			cr = CR_ANY_FREE;2986			goto repeat;2987		}2988	}2989 2990	if (sbi->s_mb_stats && ac->ac_status == AC_STATUS_FOUND)2991		atomic64_inc(&sbi->s_bal_cX_hits[ac->ac_criteria]);2992out:2993	if (!err && ac->ac_status != AC_STATUS_FOUND && first_err)2994		err = first_err;2995 2996	mb_debug(sb, "Best len %d, origin len %d, ac_status %u, ac_flags 0x%x, cr %d ret %d\n",2997		 ac->ac_b_ex.fe_len, ac->ac_o_ex.fe_len, ac->ac_status,2998		 ac->ac_flags, cr, err);2999 3000	if (nr)3001		ext4_mb_prefetch_fini(sb, prefetch_grp, nr);3002 3003	return err;3004}3005 3006static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)3007{3008	struct super_block *sb = pde_data(file_inode(seq->file));3009	ext4_group_t group;3010 3011	if (*pos < 0 || *pos >= ext4_get_groups_count(sb))3012		return NULL;3013	group = *pos + 1;3014	return (void *) ((unsigned long) group);3015}3016 3017static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)3018{3019	struct super_block *sb = pde_data(file_inode(seq->file));3020	ext4_group_t group;3021 3022	++*pos;3023	if (*pos < 0 || *pos >= ext4_get_groups_count(sb))3024		return NULL;3025	group = *pos + 1;3026	return (void *) ((unsigned long) group);3027}3028 3029static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)3030{3031	struct super_block *sb = pde_data(file_inode(seq->file));3032	ext4_group_t group = (ext4_group_t) ((unsigned long) v);3033	int i, err;3034	char nbuf[16];3035	struct ext4_buddy e4b;3036	struct ext4_group_info *grinfo;3037	unsigned char blocksize_bits = min_t(unsigned char,3038					     sb->s_blocksize_bits,3039					     EXT4_MAX_BLOCK_LOG_SIZE);3040	struct sg {3041		struct ext4_group_info info;3042		ext4_grpblk_t counters[EXT4_MAX_BLOCK_LOG_SIZE + 2];3043	} sg;3044 3045	group--;3046	if (group == 0)3047		seq_puts(seq, "#group: free  frags first ["3048			      " 2^0   2^1   2^2   2^3   2^4   2^5   2^6  "3049			      " 2^7   2^8   2^9   2^10  2^11  2^12  2^13  ]\n");3050 3051	i = (blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +3052		sizeof(struct ext4_group_info);3053 3054	grinfo = ext4_get_group_info(sb, group);3055	if (!grinfo)3056		return 0;3057	/* Load the group info in memory only if not already loaded. */3058	if (unlikely(EXT4_MB_GRP_NEED_INIT(grinfo))) {3059		err = ext4_mb_load_buddy(sb, group, &e4b);3060		if (err) {3061			seq_printf(seq, "#%-5u: %s\n", group, ext4_decode_error(NULL, err, nbuf));3062			return 0;3063		}3064		ext4_mb_unload_buddy(&e4b);3065	}3066 3067	/*3068	 * We care only about free space counters in the group info and3069	 * these are safe to access even after the buddy has been unloaded3070	 */3071	memcpy(&sg, grinfo, i);3072	seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,3073			sg.info.bb_fragments, sg.info.bb_first_free);3074	for (i = 0; i <= 13; i++)3075		seq_printf(seq, " %-5u", i <= blocksize_bits + 1 ?3076				sg.info.bb_counters[i] : 0);3077	seq_puts(seq, " ]");3078	if (EXT4_MB_GRP_BBITMAP_CORRUPT(&sg.info))3079		seq_puts(seq, " Block bitmap corrupted!");3080	seq_putc(seq, '\n');3081	return 0;3082}3083 3084static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)3085{3086}3087 3088const struct seq_operations ext4_mb_seq_groups_ops = {3089	.start  = ext4_mb_seq_groups_start,3090	.next   = ext4_mb_seq_groups_next,3091	.stop   = ext4_mb_seq_groups_stop,3092	.show   = ext4_mb_seq_groups_show,3093};3094 3095int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)3096{3097	struct super_block *sb = seq->private;3098	struct ext4_sb_info *sbi = EXT4_SB(sb);3099 3100	seq_puts(seq, "mballoc:\n");3101	if (!sbi->s_mb_stats) {3102		seq_puts(seq, "\tmb stats collection turned off.\n");3103		seq_puts(3104			seq,3105			"\tTo enable, please write \"1\" to sysfs file mb_stats.\n");3106		return 0;3107	}3108	seq_printf(seq, "\treqs: %u\n", atomic_read(&sbi->s_bal_reqs));3109	seq_printf(seq, "\tsuccess: %u\n", atomic_read(&sbi->s_bal_success));3110 3111	seq_printf(seq, "\tgroups_scanned: %u\n",3112		   atomic_read(&sbi->s_bal_groups_scanned));3113 3114	/* CR_POWER2_ALIGNED stats */3115	seq_puts(seq, "\tcr_p2_aligned_stats:\n");3116	seq_printf(seq, "\t\thits: %llu\n",3117		   atomic64_read(&sbi->s_bal_cX_hits[CR_POWER2_ALIGNED]));3118	seq_printf(3119		seq, "\t\tgroups_considered: %llu\n",3120		atomic64_read(3121			&sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]));3122	seq_printf(seq, "\t\textents_scanned: %u\n",3123		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_POWER2_ALIGNED]));3124	seq_printf(seq, "\t\tuseless_loops: %llu\n",3125		   atomic64_read(&sbi->s_bal_cX_failed[CR_POWER2_ALIGNED]));3126	seq_printf(seq, "\t\tbad_suggestions: %u\n",3127		   atomic_read(&sbi->s_bal_p2_aligned_bad_suggestions));3128 3129	/* CR_GOAL_LEN_FAST stats */3130	seq_puts(seq, "\tcr_goal_fast_stats:\n");3131	seq_printf(seq, "\t\thits: %llu\n",3132		   atomic64_read(&sbi->s_bal_cX_hits[CR_GOAL_LEN_FAST]));3133	seq_printf(seq, "\t\tgroups_considered: %llu\n",3134		   atomic64_read(3135			   &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_FAST]));3136	seq_printf(seq, "\t\textents_scanned: %u\n",3137		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_FAST]));3138	seq_printf(seq, "\t\tuseless_loops: %llu\n",3139		   atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_FAST]));3140	seq_printf(seq, "\t\tbad_suggestions: %u\n",3141		   atomic_read(&sbi->s_bal_goal_fast_bad_suggestions));3142 3143	/* CR_BEST_AVAIL_LEN stats */3144	seq_puts(seq, "\tcr_best_avail_stats:\n");3145	seq_printf(seq, "\t\thits: %llu\n",3146		   atomic64_read(&sbi->s_bal_cX_hits[CR_BEST_AVAIL_LEN]));3147	seq_printf(3148		seq, "\t\tgroups_considered: %llu\n",3149		atomic64_read(3150			&sbi->s_bal_cX_groups_considered[CR_BEST_AVAIL_LEN]));3151	seq_printf(seq, "\t\textents_scanned: %u\n",3152		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_BEST_AVAIL_LEN]));3153	seq_printf(seq, "\t\tuseless_loops: %llu\n",3154		   atomic64_read(&sbi->s_bal_cX_failed[CR_BEST_AVAIL_LEN]));3155	seq_printf(seq, "\t\tbad_suggestions: %u\n",3156		   atomic_read(&sbi->s_bal_best_avail_bad_suggestions));3157 3158	/* CR_GOAL_LEN_SLOW stats */3159	seq_puts(seq, "\tcr_goal_slow_stats:\n");3160	seq_printf(seq, "\t\thits: %llu\n",3161		   atomic64_read(&sbi->s_bal_cX_hits[CR_GOAL_LEN_SLOW]));3162	seq_printf(seq, "\t\tgroups_considered: %llu\n",3163		   atomic64_read(3164			   &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_SLOW]));3165	seq_printf(seq, "\t\textents_scanned: %u\n",3166		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_SLOW]));3167	seq_printf(seq, "\t\tuseless_loops: %llu\n",3168		   atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_SLOW]));3169 3170	/* CR_ANY_FREE stats */3171	seq_puts(seq, "\tcr_any_free_stats:\n");3172	seq_printf(seq, "\t\thits: %llu\n",3173		   atomic64_read(&sbi->s_bal_cX_hits[CR_ANY_FREE]));3174	seq_printf(3175		seq, "\t\tgroups_considered: %llu\n",3176		atomic64_read(&sbi->s_bal_cX_groups_considered[CR_ANY_FREE]));3177	seq_printf(seq, "\t\textents_scanned: %u\n",3178		   atomic_read(&sbi->s_bal_cX_ex_scanned[CR_ANY_FREE]));3179	seq_printf(seq, "\t\tuseless_loops: %llu\n",3180		   atomic64_read(&sbi->s_bal_cX_failed[CR_ANY_FREE]));3181 3182	/* Aggregates */3183	seq_printf(seq, "\textents_scanned: %u\n",3184		   atomic_read(&sbi->s_bal_ex_scanned));3185	seq_printf(seq, "\t\tgoal_hits: %u\n", atomic_read(&sbi->s_bal_goals));3186	seq_printf(seq, "\t\tlen_goal_hits: %u\n",3187		   atomic_read(&sbi->s_bal_len_goals));3188	seq_printf(seq, "\t\t2^n_hits: %u\n", atomic_read(&sbi->s_bal_2orders));3189	seq_printf(seq, "\t\tbreaks: %u\n", atomic_read(&sbi->s_bal_breaks));3190	seq_printf(seq, "\t\tlost: %u\n", atomic_read(&sbi->s_mb_lost_chunks));3191	seq_printf(seq, "\tbuddies_generated: %u/%u\n",3192		   atomic_read(&sbi->s_mb_buddies_generated),3193		   ext4_get_groups_count(sb));3194	seq_printf(seq, "\tbuddies_time_used: %llu\n",3195		   atomic64_read(&sbi->s_mb_generation_time));3196	seq_printf(seq, "\tpreallocated: %u\n",3197		   atomic_read(&sbi->s_mb_preallocated));3198	seq_printf(seq, "\tdiscarded: %u\n", atomic_read(&sbi->s_mb_discarded));3199	return 0;3200}3201 3202static void *ext4_mb_seq_structs_summary_start(struct seq_file *seq, loff_t *pos)3203{3204	struct super_block *sb = pde_data(file_inode(seq->file));3205	unsigned long position;3206 3207	if (*pos < 0 || *pos >= 2*MB_NUM_ORDERS(sb))3208		return NULL;3209	position = *pos + 1;3210	return (void *) ((unsigned long) position);3211}3212 3213static void *ext4_mb_seq_structs_summary_next(struct seq_file *seq, void *v, loff_t *pos)3214{3215	struct super_block *sb = pde_data(file_inode(seq->file));3216	unsigned long position;3217 3218	++*pos;3219	if (*pos < 0 || *pos >= 2*MB_NUM_ORDERS(sb))3220		return NULL;3221	position = *pos + 1;3222	return (void *) ((unsigned long) position);3223}3224 3225static int ext4_mb_seq_structs_summary_show(struct seq_file *seq, void *v)3226{3227	struct super_block *sb = pde_data(file_inode(seq->file));3228	struct ext4_sb_info *sbi = EXT4_SB(sb);3229	unsigned long position = ((unsigned long) v);3230	struct ext4_group_info *grp;3231	unsigned int count;3232 3233	position--;3234	if (position >= MB_NUM_ORDERS(sb)) {3235		position -= MB_NUM_ORDERS(sb);3236		if (position == 0)3237			seq_puts(seq, "avg_fragment_size_lists:\n");3238 3239		count = 0;3240		read_lock(&sbi->s_mb_avg_fragment_size_locks[position]);3241		list_for_each_entry(grp, &sbi->s_mb_avg_fragment_size[position],3242				    bb_avg_fragment_size_node)3243			count++;3244		read_unlock(&sbi->s_mb_avg_fragment_size_locks[position]);3245		seq_printf(seq, "\tlist_order_%u_groups: %u\n",3246					(unsigned int)position, count);3247		return 0;3248	}3249 3250	if (position == 0) {3251		seq_printf(seq, "optimize_scan: %d\n",3252			   test_opt2(sb, MB_OPTIMIZE_SCAN) ? 1 : 0);3253		seq_puts(seq, "max_free_order_lists:\n");3254	}3255	count = 0;3256	read_lock(&sbi->s_mb_largest_free_orders_locks[position]);3257	list_for_each_entry(grp, &sbi->s_mb_largest_free_orders[position],3258			    bb_largest_free_order_node)3259		count++;3260	read_unlock(&sbi->s_mb_largest_free_orders_locks[position]);3261	seq_printf(seq, "\tlist_order_%u_groups: %u\n",3262		   (unsigned int)position, count);3263 3264	return 0;3265}3266 3267static void ext4_mb_seq_structs_summary_stop(struct seq_file *seq, void *v)3268{3269}3270 3271const struct seq_operations ext4_mb_seq_structs_summary_ops = {3272	.start  = ext4_mb_seq_structs_summary_start,3273	.next   = ext4_mb_seq_structs_summary_next,3274	.stop   = ext4_mb_seq_structs_summary_stop,3275	.show   = ext4_mb_seq_structs_summary_show,3276};3277 3278static struct kmem_cache *get_groupinfo_cache(int blocksize_bits)3279{3280	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;3281	struct kmem_cache *cachep = ext4_groupinfo_caches[cache_index];3282 3283	BUG_ON(!cachep);3284	return cachep;3285}3286 3287/*3288 * Allocate the top-level s_group_info array for the specified number3289 * of groups3290 */3291int ext4_mb_alloc_groupinfo(struct super_block *sb, ext4_group_t ngroups)3292{3293	struct ext4_sb_info *sbi = EXT4_SB(sb);3294	unsigned size;3295	struct ext4_group_info ***old_groupinfo, ***new_groupinfo;3296 3297	size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>3298		EXT4_DESC_PER_BLOCK_BITS(sb);3299	if (size <= sbi->s_group_info_size)3300		return 0;3301 3302	size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);3303	new_groupinfo = kvzalloc(size, GFP_KERNEL);3304	if (!new_groupinfo) {3305		ext4_msg(sb, KERN_ERR, "can't allocate buddy meta group");3306		return -ENOMEM;3307	}3308	rcu_read_lock();3309	old_groupinfo = rcu_dereference(sbi->s_group_info);3310	if (old_groupinfo)3311		memcpy(new_groupinfo, old_groupinfo,3312		       sbi->s_group_info_size * sizeof(*sbi->s_group_info));3313	rcu_read_unlock();3314	rcu_assign_pointer(sbi->s_group_info, new_groupinfo);3315	sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);3316	if (old_groupinfo)3317		ext4_kvfree_array_rcu(old_groupinfo);3318	ext4_debug("allocated s_groupinfo array for %d meta_bg's\n",3319		   sbi->s_group_info_size);3320	return 0;3321}3322 3323/* Create and initialize ext4_group_info data for the given group. */3324int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,3325			  struct ext4_group_desc *desc)3326{3327	int i;3328	int metalen = 0;3329	int idx = group >> EXT4_DESC_PER_BLOCK_BITS(sb);3330	struct ext4_sb_info *sbi = EXT4_SB(sb);3331	struct ext4_group_info **meta_group_info;3332	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);3333 3334	/*3335	 * First check if this group is the first of a reserved block.3336	 * If it's true, we have to allocate a new table of pointers3337	 * to ext4_group_info structures3338	 */3339	if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {3340		metalen = sizeof(*meta_group_info) <<3341			EXT4_DESC_PER_BLOCK_BITS(sb);3342		meta_group_info = kmalloc(metalen, GFP_NOFS);3343		if (meta_group_info == NULL) {3344			ext4_msg(sb, KERN_ERR, "can't allocate mem "3345				 "for a buddy group");3346			return -ENOMEM;3347		}3348		rcu_read_lock();3349		rcu_dereference(sbi->s_group_info)[idx] = meta_group_info;3350		rcu_read_unlock();3351	}3352 3353	meta_group_info = sbi_array_rcu_deref(sbi, s_group_info, idx);3354	i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);3355 3356	meta_group_info[i] = kmem_cache_zalloc(cachep, GFP_NOFS);3357	if (meta_group_info[i] == NULL) {3358		ext4_msg(sb, KERN_ERR, "can't allocate buddy mem");3359		goto exit_group_info;3360	}3361	set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,3362		&(meta_group_info[i]->bb_state));3363 3364	/*3365	 * initialize bb_free to be able to skip3366	 * empty groups without initialization3367	 */3368	if (ext4_has_group_desc_csum(sb) &&3369	    (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {3370		meta_group_info[i]->bb_free =3371			ext4_free_clusters_after_init(sb, group, desc);3372	} else {3373		meta_group_info[i]->bb_free =3374			ext4_free_group_clusters(sb, desc);3375	}3376 3377	INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);3378	init_rwsem(&meta_group_info[i]->alloc_sem);3379	meta_group_info[i]->bb_free_root = RB_ROOT;3380	INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);3381	INIT_LIST_HEAD(&meta_group_info[i]->bb_avg_fragment_size_node);3382	meta_group_info[i]->bb_largest_free_order = -1;  /* uninit */3383	meta_group_info[i]->bb_avg_fragment_size_order = -1;  /* uninit */3384	meta_group_info[i]->bb_group = group;3385 3386	mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);3387	return 0;3388 3389exit_group_info:3390	/* If a meta_group_info table has been allocated, release it now */3391	if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {3392		struct ext4_group_info ***group_info;3393 3394		rcu_read_lock();3395		group_info = rcu_dereference(sbi->s_group_info);3396		kfree(group_info[idx]);3397		group_info[idx] = NULL;3398		rcu_read_unlock();3399	}3400	return -ENOMEM;3401} /* ext4_mb_add_groupinfo */3402 3403static int ext4_mb_init_backend(struct super_block *sb)3404{3405	ext4_group_t ngroups = ext4_get_groups_count(sb);3406	ext4_group_t i;3407	struct ext4_sb_info *sbi = EXT4_SB(sb);3408	int err;3409	struct ext4_group_desc *desc;3410	struct ext4_group_info ***group_info;3411	struct kmem_cache *cachep;3412 3413	err = ext4_mb_alloc_groupinfo(sb, ngroups);3414	if (err)3415		return err;3416 3417	sbi->s_buddy_cache = new_inode(sb);3418	if (sbi->s_buddy_cache == NULL) {3419		ext4_msg(sb, KERN_ERR, "can't get new inode");3420		goto err_freesgi;3421	}3422	/* To avoid potentially colliding with an valid on-disk inode number,3423	 * use EXT4_BAD_INO for the buddy cache inode number.  This inode is3424	 * not in the inode hash, so it should never be found by iget(), but3425	 * this will avoid confusion if it ever shows up during debugging. */3426	sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;3427	EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;3428	for (i = 0; i < ngroups; i++) {3429		cond_resched();3430		desc = ext4_get_group_desc(sb, i, NULL);3431		if (desc == NULL) {3432			ext4_msg(sb, KERN_ERR, "can't read descriptor %u", i);3433			goto err_freebuddy;3434		}3435		if (ext4_mb_add_groupinfo(sb, i, desc) != 0)3436			goto err_freebuddy;3437	}3438 3439	if (ext4_has_feature_flex_bg(sb)) {3440		/* a single flex group is supposed to be read by a single IO.3441		 * 2 ^ s_log_groups_per_flex != UINT_MAX as s_mb_prefetch is3442		 * unsigned integer, so the maximum shift is 32.3443		 */3444		if (sbi->s_es->s_log_groups_per_flex >= 32) {3445			ext4_msg(sb, KERN_ERR, "too many log groups per flexible block group");3446			goto err_freebuddy;3447		}3448		sbi->s_mb_prefetch = min_t(uint, 1 << sbi->s_es->s_log_groups_per_flex,3449			BLK_MAX_SEGMENT_SIZE >> (sb->s_blocksize_bits - 9));3450		sbi->s_mb_prefetch *= 8; /* 8 prefetch IOs in flight at most */3451	} else {3452		sbi->s_mb_prefetch = 32;3453	}3454	if (sbi->s_mb_prefetch > ext4_get_groups_count(sb))3455		sbi->s_mb_prefetch = ext4_get_groups_count(sb);3456	/*3457	 * now many real IOs to prefetch within a single allocation at3458	 * CR_POWER2_ALIGNED. Given CR_POWER2_ALIGNED is an CPU-related3459	 * optimization we shouldn't try to load too many groups, at some point3460	 * we should start to use what we've got in memory.3461	 * with an average random access time 5ms, it'd take a second to get3462	 * 200 groups (* N with flex_bg), so let's make this limit 43463	 */3464	sbi->s_mb_prefetch_limit = sbi->s_mb_prefetch * 4;3465	if (sbi->s_mb_prefetch_limit > ext4_get_groups_count(sb))3466		sbi->s_mb_prefetch_limit = ext4_get_groups_count(sb);3467 3468	return 0;3469 3470err_freebuddy:3471	cachep = get_groupinfo_cache(sb->s_blocksize_bits);3472	while (i-- > 0) {3473		struct ext4_group_info *grp = ext4_get_group_info(sb, i);3474 3475		if (grp)3476			kmem_cache_free(cachep, grp);3477	}3478	i = sbi->s_group_info_size;3479	rcu_read_lock();3480	group_info = rcu_dereference(sbi->s_group_info);3481	while (i-- > 0)3482		kfree(group_info[i]);3483	rcu_read_unlock();3484	iput(sbi->s_buddy_cache);3485err_freesgi:3486	rcu_read_lock();3487	kvfree(rcu_dereference(sbi->s_group_info));3488	rcu_read_unlock();3489	return -ENOMEM;3490}3491 3492static void ext4_groupinfo_destroy_slabs(void)3493{3494	int i;3495 3496	for (i = 0; i < NR_GRPINFO_CACHES; i++) {3497		kmem_cache_destroy(ext4_groupinfo_caches[i]);3498		ext4_groupinfo_caches[i] = NULL;3499	}3500}3501 3502static int ext4_groupinfo_create_slab(size_t size)3503{3504	static DEFINE_MUTEX(ext4_grpinfo_slab_create_mutex);3505	int slab_size;3506	int blocksize_bits = order_base_2(size);3507	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;3508	struct kmem_cache *cachep;3509 3510	if (cache_index >= NR_GRPINFO_CACHES)3511		return -EINVAL;3512 3513	if (unlikely(cache_index < 0))3514		cache_index = 0;3515 3516	mutex_lock(&ext4_grpinfo_slab_create_mutex);3517	if (ext4_groupinfo_caches[cache_index]) {3518		mutex_unlock(&ext4_grpinfo_slab_create_mutex);3519		return 0;	/* Already created */3520	}3521 3522	slab_size = offsetof(struct ext4_group_info,3523				bb_counters[blocksize_bits + 2]);3524 3525	cachep = kmem_cache_create(ext4_groupinfo_slab_names[cache_index],3526					slab_size, 0, SLAB_RECLAIM_ACCOUNT,3527					NULL);3528 3529	ext4_groupinfo_caches[cache_index] = cachep;3530 3531	mutex_unlock(&ext4_grpinfo_slab_create_mutex);3532	if (!cachep) {3533		printk(KERN_EMERG3534		       "EXT4-fs: no memory for groupinfo slab cache\n");3535		return -ENOMEM;3536	}3537 3538	return 0;3539}3540 3541static void ext4_discard_work(struct work_struct *work)3542{3543	struct ext4_sb_info *sbi = container_of(work,3544			struct ext4_sb_info, s_discard_work);3545	struct super_block *sb = sbi->s_sb;3546	struct ext4_free_data *fd, *nfd;3547	struct ext4_buddy e4b;3548	LIST_HEAD(discard_list);3549	ext4_group_t grp, load_grp;3550	int err = 0;3551 3552	spin_lock(&sbi->s_md_lock);3553	list_splice_init(&sbi->s_discard_list, &discard_list);3554	spin_unlock(&sbi->s_md_lock);3555 3556	load_grp = UINT_MAX;3557	list_for_each_entry_safe(fd, nfd, &discard_list, efd_list) {3558		/*3559		 * If filesystem is umounting or no memory or suffering3560		 * from no space, give up the discard3561		 */3562		if ((sb->s_flags & SB_ACTIVE) && !err &&3563		    !atomic_read(&sbi->s_retry_alloc_pending)) {3564			grp = fd->efd_group;3565			if (grp != load_grp) {3566				if (load_grp != UINT_MAX)3567					ext4_mb_unload_buddy(&e4b);3568 3569				err = ext4_mb_load_buddy(sb, grp, &e4b);3570				if (err) {3571					kmem_cache_free(ext4_free_data_cachep, fd);3572					load_grp = UINT_MAX;3573					continue;3574				} else {3575					load_grp = grp;3576				}3577			}3578 3579			ext4_lock_group(sb, grp);3580			ext4_try_to_trim_range(sb, &e4b, fd->efd_start_cluster,3581						fd->efd_start_cluster + fd->efd_count - 1, 1);3582			ext4_unlock_group(sb, grp);3583		}3584		kmem_cache_free(ext4_free_data_cachep, fd);3585	}3586 3587	if (load_grp != UINT_MAX)3588		ext4_mb_unload_buddy(&e4b);3589}3590 3591int ext4_mb_init(struct super_block *sb)3592{3593	struct ext4_sb_info *sbi = EXT4_SB(sb);3594	unsigned i, j;3595	unsigned offset, offset_incr;3596	unsigned max;3597	int ret;3598 3599	i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_offsets);3600 3601	sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);3602	if (sbi->s_mb_offsets == NULL) {3603		ret = -ENOMEM;3604		goto out;3605	}3606 3607	i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_maxs);3608	sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);3609	if (sbi->s_mb_maxs == NULL) {3610		ret = -ENOMEM;3611		goto out;3612	}3613 3614	ret = ext4_groupinfo_create_slab(sb->s_blocksize);3615	if (ret < 0)3616		goto out;3617 3618	/* order 0 is regular bitmap */3619	sbi->s_mb_maxs[0] = sb->s_blocksize << 3;3620	sbi->s_mb_offsets[0] = 0;3621 3622	i = 1;3623	offset = 0;3624	offset_incr = 1 << (sb->s_blocksize_bits - 1);3625	max = sb->s_blocksize << 2;3626	do {3627		sbi->s_mb_offsets[i] = offset;3628		sbi->s_mb_maxs[i] = max;3629		offset += offset_incr;3630		offset_incr = offset_incr >> 1;3631		max = max >> 1;3632		i++;3633	} while (i < MB_NUM_ORDERS(sb));3634 3635	sbi->s_mb_avg_fragment_size =3636		kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),3637			GFP_KERNEL);3638	if (!sbi->s_mb_avg_fragment_size) {3639		ret = -ENOMEM;3640		goto out;3641	}3642	sbi->s_mb_avg_fragment_size_locks =3643		kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),3644			GFP_KERNEL);3645	if (!sbi->s_mb_avg_fragment_size_locks) {3646		ret = -ENOMEM;3647		goto out;3648	}3649	for (i = 0; i < MB_NUM_ORDERS(sb); i++) {3650		INIT_LIST_HEAD(&sbi->s_mb_avg_fragment_size[i]);3651		rwlock_init(&sbi->s_mb_avg_fragment_size_locks[i]);3652	}3653	sbi->s_mb_largest_free_orders =3654		kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),3655			GFP_KERNEL);3656	if (!sbi->s_mb_largest_free_orders) {3657		ret = -ENOMEM;3658		goto out;3659	}3660	sbi->s_mb_largest_free_orders_locks =3661		kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),3662			GFP_KERNEL);3663	if (!sbi->s_mb_largest_free_orders_locks) {3664		ret = -ENOMEM;3665		goto out;3666	}3667	for (i = 0; i < MB_NUM_ORDERS(sb); i++) {3668		INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);3669		rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);3670	}3671 3672	spin_lock_init(&sbi->s_md_lock);3673	sbi->s_mb_free_pending = 0;3674	INIT_LIST_HEAD(&sbi->s_freed_data_list[0]);3675	INIT_LIST_HEAD(&sbi->s_freed_data_list[1]);3676	INIT_LIST_HEAD(&sbi->s_discard_list);3677	INIT_WORK(&sbi->s_discard_work, ext4_discard_work);3678	atomic_set(&sbi->s_retry_alloc_pending, 0);3679 3680	sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;3681	sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;3682	sbi->s_mb_stats = MB_DEFAULT_STATS;3683	sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;3684	sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;3685	sbi->s_mb_best_avail_max_trim_order = MB_DEFAULT_BEST_AVAIL_TRIM_ORDER;3686 3687	/*3688	 * The default group preallocation is 512, which for 4k block3689	 * sizes translates to 2 megabytes.  However for bigalloc file3690	 * systems, this is probably too big (i.e, if the cluster size3691	 * is 1 megabyte, then group preallocation size becomes half a3692	 * gigabyte!).  As a default, we will keep a two megabyte3693	 * group pralloc size for cluster sizes up to 64k, and after3694	 * that, we will force a minimum group preallocation size of3695	 * 32 clusters.  This translates to 8 megs when the cluster3696	 * size is 256k, and 32 megs when the cluster size is 1 meg,3697	 * which seems reasonable as a default.3698	 */3699	sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>3700				       sbi->s_cluster_bits, 32);3701	/*3702	 * If there is a s_stripe > 1, then we set the s_mb_group_prealloc3703	 * to the lowest multiple of s_stripe which is bigger than3704	 * the s_mb_group_prealloc as determined above. We want3705	 * the preallocation size to be an exact multiple of the3706	 * RAID stripe size so that preallocations don't fragment3707	 * the stripes.3708	 */3709	if (sbi->s_stripe > 1) {3710		sbi->s_mb_group_prealloc = roundup(3711			sbi->s_mb_group_prealloc, EXT4_NUM_B2C(sbi, sbi->s_stripe));3712	}3713 3714	sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);3715	if (sbi->s_locality_groups == NULL) {3716		ret = -ENOMEM;3717		goto out;3718	}3719	for_each_possible_cpu(i) {3720		struct ext4_locality_group *lg;3721		lg = per_cpu_ptr(sbi->s_locality_groups, i);3722		mutex_init(&lg->lg_mutex);3723		for (j = 0; j < PREALLOC_TB_SIZE; j++)3724			INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);3725		spin_lock_init(&lg->lg_prealloc_lock);3726	}3727 3728	if (bdev_nonrot(sb->s_bdev))3729		sbi->s_mb_max_linear_groups = 0;3730	else3731		sbi->s_mb_max_linear_groups = MB_DEFAULT_LINEAR_LIMIT;3732	/* init file for buddy data */3733	ret = ext4_mb_init_backend(sb);3734	if (ret != 0)3735		goto out_free_locality_groups;3736 3737	return 0;3738 3739out_free_locality_groups:3740	free_percpu(sbi->s_locality_groups);3741	sbi->s_locality_groups = NULL;3742out:3743	kfree(sbi->s_mb_avg_fragment_size);3744	kfree(sbi->s_mb_avg_fragment_size_locks);3745	kfree(sbi->s_mb_largest_free_orders);3746	kfree(sbi->s_mb_largest_free_orders_locks);3747	kfree(sbi->s_mb_offsets);3748	sbi->s_mb_offsets = NULL;3749	kfree(sbi->s_mb_maxs);3750	sbi->s_mb_maxs = NULL;3751	return ret;3752}3753 3754/* need to called with the ext4 group lock held */3755static int ext4_mb_cleanup_pa(struct ext4_group_info *grp)3756{3757	struct ext4_prealloc_space *pa;3758	struct list_head *cur, *tmp;3759	int count = 0;3760 3761	list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {3762		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);3763		list_del(&pa->pa_group_list);3764		count++;3765		kmem_cache_free(ext4_pspace_cachep, pa);3766	}3767	return count;3768}3769 3770void ext4_mb_release(struct super_block *sb)3771{3772	ext4_group_t ngroups = ext4_get_groups_count(sb);3773	ext4_group_t i;3774	int num_meta_group_infos;3775	struct ext4_group_info *grinfo, ***group_info;3776	struct ext4_sb_info *sbi = EXT4_SB(sb);3777	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);3778	int count;3779 3780	if (test_opt(sb, DISCARD)) {3781		/*3782		 * wait the discard work to drain all of ext4_free_data3783		 */3784		flush_work(&sbi->s_discard_work);3785		WARN_ON_ONCE(!list_empty(&sbi->s_discard_list));3786	}3787 3788	if (sbi->s_group_info) {3789		for (i = 0; i < ngroups; i++) {3790			cond_resched();3791			grinfo = ext4_get_group_info(sb, i);3792			if (!grinfo)3793				continue;3794			mb_group_bb_bitmap_free(grinfo);3795			ext4_lock_group(sb, i);3796			count = ext4_mb_cleanup_pa(grinfo);3797			if (count)3798				mb_debug(sb, "mballoc: %d PAs left\n",3799					 count);3800			ext4_unlock_group(sb, i);3801			kmem_cache_free(cachep, grinfo);3802		}3803		num_meta_group_infos = (ngroups +3804				EXT4_DESC_PER_BLOCK(sb) - 1) >>3805			EXT4_DESC_PER_BLOCK_BITS(sb);3806		rcu_read_lock();3807		group_info = rcu_dereference(sbi->s_group_info);3808		for (i = 0; i < num_meta_group_infos; i++)3809			kfree(group_info[i]);3810		kvfree(group_info);3811		rcu_read_unlock();3812	}3813	kfree(sbi->s_mb_avg_fragment_size);3814	kfree(sbi->s_mb_avg_fragment_size_locks);3815	kfree(sbi->s_mb_largest_free_orders);3816	kfree(sbi->s_mb_largest_free_orders_locks);3817	kfree(sbi->s_mb_offsets);3818	kfree(sbi->s_mb_maxs);3819	iput(sbi->s_buddy_cache);3820	if (sbi->s_mb_stats) {3821		ext4_msg(sb, KERN_INFO,3822		       "mballoc: %u blocks %u reqs (%u success)",3823				atomic_read(&sbi->s_bal_allocated),3824				atomic_read(&sbi->s_bal_reqs),3825				atomic_read(&sbi->s_bal_success));3826		ext4_msg(sb, KERN_INFO,3827		      "mballoc: %u extents scanned, %u groups scanned, %u goal hits, "3828				"%u 2^N hits, %u breaks, %u lost",3829				atomic_read(&sbi->s_bal_ex_scanned),3830				atomic_read(&sbi->s_bal_groups_scanned),3831				atomic_read(&sbi->s_bal_goals),3832				atomic_read(&sbi->s_bal_2orders),3833				atomic_read(&sbi->s_bal_breaks),3834				atomic_read(&sbi->s_mb_lost_chunks));3835		ext4_msg(sb, KERN_INFO,3836		       "mballoc: %u generated and it took %llu",3837				atomic_read(&sbi->s_mb_buddies_generated),3838				atomic64_read(&sbi->s_mb_generation_time));3839		ext4_msg(sb, KERN_INFO,3840		       "mballoc: %u preallocated, %u discarded",3841				atomic_read(&sbi->s_mb_preallocated),3842				atomic_read(&sbi->s_mb_discarded));3843	}3844 3845	free_percpu(sbi->s_locality_groups);3846}3847 3848static inline int ext4_issue_discard(struct super_block *sb,3849		ext4_group_t block_group, ext4_grpblk_t cluster, int count)3850{3851	ext4_fsblk_t discard_block;3852 3853	discard_block = (EXT4_C2B(EXT4_SB(sb), cluster) +3854			 ext4_group_first_block_no(sb, block_group));3855	count = EXT4_C2B(EXT4_SB(sb), count);3856	trace_ext4_discard_blocks(sb,3857			(unsigned long long) discard_block, count);3858 3859	return sb_issue_discard(sb, discard_block, count, GFP_NOFS, 0);3860}3861 3862static void ext4_free_data_in_buddy(struct super_block *sb,3863				    struct ext4_free_data *entry)3864{3865	struct ext4_buddy e4b;3866	struct ext4_group_info *db;3867	int err, count = 0;3868 3869	mb_debug(sb, "gonna free %u blocks in group %u (0x%p):",3870		 entry->efd_count, entry->efd_group, entry);3871 3872	err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b);3873	/* we expect to find existing buddy because it's pinned */3874	BUG_ON(err != 0);3875 3876	spin_lock(&EXT4_SB(sb)->s_md_lock);3877	EXT4_SB(sb)->s_mb_free_pending -= entry->efd_count;3878	spin_unlock(&EXT4_SB(sb)->s_md_lock);3879 3880	db = e4b.bd_info;3881	/* there are blocks to put in buddy to make them really free */3882	count += entry->efd_count;3883	ext4_lock_group(sb, entry->efd_group);3884	/* Take it out of per group rb tree */3885	rb_erase(&entry->efd_node, &(db->bb_free_root));3886	mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count);3887 3888	/*3889	 * Clear the trimmed flag for the group so that the next3890	 * ext4_trim_fs can trim it.3891	 */3892	EXT4_MB_GRP_CLEAR_TRIMMED(db);3893 3894	if (!db->bb_free_root.rb_node) {3895		/* No more items in the per group rb tree3896		 * balance refcounts from ext4_mb_free_metadata()3897		 */3898		folio_put(e4b.bd_buddy_folio);3899		folio_put(e4b.bd_bitmap_folio);3900	}3901	ext4_unlock_group(sb, entry->efd_group);3902	ext4_mb_unload_buddy(&e4b);3903 3904	mb_debug(sb, "freed %d blocks in 1 structures\n", count);3905}3906 3907/*3908 * This function is called by the jbd2 layer once the commit has finished,3909 * so we know we can free the blocks that were released with that commit.3910 */3911void ext4_process_freed_data(struct super_block *sb, tid_t commit_tid)3912{3913	struct ext4_sb_info *sbi = EXT4_SB(sb);3914	struct ext4_free_data *entry, *tmp;3915	LIST_HEAD(freed_data_list);3916	struct list_head *s_freed_head = &sbi->s_freed_data_list[commit_tid & 1];3917	bool wake;3918 3919	list_replace_init(s_freed_head, &freed_data_list);3920 3921	list_for_each_entry(entry, &freed_data_list, efd_list)3922		ext4_free_data_in_buddy(sb, entry);3923 3924	if (test_opt(sb, DISCARD)) {3925		spin_lock(&sbi->s_md_lock);3926		wake = list_empty(&sbi->s_discard_list);3927		list_splice_tail(&freed_data_list, &sbi->s_discard_list);3928		spin_unlock(&sbi->s_md_lock);3929		if (wake)3930			queue_work(system_unbound_wq, &sbi->s_discard_work);3931	} else {3932		list_for_each_entry_safe(entry, tmp, &freed_data_list, efd_list)3933			kmem_cache_free(ext4_free_data_cachep, entry);3934	}3935}3936 3937int __init ext4_init_mballoc(void)3938{3939	ext4_pspace_cachep = KMEM_CACHE(ext4_prealloc_space,3940					SLAB_RECLAIM_ACCOUNT);3941	if (ext4_pspace_cachep == NULL)3942		goto out;3943 3944	ext4_ac_cachep = KMEM_CACHE(ext4_allocation_context,3945				    SLAB_RECLAIM_ACCOUNT);3946	if (ext4_ac_cachep == NULL)3947		goto out_pa_free;3948 3949	ext4_free_data_cachep = KMEM_CACHE(ext4_free_data,3950					   SLAB_RECLAIM_ACCOUNT);3951	if (ext4_free_data_cachep == NULL)3952		goto out_ac_free;3953 3954	return 0;3955 3956out_ac_free:3957	kmem_cache_destroy(ext4_ac_cachep);3958out_pa_free:3959	kmem_cache_destroy(ext4_pspace_cachep);3960out:3961	return -ENOMEM;3962}3963 3964void ext4_exit_mballoc(void)3965{3966	/*3967	 * Wait for completion of call_rcu()'s on ext4_pspace_cachep3968	 * before destroying the slab cache.3969	 */3970	rcu_barrier();3971	kmem_cache_destroy(ext4_pspace_cachep);3972	kmem_cache_destroy(ext4_ac_cachep);3973	kmem_cache_destroy(ext4_free_data_cachep);3974	ext4_groupinfo_destroy_slabs();3975}3976 3977#define EXT4_MB_BITMAP_MARKED_CHECK 0x00013978#define EXT4_MB_SYNC_UPDATE 0x00023979static int3980ext4_mb_mark_context(handle_t *handle, struct super_block *sb, bool state,3981		     ext4_group_t group, ext4_grpblk_t blkoff,3982		     ext4_grpblk_t len, int flags, ext4_grpblk_t *ret_changed)3983{3984	struct ext4_sb_info *sbi = EXT4_SB(sb);3985	struct buffer_head *bitmap_bh = NULL;3986	struct ext4_group_desc *gdp;3987	struct buffer_head *gdp_bh;3988	int err;3989	unsigned int i, already, changed = len;3990 3991	KUNIT_STATIC_STUB_REDIRECT(ext4_mb_mark_context,3992				   handle, sb, state, group, blkoff, len,3993				   flags, ret_changed);3994 3995	if (ret_changed)3996		*ret_changed = 0;3997	bitmap_bh = ext4_read_block_bitmap(sb, group);3998	if (IS_ERR(bitmap_bh))3999		return PTR_ERR(bitmap_bh);4000 4001	if (handle) {4002		BUFFER_TRACE(bitmap_bh, "getting write access");4003		err = ext4_journal_get_write_access(handle, sb, bitmap_bh,4004						    EXT4_JTR_NONE);4005		if (err)4006			goto out_err;4007	}4008 4009	err = -EIO;4010	gdp = ext4_get_group_desc(sb, group, &gdp_bh);4011	if (!gdp)4012		goto out_err;4013 4014	if (handle) {4015		BUFFER_TRACE(gdp_bh, "get_write_access");4016		err = ext4_journal_get_write_access(handle, sb, gdp_bh,4017						    EXT4_JTR_NONE);4018		if (err)4019			goto out_err;4020	}4021 4022	ext4_lock_group(sb, group);4023	if (ext4_has_group_desc_csum(sb) &&4024	    (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {4025		gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);4026		ext4_free_group_clusters_set(sb, gdp,4027			ext4_free_clusters_after_init(sb, group, gdp));4028	}4029 4030	if (flags & EXT4_MB_BITMAP_MARKED_CHECK) {4031		already = 0;4032		for (i = 0; i < len; i++)4033			if (mb_test_bit(blkoff + i, bitmap_bh->b_data) ==4034					state)4035				already++;4036		changed = len - already;4037	}4038 4039	if (state) {4040		mb_set_bits(bitmap_bh->b_data, blkoff, len);4041		ext4_free_group_clusters_set(sb, gdp,4042			ext4_free_group_clusters(sb, gdp) - changed);4043	} else {4044		mb_clear_bits(bitmap_bh->b_data, blkoff, len);4045		ext4_free_group_clusters_set(sb, gdp,4046			ext4_free_group_clusters(sb, gdp) + changed);4047	}4048 4049	ext4_block_bitmap_csum_set(sb, gdp, bitmap_bh);4050	ext4_group_desc_csum_set(sb, group, gdp);4051	ext4_unlock_group(sb, group);4052	if (ret_changed)4053		*ret_changed = changed;4054 4055	if (sbi->s_log_groups_per_flex) {4056		ext4_group_t flex_group = ext4_flex_group(sbi, group);4057		struct flex_groups *fg = sbi_array_rcu_deref(sbi,4058					   s_flex_groups, flex_group);4059 4060		if (state)4061			atomic64_sub(changed, &fg->free_clusters);4062		else4063			atomic64_add(changed, &fg->free_clusters);4064	}4065 4066	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);4067	if (err)4068		goto out_err;4069	err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);4070	if (err)4071		goto out_err;4072 4073	if (flags & EXT4_MB_SYNC_UPDATE) {4074		sync_dirty_buffer(bitmap_bh);4075		sync_dirty_buffer(gdp_bh);4076	}4077 4078out_err:4079	brelse(bitmap_bh);4080	return err;4081}4082 4083/*4084 * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps4085 * Returns 0 if success or error code4086 */4087static noinline_for_stack int4088ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,4089				handle_t *handle, unsigned int reserv_clstrs)4090{4091	struct ext4_group_desc *gdp;4092	struct ext4_sb_info *sbi;4093	struct super_block *sb;4094	ext4_fsblk_t block;4095	int err, len;4096	int flags = 0;4097	ext4_grpblk_t changed;4098 4099	BUG_ON(ac->ac_status != AC_STATUS_FOUND);4100	BUG_ON(ac->ac_b_ex.fe_len <= 0);4101 4102	sb = ac->ac_sb;4103	sbi = EXT4_SB(sb);4104 4105	gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, NULL);4106	if (!gdp)4107		return -EIO;4108	ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,4109			ext4_free_group_clusters(sb, gdp));4110 4111	block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);4112	len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);4113	if (!ext4_inode_block_valid(ac->ac_inode, block, len)) {4114		ext4_error(sb, "Allocating blocks %llu-%llu which overlap "4115			   "fs metadata", block, block+len);4116		/* File system mounted not to panic on error4117		 * Fix the bitmap and return EFSCORRUPTED4118		 * We leak some of the blocks here.4119		 */4120		err = ext4_mb_mark_context(handle, sb, true,4121					   ac->ac_b_ex.fe_group,4122					   ac->ac_b_ex.fe_start,4123					   ac->ac_b_ex.fe_len,4124					   0, NULL);4125		if (!err)4126			err = -EFSCORRUPTED;4127		return err;4128	}4129 4130#ifdef AGGRESSIVE_CHECK4131	flags |= EXT4_MB_BITMAP_MARKED_CHECK;4132#endif4133	err = ext4_mb_mark_context(handle, sb, true, ac->ac_b_ex.fe_group,4134				   ac->ac_b_ex.fe_start, ac->ac_b_ex.fe_len,4135				   flags, &changed);4136 4137	if (err && changed == 0)4138		return err;4139 4140#ifdef AGGRESSIVE_CHECK4141	BUG_ON(changed != ac->ac_b_ex.fe_len);4142#endif4143	percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);4144	/*4145	 * Now reduce the dirty block count also. Should not go negative4146	 */4147	if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))4148		/* release all the reserved blocks if non delalloc */4149		percpu_counter_sub(&sbi->s_dirtyclusters_counter,4150				   reserv_clstrs);4151 4152	return err;4153}4154 4155/*4156 * Idempotent helper for Ext4 fast commit replay path to set the state of4157 * blocks in bitmaps and update counters.4158 */4159void ext4_mb_mark_bb(struct super_block *sb, ext4_fsblk_t block,4160		     int len, bool state)4161{4162	struct ext4_sb_info *sbi = EXT4_SB(sb);4163	ext4_group_t group;4164	ext4_grpblk_t blkoff;4165	int err = 0;4166	unsigned int clen, thisgrp_len;4167 4168	while (len > 0) {4169		ext4_get_group_no_and_offset(sb, block, &group, &blkoff);4170 4171		/*4172		 * Check to see if we are freeing blocks across a group4173		 * boundary.4174		 * In case of flex_bg, this can happen that (block, len) may4175		 * span across more than one group. In that case we need to4176		 * get the corresponding group metadata to work with.4177		 * For this we have goto again loop.4178		 */4179		thisgrp_len = min_t(unsigned int, (unsigned int)len,4180			EXT4_BLOCKS_PER_GROUP(sb) - EXT4_C2B(sbi, blkoff));4181		clen = EXT4_NUM_B2C(sbi, thisgrp_len);4182 4183		if (!ext4_sb_block_valid(sb, NULL, block, thisgrp_len)) {4184			ext4_error(sb, "Marking blocks in system zone - "4185				   "Block = %llu, len = %u",4186				   block, thisgrp_len);4187			break;4188		}4189 4190		err = ext4_mb_mark_context(NULL, sb, state,4191					   group, blkoff, clen,4192					   EXT4_MB_BITMAP_MARKED_CHECK |4193					   EXT4_MB_SYNC_UPDATE,4194					   NULL);4195		if (err)4196			break;4197 4198		block += thisgrp_len;4199		len -= thisgrp_len;4200		BUG_ON(len < 0);4201	}4202}4203 4204/*4205 * here we normalize request for locality group4206 * Group request are normalized to s_mb_group_prealloc, which goes to4207 * s_strip if we set the same via mount option.4208 * s_mb_group_prealloc can be configured via4209 * /sys/fs/ext4/<partition>/mb_group_prealloc4210 *4211 * XXX: should we try to preallocate more than the group has now?4212 */4213static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)4214{4215	struct super_block *sb = ac->ac_sb;4216	struct ext4_locality_group *lg = ac->ac_lg;4217 4218	BUG_ON(lg == NULL);4219	ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;4220	mb_debug(sb, "goal %u blocks for locality group\n", ac->ac_g_ex.fe_len);4221}4222 4223/*4224 * This function returns the next element to look at during inode4225 * PA rbtree walk. We assume that we have held the inode PA rbtree lock4226 * (ei->i_prealloc_lock)4227 *4228 * new_start	The start of the range we want to compare4229 * cur_start	The existing start that we are comparing against4230 * node	The node of the rb_tree4231 */4232static inline struct rb_node*4233ext4_mb_pa_rb_next_iter(ext4_lblk_t new_start, ext4_lblk_t cur_start, struct rb_node *node)4234{4235	if (new_start < cur_start)4236		return node->rb_left;4237	else4238		return node->rb_right;4239}4240 4241static inline void4242ext4_mb_pa_assert_overlap(struct ext4_allocation_context *ac,4243			  ext4_lblk_t start, loff_t end)4244{4245	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4246	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);4247	struct ext4_prealloc_space *tmp_pa;4248	ext4_lblk_t tmp_pa_start;4249	loff_t tmp_pa_end;4250	struct rb_node *iter;4251 4252	read_lock(&ei->i_prealloc_lock);4253	for (iter = ei->i_prealloc_node.rb_node; iter;4254	     iter = ext4_mb_pa_rb_next_iter(start, tmp_pa_start, iter)) {4255		tmp_pa = rb_entry(iter, struct ext4_prealloc_space,4256				  pa_node.inode_node);4257		tmp_pa_start = tmp_pa->pa_lstart;4258		tmp_pa_end = pa_logical_end(sbi, tmp_pa);4259 4260		spin_lock(&tmp_pa->pa_lock);4261		if (tmp_pa->pa_deleted == 0)4262			BUG_ON(!(start >= tmp_pa_end || end <= tmp_pa_start));4263		spin_unlock(&tmp_pa->pa_lock);4264	}4265	read_unlock(&ei->i_prealloc_lock);4266}4267 4268/*4269 * Given an allocation context "ac" and a range "start", "end", check4270 * and adjust boundaries if the range overlaps with any of the existing4271 * preallocatoins stored in the corresponding inode of the allocation context.4272 *4273 * Parameters:4274 *	ac			allocation context4275 *	start			start of the new range4276 *	end			end of the new range4277 */4278static inline void4279ext4_mb_pa_adjust_overlap(struct ext4_allocation_context *ac,4280			  ext4_lblk_t *start, loff_t *end)4281{4282	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);4283	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4284	struct ext4_prealloc_space *tmp_pa = NULL, *left_pa = NULL, *right_pa = NULL;4285	struct rb_node *iter;4286	ext4_lblk_t new_start, tmp_pa_start, right_pa_start = -1;4287	loff_t new_end, tmp_pa_end, left_pa_end = -1;4288 4289	new_start = *start;4290	new_end = *end;4291 4292	/*4293	 * Adjust the normalized range so that it doesn't overlap with any4294	 * existing preallocated blocks(PAs). Make sure to hold the rbtree lock4295	 * so it doesn't change underneath us.4296	 */4297	read_lock(&ei->i_prealloc_lock);4298 4299	/* Step 1: find any one immediate neighboring PA of the normalized range */4300	for (iter = ei->i_prealloc_node.rb_node; iter;4301	     iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,4302					    tmp_pa_start, iter)) {4303		tmp_pa = rb_entry(iter, struct ext4_prealloc_space,4304				  pa_node.inode_node);4305		tmp_pa_start = tmp_pa->pa_lstart;4306		tmp_pa_end = pa_logical_end(sbi, tmp_pa);4307 4308		/* PA must not overlap original request */4309		spin_lock(&tmp_pa->pa_lock);4310		if (tmp_pa->pa_deleted == 0)4311			BUG_ON(!(ac->ac_o_ex.fe_logical >= tmp_pa_end ||4312				 ac->ac_o_ex.fe_logical < tmp_pa_start));4313		spin_unlock(&tmp_pa->pa_lock);4314	}4315 4316	/*4317	 * Step 2: check if the found PA is left or right neighbor and4318	 * get the other neighbor4319	 */4320	if (tmp_pa) {4321		if (tmp_pa->pa_lstart < ac->ac_o_ex.fe_logical) {4322			struct rb_node *tmp;4323 4324			left_pa = tmp_pa;4325			tmp = rb_next(&left_pa->pa_node.inode_node);4326			if (tmp) {4327				right_pa = rb_entry(tmp,4328						    struct ext4_prealloc_space,4329						    pa_node.inode_node);4330			}4331		} else {4332			struct rb_node *tmp;4333 4334			right_pa = tmp_pa;4335			tmp = rb_prev(&right_pa->pa_node.inode_node);4336			if (tmp) {4337				left_pa = rb_entry(tmp,4338						   struct ext4_prealloc_space,4339						   pa_node.inode_node);4340			}4341		}4342	}4343 4344	/* Step 3: get the non deleted neighbors */4345	if (left_pa) {4346		for (iter = &left_pa->pa_node.inode_node;;4347		     iter = rb_prev(iter)) {4348			if (!iter) {4349				left_pa = NULL;4350				break;4351			}4352 4353			tmp_pa = rb_entry(iter, struct ext4_prealloc_space,4354					  pa_node.inode_node);4355			left_pa = tmp_pa;4356			spin_lock(&tmp_pa->pa_lock);4357			if (tmp_pa->pa_deleted == 0) {4358				spin_unlock(&tmp_pa->pa_lock);4359				break;4360			}4361			spin_unlock(&tmp_pa->pa_lock);4362		}4363	}4364 4365	if (right_pa) {4366		for (iter = &right_pa->pa_node.inode_node;;4367		     iter = rb_next(iter)) {4368			if (!iter) {4369				right_pa = NULL;4370				break;4371			}4372 4373			tmp_pa = rb_entry(iter, struct ext4_prealloc_space,4374					  pa_node.inode_node);4375			right_pa = tmp_pa;4376			spin_lock(&tmp_pa->pa_lock);4377			if (tmp_pa->pa_deleted == 0) {4378				spin_unlock(&tmp_pa->pa_lock);4379				break;4380			}4381			spin_unlock(&tmp_pa->pa_lock);4382		}4383	}4384 4385	if (left_pa) {4386		left_pa_end = pa_logical_end(sbi, left_pa);4387		BUG_ON(left_pa_end > ac->ac_o_ex.fe_logical);4388	}4389 4390	if (right_pa) {4391		right_pa_start = right_pa->pa_lstart;4392		BUG_ON(right_pa_start <= ac->ac_o_ex.fe_logical);4393	}4394 4395	/* Step 4: trim our normalized range to not overlap with the neighbors */4396	if (left_pa) {4397		if (left_pa_end > new_start)4398			new_start = left_pa_end;4399	}4400 4401	if (right_pa) {4402		if (right_pa_start < new_end)4403			new_end = right_pa_start;4404	}4405	read_unlock(&ei->i_prealloc_lock);4406 4407	/* XXX: extra loop to check we really don't overlap preallocations */4408	ext4_mb_pa_assert_overlap(ac, new_start, new_end);4409 4410	*start = new_start;4411	*end = new_end;4412}4413 4414/*4415 * Normalization means making request better in terms of4416 * size and alignment4417 */4418static noinline_for_stack void4419ext4_mb_normalize_request(struct ext4_allocation_context *ac,4420				struct ext4_allocation_request *ar)4421{4422	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4423	struct ext4_super_block *es = sbi->s_es;4424	int bsbits, max;4425	loff_t size, start_off, end;4426	loff_t orig_size __maybe_unused;4427	ext4_lblk_t start;4428 4429	/* do normalize only data requests, metadata requests4430	   do not need preallocation */4431	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))4432		return;4433 4434	/* sometime caller may want exact blocks */4435	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))4436		return;4437 4438	/* caller may indicate that preallocation isn't4439	 * required (it's a tail, for example) */4440	if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)4441		return;4442 4443	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {4444		ext4_mb_normalize_group_request(ac);4445		return ;4446	}4447 4448	bsbits = ac->ac_sb->s_blocksize_bits;4449 4450	/* first, let's learn actual file size4451	 * given current request is allocated */4452	size = extent_logical_end(sbi, &ac->ac_o_ex);4453	size = size << bsbits;4454	if (size < i_size_read(ac->ac_inode))4455		size = i_size_read(ac->ac_inode);4456	orig_size = size;4457 4458	/* max size of free chunks */4459	max = 2 << bsbits;4460 4461#define NRL_CHECK_SIZE(req, size, max, chunk_size)	\4462		(req <= (size) || max <= (chunk_size))4463 4464	/* first, try to predict filesize */4465	/* XXX: should this table be tunable? */4466	start_off = 0;4467	if (size <= 16 * 1024) {4468		size = 16 * 1024;4469	} else if (size <= 32 * 1024) {4470		size = 32 * 1024;4471	} else if (size <= 64 * 1024) {4472		size = 64 * 1024;4473	} else if (size <= 128 * 1024) {4474		size = 128 * 1024;4475	} else if (size <= 256 * 1024) {4476		size = 256 * 1024;4477	} else if (size <= 512 * 1024) {4478		size = 512 * 1024;4479	} else if (size <= 1024 * 1024) {4480		size = 1024 * 1024;4481	} else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {4482		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>4483						(21 - bsbits)) << 21;4484		size = 2 * 1024 * 1024;4485	} else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {4486		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>4487							(22 - bsbits)) << 22;4488		size = 4 * 1024 * 1024;4489	} else if (NRL_CHECK_SIZE(EXT4_C2B(sbi, ac->ac_o_ex.fe_len),4490					(8<<20)>>bsbits, max, 8 * 1024)) {4491		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>4492							(23 - bsbits)) << 23;4493		size = 8 * 1024 * 1024;4494	} else {4495		start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;4496		size	  = (loff_t) EXT4_C2B(sbi,4497					      ac->ac_o_ex.fe_len) << bsbits;4498	}4499	size = size >> bsbits;4500	start = start_off >> bsbits;4501 4502	/*4503	 * For tiny groups (smaller than 8MB) the chosen allocation4504	 * alignment may be larger than group size. Make sure the4505	 * alignment does not move allocation to a different group which4506	 * makes mballoc fail assertions later.4507	 */4508	start = max(start, rounddown(ac->ac_o_ex.fe_logical,4509			(ext4_lblk_t)EXT4_BLOCKS_PER_GROUP(ac->ac_sb)));4510 4511	/* avoid unnecessary preallocation that may trigger assertions */4512	if (start + size > EXT_MAX_BLOCKS)4513		size = EXT_MAX_BLOCKS - start;4514 4515	/* don't cover already allocated blocks in selected range */4516	if (ar->pleft && start <= ar->lleft) {4517		size -= ar->lleft + 1 - start;4518		start = ar->lleft + 1;4519	}4520	if (ar->pright && start + size - 1 >= ar->lright)4521		size -= start + size - ar->lright;4522 4523	/*4524	 * Trim allocation request for filesystems with artificially small4525	 * groups.4526	 */4527	if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))4528		size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);4529 4530	end = start + size;4531 4532	ext4_mb_pa_adjust_overlap(ac, &start, &end);4533 4534	size = end - start;4535 4536	/*4537	 * In this function "start" and "size" are normalized for better4538	 * alignment and length such that we could preallocate more blocks.4539	 * This normalization is done such that original request of4540	 * ac->ac_o_ex.fe_logical & fe_len should always lie within "start" and4541	 * "size" boundaries.4542	 * (Note fe_len can be relaxed since FS block allocation API does not4543	 * provide gurantee on number of contiguous blocks allocation since that4544	 * depends upon free space left, etc).4545	 * In case of inode pa, later we use the allocated blocks4546	 * [pa_pstart + fe_logical - pa_lstart, fe_len/size] from the preallocated4547	 * range of goal/best blocks [start, size] to put it at the4548	 * ac_o_ex.fe_logical extent of this inode.4549	 * (See ext4_mb_use_inode_pa() for more details)4550	 */4551	if (start + size <= ac->ac_o_ex.fe_logical ||4552			start > ac->ac_o_ex.fe_logical) {4553		ext4_msg(ac->ac_sb, KERN_ERR,4554			 "start %lu, size %lu, fe_logical %lu",4555			 (unsigned long) start, (unsigned long) size,4556			 (unsigned long) ac->ac_o_ex.fe_logical);4557		BUG();4558	}4559	BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));4560 4561	/* now prepare goal request */4562 4563	/* XXX: is it better to align blocks WRT to logical4564	 * placement or satisfy big request as is */4565	ac->ac_g_ex.fe_logical = start;4566	ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);4567	ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;4568 4569	/* define goal start in order to merge */4570	if (ar->pright && (ar->lright == (start + size)) &&4571	    ar->pright >= size &&4572	    ar->pright - size >= le32_to_cpu(es->s_first_data_block)) {4573		/* merge to the right */4574		ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,4575						&ac->ac_g_ex.fe_group,4576						&ac->ac_g_ex.fe_start);4577		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;4578	}4579	if (ar->pleft && (ar->lleft + 1 == start) &&4580	    ar->pleft + 1 < ext4_blocks_count(es)) {4581		/* merge to the left */4582		ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,4583						&ac->ac_g_ex.fe_group,4584						&ac->ac_g_ex.fe_start);4585		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;4586	}4587 4588	mb_debug(ac->ac_sb, "goal: %lld(was %lld) blocks at %u\n", size,4589		 orig_size, start);4590}4591 4592static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)4593{4594	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4595 4596	if (sbi->s_mb_stats && ac->ac_g_ex.fe_len >= 1) {4597		atomic_inc(&sbi->s_bal_reqs);4598		atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);4599		if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)4600			atomic_inc(&sbi->s_bal_success);4601 4602		atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);4603		for (int i=0; i<EXT4_MB_NUM_CRS; i++) {4604			atomic_add(ac->ac_cX_found[i], &sbi->s_bal_cX_ex_scanned[i]);4605		}4606 4607		atomic_add(ac->ac_groups_scanned, &sbi->s_bal_groups_scanned);4608		if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&4609				ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)4610			atomic_inc(&sbi->s_bal_goals);4611		/* did we allocate as much as normalizer originally wanted? */4612		if (ac->ac_f_ex.fe_len == ac->ac_orig_goal_len)4613			atomic_inc(&sbi->s_bal_len_goals);4614 4615		if (ac->ac_found > sbi->s_mb_max_to_scan)4616			atomic_inc(&sbi->s_bal_breaks);4617	}4618 4619	if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)4620		trace_ext4_mballoc_alloc(ac);4621	else4622		trace_ext4_mballoc_prealloc(ac);4623}4624 4625/*4626 * Called on failure; free up any blocks from the inode PA for this4627 * context.  We don't need this for MB_GROUP_PA because we only change4628 * pa_free in ext4_mb_release_context(), but on failure, we've already4629 * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.4630 */4631static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac)4632{4633	struct ext4_prealloc_space *pa = ac->ac_pa;4634	struct ext4_buddy e4b;4635	int err;4636 4637	if (pa == NULL) {4638		if (ac->ac_f_ex.fe_len == 0)4639			return;4640		err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);4641		if (WARN_RATELIMIT(err,4642				   "ext4: mb_load_buddy failed (%d)", err))4643			/*4644			 * This should never happen since we pin the4645			 * pages in the ext4_allocation_context so4646			 * ext4_mb_load_buddy() should never fail.4647			 */4648			return;4649		ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);4650		mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,4651			       ac->ac_f_ex.fe_len);4652		ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);4653		ext4_mb_unload_buddy(&e4b);4654		return;4655	}4656	if (pa->pa_type == MB_INODE_PA) {4657		spin_lock(&pa->pa_lock);4658		pa->pa_free += ac->ac_b_ex.fe_len;4659		spin_unlock(&pa->pa_lock);4660	}4661}4662 4663/*4664 * use blocks preallocated to inode4665 */4666static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,4667				struct ext4_prealloc_space *pa)4668{4669	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4670	ext4_fsblk_t start;4671	ext4_fsblk_t end;4672	int len;4673 4674	/* found preallocated blocks, use them */4675	start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);4676	end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),4677		  start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));4678	len = EXT4_NUM_B2C(sbi, end - start);4679	ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,4680					&ac->ac_b_ex.fe_start);4681	ac->ac_b_ex.fe_len = len;4682	ac->ac_status = AC_STATUS_FOUND;4683	ac->ac_pa = pa;4684 4685	BUG_ON(start < pa->pa_pstart);4686	BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));4687	BUG_ON(pa->pa_free < len);4688	BUG_ON(ac->ac_b_ex.fe_len <= 0);4689	pa->pa_free -= len;4690 4691	mb_debug(ac->ac_sb, "use %llu/%d from inode pa %p\n", start, len, pa);4692}4693 4694/*4695 * use blocks preallocated to locality group4696 */4697static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,4698				struct ext4_prealloc_space *pa)4699{4700	unsigned int len = ac->ac_o_ex.fe_len;4701 4702	ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,4703					&ac->ac_b_ex.fe_group,4704					&ac->ac_b_ex.fe_start);4705	ac->ac_b_ex.fe_len = len;4706	ac->ac_status = AC_STATUS_FOUND;4707	ac->ac_pa = pa;4708 4709	/* we don't correct pa_pstart or pa_len here to avoid4710	 * possible race when the group is being loaded concurrently4711	 * instead we correct pa later, after blocks are marked4712	 * in on-disk bitmap -- see ext4_mb_release_context()4713	 * Other CPUs are prevented from allocating from this pa by lg_mutex4714	 */4715	mb_debug(ac->ac_sb, "use %u/%u from group pa %p\n",4716		 pa->pa_lstart, len, pa);4717}4718 4719/*4720 * Return the prealloc space that have minimal distance4721 * from the goal block. @cpa is the prealloc4722 * space that is having currently known minimal distance4723 * from the goal block.4724 */4725static struct ext4_prealloc_space *4726ext4_mb_check_group_pa(ext4_fsblk_t goal_block,4727			struct ext4_prealloc_space *pa,4728			struct ext4_prealloc_space *cpa)4729{4730	ext4_fsblk_t cur_distance, new_distance;4731 4732	if (cpa == NULL) {4733		atomic_inc(&pa->pa_count);4734		return pa;4735	}4736	cur_distance = abs(goal_block - cpa->pa_pstart);4737	new_distance = abs(goal_block - pa->pa_pstart);4738 4739	if (cur_distance <= new_distance)4740		return cpa;4741 4742	/* drop the previous reference */4743	atomic_dec(&cpa->pa_count);4744	atomic_inc(&pa->pa_count);4745	return pa;4746}4747 4748/*4749 * check if found pa meets EXT4_MB_HINT_GOAL_ONLY4750 */4751static bool4752ext4_mb_pa_goal_check(struct ext4_allocation_context *ac,4753		      struct ext4_prealloc_space *pa)4754{4755	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4756	ext4_fsblk_t start;4757 4758	if (likely(!(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)))4759		return true;4760 4761	/*4762	 * If EXT4_MB_HINT_GOAL_ONLY is set, ac_g_ex will not be adjusted4763	 * in ext4_mb_normalize_request and will keep same with ac_o_ex4764	 * from ext4_mb_initialize_context. Choose ac_g_ex here to keep4765	 * consistent with ext4_mb_find_by_goal.4766	 */4767	start = pa->pa_pstart +4768		(ac->ac_g_ex.fe_logical - pa->pa_lstart);4769	if (ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex) != start)4770		return false;4771 4772	if (ac->ac_g_ex.fe_len > pa->pa_len -4773	    EXT4_B2C(sbi, ac->ac_g_ex.fe_logical - pa->pa_lstart))4774		return false;4775 4776	return true;4777}4778 4779/*4780 * search goal blocks in preallocated space4781 */4782static noinline_for_stack bool4783ext4_mb_use_preallocated(struct ext4_allocation_context *ac)4784{4785	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);4786	int order, i;4787	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);4788	struct ext4_locality_group *lg;4789	struct ext4_prealloc_space *tmp_pa = NULL, *cpa = NULL;4790	struct rb_node *iter;4791	ext4_fsblk_t goal_block;4792 4793	/* only data can be preallocated */4794	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))4795		return false;4796 4797	/*4798	 * first, try per-file preallocation by searching the inode pa rbtree.4799	 *4800	 * Here, we can't do a direct traversal of the tree because4801	 * ext4_mb_discard_group_preallocation() can paralelly mark the pa4802	 * deleted and that can cause direct traversal to skip some entries.4803	 */4804	read_lock(&ei->i_prealloc_lock);4805 4806	if (RB_EMPTY_ROOT(&ei->i_prealloc_node)) {4807		goto try_group_pa;4808	}4809 4810	/*4811	 * Step 1: Find a pa with logical start immediately adjacent to the4812	 * original logical start. This could be on the left or right.4813	 *4814	 * (tmp_pa->pa_lstart never changes so we can skip locking for it).4815	 */4816	for (iter = ei->i_prealloc_node.rb_node; iter;4817	     iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,4818					    tmp_pa->pa_lstart, iter)) {4819		tmp_pa = rb_entry(iter, struct ext4_prealloc_space,4820				  pa_node.inode_node);4821	}4822 4823	/*4824	 * Step 2: The adjacent pa might be to the right of logical start, find4825	 * the left adjacent pa. After this step we'd have a valid tmp_pa whose4826	 * logical start is towards the left of original request's logical start4827	 */4828	if (tmp_pa->pa_lstart > ac->ac_o_ex.fe_logical) {4829		struct rb_node *tmp;4830		tmp = rb_prev(&tmp_pa->pa_node.inode_node);4831 4832		if (tmp) {4833			tmp_pa = rb_entry(tmp, struct ext4_prealloc_space,4834					    pa_node.inode_node);4835		} else {4836			/*4837			 * If there is no adjacent pa to the left then finding4838			 * an overlapping pa is not possible hence stop searching4839			 * inode pa tree4840			 */4841			goto try_group_pa;4842		}4843	}4844 4845	BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));4846 4847	/*4848	 * Step 3: If the left adjacent pa is deleted, keep moving left to find4849	 * the first non deleted adjacent pa. After this step we should have a4850	 * valid tmp_pa which is guaranteed to be non deleted.4851	 */4852	for (iter = &tmp_pa->pa_node.inode_node;; iter = rb_prev(iter)) {4853		if (!iter) {4854			/*4855			 * no non deleted left adjacent pa, so stop searching4856			 * inode pa tree4857			 */4858			goto try_group_pa;4859		}4860		tmp_pa = rb_entry(iter, struct ext4_prealloc_space,4861				  pa_node.inode_node);4862		spin_lock(&tmp_pa->pa_lock);4863		if (tmp_pa->pa_deleted == 0) {4864			/*4865			 * We will keep holding the pa_lock from4866			 * this point on because we don't want group discard4867			 * to delete this pa underneath us. Since group4868			 * discard is anyways an ENOSPC operation it4869			 * should be okay for it to wait a few more cycles.4870			 */4871			break;4872		} else {4873			spin_unlock(&tmp_pa->pa_lock);4874		}4875	}4876 4877	BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));4878	BUG_ON(tmp_pa->pa_deleted == 1);4879 4880	/*4881	 * Step 4: We now have the non deleted left adjacent pa. Only this4882	 * pa can possibly satisfy the request hence check if it overlaps4883	 * original logical start and stop searching if it doesn't.4884	 */4885	if (ac->ac_o_ex.fe_logical >= pa_logical_end(sbi, tmp_pa)) {4886		spin_unlock(&tmp_pa->pa_lock);4887		goto try_group_pa;4888	}4889 4890	/* non-extent files can't have physical blocks past 2^32 */4891	if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&4892	    (tmp_pa->pa_pstart + EXT4_C2B(sbi, tmp_pa->pa_len) >4893	     EXT4_MAX_BLOCK_FILE_PHYS)) {4894		/*4895		 * Since PAs don't overlap, we won't find any other PA to4896		 * satisfy this.4897		 */4898		spin_unlock(&tmp_pa->pa_lock);4899		goto try_group_pa;4900	}4901 4902	if (tmp_pa->pa_free && likely(ext4_mb_pa_goal_check(ac, tmp_pa))) {4903		atomic_inc(&tmp_pa->pa_count);4904		ext4_mb_use_inode_pa(ac, tmp_pa);4905		spin_unlock(&tmp_pa->pa_lock);4906		read_unlock(&ei->i_prealloc_lock);4907		return true;4908	} else {4909		/*4910		 * We found a valid overlapping pa but couldn't use it because4911		 * it had no free blocks. This should ideally never happen4912		 * because:4913		 *4914		 * 1. When a new inode pa is added to rbtree it must have4915		 *    pa_free > 0 since otherwise we won't actually need4916		 *    preallocation.4917		 *4918		 * 2. An inode pa that is in the rbtree can only have it's4919		 *    pa_free become zero when another thread calls:4920		 *      ext4_mb_new_blocks4921		 *       ext4_mb_use_preallocated4922		 *        ext4_mb_use_inode_pa4923		 *4924		 * 3. Further, after the above calls make pa_free == 0, we will4925		 *    immediately remove it from the rbtree in:4926		 *      ext4_mb_new_blocks4927		 *       ext4_mb_release_context4928		 *        ext4_mb_put_pa4929		 *4930		 * 4. Since the pa_free becoming 0 and pa_free getting removed4931		 * from tree both happen in ext4_mb_new_blocks, which is always4932		 * called with i_data_sem held for data allocations, we can be4933		 * sure that another process will never see a pa in rbtree with4934		 * pa_free == 0.4935		 */4936		WARN_ON_ONCE(tmp_pa->pa_free == 0);4937	}4938	spin_unlock(&tmp_pa->pa_lock);4939try_group_pa:4940	read_unlock(&ei->i_prealloc_lock);4941 4942	/* can we use group allocation? */4943	if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))4944		return false;4945 4946	/* inode may have no locality group for some reason */4947	lg = ac->ac_lg;4948	if (lg == NULL)4949		return false;4950	order  = fls(ac->ac_o_ex.fe_len) - 1;4951	if (order > PREALLOC_TB_SIZE - 1)4952		/* The max size of hash table is PREALLOC_TB_SIZE */4953		order = PREALLOC_TB_SIZE - 1;4954 4955	goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);4956	/*4957	 * search for the prealloc space that is having4958	 * minimal distance from the goal block.4959	 */4960	for (i = order; i < PREALLOC_TB_SIZE; i++) {4961		rcu_read_lock();4962		list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[i],4963					pa_node.lg_list) {4964			spin_lock(&tmp_pa->pa_lock);4965			if (tmp_pa->pa_deleted == 0 &&4966					tmp_pa->pa_free >= ac->ac_o_ex.fe_len) {4967 4968				cpa = ext4_mb_check_group_pa(goal_block,4969								tmp_pa, cpa);4970			}4971			spin_unlock(&tmp_pa->pa_lock);4972		}4973		rcu_read_unlock();4974	}4975	if (cpa) {4976		ext4_mb_use_group_pa(ac, cpa);4977		return true;4978	}4979	return false;4980}4981 4982/*4983 * the function goes through all preallocation in this group and marks them4984 * used in in-core bitmap. buddy must be generated from this bitmap4985 * Need to be called with ext4 group lock held4986 */4987static noinline_for_stack4988void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,4989					ext4_group_t group)4990{4991	struct ext4_group_info *grp = ext4_get_group_info(sb, group);4992	struct ext4_prealloc_space *pa;4993	struct list_head *cur;4994	ext4_group_t groupnr;4995	ext4_grpblk_t start;4996	int preallocated = 0;4997	int len;4998 4999	if (!grp)5000		return;5001 5002	/* all form of preallocation discards first load group,5003	 * so the only competing code is preallocation use.5004	 * we don't need any locking here5005	 * notice we do NOT ignore preallocations with pa_deleted5006	 * otherwise we could leave used blocks available for5007	 * allocation in buddy when concurrent ext4_mb_put_pa()5008	 * is dropping preallocation5009	 */5010	list_for_each(cur, &grp->bb_prealloc_list) {5011		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);5012		spin_lock(&pa->pa_lock);5013		ext4_get_group_no_and_offset(sb, pa->pa_pstart,5014					     &groupnr, &start);5015		len = pa->pa_len;5016		spin_unlock(&pa->pa_lock);5017		if (unlikely(len == 0))5018			continue;5019		BUG_ON(groupnr != group);5020		mb_set_bits(bitmap, start, len);5021		preallocated += len;5022	}5023	mb_debug(sb, "preallocated %d for group %u\n", preallocated, group);5024}5025 5026static void ext4_mb_mark_pa_deleted(struct super_block *sb,5027				    struct ext4_prealloc_space *pa)5028{5029	struct ext4_inode_info *ei;5030 5031	if (pa->pa_deleted) {5032		ext4_warning(sb, "deleted pa, type:%d, pblk:%llu, lblk:%u, len:%d\n",5033			     pa->pa_type, pa->pa_pstart, pa->pa_lstart,5034			     pa->pa_len);5035		return;5036	}5037 5038	pa->pa_deleted = 1;5039 5040	if (pa->pa_type == MB_INODE_PA) {5041		ei = EXT4_I(pa->pa_inode);5042		atomic_dec(&ei->i_prealloc_active);5043	}5044}5045 5046static inline void ext4_mb_pa_free(struct ext4_prealloc_space *pa)5047{5048	BUG_ON(!pa);5049	BUG_ON(atomic_read(&pa->pa_count));5050	BUG_ON(pa->pa_deleted == 0);5051	kmem_cache_free(ext4_pspace_cachep, pa);5052}5053 5054static void ext4_mb_pa_callback(struct rcu_head *head)5055{5056	struct ext4_prealloc_space *pa;5057 5058	pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);5059	ext4_mb_pa_free(pa);5060}5061 5062/*5063 * drops a reference to preallocated space descriptor5064 * if this was the last reference and the space is consumed5065 */5066static void ext4_mb_put_pa(struct ext4_allocation_context *ac,5067			struct super_block *sb, struct ext4_prealloc_space *pa)5068{5069	ext4_group_t grp;5070	ext4_fsblk_t grp_blk;5071	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);5072 5073	/* in this short window concurrent discard can set pa_deleted */5074	spin_lock(&pa->pa_lock);5075	if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {5076		spin_unlock(&pa->pa_lock);5077		return;5078	}5079 5080	if (pa->pa_deleted == 1) {5081		spin_unlock(&pa->pa_lock);5082		return;5083	}5084 5085	ext4_mb_mark_pa_deleted(sb, pa);5086	spin_unlock(&pa->pa_lock);5087 5088	grp_blk = pa->pa_pstart;5089	/*5090	 * If doing group-based preallocation, pa_pstart may be in the5091	 * next group when pa is used up5092	 */5093	if (pa->pa_type == MB_GROUP_PA)5094		grp_blk--;5095 5096	grp = ext4_get_group_number(sb, grp_blk);5097 5098	/*5099	 * possible race:5100	 *5101	 *  P1 (buddy init)			P2 (regular allocation)5102	 *					find block B in PA5103	 *  copy on-disk bitmap to buddy5104	 *  					mark B in on-disk bitmap5105	 *					drop PA from group5106	 *  mark all PAs in buddy5107	 *5108	 * thus, P1 initializes buddy with B available. to prevent this5109	 * we make "copy" and "mark all PAs" atomic and serialize "drop PA"5110	 * against that pair5111	 */5112	ext4_lock_group(sb, grp);5113	list_del(&pa->pa_group_list);5114	ext4_unlock_group(sb, grp);5115 5116	if (pa->pa_type == MB_INODE_PA) {5117		write_lock(pa->pa_node_lock.inode_lock);5118		rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);5119		write_unlock(pa->pa_node_lock.inode_lock);5120		ext4_mb_pa_free(pa);5121	} else {5122		spin_lock(pa->pa_node_lock.lg_lock);5123		list_del_rcu(&pa->pa_node.lg_list);5124		spin_unlock(pa->pa_node_lock.lg_lock);5125		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);5126	}5127}5128 5129static void ext4_mb_pa_rb_insert(struct rb_root *root, struct rb_node *new)5130{5131	struct rb_node **iter = &root->rb_node, *parent = NULL;5132	struct ext4_prealloc_space *iter_pa, *new_pa;5133	ext4_lblk_t iter_start, new_start;5134 5135	while (*iter) {5136		iter_pa = rb_entry(*iter, struct ext4_prealloc_space,5137				   pa_node.inode_node);5138		new_pa = rb_entry(new, struct ext4_prealloc_space,5139				   pa_node.inode_node);5140		iter_start = iter_pa->pa_lstart;5141		new_start = new_pa->pa_lstart;5142 5143		parent = *iter;5144		if (new_start < iter_start)5145			iter = &((*iter)->rb_left);5146		else5147			iter = &((*iter)->rb_right);5148	}5149 5150	rb_link_node(new, parent, iter);5151	rb_insert_color(new, root);5152}5153 5154/*5155 * creates new preallocated space for given inode5156 */5157static noinline_for_stack void5158ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)5159{5160	struct super_block *sb = ac->ac_sb;5161	struct ext4_sb_info *sbi = EXT4_SB(sb);5162	struct ext4_prealloc_space *pa;5163	struct ext4_group_info *grp;5164	struct ext4_inode_info *ei;5165 5166	/* preallocate only when found space is larger then requested */5167	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);5168	BUG_ON(ac->ac_status != AC_STATUS_FOUND);5169	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));5170	BUG_ON(ac->ac_pa == NULL);5171 5172	pa = ac->ac_pa;5173 5174	if (ac->ac_b_ex.fe_len < ac->ac_orig_goal_len) {5175		struct ext4_free_extent ex = {5176			.fe_logical = ac->ac_g_ex.fe_logical,5177			.fe_len = ac->ac_orig_goal_len,5178		};5179		loff_t orig_goal_end = extent_logical_end(sbi, &ex);5180		loff_t o_ex_end = extent_logical_end(sbi, &ac->ac_o_ex);5181 5182		/*5183		 * We can't allocate as much as normalizer wants, so we try5184		 * to get proper lstart to cover the original request, except5185		 * when the goal doesn't cover the original request as below:5186		 *5187		 * orig_ex:2045/2055(10), isize:8417280 -> normalized:0/20485188		 * best_ex:0/200(200) -> adjusted: 1848/2048(200)5189		 */5190		BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);5191		BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);5192 5193		/*5194		 * Use the below logic for adjusting best extent as it keeps5195		 * fragmentation in check while ensuring logical range of best5196		 * extent doesn't overflow out of goal extent:5197		 *5198		 * 1. Check if best ex can be kept at end of goal (before5199		 *    cr_best_avail trimmed it) and still cover original start5200		 * 2. Else, check if best ex can be kept at start of goal and5201		 *    still cover original end5202		 * 3. Else, keep the best ex at start of original request.5203		 */5204		ex.fe_len = ac->ac_b_ex.fe_len;5205 5206		ex.fe_logical = orig_goal_end - EXT4_C2B(sbi, ex.fe_len);5207		if (ac->ac_o_ex.fe_logical >= ex.fe_logical)5208			goto adjust_bex;5209 5210		ex.fe_logical = ac->ac_g_ex.fe_logical;5211		if (o_ex_end <= extent_logical_end(sbi, &ex))5212			goto adjust_bex;5213 5214		ex.fe_logical = ac->ac_o_ex.fe_logical;5215adjust_bex:5216		ac->ac_b_ex.fe_logical = ex.fe_logical;5217 5218		BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);5219		BUG_ON(extent_logical_end(sbi, &ex) > orig_goal_end);5220	}5221 5222	pa->pa_lstart = ac->ac_b_ex.fe_logical;5223	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);5224	pa->pa_len = ac->ac_b_ex.fe_len;5225	pa->pa_free = pa->pa_len;5226	spin_lock_init(&pa->pa_lock);5227	INIT_LIST_HEAD(&pa->pa_group_list);5228	pa->pa_deleted = 0;5229	pa->pa_type = MB_INODE_PA;5230 5231	mb_debug(sb, "new inode pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,5232		 pa->pa_len, pa->pa_lstart);5233	trace_ext4_mb_new_inode_pa(ac, pa);5234 5235	atomic_add(pa->pa_free, &sbi->s_mb_preallocated);5236	ext4_mb_use_inode_pa(ac, pa);5237 5238	ei = EXT4_I(ac->ac_inode);5239	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);5240	if (!grp)5241		return;5242 5243	pa->pa_node_lock.inode_lock = &ei->i_prealloc_lock;5244	pa->pa_inode = ac->ac_inode;5245 5246	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);5247 5248	write_lock(pa->pa_node_lock.inode_lock);5249	ext4_mb_pa_rb_insert(&ei->i_prealloc_node, &pa->pa_node.inode_node);5250	write_unlock(pa->pa_node_lock.inode_lock);5251	atomic_inc(&ei->i_prealloc_active);5252}5253 5254/*5255 * creates new preallocated space for locality group inodes belongs to5256 */5257static noinline_for_stack void5258ext4_mb_new_group_pa(struct ext4_allocation_context *ac)5259{5260	struct super_block *sb = ac->ac_sb;5261	struct ext4_locality_group *lg;5262	struct ext4_prealloc_space *pa;5263	struct ext4_group_info *grp;5264 5265	/* preallocate only when found space is larger then requested */5266	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);5267	BUG_ON(ac->ac_status != AC_STATUS_FOUND);5268	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));5269	BUG_ON(ac->ac_pa == NULL);5270 5271	pa = ac->ac_pa;5272 5273	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);5274	pa->pa_lstart = pa->pa_pstart;5275	pa->pa_len = ac->ac_b_ex.fe_len;5276	pa->pa_free = pa->pa_len;5277	spin_lock_init(&pa->pa_lock);5278	INIT_LIST_HEAD(&pa->pa_node.lg_list);5279	INIT_LIST_HEAD(&pa->pa_group_list);5280	pa->pa_deleted = 0;5281	pa->pa_type = MB_GROUP_PA;5282 5283	mb_debug(sb, "new group pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,5284		 pa->pa_len, pa->pa_lstart);5285	trace_ext4_mb_new_group_pa(ac, pa);5286 5287	ext4_mb_use_group_pa(ac, pa);5288	atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);5289 5290	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);5291	if (!grp)5292		return;5293	lg = ac->ac_lg;5294	BUG_ON(lg == NULL);5295 5296	pa->pa_node_lock.lg_lock = &lg->lg_prealloc_lock;5297	pa->pa_inode = NULL;5298 5299	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);5300 5301	/*5302	 * We will later add the new pa to the right bucket5303	 * after updating the pa_free in ext4_mb_release_context5304	 */5305}5306 5307static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac)5308{5309	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)5310		ext4_mb_new_group_pa(ac);5311	else5312		ext4_mb_new_inode_pa(ac);5313}5314 5315/*5316 * finds all unused blocks in on-disk bitmap, frees them in5317 * in-core bitmap and buddy.5318 * @pa must be unlinked from inode and group lists, so that5319 * nobody else can find/use it.5320 * the caller MUST hold group/inode locks.5321 * TODO: optimize the case when there are no in-core structures yet5322 */5323static noinline_for_stack void5324ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,5325			struct ext4_prealloc_space *pa)5326{5327	struct super_block *sb = e4b->bd_sb;5328	struct ext4_sb_info *sbi = EXT4_SB(sb);5329	unsigned int end;5330	unsigned int next;5331	ext4_group_t group;5332	ext4_grpblk_t bit;5333	unsigned long long grp_blk_start;5334	int free = 0;5335 5336	BUG_ON(pa->pa_deleted == 0);5337	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);5338	grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);5339	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);5340	end = bit + pa->pa_len;5341 5342	while (bit < end) {5343		bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);5344		if (bit >= end)5345			break;5346		next = mb_find_next_bit(bitmap_bh->b_data, end, bit);5347		mb_debug(sb, "free preallocated %u/%u in group %u\n",5348			 (unsigned) ext4_group_first_block_no(sb, group) + bit,5349			 (unsigned) next - bit, (unsigned) group);5350		free += next - bit;5351 5352		trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);5353		trace_ext4_mb_release_inode_pa(pa, (grp_blk_start +5354						    EXT4_C2B(sbi, bit)),5355					       next - bit);5356		mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);5357		bit = next + 1;5358	}5359	if (free != pa->pa_free) {5360		ext4_msg(e4b->bd_sb, KERN_CRIT,5361			 "pa %p: logic %lu, phys. %lu, len %d",5362			 pa, (unsigned long) pa->pa_lstart,5363			 (unsigned long) pa->pa_pstart,5364			 pa->pa_len);5365		ext4_grp_locked_error(sb, group, 0, 0, "free %u, pa_free %u",5366					free, pa->pa_free);5367		/*5368		 * pa is already deleted so we use the value obtained5369		 * from the bitmap and continue.5370		 */5371	}5372	atomic_add(free, &sbi->s_mb_discarded);5373}5374 5375static noinline_for_stack void5376ext4_mb_release_group_pa(struct ext4_buddy *e4b,5377				struct ext4_prealloc_space *pa)5378{5379	struct super_block *sb = e4b->bd_sb;5380	ext4_group_t group;5381	ext4_grpblk_t bit;5382 5383	trace_ext4_mb_release_group_pa(sb, pa);5384	BUG_ON(pa->pa_deleted == 0);5385	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);5386	if (unlikely(group != e4b->bd_group && pa->pa_len != 0)) {5387		ext4_warning(sb, "bad group: expected %u, group %u, pa_start %llu",5388			     e4b->bd_group, group, pa->pa_pstart);5389		return;5390	}5391	mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);5392	atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);5393	trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);5394}5395 5396/*5397 * releases all preallocations in given group5398 *5399 * first, we need to decide discard policy:5400 * - when do we discard5401 *   1) ENOSPC5402 * - how many do we discard5403 *   1) how many requested5404 */5405static noinline_for_stack int5406ext4_mb_discard_group_preallocations(struct super_block *sb,5407				     ext4_group_t group, int *busy)5408{5409	struct ext4_group_info *grp = ext4_get_group_info(sb, group);5410	struct buffer_head *bitmap_bh = NULL;5411	struct ext4_prealloc_space *pa, *tmp;5412	LIST_HEAD(list);5413	struct ext4_buddy e4b;5414	struct ext4_inode_info *ei;5415	int err;5416	int free = 0;5417 5418	if (!grp)5419		return 0;5420	mb_debug(sb, "discard preallocation for group %u\n", group);5421	if (list_empty(&grp->bb_prealloc_list))5422		goto out_dbg;5423 5424	bitmap_bh = ext4_read_block_bitmap(sb, group);5425	if (IS_ERR(bitmap_bh)) {5426		err = PTR_ERR(bitmap_bh);5427		ext4_error_err(sb, -err,5428			       "Error %d reading block bitmap for %u",5429			       err, group);5430		goto out_dbg;5431	}5432 5433	err = ext4_mb_load_buddy(sb, group, &e4b);5434	if (err) {5435		ext4_warning(sb, "Error %d loading buddy information for %u",5436			     err, group);5437		put_bh(bitmap_bh);5438		goto out_dbg;5439	}5440 5441	ext4_lock_group(sb, group);5442	list_for_each_entry_safe(pa, tmp,5443				&grp->bb_prealloc_list, pa_group_list) {5444		spin_lock(&pa->pa_lock);5445		if (atomic_read(&pa->pa_count)) {5446			spin_unlock(&pa->pa_lock);5447			*busy = 1;5448			continue;5449		}5450		if (pa->pa_deleted) {5451			spin_unlock(&pa->pa_lock);5452			continue;5453		}5454 5455		/* seems this one can be freed ... */5456		ext4_mb_mark_pa_deleted(sb, pa);5457 5458		if (!free)5459			this_cpu_inc(discard_pa_seq);5460 5461		/* we can trust pa_free ... */5462		free += pa->pa_free;5463 5464		spin_unlock(&pa->pa_lock);5465 5466		list_del(&pa->pa_group_list);5467		list_add(&pa->u.pa_tmp_list, &list);5468	}5469 5470	/* now free all selected PAs */5471	list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {5472 5473		/* remove from object (inode or locality group) */5474		if (pa->pa_type == MB_GROUP_PA) {5475			spin_lock(pa->pa_node_lock.lg_lock);5476			list_del_rcu(&pa->pa_node.lg_list);5477			spin_unlock(pa->pa_node_lock.lg_lock);5478		} else {5479			write_lock(pa->pa_node_lock.inode_lock);5480			ei = EXT4_I(pa->pa_inode);5481			rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);5482			write_unlock(pa->pa_node_lock.inode_lock);5483		}5484 5485		list_del(&pa->u.pa_tmp_list);5486 5487		if (pa->pa_type == MB_GROUP_PA) {5488			ext4_mb_release_group_pa(&e4b, pa);5489			call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);5490		} else {5491			ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);5492			ext4_mb_pa_free(pa);5493		}5494	}5495 5496	ext4_unlock_group(sb, group);5497	ext4_mb_unload_buddy(&e4b);5498	put_bh(bitmap_bh);5499out_dbg:5500	mb_debug(sb, "discarded (%d) blocks preallocated for group %u bb_free (%d)\n",5501		 free, group, grp->bb_free);5502	return free;5503}5504 5505/*5506 * releases all non-used preallocated blocks for given inode5507 *5508 * It's important to discard preallocations under i_data_sem5509 * We don't want another block to be served from the prealloc5510 * space when we are discarding the inode prealloc space.5511 *5512 * FIXME!! Make sure it is valid at all the call sites5513 */5514void ext4_discard_preallocations(struct inode *inode)5515{5516	struct ext4_inode_info *ei = EXT4_I(inode);5517	struct super_block *sb = inode->i_sb;5518	struct buffer_head *bitmap_bh = NULL;5519	struct ext4_prealloc_space *pa, *tmp;5520	ext4_group_t group = 0;5521	LIST_HEAD(list);5522	struct ext4_buddy e4b;5523	struct rb_node *iter;5524	int err;5525 5526	if (!S_ISREG(inode->i_mode))5527		return;5528 5529	if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)5530		return;5531 5532	mb_debug(sb, "discard preallocation for inode %lu\n",5533		 inode->i_ino);5534	trace_ext4_discard_preallocations(inode,5535			atomic_read(&ei->i_prealloc_active));5536 5537repeat:5538	/* first, collect all pa's in the inode */5539	write_lock(&ei->i_prealloc_lock);5540	for (iter = rb_first(&ei->i_prealloc_node); iter;5541	     iter = rb_next(iter)) {5542		pa = rb_entry(iter, struct ext4_prealloc_space,5543			      pa_node.inode_node);5544		BUG_ON(pa->pa_node_lock.inode_lock != &ei->i_prealloc_lock);5545 5546		spin_lock(&pa->pa_lock);5547		if (atomic_read(&pa->pa_count)) {5548			/* this shouldn't happen often - nobody should5549			 * use preallocation while we're discarding it */5550			spin_unlock(&pa->pa_lock);5551			write_unlock(&ei->i_prealloc_lock);5552			ext4_msg(sb, KERN_ERR,5553				 "uh-oh! used pa while discarding");5554			WARN_ON(1);5555			schedule_timeout_uninterruptible(HZ);5556			goto repeat;5557 5558		}5559		if (pa->pa_deleted == 0) {5560			ext4_mb_mark_pa_deleted(sb, pa);5561			spin_unlock(&pa->pa_lock);5562			rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);5563			list_add(&pa->u.pa_tmp_list, &list);5564			continue;5565		}5566 5567		/* someone is deleting pa right now */5568		spin_unlock(&pa->pa_lock);5569		write_unlock(&ei->i_prealloc_lock);5570 5571		/* we have to wait here because pa_deleted5572		 * doesn't mean pa is already unlinked from5573		 * the list. as we might be called from5574		 * ->clear_inode() the inode will get freed5575		 * and concurrent thread which is unlinking5576		 * pa from inode's list may access already5577		 * freed memory, bad-bad-bad */5578 5579		/* XXX: if this happens too often, we can5580		 * add a flag to force wait only in case5581		 * of ->clear_inode(), but not in case of5582		 * regular truncate */5583		schedule_timeout_uninterruptible(HZ);5584		goto repeat;5585	}5586	write_unlock(&ei->i_prealloc_lock);5587 5588	list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {5589		BUG_ON(pa->pa_type != MB_INODE_PA);5590		group = ext4_get_group_number(sb, pa->pa_pstart);5591 5592		err = ext4_mb_load_buddy_gfp(sb, group, &e4b,5593					     GFP_NOFS|__GFP_NOFAIL);5594		if (err) {5595			ext4_error_err(sb, -err, "Error %d loading buddy information for %u",5596				       err, group);5597			continue;5598		}5599 5600		bitmap_bh = ext4_read_block_bitmap(sb, group);5601		if (IS_ERR(bitmap_bh)) {5602			err = PTR_ERR(bitmap_bh);5603			ext4_error_err(sb, -err, "Error %d reading block bitmap for %u",5604				       err, group);5605			ext4_mb_unload_buddy(&e4b);5606			continue;5607		}5608 5609		ext4_lock_group(sb, group);5610		list_del(&pa->pa_group_list);5611		ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);5612		ext4_unlock_group(sb, group);5613 5614		ext4_mb_unload_buddy(&e4b);5615		put_bh(bitmap_bh);5616 5617		list_del(&pa->u.pa_tmp_list);5618		ext4_mb_pa_free(pa);5619	}5620}5621 5622static int ext4_mb_pa_alloc(struct ext4_allocation_context *ac)5623{5624	struct ext4_prealloc_space *pa;5625 5626	BUG_ON(ext4_pspace_cachep == NULL);5627	pa = kmem_cache_zalloc(ext4_pspace_cachep, GFP_NOFS);5628	if (!pa)5629		return -ENOMEM;5630	atomic_set(&pa->pa_count, 1);5631	ac->ac_pa = pa;5632	return 0;5633}5634 5635static void ext4_mb_pa_put_free(struct ext4_allocation_context *ac)5636{5637	struct ext4_prealloc_space *pa = ac->ac_pa;5638 5639	BUG_ON(!pa);5640	ac->ac_pa = NULL;5641	WARN_ON(!atomic_dec_and_test(&pa->pa_count));5642	/*5643	 * current function is only called due to an error or due to5644	 * len of found blocks < len of requested blocks hence the PA has not5645	 * been added to grp->bb_prealloc_list. So we don't need to lock it5646	 */5647	pa->pa_deleted = 1;5648	ext4_mb_pa_free(pa);5649}5650 5651#ifdef CONFIG_EXT4_DEBUG5652static inline void ext4_mb_show_pa(struct super_block *sb)5653{5654	ext4_group_t i, ngroups;5655 5656	if (ext4_forced_shutdown(sb))5657		return;5658 5659	ngroups = ext4_get_groups_count(sb);5660	mb_debug(sb, "groups: ");5661	for (i = 0; i < ngroups; i++) {5662		struct ext4_group_info *grp = ext4_get_group_info(sb, i);5663		struct ext4_prealloc_space *pa;5664		ext4_grpblk_t start;5665		struct list_head *cur;5666 5667		if (!grp)5668			continue;5669		ext4_lock_group(sb, i);5670		list_for_each(cur, &grp->bb_prealloc_list) {5671			pa = list_entry(cur, struct ext4_prealloc_space,5672					pa_group_list);5673			spin_lock(&pa->pa_lock);5674			ext4_get_group_no_and_offset(sb, pa->pa_pstart,5675						     NULL, &start);5676			spin_unlock(&pa->pa_lock);5677			mb_debug(sb, "PA:%u:%d:%d\n", i, start,5678				 pa->pa_len);5679		}5680		ext4_unlock_group(sb, i);5681		mb_debug(sb, "%u: %d/%d\n", i, grp->bb_free,5682			 grp->bb_fragments);5683	}5684}5685 5686static void ext4_mb_show_ac(struct ext4_allocation_context *ac)5687{5688	struct super_block *sb = ac->ac_sb;5689 5690	if (ext4_forced_shutdown(sb))5691		return;5692 5693	mb_debug(sb, "Can't allocate:"5694			" Allocation context details:");5695	mb_debug(sb, "status %u flags 0x%x",5696			ac->ac_status, ac->ac_flags);5697	mb_debug(sb, "orig %lu/%lu/%lu@%lu, "5698			"goal %lu/%lu/%lu@%lu, "5699			"best %lu/%lu/%lu@%lu cr %d",5700			(unsigned long)ac->ac_o_ex.fe_group,5701			(unsigned long)ac->ac_o_ex.fe_start,5702			(unsigned long)ac->ac_o_ex.fe_len,5703			(unsigned long)ac->ac_o_ex.fe_logical,5704			(unsigned long)ac->ac_g_ex.fe_group,5705			(unsigned long)ac->ac_g_ex.fe_start,5706			(unsigned long)ac->ac_g_ex.fe_len,5707			(unsigned long)ac->ac_g_ex.fe_logical,5708			(unsigned long)ac->ac_b_ex.fe_group,5709			(unsigned long)ac->ac_b_ex.fe_start,5710			(unsigned long)ac->ac_b_ex.fe_len,5711			(unsigned long)ac->ac_b_ex.fe_logical,5712			(int)ac->ac_criteria);5713	mb_debug(sb, "%u found", ac->ac_found);5714	mb_debug(sb, "used pa: %s, ", ac->ac_pa ? "yes" : "no");5715	if (ac->ac_pa)5716		mb_debug(sb, "pa_type %s\n", ac->ac_pa->pa_type == MB_GROUP_PA ?5717			 "group pa" : "inode pa");5718	ext4_mb_show_pa(sb);5719}5720#else5721static inline void ext4_mb_show_pa(struct super_block *sb)5722{5723}5724static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)5725{5726	ext4_mb_show_pa(ac->ac_sb);5727}5728#endif5729 5730/*5731 * We use locality group preallocation for small size file. The size of the5732 * file is determined by the current size or the resulting size after5733 * allocation which ever is larger5734 *5735 * One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req5736 */5737static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)5738{5739	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);5740	int bsbits = ac->ac_sb->s_blocksize_bits;5741	loff_t size, isize;5742	bool inode_pa_eligible, group_pa_eligible;5743 5744	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))5745		return;5746 5747	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))5748		return;5749 5750	group_pa_eligible = sbi->s_mb_group_prealloc > 0;5751	inode_pa_eligible = true;5752	size = extent_logical_end(sbi, &ac->ac_o_ex);5753	isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)5754		>> bsbits;5755 5756	/* No point in using inode preallocation for closed files */5757	if ((size == isize) && !ext4_fs_is_busy(sbi) &&5758	    !inode_is_open_for_write(ac->ac_inode))5759		inode_pa_eligible = false;5760 5761	size = max(size, isize);5762	/* Don't use group allocation for large files */5763	if (size > sbi->s_mb_stream_request)5764		group_pa_eligible = false;5765 5766	if (!group_pa_eligible) {5767		if (inode_pa_eligible)5768			ac->ac_flags |= EXT4_MB_STREAM_ALLOC;5769		else5770			ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;5771		return;5772	}5773 5774	BUG_ON(ac->ac_lg != NULL);5775	/*5776	 * locality group prealloc space are per cpu. The reason for having5777	 * per cpu locality group is to reduce the contention between block5778	 * request from multiple CPUs.5779	 */5780	ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);5781 5782	/* we're going to use group allocation */5783	ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;5784 5785	/* serialize all allocations in the group */5786	mutex_lock(&ac->ac_lg->lg_mutex);5787}5788 5789static noinline_for_stack void5790ext4_mb_initialize_context(struct ext4_allocation_context *ac,5791				struct ext4_allocation_request *ar)5792{5793	struct super_block *sb = ar->inode->i_sb;5794	struct ext4_sb_info *sbi = EXT4_SB(sb);5795	struct ext4_super_block *es = sbi->s_es;5796	ext4_group_t group;5797	unsigned int len;5798	ext4_fsblk_t goal;5799	ext4_grpblk_t block;5800 5801	/* we can't allocate > group size */5802	len = ar->len;5803 5804	/* just a dirty hack to filter too big requests  */5805	if (len >= EXT4_CLUSTERS_PER_GROUP(sb))5806		len = EXT4_CLUSTERS_PER_GROUP(sb);5807 5808	/* start searching from the goal */5809	goal = ar->goal;5810	if (goal < le32_to_cpu(es->s_first_data_block) ||5811			goal >= ext4_blocks_count(es))5812		goal = le32_to_cpu(es->s_first_data_block);5813	ext4_get_group_no_and_offset(sb, goal, &group, &block);5814 5815	/* set up allocation goals */5816	ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);5817	ac->ac_status = AC_STATUS_CONTINUE;5818	ac->ac_sb = sb;5819	ac->ac_inode = ar->inode;5820	ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;5821	ac->ac_o_ex.fe_group = group;5822	ac->ac_o_ex.fe_start = block;5823	ac->ac_o_ex.fe_len = len;5824	ac->ac_g_ex = ac->ac_o_ex;5825	ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;5826	ac->ac_flags = ar->flags;5827 5828	/* we have to define context: we'll work with a file or5829	 * locality group. this is a policy, actually */5830	ext4_mb_group_or_file(ac);5831 5832	mb_debug(sb, "init ac: %u blocks @ %u, goal %u, flags 0x%x, 2^%d, "5833			"left: %u/%u, right %u/%u to %swritable\n",5834			(unsigned) ar->len, (unsigned) ar->logical,5835			(unsigned) ar->goal, ac->ac_flags, ac->ac_2order,5836			(unsigned) ar->lleft, (unsigned) ar->pleft,5837			(unsigned) ar->lright, (unsigned) ar->pright,5838			inode_is_open_for_write(ar->inode) ? "" : "non-");5839}5840 5841static noinline_for_stack void5842ext4_mb_discard_lg_preallocations(struct super_block *sb,5843					struct ext4_locality_group *lg,5844					int order, int total_entries)5845{5846	ext4_group_t group = 0;5847	struct ext4_buddy e4b;5848	LIST_HEAD(discard_list);5849	struct ext4_prealloc_space *pa, *tmp;5850 5851	mb_debug(sb, "discard locality group preallocation\n");5852 5853	spin_lock(&lg->lg_prealloc_lock);5854	list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],5855				pa_node.lg_list,5856				lockdep_is_held(&lg->lg_prealloc_lock)) {5857		spin_lock(&pa->pa_lock);5858		if (atomic_read(&pa->pa_count)) {5859			/*5860			 * This is the pa that we just used5861			 * for block allocation. So don't5862			 * free that5863			 */5864			spin_unlock(&pa->pa_lock);5865			continue;5866		}5867		if (pa->pa_deleted) {5868			spin_unlock(&pa->pa_lock);5869			continue;5870		}5871		/* only lg prealloc space */5872		BUG_ON(pa->pa_type != MB_GROUP_PA);5873 5874		/* seems this one can be freed ... */5875		ext4_mb_mark_pa_deleted(sb, pa);5876		spin_unlock(&pa->pa_lock);5877 5878		list_del_rcu(&pa->pa_node.lg_list);5879		list_add(&pa->u.pa_tmp_list, &discard_list);5880 5881		total_entries--;5882		if (total_entries <= 5) {5883			/*5884			 * we want to keep only 5 entries5885			 * allowing it to grow to 8. This5886			 * mak sure we don't call discard5887			 * soon for this list.5888			 */5889			break;5890		}5891	}5892	spin_unlock(&lg->lg_prealloc_lock);5893 5894	list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {5895		int err;5896 5897		group = ext4_get_group_number(sb, pa->pa_pstart);5898		err = ext4_mb_load_buddy_gfp(sb, group, &e4b,5899					     GFP_NOFS|__GFP_NOFAIL);5900		if (err) {5901			ext4_error_err(sb, -err, "Error %d loading buddy information for %u",5902				       err, group);5903			continue;5904		}5905		ext4_lock_group(sb, group);5906		list_del(&pa->pa_group_list);5907		ext4_mb_release_group_pa(&e4b, pa);5908		ext4_unlock_group(sb, group);5909 5910		ext4_mb_unload_buddy(&e4b);5911		list_del(&pa->u.pa_tmp_list);5912		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);5913	}5914}5915 5916/*5917 * We have incremented pa_count. So it cannot be freed at this5918 * point. Also we hold lg_mutex. So no parallel allocation is5919 * possible from this lg. That means pa_free cannot be updated.5920 *5921 * A parallel ext4_mb_discard_group_preallocations is possible.5922 * which can cause the lg_prealloc_list to be updated.5923 */5924 5925static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)5926{5927	int order, added = 0, lg_prealloc_count = 1;5928	struct super_block *sb = ac->ac_sb;5929	struct ext4_locality_group *lg = ac->ac_lg;5930	struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;5931 5932	order = fls(pa->pa_free) - 1;5933	if (order > PREALLOC_TB_SIZE - 1)5934		/* The max size of hash table is PREALLOC_TB_SIZE */5935		order = PREALLOC_TB_SIZE - 1;5936	/* Add the prealloc space to lg */5937	spin_lock(&lg->lg_prealloc_lock);5938	list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],5939				pa_node.lg_list,5940				lockdep_is_held(&lg->lg_prealloc_lock)) {5941		spin_lock(&tmp_pa->pa_lock);5942		if (tmp_pa->pa_deleted) {5943			spin_unlock(&tmp_pa->pa_lock);5944			continue;5945		}5946		if (!added && pa->pa_free < tmp_pa->pa_free) {5947			/* Add to the tail of the previous entry */5948			list_add_tail_rcu(&pa->pa_node.lg_list,5949						&tmp_pa->pa_node.lg_list);5950			added = 1;5951			/*5952			 * we want to count the total5953			 * number of entries in the list5954			 */5955		}5956		spin_unlock(&tmp_pa->pa_lock);5957		lg_prealloc_count++;5958	}5959	if (!added)5960		list_add_tail_rcu(&pa->pa_node.lg_list,5961					&lg->lg_prealloc_list[order]);5962	spin_unlock(&lg->lg_prealloc_lock);5963 5964	/* Now trim the list to be not more than 8 elements */5965	if (lg_prealloc_count > 8)5966		ext4_mb_discard_lg_preallocations(sb, lg,5967						  order, lg_prealloc_count);5968}5969 5970/*5971 * release all resource we used in allocation5972 */5973static void ext4_mb_release_context(struct ext4_allocation_context *ac)5974{5975	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);5976	struct ext4_prealloc_space *pa = ac->ac_pa;5977	if (pa) {5978		if (pa->pa_type == MB_GROUP_PA) {5979			/* see comment in ext4_mb_use_group_pa() */5980			spin_lock(&pa->pa_lock);5981			pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);5982			pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);5983			pa->pa_free -= ac->ac_b_ex.fe_len;5984			pa->pa_len -= ac->ac_b_ex.fe_len;5985			spin_unlock(&pa->pa_lock);5986 5987			/*5988			 * We want to add the pa to the right bucket.5989			 * Remove it from the list and while adding5990			 * make sure the list to which we are adding5991			 * doesn't grow big.5992			 */5993			if (likely(pa->pa_free)) {5994				spin_lock(pa->pa_node_lock.lg_lock);5995				list_del_rcu(&pa->pa_node.lg_list);5996				spin_unlock(pa->pa_node_lock.lg_lock);5997				ext4_mb_add_n_trim(ac);5998			}5999		}6000 6001		ext4_mb_put_pa(ac, ac->ac_sb, pa);6002	}6003	if (ac->ac_bitmap_folio)6004		folio_put(ac->ac_bitmap_folio);6005	if (ac->ac_buddy_folio)6006		folio_put(ac->ac_buddy_folio);6007	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)6008		mutex_unlock(&ac->ac_lg->lg_mutex);6009	ext4_mb_collect_stats(ac);6010}6011 6012static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)6013{6014	ext4_group_t i, ngroups = ext4_get_groups_count(sb);6015	int ret;6016	int freed = 0, busy = 0;6017	int retry = 0;6018 6019	trace_ext4_mb_discard_preallocations(sb, needed);6020 6021	if (needed == 0)6022		needed = EXT4_CLUSTERS_PER_GROUP(sb) + 1;6023 repeat:6024	for (i = 0; i < ngroups && needed > 0; i++) {6025		ret = ext4_mb_discard_group_preallocations(sb, i, &busy);6026		freed += ret;6027		needed -= ret;6028		cond_resched();6029	}6030 6031	if (needed > 0 && busy && ++retry < 3) {6032		busy = 0;6033		goto repeat;6034	}6035 6036	return freed;6037}6038 6039static bool ext4_mb_discard_preallocations_should_retry(struct super_block *sb,6040			struct ext4_allocation_context *ac, u64 *seq)6041{6042	int freed;6043	u64 seq_retry = 0;6044	bool ret = false;6045 6046	freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);6047	if (freed) {6048		ret = true;6049		goto out_dbg;6050	}6051	seq_retry = ext4_get_discard_pa_seq_sum();6052	if (!(ac->ac_flags & EXT4_MB_STRICT_CHECK) || seq_retry != *seq) {6053		ac->ac_flags |= EXT4_MB_STRICT_CHECK;6054		*seq = seq_retry;6055		ret = true;6056	}6057 6058out_dbg:6059	mb_debug(sb, "freed %d, retry ? %s\n", freed, ret ? "yes" : "no");6060	return ret;6061}6062 6063/*6064 * Simple allocator for Ext4 fast commit replay path. It searches for blocks6065 * linearly starting at the goal block and also excludes the blocks which6066 * are going to be in use after fast commit replay.6067 */6068static ext4_fsblk_t6069ext4_mb_new_blocks_simple(struct ext4_allocation_request *ar, int *errp)6070{6071	struct buffer_head *bitmap_bh;6072	struct super_block *sb = ar->inode->i_sb;6073	struct ext4_sb_info *sbi = EXT4_SB(sb);6074	ext4_group_t group, nr;6075	ext4_grpblk_t blkoff;6076	ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);6077	ext4_grpblk_t i = 0;6078	ext4_fsblk_t goal, block;6079	struct ext4_super_block *es = sbi->s_es;6080 6081	goal = ar->goal;6082	if (goal < le32_to_cpu(es->s_first_data_block) ||6083			goal >= ext4_blocks_count(es))6084		goal = le32_to_cpu(es->s_first_data_block);6085 6086	ar->len = 0;6087	ext4_get_group_no_and_offset(sb, goal, &group, &blkoff);6088	for (nr = ext4_get_groups_count(sb); nr > 0; nr--) {6089		bitmap_bh = ext4_read_block_bitmap(sb, group);6090		if (IS_ERR(bitmap_bh)) {6091			*errp = PTR_ERR(bitmap_bh);6092			pr_warn("Failed to read block bitmap\n");6093			return 0;6094		}6095 6096		while (1) {6097			i = mb_find_next_zero_bit(bitmap_bh->b_data, max,6098						blkoff);6099			if (i >= max)6100				break;6101			if (ext4_fc_replay_check_excluded(sb,6102				ext4_group_first_block_no(sb, group) +6103				EXT4_C2B(sbi, i))) {6104				blkoff = i + 1;6105			} else6106				break;6107		}6108		brelse(bitmap_bh);6109		if (i < max)6110			break;6111 6112		if (++group >= ext4_get_groups_count(sb))6113			group = 0;6114 6115		blkoff = 0;6116	}6117 6118	if (i >= max) {6119		*errp = -ENOSPC;6120		return 0;6121	}6122 6123	block = ext4_group_first_block_no(sb, group) + EXT4_C2B(sbi, i);6124	ext4_mb_mark_bb(sb, block, 1, true);6125	ar->len = 1;6126 6127	*errp = 0;6128	return block;6129}6130 6131/*6132 * Main entry point into mballoc to allocate blocks6133 * it tries to use preallocation first, then falls back6134 * to usual allocation6135 */6136ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,6137				struct ext4_allocation_request *ar, int *errp)6138{6139	struct ext4_allocation_context *ac = NULL;6140	struct ext4_sb_info *sbi;6141	struct super_block *sb;6142	ext4_fsblk_t block = 0;6143	unsigned int inquota = 0;6144	unsigned int reserv_clstrs = 0;6145	int retries = 0;6146	u64 seq;6147 6148	might_sleep();6149	sb = ar->inode->i_sb;6150	sbi = EXT4_SB(sb);6151 6152	trace_ext4_request_blocks(ar);6153	if (sbi->s_mount_state & EXT4_FC_REPLAY)6154		return ext4_mb_new_blocks_simple(ar, errp);6155 6156	/* Allow to use superuser reservation for quota file */6157	if (ext4_is_quota_file(ar->inode))6158		ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;6159 6160	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {6161		/* Without delayed allocation we need to verify6162		 * there is enough free blocks to do block allocation6163		 * and verify allocation doesn't exceed the quota limits.6164		 */6165		while (ar->len &&6166			ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {6167 6168			/* let others to free the space */6169			cond_resched();6170			ar->len = ar->len >> 1;6171		}6172		if (!ar->len) {6173			ext4_mb_show_pa(sb);6174			*errp = -ENOSPC;6175			return 0;6176		}6177		reserv_clstrs = ar->len;6178		if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {6179			dquot_alloc_block_nofail(ar->inode,6180						 EXT4_C2B(sbi, ar->len));6181		} else {6182			while (ar->len &&6183				dquot_alloc_block(ar->inode,6184						  EXT4_C2B(sbi, ar->len))) {6185 6186				ar->flags |= EXT4_MB_HINT_NOPREALLOC;6187				ar->len--;6188			}6189		}6190		inquota = ar->len;6191		if (ar->len == 0) {6192			*errp = -EDQUOT;6193			goto out;6194		}6195	}6196 6197	ac = kmem_cache_zalloc(ext4_ac_cachep, GFP_NOFS);6198	if (!ac) {6199		ar->len = 0;6200		*errp = -ENOMEM;6201		goto out;6202	}6203 6204	ext4_mb_initialize_context(ac, ar);6205 6206	ac->ac_op = EXT4_MB_HISTORY_PREALLOC;6207	seq = this_cpu_read(discard_pa_seq);6208	if (!ext4_mb_use_preallocated(ac)) {6209		ac->ac_op = EXT4_MB_HISTORY_ALLOC;6210		ext4_mb_normalize_request(ac, ar);6211 6212		*errp = ext4_mb_pa_alloc(ac);6213		if (*errp)6214			goto errout;6215repeat:6216		/* allocate space in core */6217		*errp = ext4_mb_regular_allocator(ac);6218		/*6219		 * pa allocated above is added to grp->bb_prealloc_list only6220		 * when we were able to allocate some block i.e. when6221		 * ac->ac_status == AC_STATUS_FOUND.6222		 * And error from above mean ac->ac_status != AC_STATUS_FOUND6223		 * So we have to free this pa here itself.6224		 */6225		if (*errp) {6226			ext4_mb_pa_put_free(ac);6227			ext4_discard_allocated_blocks(ac);6228			goto errout;6229		}6230		if (ac->ac_status == AC_STATUS_FOUND &&6231			ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)6232			ext4_mb_pa_put_free(ac);6233	}6234	if (likely(ac->ac_status == AC_STATUS_FOUND)) {6235		*errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs);6236		if (*errp) {6237			ext4_discard_allocated_blocks(ac);6238			goto errout;6239		} else {6240			block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);6241			ar->len = ac->ac_b_ex.fe_len;6242		}6243	} else {6244		if (++retries < 3 &&6245		    ext4_mb_discard_preallocations_should_retry(sb, ac, &seq))6246			goto repeat;6247		/*6248		 * If block allocation fails then the pa allocated above6249		 * needs to be freed here itself.6250		 */6251		ext4_mb_pa_put_free(ac);6252		*errp = -ENOSPC;6253	}6254 6255	if (*errp) {6256errout:6257		ac->ac_b_ex.fe_len = 0;6258		ar->len = 0;6259		ext4_mb_show_ac(ac);6260	}6261	ext4_mb_release_context(ac);6262	kmem_cache_free(ext4_ac_cachep, ac);6263out:6264	if (inquota && ar->len < inquota)6265		dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));6266	if (!ar->len) {6267		if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)6268			/* release all the reserved blocks if non delalloc */6269			percpu_counter_sub(&sbi->s_dirtyclusters_counter,6270						reserv_clstrs);6271	}6272 6273	trace_ext4_allocate_blocks(ar, (unsigned long long)block);6274 6275	return block;6276}6277 6278/*6279 * We can merge two free data extents only if the physical blocks6280 * are contiguous, AND the extents were freed by the same transaction,6281 * AND the blocks are associated with the same group.6282 */6283static void ext4_try_merge_freed_extent(struct ext4_sb_info *sbi,6284					struct ext4_free_data *entry,6285					struct ext4_free_data *new_entry,6286					struct rb_root *entry_rb_root)6287{6288	if ((entry->efd_tid != new_entry->efd_tid) ||6289	    (entry->efd_group != new_entry->efd_group))6290		return;6291	if (entry->efd_start_cluster + entry->efd_count ==6292	    new_entry->efd_start_cluster) {6293		new_entry->efd_start_cluster = entry->efd_start_cluster;6294		new_entry->efd_count += entry->efd_count;6295	} else if (new_entry->efd_start_cluster + new_entry->efd_count ==6296		   entry->efd_start_cluster) {6297		new_entry->efd_count += entry->efd_count;6298	} else6299		return;6300	spin_lock(&sbi->s_md_lock);6301	list_del(&entry->efd_list);6302	spin_unlock(&sbi->s_md_lock);6303	rb_erase(&entry->efd_node, entry_rb_root);6304	kmem_cache_free(ext4_free_data_cachep, entry);6305}6306 6307static noinline_for_stack void6308ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,6309		      struct ext4_free_data *new_entry)6310{6311	ext4_group_t group = e4b->bd_group;6312	ext4_grpblk_t cluster;6313	ext4_grpblk_t clusters = new_entry->efd_count;6314	struct ext4_free_data *entry;6315	struct ext4_group_info *db = e4b->bd_info;6316	struct super_block *sb = e4b->bd_sb;6317	struct ext4_sb_info *sbi = EXT4_SB(sb);6318	struct rb_node **n = &db->bb_free_root.rb_node, *node;6319	struct rb_node *parent = NULL, *new_node;6320 6321	BUG_ON(!ext4_handle_valid(handle));6322	BUG_ON(e4b->bd_bitmap_folio == NULL);6323	BUG_ON(e4b->bd_buddy_folio == NULL);6324 6325	new_node = &new_entry->efd_node;6326	cluster = new_entry->efd_start_cluster;6327 6328	if (!*n) {6329		/* first free block exent. We need to6330		   protect buddy cache from being freed,6331		 * otherwise we'll refresh it from6332		 * on-disk bitmap and lose not-yet-available6333		 * blocks */6334		folio_get(e4b->bd_buddy_folio);6335		folio_get(e4b->bd_bitmap_folio);6336	}6337	while (*n) {6338		parent = *n;6339		entry = rb_entry(parent, struct ext4_free_data, efd_node);6340		if (cluster < entry->efd_start_cluster)6341			n = &(*n)->rb_left;6342		else if (cluster >= (entry->efd_start_cluster + entry->efd_count))6343			n = &(*n)->rb_right;6344		else {6345			ext4_grp_locked_error(sb, group, 0,6346				ext4_group_first_block_no(sb, group) +6347				EXT4_C2B(sbi, cluster),6348				"Block already on to-be-freed list");6349			kmem_cache_free(ext4_free_data_cachep, new_entry);6350			return;6351		}6352	}6353 6354	rb_link_node(new_node, parent, n);6355	rb_insert_color(new_node, &db->bb_free_root);6356 6357	/* Now try to see the extent can be merged to left and right */6358	node = rb_prev(new_node);6359	if (node) {6360		entry = rb_entry(node, struct ext4_free_data, efd_node);6361		ext4_try_merge_freed_extent(sbi, entry, new_entry,6362					    &(db->bb_free_root));6363	}6364 6365	node = rb_next(new_node);6366	if (node) {6367		entry = rb_entry(node, struct ext4_free_data, efd_node);6368		ext4_try_merge_freed_extent(sbi, entry, new_entry,6369					    &(db->bb_free_root));6370	}6371 6372	spin_lock(&sbi->s_md_lock);6373	list_add_tail(&new_entry->efd_list, &sbi->s_freed_data_list[new_entry->efd_tid & 1]);6374	sbi->s_mb_free_pending += clusters;6375	spin_unlock(&sbi->s_md_lock);6376}6377 6378static void ext4_free_blocks_simple(struct inode *inode, ext4_fsblk_t block,6379					unsigned long count)6380{6381	struct super_block *sb = inode->i_sb;6382	ext4_group_t group;6383	ext4_grpblk_t blkoff;6384 6385	ext4_get_group_no_and_offset(sb, block, &group, &blkoff);6386	ext4_mb_mark_context(NULL, sb, false, group, blkoff, count,6387			     EXT4_MB_BITMAP_MARKED_CHECK |6388			     EXT4_MB_SYNC_UPDATE,6389			     NULL);6390}6391 6392/**6393 * ext4_mb_clear_bb() -- helper function for freeing blocks.6394 *			Used by ext4_free_blocks()6395 * @handle:		handle for this transaction6396 * @inode:		inode6397 * @block:		starting physical block to be freed6398 * @count:		number of blocks to be freed6399 * @flags:		flags used by ext4_free_blocks6400 */6401static void ext4_mb_clear_bb(handle_t *handle, struct inode *inode,6402			       ext4_fsblk_t block, unsigned long count,6403			       int flags)6404{6405	struct super_block *sb = inode->i_sb;6406	struct ext4_group_info *grp;6407	unsigned int overflow;6408	ext4_grpblk_t bit;6409	ext4_group_t block_group;6410	struct ext4_sb_info *sbi;6411	struct ext4_buddy e4b;6412	unsigned int count_clusters;6413	int err = 0;6414	int mark_flags = 0;6415	ext4_grpblk_t changed;6416 6417	sbi = EXT4_SB(sb);6418 6419	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&6420	    !ext4_inode_block_valid(inode, block, count)) {6421		ext4_error(sb, "Freeing blocks in system zone - "6422			   "Block = %llu, count = %lu", block, count);6423		/* err = 0. ext4_std_error should be a no op */6424		goto error_out;6425	}6426	flags |= EXT4_FREE_BLOCKS_VALIDATED;6427 6428do_more:6429	overflow = 0;6430	ext4_get_group_no_and_offset(sb, block, &block_group, &bit);6431 6432	grp = ext4_get_group_info(sb, block_group);6433	if (unlikely(!grp || EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))6434		return;6435 6436	/*6437	 * Check to see if we are freeing blocks across a group6438	 * boundary.6439	 */6440	if (EXT4_C2B(sbi, bit) + count > EXT4_BLOCKS_PER_GROUP(sb)) {6441		overflow = EXT4_C2B(sbi, bit) + count -6442			EXT4_BLOCKS_PER_GROUP(sb);6443		count -= overflow;6444		/* The range changed so it's no longer validated */6445		flags &= ~EXT4_FREE_BLOCKS_VALIDATED;6446	}6447	count_clusters = EXT4_NUM_B2C(sbi, count);6448	trace_ext4_mballoc_free(sb, inode, block_group, bit, count_clusters);6449 6450	/* __GFP_NOFAIL: retry infinitely, ignore TIF_MEMDIE and memcg limit. */6451	err = ext4_mb_load_buddy_gfp(sb, block_group, &e4b,6452				     GFP_NOFS|__GFP_NOFAIL);6453	if (err)6454		goto error_out;6455 6456	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&6457	    !ext4_inode_block_valid(inode, block, count)) {6458		ext4_error(sb, "Freeing blocks in system zone - "6459			   "Block = %llu, count = %lu", block, count);6460		/* err = 0. ext4_std_error should be a no op */6461		goto error_clean;6462	}6463 6464#ifdef AGGRESSIVE_CHECK6465	mark_flags |= EXT4_MB_BITMAP_MARKED_CHECK;6466#endif6467	err = ext4_mb_mark_context(handle, sb, false, block_group, bit,6468				   count_clusters, mark_flags, &changed);6469 6470 6471	if (err && changed == 0)6472		goto error_clean;6473 6474#ifdef AGGRESSIVE_CHECK6475	BUG_ON(changed != count_clusters);6476#endif6477 6478	/*6479	 * We need to make sure we don't reuse the freed block until after the6480	 * transaction is committed. We make an exception if the inode is to be6481	 * written in writeback mode since writeback mode has weak data6482	 * consistency guarantees.6483	 */6484	if (ext4_handle_valid(handle) &&6485	    ((flags & EXT4_FREE_BLOCKS_METADATA) ||6486	     !ext4_should_writeback_data(inode))) {6487		struct ext4_free_data *new_entry;6488		/*6489		 * We use __GFP_NOFAIL because ext4_free_blocks() is not allowed6490		 * to fail.6491		 */6492		new_entry = kmem_cache_alloc(ext4_free_data_cachep,6493				GFP_NOFS|__GFP_NOFAIL);6494		new_entry->efd_start_cluster = bit;6495		new_entry->efd_group = block_group;6496		new_entry->efd_count = count_clusters;6497		new_entry->efd_tid = handle->h_transaction->t_tid;6498 6499		ext4_lock_group(sb, block_group);6500		ext4_mb_free_metadata(handle, &e4b, new_entry);6501	} else {6502		if (test_opt(sb, DISCARD)) {6503			err = ext4_issue_discard(sb, block_group, bit,6504						 count_clusters);6505			/*6506			 * Ignore EOPNOTSUPP error. This is consistent with6507			 * what happens when using journal.6508			 */6509			if (err == -EOPNOTSUPP)6510				err = 0;6511			if (err)6512				ext4_msg(sb, KERN_WARNING, "discard request in"6513					 " group:%u block:%d count:%lu failed"6514					 " with %d", block_group, bit, count,6515					 err);6516		}6517 6518		EXT4_MB_GRP_CLEAR_TRIMMED(e4b.bd_info);6519 6520		ext4_lock_group(sb, block_group);6521		mb_free_blocks(inode, &e4b, bit, count_clusters);6522	}6523 6524	ext4_unlock_group(sb, block_group);6525 6526	/*6527	 * on a bigalloc file system, defer the s_freeclusters_counter6528	 * update to the caller (ext4_remove_space and friends) so they6529	 * can determine if a cluster freed here should be rereserved6530	 */6531	if (!(flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)) {6532		if (!(flags & EXT4_FREE_BLOCKS_NO_QUOT_UPDATE))6533			dquot_free_block(inode, EXT4_C2B(sbi, count_clusters));6534		percpu_counter_add(&sbi->s_freeclusters_counter,6535				   count_clusters);6536	}6537 6538	if (overflow && !err) {6539		block += count;6540		count = overflow;6541		ext4_mb_unload_buddy(&e4b);6542		/* The range changed so it's no longer validated */6543		flags &= ~EXT4_FREE_BLOCKS_VALIDATED;6544		goto do_more;6545	}6546 6547error_clean:6548	ext4_mb_unload_buddy(&e4b);6549error_out:6550	ext4_std_error(sb, err);6551}6552 6553/**6554 * ext4_free_blocks() -- Free given blocks and update quota6555 * @handle:		handle for this transaction6556 * @inode:		inode6557 * @bh:			optional buffer of the block to be freed6558 * @block:		starting physical block to be freed6559 * @count:		number of blocks to be freed6560 * @flags:		flags used by ext4_free_blocks6561 */6562void ext4_free_blocks(handle_t *handle, struct inode *inode,6563		      struct buffer_head *bh, ext4_fsblk_t block,6564		      unsigned long count, int flags)6565{6566	struct super_block *sb = inode->i_sb;6567	unsigned int overflow;6568	struct ext4_sb_info *sbi;6569 6570	sbi = EXT4_SB(sb);6571 6572	if (bh) {6573		if (block)6574			BUG_ON(block != bh->b_blocknr);6575		else6576			block = bh->b_blocknr;6577	}6578 6579	if (sbi->s_mount_state & EXT4_FC_REPLAY) {6580		ext4_free_blocks_simple(inode, block, EXT4_NUM_B2C(sbi, count));6581		return;6582	}6583 6584	might_sleep();6585 6586	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&6587	    !ext4_inode_block_valid(inode, block, count)) {6588		ext4_error(sb, "Freeing blocks not in datazone - "6589			   "block = %llu, count = %lu", block, count);6590		return;6591	}6592	flags |= EXT4_FREE_BLOCKS_VALIDATED;6593 6594	ext4_debug("freeing block %llu\n", block);6595	trace_ext4_free_blocks(inode, block, count, flags);6596 6597	if (bh && (flags & EXT4_FREE_BLOCKS_FORGET)) {6598		BUG_ON(count > 1);6599 6600		ext4_forget(handle, flags & EXT4_FREE_BLOCKS_METADATA,6601			    inode, bh, block);6602	}6603 6604	/*6605	 * If the extent to be freed does not begin on a cluster6606	 * boundary, we need to deal with partial clusters at the6607	 * beginning and end of the extent.  Normally we will free6608	 * blocks at the beginning or the end unless we are explicitly6609	 * requested to avoid doing so.6610	 */6611	overflow = EXT4_PBLK_COFF(sbi, block);6612	if (overflow) {6613		if (flags & EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER) {6614			overflow = sbi->s_cluster_ratio - overflow;6615			block += overflow;6616			if (count > overflow)6617				count -= overflow;6618			else6619				return;6620		} else {6621			block -= overflow;6622			count += overflow;6623		}6624		/* The range changed so it's no longer validated */6625		flags &= ~EXT4_FREE_BLOCKS_VALIDATED;6626	}6627	overflow = EXT4_LBLK_COFF(sbi, count);6628	if (overflow) {6629		if (flags & EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER) {6630			if (count > overflow)6631				count -= overflow;6632			else6633				return;6634		} else6635			count += sbi->s_cluster_ratio - overflow;6636		/* The range changed so it's no longer validated */6637		flags &= ~EXT4_FREE_BLOCKS_VALIDATED;6638	}6639 6640	if (!bh && (flags & EXT4_FREE_BLOCKS_FORGET)) {6641		int i;6642		int is_metadata = flags & EXT4_FREE_BLOCKS_METADATA;6643 6644		for (i = 0; i < count; i++) {6645			cond_resched();6646			if (is_metadata)6647				bh = sb_find_get_block(inode->i_sb, block + i);6648			ext4_forget(handle, is_metadata, inode, bh, block + i);6649		}6650	}6651 6652	ext4_mb_clear_bb(handle, inode, block, count, flags);6653}6654 6655/**6656 * ext4_group_add_blocks() -- Add given blocks to an existing group6657 * @handle:			handle to this transaction6658 * @sb:				super block6659 * @block:			start physical block to add to the block group6660 * @count:			number of blocks to free6661 *6662 * This marks the blocks as free in the bitmap and buddy.6663 */6664int ext4_group_add_blocks(handle_t *handle, struct super_block *sb,6665			 ext4_fsblk_t block, unsigned long count)6666{6667	ext4_group_t block_group;6668	ext4_grpblk_t bit;6669	struct ext4_sb_info *sbi = EXT4_SB(sb);6670	struct ext4_buddy e4b;6671	int err = 0;6672	ext4_fsblk_t first_cluster = EXT4_B2C(sbi, block);6673	ext4_fsblk_t last_cluster = EXT4_B2C(sbi, block + count - 1);6674	unsigned long cluster_count = last_cluster - first_cluster + 1;6675	ext4_grpblk_t changed;6676 6677	ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);6678 6679	if (cluster_count == 0)6680		return 0;6681 6682	ext4_get_group_no_and_offset(sb, block, &block_group, &bit);6683	/*6684	 * Check to see if we are freeing blocks across a group6685	 * boundary.6686	 */6687	if (bit + cluster_count > EXT4_CLUSTERS_PER_GROUP(sb)) {6688		ext4_warning(sb, "too many blocks added to group %u",6689			     block_group);6690		err = -EINVAL;6691		goto error_out;6692	}6693 6694	err = ext4_mb_load_buddy(sb, block_group, &e4b);6695	if (err)6696		goto error_out;6697 6698	if (!ext4_sb_block_valid(sb, NULL, block, count)) {6699		ext4_error(sb, "Adding blocks in system zones - "6700			   "Block = %llu, count = %lu",6701			   block, count);6702		err = -EINVAL;6703		goto error_clean;6704	}6705 6706	err = ext4_mb_mark_context(handle, sb, false, block_group, bit,6707				   cluster_count, EXT4_MB_BITMAP_MARKED_CHECK,6708				   &changed);6709	if (err && changed == 0)6710		goto error_clean;6711 6712	if (changed != cluster_count)6713		ext4_error(sb, "bit already cleared in group %u", block_group);6714 6715	ext4_lock_group(sb, block_group);6716	mb_free_blocks(NULL, &e4b, bit, cluster_count);6717	ext4_unlock_group(sb, block_group);6718	percpu_counter_add(&sbi->s_freeclusters_counter,6719			   changed);6720 6721error_clean:6722	ext4_mb_unload_buddy(&e4b);6723error_out:6724	ext4_std_error(sb, err);6725	return err;6726}6727 6728/**6729 * ext4_trim_extent -- function to TRIM one single free extent in the group6730 * @sb:		super block for the file system6731 * @start:	starting block of the free extent in the alloc. group6732 * @count:	number of blocks to TRIM6733 * @e4b:	ext4 buddy for the group6734 *6735 * Trim "count" blocks starting at "start" in the "group". To assure that no6736 * one will allocate those blocks, mark it as used in buddy bitmap. This must6737 * be called with under the group lock.6738 */6739static int ext4_trim_extent(struct super_block *sb,6740		int start, int count, struct ext4_buddy *e4b)6741__releases(bitlock)6742__acquires(bitlock)6743{6744	struct ext4_free_extent ex;6745	ext4_group_t group = e4b->bd_group;6746	int ret = 0;6747 6748	trace_ext4_trim_extent(sb, group, start, count);6749 6750	assert_spin_locked(ext4_group_lock_ptr(sb, group));6751 6752	ex.fe_start = start;6753	ex.fe_group = group;6754	ex.fe_len = count;6755 6756	/*6757	 * Mark blocks used, so no one can reuse them while6758	 * being trimmed.6759	 */6760	mb_mark_used(e4b, &ex);6761	ext4_unlock_group(sb, group);6762	ret = ext4_issue_discard(sb, group, start, count);6763	ext4_lock_group(sb, group);6764	mb_free_blocks(NULL, e4b, start, ex.fe_len);6765	return ret;6766}6767 6768static ext4_grpblk_t ext4_last_grp_cluster(struct super_block *sb,6769					   ext4_group_t grp)6770{6771	unsigned long nr_clusters_in_group;6772 6773	if (grp < (ext4_get_groups_count(sb) - 1))6774		nr_clusters_in_group = EXT4_CLUSTERS_PER_GROUP(sb);6775	else6776		nr_clusters_in_group = (ext4_blocks_count(EXT4_SB(sb)->s_es) -6777					ext4_group_first_block_no(sb, grp))6778				       >> EXT4_CLUSTER_BITS(sb);6779 6780	return nr_clusters_in_group - 1;6781}6782 6783static bool ext4_trim_interrupted(void)6784{6785	return fatal_signal_pending(current) || freezing(current);6786}6787 6788static int ext4_try_to_trim_range(struct super_block *sb,6789		struct ext4_buddy *e4b, ext4_grpblk_t start,6790		ext4_grpblk_t max, ext4_grpblk_t minblocks)6791__acquires(ext4_group_lock_ptr(sb, e4b->bd_group))6792__releases(ext4_group_lock_ptr(sb, e4b->bd_group))6793{6794	ext4_grpblk_t next, count, free_count, last, origin_start;6795	bool set_trimmed = false;6796	void *bitmap;6797 6798	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))6799		return 0;6800 6801	last = ext4_last_grp_cluster(sb, e4b->bd_group);6802	bitmap = e4b->bd_bitmap;6803	if (start == 0 && max >= last)6804		set_trimmed = true;6805	origin_start = start;6806	start = max(e4b->bd_info->bb_first_free, start);6807	count = 0;6808	free_count = 0;6809 6810	while (start <= max) {6811		start = mb_find_next_zero_bit(bitmap, max + 1, start);6812		if (start > max)6813			break;6814 6815		next = mb_find_next_bit(bitmap, last + 1, start);6816		if (origin_start == 0 && next >= last)6817			set_trimmed = true;6818 6819		if ((next - start) >= minblocks) {6820			int ret = ext4_trim_extent(sb, start, next - start, e4b);6821 6822			if (ret && ret != -EOPNOTSUPP)6823				return count;6824			count += next - start;6825		}6826		free_count += next - start;6827		start = next + 1;6828 6829		if (ext4_trim_interrupted())6830			return count;6831 6832		if (need_resched()) {6833			ext4_unlock_group(sb, e4b->bd_group);6834			cond_resched();6835			ext4_lock_group(sb, e4b->bd_group);6836		}6837 6838		if ((e4b->bd_info->bb_free - free_count) < minblocks)6839			break;6840	}6841 6842	if (set_trimmed)6843		EXT4_MB_GRP_SET_TRIMMED(e4b->bd_info);6844 6845	return count;6846}6847 6848/**6849 * ext4_trim_all_free -- function to trim all free space in alloc. group6850 * @sb:			super block for file system6851 * @group:		group to be trimmed6852 * @start:		first group block to examine6853 * @max:		last group block to examine6854 * @minblocks:		minimum extent block count6855 *6856 * ext4_trim_all_free walks through group's block bitmap searching for free6857 * extents. When the free extent is found, mark it as used in group buddy6858 * bitmap. Then issue a TRIM command on this extent and free the extent in6859 * the group buddy bitmap.6860 */6861static ext4_grpblk_t6862ext4_trim_all_free(struct super_block *sb, ext4_group_t group,6863		   ext4_grpblk_t start, ext4_grpblk_t max,6864		   ext4_grpblk_t minblocks)6865{6866	struct ext4_buddy e4b;6867	int ret;6868 6869	trace_ext4_trim_all_free(sb, group, start, max);6870 6871	ret = ext4_mb_load_buddy(sb, group, &e4b);6872	if (ret) {6873		ext4_warning(sb, "Error %d loading buddy information for %u",6874			     ret, group);6875		return ret;6876	}6877 6878	ext4_lock_group(sb, group);6879 6880	if (!EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) ||6881	    minblocks < EXT4_SB(sb)->s_last_trim_minblks)6882		ret = ext4_try_to_trim_range(sb, &e4b, start, max, minblocks);6883	else6884		ret = 0;6885 6886	ext4_unlock_group(sb, group);6887	ext4_mb_unload_buddy(&e4b);6888 6889	ext4_debug("trimmed %d blocks in the group %d\n",6890		ret, group);6891 6892	return ret;6893}6894 6895/**6896 * ext4_trim_fs() -- trim ioctl handle function6897 * @sb:			superblock for filesystem6898 * @range:		fstrim_range structure6899 *6900 * start:	First Byte to trim6901 * len:		number of Bytes to trim from start6902 * minlen:	minimum extent length in Bytes6903 * ext4_trim_fs goes through all allocation groups containing Bytes from6904 * start to start+len. For each such a group ext4_trim_all_free function6905 * is invoked to trim all free space.6906 */6907int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range)6908{6909	unsigned int discard_granularity = bdev_discard_granularity(sb->s_bdev);6910	struct ext4_group_info *grp;6911	ext4_group_t group, first_group, last_group;6912	ext4_grpblk_t cnt = 0, first_cluster, last_cluster;6913	uint64_t start, end, minlen, trimmed = 0;6914	ext4_fsblk_t first_data_blk =6915			le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);6916	ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);6917	int ret = 0;6918 6919	start = range->start >> sb->s_blocksize_bits;6920	end = start + (range->len >> sb->s_blocksize_bits) - 1;6921	minlen = EXT4_NUM_B2C(EXT4_SB(sb),6922			      range->minlen >> sb->s_blocksize_bits);6923 6924	if (minlen > EXT4_CLUSTERS_PER_GROUP(sb) ||6925	    start >= max_blks ||6926	    range->len < sb->s_blocksize)6927		return -EINVAL;6928	/* No point to try to trim less than discard granularity */6929	if (range->minlen < discard_granularity) {6930		minlen = EXT4_NUM_B2C(EXT4_SB(sb),6931				discard_granularity >> sb->s_blocksize_bits);6932		if (minlen > EXT4_CLUSTERS_PER_GROUP(sb))6933			goto out;6934	}6935	if (end >= max_blks - 1)6936		end = max_blks - 1;6937	if (end <= first_data_blk)6938		goto out;6939	if (start < first_data_blk)6940		start = first_data_blk;6941 6942	/* Determine first and last group to examine based on start and end */6943	ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) start,6944				     &first_group, &first_cluster);6945	ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) end,6946				     &last_group, &last_cluster);6947 6948	/* end now represents the last cluster to discard in this group */6949	end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;6950 6951	for (group = first_group; group <= last_group; group++) {6952		if (ext4_trim_interrupted())6953			break;6954		grp = ext4_get_group_info(sb, group);6955		if (!grp)6956			continue;6957		/* We only do this if the grp has never been initialized */6958		if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {6959			ret = ext4_mb_init_group(sb, group, GFP_NOFS);6960			if (ret)6961				break;6962		}6963 6964		/*6965		 * For all the groups except the last one, last cluster will6966		 * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to6967		 * change it for the last group, note that last_cluster is6968		 * already computed earlier by ext4_get_group_no_and_offset()6969		 */6970		if (group == last_group)6971			end = last_cluster;6972		if (grp->bb_free >= minlen) {6973			cnt = ext4_trim_all_free(sb, group, first_cluster,6974						 end, minlen);6975			if (cnt < 0) {6976				ret = cnt;6977				break;6978			}6979			trimmed += cnt;6980		}6981 6982		/*6983		 * For every group except the first one, we are sure6984		 * that the first cluster to discard will be cluster #0.6985		 */6986		first_cluster = 0;6987	}6988 6989	if (!ret)6990		EXT4_SB(sb)->s_last_trim_minblks = minlen;6991 6992out:6993	range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;6994	return ret;6995}6996 6997/* Iterate all the free extents in the group. */6998int6999ext4_mballoc_query_range(7000	struct super_block		*sb,7001	ext4_group_t			group,7002	ext4_grpblk_t			start,7003	ext4_grpblk_t			end,7004	ext4_mballoc_query_range_fn	formatter,7005	void				*priv)7006{7007	void				*bitmap;7008	ext4_grpblk_t			next;7009	struct ext4_buddy		e4b;7010	int				error;7011 7012	error = ext4_mb_load_buddy(sb, group, &e4b);7013	if (error)7014		return error;7015	bitmap = e4b.bd_bitmap;7016 7017	ext4_lock_group(sb, group);7018 7019	start = max(e4b.bd_info->bb_first_free, start);7020	if (end >= EXT4_CLUSTERS_PER_GROUP(sb))7021		end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;7022 7023	while (start <= end) {7024		start = mb_find_next_zero_bit(bitmap, end + 1, start);7025		if (start > end)7026			break;7027		next = mb_find_next_bit(bitmap, end + 1, start);7028 7029		ext4_unlock_group(sb, group);7030		error = formatter(sb, group, start, next - start, priv);7031		if (error)7032			goto out_unload;7033		ext4_lock_group(sb, group);7034 7035		start = next + 1;7036	}7037 7038	ext4_unlock_group(sb, group);7039out_unload:7040	ext4_mb_unload_buddy(&e4b);7041 7042	return error;7043}7044 7045#ifdef CONFIG_EXT4_KUNIT_TESTS7046#include "mballoc-test.c"7047#endif7048