On Mon, Feb 15, 2010 at 08:56:09AM +0100, Ulrich Bauer wrote: > A quick observation of > resize2fs' source revealed that the latest git tree already has a > bitmap interface that allows for different implementations of the > bitmap manipulation algorithms. To solve the memory usage problem, > two solutions seem to be feasible: > > - For the huge bitmaps that already exist on the volume, we could > create a disk-backed bitmap implementation that would only cache a > small working set of the entire bitmap. My guess is that we can > implement this efficiently enough to not loose too much performance. > - For the all-zero bitmaps, we could implement a dummy bitmap that > forces all bits to zero and spawns a real bitmap as soon as any bits > are set to one. An alternative would be a tree-based aproach that > works especially well when the bitmap is just sparsely set. What I would recommend is a run-length encoded tree-based approached. This should work well regardless of whether the bitmap is sparsely set or not, because most of the time blocks are allocated contiguously. > I'd be glad if one of the developers involved in the ext4 > development could tell me if these thoughts make sense and if yes, > are there any plans to incorporate these approaches into the ext > library anytime soon or does it make sense if I would have a deeper > look into these issues and implement them? Thanks in advance for any > thoughts about this. There are plans to incorporate the RLE tree-based implementation, but it's been relatively low on the priority list given all of the other things. If you'd be interested in implementing it, that would be great. - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
