diff options
Diffstat (limited to 'erts/emulator/sys/common')
| -rw-r--r-- | erts/emulator/sys/common/erl_mmap.c | 972 | ||||
| -rw-r--r-- | erts/emulator/sys/common/erl_mmap.h | 26 | ||||
| -rw-r--r-- | erts/emulator/sys/common/erl_mseg.c | 6 | ||||
| -rw-r--r-- | erts/emulator/sys/common/erl_mseg.h | 2 |
4 files changed, 1005 insertions, 1 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 */ diff --git a/erts/emulator/sys/common/erl_mmap.h b/erts/emulator/sys/common/erl_mmap.h new file mode 100644 index 0000000000..64baa6c493 --- /dev/null +++ b/erts/emulator/sys/common/erl_mmap.h @@ -0,0 +1,26 @@ +/* + * %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% + */ + +typedef struct { + SWord scs; /* super carrier size */ + int sco; /* super carrier only? */ + Uint scmgc; /* super carrier: max guaranteed (number of) carriers */ +}ErtsMMapInit; + +void erts_mmap_init(ErtsMMapInit*); diff --git a/erts/emulator/sys/common/erl_mseg.c b/erts/emulator/sys/common/erl_mseg.c index 2748edba02..64fcb6bb40 100644 --- a/erts/emulator/sys/common/erl_mseg.c +++ b/erts/emulator/sys/common/erl_mseg.c @@ -1668,8 +1668,12 @@ erts_mseg_init(ErtsMsegInit_t *init) erl_exit(ERTS_ABORT_EXIT, "erts_mseg: unable to open /dev/zero\n"); #endif -#if HAVE_MMAP && HALFWORD_HEAP +#if HAVE_MMAP +# if HALFWORD_HEAP initialize_pmmap(); +# else + erts_mmap_init(&init->mmap); +# endif #endif if (!IS_2POW(GET_PAGE_SIZE)) diff --git a/erts/emulator/sys/common/erl_mseg.h b/erts/emulator/sys/common/erl_mseg.h index a1b000f51c..7454e5c473 100644 --- a/erts/emulator/sys/common/erl_mseg.h +++ b/erts/emulator/sys/common/erl_mseg.h @@ -22,6 +22,7 @@ #include "sys.h" #include "erl_alloc_types.h" +#include "erl_mmap.h" #ifndef HAVE_MMAP # define HAVE_MMAP 0 @@ -68,6 +69,7 @@ typedef struct { Uint rmcbf; Uint mcs; Uint nos; + ErtsMMapInit mmap; } ErtsMsegInit_t; #define ERTS_MSEG_INIT_DEFAULT_INITIALIZER \ |