alloc: Replace Algorithm B implementation

The current implementation always starts the downlink slot allocation
with the first possible slot, depending on which channels are enabled
and which multislot class is offered by the MS. So in configurations
with many (>4) PDCH, some PDCH are not really used.

The new implementation introduced by this commit differs as follows:

 - The reservation mechanism provided by GprsMs is used to avoid
   incompatibilities is used in the same way like algo A does. This
   basically means, that the allocation is done once when the first
   TBF is requested and then used until all TBF have been released.

 - All combinations of Rx and Tx slots are checked for compatibility
   with the multiscot class. Basically the combination with the most
   usable PDCH and the least number of reservations is used.

 - Only one UL slots is provided.

 - Tta and Tra are checked.

Sponsored-by: On-Waves ehf

1 files changed, 374 insertions, 418 deletions

diff --git a/src/gprs_rlcmac_ts_alloc.cpp b/src/gprs_rlcmac_ts_alloc.cpp
index 8d4357e7..0169d49f 100644
--- a/src/gprs_rlcmac_ts_alloc.cpp
+++ b/src/gprs_rlcmac_ts_alloc.cpp
@@ -77,6 +77,42 @@ static const struct gprs_ms_multislot_class gprs_ms_multislot_class[32] = {
 /* N/A */	{ MS_NA,MS_NA,	MS_NA,	MS_NA,	MS_NA,	MS_NA,	MS_NA,	MS_NA },
 };
 
+static unsigned lsb(unsigned x)
+{
+	return x & -x;
+}
+
+static unsigned bitcount(unsigned x)
+{
+	unsigned count = 0;
+	for (count = 0; x; count += 1)
+		x &= x - 1;
+
+	return count;
+}
+
+static char *set_flag_chars(char *buf, uint8_t val, char set_char, char unset_char = 0)
+{
+	int i;
+
+	for (i = 0; i < 8; i += 1, val = val >> 1) {
+		if (val & 1)
+			buf[i] = set_char;
+		else if (unset_char)
+			buf[i] = unset_char;
+	}
+
+	return buf;
+}
+
+static bool test_and_set_bit(uint32_t *bits, size_t elem)
+{
+	bool was_set = bits[elem/32] & (1 << (elem % 32));
+	bits[elem/32] |= (1 << (elem % 32));
+
+	return was_set;
+}
+
 static inline int8_t find_free_usf(struct gprs_rlcmac_pdch *pdch)
 {
 	struct gprs_rlcmac_ul_tbf *tbf;
@@ -304,347 +340,249 @@ int alloc_algorithm_a(struct gprs_rlcmac_bts *bts,
 	return 0;
 }
 
-/*
- * Select a window of Rx slots if available.
- * The maximum allowed slots depend on RX or the window of available
- * slots. This must be done for uplink TBF also, because it is the basis
- * for calculating control slot and uplink slot(s).
- */
-static uint8_t select_dl_slots(struct gprs_rlcmac_trx *trx,
-			const int ms_type, const int ms_max_rxslots,
-			uint8_t *out_rx_win_min, uint8_t *out_rx_win_max)
-
+static int find_multi_slots(struct gprs_rlcmac_bts *bts,
+	struct gprs_rlcmac_trx *trx,
+	GprsMs *ms, uint8_t *ul_slots, uint8_t *dl_slots)
 {
-	uint8_t rx_window = 0;
-	int rx_window_size = 0;
-	int8_t last_tsc = -1; /* must be signed */
-	uint8_t rx_win_min = 0, rx_win_max = 0;
-
-	for (int ts_no = 0; ts_no < 8; ts_no++) {
-		struct gprs_rlcmac_pdch *pdch;
-		pdch = &trx->pdch[ts_no];
+	const struct gprs_ms_multislot_class *ms_class;
+	uint8_t Tx, Sum;	/* Maximum Number of Slots: RX, Tx, Sum Rx+Tx */
+	uint8_t Tta, Ttb, Tra, Trb;	/* Minimum Number of Slots */
+	uint8_t Type; /* Type of Mobile */
+	int rx_window, tx_window, pdch_slots;
+	static const char *digit[10] = { "0","1","2","3","4","5","6","7","8","9" };
+	char slot_info[9] = {0};
+	int max_capacity;
+	uint8_t max_ul_slots;
+	uint8_t max_dl_slots;
+	unsigned max_slots;
 
-		/* check if enabled */
-		if (!pdch->is_enabled()) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, because "
-				"not enabled\n", ts_no);
-			if (ms_type == 1 && rx_window)
-				goto inc_window;
-			continue;
-		}
-		/* check if TSC changes */
-		if (last_tsc < 0)
-			last_tsc = pdch->tsc;
-		else if (last_tsc != pdch->tsc) {
-			LOGP(DRLCMAC, LOGL_ERROR, "Skipping TS %d of TRX=%d, "
-				"because it has different TSC than lower TS "
-				"of TRX. In order to allow multislot, all "
-				"slots must be configured with the same "
-				"TSC!\n", ts_no, trx->trx_no);
-			if (ms_type == 1 && rx_window)
-				goto inc_window;
-			continue;
-		}
+	unsigned ul_ts, dl_ts;
+	unsigned num_tx;
 
-		if (!rx_window)
-			rx_win_min = ts_no;
+	uint32_t checked_tx[256/32] = {0};
 
-		rx_window |= (1 << ts_no);
-		LOGP(DRLCMAC, LOGL_DEBUG, "- Selected DL TS %d\n", ts_no);
+	if (ms->ms_class() >= 32) {
+		LOGP(DRLCMAC, LOGL_ERROR, "Multislot class %d out of range.\n",
+			ms->ms_class());
+		return -EINVAL;
+	}
 
-		/* range of window (required for Type 1) */
-		rx_win_max = ts_no;
+	if (ms->ms_class()) {
+		ms_class = &gprs_ms_multislot_class[ms->ms_class()];
+		LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm B) for "
+			"class %d\n", ms->ms_class());
+	} else {
+		ms_class = &gprs_ms_multislot_class[12];
+		LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm B) for "
+			"unknown class (assuming 12)\n");
+	}
 
