aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam')
-rw-r--r--erts/emulator/beam/erl_alloc.c5
-rw-r--r--erts/emulator/beam/erl_alloc_util.c37
-rw-r--r--erts/emulator/beam/erl_alloc_util.h33
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.c92
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.h4
-rw-r--r--erts/emulator/beam/erl_bestfit_alloc.c2
6 files changed, 114 insertions, 59 deletions
diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c
index 403776aade..cb69be33ad 100644
--- a/erts/emulator/beam/erl_alloc.c
+++ b/erts/emulator/beam/erl_alloc.c
@@ -1197,6 +1197,11 @@ handle_au_arg(struct au_init *auip,
}
else if (strcmp("aoff", alg) == 0) {
auip->atype = AOFIRSTFIT;
+ auip->init.aoff.bf_within_carrier = 0;
+ }
+ else if (strcmp("aoffcbf", alg) == 0) {
+ auip->atype = AOFIRSTFIT;
+ auip->init.aoff.bf_within_carrier = 1;
}
else {
bad_value(param, sub_param + 1, alg);
diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c
index 53062979a6..c57ddc424e 100644
--- a/erts/emulator/beam/erl_alloc_util.c
+++ b/erts/emulator/beam/erl_alloc_util.c
@@ -76,16 +76,6 @@ static int initialized = 0;
int erts_have_sbmbc_alloc;
-#if HAVE_ERTS_MSEG
-
-#define MSEG_UNIT_SHIFT MSEG_ALIGN_BITS
-#define MSEG_UNIT_SZ (1 << MSEG_UNIT_SHIFT)
-#define MSEG_UNIT_MASK ((~(UWord)0) << MSEG_UNIT_SHIFT)
-
-#define MSEG_UNIT_FLOOR(X) ((X) & MSEG_UNIT_MASK)
-#define MSEG_UNIT_CEILING(X) MSEG_UNIT_FLOOR((X) + ~MSEG_UNIT_MASK)
-
-#endif
#define INV_SYS_ALLOC_CARRIER_MASK ((UWord) (sys_alloc_carrier_size - 1))
#define SYS_ALLOC_CARRIER_MASK (~INV_SYS_ALLOC_CARRIER_MASK)
@@ -173,14 +163,6 @@ MBC after deallocating first block:
#define SET_BLK_SZ_FTR(B, SZ) \
(((FreeBlkFtr_t *) (((char *) (B)) + (SZ)))[-1] = (SZ))
-#define THIS_FREE_BLK_HDR_FLG (((UWord) 1) << 0)
-#define PREV_FREE_BLK_HDR_FLG (((UWord) 1) << 1)
-#define LAST_BLK_HDR_FLG (((UWord) 1) << 2)
-
-/* Special flag combo for (allocated) SBC blocks
-*/
-#define SBC_BLK_HDR_FLG (THIS_FREE_BLK_HDR_FLG | PREV_FREE_BLK_HDR_FLG | LAST_BLK_HDR_FLG)
-
#define SET_MBC_ABLK_SZ(B, SZ) \
(ASSERT(((SZ) & FLG_MASK) == 0), \
(B)->bhdr = (((B)->bhdr) & ~MBC_ABLK_SZ_MASK) | (SZ))
@@ -222,15 +204,6 @@ MBC after deallocating first block:
ASSERT(((UWord)(F) & (~FLG_MASK|THIS_FREE_BLK_HDR_FLG|PREV_FREE_BLK_HDR_FLG)) == THIS_FREE_BLK_HDR_FLG), \
(B)->bhdr = ((Sz) | (F)), \
(B)->u.carrier = (C))
-
-# define ABLK_TO_MBC(B) \
- (ASSERT(IS_MBC_BLK(B) && IS_ALLOCED_BLK(B)), \
- (Carrier_t*)((MSEG_UNIT_FLOOR((UWord)(B)) - \
- (((B)->bhdr >> MBC_ABLK_OFFSET_SHIFT) << MSEG_UNIT_SHIFT))))
-
-# define FBLK_TO_MBC(B) \
- (ASSERT(IS_MBC_BLK(B) && IS_FREE_BLK(B)), \
- (B)->u.carrier)
# define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B))
@@ -273,8 +246,6 @@ MBC after deallocating first block:
(B)->carrier = (C))
# define BLK_TO_MBC(B) ((B)->carrier)
-# define ABLK_TO_MBC(B) BLK_TO_MBC(B)
-# define FBLK_TO_MBC(B) BLK_TO_MBC(B)
# define IS_MBC_FIRST_BLK(AP,B) \
((char*)(B) == (char*)((B)->carrier) + MBC_HEADER_SIZE(AP))
@@ -300,8 +271,6 @@ MBC after deallocating first block:
((B)->bhdr & PREV_FREE_BLK_HDR_FLG)
#define IS_PREV_BLK_ALLOCED(B) \
(!IS_PREV_BLK_FREE((B)))
-#define IS_FREE_BLK(B) \
- (ASSERT(!IS_SBC_BLK(B)), (B)->bhdr & THIS_FREE_BLK_HDR_FLG)
#define IS_ALLOCED_BLK(B) \
(!IS_FREE_BLK((B)))
#define IS_LAST_BLK(B) \
@@ -318,11 +287,6 @@ MBC after deallocating first block:
#define GET_BLK_HDR_FLGS(B) \
((B)->bhdr & FLG_MASK)
-#define IS_SBC_BLK(B) \
- (((B)->bhdr & FLG_MASK) == SBC_BLK_HDR_FLG)
-#define IS_MBC_BLK(B) \
- (!IS_SBC_BLK((B)))
-
#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B))
#define NXT_BLK(B) \
@@ -4440,6 +4404,7 @@ erts_alcu_test(UWord op, UWord a1, UWord a2)
case 0x019: return (UWord) PREV_BLK((Block_t *) a1);
case 0x01a: return (UWord) IS_MBC_FIRST_BLK((Allctr_t*)a1, (Block_t *) a2);
case 0x01b: return (UWord) sizeof(Unit_t);
+ case 0x01c: return (unsigned long) BLK_TO_MBC((Block_t*) a1);
default: ASSERT(0); return ~((UWord) 0);
}
}
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index 4773598561..404ba66971 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -221,8 +221,15 @@ erts_aint32_t erts_alcu_fix_alloc_shrink(Allctr_t *, erts_aint32_t);
#define MBC_FBLK_SZ_MASK UNIT_MASK
#define CARRIER_SZ_MASK UNIT_MASK
-
#if HAVE_ERTS_MSEG
+
+# define MSEG_UNIT_SHIFT MSEG_ALIGN_BITS
+# define MSEG_UNIT_SZ (1 << MSEG_UNIT_SHIFT)
+# define MSEG_UNIT_MASK ((~(UWord)0) << MSEG_UNIT_SHIFT)
+
+# define MSEG_UNIT_FLOOR(X) ((X) & MSEG_UNIT_MASK)
+# define MSEG_UNIT_CEILING(X) MSEG_UNIT_FLOOR((X) + ~MSEG_UNIT_MASK)
+
# ifdef ARCH_64
# define MBC_ABLK_OFFSET_BITS 24
# elif HAVE_SUPER_ALIGNED_MB_CARRIERS
@@ -280,6 +287,30 @@ typedef struct {
#endif
} Block_t;
+#define THIS_FREE_BLK_HDR_FLG (((UWord) 1) << 0)
+#define PREV_FREE_BLK_HDR_FLG (((UWord) 1) << 1)
+#define LAST_BLK_HDR_FLG (((UWord) 1) << 2)
+
+#define SBC_BLK_HDR_FLG /* Special flag combo for (allocated) SBC blocks */\
+ (THIS_FREE_BLK_HDR_FLG | PREV_FREE_BLK_HDR_FLG | LAST_BLK_HDR_FLG)
+
+#define IS_SBC_BLK(B) (((B)->bhdr & FLG_MASK) == SBC_BLK_HDR_FLG)
+#define IS_MBC_BLK(B) (!IS_SBC_BLK((B)))
+#define IS_FREE_BLK(B) (ASSERT(IS_MBC_BLK(B)), \
+ (B)->bhdr & THIS_FREE_BLK_HDR_FLG)
+
+#if MBC_ABLK_OFFSET_BITS
+# define FBLK_TO_MBC(B) (ASSERT(IS_MBC_BLK(B) && IS_FREE_BLK(B)), \
+ (B)->u.carrier)
+# define ABLK_TO_MBC(B) \
+ (ASSERT(IS_MBC_BLK(B) && !IS_FREE_BLK(B)), \
+ (Carrier_t*)((MSEG_UNIT_FLOOR((UWord)(B)) - \
+ (((B)->bhdr >> MBC_ABLK_OFFSET_SHIFT) << MSEG_UNIT_SHIFT))))
+#else
+# define FBLK_TO_MBC(B) ((B)->carrier)
+# define ABLK_TO_MBC(B) ((B)->carrier)
+#endif
+
typedef UWord FreeBlkFtr_t; /* Footer of a free block */
typedef struct {
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index b916cb6198..e277006e58 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -28,11 +28,16 @@
*
* This module is a callback-module for erl_alloc_util.c
*
- * Algorithm: The tree nodes are free-blocks ordered in address order.
+ * AOFF 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.
+ * AOFFCBF:
+ * The only difference for "bestfit within carrier" is the tree
+ * sorting order. Blocks are first sorted wrt carrier address
+ * and then wrt size if they belong to the same carrier.
*
* Authors: Rickard Green/Sverker Eriksson
*/
@@ -94,7 +99,7 @@ struct AOFF_RBTree_t_ {
#define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
#ifdef HARD_DEBUG
-static AOFF_RBTree_t * check_tree(AOFF_RBTree_t* root, Uint);
+static AOFF_RBTree_t * check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint);
#endif
@@ -132,6 +137,32 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
else ASSERT(new_max == old_max);
}
+static ERTS_INLINE SWord cmp_blocks(AOFFAllctr_t* alc,
+ AOFF_RBTree_t* lhs, AOFF_RBTree_t* rhs)
+{
+ if (alc->bf_within_carrier
+ && FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr)) {
+ SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
+ if (diff) return diff;
+ }
+ return (char*)lhs - (char*)rhs;
+}
+
+static ERTS_INLINE SWord cmp_cand_blk(AOFFAllctr_t* alc,
+ Block_t* cand_blk, AOFF_RBTree_t* rhs)
+{
+ if (alc->bf_within_carrier) {
+ if (IS_FREE_BLK(cand_blk))
+ return cmp_blocks(alc, (AOFF_RBTree_t*)cand_blk, rhs);
+
+ if (ABLK_TO_MBC(cand_blk) == FBLK_TO_MBC(&rhs->hdr)) {
+ SWord diff = (SWord)MBC_ABLK_SZ(cand_blk) - (SWord)MBC_FBLK_SZ(&rhs->hdr);
+ if (diff) return diff;
+ }
+ }
+ return (char*)cand_blk - (char*)rhs;
+}
+
/* Prototypes of callback functions */
static Block_t* aoff_get_free_block(Allctr_t *, Uint, Block_t *, Uint, Uint32 flags);
@@ -184,11 +215,13 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
sys_memcpy((void *) alc, (void *) &zero.allctr, sizeof(AOFFAllctr_t));
+ alc->bf_within_carrier = aoffinit->bf_within_carrier;
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;
+ allctr->vsn_str = aoffinit->bf_within_carrier ?
+ ERTS_ALC_AOFF_CBF_ALLOC_VSN_STR : ERTS_ALC_AOFF_ALLOC_VSN_STR;
/* Callback functions */
@@ -416,7 +449,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
null_x.parent = NULL;
#ifdef HARD_DEBUG
- check_tree(*root, 0);
+ check_tree(alc, *root, 0);
#endif
/* Remove node from tree... */
@@ -576,7 +609,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
DESTROY_TREE_NODE(del);
#ifdef HARD_DEBUG
- check_tree(*root, 0);
+ check_tree(alc, *root, 0);
#endif
}
@@ -590,7 +623,7 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
Uint blk_sz = AOFF_BLK_SZ(blk);
#ifdef HARD_DEBUG
- check_tree(*root, 0);
+ check_tree(alc, *root, 0);
#endif
blk->flags = 0;
@@ -609,7 +642,7 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
if (x->max_sz < blk_sz) {
x->max_sz = blk_sz;
}
- if (blk < x) {
+ if (cmp_blocks(alc, blk, x) < 0) {
if (!x->left) {
blk->parent = x;
x->left = blk;
@@ -637,7 +670,7 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
}
#ifdef HARD_DEBUG
- check_tree(*root, 0);
+ check_tree(alc, *root, 0);
#endif
}
@@ -650,7 +683,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
? alc->sbmbc_root : alc->mbc_root);
AOFF_RBTree_t *blk = NULL;
#ifdef HARD_DEBUG
- AOFF_RBTree_t* dbg_blk = check_tree(x, size);
+ AOFF_RBTree_t* dbg_blk = check_tree(alc, x, size);
#endif
ASSERT(!cand_blk || cand_size >= size);
@@ -675,7 +708,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
if (!blk)
return NULL;
- if (cand_blk && cand_blk < &blk->hdr) {
+ if (cand_blk && cmp_cand_blk(alc, cand_blk, blk) < 0) {
return NULL; /* cand_blk was better */
}
@@ -692,6 +725,7 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
static struct {
Eterm as;
Eterm aoff;
+ Eterm aoffcbf;
#ifdef DEBUG
Eterm end_of_atoms;
#endif
@@ -720,6 +754,7 @@ init_atoms(void)
#endif
AM_INIT(as);
AM_INIT(aoff);
+ AM_INIT(aoffcbf);
#ifdef DEBUG
for (atom = (Eterm *) &am; atom < &am.end_of_atoms; atom++) {
@@ -749,6 +784,7 @@ info_options(Allctr_t *allctr,
Uint **hpp,
Uint *szp)
{
+ AOFFAllctr_t* alc = (AOFFAllctr_t*) allctr;
Eterm res = THE_NON_VALUE;
if (print_to_p) {
@@ -756,7 +792,7 @@ info_options(Allctr_t *allctr,
print_to_arg,
"%sas: %s\n",
prefix,
- "aoff");
+ alc->bf_within_carrier ? "aoffcbf" : "aoff");
}
if (hpp || szp) {
@@ -766,7 +802,8 @@ info_options(Allctr_t *allctr,
__FILE__, __LINE__);;
res = NIL;
- add_2tup(hpp, szp, &res, am.as, am.aoff);
+ add_2tup(hpp, szp, &res, am.as,
+ alc->bf_within_carrier ? am.aoffcbf : am.aoff);
}
return res;
@@ -784,14 +821,14 @@ UWord
erts_aoffalc_test(UWord op, UWord a1, UWord a2)
{
switch (op) {
- case 0x500: return (UWord) 0; /* IS_AOBF */
case 0x501: return (UWord) ((AOFFAllctr_t *) a1)->mbc_root;
case 0x502: return (UWord) ((AOFF_RBTree_t *) a1)->parent;
case 0x503: return (UWord) ((AOFF_RBTree_t *) a1)->left;
case 0x504: return (UWord) ((AOFF_RBTree_t *) a1)->right;
case 0x506: return (UWord) IS_BLACK((AOFF_RBTree_t *) a1);
- case 0x508: return (UWord) 1; /* IS_AOFF */
+ case 0x508: return (UWord) 0; /* IS_BF_ALGO */
case 0x509: return (UWord) ((AOFF_RBTree_t *) a1)->max_sz;
+ case 0x50a: return (UWord) ((AOFFAllctr_t *) a1)->bf_within_carrier;
default: ASSERT(0); return ~((UWord) 0);
}
}
@@ -840,12 +877,14 @@ static void print_tree(AOFF_RBTree_t*);
*/
static AOFF_RBTree_t *
-check_tree(AOFF_RBTree_t* root, Uint size)
+check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint size)
{
AOFF_RBTree_t *res = NULL;
Sint blacks;
Sint curr_blacks;
AOFF_RBTree_t *x;
+ Carrier_t* crr;
+ Uint depth, max_depth, node_cnt;
#ifdef PRINT_TREE
print_tree(root);
@@ -859,12 +898,16 @@ check_tree(AOFF_RBTree_t* root, Uint size)
ASSERT(!x->parent);
curr_blacks = 1;
blacks = -1;
+ depth = 1;
+ max_depth = 0;
+ node_cnt = 0;
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;
@@ -880,6 +923,7 @@ check_tree(AOFF_RBTree_t* root, Uint size)
SET_RIGHT_VISITED(x);
if (x->right) {
x = x->right;
+ ++depth;
if (IS_BLACK(x))
curr_blacks++;
continue;
@@ -891,6 +935,13 @@ check_tree(AOFF_RBTree_t* root, Uint size)
}
}
+ ++node_cnt;
+ if (depth > max_depth)
+ max_depth = depth;
+
+ crr = FBLK_TO_MBC(&x->hdr);
+ ASSERT((char*)x > (char*)crr);
+ ASSERT(((char*)x + AOFF_BLK_SZ(x)) <= ((char*)crr + CARRIER_SZ(crr)));
if (IS_RED(x)) {
ASSERT(IS_BLACK(x->right));
@@ -901,13 +952,13 @@ check_tree(AOFF_RBTree_t* root, Uint size)
if (x->left) {
ASSERT(x->left->parent == x);
- ASSERT(x->left < x);
+ ASSERT(cmp_blocks(alc, x->left, x) < 0);
ASSERT(x->left->max_sz <= x->max_sz);
}
if (x->right) {
ASSERT(x->right->parent == x);
- ASSERT(x->right > x);
+ ASSERT(cmp_blocks(alc, x->right, x) > 0);
ASSERT(x->right->max_sz <= x->max_sz);
}
ASSERT(x->max_sz >= AOFF_BLK_SZ(x));
@@ -916,7 +967,7 @@ check_tree(AOFF_RBTree_t* root, Uint size)
|| x->max_sz == (x->right ? x->right->max_sz : 0));
if (size && AOFF_BLK_SZ(x) >= size) {
- if (!res || x < res) {
+ if (!res || cmp_blocks(alc, x, res) < 0) {
res = x;
}
}
@@ -926,10 +977,11 @@ check_tree(AOFF_RBTree_t* root, Uint size)
if (IS_BLACK(x))
curr_blacks--;
x = x->parent;
-
+ --depth;
}
-
+ ASSERT(depth == 0 || (!root && depth==1));
ASSERT(curr_blacks == 0);
+ ASSERT((1 << (max_depth/2)) <= node_cnt);
UNSET_LEFT_VISITED(root);
UNSET_RIGHT_VISITED(root);
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 21c36c6654..36995a20f0 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -24,11 +24,12 @@
#include "erl_alloc_util.h"
#define ERTS_ALC_AOFF_ALLOC_VSN_STR "0.9"
+#define ERTS_ALC_AOFF_CBF_ALLOC_VSN_STR "0.9"
typedef struct AOFFAllctr_t_ AOFFAllctr_t;
typedef struct {
- int dummy;
+ int bf_within_carrier;
} AOFFAllctrInit_t;
#define ERTS_DEFAULT_AOFF_ALLCTR_INIT {0/*dummy*/}
@@ -52,6 +53,7 @@ struct AOFFAllctr_t_ {
struct AOFF_RBTree_t_* mbc_root;
struct AOFF_RBTree_t_* sbmbc_root;
+ int bf_within_carrier;
};
UWord erts_aoffalc_test(UWord, UWord, UWord);
diff --git a/erts/emulator/beam/erl_bestfit_alloc.c b/erts/emulator/beam/erl_bestfit_alloc.c
index ed843a51fb..e3fc8f4cb1 100644
--- a/erts/emulator/beam/erl_bestfit_alloc.c
+++ b/erts/emulator/beam/erl_bestfit_alloc.c
@@ -984,7 +984,7 @@ erts_bfalc_test(UWord op, UWord a1, UWord a2)
case 0x205: return (UWord) ((RBTreeList_t *) a1)->next;
case 0x206: return (UWord) IS_BLACK((RBTree_t *) a1);
case 0x207: return (UWord) IS_TREE_NODE((RBTree_t *) a1);
- case 0x208: return (UWord) 0; /* IS_AOFF */
+ case 0x208: return (UWord) 1; /* IS_BF_ALGO */
default: ASSERT(0); return ~((UWord) 0);
}
}