aboutsummaryrefslogtreecommitdiffstats
path: root/fs/ext4
diff options
context:
space:
mode:
authorAlex Tomas <alex@clusterfs.com>2008-01-28 23:58:27 -0500
committerTheodore Ts'o <tytso@mit.edu>2008-01-28 23:58:27 -0500
commit1988b51e476bd097d910c9245b53f2e38aedaf0d (patch)
treea36b860ac1a49b359d6dc5fd7af9916cf034cac8 /fs/ext4
parentaa02ad67d9b308290fde390682cd039b29f7ab85 (diff)
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 <alex@clusterfs.com> Signed-off-by: Andreas Dilger <adilger@clusterfs.com> Signed-off-by: Johann Lombardi <johann@clusterfs.com> Signed-off-by: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Diffstat (limited to 'fs/ext4')
-rw-r--r--fs/ext4/extents.c142
1 files changed, 142 insertions, 0 deletions
diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index 01eda5c5281e..f5cf2a94b6fc 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -1017,6 +1017,148 @@ out:
1017} 1017}
1018 1018
1019/* 1019/*
1020 * search the closest allocated block to the left for *logical
1021 * and returns it at @logical + it's physical address at @phys
1022 * if *logical is the smallest allocated block, the function
1023 * returns 0 at @phys
1024 * return value contains 0 (success) or error code
1025 */
1026int
1027ext4_ext_search_left(struct inode *inode, struct ext4_ext_path *path,
1028 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1029{
1030 struct ext4_extent_idx *ix;
1031 struct ext4_extent *ex;
1032 int depth;
1033
1034 BUG_ON(path == NULL);
1035 depth = path->p_depth;
1036 *phys = 0;
1037
1038 if (depth == 0 && path->p_ext == NULL)
1039 return 0;
1040
1041 /* usually extent in the path covers blocks smaller
1042 * then *logical, but it can be that extent is the
1043 * first one in the file */
1044
1045 ex = path[depth].p_ext;
1046 if (*logical < le32_to_cpu(ex->ee_block)) {
1047 BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
1048 while (--depth >= 0) {
1049 ix = path[depth].p_idx;
1050 BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
1051 }
1052 return 0;
1053 }
1054
1055 BUG_ON(*logical < le32_to_cpu(ex->ee_block) + le16_to_cpu(ex->ee_len));
1056
1057 *logical = le32_to_cpu(ex->ee_block) + le16_to_cpu(ex->ee_len) - 1;
1058 *phys = ext_pblock(ex) + le16_to_cpu(ex->ee_len) - 1;
1059 return 0;
1060}
1061
1062/*
1063 * search the closest allocated block to the right for *logical
1064 * and returns it at @logical + it's physical address at @phys
1065 * if *logical is the smallest allocated block, the function
1066 * returns 0 at @phys
1067 * return value contains 0 (success) or error code
1068 */
1069int
1070ext4_ext_search_right(struct inode *inode, struct ext4_ext_path *path,
1071 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1072{
1073 struct buffer_head *bh = NULL;
1074 struct ext4_extent_header *eh;
1075 struct ext4_extent_idx *ix;
1076 struct ext4_extent *ex;
1077 ext4_fsblk_t block;
1078 int depth;
1079
1080 BUG_ON(path == NULL);
1081 depth = path->p_depth;
1082 *phys = 0;
1083
1084 if (depth == 0 && path->p_ext == NULL)
1085 return 0;
1086
1087 /* usually extent in the path covers blocks smaller
1088 * then *logical, but it can be that extent is the
1089 * first one in the file */
1090
1091 ex = path[depth].p_ext;
1092 if (*logical < le32_to_cpu(ex->ee_block)) {
1093 BUG_ON(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex);
1094 while (--depth >= 0) {
1095 ix = path[depth].p_idx;
1096 BUG_ON(ix != EXT_FIRST_INDEX(path[depth].p_hdr));
1097 }
1098 *logical = le32_to_cpu(ex->ee_block);
1099 *phys = ext_pblock(ex);
1100 return 0;
1101 }
1102
1103 BUG_ON(*logical < le32_to_cpu(ex->ee_block) + le16_to_cpu(ex->ee_len));
1104
1105 if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1106 /* next allocated block in this leaf */
1107 ex++;
1108 *logical = le32_to_cpu(ex->ee_block);
1109 *phys = ext_pblock(ex);
1110 return 0;
1111 }
1112
1113 /* go up and search for index to the right */
1114 while (--depth >= 0) {
1115 ix = path[depth].p_idx;
1116 if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
1117 break;
1118 }
1119
1120 if (depth < 0) {
1121 /* we've gone up to the root and
1122 * found no index to the right */
1123 return 0;
1124 }
1125
1126 /* we've found index to the right, let's
1127 * follow it and find the closest allocated
1128 * block to the right */
1129 ix++;
1130 block = idx_pblock(ix);
1131 while (++depth < path->p_depth) {
1132 bh = sb_bread(inode->i_sb, block);
1133 if (bh == NULL)
1134 return -EIO;
1135 eh = ext_block_hdr(bh);
1136 if (ext4_ext_check_header(inode, eh, depth)) {
1137 put_bh(bh);
1138 return -EIO;
1139 }
1140 ix = EXT_FIRST_INDEX(eh);
1141 block = idx_pblock(ix);
1142 put_bh(bh);
1143 }
1144
1145 bh = sb_bread(inode->i_sb, block);
1146 if (bh == NULL)
1147 return -EIO;
1148 eh = ext_block_hdr(bh);
1149 if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) {
1150 put_bh(bh);
1151 return -EIO;
1152 }
1153 ex = EXT_FIRST_EXTENT(eh);
1154 *logical = le32_to_cpu(ex->ee_block);
1155 *phys = ext_pblock(ex);
1156 put_bh(bh);
1157 return 0;
1158
1159}
1160
1161/*
1020 * ext4_ext_next_allocated_block: 1162 * ext4_ext_next_allocated_block:
1021 * returns allocated block in subsequent extent or EXT_MAX_BLOCK. 1163 * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1022 * NOTE: it considers block number from index entry as 1164 * NOTE: it considers block number from index entry as