[PATCH] osmo-pcu[master]: Simplify TS alloc: split into digestible pieces

This is merely a historical archive of years 2008-2021, before the migration to mailman3.

A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/gerrit-log@lists.osmocom.org/.

Max gerrit-no-reply at lists.osmocom.org
Sat Sep 9 13:25:15 UTC 2017


Hello Neels Hofmeyr, Jenkins Builder,

I'd like you to reexamine a change.  Please visit

    https://gerrit.osmocom.org/3760

to look at the new patch set (#7).

Simplify TS alloc: split into digestible pieces

Algorithm B implementation is way too big and complex to maintain or
even to follow the code. Split it into set of smaller functions with
documented interfaces to make it easier to read and modify.

This opens up the road for reusing those functions in implementation of
additional allocation algorithms. The test results are intentionally
left unchanged to avoid potential regressions.

Change-Id: I02da2b8ba8c9c8815dae0e39e1fed277ca0df171
Related: OS#2400
---
M src/gprs_rlcmac_ts_alloc.cpp
M tests/alloc/AllocTest.cpp
2 files changed, 233 insertions(+), 133 deletions(-)


  git pull ssh://gerrit.osmocom.org:29418/osmo-pcu refs/changes/60/3760/7

diff --git a/src/gprs_rlcmac_ts_alloc.cpp b/src/gprs_rlcmac_ts_alloc.cpp
index ed4a79e..80eacd6 100644
--- a/src/gprs_rlcmac_ts_alloc.cpp
+++ b/src/gprs_rlcmac_ts_alloc.cpp
@@ -217,6 +217,16 @@
 
 }
 
