/* gprs_rlcmac.cpp * * Copyright (C) 2012 Ivan Klyuchnikov * Copyright (C) 2012 Andreas Eversberg * Copyright (C) 2013 by Holger Hans Peter Freyther * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include #include #include #include /* 3GPP TS 05.02 Annex B.1 */ #define MS_NA 255 /* N/A */ #define MS_A 254 /* 1 with hopping, 0 without */ #define MS_B 253 /* 1 with hopping, 0 without (change Rx to Tx)*/ #define MS_C 252 /* 1 with hopping, 0 without (change Tx to Rx)*/ struct gprs_ms_multislot_class { uint8_t rx, tx, sum; /* Maximum Number of Slots: RX, Tx, Sum Rx+Tx */ uint8_t ta, tb, ra, rb; /* Minimum Number of Slots */ uint8_t type; /* Type of Mobile */ }; static const struct gprs_ms_multislot_class gprs_ms_multislot_class[32] = { /* M-S Class Rx Tx Sum Tta Ttb Tra Trb Type */ /* N/A */ { MS_NA,MS_NA, MS_NA, MS_NA, MS_NA, MS_NA, MS_NA, MS_NA }, /* 1 */ { 1, 1, 2, 3, 2, 4, 2, 1 }, /* 2 */ { 2, 1, 3, 3, 2, 3, 1, 1 }, /* 3 */ { 2, 2, 3, 3, 2, 3, 1, 1 }, /* 4 */ { 3, 1, 4, 3, 1, 3, 1, 1 }, /* 5 */ { 2, 2, 4, 3, 1, 3, 1, 1 }, /* 6 */ { 3, 2, 4, 3, 1, 3, 1, 1 }, /* 7 */ { 3, 3, 4, 3, 1, 3, 1, 1 }, /* 8 */ { 4, 1, 5, 3, 1, 2, 1, 1 }, /* 9 */ { 3, 2, 5, 3, 1, 2, 1, 1 }, /* 10 */ { 4, 2, 5, 3, 1, 2, 1, 1 }, /* 11 */ { 4, 3, 5, 3, 1, 2, 1, 1 }, /* 12 */ { 4, 4, 5, 2, 1, 2, 1, 1 }, /* 13 */ { 3, 3, MS_NA, MS_NA, MS_A, 3, MS_A, 2 }, /* 14 */ { 4, 4, MS_NA, MS_NA, MS_A, 3, MS_A, 2 }, /* 15 */ { 5, 5, MS_NA, MS_NA, MS_A, 3, MS_A, 2 }, /* 16 */ { 6, 6, MS_NA, MS_NA, MS_A, 2, MS_A, 2 }, /* 17 */ { 7, 7, MS_NA, MS_NA, MS_A, 1, 0, 2 }, /* 18 */ { 8, 8, MS_NA, MS_NA, 0, 0, 0, 2 }, /* 19 */ { 6, 2, MS_NA, 3, MS_B, 2, MS_C, 1 }, /* 20 */ { 6, 3, MS_NA, 3, MS_B, 2, MS_C, 1 }, /* 21 */ { 6, 4, MS_NA, 3, MS_B, 2, MS_C, 1 }, /* 22 */ { 6, 4, MS_NA, 2, MS_B, 2, MS_C, 1 }, /* 23 */ { 6, 6, MS_NA, 2, MS_B, 2, MS_C, 1 }, /* 24 */ { 8, 2, MS_NA, 3, MS_B, 2, MS_C, 1 }, /* 25 */ { 8, 3, MS_NA, 3, MS_B, 2, MS_C, 1 }, /* 26 */ { 8, 4, MS_NA, 3, MS_B, 2, MS_C, 1 }, /* 27 */ { 8, 4, MS_NA, 2, MS_B, 2, MS_C, 1 }, /* 28 */ { 8, 6, MS_NA, 2, MS_B, 2, MS_C, 1 }, /* 29 */ { 8, 8, MS_NA, 2, MS_B, 2, MS_C, 1 }, /* N/A */ { MS_NA,MS_NA, MS_NA, MS_NA, MS_NA, MS_NA, MS_NA, MS_NA }, /* N/A */ { MS_NA,MS_NA, MS_NA, MS_NA, MS_NA, MS_NA, MS_NA, MS_NA }, }; static inline int8_t find_free_usf(struct gprs_rlcmac_pdch *pdch, uint8_t ts) { struct gprs_rlcmac_tbf *tbf; uint8_t usf_map = 0; uint8_t tfi, usf; /* make map of used USF */ for (tfi = 0; tfi < 32; tfi++) { tbf = pdch->ul_tbf[tfi]; if (!tbf) continue; usf_map |= (1 << tbf->dir.ul.usf[ts]); } /* look for USF, don't use USF=7 */ for (usf = 0; usf < 7; usf++) { if (!(usf_map & (1 << usf))) return usf; } return -1; } static int find_enabled_pdch(struct gprs_rlcmac_trx *trx, const uint8_t start_ts) { int ts; for (ts = start_ts; ts < 8; ts++) { struct gprs_rlcmac_pdch *pdch; pdch = &trx->pdch[ts]; if (!pdch->is_enabled()) { LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, because " "not enabled\n", ts); continue; } return ts; } return 8; } static void assign_uplink_tbf_usf( struct gprs_rlcmac_pdch *pdch, int ts, struct gprs_rlcmac_tbf *tbf, int8_t usf) { tbf->trx->ul_tbf[tbf->tfi] = tbf; pdch->ul_tbf[tbf->tfi] = tbf; tbf->pdch[ts] = pdch; tbf->dir.ul.usf[ts] = usf; } static void assign_dlink_tbf( struct gprs_rlcmac_pdch *pdch, int ts, struct gprs_rlcmac_tbf *tbf) { tbf->trx->dl_tbf[tbf->tfi] = tbf; pdch->dl_tbf[tbf->tfi] = tbf; tbf->pdch[ts] = pdch; } /* Slot Allocation: Algorithm A * * Assign single slot for uplink and downlink */ int alloc_algorithm_a(struct gprs_rlcmac_bts *bts, struct gprs_rlcmac_tbf *old_tbf, struct gprs_rlcmac_tbf *tbf, uint32_t cust, uint8_t single) { struct gprs_rlcmac_pdch *pdch; uint8_t ts; LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm A) for class " "%d\n", tbf->ms_class); ts = find_enabled_pdch(tbf->trx, 0); if (ts == 8) return -EINVAL; pdch = &tbf->trx->pdch[ts]; tbf->tsc = pdch->tsc; if (tbf->direction == GPRS_RLCMAC_UL_TBF) { int8_t usf; /* must be signed */ /* if USF available */ usf = find_free_usf(pdch, ts); if (usf < 0) { LOGP(DRLCMAC, LOGL_NOTICE, "- Failed " "allocating TS=%d, no USF available\n", ts); return -EBUSY; } LOGP(DRLCMAC, LOGL_DEBUG, "- Assign uplink " "TS=%d USF=%d\n", ts, usf); assign_uplink_tbf_usf(pdch, ts, tbf, usf); } else { LOGP(DRLCMAC, LOGL_DEBUG, "- Assign downlink TS=%d\n", ts); assign_dlink_tbf(pdch, ts, tbf); } /* the only one TS is the common TS */ tbf->first_ts = tbf->first_common_ts = ts; return 0; } /* Slot Allocation: Algorithm B * * Assign as many downlink slots as possible. * Assign one uplink slot. (With free USF) * */ int alloc_algorithm_b(struct gprs_rlcmac_bts *bts, struct gprs_rlcmac_tbf *old_tbf, struct gprs_rlcmac_tbf *tbf, uint32_t cust, uint8_t single) { struct gprs_rlcmac_pdch *pdch; const struct gprs_ms_multislot_class *ms_class; uint8_t Rx, 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 */ uint8_t rx_win_min = 0, rx_win_max = 7; uint8_t tx_win_min, tx_win_max, tx_range; uint8_t rx_window = 0, tx_window = 0; 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 tsc = -1; /* must be signed */ int8_t first_common_ts = -1; uint8_t i, ts; uint8_t slotcount = 0; if (tbf->ms_class >= 32) { LOGP(DRLCMAC, LOGL_ERROR, "Multislot class %d out of range.\n", tbf->ms_class); 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"); } if (ms_class->tx == MS_NA) { LOGP(DRLCMAC, LOGL_NOTICE, "Multislot class %d not " "applicable.\n", tbf->ms_class); return -EINVAL; } Rx = ms_class->rx; 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; /* Tta and Ttb may depend on hopping or frequency change */ if (Ttb == MS_A) Ttb = 0; if (Trb == MS_A) Trb = 0; if (Ttb == MS_B) Ttb = 0; if (Trb == MS_C) Trb = 0; LOGP(DRLCMAC, LOGL_DEBUG, "- Rx=%d Tx=%d Sum Rx+Tx=%s Tta=%s Ttb=%d " " Tra=%d Trb=%d Type=%d\n", Rx, Tx, (Sum == MS_NA) ? "N/A" : digit[Sum], (Tta == MS_NA) ? "N/A" : digit[Tta], Ttb, Tra, Trb, Type); /* select the values for time contraints */ /* applicable to type 1 and type 2 */ Tt = Ttb; Tr = Trb; /* 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). */ for (ts = 0, i = 0; ts < 8; ts++) { pdch = &tbf->trx->pdch[ts]; /* check if enabled */ if (!pdch->is_enabled()) { LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, because " "not enabled\n", ts); /* increase window for Type 1 */ if (Type == 1 && rx_window) i++; continue; } /* check if TSC changes */ if (tsc < 0) tbf->tsc = 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, tbf->trx_no); /* increase window for Type 1 */ if (Type == 1 && rx_window) i++; continue; } if (!rx_window) rx_win_min = ts; rx_window |= (1 << ts); LOGP(DRLCMAC, LOGL_DEBUG, "- Selected DL TS %d\n", ts); /* range of window (required for Type 1) */ rx_win_max = ts; if (++i == Rx) { LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because slots / " "window reached maximum alowed Rx size\n"); break; } } 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' : '.'); /* reduce window, if existing uplink slots collide RX window */ if (Type == 1 && old_tbf && old_tbf->direction == GPRS_RLCMAC_UL_TBF) { uint8_t collide = 0, ul_usage = 0; int j; /* calculate mask of colliding slots */ for (ts = 0; ts < 8; ts++) { if (old_tbf->pdch[ts]) { ul_usage |= (1 << ts); /* mark bits from TS-t .. TS+r */ for (j = ts - Tt; j != ((ts + Tr + 1) & 7); j = (j + 1) & 7) collide |= (1 << j); } } 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':'.'); /* apply mask to reduce tx_window (shifted by 3 slots) */ 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; } /* calculate new min/max */ for (ts = rx_win_min; ts <= rx_win_max; ts++) { if ((rx_window & (1 << ts))) break; rx_win_min = ts + 1; LOGP(DRLCMAC, LOGL_DEBUG, "- TS has been deleted, so " "raising start of DL window to %d\n", rx_win_min); } for (ts = rx_win_max; ts >= rx_win_min; ts--) { if ((rx_window & (1 << ts))) break; rx_win_max = ts - 1; LOGP(DRLCMAC, LOGL_DEBUG, "- TS has been deleted, so " "lowering end of DL window to %d\n", rx_win_max); } } /* reduce window, to allow at least one uplink TX slot * this is only required for Type 1 */ if (Type == 1 && 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); } LOGP(DRLCMAC, LOGL_DEBUG, "- RX-Window is: %d..%d\n", rx_win_min, rx_win_max); /* calculate TX window */ if (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; /* calculate the TX window size (might be larger than Tx) */ tx_range = (tx_win_max - tx_win_min + 1) & 7; } else { /* TX and RX simultaniously */ tx_win_min = rx_win_min; tx_win_max = 7; /* TX window size (might be larger than Tx) */ tx_range = tx_win_max - tx_win_min + 1; } LOGP(DRLCMAC, LOGL_DEBUG, "- TX-Window is: %d..%d\n", tx_win_min, tx_win_max); /* select a window of Tx slots if available * The maximum allowed slots depend on TX or the window of available * slots. * * also assign the first common ts, which is used for control or single * slot. */ if (tbf->direction == GPRS_RLCMAC_UL_TBF) { for (ts = tx_win_min, i = 0; i < tx_range; ts = (ts + 1) & 7) { pdch = &tbf->trx->pdch[ts]; /* check if enabled */ if (!pdch->is_enabled()) { LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, " "because not enabled\n", ts); continue; } /* check if TSC changes */ if (tsc < 0) tbf->tsc = 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, tbf->trx_no); /* increase window for Type 1 */ if (Type == 1) i++; continue; } /* check for free usf */ usf[ts] = find_free_usf(pdch, ts); if (usf[ts] < 0) { LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, " "because no USF available\n", ts); /* increase window for Type 1 */ if (Type == 1) i++; continue; } if (!tx_window) first_common_ts = ts; tx_window |= (1 << ts); LOGP(DRLCMAC, LOGL_DEBUG, "- Selected UL TS %d\n", ts); if (1 && Type == 1) { /* FIXME: multislot UL assignment */ LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because " "1 slot assigned\n"); break; } if (++i == Tx) { LOGP(DRLCMAC, LOGL_DEBUG, "- Done, because " "slots / window reached maximum " "allowed Tx size\n"); break; } } 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; } } else { /* assign the first common ts, which is used for control or * single slot. */ for (ts = tx_win_min, i = 0; i < tx_range; ts = (ts + 1) & 7) { pdch = &tbf->trx->pdch[ts]; /* check if enabled */ if (!pdch->is_enabled()) { LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, " "because not enabled\n", ts); continue; } first_common_ts = ts; break; } } if (first_common_ts < 0) { LOGP(DRLCMAC, LOGL_NOTICE, "No first common slots available\n"); return -EINVAL; } if (tbf->direction == GPRS_RLCMAC_DL_TBF) { /* assign downlink */ if (rx_window == 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); pdch = &tbf->trx->pdch[ts]; assign_dlink_tbf(pdch, ts, tbf); slotcount++; if (slotcount == 1) tbf->first_ts = ts; if (single) break; } } } else { /* assign uplink */ if (tx_window == 0) { LOGP(DRLCMAC, LOGL_NOTICE, "No uplink slots " "available\n"); return -EINVAL; } for (ts = 0; ts < 8; ts++) { if ((tx_window & (1 << ts))) { LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning UL TS " "%d\n", ts); pdch = &tbf->trx->pdch[ts]; assign_uplink_tbf_usf(pdch, ts, tbf, usf[ts]); slotcount++; if (slotcount == 1) tbf->first_ts = ts; if (single) break; } } } if (single && 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"); } else { LOGP(DRLCMAC, LOGL_INFO, "Using %d slots for %s\n", slotcount, (tbf->direction == GPRS_RLCMAC_DL_TBF) ? "DL" : "UL"); } if (slotcount == 0) return -EBUSY; tbf->first_common_ts = first_common_ts; return 0; }