Re: [RFC][PATCH -mm] swsusp: Use rbtree for tracking allocated swap

[Nigel Cunningham <nigel@nigel.suspend2.net>]

Hi.

On Sun, 2007-04-08 at 18:47 +0200, Rafael J. Wysocki wrote:
> On Sunday, 8 April 2007 01:42, Nigel Cunningham wrote:
> > Hi.
> > 
> > On Sun, 2007-04-08 at 01:13 +0200, Rafael J. Wysocki wrote:
> > > On Sunday, 8 April 2007 00:31, Nigel Cunningham wrote:
> > > > Hi.
> > > > 
> > > > On Sat, 2007-04-07 at 15:06 -0700, Andrew Morton wrote:
> > > > > On Sat, 7 Apr 2007 23:20:39 +0200 "Rafael J. Wysocki" <rjw@sisk.pl> wrote:
> > > > > 
> > > > > > This should allow us to reduce the memory usage, practically always, and
> > > > > > improve performance.
> > > > > 
> > > > > And does it?
> > > 
> > > Yes.  There are theoretical corner cases in which it may be less efficient
> > > than the current approach, but in the usual situation it is _much_ better.
> > > 
> > > > It will. I've been using extents for ages, for the same reasons. I don't
> > > > put them in an rb_tree because I view it as less than most efficient,
> > > 
> > > Actually, I don't agree with that.  In the normal situation (ie. one extent is
> > > needed) there is no difference as far as the memory usage or performance
> > > are concerned, but if there are more extents, the rbtree should be more
> > > efficient.
> > 
> > I don't think it's worth having a big discussion over, but let me give
> > you the details, which you can then feel free to ignore :)
> > 
> > The rb_node struct adds an unsigned long and two struct rb_node *
> > pointers. My extents use one struct extent * pointer. The difference is
> > thus 12/24 bytes per extent (32/64 bits) vs 20/40.
> 
> Well, you use open-coded lists.  If you used list.h lists, the numbers 
> would be different. :-)

Yes, but I don't need doubly linked lists.

> > In the normal situation, not worth worrying about, but I'm also using these for
> > recording the sectors we write too, and thinking about swap files and
> > multiple swap devices. Nearly double the memory use bites more as you
> > get more extents.
> >
> > Insertion cost for rb_node includes keeping the tree balanced. For
> > extents, I start with the location of the last insertion to minimise the
> > cost, so insertion time is usually virtually zero (inc max of last
> > extent or append a new one).
> 
> Isn't the appending one actually linear worst-case?

Worst case would be the swap allocator returning swap pages in reverse
order. As you and I both know, that doesn't happen. I first implemented
this in 2003. If the worst case actually happened, I would have seen the
effect by now :)

> > If for some reason swap was allocated out of order, I might need to traverse
> > the whole chain from the start. 
> 
> Exactly.
> 
> > Normal usage in both cases is simply iterating through the list, so I
> > guess the cost would be approximately the same.
> > 
> > Deletion could would include rebalancing for the rb_nodes.
> 
> In swsusp the deletions are needed only if there's an error.

When freeing swap at the end of the cycle?

> > Code cost is a gain for you - you're leveraging existing code, I'm
> > adding a bit more. extent.c is 300 lines including code for serialising
> > the chains in an image header and iterating through a group of chains
> > (multiple swap devices support).
> > 
> > rb_nodes seem to be the wrong solution to me because we generally don't
> > care about searching. We care about minimising memory usage and
> > maximising the speed of iteration, insertion and deletion. I believe
> > I've managed to do that with a singly linked, sorted list.
> 
> The insertion also uses searching and in fact I don't really care for anything
> else.

Ok :)

Nigel