1	// SPDX-License-Identifier: GPL-2.0
2	/*
3	* Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
4	* Written by Alex Tomas <alex@clusterfs.com>
5	*/
6
7
8	/*
9	* mballoc.c contains the multiblocks allocation routines
10	*/
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 groups
27	*
28	* TODO v4:
29	* - normalization should take into account whether file is still open
30	* - discard preallocations if no free space left (policy?)
31	* - don't normalize tails
32	* - quota
33	* - reservation for superuser
34	*
35	* TODO v3:
36	* - bitmap read-ahead (proposed by Oleg Drokin aka green)
37	* - track min/max extents in each group for better group selection
38	* - mb_mark_used() may allocate chunk right after splitting buddy
39	* - tree of groups sorted by number of free blocks
40	* - error handling
41	*/
42
43	/*
44	* The allocation request involve request for multiple number of blocks
45	* near to the goal(block) value specified.
46	*
47	* During initialization phase of the allocator we decide to use the
48	* group preallocation or inode preallocation depending on the size of
49	* the file. The size of the file could be the resulting file size we
50	* would have after allocation, or the current file size, which ever
51	* is larger. If the size is less than sbi->s_mb_stream_request we
52	* select to use the group preallocation. The default value of
53	* s_mb_stream_request is 16 blocks. This can also be tuned via
54	* /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in
55	* terms of number of blocks.
56	*
57	* The main motivation for having small file use group preallocation is to
58	* 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 prealloc
62	* spaces for this particular inode. The inode prealloc space is
63	* represented as:
64	*
65	* pa_lstart -> the logical start block for this prealloc space
66	* pa_pstart -> the physical start block for this prealloc space
67	* pa_len -> length for this prealloc space (in clusters)
68	* pa_free -> free space available in this prealloc space (in clusters)
69	*
70	* The inode preallocation space is used looking at the _logical_ start
71	* block. If only the logical file block falls within the range of prealloc
72	* space we will consume the particular prealloc space. This makes sure that
73	* we have contiguous physical blocks representing the file blocks
74	*
75	* The important thing to be noted in case of inode prealloc space is that
76	* we don't modify the values associated to inode prealloc space except
77	* pa_free.
78	*
79	* If we are not able to find blocks in the inode prealloc space and if we
80	* have the group allocation flag set then we look at the locality group
81	* prealloc space. These are per CPU prealloc list represented as
82	*
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 contention
86	* between CPUs. It is possible to get scheduled at this point.
87	*
88	* The locality group prealloc space is used looking at whether we have
89	* enough free space (pa_free) within the prealloc space.
90	*
91	* If we can't allocate blocks via inode prealloc or/and locality group
92	* prealloc then we look at the buddy cache. The buddy cache is represented
93	* by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
94	* mapped to the buddy and bitmap information regarding different
95	* groups. The buddy information is attached to buddy cache inode so that
96	* we can access them through the page cache. The information regarding
97	* each group is loaded via ext4_mb_load_buddy. The information involve
98	* block bitmap and buddy information. The information are stored in the
99	* 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 we
106	* take up 2 blocks. A page can contain blocks_per_page (PAGE_SIZE /
107	* blocksize) blocks. So it can have information regarding groups_per_page
108	* which is blocks_per_page/2
109	*
110	* The buddy cache inode is not stored on disk. The inode is thrown
111	* away when the filesystem is unmounted.
112	*
113	* We look for count number of blocks in the buddy cache. If we were able
114	* to locate that many free blocks we return with additional information
115	* regarding rest of the contiguous physical block available
116	*
117	* Before allocating blocks via buddy cache we normalize the request
118	* blocks. This ensure we ask for more blocks that we needed. The extra
119	* blocks that we get after allocation is added to the respective prealloc
120	* list. In case of inode preallocation we follow a list of heuristics
121	* based on file size. This can be found in ext4_mb_normalize_request. If
122	* we are doing a group prealloc we try to normalize the request to
123	* sbi->s_mb_group_prealloc. The default value of s_mb_group_prealloc is
124	* dependent on the cluster size; for non-bigalloc file systems, it is
125	* 512 blocks. This can be tuned via
126	* /sys/fs/ext4/<partition>/mb_group_prealloc. The value is represented in
127	* terms of number of blocks. If we have mounted the file system with -O
128	* stripe=<value> option the group prealloc request is normalized to the
129	* smallest multiple of the stripe value (sbi->s_stripe) which is
130	* greater than the default mb_group_prealloc.
131	*
132	* If "mb_optimize_scan" mount option is set, we maintain in memory group info
133	* 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 the
140	* largest free order in the buddy bitmap of the participating group infos of
141	* that list. So, there are exactly MB_NUM_ORDERS(sb) (which means total
142	* number of buddy bitmap orders possible) number of lists. Group-infos are
143	* 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 with
150	* average fragment size >= 2^i and < 2^(i+1). The average fragment size
151	* 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 groups
153	* so we only have MB_NUM_ORDERS(sb) lists.
154	*
155	* When "mb_optimize_scan" mount option is set, mballoc consults the above data
156	* structures to decide the order in which groups are to be traversed for
157	* fulfilling an allocation request.
158	*
159	* At CR_POWER2_ALIGNED , we look for groups which have the largest_free_order
160	* >= the order of the request. We directly look at the largest free order list
161	* in the data structure (1) above where largest_free_order = order of the
162	* request. If that list is empty, we look at remaining list in the increasing
163	* order of largest_free_order. This allows us to perform CR_POWER2_ALIGNED
164	* lookup in O(1) time.
165	*
166	* At CR_GOAL_LEN_FAST, we only consider groups where
167	* average fragment size > request size. So, we lookup a group which has average
168	* fragment size just above or equal to request size using our average fragment
169	* 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 satisfied
172	* in CR_GOAL_LEN_FAST. The fact that we couldn't find a group in
173	* CR_GOAL_LEN_FAST suggests that there is no BG that has avg
174	* fragment size > goal length. So before falling to the slower
175	* CR_GOAL_LEN_SLOW, in CR_BEST_AVAIL_LEN we proactively trim goal length and
176	* then use the same fragment lists as CR_GOAL_LEN_FAST to find a BG with a big
177	* enough average fragment size. This increases the chances of finding a
178	* suitable block group in O(1) time and results in faster allocation at the
179	* cost of reduced size of allocation.
180	*
181	* If "mb_optimize_scan" mount option is not set, mballoc traverses groups in
182	* linear order which requires O(N) search time for each CR_POWER2_ALIGNED and
183	* 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_scan
188	* /sys/fs/ext4/<partition>/mb_max_to_scan
189	* /sys/fs/ext4/<partition>/mb_order2_req
190	* /sys/fs/ext4/<partition>/mb_linear_limit
191	*
192	* The regular allocator uses buddy scan only if the request len is power of
193	* 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
194	* value of s_mb_order2_reqs can be tuned via
195	* /sys/fs/ext4/<partition>/mb_order2_req. If the request len is equal to
196	* stripe size (sbi->s_stripe), we try to search for contiguous block in
197	* stripe size. This should result in better allocation on RAID setups. If
198	* not, we search in the specific group using bitmap for best extents. The
199	* 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 best
201	* extent and max_to_scan indicates how long the mballoc __can__ look for a
202	* best extent in the found extents. Searching for the blocks starts with
203	* the group specified as the goal value in allocation context via
204	* ac_g_ex. Each group is first checked based on the criteria whether it
205	* can be used for allocation. ext4_mb_good_group explains how the groups are
206	* checked.
207	*
208	* When "mb_optimize_scan" is turned on, as mentioned above, the groups may not
209	* get traversed linearly. That may result in subsequent allocations being not
210	* close to each other. And so, the underlying device may get filled up in a
211	* non-linear fashion. While that may not matter on non-rotational devices, for
212	* rotational devices that may result in higher seek times. "mb_linear_limit"
213	* tells mballoc how many groups mballoc should search linearly before
214	* performing consulting above data structures for more efficient lookups. For
215	* non rotational devices, this value defaults to 0 and for rotational devices
216	* this is set to MB_DEFAULT_LINEAR_LIMIT.
217	*
218	* Both the prealloc space are getting populated as above. So for the first
219	* request we will hit the buddy cache which will result in this prealloc
220	* space getting filled. The prealloc space is then later used for the
221	* subsequent request.
222	*/
223
224	/*
225	* mballoc operates on the following data:
226	* - on-disk bitmap
227	* - in-core buddy (actually includes buddy and bitmap)
228	* - preallocation descriptors (PAs)
229	*
230	* there are two types of preallocations:
231	* - inode
232	* assiged to specific inode and can be used for this inode only.
233	* it describes part of inode's space preallocated to specific
234	* physical blocks. any block from that preallocated can be used
235	* independent. the descriptor just tracks number of blocks left
236	* unused. so, before taking some block from descriptor, one must
237	* make sure corresponded logical block isn't allocated yet. this
238	* also means that freeing any block within descriptor's range
239	* must discard all preallocated blocks.
240	* - locality group
241	* assigned to specific locality group which does not translate to
242	* permanent set of inodes: inode can join and leave group. space
243	* from this type of preallocation can be used for any inode. thus
244	* 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 descriptors
248	*
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 either
254	* free or used in ALL structures. notice: "any time" should not be read
255	* literally -- time is discrete and delimited by locks.
256	*
257	* to keep it simple, we don't use block numbers, instead we count number of
258	* 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 + PAs
262	* - new PA: buddy += N; PA = N
263	* - use inode PA: on-disk += N; PA -= N
264	* - discard inode PA buddy -= on-disk - PA; PA = 0
265	* - use locality group PA on-disk += N; PA -= N
266	* - discard locality group PA buddy -= PA; PA = 0
267	* note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
268	* is used in real operation because we can't know actual used
269	* bits from PA, only from on-disk bitmap
270	*
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 semaphores
273	* killing performance on high-end SMP hardware. let's try to relax it using
274	* the following knowledge:
275	* 1) if buddy is referenced, it's already initialized
276	* 2) while block is used in buddy and the buddy is referenced,
277	* nobody can re-allocate that block
278	* 3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
279	* bit set and PA claims same block, it's OK. IOW, one can set bit in
280	* on-disk bitmap if buddy has same bit set or/and PA covers corresponded
281	* block
282	*
283	* so, now we're building a concurrency table:
284	* - init buddy vs.
285	* - new PA
286	* blocks for PA are allocated in the buddy, buddy must be referenced
287	* until PA is linked to allocation group to avoid concurrent buddy init
288	* - use inode PA
289	* we need to make sure that either on-disk bitmap or PA has uptodate data
290	* given (3) we care that PA-=N operation doesn't interfere with init
291	* - discard inode PA
292	* the simplest way would be to have buddy initialized by the discard
293	* - use locality group PA
294	* again PA-=N must be serialized with init
295	* - discard locality group PA
296	* the simplest way would be to have buddy initialized by the discard
297	* - new PA vs.
298	* - use inode PA
299	* i_data_sem serializes them
300	* - discard inode PA
301	* discard process must wait until PA isn't used by another process
302	* - use locality group PA
303	* some mutex should serialize them
304	* - discard locality group PA
305	* discard process must wait until PA isn't used by another process
306	* - use inode PA
307	* - use inode PA
308	* i_data_sem or another mutex should serializes them
309	* - discard inode PA
310	* discard process must wait until PA isn't used by another process
311	* - use locality group PA
312	* nothing wrong here -- they're different PAs covering different blocks
313	* - discard locality group PA
314	* discard process must wait until PA isn't used by another process
315	*
316	* now we're ready to make few consequences:
317	* - PA is referenced and while it is no discard is possible
318	* - PA is referenced until block isn't marked in on-disk bitmap
319	* - PA changes only after on-disk bitmap
320	* - discard must not compete with init. either init is done before
321	* any discard or they're serialized somehow
322	* - buddy init as sum of on-disk bitmap and PAs is done atomically
323	*
324	* a special case when we've used PA to emptiness. no need to modify buddy
325	* in this case, but we should care about concurrent init
326	*
327	*/
328
329	/*
330	* Logic in few words:
331	*
332	* - allocation:
333	* load group
334	* find blocks
335	* mark bits in on-disk bitmap
336	* release group
337	*
338	* - use preallocation:
339	* find proper PA (per-inode or group)
340	* load group
341	* mark bits in on-disk bitmap
342	* release group
343	* release PA
344	*
345	* - free:
346	* load group
347	* mark bits in on-disk bitmap
348	* release group
349	*
350	* - discard preallocations in group:
351	* mark PAs deleted
352	* move them onto local list
353	* load on-disk bitmap
354	* load group
355	* remove PA from object (inode or locality group)
356	* mark free blocks in-core
357	*
358	* - discard inode's preallocations:
359	*/
360
361	/*
362	* Locking rules
363	*
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 pa
373	* object
374	* group
375	*
376	* - find and use pa:
377	* pa
378	*
379	* - release consumed pa:
380	* pa
381	* group
382	* object
383	*
384	* - generate in-core bitmap:
385	* group
386	* pa
387	*
388	* - discard all for given object (inode, locality group):
389	* object
390	* pa
391	* group
392	*
393	* - discard all for given group:
394	* group
395	* pa
396	* group
397	* object
398	*
399	* - allocation path (ext4_mb_regular_allocator)
400	* group
401	* cr_power2_aligned/cr_goal_len_fast
402	*/
403	static struct kmem_cache *ext4_pspace_cachep;
404	static struct kmem_cache *ext4_ac_cachep;
405	static struct kmem_cache *ext4_free_data_cachep;
406
407	/* We create slab caches for groupinfo data structures based on the
408	* superblock block size. There will be one per mounted filesystem for
409	* each unique s_blocksize_bits */
410	#define NR_GRPINFO_CACHES 8
411	static struct kmem_cache *ext4_groupinfo_caches[NR_GRPINFO_CACHES];
412
413	static 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
419	static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
420	ext4_group_t group);
421	static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
422
423	static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
424	ext4_group_t group, enum criteria cr);
425
426	static 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 block
433	* allocation in ext4_mb_new_blocks().
434	* 2. We increment this percpu discard_pa_seq counter when we either allocate
435	* or free these blocks i.e. while marking those blocks as used/free in
436	* mb_mark_used()/mb_free_blocks().
437	* 3. We also increment this percpu seq counter when we successfully identify
438	* that the bb_prealloc_list is not empty and hence proceed for discarding
439	* of those PAs inside ext4_mb_discard_group_preallocations().
440	*
441	* Now to make sure that the regular fast path of block allocation is not
442	* affected, as a small optimization we only sample the percpu seq counter
443	* on that cpu. Only when the block allocation fails and when freed blocks
444	* found were 0, that is when we sample percpu seq counter for all cpus using
445	* below function ext4_get_discard_pa_seq_sum(). This happens after making
446	* sure that all the PAs on grp->bb_prealloc_list got freed or if it's empty.
447	*/
448	static DEFINE_PER_CPU(u64, discard_pa_seq);
449	static 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
459	static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
460	{
461	#if BITS_PER_LONG == 64
462	*bit += ((unsigned long) addr & 7UL) << 3;
463	addr = (void *) ((unsigned long) addr & ~7UL);
464	#elif BITS_PER_LONG == 32
465	*bit += ((unsigned long) addr & 3UL) << 3;
466	addr = (void *) ((unsigned long) addr & ~3UL);
467	#else
468	#error "how many bits you are?!"
469	#endif
470	return addr;
471	}
472
473	static inline int mb_test_bit(int bit, void *addr)
474	{
475	/*
476	* ext4_test_bit on architecture like powerpc
477	* needs unsigned long aligned address
478	*/
479	addr = mb_correct_addr_and_bit(bit: &bit, addr);
480	return ext4_test_bit(nr: bit, addr);
481	}
482
483	static inline void mb_set_bit(int bit, void *addr)
484	{
485	addr = mb_correct_addr_and_bit(bit: &bit, addr);
486	ext4_set_bit(nr: bit, addr);
487	}
488
489	static inline void mb_clear_bit(int bit, void *addr)
490	{
491	addr = mb_correct_addr_and_bit(bit: &bit, addr);
492	ext4_clear_bit(nr: bit, addr);
493	}
494
495	static inline int mb_test_and_clear_bit(int bit, void *addr)
496	{
497	addr = mb_correct_addr_and_bit(bit: &bit, addr);
498	return ext4_test_and_clear_bit(nr: bit, addr);
499	}
500
501	static 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(bit: &fix, addr);
505	tmpmax = max + fix;
506	start += fix;
507
508	ret = ext4_find_next_zero_bit(addr, size: tmpmax, offset: start) - fix;
509	if (ret > max)
510	return max;
511	return ret;
512	}
513
514	static 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(bit: &fix, addr);
518	tmpmax = max + fix;
519	start += fix;
520
521	ret = ext4_find_next_bit(addr, size: tmpmax, offset: start) - fix;
522	if (ret > max)
523	return max;
524	return ret;
525	}
526
527	static 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(sb: e4b->bd_sb)->s_mb_offsets[order];
546	*max = EXT4_SB(sb: e4b->bd_sb)->s_mb_maxs[order];
547
548	return bb;
549	}
550
551	#ifdef DOUBLE_CHECK
552	static 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
580	static 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
593	static 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
615	static 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
635	static void mb_group_bb_bitmap_free(struct ext4_group_info *grp)
636	{
637	kfree(grp->bb_bitmap);
638	}
639
640	#else
641	static inline void mb_free_blocks_double(struct inode *inode,
642	struct ext4_buddy *e4b, int first, int count)
643	{
644	return;
645	}
646	static inline void mb_mark_used_double(struct ext4_buddy *e4b,
647	int first, int count)
648	{
649	return;
650	}
651	static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
652	{
653	return;
654	}
655
656	static 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
662	static inline void mb_group_bb_bitmap_free(struct ext4_group_info *grp)
663	{
664	return;
665	}
666	#endif
667
668	#ifdef AGGRESSIVE_CHECK
669
670	#define MB_CHECK_ASSERT(assert) \
671	do { \
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
680	static 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_ASSERT
773	#define mb_check_buddy(e4b) __mb_check_buddy(e4b, \
774	__FILE__, __func__, __LINE__)
775	#else
776	#define mb_check_buddy(e4b)
777	#endif
778
779	/*
780	* Divide blocks started from @first with length @len into
781	* 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	*/
785	static 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(x: 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(bit: first >> min,
814	addr: buddy + sbi->s_mb_offsets[min]);
815
816	len -= chunk;
817	first += chunk;
818	}
819	}
820
821	static 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 free
827	* extents and for completely empty groups.
828	*/
829	order = fls(x: len) - 2;
830	if (order < 0)
831	return 0;
832	if (order == MB_NUM_ORDERS(sb))
833	order--;
834	return order;
835	}
836
837	/* Move group to appropriate avg_fragment_size list */
838	static void
839	mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
840	{
841	struct ext4_sb_info *sbi = EXT4_SB(sb);
842	int new_order;
843
844	if (!test_opt2(sb, MB_OPTIMIZE_SCAN) || grp->bb_fragments == 0)
845	return;
846
847	new_order = mb_avg_fragment_size_order(sb,
848	len: grp->bb_free / grp->bb_fragments);
849	if (new_order == grp->bb_avg_fragment_size_order)
850	return;
851
852	if (grp->bb_avg_fragment_size_order != -1) {
853	write_lock(&sbi->s_mb_avg_fragment_size_locks[
854	grp->bb_avg_fragment_size_order]);
855	list_del(entry: &grp->bb_avg_fragment_size_node);
856	write_unlock(&sbi->s_mb_avg_fragment_size_locks[
857	grp->bb_avg_fragment_size_order]);
858	}
859	grp->bb_avg_fragment_size_order = new_order;
860	write_lock(&sbi->s_mb_avg_fragment_size_locks[
861	grp->bb_avg_fragment_size_order]);
862	list_add_tail(new: &grp->bb_avg_fragment_size_node,
863	head: &sbi->s_mb_avg_fragment_size[grp->bb_avg_fragment_size_order]);
864	write_unlock(&sbi->s_mb_avg_fragment_size_locks[
865	grp->bb_avg_fragment_size_order]);
866	}
867
868	/*
869	* Choose next group by traversing largest_free_order lists. Updates *new_cr if
870	* cr level needs an update.
871	*/
872	static void ext4_mb_choose_next_group_p2_aligned(struct ext4_allocation_context *ac,
873	enum criteria *new_cr, ext4_group_t *group)
874	{
875	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
876	struct ext4_group_info *iter;
877	int i;
878
879	if (ac->ac_status == AC_STATUS_FOUND)
880	return;
881
882	if (unlikely(sbi->s_mb_stats && ac->ac_flags & EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED))
883	atomic_inc(v: &sbi->s_bal_p2_aligned_bad_suggestions);
884
885	for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
886	if (list_empty(head: &sbi->s_mb_largest_free_orders[i]))
887	continue;
888	read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
889	if (list_empty(head: &sbi->s_mb_largest_free_orders[i])) {
890	read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
891	continue;
892	}
893	list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
894	bb_largest_free_order_node) {
895	if (sbi->s_mb_stats)
896	atomic64_inc(v: &sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]);
897	if (likely(ext4_mb_good_group(ac, iter->bb_group, CR_POWER2_ALIGNED))) {
898	*group = iter->bb_group;
899	ac->ac_flags |= EXT4_MB_CR_POWER2_ALIGNED_OPTIMIZED;
900	read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
901	return;
902	}
903	}
904	read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
905	}
906
907	/* Increment cr and search again if no group is found */
908	*new_cr = CR_GOAL_LEN_FAST;
909	}
910
911	/*
912	* Find a suitable group of given order from the average fragments list.
913	*/
914	static struct ext4_group_info *
915	ext4_mb_find_good_group_avg_frag_lists(struct ext4_allocation_context *ac, int order)
916	{
917	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
918	struct list_head *frag_list = &sbi->s_mb_avg_fragment_size[order];
919	rwlock_t *frag_list_lock = &sbi->s_mb_avg_fragment_size_locks[order];
920	struct ext4_group_info *grp = NULL, *iter;
921	enum criteria cr = ac->ac_criteria;
922
923	if (list_empty(head: frag_list))
924	return NULL;
925	read_lock(frag_list_lock);
926	if (list_empty(head: frag_list)) {
927	read_unlock(frag_list_lock);
928	return NULL;
929	}
930	list_for_each_entry(iter, frag_list, bb_avg_fragment_size_node) {
931	if (sbi->s_mb_stats)
932	atomic64_inc(v: &sbi->s_bal_cX_groups_considered[cr]);
933	if (likely(ext4_mb_good_group(ac, iter->bb_group, cr))) {
934	grp = iter;
935	break;
936	}
937	}
938	read_unlock(frag_list_lock);
939	return grp;
940	}
941
942	/*
943	* Choose next group by traversing average fragment size list of suitable
944	* order. Updates *new_cr if cr level needs an update.
945	*/
946	static void ext4_mb_choose_next_group_goal_fast(struct ext4_allocation_context *ac,
947	enum criteria *new_cr, ext4_group_t *group)
948	{
949	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
950	struct ext4_group_info *grp = NULL;
951	int i;
952
953	if (unlikely(ac->ac_flags & EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED)) {
954	if (sbi->s_mb_stats)
955	atomic_inc(v: &sbi->s_bal_goal_fast_bad_suggestions);
956	}
957
958	for (i = mb_avg_fragment_size_order(sb: ac->ac_sb, len: ac->ac_g_ex.fe_len);
959	i < MB_NUM_ORDERS(ac->ac_sb); i++) {
960	grp = ext4_mb_find_good_group_avg_frag_lists(ac, order: i);
961	if (grp) {
962	*group = grp->bb_group;
963	ac->ac_flags |= EXT4_MB_CR_GOAL_LEN_FAST_OPTIMIZED;
964	return;
965	}
966	}
967
968	/*
969	* CR_BEST_AVAIL_LEN works based on the concept that we have
970	* a larger normalized goal len request which can be trimmed to
971	* a smaller goal len such that it can still satisfy original
972	* request len. However, allocation request for non-regular
973	* files never gets normalized.
974	* See function ext4_mb_normalize_request() (EXT4_MB_HINT_DATA).
975	*/
976	if (ac->ac_flags & EXT4_MB_HINT_DATA)
977	*new_cr = CR_BEST_AVAIL_LEN;
978	else
979	*new_cr = CR_GOAL_LEN_SLOW;
980	}
981
982	/*
983	* We couldn't find a group in CR_GOAL_LEN_FAST so try to find the highest free fragment
984	* order we have and proactively trim the goal request length to that order to
985	* find a suitable group faster.
986	*
987	* This optimizes allocation speed at the cost of slightly reduced
988	* preallocations. However, we make sure that we don't trim the request too
989	* much and fall to CR_GOAL_LEN_SLOW in that case.
990	*/
991	static void ext4_mb_choose_next_group_best_avail(struct ext4_allocation_context *ac,
992	enum criteria *new_cr, ext4_group_t *group)
993	{
994	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
995	struct ext4_group_info *grp = NULL;
996	int i, order, min_order;
997	unsigned long num_stripe_clusters = 0;
998
999	if (unlikely(ac->ac_flags & EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED)) {
1000	if (sbi->s_mb_stats)
1001	atomic_inc(v: &sbi->s_bal_best_avail_bad_suggestions);
1002	}
1003
1004	/*
1005	* mb_avg_fragment_size_order() returns order in a way that makes
1006	* retrieving back the length using (1 << order) inaccurate. Hence, use
1007	* fls() instead since we need to know the actual length while modifying
1008	* goal length.
1009	*/
1010	order = fls(x: ac->ac_g_ex.fe_len) - 1;
1011	min_order = order - sbi->s_mb_best_avail_max_trim_order;
1012	if (min_order < 0)
1013	min_order = 0;
1014
1015	if (sbi->s_stripe > 0) {
1016	/*
1017	* We are assuming that stripe size is always a multiple of
1018	* cluster ratio otherwise __ext4_fill_super exists early.
1019	*/
1020	num_stripe_clusters = EXT4_NUM_B2C(sbi, sbi->s_stripe);
1021	if (1 << min_order < num_stripe_clusters)
1022	/*
1023	* We consider 1 order less because later we round
1024	* up the goal len to num_stripe_clusters
1025	*/
1026	min_order = fls(x: num_stripe_clusters) - 1;
1027	}
1028
1029	if (1 << min_order < ac->ac_o_ex.fe_len)
1030	min_order = fls(x: ac->ac_o_ex.fe_len);
1031
1032	for (i = order; i >= min_order; i--) {
1033	int frag_order;
1034	/*
1035	* Scale down goal len to make sure we find something
1036	* in the free fragments list. Basically, reduce
1037	* preallocations.
1038	*/
1039	ac->ac_g_ex.fe_len = 1 << i;
1040
1041	if (num_stripe_clusters > 0) {
1042	/*
1043	* Try to round up the adjusted goal length to
1044	* stripe size (in cluster units) multiple for
1045	* efficiency.
1046	*/
1047	ac->ac_g_ex.fe_len = roundup(ac->ac_g_ex.fe_len,
1048	num_stripe_clusters);
1049	}
1050
1051	frag_order = mb_avg_fragment_size_order(sb: ac->ac_sb,
1052	len: ac->ac_g_ex.fe_len);
1053
1054	grp = ext4_mb_find_good_group_avg_frag_lists(ac, order: frag_order);
1055	if (grp) {
1056	*group = grp->bb_group;
1057	ac->ac_flags |= EXT4_MB_CR_BEST_AVAIL_LEN_OPTIMIZED;
1058	return;
1059	}
1060	}
1061
1062	/* Reset goal length to original goal length before falling into CR_GOAL_LEN_SLOW */
1063	ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;
1064	*new_cr = CR_GOAL_LEN_SLOW;
1065	}
1066
1067	static inline int should_optimize_scan(struct ext4_allocation_context *ac)
1068	{
1069	if (unlikely(!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN)))
1070	return 0;
1071	if (ac->ac_criteria >= CR_GOAL_LEN_SLOW)
1072	return 0;
1073	if (!ext4_test_inode_flag(inode: ac->ac_inode, bit: EXT4_INODE_EXTENTS))
1074	return 0;
1075	return 1;
1076	}
1077
1078	/*
1079	* Return next linear group for allocation. If linear traversal should not be
1080	* performed, this function just returns the same group
1081	*/
1082	static ext4_group_t
1083	next_linear_group(struct ext4_allocation_context *ac, ext4_group_t group,
1084	ext4_group_t ngroups)
1085	{
1086	if (!should_optimize_scan(ac))
1087	goto inc_and_return;
1088
1089	if (ac->ac_groups_linear_remaining) {
1090	ac->ac_groups_linear_remaining--;
1091	goto inc_and_return;
1092	}
1093
1094	return group;
1095	inc_and_return:
1096	/*
1097	* Artificially restricted ngroups for non-extent
1098	* files makes group > ngroups possible on first loop.
1099	*/
1100	return group + 1 >= ngroups ? 0 : group + 1;
1101	}
1102
1103	/*
1104	* ext4_mb_choose_next_group: choose next group for allocation.
1105	*
1106	* @ac Allocation Context
1107	* @new_cr This is an output parameter. If the there is no good group
1108	* available at current CR level, this field is updated to indicate
1109	* the new cr level that should be used.
1110	* @group This is an input / output parameter. As an input it indicates the
1111	* next group that the allocator intends to use for allocation. As
1112	* output, this field indicates the next group that should be used as
1113	* determined by the optimization functions.
1114	* @ngroups Total number of groups
1115	*/
1116	static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
1117	enum criteria *new_cr, ext4_group_t *group, ext4_group_t ngroups)
1118	{
1119	*new_cr = ac->ac_criteria;
1120
1121	if (!should_optimize_scan(ac) || ac->ac_groups_linear_remaining) {
1122	*group = next_linear_group(ac, group: *group, ngroups);
1123	return;
1124	}
1125
1126	if (*new_cr == CR_POWER2_ALIGNED) {
1127	ext4_mb_choose_next_group_p2_aligned(ac, new_cr, group);
1128	} else if (*new_cr == CR_GOAL_LEN_FAST) {
1129	ext4_mb_choose_next_group_goal_fast(ac, new_cr, group);
1130	} else if (*new_cr == CR_BEST_AVAIL_LEN) {
1131	ext4_mb_choose_next_group_best_avail(ac, new_cr, group);
1132	} else {
1133	/*
1134	* TODO: For CR=2, we can arrange groups in an rb tree sorted by
1135	* bb_free. But until that happens, we should never come here.
1136	*/
1137	WARN_ON(1);
1138	}
1139	}
1140
1141	/*
1142	* Cache the order of the largest free extent we have available in this block
1143	* group.
1144	*/
1145	static void
1146	mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
1147	{
1148	struct ext4_sb_info *sbi = EXT4_SB(sb);
1149	int i;
1150
1151	for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--)
1152	if (grp->bb_counters[i] > 0)
1153	break;
1154	/* No need to move between order lists? */
1155	if (!test_opt2(sb, MB_OPTIMIZE_SCAN) ||
1156	i == grp->bb_largest_free_order) {
1157	grp->bb_largest_free_order = i;
1158	return;
1159	}
1160
1161	if (grp->bb_largest_free_order >= 0) {
1162	write_lock(&sbi->s_mb_largest_free_orders_locks[
1163	grp->bb_largest_free_order]);
1164	list_del_init(entry: &grp->bb_largest_free_order_node);
1165	write_unlock(&sbi->s_mb_largest_free_orders_locks[
1166	grp->bb_largest_free_order]);
1167	}
1168	grp->bb_largest_free_order = i;
1169	if (grp->bb_largest_free_order >= 0 && grp->bb_free) {
1170	write_lock(&sbi->s_mb_largest_free_orders_locks[
1171	grp->bb_largest_free_order]);
1172	list_add_tail(new: &grp->bb_largest_free_order_node,
1173	head: &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
1174	write_unlock(&sbi->s_mb_largest_free_orders_locks[
1175	grp->bb_largest_free_order]);
1176	}
1177	}
1178
1179	static noinline_for_stack
1180	void ext4_mb_generate_buddy(struct super_block *sb,
1181	void *buddy, void *bitmap, ext4_group_t group,
1182	struct ext4_group_info *grp)
1183	{
1184	struct ext4_sb_info *sbi = EXT4_SB(sb);
1185	ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
1186	ext4_grpblk_t i = 0;
1187	ext4_grpblk_t first;
1188	ext4_grpblk_t len;
1189	unsigned free = 0;
1190	unsigned fragments = 0;
1191	unsigned long long period = get_cycles();
1192
1193	/* initialize buddy from bitmap which is aggregation
1194	* of on-disk bitmap and preallocations */
1195	i = mb_find_next_zero_bit(addr: bitmap, max, start: 0);
1196	grp->bb_first_free = i;
1197	while (i < max) {
1198	fragments++;
1199	first = i;
1200	i = mb_find_next_bit(addr: bitmap, max, start: i);
1201	len = i - first;
1202	free += len;
1203	if (len > 1)
1204	ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
1205	else
1206	grp->bb_counters[0]++;
1207	if (i < max)
1208	i = mb_find_next_zero_bit(addr: bitmap, max, start: i);
1209	}
1210	grp->bb_fragments = fragments;
1211
1212	if (free != grp->bb_free) {
1213	ext4_grp_locked_error(sb, group, 0, 0,
1214	"block bitmap and bg descriptor "
1215	"inconsistent: %u vs %u free clusters",
1216	free, grp->bb_free);
1217	/*
1218	* If we intend to continue, we consider group descriptor
1219	* corrupt and update bb_free using bitmap value
1220	*/
1221	grp->bb_free = free;
1222	ext4_mark_group_bitmap_corrupted(sb, block_group: group,
1223	EXT4_GROUP_INFO_BBITMAP_CORRUPT);
1224	}
1225	mb_set_largest_free_order(sb, grp);
1226	mb_update_avg_fragment_size(sb, grp);
1227
1228	clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, addr: &(grp->bb_state));
1229
1230	period = get_cycles() - period;
1231	atomic_inc(v: &sbi->s_mb_buddies_generated);
1232	atomic64_add(i: period, v: &sbi->s_mb_generation_time);
1233	}
1234
1235	static void mb_regenerate_buddy(struct ext4_buddy *e4b)
1236	{
1237	int count;
1238	int order = 1;
1239	void *buddy;
1240
1241	while ((buddy = mb_find_buddy(e4b, order: order++, max: &count)))
1242	mb_set_bits(bm: buddy, cur: 0, len: count);
1243
1244	e4b->bd_info->bb_fragments = 0;
1245	memset(e4b->bd_info->bb_counters, 0,
1246	sizeof(*e4b->bd_info->bb_counters) *
1247	(e4b->bd_sb->s_blocksize_bits + 2));
1248
1249	ext4_mb_generate_buddy(sb: e4b->bd_sb, buddy: e4b->bd_buddy,
1250	bitmap: e4b->bd_bitmap, group: e4b->bd_group, grp: e4b->bd_info);
1251	}
1252
1253	/* The buddy information is attached the buddy cache inode
1254	* for convenience. The information regarding each group
1255	* is loaded via ext4_mb_load_buddy. The information involve
1256	* block bitmap and buddy information. The information are
1257	* stored in the inode as
1258	*
1259	* { page }
1260	* [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
1261	*
1262	*
1263	* one block each for bitmap and buddy information.
1264	* So for each group we take up 2 blocks. A page can
1265	* contain blocks_per_page (PAGE_SIZE / blocksize) blocks.
1266	* So it can have information regarding groups_per_page which
1267	* is blocks_per_page/2
1268	*
1269	* Locking note: This routine takes the block group lock of all groups
1270	* for this page; do not hold this lock when calling this routine!
1271	*/
1272
1273	static int ext4_mb_init_cache(struct page *page, char *incore, gfp_t gfp)
1274	{
1275	ext4_group_t ngroups;
1276	unsigned int blocksize;
1277	int blocks_per_page;
1278	int groups_per_page;
1279	int err = 0;
1280	int i;
1281	ext4_group_t first_group, group;
1282	int first_block;
1283	struct super_block *sb;
1284	struct buffer_head *bhs;
1285	struct buffer_head **bh = NULL;
1286	struct inode *inode;
1287	char *data;
1288	char *bitmap;
1289	struct ext4_group_info *grinfo;
1290
1291	inode = page->mapping->host;
1292	sb = inode->i_sb;
1293	ngroups = ext4_get_groups_count(sb);
1294	blocksize = i_blocksize(node: inode);
1295	blocks_per_page = PAGE_SIZE / blocksize;
1296
1297	mb_debug(sb, "init page %lu\n", page->index);
1298
1299	groups_per_page = blocks_per_page >> 1;
1300	if (groups_per_page == 0)
1301	groups_per_page = 1;
1302
1303	/* allocate buffer_heads to read bitmaps */
1304	if (groups_per_page > 1) {
1305	i = sizeof(struct buffer_head *) * groups_per_page;
1306	bh = kzalloc(size: i, flags: gfp);
1307	if (bh == NULL)
1308	return -ENOMEM;
1309	} else
1310	bh = &bhs;
1311
1312	first_group = page->index * blocks_per_page / 2;
1313
1314	/* read all groups the page covers into the cache */
1315	for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
1316	if (group >= ngroups)
1317	break;
1318
1319	grinfo = ext4_get_group_info(sb, group);
1320	if (!grinfo)
1321	continue;
1322	/*
1323	* If page is uptodate then we came here after online resize
1324	* which added some new uninitialized group info structs, so
1325	* we must skip all initialized uptodate buddies on the page,
1326	* which may be currently in use by an allocating task.
1327	*/
1328	if (PageUptodate(page) && !EXT4_MB_GRP_NEED_INIT(grinfo)) {
1329	bh[i] = NULL;
1330	continue;
1331	}
1332	bh[i] = ext4_read_block_bitmap_nowait(sb, block_group: group, ignore_locked: false);
1333	if (IS_ERR(ptr: bh[i])) {
1334	err = PTR_ERR(ptr: bh[i]);
1335	bh[i] = NULL;
1336	goto out;
1337	}
1338	mb_debug(sb, "read bitmap for group %u\n", group);
1339	}
1340
1341	/* wait for I/O completion */
1342	for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
1343	int err2;
1344
1345	if (!bh[i])
1346	continue;
1347	err2 = ext4_wait_block_bitmap(sb, block_group: group, bh: bh[i]);
1348	if (!err)
1349	err = err2;
1350	}
1351
1352	first_block = page->index * blocks_per_page;
1353	for (i = 0; i < blocks_per_page; i++) {
1354	group = (first_block + i) >> 1;
1355	if (group >= ngroups)
1356	break;
1357
1358	if (!bh[group - first_group])
1359	/* skip initialized uptodate buddy */
1360	continue;
1361
1362	if (!buffer_verified(bh: bh[group - first_group]))
1363	/* Skip faulty bitmaps */
1364	continue;
1365	err = 0;
1366
1367	/*
1368	* data carry information regarding this
1369	* particular group in the format specified
1370	* above
1371	*
1372	*/
1373	data = page_address(page) + (i * blocksize);
1374	bitmap = bh[group - first_group]->b_data;
1375
1376	/*
1377	* We place the buddy block and bitmap block
1378	* close together
1379	*/
1380	grinfo = ext4_get_group_info(sb, group);
1381	if (!grinfo) {
1382	err = -EFSCORRUPTED;
1383	goto out;
1384	}
1385	if ((first_block + i) & 1) {
1386	/* this is block of buddy */
1387	BUG_ON(incore == NULL);
1388	mb_debug(sb, "put buddy for group %u in page %lu/%x\n",
1389	group, page->index, i * blocksize);
1390	trace_ext4_mb_buddy_bitmap_load(sb, group);
1391	grinfo->bb_fragments = 0;
1392	memset(grinfo->bb_counters, 0,
1393	sizeof(*grinfo->bb_counters) *
1394	(MB_NUM_ORDERS(sb)));
1395	/*
1396	* incore got set to the group block bitmap below
1397	*/
1398	ext4_lock_group(sb, group);
1399	/* init the buddy */
1400	memset(data, 0xff, blocksize);
1401	ext4_mb_generate_buddy(sb, buddy: data, bitmap: incore, group, grp: grinfo);
1402	ext4_unlock_group(sb, group);
1403	incore = NULL;
1404	} else {
1405	/* this is block of bitmap */
1406	BUG_ON(incore != NULL);
1407	mb_debug(sb, "put bitmap for group %u in page %lu/%x\n",
1408	group, page->index, i * blocksize);
1409	trace_ext4_mb_bitmap_load(sb, group);
1410
1411	/* see comments in ext4_mb_put_pa() */
1412	ext4_lock_group(sb, group);
1413	memcpy(data, bitmap, blocksize);
1414
1415	/* mark all preallocated blks used in in-core bitmap */
1416	ext4_mb_generate_from_pa(sb, bitmap: data, group);
1417	WARN_ON_ONCE(!RB_EMPTY_ROOT(&grinfo->bb_free_root));
1418	ext4_unlock_group(sb, group);
1419
1420	/* set incore so that the buddy information can be
1421	* generated using this
1422	*/
1423	incore = data;
1424	}
1425	}
1426	SetPageUptodate(page);
1427
1428	out:
1429	if (bh) {
1430	for (i = 0; i < groups_per_page; i++)
1431	brelse(bh: bh[i]);
1432	if (bh != &bhs)
1433	kfree(objp: bh);
1434	}
1435	return err;
1436	}
1437
1438	/*
1439	* Lock the buddy and bitmap pages. This make sure other parallel init_group
1440	* on the same buddy page doesn't happen whild holding the buddy page lock.
1441	* Return locked buddy and bitmap pages on e4b struct. If buddy and bitmap
1442	* are on the same page e4b->bd_buddy_page is NULL and return value is 0.
1443	*/
1444	static int ext4_mb_get_buddy_page_lock(struct super_block *sb,
1445	ext4_group_t group, struct ext4_buddy *e4b, gfp_t gfp)
1446	{
1447	struct inode *inode = EXT4_SB(sb)->s_buddy_cache;
1448	int block, pnum, poff;
1449	int blocks_per_page;
1450	struct page *page;
1451
1452	e4b->bd_buddy_page = NULL;
1453	e4b->bd_bitmap_page = NULL;
1454
1455	blocks_per_page = PAGE_SIZE / sb->s_blocksize;
1456	/*
1457	* the buddy cache inode stores the block bitmap
1458	* and buddy information in consecutive blocks.
1459	* So for each group we need two blocks.
1460	*/
1461	block = group * 2;
1462	pnum = block / blocks_per_page;
1463	poff = block % blocks_per_page;
1464	page = find_or_create_page(mapping: inode->i_mapping, index: pnum, gfp_mask: gfp);
1465	if (!page)
1466	return -ENOMEM;
1467	BUG_ON(page->mapping != inode->i_mapping);
1468	e4b->bd_bitmap_page = page;
1469	e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
1470
1471	if (blocks_per_page >= 2) {
1472	/* buddy and bitmap are on the same page */
1473	return 0;
1474	}
1475
1476	/* blocks_per_page == 1, hence we need another page for the buddy */
1477	page = find_or_create_page(mapping: inode->i_mapping, index: block + 1, gfp_mask: gfp);
1478	if (!page)
1479	return -ENOMEM;
1480	BUG_ON(page->mapping != inode->i_mapping);
1481	e4b->bd_buddy_page = page;
1482	return 0;
1483	}
1484
1485	static void ext4_mb_put_buddy_page_lock(struct ext4_buddy *e4b)
1486	{
1487	if (e4b->bd_bitmap_page) {
1488	unlock_page(page: e4b->bd_bitmap_page);
1489	put_page(page: e4b->bd_bitmap_page);
1490	}
1491	if (e4b->bd_buddy_page) {
1492	unlock_page(page: e4b->bd_buddy_page);
1493	put_page(page: e4b->bd_buddy_page);
1494	}
1495	}
1496
1497	/*
1498	* Locking note: This routine calls ext4_mb_init_cache(), which takes the
1499	* block group lock of all groups for this page; do not hold the BG lock when
1500	* calling this routine!
1501	*/
1502	static noinline_for_stack
1503	int ext4_mb_init_group(struct super_block *sb, ext4_group_t group, gfp_t gfp)
1504	{
1505
1506	struct ext4_group_info *this_grp;
1507	struct ext4_buddy e4b;
1508	struct page *page;
1509	int ret = 0;
1510
1511	might_sleep();
1512	mb_debug(sb, "init group %u\n", group);
1513	this_grp = ext4_get_group_info(sb, group);
1514	if (!this_grp)
1515	return -EFSCORRUPTED;
1516
1517	/*
1518	* This ensures that we don't reinit the buddy cache
1519	* page which map to the group from which we are already
1520	* allocating. If we are looking at the buddy cache we would
1521	* have taken a reference using ext4_mb_load_buddy and that
1522	* would have pinned buddy page to page cache.
1523	* The call to ext4_mb_get_buddy_page_lock will mark the
1524	* page accessed.
1525	*/
1526	ret = ext4_mb_get_buddy_page_lock(sb, group, e4b: &e4b, gfp);
1527	if (ret || !EXT4_MB_GRP_NEED_INIT(this_grp)) {
1528	/*
1529	* somebody initialized the group
1530	* return without doing anything
1531	*/
1532	goto err;
1533	}
1534
1535	page = e4b.bd_bitmap_page;
1536	ret = ext4_mb_init_cache(page, NULL, gfp);
1537	if (ret)
1538	goto err;
1539	if (!PageUptodate(page)) {
1540	ret = -EIO;
1541	goto err;
1542	}
1543
1544	if (e4b.bd_buddy_page == NULL) {
1545	/*
1546	* If both the bitmap and buddy are in
1547	* the same page we don't need to force
1548	* init the buddy
1549	*/
1550	ret = 0;
1551	goto err;
1552	}
1553	/* init buddy cache */
1554	page = e4b.bd_buddy_page;
1555	ret = ext4_mb_init_cache(page, incore: e4b.bd_bitmap, gfp);
1556	if (ret)
1557	goto err;
1558	if (!PageUptodate(page)) {
1559	ret = -EIO;
1560	goto err;
1561	}
1562	err:
1563	ext4_mb_put_buddy_page_lock(e4b: &e4b);
1564	return ret;
1565	}
1566
1567	/*
1568	* Locking note: This routine calls ext4_mb_init_cache(), which takes the
1569	* block group lock of all groups for this page; do not hold the BG lock when
1570	* calling this routine!
1571	*/
1572	static noinline_for_stack int
1573	ext4_mb_load_buddy_gfp(struct super_block *sb, ext4_group_t group,
1574	struct ext4_buddy *e4b, gfp_t gfp)
1575	{
1576	int blocks_per_page;
1577	int block;
1578	int pnum;
1579	int poff;
1580	struct page *page;
1581	int ret;
1582	struct ext4_group_info *grp;
1583	struct ext4_sb_info *sbi = EXT4_SB(sb);
1584	struct inode *inode = sbi->s_buddy_cache;
1585
1586	might_sleep();
1587	mb_debug(sb, "load group %u\n", group);
1588
1589	blocks_per_page = PAGE_SIZE / sb->s_blocksize;
1590	grp = ext4_get_group_info(sb, group);
1591	if (!grp)
1592	return -EFSCORRUPTED;
1593
1594	e4b->bd_blkbits = sb->s_blocksize_bits;
1595	e4b->bd_info = grp;
1596	e4b->bd_sb = sb;
1597	e4b->bd_group = group;
1598	e4b->bd_buddy_page = NULL;
1599	e4b->bd_bitmap_page = NULL;
1600
1601	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
1602	/*
1603	* we need full data about the group
1604	* to make a good selection
1605	*/
1606	ret = ext4_mb_init_group(sb, group, gfp);
1607	if (ret)
1608	return ret;
1609	}
1610
1611	/*
1612	* the buddy cache inode stores the block bitmap
1613	* and buddy information in consecutive blocks.
1614	* So for each group we need two blocks.
1615	*/
1616	block = group * 2;
1617	pnum = block / blocks_per_page;
1618	poff = block % blocks_per_page;
1619
1620	/* we could use find_or_create_page(), but it locks page
1621	* what we'd like to avoid in fast path ... */
1622	page = find_get_page_flags(mapping: inode->i_mapping, offset: pnum, FGP_ACCESSED);
1623	if (page == NULL || !PageUptodate(page)) {
1624	if (page)
1625	/*
1626	* drop the page reference and try
1627	* to get the page with lock. If we
1628	* are not uptodate that implies
1629	* somebody just created the page but
1630	* is yet to initialize the same. So
1631	* wait for it to initialize.
1632	*/
1633	put_page(page);
1634	page = find_or_create_page(mapping: inode->i_mapping, index: pnum, gfp_mask: gfp);
1635	if (page) {
1636	if (WARN_RATELIMIT(page->mapping != inode->i_mapping,
1637	"ext4: bitmap's paging->mapping != inode->i_mapping\n")) {
1638	/* should never happen */
1639	unlock_page(page);
1640	ret = -EINVAL;
1641	goto err;
1642	}
1643	if (!PageUptodate(page)) {
1644	ret = ext4_mb_init_cache(page, NULL, gfp);
1645	if (ret) {
1646	unlock_page(page);
1647	goto err;
1648	}
1649	mb_cmp_bitmaps(e4b, page_address(page) +
1650	(poff * sb->s_blocksize));
1651	}
1652	unlock_page(page);
1653	}
1654	}
1655	if (page == NULL) {
1656	ret = -ENOMEM;
1657	goto err;
1658	}
1659	if (!PageUptodate(page)) {
1660	ret = -EIO;
1661	goto err;
1662	}
1663
1664	/* Pages marked accessed already */
1665	e4b->bd_bitmap_page = page;
1666	e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
1667
1668	block++;
1669	pnum = block / blocks_per_page;
1670	poff = block % blocks_per_page;
1671
1672	page = find_get_page_flags(mapping: inode->i_mapping, offset: pnum, FGP_ACCESSED);
1673	if (page == NULL || !PageUptodate(page)) {
1674	if (page)
1675	put_page(page);
1676	page = find_or_create_page(mapping: inode->i_mapping, index: pnum, gfp_mask: gfp);
1677	if (page) {
1678	if (WARN_RATELIMIT(page->mapping != inode->i_mapping,
1679	"ext4: buddy bitmap's page->mapping != inode->i_mapping\n")) {
1680	/* should never happen */
1681	unlock_page(page);
1682	ret = -EINVAL;
1683	goto err;
1684	}
1685	if (!PageUptodate(page)) {
1686	ret = ext4_mb_init_cache(page, incore: e4b->bd_bitmap,
1687	gfp);
1688	if (ret) {
1689	unlock_page(page);
1690	goto err;
1691	}
1692	}
1693	unlock_page(page);
1694	}
1695	}
1696	if (page == NULL) {
1697	ret = -ENOMEM;
1698	goto err;
1699	}
1700	if (!PageUptodate(page)) {
1701	ret = -EIO;
1702	goto err;
1703	}
1704
1705	/* Pages marked accessed already */
1706	e4b->bd_buddy_page = page;
1707	e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
1708
1709	return 0;
1710
1711	err:
1712	if (page)
1713	put_page(page);
1714	if (e4b->bd_bitmap_page)
1715	put_page(page: e4b->bd_bitmap_page);
1716
1717	e4b->bd_buddy = NULL;
1718	e4b->bd_bitmap = NULL;
1719	return ret;
1720	}
1721
1722	static int ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
1723	struct ext4_buddy *e4b)
1724	{
1725	return ext4_mb_load_buddy_gfp(sb, group, e4b, GFP_NOFS);
1726	}
1727
1728	static void ext4_mb_unload_buddy(struct ext4_buddy *e4b)
1729	{
1730	if (e4b->bd_bitmap_page)
1731	put_page(page: e4b->bd_bitmap_page);
1732	if (e4b->bd_buddy_page)
1733	put_page(page: e4b->bd_buddy_page);
1734	}
1735
1736
1737	static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
1738	{
1739	int order = 1, max;
1740	void *bb;
1741
1742	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
1743	BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
1744
1745	while (order <= e4b->bd_blkbits + 1) {
1746	bb = mb_find_buddy(e4b, order, max: &max);
1747	if (!mb_test_bit(bit: block >> order, addr: bb)) {
1748	/* this block is part of buddy of order 'order' */
1749	return order;
1750	}
1751	order++;
1752	}
1753	return 0;
1754	}
1755
1756	static void mb_clear_bits(void *bm, int cur, int len)
1757	{
1758	__u32 *addr;
1759
1760	len = cur + len;
1761	while (cur < len) {
1762	if ((cur & 31) == 0 && (len - cur) >= 32) {
1763	/* fast path: clear whole word at once */
1764	addr = bm + (cur >> 3);
1765	*addr = 0;
1766	cur += 32;
1767	continue;
1768	}
1769	mb_clear_bit(bit: cur, addr: bm);
1770	cur++;
1771	}
1772	}
1773
1774	/* clear bits in given range
1775	* will return first found zero bit if any, -1 otherwise
1776	*/
1777	static int mb_test_and_clear_bits(void *bm, int cur, int len)
1778	{
1779	__u32 *addr;
1780	int zero_bit = -1;
1781
1782	len = cur + len;
1783	while (cur < len) {
1784	if ((cur & 31) == 0 && (len - cur) >= 32) {
1785	/* fast path: clear whole word at once */
1786	addr = bm + (cur >> 3);
1787	if (*addr != (__u32)(-1) && zero_bit == -1)
1788	zero_bit = cur + mb_find_next_zero_bit(addr, max: 32, start: 0);
1789	*addr = 0;
1790	cur += 32;
1791	continue;
1792	}
1793	if (!mb_test_and_clear_bit(bit: cur, addr: bm) && zero_bit == -1)
1794	zero_bit = cur;
1795	cur++;
1796	}
1797
1798	return zero_bit;
1799	}
1800
1801	void mb_set_bits(void *bm, int cur, int len)
1802	{
1803	__u32 *addr;
1804
1805	len = cur + len;
1806	while (cur < len) {
1807	if ((cur & 31) == 0 && (len - cur) >= 32) {
1808	/* fast path: set whole word at once */
1809	addr = bm + (cur >> 3);
1810	*addr = 0xffffffff;
1811	cur += 32;
1812	continue;
1813	}
1814	mb_set_bit(bit: cur, addr: bm);
1815	cur++;
1816	}
1817	}
1818
1819	static inline int mb_buddy_adjust_border(int* bit, void* bitmap, int side)
1820	{
1821	if (mb_test_bit(bit: *bit + side, addr: bitmap)) {
1822	mb_clear_bit(bit: *bit, addr: bitmap);
1823	(*bit) -= side;
1824	return 1;
1825	}
1826	else {
1827	(*bit) += side;
1828	mb_set_bit(bit: *bit, addr: bitmap);
1829	return -1;
1830	}
1831	}
1832
1833	static void mb_buddy_mark_free(struct ext4_buddy *e4b, int first, int last)
1834	{
1835	int max;
1836	int order = 1;
1837	void *buddy = mb_find_buddy(e4b, order, max: &max);
1838
1839	while (buddy) {
1840	void *buddy2;
1841
1842	/* Bits in range [first; last] are known to be set since
1843	* corresponding blocks were allocated. Bits in range
1844	* (first; last) will stay set because they form buddies on
1845	* upper layer. We just deal with borders if they don't
1846	* align with upper layer and then go up.
1847	* Releasing entire group is all about clearing
1848	* single bit of highest order buddy.
1849	*/
1850
1851	/* Example:
1852	* ---------------------------------
1853	* | 1 | 1 | 1 | 1 |
1854	* ---------------------------------
1855	* | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1856	* ---------------------------------
1857	* 0 1 2 3 4 5 6 7
1858	* \_____________________/
1859	*
1860	* Neither [1] nor [6] is aligned to above layer.
1861	* Left neighbour [0] is free, so mark it busy,
1862	* decrease bb_counters and extend range to
1863	* [0; 6]
1864	* Right neighbour [7] is busy. It can't be coaleasced with [6], so
1865	* mark [6] free, increase bb_counters and shrink range to
1866	* [0; 5].
1867	* Then shift range to [0; 2], go up and do the same.
1868	*/
1869
1870
1871	if (first & 1)
1872	e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(bit: &first, bitmap: buddy, side: -1);
1873	if (!(last & 1))
1874	e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(bit: &last, bitmap: buddy, side: 1);
1875	if (first > last)
1876	break;
1877	order++;
1878
1879	buddy2 = mb_find_buddy(e4b, order, max: &max);
1880	if (!buddy2) {
1881	mb_clear_bits(bm: buddy, cur: first, len: last - first + 1);
1882	e4b->bd_info->bb_counters[order - 1] += last - first + 1;
1883	break;
1884	}
1885	first >>= 1;
1886	last >>= 1;
1887	buddy = buddy2;
1888	}
1889	}
1890
1891	static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
1892	int first, int count)
1893	{
1894	int left_is_free = 0;
1895	int right_is_free = 0;
1896	int block;
1897	int last = first + count - 1;
1898	struct super_block *sb = e4b->bd_sb;
1899
1900	if (WARN_ON(count == 0))
1901	return;
1902	BUG_ON(last >= (sb->s_blocksize << 3));
1903	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
1904	/* Don't bother if the block group is corrupt. */
1905	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
1906	return;
1907
1908	mb_check_buddy(e4b);
1909	mb_free_blocks_double(inode, e4b, first, count);
1910
1911	/* access memory sequentially: check left neighbour,
1912	* clear range and then check right neighbour
1913	*/
1914	if (first != 0)
1915	left_is_free = !mb_test_bit(bit: first - 1, addr: e4b->bd_bitmap);
1916	block = mb_test_and_clear_bits(bm: e4b->bd_bitmap, cur: first, len: count);
1917	if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])
1918	right_is_free = !mb_test_bit(bit: last + 1, addr: e4b->bd_bitmap);
1919
1920	if (unlikely(block != -1)) {
1921	struct ext4_sb_info *sbi = EXT4_SB(sb);
1922	ext4_fsblk_t blocknr;
1923
1924	/*
1925	* Fastcommit replay can free already freed blocks which
1926	* corrupts allocation info. Regenerate it.
1927	*/
1928	if (sbi->s_mount_state & EXT4_FC_REPLAY) {
1929	mb_regenerate_buddy(e4b);
1930	goto check;
1931	}
1932
1933	blocknr = ext4_group_first_block_no(sb, group_no: e4b->bd_group);
1934	blocknr += EXT4_C2B(sbi, block);
1935	ext4_mark_group_bitmap_corrupted(sb, block_group: e4b->bd_group,
1936	EXT4_GROUP_INFO_BBITMAP_CORRUPT);
1937	ext4_grp_locked_error(sb, e4b->bd_group,
1938	inode ? inode->i_ino : 0, blocknr,
1939	"freeing already freed block (bit %u); block bitmap corrupt.",
1940	block);
1941	return;
1942	}
1943
1944	this_cpu_inc(discard_pa_seq);
1945	e4b->bd_info->bb_free += count;
1946	if (first < e4b->bd_info->bb_first_free)
1947	e4b->bd_info->bb_first_free = first;
1948
1949	/* let's maintain fragments counter */
1950	if (left_is_free && right_is_free)
1951	e4b->bd_info->bb_fragments--;
1952	else if (!left_is_free && !right_is_free)
1953	e4b->bd_info->bb_fragments++;
1954
1955	/* buddy[0] == bd_bitmap is a special case, so handle
1956	* it right away and let mb_buddy_mark_free stay free of
1957	* zero order checks.
1958	* Check if neighbours are to be coaleasced,
1959	* adjust bitmap bb_counters and borders appropriately.
1960	*/
1961	if (first & 1) {
1962	first += !left_is_free;
1963	e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;
1964	}
1965	if (!(last & 1)) {
1966	last -= !right_is_free;
1967	e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;
1968	}
1969
1970	if (first <= last)
1971	mb_buddy_mark_free(e4b, first: first >> 1, last: last >> 1);
1972
1973	mb_set_largest_free_order(sb, grp: e4b->bd_info);
1974	mb_update_avg_fragment_size(sb, grp: e4b->bd_info);
1975	check:
1976	mb_check_buddy(e4b);
1977	}
1978
1979	static int mb_find_extent(struct ext4_buddy *e4b, int block,
1980	int needed, struct ext4_free_extent *ex)
1981	{
1982	int max, order, next;
1983	void *buddy;
1984
1985	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1986	BUG_ON(ex == NULL);
1987
1988	buddy = mb_find_buddy(e4b, order: 0, max: &max);
1989	BUG_ON(buddy == NULL);
1990	BUG_ON(block >= max);
1991	if (mb_test_bit(bit: block, addr: buddy)) {
1992	ex->fe_len = 0;
1993	ex->fe_start = 0;
1994	ex->fe_group = 0;
1995	return 0;
1996	}
1997
1998	/* find actual order */
1999	order = mb_find_order_for_block(e4b, block);
2000
2001	ex->fe_len = (1 << order) - (block & ((1 << order) - 1));
2002	ex->fe_start = block;
2003	ex->fe_group = e4b->bd_group;
2004
2005	block = block >> order;
2006
2007	while (needed > ex->fe_len &&
2008	mb_find_buddy(e4b, order, max: &max)) {
2009
2010	if (block + 1 >= max)
2011	break;
2012
2013	next = (block + 1) * (1 << order);
2014	if (mb_test_bit(bit: next, addr: e4b->bd_bitmap))
2015	break;
2016
2017	order = mb_find_order_for_block(e4b, block: next);
2018
2019	block = next >> order;
2020	ex->fe_len += 1 << order;
2021	}
2022
2023	if (ex->fe_start + ex->fe_len > EXT4_CLUSTERS_PER_GROUP(e4b->bd_sb)) {
2024	/* Should never happen! (but apparently sometimes does?!?) */
2025	WARN_ON(1);
2026	ext4_grp_locked_error(e4b->bd_sb, e4b->bd_group, 0, 0,
2027	"corruption or bug in mb_find_extent "
2028	"block=%d, order=%d needed=%d ex=%u/%d/%d@%u",
2029	block, order, needed, ex->fe_group, ex->fe_start,
2030	ex->fe_len, ex->fe_logical);
2031	ex->fe_len = 0;
2032	ex->fe_start = 0;
2033	ex->fe_group = 0;
2034	}
2035	return ex->fe_len;
2036	}
2037
2038	static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
2039	{
2040	int ord;
2041	int mlen = 0;
2042	int max = 0;
2043	int cur;
2044	int start = ex->fe_start;
2045	int len = ex->fe_len;
2046	unsigned ret = 0;
2047	int len0 = len;
2048	void *buddy;
2049	bool split = false;
2050
2051	BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
2052	BUG_ON(e4b->bd_group != ex->fe_group);
2053	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
2054	mb_check_buddy(e4b);
2055	mb_mark_used_double(e4b, first: start, count: len);
2056
2057	this_cpu_inc(discard_pa_seq);
2058	e4b->bd_info->bb_free -= len;
2059	if (e4b->bd_info->bb_first_free == start)
2060	e4b->bd_info->bb_first_free += len;
2061
2062	/* let's maintain fragments counter */
2063	if (start != 0)
2064	mlen = !mb_test_bit(bit: start - 1, addr: e4b->bd_bitmap);
2065	if (start + len < EXT4_SB(sb: e4b->bd_sb)->s_mb_maxs[0])
2066	max = !mb_test_bit(bit: start + len, addr: e4b->bd_bitmap);
2067	if (mlen && max)
2068	e4b->bd_info->bb_fragments++;
2069	else if (!mlen && !max)
2070	e4b->bd_info->bb_fragments--;
2071
2072	/* let's maintain buddy itself */
2073	while (len) {
2074	if (!split)
2075	ord = mb_find_order_for_block(e4b, block: start);
2076
2077	if (((start >> ord) << ord) == start && len >= (1 << ord)) {
2078	/* the whole chunk may be allocated at once! */
2079	mlen = 1 << ord;
2080	if (!split)
2081	buddy = mb_find_buddy(e4b, order: ord, max: &max);
2082	else
2083	split = false;
2084	BUG_ON((start >> ord) >= max);
2085	mb_set_bit(bit: start >> ord, addr: buddy);
2086	e4b->bd_info->bb_counters[ord]--;
2087	start += mlen;
2088	len -= mlen;
2089	BUG_ON(len < 0);
2090	continue;
2091	}
2092
2093	/* store for history */
2094	if (ret == 0)
2095	ret = len | (ord << 16);
2096
2097	/* we have to split large buddy */
2098	BUG_ON(ord <= 0);
2099	buddy = mb_find_buddy(e4b, order: ord, max: &max);
2100	mb_set_bit(bit: start >> ord, addr: buddy);
2101	e4b->bd_info->bb_counters[ord]--;
2102
2103	ord--;
2104	cur = (start >> ord) & ~1U;
2105	buddy = mb_find_buddy(e4b, order: ord, max: &max);
2106	mb_clear_bit(bit: cur, addr: buddy);
2107	mb_clear_bit(bit: cur + 1, addr: buddy);
2108	e4b->bd_info->bb_counters[ord]++;
2109	e4b->bd_info->bb_counters[ord]++;
2110	split = true;
2111	}
2112	mb_set_largest_free_order(sb: e4b->bd_sb, grp: e4b->bd_info);
2113
2114	mb_update_avg_fragment_size(sb: e4b->bd_sb, grp: e4b->bd_info);
2115	mb_set_bits(bm: e4b->bd_bitmap, cur: ex->fe_start, len: len0);
2116	mb_check_buddy(e4b);
2117
2118	return ret;
2119	}
2120
2121	/*
2122	* Must be called under group lock!
2123	*/
2124	static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
2125	struct ext4_buddy *e4b)
2126	{
2127	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
2128	int ret;
2129
2130	BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
2131	BUG_ON(ac->ac_status == AC_STATUS_FOUND);
2132
2133	ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
2134	ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
2135	ret = mb_mark_used(e4b, ex: &ac->ac_b_ex);
2136
2137	/* preallocation can change ac_b_ex, thus we store actually
2138	* allocated blocks for history */
2139	ac->ac_f_ex = ac->ac_b_ex;
2140
2141	ac->ac_status = AC_STATUS_FOUND;
2142	ac->ac_tail = ret & 0xffff;
2143	ac->ac_buddy = ret >> 16;
2144
2145	/*
2146	* take the page reference. We want the page to be pinned
2147	* so that we don't get a ext4_mb_init_cache_call for this
2148	* group until we update the bitmap. That would mean we
2149	* double allocate blocks. The reference is dropped
2150	* in ext4_mb_release_context
2151	*/
2152	ac->ac_bitmap_page = e4b->bd_bitmap_page;
2153	get_page(page: ac->ac_bitmap_page);
2154	ac->ac_buddy_page = e4b->bd_buddy_page;
2155	get_page(page: ac->ac_buddy_page);
2156	/* store last allocated for subsequent stream allocation */
2157	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
2158	spin_lock(lock: &sbi->s_md_lock);
2159	sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
2160	sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
2161	spin_unlock(lock: &sbi->s_md_lock);
2162	}
2163	/*
2164	* As we've just preallocated more space than
2165	* user requested originally, we store allocated
2166	* space in a special descriptor.
2167	*/
2168	if (ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
2169	ext4_mb_new_preallocation(ac);
2170
2171	}
2172
2173	static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
2174	struct ext4_buddy *e4b,
2175	int finish_group)
2176	{
2177	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
2178	struct ext4_free_extent *bex = &ac->ac_b_ex;
2179	struct ext4_free_extent *gex = &ac->ac_g_ex;
2180
2181	if (ac->ac_status == AC_STATUS_FOUND)
2182	return;
2183	/*
2184	* We don't want to scan for a whole year
2185	*/
2186	if (ac->ac_found > sbi->s_mb_max_to_scan &&
2187	!(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2188	ac->ac_status = AC_STATUS_BREAK;
2189	return;
2190	}
2191
2192	/*
2193	* Haven't found good chunk so far, let's continue
2194	*/
2195	if (bex->fe_len < gex->fe_len)
2196	return;
2197
2198	if (finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
2199	ext4_mb_use_best_found(ac, e4b);
2200	}
2201
2202	/*
2203	* The routine checks whether found extent is good enough. If it is,
2204	* then the extent gets marked used and flag is set to the context
2205	* to stop scanning. Otherwise, the extent is compared with the
2206	* previous found extent and if new one is better, then it's stored
2207	* in the context. Later, the best found extent will be used, if
2208	* mballoc can't find good enough extent.
2209	*
2210	* The algorithm used is roughly as follows:
2211	*
2212	* * If free extent found is exactly as big as goal, then
2213	* stop the scan and use it immediately
2214	*
2215	* * If free extent found is smaller than goal, then keep retrying
2216	* upto a max of sbi->s_mb_max_to_scan times (default 200). After
2217	* that stop scanning and use whatever we have.
2218	*
2219	* * If free extent found is bigger than goal, then keep retrying
2220	* upto a max of sbi->s_mb_min_to_scan times (default 10) before
2221	* stopping the scan and using the extent.
2222	*
2223	*
2224	* FIXME: real allocation policy is to be designed yet!
2225	*/
2226	static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
2227	struct ext4_free_extent *ex,
2228	struct ext4_buddy *e4b)
2229	{
2230	struct ext4_free_extent *bex = &ac->ac_b_ex;
2231	struct ext4_free_extent *gex = &ac->ac_g_ex;
2232
2233	BUG_ON(ex->fe_len <= 0);
2234	BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
2235	BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
2236	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
2237
2238	ac->ac_found++;
2239	ac->ac_cX_found[ac->ac_criteria]++;
2240
2241	/*
2242	* The special case - take what you catch first
2243	*/
2244	if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2245	*bex = *ex;
2246	ext4_mb_use_best_found(ac, e4b);
2247	return;
2248	}
2249
2250	/*
2251	* Let's check whether the chuck is good enough
2252	*/
2253	if (ex->fe_len == gex->fe_len) {
2254	*bex = *ex;
2255	ext4_mb_use_best_found(ac, e4b);
2256	return;
2257	}
2258
2259	/*
2260	* If this is first found extent, just store it in the context
2261	*/
2262	if (bex->fe_len == 0) {
2263	*bex = *ex;
2264	return;
2265	}
2266
2267	/*
2268	* If new found extent is better, store it in the context
2269	*/
2270	if (bex->fe_len < gex->fe_len) {
2271	/* if the request isn't satisfied, any found extent
2272	* larger than previous best one is better */
2273	if (ex->fe_len > bex->fe_len)
2274	*bex = *ex;
2275	} else if (ex->fe_len > gex->fe_len) {
2276	/* if the request is satisfied, then we try to find
2277	* an extent that still satisfy the request, but is
2278	* smaller than previous one */
2279	if (ex->fe_len < bex->fe_len)
2280	*bex = *ex;
2281	}
2282
2283	ext4_mb_check_limits(ac, e4b, finish_group: 0);
2284	}
2285
2286	static noinline_for_stack
2287	void ext4_mb_try_best_found(struct ext4_allocation_context *ac,
2288	struct ext4_buddy *e4b)
2289	{
2290	struct ext4_free_extent ex = ac->ac_b_ex;
2291	ext4_group_t group = ex.fe_group;
2292	int max;
2293	int err;
2294
2295	BUG_ON(ex.fe_len <= 0);
2296	err = ext4_mb_load_buddy(sb: ac->ac_sb, group, e4b);
2297	if (err)
2298	return;
2299
2300	ext4_lock_group(sb: ac->ac_sb, group);
2301	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
2302	goto out;
2303
2304	max = mb_find_extent(e4b, block: ex.fe_start, needed: ex.fe_len, ex: &ex);
2305
2306	if (max > 0) {
2307	ac->ac_b_ex = ex;
2308	ext4_mb_use_best_found(ac, e4b);
2309	}
2310
2311	out:
2312	ext4_unlock_group(sb: ac->ac_sb, group);
2313	ext4_mb_unload_buddy(e4b);
2314	}
2315
2316	static noinline_for_stack
2317	int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
2318	struct ext4_buddy *e4b)
2319	{
2320	ext4_group_t group = ac->ac_g_ex.fe_group;
2321	int max;
2322	int err;
2323	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
2324	struct ext4_group_info *grp = ext4_get_group_info(sb: ac->ac_sb, group);
2325	struct ext4_free_extent ex;
2326
2327	if (!grp)
2328	return -EFSCORRUPTED;
2329	if (!(ac->ac_flags & (EXT4_MB_HINT_TRY_GOAL | EXT4_MB_HINT_GOAL_ONLY)))
2330	return 0;
2331	if (grp->bb_free == 0)
2332	return 0;
2333
2334	err = ext4_mb_load_buddy(sb: ac->ac_sb, group, e4b);
2335	if (err)
2336	return err;
2337
2338	ext4_lock_group(sb: ac->ac_sb, group);
2339	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
2340	goto out;
2341
2342	max = mb_find_extent(e4b, block: ac->ac_g_ex.fe_start,
2343	needed: ac->ac_g_ex.fe_len, ex: &ex);
2344	ex.fe_logical = 0xDEADFA11; /* debug value */
2345
2346	if (max >= ac->ac_g_ex.fe_len &&
2347	ac->ac_g_ex.fe_len == EXT4_B2C(sbi, sbi->s_stripe)) {
2348	ext4_fsblk_t start;
2349
2350	start = ext4_grp_offs_to_block(sb: ac->ac_sb, fex: &ex);
2351	/* use do_div to get remainder (would be 64-bit modulo) */
2352	if (do_div(start, sbi->s_stripe) == 0) {
2353	ac->ac_found++;
2354	ac->ac_b_ex = ex;
2355	ext4_mb_use_best_found(ac, e4b);
2356	}
2357	} else if (max >= ac->ac_g_ex.fe_len) {
2358	BUG_ON(ex.fe_len <= 0);
2359	BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
2360	BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
2361	ac->ac_found++;
2362	ac->ac_b_ex = ex;
2363	ext4_mb_use_best_found(ac, e4b);
2364	} else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
2365	/* Sometimes, caller may want to merge even small
2366	* number of blocks to an existing extent */
2367	BUG_ON(ex.fe_len <= 0);
2368	BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
2369	BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
2370	ac->ac_found++;
2371	ac->ac_b_ex = ex;
2372	ext4_mb_use_best_found(ac, e4b);
2373	}
2374	out:
2375	ext4_unlock_group(sb: ac->ac_sb, group);
2376	ext4_mb_unload_buddy(e4b);
2377
2378	return 0;
2379	}
2380
2381	/*
2382	* The routine scans buddy structures (not bitmap!) from given order
2383	* to max order and tries to find big enough chunk to satisfy the req
2384	*/
2385	static noinline_for_stack
2386	void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
2387	struct ext4_buddy *e4b)
2388	{
2389	struct super_block *sb = ac->ac_sb;
2390	struct ext4_group_info *grp = e4b->bd_info;
2391	void *buddy;
2392	int i;
2393	int k;
2394	int max;
2395
2396	BUG_ON(ac->ac_2order <= 0);
2397	for (i = ac->ac_2order; i < MB_NUM_ORDERS(sb); i++) {
2398	if (grp->bb_counters[i] == 0)
2399	continue;
2400
2401	buddy = mb_find_buddy(e4b, order: i, max: &max);
2402	if (WARN_RATELIMIT(buddy == NULL,
2403	"ext4: mb_simple_scan_group: mb_find_buddy failed, (%d)\n", i))
2404	continue;
2405
2406	k = mb_find_next_zero_bit(addr: buddy, max, start: 0);
2407	if (k >= max) {
2408	ext4_mark_group_bitmap_corrupted(sb: ac->ac_sb,
2409	block_group: e4b->bd_group,
2410	EXT4_GROUP_INFO_BBITMAP_CORRUPT);
2411	ext4_grp_locked_error(ac->ac_sb, e4b->bd_group, 0, 0,
2412	"%d free clusters of order %d. But found 0",
2413	grp->bb_counters[i], i);
2414	break;
2415	}
2416	ac->ac_found++;
2417	ac->ac_cX_found[ac->ac_criteria]++;
2418
2419	ac->ac_b_ex.fe_len = 1 << i;
2420	ac->ac_b_ex.fe_start = k << i;
2421	ac->ac_b_ex.fe_group = e4b->bd_group;
2422
2423	ext4_mb_use_best_found(ac, e4b);
2424
2425	BUG_ON(ac->ac_f_ex.fe_len != ac->ac_g_ex.fe_len);
2426
2427	if (EXT4_SB(sb)->s_mb_stats)
2428	atomic_inc(v: &EXT4_SB(sb)->s_bal_2orders);
2429
2430	break;
2431	}
2432	}
2433
2434	/*
2435	* The routine scans the group and measures all found extents.
2436	* In order to optimize scanning, caller must pass number of
2437	* free blocks in the group, so the routine can know upper limit.
2438	*/
2439	static noinline_for_stack
2440	void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
2441	struct ext4_buddy *e4b)
2442	{
2443	struct super_block *sb = ac->ac_sb;
2444	void *bitmap = e4b->bd_bitmap;
2445	struct ext4_free_extent ex;
2446	int i, j, freelen;
2447	int free;
2448
2449	free = e4b->bd_info->bb_free;
2450	if (WARN_ON(free <= 0))
2451	return;
2452
2453	i = e4b->bd_info->bb_first_free;
2454
2455	while (free && ac->ac_status == AC_STATUS_CONTINUE) {
2456	i = mb_find_next_zero_bit(addr: bitmap,
2457	EXT4_CLUSTERS_PER_GROUP(sb), start: i);
2458	if (i >= EXT4_CLUSTERS_PER_GROUP(sb)) {
2459	/*
2460	* IF we have corrupt bitmap, we won't find any
2461	* free blocks even though group info says we
2462	* have free blocks
2463	*/
2464	ext4_mark_group_bitmap_corrupted(sb, block_group: e4b->bd_group,
2465	EXT4_GROUP_INFO_BBITMAP_CORRUPT);
2466	ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
2467	"%d free clusters as per "
2468	"group info. But bitmap says 0",
2469	free);
2470	break;
2471	}
2472
2473	if (!ext4_mb_cr_expensive(cr: ac->ac_criteria)) {
2474	/*
2475	* In CR_GOAL_LEN_FAST and CR_BEST_AVAIL_LEN, we are
2476	* sure that this group will have a large enough
2477	* continuous free extent, so skip over the smaller free
2478	* extents
2479	*/
2480	j = mb_find_next_bit(addr: bitmap,
2481	EXT4_CLUSTERS_PER_GROUP(sb), start: i);
2482	freelen = j - i;
2483
2484	if (freelen < ac->ac_g_ex.fe_len) {
2485	i = j;
2486	free -= freelen;
2487	continue;
2488	}
2489	}
2490
2491	mb_find_extent(e4b, block: i, needed: ac->ac_g_ex.fe_len, ex: &ex);
2492	if (WARN_ON(ex.fe_len <= 0))
2493	break;
2494	if (free < ex.fe_len) {
2495	ext4_mark_group_bitmap_corrupted(sb, block_group: e4b->bd_group,
2496	EXT4_GROUP_INFO_BBITMAP_CORRUPT);
2497	ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
2498	"%d free clusters as per "
2499	"group info. But got %d blocks",
2500	free, ex.fe_len);
2501	/*
2502	* The number of free blocks differs. This mostly
2503	* indicate that the bitmap is corrupt. So exit
2504	* without claiming the space.
2505	*/
2506	break;
2507	}
2508	ex.fe_logical = 0xDEADC0DE; /* debug value */
2509	ext4_mb_measure_extent(ac, ex: &ex, e4b);
2510
2511	i += ex.fe_len;
2512	free -= ex.fe_len;
2513	}
2514
2515	ext4_mb_check_limits(ac, e4b, finish_group: 1);
2516	}
2517
2518	/*
2519	* This is a special case for storages like raid5
2520	* we try to find stripe-aligned chunks for stripe-size-multiple requests
2521	*/
2522	static noinline_for_stack
2523	void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
2524	struct ext4_buddy *e4b)
2525	{
2526	struct super_block *sb = ac->ac_sb;
2527	struct ext4_sb_info *sbi = EXT4_SB(sb);
2528	void *bitmap = e4b->bd_bitmap;
2529	struct ext4_free_extent ex;
2530	ext4_fsblk_t first_group_block;
2531	ext4_fsblk_t a;
2532	ext4_grpblk_t i, stripe;
2533	int max;
2534
2535	BUG_ON(sbi->s_stripe == 0);
2536
2537	/* find first stripe-aligned block in group */
2538	first_group_block = ext4_group_first_block_no(sb, group_no: e4b->bd_group);
2539
2540	a = first_group_block + sbi->s_stripe - 1;
2541	do_div(a, sbi->s_stripe);
2542	i = (a * sbi->s_stripe) - first_group_block;
2543
2544	stripe = EXT4_B2C(sbi, sbi->s_stripe);
2545	i = EXT4_B2C(sbi, i);
2546	while (i < EXT4_CLUSTERS_PER_GROUP(sb)) {
2547	if (!mb_test_bit(bit: i, addr: bitmap)) {
2548	max = mb_find_extent(e4b, block: i, needed: stripe, ex: &ex);
2549	if (max >= stripe) {
2550	ac->ac_found++;
2551	ac->ac_cX_found[ac->ac_criteria]++;
2552	ex.fe_logical = 0xDEADF00D; /* debug value */
2553	ac->ac_b_ex = ex;
2554	ext4_mb_use_best_found(ac, e4b);
2555	break;
2556	}
2557	}
2558	i += stripe;
2559	}
2560	}
2561
2562	/*
2563	* This is also called BEFORE we load the buddy bitmap.
2564	* Returns either 1 or 0 indicating that the group is either suitable
2565	* for the allocation or not.
2566	*/
2567	static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
2568	ext4_group_t group, enum criteria cr)
2569	{
2570	ext4_grpblk_t free, fragments;
2571	int flex_size = ext4_flex_bg_size(sbi: EXT4_SB(sb: ac->ac_sb));
2572	struct ext4_group_info *grp = ext4_get_group_info(sb: ac->ac_sb, group);
2573
2574	BUG_ON(cr < CR_POWER2_ALIGNED || cr >= EXT4_MB_NUM_CRS);
2575
2576	if (unlikely(!grp || EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))
2577	return false;
2578
2579	free = grp->bb_free;
2580	if (free == 0)
2581	return false;
2582
2583	fragments = grp->bb_fragments;
2584	if (fragments == 0)
2585	return false;
2586
2587	switch (cr) {
2588	case CR_POWER2_ALIGNED:
2589	BUG_ON(ac->ac_2order == 0);
2590
2591	/* Avoid using the first bg of a flexgroup for data files */
2592	if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&
2593	(flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) &&
2594	((group % flex_size) == 0))
2595	return false;
2596
2597	if (free < ac->ac_g_ex.fe_len)
2598	return false;
2599
2600	if (ac->ac_2order >= MB_NUM_ORDERS(ac->ac_sb))
2601	return true;
2602
2603	if (grp->bb_largest_free_order < ac->ac_2order)
2604	return false;
2605
2606	return true;
2607	case CR_GOAL_LEN_FAST:
2608	case CR_BEST_AVAIL_LEN:
2609	if ((free / fragments) >= ac->ac_g_ex.fe_len)
2610	return true;
2611	break;
2612	case CR_GOAL_LEN_SLOW:
2613	if (free >= ac->ac_g_ex.fe_len)
2614	return true;
2615	break;
2616	case CR_ANY_FREE:
2617	return true;
2618	default:
2619	BUG();
2620	}
2621
2622	return false;
2623	}
2624
2625	/*
2626	* This could return negative error code if something goes wrong
2627	* during ext4_mb_init_group(). This should not be called with
2628	* ext4_lock_group() held.
2629	*
2630	* Note: because we are conditionally operating with the group lock in
2631	* the EXT4_MB_STRICT_CHECK case, we need to fake out sparse in this
2632	* function using __acquire and __release. This means we need to be
2633	* super careful before messing with the error path handling via "goto
2634	* out"!
2635	*/
2636	static int ext4_mb_good_group_nolock(struct ext4_allocation_context *ac,
2637	ext4_group_t group, enum criteria cr)
2638	{
2639	struct ext4_group_info *grp = ext4_get_group_info(sb: ac->ac_sb, group);
2640	struct super_block *sb = ac->ac_sb;
2641	struct ext4_sb_info *sbi = EXT4_SB(sb);
2642	bool should_lock = ac->ac_flags & EXT4_MB_STRICT_CHECK;
2643	ext4_grpblk_t free;
2644	int ret = 0;
2645
2646	if (!grp)
2647	return -EFSCORRUPTED;
2648	if (sbi->s_mb_stats)
2649	atomic64_inc(v: &sbi->s_bal_cX_groups_considered[ac->ac_criteria]);
2650	if (should_lock) {
2651	ext4_lock_group(sb, group);
2652	__release(ext4_group_lock_ptr(sb, group));
2653	}
2654	free = grp->bb_free;
2655	if (free == 0)
2656	goto out;
2657	/*
2658	* In all criterias except CR_ANY_FREE we try to avoid groups that
2659	* can't possibly satisfy the full goal request due to insufficient
2660	* free blocks.
2661	*/
2662	if (cr < CR_ANY_FREE && free < ac->ac_g_ex.fe_len)
2663	goto out;
2664	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))
2665	goto out;
2666	if (should_lock) {
2667	__acquire(ext4_group_lock_ptr(sb, group));
2668	ext4_unlock_group(sb, group);
2669	}
2670
2671	/* We only do this if the grp has never been initialized */
2672	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
2673	struct ext4_group_desc *gdp =
2674	ext4_get_group_desc(sb, block_group: group, NULL);
2675	int ret;
2676
2677	/*
2678	* cr=CR_POWER2_ALIGNED/CR_GOAL_LEN_FAST is a very optimistic
2679	* search to find large good chunks almost for free. If buddy
2680	* data is not ready, then this optimization makes no sense. But
2681	* we never skip the first block group in a flex_bg, since this
2682	* gets used for metadata block allocation, and we want to make
2683	* sure we locate metadata blocks in the first block group in
2684	* the flex_bg if possible.
2685	*/
2686	if (!ext4_mb_cr_expensive(cr) &&
2687	(!sbi->s_log_groups_per_flex ||
2688	((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &&
2689	!(ext4_has_group_desc_csum(sb) &&
2690	(gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
2691	return 0;
2692	ret = ext4_mb_init_group(sb, group, GFP_NOFS);
2693	if (ret)
2694	return ret;
2695	}
2696
2697	if (should_lock) {
2698	ext4_lock_group(sb, group);
2699	__release(ext4_group_lock_ptr(sb, group));
2700	}
2701	ret = ext4_mb_good_group(ac, group, cr);
2702	out:
2703	if (should_lock) {
2704	__acquire(ext4_group_lock_ptr(sb, group));
2705	ext4_unlock_group(sb, group);
2706	}
2707	return ret;
2708	}
2709
2710	/*
2711	* Start prefetching @nr block bitmaps starting at @group.
2712	* Return the next group which needs to be prefetched.
2713	*/
2714	ext4_group_t ext4_mb_prefetch(struct super_block *sb, ext4_group_t group,
2715	unsigned int nr, int *cnt)
2716	{
2717	ext4_group_t ngroups = ext4_get_groups_count(sb);
2718	struct buffer_head *bh;
2719	struct blk_plug plug;
2720
2721	blk_start_plug(&plug);
2722	while (nr-- > 0) {
2723	struct ext4_group_desc *gdp = ext4_get_group_desc(sb, block_group: group,
2724	NULL);
2725	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
2726
2727	/*
2728	* Prefetch block groups with free blocks; but don't
2729	* bother if it is marked uninitialized on disk, since
2730	* it won't require I/O to read. Also only try to
2731	* prefetch once, so we avoid getblk() call, which can
2732	* be expensive.
2733	*/
2734	if (gdp && grp && !EXT4_MB_GRP_TEST_AND_SET_READ(grp) &&
2735	EXT4_MB_GRP_NEED_INIT(grp) &&
2736	ext4_free_group_clusters(sb, bg: gdp) > 0 ) {
2737	bh = ext4_read_block_bitmap_nowait(sb, block_group: group, ignore_locked: true);
2738	if (bh && !IS_ERR(ptr: bh)) {
2739	if (!buffer_uptodate(bh) && cnt)
2740	(*cnt)++;
2741	brelse(bh);
2742	}
2743	}
2744	if (++group >= ngroups)
2745	group = 0;
2746	}
2747	blk_finish_plug(&plug);
2748	return group;
2749	}
2750
2751	/*
2752	* Prefetching reads the block bitmap into the buffer cache; but we
2753	* need to make sure that the buddy bitmap in the page cache has been
2754	* initialized. Note that ext4_mb_init_group() will block if the I/O
2755	* is not yet completed, or indeed if it was not initiated by
2756	* ext4_mb_prefetch did not start the I/O.
2757	*
2758	* TODO: We should actually kick off the buddy bitmap setup in a work
2759	* queue when the buffer I/O is completed, so that we don't block
2760	* waiting for the block allocation bitmap read to finish when
2761	* ext4_mb_prefetch_fini is called from ext4_mb_regular_allocator().
2762	*/
2763	void ext4_mb_prefetch_fini(struct super_block *sb, ext4_group_t group,
2764	unsigned int nr)
2765	{
2766	struct ext4_group_desc *gdp;
2767	struct ext4_group_info *grp;
2768
2769	while (nr-- > 0) {
2770	if (!group)
2771	group = ext4_get_groups_count(sb);
2772	group--;
2773	gdp = ext4_get_group_desc(sb, block_group: group, NULL);
2774	grp = ext4_get_group_info(sb, group);
2775
2776	if (grp && gdp && EXT4_MB_GRP_NEED_INIT(grp) &&
2777	ext4_free_group_clusters(sb, bg: gdp) > 0) {
2778	if (ext4_mb_init_group(sb, group, GFP_NOFS))
2779	break;
2780	}
2781	}
2782	}
2783
2784	static noinline_for_stack int
2785	ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
2786	{
2787	ext4_group_t prefetch_grp = 0, ngroups, group, i;
2788	enum criteria new_cr, cr = CR_GOAL_LEN_FAST;
2789	int err = 0, first_err = 0;
2790	unsigned int nr = 0, prefetch_ios = 0;
2791	struct ext4_sb_info *sbi;
2792	struct super_block *sb;
2793	struct ext4_buddy e4b;
2794	int lost;
2795
2796	sb = ac->ac_sb;
2797	sbi = EXT4_SB(sb);
2798	ngroups = ext4_get_groups_count(sb);
2799	/* non-extent files are limited to low blocks/groups */
2800	if (!(ext4_test_inode_flag(inode: ac->ac_inode, bit: EXT4_INODE_EXTENTS)))
2801	ngroups = sbi->s_blockfile_groups;
2802
2803	BUG_ON(ac->ac_status == AC_STATUS_FOUND);
2804
2805	/* first, try the goal */
2806	err = ext4_mb_find_by_goal(ac, e4b: &e4b);
2807	if (err || ac->ac_status == AC_STATUS_FOUND)
2808	goto out;
2809
2810	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
2811	goto out;
2812
2813	/*
2814	* ac->ac_2order is set only if the fe_len is a power of 2
2815	* if ac->ac_2order is set we also set criteria to CR_POWER2_ALIGNED
2816	* so that we try exact allocation using buddy.
2817	*/
2818	i = fls(x: ac->ac_g_ex.fe_len);
2819	ac->ac_2order = 0;
2820	/*
2821	* We search using buddy data only if the order of the request
2822	* is greater than equal to the sbi_s_mb_order2_reqs
2823	* You can tune it via /sys/fs/ext4/<partition>/mb_order2_req
2824	* We also support searching for power-of-two requests only for
2825	* requests upto maximum buddy size we have constructed.
2826	*/
2827	if (i >= sbi->s_mb_order2_reqs && i <= MB_NUM_ORDERS(sb)) {
2828	if (is_power_of_2(n: ac->ac_g_ex.fe_len))
2829	ac->ac_2order = array_index_nospec(i - 1,
2830	MB_NUM_ORDERS(sb));
2831	}
2832
2833	/* if stream allocation is enabled, use global goal */
2834	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
2835	/* TBD: may be hot point */
2836	spin_lock(lock: &sbi->s_md_lock);
2837	ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
2838	ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
2839	spin_unlock(lock: &sbi->s_md_lock);
2840	}
2841
2842	/*
2843	* Let's just scan groups to find more-less suitable blocks We
2844	* start with CR_GOAL_LEN_FAST, unless it is power of 2
2845	* aligned, in which case let's do that faster approach first.
2846	*/
2847	if (ac->ac_2order)
2848	cr = CR_POWER2_ALIGNED;
2849	repeat:
2850	for (; cr < EXT4_MB_NUM_CRS && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
2851	ac->ac_criteria = cr;
2852	/*
2853	* searching for the right group start
2854	* from the goal value specified
2855	*/
2856	group = ac->ac_g_ex.fe_group;
2857	ac->ac_groups_linear_remaining = sbi->s_mb_max_linear_groups;
2858	prefetch_grp = group;
2859
2860	for (i = 0, new_cr = cr; i < ngroups; i++,
2861	ext4_mb_choose_next_group(ac, new_cr: &new_cr, group: &group, ngroups)) {
2862	int ret = 0;
2863
2864	cond_resched();
2865	if (new_cr != cr) {
2866	cr = new_cr;
2867	goto repeat;
2868	}
2869
2870	/*
2871	* Batch reads of the block allocation bitmaps
2872	* to get multiple READs in flight; limit
2873	* prefetching at inexpensive CR, otherwise mballoc
2874	* can spend a lot of time loading imperfect groups
2875	*/
2876	if ((prefetch_grp == group) &&
2877	(ext4_mb_cr_expensive(cr) ||
2878	prefetch_ios < sbi->s_mb_prefetch_limit)) {
2879	nr = sbi->s_mb_prefetch;
2880	if (ext4_has_feature_flex_bg(sb)) {
2881	nr = 1 << sbi->s_log_groups_per_flex;
2882	nr -= group & (nr - 1);
2883	nr = min(nr, sbi->s_mb_prefetch);
2884	}
2885	prefetch_grp = ext4_mb_prefetch(sb, group,
2886	nr, cnt: &prefetch_ios);
2887	}
2888
2889	/* This now checks without needing the buddy page */
2890	ret = ext4_mb_good_group_nolock(ac, group, cr);
2891	if (ret <= 0) {
2892	if (!first_err)
2893	first_err = ret;
2894	continue;
2895	}
2896
2897	err = ext4_mb_load_buddy(sb, group, e4b: &e4b);
2898	if (err)
2899	goto out;
2900
2901	ext4_lock_group(sb, group);
2902
2903	/*
2904	* We need to check again after locking the
2905	* block group
2906	*/
2907	ret = ext4_mb_good_group(ac, group, cr);
2908	if (ret == 0) {
2909	ext4_unlock_group(sb, group);
2910	ext4_mb_unload_buddy(e4b: &e4b);
2911	continue;
2912	}
2913
2914	ac->ac_groups_scanned++;
2915	if (cr == CR_POWER2_ALIGNED)
2916	ext4_mb_simple_scan_group(ac, e4b: &e4b);
2917	else {
2918	bool is_stripe_aligned = sbi->s_stripe &&
2919	!(ac->ac_g_ex.fe_len %
2920	EXT4_B2C(sbi, sbi->s_stripe));
2921
2922	if ((cr == CR_GOAL_LEN_FAST ||
2923	cr == CR_BEST_AVAIL_LEN) &&
2924	is_stripe_aligned)
2925	ext4_mb_scan_aligned(ac, e4b: &e4b);
2926
2927	if (ac->ac_status == AC_STATUS_CONTINUE)
2928	ext4_mb_complex_scan_group(ac, e4b: &e4b);
2929	}
2930
2931	ext4_unlock_group(sb, group);
2932	ext4_mb_unload_buddy(e4b: &e4b);
2933
2934	if (ac->ac_status != AC_STATUS_CONTINUE)
2935	break;
2936	}
2937	/* Processed all groups and haven't found blocks */
2938	if (sbi->s_mb_stats && i == ngroups)
2939	atomic64_inc(v: &sbi->s_bal_cX_failed[cr]);
2940
2941	if (i == ngroups && ac->ac_criteria == CR_BEST_AVAIL_LEN)
2942	/* Reset goal length to original goal length before
2943	* falling into CR_GOAL_LEN_SLOW */
2944	ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;
2945	}
2946
2947	if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
2948	!(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2949	/*
2950	* We've been searching too long. Let's try to allocate
2951	* the best chunk we've found so far
2952	*/
2953	ext4_mb_try_best_found(ac, e4b: &e4b);
2954	if (ac->ac_status != AC_STATUS_FOUND) {
2955	/*
2956	* Someone more lucky has already allocated it.
2957	* The only thing we can do is just take first
2958	* found block(s)
2959	*/
2960	lost = atomic_inc_return(v: &sbi->s_mb_lost_chunks);
2961	mb_debug(sb, "lost chunk, group: %u, start: %d, len: %d, lost: %d\n",
2962	ac->ac_b_ex.fe_group, ac->ac_b_ex.fe_start,
2963	ac->ac_b_ex.fe_len, lost);
2964
2965	ac->ac_b_ex.fe_group = 0;
2966	ac->ac_b_ex.fe_start = 0;
2967	ac->ac_b_ex.fe_len = 0;
2968	ac->ac_status = AC_STATUS_CONTINUE;
2969	ac->ac_flags |= EXT4_MB_HINT_FIRST;
2970	cr = CR_ANY_FREE;
2971	goto repeat;
2972	}
2973	}
2974
2975	if (sbi->s_mb_stats && ac->ac_status == AC_STATUS_FOUND)
2976	atomic64_inc(v: &sbi->s_bal_cX_hits[ac->ac_criteria]);
2977	out:
2978	if (!err && ac->ac_status != AC_STATUS_FOUND && first_err)
2979	err = first_err;
2980
2981	mb_debug(sb, "Best len %d, origin len %d, ac_status %u, ac_flags 0x%x, cr %d ret %d\n",
2982	ac->ac_b_ex.fe_len, ac->ac_o_ex.fe_len, ac->ac_status,
2983	ac->ac_flags, cr, err);
2984
2985	if (nr)
2986	ext4_mb_prefetch_fini(sb, group: prefetch_grp, nr);
2987
2988	return err;
2989	}
2990
2991	static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
2992	{
2993	struct super_block *sb = pde_data(inode: file_inode(f: seq->file));
2994	ext4_group_t group;
2995
2996	if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2997	return NULL;
2998	group = *pos + 1;
2999	return (void *) ((unsigned long) group);
3000	}
3001
3002	static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
3003	{
3004	struct super_block *sb = pde_data(inode: file_inode(f: seq->file));
3005	ext4_group_t group;
3006
3007	++*pos;
3008	if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
3009	return NULL;
3010	group = *pos + 1;
3011	return (void *) ((unsigned long) group);
3012	}
3013
3014	static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
3015	{
3016	struct super_block *sb = pde_data(inode: file_inode(f: seq->file));
3017	ext4_group_t group = (ext4_group_t) ((unsigned long) v);
3018	int i, err;
3019	char nbuf[16];
3020	struct ext4_buddy e4b;
3021	struct ext4_group_info *grinfo;
3022	unsigned char blocksize_bits = min_t(unsigned char,
3023	sb->s_blocksize_bits,
3024	EXT4_MAX_BLOCK_LOG_SIZE);
3025	struct sg {
3026	struct ext4_group_info info;
3027	ext4_grpblk_t counters[EXT4_MAX_BLOCK_LOG_SIZE + 2];
3028	} sg;
3029
3030	group--;
3031	if (group == 0)
3032	seq_puts(m: seq, s: "#group: free frags first ["
3033	" 2^0 2^1 2^2 2^3 2^4 2^5 2^6 "
3034	" 2^7 2^8 2^9 2^10 2^11 2^12 2^13 ]\n");
3035
3036	i = (blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
3037	sizeof(struct ext4_group_info);
3038
3039	grinfo = ext4_get_group_info(sb, group);
3040	if (!grinfo)
3041	return 0;
3042	/* Load the group info in memory only if not already loaded. */
3043	if (unlikely(EXT4_MB_GRP_NEED_INIT(grinfo))) {
3044	err = ext4_mb_load_buddy(sb, group, e4b: &e4b);
3045	if (err) {
3046	seq_printf(m: seq, fmt: "#%-5u: %s\n", group, ext4_decode_error(NULL, errno: err, nbuf));
3047	return 0;
3048	}
3049	ext4_mb_unload_buddy(e4b: &e4b);
3050	}
3051
3052	/*
3053	* We care only about free space counters in the group info and
3054	* these are safe to access even after the buddy has been unloaded
3055	*/
3056	memcpy(&sg, grinfo, i);
3057	seq_printf(m: seq, fmt: "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,
3058	sg.info.bb_fragments, sg.info.bb_first_free);
3059	for (i = 0; i <= 13; i++)
3060	seq_printf(m: seq, fmt: " %-5u", i <= blocksize_bits + 1 ?
3061	sg.info.bb_counters[i] : 0);
3062	seq_puts(m: seq, s: " ]");
3063	if (EXT4_MB_GRP_BBITMAP_CORRUPT(&sg.info))
3064	seq_puts(m: seq, s: " Block bitmap corrupted!");
3065	seq_puts(m: seq, s: "\n");
3066
3067	return 0;
3068	}
3069
3070	static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
3071	{
3072	}
3073
3074	const struct seq_operations ext4_mb_seq_groups_ops = {
3075	.start = ext4_mb_seq_groups_start,
3076	.next = ext4_mb_seq_groups_next,
3077	.stop = ext4_mb_seq_groups_stop,
3078	.show = ext4_mb_seq_groups_show,
3079	};
3080
3081	int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
3082	{
3083	struct super_block *sb = seq->private;
3084	struct ext4_sb_info *sbi = EXT4_SB(sb);
3085
3086	seq_puts(m: seq, s: "mballoc:\n");
3087	if (!sbi->s_mb_stats) {
3088	seq_puts(m: seq, s: "\tmb stats collection turned off.\n");
3089	seq_puts(
3090	m: seq,
3091	s: "\tTo enable, please write \"1\" to sysfs file mb_stats.\n");
3092	return 0;
3093	}
3094	seq_printf(m: seq, fmt: "\treqs: %u\n", atomic_read(v: &sbi->s_bal_reqs));
3095	seq_printf(m: seq, fmt: "\tsuccess: %u\n", atomic_read(v: &sbi->s_bal_success));
3096
3097	seq_printf(m: seq, fmt: "\tgroups_scanned: %u\n",
3098	atomic_read(v: &sbi->s_bal_groups_scanned));
3099
3100	/* CR_POWER2_ALIGNED stats */
3101	seq_puts(m: seq, s: "\tcr_p2_aligned_stats:\n");
3102	seq_printf(m: seq, fmt: "\t\thits: %llu\n",
3103	atomic64_read(v: &sbi->s_bal_cX_hits[CR_POWER2_ALIGNED]));
3104	seq_printf(
3105	m: seq, fmt: "\t\tgroups_considered: %llu\n",
3106	atomic64_read(
3107	v: &sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]));
3108	seq_printf(m: seq, fmt: "\t\textents_scanned: %u\n",
3109	atomic_read(v: &sbi->s_bal_cX_ex_scanned[CR_POWER2_ALIGNED]));
3110	seq_printf(m: seq, fmt: "\t\tuseless_loops: %llu\n",
3111	atomic64_read(v: &sbi->s_bal_cX_failed[CR_POWER2_ALIGNED]));
3112	seq_printf(m: seq, fmt: "\t\tbad_suggestions: %u\n",
3113	atomic_read(v: &sbi->s_bal_p2_aligned_bad_suggestions));
3114
3115	/* CR_GOAL_LEN_FAST stats */
3116	seq_puts(m: seq, s: "\tcr_goal_fast_stats:\n");
3117	seq_printf(m: seq, fmt: "\t\thits: %llu\n",
3118	atomic64_read(v: &sbi->s_bal_cX_hits[CR_GOAL_LEN_FAST]));
3119	seq_printf(m: seq, fmt: "\t\tgroups_considered: %llu\n",
3120	atomic64_read(
3121	v: &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_FAST]));
3122	seq_printf(m: seq, fmt: "\t\textents_scanned: %u\n",
3123	atomic_read(v: &sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_FAST]));
3124	seq_printf(m: seq, fmt: "\t\tuseless_loops: %llu\n",
3125	atomic64_read(v: &sbi->s_bal_cX_failed[CR_GOAL_LEN_FAST]));
3126	seq_printf(m: seq, fmt: "\t\tbad_suggestions: %u\n",
3127	atomic_read(v: &sbi->s_bal_goal_fast_bad_suggestions));
3128
3129	/* CR_BEST_AVAIL_LEN stats */
3130	seq_puts(m: seq, s: "\tcr_best_avail_stats:\n");
3131	seq_printf(m: seq, fmt: "\t\thits: %llu\n",
3132	atomic64_read(v: &sbi->s_bal_cX_hits[CR_BEST_AVAIL_LEN]));
3133	seq_printf(
3134	m: seq, fmt: "\t\tgroups_considered: %llu\n",
3135	atomic64_read(
3136	v: &sbi->s_bal_cX_groups_considered[CR_BEST_AVAIL_LEN]));
3137	seq_printf(m: seq, fmt: "\t\textents_scanned: %u\n",
3138	atomic_read(v: &sbi->s_bal_cX_ex_scanned[CR_BEST_AVAIL_LEN]));
3139	seq_printf(m: seq, fmt: "\t\tuseless_loops: %llu\n",
3140	atomic64_read(v: &sbi->s_bal_cX_failed[CR_BEST_AVAIL_LEN]));
3141	seq_printf(m: seq, fmt: "\t\tbad_suggestions: %u\n",
3142	atomic_read(v: &sbi->s_bal_best_avail_bad_suggestions));
3143
3144	/* CR_GOAL_LEN_SLOW stats */
3145	seq_puts(m: seq, s: "\tcr_goal_slow_stats:\n");
3146	seq_printf(m: seq, fmt: "\t\thits: %llu\n",
3147	atomic64_read(v: &sbi->s_bal_cX_hits[CR_GOAL_LEN_SLOW]));
3148	seq_printf(m: seq, fmt: "\t\tgroups_considered: %llu\n",
3149	atomic64_read(
3150	v: &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_SLOW]));
3151	seq_printf(m: seq, fmt: "\t\textents_scanned: %u\n",
3152	atomic_read(v: &sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_SLOW]));
3153	seq_printf(m: seq, fmt: "\t\tuseless_loops: %llu\n",
3154	atomic64_read(v: &sbi->s_bal_cX_failed[CR_GOAL_LEN_SLOW]));
3155
3156	/* CR_ANY_FREE stats */
3157	seq_puts(m: seq, s: "\tcr_any_free_stats:\n");
3158	seq_printf(m: seq, fmt: "\t\thits: %llu\n",
3159	atomic64_read(v: &sbi->s_bal_cX_hits[CR_ANY_FREE]));
3160	seq_printf(
3161	m: seq, fmt: "\t\tgroups_considered: %llu\n",
3162	atomic64_read(v: &sbi->s_bal_cX_groups_considered[CR_ANY_FREE]));
3163	seq_printf(m: seq, fmt: "\t\textents_scanned: %u\n",
3164	atomic_read(v: &sbi->s_bal_cX_ex_scanned[CR_ANY_FREE]));
3165	seq_printf(m: seq, fmt: "\t\tuseless_loops: %llu\n",
3166	atomic64_read(v: &sbi->s_bal_cX_failed[CR_ANY_FREE]));
3167
3168	/* Aggregates */
3169	seq_printf(m: seq, fmt: "\textents_scanned: %u\n",
3170	atomic_read(v: &sbi->s_bal_ex_scanned));
3171	seq_printf(m: seq, fmt: "\t\tgoal_hits: %u\n", atomic_read(v: &sbi->s_bal_goals));
3172	seq_printf(m: seq, fmt: "\t\tlen_goal_hits: %u\n",
3173	atomic_read(v: &sbi->s_bal_len_goals));
3174	seq_printf(m: seq, fmt: "\t\t2^n_hits: %u\n", atomic_read(v: &sbi->s_bal_2orders));
3175	seq_printf(m: seq, fmt: "\t\tbreaks: %u\n", atomic_read(v: &sbi->s_bal_breaks));
3176	seq_printf(m: seq, fmt: "\t\tlost: %u\n", atomic_read(v: &sbi->s_mb_lost_chunks));
3177	seq_printf(m: seq, fmt: "\tbuddies_generated: %u/%u\n",
3178	atomic_read(v: &sbi->s_mb_buddies_generated),
3179	ext4_get_groups_count(sb));
3180	seq_printf(m: seq, fmt: "\tbuddies_time_used: %llu\n",
3181	atomic64_read(v: &sbi->s_mb_generation_time));
3182	seq_printf(m: seq, fmt: "\tpreallocated: %u\n",
3183	atomic_read(v: &sbi->s_mb_preallocated));
3184	seq_printf(m: seq, fmt: "\tdiscarded: %u\n", atomic_read(v: &sbi->s_mb_discarded));
3185	return 0;
3186	}
3187
3188	static void *ext4_mb_seq_structs_summary_start(struct seq_file *seq, loff_t *pos)
3189	__acquires(&EXT4_SB(sb)->s_mb_rb_lock)
3190	{
3191	struct super_block *sb = pde_data(inode: file_inode(f: seq->file));
3192	unsigned long position;
3193
3194	if (*pos < 0 || *pos >= 2*MB_NUM_ORDERS(sb))
3195	return NULL;
3196	position = *pos + 1;
3197	return (void *) ((unsigned long) position);
3198	}
3199
3200	static void *ext4_mb_seq_structs_summary_next(struct seq_file *seq, void *v, loff_t *pos)
3201	{
3202	struct super_block *sb = pde_data(inode: file_inode(f: seq->file));
3203	unsigned long position;
3204
3205	++*pos;
3206	if (*pos < 0 || *pos >= 2*MB_NUM_ORDERS(sb))
3207	return NULL;
3208	position = *pos + 1;
3209	return (void *) ((unsigned long) position);
3210	}
3211
3212	static int ext4_mb_seq_structs_summary_show(struct seq_file *seq, void *v)
3213	{
3214	struct super_block *sb = pde_data(inode: file_inode(f: seq->file));
3215	struct ext4_sb_info *sbi = EXT4_SB(sb);
3216	unsigned long position = ((unsigned long) v);
3217	struct ext4_group_info *grp;
3218	unsigned int count;
3219
3220	position--;
3221	if (position >= MB_NUM_ORDERS(sb)) {
3222	position -= MB_NUM_ORDERS(sb);
3223	if (position == 0)
3224	seq_puts(m: seq, s: "avg_fragment_size_lists:\n");
3225
3226	count = 0;
3227	read_lock(&sbi->s_mb_avg_fragment_size_locks[position]);
3228	list_for_each_entry(grp, &sbi->s_mb_avg_fragment_size[position],
3229	bb_avg_fragment_size_node)
3230	count++;
3231	read_unlock(&sbi->s_mb_avg_fragment_size_locks[position]);
3232	seq_printf(m: seq, fmt: "\tlist_order_%u_groups: %u\n",
3233	(unsigned int)position, count);
3234	return 0;
3235	}
3236
3237	if (position == 0) {
3238	seq_printf(m: seq, fmt: "optimize_scan: %d\n",
3239	test_opt2(sb, MB_OPTIMIZE_SCAN) ? 1 : 0);
3240	seq_puts(m: seq, s: "max_free_order_lists:\n");
3241	}
3242	count = 0;
3243	read_lock(&sbi->s_mb_largest_free_orders_locks[position]);
3244	list_for_each_entry(grp, &sbi->s_mb_largest_free_orders[position],
3245	bb_largest_free_order_node)
3246	count++;
3247	read_unlock(&sbi->s_mb_largest_free_orders_locks[position]);
3248	seq_printf(m: seq, fmt: "\tlist_order_%u_groups: %u\n",
3249	(unsigned int)position, count);
3250
3251	return 0;
3252	}
3253
3254	static void ext4_mb_seq_structs_summary_stop(struct seq_file *seq, void *v)
3255	{
3256	}
3257
3258	const struct seq_operations ext4_mb_seq_structs_summary_ops = {
3259	.start = ext4_mb_seq_structs_summary_start,
3260	.next = ext4_mb_seq_structs_summary_next,
3261	.stop = ext4_mb_seq_structs_summary_stop,
3262	.show = ext4_mb_seq_structs_summary_show,
3263	};
3264
3265	static struct kmem_cache *get_groupinfo_cache(int blocksize_bits)
3266	{
3267	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
3268	struct kmem_cache *cachep = ext4_groupinfo_caches[cache_index];
3269
3270	BUG_ON(!cachep);
3271	return cachep;
3272	}
3273
3274	/*
3275	* Allocate the top-level s_group_info array for the specified number
3276	* of groups
3277	*/
3278	int ext4_mb_alloc_groupinfo(struct super_block *sb, ext4_group_t ngroups)
3279	{
3280	struct ext4_sb_info *sbi = EXT4_SB(sb);
3281	unsigned size;
3282	struct ext4_group_info ***old_groupinfo, ***new_groupinfo;
3283
3284	size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>
3285	EXT4_DESC_PER_BLOCK_BITS(sb);
3286	if (size <= sbi->s_group_info_size)
3287	return 0;
3288
3289	size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);
3290	new_groupinfo = kvzalloc(size, GFP_KERNEL);
3291	if (!new_groupinfo) {
3292	ext4_msg(sb, KERN_ERR, "can't allocate buddy meta group");
3293	return -ENOMEM;
3294	}
3295	rcu_read_lock();
3296	old_groupinfo = rcu_dereference(sbi->s_group_info);
3297	if (old_groupinfo)
3298	memcpy(new_groupinfo, old_groupinfo,
3299	sbi->s_group_info_size * sizeof(*sbi->s_group_info));
3300	rcu_read_unlock();
3301	rcu_assign_pointer(sbi->s_group_info, new_groupinfo);
3302	sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);
3303	if (old_groupinfo)
3304	ext4_kvfree_array_rcu(to_free: old_groupinfo);
3305	ext4_debug("allocated s_groupinfo array for %d meta_bg's\n",
3306	sbi->s_group_info_size);
3307	return 0;
3308	}
3309
3310	/* Create and initialize ext4_group_info data for the given group. */
3311	int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
3312	struct ext4_group_desc *desc)
3313	{
3314	int i;
3315	int metalen = 0;
3316	int idx = group >> EXT4_DESC_PER_BLOCK_BITS(sb);
3317	struct ext4_sb_info *sbi = EXT4_SB(sb);
3318	struct ext4_group_info **meta_group_info;
3319	struct kmem_cache *cachep = get_groupinfo_cache(blocksize_bits: sb->s_blocksize_bits);
3320
3321	/*
3322	* First check if this group is the first of a reserved block.
3323	* If it's true, we have to allocate a new table of pointers
3324	* to ext4_group_info structures
3325	*/
3326	if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
3327	metalen = sizeof(*meta_group_info) <<
3328	EXT4_DESC_PER_BLOCK_BITS(sb);
3329	meta_group_info = kmalloc(size: metalen, GFP_NOFS);
3330	if (meta_group_info == NULL) {
3331	ext4_msg(sb, KERN_ERR, "can't allocate mem "
3332	"for a buddy group");
3333	return -ENOMEM;
3334	}
3335	rcu_read_lock();
3336	rcu_dereference(sbi->s_group_info)[idx] = meta_group_info;
3337	rcu_read_unlock();
3338	}
3339
3340	meta_group_info = sbi_array_rcu_deref(sbi, s_group_info, idx);
3341	i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);
3342
3343	meta_group_info[i] = kmem_cache_zalloc(k: cachep, GFP_NOFS);
3344	if (meta_group_info[i] == NULL) {
3345	ext4_msg(sb, KERN_ERR, "can't allocate buddy mem");
3346	goto exit_group_info;
3347	}
3348	set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
3349	addr: &(meta_group_info[i]->bb_state));
3350
3351	/*
3352	* initialize bb_free to be able to skip
3353	* empty groups without initialization
3354	*/
3355	if (ext4_has_group_desc_csum(sb) &&
3356	(desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
3357	meta_group_info[i]->bb_free =
3358	ext4_free_clusters_after_init(sb, block_group: group, gdp: desc);
3359	} else {
3360	meta_group_info[i]->bb_free =
3361	ext4_free_group_clusters(sb, bg: desc);
3362	}
3363
3364	INIT_LIST_HEAD(list: &meta_group_info[i]->bb_prealloc_list);
3365	init_rwsem(&meta_group_info[i]->alloc_sem);
3366	meta_group_info[i]->bb_free_root = RB_ROOT;
3367	INIT_LIST_HEAD(list: &meta_group_info[i]->bb_largest_free_order_node);
3368	INIT_LIST_HEAD(list: &meta_group_info[i]->bb_avg_fragment_size_node);
3369	meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
3370	meta_group_info[i]->bb_avg_fragment_size_order = -1; /* uninit */
3371	meta_group_info[i]->bb_group = group;
3372
3373	mb_group_bb_bitmap_alloc(sb, grp: meta_group_info[i], group);
3374	return 0;
3375
3376	exit_group_info:
3377	/* If a meta_group_info table has been allocated, release it now */
3378	if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
3379	struct ext4_group_info ***group_info;
3380
3381	rcu_read_lock();
3382	group_info = rcu_dereference(sbi->s_group_info);
3383	kfree(objp: group_info[idx]);
3384	group_info[idx] = NULL;
3385	rcu_read_unlock();
3386	}
3387	return -ENOMEM;
3388	} /* ext4_mb_add_groupinfo */
3389
3390	static int ext4_mb_init_backend(struct super_block *sb)
3391	{
3392	ext4_group_t ngroups = ext4_get_groups_count(sb);
3393	ext4_group_t i;
3394	struct ext4_sb_info *sbi = EXT4_SB(sb);
3395	int err;
3396	struct ext4_group_desc *desc;
3397	struct ext4_group_info ***group_info;
3398	struct kmem_cache *cachep;
3399
3400	err = ext4_mb_alloc_groupinfo(sb, ngroups);
3401	if (err)
3402	return err;
3403
3404	sbi->s_buddy_cache = new_inode(sb);
3405	if (sbi->s_buddy_cache == NULL) {
3406	ext4_msg(sb, KERN_ERR, "can't get new inode");
3407	goto err_freesgi;
3408	}
3409	/* To avoid potentially colliding with an valid on-disk inode number,
3410	* use EXT4_BAD_INO for the buddy cache inode number. This inode is
3411	* not in the inode hash, so it should never be found by iget(), but
3412	* this will avoid confusion if it ever shows up during debugging. */
3413	sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;
3414	EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
3415	for (i = 0; i < ngroups; i++) {
3416	cond_resched();
3417	desc = ext4_get_group_desc(sb, block_group: i, NULL);
3418	if (desc == NULL) {
3419	ext4_msg(sb, KERN_ERR, "can't read descriptor %u", i);
3420	goto err_freebuddy;
3421	}
3422	if (ext4_mb_add_groupinfo(sb, group: i, desc) != 0)
3423	goto err_freebuddy;
3424	}
3425
3426	if (ext4_has_feature_flex_bg(sb)) {
3427	/* a single flex group is supposed to be read by a single IO.
3428	* 2 ^ s_log_groups_per_flex != UINT_MAX as s_mb_prefetch is
3429	* unsigned integer, so the maximum shift is 32.
3430	*/
3431	if (sbi->s_es->s_log_groups_per_flex >= 32) {
3432	ext4_msg(sb, KERN_ERR, "too many log groups per flexible block group");
3433	goto err_freebuddy;
3434	}
3435	sbi->s_mb_prefetch = min_t(uint, 1 << sbi->s_es->s_log_groups_per_flex,
3436	BLK_MAX_SEGMENT_SIZE >> (sb->s_blocksize_bits - 9));
3437	sbi->s_mb_prefetch *= 8; /* 8 prefetch IOs in flight at most */
3438	} else {
3439	sbi->s_mb_prefetch = 32;
3440	}
3441	if (sbi->s_mb_prefetch > ext4_get_groups_count(sb))
3442	sbi->s_mb_prefetch = ext4_get_groups_count(sb);
3443	/* now many real IOs to prefetch within a single allocation at cr=0
3444	* given cr=0 is an CPU-related optimization we shouldn't try to
3445	* load too many groups, at some point we should start to use what
3446	* we've got in memory.
3447	* with an average random access time 5ms, it'd take a second to get
3448	* 200 groups (* N with flex_bg), so let's make this limit 4
3449	*/
3450	sbi->s_mb_prefetch_limit = sbi->s_mb_prefetch * 4;
3451	if (sbi->s_mb_prefetch_limit > ext4_get_groups_count(sb))
3452	sbi->s_mb_prefetch_limit = ext4_get_groups_count(sb);
3453
3454	return 0;
3455
3456	err_freebuddy:
3457	cachep = get_groupinfo_cache(blocksize_bits: sb->s_blocksize_bits);
3458	while (i-- > 0) {
3459	struct ext4_group_info *grp = ext4_get_group_info(sb, group: i);
3460
3461	if (grp)
3462	kmem_cache_free(s: cachep, objp: grp);
3463	}
3464	i = sbi->s_group_info_size;
3465	rcu_read_lock();
3466	group_info = rcu_dereference(sbi->s_group_info);
3467	while (i-- > 0)
3468	kfree(objp: group_info[i]);
3469	rcu_read_unlock();
3470	iput(sbi->s_buddy_cache);
3471	err_freesgi:
3472	rcu_read_lock();
3473	kvfree(rcu_dereference(sbi->s_group_info));
3474	rcu_read_unlock();
3475	return -ENOMEM;
3476	}
3477
3478	static void ext4_groupinfo_destroy_slabs(void)
3479	{
3480	int i;
3481
3482	for (i = 0; i < NR_GRPINFO_CACHES; i++) {
3483	kmem_cache_destroy(s: ext4_groupinfo_caches[i]);
3484	ext4_groupinfo_caches[i] = NULL;
3485	}
3486	}
3487
3488	static int ext4_groupinfo_create_slab(size_t size)
3489	{
3490	static DEFINE_MUTEX(ext4_grpinfo_slab_create_mutex);
3491	int slab_size;
3492	int blocksize_bits = order_base_2(size);
3493	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
3494	struct kmem_cache *cachep;
3495
3496	if (cache_index >= NR_GRPINFO_CACHES)
3497	return -EINVAL;
3498
3499	if (unlikely(cache_index < 0))
3500	cache_index = 0;
3501
3502	mutex_lock(&ext4_grpinfo_slab_create_mutex);
3503	if (ext4_groupinfo_caches[cache_index]) {
3504	mutex_unlock(lock: &ext4_grpinfo_slab_create_mutex);
3505	return 0; /* Already created */
3506	}
3507
3508	slab_size = offsetof(struct ext4_group_info,
3509	bb_counters[blocksize_bits + 2]);
3510
3511	cachep = kmem_cache_create(name: ext4_groupinfo_slab_names[cache_index],
3512	size: slab_size, align: 0, SLAB_RECLAIM_ACCOUNT,
3513	NULL);
3514
3515	ext4_groupinfo_caches[cache_index] = cachep;
3516
3517	mutex_unlock(lock: &ext4_grpinfo_slab_create_mutex);
3518	if (!cachep) {
3519	printk(KERN_EMERG
3520	"EXT4-fs: no memory for groupinfo slab cache\n");
3521	return -ENOMEM;
3522	}
3523
3524	return 0;
3525	}
3526
3527	static void ext4_discard_work(struct work_struct *work)
3528	{
3529	struct ext4_sb_info *sbi = container_of(work,
3530	struct ext4_sb_info, s_discard_work);
3531	struct super_block *sb = sbi->s_sb;
3532	struct ext4_free_data *fd, *nfd;
3533	struct ext4_buddy e4b;
3534	LIST_HEAD(discard_list);
3535	ext4_group_t grp, load_grp;
3536	int err = 0;
3537
3538	spin_lock(lock: &sbi->s_md_lock);
3539	list_splice_init(list: &sbi->s_discard_list, head: &discard_list);
3540	spin_unlock(lock: &sbi->s_md_lock);
3541
3542	load_grp = UINT_MAX;
3543	list_for_each_entry_safe(fd, nfd, &discard_list, efd_list) {
3544	/*
3545	* If filesystem is umounting or no memory or suffering
3546	* from no space, give up the discard
3547	*/
3548	if ((sb->s_flags & SB_ACTIVE) && !err &&
3549	!atomic_read(v: &sbi->s_retry_alloc_pending)) {
3550	grp = fd->efd_group;
3551	if (grp != load_grp) {
3552	if (load_grp != UINT_MAX)
3553	ext4_mb_unload_buddy(e4b: &e4b);
3554
3555	err = ext4_mb_load_buddy(sb, group: grp, e4b: &e4b);
3556	if (err) {
3557	kmem_cache_free(s: ext4_free_data_cachep, objp: fd);
3558	load_grp = UINT_MAX;
3559	continue;
3560	} else {
3561	load_grp = grp;
3562	}
3563	}
3564
3565	ext4_lock_group(sb, group: grp);
3566	ext4_try_to_trim_range(sb, e4b: &e4b, start: fd->efd_start_cluster,
3567	max: fd->efd_start_cluster + fd->efd_count - 1, minblocks: 1);
3568	ext4_unlock_group(sb, group: grp);
3569	}
3570	kmem_cache_free(s: ext4_free_data_cachep, objp: fd);
3571	}
3572
3573	if (load_grp != UINT_MAX)
3574	ext4_mb_unload_buddy(e4b: &e4b);
3575	}
3576
3577	int ext4_mb_init(struct super_block *sb)
3578	{
3579	struct ext4_sb_info *sbi = EXT4_SB(sb);
3580	unsigned i, j;
3581	unsigned offset, offset_incr;
3582	unsigned max;
3583	int ret;
3584
3585	i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_offsets);
3586
3587	sbi->s_mb_offsets = kmalloc(size: i, GFP_KERNEL);
3588	if (sbi->s_mb_offsets == NULL) {
3589	ret = -ENOMEM;
3590	goto out;
3591	}
3592
3593	i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_maxs);
3594	sbi->s_mb_maxs = kmalloc(size: i, GFP_KERNEL);
3595	if (sbi->s_mb_maxs == NULL) {
3596	ret = -ENOMEM;
3597	goto out;
3598	}
3599
3600	ret = ext4_groupinfo_create_slab(size: sb->s_blocksize);
3601	if (ret < 0)
3602	goto out;
3603
3604	/* order 0 is regular bitmap */
3605	sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
3606	sbi->s_mb_offsets[0] = 0;
3607
3608	i = 1;
3609	offset = 0;
3610	offset_incr = 1 << (sb->s_blocksize_bits - 1);
3611	max = sb->s_blocksize << 2;
3612	do {
3613	sbi->s_mb_offsets[i] = offset;
3614	sbi->s_mb_maxs[i] = max;
3615	offset += offset_incr;
3616	offset_incr = offset_incr >> 1;
3617	max = max >> 1;
3618	i++;
3619	} while (i < MB_NUM_ORDERS(sb));
3620
3621	sbi->s_mb_avg_fragment_size =
3622	kmalloc_array(MB_NUM_ORDERS(sb), size: sizeof(struct list_head),
3623	GFP_KERNEL);
3624	if (!sbi->s_mb_avg_fragment_size) {
3625	ret = -ENOMEM;
3626	goto out;
3627	}
3628	sbi->s_mb_avg_fragment_size_locks =
3629	kmalloc_array(MB_NUM_ORDERS(sb), size: sizeof(rwlock_t),
3630	GFP_KERNEL);
3631	if (!sbi->s_mb_avg_fragment_size_locks) {
3632	ret = -ENOMEM;
3633	goto out;
3634	}
3635	for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
3636	INIT_LIST_HEAD(list: &sbi->s_mb_avg_fragment_size[i]);
3637	rwlock_init(&sbi->s_mb_avg_fragment_size_locks[i]);
3638	}
3639	sbi->s_mb_largest_free_orders =
3640	kmalloc_array(MB_NUM_ORDERS(sb), size: sizeof(struct list_head),
3641	GFP_KERNEL);
3642	if (!sbi->s_mb_largest_free_orders) {
3643	ret = -ENOMEM;
3644	goto out;
3645	}
3646	sbi->s_mb_largest_free_orders_locks =
3647	kmalloc_array(MB_NUM_ORDERS(sb), size: sizeof(rwlock_t),
3648	GFP_KERNEL);
3649	if (!sbi->s_mb_largest_free_orders_locks) {
3650	ret = -ENOMEM;
3651	goto out;
3652	}
3653	for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
3654	INIT_LIST_HEAD(list: &sbi->s_mb_largest_free_orders[i]);
3655	rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
3656	}
3657
3658	spin_lock_init(&sbi->s_md_lock);
3659	sbi->s_mb_free_pending = 0;
3660	INIT_LIST_HEAD(list: &sbi->s_freed_data_list[0]);
3661	INIT_LIST_HEAD(list: &sbi->s_freed_data_list[1]);
3662	INIT_LIST_HEAD(list: &sbi->s_discard_list);
3663	INIT_WORK(&sbi->s_discard_work, ext4_discard_work);
3664	atomic_set(v: &sbi->s_retry_alloc_pending, i: 0);
3665
3666	sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
3667	sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
3668	sbi->s_mb_stats = MB_DEFAULT_STATS;
3669	sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
3670	sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
3671	sbi->s_mb_best_avail_max_trim_order = MB_DEFAULT_BEST_AVAIL_TRIM_ORDER;
3672
3673	/*
3674	* The default group preallocation is 512, which for 4k block
3675	* sizes translates to 2 megabytes. However for bigalloc file
3676	* systems, this is probably too big (i.e, if the cluster size
3677	* is 1 megabyte, then group preallocation size becomes half a
3678	* gigabyte!). As a default, we will keep a two megabyte
3679	* group pralloc size for cluster sizes up to 64k, and after
3680	* that, we will force a minimum group preallocation size of
3681	* 32 clusters. This translates to 8 megs when the cluster
3682	* size is 256k, and 32 megs when the cluster size is 1 meg,
3683	* which seems reasonable as a default.
3684	*/
3685	sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>
3686	sbi->s_cluster_bits, 32);
3687	/*
3688	* If there is a s_stripe > 1, then we set the s_mb_group_prealloc
3689	* to the lowest multiple of s_stripe which is bigger than
3690	* the s_mb_group_prealloc as determined above. We want
3691	* the preallocation size to be an exact multiple of the
3692	* RAID stripe size so that preallocations don't fragment
3693	* the stripes.
3694	*/
3695	if (sbi->s_stripe > 1) {
3696	sbi->s_mb_group_prealloc = roundup(
3697	sbi->s_mb_group_prealloc, EXT4_B2C(sbi, sbi->s_stripe));
3698	}
3699
3700	sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
3701	if (sbi->s_locality_groups == NULL) {
3702	ret = -ENOMEM;
3703	goto out;
3704	}
3705	for_each_possible_cpu(i) {
3706	struct ext4_locality_group *lg;
3707	lg = per_cpu_ptr(sbi->s_locality_groups, i);
3708	mutex_init(&lg->lg_mutex);
3709	for (j = 0; j < PREALLOC_TB_SIZE; j++)
3710	INIT_LIST_HEAD(list: &lg->lg_prealloc_list[j]);
3711	spin_lock_init(&lg->lg_prealloc_lock);
3712	}
3713
3714	if (bdev_nonrot(bdev: sb->s_bdev))
3715	sbi->s_mb_max_linear_groups = 0;
3716	else
3717	sbi->s_mb_max_linear_groups = MB_DEFAULT_LINEAR_LIMIT;
3718	/* init file for buddy data */
3719	ret = ext4_mb_init_backend(sb);
3720	if (ret != 0)
3721	goto out_free_locality_groups;
3722
3723	return 0;
3724
3725	out_free_locality_groups:
3726	free_percpu(pdata: sbi->s_locality_groups);
3727	sbi->s_locality_groups = NULL;
3728	out:
3729	kfree(objp: sbi->s_mb_avg_fragment_size);
3730	kfree(objp: sbi->s_mb_avg_fragment_size_locks);
3731	kfree(objp: sbi->s_mb_largest_free_orders);
3732	kfree(objp: sbi->s_mb_largest_free_orders_locks);
3733	kfree(objp: sbi->s_mb_offsets);
3734	sbi->s_mb_offsets = NULL;
3735	kfree(objp: sbi->s_mb_maxs);
3736	sbi->s_mb_maxs = NULL;
3737	return ret;
3738	}
3739
3740	/* need to called with the ext4 group lock held */
3741	static int ext4_mb_cleanup_pa(struct ext4_group_info *grp)
3742	{
3743	struct ext4_prealloc_space *pa;
3744	struct list_head *cur, *tmp;
3745	int count = 0;
3746
3747	list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
3748	pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
3749	list_del(entry: &pa->pa_group_list);
3750	count++;
3751	kmem_cache_free(s: ext4_pspace_cachep, objp: pa);
3752	}
3753	return count;
3754	}
3755
3756	void ext4_mb_release(struct super_block *sb)
3757	{
3758	ext4_group_t ngroups = ext4_get_groups_count(sb);
3759	ext4_group_t i;
3760	int num_meta_group_infos;
3761	struct ext4_group_info *grinfo, ***group_info;
3762	struct ext4_sb_info *sbi = EXT4_SB(sb);
3763	struct kmem_cache *cachep = get_groupinfo_cache(blocksize_bits: sb->s_blocksize_bits);
3764	int count;
3765
3766	if (test_opt(sb, DISCARD)) {
3767	/*
3768	* wait the discard work to drain all of ext4_free_data
3769	*/
3770	flush_work(work: &sbi->s_discard_work);
3771	WARN_ON_ONCE(!list_empty(&sbi->s_discard_list));
3772	}
3773
3774	if (sbi->s_group_info) {
3775	for (i = 0; i < ngroups; i++) {
3776	cond_resched();
3777	grinfo = ext4_get_group_info(sb, group: i);
3778	if (!grinfo)
3779	continue;
3780	mb_group_bb_bitmap_free(grp: grinfo);
3781	ext4_lock_group(sb, group: i);
3782	count = ext4_mb_cleanup_pa(grp: grinfo);
3783	if (count)
3784	mb_debug(sb, "mballoc: %d PAs left\n",
3785	count);
3786	ext4_unlock_group(sb, group: i);
3787	kmem_cache_free(s: cachep, objp: grinfo);
3788	}
3789	num_meta_group_infos = (ngroups +
3790	EXT4_DESC_PER_BLOCK(sb) - 1) >>
3791	EXT4_DESC_PER_BLOCK_BITS(sb);
3792	rcu_read_lock();
3793	group_info = rcu_dereference(sbi->s_group_info);
3794	for (i = 0; i < num_meta_group_infos; i++)
3795	kfree(objp: group_info[i]);
3796	kvfree(addr: group_info);
3797	rcu_read_unlock();
3798	}
3799	kfree(objp: sbi->s_mb_avg_fragment_size);
3800	kfree(objp: sbi->s_mb_avg_fragment_size_locks);
3801	kfree(objp: sbi->s_mb_largest_free_orders);
3802	kfree(objp: sbi->s_mb_largest_free_orders_locks);
3803	kfree(objp: sbi->s_mb_offsets);
3804	kfree(objp: sbi->s_mb_maxs);
3805	iput(sbi->s_buddy_cache);
3806	if (sbi->s_mb_stats) {
3807	ext4_msg(sb, KERN_INFO,
3808	"mballoc: %u blocks %u reqs (%u success)",
3809	atomic_read(&sbi->s_bal_allocated),
3810	atomic_read(&sbi->s_bal_reqs),
3811	atomic_read(&sbi->s_bal_success));
3812	ext4_msg(sb, KERN_INFO,
3813	"mballoc: %u extents scanned, %u groups scanned, %u goal hits, "
3814	"%u 2^N hits, %u breaks, %u lost",
3815	atomic_read(&sbi->s_bal_ex_scanned),
3816	atomic_read(&sbi->s_bal_groups_scanned),
3817	atomic_read(&sbi->s_bal_goals),
3818	atomic_read(&sbi->s_bal_2orders),
3819	atomic_read(&sbi->s_bal_breaks),
3820	atomic_read(&sbi->s_mb_lost_chunks));
3821	ext4_msg(sb, KERN_INFO,
3822	"mballoc: %u generated and it took %llu",
3823	atomic_read(&sbi->s_mb_buddies_generated),
3824	atomic64_read(&sbi->s_mb_generation_time));
3825	ext4_msg(sb, KERN_INFO,
3826	"mballoc: %u preallocated, %u discarded",
3827	atomic_read(&sbi->s_mb_preallocated),
3828	atomic_read(&sbi->s_mb_discarded));
3829	}
3830
3831	free_percpu(pdata: sbi->s_locality_groups);
3832	}
3833
3834	static inline int ext4_issue_discard(struct super_block *sb,
3835	ext4_group_t block_group, ext4_grpblk_t cluster, int count)
3836	{
3837	ext4_fsblk_t discard_block;
3838
3839	discard_block = (EXT4_C2B(EXT4_SB(sb), cluster) +
3840	ext4_group_first_block_no(sb, group_no: block_group));
3841	count = EXT4_C2B(EXT4_SB(sb), count);
3842	trace_ext4_discard_blocks(sb,
3843	blk: (unsigned long long) discard_block, count);
3844
3845	return sb_issue_discard(sb, block: discard_block, nr_blocks: count, GFP_NOFS, flags: 0);
3846	}
3847
3848	static void ext4_free_data_in_buddy(struct super_block *sb,
3849	struct ext4_free_data *entry)
3850	{
3851	struct ext4_buddy e4b;
3852	struct ext4_group_info *db;
3853	int err, count = 0;
3854
3855	mb_debug(sb, "gonna free %u blocks in group %u (0x%p):",
3856	entry->efd_count, entry->efd_group, entry);
3857
3858	err = ext4_mb_load_buddy(sb, group: entry->efd_group, e4b: &e4b);
3859	/* we expect to find existing buddy because it's pinned */
3860	BUG_ON(err != 0);
3861
3862	spin_lock(lock: &EXT4_SB(sb)->s_md_lock);
3863	EXT4_SB(sb)->s_mb_free_pending -= entry->efd_count;
3864	spin_unlock(lock: &EXT4_SB(sb)->s_md_lock);
3865
3866	db = e4b.bd_info;
3867	/* there are blocks to put in buddy to make them really free */
3868	count += entry->efd_count;
3869	ext4_lock_group(sb, group: entry->efd_group);
3870	/* Take it out of per group rb tree */
3871	rb_erase(&entry->efd_node, &(db->bb_free_root));
3872	mb_free_blocks(NULL, e4b: &e4b, first: entry->efd_start_cluster, count: entry->efd_count);
3873
3874	/*
3875	* Clear the trimmed flag for the group so that the next
3876	* ext4_trim_fs can trim it.
3877	* If the volume is mounted with -o discard, online discard
3878	* is supported and the free blocks will be trimmed online.
3879	*/
3880	if (!test_opt(sb, DISCARD))
3881	EXT4_MB_GRP_CLEAR_TRIMMED(db);
3882
3883	if (!db->bb_free_root.rb_node) {
3884	/* No more items in the per group rb tree
3885	* balance refcounts from ext4_mb_free_metadata()
3886	*/
3887	put_page(page: e4b.bd_buddy_page);
3888	put_page(page: e4b.bd_bitmap_page);
3889	}
3890	ext4_unlock_group(sb, group: entry->efd_group);
3891	ext4_mb_unload_buddy(e4b: &e4b);
3892
3893	mb_debug(sb, "freed %d blocks in 1 structures\n", count);
3894	}
3895
3896	/*
3897	* This function is called by the jbd2 layer once the commit has finished,
3898	* so we know we can free the blocks that were released with that commit.
3899	*/
3900	void ext4_process_freed_data(struct super_block *sb, tid_t commit_tid)
3901	{
3902	struct ext4_sb_info *sbi = EXT4_SB(sb);
3903	struct ext4_free_data *entry, *tmp;
3904	LIST_HEAD(freed_data_list);
3905	struct list_head *s_freed_head = &sbi->s_freed_data_list[commit_tid & 1];
3906	bool wake;
3907
3908	list_replace_init(old: s_freed_head, new: &freed_data_list);
3909
3910	list_for_each_entry(entry, &freed_data_list, efd_list)
3911	ext4_free_data_in_buddy(sb, entry);
3912
3913	if (test_opt(sb, DISCARD)) {
3914	spin_lock(lock: &sbi->s_md_lock);
3915	wake = list_empty(head: &sbi->s_discard_list);
3916	list_splice_tail(list: &freed_data_list, head: &sbi->s_discard_list);
3917	spin_unlock(lock: &sbi->s_md_lock);
3918	if (wake)
3919	queue_work(wq: system_unbound_wq, work: &sbi->s_discard_work);
3920	} else {
3921	list_for_each_entry_safe(entry, tmp, &freed_data_list, efd_list)
3922	kmem_cache_free(s: ext4_free_data_cachep, objp: entry);
3923	}
3924	}
3925
3926	int __init ext4_init_mballoc(void)
3927	{
3928	ext4_pspace_cachep = KMEM_CACHE(ext4_prealloc_space,
3929	SLAB_RECLAIM_ACCOUNT);
3930	if (ext4_pspace_cachep == NULL)
3931	goto out;
3932
3933	ext4_ac_cachep = KMEM_CACHE(ext4_allocation_context,
3934	SLAB_RECLAIM_ACCOUNT);
3935	if (ext4_ac_cachep == NULL)
3936	goto out_pa_free;
3937
3938	ext4_free_data_cachep = KMEM_CACHE(ext4_free_data,
3939	SLAB_RECLAIM_ACCOUNT);
3940	if (ext4_free_data_cachep == NULL)
3941	goto out_ac_free;
3942
3943	return 0;
3944
3945	out_ac_free:
3946	kmem_cache_destroy(s: ext4_ac_cachep);
3947	out_pa_free:
3948	kmem_cache_destroy(s: ext4_pspace_cachep);
3949	out:
3950	return -ENOMEM;
3951	}
3952
3953	void ext4_exit_mballoc(void)
3954	{
3955	/*
3956	* Wait for completion of call_rcu()'s on ext4_pspace_cachep
3957	* before destroying the slab cache.
3958	*/
3959	rcu_barrier();
3960	kmem_cache_destroy(s: ext4_pspace_cachep);
3961	kmem_cache_destroy(s: ext4_ac_cachep);
3962	kmem_cache_destroy(s: ext4_free_data_cachep);
3963	ext4_groupinfo_destroy_slabs();
3964	}
3965
3966	#define EXT4_MB_BITMAP_MARKED_CHECK 0x0001
3967	#define EXT4_MB_SYNC_UPDATE 0x0002
3968	static int
3969	ext4_mb_mark_context(handle_t *handle, struct super_block *sb, bool state,
3970	ext4_group_t group, ext4_grpblk_t blkoff,
3971	ext4_grpblk_t len, int flags, ext4_grpblk_t *ret_changed)
3972	{
3973	struct ext4_sb_info *sbi = EXT4_SB(sb);
3974	struct buffer_head *bitmap_bh = NULL;
3975	struct ext4_group_desc *gdp;
3976	struct buffer_head *gdp_bh;
3977	int err;
3978	unsigned int i, already, changed = len;
3979
3980	KUNIT_STATIC_STUB_REDIRECT(ext4_mb_mark_context,
3981	handle, sb, state, group, blkoff, len,
3982	flags, ret_changed);
3983
3984	if (ret_changed)
3985	*ret_changed = 0;
3986	bitmap_bh = ext4_read_block_bitmap(sb, block_group: group);
3987	if (IS_ERR(ptr: bitmap_bh))
3988	return PTR_ERR(ptr: bitmap_bh);
3989
3990	if (handle) {
3991	BUFFER_TRACE(bitmap_bh, "getting write access");
3992	err = ext4_journal_get_write_access(handle, sb, bitmap_bh,
3993	EXT4_JTR_NONE);
3994	if (err)
3995	goto out_err;
3996	}
3997
3998	err = -EIO;
3999	gdp = ext4_get_group_desc(sb, block_group: group, bh: &gdp_bh);
4000	if (!gdp)
4001	goto out_err;
4002
4003	if (handle) {
4004	BUFFER_TRACE(gdp_bh, "get_write_access");
4005	err = ext4_journal_get_write_access(handle, sb, gdp_bh,
4006	EXT4_JTR_NONE);
4007	if (err)
4008	goto out_err;
4009	}
4010
4011	ext4_lock_group(sb, group);
4012	if (ext4_has_group_desc_csum(sb) &&
4013	(gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
4014	gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
4015	ext4_free_group_clusters_set(sb, bg: gdp,
4016	count: ext4_free_clusters_after_init(sb, block_group: group, gdp));
4017	}
4018
4019	if (flags & EXT4_MB_BITMAP_MARKED_CHECK) {
4020	already = 0;
4021	for (i = 0; i < len; i++)
4022	if (mb_test_bit(bit: blkoff + i, addr: bitmap_bh->b_data) ==
4023	state)
4024	already++;
4025	changed = len - already;
4026	}
4027
4028	if (state) {
4029	mb_set_bits(bm: bitmap_bh->b_data, cur: blkoff, len);
4030	ext4_free_group_clusters_set(sb, bg: gdp,
4031	count: ext4_free_group_clusters(sb, bg: gdp) - changed);
4032	} else {
4033	mb_clear_bits(bm: bitmap_bh->b_data, cur: blkoff, len);
4034	ext4_free_group_clusters_set(sb, bg: gdp,
4035	count: ext4_free_group_clusters(sb, bg: gdp) + changed);
4036	}
4037
4038	ext4_block_bitmap_csum_set(sb, gdp, bh: bitmap_bh);
4039	ext4_group_desc_csum_set(sb, group, gdp);
4040	ext4_unlock_group(sb, group);
4041	if (ret_changed)
4042	*ret_changed = changed;
4043
4044	if (sbi->s_log_groups_per_flex) {
4045	ext4_group_t flex_group = ext4_flex_group(sbi, block_group: group);
4046	struct flex_groups *fg = sbi_array_rcu_deref(sbi,
4047	s_flex_groups, flex_group);
4048
4049	if (state)
4050	atomic64_sub(i: changed, v: &fg->free_clusters);
4051	else
4052	atomic64_add(i: changed, v: &fg->free_clusters);
4053	}
4054
4055	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
4056	if (err)
4057	goto out_err;
4058	err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);
4059	if (err)
4060	goto out_err;
4061
4062	if (flags & EXT4_MB_SYNC_UPDATE) {
4063	sync_dirty_buffer(bh: bitmap_bh);
4064	sync_dirty_buffer(bh: gdp_bh);
4065	}
4066
4067	out_err:
4068	brelse(bh: bitmap_bh);
4069	return err;
4070	}
4071
4072	/*
4073	* Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
4074	* Returns 0 if success or error code
4075	*/
4076	static noinline_for_stack int
4077	ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
4078	handle_t *handle, unsigned int reserv_clstrs)
4079	{
4080	struct ext4_group_desc *gdp;
4081	struct ext4_sb_info *sbi;
4082	struct super_block *sb;
4083	ext4_fsblk_t block;
4084	int err, len;
4085	int flags = 0;
4086	ext4_grpblk_t changed;
4087
4088	BUG_ON(ac->ac_status != AC_STATUS_FOUND);
4089	BUG_ON(ac->ac_b_ex.fe_len <= 0);
4090
4091	sb = ac->ac_sb;
4092	sbi = EXT4_SB(sb);
4093
4094	gdp = ext4_get_group_desc(sb, block_group: ac->ac_b_ex.fe_group, NULL);
4095	if (!gdp)
4096	return -EIO;
4097	ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,
4098	ext4_free_group_clusters(sb, gdp));
4099
4100	block = ext4_grp_offs_to_block(sb, fex: &ac->ac_b_ex);
4101	len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4102	if (!ext4_inode_block_valid(inode: ac->ac_inode, start_blk: block, count: len)) {
4103	ext4_error(sb, "Allocating blocks %llu-%llu which overlap "
4104	"fs metadata", block, block+len);
4105	/* File system mounted not to panic on error
4106	* Fix the bitmap and return EFSCORRUPTED
4107	* We leak some of the blocks here.
4108	*/
4109	err = ext4_mb_mark_context(handle, sb, state: true,
4110	group: ac->ac_b_ex.fe_group,
4111	blkoff: ac->ac_b_ex.fe_start,
4112	len: ac->ac_b_ex.fe_len,
4113	flags: 0, NULL);
4114	if (!err)
4115	err = -EFSCORRUPTED;
4116	return err;
4117	}
4118
4119	#ifdef AGGRESSIVE_CHECK
4120	flags |= EXT4_MB_BITMAP_MARKED_CHECK;
4121	#endif
4122	err = ext4_mb_mark_context(handle, sb, state: true, group: ac->ac_b_ex.fe_group,
4123	blkoff: ac->ac_b_ex.fe_start, len: ac->ac_b_ex.fe_len,
4124	flags, ret_changed: &changed);
4125
4126	if (err && changed == 0)
4127	return err;
4128
4129	#ifdef AGGRESSIVE_CHECK
4130	BUG_ON(changed != ac->ac_b_ex.fe_len);
4131	#endif
4132	percpu_counter_sub(fbc: &sbi->s_freeclusters_counter, amount: ac->ac_b_ex.fe_len);
4133	/*
4134	* Now reduce the dirty block count also. Should not go negative
4135	*/
4136	if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
4137	/* release all the reserved blocks if non delalloc */
4138	percpu_counter_sub(fbc: &sbi->s_dirtyclusters_counter,
4139	amount: reserv_clstrs);
4140
4141	return err;
4142	}
4143
4144	/*
4145	* Idempotent helper for Ext4 fast commit replay path to set the state of
4146	* blocks in bitmaps and update counters.
4147	*/
4148	void ext4_mb_mark_bb(struct super_block *sb, ext4_fsblk_t block,
4149	int len, bool state)
4150	{
4151	struct ext4_sb_info *sbi = EXT4_SB(sb);
4152	ext4_group_t group;
4153	ext4_grpblk_t blkoff;
4154	int err = 0;
4155	unsigned int clen, thisgrp_len;
4156
4157	while (len > 0) {
4158	ext4_get_group_no_and_offset(sb, blocknr: block, blockgrpp: &group, offsetp: &blkoff);
4159
4160	/*
4161	* Check to see if we are freeing blocks across a group
4162	* boundary.
4163	* In case of flex_bg, this can happen that (block, len) may
4164	* span across more than one group. In that case we need to
4165	* get the corresponding group metadata to work with.
4166	* For this we have goto again loop.
4167	*/
4168	thisgrp_len = min_t(unsigned int, (unsigned int)len,
4169	EXT4_BLOCKS_PER_GROUP(sb) - EXT4_C2B(sbi, blkoff));
4170	clen = EXT4_NUM_B2C(sbi, thisgrp_len);
4171
4172	if (!ext4_sb_block_valid(sb, NULL, start_blk: block, count: thisgrp_len)) {
4173	ext4_error(sb, "Marking blocks in system zone - "
4174	"Block = %llu, len = %u",
4175	block, thisgrp_len);
4176	break;
4177	}
4178
4179	err = ext4_mb_mark_context(NULL, sb, state,
4180	group, blkoff, len: clen,
4181	EXT4_MB_BITMAP_MARKED_CHECK |
4182	EXT4_MB_SYNC_UPDATE,
4183	NULL);
4184	if (err)
4185	break;
4186
4187	block += thisgrp_len;
4188	len -= thisgrp_len;
4189	BUG_ON(len < 0);
4190	}
4191	}
4192
4193	/*
4194	* here we normalize request for locality group
4195	* Group request are normalized to s_mb_group_prealloc, which goes to
4196	* s_strip if we set the same via mount option.
4197	* s_mb_group_prealloc can be configured via
4198	* /sys/fs/ext4/<partition>/mb_group_prealloc
4199	*
4200	* XXX: should we try to preallocate more than the group has now?
4201	*/
4202	static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
4203	{
4204	struct super_block *sb = ac->ac_sb;
4205	struct ext4_locality_group *lg = ac->ac_lg;
4206
4207	BUG_ON(lg == NULL);
4208	ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
4209	mb_debug(sb, "goal %u blocks for locality group\n", ac->ac_g_ex.fe_len);
4210	}
4211
4212	/*
4213	* This function returns the next element to look at during inode
4214	* PA rbtree walk. We assume that we have held the inode PA rbtree lock
4215	* (ei->i_prealloc_lock)
4216	*
4217	* new_start The start of the range we want to compare
4218	* cur_start The existing start that we are comparing against
4219	* node The node of the rb_tree
4220	*/
4221	static inline struct rb_node*
4222	ext4_mb_pa_rb_next_iter(ext4_lblk_t new_start, ext4_lblk_t cur_start, struct rb_node *node)
4223	{
4224	if (new_start < cur_start)
4225	return node->rb_left;
4226	else
4227	return node->rb_right;
4228	}
4229
4230	static inline void
4231	ext4_mb_pa_assert_overlap(struct ext4_allocation_context *ac,
4232	ext4_lblk_t start, loff_t end)
4233	{
4234	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4235	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
4236	struct ext4_prealloc_space *tmp_pa;
4237	ext4_lblk_t tmp_pa_start;
4238	loff_t tmp_pa_end;
4239	struct rb_node *iter;
4240
4241	read_lock(&ei->i_prealloc_lock);
4242	for (iter = ei->i_prealloc_node.rb_node; iter;
4243	iter = ext4_mb_pa_rb_next_iter(new_start: start, cur_start: tmp_pa_start, node: iter)) {
4244	tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
4245	pa_node.inode_node);
4246	tmp_pa_start = tmp_pa->pa_lstart;
4247	tmp_pa_end = pa_logical_end(sbi, pa: tmp_pa);
4248
4249	spin_lock(lock: &tmp_pa->pa_lock);
4250	if (tmp_pa->pa_deleted == 0)
4251	BUG_ON(!(start >= tmp_pa_end || end <= tmp_pa_start));
4252	spin_unlock(lock: &tmp_pa->pa_lock);
4253	}
4254	read_unlock(&ei->i_prealloc_lock);
4255	}
4256
4257	/*
4258	* Given an allocation context "ac" and a range "start", "end", check
4259	* and adjust boundaries if the range overlaps with any of the existing
4260	* preallocatoins stored in the corresponding inode of the allocation context.
4261	*
4262	* Parameters:
4263	* ac allocation context
4264	* start start of the new range
4265	* end end of the new range
4266	*/
4267	static inline void
4268	ext4_mb_pa_adjust_overlap(struct ext4_allocation_context *ac,
4269	ext4_lblk_t *start, loff_t *end)
4270	{
4271	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
4272	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4273	struct ext4_prealloc_space *tmp_pa = NULL, *left_pa = NULL, *right_pa = NULL;
4274	struct rb_node *iter;
4275	ext4_lblk_t new_start, tmp_pa_start, right_pa_start = -1;
4276	loff_t new_end, tmp_pa_end, left_pa_end = -1;
4277
4278	new_start = *start;
4279	new_end = *end;
4280
4281	/*
4282	* Adjust the normalized range so that it doesn't overlap with any
4283	* existing preallocated blocks(PAs). Make sure to hold the rbtree lock
4284	* so it doesn't change underneath us.
4285	*/
4286	read_lock(&ei->i_prealloc_lock);
4287
4288	/* Step 1: find any one immediate neighboring PA of the normalized range */
4289	for (iter = ei->i_prealloc_node.rb_node; iter;
4290	iter = ext4_mb_pa_rb_next_iter(new_start: ac->ac_o_ex.fe_logical,
4291	cur_start: tmp_pa_start, node: iter)) {
4292	tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
4293	pa_node.inode_node);
4294	tmp_pa_start = tmp_pa->pa_lstart;
4295	tmp_pa_end = pa_logical_end(sbi, pa: tmp_pa);
4296
4297	/* PA must not overlap original request */
4298	spin_lock(lock: &tmp_pa->pa_lock);
4299	if (tmp_pa->pa_deleted == 0)
4300	BUG_ON(!(ac->ac_o_ex.fe_logical >= tmp_pa_end ||
4301	ac->ac_o_ex.fe_logical < tmp_pa_start));
4302	spin_unlock(lock: &tmp_pa->pa_lock);
4303	}
4304
4305	/*
4306	* Step 2: check if the found PA is left or right neighbor and
4307	* get the other neighbor
4308	*/
4309	if (tmp_pa) {
4310	if (tmp_pa->pa_lstart < ac->ac_o_ex.fe_logical) {
4311	struct rb_node *tmp;
4312
4313	left_pa = tmp_pa;
4314	tmp = rb_next(&left_pa->pa_node.inode_node);
4315	if (tmp) {
4316	right_pa = rb_entry(tmp,
4317	struct ext4_prealloc_space,
4318	pa_node.inode_node);
4319	}
4320	} else {
4321	struct rb_node *tmp;
4322
4323	right_pa = tmp_pa;
4324	tmp = rb_prev(&right_pa->pa_node.inode_node);
4325	if (tmp) {
4326	left_pa = rb_entry(tmp,
4327	struct ext4_prealloc_space,
4328	pa_node.inode_node);
4329	}
4330	}
4331	}
4332
4333	/* Step 3: get the non deleted neighbors */
4334	if (left_pa) {
4335	for (iter = &left_pa->pa_node.inode_node;;
4336	iter = rb_prev(iter)) {
4337	if (!iter) {
4338	left_pa = NULL;
4339	break;
4340	}
4341
4342	tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
4343	pa_node.inode_node);
4344	left_pa = tmp_pa;
4345	spin_lock(lock: &tmp_pa->pa_lock);
4346	if (tmp_pa->pa_deleted == 0) {
4347	spin_unlock(lock: &tmp_pa->pa_lock);
4348	break;
4349	}
4350	spin_unlock(lock: &tmp_pa->pa_lock);
4351	}
4352	}
4353
4354	if (right_pa) {
4355	for (iter = &right_pa->pa_node.inode_node;;
4356	iter = rb_next(iter)) {
4357	if (!iter) {
4358	right_pa = NULL;
4359	break;
4360	}
4361
4362	tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
4363	pa_node.inode_node);
4364	right_pa = tmp_pa;
4365	spin_lock(lock: &tmp_pa->pa_lock);
4366	if (tmp_pa->pa_deleted == 0) {
4367	spin_unlock(lock: &tmp_pa->pa_lock);
4368	break;
4369	}
4370	spin_unlock(lock: &tmp_pa->pa_lock);
4371	}
4372	}
4373
4374	if (left_pa) {
4375	left_pa_end = pa_logical_end(sbi, pa: left_pa);
4376	BUG_ON(left_pa_end > ac->ac_o_ex.fe_logical);
4377	}
4378
4379	if (right_pa) {
4380	right_pa_start = right_pa->pa_lstart;
4381	BUG_ON(right_pa_start <= ac->ac_o_ex.fe_logical);
4382	}
4383
4384	/* Step 4: trim our normalized range to not overlap with the neighbors */
4385	if (left_pa) {
4386	if (left_pa_end > new_start)
4387	new_start = left_pa_end;
4388	}
4389
4390	if (right_pa) {
4391	if (right_pa_start < new_end)
4392	new_end = right_pa_start;
4393	}
4394	read_unlock(&ei->i_prealloc_lock);
4395
4396	/* XXX: extra loop to check we really don't overlap preallocations */
4397	ext4_mb_pa_assert_overlap(ac, start: new_start, end: new_end);
4398
4399	*start = new_start;
4400	*end = new_end;
4401	}
4402
4403	/*
4404	* Normalization means making request better in terms of
4405	* size and alignment
4406	*/
4407	static noinline_for_stack void
4408	ext4_mb_normalize_request(struct ext4_allocation_context *ac,
4409	struct ext4_allocation_request *ar)
4410	{
4411	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4412	struct ext4_super_block *es = sbi->s_es;
4413	int bsbits, max;
4414	loff_t size, start_off, end;
4415	loff_t orig_size __maybe_unused;
4416	ext4_lblk_t start;
4417
4418	/* do normalize only data requests, metadata requests
4419	do not need preallocation */
4420	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
4421	return;
4422
4423	/* sometime caller may want exact blocks */
4424	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
4425	return;
4426
4427	/* caller may indicate that preallocation isn't
4428	* required (it's a tail, for example) */
4429	if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
4430	return;
4431
4432	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
4433	ext4_mb_normalize_group_request(ac);
4434	return ;
4435	}
4436
4437	bsbits = ac->ac_sb->s_blocksize_bits;
4438
4439	/* first, let's learn actual file size
4440	* given current request is allocated */
4441	size = extent_logical_end(sbi, fex: &ac->ac_o_ex);
4442	size = size << bsbits;
4443	if (size < i_size_read(inode: ac->ac_inode))
4444	size = i_size_read(inode: ac->ac_inode);
4445	orig_size = size;
4446
4447	/* max size of free chunks */
4448	max = 2 << bsbits;
4449
4450	#define NRL_CHECK_SIZE(req, size, max, chunk_size) \
4451	(req <= (size) || max <= (chunk_size))
4452
4453	/* first, try to predict filesize */
4454	/* XXX: should this table be tunable? */
4455	start_off = 0;
4456	if (size <= 16 * 1024) {
4457	size = 16 * 1024;
4458	} else if (size <= 32 * 1024) {
4459	size = 32 * 1024;
4460	} else if (size <= 64 * 1024) {
4461	size = 64 * 1024;
4462	} else if (size <= 128 * 1024) {
4463	size = 128 * 1024;
4464	} else if (size <= 256 * 1024) {
4465	size = 256 * 1024;
4466	} else if (size <= 512 * 1024) {
4467	size = 512 * 1024;
4468	} else if (size <= 1024 * 1024) {
4469	size = 1024 * 1024;
4470	} else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
4471	start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
4472	(21 - bsbits)) << 21;
4473	size = 2 * 1024 * 1024;
4474	} else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
4475	start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
4476	(22 - bsbits)) << 22;
4477	size = 4 * 1024 * 1024;
4478	} else if (NRL_CHECK_SIZE(EXT4_C2B(sbi, ac->ac_o_ex.fe_len),
4479	(8<<20)>>bsbits, max, 8 * 1024)) {
4480	start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
4481	(23 - bsbits)) << 23;
4482	size = 8 * 1024 * 1024;
4483	} else {
4484	start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;
4485	size = (loff_t) EXT4_C2B(sbi,
4486	ac->ac_o_ex.fe_len) << bsbits;
4487	}
4488	size = size >> bsbits;
4489	start = start_off >> bsbits;
4490
4491	/*
4492	* For tiny groups (smaller than 8MB) the chosen allocation
4493	* alignment may be larger than group size. Make sure the
4494	* alignment does not move allocation to a different group which
4495	* makes mballoc fail assertions later.
4496	*/
4497	start = max(start, rounddown(ac->ac_o_ex.fe_logical,
4498	(ext4_lblk_t)EXT4_BLOCKS_PER_GROUP(ac->ac_sb)));
4499
4500	/* avoid unnecessary preallocation that may trigger assertions */
4501	if (start + size > EXT_MAX_BLOCKS)
4502	size = EXT_MAX_BLOCKS - start;
4503
4504	/* don't cover already allocated blocks in selected range */
4505	if (ar->pleft && start <= ar->lleft) {
4506	size -= ar->lleft + 1 - start;
4507	start = ar->lleft + 1;
4508	}
4509	if (ar->pright && start + size - 1 >= ar->lright)
4510	size -= start + size - ar->lright;
4511
4512	/*
4513	* Trim allocation request for filesystems with artificially small
4514	* groups.
4515	*/
4516	if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))
4517	size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);
4518
4519	end = start + size;
4520
4521	ext4_mb_pa_adjust_overlap(ac, start: &start, end: &end);
4522
4523	size = end - start;
4524
4525	/*
4526	* In this function "start" and "size" are normalized for better
4527	* alignment and length such that we could preallocate more blocks.
4528	* This normalization is done such that original request of
4529	* ac->ac_o_ex.fe_logical & fe_len should always lie within "start" and
4530	* "size" boundaries.
4531	* (Note fe_len can be relaxed since FS block allocation API does not
4532	* provide gurantee on number of contiguous blocks allocation since that
4533	* depends upon free space left, etc).
4534	* In case of inode pa, later we use the allocated blocks
4535	* [pa_pstart + fe_logical - pa_lstart, fe_len/size] from the preallocated
4536	* range of goal/best blocks [start, size] to put it at the
4537	* ac_o_ex.fe_logical extent of this inode.
4538	* (See ext4_mb_use_inode_pa() for more details)
4539	*/
4540	if (start + size <= ac->ac_o_ex.fe_logical ||
4541	start > ac->ac_o_ex.fe_logical) {
4542	ext4_msg(ac->ac_sb, KERN_ERR,
4543	"start %lu, size %lu, fe_logical %lu",
4544	(unsigned long) start, (unsigned long) size,
4545	(unsigned long) ac->ac_o_ex.fe_logical);
4546	BUG();
4547	}
4548	BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
4549
4550	/* now prepare goal request */
4551
4552	/* XXX: is it better to align blocks WRT to logical
4553	* placement or satisfy big request as is */
4554	ac->ac_g_ex.fe_logical = start;
4555	ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);
4556	ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;
4557
4558	/* define goal start in order to merge */
4559	if (ar->pright && (ar->lright == (start + size)) &&
4560	ar->pright >= size &&
4561	ar->pright - size >= le32_to_cpu(es->s_first_data_block)) {
4562	/* merge to the right */
4563	ext4_get_group_no_and_offset(sb: ac->ac_sb, blocknr: ar->pright - size,
4564	blockgrpp: &ac->ac_g_ex.fe_group,
4565	offsetp: &ac->ac_g_ex.fe_start);
4566	ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
4567	}
4568	if (ar->pleft && (ar->lleft + 1 == start) &&
4569	ar->pleft + 1 < ext4_blocks_count(es)) {
4570	/* merge to the left */
4571	ext4_get_group_no_and_offset(sb: ac->ac_sb, blocknr: ar->pleft + 1,
4572	blockgrpp: &ac->ac_g_ex.fe_group,
4573	offsetp: &ac->ac_g_ex.fe_start);
4574	ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
4575	}
4576
4577	mb_debug(ac->ac_sb, "goal: %lld(was %lld) blocks at %u\n", size,
4578	orig_size, start);
4579	}
4580
4581	static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
4582	{
4583	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4584
4585	if (sbi->s_mb_stats && ac->ac_g_ex.fe_len >= 1) {
4586	atomic_inc(v: &sbi->s_bal_reqs);
4587	atomic_add(i: ac->ac_b_ex.fe_len, v: &sbi->s_bal_allocated);
4588	if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
4589	atomic_inc(v: &sbi->s_bal_success);
4590
4591	atomic_add(i: ac->ac_found, v: &sbi->s_bal_ex_scanned);
4592	for (int i=0; i<EXT4_MB_NUM_CRS; i++) {
4593	atomic_add(i: ac->ac_cX_found[i], v: &sbi->s_bal_cX_ex_scanned[i]);
4594	}
4595
4596	atomic_add(i: ac->ac_groups_scanned, v: &sbi->s_bal_groups_scanned);
4597	if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
4598	ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
4599	atomic_inc(v: &sbi->s_bal_goals);
4600	/* did we allocate as much as normalizer originally wanted? */
4601	if (ac->ac_f_ex.fe_len == ac->ac_orig_goal_len)
4602	atomic_inc(v: &sbi->s_bal_len_goals);
4603
4604	if (ac->ac_found > sbi->s_mb_max_to_scan)
4605	atomic_inc(v: &sbi->s_bal_breaks);
4606	}
4607
4608	if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)
4609	trace_ext4_mballoc_alloc(ac);
4610	else
4611	trace_ext4_mballoc_prealloc(ac);
4612	}
4613
4614	/*
4615	* Called on failure; free up any blocks from the inode PA for this
4616	* context. We don't need this for MB_GROUP_PA because we only change
4617	* pa_free in ext4_mb_release_context(), but on failure, we've already
4618	* zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
4619	*/
4620	static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac)
4621	{
4622	struct ext4_prealloc_space *pa = ac->ac_pa;
4623	struct ext4_buddy e4b;
4624	int err;
4625
4626	if (pa == NULL) {
4627	if (ac->ac_f_ex.fe_len == 0)
4628	return;
4629	err = ext4_mb_load_buddy(sb: ac->ac_sb, group: ac->ac_f_ex.fe_group, e4b: &e4b);
4630	if (WARN_RATELIMIT(err,
4631	"ext4: mb_load_buddy failed (%d)", err))
4632	/*
4633	* This should never happen since we pin the
4634	* pages in the ext4_allocation_context so
4635	* ext4_mb_load_buddy() should never fail.
4636	*/
4637	return;
4638	ext4_lock_group(sb: ac->ac_sb, group: ac->ac_f_ex.fe_group);
4639	mb_free_blocks(inode: ac->ac_inode, e4b: &e4b, first: ac->ac_f_ex.fe_start,
4640	count: ac->ac_f_ex.fe_len);
4641	ext4_unlock_group(sb: ac->ac_sb, group: ac->ac_f_ex.fe_group);
4642	ext4_mb_unload_buddy(e4b: &e4b);
4643	return;
4644	}
4645	if (pa->pa_type == MB_INODE_PA) {
4646	spin_lock(lock: &pa->pa_lock);
4647	pa->pa_free += ac->ac_b_ex.fe_len;
4648	spin_unlock(lock: &pa->pa_lock);
4649	}
4650	}
4651
4652	/*
4653	* use blocks preallocated to inode
4654	*/
4655	static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
4656	struct ext4_prealloc_space *pa)
4657	{
4658	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4659	ext4_fsblk_t start;
4660	ext4_fsblk_t end;
4661	int len;
4662
4663	/* found preallocated blocks, use them */
4664	start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
4665	end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),
4666	start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));
4667	len = EXT4_NUM_B2C(sbi, end - start);
4668	ext4_get_group_no_and_offset(sb: ac->ac_sb, blocknr: start, blockgrpp: &ac->ac_b_ex.fe_group,
4669	offsetp: &ac->ac_b_ex.fe_start);
4670	ac->ac_b_ex.fe_len = len;
4671	ac->ac_status = AC_STATUS_FOUND;
4672	ac->ac_pa = pa;
4673
4674	BUG_ON(start < pa->pa_pstart);
4675	BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));
4676	BUG_ON(pa->pa_free < len);
4677	BUG_ON(ac->ac_b_ex.fe_len <= 0);
4678	pa->pa_free -= len;
4679
4680	mb_debug(ac->ac_sb, "use %llu/%d from inode pa %p\n", start, len, pa);
4681	}
4682
4683	/*
4684	* use blocks preallocated to locality group
4685	*/
4686	static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
4687	struct ext4_prealloc_space *pa)
4688	{
4689	unsigned int len = ac->ac_o_ex.fe_len;
4690
4691	ext4_get_group_no_and_offset(sb: ac->ac_sb, blocknr: pa->pa_pstart,
4692	blockgrpp: &ac->ac_b_ex.fe_group,
4693	offsetp: &ac->ac_b_ex.fe_start);
4694	ac->ac_b_ex.fe_len = len;
4695	ac->ac_status = AC_STATUS_FOUND;
4696	ac->ac_pa = pa;
4697
4698	/* we don't correct pa_pstart or pa_len here to avoid
4699	* possible race when the group is being loaded concurrently
4700	* instead we correct pa later, after blocks are marked
4701	* in on-disk bitmap -- see ext4_mb_release_context()
4702	* Other CPUs are prevented from allocating from this pa by lg_mutex
4703	*/
4704	mb_debug(ac->ac_sb, "use %u/%u from group pa %p\n",
4705	pa->pa_lstart, len, pa);
4706	}
4707
4708	/*
4709	* Return the prealloc space that have minimal distance
4710	* from the goal block. @cpa is the prealloc
4711	* space that is having currently known minimal distance
4712	* from the goal block.
4713	*/
4714	static struct ext4_prealloc_space *
4715	ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
4716	struct ext4_prealloc_space *pa,
4717	struct ext4_prealloc_space *cpa)
4718	{
4719	ext4_fsblk_t cur_distance, new_distance;
4720
4721	if (cpa == NULL) {
4722	atomic_inc(v: &pa->pa_count);
4723	return pa;
4724	}
4725	cur_distance = abs(goal_block - cpa->pa_pstart);
4726	new_distance = abs(goal_block - pa->pa_pstart);
4727
4728	if (cur_distance <= new_distance)
4729	return cpa;
4730
4731	/* drop the previous reference */
4732	atomic_dec(v: &cpa->pa_count);
4733	atomic_inc(v: &pa->pa_count);
4734	return pa;
4735	}
4736
4737	/*
4738	* check if found pa meets EXT4_MB_HINT_GOAL_ONLY
4739	*/
4740	static bool
4741	ext4_mb_pa_goal_check(struct ext4_allocation_context *ac,
4742	struct ext4_prealloc_space *pa)
4743	{
4744	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4745	ext4_fsblk_t start;
4746
4747	if (likely(!(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)))
4748	return true;
4749
4750	/*
4751	* If EXT4_MB_HINT_GOAL_ONLY is set, ac_g_ex will not be adjusted
4752	* in ext4_mb_normalize_request and will keep same with ac_o_ex
4753	* from ext4_mb_initialize_context. Choose ac_g_ex here to keep
4754	* consistent with ext4_mb_find_by_goal.
4755	*/
4756	start = pa->pa_pstart +
4757	(ac->ac_g_ex.fe_logical - pa->pa_lstart);
4758	if (ext4_grp_offs_to_block(sb: ac->ac_sb, fex: &ac->ac_g_ex) != start)
4759	return false;
4760
4761	if (ac->ac_g_ex.fe_len > pa->pa_len -
4762	EXT4_B2C(sbi, ac->ac_g_ex.fe_logical - pa->pa_lstart))
4763	return false;
4764
4765	return true;
4766	}
4767
4768	/*
4769	* search goal blocks in preallocated space
4770	*/
4771	static noinline_for_stack bool
4772	ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
4773	{
4774	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
4775	int order, i;
4776	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
4777	struct ext4_locality_group *lg;
4778	struct ext4_prealloc_space *tmp_pa = NULL, *cpa = NULL;
4779	struct rb_node *iter;
4780	ext4_fsblk_t goal_block;
4781
4782	/* only data can be preallocated */
4783	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
4784	return false;
4785
4786	/*
4787	* first, try per-file preallocation by searching the inode pa rbtree.
4788	*
4789	* Here, we can't do a direct traversal of the tree because
4790	* ext4_mb_discard_group_preallocation() can paralelly mark the pa
4791	* deleted and that can cause direct traversal to skip some entries.
4792	*/
4793	read_lock(&ei->i_prealloc_lock);
4794
4795	if (RB_EMPTY_ROOT(&ei->i_prealloc_node)) {
4796	goto try_group_pa;
4797	}
4798
4799	/*
4800	* Step 1: Find a pa with logical start immediately adjacent to the
4801	* original logical start. This could be on the left or right.
4802	*
4803	* (tmp_pa->pa_lstart never changes so we can skip locking for it).
4804	*/
4805	for (iter = ei->i_prealloc_node.rb_node; iter;
4806	iter = ext4_mb_pa_rb_next_iter(new_start: ac->ac_o_ex.fe_logical,
4807	cur_start: tmp_pa->pa_lstart, node: iter)) {
4808	tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
4809	pa_node.inode_node);
4810	}
4811
4812	/*
4813	* Step 2: The adjacent pa might be to the right of logical start, find
4814	* the left adjacent pa. After this step we'd have a valid tmp_pa whose
4815	* logical start is towards the left of original request's logical start
4816	*/
4817	if (tmp_pa->pa_lstart > ac->ac_o_ex.fe_logical) {
4818	struct rb_node *tmp;
4819	tmp = rb_prev(&tmp_pa->pa_node.inode_node);
4820
4821	if (tmp) {
4822	tmp_pa = rb_entry(tmp, struct ext4_prealloc_space,
4823	pa_node.inode_node);
4824	} else {
4825	/*
4826	* If there is no adjacent pa to the left then finding
4827	* an overlapping pa is not possible hence stop searching
4828	* inode pa tree
4829	*/
4830	goto try_group_pa;
4831	}
4832	}
4833
4834	BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));
4835
4836	/*
4837	* Step 3: If the left adjacent pa is deleted, keep moving left to find
4838	* the first non deleted adjacent pa. After this step we should have a
4839	* valid tmp_pa which is guaranteed to be non deleted.
4840	*/
4841	for (iter = &tmp_pa->pa_node.inode_node;; iter = rb_prev(iter)) {
4842	if (!iter) {
4843	/*
4844	* no non deleted left adjacent pa, so stop searching
4845	* inode pa tree
4846	*/
4847	goto try_group_pa;
4848	}
4849	tmp_pa = rb_entry(iter, struct ext4_prealloc_space,
4850	pa_node.inode_node);
4851	spin_lock(lock: &tmp_pa->pa_lock);
4852	if (tmp_pa->pa_deleted == 0) {
4853	/*
4854	* We will keep holding the pa_lock from
4855	* this point on because we don't want group discard
4856	* to delete this pa underneath us. Since group
4857	* discard is anyways an ENOSPC operation it
4858	* should be okay for it to wait a few more cycles.
4859	*/
4860	break;
4861	} else {
4862	spin_unlock(lock: &tmp_pa->pa_lock);
4863	}
4864	}
4865
4866	BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));
4867	BUG_ON(tmp_pa->pa_deleted == 1);
4868
4869	/*
4870	* Step 4: We now have the non deleted left adjacent pa. Only this
4871	* pa can possibly satisfy the request hence check if it overlaps
4872	* original logical start and stop searching if it doesn't.
4873	*/
4874	if (ac->ac_o_ex.fe_logical >= pa_logical_end(sbi, pa: tmp_pa)) {
4875	spin_unlock(lock: &tmp_pa->pa_lock);
4876	goto try_group_pa;
4877	}
4878
4879	/* non-extent files can't have physical blocks past 2^32 */
4880	if (!(ext4_test_inode_flag(inode: ac->ac_inode, bit: EXT4_INODE_EXTENTS)) &&
4881	(tmp_pa->pa_pstart + EXT4_C2B(sbi, tmp_pa->pa_len) >
4882	EXT4_MAX_BLOCK_FILE_PHYS)) {
4883	/*
4884	* Since PAs don't overlap, we won't find any other PA to
4885	* satisfy this.
4886	*/
4887	spin_unlock(lock: &tmp_pa->pa_lock);
4888	goto try_group_pa;
4889	}
4890
4891	if (tmp_pa->pa_free && likely(ext4_mb_pa_goal_check(ac, tmp_pa))) {
4892	atomic_inc(v: &tmp_pa->pa_count);
4893	ext4_mb_use_inode_pa(ac, pa: tmp_pa);
4894	spin_unlock(lock: &tmp_pa->pa_lock);
4895	read_unlock(&ei->i_prealloc_lock);
4896	return true;
4897	} else {
4898	/*
4899	* We found a valid overlapping pa but couldn't use it because
4900	* it had no free blocks. This should ideally never happen
4901	* because:
4902	*
4903	* 1. When a new inode pa is added to rbtree it must have
4904	* pa_free > 0 since otherwise we won't actually need
4905	* preallocation.
4906	*
4907	* 2. An inode pa that is in the rbtree can only have it's
4908	* pa_free become zero when another thread calls:
4909	* ext4_mb_new_blocks
4910	* ext4_mb_use_preallocated
4911	* ext4_mb_use_inode_pa
4912	*
4913	* 3. Further, after the above calls make pa_free == 0, we will
4914	* immediately remove it from the rbtree in:
4915	* ext4_mb_new_blocks
4916	* ext4_mb_release_context
4917	* ext4_mb_put_pa
4918	*
4919	* 4. Since the pa_free becoming 0 and pa_free getting removed
4920	* from tree both happen in ext4_mb_new_blocks, which is always
4921	* called with i_data_sem held for data allocations, we can be
4922	* sure that another process will never see a pa in rbtree with
4923	* pa_free == 0.
4924	*/
4925	WARN_ON_ONCE(tmp_pa->pa_free == 0);
4926	}
4927	spin_unlock(lock: &tmp_pa->pa_lock);
4928	try_group_pa:
4929	read_unlock(&ei->i_prealloc_lock);
4930
4931	/* can we use group allocation? */
4932	if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
4933	return false;
4934
4935	/* inode may have no locality group for some reason */
4936	lg = ac->ac_lg;
4937	if (lg == NULL)
4938	return false;
4939	order = fls(x: ac->ac_o_ex.fe_len) - 1;
4940	if (order > PREALLOC_TB_SIZE - 1)
4941	/* The max size of hash table is PREALLOC_TB_SIZE */
4942	order = PREALLOC_TB_SIZE - 1;
4943
4944	goal_block = ext4_grp_offs_to_block(sb: ac->ac_sb, fex: &ac->ac_g_ex);
4945	/*
4946	* search for the prealloc space that is having
4947	* minimal distance from the goal block.
4948	*/
4949	for (i = order; i < PREALLOC_TB_SIZE; i++) {
4950	rcu_read_lock();
4951	list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[i],
4952	pa_node.lg_list) {
4953	spin_lock(lock: &tmp_pa->pa_lock);
4954	if (tmp_pa->pa_deleted == 0 &&
4955	tmp_pa->pa_free >= ac->ac_o_ex.fe_len) {
4956
4957	cpa = ext4_mb_check_group_pa(goal_block,
4958	pa: tmp_pa, cpa);
4959	}
4960	spin_unlock(lock: &tmp_pa->pa_lock);
4961	}
4962	rcu_read_unlock();
4963	}
4964	if (cpa) {
4965	ext4_mb_use_group_pa(ac, pa: cpa);
4966	return true;
4967	}
4968	return false;
4969	}
4970
4971	/*
4972	* the function goes through all preallocation in this group and marks them
4973	* used in in-core bitmap. buddy must be generated from this bitmap
4974	* Need to be called with ext4 group lock held
4975	*/
4976	static noinline_for_stack
4977	void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
4978	ext4_group_t group)
4979	{
4980	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
4981	struct ext4_prealloc_space *pa;
4982	struct list_head *cur;
4983	ext4_group_t groupnr;
4984	ext4_grpblk_t start;
4985	int preallocated = 0;
4986	int len;
4987
4988	if (!grp)
4989	return;
4990
4991	/* all form of preallocation discards first load group,
4992	* so the only competing code is preallocation use.
4993	* we don't need any locking here
4994	* notice we do NOT ignore preallocations with pa_deleted
4995	* otherwise we could leave used blocks available for
4996	* allocation in buddy when concurrent ext4_mb_put_pa()
4997	* is dropping preallocation
4998	*/
4999	list_for_each(cur, &grp->bb_prealloc_list) {
5000	pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
5001	spin_lock(lock: &pa->pa_lock);
5002	ext4_get_group_no_and_offset(sb, blocknr: pa->pa_pstart,
5003	blockgrpp: &groupnr, offsetp: &start);
5004	len = pa->pa_len;
5005	spin_unlock(lock: &pa->pa_lock);
5006	if (unlikely(len == 0))
5007	continue;
5008	BUG_ON(groupnr != group);
5009	mb_set_bits(bm: bitmap, cur: start, len);
5010	preallocated += len;
5011	}
5012	mb_debug(sb, "preallocated %d for group %u\n", preallocated, group);
5013	}
5014
5015	static void ext4_mb_mark_pa_deleted(struct super_block *sb,
5016	struct ext4_prealloc_space *pa)
5017	{
5018	struct ext4_inode_info *ei;
5019
5020	if (pa->pa_deleted) {
5021	ext4_warning(sb, "deleted pa, type:%d, pblk:%llu, lblk:%u, len:%d\n",
5022	pa->pa_type, pa->pa_pstart, pa->pa_lstart,
5023	pa->pa_len);
5024	return;
5025	}
5026
5027	pa->pa_deleted = 1;
5028
5029	if (pa->pa_type == MB_INODE_PA) {
5030	ei = EXT4_I(pa->pa_inode);
5031	atomic_dec(v: &ei->i_prealloc_active);
5032	}
5033	}
5034
5035	static inline void ext4_mb_pa_free(struct ext4_prealloc_space *pa)
5036	{
5037	BUG_ON(!pa);
5038	BUG_ON(atomic_read(&pa->pa_count));
5039	BUG_ON(pa->pa_deleted == 0);
5040	kmem_cache_free(s: ext4_pspace_cachep, objp: pa);
5041	}
5042
5043	static void ext4_mb_pa_callback(struct rcu_head *head)
5044	{
5045	struct ext4_prealloc_space *pa;
5046
5047	pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
5048	ext4_mb_pa_free(pa);
5049	}
5050
5051	/*
5052	* drops a reference to preallocated space descriptor
5053	* if this was the last reference and the space is consumed
5054	*/
5055	static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
5056	struct super_block *sb, struct ext4_prealloc_space *pa)
5057	{
5058	ext4_group_t grp;
5059	ext4_fsblk_t grp_blk;
5060	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
5061
5062	/* in this short window concurrent discard can set pa_deleted */
5063	spin_lock(lock: &pa->pa_lock);
5064	if (!atomic_dec_and_test(v: &pa->pa_count) || pa->pa_free != 0) {
5065	spin_unlock(lock: &pa->pa_lock);
5066	return;
5067	}
5068
5069	if (pa->pa_deleted == 1) {
5070	spin_unlock(lock: &pa->pa_lock);
5071	return;
5072	}
5073
5074	ext4_mb_mark_pa_deleted(sb, pa);
5075	spin_unlock(lock: &pa->pa_lock);
5076
5077	grp_blk = pa->pa_pstart;
5078	/*
5079	* If doing group-based preallocation, pa_pstart may be in the
5080	* next group when pa is used up
5081	*/
5082	if (pa->pa_type == MB_GROUP_PA)
5083	grp_blk--;
5084
5085	grp = ext4_get_group_number(sb, block: grp_blk);
5086
5087	/*
5088	* possible race:
5089	*
5090	* P1 (buddy init) P2 (regular allocation)
5091	* find block B in PA
5092	* copy on-disk bitmap to buddy
5093	* mark B in on-disk bitmap
5094	* drop PA from group
5095	* mark all PAs in buddy
5096	*
5097	* thus, P1 initializes buddy with B available. to prevent this
5098	* we make "copy" and "mark all PAs" atomic and serialize "drop PA"
5099	* against that pair
5100	*/
5101	ext4_lock_group(sb, group: grp);
5102	list_del(entry: &pa->pa_group_list);
5103	ext4_unlock_group(sb, group: grp);
5104
5105	if (pa->pa_type == MB_INODE_PA) {
5106	write_lock(pa->pa_node_lock.inode_lock);
5107	rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
5108	write_unlock(pa->pa_node_lock.inode_lock);
5109	ext4_mb_pa_free(pa);
5110	} else {
5111	spin_lock(lock: pa->pa_node_lock.lg_lock);
5112	list_del_rcu(entry: &pa->pa_node.lg_list);
5113	spin_unlock(lock: pa->pa_node_lock.lg_lock);
5114	call_rcu(head: &(pa)->u.pa_rcu, func: ext4_mb_pa_callback);
5115	}
5116	}
5117
5118	static void ext4_mb_pa_rb_insert(struct rb_root *root, struct rb_node *new)
5119	{
5120	struct rb_node **iter = &root->rb_node, *parent = NULL;
5121	struct ext4_prealloc_space *iter_pa, *new_pa;
5122	ext4_lblk_t iter_start, new_start;
5123
5124	while (*iter) {
5125	iter_pa = rb_entry(*iter, struct ext4_prealloc_space,
5126	pa_node.inode_node);
5127	new_pa = rb_entry(new, struct ext4_prealloc_space,
5128	pa_node.inode_node);
5129	iter_start = iter_pa->pa_lstart;
5130	new_start = new_pa->pa_lstart;
5131
5132	parent = *iter;
5133	if (new_start < iter_start)
5134	iter = &((*iter)->rb_left);
5135	else
5136	iter = &((*iter)->rb_right);
5137	}
5138
5139	rb_link_node(node: new, parent, rb_link: iter);
5140	rb_insert_color(new, root);
5141	}
5142
5143	/*
5144	* creates new preallocated space for given inode
5145	*/
5146	static noinline_for_stack void
5147	ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
5148	{
5149	struct super_block *sb = ac->ac_sb;
5150	struct ext4_sb_info *sbi = EXT4_SB(sb);
5151	struct ext4_prealloc_space *pa;
5152	struct ext4_group_info *grp;
5153	struct ext4_inode_info *ei;
5154
5155	/* preallocate only when found space is larger then requested */
5156	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
5157	BUG_ON(ac->ac_status != AC_STATUS_FOUND);
5158	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
5159	BUG_ON(ac->ac_pa == NULL);
5160
5161	pa = ac->ac_pa;
5162
5163	if (ac->ac_b_ex.fe_len < ac->ac_orig_goal_len) {
5164	struct ext4_free_extent ex = {
5165	.fe_logical = ac->ac_g_ex.fe_logical,
5166	.fe_len = ac->ac_orig_goal_len,
5167	};
5168	loff_t orig_goal_end = extent_logical_end(sbi, fex: &ex);
5169	loff_t o_ex_end = extent_logical_end(sbi, fex: &ac->ac_o_ex);
5170
5171	/*
5172	* We can't allocate as much as normalizer wants, so we try
5173	* to get proper lstart to cover the original request, except
5174	* when the goal doesn't cover the original request as below:
5175	*
5176	* orig_ex:2045/2055(10), isize:8417280 -> normalized:0/2048
5177	* best_ex:0/200(200) -> adjusted: 1848/2048(200)
5178	*/
5179	BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
5180	BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
5181
5182	/*
5183	* Use the below logic for adjusting best extent as it keeps
5184	* fragmentation in check while ensuring logical range of best
5185	* extent doesn't overflow out of goal extent:
5186	*
5187	* 1. Check if best ex can be kept at end of goal (before
5188	* cr_best_avail trimmed it) and still cover original start
5189	* 2. Else, check if best ex can be kept at start of goal and
5190	* still cover original end
5191	* 3. Else, keep the best ex at start of original request.
5192	*/
5193	ex.fe_len = ac->ac_b_ex.fe_len;
5194
5195	ex.fe_logical = orig_goal_end - EXT4_C2B(sbi, ex.fe_len);
5196	if (ac->ac_o_ex.fe_logical >= ex.fe_logical)
5197	goto adjust_bex;
5198
5199	ex.fe_logical = ac->ac_g_ex.fe_logical;
5200	if (o_ex_end <= extent_logical_end(sbi, fex: &ex))
5201	goto adjust_bex;
5202
5203	ex.fe_logical = ac->ac_o_ex.fe_logical;
5204	adjust_bex:
5205	ac->ac_b_ex.fe_logical = ex.fe_logical;
5206
5207	BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
5208	BUG_ON(extent_logical_end(sbi, &ex) > orig_goal_end);
5209	}
5210
5211	pa->pa_lstart = ac->ac_b_ex.fe_logical;
5212	pa->pa_pstart = ext4_grp_offs_to_block(sb, fex: &ac->ac_b_ex);
5213	pa->pa_len = ac->ac_b_ex.fe_len;
5214	pa->pa_free = pa->pa_len;
5215	spin_lock_init(&pa->pa_lock);
5216	INIT_LIST_HEAD(list: &pa->pa_group_list);
5217	pa->pa_deleted = 0;
5218	pa->pa_type = MB_INODE_PA;
5219
5220	mb_debug(sb, "new inode pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,
5221	pa->pa_len, pa->pa_lstart);
5222	trace_ext4_mb_new_inode_pa(ac, pa);
5223
5224	atomic_add(i: pa->pa_free, v: &sbi->s_mb_preallocated);
5225	ext4_mb_use_inode_pa(ac, pa);
5226
5227	ei = EXT4_I(ac->ac_inode);
5228	grp = ext4_get_group_info(sb, group: ac->ac_b_ex.fe_group);
5229	if (!grp)
5230	return;
5231
5232	pa->pa_node_lock.inode_lock = &ei->i_prealloc_lock;
5233	pa->pa_inode = ac->ac_inode;
5234
5235	list_add(new: &pa->pa_group_list, head: &grp->bb_prealloc_list);
5236
5237	write_lock(pa->pa_node_lock.inode_lock);
5238	ext4_mb_pa_rb_insert(root: &ei->i_prealloc_node, new: &pa->pa_node.inode_node);
5239	write_unlock(pa->pa_node_lock.inode_lock);
5240	atomic_inc(v: &ei->i_prealloc_active);
5241	}
5242
5243	/*
5244	* creates new preallocated space for locality group inodes belongs to
5245	*/
5246	static noinline_for_stack void
5247	ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
5248	{
5249	struct super_block *sb = ac->ac_sb;
5250	struct ext4_locality_group *lg;
5251	struct ext4_prealloc_space *pa;
5252	struct ext4_group_info *grp;
5253
5254	/* preallocate only when found space is larger then requested */
5255	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
5256	BUG_ON(ac->ac_status != AC_STATUS_FOUND);
5257	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
5258	BUG_ON(ac->ac_pa == NULL);
5259
5260	pa = ac->ac_pa;
5261
5262	pa->pa_pstart = ext4_grp_offs_to_block(sb, fex: &ac->ac_b_ex);
5263	pa->pa_lstart = pa->pa_pstart;
5264	pa->pa_len = ac->ac_b_ex.fe_len;
5265	pa->pa_free = pa->pa_len;
5266	spin_lock_init(&pa->pa_lock);
5267	INIT_LIST_HEAD(list: &pa->pa_node.lg_list);
5268	INIT_LIST_HEAD(list: &pa->pa_group_list);
5269	pa->pa_deleted = 0;
5270	pa->pa_type = MB_GROUP_PA;
5271
5272	mb_debug(sb, "new group pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,
5273	pa->pa_len, pa->pa_lstart);
5274	trace_ext4_mb_new_group_pa(ac, pa);
5275
5276	ext4_mb_use_group_pa(ac, pa);
5277	atomic_add(i: pa->pa_free, v: &EXT4_SB(sb)->s_mb_preallocated);
5278
5279	grp = ext4_get_group_info(sb, group: ac->ac_b_ex.fe_group);
5280	if (!grp)
5281	return;
5282	lg = ac->ac_lg;
5283	BUG_ON(lg == NULL);
5284
5285	pa->pa_node_lock.lg_lock = &lg->lg_prealloc_lock;
5286	pa->pa_inode = NULL;
5287
5288	list_add(new: &pa->pa_group_list, head: &grp->bb_prealloc_list);
5289
5290	/*
5291	* We will later add the new pa to the right bucket
5292	* after updating the pa_free in ext4_mb_release_context
5293	*/
5294	}
5295
5296	static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
5297	{
5298	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
5299	ext4_mb_new_group_pa(ac);
5300	else
5301	ext4_mb_new_inode_pa(ac);
5302	}
5303
5304	/*
5305	* finds all unused blocks in on-disk bitmap, frees them in
5306	* in-core bitmap and buddy.
5307	* @pa must be unlinked from inode and group lists, so that
5308	* nobody else can find/use it.
5309	* the caller MUST hold group/inode locks.
5310	* TODO: optimize the case when there are no in-core structures yet
5311	*/
5312	static noinline_for_stack void
5313	ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
5314	struct ext4_prealloc_space *pa)
5315	{
5316	struct super_block *sb = e4b->bd_sb;
5317	struct ext4_sb_info *sbi = EXT4_SB(sb);
5318	unsigned int end;
5319	unsigned int next;
5320	ext4_group_t group;
5321	ext4_grpblk_t bit;
5322	unsigned long long grp_blk_start;
5323	int free = 0;
5324
5325	BUG_ON(pa->pa_deleted == 0);
5326	ext4_get_group_no_and_offset(sb, blocknr: pa->pa_pstart, blockgrpp: &group, offsetp: &bit);
5327	grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);
5328	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
5329	end = bit + pa->pa_len;
5330
5331	while (bit < end) {
5332	bit = mb_find_next_zero_bit(addr: bitmap_bh->b_data, max: end, start: bit);
5333	if (bit >= end)
5334	break;
5335	next = mb_find_next_bit(addr: bitmap_bh->b_data, max: end, start: bit);
5336	mb_debug(sb, "free preallocated %u/%u in group %u\n",
5337	(unsigned) ext4_group_first_block_no(sb, group) + bit,
5338	(unsigned) next - bit, (unsigned) group);
5339	free += next - bit;
5340
5341	trace_ext4_mballoc_discard(sb, NULL, group, start: bit, len: next - bit);
5342	trace_ext4_mb_release_inode_pa(pa, block: (grp_blk_start +
5343	EXT4_C2B(sbi, bit)),
5344	count: next - bit);
5345	mb_free_blocks(inode: pa->pa_inode, e4b, first: bit, count: next - bit);
5346	bit = next + 1;
5347	}
5348	if (free != pa->pa_free) {
5349	ext4_msg(e4b->bd_sb, KERN_CRIT,
5350	"pa %p: logic %lu, phys. %lu, len %d",
5351	pa, (unsigned long) pa->pa_lstart,
5352	(unsigned long) pa->pa_pstart,
5353	pa->pa_len);
5354	ext4_grp_locked_error(sb, group, 0, 0, "free %u, pa_free %u",
5355	free, pa->pa_free);
5356	/*
5357	* pa is already deleted so we use the value obtained
5358	* from the bitmap and continue.
5359	*/
5360	}
5361	atomic_add(i: free, v: &sbi->s_mb_discarded);
5362	}
5363
5364	static noinline_for_stack void
5365	ext4_mb_release_group_pa(struct ext4_buddy *e4b,
5366	struct ext4_prealloc_space *pa)
5367	{
5368	struct super_block *sb = e4b->bd_sb;
5369	ext4_group_t group;
5370	ext4_grpblk_t bit;
5371
5372	trace_ext4_mb_release_group_pa(sb, pa);
5373	BUG_ON(pa->pa_deleted == 0);
5374	ext4_get_group_no_and_offset(sb, blocknr: pa->pa_pstart, blockgrpp: &group, offsetp: &bit);
5375	if (unlikely(group != e4b->bd_group && pa->pa_len != 0)) {
5376	ext4_warning(sb, "bad group: expected %u, group %u, pa_start %llu",
5377	e4b->bd_group, group, pa->pa_pstart);
5378	return;
5379	}
5380	mb_free_blocks(inode: pa->pa_inode, e4b, first: bit, count: pa->pa_len);
5381	atomic_add(i: pa->pa_len, v: &EXT4_SB(sb)->s_mb_discarded);
5382	trace_ext4_mballoc_discard(sb, NULL, group, start: bit, len: pa->pa_len);
5383	}
5384
5385	/*
5386	* releases all preallocations in given group
5387	*
5388	* first, we need to decide discard policy:
5389	* - when do we discard
5390	* 1) ENOSPC
5391	* - how many do we discard
5392	* 1) how many requested
5393	*/
5394	static noinline_for_stack int
5395	ext4_mb_discard_group_preallocations(struct super_block *sb,
5396	ext4_group_t group, int *busy)
5397	{
5398	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
5399	struct buffer_head *bitmap_bh = NULL;
5400	struct ext4_prealloc_space *pa, *tmp;
5401	LIST_HEAD(list);
5402	struct ext4_buddy e4b;
5403	struct ext4_inode_info *ei;
5404	int err;
5405	int free = 0;
5406
5407	if (!grp)
5408	return 0;
5409	mb_debug(sb, "discard preallocation for group %u\n", group);
5410	if (list_empty(head: &grp->bb_prealloc_list))
5411	goto out_dbg;
5412
5413	bitmap_bh = ext4_read_block_bitmap(sb, block_group: group);
5414	if (IS_ERR(ptr: bitmap_bh)) {
5415	err = PTR_ERR(ptr: bitmap_bh);
5416	ext4_error_err(sb, -err,
5417	"Error %d reading block bitmap for %u",
5418	err, group);
5419	goto out_dbg;
5420	}
5421
5422	err = ext4_mb_load_buddy(sb, group, e4b: &e4b);
5423	if (err) {
5424	ext4_warning(sb, "Error %d loading buddy information for %u",
5425	err, group);
5426	put_bh(bh: bitmap_bh);
5427	goto out_dbg;
5428	}
5429
5430	ext4_lock_group(sb, group);
5431	list_for_each_entry_safe(pa, tmp,
5432	&grp->bb_prealloc_list, pa_group_list) {
5433	spin_lock(lock: &pa->pa_lock);
5434	if (atomic_read(v: &pa->pa_count)) {
5435	spin_unlock(lock: &pa->pa_lock);
5436	*busy = 1;
5437	continue;
5438	}
5439	if (pa->pa_deleted) {
5440	spin_unlock(lock: &pa->pa_lock);
5441	continue;
5442	}
5443
5444	/* seems this one can be freed ... */
5445	ext4_mb_mark_pa_deleted(sb, pa);
5446
5447	if (!free)
5448	this_cpu_inc(discard_pa_seq);
5449
5450	/* we can trust pa_free ... */
5451	free += pa->pa_free;
5452
5453	spin_unlock(lock: &pa->pa_lock);
5454
5455	list_del(entry: &pa->pa_group_list);
5456	list_add(new: &pa->u.pa_tmp_list, head: &list);
5457	}
5458
5459	/* now free all selected PAs */
5460	list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
5461
5462	/* remove from object (inode or locality group) */
5463	if (pa->pa_type == MB_GROUP_PA) {
5464	spin_lock(lock: pa->pa_node_lock.lg_lock);
5465	list_del_rcu(entry: &pa->pa_node.lg_list);
5466	spin_unlock(lock: pa->pa_node_lock.lg_lock);
5467	} else {
5468	write_lock(pa->pa_node_lock.inode_lock);
5469	ei = EXT4_I(pa->pa_inode);
5470	rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
5471	write_unlock(pa->pa_node_lock.inode_lock);
5472	}
5473
5474	list_del(entry: &pa->u.pa_tmp_list);
5475
5476	if (pa->pa_type == MB_GROUP_PA) {
5477	ext4_mb_release_group_pa(e4b: &e4b, pa);
5478	call_rcu(head: &(pa)->u.pa_rcu, func: ext4_mb_pa_callback);
5479	} else {
5480	ext4_mb_release_inode_pa(e4b: &e4b, bitmap_bh, pa);
5481	ext4_mb_pa_free(pa);
5482	}
5483	}
5484
5485	ext4_unlock_group(sb, group);
5486	ext4_mb_unload_buddy(e4b: &e4b);
5487	put_bh(bh: bitmap_bh);
5488	out_dbg:
5489	mb_debug(sb, "discarded (%d) blocks preallocated for group %u bb_free (%d)\n",
5490	free, group, grp->bb_free);
5491	return free;
5492	}
5493
5494	/*
5495	* releases all non-used preallocated blocks for given inode
5496	*
5497	* It's important to discard preallocations under i_data_sem
5498	* We don't want another block to be served from the prealloc
5499	* space when we are discarding the inode prealloc space.
5500	*
5501	* FIXME!! Make sure it is valid at all the call sites
5502	*/
5503	void ext4_discard_preallocations(struct inode *inode)
5504	{
5505	struct ext4_inode_info *ei = EXT4_I(inode);
5506	struct super_block *sb = inode->i_sb;
5507	struct buffer_head *bitmap_bh = NULL;
5508	struct ext4_prealloc_space *pa, *tmp;
5509	ext4_group_t group = 0;
5510	LIST_HEAD(list);
5511	struct ext4_buddy e4b;
5512	struct rb_node *iter;
5513	int err;
5514
5515	if (!S_ISREG(inode->i_mode))
5516	return;
5517
5518	if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)
5519	return;
5520
5521	mb_debug(sb, "discard preallocation for inode %lu\n",
5522	inode->i_ino);
5523	trace_ext4_discard_preallocations(inode,
5524	len: atomic_read(v: &ei->i_prealloc_active));
5525
5526	repeat:
5527	/* first, collect all pa's in the inode */
5528	write_lock(&ei->i_prealloc_lock);
5529	for (iter = rb_first(&ei->i_prealloc_node); iter;
5530	iter = rb_next(iter)) {
5531	pa = rb_entry(iter, struct ext4_prealloc_space,
5532	pa_node.inode_node);
5533	BUG_ON(pa->pa_node_lock.inode_lock != &ei->i_prealloc_lock);
5534
5535	spin_lock(lock: &pa->pa_lock);
5536	if (atomic_read(v: &pa->pa_count)) {
5537	/* this shouldn't happen often - nobody should
5538	* use preallocation while we're discarding it */
5539	spin_unlock(lock: &pa->pa_lock);
5540	write_unlock(&ei->i_prealloc_lock);
5541	ext4_msg(sb, KERN_ERR,
5542	"uh-oh! used pa while discarding");
5543	WARN_ON(1);
5544	schedule_timeout_uninterruptible(HZ);
5545	goto repeat;
5546
5547	}
5548	if (pa->pa_deleted == 0) {
5549	ext4_mb_mark_pa_deleted(sb, pa);
5550	spin_unlock(lock: &pa->pa_lock);
5551	rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
5552	list_add(new: &pa->u.pa_tmp_list, head: &list);
5553	continue;
5554	}
5555
5556	/* someone is deleting pa right now */
5557	spin_unlock(lock: &pa->pa_lock);
5558	write_unlock(&ei->i_prealloc_lock);
5559
5560	/* we have to wait here because pa_deleted
5561	* doesn't mean pa is already unlinked from
5562	* the list. as we might be called from
5563	* ->clear_inode() the inode will get freed
5564	* and concurrent thread which is unlinking
5565	* pa from inode's list may access already
5566	* freed memory, bad-bad-bad */
5567
5568	/* XXX: if this happens too often, we can
5569	* add a flag to force wait only in case
5570	* of ->clear_inode(), but not in case of
5571	* regular truncate */
5572	schedule_timeout_uninterruptible(HZ);
5573	goto repeat;
5574	}
5575	write_unlock(&ei->i_prealloc_lock);
5576
5577	list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
5578	BUG_ON(pa->pa_type != MB_INODE_PA);
5579	group = ext4_get_group_number(sb, block: pa->pa_pstart);
5580
5581	err = ext4_mb_load_buddy_gfp(sb, group, e4b: &e4b,
5582	GFP_NOFS|__GFP_NOFAIL);
5583	if (err) {
5584	ext4_error_err(sb, -err, "Error %d loading buddy information for %u",
5585	err, group);
5586	continue;
5587	}
5588
5589	bitmap_bh = ext4_read_block_bitmap(sb, block_group: group);
5590	if (IS_ERR(ptr: bitmap_bh)) {
5591	err = PTR_ERR(ptr: bitmap_bh);
5592	ext4_error_err(sb, -err, "Error %d reading block bitmap for %u",
5593	err, group);
5594	ext4_mb_unload_buddy(e4b: &e4b);
5595	continue;
5596	}
5597
5598	ext4_lock_group(sb, group);
5599	list_del(entry: &pa->pa_group_list);
5600	ext4_mb_release_inode_pa(e4b: &e4b, bitmap_bh, pa);
5601	ext4_unlock_group(sb, group);
5602
5603	ext4_mb_unload_buddy(e4b: &e4b);
5604	put_bh(bh: bitmap_bh);
5605
5606	list_del(entry: &pa->u.pa_tmp_list);
5607	ext4_mb_pa_free(pa);
5608	}
5609	}
5610
5611	static int ext4_mb_pa_alloc(struct ext4_allocation_context *ac)
5612	{
5613	struct ext4_prealloc_space *pa;
5614
5615	BUG_ON(ext4_pspace_cachep == NULL);
5616	pa = kmem_cache_zalloc(k: ext4_pspace_cachep, GFP_NOFS);
5617	if (!pa)
5618	return -ENOMEM;
5619	atomic_set(v: &pa->pa_count, i: 1);
5620	ac->ac_pa = pa;
5621	return 0;
5622	}
5623
5624	static void ext4_mb_pa_put_free(struct ext4_allocation_context *ac)
5625	{
5626	struct ext4_prealloc_space *pa = ac->ac_pa;
5627
5628	BUG_ON(!pa);
5629	ac->ac_pa = NULL;
5630	WARN_ON(!atomic_dec_and_test(&pa->pa_count));
5631	/*
5632	* current function is only called due to an error or due to
5633	* len of found blocks < len of requested blocks hence the PA has not
5634	* been added to grp->bb_prealloc_list. So we don't need to lock it
5635	*/
5636	pa->pa_deleted = 1;
5637	ext4_mb_pa_free(pa);
5638	}
5639
5640	#ifdef CONFIG_EXT4_DEBUG
5641	static inline void ext4_mb_show_pa(struct super_block *sb)
5642	{
5643	ext4_group_t i, ngroups;
5644
5645	if (ext4_forced_shutdown(sb))
5646	return;
5647
5648	ngroups = ext4_get_groups_count(sb);
5649	mb_debug(sb, "groups: ");
5650	for (i = 0; i < ngroups; i++) {
5651	struct ext4_group_info *grp = ext4_get_group_info(sb, group: i);
5652	struct ext4_prealloc_space *pa;
5653	ext4_grpblk_t start;
5654	struct list_head *cur;
5655
5656	if (!grp)
5657	continue;
5658	ext4_lock_group(sb, group: i);
5659	list_for_each(cur, &grp->bb_prealloc_list) {
5660	pa = list_entry(cur, struct ext4_prealloc_space,
5661	pa_group_list);
5662	spin_lock(lock: &pa->pa_lock);
5663	ext4_get_group_no_and_offset(sb, blocknr: pa->pa_pstart,
5664	NULL, offsetp: &start);
5665	spin_unlock(lock: &pa->pa_lock);
5666	mb_debug(sb, "PA:%u:%d:%d\n", i, start,
5667	pa->pa_len);
5668	}
5669	ext4_unlock_group(sb, group: i);
5670	mb_debug(sb, "%u: %d/%d\n", i, grp->bb_free,
5671	grp->bb_fragments);
5672	}
5673	}
5674
5675	static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
5676	{
5677	struct super_block *sb = ac->ac_sb;
5678
5679	if (ext4_forced_shutdown(sb))
5680	return;
5681
5682	mb_debug(sb, "Can't allocate:"
5683	" Allocation context details:");
5684	mb_debug(sb, "status %u flags 0x%x",
5685	ac->ac_status, ac->ac_flags);
5686	mb_debug(sb, "orig %lu/%lu/%lu@%lu, "
5687	"goal %lu/%lu/%lu@%lu, "
5688	"best %lu/%lu/%lu@%lu cr %d",
5689	(unsigned long)ac->ac_o_ex.fe_group,
5690	(unsigned long)ac->ac_o_ex.fe_start,
5691	(unsigned long)ac->ac_o_ex.fe_len,
5692	(unsigned long)ac->ac_o_ex.fe_logical,
5693	(unsigned long)ac->ac_g_ex.fe_group,
5694	(unsigned long)ac->ac_g_ex.fe_start,
5695	(unsigned long)ac->ac_g_ex.fe_len,
5696	(unsigned long)ac->ac_g_ex.fe_logical,
5697	(unsigned long)ac->ac_b_ex.fe_group,
5698	(unsigned long)ac->ac_b_ex.fe_start,
5699	(unsigned long)ac->ac_b_ex.fe_len,
5700	(unsigned long)ac->ac_b_ex.fe_logical,
5701	(int)ac->ac_criteria);
5702	mb_debug(sb, "%u found", ac->ac_found);
5703	mb_debug(sb, "used pa: %s, ", ac->ac_pa ? "yes" : "no");
5704	if (ac->ac_pa)
5705	mb_debug(sb, "pa_type %s\n", ac->ac_pa->pa_type == MB_GROUP_PA ?
5706	"group pa" : "inode pa");
5707	ext4_mb_show_pa(sb);
5708	}
5709	#else
5710	static inline void ext4_mb_show_pa(struct super_block *sb)
5711	{
5712	}
5713	static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
5714	{
5715	ext4_mb_show_pa(ac->ac_sb);
5716	}
5717	#endif
5718
5719	/*
5720	* We use locality group preallocation for small size file. The size of the
5721	* file is determined by the current size or the resulting size after
5722	* allocation which ever is larger
5723	*
5724	* One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req
5725	*/
5726	static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
5727	{
5728	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
5729	int bsbits = ac->ac_sb->s_blocksize_bits;
5730	loff_t size, isize;
5731	bool inode_pa_eligible, group_pa_eligible;
5732
5733	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
5734	return;
5735
5736	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
5737	return;
5738
5739	group_pa_eligible = sbi->s_mb_group_prealloc > 0;
5740	inode_pa_eligible = true;
5741	size = extent_logical_end(sbi, fex: &ac->ac_o_ex);
5742	isize = (i_size_read(inode: ac->ac_inode) + ac->ac_sb->s_blocksize - 1)
5743	>> bsbits;
5744
5745	/* No point in using inode preallocation for closed files */
5746	if ((size == isize) && !ext4_fs_is_busy(sbi) &&
5747	!inode_is_open_for_write(inode: ac->ac_inode))
5748	inode_pa_eligible = false;
5749
5750	size = max(size, isize);
5751	/* Don't use group allocation for large files */
5752	if (size > sbi->s_mb_stream_request)
5753	group_pa_eligible = false;
5754
5755	if (!group_pa_eligible) {
5756	if (inode_pa_eligible)
5757	ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
5758	else
5759	ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;
5760	return;
5761	}
5762
5763	BUG_ON(ac->ac_lg != NULL);
5764	/*
5765	* locality group prealloc space are per cpu. The reason for having
5766	* per cpu locality group is to reduce the contention between block
5767	* request from multiple CPUs.
5768	*/
5769	ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);
5770
5771	/* we're going to use group allocation */
5772	ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
5773
5774	/* serialize all allocations in the group */
5775	mutex_lock(&ac->ac_lg->lg_mutex);
5776	}
5777
5778	static noinline_for_stack void
5779	ext4_mb_initialize_context(struct ext4_allocation_context *ac,
5780	struct ext4_allocation_request *ar)
5781	{
5782	struct super_block *sb = ar->inode->i_sb;
5783	struct ext4_sb_info *sbi = EXT4_SB(sb);
5784	struct ext4_super_block *es = sbi->s_es;
5785	ext4_group_t group;
5786	unsigned int len;
5787	ext4_fsblk_t goal;
5788	ext4_grpblk_t block;
5789
5790	/* we can't allocate > group size */
5791	len = ar->len;
5792
5793	/* just a dirty hack to filter too big requests */
5794	if (len >= EXT4_CLUSTERS_PER_GROUP(sb))
5795	len = EXT4_CLUSTERS_PER_GROUP(sb);
5796
5797	/* start searching from the goal */
5798	goal = ar->goal;
5799	if (goal < le32_to_cpu(es->s_first_data_block) ||
5800	goal >= ext4_blocks_count(es))
5801	goal = le32_to_cpu(es->s_first_data_block);
5802	ext4_get_group_no_and_offset(sb, blocknr: goal, blockgrpp: &group, offsetp: &block);
5803
5804	/* set up allocation goals */
5805	ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);
5806	ac->ac_status = AC_STATUS_CONTINUE;
5807	ac->ac_sb = sb;
5808	ac->ac_inode = ar->inode;
5809	ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
5810	ac->ac_o_ex.fe_group = group;
5811	ac->ac_o_ex.fe_start = block;
5812	ac->ac_o_ex.fe_len = len;
5813	ac->ac_g_ex = ac->ac_o_ex;
5814	ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;
5815	ac->ac_flags = ar->flags;
5816
5817	/* we have to define context: we'll work with a file or
5818	* locality group. this is a policy, actually */
5819	ext4_mb_group_or_file(ac);
5820
5821	mb_debug(sb, "init ac: %u blocks @ %u, goal %u, flags 0x%x, 2^%d, "
5822	"left: %u/%u, right %u/%u to %swritable\n",
5823	(unsigned) ar->len, (unsigned) ar->logical,
5824	(unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
5825	(unsigned) ar->lleft, (unsigned) ar->pleft,
5826	(unsigned) ar->lright, (unsigned) ar->pright,
5827	inode_is_open_for_write(ar->inode) ? "" : "non-");
5828	}
5829
5830	static noinline_for_stack void
5831	ext4_mb_discard_lg_preallocations(struct super_block *sb,
5832	struct ext4_locality_group *lg,
5833	int order, int total_entries)
5834	{
5835	ext4_group_t group = 0;
5836	struct ext4_buddy e4b;
5837	LIST_HEAD(discard_list);
5838	struct ext4_prealloc_space *pa, *tmp;
5839
5840	mb_debug(sb, "discard locality group preallocation\n");
5841
5842	spin_lock(lock: &lg->lg_prealloc_lock);
5843	list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
5844	pa_node.lg_list,
5845	lockdep_is_held(&lg->lg_prealloc_lock)) {
5846	spin_lock(lock: &pa->pa_lock);
5847	if (atomic_read(v: &pa->pa_count)) {
5848	/*
5849	* This is the pa that we just used
5850	* for block allocation. So don't
5851	* free that
5852	*/
5853	spin_unlock(lock: &pa->pa_lock);
5854	continue;
5855	}
5856	if (pa->pa_deleted) {
5857	spin_unlock(lock: &pa->pa_lock);
5858	continue;
5859	}
5860	/* only lg prealloc space */
5861	BUG_ON(pa->pa_type != MB_GROUP_PA);
5862
5863	/* seems this one can be freed ... */
5864	ext4_mb_mark_pa_deleted(sb, pa);
5865	spin_unlock(lock: &pa->pa_lock);
5866
5867	list_del_rcu(entry: &pa->pa_node.lg_list);
5868	list_add(new: &pa->u.pa_tmp_list, head: &discard_list);
5869
5870	total_entries--;
5871	if (total_entries <= 5) {
5872	/*
5873	* we want to keep only 5 entries
5874	* allowing it to grow to 8. This
5875	* mak sure we don't call discard
5876	* soon for this list.
5877	*/
5878	break;
5879	}
5880	}
5881	spin_unlock(lock: &lg->lg_prealloc_lock);
5882
5883	list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {
5884	int err;
5885
5886	group = ext4_get_group_number(sb, block: pa->pa_pstart);
5887	err = ext4_mb_load_buddy_gfp(sb, group, e4b: &e4b,
5888	GFP_NOFS|__GFP_NOFAIL);
5889	if (err) {
5890	ext4_error_err(sb, -err, "Error %d loading buddy information for %u",
5891	err, group);
5892	continue;
5893	}
5894	ext4_lock_group(sb, group);
5895	list_del(entry: &pa->pa_group_list);
5896	ext4_mb_release_group_pa(e4b: &e4b, pa);
5897	ext4_unlock_group(sb, group);
5898
5899	ext4_mb_unload_buddy(e4b: &e4b);
5900	list_del(entry: &pa->u.pa_tmp_list);
5901	call_rcu(head: &(pa)->u.pa_rcu, func: ext4_mb_pa_callback);
5902	}
5903	}
5904
5905	/*
5906	* We have incremented pa_count. So it cannot be freed at this
5907	* point. Also we hold lg_mutex. So no parallel allocation is
5908	* possible from this lg. That means pa_free cannot be updated.
5909	*
5910	* A parallel ext4_mb_discard_group_preallocations is possible.
5911	* which can cause the lg_prealloc_list to be updated.
5912	*/
5913
5914	static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)
5915	{
5916	int order, added = 0, lg_prealloc_count = 1;
5917	struct super_block *sb = ac->ac_sb;
5918	struct ext4_locality_group *lg = ac->ac_lg;
5919	struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;
5920
5921	order = fls(x: pa->pa_free) - 1;
5922	if (order > PREALLOC_TB_SIZE - 1)
5923	/* The max size of hash table is PREALLOC_TB_SIZE */
5924	order = PREALLOC_TB_SIZE - 1;
5925	/* Add the prealloc space to lg */
5926	spin_lock(lock: &lg->lg_prealloc_lock);
5927	list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
5928	pa_node.lg_list,
5929	lockdep_is_held(&lg->lg_prealloc_lock)) {
5930	spin_lock(lock: &tmp_pa->pa_lock);
5931	if (tmp_pa->pa_deleted) {
5932	spin_unlock(lock: &tmp_pa->pa_lock);
5933	continue;
5934	}
5935	if (!added && pa->pa_free < tmp_pa->pa_free) {
5936	/* Add to the tail of the previous entry */
5937	list_add_tail_rcu(new: &pa->pa_node.lg_list,
5938	head: &tmp_pa->pa_node.lg_list);
5939	added = 1;
5940	/*
5941	* we want to count the total
5942	* number of entries in the list
5943	*/
5944	}
5945	spin_unlock(lock: &tmp_pa->pa_lock);
5946	lg_prealloc_count++;
5947	}
5948	if (!added)
5949	list_add_tail_rcu(new: &pa->pa_node.lg_list,
5950	head: &lg->lg_prealloc_list[order]);
5951	spin_unlock(lock: &lg->lg_prealloc_lock);
5952
5953	/* Now trim the list to be not more than 8 elements */
5954	if (lg_prealloc_count > 8)
5955	ext4_mb_discard_lg_preallocations(sb, lg,
5956	order, total_entries: lg_prealloc_count);
5957	}
5958
5959	/*
5960	* release all resource we used in allocation
5961	*/
5962	static void ext4_mb_release_context(struct ext4_allocation_context *ac)
5963	{
5964	struct ext4_sb_info *sbi = EXT4_SB(sb: ac->ac_sb);
5965	struct ext4_prealloc_space *pa = ac->ac_pa;
5966	if (pa) {
5967	if (pa->pa_type == MB_GROUP_PA) {
5968	/* see comment in ext4_mb_use_group_pa() */
5969	spin_lock(lock: &pa->pa_lock);
5970	pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
5971	pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
5972	pa->pa_free -= ac->ac_b_ex.fe_len;
5973	pa->pa_len -= ac->ac_b_ex.fe_len;
5974	spin_unlock(lock: &pa->pa_lock);
5975
5976	/*
5977	* We want to add the pa to the right bucket.
5978	* Remove it from the list and while adding
5979	* make sure the list to which we are adding
5980	* doesn't grow big.
5981	*/
5982	if (likely(pa->pa_free)) {
5983	spin_lock(lock: pa->pa_node_lock.lg_lock);
5984	list_del_rcu(entry: &pa->pa_node.lg_list);
5985	spin_unlock(lock: pa->pa_node_lock.lg_lock);
5986	ext4_mb_add_n_trim(ac);
5987	}
5988	}
5989
5990	ext4_mb_put_pa(ac, sb: ac->ac_sb, pa);
5991	}
5992	if (ac->ac_bitmap_page)
5993	put_page(page: ac->ac_bitmap_page);
5994	if (ac->ac_buddy_page)
5995	put_page(page: ac->ac_buddy_page);
5996	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
5997	mutex_unlock(lock: &ac->ac_lg->lg_mutex);
5998	ext4_mb_collect_stats(ac);
5999	}
6000
6001	static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
6002	{
6003	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
6004	int ret;
6005	int freed = 0, busy = 0;
6006	int retry = 0;
6007
6008	trace_ext4_mb_discard_preallocations(sb, needed);
6009
6010	if (needed == 0)
6011	needed = EXT4_CLUSTERS_PER_GROUP(sb) + 1;
6012	repeat:
6013	for (i = 0; i < ngroups && needed > 0; i++) {
6014	ret = ext4_mb_discard_group_preallocations(sb, group: i, busy: &busy);
6015	freed += ret;
6016	needed -= ret;
6017	cond_resched();
6018	}
6019
6020	if (needed > 0 && busy && ++retry < 3) {
6021	busy = 0;
6022	goto repeat;
6023	}
6024
6025	return freed;
6026	}
6027
6028	static bool ext4_mb_discard_preallocations_should_retry(struct super_block *sb,
6029	struct ext4_allocation_context *ac, u64 *seq)
6030	{
6031	int freed;
6032	u64 seq_retry = 0;
6033	bool ret = false;
6034
6035	freed = ext4_mb_discard_preallocations(sb, needed: ac->ac_o_ex.fe_len);
6036	if (freed) {
6037	ret = true;
6038	goto out_dbg;
6039	}
6040	seq_retry = ext4_get_discard_pa_seq_sum();
6041	if (!(ac->ac_flags & EXT4_MB_STRICT_CHECK) || seq_retry != *seq) {
6042	ac->ac_flags |= EXT4_MB_STRICT_CHECK;
6043	*seq = seq_retry;
6044	ret = true;
6045	}
6046
6047	out_dbg:
6048	mb_debug(sb, "freed %d, retry ? %s\n", freed, ret ? "yes" : "no");
6049	return ret;
6050	}
6051
6052	/*
6053	* Simple allocator for Ext4 fast commit replay path. It searches for blocks
6054	* linearly starting at the goal block and also excludes the blocks which
6055	* are going to be in use after fast commit replay.
6056	*/
6057	static ext4_fsblk_t
6058	ext4_mb_new_blocks_simple(struct ext4_allocation_request *ar, int *errp)
6059	{
6060	struct buffer_head *bitmap_bh;
6061	struct super_block *sb = ar->inode->i_sb;
6062	struct ext4_sb_info *sbi = EXT4_SB(sb);
6063	ext4_group_t group, nr;
6064	ext4_grpblk_t blkoff;
6065	ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
6066	ext4_grpblk_t i = 0;
6067	ext4_fsblk_t goal, block;
6068	struct ext4_super_block *es = sbi->s_es;
6069
6070	goal = ar->goal;
6071	if (goal < le32_to_cpu(es->s_first_data_block) ||
6072	goal >= ext4_blocks_count(es))
6073	goal = le32_to_cpu(es->s_first_data_block);
6074
6075	ar->len = 0;
6076	ext4_get_group_no_and_offset(sb, blocknr: goal, blockgrpp: &group, offsetp: &blkoff);
6077	for (nr = ext4_get_groups_count(sb); nr > 0; nr--) {
6078	bitmap_bh = ext4_read_block_bitmap(sb, block_group: group);
6079	if (IS_ERR(ptr: bitmap_bh)) {
6080	*errp = PTR_ERR(ptr: bitmap_bh);
6081	pr_warn("Failed to read block bitmap\n");
6082	return 0;
6083	}
6084
6085	while (1) {
6086	i = mb_find_next_zero_bit(addr: bitmap_bh->b_data, max,
6087	start: blkoff);
6088	if (i >= max)
6089	break;
6090	if (ext4_fc_replay_check_excluded(sb,
6091	block: ext4_group_first_block_no(sb, group_no: group) +
6092	EXT4_C2B(sbi, i))) {
6093	blkoff = i + 1;
6094	} else
6095	break;
6096	}
6097	brelse(bh: bitmap_bh);
6098	if (i < max)
6099	break;
6100
6101	if (++group >= ext4_get_groups_count(sb))
6102	group = 0;
6103
6104	blkoff = 0;
6105	}
6106
6107	if (i >= max) {
6108	*errp = -ENOSPC;
6109	return 0;
6110	}
6111
6112	block = ext4_group_first_block_no(sb, group_no: group) + EXT4_C2B(sbi, i);
6113	ext4_mb_mark_bb(sb, block, len: 1, state: true);
6114	ar->len = 1;
6115
6116	return block;
6117	}
6118
6119	/*
6120	* Main entry point into mballoc to allocate blocks
6121	* it tries to use preallocation first, then falls back
6122	* to usual allocation
6123	*/
6124	ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
6125	struct ext4_allocation_request *ar, int *errp)
6126	{
6127	struct ext4_allocation_context *ac = NULL;
6128	struct ext4_sb_info *sbi;
6129	struct super_block *sb;
6130	ext4_fsblk_t block = 0;
6131	unsigned int inquota = 0;
6132	unsigned int reserv_clstrs = 0;
6133	int retries = 0;
6134	u64 seq;
6135
6136	might_sleep();
6137	sb = ar->inode->i_sb;
6138	sbi = EXT4_SB(sb);
6139
6140	trace_ext4_request_blocks(ar);
6141	if (sbi->s_mount_state & EXT4_FC_REPLAY)
6142	return ext4_mb_new_blocks_simple(ar, errp);
6143
6144	/* Allow to use superuser reservation for quota file */
6145	if (ext4_is_quota_file(inode: ar->inode))
6146	ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;
6147
6148	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {
6149	/* Without delayed allocation we need to verify
6150	* there is enough free blocks to do block allocation
6151	* and verify allocation doesn't exceed the quota limits.
6152	*/
6153	while (ar->len &&
6154	ext4_claim_free_clusters(sbi, nclusters: ar->len, flags: ar->flags)) {
6155
6156	/* let others to free the space */
6157	cond_resched();
6158	ar->len = ar->len >> 1;
6159	}
6160	if (!ar->len) {
6161	ext4_mb_show_pa(sb);
6162	*errp = -ENOSPC;
6163	return 0;
6164	}
6165	reserv_clstrs = ar->len;
6166	if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {
6167	dquot_alloc_block_nofail(inode: ar->inode,
6168	EXT4_C2B(sbi, ar->len));
6169	} else {
6170	while (ar->len &&
6171	dquot_alloc_block(inode: ar->inode,
6172	EXT4_C2B(sbi, ar->len))) {
6173
6174	ar->flags |= EXT4_MB_HINT_NOPREALLOC;
6175	ar->len--;
6176	}
6177	}
6178	inquota = ar->len;
6179	if (ar->len == 0) {
6180	*errp = -EDQUOT;
6181	goto out;
6182	}
6183	}
6184
6185	ac = kmem_cache_zalloc(k: ext4_ac_cachep, GFP_NOFS);
6186	if (!ac) {
6187	ar->len = 0;
6188	*errp = -ENOMEM;
6189	goto out;
6190	}
6191
6192	ext4_mb_initialize_context(ac, ar);
6193
6194	ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
6195	seq = this_cpu_read(discard_pa_seq);
6196	if (!ext4_mb_use_preallocated(ac)) {
6197	ac->ac_op = EXT4_MB_HISTORY_ALLOC;
6198	ext4_mb_normalize_request(ac, ar);
6199
6200	*errp = ext4_mb_pa_alloc(ac);
6201	if (*errp)
6202	goto errout;
6203	repeat:
6204	/* allocate space in core */
6205	*errp = ext4_mb_regular_allocator(ac);
6206	/*
6207	* pa allocated above is added to grp->bb_prealloc_list only
6208	* when we were able to allocate some block i.e. when
6209	* ac->ac_status == AC_STATUS_FOUND.
6210	* And error from above mean ac->ac_status != AC_STATUS_FOUND
6211	* So we have to free this pa here itself.
6212	*/
6213	if (*errp) {
6214	ext4_mb_pa_put_free(ac);
6215	ext4_discard_allocated_blocks(ac);
6216	goto errout;
6217	}
6218	if (ac->ac_status == AC_STATUS_FOUND &&
6219	ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)
6220	ext4_mb_pa_put_free(ac);
6221	}
6222	if (likely(ac->ac_status == AC_STATUS_FOUND)) {
6223	*errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs);
6224	if (*errp) {
6225	ext4_discard_allocated_blocks(ac);
6226	goto errout;
6227	} else {
6228	block = ext4_grp_offs_to_block(sb, fex: &ac->ac_b_ex);
6229	ar->len = ac->ac_b_ex.fe_len;
6230	}
6231	} else {
6232	if (++retries < 3 &&
6233	ext4_mb_discard_preallocations_should_retry(sb, ac, seq: &seq))
6234	goto repeat;
6235	/*
6236	* If block allocation fails then the pa allocated above
6237	* needs to be freed here itself.
6238	*/
6239	ext4_mb_pa_put_free(ac);
6240	*errp = -ENOSPC;
6241	}
6242
6243	if (*errp) {
6244	errout:
6245	ac->ac_b_ex.fe_len = 0;
6246	ar->len = 0;
6247	ext4_mb_show_ac(ac);
6248	}
6249	ext4_mb_release_context(ac);
6250	kmem_cache_free(s: ext4_ac_cachep, objp: ac);
6251	out:
6252	if (inquota && ar->len < inquota)
6253	dquot_free_block(inode: ar->inode, EXT4_C2B(sbi, inquota - ar->len));
6254	if (!ar->len) {
6255	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)
6256	/* release all the reserved blocks if non delalloc */
6257	percpu_counter_sub(fbc: &sbi->s_dirtyclusters_counter,
6258	amount: reserv_clstrs);
6259	}
6260
6261	trace_ext4_allocate_blocks(ar, block: (unsigned long long)block);
6262
6263	return block;
6264	}
6265
6266	/*
6267	* We can merge two free data extents only if the physical blocks
6268	* are contiguous, AND the extents were freed by the same transaction,
6269	* AND the blocks are associated with the same group.
6270	*/
6271	static void ext4_try_merge_freed_extent(struct ext4_sb_info *sbi,
6272	struct ext4_free_data *entry,
6273	struct ext4_free_data *new_entry,
6274	struct rb_root *entry_rb_root)
6275	{
6276	if ((entry->efd_tid != new_entry->efd_tid) ||
6277	(entry->efd_group != new_entry->efd_group))
6278	return;
6279	if (entry->efd_start_cluster + entry->efd_count ==
6280	new_entry->efd_start_cluster) {
6281	new_entry->efd_start_cluster = entry->efd_start_cluster;
6282	new_entry->efd_count += entry->efd_count;
6283	} else if (new_entry->efd_start_cluster + new_entry->efd_count ==
6284	entry->efd_start_cluster) {
6285	new_entry->efd_count += entry->efd_count;
6286	} else
6287	return;
6288	spin_lock(lock: &sbi->s_md_lock);
6289	list_del(entry: &entry->efd_list);
6290	spin_unlock(lock: &sbi->s_md_lock);
6291	rb_erase(&entry->efd_node, entry_rb_root);
6292	kmem_cache_free(s: ext4_free_data_cachep, objp: entry);
6293	}
6294
6295	static noinline_for_stack void
6296	ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
6297	struct ext4_free_data *new_entry)
6298	{
6299	ext4_group_t group = e4b->bd_group;
6300	ext4_grpblk_t cluster;
6301	ext4_grpblk_t clusters = new_entry->efd_count;
6302	struct ext4_free_data *entry;
6303	struct ext4_group_info *db = e4b->bd_info;
6304	struct super_block *sb = e4b->bd_sb;
6305	struct ext4_sb_info *sbi = EXT4_SB(sb);
6306	struct rb_node **n = &db->bb_free_root.rb_node, *node;
6307	struct rb_node *parent = NULL, *new_node;
6308
6309	BUG_ON(!ext4_handle_valid(handle));
6310	BUG_ON(e4b->bd_bitmap_page == NULL);
6311	BUG_ON(e4b->bd_buddy_page == NULL);
6312
6313	new_node = &new_entry->efd_node;
6314	cluster = new_entry->efd_start_cluster;
6315
6316	if (!*n) {
6317	/* first free block exent. We need to
6318	protect buddy cache from being freed,
6319	* otherwise we'll refresh it from
6320	* on-disk bitmap and lose not-yet-available
6321	* blocks */
6322	get_page(page: e4b->bd_buddy_page);
6323	get_page(page: e4b->bd_bitmap_page);
6324	}
6325	while (*n) {
6326	parent = *n;
6327	entry = rb_entry(parent, struct ext4_free_data, efd_node);
6328	if (cluster < entry->efd_start_cluster)
6329	n = &(*n)->rb_left;
6330	else if (cluster >= (entry->efd_start_cluster + entry->efd_count))
6331	n = &(*n)->rb_right;
6332	else {
6333	ext4_grp_locked_error(sb, group, 0,
6334	ext4_group_first_block_no(sb, group) +
6335	EXT4_C2B(sbi, cluster),
6336	"Block already on to-be-freed list");
6337	kmem_cache_free(s: ext4_free_data_cachep, objp: new_entry);
6338	return;
6339	}
6340	}
6341
6342	rb_link_node(node: new_node, parent, rb_link: n);
6343	rb_insert_color(new_node, &db->bb_free_root);
6344
6345	/* Now try to see the extent can be merged to left and right */
6346	node = rb_prev(new_node);
6347	if (node) {
6348	entry = rb_entry(node, struct ext4_free_data, efd_node);
6349	ext4_try_merge_freed_extent(sbi, entry, new_entry,
6350	entry_rb_root: &(db->bb_free_root));
6351	}
6352
6353	node = rb_next(new_node);
6354	if (node) {
6355	entry = rb_entry(node, struct ext4_free_data, efd_node);
6356	ext4_try_merge_freed_extent(sbi, entry, new_entry,
6357	entry_rb_root: &(db->bb_free_root));
6358	}
6359
6360	spin_lock(lock: &sbi->s_md_lock);
6361	list_add_tail(new: &new_entry->efd_list, head: &sbi->s_freed_data_list[new_entry->efd_tid & 1]);
6362	sbi->s_mb_free_pending += clusters;
6363	spin_unlock(lock: &sbi->s_md_lock);
6364	}
6365
6366	static void ext4_free_blocks_simple(struct inode *inode, ext4_fsblk_t block,
6367	unsigned long count)
6368	{
6369	struct super_block *sb = inode->i_sb;
6370	ext4_group_t group;
6371	ext4_grpblk_t blkoff;
6372
6373	ext4_get_group_no_and_offset(sb, blocknr: block, blockgrpp: &group, offsetp: &blkoff);
6374	ext4_mb_mark_context(NULL, sb, state: false, group, blkoff, len: count,
6375	EXT4_MB_BITMAP_MARKED_CHECK |
6376	EXT4_MB_SYNC_UPDATE,
6377	NULL);
6378	}
6379
6380	/**
6381	* ext4_mb_clear_bb() -- helper function for freeing blocks.
6382	* Used by ext4_free_blocks()
6383	* @handle: handle for this transaction
6384	* @inode: inode
6385	* @block: starting physical block to be freed
6386	* @count: number of blocks to be freed
6387	* @flags: flags used by ext4_free_blocks
6388	*/
6389	static void ext4_mb_clear_bb(handle_t *handle, struct inode *inode,
6390	ext4_fsblk_t block, unsigned long count,
6391	int flags)
6392	{
6393	struct super_block *sb = inode->i_sb;
6394	struct ext4_group_info *grp;
6395	unsigned int overflow;
6396	ext4_grpblk_t bit;
6397	ext4_group_t block_group;
6398	struct ext4_sb_info *sbi;
6399	struct ext4_buddy e4b;
6400	unsigned int count_clusters;
6401	int err = 0;
6402	int mark_flags = 0;
6403	ext4_grpblk_t changed;
6404
6405	sbi = EXT4_SB(sb);
6406
6407	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&
6408	!ext4_inode_block_valid(inode, start_blk: block, count)) {
6409	ext4_error(sb, "Freeing blocks in system zone - "
6410	"Block = %llu, count = %lu", block, count);
6411	/* err = 0. ext4_std_error should be a no op */
6412	goto error_out;
6413	}
6414	flags |= EXT4_FREE_BLOCKS_VALIDATED;
6415
6416	do_more:
6417	overflow = 0;
6418	ext4_get_group_no_and_offset(sb, blocknr: block, blockgrpp: &block_group, offsetp: &bit);
6419
6420	grp = ext4_get_group_info(sb, group: block_group);
6421	if (unlikely(!grp || EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))
6422	return;
6423
6424	/*
6425	* Check to see if we are freeing blocks across a group
6426	* boundary.
6427	*/
6428	if (EXT4_C2B(sbi, bit) + count > EXT4_BLOCKS_PER_GROUP(sb)) {
6429	overflow = EXT4_C2B(sbi, bit) + count -
6430	EXT4_BLOCKS_PER_GROUP(sb);
6431	count -= overflow;
6432	/* The range changed so it's no longer validated */
6433	flags &= ~EXT4_FREE_BLOCKS_VALIDATED;
6434	}
6435	count_clusters = EXT4_NUM_B2C(sbi, count);
6436	trace_ext4_mballoc_free(sb, inode, group: block_group, start: bit, len: count_clusters);
6437
6438	/* __GFP_NOFAIL: retry infinitely, ignore TIF_MEMDIE and memcg limit. */
6439	err = ext4_mb_load_buddy_gfp(sb, group: block_group, e4b: &e4b,
6440	GFP_NOFS|__GFP_NOFAIL);
6441	if (err)
6442	goto error_out;
6443
6444	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&
6445	!ext4_inode_block_valid(inode, start_blk: block, count)) {
6446	ext4_error(sb, "Freeing blocks in system zone - "
6447	"Block = %llu, count = %lu", block, count);
6448	/* err = 0. ext4_std_error should be a no op */
6449	goto error_clean;
6450	}
6451
6452	#ifdef AGGRESSIVE_CHECK
6453	mark_flags |= EXT4_MB_BITMAP_MARKED_CHECK;
6454	#endif
6455	err = ext4_mb_mark_context(handle, sb, state: false, group: block_group, blkoff: bit,
6456	len: count_clusters, flags: mark_flags, ret_changed: &changed);
6457
6458
6459	if (err && changed == 0)
6460	goto error_clean;
6461
6462	#ifdef AGGRESSIVE_CHECK
6463	BUG_ON(changed != count_clusters);
6464	#endif
6465
6466	/*
6467	* We need to make sure we don't reuse the freed block until after the
6468	* transaction is committed. We make an exception if the inode is to be
6469	* written in writeback mode since writeback mode has weak data
6470	* consistency guarantees.
6471	*/
6472	if (ext4_handle_valid(handle) &&
6473	((flags & EXT4_FREE_BLOCKS_METADATA) ||
6474	!ext4_should_writeback_data(inode))) {
6475	struct ext4_free_data *new_entry;
6476	/*
6477	* We use __GFP_NOFAIL because ext4_free_blocks() is not allowed
6478	* to fail.
6479	*/
6480	new_entry = kmem_cache_alloc(cachep: ext4_free_data_cachep,
6481	GFP_NOFS|__GFP_NOFAIL);
6482	new_entry->efd_start_cluster = bit;
6483	new_entry->efd_group = block_group;
6484	new_entry->efd_count = count_clusters;
6485	new_entry->efd_tid = handle->h_transaction->t_tid;
6486
6487	ext4_lock_group(sb, group: block_group);
6488	ext4_mb_free_metadata(handle, e4b: &e4b, new_entry);
6489	} else {
6490	if (test_opt(sb, DISCARD)) {
6491	err = ext4_issue_discard(sb, block_group, cluster: bit,
6492	count: count_clusters);
6493	/*
6494	* Ignore EOPNOTSUPP error. This is consistent with
6495	* what happens when using journal.
6496	*/
6497	if (err == -EOPNOTSUPP)
6498	err = 0;
6499	if (err)
6500	ext4_msg(sb, KERN_WARNING, "discard request in"
6501	" group:%u block:%d count:%lu failed"
6502	" with %d", block_group, bit, count,
6503	err);
6504	} else
6505	EXT4_MB_GRP_CLEAR_TRIMMED(e4b.bd_info);
6506
6507	ext4_lock_group(sb, group: block_group);
6508	mb_free_blocks(inode, e4b: &e4b, first: bit, count: count_clusters);
6509	}
6510
6511	ext4_unlock_group(sb, group: block_group);
6512
6513	/*
6514	* on a bigalloc file system, defer the s_freeclusters_counter
6515	* update to the caller (ext4_remove_space and friends) so they
6516	* can determine if a cluster freed here should be rereserved
6517	*/
6518	if (!(flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)) {
6519	if (!(flags & EXT4_FREE_BLOCKS_NO_QUOT_UPDATE))
6520	dquot_free_block(inode, EXT4_C2B(sbi, count_clusters));
6521	percpu_counter_add(fbc: &sbi->s_freeclusters_counter,
6522	amount: count_clusters);
6523	}
6524
6525	if (overflow && !err) {
6526	block += count;
6527	count = overflow;
6528	ext4_mb_unload_buddy(e4b: &e4b);
6529	/* The range changed so it's no longer validated */
6530	flags &= ~EXT4_FREE_BLOCKS_VALIDATED;
6531	goto do_more;
6532	}
6533
6534	error_clean:
6535	ext4_mb_unload_buddy(e4b: &e4b);
6536	error_out:
6537	ext4_std_error(sb, err);
6538	}
6539
6540	/**
6541	* ext4_free_blocks() -- Free given blocks and update quota
6542	* @handle: handle for this transaction
6543	* @inode: inode
6544	* @bh: optional buffer of the block to be freed
6545	* @block: starting physical block to be freed
6546	* @count: number of blocks to be freed
6547	* @flags: flags used by ext4_free_blocks
6548	*/
6549	void ext4_free_blocks(handle_t *handle, struct inode *inode,
6550	struct buffer_head *bh, ext4_fsblk_t block,
6551	unsigned long count, int flags)
6552	{
6553	struct super_block *sb = inode->i_sb;
6554	unsigned int overflow;
6555	struct ext4_sb_info *sbi;
6556
6557	sbi = EXT4_SB(sb);
6558
6559	if (bh) {
6560	if (block)
6561	BUG_ON(block != bh->b_blocknr);
6562	else
6563	block = bh->b_blocknr;
6564	}
6565
6566	if (sbi->s_mount_state & EXT4_FC_REPLAY) {
6567	ext4_free_blocks_simple(inode, block, EXT4_NUM_B2C(sbi, count));
6568	return;
6569	}
6570
6571	might_sleep();
6572
6573	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&
6574	!ext4_inode_block_valid(inode, start_blk: block, count)) {
6575	ext4_error(sb, "Freeing blocks not in datazone - "
6576	"block = %llu, count = %lu", block, count);
6577	return;
6578	}
6579	flags |= EXT4_FREE_BLOCKS_VALIDATED;
6580
6581	ext4_debug("freeing block %llu\n", block);
6582	trace_ext4_free_blocks(inode, block, count, flags);
6583
6584	if (bh && (flags & EXT4_FREE_BLOCKS_FORGET)) {
6585	BUG_ON(count > 1);
6586
6587	ext4_forget(handle, flags & EXT4_FREE_BLOCKS_METADATA,
6588	inode, bh, block);
6589	}
6590
6591	/*
6592	* If the extent to be freed does not begin on a cluster
6593	* boundary, we need to deal with partial clusters at the
6594	* beginning and end of the extent. Normally we will free
6595	* blocks at the beginning or the end unless we are explicitly
6596	* requested to avoid doing so.
6597	*/
6598	overflow = EXT4_PBLK_COFF(sbi, block);
6599	if (overflow) {
6600	if (flags & EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER) {
6601	overflow = sbi->s_cluster_ratio - overflow;
6602	block += overflow;
6603	if (count > overflow)
6604	count -= overflow;
6605	else
6606	return;
6607	} else {
6608	block -= overflow;
6609	count += overflow;
6610	}
6611	/* The range changed so it's no longer validated */
6612	flags &= ~EXT4_FREE_BLOCKS_VALIDATED;
6613	}
6614	overflow = EXT4_LBLK_COFF(sbi, count);
6615	if (overflow) {
6616	if (flags & EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER) {
6617	if (count > overflow)
6618	count -= overflow;
6619	else
6620	return;
6621	} else
6622	count += sbi->s_cluster_ratio - overflow;
6623	/* The range changed so it's no longer validated */
6624	flags &= ~EXT4_FREE_BLOCKS_VALIDATED;
6625	}
6626
6627	if (!bh && (flags & EXT4_FREE_BLOCKS_FORGET)) {
6628	int i;
6629	int is_metadata = flags & EXT4_FREE_BLOCKS_METADATA;
6630
6631	for (i = 0; i < count; i++) {
6632	cond_resched();
6633	if (is_metadata)
6634	bh = sb_find_get_block(sb: inode->i_sb, block: block + i);
6635	ext4_forget(handle, is_metadata, inode, bh, block + i);
6636	}
6637	}
6638
6639	ext4_mb_clear_bb(handle, inode, block, count, flags);
6640	}
6641
6642	/**
6643	* ext4_group_add_blocks() -- Add given blocks to an existing group
6644	* @handle: handle to this transaction
6645	* @sb: super block
6646	* @block: start physical block to add to the block group
6647	* @count: number of blocks to free
6648	*
6649	* This marks the blocks as free in the bitmap and buddy.
6650	*/
6651	int ext4_group_add_blocks(handle_t *handle, struct super_block *sb,
6652	ext4_fsblk_t block, unsigned long count)
6653	{
6654	ext4_group_t block_group;
6655	ext4_grpblk_t bit;
6656	struct ext4_sb_info *sbi = EXT4_SB(sb);
6657	struct ext4_buddy e4b;
6658	int err = 0;
6659	ext4_fsblk_t first_cluster = EXT4_B2C(sbi, block);
6660	ext4_fsblk_t last_cluster = EXT4_B2C(sbi, block + count - 1);
6661	unsigned long cluster_count = last_cluster - first_cluster + 1;
6662	ext4_grpblk_t changed;
6663
6664	ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);
6665
6666	if (cluster_count == 0)
6667	return 0;
6668
6669	ext4_get_group_no_and_offset(sb, blocknr: block, blockgrpp: &block_group, offsetp: &bit);
6670	/*
6671	* Check to see if we are freeing blocks across a group
6672	* boundary.
6673	*/
6674	if (bit + cluster_count > EXT4_CLUSTERS_PER_GROUP(sb)) {
6675	ext4_warning(sb, "too many blocks added to group %u",
6676	block_group);
6677	err = -EINVAL;
6678	goto error_out;
6679	}
6680
6681	err = ext4_mb_load_buddy(sb, group: block_group, e4b: &e4b);
6682	if (err)
6683	goto error_out;
6684
6685	if (!ext4_sb_block_valid(sb, NULL, start_blk: block, count)) {
6686	ext4_error(sb, "Adding blocks in system zones - "
6687	"Block = %llu, count = %lu",
6688	block, count);
6689	err = -EINVAL;
6690	goto error_clean;
6691	}
6692
6693	err = ext4_mb_mark_context(handle, sb, state: false, group: block_group, blkoff: bit,
6694	len: cluster_count, EXT4_MB_BITMAP_MARKED_CHECK,
6695	ret_changed: &changed);
6696	if (err && changed == 0)
6697	goto error_clean;
6698
6699	if (changed != cluster_count)
6700	ext4_error(sb, "bit already cleared in group %u", block_group);
6701
6702	ext4_lock_group(sb, group: block_group);
6703	mb_free_blocks(NULL, e4b: &e4b, first: bit, count: cluster_count);
6704	ext4_unlock_group(sb, group: block_group);
6705	percpu_counter_add(fbc: &sbi->s_freeclusters_counter,
6706	amount: changed);
6707
6708	error_clean:
6709	ext4_mb_unload_buddy(e4b: &e4b);
6710	error_out:
6711	ext4_std_error(sb, err);
6712	return err;
6713	}
6714
6715	/**
6716	* ext4_trim_extent -- function to TRIM one single free extent in the group
6717	* @sb: super block for the file system
6718	* @start: starting block of the free extent in the alloc. group
6719	* @count: number of blocks to TRIM
6720	* @e4b: ext4 buddy for the group
6721	*
6722	* Trim "count" blocks starting at "start" in the "group". To assure that no
6723	* one will allocate those blocks, mark it as used in buddy bitmap. This must
6724	* be called with under the group lock.
6725	*/
6726	static int ext4_trim_extent(struct super_block *sb,
6727	int start, int count, struct ext4_buddy *e4b)
6728	__releases(bitlock)
6729	__acquires(bitlock)
6730	{
6731	struct ext4_free_extent ex;
6732	ext4_group_t group = e4b->bd_group;
6733	int ret = 0;
6734
6735	trace_ext4_trim_extent(sb, group, start, len: count);
6736
6737	assert_spin_locked(ext4_group_lock_ptr(sb, group));
6738
6739	ex.fe_start = start;
6740	ex.fe_group = group;
6741	ex.fe_len = count;
6742
6743	/*
6744	* Mark blocks used, so no one can reuse them while
6745	* being trimmed.
6746	*/
6747	mb_mark_used(e4b, ex: &ex);
6748	ext4_unlock_group(sb, group);
6749	ret = ext4_issue_discard(sb, block_group: group, cluster: start, count);
6750	ext4_lock_group(sb, group);
6751	mb_free_blocks(NULL, e4b, first: start, count: ex.fe_len);
6752	return ret;
6753	}
6754
6755	static ext4_grpblk_t ext4_last_grp_cluster(struct super_block *sb,
6756	ext4_group_t grp)
6757	{
6758	unsigned long nr_clusters_in_group;
6759
6760	if (grp < (ext4_get_groups_count(sb) - 1))
6761	nr_clusters_in_group = EXT4_CLUSTERS_PER_GROUP(sb);
6762	else
6763	nr_clusters_in_group = (ext4_blocks_count(es: EXT4_SB(sb)->s_es) -
6764	ext4_group_first_block_no(sb, group_no: grp))
6765	>> EXT4_CLUSTER_BITS(sb);
6766
6767	return nr_clusters_in_group - 1;
6768	}
6769
6770	static bool ext4_trim_interrupted(void)
6771	{
6772	return fatal_signal_pending(current) || freezing(current);
6773	}
6774
6775	static int ext4_try_to_trim_range(struct super_block *sb,
6776	struct ext4_buddy *e4b, ext4_grpblk_t start,
6777	ext4_grpblk_t max, ext4_grpblk_t minblocks)
6778	__acquires(ext4_group_lock_ptr(sb, e4b->bd_group))
6779	__releases(ext4_group_lock_ptr(sb, e4b->bd_group))
6780	{
6781	ext4_grpblk_t next, count, free_count, last, origin_start;
6782	bool set_trimmed = false;
6783	void *bitmap;
6784
6785	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
6786	return 0;
6787
6788	last = ext4_last_grp_cluster(sb, grp: e4b->bd_group);
6789	bitmap = e4b->bd_bitmap;
6790	if (start == 0 && max >= last)
6791	set_trimmed = true;
6792	origin_start = start;
6793	start = max(e4b->bd_info->bb_first_free, start);
6794	count = 0;
6795	free_count = 0;
6796
6797	while (start <= max) {
6798	start = mb_find_next_zero_bit(addr: bitmap, max: max + 1, start);
6799	if (start > max)
6800	break;
6801
6802	next = mb_find_next_bit(addr: bitmap, max: last + 1, start);
6803	if (origin_start == 0 && next >= last)
6804	set_trimmed = true;
6805
6806	if ((next - start) >= minblocks) {
6807	int ret = ext4_trim_extent(sb, start, count: next - start, e4b);
6808
6809	if (ret && ret != -EOPNOTSUPP)
6810	return count;
6811	count += next - start;
6812	}
6813	free_count += next - start;
6814	start = next + 1;
6815
6816	if (ext4_trim_interrupted())
6817	return count;
6818
6819	if (need_resched()) {
6820	ext4_unlock_group(sb, group: e4b->bd_group);
6821	cond_resched();
6822	ext4_lock_group(sb, group: e4b->bd_group);
6823	}
6824
6825	if ((e4b->bd_info->bb_free - free_count) < minblocks)
6826	break;
6827	}
6828
6829	if (set_trimmed)
6830	EXT4_MB_GRP_SET_TRIMMED(e4b->bd_info);
6831
6832	return count;
6833	}
6834
6835	/**
6836	* ext4_trim_all_free -- function to trim all free space in alloc. group
6837	* @sb: super block for file system
6838	* @group: group to be trimmed
6839	* @start: first group block to examine
6840	* @max: last group block to examine
6841	* @minblocks: minimum extent block count
6842	*
6843	* ext4_trim_all_free walks through group's block bitmap searching for free
6844	* extents. When the free extent is found, mark it as used in group buddy
6845	* bitmap. Then issue a TRIM command on this extent and free the extent in
6846	* the group buddy bitmap.
6847	*/
6848	static ext4_grpblk_t
6849	ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
6850	ext4_grpblk_t start, ext4_grpblk_t max,
6851	ext4_grpblk_t minblocks)
6852	{
6853	struct ext4_buddy e4b;
6854	int ret;
6855
6856	trace_ext4_trim_all_free(sb, group, start, len: max);
6857
6858	ret = ext4_mb_load_buddy(sb, group, e4b: &e4b);
6859	if (ret) {
6860	ext4_warning(sb, "Error %d loading buddy information for %u",
6861	ret, group);
6862	return ret;
6863	}
6864
6865	ext4_lock_group(sb, group);
6866
6867	if (!EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) ||
6868	minblocks < EXT4_SB(sb)->s_last_trim_minblks)
6869	ret = ext4_try_to_trim_range(sb, e4b: &e4b, start, max, minblocks);
6870	else
6871	ret = 0;
6872
6873	ext4_unlock_group(sb, group);
6874	ext4_mb_unload_buddy(e4b: &e4b);
6875
6876	ext4_debug("trimmed %d blocks in the group %d\n",
6877	ret, group);
6878
6879	return ret;
6880	}
6881
6882	/**
6883	* ext4_trim_fs() -- trim ioctl handle function
6884	* @sb: superblock for filesystem
6885	* @range: fstrim_range structure
6886	*
6887	* start: First Byte to trim
6888	* len: number of Bytes to trim from start
6889	* minlen: minimum extent length in Bytes
6890	* ext4_trim_fs goes through all allocation groups containing Bytes from
6891	* start to start+len. For each such a group ext4_trim_all_free function
6892	* is invoked to trim all free space.
6893	*/
6894	int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range)
6895	{
6896	unsigned int discard_granularity = bdev_discard_granularity(bdev: sb->s_bdev);
6897	struct ext4_group_info *grp;
6898	ext4_group_t group, first_group, last_group;
6899	ext4_grpblk_t cnt = 0, first_cluster, last_cluster;
6900	uint64_t start, end, minlen, trimmed = 0;
6901	ext4_fsblk_t first_data_blk =
6902	le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
6903	ext4_fsblk_t max_blks = ext4_blocks_count(es: EXT4_SB(sb)->s_es);
6904	int ret = 0;
6905
6906	start = range->start >> sb->s_blocksize_bits;
6907	end = start + (range->len >> sb->s_blocksize_bits) - 1;
6908	minlen = EXT4_NUM_B2C(EXT4_SB(sb),
6909	range->minlen >> sb->s_blocksize_bits);
6910
6911	if (minlen > EXT4_CLUSTERS_PER_GROUP(sb) ||
6912	start >= max_blks ||
6913	range->len < sb->s_blocksize)
6914	return -EINVAL;
6915	/* No point to try to trim less than discard granularity */
6916	if (range->minlen < discard_granularity) {
6917	minlen = EXT4_NUM_B2C(EXT4_SB(sb),
6918	discard_granularity >> sb->s_blocksize_bits);
6919	if (minlen > EXT4_CLUSTERS_PER_GROUP(sb))
6920	goto out;
6921	}
6922	if (end >= max_blks - 1)
6923	end = max_blks - 1;
6924	if (end <= first_data_blk)
6925	goto out;
6926	if (start < first_data_blk)
6927	start = first_data_blk;
6928
6929	/* Determine first and last group to examine based on start and end */
6930	ext4_get_group_no_and_offset(sb, blocknr: (ext4_fsblk_t) start,
6931	blockgrpp: &first_group, offsetp: &first_cluster);
6932	ext4_get_group_no_and_offset(sb, blocknr: (ext4_fsblk_t) end,
6933	blockgrpp: &last_group, offsetp: &last_cluster);
6934
6935	/* end now represents the last cluster to discard in this group */
6936	end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
6937
6938	for (group = first_group; group <= last_group; group++) {
6939	if (ext4_trim_interrupted())
6940	break;
6941	grp = ext4_get_group_info(sb, group);
6942	if (!grp)
6943	continue;
6944	/* We only do this if the grp has never been initialized */
6945	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
6946	ret = ext4_mb_init_group(sb, group, GFP_NOFS);
6947	if (ret)
6948	break;
6949	}
6950
6951	/*
6952	* For all the groups except the last one, last cluster will
6953	* always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to
6954	* change it for the last group, note that last_cluster is
6955	* already computed earlier by ext4_get_group_no_and_offset()
6956	*/
6957	if (group == last_group)
6958	end = last_cluster;
6959	if (grp->bb_free >= minlen) {
6960	cnt = ext4_trim_all_free(sb, group, start: first_cluster,
6961	max: end, minblocks: minlen);
6962	if (cnt < 0) {
6963	ret = cnt;
6964	break;
6965	}
6966	trimmed += cnt;
6967	}
6968
6969	/*
6970	* For every group except the first one, we are sure
6971	* that the first cluster to discard will be cluster #0.
6972	*/
6973	first_cluster = 0;
6974	}
6975
6976	if (!ret)
6977	EXT4_SB(sb)->s_last_trim_minblks = minlen;
6978
6979	out:
6980	range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;
6981	return ret;
6982	}
6983
6984	/* Iterate all the free extents in the group. */
6985	int
6986	ext4_mballoc_query_range(
6987	struct super_block *sb,
6988	ext4_group_t group,
6989	ext4_grpblk_t start,
6990	ext4_grpblk_t end,
6991	ext4_mballoc_query_range_fn formatter,
6992	void *priv)
6993	{
6994	void *bitmap;
6995	ext4_grpblk_t next;
6996	struct ext4_buddy e4b;
6997	int error;
6998
6999	error = ext4_mb_load_buddy(sb, group, e4b: &e4b);
7000	if (error)
7001	return error;
7002	bitmap = e4b.bd_bitmap;
7003
7004	ext4_lock_group(sb, group);
7005
7006	start = max(e4b.bd_info->bb_first_free, start);
7007	if (end >= EXT4_CLUSTERS_PER_GROUP(sb))
7008	end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
7009
7010	while (start <= end) {
7011	start = mb_find_next_zero_bit(addr: bitmap, max: end + 1, start);
7012	if (start > end)
7013	break;
7014	next = mb_find_next_bit(addr: bitmap, max: end + 1, start);
7015
7016	ext4_unlock_group(sb, group);
7017	error = formatter(sb, group, start, next - start, priv);
7018	if (error)
7019	goto out_unload;
7020	ext4_lock_group(sb, group);
7021
7022	start = next + 1;
7023	}
7024
7025	ext4_unlock_group(sb, group);
7026	out_unload:
7027	ext4_mb_unload_buddy(e4b: &e4b);
7028
7029	return error;
7030	}
7031
7032	#ifdef CONFIG_EXT4_KUNIT_TESTS
7033	#include "mballoc-test.c"
7034	#endif
7035