source: bootcd/isolinux/syslinux-6.03/core/fs/ext2/bmap.c

/*
 * 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;
}