Merge branch 'kvm-updates-2.6.26' of git://git.kernel.org/pub/scm/linux/kernel/git...
[linux-2.6] / fs / ext4 / balloc.c
1 /*
2  *  linux/fs/ext4/balloc.c
3  *
4  * Copyright (C) 1992, 1993, 1994, 1995
5  * Remy Card (card@masi.ibp.fr)
6  * Laboratoire MASI - Institut Blaise Pascal
7  * Universite Pierre et Marie Curie (Paris VI)
8  *
9  *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
10  *  Big-endian to little-endian byte-swapping/bitmaps by
11  *        David S. Miller (davem@caip.rutgers.edu), 1995
12  */
13
14 #include <linux/time.h>
15 #include <linux/capability.h>
16 #include <linux/fs.h>
17 #include <linux/jbd2.h>
18 #include <linux/quotaops.h>
19 #include <linux/buffer_head.h>
20 #include "ext4.h"
21 #include "ext4_jbd2.h"
22 #include "group.h"
23
24 /*
25  * balloc.c contains the blocks allocation and deallocation routines
26  */
27
28 /*
29  * Calculate the block group number and offset, given a block number
30  */
31 void ext4_get_group_no_and_offset(struct super_block *sb, ext4_fsblk_t blocknr,
32                 ext4_group_t *blockgrpp, ext4_grpblk_t *offsetp)
33 {
34         struct ext4_super_block *es = EXT4_SB(sb)->s_es;
35         ext4_grpblk_t offset;
36
37         blocknr = blocknr - le32_to_cpu(es->s_first_data_block);
38         offset = do_div(blocknr, EXT4_BLOCKS_PER_GROUP(sb));
39         if (offsetp)
40                 *offsetp = offset;
41         if (blockgrpp)
42                 *blockgrpp = blocknr;
43
44 }
45
46 static int ext4_block_in_group(struct super_block *sb, ext4_fsblk_t block,
47                         ext4_group_t block_group)
48 {
49         ext4_group_t actual_group;
50         ext4_get_group_no_and_offset(sb, block, &actual_group, 0);
51         if (actual_group == block_group)
52                 return 1;
53         return 0;
54 }
55
56 static int ext4_group_used_meta_blocks(struct super_block *sb,
57                                 ext4_group_t block_group)
58 {
59         ext4_fsblk_t tmp;
60         struct ext4_sb_info *sbi = EXT4_SB(sb);
61         /* block bitmap, inode bitmap, and inode table blocks */
62         int used_blocks = sbi->s_itb_per_group + 2;
63
64         if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FLEX_BG)) {
65                 struct ext4_group_desc *gdp;
66                 struct buffer_head *bh;
67
68                 gdp = ext4_get_group_desc(sb, block_group, &bh);
69                 if (!ext4_block_in_group(sb, ext4_block_bitmap(sb, gdp),
70                                         block_group))
71                         used_blocks--;
72
73                 if (!ext4_block_in_group(sb, ext4_inode_bitmap(sb, gdp),
74                                         block_group))
75                         used_blocks--;
76
77                 tmp = ext4_inode_table(sb, gdp);
78                 for (; tmp < ext4_inode_table(sb, gdp) +
79                                 sbi->s_itb_per_group; tmp++) {
80                         if (!ext4_block_in_group(sb, tmp, block_group))
81                                 used_blocks -= 1;
82                 }
83         }
84         return used_blocks;
85 }
86 /* Initializes an uninitialized block bitmap if given, and returns the
87  * number of blocks free in the group. */
88 unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
89                  ext4_group_t block_group, struct ext4_group_desc *gdp)
90 {
91         int bit, bit_max;
92         unsigned free_blocks, group_blocks;
93         struct ext4_sb_info *sbi = EXT4_SB(sb);
94
95         if (bh) {
96                 J_ASSERT_BH(bh, buffer_locked(bh));
97
98                 /* If checksum is bad mark all blocks used to prevent allocation
99                  * essentially implementing a per-group read-only flag. */
100                 if (!ext4_group_desc_csum_verify(sbi, block_group, gdp)) {
101                         ext4_error(sb, __func__,
102                                   "Checksum bad for group %lu\n", block_group);
103                         gdp->bg_free_blocks_count = 0;
104                         gdp->bg_free_inodes_count = 0;
105                         gdp->bg_itable_unused = 0;
106                         memset(bh->b_data, 0xff, sb->s_blocksize);
107                         return 0;
108                 }
109                 memset(bh->b_data, 0, sb->s_blocksize);
110         }
111
112         /* Check for superblock and gdt backups in this group */
113         bit_max = ext4_bg_has_super(sb, block_group);
114
115         if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_META_BG) ||
116             block_group < le32_to_cpu(sbi->s_es->s_first_meta_bg) *
117                           sbi->s_desc_per_block) {
118                 if (bit_max) {
119                         bit_max += ext4_bg_num_gdb(sb, block_group);
120                         bit_max +=
121                                 le16_to_cpu(sbi->s_es->s_reserved_gdt_blocks);
122                 }
123         } else { /* For META_BG_BLOCK_GROUPS */
124                 int group_rel = (block_group -
125                                  le32_to_cpu(sbi->s_es->s_first_meta_bg)) %
126                                 EXT4_DESC_PER_BLOCK(sb);
127                 if (group_rel == 0 || group_rel == 1 ||
128                     (group_rel == EXT4_DESC_PER_BLOCK(sb) - 1))
129                         bit_max += 1;
130         }
131
132         if (block_group == sbi->s_groups_count - 1) {
133                 /*
134                  * Even though mke2fs always initialize first and last group
135                  * if some other tool enabled the EXT4_BG_BLOCK_UNINIT we need
136                  * to make sure we calculate the right free blocks
137                  */
138                 group_blocks = ext4_blocks_count(sbi->s_es) -
139                         le32_to_cpu(sbi->s_es->s_first_data_block) -
140                         (EXT4_BLOCKS_PER_GROUP(sb) * (sbi->s_groups_count -1));
141         } else {
142                 group_blocks = EXT4_BLOCKS_PER_GROUP(sb);
143         }
144
145         free_blocks = group_blocks - bit_max;
146
147         if (bh) {
148                 ext4_fsblk_t start, tmp;
149                 int flex_bg = 0;
150
151                 for (bit = 0; bit < bit_max; bit++)
152                         ext4_set_bit(bit, bh->b_data);
153
154                 start = ext4_group_first_block_no(sb, block_group);
155
156                 if (EXT4_HAS_INCOMPAT_FEATURE(sb,
157                                               EXT4_FEATURE_INCOMPAT_FLEX_BG))
158                         flex_bg = 1;
159
160                 /* Set bits for block and inode bitmaps, and inode table */
161                 tmp = ext4_block_bitmap(sb, gdp);
162                 if (!flex_bg || ext4_block_in_group(sb, tmp, block_group))
163                         ext4_set_bit(tmp - start, bh->b_data);
164
165                 tmp = ext4_inode_bitmap(sb, gdp);
166                 if (!flex_bg || ext4_block_in_group(sb, tmp, block_group))
167                         ext4_set_bit(tmp - start, bh->b_data);
168
169                 tmp = ext4_inode_table(sb, gdp);
170                 for (; tmp < ext4_inode_table(sb, gdp) +
171                                 sbi->s_itb_per_group; tmp++) {
172                         if (!flex_bg ||
173                                 ext4_block_in_group(sb, tmp, block_group))
174                                 ext4_set_bit(tmp - start, bh->b_data);
175                 }
176                 /*
177                  * Also if the number of blocks within the group is
178                  * less than the blocksize * 8 ( which is the size
179                  * of bitmap ), set rest of the block bitmap to 1
180                  */
181                 mark_bitmap_end(group_blocks, sb->s_blocksize * 8, bh->b_data);
182         }
183         return free_blocks - ext4_group_used_meta_blocks(sb, block_group);
184 }
185
186
187 /*
188  * The free blocks are managed by bitmaps.  A file system contains several
189  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
190  * block for inodes, N blocks for the inode table and data blocks.
191  *
192  * The file system contains group descriptors which are located after the
193  * super block.  Each descriptor contains the number of the bitmap block and
194  * the free blocks count in the block.  The descriptors are loaded in memory
195  * when a file system is mounted (see ext4_fill_super).
196  */
197
198
199 #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
200
201 /**
202  * ext4_get_group_desc() -- load group descriptor from disk
203  * @sb:                 super block
204  * @block_group:        given block group
205  * @bh:                 pointer to the buffer head to store the block
206  *                      group descriptor
207  */
208 struct ext4_group_desc * ext4_get_group_desc(struct super_block * sb,
209                                              ext4_group_t block_group,
210                                              struct buffer_head ** bh)
211 {
212         unsigned long group_desc;
213         unsigned long offset;
214         struct ext4_group_desc * desc;
215         struct ext4_sb_info *sbi = EXT4_SB(sb);
216
217         if (block_group >= sbi->s_groups_count) {
218                 ext4_error (sb, "ext4_get_group_desc",
219                             "block_group >= groups_count - "
220                             "block_group = %lu, groups_count = %lu",
221                             block_group, sbi->s_groups_count);
222
223                 return NULL;
224         }
225         smp_rmb();
226
227         group_desc = block_group >> EXT4_DESC_PER_BLOCK_BITS(sb);
228         offset = block_group & (EXT4_DESC_PER_BLOCK(sb) - 1);
229         if (!sbi->s_group_desc[group_desc]) {
230                 ext4_error (sb, "ext4_get_group_desc",
231                             "Group descriptor not loaded - "
232                             "block_group = %lu, group_desc = %lu, desc = %lu",
233                              block_group, group_desc, offset);
234                 return NULL;
235         }
236
237         desc = (struct ext4_group_desc *)(
238                 (__u8 *)sbi->s_group_desc[group_desc]->b_data +
239                 offset * EXT4_DESC_SIZE(sb));
240         if (bh)
241                 *bh = sbi->s_group_desc[group_desc];
242         return desc;
243 }
244
245 static int ext4_valid_block_bitmap(struct super_block *sb,
246                                         struct ext4_group_desc *desc,
247                                         unsigned int block_group,
248                                         struct buffer_head *bh)
249 {
250         ext4_grpblk_t offset;
251         ext4_grpblk_t next_zero_bit;
252         ext4_fsblk_t bitmap_blk;
253         ext4_fsblk_t group_first_block;
254
255         if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FLEX_BG)) {
256                 /* with FLEX_BG, the inode/block bitmaps and itable
257                  * blocks may not be in the group at all
258                  * so the bitmap validation will be skipped for those groups
259                  * or it has to also read the block group where the bitmaps
260                  * are located to verify they are set.
261                  */
262                 return 1;
263         }
264         group_first_block = ext4_group_first_block_no(sb, block_group);
265
266         /* check whether block bitmap block number is set */
267         bitmap_blk = ext4_block_bitmap(sb, desc);
268         offset = bitmap_blk - group_first_block;
269         if (!ext4_test_bit(offset, bh->b_data))
270                 /* bad block bitmap */
271                 goto err_out;
272
273         /* check whether the inode bitmap block number is set */
274         bitmap_blk = ext4_inode_bitmap(sb, desc);
275         offset = bitmap_blk - group_first_block;
276         if (!ext4_test_bit(offset, bh->b_data))
277                 /* bad block bitmap */
278                 goto err_out;
279
280         /* check whether the inode table block number is set */
281         bitmap_blk = ext4_inode_table(sb, desc);
282         offset = bitmap_blk - group_first_block;
283         next_zero_bit = ext4_find_next_zero_bit(bh->b_data,
284                                 offset + EXT4_SB(sb)->s_itb_per_group,
285                                 offset);
286         if (next_zero_bit >= offset + EXT4_SB(sb)->s_itb_per_group)
287                 /* good bitmap for inode tables */
288                 return 1;
289
290 err_out:
291         ext4_error(sb, __func__,
292                         "Invalid block bitmap - "
293                         "block_group = %d, block = %llu",
294                         block_group, bitmap_blk);
295         return 0;
296 }
297 /**
298  * read_block_bitmap()
299  * @sb:                 super block
300  * @block_group:        given block group
301  *
302  * Read the bitmap for a given block_group,and validate the
303  * bits for block/inode/inode tables are set in the bitmaps
304  *
305  * Return buffer_head on success or NULL in case of failure.
306  */
307 struct buffer_head *
308 read_block_bitmap(struct super_block *sb, ext4_group_t block_group)
309 {
310         struct ext4_group_desc * desc;
311         struct buffer_head * bh = NULL;
312         ext4_fsblk_t bitmap_blk;
313
314         desc = ext4_get_group_desc(sb, block_group, NULL);
315         if (!desc)
316                 return NULL;
317         bitmap_blk = ext4_block_bitmap(sb, desc);
318         bh = sb_getblk(sb, bitmap_blk);
319         if (unlikely(!bh)) {
320                 ext4_error(sb, __func__,
321                             "Cannot read block bitmap - "
322                             "block_group = %d, block_bitmap = %llu",
323                             (int)block_group, (unsigned long long)bitmap_blk);
324                 return NULL;
325         }
326         if (bh_uptodate_or_lock(bh))
327                 return bh;
328
329         if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
330                 ext4_init_block_bitmap(sb, bh, block_group, desc);
331                 set_buffer_uptodate(bh);
332                 unlock_buffer(bh);
333                 return bh;
334         }
335         if (bh_submit_read(bh) < 0) {
336                 put_bh(bh);
337                 ext4_error(sb, __func__,
338                             "Cannot read block bitmap - "
339                             "block_group = %d, block_bitmap = %llu",
340                             (int)block_group, (unsigned long long)bitmap_blk);
341                 return NULL;
342         }
343         ext4_valid_block_bitmap(sb, desc, block_group, bh);
344         /*
345          * file system mounted not to panic on error,
346          * continue with corrupt bitmap
347          */
348         return bh;
349 }
350 /*
351  * The reservation window structure operations
352  * --------------------------------------------
353  * Operations include:
354  * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
355  *
356  * We use a red-black tree to represent per-filesystem reservation
357  * windows.
358  *
359  */
360
361 /**
362  * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
363  * @rb_root:            root of per-filesystem reservation rb tree
364  * @verbose:            verbose mode
365  * @fn:                 function which wishes to dump the reservation map
366  *
367  * If verbose is turned on, it will print the whole block reservation
368  * windows(start, end). Otherwise, it will only print out the "bad" windows,
369  * those windows that overlap with their immediate neighbors.
370  */
371 #if 1
372 static void __rsv_window_dump(struct rb_root *root, int verbose,
373                               const char *fn)
374 {
375         struct rb_node *n;
376         struct ext4_reserve_window_node *rsv, *prev;
377         int bad;
378
379 restart:
380         n = rb_first(root);
381         bad = 0;
382         prev = NULL;
383
384         printk("Block Allocation Reservation Windows Map (%s):\n", fn);
385         while (n) {
386                 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
387                 if (verbose)
388                         printk("reservation window 0x%p "
389                                "start:  %llu, end:  %llu\n",
390                                rsv, rsv->rsv_start, rsv->rsv_end);
391                 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
392                         printk("Bad reservation %p (start >= end)\n",
393                                rsv);
394                         bad = 1;
395                 }
396                 if (prev && prev->rsv_end >= rsv->rsv_start) {
397                         printk("Bad reservation %p (prev->end >= start)\n",
398                                rsv);
399                         bad = 1;
400                 }
401                 if (bad) {
402                         if (!verbose) {
403                                 printk("Restarting reservation walk in verbose mode\n");
404                                 verbose = 1;
405                                 goto restart;
406                         }
407                 }
408                 n = rb_next(n);
409                 prev = rsv;
410         }
411         printk("Window map complete.\n");
412         if (bad)
413                 BUG();
414 }
415 #define rsv_window_dump(root, verbose) \
416         __rsv_window_dump((root), (verbose), __func__)
417 #else
418 #define rsv_window_dump(root, verbose) do {} while (0)
419 #endif
420
421 /**
422  * goal_in_my_reservation()
423  * @rsv:                inode's reservation window
424  * @grp_goal:           given goal block relative to the allocation block group
425  * @group:              the current allocation block group
426  * @sb:                 filesystem super block
427  *
428  * Test if the given goal block (group relative) is within the file's
429  * own block reservation window range.
430  *
431  * If the reservation window is outside the goal allocation group, return 0;
432  * grp_goal (given goal block) could be -1, which means no specific
433  * goal block. In this case, always return 1.
434  * If the goal block is within the reservation window, return 1;
435  * otherwise, return 0;
436  */
437 static int
438 goal_in_my_reservation(struct ext4_reserve_window *rsv, ext4_grpblk_t grp_goal,
439                         ext4_group_t group, struct super_block *sb)
440 {
441         ext4_fsblk_t group_first_block, group_last_block;
442
443         group_first_block = ext4_group_first_block_no(sb, group);
444         group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
445
446         if ((rsv->_rsv_start > group_last_block) ||
447             (rsv->_rsv_end < group_first_block))
448                 return 0;
449         if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
450                 || (grp_goal + group_first_block > rsv->_rsv_end)))
451                 return 0;
452         return 1;
453 }
454
455 /**
456  * search_reserve_window()
457  * @rb_root:            root of reservation tree
458  * @goal:               target allocation block
459  *
460  * Find the reserved window which includes the goal, or the previous one
461  * if the goal is not in any window.
462  * Returns NULL if there are no windows or if all windows start after the goal.
463  */
464 static struct ext4_reserve_window_node *
465 search_reserve_window(struct rb_root *root, ext4_fsblk_t goal)
466 {
467         struct rb_node *n = root->rb_node;
468         struct ext4_reserve_window_node *rsv;
469
470         if (!n)
471                 return NULL;
472
473         do {
474                 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
475
476                 if (goal < rsv->rsv_start)
477                         n = n->rb_left;
478                 else if (goal > rsv->rsv_end)
479                         n = n->rb_right;
480                 else
481                         return rsv;
482         } while (n);
483         /*
484          * We've fallen off the end of the tree: the goal wasn't inside
485          * any particular node.  OK, the previous node must be to one
486          * side of the interval containing the goal.  If it's the RHS,
487          * we need to back up one.
488          */
489         if (rsv->rsv_start > goal) {
490                 n = rb_prev(&rsv->rsv_node);
491                 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
492         }
493         return rsv;
494 }
495
496 /**
497  * ext4_rsv_window_add() -- Insert a window to the block reservation rb tree.
498  * @sb:                 super block
499  * @rsv:                reservation window to add
500  *
501  * Must be called with rsv_lock hold.
502  */
503 void ext4_rsv_window_add(struct super_block *sb,
504                     struct ext4_reserve_window_node *rsv)
505 {
506         struct rb_root *root = &EXT4_SB(sb)->s_rsv_window_root;
507         struct rb_node *node = &rsv->rsv_node;
508         ext4_fsblk_t start = rsv->rsv_start;
509
510         struct rb_node ** p = &root->rb_node;
511         struct rb_node * parent = NULL;
512         struct ext4_reserve_window_node *this;
513
514         while (*p)
515         {
516                 parent = *p;
517                 this = rb_entry(parent, struct ext4_reserve_window_node, rsv_node);
518
519                 if (start < this->rsv_start)
520                         p = &(*p)->rb_left;
521                 else if (start > this->rsv_end)
522                         p = &(*p)->rb_right;
523                 else {
524                         rsv_window_dump(root, 1);
525                         BUG();
526                 }
527         }
528
529         rb_link_node(node, parent, p);
530         rb_insert_color(node, root);
531 }
532
533 /**
534  * ext4_rsv_window_remove() -- unlink a window from the reservation rb tree
535  * @sb:                 super block
536  * @rsv:                reservation window to remove
537  *
538  * Mark the block reservation window as not allocated, and unlink it
539  * from the filesystem reservation window rb tree. Must be called with
540  * rsv_lock hold.
541  */
542 static void rsv_window_remove(struct super_block *sb,
543                               struct ext4_reserve_window_node *rsv)
544 {
545         rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
546         rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
547         rsv->rsv_alloc_hit = 0;
548         rb_erase(&rsv->rsv_node, &EXT4_SB(sb)->s_rsv_window_root);
549 }
550
551 /*
552  * rsv_is_empty() -- Check if the reservation window is allocated.
553  * @rsv:                given reservation window to check
554  *
555  * returns 1 if the end block is EXT4_RESERVE_WINDOW_NOT_ALLOCATED.
556  */
557 static inline int rsv_is_empty(struct ext4_reserve_window *rsv)
558 {
559         /* a valid reservation end block could not be 0 */
560         return rsv->_rsv_end == EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
561 }
562
563 /**
564  * ext4_init_block_alloc_info()
565  * @inode:              file inode structure
566  *
567  * Allocate and initialize the  reservation window structure, and
568  * link the window to the ext4 inode structure at last
569  *
570  * The reservation window structure is only dynamically allocated
571  * and linked to ext4 inode the first time the open file
572  * needs a new block. So, before every ext4_new_block(s) call, for
573  * regular files, we should check whether the reservation window
574  * structure exists or not. In the latter case, this function is called.
575  * Fail to do so will result in block reservation being turned off for that
576  * open file.
577  *
578  * This function is called from ext4_get_blocks_handle(), also called
579  * when setting the reservation window size through ioctl before the file
580  * is open for write (needs block allocation).
581  *
582  * Needs down_write(i_data_sem) protection prior to call this function.
583  */
584 void ext4_init_block_alloc_info(struct inode *inode)
585 {
586         struct ext4_inode_info *ei = EXT4_I(inode);
587         struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
588         struct super_block *sb = inode->i_sb;
589
590         block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
591         if (block_i) {
592                 struct ext4_reserve_window_node *rsv = &block_i->rsv_window_node;
593
594                 rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
595                 rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
596
597                 /*
598                  * if filesystem is mounted with NORESERVATION, the goal
599                  * reservation window size is set to zero to indicate
600                  * block reservation is off
601                  */
602                 if (!test_opt(sb, RESERVATION))
603                         rsv->rsv_goal_size = 0;
604                 else
605                         rsv->rsv_goal_size = EXT4_DEFAULT_RESERVE_BLOCKS;
606                 rsv->rsv_alloc_hit = 0;
607                 block_i->last_alloc_logical_block = 0;
608                 block_i->last_alloc_physical_block = 0;
609         }
610         ei->i_block_alloc_info = block_i;
611 }
612
613 /**
614  * ext4_discard_reservation()
615  * @inode:              inode
616  *
617  * Discard(free) block reservation window on last file close, or truncate
618  * or at last iput().
619  *
620  * It is being called in three cases:
621  *      ext4_release_file(): last writer close the file
622  *      ext4_clear_inode(): last iput(), when nobody link to this file.
623  *      ext4_truncate(): when the block indirect map is about to change.
624  *
625  */
626 void ext4_discard_reservation(struct inode *inode)
627 {
628         struct ext4_inode_info *ei = EXT4_I(inode);
629         struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
630         struct ext4_reserve_window_node *rsv;
631         spinlock_t *rsv_lock = &EXT4_SB(inode->i_sb)->s_rsv_window_lock;
632
633         ext4_mb_discard_inode_preallocations(inode);
634
635         if (!block_i)
636                 return;
637
638         rsv = &block_i->rsv_window_node;
639         if (!rsv_is_empty(&rsv->rsv_window)) {
640                 spin_lock(rsv_lock);
641                 if (!rsv_is_empty(&rsv->rsv_window))
642                         rsv_window_remove(inode->i_sb, rsv);
643                 spin_unlock(rsv_lock);
644         }
645 }
646
647 /**
648  * ext4_free_blocks_sb() -- Free given blocks and update quota
649  * @handle:                     handle to this transaction
650  * @sb:                         super block
651  * @block:                      start physcial block to free
652  * @count:                      number of blocks to free
653  * @pdquot_freed_blocks:        pointer to quota
654  */
655 void ext4_free_blocks_sb(handle_t *handle, struct super_block *sb,
656                          ext4_fsblk_t block, unsigned long count,
657                          unsigned long *pdquot_freed_blocks)
658 {
659         struct buffer_head *bitmap_bh = NULL;
660         struct buffer_head *gd_bh;
661         ext4_group_t block_group;
662         ext4_grpblk_t bit;
663         unsigned long i;
664         unsigned long overflow;
665         struct ext4_group_desc * desc;
666         struct ext4_super_block * es;
667         struct ext4_sb_info *sbi;
668         int err = 0, ret;
669         ext4_grpblk_t group_freed;
670
671         *pdquot_freed_blocks = 0;
672         sbi = EXT4_SB(sb);
673         es = sbi->s_es;
674         if (block < le32_to_cpu(es->s_first_data_block) ||
675             block + count < block ||
676             block + count > ext4_blocks_count(es)) {
677                 ext4_error (sb, "ext4_free_blocks",
678                             "Freeing blocks not in datazone - "
679                             "block = %llu, count = %lu", block, count);
680                 goto error_return;
681         }
682
683         ext4_debug ("freeing block(s) %llu-%llu\n", block, block + count - 1);
684
685 do_more:
686         overflow = 0;
687         ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
688         /*
689          * Check to see if we are freeing blocks across a group
690          * boundary.
691          */
692         if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
693                 overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
694                 count -= overflow;
695         }
696         brelse(bitmap_bh);
697         bitmap_bh = read_block_bitmap(sb, block_group);
698         if (!bitmap_bh)
699                 goto error_return;
700         desc = ext4_get_group_desc (sb, block_group, &gd_bh);
701         if (!desc)
702                 goto error_return;
703
704         if (in_range(ext4_block_bitmap(sb, desc), block, count) ||
705             in_range(ext4_inode_bitmap(sb, desc), block, count) ||
706             in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||
707             in_range(block + count - 1, ext4_inode_table(sb, desc),
708                      sbi->s_itb_per_group)) {
709                 ext4_error (sb, "ext4_free_blocks",
710                             "Freeing blocks in system zones - "
711                             "Block = %llu, count = %lu",
712                             block, count);
713                 goto error_return;
714         }
715
716         /*
717          * We are about to start releasing blocks in the bitmap,
718          * so we need undo access.
719          */
720         /* @@@ check errors */
721         BUFFER_TRACE(bitmap_bh, "getting undo access");
722         err = ext4_journal_get_undo_access(handle, bitmap_bh);
723         if (err)
724                 goto error_return;
725
726         /*
727          * We are about to modify some metadata.  Call the journal APIs
728          * to unshare ->b_data if a currently-committing transaction is
729          * using it
730          */
731         BUFFER_TRACE(gd_bh, "get_write_access");
732         err = ext4_journal_get_write_access(handle, gd_bh);
733         if (err)
734                 goto error_return;
735
736         jbd_lock_bh_state(bitmap_bh);
737
738         for (i = 0, group_freed = 0; i < count; i++) {
739                 /*
740                  * An HJ special.  This is expensive...
741                  */
742 #ifdef CONFIG_JBD2_DEBUG
743                 jbd_unlock_bh_state(bitmap_bh);
744                 {
745                         struct buffer_head *debug_bh;
746                         debug_bh = sb_find_get_block(sb, block + i);
747                         if (debug_bh) {
748                                 BUFFER_TRACE(debug_bh, "Deleted!");
749                                 if (!bh2jh(bitmap_bh)->b_committed_data)
750                                         BUFFER_TRACE(debug_bh,
751                                                 "No commited data in bitmap");
752                                 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
753                                 __brelse(debug_bh);
754                         }
755                 }
756                 jbd_lock_bh_state(bitmap_bh);
757 #endif
758                 if (need_resched()) {
759                         jbd_unlock_bh_state(bitmap_bh);
760                         cond_resched();
761                         jbd_lock_bh_state(bitmap_bh);
762                 }
763                 /* @@@ This prevents newly-allocated data from being
764                  * freed and then reallocated within the same
765                  * transaction.
766                  *
767                  * Ideally we would want to allow that to happen, but to
768                  * do so requires making jbd2_journal_forget() capable of
769                  * revoking the queued write of a data block, which
770                  * implies blocking on the journal lock.  *forget()
771                  * cannot block due to truncate races.
772                  *
773                  * Eventually we can fix this by making jbd2_journal_forget()
774                  * return a status indicating whether or not it was able
775                  * to revoke the buffer.  On successful revoke, it is
776                  * safe not to set the allocation bit in the committed
777                  * bitmap, because we know that there is no outstanding
778                  * activity on the buffer any more and so it is safe to
779                  * reallocate it.
780                  */
781                 BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
782                 J_ASSERT_BH(bitmap_bh,
783                                 bh2jh(bitmap_bh)->b_committed_data != NULL);
784                 ext4_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
785                                 bh2jh(bitmap_bh)->b_committed_data);
786
787                 /*
788                  * We clear the bit in the bitmap after setting the committed
789                  * data bit, because this is the reverse order to that which
790                  * the allocator uses.
791                  */
792                 BUFFER_TRACE(bitmap_bh, "clear bit");
793                 if (!ext4_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
794                                                 bit + i, bitmap_bh->b_data)) {
795                         jbd_unlock_bh_state(bitmap_bh);
796                         ext4_error(sb, __func__,
797                                    "bit already cleared for block %llu",
798                                    (ext4_fsblk_t)(block + i));
799                         jbd_lock_bh_state(bitmap_bh);
800                         BUFFER_TRACE(bitmap_bh, "bit already cleared");
801                 } else {
802                         group_freed++;
803                 }
804         }
805         jbd_unlock_bh_state(bitmap_bh);
806
807         spin_lock(sb_bgl_lock(sbi, block_group));
808         le16_add_cpu(&desc->bg_free_blocks_count, group_freed);
809         desc->bg_checksum = ext4_group_desc_csum(sbi, block_group, desc);
810         spin_unlock(sb_bgl_lock(sbi, block_group));
811         percpu_counter_add(&sbi->s_freeblocks_counter, count);
812
813         /* We dirtied the bitmap block */
814         BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
815         err = ext4_journal_dirty_metadata(handle, bitmap_bh);
816
817         /* And the group descriptor block */
818         BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
819         ret = ext4_journal_dirty_metadata(handle, gd_bh);
820         if (!err) err = ret;
821         *pdquot_freed_blocks += group_freed;
822
823         if (overflow && !err) {
824                 block += count;
825                 count = overflow;
826                 goto do_more;
827         }
828         sb->s_dirt = 1;
829 error_return:
830         brelse(bitmap_bh);
831         ext4_std_error(sb, err);
832         return;
833 }
834
835 /**
836  * ext4_free_blocks() -- Free given blocks and update quota
837  * @handle:             handle for this transaction
838  * @inode:              inode
839  * @block:              start physical block to free
840  * @count:              number of blocks to count
841  * @metadata:           Are these metadata blocks
842  */
843 void ext4_free_blocks(handle_t *handle, struct inode *inode,
844                         ext4_fsblk_t block, unsigned long count,
845                         int metadata)
846 {
847         struct super_block * sb;
848         unsigned long dquot_freed_blocks;
849
850         /* this isn't the right place to decide whether block is metadata
851          * inode.c/extents.c knows better, but for safety ... */
852         if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
853                         ext4_should_journal_data(inode))
854                 metadata = 1;
855
856         sb = inode->i_sb;
857
858         if (!test_opt(sb, MBALLOC) || !EXT4_SB(sb)->s_group_info)
859                 ext4_free_blocks_sb(handle, sb, block, count,
860                                                 &dquot_freed_blocks);
861         else
862                 ext4_mb_free_blocks(handle, inode, block, count,
863                                                 metadata, &dquot_freed_blocks);
864         if (dquot_freed_blocks)
865                 DQUOT_FREE_BLOCK(inode, dquot_freed_blocks);
866         return;
867 }
868
869 /**
870  * ext4_test_allocatable()
871  * @nr:                 given allocation block group
872  * @bh:                 bufferhead contains the bitmap of the given block group
873  *
874  * For ext4 allocations, we must not reuse any blocks which are
875  * allocated in the bitmap buffer's "last committed data" copy.  This
876  * prevents deletes from freeing up the page for reuse until we have
877  * committed the delete transaction.
878  *
879  * If we didn't do this, then deleting something and reallocating it as
880  * data would allow the old block to be overwritten before the
881  * transaction committed (because we force data to disk before commit).
882  * This would lead to corruption if we crashed between overwriting the
883  * data and committing the delete.
884  *
885  * @@@ We may want to make this allocation behaviour conditional on
886  * data-writes at some point, and disable it for metadata allocations or
887  * sync-data inodes.
888  */
889 static int ext4_test_allocatable(ext4_grpblk_t nr, struct buffer_head *bh)
890 {
891         int ret;
892         struct journal_head *jh = bh2jh(bh);
893
894         if (ext4_test_bit(nr, bh->b_data))
895                 return 0;
896
897         jbd_lock_bh_state(bh);
898         if (!jh->b_committed_data)
899                 ret = 1;
900         else
901                 ret = !ext4_test_bit(nr, jh->b_committed_data);
902         jbd_unlock_bh_state(bh);
903         return ret;
904 }
905
906 /**
907  * bitmap_search_next_usable_block()
908  * @start:              the starting block (group relative) of the search
909  * @bh:                 bufferhead contains the block group bitmap
910  * @maxblocks:          the ending block (group relative) of the reservation
911  *
912  * The bitmap search --- search forward alternately through the actual
913  * bitmap on disk and the last-committed copy in journal, until we find a
914  * bit free in both bitmaps.
915  */
916 static ext4_grpblk_t
917 bitmap_search_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
918                                         ext4_grpblk_t maxblocks)
919 {
920         ext4_grpblk_t next;
921         struct journal_head *jh = bh2jh(bh);
922
923         while (start < maxblocks) {
924                 next = ext4_find_next_zero_bit(bh->b_data, maxblocks, start);
925                 if (next >= maxblocks)
926                         return -1;
927                 if (ext4_test_allocatable(next, bh))
928                         return next;
929                 jbd_lock_bh_state(bh);
930                 if (jh->b_committed_data)
931                         start = ext4_find_next_zero_bit(jh->b_committed_data,
932                                                         maxblocks, next);
933                 jbd_unlock_bh_state(bh);
934         }
935         return -1;
936 }
937
938 /**
939  * find_next_usable_block()
940  * @start:              the starting block (group relative) to find next
941  *                      allocatable block in bitmap.
942  * @bh:                 bufferhead contains the block group bitmap
943  * @maxblocks:          the ending block (group relative) for the search
944  *
945  * Find an allocatable block in a bitmap.  We honor both the bitmap and
946  * its last-committed copy (if that exists), and perform the "most
947  * appropriate allocation" algorithm of looking for a free block near
948  * the initial goal; then for a free byte somewhere in the bitmap; then
949  * for any free bit in the bitmap.
950  */
951 static ext4_grpblk_t
952 find_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
953                         ext4_grpblk_t maxblocks)
954 {
955         ext4_grpblk_t here, next;
956         char *p, *r;
957
958         if (start > 0) {
959                 /*
960                  * The goal was occupied; search forward for a free
961                  * block within the next XX blocks.
962                  *
963                  * end_goal is more or less random, but it has to be
964                  * less than EXT4_BLOCKS_PER_GROUP. Aligning up to the
965                  * next 64-bit boundary is simple..
966                  */
967                 ext4_grpblk_t end_goal = (start + 63) & ~63;
968                 if (end_goal > maxblocks)
969                         end_goal = maxblocks;
970                 here = ext4_find_next_zero_bit(bh->b_data, end_goal, start);
971                 if (here < end_goal && ext4_test_allocatable(here, bh))
972                         return here;
973                 ext4_debug("Bit not found near goal\n");
974         }
975
976         here = start;
977         if (here < 0)
978                 here = 0;
979
980         p = ((char *)bh->b_data) + (here >> 3);
981         r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
982         next = (r - ((char *)bh->b_data)) << 3;
983
984         if (next < maxblocks && next >= start && ext4_test_allocatable(next, bh))
985                 return next;
986
987         /*
988          * The bitmap search --- search forward alternately through the actual
989          * bitmap and the last-committed copy until we find a bit free in
990          * both
991          */
992         here = bitmap_search_next_usable_block(here, bh, maxblocks);
993         return here;
994 }
995
996 /**
997  * claim_block()
998  * @block:              the free block (group relative) to allocate
999  * @bh:                 the bufferhead containts the block group bitmap
1000  *
1001  * We think we can allocate this block in this bitmap.  Try to set the bit.
1002  * If that succeeds then check that nobody has allocated and then freed the
1003  * block since we saw that is was not marked in b_committed_data.  If it _was_
1004  * allocated and freed then clear the bit in the bitmap again and return
1005  * zero (failure).
1006  */
1007 static inline int
1008 claim_block(spinlock_t *lock, ext4_grpblk_t block, struct buffer_head *bh)
1009 {
1010         struct journal_head *jh = bh2jh(bh);
1011         int ret;
1012
1013         if (ext4_set_bit_atomic(lock, block, bh->b_data))
1014                 return 0;
1015         jbd_lock_bh_state(bh);
1016         if (jh->b_committed_data && ext4_test_bit(block,jh->b_committed_data)) {
1017                 ext4_clear_bit_atomic(lock, block, bh->b_data);
1018                 ret = 0;
1019         } else {
1020                 ret = 1;
1021         }
1022         jbd_unlock_bh_state(bh);
1023         return ret;
1024 }
1025
1026 /**
1027  * ext4_try_to_allocate()
1028  * @sb:                 superblock
1029  * @handle:             handle to this transaction
1030  * @group:              given allocation block group
1031  * @bitmap_bh:          bufferhead holds the block bitmap
1032  * @grp_goal:           given target block within the group
1033  * @count:              target number of blocks to allocate
1034  * @my_rsv:             reservation window
1035  *
1036  * Attempt to allocate blocks within a give range. Set the range of allocation
1037  * first, then find the first free bit(s) from the bitmap (within the range),
1038  * and at last, allocate the blocks by claiming the found free bit as allocated.
1039  *
1040  * To set the range of this allocation:
1041  *      if there is a reservation window, only try to allocate block(s) from the
1042  *      file's own reservation window;
1043  *      Otherwise, the allocation range starts from the give goal block, ends at
1044  *      the block group's last block.
1045  *
1046  * If we failed to allocate the desired block then we may end up crossing to a
1047  * new bitmap.  In that case we must release write access to the old one via
1048  * ext4_journal_release_buffer(), else we'll run out of credits.
1049  */
1050 static ext4_grpblk_t
1051 ext4_try_to_allocate(struct super_block *sb, handle_t *handle,
1052                         ext4_group_t group, struct buffer_head *bitmap_bh,
1053                         ext4_grpblk_t grp_goal, unsigned long *count,
1054                         struct ext4_reserve_window *my_rsv)
1055 {
1056         ext4_fsblk_t group_first_block;
1057         ext4_grpblk_t start, end;
1058         unsigned long num = 0;
1059
1060         /* we do allocation within the reservation window if we have a window */
1061         if (my_rsv) {
1062                 group_first_block = ext4_group_first_block_no(sb, group);
1063                 if (my_rsv->_rsv_start >= group_first_block)
1064                         start = my_rsv->_rsv_start - group_first_block;
1065                 else
1066                         /* reservation window cross group boundary */
1067                         start = 0;
1068                 end = my_rsv->_rsv_end - group_first_block + 1;
1069                 if (end > EXT4_BLOCKS_PER_GROUP(sb))
1070                         /* reservation window crosses group boundary */
1071                         end = EXT4_BLOCKS_PER_GROUP(sb);
1072                 if ((start <= grp_goal) && (grp_goal < end))
1073                         start = grp_goal;
1074                 else
1075                         grp_goal = -1;
1076         } else {
1077                 if (grp_goal > 0)
1078                         start = grp_goal;
1079                 else
1080                         start = 0;
1081                 end = EXT4_BLOCKS_PER_GROUP(sb);
1082         }
1083
1084         BUG_ON(start > EXT4_BLOCKS_PER_GROUP(sb));
1085
1086 repeat:
1087         if (grp_goal < 0 || !ext4_test_allocatable(grp_goal, bitmap_bh)) {
1088                 grp_goal = find_next_usable_block(start, bitmap_bh, end);
1089                 if (grp_goal < 0)
1090                         goto fail_access;
1091                 if (!my_rsv) {
1092                         int i;
1093
1094                         for (i = 0; i < 7 && grp_goal > start &&
1095                                         ext4_test_allocatable(grp_goal - 1,
1096                                                                 bitmap_bh);
1097                                         i++, grp_goal--)
1098                                 ;
1099                 }
1100         }
1101         start = grp_goal;
1102
1103         if (!claim_block(sb_bgl_lock(EXT4_SB(sb), group),
1104                 grp_goal, bitmap_bh)) {
1105                 /*
1106                  * The block was allocated by another thread, or it was
1107                  * allocated and then freed by another thread
1108                  */
1109                 start++;
1110                 grp_goal++;
1111                 if (start >= end)
1112                         goto fail_access;
1113                 goto repeat;
1114         }
1115         num++;
1116         grp_goal++;
1117         while (num < *count && grp_goal < end
1118                 && ext4_test_allocatable(grp_goal, bitmap_bh)
1119                 && claim_block(sb_bgl_lock(EXT4_SB(sb), group),
1120                                 grp_goal, bitmap_bh)) {
1121                 num++;
1122                 grp_goal++;
1123         }
1124         *count = num;
1125         return grp_goal - num;
1126 fail_access:
1127         *count = num;
1128         return -1;
1129 }
1130
1131 /**
1132  *      find_next_reservable_window():
1133  *              find a reservable space within the given range.
1134  *              It does not allocate the reservation window for now:
1135  *              alloc_new_reservation() will do the work later.
1136  *
1137  *      @search_head: the head of the searching list;
1138  *              This is not necessarily the list head of the whole filesystem
1139  *
1140  *              We have both head and start_block to assist the search
1141  *              for the reservable space. The list starts from head,
1142  *              but we will shift to the place where start_block is,
1143  *              then start from there, when looking for a reservable space.
1144  *
1145  *      @size: the target new reservation window size
1146  *
1147  *      @group_first_block: the first block we consider to start
1148  *                      the real search from
1149  *
1150  *      @last_block:
1151  *              the maximum block number that our goal reservable space
1152  *              could start from. This is normally the last block in this
1153  *              group. The search will end when we found the start of next
1154  *              possible reservable space is out of this boundary.
1155  *              This could handle the cross boundary reservation window
1156  *              request.
1157  *
1158  *      basically we search from the given range, rather than the whole
1159  *      reservation double linked list, (start_block, last_block)
1160  *      to find a free region that is of my size and has not
1161  *      been reserved.
1162  *
1163  */
1164 static int find_next_reservable_window(
1165                                 struct ext4_reserve_window_node *search_head,
1166                                 struct ext4_reserve_window_node *my_rsv,
1167                                 struct super_block * sb,
1168                                 ext4_fsblk_t start_block,
1169                                 ext4_fsblk_t last_block)
1170 {
1171         struct rb_node *next;
1172         struct ext4_reserve_window_node *rsv, *prev;
1173         ext4_fsblk_t cur;
1174         int size = my_rsv->rsv_goal_size;
1175
1176         /* TODO: make the start of the reservation window byte-aligned */
1177         /* cur = *start_block & ~7;*/
1178         cur = start_block;
1179         rsv = search_head;
1180         if (!rsv)
1181                 return -1;
1182
1183         while (1) {
1184                 if (cur <= rsv->rsv_end)
1185                         cur = rsv->rsv_end + 1;
1186
1187                 /* TODO?
1188                  * in the case we could not find a reservable space
1189                  * that is what is expected, during the re-search, we could
1190                  * remember what's the largest reservable space we could have
1191                  * and return that one.
1192                  *
1193                  * For now it will fail if we could not find the reservable
1194                  * space with expected-size (or more)...
1195                  */
1196                 if (cur > last_block)
1197                         return -1;              /* fail */
1198
1199                 prev = rsv;
1200                 next = rb_next(&rsv->rsv_node);
1201                 rsv = rb_entry(next,struct ext4_reserve_window_node,rsv_node);
1202
1203                 /*
1204                  * Reached the last reservation, we can just append to the
1205                  * previous one.
1206                  */
1207                 if (!next)
1208                         break;
1209
1210                 if (cur + size <= rsv->rsv_start) {
1211                         /*
1212                          * Found a reserveable space big enough.  We could
1213                          * have a reservation across the group boundary here
1214                          */
1215                         break;
1216                 }
1217         }
1218         /*
1219          * we come here either :
1220          * when we reach the end of the whole list,
1221          * and there is empty reservable space after last entry in the list.
1222          * append it to the end of the list.
1223          *
1224          * or we found one reservable space in the middle of the list,
1225          * return the reservation window that we could append to.
1226          * succeed.
1227          */
1228
1229         if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
1230                 rsv_window_remove(sb, my_rsv);
1231
1232         /*
1233          * Let's book the whole avaliable window for now.  We will check the
1234          * disk bitmap later and then, if there are free blocks then we adjust
1235          * the window size if it's larger than requested.
1236          * Otherwise, we will remove this node from the tree next time
1237          * call find_next_reservable_window.
1238          */
1239         my_rsv->rsv_start = cur;
1240         my_rsv->rsv_end = cur + size - 1;
1241         my_rsv->rsv_alloc_hit = 0;
1242
1243         if (prev != my_rsv)
1244                 ext4_rsv_window_add(sb, my_rsv);
1245
1246         return 0;
1247 }
1248
1249 /**
1250  *      alloc_new_reservation()--allocate a new reservation window
1251  *
1252  *              To make a new reservation, we search part of the filesystem
1253  *              reservation list (the list that inside the group). We try to
1254  *              allocate a new reservation window near the allocation goal,
1255  *              or the beginning of the group, if there is no goal.
1256  *
1257  *              We first find a reservable space after the goal, then from
1258  *              there, we check the bitmap for the first free block after
1259  *              it. If there is no free block until the end of group, then the
1260  *              whole group is full, we failed. Otherwise, check if the free
1261  *              block is inside the expected reservable space, if so, we
1262  *              succeed.
1263  *              If the first free block is outside the reservable space, then
1264  *              start from the first free block, we search for next available
1265  *              space, and go on.
1266  *
1267  *      on succeed, a new reservation will be found and inserted into the list
1268  *      It contains at least one free block, and it does not overlap with other
1269  *      reservation windows.
1270  *
1271  *      failed: we failed to find a reservation window in this group
1272  *
1273  *      @rsv: the reservation
1274  *
1275  *      @grp_goal: The goal (group-relative).  It is where the search for a
1276  *              free reservable space should start from.
1277  *              if we have a grp_goal(grp_goal >0 ), then start from there,
1278  *              no grp_goal(grp_goal = -1), we start from the first block
1279  *              of the group.
1280  *
1281  *      @sb: the super block
1282  *      @group: the group we are trying to allocate in
1283  *      @bitmap_bh: the block group block bitmap
1284  *
1285  */
1286 static int alloc_new_reservation(struct ext4_reserve_window_node *my_rsv,
1287                 ext4_grpblk_t grp_goal, struct super_block *sb,
1288                 ext4_group_t group, struct buffer_head *bitmap_bh)
1289 {
1290         struct ext4_reserve_window_node *search_head;
1291         ext4_fsblk_t group_first_block, group_end_block, start_block;
1292         ext4_grpblk_t first_free_block;
1293         struct rb_root *fs_rsv_root = &EXT4_SB(sb)->s_rsv_window_root;
1294         unsigned long size;
1295         int ret;
1296         spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
1297
1298         group_first_block = ext4_group_first_block_no(sb, group);
1299         group_end_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
1300
1301         if (grp_goal < 0)
1302                 start_block = group_first_block;
1303         else
1304                 start_block = grp_goal + group_first_block;
1305
1306         size = my_rsv->rsv_goal_size;
1307
1308         if (!rsv_is_empty(&my_rsv->rsv_window)) {
1309                 /*
1310                  * if the old reservation is cross group boundary
1311                  * and if the goal is inside the old reservation window,
1312                  * we will come here when we just failed to allocate from
1313                  * the first part of the window. We still have another part
1314                  * that belongs to the next group. In this case, there is no
1315                  * point to discard our window and try to allocate a new one
1316                  * in this group(which will fail). we should
1317                  * keep the reservation window, just simply move on.
1318                  *
1319                  * Maybe we could shift the start block of the reservation
1320                  * window to the first block of next group.
1321                  */
1322
1323                 if ((my_rsv->rsv_start <= group_end_block) &&
1324                                 (my_rsv->rsv_end > group_end_block) &&
1325                                 (start_block >= my_rsv->rsv_start))
1326                         return -1;
1327
1328                 if ((my_rsv->rsv_alloc_hit >
1329                      (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
1330                         /*
1331                          * if the previously allocation hit ratio is
1332                          * greater than 1/2, then we double the size of
1333                          * the reservation window the next time,
1334                          * otherwise we keep the same size window
1335                          */
1336                         size = size * 2;
1337                         if (size > EXT4_MAX_RESERVE_BLOCKS)
1338                                 size = EXT4_MAX_RESERVE_BLOCKS;
1339                         my_rsv->rsv_goal_size= size;
1340                 }
1341         }
1342
1343         spin_lock(rsv_lock);
1344         /*
1345          * shift the search start to the window near the goal block
1346          */
1347         search_head = search_reserve_window(fs_rsv_root, start_block);
1348
1349         /*
1350          * find_next_reservable_window() simply finds a reservable window
1351          * inside the given range(start_block, group_end_block).
1352          *
1353          * To make sure the reservation window has a free bit inside it, we
1354          * need to check the bitmap after we found a reservable window.
1355          */
1356 retry:
1357         ret = find_next_reservable_window(search_head, my_rsv, sb,
1358                                                 start_block, group_end_block);
1359
1360         if (ret == -1) {
1361                 if (!rsv_is_empty(&my_rsv->rsv_window))
1362                         rsv_window_remove(sb, my_rsv);
1363                 spin_unlock(rsv_lock);
1364                 return -1;
1365         }
1366
1367         /*
1368          * On success, find_next_reservable_window() returns the
1369          * reservation window where there is a reservable space after it.
1370          * Before we reserve this reservable space, we need
1371          * to make sure there is at least a free block inside this region.
1372          *
1373          * searching the first free bit on the block bitmap and copy of
1374          * last committed bitmap alternatively, until we found a allocatable
1375          * block. Search start from the start block of the reservable space
1376          * we just found.
1377          */
1378         spin_unlock(rsv_lock);
1379         first_free_block = bitmap_search_next_usable_block(
1380                         my_rsv->rsv_start - group_first_block,
1381                         bitmap_bh, group_end_block - group_first_block + 1);
1382
1383         if (first_free_block < 0) {
1384                 /*
1385                  * no free block left on the bitmap, no point
1386                  * to reserve the space. return failed.
1387                  */
1388                 spin_lock(rsv_lock);
1389                 if (!rsv_is_empty(&my_rsv->rsv_window))
1390                         rsv_window_remove(sb, my_rsv);
1391                 spin_unlock(rsv_lock);
1392                 return -1;              /* failed */
1393         }
1394
1395         start_block = first_free_block + group_first_block;
1396         /*
1397          * check if the first free block is within the
1398          * free space we just reserved
1399          */
1400         if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end)
1401                 return 0;               /* success */
1402         /*
1403          * if the first free bit we found is out of the reservable space
1404          * continue search for next reservable space,
1405          * start from where the free block is,
1406          * we also shift the list head to where we stopped last time
1407          */
1408         search_head = my_rsv;
1409         spin_lock(rsv_lock);
1410         goto retry;
1411 }
1412
1413 /**
1414  * try_to_extend_reservation()
1415  * @my_rsv:             given reservation window
1416  * @sb:                 super block
1417  * @size:               the delta to extend
1418  *
1419  * Attempt to expand the reservation window large enough to have
1420  * required number of free blocks
1421  *
1422  * Since ext4_try_to_allocate() will always allocate blocks within
1423  * the reservation window range, if the window size is too small,
1424  * multiple blocks allocation has to stop at the end of the reservation
1425  * window. To make this more efficient, given the total number of
1426  * blocks needed and the current size of the window, we try to
1427  * expand the reservation window size if necessary on a best-effort
1428  * basis before ext4_new_blocks() tries to allocate blocks,
1429  */
1430 static void try_to_extend_reservation(struct ext4_reserve_window_node *my_rsv,
1431                         struct super_block *sb, int size)
1432 {
1433         struct ext4_reserve_window_node *next_rsv;
1434         struct rb_node *next;
1435         spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
1436
1437         if (!spin_trylock(rsv_lock))
1438                 return;
1439
1440         next = rb_next(&my_rsv->rsv_node);
1441
1442         if (!next)
1443                 my_rsv->rsv_end += size;
1444         else {
1445                 next_rsv = rb_entry(next, struct ext4_reserve_window_node, rsv_node);
1446
1447                 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
1448                         my_rsv->rsv_end += size;
1449                 else
1450                         my_rsv->rsv_end = next_rsv->rsv_start - 1;
1451         }
1452         spin_unlock(rsv_lock);
1453 }
1454
1455 /**
1456  * ext4_try_to_allocate_with_rsv()
1457  * @sb:                 superblock
1458  * @handle:             handle to this transaction
1459  * @group:              given allocation block group
1460  * @bitmap_bh:          bufferhead holds the block bitmap
1461  * @grp_goal:           given target block within the group
1462  * @count:              target number of blocks to allocate
1463  * @my_rsv:             reservation window
1464  * @errp:               pointer to store the error code
1465  *
1466  * This is the main function used to allocate a new block and its reservation
1467  * window.
1468  *
1469  * Each time when a new block allocation is need, first try to allocate from
1470  * its own reservation.  If it does not have a reservation window, instead of
1471  * looking for a free bit on bitmap first, then look up the reservation list to
1472  * see if it is inside somebody else's reservation window, we try to allocate a
1473  * reservation window for it starting from the goal first. Then do the block
1474  * allocation within the reservation window.
1475  *
1476  * This will avoid keeping on searching the reservation list again and
1477  * again when somebody is looking for a free block (without
1478  * reservation), and there are lots of free blocks, but they are all
1479  * being reserved.
1480  *
1481  * We use a red-black tree for the per-filesystem reservation list.
1482  *
1483  */
1484 static ext4_grpblk_t
1485 ext4_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
1486                         ext4_group_t group, struct buffer_head *bitmap_bh,
1487                         ext4_grpblk_t grp_goal,
1488                         struct ext4_reserve_window_node * my_rsv,
1489                         unsigned long *count, int *errp)
1490 {
1491         ext4_fsblk_t group_first_block, group_last_block;
1492         ext4_grpblk_t ret = 0;
1493         int fatal;
1494         unsigned long num = *count;
1495
1496         *errp = 0;
1497
1498         /*
1499          * Make sure we use undo access for the bitmap, because it is critical
1500          * that we do the frozen_data COW on bitmap buffers in all cases even
1501          * if the buffer is in BJ_Forget state in the committing transaction.
1502          */
1503         BUFFER_TRACE(bitmap_bh, "get undo access for new block");
1504         fatal = ext4_journal_get_undo_access(handle, bitmap_bh);
1505         if (fatal) {
1506                 *errp = fatal;
1507                 return -1;
1508         }
1509
1510         /*
1511          * we don't deal with reservation when
1512          * filesystem is mounted without reservation
1513          * or the file is not a regular file
1514          * or last attempt to allocate a block with reservation turned on failed
1515          */
1516         if (my_rsv == NULL ) {
1517                 ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
1518                                                 grp_goal, count, NULL);
1519                 goto out;
1520         }
1521         /*
1522          * grp_goal is a group relative block number (if there is a goal)
1523          * 0 <= grp_goal < EXT4_BLOCKS_PER_GROUP(sb)
1524          * first block is a filesystem wide block number
1525          * first block is the block number of the first block in this group
1526          */
1527         group_first_block = ext4_group_first_block_no(sb, group);
1528         group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
1529
1530         /*
1531          * Basically we will allocate a new block from inode's reservation
1532          * window.
1533          *
1534          * We need to allocate a new reservation window, if:
1535          * a) inode does not have a reservation window; or
1536          * b) last attempt to allocate a block from existing reservation
1537          *    failed; or
1538          * c) we come here with a goal and with a reservation window
1539          *
1540          * We do not need to allocate a new reservation window if we come here
1541          * at the beginning with a goal and the goal is inside the window, or
1542          * we don't have a goal but already have a reservation window.
1543          * then we could go to allocate from the reservation window directly.
1544          */
1545         while (1) {
1546                 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
1547                         !goal_in_my_reservation(&my_rsv->rsv_window,
1548                                                 grp_goal, group, sb)) {
1549                         if (my_rsv->rsv_goal_size < *count)
1550                                 my_rsv->rsv_goal_size = *count;
1551                         ret = alloc_new_reservation(my_rsv, grp_goal, sb,
1552                                                         group, bitmap_bh);
1553                         if (ret < 0)
1554                                 break;                  /* failed */
1555
1556                         if (!goal_in_my_reservation(&my_rsv->rsv_window,
1557                                                         grp_goal, group, sb))
1558                                 grp_goal = -1;
1559                 } else if (grp_goal >= 0) {
1560                         int curr = my_rsv->rsv_end -
1561                                         (grp_goal + group_first_block) + 1;
1562
1563                         if (curr < *count)
1564                                 try_to_extend_reservation(my_rsv, sb,
1565                                                         *count - curr);
1566                 }
1567
1568                 if ((my_rsv->rsv_start > group_last_block) ||
1569                                 (my_rsv->rsv_end < group_first_block)) {
1570                         rsv_window_dump(&EXT4_SB(sb)->s_rsv_window_root, 1);
1571                         BUG();
1572                 }
1573                 ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
1574                                            grp_goal, &num, &my_rsv->rsv_window);
1575                 if (ret >= 0) {
1576                         my_rsv->rsv_alloc_hit += num;
1577                         *count = num;
1578                         break;                          /* succeed */
1579                 }
1580                 num = *count;
1581         }
1582 out:
1583         if (ret >= 0) {
1584                 BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for "
1585                                         "bitmap block");
1586                 fatal = ext4_journal_dirty_metadata(handle, bitmap_bh);
1587                 if (fatal) {
1588                         *errp = fatal;
1589                         return -1;
1590                 }
1591                 return ret;
1592         }
1593
1594         BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
1595         ext4_journal_release_buffer(handle, bitmap_bh);
1596         return ret;
1597 }
1598
1599 /**
1600  * ext4_has_free_blocks()
1601  * @sbi:                in-core super block structure.
1602  *
1603  * Check if filesystem has at least 1 free block available for allocation.
1604  */
1605 static int ext4_has_free_blocks(struct ext4_sb_info *sbi)
1606 {
1607         ext4_fsblk_t free_blocks, root_blocks;
1608
1609         free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
1610         root_blocks = ext4_r_blocks_count(sbi->s_es);
1611         if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
1612                 sbi->s_resuid != current->fsuid &&
1613                 (sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
1614                 return 0;
1615         }
1616         return 1;
1617 }
1618
1619 /**
1620  * ext4_should_retry_alloc()
1621  * @sb:                 super block
1622  * @retries             number of attemps has been made
1623  *
1624  * ext4_should_retry_alloc() is called when ENOSPC is returned, and if
1625  * it is profitable to retry the operation, this function will wait
1626  * for the current or commiting transaction to complete, and then
1627  * return TRUE.
1628  *
1629  * if the total number of retries exceed three times, return FALSE.
1630  */
1631 int ext4_should_retry_alloc(struct super_block *sb, int *retries)
1632 {
1633         if (!ext4_has_free_blocks(EXT4_SB(sb)) || (*retries)++ > 3)
1634                 return 0;
1635
1636         jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
1637
1638         return jbd2_journal_force_commit_nested(EXT4_SB(sb)->s_journal);
1639 }
1640
1641 /**
1642  * ext4_new_blocks_old() -- core block(s) allocation function
1643  * @handle:             handle to this transaction
1644  * @inode:              file inode
1645  * @goal:               given target block(filesystem wide)
1646  * @count:              target number of blocks to allocate
1647  * @errp:               error code
1648  *
1649  * ext4_new_blocks uses a goal block to assist allocation.  It tries to
1650  * allocate block(s) from the block group contains the goal block first. If that
1651  * fails, it will try to allocate block(s) from other block groups without
1652  * any specific goal block.
1653  *
1654  */
1655 ext4_fsblk_t ext4_new_blocks_old(handle_t *handle, struct inode *inode,
1656                         ext4_fsblk_t goal, unsigned long *count, int *errp)
1657 {
1658         struct buffer_head *bitmap_bh = NULL;
1659         struct buffer_head *gdp_bh;
1660         ext4_group_t group_no;
1661         ext4_group_t goal_group;
1662         ext4_grpblk_t grp_target_blk;   /* blockgroup relative goal block */
1663         ext4_grpblk_t grp_alloc_blk;    /* blockgroup-relative allocated block*/
1664         ext4_fsblk_t ret_block;         /* filesyetem-wide allocated block */
1665         ext4_group_t bgi;                       /* blockgroup iteration index */
1666         int fatal = 0, err;
1667         int performed_allocation = 0;
1668         ext4_grpblk_t free_blocks;      /* number of free blocks in a group */
1669         struct super_block *sb;
1670         struct ext4_group_desc *gdp;
1671         struct ext4_super_block *es;
1672         struct ext4_sb_info *sbi;
1673         struct ext4_reserve_window_node *my_rsv = NULL;
1674         struct ext4_block_alloc_info *block_i;
1675         unsigned short windowsz = 0;
1676         ext4_group_t ngroups;
1677         unsigned long num = *count;
1678
1679         *errp = -ENOSPC;
1680         sb = inode->i_sb;
1681         if (!sb) {
1682                 printk("ext4_new_block: nonexistent device");
1683                 return 0;
1684         }
1685
1686         /*
1687          * Check quota for allocation of this block.
1688          */
1689         if (DQUOT_ALLOC_BLOCK(inode, num)) {
1690                 *errp = -EDQUOT;
1691                 return 0;
1692         }
1693
1694         sbi = EXT4_SB(sb);
1695         es = EXT4_SB(sb)->s_es;
1696         ext4_debug("goal=%llu.\n", goal);
1697         /*
1698          * Allocate a block from reservation only when
1699          * filesystem is mounted with reservation(default,-o reservation), and
1700          * it's a regular file, and
1701          * the desired window size is greater than 0 (One could use ioctl
1702          * command EXT4_IOC_SETRSVSZ to set the window size to 0 to turn off
1703          * reservation on that particular file)
1704          */
1705         block_i = EXT4_I(inode)->i_block_alloc_info;
1706         if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
1707                 my_rsv = &block_i->rsv_window_node;
1708
1709         if (!ext4_has_free_blocks(sbi)) {
1710                 *errp = -ENOSPC;
1711                 goto out;
1712         }
1713
1714         /*
1715          * First, test whether the goal block is free.
1716          */
1717         if (goal < le32_to_cpu(es->s_first_data_block) ||
1718             goal >= ext4_blocks_count(es))
1719                 goal = le32_to_cpu(es->s_first_data_block);
1720         ext4_get_group_no_and_offset(sb, goal, &group_no, &grp_target_blk);
1721         goal_group = group_no;
1722 retry_alloc:
1723         gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
1724         if (!gdp)
1725                 goto io_error;
1726
1727         free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1728         /*
1729          * if there is not enough free blocks to make a new resevation
1730          * turn off reservation for this allocation
1731          */
1732         if (my_rsv && (free_blocks < windowsz)
1733                 && (rsv_is_empty(&my_rsv->rsv_window)))
1734                 my_rsv = NULL;
1735
1736         if (free_blocks > 0) {
1737                 bitmap_bh = read_block_bitmap(sb, group_no);
1738                 if (!bitmap_bh)
1739                         goto io_error;
1740                 grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
1741                                         group_no, bitmap_bh, grp_target_blk,
1742                                         my_rsv, &num, &fatal);
1743                 if (fatal)
1744                         goto out;
1745                 if (grp_alloc_blk >= 0)
1746                         goto allocated;
1747         }
1748
1749         ngroups = EXT4_SB(sb)->s_groups_count;
1750         smp_rmb();
1751
1752         /*
1753          * Now search the rest of the groups.  We assume that
1754          * group_no and gdp correctly point to the last group visited.
1755          */
1756         for (bgi = 0; bgi < ngroups; bgi++) {
1757                 group_no++;
1758                 if (group_no >= ngroups)
1759                         group_no = 0;
1760                 gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
1761                 if (!gdp)
1762                         goto io_error;
1763                 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1764                 /*
1765                  * skip this group if the number of
1766                  * free blocks is less than half of the reservation
1767                  * window size.
1768                  */
1769                 if (free_blocks <= (windowsz/2))
1770                         continue;
1771
1772                 brelse(bitmap_bh);
1773                 bitmap_bh = read_block_bitmap(sb, group_no);
1774                 if (!bitmap_bh)
1775                         goto io_error;
1776                 /*
1777                  * try to allocate block(s) from this group, without a goal(-1).
1778                  */
1779                 grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
1780                                         group_no, bitmap_bh, -1, my_rsv,
1781                                         &num, &fatal);
1782                 if (fatal)
1783                         goto out;
1784                 if (grp_alloc_blk >= 0)
1785                         goto allocated;
1786         }
1787         /*
1788          * We may end up a bogus ealier ENOSPC error due to
1789          * filesystem is "full" of reservations, but
1790          * there maybe indeed free blocks avaliable on disk
1791          * In this case, we just forget about the reservations
1792          * just do block allocation as without reservations.
1793          */
1794         if (my_rsv) {
1795                 my_rsv = NULL;
1796                 windowsz = 0;
1797                 group_no = goal_group;
1798                 goto retry_alloc;
1799         }
1800         /* No space left on the device */
1801         *errp = -ENOSPC;
1802         goto out;
1803
1804 allocated:
1805
1806         ext4_debug("using block group %lu(%d)\n",
1807                         group_no, gdp->bg_free_blocks_count);
1808
1809         BUFFER_TRACE(gdp_bh, "get_write_access");
1810         fatal = ext4_journal_get_write_access(handle, gdp_bh);
1811         if (fatal)
1812                 goto out;
1813
1814         ret_block = grp_alloc_blk + ext4_group_first_block_no(sb, group_no);
1815
1816         if (in_range(ext4_block_bitmap(sb, gdp), ret_block, num) ||
1817             in_range(ext4_inode_bitmap(sb, gdp), ret_block, num) ||
1818             in_range(ret_block, ext4_inode_table(sb, gdp),
1819                      EXT4_SB(sb)->s_itb_per_group) ||
1820             in_range(ret_block + num - 1, ext4_inode_table(sb, gdp),
1821                      EXT4_SB(sb)->s_itb_per_group)) {
1822                 ext4_error(sb, "ext4_new_block",
1823                             "Allocating block in system zone - "
1824                             "blocks from %llu, length %lu",
1825                              ret_block, num);
1826                 /*
1827                  * claim_block marked the blocks we allocated
1828                  * as in use. So we may want to selectively
1829                  * mark some of the blocks as free
1830                  */
1831                 goto retry_alloc;
1832         }
1833
1834         performed_allocation = 1;
1835
1836 #ifdef CONFIG_JBD2_DEBUG
1837         {
1838                 struct buffer_head *debug_bh;
1839
1840                 /* Record bitmap buffer state in the newly allocated block */
1841                 debug_bh = sb_find_get_block(sb, ret_block);
1842                 if (debug_bh) {
1843                         BUFFER_TRACE(debug_bh, "state when allocated");
1844                         BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap state");
1845                         brelse(debug_bh);
1846                 }
1847         }
1848         jbd_lock_bh_state(bitmap_bh);
1849         spin_lock(sb_bgl_lock(sbi, group_no));
1850         if (buffer_jbd(bitmap_bh) && bh2jh(bitmap_bh)->b_committed_data) {
1851                 int i;
1852
1853                 for (i = 0; i < num; i++) {
1854                         if (ext4_test_bit(grp_alloc_blk+i,
1855                                         bh2jh(bitmap_bh)->b_committed_data)) {
1856                                 printk("%s: block was unexpectedly set in "
1857                                         "b_committed_data\n", __func__);
1858                         }
1859                 }
1860         }
1861         ext4_debug("found bit %d\n", grp_alloc_blk);
1862         spin_unlock(sb_bgl_lock(sbi, group_no));
1863         jbd_unlock_bh_state(bitmap_bh);
1864 #endif
1865
1866         if (ret_block + num - 1 >= ext4_blocks_count(es)) {
1867                 ext4_error(sb, "ext4_new_block",
1868                             "block(%llu) >= blocks count(%llu) - "
1869                             "block_group = %lu, es == %p ", ret_block,
1870                         ext4_blocks_count(es), group_no, es);
1871                 goto out;
1872         }
1873
1874         /*
1875          * It is up to the caller to add the new buffer to a journal
1876          * list of some description.  We don't know in advance whether
1877          * the caller wants to use it as metadata or data.
1878          */
1879         spin_lock(sb_bgl_lock(sbi, group_no));
1880         if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
1881                 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
1882         le16_add_cpu(&gdp->bg_free_blocks_count, -num);
1883         gdp->bg_checksum = ext4_group_desc_csum(sbi, group_no, gdp);
1884         spin_unlock(sb_bgl_lock(sbi, group_no));
1885         percpu_counter_sub(&sbi->s_freeblocks_counter, num);
1886
1887         BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
1888         err = ext4_journal_dirty_metadata(handle, gdp_bh);
1889         if (!fatal)
1890                 fatal = err;
1891
1892         sb->s_dirt = 1;
1893         if (fatal)
1894                 goto out;
1895
1896         *errp = 0;
1897         brelse(bitmap_bh);
1898         DQUOT_FREE_BLOCK(inode, *count-num);
1899         *count = num;
1900         return ret_block;
1901
1902 io_error:
1903         *errp = -EIO;
1904 out:
1905         if (fatal) {
1906                 *errp = fatal;
1907                 ext4_std_error(sb, fatal);
1908         }
1909         /*
1910          * Undo the block allocation
1911          */
1912         if (!performed_allocation)
1913                 DQUOT_FREE_BLOCK(inode, *count);
1914         brelse(bitmap_bh);
1915         return 0;
1916 }
1917
1918 ext4_fsblk_t ext4_new_block(handle_t *handle, struct inode *inode,
1919                 ext4_fsblk_t goal, int *errp)
1920 {
1921         struct ext4_allocation_request ar;
1922         ext4_fsblk_t ret;
1923
1924         if (!test_opt(inode->i_sb, MBALLOC)) {
1925                 unsigned long count = 1;
1926                 ret = ext4_new_blocks_old(handle, inode, goal, &count, errp);
1927                 return ret;
1928         }
1929
1930         memset(&ar, 0, sizeof(ar));
1931         ar.inode = inode;
1932         ar.goal = goal;
1933         ar.len = 1;
1934         ret = ext4_mb_new_blocks(handle, &ar, errp);
1935         return ret;
1936 }
1937
1938 ext4_fsblk_t ext4_new_blocks(handle_t *handle, struct inode *inode,
1939                 ext4_fsblk_t goal, unsigned long *count, int *errp)
1940 {
1941         struct ext4_allocation_request ar;
1942         ext4_fsblk_t ret;
1943
1944         if (!test_opt(inode->i_sb, MBALLOC)) {
1945                 ret = ext4_new_blocks_old(handle, inode, goal, count, errp);
1946                 return ret;
1947         }
1948
1949         memset(&ar, 0, sizeof(ar));
1950         ar.inode = inode;
1951         ar.goal = goal;
1952         ar.len = *count;
1953         ret = ext4_mb_new_blocks(handle, &ar, errp);
1954         *count = ar.len;
1955         return ret;
1956 }
1957
1958
1959 /**
1960  * ext4_count_free_blocks() -- count filesystem free blocks
1961  * @sb:         superblock
1962  *
1963  * Adds up the number of free blocks from each block group.
1964  */
1965 ext4_fsblk_t ext4_count_free_blocks(struct super_block *sb)
1966 {
1967         ext4_fsblk_t desc_count;
1968         struct ext4_group_desc *gdp;
1969         ext4_group_t i;
1970         ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
1971 #ifdef EXT4FS_DEBUG
1972         struct ext4_super_block *es;
1973         ext4_fsblk_t bitmap_count;
1974         unsigned long x;
1975         struct buffer_head *bitmap_bh = NULL;
1976
1977         es = EXT4_SB(sb)->s_es;
1978         desc_count = 0;
1979         bitmap_count = 0;
1980         gdp = NULL;
1981
1982         smp_rmb();
1983         for (i = 0; i < ngroups; i++) {
1984                 gdp = ext4_get_group_desc(sb, i, NULL);
1985                 if (!gdp)
1986                         continue;
1987                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1988                 brelse(bitmap_bh);
1989                 bitmap_bh = read_block_bitmap(sb, i);
1990                 if (bitmap_bh == NULL)
1991                         continue;
1992
1993                 x = ext4_count_free(bitmap_bh, sb->s_blocksize);
1994                 printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1995                         i, le16_to_cpu(gdp->bg_free_blocks_count), x);
1996                 bitmap_count += x;
1997         }
1998         brelse(bitmap_bh);
1999         printk("ext4_count_free_blocks: stored = %llu"
2000                 ", computed = %llu, %llu\n",
2001                 ext4_free_blocks_count(es),
2002                 desc_count, bitmap_count);
2003         return bitmap_count;
2004 #else
2005         desc_count = 0;
2006         smp_rmb();
2007         for (i = 0; i < ngroups; i++) {
2008                 gdp = ext4_get_group_desc(sb, i, NULL);
2009                 if (!gdp)
2010                         continue;
2011                 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
2012         }
2013
2014         return desc_count;
2015 #endif
2016 }
2017
2018 static inline int test_root(ext4_group_t a, int b)
2019 {
2020         int num = b;
2021
2022         while (a > num)
2023                 num *= b;
2024         return num == a;
2025 }
2026
2027 static int ext4_group_sparse(ext4_group_t group)
2028 {
2029         if (group <= 1)
2030                 return 1;
2031         if (!(group & 1))
2032                 return 0;
2033         return (test_root(group, 7) || test_root(group, 5) ||
2034                 test_root(group, 3));
2035 }
2036
2037 /**
2038  *      ext4_bg_has_super - number of blocks used by the superblock in group
2039  *      @sb: superblock for filesystem
2040  *      @group: group number to check
2041  *
2042  *      Return the number of blocks used by the superblock (primary or backup)
2043  *      in this group.  Currently this will be only 0 or 1.
2044  */
2045 int ext4_bg_has_super(struct super_block *sb, ext4_group_t group)
2046 {
2047         if (EXT4_HAS_RO_COMPAT_FEATURE(sb,
2048                                 EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER) &&
2049                         !ext4_group_sparse(group))
2050                 return 0;
2051         return 1;
2052 }
2053
2054 static unsigned long ext4_bg_num_gdb_meta(struct super_block *sb,
2055                                         ext4_group_t group)
2056 {
2057         unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
2058         ext4_group_t first = metagroup * EXT4_DESC_PER_BLOCK(sb);
2059         ext4_group_t last = first + EXT4_DESC_PER_BLOCK(sb) - 1;
2060
2061         if (group == first || group == first + 1 || group == last)
2062                 return 1;
2063         return 0;
2064 }
2065
2066 static unsigned long ext4_bg_num_gdb_nometa(struct super_block *sb,
2067                                         ext4_group_t group)
2068 {
2069         return ext4_bg_has_super(sb, group) ? EXT4_SB(sb)->s_gdb_count : 0;
2070 }
2071
2072 /**
2073  *      ext4_bg_num_gdb - number of blocks used by the group table in group
2074  *      @sb: superblock for filesystem
2075  *      @group: group number to check
2076  *
2077  *      Return the number of blocks used by the group descriptor table
2078  *      (primary or backup) in this group.  In the future there may be a
2079  *      different number of descriptor blocks in each group.
2080  */
2081 unsigned long ext4_bg_num_gdb(struct super_block *sb, ext4_group_t group)
2082 {
2083         unsigned long first_meta_bg =
2084                         le32_to_cpu(EXT4_SB(sb)->s_es->s_first_meta_bg);
2085         unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
2086
2087         if (!EXT4_HAS_INCOMPAT_FEATURE(sb,EXT4_FEATURE_INCOMPAT_META_BG) ||
2088                         metagroup < first_meta_bg)
2089                 return ext4_bg_num_gdb_nometa(sb,group);
2090
2091         return ext4_bg_num_gdb_meta(sb,group);
2092
2093 }