Re: [patch] Converting writeback linked lists to a tree based data structure

[Fengguang Wu <wfg@mail.ustc.edu.cn>]

On Tue, Jan 15, 2008 at 08:42:36PM -0800, Andrew Morton wrote:
> On Wed, 16 Jan 2008 12:25:53 +0800 Fengguang Wu <wfg@mail.ustc.edu.cn> wrote:
> 
> > list_heads are OK if we use them for one and only function.
> 
> Not really.  They're inappropriate when you wish to remember your
> position in the list while you dropped the lock (as we must do in
> writeback).
> 
> A data structure which permits us to interate across the search key rather
> than across the actual storage locations is more appropriate.

I totally agree with you. What I mean is to first do the split of
functions - into three: ordering, starvation prevention, and blockade
waiting. Then to do better ordering by adopting radix tree(or rbtree
if radix tree is not enough), and lastly get rid of the list_heads to
avoid locking. Does it sound like a good path?