From: Alex Tomas Subject: [RFC] ext4-extents-search-routines patch Date: Fri, 01 Dec 2006 02:51:46 +0300 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Return-path: Received: from [80.71.248.82] ([80.71.248.82]:14800 "EHLO gw.home.net") by vger.kernel.org with ESMTP id S1031636AbWLAASC (ORCPT ); Thu, 30 Nov 2006 19:18:02 -0500 Received: from bzzz.home.net (gw.home.net [127.0.0.1]) by gw.home.net (8.13.7/8.13.4) with ESMTP id kB11JJYZ005496 for ; Fri, 1 Dec 2006 04:19:19 +0300 To: linux-ext4@vger.kernel.org Sender: linux-ext4-owner@vger.kernel.org List-Id: linux-ext4.vger.kernel.org the couple routines to find closest allocated blocks to the left and to the right for given path. thanks, Alex Index: linux-2.6.19-rc6/include/linux/ext4_fs_extents.h =================================================================== --- linux-2.6.19-rc6.orig/include/linux/ext4_fs_extents.h 2006-11-16 07:03:40.000000000 +0300 +++ linux-2.6.19-rc6/include/linux/ext4_fs_extents.h 2006-11-28 23:38:54.000000000 +0300 @@ -193,6 +193,8 @@ extern int ext4_ext_calc_credits_for_ins extern int ext4_ext_insert_extent(handle_t *, struct inode *, struct ext4_ext_path *, struct ext4_extent *); extern int ext4_ext_walk_space(struct inode *, unsigned long, unsigned long, ext_prepare_callback, void *); extern struct ext4_ext_path * ext4_ext_find_extent(struct inode *, int, struct ext4_ext_path *); +extern int ext4_ext_search_left(struct inode *, struct ext4_ext_path *, ext4_fsblk_t *, ext4_fsblk_t *); +extern int ext4_ext_search_right(struct inode *, struct ext4_ext_path *, ext4_fsblk_t *, ext4_fsblk_t *); #endif /* _LINUX_EXT4_EXTENTS */ Index: linux-2.6.19-rc6/fs/ext4/extents.c =================================================================== --- linux-2.6.19-rc6.orig/fs/ext4/extents.c 2006-11-16 07:03:40.000000000 +0300 +++ linux-2.6.19-rc6/fs/ext4/extents.c 2006-11-28 23:40:25.000000000 +0300 @@ -974,6 +974,148 @@ out: } /* + * search the closest allocated block to the left for *logical + * and returns it at @logical + it's physical address at @phys + * if *logical is the smallest allocated block, the function + * returns 0 at @phys + * return value contains 0 (success) or error code + */ +int +ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path, + ext4_fsblk_t *logical, ext4_fsblk_t *phys) +{ + struct ext4_extent_idx *ix; + struct ext4_extent *ex; + int depth; + + BUG_ON(path == NULL); + depth = path->p_depth; + *phys = 0; + + if (depth == 0 && path->p_ext == NULL) + return 0; + + /* usually extent in the path covers blocks smaller + * then *logical, but it can be that extent is the + * first one in the file */ + + ex = path[depth].p_ext; + if (*logical < le32_to_cpu(ex->ee_block)) { + BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex); + while (--depth >= 0) { + ix = path[depth].p_idx; + BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr)); + } + return 0; + } + + BUG_ON(*logical < le32_to_cpu(ex->ee_block) + le16_to_cpu(ex->ee_len)); + + *logical = le32_to_cpu(ex->ee_block) + le16_to_cpu(ex->ee_len) - 1; + *phys = ext_pblock(ex) + le16_to_cpu(ex->ee_len) - 1; + return 0; +} + +/* + * search the closest allocated block to the right for *logical + * and returns it at @logical + it's physical address at @phys + * if *logical is the smallest allocated block, the function + * returns 0 at @phys + * return value contains 0 (success) or error code + */ +int +ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path, + ext4_fsblk_t *logical, ext4_fsblk_t *phys) +{ + struct buffer_head *bh = NULL; + struct ext4_extent_header *eh; + struct ext4_extent_idx *ix; + struct ext4_extent *ex; + ext4_fsblk_t block; + int depth; + + BUG_ON(path == NULL); + depth = path->p_depth; + *phys = 0; + + if (depth == 0 && path->p_ext == NULL) + return 0; + + /* usually extent in the path covers blocks smaller + * then *logical, but it can be that extent is the + * first one in the file */ + + ex = path[depth].p_ext; + if (*logical < le32_to_cpu(ex->ee_block)) { + BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex); + while (--depth >= 0) { + ix = path[depth].p_idx; + BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr)); + } + *logical = le32_to_cpu(ex->ee_block); + *phys = ext_pblock(ex); + return 0; + } + + BUG_ON(*logical < le32_to_cpu(ex->ee_block) + le16_to_cpu(ex->ee_len)); + + if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) { + /* next allocated block in this leaf */ + ex++; + *logical = le32_to_cpu(ex->ee_block); + *phys = ext_pblock(ex); + return 0; + } + + /* go up and search for index to the right */ + while (--depth >= 0) { + ix = path[depth].p_idx; + if (ix != EXT_LAST_INDEX(path[depth].p_hdr)) + break; + } + + if (depth < 0) { + /* we've gone up to the root and + * found no index to the right */ + return 0; + } + + /* we've found index to the right, let's + * follow it and find the closest allocated + * block to the right */ + ix++; + block = idx_pblock(ix); + while (++depth < path->p_depth) { + bh = sb_bread(inode->i_sb, block); + if (bh == NULL) + return -EIO; + eh = ext_block_hdr(bh); + if (ext4_ext_check_header(__FUNCTION__, inode, eh)) { + brelse(bh); + return -EIO; + } + ix = EXT_FIRST_INDEX(eh); + block = idx_pblock(ix); + brelse(bh); + } + + bh = sb_bread(inode->i_sb, block); + if (bh == NULL) + return -EIO; + eh = ext_block_hdr(bh); + if (ext4_ext_check_header(__FUNCTION__, inode, eh)) { + brelse(bh); + return -EIO; + } + ex = EXT_FIRST_EXTENT(eh); + *logical = le32_to_cpu(ex->ee_block); + *phys = ext_pblock(ex); + brelse(bh); + return 0; + +} + +/* * ext4_ext_next_allocated_block: * returns allocated block in subsequent extent or EXT_MAX_BLOCK. * NOTE: it considers block number from index entry as