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