Transcendent memory ("tmem") for Xen.

Tmem, when called from a tmem-capable (paravirtualized) guest, makes
use of otherwise unutilized ("fallow") memory to create and manage
pools of pages that can be accessed from the guest either as
"ephemeral" pages or as "persistent" pages.  In either case, the pages
are not directly addressible by the guest, only copied to and fro via
the tmem interface.  Ephemeral pages are a nice place for a guest to
put recently evicted clean pages that it might need again; these pages
can be reclaimed synchronously by Xen for other guests or other uses.
Persistent pages are a nice place for a guest to put "swap" pages to
avoid sending them to disk.  These pages retain data as long as the
guest lives, but count against the guest memory allocation.

Tmem pages may optionally be compressed and, in certain cases, can be
shared between guests.  Tmem also handles concurrency nicely and
provides limited QoS settings to combat malicious DoS attempts.
Save/restore and live migration support is not yet provided.

Tmem is primarily targeted for an x86 64-bit hypervisor.  On a 32-bit
x86 hypervisor, it has limited functionality and testing due to
limitations of the xen heap.  Nearly all of tmem is
architecture-independent; three routines remain to be ported to ia64
and it should work on that architecture too.  It is also structured to
be portable to non-Xen environments.

Tmem defaults off (for now) and must be enabled with a "tmem" xen boot
option (and does nothing unless a tmem-capable guest is running).  The
"tmem_compress" boot option enables compression which takes about 10x
more CPU but approximately doubles the number of pages that can be
stored.

Tmem can be controlled via several "xm" commands and many interesting
tmem statistics can be obtained.  A README and internal specification
will follow, but lots of useful prose about tmem, as well as Linux
patches, can be found at http://oss.oracle.com/projects/tmem .

Signed-off-by: Dan Magenheimer <dan.magenheimer@oracle.com>

1 files changed, 398 insertions, 0 deletions

