core/fs/ext2/bmap.c

   1 /*
   2  * The logical block -> physical block routine.
   3  *
   4  * Copyright (C) 2009 Liu Aleaxander -- All rights reserved. This file
   5  * may be redistributed under the terms of the GNU Public License.
   6  */
   7
   8 #include <stdio.h>
   9 #include <dprintf.h>
  10 #include <fs.h>
  11 #include <disk.h>
  12 #include <cache.h>
  13 #include "ext2_fs.h"
  14
  15 static const struct ext4_extent_header *
  16 ext4_find_leaf(struct fs_info *fs, const struct ext4_extent_header *eh,
  17                block_t block)
  18 {
  19     struct ext4_extent_idx *index;
  20     block_t blk;
  21     int i;
  22
  23     while (1) {
  24         if (eh->eh_magic != EXT4_EXT_MAGIC)
  25             return NULL;
  26         if (eh->eh_depth == 0)
  27             return eh;
  28
  29         index = EXT4_FIRST_INDEX(eh);
  30         for (i = 0; i < (int)eh->eh_entries; i++) {
  31             if (block < index[i].ei_block)
  32                 break;
  33         }
  34         if (--i < 0)
  35             return NULL;
  36
  37         blk = index[i].ei_leaf_hi;
  38         blk = (blk << 32) + index[i].ei_leaf_lo;
  39         eh = get_cache(fs->fs_dev, blk);
  40     }
  41 }
  42
  43 /* handle the ext4 extents to get the phsical block number */
  44 /* XXX: still need to handle sparse files with extents */
  45 static block_t
  46 bmap_extent(struct inode *inode, uint32_t block, size_t *nblocks)
  47 {
  48     struct fs_info *fs = inode->fs;
  49     const struct ext4_extent_header *leaf;
  50     const struct ext4_extent *ext;
  51     int i;
  52     block_t start;
  53
  54     leaf = ext4_find_leaf(fs, &PVT(inode)->i_extent_hdr, block);
  55     if (!leaf) {
  56         printf("ERROR, extent leaf not found\n");
  57         return 0;
  58     }
  59
  60     ext = EXT4_FIRST_EXTENT(leaf);
  61     for (i = 0; i < leaf->eh_entries; i++) {
  62         if (block < ext[i].ee_block)
  63             break;
  64     }
  65     if (--i < 0) {
  66         printf("ERROR, not find the right block\n");
  67         return 0;
  68     }
  69
  70     /* got it */
  71     block -= ext[i].ee_block;
  72     if (block >= ext[i].ee_len)
  73         return 0;
  74     start = ((block_t)ext[i].ee_start_hi << 32) + ext[i].ee_start_lo;
  75
  76     if (nblocks)
  77         *nblocks = ext[i].ee_len - block;
  78
  79     return start + block;
  80 }
  81
  82 /*
  83  * Scan forward in a range of blocks to see if they are contiguous,
  84  * then return the initial value.
  85  */
  86 static uint32_t
  87 scan_set_nblocks(const uint32_t *map, unsigned int count, size_t *nblocks)
  88 {
  89     uint32_t blk = *map;
  90
  91     if (nblocks) {
  92         uint32_t skip = blk ? 1 : 0;
  93         uint32_t next = blk + skip;
  94         size_t   cnt = 1;
  95
  96         while (--count) {
  97             map++;
  98             if (*map == next) {
  99                 cnt++;
 100                 next += skip;
 101             } else {
 102                 break;
 103             }
 104         }
 105
 106         *nblocks = cnt;
 107     }
 108
 109     return blk;
 110 }
 111
 112 /*
 113  * The actual indirect block map handling - the block passed in should
 114  * be relative to the beginning of the particular block hierarchy.
 115  */
 116 static block_t
 117 bmap_indirect(struct fs_info *fs, uint32_t start, uint32_t block,
 118               int levels, size_t *nblocks)
 119 {
 120     int addr_shift = BLOCK_SHIFT(fs) - 2;
 121     uint32_t addr_count = 1 << addr_shift;
 122     const uint32_t *blk = NULL;
 123     uint32_t index = 0;
 124
 125     while (levels--) {
 126         if (!start) {
 127             if (nblocks)
 128                 *nblocks = addr_count << (levels * addr_shift);
 129             return 0;
 130         }
 131         blk = get_cache(fs->fs_dev, start);
 132         index = (block >> (levels * addr_shift)) & (addr_count - 1);
 133         start = blk[index];
 134     }
 135
 136     return scan_set_nblocks(blk + index, addr_count - index, nblocks);
 137 }
 138
 139 /*
 140  * Handle the traditional block map, like indirect, double indirect
 141  * and triple indirect
 142  */
 143 static block_t
 144 bmap_traditional(struct inode *inode, block_t block, size_t *nblocks)
 145 {
 146     struct fs_info *fs = inode->fs;
 147     const uint32_t addr_per_block = BLOCK_SIZE(fs) >> 2;
 148     const int shft_per_block      = BLOCK_SHIFT(fs) - 2;
 149     const uint32_t direct_blocks   = EXT2_NDIR_BLOCKS;
 150     const uint32_t indirect_blocks = addr_per_block;
 151     const uint32_t double_blocks   = addr_per_block << shft_per_block;
 152     const uint32_t triple_blocks   = double_blocks  << shft_per_block;
 153
 154     /* direct blocks */
 155     if (block < direct_blocks)
 156         return scan_set_nblocks(&PVT(inode)->i_block[block],
 157                                 direct_blocks - block, nblocks);
 158
 159     /* indirect blocks */
 160     block -= direct_blocks;
 161     if (block < indirect_blocks)
 162         return bmap_indirect(fs, PVT(inode)->i_block[EXT2_IND_BLOCK],
 163                              block, 1, nblocks);
 164
 165     /* double indirect blocks */
 166     block -= indirect_blocks;
 167     if (block < double_blocks)
 168         return bmap_indirect(fs, PVT(inode)->i_block[EXT2_DIND_BLOCK],
 169                              block, 2, nblocks);
 170
 171     /* triple indirect block */
 172     block -= double_blocks;
 173     if (block < triple_blocks)
 174         return bmap_indirect(fs, PVT(inode)->i_block[EXT2_TIND_BLOCK],
 175                              block, 3, nblocks);
 176
 177     /* This can't happen... */
 178     return 0;
 179 }
 180
 181
 182 /**
 183  * Map the logical block to physic block where the file data stores.
 184  * In EXT4, there are two ways to handle the map process, extents and indirect.
 185  * EXT4 uses a inode flag to mark extent file and indirect block file.
 186  *
 187  * @fs:      the fs_info structure.
 188  * @inode:   the inode structure.
 189  * @block:   the logical block to be mapped.
 190  * @nblocks: optional pointer to number of contiguous blocks (low estimate)
 191  * @retrun:  the physical block number.
 192  *
 193  */
 194 block_t ext2_bmap(struct inode *inode, block_t block, size_t *nblocks)
 195 {
 196     block_t ret;
 197
 198     if (inode->flags & EXT4_EXTENTS_FLAG)
 199         ret = bmap_extent(inode, block, nblocks);
 200     else
 201         ret = bmap_traditional(inode, block, nblocks);
 202
 203     return ret;
 204 }
 205
 206
 207 /*
 208  * Next extent for getfssec
 209  */
 210 int ext2_next_extent(struct inode *inode, uint32_t lstart)
 211 {
 212     struct fs_info *fs = inode->fs;
 213     int blktosec =  BLOCK_SHIFT(fs) - SECTOR_SHIFT(fs);
 214     int blkmask = (1 << blktosec) - 1;
 215     block_t block;
 216     size_t nblocks = 0;
 217
 218     block = ext2_bmap(inode, lstart >> blktosec, &nblocks);
 219
 220     if (!block)
 221         inode->next_extent.pstart = EXTENT_ZERO;
 222     else
 223         inode->next_extent.pstart =
 224             ((sector_t)block << blktosec) | (lstart & blkmask);
 225
 226     inode->next_extent.len = (nblocks << blktosec) - (lstart & blkmask);
 227     return 0;
 228 }