erts: Add "bestfit within carrier" for aoff allocator (aoffcbf)

3 files changed, 67 insertions, 7 deletions

diff --git a/erts/emulator/test/alloc_SUITE_data/allocator_test.h b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
index c0396ddb61..ec5bb9dcd6 100644
--- a/erts/emulator/test/alloc_SUITE_data/allocator_test.h
+++ b/erts/emulator/test/alloc_SUITE_data/allocator_test.h
@@ -75,6 +75,7 @@ typedef void* erts_cond;
 #define PREV_BLK(B)		((Block_t *)	ALC_TEST1(0x019, (B)))
 #define IS_MBC_FIRST_BLK(A,B)	((Ulong)	ALC_TEST2(0x01a, (A), (B)))
 #define UNIT_SZ			((Ulong)	ALC_TEST0(0x01b))
+#define BLK_TO_MBC(B)		((Carrier_t *)	ALC_TEST1(0x01c, (B)))
 
 /* From erl_goodfit_alloc.c */
 #define BKT_IX(A, S)		((Ulong)	ALC_TEST2(0x100, (A), (S)))
@@ -91,8 +92,9 @@ typedef void* erts_cond;
 #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 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)))
 
 /* 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 981fa6d43e..1fb4d7791d 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", NULL};
+    char *alg[] = {"af", "gf", "bf", "aobf", "aoff", "aoffcbf", 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 4e7f821baf..105c9c0eb4 100644
--- a/erts/emulator/test/alloc_SUITE_data/rbtree.c
+++ b/erts/emulator/test/alloc_SUITE_data/rbtree.c
@@ -85,7 +85,7 @@ 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 }type;
+    enum { BF, AOBF, AOFF, AOFFCBF }type;
     int i, max_i;
     char stk[128];
     RBT_t *root, *x, *y, *res;
@@ -94,9 +94,14 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 
     res = NULL;
 
-    if      (IS_AOBF(alc)) type = AOBF;
-    else if (IS_AOFF(alc)) type = AOFF;
-    else type = BF;
+    if (IS_BF_ALGO(alc)) {
+	if (IS_AOBF(alc)) type = AOBF;
+	else type = BF;
+    }
+    else { /* AOFF_ALGO */
+	if (IS_CBF(alc)) type = AOFFCBF;
+	else type = AOFF;
+    }
 
     root = RBT_ROOT(alc);
 
@@ -188,6 +193,15 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 		ASSERT(tcs, y < x);
 		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 		break;
+	    case AOFFCBF:
+		{
+		    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;
+		}
 	    }
 	}
 
@@ -207,6 +221,15 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 		ASSERT(tcs, y > x);
 		ASSERT(tcs, RBT_MAX_SZ(y) <= RBT_MAX_SZ(x));
 		break;
+	    case AOFFCBF:
+		{
+		    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;
+		}
 	    }
 	}
 
@@ -239,7 +262,18 @@ check_tree(TestCaseState_t *tcs, Allctr_t *alc, Ulong size)
 			res = x;
 		    }
 		    break;
+		case AOFFCBF:
+		    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;
 		}
+
 	    }
 	}
 
@@ -273,7 +307,7 @@ do_check(TestCaseState_t *tcs, Allctr_t *a, Ulong size)
     tmp = ALLOC(a, sz - ABLK_HDR_SZ);
     ASSERT(tcs, tmp);
     y = UMEM2BLK(tmp);
-    if (IS_AOBF(a)) {
+    if (!(IS_BF_ALGO(a) && !IS_AOBF(a))) {
 	ASSERT(tcs, x == y);
     }
     else {
@@ -369,6 +403,7 @@ testcase_run(TestCaseState_t *tcs)
     char *argv1[] = {"-tasbf", NULL};
     char *argv2[] = {"-tasaobf", NULL};
     char *argv3[] = {"-tasaoff", NULL};
+    char *argv4[] = {"-tasaoffcbf", NULL};
     Allctr_t *a;
     rbtree_test_data *td;
 
@@ -390,6 +425,7 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = a = START_ALC("rbtree_bf_", 0, argv1);
 
     ASSERT(tcs, a);
+    ASSERT(tcs, IS_BF_ALGO(a));
     ASSERT(tcs, !IS_AOBF(a));
 
     test_it(tcs);
@@ -407,6 +443,7 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = a = START_ALC("rbtree_aobf_", 0, argv2);
 
     ASSERT(tcs, a);
+    ASSERT(tcs, IS_BF_ALGO(a));
     ASSERT(tcs, IS_AOBF(a));
 
     test_it(tcs);
@@ -424,6 +461,8 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = a = START_ALC("rbtree_aoff_", 0, argv3);
 
     ASSERT(tcs, a);
+    ASSERT(tcs, !IS_BF_ALGO(a));
+    ASSERT(tcs, !IS_CBF(a));
 
     test_it(tcs);
 
@@ -431,4 +470,23 @@ testcase_run(TestCaseState_t *tcs)
     td->allocator = NULL;
 
     testcase_printf(tcs, "Address order first fit test succeeded!\n");
+
+    /* Address order first fit, best fit 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, argv4);
+
+    ASSERT(tcs, a);
+    ASSERT(tcs, !IS_BF_ALGO(a));
+    ASSERT(tcs, IS_CBF(a));
+
+    test_it(tcs);
+
+    STOP_ALC(a);
+    td->allocator = NULL;
+
+    testcase_printf(tcs, "aoffcbf test succeeded!\n");
+
 }