2
* linux/fs/ext4/indirect.c
6
* linux/fs/ext4/inode.c
8
* Copyright (C) 1992, 1993, 1994, 1995
9
* Remy Card (card@masi.ibp.fr)
10
* Laboratoire MASI - Institut Blaise Pascal
11
* Universite Pierre et Marie Curie (Paris VI)
15
* linux/fs/minix/inode.c
17
* Copyright (C) 1991, 1992 Linus Torvalds
19
* Goal-directed block allocation by Stephen Tweedie
20
* (sct@redhat.com), 1993, 1998
23
#include <linux/module.h>
24
#include "ext4_jbd2.h"
27
#include <trace/events/ext4.h>
32
struct buffer_head *bh;
35
static inline void add_chain(Indirect *p, struct buffer_head *bh, __le32 *v)
42
* ext4_block_to_path - parse the block number into array of offsets
43
* @inode: inode in question (we are only interested in its superblock)
44
* @i_block: block number to be parsed
45
* @offsets: array to store the offsets in
46
* @boundary: set this non-zero if the referred-to block is likely to be
47
* followed (on disk) by an indirect block.
49
* To store the locations of file's data ext4 uses a data structure common
50
* for UNIX filesystems - tree of pointers anchored in the inode, with
51
* data blocks at leaves and indirect blocks in intermediate nodes.
52
* This function translates the block number into path in that tree -
53
* return value is the path length and @offsets[n] is the offset of
54
* pointer to (n+1)th node in the nth one. If @block is out of range
55
* (negative or too large) warning is printed and zero returned.
57
* Note: function doesn't find node addresses, so no IO is needed. All
58
* we need to know is the capacity of indirect blocks (taken from the
63
* Portability note: the last comparison (check that we fit into triple
64
* indirect block) is spelled differently, because otherwise on an
65
* architecture with 32-bit longs and 8Kb pages we might get into trouble
66
* if our filesystem had 8Kb blocks. We might use long long, but that would
67
* kill us on x86. Oh, well, at least the sign propagation does not matter -
68
* i_block would have to be negative in the very beginning, so we would not
72
static int ext4_block_to_path(struct inode *inode,
74
ext4_lblk_t offsets[4], int *boundary)
76
int ptrs = EXT4_ADDR_PER_BLOCK(inode->i_sb);
77
int ptrs_bits = EXT4_ADDR_PER_BLOCK_BITS(inode->i_sb);
78
const long direct_blocks = EXT4_NDIR_BLOCKS,
79
indirect_blocks = ptrs,
80
double_blocks = (1 << (ptrs_bits * 2));
84
if (i_block < direct_blocks) {
85
offsets[n++] = i_block;
86
final = direct_blocks;
87
} else if ((i_block -= direct_blocks) < indirect_blocks) {
88
offsets[n++] = EXT4_IND_BLOCK;
89
offsets[n++] = i_block;
91
} else if ((i_block -= indirect_blocks) < double_blocks) {
92
offsets[n++] = EXT4_DIND_BLOCK;
93
offsets[n++] = i_block >> ptrs_bits;
94
offsets[n++] = i_block & (ptrs - 1);
96
} else if (((i_block -= double_blocks) >> (ptrs_bits * 2)) < ptrs) {
97
offsets[n++] = EXT4_TIND_BLOCK;
98
offsets[n++] = i_block >> (ptrs_bits * 2);
99
offsets[n++] = (i_block >> ptrs_bits) & (ptrs - 1);
100
offsets[n++] = i_block & (ptrs - 1);
103
ext4_warning(inode->i_sb, "block %lu > max in inode %lu",
104
i_block + direct_blocks +
105
indirect_blocks + double_blocks, inode->i_ino);
108
*boundary = final - 1 - (i_block & (ptrs - 1));
113
* ext4_get_branch - read the chain of indirect blocks leading to data
114
* @inode: inode in question
115
* @depth: depth of the chain (1 - direct pointer, etc.)
116
* @offsets: offsets of pointers in inode/indirect blocks
117
* @chain: place to store the result
118
* @err: here we store the error value
120
* Function fills the array of triples <key, p, bh> and returns %NULL
121
* if everything went OK or the pointer to the last filled triple
122
* (incomplete one) otherwise. Upon the return chain[i].key contains
123
* the number of (i+1)-th block in the chain (as it is stored in memory,
124
* i.e. little-endian 32-bit), chain[i].p contains the address of that
125
* number (it points into struct inode for i==0 and into the bh->b_data
126
* for i>0) and chain[i].bh points to the buffer_head of i-th indirect
127
* block for i>0 and NULL for i==0. In other words, it holds the block
128
* numbers of the chain, addresses they were taken from (and where we can
129
* verify that chain did not change) and buffer_heads hosting these
132
* Function stops when it stumbles upon zero pointer (absent block)
133
* (pointer to last triple returned, *@err == 0)
134
* or when it gets an IO error reading an indirect block
135
* (ditto, *@err == -EIO)
136
* or when it reads all @depth-1 indirect blocks successfully and finds
137
* the whole chain, all way to the data (returns %NULL, *err == 0).
139
* Need to be called with
140
* down_read(&EXT4_I(inode)->i_data_sem)
142
static Indirect *ext4_get_branch(struct inode *inode, int depth,
143
ext4_lblk_t *offsets,
144
Indirect chain[4], int *err)
146
struct super_block *sb = inode->i_sb;
148
struct buffer_head *bh;
151
/* i_data is not going away, no lock needed */
152
add_chain(chain, NULL, EXT4_I(inode)->i_data + *offsets);
156
bh = sb_getblk(sb, le32_to_cpu(p->key));
160
if (!bh_uptodate_or_lock(bh)) {
161
if (bh_submit_read(bh) < 0) {
165
/* validate block references */
166
if (ext4_check_indirect_blockref(inode, bh)) {
172
add_chain(++p, bh, (__le32 *)bh->b_data + *++offsets);
186
* ext4_find_near - find a place for allocation with sufficient locality
188
* @ind: descriptor of indirect block.
190
* This function returns the preferred place for block allocation.
191
* It is used when heuristic for sequential allocation fails.
193
* + if there is a block to the left of our position - allocate near it.
194
* + if pointer will live in indirect block - allocate near that block.
195
* + if pointer will live in inode - allocate in the same
198
* In the latter case we colour the starting block by the callers PID to
199
* prevent it from clashing with concurrent allocations for a different inode
200
* in the same block group. The PID is used here so that functionally related
201
* files will be close-by on-disk.
203
* Caller must make sure that @ind is valid and will stay that way.
205
static ext4_fsblk_t ext4_find_near(struct inode *inode, Indirect *ind)
207
struct ext4_inode_info *ei = EXT4_I(inode);
208
__le32 *start = ind->bh ? (__le32 *) ind->bh->b_data : ei->i_data;
211
/* Try to find previous block */
212
for (p = ind->p - 1; p >= start; p--) {
214
return le32_to_cpu(*p);
217
/* No such thing, so let's try location of indirect block */
219
return ind->bh->b_blocknr;
222
* It is going to be referred to from the inode itself? OK, just put it
223
* into the same cylinder group then.
225
return ext4_inode_to_goal_block(inode);
229
* ext4_find_goal - find a preferred place for allocation.
231
* @block: block we want
232
* @partial: pointer to the last triple within a chain
234
* Normally this function find the preferred place for block allocation,
236
* Because this is only used for non-extent files, we limit the block nr
239
static ext4_fsblk_t ext4_find_goal(struct inode *inode, ext4_lblk_t block,
245
* XXX need to get goal block from mballoc's data structures
248
goal = ext4_find_near(inode, partial);
249
goal = goal & EXT4_MAX_BLOCK_FILE_PHYS;
254
* ext4_blks_to_allocate - Look up the block map and count the number
255
* of direct blocks need to be allocated for the given branch.
257
* @branch: chain of indirect blocks
258
* @k: number of blocks need for indirect blocks
259
* @blks: number of data blocks to be mapped.
260
* @blocks_to_boundary: the offset in the indirect block
262
* return the total number of blocks to be allocate, including the
263
* direct and indirect blocks.
265
static int ext4_blks_to_allocate(Indirect *branch, int k, unsigned int blks,
266
int blocks_to_boundary)
268
unsigned int count = 0;
271
* Simple case, [t,d]Indirect block(s) has not allocated yet
272
* then it's clear blocks on that path have not allocated
275
/* right now we don't handle cross boundary allocation */
276
if (blks < blocks_to_boundary + 1)
279
count += blocks_to_boundary + 1;
284
while (count < blks && count <= blocks_to_boundary &&
285
le32_to_cpu(*(branch[0].p + count)) == 0) {
292
* ext4_alloc_blocks: multiple allocate blocks needed for a branch
293
* @handle: handle for this transaction
294
* @inode: inode which needs allocated blocks
295
* @iblock: the logical block to start allocated at
296
* @goal: preferred physical block of allocation
297
* @indirect_blks: the number of blocks need to allocate for indirect
299
* @blks: number of desired blocks
300
* @new_blocks: on return it will store the new block numbers for
301
* the indirect blocks(if needed) and the first direct block,
302
* @err: on return it will store the error code
304
* This function will return the number of blocks allocated as
305
* requested by the passed-in parameters.
307
static int ext4_alloc_blocks(handle_t *handle, struct inode *inode,
308
ext4_lblk_t iblock, ext4_fsblk_t goal,
309
int indirect_blks, int blks,
310
ext4_fsblk_t new_blocks[4], int *err)
312
struct ext4_allocation_request ar;
314
unsigned long count = 0, blk_allocated = 0;
316
ext4_fsblk_t current_block = 0;
320
* Here we try to allocate the requested multiple blocks at once,
321
* on a best-effort basis.
322
* To build a branch, we should allocate blocks for
323
* the indirect blocks(if not allocated yet), and at least
324
* the first direct block of this branch. That's the
325
* minimum number of blocks need to allocate(required)
327
/* first we try to allocate the indirect blocks */
328
target = indirect_blks;
331
/* allocating blocks for indirect blocks and direct blocks */
332
current_block = ext4_new_meta_blocks(handle, inode, goal,
337
if (unlikely(current_block + count > EXT4_MAX_BLOCK_FILE_PHYS)) {
338
EXT4_ERROR_INODE(inode,
339
"current_block %llu + count %lu > %d!",
340
current_block, count,
341
EXT4_MAX_BLOCK_FILE_PHYS);
347
/* allocate blocks for indirect blocks */
348
while (index < indirect_blks && count) {
349
new_blocks[index++] = current_block++;
354
* save the new block number
355
* for the first direct block
357
new_blocks[index] = current_block;
358
printk(KERN_INFO "%s returned more blocks than "
359
"requested\n", __func__);
365
target = blks - count ;
366
blk_allocated = count;
369
/* Now allocate data blocks */
370
memset(&ar, 0, sizeof(ar));
375
if (S_ISREG(inode->i_mode))
376
/* enable in-core preallocation only for regular files */
377
ar.flags = EXT4_MB_HINT_DATA;
379
current_block = ext4_mb_new_blocks(handle, &ar, err);
380
if (unlikely(current_block + ar.len > EXT4_MAX_BLOCK_FILE_PHYS)) {
381
EXT4_ERROR_INODE(inode,
382
"current_block %llu + ar.len %d > %d!",
383
current_block, ar.len,
384
EXT4_MAX_BLOCK_FILE_PHYS);
389
if (*err && (target == blks)) {
391
* if the allocation failed and we didn't allocate
397
if (target == blks) {
399
* save the new block number
400
* for the first direct block
402
new_blocks[index] = current_block;
404
blk_allocated += ar.len;
407
/* total number of blocks allocated for direct blocks */
412
for (i = 0; i < index; i++)
413
ext4_free_blocks(handle, inode, NULL, new_blocks[i], 1, 0);
418
* ext4_alloc_branch - allocate and set up a chain of blocks.
419
* @handle: handle for this transaction
421
* @indirect_blks: number of allocated indirect blocks
422
* @blks: number of allocated direct blocks
423
* @goal: preferred place for allocation
424
* @offsets: offsets (in the blocks) to store the pointers to next.
425
* @branch: place to store the chain in.
427
* This function allocates blocks, zeroes out all but the last one,
428
* links them into chain and (if we are synchronous) writes them to disk.
429
* In other words, it prepares a branch that can be spliced onto the
430
* inode. It stores the information about that chain in the branch[], in
431
* the same format as ext4_get_branch() would do. We are calling it after
432
* we had read the existing part of chain and partial points to the last
433
* triple of that (one with zero ->key). Upon the exit we have the same
434
* picture as after the successful ext4_get_block(), except that in one
435
* place chain is disconnected - *branch->p is still zero (we did not
436
* set the last link), but branch->key contains the number that should
437
* be placed into *branch->p to fill that gap.
439
* If allocation fails we free all blocks we've allocated (and forget
440
* their buffer_heads) and return the error value the from failed
441
* ext4_alloc_block() (normally -ENOSPC). Otherwise we set the chain
442
* as described above and return 0.
444
static int ext4_alloc_branch(handle_t *handle, struct inode *inode,
445
ext4_lblk_t iblock, int indirect_blks,
446
int *blks, ext4_fsblk_t goal,
447
ext4_lblk_t *offsets, Indirect *branch)
449
int blocksize = inode->i_sb->s_blocksize;
452
struct buffer_head *bh;
454
ext4_fsblk_t new_blocks[4];
455
ext4_fsblk_t current_block;
457
num = ext4_alloc_blocks(handle, inode, iblock, goal, indirect_blks,
458
*blks, new_blocks, &err);
462
branch[0].key = cpu_to_le32(new_blocks[0]);
464
* metadata blocks and data blocks are allocated.
466
for (n = 1; n <= indirect_blks; n++) {
468
* Get buffer_head for parent block, zero it out
469
* and set the pointer to new one, then send
472
bh = sb_getblk(inode->i_sb, new_blocks[n-1]);
480
BUFFER_TRACE(bh, "call get_create_access");
481
err = ext4_journal_get_create_access(handle, bh);
483
/* Don't brelse(bh) here; it's done in
484
* ext4_journal_forget() below */
489
memset(bh->b_data, 0, blocksize);
490
branch[n].p = (__le32 *) bh->b_data + offsets[n];
491
branch[n].key = cpu_to_le32(new_blocks[n]);
492
*branch[n].p = branch[n].key;
493
if (n == indirect_blks) {
494
current_block = new_blocks[n];
496
* End of chain, update the last new metablock of
497
* the chain to point to the new allocated
498
* data blocks numbers
500
for (i = 1; i < num; i++)
501
*(branch[n].p + i) = cpu_to_le32(++current_block);
503
BUFFER_TRACE(bh, "marking uptodate");
504
set_buffer_uptodate(bh);
507
BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
508
err = ext4_handle_dirty_metadata(handle, inode, bh);
515
/* Allocation failed, free what we already allocated */
516
ext4_free_blocks(handle, inode, NULL, new_blocks[0], 1, 0);
517
for (i = 1; i <= n ; i++) {
519
* branch[i].bh is newly allocated, so there is no
520
* need to revoke the block, which is why we don't
521
* need to set EXT4_FREE_BLOCKS_METADATA.
523
ext4_free_blocks(handle, inode, NULL, new_blocks[i], 1,
524
EXT4_FREE_BLOCKS_FORGET);
526
for (i = n+1; i < indirect_blks; i++)
527
ext4_free_blocks(handle, inode, NULL, new_blocks[i], 1, 0);
529
ext4_free_blocks(handle, inode, NULL, new_blocks[i], num, 0);
535
* ext4_splice_branch - splice the allocated branch onto inode.
536
* @handle: handle for this transaction
538
* @block: (logical) number of block we are adding
539
* @chain: chain of indirect blocks (with a missing link - see
541
* @where: location of missing link
542
* @num: number of indirect blocks we are adding
543
* @blks: number of direct blocks we are adding
545
* This function fills the missing link and does all housekeeping needed in
546
* inode (->i_blocks, etc.). In case of success we end up with the full
547
* chain to new block and return 0.
549
static int ext4_splice_branch(handle_t *handle, struct inode *inode,
550
ext4_lblk_t block, Indirect *where, int num,
555
ext4_fsblk_t current_block;
558
* If we're splicing into a [td]indirect block (as opposed to the
559
* inode) then we need to get write access to the [td]indirect block
563
BUFFER_TRACE(where->bh, "get_write_access");
564
err = ext4_journal_get_write_access(handle, where->bh);
570
*where->p = where->key;
573
* Update the host buffer_head or inode to point to more just allocated
574
* direct blocks blocks
576
if (num == 0 && blks > 1) {
577
current_block = le32_to_cpu(where->key) + 1;
578
for (i = 1; i < blks; i++)
579
*(where->p + i) = cpu_to_le32(current_block++);
582
/* We are done with atomic stuff, now do the rest of housekeeping */
583
/* had we spliced it onto indirect block? */
586
* If we spliced it onto an indirect block, we haven't
587
* altered the inode. Note however that if it is being spliced
588
* onto an indirect block at the very end of the file (the
589
* file is growing) then we *will* alter the inode to reflect
590
* the new i_size. But that is not done here - it is done in
591
* generic_commit_write->__mark_inode_dirty->ext4_dirty_inode.
593
jbd_debug(5, "splicing indirect only\n");
594
BUFFER_TRACE(where->bh, "call ext4_handle_dirty_metadata");
595
err = ext4_handle_dirty_metadata(handle, inode, where->bh);
600
* OK, we spliced it into the inode itself on a direct block.
602
ext4_mark_inode_dirty(handle, inode);
603
jbd_debug(5, "splicing direct\n");
608
for (i = 1; i <= num; i++) {
610
* branch[i].bh is newly allocated, so there is no
611
* need to revoke the block, which is why we don't
612
* need to set EXT4_FREE_BLOCKS_METADATA.
614
ext4_free_blocks(handle, inode, where[i].bh, 0, 1,
615
EXT4_FREE_BLOCKS_FORGET);
617
ext4_free_blocks(handle, inode, NULL, le32_to_cpu(where[num].key),
624
* The ext4_ind_map_blocks() function handles non-extents inodes
625
* (i.e., using the traditional indirect/double-indirect i_blocks
626
* scheme) for ext4_map_blocks().
628
* Allocation strategy is simple: if we have to allocate something, we will
629
* have to go the whole way to leaf. So let's do it before attaching anything
630
* to tree, set linkage between the newborn blocks, write them if sync is
631
* required, recheck the path, free and repeat if check fails, otherwise
632
* set the last missing link (that will protect us from any truncate-generated
633
* removals - all blocks on the path are immune now) and possibly force the
634
* write on the parent block.
635
* That has a nice additional property: no special recovery from the failed
636
* allocations is needed - we simply release blocks and do not touch anything
637
* reachable from inode.
639
* `handle' can be NULL if create == 0.
641
* return > 0, # of blocks mapped or allocated.
642
* return = 0, if plain lookup failed.
643
* return < 0, error case.
645
* The ext4_ind_get_blocks() function should be called with
646
* down_write(&EXT4_I(inode)->i_data_sem) if allocating filesystem
647
* blocks (i.e., flags has EXT4_GET_BLOCKS_CREATE set) or
648
* down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system
651
int ext4_ind_map_blocks(handle_t *handle, struct inode *inode,
652
struct ext4_map_blocks *map,
656
ext4_lblk_t offsets[4];
661
int blocks_to_boundary = 0;
664
ext4_fsblk_t first_block = 0;
666
trace_ext4_ind_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
667
J_ASSERT(!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)));
668
J_ASSERT(handle != NULL || (flags & EXT4_GET_BLOCKS_CREATE) == 0);
669
depth = ext4_block_to_path(inode, map->m_lblk, offsets,
670
&blocks_to_boundary);
675
partial = ext4_get_branch(inode, depth, offsets, chain, &err);
677
/* Simplest case - block found, no allocation needed */
679
first_block = le32_to_cpu(chain[depth - 1].key);
682
while (count < map->m_len && count <= blocks_to_boundary) {
685
blk = le32_to_cpu(*(chain[depth-1].p + count));
687
if (blk == first_block + count)
695
/* Next simple case - plain lookup or failed read of indirect block */
696
if ((flags & EXT4_GET_BLOCKS_CREATE) == 0 || err == -EIO)
700
* Okay, we need to do block allocation.
702
if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
703
EXT4_FEATURE_RO_COMPAT_BIGALLOC)) {
704
EXT4_ERROR_INODE(inode, "Can't allocate blocks for "
705
"non-extent mapped inodes with bigalloc");
709
goal = ext4_find_goal(inode, map->m_lblk, partial);
711
/* the number of blocks need to allocate for [d,t]indirect blocks */
712
indirect_blks = (chain + depth) - partial - 1;
715
* Next look up the indirect map to count the totoal number of
716
* direct blocks to allocate for this branch.
718
count = ext4_blks_to_allocate(partial, indirect_blks,
719
map->m_len, blocks_to_boundary);
721
* Block out ext4_truncate while we alter the tree
723
err = ext4_alloc_branch(handle, inode, map->m_lblk, indirect_blks,
725
offsets + (partial - chain), partial);
728
* The ext4_splice_branch call will free and forget any buffers
729
* on the new chain if there is a failure, but that risks using
730
* up transaction credits, especially for bitmaps where the
731
* credits cannot be returned. Can we handle this somehow? We
732
* may need to return -EAGAIN upwards in the worst case. --sct
735
err = ext4_splice_branch(handle, inode, map->m_lblk,
736
partial, indirect_blks, count);
740
map->m_flags |= EXT4_MAP_NEW;
742
ext4_update_inode_fsync_trans(handle, inode, 1);
744
map->m_flags |= EXT4_MAP_MAPPED;
745
map->m_pblk = le32_to_cpu(chain[depth-1].key);
747
if (count > blocks_to_boundary)
748
map->m_flags |= EXT4_MAP_BOUNDARY;
750
/* Clean up and exit */
751
partial = chain + depth - 1; /* the whole chain */
753
while (partial > chain) {
754
BUFFER_TRACE(partial->bh, "call brelse");
759
trace_ext4_ind_map_blocks_exit(inode, map->m_lblk,
760
map->m_pblk, map->m_len, err);
765
* O_DIRECT for ext3 (or indirect map) based files
767
* If the O_DIRECT write will extend the file then add this inode to the
768
* orphan list. So recovery will truncate it back to the original size
769
* if the machine crashes during the write.
771
* If the O_DIRECT write is intantiating holes inside i_size and the machine
772
* crashes then stale disk data _may_ be exposed inside the file. But current
773
* VFS code falls back into buffered path in that case so we are safe.
775
ssize_t ext4_ind_direct_IO(int rw, struct kiocb *iocb,
776
const struct iovec *iov, loff_t offset,
777
unsigned long nr_segs)
779
struct file *file = iocb->ki_filp;
780
struct inode *inode = file->f_mapping->host;
781
struct ext4_inode_info *ei = EXT4_I(inode);
785
size_t count = iov_length(iov, nr_segs);
789
loff_t final_size = offset + count;
791
if (final_size > inode->i_size) {
792
/* Credits for sb + inode write */
793
handle = ext4_journal_start(inode, 2);
794
if (IS_ERR(handle)) {
795
ret = PTR_ERR(handle);
798
ret = ext4_orphan_add(handle, inode);
800
ext4_journal_stop(handle);
804
ei->i_disksize = inode->i_size;
805
ext4_journal_stop(handle);
810
if (rw == READ && ext4_should_dioread_nolock(inode)) {
811
if (unlikely(!list_empty(&ei->i_completed_io_list))) {
812
mutex_lock(&inode->i_mutex);
813
ext4_flush_completed_IO(inode);
814
mutex_unlock(&inode->i_mutex);
816
ret = __blockdev_direct_IO(rw, iocb, inode,
817
inode->i_sb->s_bdev, iov,
819
ext4_get_block, NULL, NULL, 0);
821
ret = blockdev_direct_IO(rw, iocb, inode, iov,
822
offset, nr_segs, ext4_get_block);
824
if (unlikely((rw & WRITE) && ret < 0)) {
825
loff_t isize = i_size_read(inode);
826
loff_t end = offset + iov_length(iov, nr_segs);
829
ext4_truncate_failed_write(inode);
832
if (ret == -ENOSPC && ext4_should_retry_alloc(inode->i_sb, &retries))
838
/* Credits for sb + inode write */
839
handle = ext4_journal_start(inode, 2);
840
if (IS_ERR(handle)) {
841
/* This is really bad luck. We've written the data
842
* but cannot extend i_size. Bail out and pretend
843
* the write failed... */
844
ret = PTR_ERR(handle);
846
ext4_orphan_del(NULL, inode);
851
ext4_orphan_del(handle, inode);
853
loff_t end = offset + ret;
854
if (end > inode->i_size) {
855
ei->i_disksize = end;
856
i_size_write(inode, end);
858
* We're going to return a positive `ret'
859
* here due to non-zero-length I/O, so there's
860
* no way of reporting error returns from
861
* ext4_mark_inode_dirty() to userspace. So
864
ext4_mark_inode_dirty(handle, inode);
867
err = ext4_journal_stop(handle);
876
* Calculate the number of metadata blocks need to reserve
877
* to allocate a new block at @lblocks for non extent file based file
879
int ext4_ind_calc_metadata_amount(struct inode *inode, sector_t lblock)
881
struct ext4_inode_info *ei = EXT4_I(inode);
882
sector_t dind_mask = ~((sector_t)EXT4_ADDR_PER_BLOCK(inode->i_sb) - 1);
885
if (lblock < EXT4_NDIR_BLOCKS)
888
lblock -= EXT4_NDIR_BLOCKS;
890
if (ei->i_da_metadata_calc_len &&
891
(lblock & dind_mask) == ei->i_da_metadata_calc_last_lblock) {
892
ei->i_da_metadata_calc_len++;
895
ei->i_da_metadata_calc_last_lblock = lblock & dind_mask;
896
ei->i_da_metadata_calc_len = 1;
897
blk_bits = order_base_2(lblock);
898
return (blk_bits / EXT4_ADDR_PER_BLOCK_BITS(inode->i_sb)) + 1;
901
int ext4_ind_trans_blocks(struct inode *inode, int nrblocks, int chunk)
905
/* if nrblocks are contiguous */
908
* With N contiguous data blocks, we need at most
909
* N/EXT4_ADDR_PER_BLOCK(inode->i_sb) + 1 indirect blocks,
910
* 2 dindirect blocks, and 1 tindirect block
912
return DIV_ROUND_UP(nrblocks,
913
EXT4_ADDR_PER_BLOCK(inode->i_sb)) + 4;
916
* if nrblocks are not contiguous, worse case, each block touch
917
* a indirect block, and each indirect block touch a double indirect
918
* block, plus a triple indirect block
920
indirects = nrblocks * 2 + 1;
925
* Truncate transactions can be complex and absolutely huge. So we need to
926
* be able to restart the transaction at a conventient checkpoint to make
927
* sure we don't overflow the journal.
929
* start_transaction gets us a new handle for a truncate transaction,
930
* and extend_transaction tries to extend the existing one a bit. If
931
* extend fails, we need to propagate the failure up and restart the
932
* transaction in the top-level truncate loop. --sct
934
static handle_t *start_transaction(struct inode *inode)
938
result = ext4_journal_start(inode, ext4_blocks_for_truncate(inode));
942
ext4_std_error(inode->i_sb, PTR_ERR(result));
947
* Try to extend this transaction for the purposes of truncation.
949
* Returns 0 if we managed to create more room. If we can't create more
950
* room, and the transaction must be restarted we return 1.
952
static int try_to_extend_transaction(handle_t *handle, struct inode *inode)
954
if (!ext4_handle_valid(handle))
956
if (ext4_handle_has_enough_credits(handle, EXT4_RESERVE_TRANS_BLOCKS+1))
958
if (!ext4_journal_extend(handle, ext4_blocks_for_truncate(inode)))
964
* Probably it should be a library function... search for first non-zero word
965
* or memcmp with zero_page, whatever is better for particular architecture.
968
static inline int all_zeroes(__le32 *p, __le32 *q)
977
* ext4_find_shared - find the indirect blocks for partial truncation.
978
* @inode: inode in question
979
* @depth: depth of the affected branch
980
* @offsets: offsets of pointers in that branch (see ext4_block_to_path)
981
* @chain: place to store the pointers to partial indirect blocks
982
* @top: place to the (detached) top of branch
984
* This is a helper function used by ext4_truncate().
986
* When we do truncate() we may have to clean the ends of several
987
* indirect blocks but leave the blocks themselves alive. Block is
988
* partially truncated if some data below the new i_size is referred
989
* from it (and it is on the path to the first completely truncated
990
* data block, indeed). We have to free the top of that path along
991
* with everything to the right of the path. Since no allocation
992
* past the truncation point is possible until ext4_truncate()
993
* finishes, we may safely do the latter, but top of branch may
994
* require special attention - pageout below the truncation point
995
* might try to populate it.
997
* We atomically detach the top of branch from the tree, store the
998
* block number of its root in *@top, pointers to buffer_heads of
999
* partially truncated blocks - in @chain[].bh and pointers to
1000
* their last elements that should not be removed - in
1001
* @chain[].p. Return value is the pointer to last filled element
1004
* The work left to caller to do the actual freeing of subtrees:
1005
* a) free the subtree starting from *@top
1006
* b) free the subtrees whose roots are stored in
1007
* (@chain[i].p+1 .. end of @chain[i].bh->b_data)
1008
* c) free the subtrees growing from the inode past the @chain[0].
1009
* (no partially truncated stuff there). */
1011
static Indirect *ext4_find_shared(struct inode *inode, int depth,
1012
ext4_lblk_t offsets[4], Indirect chain[4],
1015
Indirect *partial, *p;
1019
/* Make k index the deepest non-null offset + 1 */
1020
for (k = depth; k > 1 && !offsets[k-1]; k--)
1022
partial = ext4_get_branch(inode, k, offsets, chain, &err);
1023
/* Writer: pointers */
1025
partial = chain + k-1;
1027
* If the branch acquired continuation since we've looked at it -
1028
* fine, it should all survive and (new) top doesn't belong to us.
1030
if (!partial->key && *partial->p)
1033
for (p = partial; (p > chain) && all_zeroes((__le32 *) p->bh->b_data, p->p); p--)
1036
* OK, we've found the last block that must survive. The rest of our
1037
* branch should be detached before unlocking. However, if that rest
1038
* of branch is all ours and does not grow immediately from the inode
1039
* it's easier to cheat and just decrement partial->p.
1041
if (p == chain + k - 1 && p > chain) {
1045
/* Nope, don't do this in ext4. Must leave the tree intact */
1052
while (partial > p) {
1053
brelse(partial->bh);
1061
* Zero a number of block pointers in either an inode or an indirect block.
1062
* If we restart the transaction we must again get write access to the
1063
* indirect block for further modification.
1065
* We release `count' blocks on disk, but (last - first) may be greater
1066
* than `count' because there can be holes in there.
1068
* Return 0 on success, 1 on invalid block range
1069
* and < 0 on fatal error.
1071
static int ext4_clear_blocks(handle_t *handle, struct inode *inode,
1072
struct buffer_head *bh,
1073
ext4_fsblk_t block_to_free,
1074
unsigned long count, __le32 *first,
1078
int flags = EXT4_FREE_BLOCKS_FORGET | EXT4_FREE_BLOCKS_VALIDATED;
1081
if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
1082
flags |= EXT4_FREE_BLOCKS_METADATA;
1084
if (!ext4_data_block_valid(EXT4_SB(inode->i_sb), block_to_free,
1086
EXT4_ERROR_INODE(inode, "attempt to clear invalid "
1087
"blocks %llu len %lu",
1088
(unsigned long long) block_to_free, count);
1092
if (try_to_extend_transaction(handle, inode)) {
1094
BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
1095
err = ext4_handle_dirty_metadata(handle, inode, bh);
1099
err = ext4_mark_inode_dirty(handle, inode);
1102
err = ext4_truncate_restart_trans(handle, inode,
1103
ext4_blocks_for_truncate(inode));
1107
BUFFER_TRACE(bh, "retaking write access");
1108
err = ext4_journal_get_write_access(handle, bh);
1114
for (p = first; p < last; p++)
1117
ext4_free_blocks(handle, inode, NULL, block_to_free, count, flags);
1120
ext4_std_error(inode->i_sb, err);
1125
* ext4_free_data - free a list of data blocks
1126
* @handle: handle for this transaction
1127
* @inode: inode we are dealing with
1128
* @this_bh: indirect buffer_head which contains *@first and *@last
1129
* @first: array of block numbers
1130
* @last: points immediately past the end of array
1132
* We are freeing all blocks referred from that array (numbers are stored as
1133
* little-endian 32-bit) and updating @inode->i_blocks appropriately.
1135
* We accumulate contiguous runs of blocks to free. Conveniently, if these
1136
* blocks are contiguous then releasing them at one time will only affect one
1137
* or two bitmap blocks (+ group descriptor(s) and superblock) and we won't
1138
* actually use a lot of journal space.
1140
* @this_bh will be %NULL if @first and @last point into the inode's direct
1143
static void ext4_free_data(handle_t *handle, struct inode *inode,
1144
struct buffer_head *this_bh,
1145
__le32 *first, __le32 *last)
1147
ext4_fsblk_t block_to_free = 0; /* Starting block # of a run */
1148
unsigned long count = 0; /* Number of blocks in the run */
1149
__le32 *block_to_free_p = NULL; /* Pointer into inode/ind
1152
ext4_fsblk_t nr; /* Current block # */
1153
__le32 *p; /* Pointer into inode/ind
1154
for current block */
1157
if (this_bh) { /* For indirect block */
1158
BUFFER_TRACE(this_bh, "get_write_access");
1159
err = ext4_journal_get_write_access(handle, this_bh);
1160
/* Important: if we can't update the indirect pointers
1161
* to the blocks, we can't free them. */
1166
for (p = first; p < last; p++) {
1167
nr = le32_to_cpu(*p);
1169
/* accumulate blocks to free if they're contiguous */
1172
block_to_free_p = p;
1174
} else if (nr == block_to_free + count) {
1177
err = ext4_clear_blocks(handle, inode, this_bh,
1178
block_to_free, count,
1179
block_to_free_p, p);
1183
block_to_free_p = p;
1189
if (!err && count > 0)
1190
err = ext4_clear_blocks(handle, inode, this_bh, block_to_free,
1191
count, block_to_free_p, p);
1197
BUFFER_TRACE(this_bh, "call ext4_handle_dirty_metadata");
1200
* The buffer head should have an attached journal head at this
1201
* point. However, if the data is corrupted and an indirect
1202
* block pointed to itself, it would have been detached when
1203
* the block was cleared. Check for this instead of OOPSing.
1205
if ((EXT4_JOURNAL(inode) == NULL) || bh2jh(this_bh))
1206
ext4_handle_dirty_metadata(handle, inode, this_bh);
1208
EXT4_ERROR_INODE(inode,
1209
"circular indirect block detected at "
1211
(unsigned long long) this_bh->b_blocknr);
1216
* ext4_free_branches - free an array of branches
1217
* @handle: JBD handle for this transaction
1218
* @inode: inode we are dealing with
1219
* @parent_bh: the buffer_head which contains *@first and *@last
1220
* @first: array of block numbers
1221
* @last: pointer immediately past the end of array
1222
* @depth: depth of the branches to free
1224
* We are freeing all blocks referred from these branches (numbers are
1225
* stored as little-endian 32-bit) and updating @inode->i_blocks
1228
static void ext4_free_branches(handle_t *handle, struct inode *inode,
1229
struct buffer_head *parent_bh,
1230
__le32 *first, __le32 *last, int depth)
1235
if (ext4_handle_is_aborted(handle))
1239
struct buffer_head *bh;
1240
int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb);
1242
while (--p >= first) {
1243
nr = le32_to_cpu(*p);
1245
continue; /* A hole */
1247
if (!ext4_data_block_valid(EXT4_SB(inode->i_sb),
1249
EXT4_ERROR_INODE(inode,
1250
"invalid indirect mapped "
1251
"block %lu (level %d)",
1252
(unsigned long) nr, depth);
1256
/* Go read the buffer for the next level down */
1257
bh = sb_bread(inode->i_sb, nr);
1260
* A read failure? Report error and clear slot
1264
EXT4_ERROR_INODE_BLOCK(inode, nr,
1269
/* This zaps the entire block. Bottom up. */
1270
BUFFER_TRACE(bh, "free child branches");
1271
ext4_free_branches(handle, inode, bh,
1272
(__le32 *) bh->b_data,
1273
(__le32 *) bh->b_data + addr_per_block,
1278
* Everything below this this pointer has been
1279
* released. Now let this top-of-subtree go.
1281
* We want the freeing of this indirect block to be
1282
* atomic in the journal with the updating of the
1283
* bitmap block which owns it. So make some room in
1286
* We zero the parent pointer *after* freeing its
1287
* pointee in the bitmaps, so if extend_transaction()
1288
* for some reason fails to put the bitmap changes and
1289
* the release into the same transaction, recovery
1290
* will merely complain about releasing a free block,
1291
* rather than leaking blocks.
1293
if (ext4_handle_is_aborted(handle))
1295
if (try_to_extend_transaction(handle, inode)) {
1296
ext4_mark_inode_dirty(handle, inode);
1297
ext4_truncate_restart_trans(handle, inode,
1298
ext4_blocks_for_truncate(inode));
1302
* The forget flag here is critical because if
1303
* we are journaling (and not doing data
1304
* journaling), we have to make sure a revoke
1305
* record is written to prevent the journal
1306
* replay from overwriting the (former)
1307
* indirect block if it gets reallocated as a
1308
* data block. This must happen in the same
1309
* transaction where the data blocks are
1312
ext4_free_blocks(handle, inode, NULL, nr, 1,
1313
EXT4_FREE_BLOCKS_METADATA|
1314
EXT4_FREE_BLOCKS_FORGET);
1318
* The block which we have just freed is
1319
* pointed to by an indirect block: journal it
1321
BUFFER_TRACE(parent_bh, "get_write_access");
1322
if (!ext4_journal_get_write_access(handle,
1325
BUFFER_TRACE(parent_bh,
1326
"call ext4_handle_dirty_metadata");
1327
ext4_handle_dirty_metadata(handle,
1334
/* We have reached the bottom of the tree. */
1335
BUFFER_TRACE(parent_bh, "free data blocks");
1336
ext4_free_data(handle, inode, parent_bh, first, last);
1340
void ext4_ind_truncate(struct inode *inode)
1343
struct ext4_inode_info *ei = EXT4_I(inode);
1344
__le32 *i_data = ei->i_data;
1345
int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb);
1346
struct address_space *mapping = inode->i_mapping;
1347
ext4_lblk_t offsets[4];
1352
ext4_lblk_t last_block, max_block;
1354
unsigned blocksize = inode->i_sb->s_blocksize;
1357
handle = start_transaction(inode);
1359
return; /* AKPM: return what? */
1361
last_block = (inode->i_size + blocksize-1)
1362
>> EXT4_BLOCK_SIZE_BITS(inode->i_sb);
1363
max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1)
1364
>> EXT4_BLOCK_SIZE_BITS(inode->i_sb);
1366
if (inode->i_size % PAGE_CACHE_SIZE != 0) {
1367
page_len = PAGE_CACHE_SIZE -
1368
(inode->i_size & (PAGE_CACHE_SIZE - 1));
1370
err = ext4_discard_partial_page_buffers(handle,
1371
mapping, inode->i_size, page_len, 0);
1377
if (last_block != max_block) {
1378
n = ext4_block_to_path(inode, last_block, offsets, NULL);
1380
goto out_stop; /* error */
1384
* OK. This truncate is going to happen. We add the inode to the
1385
* orphan list, so that if this truncate spans multiple transactions,
1386
* and we crash, we will resume the truncate when the filesystem
1387
* recovers. It also marks the inode dirty, to catch the new size.
1389
* Implication: the file must always be in a sane, consistent
1390
* truncatable state while each transaction commits.
1392
if (ext4_orphan_add(handle, inode))
1396
* From here we block out all ext4_get_block() callers who want to
1397
* modify the block allocation tree.
1399
down_write(&ei->i_data_sem);
1401
ext4_discard_preallocations(inode);
1404
* The orphan list entry will now protect us from any crash which
1405
* occurs before the truncate completes, so it is now safe to propagate
1406
* the new, shorter inode size (held for now in i_size) into the
1407
* on-disk inode. We do this via i_disksize, which is the value which
1408
* ext4 *really* writes onto the disk inode.
1410
ei->i_disksize = inode->i_size;
1412
if (last_block == max_block) {
1414
* It is unnecessary to free any data blocks if last_block is
1415
* equal to the indirect block limit.
1418
} else if (n == 1) { /* direct blocks */
1419
ext4_free_data(handle, inode, NULL, i_data+offsets[0],
1420
i_data + EXT4_NDIR_BLOCKS);
1424
partial = ext4_find_shared(inode, n, offsets, chain, &nr);
1425
/* Kill the top of shared branch (not detached) */
1427
if (partial == chain) {
1428
/* Shared branch grows from the inode */
1429
ext4_free_branches(handle, inode, NULL,
1430
&nr, &nr+1, (chain+n-1) - partial);
1433
* We mark the inode dirty prior to restart,
1434
* and prior to stop. No need for it here.
1437
/* Shared branch grows from an indirect block */
1438
BUFFER_TRACE(partial->bh, "get_write_access");
1439
ext4_free_branches(handle, inode, partial->bh,
1441
partial->p+1, (chain+n-1) - partial);
1444
/* Clear the ends of indirect blocks on the shared branch */
1445
while (partial > chain) {
1446
ext4_free_branches(handle, inode, partial->bh, partial->p + 1,
1447
(__le32*)partial->bh->b_data+addr_per_block,
1448
(chain+n-1) - partial);
1449
BUFFER_TRACE(partial->bh, "call brelse");
1450
brelse(partial->bh);
1454
/* Kill the remaining (whole) subtrees */
1455
switch (offsets[0]) {
1457
nr = i_data[EXT4_IND_BLOCK];
1459
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 1);
1460
i_data[EXT4_IND_BLOCK] = 0;
1462
case EXT4_IND_BLOCK:
1463
nr = i_data[EXT4_DIND_BLOCK];
1465
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 2);
1466
i_data[EXT4_DIND_BLOCK] = 0;
1468
case EXT4_DIND_BLOCK:
1469
nr = i_data[EXT4_TIND_BLOCK];
1471
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 3);
1472
i_data[EXT4_TIND_BLOCK] = 0;
1474
case EXT4_TIND_BLOCK:
1479
up_write(&ei->i_data_sem);
1480
inode->i_mtime = inode->i_ctime = ext4_current_time(inode);
1481
ext4_mark_inode_dirty(handle, inode);
1484
* In a multi-transaction truncate, we only make the final transaction
1488
ext4_handle_sync(handle);
1491
* If this was a simple ftruncate(), and the file will remain alive
1492
* then we need to clear up the orphan record which we created above.
1493
* However, if this was a real unlink then we were called by
1494
* ext4_delete_inode(), and we allow that function to clean up the
1495
* orphan info for us.
1498
ext4_orphan_del(handle, inode);
1500
ext4_journal_stop(handle);
1501
trace_ext4_truncate_exit(inode);