| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1200970948-17903-41-git-send-email-tytso@mit.edu>
Date: Mon, 21 Jan 2008 22:02:19 -0500
From: "Theodore Ts'o" <tytso@....EDU>
To: linux-kernel@...r.kernel.org
Cc: Alex Tomas <alex@...sterfs.com>,
Andreas Dilger <adilger@...sterfs.com>,
Johann Lombardi <johann@...sterfs.com>,
"Aneesh Kumar K.V" <aneesh.kumar@...ux.vnet.ibm.com>,
"Theodore Ts'o" <tytso@....edu>
Subject: [PATCH 40/49] ext4: Add new functions for searching extent tree
From: Alex Tomas <alex@...sterfs.com>
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 <alex@...sterfs.com>
Signed-off-by: Andreas Dilger <adilger@...sterfs.com>
Signed-off-by: Johann Lombardi <johann@...sterfs.com>
Signed-off-by: Aneesh Kumar K.V <aneesh.kumar@...ux.vnet.ibm.com>
Signed-off-by: "Theodore Ts'o" <tytso@....edu>
---
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 03d1bbb..a60227c 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)) {
+ 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(inode, eh, path->p_depth - depth)) {
+ 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
diff --git a/include/linux/ext4_fs_extents.h b/include/linux/ext4_fs_extents.h
index 023683b..56d0ec6 100644
--- a/include/linux/ext4_fs_extents.h
+++ b/include/linux/ext4_fs_extents.h
@@ -221,5 +221,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 */
--
1.5.4.rc3.31.g1271-dirty
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists