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 (!EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
 149                                         EXT4_FEATURE_RO_COMPAT_BIGALLOC))
 150                 return 0;
 151
 152         base_block = lblk & ~EXT2FS_CLUSTER_MASK(fs);
 153         /*
 154          * Except for the logical block (lblk) that was passed in, search all
 155          * blocks in this logical cluster for a mapping to a physical cluster.
 156          * If any such map exists, calculate the physical block that maps to
 157          * the logical block and return that.
 158          *
 159          * The old code wouldn't even look if (block % cluster_ratio) == 0;
 160          * this is incorrect if we're allocating blocks in reverse order.
 161          */
 162         for (i = 0; i < EXT2FS_CLUSTER_RATIO(fs); i++) {
 163                 if (base_block + i == lblk)
 164                         continue;
 165                 extent_bmap(fs, ino, inode, handle, 0, 0,
 166                             base_block + i, 0, 0, &pblock);
 167                 if (pblock)
 168                         break;
 169         }
 170         if (pblock == 0)
 171                 return 0;
 172         *phys_blk = pblock - i + (lblk - base_block);
 173         return 0;
 174 }
 175
 176 /* Try to map a logical block to an already-allocated physical cluster. */
 177 errcode_t ext2fs_map_cluster_block(ext2_filsys fs, ext2_ino_t ino,
 178                                    struct ext2_inode *inode, blk64_t lblk,
 179                                    blk64_t *pblk)
 180 {
 181         ext2_extent_handle_t handle;
 182         errcode_t retval;
 183
 184         /* Need bigalloc and extents to be enabled */
 185         *pblk = 0;
 186         if (!EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
 187                                         EXT4_FEATURE_RO_COMPAT_BIGALLOC) ||
 188             !(inode->i_flags & EXT4_EXTENTS_FL))
 189                 return 0;
 190
 191         retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 192         if (retval)
 193                 goto out;
 194
 195         retval = implied_cluster_alloc(fs, ino, inode, handle, lblk, pblk);
 196         if (retval)
 197                 goto out2;
 198
 199 out2:
 200         ext2fs_extent_free(handle);
 201 out:
 202         return retval;
 203 }
 204
 205 static errcode_t extent_bmap(ext2_filsys fs, ext2_ino_t ino,
 206                              struct ext2_inode *inode,
 207                              ext2_extent_handle_t handle,
 208                              char *block_buf, int bmap_flags, blk64_t block,
 209                              int *ret_flags, int *blocks_alloc,
 210                              blk64_t *phys_blk)
 211 {
 212         struct ext2fs_extent    extent;
 213         unsigned int            offset;
 214         errcode_t               retval = 0;
 215         blk64_t                 blk64 = 0;
 216         int                     alloc = 0;
 217
 218         if (bmap_flags & BMAP_SET) {
 219                 retval = ext2fs_extent_set_bmap(handle, block,
 220                                                 *phys_blk, 0);
 221                 return retval;
 222         }
 223         retval = ext2fs_extent_goto(handle, block);
 224         if (retval) {
 225                 /* If the extent is not found, return phys_blk = 0 */
 226                 if (retval == EXT2_ET_EXTENT_NOT_FOUND)
 227                         goto got_block;
 228                 return retval;
 229         }
 230         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 231         if (retval)
 232                 return retval;
 233         offset = block - extent.e_lblk;
 234         if (block >= extent.e_lblk && (offset <= extent.e_len)) {
 235                 *phys_blk = extent.e_pblk + offset;
 236                 if (ret_flags && extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
 237                         *ret_flags |= BMAP_RET_UNINIT;
 238         }
 239 got_block:
 240         if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) {
 241                 implied_cluster_alloc(fs, ino, inode, handle, block, &blk64);
 242                 if (blk64)
 243                         goto set_extent;
 244                 retval = extent_bmap(fs, ino, inode, handle, block_buf,
 245                                      0, block-1, 0, blocks_alloc, &blk64);
 246                 if (retval)
 247                         blk64 = 0;
 248                 retval = ext2fs_alloc_block2(fs, blk64, block_buf,
 249                                              &blk64);
 250                 if (retval)
 251                         return retval;
 252                 blk64 &= ~EXT2FS_CLUSTER_MASK(fs);
 253                 blk64 += EXT2FS_CLUSTER_MASK(fs) & block;
 254                 alloc++;
 255         set_extent:
 256                 retval = ext2fs_extent_set_bmap(handle, block,
 257                                                 blk64, 0);
 258                 if (retval) {
 259                         ext2fs_block_alloc_stats2(fs, blk64, -1);
 260                         return retval;
 261                 }
 262                 /* Update inode after setting extent */
 263                 retval = ext2fs_read_inode(fs, ino, inode);
 264                 if (retval)
 265                         return retval;
 266                 *blocks_alloc += alloc;
 267                 *phys_blk = blk64;
 268         }
 269         return 0;
 270 }
 271
 272 int ext2fs_file_block_offset_too_big(ext2_filsys fs,
 273                                      struct ext2_inode *inode,
 274                                      blk64_t offset)
 275 {
 276         blk64_t addr_per_block, max_map_block;
 277
 278         /* Kernel seems to cut us off at 4294967294 blocks */
 279         if (offset >= (1ULL << 32) - 1)
 280                 return 1;
 281
 282         if (inode->i_flags & EXT4_EXTENTS_FL)
 283                 return 0;
 284
 285         addr_per_block = fs->blocksize >> 2;
 286         max_map_block = addr_per_block;
 287         max_map_block += addr_per_block * addr_per_block;
 288         max_map_block += addr_per_block * addr_per_block * addr_per_block;
 289         max_map_block += 12;
 290
 291         return offset >= max_map_block;
 292 }
 293
 294 errcode_t ext2fs_bmap2(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode,
 295                        char *block_buf, int bmap_flags, blk64_t block,
 296                        int *ret_flags, blk64_t *phys_blk)
 297 {
 298         struct ext2_inode inode_buf;
 299         ext2_extent_handle_t handle = 0;
 300         blk_t addr_per_block;
 301         blk_t   b, blk32;
 302         char    *buf = 0;
 303         errcode_t       retval = 0;
 304         int             blocks_alloc = 0, inode_dirty = 0;
 305
 306         if (!(bmap_flags & BMAP_SET))
 307                 *phys_blk = 0;
 308
 309         if (ret_flags)
 310                 *ret_flags = 0;
 311
 312         /* Read inode structure if necessary */
 313         if (!inode) {
 314                 retval = ext2fs_read_inode(fs, ino, &inode_buf);
 315                 if (retval)
 316                         return retval;
 317                 inode = &inode_buf;
 318         }
 319         addr_per_block = (blk_t) fs->blocksize >> 2;
 320
 321         if (ext2fs_file_block_offset_too_big(fs, inode, block))
 322                 return EXT2_ET_FILE_TOO_BIG;
 323
 324         /*
 325          * If an inode has inline data, that means that it doesn't have
 326          * any blocks and we shouldn't map any blocks for it.
 327          */
 328         if (inode->i_flags & EXT4_INLINE_DATA_FL)
 329                 return EXT2_ET_INLINE_DATA_NO_BLOCK;
 330
 331         if (!block_buf) {
 332                 retval = ext2fs_get_array(2, fs->blocksize, &buf);
 333                 if (retval)
 334                         return retval;
 335                 block_buf = buf;
 336         }
 337
 338         if (inode->i_flags & EXT4_EXTENTS_FL) {
 339                 retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 340                 if (retval)
 341                         goto done;
 342                 retval = extent_bmap(fs, ino, inode, handle, block_buf,
 343                                      bmap_flags, block, ret_flags,
 344                                      &blocks_alloc, phys_blk);
 345                 goto done;
 346         }
 347
 348         if (block < EXT2_NDIR_BLOCKS) {
 349                 if (bmap_flags & BMAP_SET) {
 350                         b = *phys_blk;
 351                         inode_bmap(inode, block) = b;
 352                         inode_dirty++;
 353                         goto done;
 354                 }
 355
 356                 *phys_blk = inode_bmap(inode, block);
 357                 b = block ? inode_bmap(inode, block-1) : 0;
 358
 359                 if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) {
 360                         retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 361                         if (retval)
 362                                 goto done;
 363                         inode_bmap(inode, block) = b;
 364                         blocks_alloc++;
 365                         *phys_blk = b;
 366                 }
 367                 goto done;
 368         }
 369
 370         /* Indirect block */
 371         block -= EXT2_NDIR_BLOCKS;
 372         blk32 = *phys_blk;
 373         if (block < addr_per_block) {
 374                 b = inode_bmap(inode, EXT2_IND_BLOCK);
 375                 if (!b) {
 376                         if (!(bmap_flags & BMAP_ALLOC)) {
 377                                 if (bmap_flags & BMAP_SET)
 378                                         retval = EXT2_ET_SET_BMAP_NO_IND;
 379                                 goto done;
 380                         }
 381
 382                         b = inode_bmap(inode, EXT2_IND_BLOCK-1);
 383                         retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 384                         if (retval)
 385                                 goto done;
 386                         inode_bmap(inode, EXT2_IND_BLOCK) = b;
 387                         blocks_alloc++;
 388                 }
 389                 retval = block_ind_bmap(fs, bmap_flags, b, block_buf,
 390                                         &blocks_alloc, block, &blk32);
 391                 if (retval == 0)
 392                         *phys_blk = blk32;
 393                 goto done;
 394         }
 395
 396         /* Doubly indirect block  */
 397         block -= addr_per_block;
 398         if (block < addr_per_block * addr_per_block) {
 399                 b = inode_bmap(inode, EXT2_DIND_BLOCK);
 400                 if (!b) {
 401                         if (!(bmap_flags & BMAP_ALLOC)) {
 402                                 if (bmap_flags & BMAP_SET)
 403                                         retval = EXT2_ET_SET_BMAP_NO_IND;
 404                                 goto done;
 405                         }
 406
 407                         b = inode_bmap(inode, EXT2_IND_BLOCK);
 408                         retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 409                         if (retval)
 410                                 goto done;
 411                         inode_bmap(inode, EXT2_DIND_BLOCK) = b;
 412                         blocks_alloc++;
 413                 }
 414                 retval = block_dind_bmap(fs, bmap_flags, b, block_buf,
 415                                          &blocks_alloc, block, &blk32);
 416                 if (retval == 0)
 417                         *phys_blk = blk32;
 418                 goto done;
 419         }
 420
 421         /* Triply indirect block */
 422         block -= addr_per_block * addr_per_block;
 423         b = inode_bmap(inode, EXT2_TIND_BLOCK);
 424         if (!b) {
 425                 if (!(bmap_flags & BMAP_ALLOC)) {
 426                         if (bmap_flags & BMAP_SET)
 427                                 retval = EXT2_ET_SET_BMAP_NO_IND;
 428                         goto done;
 429                 }
 430
 431                 b = inode_bmap(inode, EXT2_DIND_BLOCK);
 432                 retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 433                 if (retval)
 434                         goto done;
 435                 inode_bmap(inode, EXT2_TIND_BLOCK) = b;
 436                 blocks_alloc++;
 437         }
 438         retval = block_tind_bmap(fs, bmap_flags, b, block_buf,
 439                                  &blocks_alloc, block, &blk32);
 440         if (retval == 0)
 441                 *phys_blk = blk32;
 442 done:
 443         if (buf)
 444                 ext2fs_free_mem(&buf);
 445         if (handle)
 446                 ext2fs_extent_free(handle);
 447         if ((retval == 0) && (blocks_alloc || inode_dirty)) {
 448                 ext2fs_iblk_add_blocks(fs, inode, blocks_alloc);
 449                 retval = ext2fs_write_inode(fs, ino, inode);
 450         }
 451         return retval;
 452 }
 453
 454 errcode_t ext2fs_bmap(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode,
 455                       char *block_buf, int bmap_flags, blk_t block,
 456                       blk_t *phys_blk)
 457 {
 458         errcode_t ret;
 459         blk64_t ret_blk = *phys_blk;
 460
 461         ret = ext2fs_bmap2(fs, ino, inode, block_buf, bmap_flags, block,
 462                             0, &ret_blk);
 463         if (ret)
 464                 return ret;
 465         if (ret_blk >= ((long long) 1 << 32))
 466                 return EOVERFLOW;
 467         *phys_blk = ret_blk;
 468         return 0;
 469 }