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