lib/ext2fs/bmap.c

   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 }