Root/fs/ext4/mballoc.c

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

Archive Download this file



interactive