Dan Magenheimer
2011-May-11 20:38 UTC
[Xen-devel] RE: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
> From: Xen patchbot-unstable [mailto:patchbot@xen.org] > Sent: Tuesday, May 10, 2011 9:40 PM > To: xen-changelog@lists.xensource.com > Subject: [Xen-changelog] [xen-unstable] Update radix-tree.[ch] from > upstream Linux to gain RCU awareness. > > # HG changeset patch > # User Keir Fraser <keir@xen.org> > # Date 1304929523 -3600 > # Node ID 44bfebf40b2bb7f219333ef5bf97eb7493592cdc > # Parent 4b0692880dfa557d4e1537c7a58c412c1286a416 > Update radix-tree.[ch] from upstream Linux to gain RCU awareness. > > We still leave behind features we don''t need such as tagged nodes. > > Other changes: > - Allow callers to define their own node alloc routines. > - Only allocate per-node rcu_head when using the default RCU-safe > alloc routines. > - Keep our own radix_tree_destroy(). > > In future it may also be worth getting rid of the complex and > pointless special-casing of radix-tree height==0, in which a single > data item can be stored directly in radix_tree_root. It introduces a > whole lot of special cases and complicates RCU handling. If we get rid > of it we can reclaim the ''indirect pointer'' tag in bit 0 of every slot > entry. > > Signed-off-by: Keir Fraser <keir@xen.org>Thanks for handling this. A couple thoughts worth noting: I''m not sure the height=0 special-casing is pointless. IIRC, a radix-tree node contains 64 pointers (512 bytes). When trees containing a single item are common, 512 bytes may be a relatively large overhead For tmem, each tree contains pages from a file, many files on many filesystems are less than one-page, and, when compressed that one page may be represented by far less than 4096 bytes, so avoiding the overhead is a big win. While I like your improvements avoiding the extra args passed on each insert/delete, I''m not sure for tmem the tradeoff is a good one. A basic assumption of tmem is that memory is constrained and CPU cycles are abundant. While we''ve all been trained to avoid passing parameters when possible to reduce CPU overhead, the world is changing. If radix-tree.c is used in Xen in the future for non-tmem high-frequency inserts/deletes, your CPU optimization is probably best, but for tmem I think it''s a net loss as now each radix tree (and there may be thousands or millions in a large tmem-enabled Xen system) "wastes" 24 bytes. Thanks, Dan _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Keir Fraser
2011-May-11 21:48 UTC
[Xen-devel] Re: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
On 11/05/2011 21:38, "Dan Magenheimer" <dan.magenheimer@oracle.com> wrote:> I''m not sure the height=0 special-casing is pointless. IIRC, a > radix-tree node contains 64 pointers (512 bytes). When trees containing > a single item are common, 512 bytes may be a relatively large overhead > For tmem, each tree contains pages from a file, many files on > many filesystems are less than one-page, and, when compressed that > one page may be represented by far less than 4096 bytes, so avoiding > the overhead is a big win. > > While I like your improvements avoiding the extra args passed on each > insert/delete, I''m not sure for tmem the tradeoff is a good one. > A basic assumption of tmem is that memory is constrained and > CPU cycles are abundant. While we''ve all been trained to avoid > passing parameters when possible to reduce CPU overhead, > the world is changing. If radix-tree.c is used in Xen in the future > for non-tmem high-frequency inserts/deletes, your CPU optimization > is probably best, but for tmem I think it''s a net loss as now > each radix tree (and there may be thousands or millions in a > large tmem-enabled Xen system) "wastes" 24 bytes.If this is critical, you simply shouldn''t represent such small files with a radix tree. I''m sure you could easily come up with some scheme to switch to a single direct reference in the <= 1 page case, thus saving a whole radix_tree_root structure (and a radix_tree_node structure if I do kill the height=0 special case). I''d recommend changing the radix_tree_root inlined structure in tmem_object_root into a pointer which points at a radix_tree_root or a singleton page, discriminating between these two cases perhaps on pgp_count. -- Keir _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Dan Magenheimer
2011-May-11 22:12 UTC
[Xen-devel] RE: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
> From: Keir Fraser [mailto:keir.xen@gmail.com] > Subject: Re: Update radix-tree.[ch] from upstream Linux to gain RCU > awareness. > > On 11/05/2011 21:38, "Dan Magenheimer" <dan.magenheimer@oracle.com> > wrote: > > > I''m not sure the height=0 special-casing is pointless. IIRC, a > > radix-tree node contains 64 pointers (512 bytes). When trees > containing > > a single item are common, 512 bytes may be a relatively large > overhead > > For tmem, each tree contains pages from a file, many files on > > many filesystems are less than one-page, and, when compressed that > > one page may be represented by far less than 4096 bytes, so avoiding > > the overhead is a big win. > > > > While I like your improvements avoiding the extra args passed on each > > insert/delete, I''m not sure for tmem the tradeoff is a good one. > > A basic assumption of tmem is that memory is constrained and > > CPU cycles are abundant. While we''ve all been trained to avoid > > passing parameters when possible to reduce CPU overhead, > > the world is changing. If radix-tree.c is used in Xen in the future > > for non-tmem high-frequency inserts/deletes, your CPU optimization > > is probably best, but for tmem I think it''s a net loss as now > > each radix tree (and there may be thousands or millions in a > > large tmem-enabled Xen system) "wastes" 24 bytes. > > If this is critical, you simply shouldn''t represent such small files > with a > radix tree. I''m sure you could easily come up with some scheme to > switch to > a single direct reference in the <= 1 page case, thus saving a whole > radix_tree_root structure (and a radix_tree_node structure if I do kill > the > height=0 special case). I''d recommend changing the radix_tree_root > inlined > structure in tmem_object_root into a pointer which points at a > radix_tree_root or a singleton page, discriminating between these two > cases > perhaps on pgp_count.True, the special casing could be handled in tmem. (On the chance that you decide to do this, the special case only applies if the pgp_count is 1 AND the index of the page is zero.) Note also that tmem doesn''t have a clue about the size of the file and may frequently need to change between an object that only has page index==0 in tmem and one that has more than that. The net result is that you would simply be moving the special casing and "automatic transformation" code from radix-tree to tmem, for a net result of no advantage (AFAICT) and IMHO since the code needs to be somewhere, it might as well be in radix-tree since it is already there and debugged for Linux. _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel