~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/ext4/mballoc.c

Version: ~ [ linux-5.15-rc5 ] ~ [ linux-5.14.11 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.72 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.152 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.210 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.250 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.286 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.288 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 <trace/events/ext4.h>
 20 
 21 #ifdef CONFIG_EXT4_DEBUG
 22 ushort ext4_mballoc_debug __read_mostly;
 23 
 24 module_param_named(mballoc_debug, ext4_mballoc_debug, ushort, 0644);
 25 MODULE_PARM_DESC(mballoc_debug, "Debugging level for ext4's mballoc");
 26 #endif
 27 
 28 /*
 29  * MUSTDO:
 30  *   - test ext4_ext_search_left() and ext4_ext_search_right()
 31  *   - search for metadata in few groups
 32  *
 33  * TODO v4:
 34  *   - normalization should take into account whether file is still open
 35  *   - discard preallocations if no free space left (policy?)
 36  *   - don't normalize tails
 37  *   - quota
 38  *   - reservation for superuser
 39  *
 40  * TODO v3:
 41  *   - bitmap read-ahead (proposed by Oleg Drokin aka green)
 42  *   - track min/max extents in each group for better group selection
 43  *   - mb_mark_used() may allocate chunk right after splitting buddy
 44  *   - tree of groups sorted by number of free blocks
 45  *   - error handling
 46  */
 47 
 48 /*
 49  * The allocation request involve request for multiple number of blocks
 50  * near to the goal(block) value specified.
 51  *
 52  * During initialization phase of the allocator we decide to use the
 53  * group preallocation or inode preallocation depending on the size of
 54  * the file. The size of the file could be the resulting file size we
 55  * would have after allocation, or the current file size, which ever
 56  * is larger. If the size is less than sbi->s_mb_stream_request we
 57  * select to use the group preallocation. The default value of
 58  * s_mb_stream_request is 16 blocks. This can also be tuned via
 59  * /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in
 60  * terms of number of blocks.
 61  *
 62  * The main motivation for having small file use group preallocation is to
 63  * ensure that we have small files closer together on the disk.
 64  *
 65  * First stage the allocator looks at the inode prealloc list,
 66  * ext4_inode_info->i_prealloc_list, which contains list of prealloc
 67  * spaces for this particular inode. The inode prealloc space is
 68  * represented as:
 69  *
 70  * pa_lstart -> the logical start block for this prealloc space
 71  * pa_pstart -> the physical start block for this prealloc space
 72  * pa_len    -> length for this prealloc space (in clusters)
 73  * pa_free   ->  free space available in this prealloc space (in clusters)
 74  *
 75  * The inode preallocation space is used looking at the _logical_ start
 76  * block. If only the logical file block falls within the range of prealloc
 77  * space we will consume the particular prealloc space. This makes sure that
 78  * we have contiguous physical blocks representing the file blocks
 79  *
 80  * The important thing to be noted in case of inode prealloc space is that
 81  * we don't modify the values associated to inode prealloc space except
 82  * pa_free.
 83  *
 84  * If we are not able to find blocks in the inode prealloc space and if we
 85  * have the group allocation flag set then we look at the locality group
 86  * prealloc space. These are per CPU prealloc list represented as
 87  *
 88  * ext4_sb_info.s_locality_groups[smp_processor_id()]
 89  *
 90  * The reason for having a per cpu locality group is to reduce the contention
 91  * between CPUs. It is possible to get scheduled at this point.
 92  *
 93  * The locality group prealloc space is used looking at whether we have
 94  * enough free space (pa_free) within the prealloc space.
 95  *
 96  * If we can't allocate blocks via inode prealloc or/and locality group
 97  * prealloc then we look at the buddy cache. The buddy cache is represented
 98  * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
 99  * mapped to the buddy and bitmap information regarding different
100  * groups. The buddy information is attached to buddy cache inode so that
101  * we can access them through the page cache. The information regarding
102  * each group is loaded via ext4_mb_load_buddy.  The information involve
103  * block bitmap and buddy information. The information are stored in the
104  * inode as:
105  *
106  *  {                        page                        }
107  *  [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
108  *
109  *
110  * one block each for bitmap and buddy information.  So for each group we
111  * take up 2 blocks. A page can contain blocks_per_page (PAGE_SIZE /
112  * blocksize) blocks.  So it can have information regarding groups_per_page
113  * which is blocks_per_page/2
114  *
115  * The buddy cache inode is not stored on disk. The inode is thrown
116  * away when the filesystem is unmounted.
117  *
118  * We look for count number of blocks in the buddy cache. If we were able
119  * to locate that many free blocks we return with additional information
120  * regarding rest of the contiguous physical block available
121  *
122  * Before allocating blocks via buddy cache we normalize the request
123  * blocks. This ensure we ask for more blocks that we needed. The extra
124  * blocks that we get after allocation is added to the respective prealloc
125  * list. In case of inode preallocation we follow a list of heuristics
126  * based on file size. This can be found in ext4_mb_normalize_request. If
127  * we are doing a group prealloc we try to normalize the request to
128  * sbi->s_mb_group_prealloc.  The default value of s_mb_group_prealloc is
129  * dependent on the cluster size; for non-bigalloc file systems, it is
130  * 512 blocks. This can be tuned via
131  * /sys/fs/ext4/<partition>/mb_group_prealloc. The value is represented in
132  * terms of number of blocks. If we have mounted the file system with -O
133  * stripe=<value> option the group prealloc request is normalized to the
134  * the smallest multiple of the stripe value (sbi->s_stripe) which is
135  * greater than the default mb_group_prealloc.
136  *
137  * The regular allocator (using the buddy cache) supports a few tunables.
138  *
139  * /sys/fs/ext4/<partition>/mb_min_to_scan
140  * /sys/fs/ext4/<partition>/mb_max_to_scan
141  * /sys/fs/ext4/<partition>/mb_order2_req
142  *
143  * The regular allocator uses buddy scan only if the request len is power of
144  * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
145  * value of s_mb_order2_reqs can be tuned via
146  * /sys/fs/ext4/<partition>/mb_order2_req.  If the request len is equal to
147  * stripe size (sbi->s_stripe), we try to search for contiguous block in
148  * stripe size. This should result in better allocation on RAID setups. If
149  * not, we search in the specific group using bitmap for best extents. The
150  * tunable min_to_scan and max_to_scan control the behaviour here.
151  * min_to_scan indicate how long the mballoc __must__ look for a best
152  * extent and max_to_scan indicates how long the mballoc __can__ look for a
153  * best extent in the found extents. Searching for the blocks starts with
154  * the group specified as the goal value in allocation context via
155  * ac_g_ex. Each group is first checked based on the criteria whether it
156  * can be used for allocation. ext4_mb_good_group explains how the groups are
157  * checked.
158  *
159  * Both the prealloc space are getting populated as above. So for the first
160  * request we will hit the buddy cache which will result in this prealloc
161  * space getting filled. The prealloc space is then later used for the
162  * subsequent request.
163  */
164 
165 /*
166  * mballoc operates on the following data:
167  *  - on-disk bitmap
168  *  - in-core buddy (actually includes buddy and bitmap)
169  *  - preallocation descriptors (PAs)
170  *
171  * there are two types of preallocations:
172  *  - inode
173  *    assiged to specific inode and can be used for this inode only.
174  *    it describes part of inode's space preallocated to specific
175  *    physical blocks. any block from that preallocated can be used
176  *    independent. the descriptor just tracks number of blocks left
177  *    unused. so, before taking some block from descriptor, one must
178  *    make sure corresponded logical block isn't allocated yet. this
179  *    also means that freeing any block within descriptor's range
180  *    must discard all preallocated blocks.
181  *  - locality group
182  *    assigned to specific locality group which does not translate to
183  *    permanent set of inodes: inode can join and leave group. space
184  *    from this type of preallocation can be used for any inode. thus
185  *    it's consumed from the beginning to the end.
186  *
187  * relation between them can be expressed as:
188  *    in-core buddy = on-disk bitmap + preallocation descriptors
189  *
190  * this mean blocks mballoc considers used are:
191  *  - allocated blocks (persistent)
192  *  - preallocated blocks (non-persistent)
193  *
194  * consistency in mballoc world means that at any time a block is either
195  * free or used in ALL structures. notice: "any time" should not be read
196  * literally -- time is discrete and delimited by locks.
197  *
198  *  to keep it simple, we don't use block numbers, instead we count number of
199  *  blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
200  *
201  * all operations can be expressed as:
202  *  - init buddy:                       buddy = on-disk + PAs
203  *  - new PA:                           buddy += N; PA = N
204  *  - use inode PA:                     on-disk += N; PA -= N
205  *  - discard inode PA                  buddy -= on-disk - PA; PA = 0
206  *  - use locality group PA             on-disk += N; PA -= N
207  *  - discard locality group PA         buddy -= PA; PA = 0
208  *  note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
209  *        is used in real operation because we can't know actual used
210  *        bits from PA, only from on-disk bitmap
211  *
212  * if we follow this strict logic, then all operations above should be atomic.
213  * given some of them can block, we'd have to use something like semaphores
214  * killing performance on high-end SMP hardware. let's try to relax it using
215  * the following knowledge:
216  *  1) if buddy is referenced, it's already initialized
217  *  2) while block is used in buddy and the buddy is referenced,
218  *     nobody can re-allocate that block
219  *  3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
220  *     bit set and PA claims same block, it's OK. IOW, one can set bit in
221  *     on-disk bitmap if buddy has same bit set or/and PA covers corresponded
222  *     block
223  *
224  * so, now we're building a concurrency table:
225  *  - init buddy vs.
226  *    - new PA
227  *      blocks for PA are allocated in the buddy, buddy must be referenced
228  *      until PA is linked to allocation group to avoid concurrent buddy init
229  *    - use inode PA
230  *      we need to make sure that either on-disk bitmap or PA has uptodate data
231  *      given (3) we care that PA-=N operation doesn't interfere with init
232  *    - discard inode PA
233  *      the simplest way would be to have buddy initialized by the discard
234  *    - use locality group PA
235  *      again PA-=N must be serialized with init
236  *    - discard locality group PA
237  *      the simplest way would be to have buddy initialized by the discard
238  *  - new PA vs.
239  *    - use inode PA
240  *      i_data_sem serializes them
241  *    - discard inode PA
242  *      discard process must wait until PA isn't used by another process
243  *    - use locality group PA
244  *      some mutex should serialize them
245  *    - discard locality group PA
246  *      discard process must wait until PA isn't used by another process
247  *  - use inode PA
248  *    - use inode PA
249  *      i_data_sem or another mutex should serializes them
250  *    - discard inode PA
251  *      discard process must wait until PA isn't used by another process
252  *    - use locality group PA
253  *      nothing wrong here -- they're different PAs covering different blocks
254  *    - discard locality group PA
255  *      discard process must wait until PA isn't used by another process
256  *
257  * now we're ready to make few consequences:
258  *  - PA is referenced and while it is no discard is possible
259  *  - PA is referenced until block isn't marked in on-disk bitmap
260  *  - PA changes only after on-disk bitmap
261  *  - discard must not compete with init. either init is done before
262  *    any discard or they're serialized somehow
263  *  - buddy init as sum of on-disk bitmap and PAs is done atomically
264  *
265  * a special case when we've used PA to emptiness. no need to modify buddy
266  * in this case, but we should care about concurrent init
267  *
268  */
269 
270  /*
271  * Logic in few words:
272  *
273  *  - allocation:
274  *    load group
275  *    find blocks
276  *    mark bits in on-disk bitmap
277  *    release group
278  *
279  *  - use preallocation:
280  *    find proper PA (per-inode or group)
281  *    load group
282  *    mark bits in on-disk bitmap
283  *    release group
284  *    release PA
285  *
286  *  - free:
287  *    load group
288  *    mark bits in on-disk bitmap
289  *    release group
290  *
291  *  - discard preallocations in group:
292  *    mark PAs deleted
293  *    move them onto local list
294  *    load on-disk bitmap
295  *    load group
296  *    remove PA from object (inode or locality group)
297  *    mark free blocks in-core
298  *
299  *  - discard inode's preallocations:
300  */
301 
302 /*
303  * Locking rules
304  *
305  * Locks:
306  *  - bitlock on a group        (group)
307  *  - object (inode/locality)   (object)
308  *  - per-pa lock               (pa)
309  *
310  * Paths:
311  *  - new pa
312  *    object
313  *    group
314  *
315  *  - find and use pa:
316  *    pa
317  *
318  *  - release consumed pa:
319  *    pa
320  *    group
321  *    object
322  *
323  *  - generate in-core bitmap:
324  *    group
325  *        pa
326  *
327  *  - discard all for given object (inode, locality group):
328  *    object
329  *        pa
330  *    group
331  *
332  *  - discard all for given group:
333  *    group
334  *        pa
335  *    group
336  *        object
337  *
338  */
339 static struct kmem_cache *ext4_pspace_cachep;
340 static struct kmem_cache *ext4_ac_cachep;
341 static struct kmem_cache *ext4_free_data_cachep;
342 
343 /* We create slab caches for groupinfo data structures based on the
344  * superblock block size.  There will be one per mounted filesystem for
345  * each unique s_blocksize_bits */
346 #define NR_GRPINFO_CACHES 8
347 static struct kmem_cache *ext4_groupinfo_caches[NR_GRPINFO_CACHES];
348 
349 static const char * const ext4_groupinfo_slab_names[NR_GRPINFO_CACHES] = {
350         "ext4_groupinfo_1k", "ext4_groupinfo_2k", "ext4_groupinfo_4k",
351         "ext4_groupinfo_8k", "ext4_groupinfo_16k", "ext4_groupinfo_32k",
352         "ext4_groupinfo_64k", "ext4_groupinfo_128k"
353 };
354 
355 static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
356                                         ext4_group_t group);
357 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
358                                                 ext4_group_t group);
359 
360 static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
361 {
362 #if BITS_PER_LONG == 64
363         *bit += ((unsigned long) addr & 7UL) << 3;
364         addr = (void *) ((unsigned long) addr & ~7UL);
365 #elif BITS_PER_LONG == 32
366         *bit += ((unsigned long) addr & 3UL) << 3;
367         addr = (void *) ((unsigned long) addr & ~3UL);
368 #else
369 #error "how many bits you are?!"
370 #endif
371         return addr;
372 }
373 
374 static inline int mb_test_bit(int bit, void *addr)
375 {
376         /*
377          * ext4_test_bit on architecture like powerpc
378          * needs unsigned long aligned address
379          */
380         addr = mb_correct_addr_and_bit(&bit, addr);
381         return ext4_test_bit(bit, addr);
382 }
383 
384 static inline void mb_set_bit(int bit, void *addr)
385 {
386         addr = mb_correct_addr_and_bit(&bit, addr);
387         ext4_set_bit(bit, addr);
388 }
389 
390 static inline void mb_clear_bit(int bit, void *addr)
391 {
392         addr = mb_correct_addr_and_bit(&bit, addr);
393         ext4_clear_bit(bit, addr);
394 }
395 
396 static inline int mb_test_and_clear_bit(int bit, void *addr)
397 {
398         addr = mb_correct_addr_and_bit(&bit, addr);
399         return ext4_test_and_clear_bit(bit, addr);
400 }
401 
402 static inline int mb_find_next_zero_bit(void *addr, int max, int start)
403 {
404         int fix = 0, ret, tmpmax;
405         addr = mb_correct_addr_and_bit(&fix, addr);
406         tmpmax = max + fix;
407         start += fix;
408 
409         ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
410         if (ret > max)
411                 return max;
412         return ret;
413 }
414 
415 static inline int mb_find_next_bit(void *addr, int max, int start)
416 {
417         int fix = 0, ret, tmpmax;
418         addr = mb_correct_addr_and_bit(&fix, addr);
419         tmpmax = max + fix;
420         start += fix;
421 
422         ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
423         if (ret > max)
424                 return max;
425         return ret;
426 }
427 
428 static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
429 {
430         char *bb;
431 
432         BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
433         BUG_ON(max == NULL);
434 
435         if (order > e4b->bd_blkbits + 1) {
436                 *max = 0;
437                 return NULL;
438         }
439 
440         /* at order 0 we see each particular block */
441         if (order == 0) {
442                 *max = 1 << (e4b->bd_blkbits + 3);
443                 return e4b->bd_bitmap;
444         }
445 
446         bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
447         *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];
448 
449         return bb;
450 }
451 
452 #ifdef DOUBLE_CHECK
453 static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,
454                            int first, int count)
455 {
456         int i;
457         struct super_block *sb = e4b->bd_sb;
458 
459         if (unlikely(e4b->bd_info->bb_bitmap == NULL))
460                 return;
461         assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
462         for (i = 0; i < count; i++) {
463                 if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
464                         ext4_fsblk_t blocknr;
465 
466                         blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
467                         blocknr += EXT4_C2B(EXT4_SB(sb), first + i);
468                         ext4_grp_locked_error(sb, e4b->bd_group,
469                                               inode ? inode->i_ino : 0,
470                                               blocknr,
471                                               "freeing block already freed "
472                                               "(bit %u)",
473                                               first + i);
474                         ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
475                                         EXT4_GROUP_INFO_BBITMAP_CORRUPT);
476                 }
477                 mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
478         }
479 }
480 
481 static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)
482 {
483         int i;
484 
485         if (unlikely(e4b->bd_info->bb_bitmap == NULL))
486                 return;
487         assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
488         for (i = 0; i < count; i++) {
489                 BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
490                 mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
491         }
492 }
493 
494 static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
495 {
496         if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
497                 unsigned char *b1, *b2;
498                 int i;
499                 b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
500                 b2 = (unsigned char *) bitmap;
501                 for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
502                         if (b1[i] != b2[i]) {
503                                 ext4_msg(e4b->bd_sb, KERN_ERR,
504                                          "corruption in group %u "
505                                          "at byte %u(%u): %x in copy != %x "
506                                          "on disk/prealloc",
507                                          e4b->bd_group, i, i * 8, b1[i], b2[i]);
508                                 BUG();
509                         }
510                 }
511         }
512 }
513 
514 #else
515 static inline void mb_free_blocks_double(struct inode *inode,
516                                 struct ext4_buddy *e4b, int first, int count)
517 {
518         return;
519 }
520 static inline void mb_mark_used_double(struct ext4_buddy *e4b,
521                                                 int first, int count)
522 {
523         return;
524 }
525 static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
526 {
527         return;
528 }
529 #endif
530 
531 #ifdef AGGRESSIVE_CHECK
532 
533 #define MB_CHECK_ASSERT(assert)                                         \
534 do {                                                                    \
535         if (!(assert)) {                                                \
536                 printk(KERN_EMERG                                       \
537                         "Assertion failure in %s() at %s:%d: \"%s\"\n", \
538                         function, file, line, # assert);                \
539                 BUG();                                                  \
540         }                                                               \
541 } while (0)
542 
543 static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
544                                 const char *function, int line)
545 {
546         struct super_block *sb = e4b->bd_sb;
547         int order = e4b->bd_blkbits + 1;
548         int max;
549         int max2;
550         int i;
551         int j;
552         int k;
553         int count;
554         struct ext4_group_info *grp;
555         int fragments = 0;
556         int fstart;
557         struct list_head *cur;
558         void *buddy;
559         void *buddy2;
560 
561         {
562                 static int mb_check_counter;
563                 if (mb_check_counter++ % 100 != 0)
564                         return 0;
565         }
566 
567         while (order > 1) {
568                 buddy = mb_find_buddy(e4b, order, &max);
569                 MB_CHECK_ASSERT(buddy);
570                 buddy2 = mb_find_buddy(e4b, order - 1, &max2);
571                 MB_CHECK_ASSERT(buddy2);
572                 MB_CHECK_ASSERT(buddy != buddy2);
573                 MB_CHECK_ASSERT(max * 2 == max2);
574 
575                 count = 0;
576                 for (i = 0; i < max; i++) {
577 
578                         if (mb_test_bit(i, buddy)) {
579                                 /* only single bit in buddy2 may be 1 */
580                                 if (!mb_test_bit(i << 1, buddy2)) {
581                                         MB_CHECK_ASSERT(
582                                                 mb_test_bit((i<<1)+1, buddy2));
583                                 } else if (!mb_test_bit((i << 1) + 1, buddy2)) {
584                                         MB_CHECK_ASSERT(
585                                                 mb_test_bit(i << 1, buddy2));
586                                 }
587                                 continue;
588                         }
589 
590                         /* both bits in buddy2 must be 1 */
591                         MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
592                         MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
593 
594                         for (j = 0; j < (1 << order); j++) {
595                                 k = (i * (1 << order)) + j;
596                                 MB_CHECK_ASSERT(
597                                         !mb_test_bit(k, e4b->bd_bitmap));
598                         }
599                         count++;
600                 }
601                 MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
602                 order--;
603         }
604 
605         fstart = -1;
606         buddy = mb_find_buddy(e4b, 0, &max);
607         for (i = 0; i < max; i++) {
608                 if (!mb_test_bit(i, buddy)) {
609                         MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
610                         if (fstart == -1) {
611                                 fragments++;
612                                 fstart = i;
613                         }
614                         continue;
615                 }
616                 fstart = -1;
617                 /* check used bits only */
618                 for (j = 0; j < e4b->bd_blkbits + 1; j++) {
619                         buddy2 = mb_find_buddy(e4b, j, &max2);
620                         k = i >> j;
621                         MB_CHECK_ASSERT(k < max2);
622                         MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
623                 }
624         }
625         MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
626         MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);
627 
628         grp = ext4_get_group_info(sb, e4b->bd_group);
629         list_for_each(cur, &grp->bb_prealloc_list) {
630                 ext4_group_t groupnr;
631                 struct ext4_prealloc_space *pa;
632                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
633                 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
634                 MB_CHECK_ASSERT(groupnr == e4b->bd_group);
635                 for (i = 0; i < pa->pa_len; i++)
636                         MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
637         }
638         return 0;
639 }
640 #undef MB_CHECK_ASSERT
641 #define mb_check_buddy(e4b) __mb_check_buddy(e4b,       \
642                                         __FILE__, __func__, __LINE__)
643 #else
644 #define mb_check_buddy(e4b)
645 #endif
646 
647 /*
648  * Divide blocks started from @first with length @len into
649  * smaller chunks with power of 2 blocks.
650  * Clear the bits in bitmap which the blocks of the chunk(s) covered,
651  * then increase bb_counters[] for corresponded chunk size.
652  */
653 static void ext4_mb_mark_free_simple(struct super_block *sb,
654                                 void *buddy, ext4_grpblk_t first, ext4_grpblk_t len,
655                                         struct ext4_group_info *grp)
656 {
657         struct ext4_sb_info *sbi = EXT4_SB(sb);
658         ext4_grpblk_t min;
659         ext4_grpblk_t max;
660         ext4_grpblk_t chunk;
661         unsigned int border;
662 
663         BUG_ON(len > EXT4_CLUSTERS_PER_GROUP(sb));
664 
665         border = 2 << sb->s_blocksize_bits;
666 
667         while (len > 0) {
668                 /* find how many blocks can be covered since this position */
669                 max = ffs(first | border) - 1;
670 
671                 /* find how many blocks of power 2 we need to mark */
672                 min = fls(len) - 1;
673 
674                 if (max < min)
675                         min = max;
676                 chunk = 1 << min;
677 
678                 /* mark multiblock chunks only */
679                 grp->bb_counters[min]++;
680                 if (min > 0)
681                         mb_clear_bit(first >> min,
682                                      buddy + sbi->s_mb_offsets[min]);
683 
684                 len -= chunk;
685                 first += chunk;
686         }
687 }
688 
689 /*
690  * Cache the order of the largest free extent we have available in this block
691  * group.
692  */
693 static void
694 mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
695 {
696         int i;
697         int bits;
698 
699         grp->bb_largest_free_order = -1; /* uninit */
700 
701         bits = sb->s_blocksize_bits + 1;
702         for (i = bits; i >= 0; i--) {
703                 if (grp->bb_counters[i] > 0) {
704                         grp->bb_largest_free_order = i;
705                         break;
706                 }
707         }
708 }
709 
710 static noinline_for_stack
711 void ext4_mb_generate_buddy(struct super_block *sb,
712                                 void *buddy, void *bitmap, ext4_group_t group)
713 {
714         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
715         struct ext4_sb_info *sbi = EXT4_SB(sb);
716         ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
717         ext4_grpblk_t i = 0;
718         ext4_grpblk_t first;
719         ext4_grpblk_t len;
720         unsigned free = 0;
721         unsigned fragments = 0;
722         unsigned long long period = get_cycles();
723 
724         /* initialize buddy from bitmap which is aggregation
725          * of on-disk bitmap and preallocations */
726         i = mb_find_next_zero_bit(bitmap, max, 0);
727         grp->bb_first_free = i;
728         while (i < max) {
729                 fragments++;
730                 first = i;
731                 i = mb_find_next_bit(bitmap, max, i);
732                 len = i - first;
733                 free += len;
734                 if (len > 1)
735                         ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
736                 else
737                         grp->bb_counters[0]++;
738                 if (i < max)
739                         i = mb_find_next_zero_bit(bitmap, max, i);
740         }
741         grp->bb_fragments = fragments;
742 
743         if (free != grp->bb_free) {
744                 ext4_grp_locked_error(sb, group, 0, 0,
745                                       "block bitmap and bg descriptor "
746                                       "inconsistent: %u vs %u free clusters",
747                                       free, grp->bb_free);
748                 /*
749                  * If we intend to continue, we consider group descriptor
750                  * corrupt and update bb_free using bitmap value
751                  */
752                 grp->bb_free = free;
753                 ext4_mark_group_bitmap_corrupted(sb, group,
754                                         EXT4_GROUP_INFO_BBITMAP_CORRUPT);
755         }
756         mb_set_largest_free_order(sb, grp);
757 
758         clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));
759 
760         period = get_cycles() - period;
761         spin_lock(&sbi->s_bal_lock);
762         sbi->s_mb_buddies_generated++;
763         sbi->s_mb_generation_time += period;
764         spin_unlock(&sbi->s_bal_lock);
765 }
766 
767 static void mb_regenerate_buddy(struct ext4_buddy *e4b)
768 {
769         int count;
770         int order = 1;
771         void *buddy;
772 
773         while ((buddy = mb_find_buddy(e4b, order++, &count))) {
774                 ext4_set_bits(buddy, 0, count);
775         }
776         e4b->bd_info->bb_fragments = 0;
777         memset(e4b->bd_info->bb_counters, 0,
778                 sizeof(*e4b->bd_info->bb_counters) *
779                 (e4b->bd_sb->s_blocksize_bits + 2));
780 
781         ext4_mb_generate_buddy(e4b->bd_sb, e4b->bd_buddy,
782                 e4b->bd_bitmap, e4b->bd_group);
783 }
784 
785 /* The buddy information is attached the buddy cache inode
786  * for convenience. The information regarding each group
787  * is loaded via ext4_mb_load_buddy. The information involve
788  * block bitmap and buddy information. The information are
789  * stored in the inode as
790  *
791  * {                        page                        }
792  * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
793  *
794  *
795  * one block each for bitmap and buddy information.
796  * So for each group we take up 2 blocks. A page can
797  * contain blocks_per_page (PAGE_SIZE / blocksize)  blocks.
798  * So it can have information regarding groups_per_page which
799  * is blocks_per_page/2
800  *
801  * Locking note:  This routine takes the block group lock of all groups
802  * for this page; do not hold this lock when calling this routine!
803  */
804 
805 static int ext4_mb_init_cache(struct page *page, char *incore, gfp_t gfp)
806 {
807         ext4_group_t ngroups;
808         int blocksize;
809         int blocks_per_page;
810         int groups_per_page;
811         int err = 0;
812         int i;
813         ext4_group_t first_group, group;
814         int first_block;
815         struct super_block *sb;
816         struct buffer_head *bhs;
817         struct buffer_head **bh = NULL;
818         struct inode *inode;
819         char *data;
820         char *bitmap;
821         struct ext4_group_info *grinfo;
822 
823         mb_debug(1, "init page %lu\n", page->index);
824 
825         inode = page->mapping->host;
826         sb = inode->i_sb;
827         ngroups = ext4_get_groups_count(sb);
828         blocksize = i_blocksize(inode);
829         blocks_per_page = PAGE_SIZE / blocksize;
830 
831         groups_per_page = blocks_per_page >> 1;
832         if (groups_per_page == 0)
833                 groups_per_page = 1;
834 
835         /* allocate buffer_heads to read bitmaps */
836         if (groups_per_page > 1) {
837                 i = sizeof(struct buffer_head *) * groups_per_page;
838                 bh = kzalloc(i, gfp);
839                 if (bh == NULL) {
840                         err = -ENOMEM;
841                         goto out;
842                 }
843         } else
844                 bh = &bhs;
845 
846         first_group = page->index * blocks_per_page / 2;
847 
848         /* read all groups the page covers into the cache */
849         for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
850                 if (group >= ngroups)
851                         break;
852 
853                 grinfo = ext4_get_group_info(sb, group);
854                 /*
855                  * If page is uptodate then we came here after online resize
856                  * which added some new uninitialized group info structs, so
857                  * we must skip all initialized uptodate buddies on the page,
858                  * which may be currently in use by an allocating task.
859                  */
860                 if (PageUptodate(page) && !EXT4_MB_GRP_NEED_INIT(grinfo)) {
861                         bh[i] = NULL;
862                         continue;
863                 }
864                 bh[i] = ext4_read_block_bitmap_nowait(sb, group);
865                 if (IS_ERR(bh[i])) {
866                         err = PTR_ERR(bh[i]);
867                         bh[i] = NULL;
868                         goto out;
869                 }
870                 mb_debug(1, "read bitmap for group %u\n", group);
871         }
872 
873         /* wait for I/O completion */
874         for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
875                 int err2;
876 
877                 if (!bh[i])
878                         continue;
879                 err2 = ext4_wait_block_bitmap(sb, group, bh[i]);
880                 if (!err)
881                         err = err2;
882         }
883 
884         first_block = page->index * blocks_per_page;
885         for (i = 0; i < blocks_per_page; i++) {
886                 group = (first_block + i) >> 1;
887                 if (group >= ngroups)
888                         break;
889 
890                 if (!bh[group - first_group])
891                         /* skip initialized uptodate buddy */
892                         continue;
893 
894                 if (!buffer_verified(bh[group - first_group]))
895                         /* Skip faulty bitmaps */
896                         continue;
897                 err = 0;
898 
899                 /*
900                  * data carry information regarding this
901                  * particular group in the format specified
902                  * above
903                  *
904                  */
905                 data = page_address(page) + (i * blocksize);
906                 bitmap = bh[group - first_group]->b_data;
907 
908                 /*
909                  * We place the buddy block and bitmap block
910                  * close together
911                  */
912                 if ((first_block + i) & 1) {
913                         /* this is block of buddy */
914                         BUG_ON(incore == NULL);
915                         mb_debug(1, "put buddy for group %u in page %lu/%x\n",
916                                 group, page->index, i * blocksize);
917                         trace_ext4_mb_buddy_bitmap_load(sb, group);
918                         grinfo = ext4_get_group_info(sb, group);
919                         grinfo->bb_fragments = 0;
920                         memset(grinfo->bb_counters, 0,
921                                sizeof(*grinfo->bb_counters) *
922                                 (sb->s_blocksize_bits+2));
923                         /*
924                          * incore got set to the group block bitmap below
925                          */
926                         ext4_lock_group(sb, group);
927                         /* init the buddy */
928                         memset(data, 0xff, blocksize);
929                         ext4_mb_generate_buddy(sb, data, incore, group);
930                         ext4_unlock_group(sb, group);
931                         incore = NULL;
932                 } else {
933                         /* this is block of bitmap */
934                         BUG_ON(incore != NULL);
935                         mb_debug(1, "put bitmap for group %u in page %lu/%x\n",
936                                 group, page->index, i * blocksize);
937                         trace_ext4_mb_bitmap_load(sb, group);
938 
939                         /* see comments in ext4_mb_put_pa() */
940                         ext4_lock_group(sb, group);
941                         memcpy(data, bitmap, blocksize);
942 
943                         /* mark all preallocated blks used in in-core bitmap */
944                         ext4_mb_generate_from_pa(sb, data, group);
945                         ext4_mb_generate_from_freelist(sb, data, group);
946                         ext4_unlock_group(sb, group);
947 
948                         /* set incore so that the buddy information can be
949                          * generated using this
950                          */
951                         incore = data;
952                 }
953         }
954         SetPageUptodate(page);
955 
956 out:
957         if (bh) {
958                 for (i = 0; i < groups_per_page; i++)
959                         brelse(bh[i]);
960                 if (bh != &bhs)
961                         kfree(bh);
962         }
963         return err;
964 }
965 
966 /*
967  * Lock the buddy and bitmap pages. This make sure other parallel init_group
968  * on the same buddy page doesn't happen whild holding the buddy page lock.
969  * Return locked buddy and bitmap pages on e4b struct. If buddy and bitmap
970  * are on the same page e4b->bd_buddy_page is NULL and return value is 0.
971  */
972 static int ext4_mb_get_buddy_page_lock(struct super_block *sb,
973                 ext4_group_t group, struct ext4_buddy *e4b, gfp_t gfp)
974 {
975         struct inode *inode = EXT4_SB(sb)->s_buddy_cache;
976         int block, pnum, poff;
977         int blocks_per_page;
978         struct page *page;
979 
980         e4b->bd_buddy_page = NULL;
981         e4b->bd_bitmap_page = NULL;
982 
983         blocks_per_page = PAGE_SIZE / sb->s_blocksize;
984         /*
985          * the buddy cache inode stores the block bitmap
986          * and buddy information in consecutive blocks.
987          * So for each group we need two blocks.
988          */
989         block = group * 2;
990         pnum = block / blocks_per_page;
991         poff = block % blocks_per_page;
992         page = find_or_create_page(inode->i_mapping, pnum, gfp);
993         if (!page)
994                 return -ENOMEM;
995         BUG_ON(page->mapping != inode->i_mapping);
996         e4b->bd_bitmap_page = page;
997         e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
998 
999         if (blocks_per_page >= 2) {
1000                 /* buddy and bitmap are on the same page */
1001                 return 0;
1002         }
1003 
1004         block++;
1005         pnum = block / blocks_per_page;
1006         page = find_or_create_page(inode->i_mapping, pnum, gfp);
1007         if (!page)
1008                 return -ENOMEM;
1009         BUG_ON(page->mapping != inode->i_mapping);
1010         e4b->bd_buddy_page = page;
1011         return 0;
1012 }
1013 
1014 static void ext4_mb_put_buddy_page_lock(struct ext4_buddy *e4b)
1015 {
1016         if (e4b->bd_bitmap_page) {
1017                 unlock_page(e4b->bd_bitmap_page);
1018                 put_page(e4b->bd_bitmap_page);
1019         }
1020         if (e4b->bd_buddy_page) {
1021                 unlock_page(e4b->bd_buddy_page);
1022                 put_page(e4b->bd_buddy_page);
1023         }
1024 }
1025 
1026 /*
1027  * Locking note:  This routine calls ext4_mb_init_cache(), which takes the
1028  * block group lock of all groups for this page; do not hold the BG lock when
1029  * calling this routine!
1030  */
1031 static noinline_for_stack
1032 int ext4_mb_init_group(struct super_block *sb, ext4_group_t group, gfp_t gfp)
1033 {
1034 
1035         struct ext4_group_info *this_grp;
1036         struct ext4_buddy e4b;
1037         struct page *page;
1038         int ret = 0;
1039 
1040         might_sleep();
1041         mb_debug(1, "init group %u\n", group);
1042         this_grp = ext4_get_group_info(sb, group);
1043         /*
1044          * This ensures that we don't reinit the buddy cache
1045          * page which map to the group from which we are already
1046          * allocating. If we are looking at the buddy cache we would
1047          * have taken a reference using ext4_mb_load_buddy and that
1048          * would have pinned buddy page to page cache.
1049          * The call to ext4_mb_get_buddy_page_lock will mark the
1050          * page accessed.
1051          */
1052         ret = ext4_mb_get_buddy_page_lock(sb, group, &e4b, gfp);
1053         if (ret || !EXT4_MB_GRP_NEED_INIT(this_grp)) {
1054                 /*
1055                  * somebody initialized the group
1056                  * return without doing anything
1057                  */
1058                 goto err;
1059         }
1060 
1061         page = e4b.bd_bitmap_page;
1062         ret = ext4_mb_init_cache(page, NULL, gfp);
1063         if (ret)
1064                 goto err;
1065         if (!PageUptodate(page)) {
1066                 ret = -EIO;
1067                 goto err;
1068         }
1069 
1070         if (e4b.bd_buddy_page == NULL) {
1071                 /*
1072                  * If both the bitmap and buddy are in
1073                  * the same page we don't need to force
1074                  * init the buddy
1075                  */
1076                 ret = 0;
1077                 goto err;
1078         }
1079         /* init buddy cache */
1080         page = e4b.bd_buddy_page;
1081         ret = ext4_mb_init_cache(page, e4b.bd_bitmap, gfp);
1082         if (ret)
1083                 goto err;
1084         if (!PageUptodate(page)) {
1085                 ret = -EIO;
1086                 goto err;
1087         }
1088 err:
1089         ext4_mb_put_buddy_page_lock(&e4b);
1090         return ret;
1091 }
1092 
1093 /*
1094  * Locking note:  This routine calls ext4_mb_init_cache(), which takes the
1095  * block group lock of all groups for this page; do not hold the BG lock when
1096  * calling this routine!
1097  */
1098 static noinline_for_stack int
1099 ext4_mb_load_buddy_gfp(struct super_block *sb, ext4_group_t group,
1100                        struct ext4_buddy *e4b, gfp_t gfp)
1101 {
1102         int blocks_per_page;
1103         int block;
1104         int pnum;
1105         int poff;
1106         struct page *page;
1107         int ret;
1108         struct ext4_group_info *grp;
1109         struct ext4_sb_info *sbi = EXT4_SB(sb);
1110         struct inode *inode = sbi->s_buddy_cache;
1111 
1112         might_sleep();
1113         mb_debug(1, "load group %u\n", group);
1114 
1115         blocks_per_page = PAGE_SIZE / sb->s_blocksize;
1116         grp = ext4_get_group_info(sb, group);
1117 
1118         e4b->bd_blkbits = sb->s_blocksize_bits;
1119         e4b->bd_info = grp;
1120         e4b->bd_sb = sb;
1121         e4b->bd_group = group;
1122         e4b->bd_buddy_page = NULL;
1123         e4b->bd_bitmap_page = NULL;
1124 
1125         if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
1126                 /*
1127                  * we need full data about the group
1128                  * to make a good selection
1129                  */
1130                 ret = ext4_mb_init_group(sb, group, gfp);
1131                 if (ret)
1132                         return ret;
1133         }
1134 
1135         /*
1136          * the buddy cache inode stores the block bitmap
1137          * and buddy information in consecutive blocks.
1138          * So for each group we need two blocks.
1139          */
1140         block = group * 2;
1141         pnum = block / blocks_per_page;
1142         poff = block % blocks_per_page;
1143 
1144         /* we could use find_or_create_page(), but it locks page
1145          * what we'd like to avoid in fast path ... */
1146         page = find_get_page_flags(inode->i_mapping, pnum, FGP_ACCESSED);
1147         if (page == NULL || !PageUptodate(page)) {
1148                 if (page)
1149                         /*
1150                          * drop the page reference and try
1151                          * to get the page with lock. If we
1152                          * are not uptodate that implies
1153                          * somebody just created the page but
1154                          * is yet to initialize the same. So
1155                          * wait for it to initialize.
1156                          */
1157                         put_page(page);
1158                 page = find_or_create_page(inode->i_mapping, pnum, gfp);
1159                 if (page) {
1160                         BUG_ON(page->mapping != inode->i_mapping);
1161                         if (!PageUptodate(page)) {
1162                                 ret = ext4_mb_init_cache(page, NULL, gfp);
1163                                 if (ret) {
1164                                         unlock_page(page);
1165                                         goto err;
1166                                 }
1167                                 mb_cmp_bitmaps(e4b, page_address(page) +
1168                                                (poff * sb->s_blocksize));
1169                         }
1170                         unlock_page(page);
1171                 }
1172         }
1173         if (page == NULL) {
1174                 ret = -ENOMEM;
1175                 goto err;
1176         }
1177         if (!PageUptodate(page)) {
1178                 ret = -EIO;
1179                 goto err;
1180         }
1181 
1182         /* Pages marked accessed already */
1183         e4b->bd_bitmap_page = page;
1184         e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
1185 
1186         block++;
1187         pnum = block / blocks_per_page;
1188         poff = block % blocks_per_page;
1189 
1190         page = find_get_page_flags(inode->i_mapping, pnum, FGP_ACCESSED);
1191         if (page == NULL || !PageUptodate(page)) {
1192                 if (page)
1193                         put_page(page);
1194                 page = find_or_create_page(inode->i_mapping, pnum, gfp);
1195                 if (page) {
1196                         BUG_ON(page->mapping != inode->i_mapping);
1197                         if (!PageUptodate(page)) {
1198                                 ret = ext4_mb_init_cache(page, e4b->bd_bitmap,
1199                                                          gfp);
1200                                 if (ret) {
1201                                         unlock_page(page);
1202                                         goto err;
1203                                 }
1204                         }
1205                         unlock_page(page);
1206                 }
1207         }
1208         if (page == NULL) {
1209                 ret = -ENOMEM;
1210                 goto err;
1211         }
1212         if (!PageUptodate(page)) {
1213                 ret = -EIO;
1214                 goto err;
1215         }
1216 
1217         /* Pages marked accessed already */
1218         e4b->bd_buddy_page = page;
1219         e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
1220 
1221         BUG_ON(e4b->bd_bitmap_page == NULL);
1222         BUG_ON(e4b->bd_buddy_page == NULL);
1223 
1224         return 0;
1225 
1226 err:
1227         if (page)
1228                 put_page(page);
1229         if (e4b->bd_bitmap_page)
1230                 put_page(e4b->bd_bitmap_page);
1231         if (e4b->bd_buddy_page)
1232                 put_page(e4b->bd_buddy_page);
1233         e4b->bd_buddy = NULL;
1234         e4b->bd_bitmap = NULL;
1235         return ret;
1236 }
1237 
1238 static int ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
1239                               struct ext4_buddy *e4b)
1240 {
1241         return ext4_mb_load_buddy_gfp(sb, group, e4b, GFP_NOFS);
1242 }
1243 
1244 static void ext4_mb_unload_buddy(struct ext4_buddy *e4b)
1245 {
1246         if (e4b->bd_bitmap_page)
1247                 put_page(e4b->bd_bitmap_page);
1248         if (e4b->bd_buddy_page)
1249                 put_page(e4b->bd_buddy_page);
1250 }
1251 
1252 
1253 static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
1254 {
1255         int order = 1;
1256         int bb_incr = 1 << (e4b->bd_blkbits - 1);
1257         void *bb;
1258 
1259         BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
1260         BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
1261 
1262         bb = e4b->bd_buddy;
1263         while (order <= e4b->bd_blkbits + 1) {
1264                 block = block >> 1;
1265                 if (!mb_test_bit(block, bb)) {
1266                         /* this block is part of buddy of order 'order' */
1267                         return order;
1268                 }
1269                 bb += bb_incr;
1270                 bb_incr >>= 1;
1271                 order++;
1272         }
1273         return 0;
1274 }
1275 
1276 static void mb_clear_bits(void *bm, int cur, int len)
1277 {
1278         __u32 *addr;
1279 
1280         len = cur + len;
1281         while (cur < len) {
1282                 if ((cur & 31) == 0 && (len - cur) >= 32) {
1283                         /* fast path: clear whole word at once */
1284                         addr = bm + (cur >> 3);
1285                         *addr = 0;
1286                         cur += 32;
1287                         continue;
1288                 }
1289                 mb_clear_bit(cur, bm);
1290                 cur++;
1291         }
1292 }
1293 
1294 /* clear bits in given range
1295  * will return first found zero bit if any, -1 otherwise
1296  */
1297 static int mb_test_and_clear_bits(void *bm, int cur, int len)
1298 {
1299         __u32 *addr;
1300         int zero_bit = -1;
1301 
1302         len = cur + len;
1303         while (cur < len) {
1304                 if ((cur & 31) == 0 && (len - cur) >= 32) {
1305                         /* fast path: clear whole word at once */
1306                         addr = bm + (cur >> 3);
1307                         if (*addr != (__u32)(-1) && zero_bit == -1)
1308                                 zero_bit = cur + mb_find_next_zero_bit(addr, 32, 0);
1309                         *addr = 0;
1310                         cur += 32;
1311                         continue;
1312                 }
1313                 if (!mb_test_and_clear_bit(cur, bm) && zero_bit == -1)
1314                         zero_bit = cur;
1315                 cur++;
1316         }
1317 
1318         return zero_bit;
1319 }
1320 
1321 void ext4_set_bits(void *bm, int cur, int len)
1322 {
1323         __u32 *addr;
1324 
1325         len = cur + len;
1326         while (cur < len) {
1327                 if ((cur & 31) == 0 && (len - cur) >= 32) {
1328                         /* fast path: set whole word at once */
1329                         addr = bm + (cur >> 3);
1330                         *addr = 0xffffffff;
1331                         cur += 32;
1332                         continue;
1333                 }
1334                 mb_set_bit(cur, bm);
1335                 cur++;
1336         }
1337 }
1338 
1339 /*
1340  * _________________________________________________________________ */
1341 
1342 static inline int mb_buddy_adjust_border(int* bit, void* bitmap, int side)
1343 {
1344         if (mb_test_bit(*bit + side, bitmap)) {
1345                 mb_clear_bit(*bit, bitmap);
1346                 (*bit) -= side;
1347                 return 1;
1348         }
1349         else {
1350                 (*bit) += side;
1351                 mb_set_bit(*bit, bitmap);
1352                 return -1;
1353         }
1354 }
1355 
1356 static void mb_buddy_mark_free(struct ext4_buddy *e4b, int first, int last)
1357 {
1358         int max;
1359         int order = 1;
1360         void *buddy = mb_find_buddy(e4b, order, &max);
1361 
1362         while (buddy) {
1363                 void *buddy2;
1364 
1365                 /* Bits in range [first; last] are known to be set since
1366                  * corresponding blocks were allocated. Bits in range
1367                  * (first; last) will stay set because they form buddies on
1368                  * upper layer. We just deal with borders if they don't
1369                  * align with upper layer and then go up.
1370                  * Releasing entire group is all about clearing
1371                  * single bit of highest order buddy.
1372                  */
1373 
1374                 /* Example:
1375                  * ---------------------------------
1376                  * |   1   |   1   |   1   |   1   |
1377                  * ---------------------------------
1378                  * | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1379                  * ---------------------------------
1380                  *   0   1   2   3   4   5   6   7
1381                  *      \_____________________/
1382                  *
1383                  * Neither [1] nor [6] is aligned to above layer.
1384                  * Left neighbour [0] is free, so mark it busy,
1385                  * decrease bb_counters and extend range to
1386                  * [0; 6]
1387                  * Right neighbour [7] is busy. It can't be coaleasced with [6], so
1388                  * mark [6] free, increase bb_counters and shrink range to
1389                  * [0; 5].
1390                  * Then shift range to [0; 2], go up and do the same.
1391                  */
1392 
1393 
1394                 if (first & 1)
1395                         e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&first, buddy, -1);
1396                 if (!(last & 1))
1397                         e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&last, buddy, 1);
1398                 if (first > last)
1399                         break;
1400                 order++;
1401 
1402                 if (first == last || !(buddy2 = mb_find_buddy(e4b, order, &max))) {
1403                         mb_clear_bits(buddy, first, last - first + 1);
1404                         e4b->bd_info->bb_counters[order - 1] += last - first + 1;
1405                         break;
1406                 }
1407                 first >>= 1;
1408                 last >>= 1;
1409                 buddy = buddy2;
1410         }
1411 }
1412 
1413 static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
1414                            int first, int count)
1415 {
1416         int left_is_free = 0;
1417         int right_is_free = 0;
1418         int block;
1419         int last = first + count - 1;
1420         struct super_block *sb = e4b->bd_sb;
1421 
1422         if (WARN_ON(count == 0))
1423                 return;
1424         BUG_ON(last >= (sb->s_blocksize << 3));
1425         assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
1426         /* Don't bother if the block group is corrupt. */
1427         if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
1428                 return;
1429 
1430         mb_check_buddy(e4b);
1431         mb_free_blocks_double(inode, e4b, first, count);
1432 
1433         e4b->bd_info->bb_free += count;
1434         if (first < e4b->bd_info->bb_first_free)
1435                 e4b->bd_info->bb_first_free = first;
1436 
1437         /* access memory sequentially: check left neighbour,
1438          * clear range and then check right neighbour
1439          */
1440         if (first != 0)
1441                 left_is_free = !mb_test_bit(first - 1, e4b->bd_bitmap);
1442         block = mb_test_and_clear_bits(e4b->bd_bitmap, first, count);
1443         if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])
1444                 right_is_free = !mb_test_bit(last + 1, e4b->bd_bitmap);
1445 
1446         if (unlikely(block != -1)) {
1447                 struct ext4_sb_info *sbi = EXT4_SB(sb);
1448                 ext4_fsblk_t blocknr;
1449 
1450                 blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
1451                 blocknr += EXT4_C2B(sbi, block);
1452                 ext4_grp_locked_error(sb, e4b->bd_group,
1453                                       inode ? inode->i_ino : 0,
1454                                       blocknr,
1455                                       "freeing already freed block "
1456                                       "(bit %u); block bitmap corrupt.",
1457                                       block);
1458                 ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
1459                                 EXT4_GROUP_INFO_BBITMAP_CORRUPT);
1460                 mb_regenerate_buddy(e4b);
1461                 goto done;
1462         }
1463 
1464         /* let's maintain fragments counter */
1465         if (left_is_free && right_is_free)
1466                 e4b->bd_info->bb_fragments--;
1467         else if (!left_is_free && !right_is_free)
1468                 e4b->bd_info->bb_fragments++;
1469 
1470         /* buddy[0] == bd_bitmap is a special case, so handle
1471          * it right away and let mb_buddy_mark_free stay free of
1472          * zero order checks.
1473          * Check if neighbours are to be coaleasced,
1474          * adjust bitmap bb_counters and borders appropriately.
1475          */
1476         if (first & 1) {
1477                 first += !left_is_free;
1478                 e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;
1479         }
1480         if (!(last & 1)) {
1481                 last -= !right_is_free;
1482                 e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;
1483         }
1484 
1485         if (first <= last)
1486                 mb_buddy_mark_free(e4b, first >> 1, last >> 1);
1487 
1488 done:
1489         mb_set_largest_free_order(sb, e4b->bd_info);
1490         mb_check_buddy(e4b);
1491 }
1492 
1493 static int mb_find_extent(struct ext4_buddy *e4b, int block,
1494                                 int needed, struct ext4_free_extent *ex)
1495 {
1496         int next = block;
1497         int max, order;
1498         void *buddy;
1499 
1500         assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1501         BUG_ON(ex == NULL);
1502 
1503         buddy = mb_find_buddy(e4b, 0, &max);
1504         BUG_ON(buddy == NULL);
1505         BUG_ON(block >= max);
1506         if (mb_test_bit(block, buddy)) {
1507                 ex->fe_len = 0;
1508                 ex->fe_start = 0;
1509                 ex->fe_group = 0;
1510                 return 0;
1511         }
1512 
1513         /* find actual order */
1514         order = mb_find_order_for_block(e4b, block);
1515         block = block >> order;
1516 
1517         ex->fe_len = 1 << order;
1518         ex->fe_start = block << order;
1519         ex->fe_group = e4b->bd_group;
1520 
1521         /* calc difference from given start */
1522         next = next - ex->fe_start;
1523         ex->fe_len -= next;
1524         ex->fe_start += next;
1525 
1526         while (needed > ex->fe_len &&
1527                mb_find_buddy(e4b, order, &max)) {
1528 
1529                 if (block + 1 >= max)
1530                         break;
1531 
1532                 next = (block + 1) * (1 << order);
1533                 if (mb_test_bit(next, e4b->bd_bitmap))
1534                         break;
1535 
1536                 order = mb_find_order_for_block(e4b, next);
1537 
1538                 block = next >> order;
1539                 ex->fe_len += 1 << order;
1540         }
1541 
1542         if (ex->fe_start + ex->fe_len > EXT4_CLUSTERS_PER_GROUP(e4b->bd_sb)) {
1543                 /* Should never happen! (but apparently sometimes does?!?) */
1544                 WARN_ON(1);
1545                 ext4_error(e4b->bd_sb, "corruption or bug in mb_find_extent "
1546                            "block=%d, order=%d needed=%d ex=%u/%d/%d@%u",
1547                            block, order, needed, ex->fe_group, ex->fe_start,
1548                            ex->fe_len, ex->fe_logical);
1549                 ex->fe_len = 0;
1550                 ex->fe_start = 0;
1551                 ex->fe_group = 0;
1552         }
1553         return ex->fe_len;
1554 }
1555 
1556 static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
1557 {
1558         int ord;
1559         int mlen = 0;
1560         int max = 0;
1561         int cur;
1562         int start = ex->fe_start;
1563         int len = ex->fe_len;
1564         unsigned ret = 0;
1565         int len0 = len;
1566         void *buddy;
1567 
1568         BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
1569         BUG_ON(e4b->bd_group != ex->fe_group);
1570         assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1571         mb_check_buddy(e4b);
1572         mb_mark_used_double(e4b, start, len);
1573 
1574         e4b->bd_info->bb_free -= len;
1575         if (e4b->bd_info->bb_first_free == start)
1576                 e4b->bd_info->bb_first_free += len;
1577 
1578         /* let's maintain fragments counter */
1579         if (start != 0)
1580                 mlen = !mb_test_bit(start - 1, e4b->bd_bitmap);
1581         if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
1582                 max = !mb_test_bit(start + len, e4b->bd_bitmap);
1583         if (mlen && max)
1584                 e4b->bd_info->bb_fragments++;
1585         else if (!mlen && !max)
1586                 e4b->bd_info->bb_fragments--;
1587 
1588         /* let's maintain buddy itself */
1589         while (len) {
1590                 ord = mb_find_order_for_block(e4b, start);
1591 
1592                 if (((start >> ord) << ord) == start && len >= (1 << ord)) {
1593                         /* the whole chunk may be allocated at once! */
1594                         mlen = 1 << ord;
1595                         buddy = mb_find_buddy(e4b, ord, &max);
1596                         BUG_ON((start >> ord) >= max);
1597                         mb_set_bit(start >> ord, buddy);
1598                         e4b->bd_info->bb_counters[ord]--;
1599                         start += mlen;
1600                         len -= mlen;
1601                         BUG_ON(len < 0);
1602                         continue;
1603                 }
1604 
1605                 /* store for history */
1606                 if (ret == 0)
1607                         ret = len | (ord << 16);
1608 
1609                 /* we have to split large buddy */
1610                 BUG_ON(ord <= 0);
1611                 buddy = mb_find_buddy(e4b, ord, &max);
1612                 mb_set_bit(start >> ord, buddy);
1613                 e4b->bd_info->bb_counters[ord]--;
1614 
1615                 ord--;
1616                 cur = (start >> ord) & ~1U;
1617                 buddy = mb_find_buddy(e4b, ord, &max);
1618                 mb_clear_bit(cur, buddy);
1619                 mb_clear_bit(cur + 1, buddy);
1620                 e4b->bd_info->bb_counters[ord]++;
1621                 e4b->bd_info->bb_counters[ord]++;
1622         }
1623         mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
1624 
1625         ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
1626         mb_check_buddy(e4b);
1627 
1628         return ret;
1629 }
1630 
1631 /*
1632  * Must be called under group lock!
1633  */
1634 static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
1635                                         struct ext4_buddy *e4b)
1636 {
1637         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1638         int ret;
1639 
1640         BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
1641         BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1642 
1643         ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
1644         ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
1645         ret = mb_mark_used(e4b, &ac->ac_b_ex);
1646 
1647         /* preallocation can change ac_b_ex, thus we store actually
1648          * allocated blocks for history */
1649         ac->ac_f_ex = ac->ac_b_ex;
1650 
1651         ac->ac_status = AC_STATUS_FOUND;
1652         ac->ac_tail = ret & 0xffff;
1653         ac->ac_buddy = ret >> 16;
1654 
1655         /*
1656          * take the page reference. We want the page to be pinned
1657          * so that we don't get a ext4_mb_init_cache_call for this
1658          * group until we update the bitmap. That would mean we
1659          * double allocate blocks. The reference is dropped
1660          * in ext4_mb_release_context
1661          */
1662         ac->ac_bitmap_page = e4b->bd_bitmap_page;
1663         get_page(ac->ac_bitmap_page);
1664         ac->ac_buddy_page = e4b->bd_buddy_page;
1665         get_page(ac->ac_buddy_page);
1666         /* store last allocated for subsequent stream allocation */
1667         if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
1668                 spin_lock(&sbi->s_md_lock);
1669                 sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
1670                 sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
1671                 spin_unlock(&sbi->s_md_lock);
1672         }
1673 }
1674 
1675 /*
1676  * regular allocator, for general purposes allocation
1677  */
1678 
1679 static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
1680                                         struct ext4_buddy *e4b,
1681                                         int finish_group)
1682 {
1683         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1684         struct ext4_free_extent *bex = &ac->ac_b_ex;
1685         struct ext4_free_extent *gex = &ac->ac_g_ex;
1686         struct ext4_free_extent ex;
1687         int max;
1688 
1689         if (ac->ac_status == AC_STATUS_FOUND)
1690                 return;
1691         /*
1692          * We don't want to scan for a whole year
1693          */
1694         if (ac->ac_found > sbi->s_mb_max_to_scan &&
1695                         !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1696                 ac->ac_status = AC_STATUS_BREAK;
1697                 return;
1698         }
1699 
1700         /*
1701          * Haven't found good chunk so far, let's continue
1702          */
1703         if (bex->fe_len < gex->fe_len)
1704                 return;
1705 
1706         if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
1707                         && bex->fe_group == e4b->bd_group) {
1708                 /* recheck chunk's availability - we don't know
1709                  * when it was found (within this lock-unlock
1710                  * period or not) */
1711                 max = mb_find_extent(e4b, bex->fe_start, gex->fe_len, &ex);
1712                 if (max >= gex->fe_len) {
1713                         ext4_mb_use_best_found(ac, e4b);
1714                         return;
1715                 }
1716         }
1717 }
1718 
1719 /*
1720  * The routine checks whether found extent is good enough. If it is,
1721  * then the extent gets marked used and flag is set to the context
1722  * to stop scanning. Otherwise, the extent is compared with the
1723  * previous found extent and if new one is better, then it's stored
1724  * in the context. Later, the best found extent will be used, if
1725  * mballoc can't find good enough extent.
1726  *
1727  * FIXME: real allocation policy is to be designed yet!
1728  */
1729 static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
1730                                         struct ext4_free_extent *ex,
1731                                         struct ext4_buddy *e4b)
1732 {
1733         struct ext4_free_extent *bex = &ac->ac_b_ex;
1734         struct ext4_free_extent *gex = &ac->ac_g_ex;
1735 
1736         BUG_ON(ex->fe_len <= 0);
1737         BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
1738         BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
1739         BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
1740 
1741         ac->ac_found++;
1742 
1743         /*
1744          * The special case - take what you catch first
1745          */
1746         if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1747                 *bex = *ex;
1748                 ext4_mb_use_best_found(ac, e4b);
1749                 return;
1750         }
1751 
1752         /*
1753          * Let's check whether the chuck is good enough
1754          */
1755         if (ex->fe_len == gex->fe_len) {
1756                 *bex = *ex;
1757                 ext4_mb_use_best_found(ac, e4b);
1758                 return;
1759         }
1760 
1761         /*
1762          * If this is first found extent, just store it in the context
1763          */
1764         if (bex->fe_len == 0) {
1765                 *bex = *ex;
1766                 return;
1767         }
1768 
1769         /*
1770          * If new found extent is better, store it in the context
1771          */
1772         if (bex->fe_len < gex->fe_len) {
1773                 /* if the request isn't satisfied, any found extent
1774                  * larger than previous best one is better */
1775                 if (ex->fe_len > bex->fe_len)
1776                         *bex = *ex;
1777         } else if (ex->fe_len > gex->fe_len) {
1778                 /* if the request is satisfied, then we try to find
1779                  * an extent that still satisfy the request, but is
1780                  * smaller than previous one */
1781                 if (ex->fe_len < bex->fe_len)
1782                         *bex = *ex;
1783         }
1784 
1785         ext4_mb_check_limits(ac, e4b, 0);
1786 }
1787 
1788 static noinline_for_stack
1789 int ext4_mb_try_best_found(struct ext4_allocation_context *ac,
1790                                         struct ext4_buddy *e4b)
1791 {
1792         struct ext4_free_extent ex = ac->ac_b_ex;
1793         ext4_group_t group = ex.fe_group;
1794         int max;
1795         int err;
1796 
1797         BUG_ON(ex.fe_len <= 0);
1798         err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1799         if (err)
1800                 return err;
1801 
1802         ext4_lock_group(ac->ac_sb, group);
1803         max = mb_find_extent(e4b, ex.fe_start, ex.fe_len, &ex);
1804 
1805         if (max > 0) {
1806                 ac->ac_b_ex = ex;
1807                 ext4_mb_use_best_found(ac, e4b);
1808         }
1809 
1810         ext4_unlock_group(ac->ac_sb, group);
1811         ext4_mb_unload_buddy(e4b);
1812 
1813         return 0;
1814 }
1815 
1816 static noinline_for_stack
1817 int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
1818                                 struct ext4_buddy *e4b)
1819 {
1820         ext4_group_t group = ac->ac_g_ex.fe_group;
1821         int max;
1822         int err;
1823         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1824         struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
1825         struct ext4_free_extent ex;
1826 
1827         if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
1828                 return 0;
1829         if (grp->bb_free == 0)
1830                 return 0;
1831 
1832         err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1833         if (err)
1834                 return err;
1835 
1836         if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info))) {
1837                 ext4_mb_unload_buddy(e4b);
1838                 return 0;
1839         }
1840 
1841         ext4_lock_group(ac->ac_sb, group);
1842         max = mb_find_extent(e4b, ac->ac_g_ex.fe_start,
1843                              ac->ac_g_ex.fe_len, &ex);
1844         ex.fe_logical = 0xDEADFA11; /* debug value */
1845 
1846         if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
1847                 ext4_fsblk_t start;
1848 
1849                 start = ext4_group_first_block_no(ac->ac_sb, e4b->bd_group) +
1850                         ex.fe_start;
1851                 /* use do_div to get remainder (would be 64-bit modulo) */
1852                 if (do_div(start, sbi->s_stripe) == 0) {
1853                         ac->ac_found++;
1854                         ac->ac_b_ex = ex;
1855                         ext4_mb_use_best_found(ac, e4b);
1856                 }
1857         } else if (max >= ac->ac_g_ex.fe_len) {
1858                 BUG_ON(ex.fe_len <= 0);
1859                 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1860                 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1861                 ac->ac_found++;
1862                 ac->ac_b_ex = ex;
1863                 ext4_mb_use_best_found(ac, e4b);
1864         } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
1865                 /* Sometimes, caller may want to merge even small
1866                  * number of blocks to an existing extent */
1867                 BUG_ON(ex.fe_len <= 0);
1868                 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1869                 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1870                 ac->ac_found++;
1871                 ac->ac_b_ex = ex;
1872                 ext4_mb_use_best_found(ac, e4b);
1873         }
1874         ext4_unlock_group(ac->ac_sb, group);
1875         ext4_mb_unload_buddy(e4b);
1876 
1877         return 0;
1878 }
1879 
1880 /*
1881  * The routine scans buddy structures (not bitmap!) from given order
1882  * to max order and tries to find big enough chunk to satisfy the req
1883  */
1884 static noinline_for_stack
1885 void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
1886                                         struct ext4_buddy *e4b)
1887 {
1888         struct super_block *sb = ac->ac_sb;
1889         struct ext4_group_info *grp = e4b->bd_info;
1890         void *buddy;
1891         int i;
1892         int k;
1893         int max;
1894 
1895         BUG_ON(ac->ac_2order <= 0);
1896         for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
1897                 if (grp->bb_counters[i] == 0)
1898                         continue;
1899 
1900                 buddy = mb_find_buddy(e4b, i, &max);
1901                 BUG_ON(buddy == NULL);
1902 
1903                 k = mb_find_next_zero_bit(buddy, max, 0);
1904                 BUG_ON(k >= max);
1905 
1906                 ac->ac_found++;
1907 
1908                 ac->ac_b_ex.fe_len = 1 << i;
1909                 ac->ac_b_ex.fe_start = k << i;
1910                 ac->ac_b_ex.fe_group = e4b->bd_group;
1911 
1912                 ext4_mb_use_best_found(ac, e4b);
1913 
1914                 BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);
1915 
1916                 if (EXT4_SB(sb)->s_mb_stats)
1917                         atomic_inc(&EXT4_SB(sb)->s_bal_2orders);
1918 
1919                 break;
1920         }
1921 }
1922 
1923 /*
1924  * The routine scans the group and measures all found extents.
1925  * In order to optimize scanning, caller must pass number of
1926  * free blocks in the group, so the routine can know upper limit.
1927  */
1928 static noinline_for_stack
1929 void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
1930                                         struct ext4_buddy *e4b)
1931 {
1932         struct super_block *sb = ac->ac_sb;
1933         void *bitmap = e4b->bd_bitmap;
1934         struct ext4_free_extent ex;
1935         int i;
1936         int free;
1937 
1938         free = e4b->bd_info->bb_free;
1939         BUG_ON(free <= 0);
1940 
1941         i = e4b->bd_info->bb_first_free;
1942 
1943         while (free && ac->ac_status == AC_STATUS_CONTINUE) {
1944                 i = mb_find_next_zero_bit(bitmap,
1945                                                 EXT4_CLUSTERS_PER_GROUP(sb), i);
1946                 if (i >= EXT4_CLUSTERS_PER_GROUP(sb)) {
1947                         /*
1948                          * IF we have corrupt bitmap, we won't find any
1949                          * free blocks even though group info says we
1950                          * we have free blocks
1951                          */
1952                         ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
1953                                         "%d free clusters as per "
1954                                         "group info. But bitmap says 0",
1955                                         free);
1956                         ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
1957                                         EXT4_GROUP_INFO_BBITMAP_CORRUPT);
1958                         break;
1959                 }
1960 
1961                 mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);
1962                 BUG_ON(ex.fe_len <= 0);
1963                 if (free < ex.fe_len) {
1964                         ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
1965                                         "%d free clusters as per "
1966                                         "group info. But got %d blocks",
1967                                         free, ex.fe_len);
1968                         ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
1969                                         EXT4_GROUP_INFO_BBITMAP_CORRUPT);
1970                         /*
1971                          * The number of free blocks differs. This mostly
1972                          * indicate that the bitmap is corrupt. So exit
1973                          * without claiming the space.
1974                          */
1975                         break;
1976                 }
1977                 ex.fe_logical = 0xDEADC0DE; /* debug value */
1978                 ext4_mb_measure_extent(ac, &ex, e4b);
1979 
1980                 i += ex.fe_len;
1981                 free -= ex.fe_len;
1982         }
1983 
1984         ext4_mb_check_limits(ac, e4b, 1);
1985 }
1986 
1987 /*
1988  * This is a special case for storages like raid5
1989  * we try to find stripe-aligned chunks for stripe-size-multiple requests
1990  */
1991 static noinline_for_stack
1992 void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
1993                                  struct ext4_buddy *e4b)
1994 {
1995         struct super_block *sb = ac->ac_sb;
1996         struct ext4_sb_info *sbi = EXT4_SB(sb);
1997         void *bitmap = e4b->bd_bitmap;
1998         struct ext4_free_extent ex;
1999         ext4_fsblk_t first_group_block;
2000         ext4_fsblk_t a;
2001         ext4_grpblk_t i;
2002         int max;
2003 
2004         BUG_ON(sbi->s_stripe == 0);
2005 
2006         /* find first stripe-aligned block in group */
2007         first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);
2008 
2009         a = first_group_block + sbi->s_stripe - 1;
2010         do_div(a, sbi->s_stripe);
2011         i = (a * sbi->s_stripe) - first_group_block;
2012 
2013         while (i < EXT4_CLUSTERS_PER_GROUP(sb)) {
2014                 if (!mb_test_bit(i, bitmap)) {
2015                         max = mb_find_extent(e4b, i, sbi->s_stripe, &ex);
2016                         if (max >= sbi->s_stripe) {
2017                                 ac->ac_found++;
2018                                 ex.fe_logical = 0xDEADF00D; /* debug value */
2019                                 ac->ac_b_ex = ex;
2020                                 ext4_mb_use_best_found(ac, e4b);
2021                                 break;
2022                         }
2023                 }
2024                 i += sbi->s_stripe;
2025         }
2026 }
2027 
2028 /*
2029  * This is now called BEFORE we load the buddy bitmap.
2030  * Returns either 1 or 0 indicating that the group is either suitable
2031  * for the allocation or not. In addition it can also return negative
2032  * error code when something goes wrong.
2033  */
2034 static int ext4_mb_good_group(struct ext4_allocation_context *ac,
2035                                 ext4_group_t group, int cr)
2036 {
2037         unsigned free, fragments;
2038         int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));
2039         struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
2040 
2041         BUG_ON(cr < 0 || cr >= 4);
2042 
2043         free = grp->bb_free;
2044         if (free == 0)
2045                 return 0;
2046         if (cr <= 2 && free < ac->ac_g_ex.fe_len)
2047                 return 0;
2048 
2049         if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))
2050                 return 0;
2051 
2052         /* We only do this if the grp has never been initialized */
2053         if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
2054                 int ret = ext4_mb_init_group(ac->ac_sb, group, GFP_NOFS);
2055                 if (ret)
2056                         return ret;
2057         }
2058 
2059         fragments = grp->bb_fragments;
2060         if (fragments == 0)
2061                 return 0;
2062 
2063         switch (cr) {
2064         case 0:
2065                 BUG_ON(ac->ac_2order == 0);
2066 
2067                 /* Avoid using the first bg of a flexgroup for data files */
2068                 if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&
2069                     (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) &&
2070                     ((group % flex_size) == 0))
2071                         return 0;
2072 
2073                 if ((ac->ac_2order > ac->ac_sb->s_blocksize_bits+1) ||
2074                     (free / fragments) >= ac->ac_g_ex.fe_len)
2075                         return 1;
2076 
2077                 if (grp->bb_largest_free_order < ac->ac_2order)
2078                         return 0;
2079 
2080                 return 1;
2081         case 1:
2082                 if ((free / fragments) >= ac->ac_g_ex.fe_len)
2083                         return 1;
2084                 break;
2085         case 2:
2086                 if (free >= ac->ac_g_ex.fe_len)
2087                         return 1;
2088                 break;
2089         case 3:
2090                 return 1;
2091         default:
2092                 BUG();
2093         }
2094 
2095         return 0;
2096 }
2097 
2098 static noinline_for_stack int
2099 ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
2100 {
2101         ext4_group_t ngroups, group, i;
2102         int cr;
2103         int err = 0, first_err = 0;
2104         struct ext4_sb_info *sbi;
2105         struct super_block *sb;
2106         struct ext4_buddy e4b;
2107 
2108         sb = ac->ac_sb;
2109         sbi = EXT4_SB(sb);
2110         ngroups = ext4_get_groups_count(sb);
2111         /* non-extent files are limited to low blocks/groups */
2112         if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))
2113                 ngroups = sbi->s_blockfile_groups;
2114 
2115         BUG_ON(ac->ac_status == AC_STATUS_FOUND);
2116 
2117         /* first, try the goal */
2118         err = ext4_mb_find_by_goal(ac, &e4b);
2119         if (err || ac->ac_status == AC_STATUS_FOUND)
2120                 goto out;
2121 
2122         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
2123                 goto out;
2124 
2125         /*
2126          * ac->ac2_order is set only if the fe_len is a power of 2
2127          * if ac2_order is set we also set criteria to 0 so that we
2128          * try exact allocation using buddy.
2129          */
2130         i = fls(ac->ac_g_ex.fe_len);
2131         ac->ac_2order = 0;
2132         /*
2133          * We search using buddy data only if the order of the request
2134          * is greater than equal to the sbi_s_mb_order2_reqs
2135          * You can tune it via /sys/fs/ext4/<partition>/mb_order2_req
2136          * We also support searching for power-of-two requests only for
2137          * requests upto maximum buddy size we have constructed.
2138          */
2139         if (i >= sbi->s_mb_order2_reqs && i <= sb->s_blocksize_bits + 2) {
2140                 /*
2141                  * This should tell if fe_len is exactly power of 2
2142                  */
2143                 if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)
2144                         ac->ac_2order = array_index_nospec(i - 1,
2145                                                            sb->s_blocksize_bits + 2);
2146         }
2147 
2148         /* if stream allocation is enabled, use global goal */
2149         if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
2150                 /* TBD: may be hot point */
2151                 spin_lock(&sbi->s_md_lock);
2152                 ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
2153                 ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
2154                 spin_unlock(&sbi->s_md_lock);
2155         }
2156 
2157         /* Let's just scan groups to find more-less suitable blocks */
2158         cr = ac->ac_2order ? 0 : 1;
2159         /*
2160          * cr == 0 try to get exact allocation,
2161          * cr == 3  try to get anything
2162          */
2163 repeat:
2164         for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
2165                 ac->ac_criteria = cr;
2166                 /*
2167                  * searching for the right group start
2168                  * from the goal value specified
2169                  */
2170                 group = ac->ac_g_ex.fe_group;
2171 
2172                 for (i = 0; i < ngroups; group++, i++) {
2173                         int ret = 0;
2174                         cond_resched();
2175                         /*
2176                          * Artificially restricted ngroups for non-extent
2177                          * files makes group > ngroups possible on first loop.
2178                          */
2179                         if (group >= ngroups)
2180                                 group = 0;
2181 
2182                         /* This now checks without needing the buddy page */
2183                         ret = ext4_mb_good_group(ac, group, cr);
2184                         if (ret <= 0) {
2185                                 if (!first_err)
2186                                         first_err = ret;
2187                                 continue;
2188                         }
2189 
2190                         err = ext4_mb_load_buddy(sb, group, &e4b);
2191                         if (err)
2192                                 goto out;
2193 
2194                         ext4_lock_group(sb, group);
2195 
2196                         /*
2197                          * We need to check again after locking the
2198                          * block group
2199                          */
2200                         ret = ext4_mb_good_group(ac, group, cr);
2201                         if (ret <= 0) {
2202                                 ext4_unlock_group(sb, group);
2203                                 ext4_mb_unload_buddy(&e4b);
2204                                 if (!first_err)
2205                                         first_err = ret;
2206                                 continue;
2207                         }
2208 
2209                         ac->ac_groups_scanned++;
2210                         if (cr == 0)
2211                                 ext4_mb_simple_scan_group(ac, &e4b);
2212                         else if (cr == 1 && sbi->s_stripe &&
2213                                         !(ac->ac_g_ex.fe_len % sbi->s_stripe))
2214                                 ext4_mb_scan_aligned(ac, &e4b);
2215                         else
2216                                 ext4_mb_complex_scan_group(ac, &e4b);
2217 
2218                         ext4_unlock_group(sb, group);
2219                         ext4_mb_unload_buddy(&e4b);
2220 
2221                         if (ac->ac_status != AC_STATUS_CONTINUE)
2222                                 break;
2223                 }
2224         }
2225 
2226         if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
2227             !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2228                 /*
2229                  * We've been searching too long. Let's try to allocate
2230                  * the best chunk we've found so far
2231                  */
2232 
2233                 ext4_mb_try_best_found(ac, &e4b);
2234                 if (ac->ac_status != AC_STATUS_FOUND) {
2235                         /*
2236                          * Someone more lucky has already allocated it.
2237                          * The only thing we can do is just take first
2238                          * found block(s)
2239                         printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n");
2240                          */
2241                         ac->ac_b_ex.fe_group = 0;
2242                         ac->ac_b_ex.fe_start = 0;
2243                         ac->ac_b_ex.fe_len = 0;
2244                         ac->ac_status = AC_STATUS_CONTINUE;
2245                         ac->ac_flags |= EXT4_MB_HINT_FIRST;
2246                         cr = 3;
2247                         atomic_inc(&sbi->s_mb_lost_chunks);
2248                         goto repeat;
2249                 }
2250         }
2251 out:
2252         if (!err && ac->ac_status != AC_STATUS_FOUND && first_err)
2253                 err = first_err;
2254         return err;
2255 }
2256 
2257 static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
2258 {
2259         struct super_block *sb = PDE_DATA(file_inode(seq->file));
2260         ext4_group_t group;
2261 
2262         if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2263                 return NULL;
2264         group = *pos + 1;
2265         return (void *) ((unsigned long) group);
2266 }
2267 
2268 static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
2269 {
2270         struct super_block *sb = PDE_DATA(file_inode(seq->file));
2271         ext4_group_t group;
2272 
2273         ++*pos;
2274         if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2275                 return NULL;
2276         group = *pos + 1;
2277         return (void *) ((unsigned long) group);
2278 }
2279 
2280 static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
2281 {
2282         struct super_block *sb = PDE_DATA(file_inode(seq->file));
2283         ext4_group_t group = (ext4_group_t) ((unsigned long) v);
2284         int i;
2285         int err, buddy_loaded = 0;
2286         struct ext4_buddy e4b;
2287         struct ext4_group_info *grinfo;
2288         unsigned char blocksize_bits = min_t(unsigned char,
2289                                              sb->s_blocksize_bits,
2290                                              EXT4_MAX_BLOCK_LOG_SIZE);
2291         struct sg {
2292                 struct ext4_group_info info;
2293                 ext4_grpblk_t counters[EXT4_MAX_BLOCK_LOG_SIZE + 2];
2294         } sg;
2295 
2296         group--;
2297         if (group == 0)
2298                 seq_puts(seq, "#group: free  frags first ["
2299                               " 2^0   2^1   2^2   2^3   2^4   2^5   2^6  "
2300                               " 2^7   2^8   2^9   2^10  2^11  2^12  2^13  ]\n");
2301 
2302         i = (blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
2303                 sizeof(struct ext4_group_info);
2304 
2305         grinfo = ext4_get_group_info(sb, group);
2306         /* Load the group info in memory only if not already loaded. */
2307         if (unlikely(EXT4_MB_GRP_NEED_INIT(grinfo))) {
2308                 err = ext4_mb_load_buddy(sb, group, &e4b);
2309                 if (err) {
2310                         seq_printf(seq, "#%-5u: I/O error\n", group);
2311                         return 0;
2312                 }
2313                 buddy_loaded = 1;
2314         }
2315 
2316         memcpy(&sg, ext4_get_group_info(sb, group), i);
2317 
2318         if (buddy_loaded)
2319                 ext4_mb_unload_buddy(&e4b);
2320 
2321         seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,
2322                         sg.info.bb_fragments, sg.info.bb_first_free);
2323         for (i = 0; i <= 13; i++)
2324                 seq_printf(seq, " %-5u", i <= blocksize_bits + 1 ?
2325                                 sg.info.bb_counters[i] : 0);
2326         seq_printf(seq, " ]\n");
2327 
2328         return 0;
2329 }
2330 
2331 static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
2332 {
2333 }
2334 
2335 const struct seq_operations ext4_mb_seq_groups_ops = {
2336         .start  = ext4_mb_seq_groups_start,
2337         .next   = ext4_mb_seq_groups_next,
2338         .stop   = ext4_mb_seq_groups_stop,
2339         .show   = ext4_mb_seq_groups_show,
2340 };
2341 
2342 static struct kmem_cache *get_groupinfo_cache(int blocksize_bits)
2343 {
2344         int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
2345         struct kmem_cache *cachep = ext4_groupinfo_caches[cache_index];
2346 
2347         BUG_ON(!cachep);
2348         return cachep;
2349 }
2350 
2351 /*
2352  * Allocate the top-level s_group_info array for the specified number
2353  * of groups
2354  */
2355 int ext4_mb_alloc_groupinfo(struct super_block *sb, ext4_group_t ngroups)
2356 {
2357         struct ext4_sb_info *sbi = EXT4_SB(sb);
2358         unsigned size;
2359         struct ext4_group_info ***old_groupinfo, ***new_groupinfo;
2360 
2361         size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>
2362                 EXT4_DESC_PER_BLOCK_BITS(sb);
2363         if (size <= sbi->s_group_info_size)
2364                 return 0;
2365 
2366         size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);
2367         new_groupinfo = kvzalloc(size, GFP_KERNEL);
2368         if (!new_groupinfo) {
2369                 ext4_msg(sb, KERN_ERR, "can't allocate buddy meta group");
2370                 return -ENOMEM;
2371         }
2372         rcu_read_lock();
2373         old_groupinfo = rcu_dereference(sbi->s_group_info);
2374         if (old_groupinfo)
2375                 memcpy(new_groupinfo, old_groupinfo,
2376                        sbi->s_group_info_size * sizeof(*sbi->s_group_info));
2377         rcu_read_unlock();
2378         rcu_assign_pointer(sbi->s_group_info, new_groupinfo);
2379         sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);
2380         if (old_groupinfo)
2381                 ext4_kvfree_array_rcu(old_groupinfo);
2382         ext4_debug("allocated s_groupinfo array for %d meta_bg's\n", 
2383                    sbi->s_group_info_size);
2384         return 0;
2385 }
2386 
2387 /* Create and initialize ext4_group_info data for the given group. */
2388 int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
2389                           struct ext4_group_desc *desc)
2390 {
2391         int i;
2392         int metalen = 0;
2393         int idx = group >> EXT4_DESC_PER_BLOCK_BITS(sb);
2394         struct ext4_sb_info *sbi = EXT4_SB(sb);
2395         struct ext4_group_info **meta_group_info;
2396         struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2397 
2398         /*
2399          * First check if this group is the first of a reserved block.
2400          * If it's true, we have to allocate a new table of pointers
2401          * to ext4_group_info structures
2402          */
2403         if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
2404                 metalen = sizeof(*meta_group_info) <<
2405                         EXT4_DESC_PER_BLOCK_BITS(sb);
2406                 meta_group_info = kmalloc(metalen, GFP_NOFS);
2407                 if (meta_group_info == NULL) {
2408                         ext4_msg(sb, KERN_ERR, "can't allocate mem "
2409                                  "for a buddy group");
2410                         goto exit_meta_group_info;
2411                 }
2412                 rcu_read_lock();
2413                 rcu_dereference(sbi->s_group_info)[idx] = meta_group_info;
2414                 rcu_read_unlock();
2415         }
2416 
2417         meta_group_info = sbi_array_rcu_deref(sbi, s_group_info, idx);
2418         i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);
2419 
2420         meta_group_info[i] = kmem_cache_zalloc(cachep, GFP_NOFS);
2421         if (meta_group_info[i] == NULL) {
2422                 ext4_msg(sb, KERN_ERR, "can't allocate buddy mem");
2423                 goto exit_group_info;
2424         }
2425         set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
2426                 &(meta_group_info[i]->bb_state));
2427 
2428         /*
2429          * initialize bb_free to be able to skip
2430          * empty groups without initialization
2431          */
2432         if (ext4_has_group_desc_csum(sb) &&
2433             (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
2434                 meta_group_info[i]->bb_free =
2435                         ext4_free_clusters_after_init(sb, group, desc);
2436         } else {
2437                 meta_group_info[i]->bb_free =
2438                         ext4_free_group_clusters(sb, desc);
2439         }
2440 
2441         INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
2442         init_rwsem(&meta_group_info[i]->alloc_sem);
2443         meta_group_info[i]->bb_free_root = RB_ROOT;
2444         meta_group_info[i]->bb_largest_free_order = -1;  /* uninit */
2445 
2446 #ifdef DOUBLE_CHECK
2447         {
2448                 struct buffer_head *bh;
2449                 meta_group_info[i]->bb_bitmap =
2450                         kmalloc(sb->s_blocksize, GFP_NOFS);
2451                 BUG_ON(meta_group_info[i]->bb_bitmap == NULL);
2452                 bh = ext4_read_block_bitmap(sb, group);
2453                 BUG_ON(IS_ERR_OR_NULL(bh));
2454                 memcpy(meta_group_info[i]->bb_bitmap, bh->b_data,
2455                         sb->s_blocksize);
2456                 put_bh(bh);
2457         }
2458 #endif
2459 
2460         return 0;
2461 
2462 exit_group_info:
2463         /* If a meta_group_info table has been allocated, release it now */
2464         if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
2465                 struct ext4_group_info ***group_info;
2466 
2467                 rcu_read_lock();
2468                 group_info = rcu_dereference(sbi->s_group_info);
2469                 kfree(group_info[idx]);
2470                 group_info[idx] = NULL;
2471                 rcu_read_unlock();
2472         }
2473 exit_meta_group_info:
2474         return -ENOMEM;
2475 } /* ext4_mb_add_groupinfo */
2476 
2477 static int ext4_mb_init_backend(struct super_block *sb)
2478 {
2479         ext4_group_t ngroups = ext4_get_groups_count(sb);
2480         ext4_group_t i;
2481         struct ext4_sb_info *sbi = EXT4_SB(sb);
2482         int err;
2483         struct ext4_group_desc *desc;
2484         struct ext4_group_info ***group_info;
2485         struct kmem_cache *cachep;
2486 
2487         err = ext4_mb_alloc_groupinfo(sb, ngroups);
2488         if (err)
2489                 return err;
2490 
2491         sbi->s_buddy_cache = new_inode(sb);
2492         if (sbi->s_buddy_cache == NULL) {
2493                 ext4_msg(sb, KERN_ERR, "can't get new inode");
2494                 goto err_freesgi;
2495         }
2496         /* To avoid potentially colliding with an valid on-disk inode number,
2497          * use EXT4_BAD_INO for the buddy cache inode number.  This inode is
2498          * not in the inode hash, so it should never be found by iget(), but
2499          * this will avoid confusion if it ever shows up during debugging. */
2500         sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;
2501         EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
2502         for (i = 0; i < ngroups; i++) {
2503                 cond_resched();
2504                 desc = ext4_get_group_desc(sb, i, NULL);
2505                 if (desc == NULL) {
2506                         ext4_msg(sb, KERN_ERR, "can't read descriptor %u", i);
2507                         goto err_freebuddy;
2508                 }
2509                 if (ext4_mb_add_groupinfo(sb, i, desc) != 0)
2510                         goto err_freebuddy;
2511         }
2512 
2513         return 0;
2514 
2515 err_freebuddy:
2516         cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2517         while (i-- > 0)
2518                 kmem_cache_free(cachep, ext4_get_group_info(sb, i));
2519         i = sbi->s_group_info_size;
2520         rcu_read_lock();
2521         group_info = rcu_dereference(sbi->s_group_info);
2522         while (i-- > 0)
2523                 kfree(group_info[i]);
2524         rcu_read_unlock();
2525         iput(sbi->s_buddy_cache);
2526 err_freesgi:
2527         rcu_read_lock();
2528         kvfree(rcu_dereference(sbi->s_group_info));
2529         rcu_read_unlock();
2530         return -ENOMEM;
2531 }
2532 
2533 static void ext4_groupinfo_destroy_slabs(void)
2534 {
2535         int i;
2536 
2537         for (i = 0; i < NR_GRPINFO_CACHES; i++) {
2538                 kmem_cache_destroy(ext4_groupinfo_caches[i]);
2539                 ext4_groupinfo_caches[i] = NULL;
2540         }
2541 }
2542 
2543 static int ext4_groupinfo_create_slab(size_t size)
2544 {
2545         static DEFINE_MUTEX(ext4_grpinfo_slab_create_mutex);
2546         int slab_size;
2547         int blocksize_bits = order_base_2(size);
2548         int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
2549         struct kmem_cache *cachep;
2550 
2551         if (cache_index >= NR_GRPINFO_CACHES)
2552                 return -EINVAL;
2553 
2554         if (unlikely(cache_index < 0))
2555                 cache_index = 0;
2556 
2557         mutex_lock(&ext4_grpinfo_slab_create_mutex);
2558         if (ext4_groupinfo_caches[cache_index]) {
2559                 mutex_unlock(&ext4_grpinfo_slab_create_mutex);
2560                 return 0;       /* Already created */
2561         }
2562 
2563         slab_size = offsetof(struct ext4_group_info,
2564                                 bb_counters[blocksize_bits + 2]);
2565 
2566         cachep = kmem_cache_create(ext4_groupinfo_slab_names[cache_index],
2567                                         slab_size, 0, SLAB_RECLAIM_ACCOUNT,
2568                                         NULL);
2569 
2570         ext4_groupinfo_caches[cache_index] = cachep;
2571 
2572         mutex_unlock(&ext4_grpinfo_slab_create_mutex);
2573         if (!cachep) {
2574                 printk(KERN_EMERG
2575                        "EXT4-fs: no memory for groupinfo slab cache\n");
2576                 return -ENOMEM;
2577         }
2578 
2579         return 0;
2580 }
2581 
2582 int ext4_mb_init(struct super_block *sb)
2583 {
2584         struct ext4_sb_info *sbi = EXT4_SB(sb);
2585         unsigned i, j;
2586         unsigned offset, offset_incr;
2587         unsigned max;
2588         int ret;
2589 
2590         i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_offsets);
2591 
2592         sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
2593         if (sbi->s_mb_offsets == NULL) {
2594                 ret = -ENOMEM;
2595                 goto out;
2596         }
2597 
2598         i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_maxs);
2599         sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
2600         if (sbi->s_mb_maxs == NULL) {
2601                 ret = -ENOMEM;
2602                 goto out;
2603         }
2604 
2605         ret = ext4_groupinfo_create_slab(sb->s_blocksize);
2606         if (ret < 0)
2607                 goto out;
2608 
2609         /* order 0 is regular bitmap */
2610         sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
2611         sbi->s_mb_offsets[0] = 0;
2612 
2613         i = 1;
2614         offset = 0;
2615         offset_incr = 1 << (sb->s_blocksize_bits - 1);
2616         max = sb->s_blocksize << 2;
2617         do {
2618                 sbi->s_mb_offsets[i] = offset;
2619                 sbi->s_mb_maxs[i] = max;
2620                 offset += offset_incr;
2621                 offset_incr = offset_incr >> 1;
2622                 max = max >> 1;
2623                 i++;
2624         } while (i <= sb->s_blocksize_bits + 1);
2625 
2626         spin_lock_init(&sbi->s_md_lock);
2627         spin_lock_init(&sbi->s_bal_lock);
2628         sbi->s_mb_free_pending = 0;
2629         INIT_LIST_HEAD(&sbi->s_freed_data_list);
2630 
2631         sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
2632         sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
2633         sbi->s_mb_stats = MB_DEFAULT_STATS;
2634         sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
2635         sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
2636         /*
2637          * The default group preallocation is 512, which for 4k block
2638          * sizes translates to 2 megabytes.  However for bigalloc file
2639          * systems, this is probably too big (i.e, if the cluster size
2640          * is 1 megabyte, then group preallocation size becomes half a
2641          * gigabyte!).  As a default, we will keep a two megabyte
2642          * group pralloc size for cluster sizes up to 64k, and after
2643          * that, we will force a minimum group preallocation size of
2644          * 32 clusters.  This translates to 8 megs when the cluster
2645          * size is 256k, and 32 megs when the cluster size is 1 meg,
2646          * which seems reasonable as a default.
2647          */
2648         sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>
2649                                        sbi->s_cluster_bits, 32);
2650         /*
2651          * If there is a s_stripe > 1, then we set the s_mb_group_prealloc
2652          * to the lowest multiple of s_stripe which is bigger than
2653          * the s_mb_group_prealloc as determined above. We want
2654          * the preallocation size to be an exact multiple of the
2655          * RAID stripe size so that preallocations don't fragment
2656          * the stripes.
2657          */
2658         if (sbi->s_stripe > 1) {
2659                 sbi->s_mb_group_prealloc = roundup(
2660                         sbi->s_mb_group_prealloc, sbi->s_stripe);
2661         }
2662 
2663         sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
2664         if (sbi->s_locality_groups == NULL) {
2665                 ret = -ENOMEM;
2666                 goto out;
2667         }
2668         for_each_possible_cpu(i) {
2669                 struct ext4_locality_group *lg;
2670                 lg = per_cpu_ptr(sbi->s_locality_groups, i);
2671                 mutex_init(&lg->lg_mutex);
2672                 for (j = 0; j < PREALLOC_TB_SIZE; j++)
2673                         INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);
2674                 spin_lock_init(&lg->lg_prealloc_lock);
2675         }
2676 
2677         /* init file for buddy data */
2678         ret = ext4_mb_init_backend(sb);
2679         if (ret != 0)
2680                 goto out_free_locality_groups;
2681 
2682         return 0;
2683 
2684 out_free_locality_groups:
2685         free_percpu(sbi->s_locality_groups);
2686         sbi->s_locality_groups = NULL;
2687 out:
2688         kfree(sbi->s_mb_offsets);
2689         sbi->s_mb_offsets = NULL;
2690         kfree(sbi->s_mb_maxs);
2691         sbi->s_mb_maxs = NULL;
2692         return ret;
2693 }
2694 
2695 /* need to called with the ext4 group lock held */
2696 static void ext4_mb_cleanup_pa(struct ext4_group_info *grp)
2697 {
2698         struct ext4_prealloc_space *pa;
2699         struct list_head *cur, *tmp;
2700         int count = 0;
2701 
2702         list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
2703                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
2704                 list_del(&pa->pa_group_list);
2705                 count++;
2706                 kmem_cache_free(ext4_pspace_cachep, pa);
2707         }
2708         if (count)
2709                 mb_debug(1, "mballoc: %u PAs left\n", count);
2710 
2711 }
2712 
2713 int ext4_mb_release(struct super_block *sb)
2714 {
2715         ext4_group_t ngroups = ext4_get_groups_count(sb);
2716         ext4_group_t i;
2717         int num_meta_group_infos;
2718         struct ext4_group_info *grinfo, ***group_info;
2719         struct ext4_sb_info *sbi = EXT4_SB(sb);
2720         struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2721 
2722         if (sbi->s_group_info) {
2723                 for (i = 0; i < ngroups; i++) {
2724                         cond_resched();
2725                         grinfo = ext4_get_group_info(sb, i);
2726 #ifdef DOUBLE_CHECK
2727                         kfree(grinfo->bb_bitmap);
2728 #endif
2729                         ext4_lock_group(sb, i);
2730                         ext4_mb_cleanup_pa(grinfo);
2731                         ext4_unlock_group(sb, i);
2732                         kmem_cache_free(cachep, grinfo);
2733                 }
2734                 num_meta_group_infos = (ngroups +
2735                                 EXT4_DESC_PER_BLOCK(sb) - 1) >>
2736                         EXT4_DESC_PER_BLOCK_BITS(sb);
2737                 rcu_read_lock();
2738                 group_info = rcu_dereference(sbi->s_group_info);
2739                 for (i = 0; i < num_meta_group_infos; i++)
2740                         kfree(group_info[i]);
2741                 kvfree(group_info);
2742                 rcu_read_unlock();
2743         }
2744         kfree(sbi->s_mb_offsets);
2745         kfree(sbi->s_mb_maxs);
2746         iput(sbi->s_buddy_cache);
2747         if (sbi->s_mb_stats) {
2748                 ext4_msg(sb, KERN_INFO,
2749                        "mballoc: %u blocks %u reqs (%u success)",
2750                                 atomic_read(&sbi->s_bal_allocated),
2751                                 atomic_read(&sbi->s_bal_reqs),
2752                                 atomic_read(&sbi->s_bal_success));
2753                 ext4_msg(sb, KERN_INFO,
2754                       "mballoc: %u extents scanned, %u goal hits, "
2755                                 "%u 2^N hits, %u breaks, %u lost",
2756                                 atomic_read(&sbi->s_bal_ex_scanned),
2757                                 atomic_read(&sbi->s_bal_goals),
2758                                 atomic_read(&sbi->s_bal_2orders),
2759                                 atomic_read(&sbi->s_bal_breaks),
2760                                 atomic_read(&sbi->s_mb_lost_chunks));
2761                 ext4_msg(sb, KERN_INFO,
2762                        "mballoc: %lu generated and it took %Lu",
2763                                 sbi->s_mb_buddies_generated,
2764                                 sbi->s_mb_generation_time);
2765                 ext4_msg(sb, KERN_INFO,
2766                        "mballoc: %u preallocated, %u discarded",
2767                                 atomic_read(&sbi->s_mb_preallocated),
2768                                 atomic_read(&sbi->s_mb_discarded));
2769         }
2770 
2771         free_percpu(sbi->s_locality_groups);
2772 
2773         return 0;
2774 }
2775 
2776 static inline int ext4_issue_discard(struct super_block *sb,
2777                 ext4_group_t block_group, ext4_grpblk_t cluster, int count,
2778                 struct bio **biop)
2779 {
2780         ext4_fsblk_t discard_block;
2781 
2782         discard_block = (EXT4_C2B(EXT4_SB(sb), cluster) +
2783                          ext4_group_first_block_no(sb, block_group));
2784         count = EXT4_C2B(EXT4_SB(sb), count);
2785         trace_ext4_discard_blocks(sb,
2786                         (unsigned long long) discard_block, count);
2787         if (biop) {
2788                 return __blkdev_issue_discard(sb->s_bdev,
2789                         (sector_t)discard_block << (sb->s_blocksize_bits - 9),
2790                         (sector_t)count << (sb->s_blocksize_bits - 9),
2791                         GFP_NOFS, 0, biop);
2792         } else
2793                 return sb_issue_discard(sb, discard_block, count, GFP_NOFS, 0);
2794 }
2795 
2796 static void ext4_free_data_in_buddy(struct super_block *sb,
2797                                     struct ext4_free_data *entry)
2798 {
2799         struct ext4_buddy e4b;
2800         struct ext4_group_info *db;
2801         int err, count = 0, count2 = 0;
2802 
2803         mb_debug(1, "gonna free %u blocks in group %u (0x%p):",
2804                  entry->efd_count, entry->efd_group, entry);
2805 
2806         err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b);
2807         /* we expect to find existing buddy because it's pinned */
2808         BUG_ON(err != 0);
2809 
2810         spin_lock(&EXT4_SB(sb)->s_md_lock);
2811         EXT4_SB(sb)->s_mb_free_pending -= entry->efd_count;
2812         spin_unlock(&EXT4_SB(sb)->s_md_lock);
2813 
2814         db = e4b.bd_info;
2815         /* there are blocks to put in buddy to make them really free */
2816         count += entry->efd_count;
2817         count2++;
2818         ext4_lock_group(sb, entry->efd_group);
2819         /* Take it out of per group rb tree */
2820         rb_erase(&entry->efd_node, &(db->bb_free_root));
2821         mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count);
2822 
2823         /*
2824          * Clear the trimmed flag for the group so that the next
2825          * ext4_trim_fs can trim it.
2826          * If the volume is mounted with -o discard, online discard
2827          * is supported and the free blocks will be trimmed online.
2828          */
2829         if (!test_opt(sb, DISCARD))
2830                 EXT4_MB_GRP_CLEAR_TRIMMED(db);
2831 
2832         if (!db->bb_free_root.rb_node) {
2833                 /* No more items in the per group rb tree
2834                  * balance refcounts from ext4_mb_free_metadata()
2835                  */
2836                 put_page(e4b.bd_buddy_page);
2837                 put_page(e4b.bd_bitmap_page);
2838         }
2839         ext4_unlock_group(sb, entry->efd_group);
2840         kmem_cache_free(ext4_free_data_cachep, entry);
2841         ext4_mb_unload_buddy(&e4b);
2842 
2843         mb_debug(1, "freed %u blocks in %u structures\n", count, count2);
2844 }
2845 
2846 /*
2847  * This function is called by the jbd2 layer once the commit has finished,
2848  * so we know we can free the blocks that were released with that commit.
2849  */
2850 void ext4_process_freed_data(struct super_block *sb, tid_t commit_tid)
2851 {
2852         struct ext4_sb_info *sbi = EXT4_SB(sb);
2853         struct ext4_free_data *entry, *tmp;
2854         struct bio *discard_bio = NULL;
2855         struct list_head freed_data_list;
2856         struct list_head *cut_pos = NULL;
2857         int err;
2858 
2859         INIT_LIST_HEAD(&freed_data_list);
2860 
2861         spin_lock(&sbi->s_md_lock);
2862         list_for_each_entry(entry, &sbi->s_freed_data_list, efd_list) {
2863                 if (entry->efd_tid != commit_tid)
2864                         break;
2865                 cut_pos = &entry->efd_list;
2866         }
2867         if (cut_pos)
2868                 list_cut_position(&freed_data_list, &sbi->s_freed_data_list,
2869                                   cut_pos);
2870         spin_unlock(&sbi->s_md_lock);
2871 
2872         if (test_opt(sb, DISCARD)) {
2873                 list_for_each_entry(entry, &freed_data_list, efd_list) {
2874                         err = ext4_issue_discard(sb, entry->efd_group,
2875                                                  entry->efd_start_cluster,
2876                                                  entry->efd_count,
2877                                                  &discard_bio);
2878                         if (err && err != -EOPNOTSUPP) {
2879                                 ext4_msg(sb, KERN_WARNING, "discard request in"
2880                                          " group:%d block:%d count:%d failed"
2881                                          " with %d", entry->efd_group,
2882                                          entry->efd_start_cluster,
2883                                          entry->efd_count, err);
2884                         } else if (err == -EOPNOTSUPP)
2885                                 break;
2886                 }
2887 
2888                 if (discard_bio) {
2889                         submit_bio_wait(discard_bio);
2890                         bio_put(discard_bio);
2891                 }
2892         }
2893 
2894         list_for_each_entry_safe(entry, tmp, &freed_data_list, efd_list)
2895                 ext4_free_data_in_buddy(sb, entry);
2896 }
2897 
2898 int __init ext4_init_mballoc(void)
2899 {
2900         ext4_pspace_cachep = KMEM_CACHE(ext4_prealloc_space,
2901                                         SLAB_RECLAIM_ACCOUNT);
2902         if (ext4_pspace_cachep == NULL)
2903                 return -ENOMEM;
2904 
2905         ext4_ac_cachep = KMEM_CACHE(ext4_allocation_context,
2906                                     SLAB_RECLAIM_ACCOUNT);
2907         if (ext4_ac_cachep == NULL) {
2908                 kmem_cache_destroy(ext4_pspace_cachep);
2909                 return -ENOMEM;
2910         }
2911 
2912         ext4_free_data_cachep = KMEM_CACHE(ext4_free_data,
2913                                            SLAB_RECLAIM_ACCOUNT);
2914         if (ext4_free_data_cachep == NULL) {
2915                 kmem_cache_destroy(ext4_pspace_cachep);
2916                 kmem_cache_destroy(ext4_ac_cachep);
2917                 return -ENOMEM;
2918         }
2919         return 0;
2920 }
2921 
2922 void ext4_exit_mballoc(void)
2923 {
2924         /*
2925          * Wait for completion of call_rcu()'s on ext4_pspace_cachep
2926          * before destroying the slab cache.
2927          */
2928         rcu_barrier();
2929         kmem_cache_destroy(ext4_pspace_cachep);
2930         kmem_cache_destroy(ext4_ac_cachep);
2931         kmem_cache_destroy(ext4_free_data_cachep);
2932         ext4_groupinfo_destroy_slabs();
2933 }
2934 
2935 
2936 /*
2937  * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
2938  * Returns 0 if success or error code
2939  */
2940 static noinline_for_stack int
2941 ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
2942                                 handle_t *handle, unsigned int reserv_clstrs)
2943 {
2944         struct buffer_head *bitmap_bh = NULL;
2945         struct ext4_group_desc *gdp;
2946         struct buffer_head *gdp_bh;
2947         struct ext4_sb_info *sbi;
2948         struct super_block *sb;
2949         ext4_fsblk_t block;
2950         int err, len;
2951 
2952         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
2953         BUG_ON(ac->ac_b_ex.fe_len <= 0);
2954 
2955         sb = ac->ac_sb;
2956         sbi = EXT4_SB(sb);
2957 
2958         bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);
2959         if (IS_ERR(bitmap_bh)) {
2960                 err = PTR_ERR(bitmap_bh);
2961                 bitmap_bh = NULL;
2962                 goto out_err;
2963         }
2964 
2965         BUFFER_TRACE(bitmap_bh, "getting write access");
2966         err = ext4_journal_get_write_access(handle, bitmap_bh);
2967         if (err)
2968                 goto out_err;
2969 
2970         err = -EIO;
2971         gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);
2972         if (!gdp)
2973                 goto out_err;
2974 
2975         ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,
2976                         ext4_free_group_clusters(sb, gdp));
2977 
2978         BUFFER_TRACE(gdp_bh, "get_write_access");
2979         err = ext4_journal_get_write_access(handle, gdp_bh);
2980         if (err)
2981                 goto out_err;
2982 
2983         block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
2984 
2985         len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
2986         if (!ext4_data_block_valid(sbi, block, len)) {
2987                 ext4_error(sb, "Allocating blocks %llu-%llu which overlap "
2988                            "fs metadata", block, block+len);
2989                 /* File system mounted not to panic on error
2990                  * Fix the bitmap and return EFSCORRUPTED
2991                  * We leak some of the blocks here.
2992                  */
2993                 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
2994                 ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
2995                               ac->ac_b_ex.fe_len);
2996                 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
2997                 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
2998                 if (!err)
2999                         err = -EFSCORRUPTED;
3000                 goto out_err;
3001         }
3002 
3003         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3004 #ifdef AGGRESSIVE_CHECK
3005         {
3006                 int i;
3007                 for (i = 0; i < ac->ac_b_ex.fe_len; i++) {
3008                         BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,
3009                                                 bitmap_bh->b_data));
3010                 }
3011         }
3012 #endif
3013         ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
3014                       ac->ac_b_ex.fe_len);
3015         if (ext4_has_group_desc_csum(sb) &&
3016             (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
3017                 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
3018                 ext4_free_group_clusters_set(sb, gdp,
3019                                              ext4_free_clusters_after_init(sb,
3020                                                 ac->ac_b_ex.fe_group, gdp));
3021         }
3022         len = ext4_free_group_clusters(sb, gdp) - ac->ac_b_ex.fe_len;
3023         ext4_free_group_clusters_set(sb, gdp, len);
3024         ext4_block_bitmap_csum_set(sb, ac->ac_b_ex.fe_group, gdp, bitmap_bh);
3025         ext4_group_desc_csum_set(sb, ac->ac_b_ex.fe_group, gdp);
3026 
3027         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3028         percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);
3029         /*
3030          * Now reduce the dirty block count also. Should not go negative
3031          */
3032         if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
3033                 /* release all the reserved blocks if non delalloc */
3034                 percpu_counter_sub(&sbi->s_dirtyclusters_counter,
3035                                    reserv_clstrs);
3036 
3037         if (sbi->s_log_groups_per_flex) {
3038                 ext4_group_t flex_group = ext4_flex_group(sbi,
3039                                                           ac->ac_b_ex.fe_group);
3040                 atomic64_sub(ac->ac_b_ex.fe_len,
3041                              &sbi_array_rcu_deref(sbi, s_flex_groups,
3042                                                   flex_group)->free_clusters);
3043         }
3044 
3045         err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
3046         if (err)
3047                 goto out_err;
3048         err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);
3049 
3050 out_err:
3051         brelse(bitmap_bh);
3052         return err;
3053 }
3054 
3055 /*
3056  * here we normalize request for locality group
3057  * Group request are normalized to s_mb_group_prealloc, which goes to
3058  * s_strip if we set the same via mount option.
3059  * s_mb_group_prealloc can be configured via
3060  * /sys/fs/ext4/<partition>/mb_group_prealloc
3061  *
3062  * XXX: should we try to preallocate more than the group has now?
3063  */
3064 static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
3065 {
3066         struct super_block *sb = ac->ac_sb;
3067         struct ext4_locality_group *lg = ac->ac_lg;
3068 
3069         BUG_ON(lg == NULL);
3070         ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
3071         mb_debug(1, "#%u: goal %u blocks for locality group\n",
3072                 current->pid, ac->ac_g_ex.fe_len);
3073 }
3074 
3075 /*
3076  * Normalization means making request better in terms of
3077  * size and alignment
3078  */
3079 static noinline_for_stack void
3080 ext4_mb_normalize_request(struct ext4_allocation_context *ac,
3081                                 struct ext4_allocation_request *ar)
3082 {
3083         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3084         int bsbits, max;
3085         ext4_lblk_t end;
3086         loff_t size, start_off;
3087         loff_t orig_size __maybe_unused;
3088         ext4_lblk_t start;
3089         struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3090         struct ext4_prealloc_space *pa;
3091 
3092         /* do normalize only data requests, metadata requests
3093            do not need preallocation */
3094         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3095                 return;
3096 
3097         /* sometime caller may want exact blocks */
3098         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
3099                 return;
3100 
3101         /* caller may indicate that preallocation isn't
3102          * required (it's a tail, for example) */
3103         if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
3104                 return;
3105 
3106         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
3107                 ext4_mb_normalize_group_request(ac);
3108                 return ;
3109         }
3110 
3111         bsbits = ac->ac_sb->s_blocksize_bits;
3112 
3113         /* first, let's learn actual file size
3114          * given current request is allocated */
3115         size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
3116         size = size << bsbits;
3117         if (size < i_size_read(ac->ac_inode))
3118                 size = i_size_read(ac->ac_inode);
3119         orig_size = size;
3120 
3121         /* max size of free chunks */
3122         max = 2 << bsbits;
3123 
3124 #define NRL_CHECK_SIZE(req, size, max, chunk_size)      \
3125                 (req <= (size) || max <= (chunk_size))
3126 
3127         /* first, try to predict filesize */
3128         /* XXX: should this table be tunable? */
3129         start_off = 0;
3130         if (size <= 16 * 1024) {
3131                 size = 16 * 1024;
3132         } else if (size <= 32 * 1024) {
3133                 size = 32 * 1024;
3134         } else if (size <= 64 * 1024) {
3135                 size = 64 * 1024;
3136         } else if (size <= 128 * 1024) {
3137                 size = 128 * 1024;
3138         } else if (size <= 256 * 1024) {
3139                 size = 256 * 1024;
3140         } else if (size <= 512 * 1024) {
3141                 size = 512 * 1024;
3142         } else if (size <= 1024 * 1024) {
3143                 size = 1024 * 1024;
3144         } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
3145                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
3146                                                 (21 - bsbits)) << 21;
3147                 size = 2 * 1024 * 1024;
3148         } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
3149                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
3150                                                         (22 - bsbits)) << 22;
3151                 size = 4 * 1024 * 1024;
3152         } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
3153                                         (8<<20)>>bsbits, max, 8 * 1024)) {
3154                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
3155                                                         (23 - bsbits)) << 23;
3156                 size = 8 * 1024 * 1024;
3157         } else {
3158                 start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;
3159                 size      = (loff_t) EXT4_C2B(EXT4_SB(ac->ac_sb),
3160                                               ac->ac_o_ex.fe_len) << bsbits;
3161         }
3162         size = size >> bsbits;
3163         start = start_off >> bsbits;
3164 
3165         /* don't cover already allocated blocks in selected range */
3166         if (ar->pleft && start <= ar->lleft) {
3167                 size -= ar->lleft + 1 - start;
3168                 start = ar->lleft + 1;
3169         }
3170         if (ar->pright && start + size - 1 >= ar->lright)
3171                 size -= start + size - ar->lright;
3172 
3173         /*
3174          * Trim allocation request for filesystems with artificially small
3175          * groups.
3176          */
3177         if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))
3178                 size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);
3179 
3180         end = start + size;
3181 
3182         /* check we don't cross already preallocated blocks */
3183         rcu_read_lock();
3184         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3185                 ext4_lblk_t pa_end;
3186 
3187                 if (pa->pa_deleted)
3188                         continue;
3189                 spin_lock(&pa->pa_lock);
3190                 if (pa->pa_deleted) {
3191                         spin_unlock(&pa->pa_lock);
3192                         continue;
3193                 }
3194 
3195                 pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
3196                                                   pa->pa_len);
3197 
3198                 /* PA must not overlap original request */
3199                 BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
3200                         ac->ac_o_ex.fe_logical < pa->pa_lstart));
3201 
3202                 /* skip PAs this normalized request doesn't overlap with */
3203                 if (pa->pa_lstart >= end || pa_end <= start) {
3204                         spin_unlock(&pa->pa_lock);
3205                         continue;
3206                 }
3207                 BUG_ON(pa->pa_lstart <= start && pa_end >= end);
3208 
3209                 /* adjust start or end to be adjacent to this pa */
3210                 if (pa_end <= ac->ac_o_ex.fe_logical) {
3211                         BUG_ON(pa_end < start);
3212                         start = pa_end;
3213                 } else if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
3214                         BUG_ON(pa->pa_lstart > end);
3215                         end = pa->pa_lstart;
3216                 }
3217                 spin_unlock(&pa->pa_lock);
3218         }
3219         rcu_read_unlock();
3220         size = end - start;
3221 
3222         /* XXX: extra loop to check we really don't overlap preallocations */
3223         rcu_read_lock();
3224         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3225                 ext4_lblk_t pa_end;
3226 
3227                 spin_lock(&pa->pa_lock);
3228                 if (pa->pa_deleted == 0) {
3229                         pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
3230                                                           pa->pa_len);
3231                         BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
3232                 }
3233                 spin_unlock(&pa->pa_lock);
3234         }
3235         rcu_read_unlock();
3236 
3237         if (start + size <= ac->ac_o_ex.fe_logical &&
3238                         start > ac->ac_o_ex.fe_logical) {
3239                 ext4_msg(ac->ac_sb, KERN_ERR,
3240                          "start %lu, size %lu, fe_logical %lu",
3241                          (unsigned long) start, (unsigned long) size,
3242                          (unsigned long) ac->ac_o_ex.fe_logical);
3243                 BUG();
3244         }
3245         BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
3246 
3247         /* now prepare goal request */
3248 
3249         /* XXX: is it better to align blocks WRT to logical
3250          * placement or satisfy big request as is */
3251         ac->ac_g_ex.fe_logical = start;
3252         ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);
3253 
3254         /* define goal start in order to merge */
3255         if (ar->pright && (ar->lright == (start + size))) {
3256                 /* merge to the right */
3257                 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
3258                                                 &ac->ac_f_ex.fe_group,
3259                                                 &ac->ac_f_ex.fe_start);
3260                 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3261         }
3262         if (ar->pleft && (ar->lleft + 1 == start)) {
3263                 /* merge to the left */
3264                 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
3265                                                 &ac->ac_f_ex.fe_group,
3266                                                 &ac->ac_f_ex.fe_start);
3267                 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3268         }
3269 
3270         mb_debug(1, "goal: %u(was %u) blocks at %u\n", (unsigned) size,
3271                 (unsigned) orig_size, (unsigned) start);
3272 }
3273 
3274 static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
3275 {
3276         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3277 
3278         if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
3279                 atomic_inc(&sbi->s_bal_reqs);
3280                 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
3281                 if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
3282                         atomic_inc(&sbi->s_bal_success);
3283                 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
3284                 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
3285                                 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
3286                         atomic_inc(&sbi->s_bal_goals);
3287                 if (ac->ac_found > sbi->s_mb_max_to_scan)
3288                         atomic_inc(&sbi->s_bal_breaks);
3289         }
3290 
3291         if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)
3292                 trace_ext4_mballoc_alloc(ac);
3293         else
3294                 trace_ext4_mballoc_prealloc(ac);
3295 }
3296 
3297 /*
3298  * Called on failure; free up any blocks from the inode PA for this
3299  * context.  We don't need this for MB_GROUP_PA because we only change
3300  * pa_free in ext4_mb_release_context(), but on failure, we've already
3301  * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
3302  */
3303 static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac)
3304 {
3305         struct ext4_prealloc_space *pa = ac->ac_pa;
3306         struct ext4_buddy e4b;
3307         int err;
3308 
3309         if (pa == NULL) {
3310                 if (ac->ac_f_ex.fe_len == 0)
3311                         return;
3312                 err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);
3313                 if (err) {
3314                         /*
3315                          * This should never happen since we pin the
3316                          * pages in the ext4_allocation_context so
3317                          * ext4_mb_load_buddy() should never fail.
3318                          */
3319                         WARN(1, "mb_load_buddy failed (%d)", err);
3320                         return;
3321                 }
3322                 ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
3323                 mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,
3324                                ac->ac_f_ex.fe_len);
3325                 ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
3326                 ext4_mb_unload_buddy(&e4b);
3327                 return;
3328         }
3329         if (pa->pa_type == MB_INODE_PA)
3330                 pa->pa_free += ac->ac_b_ex.fe_len;
3331 }
3332 
3333 /*
3334  * use blocks preallocated to inode
3335  */
3336 static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
3337                                 struct ext4_prealloc_space *pa)
3338 {
3339         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3340         ext4_fsblk_t start;
3341         ext4_fsblk_t end;
3342         int len;
3343 
3344         /* found preallocated blocks, use them */
3345         start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
3346         end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),
3347                   start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));
3348         len = EXT4_NUM_B2C(sbi, end - start);
3349         ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
3350                                         &ac->ac_b_ex.fe_start);
3351         ac->ac_b_ex.fe_len = len;
3352         ac->ac_status = AC_STATUS_FOUND;
3353         ac->ac_pa = pa;
3354 
3355         BUG_ON(start < pa->pa_pstart);
3356         BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));
3357         BUG_ON(pa->pa_free < len);
3358         pa->pa_free -= len;
3359 
3360         mb_debug(1, "use %llu/%u from inode pa %p\n", start, len, pa);
3361 }
3362 
3363 /*
3364  * use blocks preallocated to locality group
3365  */
3366 static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
3367                                 struct ext4_prealloc_space *pa)
3368 {
3369         unsigned int len = ac->ac_o_ex.fe_len;
3370 
3371         ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
3372                                         &ac->ac_b_ex.fe_group,
3373                                         &ac->ac_b_ex.fe_start);
3374         ac->ac_b_ex.fe_len = len;
3375         ac->ac_status = AC_STATUS_FOUND;
3376         ac->ac_pa = pa;
3377 
3378         /* we don't correct pa_pstart or pa_plen here to avoid
3379          * possible race when the group is being loaded concurrently
3380          * instead we correct pa later, after blocks are marked
3381          * in on-disk bitmap -- see ext4_mb_release_context()
3382          * Other CPUs are prevented from allocating from this pa by lg_mutex
3383          */
3384         mb_debug(1, "use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
3385 }
3386 
3387 /*
3388  * Return the prealloc space that have minimal distance
3389  * from the goal block. @cpa is the prealloc
3390  * space that is having currently known minimal distance
3391  * from the goal block.
3392  */
3393 static struct ext4_prealloc_space *
3394 ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
3395                         struct ext4_prealloc_space *pa,
3396                         struct ext4_prealloc_space *cpa)
3397 {
3398         ext4_fsblk_t cur_distance, new_distance;
3399 
3400         if (cpa == NULL) {
3401                 atomic_inc(&pa->pa_count);
3402                 return pa;
3403         }
3404         cur_distance = abs(goal_block - cpa->pa_pstart);
3405         new_distance = abs(goal_block - pa->pa_pstart);
3406 
3407         if (cur_distance <= new_distance)
3408                 return cpa;
3409 
3410         /* drop the previous reference */
3411         atomic_dec(&cpa->pa_count);
3412         atomic_inc(&pa->pa_count);
3413         return pa;
3414 }
3415 
3416 /*
3417  * search goal blocks in preallocated space
3418  */
3419 static noinline_for_stack int
3420 ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
3421 {
3422         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3423         int order, i;
3424         struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3425         struct ext4_locality_group *lg;
3426         struct ext4_prealloc_space *pa, *cpa = NULL;
3427         ext4_fsblk_t goal_block;
3428 
3429         /* only data can be preallocated */
3430         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3431                 return 0;
3432 
3433         /* first, try per-file preallocation */
3434         rcu_read_lock();
3435         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3436 
3437                 /* all fields in this condition don't change,
3438                  * so we can skip locking for them */
3439                 if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
3440                     ac->ac_o_ex.fe_logical >= (pa->pa_lstart +
3441                                                EXT4_C2B(sbi, pa->pa_len)))
3442                         continue;
3443 
3444                 /* non-extent files can't have physical blocks past 2^32 */
3445                 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&
3446                     (pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len) >
3447                      EXT4_MAX_BLOCK_FILE_PHYS))
3448                         continue;
3449 
3450                 /* found preallocated blocks, use them */
3451                 spin_lock(&pa->pa_lock);
3452                 if (pa->pa_deleted == 0 && pa->pa_free) {
3453                         atomic_inc(&pa->pa_count);
3454                         ext4_mb_use_inode_pa(ac, pa);
3455                         spin_unlock(&pa->pa_lock);
3456                         ac->ac_criteria = 10;
3457                         rcu_read_unlock();
3458                         return 1;
3459                 }
3460                 spin_unlock(&pa->pa_lock);
3461         }
3462         rcu_read_unlock();
3463 
3464         /* can we use group allocation? */
3465         if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
3466                 return 0;
3467 
3468         /* inode may have no locality group for some reason */
3469         lg = ac->ac_lg;
3470         if (lg == NULL)
3471                 return 0;
3472         order  = fls(ac->ac_o_ex.fe_len) - 1;
3473         if (order > PREALLOC_TB_SIZE - 1)
3474                 /* The max size of hash table is PREALLOC_TB_SIZE */
3475                 order = PREALLOC_TB_SIZE - 1;
3476 
3477         goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);
3478         /*
3479          * search for the prealloc space that is having
3480          * minimal distance from the goal block.
3481          */
3482         for (i = order; i < PREALLOC_TB_SIZE; i++) {
3483                 rcu_read_lock();
3484                 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],
3485                                         pa_inode_list) {
3486                         spin_lock(&pa->pa_lock);
3487                         if (pa->pa_deleted == 0 &&
3488                                         pa->pa_free >= ac->ac_o_ex.fe_len) {
3489 
3490                                 cpa = ext4_mb_check_group_pa(goal_block,
3491                                                                 pa, cpa);
3492                         }
3493                         spin_unlock(&pa->pa_lock);
3494                 }
3495                 rcu_read_unlock();
3496         }
3497         if (cpa) {
3498                 ext4_mb_use_group_pa(ac, cpa);
3499                 ac->ac_criteria = 20;
3500                 return 1;
3501         }
3502         return 0;
3503 }
3504 
3505 /*
3506  * the function goes through all block freed in the group
3507  * but not yet committed and marks them used in in-core bitmap.
3508  * buddy must be generated from this bitmap
3509  * Need to be called with the ext4 group lock held
3510  */
3511 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
3512                                                 ext4_group_t group)
3513 {
3514         struct rb_node *n;
3515         struct ext4_group_info *grp;
3516         struct ext4_free_data *entry;
3517 
3518         grp = ext4_get_group_info(sb, group);
3519         n = rb_first(&(grp->bb_free_root));
3520 
3521         while (n) {
3522                 entry = rb_entry(n, struct ext4_free_data, efd_node);
3523                 ext4_set_bits(bitmap, entry->efd_start_cluster, entry->efd_count);
3524                 n = rb_next(n);
3525         }
3526         return;
3527 }
3528 
3529 /*
3530  * the function goes through all preallocation in this group and marks them
3531  * used in in-core bitmap. buddy must be generated from this bitmap
3532  * Need to be called with ext4 group lock held
3533  */
3534 static noinline_for_stack
3535 void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
3536                                         ext4_group_t group)
3537 {
3538         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3539         struct ext4_prealloc_space *pa;
3540         struct list_head *cur;
3541         ext4_group_t groupnr;
3542         ext4_grpblk_t start;
3543         int preallocated = 0;
3544         int len;
3545 
3546         /* all form of preallocation discards first load group,
3547          * so the only competing code is preallocation use.
3548          * we don't need any locking here
3549          * notice we do NOT ignore preallocations with pa_deleted
3550          * otherwise we could leave used blocks available for
3551          * allocation in buddy when concurrent ext4_mb_put_pa()
3552          * is dropping preallocation
3553          */
3554         list_for_each(cur, &grp->bb_prealloc_list) {
3555                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
3556                 spin_lock(&pa->pa_lock);
3557                 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3558                                              &groupnr, &start);
3559                 len = pa->pa_len;
3560                 spin_unlock(&pa->pa_lock);
3561                 if (unlikely(len == 0))
3562                         continue;
3563                 BUG_ON(groupnr != group);
3564                 ext4_set_bits(bitmap, start, len);
3565                 preallocated += len;
3566         }
3567         mb_debug(1, "preallocated %u for group %u\n", preallocated, group);
3568 }
3569 
3570 static void ext4_mb_pa_callback(struct rcu_head *head)
3571 {
3572         struct ext4_prealloc_space *pa;
3573         pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
3574 
3575         BUG_ON(atomic_read(&pa->pa_count));
3576         BUG_ON(pa->pa_deleted == 0);
3577         kmem_cache_free(ext4_pspace_cachep, pa);
3578 }
3579 
3580 /*
3581  * drops a reference to preallocated space descriptor
3582  * if this was the last reference and the space is consumed
3583  */
3584 static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
3585                         struct super_block *sb, struct ext4_prealloc_space *pa)
3586 {
3587         ext4_group_t grp;
3588         ext4_fsblk_t grp_blk;
3589 
3590         /* in this short window concurrent discard can set pa_deleted */
3591         spin_lock(&pa->pa_lock);
3592         if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {
3593                 spin_unlock(&pa->pa_lock);
3594                 return;
3595         }
3596 
3597         if (pa->pa_deleted == 1) {
3598                 spin_unlock(&pa->pa_lock);
3599                 return;
3600         }
3601 
3602         pa->pa_deleted = 1;
3603         spin_unlock(&pa->pa_lock);
3604 
3605         grp_blk = pa->pa_pstart;
3606         /*
3607          * If doing group-based preallocation, pa_pstart may be in the
3608          * next group when pa is used up
3609          */
3610         if (pa->pa_type == MB_GROUP_PA)
3611                 grp_blk--;
3612 
3613         grp = ext4_get_group_number(sb, grp_blk);
3614 
3615         /*
3616          * possible race:
3617          *
3618          *  P1 (buddy init)                     P2 (regular allocation)
3619          *                                      find block B in PA
3620          *  copy on-disk bitmap to buddy
3621          *                                      mark B in on-disk bitmap
3622          *                                      drop PA from group
3623          *  mark all PAs in buddy
3624          *
3625          * thus, P1 initializes buddy with B available. to prevent this
3626          * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
3627          * against that pair
3628          */
3629         ext4_lock_group(sb, grp);
3630         list_del(&pa->pa_group_list);
3631         ext4_unlock_group(sb, grp);
3632 
3633         spin_lock(pa->pa_obj_lock);
3634         list_del_rcu(&pa->pa_inode_list);
3635         spin_unlock(pa->pa_obj_lock);
3636 
3637         call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3638 }
3639 
3640 /*
3641  * creates new preallocated space for given inode
3642  */
3643 static noinline_for_stack int
3644 ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
3645 {
3646         struct super_block *sb = ac->ac_sb;
3647         struct ext4_sb_info *sbi = EXT4_SB(sb);
3648         struct ext4_prealloc_space *pa;
3649         struct ext4_group_info *grp;
3650         struct ext4_inode_info *ei;
3651 
3652         /* preallocate only when found space is larger then requested */
3653         BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3654         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3655         BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3656 
3657         pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3658         if (pa == NULL)
3659                 return -ENOMEM;
3660 
3661         if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
3662                 int winl;
3663                 int wins;
3664                 int win;
3665                 int offs;
3666 
3667                 /* we can't allocate as much as normalizer wants.
3668                  * so, found space must get proper lstart
3669                  * to cover original request */
3670                 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
3671                 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
3672 
3673                 /* we're limited by original request in that
3674                  * logical block must be covered any way
3675                  * winl is window we can move our chunk within */
3676                 winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;
3677 
3678                 /* also, we should cover whole original request */
3679                 wins = EXT4_C2B(sbi, ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len);
3680 
3681                 /* the smallest one defines real window */
3682                 win = min(winl, wins);
3683 
3684                 offs = ac->ac_o_ex.fe_logical %
3685                         EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
3686                 if (offs && offs < win)
3687                         win = offs;
3688 
3689                 ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical -
3690                         EXT4_NUM_B2C(sbi, win);
3691                 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
3692                 BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
3693         }
3694 
3695         /* preallocation can change ac_b_ex, thus we store actually
3696          * allocated blocks for history */
3697         ac->ac_f_ex = ac->ac_b_ex;
3698 
3699         pa->pa_lstart = ac->ac_b_ex.fe_logical;
3700         pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3701         pa->pa_len = ac->ac_b_ex.fe_len;
3702         pa->pa_free = pa->pa_len;
3703         atomic_set(&pa->pa_count, 1);
3704         spin_lock_init(&pa->pa_lock);
3705         INIT_LIST_HEAD(&pa->pa_inode_list);
3706         INIT_LIST_HEAD(&pa->pa_group_list);
3707         pa->pa_deleted = 0;
3708         pa->pa_type = MB_INODE_PA;
3709 
3710         mb_debug(1, "new inode pa %p: %llu/%u for %u\n", pa,
3711                         pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3712         trace_ext4_mb_new_inode_pa(ac, pa);
3713 
3714         ext4_mb_use_inode_pa(ac, pa);
3715         atomic_add(pa->pa_free, &sbi->s_mb_preallocated);
3716 
3717         ei = EXT4_I(ac->ac_inode);
3718         grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3719 
3720         pa->pa_obj_lock = &ei->i_prealloc_lock;
3721         pa->pa_inode = ac->ac_inode;
3722 
3723         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3724         list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3725         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3726 
3727         spin_lock(pa->pa_obj_lock);
3728         list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
3729         spin_unlock(pa->pa_obj_lock);
3730 
3731         return 0;
3732 }
3733 
3734 /*
3735  * creates new preallocated space for locality group inodes belongs to
3736  */
3737 static noinline_for_stack int
3738 ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
3739 {
3740         struct super_block *sb = ac->ac_sb;
3741         struct ext4_locality_group *lg;
3742         struct ext4_prealloc_space *pa;
3743         struct ext4_group_info *grp;
3744 
3745         /* preallocate only when found space is larger then requested */
3746         BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3747         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3748         BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3749 
3750         BUG_ON(ext4_pspace_cachep == NULL);
3751         pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3752         if (pa == NULL)
3753                 return -ENOMEM;
3754 
3755         /* preallocation can change ac_b_ex, thus we store actually
3756          * allocated blocks for history */
3757         ac->ac_f_ex = ac->ac_b_ex;
3758 
3759         pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3760         pa->pa_lstart = pa->pa_pstart;
3761         pa->pa_len = ac->ac_b_ex.fe_len;
3762         pa->pa_free = pa->pa_len;
3763         atomic_set(&pa->pa_count, 1);
3764         spin_lock_init(&pa->pa_lock);
3765         INIT_LIST_HEAD(&pa->pa_inode_list);
3766         INIT_LIST_HEAD(&pa->pa_group_list);
3767         pa->pa_deleted = 0;
3768         pa->pa_type = MB_GROUP_PA;
3769 
3770         mb_debug(1, "new group pa %p: %llu/%u for %u\n", pa,
3771                         pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3772         trace_ext4_mb_new_group_pa(ac, pa);
3773 
3774         ext4_mb_use_group_pa(ac, pa);
3775         atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3776 
3777         grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3778         lg = ac->ac_lg;
3779         BUG_ON(lg == NULL);
3780 
3781         pa->pa_obj_lock = &lg->lg_prealloc_lock;
3782         pa->pa_inode = NULL;
3783 
3784         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3785         list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3786         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3787 
3788         /*
3789          * We will later add the new pa to the right bucket
3790          * after updating the pa_free in ext4_mb_release_context
3791          */
3792         return 0;
3793 }
3794 
3795 static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
3796 {
3797         int err;
3798 
3799         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
3800                 err = ext4_mb_new_group_pa(ac);
3801         else
3802                 err = ext4_mb_new_inode_pa(ac);
3803         return err;
3804 }
3805 
3806 /*
3807  * finds all unused blocks in on-disk bitmap, frees them in
3808  * in-core bitmap and buddy.
3809  * @pa must be unlinked from inode and group lists, so that
3810  * nobody else can find/use it.
3811  * the caller MUST hold group/inode locks.
3812  * TODO: optimize the case when there are no in-core structures yet
3813  */
3814 static noinline_for_stack int
3815 ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
3816                         struct ext4_prealloc_space *pa)
3817 {
3818         struct super_block *sb = e4b->bd_sb;
3819         struct ext4_sb_info *sbi = EXT4_SB(sb);
3820         unsigned int end;
3821         unsigned int next;
3822         ext4_group_t group;
3823         ext4_grpblk_t bit;
3824         unsigned long long grp_blk_start;
3825         int free = 0;
3826 
3827         BUG_ON(pa->pa_deleted == 0);
3828         ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3829         grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);
3830         BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3831         end = bit + pa->pa_len;
3832 
3833         while (bit < end) {
3834                 bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
3835                 if (bit >= end)
3836                         break;
3837                 next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
3838                 mb_debug(1, "    free preallocated %u/%u in group %u\n",
3839                          (unsigned) ext4_group_first_block_no(sb, group) + bit,
3840                          (unsigned) next - bit, (unsigned) group);
3841                 free += next - bit;
3842 
3843                 trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);
3844                 trace_ext4_mb_release_inode_pa(pa, (grp_blk_start +
3845                                                     EXT4_C2B(sbi, bit)),
3846                                                next - bit);
3847                 mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
3848                 bit = next + 1;
3849         }
3850         if (free != pa->pa_free) {
3851                 ext4_msg(e4b->bd_sb, KERN_CRIT,
3852                          "pa %p: logic %lu, phys. %lu, len %lu",
3853                          pa, (unsigned long) pa->pa_lstart,
3854                          (unsigned long) pa->pa_pstart,
3855                          (unsigned long) pa->pa_len);
3856                 ext4_grp_locked_error(sb, group, 0, 0, "free %u, pa_free %u",
3857                                         free, pa->pa_free);
3858                 /*
3859                  * pa is already deleted so we use the value obtained
3860                  * from the bitmap and continue.
3861                  */
3862         }
3863         atomic_add(free, &sbi->s_mb_discarded);
3864 
3865         return 0;
3866 }
3867 
3868 static noinline_for_stack int
3869 ext4_mb_release_group_pa(struct ext4_buddy *e4b,
3870                                 struct ext4_prealloc_space *pa)
3871 {
3872         struct super_block *sb = e4b->bd_sb;
3873         ext4_group_t group;
3874         ext4_grpblk_t bit;
3875 
3876         trace_ext4_mb_release_group_pa(sb, pa);
3877         BUG_ON(pa->pa_deleted == 0);
3878         ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3879         BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3880         mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
3881         atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
3882         trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);
3883 
3884         return 0;
3885 }
3886 
3887 /*
3888  * releases all preallocations in given group
3889  *
3890  * first, we need to decide discard policy:
3891  * - when do we discard
3892  *   1) ENOSPC
3893  * - how many do we discard
3894  *   1) how many requested
3895  */
3896 static noinline_for_stack int
3897 ext4_mb_discard_group_preallocations(struct super_block *sb,
3898                                         ext4_group_t group, int needed)
3899 {
3900         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3901         struct buffer_head *bitmap_bh = NULL;
3902         struct ext4_prealloc_space *pa, *tmp;
3903         struct list_head list;
3904         struct ext4_buddy e4b;
3905         int err;
3906         int busy = 0;
3907         int free = 0;
3908 
3909         mb_debug(1, "discard preallocation for group %u\n", group);
3910 
3911         if (list_empty(&grp->bb_prealloc_list))
3912                 return 0;
3913 
3914         bitmap_bh = ext4_read_block_bitmap(sb, group);
3915         if (IS_ERR(bitmap_bh)) {
3916                 err = PTR_ERR(bitmap_bh);
3917                 ext4_error(sb, "Error %d reading block bitmap for %u",
3918                            err, group);
3919                 return 0;
3920         }
3921 
3922         err = ext4_mb_load_buddy(sb, group, &e4b);
3923         if (err) {
3924                 ext4_warning(sb, "Error %d loading buddy information for %u",
3925                              err, group);
3926                 put_bh(bitmap_bh);
3927                 return 0;
3928         }
3929 
3930         if (needed == 0)
3931                 needed = EXT4_CLUSTERS_PER_GROUP(sb) + 1;
3932 
3933         INIT_LIST_HEAD(&list);
3934 repeat:
3935         ext4_lock_group(sb, group);
3936         list_for_each_entry_safe(pa, tmp,
3937                                 &grp->bb_prealloc_list, pa_group_list) {
3938                 spin_lock(&pa->pa_lock);
3939                 if (atomic_read(&pa->pa_count)) {
3940                         spin_unlock(&pa->pa_lock);
3941                         busy = 1;
3942                         continue;
3943                 }
3944                 if (pa->pa_deleted) {
3945                         spin_unlock(&pa->pa_lock);
3946                         continue;
3947                 }
3948 
3949                 /* seems this one can be freed ... */
3950                 pa->pa_deleted = 1;
3951 
3952                 /* we can trust pa_free ... */
3953                 free += pa->pa_free;
3954 
3955                 spin_unlock(&pa->pa_lock);
3956 
3957                 list_del(&pa->pa_group_list);
3958                 list_add(&pa->u.pa_tmp_list, &list);
3959         }
3960 
3961         /* if we still need more blocks and some PAs were used, try again */
3962         if (free < needed && busy) {
3963                 busy = 0;
3964                 ext4_unlock_group(sb, group);
3965                 cond_resched();
3966                 goto repeat;
3967         }
3968 
3969         /* found anything to free? */
3970         if (list_empty(&list)) {
3971                 BUG_ON(free != 0);
3972                 goto out;
3973         }
3974 
3975         /* now free all selected PAs */
3976         list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
3977 
3978                 /* remove from object (inode or locality group) */
3979                 spin_lock(pa->pa_obj_lock);
3980                 list_del_rcu(&pa->pa_inode_list);
3981                 spin_unlock(pa->pa_obj_lock);
3982 
3983                 if (pa->pa_type == MB_GROUP_PA)
3984                         ext4_mb_release_group_pa(&e4b, pa);
3985                 else
3986                         ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);
3987 
3988                 list_del(&pa->u.pa_tmp_list);
3989                 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3990         }
3991 
3992 out:
3993         ext4_unlock_group(sb, group);
3994         ext4_mb_unload_buddy(&e4b);
3995         put_bh(bitmap_bh);
3996         return free;
3997 }
3998 
3999 /*
4000  * releases all non-used preallocated blocks for given inode
4001  *
4002  * It's important to discard preallocations under i_data_sem
4003  * We don't want another block to be served from the prealloc
4004  * space when we are discarding the inode prealloc space.
4005  *
4006  * FIXME!! Make sure it is valid at all the call sites
4007  */
4008 void ext4_discard_preallocations(struct inode *inode)
4009 {
4010         struct ext4_inode_info *ei = EXT4_I(inode);
4011         struct super_block *sb = inode->i_sb;
4012         struct buffer_head *bitmap_bh = NULL;
4013         struct ext4_prealloc_space *pa, *tmp;
4014         ext4_group_t group = 0;
4015         struct list_head list;
4016         struct ext4_buddy e4b;
4017         int err;
4018 
4019         if (!S_ISREG(inode->i_mode)) {
4020                 /*BUG_ON(!list_empty(&ei->i_prealloc_list));*/
4021                 return;
4022         }
4023 
4024         mb_debug(1, "discard preallocation for inode %lu\n", inode->i_ino);
4025         trace_ext4_discard_preallocations(inode);
4026 
4027         INIT_LIST_HEAD(&list);
4028 
4029 repeat:
4030         /* first, collect all pa's in the inode */
4031         spin_lock(&ei->i_prealloc_lock);
4032         while (!list_empty(&ei->i_prealloc_list)) {
4033                 pa = list_entry(ei->i_prealloc_list.next,
4034                                 struct ext4_prealloc_space, pa_inode_list);
4035                 BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);
4036                 spin_lock(&pa->pa_lock);
4037                 if (atomic_read(&pa->pa_count)) {
4038                         /* this shouldn't happen often - nobody should
4039                          * use preallocation while we're discarding it */
4040                         spin_unlock(&pa->pa_lock);
4041                         spin_unlock(&ei->i_prealloc_lock);
4042                         ext4_msg(sb, KERN_ERR,
4043                                  "uh-oh! used pa while discarding");
4044                         WARN_ON(1);
4045                         schedule_timeout_uninterruptible(HZ);
4046                         goto repeat;
4047 
4048                 }
4049                 if (pa->pa_deleted == 0) {
4050                         pa->pa_deleted = 1;
4051                         spin_unlock(&pa->pa_lock);
4052                         list_del_rcu(&pa->pa_inode_list);
4053                         list_add(&pa->u.pa_tmp_list, &list);
4054                         continue;
4055                 }
4056 
4057                 /* someone is deleting pa right now */
4058                 spin_unlock(&pa->pa_lock);
4059                 spin_unlock(&ei->i_prealloc_lock);
4060 
4061                 /* we have to wait here because pa_deleted
4062                  * doesn't mean pa is already unlinked from
4063                  * the list. as we might be called from
4064                  * ->clear_inode() the inode will get freed
4065                  * and concurrent thread which is unlinking
4066                  * pa from inode's list may access already
4067                  * freed memory, bad-bad-bad */
4068 
4069                 /* XXX: if this happens too often, we can
4070                  * add a flag to force wait only in case
4071                  * of ->clear_inode(), but not in case of
4072                  * regular truncate */
4073                 schedule_timeout_uninterruptible(HZ);
4074                 goto repeat;
4075         }
4076         spin_unlock(&ei->i_prealloc_lock);
4077 
4078         list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
4079                 BUG_ON(pa->pa_type != MB_INODE_PA);
4080                 group = ext4_get_group_number(sb, pa->pa_pstart);
4081 
4082                 err = ext4_mb_load_buddy_gfp(sb, group, &e4b,
4083                                              GFP_NOFS|__GFP_NOFAIL);
4084                 if (err) {
4085                         ext4_error(sb, "Error %d loading buddy information for %u",
4086                                    err, group);
4087                         continue;
4088                 }
4089 
4090                 bitmap_bh = ext4_read_block_bitmap(sb, group);
4091                 if (IS_ERR(bitmap_bh)) {
4092                         err = PTR_ERR(bitmap_bh);
4093                         ext4_error(sb, "Error %d reading block bitmap for %u",
4094                                         err, group);
4095                         ext4_mb_unload_buddy(&e4b);
4096                         continue;
4097                 }
4098 
4099                 ext4_lock_group(sb, group);
4100                 list_del(&pa->pa_group_list);
4101                 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);
4102                 ext4_unlock_group(sb, group);
4103 
4104                 ext4_mb_unload_buddy(&e4b);
4105                 put_bh(bitmap_bh);
4106 
4107                 list_del(&pa->u.pa_tmp_list);
4108                 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
4109         }
4110 }
4111 
4112 #ifdef CONFIG_EXT4_DEBUG
4113 static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
4114 {
4115         struct super_block *sb = ac->ac_sb;
4116         ext4_group_t ngroups, i;
4117 
4118         if (!ext4_mballoc_debug ||
4119             (EXT4_SB(sb)->s_mount_flags & EXT4_MF_FS_ABORTED))
4120                 return;
4121 
4122         ext4_msg(ac->ac_sb, KERN_ERR, "Can't allocate:"
4123                         " Allocation context details:");
4124         ext4_msg(ac->ac_sb, KERN_ERR, "status %d flags %d",
4125                         ac->ac_status, ac->ac_flags);
4126         ext4_msg(ac->ac_sb, KERN_ERR, "orig %lu/%lu/%lu@%lu, "
4127                         "goal %lu/%lu/%lu@%lu, "
4128                         "best %lu/%lu/%lu@%lu cr %d",
4129                         (unsigned long)ac->ac_o_ex.fe_group,
4130                         (unsigned long)ac->ac_o_ex.fe_start,
4131                         (unsigned long)ac->ac_o_ex.fe_len,
4132                         (unsigned long)ac->ac_o_ex.fe_logical,
4133                         (unsigned long)ac->ac_g_ex.fe_group,
4134                         (unsigned long)ac->ac_g_ex.fe_start,
4135                         (unsigned long)ac->ac_g_ex.fe_len,
4136                         (unsigned long)ac->ac_g_ex.fe_logical,
4137                         (unsigned long)ac->ac_b_ex.fe_group,
4138                         (unsigned long)ac->ac_b_ex.fe_start,
4139                         (unsigned long)ac->ac_b_ex.fe_len,
4140                         (unsigned long)ac->ac_b_ex.fe_logical,
4141                         (int)ac->ac_criteria);
4142         ext4_msg(ac->ac_sb, KERN_ERR, "%d found", ac->ac_found);
4143         ext4_msg(ac->ac_sb, KERN_ERR, "groups: ");
4144         ngroups = ext4_get_groups_count(sb);
4145         for (i = 0; i < ngroups; i++) {
4146                 struct ext4_group_info *grp = ext4_get_group_info(sb, i);
4147                 struct ext4_prealloc_space *pa;
4148                 ext4_grpblk_t start;
4149                 struct list_head *cur;
4150                 ext4_lock_group(sb, i);
4151                 list_for_each(cur, &grp->bb_prealloc_list) {
4152                         pa = list_entry(cur, struct ext4_prealloc_space,
4153                                         pa_group_list);
4154                         spin_lock(&pa->pa_lock);
4155                         ext4_get_group_no_and_offset(sb, pa->pa_pstart,
4156                                                      NULL, &start);
4157                         spin_unlock(&pa->pa_lock);
4158                         printk(KERN_ERR "PA:%u:%d:%u \n", i,
4159                                start, pa->pa_len);
4160                 }
4161                 ext4_unlock_group(sb, i);
4162 
4163                 if (grp->bb_free == 0)
4164                         continue;
4165                 printk(KERN_ERR "%u: %d/%d \n",
4166                        i, grp->bb_free, grp->bb_fragments);
4167         }
4168         printk(KERN_ERR "\n");
4169 }
4170 #else
4171 static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
4172 {
4173         return;
4174 }
4175 #endif
4176 
4177 /*
4178  * We use locality group preallocation for small size file. The size of the
4179  * file is determined by the current size or the resulting size after
4180  * allocation which ever is larger
4181  *
4182  * One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req
4183  */
4184 static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
4185 {
4186         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4187         int bsbits = ac->ac_sb->s_blocksize_bits;
4188         loff_t size, isize;
4189 
4190         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
4191                 return;
4192 
4193         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
4194                 return;
4195 
4196         size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
4197         isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)
4198                 >> bsbits;
4199 
4200         if ((size == isize) && !ext4_fs_is_busy(sbi) &&
4201             !inode_is_open_for_write(ac->ac_inode)) {
4202                 ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;
4203                 return;
4204         }
4205 
4206         if (sbi->s_mb_group_prealloc <= 0) {
4207                 ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
4208                 return;
4209         }
4210 
4211         /* don't use group allocation for large files */
4212         size = max(size, isize);
4213         if (size > sbi->s_mb_stream_request) {
4214                 ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
4215                 return;
4216         }
4217 
4218         BUG_ON(ac->ac_lg != NULL);
4219         /*
4220          * locality group prealloc space are per cpu. The reason for having
4221          * per cpu locality group is to reduce the contention between block
4222          * request from multiple CPUs.
4223          */
4224         ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);
4225 
4226         /* we're going to use group allocation */
4227         ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
4228 
4229         /* serialize all allocations in the group */
4230         mutex_lock(&ac->ac_lg->lg_mutex);
4231 }
4232 
4233 static noinline_for_stack int
4234 ext4_mb_initialize_context(struct ext4_allocation_context *ac,
4235                                 struct ext4_allocation_request *ar)
4236 {
4237         struct super_block *sb = ar->inode->i_sb;
4238         struct ext4_sb_info *sbi = EXT4_SB(sb);
4239         struct ext4_super_block *es = sbi->s_es;
4240         ext4_group_t group;
4241         unsigned int len;
4242         ext4_fsblk_t goal;
4243         ext4_grpblk_t block;
4244 
4245         /* we can't allocate > group size */
4246         len = ar->len;
4247 
4248         /* just a dirty hack to filter too big requests  */
4249         if (len >= EXT4_CLUSTERS_PER_GROUP(sb))
4250                 len = EXT4_CLUSTERS_PER_GROUP(sb);
4251 
4252         /* start searching from the goal */
4253         goal = ar->goal;
4254         if (goal < le32_to_cpu(es->s_first_data_block) ||
4255                         goal >= ext4_blocks_count(es))
4256                 goal = le32_to_cpu(es->s_first_data_block);
4257         ext4_get_group_no_and_offset(sb, goal, &group, &block);
4258 
4259         /* set up allocation goals */
4260         ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);
4261         ac->ac_status = AC_STATUS_CONTINUE;
4262         ac->ac_sb = sb;
4263         ac->ac_inode = ar->inode;
4264         ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
4265         ac->ac_o_ex.fe_group = group;
4266         ac->ac_o_ex.fe_start = block;
4267         ac->ac_o_ex.fe_len = len;
4268         ac->ac_g_ex = ac->ac_o_ex;
4269         ac->ac_flags = ar->flags;
4270 
4271         /* we have to define context: we'll we work with a file or
4272          * locality group. this is a policy, actually */
4273         ext4_mb_group_or_file(ac);
4274 
4275         mb_debug(1, "init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, "
4276                         "left: %u/%u, right %u/%u to %swritable\n",
4277                         (unsigned) ar->len, (unsigned) ar->logical,
4278                         (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
4279                         (unsigned) ar->lleft, (unsigned) ar->pleft,
4280                         (unsigned) ar->lright, (unsigned) ar->pright,
4281                         inode_is_open_for_write(ar->inode) ? "" : "non-");
4282         return 0;
4283 
4284 }
4285 
4286 static noinline_for_stack void
4287 ext4_mb_discard_lg_preallocations(struct super_block *sb,
4288                                         struct ext4_locality_group *lg,
4289                                         int order, int total_entries)
4290 {
4291         ext4_group_t group = 0;
4292         struct ext4_buddy e4b;
4293         struct list_head discard_list;
4294         struct ext4_prealloc_space *pa, *tmp;
4295 
4296         mb_debug(1, "discard locality group preallocation\n");
4297 
4298         INIT_LIST_HEAD(&discard_list);
4299 
4300         spin_lock(&lg->lg_prealloc_lock);
4301         list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
4302                                                 pa_inode_list) {
4303                 spin_lock(&pa->pa_lock);
4304                 if (atomic_read(&pa->pa_count)) {
4305                         /*
4306                          * This is the pa that we just used
4307                          * for block allocation. So don't
4308                          * free that
4309                          */
4310                         spin_unlock(&pa->pa_lock);
4311                         continue;
4312                 }
4313                 if (pa->pa_deleted) {
4314                         spin_unlock(&pa->pa_lock);
4315                         continue;
4316                 }
4317                 /* only lg prealloc space */
4318                 BUG_ON(pa->pa_type != MB_GROUP_PA);
4319 
4320                 /* seems this one can be freed ... */
4321                 pa->pa_deleted = 1;
4322                 spin_unlock(&pa->pa_lock);
4323 
4324                 list_del_rcu(&pa->pa_inode_list);
4325                 list_add(&pa->u.pa_tmp_list, &discard_list);
4326 
4327                 total_entries--;
4328                 if (total_entries <= 5) {
4329                         /*
4330                          * we want to keep only 5 entries
4331                          * allowing it to grow to 8. This
4332                          * mak sure we don't call discard
4333                          * soon for this list.
4334                          */
4335                         break;
4336                 }
4337         }
4338         spin_unlock(&lg->lg_prealloc_lock);
4339 
4340         list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {
4341                 int err;
4342 
4343                 group = ext4_get_group_number(sb, pa->pa_pstart);
4344                 err = ext4_mb_load_buddy_gfp(sb, group, &e4b,
4345                                              GFP_NOFS|__GFP_NOFAIL);
4346                 if (err) {
4347                         ext4_error(sb, "Error %d loading buddy information for %u",
4348                                    err, group);
4349                         continue;
4350                 }
4351                 ext4_lock_group(sb, group);
4352                 list_del(&pa->pa_group_list);
4353                 ext4_mb_release_group_pa(&e4b, pa);
4354                 ext4_unlock_group(sb, group);
4355 
4356                 ext4_mb_unload_buddy(&e4b);
4357                 list_del(&pa->u.pa_tmp_list);
4358                 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
4359         }
4360 }
4361 
4362 /*
4363  * We have incremented pa_count. So it cannot be freed at this
4364  * point. Also we hold lg_mutex. So no parallel allocation is
4365  * possible from this lg. That means pa_free cannot be updated.
4366  *
4367  * A parallel ext4_mb_discard_group_preallocations is possible.
4368  * which can cause the lg_prealloc_list to be updated.
4369  */
4370 
4371 static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)
4372 {
4373         int order, added = 0, lg_prealloc_count = 1;
4374         struct super_block *sb = ac->ac_sb;
4375         struct ext4_locality_group *lg = ac->ac_lg;
4376         struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;
4377 
4378         order = fls(pa->pa_free) - 1;
4379         if (order > PREALLOC_TB_SIZE - 1)
4380                 /* The max size of hash table is PREALLOC_TB_SIZE */
4381                 order = PREALLOC_TB_SIZE - 1;
4382         /* Add the prealloc space to lg */
4383         spin_lock(&lg->lg_prealloc_lock);
4384         list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
4385                                                 pa_inode_list) {
4386                 spin_lock(&tmp_pa->pa_lock);
4387                 if (tmp_pa->pa_deleted) {
4388                         spin_unlock(&tmp_pa->pa_lock);
4389                         continue;
4390                 }
4391                 if (!added && pa->pa_free < tmp_pa->pa_free) {
4392                         /* Add to the tail of the previous entry */
4393                         list_add_tail_rcu(&pa->pa_inode_list,
4394                                                 &tmp_pa->pa_inode_list);
4395                         added = 1;
4396                         /*
4397                          * we want to count the total
4398                          * number of entries in the list
4399                          */
4400                 }
4401                 spin_unlock(&tmp_pa->pa_lock);
4402                 lg_prealloc_count++;
4403         }
4404         if (!added)
4405                 list_add_tail_rcu(&pa->pa_inode_list,
4406                                         &lg->lg_prealloc_list[order]);
4407         spin_unlock(&lg->lg_prealloc_lock);
4408 
4409         /* Now trim the list to be not more than 8 elements */
4410         if (lg_prealloc_count > 8) {
4411                 ext4_mb_discard_lg_preallocations(sb, lg,
4412                                                   order, lg_prealloc_count);
4413                 return;
4414         }
4415         return ;
4416 }
4417 
4418 /*
4419  * release all resource we used in allocation
4420  */
4421 static int ext4_mb_release_context(struct ext4_allocation_context *ac)
4422 {
4423         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4424         struct ext4_prealloc_space *pa = ac->ac_pa;
4425         if (pa) {
4426                 if (pa->pa_type == MB_GROUP_PA) {
4427                         /* see comment in ext4_mb_use_group_pa() */
4428                         spin_lock(&pa->pa_lock);
4429                         pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4430                         pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4431                         pa->pa_free -= ac->ac_b_ex.fe_len;
4432                         pa->pa_len -= ac->ac_b_ex.fe_len;
4433                         spin_unlock(&pa->pa_lock);
4434                 }
4435         }
4436         if (pa) {
4437                 /*
4438                  * We want to add the pa to the right bucket.
4439                  * Remove it from the list and while adding
4440                  * make sure the list to which we are adding
4441                  * doesn't grow big.
4442                  */
4443                 if ((pa->pa_type == MB_GROUP_PA) && likely(pa->pa_free)) {
4444                         spin_lock(pa->pa_obj_lock);
4445                         list_del_rcu(&pa->pa_inode_list);
4446                         spin_unlock(pa->pa_obj_lock);
4447                         ext4_mb_add_n_trim(ac);
4448                 }
4449                 ext4_mb_put_pa(ac, ac->ac_sb, pa);
4450         }
4451         if (ac->ac_bitmap_page)
4452                 put_page(ac->ac_bitmap_page);
4453         if (ac->ac_buddy_page)
4454                 put_page(ac->ac_buddy_page);
4455         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
4456                 mutex_unlock(&ac->ac_lg->lg_mutex);
4457         ext4_mb_collect_stats(ac);
4458         return 0;
4459 }
4460 
4461 static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
4462 {
4463         ext4_group_t i, ngroups = ext4_get_groups_count(sb);
4464         int ret;
4465         int freed = 0;
4466 
4467         trace_ext4_mb_discard_preallocations(sb, needed);
4468         for (i = 0; i < ngroups && needed > 0; i++) {
4469                 ret = ext4_mb_discard_group_preallocations(sb, i, needed);
4470                 freed += ret;
4471                 needed -= ret;
4472         }
4473 
4474         return freed;
4475 }
4476 
4477 /*
4478  * Main entry point into mballoc to allocate blocks
4479  * it tries to use preallocation first, then falls back
4480  * to usual allocation
4481  */
4482 ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
4483                                 struct ext4_allocation_request *ar, int *errp)
4484 {
4485         int freed;
4486         struct ext4_allocation_context *ac = NULL;
4487         struct ext4_sb_info *sbi;
4488         struct super_block *sb;
4489         ext4_fsblk_t block = 0;
4490         unsigned int inquota = 0;
4491         unsigned int reserv_clstrs = 0;
4492 
4493         might_sleep();
4494         sb = ar->inode->i_sb;
4495         sbi = EXT4_SB(sb);
4496 
4497         trace_ext4_request_blocks(ar);
4498 
4499         /* Allow to use superuser reservation for quota file */
4500         if (ext4_is_quota_file(ar->inode))
4501                 ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;
4502 
4503         if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {
4504                 /* Without delayed allocation we need to verify
4505                  * there is enough free blocks to do block allocation
4506                  * and verify allocation doesn't exceed the quota limits.
4507                  */
4508                 while (ar->len &&
4509                         ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {
4510 
4511                         /* let others to free the space */
4512                         cond_resched();
4513                         ar->len = ar->len >> 1;
4514                 }
4515                 if (!ar->len) {
4516                         *errp = -ENOSPC;
4517                         return 0;
4518                 }
4519                 reserv_clstrs = ar->len;
4520                 if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {
4521                         dquot_alloc_block_nofail(ar->inode,
4522                                                  EXT4_C2B(sbi, ar->len));
4523                 } else {
4524                         while (ar->len &&
4525                                 dquot_alloc_block(ar->inode,
4526                                                   EXT4_C2B(sbi, ar->len))) {
4527 
4528                                 ar->flags |= EXT4_MB_HINT_NOPREALLOC;
4529                                 ar->len--;
4530                         }
4531                 }
4532                 inquota = ar->len;
4533                 if (ar->len == 0) {
4534                         *errp = -EDQUOT;
4535                         goto out;
4536                 }
4537         }
4538 
4539         ac = kmem_cache_zalloc(ext4_ac_cachep, GFP_NOFS);
4540         if (!ac) {
4541                 ar->len = 0;
4542                 *errp = -ENOMEM;
4543                 goto out;
4544         }
4545 
4546         *errp = ext4_mb_initialize_context(ac, ar);
4547         if (*errp) {
4548                 ar->len = 0;
4549                 goto out;
4550         }
4551 
4552         ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
4553         if (!ext4_mb_use_preallocated(ac)) {
4554                 ac->ac_op = EXT4_MB_HISTORY_ALLOC;
4555                 ext4_mb_normalize_request(ac, ar);
4556 repeat:
4557                 /* allocate space in core */
4558                 *errp = ext4_mb_regular_allocator(ac);
4559                 if (*errp)
4560                         goto discard_and_exit;
4561 
4562                 /* as we've just preallocated more space than
4563                  * user requested originally, we store allocated
4564                  * space in a special descriptor */
4565                 if (ac->ac_status == AC_STATUS_FOUND &&
4566                     ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
4567                         *errp = ext4_mb_new_preallocation(ac);
4568                 if (*errp) {
4569                 discard_and_exit:
4570                         ext4_discard_allocated_blocks(ac);
4571                         goto errout;
4572                 }
4573         }
4574         if (likely(ac->ac_status == AC_STATUS_FOUND)) {
4575                 *errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs);
4576                 if (*errp) {
4577                         ext4_discard_allocated_blocks(ac);
4578                         goto errout;
4579                 } else {
4580                         block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
4581                         ar->len = ac->ac_b_ex.fe_len;
4582                 }
4583         } else {
4584                 freed  = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
4585                 if (freed)
4586                         goto repeat;
4587                 *errp = -ENOSPC;
4588         }
4589 
4590 errout:
4591         if (*errp) {
4592                 ac->ac_b_ex.fe_len = 0;
4593                 ar->len = 0;
4594                 ext4_mb_show_ac(ac);
4595         }
4596         ext4_mb_release_context(ac);
4597 out:
4598         if (ac)
4599                 kmem_cache_free(ext4_ac_cachep, ac);
4600         if (inquota && ar->len < inquota)
4601                 dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));
4602         if (!ar->len) {
4603                 if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)
4604                         /* release all the reserved blocks if non delalloc */
4605                         percpu_counter_sub(&sbi->s_dirtyclusters_counter,
4606                                                 reserv_clstrs);
4607         }
4608 
4609         trace_ext4_allocate_blocks(ar, (unsigned long long)block);
4610 
4611         return block;
4612 }
4613 
4614 /*
4615  * We can merge two free data extents only if the physical blocks
4616  * are contiguous, AND the extents were freed by the same transaction,
4617  * AND the blocks are associated with the same group.
4618  */
4619 static void ext4_try_merge_freed_extent(struct ext4_sb_info *sbi,
4620                                         struct ext4_free_data *entry,
4621                                         struct ext4_free_data *new_entry,
4622                                         struct rb_root *entry_rb_root)
4623 {
4624         if ((entry->efd_tid != new_entry->efd_tid) ||
4625             (entry->efd_group != new_entry->efd_group))
4626                 return;
4627         if (entry->efd_start_cluster + entry->efd_count ==
4628             new_entry->efd_start_cluster) {
4629                 new_entry->efd_start_cluster = entry->efd_start_cluster;
4630                 new_entry->efd_count += entry->efd_count;
4631         } else if (new_entry->efd_start_cluster + new_entry->efd_count ==
4632                    entry->efd_start_cluster) {
4633                 new_entry->efd_count += entry->efd_count;
4634         } else
4635                 return;
4636         spin_lock(&sbi->s_md_lock);
4637         list_del(&entry->efd_list);
4638         spin_unlock(&sbi->s_md_lock);
4639         rb_erase(&entry->efd_node, entry_rb_root);
4640         kmem_cache_free(ext4_free_data_cachep, entry);
4641 }
4642 
4643 static noinline_for_stack int
4644 ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
4645                       struct ext4_free_data *new_entry)
4646 {
4647         ext4_group_t group = e4b->bd_group;
4648         ext4_grpblk_t cluster;
4649         ext4_grpblk_t clusters = new_entry->efd_count;
4650         struct ext4_free_data *entry;
4651         struct ext4_group_info *db = e4b->bd_info;
4652         struct super_block *sb = e4b->bd_sb;
4653         struct ext4_sb_info *sbi = EXT4_SB(sb);
4654         struct rb_node **n = &db->bb_free_root.rb_node, *node;
4655         struct rb_node *parent = NULL, *new_node;
4656 
4657         BUG_ON(!ext4_handle_valid(handle));
4658         BUG_ON(e4b->bd_bitmap_page == NULL);
4659         BUG_ON(e4b->bd_buddy_page == NULL);
4660 
4661         new_node = &new_entry->efd_node;
4662         cluster = new_entry->efd_start_cluster;
4663 
4664         if (!*n) {
4665                 /* first free block exent. We need to
4666                    protect buddy cache from being freed,
4667                  * otherwise we'll refresh it from
4668                  * on-disk bitmap and lose not-yet-available
4669                  * blocks */
4670                 get_page(e4b->bd_buddy_page);
4671                 get_page(e4b->bd_bitmap_page);
4672         }
4673         while (*n) {
4674                 parent = *n;
4675                 entry = rb_entry(parent, struct ext4_free_data, efd_node);
4676                 if (cluster < entry->efd_start_cluster)
4677                         n = &(*n)->rb_left;
4678                 else if (cluster >= (entry->efd_start_cluster + entry->efd_count))
4679                         n = &(*n)->rb_right;
4680                 else {
4681                         ext4_grp_locked_error(sb, group, 0,
4682                                 ext4_group_first_block_no(sb, group) +
4683                                 EXT4_C2B(sbi, cluster),
4684                                 "Block already on to-be-freed list");
4685                         return 0;
4686                 }
4687         }
4688 
4689         rb_link_node(new_node, parent, n);
4690         rb_insert_color(new_node, &db->bb_free_root);
4691 
4692         /* Now try to see the extent can be merged to left and right */
4693         node = rb_prev(new_node);
4694         if (node) {
4695                 entry = rb_entry(node, struct ext4_free_data, efd_node);
4696                 ext4_try_merge_freed_extent(sbi, entry, new_entry,
4697                                             &(db->bb_free_root));
4698         }
4699 
4700         node = rb_next(new_node);
4701         if (node) {
4702                 entry = rb_entry(node, struct ext4_free_data, efd_node);
4703                 ext4_try_merge_freed_extent(sbi, entry, new_entry,
4704                                             &(db->bb_free_root));
4705         }
4706 
4707         spin_lock(&sbi->s_md_lock);
4708         list_add_tail(&new_entry->efd_list, &sbi->s_freed_data_list);
4709         sbi->s_mb_free_pending += clusters;
4710         spin_unlock(&sbi->s_md_lock);
4711         return 0;
4712 }
4713 
4714 /**
4715  * ext4_free_blocks() -- Free given blocks and update quota
4716  * @handle:             handle for this transaction
4717  * @inode:              inode
4718  * @bh:                 optional buffer of the block to be freed
4719  * @block:              starting physical block to be freed
4720  * @count:              number of blocks to be freed
4721  * @flags:              flags used by ext4_free_blocks
4722  */
4723 void ext4_free_blocks(handle_t *handle, struct inode *inode,
4724                       struct buffer_head *bh, ext4_fsblk_t block,
4725                       unsigned long count, int flags)
4726 {
4727         struct buffer_head *bitmap_bh = NULL;
4728         struct super_block *sb = inode->i_sb;
4729         struct ext4_group_desc *gdp;
4730         unsigned int overflow;
4731         ext4_grpblk_t bit;
4732         struct buffer_head *gd_bh;
4733         ext4_group_t block_group;
4734         struct ext4_sb_info *sbi;
4735         struct ext4_buddy e4b;
4736         unsigned int count_clusters;
4737         int err = 0;
4738         int ret;
4739 
4740         might_sleep();
4741         if (bh) {
4742                 if (block)
4743                         BUG_ON(block != bh->b_blocknr);
4744                 else
4745                         block = bh->b_blocknr;
4746         }
4747 
4748         sbi = EXT4_SB(sb);
4749         if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&
4750             !ext4_data_block_valid(sbi, block, count)) {
4751                 ext4_error(sb, "Freeing blocks not in datazone - "
4752                            "block = %llu, count = %lu", block, count);
4753                 goto error_return;
4754         }
4755 
4756         ext4_debug("freeing block %llu\n", block);
4757         trace_ext4_free_blocks(inode, block, count, flags);
4758 
4759         if (bh && (flags & EXT4_FREE_BLOCKS_FORGET)) {
4760                 BUG_ON(count > 1);
4761 
4762                 ext4_forget(handle, flags & EXT4_FREE_BLOCKS_METADATA,
4763                             inode, bh, block);
4764         }
4765 
4766         /*
4767          * If the extent to be freed does not begin on a cluster
4768          * boundary, we need to deal with partial clusters at the
4769          * beginning and end of the extent.  Normally we will free
4770          * blocks at the beginning or the end unless we are explicitly
4771          * requested to avoid doing so.
4772          */
4773         overflow = EXT4_PBLK_COFF(sbi, block);
4774         if (overflow) {
4775                 if (flags & EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER) {
4776                         overflow = sbi->s_cluster_ratio - overflow;
4777                         block += overflow;
4778                         if (count > overflow)
4779                                 count -= overflow;
4780                         else
4781                                 return;
4782                 } else {
4783                         block -= overflow;
4784                         count += overflow;
4785                 }
4786         }
4787         overflow = EXT4_LBLK_COFF(sbi, count);
4788         if (overflow) {
4789                 if (flags & EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER) {
4790                         if (count > overflow)
4791                                 count -= overflow;
4792                         else
4793                                 return;
4794                 } else
4795                         count += sbi->s_cluster_ratio - overflow;
4796         }
4797 
4798         if (!bh && (flags & EXT4_FREE_BLOCKS_FORGET)) {
4799                 int i;
4800                 int is_metadata = flags & EXT4_FREE_BLOCKS_METADATA;
4801 
4802                 for (i = 0; i < count; i++) {
4803                         cond_resched();
4804                         if (is_metadata)
4805                                 bh = sb_find_get_block(inode->i_sb, block + i);
4806                         ext4_forget(handle, is_metadata, inode, bh, block + i);
4807                 }
4808         }
4809 
4810 do_more:
4811         overflow = 0;
4812         ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
4813 
4814         if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(
4815                         ext4_get_group_info(sb, block_group))))
4816                 return;
4817 
4818         /*
4819          * Check to see if we are freeing blocks across a group
4820          * boundary.
4821          */
4822         if (EXT4_C2B(sbi, bit) + count > EXT4_BLOCKS_PER_GROUP(sb)) {
4823                 overflow = EXT4_C2B(sbi, bit) + count -
4824                         EXT4_BLOCKS_PER_GROUP(sb);
4825                 count -= overflow;
4826         }
4827         count_clusters = EXT4_NUM_B2C(sbi, count);
4828         bitmap_bh = ext4_read_block_bitmap(sb, block_group);
4829         if (IS_ERR(bitmap_bh)) {
4830                 err = PTR_ERR(bitmap_bh);
4831                 bitmap_bh = NULL;
4832                 goto error_return;
4833         }
4834         gdp = ext4_get_group_desc(sb, block_group, &gd_bh);
4835         if (!gdp) {
4836                 err = -EIO;
4837                 goto error_return;
4838         }
4839 
4840         if (in_range(ext4_block_bitmap(sb, gdp), block, count) ||
4841             in_range(ext4_inode_bitmap(sb, gdp), block, count) ||
4842             in_range(block, ext4_inode_table(sb, gdp),
4843                      sbi->s_itb_per_group) ||
4844             in_range(block + count - 1, ext4_inode_table(sb, gdp),
4845                      sbi->s_itb_per_group)) {
4846 
4847                 ext4_error(sb, "Freeing blocks in system zone - "
4848                            "Block = %llu, count = %lu", block, count);
4849                 /* err = 0. ext4_std_error should be a no op */
4850                 goto error_return;
4851         }
4852 
4853         BUFFER_TRACE(bitmap_bh, "getting write access");
4854         err = ext4_journal_get_write_access(handle, bitmap_bh);
4855         if (err)
4856                 goto error_return;
4857 
4858         /*
4859          * We are about to modify some metadata.  Call the journal APIs
4860          * to unshare ->b_data if a currently-committing transaction is
4861          * using it
4862          */
4863         BUFFER_TRACE(gd_bh, "get_write_access");
4864         err = ext4_journal_get_write_access(handle, gd_bh);
4865         if (err)
4866                 goto error_return;
4867 #ifdef AGGRESSIVE_CHECK
4868         {
4869                 int i;
4870                 for (i = 0; i < count_clusters; i++)
4871                         BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));
4872         }
4873 #endif
4874         trace_ext4_mballoc_free(sb, inode, block_group, bit, count_clusters);
4875 
4876         /* __GFP_NOFAIL: retry infinitely, ignore TIF_MEMDIE and memcg limit. */
4877         err = ext4_mb_load_buddy_gfp(sb, block_group, &e4b,
4878                                      GFP_NOFS|__GFP_NOFAIL);
4879         if (err)
4880                 goto error_return;
4881 
4882         /*
4883          * We need to make sure we don't reuse the freed block until after the
4884          * transaction is committed. We make an exception if the inode is to be
4885          * written in writeback mode since writeback mode has weak data
4886          * consistency guarantees.
4887          */
4888         if (ext4_handle_valid(handle) &&
4889             ((flags & EXT4_FREE_BLOCKS_METADATA) ||
4890              !ext4_should_writeback_data(inode))) {
4891                 struct ext4_free_data *new_entry;
4892                 /*
4893                  * We use __GFP_NOFAIL because ext4_free_blocks() is not allowed
4894                  * to fail.
4895                  */
4896                 new_entry = kmem_cache_alloc(ext4_free_data_cachep,
4897                                 GFP_NOFS|__GFP_NOFAIL);
4898                 new_entry->efd_start_cluster = bit;
4899                 new_entry->efd_group = block_group;
4900                 new_entry->efd_count = count_clusters;
4901                 new_entry->efd_tid = handle->h_transaction->t_tid;
4902 
4903                 ext4_lock_group(sb, block_group);
4904                 mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);
4905                 ext4_mb_free_metadata(handle, &e4b, new_entry);
4906         } else {
4907                 /* need to update group_info->bb_free and bitmap
4908                  * with group lock held. generate_buddy look at
4909                  * them with group lock_held
4910                  */
4911                 if (test_opt(sb, DISCARD)) {
4912                         err = ext4_issue_discard(sb, block_group, bit, count,
4913                                                  NULL);
4914                         if (err && err != -EOPNOTSUPP)
4915                                 ext4_msg(sb, KERN_WARNING, "discard request in"
4916                                          " group:%d block:%d count:%lu failed"
4917                                          " with %d", block_group, bit, count,
4918                                          err);
4919                 } else
4920                         EXT4_MB_GRP_CLEAR_TRIMMED(e4b.bd_info);
4921 
4922                 ext4_lock_group(sb, block_group);
4923                 mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);
4924                 mb_free_blocks(inode, &e4b, bit, count_clusters);
4925         }
4926 
4927         ret = ext4_free_group_clusters(sb, gdp) + count_clusters;
4928         ext4_free_group_clusters_set(sb, gdp, ret);
4929         ext4_block_bitmap_csum_set(sb, block_group, gdp, bitmap_bh);
4930         ext4_group_desc_csum_set(sb, block_group, gdp);
4931         ext4_unlock_group(sb, block_group);
4932 
4933         if (sbi->s_log_groups_per_flex) {
4934                 ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
4935                 atomic64_add(count_clusters,
4936                              &sbi_array_rcu_deref(sbi, s_flex_groups,
4937                                                   flex_group)->free_clusters);
4938         }
4939 
4940         /*
4941          * on a bigalloc file system, defer the s_freeclusters_counter
4942          * update to the caller (ext4_remove_space and friends) so they
4943          * can determine if a cluster freed here should be rereserved
4944          */
4945         if (!(flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)) {
4946                 if (!(flags & EXT4_FREE_BLOCKS_NO_QUOT_UPDATE))
4947                         dquot_free_block(inode, EXT4_C2B(sbi, count_clusters));
4948                 percpu_counter_add(&sbi->s_freeclusters_counter,
4949                                    count_clusters);
4950         }
4951 
4952         ext4_mb_unload_buddy(&e4b);
4953 
4954         /* We dirtied the bitmap block */
4955         BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
4956         err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
4957 
4958         /* And the group descriptor block */
4959         BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
4960         ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh);
4961         if (!err)
4962                 err = ret;
4963 
4964         if (overflow && !err) {
4965                 block += count;
4966                 count = overflow;
4967                 put_bh(bitmap_bh);
4968                 goto do_more;
4969         }
4970 error_return:
4971         brelse(bitmap_bh);
4972         ext4_std_error(sb, err);
4973         return;
4974 }
4975 
4976 /**
4977  * ext4_group_add_blocks() -- Add given blocks to an existing group
4978  * @handle:                     handle to this transaction
4979  * @sb:                         super block
4980  * @block:                      start physical block to add to the block group
4981  * @count:                      number of blocks to free
4982  *
4983  * This marks the blocks as free in the bitmap and buddy.
4984  */
4985 int ext4_group_add_blocks(handle_t *handle, struct super_block *sb,
4986                          ext4_fsblk_t block, unsigned long count)
4987 {
4988         struct buffer_head *bitmap_bh = NULL;
4989         struct buffer_head *gd_bh;
4990         ext4_group_t block_group;
4991         ext4_grpblk_t bit;
4992         unsigned int i;
4993         struct ext4_group_desc *desc;
4994         struct ext4_sb_info *sbi = EXT4_SB(sb);
4995         struct ext4_buddy e4b;
4996         int err = 0, ret, free_clusters_count;
4997         ext4_grpblk_t clusters_freed;
4998         ext4_fsblk_t first_cluster = EXT4_B2C(sbi, block);
4999         ext4_fsblk_t last_cluster = EXT4_B2C(sbi, block + count - 1);
5000         unsigned long cluster_count = last_cluster - first_cluster + 1;
5001 
5002         ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);
5003 
5004         if (count == 0)
5005                 return 0;
5006 
5007         ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
5008         /*
5009          * Check to see if we are freeing blocks across a group
5010          * boundary.
5011          */
5012         if (bit + cluster_count > EXT4_CLUSTERS_PER_GROUP(sb)) {
5013                 ext4_warning(sb, "too many blocks added to group %u",
5014                              block_group);
5015                 err = -EINVAL;
5016                 goto error_return;
5017         }
5018 
5019         bitmap_bh = ext4_read_block_bitmap(sb, block_group);
5020         if (IS_ERR(bitmap_bh)) {
5021                 err = PTR_ERR(bitmap_bh);
5022                 bitmap_bh = NULL;
5023                 goto error_return;
5024         }
5025 
5026         desc = ext4_get_group_desc(sb, block_group, &gd_bh);
5027         if (!desc) {
5028                 err = -EIO;
5029                 goto error_return;
5030         }
5031 
5032         if (in_range(ext4_block_bitmap(sb, desc), block, count) ||
5033             in_range(ext4_inode_bitmap(sb, desc), block, count) ||
5034             in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||
5035             in_range(block + count - 1, ext4_inode_table(sb, desc),
5036                      sbi->s_itb_per_group)) {
5037                 ext4_error(sb, "Adding blocks in system zones - "
5038                            "Block = %llu, count = %lu",
5039                            block, count);
5040                 err = -EINVAL;
5041                 goto error_return;
5042         }
5043 
5044         BUFFER_TRACE(bitmap_bh, "getting write access");
5045         err = ext4_journal_get_write_access(handle, bitmap_bh);
5046         if (err)
5047                 goto error_return;
5048 
5049         /*
5050          * We are about to modify some metadata.  Call the journal APIs
5051          * to unshare ->b_data if a currently-committing transaction is
5052          * using it
5053          */
5054         BUFFER_TRACE(gd_bh, "get_write_access");
5055         err = ext4_journal_get_write_access(handle, gd_bh);
5056         if (err)
5057                 goto error_return;
5058 
5059         for (i = 0, clusters_freed = 0; i < cluster_count; i++) {
5060                 BUFFER_TRACE(bitmap_bh, "clear bit");
5061                 if (!mb_test_bit(bit + i, bitmap_bh->b_data)) {
5062                         ext4_error(sb, "bit already cleared for block %llu",
5063                                    (ext4_fsblk_t)(block + i));
5064                         BUFFER_TRACE(bitmap_bh, "bit already cleared");
5065                 } else {
5066                         clusters_freed++;
5067                 }
5068         }
5069 
5070         err = ext4_mb_load_buddy(sb, block_group, &e4b);
5071         if (err)
5072                 goto error_return;
5073 
5074         /*
5075          * need to update group_info->bb_free and bitmap
5076          * with group lock held. generate_buddy look at
5077          * them with group lock_held
5078          */
5079         ext4_lock_group(sb, block_group);
5080         mb_clear_bits(bitmap_bh->b_data, bit, cluster_count);
5081         mb_free_blocks(NULL, &e4b, bit, cluster_count);
5082         free_clusters_count = clusters_freed +
5083                 ext4_free_group_clusters(sb, desc);
5084         ext4_free_group_clusters_set(sb, desc, free_clusters_count);
5085         ext4_block_bitmap_csum_set(sb, block_group, desc, bitmap_bh);
5086         ext4_group_desc_csum_set(sb, block_group, desc);
5087         ext4_unlock_group(sb, block_group);
5088         percpu_counter_add(&sbi->s_freeclusters_counter,
5089                            clusters_freed);
5090 
5091         if (sbi->s_log_groups_per_flex) {
5092                 ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
5093                 atomic64_add(clusters_freed,
5094                              &sbi_array_rcu_deref(sbi, s_flex_groups,
5095                                                   flex_group)->free_clusters);
5096         }
5097 
5098         ext4_mb_unload_buddy(&e4b);
5099 
5100         /* We dirtied the bitmap block */
5101         BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
5102         err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
5103 
5104         /* And the group descriptor block */
5105         BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
5106         ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh);
5107         if (!err)
5108                 err = ret;
5109 
5110 error_return:
5111         brelse(bitmap_bh);
5112         ext4_std_error(sb, err);
5113         return err;
5114 }
5115 
5116 /**
5117  * ext4_trim_extent -- function to TRIM one single free extent in the group
5118  * @sb:         super block for the file system
5119  * @start:      starting block of the free extent in the alloc. group
5120  * @count:      number of blocks to TRIM
5121  * @group:      alloc. group we are working with
5122  * @e4b:        ext4 buddy for the group
5123  *
5124  * Trim "count" blocks starting at "start" in the "group". To assure that no
5125  * one will allocate those blocks, mark it as used in buddy bitmap. This must
5126  * be called with under the group lock.
5127  */
5128 static int ext4_trim_extent(struct super_block *sb, int start, int count,
5129                              ext4_group_t group, struct ext4_buddy *e4b)
5130 __releases(bitlock)
5131 __acquires(bitlock)
5132 {
5133         struct ext4_free_extent ex;
5134         int ret = 0;
5135 
5136         trace_ext4_trim_extent(sb, group, start, count);
5137 
5138         assert_spin_locked(ext4_group_lock_ptr(sb, group));
5139 
5140         ex.fe_start = start;
5141         ex.fe_group = group;
5142         ex.fe_len = count;
5143 
5144         /*
5145          * Mark blocks used, so no one can reuse them while
5146          * being trimmed.
5147          */
5148         mb_mark_used(e4b, &ex);
5149         ext4_unlock_group(sb, group);
5150         ret = ext4_issue_discard(sb, group, start, count, NULL);
5151         ext4_lock_group(sb, group);
5152         mb_free_blocks(NULL, e4b, start, ex.fe_len);
5153         return ret;
5154 }
5155 
5156 /**
5157  * ext4_trim_all_free -- function to trim all free space in alloc. group
5158  * @sb:                 super block for file system
5159  * @group:              group to be trimmed
5160  * @start:              first group block to examine
5161  * @max:                last group block to examine
5162  * @minblocks:          minimum extent block count
5163  *
5164  * ext4_trim_all_free walks through group's buddy bitmap searching for free
5165  * extents. When the free block is found, ext4_trim_extent is called to TRIM
5166  * the extent.
5167  *
5168  *
5169  * ext4_trim_all_free walks through group's block bitmap searching for free
5170  * extents. When the free extent is found, mark it as used in group buddy
5171  * bitmap. Then issue a TRIM command on this extent and free the extent in
5172  * the group buddy bitmap. This is done until whole group is scanned.
5173  */
5174 static ext4_grpblk_t
5175 ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
5176                    ext4_grpblk_t start, ext4_grpblk_t max,
5177                    ext4_grpblk_t minblocks)
5178 {
5179         void *bitmap;
5180         ext4_grpblk_t next, count = 0, free_count = 0;
5181         struct ext4_buddy e4b;
5182         int ret = 0;
5183 
5184         trace_ext4_trim_all_free(sb, group, start, max);
5185 
5186         ret = ext4_mb_load_buddy(sb, group, &e4b);
5187         if (ret) {
5188                 ext4_warning(sb, "Error %d loading buddy information for %u",
5189                              ret, group);
5190                 return ret;
5191         }
5192         bitmap = e4b.bd_bitmap;
5193 
5194         ext4_lock_group(sb, group);
5195         if (EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) &&
5196             minblocks >= atomic_read(&EXT4_SB(sb)->s_last_trim_minblks))
5197                 goto out;
5198 
5199         start = (e4b.bd_info->bb_first_free > start) ?
5200                 e4b.bd_info->bb_first_free : start;
5201 
5202         while (start <= max) {
5203                 start = mb_find_next_zero_bit(bitmap, max + 1, start);
5204                 if (start > max)
5205                         break;
5206                 next = mb_find_next_bit(bitmap, max + 1, start);
5207 
5208                 if ((next - start) >= minblocks) {
5209                         ret = ext4_trim_extent(sb, start,
5210                                                next - start, group, &e4b);
5211                         if (ret && ret != -EOPNOTSUPP)
5212                                 break;
5213                         ret = 0;
5214                         count += next - start;
5215                 }
5216                 free_count += next - start;
5217                 start = next + 1;
5218 
5219                 if (fatal_signal_pending(current)) {
5220                         count = -ERESTARTSYS;
5221                         break;
5222                 }
5223 
5224                 if (need_resched()) {
5225                         ext4_unlock_group(sb, group);
5226                         cond_resched();
5227                         ext4_lock_group(sb, group);
5228                 }
5229 
5230                 if ((e4b.bd_info->bb_free - free_count) < minblocks)
5231                         break;
5232         }
5233 
5234         if (!ret) {
5235                 ret = count;
5236                 EXT4_MB_GRP_SET_TRIMMED(e4b.bd_info);
5237         }
5238 out:
5239         ext4_unlock_group(sb, group);
5240         ext4_mb_unload_buddy(&e4b);
5241 
5242         ext4_debug("trimmed %d blocks in the group %d\n",
5243                 count, group);
5244 
5245         return ret;
5246 }
5247 
5248 /**
5249  * ext4_trim_fs() -- trim ioctl handle function
5250  * @sb:                 superblock for filesystem
5251  * @range:              fstrim_range structure
5252  *
5253  * start:       First Byte to trim
5254  * len:         number of Bytes to trim from start
5255  * minlen:      minimum extent length in Bytes
5256  * ext4_trim_fs goes through all allocation groups containing Bytes from
5257  * start to start+len. For each such a group ext4_trim_all_free function
5258  * is invoked to trim all free space.
5259  */
5260 int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range)
5261 {
5262         struct ext4_group_info *grp;
5263         ext4_group_t group, first_group, last_group;
5264         ext4_grpblk_t cnt = 0, first_cluster, last_cluster;
5265         uint64_t start, end, minlen, trimmed = 0;
5266         ext4_fsblk_t first_data_blk =
5267                         le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
5268         ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);
5269         int ret = 0;
5270 
5271         start = range->start >> sb->s_blocksize_bits;
5272         end = start + (range->len >> sb->s_blocksize_bits) - 1;
5273         minlen = EXT4_NUM_B2C(EXT4_SB(sb),
5274                               range->minlen >> sb->s_blocksize_bits);
5275 
5276         if (minlen > EXT4_CLUSTERS_PER_GROUP(sb) ||
5277             start >= max_blks ||
5278             range->len < sb->s_blocksize)
5279                 return -EINVAL;
5280         if (end >= max_blks)
5281                 end = max_blks - 1;
5282         if (end <= first_data_blk)
5283                 goto out;
5284         if (start < first_data_blk)
5285                 start = first_data_blk;
5286 
5287         /* Determine first and last group to examine based on start and end */
5288         ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) start,
5289                                      &first_group, &first_cluster);
5290         ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) end,
5291                                      &last_group, &last_cluster);
5292 
5293         /* end now represents the last cluster to discard in this group */
5294         end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
5295 
5296         for (group = first_group; group <= last_group; group++) {
5297                 grp = ext4_get_group_info(sb, group);
5298                 /* We only do this if the grp has never been initialized */
5299                 if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
5300                         ret = ext4_mb_init_group(sb, group, GFP_NOFS);
5301                         if (ret)
5302                                 break;
5303                 }
5304 
5305                 /*
5306                  * For all the groups except the last one, last cluster will
5307                  * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to
5308                  * change it for the last group, note that last_cluster is
5309                  * already computed earlier by ext4_get_group_no_and_offset()
5310                  */
5311                 if (group == last_group)
5312                         end = last_cluster;
5313 
5314                 if (grp->bb_free >= minlen) {
5315                         cnt = ext4_trim_all_free(sb, group, first_cluster,
5316                                                 end, minlen);
5317                         if (cnt < 0) {
5318                                 ret = cnt;
5319                                 break;
5320                         }
5321                         trimmed += cnt;
5322                 }
5323 
5324                 /*
5325                  * For every group except the first one, we are sure
5326                  * that the first cluster to discard will be cluster #0.
5327                  */
5328                 first_cluster = 0;
5329         }
5330 
5331         if (!ret)
5332                 atomic_set(&EXT4_SB(sb)->s_last_trim_minblks, minlen);
5333 
5334 out:
5335         range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;
5336         return ret;
5337 }
5338 
5339 /* Iterate all the free extents in the group. */
5340 int
5341 ext4_mballoc_query_range(
5342         struct super_block              *sb,
5343         ext4_group_t                    group,
5344         ext4_grpblk_t                   start,
5345         ext4_grpblk_t                   end,
5346         ext4_mballoc_query_range_fn     formatter,
5347         void                            *priv)
5348 {
5349         void                            *bitmap;
5350         ext4_grpblk_t                   next;
5351         struct ext4_buddy               e4b;
5352         int                             error;
5353 
5354         error = ext4_mb_load_buddy(sb, group, &e4b);
5355         if (error)
5356                 return error;
5357         bitmap = e4b.bd_bitmap;
5358 
5359         ext4_lock_group(sb, group);
5360 
5361         start = (e4b.bd_info->bb_first_free > start) ?
5362                 e4b.bd_info->bb_first_free : start;
5363         if (end >= EXT4_CLUSTERS_PER_GROUP(sb))
5364                 end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
5365 
5366         while (start <= end) {
5367                 start = mb_find_next_zero_bit(bitmap, end + 1, start);
5368                 if (start > end)
5369                         break;
5370                 next = mb_find_next_bit(bitmap, end + 1, start);
5371 
5372                 ext4_unlock_group(sb, group);
5373                 error = formatter(sb, group, start, next - start, priv);
5374                 if (error)
5375                         goto out_unload;
5376                 ext4_lock_group(sb, group);
5377 
5378                 start = next + 1;
5379         }
5380 
5381         ext4_unlock_group(sb, group);
5382 out_unload:
5383         ext4_mb_unload_buddy(&e4b);
5384 
5385         return error;
5386 }
5387 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp