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_util.c6
-rw-r--r--erts/emulator/beam/erl_alloc_util.h3
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.c148
-rw-r--r--erts/emulator/beam/erl_ao_firstfit_alloc.h4
4 files changed, 132 insertions, 29 deletions
diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c
index bf7d561b00..ce66727fae 100644
--- a/erts/emulator/beam/erl_alloc_util.c
+++ b/erts/emulator/beam/erl_alloc_util.c
@@ -205,8 +205,6 @@ MBC after deallocating first block:
(B)->bhdr = ((Sz) | (F)), \
(B)->u.carrier = (C))
-# define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B))
-
# define IS_MBC_FIRST_ABLK(AP,B) \
((((UWord)(B) & ~MSEG_UNIT_MASK) == MBC_HEADER_SIZE(AP)) \
&& ((B)->bhdr & MBC_ABLK_OFFSET_MASK) == 0)
@@ -245,8 +243,6 @@ MBC after deallocating first block:
(B)->bhdr = ((Sz) | (F)), \
(B)->carrier = (C))
-# define BLK_TO_MBC(B) ((B)->carrier)
-
# define IS_MBC_FIRST_BLK(AP,B) \
((char*)(B) == (char*)((B)->carrier) + MBC_HEADER_SIZE(AP))
# define IS_MBC_FIRST_ABLK(AP,B) IS_MBC_FIRST_BLK(AP,B)
@@ -287,8 +283,6 @@ MBC after deallocating first block:
#define GET_BLK_HDR_FLGS(B) \
((B)->bhdr & FLG_MASK)
-#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B))
-
#define NXT_BLK(B) \
(ASSERT(IS_MBC_BLK(B)), \
(Block_t *) (((char *) (B)) + MBC_BLK_SZ((B))))
diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h
index af8f72ed7d..1183bf901d 100644
--- a/erts/emulator/beam/erl_alloc_util.h
+++ b/erts/emulator/beam/erl_alloc_util.h
@@ -306,10 +306,13 @@ typedef struct {
(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))))
+# define BLK_TO_MBC(B) (IS_FREE_BLK(B) ? FBLK_TO_MBC(B) : ABLK_TO_MBC(B))
#else
# define FBLK_TO_MBC(B) ((B)->carrier)
# define ABLK_TO_MBC(B) ((B)->carrier)
+# define BLK_TO_MBC(B) ((B)->carrier)
#endif
+#define MBC_BLK_SZ(B) (IS_FREE_BLK(B) ? MBC_FBLK_SZ(B) : MBC_ABLK_SZ(B))
typedef UWord FreeBlkFtr_t; /* Footer of a free block */
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.c b/erts/emulator/beam/erl_ao_firstfit_alloc.c
index 1570daf90e..50cbfc5033 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.c
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.c
@@ -98,7 +98,17 @@ struct AOFF_RBTree_t_ {
};
#define AOFF_BLK_SZ(B) MBC_FBLK_SZ(&(B)->hdr)
+typedef struct AOFF_Carrier_t_ AOFF_Carrier_t;
+
+struct AOFF_Carrier_t_ {
+ Carrier_t crr;
+ AOFF_Carrier_t* next;
+ AOFF_Carrier_t** prevp;
+ AOFF_RBTree_t* root;
+};
+
#ifdef HARD_DEBUG
+static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags);
static AOFF_RBTree_t * check_tree(AOFFAllctr_t* alc, AOFF_RBTree_t* root, Uint);
#endif
@@ -140,8 +150,8 @@ static ERTS_INLINE void lower_max_size(AOFF_RBTree_t *node,
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)) {
+ ASSERT(FBLK_TO_MBC(&lhs->hdr) == FBLK_TO_MBC(&rhs->hdr));
+ if (alc->bf_within_carrier) {
SWord diff = (SWord)AOFF_BLK_SZ(lhs) - (SWord)AOFF_BLK_SZ(rhs);
if (diff) return diff;
}
@@ -152,11 +162,8 @@ 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 (BLK_TO_MBC(cand_blk) == FBLK_TO_MBC(&rhs->hdr)) {
+ SWord diff = (SWord)MBC_BLK_SZ(cand_blk) - (SWord)MBC_FBLK_SZ(&rhs->hdr);
if (diff) return diff;
}
}
@@ -168,6 +175,8 @@ static ERTS_INLINE SWord cmp_cand_blk(AOFFAllctr_t* alc,
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 void aoff_creating_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
+static void aoff_destroying_mbc(Allctr_t*, Carrier_t*, Uint32 flags);
static Eterm info_options(Allctr_t *, char *, int *, void *, Uint **, Uint *);
static void init_atoms(void);
@@ -216,7 +225,7 @@ 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->mbc_header_size = sizeof(Carrier_t);
+ allctr->mbc_header_size = sizeof(AOFF_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);
@@ -233,8 +242,8 @@ erts_aoffalc_start(AOFFAllctr_t *alc,
allctr->info_options = info_options;
allctr->get_next_mbc_size = NULL;
- allctr->creating_mbc = NULL;
- allctr->destroying_mbc = NULL;
+ allctr->creating_mbc = aoff_creating_mbc;
+ allctr->destroying_mbc = aoff_destroying_mbc;
allctr->init_atoms = init_atoms;
#ifdef ERTS_ALLOC_UTIL_HARD_DEBUG
@@ -439,9 +448,11 @@ tree_insert_fixup(AOFF_RBTree_t** root, AOFF_RBTree_t *blk)
static void
aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
{
+#ifdef HARD_DEBUG
AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
- AOFF_RBTree_t **root = ((flags & ERTS_ALCU_FLG_SBMBC)
- ? &alc->sbmbc_root : &alc->mbc_root);
+#endif
+ AOFF_Carrier_t *crr = (AOFF_Carrier_t*) FBLK_TO_MBC(del);
+ AOFF_RBTree_t **root = &crr->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
@@ -450,6 +461,7 @@ aoff_unlink_free_block(Allctr_t *allctr, Block_t *del, Uint32 flags)
null_x.parent = NULL;
#ifdef HARD_DEBUG
+ check_carriers(alc, crr, flags);
check_tree(alc, *root, 0);
#endif
@@ -619,14 +631,16 @@ 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);
+ AOFF_RBTree_t **root;
+ AOFF_Carrier_t *blk_crr = (AOFF_Carrier_t*) FBLK_TO_MBC(block);
Uint blk_sz = AOFF_BLK_SZ(blk);
#ifdef HARD_DEBUG
- check_tree(alc, *root, 0);
+ check_carriers(alc, blk_crr, flags);
+ check_tree(alc, blk_crr->root, 0);
#endif
+ root = &blk_crr->root;
blk->flags = 0;
blk->left = NULL;
blk->right = NULL;
@@ -659,7 +673,6 @@ aoff_link_free_block(Allctr_t *allctr, Block_t *block, Uint32 flags)
}
x = x->right;
}
-
}
/* Insert block into size tree */
@@ -680,15 +693,32 @@ 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;
+ AOFF_Carrier_t *crr = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? alc->sbmbc_first : alc->mbc_first);
+ AOFF_RBTree_t *x, *blk = NULL;
#ifdef HARD_DEBUG
- AOFF_RBTree_t* dbg_blk = check_tree(alc, x, size);
+ AOFF_RBTree_t* dbg_blk;
#endif
ASSERT(!cand_blk || cand_size >= size);
+ /* Get first-fit carrier
+ */
+ for (;;) {
+ if (!crr)
+ return NULL;
+ if (crr->root && crr->root->max_sz >= size)
+ break;
+ crr = crr->next;
+ }
+
+ /* Get block within carrier tree
+ */
+ x = crr->root;
+#ifdef HARD_DEBUG
+ dbg_blk = check_tree(alc, x, size);
+#endif
+
while (x) {
if (x->left && x->left->max_sz >= size) {
x = x->left;
@@ -718,6 +748,54 @@ aoff_get_free_block(Allctr_t *allctr, Uint size,
return (Block_t *) blk;
}
+static void aoff_creating_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+{
+ AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+ AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+ AOFF_Carrier_t **prevp = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? &alc->sbmbc_first : &alc->mbc_first);
+ AOFF_Carrier_t *p;
+
+
+ /* Link carrier in address order
+ */
+ for (p = *prevp; p && crr > p; p = p->next) {
+ prevp = &p->next;
+ }
+ ASSERT(crr != p);
+
+ crr->next = p;
+ crr->prevp = prevp;
+ *prevp = crr;
+ if (p) {
+ ASSERT(prevp == p->prevp);
+ p->prevp = &crr->next;
+ }
+
+ /* aoff_link_free_block will add free block later */
+ crr->root = NULL;
+}
+
+static void aoff_destroying_mbc(Allctr_t *allctr, Carrier_t *carrier, Uint32 flags)
+{
+ AOFFAllctr_t *alc = (AOFFAllctr_t *) allctr;
+ AOFF_Carrier_t *crr = (AOFF_Carrier_t*) carrier;
+ AOFF_Carrier_t **pp = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? &alc->sbmbc_first : &alc->mbc_first);
+
+ /* Unlink carrier
+ */
+ while (*pp != crr) {
+ ASSERT(*pp && (*pp)->prevp == pp);
+ pp = &(*pp)->next;
+ }
+ *pp = crr->next;
+ if (crr->next) {
+ ASSERT(crr->next->prevp == &crr->next);
+ crr->next->prevp = crr->prevp;
+ }
+}
+
/*
* info_options()
@@ -822,7 +900,18 @@ UWord
erts_aoffalc_test(UWord op, UWord a1, UWord a2)
{
switch (op) {
- case 0x501: return (UWord) ((AOFFAllctr_t *) a1)->mbc_root;
+ case 0x501: {
+ AOFF_Carrier_t* crr = ((AOFFAllctr_t *) a1)->mbc_first;
+ Uint size = (Uint) a2;
+ for (;;) {
+ if (!crr)
+ return (UWord)NULL;
+ if (crr->root && crr->root->max_sz >= size)
+ break;
+ crr = crr->next;
+ }
+ return (UWord) crr->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;
@@ -842,6 +931,23 @@ erts_aoffalc_test(UWord op, UWord a1, UWord a2)
#ifdef HARD_DEBUG
+static void check_carriers(AOFFAllctr_t* alc, AOFF_Carrier_t *crr, Uint32 flags)
+{
+ AOFF_Carrier_t *p = ((flags & ERTS_ALCU_FLG_SBMBC)
+ ? alc->sbmbc_first : alc->mbc_first);
+ int found_it = 0;
+
+ for ( ; p; p = p->next) {
+ if (p == crr) {
+ ASSERT(!found_it);
+ found_it = 1;
+ }
+ ASSERT(!p->next || p->next > p);
+ }
+ ASSERT(found_it);
+}
+
+
#define IS_LEFT_VISITED(FB) ((FB)->flags & LEFT_VISITED_FLG)
#define IS_RIGHT_VISITED(FB) ((FB)->flags & RIGHT_VISITED_FLG)
diff --git a/erts/emulator/beam/erl_ao_firstfit_alloc.h b/erts/emulator/beam/erl_ao_firstfit_alloc.h
index 36995a20f0..a8fa69ab79 100644
--- a/erts/emulator/beam/erl_ao_firstfit_alloc.h
+++ b/erts/emulator/beam/erl_ao_firstfit_alloc.h
@@ -51,8 +51,8 @@ Allctr_t *erts_aoffalc_start(AOFFAllctr_t *, AOFFAllctrInit_t*, AllctrInit_t *);
struct AOFFAllctr_t_ {
Allctr_t allctr; /* Has to be first! */
- struct AOFF_RBTree_t_* mbc_root;
- struct AOFF_RBTree_t_* sbmbc_root;
+ struct AOFF_Carrier_t_* mbc_first;
+ struct AOFF_Carrier_t_* sbmbc_first;
int bf_within_carrier;
};
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-18 16:30:10 +0000