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 "ext2fs.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 ? ((blk_t *) block_buf)[nr-1] : 0;
  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;
  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;
 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 block, 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 = block & ~EXT2FS_CLUSTER_MASK(fs);
 153         for (i = 0; i < EXT2FS_CLUSTER_RATIO(fs); i++) {
 154                 if (block == base_block)
 155                         return 0;
 156                 extent_bmap(fs, ino, inode, handle, 0, 0,
 157                             base_block + i, 0, 0, &pblock);
 158                 if (pblock)
 159                         break;
 160         }
 161         if (pblock == 0)
 162                 return 0;
 163         *phys_blk = pblock - i + (block - base_block);
 164         return 0;
 165 }
 166
 167 static errcode_t extent_bmap(ext2_filsys fs, ext2_ino_t ino,
 168                              struct ext2_inode *inode,
 169                              ext2_extent_handle_t handle,
 170                              char *block_buf, int bmap_flags, blk64_t block,
 171                              int *ret_flags, int *blocks_alloc,
 172                              blk64_t *phys_blk)
 173 {
 174         struct ext2fs_extent    extent;
 175         unsigned int            offset;
 176         errcode_t               retval = 0;
 177         blk64_t                 blk64 = 0;
 178         int                     alloc = 0;
 179
 180         if (bmap_flags & BMAP_SET) {
 181                 retval = ext2fs_extent_set_bmap(handle, block,
 182                                                 *phys_blk, 0);
 183                 return retval;
 184         }
 185         retval = ext2fs_extent_goto(handle, block);
 186         if (retval) {
 187                 /* If the extent is not found, return phys_blk = 0 */
 188                 if (retval == EXT2_ET_EXTENT_NOT_FOUND)
 189                         goto got_block;
 190                 return retval;
 191         }
 192         retval = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent);
 193         if (retval)
 194                 return retval;
 195         offset = block - extent.e_lblk;
 196         if (block >= extent.e_lblk && (offset <= extent.e_len)) {
 197                 *phys_blk = extent.e_pblk + offset;
 198                 if (ret_flags && extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT)
 199                         *ret_flags |= BMAP_RET_UNINIT;
 200         }
 201 got_block:
 202         if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) {
 203                 implied_cluster_alloc(fs, ino, inode, handle, block, &blk64);
 204                 if (blk64)
 205                         goto set_extent;
 206                 retval = extent_bmap(fs, ino, inode, handle, block_buf,
 207                                      0, block-1, 0, blocks_alloc, &blk64);
 208                 if (retval)
 209                         blk64 = 0;
 210                 retval = ext2fs_alloc_block2(fs, blk64, block_buf,
 211                                              &blk64);
 212                 if (retval)
 213                         return retval;
 214                 blk64 &= ~EXT2FS_CLUSTER_MASK(fs);
 215                 blk64 += EXT2FS_CLUSTER_MASK(fs) & block;
 216                 alloc++;
 217         set_extent:
 218                 retval = ext2fs_extent_set_bmap(handle, block,
 219                                                 blk64, 0);
 220                 if (retval)
 221                         return retval;
 222                 /* Update inode after setting extent */
 223                 retval = ext2fs_read_inode(fs, ino, inode);
 224                 if (retval)
 225                         return retval;
 226                 *blocks_alloc += alloc;
 227                 *phys_blk = blk64;
 228         }
 229         return 0;
 230 }
 231
 232
 233 errcode_t ext2fs_bmap2(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode,
 234                        char *block_buf, int bmap_flags, blk64_t block,
 235                        int *ret_flags, blk64_t *phys_blk)
 236 {
 237         struct ext2_inode inode_buf;
 238         ext2_extent_handle_t handle = 0;
 239         blk_t addr_per_block;
 240         blk_t   b, blk32;
 241         char    *buf = 0;
 242         errcode_t       retval = 0;
 243         int             blocks_alloc = 0, inode_dirty = 0;
 244
 245         if (!(bmap_flags & BMAP_SET))
 246                 *phys_blk = 0;
 247
 248         if (ret_flags)
 249                 *ret_flags = 0;
 250
 251         /* Read inode structure if necessary */
 252         if (!inode) {
 253                 retval = ext2fs_read_inode(fs, ino, &inode_buf);
 254                 if (retval)
 255                         return retval;
 256                 inode = &inode_buf;
 257         }
 258         addr_per_block = (blk_t) fs->blocksize >> 2;
 259
 260         if (!block_buf) {
 261                 retval = ext2fs_get_array(2, fs->blocksize, &buf);
 262                 if (retval)
 263                         return retval;
 264                 block_buf = buf;
 265         }
 266
 267         if (inode->i_flags & EXT4_EXTENTS_FL) {
 268                 retval = ext2fs_extent_open2(fs, ino, inode, &handle);
 269                 if (retval)
 270                         goto done;
 271                 retval = extent_bmap(fs, ino, inode, handle, block_buf,
 272                                      bmap_flags, block, ret_flags,
 273                                      &blocks_alloc, phys_blk);
 274                 goto done;
 275         }
 276
 277         if (block < EXT2_NDIR_BLOCKS) {
 278                 if (bmap_flags & BMAP_SET) {
 279                         b = *phys_blk;
 280                         inode_bmap(inode, block) = b;
 281                         inode_dirty++;
 282                         goto done;
 283                 }
 284
 285                 *phys_blk = inode_bmap(inode, block);
 286                 b = block ? inode_bmap(inode, block-1) : 0;
 287
 288                 if ((*phys_blk == 0) && (bmap_flags & BMAP_ALLOC)) {
 289                         retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 290                         if (retval)
 291                                 goto done;
 292                         inode_bmap(inode, block) = b;
 293                         blocks_alloc++;
 294                         *phys_blk = b;
 295                 }
 296                 goto done;
 297         }
 298
 299         /* Indirect block */
 300         block -= EXT2_NDIR_BLOCKS;
 301         blk32 = *phys_blk;
 302         if (block < addr_per_block) {
 303                 b = inode_bmap(inode, EXT2_IND_BLOCK);
 304                 if (!b) {
 305                         if (!(bmap_flags & BMAP_ALLOC)) {
 306                                 if (bmap_flags & BMAP_SET)
 307                                         retval = EXT2_ET_SET_BMAP_NO_IND;
 308                                 goto done;
 309                         }
 310
 311                         b = inode_bmap(inode, EXT2_IND_BLOCK-1);
 312                         retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 313                         if (retval)
 314                                 goto done;
 315                         inode_bmap(inode, EXT2_IND_BLOCK) = b;
 316                         blocks_alloc++;
 317                 }
 318                 retval = block_ind_bmap(fs, bmap_flags, b, block_buf,
 319                                         &blocks_alloc, block, &blk32);
 320                 if (retval == 0)
 321                         *phys_blk = blk32;
 322                 goto done;
 323         }
 324
 325         /* Doubly indirect block  */
 326         block -= addr_per_block;
 327         if (block < addr_per_block * addr_per_block) {
 328                 b = inode_bmap(inode, EXT2_DIND_BLOCK);
 329                 if (!b) {
 330                         if (!(bmap_flags & BMAP_ALLOC)) {
 331                                 if (bmap_flags & BMAP_SET)
 332                                         retval = EXT2_ET_SET_BMAP_NO_IND;
 333                                 goto done;
 334                         }
 335
 336                         b = inode_bmap(inode, EXT2_IND_BLOCK);
 337                         retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 338                         if (retval)
 339                                 goto done;
 340                         inode_bmap(inode, EXT2_DIND_BLOCK) = b;
 341                         blocks_alloc++;
 342                 }
 343                 retval = block_dind_bmap(fs, bmap_flags, b, block_buf,
 344                                          &blocks_alloc, block, &blk32);
 345                 if (retval == 0)
 346                         *phys_blk = blk32;
 347                 goto done;
 348         }
 349
 350         /* Triply indirect block */
 351         block -= addr_per_block * addr_per_block;
 352         b = inode_bmap(inode, EXT2_TIND_BLOCK);
 353         if (!b) {
 354                 if (!(bmap_flags & BMAP_ALLOC)) {
 355                         if (bmap_flags & BMAP_SET)
 356                                 retval = EXT2_ET_SET_BMAP_NO_IND;
 357                         goto done;
 358                 }
 359
 360                 b = inode_bmap(inode, EXT2_DIND_BLOCK);
 361                 retval = ext2fs_alloc_block(fs, b, block_buf, &b);
 362                 if (retval)
 363                         goto done;
 364                 inode_bmap(inode, EXT2_TIND_BLOCK) = b;
 365                 blocks_alloc++;
 366         }
 367         retval = block_tind_bmap(fs, bmap_flags, b, block_buf,
 368                                  &blocks_alloc, block, &blk32);
 369         if (retval == 0)
 370                 *phys_blk = blk32;
 371 done:
 372         if (buf)
 373                 ext2fs_free_mem(&buf);
 374         if (handle)
 375                 ext2fs_extent_free(handle);
 376         if ((retval == 0) && (blocks_alloc || inode_dirty)) {
 377                 ext2fs_iblk_add_blocks(fs, inode, blocks_alloc);
 378                 retval = ext2fs_write_inode(fs, ino, inode);
 379         }
 380         return retval;
 381 }
 382
 383 errcode_t ext2fs_bmap(ext2_filsys fs, ext2_ino_t ino, struct ext2_inode *inode,
 384                       char *block_buf, int bmap_flags, blk_t block,
 385                       blk_t *phys_blk)
 386 {
 387         errcode_t ret;
 388         blk64_t ret_blk = *phys_blk;
 389
 390         ret = ext2fs_bmap2(fs, ino, inode, block_buf, bmap_flags, block,
 391                             0, &ret_blk);
 392         if (ret)
 393                 return ret;
 394         if (ret_blk >= ((long long) 1 << 32))
 395                 return EOVERFLOW;
 396         *phys_blk = ret_blk;
 397         return 0;
 398 }