alloc: Use least reserved PDCH for algo A

Currently the slot selection of algorithm A is based on the current
slot usage by active TBF. Especially in the Dl after UL case which
reflects the commen use case "MS initiates TCP connection", the
resulting distribution is not optimal with respect to PDCH usage.

This commit changes the implementation to use the slot reservation
information instead.

Sponsored-by: On-Waves ehf

4 files changed, 118 insertions, 34 deletions

diff --git a/src/gprs_rlcmac_ts_alloc.cpp b/src/gprs_rlcmac_ts_alloc.cpp
index 8c42bb19..c1b73398 100644
--- a/src/gprs_rlcmac_ts_alloc.cpp
+++ b/src/gprs_rlcmac_ts_alloc.cpp
@@ -234,6 +234,65 @@ static int find_least_busy_pdch(struct gprs_rlcmac_trx *trx,
 	return min_ts;
 }
 
+static int find_least_reserved_pdch(struct gprs_rlcmac_trx *trx,
+	enum gprs_rlcmac_tbf_direction dir,
+	uint8_t mask,
+	int *free_usf = 0)
+{
+	unsigned ts;
+	int min_used = INT_MAX;
+	int min_ts = -1;
+	int min_usf = -1;
+
+	for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
+		struct gprs_rlcmac_pdch *pdch = &trx->pdch[ts];
+		int num_tbfs;
+		int usf = -1; /* must be signed */
+
+		if (((1 << ts) & mask) == 0)
+			continue;
+
+		num_tbfs =
+			pdch->num_reserved(GPRS_RLCMAC_DL_TBF) +
+			pdch->num_reserved(GPRS_RLCMAC_UL_TBF);
+
+		if (num_tbfs < min_used) {
+			/* We have found a candidate */
+			/* Make sure that an USF is available */
+			if (dir == GPRS_RLCMAC_UL_TBF) {
+				usf = find_free_usf(pdch);
+				if (usf < 0) {
+					LOGP(DRLCMAC, LOGL_DEBUG,
+						"- Skipping TS %d, because "
+						"no USF available\n", ts);
+					continue;
+				}
+			}
+			if (min_ts >= 0)
+				LOGP(DRLCMAC, LOGL_DEBUG,
+					"- Skipping TS %d, because "
+					"num TBFs %d > %d\n",
+					min_ts, min_used, num_tbfs);
+			min_used = num_tbfs;
+			min_ts = ts;
+			min_usf = usf;
+		} else {
+			LOGP(DRLCMAC, LOGL_DEBUG,
+				"- Skipping TS %d, because "
+				"num TBFs %d >= %d\n",
+				ts, num_tbfs, min_used);
+		}
+	}
+
+	if (min_ts < 0)
+		return -1;
+
+	if (free_usf)
+		*free_usf = min_usf;
+
+	return min_ts;
+}
+
 static void attach_tbf_to_pdch(struct gprs_rlcmac_pdch *pdch,
 	struct gprs_rlcmac_tbf *tbf)
 {
@@ -297,7 +356,7 @@ int alloc_algorithm_a(struct gprs_rlcmac_bts *bts,
 	if (!mask)
 		return -EINVAL;
 
-	ts = find_least_busy_pdch(tbf->trx, tbf->direction, mask, &usf);
+	ts = find_least_reserved_pdch(tbf->trx, tbf->direction, mask, &usf);
 
 	if (ts < 0) {
 		LOGP(DRLCMAC, LOGL_NOTICE, "- Failed "
diff --git a/tests/alloc/AllocTest.cpp b/tests/alloc/AllocTest.cpp
index bf93f579..973ee29f 100644
--- a/tests/alloc/AllocTest.cpp
+++ b/tests/alloc/AllocTest.cpp
@@ -586,7 +586,7 @@ static void test_successive_allocation()
 		32, "algorithm B class 10 (DL after UL)");
 
 	test_successive_allocation(alloc_algorithm_a, 1, 1, TEST_MODE_UL_AFTER_DL,
-		7, "algorithm A (UL after DL)");
+		32, "algorithm A (UL after DL)");
 	test_successive_allocation(alloc_algorithm_b, 10, 10, TEST_MODE_UL_AFTER_DL,
 		32, "algorithm B class 10 (UL after DL)");
 
diff --git a/tests/alloc/AllocTest.err b/tests/alloc/AllocTest.err
index 7bb29950..af9b1340 100644
--- a/tests/alloc/AllocTest.err
+++ b/tests/alloc/AllocTest.err
@@ -11,7 +11,7 @@ No TFI available.
 No TFI available.
 No TFI available.
 No TFI available.
-- Failed to allocate a TS, no USF available
+No TFI available.
 No TFI available.
 No TFI available.
 No TFI available.
diff --git a/tests/alloc/AllocTest.ok b/tests/alloc/AllocTest.ok
index 231b42fd..00cff6e7 100644
--- a/tests/alloc/AllocTest.ok
+++ b/tests/alloc/AllocTest.ok
@@ -8828,37 +8828,37 @@ Going to test assignment with many TBF, algorithm B class 10 (DL and UL)
   Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm A (DL after UL)
  TBF[0] class 1 reserves ...C....
- TBF[1] class 1 reserves ...C....
- TBF[2] class 1 reserves ...C....
- TBF[3] class 1 reserves ...C....
- TBF[4] class 1 reserves ...C....
+ TBF[1] class 1 reserves ....C...
+ TBF[2] class 1 reserves .....C..
+ TBF[3] class 1 reserves ......C.
+ TBF[4] class 1 reserves .......C
  TBF[5] class 1 reserves ...C....
- TBF[6] class 1 reserves ...C....
- TBF[7] class 1 reserves ...C....
- TBF[8] class 1 reserves ...C....
- TBF[9] class 1 reserves ...C....
+ TBF[6] class 1 reserves ....C...
+ TBF[7] class 1 reserves .....C..
+ TBF[8] class 1 reserves ......C.
+ TBF[9] class 1 reserves .......C
  TBF[10] class 1 reserves ...C....
- TBF[11] class 1 reserves ...C....
- TBF[12] class 1 reserves ...C....
- TBF[13] class 1 reserves ...C....
- TBF[14] class 1 reserves ...C....
+ TBF[11] class 1 reserves ....C...
+ TBF[12] class 1 reserves .....C..
+ TBF[13] class 1 reserves ......C.
+ TBF[14] class 1 reserves .......C
  TBF[15] class 1 reserves ...C....
- TBF[16] class 1 reserves ...C....
- TBF[17] class 1 reserves ...C....
- TBF[18] class 1 reserves ...C....
- TBF[19] class 1 reserves ...C....
+ TBF[16] class 1 reserves ....C...
+ TBF[17] class 1 reserves .....C..
+ TBF[18] class 1 reserves ......C.
+ TBF[19] class 1 reserves .......C
  TBF[20] class 1 reserves ...C....
- TBF[21] class 1 reserves ...C....
- TBF[22] class 1 reserves ...C....
- TBF[23] class 1 reserves ...C....
- TBF[24] class 1 reserves ...C....
+ TBF[21] class 1 reserves ....C...
+ TBF[22] class 1 reserves .....C..
+ TBF[23] class 1 reserves ......C.
+ TBF[24] class 1 reserves .......C
  TBF[25] class 1 reserves ...C....
- TBF[26] class 1 reserves ...C....
- TBF[27] class 1 reserves ...C....
- TBF[28] class 1 reserves ...C....
- TBF[29] class 1 reserves ...C....
+ TBF[26] class 1 reserves ....C...
+ TBF[27] class 1 reserves .....C..
+ TBF[28] class 1 reserves ......C.
+ TBF[29] class 1 reserves .......C
  TBF[30] class 1 reserves ...C....
- TBF[31] class 1 reserves ...C....
+ TBF[31] class 1 reserves ....C...
   Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (DL after UL)
  TBF[0] class 10 reserves ...DDCD.
@@ -8896,13 +8896,38 @@ Going to test assignment with many TBF, algorithm B class 10 (DL after UL)
   Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm A (UL after DL)
  TBF[0] class 1 reserves ...U....
- TBF[1] class 1 reserves ...U....
- TBF[2] class 1 reserves ...U....
- TBF[3] class 1 reserves ...U....
- TBF[4] class 1 reserves ...U....
+ TBF[1] class 1 reserves ....U...
+ TBF[2] class 1 reserves .....U..
+ TBF[3] class 1 reserves ......U.
+ TBF[4] class 1 reserves .......U
  TBF[5] class 1 reserves ...U....
- TBF[6] class 1 reserves ...U....
-  Successfully allocated 7 UL TBFs
+ TBF[6] class 1 reserves ....U...
+ TBF[7] class 1 reserves .....U..
+ TBF[8] class 1 reserves ......U.
+ TBF[9] class 1 reserves .......U
+ TBF[10] class 1 reserves ...U....
+ TBF[11] class 1 reserves ....U...
+ TBF[12] class 1 reserves .....U..
+ TBF[13] class 1 reserves ......U.
+ TBF[14] class 1 reserves .......U
+ TBF[15] class 1 reserves ...U....
+ TBF[16] class 1 reserves ....U...
+ TBF[17] class 1 reserves .....U..
+ TBF[18] class 1 reserves ......U.
+ TBF[19] class 1 reserves .......U
+ TBF[20] class 1 reserves ...U....
+ TBF[21] class 1 reserves ....U...
+ TBF[22] class 1 reserves .....U..
+ TBF[23] class 1 reserves ......U.
+ TBF[24] class 1 reserves .......U
+ TBF[25] class 1 reserves ...U....
+ TBF[26] class 1 reserves ....U...
+ TBF[27] class 1 reserves .....U..
+ TBF[28] class 1 reserves ......U.
+ TBF[29] class 1 reserves .......U
+ TBF[30] class 1 reserves ...U....
+ TBF[31] class 1 reserves ....U...
+  Successfully allocated 32 UL TBFs
 Going to test assignment with many TBF, algorithm B class 10 (UL after DL)
  TBF[0] class 10 reserves .....U..
  TBF[1] class 10 reserves ......U.