+/*! Return the TS which corresponds to least busy PDCH
+ *
+ *  \param[in,out] trx Pointer to TRX object
+ *  \param[in] dir TBF direction
+ *  \param[in] mask set of available timeslots
+ *  \param[in] fn Function pointer to function which computes number of associated TBFs
+ *  \param[out] free_tfi Free TFI
+ *  \param[out] free_usf Free USF
+ *  \returns TS number or -1 if unable to find
+ */
 static int find_least_busy_pdch(struct gprs_rlcmac_trx *trx,
 	enum gprs_rlcmac_tbf_direction dir,
 	uint8_t mask,
@@ -374,18 +384,27 @@
 /*! Return free TFI
  *
  *  \param[in,out] bts Pointer to BTS struct
- *  \param[in] trx Pointer to TRX struct
+ *  \param[in] trx Optional pointer to TRX struct
  *  \param[in] ms Pointer to MS object
  *  \param[in] dir DL or UL direction
  *  \param[in] use_trx which TRX to use or -1 if it should be selected based on what MS uses
  *  \param[out] trx_no_ TRX number on which TFI was found
  *  \returns negative error code or 0 on success
  */
-static int tfi_find_free(BTS *bts, const GprsMs *ms,
+static int tfi_find_free(BTS *bts, const gprs_rlcmac_trx *trx, const GprsMs *ms,
 			 enum gprs_rlcmac_tbf_direction dir, int8_t use_trx, uint8_t *trx_no_)
 {
 	int tfi;
 	uint8_t trx_no;
+
+	if (trx) {
+		if (use_trx >= 0 && use_trx != trx->trx_no) {
+			LOGP(DRLCMAC, LOGL_ERROR, "- Requested incompatible TRX %d (current is %d)\n",
+			     use_trx, trx->trx_no);
+			return -EINVAL;
+		}
+		use_trx = trx->trx_no;
+	}
 
 	if (use_trx == -1 && ms->current_trx())
 		use_trx = ms->current_trx()->trx_no;
@@ -394,8 +413,7 @@
 	if (tfi < 0)
 		return -EBUSY;
 
-	if (trx_no_)
-		*trx_no_ = trx_no;
+	*trx_no_ = trx_no;
 
 	return tfi;
 }
@@ -811,6 +829,197 @@
 	return 0;
 }
 
+/*! Update MS' reserved timeslots
+ *
+ *  \param[in,out] trx Pointer to TRX struct
+ *  \param[in,out] ms_ Pointer to MS object
+ *  \param[in] tbf_ Pointer to TBF struct
+ *  \param[in] res_ul_slots Newly reserved UL slots
+ *  \param[in] res_dl_slots Newly reserved DL slots
+ *  \param[in] ul_slots available UL slots (for logging only)
+ *  \param[in] dl_slots available DL slots (for logging only)
+ */
+static void update_ms_reserved_slots(gprs_rlcmac_trx *trx, GprsMs *ms, uint8_t res_ul_slots, uint8_t res_dl_slots,
+				     uint8_t ul_slots, uint8_t dl_slots)
+{
+	char slot_info[9] = { 0 };
+
+	if (res_ul_slots == ms->reserved_ul_slots() && res_dl_slots == ms->reserved_dl_slots())
+		return;
+
+	/* The reserved slots have changed, update the MS */
+	ms->set_reserved_slots(trx, res_ul_slots, res_dl_slots);
+
+	LOGP(DRLCMAC, LOGL_DEBUG, "- Reserved DL/UL slots: (TS=0)\"%s\"(TS=7)\n",
+	     set_flag_chars(set_flag_chars(set_flag_chars(slot_info, dl_slots, 'D', '.'), ul_slots, 'U'),
+			    ul_slots & dl_slots, 'C'));
+}
+
+/*! Assign given UL timeslots to UL TBF
+ *
+ *  \param[in,out] ul_tbf Pointer to UL TBF struct
+ *  \param[in,out] trx Pointer to TRX object
+ *  \param[in] ul_slots Set of slots to be assigned
+ *  \param[in] tfi selected TFI
+ *  \param[in] usf selected USF
+ */
+static void assign_ul_tbf_slots(struct gprs_rlcmac_ul_tbf *ul_tbf, gprs_rlcmac_trx *trx, uint8_t ul_slots, int tfi,
+				int *usf)
+{
+	uint8_t ts;
+
+	for (ts = 0; ts < 8; ts++) {
+		if (!(ul_slots & (1 << ts)))
+			continue;
+
+		OSMO_ASSERT(usf[ts] >= 0);
+
+		LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning UL TS %u\n", ts);
+		assign_uplink_tbf_usf(&trx->pdch[ts], ul_tbf, tfi, usf[ts]);
+	}
+}
+
+/*! Assign given DL timeslots to DL TBF
+ *
+ *  \param[in,out] dl_tbf Pointer to DL TBF struct
+ *  \param[in,out] trx Pointer to TRX object
+ *  \param[in] ul_slots Set of slots to be assigned
+ *  \param[in] tfi selected TFI
+ */
+static void assign_dl_tbf_slots(struct gprs_rlcmac_dl_tbf *dl_tbf, gprs_rlcmac_trx *trx, uint8_t dl_slots, int tfi)
+{
+	uint8_t ts;
+
+	for (ts = 0; ts < 8; ts++) {
+		if (!(dl_slots & (1 << ts)))
+			continue;
+
+		LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning DL TS %u\n", ts);
+		assign_dlink_tbf(&trx->pdch[ts], dl_tbf, tfi);
+	}
+}
+
+/*! Count used bits in slots and reserved_slots bitmasks
+ *
+ *  \param[in] slots Timeslots in use
+ *  \param[in] reserved_slots Reserved timeslots
+ *  \param[out] slotcount Number of TS in use
+ *  \param[out] avail_count Number of reserved TS
+ */
+static void update_slot_counters(uint8_t slots, uint8_t reserved_slots, uint8_t *slotcount, uint8_t *avail_count)
+{
+	(*slotcount) = pcu_bitcount(slots);
+	(*avail_count) = pcu_bitcount(reserved_slots);
+}
+
+/*! Return slot mask with single TS from a given UL/DL set according to TBF's direction, ts pointer is set to that TS
+ * number or to negative value on error
+ *
+ *  \param[in,out] trx Pointer to TRX object
+ *  \param[in] tbf Pointer to TBF object
+ *  \param[in] dl_slots set of DL timeslots
+ *  \param[in] ul_slots set of UL timeslots
+ *  \param[in,out] ts corresponding TS or -1 for autoselection
+ *  \returns slot mask with single UL or DL timeslot number if possible
+ */
+static uint8_t get_single_ts(gprs_rlcmac_trx *trx, const gprs_rlcmac_tbf *tbf, uint8_t dl_slots, uint8_t ul_slots,
+			     int *ts)
+{
+	uint8_t ret = dl_slots & ul_slots; /* Make sure to consider the first common slot only */
+
+	if (*ts < 0)
+		*ts = find_least_busy_pdch(trx, tbf->direction, ret, compute_usage_by_num_tbfs, NULL, NULL);
+
+	if (*ts < 0)
+		return pcu_lsb(ret);
+
+	return ret & (1 << (*ts));
+}
+
+/*! Find set of UL timeslots available for allocation
+ *
+ *  \param[in,out] trx Pointer to TRX object
+ *  \param[in] tbf Pointer to TBF object
+ *  \param[in] single Flag to force the single TS allocation
+ *  \param[in] dl_slots set of DL timeslots
+ *  \param[in] reserved_ul_slots set of reserved UL timeslots
+ *  \param[in] first_common_ts First TS common for both UL and DL or -1 if unknown
+ *  \param[in,out] usf USF array
+ *  \param[in,out] ul_slots set of UL timeslots
+ *  \returns negative error code or first selected TS on success
+ */
+static int select_ul_slot_set(gprs_rlcmac_trx *trx, const gprs_rlcmac_tbf *tbf, bool single, uint8_t dl_slots,
+			      uint8_t reserved_ul_slots, int8_t first_common_ts,
+			      int *usf, uint8_t *ul_slots)
+{
+	int ts = first_common_ts;
+	char slot_info[9] = { 0 };
+	int free_usf = -1;
+
+	if (single)
+		(*ul_slots) = get_single_ts(trx, tbf, dl_slots, *ul_slots, &ts);
+
+	if ((*ul_slots) == 0) {
+		LOGP(DRLCMAC, LOGL_NOTICE, "No uplink slots available\n");
+		return -EINVAL;
+	}
+
+	if (first_common_ts >= 0)
+		(*ul_slots) = 1 << first_common_ts;
+	else
+		(*ul_slots) = (*ul_slots) & dl_slots;
+
+	ts = find_least_busy_pdch(trx, GPRS_RLCMAC_UL_TBF, *ul_slots, compute_usage_by_num_tbfs, NULL, &free_usf);
+
+	if (free_usf < 0) {
+		LOGP(DRLCMAC, LOGL_NOTICE, "No USF available\n");
+		return -EBUSY;
+	}
+	OSMO_ASSERT(ts >= 0 && ts <= 8);
+
+	(*ul_slots) = 1 << ts;
+	usf[ts] = free_usf;
+
+	LOGP(DRLCMAC, LOGL_DEBUG, "- Selected UL slots: (TS=0)\"%s\"(TS=7)%s\n",
+	     set_flag_chars(set_flag_chars(slot_info, reserved_ul_slots, 'u', '.'), *ul_slots, 'U'),
+	     single ? ", single" : "");
+
+	return ffs(*ul_slots) - 1;
+}
+
+/*! Find set of DL timeslots available for allocation
+ *
+ *  \param[in,out] trx Pointer to TRX object
+ *  \param[in] tbf Pointer to TBF object
+ *  \param[in] single Flag to force the single TS allocation
+ *  \param[in] ul_slots set of UL timeslots
+ *  \param[in] reserved_dl_slots set of reserved DL timeslots
+ *  \param[in] first_common_ts First TS common for both UL and DL or -1 if unknown
+ *  \param[in,out] dl_slots set of DL timeslots
+ *  \returns negative error code or first selected TS on success
+ */
+static int select_dl_slot_set(gprs_rlcmac_trx *trx, const gprs_rlcmac_tbf *tbf, bool single, uint8_t ul_slots,
+			      uint8_t reserved_dl_slots, int8_t first_common_ts,
+			      uint8_t *dl_slots)
+{
+	int ts = first_common_ts;
+	char slot_info[9] = { 0 };
+
+	if (single)
+		(*dl_slots) = get_single_ts(trx, tbf, *dl_slots, ul_slots, &ts);
+
+	if ((*dl_slots) == 0) {
+		LOGP(DRLCMAC, LOGL_NOTICE, "No downlink slots available\n");
+		return -EINVAL;
+	}
+
+	LOGP(DRLCMAC, LOGL_DEBUG, "- Selected DL slots: (TS=0)\"%s\"(TS=7)%s\n",
+	     set_flag_chars(set_flag_chars(slot_info, reserved_dl_slots, 'd', '.'), (*dl_slots), 'D'),
+	     single ? ", single" : "");
+
+	return ffs(*dl_slots) - 1;
+}
+
 /*! Slot Allocation: Algorithm B
  *
  * Assign as many downlink slots as possible.
@@ -833,8 +1042,6 @@
 	int8_t first_common_ts;
 	uint8_t slotcount = 0;
 	uint8_t avail_count = 0, trx_no;
-	char slot_info[9] = {0};
-	int ts;
 	int first_ts = -1;
 	int usf[8] = {-1, -1, -1, -1, -1, -1, -1, -1};
 	int rc;
@@ -855,18 +1062,8 @@
 	first_common_ts = ms->first_common_ts();
 	trx = ms->current_trx();
 
-	if (trx) {
-		if (use_trx >= 0 && use_trx != trx->trx_no) {
-			LOGP(DRLCMAC, LOGL_ERROR,
-				"- Requested incompatible TRX %d (current is %d)\n",
-				use_trx, trx->trx_no);
-			return -EINVAL;
-		}
-		use_trx = trx->trx_no;
-	}
-
 	/* Step 2a: Find usable TRX and TFI */
-	tfi = tfi_find_free(bts->bts, ms, tbf->direction, use_trx, &trx_no);
+	tfi = tfi_find_free(bts->bts, trx, ms, tbf->direction, use_trx, &trx_no);
 	if (tfi < 0) {
 		LOGP(DRLCMAC, LOGL_NOTICE, "- Failed to allocate a TFI\n");
 		return tfi;
@@ -886,95 +1083,29 @@
 	}
 
 	/* Step 3: Derive the slot set for the current TBF */
-	if (single) {
-		/* Make sure to consider the first common slot only */
-		ul_slots = dl_slots = dl_slots & ul_slots;
-
-		ts = first_common_ts;
-
-		if (ts < 0)
-			ts = find_least_busy_pdch(trx, tbf->direction,
-				dl_slots & ul_slots, compute_usage_by_num_tbfs,
-				NULL, NULL);
-		if (ts < 0)
-			ul_slots = dl_slots = pcu_lsb(dl_slots & ul_slots);
-		else
-			ul_slots = dl_slots = (dl_slots & ul_slots) & (1<<ts);
-	}
-
-	if (dl_slots == 0) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "No downlink slots available\n");
-		return -EINVAL;
-	}
-
-	if (ul_slots == 0) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "No uplink slots available\n");
-		return -EINVAL;
-	}
-
 	if (tbf->direction == GPRS_RLCMAC_DL_TBF) {
-		LOGP(DRLCMAC, LOGL_DEBUG,
-			"- Selected DL slots: (TS=0)\"%s\"(TS=7)%s\n",
-			set_flag_chars(set_flag_chars(slot_info,
-					reserved_dl_slots, 'd', '.'),
-					dl_slots, 'D'),
-			single ? ", single" : "");
+		first_ts = select_dl_slot_set(trx, tbf, single, ul_slots, reserved_dl_slots, first_common_ts,
+					      &dl_slots);
 
-		/* assign downlink */
-		if (dl_slots == 0) {
-			LOGP(DRLCMAC, LOGL_NOTICE, "No downlink slots "
-				"available\n");
-			return -EINVAL;
-		}
-		slotcount = pcu_bitcount(dl_slots);
-		first_ts = ffs(dl_slots) - 1;
-		avail_count = pcu_bitcount(reserved_dl_slots);
-
+		update_slot_counters(dl_slots, reserved_dl_slots, &slotcount, &avail_count);
 	} else {
-		int free_usf = -1;
-
-		if (first_common_ts >= 0)
-			ul_slots = 1 << first_common_ts;
-		else
-			ul_slots = ul_slots & dl_slots;
-
-		ts = find_least_busy_pdch(trx, GPRS_RLCMAC_UL_TBF,
-			ul_slots, compute_usage_by_num_tbfs,
-			NULL, &free_usf);
-
-		if (free_usf < 0) {
-			LOGP(DRLCMAC, LOGL_NOTICE, "No USF available\n");
-			return -EBUSY;
-		}
-		OSMO_ASSERT(ts >= 0 && ts <= 8);
-
-		ul_slots = 1 << ts;
-		usf[ts] = free_usf;
-
-		LOGP(DRLCMAC, LOGL_DEBUG,
-			"- Selected UL slots: (TS=0)\"%s\"(TS=7)%s\n",
-			set_flag_chars(set_flag_chars(slot_info,
-					reserved_ul_slots, 'u', '.'),
-					ul_slots, 'U'),
-			single ? ", single" : "");
-
-		slotcount++;
-		first_ts = ts;
+		first_ts = select_ul_slot_set(trx, tbf, single, dl_slots, reserved_ul_slots, first_common_ts, usf,
+					      &ul_slots);
 
 		/* We will stick to that single UL slot, unreserve the others */
+		slotcount = 1;
 		reserved_ul_slots = ul_slots;
 
-		avail_count = pcu_bitcount(reserved_ul_slots);
+		update_slot_counters(ul_slots, reserved_ul_slots, &slotcount, &avail_count);
 	}