-inc_window:
-		if (++rx_window_size == ms_max_rxslots) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because slots / "
-				"window reached maximum alowed Rx size\n");
-			break;
-		}
-		if (ms_type == 1 && rx_window_size == 5) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because slots / "
-				"window reached maximum supported Rx size of "
-				"this algorithm\n");
-			break;
-		}
+	if (ms_class->tx == MS_NA) {
+		LOGP(DRLCMAC, LOGL_NOTICE, "Multislot class %d not "
+			"applicable.\n", ms->ms_class());
+		return -EINVAL;
 	}
 
-	LOGP(DRLCMAC, LOGL_DEBUG, "- Selected slots for RX: "
-		"(TS=0)\"%c%c%c%c%c%c%c%c\"(TS=7)\n",
-		((rx_window & 0x01)) ? 'D' : '.',
-		((rx_window & 0x02)) ? 'D' : '.',
-		((rx_window & 0x04)) ? 'D' : '.',
-		((rx_window & 0x08)) ? 'D' : '.',
-		((rx_window & 0x10)) ? 'D' : '.',
-		((rx_window & 0x20)) ? 'D' : '.',
-		((rx_window & 0x40)) ? 'D' : '.',
-		((rx_window & 0x80)) ? 'D' : '.');
-
-	*out_rx_win_min = rx_win_min;
-	*out_rx_win_max = rx_win_max;
-	return rx_window;
-}
+	Tx = ms_class->tx;
+	Sum = ms_class->sum;
+	Tta = ms_class->ta;
+	Ttb = ms_class->tb;
+	Tra = ms_class->ra;
+	Trb = ms_class->rb;
+	Type = ms_class->type;
 
