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

/*
 * Copyright (C) 2013 Raphael S. Carvalho <raphael.scarv@gmail.com>
 *
 * Partially taken from fs/ext2/bmap.c
 * This file was modified according UFS1/2 needs.
 *
 * 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 "ufs.h"

/*
 * Copy blk address into buffer, this was needed since UFS1/2 addr size
 * in blk maps differs from each other (32/64 bits respectivelly).
 */
static inline uint64_t
get_blkaddr (const uint8_t *blk, uint32_t index, uint32_t shift)
{
    uint64_t addr = 0;

    memcpy((uint8_t *) &addr,
           (uint8_t *) blk + (index << shift),
            1 << shift);

    return addr;
}

/*
 * Scan forward in a range of blocks to see if they are contiguous,
 * then return the initial value.
 */
static uint64_t
scan_set_nblocks(const uint8_t *map, uint32_t index, uint32_t addr_shift,
                  unsigned int count, size_t *nblocks)
{
    uint64_t addr;
    uint64_t blk = get_blkaddr(map, index, addr_shift);

    /*
     * Block spans 8 fragments, then address is interleaved by 8.
     * This code works for either 32/64 sized addresses.
     */
    if (nblocks) {
        uint32_t skip = blk ? FRAGMENTS_PER_BLK : 0;
        uint32_t next = blk + skip;
        size_t   cnt = 1;

        /* Get address of starting blk pointer */
        map += (index << addr_shift);

        ufs_debug("[scan] start blk: %u\n", blk);
        ufs_debug("[scan] count (nr of blks): %u\n", count);
        /* Go up to the end of blk map */
        while (--count) {
            map += 1 << addr_shift;
            addr = get_blkaddr(map, 0, addr_shift);
#if 0
            /* Extra debugging info (Too much prints) */
            ufs_debug("[scan] addr: %u next: %u\n", addr, next);
#endif
            if (addr == next) {
                cnt++;
                next += skip;
            } else {
                break;
            }
        }
        *nblocks = cnt;
        ufs_debug("[scan] nblocks: %u\n", cnt);
        ufs_debug("[scan] end blk: %u\n", next - FRAGMENTS_PER_BLK);
    }

    return blk;
}

/*
 * The actual indirect block map handling - the block passed in should
 * be relative to the beginning of the particular block hierarchy.
 *
 * @shft_per_blk: shift to get nr. of addresses in a block.
 * @mask_per_blk: mask to limit the max nr. of addresses in a block.
 * @addr_count:   nr. of addresses in a block.
 */
static uint64_t
bmap_indirect(struct fs_info *fs, uint64_t start, uint32_t block,
              int levels, size_t *nblocks)
{
    uint32_t shft_per_blk = fs->block_shift - UFS_SB(fs)->addr_shift;
    uint32_t addr_count = (1 << shft_per_blk);
    uint32_t mask_per_blk = addr_count - 1;
    const uint8_t *blk = NULL;
    uint32_t index = 0;

    while (levels--) {
        if (!start) {
            if (nblocks)
                *nblocks = addr_count << (levels * shft_per_blk);
            return 0;
        }

        blk = get_cache(fs->fs_dev, frag_to_blk(fs, start));
        index = (block >> (levels * shft_per_blk)) & mask_per_blk;
        start = get_blkaddr(blk, index, UFS_SB(fs)->addr_shift);
    }

    return scan_set_nblocks(blk, index, UFS_SB(fs)->addr_shift,
                            addr_count - index, nblocks);
}

/*
 * Handle the traditional block map, like indirect, double indirect
 * and triple indirect
 */
uint64_t ufs_bmap (struct inode *inode, block_t block, size_t *nblocks)
{
    uint32_t shft_per_blk, ptrs_per_blk;
    static uint32_t indir_blks, double_blks, triple_blks;
    struct fs_info *fs = inode->fs;

    /* Initialize static values */
    if (!indir_blks) {
        shft_per_blk = fs->block_shift - UFS_SB(fs)->addr_shift;
        ptrs_per_blk = fs->block_size >> UFS_SB(fs)->addr_shift;

        indir_blks = ptrs_per_blk;
        double_blks = ptrs_per_blk << shft_per_blk;
        triple_blks = double_blks << shft_per_blk;
    }

    /*
     * direct blocks
     * (UFS2_ADDR_SHIFT) is also used for UFS1 because its direct ptr array
     * was extended to 64 bits.
     */
    if (block < UFS_DIRECT_BLOCKS)
        return scan_set_nblocks((uint8_t *) PVT(inode)->direct_blk_ptr,
                                block, UFS2_ADDR_SHIFT,
                                UFS_DIRECT_BLOCKS - block, nblocks);

    /* indirect blocks */
    block -= UFS_DIRECT_BLOCKS;
    if (block < indir_blks)
        return bmap_indirect(fs, PVT(inode)->indirect_blk_ptr,
                             block, 1, nblocks);

    /* double indirect blocks */
    block -= indir_blks;
    if (block < double_blks)
        return bmap_indirect(fs, PVT(inode)->double_indirect_blk_ptr,
                             block, 2, nblocks);

    /* triple indirect blocks */
    block -= double_blks;
    if (block < triple_blks)
        return bmap_indirect(fs, PVT(inode)->triple_indirect_blk_ptr,
                             block, 3, nblocks);

    /* This can't happen... */
    return 0;
}

/*
 * Next extent for getfssec
 * "Remaining sectors" means (lstart & blkmask).
 */
int ufs_next_extent(struct inode *inode, uint32_t lstart)
{
    struct fs_info *fs = inode->fs;
    int blktosec =  BLOCK_SHIFT(fs) - SECTOR_SHIFT(fs);
    int frag_shift = BLOCK_SHIFT(fs) - UFS_SB(fs)->c_blk_frag_shift;
    int blkmask = (1 << blktosec) - 1;
    block_t block;
    size_t nblocks = 0;

    ufs_debug("ufs_next_extent:\n");
    block = ufs_bmap(inode, lstart >> blktosec, &nblocks);
    ufs_debug("blk: %u\n", block);

    if (!block) // Sparse block
        inode->next_extent.pstart = EXTENT_ZERO;
    else
        /*
         * Convert blk into sect addr and add the remaining
         * sectors into pstart (sector start address).
         */
        inode->next_extent.pstart =
            ((sector_t) (block << (frag_shift - SECTOR_SHIFT(fs)))) |
            (lstart & blkmask);

    /*
     * Subtract the remaining sectors from len since these sectors
     * were added to pstart (sector start address).
     */
    inode->next_extent.len = (nblocks << blktosec) - (lstart & blkmask);
    return 0;
}