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