blob: 240cf0daad4b2771696af4f8ae257abce5527b32 [file] [log] [blame]
Alex Tomasa86c6182006-10-11 01:21:03 -07001/*
2 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
3 * Written by Alex Tomas <alex@clusterfs.com>
4 *
5 * Architecture independence:
6 * Copyright (c) 2005, Bull S.A.
7 * Written by Pierre Peiffer <pierre.peiffer@bull.net>
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public Licens
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-
21 */
22
23/*
24 * Extents support for EXT4
25 *
26 * TODO:
27 * - ext4*_error() should be used in some situations
28 * - analyze all BUG()/BUG_ON(), use -EIO where appropriate
29 * - smart tree reduction
30 */
31
32#include <linux/module.h>
33#include <linux/fs.h>
34#include <linux/time.h>
Mingming Caocd02ff02007-10-16 18:38:25 -040035#include <linux/jbd2.h>
Alex Tomasa86c6182006-10-11 01:21:03 -070036#include <linux/highuid.h>
37#include <linux/pagemap.h>
38#include <linux/quotaops.h>
39#include <linux/string.h>
40#include <linux/slab.h>
Amit Aroraa2df2a62007-07-17 21:42:41 -040041#include <linux/falloc.h>
Alex Tomasa86c6182006-10-11 01:21:03 -070042#include <asm/uaccess.h>
Eric Sandeen6873fa02008-10-07 00:46:36 -040043#include <linux/fiemap.h>
Christoph Hellwig3dcf5452008-04-29 18:13:32 -040044#include "ext4_jbd2.h"
45#include "ext4_extents.h"
Alex Tomasa86c6182006-10-11 01:21:03 -070046
47
Randy Dunlapd0d856e2006-10-11 01:21:07 -070048/*
49 * ext_pblock:
50 * combine low and high parts of physical block number into ext4_fsblk_t
51 */
Avantika Mathur09b88252006-12-06 20:41:36 -080052static ext4_fsblk_t ext_pblock(struct ext4_extent *ex)
Alex Tomasf65e6fb2006-10-11 01:21:05 -070053{
54 ext4_fsblk_t block;
55
Aneesh Kumar K.Vb3776112007-10-16 18:38:25 -040056 block = le32_to_cpu(ex->ee_start_lo);
Mingming Cao9b8f1f02006-10-11 01:21:13 -070057 block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
Alex Tomasf65e6fb2006-10-11 01:21:05 -070058 return block;
59}
60
Randy Dunlapd0d856e2006-10-11 01:21:07 -070061/*
62 * idx_pblock:
63 * combine low and high parts of a leaf physical block number into ext4_fsblk_t
64 */
Aneesh Kumar K.Vc14c6fd2008-01-28 23:58:26 -050065ext4_fsblk_t idx_pblock(struct ext4_extent_idx *ix)
Alex Tomasf65e6fb2006-10-11 01:21:05 -070066{
67 ext4_fsblk_t block;
68
Aneesh Kumar K.Vd8dd0b42007-10-16 18:38:25 -040069 block = le32_to_cpu(ix->ei_leaf_lo);
Mingming Cao9b8f1f02006-10-11 01:21:13 -070070 block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
Alex Tomasf65e6fb2006-10-11 01:21:05 -070071 return block;
72}
73
Randy Dunlapd0d856e2006-10-11 01:21:07 -070074/*
75 * ext4_ext_store_pblock:
76 * stores a large physical block number into an extent struct,
77 * breaking it into parts
78 */
Aneesh Kumar K.Vc14c6fd2008-01-28 23:58:26 -050079void ext4_ext_store_pblock(struct ext4_extent *ex, ext4_fsblk_t pb)
Alex Tomasf65e6fb2006-10-11 01:21:05 -070080{
Aneesh Kumar K.Vb3776112007-10-16 18:38:25 -040081 ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
Mingming Cao9b8f1f02006-10-11 01:21:13 -070082 ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
Alex Tomasf65e6fb2006-10-11 01:21:05 -070083}
84
Randy Dunlapd0d856e2006-10-11 01:21:07 -070085/*
86 * ext4_idx_store_pblock:
87 * stores a large physical block number into an index struct,
88 * breaking it into parts
89 */
Avantika Mathur09b88252006-12-06 20:41:36 -080090static void ext4_idx_store_pblock(struct ext4_extent_idx *ix, ext4_fsblk_t pb)
Alex Tomasf65e6fb2006-10-11 01:21:05 -070091{
Aneesh Kumar K.Vd8dd0b42007-10-16 18:38:25 -040092 ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
Mingming Cao9b8f1f02006-10-11 01:21:13 -070093 ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
Alex Tomasf65e6fb2006-10-11 01:21:05 -070094}
95
Shen Feng9102e4f2008-07-11 19:27:31 -040096static int ext4_ext_journal_restart(handle_t *handle, int needed)
Alex Tomasa86c6182006-10-11 01:21:03 -070097{
98 int err;
99
Frank Mayhar03901312009-01-07 00:06:22 -0500100 if (!ext4_handle_valid(handle))
101 return 0;
Alex Tomasa86c6182006-10-11 01:21:03 -0700102 if (handle->h_buffer_credits > needed)
Shen Feng9102e4f2008-07-11 19:27:31 -0400103 return 0;
104 err = ext4_journal_extend(handle, needed);
Theodore Ts'o0123c932008-08-01 20:57:54 -0400105 if (err <= 0)
Shen Feng9102e4f2008-07-11 19:27:31 -0400106 return err;
107 return ext4_journal_restart(handle, needed);
Alex Tomasa86c6182006-10-11 01:21:03 -0700108}
109
110/*
111 * could return:
112 * - EROFS
113 * - ENOMEM
114 */
115static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
116 struct ext4_ext_path *path)
117{
118 if (path->p_bh) {
119 /* path points to block */
120 return ext4_journal_get_write_access(handle, path->p_bh);
121 }
122 /* path points to leaf/index in inode body */
123 /* we use in-core data, no need to protect them */
124 return 0;
125}
126
127/*
128 * could return:
129 * - EROFS
130 * - ENOMEM
131 * - EIO
132 */
133static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
134 struct ext4_ext_path *path)
135{
136 int err;
137 if (path->p_bh) {
138 /* path points to block */
Frank Mayhar03901312009-01-07 00:06:22 -0500139 err = ext4_handle_dirty_metadata(handle, inode, path->p_bh);
Alex Tomasa86c6182006-10-11 01:21:03 -0700140 } else {
141 /* path points to leaf/index in inode body */
142 err = ext4_mark_inode_dirty(handle, inode);
143 }
144 return err;
145}
146
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700147static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
Alex Tomasa86c6182006-10-11 01:21:03 -0700148 struct ext4_ext_path *path,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -0500149 ext4_lblk_t block)
Alex Tomasa86c6182006-10-11 01:21:03 -0700150{
151 struct ext4_inode_info *ei = EXT4_I(inode);
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700152 ext4_fsblk_t bg_start;
Valerie Clement74d34872008-02-15 13:43:07 -0500153 ext4_fsblk_t last_block;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700154 ext4_grpblk_t colour;
Alex Tomasa86c6182006-10-11 01:21:03 -0700155 int depth;
156
157 if (path) {
158 struct ext4_extent *ex;
159 depth = path->p_depth;
160
161 /* try to predict block placement */
Avantika Mathur7e028972006-12-06 20:41:33 -0800162 ex = path[depth].p_ext;
163 if (ex)
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700164 return ext_pblock(ex)+(block-le32_to_cpu(ex->ee_block));
Alex Tomasa86c6182006-10-11 01:21:03 -0700165
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700166 /* it looks like index is empty;
167 * try to find starting block from index itself */
Alex Tomasa86c6182006-10-11 01:21:03 -0700168 if (path[depth].p_bh)
169 return path[depth].p_bh->b_blocknr;
170 }
171
172 /* OK. use inode's group */
173 bg_start = (ei->i_block_group * EXT4_BLOCKS_PER_GROUP(inode->i_sb)) +
174 le32_to_cpu(EXT4_SB(inode->i_sb)->s_es->s_first_data_block);
Valerie Clement74d34872008-02-15 13:43:07 -0500175 last_block = ext4_blocks_count(EXT4_SB(inode->i_sb)->s_es) - 1;
176
177 if (bg_start + EXT4_BLOCKS_PER_GROUP(inode->i_sb) <= last_block)
178 colour = (current->pid % 16) *
Alex Tomasa86c6182006-10-11 01:21:03 -0700179 (EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16);
Valerie Clement74d34872008-02-15 13:43:07 -0500180 else
181 colour = (current->pid % 16) * ((last_block - bg_start) / 16);
Alex Tomasa86c6182006-10-11 01:21:03 -0700182 return bg_start + colour + block;
183}
184
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -0400185/*
186 * Allocation for a meta data block
187 */
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700188static ext4_fsblk_t
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -0400189ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
Alex Tomasa86c6182006-10-11 01:21:03 -0700190 struct ext4_ext_path *path,
191 struct ext4_extent *ex, int *err)
192{
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700193 ext4_fsblk_t goal, newblock;
Alex Tomasa86c6182006-10-11 01:21:03 -0700194
195 goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
Theodore Ts'o97df5d12008-12-12 12:41:28 -0500196 newblock = ext4_new_meta_blocks(handle, inode, goal, NULL, err);
Alex Tomasa86c6182006-10-11 01:21:03 -0700197 return newblock;
198}
199
Avantika Mathur09b88252006-12-06 20:41:36 -0800200static int ext4_ext_space_block(struct inode *inode)
Alex Tomasa86c6182006-10-11 01:21:03 -0700201{
202 int size;
203
204 size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
205 / sizeof(struct ext4_extent);
Robert P. J. Daybbf2f9f2007-02-17 19:20:16 +0100206#ifdef AGGRESSIVE_TEST
Alex Tomasa86c6182006-10-11 01:21:03 -0700207 if (size > 6)
208 size = 6;
209#endif
210 return size;
211}
212
Avantika Mathur09b88252006-12-06 20:41:36 -0800213static int ext4_ext_space_block_idx(struct inode *inode)
Alex Tomasa86c6182006-10-11 01:21:03 -0700214{
215 int size;
216
217 size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
218 / sizeof(struct ext4_extent_idx);
Robert P. J. Daybbf2f9f2007-02-17 19:20:16 +0100219#ifdef AGGRESSIVE_TEST
Alex Tomasa86c6182006-10-11 01:21:03 -0700220 if (size > 5)
221 size = 5;
222#endif
223 return size;
224}
225
Avantika Mathur09b88252006-12-06 20:41:36 -0800226static int ext4_ext_space_root(struct inode *inode)
Alex Tomasa86c6182006-10-11 01:21:03 -0700227{
228 int size;
229
230 size = sizeof(EXT4_I(inode)->i_data);
231 size -= sizeof(struct ext4_extent_header);
232 size /= sizeof(struct ext4_extent);
Robert P. J. Daybbf2f9f2007-02-17 19:20:16 +0100233#ifdef AGGRESSIVE_TEST
Alex Tomasa86c6182006-10-11 01:21:03 -0700234 if (size > 3)
235 size = 3;
236#endif
237 return size;
238}
239
Avantika Mathur09b88252006-12-06 20:41:36 -0800240static int ext4_ext_space_root_idx(struct inode *inode)
Alex Tomasa86c6182006-10-11 01:21:03 -0700241{
242 int size;
243
244 size = sizeof(EXT4_I(inode)->i_data);
245 size -= sizeof(struct ext4_extent_header);
246 size /= sizeof(struct ext4_extent_idx);
Robert P. J. Daybbf2f9f2007-02-17 19:20:16 +0100247#ifdef AGGRESSIVE_TEST
Alex Tomasa86c6182006-10-11 01:21:03 -0700248 if (size > 4)
249 size = 4;
250#endif
251 return size;
252}
253
Mingming Caod2a17632008-07-14 17:52:37 -0400254/*
255 * Calculate the number of metadata blocks needed
256 * to allocate @blocks
257 * Worse case is one block per extent
258 */
259int ext4_ext_calc_metadata_amount(struct inode *inode, int blocks)
260{
261 int lcap, icap, rcap, leafs, idxs, num;
262 int newextents = blocks;
263
264 rcap = ext4_ext_space_root_idx(inode);
265 lcap = ext4_ext_space_block(inode);
266 icap = ext4_ext_space_block_idx(inode);
267
268 /* number of new leaf blocks needed */
269 num = leafs = (newextents + lcap - 1) / lcap;
270
271 /*
272 * Worse case, we need separate index block(s)
273 * to link all new leaf blocks
274 */
275 idxs = (leafs + icap - 1) / icap;
276 do {
277 num += idxs;
278 idxs = (idxs + icap - 1) / icap;
279 } while (idxs > rcap);
280
281 return num;
282}
283
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400284static int
285ext4_ext_max_entries(struct inode *inode, int depth)
286{
287 int max;
288
289 if (depth == ext_depth(inode)) {
290 if (depth == 0)
291 max = ext4_ext_space_root(inode);
292 else
293 max = ext4_ext_space_root_idx(inode);
294 } else {
295 if (depth == 0)
296 max = ext4_ext_space_block(inode);
297 else
298 max = ext4_ext_space_block_idx(inode);
299 }
300
301 return max;
302}
303
304static int __ext4_ext_check_header(const char *function, struct inode *inode,
305 struct ext4_extent_header *eh,
306 int depth)
307{
308 const char *error_msg;
309 int max = 0;
310
311 if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
312 error_msg = "invalid magic";
313 goto corrupted;
314 }
315 if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
316 error_msg = "unexpected eh_depth";
317 goto corrupted;
318 }
319 if (unlikely(eh->eh_max == 0)) {
320 error_msg = "invalid eh_max";
321 goto corrupted;
322 }
323 max = ext4_ext_max_entries(inode, depth);
324 if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
325 error_msg = "too large eh_max";
326 goto corrupted;
327 }
328 if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
329 error_msg = "invalid eh_entries";
330 goto corrupted;
331 }
332 return 0;
333
334corrupted:
335 ext4_error(inode->i_sb, function,
336 "bad header in inode #%lu: %s - magic %x, "
337 "entries %u, max %u(%u), depth %u(%u)",
338 inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic),
339 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
340 max, le16_to_cpu(eh->eh_depth), depth);
341
342 return -EIO;
343}
344
345#define ext4_ext_check_header(inode, eh, depth) \
Harvey Harrison46e665e2008-04-17 10:38:59 -0400346 __ext4_ext_check_header(__func__, inode, eh, depth)
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400347
Alex Tomasa86c6182006-10-11 01:21:03 -0700348#ifdef EXT_DEBUG
349static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
350{
351 int k, l = path->p_depth;
352
353 ext_debug("path:");
354 for (k = 0; k <= l; k++, path++) {
355 if (path->p_idx) {
Mingming Cao2ae02102006-10-11 01:21:11 -0700356 ext_debug(" %d->%llu", le32_to_cpu(path->p_idx->ei_block),
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700357 idx_pblock(path->p_idx));
Alex Tomasa86c6182006-10-11 01:21:03 -0700358 } else if (path->p_ext) {
Mingming Cao2ae02102006-10-11 01:21:11 -0700359 ext_debug(" %d:%d:%llu ",
Alex Tomasa86c6182006-10-11 01:21:03 -0700360 le32_to_cpu(path->p_ext->ee_block),
Amit Aroraa2df2a62007-07-17 21:42:41 -0400361 ext4_ext_get_actual_len(path->p_ext),
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700362 ext_pblock(path->p_ext));
Alex Tomasa86c6182006-10-11 01:21:03 -0700363 } else
364 ext_debug(" []");
365 }
366 ext_debug("\n");
367}
368
369static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
370{
371 int depth = ext_depth(inode);
372 struct ext4_extent_header *eh;
373 struct ext4_extent *ex;
374 int i;
375
376 if (!path)
377 return;
378
379 eh = path[depth].p_hdr;
380 ex = EXT_FIRST_EXTENT(eh);
381
382 for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
Mingming Cao2ae02102006-10-11 01:21:11 -0700383 ext_debug("%d:%d:%llu ", le32_to_cpu(ex->ee_block),
Amit Aroraa2df2a62007-07-17 21:42:41 -0400384 ext4_ext_get_actual_len(ex), ext_pblock(ex));
Alex Tomasa86c6182006-10-11 01:21:03 -0700385 }
386 ext_debug("\n");
387}
388#else
Theodore Ts'oaf5bc922008-09-08 22:25:24 -0400389#define ext4_ext_show_path(inode, path)
390#define ext4_ext_show_leaf(inode, path)
Alex Tomasa86c6182006-10-11 01:21:03 -0700391#endif
392
Aneesh Kumar K.Vb35905c2008-02-25 16:54:37 -0500393void ext4_ext_drop_refs(struct ext4_ext_path *path)
Alex Tomasa86c6182006-10-11 01:21:03 -0700394{
395 int depth = path->p_depth;
396 int i;
397
398 for (i = 0; i <= depth; i++, path++)
399 if (path->p_bh) {
400 brelse(path->p_bh);
401 path->p_bh = NULL;
402 }
403}
404
405/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700406 * ext4_ext_binsearch_idx:
407 * binary search for the closest index of the given block
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400408 * the header must be checked before calling this
Alex Tomasa86c6182006-10-11 01:21:03 -0700409 */
410static void
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -0500411ext4_ext_binsearch_idx(struct inode *inode,
412 struct ext4_ext_path *path, ext4_lblk_t block)
Alex Tomasa86c6182006-10-11 01:21:03 -0700413{
414 struct ext4_extent_header *eh = path->p_hdr;
415 struct ext4_extent_idx *r, *l, *m;
416
Alex Tomasa86c6182006-10-11 01:21:03 -0700417
Eric Sandeenbba90742008-01-28 23:58:27 -0500418 ext_debug("binsearch for %u(idx): ", block);
Alex Tomasa86c6182006-10-11 01:21:03 -0700419
420 l = EXT_FIRST_INDEX(eh) + 1;
Dmitry Monakhove9f410b2007-07-18 09:09:15 -0400421 r = EXT_LAST_INDEX(eh);
Alex Tomasa86c6182006-10-11 01:21:03 -0700422 while (l <= r) {
423 m = l + (r - l) / 2;
424 if (block < le32_to_cpu(m->ei_block))
425 r = m - 1;
426 else
427 l = m + 1;
Dmitry Monakhov26d535e2007-07-18 08:33:37 -0400428 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
429 m, le32_to_cpu(m->ei_block),
430 r, le32_to_cpu(r->ei_block));
Alex Tomasa86c6182006-10-11 01:21:03 -0700431 }
432
433 path->p_idx = l - 1;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700434 ext_debug(" -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
Dmitry Monakhov26d535e2007-07-18 08:33:37 -0400435 idx_pblock(path->p_idx));
Alex Tomasa86c6182006-10-11 01:21:03 -0700436
437#ifdef CHECK_BINSEARCH
438 {
439 struct ext4_extent_idx *chix, *ix;
440 int k;
441
442 chix = ix = EXT_FIRST_INDEX(eh);
443 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
444 if (k != 0 &&
445 le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400446 printk(KERN_DEBUG "k=%d, ix=0x%p, "
447 "first=0x%p\n", k,
448 ix, EXT_FIRST_INDEX(eh));
449 printk(KERN_DEBUG "%u <= %u\n",
Alex Tomasa86c6182006-10-11 01:21:03 -0700450 le32_to_cpu(ix->ei_block),
451 le32_to_cpu(ix[-1].ei_block));
452 }
453 BUG_ON(k && le32_to_cpu(ix->ei_block)
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400454 <= le32_to_cpu(ix[-1].ei_block));
Alex Tomasa86c6182006-10-11 01:21:03 -0700455 if (block < le32_to_cpu(ix->ei_block))
456 break;
457 chix = ix;
458 }
459 BUG_ON(chix != path->p_idx);
460 }
461#endif
462
463}
464
465/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700466 * ext4_ext_binsearch:
467 * binary search for closest extent of the given block
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400468 * the header must be checked before calling this
Alex Tomasa86c6182006-10-11 01:21:03 -0700469 */
470static void
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -0500471ext4_ext_binsearch(struct inode *inode,
472 struct ext4_ext_path *path, ext4_lblk_t block)
Alex Tomasa86c6182006-10-11 01:21:03 -0700473{
474 struct ext4_extent_header *eh = path->p_hdr;
475 struct ext4_extent *r, *l, *m;
476
Alex Tomasa86c6182006-10-11 01:21:03 -0700477 if (eh->eh_entries == 0) {
478 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700479 * this leaf is empty:
480 * we get such a leaf in split/add case
Alex Tomasa86c6182006-10-11 01:21:03 -0700481 */
482 return;
483 }
484
Eric Sandeenbba90742008-01-28 23:58:27 -0500485 ext_debug("binsearch for %u: ", block);
Alex Tomasa86c6182006-10-11 01:21:03 -0700486
487 l = EXT_FIRST_EXTENT(eh) + 1;
Dmitry Monakhove9f410b2007-07-18 09:09:15 -0400488 r = EXT_LAST_EXTENT(eh);
Alex Tomasa86c6182006-10-11 01:21:03 -0700489
490 while (l <= r) {
491 m = l + (r - l) / 2;
492 if (block < le32_to_cpu(m->ee_block))
493 r = m - 1;
494 else
495 l = m + 1;
Dmitry Monakhov26d535e2007-07-18 08:33:37 -0400496 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
497 m, le32_to_cpu(m->ee_block),
498 r, le32_to_cpu(r->ee_block));
Alex Tomasa86c6182006-10-11 01:21:03 -0700499 }
500
501 path->p_ext = l - 1;
Mingming Cao2ae02102006-10-11 01:21:11 -0700502 ext_debug(" -> %d:%llu:%d ",
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400503 le32_to_cpu(path->p_ext->ee_block),
504 ext_pblock(path->p_ext),
Amit Aroraa2df2a62007-07-17 21:42:41 -0400505 ext4_ext_get_actual_len(path->p_ext));
Alex Tomasa86c6182006-10-11 01:21:03 -0700506
507#ifdef CHECK_BINSEARCH
508 {
509 struct ext4_extent *chex, *ex;
510 int k;
511
512 chex = ex = EXT_FIRST_EXTENT(eh);
513 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
514 BUG_ON(k && le32_to_cpu(ex->ee_block)
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400515 <= le32_to_cpu(ex[-1].ee_block));
Alex Tomasa86c6182006-10-11 01:21:03 -0700516 if (block < le32_to_cpu(ex->ee_block))
517 break;
518 chex = ex;
519 }
520 BUG_ON(chex != path->p_ext);
521 }
522#endif
523
524}
525
526int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
527{
528 struct ext4_extent_header *eh;
529
530 eh = ext_inode_hdr(inode);
531 eh->eh_depth = 0;
532 eh->eh_entries = 0;
533 eh->eh_magic = EXT4_EXT_MAGIC;
534 eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode));
535 ext4_mark_inode_dirty(handle, inode);
536 ext4_ext_invalidate_cache(inode);
537 return 0;
538}
539
540struct ext4_ext_path *
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -0500541ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
542 struct ext4_ext_path *path)
Alex Tomasa86c6182006-10-11 01:21:03 -0700543{
544 struct ext4_extent_header *eh;
545 struct buffer_head *bh;
546 short int depth, i, ppos = 0, alloc = 0;
547
548 eh = ext_inode_hdr(inode);
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400549 depth = ext_depth(inode);
550 if (ext4_ext_check_header(inode, eh, depth))
Alex Tomasa86c6182006-10-11 01:21:03 -0700551 return ERR_PTR(-EIO);
552
Alex Tomasa86c6182006-10-11 01:21:03 -0700553
554 /* account possible depth increase */
555 if (!path) {
Avantika Mathur5d4958f2006-12-06 20:41:35 -0800556 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
Alex Tomasa86c6182006-10-11 01:21:03 -0700557 GFP_NOFS);
558 if (!path)
559 return ERR_PTR(-ENOMEM);
560 alloc = 1;
561 }
Alex Tomasa86c6182006-10-11 01:21:03 -0700562 path[0].p_hdr = eh;
Shen Feng1973adc2008-07-11 19:27:31 -0400563 path[0].p_bh = NULL;
Alex Tomasa86c6182006-10-11 01:21:03 -0700564
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400565 i = depth;
Alex Tomasa86c6182006-10-11 01:21:03 -0700566 /* walk through the tree */
567 while (i) {
568 ext_debug("depth %d: num %d, max %d\n",
569 ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400570
Alex Tomasa86c6182006-10-11 01:21:03 -0700571 ext4_ext_binsearch_idx(inode, path + ppos, block);
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700572 path[ppos].p_block = idx_pblock(path[ppos].p_idx);
Alex Tomasa86c6182006-10-11 01:21:03 -0700573 path[ppos].p_depth = i;
574 path[ppos].p_ext = NULL;
575
576 bh = sb_bread(inode->i_sb, path[ppos].p_block);
577 if (!bh)
578 goto err;
579
580 eh = ext_block_hdr(bh);
581 ppos++;
582 BUG_ON(ppos > depth);
583 path[ppos].p_bh = bh;
584 path[ppos].p_hdr = eh;
585 i--;
586
Alex Tomasc29c0ae2007-07-18 09:19:09 -0400587 if (ext4_ext_check_header(inode, eh, i))
Alex Tomasa86c6182006-10-11 01:21:03 -0700588 goto err;
589 }
590
591 path[ppos].p_depth = i;
Alex Tomasa86c6182006-10-11 01:21:03 -0700592 path[ppos].p_ext = NULL;
593 path[ppos].p_idx = NULL;
594
Alex Tomasa86c6182006-10-11 01:21:03 -0700595 /* find extent */
596 ext4_ext_binsearch(inode, path + ppos, block);
Shen Feng1973adc2008-07-11 19:27:31 -0400597 /* if not an empty leaf */
598 if (path[ppos].p_ext)
599 path[ppos].p_block = ext_pblock(path[ppos].p_ext);
Alex Tomasa86c6182006-10-11 01:21:03 -0700600
601 ext4_ext_show_path(inode, path);
602
603 return path;
604
605err:
606 ext4_ext_drop_refs(path);
607 if (alloc)
608 kfree(path);
609 return ERR_PTR(-EIO);
610}
611
612/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700613 * ext4_ext_insert_index:
614 * insert new index [@logical;@ptr] into the block at @curp;
615 * check where to insert: before @curp or after @curp
Alex Tomasa86c6182006-10-11 01:21:03 -0700616 */
617static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
618 struct ext4_ext_path *curp,
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700619 int logical, ext4_fsblk_t ptr)
Alex Tomasa86c6182006-10-11 01:21:03 -0700620{
621 struct ext4_extent_idx *ix;
622 int len, err;
623
Avantika Mathur7e028972006-12-06 20:41:33 -0800624 err = ext4_ext_get_access(handle, inode, curp);
625 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700626 return err;
627
628 BUG_ON(logical == le32_to_cpu(curp->p_idx->ei_block));
629 len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx;
630 if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
631 /* insert after */
632 if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) {
633 len = (len - 1) * sizeof(struct ext4_extent_idx);
634 len = len < 0 ? 0 : len;
Dmitry Monakhov26d535e2007-07-18 08:33:37 -0400635 ext_debug("insert new index %d after: %llu. "
Alex Tomasa86c6182006-10-11 01:21:03 -0700636 "move %d from 0x%p to 0x%p\n",
637 logical, ptr, len,
638 (curp->p_idx + 1), (curp->p_idx + 2));
639 memmove(curp->p_idx + 2, curp->p_idx + 1, len);
640 }
641 ix = curp->p_idx + 1;
642 } else {
643 /* insert before */
644 len = len * sizeof(struct ext4_extent_idx);
645 len = len < 0 ? 0 : len;
Dmitry Monakhov26d535e2007-07-18 08:33:37 -0400646 ext_debug("insert new index %d before: %llu. "
Alex Tomasa86c6182006-10-11 01:21:03 -0700647 "move %d from 0x%p to 0x%p\n",
648 logical, ptr, len,
649 curp->p_idx, (curp->p_idx + 1));
650 memmove(curp->p_idx + 1, curp->p_idx, len);
651 ix = curp->p_idx;
652 }
653
654 ix->ei_block = cpu_to_le32(logical);
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700655 ext4_idx_store_pblock(ix, ptr);
Marcin Slusarze8546d02008-04-17 10:38:59 -0400656 le16_add_cpu(&curp->p_hdr->eh_entries, 1);
Alex Tomasa86c6182006-10-11 01:21:03 -0700657
658 BUG_ON(le16_to_cpu(curp->p_hdr->eh_entries)
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400659 > le16_to_cpu(curp->p_hdr->eh_max));
Alex Tomasa86c6182006-10-11 01:21:03 -0700660 BUG_ON(ix > EXT_LAST_INDEX(curp->p_hdr));
661
662 err = ext4_ext_dirty(handle, inode, curp);
663 ext4_std_error(inode->i_sb, err);
664
665 return err;
666}
667
668/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700669 * ext4_ext_split:
670 * inserts new subtree into the path, using free index entry
671 * at depth @at:
672 * - allocates all needed blocks (new leaf and all intermediate index blocks)
673 * - makes decision where to split
674 * - moves remaining extents and index entries (right to the split point)
675 * into the newly allocated blocks
676 * - initializes subtree
Alex Tomasa86c6182006-10-11 01:21:03 -0700677 */
678static int ext4_ext_split(handle_t *handle, struct inode *inode,
679 struct ext4_ext_path *path,
680 struct ext4_extent *newext, int at)
681{
682 struct buffer_head *bh = NULL;
683 int depth = ext_depth(inode);
684 struct ext4_extent_header *neh;
685 struct ext4_extent_idx *fidx;
686 struct ext4_extent *ex;
687 int i = at, k, m, a;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700688 ext4_fsblk_t newblock, oldblock;
Alex Tomasa86c6182006-10-11 01:21:03 -0700689 __le32 border;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700690 ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
Alex Tomasa86c6182006-10-11 01:21:03 -0700691 int err = 0;
692
693 /* make decision: where to split? */
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700694 /* FIXME: now decision is simplest: at current extent */
Alex Tomasa86c6182006-10-11 01:21:03 -0700695
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700696 /* if current leaf will be split, then we should use
Alex Tomasa86c6182006-10-11 01:21:03 -0700697 * border from split point */
698 BUG_ON(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr));
699 if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
700 border = path[depth].p_ext[1].ee_block;
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700701 ext_debug("leaf will be split."
Alex Tomasa86c6182006-10-11 01:21:03 -0700702 " next leaf starts at %d\n",
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400703 le32_to_cpu(border));
Alex Tomasa86c6182006-10-11 01:21:03 -0700704 } else {
705 border = newext->ee_block;
706 ext_debug("leaf will be added."
707 " next leaf starts at %d\n",
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400708 le32_to_cpu(border));
Alex Tomasa86c6182006-10-11 01:21:03 -0700709 }
710
711 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700712 * If error occurs, then we break processing
713 * and mark filesystem read-only. index won't
Alex Tomasa86c6182006-10-11 01:21:03 -0700714 * be inserted and tree will be in consistent
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700715 * state. Next mount will repair buffers too.
Alex Tomasa86c6182006-10-11 01:21:03 -0700716 */
717
718 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700719 * Get array to track all allocated blocks.
720 * We need this to handle errors and free blocks
721 * upon them.
Alex Tomasa86c6182006-10-11 01:21:03 -0700722 */
Avantika Mathur5d4958f2006-12-06 20:41:35 -0800723 ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
Alex Tomasa86c6182006-10-11 01:21:03 -0700724 if (!ablocks)
725 return -ENOMEM;
Alex Tomasa86c6182006-10-11 01:21:03 -0700726
727 /* allocate all needed blocks */
728 ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
729 for (a = 0; a < depth - at; a++) {
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -0400730 newblock = ext4_ext_new_meta_block(handle, inode, path,
731 newext, &err);
Alex Tomasa86c6182006-10-11 01:21:03 -0700732 if (newblock == 0)
733 goto cleanup;
734 ablocks[a] = newblock;
735 }
736
737 /* initialize new leaf */
738 newblock = ablocks[--a];
739 BUG_ON(newblock == 0);
740 bh = sb_getblk(inode->i_sb, newblock);
741 if (!bh) {
742 err = -EIO;
743 goto cleanup;
744 }
745 lock_buffer(bh);
746
Avantika Mathur7e028972006-12-06 20:41:33 -0800747 err = ext4_journal_get_create_access(handle, bh);
748 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700749 goto cleanup;
750
751 neh = ext_block_hdr(bh);
752 neh->eh_entries = 0;
753 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode));
754 neh->eh_magic = EXT4_EXT_MAGIC;
755 neh->eh_depth = 0;
756 ex = EXT_FIRST_EXTENT(neh);
757
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700758 /* move remainder of path[depth] to the new leaf */
Alex Tomasa86c6182006-10-11 01:21:03 -0700759 BUG_ON(path[depth].p_hdr->eh_entries != path[depth].p_hdr->eh_max);
760 /* start copy from next extent */
761 /* TODO: we could do it by single memmove */
762 m = 0;
763 path[depth].p_ext++;
764 while (path[depth].p_ext <=
765 EXT_MAX_EXTENT(path[depth].p_hdr)) {
Mingming Cao2ae02102006-10-11 01:21:11 -0700766 ext_debug("move %d:%llu:%d in new leaf %llu\n",
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400767 le32_to_cpu(path[depth].p_ext->ee_block),
768 ext_pblock(path[depth].p_ext),
Amit Aroraa2df2a62007-07-17 21:42:41 -0400769 ext4_ext_get_actual_len(path[depth].p_ext),
Alex Tomasa86c6182006-10-11 01:21:03 -0700770 newblock);
771 /*memmove(ex++, path[depth].p_ext++,
772 sizeof(struct ext4_extent));
773 neh->eh_entries++;*/
774 path[depth].p_ext++;
775 m++;
776 }
777 if (m) {
778 memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m);
Marcin Slusarze8546d02008-04-17 10:38:59 -0400779 le16_add_cpu(&neh->eh_entries, m);
Alex Tomasa86c6182006-10-11 01:21:03 -0700780 }
781
782 set_buffer_uptodate(bh);
783 unlock_buffer(bh);
784
Frank Mayhar03901312009-01-07 00:06:22 -0500785 err = ext4_handle_dirty_metadata(handle, inode, bh);
Avantika Mathur7e028972006-12-06 20:41:33 -0800786 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700787 goto cleanup;
788 brelse(bh);
789 bh = NULL;
790
791 /* correct old leaf */
792 if (m) {
Avantika Mathur7e028972006-12-06 20:41:33 -0800793 err = ext4_ext_get_access(handle, inode, path + depth);
794 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700795 goto cleanup;
Marcin Slusarze8546d02008-04-17 10:38:59 -0400796 le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
Avantika Mathur7e028972006-12-06 20:41:33 -0800797 err = ext4_ext_dirty(handle, inode, path + depth);
798 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700799 goto cleanup;
800
801 }
802
803 /* create intermediate indexes */
804 k = depth - at - 1;
805 BUG_ON(k < 0);
806 if (k)
807 ext_debug("create %d intermediate indices\n", k);
808 /* insert new index into current index block */
809 /* current depth stored in i var */
810 i = depth - 1;
811 while (k--) {
812 oldblock = newblock;
813 newblock = ablocks[--a];
Eric Sandeenbba90742008-01-28 23:58:27 -0500814 bh = sb_getblk(inode->i_sb, newblock);
Alex Tomasa86c6182006-10-11 01:21:03 -0700815 if (!bh) {
816 err = -EIO;
817 goto cleanup;
818 }
819 lock_buffer(bh);
820
Avantika Mathur7e028972006-12-06 20:41:33 -0800821 err = ext4_journal_get_create_access(handle, bh);
822 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700823 goto cleanup;
824
825 neh = ext_block_hdr(bh);
826 neh->eh_entries = cpu_to_le16(1);
827 neh->eh_magic = EXT4_EXT_MAGIC;
828 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode));
829 neh->eh_depth = cpu_to_le16(depth - i);
830 fidx = EXT_FIRST_INDEX(neh);
831 fidx->ei_block = border;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700832 ext4_idx_store_pblock(fidx, oldblock);
Alex Tomasa86c6182006-10-11 01:21:03 -0700833
Eric Sandeenbba90742008-01-28 23:58:27 -0500834 ext_debug("int.index at %d (block %llu): %u -> %llu\n",
835 i, newblock, le32_to_cpu(border), oldblock);
Alex Tomasa86c6182006-10-11 01:21:03 -0700836 /* copy indexes */
837 m = 0;
838 path[i].p_idx++;
839
840 ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
841 EXT_MAX_INDEX(path[i].p_hdr));
842 BUG_ON(EXT_MAX_INDEX(path[i].p_hdr) !=
843 EXT_LAST_INDEX(path[i].p_hdr));
844 while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
Dmitry Monakhov26d535e2007-07-18 08:33:37 -0400845 ext_debug("%d: move %d:%llu in new index %llu\n", i,
Dave Kleikamp8c55e202007-05-24 13:04:54 -0400846 le32_to_cpu(path[i].p_idx->ei_block),
847 idx_pblock(path[i].p_idx),
848 newblock);
Alex Tomasa86c6182006-10-11 01:21:03 -0700849 /*memmove(++fidx, path[i].p_idx++,
850 sizeof(struct ext4_extent_idx));
851 neh->eh_entries++;
852 BUG_ON(neh->eh_entries > neh->eh_max);*/
853 path[i].p_idx++;
854 m++;
855 }
856 if (m) {
857 memmove(++fidx, path[i].p_idx - m,
858 sizeof(struct ext4_extent_idx) * m);
Marcin Slusarze8546d02008-04-17 10:38:59 -0400859 le16_add_cpu(&neh->eh_entries, m);
Alex Tomasa86c6182006-10-11 01:21:03 -0700860 }
861 set_buffer_uptodate(bh);
862 unlock_buffer(bh);
863
Frank Mayhar03901312009-01-07 00:06:22 -0500864 err = ext4_handle_dirty_metadata(handle, inode, bh);
Avantika Mathur7e028972006-12-06 20:41:33 -0800865 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700866 goto cleanup;
867 brelse(bh);
868 bh = NULL;
869
870 /* correct old index */
871 if (m) {
872 err = ext4_ext_get_access(handle, inode, path + i);
873 if (err)
874 goto cleanup;
Marcin Slusarze8546d02008-04-17 10:38:59 -0400875 le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
Alex Tomasa86c6182006-10-11 01:21:03 -0700876 err = ext4_ext_dirty(handle, inode, path + i);
877 if (err)
878 goto cleanup;
879 }
880
881 i--;
882 }
883
884 /* insert new index */
Alex Tomasa86c6182006-10-11 01:21:03 -0700885 err = ext4_ext_insert_index(handle, inode, path + at,
886 le32_to_cpu(border), newblock);
887
888cleanup:
889 if (bh) {
890 if (buffer_locked(bh))
891 unlock_buffer(bh);
892 brelse(bh);
893 }
894
895 if (err) {
896 /* free all allocated blocks in error case */
897 for (i = 0; i < depth; i++) {
898 if (!ablocks[i])
899 continue;
Alex Tomasc9de5602008-01-29 00:19:52 -0500900 ext4_free_blocks(handle, inode, ablocks[i], 1, 1);
Alex Tomasa86c6182006-10-11 01:21:03 -0700901 }
902 }
903 kfree(ablocks);
904
905 return err;
906}
907
908/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700909 * ext4_ext_grow_indepth:
910 * implements tree growing procedure:
911 * - allocates new block
912 * - moves top-level data (index block or leaf) into the new block
913 * - initializes new top-level, creating index that points to the
914 * just created block
Alex Tomasa86c6182006-10-11 01:21:03 -0700915 */
916static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
917 struct ext4_ext_path *path,
918 struct ext4_extent *newext)
919{
920 struct ext4_ext_path *curp = path;
921 struct ext4_extent_header *neh;
922 struct ext4_extent_idx *fidx;
923 struct buffer_head *bh;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700924 ext4_fsblk_t newblock;
Alex Tomasa86c6182006-10-11 01:21:03 -0700925 int err = 0;
926
Aneesh Kumar K.V654b4902008-07-11 19:27:31 -0400927 newblock = ext4_ext_new_meta_block(handle, inode, path, newext, &err);
Alex Tomasa86c6182006-10-11 01:21:03 -0700928 if (newblock == 0)
929 return err;
930
931 bh = sb_getblk(inode->i_sb, newblock);
932 if (!bh) {
933 err = -EIO;
934 ext4_std_error(inode->i_sb, err);
935 return err;
936 }
937 lock_buffer(bh);
938
Avantika Mathur7e028972006-12-06 20:41:33 -0800939 err = ext4_journal_get_create_access(handle, bh);
940 if (err) {
Alex Tomasa86c6182006-10-11 01:21:03 -0700941 unlock_buffer(bh);
942 goto out;
943 }
944
945 /* move top-level index/leaf into new block */
946 memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data));
947
948 /* set size of new block */
949 neh = ext_block_hdr(bh);
950 /* old root could have indexes or leaves
951 * so calculate e_max right way */
952 if (ext_depth(inode))
953 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode));
954 else
955 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode));
956 neh->eh_magic = EXT4_EXT_MAGIC;
957 set_buffer_uptodate(bh);
958 unlock_buffer(bh);
959
Frank Mayhar03901312009-01-07 00:06:22 -0500960 err = ext4_handle_dirty_metadata(handle, inode, bh);
Avantika Mathur7e028972006-12-06 20:41:33 -0800961 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700962 goto out;
963
964 /* create index in new top-level index: num,max,pointer */
Avantika Mathur7e028972006-12-06 20:41:33 -0800965 err = ext4_ext_get_access(handle, inode, curp);
966 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -0700967 goto out;
968
969 curp->p_hdr->eh_magic = EXT4_EXT_MAGIC;
970 curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode));
971 curp->p_hdr->eh_entries = cpu_to_le16(1);
972 curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr);
Dmitry Monakhove9f410b2007-07-18 09:09:15 -0400973
974 if (path[0].p_hdr->eh_depth)
975 curp->p_idx->ei_block =
976 EXT_FIRST_INDEX(path[0].p_hdr)->ei_block;
977 else
978 curp->p_idx->ei_block =
979 EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block;
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700980 ext4_idx_store_pblock(curp->p_idx, newblock);
Alex Tomasa86c6182006-10-11 01:21:03 -0700981
982 neh = ext_inode_hdr(inode);
983 fidx = EXT_FIRST_INDEX(neh);
Mingming Cao2ae02102006-10-11 01:21:11 -0700984 ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
Alex Tomasa86c6182006-10-11 01:21:03 -0700985 le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
Alex Tomasf65e6fb2006-10-11 01:21:05 -0700986 le32_to_cpu(fidx->ei_block), idx_pblock(fidx));
Alex Tomasa86c6182006-10-11 01:21:03 -0700987
988 neh->eh_depth = cpu_to_le16(path->p_depth + 1);
989 err = ext4_ext_dirty(handle, inode, curp);
990out:
991 brelse(bh);
992
993 return err;
994}
995
996/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -0700997 * ext4_ext_create_new_leaf:
998 * finds empty index and adds new leaf.
999 * if no free index is found, then it requests in-depth growing.
Alex Tomasa86c6182006-10-11 01:21:03 -07001000 */
1001static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1002 struct ext4_ext_path *path,
1003 struct ext4_extent *newext)
1004{
1005 struct ext4_ext_path *curp;
1006 int depth, i, err = 0;
1007
1008repeat:
1009 i = depth = ext_depth(inode);
1010
1011 /* walk up to the tree and look for free index entry */
1012 curp = path + depth;
1013 while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1014 i--;
1015 curp--;
1016 }
1017
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001018 /* we use already allocated block for index block,
1019 * so subsequent data blocks should be contiguous */
Alex Tomasa86c6182006-10-11 01:21:03 -07001020 if (EXT_HAS_FREE_INDEX(curp)) {
1021 /* if we found index with free entry, then use that
1022 * entry: create all needed subtree and add new leaf */
1023 err = ext4_ext_split(handle, inode, path, newext, i);
Shen Feng787e0982008-07-11 19:27:31 -04001024 if (err)
1025 goto out;
Alex Tomasa86c6182006-10-11 01:21:03 -07001026
1027 /* refill path */
1028 ext4_ext_drop_refs(path);
1029 path = ext4_ext_find_extent(inode,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001030 (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1031 path);
Alex Tomasa86c6182006-10-11 01:21:03 -07001032 if (IS_ERR(path))
1033 err = PTR_ERR(path);
1034 } else {
1035 /* tree is full, time to grow in depth */
1036 err = ext4_ext_grow_indepth(handle, inode, path, newext);
1037 if (err)
1038 goto out;
1039
1040 /* refill path */
1041 ext4_ext_drop_refs(path);
1042 path = ext4_ext_find_extent(inode,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001043 (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1044 path);
Alex Tomasa86c6182006-10-11 01:21:03 -07001045 if (IS_ERR(path)) {
1046 err = PTR_ERR(path);
1047 goto out;
1048 }
1049
1050 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001051 * only first (depth 0 -> 1) produces free space;
1052 * in all other cases we have to split the grown tree
Alex Tomasa86c6182006-10-11 01:21:03 -07001053 */
1054 depth = ext_depth(inode);
1055 if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001056 /* now we need to split */
Alex Tomasa86c6182006-10-11 01:21:03 -07001057 goto repeat;
1058 }
1059 }
1060
1061out:
1062 return err;
1063}
1064
1065/*
Alex Tomas1988b512008-01-28 23:58:27 -05001066 * search the closest allocated block to the left for *logical
1067 * and returns it at @logical + it's physical address at @phys
1068 * if *logical is the smallest allocated block, the function
1069 * returns 0 at @phys
1070 * return value contains 0 (success) or error code
1071 */
1072int
1073ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path,
1074 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1075{
1076 struct ext4_extent_idx *ix;
1077 struct ext4_extent *ex;
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001078 int depth, ee_len;
Alex Tomas1988b512008-01-28 23:58:27 -05001079
1080 BUG_ON(path == NULL);
1081 depth = path->p_depth;
1082 *phys = 0;
1083
1084 if (depth == 0 && path->p_ext == NULL)
1085 return 0;
1086
1087 /* usually extent in the path covers blocks smaller
1088 * then *logical, but it can be that extent is the
1089 * first one in the file */
1090
1091 ex = path[depth].p_ext;
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001092 ee_len = ext4_ext_get_actual_len(ex);
Alex Tomas1988b512008-01-28 23:58:27 -05001093 if (*logical < le32_to_cpu(ex->ee_block)) {
1094 BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
1095 while (--depth >= 0) {
1096 ix = path[depth].p_idx;
1097 BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
1098 }
1099 return 0;
1100 }
1101
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001102 BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len));
Alex Tomas1988b512008-01-28 23:58:27 -05001103
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001104 *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1105 *phys = ext_pblock(ex) + ee_len - 1;
Alex Tomas1988b512008-01-28 23:58:27 -05001106 return 0;
1107}
1108
1109/*
1110 * search the closest allocated block to the right for *logical
1111 * and returns it at @logical + it's physical address at @phys
1112 * if *logical is the smallest allocated block, the function
1113 * returns 0 at @phys
1114 * return value contains 0 (success) or error code
1115 */
1116int
1117ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path,
1118 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1119{
1120 struct buffer_head *bh = NULL;
1121 struct ext4_extent_header *eh;
1122 struct ext4_extent_idx *ix;
1123 struct ext4_extent *ex;
1124 ext4_fsblk_t block;
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001125 int depth, ee_len;
Alex Tomas1988b512008-01-28 23:58:27 -05001126
1127 BUG_ON(path == NULL);
1128 depth = path->p_depth;
1129 *phys = 0;
1130
1131 if (depth == 0 && path->p_ext == NULL)
1132 return 0;
1133
1134 /* usually extent in the path covers blocks smaller
1135 * then *logical, but it can be that extent is the
1136 * first one in the file */
1137
1138 ex = path[depth].p_ext;
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001139 ee_len = ext4_ext_get_actual_len(ex);
Alex Tomas1988b512008-01-28 23:58:27 -05001140 if (*logical < le32_to_cpu(ex->ee_block)) {
1141 BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
1142 while (--depth >= 0) {
1143 ix = path[depth].p_idx;
1144 BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
1145 }
1146 *logical = le32_to_cpu(ex->ee_block);
1147 *phys = ext_pblock(ex);
1148 return 0;
1149 }
1150
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001151 BUG_ON(*logical < (le32_to_cpu(ex->ee_block) + ee_len));
Alex Tomas1988b512008-01-28 23:58:27 -05001152
1153 if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1154 /* next allocated block in this leaf */
1155 ex++;
1156 *logical = le32_to_cpu(ex->ee_block);
1157 *phys = ext_pblock(ex);
1158 return 0;
1159 }
1160
1161 /* go up and search for index to the right */
1162 while (--depth >= 0) {
1163 ix = path[depth].p_idx;
1164 if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
Wu Fengguang25f1ee32008-11-25 17:24:23 -05001165 goto got_index;
Alex Tomas1988b512008-01-28 23:58:27 -05001166 }
1167
Wu Fengguang25f1ee32008-11-25 17:24:23 -05001168 /* we've gone up to the root and found no index to the right */
1169 return 0;
Alex Tomas1988b512008-01-28 23:58:27 -05001170
Wu Fengguang25f1ee32008-11-25 17:24:23 -05001171got_index:
Alex Tomas1988b512008-01-28 23:58:27 -05001172 /* we've found index to the right, let's
1173 * follow it and find the closest allocated
1174 * block to the right */
1175 ix++;
1176 block = idx_pblock(ix);
1177 while (++depth < path->p_depth) {
1178 bh = sb_bread(inode->i_sb, block);
1179 if (bh == NULL)
1180 return -EIO;
1181 eh = ext_block_hdr(bh);
1182 if (ext4_ext_check_header(inode, eh, depth)) {
1183 put_bh(bh);
1184 return -EIO;
1185 }
1186 ix = EXT_FIRST_INDEX(eh);
1187 block = idx_pblock(ix);
1188 put_bh(bh);
1189 }
1190
1191 bh = sb_bread(inode->i_sb, block);
1192 if (bh == NULL)
1193 return -EIO;
1194 eh = ext_block_hdr(bh);
1195 if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) {
1196 put_bh(bh);
1197 return -EIO;
1198 }
1199 ex = EXT_FIRST_EXTENT(eh);
1200 *logical = le32_to_cpu(ex->ee_block);
1201 *phys = ext_pblock(ex);
1202 put_bh(bh);
1203 return 0;
Alex Tomas1988b512008-01-28 23:58:27 -05001204}
1205
1206/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001207 * ext4_ext_next_allocated_block:
1208 * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1209 * NOTE: it considers block number from index entry as
1210 * allocated block. Thus, index entries have to be consistent
1211 * with leaves.
Alex Tomasa86c6182006-10-11 01:21:03 -07001212 */
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001213static ext4_lblk_t
Alex Tomasa86c6182006-10-11 01:21:03 -07001214ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1215{
1216 int depth;
1217
1218 BUG_ON(path == NULL);
1219 depth = path->p_depth;
1220
1221 if (depth == 0 && path->p_ext == NULL)
1222 return EXT_MAX_BLOCK;
1223
1224 while (depth >= 0) {
1225 if (depth == path->p_depth) {
1226 /* leaf */
1227 if (path[depth].p_ext !=
1228 EXT_LAST_EXTENT(path[depth].p_hdr))
1229 return le32_to_cpu(path[depth].p_ext[1].ee_block);
1230 } else {
1231 /* index */
1232 if (path[depth].p_idx !=
1233 EXT_LAST_INDEX(path[depth].p_hdr))
1234 return le32_to_cpu(path[depth].p_idx[1].ei_block);
1235 }
1236 depth--;
1237 }
1238
1239 return EXT_MAX_BLOCK;
1240}
1241
1242/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001243 * ext4_ext_next_leaf_block:
Alex Tomasa86c6182006-10-11 01:21:03 -07001244 * returns first allocated block from next leaf or EXT_MAX_BLOCK
1245 */
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001246static ext4_lblk_t ext4_ext_next_leaf_block(struct inode *inode,
Andrew Morton63f57932006-10-11 01:21:24 -07001247 struct ext4_ext_path *path)
Alex Tomasa86c6182006-10-11 01:21:03 -07001248{
1249 int depth;
1250
1251 BUG_ON(path == NULL);
1252 depth = path->p_depth;
1253
1254 /* zero-tree has no leaf blocks at all */
1255 if (depth == 0)
1256 return EXT_MAX_BLOCK;
1257
1258 /* go to index block */
1259 depth--;
1260
1261 while (depth >= 0) {
1262 if (path[depth].p_idx !=
1263 EXT_LAST_INDEX(path[depth].p_hdr))
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001264 return (ext4_lblk_t)
1265 le32_to_cpu(path[depth].p_idx[1].ei_block);
Alex Tomasa86c6182006-10-11 01:21:03 -07001266 depth--;
1267 }
1268
1269 return EXT_MAX_BLOCK;
1270}
1271
1272/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001273 * ext4_ext_correct_indexes:
1274 * if leaf gets modified and modified extent is first in the leaf,
1275 * then we have to correct all indexes above.
Alex Tomasa86c6182006-10-11 01:21:03 -07001276 * TODO: do we need to correct tree in all cases?
1277 */
Aneesh Kumar K.V1d03ec92008-01-28 23:58:27 -05001278static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
Alex Tomasa86c6182006-10-11 01:21:03 -07001279 struct ext4_ext_path *path)
1280{
1281 struct ext4_extent_header *eh;
1282 int depth = ext_depth(inode);
1283 struct ext4_extent *ex;
1284 __le32 border;
1285 int k, err = 0;
1286
1287 eh = path[depth].p_hdr;
1288 ex = path[depth].p_ext;
1289 BUG_ON(ex == NULL);
1290 BUG_ON(eh == NULL);
1291
1292 if (depth == 0) {
1293 /* there is no tree at all */
1294 return 0;
1295 }
1296
1297 if (ex != EXT_FIRST_EXTENT(eh)) {
1298 /* we correct tree if first leaf got modified only */
1299 return 0;
1300 }
1301
1302 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001303 * TODO: we need correction if border is smaller than current one
Alex Tomasa86c6182006-10-11 01:21:03 -07001304 */
1305 k = depth - 1;
1306 border = path[depth].p_ext->ee_block;
Avantika Mathur7e028972006-12-06 20:41:33 -08001307 err = ext4_ext_get_access(handle, inode, path + k);
1308 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001309 return err;
1310 path[k].p_idx->ei_block = border;
Avantika Mathur7e028972006-12-06 20:41:33 -08001311 err = ext4_ext_dirty(handle, inode, path + k);
1312 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001313 return err;
1314
1315 while (k--) {
1316 /* change all left-side indexes */
1317 if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1318 break;
Avantika Mathur7e028972006-12-06 20:41:33 -08001319 err = ext4_ext_get_access(handle, inode, path + k);
1320 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001321 break;
1322 path[k].p_idx->ei_block = border;
Avantika Mathur7e028972006-12-06 20:41:33 -08001323 err = ext4_ext_dirty(handle, inode, path + k);
1324 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001325 break;
1326 }
1327
1328 return err;
1329}
1330
Avantika Mathur09b88252006-12-06 20:41:36 -08001331static int
Alex Tomasa86c6182006-10-11 01:21:03 -07001332ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1333 struct ext4_extent *ex2)
1334{
Amit Arora749269f2007-07-18 09:02:56 -04001335 unsigned short ext1_ee_len, ext2_ee_len, max_len;
Amit Aroraa2df2a62007-07-17 21:42:41 -04001336
1337 /*
1338 * Make sure that either both extents are uninitialized, or
1339 * both are _not_.
1340 */
1341 if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
1342 return 0;
1343
Amit Arora749269f2007-07-18 09:02:56 -04001344 if (ext4_ext_is_uninitialized(ex1))
1345 max_len = EXT_UNINIT_MAX_LEN;
1346 else
1347 max_len = EXT_INIT_MAX_LEN;
1348
Amit Aroraa2df2a62007-07-17 21:42:41 -04001349 ext1_ee_len = ext4_ext_get_actual_len(ex1);
1350 ext2_ee_len = ext4_ext_get_actual_len(ex2);
1351
1352 if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
Andrew Morton63f57932006-10-11 01:21:24 -07001353 le32_to_cpu(ex2->ee_block))
Alex Tomasa86c6182006-10-11 01:21:03 -07001354 return 0;
1355
Suparna Bhattacharya471d4012006-10-11 01:21:06 -07001356 /*
1357 * To allow future support for preallocated extents to be added
1358 * as an RO_COMPAT feature, refuse to merge to extents if
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001359 * this can result in the top bit of ee_len being set.
Suparna Bhattacharya471d4012006-10-11 01:21:06 -07001360 */
Amit Arora749269f2007-07-18 09:02:56 -04001361 if (ext1_ee_len + ext2_ee_len > max_len)
Suparna Bhattacharya471d4012006-10-11 01:21:06 -07001362 return 0;
Robert P. J. Daybbf2f9f2007-02-17 19:20:16 +01001363#ifdef AGGRESSIVE_TEST
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05001364 if (ext1_ee_len >= 4)
Alex Tomasa86c6182006-10-11 01:21:03 -07001365 return 0;
1366#endif
1367
Amit Aroraa2df2a62007-07-17 21:42:41 -04001368 if (ext_pblock(ex1) + ext1_ee_len == ext_pblock(ex2))
Alex Tomasa86c6182006-10-11 01:21:03 -07001369 return 1;
1370 return 0;
1371}
1372
1373/*
Amit Arora56055d32007-07-17 21:42:38 -04001374 * This function tries to merge the "ex" extent to the next extent in the tree.
1375 * It always tries to merge towards right. If you want to merge towards
1376 * left, pass "ex - 1" as argument instead of "ex".
1377 * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1378 * 1 if they got merged.
1379 */
1380int ext4_ext_try_to_merge(struct inode *inode,
1381 struct ext4_ext_path *path,
1382 struct ext4_extent *ex)
1383{
1384 struct ext4_extent_header *eh;
1385 unsigned int depth, len;
1386 int merge_done = 0;
1387 int uninitialized = 0;
1388
1389 depth = ext_depth(inode);
1390 BUG_ON(path[depth].p_hdr == NULL);
1391 eh = path[depth].p_hdr;
1392
1393 while (ex < EXT_LAST_EXTENT(eh)) {
1394 if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1395 break;
1396 /* merge with next extent! */
1397 if (ext4_ext_is_uninitialized(ex))
1398 uninitialized = 1;
1399 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1400 + ext4_ext_get_actual_len(ex + 1));
1401 if (uninitialized)
1402 ext4_ext_mark_uninitialized(ex);
1403
1404 if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1405 len = (EXT_LAST_EXTENT(eh) - ex - 1)
1406 * sizeof(struct ext4_extent);
1407 memmove(ex + 1, ex + 2, len);
1408 }
Marcin Slusarze8546d02008-04-17 10:38:59 -04001409 le16_add_cpu(&eh->eh_entries, -1);
Amit Arora56055d32007-07-17 21:42:38 -04001410 merge_done = 1;
1411 WARN_ON(eh->eh_entries == 0);
1412 if (!eh->eh_entries)
1413 ext4_error(inode->i_sb, "ext4_ext_try_to_merge",
1414 "inode#%lu, eh->eh_entries = 0!", inode->i_ino);
1415 }
1416
1417 return merge_done;
1418}
1419
1420/*
Amit Arora25d14f92007-05-24 13:04:13 -04001421 * check if a portion of the "newext" extent overlaps with an
1422 * existing extent.
1423 *
1424 * If there is an overlap discovered, it updates the length of the newext
1425 * such that there will be no overlap, and then returns 1.
1426 * If there is no overlap found, it returns 0.
1427 */
1428unsigned int ext4_ext_check_overlap(struct inode *inode,
1429 struct ext4_extent *newext,
1430 struct ext4_ext_path *path)
1431{
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001432 ext4_lblk_t b1, b2;
Amit Arora25d14f92007-05-24 13:04:13 -04001433 unsigned int depth, len1;
1434 unsigned int ret = 0;
1435
1436 b1 = le32_to_cpu(newext->ee_block);
Amit Aroraa2df2a62007-07-17 21:42:41 -04001437 len1 = ext4_ext_get_actual_len(newext);
Amit Arora25d14f92007-05-24 13:04:13 -04001438 depth = ext_depth(inode);
1439 if (!path[depth].p_ext)
1440 goto out;
1441 b2 = le32_to_cpu(path[depth].p_ext->ee_block);
1442
1443 /*
1444 * get the next allocated block if the extent in the path
Theodore Ts'o2b2d6d02008-07-26 16:15:44 -04001445 * is before the requested block(s)
Amit Arora25d14f92007-05-24 13:04:13 -04001446 */
1447 if (b2 < b1) {
1448 b2 = ext4_ext_next_allocated_block(path);
1449 if (b2 == EXT_MAX_BLOCK)
1450 goto out;
1451 }
1452
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001453 /* check for wrap through zero on extent logical start block*/
Amit Arora25d14f92007-05-24 13:04:13 -04001454 if (b1 + len1 < b1) {
1455 len1 = EXT_MAX_BLOCK - b1;
1456 newext->ee_len = cpu_to_le16(len1);
1457 ret = 1;
1458 }
1459
1460 /* check for overlap */
1461 if (b1 + len1 > b2) {
1462 newext->ee_len = cpu_to_le16(b2 - b1);
1463 ret = 1;
1464 }
1465out:
1466 return ret;
1467}
1468
1469/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001470 * ext4_ext_insert_extent:
1471 * tries to merge requsted extent into the existing extent or
1472 * inserts requested extent as new one into the tree,
1473 * creating new leaf in the no-space case.
Alex Tomasa86c6182006-10-11 01:21:03 -07001474 */
1475int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1476 struct ext4_ext_path *path,
1477 struct ext4_extent *newext)
1478{
Theodore Ts'oaf5bc922008-09-08 22:25:24 -04001479 struct ext4_extent_header *eh;
Alex Tomasa86c6182006-10-11 01:21:03 -07001480 struct ext4_extent *ex, *fex;
1481 struct ext4_extent *nearex; /* nearest extent */
1482 struct ext4_ext_path *npath = NULL;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001483 int depth, len, err;
1484 ext4_lblk_t next;
Amit Aroraa2df2a62007-07-17 21:42:41 -04001485 unsigned uninitialized = 0;
Alex Tomasa86c6182006-10-11 01:21:03 -07001486
Amit Aroraa2df2a62007-07-17 21:42:41 -04001487 BUG_ON(ext4_ext_get_actual_len(newext) == 0);
Alex Tomasa86c6182006-10-11 01:21:03 -07001488 depth = ext_depth(inode);
1489 ex = path[depth].p_ext;
1490 BUG_ON(path[depth].p_hdr == NULL);
1491
1492 /* try to insert block into found extent and return */
1493 if (ex && ext4_can_extents_be_merged(inode, ex, newext)) {
Mingming Cao2ae02102006-10-11 01:21:11 -07001494 ext_debug("append %d block to %d:%d (from %llu)\n",
Amit Aroraa2df2a62007-07-17 21:42:41 -04001495 ext4_ext_get_actual_len(newext),
Alex Tomasa86c6182006-10-11 01:21:03 -07001496 le32_to_cpu(ex->ee_block),
Amit Aroraa2df2a62007-07-17 21:42:41 -04001497 ext4_ext_get_actual_len(ex), ext_pblock(ex));
Avantika Mathur7e028972006-12-06 20:41:33 -08001498 err = ext4_ext_get_access(handle, inode, path + depth);
1499 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001500 return err;
Amit Aroraa2df2a62007-07-17 21:42:41 -04001501
1502 /*
1503 * ext4_can_extents_be_merged should have checked that either
1504 * both extents are uninitialized, or both aren't. Thus we
1505 * need to check only one of them here.
1506 */
1507 if (ext4_ext_is_uninitialized(ex))
1508 uninitialized = 1;
1509 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1510 + ext4_ext_get_actual_len(newext));
1511 if (uninitialized)
1512 ext4_ext_mark_uninitialized(ex);
Alex Tomasa86c6182006-10-11 01:21:03 -07001513 eh = path[depth].p_hdr;
1514 nearex = ex;
1515 goto merge;
1516 }
1517
1518repeat:
1519 depth = ext_depth(inode);
1520 eh = path[depth].p_hdr;
1521 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
1522 goto has_space;
1523
1524 /* probably next leaf has space for us? */
1525 fex = EXT_LAST_EXTENT(eh);
1526 next = ext4_ext_next_leaf_block(inode, path);
1527 if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block)
1528 && next != EXT_MAX_BLOCK) {
1529 ext_debug("next leaf block - %d\n", next);
1530 BUG_ON(npath != NULL);
1531 npath = ext4_ext_find_extent(inode, next, NULL);
1532 if (IS_ERR(npath))
1533 return PTR_ERR(npath);
1534 BUG_ON(npath->p_depth != path->p_depth);
1535 eh = npath[depth].p_hdr;
1536 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
1537 ext_debug("next leaf isnt full(%d)\n",
1538 le16_to_cpu(eh->eh_entries));
1539 path = npath;
1540 goto repeat;
1541 }
1542 ext_debug("next leaf has no free space(%d,%d)\n",
1543 le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
1544 }
1545
1546 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001547 * There is no free space in the found leaf.
1548 * We're gonna add a new leaf in the tree.
Alex Tomasa86c6182006-10-11 01:21:03 -07001549 */
1550 err = ext4_ext_create_new_leaf(handle, inode, path, newext);
1551 if (err)
1552 goto cleanup;
1553 depth = ext_depth(inode);
1554 eh = path[depth].p_hdr;
1555
1556has_space:
1557 nearex = path[depth].p_ext;
1558
Avantika Mathur7e028972006-12-06 20:41:33 -08001559 err = ext4_ext_get_access(handle, inode, path + depth);
1560 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001561 goto cleanup;
1562
1563 if (!nearex) {
1564 /* there is no extent in this leaf, create first one */
Mingming Cao2ae02102006-10-11 01:21:11 -07001565 ext_debug("first extent in the leaf: %d:%llu:%d\n",
Dave Kleikamp8c55e202007-05-24 13:04:54 -04001566 le32_to_cpu(newext->ee_block),
1567 ext_pblock(newext),
Amit Aroraa2df2a62007-07-17 21:42:41 -04001568 ext4_ext_get_actual_len(newext));
Alex Tomasa86c6182006-10-11 01:21:03 -07001569 path[depth].p_ext = EXT_FIRST_EXTENT(eh);
1570 } else if (le32_to_cpu(newext->ee_block)
Dave Kleikamp8c55e202007-05-24 13:04:54 -04001571 > le32_to_cpu(nearex->ee_block)) {
Alex Tomasa86c6182006-10-11 01:21:03 -07001572/* BUG_ON(newext->ee_block == nearex->ee_block); */
1573 if (nearex != EXT_LAST_EXTENT(eh)) {
1574 len = EXT_MAX_EXTENT(eh) - nearex;
1575 len = (len - 1) * sizeof(struct ext4_extent);
1576 len = len < 0 ? 0 : len;
Mingming Cao2ae02102006-10-11 01:21:11 -07001577 ext_debug("insert %d:%llu:%d after: nearest 0x%p, "
Alex Tomasa86c6182006-10-11 01:21:03 -07001578 "move %d from 0x%p to 0x%p\n",
Dave Kleikamp8c55e202007-05-24 13:04:54 -04001579 le32_to_cpu(newext->ee_block),
1580 ext_pblock(newext),
Amit Aroraa2df2a62007-07-17 21:42:41 -04001581 ext4_ext_get_actual_len(newext),
Alex Tomasa86c6182006-10-11 01:21:03 -07001582 nearex, len, nearex + 1, nearex + 2);
1583 memmove(nearex + 2, nearex + 1, len);
1584 }
1585 path[depth].p_ext = nearex + 1;
1586 } else {
1587 BUG_ON(newext->ee_block == nearex->ee_block);
1588 len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1589 len = len < 0 ? 0 : len;
Mingming Cao2ae02102006-10-11 01:21:11 -07001590 ext_debug("insert %d:%llu:%d before: nearest 0x%p, "
Alex Tomasa86c6182006-10-11 01:21:03 -07001591 "move %d from 0x%p to 0x%p\n",
1592 le32_to_cpu(newext->ee_block),
Alex Tomasf65e6fb2006-10-11 01:21:05 -07001593 ext_pblock(newext),
Amit Aroraa2df2a62007-07-17 21:42:41 -04001594 ext4_ext_get_actual_len(newext),
Alex Tomasa86c6182006-10-11 01:21:03 -07001595 nearex, len, nearex + 1, nearex + 2);
1596 memmove(nearex + 1, nearex, len);
1597 path[depth].p_ext = nearex;
1598 }
1599
Marcin Slusarze8546d02008-04-17 10:38:59 -04001600 le16_add_cpu(&eh->eh_entries, 1);
Alex Tomasa86c6182006-10-11 01:21:03 -07001601 nearex = path[depth].p_ext;
1602 nearex->ee_block = newext->ee_block;
Aneesh Kumar K.Vb3776112007-10-16 18:38:25 -04001603 ext4_ext_store_pblock(nearex, ext_pblock(newext));
Alex Tomasa86c6182006-10-11 01:21:03 -07001604 nearex->ee_len = newext->ee_len;
Alex Tomasa86c6182006-10-11 01:21:03 -07001605
1606merge:
1607 /* try to merge extents to the right */
Amit Arora56055d32007-07-17 21:42:38 -04001608 ext4_ext_try_to_merge(inode, path, nearex);
Alex Tomasa86c6182006-10-11 01:21:03 -07001609
1610 /* try to merge extents to the left */
1611
1612 /* time to correct all indexes above */
1613 err = ext4_ext_correct_indexes(handle, inode, path);
1614 if (err)
1615 goto cleanup;
1616
1617 err = ext4_ext_dirty(handle, inode, path + depth);
1618
1619cleanup:
1620 if (npath) {
1621 ext4_ext_drop_refs(npath);
1622 kfree(npath);
1623 }
Alex Tomasa86c6182006-10-11 01:21:03 -07001624 ext4_ext_invalidate_cache(inode);
1625 return err;
1626}
1627
Eric Sandeen6873fa02008-10-07 00:46:36 -04001628int ext4_ext_walk_space(struct inode *inode, ext4_lblk_t block,
1629 ext4_lblk_t num, ext_prepare_callback func,
1630 void *cbdata)
1631{
1632 struct ext4_ext_path *path = NULL;
1633 struct ext4_ext_cache cbex;
1634 struct ext4_extent *ex;
1635 ext4_lblk_t next, start = 0, end = 0;
1636 ext4_lblk_t last = block + num;
1637 int depth, exists, err = 0;
1638
1639 BUG_ON(func == NULL);
1640 BUG_ON(inode == NULL);
1641
1642 while (block < last && block != EXT_MAX_BLOCK) {
1643 num = last - block;
1644 /* find extent for this block */
1645 path = ext4_ext_find_extent(inode, block, path);
1646 if (IS_ERR(path)) {
1647 err = PTR_ERR(path);
1648 path = NULL;
1649 break;
1650 }
1651
1652 depth = ext_depth(inode);
1653 BUG_ON(path[depth].p_hdr == NULL);
1654 ex = path[depth].p_ext;
1655 next = ext4_ext_next_allocated_block(path);
1656
1657 exists = 0;
1658 if (!ex) {
1659 /* there is no extent yet, so try to allocate
1660 * all requested space */
1661 start = block;
1662 end = block + num;
1663 } else if (le32_to_cpu(ex->ee_block) > block) {
1664 /* need to allocate space before found extent */
1665 start = block;
1666 end = le32_to_cpu(ex->ee_block);
1667 if (block + num < end)
1668 end = block + num;
1669 } else if (block >= le32_to_cpu(ex->ee_block)
1670 + ext4_ext_get_actual_len(ex)) {
1671 /* need to allocate space after found extent */
1672 start = block;
1673 end = block + num;
1674 if (end >= next)
1675 end = next;
1676 } else if (block >= le32_to_cpu(ex->ee_block)) {
1677 /*
1678 * some part of requested space is covered
1679 * by found extent
1680 */
1681 start = block;
1682 end = le32_to_cpu(ex->ee_block)
1683 + ext4_ext_get_actual_len(ex);
1684 if (block + num < end)
1685 end = block + num;
1686 exists = 1;
1687 } else {
1688 BUG();
1689 }
1690 BUG_ON(end <= start);
1691
1692 if (!exists) {
1693 cbex.ec_block = start;
1694 cbex.ec_len = end - start;
1695 cbex.ec_start = 0;
1696 cbex.ec_type = EXT4_EXT_CACHE_GAP;
1697 } else {
1698 cbex.ec_block = le32_to_cpu(ex->ee_block);
1699 cbex.ec_len = ext4_ext_get_actual_len(ex);
1700 cbex.ec_start = ext_pblock(ex);
1701 cbex.ec_type = EXT4_EXT_CACHE_EXTENT;
1702 }
1703
1704 BUG_ON(cbex.ec_len == 0);
1705 err = func(inode, path, &cbex, ex, cbdata);
1706 ext4_ext_drop_refs(path);
1707
1708 if (err < 0)
1709 break;
1710
1711 if (err == EXT_REPEAT)
1712 continue;
1713 else if (err == EXT_BREAK) {
1714 err = 0;
1715 break;
1716 }
1717
1718 if (ext_depth(inode) != depth) {
1719 /* depth was changed. we have to realloc path */
1720 kfree(path);
1721 path = NULL;
1722 }
1723
1724 block = cbex.ec_block + cbex.ec_len;
1725 }
1726
1727 if (path) {
1728 ext4_ext_drop_refs(path);
1729 kfree(path);
1730 }
1731
1732 return err;
1733}
1734
Avantika Mathur09b88252006-12-06 20:41:36 -08001735static void
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001736ext4_ext_put_in_cache(struct inode *inode, ext4_lblk_t block,
Mingming Caodd545672007-07-31 00:37:46 -07001737 __u32 len, ext4_fsblk_t start, int type)
Alex Tomasa86c6182006-10-11 01:21:03 -07001738{
1739 struct ext4_ext_cache *cex;
1740 BUG_ON(len == 0);
1741 cex = &EXT4_I(inode)->i_cached_extent;
1742 cex->ec_type = type;
1743 cex->ec_block = block;
1744 cex->ec_len = len;
1745 cex->ec_start = start;
1746}
1747
1748/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001749 * ext4_ext_put_gap_in_cache:
1750 * calculate boundaries of the gap that the requested block fits into
Alex Tomasa86c6182006-10-11 01:21:03 -07001751 * and cache this gap
1752 */
Avantika Mathur09b88252006-12-06 20:41:36 -08001753static void
Alex Tomasa86c6182006-10-11 01:21:03 -07001754ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001755 ext4_lblk_t block)
Alex Tomasa86c6182006-10-11 01:21:03 -07001756{
1757 int depth = ext_depth(inode);
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001758 unsigned long len;
1759 ext4_lblk_t lblock;
Alex Tomasa86c6182006-10-11 01:21:03 -07001760 struct ext4_extent *ex;
1761
1762 ex = path[depth].p_ext;
1763 if (ex == NULL) {
1764 /* there is no extent yet, so gap is [0;-] */
1765 lblock = 0;
1766 len = EXT_MAX_BLOCK;
1767 ext_debug("cache gap(whole file):");
1768 } else if (block < le32_to_cpu(ex->ee_block)) {
1769 lblock = block;
1770 len = le32_to_cpu(ex->ee_block) - block;
Eric Sandeenbba90742008-01-28 23:58:27 -05001771 ext_debug("cache gap(before): %u [%u:%u]",
1772 block,
1773 le32_to_cpu(ex->ee_block),
1774 ext4_ext_get_actual_len(ex));
Alex Tomasa86c6182006-10-11 01:21:03 -07001775 } else if (block >= le32_to_cpu(ex->ee_block)
Amit Aroraa2df2a62007-07-17 21:42:41 -04001776 + ext4_ext_get_actual_len(ex)) {
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001777 ext4_lblk_t next;
Dave Kleikamp8c55e202007-05-24 13:04:54 -04001778 lblock = le32_to_cpu(ex->ee_block)
Amit Aroraa2df2a62007-07-17 21:42:41 -04001779 + ext4_ext_get_actual_len(ex);
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001780
1781 next = ext4_ext_next_allocated_block(path);
Eric Sandeenbba90742008-01-28 23:58:27 -05001782 ext_debug("cache gap(after): [%u:%u] %u",
1783 le32_to_cpu(ex->ee_block),
1784 ext4_ext_get_actual_len(ex),
1785 block);
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001786 BUG_ON(next == lblock);
1787 len = next - lblock;
Alex Tomasa86c6182006-10-11 01:21:03 -07001788 } else {
1789 lblock = len = 0;
1790 BUG();
1791 }
1792
Eric Sandeenbba90742008-01-28 23:58:27 -05001793 ext_debug(" -> %u:%lu\n", lblock, len);
Alex Tomasa86c6182006-10-11 01:21:03 -07001794 ext4_ext_put_in_cache(inode, lblock, len, 0, EXT4_EXT_CACHE_GAP);
1795}
1796
Avantika Mathur09b88252006-12-06 20:41:36 -08001797static int
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001798ext4_ext_in_cache(struct inode *inode, ext4_lblk_t block,
Alex Tomasa86c6182006-10-11 01:21:03 -07001799 struct ext4_extent *ex)
1800{
1801 struct ext4_ext_cache *cex;
1802
1803 cex = &EXT4_I(inode)->i_cached_extent;
1804
1805 /* has cache valid data? */
1806 if (cex->ec_type == EXT4_EXT_CACHE_NO)
1807 return EXT4_EXT_CACHE_NO;
1808
1809 BUG_ON(cex->ec_type != EXT4_EXT_CACHE_GAP &&
1810 cex->ec_type != EXT4_EXT_CACHE_EXTENT);
1811 if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) {
Dave Kleikamp8c55e202007-05-24 13:04:54 -04001812 ex->ee_block = cpu_to_le32(cex->ec_block);
Alex Tomasf65e6fb2006-10-11 01:21:05 -07001813 ext4_ext_store_pblock(ex, cex->ec_start);
Dave Kleikamp8c55e202007-05-24 13:04:54 -04001814 ex->ee_len = cpu_to_le16(cex->ec_len);
Eric Sandeenbba90742008-01-28 23:58:27 -05001815 ext_debug("%u cached by %u:%u:%llu\n",
1816 block,
1817 cex->ec_block, cex->ec_len, cex->ec_start);
Alex Tomasa86c6182006-10-11 01:21:03 -07001818 return cex->ec_type;
1819 }
1820
1821 /* not in cache */
1822 return EXT4_EXT_CACHE_NO;
1823}
1824
1825/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07001826 * ext4_ext_rm_idx:
1827 * removes index from the index block.
1828 * It's used in truncate case only, thus all requests are for
1829 * last index in the block only.
Alex Tomasa86c6182006-10-11 01:21:03 -07001830 */
Aneesh Kumar K.V1d03ec92008-01-28 23:58:27 -05001831static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
Alex Tomasa86c6182006-10-11 01:21:03 -07001832 struct ext4_ext_path *path)
1833{
1834 struct buffer_head *bh;
1835 int err;
Alex Tomasf65e6fb2006-10-11 01:21:05 -07001836 ext4_fsblk_t leaf;
Alex Tomasa86c6182006-10-11 01:21:03 -07001837
1838 /* free index block */
1839 path--;
Alex Tomasf65e6fb2006-10-11 01:21:05 -07001840 leaf = idx_pblock(path->p_idx);
Alex Tomasa86c6182006-10-11 01:21:03 -07001841 BUG_ON(path->p_hdr->eh_entries == 0);
Avantika Mathur7e028972006-12-06 20:41:33 -08001842 err = ext4_ext_get_access(handle, inode, path);
1843 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001844 return err;
Marcin Slusarze8546d02008-04-17 10:38:59 -04001845 le16_add_cpu(&path->p_hdr->eh_entries, -1);
Avantika Mathur7e028972006-12-06 20:41:33 -08001846 err = ext4_ext_dirty(handle, inode, path);
1847 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07001848 return err;
Mingming Cao2ae02102006-10-11 01:21:11 -07001849 ext_debug("index is empty, remove it, free block %llu\n", leaf);
Alex Tomasa86c6182006-10-11 01:21:03 -07001850 bh = sb_find_get_block(inode->i_sb, leaf);
1851 ext4_forget(handle, 1, inode, bh, leaf);
Alex Tomasc9de5602008-01-29 00:19:52 -05001852 ext4_free_blocks(handle, inode, leaf, 1, 1);
Alex Tomasa86c6182006-10-11 01:21:03 -07001853 return err;
1854}
1855
1856/*
Mingming Caoee12b632008-08-19 22:16:05 -04001857 * ext4_ext_calc_credits_for_single_extent:
1858 * This routine returns max. credits that needed to insert an extent
1859 * to the extent tree.
1860 * When pass the actual path, the caller should calculate credits
1861 * under i_data_sem.
Alex Tomasa86c6182006-10-11 01:21:03 -07001862 */
Mingming Cao525f4ed2008-08-19 22:15:58 -04001863int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
Alex Tomasa86c6182006-10-11 01:21:03 -07001864 struct ext4_ext_path *path)
1865{
Alex Tomasa86c6182006-10-11 01:21:03 -07001866 if (path) {
Mingming Caoee12b632008-08-19 22:16:05 -04001867 int depth = ext_depth(inode);
Mingming Caof3bd1f32008-08-19 22:16:03 -04001868 int ret = 0;
Mingming Caoee12b632008-08-19 22:16:05 -04001869
Alex Tomasa86c6182006-10-11 01:21:03 -07001870 /* probably there is space in leaf? */
Alex Tomasa86c6182006-10-11 01:21:03 -07001871 if (le16_to_cpu(path[depth].p_hdr->eh_entries)
Mingming Caoee12b632008-08-19 22:16:05 -04001872 < le16_to_cpu(path[depth].p_hdr->eh_max)) {
1873
1874 /*
1875 * There are some space in the leaf tree, no
1876 * need to account for leaf block credit
1877 *
1878 * bitmaps and block group descriptor blocks
1879 * and other metadat blocks still need to be
1880 * accounted.
1881 */
Mingming Cao525f4ed2008-08-19 22:15:58 -04001882 /* 1 bitmap, 1 block group descriptor */
Mingming Caoee12b632008-08-19 22:16:05 -04001883 ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
1884 }
Alex Tomasa86c6182006-10-11 01:21:03 -07001885 }
1886
Mingming Cao525f4ed2008-08-19 22:15:58 -04001887 return ext4_chunk_trans_blocks(inode, nrblocks);
Mingming Caoee12b632008-08-19 22:16:05 -04001888}
Alex Tomasa86c6182006-10-11 01:21:03 -07001889
Mingming Caoee12b632008-08-19 22:16:05 -04001890/*
1891 * How many index/leaf blocks need to change/allocate to modify nrblocks?
1892 *
1893 * if nrblocks are fit in a single extent (chunk flag is 1), then
1894 * in the worse case, each tree level index/leaf need to be changed
1895 * if the tree split due to insert a new extent, then the old tree
1896 * index/leaf need to be updated too
1897 *
1898 * If the nrblocks are discontiguous, they could cause
1899 * the whole tree split more than once, but this is really rare.
1900 */
Mingming Cao525f4ed2008-08-19 22:15:58 -04001901int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
Mingming Caoee12b632008-08-19 22:16:05 -04001902{
1903 int index;
1904 int depth = ext_depth(inode);
Alex Tomasa86c6182006-10-11 01:21:03 -07001905
Mingming Caoee12b632008-08-19 22:16:05 -04001906 if (chunk)
1907 index = depth * 2;
1908 else
1909 index = depth * 3;
Alex Tomasa86c6182006-10-11 01:21:03 -07001910
Mingming Caoee12b632008-08-19 22:16:05 -04001911 return index;
Alex Tomasa86c6182006-10-11 01:21:03 -07001912}
1913
1914static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
1915 struct ext4_extent *ex,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001916 ext4_lblk_t from, ext4_lblk_t to)
Alex Tomasa86c6182006-10-11 01:21:03 -07001917{
1918 struct buffer_head *bh;
Amit Aroraa2df2a62007-07-17 21:42:41 -04001919 unsigned short ee_len = ext4_ext_get_actual_len(ex);
Alex Tomasc9de5602008-01-29 00:19:52 -05001920 int i, metadata = 0;
Alex Tomasa86c6182006-10-11 01:21:03 -07001921
Alex Tomasc9de5602008-01-29 00:19:52 -05001922 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
1923 metadata = 1;
Alex Tomasa86c6182006-10-11 01:21:03 -07001924#ifdef EXTENTS_STATS
1925 {
1926 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
Alex Tomasa86c6182006-10-11 01:21:03 -07001927 spin_lock(&sbi->s_ext_stats_lock);
1928 sbi->s_ext_blocks += ee_len;
1929 sbi->s_ext_extents++;
1930 if (ee_len < sbi->s_ext_min)
1931 sbi->s_ext_min = ee_len;
1932 if (ee_len > sbi->s_ext_max)
1933 sbi->s_ext_max = ee_len;
1934 if (ext_depth(inode) > sbi->s_depth_max)
1935 sbi->s_depth_max = ext_depth(inode);
1936 spin_unlock(&sbi->s_ext_stats_lock);
1937 }
1938#endif
1939 if (from >= le32_to_cpu(ex->ee_block)
Amit Aroraa2df2a62007-07-17 21:42:41 -04001940 && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
Alex Tomasa86c6182006-10-11 01:21:03 -07001941 /* tail removal */
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001942 ext4_lblk_t num;
Alex Tomasf65e6fb2006-10-11 01:21:05 -07001943 ext4_fsblk_t start;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001944
Amit Aroraa2df2a62007-07-17 21:42:41 -04001945 num = le32_to_cpu(ex->ee_block) + ee_len - from;
1946 start = ext_pblock(ex) + ee_len - num;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001947 ext_debug("free last %u blocks starting %llu\n", num, start);
Alex Tomasa86c6182006-10-11 01:21:03 -07001948 for (i = 0; i < num; i++) {
1949 bh = sb_find_get_block(inode->i_sb, start + i);
1950 ext4_forget(handle, 0, inode, bh, start + i);
1951 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001952 ext4_free_blocks(handle, inode, start, num, metadata);
Alex Tomasa86c6182006-10-11 01:21:03 -07001953 } else if (from == le32_to_cpu(ex->ee_block)
Amit Aroraa2df2a62007-07-17 21:42:41 -04001954 && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001955 printk(KERN_INFO "strange request: removal %u-%u from %u:%u\n",
Amit Aroraa2df2a62007-07-17 21:42:41 -04001956 from, to, le32_to_cpu(ex->ee_block), ee_len);
Alex Tomasa86c6182006-10-11 01:21:03 -07001957 } else {
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001958 printk(KERN_INFO "strange request: removal(2) "
1959 "%u-%u from %u:%u\n",
1960 from, to, le32_to_cpu(ex->ee_block), ee_len);
Alex Tomasa86c6182006-10-11 01:21:03 -07001961 }
1962 return 0;
1963}
1964
1965static int
1966ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001967 struct ext4_ext_path *path, ext4_lblk_t start)
Alex Tomasa86c6182006-10-11 01:21:03 -07001968{
1969 int err = 0, correct_index = 0;
1970 int depth = ext_depth(inode), credits;
1971 struct ext4_extent_header *eh;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001972 ext4_lblk_t a, b, block;
1973 unsigned num;
1974 ext4_lblk_t ex_ee_block;
Alex Tomasa86c6182006-10-11 01:21:03 -07001975 unsigned short ex_ee_len;
Amit Aroraa2df2a62007-07-17 21:42:41 -04001976 unsigned uninitialized = 0;
Alex Tomasa86c6182006-10-11 01:21:03 -07001977 struct ext4_extent *ex;
1978
Alex Tomasc29c0ae2007-07-18 09:19:09 -04001979 /* the header must be checked already in ext4_ext_remove_space() */
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05001980 ext_debug("truncate since %u in leaf\n", start);
Alex Tomasa86c6182006-10-11 01:21:03 -07001981 if (!path[depth].p_hdr)
1982 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
1983 eh = path[depth].p_hdr;
1984 BUG_ON(eh == NULL);
Alex Tomasa86c6182006-10-11 01:21:03 -07001985
1986 /* find where to start removing */
1987 ex = EXT_LAST_EXTENT(eh);
1988
1989 ex_ee_block = le32_to_cpu(ex->ee_block);
Amit Aroraa2df2a62007-07-17 21:42:41 -04001990 if (ext4_ext_is_uninitialized(ex))
1991 uninitialized = 1;
1992 ex_ee_len = ext4_ext_get_actual_len(ex);
Alex Tomasa86c6182006-10-11 01:21:03 -07001993
1994 while (ex >= EXT_FIRST_EXTENT(eh) &&
1995 ex_ee_block + ex_ee_len > start) {
1996 ext_debug("remove ext %lu:%u\n", ex_ee_block, ex_ee_len);
1997 path[depth].p_ext = ex;
1998
1999 a = ex_ee_block > start ? ex_ee_block : start;
2000 b = ex_ee_block + ex_ee_len - 1 < EXT_MAX_BLOCK ?
2001 ex_ee_block + ex_ee_len - 1 : EXT_MAX_BLOCK;
2002
2003 ext_debug(" border %u:%u\n", a, b);
2004
2005 if (a != ex_ee_block && b != ex_ee_block + ex_ee_len - 1) {
2006 block = 0;
2007 num = 0;
2008 BUG();
2009 } else if (a != ex_ee_block) {
2010 /* remove tail of the extent */
2011 block = ex_ee_block;
2012 num = a - block;
2013 } else if (b != ex_ee_block + ex_ee_len - 1) {
2014 /* remove head of the extent */
2015 block = a;
2016 num = b - a;
2017 /* there is no "make a hole" API yet */
2018 BUG();
2019 } else {
2020 /* remove whole extent: excellent! */
2021 block = ex_ee_block;
2022 num = 0;
2023 BUG_ON(a != ex_ee_block);
2024 BUG_ON(b != ex_ee_block + ex_ee_len - 1);
2025 }
2026
Theodore Ts'o34071da2008-08-01 21:59:19 -04002027 /*
2028 * 3 for leaf, sb, and inode plus 2 (bmap and group
2029 * descriptor) for each block group; assume two block
2030 * groups plus ex_ee_len/blocks_per_block_group for
2031 * the worst case
2032 */
2033 credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
Alex Tomasa86c6182006-10-11 01:21:03 -07002034 if (ex == EXT_FIRST_EXTENT(eh)) {
2035 correct_index = 1;
2036 credits += (ext_depth(inode)) + 1;
2037 }
Alex Tomasa86c6182006-10-11 01:21:03 -07002038 credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb);
Alex Tomasa86c6182006-10-11 01:21:03 -07002039
Shen Feng9102e4f2008-07-11 19:27:31 -04002040 err = ext4_ext_journal_restart(handle, credits);
2041 if (err)
Alex Tomasa86c6182006-10-11 01:21:03 -07002042 goto out;
Alex Tomasa86c6182006-10-11 01:21:03 -07002043
2044 err = ext4_ext_get_access(handle, inode, path + depth);
2045 if (err)
2046 goto out;
2047
2048 err = ext4_remove_blocks(handle, inode, ex, a, b);
2049 if (err)
2050 goto out;
2051
2052 if (num == 0) {
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002053 /* this extent is removed; mark slot entirely unused */
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002054 ext4_ext_store_pblock(ex, 0);
Marcin Slusarze8546d02008-04-17 10:38:59 -04002055 le16_add_cpu(&eh->eh_entries, -1);
Alex Tomasa86c6182006-10-11 01:21:03 -07002056 }
2057
2058 ex->ee_block = cpu_to_le32(block);
2059 ex->ee_len = cpu_to_le16(num);
Amit Arora749269f2007-07-18 09:02:56 -04002060 /*
2061 * Do not mark uninitialized if all the blocks in the
2062 * extent have been removed.
2063 */
2064 if (uninitialized && num)
Amit Aroraa2df2a62007-07-17 21:42:41 -04002065 ext4_ext_mark_uninitialized(ex);
Alex Tomasa86c6182006-10-11 01:21:03 -07002066
2067 err = ext4_ext_dirty(handle, inode, path + depth);
2068 if (err)
2069 goto out;
2070
Mingming Cao2ae02102006-10-11 01:21:11 -07002071 ext_debug("new extent: %u:%u:%llu\n", block, num,
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002072 ext_pblock(ex));
Alex Tomasa86c6182006-10-11 01:21:03 -07002073 ex--;
2074 ex_ee_block = le32_to_cpu(ex->ee_block);
Amit Aroraa2df2a62007-07-17 21:42:41 -04002075 ex_ee_len = ext4_ext_get_actual_len(ex);
Alex Tomasa86c6182006-10-11 01:21:03 -07002076 }
2077
2078 if (correct_index && eh->eh_entries)
2079 err = ext4_ext_correct_indexes(handle, inode, path);
2080
2081 /* if this leaf is free, then we should
2082 * remove it from index block above */
2083 if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2084 err = ext4_ext_rm_idx(handle, inode, path + depth);
2085
2086out:
2087 return err;
2088}
2089
2090/*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002091 * ext4_ext_more_to_rm:
2092 * returns 1 if current index has to be freed (even partial)
Alex Tomasa86c6182006-10-11 01:21:03 -07002093 */
Avantika Mathur09b88252006-12-06 20:41:36 -08002094static int
Alex Tomasa86c6182006-10-11 01:21:03 -07002095ext4_ext_more_to_rm(struct ext4_ext_path *path)
2096{
2097 BUG_ON(path->p_idx == NULL);
2098
2099 if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2100 return 0;
2101
2102 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002103 * if truncate on deeper level happened, it wasn't partial,
Alex Tomasa86c6182006-10-11 01:21:03 -07002104 * so we have to consider current index for truncation
2105 */
2106 if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2107 return 0;
2108 return 1;
2109}
2110
Aneesh Kumar K.V1d03ec92008-01-28 23:58:27 -05002111static int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start)
Alex Tomasa86c6182006-10-11 01:21:03 -07002112{
2113 struct super_block *sb = inode->i_sb;
2114 int depth = ext_depth(inode);
2115 struct ext4_ext_path *path;
2116 handle_t *handle;
2117 int i = 0, err = 0;
2118
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05002119 ext_debug("truncate since %u\n", start);
Alex Tomasa86c6182006-10-11 01:21:03 -07002120
2121 /* probably first extent we're gonna free will be last in block */
2122 handle = ext4_journal_start(inode, depth + 1);
2123 if (IS_ERR(handle))
2124 return PTR_ERR(handle);
2125
2126 ext4_ext_invalidate_cache(inode);
2127
2128 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002129 * We start scanning from right side, freeing all the blocks
2130 * after i_size and walking into the tree depth-wise.
Alex Tomasa86c6182006-10-11 01:21:03 -07002131 */
Josef Bacik216553c2008-04-29 22:02:02 -04002132 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_NOFS);
Alex Tomasa86c6182006-10-11 01:21:03 -07002133 if (path == NULL) {
2134 ext4_journal_stop(handle);
2135 return -ENOMEM;
2136 }
Alex Tomasa86c6182006-10-11 01:21:03 -07002137 path[0].p_hdr = ext_inode_hdr(inode);
Alex Tomasc29c0ae2007-07-18 09:19:09 -04002138 if (ext4_ext_check_header(inode, path[0].p_hdr, depth)) {
Alex Tomasa86c6182006-10-11 01:21:03 -07002139 err = -EIO;
2140 goto out;
2141 }
2142 path[0].p_depth = depth;
2143
2144 while (i >= 0 && err == 0) {
2145 if (i == depth) {
2146 /* this is leaf block */
2147 err = ext4_ext_rm_leaf(handle, inode, path, start);
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002148 /* root level has p_bh == NULL, brelse() eats this */
Alex Tomasa86c6182006-10-11 01:21:03 -07002149 brelse(path[i].p_bh);
2150 path[i].p_bh = NULL;
2151 i--;
2152 continue;
2153 }
2154
2155 /* this is index block */
2156 if (!path[i].p_hdr) {
2157 ext_debug("initialize header\n");
2158 path[i].p_hdr = ext_block_hdr(path[i].p_bh);
Alex Tomasa86c6182006-10-11 01:21:03 -07002159 }
2160
Alex Tomasa86c6182006-10-11 01:21:03 -07002161 if (!path[i].p_idx) {
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002162 /* this level hasn't been touched yet */
Alex Tomasa86c6182006-10-11 01:21:03 -07002163 path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2164 path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2165 ext_debug("init index ptr: hdr 0x%p, num %d\n",
2166 path[i].p_hdr,
2167 le16_to_cpu(path[i].p_hdr->eh_entries));
2168 } else {
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002169 /* we were already here, see at next index */
Alex Tomasa86c6182006-10-11 01:21:03 -07002170 path[i].p_idx--;
2171 }
2172
2173 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2174 i, EXT_FIRST_INDEX(path[i].p_hdr),
2175 path[i].p_idx);
2176 if (ext4_ext_more_to_rm(path + i)) {
Alex Tomasc29c0ae2007-07-18 09:19:09 -04002177 struct buffer_head *bh;
Alex Tomasa86c6182006-10-11 01:21:03 -07002178 /* go to the next level */
Mingming Cao2ae02102006-10-11 01:21:11 -07002179 ext_debug("move to level %d (block %llu)\n",
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002180 i + 1, idx_pblock(path[i].p_idx));
Alex Tomasa86c6182006-10-11 01:21:03 -07002181 memset(path + i + 1, 0, sizeof(*path));
Alex Tomasc29c0ae2007-07-18 09:19:09 -04002182 bh = sb_bread(sb, idx_pblock(path[i].p_idx));
2183 if (!bh) {
Alex Tomasa86c6182006-10-11 01:21:03 -07002184 /* should we reset i_size? */
2185 err = -EIO;
2186 break;
2187 }
Alex Tomasc29c0ae2007-07-18 09:19:09 -04002188 if (WARN_ON(i + 1 > depth)) {
2189 err = -EIO;
2190 break;
2191 }
2192 if (ext4_ext_check_header(inode, ext_block_hdr(bh),
2193 depth - i - 1)) {
2194 err = -EIO;
2195 break;
2196 }
2197 path[i + 1].p_bh = bh;
Alex Tomasa86c6182006-10-11 01:21:03 -07002198
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002199 /* save actual number of indexes since this
2200 * number is changed at the next iteration */
Alex Tomasa86c6182006-10-11 01:21:03 -07002201 path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
2202 i++;
2203 } else {
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002204 /* we finished processing this index, go up */
Alex Tomasa86c6182006-10-11 01:21:03 -07002205 if (path[i].p_hdr->eh_entries == 0 && i > 0) {
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002206 /* index is empty, remove it;
Alex Tomasa86c6182006-10-11 01:21:03 -07002207 * handle must be already prepared by the
2208 * truncatei_leaf() */
2209 err = ext4_ext_rm_idx(handle, inode, path + i);
2210 }
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002211 /* root level has p_bh == NULL, brelse() eats this */
Alex Tomasa86c6182006-10-11 01:21:03 -07002212 brelse(path[i].p_bh);
2213 path[i].p_bh = NULL;
2214 i--;
2215 ext_debug("return to level %d\n", i);
2216 }
2217 }
2218
2219 /* TODO: flexible tree reduction should be here */
2220 if (path->p_hdr->eh_entries == 0) {
2221 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002222 * truncate to zero freed all the tree,
2223 * so we need to correct eh_depth
Alex Tomasa86c6182006-10-11 01:21:03 -07002224 */
2225 err = ext4_ext_get_access(handle, inode, path);
2226 if (err == 0) {
2227 ext_inode_hdr(inode)->eh_depth = 0;
2228 ext_inode_hdr(inode)->eh_max =
2229 cpu_to_le16(ext4_ext_space_root(inode));
2230 err = ext4_ext_dirty(handle, inode, path);
2231 }
2232 }
2233out:
Alex Tomasa86c6182006-10-11 01:21:03 -07002234 ext4_ext_drop_refs(path);
2235 kfree(path);
2236 ext4_journal_stop(handle);
2237
2238 return err;
2239}
2240
2241/*
2242 * called at mount time
2243 */
2244void ext4_ext_init(struct super_block *sb)
2245{
2246 /*
2247 * possible initialization would be here
2248 */
2249
Theodore Ts'o83982b62009-01-06 14:53:16 -05002250 if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
Theodore Ts'o4776004f2008-09-08 23:00:52 -04002251 printk(KERN_INFO "EXT4-fs: file extents enabled");
Robert P. J. Daybbf2f9f2007-02-17 19:20:16 +01002252#ifdef AGGRESSIVE_TEST
2253 printk(", aggressive tests");
Alex Tomasa86c6182006-10-11 01:21:03 -07002254#endif
2255#ifdef CHECK_BINSEARCH
2256 printk(", check binsearch");
2257#endif
2258#ifdef EXTENTS_STATS
2259 printk(", stats");
2260#endif
2261 printk("\n");
2262#ifdef EXTENTS_STATS
2263 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
2264 EXT4_SB(sb)->s_ext_min = 1 << 30;
2265 EXT4_SB(sb)->s_ext_max = 0;
2266#endif
2267 }
2268}
2269
2270/*
2271 * called at umount time
2272 */
2273void ext4_ext_release(struct super_block *sb)
2274{
Theodore Ts'o83982b62009-01-06 14:53:16 -05002275 if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS))
Alex Tomasa86c6182006-10-11 01:21:03 -07002276 return;
2277
2278#ifdef EXTENTS_STATS
2279 if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
2280 struct ext4_sb_info *sbi = EXT4_SB(sb);
2281 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2282 sbi->s_ext_blocks, sbi->s_ext_extents,
2283 sbi->s_ext_blocks / sbi->s_ext_extents);
2284 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2285 sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
2286 }
2287#endif
2288}
2289
Aneesh Kumar K.V093a0882008-04-29 08:11:12 -04002290static void bi_complete(struct bio *bio, int error)
2291{
2292 complete((struct completion *)bio->bi_private);
2293}
2294
2295/* FIXME!! we need to try to merge to left or right after zero-out */
2296static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
2297{
2298 int ret = -EIO;
2299 struct bio *bio;
2300 int blkbits, blocksize;
2301 sector_t ee_pblock;
2302 struct completion event;
2303 unsigned int ee_len, len, done, offset;
2304
2305
2306 blkbits = inode->i_blkbits;
2307 blocksize = inode->i_sb->s_blocksize;
2308 ee_len = ext4_ext_get_actual_len(ex);
2309 ee_pblock = ext_pblock(ex);
2310
2311 /* convert ee_pblock to 512 byte sectors */
2312 ee_pblock = ee_pblock << (blkbits - 9);
2313
2314 while (ee_len > 0) {
2315
2316 if (ee_len > BIO_MAX_PAGES)
2317 len = BIO_MAX_PAGES;
2318 else
2319 len = ee_len;
2320
2321 bio = bio_alloc(GFP_NOIO, len);
2322 if (!bio)
2323 return -ENOMEM;
2324 bio->bi_sector = ee_pblock;
2325 bio->bi_bdev = inode->i_sb->s_bdev;
2326
2327 done = 0;
2328 offset = 0;
2329 while (done < len) {
2330 ret = bio_add_page(bio, ZERO_PAGE(0),
2331 blocksize, offset);
2332 if (ret != blocksize) {
2333 /*
2334 * We can't add any more pages because of
2335 * hardware limitations. Start a new bio.
2336 */
2337 break;
2338 }
2339 done++;
2340 offset += blocksize;
2341 if (offset >= PAGE_CACHE_SIZE)
2342 offset = 0;
2343 }
2344
2345 init_completion(&event);
2346 bio->bi_private = &event;
2347 bio->bi_end_io = bi_complete;
2348 submit_bio(WRITE, bio);
2349 wait_for_completion(&event);
2350
2351 if (test_bit(BIO_UPTODATE, &bio->bi_flags))
2352 ret = 0;
2353 else {
2354 ret = -EIO;
2355 break;
2356 }
2357 bio_put(bio);
2358 ee_len -= done;
2359 ee_pblock += done << (blkbits - 9);
2360 }
2361 return ret;
2362}
2363
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002364#define EXT4_EXT_ZERO_LEN 7
2365
Amit Arora56055d32007-07-17 21:42:38 -04002366/*
2367 * This function is called by ext4_ext_get_blocks() if someone tries to write
2368 * to an uninitialized extent. It may result in splitting the uninitialized
2369 * extent into multiple extents (upto three - one initialized and two
2370 * uninitialized).
2371 * There are three possibilities:
2372 * a> There is no split required: Entire extent should be initialized
2373 * b> Splits in two extents: Write is happening at either end of the extent
2374 * c> Splits in three extents: Somone is writing in middle of the extent
2375 */
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05002376static int ext4_ext_convert_to_initialized(handle_t *handle,
2377 struct inode *inode,
2378 struct ext4_ext_path *path,
2379 ext4_lblk_t iblock,
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002380 unsigned int max_blocks)
Amit Arora56055d32007-07-17 21:42:38 -04002381{
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002382 struct ext4_extent *ex, newex, orig_ex;
Amit Arora56055d32007-07-17 21:42:38 -04002383 struct ext4_extent *ex1 = NULL;
2384 struct ext4_extent *ex2 = NULL;
2385 struct ext4_extent *ex3 = NULL;
2386 struct ext4_extent_header *eh;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05002387 ext4_lblk_t ee_block;
2388 unsigned int allocated, ee_len, depth;
Amit Arora56055d32007-07-17 21:42:38 -04002389 ext4_fsblk_t newblock;
2390 int err = 0;
2391 int ret = 0;
2392
2393 depth = ext_depth(inode);
2394 eh = path[depth].p_hdr;
2395 ex = path[depth].p_ext;
2396 ee_block = le32_to_cpu(ex->ee_block);
2397 ee_len = ext4_ext_get_actual_len(ex);
2398 allocated = ee_len - (iblock - ee_block);
2399 newblock = iblock - ee_block + ext_pblock(ex);
2400 ex2 = ex;
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002401 orig_ex.ee_block = ex->ee_block;
2402 orig_ex.ee_len = cpu_to_le16(ee_len);
2403 ext4_ext_store_pblock(&orig_ex, ext_pblock(ex));
Amit Arora56055d32007-07-17 21:42:38 -04002404
Aneesh Kumar K.V9df56432008-02-22 06:17:31 -05002405 err = ext4_ext_get_access(handle, inode, path + depth);
2406 if (err)
2407 goto out;
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002408 /* If extent has less than 2*EXT4_EXT_ZERO_LEN zerout directly */
2409 if (ee_len <= 2*EXT4_EXT_ZERO_LEN) {
2410 err = ext4_ext_zeroout(inode, &orig_ex);
2411 if (err)
2412 goto fix_extent_len;
2413 /* update the extent length and mark as initialized */
2414 ex->ee_block = orig_ex.ee_block;
2415 ex->ee_len = orig_ex.ee_len;
2416 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2417 ext4_ext_dirty(handle, inode, path + depth);
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002418 /* zeroed the full extent */
2419 return allocated;
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002420 }
Aneesh Kumar K.V9df56432008-02-22 06:17:31 -05002421
Amit Arora56055d32007-07-17 21:42:38 -04002422 /* ex1: ee_block to iblock - 1 : uninitialized */
2423 if (iblock > ee_block) {
2424 ex1 = ex;
2425 ex1->ee_len = cpu_to_le16(iblock - ee_block);
2426 ext4_ext_mark_uninitialized(ex1);
2427 ex2 = &newex;
2428 }
2429 /*
2430 * for sanity, update the length of the ex2 extent before
2431 * we insert ex3, if ex1 is NULL. This is to avoid temporary
2432 * overlap of blocks.
2433 */
2434 if (!ex1 && allocated > max_blocks)
2435 ex2->ee_len = cpu_to_le16(max_blocks);
2436 /* ex3: to ee_block + ee_len : uninitialised */
2437 if (allocated > max_blocks) {
2438 unsigned int newdepth;
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002439 /* If extent has less than EXT4_EXT_ZERO_LEN zerout directly */
2440 if (allocated <= EXT4_EXT_ZERO_LEN) {
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002441 /*
2442 * iblock == ee_block is handled by the zerouout
2443 * at the beginning.
2444 * Mark first half uninitialized.
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002445 * Mark second half initialized and zero out the
2446 * initialized extent
2447 */
2448 ex->ee_block = orig_ex.ee_block;
2449 ex->ee_len = cpu_to_le16(ee_len - allocated);
2450 ext4_ext_mark_uninitialized(ex);
2451 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2452 ext4_ext_dirty(handle, inode, path + depth);
2453
2454 ex3 = &newex;
2455 ex3->ee_block = cpu_to_le32(iblock);
2456 ext4_ext_store_pblock(ex3, newblock);
2457 ex3->ee_len = cpu_to_le16(allocated);
2458 err = ext4_ext_insert_extent(handle, inode, path, ex3);
2459 if (err == -ENOSPC) {
2460 err = ext4_ext_zeroout(inode, &orig_ex);
2461 if (err)
2462 goto fix_extent_len;
2463 ex->ee_block = orig_ex.ee_block;
2464 ex->ee_len = orig_ex.ee_len;
2465 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2466 ext4_ext_dirty(handle, inode, path + depth);
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002467 /* blocks available from iblock */
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002468 return allocated;
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002469
2470 } else if (err)
2471 goto fix_extent_len;
2472
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002473 /*
2474 * We need to zero out the second half because
2475 * an fallocate request can update file size and
2476 * converting the second half to initialized extent
2477 * implies that we can leak some junk data to user
2478 * space.
2479 */
2480 err = ext4_ext_zeroout(inode, ex3);
2481 if (err) {
2482 /*
2483 * We should actually mark the
2484 * second half as uninit and return error
2485 * Insert would have changed the extent
2486 */
2487 depth = ext_depth(inode);
2488 ext4_ext_drop_refs(path);
2489 path = ext4_ext_find_extent(inode,
2490 iblock, path);
2491 if (IS_ERR(path)) {
2492 err = PTR_ERR(path);
2493 return err;
2494 }
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002495 /* get the second half extent details */
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002496 ex = path[depth].p_ext;
2497 err = ext4_ext_get_access(handle, inode,
2498 path + depth);
2499 if (err)
2500 return err;
2501 ext4_ext_mark_uninitialized(ex);
2502 ext4_ext_dirty(handle, inode, path + depth);
2503 return err;
2504 }
2505
2506 /* zeroed the second half */
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002507 return allocated;
2508 }
Amit Arora56055d32007-07-17 21:42:38 -04002509 ex3 = &newex;
2510 ex3->ee_block = cpu_to_le32(iblock + max_blocks);
2511 ext4_ext_store_pblock(ex3, newblock + max_blocks);
2512 ex3->ee_len = cpu_to_le16(allocated - max_blocks);
2513 ext4_ext_mark_uninitialized(ex3);
2514 err = ext4_ext_insert_extent(handle, inode, path, ex3);
Aneesh Kumar K.V093a0882008-04-29 08:11:12 -04002515 if (err == -ENOSPC) {
2516 err = ext4_ext_zeroout(inode, &orig_ex);
2517 if (err)
2518 goto fix_extent_len;
2519 /* update the extent length and mark as initialized */
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002520 ex->ee_block = orig_ex.ee_block;
2521 ex->ee_len = orig_ex.ee_len;
2522 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002523 ext4_ext_dirty(handle, inode, path + depth);
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002524 /* zeroed the full extent */
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002525 /* blocks available from iblock */
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002526 return allocated;
Aneesh Kumar K.V093a0882008-04-29 08:11:12 -04002527
2528 } else if (err)
2529 goto fix_extent_len;
Amit Arora56055d32007-07-17 21:42:38 -04002530 /*
2531 * The depth, and hence eh & ex might change
2532 * as part of the insert above.
2533 */
2534 newdepth = ext_depth(inode);
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002535 /*
2536 * update the extent length after successfull insert of the
2537 * split extent
2538 */
2539 orig_ex.ee_len = cpu_to_le16(ee_len -
2540 ext4_ext_get_actual_len(ex3));
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002541 depth = newdepth;
2542 ext4_ext_drop_refs(path);
2543 path = ext4_ext_find_extent(inode, iblock, path);
2544 if (IS_ERR(path)) {
2545 err = PTR_ERR(path);
2546 goto out;
Amit Arora56055d32007-07-17 21:42:38 -04002547 }
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002548 eh = path[depth].p_hdr;
2549 ex = path[depth].p_ext;
2550 if (ex2 != &newex)
2551 ex2 = ex;
2552
2553 err = ext4_ext_get_access(handle, inode, path + depth);
2554 if (err)
2555 goto out;
2556
Amit Arora56055d32007-07-17 21:42:38 -04002557 allocated = max_blocks;
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002558
2559 /* If extent has less than EXT4_EXT_ZERO_LEN and we are trying
2560 * to insert a extent in the middle zerout directly
2561 * otherwise give the extent a chance to merge to left
2562 */
2563 if (le16_to_cpu(orig_ex.ee_len) <= EXT4_EXT_ZERO_LEN &&
2564 iblock != ee_block) {
2565 err = ext4_ext_zeroout(inode, &orig_ex);
2566 if (err)
2567 goto fix_extent_len;
2568 /* update the extent length and mark as initialized */
2569 ex->ee_block = orig_ex.ee_block;
2570 ex->ee_len = orig_ex.ee_len;
2571 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2572 ext4_ext_dirty(handle, inode, path + depth);
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002573 /* zero out the first half */
Aneesh Kumar K.Vd03856b2008-08-02 18:51:32 -04002574 /* blocks available from iblock */
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002575 return allocated;
Aneesh Kumar K.V3977c962008-04-17 10:38:59 -04002576 }
Amit Arora56055d32007-07-17 21:42:38 -04002577 }
2578 /*
2579 * If there was a change of depth as part of the
2580 * insertion of ex3 above, we need to update the length
2581 * of the ex1 extent again here
2582 */
2583 if (ex1 && ex1 != ex) {
2584 ex1 = ex;
2585 ex1->ee_len = cpu_to_le16(iblock - ee_block);
2586 ext4_ext_mark_uninitialized(ex1);
2587 ex2 = &newex;
2588 }
2589 /* ex2: iblock to iblock + maxblocks-1 : initialised */
2590 ex2->ee_block = cpu_to_le32(iblock);
Amit Arora56055d32007-07-17 21:42:38 -04002591 ext4_ext_store_pblock(ex2, newblock);
2592 ex2->ee_len = cpu_to_le16(allocated);
2593 if (ex2 != ex)
2594 goto insert;
Amit Arora56055d32007-07-17 21:42:38 -04002595 /*
2596 * New (initialized) extent starts from the first block
2597 * in the current extent. i.e., ex2 == ex
2598 * We have to see if it can be merged with the extent
2599 * on the left.
2600 */
2601 if (ex2 > EXT_FIRST_EXTENT(eh)) {
2602 /*
2603 * To merge left, pass "ex2 - 1" to try_to_merge(),
2604 * since it merges towards right _only_.
2605 */
2606 ret = ext4_ext_try_to_merge(inode, path, ex2 - 1);
2607 if (ret) {
2608 err = ext4_ext_correct_indexes(handle, inode, path);
2609 if (err)
2610 goto out;
2611 depth = ext_depth(inode);
2612 ex2--;
2613 }
2614 }
2615 /*
2616 * Try to Merge towards right. This might be required
2617 * only when the whole extent is being written to.
2618 * i.e. ex2 == ex and ex3 == NULL.
2619 */
2620 if (!ex3) {
2621 ret = ext4_ext_try_to_merge(inode, path, ex2);
2622 if (ret) {
2623 err = ext4_ext_correct_indexes(handle, inode, path);
2624 if (err)
2625 goto out;
2626 }
2627 }
2628 /* Mark modified extent as dirty */
2629 err = ext4_ext_dirty(handle, inode, path + depth);
2630 goto out;
2631insert:
2632 err = ext4_ext_insert_extent(handle, inode, path, &newex);
Aneesh Kumar K.V093a0882008-04-29 08:11:12 -04002633 if (err == -ENOSPC) {
2634 err = ext4_ext_zeroout(inode, &orig_ex);
2635 if (err)
2636 goto fix_extent_len;
2637 /* update the extent length and mark as initialized */
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002638 ex->ee_block = orig_ex.ee_block;
2639 ex->ee_len = orig_ex.ee_len;
2640 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
Aneesh Kumar K.V95c38892008-04-17 10:38:59 -04002641 ext4_ext_dirty(handle, inode, path + depth);
Aneesh Kumar K.V161e7b72008-04-29 22:03:59 -04002642 /* zero out the first half */
2643 return allocated;
Aneesh Kumar K.V093a0882008-04-29 08:11:12 -04002644 } else if (err)
2645 goto fix_extent_len;
Amit Arora56055d32007-07-17 21:42:38 -04002646out:
2647 return err ? err : allocated;
Aneesh Kumar K.V093a0882008-04-29 08:11:12 -04002648
2649fix_extent_len:
2650 ex->ee_block = orig_ex.ee_block;
2651 ex->ee_len = orig_ex.ee_len;
2652 ext4_ext_store_pblock(ex, ext_pblock(&orig_ex));
2653 ext4_ext_mark_uninitialized(ex);
2654 ext4_ext_dirty(handle, inode, path + depth);
2655 return err;
Amit Arora56055d32007-07-17 21:42:38 -04002656}
2657
Aneesh Kumar K.Vc278bfe2008-01-28 23:58:27 -05002658/*
Mingming Caof5ab0d12008-02-25 15:29:55 -05002659 * Block allocation/map/preallocation routine for extents based files
2660 *
2661 *
Aneesh Kumar K.Vc278bfe2008-01-28 23:58:27 -05002662 * Need to be called with
Aneesh Kumar K.V0e855ac2008-01-28 23:58:26 -05002663 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
2664 * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
Mingming Caof5ab0d12008-02-25 15:29:55 -05002665 *
2666 * return > 0, number of of blocks already mapped/allocated
2667 * if create == 0 and these are pre-allocated blocks
2668 * buffer head is unmapped
2669 * otherwise blocks are mapped
2670 *
2671 * return = 0, if plain look up failed (blocks have not been allocated)
2672 * buffer head is unmapped
2673 *
2674 * return < 0, error case.
Aneesh Kumar K.Vc278bfe2008-01-28 23:58:27 -05002675 */
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002676int ext4_ext_get_blocks(handle_t *handle, struct inode *inode,
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05002677 ext4_lblk_t iblock,
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002678 unsigned int max_blocks, struct buffer_head *bh_result,
Alex Tomasa86c6182006-10-11 01:21:03 -07002679 int create, int extend_disksize)
2680{
2681 struct ext4_ext_path *path = NULL;
Amit Arora56055d32007-07-17 21:42:38 -04002682 struct ext4_extent_header *eh;
Alex Tomasa86c6182006-10-11 01:21:03 -07002683 struct ext4_extent newex, *ex;
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002684 ext4_fsblk_t newblock;
2685 int err = 0, depth, ret, cache_type;
2686 unsigned int allocated = 0;
Alex Tomasc9de5602008-01-29 00:19:52 -05002687 struct ext4_allocation_request ar;
Mingming Cao61628a32008-07-11 19:27:31 -04002688 loff_t disksize;
Alex Tomasa86c6182006-10-11 01:21:03 -07002689
2690 __clear_bit(BH_New, &bh_result->b_state);
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002691 ext_debug("blocks %u/%u requested for inode %u\n",
Eric Sandeenbba90742008-01-28 23:58:27 -05002692 iblock, max_blocks, inode->i_ino);
Alex Tomasa86c6182006-10-11 01:21:03 -07002693
2694 /* check in cache */
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002695 cache_type = ext4_ext_in_cache(inode, iblock, &newex);
2696 if (cache_type) {
2697 if (cache_type == EXT4_EXT_CACHE_GAP) {
Alex Tomasa86c6182006-10-11 01:21:03 -07002698 if (!create) {
Amit Arora56055d32007-07-17 21:42:38 -04002699 /*
2700 * block isn't allocated yet and
2701 * user doesn't want to allocate it
2702 */
Alex Tomasa86c6182006-10-11 01:21:03 -07002703 goto out2;
2704 }
2705 /* we should allocate requested block */
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002706 } else if (cache_type == EXT4_EXT_CACHE_EXTENT) {
Alex Tomasa86c6182006-10-11 01:21:03 -07002707 /* block is already allocated */
Dave Kleikamp8c55e202007-05-24 13:04:54 -04002708 newblock = iblock
2709 - le32_to_cpu(newex.ee_block)
2710 + ext_pblock(&newex);
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002711 /* number of remaining blocks in the extent */
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05002712 allocated = ext4_ext_get_actual_len(&newex) -
Alex Tomasa86c6182006-10-11 01:21:03 -07002713 (iblock - le32_to_cpu(newex.ee_block));
2714 goto out;
2715 } else {
2716 BUG();
2717 }
2718 }
2719
2720 /* find extent for this block */
2721 path = ext4_ext_find_extent(inode, iblock, NULL);
2722 if (IS_ERR(path)) {
2723 err = PTR_ERR(path);
2724 path = NULL;
2725 goto out2;
2726 }
2727
2728 depth = ext_depth(inode);
2729
2730 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002731 * consistent leaf must not be empty;
2732 * this situation is possible, though, _during_ tree modification;
Alex Tomasa86c6182006-10-11 01:21:03 -07002733 * this is why assert can't be put in ext4_ext_find_extent()
2734 */
2735 BUG_ON(path[depth].p_ext == NULL && depth != 0);
Amit Arora56055d32007-07-17 21:42:38 -04002736 eh = path[depth].p_hdr;
Alex Tomasa86c6182006-10-11 01:21:03 -07002737
Avantika Mathur7e028972006-12-06 20:41:33 -08002738 ex = path[depth].p_ext;
2739 if (ex) {
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05002740 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002741 ext4_fsblk_t ee_start = ext_pblock(ex);
Amit Aroraa2df2a62007-07-17 21:42:41 -04002742 unsigned short ee_len;
Suparna Bhattacharya471d4012006-10-11 01:21:06 -07002743
2744 /*
Suparna Bhattacharya471d4012006-10-11 01:21:06 -07002745 * Uninitialized extents are treated as holes, except that
Amit Arora56055d32007-07-17 21:42:38 -04002746 * we split out initialized portions during a write.
Suparna Bhattacharya471d4012006-10-11 01:21:06 -07002747 */
Amit Aroraa2df2a62007-07-17 21:42:41 -04002748 ee_len = ext4_ext_get_actual_len(ex);
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002749 /* if found extent covers block, simply return it */
Dave Kleikamp8c55e202007-05-24 13:04:54 -04002750 if (iblock >= ee_block && iblock < ee_block + ee_len) {
Alex Tomasa86c6182006-10-11 01:21:03 -07002751 newblock = iblock - ee_block + ee_start;
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002752 /* number of remaining blocks in the extent */
Alex Tomasa86c6182006-10-11 01:21:03 -07002753 allocated = ee_len - (iblock - ee_block);
Eric Sandeenbba90742008-01-28 23:58:27 -05002754 ext_debug("%u fit into %lu:%d -> %llu\n", iblock,
Alex Tomasa86c6182006-10-11 01:21:03 -07002755 ee_block, ee_len, newblock);
Amit Arora56055d32007-07-17 21:42:38 -04002756
Amit Aroraa2df2a62007-07-17 21:42:41 -04002757 /* Do not put uninitialized extent in the cache */
Amit Arora56055d32007-07-17 21:42:38 -04002758 if (!ext4_ext_is_uninitialized(ex)) {
Amit Aroraa2df2a62007-07-17 21:42:41 -04002759 ext4_ext_put_in_cache(inode, ee_block,
2760 ee_len, ee_start,
2761 EXT4_EXT_CACHE_EXTENT);
Amit Arora56055d32007-07-17 21:42:38 -04002762 goto out;
2763 }
2764 if (create == EXT4_CREATE_UNINITIALIZED_EXT)
2765 goto out;
Aneesh Kumar K.Ve067ba02008-04-29 08:11:12 -04002766 if (!create) {
2767 /*
2768 * We have blocks reserved already. We
2769 * return allocated blocks so that delalloc
2770 * won't do block reservation for us. But
2771 * the buffer head will be unmapped so that
2772 * a read from the block returns 0s.
2773 */
2774 if (allocated > max_blocks)
2775 allocated = max_blocks;
Eric Sandeen953e6222008-07-11 19:27:31 -04002776 set_buffer_unwritten(bh_result);
Amit Arora56055d32007-07-17 21:42:38 -04002777 goto out2;
Aneesh Kumar K.Ve067ba02008-04-29 08:11:12 -04002778 }
Amit Arora56055d32007-07-17 21:42:38 -04002779
2780 ret = ext4_ext_convert_to_initialized(handle, inode,
2781 path, iblock,
2782 max_blocks);
Dmitry Monakhovdbf9d7d2008-01-28 23:58:27 -05002783 if (ret <= 0) {
2784 err = ret;
Amit Arora56055d32007-07-17 21:42:38 -04002785 goto out2;
Dmitry Monakhovdbf9d7d2008-01-28 23:58:27 -05002786 } else
Amit Arora56055d32007-07-17 21:42:38 -04002787 allocated = ret;
2788 goto outnew;
Alex Tomasa86c6182006-10-11 01:21:03 -07002789 }
2790 }
2791
2792 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002793 * requested block isn't allocated yet;
Alex Tomasa86c6182006-10-11 01:21:03 -07002794 * we couldn't try to create block if create flag is zero
2795 */
2796 if (!create) {
Amit Arora56055d32007-07-17 21:42:38 -04002797 /*
2798 * put just found gap into cache to speed up
2799 * subsequent requests
2800 */
Alex Tomasa86c6182006-10-11 01:21:03 -07002801 ext4_ext_put_gap_in_cache(inode, path, iblock);
2802 goto out2;
2803 }
2804 /*
Theodore Ts'oc2ea3fd2008-10-10 09:40:52 -04002805 * Okay, we need to do block allocation.
Andrew Morton63f57932006-10-11 01:21:24 -07002806 */
Alex Tomasa86c6182006-10-11 01:21:03 -07002807
Alex Tomasc9de5602008-01-29 00:19:52 -05002808 /* find neighbour allocated blocks */
2809 ar.lleft = iblock;
2810 err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
2811 if (err)
2812 goto out2;
2813 ar.lright = iblock;
2814 err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright);
2815 if (err)
2816 goto out2;
Amit Arora25d14f92007-05-24 13:04:13 -04002817
Amit Arora749269f2007-07-18 09:02:56 -04002818 /*
2819 * See if request is beyond maximum number of blocks we can have in
2820 * a single extent. For an initialized extent this limit is
2821 * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
2822 * EXT_UNINIT_MAX_LEN.
2823 */
2824 if (max_blocks > EXT_INIT_MAX_LEN &&
2825 create != EXT4_CREATE_UNINITIALIZED_EXT)
2826 max_blocks = EXT_INIT_MAX_LEN;
2827 else if (max_blocks > EXT_UNINIT_MAX_LEN &&
2828 create == EXT4_CREATE_UNINITIALIZED_EXT)
2829 max_blocks = EXT_UNINIT_MAX_LEN;
2830
Amit Arora25d14f92007-05-24 13:04:13 -04002831 /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
2832 newex.ee_block = cpu_to_le32(iblock);
2833 newex.ee_len = cpu_to_le16(max_blocks);
2834 err = ext4_ext_check_overlap(inode, &newex, path);
2835 if (err)
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05002836 allocated = ext4_ext_get_actual_len(&newex);
Amit Arora25d14f92007-05-24 13:04:13 -04002837 else
2838 allocated = max_blocks;
Alex Tomasc9de5602008-01-29 00:19:52 -05002839
2840 /* allocate new block */
2841 ar.inode = inode;
2842 ar.goal = ext4_ext_find_goal(inode, path, iblock);
2843 ar.logical = iblock;
2844 ar.len = allocated;
2845 if (S_ISREG(inode->i_mode))
2846 ar.flags = EXT4_MB_HINT_DATA;
2847 else
2848 /* disable in-core preallocation for non-regular files */
2849 ar.flags = 0;
2850 newblock = ext4_mb_new_blocks(handle, &ar, &err);
Alex Tomasa86c6182006-10-11 01:21:03 -07002851 if (!newblock)
2852 goto out2;
Mingming Cao2ae02102006-10-11 01:21:11 -07002853 ext_debug("allocate new block: goal %llu, found %llu/%lu\n",
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002854 ar.goal, newblock, allocated);
Alex Tomasa86c6182006-10-11 01:21:03 -07002855
2856 /* try to insert new extent into found leaf and return */
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002857 ext4_ext_store_pblock(&newex, newblock);
Alex Tomasc9de5602008-01-29 00:19:52 -05002858 newex.ee_len = cpu_to_le16(ar.len);
Amit Aroraa2df2a62007-07-17 21:42:41 -04002859 if (create == EXT4_CREATE_UNINITIALIZED_EXT) /* Mark uninitialized */
2860 ext4_ext_mark_uninitialized(&newex);
Alex Tomasa86c6182006-10-11 01:21:03 -07002861 err = ext4_ext_insert_extent(handle, inode, path, &newex);
Alex Tomas315054f2007-05-24 13:04:25 -04002862 if (err) {
2863 /* free data blocks we just allocated */
Alex Tomasc9de5602008-01-29 00:19:52 -05002864 /* not a good idea to call discard here directly,
2865 * but otherwise we'd need to call it every free() */
Theodore Ts'oc2ea3fd2008-10-10 09:40:52 -04002866 ext4_discard_preallocations(inode);
Alex Tomas315054f2007-05-24 13:04:25 -04002867 ext4_free_blocks(handle, inode, ext_pblock(&newex),
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05002868 ext4_ext_get_actual_len(&newex), 0);
Alex Tomasa86c6182006-10-11 01:21:03 -07002869 goto out2;
Alex Tomas315054f2007-05-24 13:04:25 -04002870 }
Alex Tomasa86c6182006-10-11 01:21:03 -07002871
Alex Tomasa86c6182006-10-11 01:21:03 -07002872 /* previous routine could use block we allocated */
Alex Tomasf65e6fb2006-10-11 01:21:05 -07002873 newblock = ext_pblock(&newex);
Aneesh Kumar K.Vb939e372008-01-28 23:58:27 -05002874 allocated = ext4_ext_get_actual_len(&newex);
Amit Arora56055d32007-07-17 21:42:38 -04002875outnew:
Mingming Cao61628a32008-07-11 19:27:31 -04002876 if (extend_disksize) {
2877 disksize = ((loff_t) iblock + ar.len) << inode->i_blkbits;
2878 if (disksize > i_size_read(inode))
2879 disksize = i_size_read(inode);
2880 if (disksize > EXT4_I(inode)->i_disksize)
2881 EXT4_I(inode)->i_disksize = disksize;
2882 }
Aneesh Kumar K.Va379cd12008-07-11 19:27:31 -04002883
Eric Sandeen953e6222008-07-11 19:27:31 -04002884 set_buffer_new(bh_result);
Alex Tomasa86c6182006-10-11 01:21:03 -07002885
Amit Aroraa2df2a62007-07-17 21:42:41 -04002886 /* Cache only when it is _not_ an uninitialized extent */
2887 if (create != EXT4_CREATE_UNINITIALIZED_EXT)
2888 ext4_ext_put_in_cache(inode, iblock, allocated, newblock,
2889 EXT4_EXT_CACHE_EXTENT);
Alex Tomasa86c6182006-10-11 01:21:03 -07002890out:
2891 if (allocated > max_blocks)
2892 allocated = max_blocks;
2893 ext4_ext_show_leaf(inode, path);
Eric Sandeen953e6222008-07-11 19:27:31 -04002894 set_buffer_mapped(bh_result);
Alex Tomasa86c6182006-10-11 01:21:03 -07002895 bh_result->b_bdev = inode->i_sb->s_bdev;
2896 bh_result->b_blocknr = newblock;
2897out2:
2898 if (path) {
2899 ext4_ext_drop_refs(path);
2900 kfree(path);
2901 }
Alex Tomasa86c6182006-10-11 01:21:03 -07002902 return err ? err : allocated;
2903}
2904
Jan Karacf108bc2008-07-11 19:27:31 -04002905void ext4_ext_truncate(struct inode *inode)
Alex Tomasa86c6182006-10-11 01:21:03 -07002906{
2907 struct address_space *mapping = inode->i_mapping;
2908 struct super_block *sb = inode->i_sb;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05002909 ext4_lblk_t last_block;
Alex Tomasa86c6182006-10-11 01:21:03 -07002910 handle_t *handle;
2911 int err = 0;
2912
2913 /*
2914 * probably first extent we're gonna free will be last in block
2915 */
Mingming Caof3bd1f32008-08-19 22:16:03 -04002916 err = ext4_writepage_trans_blocks(inode);
Alex Tomasa86c6182006-10-11 01:21:03 -07002917 handle = ext4_journal_start(inode, err);
Jan Karacf108bc2008-07-11 19:27:31 -04002918 if (IS_ERR(handle))
Alex Tomasa86c6182006-10-11 01:21:03 -07002919 return;
Alex Tomasa86c6182006-10-11 01:21:03 -07002920
Jan Karacf108bc2008-07-11 19:27:31 -04002921 if (inode->i_size & (sb->s_blocksize - 1))
2922 ext4_block_truncate_page(handle, mapping, inode->i_size);
Alex Tomasa86c6182006-10-11 01:21:03 -07002923
Jan Kara9ddfc3d2008-07-11 19:27:31 -04002924 if (ext4_orphan_add(handle, inode))
2925 goto out_stop;
2926
Aneesh Kumar K.V0e855ac2008-01-28 23:58:26 -05002927 down_write(&EXT4_I(inode)->i_data_sem);
Alex Tomasa86c6182006-10-11 01:21:03 -07002928 ext4_ext_invalidate_cache(inode);
2929
Theodore Ts'oc2ea3fd2008-10-10 09:40:52 -04002930 ext4_discard_preallocations(inode);
Alex Tomasc9de5602008-01-29 00:19:52 -05002931
Alex Tomasa86c6182006-10-11 01:21:03 -07002932 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002933 * TODO: optimization is possible here.
2934 * Probably we need not scan at all,
2935 * because page truncation is enough.
Alex Tomasa86c6182006-10-11 01:21:03 -07002936 */
Alex Tomasa86c6182006-10-11 01:21:03 -07002937
2938 /* we have to know where to truncate from in crash case */
2939 EXT4_I(inode)->i_disksize = inode->i_size;
2940 ext4_mark_inode_dirty(handle, inode);
2941
2942 last_block = (inode->i_size + sb->s_blocksize - 1)
2943 >> EXT4_BLOCK_SIZE_BITS(sb);
2944 err = ext4_ext_remove_space(inode, last_block);
2945
2946 /* In a multi-transaction truncate, we only make the final
Amit Arora56055d32007-07-17 21:42:38 -04002947 * transaction synchronous.
2948 */
Alex Tomasa86c6182006-10-11 01:21:03 -07002949 if (IS_SYNC(inode))
Frank Mayhar03901312009-01-07 00:06:22 -05002950 ext4_handle_sync(handle);
Alex Tomasa86c6182006-10-11 01:21:03 -07002951
2952out_stop:
Jan Kara9ddfc3d2008-07-11 19:27:31 -04002953 up_write(&EXT4_I(inode)->i_data_sem);
Alex Tomasa86c6182006-10-11 01:21:03 -07002954 /*
Randy Dunlapd0d856e2006-10-11 01:21:07 -07002955 * If this was a simple ftruncate() and the file will remain alive,
Alex Tomasa86c6182006-10-11 01:21:03 -07002956 * then we need to clear up the orphan record which we created above.
2957 * However, if this was a real unlink then we were called by
2958 * ext4_delete_inode(), and we allow that function to clean up the
2959 * orphan info for us.
2960 */
2961 if (inode->i_nlink)
2962 ext4_orphan_del(handle, inode);
2963
Solofo Ramangalahyef737722008-04-29 22:00:41 -04002964 inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
2965 ext4_mark_inode_dirty(handle, inode);
Alex Tomasa86c6182006-10-11 01:21:03 -07002966 ext4_journal_stop(handle);
2967}
2968
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04002969static void ext4_falloc_update_inode(struct inode *inode,
2970 int mode, loff_t new_size, int update_ctime)
2971{
2972 struct timespec now;
2973
2974 if (update_ctime) {
2975 now = current_fs_time(inode->i_sb);
2976 if (!timespec_equal(&inode->i_ctime, &now))
2977 inode->i_ctime = now;
2978 }
2979 /*
2980 * Update only when preallocation was requested beyond
2981 * the file size.
2982 */
Aneesh Kumar K.Vcf17fea2008-09-13 13:06:18 -04002983 if (!(mode & FALLOC_FL_KEEP_SIZE)) {
2984 if (new_size > i_size_read(inode))
2985 i_size_write(inode, new_size);
2986 if (new_size > EXT4_I(inode)->i_disksize)
2987 ext4_update_i_disksize(inode, new_size);
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04002988 }
2989
2990}
2991
Amit Aroraa2df2a62007-07-17 21:42:41 -04002992/*
2993 * preallocate space for a file. This implements ext4's fallocate inode
2994 * operation, which gets called from sys_fallocate system call.
2995 * For block-mapped files, posix_fallocate should fall back to the method
2996 * of writing zeroes to the required new blocks (the same behavior which is
2997 * expected for file systems which do not support fallocate() system call).
2998 */
2999long ext4_fallocate(struct inode *inode, int mode, loff_t offset, loff_t len)
3000{
3001 handle_t *handle;
Aneesh Kumar K.V725d26d2008-01-28 23:58:27 -05003002 ext4_lblk_t block;
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04003003 loff_t new_size;
Theodore Ts'o498e5f22008-11-05 00:14:04 -05003004 unsigned int max_blocks;
Amit Aroraa2df2a62007-07-17 21:42:41 -04003005 int ret = 0;
3006 int ret2 = 0;
3007 int retries = 0;
3008 struct buffer_head map_bh;
3009 unsigned int credits, blkbits = inode->i_blkbits;
3010
3011 /*
3012 * currently supporting (pre)allocate mode for extent-based
3013 * files _only_
3014 */
3015 if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
3016 return -EOPNOTSUPP;
3017
3018 /* preallocation to directories is currently not supported */
3019 if (S_ISDIR(inode->i_mode))
3020 return -ENODEV;
3021
3022 block = offset >> blkbits;
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04003023 /*
3024 * We can't just convert len to max_blocks because
3025 * If blocksize = 4096 offset = 3072 and len = 2048
3026 */
Amit Aroraa2df2a62007-07-17 21:42:41 -04003027 max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04003028 - block;
Amit Aroraa2df2a62007-07-17 21:42:41 -04003029 /*
Mingming Caof3bd1f32008-08-19 22:16:03 -04003030 * credits to insert 1 extent into extent tree
Amit Aroraa2df2a62007-07-17 21:42:41 -04003031 */
Mingming Caof3bd1f32008-08-19 22:16:03 -04003032 credits = ext4_chunk_trans_blocks(inode, max_blocks);
Aneesh Kumar K.V55bd7252008-02-15 12:47:21 -05003033 mutex_lock(&inode->i_mutex);
Amit Aroraa2df2a62007-07-17 21:42:41 -04003034retry:
3035 while (ret >= 0 && ret < max_blocks) {
3036 block = block + ret;
3037 max_blocks = max_blocks - ret;
3038 handle = ext4_journal_start(inode, credits);
3039 if (IS_ERR(handle)) {
3040 ret = PTR_ERR(handle);
3041 break;
3042 }
Aneesh Kumar K.V55bd7252008-02-15 12:47:21 -05003043 ret = ext4_get_blocks_wrap(handle, inode, block,
Amit Aroraa2df2a62007-07-17 21:42:41 -04003044 max_blocks, &map_bh,
Mingming Caod2a17632008-07-14 17:52:37 -04003045 EXT4_CREATE_UNINITIALIZED_EXT, 0, 0);
Aneesh Kumar K.V221879c2008-01-28 23:58:27 -05003046 if (ret <= 0) {
Aneesh Kumar K.V2c986152008-02-25 15:41:35 -05003047#ifdef EXT4FS_DEBUG
3048 WARN_ON(ret <= 0);
3049 printk(KERN_ERR "%s: ext4_ext_get_blocks "
3050 "returned error inode#%lu, block=%u, "
3051 "max_blocks=%lu", __func__,
Aneesh Kumar K.V221879c2008-01-28 23:58:27 -05003052 inode->i_ino, block, max_blocks);
Aneesh Kumar K.V2c986152008-02-25 15:41:35 -05003053#endif
Amit Aroraa2df2a62007-07-17 21:42:41 -04003054 ext4_mark_inode_dirty(handle, inode);
3055 ret2 = ext4_journal_stop(handle);
3056 break;
3057 }
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04003058 if ((block + ret) >= (EXT4_BLOCK_ALIGN(offset + len,
3059 blkbits) >> blkbits))
3060 new_size = offset + len;
3061 else
3062 new_size = (block + ret) << blkbits;
Amit Aroraa2df2a62007-07-17 21:42:41 -04003063
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04003064 ext4_falloc_update_inode(inode, mode, new_size,
3065 buffer_new(&map_bh));
Amit Aroraa2df2a62007-07-17 21:42:41 -04003066 ext4_mark_inode_dirty(handle, inode);
3067 ret2 = ext4_journal_stop(handle);
3068 if (ret2)
3069 break;
3070 }
Aneesh Kumar K.Vfd287842008-04-29 08:11:12 -04003071 if (ret == -ENOSPC &&
3072 ext4_should_retry_alloc(inode->i_sb, &retries)) {
3073 ret = 0;
Amit Aroraa2df2a62007-07-17 21:42:41 -04003074 goto retry;
Amit Aroraa2df2a62007-07-17 21:42:41 -04003075 }
Aneesh Kumar K.V55bd7252008-02-15 12:47:21 -05003076 mutex_unlock(&inode->i_mutex);
Amit Aroraa2df2a62007-07-17 21:42:41 -04003077 return ret > 0 ? ret2 : ret;
3078}
Eric Sandeen6873fa02008-10-07 00:46:36 -04003079
3080/*
3081 * Callback function called for each extent to gather FIEMAP information.
3082 */
Aneesh Kumar K.V3a06d772008-11-22 15:04:59 -05003083static int ext4_ext_fiemap_cb(struct inode *inode, struct ext4_ext_path *path,
Eric Sandeen6873fa02008-10-07 00:46:36 -04003084 struct ext4_ext_cache *newex, struct ext4_extent *ex,
3085 void *data)
3086{
3087 struct fiemap_extent_info *fieinfo = data;
3088 unsigned long blksize_bits = inode->i_sb->s_blocksize_bits;
3089 __u64 logical;
3090 __u64 physical;
3091 __u64 length;
3092 __u32 flags = 0;
3093 int error;
3094
3095 logical = (__u64)newex->ec_block << blksize_bits;
3096
3097 if (newex->ec_type == EXT4_EXT_CACHE_GAP) {
3098 pgoff_t offset;
3099 struct page *page;
3100 struct buffer_head *bh = NULL;
3101
3102 offset = logical >> PAGE_SHIFT;
3103 page = find_get_page(inode->i_mapping, offset);
3104 if (!page || !page_has_buffers(page))
3105 return EXT_CONTINUE;
3106
3107 bh = page_buffers(page);
3108
3109 if (!bh)
3110 return EXT_CONTINUE;
3111
3112 if (buffer_delay(bh)) {
3113 flags |= FIEMAP_EXTENT_DELALLOC;
3114 page_cache_release(page);
3115 } else {
3116 page_cache_release(page);
3117 return EXT_CONTINUE;
3118 }
3119 }
3120
3121 physical = (__u64)newex->ec_start << blksize_bits;
3122 length = (__u64)newex->ec_len << blksize_bits;
3123
3124 if (ex && ext4_ext_is_uninitialized(ex))
3125 flags |= FIEMAP_EXTENT_UNWRITTEN;
3126
3127 /*
3128 * If this extent reaches EXT_MAX_BLOCK, it must be last.
3129 *
3130 * Or if ext4_ext_next_allocated_block is EXT_MAX_BLOCK,
3131 * this also indicates no more allocated blocks.
3132 *
3133 * XXX this might miss a single-block extent at EXT_MAX_BLOCK
3134 */
3135 if (logical + length - 1 == EXT_MAX_BLOCK ||
3136 ext4_ext_next_allocated_block(path) == EXT_MAX_BLOCK)
3137 flags |= FIEMAP_EXTENT_LAST;
3138
3139 error = fiemap_fill_next_extent(fieinfo, logical, physical,
3140 length, flags);
3141 if (error < 0)
3142 return error;
3143 if (error == 1)
3144 return EXT_BREAK;
3145
3146 return EXT_CONTINUE;
3147}
3148
3149/* fiemap flags we can handle specified here */
3150#define EXT4_FIEMAP_FLAGS (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
3151
Aneesh Kumar K.V3a06d772008-11-22 15:04:59 -05003152static int ext4_xattr_fiemap(struct inode *inode,
3153 struct fiemap_extent_info *fieinfo)
Eric Sandeen6873fa02008-10-07 00:46:36 -04003154{
3155 __u64 physical = 0;
3156 __u64 length;
3157 __u32 flags = FIEMAP_EXTENT_LAST;
3158 int blockbits = inode->i_sb->s_blocksize_bits;
3159 int error = 0;
3160
3161 /* in-inode? */
3162 if (EXT4_I(inode)->i_state & EXT4_STATE_XATTR) {
3163 struct ext4_iloc iloc;
3164 int offset; /* offset of xattr in inode */
3165
3166 error = ext4_get_inode_loc(inode, &iloc);
3167 if (error)
3168 return error;
3169 physical = iloc.bh->b_blocknr << blockbits;
3170 offset = EXT4_GOOD_OLD_INODE_SIZE +
3171 EXT4_I(inode)->i_extra_isize;
3172 physical += offset;
3173 length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
3174 flags |= FIEMAP_EXTENT_DATA_INLINE;
3175 } else { /* external block */
3176 physical = EXT4_I(inode)->i_file_acl << blockbits;
3177 length = inode->i_sb->s_blocksize;
3178 }
3179
3180 if (physical)
3181 error = fiemap_fill_next_extent(fieinfo, 0, physical,
3182 length, flags);
3183 return (error < 0 ? error : 0);
3184}
3185
3186int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
3187 __u64 start, __u64 len)
3188{
3189 ext4_lblk_t start_blk;
3190 ext4_lblk_t len_blks;
3191 int error = 0;
3192
3193 /* fallback to generic here if not in extents fmt */
3194 if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
3195 return generic_block_fiemap(inode, fieinfo, start, len,
3196 ext4_get_block);
3197
3198 if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
3199 return -EBADR;
3200
3201 if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
3202 error = ext4_xattr_fiemap(inode, fieinfo);
3203 } else {
3204 start_blk = start >> inode->i_sb->s_blocksize_bits;
3205 len_blks = len >> inode->i_sb->s_blocksize_bits;
3206
3207 /*
3208 * Walk the extent tree gathering extent information.
3209 * ext4_ext_fiemap_cb will push extents back to user.
3210 */
3211 down_write(&EXT4_I(inode)->i_data_sem);
3212 error = ext4_ext_walk_space(inode, start_blk, len_blks,
3213 ext4_ext_fiemap_cb, fieinfo);
3214 up_write(&EXT4_I(inode)->i_data_sem);
3215 }
3216
3217 return error;
3218}
3219