diff options
Diffstat (limited to 'contrib/syslinux-4.02/core/fs/ext2/bmap.c')
| -rw-r--r-- | contrib/syslinux-4.02/core/fs/ext2/bmap.c | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/contrib/syslinux-4.02/core/fs/ext2/bmap.c b/contrib/syslinux-4.02/core/fs/ext2/bmap.c new file mode 100644 index 0000000..ef2bf64 --- /dev/null +++ b/contrib/syslinux-4.02/core/fs/ext2/bmap.c @@ -0,0 +1,228 @@ +/* + * The logical block -> physical block routine. + * + * Copyright (C) 2009 Liu Aleaxander -- All rights reserved. This file + * may be redistributed under the terms of the GNU Public License. + */ + +#include <stdio.h> +#include <dprintf.h> +#include <fs.h> +#include <disk.h> +#include <cache.h> +#include "ext2_fs.h" + +static const struct ext4_extent_header * +ext4_find_leaf(struct fs_info *fs, const struct ext4_extent_header *eh, + block_t block) +{ + struct ext4_extent_idx *index; + block_t blk; + int i; + + while (1) { + if (eh->eh_magic != EXT4_EXT_MAGIC) + return NULL; + if (eh->eh_depth == 0) + return eh; + + index = EXT4_FIRST_INDEX(eh); + for (i = 0; i < (int)eh->eh_entries; i++) { + if (block < index[i].ei_block) + break; + } + if (--i < 0) + return NULL; + + blk = index[i].ei_leaf_hi; + blk = (blk << 32) + index[i].ei_leaf_lo; + eh = get_cache(fs->fs_dev, blk); + } +} + +/* handle the ext4 extents to get the phsical block number */ +/* XXX: still need to handle sparse files with extents */ +static block_t +bmap_extent(struct inode *inode, uint32_t block, size_t *nblocks) +{ + struct fs_info *fs = inode->fs; + const struct ext4_extent_header *leaf; + const struct ext4_extent *ext; + int i; + block_t start; + + leaf = ext4_find_leaf(fs, &PVT(inode)->i_extent_hdr, block); + if (!leaf) { + printf("ERROR, extent leaf not found\n"); + return 0; + } + + ext = EXT4_FIRST_EXTENT(leaf); + for (i = 0; i < leaf->eh_entries; i++) { + if (block < ext[i].ee_block) + break; + } + if (--i < 0) { + printf("ERROR, not find the right block\n"); + return 0; + } + + /* got it */ + block -= ext[i].ee_block; + if (block >= ext[i].ee_len) + return 0; + start = ((block_t)ext[i].ee_start_hi << 32) + ext[i].ee_start_lo; + + if (nblocks) + *nblocks = ext[i].ee_len - block; + + return start + block; +} + +/* + * Scan forward in a range of blocks to see if they are contiguous, + * then return the initial value. + */ +static uint32_t +scan_set_nblocks(const uint32_t *map, unsigned int count, size_t *nblocks) +{ + uint32_t blk = *map; + + if (nblocks) { + uint32_t skip = blk ? 1 : 0; + uint32_t next = blk + skip; + size_t cnt = 1; + + while (--count) { + map++; + if (*map == next) { + cnt++; + next += skip; + } else { + break; + } + } + + *nblocks = cnt; + } + + return blk; +} + +/* + * The actual indirect block map handling - the block passed in should + * be relative to the beginning of the particular block hierarchy. + */ +static block_t +bmap_indirect(struct fs_info *fs, uint32_t start, uint32_t block, + int levels, size_t *nblocks) +{ + int addr_shift = BLOCK_SHIFT(fs) - 2; + uint32_t addr_count = 1 << addr_shift; + const uint32_t *blk = NULL; + uint32_t index = 0; + + while (levels--) { + if (!start) { + if (nblocks) + *nblocks = addr_count << (levels * addr_shift); + return 0; + } + blk = get_cache(fs->fs_dev, start); + index = (block >> (levels * addr_shift)) & (addr_count - 1); + start = blk[index]; + } + + return scan_set_nblocks(blk + index, addr_count - index, nblocks); +} + +/* + * Handle the traditional block map, like indirect, double indirect + * and triple indirect + */ +static block_t +bmap_traditional(struct inode *inode, block_t block, size_t *nblocks) +{ + struct fs_info *fs = inode->fs; + const uint32_t addr_per_block = BLOCK_SIZE(fs) >> 2; + const int shft_per_block = BLOCK_SHIFT(fs) - 2; + const uint32_t direct_blocks = EXT2_NDIR_BLOCKS; + const uint32_t indirect_blocks = addr_per_block; + const uint32_t double_blocks = addr_per_block << shft_per_block; + const uint32_t triple_blocks = double_blocks << shft_per_block; + + /* direct blocks */ + if (block < direct_blocks) + return scan_set_nblocks(&PVT(inode)->i_block[block], + direct_blocks - block, nblocks); + + /* indirect blocks */ + block -= direct_blocks; + if (block < indirect_blocks) + return bmap_indirect(fs, PVT(inode)->i_block[EXT2_IND_BLOCK], + block, 1, nblocks); + + /* double indirect blocks */ + block -= indirect_blocks; + if (block < double_blocks) + return bmap_indirect(fs, PVT(inode)->i_block[EXT2_DIND_BLOCK], + block, 2, nblocks); + + /* triple indirect block */ + block -= double_blocks; + if (block < triple_blocks) + return bmap_indirect(fs, PVT(inode)->i_block[EXT2_TIND_BLOCK], + block, 3, nblocks); + + /* This can't happen... */ + return 0; +} + + +/** + * Map the logical block to physic block where the file data stores. + * In EXT4, there are two ways to handle the map process, extents and indirect. + * EXT4 uses a inode flag to mark extent file and indirect block file. + * + * @fs: the fs_info structure. + * @inode: the inode structure. + * @block: the logical block to be mapped. + * @nblocks: optional pointer to number of contiguous blocks (low estimate) + * @retrun: the physical block number. + * + */ +block_t ext2_bmap(struct inode *inode, block_t block, size_t *nblocks) +{ + block_t ret; + + if (inode->flags & EXT4_EXTENTS_FLAG) + ret = bmap_extent(inode, block, nblocks); + else + ret = bmap_traditional(inode, block, nblocks); + + return ret; +} + + +/* + * Next extent for getfssec + */ +int ext2_next_extent(struct inode *inode, uint32_t lstart) +{ + struct fs_info *fs = inode->fs; + int blktosec = BLOCK_SHIFT(fs) - SECTOR_SHIFT(fs); + int blkmask = (1 << blktosec) - 1; + block_t block; + size_t nblocks = 0; + + block = ext2_bmap(inode, lstart >> blktosec, &nblocks); + + if (!block) + inode->next_extent.pstart = EXTENT_ZERO; + else + inode->next_extent.pstart = + ((sector_t)block << blktosec) | (lstart & blkmask); + + inode->next_extent.len = (nblocks << blktosec) - (lstart & blkmask); + return 0; +} |