blob: cca7fd53ad7b413a9ed7cc5714f8219718ac89ef [file] [log] [blame]
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001/*
Mingming Cao617ba132006-10-11 01:20:53 -07002 * linux/fs/ext4/balloc.c
Dave Kleikampac27a0e2006-10-11 01:20:50 -07003 *
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>
Mingming Caodab291a2006-10-11 01:21:01 -070017#include <linux/jbd2.h>
Dave Kleikampac27a0e2006-10-11 01:20:50 -070018#include <linux/quotaops.h>
19#include <linux/buffer_head.h>
Christoph Hellwig3dcf5452008-04-29 18:13:32 -040020#include "ext4.h"
21#include "ext4_jbd2.h"
Andreas Dilger717d50e2007-10-16 18:38:25 -040022#include "group.h"
Christoph Hellwig3dcf5452008-04-29 18:13:32 -040023
Dave Kleikampac27a0e2006-10-11 01:20:50 -070024/*
25 * balloc.c contains the blocks allocation and deallocation routines
26 */
27
28/*
Andrew Morton72b64b52006-10-11 01:21:18 -070029 * Calculate the block group number and offset, given a block number
30 */
31void ext4_get_group_no_and_offset(struct super_block *sb, ext4_fsblk_t blocknr,
Avantika Mathurfd2d4292008-01-28 23:58:27 -050032 ext4_group_t *blockgrpp, ext4_grpblk_t *offsetp)
Andrew Morton72b64b52006-10-11 01:21:18 -070033{
Dave Kleikamp8c55e202007-05-24 13:04:54 -040034 struct ext4_super_block *es = EXT4_SB(sb)->s_es;
Andrew Morton72b64b52006-10-11 01:21:18 -070035 ext4_grpblk_t offset;
36
Dave Kleikamp8c55e202007-05-24 13:04:54 -040037 blocknr = blocknr - le32_to_cpu(es->s_first_data_block);
Andrew Mortonf4e5bc22006-10-11 01:21:19 -070038 offset = do_div(blocknr, EXT4_BLOCKS_PER_GROUP(sb));
Andrew Morton72b64b52006-10-11 01:21:18 -070039 if (offsetp)
40 *offsetp = offset;
41 if (blockgrpp)
Dave Kleikamp8c55e202007-05-24 13:04:54 -040042 *blockgrpp = blocknr;
Andrew Morton72b64b52006-10-11 01:21:18 -070043
44}
45
Jose R. Santos0bf7e832008-06-03 14:07:29 -040046static 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;
Aneesh Kumar K.V74778272008-07-11 19:27:31 -040050 ext4_get_group_no_and_offset(sb, block, &actual_group, NULL);
Jose R. Santos0bf7e832008-06-03 14:07:29 -040051 if (actual_group == block_group)
52 return 1;
53 return 0;
54}
55
56static 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}
Andreas Dilger717d50e2007-10-16 18:38:25 -040086/* Initializes an uninitialized block bitmap if given, and returns the
87 * number of blocks free in the group. */
88unsigned ext4_init_block_bitmap(struct super_block *sb, struct buffer_head *bh,
Avantika Mathurfd2d4292008-01-28 23:58:27 -050089 ext4_group_t block_group, struct ext4_group_desc *gdp)
Andreas Dilger717d50e2007-10-16 18:38:25 -040090{
Andreas Dilger717d50e2007-10-16 18:38:25 -040091 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)) {
Harvey Harrison46e665e2008-04-17 10:38:59 -0400101 ext4_error(sb, __func__,
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500102 "Checksum bad for group %lu\n", block_group);
Andreas Dilger717d50e2007-10-16 18:38:25 -0400103 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 */
Akinobu Mita6afd6702008-07-11 19:27:31 -0400124 bit_max += ext4_bg_num_gdb(sb, block_group);
Andreas Dilger717d50e2007-10-16 18:38:25 -0400125 }
126
127 if (block_group == sbi->s_groups_count - 1) {
128 /*
129 * Even though mke2fs always initialize first and last group
130 * if some other tool enabled the EXT4_BG_BLOCK_UNINIT we need
131 * to make sure we calculate the right free blocks
132 */
133 group_blocks = ext4_blocks_count(sbi->s_es) -
134 le32_to_cpu(sbi->s_es->s_first_data_block) -
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400135 (EXT4_BLOCKS_PER_GROUP(sb) * (sbi->s_groups_count - 1));
Andreas Dilger717d50e2007-10-16 18:38:25 -0400136 } else {
137 group_blocks = EXT4_BLOCKS_PER_GROUP(sb);
138 }
139
140 free_blocks = group_blocks - bit_max;
141
142 if (bh) {
Jose R. Santos0bf7e832008-06-03 14:07:29 -0400143 ext4_fsblk_t start, tmp;
144 int flex_bg = 0;
Akinobu Mitad00a6d72008-04-17 10:38:59 -0400145
Andreas Dilger717d50e2007-10-16 18:38:25 -0400146 for (bit = 0; bit < bit_max; bit++)
147 ext4_set_bit(bit, bh->b_data);
148
Akinobu Mitad00a6d72008-04-17 10:38:59 -0400149 start = ext4_group_first_block_no(sb, block_group);
Andreas Dilger717d50e2007-10-16 18:38:25 -0400150
Jose R. Santos0bf7e832008-06-03 14:07:29 -0400151 if (EXT4_HAS_INCOMPAT_FEATURE(sb,
152 EXT4_FEATURE_INCOMPAT_FLEX_BG))
153 flex_bg = 1;
Andreas Dilger717d50e2007-10-16 18:38:25 -0400154
Jose R. Santos0bf7e832008-06-03 14:07:29 -0400155 /* Set bits for block and inode bitmaps, and inode table */
156 tmp = ext4_block_bitmap(sb, gdp);
157 if (!flex_bg || ext4_block_in_group(sb, tmp, block_group))
158 ext4_set_bit(tmp - start, bh->b_data);
159
160 tmp = ext4_inode_bitmap(sb, gdp);
161 if (!flex_bg || ext4_block_in_group(sb, tmp, block_group))
162 ext4_set_bit(tmp - start, bh->b_data);
163
164 tmp = ext4_inode_table(sb, gdp);
165 for (; tmp < ext4_inode_table(sb, gdp) +
166 sbi->s_itb_per_group; tmp++) {
167 if (!flex_bg ||
168 ext4_block_in_group(sb, tmp, block_group))
169 ext4_set_bit(tmp - start, bh->b_data);
170 }
Andreas Dilger717d50e2007-10-16 18:38:25 -0400171 /*
172 * Also if the number of blocks within the group is
173 * less than the blocksize * 8 ( which is the size
174 * of bitmap ), set rest of the block bitmap to 1
175 */
176 mark_bitmap_end(group_blocks, sb->s_blocksize * 8, bh->b_data);
177 }
Jose R. Santos0bf7e832008-06-03 14:07:29 -0400178 return free_blocks - ext4_group_used_meta_blocks(sb, block_group);
Andreas Dilger717d50e2007-10-16 18:38:25 -0400179}
180
181
Andrew Morton72b64b52006-10-11 01:21:18 -0700182/*
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700183 * The free blocks are managed by bitmaps. A file system contains several
184 * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
185 * block for inodes, N blocks for the inode table and data blocks.
186 *
187 * The file system contains group descriptors which are located after the
188 * super block. Each descriptor contains the number of the bitmap block and
189 * the free blocks count in the block. The descriptors are loaded in memory
Aneesh Kumar K.Ve6274322007-02-20 13:57:58 -0800190 * when a file system is mounted (see ext4_fill_super).
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700191 */
192
193
194#define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
195
196/**
Mingming Cao617ba132006-10-11 01:20:53 -0700197 * ext4_get_group_desc() -- load group descriptor from disk
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700198 * @sb: super block
199 * @block_group: given block group
200 * @bh: pointer to the buffer head to store the block
201 * group descriptor
202 */
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400203struct ext4_group_desc * ext4_get_group_desc(struct super_block *sb,
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500204 ext4_group_t block_group,
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400205 struct buffer_head **bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700206{
207 unsigned long group_desc;
208 unsigned long offset;
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400209 struct ext4_group_desc *desc;
Mingming Cao617ba132006-10-11 01:20:53 -0700210 struct ext4_sb_info *sbi = EXT4_SB(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700211
212 if (block_group >= sbi->s_groups_count) {
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400213 ext4_error(sb, "ext4_get_group_desc",
214 "block_group >= groups_count - "
215 "block_group = %lu, groups_count = %lu",
216 block_group, sbi->s_groups_count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700217
218 return NULL;
219 }
220 smp_rmb();
221
Mingming Cao617ba132006-10-11 01:20:53 -0700222 group_desc = block_group >> EXT4_DESC_PER_BLOCK_BITS(sb);
223 offset = block_group & (EXT4_DESC_PER_BLOCK(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700224 if (!sbi->s_group_desc[group_desc]) {
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400225 ext4_error(sb, "ext4_get_group_desc",
226 "Group descriptor not loaded - "
227 "block_group = %lu, group_desc = %lu, desc = %lu",
228 block_group, group_desc, offset);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700229 return NULL;
230 }
231
Alexandre Ratchov0d1ee422006-10-11 01:21:14 -0700232 desc = (struct ext4_group_desc *)(
233 (__u8 *)sbi->s_group_desc[group_desc]->b_data +
234 offset * EXT4_DESC_SIZE(sb));
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700235 if (bh)
236 *bh = sbi->s_group_desc[group_desc];
Alexandre Ratchov0d1ee422006-10-11 01:21:14 -0700237 return desc;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700238}
239
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500240static int ext4_valid_block_bitmap(struct super_block *sb,
241 struct ext4_group_desc *desc,
242 unsigned int block_group,
243 struct buffer_head *bh)
244{
245 ext4_grpblk_t offset;
246 ext4_grpblk_t next_zero_bit;
247 ext4_fsblk_t bitmap_blk;
248 ext4_fsblk_t group_first_block;
249
250 if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FLEX_BG)) {
251 /* with FLEX_BG, the inode/block bitmaps and itable
252 * blocks may not be in the group at all
253 * so the bitmap validation will be skipped for those groups
254 * or it has to also read the block group where the bitmaps
255 * are located to verify they are set.
256 */
257 return 1;
258 }
259 group_first_block = ext4_group_first_block_no(sb, block_group);
260
261 /* check whether block bitmap block number is set */
262 bitmap_blk = ext4_block_bitmap(sb, desc);
263 offset = bitmap_blk - group_first_block;
264 if (!ext4_test_bit(offset, bh->b_data))
265 /* bad block bitmap */
266 goto err_out;
267
268 /* check whether the inode bitmap block number is set */
269 bitmap_blk = ext4_inode_bitmap(sb, desc);
270 offset = bitmap_blk - group_first_block;
271 if (!ext4_test_bit(offset, bh->b_data))
272 /* bad block bitmap */
273 goto err_out;
274
275 /* check whether the inode table block number is set */
276 bitmap_blk = ext4_inode_table(sb, desc);
277 offset = bitmap_blk - group_first_block;
278 next_zero_bit = ext4_find_next_zero_bit(bh->b_data,
279 offset + EXT4_SB(sb)->s_itb_per_group,
280 offset);
281 if (next_zero_bit >= offset + EXT4_SB(sb)->s_itb_per_group)
282 /* good bitmap for inode tables */
283 return 1;
284
285err_out:
Harvey Harrison46e665e2008-04-17 10:38:59 -0400286 ext4_error(sb, __func__,
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500287 "Invalid block bitmap - "
288 "block_group = %d, block = %llu",
289 block_group, bitmap_blk);
290 return 0;
291}
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700292/**
Theodore Ts'o574ca172008-07-11 19:27:31 -0400293 * ext4_read_block_bitmap()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700294 * @sb: super block
295 * @block_group: given block group
296 *
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500297 * Read the bitmap for a given block_group,and validate the
298 * bits for block/inode/inode tables are set in the bitmaps
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700299 *
300 * Return buffer_head on success or NULL in case of failure.
301 */
Andreas Dilger717d50e2007-10-16 18:38:25 -0400302struct buffer_head *
Theodore Ts'o574ca172008-07-11 19:27:31 -0400303ext4_read_block_bitmap(struct super_block *sb, ext4_group_t block_group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700304{
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400305 struct ext4_group_desc *desc;
306 struct buffer_head *bh = NULL;
Aneesh Kumar K.V7c9e69f2007-10-16 23:27:02 -0700307 ext4_fsblk_t bitmap_blk;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700308
Andreas Dilger717d50e2007-10-16 18:38:25 -0400309 desc = ext4_get_group_desc(sb, block_group, NULL);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700310 if (!desc)
Aneesh Kumar K.V7c9e69f2007-10-16 23:27:02 -0700311 return NULL;
312 bitmap_blk = ext4_block_bitmap(sb, desc);
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500313 bh = sb_getblk(sb, bitmap_blk);
314 if (unlikely(!bh)) {
Harvey Harrison46e665e2008-04-17 10:38:59 -0400315 ext4_error(sb, __func__,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700316 "Cannot read block bitmap - "
Eric Sandeene29d1cd2008-08-02 21:21:02 -0400317 "block_group = %lu, block_bitmap = %llu",
318 block_group, bitmap_blk);
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500319 return NULL;
320 }
321 if (bh_uptodate_or_lock(bh))
322 return bh;
323
Eric Sandeenb5f10ee2008-08-02 21:21:08 -0400324 spin_lock(sb_bgl_lock(EXT4_SB(sb), block_group));
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500325 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
326 ext4_init_block_bitmap(sb, bh, block_group, desc);
327 set_buffer_uptodate(bh);
328 unlock_buffer(bh);
Eric Sandeenb5f10ee2008-08-02 21:21:08 -0400329 spin_unlock(sb_bgl_lock(EXT4_SB(sb), block_group));
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500330 return bh;
331 }
Eric Sandeenb5f10ee2008-08-02 21:21:08 -0400332 spin_unlock(sb_bgl_lock(EXT4_SB(sb), block_group));
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500333 if (bh_submit_read(bh) < 0) {
334 put_bh(bh);
Harvey Harrison46e665e2008-04-17 10:38:59 -0400335 ext4_error(sb, __func__,
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500336 "Cannot read block bitmap - "
Eric Sandeene29d1cd2008-08-02 21:21:02 -0400337 "block_group = %lu, block_bitmap = %llu",
338 block_group, bitmap_blk);
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500339 return NULL;
340 }
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -0400341 ext4_valid_block_bitmap(sb, desc, block_group, bh);
342 /*
343 * file system mounted not to panic on error,
344 * continue with corrupt bitmap
345 */
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700346 return bh;
347}
348/*
349 * The reservation window structure operations
350 * --------------------------------------------
351 * Operations include:
352 * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
353 *
354 * We use a red-black tree to represent per-filesystem reservation
355 * windows.
356 *
357 */
358
359/**
360 * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
361 * @rb_root: root of per-filesystem reservation rb tree
362 * @verbose: verbose mode
363 * @fn: function which wishes to dump the reservation map
364 *
365 * If verbose is turned on, it will print the whole block reservation
366 * windows(start, end). Otherwise, it will only print out the "bad" windows,
367 * those windows that overlap with their immediate neighbors.
368 */
369#if 1
370static void __rsv_window_dump(struct rb_root *root, int verbose,
371 const char *fn)
372{
373 struct rb_node *n;
Mingming Cao617ba132006-10-11 01:20:53 -0700374 struct ext4_reserve_window_node *rsv, *prev;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700375 int bad;
376
377restart:
378 n = rb_first(root);
379 bad = 0;
380 prev = NULL;
381
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400382 printk(KERN_DEBUG "Block Allocation Reservation "
383 "Windows Map (%s):\n", fn);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700384 while (n) {
Hugh Dickinsb78a6572006-12-06 20:39:21 -0800385 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700386 if (verbose)
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400387 printk(KERN_DEBUG "reservation window 0x%p "
Mingming Cao2ae02102006-10-11 01:21:11 -0700388 "start: %llu, end: %llu\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700389 rsv, rsv->rsv_start, rsv->rsv_end);
390 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400391 printk(KERN_DEBUG "Bad reservation %p (start >= end)\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700392 rsv);
393 bad = 1;
394 }
395 if (prev && prev->rsv_end >= rsv->rsv_start) {
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400396 printk(KERN_DEBUG "Bad reservation %p "
397 "(prev->end >= start)\n", rsv);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700398 bad = 1;
399 }
400 if (bad) {
401 if (!verbose) {
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400402 printk(KERN_DEBUG "Restarting reservation "
403 "walk in verbose mode\n");
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700404 verbose = 1;
405 goto restart;
406 }
407 }
408 n = rb_next(n);
409 prev = rsv;
410 }
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400411 printk(KERN_DEBUG "Window map complete.\n");
Julia Lawall07d45f12008-07-11 19:27:31 -0400412 BUG_ON(bad);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700413}
414#define rsv_window_dump(root, verbose) \
Harvey Harrison46e665e2008-04-17 10:38:59 -0400415 __rsv_window_dump((root), (verbose), __func__)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700416#else
417#define rsv_window_dump(root, verbose) do {} while (0)
418#endif
419
420/**
421 * goal_in_my_reservation()
422 * @rsv: inode's reservation window
423 * @grp_goal: given goal block relative to the allocation block group
424 * @group: the current allocation block group
425 * @sb: filesystem super block
426 *
427 * Test if the given goal block (group relative) is within the file's
428 * own block reservation window range.
429 *
430 * If the reservation window is outside the goal allocation group, return 0;
431 * grp_goal (given goal block) could be -1, which means no specific
432 * goal block. In this case, always return 1.
433 * If the goal block is within the reservation window, return 1;
434 * otherwise, return 0;
435 */
436static int
Mingming Cao617ba132006-10-11 01:20:53 -0700437goal_in_my_reservation(struct ext4_reserve_window *rsv, ext4_grpblk_t grp_goal,
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500438 ext4_group_t group, struct super_block *sb)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700439{
Mingming Cao617ba132006-10-11 01:20:53 -0700440 ext4_fsblk_t group_first_block, group_last_block;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700441
Mingming Cao617ba132006-10-11 01:20:53 -0700442 group_first_block = ext4_group_first_block_no(sb, group);
443 group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700444
445 if ((rsv->_rsv_start > group_last_block) ||
446 (rsv->_rsv_end < group_first_block))
447 return 0;
448 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
449 || (grp_goal + group_first_block > rsv->_rsv_end)))
450 return 0;
451 return 1;
452}
453
454/**
455 * search_reserve_window()
456 * @rb_root: root of reservation tree
457 * @goal: target allocation block
458 *
459 * Find the reserved window which includes the goal, or the previous one
460 * if the goal is not in any window.
461 * Returns NULL if there are no windows or if all windows start after the goal.
462 */
Mingming Cao617ba132006-10-11 01:20:53 -0700463static struct ext4_reserve_window_node *
464search_reserve_window(struct rb_root *root, ext4_fsblk_t goal)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700465{
466 struct rb_node *n = root->rb_node;
Mingming Cao617ba132006-10-11 01:20:53 -0700467 struct ext4_reserve_window_node *rsv;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700468
469 if (!n)
470 return NULL;
471
472 do {
Mingming Cao617ba132006-10-11 01:20:53 -0700473 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700474
475 if (goal < rsv->rsv_start)
476 n = n->rb_left;
477 else if (goal > rsv->rsv_end)
478 n = n->rb_right;
479 else
480 return rsv;
481 } while (n);
482 /*
483 * We've fallen off the end of the tree: the goal wasn't inside
484 * any particular node. OK, the previous node must be to one
485 * side of the interval containing the goal. If it's the RHS,
486 * we need to back up one.
487 */
488 if (rsv->rsv_start > goal) {
489 n = rb_prev(&rsv->rsv_node);
Mingming Cao617ba132006-10-11 01:20:53 -0700490 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700491 }
492 return rsv;
493}
494
495/**
Mingming Cao617ba132006-10-11 01:20:53 -0700496 * ext4_rsv_window_add() -- Insert a window to the block reservation rb tree.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700497 * @sb: super block
498 * @rsv: reservation window to add
499 *
500 * Must be called with rsv_lock hold.
501 */
Mingming Cao617ba132006-10-11 01:20:53 -0700502void ext4_rsv_window_add(struct super_block *sb,
503 struct ext4_reserve_window_node *rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700504{
Mingming Cao617ba132006-10-11 01:20:53 -0700505 struct rb_root *root = &EXT4_SB(sb)->s_rsv_window_root;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700506 struct rb_node *node = &rsv->rsv_node;
Mingming Cao617ba132006-10-11 01:20:53 -0700507 ext4_fsblk_t start = rsv->rsv_start;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700508
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400509 struct rb_node **p = &root->rb_node;
510 struct rb_node *parent = NULL;
Mingming Cao617ba132006-10-11 01:20:53 -0700511 struct ext4_reserve_window_node *this;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700512
513 while (*p)
514 {
515 parent = *p;
Mingming Cao617ba132006-10-11 01:20:53 -0700516 this = rb_entry(parent, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700517
518 if (start < this->rsv_start)
519 p = &(*p)->rb_left;
520 else if (start > this->rsv_end)
521 p = &(*p)->rb_right;
522 else {
523 rsv_window_dump(root, 1);
524 BUG();
525 }
526 }
527
528 rb_link_node(node, parent, p);
529 rb_insert_color(node, root);
530}
531
532/**
Mingming Cao617ba132006-10-11 01:20:53 -0700533 * ext4_rsv_window_remove() -- unlink a window from the reservation rb tree
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700534 * @sb: super block
535 * @rsv: reservation window to remove
536 *
537 * Mark the block reservation window as not allocated, and unlink it
538 * from the filesystem reservation window rb tree. Must be called with
539 * rsv_lock hold.
540 */
541static void rsv_window_remove(struct super_block *sb,
Mingming Cao617ba132006-10-11 01:20:53 -0700542 struct ext4_reserve_window_node *rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700543{
Mingming Cao617ba132006-10-11 01:20:53 -0700544 rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
545 rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700546 rsv->rsv_alloc_hit = 0;
Mingming Cao617ba132006-10-11 01:20:53 -0700547 rb_erase(&rsv->rsv_node, &EXT4_SB(sb)->s_rsv_window_root);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700548}
549
550/*
551 * rsv_is_empty() -- Check if the reservation window is allocated.
552 * @rsv: given reservation window to check
553 *
Mingming Cao617ba132006-10-11 01:20:53 -0700554 * returns 1 if the end block is EXT4_RESERVE_WINDOW_NOT_ALLOCATED.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700555 */
Mingming Cao617ba132006-10-11 01:20:53 -0700556static inline int rsv_is_empty(struct ext4_reserve_window *rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700557{
558 /* a valid reservation end block could not be 0 */
Mingming Cao617ba132006-10-11 01:20:53 -0700559 return rsv->_rsv_end == EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700560}
561
562/**
Mingming Cao617ba132006-10-11 01:20:53 -0700563 * ext4_init_block_alloc_info()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700564 * @inode: file inode structure
565 *
566 * Allocate and initialize the reservation window structure, and
Mingming Cao617ba132006-10-11 01:20:53 -0700567 * link the window to the ext4 inode structure at last
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700568 *
569 * The reservation window structure is only dynamically allocated
Mingming Cao617ba132006-10-11 01:20:53 -0700570 * and linked to ext4 inode the first time the open file
571 * needs a new block. So, before every ext4_new_block(s) call, for
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700572 * regular files, we should check whether the reservation window
573 * structure exists or not. In the latter case, this function is called.
574 * Fail to do so will result in block reservation being turned off for that
575 * open file.
576 *
Mingming Cao617ba132006-10-11 01:20:53 -0700577 * This function is called from ext4_get_blocks_handle(), also called
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700578 * when setting the reservation window size through ioctl before the file
579 * is open for write (needs block allocation).
580 *
Aneesh Kumar K.V0e855ac2008-01-28 23:58:26 -0500581 * Needs down_write(i_data_sem) protection prior to call this function.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700582 */
Mingming Cao617ba132006-10-11 01:20:53 -0700583void ext4_init_block_alloc_info(struct inode *inode)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700584{
Mingming Cao617ba132006-10-11 01:20:53 -0700585 struct ext4_inode_info *ei = EXT4_I(inode);
586 struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700587 struct super_block *sb = inode->i_sb;
588
589 block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
590 if (block_i) {
Mingming Cao617ba132006-10-11 01:20:53 -0700591 struct ext4_reserve_window_node *rsv = &block_i->rsv_window_node;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700592
Mingming Cao617ba132006-10-11 01:20:53 -0700593 rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
594 rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700595
596 /*
597 * if filesystem is mounted with NORESERVATION, the goal
598 * reservation window size is set to zero to indicate
599 * block reservation is off
600 */
601 if (!test_opt(sb, RESERVATION))
602 rsv->rsv_goal_size = 0;
603 else
Mingming Cao617ba132006-10-11 01:20:53 -0700604 rsv->rsv_goal_size = EXT4_DEFAULT_RESERVE_BLOCKS;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700605 rsv->rsv_alloc_hit = 0;
606 block_i->last_alloc_logical_block = 0;
607 block_i->last_alloc_physical_block = 0;
608 }
609 ei->i_block_alloc_info = block_i;
610}
611
612/**
Mingming Cao617ba132006-10-11 01:20:53 -0700613 * ext4_discard_reservation()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700614 * @inode: inode
615 *
616 * Discard(free) block reservation window on last file close, or truncate
617 * or at last iput().
618 *
619 * It is being called in three cases:
Mingming Cao617ba132006-10-11 01:20:53 -0700620 * ext4_release_file(): last writer close the file
621 * ext4_clear_inode(): last iput(), when nobody link to this file.
622 * ext4_truncate(): when the block indirect map is about to change.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700623 *
624 */
Mingming Cao617ba132006-10-11 01:20:53 -0700625void ext4_discard_reservation(struct inode *inode)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700626{
Mingming Cao617ba132006-10-11 01:20:53 -0700627 struct ext4_inode_info *ei = EXT4_I(inode);
628 struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
629 struct ext4_reserve_window_node *rsv;
630 spinlock_t *rsv_lock = &EXT4_SB(inode->i_sb)->s_rsv_window_lock;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700631
Alex Tomasc9de5602008-01-29 00:19:52 -0500632 ext4_mb_discard_inode_preallocations(inode);
633
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700634 if (!block_i)
635 return;
636
637 rsv = &block_i->rsv_window_node;
638 if (!rsv_is_empty(&rsv->rsv_window)) {
639 spin_lock(rsv_lock);
640 if (!rsv_is_empty(&rsv->rsv_window))
641 rsv_window_remove(inode->i_sb, rsv);
642 spin_unlock(rsv_lock);
643 }
644}
645
646/**
Mingming Cao617ba132006-10-11 01:20:53 -0700647 * ext4_free_blocks_sb() -- Free given blocks and update quota
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700648 * @handle: handle to this transaction
649 * @sb: super block
650 * @block: start physcial block to free
651 * @count: number of blocks to free
652 * @pdquot_freed_blocks: pointer to quota
653 */
Mingming Cao617ba132006-10-11 01:20:53 -0700654void ext4_free_blocks_sb(handle_t *handle, struct super_block *sb,
655 ext4_fsblk_t block, unsigned long count,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700656 unsigned long *pdquot_freed_blocks)
657{
658 struct buffer_head *bitmap_bh = NULL;
659 struct buffer_head *gd_bh;
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500660 ext4_group_t block_group;
Mingming Cao617ba132006-10-11 01:20:53 -0700661 ext4_grpblk_t bit;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700662 unsigned long i;
663 unsigned long overflow;
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400664 struct ext4_group_desc *desc;
665 struct ext4_super_block *es;
Mingming Cao617ba132006-10-11 01:20:53 -0700666 struct ext4_sb_info *sbi;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700667 int err = 0, ret;
Mingming Cao617ba132006-10-11 01:20:53 -0700668 ext4_grpblk_t group_freed;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700669
670 *pdquot_freed_blocks = 0;
Mingming Cao617ba132006-10-11 01:20:53 -0700671 sbi = EXT4_SB(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700672 es = sbi->s_es;
673 if (block < le32_to_cpu(es->s_first_data_block) ||
674 block + count < block ||
Laurent Vivierbd81d8e2006-10-11 01:21:10 -0700675 block + count > ext4_blocks_count(es)) {
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400676 ext4_error(sb, "ext4_free_blocks",
677 "Freeing blocks not in datazone - "
678 "block = %llu, count = %lu", block, count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700679 goto error_return;
680 }
681
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400682 ext4_debug("freeing block(s) %llu-%llu\n", block, block + count - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700683
684do_more:
685 overflow = 0;
Mingming Cao3a5b2ec2006-10-11 01:21:05 -0700686 ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700687 /*
688 * Check to see if we are freeing blocks across a group
689 * boundary.
690 */
Mingming Cao617ba132006-10-11 01:20:53 -0700691 if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
692 overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700693 count -= overflow;
694 }
695 brelse(bitmap_bh);
Theodore Ts'o574ca172008-07-11 19:27:31 -0400696 bitmap_bh = ext4_read_block_bitmap(sb, block_group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700697 if (!bitmap_bh)
698 goto error_return;
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400699 desc = ext4_get_group_desc(sb, block_group, &gd_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700700 if (!desc)
701 goto error_return;
702
Alexandre Ratchov8fadc142006-10-11 01:21:15 -0700703 if (in_range(ext4_block_bitmap(sb, desc), block, count) ||
704 in_range(ext4_inode_bitmap(sb, desc), block, count) ||
705 in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||
706 in_range(block + count - 1, ext4_inode_table(sb, desc),
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -0500707 sbi->s_itb_per_group)) {
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400708 ext4_error(sb, "ext4_free_blocks",
709 "Freeing blocks in system zones - "
710 "Block = %llu, count = %lu",
711 block, count);
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -0500712 goto error_return;
713 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700714
715 /*
716 * We are about to start releasing blocks in the bitmap,
717 * so we need undo access.
718 */
719 /* @@@ check errors */
720 BUFFER_TRACE(bitmap_bh, "getting undo access");
Mingming Cao617ba132006-10-11 01:20:53 -0700721 err = ext4_journal_get_undo_access(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700722 if (err)
723 goto error_return;
724
725 /*
726 * We are about to modify some metadata. Call the journal APIs
727 * to unshare ->b_data if a currently-committing transaction is
728 * using it
729 */
730 BUFFER_TRACE(gd_bh, "get_write_access");
Mingming Cao617ba132006-10-11 01:20:53 -0700731 err = ext4_journal_get_write_access(handle, gd_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700732 if (err)
733 goto error_return;
734
735 jbd_lock_bh_state(bitmap_bh);
736
737 for (i = 0, group_freed = 0; i < count; i++) {
738 /*
739 * An HJ special. This is expensive...
740 */
Jose R. Santose23291b2007-07-18 08:57:06 -0400741#ifdef CONFIG_JBD2_DEBUG
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700742 jbd_unlock_bh_state(bitmap_bh);
743 {
744 struct buffer_head *debug_bh;
745 debug_bh = sb_find_get_block(sb, block + i);
746 if (debug_bh) {
747 BUFFER_TRACE(debug_bh, "Deleted!");
748 if (!bh2jh(bitmap_bh)->b_committed_data)
749 BUFFER_TRACE(debug_bh,
750 "No commited data in bitmap");
751 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
752 __brelse(debug_bh);
753 }
754 }
755 jbd_lock_bh_state(bitmap_bh);
756#endif
757 if (need_resched()) {
758 jbd_unlock_bh_state(bitmap_bh);
759 cond_resched();
760 jbd_lock_bh_state(bitmap_bh);
761 }
762 /* @@@ This prevents newly-allocated data from being
763 * freed and then reallocated within the same
764 * transaction.
765 *
766 * Ideally we would want to allow that to happen, but to
Mingming Caodab291a2006-10-11 01:21:01 -0700767 * do so requires making jbd2_journal_forget() capable of
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700768 * revoking the queued write of a data block, which
769 * implies blocking on the journal lock. *forget()
770 * cannot block due to truncate races.
771 *
Mingming Caodab291a2006-10-11 01:21:01 -0700772 * Eventually we can fix this by making jbd2_journal_forget()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700773 * return a status indicating whether or not it was able
774 * to revoke the buffer. On successful revoke, it is
775 * safe not to set the allocation bit in the committed
776 * bitmap, because we know that there is no outstanding
777 * activity on the buffer any more and so it is safe to
778 * reallocate it.
779 */
780 BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
781 J_ASSERT_BH(bitmap_bh,
782 bh2jh(bitmap_bh)->b_committed_data != NULL);
Mingming Cao617ba132006-10-11 01:20:53 -0700783 ext4_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700784 bh2jh(bitmap_bh)->b_committed_data);
785
786 /*
787 * We clear the bit in the bitmap after setting the committed
788 * data bit, because this is the reverse order to that which
789 * the allocator uses.
790 */
791 BUFFER_TRACE(bitmap_bh, "clear bit");
Mingming Cao617ba132006-10-11 01:20:53 -0700792 if (!ext4_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700793 bit + i, bitmap_bh->b_data)) {
794 jbd_unlock_bh_state(bitmap_bh);
Harvey Harrison46e665e2008-04-17 10:38:59 -0400795 ext4_error(sb, __func__,
Mingming Cao2ae02102006-10-11 01:21:11 -0700796 "bit already cleared for block %llu",
Laurent Vivierbd81d8e2006-10-11 01:21:10 -0700797 (ext4_fsblk_t)(block + i));
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700798 jbd_lock_bh_state(bitmap_bh);
799 BUFFER_TRACE(bitmap_bh, "bit already cleared");
800 } else {
801 group_freed++;
802 }
803 }
804 jbd_unlock_bh_state(bitmap_bh);
805
806 spin_lock(sb_bgl_lock(sbi, block_group));
Marcin Slusarze8546d02008-04-17 10:38:59 -0400807 le16_add_cpu(&desc->bg_free_blocks_count, group_freed);
Andreas Dilger717d50e2007-10-16 18:38:25 -0400808 desc->bg_checksum = ext4_group_desc_csum(sbi, block_group, desc);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700809 spin_unlock(sb_bgl_lock(sbi, block_group));
Peter Zijlstraaa0dff22007-10-16 23:25:42 -0700810 percpu_counter_add(&sbi->s_freeblocks_counter, count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700811
Jose R. Santos772cb7c2008-07-11 19:27:31 -0400812 if (sbi->s_log_groups_per_flex) {
813 ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
814 spin_lock(sb_bgl_lock(sbi, flex_group));
815 sbi->s_flex_groups[flex_group].free_blocks += count;
816 spin_unlock(sb_bgl_lock(sbi, flex_group));
817 }
818
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700819 /* We dirtied the bitmap block */
820 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
Mingming Cao617ba132006-10-11 01:20:53 -0700821 err = ext4_journal_dirty_metadata(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700822
823 /* And the group descriptor block */
824 BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
Mingming Cao617ba132006-10-11 01:20:53 -0700825 ret = ext4_journal_dirty_metadata(handle, gd_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700826 if (!err) err = ret;
827 *pdquot_freed_blocks += group_freed;
828
829 if (overflow && !err) {
830 block += count;
831 count = overflow;
832 goto do_more;
833 }
834 sb->s_dirt = 1;
835error_return:
836 brelse(bitmap_bh);
Mingming Cao617ba132006-10-11 01:20:53 -0700837 ext4_std_error(sb, err);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700838 return;
839}
840
841/**
Mingming Cao617ba132006-10-11 01:20:53 -0700842 * ext4_free_blocks() -- Free given blocks and update quota
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700843 * @handle: handle for this transaction
844 * @inode: inode
845 * @block: start physical block to free
846 * @count: number of blocks to count
Alex Tomasc9de5602008-01-29 00:19:52 -0500847 * @metadata: Are these metadata blocks
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700848 */
Mingming Cao617ba132006-10-11 01:20:53 -0700849void ext4_free_blocks(handle_t *handle, struct inode *inode,
Alex Tomasc9de5602008-01-29 00:19:52 -0500850 ext4_fsblk_t block, unsigned long count,
851 int metadata)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700852{
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400853 struct super_block *sb;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700854 unsigned long dquot_freed_blocks;
855
Alex Tomasc9de5602008-01-29 00:19:52 -0500856 /* this isn't the right place to decide whether block is metadata
857 * inode.c/extents.c knows better, but for safety ... */
858 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
859 ext4_should_journal_data(inode))
860 metadata = 1;
861
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700862 sb = inode->i_sb;
Alex Tomasc9de5602008-01-29 00:19:52 -0500863
864 if (!test_opt(sb, MBALLOC) || !EXT4_SB(sb)->s_group_info)
865 ext4_free_blocks_sb(handle, sb, block, count,
866 &dquot_freed_blocks);
867 else
868 ext4_mb_free_blocks(handle, inode, block, count,
869 metadata, &dquot_freed_blocks);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700870 if (dquot_freed_blocks)
871 DQUOT_FREE_BLOCK(inode, dquot_freed_blocks);
872 return;
873}
874
875/**
Mingming Cao617ba132006-10-11 01:20:53 -0700876 * ext4_test_allocatable()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700877 * @nr: given allocation block group
878 * @bh: bufferhead contains the bitmap of the given block group
879 *
Mingming Cao617ba132006-10-11 01:20:53 -0700880 * For ext4 allocations, we must not reuse any blocks which are
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700881 * allocated in the bitmap buffer's "last committed data" copy. This
882 * prevents deletes from freeing up the page for reuse until we have
883 * committed the delete transaction.
884 *
885 * If we didn't do this, then deleting something and reallocating it as
886 * data would allow the old block to be overwritten before the
887 * transaction committed (because we force data to disk before commit).
888 * This would lead to corruption if we crashed between overwriting the
889 * data and committing the delete.
890 *
891 * @@@ We may want to make this allocation behaviour conditional on
892 * data-writes at some point, and disable it for metadata allocations or
893 * sync-data inodes.
894 */
Mingming Cao617ba132006-10-11 01:20:53 -0700895static int ext4_test_allocatable(ext4_grpblk_t nr, struct buffer_head *bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700896{
897 int ret;
898 struct journal_head *jh = bh2jh(bh);
899
Mingming Cao617ba132006-10-11 01:20:53 -0700900 if (ext4_test_bit(nr, bh->b_data))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700901 return 0;
902
903 jbd_lock_bh_state(bh);
904 if (!jh->b_committed_data)
905 ret = 1;
906 else
Mingming Cao617ba132006-10-11 01:20:53 -0700907 ret = !ext4_test_bit(nr, jh->b_committed_data);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700908 jbd_unlock_bh_state(bh);
909 return ret;
910}
911
912/**
913 * bitmap_search_next_usable_block()
914 * @start: the starting block (group relative) of the search
915 * @bh: bufferhead contains the block group bitmap
916 * @maxblocks: the ending block (group relative) of the reservation
917 *
918 * The bitmap search --- search forward alternately through the actual
919 * bitmap on disk and the last-committed copy in journal, until we find a
920 * bit free in both bitmaps.
921 */
Mingming Cao617ba132006-10-11 01:20:53 -0700922static ext4_grpblk_t
923bitmap_search_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
924 ext4_grpblk_t maxblocks)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700925{
Mingming Cao617ba132006-10-11 01:20:53 -0700926 ext4_grpblk_t next;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700927 struct journal_head *jh = bh2jh(bh);
928
929 while (start < maxblocks) {
Mingming Cao617ba132006-10-11 01:20:53 -0700930 next = ext4_find_next_zero_bit(bh->b_data, maxblocks, start);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700931 if (next >= maxblocks)
932 return -1;
Mingming Cao617ba132006-10-11 01:20:53 -0700933 if (ext4_test_allocatable(next, bh))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700934 return next;
935 jbd_lock_bh_state(bh);
936 if (jh->b_committed_data)
Mingming Cao617ba132006-10-11 01:20:53 -0700937 start = ext4_find_next_zero_bit(jh->b_committed_data,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700938 maxblocks, next);
939 jbd_unlock_bh_state(bh);
940 }
941 return -1;
942}
943
944/**
945 * find_next_usable_block()
946 * @start: the starting block (group relative) to find next
947 * allocatable block in bitmap.
948 * @bh: bufferhead contains the block group bitmap
949 * @maxblocks: the ending block (group relative) for the search
950 *
951 * Find an allocatable block in a bitmap. We honor both the bitmap and
952 * its last-committed copy (if that exists), and perform the "most
953 * appropriate allocation" algorithm of looking for a free block near
954 * the initial goal; then for a free byte somewhere in the bitmap; then
955 * for any free bit in the bitmap.
956 */
Mingming Cao617ba132006-10-11 01:20:53 -0700957static ext4_grpblk_t
958find_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
959 ext4_grpblk_t maxblocks)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700960{
Mingming Cao617ba132006-10-11 01:20:53 -0700961 ext4_grpblk_t here, next;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700962 char *p, *r;
963
964 if (start > 0) {
965 /*
966 * The goal was occupied; search forward for a free
967 * block within the next XX blocks.
968 *
969 * end_goal is more or less random, but it has to be
Mingming Cao617ba132006-10-11 01:20:53 -0700970 * less than EXT4_BLOCKS_PER_GROUP. Aligning up to the
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700971 * next 64-bit boundary is simple..
972 */
Mingming Cao617ba132006-10-11 01:20:53 -0700973 ext4_grpblk_t end_goal = (start + 63) & ~63;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700974 if (end_goal > maxblocks)
975 end_goal = maxblocks;
Mingming Cao617ba132006-10-11 01:20:53 -0700976 here = ext4_find_next_zero_bit(bh->b_data, end_goal, start);
977 if (here < end_goal && ext4_test_allocatable(here, bh))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700978 return here;
Mingming Cao617ba132006-10-11 01:20:53 -0700979 ext4_debug("Bit not found near goal\n");
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700980 }
981
982 here = start;
983 if (here < 0)
984 here = 0;
985
986 p = ((char *)bh->b_data) + (here >> 3);
Hugh Dickinsec0837f2006-12-06 20:39:26 -0800987 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700988 next = (r - ((char *)bh->b_data)) << 3;
989
Mingming Cao617ba132006-10-11 01:20:53 -0700990 if (next < maxblocks && next >= start && ext4_test_allocatable(next, bh))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700991 return next;
992
993 /*
994 * The bitmap search --- search forward alternately through the actual
995 * bitmap and the last-committed copy until we find a bit free in
996 * both
997 */
998 here = bitmap_search_next_usable_block(here, bh, maxblocks);
999 return here;
1000}
1001
1002/**
1003 * claim_block()
1004 * @block: the free block (group relative) to allocate
1005 * @bh: the bufferhead containts the block group bitmap
1006 *
1007 * We think we can allocate this block in this bitmap. Try to set the bit.
1008 * If that succeeds then check that nobody has allocated and then freed the
1009 * block since we saw that is was not marked in b_committed_data. If it _was_
1010 * allocated and freed then clear the bit in the bitmap again and return
1011 * zero (failure).
1012 */
1013static inline int
Mingming Cao617ba132006-10-11 01:20:53 -07001014claim_block(spinlock_t *lock, ext4_grpblk_t block, struct buffer_head *bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001015{
1016 struct journal_head *jh = bh2jh(bh);
1017 int ret;
1018
Mingming Cao617ba132006-10-11 01:20:53 -07001019 if (ext4_set_bit_atomic(lock, block, bh->b_data))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001020 return 0;
1021 jbd_lock_bh_state(bh);
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001022 if (jh->b_committed_data && ext4_test_bit(block, jh->b_committed_data)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001023 ext4_clear_bit_atomic(lock, block, bh->b_data);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001024 ret = 0;
1025 } else {
1026 ret = 1;
1027 }
1028 jbd_unlock_bh_state(bh);
1029 return ret;
1030}
1031
1032/**
Mingming Cao617ba132006-10-11 01:20:53 -07001033 * ext4_try_to_allocate()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001034 * @sb: superblock
1035 * @handle: handle to this transaction
1036 * @group: given allocation block group
1037 * @bitmap_bh: bufferhead holds the block bitmap
1038 * @grp_goal: given target block within the group
1039 * @count: target number of blocks to allocate
1040 * @my_rsv: reservation window
1041 *
1042 * Attempt to allocate blocks within a give range. Set the range of allocation
1043 * first, then find the first free bit(s) from the bitmap (within the range),
1044 * and at last, allocate the blocks by claiming the found free bit as allocated.
1045 *
1046 * To set the range of this allocation:
1047 * if there is a reservation window, only try to allocate block(s) from the
1048 * file's own reservation window;
1049 * Otherwise, the allocation range starts from the give goal block, ends at
1050 * the block group's last block.
1051 *
1052 * If we failed to allocate the desired block then we may end up crossing to a
1053 * new bitmap. In that case we must release write access to the old one via
Mingming Cao617ba132006-10-11 01:20:53 -07001054 * ext4_journal_release_buffer(), else we'll run out of credits.
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001055 */
Mingming Cao617ba132006-10-11 01:20:53 -07001056static ext4_grpblk_t
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001057ext4_try_to_allocate(struct super_block *sb, handle_t *handle,
1058 ext4_group_t group, struct buffer_head *bitmap_bh,
1059 ext4_grpblk_t grp_goal, unsigned long *count,
1060 struct ext4_reserve_window *my_rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001061{
Mingming Cao617ba132006-10-11 01:20:53 -07001062 ext4_fsblk_t group_first_block;
1063 ext4_grpblk_t start, end;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001064 unsigned long num = 0;
1065
1066 /* we do allocation within the reservation window if we have a window */
1067 if (my_rsv) {
Mingming Cao617ba132006-10-11 01:20:53 -07001068 group_first_block = ext4_group_first_block_no(sb, group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001069 if (my_rsv->_rsv_start >= group_first_block)
1070 start = my_rsv->_rsv_start - group_first_block;
1071 else
1072 /* reservation window cross group boundary */
1073 start = 0;
1074 end = my_rsv->_rsv_end - group_first_block + 1;
Mingming Cao617ba132006-10-11 01:20:53 -07001075 if (end > EXT4_BLOCKS_PER_GROUP(sb))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001076 /* reservation window crosses group boundary */
Mingming Cao617ba132006-10-11 01:20:53 -07001077 end = EXT4_BLOCKS_PER_GROUP(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001078 if ((start <= grp_goal) && (grp_goal < end))
1079 start = grp_goal;
1080 else
1081 grp_goal = -1;
1082 } else {
1083 if (grp_goal > 0)
1084 start = grp_goal;
1085 else
1086 start = 0;
Mingming Cao617ba132006-10-11 01:20:53 -07001087 end = EXT4_BLOCKS_PER_GROUP(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001088 }
1089
Mingming Cao617ba132006-10-11 01:20:53 -07001090 BUG_ON(start > EXT4_BLOCKS_PER_GROUP(sb));
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001091
1092repeat:
Mingming Cao617ba132006-10-11 01:20:53 -07001093 if (grp_goal < 0 || !ext4_test_allocatable(grp_goal, bitmap_bh)) {
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001094 grp_goal = find_next_usable_block(start, bitmap_bh, end);
1095 if (grp_goal < 0)
1096 goto fail_access;
1097 if (!my_rsv) {
1098 int i;
1099
1100 for (i = 0; i < 7 && grp_goal > start &&
Mingming Cao617ba132006-10-11 01:20:53 -07001101 ext4_test_allocatable(grp_goal - 1,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001102 bitmap_bh);
1103 i++, grp_goal--)
1104 ;
1105 }
1106 }
1107 start = grp_goal;
1108
Mingming Cao617ba132006-10-11 01:20:53 -07001109 if (!claim_block(sb_bgl_lock(EXT4_SB(sb), group),
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001110 grp_goal, bitmap_bh)) {
1111 /*
1112 * The block was allocated by another thread, or it was
1113 * allocated and then freed by another thread
1114 */
1115 start++;
1116 grp_goal++;
1117 if (start >= end)
1118 goto fail_access;
1119 goto repeat;
1120 }
1121 num++;
1122 grp_goal++;
1123 while (num < *count && grp_goal < end
Mingming Cao617ba132006-10-11 01:20:53 -07001124 && ext4_test_allocatable(grp_goal, bitmap_bh)
1125 && claim_block(sb_bgl_lock(EXT4_SB(sb), group),
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001126 grp_goal, bitmap_bh)) {
1127 num++;
1128 grp_goal++;
1129 }
1130 *count = num;
1131 return grp_goal - num;
1132fail_access:
1133 *count = num;
1134 return -1;
1135}
1136
1137/**
1138 * find_next_reservable_window():
1139 * find a reservable space within the given range.
1140 * It does not allocate the reservation window for now:
1141 * alloc_new_reservation() will do the work later.
1142 *
1143 * @search_head: the head of the searching list;
1144 * This is not necessarily the list head of the whole filesystem
1145 *
1146 * We have both head and start_block to assist the search
1147 * for the reservable space. The list starts from head,
1148 * but we will shift to the place where start_block is,
1149 * then start from there, when looking for a reservable space.
1150 *
1151 * @size: the target new reservation window size
1152 *
1153 * @group_first_block: the first block we consider to start
1154 * the real search from
1155 *
1156 * @last_block:
1157 * the maximum block number that our goal reservable space
1158 * could start from. This is normally the last block in this
1159 * group. The search will end when we found the start of next
1160 * possible reservable space is out of this boundary.
1161 * This could handle the cross boundary reservation window
1162 * request.
1163 *
1164 * basically we search from the given range, rather than the whole
1165 * reservation double linked list, (start_block, last_block)
1166 * to find a free region that is of my size and has not
1167 * been reserved.
1168 *
1169 */
1170static int find_next_reservable_window(
Mingming Cao617ba132006-10-11 01:20:53 -07001171 struct ext4_reserve_window_node *search_head,
1172 struct ext4_reserve_window_node *my_rsv,
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001173 struct super_block *sb,
Mingming Cao617ba132006-10-11 01:20:53 -07001174 ext4_fsblk_t start_block,
1175 ext4_fsblk_t last_block)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001176{
1177 struct rb_node *next;
Mingming Cao617ba132006-10-11 01:20:53 -07001178 struct ext4_reserve_window_node *rsv, *prev;
1179 ext4_fsblk_t cur;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001180 int size = my_rsv->rsv_goal_size;
1181
1182 /* TODO: make the start of the reservation window byte-aligned */
1183 /* cur = *start_block & ~7;*/
1184 cur = start_block;
1185 rsv = search_head;
1186 if (!rsv)
1187 return -1;
1188
1189 while (1) {
1190 if (cur <= rsv->rsv_end)
1191 cur = rsv->rsv_end + 1;
1192
1193 /* TODO?
1194 * in the case we could not find a reservable space
1195 * that is what is expected, during the re-search, we could
1196 * remember what's the largest reservable space we could have
1197 * and return that one.
1198 *
1199 * For now it will fail if we could not find the reservable
1200 * space with expected-size (or more)...
1201 */
1202 if (cur > last_block)
1203 return -1; /* fail */
1204
1205 prev = rsv;
1206 next = rb_next(&rsv->rsv_node);
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001207 rsv = rb_entry(next, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001208
1209 /*
1210 * Reached the last reservation, we can just append to the
1211 * previous one.
1212 */
1213 if (!next)
1214 break;
1215
1216 if (cur + size <= rsv->rsv_start) {
1217 /*
1218 * Found a reserveable space big enough. We could
1219 * have a reservation across the group boundary here
1220 */
1221 break;
1222 }
1223 }
1224 /*
1225 * we come here either :
1226 * when we reach the end of the whole list,
1227 * and there is empty reservable space after last entry in the list.
1228 * append it to the end of the list.
1229 *
1230 * or we found one reservable space in the middle of the list,
1231 * return the reservation window that we could append to.
1232 * succeed.
1233 */
1234
1235 if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
1236 rsv_window_remove(sb, my_rsv);
1237
1238 /*
1239 * Let's book the whole avaliable window for now. We will check the
1240 * disk bitmap later and then, if there are free blocks then we adjust
1241 * the window size if it's larger than requested.
1242 * Otherwise, we will remove this node from the tree next time
1243 * call find_next_reservable_window.
1244 */
1245 my_rsv->rsv_start = cur;
1246 my_rsv->rsv_end = cur + size - 1;
1247 my_rsv->rsv_alloc_hit = 0;
1248
1249 if (prev != my_rsv)
Mingming Cao617ba132006-10-11 01:20:53 -07001250 ext4_rsv_window_add(sb, my_rsv);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001251
1252 return 0;
1253}
1254
1255/**
1256 * alloc_new_reservation()--allocate a new reservation window
1257 *
1258 * To make a new reservation, we search part of the filesystem
1259 * reservation list (the list that inside the group). We try to
1260 * allocate a new reservation window near the allocation goal,
1261 * or the beginning of the group, if there is no goal.
1262 *
1263 * We first find a reservable space after the goal, then from
1264 * there, we check the bitmap for the first free block after
1265 * it. If there is no free block until the end of group, then the
1266 * whole group is full, we failed. Otherwise, check if the free
1267 * block is inside the expected reservable space, if so, we
1268 * succeed.
1269 * If the first free block is outside the reservable space, then
1270 * start from the first free block, we search for next available
1271 * space, and go on.
1272 *
1273 * on succeed, a new reservation will be found and inserted into the list
1274 * It contains at least one free block, and it does not overlap with other
1275 * reservation windows.
1276 *
1277 * failed: we failed to find a reservation window in this group
1278 *
1279 * @rsv: the reservation
1280 *
1281 * @grp_goal: The goal (group-relative). It is where the search for a
1282 * free reservable space should start from.
1283 * if we have a grp_goal(grp_goal >0 ), then start from there,
1284 * no grp_goal(grp_goal = -1), we start from the first block
1285 * of the group.
1286 *
1287 * @sb: the super block
1288 * @group: the group we are trying to allocate in
1289 * @bitmap_bh: the block group block bitmap
1290 *
1291 */
Mingming Cao617ba132006-10-11 01:20:53 -07001292static int alloc_new_reservation(struct ext4_reserve_window_node *my_rsv,
1293 ext4_grpblk_t grp_goal, struct super_block *sb,
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001294 ext4_group_t group, struct buffer_head *bitmap_bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001295{
Mingming Cao617ba132006-10-11 01:20:53 -07001296 struct ext4_reserve_window_node *search_head;
1297 ext4_fsblk_t group_first_block, group_end_block, start_block;
1298 ext4_grpblk_t first_free_block;
1299 struct rb_root *fs_rsv_root = &EXT4_SB(sb)->s_rsv_window_root;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001300 unsigned long size;
1301 int ret;
Mingming Cao617ba132006-10-11 01:20:53 -07001302 spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001303
Mingming Cao617ba132006-10-11 01:20:53 -07001304 group_first_block = ext4_group_first_block_no(sb, group);
1305 group_end_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001306
1307 if (grp_goal < 0)
1308 start_block = group_first_block;
1309 else
1310 start_block = grp_goal + group_first_block;
1311
1312 size = my_rsv->rsv_goal_size;
1313
1314 if (!rsv_is_empty(&my_rsv->rsv_window)) {
1315 /*
1316 * if the old reservation is cross group boundary
1317 * and if the goal is inside the old reservation window,
1318 * we will come here when we just failed to allocate from
1319 * the first part of the window. We still have another part
1320 * that belongs to the next group. In this case, there is no
1321 * point to discard our window and try to allocate a new one
1322 * in this group(which will fail). we should
1323 * keep the reservation window, just simply move on.
1324 *
1325 * Maybe we could shift the start block of the reservation
1326 * window to the first block of next group.
1327 */
1328
1329 if ((my_rsv->rsv_start <= group_end_block) &&
1330 (my_rsv->rsv_end > group_end_block) &&
1331 (start_block >= my_rsv->rsv_start))
1332 return -1;
1333
1334 if ((my_rsv->rsv_alloc_hit >
1335 (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
1336 /*
1337 * if the previously allocation hit ratio is
1338 * greater than 1/2, then we double the size of
1339 * the reservation window the next time,
1340 * otherwise we keep the same size window
1341 */
1342 size = size * 2;
Mingming Cao617ba132006-10-11 01:20:53 -07001343 if (size > EXT4_MAX_RESERVE_BLOCKS)
1344 size = EXT4_MAX_RESERVE_BLOCKS;
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001345 my_rsv->rsv_goal_size = size;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001346 }
1347 }
1348
1349 spin_lock(rsv_lock);
1350 /*
1351 * shift the search start to the window near the goal block
1352 */
1353 search_head = search_reserve_window(fs_rsv_root, start_block);
1354
1355 /*
1356 * find_next_reservable_window() simply finds a reservable window
1357 * inside the given range(start_block, group_end_block).
1358 *
1359 * To make sure the reservation window has a free bit inside it, we
1360 * need to check the bitmap after we found a reservable window.
1361 */
1362retry:
1363 ret = find_next_reservable_window(search_head, my_rsv, sb,
1364 start_block, group_end_block);
1365
1366 if (ret == -1) {
1367 if (!rsv_is_empty(&my_rsv->rsv_window))
1368 rsv_window_remove(sb, my_rsv);
1369 spin_unlock(rsv_lock);
1370 return -1;
1371 }
1372
1373 /*
1374 * On success, find_next_reservable_window() returns the
1375 * reservation window where there is a reservable space after it.
1376 * Before we reserve this reservable space, we need
1377 * to make sure there is at least a free block inside this region.
1378 *
1379 * searching the first free bit on the block bitmap and copy of
1380 * last committed bitmap alternatively, until we found a allocatable
1381 * block. Search start from the start block of the reservable space
1382 * we just found.
1383 */
1384 spin_unlock(rsv_lock);
1385 first_free_block = bitmap_search_next_usable_block(
1386 my_rsv->rsv_start - group_first_block,
1387 bitmap_bh, group_end_block - group_first_block + 1);
1388
1389 if (first_free_block < 0) {
1390 /*
1391 * no free block left on the bitmap, no point
1392 * to reserve the space. return failed.
1393 */
1394 spin_lock(rsv_lock);
1395 if (!rsv_is_empty(&my_rsv->rsv_window))
1396 rsv_window_remove(sb, my_rsv);
1397 spin_unlock(rsv_lock);
1398 return -1; /* failed */
1399 }
1400
1401 start_block = first_free_block + group_first_block;
1402 /*
1403 * check if the first free block is within the
1404 * free space we just reserved
1405 */
Hugh Dickinsb2f2c762006-12-06 20:39:20 -08001406 if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001407 return 0; /* success */
1408 /*
1409 * if the first free bit we found is out of the reservable space
1410 * continue search for next reservable space,
1411 * start from where the free block is,
1412 * we also shift the list head to where we stopped last time
1413 */
1414 search_head = my_rsv;
1415 spin_lock(rsv_lock);
1416 goto retry;
1417}
1418
1419/**
1420 * try_to_extend_reservation()
1421 * @my_rsv: given reservation window
1422 * @sb: super block
1423 * @size: the delta to extend
1424 *
1425 * Attempt to expand the reservation window large enough to have
1426 * required number of free blocks
1427 *
Mingming Cao617ba132006-10-11 01:20:53 -07001428 * Since ext4_try_to_allocate() will always allocate blocks within
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001429 * the reservation window range, if the window size is too small,
1430 * multiple blocks allocation has to stop at the end of the reservation
1431 * window. To make this more efficient, given the total number of
1432 * blocks needed and the current size of the window, we try to
1433 * expand the reservation window size if necessary on a best-effort
Mingming Cao617ba132006-10-11 01:20:53 -07001434 * basis before ext4_new_blocks() tries to allocate blocks,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001435 */
Mingming Cao617ba132006-10-11 01:20:53 -07001436static void try_to_extend_reservation(struct ext4_reserve_window_node *my_rsv,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001437 struct super_block *sb, int size)
1438{
Mingming Cao617ba132006-10-11 01:20:53 -07001439 struct ext4_reserve_window_node *next_rsv;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001440 struct rb_node *next;
Mingming Cao617ba132006-10-11 01:20:53 -07001441 spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001442
1443 if (!spin_trylock(rsv_lock))
1444 return;
1445
1446 next = rb_next(&my_rsv->rsv_node);
1447
1448 if (!next)
1449 my_rsv->rsv_end += size;
1450 else {
Hugh Dickinsb78a6572006-12-06 20:39:21 -08001451 next_rsv = rb_entry(next, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001452
1453 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
1454 my_rsv->rsv_end += size;
1455 else
1456 my_rsv->rsv_end = next_rsv->rsv_start - 1;
1457 }
1458 spin_unlock(rsv_lock);
1459}
1460
1461/**
Mingming Cao617ba132006-10-11 01:20:53 -07001462 * ext4_try_to_allocate_with_rsv()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001463 * @sb: superblock
1464 * @handle: handle to this transaction
1465 * @group: given allocation block group
1466 * @bitmap_bh: bufferhead holds the block bitmap
1467 * @grp_goal: given target block within the group
1468 * @count: target number of blocks to allocate
1469 * @my_rsv: reservation window
1470 * @errp: pointer to store the error code
1471 *
1472 * This is the main function used to allocate a new block and its reservation
1473 * window.
1474 *
1475 * Each time when a new block allocation is need, first try to allocate from
1476 * its own reservation. If it does not have a reservation window, instead of
1477 * looking for a free bit on bitmap first, then look up the reservation list to
1478 * see if it is inside somebody else's reservation window, we try to allocate a
1479 * reservation window for it starting from the goal first. Then do the block
1480 * allocation within the reservation window.
1481 *
1482 * This will avoid keeping on searching the reservation list again and
1483 * again when somebody is looking for a free block (without
1484 * reservation), and there are lots of free blocks, but they are all
1485 * being reserved.
1486 *
1487 * We use a red-black tree for the per-filesystem reservation list.
1488 *
1489 */
Mingming Cao617ba132006-10-11 01:20:53 -07001490static ext4_grpblk_t
1491ext4_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001492 ext4_group_t group, struct buffer_head *bitmap_bh,
Mingming Cao617ba132006-10-11 01:20:53 -07001493 ext4_grpblk_t grp_goal,
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001494 struct ext4_reserve_window_node *my_rsv,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001495 unsigned long *count, int *errp)
1496{
Mingming Cao617ba132006-10-11 01:20:53 -07001497 ext4_fsblk_t group_first_block, group_last_block;
1498 ext4_grpblk_t ret = 0;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001499 int fatal;
1500 unsigned long num = *count;
1501
1502 *errp = 0;
1503
1504 /*
1505 * Make sure we use undo access for the bitmap, because it is critical
1506 * that we do the frozen_data COW on bitmap buffers in all cases even
1507 * if the buffer is in BJ_Forget state in the committing transaction.
1508 */
1509 BUFFER_TRACE(bitmap_bh, "get undo access for new block");
Mingming Cao617ba132006-10-11 01:20:53 -07001510 fatal = ext4_journal_get_undo_access(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001511 if (fatal) {
1512 *errp = fatal;
1513 return -1;
1514 }
1515
1516 /*
1517 * we don't deal with reservation when
1518 * filesystem is mounted without reservation
1519 * or the file is not a regular file
1520 * or last attempt to allocate a block with reservation turned on failed
1521 */
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001522 if (my_rsv == NULL) {
Mingming Cao617ba132006-10-11 01:20:53 -07001523 ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001524 grp_goal, count, NULL);
1525 goto out;
1526 }
1527 /*
1528 * grp_goal is a group relative block number (if there is a goal)
Hugh Dickinse7dc95d2006-12-06 20:39:19 -08001529 * 0 <= grp_goal < EXT4_BLOCKS_PER_GROUP(sb)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001530 * first block is a filesystem wide block number
1531 * first block is the block number of the first block in this group
1532 */
Mingming Cao617ba132006-10-11 01:20:53 -07001533 group_first_block = ext4_group_first_block_no(sb, group);
1534 group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001535
1536 /*
1537 * Basically we will allocate a new block from inode's reservation
1538 * window.
1539 *
1540 * We need to allocate a new reservation window, if:
1541 * a) inode does not have a reservation window; or
1542 * b) last attempt to allocate a block from existing reservation
1543 * failed; or
1544 * c) we come here with a goal and with a reservation window
1545 *
1546 * We do not need to allocate a new reservation window if we come here
1547 * at the beginning with a goal and the goal is inside the window, or
1548 * we don't have a goal but already have a reservation window.
1549 * then we could go to allocate from the reservation window directly.
1550 */
1551 while (1) {
1552 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
1553 !goal_in_my_reservation(&my_rsv->rsv_window,
1554 grp_goal, group, sb)) {
1555 if (my_rsv->rsv_goal_size < *count)
1556 my_rsv->rsv_goal_size = *count;
1557 ret = alloc_new_reservation(my_rsv, grp_goal, sb,
1558 group, bitmap_bh);
1559 if (ret < 0)
1560 break; /* failed */
1561
1562 if (!goal_in_my_reservation(&my_rsv->rsv_window,
1563 grp_goal, group, sb))
1564 grp_goal = -1;
Hugh Dickinse7dc95d2006-12-06 20:39:19 -08001565 } else if (grp_goal >= 0) {
Mingming Cao1df1e632006-12-06 20:38:19 -08001566 int curr = my_rsv->rsv_end -
1567 (grp_goal + group_first_block) + 1;
1568
1569 if (curr < *count)
1570 try_to_extend_reservation(my_rsv, sb,
1571 *count - curr);
1572 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001573
1574 if ((my_rsv->rsv_start > group_last_block) ||
1575 (my_rsv->rsv_end < group_first_block)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001576 rsv_window_dump(&EXT4_SB(sb)->s_rsv_window_root, 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001577 BUG();
1578 }
Mingming Cao617ba132006-10-11 01:20:53 -07001579 ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001580 grp_goal, &num, &my_rsv->rsv_window);
1581 if (ret >= 0) {
1582 my_rsv->rsv_alloc_hit += num;
1583 *count = num;
1584 break; /* succeed */
1585 }
1586 num = *count;
1587 }
1588out:
1589 if (ret >= 0) {
1590 BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for "
1591 "bitmap block");
Mingming Cao617ba132006-10-11 01:20:53 -07001592 fatal = ext4_journal_dirty_metadata(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001593 if (fatal) {
1594 *errp = fatal;
1595 return -1;
1596 }
1597 return ret;
1598 }
1599
1600 BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
Mingming Cao617ba132006-10-11 01:20:53 -07001601 ext4_journal_release_buffer(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001602 return ret;
1603}
1604
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001605int ext4_claim_free_blocks(struct ext4_sb_info *sbi,
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001606 s64 nblocks)
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001607{
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001608 s64 free_blocks, dirty_blocks;
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001609 s64 root_blocks = 0;
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001610 struct percpu_counter *fbc = &sbi->s_freeblocks_counter;
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001611 struct percpu_counter *dbc = &sbi->s_dirtyblocks_counter;
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001612
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001613 free_blocks = percpu_counter_read_positive(fbc);
1614 dirty_blocks = percpu_counter_read_positive(dbc);
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001615
1616 if (!capable(CAP_SYS_RESOURCE) &&
1617 sbi->s_resuid != current->fsuid &&
1618 (sbi->s_resgid == 0 || !in_group_p(sbi->s_resgid)))
1619 root_blocks = ext4_r_blocks_count(sbi->s_es);
1620
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001621 if (free_blocks - (nblocks + root_blocks + dirty_blocks) <
1622 EXT4_FREEBLOCKS_WATERMARK) {
1623 free_blocks = percpu_counter_sum(fbc);
1624 dirty_blocks = percpu_counter_sum(dbc);
1625 if (dirty_blocks < 0) {
1626 printk(KERN_CRIT "Dirty block accounting "
1627 "went wrong %lld\n",
1628 dirty_blocks);
1629 }
1630 }
1631 /* Check whether we have space after
1632 * accounting for current dirty blocks
1633 */
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001634 if (free_blocks < ((root_blocks + nblocks) + dirty_blocks))
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001635 /* we don't have free space */
1636 return -ENOSPC;
1637
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001638 /* Add the blocks to nblocks */
1639 percpu_counter_add(dbc, nblocks);
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001640 return 0;
1641}
1642
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001643/**
Mingming Cao617ba132006-10-11 01:20:53 -07001644 * ext4_has_free_blocks()
Mingming Cao07031432008-07-11 19:27:31 -04001645 * @sbi: in-core super block structure.
1646 * @nblocks: number of neeed blocks
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001647 *
Mingming Cao07031432008-07-11 19:27:31 -04001648 * Check if filesystem has free blocks available for allocation.
1649 * Return the number of blocks avaible for allocation for this request
1650 * On success, return nblocks
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001651 */
Mingming Cao07031432008-07-11 19:27:31 -04001652ext4_fsblk_t ext4_has_free_blocks(struct ext4_sb_info *sbi,
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001653 s64 nblocks)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001654{
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001655 s64 free_blocks, dirty_blocks;
1656 s64 root_blocks = 0;
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001657 struct percpu_counter *fbc = &sbi->s_freeblocks_counter;
1658 struct percpu_counter *dbc = &sbi->s_dirtyblocks_counter;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001659
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001660 free_blocks = percpu_counter_read_positive(fbc);
1661 dirty_blocks = percpu_counter_read_positive(dbc);
Mingming Cao07031432008-07-11 19:27:31 -04001662
1663 if (!capable(CAP_SYS_RESOURCE) &&
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001664 sbi->s_resuid != current->fsuid &&
Mingming Cao07031432008-07-11 19:27:31 -04001665 (sbi->s_resgid == 0 || !in_group_p(sbi->s_resgid)))
1666 root_blocks = ext4_r_blocks_count(sbi->s_es);
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001667
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001668 if (free_blocks - (nblocks + root_blocks + dirty_blocks) <
1669 EXT4_FREEBLOCKS_WATERMARK) {
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001670 free_blocks = percpu_counter_sum(fbc);
1671 dirty_blocks = percpu_counter_sum(dbc);
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001672 }
1673 if (free_blocks <= (root_blocks + dirty_blocks))
Aneesh Kumar K.V16eb7292008-08-19 21:16:54 -04001674 /* we don't have free space */
1675 return 0;
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001676
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001677 if (free_blocks - (root_blocks + dirty_blocks) < nblocks)
Aneesh Kumar K.V5c791612008-10-08 23:12:24 -04001678 return free_blocks - (root_blocks + dirty_blocks);
Mingming Cao07031432008-07-11 19:27:31 -04001679 return nblocks;
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001680}
Mingming Cao07031432008-07-11 19:27:31 -04001681
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001682
1683/**
Mingming Cao617ba132006-10-11 01:20:53 -07001684 * ext4_should_retry_alloc()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001685 * @sb: super block
1686 * @retries number of attemps has been made
1687 *
Mingming Cao617ba132006-10-11 01:20:53 -07001688 * ext4_should_retry_alloc() is called when ENOSPC is returned, and if
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001689 * it is profitable to retry the operation, this function will wait
1690 * for the current or commiting transaction to complete, and then
1691 * return TRUE.
1692 *
1693 * if the total number of retries exceed three times, return FALSE.
1694 */
Mingming Cao617ba132006-10-11 01:20:53 -07001695int ext4_should_retry_alloc(struct super_block *sb, int *retries)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001696{
Mingming Cao07031432008-07-11 19:27:31 -04001697 if (!ext4_has_free_blocks(EXT4_SB(sb), 1) || (*retries)++ > 3)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001698 return 0;
1699
1700 jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
1701
Mingming Caodab291a2006-10-11 01:21:01 -07001702 return jbd2_journal_force_commit_nested(EXT4_SB(sb)->s_journal);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001703}
1704
1705/**
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04001706 * ext4_old_new_blocks() -- core block bitmap based block allocation function
1707 *
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001708 * @handle: handle to this transaction
1709 * @inode: file inode
1710 * @goal: given target block(filesystem wide)
1711 * @count: target number of blocks to allocate
1712 * @errp: error code
1713 *
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04001714 * ext4_old_new_blocks uses a goal block to assist allocation and look up
1715 * the block bitmap directly to do block allocation. It tries to
1716 * allocate block(s) from the block group contains the goal block first. If
1717 * that fails, it will try to allocate block(s) from other block groups
1718 * without any specific goal block.
1719 *
1720 * This function is called when -o nomballoc mount option is enabled
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001721 *
1722 */
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04001723ext4_fsblk_t ext4_old_new_blocks(handle_t *handle, struct inode *inode,
Mingming Cao617ba132006-10-11 01:20:53 -07001724 ext4_fsblk_t goal, unsigned long *count, int *errp)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001725{
1726 struct buffer_head *bitmap_bh = NULL;
1727 struct buffer_head *gdp_bh;
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001728 ext4_group_t group_no;
1729 ext4_group_t goal_group;
Mingming Cao617ba132006-10-11 01:20:53 -07001730 ext4_grpblk_t grp_target_blk; /* blockgroup relative goal block */
1731 ext4_grpblk_t grp_alloc_blk; /* blockgroup-relative allocated block*/
1732 ext4_fsblk_t ret_block; /* filesyetem-wide allocated block */
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001733 ext4_group_t bgi; /* blockgroup iteration index */
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001734 int fatal = 0, err;
1735 int performed_allocation = 0;
Mingming Cao617ba132006-10-11 01:20:53 -07001736 ext4_grpblk_t free_blocks; /* number of free blocks in a group */
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001737 struct super_block *sb;
Mingming Cao617ba132006-10-11 01:20:53 -07001738 struct ext4_group_desc *gdp;
1739 struct ext4_super_block *es;
1740 struct ext4_sb_info *sbi;
1741 struct ext4_reserve_window_node *my_rsv = NULL;
1742 struct ext4_block_alloc_info *block_i;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001743 unsigned short windowsz = 0;
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001744 ext4_group_t ngroups;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001745 unsigned long num = *count;
1746
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001747 sb = inode->i_sb;
1748 if (!sb) {
Mingming Cao07031432008-07-11 19:27:31 -04001749 *errp = -ENODEV;
Theodore Ts'o4776004f2008-09-08 23:00:52 -04001750 printk(KERN_ERR "ext4_new_block: nonexistent superblock");
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001751 return 0;
1752 }
1753
Mingming Cao07031432008-07-11 19:27:31 -04001754 sbi = EXT4_SB(sb);
Mingming Caod2a17632008-07-14 17:52:37 -04001755 if (!EXT4_I(inode)->i_delalloc_reserved_flag) {
1756 /*
1757 * With delalloc we already reserved the blocks
1758 */
Aneesh Kumar K.V030ba6b2008-09-08 23:14:50 -04001759 while (*count && ext4_claim_free_blocks(sbi, *count)) {
1760 /* let others to free the space */
1761 yield();
1762 *count = *count >> 1;
1763 }
1764 if (!*count) {
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04001765 *errp = -ENOSPC;
1766 return 0; /*return with ENOSPC error */
1767 }
Aneesh Kumar K.V030ba6b2008-09-08 23:14:50 -04001768 num = *count;
Mingming Caod2a17632008-07-14 17:52:37 -04001769 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001770 /*
1771 * Check quota for allocation of this block.
1772 */
1773 if (DQUOT_ALLOC_BLOCK(inode, num)) {
1774 *errp = -EDQUOT;
1775 return 0;
1776 }
1777
Mingming Cao617ba132006-10-11 01:20:53 -07001778 sbi = EXT4_SB(sb);
1779 es = EXT4_SB(sb)->s_es;
Eric Sandeenc549a952008-01-28 23:58:27 -05001780 ext4_debug("goal=%llu.\n", goal);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001781 /*
1782 * Allocate a block from reservation only when
1783 * filesystem is mounted with reservation(default,-o reservation), and
1784 * it's a regular file, and
1785 * the desired window size is greater than 0 (One could use ioctl
Mingming Cao617ba132006-10-11 01:20:53 -07001786 * command EXT4_IOC_SETRSVSZ to set the window size to 0 to turn off
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001787 * reservation on that particular file)
1788 */
Mingming Cao617ba132006-10-11 01:20:53 -07001789 block_i = EXT4_I(inode)->i_block_alloc_info;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001790 if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
1791 my_rsv = &block_i->rsv_window_node;
1792
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001793 /*
1794 * First, test whether the goal block is free.
1795 */
1796 if (goal < le32_to_cpu(es->s_first_data_block) ||
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001797 goal >= ext4_blocks_count(es))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001798 goal = le32_to_cpu(es->s_first_data_block);
Mingming Cao3a5b2ec2006-10-11 01:21:05 -07001799 ext4_get_group_no_and_offset(sb, goal, &group_no, &grp_target_blk);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001800 goal_group = group_no;
1801retry_alloc:
Mingming Cao617ba132006-10-11 01:20:53 -07001802 gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001803 if (!gdp)
1804 goto io_error;
1805
1806 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001807
1808 if (free_blocks > 0) {
Aneesh Kumar K.V68629f22008-09-08 23:09:17 -04001809 /*
1810 * try to allocate with group target block
1811 * in the goal group. If we have low free_blocks
1812 * count turn off reservation
1813 */
1814 if (my_rsv && (free_blocks < windowsz)
1815 && (rsv_is_empty(&my_rsv->rsv_window)))
1816 my_rsv = NULL;
1817
Theodore Ts'o574ca172008-07-11 19:27:31 -04001818 bitmap_bh = ext4_read_block_bitmap(sb, group_no);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001819 if (!bitmap_bh)
1820 goto io_error;
Mingming Cao617ba132006-10-11 01:20:53 -07001821 grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001822 group_no, bitmap_bh, grp_target_blk,
1823 my_rsv, &num, &fatal);
1824 if (fatal)
1825 goto out;
1826 if (grp_alloc_blk >= 0)
1827 goto allocated;
1828 }
1829
Mingming Cao617ba132006-10-11 01:20:53 -07001830 ngroups = EXT4_SB(sb)->s_groups_count;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001831 smp_rmb();
1832
1833 /*
1834 * Now search the rest of the groups. We assume that
Akinobu Mita144704e2008-02-06 01:40:15 -08001835 * group_no and gdp correctly point to the last group visited.
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001836 */
1837 for (bgi = 0; bgi < ngroups; bgi++) {
1838 group_no++;
1839 if (group_no >= ngroups)
1840 group_no = 0;
Mingming Cao617ba132006-10-11 01:20:53 -07001841 gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
Hugh Dickins341cee42006-12-06 20:39:24 -08001842 if (!gdp)
1843 goto io_error;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001844 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1845 /*
1846 * skip this group if the number of
1847 * free blocks is less than half of the reservation
1848 * window size.
1849 */
Aneesh Kumar K.V68629f22008-09-08 23:09:17 -04001850 if (my_rsv && (free_blocks <= (windowsz/2)))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001851 continue;
1852
1853 brelse(bitmap_bh);
Theodore Ts'o574ca172008-07-11 19:27:31 -04001854 bitmap_bh = ext4_read_block_bitmap(sb, group_no);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001855 if (!bitmap_bh)
1856 goto io_error;
1857 /*
1858 * try to allocate block(s) from this group, without a goal(-1).
1859 */
Mingming Cao617ba132006-10-11 01:20:53 -07001860 grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001861 group_no, bitmap_bh, -1, my_rsv,
1862 &num, &fatal);
1863 if (fatal)
1864 goto out;
1865 if (grp_alloc_blk >= 0)
1866 goto allocated;
1867 }
1868 /*
1869 * We may end up a bogus ealier ENOSPC error due to
1870 * filesystem is "full" of reservations, but
1871 * there maybe indeed free blocks avaliable on disk
1872 * In this case, we just forget about the reservations
1873 * just do block allocation as without reservations.
1874 */
1875 if (my_rsv) {
1876 my_rsv = NULL;
Hugh Dickinscd16c8f2006-12-06 20:39:18 -08001877 windowsz = 0;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001878 group_no = goal_group;
1879 goto retry_alloc;
1880 }
1881 /* No space left on the device */
1882 *errp = -ENOSPC;
1883 goto out;
1884
1885allocated:
1886
Eric Sandeenc549a952008-01-28 23:58:27 -05001887 ext4_debug("using block group %lu(%d)\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001888 group_no, gdp->bg_free_blocks_count);
1889
1890 BUFFER_TRACE(gdp_bh, "get_write_access");
Mingming Cao617ba132006-10-11 01:20:53 -07001891 fatal = ext4_journal_get_write_access(handle, gdp_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001892 if (fatal)
1893 goto out;
1894
Mingming Cao617ba132006-10-11 01:20:53 -07001895 ret_block = grp_alloc_blk + ext4_group_first_block_no(sb, group_no);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001896
Alexandre Ratchov8fadc142006-10-11 01:21:15 -07001897 if (in_range(ext4_block_bitmap(sb, gdp), ret_block, num) ||
Toshiyuki Okajima29bc5b42007-07-15 23:41:22 -07001898 in_range(ext4_inode_bitmap(sb, gdp), ret_block, num) ||
Alexandre Ratchov8fadc142006-10-11 01:21:15 -07001899 in_range(ret_block, ext4_inode_table(sb, gdp),
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001900 EXT4_SB(sb)->s_itb_per_group) ||
Alexandre Ratchov8fadc142006-10-11 01:21:15 -07001901 in_range(ret_block + num - 1, ext4_inode_table(sb, gdp),
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -05001902 EXT4_SB(sb)->s_itb_per_group)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001903 ext4_error(sb, "ext4_new_block",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001904 "Allocating block in system zone - "
Mingming Cao2ae02102006-10-11 01:21:11 -07001905 "blocks from %llu, length %lu",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001906 ret_block, num);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04001907 /*
1908 * claim_block marked the blocks we allocated
1909 * as in use. So we may want to selectively
1910 * mark some of the blocks as free
1911 */
1912 goto retry_alloc;
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -05001913 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001914
1915 performed_allocation = 1;
1916
Jose R. Santose23291b2007-07-18 08:57:06 -04001917#ifdef CONFIG_JBD2_DEBUG
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001918 {
1919 struct buffer_head *debug_bh;
1920
1921 /* Record bitmap buffer state in the newly allocated block */
1922 debug_bh = sb_find_get_block(sb, ret_block);
1923 if (debug_bh) {
1924 BUFFER_TRACE(debug_bh, "state when allocated");
1925 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap state");
1926 brelse(debug_bh);
1927 }
1928 }
1929 jbd_lock_bh_state(bitmap_bh);
1930 spin_lock(sb_bgl_lock(sbi, group_no));
1931 if (buffer_jbd(bitmap_bh) && bh2jh(bitmap_bh)->b_committed_data) {
1932 int i;
1933
1934 for (i = 0; i < num; i++) {
Mingming Cao617ba132006-10-11 01:20:53 -07001935 if (ext4_test_bit(grp_alloc_blk+i,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001936 bh2jh(bitmap_bh)->b_committed_data)) {
Theodore Ts'o4776004f2008-09-08 23:00:52 -04001937 printk(KERN_ERR "%s: block was unexpectedly "
1938 "set in b_committed_data\n", __func__);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001939 }
1940 }
1941 }
Mingming Cao617ba132006-10-11 01:20:53 -07001942 ext4_debug("found bit %d\n", grp_alloc_blk);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001943 spin_unlock(sb_bgl_lock(sbi, group_no));
1944 jbd_unlock_bh_state(bitmap_bh);
1945#endif
1946
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001947 if (ret_block + num - 1 >= ext4_blocks_count(es)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001948 ext4_error(sb, "ext4_new_block",
Mingming Cao2ae02102006-10-11 01:21:11 -07001949 "block(%llu) >= blocks count(%llu) - "
Mingming Cao3a5b2ec2006-10-11 01:21:05 -07001950 "block_group = %lu, es == %p ", ret_block,
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001951 ext4_blocks_count(es), group_no, es);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001952 goto out;
1953 }
1954
1955 /*
1956 * It is up to the caller to add the new buffer to a journal
1957 * list of some description. We don't know in advance whether
1958 * the caller wants to use it as metadata or data.
1959 */
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001960 spin_lock(sb_bgl_lock(sbi, group_no));
Andreas Dilger717d50e2007-10-16 18:38:25 -04001961 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
1962 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
Marcin Slusarze8546d02008-04-17 10:38:59 -04001963 le16_add_cpu(&gdp->bg_free_blocks_count, -num);
Andreas Dilger717d50e2007-10-16 18:38:25 -04001964 gdp->bg_checksum = ext4_group_desc_csum(sbi, group_no, gdp);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001965 spin_unlock(sb_bgl_lock(sbi, group_no));
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04001966 percpu_counter_sub(&sbi->s_freeblocks_counter, num);
1967 /*
1968 * Now reduce the dirty block count also. Should not go negative
1969 */
1970 if (!EXT4_I(inode)->i_delalloc_reserved_flag)
1971 percpu_counter_sub(&sbi->s_dirtyblocks_counter, *count);
1972 else
1973 percpu_counter_sub(&sbi->s_dirtyblocks_counter, num);
Jose R. Santos772cb7c2008-07-11 19:27:31 -04001974 if (sbi->s_log_groups_per_flex) {
1975 ext4_group_t flex_group = ext4_flex_group(sbi, group_no);
1976 spin_lock(sb_bgl_lock(sbi, flex_group));
1977 sbi->s_flex_groups[flex_group].free_blocks -= num;
1978 spin_unlock(sb_bgl_lock(sbi, flex_group));
1979 }
1980
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001981 BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
Mingming Cao617ba132006-10-11 01:20:53 -07001982 err = ext4_journal_dirty_metadata(handle, gdp_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001983 if (!fatal)
1984 fatal = err;
1985
1986 sb->s_dirt = 1;
1987 if (fatal)
1988 goto out;
1989
1990 *errp = 0;
1991 brelse(bitmap_bh);
1992 DQUOT_FREE_BLOCK(inode, *count-num);
1993 *count = num;
1994 return ret_block;
1995
1996io_error:
1997 *errp = -EIO;
1998out:
1999 if (fatal) {
2000 *errp = fatal;
Mingming Cao617ba132006-10-11 01:20:53 -07002001 ext4_std_error(sb, fatal);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002002 }
2003 /*
2004 * Undo the block allocation
2005 */
2006 if (!performed_allocation)
2007 DQUOT_FREE_BLOCK(inode, *count);
2008 brelse(bitmap_bh);
2009 return 0;
2010}
2011
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002012#define EXT4_META_BLOCK 0x1
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002013
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002014static ext4_fsblk_t do_blk_alloc(handle_t *handle, struct inode *inode,
Aneesh Kumar K.V7061eba2008-07-11 19:27:31 -04002015 ext4_lblk_t iblock, ext4_fsblk_t goal,
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002016 unsigned long *count, int *errp, int flags)
Aneesh Kumar K.V7061eba2008-07-11 19:27:31 -04002017{
2018 struct ext4_allocation_request ar;
2019 ext4_fsblk_t ret;
2020
2021 if (!test_opt(inode->i_sb, MBALLOC)) {
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002022 return ext4_old_new_blocks(handle, inode, goal, count, errp);
Aneesh Kumar K.V7061eba2008-07-11 19:27:31 -04002023 }
2024
2025 memset(&ar, 0, sizeof(ar));
2026 /* Fill with neighbour allocated blocks */
Aneesh Kumar K.V7061eba2008-07-11 19:27:31 -04002027
2028 ar.inode = inode;
2029 ar.goal = goal;
2030 ar.len = *count;
2031 ar.logical = iblock;
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002032
2033 if (S_ISREG(inode->i_mode) && !(flags & EXT4_META_BLOCK))
2034 /* enable in-core preallocation for data block allocation */
Aneesh Kumar K.V7061eba2008-07-11 19:27:31 -04002035 ar.flags = EXT4_MB_HINT_DATA;
2036 else
2037 /* disable in-core preallocation for non-regular files */
2038 ar.flags = 0;
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002039
Aneesh Kumar K.V7061eba2008-07-11 19:27:31 -04002040 ret = ext4_mb_new_blocks(handle, &ar, errp);
2041 *count = ar.len;
2042 return ret;
2043}
2044
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002045/*
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002046 * ext4_new_meta_blocks() -- allocate block for meta data (indexing) blocks
2047 *
2048 * @handle: handle to this transaction
2049 * @inode: file inode
2050 * @goal: given target block(filesystem wide)
2051 * @count: total number of blocks need
2052 * @errp: error code
2053 *
2054 * Return 1st allocated block numberon success, *count stores total account
2055 * error stores in errp pointer
2056 */
2057ext4_fsblk_t ext4_new_meta_blocks(handle_t *handle, struct inode *inode,
2058 ext4_fsblk_t goal, unsigned long *count, int *errp)
2059{
Mingming Caod2a17632008-07-14 17:52:37 -04002060 ext4_fsblk_t ret;
2061 ret = do_blk_alloc(handle, inode, 0, goal,
2062 count, errp, EXT4_META_BLOCK);
2063 /*
2064 * Account for the allocated meta blocks
2065 */
Aneesh Kumar K.V166348d2008-09-08 23:08:40 -04002066 if (!(*errp) && EXT4_I(inode)->i_delalloc_reserved_flag) {
Mingming Caod2a17632008-07-14 17:52:37 -04002067 spin_lock(&EXT4_I(inode)->i_block_reservation_lock);
2068 EXT4_I(inode)->i_allocated_meta_blocks += *count;
2069 spin_unlock(&EXT4_I(inode)->i_block_reservation_lock);
2070 }
2071 return ret;
2072}
2073
2074/*
2075 * ext4_new_meta_block() -- allocate block for meta data (indexing) blocks
2076 *
2077 * @handle: handle to this transaction
2078 * @inode: file inode
2079 * @goal: given target block(filesystem wide)
2080 * @errp: error code
2081 *
2082 * Return allocated block number on success
2083 */
2084ext4_fsblk_t ext4_new_meta_block(handle_t *handle, struct inode *inode,
2085 ext4_fsblk_t goal, int *errp)
2086{
2087 unsigned long count = 1;
2088 return ext4_new_meta_blocks(handle, inode, goal, &count, errp);
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -04002089}
2090
2091/*
2092 * ext4_new_blocks() -- allocate data blocks
2093 *
2094 * @handle: handle to this transaction
2095 * @inode: file inode
2096 * @goal: given target block(filesystem wide)
2097 * @count: total number of blocks need
2098 * @errp: error code
2099 *
2100 * Return 1st allocated block numberon success, *count stores total account
2101 * error stores in errp pointer
2102 */
2103
2104ext4_fsblk_t ext4_new_blocks(handle_t *handle, struct inode *inode,
2105 ext4_lblk_t iblock, ext4_fsblk_t goal,
2106 unsigned long *count, int *errp)
2107{
2108 return do_blk_alloc(handle, inode, iblock, goal, count, errp, 0);
2109}
Alex Tomasc9de5602008-01-29 00:19:52 -05002110
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002111/**
Mingming Cao617ba132006-10-11 01:20:53 -07002112 * ext4_count_free_blocks() -- count filesystem free blocks
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002113 * @sb: superblock
2114 *
2115 * Adds up the number of free blocks from each block group.
2116 */
Mingming Cao617ba132006-10-11 01:20:53 -07002117ext4_fsblk_t ext4_count_free_blocks(struct super_block *sb)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002118{
Mingming Cao617ba132006-10-11 01:20:53 -07002119 ext4_fsblk_t desc_count;
2120 struct ext4_group_desc *gdp;
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002121 ext4_group_t i;
2122 ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
Mingming Cao617ba132006-10-11 01:20:53 -07002123#ifdef EXT4FS_DEBUG
2124 struct ext4_super_block *es;
2125 ext4_fsblk_t bitmap_count;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002126 unsigned long x;
2127 struct buffer_head *bitmap_bh = NULL;
2128
Mingming Cao617ba132006-10-11 01:20:53 -07002129 es = EXT4_SB(sb)->s_es;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002130 desc_count = 0;
2131 bitmap_count = 0;
2132 gdp = NULL;
2133
2134 smp_rmb();
2135 for (i = 0; i < ngroups; i++) {
Mingming Cao617ba132006-10-11 01:20:53 -07002136 gdp = ext4_get_group_desc(sb, i, NULL);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002137 if (!gdp)
2138 continue;
2139 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
2140 brelse(bitmap_bh);
Theodore Ts'o574ca172008-07-11 19:27:31 -04002141 bitmap_bh = ext4_read_block_bitmap(sb, i);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002142 if (bitmap_bh == NULL)
2143 continue;
2144
Mingming Cao617ba132006-10-11 01:20:53 -07002145 x = ext4_count_free(bitmap_bh, sb->s_blocksize);
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002146 printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002147 i, le16_to_cpu(gdp->bg_free_blocks_count), x);
2148 bitmap_count += x;
2149 }
2150 brelse(bitmap_bh);
Theodore Ts'o4776004f2008-09-08 23:00:52 -04002151 printk(KERN_DEBUG "ext4_count_free_blocks: stored = %llu"
2152 ", computed = %llu, %llu\n", ext4_free_blocks_count(es),
2153 desc_count, bitmap_count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002154 return bitmap_count;
2155#else
2156 desc_count = 0;
2157 smp_rmb();
2158 for (i = 0; i < ngroups; i++) {
Mingming Cao617ba132006-10-11 01:20:53 -07002159 gdp = ext4_get_group_desc(sb, i, NULL);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002160 if (!gdp)
2161 continue;
2162 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
2163 }
2164
2165 return desc_count;
2166#endif
2167}
2168
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002169static inline int test_root(ext4_group_t a, int b)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002170{
2171 int num = b;
2172
2173 while (a > num)
2174 num *= b;
2175 return num == a;
2176}
2177
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002178static int ext4_group_sparse(ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002179{
2180 if (group <= 1)
2181 return 1;
2182 if (!(group & 1))
2183 return 0;
2184 return (test_root(group, 7) || test_root(group, 5) ||
2185 test_root(group, 3));
2186}
2187
2188/**
Mingming Cao617ba132006-10-11 01:20:53 -07002189 * ext4_bg_has_super - number of blocks used by the superblock in group
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002190 * @sb: superblock for filesystem
2191 * @group: group number to check
2192 *
2193 * Return the number of blocks used by the superblock (primary or backup)
2194 * in this group. Currently this will be only 0 or 1.
2195 */
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002196int ext4_bg_has_super(struct super_block *sb, ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002197{
Mingming Cao617ba132006-10-11 01:20:53 -07002198 if (EXT4_HAS_RO_COMPAT_FEATURE(sb,
2199 EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER) &&
2200 !ext4_group_sparse(group))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002201 return 0;
2202 return 1;
2203}
2204
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002205static unsigned long ext4_bg_num_gdb_meta(struct super_block *sb,
2206 ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002207{
Mingming Cao617ba132006-10-11 01:20:53 -07002208 unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002209 ext4_group_t first = metagroup * EXT4_DESC_PER_BLOCK(sb);
2210 ext4_group_t last = first + EXT4_DESC_PER_BLOCK(sb) - 1;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002211
2212 if (group == first || group == first + 1 || group == last)
2213 return 1;
2214 return 0;
2215}
2216
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002217static unsigned long ext4_bg_num_gdb_nometa(struct super_block *sb,
2218 ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002219{
Akinobu Mita859cb932008-02-06 01:40:17 -08002220 return ext4_bg_has_super(sb, group) ? EXT4_SB(sb)->s_gdb_count : 0;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002221}
2222
2223/**
Mingming Cao617ba132006-10-11 01:20:53 -07002224 * ext4_bg_num_gdb - number of blocks used by the group table in group
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002225 * @sb: superblock for filesystem
2226 * @group: group number to check
2227 *
2228 * Return the number of blocks used by the group descriptor table
2229 * (primary or backup) in this group. In the future there may be a
2230 * different number of descriptor blocks in each group.
2231 */
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002232unsigned long ext4_bg_num_gdb(struct super_block *sb, ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002233{
2234 unsigned long first_meta_bg =
Mingming Cao617ba132006-10-11 01:20:53 -07002235 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_meta_bg);
2236 unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002237
Mingming Cao617ba132006-10-11 01:20:53 -07002238 if (!EXT4_HAS_INCOMPAT_FEATURE(sb,EXT4_FEATURE_INCOMPAT_META_BG) ||
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002239 metagroup < first_meta_bg)
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04002240 return ext4_bg_num_gdb_nometa(sb, group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002241
Mingming Cao617ba132006-10-11 01:20:53 -07002242 return ext4_bg_num_gdb_meta(sb,group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002243
2244}