| 1 |
// SPDX-License-Identifier: GPL-2.0 |
| 2 |
/* |
| 3 |
* linux/fs/ext4/indirect.c |
| 4 |
* |
| 5 |
* from |
| 6 |
* |
| 7 |
* linux/fs/ext4/inode.c |
| 8 |
* |
| 9 |
* Copyright (C) 1992, 1993, 1994, 1995 |
| 10 |
* Remy Card ([email protected]) |
| 11 |
* Laboratoire MASI - Institut Blaise Pascal |
| 12 |
* Universite Pierre et Marie Curie (Paris VI) |
| 13 |
* |
| 14 |
* from |
| 15 |
* |
| 16 |
* linux/fs/minix/inode.c |
| 17 |
* |
| 18 |
* Copyright (C) 1991, 1992 Linus Torvalds |
| 19 |
* |
| 20 |
* Goal-directed block allocation by Stephen Tweedie |
| 21 |
* ([email protected]), 1993, 1998 |
| 22 |
*/ |
| 23 |
|
| 24 |
#include "ext4_jbd2.h" |
| 25 |
#include "truncate.h" |
| 26 |
#include <linux/dax.h> |
| 27 |
#include <linux/uio.h> |
| 28 |
|
| 29 |
#include <trace/events/ext4.h> |
| 30 |
|
| 31 |
typedef struct { |
| 32 |
__le32 *p; |
| 33 |
__le32 key; |
| 34 |
struct buffer_head *bh; |
| 35 |
} Indirect; |
| 36 |
|
| 37 |
static inline void add_chain(Indirect *p, struct buffer_head *bh, __le32 *v) |
| 38 |
{ |
| 39 |
p->key = *(p->p = v); |
| 40 |
p->bh = bh; |
| 41 |
} |
| 42 |
|
| 43 |
/** |
| 44 |
* ext4_block_to_path - parse the block number into array of offsets |
| 45 |
* @inode: inode in question (we are only interested in its superblock) |
| 46 |
* @i_block: block number to be parsed |
| 47 |
* @offsets: array to store the offsets in |
| 48 |
* @boundary: set this non-zero if the referred-to block is likely to be |
| 49 |
* followed (on disk) by an indirect block. |
| 50 |
* |
| 51 |
* To store the locations of file's data ext4 uses a data structure common |
| 52 |
* for UNIX filesystems - tree of pointers anchored in the inode, with |
| 53 |
* data blocks at leaves and indirect blocks in intermediate nodes. |
| 54 |
* This function translates the block number into path in that tree - |
| 55 |
* return value is the path length and @offsets[n] is the offset of |
| 56 |
* pointer to (n+1)th node in the nth one. If @block is out of range |
| 57 |
* (negative or too large) warning is printed and zero returned. |
| 58 |
* |
| 59 |
* Note: function doesn't find node addresses, so no IO is needed. All |
| 60 |
* we need to know is the capacity of indirect blocks (taken from the |
| 61 |
* inode->i_sb). |
| 62 |
*/ |
| 63 |
|
| 64 |
/* |
| 65 |
* Portability note: the last comparison (check that we fit into triple |
| 66 |
* indirect block) is spelled differently, because otherwise on an |
| 67 |
* architecture with 32-bit longs and 8Kb pages we might get into trouble |
| 68 |
* if our filesystem had 8Kb blocks. We might use long long, but that would |
| 69 |
* kill us on x86. Oh, well, at least the sign propagation does not matter - |
| 70 |
* i_block would have to be negative in the very beginning, so we would not |
| 71 |
* get there at all. |
| 72 |
*/ |
| 73 |
|
| 74 |
static int ext4_block_to_path(struct inode *inode, |
| 75 |
ext4_lblk_t i_block, |
| 76 |
ext4_lblk_t offsets[4], int *boundary) |
| 77 |
{ |
| 78 |
int ptrs = EXT4_ADDR_PER_BLOCK(inode->i_sb); |
| 79 |
int ptrs_bits = EXT4_ADDR_PER_BLOCK_BITS(inode->i_sb); |
| 80 |
const long direct_blocks = EXT4_NDIR_BLOCKS, |
| 81 |
indirect_blocks = ptrs, |
| 82 |
double_blocks = (1 << (ptrs_bits * 2)); |
| 83 |
int n = 0; |
| 84 |
int final = 0; |
| 85 |
|
| 86 |
if (i_block < direct_blocks) { |
| 87 |
offsets[n++] = i_block; |
| 88 |
final = direct_blocks; |
| 89 |
} else if ((i_block -= direct_blocks) < indirect_blocks) { |
| 90 |
offsets[n++] = EXT4_IND_BLOCK; |
| 91 |
offsets[n++] = i_block; |
| 92 |
final = ptrs; |
| 93 |
} else if ((i_block -= indirect_blocks) < double_blocks) { |
| 94 |
offsets[n++] = EXT4_DIND_BLOCK; |
| 95 |
offsets[n++] = i_block >> ptrs_bits; |
| 96 |
offsets[n++] = i_block & (ptrs - 1); |
| 97 |
final = ptrs; |
| 98 |
} else if (((i_block -= double_blocks) >> (ptrs_bits * 2)) < ptrs) { |
| 99 |
offsets[n++] = EXT4_TIND_BLOCK; |
| 100 |
offsets[n++] = i_block >> (ptrs_bits * 2); |
| 101 |
offsets[n++] = (i_block >> ptrs_bits) & (ptrs - 1); |
| 102 |
offsets[n++] = i_block & (ptrs - 1); |
| 103 |
final = ptrs; |
| 104 |
} else { |
| 105 |
ext4_warning(inode->i_sb, "block %lu > max in inode %lu", |
| 106 |
i_block + direct_blocks + |
| 107 |
indirect_blocks + double_blocks, inode->i_ino); |
| 108 |
} |
| 109 |
if (boundary) |
| 110 |
*boundary = final - 1 - (i_block & (ptrs - 1)); |
| 111 |
return n; |
| 112 |
} |
| 113 |
|
| 114 |
/** |
| 115 |
* ext4_get_branch - read the chain of indirect blocks leading to data |
| 116 |
* @inode: inode in question |
| 117 |
* @depth: depth of the chain (1 - direct pointer, etc.) |
| 118 |
* @offsets: offsets of pointers in inode/indirect blocks |
| 119 |
* @chain: place to store the result |
| 120 |
* @err: here we store the error value |
| 121 |
* |
| 122 |
* Function fills the array of triples <key, p, bh> and returns %NULL |
| 123 |
* if everything went OK or the pointer to the last filled triple |
| 124 |
* (incomplete one) otherwise. Upon the return chain[i].key contains |
| 125 |
* the number of (i+1)-th block in the chain (as it is stored in memory, |
| 126 |
* i.e. little-endian 32-bit), chain[i].p contains the address of that |
| 127 |
* number (it points into struct inode for i==0 and into the bh->b_data |
| 128 |
* for i>0) and chain[i].bh points to the buffer_head of i-th indirect |
| 129 |
* block for i>0 and NULL for i==0. In other words, it holds the block |
| 130 |
* numbers of the chain, addresses they were taken from (and where we can |
| 131 |
* verify that chain did not change) and buffer_heads hosting these |
| 132 |
* numbers. |
| 133 |
* |
| 134 |
* Function stops when it stumbles upon zero pointer (absent block) |
| 135 |
* (pointer to last triple returned, *@err == 0) |
| 136 |
* or when it gets an IO error reading an indirect block |
| 137 |
* (ditto, *@err == -EIO) |
| 138 |
* or when it reads all @depth-1 indirect blocks successfully and finds |
| 139 |
* the whole chain, all way to the data (returns %NULL, *err == 0). |
| 140 |
* |
| 141 |
* Need to be called with |
| 142 |
* down_read(&EXT4_I(inode)->i_data_sem) |
| 143 |
*/ |
| 144 |
static Indirect *ext4_get_branch(struct inode *inode, int depth, |
| 145 |
ext4_lblk_t *offsets, |
| 146 |
Indirect chain[4], int *err) |
| 147 |
{ |
| 148 |
struct super_block *sb = inode->i_sb; |
| 149 |
Indirect *p = chain; |
| 150 |
struct buffer_head *bh; |
| 151 |
unsigned int key; |
| 152 |
int ret = -EIO; |
| 153 |
|
| 154 |
*err = 0; |
| 155 |
/* i_data is not going away, no lock needed */ |
| 156 |
add_chain(chain, NULL, EXT4_I(inode)->i_data + *offsets); |
| 157 |
if (!p->key) |
| 158 |
goto no_block; |
| 159 |
while (--depth) { |
| 160 |
key = le32_to_cpu(p->key); |
| 161 |
if (key > ext4_blocks_count(EXT4_SB(sb)->s_es)) { |
| 162 |
/* the block was out of range */ |
| 163 |
ret = -EFSCORRUPTED; |
| 164 |
goto failure; |
| 165 |
} |
| 166 |
bh = sb_getblk(sb, key); |
| 167 |
if (unlikely(!bh)) { |
| 168 |
ret = -ENOMEM; |
| 169 |
goto failure; |
| 170 |
} |
| 171 |
|
| 172 |
if (!bh_uptodate_or_lock(bh)) { |
| 173 |
if (ext4_read_bh(bh, 0, NULL, false) < 0) { |
| 174 |
put_bh(bh); |
| 175 |
goto failure; |
| 176 |
} |
| 177 |
/* validate block references */ |
| 178 |
if (ext4_check_indirect_blockref(inode, bh)) { |
| 179 |
put_bh(bh); |
| 180 |
goto failure; |
| 181 |
} |
| 182 |
} |
| 183 |
|
| 184 |
add_chain(++p, bh, (__le32 *)bh->b_data + *++offsets); |
| 185 |
/* Reader: end */ |
| 186 |
if (!p->key) |
| 187 |
goto no_block; |
| 188 |
} |
| 189 |
return NULL; |
| 190 |
|
| 191 |
failure: |
| 192 |
*err = ret; |
| 193 |
no_block: |
| 194 |
return p; |
| 195 |
} |
| 196 |
|
| 197 |
/** |
| 198 |
* ext4_find_near - find a place for allocation with sufficient locality |
| 199 |
* @inode: owner |
| 200 |
* @ind: descriptor of indirect block. |
| 201 |
* |
| 202 |
* This function returns the preferred place for block allocation. |
| 203 |
* It is used when heuristic for sequential allocation fails. |
| 204 |
* Rules are: |
| 205 |
* + if there is a block to the left of our position - allocate near it. |
| 206 |
* + if pointer will live in indirect block - allocate near that block. |
| 207 |
* + if pointer will live in inode - allocate in the same |
| 208 |
* cylinder group. |
| 209 |
* |
| 210 |
* In the latter case we colour the starting block by the callers PID to |
| 211 |
* prevent it from clashing with concurrent allocations for a different inode |
| 212 |
* in the same block group. The PID is used here so that functionally related |
| 213 |
* files will be close-by on-disk. |
| 214 |
* |
| 215 |
* Caller must make sure that @ind is valid and will stay that way. |
| 216 |
*/ |
| 217 |
static ext4_fsblk_t ext4_find_near(struct inode *inode, Indirect *ind) |
| 218 |
{ |
| 219 |
struct ext4_inode_info *ei = EXT4_I(inode); |
| 220 |
__le32 *start = ind->bh ? (__le32 *) ind->bh->b_data : ei->i_data; |
| 221 |
__le32 *p; |
| 222 |
|
| 223 |
/* Try to find previous block */ |
| 224 |
for (p = ind->p - 1; p >= start; p--) { |
| 225 |
if (*p) |
| 226 |
return le32_to_cpu(*p); |
| 227 |
} |
| 228 |
|
| 229 |
/* No such thing, so let's try location of indirect block */ |
| 230 |
if (ind->bh) |
| 231 |
return ind->bh->b_blocknr; |
| 232 |
|
| 233 |
/* |
| 234 |
* It is going to be referred to from the inode itself? OK, just put it |
| 235 |
* into the same cylinder group then. |
| 236 |
*/ |
| 237 |
return ext4_inode_to_goal_block(inode); |
| 238 |
} |
| 239 |
|
| 240 |
/** |
| 241 |
* ext4_find_goal - find a preferred place for allocation. |
| 242 |
* @inode: owner |
| 243 |
* @block: block we want |
| 244 |
* @partial: pointer to the last triple within a chain |
| 245 |
* |
| 246 |
* Normally this function find the preferred place for block allocation, |
| 247 |
* returns it. |
| 248 |
* Because this is only used for non-extent files, we limit the block nr |
| 249 |
* to 32 bits. |
| 250 |
*/ |
| 251 |
static ext4_fsblk_t ext4_find_goal(struct inode *inode, ext4_lblk_t block, |
| 252 |
Indirect *partial) |
| 253 |
{ |
| 254 |
ext4_fsblk_t goal; |
| 255 |
|
| 256 |
/* |
| 257 |
* XXX need to get goal block from mballoc's data structures |
| 258 |
*/ |
| 259 |
|
| 260 |
goal = ext4_find_near(inode, partial); |
| 261 |
goal = goal & EXT4_MAX_BLOCK_FILE_PHYS; |
| 262 |
return goal; |
| 263 |
} |
| 264 |
|
| 265 |
/** |
| 266 |
* ext4_blks_to_allocate - Look up the block map and count the number |
| 267 |
* of direct blocks need to be allocated for the given branch. |
| 268 |
* |
| 269 |
* @branch: chain of indirect blocks |
| 270 |
* @k: number of blocks need for indirect blocks |
| 271 |
* @blks: number of data blocks to be mapped. |
| 272 |
* @blocks_to_boundary: the offset in the indirect block |
| 273 |
* |
| 274 |
* return the total number of blocks to be allocate, including the |
| 275 |
* direct and indirect blocks. |
| 276 |
*/ |
| 277 |
static int ext4_blks_to_allocate(Indirect *branch, int k, unsigned int blks, |
| 278 |
int blocks_to_boundary) |
| 279 |
{ |
| 280 |
unsigned int count = 0; |
| 281 |
|
| 282 |
/* |
| 283 |
* Simple case, [t,d]Indirect block(s) has not allocated yet |
| 284 |
* then it's clear blocks on that path have not allocated |
| 285 |
*/ |
| 286 |
if (k > 0) { |
| 287 |
/* right now we don't handle cross boundary allocation */ |
| 288 |
if (blks < blocks_to_boundary + 1) |
| 289 |
count += blks; |
| 290 |
else |
| 291 |
count += blocks_to_boundary + 1; |
| 292 |
return count; |
| 293 |
} |
| 294 |
|
| 295 |
count++; |
| 296 |
while (count < blks && count <= blocks_to_boundary && |
| 297 |
le32_to_cpu(*(branch[0].p + count)) == 0) { |
| 298 |
count++; |
| 299 |
} |
| 300 |
return count; |
| 301 |
} |
| 302 |
|
| 303 |
/** |
| 304 |
* ext4_alloc_branch() - allocate and set up a chain of blocks |
| 305 |
* @handle: handle for this transaction |
| 306 |
* @ar: structure describing the allocation request |
| 307 |
* @indirect_blks: number of allocated indirect blocks |
| 308 |
* @offsets: offsets (in the blocks) to store the pointers to next. |
| 309 |
* @branch: place to store the chain in. |
| 310 |
* |
| 311 |
* This function allocates blocks, zeroes out all but the last one, |
| 312 |
* links them into chain and (if we are synchronous) writes them to disk. |
| 313 |
* In other words, it prepares a branch that can be spliced onto the |
| 314 |
* inode. It stores the information about that chain in the branch[], in |
| 315 |
* the same format as ext4_get_branch() would do. We are calling it after |
| 316 |
* we had read the existing part of chain and partial points to the last |
| 317 |
* triple of that (one with zero ->key). Upon the exit we have the same |
| 318 |
* picture as after the successful ext4_get_block(), except that in one |
| 319 |
* place chain is disconnected - *branch->p is still zero (we did not |
| 320 |
* set the last link), but branch->key contains the number that should |
| 321 |
* be placed into *branch->p to fill that gap. |
| 322 |
* |
| 323 |
* If allocation fails we free all blocks we've allocated (and forget |
| 324 |
* their buffer_heads) and return the error value the from failed |
| 325 |
* ext4_alloc_block() (normally -ENOSPC). Otherwise we set the chain |
| 326 |
* as described above and return 0. |
| 327 |
*/ |
| 328 |
static int ext4_alloc_branch(handle_t *handle, |
| 329 |
struct ext4_allocation_request *ar, |
| 330 |
int indirect_blks, ext4_lblk_t *offsets, |
| 331 |
Indirect *branch) |
| 332 |
{ |
| 333 |
struct buffer_head * bh; |
| 334 |
ext4_fsblk_t b, new_blocks[4]; |
| 335 |
__le32 *p; |
| 336 |
int i, j, err, len = 1; |
| 337 |
|
| 338 |
for (i = 0; i <= indirect_blks; i++) { |
| 339 |
if (i == indirect_blks) { |
| 340 |
new_blocks[i] = ext4_mb_new_blocks(handle, ar, &err); |
| 341 |
} else { |
| 342 |
ar->goal = new_blocks[i] = ext4_new_meta_blocks(handle, |
| 343 |
ar->inode, ar->goal, |
| 344 |
ar->flags & EXT4_MB_DELALLOC_RESERVED, |
| 345 |
NULL, &err); |
| 346 |
/* Simplify error cleanup... */ |
| 347 |
branch[i+1].bh = NULL; |
| 348 |
} |
| 349 |
if (err) { |
| 350 |
i--; |
| 351 |
goto failed; |
| 352 |
} |
| 353 |
branch[i].key = cpu_to_le32(new_blocks[i]); |
| 354 |
if (i == 0) |
| 355 |
continue; |
| 356 |
|
| 357 |
bh = branch[i].bh = sb_getblk(ar->inode->i_sb, new_blocks[i-1]); |
| 358 |
if (unlikely(!bh)) { |
| 359 |
err = -ENOMEM; |
| 360 |
goto failed; |
| 361 |
} |
| 362 |
lock_buffer(bh); |
| 363 |
BUFFER_TRACE(bh, "call get_create_access"); |
| 364 |
err = ext4_journal_get_create_access(handle, ar->inode->i_sb, |
| 365 |
bh, EXT4_JTR_NONE); |
| 366 |
if (err) { |
| 367 |
unlock_buffer(bh); |
| 368 |
goto failed; |
| 369 |
} |
| 370 |
|
| 371 |
memset(bh->b_data, 0, bh->b_size); |
| 372 |
p = branch[i].p = (__le32 *) bh->b_data + offsets[i]; |
| 373 |
b = new_blocks[i]; |
| 374 |
|
| 375 |
if (i == indirect_blks) |
| 376 |
len = ar->len; |
| 377 |
for (j = 0; j < len; j++) |
| 378 |
*p++ = cpu_to_le32(b++); |
| 379 |
|
| 380 |
BUFFER_TRACE(bh, "marking uptodate"); |
| 381 |
set_buffer_uptodate(bh); |
| 382 |
unlock_buffer(bh); |
| 383 |
|
| 384 |
BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata"); |
| 385 |
err = ext4_handle_dirty_metadata(handle, ar->inode, bh); |
| 386 |
if (err) |
| 387 |
goto failed; |
| 388 |
} |
| 389 |
return 0; |
| 390 |
failed: |
| 391 |
if (i == indirect_blks) { |
| 392 |
/* Free data blocks */ |
| 393 |
ext4_free_blocks(handle, ar->inode, NULL, new_blocks[i], |
| 394 |
ar->len, 0); |
| 395 |
i--; |
| 396 |
} |
| 397 |
for (; i >= 0; i--) { |
| 398 |
/* |
| 399 |
* We want to ext4_forget() only freshly allocated indirect |
| 400 |
* blocks. Buffer for new_blocks[i] is at branch[i+1].bh |
| 401 |
* (buffer at branch[0].bh is indirect block / inode already |
| 402 |
* existing before ext4_alloc_branch() was called). Also |
| 403 |
* because blocks are freshly allocated, we don't need to |
| 404 |
* revoke them which is why we don't set |
| 405 |
* EXT4_FREE_BLOCKS_METADATA. |
| 406 |
*/ |
| 407 |
ext4_free_blocks(handle, ar->inode, branch[i+1].bh, |
| 408 |
new_blocks[i], 1, |
| 409 |
branch[i+1].bh ? EXT4_FREE_BLOCKS_FORGET : 0); |
| 410 |
} |
| 411 |
return err; |
| 412 |
} |
| 413 |
|
| 414 |
/** |
| 415 |
* ext4_splice_branch() - splice the allocated branch onto inode. |
| 416 |
* @handle: handle for this transaction |
| 417 |
* @ar: structure describing the allocation request |
| 418 |
* @where: location of missing link |
| 419 |
* @num: number of indirect blocks we are adding |
| 420 |
* |
| 421 |
* This function fills the missing link and does all housekeeping needed in |
| 422 |
* inode (->i_blocks, etc.). In case of success we end up with the full |
| 423 |
* chain to new block and return 0. |
| 424 |
*/ |
| 425 |
static int ext4_splice_branch(handle_t *handle, |
| 426 |
struct ext4_allocation_request *ar, |
| 427 |
Indirect *where, int num) |
| 428 |
{ |
| 429 |
int i; |
| 430 |
int err = 0; |
| 431 |
ext4_fsblk_t current_block; |
| 432 |
|
| 433 |
/* |
| 434 |
* If we're splicing into a [td]indirect block (as opposed to the |
| 435 |
* inode) then we need to get write access to the [td]indirect block |
| 436 |
* before the splice. |
| 437 |
*/ |
| 438 |
if (where->bh) { |
| 439 |
BUFFER_TRACE(where->bh, "get_write_access"); |
| 440 |
err = ext4_journal_get_write_access(handle, ar->inode->i_sb, |
| 441 |
where->bh, EXT4_JTR_NONE); |
| 442 |
if (err) |
| 443 |
goto err_out; |
| 444 |
} |
| 445 |
/* That's it */ |
| 446 |
|
| 447 |
*where->p = where->key; |
| 448 |
|
| 449 |
/* |
| 450 |
* Update the host buffer_head or inode to point to more just allocated |
| 451 |
* direct blocks blocks |
| 452 |
*/ |
| 453 |
if (num == 0 && ar->len > 1) { |
| 454 |
current_block = le32_to_cpu(where->key) + 1; |
| 455 |
for (i = 1; i < ar->len; i++) |
| 456 |
*(where->p + i) = cpu_to_le32(current_block++); |
| 457 |
} |
| 458 |
|
| 459 |
/* We are done with atomic stuff, now do the rest of housekeeping */ |
| 460 |
/* had we spliced it onto indirect block? */ |
| 461 |
if (where->bh) { |
| 462 |
/* |
| 463 |
* If we spliced it onto an indirect block, we haven't |
| 464 |
* altered the inode. Note however that if it is being spliced |
| 465 |
* onto an indirect block at the very end of the file (the |
| 466 |
* file is growing) then we *will* alter the inode to reflect |
| 467 |
* the new i_size. But that is not done here - it is done in |
| 468 |
* generic_commit_write->__mark_inode_dirty->ext4_dirty_inode. |
| 469 |
*/ |
| 470 |
ext4_debug("splicing indirect only\n"); |
| 471 |
BUFFER_TRACE(where->bh, "call ext4_handle_dirty_metadata"); |
| 472 |
err = ext4_handle_dirty_metadata(handle, ar->inode, where->bh); |
| 473 |
if (err) |
| 474 |
goto err_out; |
| 475 |
} else { |
| 476 |
/* |
| 477 |
* OK, we spliced it into the inode itself on a direct block. |
| 478 |
*/ |
| 479 |
err = ext4_mark_inode_dirty(handle, ar->inode); |
| 480 |
if (unlikely(err)) |
| 481 |
goto err_out; |
| 482 |
ext4_debug("splicing direct\n"); |
| 483 |
} |
| 484 |
return err; |
| 485 |
|
| 486 |
err_out: |
| 487 |
for (i = 1; i <= num; i++) { |
| 488 |
/* |
| 489 |
* branch[i].bh is newly allocated, so there is no |
| 490 |
* need to revoke the block, which is why we don't |
| 491 |
* need to set EXT4_FREE_BLOCKS_METADATA. |
| 492 |
*/ |
| 493 |
ext4_free_blocks(handle, ar->inode, where[i].bh, 0, 1, |
| 494 |
EXT4_FREE_BLOCKS_FORGET); |
| 495 |
} |
| 496 |
ext4_free_blocks(handle, ar->inode, NULL, le32_to_cpu(where[num].key), |
| 497 |
ar->len, 0); |
| 498 |
|
| 499 |
return err; |
| 500 |
} |
| 501 |
|
| 502 |
/* |
| 503 |
* The ext4_ind_map_blocks() function handles non-extents inodes |
| 504 |
* (i.e., using the traditional indirect/double-indirect i_blocks |
| 505 |
* scheme) for ext4_map_blocks(). |
| 506 |
* |
| 507 |
* Allocation strategy is simple: if we have to allocate something, we will |
| 508 |
* have to go the whole way to leaf. So let's do it before attaching anything |
| 509 |
* to tree, set linkage between the newborn blocks, write them if sync is |
| 510 |
* required, recheck the path, free and repeat if check fails, otherwise |
| 511 |
* set the last missing link (that will protect us from any truncate-generated |
| 512 |
* removals - all blocks on the path are immune now) and possibly force the |
| 513 |
* write on the parent block. |
| 514 |
* That has a nice additional property: no special recovery from the failed |
| 515 |
* allocations is needed - we simply release blocks and do not touch anything |
| 516 |
* reachable from inode. |
| 517 |
* |
| 518 |
* `handle' can be NULL if create == 0. |
| 519 |
* |
| 520 |
* return > 0, # of blocks mapped or allocated. |
| 521 |
* return = 0, if plain lookup failed. |
| 522 |
* return < 0, error case. |
| 523 |
* |
| 524 |
* The ext4_ind_get_blocks() function should be called with |
| 525 |
* down_write(&EXT4_I(inode)->i_data_sem) if allocating filesystem |
| 526 |
* blocks (i.e., flags has EXT4_GET_BLOCKS_CREATE set) or |
| 527 |
* down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system |
| 528 |
* blocks. |
| 529 |
*/ |
| 530 |
int ext4_ind_map_blocks(handle_t *handle, struct inode *inode, |
| 531 |
struct ext4_map_blocks *map, |
| 532 |
int flags) |
| 533 |
{ |
| 534 |
struct ext4_allocation_request ar; |
| 535 |
int err = -EIO; |
| 536 |
ext4_lblk_t offsets[4]; |
| 537 |
Indirect chain[4]; |
| 538 |
Indirect *partial; |
| 539 |
int indirect_blks; |
| 540 |
int blocks_to_boundary = 0; |
| 541 |
int depth; |
| 542 |
u64 count = 0; |
| 543 |
ext4_fsblk_t first_block = 0; |
| 544 |
|
| 545 |
trace_ext4_ind_map_blocks_enter(inode, map->m_lblk, map->m_len, flags); |
| 546 |
ASSERT(!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))); |
| 547 |
ASSERT(handle != NULL || (flags & EXT4_GET_BLOCKS_CREATE) == 0); |
| 548 |
depth = ext4_block_to_path(inode, map->m_lblk, offsets, |
| 549 |
&blocks_to_boundary); |
| 550 |
|
| 551 |
if (depth == 0) |
| 552 |
goto out; |
| 553 |
|
| 554 |
partial = ext4_get_branch(inode, depth, offsets, chain, &err); |
| 555 |
|
| 556 |
/* Simplest case - block found, no allocation needed */ |
| 557 |
if (!partial) { |
| 558 |
first_block = le32_to_cpu(chain[depth - 1].key); |
| 559 |
count++; |
| 560 |
/*map more blocks*/ |
| 561 |
while (count < map->m_len && count <= blocks_to_boundary) { |
| 562 |
ext4_fsblk_t blk; |
| 563 |
|
| 564 |
blk = le32_to_cpu(*(chain[depth-1].p + count)); |
| 565 |
|
| 566 |
if (blk == first_block + count) |
| 567 |
count++; |
| 568 |
else |
| 569 |
break; |
| 570 |
} |
| 571 |
goto got_it; |
| 572 |
} |
| 573 |
|
| 574 |
/* Next simple case - plain lookup failed */ |
| 575 |
if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) { |
| 576 |
unsigned epb = inode->i_sb->s_blocksize / sizeof(u32); |
| 577 |
int i; |
| 578 |
|
| 579 |
/* |
| 580 |
* Count number blocks in a subtree under 'partial'. At each |
| 581 |
* level we count number of complete empty subtrees beyond |
| 582 |
* current offset and then descend into the subtree only |
| 583 |
* partially beyond current offset. |
| 584 |
*/ |
| 585 |
count = 0; |
| 586 |
for (i = partial - chain + 1; i < depth; i++) |
| 587 |
count = count * epb + (epb - offsets[i] - 1); |
| 588 |
count++; |
| 589 |
/* Fill in size of a hole we found */ |
| 590 |
map->m_pblk = 0; |
| 591 |
map->m_len = umin(map->m_len, count); |
| 592 |
goto cleanup; |
| 593 |
} |
| 594 |
|
| 595 |
/* Failed read of indirect block */ |
| 596 |
if (err == -EIO) |
| 597 |
goto cleanup; |
| 598 |
|
| 599 |
/* |
| 600 |
* Okay, we need to do block allocation. |
| 601 |
*/ |
| 602 |
if (ext4_has_feature_bigalloc(inode->i_sb)) { |
| 603 |
EXT4_ERROR_INODE(inode, "Can't allocate blocks for " |
| 604 |
"non-extent mapped inodes with bigalloc"); |
| 605 |
err = -EFSCORRUPTED; |
| 606 |
goto out; |
| 607 |
} |
| 608 |
|
| 609 |
/* Set up for the direct block allocation */ |
| 610 |
memset(&ar, 0, sizeof(ar)); |
| 611 |
ar.inode = inode; |
| 612 |
ar.logical = map->m_lblk; |
| 613 |
if (S_ISREG(inode->i_mode)) |
| 614 |
ar.flags = EXT4_MB_HINT_DATA; |
| 615 |
if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) |
| 616 |
ar.flags |= EXT4_MB_DELALLOC_RESERVED; |
| 617 |
if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL) |
| 618 |
ar.flags |= EXT4_MB_USE_RESERVED; |
| 619 |
|
| 620 |
ar.goal = ext4_find_goal(inode, map->m_lblk, partial); |
| 621 |
|
| 622 |
/* the number of blocks need to allocate for [d,t]indirect blocks */ |
| 623 |
indirect_blks = (chain + depth) - partial - 1; |
| 624 |
|
| 625 |
/* |
| 626 |
* Next look up the indirect map to count the totoal number of |
| 627 |
* direct blocks to allocate for this branch. |
| 628 |
*/ |
| 629 |
ar.len = ext4_blks_to_allocate(partial, indirect_blks, |
| 630 |
map->m_len, blocks_to_boundary); |
| 631 |
|
| 632 |
/* |
| 633 |
* Block out ext4_truncate while we alter the tree |
| 634 |
*/ |
| 635 |
err = ext4_alloc_branch(handle, &ar, indirect_blks, |
| 636 |
offsets + (partial - chain), partial); |
| 637 |
|
| 638 |
/* |
| 639 |
* The ext4_splice_branch call will free and forget any buffers |
| 640 |
* on the new chain if there is a failure, but that risks using |
| 641 |
* up transaction credits, especially for bitmaps where the |
| 642 |
* credits cannot be returned. Can we handle this somehow? We |
| 643 |
* may need to return -EAGAIN upwards in the worst case. --sct |
| 644 |
*/ |
| 645 |
if (!err) |
| 646 |
err = ext4_splice_branch(handle, &ar, partial, indirect_blks); |
| 647 |
if (err) |
| 648 |
goto cleanup; |
| 649 |
|
| 650 |
map->m_flags |= EXT4_MAP_NEW; |
| 651 |
|
| 652 |
ext4_update_inode_fsync_trans(handle, inode, 1); |
| 653 |
count = ar.len; |
| 654 |
|
| 655 |
got_it: |
| 656 |
map->m_flags |= EXT4_MAP_MAPPED; |
| 657 |
map->m_pblk = le32_to_cpu(chain[depth-1].key); |
| 658 |
map->m_len = count; |
| 659 |
if (count > blocks_to_boundary) |
| 660 |
map->m_flags |= EXT4_MAP_BOUNDARY; |
| 661 |
err = count; |
| 662 |
/* Clean up and exit */ |
| 663 |
partial = chain + depth - 1; /* the whole chain */ |
| 664 |
cleanup: |
| 665 |
while (partial > chain) { |
| 666 |
BUFFER_TRACE(partial->bh, "call brelse"); |
| 667 |
brelse(partial->bh); |
| 668 |
partial--; |
| 669 |
} |
| 670 |
out: |
| 671 |
trace_ext4_ind_map_blocks_exit(inode, flags, map, err); |
| 672 |
return err; |
| 673 |
} |
| 674 |
|
| 675 |
/* |
| 676 |
* Calculate number of indirect blocks touched by mapping @nrblocks logically |
| 677 |
* contiguous blocks |
| 678 |
*/ |
| 679 |
int ext4_ind_trans_blocks(struct inode *inode, int nrblocks) |
| 680 |
{ |
| 681 |
/* |
| 682 |
* With N contiguous data blocks, we need at most |
| 683 |
* N/EXT4_ADDR_PER_BLOCK(inode->i_sb) + 1 indirect blocks, |
| 684 |
* 2 dindirect blocks, and 1 tindirect block |
| 685 |
*/ |
| 686 |
return DIV_ROUND_UP(nrblocks, EXT4_ADDR_PER_BLOCK(inode->i_sb)) + 4; |
| 687 |
} |
| 688 |
|
| 689 |
static int ext4_ind_trunc_restart_fn(handle_t *handle, struct inode *inode, |
| 690 |
struct buffer_head *bh, int *dropped) |
| 691 |
{ |
| 692 |
int err; |
| 693 |
|
| 694 |
if (bh) { |
| 695 |
BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata"); |
| 696 |
err = ext4_handle_dirty_metadata(handle, inode, bh); |
| 697 |
if (unlikely(err)) |
| 698 |
return err; |
| 699 |
} |
| 700 |
err = ext4_mark_inode_dirty(handle, inode); |
| 701 |
if (unlikely(err)) |
| 702 |
return err; |
| 703 |
/* |
| 704 |
* Drop i_data_sem to avoid deadlock with ext4_map_blocks. At this |
| 705 |
* moment, get_block can be called only for blocks inside i_size since |
| 706 |
* page cache has been already dropped and writes are blocked by |
| 707 |
* i_rwsem. So we can safely drop the i_data_sem here. |
| 708 |
*/ |
| 709 |
BUG_ON(EXT4_JOURNAL(inode) == NULL); |
| 710 |
ext4_discard_preallocations(inode); |
| 711 |
up_write(&EXT4_I(inode)->i_data_sem); |
| 712 |
*dropped = 1; |
| 713 |
return 0; |
| 714 |
} |
| 715 |
|
| 716 |
/* |
| 717 |
* Truncate transactions can be complex and absolutely huge. So we need to |
| 718 |
* be able to restart the transaction at a convenient checkpoint to make |
| 719 |
* sure we don't overflow the journal. |
| 720 |
* |
| 721 |
* Try to extend this transaction for the purposes of truncation. If |
| 722 |
* extend fails, we restart transaction. |
| 723 |
*/ |
| 724 |
static int ext4_ind_truncate_ensure_credits(handle_t *handle, |
| 725 |
struct inode *inode, |
| 726 |
struct buffer_head *bh, |
| 727 |
int revoke_creds) |
| 728 |
{ |
| 729 |
int ret; |
| 730 |
int dropped = 0; |
| 731 |
|
| 732 |
ret = ext4_journal_ensure_credits_fn(handle, EXT4_RESERVE_TRANS_BLOCKS, |
| 733 |
ext4_blocks_for_truncate(inode), revoke_creds, |
| 734 |
ext4_ind_trunc_restart_fn(handle, inode, bh, &dropped)); |
| 735 |
if (dropped) |
| 736 |
down_write(&EXT4_I(inode)->i_data_sem); |
| 737 |
if (ret <= 0) |
| 738 |
return ret; |
| 739 |
if (bh) { |
| 740 |
BUFFER_TRACE(bh, "retaking write access"); |
| 741 |
ret = ext4_journal_get_write_access(handle, inode->i_sb, bh, |
| 742 |
EXT4_JTR_NONE); |
| 743 |
if (unlikely(ret)) |
| 744 |
return ret; |
| 745 |
} |
| 746 |
return 0; |
| 747 |
} |
| 748 |
|
| 749 |
/* |
| 750 |
* Probably it should be a library function... search for first non-zero word |
| 751 |
* or memcmp with zero_page, whatever is better for particular architecture. |
| 752 |
* Linus? |
| 753 |
*/ |
| 754 |
static inline int all_zeroes(__le32 *p, __le32 *q) |
| 755 |
{ |
| 756 |
while (p < q) |
| 757 |
if (*p++) |
| 758 |
return 0; |
| 759 |
return 1; |
| 760 |
} |
| 761 |
|
| 762 |
/** |
| 763 |
* ext4_find_shared - find the indirect blocks for partial truncation. |
| 764 |
* @inode: inode in question |
| 765 |
* @depth: depth of the affected branch |
| 766 |
* @offsets: offsets of pointers in that branch (see ext4_block_to_path) |
| 767 |
* @chain: place to store the pointers to partial indirect blocks |
| 768 |
* @top: place to the (detached) top of branch |
| 769 |
* |
| 770 |
* This is a helper function used by ext4_truncate(). |
| 771 |
* |
| 772 |
* When we do truncate() we may have to clean the ends of several |
| 773 |
* indirect blocks but leave the blocks themselves alive. Block is |
| 774 |
* partially truncated if some data below the new i_size is referred |
| 775 |
* from it (and it is on the path to the first completely truncated |
| 776 |
* data block, indeed). We have to free the top of that path along |
| 777 |
* with everything to the right of the path. Since no allocation |
| 778 |
* past the truncation point is possible until ext4_truncate() |
| 779 |
* finishes, we may safely do the latter, but top of branch may |
| 780 |
* require special attention - pageout below the truncation point |
| 781 |
* might try to populate it. |
| 782 |
* |
| 783 |
* We atomically detach the top of branch from the tree, store the |
| 784 |
* block number of its root in *@top, pointers to buffer_heads of |
| 785 |
* partially truncated blocks - in @chain[].bh and pointers to |
| 786 |
* their last elements that should not be removed - in |
| 787 |
* @chain[].p. Return value is the pointer to last filled element |
| 788 |
* of @chain. |
| 789 |
* |
| 790 |
* The work left to caller to do the actual freeing of subtrees: |
| 791 |
* a) free the subtree starting from *@top |
| 792 |
* b) free the subtrees whose roots are stored in |
| 793 |
* (@chain[i].p+1 .. end of @chain[i].bh->b_data) |
| 794 |
* c) free the subtrees growing from the inode past the @chain[0]. |
| 795 |
* (no partially truncated stuff there). */ |
| 796 |
|
| 797 |
static Indirect *ext4_find_shared(struct inode *inode, int depth, |
| 798 |
ext4_lblk_t offsets[4], Indirect chain[4], |
| 799 |
__le32 *top) |
| 800 |
{ |
| 801 |
Indirect *partial, *p; |
| 802 |
int k, err; |
| 803 |
|
| 804 |
*top = 0; |
| 805 |
/* Make k index the deepest non-null offset + 1 */ |
| 806 |
for (k = depth; k > 1 && !offsets[k-1]; k--) |
| 807 |
; |
| 808 |
partial = ext4_get_branch(inode, k, offsets, chain, &err); |
| 809 |
/* Writer: pointers */ |
| 810 |
if (!partial) |
| 811 |
partial = chain + k-1; |
| 812 |
/* |
| 813 |
* If the branch acquired continuation since we've looked at it - |
| 814 |
* fine, it should all survive and (new) top doesn't belong to us. |
| 815 |
*/ |
| 816 |
if (!partial->key && *partial->p) |
| 817 |
/* Writer: end */ |
| 818 |
goto no_top; |
| 819 |
for (p = partial; (p > chain) && all_zeroes((__le32 *) p->bh->b_data, p->p); p--) |
| 820 |
; |
| 821 |
/* |
| 822 |
* OK, we've found the last block that must survive. The rest of our |
| 823 |
* branch should be detached before unlocking. However, if that rest |
| 824 |
* of branch is all ours and does not grow immediately from the inode |
| 825 |
* it's easier to cheat and just decrement partial->p. |
| 826 |
*/ |
| 827 |
if (p == chain + k - 1 && p > chain) { |
| 828 |
p->p--; |
| 829 |
} else { |
| 830 |
*top = *p->p; |
| 831 |
/* Nope, don't do this in ext4. Must leave the tree intact */ |
| 832 |
#if 0 |
| 833 |
*p->p = 0; |
| 834 |
#endif |
| 835 |
} |
| 836 |
/* Writer: end */ |
| 837 |
|
| 838 |
while (partial > p) { |
| 839 |
brelse(partial->bh); |
| 840 |
partial--; |
| 841 |
} |
| 842 |
no_top: |
| 843 |
return partial; |
| 844 |
} |
| 845 |
|
| 846 |
/* |
| 847 |
* Zero a number of block pointers in either an inode or an indirect block. |
| 848 |
* If we restart the transaction we must again get write access to the |
| 849 |
* indirect block for further modification. |
| 850 |
* |
| 851 |
* We release `count' blocks on disk, but (last - first) may be greater |
| 852 |
* than `count' because there can be holes in there. |
| 853 |
* |
| 854 |
* Return 0 on success, 1 on invalid block range |
| 855 |
* and < 0 on fatal error. |
| 856 |
*/ |
| 857 |
static int ext4_clear_blocks(handle_t *handle, struct inode *inode, |
| 858 |
struct buffer_head *bh, |
| 859 |
ext4_fsblk_t block_to_free, |
| 860 |
unsigned long count, __le32 *first, |
| 861 |
__le32 *last) |
| 862 |
{ |
| 863 |
__le32 *p; |
| 864 |
int flags = EXT4_FREE_BLOCKS_VALIDATED; |
| 865 |
int err; |
| 866 |
|
| 867 |
if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) || |
| 868 |
ext4_test_inode_flag(inode, EXT4_INODE_EA_INODE)) |
| 869 |
flags |= EXT4_FREE_BLOCKS_FORGET | EXT4_FREE_BLOCKS_METADATA; |
| 870 |
else if (ext4_should_journal_data(inode)) |
| 871 |
flags |= EXT4_FREE_BLOCKS_FORGET; |
| 872 |
|
| 873 |
if (!ext4_inode_block_valid(inode, block_to_free, count)) { |
| 874 |
EXT4_ERROR_INODE(inode, "attempt to clear invalid " |
| 875 |
"blocks %llu len %lu", |
| 876 |
(unsigned long long) block_to_free, count); |
| 877 |
return 1; |
| 878 |
} |
| 879 |
|
| 880 |
err = ext4_ind_truncate_ensure_credits(handle, inode, bh, |
| 881 |
ext4_free_data_revoke_credits(inode, count)); |
| 882 |
if (err < 0) |
| 883 |
goto out_err; |
| 884 |
|
| 885 |
for (p = first; p < last; p++) |
| 886 |
*p = 0; |
| 887 |
|
| 888 |
ext4_free_blocks(handle, inode, NULL, block_to_free, count, flags); |
| 889 |
return 0; |
| 890 |
out_err: |
| 891 |
ext4_std_error(inode->i_sb, err); |
| 892 |
return err; |
| 893 |
} |
| 894 |
|
| 895 |
/** |
| 896 |
* ext4_free_data - free a list of data blocks |
| 897 |
* @handle: handle for this transaction |
| 898 |
* @inode: inode we are dealing with |
| 899 |
* @this_bh: indirect buffer_head which contains *@first and *@last |
| 900 |
* @first: array of block numbers |
| 901 |
* @last: points immediately past the end of array |
| 902 |
* |
| 903 |
* We are freeing all blocks referred from that array (numbers are stored as |
| 904 |
* little-endian 32-bit) and updating @inode->i_blocks appropriately. |
| 905 |
* |
| 906 |
* We accumulate contiguous runs of blocks to free. Conveniently, if these |
| 907 |
* blocks are contiguous then releasing them at one time will only affect one |
| 908 |
* or two bitmap blocks (+ group descriptor(s) and superblock) and we won't |
| 909 |
* actually use a lot of journal space. |
| 910 |
* |
| 911 |
* @this_bh will be %NULL if @first and @last point into the inode's direct |
| 912 |
* block pointers. |
| 913 |
*/ |
| 914 |
static void ext4_free_data(handle_t *handle, struct inode *inode, |
| 915 |
struct buffer_head *this_bh, |
| 916 |
__le32 *first, __le32 *last) |
| 917 |
{ |
| 918 |
ext4_fsblk_t block_to_free = 0; /* Starting block # of a run */ |
| 919 |
unsigned long count = 0; /* Number of blocks in the run */ |
| 920 |
__le32 *block_to_free_p = NULL; /* Pointer into inode/ind |
| 921 |
corresponding to |
| 922 |
block_to_free */ |
| 923 |
ext4_fsblk_t nr; /* Current block # */ |
| 924 |
__le32 *p; /* Pointer into inode/ind |
| 925 |
for current block */ |
| 926 |
int err = 0; |
| 927 |
|
| 928 |
if (this_bh) { /* For indirect block */ |
| 929 |
BUFFER_TRACE(this_bh, "get_write_access"); |
| 930 |
err = ext4_journal_get_write_access(handle, inode->i_sb, |
| 931 |
this_bh, EXT4_JTR_NONE); |
| 932 |
/* Important: if we can't update the indirect pointers |
| 933 |
* to the blocks, we can't free them. */ |
| 934 |
if (err) |
| 935 |
return; |
| 936 |
} |
| 937 |
|
| 938 |
for (p = first; p < last; p++) { |
| 939 |
nr = le32_to_cpu(*p); |
| 940 |
if (nr) { |
| 941 |
/* accumulate blocks to free if they're contiguous */ |
| 942 |
if (count == 0) { |
| 943 |
block_to_free = nr; |
| 944 |
block_to_free_p = p; |
| 945 |
count = 1; |
| 946 |
} else if (nr == block_to_free + count) { |
| 947 |
count++; |
| 948 |
} else { |
| 949 |
err = ext4_clear_blocks(handle, inode, this_bh, |
| 950 |
block_to_free, count, |
| 951 |
block_to_free_p, p); |
| 952 |
if (err) |
| 953 |
break; |
| 954 |
block_to_free = nr; |
| 955 |
block_to_free_p = p; |
| 956 |
count = 1; |
| 957 |
} |
| 958 |
} |
| 959 |
} |
| 960 |
|
| 961 |
if (!err && count > 0) |
| 962 |
err = ext4_clear_blocks(handle, inode, this_bh, block_to_free, |
| 963 |
count, block_to_free_p, p); |
| 964 |
if (err < 0) |
| 965 |
/* fatal error */ |
| 966 |
return; |
| 967 |
|
| 968 |
if (this_bh) { |
| 969 |
BUFFER_TRACE(this_bh, "call ext4_handle_dirty_metadata"); |
| 970 |
|
| 971 |
/* |
| 972 |
* The buffer head should have an attached journal head at this |
| 973 |
* point. However, if the data is corrupted and an indirect |
| 974 |
* block pointed to itself, it would have been detached when |
| 975 |
* the block was cleared. Check for this instead of OOPSing. |
| 976 |
*/ |
| 977 |
if ((EXT4_JOURNAL(inode) == NULL) || bh2jh(this_bh)) |
| 978 |
ext4_handle_dirty_metadata(handle, inode, this_bh); |
| 979 |
else |
| 980 |
EXT4_ERROR_INODE(inode, |
| 981 |
"circular indirect block detected at " |
| 982 |
"block %llu", |
| 983 |
(unsigned long long) this_bh->b_blocknr); |
| 984 |
} |
| 985 |
} |
| 986 |
|
| 987 |
/** |
| 988 |
* ext4_free_branches - free an array of branches |
| 989 |
* @handle: JBD handle for this transaction |
| 990 |
* @inode: inode we are dealing with |
| 991 |
* @parent_bh: the buffer_head which contains *@first and *@last |
| 992 |
* @first: array of block numbers |
| 993 |
* @last: pointer immediately past the end of array |
| 994 |
* @depth: depth of the branches to free |
| 995 |
* |
| 996 |
* We are freeing all blocks referred from these branches (numbers are |
| 997 |
* stored as little-endian 32-bit) and updating @inode->i_blocks |
| 998 |
* appropriately. |
| 999 |
*/ |
| 1000 |
static void ext4_free_branches(handle_t *handle, struct inode *inode, |
| 1001 |
struct buffer_head *parent_bh, |
| 1002 |
__le32 *first, __le32 *last, int depth) |
| 1003 |
{ |
| 1004 |
ext4_fsblk_t nr; |
| 1005 |
__le32 *p; |
| 1006 |
|
| 1007 |
if (ext4_handle_is_aborted(handle)) |
| 1008 |
return; |
| 1009 |
|
| 1010 |
if (depth--) { |
| 1011 |
struct buffer_head *bh; |
| 1012 |
int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); |
| 1013 |
p = last; |
| 1014 |
while (--p >= first) { |
| 1015 |
nr = le32_to_cpu(*p); |
| 1016 |
if (!nr) |
| 1017 |
continue; /* A hole */ |
| 1018 |
|
| 1019 |
if (!ext4_inode_block_valid(inode, nr, 1)) { |
| 1020 |
EXT4_ERROR_INODE(inode, |
| 1021 |
"invalid indirect mapped " |
| 1022 |
"block %lu (level %d)", |
| 1023 |
(unsigned long) nr, depth); |
| 1024 |
break; |
| 1025 |
} |
| 1026 |
|
| 1027 |
/* Go read the buffer for the next level down */ |
| 1028 |
bh = ext4_sb_bread_nofail(inode->i_sb, nr); |
| 1029 |
|
| 1030 |
/* |
| 1031 |
* A read failure? Report error and clear slot |
| 1032 |
* (should be rare). |
| 1033 |
*/ |
| 1034 |
if (IS_ERR(bh)) { |
| 1035 |
ext4_error_inode_block(inode, nr, -PTR_ERR(bh), |
| 1036 |
"Read failure"); |
| 1037 |
continue; |
| 1038 |
} |
| 1039 |
|
| 1040 |
/* This zaps the entire block. Bottom up. */ |
| 1041 |
BUFFER_TRACE(bh, "free child branches"); |
| 1042 |
ext4_free_branches(handle, inode, bh, |
| 1043 |
(__le32 *) bh->b_data, |
| 1044 |
(__le32 *) bh->b_data + addr_per_block, |
| 1045 |
depth); |
| 1046 |
brelse(bh); |
| 1047 |
|
| 1048 |
/* |
| 1049 |
* Everything below this pointer has been |
| 1050 |
* released. Now let this top-of-subtree go. |
| 1051 |
* |
| 1052 |
* We want the freeing of this indirect block to be |
| 1053 |
* atomic in the journal with the updating of the |
| 1054 |
* bitmap block which owns it. So make some room in |
| 1055 |
* the journal. |
| 1056 |
* |
| 1057 |
* We zero the parent pointer *after* freeing its |
| 1058 |
* pointee in the bitmaps, so if extend_transaction() |
| 1059 |
* for some reason fails to put the bitmap changes and |
| 1060 |
* the release into the same transaction, recovery |
| 1061 |
* will merely complain about releasing a free block, |
| 1062 |
* rather than leaking blocks. |
| 1063 |
*/ |
| 1064 |
if (ext4_handle_is_aborted(handle)) |
| 1065 |
return; |
| 1066 |
if (ext4_ind_truncate_ensure_credits(handle, inode, |
| 1067 |
NULL, |
| 1068 |
ext4_free_metadata_revoke_credits( |
| 1069 |
inode->i_sb, 1)) < 0) |
| 1070 |
return; |
| 1071 |
|
| 1072 |
/* |
| 1073 |
* The forget flag here is critical because if |
| 1074 |
* we are journaling (and not doing data |
| 1075 |
* journaling), we have to make sure a revoke |
| 1076 |
* record is written to prevent the journal |
| 1077 |
* replay from overwriting the (former) |
| 1078 |
* indirect block if it gets reallocated as a |
| 1079 |
* data block. This must happen in the same |
| 1080 |
* transaction where the data blocks are |
| 1081 |
* actually freed. |
| 1082 |
*/ |
| 1083 |
ext4_free_blocks(handle, inode, NULL, nr, 1, |
| 1084 |
EXT4_FREE_BLOCKS_METADATA| |
| 1085 |
EXT4_FREE_BLOCKS_FORGET); |
| 1086 |
|
| 1087 |
if (parent_bh) { |
| 1088 |
/* |
| 1089 |
* The block which we have just freed is |
| 1090 |
* pointed to by an indirect block: journal it |
| 1091 |
*/ |
| 1092 |
BUFFER_TRACE(parent_bh, "get_write_access"); |
| 1093 |
if (!ext4_journal_get_write_access(handle, |
| 1094 |
inode->i_sb, parent_bh, |
| 1095 |
EXT4_JTR_NONE)) { |
| 1096 |
*p = 0; |
| 1097 |
BUFFER_TRACE(parent_bh, |
| 1098 |
"call ext4_handle_dirty_metadata"); |
| 1099 |
ext4_handle_dirty_metadata(handle, |
| 1100 |
inode, |
| 1101 |
parent_bh); |
| 1102 |
} |
| 1103 |
} |
| 1104 |
} |
| 1105 |
} else { |
| 1106 |
/* We have reached the bottom of the tree. */ |
| 1107 |
BUFFER_TRACE(parent_bh, "free data blocks"); |
| 1108 |
ext4_free_data(handle, inode, parent_bh, first, last); |
| 1109 |
} |
| 1110 |
} |
| 1111 |
|
| 1112 |
void ext4_ind_truncate(handle_t *handle, struct inode *inode) |
| 1113 |
{ |
| 1114 |
struct ext4_inode_info *ei = EXT4_I(inode); |
| 1115 |
__le32 *i_data = ei->i_data; |
| 1116 |
int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); |
| 1117 |
ext4_lblk_t offsets[4]; |
| 1118 |
Indirect chain[4]; |
| 1119 |
Indirect *partial; |
| 1120 |
__le32 nr = 0; |
| 1121 |
int n = 0; |
| 1122 |
ext4_lblk_t last_block, max_block; |
| 1123 |
unsigned blocksize = inode->i_sb->s_blocksize; |
| 1124 |
|
| 1125 |
last_block = (inode->i_size + blocksize-1) |
| 1126 |
>> EXT4_BLOCK_SIZE_BITS(inode->i_sb); |
| 1127 |
max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1) |
| 1128 |
>> EXT4_BLOCK_SIZE_BITS(inode->i_sb); |
| 1129 |
|
| 1130 |
if (last_block != max_block) { |
| 1131 |
n = ext4_block_to_path(inode, last_block, offsets, NULL); |
| 1132 |
if (n == 0) |
| 1133 |
return; |
| 1134 |
} |
| 1135 |
|
| 1136 |
ext4_es_remove_extent(inode, last_block, EXT_MAX_BLOCKS - last_block); |
| 1137 |
|
| 1138 |
/* |
| 1139 |
* The orphan list entry will now protect us from any crash which |
| 1140 |
* occurs before the truncate completes, so it is now safe to propagate |
| 1141 |
* the new, shorter inode size (held for now in i_size) into the |
| 1142 |
* on-disk inode. We do this via i_disksize, which is the value which |
| 1143 |
* ext4 *really* writes onto the disk inode. |
| 1144 |
*/ |
| 1145 |
ei->i_disksize = inode->i_size; |
| 1146 |
|
| 1147 |
if (last_block == max_block) { |
| 1148 |
/* |
| 1149 |
* It is unnecessary to free any data blocks if last_block is |
| 1150 |
* equal to the indirect block limit. |
| 1151 |
*/ |
| 1152 |
return; |
| 1153 |
} else if (n == 1) { /* direct blocks */ |
| 1154 |
ext4_free_data(handle, inode, NULL, i_data+offsets[0], |
| 1155 |
i_data + EXT4_NDIR_BLOCKS); |
| 1156 |
goto do_indirects; |
| 1157 |
} |
| 1158 |
|
| 1159 |
partial = ext4_find_shared(inode, n, offsets, chain, &nr); |
| 1160 |
/* Kill the top of shared branch (not detached) */ |
| 1161 |
if (nr) { |
| 1162 |
if (partial == chain) { |
| 1163 |
/* Shared branch grows from the inode */ |
| 1164 |
ext4_free_branches(handle, inode, NULL, |
| 1165 |
&nr, &nr+1, (chain+n-1) - partial); |
| 1166 |
*partial->p = 0; |
| 1167 |
/* |
| 1168 |
* We mark the inode dirty prior to restart, |
| 1169 |
* and prior to stop. No need for it here. |
| 1170 |
*/ |
| 1171 |
} else { |
| 1172 |
/* Shared branch grows from an indirect block */ |
| 1173 |
BUFFER_TRACE(partial->bh, "get_write_access"); |
| 1174 |
ext4_free_branches(handle, inode, partial->bh, |
| 1175 |
partial->p, |
| 1176 |
partial->p+1, (chain+n-1) - partial); |
| 1177 |
} |
| 1178 |
} |
| 1179 |
/* Clear the ends of indirect blocks on the shared branch */ |
| 1180 |
while (partial > chain) { |
| 1181 |
ext4_free_branches(handle, inode, partial->bh, partial->p + 1, |
| 1182 |
(__le32*)partial->bh->b_data+addr_per_block, |
| 1183 |
(chain+n-1) - partial); |
| 1184 |
BUFFER_TRACE(partial->bh, "call brelse"); |
| 1185 |
brelse(partial->bh); |
| 1186 |
partial--; |
| 1187 |
} |
| 1188 |
do_indirects: |
| 1189 |
/* Kill the remaining (whole) subtrees */ |
| 1190 |
switch (offsets[0]) { |
| 1191 |
default: |
| 1192 |
nr = i_data[EXT4_IND_BLOCK]; |
| 1193 |
if (nr) { |
| 1194 |
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 1); |
| 1195 |
i_data[EXT4_IND_BLOCK] = 0; |
| 1196 |
} |
| 1197 |
fallthrough; |
| 1198 |
case EXT4_IND_BLOCK: |
| 1199 |
nr = i_data[EXT4_DIND_BLOCK]; |
| 1200 |
if (nr) { |
| 1201 |
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 2); |
| 1202 |
i_data[EXT4_DIND_BLOCK] = 0; |
| 1203 |
} |
| 1204 |
fallthrough; |
| 1205 |
case EXT4_DIND_BLOCK: |
| 1206 |
nr = i_data[EXT4_TIND_BLOCK]; |
| 1207 |
if (nr) { |
| 1208 |
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 3); |
| 1209 |
i_data[EXT4_TIND_BLOCK] = 0; |
| 1210 |
} |
| 1211 |
fallthrough; |
| 1212 |
case EXT4_TIND_BLOCK: |
| 1213 |
; |
| 1214 |
} |
| 1215 |
} |
| 1216 |
|
| 1217 |
/** |
| 1218 |
* ext4_ind_remove_space - remove space from the range |
| 1219 |
* @handle: JBD handle for this transaction |
| 1220 |
* @inode: inode we are dealing with |
| 1221 |
* @start: First block to remove |
| 1222 |
* @end: One block after the last block to remove (exclusive) |
| 1223 |
* |
| 1224 |
* Free the blocks in the defined range (end is exclusive endpoint of |
| 1225 |
* range). This is used by ext4_punch_hole(). |
| 1226 |
*/ |
| 1227 |
int ext4_ind_remove_space(handle_t *handle, struct inode *inode, |
| 1228 |
ext4_lblk_t start, ext4_lblk_t end) |
| 1229 |
{ |
| 1230 |
struct ext4_inode_info *ei = EXT4_I(inode); |
| 1231 |
__le32 *i_data = ei->i_data; |
| 1232 |
int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); |
| 1233 |
ext4_lblk_t offsets[4], offsets2[4]; |
| 1234 |
Indirect chain[4], chain2[4]; |
| 1235 |
Indirect *partial, *partial2; |
| 1236 |
Indirect *p = NULL, *p2 = NULL; |
| 1237 |
ext4_lblk_t max_block; |
| 1238 |
__le32 nr = 0, nr2 = 0; |
| 1239 |
int n = 0, n2 = 0; |
| 1240 |
unsigned blocksize = inode->i_sb->s_blocksize; |
| 1241 |
|
| 1242 |
max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1) |
| 1243 |
>> EXT4_BLOCK_SIZE_BITS(inode->i_sb); |
| 1244 |
if (end >= max_block) |
| 1245 |
end = max_block; |
| 1246 |
if ((start >= end) || (start > max_block)) |
| 1247 |
return 0; |
| 1248 |
|
| 1249 |
n = ext4_block_to_path(inode, start, offsets, NULL); |
| 1250 |
n2 = ext4_block_to_path(inode, end, offsets2, NULL); |
| 1251 |
|
| 1252 |
BUG_ON(n > n2); |
| 1253 |
|
| 1254 |
if ((n == 1) && (n == n2)) { |
| 1255 |
/* We're punching only within direct block range */ |
| 1256 |
ext4_free_data(handle, inode, NULL, i_data + offsets[0], |
| 1257 |
i_data + offsets2[0]); |
| 1258 |
return 0; |
| 1259 |
} else if (n2 > n) { |
| 1260 |
/* |
| 1261 |
* Start and end are on a different levels so we're going to |
| 1262 |
* free partial block at start, and partial block at end of |
| 1263 |
* the range. If there are some levels in between then |
| 1264 |
* do_indirects label will take care of that. |
| 1265 |
*/ |
| 1266 |
|
| 1267 |
if (n == 1) { |
| 1268 |
/* |
| 1269 |
* Start is at the direct block level, free |
| 1270 |
* everything to the end of the level. |
| 1271 |
*/ |
| 1272 |
ext4_free_data(handle, inode, NULL, i_data + offsets[0], |
| 1273 |
i_data + EXT4_NDIR_BLOCKS); |
| 1274 |
goto end_range; |
| 1275 |
} |
| 1276 |
|
| 1277 |
|
| 1278 |
partial = p = ext4_find_shared(inode, n, offsets, chain, &nr); |
| 1279 |
if (nr) { |
| 1280 |
if (partial == chain) { |
| 1281 |
/* Shared branch grows from the inode */ |
| 1282 |
ext4_free_branches(handle, inode, NULL, |
| 1283 |
&nr, &nr+1, (chain+n-1) - partial); |
| 1284 |
*partial->p = 0; |
| 1285 |
} else { |
| 1286 |
/* Shared branch grows from an indirect block */ |
| 1287 |
BUFFER_TRACE(partial->bh, "get_write_access"); |
| 1288 |
ext4_free_branches(handle, inode, partial->bh, |
| 1289 |
partial->p, |
| 1290 |
partial->p+1, (chain+n-1) - partial); |
| 1291 |
} |
| 1292 |
} |
| 1293 |
|
| 1294 |
/* |
| 1295 |
* Clear the ends of indirect blocks on the shared branch |
| 1296 |
* at the start of the range |
| 1297 |
*/ |
| 1298 |
while (partial > chain) { |
| 1299 |
ext4_free_branches(handle, inode, partial->bh, |
| 1300 |
partial->p + 1, |
| 1301 |
(__le32 *)partial->bh->b_data+addr_per_block, |
| 1302 |
(chain+n-1) - partial); |
| 1303 |
partial--; |
| 1304 |
} |
| 1305 |
|
| 1306 |
end_range: |
| 1307 |
partial2 = p2 = ext4_find_shared(inode, n2, offsets2, chain2, &nr2); |
| 1308 |
if (nr2) { |
| 1309 |
if (partial2 == chain2) { |
| 1310 |
/* |
| 1311 |
* Remember, end is exclusive so here we're at |
| 1312 |
* the start of the next level we're not going |
| 1313 |
* to free. Everything was covered by the start |
| 1314 |
* of the range. |
| 1315 |
*/ |
| 1316 |
goto do_indirects; |
| 1317 |
} |
| 1318 |
} else { |
| 1319 |
/* |
| 1320 |
* ext4_find_shared returns Indirect structure which |
| 1321 |
* points to the last element which should not be |
| 1322 |
* removed by truncate. But this is end of the range |
| 1323 |
* in punch_hole so we need to point to the next element |
| 1324 |
*/ |
| 1325 |
partial2->p++; |
| 1326 |
} |
| 1327 |
|
| 1328 |
/* |
| 1329 |
* Clear the ends of indirect blocks on the shared branch |
| 1330 |
* at the end of the range |
| 1331 |
*/ |
| 1332 |
while (partial2 > chain2) { |
| 1333 |
ext4_free_branches(handle, inode, partial2->bh, |
| 1334 |
(__le32 *)partial2->bh->b_data, |
| 1335 |
partial2->p, |
| 1336 |
(chain2+n2-1) - partial2); |
| 1337 |
partial2--; |
| 1338 |
} |
| 1339 |
goto do_indirects; |
| 1340 |
} |
| 1341 |
|
| 1342 |
/* Punch happened within the same level (n == n2) */ |
| 1343 |
partial = p = ext4_find_shared(inode, n, offsets, chain, &nr); |
| 1344 |
partial2 = p2 = ext4_find_shared(inode, n2, offsets2, chain2, &nr2); |
| 1345 |
|
| 1346 |
/* Free top, but only if partial2 isn't its subtree. */ |
| 1347 |
if (nr) { |
| 1348 |
int level = min(partial - chain, partial2 - chain2); |
| 1349 |
int i; |
| 1350 |
int subtree = 1; |
| 1351 |
|
| 1352 |
for (i = 0; i <= level; i++) { |
| 1353 |
if (offsets[i] != offsets2[i]) { |
| 1354 |
subtree = 0; |
| 1355 |
break; |
| 1356 |
} |
| 1357 |
} |
| 1358 |
|
| 1359 |
if (!subtree) { |
| 1360 |
if (partial == chain) { |
| 1361 |
/* Shared branch grows from the inode */ |
| 1362 |
ext4_free_branches(handle, inode, NULL, |
| 1363 |
&nr, &nr+1, |
| 1364 |
(chain+n-1) - partial); |
| 1365 |
*partial->p = 0; |
| 1366 |
} else { |
| 1367 |
/* Shared branch grows from an indirect block */ |
| 1368 |
BUFFER_TRACE(partial->bh, "get_write_access"); |
| 1369 |
ext4_free_branches(handle, inode, partial->bh, |
| 1370 |
partial->p, |
| 1371 |
partial->p+1, |
| 1372 |
(chain+n-1) - partial); |
| 1373 |
} |
| 1374 |
} |
| 1375 |
} |
| 1376 |
|
| 1377 |
if (!nr2) { |
| 1378 |
/* |
| 1379 |
* ext4_find_shared returns Indirect structure which |
| 1380 |
* points to the last element which should not be |
| 1381 |
* removed by truncate. But this is end of the range |
| 1382 |
* in punch_hole so we need to point to the next element |
| 1383 |
*/ |
| 1384 |
partial2->p++; |
| 1385 |
} |
| 1386 |
|
| 1387 |
while (partial > chain || partial2 > chain2) { |
| 1388 |
int depth = (chain+n-1) - partial; |
| 1389 |
int depth2 = (chain2+n2-1) - partial2; |
| 1390 |
|
| 1391 |
if (partial > chain && partial2 > chain2 && |
| 1392 |
partial->bh->b_blocknr == partial2->bh->b_blocknr) { |
| 1393 |
/* |
| 1394 |
* We've converged on the same block. Clear the range, |
| 1395 |
* then we're done. |
| 1396 |
*/ |
| 1397 |
ext4_free_branches(handle, inode, partial->bh, |
| 1398 |
partial->p + 1, |
| 1399 |
partial2->p, |
| 1400 |
(chain+n-1) - partial); |
| 1401 |
goto cleanup; |
| 1402 |
} |
| 1403 |
|
| 1404 |
/* |
| 1405 |
* The start and end partial branches may not be at the same |
| 1406 |
* level even though the punch happened within one level. So, we |
| 1407 |
* give them a chance to arrive at the same level, then walk |
| 1408 |
* them in step with each other until we converge on the same |
| 1409 |
* block. |
| 1410 |
*/ |
| 1411 |
if (partial > chain && depth <= depth2) { |
| 1412 |
ext4_free_branches(handle, inode, partial->bh, |
| 1413 |
partial->p + 1, |
| 1414 |
(__le32 *)partial->bh->b_data+addr_per_block, |
| 1415 |
(chain+n-1) - partial); |
| 1416 |
partial--; |
| 1417 |
} |
| 1418 |
if (partial2 > chain2 && depth2 <= depth) { |
| 1419 |
ext4_free_branches(handle, inode, partial2->bh, |
| 1420 |
(__le32 *)partial2->bh->b_data, |
| 1421 |
partial2->p, |
| 1422 |
(chain2+n2-1) - partial2); |
| 1423 |
partial2--; |
| 1424 |
} |
| 1425 |
} |
| 1426 |
|
| 1427 |
cleanup: |
| 1428 |
while (p && p > chain) { |
| 1429 |
BUFFER_TRACE(p->bh, "call brelse"); |
| 1430 |
brelse(p->bh); |
| 1431 |
p--; |
| 1432 |
} |
| 1433 |
while (p2 && p2 > chain2) { |
| 1434 |
BUFFER_TRACE(p2->bh, "call brelse"); |
| 1435 |
brelse(p2->bh); |
| 1436 |
p2--; |
| 1437 |
} |
| 1438 |
return 0; |
| 1439 |
|
| 1440 |
do_indirects: |
| 1441 |
/* Kill the remaining (whole) subtrees */ |
| 1442 |
switch (offsets[0]) { |
| 1443 |
default: |
| 1444 |
if (++n >= n2) |
| 1445 |
break; |
| 1446 |
nr = i_data[EXT4_IND_BLOCK]; |
| 1447 |
if (nr) { |
| 1448 |
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 1); |
| 1449 |
i_data[EXT4_IND_BLOCK] = 0; |
| 1450 |
} |
| 1451 |
fallthrough; |
| 1452 |
case EXT4_IND_BLOCK: |
| 1453 |
if (++n >= n2) |
| 1454 |
break; |
| 1455 |
nr = i_data[EXT4_DIND_BLOCK]; |
| 1456 |
if (nr) { |
| 1457 |
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 2); |
| 1458 |
i_data[EXT4_DIND_BLOCK] = 0; |
| 1459 |
} |
| 1460 |
fallthrough; |
| 1461 |
case EXT4_DIND_BLOCK: |
| 1462 |
if (++n >= n2) |
| 1463 |
break; |
| 1464 |
nr = i_data[EXT4_TIND_BLOCK]; |
| 1465 |
if (nr) { |
| 1466 |
ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 3); |
| 1467 |
i_data[EXT4_TIND_BLOCK] = 0; |
| 1468 |
} |
| 1469 |
fallthrough; |
| 1470 |
case EXT4_TIND_BLOCK: |
| 1471 |
; |
| 1472 |
} |
| 1473 |
goto cleanup; |
| 1474 |
} |