-static int reduce_rx_window(const int ms_type, const GprsMs *ms,
-				const int Tt, const int Tr,
-				int *rx_window,
-				uint8_t *rx_win_min, uint8_t *rx_win_max)
-{
-	gprs_rlcmac_ul_tbf *ul_tbf;
+	/* Tta and Ttb may depend on hopping or frequency change */
+	/* TODO: Set them to 1  */
+	if (Ttb == MS_A || Ttb == MS_B)
+		Ttb = 0;
+	if (Trb == MS_A || Trb == MS_C)
+		Trb = 0;
 
-	if (ms_type != 1)
-		return 0;
-	if (!ms)
-		return 0;
+	LOGP(DRLCMAC, LOGL_DEBUG, "- Rx=%d Tx=%d Sum Rx+Tx=%s  Tta=%s Ttb=%d "
+		" Tra=%d Trb=%d Type=%d\n", ms_class->rx, Tx,
+		(Sum == MS_NA) ? "N/A" : digit[Sum],
+		(Tta == MS_NA) ? "N/A" : digit[Tta], Ttb, Tra, Trb, Type);
 
-	ul_tbf = ms->ul_tbf();
+	max_slots = OSMO_MAX(ms_class->rx, ms_class->tx);
 
-	if (!ul_tbf)
-		return 0;
+	if (*dl_slots == 0)
+		*dl_slots = 0xff;
 
-	uint8_t collide = 0, ul_usage = 0;
+	if (*ul_slots == 0)
+		*ul_slots = 0xff;
 
-	/* calculate mask of colliding slots */
-	for (uint8_t ts_no = 0; ts_no < 8; ts_no++) {
-		int j;
-		if (!ul_tbf->pdch[ts_no])
-			continue;
+	pdch_slots = find_possible_pdchs(trx, max_slots, 0xff);
 
-		ul_usage |= (1 << ts_no);
-		/* mark bits from TS-t .. TS+r */
-		for (j = (ts_no - Tt) & 7; j != ((ts_no + Tr + 1) & 7); j = (j + 1) & 7)
-			collide |= (1 << j);
-	}
+	*dl_slots &= pdch_slots;
+	*ul_slots &= pdch_slots;
 
-	LOGP(DRLCMAC, LOGL_DEBUG, "- Not allowed slots due to existing "
-		"UL allocation: (TS=0)\"%c%c%c%c%c%c%c%c\"(TS=7) "
-		" D=downlink  x=not usable\n",
-		((ul_usage & 0x01)) ? 'D' : ((collide & 0x01))?'x':'.',
-		((ul_usage & 0x02)) ? 'D' : ((collide & 0x02))?'x':'.',
-		((ul_usage & 0x04)) ? 'D' : ((collide & 0x04))?'x':'.',
-		((ul_usage & 0x08)) ? 'D' : ((collide & 0x08))?'x':'.',
-		((ul_usage & 0x10)) ? 'D' : ((collide & 0x10))?'x':'.',
-		((ul_usage & 0x20)) ? 'D' : ((collide & 0x20))?'x':'.',
-		((ul_usage & 0x40)) ? 'D' : ((collide & 0x40))?'x':'.',
-		((ul_usage & 0x80)) ? 'D' : ((collide & 0x80))?'x':'.');
-
-	/*
-	 * Uplink/Downlink in GSM is shifted by three timeslots. Make
-	 * sure they don't collide.
-	 */
-	*rx_window &= ~(collide << 3);
-	*rx_window &= ~(collide >> 5);
-	LOGP(DRLCMAC, LOGL_DEBUG, "- Remaining slots for RX: "
-		"(TS=0)\"%c%c%c%c%c%c%c%c\"(TS=7)\n",
-		((*rx_window & 0x01)) ? 'D' : '.',
-		((*rx_window & 0x02)) ? 'D' : '.',
-		((*rx_window & 0x04)) ? 'D' : '.',
-		((*rx_window & 0x08)) ? 'D' : '.',
-		((*rx_window & 0x10)) ? 'D' : '.',
-		((*rx_window & 0x20)) ? 'D' : '.',
-		((*rx_window & 0x40)) ? 'D' : '.',
-		((*rx_window & 0x80)) ? 'D' : '.');
-
-	if (!*rx_window) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "No suitable downlink slots "
-			"available with current uplink assignment\n");
-		return -EBUSY;
-	}
+	LOGP(DRLCMAC, LOGL_DEBUG, "- Possible 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'));
 
-	return 0;
-}
+	/* Check for each UL (TX) slot */
 
-/* shrink range of rx_win_min and rx_win_max */
-static void shrink_rx_window(uint8_t *rx_win_min, uint8_t *rx_win_max, int rx_window)
-{
-	/* calculate new min/max */
-	for (uint8_t ts_no = *rx_win_min; ts_no <= *rx_win_max; ts_no++) {
-		if ((rx_window & (1 << ts_no)))
-			break;
-		*rx_win_min = ts_no + 1;
-		LOGP(DRLCMAC, LOGL_DEBUG, "- TS is unused, so "
-			"raising start of DL window to %d\n",
-			*rx_win_min);
-	}
-	for (uint8_t ts_no = *rx_win_max; ts_no >= *rx_win_min; ts_no--) {
-		if ((rx_window & (1 << ts_no)))
-			break;
-		*rx_win_max = ts_no - 1;
-		LOGP(DRLCMAC, LOGL_DEBUG, "- TS is unused, so "
-			"lowering end of DL window to %d\n",
-			*rx_win_max);
-	}
-}
+	max_capacity = -1;
+	max_ul_slots = 0;
+	max_dl_slots = 0;
 
