ebc50aa7347c8f486a7fd7438f5c6de91b0e3ab4
[pandora-kernel.git] / fs / ext4 / mballoc.c
1 /*
2  * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3  * Written by Alex Tomas <alex@clusterfs.com>
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public Licens
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
17  */
18
19
20 /*
21  * mballoc.c contains the multiblocks allocation routines
22  */
23
24 #include "mballoc.h"
25 #include <linux/debugfs.h>
26 #include <linux/slab.h>
27 #include <trace/events/ext4.h>
28
29 /*
30  * MUSTDO:
31  *   - test ext4_ext_search_left() and ext4_ext_search_right()
32  *   - search for metadata in few groups
33  *
34  * TODO v4:
35  *   - normalization should take into account whether file is still open
36  *   - discard preallocations if no free space left (policy?)
37  *   - don't normalize tails
38  *   - quota
39  *   - reservation for superuser
40  *
41  * TODO v3:
42  *   - bitmap read-ahead (proposed by Oleg Drokin aka green)
43  *   - track min/max extents in each group for better group selection
44  *   - mb_mark_used() may allocate chunk right after splitting buddy
45  *   - tree of groups sorted by number of free blocks
46  *   - error handling
47  */
48
49 /*
50  * The allocation request involve request for multiple number of blocks
51  * near to the goal(block) value specified.
52  *
53  * During initialization phase of the allocator we decide to use the
54  * group preallocation or inode preallocation depending on the size of
55  * the file. The size of the file could be the resulting file size we
56  * would have after allocation, or the current file size, which ever
57  * is larger. If the size is less than sbi->s_mb_stream_request we
58  * select to use the group preallocation. The default value of
59  * s_mb_stream_request is 16 blocks. This can also be tuned via
60  * /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in
61  * terms of number of blocks.
62  *
63  * The main motivation for having small file use group preallocation is to
64  * ensure that we have small files closer together on the disk.
65  *
66  * First stage the allocator looks at the inode prealloc list,
67  * ext4_inode_info->i_prealloc_list, which contains list of prealloc
68  * spaces for this particular inode. The inode prealloc space is
69  * represented as:
70  *
71  * pa_lstart -> the logical start block for this prealloc space
72  * pa_pstart -> the physical start block for this prealloc space
73  * pa_len    -> length for this prealloc space (in clusters)
74  * pa_free   ->  free space available in this prealloc space (in clusters)
75  *
76  * The inode preallocation space is used looking at the _logical_ start
77  * block. If only the logical file block falls within the range of prealloc
78  * space we will consume the particular prealloc space. This makes sure that
79  * we have contiguous physical blocks representing the file blocks
80  *
81  * The important thing to be noted in case of inode prealloc space is that
82  * we don't modify the values associated to inode prealloc space except
83  * pa_free.
84  *
85  * If we are not able to find blocks in the inode prealloc space and if we
86  * have the group allocation flag set then we look at the locality group
87  * prealloc space. These are per CPU prealloc list represented as
88  *
89  * ext4_sb_info.s_locality_groups[smp_processor_id()]
90  *
91  * The reason for having a per cpu locality group is to reduce the contention
92  * between CPUs. It is possible to get scheduled at this point.
93  *
94  * The locality group prealloc space is used looking at whether we have
95  * enough free space (pa_free) within the prealloc space.
96  *
97  * If we can't allocate blocks via inode prealloc or/and locality group
98  * prealloc then we look at the buddy cache. The buddy cache is represented
99  * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
100  * mapped to the buddy and bitmap information regarding different
101  * groups. The buddy information is attached to buddy cache inode so that
102  * we can access them through the page cache. The information regarding
103  * each group is loaded via ext4_mb_load_buddy.  The information involve
104  * block bitmap and buddy information. The information are stored in the
105  * inode as:
106  *
107  *  {                        page                        }
108  *  [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
109  *
110  *
111  * one block each for bitmap and buddy information.  So for each group we
112  * take up 2 blocks. A page can contain blocks_per_page (PAGE_CACHE_SIZE /
113  * blocksize) blocks.  So it can have information regarding groups_per_page
114  * which is blocks_per_page/2
115  *
116  * The buddy cache inode is not stored on disk. The inode is thrown
117  * away when the filesystem is unmounted.
118  *
119  * We look for count number of blocks in the buddy cache. If we were able
120  * to locate that many free blocks we return with additional information
121  * regarding rest of the contiguous physical block available
122  *
123  * Before allocating blocks via buddy cache we normalize the request
124  * blocks. This ensure we ask for more blocks that we needed. The extra
125  * blocks that we get after allocation is added to the respective prealloc
126  * list. In case of inode preallocation we follow a list of heuristics
127  * based on file size. This can be found in ext4_mb_normalize_request. If
128  * we are doing a group prealloc we try to normalize the request to
129  * sbi->s_mb_group_prealloc.  The default value of s_mb_group_prealloc is
130  * dependent on the cluster size; for non-bigalloc file systems, it is
131  * 512 blocks. This can be tuned via
132  * /sys/fs/ext4/<partition>/mb_group_prealloc. The value is represented in
133  * terms of number of blocks. If we have mounted the file system with -O
134  * stripe=<value> option the group prealloc request is normalized to the
135  * the smallest multiple of the stripe value (sbi->s_stripe) which is
136  * greater than the default mb_group_prealloc.
137  *
138  * The regular allocator (using the buddy cache) supports a few tunables.
139  *
140  * /sys/fs/ext4/<partition>/mb_min_to_scan
141  * /sys/fs/ext4/<partition>/mb_max_to_scan
142  * /sys/fs/ext4/<partition>/mb_order2_req
143  *
144  * The regular allocator uses buddy scan only if the request len is power of
145  * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
146  * value of s_mb_order2_reqs can be tuned via
147  * /sys/fs/ext4/<partition>/mb_order2_req.  If the request len is equal to
148  * stripe size (sbi->s_stripe), we try to search for contiguous block in
149  * stripe size. This should result in better allocation on RAID setups. If
150  * not, we search in the specific group using bitmap for best extents. The
151  * tunable min_to_scan and max_to_scan control the behaviour here.
152  * min_to_scan indicate how long the mballoc __must__ look for a best
153  * extent and max_to_scan indicates how long the mballoc __can__ look for a
154  * best extent in the found extents. Searching for the blocks starts with
155  * the group specified as the goal value in allocation context via
156  * ac_g_ex. Each group is first checked based on the criteria whether it
157  * can be used for allocation. ext4_mb_good_group explains how the groups are
158  * checked.
159  *
160  * Both the prealloc space are getting populated as above. So for the first
161  * request we will hit the buddy cache which will result in this prealloc
162  * space getting filled. The prealloc space is then later used for the
163  * subsequent request.
164  */
165
166 /*
167  * mballoc operates on the following data:
168  *  - on-disk bitmap
169  *  - in-core buddy (actually includes buddy and bitmap)
170  *  - preallocation descriptors (PAs)
171  *
172  * there are two types of preallocations:
173  *  - inode
174  *    assiged to specific inode and can be used for this inode only.
175  *    it describes part of inode's space preallocated to specific
176  *    physical blocks. any block from that preallocated can be used
177  *    independent. the descriptor just tracks number of blocks left
178  *    unused. so, before taking some block from descriptor, one must
179  *    make sure corresponded logical block isn't allocated yet. this
180  *    also means that freeing any block within descriptor's range
181  *    must discard all preallocated blocks.
182  *  - locality group
183  *    assigned to specific locality group which does not translate to
184  *    permanent set of inodes: inode can join and leave group. space
185  *    from this type of preallocation can be used for any inode. thus
186  *    it's consumed from the beginning to the end.
187  *
188  * relation between them can be expressed as:
189  *    in-core buddy = on-disk bitmap + preallocation descriptors
190  *
191  * this mean blocks mballoc considers used are:
192  *  - allocated blocks (persistent)
193  *  - preallocated blocks (non-persistent)
194  *
195  * consistency in mballoc world means that at any time a block is either
196  * free or used in ALL structures. notice: "any time" should not be read
197  * literally -- time is discrete and delimited by locks.
198  *
199  *  to keep it simple, we don't use block numbers, instead we count number of
200  *  blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
201  *
202  * all operations can be expressed as:
203  *  - init buddy:                       buddy = on-disk + PAs
204  *  - new PA:                           buddy += N; PA = N
205  *  - use inode PA:                     on-disk += N; PA -= N
206  *  - discard inode PA                  buddy -= on-disk - PA; PA = 0
207  *  - use locality group PA             on-disk += N; PA -= N
208  *  - discard locality group PA         buddy -= PA; PA = 0
209  *  note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
210  *        is used in real operation because we can't know actual used
211  *        bits from PA, only from on-disk bitmap
212  *
213  * if we follow this strict logic, then all operations above should be atomic.
214  * given some of them can block, we'd have to use something like semaphores
215  * killing performance on high-end SMP hardware. let's try to relax it using
216  * the following knowledge:
217  *  1) if buddy is referenced, it's already initialized
218  *  2) while block is used in buddy and the buddy is referenced,
219  *     nobody can re-allocate that block
220  *  3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
221  *     bit set and PA claims same block, it's OK. IOW, one can set bit in
222  *     on-disk bitmap if buddy has same bit set or/and PA covers corresponded
223  *     block
224  *
225  * so, now we're building a concurrency table:
226  *  - init buddy vs.
227  *    - new PA
228  *      blocks for PA are allocated in the buddy, buddy must be referenced
229  *      until PA is linked to allocation group to avoid concurrent buddy init
230  *    - use inode PA
231  *      we need to make sure that either on-disk bitmap or PA has uptodate data
232  *      given (3) we care that PA-=N operation doesn't interfere with init
233  *    - discard inode PA
234  *      the simplest way would be to have buddy initialized by the discard
235  *    - use locality group PA
236  *      again PA-=N must be serialized with init
237  *    - discard locality group PA
238  *      the simplest way would be to have buddy initialized by the discard
239  *  - new PA vs.
240  *    - use inode PA
241  *      i_data_sem serializes them
242  *    - discard inode PA
243  *      discard process must wait until PA isn't used by another process
244  *    - use locality group PA
245  *      some mutex should serialize them
246  *    - discard locality group PA
247  *      discard process must wait until PA isn't used by another process
248  *  - use inode PA
249  *    - use inode PA
250  *      i_data_sem or another mutex should serializes them
251  *    - discard inode PA
252  *      discard process must wait until PA isn't used by another process
253  *    - use locality group PA
254  *      nothing wrong here -- they're different PAs covering different blocks
255  *    - discard locality group PA
256  *      discard process must wait until PA isn't used by another process
257  *
258  * now we're ready to make few consequences:
259  *  - PA is referenced and while it is no discard is possible
260  *  - PA is referenced until block isn't marked in on-disk bitmap
261  *  - PA changes only after on-disk bitmap
262  *  - discard must not compete with init. either init is done before
263  *    any discard or they're serialized somehow
264  *  - buddy init as sum of on-disk bitmap and PAs is done atomically
265  *
266  * a special case when we've used PA to emptiness. no need to modify buddy
267  * in this case, but we should care about concurrent init
268  *
269  */
270
271  /*
272  * Logic in few words:
273  *
274  *  - allocation:
275  *    load group
276  *    find blocks
277  *    mark bits in on-disk bitmap
278  *    release group
279  *
280  *  - use preallocation:
281  *    find proper PA (per-inode or group)
282  *    load group
283  *    mark bits in on-disk bitmap
284  *    release group
285  *    release PA
286  *
287  *  - free:
288  *    load group
289  *    mark bits in on-disk bitmap
290  *    release group
291  *
292  *  - discard preallocations in group:
293  *    mark PAs deleted
294  *    move them onto local list
295  *    load on-disk bitmap
296  *    load group
297  *    remove PA from object (inode or locality group)
298  *    mark free blocks in-core
299  *
300  *  - discard inode's preallocations:
301  */
302
303 /*
304  * Locking rules
305  *
306  * Locks:
307  *  - bitlock on a group        (group)
308  *  - object (inode/locality)   (object)
309  *  - per-pa lock               (pa)
310  *
311  * Paths:
312  *  - new pa
313  *    object
314  *    group
315  *
316  *  - find and use pa:
317  *    pa
318  *
319  *  - release consumed pa:
320  *    pa
321  *    group
322  *    object
323  *
324  *  - generate in-core bitmap:
325  *    group
326  *        pa
327  *
328  *  - discard all for given object (inode, locality group):
329  *    object
330  *        pa
331  *    group
332  *
333  *  - discard all for given group:
334  *    group
335  *        pa
336  *    group
337  *        object
338  *
339  */
340 static struct kmem_cache *ext4_pspace_cachep;
341 static struct kmem_cache *ext4_ac_cachep;
342 static struct kmem_cache *ext4_free_ext_cachep;
343
344 /* We create slab caches for groupinfo data structures based on the
345  * superblock block size.  There will be one per mounted filesystem for
346  * each unique s_blocksize_bits */
347 #define NR_GRPINFO_CACHES 8
348 static struct kmem_cache *ext4_groupinfo_caches[NR_GRPINFO_CACHES];
349
350 static const char *ext4_groupinfo_slab_names[NR_GRPINFO_CACHES] = {
351         "ext4_groupinfo_1k", "ext4_groupinfo_2k", "ext4_groupinfo_4k",
352         "ext4_groupinfo_8k", "ext4_groupinfo_16k", "ext4_groupinfo_32k",
353         "ext4_groupinfo_64k", "ext4_groupinfo_128k"
354 };
355
356 static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
357                                         ext4_group_t group);
358 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
359                                                 ext4_group_t group);
360 static void release_blocks_on_commit(journal_t *journal, transaction_t *txn);
361
362 static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
363 {
364 #if BITS_PER_LONG == 64
365         *bit += ((unsigned long) addr & 7UL) << 3;
366         addr = (void *) ((unsigned long) addr & ~7UL);
367 #elif BITS_PER_LONG == 32
368         *bit += ((unsigned long) addr & 3UL) << 3;
369         addr = (void *) ((unsigned long) addr & ~3UL);
370 #else
371 #error "how many bits you are?!"
372 #endif
373         return addr;
374 }
375
376 static inline int mb_test_bit(int bit, void *addr)
377 {
378         /*
379          * ext4_test_bit on architecture like powerpc
380          * needs unsigned long aligned address
381          */
382         addr = mb_correct_addr_and_bit(&bit, addr);
383         return ext4_test_bit(bit, addr);
384 }
385
386 static inline void mb_set_bit(int bit, void *addr)
387 {
388         addr = mb_correct_addr_and_bit(&bit, addr);
389         ext4_set_bit(bit, addr);
390 }
391
392 static inline void mb_clear_bit(int bit, void *addr)
393 {
394         addr = mb_correct_addr_and_bit(&bit, addr);
395         ext4_clear_bit(bit, addr);
396 }
397
398 static inline int mb_find_next_zero_bit(void *addr, int max, int start)
399 {
400         int fix = 0, ret, tmpmax;
401         addr = mb_correct_addr_and_bit(&fix, addr);
402         tmpmax = max + fix;
403         start += fix;
404
405         ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
406         if (ret > max)
407                 return max;
408         return ret;
409 }
410
411 static inline int mb_find_next_bit(void *addr, int max, int start)
412 {
413         int fix = 0, ret, tmpmax;
414         addr = mb_correct_addr_and_bit(&fix, addr);
415         tmpmax = max + fix;
416         start += fix;
417
418         ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
419         if (ret > max)
420                 return max;
421         return ret;
422 }
423
424 static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
425 {
426         char *bb;
427
428         BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
429         BUG_ON(max == NULL);
430
431         if (order > e4b->bd_blkbits + 1) {
432                 *max = 0;
433                 return NULL;
434         }
435
436         /* at order 0 we see each particular block */
437         if (order == 0) {
438                 *max = 1 << (e4b->bd_blkbits + 3);
439                 return EXT4_MB_BITMAP(e4b);
440         }
441
442         bb = EXT4_MB_BUDDY(e4b) + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
443         *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];
444
445         return bb;
446 }
447
448 #ifdef DOUBLE_CHECK
449 static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,
450                            int first, int count)
451 {
452         int i;
453         struct super_block *sb = e4b->bd_sb;
454
455         if (unlikely(e4b->bd_info->bb_bitmap == NULL))
456                 return;
457         assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
458         for (i = 0; i < count; i++) {
459                 if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
460                         ext4_fsblk_t blocknr;
461
462                         blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
463                         blocknr += EXT4_C2B(EXT4_SB(sb), first + i);
464                         ext4_grp_locked_error(sb, e4b->bd_group,
465                                               inode ? inode->i_ino : 0,
466                                               blocknr,
467                                               "freeing block already freed "
468                                               "(bit %u)",
469                                               first + i);
470                 }
471                 mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
472         }
473 }
474
475 static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)
476 {
477         int i;
478
479         if (unlikely(e4b->bd_info->bb_bitmap == NULL))
480                 return;
481         assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
482         for (i = 0; i < count; i++) {
483                 BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
484                 mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
485         }
486 }
487
488 static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
489 {
490         if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
491                 unsigned char *b1, *b2;
492                 int i;
493                 b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
494                 b2 = (unsigned char *) bitmap;
495                 for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
496                         if (b1[i] != b2[i]) {
497                                 ext4_msg(e4b->bd_sb, KERN_ERR,
498                                          "corruption in group %u "
499                                          "at byte %u(%u): %x in copy != %x "
500                                          "on disk/prealloc",
501                                          e4b->bd_group, i, i * 8, b1[i], b2[i]);
502                                 BUG();
503                         }
504                 }
505         }
506 }
507
508 #else
509 static inline void mb_free_blocks_double(struct inode *inode,
510                                 struct ext4_buddy *e4b, int first, int count)
511 {
512         return;
513 }
514 static inline void mb_mark_used_double(struct ext4_buddy *e4b,
515                                                 int first, int count)
516 {
517         return;
518 }
519 static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
520 {
521         return;
522 }
523 #endif
524
525 #ifdef AGGRESSIVE_CHECK
526
527 #define MB_CHECK_ASSERT(assert)                                         \
528 do {                                                                    \
529         if (!(assert)) {                                                \
530                 printk(KERN_EMERG                                       \
531                         "Assertion failure in %s() at %s:%d: \"%s\"\n", \
532                         function, file, line, # assert);                \
533                 BUG();                                                  \
534         }                                                               \
535 } while (0)
536
537 static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
538                                 const char *function, int line)
539 {
540         struct super_block *sb = e4b->bd_sb;
541         int order = e4b->bd_blkbits + 1;
542         int max;
543         int max2;
544         int i;
545         int j;
546         int k;
547         int count;
548         struct ext4_group_info *grp;
549         int fragments = 0;
550         int fstart;
551         struct list_head *cur;
552         void *buddy;
553         void *buddy2;
554
555         {
556                 static int mb_check_counter;
557                 if (mb_check_counter++ % 100 != 0)
558                         return 0;
559         }
560
561         while (order > 1) {
562                 buddy = mb_find_buddy(e4b, order, &max);
563                 MB_CHECK_ASSERT(buddy);
564                 buddy2 = mb_find_buddy(e4b, order - 1, &max2);
565                 MB_CHECK_ASSERT(buddy2);
566                 MB_CHECK_ASSERT(buddy != buddy2);
567                 MB_CHECK_ASSERT(max * 2 == max2);
568
569                 count = 0;
570                 for (i = 0; i < max; i++) {
571
572                         if (mb_test_bit(i, buddy)) {
573                                 /* only single bit in buddy2 may be 1 */
574                                 if (!mb_test_bit(i << 1, buddy2)) {
575                                         MB_CHECK_ASSERT(
576                                                 mb_test_bit((i<<1)+1, buddy2));
577                                 } else if (!mb_test_bit((i << 1) + 1, buddy2)) {
578                                         MB_CHECK_ASSERT(
579                                                 mb_test_bit(i << 1, buddy2));
580                                 }
581                                 continue;
582                         }
583
584                         /* both bits in buddy2 must be 1 */
585                         MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
586                         MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
587
588                         for (j = 0; j < (1 << order); j++) {
589                                 k = (i * (1 << order)) + j;
590                                 MB_CHECK_ASSERT(
591                                         !mb_test_bit(k, EXT4_MB_BITMAP(e4b)));
592                         }
593                         count++;
594                 }
595                 MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
596                 order--;
597         }
598
599         fstart = -1;
600         buddy = mb_find_buddy(e4b, 0, &max);
601         for (i = 0; i < max; i++) {
602                 if (!mb_test_bit(i, buddy)) {
603                         MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
604                         if (fstart == -1) {
605                                 fragments++;
606                                 fstart = i;
607                         }
608                         continue;
609                 }
610                 fstart = -1;
611                 /* check used bits only */
612                 for (j = 0; j < e4b->bd_blkbits + 1; j++) {
613                         buddy2 = mb_find_buddy(e4b, j, &max2);
614                         k = i >> j;
615                         MB_CHECK_ASSERT(k < max2);
616                         MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
617                 }
618         }
619         MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
620         MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);
621
622         grp = ext4_get_group_info(sb, e4b->bd_group);
623         list_for_each(cur, &grp->bb_prealloc_list) {
624                 ext4_group_t groupnr;
625                 struct ext4_prealloc_space *pa;
626                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
627                 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
628                 MB_CHECK_ASSERT(groupnr == e4b->bd_group);
629                 for (i = 0; i < pa->pa_len; i++)
630                         MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
631         }
632         return 0;
633 }
634 #undef MB_CHECK_ASSERT
635 #define mb_check_buddy(e4b) __mb_check_buddy(e4b,       \
636                                         __FILE__, __func__, __LINE__)
637 #else
638 #define mb_check_buddy(e4b)
639 #endif
640
641 /*
642  * Divide blocks started from @first with length @len into
643  * smaller chunks with power of 2 blocks.
644  * Clear the bits in bitmap which the blocks of the chunk(s) covered,
645  * then increase bb_counters[] for corresponded chunk size.
646  */
647 static void ext4_mb_mark_free_simple(struct super_block *sb,
648                                 void *buddy, ext4_grpblk_t first, ext4_grpblk_t len,
649                                         struct ext4_group_info *grp)
650 {
651         struct ext4_sb_info *sbi = EXT4_SB(sb);
652         ext4_grpblk_t min;
653         ext4_grpblk_t max;
654         ext4_grpblk_t chunk;
655         unsigned int border;
656
657         BUG_ON(len > EXT4_CLUSTERS_PER_GROUP(sb));
658
659         border = 2 << sb->s_blocksize_bits;
660
661         while (len > 0) {
662                 /* find how many blocks can be covered since this position */
663                 max = ffs(first | border) - 1;
664
665                 /* find how many blocks of power 2 we need to mark */
666                 min = fls(len) - 1;
667
668                 if (max < min)
669                         min = max;
670                 chunk = 1 << min;
671
672                 /* mark multiblock chunks only */
673                 grp->bb_counters[min]++;
674                 if (min > 0)
675                         mb_clear_bit(first >> min,
676                                      buddy + sbi->s_mb_offsets[min]);
677
678                 len -= chunk;
679                 first += chunk;
680         }
681 }
682
683 /*
684  * Cache the order of the largest free extent we have available in this block
685  * group.
686  */
687 static void
688 mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
689 {
690         int i;
691         int bits;
692
693         grp->bb_largest_free_order = -1; /* uninit */
694
695         bits = sb->s_blocksize_bits + 1;
696         for (i = bits; i >= 0; i--) {
697                 if (grp->bb_counters[i] > 0) {
698                         grp->bb_largest_free_order = i;
699                         break;
700                 }
701         }
702 }
703
704 static noinline_for_stack
705 void ext4_mb_generate_buddy(struct super_block *sb,
706                                 void *buddy, void *bitmap, ext4_group_t group)
707 {
708         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
709         ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
710         ext4_grpblk_t i = 0;
711         ext4_grpblk_t first;
712         ext4_grpblk_t len;
713         unsigned free = 0;
714         unsigned fragments = 0;
715         unsigned long long period = get_cycles();
716
717         /* initialize buddy from bitmap which is aggregation
718          * of on-disk bitmap and preallocations */
719         i = mb_find_next_zero_bit(bitmap, max, 0);
720         grp->bb_first_free = i;
721         while (i < max) {
722                 fragments++;
723                 first = i;
724                 i = mb_find_next_bit(bitmap, max, i);
725                 len = i - first;
726                 free += len;
727                 if (len > 1)
728                         ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
729                 else
730                         grp->bb_counters[0]++;
731                 if (i < max)
732                         i = mb_find_next_zero_bit(bitmap, max, i);
733         }
734         grp->bb_fragments = fragments;
735
736         if (free != grp->bb_free) {
737                 ext4_grp_locked_error(sb, group, 0, 0,
738                                       "%u clusters in bitmap, %u in gd",
739                                       free, grp->bb_free);
740                 /*
741                  * If we intent to continue, we consider group descritor
742                  * corrupt and update bb_free using bitmap value
743                  */
744                 grp->bb_free = free;
745         }
746         mb_set_largest_free_order(sb, grp);
747
748         clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));
749
750         period = get_cycles() - period;
751         spin_lock(&EXT4_SB(sb)->s_bal_lock);
752         EXT4_SB(sb)->s_mb_buddies_generated++;
753         EXT4_SB(sb)->s_mb_generation_time += period;
754         spin_unlock(&EXT4_SB(sb)->s_bal_lock);
755 }
756
757 /* The buddy information is attached the buddy cache inode
758  * for convenience. The information regarding each group
759  * is loaded via ext4_mb_load_buddy. The information involve
760  * block bitmap and buddy information. The information are
761  * stored in the inode as
762  *
763  * {                        page                        }
764  * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
765  *
766  *
767  * one block each for bitmap and buddy information.
768  * So for each group we take up 2 blocks. A page can
769  * contain blocks_per_page (PAGE_CACHE_SIZE / blocksize)  blocks.
770  * So it can have information regarding groups_per_page which
771  * is blocks_per_page/2
772  *
773  * Locking note:  This routine takes the block group lock of all groups
774  * for this page; do not hold this lock when calling this routine!
775  */
776
777 static int ext4_mb_init_cache(struct page *page, char *incore)
778 {
779         ext4_group_t ngroups;
780         int blocksize;
781         int blocks_per_page;
782         int groups_per_page;
783         int err = 0;
784         int i;
785         ext4_group_t first_group;
786         int first_block;
787         struct super_block *sb;
788         struct buffer_head *bhs;
789         struct buffer_head **bh;
790         struct inode *inode;
791         char *data;
792         char *bitmap;
793         struct ext4_group_info *grinfo;
794
795         mb_debug(1, "init page %lu\n", page->index);
796
797         inode = page->mapping->host;
798         sb = inode->i_sb;
799         ngroups = ext4_get_groups_count(sb);
800         blocksize = 1 << inode->i_blkbits;
801         blocks_per_page = PAGE_CACHE_SIZE / blocksize;
802
803         groups_per_page = blocks_per_page >> 1;
804         if (groups_per_page == 0)
805                 groups_per_page = 1;
806
807         /* allocate buffer_heads to read bitmaps */
808         if (groups_per_page > 1) {
809                 err = -ENOMEM;
810                 i = sizeof(struct buffer_head *) * groups_per_page;
811                 bh = kzalloc(i, GFP_NOFS);
812                 if (bh == NULL)
813                         goto out;
814         } else
815                 bh = &bhs;
816
817         first_group = page->index * blocks_per_page / 2;
818
819         /* read all groups the page covers into the cache */
820         for (i = 0; i < groups_per_page; i++) {
821                 struct ext4_group_desc *desc;
822
823                 if (first_group + i >= ngroups)
824                         break;
825
826                 grinfo = ext4_get_group_info(sb, first_group + i);
827                 /*
828                  * If page is uptodate then we came here after online resize
829                  * which added some new uninitialized group info structs, so
830                  * we must skip all initialized uptodate buddies on the page,
831                  * which may be currently in use by an allocating task.
832                  */
833                 if (PageUptodate(page) && !EXT4_MB_GRP_NEED_INIT(grinfo)) {
834                         bh[i] = NULL;
835                         continue;
836                 }
837
838                 err = -EIO;
839                 desc = ext4_get_group_desc(sb, first_group + i, NULL);
840                 if (desc == NULL)
841                         goto out;
842
843                 err = -ENOMEM;
844                 bh[i] = sb_getblk(sb, ext4_block_bitmap(sb, desc));
845                 if (bh[i] == NULL)
846                         goto out;
847
848                 if (bitmap_uptodate(bh[i]))
849                         continue;
850
851                 lock_buffer(bh[i]);
852                 if (bitmap_uptodate(bh[i])) {
853                         unlock_buffer(bh[i]);
854                         continue;
855                 }
856                 ext4_lock_group(sb, first_group + i);
857                 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
858                         ext4_init_block_bitmap(sb, bh[i],
859                                                 first_group + i, desc);
860                         set_bitmap_uptodate(bh[i]);
861                         set_buffer_uptodate(bh[i]);
862                         ext4_unlock_group(sb, first_group + i);
863                         unlock_buffer(bh[i]);
864                         continue;
865                 }
866                 ext4_unlock_group(sb, first_group + i);
867                 if (buffer_uptodate(bh[i])) {
868                         /*
869                          * if not uninit if bh is uptodate,
870                          * bitmap is also uptodate
871                          */
872                         set_bitmap_uptodate(bh[i]);
873                         unlock_buffer(bh[i]);
874                         continue;
875                 }
876                 get_bh(bh[i]);
877                 /*
878                  * submit the buffer_head for read. We can
879                  * safely mark the bitmap as uptodate now.
880                  * We do it here so the bitmap uptodate bit
881                  * get set with buffer lock held.
882                  */
883                 set_bitmap_uptodate(bh[i]);
884                 bh[i]->b_end_io = end_buffer_read_sync;
885                 submit_bh(READ, bh[i]);
886                 mb_debug(1, "read bitmap for group %u\n", first_group + i);
887         }
888
889         /* wait for I/O completion */
890         for (i = 0; i < groups_per_page; i++)
891                 if (bh[i])
892                         wait_on_buffer(bh[i]);
893
894         err = -EIO;
895         for (i = 0; i < groups_per_page; i++)
896                 if (bh[i] && !buffer_uptodate(bh[i]))
897                         goto out;
898
899         err = 0;
900         first_block = page->index * blocks_per_page;
901         for (i = 0; i < blocks_per_page; i++) {
902                 int group;
903
904                 group = (first_block + i) >> 1;
905                 if (group >= ngroups)
906                         break;
907
908                 if (!bh[group - first_group])
909                         /* skip initialized uptodate buddy */
910                         continue;
911
912                 /*
913                  * data carry information regarding this
914                  * particular group in the format specified
915                  * above
916                  *
917                  */
918                 data = page_address(page) + (i * blocksize);
919                 bitmap = bh[group - first_group]->b_data;
920
921                 /*
922                  * We place the buddy block and bitmap block
923                  * close together
924                  */
925                 if ((first_block + i) & 1) {
926                         /* this is block of buddy */
927                         BUG_ON(incore == NULL);
928                         mb_debug(1, "put buddy for group %u in page %lu/%x\n",
929                                 group, page->index, i * blocksize);
930                         trace_ext4_mb_buddy_bitmap_load(sb, group);
931                         grinfo = ext4_get_group_info(sb, group);
932                         grinfo->bb_fragments = 0;
933                         memset(grinfo->bb_counters, 0,
934                                sizeof(*grinfo->bb_counters) *
935                                 (sb->s_blocksize_bits+2));
936                         /*
937                          * incore got set to the group block bitmap below
938                          */
939                         ext4_lock_group(sb, group);
940                         /* init the buddy */
941                         memset(data, 0xff, blocksize);
942                         ext4_mb_generate_buddy(sb, data, incore, group);
943                         ext4_unlock_group(sb, group);
944                         incore = NULL;
945                 } else {
946                         /* this is block of bitmap */
947                         BUG_ON(incore != NULL);
948                         mb_debug(1, "put bitmap for group %u in page %lu/%x\n",
949                                 group, page->index, i * blocksize);
950                         trace_ext4_mb_bitmap_load(sb, group);
951
952                         /* see comments in ext4_mb_put_pa() */
953                         ext4_lock_group(sb, group);
954                         memcpy(data, bitmap, blocksize);
955
956                         /* mark all preallocated blks used in in-core bitmap */
957                         ext4_mb_generate_from_pa(sb, data, group);
958                         ext4_mb_generate_from_freelist(sb, data, group);
959                         ext4_unlock_group(sb, group);
960
961                         /* set incore so that the buddy information can be
962                          * generated using this
963                          */
964                         incore = data;
965                 }
966         }
967         SetPageUptodate(page);
968
969 out:
970         if (bh) {
971                 for (i = 0; i < groups_per_page; i++)
972                         brelse(bh[i]);
973                 if (bh != &bhs)
974                         kfree(bh);
975         }
976         return err;
977 }
978
979 /*
980  * Lock the buddy and bitmap pages. This make sure other parallel init_group
981  * on the same buddy page doesn't happen whild holding the buddy page lock.
982  * Return locked buddy and bitmap pages on e4b struct. If buddy and bitmap
983  * are on the same page e4b->bd_buddy_page is NULL and return value is 0.
984  */
985 static int ext4_mb_get_buddy_page_lock(struct super_block *sb,
986                 ext4_group_t group, struct ext4_buddy *e4b)
987 {
988         struct inode *inode = EXT4_SB(sb)->s_buddy_cache;
989         int block, pnum, poff;
990         int blocks_per_page;
991         struct page *page;
992
993         e4b->bd_buddy_page = NULL;
994         e4b->bd_bitmap_page = NULL;
995
996         blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
997         /*
998          * the buddy cache inode stores the block bitmap
999          * and buddy information in consecutive blocks.
1000          * So for each group we need two blocks.
1001          */
1002         block = group * 2;
1003         pnum = block / blocks_per_page;
1004         poff = block % blocks_per_page;
1005         page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1006         if (!page)
1007                 return -EIO;
1008         BUG_ON(page->mapping != inode->i_mapping);
1009         e4b->bd_bitmap_page = page;
1010         e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
1011
1012         if (blocks_per_page >= 2) {
1013                 /* buddy and bitmap are on the same page */
1014                 return 0;
1015         }
1016
1017         block++;
1018         pnum = block / blocks_per_page;
1019         poff = block % blocks_per_page;
1020         page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1021         if (!page)
1022                 return -EIO;
1023         BUG_ON(page->mapping != inode->i_mapping);
1024         e4b->bd_buddy_page = page;
1025         return 0;
1026 }
1027
1028 static void ext4_mb_put_buddy_page_lock(struct ext4_buddy *e4b)
1029 {
1030         if (e4b->bd_bitmap_page) {
1031                 unlock_page(e4b->bd_bitmap_page);
1032                 page_cache_release(e4b->bd_bitmap_page);
1033         }
1034         if (e4b->bd_buddy_page) {
1035                 unlock_page(e4b->bd_buddy_page);
1036                 page_cache_release(e4b->bd_buddy_page);
1037         }
1038 }
1039
1040 /*
1041  * Locking note:  This routine calls ext4_mb_init_cache(), which takes the
1042  * block group lock of all groups for this page; do not hold the BG lock when
1043  * calling this routine!
1044  */
1045 static noinline_for_stack
1046 int ext4_mb_init_group(struct super_block *sb, ext4_group_t group)
1047 {
1048
1049         struct ext4_group_info *this_grp;
1050         struct ext4_buddy e4b;
1051         struct page *page;
1052         int ret = 0;
1053
1054         mb_debug(1, "init group %u\n", group);
1055         this_grp = ext4_get_group_info(sb, group);
1056         /*
1057          * This ensures that we don't reinit the buddy cache
1058          * page which map to the group from which we are already
1059          * allocating. If we are looking at the buddy cache we would
1060          * have taken a reference using ext4_mb_load_buddy and that
1061          * would have pinned buddy page to page cache.
1062          */
1063         ret = ext4_mb_get_buddy_page_lock(sb, group, &e4b);
1064         if (ret || !EXT4_MB_GRP_NEED_INIT(this_grp)) {
1065                 /*
1066                  * somebody initialized the group
1067                  * return without doing anything
1068                  */
1069                 goto err;
1070         }
1071
1072         page = e4b.bd_bitmap_page;
1073         ret = ext4_mb_init_cache(page, NULL);
1074         if (ret)
1075                 goto err;
1076         if (!PageUptodate(page)) {
1077                 ret = -EIO;
1078                 goto err;
1079         }
1080         mark_page_accessed(page);
1081
1082         if (e4b.bd_buddy_page == NULL) {
1083                 /*
1084                  * If both the bitmap and buddy are in
1085                  * the same page we don't need to force
1086                  * init the buddy
1087                  */
1088                 ret = 0;
1089                 goto err;
1090         }
1091         /* init buddy cache */
1092         page = e4b.bd_buddy_page;
1093         ret = ext4_mb_init_cache(page, e4b.bd_bitmap);
1094         if (ret)
1095                 goto err;
1096         if (!PageUptodate(page)) {
1097                 ret = -EIO;
1098                 goto err;
1099         }
1100         mark_page_accessed(page);
1101 err:
1102         ext4_mb_put_buddy_page_lock(&e4b);
1103         return ret;
1104 }
1105
1106 /*
1107  * Locking note:  This routine calls ext4_mb_init_cache(), which takes the
1108  * block group lock of all groups for this page; do not hold the BG lock when
1109  * calling this routine!
1110  */
1111 static noinline_for_stack int
1112 ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
1113                                         struct ext4_buddy *e4b)
1114 {
1115         int blocks_per_page;
1116         int block;
1117         int pnum;
1118         int poff;
1119         struct page *page;
1120         int ret;
1121         struct ext4_group_info *grp;
1122         struct ext4_sb_info *sbi = EXT4_SB(sb);
1123         struct inode *inode = sbi->s_buddy_cache;
1124
1125         mb_debug(1, "load group %u\n", group);
1126
1127         blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
1128         grp = ext4_get_group_info(sb, group);
1129
1130         e4b->bd_blkbits = sb->s_blocksize_bits;
1131         e4b->bd_info = grp;
1132         e4b->bd_sb = sb;
1133         e4b->bd_group = group;
1134         e4b->bd_buddy_page = NULL;
1135         e4b->bd_bitmap_page = NULL;
1136
1137         if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
1138                 /*
1139                  * we need full data about the group
1140                  * to make a good selection
1141                  */
1142                 ret = ext4_mb_init_group(sb, group);
1143                 if (ret)
1144                         return ret;
1145         }
1146
1147         /*
1148          * the buddy cache inode stores the block bitmap
1149          * and buddy information in consecutive blocks.
1150          * So for each group we need two blocks.
1151          */
1152         block = group * 2;
1153         pnum = block / blocks_per_page;
1154         poff = block % blocks_per_page;
1155
1156         /* we could use find_or_create_page(), but it locks page
1157          * what we'd like to avoid in fast path ... */
1158         page = find_get_page(inode->i_mapping, pnum);
1159         if (page == NULL || !PageUptodate(page)) {
1160                 if (page)
1161                         /*
1162                          * drop the page reference and try
1163                          * to get the page with lock. If we
1164                          * are not uptodate that implies
1165                          * somebody just created the page but
1166                          * is yet to initialize the same. So
1167                          * wait for it to initialize.
1168                          */
1169                         page_cache_release(page);
1170                 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1171                 if (page) {
1172                         BUG_ON(page->mapping != inode->i_mapping);
1173                         if (!PageUptodate(page)) {
1174                                 ret = ext4_mb_init_cache(page, NULL);
1175                                 if (ret) {
1176                                         unlock_page(page);
1177                                         goto err;
1178                                 }
1179                                 mb_cmp_bitmaps(e4b, page_address(page) +
1180                                                (poff * sb->s_blocksize));
1181                         }
1182                         unlock_page(page);
1183                 }
1184         }
1185         if (page == NULL || !PageUptodate(page)) {
1186                 ret = -EIO;
1187                 goto err;
1188         }
1189         e4b->bd_bitmap_page = page;
1190         e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
1191         mark_page_accessed(page);
1192
1193         block++;
1194         pnum = block / blocks_per_page;
1195         poff = block % blocks_per_page;
1196
1197         page = find_get_page(inode->i_mapping, pnum);
1198         if (page == NULL || !PageUptodate(page)) {
1199                 if (page)
1200                         page_cache_release(page);
1201                 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1202                 if (page) {
1203                         BUG_ON(page->mapping != inode->i_mapping);
1204                         if (!PageUptodate(page)) {
1205                                 ret = ext4_mb_init_cache(page, e4b->bd_bitmap);
1206                                 if (ret) {
1207                                         unlock_page(page);
1208                                         goto err;
1209                                 }
1210                         }
1211                         unlock_page(page);
1212                 }
1213         }
1214         if (page == NULL || !PageUptodate(page)) {
1215                 ret = -EIO;
1216                 goto err;
1217         }
1218         e4b->bd_buddy_page = page;
1219         e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
1220         mark_page_accessed(page);
1221
1222         BUG_ON(e4b->bd_bitmap_page == NULL);
1223         BUG_ON(e4b->bd_buddy_page == NULL);
1224
1225         return 0;
1226
1227 err:
1228         if (page)
1229                 page_cache_release(page);
1230         if (e4b->bd_bitmap_page)
1231                 page_cache_release(e4b->bd_bitmap_page);
1232         if (e4b->bd_buddy_page)
1233                 page_cache_release(e4b->bd_buddy_page);
1234         e4b->bd_buddy = NULL;
1235         e4b->bd_bitmap = NULL;
1236         return ret;
1237 }
1238
1239 static void ext4_mb_unload_buddy(struct ext4_buddy *e4b)
1240 {
1241         if (e4b->bd_bitmap_page)
1242                 page_cache_release(e4b->bd_bitmap_page);
1243         if (e4b->bd_buddy_page)
1244                 page_cache_release(e4b->bd_buddy_page);
1245 }
1246
1247
1248 static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
1249 {
1250         int order = 1;
1251         void *bb;
1252
1253         BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
1254         BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
1255
1256         bb = EXT4_MB_BUDDY(e4b);
1257         while (order <= e4b->bd_blkbits + 1) {
1258                 block = block >> 1;
1259                 if (!mb_test_bit(block, bb)) {
1260                         /* this block is part of buddy of order 'order' */
1261                         return order;
1262                 }
1263                 bb += 1 << (e4b->bd_blkbits - order);
1264                 order++;
1265         }
1266         return 0;
1267 }
1268
1269 static void mb_clear_bits(void *bm, int cur, int len)
1270 {
1271         __u32 *addr;
1272
1273         len = cur + len;
1274         while (cur < len) {
1275                 if ((cur & 31) == 0 && (len - cur) >= 32) {
1276                         /* fast path: clear whole word at once */
1277                         addr = bm + (cur >> 3);
1278                         *addr = 0;
1279                         cur += 32;
1280                         continue;
1281                 }
1282                 mb_clear_bit(cur, bm);
1283                 cur++;
1284         }
1285 }
1286
1287 void ext4_set_bits(void *bm, int cur, int len)
1288 {
1289         __u32 *addr;
1290
1291         len = cur + len;
1292         while (cur < len) {
1293                 if ((cur & 31) == 0 && (len - cur) >= 32) {
1294                         /* fast path: set whole word at once */
1295                         addr = bm + (cur >> 3);
1296                         *addr = 0xffffffff;
1297                         cur += 32;
1298                         continue;
1299                 }
1300                 mb_set_bit(cur, bm);
1301                 cur++;
1302         }
1303 }
1304
1305 static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
1306                           int first, int count)
1307 {
1308         int block = 0;
1309         int max = 0;
1310         int order;
1311         void *buddy;
1312         void *buddy2;
1313         struct super_block *sb = e4b->bd_sb;
1314
1315         if (WARN_ON(count == 0))
1316                 return;
1317         BUG_ON(first + count > (sb->s_blocksize << 3));
1318         assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
1319         mb_check_buddy(e4b);
1320         mb_free_blocks_double(inode, e4b, first, count);
1321
1322         e4b->bd_info->bb_free += count;
1323         if (first < e4b->bd_info->bb_first_free)
1324                 e4b->bd_info->bb_first_free = first;
1325
1326         /* let's maintain fragments counter */
1327         if (first != 0)
1328                 block = !mb_test_bit(first - 1, EXT4_MB_BITMAP(e4b));
1329         if (first + count < EXT4_SB(sb)->s_mb_maxs[0])
1330                 max = !mb_test_bit(first + count, EXT4_MB_BITMAP(e4b));
1331         if (block && max)
1332                 e4b->bd_info->bb_fragments--;
1333         else if (!block && !max)
1334                 e4b->bd_info->bb_fragments++;
1335
1336         /* let's maintain buddy itself */
1337         while (count-- > 0) {
1338                 block = first++;
1339                 order = 0;
1340
1341                 if (!mb_test_bit(block, EXT4_MB_BITMAP(e4b))) {
1342                         ext4_fsblk_t blocknr;
1343
1344                         blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
1345                         blocknr += EXT4_C2B(EXT4_SB(sb), block);
1346                         ext4_grp_locked_error(sb, e4b->bd_group,
1347                                               inode ? inode->i_ino : 0,
1348                                               blocknr,
1349                                               "freeing already freed block "
1350                                               "(bit %u)", block);
1351                 }
1352                 mb_clear_bit(block, EXT4_MB_BITMAP(e4b));
1353                 e4b->bd_info->bb_counters[order]++;
1354
1355                 /* start of the buddy */
1356                 buddy = mb_find_buddy(e4b, order, &max);
1357
1358                 do {
1359                         block &= ~1UL;
1360                         if (mb_test_bit(block, buddy) ||
1361                                         mb_test_bit(block + 1, buddy))
1362                                 break;
1363
1364                         /* both the buddies are free, try to coalesce them */
1365                         buddy2 = mb_find_buddy(e4b, order + 1, &max);
1366
1367                         if (!buddy2)
1368                                 break;
1369
1370                         if (order > 0) {
1371                                 /* for special purposes, we don't set
1372                                  * free bits in bitmap */
1373                                 mb_set_bit(block, buddy);
1374                                 mb_set_bit(block + 1, buddy);
1375                         }
1376                         e4b->bd_info->bb_counters[order]--;
1377                         e4b->bd_info->bb_counters[order]--;
1378
1379                         block = block >> 1;
1380                         order++;
1381                         e4b->bd_info->bb_counters[order]++;
1382
1383                         mb_clear_bit(block, buddy2);
1384                         buddy = buddy2;
1385                 } while (1);
1386         }
1387         mb_set_largest_free_order(sb, e4b->bd_info);
1388         mb_check_buddy(e4b);
1389 }
1390
1391 static int mb_find_extent(struct ext4_buddy *e4b, int order, int block,
1392                                 int needed, struct ext4_free_extent *ex)
1393 {
1394         int next = block;
1395         int max;
1396         void *buddy;
1397
1398         assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1399         BUG_ON(ex == NULL);
1400
1401         buddy = mb_find_buddy(e4b, order, &max);
1402         BUG_ON(buddy == NULL);
1403         BUG_ON(block >= max);
1404         if (mb_test_bit(block, buddy)) {
1405                 ex->fe_len = 0;
1406                 ex->fe_start = 0;
1407                 ex->fe_group = 0;
1408                 return 0;
1409         }
1410
1411         /* FIXME dorp order completely ? */
1412         if (likely(order == 0)) {
1413                 /* find actual order */
1414                 order = mb_find_order_for_block(e4b, block);
1415                 block = block >> order;
1416         }
1417
1418         ex->fe_len = 1 << order;
1419         ex->fe_start = block << order;
1420         ex->fe_group = e4b->bd_group;
1421
1422         /* calc difference from given start */
1423         next = next - ex->fe_start;
1424         ex->fe_len -= next;
1425         ex->fe_start += next;
1426
1427         while (needed > ex->fe_len &&
1428                (buddy = mb_find_buddy(e4b, order, &max))) {
1429
1430                 if (block + 1 >= max)
1431                         break;
1432
1433                 next = (block + 1) * (1 << order);
1434                 if (mb_test_bit(next, EXT4_MB_BITMAP(e4b)))
1435                         break;
1436
1437                 order = mb_find_order_for_block(e4b, next);
1438
1439                 block = next >> order;
1440                 ex->fe_len += 1 << order;
1441         }
1442
1443         BUG_ON(ex->fe_start + ex->fe_len > (1 << (e4b->bd_blkbits + 3)));
1444         return ex->fe_len;
1445 }
1446
1447 static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
1448 {
1449         int ord;
1450         int mlen = 0;
1451         int max = 0;
1452         int cur;
1453         int start = ex->fe_start;
1454         int len = ex->fe_len;
1455         unsigned ret = 0;
1456         int len0 = len;
1457         void *buddy;
1458
1459         BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
1460         BUG_ON(e4b->bd_group != ex->fe_group);
1461         assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1462         mb_check_buddy(e4b);
1463         mb_mark_used_double(e4b, start, len);
1464
1465         e4b->bd_info->bb_free -= len;
1466         if (e4b->bd_info->bb_first_free == start)
1467                 e4b->bd_info->bb_first_free += len;
1468
1469         /* let's maintain fragments counter */
1470         if (start != 0)
1471                 mlen = !mb_test_bit(start - 1, EXT4_MB_BITMAP(e4b));
1472         if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
1473                 max = !mb_test_bit(start + len, EXT4_MB_BITMAP(e4b));
1474         if (mlen && max)
1475                 e4b->bd_info->bb_fragments++;
1476         else if (!mlen && !max)
1477                 e4b->bd_info->bb_fragments--;
1478
1479         /* let's maintain buddy itself */
1480         while (len) {
1481                 ord = mb_find_order_for_block(e4b, start);
1482
1483                 if (((start >> ord) << ord) == start && len >= (1 << ord)) {
1484                         /* the whole chunk may be allocated at once! */
1485                         mlen = 1 << ord;
1486                         buddy = mb_find_buddy(e4b, ord, &max);
1487                         BUG_ON((start >> ord) >= max);
1488                         mb_set_bit(start >> ord, buddy);
1489                         e4b->bd_info->bb_counters[ord]--;
1490                         start += mlen;
1491                         len -= mlen;
1492                         BUG_ON(len < 0);
1493                         continue;
1494                 }
1495
1496                 /* store for history */
1497                 if (ret == 0)
1498                         ret = len | (ord << 16);
1499
1500                 /* we have to split large buddy */
1501                 BUG_ON(ord <= 0);
1502                 buddy = mb_find_buddy(e4b, ord, &max);
1503                 mb_set_bit(start >> ord, buddy);
1504                 e4b->bd_info->bb_counters[ord]--;
1505
1506                 ord--;
1507                 cur = (start >> ord) & ~1U;
1508                 buddy = mb_find_buddy(e4b, ord, &max);
1509                 mb_clear_bit(cur, buddy);
1510                 mb_clear_bit(cur + 1, buddy);
1511                 e4b->bd_info->bb_counters[ord]++;
1512                 e4b->bd_info->bb_counters[ord]++;
1513         }
1514         mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
1515
1516         ext4_set_bits(EXT4_MB_BITMAP(e4b), ex->fe_start, len0);
1517         mb_check_buddy(e4b);
1518
1519         return ret;
1520 }
1521
1522 /*
1523  * Must be called under group lock!
1524  */
1525 static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
1526                                         struct ext4_buddy *e4b)
1527 {
1528         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1529         int ret;
1530
1531         BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
1532         BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1533
1534         ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
1535         ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
1536         ret = mb_mark_used(e4b, &ac->ac_b_ex);
1537
1538         /* preallocation can change ac_b_ex, thus we store actually
1539          * allocated blocks for history */
1540         ac->ac_f_ex = ac->ac_b_ex;
1541
1542         ac->ac_status = AC_STATUS_FOUND;
1543         ac->ac_tail = ret & 0xffff;
1544         ac->ac_buddy = ret >> 16;
1545
1546         /*
1547          * take the page reference. We want the page to be pinned
1548          * so that we don't get a ext4_mb_init_cache_call for this
1549          * group until we update the bitmap. That would mean we
1550          * double allocate blocks. The reference is dropped
1551          * in ext4_mb_release_context
1552          */
1553         ac->ac_bitmap_page = e4b->bd_bitmap_page;
1554         get_page(ac->ac_bitmap_page);
1555         ac->ac_buddy_page = e4b->bd_buddy_page;
1556         get_page(ac->ac_buddy_page);
1557         /* store last allocated for subsequent stream allocation */
1558         if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
1559                 spin_lock(&sbi->s_md_lock);
1560                 sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
1561                 sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
1562                 spin_unlock(&sbi->s_md_lock);
1563         }
1564 }
1565
1566 /*
1567  * regular allocator, for general purposes allocation
1568  */
1569
1570 static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
1571                                         struct ext4_buddy *e4b,
1572                                         int finish_group)
1573 {
1574         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1575         struct ext4_free_extent *bex = &ac->ac_b_ex;
1576         struct ext4_free_extent *gex = &ac->ac_g_ex;
1577         struct ext4_free_extent ex;
1578         int max;
1579
1580         if (ac->ac_status == AC_STATUS_FOUND)
1581                 return;
1582         /*
1583          * We don't want to scan for a whole year
1584          */
1585         if (ac->ac_found > sbi->s_mb_max_to_scan &&
1586                         !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1587                 ac->ac_status = AC_STATUS_BREAK;
1588                 return;
1589         }
1590
1591         /*
1592          * Haven't found good chunk so far, let's continue
1593          */
1594         if (bex->fe_len < gex->fe_len)
1595                 return;
1596
1597         if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
1598                         && bex->fe_group == e4b->bd_group) {
1599                 /* recheck chunk's availability - we don't know
1600                  * when it was found (within this lock-unlock
1601                  * period or not) */
1602                 max = mb_find_extent(e4b, 0, bex->fe_start, gex->fe_len, &ex);
1603                 if (max >= gex->fe_len) {
1604                         ext4_mb_use_best_found(ac, e4b);
1605                         return;
1606                 }
1607         }
1608 }
1609
1610 /*
1611  * The routine checks whether found extent is good enough. If it is,
1612  * then the extent gets marked used and flag is set to the context
1613  * to stop scanning. Otherwise, the extent is compared with the
1614  * previous found extent and if new one is better, then it's stored
1615  * in the context. Later, the best found extent will be used, if
1616  * mballoc can't find good enough extent.
1617  *
1618  * FIXME: real allocation policy is to be designed yet!
1619  */
1620 static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
1621                                         struct ext4_free_extent *ex,
1622                                         struct ext4_buddy *e4b)
1623 {
1624         struct ext4_free_extent *bex = &ac->ac_b_ex;
1625         struct ext4_free_extent *gex = &ac->ac_g_ex;
1626
1627         BUG_ON(ex->fe_len <= 0);
1628         BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
1629         BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
1630         BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
1631
1632         ac->ac_found++;
1633
1634         /*
1635          * The special case - take what you catch first
1636          */
1637         if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1638                 *bex = *ex;
1639                 ext4_mb_use_best_found(ac, e4b);
1640                 return;
1641         }
1642
1643         /*
1644          * Let's check whether the chuck is good enough
1645          */
1646         if (ex->fe_len == gex->fe_len) {
1647                 *bex = *ex;
1648                 ext4_mb_use_best_found(ac, e4b);
1649                 return;
1650         }
1651
1652         /*
1653          * If this is first found extent, just store it in the context
1654          */
1655         if (bex->fe_len == 0) {
1656                 *bex = *ex;
1657                 return;
1658         }
1659
1660         /*
1661          * If new found extent is better, store it in the context
1662          */
1663         if (bex->fe_len < gex->fe_len) {
1664                 /* if the request isn't satisfied, any found extent
1665                  * larger than previous best one is better */
1666                 if (ex->fe_len > bex->fe_len)
1667                         *bex = *ex;
1668         } else if (ex->fe_len > gex->fe_len) {
1669                 /* if the request is satisfied, then we try to find
1670                  * an extent that still satisfy the request, but is
1671                  * smaller than previous one */
1672                 if (ex->fe_len < bex->fe_len)
1673                         *bex = *ex;
1674         }
1675
1676         ext4_mb_check_limits(ac, e4b, 0);
1677 }
1678
1679 static noinline_for_stack
1680 int ext4_mb_try_best_found(struct ext4_allocation_context *ac,
1681                                         struct ext4_buddy *e4b)
1682 {
1683         struct ext4_free_extent ex = ac->ac_b_ex;
1684         ext4_group_t group = ex.fe_group;
1685         int max;
1686         int err;
1687
1688         BUG_ON(ex.fe_len <= 0);
1689         err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1690         if (err)
1691                 return err;
1692
1693         ext4_lock_group(ac->ac_sb, group);
1694         max = mb_find_extent(e4b, 0, ex.fe_start, ex.fe_len, &ex);
1695
1696         if (max > 0) {
1697                 ac->ac_b_ex = ex;
1698                 ext4_mb_use_best_found(ac, e4b);
1699         }
1700
1701         ext4_unlock_group(ac->ac_sb, group);
1702         ext4_mb_unload_buddy(e4b);
1703
1704         return 0;
1705 }
1706
1707 static noinline_for_stack
1708 int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
1709                                 struct ext4_buddy *e4b)
1710 {
1711         ext4_group_t group = ac->ac_g_ex.fe_group;
1712         int max;
1713         int err;
1714         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1715         struct ext4_free_extent ex;
1716
1717         if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
1718                 return 0;
1719
1720         err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1721         if (err)
1722                 return err;
1723
1724         ext4_lock_group(ac->ac_sb, group);
1725         max = mb_find_extent(e4b, 0, ac->ac_g_ex.fe_start,
1726                              ac->ac_g_ex.fe_len, &ex);
1727
1728         if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
1729                 ext4_fsblk_t start;
1730
1731                 start = ext4_group_first_block_no(ac->ac_sb, e4b->bd_group) +
1732                         ex.fe_start;
1733                 /* use do_div to get remainder (would be 64-bit modulo) */
1734                 if (do_div(start, sbi->s_stripe) == 0) {
1735                         ac->ac_found++;
1736                         ac->ac_b_ex = ex;
1737                         ext4_mb_use_best_found(ac, e4b);
1738                 }
1739         } else if (max >= ac->ac_g_ex.fe_len) {
1740                 BUG_ON(ex.fe_len <= 0);
1741                 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1742                 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1743                 ac->ac_found++;
1744                 ac->ac_b_ex = ex;
1745                 ext4_mb_use_best_found(ac, e4b);
1746         } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
1747                 /* Sometimes, caller may want to merge even small
1748                  * number of blocks to an existing extent */
1749                 BUG_ON(ex.fe_len <= 0);
1750                 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1751                 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1752                 ac->ac_found++;
1753                 ac->ac_b_ex = ex;
1754                 ext4_mb_use_best_found(ac, e4b);
1755         }
1756         ext4_unlock_group(ac->ac_sb, group);
1757         ext4_mb_unload_buddy(e4b);
1758
1759         return 0;
1760 }
1761
1762 /*
1763  * The routine scans buddy structures (not bitmap!) from given order
1764  * to max order and tries to find big enough chunk to satisfy the req
1765  */
1766 static noinline_for_stack
1767 void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
1768                                         struct ext4_buddy *e4b)
1769 {
1770         struct super_block *sb = ac->ac_sb;
1771         struct ext4_group_info *grp = e4b->bd_info;
1772         void *buddy;
1773         int i;
1774         int k;
1775         int max;
1776
1777         BUG_ON(ac->ac_2order <= 0);
1778         for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
1779                 if (grp->bb_counters[i] == 0)
1780                         continue;
1781
1782                 buddy = mb_find_buddy(e4b, i, &max);
1783                 BUG_ON(buddy == NULL);
1784
1785                 k = mb_find_next_zero_bit(buddy, max, 0);
1786                 BUG_ON(k >= max);
1787
1788                 ac->ac_found++;
1789
1790                 ac->ac_b_ex.fe_len = 1 << i;
1791                 ac->ac_b_ex.fe_start = k << i;
1792                 ac->ac_b_ex.fe_group = e4b->bd_group;
1793
1794                 ext4_mb_use_best_found(ac, e4b);
1795
1796                 BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);
1797
1798                 if (EXT4_SB(sb)->s_mb_stats)
1799                         atomic_inc(&EXT4_SB(sb)->s_bal_2orders);
1800
1801                 break;
1802         }
1803 }
1804
1805 /*
1806  * The routine scans the group and measures all found extents.
1807  * In order to optimize scanning, caller must pass number of
1808  * free blocks in the group, so the routine can know upper limit.
1809  */
1810 static noinline_for_stack
1811 void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
1812                                         struct ext4_buddy *e4b)
1813 {
1814         struct super_block *sb = ac->ac_sb;
1815         void *bitmap = EXT4_MB_BITMAP(e4b);
1816         struct ext4_free_extent ex;
1817         int i;
1818         int free;
1819
1820         free = e4b->bd_info->bb_free;
1821         BUG_ON(free <= 0);
1822
1823         i = e4b->bd_info->bb_first_free;
1824
1825         while (free && ac->ac_status == AC_STATUS_CONTINUE) {
1826                 i = mb_find_next_zero_bit(bitmap,
1827                                                 EXT4_CLUSTERS_PER_GROUP(sb), i);
1828                 if (i >= EXT4_CLUSTERS_PER_GROUP(sb)) {
1829                         /*
1830                          * IF we have corrupt bitmap, we won't find any
1831                          * free blocks even though group info says we
1832                          * we have free blocks
1833                          */
1834                         ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
1835                                         "%d free clusters as per "
1836                                         "group info. But bitmap says 0",
1837                                         free);
1838                         break;
1839                 }
1840
1841                 mb_find_extent(e4b, 0, i, ac->ac_g_ex.fe_len, &ex);
1842                 BUG_ON(ex.fe_len <= 0);
1843                 if (free < ex.fe_len) {
1844                         ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
1845                                         "%d free clusters as per "
1846                                         "group info. But got %d blocks",
1847                                         free, ex.fe_len);
1848                         /*
1849                          * The number of free blocks differs. This mostly
1850                          * indicate that the bitmap is corrupt. So exit
1851                          * without claiming the space.
1852                          */
1853                         break;
1854                 }
1855
1856                 ext4_mb_measure_extent(ac, &ex, e4b);
1857
1858                 i += ex.fe_len;
1859                 free -= ex.fe_len;
1860         }
1861
1862         ext4_mb_check_limits(ac, e4b, 1);
1863 }
1864
1865 /*
1866  * This is a special case for storages like raid5
1867  * we try to find stripe-aligned chunks for stripe-size-multiple requests
1868  */
1869 static noinline_for_stack
1870 void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
1871                                  struct ext4_buddy *e4b)
1872 {
1873         struct super_block *sb = ac->ac_sb;
1874         struct ext4_sb_info *sbi = EXT4_SB(sb);
1875         void *bitmap = EXT4_MB_BITMAP(e4b);
1876         struct ext4_free_extent ex;
1877         ext4_fsblk_t first_group_block;
1878         ext4_fsblk_t a;
1879         ext4_grpblk_t i;
1880         int max;
1881
1882         BUG_ON(sbi->s_stripe == 0);
1883
1884         /* find first stripe-aligned block in group */
1885         first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);
1886
1887         a = first_group_block + sbi->s_stripe - 1;
1888         do_div(a, sbi->s_stripe);
1889         i = (a * sbi->s_stripe) - first_group_block;
1890
1891         while (i < EXT4_CLUSTERS_PER_GROUP(sb)) {
1892                 if (!mb_test_bit(i, bitmap)) {
1893                         max = mb_find_extent(e4b, 0, i, sbi->s_stripe, &ex);
1894                         if (max >= sbi->s_stripe) {
1895                                 ac->ac_found++;
1896                                 ac->ac_b_ex = ex;
1897                                 ext4_mb_use_best_found(ac, e4b);
1898                                 break;
1899                         }
1900                 }
1901                 i += sbi->s_stripe;
1902         }
1903 }
1904
1905 /* This is now called BEFORE we load the buddy bitmap. */
1906 static int ext4_mb_good_group(struct ext4_allocation_context *ac,
1907                                 ext4_group_t group, int cr)
1908 {
1909         unsigned free, fragments;
1910         int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));
1911         struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
1912
1913         BUG_ON(cr < 0 || cr >= 4);
1914
1915         /* We only do this if the grp has never been initialized */
1916         if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
1917                 int ret = ext4_mb_init_group(ac->ac_sb, group);
1918                 if (ret)
1919                         return 0;
1920         }
1921
1922         free = grp->bb_free;
1923         fragments = grp->bb_fragments;
1924         if (free == 0)
1925                 return 0;
1926         if (fragments == 0)
1927                 return 0;
1928
1929         switch (cr) {
1930         case 0:
1931                 BUG_ON(ac->ac_2order == 0);
1932
1933                 if (grp->bb_largest_free_order < ac->ac_2order)
1934                         return 0;
1935
1936                 /* Avoid using the first bg of a flexgroup for data files */
1937                 if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&
1938                     (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) &&
1939                     ((group % flex_size) == 0))
1940                         return 0;
1941
1942                 return 1;
1943         case 1:
1944                 if ((free / fragments) >= ac->ac_g_ex.fe_len)
1945                         return 1;
1946                 break;
1947         case 2:
1948                 if (free >= ac->ac_g_ex.fe_len)
1949                         return 1;
1950                 break;
1951         case 3:
1952                 return 1;
1953         default:
1954                 BUG();
1955         }
1956
1957         return 0;
1958 }
1959
1960 static noinline_for_stack int
1961 ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
1962 {
1963         ext4_group_t ngroups, group, i;
1964         int cr;
1965         int err = 0;
1966         struct ext4_sb_info *sbi;
1967         struct super_block *sb;
1968         struct ext4_buddy e4b;
1969
1970         sb = ac->ac_sb;
1971         sbi = EXT4_SB(sb);
1972         ngroups = ext4_get_groups_count(sb);
1973         /* non-extent files are limited to low blocks/groups */
1974         if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))
1975                 ngroups = sbi->s_blockfile_groups;
1976
1977         BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1978
1979         /* first, try the goal */
1980         err = ext4_mb_find_by_goal(ac, &e4b);
1981         if (err || ac->ac_status == AC_STATUS_FOUND)
1982                 goto out;
1983
1984         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
1985                 goto out;
1986
1987         /*
1988          * ac->ac2_order is set only if the fe_len is a power of 2
1989          * if ac2_order is set we also set criteria to 0 so that we
1990          * try exact allocation using buddy.
1991          */
1992         i = fls(ac->ac_g_ex.fe_len);
1993         ac->ac_2order = 0;
1994         /*
1995          * We search using buddy data only if the order of the request
1996          * is greater than equal to the sbi_s_mb_order2_reqs
1997          * You can tune it via /sys/fs/ext4/<partition>/mb_order2_req
1998          */
1999         if (i >= sbi->s_mb_order2_reqs) {
2000                 /*
2001                  * This should tell if fe_len is exactly power of 2
2002                  */
2003                 if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)
2004                         ac->ac_2order = i - 1;
2005         }
2006
2007         /* if stream allocation is enabled, use global goal */
2008         if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
2009                 /* TBD: may be hot point */
2010                 spin_lock(&sbi->s_md_lock);
2011                 ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
2012                 ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
2013                 spin_unlock(&sbi->s_md_lock);
2014         }
2015
2016         /* Let's just scan groups to find more-less suitable blocks */
2017         cr = ac->ac_2order ? 0 : 1;
2018         /*
2019          * cr == 0 try to get exact allocation,
2020          * cr == 3  try to get anything
2021          */
2022 repeat:
2023         for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
2024                 ac->ac_criteria = cr;
2025                 /*
2026                  * searching for the right group start
2027                  * from the goal value specified
2028                  */
2029                 group = ac->ac_g_ex.fe_group;
2030
2031                 for (i = 0; i < ngroups; group++, i++) {
2032                         /*
2033                          * Artificially restricted ngroups for non-extent
2034                          * files makes group > ngroups possible on first loop.
2035                          */
2036                         if (group >= ngroups)
2037                                 group = 0;
2038
2039                         /* This now checks without needing the buddy page */
2040                         if (!ext4_mb_good_group(ac, group, cr))
2041                                 continue;
2042
2043                         err = ext4_mb_load_buddy(sb, group, &e4b);
2044                         if (err)
2045                                 goto out;
2046
2047                         ext4_lock_group(sb, group);
2048
2049                         /*
2050                          * We need to check again after locking the
2051                          * block group
2052                          */
2053                         if (!ext4_mb_good_group(ac, group, cr)) {
2054                                 ext4_unlock_group(sb, group);
2055                                 ext4_mb_unload_buddy(&e4b);
2056                                 continue;
2057                         }
2058
2059                         ac->ac_groups_scanned++;
2060                         if (cr == 0)
2061                                 ext4_mb_simple_scan_group(ac, &e4b);
2062                         else if (cr == 1 && sbi->s_stripe &&
2063                                         !(ac->ac_g_ex.fe_len % sbi->s_stripe))
2064                                 ext4_mb_scan_aligned(ac, &e4b);
2065                         else
2066                                 ext4_mb_complex_scan_group(ac, &e4b);
2067
2068                         ext4_unlock_group(sb, group);
2069                         ext4_mb_unload_buddy(&e4b);
2070
2071                         if (ac->ac_status != AC_STATUS_CONTINUE)
2072                                 break;
2073                 }
2074         }
2075
2076         if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
2077             !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2078                 /*
2079                  * We've been searching too long. Let's try to allocate
2080                  * the best chunk we've found so far
2081                  */
2082
2083                 ext4_mb_try_best_found(ac, &e4b);
2084                 if (ac->ac_status != AC_STATUS_FOUND) {
2085                         /*
2086                          * Someone more lucky has already allocated it.
2087                          * The only thing we can do is just take first
2088                          * found block(s)
2089                         printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n");
2090                          */
2091                         ac->ac_b_ex.fe_group = 0;
2092                         ac->ac_b_ex.fe_start = 0;
2093                         ac->ac_b_ex.fe_len = 0;
2094                         ac->ac_status = AC_STATUS_CONTINUE;
2095                         ac->ac_flags |= EXT4_MB_HINT_FIRST;
2096                         cr = 3;
2097                         atomic_inc(&sbi->s_mb_lost_chunks);
2098                         goto repeat;
2099                 }
2100         }
2101 out:
2102         return err;
2103 }
2104
2105 static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
2106 {
2107         struct super_block *sb = seq->private;
2108         ext4_group_t group;
2109
2110         if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2111                 return NULL;
2112         group = *pos + 1;
2113         return (void *) ((unsigned long) group);
2114 }
2115
2116 static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
2117 {
2118         struct super_block *sb = seq->private;
2119         ext4_group_t group;
2120
2121         ++*pos;
2122         if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2123                 return NULL;
2124         group = *pos + 1;
2125         return (void *) ((unsigned long) group);
2126 }
2127
2128 static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
2129 {
2130         struct super_block *sb = seq->private;
2131         ext4_group_t group = (ext4_group_t) ((unsigned long) v);
2132         int i;
2133         int err;
2134         struct ext4_buddy e4b;
2135         struct sg {
2136                 struct ext4_group_info info;
2137                 ext4_grpblk_t counters[EXT4_MAX_BLOCK_LOG_SIZE + 2];
2138         } sg;
2139
2140         group--;
2141         if (group == 0)
2142                 seq_printf(seq, "#%-5s: %-5s %-5s %-5s "
2143                                 "[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s "
2144                                   "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n",
2145                            "group", "free", "frags", "first",
2146                            "2^0", "2^1", "2^2", "2^3", "2^4", "2^5", "2^6",
2147                            "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13");
2148
2149         i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
2150                 sizeof(struct ext4_group_info);
2151         err = ext4_mb_load_buddy(sb, group, &e4b);
2152         if (err) {
2153                 seq_printf(seq, "#%-5u: I/O error\n", group);
2154                 return 0;
2155         }
2156         ext4_lock_group(sb, group);
2157         memcpy(&sg, ext4_get_group_info(sb, group), i);
2158         ext4_unlock_group(sb, group);
2159         ext4_mb_unload_buddy(&e4b);
2160
2161         seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,
2162                         sg.info.bb_fragments, sg.info.bb_first_free);
2163         for (i = 0; i <= 13; i++)
2164                 seq_printf(seq, " %-5u", i <= sb->s_blocksize_bits + 1 ?
2165                                 sg.info.bb_counters[i] : 0);
2166         seq_printf(seq, " ]\n");
2167
2168         return 0;
2169 }
2170
2171 static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
2172 {
2173 }
2174
2175 static const struct seq_operations ext4_mb_seq_groups_ops = {
2176         .start  = ext4_mb_seq_groups_start,
2177         .next   = ext4_mb_seq_groups_next,
2178         .stop   = ext4_mb_seq_groups_stop,
2179         .show   = ext4_mb_seq_groups_show,
2180 };
2181
2182 static int ext4_mb_seq_groups_open(struct inode *inode, struct file *file)
2183 {
2184         struct super_block *sb = PDE(inode)->data;
2185         int rc;
2186
2187         rc = seq_open(file, &ext4_mb_seq_groups_ops);
2188         if (rc == 0) {
2189                 struct seq_file *m = file->private_data;
2190                 m->private = sb;
2191         }
2192         return rc;
2193
2194 }
2195
2196 static const struct file_operations ext4_mb_seq_groups_fops = {
2197         .owner          = THIS_MODULE,
2198         .open           = ext4_mb_seq_groups_open,
2199         .read           = seq_read,
2200         .llseek         = seq_lseek,
2201         .release        = seq_release,
2202 };
2203
2204 static struct kmem_cache *get_groupinfo_cache(int blocksize_bits)
2205 {
2206         int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
2207         struct kmem_cache *cachep = ext4_groupinfo_caches[cache_index];
2208
2209         BUG_ON(!cachep);
2210         return cachep;
2211 }
2212
2213 /* Create and initialize ext4_group_info data for the given group. */
2214 int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
2215                           struct ext4_group_desc *desc)
2216 {
2217         int i;
2218         int metalen = 0;
2219         struct ext4_sb_info *sbi = EXT4_SB(sb);
2220         struct ext4_group_info **meta_group_info;
2221         struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2222
2223         /*
2224          * First check if this group is the first of a reserved block.
2225          * If it's true, we have to allocate a new table of pointers
2226          * to ext4_group_info structures
2227          */
2228         if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
2229                 metalen = sizeof(*meta_group_info) <<
2230                         EXT4_DESC_PER_BLOCK_BITS(sb);
2231                 meta_group_info = kmalloc(metalen, GFP_KERNEL);
2232                 if (meta_group_info == NULL) {
2233                         ext4_msg(sb, KERN_ERR, "EXT4-fs: can't allocate mem "
2234                                  "for a buddy group");
2235                         goto exit_meta_group_info;
2236                 }
2237                 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] =
2238                         meta_group_info;
2239         }
2240
2241         meta_group_info =
2242                 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)];
2243         i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);
2244
2245         meta_group_info[i] = kmem_cache_alloc(cachep, GFP_KERNEL);
2246         if (meta_group_info[i] == NULL) {
2247                 ext4_msg(sb, KERN_ERR, "EXT4-fs: can't allocate buddy mem");
2248                 goto exit_group_info;
2249         }
2250         memset(meta_group_info[i], 0, kmem_cache_size(cachep));
2251         set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
2252                 &(meta_group_info[i]->bb_state));
2253
2254         /*
2255          * initialize bb_free to be able to skip
2256          * empty groups without initialization
2257          */
2258         if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
2259                 meta_group_info[i]->bb_free =
2260                         ext4_free_clusters_after_init(sb, group, desc);
2261         } else {
2262                 meta_group_info[i]->bb_free =
2263                         ext4_free_group_clusters(sb, desc);
2264         }
2265
2266         INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
2267         init_rwsem(&meta_group_info[i]->alloc_sem);
2268         meta_group_info[i]->bb_free_root = RB_ROOT;
2269         meta_group_info[i]->bb_largest_free_order = -1;  /* uninit */
2270
2271 #ifdef DOUBLE_CHECK
2272         {
2273                 struct buffer_head *bh;
2274                 meta_group_info[i]->bb_bitmap =
2275                         kmalloc(sb->s_blocksize, GFP_KERNEL);
2276                 BUG_ON(meta_group_info[i]->bb_bitmap == NULL);
2277                 bh = ext4_read_block_bitmap(sb, group);
2278                 BUG_ON(bh == NULL);
2279                 memcpy(meta_group_info[i]->bb_bitmap, bh->b_data,
2280                         sb->s_blocksize);
2281                 put_bh(bh);
2282         }
2283 #endif
2284
2285         return 0;
2286
2287 exit_group_info:
2288         /* If a meta_group_info table has been allocated, release it now */
2289         if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
2290                 kfree(sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)]);
2291                 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] = NULL;
2292         }
2293 exit_meta_group_info:
2294         return -ENOMEM;
2295 } /* ext4_mb_add_groupinfo */
2296
2297 static int ext4_mb_init_backend(struct super_block *sb)
2298 {
2299         ext4_group_t ngroups = ext4_get_groups_count(sb);
2300         ext4_group_t i;
2301         struct ext4_sb_info *sbi = EXT4_SB(sb);
2302         struct ext4_super_block *es = sbi->s_es;
2303         int num_meta_group_infos;
2304         int num_meta_group_infos_max;
2305         int array_size;
2306         struct ext4_group_desc *desc;
2307         struct kmem_cache *cachep;
2308
2309         /* This is the number of blocks used by GDT */
2310         num_meta_group_infos = (ngroups + EXT4_DESC_PER_BLOCK(sb) -
2311                                 1) >> EXT4_DESC_PER_BLOCK_BITS(sb);
2312
2313         /*
2314          * This is the total number of blocks used by GDT including
2315          * the number of reserved blocks for GDT.
2316          * The s_group_info array is allocated with this value
2317          * to allow a clean online resize without a complex
2318          * manipulation of pointer.
2319          * The drawback is the unused memory when no resize
2320          * occurs but it's very low in terms of pages
2321          * (see comments below)
2322          * Need to handle this properly when META_BG resizing is allowed
2323          */
2324         num_meta_group_infos_max = num_meta_group_infos +
2325                                 le16_to_cpu(es->s_reserved_gdt_blocks);
2326
2327         /*
2328          * array_size is the size of s_group_info array. We round it
2329          * to the next power of two because this approximation is done
2330          * internally by kmalloc so we can have some more memory
2331          * for free here (e.g. may be used for META_BG resize).
2332          */
2333         array_size = 1;
2334         while (array_size < sizeof(*sbi->s_group_info) *
2335                num_meta_group_infos_max)
2336                 array_size = array_size << 1;
2337         /* An 8TB filesystem with 64-bit pointers requires a 4096 byte
2338          * kmalloc. A 128kb malloc should suffice for a 256TB filesystem.
2339          * So a two level scheme suffices for now. */
2340         sbi->s_group_info = ext4_kvzalloc(array_size, GFP_KERNEL);
2341         if (sbi->s_group_info == NULL) {
2342                 ext4_msg(sb, KERN_ERR, "can't allocate buddy meta group");
2343                 return -ENOMEM;
2344         }
2345         sbi->s_buddy_cache = new_inode(sb);
2346         if (sbi->s_buddy_cache == NULL) {
2347                 ext4_msg(sb, KERN_ERR, "can't get new inode");
2348                 goto err_freesgi;
2349         }
2350         /* To avoid potentially colliding with an valid on-disk inode number,
2351          * use EXT4_BAD_INO for the buddy cache inode number.  This inode is
2352          * not in the inode hash, so it should never be found by iget(), but
2353          * this will avoid confusion if it ever shows up during debugging. */
2354         sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;
2355         EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
2356         for (i = 0; i < ngroups; i++) {
2357                 desc = ext4_get_group_desc(sb, i, NULL);
2358                 if (desc == NULL) {
2359                         ext4_msg(sb, KERN_ERR, "can't read descriptor %u", i);
2360                         goto err_freebuddy;
2361                 }
2362                 if (ext4_mb_add_groupinfo(sb, i, desc) != 0)
2363                         goto err_freebuddy;
2364         }
2365
2366         return 0;
2367
2368 err_freebuddy:
2369         cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2370         while (i-- > 0)
2371                 kmem_cache_free(cachep, ext4_get_group_info(sb, i));
2372         i = num_meta_group_infos;
2373         while (i-- > 0)
2374                 kfree(sbi->s_group_info[i]);
2375         iput(sbi->s_buddy_cache);
2376 err_freesgi:
2377         ext4_kvfree(sbi->s_group_info);
2378         return -ENOMEM;
2379 }
2380
2381 static void ext4_groupinfo_destroy_slabs(void)
2382 {
2383         int i;
2384
2385         for (i = 0; i < NR_GRPINFO_CACHES; i++) {
2386                 if (ext4_groupinfo_caches[i])
2387                         kmem_cache_destroy(ext4_groupinfo_caches[i]);
2388                 ext4_groupinfo_caches[i] = NULL;
2389         }
2390 }
2391
2392 static int ext4_groupinfo_create_slab(size_t size)
2393 {
2394         static DEFINE_MUTEX(ext4_grpinfo_slab_create_mutex);
2395         int slab_size;
2396         int blocksize_bits = order_base_2(size);
2397         int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
2398         struct kmem_cache *cachep;
2399
2400         if (cache_index >= NR_GRPINFO_CACHES)
2401                 return -EINVAL;
2402
2403         if (unlikely(cache_index < 0))
2404                 cache_index = 0;
2405
2406         mutex_lock(&ext4_grpinfo_slab_create_mutex);
2407         if (ext4_groupinfo_caches[cache_index]) {
2408                 mutex_unlock(&ext4_grpinfo_slab_create_mutex);
2409                 return 0;       /* Already created */
2410         }
2411
2412         slab_size = offsetof(struct ext4_group_info,
2413                                 bb_counters[blocksize_bits + 2]);
2414
2415         cachep = kmem_cache_create(ext4_groupinfo_slab_names[cache_index],
2416                                         slab_size, 0, SLAB_RECLAIM_ACCOUNT,
2417                                         NULL);
2418
2419         ext4_groupinfo_caches[cache_index] = cachep;
2420
2421         mutex_unlock(&ext4_grpinfo_slab_create_mutex);
2422         if (!cachep) {
2423                 printk(KERN_EMERG
2424                        "EXT4-fs: no memory for groupinfo slab cache\n");
2425                 return -ENOMEM;
2426         }
2427
2428         return 0;
2429 }
2430
2431 int ext4_mb_init(struct super_block *sb, int needs_recovery)
2432 {
2433         struct ext4_sb_info *sbi = EXT4_SB(sb);
2434         unsigned i, j;
2435         unsigned offset;
2436         unsigned max;
2437         int ret;
2438
2439         i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_offsets);
2440
2441         sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
2442         if (sbi->s_mb_offsets == NULL) {
2443                 ret = -ENOMEM;
2444                 goto out;
2445         }
2446
2447         i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_maxs);
2448         sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
2449         if (sbi->s_mb_maxs == NULL) {
2450                 ret = -ENOMEM;
2451                 goto out;
2452         }
2453
2454         ret = ext4_groupinfo_create_slab(sb->s_blocksize);
2455         if (ret < 0)
2456                 goto out;
2457
2458         /* order 0 is regular bitmap */
2459         sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
2460         sbi->s_mb_offsets[0] = 0;
2461
2462         i = 1;
2463         offset = 0;
2464         max = sb->s_blocksize << 2;
2465         do {
2466                 sbi->s_mb_offsets[i] = offset;
2467                 sbi->s_mb_maxs[i] = max;
2468                 offset += 1 << (sb->s_blocksize_bits - i);
2469                 max = max >> 1;
2470                 i++;
2471         } while (i <= sb->s_blocksize_bits + 1);
2472
2473         spin_lock_init(&sbi->s_md_lock);
2474         spin_lock_init(&sbi->s_bal_lock);
2475
2476         sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
2477         sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
2478         sbi->s_mb_stats = MB_DEFAULT_STATS;
2479         sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
2480         sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
2481         /*
2482          * The default group preallocation is 512, which for 4k block
2483          * sizes translates to 2 megabytes.  However for bigalloc file
2484          * systems, this is probably too big (i.e, if the cluster size
2485          * is 1 megabyte, then group preallocation size becomes half a
2486          * gigabyte!).  As a default, we will keep a two megabyte
2487          * group pralloc size for cluster sizes up to 64k, and after
2488          * that, we will force a minimum group preallocation size of
2489          * 32 clusters.  This translates to 8 megs when the cluster
2490          * size is 256k, and 32 megs when the cluster size is 1 meg,
2491          * which seems reasonable as a default.
2492          */
2493         sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>
2494                                        sbi->s_cluster_bits, 32);
2495         /*
2496          * If there is a s_stripe > 1, then we set the s_mb_group_prealloc
2497          * to the lowest multiple of s_stripe which is bigger than
2498          * the s_mb_group_prealloc as determined above. We want
2499          * the preallocation size to be an exact multiple of the
2500          * RAID stripe size so that preallocations don't fragment
2501          * the stripes.
2502          */
2503         if (sbi->s_stripe > 1) {
2504                 sbi->s_mb_group_prealloc = roundup(
2505                         sbi->s_mb_group_prealloc, sbi->s_stripe);
2506         }
2507
2508         sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
2509         if (sbi->s_locality_groups == NULL) {
2510                 ret = -ENOMEM;
2511                 goto out_free_groupinfo_slab;
2512         }
2513         for_each_possible_cpu(i) {
2514                 struct ext4_locality_group *lg;
2515                 lg = per_cpu_ptr(sbi->s_locality_groups, i);
2516                 mutex_init(&lg->lg_mutex);
2517                 for (j = 0; j < PREALLOC_TB_SIZE; j++)
2518                         INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);
2519                 spin_lock_init(&lg->lg_prealloc_lock);
2520         }
2521
2522         /* init file for buddy data */
2523         ret = ext4_mb_init_backend(sb);
2524         if (ret != 0)
2525                 goto out_free_locality_groups;
2526
2527         if (sbi->s_proc)
2528                 proc_create_data("mb_groups", S_IRUGO, sbi->s_proc,
2529                                  &ext4_mb_seq_groups_fops, sb);
2530
2531         if (sbi->s_journal)
2532                 sbi->s_journal->j_commit_callback = release_blocks_on_commit;
2533
2534         return 0;
2535
2536 out_free_locality_groups:
2537         free_percpu(sbi->s_locality_groups);
2538         sbi->s_locality_groups = NULL;
2539 out_free_groupinfo_slab:
2540         ext4_groupinfo_destroy_slabs();
2541 out:
2542         kfree(sbi->s_mb_offsets);
2543         sbi->s_mb_offsets = NULL;
2544         kfree(sbi->s_mb_maxs);
2545         sbi->s_mb_maxs = NULL;
2546         return ret;
2547 }
2548
2549 /* need to called with the ext4 group lock held */
2550 static void ext4_mb_cleanup_pa(struct ext4_group_info *grp)
2551 {
2552         struct ext4_prealloc_space *pa;
2553         struct list_head *cur, *tmp;
2554         int count = 0;
2555
2556         list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
2557                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
2558                 list_del(&pa->pa_group_list);
2559                 count++;
2560                 kmem_cache_free(ext4_pspace_cachep, pa);
2561         }
2562         if (count)
2563                 mb_debug(1, "mballoc: %u PAs left\n", count);
2564
2565 }
2566
2567 int ext4_mb_release(struct super_block *sb)
2568 {
2569         ext4_group_t ngroups = ext4_get_groups_count(sb);
2570         ext4_group_t i;
2571         int num_meta_group_infos;
2572         struct ext4_group_info *grinfo;
2573         struct ext4_sb_info *sbi = EXT4_SB(sb);
2574         struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2575
2576         if (sbi->s_proc)
2577                 remove_proc_entry("mb_groups", sbi->s_proc);
2578
2579         if (sbi->s_group_info) {
2580                 for (i = 0; i < ngroups; i++) {
2581                         grinfo = ext4_get_group_info(sb, i);
2582 #ifdef DOUBLE_CHECK
2583                         kfree(grinfo->bb_bitmap);
2584 #endif
2585                         ext4_lock_group(sb, i);
2586                         ext4_mb_cleanup_pa(grinfo);
2587                         ext4_unlock_group(sb, i);
2588                         kmem_cache_free(cachep, grinfo);
2589                 }
2590                 num_meta_group_infos = (ngroups +
2591                                 EXT4_DESC_PER_BLOCK(sb) - 1) >>
2592                         EXT4_DESC_PER_BLOCK_BITS(sb);
2593                 for (i = 0; i < num_meta_group_infos; i++)
2594                         kfree(sbi->s_group_info[i]);
2595                 ext4_kvfree(sbi->s_group_info);
2596         }
2597         kfree(sbi->s_mb_offsets);
2598         kfree(sbi->s_mb_maxs);
2599         if (sbi->s_buddy_cache)
2600                 iput(sbi->s_buddy_cache);
2601         if (sbi->s_mb_stats) {
2602                 ext4_msg(sb, KERN_INFO,
2603                        "mballoc: %u blocks %u reqs (%u success)",
2604                                 atomic_read(&sbi->s_bal_allocated),
2605                                 atomic_read(&sbi->s_bal_reqs),
2606                                 atomic_read(&sbi->s_bal_success));
2607                 ext4_msg(sb, KERN_INFO,
2608                       "mballoc: %u extents scanned, %u goal hits, "
2609                                 "%u 2^N hits, %u breaks, %u lost",
2610                                 atomic_read(&sbi->s_bal_ex_scanned),
2611                                 atomic_read(&sbi->s_bal_goals),
2612                                 atomic_read(&sbi->s_bal_2orders),
2613                                 atomic_read(&sbi->s_bal_breaks),
2614                                 atomic_read(&sbi->s_mb_lost_chunks));
2615                 ext4_msg(sb, KERN_INFO,
2616                        "mballoc: %lu generated and it took %Lu",
2617                                 sbi->s_mb_buddies_generated,
2618                                 sbi->s_mb_generation_time);
2619                 ext4_msg(sb, KERN_INFO,
2620                        "mballoc: %u preallocated, %u discarded",
2621                                 atomic_read(&sbi->s_mb_preallocated),
2622                                 atomic_read(&sbi->s_mb_discarded));
2623         }
2624
2625         free_percpu(sbi->s_locality_groups);
2626
2627         return 0;
2628 }
2629
2630 static inline int ext4_issue_discard(struct super_block *sb,
2631                 ext4_group_t block_group, ext4_grpblk_t cluster, int count)
2632 {
2633         ext4_fsblk_t discard_block;
2634
2635         discard_block = (EXT4_C2B(EXT4_SB(sb), cluster) +
2636                          ext4_group_first_block_no(sb, block_group));
2637         count = EXT4_C2B(EXT4_SB(sb), count);
2638         trace_ext4_discard_blocks(sb,
2639                         (unsigned long long) discard_block, count);
2640         return sb_issue_discard(sb, discard_block, count, GFP_NOFS, 0);
2641 }
2642
2643 /*
2644  * This function is called by the jbd2 layer once the commit has finished,
2645  * so we know we can free the blocks that were released with that commit.
2646  */
2647 static void release_blocks_on_commit(journal_t *journal, transaction_t *txn)
2648 {
2649         struct super_block *sb = journal->j_private;
2650         struct ext4_buddy e4b;
2651         struct ext4_group_info *db;
2652         int err, count = 0, count2 = 0;
2653         struct ext4_free_data *entry;
2654         struct list_head *l, *ltmp;
2655
2656         list_for_each_safe(l, ltmp, &txn->t_private_list) {
2657                 entry = list_entry(l, struct ext4_free_data, list);
2658
2659                 mb_debug(1, "gonna free %u blocks in group %u (0x%p):",
2660                          entry->count, entry->group, entry);
2661
2662                 if (test_opt(sb, DISCARD))
2663                         ext4_issue_discard(sb, entry->group,
2664                                            entry->start_cluster, entry->count);
2665
2666                 err = ext4_mb_load_buddy(sb, entry->group, &e4b);
2667                 /* we expect to find existing buddy because it's pinned */
2668                 BUG_ON(err != 0);
2669
2670                 db = e4b.bd_info;
2671                 /* there are blocks to put in buddy to make them really free */
2672                 count += entry->count;
2673                 count2++;
2674                 ext4_lock_group(sb, entry->group);
2675                 /* Take it out of per group rb tree */
2676                 rb_erase(&entry->node, &(db->bb_free_root));
2677                 mb_free_blocks(NULL, &e4b, entry->start_cluster, entry->count);
2678
2679                 /*
2680                  * Clear the trimmed flag for the group so that the next
2681                  * ext4_trim_fs can trim it.
2682                  * If the volume is mounted with -o discard, online discard
2683                  * is supported and the free blocks will be trimmed online.
2684                  */
2685                 if (!test_opt(sb, DISCARD))
2686                         EXT4_MB_GRP_CLEAR_TRIMMED(db);
2687
2688                 if (!db->bb_free_root.rb_node) {
2689                         /* No more items in the per group rb tree
2690                          * balance refcounts from ext4_mb_free_metadata()
2691                          */
2692                         page_cache_release(e4b.bd_buddy_page);
2693                         page_cache_release(e4b.bd_bitmap_page);
2694                 }
2695                 ext4_unlock_group(sb, entry->group);
2696                 kmem_cache_free(ext4_free_ext_cachep, entry);
2697                 ext4_mb_unload_buddy(&e4b);
2698         }
2699
2700         mb_debug(1, "freed %u blocks in %u structures\n", count, count2);
2701 }
2702
2703 #ifdef CONFIG_EXT4_DEBUG
2704 u8 mb_enable_debug __read_mostly;
2705
2706 static struct dentry *debugfs_dir;
2707 static struct dentry *debugfs_debug;
2708
2709 static void __init ext4_create_debugfs_entry(void)
2710 {
2711         debugfs_dir = debugfs_create_dir("ext4", NULL);
2712         if (debugfs_dir)
2713                 debugfs_debug = debugfs_create_u8("mballoc-debug",
2714                                                   S_IRUGO | S_IWUSR,
2715                                                   debugfs_dir,
2716                                                   &mb_enable_debug);
2717 }
2718
2719 static void ext4_remove_debugfs_entry(void)
2720 {
2721         debugfs_remove(debugfs_debug);
2722         debugfs_remove(debugfs_dir);
2723 }
2724
2725 #else
2726
2727 static void __init ext4_create_debugfs_entry(void)
2728 {
2729 }
2730
2731 static void ext4_remove_debugfs_entry(void)
2732 {
2733 }
2734
2735 #endif
2736
2737 int __init ext4_init_mballoc(void)
2738 {
2739         ext4_pspace_cachep = KMEM_CACHE(ext4_prealloc_space,
2740                                         SLAB_RECLAIM_ACCOUNT);
2741         if (ext4_pspace_cachep == NULL)
2742                 return -ENOMEM;
2743
2744         ext4_ac_cachep = KMEM_CACHE(ext4_allocation_context,
2745                                     SLAB_RECLAIM_ACCOUNT);
2746         if (ext4_ac_cachep == NULL) {
2747                 kmem_cache_destroy(ext4_pspace_cachep);
2748                 return -ENOMEM;
2749         }
2750
2751         ext4_free_ext_cachep = KMEM_CACHE(ext4_free_data,
2752                                           SLAB_RECLAIM_ACCOUNT);
2753         if (ext4_free_ext_cachep == NULL) {
2754                 kmem_cache_destroy(ext4_pspace_cachep);
2755                 kmem_cache_destroy(ext4_ac_cachep);
2756                 return -ENOMEM;
2757         }
2758         ext4_create_debugfs_entry();
2759         return 0;
2760 }
2761
2762 void ext4_exit_mballoc(void)
2763 {
2764         /*
2765          * Wait for completion of call_rcu()'s on ext4_pspace_cachep
2766          * before destroying the slab cache.
2767          */
2768         rcu_barrier();
2769         kmem_cache_destroy(ext4_pspace_cachep);
2770         kmem_cache_destroy(ext4_ac_cachep);
2771         kmem_cache_destroy(ext4_free_ext_cachep);
2772         ext4_groupinfo_destroy_slabs();
2773         ext4_remove_debugfs_entry();
2774 }
2775
2776
2777 /*
2778  * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
2779  * Returns 0 if success or error code
2780  */
2781 static noinline_for_stack int
2782 ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
2783                                 handle_t *handle, unsigned int reserv_clstrs)
2784 {
2785         struct buffer_head *bitmap_bh = NULL;
2786         struct ext4_group_desc *gdp;
2787         struct buffer_head *gdp_bh;
2788         struct ext4_sb_info *sbi;
2789         struct super_block *sb;
2790         ext4_fsblk_t block;
2791         int err, len;
2792
2793         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
2794         BUG_ON(ac->ac_b_ex.fe_len <= 0);
2795
2796         sb = ac->ac_sb;
2797         sbi = EXT4_SB(sb);
2798
2799         err = -EIO;
2800         bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);
2801         if (!bitmap_bh)
2802                 goto out_err;
2803
2804         err = ext4_journal_get_write_access(handle, bitmap_bh);
2805         if (err)
2806                 goto out_err;
2807
2808         err = -EIO;
2809         gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);
2810         if (!gdp)
2811                 goto out_err;
2812
2813         ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,
2814                         ext4_free_group_clusters(sb, gdp));
2815
2816         err = ext4_journal_get_write_access(handle, gdp_bh);
2817         if (err)
2818                 goto out_err;
2819
2820         block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
2821
2822         len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
2823         if (!ext4_data_block_valid(sbi, block, len)) {
2824                 ext4_error(sb, "Allocating blocks %llu-%llu which overlap "
2825                            "fs metadata\n", block, block+len);
2826                 /* File system mounted not to panic on error
2827                  * Fix the bitmap and return EIO
2828                  * We leak some of the blocks here.
2829                  */
2830                 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
2831                 ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
2832                               ac->ac_b_ex.fe_len);
2833                 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
2834                 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
2835                 if (!err)
2836                         err = -EIO;
2837                 goto out_err;
2838         }
2839
2840         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
2841 #ifdef AGGRESSIVE_CHECK
2842         {
2843                 int i;
2844                 for (i = 0; i < ac->ac_b_ex.fe_len; i++) {
2845                         BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,
2846                                                 bitmap_bh->b_data));
2847                 }
2848         }
2849 #endif
2850         ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
2851                       ac->ac_b_ex.fe_len);
2852         if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
2853                 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
2854                 ext4_free_group_clusters_set(sb, gdp,
2855                                              ext4_free_clusters_after_init(sb,
2856                                                 ac->ac_b_ex.fe_group, gdp));
2857         }
2858         len = ext4_free_group_clusters(sb, gdp) - ac->ac_b_ex.fe_len;
2859         ext4_free_group_clusters_set(sb, gdp, len);
2860         gdp->bg_checksum = ext4_group_desc_csum(sbi, ac->ac_b_ex.fe_group, gdp);
2861
2862         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
2863         percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);
2864         /*
2865          * Now reduce the dirty block count also. Should not go negative
2866          */
2867         if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
2868                 /* release all the reserved blocks if non delalloc */
2869                 percpu_counter_sub(&sbi->s_dirtyclusters_counter,
2870                                    reserv_clstrs);
2871
2872         if (sbi->s_log_groups_per_flex) {
2873                 ext4_group_t flex_group = ext4_flex_group(sbi,
2874                                                           ac->ac_b_ex.fe_group);
2875                 atomic64_sub(ac->ac_b_ex.fe_len,
2876                              &sbi->s_flex_groups[flex_group].free_clusters);
2877         }
2878
2879         err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
2880         if (err)
2881                 goto out_err;
2882         err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);
2883
2884 out_err:
2885         ext4_mark_super_dirty(sb);
2886         brelse(bitmap_bh);
2887         return err;
2888 }
2889
2890 /*
2891  * here we normalize request for locality group
2892  * Group request are normalized to s_mb_group_prealloc, which goes to
2893  * s_strip if we set the same via mount option.
2894  * s_mb_group_prealloc can be configured via
2895  * /sys/fs/ext4/<partition>/mb_group_prealloc
2896  *
2897  * XXX: should we try to preallocate more than the group has now?
2898  */
2899 static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
2900 {
2901         struct super_block *sb = ac->ac_sb;
2902         struct ext4_locality_group *lg = ac->ac_lg;
2903
2904         BUG_ON(lg == NULL);
2905         ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
2906         mb_debug(1, "#%u: goal %u blocks for locality group\n",
2907                 current->pid, ac->ac_g_ex.fe_len);
2908 }
2909
2910 /*
2911  * Normalization means making request better in terms of
2912  * size and alignment
2913  */
2914 static noinline_for_stack void
2915 ext4_mb_normalize_request(struct ext4_allocation_context *ac,
2916                                 struct ext4_allocation_request *ar)
2917 {
2918         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2919         int bsbits, max;
2920         ext4_lblk_t end;
2921         loff_t size, orig_size, start_off;
2922         ext4_lblk_t start;
2923         struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
2924         struct ext4_prealloc_space *pa;
2925
2926         /* do normalize only data requests, metadata requests
2927            do not need preallocation */
2928         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
2929                 return;
2930
2931         /* sometime caller may want exact blocks */
2932         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
2933                 return;
2934
2935         /* caller may indicate that preallocation isn't
2936          * required (it's a tail, for example) */
2937         if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
2938                 return;
2939
2940         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
2941                 ext4_mb_normalize_group_request(ac);
2942                 return ;
2943         }
2944
2945         bsbits = ac->ac_sb->s_blocksize_bits;
2946
2947         /* first, let's learn actual file size
2948          * given current request is allocated */
2949         size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
2950         size = size << bsbits;
2951         if (size < i_size_read(ac->ac_inode))
2952                 size = i_size_read(ac->ac_inode);
2953         orig_size = size;
2954
2955         /* max size of free chunks */
2956         max = 2 << bsbits;
2957
2958 #define NRL_CHECK_SIZE(req, size, max, chunk_size)      \
2959                 (req <= (size) || max <= (chunk_size))
2960
2961         /* first, try to predict filesize */
2962         /* XXX: should this table be tunable? */
2963         start_off = 0;
2964         if (size <= 16 * 1024) {
2965                 size = 16 * 1024;
2966         } else if (size <= 32 * 1024) {
2967                 size = 32 * 1024;
2968         } else if (size <= 64 * 1024) {
2969                 size = 64 * 1024;
2970         } else if (size <= 128 * 1024) {
2971                 size = 128 * 1024;
2972         } else if (size <= 256 * 1024) {
2973                 size = 256 * 1024;
2974         } else if (size <= 512 * 1024) {
2975                 size = 512 * 1024;
2976         } else if (size <= 1024 * 1024) {
2977                 size = 1024 * 1024;
2978         } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
2979                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2980                                                 (21 - bsbits)) << 21;
2981                 size = 2 * 1024 * 1024;
2982         } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
2983                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2984                                                         (22 - bsbits)) << 22;
2985                 size = 4 * 1024 * 1024;
2986         } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
2987                                         (8<<20)>>bsbits, max, 8 * 1024)) {
2988                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2989                                                         (23 - bsbits)) << 23;
2990                 size = 8 * 1024 * 1024;
2991         } else {
2992                 start_off = (loff_t)ac->ac_o_ex.fe_logical << bsbits;
2993                 size      = ac->ac_o_ex.fe_len << bsbits;
2994         }
2995         size = size >> bsbits;
2996         start = start_off >> bsbits;
2997
2998         /* don't cover already allocated blocks in selected range */
2999         if (ar->pleft && start <= ar->lleft) {
3000                 size -= ar->lleft + 1 - start;
3001                 start = ar->lleft + 1;
3002         }
3003         if (ar->pright && start + size - 1 >= ar->lright)
3004                 size -= start + size - ar->lright;
3005
3006         end = start + size;
3007
3008         /* check we don't cross already preallocated blocks */
3009         rcu_read_lock();
3010         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3011                 ext4_lblk_t pa_end;
3012
3013                 if (pa->pa_deleted)
3014                         continue;
3015                 spin_lock(&pa->pa_lock);
3016                 if (pa->pa_deleted) {
3017                         spin_unlock(&pa->pa_lock);
3018                         continue;
3019                 }
3020
3021                 pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
3022                                                   pa->pa_len);
3023
3024                 /* PA must not overlap original request */
3025                 BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
3026                         ac->ac_o_ex.fe_logical < pa->pa_lstart));
3027
3028                 /* skip PAs this normalized request doesn't overlap with */
3029                 if (pa->pa_lstart >= end || pa_end <= start) {
3030                         spin_unlock(&pa->pa_lock);
3031                         continue;
3032                 }
3033                 BUG_ON(pa->pa_lstart <= start && pa_end >= end);
3034
3035                 /* adjust start or end to be adjacent to this pa */
3036                 if (pa_end <= ac->ac_o_ex.fe_logical) {
3037                         BUG_ON(pa_end < start);
3038                         start = pa_end;
3039                 } else if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
3040                         BUG_ON(pa->pa_lstart > end);
3041                         end = pa->pa_lstart;
3042                 }
3043                 spin_unlock(&pa->pa_lock);
3044         }
3045         rcu_read_unlock();
3046         size = end - start;
3047
3048         /* XXX: extra loop to check we really don't overlap preallocations */
3049         rcu_read_lock();
3050         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3051                 ext4_lblk_t pa_end;
3052
3053                 spin_lock(&pa->pa_lock);
3054                 if (pa->pa_deleted == 0) {
3055                         pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
3056                                                           pa->pa_len);
3057                         BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
3058                 }
3059                 spin_unlock(&pa->pa_lock);
3060         }
3061         rcu_read_unlock();
3062
3063         if (start + size <= ac->ac_o_ex.fe_logical &&
3064                         start > ac->ac_o_ex.fe_logical) {
3065                 ext4_msg(ac->ac_sb, KERN_ERR,
3066                          "start %lu, size %lu, fe_logical %lu",
3067                          (unsigned long) start, (unsigned long) size,
3068                          (unsigned long) ac->ac_o_ex.fe_logical);
3069         }
3070         BUG_ON(start + size <= ac->ac_o_ex.fe_logical &&
3071                         start > ac->ac_o_ex.fe_logical);
3072         BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
3073
3074         /* now prepare goal request */
3075
3076         /* XXX: is it better to align blocks WRT to logical
3077          * placement or satisfy big request as is */
3078         ac->ac_g_ex.fe_logical = start;
3079         ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);
3080
3081         /* define goal start in order to merge */
3082         if (ar->pright && (ar->lright == (start + size))) {
3083                 /* merge to the right */
3084                 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
3085                                                 &ac->ac_f_ex.fe_group,
3086                                                 &ac->ac_f_ex.fe_start);
3087                 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3088         }
3089         if (ar->pleft && (ar->lleft + 1 == start)) {
3090                 /* merge to the left */
3091                 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
3092                                                 &ac->ac_f_ex.fe_group,
3093                                                 &ac->ac_f_ex.fe_start);
3094                 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3095         }
3096
3097         mb_debug(1, "goal: %u(was %u) blocks at %u\n", (unsigned) size,
3098                 (unsigned) orig_size, (unsigned) start);
3099 }
3100
3101 static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
3102 {
3103         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3104
3105         if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
3106                 atomic_inc(&sbi->s_bal_reqs);
3107                 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
3108                 if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
3109                         atomic_inc(&sbi->s_bal_success);
3110                 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
3111                 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
3112                                 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
3113                         atomic_inc(&sbi->s_bal_goals);
3114                 if (ac->ac_found > sbi->s_mb_max_to_scan)
3115                         atomic_inc(&sbi->s_bal_breaks);
3116         }
3117
3118         if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)
3119                 trace_ext4_mballoc_alloc(ac);
3120         else
3121                 trace_ext4_mballoc_prealloc(ac);
3122 }
3123
3124 /*
3125  * Called on failure; free up any blocks from the inode PA for this
3126  * context.  We don't need this for MB_GROUP_PA because we only change
3127  * pa_free in ext4_mb_release_context(), but on failure, we've already
3128  * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
3129  */
3130 static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac)
3131 {
3132         struct ext4_prealloc_space *pa = ac->ac_pa;
3133         struct ext4_buddy e4b;
3134         int err;
3135
3136         if (pa == NULL) {
3137                 if (ac->ac_f_ex.fe_len == 0)
3138                         return;
3139                 err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);
3140                 if (err) {
3141                         /*
3142                          * This should never happen since we pin the
3143                          * pages in the ext4_allocation_context so
3144                          * ext4_mb_load_buddy() should never fail.
3145                          */
3146                         WARN(1, "mb_load_buddy failed (%d)", err);
3147                         return;
3148                 }
3149                 ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
3150                 mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,
3151                                ac->ac_f_ex.fe_len);
3152                 ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
3153                 ext4_mb_unload_buddy(&e4b);
3154                 return;
3155         }
3156         if (pa->pa_type == MB_INODE_PA)
3157                 pa->pa_free += ac->ac_b_ex.fe_len;
3158 }
3159
3160 /*
3161  * use blocks preallocated to inode
3162  */
3163 static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
3164                                 struct ext4_prealloc_space *pa)
3165 {
3166         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3167         ext4_fsblk_t start;
3168         ext4_fsblk_t end;
3169         int len;
3170
3171         /* found preallocated blocks, use them */
3172         start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
3173         end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),
3174                   start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));
3175         len = EXT4_NUM_B2C(sbi, end - start);
3176         ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
3177                                         &ac->ac_b_ex.fe_start);
3178         ac->ac_b_ex.fe_len = len;
3179         ac->ac_status = AC_STATUS_FOUND;
3180         ac->ac_pa = pa;
3181
3182         BUG_ON(start < pa->pa_pstart);
3183         BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));
3184         BUG_ON(pa->pa_free < len);
3185         pa->pa_free -= len;
3186
3187         mb_debug(1, "use %llu/%u from inode pa %p\n", start, len, pa);
3188 }
3189
3190 /*
3191  * use blocks preallocated to locality group
3192  */
3193 static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
3194                                 struct ext4_prealloc_space *pa)
3195 {
3196         unsigned int len = ac->ac_o_ex.fe_len;
3197
3198         ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
3199                                         &ac->ac_b_ex.fe_group,
3200                                         &ac->ac_b_ex.fe_start);
3201         ac->ac_b_ex.fe_len = len;
3202         ac->ac_status = AC_STATUS_FOUND;
3203         ac->ac_pa = pa;
3204
3205         /* we don't correct pa_pstart or pa_plen here to avoid
3206          * possible race when the group is being loaded concurrently
3207          * instead we correct pa later, after blocks are marked
3208          * in on-disk bitmap -- see ext4_mb_release_context()
3209          * Other CPUs are prevented from allocating from this pa by lg_mutex
3210          */
3211         mb_debug(1, "use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
3212 }
3213
3214 /*
3215  * Return the prealloc space that have minimal distance
3216  * from the goal block. @cpa is the prealloc
3217  * space that is having currently known minimal distance
3218  * from the goal block.
3219  */
3220 static struct ext4_prealloc_space *
3221 ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
3222                         struct ext4_prealloc_space *pa,
3223                         struct ext4_prealloc_space *cpa)
3224 {
3225         ext4_fsblk_t cur_distance, new_distance;
3226
3227         if (cpa == NULL) {
3228                 atomic_inc(&pa->pa_count);
3229                 return pa;
3230         }
3231         cur_distance = abs(goal_block - cpa->pa_pstart);
3232         new_distance = abs(goal_block - pa->pa_pstart);
3233
3234         if (cur_distance <= new_distance)
3235                 return cpa;
3236
3237         /* drop the previous reference */
3238         atomic_dec(&cpa->pa_count);
3239         atomic_inc(&pa->pa_count);
3240         return pa;
3241 }
3242
3243 /*
3244  * search goal blocks in preallocated space
3245  */
3246 static noinline_for_stack int
3247 ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
3248 {
3249         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3250         int order, i;
3251         struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3252         struct ext4_locality_group *lg;
3253         struct ext4_prealloc_space *pa, *cpa = NULL;
3254         ext4_fsblk_t goal_block;
3255
3256         /* only data can be preallocated */
3257         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3258                 return 0;
3259
3260         /* first, try per-file preallocation */
3261         rcu_read_lock();
3262         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3263
3264                 /* all fields in this condition don't change,
3265                  * so we can skip locking for them */
3266                 if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
3267                     ac->ac_o_ex.fe_logical >= (pa->pa_lstart +
3268                                                EXT4_C2B(sbi, pa->pa_len)))
3269                         continue;
3270
3271                 /* non-extent files can't have physical blocks past 2^32 */
3272                 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&
3273                     (pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len) >
3274                      EXT4_MAX_BLOCK_FILE_PHYS))
3275                         continue;
3276
3277                 /* found preallocated blocks, use them */
3278                 spin_lock(&pa->pa_lock);
3279                 if (pa->pa_deleted == 0 && pa->pa_free) {
3280                         atomic_inc(&pa->pa_count);
3281                         ext4_mb_use_inode_pa(ac, pa);
3282                         spin_unlock(&pa->pa_lock);
3283                         ac->ac_criteria = 10;
3284                         rcu_read_unlock();
3285                         return 1;
3286                 }
3287                 spin_unlock(&pa->pa_lock);
3288         }
3289         rcu_read_unlock();
3290
3291         /* can we use group allocation? */
3292         if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
3293                 return 0;
3294
3295         /* inode may have no locality group for some reason */
3296         lg = ac->ac_lg;
3297         if (lg == NULL)
3298                 return 0;
3299         order  = fls(ac->ac_o_ex.fe_len) - 1;
3300         if (order > PREALLOC_TB_SIZE - 1)
3301                 /* The max size of hash table is PREALLOC_TB_SIZE */
3302                 order = PREALLOC_TB_SIZE - 1;
3303
3304         goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);
3305         /*
3306          * search for the prealloc space that is having
3307          * minimal distance from the goal block.
3308          */
3309         for (i = order; i < PREALLOC_TB_SIZE; i++) {
3310                 rcu_read_lock();
3311                 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],
3312                                         pa_inode_list) {
3313                         spin_lock(&pa->pa_lock);
3314                         if (pa->pa_deleted == 0 &&
3315                                         pa->pa_free >= ac->ac_o_ex.fe_len) {
3316
3317                                 cpa = ext4_mb_check_group_pa(goal_block,
3318                                                                 pa, cpa);
3319                         }
3320                         spin_unlock(&pa->pa_lock);
3321                 }
3322                 rcu_read_unlock();
3323         }
3324         if (cpa) {
3325                 ext4_mb_use_group_pa(ac, cpa);
3326                 ac->ac_criteria = 20;
3327                 return 1;
3328         }
3329         return 0;
3330 }
3331
3332 /*
3333  * the function goes through all block freed in the group
3334  * but not yet committed and marks them used in in-core bitmap.
3335  * buddy must be generated from this bitmap
3336  * Need to be called with the ext4 group lock held
3337  */
3338 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
3339                                                 ext4_group_t group)
3340 {
3341         struct rb_node *n;
3342         struct ext4_group_info *grp;
3343         struct ext4_free_data *entry;
3344
3345         grp = ext4_get_group_info(sb, group);
3346         n = rb_first(&(grp->bb_free_root));
3347
3348         while (n) {
3349                 entry = rb_entry(n, struct ext4_free_data, node);
3350                 ext4_set_bits(bitmap, entry->start_cluster, entry->count);
3351                 n = rb_next(n);
3352         }
3353         return;
3354 }
3355
3356 /*
3357  * the function goes through all preallocation in this group and marks them
3358  * used in in-core bitmap. buddy must be generated from this bitmap
3359  * Need to be called with ext4 group lock held
3360  */
3361 static noinline_for_stack
3362 void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
3363                                         ext4_group_t group)
3364 {
3365         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3366         struct ext4_prealloc_space *pa;
3367         struct list_head *cur;
3368         ext4_group_t groupnr;
3369         ext4_grpblk_t start;
3370         int preallocated = 0;
3371         int len;
3372
3373         /* all form of preallocation discards first load group,
3374          * so the only competing code is preallocation use.
3375          * we don't need any locking here
3376          * notice we do NOT ignore preallocations with pa_deleted
3377          * otherwise we could leave used blocks available for
3378          * allocation in buddy when concurrent ext4_mb_put_pa()
3379          * is dropping preallocation
3380          */
3381         list_for_each(cur, &grp->bb_prealloc_list) {
3382                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
3383                 spin_lock(&pa->pa_lock);
3384                 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3385                                              &groupnr, &start);
3386                 len = pa->pa_len;
3387                 spin_unlock(&pa->pa_lock);
3388                 if (unlikely(len == 0))
3389                         continue;
3390                 BUG_ON(groupnr != group);
3391                 ext4_set_bits(bitmap, start, len);
3392                 preallocated += len;
3393         }
3394         mb_debug(1, "prellocated %u for group %u\n", preallocated, group);
3395 }
3396
3397 static void ext4_mb_pa_callback(struct rcu_head *head)
3398 {
3399         struct ext4_prealloc_space *pa;
3400         pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
3401
3402         BUG_ON(atomic_read(&pa->pa_count));
3403         BUG_ON(pa->pa_deleted == 0);
3404         kmem_cache_free(ext4_pspace_cachep, pa);
3405 }
3406
3407 /*
3408  * drops a reference to preallocated space descriptor
3409  * if this was the last reference and the space is consumed
3410  */
3411 static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
3412                         struct super_block *sb, struct ext4_prealloc_space *pa)
3413 {
3414         ext4_group_t grp;
3415         ext4_fsblk_t grp_blk;
3416
3417         /* in this short window concurrent discard can set pa_deleted */
3418         spin_lock(&pa->pa_lock);
3419         if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {
3420                 spin_unlock(&pa->pa_lock);
3421                 return;
3422         }
3423
3424         if (pa->pa_deleted == 1) {
3425                 spin_unlock(&pa->pa_lock);
3426                 return;
3427         }
3428
3429         pa->pa_deleted = 1;
3430         spin_unlock(&pa->pa_lock);
3431
3432         grp_blk = pa->pa_pstart;
3433         /*
3434          * If doing group-based preallocation, pa_pstart may be in the
3435          * next group when pa is used up
3436          */
3437         if (pa->pa_type == MB_GROUP_PA)
3438                 grp_blk--;
3439
3440         ext4_get_group_no_and_offset(sb, grp_blk, &grp, NULL);
3441
3442         /*
3443          * possible race:
3444          *
3445          *  P1 (buddy init)                     P2 (regular allocation)
3446          *                                      find block B in PA
3447          *  copy on-disk bitmap to buddy
3448          *                                      mark B in on-disk bitmap
3449          *                                      drop PA from group
3450          *  mark all PAs in buddy
3451          *
3452          * thus, P1 initializes buddy with B available. to prevent this
3453          * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
3454          * against that pair
3455          */
3456         ext4_lock_group(sb, grp);
3457         list_del(&pa->pa_group_list);
3458         ext4_unlock_group(sb, grp);
3459
3460         spin_lock(pa->pa_obj_lock);
3461         list_del_rcu(&pa->pa_inode_list);
3462         spin_unlock(pa->pa_obj_lock);
3463
3464         call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3465 }
3466
3467 /*
3468  * creates new preallocated space for given inode
3469  */
3470 static noinline_for_stack int
3471 ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
3472 {
3473         struct super_block *sb = ac->ac_sb;
3474         struct ext4_sb_info *sbi = EXT4_SB(sb);
3475         struct ext4_prealloc_space *pa;
3476         struct ext4_group_info *grp;
3477         struct ext4_inode_info *ei;
3478
3479         /* preallocate only when found space is larger then requested */
3480         BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3481         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3482         BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3483
3484         pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3485         if (pa == NULL)
3486                 return -ENOMEM;
3487
3488         if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
3489                 int winl;
3490                 int wins;
3491                 int win;
3492                 int offs;
3493
3494                 /* we can't allocate as much as normalizer wants.
3495                  * so, found space must get proper lstart
3496                  * to cover original request */
3497                 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
3498                 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
3499
3500                 /* we're limited by original request in that
3501                  * logical block must be covered any way
3502                  * winl is window we can move our chunk within */
3503                 winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;
3504
3505                 /* also, we should cover whole original request */
3506                 wins = EXT4_C2B(sbi, ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len);
3507
3508                 /* the smallest one defines real window */
3509                 win = min(winl, wins);
3510
3511                 offs = ac->ac_o_ex.fe_logical %
3512                         EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
3513                 if (offs && offs < win)
3514                         win = offs;
3515
3516                 ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical -
3517                         EXT4_NUM_B2C(sbi, win);
3518                 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
3519                 BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
3520         }
3521
3522         /* preallocation can change ac_b_ex, thus we store actually
3523          * allocated blocks for history */
3524         ac->ac_f_ex = ac->ac_b_ex;
3525
3526         pa->pa_lstart = ac->ac_b_ex.fe_logical;
3527         pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3528         pa->pa_len = ac->ac_b_ex.fe_len;
3529         pa->pa_free = pa->pa_len;
3530         atomic_set(&pa->pa_count, 1);
3531         spin_lock_init(&pa->pa_lock);
3532         INIT_LIST_HEAD(&pa->pa_inode_list);
3533         INIT_LIST_HEAD(&pa->pa_group_list);
3534         pa->pa_deleted = 0;
3535         pa->pa_type = MB_INODE_PA;
3536
3537         mb_debug(1, "new inode pa %p: %llu/%u for %u\n", pa,
3538                         pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3539         trace_ext4_mb_new_inode_pa(ac, pa);
3540
3541         ext4_mb_use_inode_pa(ac, pa);
3542         atomic_add(pa->pa_free, &sbi->s_mb_preallocated);
3543
3544         ei = EXT4_I(ac->ac_inode);
3545         grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3546
3547         pa->pa_obj_lock = &ei->i_prealloc_lock;
3548         pa->pa_inode = ac->ac_inode;
3549
3550         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3551         list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3552         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3553
3554         spin_lock(pa->pa_obj_lock);
3555         list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
3556         spin_unlock(pa->pa_obj_lock);
3557
3558         return 0;
3559 }
3560
3561 /*
3562  * creates new preallocated space for locality group inodes belongs to
3563  */
3564 static noinline_for_stack int
3565 ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
3566 {
3567         struct super_block *sb = ac->ac_sb;
3568         struct ext4_locality_group *lg;
3569         struct ext4_prealloc_space *pa;
3570         struct ext4_group_info *grp;
3571
3572         /* preallocate only when found space is larger then requested */
3573         BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3574         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3575         BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3576
3577         BUG_ON(ext4_pspace_cachep == NULL);
3578         pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3579         if (pa == NULL)
3580                 return -ENOMEM;
3581
3582         /* preallocation can change ac_b_ex, thus we store actually
3583          * allocated blocks for history */
3584         ac->ac_f_ex = ac->ac_b_ex;
3585
3586         pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3587         pa->pa_lstart = pa->pa_pstart;
3588         pa->pa_len = ac->ac_b_ex.fe_len;
3589         pa->pa_free = pa->pa_len;
3590         atomic_set(&pa->pa_count, 1);
3591         spin_lock_init(&pa->pa_lock);
3592         INIT_LIST_HEAD(&pa->pa_inode_list);
3593         INIT_LIST_HEAD(&pa->pa_group_list);
3594         pa->pa_deleted = 0;
3595         pa->pa_type = MB_GROUP_PA;
3596
3597         mb_debug(1, "new group pa %p: %llu/%u for %u\n", pa,
3598                         pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3599         trace_ext4_mb_new_group_pa(ac, pa);
3600
3601         ext4_mb_use_group_pa(ac, pa);
3602         atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3603
3604         grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3605         lg = ac->ac_lg;
3606         BUG_ON(lg == NULL);
3607
3608         pa->pa_obj_lock = &lg->lg_prealloc_lock;
3609         pa->pa_inode = NULL;
3610
3611         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3612         list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3613         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3614
3615         /*
3616          * We will later add the new pa to the right bucket
3617          * after updating the pa_free in ext4_mb_release_context
3618          */
3619         return 0;
3620 }
3621
3622 static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
3623 {
3624         int err;
3625
3626         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
3627                 err = ext4_mb_new_group_pa(ac);
3628         else
3629                 err = ext4_mb_new_inode_pa(ac);
3630         return err;
3631 }
3632
3633 /*
3634  * finds all unused blocks in on-disk bitmap, frees them in
3635  * in-core bitmap and buddy.
3636  * @pa must be unlinked from inode and group lists, so that
3637  * nobody else can find/use it.
3638  * the caller MUST hold group/inode locks.
3639  * TODO: optimize the case when there are no in-core structures yet
3640  */
3641 static noinline_for_stack int
3642 ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
3643                         struct ext4_prealloc_space *pa)
3644 {
3645         struct super_block *sb = e4b->bd_sb;
3646         struct ext4_sb_info *sbi = EXT4_SB(sb);
3647         unsigned int end;