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