> On Wed, 21 Apr 2010, Greg Freemyer wrote: > And also, currently I am rewriting the patch do use rbtree instead of the > bitmap, because there were some concerns of memory consumption. It is a > question whether or not the rbtree will be more memory friendly. > Generally I think that in most "normal" cases it will, but there are some > extreme scenarios, where the rbtree will be much worse. Any comment on > this ? I see two possible improvements here: a) At a cost of some code complexity, you can bound the worst case by combining RB-trees with bitmaps. The basic idea is that when space to TRIM gets too fragmented (memory to keep to-TRIM blocks in RB-tree for a given group exceeds the memory needed to keep it in a bitmap), you convert RB-tree for a problematic group to a bitmap and attach it to an appropriate RB-node. If you track with a bitmap also a number of to-TRIM extents in the bitmap, you can also decide whether it's benefitial to switch back to an RB-tree. b) Another idea might be: When to-TRIM space is fragmented (again, let's say in some block group), there's not much point in sending tiny trim commands anyway (at least that's what I've understood from this discussion). So you might as well stop maintaining information which blocks we need to trim for that group. When the situation gets better, you can always walk block bitmap and issue trim commands. You might even trigger this rescan from kernel - if you'd maintain number of free block extents for each block group (which is rather easy), you could trigger the bitmap rescan and trim as soon as ratio number of free blocks / number of extents gets above a reasonable threshold. Honza -- Jan Kara <jack@xxxxxxx> SuSE CR Labs -- 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