-/*
- * reduce window, to allow at least one uplink TX slot
- * this is only required for Type 1
- */
-static uint8_t update_rx_win_max(const int ms_type, const int Tt,
-			const int Tr, uint8_t rx_win_min, uint8_t rx_win_max)
-{
-	if (ms_type != 1)
-		return rx_win_max;
+	/* Iterate through possible numbers of TX slots */
+	for (num_tx = 1; num_tx <= ms_class->tx; num_tx += 1) {
+		uint16_t tx_valid_win = (1 << num_tx) - 1;
 
-	if (rx_win_max - rx_win_min + 1 + Tt + 1 + Tr > 8) {
-		rx_win_max = rx_win_min + 7 - Tt - 1 - Tr;
-		LOGP(DRLCMAC, LOGL_DEBUG, "- Reduce RX window due to time "
-			"contraints to %d slots\n", rx_win_max - rx_win_min + 1);
-	}
+		uint8_t rx_mask[2]; /* 0: Tt*, 1: Tr* */
+		rx_mask[0] = (0x100 >> OSMO_MAX(Ttb, Tta)) - 1;
+		rx_mask[0] &= ~((1 << (Trb + num_tx)) - 1);
+		rx_mask[0] = rx_mask[0] << 3 | rx_mask[0] >> 5;
+		rx_mask[1] = (0x100 >> Ttb) - 1;
+		rx_mask[1] &= ~((1 << (OSMO_MAX(Trb, Tra) + num_tx)) - 1);
+		rx_mask[1] = rx_mask[1] << 3 | rx_mask[1] >> 5;
 
-	return rx_win_max;
-}
+	/* Rotate group of TX slots: UUU-----, -UUU----, ..., UU-----U */
+	for (ul_ts = 0; ul_ts < 8; ul_ts += 1, tx_valid_win <<= 1) {
+		unsigned tx_slot_count;
+		int max_rx;
+		uint16_t rx_valid_win;
+		uint32_t checked_rx[256/32] = {0};
 
-static void tx_win_from_rx(const int ms_type,
-				uint8_t rx_win_min, uint8_t rx_win_max,
-				int Tt, int Tr,
-				uint8_t *tx_win_min, uint8_t *tx_win_max,
-				uint8_t *tx_range)
-{
-	if (ms_type == 1) {
-		/* calculate TX window (shifted by 3 timeslots)
-		 * it uses the space between tx_win_max and tx_win_min */
-		*tx_win_min = (rx_win_max - 2 + Tt) & 7;
-		*tx_win_max = (rx_win_min + 4 - Tr) & 7;
-	} else {
-		/* TX and RX simultaniously */
-		*tx_win_min = rx_win_min;
-		*tx_win_max = 7;
-	}
+		/* Wrap valid window */
+		tx_valid_win = (tx_valid_win | tx_valid_win >> 8) & 0xff;
 
-	*tx_range = (*tx_win_max - *tx_win_min + 1) & 7;
-	/* if TX window fills complete range */
-	if (*tx_range == 0)
-		*tx_range = 8;
-	LOGP(DRLCMAC, LOGL_DEBUG, "- TX-Window is: %d..%d\n", *tx_win_min,
-		*tx_win_max);
-}
+		tx_window = tx_valid_win;
 
-/*
- * Select a window of Tx slots if available.
- * The maximum allowed slots depend on TX or the window of available
- * slots.
- */
-static int select_ul_slots(gprs_rlcmac_trx *trx,
-		const int ms_type, const int ms_max_txslots,
-		uint8_t tx_win_min, uint8_t tx_range,
-		int8_t *usf, int8_t *first_common_ts, uint8_t rx_window)
-{
-	int tsc = -1;
-	uint8_t tx_window = 0;
-	int i;
-	uint8_t ts_no;
+		/* Filter out unavailable slots */
+		tx_window &= *ul_slots;
 
-	for (ts_no = tx_win_min, i = 0; i < tx_range; ts_no = (ts_no + 1) & 7, i++) {
-		gprs_rlcmac_pdch *pdch = &trx->pdch[ts_no];
+		/* Avoid repeated TX combination check */
+		if (test_and_set_bit(checked_tx, tx_window))
+			continue;
 
-		/* check if enabled */
-		if (!pdch->is_enabled()) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, "
-				"because not enabled\n", ts_no);
-			if (ms_type == 1 && tx_window)
-				goto inc_window;
+		if (!tx_window)
 			continue;
-		}
-		/* check if used as downlink */
-		if (!(rx_window & (1 << ts_no))) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, "
-				"because not a downlink slot\n", ts_no);
-			if (ms_type == 1 && tx_window)
-				goto inc_window;
+
+		tx_slot_count = bitcount(tx_window);
+
+		max_rx = OSMO_MIN(ms_class->rx, ms_class->sum - num_tx);
+		rx_valid_win = (1 << max_rx) - 1;
+
+	/* Rotate group of RX slots: DDD-----, -DDD----, ..., DD-----D */
+	for (dl_ts = 0; dl_ts < 8; dl_ts += 1, rx_valid_win <<= 1) {
+		/* Wrap valid window */
+		rx_valid_win = (rx_valid_win | rx_valid_win >> 8) & 0xff;
+
+	/* Validate with both Tta/Ttb/Trb and Ttb/Tra/Trb */
+	for (unsigned m_idx = 0; m_idx < ARRAY_SIZE(rx_mask); m_idx += 1) {
+		unsigned common_slot_count;
+		unsigned req_common_slots;
+		unsigned rx_slot_count;
+		uint16_t rx_bad;
+		uint8_t rx_good;
+		unsigned ts;
+		int capacity;
+
+		/* Filter out bad slots */
+		rx_bad = (uint16_t)(0xff & ~rx_mask[m_idx]) << ul_ts;
+		rx_bad = (rx_bad | (rx_bad >> 8)) & 0xff;
+		rx_good = *dl_slots & ~rx_bad;
+
+		/* TODO: CHECK this calculation -> separate function for unit
+		 * testing */
+
+		rx_window = rx_good & rx_valid_win;
+
+		/* Avoid repeated RX combination check */
+		if (test_and_set_bit(checked_rx, rx_window))
 			continue;
-		}
-		/* check if TSC changes */
-		if (tsc < 0)
-			tsc = pdch->tsc;
-		else if (tsc != pdch->tsc) {
-			LOGP(DRLCMAC, LOGL_ERROR, "Skipping TS %d of "
-				"TRX=%d, because it has different TSC "
-				"than lower TS of TRX. In order to "
-				"allow multislot, all slots must be "
-				"configured with the same TSC!\n",
-				ts_no, trx->trx_no);
-			if (ms_type == 1)
-				goto inc_window;
+
+		rx_slot_count = bitcount(rx_window);
+
+#if 0
+		LOGP(DRLCMAC, LOGL_DEBUG, "n_tx=%d, n_rx=%d, "
+			"tx=%02x, rx=%02x, mask=%02x, bad=%02x, good=%02x, ul=%02x, dl=%02x\n",
+			tx_slot_count, rx_slot_count,
+			tx_window, rx_window, rx_mask[m_idx], rx_bad, rx_good, *ul_slots, *dl_slots);
+#endif
+
+		if (!rx_good) {
+			LOGP(DRLCMAC, LOGL_DEBUG,
+				"- Skipping DL/UL slots: (TS=0)\"%s\"(TS=7), "
+				"no DL slots available\n",
+				set_flag_chars(set_flag_chars(slot_info,
+						rx_bad, 'x', '.'),
+						tx_window, 'U'));
 			continue;
 		}
-		/* check for free usf */
-		usf[ts_no] = find_free_usf(pdch);
-		if (usf[ts_no] < 0) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, "
-			"because no USF available\n", ts_no);
-			if (ms_type == 1)
-				goto inc_window;
+
+		if (!rx_window)
 			continue;
-		}
 
-		if (!tx_window)
-			*first_common_ts = ts_no;
+		/* Check number of common slots according to TS 54.002, 6.4.2.2 */
+		common_slot_count = bitcount(tx_window & rx_window);
+		req_common_slots = OSMO_MIN(tx_slot_count, rx_slot_count);
+		if (ms_class->type == 1)
+			req_common_slots = OSMO_MIN(req_common_slots, 2);
+
+		if (req_common_slots != common_slot_count) {
+		LOGP(DRLCMAC, LOGL_DEBUG,
+			"- Skipping DL/UL slots: (TS=0)\"%s\"(TS=7), "
+			"invalid number of common TS: %d (expected %d)\n",
+			set_flag_chars(set_flag_chars(set_flag_chars(
+					slot_info,
+					rx_bad, 'x', '.'),
+					rx_window, 'D'),
+					tx_window, 'U'),
+			common_slot_count,
+			req_common_slots);
+			continue;
+		}
 
-		tx_window |= (1 << ts_no);
-		LOGP(DRLCMAC, LOGL_DEBUG, "- Selected UL TS %d\n", ts_no);
+		/* Compute capacity */
+		capacity = 0;
 
-inc_window:
-		if (1 && ms_type == 1) { /* FIXME: multislot UL assignment */
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because "
-				"1 slot assigned\n");
-			break;
-		}
-		if (i+1 == ms_max_txslots) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because "
-				"slots / window reached maximum "
-				"allowed Tx size\n");
-			break;
+		for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
+			int c;
+			struct gprs_rlcmac_pdch *pdch = &trx->pdch[ts];
+			if (rx_window & (1 << ts)) {
+				c = 32 - pdch->num_reserved(GPRS_RLCMAC_DL_TBF);
+				capacity += c;
+			}
+			if (tx_window & (1 << ts)) {
+				c = 32 - pdch->num_reserved(GPRS_RLCMAC_UL_TBF);
+				capacity += c;
+			}
 		}
