blob: 1327ac3a04de15fcfc92a0acaaf1d810b4524b58 [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) -
135 (EXT4_BLOCKS_PER_GROUP(sb) * (sbi->s_groups_count -1));
136 } 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 */
Mingming Cao617ba132006-10-11 01:20:53 -0700203struct ext4_group_desc * ext4_get_group_desc(struct super_block * sb,
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500204 ext4_group_t block_group,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700205 struct buffer_head ** bh)
206{
207 unsigned long group_desc;
208 unsigned long offset;
Mingming Cao617ba132006-10-11 01:20:53 -0700209 struct ext4_group_desc * desc;
210 struct ext4_sb_info *sbi = EXT4_SB(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700211
212 if (block_group >= sbi->s_groups_count) {
Mingming Cao617ba132006-10-11 01:20:53 -0700213 ext4_error (sb, "ext4_get_group_desc",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700214 "block_group >= groups_count - "
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500215 "block_group = %lu, groups_count = %lu",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700216 block_group, sbi->s_groups_count);
217
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]) {
Mingming Cao617ba132006-10-11 01:20:53 -0700225 ext4_error (sb, "ext4_get_group_desc",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700226 "Group descriptor not loaded - "
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500227 "block_group = %lu, group_desc = %lu, desc = %lu",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700228 block_group, group_desc, offset);
229 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{
Mingming Cao617ba132006-10-11 01:20:53 -0700305 struct ext4_group_desc * desc;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700306 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 - "
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500317 "block_group = %d, block_bitmap = %llu",
318 (int)block_group, (unsigned long long)bitmap_blk);
319 return NULL;
320 }
321 if (bh_uptodate_or_lock(bh))
322 return bh;
323
324 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
325 ext4_init_block_bitmap(sb, bh, block_group, desc);
326 set_buffer_uptodate(bh);
327 unlock_buffer(bh);
328 return bh;
329 }
330 if (bh_submit_read(bh) < 0) {
331 put_bh(bh);
Harvey Harrison46e665e2008-04-17 10:38:59 -0400332 ext4_error(sb, __func__,
Aneesh Kumar K.Vabcb2942008-01-28 23:58:27 -0500333 "Cannot read block bitmap - "
334 "block_group = %d, block_bitmap = %llu",
335 (int)block_group, (unsigned long long)bitmap_blk);
336 return NULL;
337 }
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -0400338 ext4_valid_block_bitmap(sb, desc, block_group, bh);
339 /*
340 * file system mounted not to panic on error,
341 * continue with corrupt bitmap
342 */
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700343 return bh;
344}
345/*
346 * The reservation window structure operations
347 * --------------------------------------------
348 * Operations include:
349 * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
350 *
351 * We use a red-black tree to represent per-filesystem reservation
352 * windows.
353 *
354 */
355
356/**
357 * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
358 * @rb_root: root of per-filesystem reservation rb tree
359 * @verbose: verbose mode
360 * @fn: function which wishes to dump the reservation map
361 *
362 * If verbose is turned on, it will print the whole block reservation
363 * windows(start, end). Otherwise, it will only print out the "bad" windows,
364 * those windows that overlap with their immediate neighbors.
365 */
366#if 1
367static void __rsv_window_dump(struct rb_root *root, int verbose,
368 const char *fn)
369{
370 struct rb_node *n;
Mingming Cao617ba132006-10-11 01:20:53 -0700371 struct ext4_reserve_window_node *rsv, *prev;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700372 int bad;
373
374restart:
375 n = rb_first(root);
376 bad = 0;
377 prev = NULL;
378
379 printk("Block Allocation Reservation Windows Map (%s):\n", fn);
380 while (n) {
Hugh Dickinsb78a6572006-12-06 20:39:21 -0800381 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700382 if (verbose)
383 printk("reservation window 0x%p "
Mingming Cao2ae02102006-10-11 01:21:11 -0700384 "start: %llu, end: %llu\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700385 rsv, rsv->rsv_start, rsv->rsv_end);
386 if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
387 printk("Bad reservation %p (start >= end)\n",
388 rsv);
389 bad = 1;
390 }
391 if (prev && prev->rsv_end >= rsv->rsv_start) {
392 printk("Bad reservation %p (prev->end >= start)\n",
393 rsv);
394 bad = 1;
395 }
396 if (bad) {
397 if (!verbose) {
398 printk("Restarting reservation walk in verbose mode\n");
399 verbose = 1;
400 goto restart;
401 }
402 }
403 n = rb_next(n);
404 prev = rsv;
405 }
406 printk("Window map complete.\n");
Julia Lawall07d45f12008-07-11 19:27:31 -0400407 BUG_ON(bad);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700408}
409#define rsv_window_dump(root, verbose) \
Harvey Harrison46e665e2008-04-17 10:38:59 -0400410 __rsv_window_dump((root), (verbose), __func__)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700411#else
412#define rsv_window_dump(root, verbose) do {} while (0)
413#endif
414
415/**
416 * goal_in_my_reservation()
417 * @rsv: inode's reservation window
418 * @grp_goal: given goal block relative to the allocation block group
419 * @group: the current allocation block group
420 * @sb: filesystem super block
421 *
422 * Test if the given goal block (group relative) is within the file's
423 * own block reservation window range.
424 *
425 * If the reservation window is outside the goal allocation group, return 0;
426 * grp_goal (given goal block) could be -1, which means no specific
427 * goal block. In this case, always return 1.
428 * If the goal block is within the reservation window, return 1;
429 * otherwise, return 0;
430 */
431static int
Mingming Cao617ba132006-10-11 01:20:53 -0700432goal_in_my_reservation(struct ext4_reserve_window *rsv, ext4_grpblk_t grp_goal,
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500433 ext4_group_t group, struct super_block *sb)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700434{
Mingming Cao617ba132006-10-11 01:20:53 -0700435 ext4_fsblk_t group_first_block, group_last_block;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700436
Mingming Cao617ba132006-10-11 01:20:53 -0700437 group_first_block = ext4_group_first_block_no(sb, group);
438 group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700439
440 if ((rsv->_rsv_start > group_last_block) ||
441 (rsv->_rsv_end < group_first_block))
442 return 0;
443 if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)
444 || (grp_goal + group_first_block > rsv->_rsv_end)))
445 return 0;
446 return 1;
447}
448
449/**
450 * search_reserve_window()
451 * @rb_root: root of reservation tree
452 * @goal: target allocation block
453 *
454 * Find the reserved window which includes the goal, or the previous one
455 * if the goal is not in any window.
456 * Returns NULL if there are no windows or if all windows start after the goal.
457 */
Mingming Cao617ba132006-10-11 01:20:53 -0700458static struct ext4_reserve_window_node *
459search_reserve_window(struct rb_root *root, ext4_fsblk_t goal)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700460{
461 struct rb_node *n = root->rb_node;
Mingming Cao617ba132006-10-11 01:20:53 -0700462 struct ext4_reserve_window_node *rsv;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700463
464 if (!n)
465 return NULL;
466
467 do {
Mingming Cao617ba132006-10-11 01:20:53 -0700468 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700469
470 if (goal < rsv->rsv_start)
471 n = n->rb_left;
472 else if (goal > rsv->rsv_end)
473 n = n->rb_right;
474 else
475 return rsv;
476 } while (n);
477 /*
478 * We've fallen off the end of the tree: the goal wasn't inside
479 * any particular node. OK, the previous node must be to one
480 * side of the interval containing the goal. If it's the RHS,
481 * we need to back up one.
482 */
483 if (rsv->rsv_start > goal) {
484 n = rb_prev(&rsv->rsv_node);
Mingming Cao617ba132006-10-11 01:20:53 -0700485 rsv = rb_entry(n, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700486 }
487 return rsv;
488}
489
490/**
Mingming Cao617ba132006-10-11 01:20:53 -0700491 * ext4_rsv_window_add() -- Insert a window to the block reservation rb tree.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700492 * @sb: super block
493 * @rsv: reservation window to add
494 *
495 * Must be called with rsv_lock hold.
496 */
Mingming Cao617ba132006-10-11 01:20:53 -0700497void ext4_rsv_window_add(struct super_block *sb,
498 struct ext4_reserve_window_node *rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700499{
Mingming Cao617ba132006-10-11 01:20:53 -0700500 struct rb_root *root = &EXT4_SB(sb)->s_rsv_window_root;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700501 struct rb_node *node = &rsv->rsv_node;
Mingming Cao617ba132006-10-11 01:20:53 -0700502 ext4_fsblk_t start = rsv->rsv_start;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700503
504 struct rb_node ** p = &root->rb_node;
505 struct rb_node * parent = NULL;
Mingming Cao617ba132006-10-11 01:20:53 -0700506 struct ext4_reserve_window_node *this;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700507
508 while (*p)
509 {
510 parent = *p;
Mingming Cao617ba132006-10-11 01:20:53 -0700511 this = rb_entry(parent, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700512
513 if (start < this->rsv_start)
514 p = &(*p)->rb_left;
515 else if (start > this->rsv_end)
516 p = &(*p)->rb_right;
517 else {
518 rsv_window_dump(root, 1);
519 BUG();
520 }
521 }
522
523 rb_link_node(node, parent, p);
524 rb_insert_color(node, root);
525}
526
527/**
Mingming Cao617ba132006-10-11 01:20:53 -0700528 * ext4_rsv_window_remove() -- unlink a window from the reservation rb tree
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700529 * @sb: super block
530 * @rsv: reservation window to remove
531 *
532 * Mark the block reservation window as not allocated, and unlink it
533 * from the filesystem reservation window rb tree. Must be called with
534 * rsv_lock hold.
535 */
536static void rsv_window_remove(struct super_block *sb,
Mingming Cao617ba132006-10-11 01:20:53 -0700537 struct ext4_reserve_window_node *rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700538{
Mingming Cao617ba132006-10-11 01:20:53 -0700539 rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
540 rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700541 rsv->rsv_alloc_hit = 0;
Mingming Cao617ba132006-10-11 01:20:53 -0700542 rb_erase(&rsv->rsv_node, &EXT4_SB(sb)->s_rsv_window_root);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700543}
544
545/*
546 * rsv_is_empty() -- Check if the reservation window is allocated.
547 * @rsv: given reservation window to check
548 *
Mingming Cao617ba132006-10-11 01:20:53 -0700549 * returns 1 if the end block is EXT4_RESERVE_WINDOW_NOT_ALLOCATED.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700550 */
Mingming Cao617ba132006-10-11 01:20:53 -0700551static inline int rsv_is_empty(struct ext4_reserve_window *rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700552{
553 /* a valid reservation end block could not be 0 */
Mingming Cao617ba132006-10-11 01:20:53 -0700554 return rsv->_rsv_end == EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700555}
556
557/**
Mingming Cao617ba132006-10-11 01:20:53 -0700558 * ext4_init_block_alloc_info()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700559 * @inode: file inode structure
560 *
561 * Allocate and initialize the reservation window structure, and
Mingming Cao617ba132006-10-11 01:20:53 -0700562 * link the window to the ext4 inode structure at last
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700563 *
564 * The reservation window structure is only dynamically allocated
Mingming Cao617ba132006-10-11 01:20:53 -0700565 * and linked to ext4 inode the first time the open file
566 * needs a new block. So, before every ext4_new_block(s) call, for
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700567 * regular files, we should check whether the reservation window
568 * structure exists or not. In the latter case, this function is called.
569 * Fail to do so will result in block reservation being turned off for that
570 * open file.
571 *
Mingming Cao617ba132006-10-11 01:20:53 -0700572 * This function is called from ext4_get_blocks_handle(), also called
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700573 * when setting the reservation window size through ioctl before the file
574 * is open for write (needs block allocation).
575 *
Aneesh Kumar K.V0e855ac2008-01-28 23:58:26 -0500576 * Needs down_write(i_data_sem) protection prior to call this function.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700577 */
Mingming Cao617ba132006-10-11 01:20:53 -0700578void ext4_init_block_alloc_info(struct inode *inode)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700579{
Mingming Cao617ba132006-10-11 01:20:53 -0700580 struct ext4_inode_info *ei = EXT4_I(inode);
581 struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700582 struct super_block *sb = inode->i_sb;
583
584 block_i = kmalloc(sizeof(*block_i), GFP_NOFS);
585 if (block_i) {
Mingming Cao617ba132006-10-11 01:20:53 -0700586 struct ext4_reserve_window_node *rsv = &block_i->rsv_window_node;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700587
Mingming Cao617ba132006-10-11 01:20:53 -0700588 rsv->rsv_start = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
589 rsv->rsv_end = EXT4_RESERVE_WINDOW_NOT_ALLOCATED;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700590
591 /*
592 * if filesystem is mounted with NORESERVATION, the goal
593 * reservation window size is set to zero to indicate
594 * block reservation is off
595 */
596 if (!test_opt(sb, RESERVATION))
597 rsv->rsv_goal_size = 0;
598 else
Mingming Cao617ba132006-10-11 01:20:53 -0700599 rsv->rsv_goal_size = EXT4_DEFAULT_RESERVE_BLOCKS;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700600 rsv->rsv_alloc_hit = 0;
601 block_i->last_alloc_logical_block = 0;
602 block_i->last_alloc_physical_block = 0;
603 }
604 ei->i_block_alloc_info = block_i;
605}
606
607/**
Mingming Cao617ba132006-10-11 01:20:53 -0700608 * ext4_discard_reservation()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700609 * @inode: inode
610 *
611 * Discard(free) block reservation window on last file close, or truncate
612 * or at last iput().
613 *
614 * It is being called in three cases:
Mingming Cao617ba132006-10-11 01:20:53 -0700615 * ext4_release_file(): last writer close the file
616 * ext4_clear_inode(): last iput(), when nobody link to this file.
617 * ext4_truncate(): when the block indirect map is about to change.
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700618 *
619 */
Mingming Cao617ba132006-10-11 01:20:53 -0700620void ext4_discard_reservation(struct inode *inode)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700621{
Mingming Cao617ba132006-10-11 01:20:53 -0700622 struct ext4_inode_info *ei = EXT4_I(inode);
623 struct ext4_block_alloc_info *block_i = ei->i_block_alloc_info;
624 struct ext4_reserve_window_node *rsv;
625 spinlock_t *rsv_lock = &EXT4_SB(inode->i_sb)->s_rsv_window_lock;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700626
Alex Tomasc9de5602008-01-29 00:19:52 -0500627 ext4_mb_discard_inode_preallocations(inode);
628
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700629 if (!block_i)
630 return;
631
632 rsv = &block_i->rsv_window_node;
633 if (!rsv_is_empty(&rsv->rsv_window)) {
634 spin_lock(rsv_lock);
635 if (!rsv_is_empty(&rsv->rsv_window))
636 rsv_window_remove(inode->i_sb, rsv);
637 spin_unlock(rsv_lock);
638 }
639}
640
641/**
Mingming Cao617ba132006-10-11 01:20:53 -0700642 * ext4_free_blocks_sb() -- Free given blocks and update quota
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700643 * @handle: handle to this transaction
644 * @sb: super block
645 * @block: start physcial block to free
646 * @count: number of blocks to free
647 * @pdquot_freed_blocks: pointer to quota
648 */
Mingming Cao617ba132006-10-11 01:20:53 -0700649void ext4_free_blocks_sb(handle_t *handle, struct super_block *sb,
650 ext4_fsblk_t block, unsigned long count,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700651 unsigned long *pdquot_freed_blocks)
652{
653 struct buffer_head *bitmap_bh = NULL;
654 struct buffer_head *gd_bh;
Avantika Mathurfd2d4292008-01-28 23:58:27 -0500655 ext4_group_t block_group;
Mingming Cao617ba132006-10-11 01:20:53 -0700656 ext4_grpblk_t bit;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700657 unsigned long i;
658 unsigned long overflow;
Mingming Cao617ba132006-10-11 01:20:53 -0700659 struct ext4_group_desc * desc;
660 struct ext4_super_block * es;
661 struct ext4_sb_info *sbi;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700662 int err = 0, ret;
Mingming Cao617ba132006-10-11 01:20:53 -0700663 ext4_grpblk_t group_freed;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700664
665 *pdquot_freed_blocks = 0;
Mingming Cao617ba132006-10-11 01:20:53 -0700666 sbi = EXT4_SB(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700667 es = sbi->s_es;
668 if (block < le32_to_cpu(es->s_first_data_block) ||
669 block + count < block ||
Laurent Vivierbd81d8e2006-10-11 01:21:10 -0700670 block + count > ext4_blocks_count(es)) {
Mingming Cao617ba132006-10-11 01:20:53 -0700671 ext4_error (sb, "ext4_free_blocks",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700672 "Freeing blocks not in datazone - "
Mingming Cao2ae02102006-10-11 01:21:11 -0700673 "block = %llu, count = %lu", block, count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700674 goto error_return;
675 }
676
Laurent Vivierbd81d8e2006-10-11 01:21:10 -0700677 ext4_debug ("freeing block(s) %llu-%llu\n", block, block + count - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700678
679do_more:
680 overflow = 0;
Mingming Cao3a5b2ec2006-10-11 01:21:05 -0700681 ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700682 /*
683 * Check to see if we are freeing blocks across a group
684 * boundary.
685 */
Mingming Cao617ba132006-10-11 01:20:53 -0700686 if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
687 overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700688 count -= overflow;
689 }
690 brelse(bitmap_bh);
Theodore Ts'o574ca172008-07-11 19:27:31 -0400691 bitmap_bh = ext4_read_block_bitmap(sb, block_group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700692 if (!bitmap_bh)
693 goto error_return;
Mingming Cao617ba132006-10-11 01:20:53 -0700694 desc = ext4_get_group_desc (sb, block_group, &gd_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700695 if (!desc)
696 goto error_return;
697
Alexandre Ratchov8fadc142006-10-11 01:21:15 -0700698 if (in_range(ext4_block_bitmap(sb, desc), block, count) ||
699 in_range(ext4_inode_bitmap(sb, desc), block, count) ||
700 in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||
701 in_range(block + count - 1, ext4_inode_table(sb, desc),
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -0500702 sbi->s_itb_per_group)) {
Mingming Cao617ba132006-10-11 01:20:53 -0700703 ext4_error (sb, "ext4_free_blocks",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700704 "Freeing blocks in system zones - "
Mingming Cao2ae02102006-10-11 01:21:11 -0700705 "Block = %llu, count = %lu",
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700706 block, count);
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -0500707 goto error_return;
708 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700709
710 /*
711 * We are about to start releasing blocks in the bitmap,
712 * so we need undo access.
713 */
714 /* @@@ check errors */
715 BUFFER_TRACE(bitmap_bh, "getting undo access");
Mingming Cao617ba132006-10-11 01:20:53 -0700716 err = ext4_journal_get_undo_access(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700717 if (err)
718 goto error_return;
719
720 /*
721 * We are about to modify some metadata. Call the journal APIs
722 * to unshare ->b_data if a currently-committing transaction is
723 * using it
724 */
725 BUFFER_TRACE(gd_bh, "get_write_access");
Mingming Cao617ba132006-10-11 01:20:53 -0700726 err = ext4_journal_get_write_access(handle, gd_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700727 if (err)
728 goto error_return;
729
730 jbd_lock_bh_state(bitmap_bh);
731
732 for (i = 0, group_freed = 0; i < count; i++) {
733 /*
734 * An HJ special. This is expensive...
735 */
Jose R. Santose23291b2007-07-18 08:57:06 -0400736#ifdef CONFIG_JBD2_DEBUG
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700737 jbd_unlock_bh_state(bitmap_bh);
738 {
739 struct buffer_head *debug_bh;
740 debug_bh = sb_find_get_block(sb, block + i);
741 if (debug_bh) {
742 BUFFER_TRACE(debug_bh, "Deleted!");
743 if (!bh2jh(bitmap_bh)->b_committed_data)
744 BUFFER_TRACE(debug_bh,
745 "No commited data in bitmap");
746 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap");
747 __brelse(debug_bh);
748 }
749 }
750 jbd_lock_bh_state(bitmap_bh);
751#endif
752 if (need_resched()) {
753 jbd_unlock_bh_state(bitmap_bh);
754 cond_resched();
755 jbd_lock_bh_state(bitmap_bh);
756 }
757 /* @@@ This prevents newly-allocated data from being
758 * freed and then reallocated within the same
759 * transaction.
760 *
761 * Ideally we would want to allow that to happen, but to
Mingming Caodab291a2006-10-11 01:21:01 -0700762 * do so requires making jbd2_journal_forget() capable of
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700763 * revoking the queued write of a data block, which
764 * implies blocking on the journal lock. *forget()
765 * cannot block due to truncate races.
766 *
Mingming Caodab291a2006-10-11 01:21:01 -0700767 * Eventually we can fix this by making jbd2_journal_forget()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700768 * return a status indicating whether or not it was able
769 * to revoke the buffer. On successful revoke, it is
770 * safe not to set the allocation bit in the committed
771 * bitmap, because we know that there is no outstanding
772 * activity on the buffer any more and so it is safe to
773 * reallocate it.
774 */
775 BUFFER_TRACE(bitmap_bh, "set in b_committed_data");
776 J_ASSERT_BH(bitmap_bh,
777 bh2jh(bitmap_bh)->b_committed_data != NULL);
Mingming Cao617ba132006-10-11 01:20:53 -0700778 ext4_set_bit_atomic(sb_bgl_lock(sbi, block_group), bit + i,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700779 bh2jh(bitmap_bh)->b_committed_data);
780
781 /*
782 * We clear the bit in the bitmap after setting the committed
783 * data bit, because this is the reverse order to that which
784 * the allocator uses.
785 */
786 BUFFER_TRACE(bitmap_bh, "clear bit");
Mingming Cao617ba132006-10-11 01:20:53 -0700787 if (!ext4_clear_bit_atomic(sb_bgl_lock(sbi, block_group),
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700788 bit + i, bitmap_bh->b_data)) {
789 jbd_unlock_bh_state(bitmap_bh);
Harvey Harrison46e665e2008-04-17 10:38:59 -0400790 ext4_error(sb, __func__,
Mingming Cao2ae02102006-10-11 01:21:11 -0700791 "bit already cleared for block %llu",
Laurent Vivierbd81d8e2006-10-11 01:21:10 -0700792 (ext4_fsblk_t)(block + i));
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700793 jbd_lock_bh_state(bitmap_bh);
794 BUFFER_TRACE(bitmap_bh, "bit already cleared");
795 } else {
796 group_freed++;
797 }
798 }
799 jbd_unlock_bh_state(bitmap_bh);
800
801 spin_lock(sb_bgl_lock(sbi, block_group));
Marcin Slusarze8546d02008-04-17 10:38:59 -0400802 le16_add_cpu(&desc->bg_free_blocks_count, group_freed);
Andreas Dilger717d50e2007-10-16 18:38:25 -0400803 desc->bg_checksum = ext4_group_desc_csum(sbi, block_group, desc);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700804 spin_unlock(sb_bgl_lock(sbi, block_group));
Peter Zijlstraaa0dff22007-10-16 23:25:42 -0700805 percpu_counter_add(&sbi->s_freeblocks_counter, count);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700806
Jose R. Santos772cb7c2008-07-11 19:27:31 -0400807 if (sbi->s_log_groups_per_flex) {
808 ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
809 spin_lock(sb_bgl_lock(sbi, flex_group));
810 sbi->s_flex_groups[flex_group].free_blocks += count;
811 spin_unlock(sb_bgl_lock(sbi, flex_group));
812 }
813
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700814 /* We dirtied the bitmap block */
815 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
Mingming Cao617ba132006-10-11 01:20:53 -0700816 err = ext4_journal_dirty_metadata(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700817
818 /* And the group descriptor block */
819 BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
Mingming Cao617ba132006-10-11 01:20:53 -0700820 ret = ext4_journal_dirty_metadata(handle, gd_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700821 if (!err) err = ret;
822 *pdquot_freed_blocks += group_freed;
823
824 if (overflow && !err) {
825 block += count;
826 count = overflow;
827 goto do_more;
828 }
829 sb->s_dirt = 1;
830error_return:
831 brelse(bitmap_bh);
Mingming Cao617ba132006-10-11 01:20:53 -0700832 ext4_std_error(sb, err);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700833 return;
834}
835
836/**
Mingming Cao617ba132006-10-11 01:20:53 -0700837 * ext4_free_blocks() -- Free given blocks and update quota
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700838 * @handle: handle for this transaction
839 * @inode: inode
840 * @block: start physical block to free
841 * @count: number of blocks to count
Alex Tomasc9de5602008-01-29 00:19:52 -0500842 * @metadata: Are these metadata blocks
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700843 */
Mingming Cao617ba132006-10-11 01:20:53 -0700844void ext4_free_blocks(handle_t *handle, struct inode *inode,
Alex Tomasc9de5602008-01-29 00:19:52 -0500845 ext4_fsblk_t block, unsigned long count,
846 int metadata)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700847{
848 struct super_block * sb;
849 unsigned long dquot_freed_blocks;
850
Alex Tomasc9de5602008-01-29 00:19:52 -0500851 /* this isn't the right place to decide whether block is metadata
852 * inode.c/extents.c knows better, but for safety ... */
853 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
854 ext4_should_journal_data(inode))
855 metadata = 1;
856
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700857 sb = inode->i_sb;
Alex Tomasc9de5602008-01-29 00:19:52 -0500858
859 if (!test_opt(sb, MBALLOC) || !EXT4_SB(sb)->s_group_info)
860 ext4_free_blocks_sb(handle, sb, block, count,
861 &dquot_freed_blocks);
862 else
863 ext4_mb_free_blocks(handle, inode, block, count,
864 metadata, &dquot_freed_blocks);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700865 if (dquot_freed_blocks)
866 DQUOT_FREE_BLOCK(inode, dquot_freed_blocks);
867 return;
868}
869
870/**
Mingming Cao617ba132006-10-11 01:20:53 -0700871 * ext4_test_allocatable()
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700872 * @nr: given allocation block group
873 * @bh: bufferhead contains the bitmap of the given block group
874 *
Mingming Cao617ba132006-10-11 01:20:53 -0700875 * For ext4 allocations, we must not reuse any blocks which are
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700876 * allocated in the bitmap buffer's "last committed data" copy. This
877 * prevents deletes from freeing up the page for reuse until we have
878 * committed the delete transaction.
879 *
880 * If we didn't do this, then deleting something and reallocating it as
881 * data would allow the old block to be overwritten before the
882 * transaction committed (because we force data to disk before commit).
883 * This would lead to corruption if we crashed between overwriting the
884 * data and committing the delete.
885 *
886 * @@@ We may want to make this allocation behaviour conditional on
887 * data-writes at some point, and disable it for metadata allocations or
888 * sync-data inodes.
889 */
Mingming Cao617ba132006-10-11 01:20:53 -0700890static int ext4_test_allocatable(ext4_grpblk_t nr, struct buffer_head *bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700891{
892 int ret;
893 struct journal_head *jh = bh2jh(bh);
894
Mingming Cao617ba132006-10-11 01:20:53 -0700895 if (ext4_test_bit(nr, bh->b_data))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700896 return 0;
897
898 jbd_lock_bh_state(bh);
899 if (!jh->b_committed_data)
900 ret = 1;
901 else
Mingming Cao617ba132006-10-11 01:20:53 -0700902 ret = !ext4_test_bit(nr, jh->b_committed_data);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700903 jbd_unlock_bh_state(bh);
904 return ret;
905}
906
907/**
908 * bitmap_search_next_usable_block()
909 * @start: the starting block (group relative) of the search
910 * @bh: bufferhead contains the block group bitmap
911 * @maxblocks: the ending block (group relative) of the reservation
912 *
913 * The bitmap search --- search forward alternately through the actual
914 * bitmap on disk and the last-committed copy in journal, until we find a
915 * bit free in both bitmaps.
916 */
Mingming Cao617ba132006-10-11 01:20:53 -0700917static ext4_grpblk_t
918bitmap_search_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
919 ext4_grpblk_t maxblocks)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700920{
Mingming Cao617ba132006-10-11 01:20:53 -0700921 ext4_grpblk_t next;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700922 struct journal_head *jh = bh2jh(bh);
923
924 while (start < maxblocks) {
Mingming Cao617ba132006-10-11 01:20:53 -0700925 next = ext4_find_next_zero_bit(bh->b_data, maxblocks, start);
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700926 if (next >= maxblocks)
927 return -1;
Mingming Cao617ba132006-10-11 01:20:53 -0700928 if (ext4_test_allocatable(next, bh))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700929 return next;
930 jbd_lock_bh_state(bh);
931 if (jh->b_committed_data)
Mingming Cao617ba132006-10-11 01:20:53 -0700932 start = ext4_find_next_zero_bit(jh->b_committed_data,
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700933 maxblocks, next);
934 jbd_unlock_bh_state(bh);
935 }
936 return -1;
937}
938
939/**
940 * find_next_usable_block()
941 * @start: the starting block (group relative) to find next
942 * allocatable block in bitmap.
943 * @bh: bufferhead contains the block group bitmap
944 * @maxblocks: the ending block (group relative) for the search
945 *
946 * Find an allocatable block in a bitmap. We honor both the bitmap and
947 * its last-committed copy (if that exists), and perform the "most
948 * appropriate allocation" algorithm of looking for a free block near
949 * the initial goal; then for a free byte somewhere in the bitmap; then
950 * for any free bit in the bitmap.
951 */
Mingming Cao617ba132006-10-11 01:20:53 -0700952static ext4_grpblk_t
953find_next_usable_block(ext4_grpblk_t start, struct buffer_head *bh,
954 ext4_grpblk_t maxblocks)
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700955{
Mingming Cao617ba132006-10-11 01:20:53 -0700956 ext4_grpblk_t here, next;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700957 char *p, *r;
958
959 if (start > 0) {
960 /*
961 * The goal was occupied; search forward for a free
962 * block within the next XX blocks.
963 *
964 * end_goal is more or less random, but it has to be
Mingming Cao617ba132006-10-11 01:20:53 -0700965 * less than EXT4_BLOCKS_PER_GROUP. Aligning up to the
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700966 * next 64-bit boundary is simple..
967 */
Mingming Cao617ba132006-10-11 01:20:53 -0700968 ext4_grpblk_t end_goal = (start + 63) & ~63;
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700969 if (end_goal > maxblocks)
970 end_goal = maxblocks;
Mingming Cao617ba132006-10-11 01:20:53 -0700971 here = ext4_find_next_zero_bit(bh->b_data, end_goal, start);
972 if (here < end_goal && ext4_test_allocatable(here, bh))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700973 return here;
Mingming Cao617ba132006-10-11 01:20:53 -0700974 ext4_debug("Bit not found near goal\n");
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700975 }
976
977 here = start;
978 if (here < 0)
979 here = 0;
980
981 p = ((char *)bh->b_data) + (here >> 3);
Hugh Dickinsec0837f2006-12-06 20:39:26 -0800982 r = memscan(p, 0, ((maxblocks + 7) >> 3) - (here >> 3));
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700983 next = (r - ((char *)bh->b_data)) << 3;
984
Mingming Cao617ba132006-10-11 01:20:53 -0700985 if (next < maxblocks && next >= start && ext4_test_allocatable(next, bh))
Dave Kleikampac27a0e2006-10-11 01:20:50 -0700986 return next;
987
988 /*
989 * The bitmap search --- search forward alternately through the actual
990 * bitmap and the last-committed copy until we find a bit free in
991 * both
992 */
993 here = bitmap_search_next_usable_block(here, bh, maxblocks);
994 return here;
995}
996
997/**
998 * claim_block()
999 * @block: the free block (group relative) to allocate
1000 * @bh: the bufferhead containts the block group bitmap
1001 *
1002 * We think we can allocate this block in this bitmap. Try to set the bit.
1003 * If that succeeds then check that nobody has allocated and then freed the
1004 * block since we saw that is was not marked in b_committed_data. If it _was_
1005 * allocated and freed then clear the bit in the bitmap again and return
1006 * zero (failure).
1007 */
1008static inline int
Mingming Cao617ba132006-10-11 01:20:53 -07001009claim_block(spinlock_t *lock, ext4_grpblk_t block, struct buffer_head *bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001010{
1011 struct journal_head *jh = bh2jh(bh);
1012 int ret;
1013
Mingming Cao617ba132006-10-11 01:20:53 -07001014 if (ext4_set_bit_atomic(lock, block, bh->b_data))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001015 return 0;
1016 jbd_lock_bh_state(bh);
Mingming Cao617ba132006-10-11 01:20:53 -07001017 if (jh->b_committed_data && ext4_test_bit(block,jh->b_committed_data)) {
1018 ext4_clear_bit_atomic(lock, block, bh->b_data);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001019 ret = 0;
1020 } else {
1021 ret = 1;
1022 }
1023 jbd_unlock_bh_state(bh);
1024 return ret;
1025}
1026
1027/**
Mingming Cao617ba132006-10-11 01:20:53 -07001028 * ext4_try_to_allocate()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001029 * @sb: superblock
1030 * @handle: handle to this transaction
1031 * @group: given allocation block group
1032 * @bitmap_bh: bufferhead holds the block bitmap
1033 * @grp_goal: given target block within the group
1034 * @count: target number of blocks to allocate
1035 * @my_rsv: reservation window
1036 *
1037 * Attempt to allocate blocks within a give range. Set the range of allocation
1038 * first, then find the first free bit(s) from the bitmap (within the range),
1039 * and at last, allocate the blocks by claiming the found free bit as allocated.
1040 *
1041 * To set the range of this allocation:
1042 * if there is a reservation window, only try to allocate block(s) from the
1043 * file's own reservation window;
1044 * Otherwise, the allocation range starts from the give goal block, ends at
1045 * the block group's last block.
1046 *
1047 * If we failed to allocate the desired block then we may end up crossing to a
1048 * new bitmap. In that case we must release write access to the old one via
Mingming Cao617ba132006-10-11 01:20:53 -07001049 * ext4_journal_release_buffer(), else we'll run out of credits.
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001050 */
Mingming Cao617ba132006-10-11 01:20:53 -07001051static ext4_grpblk_t
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001052ext4_try_to_allocate(struct super_block *sb, handle_t *handle,
1053 ext4_group_t group, struct buffer_head *bitmap_bh,
1054 ext4_grpblk_t grp_goal, unsigned long *count,
1055 struct ext4_reserve_window *my_rsv)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001056{
Mingming Cao617ba132006-10-11 01:20:53 -07001057 ext4_fsblk_t group_first_block;
1058 ext4_grpblk_t start, end;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001059 unsigned long num = 0;
1060
1061 /* we do allocation within the reservation window if we have a window */
1062 if (my_rsv) {
Mingming Cao617ba132006-10-11 01:20:53 -07001063 group_first_block = ext4_group_first_block_no(sb, group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001064 if (my_rsv->_rsv_start >= group_first_block)
1065 start = my_rsv->_rsv_start - group_first_block;
1066 else
1067 /* reservation window cross group boundary */
1068 start = 0;
1069 end = my_rsv->_rsv_end - group_first_block + 1;
Mingming Cao617ba132006-10-11 01:20:53 -07001070 if (end > EXT4_BLOCKS_PER_GROUP(sb))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001071 /* reservation window crosses group boundary */
Mingming Cao617ba132006-10-11 01:20:53 -07001072 end = EXT4_BLOCKS_PER_GROUP(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001073 if ((start <= grp_goal) && (grp_goal < end))
1074 start = grp_goal;
1075 else
1076 grp_goal = -1;
1077 } else {
1078 if (grp_goal > 0)
1079 start = grp_goal;
1080 else
1081 start = 0;
Mingming Cao617ba132006-10-11 01:20:53 -07001082 end = EXT4_BLOCKS_PER_GROUP(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001083 }
1084
Mingming Cao617ba132006-10-11 01:20:53 -07001085 BUG_ON(start > EXT4_BLOCKS_PER_GROUP(sb));
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001086
1087repeat:
Mingming Cao617ba132006-10-11 01:20:53 -07001088 if (grp_goal < 0 || !ext4_test_allocatable(grp_goal, bitmap_bh)) {
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001089 grp_goal = find_next_usable_block(start, bitmap_bh, end);
1090 if (grp_goal < 0)
1091 goto fail_access;
1092 if (!my_rsv) {
1093 int i;
1094
1095 for (i = 0; i < 7 && grp_goal > start &&
Mingming Cao617ba132006-10-11 01:20:53 -07001096 ext4_test_allocatable(grp_goal - 1,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001097 bitmap_bh);
1098 i++, grp_goal--)
1099 ;
1100 }
1101 }
1102 start = grp_goal;
1103
Mingming Cao617ba132006-10-11 01:20:53 -07001104 if (!claim_block(sb_bgl_lock(EXT4_SB(sb), group),
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001105 grp_goal, bitmap_bh)) {
1106 /*
1107 * The block was allocated by another thread, or it was
1108 * allocated and then freed by another thread
1109 */
1110 start++;
1111 grp_goal++;
1112 if (start >= end)
1113 goto fail_access;
1114 goto repeat;
1115 }
1116 num++;
1117 grp_goal++;
1118 while (num < *count && grp_goal < end
Mingming Cao617ba132006-10-11 01:20:53 -07001119 && ext4_test_allocatable(grp_goal, bitmap_bh)
1120 && claim_block(sb_bgl_lock(EXT4_SB(sb), group),
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001121 grp_goal, bitmap_bh)) {
1122 num++;
1123 grp_goal++;
1124 }
1125 *count = num;
1126 return grp_goal - num;
1127fail_access:
1128 *count = num;
1129 return -1;
1130}
1131
1132/**
1133 * find_next_reservable_window():
1134 * find a reservable space within the given range.
1135 * It does not allocate the reservation window for now:
1136 * alloc_new_reservation() will do the work later.
1137 *
1138 * @search_head: the head of the searching list;
1139 * This is not necessarily the list head of the whole filesystem
1140 *
1141 * We have both head and start_block to assist the search
1142 * for the reservable space. The list starts from head,
1143 * but we will shift to the place where start_block is,
1144 * then start from there, when looking for a reservable space.
1145 *
1146 * @size: the target new reservation window size
1147 *
1148 * @group_first_block: the first block we consider to start
1149 * the real search from
1150 *
1151 * @last_block:
1152 * the maximum block number that our goal reservable space
1153 * could start from. This is normally the last block in this
1154 * group. The search will end when we found the start of next
1155 * possible reservable space is out of this boundary.
1156 * This could handle the cross boundary reservation window
1157 * request.
1158 *
1159 * basically we search from the given range, rather than the whole
1160 * reservation double linked list, (start_block, last_block)
1161 * to find a free region that is of my size and has not
1162 * been reserved.
1163 *
1164 */
1165static int find_next_reservable_window(
Mingming Cao617ba132006-10-11 01:20:53 -07001166 struct ext4_reserve_window_node *search_head,
1167 struct ext4_reserve_window_node *my_rsv,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001168 struct super_block * sb,
Mingming Cao617ba132006-10-11 01:20:53 -07001169 ext4_fsblk_t start_block,
1170 ext4_fsblk_t last_block)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001171{
1172 struct rb_node *next;
Mingming Cao617ba132006-10-11 01:20:53 -07001173 struct ext4_reserve_window_node *rsv, *prev;
1174 ext4_fsblk_t cur;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001175 int size = my_rsv->rsv_goal_size;
1176
1177 /* TODO: make the start of the reservation window byte-aligned */
1178 /* cur = *start_block & ~7;*/
1179 cur = start_block;
1180 rsv = search_head;
1181 if (!rsv)
1182 return -1;
1183
1184 while (1) {
1185 if (cur <= rsv->rsv_end)
1186 cur = rsv->rsv_end + 1;
1187
1188 /* TODO?
1189 * in the case we could not find a reservable space
1190 * that is what is expected, during the re-search, we could
1191 * remember what's the largest reservable space we could have
1192 * and return that one.
1193 *
1194 * For now it will fail if we could not find the reservable
1195 * space with expected-size (or more)...
1196 */
1197 if (cur > last_block)
1198 return -1; /* fail */
1199
1200 prev = rsv;
1201 next = rb_next(&rsv->rsv_node);
Hugh Dickinsb78a6572006-12-06 20:39:21 -08001202 rsv = rb_entry(next,struct ext4_reserve_window_node,rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001203
1204 /*
1205 * Reached the last reservation, we can just append to the
1206 * previous one.
1207 */
1208 if (!next)
1209 break;
1210
1211 if (cur + size <= rsv->rsv_start) {
1212 /*
1213 * Found a reserveable space big enough. We could
1214 * have a reservation across the group boundary here
1215 */
1216 break;
1217 }
1218 }
1219 /*
1220 * we come here either :
1221 * when we reach the end of the whole list,
1222 * and there is empty reservable space after last entry in the list.
1223 * append it to the end of the list.
1224 *
1225 * or we found one reservable space in the middle of the list,
1226 * return the reservation window that we could append to.
1227 * succeed.
1228 */
1229
1230 if ((prev != my_rsv) && (!rsv_is_empty(&my_rsv->rsv_window)))
1231 rsv_window_remove(sb, my_rsv);
1232
1233 /*
1234 * Let's book the whole avaliable window for now. We will check the
1235 * disk bitmap later and then, if there are free blocks then we adjust
1236 * the window size if it's larger than requested.
1237 * Otherwise, we will remove this node from the tree next time
1238 * call find_next_reservable_window.
1239 */
1240 my_rsv->rsv_start = cur;
1241 my_rsv->rsv_end = cur + size - 1;
1242 my_rsv->rsv_alloc_hit = 0;
1243
1244 if (prev != my_rsv)
Mingming Cao617ba132006-10-11 01:20:53 -07001245 ext4_rsv_window_add(sb, my_rsv);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001246
1247 return 0;
1248}
1249
1250/**
1251 * alloc_new_reservation()--allocate a new reservation window
1252 *
1253 * To make a new reservation, we search part of the filesystem
1254 * reservation list (the list that inside the group). We try to
1255 * allocate a new reservation window near the allocation goal,
1256 * or the beginning of the group, if there is no goal.
1257 *
1258 * We first find a reservable space after the goal, then from
1259 * there, we check the bitmap for the first free block after
1260 * it. If there is no free block until the end of group, then the
1261 * whole group is full, we failed. Otherwise, check if the free
1262 * block is inside the expected reservable space, if so, we
1263 * succeed.
1264 * If the first free block is outside the reservable space, then
1265 * start from the first free block, we search for next available
1266 * space, and go on.
1267 *
1268 * on succeed, a new reservation will be found and inserted into the list
1269 * It contains at least one free block, and it does not overlap with other
1270 * reservation windows.
1271 *
1272 * failed: we failed to find a reservation window in this group
1273 *
1274 * @rsv: the reservation
1275 *
1276 * @grp_goal: The goal (group-relative). It is where the search for a
1277 * free reservable space should start from.
1278 * if we have a grp_goal(grp_goal >0 ), then start from there,
1279 * no grp_goal(grp_goal = -1), we start from the first block
1280 * of the group.
1281 *
1282 * @sb: the super block
1283 * @group: the group we are trying to allocate in
1284 * @bitmap_bh: the block group block bitmap
1285 *
1286 */
Mingming Cao617ba132006-10-11 01:20:53 -07001287static int alloc_new_reservation(struct ext4_reserve_window_node *my_rsv,
1288 ext4_grpblk_t grp_goal, struct super_block *sb,
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001289 ext4_group_t group, struct buffer_head *bitmap_bh)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001290{
Mingming Cao617ba132006-10-11 01:20:53 -07001291 struct ext4_reserve_window_node *search_head;
1292 ext4_fsblk_t group_first_block, group_end_block, start_block;
1293 ext4_grpblk_t first_free_block;
1294 struct rb_root *fs_rsv_root = &EXT4_SB(sb)->s_rsv_window_root;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001295 unsigned long size;
1296 int ret;
Mingming Cao617ba132006-10-11 01:20:53 -07001297 spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001298
Mingming Cao617ba132006-10-11 01:20:53 -07001299 group_first_block = ext4_group_first_block_no(sb, group);
1300 group_end_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001301
1302 if (grp_goal < 0)
1303 start_block = group_first_block;
1304 else
1305 start_block = grp_goal + group_first_block;
1306
1307 size = my_rsv->rsv_goal_size;
1308
1309 if (!rsv_is_empty(&my_rsv->rsv_window)) {
1310 /*
1311 * if the old reservation is cross group boundary
1312 * and if the goal is inside the old reservation window,
1313 * we will come here when we just failed to allocate from
1314 * the first part of the window. We still have another part
1315 * that belongs to the next group. In this case, there is no
1316 * point to discard our window and try to allocate a new one
1317 * in this group(which will fail). we should
1318 * keep the reservation window, just simply move on.
1319 *
1320 * Maybe we could shift the start block of the reservation
1321 * window to the first block of next group.
1322 */
1323
1324 if ((my_rsv->rsv_start <= group_end_block) &&
1325 (my_rsv->rsv_end > group_end_block) &&
1326 (start_block >= my_rsv->rsv_start))
1327 return -1;
1328
1329 if ((my_rsv->rsv_alloc_hit >
1330 (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
1331 /*
1332 * if the previously allocation hit ratio is
1333 * greater than 1/2, then we double the size of
1334 * the reservation window the next time,
1335 * otherwise we keep the same size window
1336 */
1337 size = size * 2;
Mingming Cao617ba132006-10-11 01:20:53 -07001338 if (size > EXT4_MAX_RESERVE_BLOCKS)
1339 size = EXT4_MAX_RESERVE_BLOCKS;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001340 my_rsv->rsv_goal_size= size;
1341 }
1342 }
1343
1344 spin_lock(rsv_lock);
1345 /*
1346 * shift the search start to the window near the goal block
1347 */
1348 search_head = search_reserve_window(fs_rsv_root, start_block);
1349
1350 /*
1351 * find_next_reservable_window() simply finds a reservable window
1352 * inside the given range(start_block, group_end_block).
1353 *
1354 * To make sure the reservation window has a free bit inside it, we
1355 * need to check the bitmap after we found a reservable window.
1356 */
1357retry:
1358 ret = find_next_reservable_window(search_head, my_rsv, sb,
1359 start_block, group_end_block);
1360
1361 if (ret == -1) {
1362 if (!rsv_is_empty(&my_rsv->rsv_window))
1363 rsv_window_remove(sb, my_rsv);
1364 spin_unlock(rsv_lock);
1365 return -1;
1366 }
1367
1368 /*
1369 * On success, find_next_reservable_window() returns the
1370 * reservation window where there is a reservable space after it.
1371 * Before we reserve this reservable space, we need
1372 * to make sure there is at least a free block inside this region.
1373 *
1374 * searching the first free bit on the block bitmap and copy of
1375 * last committed bitmap alternatively, until we found a allocatable
1376 * block. Search start from the start block of the reservable space
1377 * we just found.
1378 */
1379 spin_unlock(rsv_lock);
1380 first_free_block = bitmap_search_next_usable_block(
1381 my_rsv->rsv_start - group_first_block,
1382 bitmap_bh, group_end_block - group_first_block + 1);
1383
1384 if (first_free_block < 0) {
1385 /*
1386 * no free block left on the bitmap, no point
1387 * to reserve the space. return failed.
1388 */
1389 spin_lock(rsv_lock);
1390 if (!rsv_is_empty(&my_rsv->rsv_window))
1391 rsv_window_remove(sb, my_rsv);
1392 spin_unlock(rsv_lock);
1393 return -1; /* failed */
1394 }
1395
1396 start_block = first_free_block + group_first_block;
1397 /*
1398 * check if the first free block is within the
1399 * free space we just reserved
1400 */
Hugh Dickinsb2f2c762006-12-06 20:39:20 -08001401 if (start_block >= my_rsv->rsv_start && start_block <= my_rsv->rsv_end)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001402 return 0; /* success */
1403 /*
1404 * if the first free bit we found is out of the reservable space
1405 * continue search for next reservable space,
1406 * start from where the free block is,
1407 * we also shift the list head to where we stopped last time
1408 */
1409 search_head = my_rsv;
1410 spin_lock(rsv_lock);
1411 goto retry;
1412}
1413
1414/**
1415 * try_to_extend_reservation()
1416 * @my_rsv: given reservation window
1417 * @sb: super block
1418 * @size: the delta to extend
1419 *
1420 * Attempt to expand the reservation window large enough to have
1421 * required number of free blocks
1422 *
Mingming Cao617ba132006-10-11 01:20:53 -07001423 * Since ext4_try_to_allocate() will always allocate blocks within
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001424 * the reservation window range, if the window size is too small,
1425 * multiple blocks allocation has to stop at the end of the reservation
1426 * window. To make this more efficient, given the total number of
1427 * blocks needed and the current size of the window, we try to
1428 * expand the reservation window size if necessary on a best-effort
Mingming Cao617ba132006-10-11 01:20:53 -07001429 * basis before ext4_new_blocks() tries to allocate blocks,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001430 */
Mingming Cao617ba132006-10-11 01:20:53 -07001431static void try_to_extend_reservation(struct ext4_reserve_window_node *my_rsv,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001432 struct super_block *sb, int size)
1433{
Mingming Cao617ba132006-10-11 01:20:53 -07001434 struct ext4_reserve_window_node *next_rsv;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001435 struct rb_node *next;
Mingming Cao617ba132006-10-11 01:20:53 -07001436 spinlock_t *rsv_lock = &EXT4_SB(sb)->s_rsv_window_lock;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001437
1438 if (!spin_trylock(rsv_lock))
1439 return;
1440
1441 next = rb_next(&my_rsv->rsv_node);
1442
1443 if (!next)
1444 my_rsv->rsv_end += size;
1445 else {
Hugh Dickinsb78a6572006-12-06 20:39:21 -08001446 next_rsv = rb_entry(next, struct ext4_reserve_window_node, rsv_node);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001447
1448 if ((next_rsv->rsv_start - my_rsv->rsv_end - 1) >= size)
1449 my_rsv->rsv_end += size;
1450 else
1451 my_rsv->rsv_end = next_rsv->rsv_start - 1;
1452 }
1453 spin_unlock(rsv_lock);
1454}
1455
1456/**
Mingming Cao617ba132006-10-11 01:20:53 -07001457 * ext4_try_to_allocate_with_rsv()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001458 * @sb: superblock
1459 * @handle: handle to this transaction
1460 * @group: given allocation block group
1461 * @bitmap_bh: bufferhead holds the block bitmap
1462 * @grp_goal: given target block within the group
1463 * @count: target number of blocks to allocate
1464 * @my_rsv: reservation window
1465 * @errp: pointer to store the error code
1466 *
1467 * This is the main function used to allocate a new block and its reservation
1468 * window.
1469 *
1470 * Each time when a new block allocation is need, first try to allocate from
1471 * its own reservation. If it does not have a reservation window, instead of
1472 * looking for a free bit on bitmap first, then look up the reservation list to
1473 * see if it is inside somebody else's reservation window, we try to allocate a
1474 * reservation window for it starting from the goal first. Then do the block
1475 * allocation within the reservation window.
1476 *
1477 * This will avoid keeping on searching the reservation list again and
1478 * again when somebody is looking for a free block (without
1479 * reservation), and there are lots of free blocks, but they are all
1480 * being reserved.
1481 *
1482 * We use a red-black tree for the per-filesystem reservation list.
1483 *
1484 */
Mingming Cao617ba132006-10-11 01:20:53 -07001485static ext4_grpblk_t
1486ext4_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001487 ext4_group_t group, struct buffer_head *bitmap_bh,
Mingming Cao617ba132006-10-11 01:20:53 -07001488 ext4_grpblk_t grp_goal,
1489 struct ext4_reserve_window_node * my_rsv,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001490 unsigned long *count, int *errp)
1491{
Mingming Cao617ba132006-10-11 01:20:53 -07001492 ext4_fsblk_t group_first_block, group_last_block;
1493 ext4_grpblk_t ret = 0;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001494 int fatal;
1495 unsigned long num = *count;
1496
1497 *errp = 0;
1498
1499 /*
1500 * Make sure we use undo access for the bitmap, because it is critical
1501 * that we do the frozen_data COW on bitmap buffers in all cases even
1502 * if the buffer is in BJ_Forget state in the committing transaction.
1503 */
1504 BUFFER_TRACE(bitmap_bh, "get undo access for new block");
Mingming Cao617ba132006-10-11 01:20:53 -07001505 fatal = ext4_journal_get_undo_access(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001506 if (fatal) {
1507 *errp = fatal;
1508 return -1;
1509 }
1510
1511 /*
1512 * we don't deal with reservation when
1513 * filesystem is mounted without reservation
1514 * or the file is not a regular file
1515 * or last attempt to allocate a block with reservation turned on failed
1516 */
1517 if (my_rsv == NULL ) {
Mingming Cao617ba132006-10-11 01:20:53 -07001518 ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001519 grp_goal, count, NULL);
1520 goto out;
1521 }
1522 /*
1523 * grp_goal is a group relative block number (if there is a goal)
Hugh Dickinse7dc95d2006-12-06 20:39:19 -08001524 * 0 <= grp_goal < EXT4_BLOCKS_PER_GROUP(sb)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001525 * first block is a filesystem wide block number
1526 * first block is the block number of the first block in this group
1527 */
Mingming Cao617ba132006-10-11 01:20:53 -07001528 group_first_block = ext4_group_first_block_no(sb, group);
1529 group_last_block = group_first_block + (EXT4_BLOCKS_PER_GROUP(sb) - 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001530
1531 /*
1532 * Basically we will allocate a new block from inode's reservation
1533 * window.
1534 *
1535 * We need to allocate a new reservation window, if:
1536 * a) inode does not have a reservation window; or
1537 * b) last attempt to allocate a block from existing reservation
1538 * failed; or
1539 * c) we come here with a goal and with a reservation window
1540 *
1541 * We do not need to allocate a new reservation window if we come here
1542 * at the beginning with a goal and the goal is inside the window, or
1543 * we don't have a goal but already have a reservation window.
1544 * then we could go to allocate from the reservation window directly.
1545 */
1546 while (1) {
1547 if (rsv_is_empty(&my_rsv->rsv_window) || (ret < 0) ||
1548 !goal_in_my_reservation(&my_rsv->rsv_window,
1549 grp_goal, group, sb)) {
1550 if (my_rsv->rsv_goal_size < *count)
1551 my_rsv->rsv_goal_size = *count;
1552 ret = alloc_new_reservation(my_rsv, grp_goal, sb,
1553 group, bitmap_bh);
1554 if (ret < 0)
1555 break; /* failed */
1556
1557 if (!goal_in_my_reservation(&my_rsv->rsv_window,
1558 grp_goal, group, sb))
1559 grp_goal = -1;
Hugh Dickinse7dc95d2006-12-06 20:39:19 -08001560 } else if (grp_goal >= 0) {
Mingming Cao1df1e632006-12-06 20:38:19 -08001561 int curr = my_rsv->rsv_end -
1562 (grp_goal + group_first_block) + 1;
1563
1564 if (curr < *count)
1565 try_to_extend_reservation(my_rsv, sb,
1566 *count - curr);
1567 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001568
1569 if ((my_rsv->rsv_start > group_last_block) ||
1570 (my_rsv->rsv_end < group_first_block)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001571 rsv_window_dump(&EXT4_SB(sb)->s_rsv_window_root, 1);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001572 BUG();
1573 }
Mingming Cao617ba132006-10-11 01:20:53 -07001574 ret = ext4_try_to_allocate(sb, handle, group, bitmap_bh,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001575 grp_goal, &num, &my_rsv->rsv_window);
1576 if (ret >= 0) {
1577 my_rsv->rsv_alloc_hit += num;
1578 *count = num;
1579 break; /* succeed */
1580 }
1581 num = *count;
1582 }
1583out:
1584 if (ret >= 0) {
1585 BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for "
1586 "bitmap block");
Mingming Cao617ba132006-10-11 01:20:53 -07001587 fatal = ext4_journal_dirty_metadata(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001588 if (fatal) {
1589 *errp = fatal;
1590 return -1;
1591 }
1592 return ret;
1593 }
1594
1595 BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
Mingming Cao617ba132006-10-11 01:20:53 -07001596 ext4_journal_release_buffer(handle, bitmap_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001597 return ret;
1598}
1599
1600/**
Mingming Cao617ba132006-10-11 01:20:53 -07001601 * ext4_has_free_blocks()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001602 * @sbi: in-core super block structure.
1603 *
1604 * Check if filesystem has at least 1 free block available for allocation.
1605 */
Mingming Cao617ba132006-10-11 01:20:53 -07001606static int ext4_has_free_blocks(struct ext4_sb_info *sbi)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001607{
Mingming Cao617ba132006-10-11 01:20:53 -07001608 ext4_fsblk_t free_blocks, root_blocks;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001609
1610 free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001611 root_blocks = ext4_r_blocks_count(sbi->s_es);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001612 if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
1613 sbi->s_resuid != current->fsuid &&
1614 (sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
1615 return 0;
1616 }
1617 return 1;
1618}
1619
1620/**
Mingming Cao617ba132006-10-11 01:20:53 -07001621 * ext4_should_retry_alloc()
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001622 * @sb: super block
1623 * @retries number of attemps has been made
1624 *
Mingming Cao617ba132006-10-11 01:20:53 -07001625 * ext4_should_retry_alloc() is called when ENOSPC is returned, and if
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001626 * it is profitable to retry the operation, this function will wait
1627 * for the current or commiting transaction to complete, and then
1628 * return TRUE.
1629 *
1630 * if the total number of retries exceed three times, return FALSE.
1631 */
Mingming Cao617ba132006-10-11 01:20:53 -07001632int ext4_should_retry_alloc(struct super_block *sb, int *retries)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001633{
Mingming Cao617ba132006-10-11 01:20:53 -07001634 if (!ext4_has_free_blocks(EXT4_SB(sb)) || (*retries)++ > 3)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001635 return 0;
1636
1637 jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
1638
Mingming Caodab291a2006-10-11 01:21:01 -07001639 return jbd2_journal_force_commit_nested(EXT4_SB(sb)->s_journal);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001640}
1641
1642/**
Alex Tomasc9de5602008-01-29 00:19:52 -05001643 * ext4_new_blocks_old() -- core block(s) allocation function
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001644 * @handle: handle to this transaction
1645 * @inode: file inode
1646 * @goal: given target block(filesystem wide)
1647 * @count: target number of blocks to allocate
1648 * @errp: error code
1649 *
Mingming Cao617ba132006-10-11 01:20:53 -07001650 * ext4_new_blocks uses a goal block to assist allocation. It tries to
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001651 * allocate block(s) from the block group contains the goal block first. If that
1652 * fails, it will try to allocate block(s) from other block groups without
1653 * any specific goal block.
1654 *
1655 */
Alex Tomasc9de5602008-01-29 00:19:52 -05001656ext4_fsblk_t ext4_new_blocks_old(handle_t *handle, struct inode *inode,
Mingming Cao617ba132006-10-11 01:20:53 -07001657 ext4_fsblk_t goal, unsigned long *count, int *errp)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001658{
1659 struct buffer_head *bitmap_bh = NULL;
1660 struct buffer_head *gdp_bh;
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001661 ext4_group_t group_no;
1662 ext4_group_t goal_group;
Mingming Cao617ba132006-10-11 01:20:53 -07001663 ext4_grpblk_t grp_target_blk; /* blockgroup relative goal block */
1664 ext4_grpblk_t grp_alloc_blk; /* blockgroup-relative allocated block*/
1665 ext4_fsblk_t ret_block; /* filesyetem-wide allocated block */
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001666 ext4_group_t bgi; /* blockgroup iteration index */
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001667 int fatal = 0, err;
1668 int performed_allocation = 0;
Mingming Cao617ba132006-10-11 01:20:53 -07001669 ext4_grpblk_t free_blocks; /* number of free blocks in a group */
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001670 struct super_block *sb;
Mingming Cao617ba132006-10-11 01:20:53 -07001671 struct ext4_group_desc *gdp;
1672 struct ext4_super_block *es;
1673 struct ext4_sb_info *sbi;
1674 struct ext4_reserve_window_node *my_rsv = NULL;
1675 struct ext4_block_alloc_info *block_i;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001676 unsigned short windowsz = 0;
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001677 ext4_group_t ngroups;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001678 unsigned long num = *count;
1679
1680 *errp = -ENOSPC;
1681 sb = inode->i_sb;
1682 if (!sb) {
Mingming Cao617ba132006-10-11 01:20:53 -07001683 printk("ext4_new_block: nonexistent device");
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001684 return 0;
1685 }
1686
1687 /*
1688 * Check quota for allocation of this block.
1689 */
1690 if (DQUOT_ALLOC_BLOCK(inode, num)) {
1691 *errp = -EDQUOT;
1692 return 0;
1693 }
1694
Mingming Cao617ba132006-10-11 01:20:53 -07001695 sbi = EXT4_SB(sb);
1696 es = EXT4_SB(sb)->s_es;
Eric Sandeenc549a952008-01-28 23:58:27 -05001697 ext4_debug("goal=%llu.\n", goal);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001698 /*
1699 * Allocate a block from reservation only when
1700 * filesystem is mounted with reservation(default,-o reservation), and
1701 * it's a regular file, and
1702 * the desired window size is greater than 0 (One could use ioctl
Mingming Cao617ba132006-10-11 01:20:53 -07001703 * command EXT4_IOC_SETRSVSZ to set the window size to 0 to turn off
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001704 * reservation on that particular file)
1705 */
Mingming Cao617ba132006-10-11 01:20:53 -07001706 block_i = EXT4_I(inode)->i_block_alloc_info;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001707 if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
1708 my_rsv = &block_i->rsv_window_node;
1709
Mingming Cao617ba132006-10-11 01:20:53 -07001710 if (!ext4_has_free_blocks(sbi)) {
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001711 *errp = -ENOSPC;
1712 goto out;
1713 }
1714
1715 /*
1716 * First, test whether the goal block is free.
1717 */
1718 if (goal < le32_to_cpu(es->s_first_data_block) ||
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001719 goal >= ext4_blocks_count(es))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001720 goal = le32_to_cpu(es->s_first_data_block);
Mingming Cao3a5b2ec2006-10-11 01:21:05 -07001721 ext4_get_group_no_and_offset(sb, goal, &group_no, &grp_target_blk);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001722 goal_group = group_no;
1723retry_alloc:
Mingming Cao617ba132006-10-11 01:20:53 -07001724 gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001725 if (!gdp)
1726 goto io_error;
1727
1728 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1729 /*
1730 * if there is not enough free blocks to make a new resevation
1731 * turn off reservation for this allocation
1732 */
1733 if (my_rsv && (free_blocks < windowsz)
1734 && (rsv_is_empty(&my_rsv->rsv_window)))
1735 my_rsv = NULL;
1736
1737 if (free_blocks > 0) {
Theodore Ts'o574ca172008-07-11 19:27:31 -04001738 bitmap_bh = ext4_read_block_bitmap(sb, group_no);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001739 if (!bitmap_bh)
1740 goto io_error;
Mingming Cao617ba132006-10-11 01:20:53 -07001741 grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001742 group_no, bitmap_bh, grp_target_blk,
1743 my_rsv, &num, &fatal);
1744 if (fatal)
1745 goto out;
1746 if (grp_alloc_blk >= 0)
1747 goto allocated;
1748 }
1749
Mingming Cao617ba132006-10-11 01:20:53 -07001750 ngroups = EXT4_SB(sb)->s_groups_count;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001751 smp_rmb();
1752
1753 /*
1754 * Now search the rest of the groups. We assume that
Akinobu Mita144704e2008-02-06 01:40:15 -08001755 * group_no and gdp correctly point to the last group visited.
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001756 */
1757 for (bgi = 0; bgi < ngroups; bgi++) {
1758 group_no++;
1759 if (group_no >= ngroups)
1760 group_no = 0;
Mingming Cao617ba132006-10-11 01:20:53 -07001761 gdp = ext4_get_group_desc(sb, group_no, &gdp_bh);
Hugh Dickins341cee42006-12-06 20:39:24 -08001762 if (!gdp)
1763 goto io_error;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001764 free_blocks = le16_to_cpu(gdp->bg_free_blocks_count);
1765 /*
1766 * skip this group if the number of
1767 * free blocks is less than half of the reservation
1768 * window size.
1769 */
1770 if (free_blocks <= (windowsz/2))
1771 continue;
1772
1773 brelse(bitmap_bh);
Theodore Ts'o574ca172008-07-11 19:27:31 -04001774 bitmap_bh = ext4_read_block_bitmap(sb, group_no);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001775 if (!bitmap_bh)
1776 goto io_error;
1777 /*
1778 * try to allocate block(s) from this group, without a goal(-1).
1779 */
Mingming Cao617ba132006-10-11 01:20:53 -07001780 grp_alloc_blk = ext4_try_to_allocate_with_rsv(sb, handle,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001781 group_no, bitmap_bh, -1, my_rsv,
1782 &num, &fatal);
1783 if (fatal)
1784 goto out;
1785 if (grp_alloc_blk >= 0)
1786 goto allocated;
1787 }
1788 /*
1789 * We may end up a bogus ealier ENOSPC error due to
1790 * filesystem is "full" of reservations, but
1791 * there maybe indeed free blocks avaliable on disk
1792 * In this case, we just forget about the reservations
1793 * just do block allocation as without reservations.
1794 */
1795 if (my_rsv) {
1796 my_rsv = NULL;
Hugh Dickinscd16c8f2006-12-06 20:39:18 -08001797 windowsz = 0;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001798 group_no = goal_group;
1799 goto retry_alloc;
1800 }
1801 /* No space left on the device */
1802 *errp = -ENOSPC;
1803 goto out;
1804
1805allocated:
1806
Eric Sandeenc549a952008-01-28 23:58:27 -05001807 ext4_debug("using block group %lu(%d)\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001808 group_no, gdp->bg_free_blocks_count);
1809
1810 BUFFER_TRACE(gdp_bh, "get_write_access");
Mingming Cao617ba132006-10-11 01:20:53 -07001811 fatal = ext4_journal_get_write_access(handle, gdp_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001812 if (fatal)
1813 goto out;
1814
Mingming Cao617ba132006-10-11 01:20:53 -07001815 ret_block = grp_alloc_blk + ext4_group_first_block_no(sb, group_no);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001816
Alexandre Ratchov8fadc142006-10-11 01:21:15 -07001817 if (in_range(ext4_block_bitmap(sb, gdp), ret_block, num) ||
Toshiyuki Okajima29bc5b42007-07-15 23:41:22 -07001818 in_range(ext4_inode_bitmap(sb, gdp), ret_block, num) ||
Alexandre Ratchov8fadc142006-10-11 01:21:15 -07001819 in_range(ret_block, ext4_inode_table(sb, gdp),
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001820 EXT4_SB(sb)->s_itb_per_group) ||
Alexandre Ratchov8fadc142006-10-11 01:21:15 -07001821 in_range(ret_block + num - 1, ext4_inode_table(sb, gdp),
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -05001822 EXT4_SB(sb)->s_itb_per_group)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001823 ext4_error(sb, "ext4_new_block",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001824 "Allocating block in system zone - "
Mingming Cao2ae02102006-10-11 01:21:11 -07001825 "blocks from %llu, length %lu",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001826 ret_block, num);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04001827 /*
1828 * claim_block marked the blocks we allocated
1829 * as in use. So we may want to selectively
1830 * mark some of the blocks as free
1831 */
1832 goto retry_alloc;
Aneesh Kumar K.Vcb47dce2008-01-28 23:58:27 -05001833 }
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001834
1835 performed_allocation = 1;
1836
Jose R. Santose23291b2007-07-18 08:57:06 -04001837#ifdef CONFIG_JBD2_DEBUG
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001838 {
1839 struct buffer_head *debug_bh;
1840
1841 /* Record bitmap buffer state in the newly allocated block */
1842 debug_bh = sb_find_get_block(sb, ret_block);
1843 if (debug_bh) {
1844 BUFFER_TRACE(debug_bh, "state when allocated");
1845 BUFFER_TRACE2(debug_bh, bitmap_bh, "bitmap state");
1846 brelse(debug_bh);
1847 }
1848 }
1849 jbd_lock_bh_state(bitmap_bh);
1850 spin_lock(sb_bgl_lock(sbi, group_no));
1851 if (buffer_jbd(bitmap_bh) && bh2jh(bitmap_bh)->b_committed_data) {
1852 int i;
1853
1854 for (i = 0; i < num; i++) {
Mingming Cao617ba132006-10-11 01:20:53 -07001855 if (ext4_test_bit(grp_alloc_blk+i,
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001856 bh2jh(bitmap_bh)->b_committed_data)) {
1857 printk("%s: block was unexpectedly set in "
Harvey Harrison46e665e2008-04-17 10:38:59 -04001858 "b_committed_data\n", __func__);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001859 }
1860 }
1861 }
Mingming Cao617ba132006-10-11 01:20:53 -07001862 ext4_debug("found bit %d\n", grp_alloc_blk);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001863 spin_unlock(sb_bgl_lock(sbi, group_no));
1864 jbd_unlock_bh_state(bitmap_bh);
1865#endif
1866
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001867 if (ret_block + num - 1 >= ext4_blocks_count(es)) {
Mingming Cao617ba132006-10-11 01:20:53 -07001868 ext4_error(sb, "ext4_new_block",
Mingming Cao2ae02102006-10-11 01:21:11 -07001869 "block(%llu) >= blocks count(%llu) - "
Mingming Cao3a5b2ec2006-10-11 01:21:05 -07001870 "block_group = %lu, es == %p ", ret_block,
Laurent Vivierbd81d8e2006-10-11 01:21:10 -07001871 ext4_blocks_count(es), group_no, es);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001872 goto out;
1873 }
1874
1875 /*
1876 * It is up to the caller to add the new buffer to a journal
1877 * list of some description. We don't know in advance whether
1878 * the caller wants to use it as metadata or data.
1879 */
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001880 spin_lock(sb_bgl_lock(sbi, group_no));
Andreas Dilger717d50e2007-10-16 18:38:25 -04001881 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
1882 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
Marcin Slusarze8546d02008-04-17 10:38:59 -04001883 le16_add_cpu(&gdp->bg_free_blocks_count, -num);
Andreas Dilger717d50e2007-10-16 18:38:25 -04001884 gdp->bg_checksum = ext4_group_desc_csum(sbi, group_no, gdp);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001885 spin_unlock(sb_bgl_lock(sbi, group_no));
Peter Zijlstra3cb4f9f2007-10-16 23:25:42 -07001886 percpu_counter_sub(&sbi->s_freeblocks_counter, num);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001887
Jose R. Santos772cb7c2008-07-11 19:27:31 -04001888 if (sbi->s_log_groups_per_flex) {
1889 ext4_group_t flex_group = ext4_flex_group(sbi, group_no);
1890 spin_lock(sb_bgl_lock(sbi, flex_group));
1891 sbi->s_flex_groups[flex_group].free_blocks -= num;
1892 spin_unlock(sb_bgl_lock(sbi, flex_group));
1893 }
1894
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001895 BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
Mingming Cao617ba132006-10-11 01:20:53 -07001896 err = ext4_journal_dirty_metadata(handle, gdp_bh);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001897 if (!fatal)
1898 fatal = err;
1899
1900 sb->s_dirt = 1;
1901 if (fatal)
1902 goto out;
1903
1904 *errp = 0;
1905 brelse(bitmap_bh);
1906 DQUOT_FREE_BLOCK(inode, *count-num);
1907 *count = num;
1908 return ret_block;
1909
1910io_error:
1911 *errp = -EIO;
1912out:
1913 if (fatal) {
1914 *errp = fatal;
Mingming Cao617ba132006-10-11 01:20:53 -07001915 ext4_std_error(sb, fatal);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001916 }
1917 /*
1918 * Undo the block allocation
1919 */
1920 if (!performed_allocation)
1921 DQUOT_FREE_BLOCK(inode, *count);
1922 brelse(bitmap_bh);
1923 return 0;
1924}
1925
Mingming Cao617ba132006-10-11 01:20:53 -07001926ext4_fsblk_t ext4_new_block(handle_t *handle, struct inode *inode,
Alex Tomasc9de5602008-01-29 00:19:52 -05001927 ext4_fsblk_t goal, int *errp)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001928{
Alex Tomasc9de5602008-01-29 00:19:52 -05001929 struct ext4_allocation_request ar;
1930 ext4_fsblk_t ret;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001931
Alex Tomasc9de5602008-01-29 00:19:52 -05001932 if (!test_opt(inode->i_sb, MBALLOC)) {
1933 unsigned long count = 1;
1934 ret = ext4_new_blocks_old(handle, inode, goal, &count, errp);
1935 return ret;
1936 }
1937
1938 memset(&ar, 0, sizeof(ar));
1939 ar.inode = inode;
1940 ar.goal = goal;
1941 ar.len = 1;
1942 ret = ext4_mb_new_blocks(handle, &ar, errp);
1943 return ret;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001944}
1945
Alex Tomasc9de5602008-01-29 00:19:52 -05001946ext4_fsblk_t ext4_new_blocks(handle_t *handle, struct inode *inode,
1947 ext4_fsblk_t goal, unsigned long *count, int *errp)
1948{
1949 struct ext4_allocation_request ar;
1950 ext4_fsblk_t ret;
1951
1952 if (!test_opt(inode->i_sb, MBALLOC)) {
1953 ret = ext4_new_blocks_old(handle, inode, goal, count, errp);
1954 return ret;
1955 }
1956
1957 memset(&ar, 0, sizeof(ar));
1958 ar.inode = inode;
1959 ar.goal = goal;
1960 ar.len = *count;
1961 ret = ext4_mb_new_blocks(handle, &ar, errp);
1962 *count = ar.len;
1963 return ret;
1964}
1965
1966
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001967/**
Mingming Cao617ba132006-10-11 01:20:53 -07001968 * ext4_count_free_blocks() -- count filesystem free blocks
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001969 * @sb: superblock
1970 *
1971 * Adds up the number of free blocks from each block group.
1972 */
Mingming Cao617ba132006-10-11 01:20:53 -07001973ext4_fsblk_t ext4_count_free_blocks(struct super_block *sb)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001974{
Mingming Cao617ba132006-10-11 01:20:53 -07001975 ext4_fsblk_t desc_count;
1976 struct ext4_group_desc *gdp;
Avantika Mathurfd2d4292008-01-28 23:58:27 -05001977 ext4_group_t i;
1978 ext4_group_t ngroups = EXT4_SB(sb)->s_groups_count;
Mingming Cao617ba132006-10-11 01:20:53 -07001979#ifdef EXT4FS_DEBUG
1980 struct ext4_super_block *es;
1981 ext4_fsblk_t bitmap_count;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001982 unsigned long x;
1983 struct buffer_head *bitmap_bh = NULL;
1984
Mingming Cao617ba132006-10-11 01:20:53 -07001985 es = EXT4_SB(sb)->s_es;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001986 desc_count = 0;
1987 bitmap_count = 0;
1988 gdp = NULL;
1989
1990 smp_rmb();
1991 for (i = 0; i < ngroups; i++) {
Mingming Cao617ba132006-10-11 01:20:53 -07001992 gdp = ext4_get_group_desc(sb, i, NULL);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001993 if (!gdp)
1994 continue;
1995 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
1996 brelse(bitmap_bh);
Theodore Ts'o574ca172008-07-11 19:27:31 -04001997 bitmap_bh = ext4_read_block_bitmap(sb, i);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07001998 if (bitmap_bh == NULL)
1999 continue;
2000
Mingming Cao617ba132006-10-11 01:20:53 -07002001 x = ext4_count_free(bitmap_bh, sb->s_blocksize);
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002002 printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002003 i, le16_to_cpu(gdp->bg_free_blocks_count), x);
2004 bitmap_count += x;
2005 }
2006 brelse(bitmap_bh);
Mingming Cao2ae02102006-10-11 01:21:11 -07002007 printk("ext4_count_free_blocks: stored = %llu"
2008 ", computed = %llu, %llu\n",
Eric Sandeenc549a952008-01-28 23:58:27 -05002009 ext4_free_blocks_count(es),
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002010 desc_count, bitmap_count);
2011 return bitmap_count;
2012#else
2013 desc_count = 0;
2014 smp_rmb();
2015 for (i = 0; i < ngroups; i++) {
Mingming Cao617ba132006-10-11 01:20:53 -07002016 gdp = ext4_get_group_desc(sb, i, NULL);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002017 if (!gdp)
2018 continue;
2019 desc_count += le16_to_cpu(gdp->bg_free_blocks_count);
2020 }
2021
2022 return desc_count;
2023#endif
2024}
2025
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002026static inline int test_root(ext4_group_t a, int b)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002027{
2028 int num = b;
2029
2030 while (a > num)
2031 num *= b;
2032 return num == a;
2033}
2034
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002035static int ext4_group_sparse(ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002036{
2037 if (group <= 1)
2038 return 1;
2039 if (!(group & 1))
2040 return 0;
2041 return (test_root(group, 7) || test_root(group, 5) ||
2042 test_root(group, 3));
2043}
2044
2045/**
Mingming Cao617ba132006-10-11 01:20:53 -07002046 * ext4_bg_has_super - number of blocks used by the superblock in group
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002047 * @sb: superblock for filesystem
2048 * @group: group number to check
2049 *
2050 * Return the number of blocks used by the superblock (primary or backup)
2051 * in this group. Currently this will be only 0 or 1.
2052 */
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002053int ext4_bg_has_super(struct super_block *sb, ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002054{
Mingming Cao617ba132006-10-11 01:20:53 -07002055 if (EXT4_HAS_RO_COMPAT_FEATURE(sb,
2056 EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER) &&
2057 !ext4_group_sparse(group))
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002058 return 0;
2059 return 1;
2060}
2061
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002062static unsigned long ext4_bg_num_gdb_meta(struct super_block *sb,
2063 ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002064{
Mingming Cao617ba132006-10-11 01:20:53 -07002065 unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002066 ext4_group_t first = metagroup * EXT4_DESC_PER_BLOCK(sb);
2067 ext4_group_t last = first + EXT4_DESC_PER_BLOCK(sb) - 1;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002068
2069 if (group == first || group == first + 1 || group == last)
2070 return 1;
2071 return 0;
2072}
2073
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002074static unsigned long ext4_bg_num_gdb_nometa(struct super_block *sb,
2075 ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002076{
Akinobu Mita859cb932008-02-06 01:40:17 -08002077 return ext4_bg_has_super(sb, group) ? EXT4_SB(sb)->s_gdb_count : 0;
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002078}
2079
2080/**
Mingming Cao617ba132006-10-11 01:20:53 -07002081 * ext4_bg_num_gdb - number of blocks used by the group table in group
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002082 * @sb: superblock for filesystem
2083 * @group: group number to check
2084 *
2085 * Return the number of blocks used by the group descriptor table
2086 * (primary or backup) in this group. In the future there may be a
2087 * different number of descriptor blocks in each group.
2088 */
Avantika Mathurfd2d4292008-01-28 23:58:27 -05002089unsigned long ext4_bg_num_gdb(struct super_block *sb, ext4_group_t group)
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002090{
2091 unsigned long first_meta_bg =
Mingming Cao617ba132006-10-11 01:20:53 -07002092 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_meta_bg);
2093 unsigned long metagroup = group / EXT4_DESC_PER_BLOCK(sb);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002094
Mingming Cao617ba132006-10-11 01:20:53 -07002095 if (!EXT4_HAS_INCOMPAT_FEATURE(sb,EXT4_FEATURE_INCOMPAT_META_BG) ||
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002096 metagroup < first_meta_bg)
Mingming Cao617ba132006-10-11 01:20:53 -07002097 return ext4_bg_num_gdb_nometa(sb,group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002098
Mingming Cao617ba132006-10-11 01:20:53 -07002099 return ext4_bg_num_gdb_meta(sb,group);
Dave Kleikampac27a0e2006-10-11 01:20:50 -07002100
2101}