Andreas Dilger wrote:

quoted

@@ -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...

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...

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

+	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.

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