From 94ad6bd0aec9dd41b1bb4d789df313ddcad5af5b Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 16 Jun 2011 15:26:29 +0200 Subject: New allocator: Address order first fit (aoff) --- erts/doc/src/erts_alloc.xml | 14 +- erts/emulator/Makefile.in | 2 +- erts/emulator/beam/erl_alloc.c | 31 +- erts/emulator/beam/erl_ao_firstfit_alloc.c | 972 +++++++++++++++++++++ erts/emulator/beam/erl_ao_firstfit_alloc.h | 60 ++ erts/emulator/beam/erl_bestfit_alloc.c | 1 + .../test/alloc_SUITE_data/allocator_test.h | 20 +- erts/emulator/test/alloc_SUITE_data/coalesce.c | 2 +- erts/emulator/test/alloc_SUITE_data/rbtree.c | 86 +- 9 files changed, 1153 insertions(+), 35 deletions(-) create mode 100644 erts/emulator/beam/erl_ao_firstfit_alloc.c create mode 100644 erts/emulator/beam/erl_ao_firstfit_alloc.h (limited to 'erts') diff --git a/erts/doc/src/erts_alloc.xml b/erts/doc/src/erts_alloc.xml index 452e5d990e..90347824d5 100644 --- a/erts/doc/src/erts_alloc.xml +++ b/erts/doc/src/erts_alloc.xml @@ -180,6 +180,14 @@ used. The time complexity is proportional to log N, where N is the number of free blocks.

+ Address order first fit + +

Strategy: Find the block with the lowest address that satisfies the + requested block size.

+

Implementation: A balanced binary search tree is + used. The time complexity is proportional to log N, where + N is the number of free blocks.

+ Good fit

Strategy: Try to find the best fit, but settle for the best fit @@ -320,11 +328,11 @@ subsystem identifier, only the specific allocator identified will be effected:

