diff options
-rw-r--r-- | fs/ext3/namei.c | 39 | ||||
-rw-r--r-- | fs/ext4/namei.c | 39 |
2 files changed, 70 insertions, 8 deletions
diff --git a/fs/ext3/namei.c b/fs/ext3/namei.c index 9d4a89820e1e..c1fa1908dba0 100644 --- a/fs/ext3/namei.c +++ b/fs/ext3/namei.c | |||
@@ -140,7 +140,8 @@ struct dx_frame | |||
140 | struct dx_map_entry | 140 | struct dx_map_entry |
141 | { | 141 | { |
142 | u32 hash; | 142 | u32 hash; |
143 | u32 offs; | 143 | u16 offs; |
144 | u16 size; | ||
144 | }; | 145 | }; |
145 | 146 | ||
146 | #ifdef CONFIG_EXT3_INDEX | 147 | #ifdef CONFIG_EXT3_INDEX |
@@ -697,6 +698,10 @@ errout: | |||
697 | * Directory block splitting, compacting | 698 | * Directory block splitting, compacting |
698 | */ | 699 | */ |
699 | 700 | ||
701 | /* | ||
702 | * Create map of hash values, offsets, and sizes, stored at end of block. | ||
703 | * Returns number of entries mapped. | ||
704 | */ | ||
700 | static int dx_make_map (struct ext3_dir_entry_2 *de, int size, | 705 | static int dx_make_map (struct ext3_dir_entry_2 *de, int size, |
701 | struct dx_hash_info *hinfo, struct dx_map_entry *map_tail) | 706 | struct dx_hash_info *hinfo, struct dx_map_entry *map_tail) |
702 | { | 707 | { |
@@ -710,7 +715,8 @@ static int dx_make_map (struct ext3_dir_entry_2 *de, int size, | |||
710 | ext3fs_dirhash(de->name, de->name_len, &h); | 715 | ext3fs_dirhash(de->name, de->name_len, &h); |
711 | map_tail--; | 716 | map_tail--; |
712 | map_tail->hash = h.hash; | 717 | map_tail->hash = h.hash; |
713 | map_tail->offs = (u32) ((char *) de - base); | 718 | map_tail->offs = (u16) ((char *) de - base); |
719 | map_tail->size = le16_to_cpu(de->rec_len); | ||
714 | count++; | 720 | count++; |
715 | cond_resched(); | 721 | cond_resched(); |
716 | } | 722 | } |
@@ -720,6 +726,7 @@ static int dx_make_map (struct ext3_dir_entry_2 *de, int size, | |||
720 | return count; | 726 | return count; |
721 | } | 727 | } |
722 | 728 | ||
729 | /* Sort map by hash value */ | ||
723 | static void dx_sort_map (struct dx_map_entry *map, unsigned count) | 730 | static void dx_sort_map (struct dx_map_entry *map, unsigned count) |
724 | { | 731 | { |
725 | struct dx_map_entry *p, *q, *top = map + count - 1; | 732 | struct dx_map_entry *p, *q, *top = map + count - 1; |
@@ -1117,6 +1124,10 @@ static inline void ext3_set_de_type(struct super_block *sb, | |||
1117 | } | 1124 | } |
1118 | 1125 | ||
1119 | #ifdef CONFIG_EXT3_INDEX | 1126 | #ifdef CONFIG_EXT3_INDEX |
1127 | /* | ||
1128 | * Move count entries from end of map between two memory locations. | ||
1129 | * Returns pointer to last entry moved. | ||
1130 | */ | ||
1120 | static struct ext3_dir_entry_2 * | 1131 | static struct ext3_dir_entry_2 * |
1121 | dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) | 1132 | dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) |
1122 | { | 1133 | { |
@@ -1135,6 +1146,10 @@ dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) | |||
1135 | return (struct ext3_dir_entry_2 *) (to - rec_len); | 1146 | return (struct ext3_dir_entry_2 *) (to - rec_len); |
1136 | } | 1147 | } |
1137 | 1148 | ||
1149 | /* | ||
1150 | * Compact each dir entry in the range to the minimal rec_len. | ||
1151 | * Returns pointer to last entry in range. | ||
1152 | */ | ||
1138 | static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size) | 1153 | static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size) |
1139 | { | 1154 | { |
1140 | struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base; | 1155 | struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base; |
@@ -1157,6 +1172,11 @@ static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size) | |||
1157 | return prev; | 1172 | return prev; |
1158 | } | 1173 | } |
1159 | 1174 | ||
1175 | /* | ||
1176 | * Split a full leaf block to make room for a new dir entry. | ||
1177 | * Allocate a new block, and move entries so that they are approx. equally full. | ||
1178 | * Returns pointer to de in block into which the new entry will be inserted. | ||
1179 | */ | ||
1160 | static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, | 1180 | static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, |
1161 | struct buffer_head **bh,struct dx_frame *frame, | 1181 | struct buffer_head **bh,struct dx_frame *frame, |
1162 | struct dx_hash_info *hinfo, int *error) | 1182 | struct dx_hash_info *hinfo, int *error) |
@@ -1168,7 +1188,7 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, | |||
1168 | u32 hash2; | 1188 | u32 hash2; |
1169 | struct dx_map_entry *map; | 1189 | struct dx_map_entry *map; |
1170 | char *data1 = (*bh)->b_data, *data2; | 1190 | char *data1 = (*bh)->b_data, *data2; |
1171 | unsigned split; | 1191 | unsigned split, move, size, i; |
1172 | struct ext3_dir_entry_2 *de = NULL, *de2; | 1192 | struct ext3_dir_entry_2 *de = NULL, *de2; |
1173 | int err = 0; | 1193 | int err = 0; |
1174 | 1194 | ||
@@ -1196,8 +1216,19 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, | |||
1196 | count = dx_make_map ((struct ext3_dir_entry_2 *) data1, | 1216 | count = dx_make_map ((struct ext3_dir_entry_2 *) data1, |
1197 | blocksize, hinfo, map); | 1217 | blocksize, hinfo, map); |
1198 | map -= count; | 1218 | map -= count; |
1199 | split = count/2; // need to adjust to actual middle | ||
1200 | dx_sort_map (map, count); | 1219 | dx_sort_map (map, count); |
1220 | /* Split the existing block in the middle, size-wise */ | ||
1221 | size = 0; | ||
1222 | move = 0; | ||
1223 | for (i = count-1; i >= 0; i--) { | ||
1224 | /* is more than half of this entry in 2nd half of the block? */ | ||
1225 | if (size + map[i].size/2 > blocksize/2) | ||
1226 | break; | ||
1227 | size += map[i].size; | ||
1228 | move++; | ||
1229 | } | ||
1230 | /* map index at which we will split */ | ||
1231 | split = count - move; | ||
1201 | hash2 = map[split].hash; | 1232 | hash2 = map[split].hash; |
1202 | continued = hash2 == map[split - 1].hash; | 1233 | continued = hash2 == map[split - 1].hash; |
1203 | dxtrace(printk("Split block %i at %x, %i/%i\n", | 1234 | dxtrace(printk("Split block %i at %x, %i/%i\n", |
diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c index 9468289637a5..5fdb862e71c4 100644 --- a/fs/ext4/namei.c +++ b/fs/ext4/namei.c | |||
@@ -140,7 +140,8 @@ struct dx_frame | |||
140 | struct dx_map_entry | 140 | struct dx_map_entry |
141 | { | 141 | { |
142 | u32 hash; | 142 | u32 hash; |
143 | u32 offs; | 143 | u16 offs; |
144 | u16 size; | ||
144 | }; | 145 | }; |
145 | 146 | ||
146 | #ifdef CONFIG_EXT4_INDEX | 147 | #ifdef CONFIG_EXT4_INDEX |
@@ -697,6 +698,10 @@ errout: | |||
697 | * Directory block splitting, compacting | 698 | * Directory block splitting, compacting |
698 | */ | 699 | */ |
699 | 700 | ||
701 | /* | ||
702 | * Create map of hash values, offsets, and sizes, stored at end of block. | ||
703 | * Returns number of entries mapped. | ||
704 | */ | ||
700 | static int dx_make_map (struct ext4_dir_entry_2 *de, int size, | 705 | static int dx_make_map (struct ext4_dir_entry_2 *de, int size, |
701 | struct dx_hash_info *hinfo, struct dx_map_entry *map_tail) | 706 | struct dx_hash_info *hinfo, struct dx_map_entry *map_tail) |
702 | { | 707 | { |
@@ -710,7 +715,8 @@ static int dx_make_map (struct ext4_dir_entry_2 *de, int size, | |||
710 | ext4fs_dirhash(de->name, de->name_len, &h); | 715 | ext4fs_dirhash(de->name, de->name_len, &h); |
711 | map_tail--; | 716 | map_tail--; |
712 | map_tail->hash = h.hash; | 717 | map_tail->hash = h.hash; |
713 | map_tail->offs = (u32) ((char *) de - base); | 718 | map_tail->offs = (u16) ((char *) de - base); |
719 | map_tail->size = le16_to_cpu(de->rec_len); | ||
714 | count++; | 720 | count++; |
715 | cond_resched(); | 721 | cond_resched(); |
716 | } | 722 | } |
@@ -720,6 +726,7 @@ static int dx_make_map (struct ext4_dir_entry_2 *de, int size, | |||
720 | return count; | 726 | return count; |
721 | } | 727 | } |
722 | 728 | ||
729 | /* Sort map by hash value */ | ||
723 | static void dx_sort_map (struct dx_map_entry *map, unsigned count) | 730 | static void dx_sort_map (struct dx_map_entry *map, unsigned count) |
724 | { | 731 | { |
725 | struct dx_map_entry *p, *q, *top = map + count - 1; | 732 | struct dx_map_entry *p, *q, *top = map + count - 1; |
@@ -1115,6 +1122,10 @@ static inline void ext4_set_de_type(struct super_block *sb, | |||
1115 | } | 1122 | } |
1116 | 1123 | ||
1117 | #ifdef CONFIG_EXT4_INDEX | 1124 | #ifdef CONFIG_EXT4_INDEX |
1125 | /* | ||
1126 | * Move count entries from end of map between two memory locations. | ||
1127 | * Returns pointer to last entry moved. | ||
1128 | */ | ||
1118 | static struct ext4_dir_entry_2 * | 1129 | static struct ext4_dir_entry_2 * |
1119 | dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) | 1130 | dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) |
1120 | { | 1131 | { |
@@ -1133,6 +1144,10 @@ dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) | |||
1133 | return (struct ext4_dir_entry_2 *) (to - rec_len); | 1144 | return (struct ext4_dir_entry_2 *) (to - rec_len); |
1134 | } | 1145 | } |
1135 | 1146 | ||
1147 | /* | ||
1148 | * Compact each dir entry in the range to the minimal rec_len. | ||
1149 | * Returns pointer to last entry in range. | ||
1150 | */ | ||
1136 | static struct ext4_dir_entry_2* dx_pack_dirents(char *base, int size) | 1151 | static struct ext4_dir_entry_2* dx_pack_dirents(char *base, int size) |
1137 | { | 1152 | { |
1138 | struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base; | 1153 | struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base; |
@@ -1155,6 +1170,11 @@ static struct ext4_dir_entry_2* dx_pack_dirents(char *base, int size) | |||
1155 | return prev; | 1170 | return prev; |
1156 | } | 1171 | } |
1157 | 1172 | ||
1173 | /* | ||
1174 | * Split a full leaf block to make room for a new dir entry. | ||
1175 | * Allocate a new block, and move entries so that they are approx. equally full. | ||
1176 | * Returns pointer to de in block into which the new entry will be inserted. | ||
1177 | */ | ||
1158 | static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, | 1178 | static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, |
1159 | struct buffer_head **bh,struct dx_frame *frame, | 1179 | struct buffer_head **bh,struct dx_frame *frame, |
1160 | struct dx_hash_info *hinfo, int *error) | 1180 | struct dx_hash_info *hinfo, int *error) |
@@ -1166,7 +1186,7 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, | |||
1166 | u32 hash2; | 1186 | u32 hash2; |
1167 | struct dx_map_entry *map; | 1187 | struct dx_map_entry *map; |
1168 | char *data1 = (*bh)->b_data, *data2; | 1188 | char *data1 = (*bh)->b_data, *data2; |
1169 | unsigned split; | 1189 | unsigned split, move, size, i; |
1170 | struct ext4_dir_entry_2 *de = NULL, *de2; | 1190 | struct ext4_dir_entry_2 *de = NULL, *de2; |
1171 | int err = 0; | 1191 | int err = 0; |
1172 | 1192 | ||
@@ -1194,8 +1214,19 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, | |||
1194 | count = dx_make_map ((struct ext4_dir_entry_2 *) data1, | 1214 | count = dx_make_map ((struct ext4_dir_entry_2 *) data1, |
1195 | blocksize, hinfo, map); | 1215 | blocksize, hinfo, map); |
1196 | map -= count; | 1216 | map -= count; |
1197 | split = count/2; // need to adjust to actual middle | ||
1198 | dx_sort_map (map, count); | 1217 | dx_sort_map (map, count); |
1218 | /* Split the existing block in the middle, size-wise */ | ||
1219 | size = 0; | ||
1220 | move = 0; | ||
1221 | for (i = count-1; i >= 0; i--) { | ||
1222 | /* is more than half of this entry in 2nd half of the block? */ | ||
1223 | if (size + map[i].size/2 > blocksize/2) | ||
1224 | break; | ||
1225 | size += map[i].size; | ||
1226 | move++; | ||
1227 | } | ||
1228 | /* map index at which we will split */ | ||
1229 | split = count - move; | ||
1199 | hash2 = map[split].hash; | 1230 | hash2 = map[split].hash; |
1200 | continued = hash2 == map[split - 1].hash; | 1231 | continued = hash2 == map[split - 1].hash; |
1201 | dxtrace(printk("Split block %i at %x, %i/%i\n", | 1232 | dxtrace(printk("Split block %i at %x, %i/%i\n", |