+
+	if (first_ts < 0)
+		return -EINVAL;
 
 	first_common_ts = ffs(dl_slots & ul_slots) - 1;
 
 	if (first_common_ts < 0) {
 		LOGP(DRLCMAC, LOGL_NOTICE, "No first common slots available\n");
-		return -EINVAL;
-	}
-	if (first_ts < 0) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "No first slot available\n");
 		return -EINVAL;
 	}
 
@@ -993,51 +1124,16 @@
 	 * may be modified from now on. */
 
 	/* Step 4: Update MS and TBF and really allocate the resources */
-
-	/* The reserved slots have changed, update the MS */
-	if (reserved_ul_slots != ms->reserved_ul_slots() ||
-		reserved_dl_slots != ms->reserved_dl_slots())
-	{
-		ms_->set_reserved_slots(trx,
-			reserved_ul_slots, reserved_dl_slots);
-
-		LOGP(DRLCMAC, LOGL_DEBUG,
-			"- Reserved DL/UL slots: (TS=0)\"%s\"(TS=7)\n",
-			set_flag_chars(set_flag_chars(set_flag_chars(slot_info,
-				dl_slots, 'D', '.'),
-				ul_slots, 'U'),
-				ul_slots & dl_slots, 'C'));
-	}
+	update_ms_reserved_slots(trx, ms_, reserved_ul_slots, reserved_dl_slots, ul_slots, dl_slots);
 
 	tbf_->trx = trx;
 	tbf_->first_common_ts = first_common_ts;
 	tbf_->first_ts = first_ts;
 