-	}
 
-	LOGP(DRLCMAC, LOGL_DEBUG, "- Selected TX window: "
-		"(TS=0)\"%c%c%c%c%c%c%c%c\"(TS=7)\n",
-		((tx_window & 0x01)) ? 'U' : '.',
-		((tx_window & 0x02)) ? 'U' : '.',
-		((tx_window & 0x04)) ? 'U' : '.',
-		((tx_window & 0x08)) ? 'U' : '.',
-		((tx_window & 0x10)) ? 'U' : '.',
-		((tx_window & 0x20)) ? 'U' : '.',
-		((tx_window & 0x40)) ? 'U' : '.',
-		((tx_window & 0x80)) ? 'U' : '.');
-
-	if (!tx_window) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "No suitable uplink slots "
-			"available\n");
-		return -EBUSY;
-	}
+		LOGP(DRLCMAC, LOGL_DEBUG,
+			"- Considering DL/UL slots: (TS=0)\"%s\"(TS=7), "
+			"capacity = %d\n",
+			set_flag_chars(set_flag_chars(set_flag_chars(set_flag_chars(
+					slot_info,
+					rx_bad, 'x', '.'),
+					rx_window, 'D'),
+					tx_window, 'U'),
+					rx_window & tx_window, 'C'),
+			capacity);
+
+		if (capacity <= max_capacity)
+			continue;
 