- as bf|aobf|gf|af]]> + as bf|aobf|aoff|gf|af]]> Allocation strategy. Valid strategies are bf (best fit), - aobf (address order best fit), gf (good fit), - and af (a fit). See + aobf (address order best fit), aoff (address order first fit), + gf (good fit), and af (a fit). See the description of allocation strategies in "the alloc_util framework" section. asbcst ]]> diff --git a/erts/emulator/Makefile.in b/erts/emulator/Makefile.in index d9362a2a8f..b658e79378 100644 --- a/erts/emulator/Makefile.in +++ b/erts/emulator/Makefile.in @@ -742,7 +742,7 @@ RUN_OBJS = \ $(OBJDIR)/erl_bif_re.o $(OBJDIR)/erl_unicode.o \ $(OBJDIR)/packet_parser.o $(OBJDIR)/safe_hash.o \ $(OBJDIR)/erl_zlib.o $(OBJDIR)/erl_nif.o \ - $(OBJDIR)/erl_bif_binary.o + $(OBJDIR)/erl_bif_binary.o $(OBJDIR)/erl_ao_firstfit_alloc.o ifeq ($(TARGET),win32) DRV_OBJS = \ diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c index 840534ec5e..1aa5308a5f 100644 --- a/erts/emulator/beam/erl_alloc.c +++ b/erts/emulator/beam/erl_alloc.c @@ -50,6 +50,9 @@ #include "erl_bestfit_alloc.h" #define GET_ERL_AF_ALLOC_IMPL #include "erl_afit_alloc.h" +#define GET_ERL_AOFF_ALLOC_IMPL +#include "erl_ao_firstfit_alloc.h" + #define ERTS_ALC_DEFAULT_MAX_THR_PREF 16 @@ -85,6 +88,8 @@ typedef union { char align_bfa[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(BFAllctr_t))]; AFAllctr_t afa; char align_afa[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(AFAllctr_t))]; + AOFFAllctr_t aoffa; + char align_aoffa[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(AOFFAllctr_t))]; } ErtsAllocatorState_t; static ErtsAllocatorState_t sbmbc_alloc_state; @@ -122,7 +127,8 @@ static void *fix_core_alloc(Uint size) enum allctr_type { GOODFIT, BESTFIT, - AFIT + AFIT, + AOFIRSTFIT }; struct au_init { @@ -134,6 +140,7 @@ struct au_init { GFAllctrInit_t gf; BFAllctrInit_t bf; AFAllctrInit_t af; + AOFFAllctrInit_t aoff; } init; struct { int mmbcs; @@ -147,7 +154,8 @@ struct au_init { ERTS_DEFAULT_ALLCTR_INIT, \ ERTS_DEFAULT_GF_ALLCTR_INIT, \ ERTS_DEFAULT_BF_ALLCTR_INIT, \ - ERTS_DEFAULT_AF_ALLCTR_INIT \ + ERTS_DEFAULT_AF_ALLCTR_INIT, \ + ERTS_DEFAULT_AOFF_ALLCTR_INIT \ } typedef struct { @@ -562,6 +570,7 @@ erts_alloc_init(int *argc, char **argv, ErtsAllocInitOpts *eaiop) erts_afalc_init(); erts_bfalc_init(); erts_gfalc_init(); + erts_aoffalc_init(); for (i = ERTS_ALC_A_MIN; i <= ERTS_ALC_A_MAX; i++) { erts_allctrs[i].alloc = NULL; @@ -903,6 +912,12 @@ start_au_allocator(ErtsAlcType_t alctr_n, &init->init.af, &init->init.util); break; + case AOFIRSTFIT: + as = (void *) erts_aoffalc_start((AOFFAllctr_t *) as0, + &init->init.aoff, + &init->init.util); + break; + default: as = NULL; ASSERT(0); @@ -1097,6 +1112,9 @@ handle_au_arg(struct au_init *auip, else if (strcmp("af", alg) == 0) { auip->atype = AFIT; } + else if (strcmp("aoff", alg) == 0) { + auip->atype = AOFIRSTFIT; + } else { bad_value(param, sub_param + 1, alg); } @@ -2982,6 +3000,7 @@ unsigned long erts_alc_test(unsigned long op, case 0x2: return erts_bfalc_test(op, a1, a2); case 0x3: return erts_afalc_test(op, a1, a2); case 0x4: return erts_mseg_test(op, a1, a2, a3); + case 0x5: return erts_aoffalc_test(op, a1, a2); case 0xf: switch (op) { case 0xf00: @@ -3061,6 +3080,14 @@ unsigned long erts_alc_test(unsigned long op, &init.init.af, &init.init.util); break; + case AOFIRSTFIT: + allctr = erts_aoffalc_start((AOFFAllctr_t *) + erts_alloc(ERTS_ALC_T_UNDEF, + sizeof(AOFFAllctr_t)), + &init.init.aoff, + &init.init.util); + break; + default: ASSERT(0); allctr = NULL; diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c new file mode 100644 index 0000000000..002852cdad --- /dev/null +++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c @@ -0,0 +1,972 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2003-2009. 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% + */ + + +/* + * Description: An "address order first fit" allocator + * based on a Red-Black (binary search) Tree. The search, + * insert, and delete operations are all O(log n) operations + * on a Red-Black Tree. + * Red-Black Trees are described in "Introduction to Algorithms", + * by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Riverest. + * + * This module is a callback-module for erl_alloc_util.c + * + * Algorithm: The tree nodes are free-blocks ordered in address order. + * Every node also keeps the size of the largest block in its + * sub-tree ('max_size'). By that we can start from root and keep + * left (for low addresses) while dismissing entire sub-trees with + * too small blocks. + * + * Authors: Rickard Green/Sverker Eriksson + */ + + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif +#include "global.h" +#define GET_ERL_AOFF_ALLOC_IMPL +#include "erl_ao_firstfit_alloc.h" + +#ifdef DEBUG +#if 0 +#define HARD_DEBUG +#endif +#else +#undef HARD_DEBUG +#endif + +#define MIN_MBC_SZ (16*1024) +#define MIN_MBC_FIRST_FREE_SZ (4*1024) + +#define TREE_NODE_FLG (((Uint) 1) << 0) +#define RED_FLG (((Uint) 1) << 1) +#ifdef HARD_DEBUG +# define LEFT_VISITED_FLG (((Uint) 1) << 2) +# define RIGHT_VISITED_FLG (((Uint) 1) << 3) +#endif + +#define IS_RED(N) (((AOFF_RBTree_t *) (N)) \ + && ((AOFF_RBTree_t *) (N))->flags & RED_FLG) +#define IS_BLACK(N) (!IS_RED(((AOFF_RBTree_t *) (N)))) + +#define SET_RED(N) (((AOFF_RBTree_t *) (N))->flags |= RED_FLG) +#define SET_BLACK(N) (((AOFF_RBTree_t *) (N))->flags &= ~RED_FLG) + +#undef ASSERT +#define ASSERT ASSERT_EXPR + +#if 1 +#define RBT_ASSERT ASSERT +#else +#define RBT_ASSERT(x) +#endif + + +/* Types... */ +typedef struct AOFF_RBTree_t_ AOFF_RBTree_t; + +struct AOFF_RBTree_t_ { + Block_t hdr; + Uint flags; + AOFF_RBTree_t *parent; + AOFF_RBTree_t *left; + AOFF_RBTree_t *right; + Uint max_sz; /* of all blocks in this sub-tree */ +}; + +#ifdef HARD_DEBUG +static AOFF_RBTree_t * check_tree(AOFF_RBTree_t* root, Uint); +#endif + + +/* Calculate 'max_size' of tree node x by only looking at the direct children + * of x and x itself. + */ +static ERTS_INLINE Uint node_max_size(AOFF_RBTree_t *x) +{ + Uint sz = BLK_SZ(x); + if (x->left && x->left->max_sz > sz) { + sz = x->left->max_sz; + } + if (x->right && x->right->max_sz > sz) { + sz = x->right->max_sz; + } + return sz; +} + +/* Set new possibly lower 'max_size' of node and propagate change toward root +*/ +static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node, + AOFF_RBTree_t* stop_at) +{ + AOFF_RBTree_t* x = node; + Uint old_max = x->max_sz; + Uint new_max = node_max_size(x); + + if (new_max < old_max) { + x->max_sz = new_max; + while ((x=x->parent) != stop_at && x->max_sz == old_max) { + x->max_sz = node_max_size(x); + } + ASSERT(x == stop_at || x->max_sz > old_max); + } + else ASSERT(new_max == old_max); +} + + +/* Prototypes of callback functions */ +static Block_t* aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint, Uint32 flags); +static void aoff_link_free_block(Allctr_t *, Block_t*, Uint32 flags); +static void aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags); + +static Eterm info_options(Allctr_t *, char *, int *, void *, Uint **, Uint *); +static void init_atoms(void); + + + +#ifdef DEBUG + +/* Destroy all tree fields */ +#define DESTROY_TREE_NODE(N) \ + sys_memset((void *) (((Block_t *) (N)) + 1), \ + 0xff, \ + (sizeof(AOFF_RBTree_t) - sizeof(Block_t))) + +#else + +#define DESTROY_TREE_NODE(N) + +#endif + + +static int atoms_initialized = 0; + +void +erts_aoffalc_init(void) +{ + atoms_initialized = 0; +} + +Allctr_t * +erts_aoffalc_start(AOFFAllctr_t *alc, + AOFFAllctrInit_t* aoffinit, + AllctrInit_t *init) +{ + AOFFAllctr_t nulled_state = {{0}}; + /* {{0}} is used instead of {0}, in order to avoid (an incorrect) gcc + warning. gcc warns if {0} is used as initializer of a struct when + the first member is a struct (not if, for example, the third member + is a struct). */ + Allctr_t *allctr = (Allctr_t *) alc; + + sys_memcpy((void *) alc, (void *) &nulled_state, sizeof(AOFFAllctr_t)); + + allctr->mbc_header_size = sizeof(Carrier_t); + allctr->min_mbc_size = MIN_MBC_SZ; + allctr->min_mbc_first_free_size = MIN_MBC_FIRST_FREE_SZ; + allctr->min_block_size = sizeof(AOFF_RBTree_t); + + allctr->vsn_str = ERTS_ALC_AOFF_ALLOC_VSN_STR; + + + /* Callback functions */ + + allctr->get_free_block = aoff_get_free_block; + allctr->link_free_block = aoff_link_free_block; + allctr->unlink_free_block = aoff_unlink_free_block; + allctr->info_options = info_options; + + allctr->get_next_mbc_size = NULL; + allctr->creating_mbc = NULL; + allctr->destroying_mbc = NULL; + allctr->init_atoms = init_atoms; + +#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG + allctr->check_block = NULL; + allctr->check_mbc = NULL; +#endif + + allctr->atoms_initialized = 0; + + if (!erts_alcu_start(allctr, init)) + return NULL; + + return allctr; +} + +/* + * Red-Black Tree operations needed + */ + +static ERTS_INLINE void +left_rotate(AOFF_RBTree_t **root, AOFF_RBTree_t *x) +{ + AOFF_RBTree_t *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; + + 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(AOFF_RBTree_t **root, AOFF_RBTree_t *x) +{ + AOFF_RBTree_t *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; + 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(AOFF_RBTree_t **root, AOFF_RBTree_t *x, AOFF_RBTree_t *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; + + y->max_sz = x->max_sz; + lower_max_size(y, NULL); + DESTROY_TREE_NODE(x); +} + +static void +tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk) +{ + AOFF_RBTree_t *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 +aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags) +{ + AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr; + AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC) + ? &alc->sbmbc_root : &alc->mbc_root); + Uint spliced_is_black; + AOFF_RBTree_t *x, *y, *z = (AOFF_RBTree_t *) del; + AOFF_RBTree_t null_x; /* null_x is used to get the fixup started when we + splice out a node without children. */ + + null_x.parent = NULL; + +#ifdef HARD_DEBUG + check_tree(*root, 0); +#endif + + /* 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; + 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; + } + 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 */ + replace(root, z, y); + } + + 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); + } + } + + DESTROY_TREE_NODE(del); + +#ifdef HARD_DEBUG + check_tree(*root, 0); +#endif +} + +static void +aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags) +{ + AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr; + AOFF_RBTree_t *blk = (AOFF_RBTree_t *) block; + AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC) + ? &alc->sbmbc_root : &alc->mbc_root); + Uint blk_sz = BLK_SZ(blk); + +#ifdef HARD_DEBUG + check_tree(*root, 0); +#endif + + blk->flags = 0; + blk->left = NULL; + blk->right = NULL; + blk->max_sz = blk_sz; + + if (!*root) { + blk->parent = NULL; + SET_BLACK(blk); + *root = blk; + } + else { + AOFF_RBTree_t *x = *root; + while (1) { + if (x->max_sz < blk_sz) { + x->max_sz = blk_sz; + } + if (blk < x) { + if (!x->left) { + blk->parent = x; + x->left = blk; + break; + } + x = x->left; + } + else { + if (!x->right) { + blk->parent = x; + x->right = blk; + break; + } + x = x->right; + } + + } + + /* Insert block into size tree */ + RBT_ASSERT(blk->parent); + + SET_RED(blk); + if (IS_RED(blk->parent)) + tree_insert_fixup(root, blk); + } + +#ifdef HARD_DEBUG + check_tree(*root, 0); +#endif +} + +static Block_t * +aoff_get_free_block(Allctr_t *allctr, Uint size, + Block_t *cand_blk, Uint cand_size, Uint32 flags) +{ + AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr; + AOFF_RBTree_t *x = ((flags & ERTS_ALCU_FLG_SBMBC) + ? alc->sbmbc_root : alc->mbc_root); + AOFF_RBTree_t *blk = NULL; +#ifdef HARD_DEBUG + AOFF_RBTree_t* dbg_blk = check_tree(x, size); +#endif + + ASSERT(!cand_blk || cand_size >= size); + + while (x) { + if (x->left && x->left->max_sz >= size) { + x = x->left; + } + else if (BLK_SZ(x) >= size) { + blk = x; + break; + } + else { + x = x->right; + } + } + +#ifdef HARD_DEBUG + ASSERT(blk == dbg_blk); +#endif + + if (!blk) + return NULL; + + if (cand_blk && cand_blk < &blk->hdr) { + return NULL; /* cand_blk was better */ + } + + aoff_unlink_free_block(allctr, (Block_t *) blk, flags); + + return (Block_t *) blk; +} + + +/* + * info_options() + */ + +static struct { + Eterm as; + Eterm aoff; +#ifdef DEBUG + Eterm end_of_atoms; +#endif +} am; + +static void ERTS_INLINE atom_init(Eterm *atom, char *name) +{ + *atom = am_atom_put(name, strlen(name)); +} +#define AM_INIT(AM) atom_init(&am.AM, #AM) + +static void +init_atoms(void) +{ +#ifdef DEBUG + Eterm *atom; +#endif + + if (atoms_initialized) + return; + +#ifdef DEBUG + for (atom = (Eterm *) &am; atom <= &am.end_of_atoms; atom++) { + *atom = THE_NON_VALUE; + } +#endif + AM_INIT(as); + AM_INIT(aoff); + +#ifdef DEBUG + for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) { + ASSERT(*atom != THE_NON_VALUE); + } +#endif + + atoms_initialized = 1; +} + + +#define bld_uint erts_bld_uint +#define bld_cons erts_bld_cons +#define bld_tuple erts_bld_tuple + +static ERTS_INLINE void +add_2tup(Uint **hpp, Uint *szp, Eterm *lp, Eterm el1, Eterm el2) +{ + *lp = bld_cons(hpp, szp, bld_tuple(hpp, szp, 2, el1, el2), *lp); +} + +static Eterm +info_options(Allctr_t *allctr, + char *prefix, + int *print_to_p, + void *print_to_arg, + Uint **hpp, + Uint *szp) +{ + Eterm res = THE_NON_VALUE; + + if (print_to_p) { + erts_print(*print_to_p, + print_to_arg, + "%sas: %s\n", + prefix, + "aoff"); + } + + if (hpp || szp) { + + if (!atoms_initialized) + erl_exit(1, "%s:%d: Internal error: Atoms not initialized", + __FILE__, __LINE__);; + + res = NIL; + add_2tup(hpp, szp, &res, am.as, am.aoff); + } + + return res; +} + + +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ + * NOTE: erts_aoffalc_test() is only supposed to be used for testing. * + * * + * Keep alloc_SUITE_data/allocator_test.h updated if changes are made * + * to erts_aoffalc_test() * +\* */ + +unsigned long +erts_aoffalc_test(unsigned long op, unsigned long a1, unsigned long a2) +{ + switch (op) { + case 0x500: return (unsigned long) 0; /* IS_AOBF */ + case 0x501: return (unsigned long) ((AOFFAllctr_t *) a1)->mbc_root; + case 0x502: return (unsigned long) ((AOFF_RBTree_t *) a1)->parent; + case 0x503: return (unsigned long) ((AOFF_RBTree_t *) a1)->left; + case 0x504: return (unsigned long) ((AOFF_RBTree_t *) a1)->right; + case 0x506: return (unsigned long) IS_BLACK((AOFF_RBTree_t *) a1); + case 0x508: return (unsigned long) 1; /* IS_AOFF */ + case 0x509: return (unsigned long) ((AOFF_RBTree_t *) a1)->max_sz; + default: ASSERT(0); return ~((unsigned long) 0); + } +} + + +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ + * Debug functions * +\* */ + + +#ifdef HARD_DEBUG + +#define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG) +#define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG) + +#define SET_LEFT_VISITED(FB) ((FB)->flags |= LEFT_VISITED_FLG) +#define SET_RIGHT_VISITED(FB) ((FB)->flags |= RIGHT_VISITED_FLG) + +#define UNSET_LEFT_VISITED(FB) ((FB)->flags &= ~LEFT_VISITED_FLG) +#define UNSET_RIGHT_VISITED(FB) ((FB)->flags &= ~RIGHT_VISITED_FLG) + + +#if 0 +# define PRINT_TREE +#else +# undef PRINT_TREE +#endif + +#ifdef PRINT_TREE +static void print_tree(AOFF_RBTree_t*); +#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. + * + * + own.max_size == MAX(own.size, left.max_size, right.max_size) + */ + +static AOFF_RBTree_t * +check_tree(AOFF_RBTree_t* root, Uint size) +{ + AOFF_RBTree_t *res = NULL; + Sint blacks; + Sint curr_blacks; + AOFF_RBTree_t *x; + +#ifdef PRINT_TREE + print_tree(root); +#endif + + if (!root) + return res; + + x = root; + ASSERT(IS_BLACK(x)); + ASSERT(!x->parent); + curr_blacks = 1; + blacks = -1; + + while (x) { + if (!IS_LEFT_VISITED(x)) { + SET_LEFT_VISITED(x); + if (x->left) { + x = x->left; + if (IS_BLACK(x)) + curr_blacks++; + continue; + } + else { + if (blacks < 0) + blacks = curr_blacks; + ASSERT(blacks == curr_blacks); + } + } + + if (!IS_RIGHT_VISITED(x)) { + SET_RIGHT_VISITED(x); + if (x->right) { + x = x->right; + if (IS_BLACK(x)) + curr_blacks++; + continue; + } + else { + if (blacks < 0) + blacks = curr_blacks; + ASSERT(blacks == curr_blacks); + } + } + + + if (IS_RED(x)) { + ASSERT(IS_BLACK(x->right)); + ASSERT(IS_BLACK(x->left)); + } + + ASSERT(x->parent || x == root); + + if (x->left) { + ASSERT(x->left->parent == x); + ASSERT(x->left < x); + ASSERT(x->left->max_sz <= x->max_sz); + } + + if (x->right) { + ASSERT(x->right->parent == x); + ASSERT(x->right > x); + ASSERT(x->right->max_sz <= x->max_sz); + } + ASSERT(x->max_sz >= BLK_SZ(x)); + ASSERT(x->max_sz == BLK_SZ(x) + || x->max_sz == (x->left ? x->left->max_sz : 0) + || x->max_sz == (x->right ? x->right->max_sz : 0)); + + if (size && BLK_SZ(x) >= size) { + if (!res || x < res) { + res = x; + } + } + + UNSET_LEFT_VISITED(x); + UNSET_RIGHT_VISITED(x); + if (IS_BLACK(x)) + curr_blacks--; + x = x->parent; + + } + + ASSERT(curr_blacks == 0); + + UNSET_LEFT_VISITED(root); + UNSET_RIGHT_VISITED(root); + + return res; + +} + + +#ifdef PRINT_TREE +#define INDENT_STEP 2 + +#include + +static void +print_tree_aux(AOFF_RBTree_t *x, int indent) +{ + int i; + + if (x) { + print_tree_aux(x->right, indent + INDENT_STEP); + for (i = 0; i < indent; i++) { + putc(' ', stderr); + } + fprintf(stderr, "%s: sz=%lu addr=0x%lx max_size=%lu\r\n", + IS_BLACK(x) ? "BLACK" : "RED", + BLK_SZ(x), (Uint)x, x->max_sz); + print_tree_aux(x->left, indent + INDENT_STEP); + } +} + + +static void +print_tree(AOFF_RBTree_t* root) +{ + fprintf(stderr, " --- AOFF tree begin ---\r\n"); + print_tree_aux(root, 0); + fprintf(stderr, " --- AOFF tree end ---\r\n"); +} + +#endif /* PRINT_TREE */ + +#endif /* HARD_DEBUG */ + diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h new file mode 100644 index 0000000000..0bf0ec8cee --- /dev/null +++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h @@ -0,0 +1,60 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2003-2009. 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% + */ + + +#ifndef ERL_AO_FIRSTFIT_ALLOC__ +#define ERL_AO_FIRSTFIT_ALLOC__ + +#include "erl_alloc_util.h" + +#define ERTS_ALC_AOFF_ALLOC_VSN_STR "0.9" + +typedef struct AOFFAllctr_t_ AOFFAllctr_t; + +typedef struct { + int dummy; +} AOFFAllctrInit_t; + +#define ERTS_DEFAULT_AOFF_ALLCTR_INIT {0/*dummy*/} + +void erts_aoffalc_init(void); +Allctr_t *erts_aoffalc_start(AOFFAllctr_t *, AOFFAllctrInit_t*, AllctrInit_t *); + +#endif /* #ifndef ERL_AO_FIRSTFIT_ALLOC__ */ + + + +#if defined(GET_ERL_AOFF_ALLOC_IMPL) && !defined(ERL_AOFF_ALLOC_IMPL__) +#define ERL_AOFF_ALLOC_IMPL__ + +#define GET_ERL_ALLOC_UTIL_IMPL +#include "erl_alloc_util.h" + + +struct AOFFAllctr_t_ { + Allctr_t allctr; /* Has to be first! */ + + struct AOFF_RBTree_t_* mbc_root; + struct AOFF_RBTree_t_* sbmbc_root; +}; + +unsigned long erts_aoffalc_test(unsigned long, unsigned long, unsigned long); + +#endif /* #if defined(GET_ERL_AOFF_ALLOC_IMPL) + && !defined(ERL_AOFF_ALLOC_IMPL__) */ diff --git a/erts/emulator/beam/erl_bestfit_alloc.c b/erts/emulator/beam/erl_bestfit_alloc.c index d9b1170a3d..5e3032ddaa 100644 --- a/erts/emulator/beam/erl_bestfit_alloc.c +++ b/erts/emulator/beam/erl_bestfit_alloc.c @@ -979,6 +979,7 @@ erts_bfalc_test(unsigned long op, unsigned long a1, unsigned long a2) case 0x205: return (unsigned long) ((RBTreeList_t *) a1)->next; case 0x206: return (unsigned long) IS_BLACK((RBTree_t *) a1); case 0x207: return (unsigned long) IS_TREE_NODE((RBTree_t *) a1); + case 0x208: return (unsigned long) 0; /* IS_AOFF */ default: ASSERT(0); return ~((unsigned long) 0); } } diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h index b869a4079c..8b34375980 100644 --- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h +++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h @@ -82,15 +82,17 @@ typedef void* erts_cond; #define NO_OF_BKTS ((Ulong) ALC_TEST0(0x102)) #define FIND_BKT(A, I) ((int) ALC_TEST2(0x103, (A), (I))) -/* From erl_bestfit_alloc.c */ -#define IS_AOBF(A) ((Ulong) ALC_TEST1(0x200, (A))) -#define RBT_ROOT(A) ((RBT_t *) ALC_TEST1(0x201, (A))) -#define RBT_PARENT(T) ((RBT_t *) ALC_TEST1(0x202, (T))) -#define RBT_LEFT(T) ((RBT_t *) ALC_TEST1(0x203, (T))) -#define RBT_RIGHT(T) ((RBT_t *) ALC_TEST1(0x204, (T))) -#define RBT_NEXT(T) ((RBTL_t *) ALC_TEST1(0x205, (T))) -#define RBT_IS_BLACK(T) ((Ulong) ALC_TEST1(0x206, (T))) -#define RBT_IS_TREE(T) ((Ulong) ALC_TEST1(0x207, (T))) +/* From erl_bestfit_alloc.c and erl_ao_firstfit_alloc.c */ +#define IS_AOBF(A) ((Ulong) ALC_TEST1(RBT_OP(0), (A))) +#define RBT_ROOT(A) ((RBT_t *) ALC_TEST1(RBT_OP(1), (A))) +#define RBT_PARENT(T) ((RBT_t *) ALC_TEST1(RBT_OP(2), (T))) +#define RBT_LEFT(T) ((RBT_t *) ALC_TEST1(RBT_OP(3), (T))) +#define RBT_RIGHT(T) ((RBT_t *) ALC_TEST1(RBT_OP(4), (T))) +#define RBT_NEXT(T) ((RBTL_t *) ALC_TEST1(RBT_OP(5), (T))) +#define RBT_IS_BLACK(T) ((Ulong) ALC_TEST1(RBT_OP(6), (T))) +#define RBT_IS_TREE(T) ((Ulong) ALC_TEST1(RBT_OP(7), (T))) +#define IS_AOFF(A) ((Ulong) ALC_TEST1(RBT_OP(8), (A))) +#define RBT_MAX_SZ(T) ((Ulong) ALC_TEST1(RBT_OP(9), (T))) /* From erl_mseg.c */ #define HAVE_MSEG() ((int) ALC_TEST0(0x400)) diff --git a/erts/emulator/test/alloc_SUITE_data/coalesce.c b/erts/emulator/test/alloc_SUITE_data/coalesce.c index c84da97d35..6f35d3279b 100644 --- a/erts/emulator/test/alloc_SUITE_data/coalesce.c +++ b/erts/emulator/test/alloc_SUITE_data/coalesce.c @@ -267,7 +267,7 @@ void testcase_run(TestCaseState_t *tcs) { char *argv_org[] = {"-tmmbcs1024", "-tsbct2048", "-trmbcmt100", "-tas", NULL, NULL}; - char *alg[] = {"af", "gf", "bf", "aobf", NULL}; + char *alg[] = {"af", "gf", "bf", "aobf", "aoff", NULL}; int i; for (i = 0; alg[i]; i++) { diff --git a/erts/emulator/test/alloc_SUITE_data/rbtree.c b/erts/emulator/test/alloc_SUITE_data/rbtree.c index c97e0aac1a..4e7f821baf 100644 --- a/erts/emulator/test/alloc_SUITE_data/rbtree.c +++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c @@ -34,6 +34,14 @@ typedef struct { #define PRINT_TREE #endif +/* Ugly hack to steer the test code towards the right allocator */ +#define RBT_OP(CMD) (current_rbt_type_op_base + (CMD)) +static enum { + BESTFIT_OP_BASE = 0x200, + AO_FIRSTFIT_OP_BASE = 0x500 +}current_rbt_type_op_base; + + #ifdef PRINT_TREE #define INDENT_STEP 5 @@ -65,12 +73,11 @@ print_tree_aux(TestCaseState_t *tcs, RBT_t *x, int indent) static void -print_tree(TestCaseState_t *tcs, RBT_t *root, int aobf) +print_tree(TestCaseState_t *tcs, RBT_t *root) { - char *type = aobf ? "Size-Adress" : "Size"; - testcase_printf(tcs, " --- %s tree begin ---\r\n", type); + testcase_printf(tcs, " --- Tree begin ---\r\n"); print_tree_aux(tcs, root, 0); - testcase_printf(tcs, " --- %s tree end ---\r\n", type); + testcase_printf(tcs, " --- Tree end ---\r\n"); } #endif @@ -78,7 +85,8 @@ print_tree(TestCaseState_t *tcs, RBT_t *root, int aobf) static RBT_t * check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) { - int i, max_i, address_order; + enum { BF, AOBF, AOFF }type; + int i, max_i; char stk[128]; RBT_t *root, *x, *y, *res; Ulong x_sz, y_sz, is_x_black; @@ -86,11 +94,14 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) res = NULL; - address_order = IS_AOBF(alc); + if (IS_AOBF(alc)) type = AOBF; + else if (IS_AOFF(alc)) type = AOFF; + else type = BF; + root = RBT_ROOT(alc); #ifdef PRINT_TREE - print_tree(tcs, root, address_order); + print_tree(tcs, root); #endif max_i = i = -1; @@ -165,12 +176,18 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) if (y) { y_sz = BLK_SZ(y); ASSERT(tcs, RBT_PARENT(y) == x); - if (address_order) { + switch (type) { + case AOBF: ASSERT(tcs, y_sz < x_sz || (y_sz == x_sz && y < x)); - } - else { + break; + case BF: ASSERT(tcs, RBT_IS_TREE(y)); ASSERT(tcs, y_sz < x_sz); + break; + case AOFF: + ASSERT(tcs, y < x); + ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); + break; } } @@ -178,16 +195,22 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) if (y) { y_sz = BLK_SZ(y); ASSERT(tcs, RBT_PARENT(y) == x); - if (address_order) { + switch (type) { + case AOBF: ASSERT(tcs, y_sz > x_sz || (y_sz == x_sz && y > x)); - } - else { + break; + case BF: ASSERT(tcs, RBT_IS_TREE(y)); ASSERT(tcs, y_sz > x_sz); + break; + case AOFF: + ASSERT(tcs, y > x); + ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x)); + break; } } - if (!address_order) { + if (type == BF) { Ulong l_sz; RBTL_t *l = RBT_NEXT(x); for (l = RBT_NEXT(x); l; l = RBT_NEXT(l)) { @@ -202,13 +225,20 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size) res = x; else { y_sz = BLK_SZ(res); - if (address_order) { + switch (type) { + case AOBF: if (x_sz < y_sz || (x_sz == y_sz && x < res)) res = x; - } - else { - if (!res || x_sz < y_sz) + break; + case BF: + if (x_sz < y_sz) res = x; + break; + case AOFF: + if (x < res) { + res = x; + } + break; } } } @@ -257,7 +287,7 @@ static void test_it(TestCaseState_t *tcs) { int i; - Allctr_t a = ((rbtree_test_data *) tcs->extra)->allocator; + Allctr_t* a = ((rbtree_test_data *) tcs->extra)->allocator; void **blk = ((rbtree_test_data *) tcs->extra)->blk; void **fence = ((rbtree_test_data *) tcs->extra)->fence; Ulong min_blk_sz; @@ -338,6 +368,7 @@ testcase_run(TestCaseState_t *tcs) { char *argv1[] = {"-tasbf", NULL}; char *argv2[] = {"-tasaobf", NULL}; + char *argv3[] = {"-tasaoff", NULL}; Allctr_t *a; rbtree_test_data *td; @@ -355,6 +386,7 @@ testcase_run(TestCaseState_t *tcs) testcase_printf(tcs, "Starting test of best fit...\n"); + current_rbt_type_op_base = BESTFIT_OP_BASE; td->allocator = a = START_ALC("rbtree_bf_", 0, argv1); ASSERT(tcs, a); @@ -371,6 +403,7 @@ testcase_run(TestCaseState_t *tcs) testcase_printf(tcs, "Starting test of address order best fit...\n"); + current_rbt_type_op_base = BESTFIT_OP_BASE; td->allocator = a = START_ALC("rbtree_aobf_", 0, argv2); ASSERT(tcs, a); @@ -383,4 +416,19 @@ testcase_run(TestCaseState_t *tcs) testcase_printf(tcs, "Address order best fit test succeeded!\n"); + /* Address order first fit... */ + + testcase_printf(tcs, "Starting test of address order first fit...\n"); + + current_rbt_type_op_base = AO_FIRSTFIT_OP_BASE; + td->allocator = a = START_ALC("rbtree_aoff_", 0, argv3); + + ASSERT(tcs, a); + + test_it(tcs); + + STOP_ALC(a); + td->allocator = NULL; + + testcase_printf(tcs, "Address order first fit test succeeded!\n"); } -- cgit v1.2.3