ensure do_split leaves enough free space in both blocks
RFC PATCH 1/1 ensure do_split leaves enough free space in both blocks
For me, this fixes the problem reported by [email protected], "ext3 dir_index causes an error"
The issue is that the do_split() function sorts the entries in the old block by hash value, then moves half the entries to the new block without accounting for how much space this actually moves. (IOW, it moves half of the entry *count* not half of the entry *space*)
The patch below stores size as well when calculating the dx_map, and then walks the hash-sorted dx_map, calculating how many entries must be moved to more evenly split the existing entries between the old block and the new block, guaranteeing enough space for the new entry.
Enhancements that could be made, though I'm not sure it's worth it:
* pack the old dir block before calculating nr of entries to move,
-or-
* calculate the minimum rec_len when generating the map, vs. just storing the current rec_len.
I'm not sure it's worth the extra calculations, I think this code below works just fine from a correctness perspective.
How's this look, any comments?
Thanks,
-Eric
fs/ext3/namei.c +15 -2
@@ -141,6 +141,7 @@ struct dx_map_entry {u32 hash;u32 offs; +u32 size; };#ifdef CONFIG_EXT3_INDEX
@@ -685,6 +687,7 @@ static int dx_make_map (struct ext3_dir_ map_tail--; map_tail->hash = h.hash; map_tail->offs = (u32) ((char *) de - base); + map_tail->size =le16_to_cpu (de->rec_len); count++;cond_resched (); }
@@ -1142,7 +1159,7 @@ static struct ext3_dir_entry_2 *do_splitu32 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 ;
@@ -1170,8 +1187,19 @@ static struct ext3_dir_entry_2 *do_split 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 last 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",
Quoted 2 lines · Eric Sandeen
* calculate the minimum
rec_lenwhen generating the map, vs. just storing the currentrec_len.
Well, we already do this when moving the entries, so in theory we should do it when checking how many entries to move. That said, we know we can't _increase_ the amount of space used (so no chance of introducing a problem) but we might still end up with some imbalance.
fs/ext3/namei.c struct dx_map_entry · line 145
Quoted 6 lines
fs/ext3/namei.c +1
-0@@ -141,6 +141,7 @@ struct dx_map_entry {u32 hash;u32 offs; +u32 size; };
Hmm, there was something about the size of the dx_map_entry, because it is actually built at the end of the target block, that we don't want to make it too large.
Now, I'm not sure if adding an extra 32-bit field per entry would make it too large or not, since I haven't looked at that code in ages. The critical factor is whether max_entries = blocksize / min_rec_len would consume more than the worst-case amount of space in the target block.
So, because thinking is hard, you might consider just changing the above code to use "u16 offs; u16 size;" since we know those are big enough variables, and won't increase the size of the map...
fs/ext3/namei.c static struct ext3_dir_entry_2 *do_split · line 1202
Quoted 9 lines
fs/ext3/namei.c +9
-0+for (i = count-1 ; i >=0 ; i--) { +/* is more than half of this entry in last 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;
The rest of this looks fine - I think the "1/2 of median entry" decision is the right one as we discussed.
Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.
Quoted 10 lines · Andreas Dilger
fs/ext3/namei.c struct dx_map_entry · line 145
Quoted 6 lines
fs/ext3/namei.c +1
-0@@ -141,6 +141,7 @@ struct dx_map_entry {u32 hash;u32 offs; +u32 size; };Hmm, there was something about the size of the
dx_map_entry, because it is actually built at the end of the target block, that we don't want to make it too large.
Yep, that crossed my mind...
Quoted 8 lines
Now, I'm not sure if adding an extra 32-bit field per entry would make it too large or not, since I haven't looked at that code in ages. The critical factor is whether
max_entries= blocksize /min_rec_lenwould consume more than the worst-case amount of space in the target block.So, because thinking is hard, you might consider just changing the above code to use "u16 offs; u16 size;" since we know those are big enough variables, and won't increase the size of the map...
That sounds like a good plan. The other possibility is, we don't *have* to store size in the map, with offset we can always get to the size, too.
Quoted 4 lines
Quoted 4 lines
fs/ext3/namei.c +4
-0+for (i = count-1 ; i >=0 ; i--) { +/* is more than half of this entry in last half of the block? */ +if (size + map[i].size/2 > blocksize/2 ) +break ;
Quoted 8 lines
fs/ext3/namei.c static struct ext3_dir_entry_2 *do_split · line 1202
Quoted 5 lines
fs/ext3/namei.c +5
-0+ size += map[i].size; + move++; + } +/* map index at which we will split */ + split = count - move;The rest of this looks fine - I think the "1/2 of median entry" decision is the right one as we discussed.
Yes, I forgot to mention that I had discussed this with you a bit already. :) After drawing a few pictures, this seems like the right way to go.
-Eric
Quoted 8 lines · Andreas Dilger
Quoted 2 lines · Eric Sandeen
* calculate the minimum
rec_lenwhen generating the map, vs. just storing the currentrec_len.Well, we already do this when moving the entries, so in theory we should do it when checking how many entries to move. That said, we know we can't _increase_ the amount of space used (so no chance of introducing a problem) but we might still end up with some imbalance.
I think I'm going to pass on this, at least for now, to save the extra calculation. We've lived for years with whatever split the original code gave us, and with the exception of this overflow, we've not seen problems. Splitting based on rec_len (vs. EXT3_DIR_REC_LEN) should still split things fairly well, on average.
If we used EXT3_DIR_REC_LEN)(name_len) for the new tests, I think we'd first need to add up the minimal size of *all* entries, because the new threshold would no longer be blocksize/2. So, this would be more times around the loop.
If anyone feels strongly that we should make this split as accurate as possible, I'm willing to patch that up too, but for now I think I'd like to get the more targeted fix in place, as it should solve the bug at hand in a simpler manner.
Sound ok?
-Eric