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
 struct dx_map_entry
 {
         u32 hash;
-        u32 offs;
+        u16 offs;
+        u16 size;
 };
 
 #ifdef CONFIG_EXT3_INDEX
@@ -697,6 +698,10 @@ errout:
  * Directory block splitting, compacting
  */
 
+/*
+ * Create map of hash values, offsets, and sizes, stored at end of block.
+ * Returns number of entries mapped.
+ */
 static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
                         struct dx_hash_info *hinfo, struct dx_map_entry *map_tail)
 {
@@ -710,7 +715,8 @@ static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
                         ext3fs_dirhash(de->name, de->name_len, &h);
                         map_tail--;
                         map_tail->hash = h.hash;
-                        map_tail->offs = (u32) ((char *) de - base);
+                        map_tail->offs = (u16) ((char *) de - base);
+                        map_tail->size = le16_to_cpu(de->rec_len);
                         count++;
                         cond_resched();
                 }
@@ -720,6 +726,7 @@ static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
         return count;
 }
 
+/* Sort map by hash value */
 static void dx_sort_map (struct dx_map_entry *map, unsigned count)
 {
         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,
 }
 
 #ifdef CONFIG_EXT3_INDEX
+/*
+ * Move count entries from end of map between two memory locations.
+ * Returns pointer to last entry moved.
+ */
 static struct ext3_dir_entry_2 *
 dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
 {
@@ -1135,6 +1146,10 @@ dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
         return (struct ext3_dir_entry_2 *) (to - rec_len);
 }
 
+/*
+ * Compact each dir entry in the range to the minimal rec_len.
+ * Returns pointer to last entry in range.
+ */
 static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size)
 {
         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)
         return prev;
 }
 
+/*
+ * Split a full leaf block to make room for a new dir entry.
+ * Allocate a new block, and move entries so that they are approx. equally full.
+ * Returns pointer to de in block into which the new entry will be inserted.
+ */
 static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
                         struct buffer_head **bh,struct dx_frame *frame,
                         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,
         u32 hash2;
         struct dx_map_entry *map;
         char *data1 = (*bh)->b_data, *data2;
-        unsigned split;
+        unsigned split, move, size, i;
         struct ext3_dir_entry_2 *de = NULL, *de2;
         int     err = 0;
 
@@ -1196,8 +1216,19 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
         count = dx_make_map ((struct ext3_dir_entry_2 *) data1,
                              blocksize, hinfo, map);
         map -= count;
-        split = count/2; // need to adjust to actual middle
         dx_sort_map (map, count);
+        /* Split the existing block in the middle, size-wise */
+        size = 0;
+        move = 0;
+        for (i = count-1; i >= 0; i--) {
+                /* is more than half of this entry in 2nd half of the block? */
+                if (size + map[i].size/2 > blocksize/2)
+                        break;
+                size += map[i].size;
+                move++;
+        }
+        /* map index at which we will split */
+        split = count - move;
         hash2 = map[split].hash;
         continued = hash2 == map[split - 1].hash;
         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
 struct dx_map_entry
 {
         u32 hash;
-        u32 offs;
+        u16 offs;
+        u16 size;
 };
 
 #ifdef CONFIG_EXT4_INDEX
@@ -697,6 +698,10 @@ errout:
  * Directory block splitting, compacting
  */
 
+/*
+ * Create map of hash values, offsets, and sizes, stored at end of block.
+ * Returns number of entries mapped.
+ */
 static int dx_make_map (struct ext4_dir_entry_2 *de, int size,
                         struct dx_hash_info *hinfo, struct dx_map_entry *map_tail)
 {
@@ -710,7 +715,8 @@ static int dx_make_map (struct ext4_dir_entry_2 *de, int size,
                         ext4fs_dirhash(de->name, de->name_len, &h);
                         map_tail--;
                         map_tail->hash = h.hash;
-                        map_tail->offs = (u32) ((char *) de - base);
+                        map_tail->offs = (u16) ((char *) de - base);
+                        map_tail->size = le16_to_cpu(de->rec_len);
                         count++;
                         cond_resched();
                 }
@@ -720,6 +726,7 @@ static int dx_make_map (struct ext4_dir_entry_2 *de, int size,
         return count;
 }
 
+/* Sort map by hash value */
 static void dx_sort_map (struct dx_map_entry *map, unsigned count)
 {
         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,
 }
 
 #ifdef CONFIG_EXT4_INDEX
+/*
+ * Move count entries from end of map between two memory locations.
+ * Returns pointer to last entry moved.
+ */
 static struct ext4_dir_entry_2 *
 dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
 {
@@ -1133,6 +1144,10 @@ dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
         return (struct ext4_dir_entry_2 *) (to - rec_len);
 }
 
+/*
+ * Compact each dir entry in the range to the minimal rec_len.
+ * Returns pointer to last entry in range.
+ */
 static struct ext4_dir_entry_2* dx_pack_dirents(char *base, int size)
 {
         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)
         return prev;
 }
 
+/*
+ * Split a full leaf block to make room for a new dir entry.
+ * Allocate a new block, and move entries so that they are approx. equally full.
+ * Returns pointer to de in block into which the new entry will be inserted.
+ */
 static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
                         struct buffer_head **bh,struct dx_frame *frame,
                         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,
         u32 hash2;
         struct dx_map_entry *map;
         char *data1 = (*bh)->b_data, *data2;
-        unsigned split;
+        unsigned split, move, size, i;
         struct ext4_dir_entry_2 *de = NULL, *de2;
         int     err = 0;
 
@@ -1194,8 +1214,19 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
         count = dx_make_map ((struct ext4_dir_entry_2 *) data1,
                              blocksize, hinfo, map);
         map -= count;
-        split = count/2; // need to adjust to actual middle
         dx_sort_map (map, count);
+        /* Split the existing block in the middle, size-wise */
+        size = 0;
+        move = 0;
+        for (i = count-1; i >= 0; i--) {
+                /* is more than half of this entry in 2nd half of the block? */
+                if (size + map[i].size/2 > blocksize/2)
+                        break;
+                size += map[i].size;
+                move++;
+        }
+        /* map index at which we will split */
+        split = count - move;
         hash2 = map[split].hash;
         continued = hash2 == map[split - 1].hash;
         dxtrace(printk("Split block %i at %x, %i/%i\n",