-	if (tbf->direction == GPRS_RLCMAC_DL_TBF) {
-		struct gprs_rlcmac_dl_tbf *dl_tbf = as_dl_tbf(tbf_);
-		for (ts = 0; ts < 8; ts++) {
-			if (!(dl_slots & (1 << ts)))
-				continue;
-
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning DL TS "
-				"%d\n", ts);
-			assign_dlink_tbf(&trx->pdch[ts], dl_tbf, tfi);
-		}
-	} else {
-		struct gprs_rlcmac_ul_tbf *ul_tbf = as_ul_tbf(tbf_);
-
-		for (ts = 0; ts < 8; ts++) {
-			if (!(ul_slots & (1 << ts)))
-				continue;
-
-			OSMO_ASSERT(usf[ts] >= 0);
-
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning UL TS "
-				"%d\n", ts);
-			assign_uplink_tbf_usf(&trx->pdch[ts], ul_tbf,
-				tfi, usf[ts]);
-		}
-	}
+	if (tbf->direction == GPRS_RLCMAC_DL_TBF)
+		assign_dl_tbf_slots(as_dl_tbf(tbf_), trx, dl_slots, tfi);
+	else
+		assign_ul_tbf_slots(as_ul_tbf(tbf_), trx, ul_slots, tfi, usf);
 
 	bts->bts->tbf_alloc_algo_b();
 
