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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <200704080113.24171.rjw@sisk.pl>
Date:	Sun, 8 Apr 2007 01:13:23 +0200
From:	"Rafael J. Wysocki" <rjw@...k.pl>
To:	Nigel Cunningham <ncunningham@...uxmail.org>,
	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Pavel Machek <pavel@....cz>, LKML <linux-kernel@...r.kernel.org>
Subject: Re: [RFC][PATCH -mm] swsusp: Use rbtree for tracking allocated swap

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@...k.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.

> but it will still be a huge step forward from bitmaps in the normal
> case.
> 
> The worst case would be if every second page of swap was in use, so that
> you needed one extent per swap page. In that case, it would use more
> memory than the bitmap, but far, far more common will be the case where
> only one extent is needed for the whole swap partition, because the
> algorithm used by the swap allocator minimises fragmentation.

Exactly.

Greetings,
Rafael
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/