erts: Prepare erl_mmap with tree structures for free seg storage

1 files changed, 972 insertions, 0 deletions

diff --git a/erts/emulator/sys/common/erl_mmap.c b/erts/emulator/sys/common/erl_mmap.c
new file mode 100644
index 0000000000..a16ee7ae39
--- /dev/null
+++ b/erts/emulator/sys/common/erl_mmap.c
@@ -0,0 +1,972 @@
+/*
+ * %CopyrightBegin%
+ *
+ * Copyright Ericsson AB 2002-2013. All Rights Reserved.
+ *
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * %CopyrightEnd%
+ */
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif
+
+#include <sys.h>
+#include <erl_mmap.h>
+#include <stddef.h>
+
+#ifdef DEBUG
+#  define RBT_DEBUG
+#endif
+#ifdef RBT_DEBUG
+#  define RBT_ASSERT	ERTS_ASSERT
+#  define IF_RBT_DEBUG(C) C
+#else
+#  define RBT_ASSERT(x)
+#  define IF_RBT_DEBUG(C)
+#endif
+
+typedef struct RBTNode_ RBTNode;
+struct RBTNode_ {
+    RBTNode *parent;
+    RBTNode *left;
+    RBTNode *right;
+    int flags;
+};
+
+enum SortOrder {
+    ADDR_ORDER,
+    SZ_ADDR_ORDER,
+    SZ_REVERSE_ADDR_ORDER
+};
+
+typedef struct {
+    RBTNode* root;
+    enum SortOrder order;
+}RBTree;
+
+#define RED_FLG      (1)
+#define IS_RED(N)    ((N) && ((N)->flags & RED_FLG))
+#define IS_BLACK(N)  (!IS_RED(N))
+#define SET_RED(N)   ((N)->flags |= RED_FLG)
+#define SET_BLACK(N) ((N)->flags &= ~RED_FLG)
+
+#define HARD_DEBUG /*SVERK*/
+#ifdef HARD_DEBUG
+#  define HARD_CHECK_IS_MEMBER(ROOT,NODE) rbt_assert_is_member(ROOT,NODE)
+#  define HARD_CHECK_TREE(TREE,SZ) check_tree(TREE, SZ)
+static int rbt_assert_is_member(RBTNode* root, RBTNode* node);
+static RBTNode* check_tree(RBTree* tree, Uint);
+#else
+#  define HARD_CHECK_IS_MEMBER(ROOT,NODE)
+#  define HARD_CHECK_TREE(TREE,SZ)
+#endif
+
+
+typedef struct {
+    RBTNode snode;
+    RBTNode anode;
+    char* start;
+    char* end;
+}ErtsFreeSegDesc;
+
+static ERTS_INLINE ErtsFreeSegDesc* anode_to_desc(RBTNode* anode)
+{
+    return (ErtsFreeSegDesc*) ((char*)anode - offsetof(ErtsFreeSegDesc, anode));
+}
+
+static ERTS_INLINE ErtsFreeSegDesc* snode_to_desc(RBTNode* snode)
+{
+    return (ErtsFreeSegDesc*) ((char*)snode - offsetof(ErtsFreeSegDesc, snode));
+}
+
+static ERTS_INLINE ErtsFreeSegDesc* node_to_desc(enum SortOrder order, RBTNode* node)
+{
+    return order==ADDR_ORDER ? anode_to_desc(node) : snode_to_desc(node);
+}
+
+typedef struct {
+    RBTree stree;
+    RBTree atree;
+}ErtsFreeSegMap;
+
+
+#ifdef HARD_DEBUG
+static ERTS_INLINE SWord cmp_blocks(enum SortOrder order,
+                                     RBTNode* lhs, RBTNode* rhs)
+{
+    ErtsFreeSegDesc* ldesc = node_to_desc(order, lhs);
+    ErtsFreeSegDesc* rdesc = node_to_desc(order, rhs);
+    RBT_ASSERT(lhs != rhs);
+    if (order != ADDR_ORDER) {
+        SWord lsz = ldesc->end - ldesc->start;
+        SWord rsz = rdesc->end - rdesc->start;
+	SWord diff = lsz - rsz;
+	if (diff) return diff;
+    }
+    if (order != SZ_REVERSE_ADDR_ORDER) {
+        return (char*)ldesc->start - (char*)rdesc->start;
+    }
+    else {
+        return (char*)rdesc->start - (char*)ldesc->start;
+    }
+}
+#endif
+
+static ERTS_INLINE SWord cmp_with_block(enum SortOrder order,
+                                        SWord sz, char* addr, RBTNode* rhs)
+{
+    ErtsFreeSegDesc* rdesc;
+    if (order != ADDR_ORDER) {
+        rdesc = snode_to_desc(rhs);
+        {
+            SWord rhs_sz = rdesc->end - rdesc->start;
+            SWord diff = sz - rhs_sz;
+            if (diff) return diff;
+        }
+    }
+    else
+        rdesc = anode_to_desc(rhs);
+
+    if (order != SZ_REVERSE_ADDR_ORDER)
+        return addr - (char*)rdesc->start;
+    else
+        return (char*)rdesc->start - addr;
+}
+
+
+static ERTS_INLINE void
+left_rotate(RBTNode **root, RBTNode *x)
+{
+    RBTNode *y = x->right;
+    x->right = y->left;
+    if (y->left)
+	y->left->parent = x;
+    y->parent = x->parent;
+    if (!y->parent) {
+	RBT_ASSERT(*root == x);
+	*root = y;
+    }
+    else if (x == x->parent->left)
+	x->parent->left = y;
+    else {
+	RBT_ASSERT(x == x->parent->right);
+	x->parent->right = y;
+    }
+    y->left = x;
+    x->parent = y;
+
+    /*SVERK y->max_sz = x->max_sz;
+    x->max_sz = node_max_size(x);
+    ASSERT(y->max_sz >= x->max_sz);*/
+}
+
+static ERTS_INLINE void
+right_rotate(RBTNode **root, RBTNode *x)
+{
+    RBTNode *y = x->left;
+    x->left = y->right;
+    if (y->right)
+	y->right->parent = x;
+    y->parent = x->parent;
+    if (!y->parent) {
+	RBT_ASSERT(*root == x);
+	*root = y;
+    }
+    else if (x == x->parent->right)
+	x->parent->right = y;
+    else {
+	RBT_ASSERT(x == x->parent->left);
+	x->parent->left = y;
+    }
+    y->right = x;
+    x->parent = y;
+    /*SVERK y->max_sz = x->max_sz;
+    x->max_sz = node_max_size(x);
+    ASSERT(y->max_sz >= x->max_sz);*/
+}
+
+/*
+ * Replace node x with node y
+ * NOTE: block header of y is not changed
+ */
+static ERTS_INLINE void
+replace(RBTNode **root, RBTNode *x, RBTNode *y)
+{
+
+    if (!x->parent) {
+	RBT_ASSERT(*root == x);
+	*root = y;
+    }
+    else if (x == x->parent->left)
+	x->parent->left = y;
+    else {
+	RBT_ASSERT(x == x->parent->right);
+	x->parent->right = y;
+    }
+    if (x->left) {
+	RBT_ASSERT(x->left->parent == x);
+	x->left->parent = y;
+    }
+    if (x->right) {
+	RBT_ASSERT(x->right->parent == x);
+	x->right->parent = y;
+    }
+
+    y->flags	= x->flags;
+    y->parent	= x->parent;
+    y->right	= x->right;
+    y->left	= x->left;
+    /*SVERK y->max_sz   = x->max_sz;*/
+}
+
+static void
+tree_insert_fixup(RBTNode** root, RBTNode *blk)
+{
+    RBTNode *x = blk, *y;
+
+    /*
+     * Rearrange the tree so that it satisfies the Red-Black Tree properties
+     */
+
+    RBT_ASSERT(x != *root && IS_RED(x->parent));
+    do {
+
+	/*
+	 * x and its parent are both red. Move the red pair up the tree
+	 * until we get to the root or until we can separate them.
+	 */
+
+	RBT_ASSERT(IS_RED(x));
+	RBT_ASSERT(IS_BLACK(x->parent->parent));
+	RBT_ASSERT(x->parent->parent);
+
+	if (x->parent == x->parent->parent->left) {
+	    y = x->parent->parent->right;
+	    if (IS_RED(y)) {
+		SET_BLACK(y);
+		x = x->parent;
+		SET_BLACK(x);
+		x = x->parent;
+		SET_RED(x);
+	    }
+	    else {
+
+		if (x == x->parent->right) {
+		    x = x->parent;
+		    left_rotate(root, x);
+		}
+
+		RBT_ASSERT(x == x->parent->parent->left->left);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent));
+		RBT_ASSERT(IS_BLACK(x->parent->parent));
+		RBT_ASSERT(IS_BLACK(y));
+
+		SET_BLACK(x->parent);
+		SET_RED(x->parent->parent);
+		right_rotate(root, x->parent->parent);
+
+		RBT_ASSERT(x == x->parent->left);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent->right));
+		RBT_ASSERT(IS_BLACK(x->parent));
+		break;
+	    }
+	}
+	else {
+	    RBT_ASSERT(x->parent == x->parent->parent->right);
+	    y = x->parent->parent->left;
+	    if (IS_RED(y)) {
+		SET_BLACK(y);
+		x = x->parent;
+		SET_BLACK(x);
+		x = x->parent;
+		SET_RED(x);
+	    }
+	    else {
+
+		if (x == x->parent->left) {
+		    x = x->parent;
+		    right_rotate(root, x);
+		}
+
+		RBT_ASSERT(x == x->parent->parent->right->right);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent));
+		RBT_ASSERT(IS_BLACK(x->parent->parent));
+		RBT_ASSERT(IS_BLACK(y));
+
+		SET_BLACK(x->parent);
+		SET_RED(x->parent->parent);
+		left_rotate(root, x->parent->parent);
+
+		RBT_ASSERT(x == x->parent->right);
+		RBT_ASSERT(IS_RED(x));
+		RBT_ASSERT(IS_RED(x->parent->left));
+		RBT_ASSERT(IS_BLACK(x->parent));
+		break;
+	    }
+	}
+    } while (x != *root && IS_RED(x->parent));
+
+    SET_BLACK(*root);
+}
+
+static void
+rbt_delete(RBTNode** root, RBTNode* del)
+{
+    Uint spliced_is_black;
+    RBTNode *x, *y, *z = del;
+    RBTNode null_x; /* null_x is used to get the fixup started when we
+			splice out a node without children. */
+
+    HARD_CHECK_IS_MEMBER(*root, del);
+
+    null_x.parent = NULL;
+
+    /* Remove node from tree... */
+
+    /* Find node to splice out */
+    if (!z->left || !z->right)
+	y = z;
+    else
+	/* Set y to z:s successor */
+	for(y = z->right; y->left; y = y->left);
+    /* splice out y */
+    x = y->left ? y->left : y->right;
+    spliced_is_black = IS_BLACK(y);
+    if (x) {
+	x->parent = y->parent;
+    }
+    else if (spliced_is_black) {
+	x = &null_x;
+	x->flags = 0;
+	SET_BLACK(x);
+	x->right = x->left = NULL;
+        /*SVERK x->max_sz = 0;*/
+	x->parent = y->parent;
+	y->left = x;
+    }
+
+    if (!y->parent) {
+	RBT_ASSERT(*root == y);
+	*root = x;
+    }
+    else {
+	if (y == y->parent->left) {
+	    y->parent->left = x;
+	}
+	else {
+	    RBT_ASSERT(y == y->parent->right);
+	    y->parent->right = x;
+	}
+	/*SVERK if (y->parent != z) {
+	    lower_max_size(y->parent, (y==z ? NULL : z));
+	}*/
+    }
+    if (y != z) {
+	/* We spliced out the successor of z; replace z by the successor */
+	RBT_ASSERT(z != &null_x);
+	replace(root, z, y);
+	/*SVERK lower_max_size(y, NULL);*/
+    }
+
+    if (spliced_is_black) {
+	/* We removed a black node which makes the resulting tree
+	   violate the Red-Black Tree properties. Fixup tree... */
+
+	while (IS_BLACK(x) && x->parent) {
+
+	    /*
+	     * x has an "extra black" which we move up the tree
+	     * until we reach the root or until we can get rid of it.
+	     *
+	     * y is the sibbling of x
+	     */
+
+	    if (x == x->parent->left) {
+		y = x->parent->right;
+		RBT_ASSERT(y);
+		if (IS_RED(y)) {
+		    RBT_ASSERT(y->right);
+		    RBT_ASSERT(y->left);
+		    SET_BLACK(y);
+		    RBT_ASSERT(IS_BLACK(x->parent));
+		    SET_RED(x->parent);
+		    left_rotate(root, x->parent);
+		    y = x->parent->right;
+		}
+		RBT_ASSERT(y);
+		RBT_ASSERT(IS_BLACK(y));
+		if (IS_BLACK(y->left) && IS_BLACK(y->right)) {
+		    SET_RED(y);
+		    x = x->parent;
+		}
+		else {
+		    if (IS_BLACK(y->right)) {
+			SET_BLACK(y->left);
+			SET_RED(y);
+			right_rotate(root, y);
+			y = x->parent->right;
+		    }
+		    RBT_ASSERT(y);
+		    if (IS_RED(x->parent)) {
+
+			SET_BLACK(x->parent);
+			SET_RED(y);
+		    }
+		    RBT_ASSERT(y->right);
+		    SET_BLACK(y->right);
+		    left_rotate(root, x->parent);
+		    x = *root;
+		    break;
+		}
+	    }
+	    else {
+		RBT_ASSERT(x == x->parent->right);
+		y = x->parent->left;
+		RBT_ASSERT(y);
+		if (IS_RED(y)) {
+		    RBT_ASSERT(y->right);
+		    RBT_ASSERT(y->left);
+		    SET_BLACK(y);
+		    RBT_ASSERT(IS_BLACK(x->parent));
+		    SET_RED(x->parent);
+		    right_rotate(root, x->parent);
+		    y = x->parent->left;
+		}
+		RBT_ASSERT(y);
+		RBT_ASSERT(IS_BLACK(y));
+		if (IS_BLACK(y->right) && IS_BLACK(y->left)) {
+		    SET_RED(y);
+		    x = x->parent;
+		}
+		else {
+		    if (IS_BLACK(y->left)) {
+			SET_BLACK(y->right);
+			SET_RED(y);
+			left_rotate(root, y);
+			y = x->parent->left;
+		    }
+		    RBT_ASSERT(y);
+		    if (IS_RED(x->parent)) {
+			SET_BLACK(x->parent);
+			SET_RED(y);
+		    }
+		    RBT_ASSERT(y->left);
+		    SET_BLACK(y->left);
+		    right_rotate(root, x->parent);
+		    x = *root;
+		    break;
+		}
+	    }
+	}
+	SET_BLACK(x);
+
+	if (null_x.parent) {
+	    if (null_x.parent->left == &null_x)
+		null_x.parent->left = NULL;
+	    else {
+		RBT_ASSERT(null_x.parent->right == &null_x);
+		null_x.parent->right = NULL;
+	    }
+	    RBT_ASSERT(!null_x.left);
+	    RBT_ASSERT(!null_x.right);
+	}
+	else if (*root == &null_x) {
+	    *root = NULL;
+	    RBT_ASSERT(!null_x.left);
+	    RBT_ASSERT(!null_x.right);
+	}
+    }
+}
+
+
+static void
+rbt_insert(enum SortOrder order, RBTNode** root, RBTNode* blk)
+{
+#ifdef RBT_DEBUG
+    ErtsFreeSegDesc *dbg_under=NULL, *dbg_over=NULL;
+#endif
+    ErtsFreeSegDesc* desc = node_to_desc(order, blk);
+    char* blk_addr = desc->start;
+    SWord blk_sz = desc->end - desc->start;
+    /*SVERK Uint blk_sz = AOFF_BLK_SZ(blk);*/
+
+    blk->flags  = 0;
+    blk->left	= NULL;
+    blk->right	= NULL;
+    /*SVERK blk->max_sz = blk_sz;*/
+
+    if (!*root) {
+	blk->parent = NULL;
+	SET_BLACK(blk);
+	*root = blk;
+    }
+    else {
+	RBTNode *x = *root;
+	while (1) {
+	    SWord diff;
+	    /*SVERK if (x->max_sz < blk_sz) {
+		x->max_sz = blk_sz;
+	    }*/
+	    diff = cmp_with_block(order, blk_sz, blk_addr, x);
+	    if (diff < 0) {
+                IF_RBT_DEBUG(dbg_over = node_to_desc(order, x));
+		if (!x->left) {
+		    blk->parent = x;
+		    x->left = blk;
+		    break;
+		}
+		x = x->left;
+	    }
+	    else {
+                RBT_ASSERT(diff > 0);
+                IF_RBT_DEBUG(dbg_under = node_to_desc(order, x));
+                if (!x->right) {
+                    blk->parent = x;
+                    x->right = blk;
+                    break;
+                }
+                x = x->right;
+            }
+	    /*SVERK else {
+		ASSERT(flavor == AOFF_BF);
+		ASSERT(blk->flags & IS_BF_FLG);
+		ASSERT(x->flags & IS_BF_FLG);
+		SET_LIST_ELEM(blk);
+		LIST_NEXT(blk) = LIST_NEXT(x);
+		LIST_PREV(blk) = x;
+		if (LIST_NEXT(x))
+		    LIST_PREV(LIST_NEXT(x)) = blk;
+		LIST_NEXT(x) = blk;
+		return;
+	    }*/
+	}
+
+	/* Insert block into size tree */
+	RBT_ASSERT(blk->parent);
+#ifdef RBT_DEBUG
+        if (!order) {
+            RBT_ASSERT(!dbg_under || dbg_under->end < desc->start);
+            RBT_ASSERT(!dbg_over || dbg_over->start > desc->end);
+        }
+#endif
+	SET_RED(blk);
+	if (IS_RED(blk->parent))
+	    tree_insert_fixup(root, blk);
+    }
+    /*SVERK if (flavor == AOFF_BF) {
+	SET_TREE_NODE(blk);
+	LIST_NEXT(blk) = NULL;
+    }*/
+}
+
+
+/* The API to keep track of a bunch of separated free segments
+   (non-overlapping and non-adjacent).
+ */
+static void init_free_seg_map(ErtsFreeSegMap*, int reverse_ao);
+static void adjacent_free_seg(ErtsFreeSegMap*, char* start, char* end,
+                              ErtsFreeSegDesc** under, ErtsFreeSegDesc** over);
+static void insert_free_seg(ErtsFreeSegMap*, ErtsFreeSegDesc*, char* start, char* end);
+static void resize_free_seg(ErtsFreeSegMap*, ErtsFreeSegDesc*, char* start, char* end);
+static void delete_free_seg(ErtsFreeSegMap*, ErtsFreeSegDesc*);
+static ErtsFreeSegDesc* lookup_free_seg(ErtsFreeSegMap*, SWord sz);
+
+
+static void init_free_seg_map(ErtsFreeSegMap* map, int reverse_ao)
+{
+    map->atree.root = NULL;
+    map->atree.order = ADDR_ORDER;
+    map->stree.root = NULL;
+    map->stree.order = reverse_ao ? SZ_REVERSE_ADDR_ORDER : SZ_ADDR_ORDER;
+}
+
+static void adjacent_free_seg(ErtsFreeSegMap* map, char* start, char* end,
+                              ErtsFreeSegDesc** under, ErtsFreeSegDesc** over)
+{
+    RBTNode* x = map->atree.root;
+
+    *under = NULL;
+    *over = NULL;
+    while (x) {
+	if (start < anode_to_desc(x)->start) {
+            RBT_ASSERT(end <= anode_to_desc(x)->start);
+            if (end == anode_to_desc(x)->start) {
+                RBT_ASSERT(!*over);
+                *over = anode_to_desc(x);
+            }
+            x = x->left;
+	}
+	else {
+            RBT_ASSERT(start >= anode_to_desc(x)->end);
+            if (start == anode_to_desc(x)->end) {
+                RBT_ASSERT(!*under);
+                *under = anode_to_desc(x);
+            }
+            x = x->right;
+        }
+    }
+}
+
+static void insert_free_seg(ErtsFreeSegMap* map, ErtsFreeSegDesc* desc,
+                            char* start, char* end)
+{
+    desc->start = start;
+    desc->end = end;
+    rbt_insert(map->atree.order, &map->atree.root, &desc->anode);
+    rbt_insert(map->stree.order, &map->stree.root, &desc->snode);
+}
+
+static void resize_free_seg(ErtsFreeSegMap* map, ErtsFreeSegDesc* desc,
+                            char* start, char* end)
+{
+#ifdef DEBUG
+    ErtsFreeSegDesc *dbg_under, *dbg_over;
+    rbt_delete(&map->atree.root, &desc->anode);
+    adjacent_free_seg(map, start, end, &dbg_under, &dbg_over);
+    RBT_ASSERT(dbg_under == NULL && dbg_over == NULL);
+    rbt_insert(map->atree.order, &map->atree.root, &desc->anode);
+#endif
+    rbt_delete(&map->stree.root, &desc->snode);
+    desc->start = start;
+    desc->end = end;
+    rbt_insert(map->stree.order, &map->stree.root, &desc->snode);
+}
+
+static void delete_free_seg(ErtsFreeSegMap* map, ErtsFreeSegDesc* desc)
+{
+    rbt_delete(&map->atree.root, &desc->anode);
+    rbt_delete(&map->stree.root, &desc->snode);
+}
+
+static ErtsFreeSegDesc* lookup_free_seg(ErtsFreeSegMap* map, SWord need_sz)
+{
+    RBTNode* x = map->stree.root;
+    ErtsFreeSegDesc* best_desc = NULL;
+
+    while (x) {
+        ErtsFreeSegDesc* desc = snode_to_desc(x);
+        SWord seg_sz = desc->end - desc->start;
+
+	if (seg_sz < need_sz) {
+	    x = x->right;
+	}
+	else {
+            best_desc = desc;
+	    x = x->left;
+	}
+    }
+    return best_desc;
+}
+
+
+void erts_mmap_init(ErtsMMapInit* init)
+{
+#ifdef HARD_DEBUG
+    erts_fprintf(stderr, "SVERK: scs = %bpu\n", init->scs);
+    erts_fprintf(stderr, "SVERK: sco = %i\n", init->sco);
+    erts_fprintf(stderr, "SVERK: scmgc = %i\n", init->scmgc);
+
+    {
+        void test_it(void);
+        test_it();
+    }
+#endif
+}
+
+
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+ * Debug functions                                                           *
+\*                                                                           */
+
+
+#ifdef HARD_DEBUG
+
+static int rbt_assert_is_member(RBTNode* root, RBTNode* node)
+{
+    while (node != root) {
+	RBT_ASSERT(node->parent);
+	RBT_ASSERT(node->parent->left == node || node->parent->right == node);
+	node = node->parent;
+    }
+    return 1;
+}
+
+#define LEFT_VISITED_FLG 0x1000
+#define THIS_VISITED_FLG 0x100
+#define RIGHT_VISITED_FLG 0x10
+#define IS_LEFT_VISITED(FB)	((FB)->flags & LEFT_VISITED_FLG)
+#define IS_THIS_VISITED(FB)	((FB)->flags & THIS_VISITED_FLG)
+#define IS_RIGHT_VISITED(FB)	((FB)->flags & RIGHT_VISITED_FLG)
+
+#define SET_LEFT_VISITED(FB)	((FB)->flags |= LEFT_VISITED_FLG)
+#define SET_THIS_VISITED(FB)	((FB)->flags |= THIS_VISITED_FLG)
+#define SET_RIGHT_VISITED(FB)	((FB)->flags |= RIGHT_VISITED_FLG)
+
+#define UNSET_LEFT_VISITED(FB)	((FB)->flags &= ~LEFT_VISITED_FLG)
+#define UNSET_THIS_VISITED(FB)	((FB)->flags &= ~THIS_VISITED_FLG)
+#define UNSET_RIGHT_VISITED(FB)	((FB)->flags &= ~RIGHT_VISITED_FLG)
+
+
+
+#if 1 /*SVERK*/
+#  define PRINT_TREE
+#else
+#  undef PRINT_TREE
+#endif
+
+#ifdef PRINT_TREE
+static void print_tree(enum SortOrder order, RBTNode*);
+#endif
+
+/*
+ * Checks that the order between parent and children are correct,
+ * and that the Red-Black Tree properies are satisfied. if size > 0,
+ * check_tree() returns the node that satisfies "address order first fit"
+ *
+ * The Red-Black Tree properies are:
+ *   1. Every node is either red or black.
+ *   2. Every leaf (NIL) is black.
+ *   3. If a node is red, then both its children are black.
+ *   4. Every simple path from a node to a descendant leaf
+ *      contains the same number of black nodes.
+ *
+ */
+
+static RBTNode *
+check_tree(RBTree* tree, Uint size)
+{
+    RBTNode *res = NULL;
+    Sint blacks;
+    Sint curr_blacks;
+    RBTNode *x;
+    Uint depth, max_depth, node_cnt;
+    ErtsFreeSegDesc* seg = NULL;
+    ErtsFreeSegDesc* prev_seg = NULL;
+
+#ifdef PRINT_TREE
+    print_tree(tree->order, tree->root);
+#endif
+
+    if (!tree->root)
+	return res;
+
+    x = tree->root;
+    RBT_ASSERT(IS_BLACK(x));
+    RBT_ASSERT(!x->parent);
+    curr_blacks = 1;
+    blacks = -1;
+    depth = 1;
+    max_depth = 0;
+    node_cnt = 0;
+
+    /* Traverse tree in sorting order */
+    while (x) {
+	if (!IS_LEFT_VISITED(x)) {
+	    SET_LEFT_VISITED(x);
+	    if (x->left) {
+		x = x->left;
+		++depth;
+		if (IS_BLACK(x))
+		    curr_blacks++;
+		continue;
+	    }
+	    else {
+		if (blacks < 0)
+		    blacks = curr_blacks;
+		RBT_ASSERT(blacks == curr_blacks);
+	    }
+	}
+
+        if (!IS_THIS_VISITED(x)) {
+            SET_THIS_VISITED(x);
+            ++node_cnt;
+            if (depth > max_depth)
+                max_depth = depth;
+
+            if (IS_RED(x)) {
+                RBT_ASSERT(IS_BLACK(x->right));
+                RBT_ASSERT(IS_BLACK(x->left));
+            }
+
+            RBT_ASSERT(x->parent || x == tree->root);
+
+            if (x->left) {
+                RBT_ASSERT(x->left->parent == x);
+                RBT_ASSERT(cmp_blocks(tree->order, x->left, x) < 0);
+            }
+
+            if (x->right) {
+                RBT_ASSERT(x->right->parent == x);
+                RBT_ASSERT(cmp_blocks(tree->order, x->right, x) > 0);
+            }
+
+            seg = node_to_desc(tree->order, x);
+            RBT_ASSERT(seg->start < seg->end);
+            if (size && (seg->end - seg->start) >= size) {
+                if (!res || cmp_blocks(tree->order, x, res) < 0) {
+                    res = x;
+                }
+            }
+            if (tree->order == ADDR_ORDER) {
+                RBT_ASSERT(!prev_seg || prev_seg->end < seg->start);
+                prev_seg = seg;
+            }
+
+        }
+	if (!IS_RIGHT_VISITED(x)) {
+	    SET_RIGHT_VISITED(x);
+	    if (x->right) {
+		x = x->right;
+		++depth;
+		if (IS_BLACK(x))
+		    curr_blacks++;
+		continue;
+	    }
+	    else {
+		if (blacks < 0)
+		    blacks = curr_blacks;
+		RBT_ASSERT(blacks == curr_blacks);
+	    }
+	}
+
+	UNSET_LEFT_VISITED(x);
+        UNSET_THIS_VISITED(x);
+        UNSET_RIGHT_VISITED(x);
+	if (IS_BLACK(x))
+	    curr_blacks--;
+	x = x->parent;
+	--depth;
+    }
+    RBT_ASSERT(depth == 0 || (!tree->root && depth==1));
+    RBT_ASSERT(curr_blacks == 0);
+    RBT_ASSERT((1 << (max_depth/2)) <= node_cnt);
+
+    UNSET_LEFT_VISITED(tree->root);
+    UNSET_THIS_VISITED(tree->root);
+    UNSET_RIGHT_VISITED(tree->root);
+
+    return res;
+}
+
+
+#ifdef PRINT_TREE
+#define INDENT_STEP 2
+
+#include <stdio.h>
+
+static void
+print_tree_aux(enum SortOrder order, RBTNode *x, int indent)
+{
+    int i;
+
+    if (x) {
+        ErtsFreeSegDesc* desc = node_to_desc(order, x);
+	print_tree_aux(order, x->right, indent + INDENT_STEP);
+	for (i = 0; i < indent; i++) {
+	    putc(' ', stderr);
+	}
+	fprintf(stderr, "%s: sz=%lx [%p - %p] desc=%p\r\n",
+		IS_BLACK(x) ? "BLACK" : "RED",
+                desc->end - desc->start, desc->start, desc->end, desc);
+	print_tree_aux(order, x->left,  indent + INDENT_STEP);
+    }
+}
+
+
+static void
+print_tree(enum SortOrder order, RBTNode* root)
+{
+    static const char* type[] = {"Address","Size-Address","Size-RevAddress"};
+    fprintf(stderr, " --- %s ordered tree begin ---\r\n", type[order]);
+    print_tree_aux(order, root, 0);
+    fprintf(stderr, " --- %s ordered tree end ---\r\n", type[order]);
+}
+
+#endif /* PRINT_TREE */
+
+
+static ErtsFreeSegDesc* new_desc(void)
+{
+    return (ErtsFreeSegDesc*) malloc(sizeof(ErtsFreeSegDesc));
+}
+
+void test_it(void)
+{
+    ErtsFreeSegMap map;
+    ErtsFreeSegDesc *desc, *under, *over, *d1, *d2;
+    int i;
+
+    for (i=0; i<2; i++) {
+        init_free_seg_map(&map, i);
+
+        insert_free_seg(&map, new_desc(), (char*)0x11000, (char*)0x12000);
+        check_tree(&map.atree, 0); check_tree(&map.stree, 0);
+        insert_free_seg(&map, new_desc(), (char*)0x13000, (char*)0x14000);
+        check_tree(&map.atree, 0); check_tree(&map.stree, 0);
+        insert_free_seg(&map, new_desc(), (char*)0x15000, (char*)0x17000);
+        check_tree(&map.atree, 0); check_tree(&map.stree, 0);
+        insert_free_seg(&map, new_desc(), (char*)0x8000, (char*)0x10000);
+        check_tree(&map.atree, 0); check_tree(&map.stree, 0);
+
+        desc = lookup_free_seg(&map, 0x500);
+        ERTS_ASSERT(desc->start == (char*)(i?0x13000L:0x11000L));
+
+        desc = lookup_free_seg(&map, 0x1500);
+        ERTS_ASSERT(desc->start == (char*)0x15000);
+
+        adjacent_free_seg(&map, (char*)0x6666, (char*)0x7777, &under, &over);
+        ERTS_ASSERT(!under && !over);
+
+        adjacent_free_seg(&map, (char*)0x6666, (char*)0x8000, &under, &over);
+        ERTS_ASSERT(!under && over->start == (char*)0x8000);
+
+        adjacent_free_seg(&map, (char*)0x10000, (char*)0x10500, &under, &over);
+        ERTS_ASSERT(under->end == (char*)0x10000 && !over);
+
+        adjacent_free_seg(&map, (char*)0x10100, (char*)0x10500, &under, &over);
+        ERTS_ASSERT(!under && !over);
+
+        adjacent_free_seg(&map, (char*)0x10100, (char*)0x11000, &under, &over);
+        ERTS_ASSERT(!under && over && over->start == (char*)0x11000);
+
+        adjacent_free_seg(&map, (char*)0x12000, (char*)0x12500, &under, &over);
+        ERTS_ASSERT(under && under->end == (char*)0x12000 && !over);
+
+        adjacent_free_seg(&map, (char*)0x12000, (char*)0x13000, &under, &over);
+        ERTS_ASSERT(under && under->end == (char*)0x12000 &&
+                    over && over->start == (char*)0x13000);
+
+        adjacent_free_seg(&map, (char*)0x12500, (char*)0x13000, &under, &over);
+        ERTS_ASSERT(!under && over && over->start == (char*)0x13000);
+
+        d1 = lookup_free_seg(&map, 0x500);
+        ERTS_ASSERT(d1->start == (char*)(i?0x13000L:0x11000L));
+
+        resize_free_seg(&map, d1, d1->start - 0x800, (char*)d1->end);
+        check_tree(&map.atree, 0); check_tree(&map.stree, 0);
+
+        d2 = lookup_free_seg(&map, 0x1200);
+        ERTS_ASSERT(d2 == d1);
+
+        delete_free_seg(&map, d1);
+        check_tree(&map.atree, 0); check_tree(&map.stree, 0);
+
+        d1 = lookup_free_seg(&map, 0x1200);
+        ERTS_ASSERT(d1->start == (char*)0x15000);
+    }
+}
+
+#endif /* HARD_DEBUG */