-	return tx_window;
-}
+		max_capacity = capacity;
+		max_ul_slots = tx_window;
+		max_dl_slots = rx_window;
+	}}}}
 
-/*
- * Assign the first common ts, which is used for control or
- * single slot.
- */
-static int select_first_ts(gprs_rlcmac_trx *trx, uint8_t tx_win_min,
-	uint8_t tx_range, uint8_t rx_window)
-{
-	uint8_t ts_no;
-	int i;
-	for (ts_no = tx_win_min, i = 0; i < tx_range; ts_no = (ts_no + 1) & 7, i++) {
-		gprs_rlcmac_pdch *pdch = &trx->pdch[ts_no];
-		/* check if enabled */
-		if (!pdch->is_enabled()) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, "
-					"because not enabled\n", ts_no);
-			continue;
-		}
-		/* check if used as downlink */
-		if (!(rx_window & (1 << ts_no))) {
-			LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, "
-				"because not a downlink slot\n", ts_no);
-			continue;
-		}
-		return ts_no;
+	if (!max_ul_slots || !max_dl_slots) {
+		LOGP(DRLCMAC, LOGL_NOTICE,
+			"No valid UL/DL slot combination found\n");
+		return -EINVAL;
 	}
 
-	return -1;
+	*ul_slots = max_ul_slots;
+	*dl_slots = max_dl_slots;
+
+	return 0;
 }
 
 /* Slot Allocation: Algorithm B
@@ -657,153 +595,166 @@ int alloc_algorithm_b(struct gprs_rlcmac_bts *bts,
 	GprsMs *ms,
 	struct gprs_rlcmac_tbf *tbf, uint32_t cust, uint8_t single)
 {
-	const struct gprs_ms_multislot_class *ms_class;
-	uint8_t Tx, Sum;	/* Maximum Number of Slots: RX, Tx, Sum Rx+Tx */
-	uint8_t Tta, Ttb, Tra, Trb, Tt, Tr;	/* Minimum Number of Slots */
-	uint8_t Type; /* Type of Mobile */
-	int rx_window;
-	static const char *digit[10] = { "0","1","2","3","4","5","6","7","8","9" };
-	int8_t usf[8] = { -1, -1, -1, -1, -1, -1, -1, -1 }; /* must be signed */
-	int8_t first_common_ts = -1;
-	uint8_t ts;
+	uint8_t dl_slots = 0;
+	uint8_t ul_slots = 0;
+	int8_t first_common_ts;
 	uint8_t slotcount = 0;
+	uint8_t avail_count = 0;
+	char slot_info[9] = {0};
+	int ts;
+	int rc;
 
-
-	if (tbf->ms_class() >= 32) {
-		LOGP(DRLCMAC, LOGL_ERROR, "Multislot class %d out of range.\n",
-			tbf->ms_class());
+	if (!ms) {
+		LOGP(DRLCMAC, LOGL_ERROR, "MS not set\n");
 		return -EINVAL;
 	}
 
-	if (tbf->ms_class()) {
-		ms_class = &gprs_ms_multislot_class[tbf->ms_class()];
-		LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm B) for "
-			"class %d\n", tbf->ms_class());
-	} else {
-		ms_class = &gprs_ms_multislot_class[12];
-		LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm B) for "
-			"unknow class (assuming 12)\n");
-	}
+	dl_slots = ms->reserved_dl_slots();
+	ul_slots = ms->reserved_ul_slots();
 
