1 /* 2 * bmap.c --- logical to physical block mapping 3 * 4 * Copyright (C) 1997 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Library 8 * General Public License, version 2. 9 * %End-Header% 10 */ 11 12 #include "config.h" 13 #include <stdio.h> 14 #include <string.h> 15 #if HAVE_UNISTD_H 16 #include <unistd.h> 17 #endif 18 #include <errno.h> 19 20 #include "ext2_fs.h" 21 #include "ext2fsP.h" 22 23 #if defined(__GNUC__) && !defined(NO_INLINE_FUNCS) 24 #define _BMAP_INLINE_ __inline__ 25 #else 26 #define _BMAP_INLINE_ 27 #endif 28 29 extern errcode_t ext2fs_bmap(ext2_filsys fs, ext2_ino_t ino, 30 struct ext2_inode *inode, 31 char *block_buf, int bmap_flags, 32 blk_t block, blk_t *phys_blk); 33 34 #define inode_bmap(inode, nr) ((inode)->i_block[(nr)]) 35 36 static _BMAP_INLINE_ errcode_t block_ind_bmap(ext2_filsys fs, int flags, 37 blk_t ind, char *block_buf, 38 int *blocks_alloc, 39 blk_t nr, blk_t *ret_blk) 40 { 41 errcode_t retval; 42 blk_t b; 43 44 if (!ind) { 45 if (flags & BMAP_SET) 46 return EXT2_ET_SET_BMAP_NO_IND; 47 *ret_blk = 0; 48 return 0; 49 } 50 retval = io_channel_read_blk(fs->io, ind, 1, block_buf); 51 if (retval) 52 return retval; 53 54 if (flags & BMAP_SET) { 55 b = *ret_blk; 56 #ifdef WORDS_BIGENDIAN 57 b = ext2fs_swab32(b); 58 #endif 59 ((blk_t *) block_buf)[nr] = b; 60 return io_channel_write_blk(fs->io, ind, 1, block_buf); 61 } 62 63 b = ((blk_t *) block_buf)[nr]; 64 65 #ifdef WORDS_BIGENDIAN 66 b = ext2fs_swab32(b); 67 #endif 68 69 if (!b && (flags & BMAP_ALLOC)) { 70 b = nr ? ext2fs_le32_to_cpu(((blk_t *)block_buf)[nr - 1]) : ind; 71 retval = ext2fs_alloc_block(fs, b, 72 block_buf + fs->blocksize, &b); 73 if (retval) 74 return retval; 75 76 #ifdef WORDS_BIGENDIAN 77 ((blk_t *) block_buf)[nr] = ext2fs_swab32(b); 78 #else 79 ((blk_t *) block_buf)[nr] = b; 80 #endif 81 82 retval = io_channel_write_blk(fs->io, ind, 1, block_buf); 83 if (retval) 84 return retval; 85 86 (*blocks_alloc)++; 87 } 88 89 *ret_blk = b; 90 return 0; 91 } 92 93 static _BMAP_INLINE_ errcode_t block_dind_bmap(ext2_filsys fs, int flags, 94 blk_t dind, char *block_buf, 95 int *blocks_alloc, 96 blk_t nr, blk_t *ret_blk) 97 { 98 blk_t b = 0; 99 errcode_t retval; 100 blk_t addr_per_block; 101 102 addr_per_block = (blk_t) fs->blocksize >> 2; 103 104 retval = block_ind_bmap(fs, flags & ~BMAP_SET, dind, block_buf, 105 blocks_alloc, nr / addr_per_block, &b); 106 if (retval) 107 return retval; 108 retval = block_ind_bmap(fs, flags, b, block_buf, blocks_alloc, 109 nr % addr_per_block, ret_blk); 110 return retval; 111 } 112 113 static _BMAP_INLINE_ errcode_t block_tind_bmap(ext2_filsys fs, int flags, 114 blk_t tind, char *block_buf, 115 int *blocks_alloc, 116 blk_t nr, blk_t *ret_blk) 117 { 118 blk_t b = 0; 119 errcode_t retval; 120 blk_t addr_per_block; 121 122 addr_per_block = (blk_t) fs->blocksize >> 2; 123 124 retval = block_dind_bmap(fs, flags & ~BMAP_SET, tind, block_buf, 125 blocks_alloc, nr / addr_per_block, &b); 126 if (retval) 127 return retval; 128 retval = block_ind_bmap(fs, flags, b, block_buf, blocks_alloc, 129 nr % addr_per_block, ret_blk); 130 return retval; 131 } 132 133 static errcode_t extent_bmap(ext2_filsys fs, ext2_ino_t ino, 134 struct ext2_inode *inode, 135 ext2_extent_handle_t handle, 136 char *block_buf, int bmap_flags, blk64_t block, 137 int *ret_flags, int *blocks_alloc, 138 blk64_t *phys_blk); 139 140 static errcode_t implied_cluster_alloc(ext2_filsys fs, ext2_ino_t ino, 141 struct ext2_inode *inode, 142 ext2_extent_handle_t handle, 143 blk64_t lblk, blk64_t *phys_blk) 144 { 145 blk64_t base_block, pblock = 0; 146 int i; 147 148 if (!ext2fs_has_feature_bigalloc(fs->super)) 149 return 0; 150 151 base_block = lblk & ~EXT2FS_CLUSTER_MASK(fs); 152 /* 153 * Except for the logical block (lblk) that was passed in, search all 154 * blocks in this logical cluster for a mapping to a physical cluster. 155 * If any such map exists, calculate the physical block that maps to 156 * the logical block and return that. 157 * 158 * The old code wouldn't even look if (block % cluster_ratio) == 0; 159 * this is incorrect if we're allocating blocks in reverse order. 160 */ 161 for (i = 0; i < EXT2FS_CLUSTER_RATIO(fs); i++) { 162 if (base_block + i == lblk) 163 continue; 164 extent_bmap(fs, ino, inode, handle, 0, 0, 165 base_block + i, 0, 0, &pblock); 166 if (pblock) 167 break; 168 } 169 if (pblock == 0) 170 return 0; 171 *phys_blk = pblock - i + (lblk - base_block); 172 return 0; 173 } 174 175 /* Try to map a logical block to an already-allocated physical cluster. */ 176 errcode_t ext2fs_map_cluster_block(ext2_filsys fs, ext2_ino_t ino, 177 struct ext2_inode *inode, blk64_t lblk, 178 blk64_t *pblk) 179 { 180 ext2_extent_handle_t handle; 181 errcode_t retval; 182 183 /* Need bigalloc and extents to be enabled */ 184 *pblk = 0; 185 if (!ext2fs_has_feature_bigalloc(fs->super) || 186 !(inode->i_flags & EXT4_EXTENTS_FL)) 187 return 0; 188 189 retval = ext2fs_extent_open2(fs, ino, inode, &handle); 190 if (retval) 191 goto out; 192 193 retval = implied_cluster_alloc(fs, ino, inode, handle, lblk, pblk); 194 if (retval) 195 goto out2; 196 197 out2: 198 ext2fs_extent_free(handle); 199 out: 200 return retval; 201 } 202 203 static errcode_t extent_bmap(ext2_filsys fs, ext2_ino_t ino, 204 struct ext2_inode *inode, 205 ext2_extent_handle_t handle, 206 char *block_buf, int bmap_flags, blk64_t block, 207 int *ret_flags, int *blocks_alloc, 208 blk64_t *phys_blk) 209 { 210 struct blk_alloc_ctx alloc_ctx; 211 struct ext2fs_extent extent; 212 unsigned int offset; 213 errcode_t retval = 0; 214 blk64_t blk64 = 0; 215 int alloc = 0; 216 int set_flags; 217 218 set_flags = bmap_flags & BMAP_UNINIT ? EXT2_EXTENT_SET_BMAP_UNINIT : 0; 219 220 if (bmap_flags & BMAP_SET) { 221 retval = ext2fs_extent_set_bmap(handle, block, 222 *phys_blk, set_flags); 223 return retval; 224 } 225 retval = ext2fs_extent_goto(handle, block); 226 if (retval) { 227 /* If the extent is not found, return phys_blk = 0 */ 228 if (retval == EXT2_ET_EXTENT_NOT_FOUND) { 229 extent.e_lblk = block; 230 goto got_block; 231 } 232 return retval; 233 } 234 retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 235 if (retval) 236 return retval; 237 offset = block - extent.e_lblk; 238 if (block >= extent.e_lblk && (offset <= extent.e_len)) { 239 *phys_blk = extent.e_pblk + offset; 240 if (ret_flags && extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT) 241 *ret_flags |= BMAP_RET_UNINIT; 242 } 243 got_block: 244 if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) { 245 implied_cluster_alloc(fs, ino, inode, handle, block, &blk64); 246 if (blk64) 247 goto set_extent; 248 retval = extent_bmap(fs, ino, inode, handle, block_buf, 249 0, block-1, 0, blocks_alloc, &blk64); 250 if (retval) 251 blk64 = ext2fs_find_inode_goal(fs, ino, inode, block); 252 alloc_ctx.ino = ino; 253 alloc_ctx.inode = inode; 254 alloc_ctx.lblk = extent.e_lblk; 255 alloc_ctx.flags = BLOCK_ALLOC_DATA; 256 retval = ext2fs_alloc_block3(fs, blk64, block_buf, &blk64, 257 &alloc_ctx); 258 if (retval) 259 return retval; 260 blk64 &= ~EXT2FS_CLUSTER_MASK(fs); 261 blk64 += EXT2FS_CLUSTER_MASK(fs) & block; 262 alloc++; 263 set_extent: 264 retval = ext2fs_extent_set_bmap(handle, block, 265 blk64, set_flags); 266 if (retval) { 267 ext2fs_block_alloc_stats2(fs, blk64, -1); 268 return retval; 269 } 270 /* Update inode after setting extent */ 271 retval = ext2fs_read_inode(fs, ino, inode); 272 if (retval) 273 return retval; 274 *blocks_alloc += alloc; 275 *phys_blk = blk64; 276 } 277 return 0; 278 } 279 280 int ext2fs_file_block_offset_too_big(ext2_filsys fs, 281 struct ext2_inode *inode, 282 blk64_t offset) 283 { 284 blk64_t addr_per_block, max_map_block; 285 286 /* Kernel seems to cut us off at 4294967294 blocks */ 287 if (offset >= (1ULL << 32) - 1) 288 return 1; 289 290 if (inode->i_flags & EXT4_EXTENTS_FL) 291 return 0; 292 293 addr_per_block = fs->blocksize >> 2; 294 max_map_block = addr_per_block; 295 max_map_block += addr_per_block * addr_per_block; 296 max_map_block += addr_per_block * addr_per_block * addr_per_block; 297 max_map_block += 12; 298 299 return offset >= max_map_block; 300 } 301 302 errcode_t ext2fs_bmap2(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode, 303 char *block_buf, int bmap_flags, blk64_t block, 304 int *ret_flags, blk64_t *phys_blk) 305 { 306 struct ext2_inode inode_buf; 307 ext2_extent_handle_t handle = 0; 308 blk_t addr_per_block; 309 blk_t b, blk32; 310 blk64_t b64; 311 char *buf = 0; 312 errcode_t retval = 0; 313 int blocks_alloc = 0, inode_dirty = 0; 314 struct blk_alloc_ctx alloc_ctx = { 315 .ino = ino, 316 .inode = inode, 317 .lblk = 0, 318 .flags = BLOCK_ALLOC_DATA, 319 }; 320 321 if (!(bmap_flags & BMAP_SET)) 322 *phys_blk = 0; 323 324 if (ret_flags) 325 *ret_flags = 0; 326 327 /* Read inode structure if necessary */ 328 if (!inode) { 329 retval = ext2fs_read_inode(fs, ino, &inode_buf); 330 if (retval) 331 return retval; 332 inode = &inode_buf; 333 } 334 addr_per_block = (blk_t) fs->blocksize >> 2; 335 336 if (ext2fs_file_block_offset_too_big(fs, inode, block)) 337 return EXT2_ET_FILE_TOO_BIG; 338 339 /* 340 * If an inode has inline data, that means that it doesn't have 341 * any blocks and we shouldn't map any blocks for it. 342 */ 343 if (inode->i_flags & EXT4_INLINE_DATA_FL) 344 return EXT2_ET_INLINE_DATA_NO_BLOCK; 345 346 if (!block_buf) { 347 retval = ext2fs_get_array(2, fs->blocksize, &buf); 348 if (retval) 349 return retval; 350 block_buf = buf; 351 } 352 353 if (inode->i_flags & EXT4_EXTENTS_FL) { 354 retval = ext2fs_extent_open2(fs, ino, inode, &handle); 355 if (retval) 356 goto done; 357 retval = extent_bmap(fs, ino, inode, handle, block_buf, 358 bmap_flags, block, ret_flags, 359 &blocks_alloc, phys_blk); 360 goto done; 361 } 362 363 if (block < EXT2_NDIR_BLOCKS) { 364 if (bmap_flags & BMAP_SET) { 365 b = *phys_blk; 366 inode_bmap(inode, block) = b; 367 inode_dirty++; 368 goto done; 369 } 370 371 *phys_blk = inode_bmap(inode, block); 372 b = block ? inode_bmap(inode, block - 1) : 373 ext2fs_find_inode_goal(fs, ino, inode, block); 374 375 if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) { 376 b64 = b; 377 retval = ext2fs_alloc_block3(fs, b64, block_buf, &b64, 378 &alloc_ctx); 379 b = b64; 380 if (retval) 381 goto done; 382 inode_bmap(inode, block) = b; 383 blocks_alloc++; 384 *phys_blk = b; 385 } 386 goto done; 387 } 388 389 /* Indirect block */ 390 block -= EXT2_NDIR_BLOCKS; 391 blk32 = *phys_blk; 392 if (block < addr_per_block) { 393 b = inode_bmap(inode, EXT2_IND_BLOCK); 394 if (!b) { 395 if (!(bmap_flags & BMAP_ALLOC)) { 396 if (bmap_flags & BMAP_SET) 397 retval = EXT2_ET_SET_BMAP_NO_IND; 398 goto done; 399 } 400 401 b = inode_bmap(inode, EXT2_IND_BLOCK-1); 402 b64 = b; 403 retval = ext2fs_alloc_block3(fs, b64, block_buf, &b64, 404 &alloc_ctx); 405 b = b64; 406 if (retval) 407 goto done; 408 inode_bmap(inode, EXT2_IND_BLOCK) = b; 409 blocks_alloc++; 410 } 411 retval = block_ind_bmap(fs, bmap_flags, b, block_buf, 412 &blocks_alloc, block, &blk32); 413 if (retval == 0) 414 *phys_blk = blk32; 415 goto done; 416 } 417 418 /* Doubly indirect block */ 419 block -= addr_per_block; 420 if (block < addr_per_block * addr_per_block) { 421 b = inode_bmap(inode, EXT2_DIND_BLOCK); 422 if (!b) { 423 if (!(bmap_flags & BMAP_ALLOC)) { 424 if (bmap_flags & BMAP_SET) 425 retval = EXT2_ET_SET_BMAP_NO_IND; 426 goto done; 427 } 428 429 b = inode_bmap(inode, EXT2_IND_BLOCK); 430 b64 = b; 431 retval = ext2fs_alloc_block3(fs, b64, block_buf, &b64, 432 &alloc_ctx); 433 b = b64; 434 if (retval) 435 goto done; 436 inode_bmap(inode, EXT2_DIND_BLOCK) = b; 437 blocks_alloc++; 438 } 439 retval = block_dind_bmap(fs, bmap_flags, b, block_buf, 440 &blocks_alloc, block, &blk32); 441 if (retval == 0) 442 *phys_blk = blk32; 443 goto done; 444 } 445 446 /* Triply indirect block */ 447 block -= addr_per_block * addr_per_block; 448 b = inode_bmap(inode, EXT2_TIND_BLOCK); 449 if (!b) { 450 if (!(bmap_flags & BMAP_ALLOC)) { 451 if (bmap_flags & BMAP_SET) 452 retval = EXT2_ET_SET_BMAP_NO_IND; 453 goto done; 454 } 455 456 b = inode_bmap(inode, EXT2_DIND_BLOCK); 457 b64 = b; 458 retval = ext2fs_alloc_block3(fs, b64, block_buf, &b64, 459 &alloc_ctx); 460 b = b64; 461 if (retval) 462 goto done; 463 inode_bmap(inode, EXT2_TIND_BLOCK) = b; 464 blocks_alloc++; 465 } 466 retval = block_tind_bmap(fs, bmap_flags, b, block_buf, 467 &blocks_alloc, block, &blk32); 468 if (retval == 0) 469 *phys_blk = blk32; 470 done: 471 if (*phys_blk && retval == 0 && (bmap_flags & BMAP_ZERO)) 472 retval = ext2fs_zero_blocks2(fs, *phys_blk, 1, NULL, NULL); 473 if (buf) 474 ext2fs_free_mem(&buf); 475 if (handle) 476 ext2fs_extent_free(handle); 477 if ((retval == 0) && (blocks_alloc || inode_dirty)) { 478 ext2fs_iblk_add_blocks(fs, inode, blocks_alloc); 479 retval = ext2fs_write_inode(fs, ino, inode); 480 } 481 return retval; 482 } 483 484 errcode_t ext2fs_bmap(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode, 485 char *block_buf, int bmap_flags, blk_t block, 486 blk_t *phys_blk) 487 { 488 errcode_t ret; 489 blk64_t ret_blk = *phys_blk; 490 491 ret = ext2fs_bmap2(fs, ino, inode, block_buf, bmap_flags, block, 492 0, &ret_blk); 493 if (ret) 494 return ret; 495 if (ret_blk >= ((long long) 1 << 32)) 496 return EOVERFLOW; 497 *phys_blk = ret_blk; 498 return 0; 499 }