> On Wed, 21 Apr 2010, Greg Freemyer wrote:
quoted text
> 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@suse.cz>
SuSE CR Labs
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html