Gitweb:     
http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=1988b51e476bd097d910c9245b53f2e38aedaf0d
Commit:     1988b51e476bd097d910c9245b53f2e38aedaf0d
Parent:     aa02ad67d9b308290fde390682cd039b29f7ab85
Author:     Alex Tomas <[EMAIL PROTECTED]>
AuthorDate: Mon Jan 28 23:58:27 2008 -0500
Committer:  Theodore Ts'o <[EMAIL PROTECTED]>
CommitDate: Mon Jan 28 23:58:27 2008 -0500

    ext4: Add new functions for searching extent tree
    
    Add the functions ext4_ext_search_left() and ext4_ext_search_right(),
    which are used by mballoc during ext4_ext_get_blocks to decided whether
    to merge extent information.
    
    Signed-off-by: Alex Tomas <[EMAIL PROTECTED]>
    Signed-off-by: Andreas Dilger <[EMAIL PROTECTED]>
    Signed-off-by: Johann Lombardi <[EMAIL PROTECTED]>
    Signed-off-by: Aneesh Kumar K.V <[EMAIL PROTECTED]>
    Signed-off-by: "Theodore Ts'o" <[EMAIL PROTECTED]>
---
 fs/ext4/extents.c               |  142 +++++++++++++++++++++++++++++++++++++++
 include/linux/ext4_fs_extents.h |    4 +
 2 files changed, 146 insertions(+), 0 deletions(-)

diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index 01eda5c..f5cf2a9 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -1017,6 +1017,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_lblk_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_lblk_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(inode, eh, depth)) {
+                       put_bh(bh);
+                       return -EIO;
+               }
+               ix = EXT_FIRST_INDEX(eh);
+               block = idx_pblock(ix);
+               put_bh(bh);
+       }
+
+       bh = sb_bread(inode->i_sb, block);
+       if (bh == NULL)
+               return -EIO;
+       eh = ext_block_hdr(bh);
+       if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) {
+               put_bh(bh);
+               return -EIO;
+       }
+       ex = EXT_FIRST_EXTENT(eh);
+       *logical = le32_to_cpu(ex->ee_block);
+       *phys = ext_pblock(ex);
+       put_bh(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
diff --git a/include/linux/ext4_fs_extents.h b/include/linux/ext4_fs_extents.h
index 1cfb485..697da4b 100644
--- a/include/linux/ext4_fs_extents.h
+++ b/include/linux/ext4_fs_extents.h
@@ -223,5 +223,9 @@ extern unsigned int ext4_ext_check_overlap(struct inode *, 
struct ext4_extent *,
 extern int ext4_ext_insert_extent(handle_t *, struct inode *, struct 
ext4_ext_path *, struct ext4_extent *);
 extern struct ext4_ext_path *ext4_ext_find_extent(struct inode *, ext4_lblk_t,
                                                        struct ext4_ext_path *);
+extern int ext4_ext_search_left(struct inode *, struct ext4_ext_path *,
+                                               ext4_lblk_t *, ext4_fsblk_t *);
+extern int ext4_ext_search_right(struct inode *, struct ext4_ext_path *,
+                                               ext4_lblk_t *, ext4_fsblk_t *);
 #endif /* _LINUX_EXT4_EXTENTS */
 
-
To unsubscribe from this list: send the line "unsubscribe git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to