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