linux-kernel - Re: [PATCH 0/6] PM / Hibernate: Memory bitmap scalability improvements

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <20140721114507.GA13921@amd.pavel.ucw.cz>
Date:	Mon, 21 Jul 2014 13:45:07 +0200
From:	Pavel Machek <pavel@....cz>
To:	Joerg Roedel <joro@...tes.org>
Cc:	"Rafael J. Wysocki" <rjw@...ysocki.net>,
	Len Brown <len.brown@...el.com>, linux-pm@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 0/6] PM / Hibernate: Memory bitmap scalability
 improvements

On Mon 2014-07-21 10:32:11, Joerg Roedel wrote:
> On Sat, Jul 19, 2014 at 03:49:04PM +0200, Pavel Machek wrote:
> > Hi!
> > 
> > > These patches improve the data structure by adding a radix
> > > tree to the linked list structure to improve random access
> > > performance from O(n) to O(log_b(n)), where b depends on the
> > > architecture (b=512 on amd64, 1024 in i386).
> > 
> > Are you sure? From your other mail, you said you are adding just a
> > single page. I'd expect random access performance to go from
> > 
> > O(n) to O(n/1024) in such case?
> 
> No, for the 4GB case the additional page is used as an index page into
> the block-bitmap pages. On AM64 a page can hold 512 references and a
> single block-bitmap page is enough for 128MB of RAM. This means that for
> systems with up to 64GB of RAM we can get the block-bitmap page directly
> from the index page. For systems with more than 64GB of RAM we need
> another level of index pages, and now we need two memory accesses to get
> to the block-bitmap page (okay, with this implementation its actually 2
> memory accesses per level, because the index-pages refer to a struct
> rtree_node which itself contains the pointer to the index/data page).
> 
> A two-level radix tree would be enough for systems with up to 32TB of
> RAM. After that we need 3 levels, but you can already see that this
> doesn't scale linearly anymore but with log_512(n), where n is the
> number of block-bitmap pages required.

Ok, so you have sped it up from O(n) to O(log(n)) speed, and increased
memory requirements from O(n) to O(n * log(n)), right?

does enough_swap() or reqd_free_pages() need to be updated?

Best regards,
								Pavel

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
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/