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