~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/ext4/mballoc.c

Version: ~ [ linux-5.9-rc5 ] ~ [ linux-5.8.10 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.66 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.146 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.198 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.236 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.236 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp