aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/test
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2013-06-19 18:34:56 +0200
committerSverker Eriksson <[email protected]>2013-06-19 18:51:06 +0200
commit5d67cc7f4c176ea6ab4d2538443d5fe264152861 (patch)
tree02629c584461df3b6f80d09a1de6298af4c3440c /erts/emulator/test
parentf91c381afa2ebed6e37b49b4cc3f81bb9ca9e3eb (diff)
downloadotp-5d67cc7f4c176ea6ab4d2538443d5fe264152861.tar.gz
otp-5d67cc7f4c176ea6ab4d2538443d5fe264152861.tar.bz2
otp-5d67cc7f4c176ea6ab4d2538443d5fe264152861.zip
erts: Add new allocator strategy aoffcbf
with better performance than aoffcaobf as we don't have to rearrange the search tree when there are blocks of equal size.
Diffstat (limited to 'erts/emulator/test')
-rw-r--r--erts/emulator/test/alloc_SUITE_data/allocator_test.h3
-rw-r--r--erts/emulator/test/alloc_SUITE_data/coalesce.c2
-rw-r--r--erts/emulator/test/alloc_SUITE_data/rbtree.c90
3 files changed, 48 insertions, 47 deletions
diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
index c37b074f93..2d6c5f9dc7 100644
--- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h
+++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
@@ -102,7 +102,8 @@ typedef void* erts_cond;
#define RBT_IS_TREE(T) ((Ulong) ALC_TEST1(RBT_OP(7), (T)))
#define IS_BF_ALGO(A) ((Ulong) ALC_TEST1(RBT_OP(8), (A)))
#define RBT_MAX_SZ(T) ((Ulong) ALC_TEST1(RBT_OP(9), (T)))
-#define IS_CBF(A) ((Ulong) ALC_TEST1(RBT_OP(0xa), (A)))
+#define IS_BF(A) ((Ulong) ALC_TEST1(RBT_OP(0xa), (A)))
+#define RBT_PREV(T) ((RBTL_t *) ALC_TEST1(RBT_OP(0xb), (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 36710bf7b5..9da49a0d14 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[] = {"-tsmbcs511","-tmmbcs511", "-tsbct512", "-trmbcmt100", "-tas", NULL, NULL};
- char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcaobf", NULL};
+ char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcbf", "aoffcaobf", 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 702f075304..49df2f0245 100644
--- a/erts/emulator/test/alloc_SUITE_data/rbtree.c
+++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c
@@ -85,23 +85,21 @@ print_tree(TestCaseState_t *tcs, RBT_t *root)
static RBT_t *
check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
{
- enum { BF, AOBF, AOFF, AOFFCAOBF }type;
+ 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;
long blacks, curr_blacks;
+ int have_max_sz;
res = NULL;
- if (IS_BF_ALGO(alc)) {
- if (IS_AOBF(alc)) type = AOBF;
- else type = BF;
- }
- else { /* AOFF_ALGO */
- if (IS_CBF(alc)) type = AOFFCAOBF;
- else type = AOFF;
- }
+ if (IS_AOBF(alc)) type = AOBF;
+ else if (IS_BF(alc)) type = BF;
+ else type = AOFF;
+
+ have_max_sz = !IS_BF_ALGO(alc);
root = RBT_ROOT(alc, size);
@@ -191,17 +189,10 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
break;
case AOFF:
ASSERT(tcs, y < x);
- ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
break;
- case AOFFCAOBF:
- {
- void* x_crr = BLK_TO_MBC(x);
- void* y_crr = BLK_TO_MBC(y);
- ASSERT(tcs, (y < x && (x_crr != y_crr || x_sz == y_sz))
- || (y_sz < x_sz && x_crr == y_crr));
- ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
- break;
- }
+ }
+ if (have_max_sz) {
+ ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
}
}
@@ -219,27 +210,22 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
break;
case AOFF:
ASSERT(tcs, y > x);
- ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
break;
- case AOFFCAOBF:
- {
- void* x_crr = BLK_TO_MBC(x);
- void* y_crr = BLK_TO_MBC(y);
- ASSERT(tcs, (y > x && (x_crr != y_crr || x_sz == y_sz))
- || (y_sz > x_sz && x_crr == y_crr));
- ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
- break;
- }
+ }
+ if (have_max_sz) {
+ ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
}
}
if (type == BF) {
Ulong l_sz;
- RBTL_t *l = RBT_NEXT(x);
+ RBTL_t *l, *prev=x;
for (l = RBT_NEXT(x); l; l = RBT_NEXT(l)) {
l_sz = BLK_SZ(l);
ASSERT(tcs, l_sz == x_sz);
ASSERT(tcs, !RBT_IS_TREE(l));
+ ASSERT(tcs, RBT_PREV(l) == prev);
+ prev = l;
}
}
@@ -262,18 +248,7 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
res = x;
}
break;
- case AOFFCAOBF:
- if (BLK_TO_MBC(x) != BLK_TO_MBC(res) || x_sz == y_sz) {
- if (x < res) {
- res = x;
- }
- }
- else if (x_sz < y_sz) {
- res = x;
- }
- break;
}
-
}
}
@@ -310,7 +285,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size, int ignore_null)
tmp = ALLOC(a, sz - ABLK_HDR_SZ);
ASSERT(tcs, tmp);
y = UMEM2BLK(tmp);
- if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) {
+ if (!IS_BF(a)) {
ASSERT(tcs, x == y);
}
else {
@@ -488,6 +463,7 @@ testcase_run(TestCaseState_t *tcs)
char *argv2[] = {"-tasaobf", NULL};
char *argv3[] = {"-tasaoff", NULL};
char *argv4[] = {"-tasaoffcaobf", NULL};
+ char *argv5[] = {"-tasaoffcbf", NULL};
Allctr_t *a;
rbtree_test_data *td;
@@ -511,6 +487,7 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, IS_BF_ALGO(a));
ASSERT(tcs, !IS_AOBF(a));
+ ASSERT(tcs, IS_BF(a));
test_it(tcs);
@@ -529,6 +506,7 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, IS_BF_ALGO(a));
ASSERT(tcs, IS_AOBF(a));
+ ASSERT(tcs, !IS_BF(a));
test_it(tcs);
@@ -546,7 +524,8 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, !IS_BF_ALGO(a));
- ASSERT(tcs, !IS_CBF(a));
+ ASSERT(tcs, !IS_AOBF(a));
+ ASSERT(tcs, !IS_BF(a));
test_it(tcs);
test_carrier_migration(tcs);
@@ -556,7 +535,7 @@ testcase_run(TestCaseState_t *tcs)
testcase_printf(tcs, "Address order first fit test succeeded!\n");
- /* Address order first fit, best fit within carrier */
+ /* Address order first fit, aobf within carrier */
testcase_printf(tcs, "Starting test of aoffcaobf...\n");
@@ -565,7 +544,28 @@ testcase_run(TestCaseState_t *tcs)
ASSERT(tcs, a);
ASSERT(tcs, !IS_BF_ALGO(a));
- ASSERT(tcs, IS_CBF(a));
+ ASSERT(tcs, IS_AOBF(a));
+ ASSERT(tcs, !IS_BF(a));
+
+ test_it(tcs);
+ test_carrier_migration(tcs);
+
+ STOP_ALC(a);
+ td->allocator = NULL;
+
+ testcase_printf(tcs, "aoffcaobf test succeeded!\n");
+
+ /* Address order first fit, bf within carrier */
+
+ testcase_printf(tcs, "Starting test of aoffcbf...\n");
+
+ current_rbt_type_op_base = AO_FIRSTFIT_OP_BASE;
+ td->allocator = a = START_ALC("rbtree_aoffcbf_", 0, argv5);
+
+ ASSERT(tcs, a);
+ ASSERT(tcs, !IS_BF_ALGO(a));
+ ASSERT(tcs, !IS_AOBF(a));
+ ASSERT(tcs, IS_BF(a));
test_it(tcs);
test_carrier_migration(tcs);