blob: a243d21658050fbf4507b56e6879b1fa688a5738 [file] [log] [blame]
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +02001/* gprs_rlcmac.cpp
2 *
3 * Copyright (C) 2012 Ivan Klyuchnikov
4 * Copyright (C) 2012 Andreas Eversberg <jolly@eversberg.eu>
5 * Copyright (C) 2013 by Holger Hans Peter Freyther
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 */
21
22#include <gprs_rlcmac.h>
23#include <gprs_debug.h>
Holger Hans Peter Freyther34bd8bd2013-10-19 21:10:38 +020024#include <bts.h>
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +020025#include <tbf.h>
Pau Espin Pedrol9d1cdb12019-09-25 17:47:02 +020026#include <tbf_ul.h>
Max6dc90b82018-02-19 17:17:28 +010027#include <pdch.h>
Jacob Erlbecke2e004e2015-06-18 17:16:26 +020028#include <gprs_ms.h>
Jacob Erlbeck8cba7e92016-01-19 15:48:03 +010029#include <pcu_utils.h>
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +020030
31#include <errno.h>
Jacob Erlbeckec478752015-06-19 16:35:38 +020032#include <values.h>
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +020033
Max842d7812017-11-01 18:11:24 +010034extern "C" {
35#include "mslot_class.h"
Max1187a772018-01-26 13:31:42 +010036#include <osmocom/core/linuxlist.h>
37#include <osmocom/core/logging.h>
38#include <osmocom/core/utils.h>
Max842d7812017-11-01 18:11:24 +010039}
40
Jacob Erlbeck77da3552015-07-16 18:33:46 +020041/* Consider a PDCH as idle if has at most this number of TBFs assigned to it */
42#define PDCH_IDLE_TBF_THRESH 1
43
Max0e6ac792018-02-19 18:43:01 +010044#define LOGPSL(tbf, level, fmt, args...) LOGP(DRLCMAC, level, "[%s] " fmt, \
45 (tbf->direction == GPRS_RLCMAC_DL_TBF) ? "DL" : "UL", ## args)
46
47#define LOGPAL(tbf, kind, single, trx_n, level, fmt, args...) LOGPSL(tbf, level, \
48 "algo %s <%s> (suggested TRX: %d): " fmt, \
49 kind, single ? "single" : "multi", trx_n, ## args)
50
Jacob Erlbeckea65c722015-06-22 16:14:23 +020051static char *set_flag_chars(char *buf, uint8_t val, char set_char, char unset_char = 0)
52{
53 int i;
54
55 for (i = 0; i < 8; i += 1, val = val >> 1) {
56 if (val & 1)
57 buf[i] = set_char;
58 else if (unset_char)
59 buf[i] = unset_char;
60 }
61
62 return buf;
63}
64
Max731e2bb2018-02-05 16:15:30 +010065static uint8_t find_possible_pdchs(const struct gprs_rlcmac_trx *trx, uint8_t max_slots, uint8_t mask,
66 const char *mask_reason = NULL)
Holger Hans Peter Freytherb0a00752013-09-29 08:18:17 +020067{
Jacob Erlbeckec478752015-06-19 16:35:38 +020068 unsigned ts;
Max731e2bb2018-02-05 16:15:30 +010069 uint8_t valid_ts_set = 0;
Jacob Erlbeck83426b22015-06-30 09:44:05 +020070 int8_t last_tsc = -1; /* must be signed */
Jacob Erlbeckec478752015-06-19 16:35:38 +020071
72 for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
Maxa76a7d02018-01-26 11:09:16 +010073 const struct gprs_rlcmac_pdch *pdch;
Holger Hans Peter Freytherb0a00752013-09-29 08:18:17 +020074
75 pdch = &trx->pdch[ts];
Holger Hans Peter Freyther17b0d832013-10-19 17:37:48 +020076 if (!pdch->is_enabled()) {
Holger Hans Peter Freytherb0a00752013-09-29 08:18:17 +020077 LOGP(DRLCMAC, LOGL_DEBUG, "- Skipping TS %d, because "
78 "not enabled\n", ts);
79 continue;
80 }
Jacob Erlbeckec478752015-06-19 16:35:38 +020081
82 if (((1 << ts) & mask) == 0) {
83 if (mask_reason)
84 LOGP(DRLCMAC, LOGL_DEBUG,
85 "- Skipping TS %d, because %s\n",
86 ts, mask_reason);
87 continue;
88 }
89
Jacob Erlbeck83426b22015-06-30 09:44:05 +020090 if (max_slots > 1) {
91 /* check if TSC changes, see TS 45.002, 6.4.2 */
92 if (last_tsc < 0)
93 last_tsc = pdch->tsc;
94 else if (last_tsc != pdch->tsc) {
95 LOGP(DRLCMAC, LOGL_ERROR,
96 "Skipping TS %d of TRX=%d, because it "
97 "has different TSC than lower TS of TRX. "
98 "In order to allow multislot, all "
99 "slots must be configured with the same "
100 "TSC!\n", ts, trx->trx_no);
101 continue;
102 }
103 }
104
Jacob Erlbeckec478752015-06-19 16:35:38 +0200105 valid_ts_set |= 1 << ts;
Holger Hans Peter Freytherb0a00752013-09-29 08:18:17 +0200106 }
107
Jacob Erlbeckec478752015-06-19 16:35:38 +0200108 return valid_ts_set;
109}
110
Maxa76a7d02018-01-26 11:09:16 +0100111static int compute_usage_by_num_tbfs(const struct gprs_rlcmac_pdch *pdch, enum gprs_rlcmac_tbf_direction dir)
Jacob Erlbeckc135b872015-07-09 13:44:18 +0200112{
113 return pdch->num_tbfs(dir);
114}
115
Maxa76a7d02018-01-26 11:09:16 +0100116static int compute_usage_by_reservation(const struct gprs_rlcmac_pdch *pdch, enum gprs_rlcmac_tbf_direction)
Jacob Erlbeckc135b872015-07-09 13:44:18 +0200117{
118 return
119 pdch->num_reserved(GPRS_RLCMAC_DL_TBF) +
120 pdch->num_reserved(GPRS_RLCMAC_UL_TBF);
121}
122
Maxa76a7d02018-01-26 11:09:16 +0100123static int compute_usage_for_algo_a(const struct gprs_rlcmac_pdch *pdch, enum gprs_rlcmac_tbf_direction dir)
Jacob Erlbeck7af53e62015-07-16 15:04:07 +0200124{
125 int usage =
126 pdch->num_tbfs(GPRS_RLCMAC_DL_TBF) +
127 pdch->num_tbfs(GPRS_RLCMAC_UL_TBF) +
128 compute_usage_by_reservation(pdch, dir);
129
Maxd000d802017-09-20 17:55:28 +0200130 if (pdch->assigned_tfi(reverse(dir)) == NO_FREE_TFI)
Jacob Erlbeck7af53e62015-07-16 15:04:07 +0200131 /* No TFI in the opposite direction, avoid it */
132 usage += 32;
133
134 return usage;
135
136}
137
Maxa76a7d02018-01-26 11:09:16 +0100138/*! Return the TS which corresponds to least busy PDCH
139 *
140 * \param[in] trx Pointer to TRX object
141 * \param[in] dir TBF direction
142 * \param[in] mask set of available timeslots
143 * \param[in] fn Function pointer to function which computes number of associated TBFs
144 * \param[out] free_tfi Free TFI
145 * \param[out] free_usf Free USF
146 * \returns TS number or -1 if unable to find
147 */
148static int find_least_busy_pdch(const struct gprs_rlcmac_trx *trx, enum gprs_rlcmac_tbf_direction dir, uint8_t mask,
149 int (*fn)(const struct gprs_rlcmac_pdch *, enum gprs_rlcmac_tbf_direction dir),
Pau Espin Pedrol1f8e2292021-02-19 16:49:16 +0100150 int *free_tfi = NULL, int *free_usf = NULL)
Jacob Erlbeckec478752015-06-19 16:35:38 +0200151{
152 unsigned ts;
153 int min_used = INT_MAX;
154 int min_ts = -1;
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200155 int min_tfi = -1;
Jacob Erlbeckec478752015-06-19 16:35:38 +0200156 int min_usf = -1;
157
158 for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
Maxa76a7d02018-01-26 11:09:16 +0100159 const struct gprs_rlcmac_pdch *pdch = &trx->pdch[ts];
Jacob Erlbeckec478752015-06-19 16:35:38 +0200160 int num_tbfs;
161 int usf = -1; /* must be signed */
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200162 int tfi = -1;
Jacob Erlbeckec478752015-06-19 16:35:38 +0200163
164 if (((1 << ts) & mask) == 0)
165 continue;
166
Jacob Erlbeckc135b872015-07-09 13:44:18 +0200167 num_tbfs = fn(pdch, dir);
Jacob Erlbeckefe62a72015-07-02 15:48:25 +0200168
169 if (num_tbfs < min_used) {
170 /* We have found a candidate */
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200171 /* Make sure that a TFI is available */
172 if (free_tfi) {
Maxc5407c72018-02-05 16:11:36 +0100173 tfi = find_free_tfi(pdch->assigned_tfi(dir));
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200174 if (tfi < 0) {
175 LOGP(DRLCMAC, LOGL_DEBUG,
176 "- Skipping TS %d, because "
177 "no TFI available\n", ts);
178 continue;
179 }
180 }
Jacob Erlbeckefe62a72015-07-02 15:48:25 +0200181 /* Make sure that an USF is available */
182 if (dir == GPRS_RLCMAC_UL_TBF) {
Maxadca67b2018-01-31 15:22:36 +0100183 usf = find_free_usf(pdch->assigned_usf());
Jacob Erlbeckefe62a72015-07-02 15:48:25 +0200184 if (usf < 0) {
185 LOGP(DRLCMAC, LOGL_DEBUG,
186 "- Skipping TS %d, because "
187 "no USF available\n", ts);
188 continue;
189 }
190 }
191 if (min_ts >= 0)
192 LOGP(DRLCMAC, LOGL_DEBUG,
193 "- Skipping TS %d, because "
194 "num TBFs %d > %d\n",
195 min_ts, min_used, num_tbfs);
196 min_used = num_tbfs;
197 min_ts = ts;
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200198 min_tfi = tfi;
Jacob Erlbeckefe62a72015-07-02 15:48:25 +0200199 min_usf = usf;
200 } else {
201 LOGP(DRLCMAC, LOGL_DEBUG,
202 "- Skipping TS %d, because "
203 "num TBFs %d >= %d\n",
204 ts, num_tbfs, min_used);
205 }
206 }
207
208 if (min_ts < 0)
209 return -1;
210
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200211 if (free_tfi)
212 *free_tfi = min_tfi;
Jacob Erlbeckefe62a72015-07-02 15:48:25 +0200213 if (free_usf)
214 *free_usf = min_usf;
215
216 return min_ts;
217}
218
Jacob Erlbeckccc34e42015-06-29 13:45:05 +0200219static void attach_tbf_to_pdch(struct gprs_rlcmac_pdch *pdch,
220 struct gprs_rlcmac_tbf *tbf)
221{
222 if (tbf->pdch[pdch->ts_no])
223 tbf->pdch[pdch->ts_no]->detach_tbf(tbf);
224
225 tbf->pdch[pdch->ts_no] = pdch;
226 pdch->attach_tbf(tbf);
227}
228
Maxa76a7d02018-01-26 11:09:16 +0100229static void assign_uplink_tbf_usf(struct gprs_rlcmac_pdch *pdch, struct gprs_rlcmac_ul_tbf *tbf, uint8_t tfi, int8_t usf)
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200230{
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200231 tbf->m_tfi = tfi;
Daniel Willmann7e994e32014-08-07 15:49:21 +0200232 tbf->m_usf[pdch->ts_no] = usf;
Jacob Erlbeckccc34e42015-06-29 13:45:05 +0200233 attach_tbf_to_pdch(pdch, tbf);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200234}
235
Maxa76a7d02018-01-26 11:09:16 +0100236static void assign_dlink_tbf(struct gprs_rlcmac_pdch *pdch, struct gprs_rlcmac_dl_tbf *tbf, uint8_t tfi)
Holger Hans Peter Freyther8481a052013-09-29 08:08:28 +0200237{
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200238 tbf->m_tfi = tfi;
Jacob Erlbeckccc34e42015-06-29 13:45:05 +0200239 attach_tbf_to_pdch(pdch, tbf);
Holger Hans Peter Freyther8481a052013-09-29 08:08:28 +0200240}
241
Pau Espin Pedrol0ece97d2021-01-18 12:53:54 +0100242static int find_trx(const struct gprs_rlcmac_bts *bts, const GprsMs *ms, int8_t use_trx)
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200243{
244 unsigned trx_no;
245 unsigned ts;
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200246
247 /* We must use the TRX currently actively used by an MS */
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100248 if (ms && ms_current_trx(ms))
249 return ms_current_trx(ms)->trx_no;
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200250
251 if (use_trx >= 0 && use_trx < 8)
252 return use_trx;
253
254 /* Find the first TRX that has a PDCH with a free UL and DL TFI */
Pau Espin Pedrol0ece97d2021-01-18 12:53:54 +0100255 for (trx_no = 0; trx_no < ARRAY_SIZE(bts->trx); trx_no += 1) {
256 const struct gprs_rlcmac_trx *trx = &bts->trx[trx_no];
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200257 for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
Maxa76a7d02018-01-26 11:09:16 +0100258 const struct gprs_rlcmac_pdch *pdch = &trx->pdch[ts];
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200259 if (!pdch->is_enabled())
260 continue;
261
Maxd000d802017-09-20 17:55:28 +0200262 if (pdch->assigned_tfi(GPRS_RLCMAC_UL_TBF) == NO_FREE_TFI)
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200263 continue;
264
Maxd000d802017-09-20 17:55:28 +0200265 if (pdch->assigned_tfi(GPRS_RLCMAC_DL_TBF) == NO_FREE_TFI)
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200266 continue;
267
268 return trx_no;
269 }
270 }
271
272 return -EBUSY;
273}
274
Pau Espin Pedrol0ece97d2021-01-18 12:53:54 +0100275static bool idle_pdch_avail(const struct gprs_rlcmac_bts *bts)
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200276{
277 unsigned trx_no;
278 unsigned ts;
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200279
280 /* Find the first PDCH with an unused DL TS */
Pau Espin Pedrol0ece97d2021-01-18 12:53:54 +0100281 for (trx_no = 0; trx_no < ARRAY_SIZE(bts->trx); trx_no += 1) {
282 const struct gprs_rlcmac_trx *trx = &bts->trx[trx_no];
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200283 for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
Maxa76a7d02018-01-26 11:09:16 +0100284 const struct gprs_rlcmac_pdch *pdch = &trx->pdch[ts];
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200285 if (!pdch->is_enabled())
286 continue;
287
288 if (pdch->num_tbfs(GPRS_RLCMAC_DL_TBF) > PDCH_IDLE_TBF_THRESH)
289 continue;
290
Maxa76a7d02018-01-26 11:09:16 +0100291 return true;
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200292 }
293 }
294
Maxa76a7d02018-01-26 11:09:16 +0100295 return false;
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200296}
297
Maxa76a7d02018-01-26 11:09:16 +0100298/*! Return free TFI
299 *
300 * \param[in] bts Pointer to BTS struct
Maxa76a7d02018-01-26 11:09:16 +0100301 * \param[in] ms Pointer to MS object
302 * \param[in] dir DL or UL direction
303 * \param[in] use_trx which TRX to use or -1 if it should be selected based on what MS uses
304 * \param[out] trx_no_ TRX number on which TFI was found
305 * \returns negative error code or 0 on success
306 */
Pau Espin Pedrold9066272021-11-09 16:52:31 +0100307static int tfi_find_free(const struct gprs_rlcmac_bts *bts, const GprsMs *ms,
Maxa76a7d02018-01-26 11:09:16 +0100308 enum gprs_rlcmac_tbf_direction dir, int8_t use_trx, uint8_t *trx_no_)
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200309{
Pau Espin Pedrold9066272021-11-09 16:52:31 +0100310 const struct gprs_rlcmac_trx *trx;
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200311 int tfi;
312 uint8_t trx_no;
313
Pau Espin Pedrold9066272021-11-09 16:52:31 +0100314 /* If MS is already doing stuff on a TRX, set use_trx to it: */
315 if ((trx = ms_current_trx(ms))) {
Max7e4921d2017-09-28 16:41:24 +0200316 if (use_trx >= 0 && use_trx != trx->trx_no) {
317 LOGP(DRLCMAC, LOGL_ERROR, "- Requested incompatible TRX %d (current is %d)\n",
318 use_trx, trx->trx_no);
319 return -EINVAL;
320 }
321 use_trx = trx->trx_no;
322 }
323
Pau Espin Pedrol2182e622021-01-14 16:48:38 +0100324 tfi = bts_tfi_find_free(bts, dir, &trx_no, use_trx);
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200325 if (tfi < 0)
326 return -EBUSY;
327
328 if (trx_no_)
329 *trx_no_ = trx_no;
330
331 return tfi;
332}
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200333
Maxe9fe0e32017-09-28 15:56:05 +0200334/*! Slot Allocation: Algorithm A
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200335 *
336 * Assign single slot for uplink and downlink
Maxe9fe0e32017-09-28 15:56:05 +0200337 *
338 * \param[in,out] bts Pointer to BTS struct
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200339 * \param[in,out] tbf Pointer to TBF struct
Maxe9fe0e32017-09-28 15:56:05 +0200340 * \param[in] single flag indicating if we should force single-slot allocation
341 * \param[in] use_trx which TRX to use or -1 if it should be selected during allocation
342 * \returns negative error code or 0 on success
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200343 */
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200344int alloc_algorithm_a(struct gprs_rlcmac_bts *bts, struct gprs_rlcmac_tbf *tbf, bool single,
Maxe9fe0e32017-09-28 15:56:05 +0200345 int8_t use_trx)
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200346{
347 struct gprs_rlcmac_pdch *pdch;
Jacob Erlbeckec478752015-06-19 16:35:38 +0200348 int ts = -1;
Jacob Erlbeck5cd496d2015-06-30 10:24:37 +0200349 uint8_t ul_slots, dl_slots;
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200350 int trx_no;
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200351 int tfi = -1;
Jacob Erlbeckec478752015-06-19 16:35:38 +0200352 int usf = -1;
Max731e2bb2018-02-05 16:15:30 +0100353 uint8_t mask = 0xff;
Jacob Erlbeckec478752015-06-19 16:35:38 +0200354 const char *mask_reason = NULL;
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200355 struct GprsMs *ms = tbf->ms();
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100356 gprs_rlcmac_trx *trx = ms_current_trx(ms);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200357
Pau Espin Pedrol8353d972020-10-23 17:07:10 +0200358 LOGPAL(tbf, "A", single, use_trx, LOGL_DEBUG, "Alloc start\n");
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200359
Maxa76a7d02018-01-26 11:09:16 +0100360 trx_no = find_trx(bts, ms, use_trx);
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200361 if (trx_no < 0) {
Pau Espin Pedrola611b4f2020-10-23 17:11:00 +0200362 LOGPAL(tbf, "A", single, use_trx, LOGL_NOTICE,
Max0e6ac792018-02-19 18:43:01 +0100363 "failed to find a usable TRX (TFI exhausted)\n");
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200364 return trx_no;
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200365 }
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200366 if (!trx)
367 trx = &bts->trx[trx_no];
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200368
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100369 dl_slots = ms_reserved_dl_slots(ms);
370 ul_slots = ms_reserved_ul_slots(ms);
Jacob Erlbeck5cd496d2015-06-30 10:24:37 +0200371
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100372 ts = ms_first_common_ts(ms);
Jacob Erlbeck5cd496d2015-06-30 10:24:37 +0200373
374 if (ts >= 0) {
Jacob Erlbeckec478752015-06-19 16:35:38 +0200375 mask_reason = "need to reuse TS";
Jacob Erlbeckec478752015-06-19 16:35:38 +0200376 mask = 1 << ts;
Jacob Erlbeck5cd496d2015-06-30 10:24:37 +0200377 } else if (dl_slots || ul_slots) {
378 mask_reason = "need to use a reserved common TS";
379 mask = dl_slots & ul_slots;
380 }
Jacob Erlbeckec478752015-06-19 16:35:38 +0200381
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200382 mask = find_possible_pdchs(trx, 1, mask, mask_reason);
Jacob Erlbeckec478752015-06-19 16:35:38 +0200383 if (!mask)
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200384 return -EINVAL;
385
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200386 ts = find_least_busy_pdch(trx, tbf->direction, mask,
Jacob Erlbeck7af53e62015-07-16 15:04:07 +0200387 compute_usage_for_algo_a,
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200388 &tfi, &usf);
Jacob Erlbeckec478752015-06-19 16:35:38 +0200389
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200390 if (tbf->direction == GPRS_RLCMAC_UL_TBF && usf < 0) {
Pau Espin Pedrola611b4f2020-10-23 17:11:00 +0200391 LOGPAL(tbf, "A", single, use_trx, LOGL_NOTICE,
Max0e6ac792018-02-19 18:43:01 +0100392 "failed to allocate a TS, no USF available\n");
Jacob Erlbeckec478752015-06-19 16:35:38 +0200393 return -EBUSY;
394 }
395
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200396 if (ts < 0) {
Pau Espin Pedrola611b4f2020-10-23 17:11:00 +0200397 LOGPAL(tbf, "A", single, use_trx, LOGL_NOTICE,
Max0e6ac792018-02-19 18:43:01 +0100398 "failed to allocate a TS, no TFI available\n");
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200399 return -EBUSY;
400 }
401
402 pdch = &trx->pdch[ts];
403
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200404 /* The allocation will be successful, so the system state and tbf/ms
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200405 * may be modified from now on. */
Pau Espin Pedrolb5fece92021-08-23 16:58:04 +0200406 if (tbf->direction == GPRS_RLCMAC_UL_TBF) {
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200407 struct gprs_rlcmac_ul_tbf *ul_tbf = as_ul_tbf(tbf);
Max0e6ac792018-02-19 18:43:01 +0100408 LOGPSL(tbf, LOGL_DEBUG, "Assign uplink TS=%d TFI=%d USF=%d\n", ts, tfi, usf);
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200409 assign_uplink_tbf_usf(pdch, ul_tbf, tfi, usf);
Pau Espin Pedrolb5fece92021-08-23 16:58:04 +0200410 } else {
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200411 struct gprs_rlcmac_dl_tbf *dl_tbf = as_dl_tbf(tbf);
Max0e6ac792018-02-19 18:43:01 +0100412 LOGPSL(tbf, LOGL_DEBUG, "Assign downlink TS=%d TFI=%d\n", ts, tfi);
Jacob Erlbecke0853cd2015-07-10 12:25:25 +0200413 assign_dlink_tbf(pdch, dl_tbf, tfi);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200414 }
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200415
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200416 tbf->trx = trx;
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200417 /* the only one TS is the common TS */
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200418 tbf->first_ts = tbf->first_common_ts = ts;
Pau Espin Pedrolc85e0932021-02-25 18:08:10 +0100419 ms_set_reserved_slots(ms, trx, 1 << ts, 1 << ts);
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200420
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200421 tbf->upgrade_to_multislot = false;
Pau Espin Pedrol2182e622021-01-14 16:48:38 +0100422 bts_do_rate_ctr_inc(bts, CTR_TBF_ALLOC_ALGO_A);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200423 return 0;
424}
425
Maxadca67b2018-01-31 15:22:36 +0100426/*! Compute capacity of a given TRX
427 *
428 * \param[in] trx Pointer to TRX object
429 * \param[in] rx_window Receive window
430 * \param[in] tx_window Transmit window
431 * \returns non-negative capacity
432 */
433static inline unsigned compute_capacity(const struct gprs_rlcmac_trx *trx, int rx_window, int tx_window)
434{
435 const struct gprs_rlcmac_pdch *pdch;
436 unsigned ts, capacity = 0;
437
438 for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
439 pdch = &trx->pdch[ts];
440 if (rx_window & (1 << ts))
441 capacity += OSMO_MAX(32 - pdch->num_reserved(GPRS_RLCMAC_DL_TBF), 1);
442
443 /* Only consider common slots for UL */
444 if (tx_window & rx_window & (1 << ts)) {
445 if (find_free_usf(pdch->assigned_usf()) >= 0)
446 capacity += OSMO_MAX(32 - pdch->num_reserved(GPRS_RLCMAC_UL_TBF), 1);
447 }
448 }
449
450 return capacity;
451}
452
Max731e2bb2018-02-05 16:15:30 +0100453/*! Decide if a given slot should be skipped by multislot allocator
454 *
455 * \param[in] ms_class Pointer to MS Class object
456 * \param[in] check_tr Flag indicating whether we should check for Tra or Tta parameters for a given MS class
457 * \param[in] rx_window Receive window
458 * \param[in] tx_window Transmit window
459 * \param[in,out] checked_rx array with already checked RX timeslots
460 * \returns true if the slot should be skipped, false otherwise
461 */
462static bool skip_slot(uint8_t mslot_class, bool check_tr,
463 int16_t rx_window, int16_t tx_window,
464 uint32_t *checked_rx)
465{
466 uint8_t common_slot_count, req_common_slots,
467 rx_slot_count = pcu_bitcount(rx_window),
468 tx_slot_count = pcu_bitcount(tx_window);
469
470 /* Check compliance with TS 45.002, table 6.4.2.2.1 */
471 /* Whether to skip this round doesn not only depend on the bit
472 * sets but also on check_tr. Therefore this check must be done
473 * before doing the mslot_test_and_set_bit shortcut. */
474 if (mslot_class_get_type(mslot_class) == 1) {
475 uint16_t slot_sum = rx_slot_count + tx_slot_count;
476 /* Assume down + up / dynamic.
477 * TODO: For ext-dynamic, down only, up only add more cases.
478 */
479 if (slot_sum <= 6 && tx_slot_count < 3) {
480 if (!check_tr)
481 return true; /* Skip Tta */
482 } else if (slot_sum > 6 && tx_slot_count < 3) {
483 if (check_tr)
484 return true; /* Skip Tra */
485 } else
486 return true; /* No supported row in TS 45.002, table 6.4.2.2.1. */
487 }
488
489 /* Avoid repeated RX combination check */
490 if (mslot_test_and_set_bit(checked_rx, rx_window))
491 return true;
492
493 /* Check number of common slots according to TS 45.002, §6.4.2.2 */
494 common_slot_count = pcu_bitcount(tx_window & rx_window);
495 req_common_slots = OSMO_MIN(tx_slot_count, rx_slot_count);
496 if (mslot_class_get_type(mslot_class) == 1)
497 req_common_slots = OSMO_MIN(req_common_slots, 2);
498
499 if (req_common_slots != common_slot_count)
500 return true;
501
502 return false;
503}
504
Maxa76a7d02018-01-26 11:09:16 +0100505/*! Find set of slots available for allocation while taking MS class into account
506 *
507 * \param[in] trx Pointer to TRX object
508 * \param[in] mslot_class The multislot class
509 * \param[in,out] ul_slots set of UL timeslots
510 * \param[in,out] dl_slots set of DL timeslots
511 * \returns negative error code or 0 on success
512 */
Max46fbfce2017-11-01 19:22:25 +0100513int find_multi_slots(struct gprs_rlcmac_trx *trx, uint8_t mslot_class, uint8_t *ul_slots, uint8_t *dl_slots)
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200514{
Pau Espin Pedrol10475f52021-02-19 17:33:21 +0100515 const uint8_t Rx = mslot_class_get_rx(mslot_class), /* Max number of Rx slots */
516 Tx = mslot_class_get_tx(mslot_class), /* Max number of Tx slots */
Pau Espin Pedrol4df26582021-02-19 17:35:11 +0100517 Sum = mslot_class_get_sum(mslot_class), /* Max number of Tx + Rx slots */
518 Type = mslot_class_get_type(mslot_class);
Pau Espin Pedrol10475f52021-02-19 17:33:21 +0100519 uint8_t max_slots, num_rx, num_tx, mask_sel, pdch_slots, ul_ts, dl_ts;
Max731e2bb2018-02-05 16:15:30 +0100520 int16_t rx_window, tx_window;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200521 char slot_info[9] = {0};
Maxf633b8d2018-01-31 15:28:53 +0100522 int max_capacity = -1;
523 uint8_t max_ul_slots = 0, max_dl_slots = 0;
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200524
Max842d7812017-11-01 18:11:24 +0100525 if (mslot_class)
526 LOGP(DRLCMAC, LOGL_DEBUG, "Slot Allocation (Algorithm B) for class %d\n",
527 mslot_class);
528
Max842d7812017-11-01 18:11:24 +0100529 if (Tx == MS_NA) {
530 LOGP(DRLCMAC, LOGL_NOTICE, "Multislot class %d not applicable.\n",
531 mslot_class);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200532 return -EINVAL;
533 }
534
Pau Espin Pedroldfbf3d22021-02-19 17:31:24 +0100535 max_slots = OSMO_MAX(Rx, Tx);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200536
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200537 if (*dl_slots == 0)
538 *dl_slots = 0xff;
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200539
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200540 if (*ul_slots == 0)
541 *ul_slots = 0xff;
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200542
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200543 pdch_slots = find_possible_pdchs(trx, max_slots, 0xff);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200544
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200545 *dl_slots &= pdch_slots;
546 *ul_slots &= pdch_slots;
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200547
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200548 LOGP(DRLCMAC, LOGL_DEBUG, "- Possible DL/UL slots: (TS=0)\"%s\"(TS=7)\n",
549 set_flag_chars(set_flag_chars(set_flag_chars(slot_info,
550 *dl_slots, 'D', '.'),
551 *ul_slots, 'U'),
552 *ul_slots & *dl_slots, 'C'));
553
554 /* Check for each UL (TX) slot */
555
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200556 /* Iterate through possible numbers of TX slots */
Pau Espin Pedrol47a3b782021-02-19 16:56:36 +0100557 for (num_tx = 1; num_tx <= Tx; num_tx += 1) {
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200558 uint16_t tx_valid_win = (1 << num_tx) - 1;
Maxf633b8d2018-01-31 15:28:53 +0100559 uint8_t rx_mask[MASK_TR + 1];
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200560
Maxf633b8d2018-01-31 15:28:53 +0100561 mslot_fill_rx_mask(mslot_class, num_tx, rx_mask);
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200562
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200563 /* Rotate group of TX slots: UUU-----, -UUU----, ..., UU-----U */
564 for (ul_ts = 0; ul_ts < 8; ul_ts += 1, tx_valid_win <<= 1) {
565 uint16_t rx_valid_win;
566 uint32_t checked_rx[256/32] = {0};
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200567
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200568 /* Wrap valid window */
569 tx_valid_win = mslot_wrap_window(tx_valid_win);
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200570
Alexander Couzens695ce772021-01-12 19:33:53 +0100571 /* for multislot type 1: don't split the window to wrap around.
572 * E.g. 'UU-----U' is invalid for a 4 TN window. Except 8 TN window.
573 * See 45.002 B.1 */
Pau Espin Pedrol4df26582021-02-19 17:35:11 +0100574 if (Type == 1 && num_tx < 8 &&
Alexander Couzens695ce772021-01-12 19:33:53 +0100575 tx_valid_win & (1 << 0) && tx_valid_win & (1 << 7))
576 continue;
577
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200578 tx_window = tx_valid_win;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200579
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200580 /* Filter out unavailable slots */
581 tx_window &= *ul_slots;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200582
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200583 /* Skip if the the first TS (ul_ts) is not in the set */
584 if ((tx_window & (1 << ul_ts)) == 0)
585 continue;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200586
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200587 /* Skip if the the last TS (ul_ts+num_tx-1) is not in the set */
588 if ((tx_window & (1 << ((ul_ts+num_tx-1) % 8))) == 0)
589 continue;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200590
Pau Espin Pedroldfbf3d22021-02-19 17:31:24 +0100591 num_rx = OSMO_MIN(Rx, Sum - num_tx);
Alexander Couzens695ce772021-01-12 19:33:53 +0100592 rx_valid_win = (1 << num_rx) - 1;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200593
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200594 /* Rotate group of RX slots: DDD-----, -DDD----, ..., DD-----D */
595 for (dl_ts = 0; dl_ts < 8; dl_ts += 1, rx_valid_win <<= 1) {
596 /* Wrap valid window */
597 rx_valid_win = (rx_valid_win | rx_valid_win >> 8) & 0xff;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200598
Alexander Couzens695ce772021-01-12 19:33:53 +0100599 /* for multislot type 1: don't split the window to wrap around.
600 * E.g. 'DD-----D' is invalid for a 4 TN window. Except 8 TN window.
601 * See 45.002 B.1 */
Pau Espin Pedrol4df26582021-02-19 17:35:11 +0100602 if (Type == 1 && num_rx < 8 &&
Alexander Couzens695ce772021-01-12 19:33:53 +0100603 (rx_valid_win & (1 << 0)) && (rx_valid_win & (1 << 7)))
604 continue;
605
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200606 /* Validate with both Tta/Ttb/Trb and Ttb/Tra/Trb */
607 for (mask_sel = MASK_TT; mask_sel <= MASK_TR; mask_sel += 1) {
608 int capacity;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200609
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200610 rx_window = mslot_filter_bad(rx_mask[mask_sel], ul_ts, *dl_slots, rx_valid_win);
611 if (rx_window < 0)
612 continue;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200613
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200614 if (skip_slot(mslot_class, mask_sel != MASK_TT, rx_window, tx_window, checked_rx))
615 continue;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200616
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200617 /* Compute capacity */
618 capacity = compute_capacity(trx, rx_window, tx_window);
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200619
Jacob Erlbeck1653f832015-06-30 14:48:13 +0200620#ifdef ENABLE_TS_ALLOC_DEBUG
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200621 LOGP(DRLCMAC, LOGL_DEBUG,
622 "- Considering DL/UL slots: (TS=0)\"%s\"(TS=7), "
623 "capacity = %d\n",
624 set_flag_chars(set_flag_chars(set_flag_chars(set_flag_chars(
625 slot_info,
626 rx_bad, 'x', '.'),
627 rx_window, 'D'),
628 tx_window, 'U'),
629 rx_window & tx_window, 'C'),
630 capacity);
Jacob Erlbeck1653f832015-06-30 14:48:13 +0200631#endif
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200632
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200633 if (capacity <= max_capacity)
634 continue;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200635
Pau Espin Pedrol5d2d2ec2020-09-22 18:03:56 +0200636 max_capacity = capacity;
637 max_ul_slots = tx_window;
638 max_dl_slots = rx_window;
639 }
640 }
641 }
Maxadca67b2018-01-31 15:22:36 +0100642 }
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200643
644 if (!max_ul_slots || !max_dl_slots) {
645 LOGP(DRLCMAC, LOGL_NOTICE,
646 "No valid UL/DL slot combination found\n");
Pau Espin Pedrol9688dc92021-02-25 18:30:33 +0100647 bts_do_rate_ctr_inc(trx->bts, CTR_TBF_ALLOC_FAIL_NO_SLOT_COMBI);
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200648 return -EINVAL;
649 }
650
651 *ul_slots = max_ul_slots;
652 *dl_slots = max_dl_slots;
653
654 return 0;
655}
656
Max0cc72122018-01-31 17:00:06 +0100657/*! Count used bits in slots and reserved_slots bitmasks
658 *
659 * \param[in] slots Timeslots in use
660 * \param[in] reserved_slots Reserved timeslots
661 * \param[out] slotcount Number of TS in use
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100662 * \param[out] reserve_count Number of reserved TS
Max0cc72122018-01-31 17:00:06 +0100663 */
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100664static void count_slots(uint8_t slots, uint8_t reserved_slots, uint8_t *slotcount, uint8_t *reserve_count)
Max0cc72122018-01-31 17:00:06 +0100665{
666 (*slotcount) = pcu_bitcount(slots);
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100667 (*reserve_count) = pcu_bitcount(reserved_slots);
Max0cc72122018-01-31 17:00:06 +0100668}
669
670/*! Return slot mask with single TS from a given UL/DL set according to TBF's direction, ts pointer is set to that TS
671 * number or to negative value on error
672 *
673 * \param[in] trx Pointer to TRX object
674 * \param[in] tbf Pointer to TBF object
675 * \param[in] dl_slots set of DL timeslots
676 * \param[in] ul_slots set of UL timeslots
677 * \param[in] ts corresponding TS or -1 for autoselection
678 * \returns slot mask with single UL or DL timeslot number if possible
679 */
680static uint8_t get_single_ts(const gprs_rlcmac_trx *trx, const gprs_rlcmac_tbf *tbf, uint8_t dl_slots, uint8_t ul_slots,
681 int ts)
682{
683 uint8_t ret = dl_slots & ul_slots; /* Make sure to consider the first common slot only */
684
685 if (ts < 0)
686 ts = find_least_busy_pdch(trx, tbf->direction, ret, compute_usage_by_num_tbfs, NULL, NULL);
687
688 if (ts < 0)
689 return ffs(ret);
690
691 return ret & (1 << ts);
692}
693
694/*! Find set of timeslots available for allocation
695 *
696 * \param[in] trx Pointer to TRX object
697 * \param[in] tbf Pointer to TBF object
698 * \param[in] single Flag to force the single TS allocation
699 * \param[in] ul_slots set of UL timeslots
700 * \param[in] dl_slots set of DL timeslots
701 * \param[in] reserved_ul_slots set of reserved UL timeslots
702 * \param[in] reserved_dl_slots set of reserved DL timeslots
703 * \param[in] first_common_ts First TS common for both UL and DL or -1 if unknown
704 * \returns negative error code or selected TS on success
705 */
706static int tbf_select_slot_set(const gprs_rlcmac_tbf *tbf, const gprs_rlcmac_trx *trx, bool single,
707 uint8_t ul_slots, uint8_t dl_slots,
708 uint8_t reserved_ul_slots, uint8_t reserved_dl_slots,
709 int8_t first_common_ts)
710{
Pau Espin Pedrol393484a2021-05-10 11:21:50 +0200711 bool is_ul = tbf->direction == GPRS_RLCMAC_UL_TBF;
712 uint8_t sl = is_ul ? ul_slots : dl_slots;
Max0cc72122018-01-31 17:00:06 +0100713 char slot_info[9] = { 0 };
714
715 if (single)
716 sl = get_single_ts(trx, tbf, dl_slots, ul_slots, first_common_ts);
717
718 if (!sl) {
719 LOGP(DRLCMAC, LOGL_NOTICE, "No %s slots available\n",
Pau Espin Pedrol393484a2021-05-10 11:21:50 +0200720 is_ul ? "uplink" : "downlink");
Pau Espin Pedrol9688dc92021-02-25 18:30:33 +0100721 bts_do_rate_ctr_inc(trx->bts, CTR_TBF_ALLOC_FAIL_NO_SLOT_AVAIL);
Max0cc72122018-01-31 17:00:06 +0100722 return -EINVAL;
723 }
724
Pau Espin Pedrol393484a2021-05-10 11:21:50 +0200725 if (is_ul) {
Max0cc72122018-01-31 17:00:06 +0100726 snprintf(slot_info, 9, OSMO_BIT_SPEC, OSMO_BIT_PRINT_EX(reserved_ul_slots, 'u'));
727 masked_override_with(slot_info, sl, 'U');
Max0cc72122018-01-31 17:00:06 +0100728 } else {
729 snprintf(slot_info, 9, OSMO_BIT_SPEC, OSMO_BIT_PRINT_EX(reserved_dl_slots, 'd'));
730 masked_override_with(slot_info, sl, 'D');
Max0cc72122018-01-31 17:00:06 +0100731 }
732
Pau Espin Pedrol393484a2021-05-10 11:21:50 +0200733 LOGPC(DRLCMAC, LOGL_DEBUG, "Selected %s slots: (TS=0)\"%s\"(TS=7), %s\n",
734 is_ul ? "UL" : "DL",
735 slot_info, single ? "single" : "multi");
Max0cc72122018-01-31 17:00:06 +0100736
737 return sl;
738}
739
Max2afec6d2018-01-31 17:21:21 +0100740/*! Allocate USF according to a given UL TS mapping
741 *
Max2afec6d2018-01-31 17:21:21 +0100742 * \param[in] trx Pointer to TRX object
Max2afec6d2018-01-31 17:21:21 +0100743 * \param[in] selected_ul_slots set of UL timeslots selected for allocation
744 * \param[in] dl_slots set of DL timeslots
745 * \param[out] usf array for allocated USF
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100746 * \returns updated UL TS mask or negative on error
Max2afec6d2018-01-31 17:21:21 +0100747 */
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100748static int allocate_usf(const gprs_rlcmac_trx *trx, uint8_t selected_ul_slots, uint8_t dl_slots,
749 int *usf_list)
Max2afec6d2018-01-31 17:21:21 +0100750{
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100751 uint8_t ul_slots = selected_ul_slots & dl_slots;
752 unsigned int ts;
Max2afec6d2018-01-31 17:21:21 +0100753
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100754 for (ts = 0; ts < ARRAY_SIZE(trx->pdch); ts++) {
755 const struct gprs_rlcmac_pdch *pdch = &trx->pdch[ts];
756 int8_t free_usf;
Max2afec6d2018-01-31 17:21:21 +0100757
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100758 if (((1 << ts) & ul_slots) == 0)
759 continue;
Max2afec6d2018-01-31 17:21:21 +0100760
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100761 free_usf = find_free_usf(pdch->assigned_usf());
762 if (free_usf < 0) {
763 LOGP(DRLCMAC, LOGL_DEBUG,
764 "- Skipping TS %d, because "
765 "no USF available\n", ts);
766 ul_slots &= (~(1 << ts)) & 0xff;
767 continue;
768 }
769 usf_list[ts] = free_usf;
770 }
771
772 if (!ul_slots) {
Max2afec6d2018-01-31 17:21:21 +0100773 LOGP(DRLCMAC, LOGL_NOTICE, "No USF available\n");
Pau Espin Pedrol9688dc92021-02-25 18:30:33 +0100774 bts_do_rate_ctr_inc(trx->bts, CTR_TBF_ALLOC_FAIL_NO_USF);
Max2afec6d2018-01-31 17:21:21 +0100775 return -EBUSY;
776 }
777
Max2afec6d2018-01-31 17:21:21 +0100778 return ul_slots;
779}
780
Max77988d42018-02-19 18:00:38 +0100781/*! Update MS' reserved timeslots
782 *
783 * \param[in,out] trx Pointer to TRX struct
784 * \param[in,out] ms_ Pointer to MS object
785 * \param[in] tbf_ Pointer to TBF struct
786 * \param[in] res_ul_slots Newly reserved UL slots
787 * \param[in] res_dl_slots Newly reserved DL slots
788 * \param[in] ul_slots available UL slots (for logging only)
789 * \param[in] dl_slots available DL slots (for logging only)
790 */
791static void update_ms_reserved_slots(gprs_rlcmac_trx *trx, GprsMs *ms, uint8_t res_ul_slots, uint8_t res_dl_slots,
792 uint8_t ul_slots, uint8_t dl_slots)
793{
794 char slot_info[9] = { 0 };
795
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100796 if (res_ul_slots == ms_reserved_ul_slots(ms) && res_dl_slots == ms_reserved_dl_slots(ms))
Max77988d42018-02-19 18:00:38 +0100797 return;
798
799 /* The reserved slots have changed, update the MS */
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100800 ms_set_reserved_slots(ms, trx, res_ul_slots, res_dl_slots);
Max77988d42018-02-19 18:00:38 +0100801
802 ts_format(slot_info, dl_slots, ul_slots);
803 LOGP(DRLCMAC, LOGL_DEBUG, "- Reserved DL/UL slots: (TS=0)\"%s\"(TS=7)\n", slot_info);
804}
805
806/*! Assign given UL timeslots to UL TBF
807 *
808 * \param[in,out] ul_tbf Pointer to UL TBF struct
809 * \param[in,out] trx Pointer to TRX object
810 * \param[in] ul_slots Set of slots to be assigned
811 * \param[in] tfi selected TFI
812 * \param[in] usf selected USF
813 */
814static void assign_ul_tbf_slots(struct gprs_rlcmac_ul_tbf *ul_tbf, gprs_rlcmac_trx *trx, uint8_t ul_slots, int tfi,
815 int *usf)
816{
817 uint8_t ts;
818
819 for (ts = 0; ts < 8; ts++) {
820 if (!(ul_slots & (1 << ts)))
821 continue;
822
823 OSMO_ASSERT(usf[ts] >= 0);
824
825 LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning UL TS %u\n", ts);
826 assign_uplink_tbf_usf(&trx->pdch[ts], ul_tbf, tfi, usf[ts]);
827 }
828}
829
830/*! Assign given DL timeslots to DL TBF
831 *
832 * \param[in,out] dl_tbf Pointer to DL TBF struct
833 * \param[in,out] trx Pointer to TRX object
834 * \param[in] ul_slots Set of slots to be assigned
835 * \param[in] tfi selected TFI
836 */
837static void assign_dl_tbf_slots(struct gprs_rlcmac_dl_tbf *dl_tbf, gprs_rlcmac_trx *trx, uint8_t dl_slots, int tfi)
838{
839 uint8_t ts;
840
841 for (ts = 0; ts < 8; ts++) {
842 if (!(dl_slots & (1 << ts)))
843 continue;
844
845 LOGP(DRLCMAC, LOGL_DEBUG, "- Assigning DL TS %u\n", ts);
846 assign_dlink_tbf(&trx->pdch[ts], dl_tbf, tfi);
847 }
848}
849
Maxe9fe0e32017-09-28 15:56:05 +0200850/*! Slot Allocation: Algorithm B
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200851 *
852 * Assign as many downlink slots as possible.
853 * Assign one uplink slot. (With free USF)
854 *
Maxe9fe0e32017-09-28 15:56:05 +0200855 * \param[in,out] bts Pointer to BTS struct
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200856 * \param[in,out] tbf Pointer to TBF struct
Maxe9fe0e32017-09-28 15:56:05 +0200857 * \param[in] single flag indicating if we should force single-slot allocation
858 * \param[in] use_trx which TRX to use or -1 if it should be selected during allocation
859 * \returns negative error code or 0 on success
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200860 */
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200861int alloc_algorithm_b(struct gprs_rlcmac_bts *bts, struct gprs_rlcmac_tbf *tbf, bool single,
Maxe9fe0e32017-09-28 15:56:05 +0200862 int8_t use_trx)
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200863{
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200864 uint8_t dl_slots;
865 uint8_t ul_slots;
866 uint8_t reserved_dl_slots;
867 uint8_t reserved_ul_slots;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200868 int8_t first_common_ts;
869 uint8_t slotcount = 0;
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100870 uint8_t reserve_count = 0, trx_no;
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200871 int first_ts = -1;
872 int usf[8] = {-1, -1, -1, -1, -1, -1, -1, -1};
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200873 int rc;
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200874 int tfi;
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200875 struct GprsMs *ms = tbf->ms();
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200876 gprs_rlcmac_trx *trx;
Jacob Erlbeck5879c642015-07-10 10:41:36 +0200877
Pau Espin Pedrol8353d972020-10-23 17:07:10 +0200878 LOGPAL(tbf, "B", single, use_trx, LOGL_DEBUG, "Alloc start\n");
879
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200880 /* Step 1: Get current state from the MS object */
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200881
Pau Espin Pedrol50272a42021-05-10 12:25:20 +0200882 reserved_dl_slots = ms_reserved_dl_slots(ms);
883 reserved_ul_slots = ms_reserved_ul_slots(ms);
Pau Espin Pedrolda971ee2020-12-16 15:59:45 +0100884 first_common_ts = ms_first_common_ts(ms);
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200885
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200886 /* Step 2a: Find usable TRX and TFI */
Pau Espin Pedrold9066272021-11-09 16:52:31 +0100887 tfi = tfi_find_free(bts, ms, tbf->direction, use_trx, &trx_no);
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200888 if (tfi < 0) {
Max0e6ac792018-02-19 18:43:01 +0100889 LOGPAL(tbf, "B", single, use_trx, LOGL_NOTICE, "failed to allocate a TFI\n");
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200890 return tfi;
891 }
892
893 /* Step 2b: Reserve slots on the TRX for the MS */
Pau Espin Pedrold9066272021-11-09 16:52:31 +0100894 trx = &bts->trx[trx_no];
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200895
Pau Espin Pedrol50272a42021-05-10 12:25:20 +0200896 if (!reserved_dl_slots || !reserved_ul_slots) {
897 rc = find_multi_slots(trx, ms_ms_class(ms), &reserved_ul_slots, &reserved_dl_slots);
Holger Hans Peter Freyther73193112013-12-26 09:49:05 +0100898 if (rc < 0)
899 return rc;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200900 }
Pau Espin Pedrol50272a42021-05-10 12:25:20 +0200901 dl_slots = reserved_dl_slots;
902 ul_slots = reserved_ul_slots;
Max92e9c172017-09-28 16:25:25 +0200903
Max0cc72122018-01-31 17:00:06 +0100904 /* Step 3a: Derive the slot set for the current TBF */
905 rc = tbf_select_slot_set(tbf, trx, single, ul_slots, dl_slots, reserved_ul_slots, reserved_dl_slots,
906 first_common_ts);
907 if (rc < 0)
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200908 return -EINVAL;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200909
Max0cc72122018-01-31 17:00:06 +0100910 /* Step 3b: Derive the slot set for a given direction */
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200911 if (tbf->direction == GPRS_RLCMAC_DL_TBF) {
Max0cc72122018-01-31 17:00:06 +0100912 dl_slots = rc;
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100913 count_slots(dl_slots, reserved_dl_slots, &slotcount, &reserve_count);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200914 } else {
Pau Espin Pedroled2afa32021-02-22 17:20:15 +0100915 rc = allocate_usf(trx, rc, dl_slots, usf);
Max2afec6d2018-01-31 17:21:21 +0100916 if (rc < 0)
917 return rc;
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200918
Max2afec6d2018-01-31 17:21:21 +0100919 ul_slots = rc;
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200920 reserved_ul_slots = ul_slots;
Jacob Erlbeck5f494b82015-07-01 13:10:41 +0200921
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100922 count_slots(ul_slots, reserved_ul_slots, &slotcount, &reserve_count);
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200923 }
924
Pau Espin Pedrol84abd2f2020-09-22 20:08:18 +0200925 first_ts = ffs(rc) - 1;
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200926 first_common_ts = ffs(dl_slots & ul_slots) - 1;
927
928 if (first_common_ts < 0) {
Max0e6ac792018-02-19 18:43:01 +0100929 LOGPAL(tbf, "B", single, use_trx, LOGL_NOTICE, "first common slot unavailable\n");
Jacob Erlbeckea65c722015-06-22 16:14:23 +0200930 return -EINVAL;
931 }
Max0e6ac792018-02-19 18:43:01 +0100932
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200933 if (first_ts < 0) {
Max0e6ac792018-02-19 18:43:01 +0100934 LOGPAL(tbf, "B", single, use_trx, LOGL_NOTICE, "first slot unavailable\n");
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200935 return -EINVAL;
936 }
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200937
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200938 if (single && slotcount) {
Pau Espin Pedrol853cdf82021-11-09 17:35:30 +0100939 tbf->upgrade_to_multislot = (reserve_count > slotcount);
Max0e6ac792018-02-19 18:43:01 +0100940 LOGPAL(tbf, "B", single, use_trx, LOGL_INFO, "using single slot at TS %d\n", first_ts);
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200941 } else {
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200942 tbf->upgrade_to_multislot = false;
Max0e6ac792018-02-19 18:43:01 +0100943 LOGPAL(tbf, "B", single, use_trx, LOGL_INFO, "using %d slots\n", slotcount);
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200944 }
945
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200946 /* The allocation will be successful, so the system state and tbf/ms
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200947 * may be modified from now on. */
948
949 /* Step 4: Update MS and TBF and really allocate the resources */
950
Pau Espin Pedrolc85e0932021-02-25 18:08:10 +0100951 update_ms_reserved_slots(trx, ms, reserved_ul_slots, reserved_dl_slots, ul_slots, dl_slots);
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200952
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200953 tbf->trx = trx;
954 tbf->first_common_ts = first_common_ts;
955 tbf->first_ts = first_ts;
Jacob Erlbeck5a2b8be2015-07-14 11:35:21 +0200956
Pau Espin Pedrolb5fece92021-08-23 16:58:04 +0200957 if (tbf->direction == GPRS_RLCMAC_DL_TBF)
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200958 assign_dl_tbf_slots(as_dl_tbf(tbf), trx, dl_slots, tfi);
Pau Espin Pedrolb5fece92021-08-23 16:58:04 +0200959 else
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200960 assign_ul_tbf_slots(as_ul_tbf(tbf), trx, ul_slots, tfi, usf);
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200961
Pau Espin Pedrol2182e622021-01-14 16:48:38 +0100962 bts_do_rate_ctr_inc(bts, CTR_TBF_ALLOC_ALGO_B);
Jacob Erlbeck5979fe92015-07-14 14:02:41 +0200963
Holger Hans Peter Freyther02ab4a82013-09-29 07:37:40 +0200964 return 0;
965}
Jacob Erlbeck400ec022015-07-14 13:31:48 +0200966
Maxe9fe0e32017-09-28 15:56:05 +0200967/*! Slot Allocation: Algorithm dynamic
Jacob Erlbeck400ec022015-07-14 13:31:48 +0200968 *
969 * This meta algorithm automatically selects on of the other algorithms based
970 * on the current system state.
971 *
972 * The goal is to support as many MS and TBF as possible. On low usage, the
973 * goal is to provide the highest possible bandwidth per MS.
974 *
Maxe9fe0e32017-09-28 15:56:05 +0200975 * \param[in,out] bts Pointer to BTS struct
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200976 * \param[in,out] tbf Pointer to TBF struct
Maxe9fe0e32017-09-28 15:56:05 +0200977 * \param[in] single flag indicating if we should force single-slot allocation
978 * \param[in] use_trx which TRX to use or -1 if it should be selected during allocation
979 * \returns negative error code or 0 on success
Jacob Erlbeck400ec022015-07-14 13:31:48 +0200980 */
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200981int alloc_algorithm_dynamic(struct gprs_rlcmac_bts *bts, struct gprs_rlcmac_tbf *tbf, bool single,
Maxe9fe0e32017-09-28 15:56:05 +0200982 int8_t use_trx)
Jacob Erlbeck400ec022015-07-14 13:31:48 +0200983{
984 int rc;
985
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200986 /* Reset load_is_high if there is at least one idle PDCH */
987 if (bts->multislot_disabled) {
Maxa76a7d02018-01-26 11:09:16 +0100988 bts->multislot_disabled = !idle_pdch_avail(bts);
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200989 if (!bts->multislot_disabled)
990 LOGP(DRLCMAC, LOGL_DEBUG, "Enabling algorithm B\n");
991 }
992
993 if (!bts->multislot_disabled) {
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +0200994 rc = alloc_algorithm_b(bts, tbf, single, use_trx);
Jacob Erlbeck77da3552015-07-16 18:33:46 +0200995 if (rc >= 0)
996 return rc;
997
998 if (!bts->multislot_disabled)
999 LOGP(DRLCMAC, LOGL_DEBUG, "Disabling algorithm B\n");
1000 bts->multislot_disabled = 1;
1001 }
Jacob Erlbeck400ec022015-07-14 13:31:48 +02001002
Pau Espin Pedrol77e2ff32021-10-18 14:00:24 +02001003 return alloc_algorithm_a(bts, tbf, single, use_trx);
Jacob Erlbeck400ec022015-07-14 13:31:48 +02001004}
Jacob Erlbeck7f79f0d2015-07-17 11:38:49 +02001005
Max4da38592018-01-31 18:03:49 +01001006int gprs_alloc_max_dl_slots_per_ms(const struct gprs_rlcmac_bts *bts, uint8_t ms_class)
Jacob Erlbeck7f79f0d2015-07-17 11:38:49 +02001007{
Max842d7812017-11-01 18:11:24 +01001008 int rx = mslot_class_get_rx(ms_class);
Jacob Erlbeck7f79f0d2015-07-17 11:38:49 +02001009
1010 if (rx == MS_NA)
1011 rx = 4;
1012
Pau Espin Pedrolac3fd122021-01-13 18:54:38 +01001013 if (the_pcu->alloc_algorithm == alloc_algorithm_a)
Jacob Erlbeck7f79f0d2015-07-17 11:38:49 +02001014 return 1;
1015
1016 if (bts->multislot_disabled)
1017 return 1;
1018
1019 return rx;
1020}