linux-kernel - Re: [PATCHv6 0/8] zswap: compressed swap caching

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]

Date:	Thu, 21 Feb 2013 12:25:54 -0600
From:	Seth Jennings <sjenning@...ux.vnet.ibm.com>
To:	Dan Magenheimer <dan.magenheimer@...cle.com>
CC:	Andrew Morton <akpm@...ux-foundation.org>,
	Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
	Nitin Gupta <ngupta@...are.org>,
	Minchan Kim <minchan@...nel.org>,
	Konrad Wilk <konrad.wilk@...cle.com>,
	Robert Jennings <rcj@...ux.vnet.ibm.com>,
	Jenifer Hopper <jhopper@...ibm.com>,
	Mel Gorman <mgorman@...e.de>,
	Johannes Weiner <jweiner@...hat.com>,
	Rik van Riel <riel@...hat.com>,
	Larry Woodman <lwoodman@...hat.com>,
	Benjamin Herrenschmidt <benh@...nel.crashing.org>,
	Dave Hansen <dave@...ux.vnet.ibm.com>,
	Joe Perches <joe@...ches.com>,
	Joonsoo Kim <iamjoonsoo.kim@....com>,
	Cody P Schafer <cody@...ux.vnet.ibm.com>, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org, devel@...verdev.osuosl.org
Subject: Re: [PATCHv6 0/8] zswap: compressed swap caching

On 02/21/2013 09:50 AM, Dan Magenheimer wrote:
>> From: Seth Jennings [mailto:sjenning@...ux.vnet.ibm.com]
>> Subject: [PATCHv6 0/8] zswap: compressed swap caching
>>
>> Changelog:
>>
>> v6:
>> * fix improper freeing of rbtree (Cody)
> 
> Cody's bug fix reminded me of a rather fundamental question:
> 
> Why does zswap use a rbtree instead of a radix tree?
> 
> Intuitively, I'd expect that pgoff_t values would
> have a relatively high level of locality AND at any one time
> the set of stored pgoff_t values would be relatively non-sparse.
> This would argue that a radix tree would result in fewer nodes
> touched on average for lookup/insert/remove.

I considered using a radix tree, but I don't think there is a compelling
reason to choose a radix tree over a red-black tree in this case
(explanation below).

>From a runtime standpoint, a radix tree might be faster.  The swap
offsets will be largely in linearly bunched groups over the indexed
range.  However, there are also memory constraints to consider in this
particular situation.

Using a radix tree could result in intermediate radix_tree_node
allocations in the store (insert) path in addition to the zswap_entry
allocation.  Since we are under memory pressure, using the red-black
tree, whose metadata is included in the struct zswap_entry, reduces the
number of opportunities to fail.

On my system, the radix_tree_node structure is 568 bytes.  The
radix_tree_node cache requires 4 pages per slab, an order-2 page
allocation.  Growing that cache will be difficult under the pressure.

In my mind, cost of even a single node allocation failure resulting in
an additional page swapped to disk will more that wipe out any possible
performance advantage using a radix tree might have.

Thanks,
Seth

--
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/