diff --git a/tests/alloc/AllocTest.cpp b/tests/alloc/AllocTest.cpp
index 271f966..13f3869 100644
--- a/tests/alloc/AllocTest.cpp
+++ b/tests/alloc/AllocTest.cpp
@@ -600,6 +600,10 @@
 			if (dl_tbf->pdch[i])
 				dl_slots |= 1 << i;
 
+		for (i = 0; ul_tbf && i < ARRAY_SIZE(ul_tbf->pdch); i += 1)
+			if (ul_tbf->pdch[i])
+				ul_slots |= 1 << i;
+
 		for (i = 0; trx && i < ARRAY_SIZE(trx->pdch); i += 1) {
 			struct gprs_rlcmac_pdch *pdch = &trx->pdch[i];
 

-- 
To view, visit https://gerrit.osmocom.org/3760
To unsubscribe, visit https://gerrit.osmocom.org/settings

Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I02da2b8ba8c9c8815dae0e39e1fed277ca0df171
Gerrit-PatchSet: 7
Gerrit-Project: osmo-pcu
Gerrit-Branch: master
Gerrit-Owner: Max <msuraev at sysmocom.de>
Gerrit-Reviewer: Holger Freyther <holger at freyther.de>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: Neels Hofmeyr <nhofmeyr at sysmocom.de>



More information about the gerrit-log mailing list