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