diff --git a/xen/common/rbtree.c b/xen/common/rbtree.c
new file mode 100644
index 0000000000..67564c81b3
--- /dev/null
+++ b/xen/common/rbtree.c
@@ -0,0 +1,398 @@
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  (C) 2002  David Woodhouse <dwmw2@infradead.org>
+  
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+  linux/lib/rbtree.c
+*/
+
+#include <xen/config.h>
+#include <xen/types.h>
+#include <xen/rbtree.h>
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+    struct rb_node *right = node->rb_right;
+    struct rb_node *parent = rb_parent(node);
+
+    if ((node->rb_right = right->rb_left))
+        rb_set_parent(right->rb_left, node);
+    right->rb_left = node;
+
+    rb_set_parent(right, parent);
+
+    if (parent)
+    {
+        if (node == parent->rb_left)
+            parent->rb_left = right;
+        else
+            parent->rb_right = right;
+    }
+    else
+        root->rb_node = right;
+    rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+    struct rb_node *left = node->rb_left;
+    struct rb_node *parent = rb_parent(node);
+
+    if ((node->rb_left = left->rb_right))
+        rb_set_parent(left->rb_right, node);
+    left->rb_right = node;
+
+    rb_set_parent(left, parent);
+
+    if (parent)
+    {
+        if (node == parent->rb_right)
+            parent->rb_right = left;
+        else
+            parent->rb_left = left;
+    }
+    else
+        root->rb_node = left;
+    rb_set_parent(node, left);
+}
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+    struct rb_node *parent, *gparent;
+
+    while ((parent = rb_parent(node)) && rb_is_red(parent))
+    {
+        gparent = rb_parent(parent);
+
+        if (parent == gparent->rb_left)
+        {
+            {
+                register struct rb_node *uncle = gparent->rb_right;
+                if (uncle && rb_is_red(uncle))
+                {
+                    rb_set_black(uncle);
+                    rb_set_black(parent);
+                    rb_set_red(gparent);
+                    node = gparent;
+                    continue;
+                }
+            }
+
+            if (parent->rb_right == node)
+            {
+                register struct rb_node *tmp;
+                __rb_rotate_left(parent, root);
+                tmp = parent;
+                parent = node;
+                node = tmp;
+            }
+
+            rb_set_black(parent);
+            rb_set_red(gparent);
+            __rb_rotate_right(gparent, root);
+        } else {
+            {
+                register struct rb_node *uncle = gparent->rb_left;
+                if (uncle && rb_is_red(uncle))
+                {
+                    rb_set_black(uncle);
+                    rb_set_black(parent);
+                    rb_set_red(gparent);
+                    node = gparent;
+                    continue;
+                }
+            }
+
+            if (parent->rb_left == node)
+            {
+                register struct rb_node *tmp;
+                __rb_rotate_right(parent, root);
+                tmp = parent;
+                parent = node;
+                node = tmp;
+            }
+
+            rb_set_black(parent);
+            rb_set_red(gparent);
+            __rb_rotate_left(gparent, root);
+        }
+    }
+
+    rb_set_black(root->rb_node);
+}
+EXPORT_SYMBOL(rb_insert_color);
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+                             struct rb_root *root)
+{
+    struct rb_node *other;
+
+    while ((!node || rb_is_black(node)) && node != root->rb_node)
+    {
+        if (parent->rb_left == node)
+        {
+            other = parent->rb_right;
+            if (rb_is_red(other))
+            {
+                rb_set_black(other);
+                rb_set_red(parent);
+                __rb_rotate_left(parent, root);
+                other = parent->rb_right;
+            }
+            if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+                (!other->rb_right || rb_is_black(other->rb_right)))
+            {
+                rb_set_red(other);
+                node = parent;
+                parent = rb_parent(node);
+            }
+            else
+            {
+                if (!other->rb_right || rb_is_black(other->rb_right))
+                {
+                    struct rb_node *o_left;
+                    if ((o_left = other->rb_left))
+                        rb_set_black(o_left);
+                    rb_set_red(other);
+                    __rb_rotate_right(other, root);
+                    other = parent->rb_right;
+                }
+                rb_set_color(other, rb_color(parent));
+                rb_set_black(parent);
+                if (other->rb_right)
+                    rb_set_black(other->rb_right);
+                __rb_rotate_left(parent, root);
+                node = root->rb_node;
+                break;
+            }
+        }
+        else
+        {
+            other = parent->rb_left;
+            if (rb_is_red(other))
+            {
+                rb_set_black(other);
+                rb_set_red(parent);
+                __rb_rotate_right(parent, root);
+                other = parent->rb_left;
+            }
+            if ((!other->rb_left || rb_is_black(other->rb_left)) &&
+                (!other->rb_right || rb_is_black(other->rb_right)))
+            {
+                rb_set_red(other);
+                node = parent;
+                parent = rb_parent(node);
+            }
+            else
+            {
+                if (!other->rb_left || rb_is_black(other->rb_left))
+                {
+                    register struct rb_node *o_right;
+                    if ((o_right = other->rb_right))
+                        rb_set_black(o_right);
+                    rb_set_red(other);
+                    __rb_rotate_left(other, root);
+                    other = parent->rb_left;
+                }
+                rb_set_color(other, rb_color(parent));
+                rb_set_black(parent);
+                if (other->rb_left)
+                    rb_set_black(other->rb_left);
+                __rb_rotate_right(parent, root);
+                node = root->rb_node;
+                break;
+            }
+        }
+    }
+    if (node)
+        rb_set_black(node);
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+    struct rb_node *child, *parent;
+    int color;
+
+    if (!node->rb_left)
+        child = node->rb_right;
+    else if (!node->rb_right)
+        child = node->rb_left;
+    else
+    {
+        struct rb_node *old = node, *left;
+
+        node = node->rb_right;
+        while ((left = node->rb_left) != NULL)
+            node = left;
+        child = node->rb_right;
+        parent = rb_parent(node);
+        color = rb_color(node);
+
+        if (child)
+            rb_set_parent(child, parent);
+        if (parent == old) {
+            parent->rb_right = child;
+            parent = node;
+        } else
+            parent->rb_left = child;
+
+        node->rb_parent_color = old->rb_parent_color;
+        node->rb_right = old->rb_right;
+        node->rb_left = old->rb_left;
+
+        if (rb_parent(old))
+        {
+            if (rb_parent(old)->rb_left == old)
+                rb_parent(old)->rb_left = node;
+            else
+                rb_parent(old)->rb_right = node;
+        } else
+            root->rb_node = node;
+
+        rb_set_parent(old->rb_left, node);
+        if (old->rb_right)
+            rb_set_parent(old->rb_right, node);
+        goto color;
+    }
+
+    parent = rb_parent(node);
+    color = rb_color(node);
+
+    if (child)
+        rb_set_parent(child, parent);
+    if (parent)
+    {
+        if (parent->rb_left == node)
+            parent->rb_left = child;
+        else
+            parent->rb_right = child;
+    }
+    else
+        root->rb_node = child;
+
+ color:
+    if (color == RB_BLACK)
+        __rb_erase_color(child, parent, root);
+}
+EXPORT_SYMBOL(rb_erase);
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(struct rb_root *root)
+{
+    struct rb_node *n;
+
+    n = root->rb_node;
+    if (!n)
+        return NULL;
+    while (n->rb_left)
+        n = n->rb_left;
+    return n;
+}
+EXPORT_SYMBOL(rb_first);
+
+struct rb_node *rb_last(struct rb_root *root)
+{
+    struct rb_node *n;
+
+    n = root->rb_node;
+    if (!n)
+        return NULL;
+    while (n->rb_right)
+        n = n->rb_right;
+    return n;
+}
+EXPORT_SYMBOL(rb_last);
+
+struct rb_node *rb_next(struct rb_node *node)
+{
+    struct rb_node *parent;
+
+    if (rb_parent(node) == node)
+        return NULL;
+
+    /* If we have a right-hand child, go down and then left as far
+       as we can. */
+    if (node->rb_right) {
+        node = node->rb_right; 
+        while (node->rb_left)
+            node=node->rb_left;
+        return node;
+    }
+
+    /* No right-hand children.  Everything down and left is
+       smaller than us, so any 'next' node must be in the general
+       direction of our parent. Go up the tree; any time the
+       ancestor is a right-hand child of its parent, keep going
+       up. First time it's a left-hand child of its parent, said
+       parent is our 'next' node. */
+    while ((parent = rb_parent(node)) && node == parent->rb_right)
+        node = parent;
+
+    return parent;
+}
+EXPORT_SYMBOL(rb_next);
+
+struct rb_node *rb_prev(struct rb_node *node)
+{
+    struct rb_node *parent;
+
+    if (rb_parent(node) == node)
+        return NULL;
+
+    /* If we have a left-hand child, go down and then right as far
+       as we can. */
+    if (node->rb_left) {
+        node = node->rb_left; 
+        while (node->rb_right)
+            node=node->rb_right;
+        return node;
+    }
+
+    /* No left-hand children. Go up till we find an ancestor which
+       is a right-hand child of its parent */
+    while ((parent = rb_parent(node)) && node == parent->rb_left)
+        node = parent;
+
+    return parent;
+}
+EXPORT_SYMBOL(rb_prev);
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+                     struct rb_root *root)
+{
+    struct rb_node *parent = rb_parent(victim);
+
+    /* Set the surrounding nodes to point to the replacement */
+    if (parent) {
+        if (victim == parent->rb_left)
+            parent->rb_left = new;
+        else
+            parent->rb_right = new;
+    } else {
+        root->rb_node = new;
+    }
+    if (victim->rb_left)
+        rb_set_parent(victim->rb_left, new);
+    if (victim->rb_right)
+        rb_set_parent(victim->rb_right, new);
+
+    /* Copy the pointers/colour from the victim to the replacement */
+    *new = *victim;
+}
+EXPORT_SYMBOL(rb_replace_node);