Merge tag 'v3.5'
[firefly-linux-kernel-4.4.55.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 = NULL;
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)
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         ext4_block_bitmap_csum_set(sb, ac->ac_b_ex.fe_group, gdp, bitmap_bh,
2802                                    EXT4_BLOCKS_PER_GROUP(sb) / 8);
2803         ext4_group_desc_csum_set(sb, ac->ac_b_ex.fe_group, gdp);
2804
2805         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
2806         percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);
2807         /*
2808          * Now reduce the dirty block count also. Should not go negative
2809          */
2810         if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
2811                 /* release all the reserved blocks if non delalloc */
2812                 percpu_counter_sub(&sbi->s_dirtyclusters_counter,
2813                                    reserv_clstrs);
2814
2815         if (sbi->s_log_groups_per_flex) {
2816                 ext4_group_t flex_group = ext4_flex_group(sbi,
2817                                                           ac->ac_b_ex.fe_group);
2818                 atomic_sub(ac->ac_b_ex.fe_len,
2819                            &sbi->s_flex_groups[flex_group].free_clusters);
2820         }
2821
2822         err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
2823         if (err)
2824                 goto out_err;
2825         err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);
2826
2827 out_err:
2828         ext4_mark_super_dirty(sb);
2829         brelse(bitmap_bh);
2830         return err;
2831 }
2832
2833 /*
2834  * here we normalize request for locality group
2835  * Group request are normalized to s_mb_group_prealloc, which goes to
2836  * s_strip if we set the same via mount option.
2837  * s_mb_group_prealloc can be configured via
2838  * /sys/fs/ext4/<partition>/mb_group_prealloc
2839  *
2840  * XXX: should we try to preallocate more than the group has now?
2841  */
2842 static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
2843 {
2844         struct super_block *sb = ac->ac_sb;
2845         struct ext4_locality_group *lg = ac->ac_lg;
2846
2847         BUG_ON(lg == NULL);
2848         ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
2849         mb_debug(1, "#%u: goal %u blocks for locality group\n",
2850                 current->pid, ac->ac_g_ex.fe_len);
2851 }
2852
2853 /*
2854  * Normalization means making request better in terms of
2855  * size and alignment
2856  */
2857 static noinline_for_stack void
2858 ext4_mb_normalize_request(struct ext4_allocation_context *ac,
2859                                 struct ext4_allocation_request *ar)
2860 {
2861         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2862         int bsbits, max;
2863         ext4_lblk_t end;
2864         loff_t size, start_off;
2865         loff_t orig_size __maybe_unused;
2866         ext4_lblk_t start;
2867         struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
2868         struct ext4_prealloc_space *pa;
2869
2870         /* do normalize only data requests, metadata requests
2871            do not need preallocation */
2872         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
2873                 return;
2874
2875         /* sometime caller may want exact blocks */
2876         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
2877                 return;
2878
2879         /* caller may indicate that preallocation isn't
2880          * required (it's a tail, for example) */
2881         if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
2882                 return;
2883
2884         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
2885                 ext4_mb_normalize_group_request(ac);
2886                 return ;
2887         }
2888
2889         bsbits = ac->ac_sb->s_blocksize_bits;
2890
2891         /* first, let's learn actual file size
2892          * given current request is allocated */
2893         size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
2894         size = size << bsbits;
2895         if (size < i_size_read(ac->ac_inode))
2896                 size = i_size_read(ac->ac_inode);
2897         orig_size = size;
2898
2899         /* max size of free chunks */
2900         max = 2 << bsbits;
2901
2902 #define NRL_CHECK_SIZE(req, size, max, chunk_size)      \
2903                 (req <= (size) || max <= (chunk_size))
2904
2905         /* first, try to predict filesize */
2906         /* XXX: should this table be tunable? */
2907         start_off = 0;
2908         if (size <= 16 * 1024) {
2909                 size = 16 * 1024;
2910         } else if (size <= 32 * 1024) {
2911                 size = 32 * 1024;
2912         } else if (size <= 64 * 1024) {
2913                 size = 64 * 1024;
2914         } else if (size <= 128 * 1024) {
2915                 size = 128 * 1024;
2916         } else if (size <= 256 * 1024) {
2917                 size = 256 * 1024;
2918         } else if (size <= 512 * 1024) {
2919                 size = 512 * 1024;
2920         } else if (size <= 1024 * 1024) {
2921                 size = 1024 * 1024;
2922         } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
2923                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2924                                                 (21 - bsbits)) << 21;
2925                 size = 2 * 1024 * 1024;
2926         } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
2927                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2928                                                         (22 - bsbits)) << 22;
2929                 size = 4 * 1024 * 1024;
2930         } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
2931                                         (8<<20)>>bsbits, max, 8 * 1024)) {
2932                 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2933                                                         (23 - bsbits)) << 23;
2934                 size = 8 * 1024 * 1024;
2935         } else {
2936                 start_off = (loff_t)ac->ac_o_ex.fe_logical << bsbits;
2937                 size      = ac->ac_o_ex.fe_len << bsbits;
2938         }
2939         size = size >> bsbits;
2940         start = start_off >> bsbits;
2941
2942         /* don't cover already allocated blocks in selected range */
2943         if (ar->pleft && start <= ar->lleft) {
2944                 size -= ar->lleft + 1 - start;
2945                 start = ar->lleft + 1;
2946         }
2947         if (ar->pright && start + size - 1 >= ar->lright)
2948                 size -= start + size - ar->lright;
2949
2950         end = start + size;
2951
2952         /* check we don't cross already preallocated blocks */
2953         rcu_read_lock();
2954         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
2955                 ext4_lblk_t pa_end;
2956
2957                 if (pa->pa_deleted)
2958                         continue;
2959                 spin_lock(&pa->pa_lock);
2960                 if (pa->pa_deleted) {
2961                         spin_unlock(&pa->pa_lock);
2962                         continue;
2963                 }
2964
2965                 pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
2966                                                   pa->pa_len);
2967
2968                 /* PA must not overlap original request */
2969                 BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
2970                         ac->ac_o_ex.fe_logical < pa->pa_lstart));
2971
2972                 /* skip PAs this normalized request doesn't overlap with */
2973                 if (pa->pa_lstart >= end || pa_end <= start) {
2974                         spin_unlock(&pa->pa_lock);
2975                         continue;
2976                 }
2977                 BUG_ON(pa->pa_lstart <= start && pa_end >= end);
2978
2979                 /* adjust start or end to be adjacent to this pa */
2980                 if (pa_end <= ac->ac_o_ex.fe_logical) {
2981                         BUG_ON(pa_end < start);
2982                         start = pa_end;
2983                 } else if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
2984                         BUG_ON(pa->pa_lstart > end);
2985                         end = pa->pa_lstart;
2986                 }
2987                 spin_unlock(&pa->pa_lock);
2988         }
2989         rcu_read_unlock();
2990         size = end - start;
2991
2992         /* XXX: extra loop to check we really don't overlap preallocations */
2993         rcu_read_lock();
2994         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
2995                 ext4_lblk_t pa_end;
2996
2997                 spin_lock(&pa->pa_lock);
2998                 if (pa->pa_deleted == 0) {
2999                         pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
3000                                                           pa->pa_len);
3001                         BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
3002                 }
3003                 spin_unlock(&pa->pa_lock);
3004         }
3005         rcu_read_unlock();
3006
3007         if (start + size <= ac->ac_o_ex.fe_logical &&
3008                         start > ac->ac_o_ex.fe_logical) {
3009                 ext4_msg(ac->ac_sb, KERN_ERR,
3010                          "start %lu, size %lu, fe_logical %lu",
3011                          (unsigned long) start, (unsigned long) size,
3012                          (unsigned long) ac->ac_o_ex.fe_logical);
3013         }
3014         BUG_ON(start + size <= ac->ac_o_ex.fe_logical &&
3015                         start > ac->ac_o_ex.fe_logical);
3016         BUG_ON(size <= 0 || size > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
3017
3018         /* now prepare goal request */
3019
3020         /* XXX: is it better to align blocks WRT to logical
3021          * placement or satisfy big request as is */
3022         ac->ac_g_ex.fe_logical = start;
3023         ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);
3024
3025         /* define goal start in order to merge */
3026         if (ar->pright && (ar->lright == (start + size))) {
3027                 /* merge to the right */
3028                 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
3029                                                 &ac->ac_f_ex.fe_group,
3030                                                 &ac->ac_f_ex.fe_start);
3031                 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3032         }
3033         if (ar->pleft && (ar->lleft + 1 == start)) {
3034                 /* merge to the left */
3035                 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
3036                                                 &ac->ac_f_ex.fe_group,
3037                                                 &ac->ac_f_ex.fe_start);
3038                 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3039         }
3040
3041         mb_debug(1, "goal: %u(was %u) blocks at %u\n", (unsigned) size,
3042                 (unsigned) orig_size, (unsigned) start);
3043 }
3044
3045 static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
3046 {
3047         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3048
3049         if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
3050                 atomic_inc(&sbi->s_bal_reqs);
3051                 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
3052                 if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
3053                         atomic_inc(&sbi->s_bal_success);
3054                 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
3055                 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
3056                                 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
3057                         atomic_inc(&sbi->s_bal_goals);
3058                 if (ac->ac_found > sbi->s_mb_max_to_scan)
3059                         atomic_inc(&sbi->s_bal_breaks);
3060         }
3061
3062         if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)
3063                 trace_ext4_mballoc_alloc(ac);
3064         else
3065                 trace_ext4_mballoc_prealloc(ac);
3066 }
3067
3068 /*
3069  * Called on failure; free up any blocks from the inode PA for this
3070  * context.  We don't need this for MB_GROUP_PA because we only change
3071  * pa_free in ext4_mb_release_context(), but on failure, we've already
3072  * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
3073  */
3074 static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac)
3075 {
3076         struct ext4_prealloc_space *pa = ac->ac_pa;
3077
3078         if (pa && pa->pa_type == MB_INODE_PA)
3079                 pa->pa_free += ac->ac_b_ex.fe_len;
3080 }
3081
3082 /*
3083  * use blocks preallocated to inode
3084  */
3085 static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
3086                                 struct ext4_prealloc_space *pa)
3087 {
3088         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3089         ext4_fsblk_t start;
3090         ext4_fsblk_t end;
3091         int len;
3092
3093         /* found preallocated blocks, use them */
3094         start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
3095         end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),
3096                   start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));
3097         len = EXT4_NUM_B2C(sbi, end - start);
3098         ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
3099                                         &ac->ac_b_ex.fe_start);
3100         ac->ac_b_ex.fe_len = len;
3101         ac->ac_status = AC_STATUS_FOUND;
3102         ac->ac_pa = pa;
3103
3104         BUG_ON(start < pa->pa_pstart);
3105         BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));
3106         BUG_ON(pa->pa_free < len);
3107         pa->pa_free -= len;
3108
3109         mb_debug(1, "use %llu/%u from inode pa %p\n", start, len, pa);
3110 }
3111
3112 /*
3113  * use blocks preallocated to locality group
3114  */
3115 static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
3116                                 struct ext4_prealloc_space *pa)
3117 {
3118         unsigned int len = ac->ac_o_ex.fe_len;
3119
3120         ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
3121                                         &ac->ac_b_ex.fe_group,
3122                                         &ac->ac_b_ex.fe_start);
3123         ac->ac_b_ex.fe_len = len;
3124         ac->ac_status = AC_STATUS_FOUND;
3125         ac->ac_pa = pa;
3126
3127         /* we don't correct pa_pstart or pa_plen here to avoid
3128          * possible race when the group is being loaded concurrently
3129          * instead we correct pa later, after blocks are marked
3130          * in on-disk bitmap -- see ext4_mb_release_context()
3131          * Other CPUs are prevented from allocating from this pa by lg_mutex
3132          */
3133         mb_debug(1, "use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
3134 }
3135
3136 /*
3137  * Return the prealloc space that have minimal distance
3138  * from the goal block. @cpa is the prealloc
3139  * space that is having currently known minimal distance
3140  * from the goal block.
3141  */
3142 static struct ext4_prealloc_space *
3143 ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
3144                         struct ext4_prealloc_space *pa,
3145                         struct ext4_prealloc_space *cpa)
3146 {
3147         ext4_fsblk_t cur_distance, new_distance;
3148
3149         if (cpa == NULL) {
3150                 atomic_inc(&pa->pa_count);
3151                 return pa;
3152         }
3153         cur_distance = abs(goal_block - cpa->pa_pstart);
3154         new_distance = abs(goal_block - pa->pa_pstart);
3155
3156         if (cur_distance <= new_distance)
3157                 return cpa;
3158
3159         /* drop the previous reference */
3160         atomic_dec(&cpa->pa_count);
3161         atomic_inc(&pa->pa_count);
3162         return pa;
3163 }
3164
3165 /*
3166  * search goal blocks in preallocated space
3167  */
3168 static noinline_for_stack int
3169 ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
3170 {
3171         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3172         int order, i;
3173         struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3174         struct ext4_locality_group *lg;
3175         struct ext4_prealloc_space *pa, *cpa = NULL;
3176         ext4_fsblk_t goal_block;
3177
3178         /* only data can be preallocated */
3179         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3180                 return 0;
3181
3182         /* first, try per-file preallocation */
3183         rcu_read_lock();
3184         list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3185
3186                 /* all fields in this condition don't change,
3187                  * so we can skip locking for them */
3188                 if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
3189                     ac->ac_o_ex.fe_logical >= (pa->pa_lstart +
3190                                                EXT4_C2B(sbi, pa->pa_len)))
3191                         continue;
3192
3193                 /* non-extent files can't have physical blocks past 2^32 */
3194                 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&
3195                     (pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len) >
3196                      EXT4_MAX_BLOCK_FILE_PHYS))
3197                         continue;
3198
3199                 /* found preallocated blocks, use them */
3200                 spin_lock(&pa->pa_lock);
3201                 if (pa->pa_deleted == 0 && pa->pa_free) {
3202                         atomic_inc(&pa->pa_count);
3203                         ext4_mb_use_inode_pa(ac, pa);
3204                         spin_unlock(&pa->pa_lock);
3205                         ac->ac_criteria = 10;
3206                         rcu_read_unlock();
3207                         return 1;
3208                 }
3209                 spin_unlock(&pa->pa_lock);
3210         }
3211         rcu_read_unlock();
3212
3213         /* can we use group allocation? */
3214         if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
3215                 return 0;
3216
3217         /* inode may have no locality group for some reason */
3218         lg = ac->ac_lg;
3219         if (lg == NULL)
3220                 return 0;
3221         order  = fls(ac->ac_o_ex.fe_len) - 1;
3222         if (order > PREALLOC_TB_SIZE - 1)
3223                 /* The max size of hash table is PREALLOC_TB_SIZE */
3224                 order = PREALLOC_TB_SIZE - 1;
3225
3226         goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);
3227         /*
3228          * search for the prealloc space that is having
3229          * minimal distance from the goal block.
3230          */
3231         for (i = order; i < PREALLOC_TB_SIZE; i++) {
3232                 rcu_read_lock();
3233                 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],
3234                                         pa_inode_list) {
3235                         spin_lock(&pa->pa_lock);
3236                         if (pa->pa_deleted == 0 &&
3237                                         pa->pa_free >= ac->ac_o_ex.fe_len) {
3238
3239                                 cpa = ext4_mb_check_group_pa(goal_block,
3240                                                                 pa, cpa);
3241                         }
3242                         spin_unlock(&pa->pa_lock);
3243                 }
3244                 rcu_read_unlock();
3245         }
3246         if (cpa) {
3247                 ext4_mb_use_group_pa(ac, cpa);
3248                 ac->ac_criteria = 20;
3249                 return 1;
3250         }
3251         return 0;
3252 }
3253
3254 /*
3255  * the function goes through all block freed in the group
3256  * but not yet committed and marks them used in in-core bitmap.
3257  * buddy must be generated from this bitmap
3258  * Need to be called with the ext4 group lock held
3259  */
3260 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
3261                                                 ext4_group_t group)
3262 {
3263         struct rb_node *n;
3264         struct ext4_group_info *grp;
3265         struct ext4_free_data *entry;
3266
3267         grp = ext4_get_group_info(sb, group);
3268         n = rb_first(&(grp->bb_free_root));
3269
3270         while (n) {
3271                 entry = rb_entry(n, struct ext4_free_data, efd_node);
3272                 ext4_set_bits(bitmap, entry->efd_start_cluster, entry->efd_count);
3273                 n = rb_next(n);
3274         }
3275         return;
3276 }
3277
3278 /*
3279  * the function goes through all preallocation in this group and marks them
3280  * used in in-core bitmap. buddy must be generated from this bitmap
3281  * Need to be called with ext4 group lock held
3282  */
3283 static noinline_for_stack
3284 void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
3285                                         ext4_group_t group)
3286 {
3287         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3288         struct ext4_prealloc_space *pa;
3289         struct list_head *cur;
3290         ext4_group_t groupnr;
3291         ext4_grpblk_t start;
3292         int preallocated = 0;
3293         int len;
3294
3295         /* all form of preallocation discards first load group,
3296          * so the only competing code is preallocation use.
3297          * we don't need any locking here
3298          * notice we do NOT ignore preallocations with pa_deleted
3299          * otherwise we could leave used blocks available for
3300          * allocation in buddy when concurrent ext4_mb_put_pa()
3301          * is dropping preallocation
3302          */
3303         list_for_each(cur, &grp->bb_prealloc_list) {
3304                 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
3305                 spin_lock(&pa->pa_lock);
3306                 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3307                                              &groupnr, &start);
3308                 len = pa->pa_len;
3309                 spin_unlock(&pa->pa_lock);
3310                 if (unlikely(len == 0))
3311                         continue;
3312                 BUG_ON(groupnr != group);
3313                 ext4_set_bits(bitmap, start, len);
3314                 preallocated += len;
3315         }
3316         mb_debug(1, "prellocated %u for group %u\n", preallocated, group);
3317 }
3318
3319 static void ext4_mb_pa_callback(struct rcu_head *head)
3320 {
3321         struct ext4_prealloc_space *pa;
3322         pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
3323         kmem_cache_free(ext4_pspace_cachep, pa);
3324 }
3325
3326 /*
3327  * drops a reference to preallocated space descriptor
3328  * if this was the last reference and the space is consumed
3329  */
3330 static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
3331                         struct super_block *sb, struct ext4_prealloc_space *pa)
3332 {
3333         ext4_group_t grp;
3334         ext4_fsblk_t grp_blk;
3335
3336         if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0)
3337                 return;
3338
3339         /* in this short window concurrent discard can set pa_deleted */
3340         spin_lock(&pa->pa_lock);
3341         if (pa->pa_deleted == 1) {
3342                 spin_unlock(&pa->pa_lock);
3343                 return;
3344         }
3345
3346         pa->pa_deleted = 1;
3347         spin_unlock(&pa->pa_lock);
3348
3349         grp_blk = pa->pa_pstart;
3350         /*
3351          * If doing group-based preallocation, pa_pstart may be in the
3352          * next group when pa is used up
3353          */
3354         if (pa->pa_type == MB_GROUP_PA)
3355                 grp_blk--;
3356
3357         ext4_get_group_no_and_offset(sb, grp_blk, &grp, NULL);
3358
3359         /*
3360          * possible race:
3361          *
3362          *  P1 (buddy init)                     P2 (regular allocation)
3363          *                                      find block B in PA
3364          *  copy on-disk bitmap to buddy
3365          *                                      mark B in on-disk bitmap
3366          *                                      drop PA from group
3367          *  mark all PAs in buddy
3368          *
3369          * thus, P1 initializes buddy with B available. to prevent this
3370          * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
3371          * against that pair
3372          */
3373         ext4_lock_group(sb, grp);
3374         list_del(&pa->pa_group_list);
3375         ext4_unlock_group(sb, grp);
3376
3377         spin_lock(pa->pa_obj_lock);
3378         list_del_rcu(&pa->pa_inode_list);
3379         spin_unlock(pa->pa_obj_lock);
3380
3381         call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3382 }
3383
3384 /*
3385  * creates new preallocated space for given inode
3386  */
3387 static noinline_for_stack int
3388 ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
3389 {
3390         struct super_block *sb = ac->ac_sb;
3391         struct ext4_sb_info *sbi = EXT4_SB(sb);
3392         struct ext4_prealloc_space *pa;
3393         struct ext4_group_info *grp;
3394         struct ext4_inode_info *ei;
3395
3396         /* preallocate only when found space is larger then requested */
3397         BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3398         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3399         BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3400
3401         pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3402         if (pa == NULL)
3403                 return -ENOMEM;
3404
3405         if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
3406                 int winl;
3407                 int wins;
3408                 int win;
3409                 int offs;
3410
3411                 /* we can't allocate as much as normalizer wants.
3412                  * so, found space must get proper lstart
3413                  * to cover original request */
3414                 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
3415                 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
3416
3417                 /* we're limited by original request in that
3418                  * logical block must be covered any way
3419                  * winl is window we can move our chunk within */
3420                 winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;
3421
3422                 /* also, we should cover whole original request */
3423                 wins = EXT4_C2B(sbi, ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len);
3424
3425                 /* the smallest one defines real window */
3426                 win = min(winl, wins);
3427
3428                 offs = ac->ac_o_ex.fe_logical %
3429                         EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
3430                 if (offs && offs < win)
3431                         win = offs;
3432
3433                 ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical -
3434                         EXT4_B2C(sbi, win);
3435                 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
3436                 BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
3437         }
3438
3439         /* preallocation can change ac_b_ex, thus we store actually
3440          * allocated blocks for history */
3441         ac->ac_f_ex = ac->ac_b_ex;
3442
3443         pa->pa_lstart = ac->ac_b_ex.fe_logical;
3444         pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3445         pa->pa_len = ac->ac_b_ex.fe_len;
3446         pa->pa_free = pa->pa_len;
3447         atomic_set(&pa->pa_count, 1);
3448         spin_lock_init(&pa->pa_lock);
3449         INIT_LIST_HEAD(&pa->pa_inode_list);
3450         INIT_LIST_HEAD(&pa->pa_group_list);
3451         pa->pa_deleted = 0;
3452         pa->pa_type = MB_INODE_PA;
3453
3454         mb_debug(1, "new inode pa %p: %llu/%u for %u\n", pa,
3455                         pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3456         trace_ext4_mb_new_inode_pa(ac, pa);
3457
3458         ext4_mb_use_inode_pa(ac, pa);
3459         atomic_add(pa->pa_free, &sbi->s_mb_preallocated);
3460
3461         ei = EXT4_I(ac->ac_inode);
3462         grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3463
3464         pa->pa_obj_lock = &ei->i_prealloc_lock;
3465         pa->pa_inode = ac->ac_inode;
3466
3467         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3468         list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3469         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3470
3471         spin_lock(pa->pa_obj_lock);
3472         list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
3473         spin_unlock(pa->pa_obj_lock);
3474
3475         return 0;
3476 }
3477
3478 /*
3479  * creates new preallocated space for locality group inodes belongs to
3480  */
3481 static noinline_for_stack int
3482 ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
3483 {
3484         struct super_block *sb = ac->ac_sb;
3485         struct ext4_locality_group *lg;
3486         struct ext4_prealloc_space *pa;
3487         struct ext4_group_info *grp;
3488
3489         /* preallocate only when found space is larger then requested */
3490         BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3491         BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3492         BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3493
3494         BUG_ON(ext4_pspace_cachep == NULL);
3495         pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3496         if (pa == NULL)
3497                 return -ENOMEM;
3498
3499         /* preallocation can change ac_b_ex, thus we store actually
3500          * allocated blocks for history */
3501         ac->ac_f_ex = ac->ac_b_ex;
3502
3503         pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3504         pa->pa_lstart = pa->pa_pstart;
3505         pa->pa_len = ac->ac_b_ex.fe_len;
3506         pa->pa_free = pa->pa_len;
3507         atomic_set(&pa->pa_count, 1);
3508         spin_lock_init(&pa->pa_lock);
3509         INIT_LIST_HEAD(&pa->pa_inode_list);
3510         INIT_LIST_HEAD(&pa->pa_group_list);
3511         pa->pa_deleted = 0;
3512         pa->pa_type = MB_GROUP_PA;
3513
3514         mb_debug(1, "new group pa %p: %llu/%u for %u\n", pa,
3515                         pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3516         trace_ext4_mb_new_group_pa(ac, pa);
3517
3518         ext4_mb_use_group_pa(ac, pa);
3519         atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3520
3521         grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3522         lg = ac->ac_lg;
3523         BUG_ON(lg == NULL);
3524
3525         pa->pa_obj_lock = &lg->lg_prealloc_lock;
3526         pa->pa_inode = NULL;
3527
3528         ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3529         list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3530         ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3531
3532         /*
3533          * We will later add the new pa to the right bucket
3534          * after updating the pa_free in ext4_mb_release_context
3535          */
3536         return 0;
3537 }
3538
3539 static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
3540 {
3541         int err;
3542
3543         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
3544                 err = ext4_mb_new_group_pa(ac);
3545         else
3546                 err = ext4_mb_new_inode_pa(ac);
3547         return err;
3548 }
3549
3550 /*
3551  * finds all unused blocks in on-disk bitmap, frees them in
3552  * in-core bitmap and buddy.
3553  * @pa must be unlinked from inode and group lists, so that
3554  * nobody else can find/use it.
3555  * the caller MUST hold group/inode locks.
3556  * TODO: optimize the case when there are no in-core structures yet
3557  */
3558 static noinline_for_stack int
3559 ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
3560                         struct ext4_prealloc_space *pa)
3561 {
3562         struct super_block *sb = e4b->bd_sb;
3563         struct ext4_sb_info *sbi = EXT4_SB(sb);
3564         unsigned int end;
3565         unsigned int next;
3566         ext4_group_t group;
3567         ext4_grpblk_t bit;
3568         unsigned long long grp_blk_start;
3569         int err = 0;
3570         int free = 0;
3571
3572         BUG_ON(pa->pa_deleted == 0);
3573         ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3574         grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);
3575         BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3576         end = bit + pa->pa_len;
3577
3578         while (bit < end) {
3579                 bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
3580                 if (bit >= end)
3581                         break;
3582                 next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
3583                 mb_debug(1, "    free preallocated %u/%u in group %u\n",
3584                          (unsigned) ext4_group_first_block_no(sb, group) + bit,
3585                          (unsigned) next - bit, (unsigned) group);
3586                 free += next - bit;
3587
3588                 trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);
3589                 trace_ext4_mb_release_inode_pa(pa, (grp_blk_start +
3590                                                     EXT4_C2B(sbi, bit)),
3591                                                next - bit);
3592                 mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
3593                 bit = next + 1;
3594         }
3595         if (free != pa->pa_free) {
3596                 ext4_msg(e4b->bd_sb, KERN_CRIT,
3597                          "pa %p: logic %lu, phys. %lu, len %lu",
3598                          pa, (unsigned long) pa->pa_lstart,
3599                          (unsigned long) pa->pa_pstart,
3600                          (unsigned long) pa->pa_len);
3601                 ext4_grp_locked_error(sb, group, 0, 0, "free %u, pa_free %u",
3602                                         free, pa->pa_free);
3603                 /*
3604                  * pa is already deleted so we use the value obtained
3605                  * from the bitmap and continue.
3606                  */
3607         }
3608         atomic_add(free, &sbi->s_mb_discarded);
3609
3610         return err;
3611 }
3612
3613 static noinline_for_stack int
3614 ext4_mb_release_group_pa(struct ext4_buddy *e4b,
3615                                 struct ext4_prealloc_space *pa)
3616 {
3617         struct super_block *sb = e4b->bd_sb;
3618         ext4_group_t group;
3619         ext4_grpblk_t bit;
3620
3621         trace_ext4_mb_release_group_pa(sb, pa);
3622         BUG_ON(pa->pa_deleted == 0);
3623         ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3624         BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3625         mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
3626         atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
3627         trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);
3628
3629         return 0;
3630 }
3631
3632 /*
3633  * releases all preallocations in given group
3634  *
3635  * first, we need to decide discard policy:
3636  * - when do we discard
3637  *   1) ENOSPC
3638  * - how many do we discard
3639  *   1) how many requested
3640  */
3641 static noinline_for_stack int
3642 ext4_mb_discard_group_preallocations(struct super_block *sb,
3643                                         ext4_group_t group, int needed)
3644 {
3645         struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3646         struct buffer_head *bitmap_bh = NULL;
3647         struct ext4_prealloc_space *pa, *tmp;
3648         struct list_head list;
3649         struct ext4_buddy e4b;
3650         int err;
3651         int busy = 0;
3652         int free = 0;
3653
3654         mb_debug(1, "discard preallocation for group %u\n", group);
3655
3656         if (list_empty(&grp->bb_prealloc_list))
3657                 return 0;
3658
3659         bitmap_bh = ext4_read_block_bitmap(sb, group);
3660         if (bitmap_bh == NULL) {
3661                 ext4_error(sb, "Error reading block bitmap for %u", group);
3662                 return 0;
3663         }
3664
3665         err = ext4_mb_load_buddy(sb, group, &e4b);
3666         if (err) {
3667                 ext4_error(sb, "Error loading buddy information for %u", group);
3668                 put_bh(bitmap_bh);
3669                 return 0;
3670         }
3671
3672         if (needed == 0)
3673                 needed = EXT4_CLUSTERS_PER_GROUP(sb) + 1;
3674
3675         INIT_LIST_HEAD(&list);
3676 repeat:
3677         ext4_lock_group(sb, group);
3678         list_for_each_entry_safe(pa, tmp,
3679                                 &grp->bb_prealloc_list, pa_group_list) {
3680                 spin_lock(&pa->pa_lock);
3681                 if (atomic_read(&pa->pa_count)) {
3682                         spin_unlock(&pa->pa_lock);
3683                         busy = 1;
3684                         continue;
3685                 }
3686                 if (pa->pa_deleted) {
3687                         spin_unlock(&pa->pa_lock);
3688                         continue;
3689                 }
3690
3691                 /* seems this one can be freed ... */
3692                 pa->pa_deleted = 1;
3693
3694                 /* we can trust pa_free ... */
3695                 free += pa->pa_free;
3696
3697                 spin_unlock(&pa->pa_lock);
3698
3699                 list_del(&pa->pa_group_list);
3700                 list_add(&pa->u.pa_tmp_list, &list);
3701         }
3702
3703         /* if we still need more blocks and some PAs were used, try again */
3704         if (free < needed && busy) {
3705                 busy = 0;
3706                 ext4_unlock_group(sb, group);
3707                 /*
3708                  * Yield the CPU here so that we don't get soft lockup
3709                  * in non preempt case.
3710                  */
3711                 yield();
3712                 goto repeat;
3713         }
3714
3715         /* found anything to free? */
3716         if (list_empty(&list)) {
3717                 BUG_ON(free != 0);
3718                 goto out;
3719         }
3720
3721         /* now free all selected PAs */
3722         list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
3723
3724                 /* remove from object (inode or locality group) */
3725                 spin_lock(pa->pa_obj_lock);
3726                 list_del_rcu(&pa->pa_inode_list);
3727                 spin_unlock(pa->pa_obj_lock);
3728
3729                 if (pa->pa_type == MB_GROUP_PA)
3730                         ext4_mb_release_group_pa(&e4b, pa);
3731                 else
3732                         ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);
3733
3734                 list_del(&pa->u.pa_tmp_list);
3735                 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3736         }
3737
3738 out:
3739         ext4_unlock_group(sb, group);
3740         ext4_mb_unload_buddy(&e4b);
3741         put_bh(bitmap_bh);
3742         return free;
3743 }
3744
3745 /*
3746  * releases all non-used preallocated blocks for given inode
3747  *
3748  * It's important to discard preallocations under i_data_sem
3749  * We don't want another block to be served from the prealloc
3750  * space when we are discarding the inode prealloc space.
3751  *
3752  * FIXME!! Make sure it is valid at all the call sites
3753  */
3754 void ext4_discard_preallocations(struct inode *inode)
3755 {
3756         struct ext4_inode_info *ei = EXT4_I(inode);
3757         struct super_block *sb = inode->i_sb;
3758         struct buffer_head *bitmap_bh = NULL;
3759         struct ext4_prealloc_space *pa, *tmp;
3760         ext4_group_t group = 0;
3761         struct list_head list;
3762         struct ext4_buddy e4b;
3763         int err;
3764
3765         if (!S_ISREG(inode->i_mode)) {
3766                 /*BUG_ON(!list_empty(&ei->i_prealloc_list));*/
3767                 return;
3768         }
3769
3770         mb_debug(1, "discard preallocation for inode %lu\n", inode->i_ino);
3771         trace_ext4_discard_preallocations(inode);
3772
3773         INIT_LIST_HEAD(&list);
3774
3775 repeat:
3776         /* first, collect all pa's in the inode */
3777         spin_lock(&ei->i_prealloc_lock);
3778         while (!list_empty(&ei->i_prealloc_list)) {
3779                 pa = list_entry(ei->i_prealloc_list.next,
3780                                 struct ext4_prealloc_space, pa_inode_list);
3781                 BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);
3782                 spin_lock(&pa->pa_lock);
3783                 if (atomic_read(&pa->pa_count)) {
3784                         /* this shouldn't happen often - nobody should
3785                          * use preallocation while we're discarding it */
3786                         spin_unlock(&pa->pa_lock);
3787                         spin_unlock(&ei->i_prealloc_lock);
3788                         ext4_msg(sb, KERN_ERR,
3789                                  "uh-oh! used pa while discarding");
3790                         WARN_ON(1);
3791                         schedule_timeout_uninterruptible(HZ);
3792                         goto repeat;
3793
3794                 }
3795                 if (pa->pa_deleted == 0) {
3796                         pa->pa_deleted = 1;
3797                         spin_unlock(&pa->pa_lock);
3798                         list_del_rcu(&pa->pa_inode_list);
3799                         list_add(&pa->u.pa_tmp_list, &list);
3800                         continue;
3801                 }
3802
3803                 /* someone is deleting pa right now */
3804                 spin_unlock(&pa->pa_lock);
3805                 spin_unlock(&ei->i_prealloc_lock);
3806
3807                 /* we have to wait here because pa_deleted
3808                  * doesn't mean pa is already unlinked from
3809                  * the list. as we might be called from
3810                  * ->clear_inode() the inode will get freed
3811                  * and concurrent thread which is unlinking
3812                  * pa from inode's list may access already
3813                  * freed memory, bad-bad-bad */
3814
3815                 /* XXX: if this happens too often, we can
3816                  * add a flag to force wait only in case
3817                  * of ->clear_inode(), but not in case of
3818                  * regular truncate */
3819                 schedule_timeout_uninterruptible(HZ);
3820                 goto repeat;
3821         }
3822         spin_unlock(&ei->i_prealloc_lock);
3823
3824         list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
3825                 BUG_ON(pa->pa_type != MB_INODE_PA);
3826                 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
3827
3828                 err = ext4_mb_load_buddy(sb, group, &e4b);
3829                 if (err) {
3830                         ext4_error(sb, "Error loading buddy information for %u",
3831                                         group);
3832                         continue;
3833                 }
3834
3835                 bitmap_bh = ext4_read_block_bitmap(sb, group);
3836                 if (bitmap_bh == NULL) {
3837                         ext4_error(sb, "Error reading block bitmap for %u",
3838                                         group);
3839                         ext4_mb_unload_buddy(&e4b);
3840                         continue;
3841                 }
3842
3843                 ext4_lock_group(sb, group);
3844                 list_del(&pa->pa_group_list);
3845                 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);
3846                 ext4_unlock_group(sb, group);
3847
3848                 ext4_mb_unload_buddy(&e4b);
3849                 put_bh(bitmap_bh);
3850
3851                 list_del(&pa->u.pa_tmp_list);
3852                 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3853         }
3854 }
3855
3856 #ifdef CONFIG_EXT4_DEBUG
3857 static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
3858 {
3859         struct super_block *sb = ac->ac_sb;
3860         ext4_group_t ngroups, i;
3861
3862         if (!mb_enable_debug ||
3863             (EXT4_SB(sb)->s_mount_flags & EXT4_MF_FS_ABORTED))
3864                 return;
3865
3866         ext4_msg(ac->ac_sb, KERN_ERR, "Can't allocate:"
3867                         " Allocation context details:");
3868         ext4_msg(ac->ac_sb, KERN_ERR, "status %d flags %d",
3869                         ac->ac_status, ac->ac_flags);
3870         ext4_msg(ac->ac_sb, KERN_ERR, "orig %lu/%lu/%lu@%lu, "
3871                         "goal %lu/%lu/%lu@%lu, "
3872                         "best %lu/%lu/%lu@%lu cr %d",
3873                         (unsigned long)ac->ac_o_ex.fe_group,
3874                         (unsigned long)ac->ac_o_ex.fe_start,
3875                         (unsigned long)ac->ac_o_ex.fe_len,
3876                         (unsigned long)ac->ac_o_ex.fe_logical,
3877                         (unsigned long)ac->ac_g_ex.fe_group,
3878                         (unsigned long)ac->ac_g_ex.fe_start,
3879                         (unsigned long)ac->ac_g_ex.fe_len,
3880                         (unsigned long)ac->ac_g_ex.fe_logical,
3881                         (unsigned long)ac->ac_b_ex.fe_group,
3882                         (unsigned long)ac->ac_b_ex.fe_start,
3883                         (unsigned long)ac->ac_b_ex.fe_len,
3884                         (unsigned long)ac->ac_b_ex.fe_logical,
3885                         (int)ac->ac_criteria);
3886         ext4_msg(ac->ac_sb, KERN_ERR, "%lu scanned, %d found",
3887                  ac->ac_ex_scanned, ac->ac_found);
3888         ext4_msg(ac->ac_sb, KERN_ERR, "groups: ");
3889         ngroups = ext4_get_groups_count(sb);
3890         for (i = 0; i < ngroups; i++) {
3891                 struct ext4_group_info *grp = ext4_get_group_info(sb, i);
3892                 struct ext4_prealloc_space *pa;
3893                 ext4_grpblk_t start;
3894                 struct list_head *cur;
3895                 ext4_lock_group(sb, i);
3896                 list_for_each(cur, &grp->bb_prealloc_list) {
3897                         pa = list_entry(cur, struct ext4_prealloc_space,
3898                                         pa_group_list);
3899                         spin_lock(&pa->pa_lock);
3900                         ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3901                                                      NULL, &start);
3902                         spin_unlock(&pa->pa_lock);
3903                         printk(KERN_ERR "PA:%u:%d:%u \n", i,
3904                                start, pa->pa_len);
3905                 }
3906                 ext4_unlock_group(sb, i);
3907
3908                 if (grp->bb_free == 0)
3909                         continue;
3910                 printk(KERN_ERR "%u: %d/%d \n",
3911                        i, grp->bb_free, grp->bb_fragments);
3912         }
3913         printk(KERN_ERR "\n");
3914 }
3915 #else
3916 static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
3917 {
3918         return;
3919 }
3920 #endif
3921
3922 /*
3923  * We use locality group preallocation for small size file. The size of the
3924  * file is determined by the current size or the resulting size after
3925  * allocation which ever is larger
3926  *
3927  * One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req
3928  */
3929 static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
3930 {
3931         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3932         int bsbits = ac->ac_sb->s_blocksize_bits;
3933         loff_t size, isize;
3934
3935         if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3936                 return;
3937
3938         if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
3939                 return;
3940
3941         size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
3942         isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)
3943                 >> bsbits;
3944
3945         if ((size == isize) &&
3946             !ext4_fs_is_busy(sbi) &&
3947             (atomic_read(&ac->ac_inode->i_writecount) == 0)) {
3948                 ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;
3949                 return;
3950         }
3951
3952         if (sbi->s_mb_group_prealloc <= 0) {
3953                 ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
3954                 return;
3955         }
3956
3957         /* don't use group allocation for large files */
3958         size = max(size, isize);
3959         if (size > sbi->s_mb_stream_request) {
3960                 ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
3961                 return;
3962         }
3963
3964         BUG_ON(ac->ac_lg != NULL);
3965         /*
3966          * locality group prealloc space are per cpu. The reason for having
3967          * per cpu locality group is to reduce the contention between block
3968          * request from multiple CPUs.
3969          */
3970         ac->ac_lg = __this_cpu_ptr(sbi->s_locality_groups);
3971
3972         /* we're going to use group allocation */
3973         ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
3974
3975         /* serialize all allocations in the group */
3976         mutex_lock(&ac->ac_lg->lg_mutex);
3977 }
3978
3979 static noinline_for_stack int
3980 ext4_mb_initialize_context(struct ext4_allocation_context *ac,
3981                                 struct ext4_allocation_request *ar)
3982 {
3983         struct super_block *sb = ar->inode->i_sb;
3984         struct ext4_sb_info *sbi = EXT4_SB(sb);
3985         struct ext4_super_block *es = sbi->s_es;
3986         ext4_group_t group;
3987         unsigned int len;
3988         ext4_fsblk_t goal;
3989         ext4_grpblk_t block;
3990
3991         /* we can't allocate > group size */
3992         len = ar->len;
3993
3994         /* just a dirty hack to filter too big requests  */
3995         if (len >= EXT4_CLUSTERS_PER_GROUP(sb) - 10)
3996                 len = EXT4_CLUSTERS_PER_GROUP(sb) - 10;
3997
3998         /* start searching from the goal */
3999         goal = ar->goal;
4000         if (goal < le32_to_cpu(es->s_first_data_block) ||
4001                         goal >= ext4_blocks_count(es))
4002                 goal = le32_to_cpu(es->s_first_data_block);
4003         ext4_get_group_no_and_offset(sb, goal, &group, &block);
4004
4005         /* set up allocation goals */
4006         memset(ac, 0, sizeof(struct ext4_allocation_context));
4007         ac->ac_b_ex.fe_logical = ar->logical & ~(sbi->s_cluster_ratio - 1);
4008         ac->ac_status = AC_STATUS_CONTINUE;
4009         ac->ac_sb = sb;
4010         ac->ac_inode = ar->inode;
4011         ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
4012         ac->ac_o_ex.fe_group = group;
4013         ac->ac_o_ex.fe_start = block;
4014         ac->ac_o_ex.fe_len = len;
4015         ac->ac_g_ex = ac->ac_o_ex;
4016         ac->ac_flags = ar->flags;
4017
4018         /* we have to define context: we'll we work with a file or
4019          * locality group. this is a policy, actually */
4020         ext4_mb_group_or_file(ac);
4021
4022         mb_debug(1, "init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, "
4023                         "left: %u/%u, right %u/%u to %swritable\n",
4024                         (unsigned) ar->len, (unsigned) ar->logical,
4025                         (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
4026                         (unsigned) ar->lleft, (unsigned) ar->pleft,
4027                         (unsigned) ar->lright, (unsigned) ar->pright,
4028                         atomic_read(&ar->inode->i_writecount) ? "" : "non-");
4029         return 0;
4030
4031 }
4032
4033 static noinline_for_stack void
4034 ext4_mb_discard_lg_preallocations(struct super_block *sb,
4035                                         struct ext4_locality_group *lg,
4036                                         int order, int total_entries)
4037 {
4038         ext4_group_t group = 0;
4039         struct ext4_buddy e4b;
4040         struct list_head discard_list;
4041         struct ext4_prealloc_space *pa, *tmp;
4042
4043         mb_debug(1, "discard locality group preallocation\n");
4044
4045         INIT_LIST_HEAD(&discard_list);
4046
4047         spin_lock(&lg->lg_prealloc_lock);
4048         list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
4049                                                 pa_inode_list) {
4050                 spin_lock(&pa->pa_lock);
4051                 if (atomic_read(&pa->pa_count)) {
4052                         /*
4053                          * This is the pa that we just used
4054                          * for block allocation. So don't
4055                          * free that
4056                          */
4057                         spin_unlock(&pa->pa_lock);
4058                         continue;
4059                 }
4060                 if (pa->pa_deleted) {
4061                         spin_unlock(&pa->pa_lock);
4062                         continue;
4063                 }
4064                 /* only lg prealloc space */
4065                 BUG_ON(pa->pa_type != MB_GROUP_PA);
4066
4067                 /* seems this one can be freed ... */
4068                 pa->pa_deleted = 1;
4069                 spin_unlock(&pa->pa_lock);
4070
4071                 list_del_rcu(&pa->pa_inode_list);
4072                 list_add(&pa->u.pa_tmp_list, &discard_list);
4073
4074                 total_entries--;
4075                 if (total_entries <= 5) {
4076                         /*
4077                          * we want to keep only 5 entries
4078                          * allowing it to grow to 8. This
4079                          * mak sure we don't call discard
4080                          * soon for this list.
4081                          */
4082                         break;
4083                 }
4084         }
4085         spin_unlock(&lg->lg_prealloc_lock);
4086
4087         list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {
4088
4089                 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
4090                 if (ext4_mb_load_buddy(sb, group, &e4b)) {
4091                         ext4_error(sb, "Error loading buddy information for %u",
4092                                         group);
4093                         continue;
4094                 }
4095                 ext4_lock_group(sb, group);
4096                 list_del(&pa->pa_group_list);
4097                 ext4_mb_release_group_pa(&e4b, pa);
4098                 ext4_unlock_group(sb, group);
4099
4100                 ext4_mb_unload_buddy(&e4b);
4101                 list_del(&pa->u.pa_tmp_list);
4102                 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
4103         }
4104 }
4105
4106 /*
4107  * We have incremented pa_count. So it cannot be freed at this
4108  * point. Also we hold lg_mutex. So no parallel allocation is
4109  * possible from this lg. That means pa_free cannot be updated.
4110  *
4111  * A parallel ext4_mb_discard_group_preallocations is possible.
4112  * which can cause the lg_prealloc_list to be updated.
4113  */
4114
4115 static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)
4116 {
4117         int order, added = 0, lg_prealloc_count = 1;
4118         struct super_block *sb = ac->ac_sb;
4119         struct ext4_locality_group *lg = ac->ac_lg;
4120         struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;
4121
4122         order = fls(pa->pa_free) - 1;
4123         if (order > PREALLOC_TB_SIZE - 1)
4124                 /* The max size of hash table is PREALLOC_TB_SIZE */
4125                 order = PREALLOC_TB_SIZE - 1;
4126         /* Add the prealloc space to lg */
4127         rcu_read_lock();
4128         list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
4129                                                 pa_inode_list) {
4130                 spin_lock(&tmp_pa->pa_lock);
4131                 if (tmp_pa->pa_deleted) {
4132                         spin_unlock(&tmp_pa->pa_lock);
4133                         continue;
4134                 }
4135                 if (!added && pa->pa_free < tmp_pa->pa_free) {
4136                         /* Add to the tail of the previous entry */
4137                         list_add_tail_rcu(&pa->pa_inode_list,
4138                                                 &tmp_pa->pa_inode_list);
4139                         added = 1;
4140                         /*
4141                          * we want to count the total
4142                          * number of entries in the list
4143                          */
4144                 }
4145                 spin_unlock(&tmp_pa->pa_lock);
4146                 lg_prealloc_count++;
4147         }
4148         if (!added)
4149                 list_add_tail_rcu(&pa->pa_inode_list,
4150                                         &lg->lg_prealloc_list[order]);
4151         rcu_read_unlock();
4152
4153         /* Now trim the list to be not more than 8 elements */
4154         if (lg_prealloc_count > 8) {
4155                 ext4_mb_discard_lg_preallocations(sb, lg,
4156                                                 order, lg_prealloc_count);
4157                 return;
4158         }
4159         return ;
4160 }
4161
4162 /*
4163  * release all resource we used in allocation
4164  */
4165 static int ext4_mb_release_context(struct ext4_allocation_context *ac)
4166 {
4167         struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4168         struct ext4_prealloc_space *pa = ac->ac_pa;
4169         if (pa) {
4170                 if (pa->pa_type == MB_GROUP_PA) {
4171                         /* see comment in ext4_mb_use_group_pa() */
4172                         spin_lock(&pa->pa_lock);
4173                         pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4174                         pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4175                         pa->pa_free -= ac->ac_b_ex.fe_len;
4176                         pa->pa_len -= ac->ac_b_ex.fe_len;
4177                         spin_unlock(&pa->pa_lock);
4178                 }
4179         }
4180         if (pa) {
4181                 /*
4182                  * We want to add the pa to the right bucket.
4183                  * Remove it from the list and while adding
4184                  * make sure the list to which we are adding
4185                  * doesn't grow big.
4186                  */
4187                 if ((pa->pa_type == MB_GROUP_PA) && likely(pa->pa_free)) {
4188                         spin_lock(pa->pa_obj_lock);
4189                         list_del_rcu(&pa->pa_inode_list);
4190                         spin_unlock(pa->pa_obj_lock);
4191                         ext4_mb_add_n_trim(ac);
4192                 }
4193                 ext4_mb_put_pa(ac, ac->ac_sb, pa);
4194         }
4195         if (ac->ac_bitmap_page)
4196                 page_cache_release(ac->ac_bitmap_page);
4197         if (ac->ac_buddy_page)
4198                 page_cache_release(ac->ac_buddy_page);
4199         if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
4200                 mutex_unlock(&ac->ac_lg->lg_mutex);
4201         ext4_mb_collect_stats(ac);
4202         return 0;
4203 }
4204
4205 static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
4206 {
4207         ext4_group_t i, ngroups = ext4_get_groups_count(sb);
4208         int ret;
4209         int freed = 0;
4210
4211         trace_ext4_mb_discard_preallocations(sb, needed);
4212         for (i = 0; i < ngroups && needed > 0; i++) {
4213                 ret = ext4_mb_discard_group_preallocations(sb, i, needed);
4214                 freed += ret;
4215                 needed -= ret;
4216         }
4217
4218         return freed;
4219 }
4220
4221 /*
4222  * Main entry point into mballoc to allocate blocks
4223  * it tries to use preallocation first, then falls back
4224  * to usual allocation
4225  */
4226 ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
4227                                 struct ext4_allocation_request *ar, int *errp)
4228 {
4229         int freed;
4230         struct ext4_allocation_context *ac = NULL;
4231         struct ext4_sb_info *sbi;
4232         struct super_block *sb;
4233         ext4_fsblk_t block = 0;
4234         unsigned int inquota = 0;
4235         unsigned int reserv_clstrs = 0;
4236
4237         sb = ar->inode->i_sb;
4238         sbi = EXT4_SB(sb);
4239
4240         trace_ext4_request_blocks(ar);
4241
4242         /* Allow to use superuser reservation for quota file */
4243         if (IS_NOQUOTA(ar->inode))
4244                 ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;
4245
4246         /*
4247          * For delayed allocation, we could skip the ENOSPC and
4248          * EDQUOT check, as blocks and quotas have been already
4249          * reserved when data being copied into pagecache.
4250          */
4251         if (ext4_test_inode_state(ar->inode, EXT4_STATE_DELALLOC_RESERVED))
4252                 ar->flags |= EXT4_MB_DELALLOC_RESERVED;
4253         else {
4254                 /* Without delayed allocation we need to verify
4255                  * there is enough free blocks to do block allocation
4256                  * and verify allocation doesn't exceed the quota limits.
4257                  */
4258                 while (ar->len &&
4259                         ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {
4260
4261                         /* let others to free the space */
4262                         yield();
4263                         ar->len = ar->len >> 1;
4264                 }
4265                 if (!ar->len) {
4266                         *errp = -ENOSPC;
4267                         return 0;
4268                 }
4269                 reserv_clstrs = ar->len;
4270                 if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {
4271                         dquot_alloc_block_nofail(ar->inode,
4272                                                  EXT4_C2B(sbi, ar->len));
4273                 } else {
4274                         while (ar->len &&
4275                                 dquot_alloc_block(ar->inode,
4276                                                   EXT4_C2B(sbi, ar->len))) {
4277
4278                                 ar->flags |= EXT4_MB_HINT_NOPREALLOC;
4279                                 ar->len--;
4280                         }
4281                 }
4282                 inquota = ar->len;
4283                 if (ar->len == 0) {
4284                         *errp = -EDQUOT;
4285                         goto out;
4286                 }
4287         }
4288
4289         ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
4290         if (!ac) {
4291                 ar->len = 0;
4292                 *errp = -ENOMEM;
4293                 goto out;
4294         }
4295
4296         *errp = ext4_mb_initialize_context(ac, ar);
4297         if (*errp) {
4298                 ar->len = 0;
4299                 goto out;
4300         }
4301
4302         ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
4303         if (!ext4_mb_use_preallocated(ac)) {
4304                 ac->ac_op = EXT4_MB_HISTORY_ALLOC;
4305                 ext4_mb_normalize_request(ac, ar);
4306 repeat:
4307                 /* allocate space in core */
4308                 *errp = ext4_mb_regular_allocator(ac);
4309                 if (*errp)
4310                         goto errout;
4311
4312                 /* as we've just preallocated more space than
4313                  * user requested orinally, we store allocated
4314                  * space in a special descriptor */
4315                 if (ac->ac_status == AC_STATUS_FOUND &&
4316                                 ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
4317                         ext4_mb_new_preallocation(ac);
4318         }
4319         if (likely(ac->ac_status == AC_STATUS_FOUND)) {
4320                 *errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs);
4321                 if (*errp == -EAGAIN) {
4322                         /*
4323                          * drop the reference that we took
4324                          * in ext4_mb_use_best_found
4325                          */
4326                         ext4_mb_release_context(ac);
4327                         ac->ac_b_ex.fe_group = 0;
4328                         ac->ac_b_ex.fe_start = 0;
4329                         ac->ac_b_ex.fe_len = 0;
4330                         ac->ac_status = AC_STATUS_CONTINUE;
4331                         goto repeat;
4332                 } else if (*errp)
4333                 errout:
4334                         ext4_discard_allocated_blocks(ac);
4335                 else {
4336                         block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
4337                         ar->len = ac->ac_b_ex.fe_len;
4338                 }
4339         } else {
4340                 freed  = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
4341                 if (freed)
4342                         goto repeat;
4343                 *errp = -ENOSPC;
4344         }
4345
4346         if (*errp) {
4347                 ac->ac_b_ex.fe_len = 0;
4348                 ar->len = 0;
4349                 ext4_mb_show_ac(ac);
4350         }
4351         ext4_mb_release_context(ac);
4352 out:
4353         if (ac)
4354                 kmem_cache_free(ext4_ac_cachep, ac);
4355         if (inquota && ar->len < inquota)
4356                 dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));
4357         if (!ar->len) {
4358                 if (!ext4_test_inode_state(ar->inode,
4359                                            EXT4_STATE_DELALLOC_RESERVED))
4360                         /* release all the reserved blocks if non delalloc */
4361                         percpu_counter_sub(&sbi->s_dirtyclusters_counter,
4362                                                 reserv_clstrs);
4363         }
4364
4365         trace_ext4_allocate_blocks(ar, (unsigned long long)block);
4366
4367         return block;
4368 }
4369
4370 /*
4371  * We can merge two free data extents only if the physical blocks
4372  * are contiguous, AND the extents were freed by the same transaction,
4373  * AND the blocks are associated with the same group.
4374  */
4375 static int can_merge(struct ext4_free_data *entry1,
4376                         struct ext4_free_data *entry2)
4377 {
4378         if ((entry1->efd_tid == entry2->efd_tid) &&
4379             (entry1->efd_group == entry2->efd_group) &&
4380             ((entry1->efd_start_cluster + entry1->efd_count) == entry2->efd_start_cluster))
4381                 return 1;
4382         return 0;
4383 }
4384
4385 static noinline_for_stack int
4386 ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
4387                       struct ext4_free_data *new_entry)
4388 {
4389         ext4_group_t group = e4b->bd_group;
4390         ext4_grpblk_t cluster;
4391         struct ext4_free_data *entry;
4392         struct ext4_group_info *db = e4b->bd_info;
4393         struct super_block *sb = e4b->bd_sb;
4394         struct ext4_sb_info *sbi = EXT4_SB(sb);
4395         struct rb_node **n = &db->bb_free_root.rb_node, *node;
4396         struct rb_node *parent = NULL, *new_node;
4397
4398         BUG_ON(!ext4_handle_valid(handle));
4399         BUG_ON(e4b->bd_bitmap_page == NULL);
4400         BUG_ON(e4b->bd_buddy_page == NULL);
4401
4402         new_node = &new_entry->efd_node;
4403         cluster = new_entry->efd_start_cluster;
4404
4405         if (!*n) {
4406                 /* first free block exent. We need to
4407                    protect buddy cache from being freed,
4408                  * otherwise we'll refresh it from
4409                  * on-disk bitmap and lose not-yet-available
4410                  * blocks */
4411                 page_cache_get(e4b->bd_buddy_page);
4412                 page_cache_get(e4b->bd_bitmap_page);
4413         }
4414         while (*n) {
4415                 parent = *n;
4416                 entry = rb_entry(parent, struct ext4_free_data, efd_node);
4417                 if (cluster < entry->efd_start_cluster)
4418                         n = &(*n)->rb_left;
4419                 else if (cluster >= (entry->efd_start_cluster + entry->efd_count))
4420                         n = &(*n)->rb_right;
4421                 else {
4422                         ext4_grp_locked_error(sb, group, 0,
4423                                 ext4_group_first_block_no(sb, group) +
4424                                 EXT4_C2B(sbi, cluster),
4425                                 "Block already on to-be-freed list");
4426                         return 0;
4427                 }
4428         }
4429
4430         rb_link_node(new_node, parent, n);
4431         rb_insert_color(new_node, &db->bb_free_root);
4432
4433         /* Now try to see the extent can be merged to left and right */
4434         node = rb_prev(new_node);
4435         if (node) {
4436                 entry = rb_entry(node, struct ext4_free_data, efd_node);
4437                 if (can_merge(entry, new_entry)) {
4438                         new_entry->efd_start_cluster = entry->efd_start_cluster;
4439                         new_entry->efd_count += entry->efd_count;
4440                         rb_erase(node, &(db->bb_free_root));
4441                         ext4_journal_callback_del(handle, &entry->efd_jce);
4442                         kmem_cache_free(ext4_free_data_cachep, entry);
4443                 }
4444         }
4445
4446         node = rb_next(new_node);
4447         if (node) {
4448                 entry = rb_entry(node, struct ext4_free_data, efd_node);
4449                 if (can_merge(new_entry, entry)) {
4450                         new_entry->efd_count += entry->efd_count;
4451                         rb_erase(node, &(db->bb_free_root));
4452                         ext4_journal_callback_del(handle, &entry->efd_jce);
4453                         kmem_cache_free(ext4_free_data_cachep, entry);
4454                 }
4455         }
4456         /* Add the extent to transaction's private list */
4457         ext4_journal_callback_add(handle, ext4_free_data_callback,
4458                                   &new_entry->efd_jce);
4459         return 0;
4460 }
4461
4462 /**
4463  * ext4_free_blocks() -- Free given blocks and update quota
4464  * @handle:             handle for this transaction
4465  * @inode:              inode
4466  * @block:              start physical block to free
4467  * @count:              number of blocks to count
4468  * @flags:              flags used by ext4_free_blocks
4469  */
4470 void ext4_free_blocks(handle_t *handle, struct inode *inode,
4471                       struct buffer_head *bh, ext4_fsblk_t block,
4472                       unsigned long count, int flags)
4473 {
4474         struct buffer_head *bitmap_bh = NULL;
4475         struct super_block *sb = inode->i_sb;
4476         struct ext4_group_desc *gdp;
4477         unsigned long freed = 0;
4478         unsigned int overflow;
4479         ext4_grpblk_t bit;
4480         struct buffer_head *gd_bh;
4481         ext4_group_t block_group;
4482         struct ext4_sb_info *sbi;
4483         struct ext4_buddy e4b;
4484         unsigned int count_clusters;
4485         int err = 0;
4486         int ret;
4487
4488         if (bh) {
4489                 if (block)
4490                         BUG_ON(block != bh->b_blocknr);
4491                 else
4492                         block = bh->b_blocknr;
4493         }
4494
4495         sbi = EXT4_SB(sb);
4496         if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&
4497             !ext4_data_block_valid(sbi, block, count)) {
4498                 ext4_error(sb, "Freeing blocks not in datazone - "
4499                            "block = %llu, count = %lu", block, count);
4500                 goto error_return;
4501         }
4502
4503         ext4_debug("freeing block %llu\n", block);
4504         trace_ext4_free_blocks(inode, block, count, flags);
4505
4506         if (flags & EXT4_FREE_BLOCKS_FORGET) {
4507                 struct buffer_head *tbh = bh;
4508                 int i;
4509
4510                 BUG_ON(bh && (count > 1));
4511
4512                 for (i = 0; i < count; i++) {
4513                         if (!bh)
4514                                 tbh = sb_find_get_block(inode->i_sb,
4515                                                         block + i);
4516                         if (unlikely(!tbh))
4517                                 continue;
4518                         ext4_forget(handle, flags & EXT4_FREE_BLOCKS_METADATA,
4519                                     inode, tbh, block + i);
4520                 }
4521         }
4522
4523         /*
4524          * We need to make sure we don't reuse the freed block until
4525          * after the transaction is committed, which we can do by
4526          * treating the block as metadata, below.  We make an
4527          * exception if the inode is to be written in writeback mode
4528          * since writeback mode has weak data consistency guarantees.
4529          */
4530         if (!ext4_should_writeback_data(inode))
4531                 flags |= EXT4_FREE_BLOCKS_METADATA;
4532
4533         /*
4534          * If the extent to be freed does not begin on a cluster
4535          * boundary, we need to deal with partial clusters at the
4536          * beginning and end of the extent.  Normally we will free
4537          * blocks at the beginning or the end unless we are explicitly
4538          * requested to avoid doing so.
4539          */
4540         overflow = block & (sbi->s_cluster_ratio - 1);
4541         if (overflow) {
4542                 if (flags & EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER) {
4543                         overflow = sbi->s_cluster_ratio - overflow;
4544                         block += overflow;
4545                         if (count > overflow)
4546                                 count -= overflow;
4547                         else
4548                                 return;
4549                 } else {
4550                         block -= overflow;
4551                         count += overflow;
4552                 }
4553         }
4554         overflow = count & (sbi->s_cluster_ratio - 1);
4555         if (overflow) {
4556                 if (flags & EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER) {
4557                         if (count > overflow)
4558                                 count -= overflow;
4559                         else
4560                                 return;
4561                 } else
4562                         count += sbi->s_cluster_ratio - overflow;
4563         }
4564
4565 do_more:
4566         overflow = 0;
4567         ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
4568
4569         /*
4570          * Check to see if we are freeing blocks across a group
4571          * boundary.
4572          */
4573         if (EXT4_C2B(sbi, bit) + count > EXT4_BLOCKS_PER_GROUP(sb)) {
4574                 overflow = EXT4_C2B(sbi, bit) + count -
4575                         EXT4_BLOCKS_PER_GROUP(sb);
4576                 count -= overflow;
4577         }
4578         count_clusters = EXT4_B2C(sbi, count);
4579         bitmap_bh = ext4_read_block_bitmap(sb, block_group);
4580         if (!bitmap_bh) {
4581                 err = -EIO;
4582                 goto error_return;
4583         }
4584         gdp = ext4_get_group_desc(sb, block_group, &gd_bh);
4585         if (!gdp) {
4586                 err = -EIO;
4587                 goto error_return;
4588         }
4589
4590         if (in_range(ext4_block_bitmap(sb, gdp), block, count) ||
4591             in_range(ext4_inode_bitmap(sb, gdp), block, count) ||
4592             in_range(block, ext4_inode_table(sb, gdp),
4593                      EXT4_SB(sb)->s_itb_per_group) ||
4594             in_range(block + count - 1, ext4_inode_table(sb, gdp),
4595                      EXT4_SB(sb)->s_itb_per_group)) {
4596
4597                 ext4_error(sb, "Freeing blocks in system zone - "
4598                            "Block = %llu, count = %lu", block, count);
4599                 /* err = 0. ext4_std_error should be a no op */
4600                 goto error_return;
4601         }
4602
4603         BUFFER_TRACE(bitmap_bh, "getting write access");
4604         err = ext4_journal_get_write_access(handle, bitmap_bh);
4605         if (err)
4606                 goto error_return;
4607
4608         /*
4609          * We are about to modify some metadata.  Call the journal APIs
4610          * to unshare ->b_data if a currently-committing transaction is
4611          * using it
4612          */
4613         BUFFER_TRACE(gd_bh, "get_write_access");
4614         err = ext4_journal_get_write_access(handle, gd_bh);
4615         if (err)
4616                 goto error_return;
4617 #ifdef AGGRESSIVE_CHECK
4618         {
4619                 int i;
4620                 for (i = 0; i < count_clusters; i++)
4621                         BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));
4622         }
4623 #endif
4624         trace_ext4_mballoc_free(sb, inode, block_group, bit, count_clusters);
4625
4626         err = ext4_mb_load_buddy(sb, block_group, &e4b);
4627         if (err)
4628                 goto error_return;
4629
4630         if ((flags & EXT4_FREE_BLOCKS_METADATA) && ext4_handle_valid(handle)) {
4631                 struct ext4_free_data *new_entry;
4632                 /*
4633                  * blocks being freed are metadata. these blocks shouldn't
4634                  * be used until this transaction is committed
4635                  */
4636                 new_entry = kmem_cache_alloc(ext4_free_data_cachep, GFP_NOFS);
4637                 if (!new_entry) {
4638                         ext4_mb_unload_buddy(&e4b);
4639                         err = -ENOMEM;
4640                         goto error_return;
4641                 }
4642                 new_entry->efd_start_cluster = bit;
4643                 new_entry->efd_group = block_group;
4644                 new_entry->efd_count = count_clusters;
4645                 new_entry->efd_tid = handle->h_transaction->t_tid;
4646
4647                 ext4_lock_group(sb, block_group);
4648                 mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);
4649                 ext4_mb_free_metadata(handle, &e4b, new_entry);
4650         } else {
4651                 /* need to update group_info->bb_free and bitmap
4652                  * with group lock held. generate_buddy look at
4653                  * them with group lock_held
4654                  */
4655                 ext4_lock_group(sb, block_group);
4656                 mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);
4657                 mb_free_blocks(inode, &e4b, bit, count_clusters);
4658         }
4659
4660         ret = ext4_free_group_clusters(sb, gdp) + count_clusters;
4661         ext4_free_group_clusters_set(sb, gdp, ret);
4662         ext4_block_bitmap_csum_set(sb, block_group, gdp, bitmap_bh,
4663                                    EXT4_BLOCKS_PER_GROUP(sb) / 8);
4664         ext4_group_desc_csum_set(sb, 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         ext4_block_bitmap_csum_set(sb, block_group, desc, bitmap_bh,
4809                                    EXT4_BLOCKS_PER_GROUP(sb) / 8);
4810         ext4_group_desc_csum_set(sb, block_group, desc);
4811         ext4_unlock_group(sb, block_group);
4812         percpu_counter_add(&sbi->s_freeclusters_counter,
4813                            EXT4_B2C(sbi, blocks_freed));
4814
4815         if (sbi->s_log_groups_per_flex) {
4816                 ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
4817                 atomic_add(EXT4_B2C(sbi, blocks_freed),
4818                            &sbi->s_flex_groups[flex_group].free_clusters);
4819         }
4820
4821         ext4_mb_unload_buddy(&e4b);
4822
4823         /* We dirtied the bitmap block */
4824         BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
4825         err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
4826
4827         /* And the group descriptor block */
4828         BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
4829         ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh);
4830         if (!err)
4831                 err = ret;
4832
4833 error_return:
4834         brelse(bitmap_bh);
4835         ext4_std_error(sb, err);
4836         return err;
4837 }
4838
4839 /**
4840  * ext4_trim_extent -- function to TRIM one single free extent in the group
4841  * @sb:         super block for the file system
4842  * @start:      starting block of the free extent in the alloc. group
4843  * @count:      number of blocks to TRIM
4844  * @group:      alloc. group we are working with
4845  * @e4b:        ext4 buddy for the group
4846  *
4847  * Trim "count" blocks starting at "start" in the "group". To assure that no
4848  * one will allocate those blocks, mark it as used in buddy bitmap. This must
4849  * be called with under the group lock.
4850  */
4851 static void ext4_trim_extent(struct super_block *sb, int start, int count,
4852                              ext4_group_t group, struct ext4_buddy *e4b)
4853 {
4854         struct ext4_free_extent ex;
4855
4856         trace_ext4_trim_extent(sb, group, start, count);
4857
4858         assert_spin_locked(ext4_group_lock_ptr(sb, group));
4859
4860         ex.fe_start = start;
4861         ex.fe_group = group;
4862         ex.fe_len = count;
4863
4864         /*
4865          * Mark blocks used, so no one can reuse them while
4866          * being trimmed.
4867          */
4868         mb_mark_used(e4b, &ex);
4869         ext4_unlock_group(sb, group);
4870         ext4_issue_discard(sb, group, start, count);
4871         ext4_lock_group(sb, group);
4872         mb_free_blocks(NULL, e4b, start, ex.fe_len);
4873 }
4874
4875 /**
4876  * ext4_trim_all_free -- function to trim all free space in alloc. group
4877  * @sb:                 super block for file system
4878  * @group:              group to be trimmed
4879  * @start:              first group block to examine
4880  * @max:                last group block to examine
4881  * @minblocks:          minimum extent block count
4882  *
4883  * ext4_trim_all_free walks through group's buddy bitmap searching for free
4884  * extents. When the free block is found, ext4_trim_extent is called to TRIM
4885  * the extent.
4886  *
4887  *
4888  * ext4_trim_all_free walks through group's block bitmap searching for free
4889  * extents. When the free extent is found, mark it as used in group buddy
4890  * bitmap. Then issue a TRIM command on this extent and free the extent in
4891  * the group buddy bitmap. This is done until whole group is scanned.
4892  */
4893 static ext4_grpblk_t
4894 ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
4895                    ext4_grpblk_t start, ext4_grpblk_t max,
4896                    ext4_grpblk_t minblocks)
4897 {
4898         void *bitmap;
4899         ext4_grpblk_t next, count = 0, free_count = 0;
4900         struct ext4_buddy e4b;
4901         int ret;
4902
4903         trace_ext4_trim_all_free(sb, group, start, max);
4904
4905         ret = ext4_mb_load_buddy(sb, group, &e4b);
4906         if (ret) {
4907                 ext4_error(sb, "Error in loading buddy "
4908                                 "information for %u", group);
4909                 return ret;
4910         }
4911         bitmap = e4b.bd_bitmap;
4912
4913         ext4_lock_group(sb, group);
4914         if (EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) &&
4915             minblocks >= atomic_read(&EXT4_SB(sb)->s_last_trim_minblks))
4916                 goto out;
4917
4918         start = (e4b.bd_info->bb_first_free > start) ?
4919                 e4b.bd_info->bb_first_free : start;
4920
4921         while (start <= max) {
4922                 start = mb_find_next_zero_bit(bitmap, max + 1, start);
4923                 if (start > max)
4924                         break;
4925                 next = mb_find_next_bit(bitmap, max + 1, start);
4926
4927                 if ((next - start) >= minblocks) {
4928                         ext4_trim_extent(sb, start,
4929                                          next - start, group, &e4b);
4930                         count += next - start;
4931                 }
4932                 free_count += next - start;
4933                 start = next + 1;
4934
4935                 if (fatal_signal_pending(current)) {
4936                         count = -ERESTARTSYS;
4937                         break;
4938                 }
4939
4940                 if (need_resched()) {
4941                         ext4_unlock_group(sb, group);
4942                         cond_resched();
4943                         ext4_lock_group(sb, group);
4944                 }
4945
4946                 if ((e4b.bd_info->bb_free - free_count) < minblocks)
4947                         break;
4948         }
4949
4950         if (!ret)
4951                 EXT4_MB_GRP_SET_TRIMMED(e4b.bd_info);
4952 out:
4953         ext4_unlock_group(sb, group);
4954         ext4_mb_unload_buddy(&e4b);
4955
4956         ext4_debug("trimmed %d blocks in the group %d\n",
4957                 count, group);
4958
4959         return count;
4960 }
4961
4962 /**
4963  * ext4_trim_fs() -- trim ioctl handle function
4964  * @sb:                 superblock for filesystem
4965  * @range:              fstrim_range structure
4966  *
4967  * start:       First Byte to trim
4968  * len:         number of Bytes to trim from start
4969  * minlen:      minimum extent length in Bytes
4970  * ext4_trim_fs goes through all allocation groups containing Bytes from
4971  * start to start+len. For each such a group ext4_trim_all_free function
4972  * is invoked to trim all free space.
4973  */
4974 int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range)
4975 {
4976         struct ext4_group_info *grp;
4977         ext4_group_t group, first_group, last_group;
4978         ext4_grpblk_t cnt = 0, first_cluster, last_cluster;
4979         uint64_t start, end, minlen, trimmed = 0;
4980         ext4_fsblk_t first_data_blk =
4981                         le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
4982         ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);
4983         int ret = 0;
4984
4985         start = range->start >> sb->s_blocksize_bits;
4986         end = start + (range->len >> sb->s_blocksize_bits) - 1;
4987         minlen = range->minlen >> sb->s_blocksize_bits;
4988
4989         if (unlikely(minlen > EXT4_CLUSTERS_PER_GROUP(sb)) ||
4990             unlikely(start >= max_blks))
4991                 return -EINVAL;
4992         if (end >= max_blks)
4993                 end = max_blks - 1;
4994         if (end <= first_data_blk)
4995                 goto out;
4996         if (start < first_data_blk)
4997                 start = first_data_blk;
4998
4999         /* Determine first and last group to examine based on start and end */
5000         ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) start,
5001                                      &first_group, &first_cluster);
5002         ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) end,
5003                                      &last_group, &last_cluster);
5004
5005         /* end now represents the last cluster to discard in this group */
5006         end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
5007
5008         for (group = first_group; group <= last_group; group++) {
5009                 grp = ext4_get_group_info(sb, group);
5010                 /* We only do this if the grp has never been initialized */
5011                 if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
5012                         ret = ext4_mb_init_group(sb, group);
5013                         if (ret)
5014                                 break;
5015                 }
5016
5017                 /*
5018                  * For all the groups except the last one, last cluster will
5019                  * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to
5020                  * change it for the last group, note that last_cluster is
5021                  * already computed earlier by ext4_get_group_no_and_offset()
5022                  */
5023                 if (group == last_group)
5024                         end = last_cluster;
5025
5026                 if (grp->bb_free >= minlen) {
5027                         cnt = ext4_trim_all_free(sb, group, first_cluster,
5028                                                 end, minlen);
5029                         if (cnt < 0) {
5030                                 ret = cnt;
5031                                 break;
5032                         }
5033                         trimmed += cnt;
5034                 }
5035
5036                 /*
5037                  * For every group except the first one, we are sure
5038                  * that the first cluster to discard will be cluster #0.
5039                  */
5040                 first_cluster = 0;
5041         }
5042
5043         if (!ret)
5044                 atomic_set(&EXT4_SB(sb)->s_last_trim_minblks, minlen);
5045
5046 out:
5047         range->len = trimmed * sb->s_blocksize;
5048         return ret;
5049 }