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