-	if (ms_class->tx == MS_NA) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "Multislot class %d not "
-			"applicable.\n", tbf->ms_class());
-		return -EINVAL;
+	if (!dl_slots || !ul_slots) {
+		rc = find_multi_slots(bts, tbf->trx, ms, &ul_slots, &dl_slots);
+		if (rc < 0)
+			return rc;
+
+		ms->set_reserved_slots(tbf->trx, ul_slots, 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'));
 	}
 
-	Tx = ms_class->tx;
-	Sum = ms_class->sum;
-	Tta = ms_class->ta;
-	Ttb = ms_class->tb;
-	Tra = ms_class->ra;
-	Trb = ms_class->rb;
-	Type = ms_class->type;
+	first_common_ts = ms->first_common_ts();
 
-	/* Tta and Ttb may depend on hopping or frequency change */
-	if (Ttb == MS_A || Ttb == MS_B)
-		Ttb = 0;
-	if (Trb == MS_A || Trb == MS_C)
-		Trb = 0;
+	if (single) {
+		/* Make sure to consider the first common slot only */
+		ul_slots = dl_slots = dl_slots & ul_slots;
 
-	LOGP(DRLCMAC, LOGL_DEBUG, "- Rx=%d Tx=%d Sum Rx+Tx=%s  Tta=%s Ttb=%d "
-		" Tra=%d Trb=%d Type=%d\n", ms_class->rx, Tx,
-		(Sum == MS_NA) ? "N/A" : digit[Sum],
-		(Tta == MS_NA) ? "N/A" : digit[Tta], Ttb, Tra, Trb, Type);
+		ts = first_common_ts;
 
-	/* select the values for time contraints */
-	/* applicable to type 1 and type 2 */
-	Tt = Ttb;
-	Tr = Trb;
-
-	uint8_t rx_win_min, rx_win_max;
-	rx_window = select_dl_slots(tbf->trx, ms_class->type, ms_class->rx,
-				&rx_win_min, &rx_win_max);
-
-
-	/* reduce window, if existing uplink slots collide RX window */
-	int rc = reduce_rx_window(ms_class->type, ms, Tt, Tr,
-				&rx_window, &rx_win_min, &rx_win_max);
-	if (rc < 0)
-		return rc;
-	shrink_rx_window(&rx_win_min, &rx_win_max, rx_window);
-	rx_win_max = update_rx_win_max(ms_class->type, Tt, Tr,
-				rx_win_min, rx_win_max);
-	shrink_rx_window(&rx_win_min, &rx_win_max, rx_window);
-	LOGP(DRLCMAC, LOGL_DEBUG, "- RX-Window is: %d..%d\n", rx_win_min,
-		rx_win_max);
-
-	/* calculate TX window */
-	uint8_t tx_win_min, tx_win_max, tx_range;
-	tx_win_from_rx(ms_class->type, rx_win_min, rx_win_max, Tt, Tr,
-				&tx_win_min, &tx_win_max, &tx_range);
-
-	/* select UL slots but in both cases assign first_common_ts */
-	uint8_t tx_window = 0;
-	if (tbf->direction == GPRS_RLCMAC_UL_TBF) {
-		rc = select_ul_slots(tbf->trx, ms_class->type, ms_class->tx,
-					tx_win_min, tx_range, usf,
-					&first_common_ts, rx_window);
-		if (rc < 0)
-			return rc;
-		tx_window = rc;
-	} else {
-		first_common_ts = select_first_ts(tbf->trx, tx_win_min,
-					tx_range, rx_window);
+		if (ts < 0)
+			ts = find_least_busy_pdch(tbf->trx, tbf->direction,
+				dl_slots & ul_slots, NULL);
+		if (ts < 0)
+			ul_slots = dl_slots = lsb(dl_slots & ul_slots);
+		else
+			ul_slots = dl_slots = (dl_slots & ul_slots) & (1<<ts);
+	} else if (first_common_ts > 0) {
+		/* Make sure to keep the common TBF */
+		uint8_t disable_dl_slots;
+
+		/* Mark all slots below the common TBF, e.g. cTS=4 -> xxx----- */
+		disable_dl_slots = (1 << (first_common_ts - 1)) - 1;
+
+		/* Only disable common slots in that set */
+		disable_dl_slots &= (dl_slots & ul_slots);
+
+		/* Remove them from the uplink set */
+		ul_slots &= ~disable_dl_slots;
+
+		/* The disabled UL slots will not be used again for subsequent
+		 * TBF, do not reserve them anymore */
+		if (disable_dl_slots)
+			ms->set_reserved_slots(tbf->trx, ul_slots, dl_slots);
 	}
-	#warning "first_common_ts might be different if there was no free USF for the new uplink assignment"
 
-	if (first_common_ts < 0) {
-		LOGP(DRLCMAC, LOGL_NOTICE, "No first common slots available\n");
+	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) {
 		struct gprs_rlcmac_dl_tbf *dl_tbf = static_cast<gprs_rlcmac_dl_tbf *>(tbf);
+
+		LOGP(DRLCMAC, LOGL_DEBUG,
+			"- Selected DL slots: (TS=0)\"%s\"(TS=7)%s\n",
+			set_flag_chars(set_flag_chars(slot_info,
+					ms->reserved_dl_slots(), 'd', '.'),
+					dl_slots, 'D'),
+			single ? ", single" : "");
+
 		/* assign downlink */
-		if (rx_window == 0) {
+		if (dl_slots == 0) {
 			LOGP(DRLCMAC, LOGL_NOTICE, "No downlink slots "
 				"available\n");
 			return -EINVAL;
 		}
 		for (ts = 0; ts < 8; ts++) {
-			if ((rx_window & (1 << ts))) {
-				/* be sure to select a single downlink slots
-				 * that can be used for uplink, if multiple
-				 * slots are assigned later. */
-				if (single && first_common_ts != ts)
-					continue;
-				LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning DL TS "
-					"%d\n", ts);
-				assign_dlink_tbf(&tbf->trx->pdch[ts], dl_tbf);
-				slotcount++;
-				if (slotcount == 1)
-					dl_tbf->first_ts = ts;
-				if (single)
-					break;
-			}
+			if (!(dl_slots & (1 << ts)))
+				continue;
+
+			LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning DL TS "
+				"%d\n", ts);
+			assign_dlink_tbf(&tbf->trx->pdch[ts], dl_tbf);
+			slotcount++;
+			if (slotcount == 1)
+				dl_tbf->first_ts = ts;
 		}
+		avail_count = bitcount(ms->reserved_dl_slots());
+
 	} else {
 		struct gprs_rlcmac_ul_tbf *ul_tbf = static_cast<gprs_rlcmac_ul_tbf *>(tbf);
+		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(tbf->trx, GPRS_RLCMAC_UL_TBF,
+			ul_slots, &free_usf);
+
+		if (free_usf < 0) {
+			LOGP(DRLCMAC, LOGL_NOTICE, "No USF available\n");
+			return -EBUSY;
+		}
+		ul_slots = 1 << ts;
+
+		LOGP(DRLCMAC, LOGL_DEBUG,
+			"- Selected UL slots: (TS=0)\"%s\"(TS=7)%s\n",
+			set_flag_chars(set_flag_chars(slot_info,
+					ms->reserved_ul_slots(), 'u', '.'),
+					ul_slots, 'U'),
+			single ? ", single" : "");
+
+		assign_uplink_tbf_usf(&tbf->trx->pdch[ts], ul_tbf, free_usf);
+		slotcount++;
+		ul_tbf->first_ts = ts;
+
+		avail_count = bitcount(ms->reserved_ul_slots());
+#if 0 /* This code assigns multiple slots for UL (and wastes USFs that way) */
 		for (ts = 0; ts < 8; ts++) {
-			if ((tx_window & (1 << ts))) {
-				LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning UL TS "
-					"%d\n", ts);
-				assign_uplink_tbf_usf(&tbf->trx->pdch[ts], ul_tbf, usf[ts]);
-				slotcount++;
-				if (slotcount == 1)
-					ul_tbf->first_ts = ts;
-				if (single)
-					break;
+			if (!(ul_slots & (1 << ts)))
+				continue;
+
+			free_usf = find_free_usf(&tbf->trx->pdch[ts]);
+			if (free_usf < 0) {
+				LOGP(DRLCMAC, LOGL_DEBUG,
+					"- Skipping TS %d, because "
+					"no USF available\n", ts);
+				continue;
 			}
+
+			LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning UL TS "
+				"%d\n", ts);
+			assign_uplink_tbf_usf(&tbf->trx->pdch[ts], ul_tbf, free_usf);
+			slotcount++;
+			if (slotcount == 1)
+				ul_tbf->first_ts = ts;
 		}
+#endif
 	}
-	if (single && slotcount) {
-		uint8_t ts_count = 0;
-		for (ts = 0; ts < 8; ts++)
-			if ((tx_window & (1 << ts)))
-				ts_count++;
 
-		tbf->upgrade_to_multislot = (ts_count > 1);
+	if (single && slotcount) {
+		tbf->upgrade_to_multislot = (avail_count > slotcount);
 		LOGP(DRLCMAC, LOGL_INFO, "Using single slot at TS %d for %s\n",
 			tbf->first_ts,
 			(tbf->direction == GPRS_RLCMAC_DL_TBF) ? "DL" : "UL");
@@ -812,8 +763,13 @@ int alloc_algorithm_b(struct gprs_rlcmac_bts *bts,
 		LOGP(DRLCMAC, LOGL_INFO, "Using %d slots for %s\n", slotcount,
 			(tbf->direction == GPRS_RLCMAC_DL_TBF) ? "DL" : "UL");
 	}
-	if (slotcount == 0)
-		return -EBUSY;
+
+	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;
+	}
 
 	tbf->first_common_ts = first_common_ts;