pespin has submitted this change. ( https://gerrit.osmocom.org/c/libosmo-gprs/+/31098 )
Change subject: rlcmac: Enqueue LLC PDUs based on RadioPriority and SAPI ......................................................................
rlcmac: Enqueue LLC PDUs based on RadioPriority and SAPI
llc_queue and codel code has been taken from osmo-pcu.git 6a5b1b1f3ef83f87a9df1d4511e22f59039e11ed and have been refactored to fit in libosmo-gprs (removed llc_pdu structs, reworked struct types being enqueued, etc.). Support for queues based on radio_prio has also been added.
Related: OS#5500 Change-Id: Icdaa046fb6a71367f10beee16dcf9a5b7b61022e --- M include/osmocom/gprs/rlcmac/Makefile.am A include/osmocom/gprs/rlcmac/codel.h A include/osmocom/gprs/rlcmac/gre.h A include/osmocom/gprs/rlcmac/llc_queue.h M include/osmocom/gprs/rlcmac/rlcmac.h M include/osmocom/gprs/rlcmac/rlcmac_private.h M src/rlcmac/Makefile.am A src/rlcmac/codel.c A src/rlcmac/gre.c A src/rlcmac/llc_queue.c M src/rlcmac/rlcmac.c M src/rlcmac/rlcmac_prim.c 12 files changed, 716 insertions(+), 3 deletions(-)
Approvals: Jenkins Builder: Verified laforge: Looks good to me, but someone else must approve osmith: Looks good to me, but someone else must approve pespin: Looks good to me, approved
diff --git a/include/osmocom/gprs/rlcmac/Makefile.am b/include/osmocom/gprs/rlcmac/Makefile.am index db16d94..b8ff1e0 100644 --- a/include/osmocom/gprs/rlcmac/Makefile.am +++ b/include/osmocom/gprs/rlcmac/Makefile.am @@ -1,4 +1,7 @@ noinst_HEADERS = \ + codel.h \ + gre.h \ + llc_queue.h \ rlcmac_private.h \ $(NULL)
diff --git a/include/osmocom/gprs/rlcmac/codel.h b/include/osmocom/gprs/rlcmac/codel.h new file mode 100644 index 0000000..0314f11 --- /dev/null +++ b/include/osmocom/gprs/rlcmac/codel.h @@ -0,0 +1,96 @@ +/* codel.h + * + * This is an implementation of the CoDel algorithm based on the reference + * pseudocode (see http://queue.acm.org/appendices/codel.html). + * Instead of abstracting the queue itself, the following implementation + * provides a time stamp based automaton. The main work is done by a single + * decision function which updates the state and tells whether to pass or to + * drop a packet after it has been taken from the queue. + * + * Copyright (C) 2015-2023 by sysmocom - s.f.m.c. GmbH info@sysmocom.de + * Author: Jacob Erlbeck jerlbeck@sysmocom.de + * + * 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. + */ + +#pragma once + +#include <time.h> + +/* Spec default values */ +#define GPRS_CODEL_DEFAULT_INTERVAL_MS 100 +#define GPRS_CODEL_DEFAULT_MAXPACKET 512 + +struct gprs_codel { + int dropping; + unsigned count; + struct timespec first_above_time; + struct timespec drop_next; + struct timespec target; + struct timespec interval; + unsigned maxpacket; +}; + +/*! + * \brief Decide about packet drop and update CoDel state + * + * This function takes timing information and decides whether the packet in + * question should be dropped in order to keep related queue in a 'good' state. + * The function is meant to be called when the packet is dequeued. + * + * The CoDel state is updated by this function. + * + * \param state A pointer to the CoDel state of this queue + * \param recv The time when the packet has entered the queue, + * use NULL if dequeueing was not possible because the queue is + * empty + * \param now The current (dequeueing) time + * \param bytes The number of bytes currently stored in the queue (-1 if + * unknown) + * + * \return != 0 if the packet should be dropped, 0 otherwise + */ +int gprs_codel_control(struct gprs_codel *state, const struct timespec *recv, + const struct timespec *now, int bytes); + +/*! + * \brief Initialise CoDel state + * + * This function initialises the CoDel state object. It sets the interval time + * to the default value (GPRS_CODEL_DEFAULT_INTERVAL_MS). + * + * \param state A pointer to the CoDel state of this queue + */ +void gprs_codel_init(struct gprs_codel *state); + +/*! + * \brief Set interval time + * + * This function changes the interval time. + * The target time is derived from the interval time as proposed in the spec + * (5% of interval time). + * + * \param state A pointer to the CoDel state of this queue + * \param interval_ms The initial interval in ms to be used (<= 0 selects the + * default value) + */ +void gprs_codel_set_interval(struct gprs_codel *state, int interval_ms); + +/*! + * \brief Set max packet size + * + * This function changes the maxpacket value. If no more than this number of + * bytes are still stored in the queue, no dropping will be done. + * + * \param state A pointer to the CoDel state of this queue + * \param maxpacket The value in bytes + */ +void gprs_codel_set_maxpacket(struct gprs_codel *state, int maxpacket); diff --git a/include/osmocom/gprs/rlcmac/gre.h b/include/osmocom/gprs/rlcmac/gre.h new file mode 100644 index 0000000..ea50ddb --- /dev/null +++ b/include/osmocom/gprs/rlcmac/gre.h @@ -0,0 +1,25 @@ +/* GPRS RLC/MAC Entity (one per MS) */ +#pragma once + +#include <osmocom/gprs/rlcmac/rlcmac.h> +#include <osmocom/gprs/rlcmac/llc_queue.h> + +struct gprs_rlcmac_ul_tbf; + +struct gprs_rlcmac_entity { + struct llist_head entry; /* item in (struct gprs_rlcmac_ctx)->gre_list */ + uint32_t tlli; + + struct gprs_rlcmac_llc_queue *llc_queue; + + struct gprs_rlcmac_ul_tbf *ul_tbf; +}; + +struct gprs_rlcmac_entity *gprs_rlcmac_entity_alloc(uint32_t tlli); +void gprs_rlcmac_entity_free(struct gprs_rlcmac_entity *gre); + +int gprs_rlcmac_entity_llc_enqueue(struct gprs_rlcmac_entity *gre, uint8_t *ll_pdu, unsigned int ll_pdu_len, + enum osmo_gprs_rlcmac_llc_sapi sapi, uint8_t radio_prio); + +#define LOGGRE(gre, level, fmt, args...) \ + LOGRLCMAC(level, "GRE(%08x) " fmt, (gre)->tlli, ## args) diff --git a/include/osmocom/gprs/rlcmac/llc_queue.h b/include/osmocom/gprs/rlcmac/llc_queue.h new file mode 100644 index 0000000..7e941fb --- /dev/null +++ b/include/osmocom/gprs/rlcmac/llc_queue.h @@ -0,0 +1,62 @@ +#pragma once + +#include <stdint.h> +#include <string.h> +#include <time.h> + +#include <osmocom/core/linuxlist.h> +#include <osmocom/core/msgb.h> + +#include <osmocom/gprs/rlcmac/codel.h> +#include <osmocom/gprs/rlcmac/rlcmac_prim.h> +#include <osmocom/gprs/rlcmac/rlcmac.h> + +struct gprs_rlcmac_entity; + +/* Highet/Lowest radio priority (biggest number) as per 3GPP TS 24.008 version 16.7.0 Release 16 section 10.5.7.2: + * "All other values are interpreted as priority level 4 by this version of the protocol." */ +#define _GPRS_RLCMAC_RADIO_PRIO_HIGHEST 1 +#define _GPRS_RLCMAC_RADIO_PRIO_LOWEST 4 +/* Normalize 0..N-1 (to be used in arrays): */ +#define RADIO_PRIO_NORM(radio_prio) ((radio_prio) - _GPRS_RLCMAC_RADIO_PRIO_HIGHEST) + +enum gprs_rlcmac_llc_queue_sapi_prio { /* lowest value has highest prio */ + GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_GMM = 0, /* SAPI 1 */ + GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_TOM_SMS, /* SAPI 2,7,8 */ + GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_OTHER, /* Other SAPIs */ + _GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_SIZE /* used to calculate size of enum */ +}; + +struct gprs_llc_prio_queue { + struct gprs_codel codel_state; + struct llist_head queue; /* queued LLC DL data. See enum gprs_rlcmac_llc_queue_prio. */ +}; + +struct gprs_rlcmac_llc_queue { + struct gprs_rlcmac_entity *gre; /* backpointer */ + uint32_t avg_queue_delay; /* Average delay of data going through the queue */ + size_t queue_size; + size_t queue_octets; + bool use_codel; + struct gprs_llc_prio_queue pq[RADIO_PRIO_NORM(_GPRS_RLCMAC_RADIO_PRIO_LOWEST) + 1][_GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_SIZE]; /* queued LLC DL data. See enum gprs_rlcmac_llc_queue_prio. */ +}; + +struct gprs_rlcmac_llc_queue *gprs_rlcmac_llc_queue_alloc(struct gprs_rlcmac_entity *gre); +void gprs_rlcmac_llc_queue_free(struct gprs_rlcmac_llc_queue *q); +void gprs_rlcmac_llc_queue_clear(struct gprs_rlcmac_llc_queue *q); + +void gprs_rlcmac_llc_queue_set_codel_params(struct gprs_rlcmac_llc_queue *q, bool use, unsigned int interval_msec); + +int gprs_rlcmac_llc_queue_enqueue(struct gprs_rlcmac_llc_queue *q, uint8_t *ll_pdu, unsigned int ll_pdu_len, + enum osmo_gprs_rlcmac_llc_sapi sapi, uint8_t radio_prio); +struct msgb *gprs_rlcmac_llc_queue_dequeue(struct gprs_rlcmac_llc_queue *q); + +static inline size_t gprs_rlcmac_llc_queue_size(const struct gprs_rlcmac_llc_queue *q) +{ + return q->queue_size; +} + +static inline size_t gprs_rlcmac_llc_queue_octets(const struct gprs_rlcmac_llc_queue *q) +{ + return q->queue_octets; +} diff --git a/include/osmocom/gprs/rlcmac/rlcmac.h b/include/osmocom/gprs/rlcmac/rlcmac.h index 2b5f208..e433a08 100644 --- a/include/osmocom/gprs/rlcmac/rlcmac.h +++ b/include/osmocom/gprs/rlcmac/rlcmac.h @@ -35,3 +35,4 @@ };
void osmo_gprs_rlcmac_set_log_cat(enum osmo_gprs_rlcmac_log_cat logc, int logc_num); +int osmo_gprs_rlcmac_set_codel_params(bool use, unsigned int interval_msec); diff --git a/include/osmocom/gprs/rlcmac/rlcmac_private.h b/include/osmocom/gprs/rlcmac/rlcmac_private.h index fb3ec7a..26284c1 100644 --- a/include/osmocom/gprs/rlcmac/rlcmac_private.h +++ b/include/osmocom/gprs/rlcmac/rlcmac_private.h @@ -18,16 +18,27 @@ #define msgb_rlcmac_prim(msg) ((struct osmo_gprs_rlcmac_prim *)(msg)->l1h)
struct gprs_rlcmac_ctx { - enum osmo_gprs_rlcmac_location location; + struct { + enum osmo_gprs_rlcmac_location location; + struct { + bool use; + uint32_t interval_msec; + } codel; + } cfg; osmo_gprs_rlcmac_prim_up_cb rlcmac_up_cb; void *rlcmac_up_cb_user_data;
osmo_gprs_rlcmac_prim_down_cb rlcmac_down_cb; void *rlcmac_down_cb_user_data; + + struct llist_head gre_list; /* contains (struct gprs_rlcmac_entity)->entry */ };
extern struct gprs_rlcmac_ctx *g_ctx;
+/* rlcmac.c */ +struct gprs_rlcmac_entity *gprs_rlcmac_find_entity_by_tlli(uint32_t tlli); + /* rlcmac_prim.c */ int gprs_rlcmac_prim_call_up_cb(struct osmo_gprs_rlcmac_prim *rlcmac_prim); int gprs_rlcmac_prim_call_down_cb(struct osmo_gprs_rlcmac_prim *rlcmac_prim); diff --git a/src/rlcmac/Makefile.am b/src/rlcmac/Makefile.am index 2e82e25..47e88b6 100644 --- a/src/rlcmac/Makefile.am +++ b/src/rlcmac/Makefile.am @@ -22,6 +22,9 @@ $(NULL)
libosmo_gprs_rlcmac_la_SOURCES = \ + codel.c \ + gre.c \ + llc_queue.c \ rlcmac.c \ rlcmac_prim.c \ ts_24_008.c \ diff --git a/src/rlcmac/codel.c b/src/rlcmac/codel.c new file mode 100644 index 0000000..a6e331e --- /dev/null +++ b/src/rlcmac/codel.c @@ -0,0 +1,175 @@ +/* codel.c + * + * Copyright (C) 2015-2023 by sysmocom - s.f.m.c. GmbH info@sysmocom.de + * Author: Jacob Erlbeck jerlbeck@sysmocom.de + * + * 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. + */ + +#include <stdint.h> +#include <stdlib.h> +#include <math.h> + +#include <osmocom/core/utils.h> +#include <osmocom/core/logging.h> +#include <osmocom/core/timer_compat.h> +#include <osmocom/gprs/rlcmac/codel.h> +#include <osmocom/gprs/rlcmac/rlcmac_private.h> + +static void control_law(struct gprs_codel *state, struct timespec *delta) +{ + /* 256 / sqrt(x), limited to 255 */ + static uint8_t inv_sqrt_tab[] = {255, + 255, 181, 147, 128, 114, 104, 96, 90, 85, 80, 77, 73, 71, 68, + 66, 64, 62, 60, 58, 57, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, + 45, 45, 44, 43, 43, 42, 42, 41, 40, 40, 39, 39, 39, 38, 38, 37, + 37, 36, 36, 36, 35, 35, 35, 34, 34, 34, 33, 33, 33, 33, 32, 32, + 32, 32, 31, 31, 31, 31, 30, 30, 30, 30, 29, 29, 29, 29, 29, 28, + 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, + 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24, + 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, + 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21, + 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, + 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, + 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, + 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17, + 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, + 17, 17, 17, 17 + }; + uint_fast32_t delta_usecs; + uint_fast32_t inv_sqrt; + div_t q; + + if (state->count >= ARRAY_SIZE(inv_sqrt_tab)) + inv_sqrt = 16; + else + inv_sqrt = inv_sqrt_tab[state->count]; + + /* delta = state->interval / sqrt(count) */ + delta_usecs = state->interval.tv_sec * 1000000 + state->interval.tv_nsec/1000; + delta_usecs = delta_usecs * inv_sqrt / 256; + + q = div(delta_usecs, 1000000); + delta->tv_sec = q.quot; + delta->tv_nsec = q.rem * 1000; +} + +void gprs_codel_init(struct gprs_codel *state) +{ + static const struct gprs_codel init_state = {0}; + + *state = init_state; + gprs_codel_set_interval(state, -1); + gprs_codel_set_maxpacket(state, -1); +} + +void gprs_codel_set_interval(struct gprs_codel *state, int interval_ms) +{ + div_t q; + + if (interval_ms <= 0) + interval_ms = GPRS_CODEL_DEFAULT_INTERVAL_MS; + + q = div(interval_ms, 1000); + state->interval.tv_sec = q.quot; + state->interval.tv_nsec = q.rem * 1000000; + + /* target ~ 5% of interval */ + q = div(interval_ms * 13 / 256, 1000); + state->target.tv_sec = q.quot; + state->target.tv_nsec = q.rem * 1000000; +} + +void gprs_codel_set_maxpacket(struct gprs_codel *state, int maxpacket) +{ + + if (maxpacket < 0) + maxpacket = GPRS_CODEL_DEFAULT_MAXPACKET; + + state->maxpacket = maxpacket; +} + +/* + * This is an broken up variant of the algorithm being described in + * http://queue.acm.org/appendices/codel.html + */ +int gprs_codel_control(struct gprs_codel *state, const struct timespec *recv, + const struct timespec *now, int bytes) +{ + struct timespec sojourn_time; + struct timespec delta; + + if (recv == NULL) + goto stop_dropping; + + timespecsub(now, recv, &sojourn_time); + + if (timespeccmp(&sojourn_time, &state->target, <)) + goto stop_dropping; + + if (bytes >= 0 && (unsigned)bytes <= state->maxpacket) + goto stop_dropping; + + if (!timespecisset(&state->first_above_time)) { + timespecadd(now, &state->interval, &state->first_above_time); + goto not_ok_to_drop; + } + + if (timespeccmp(now, &state->first_above_time, <)) + goto not_ok_to_drop; + + /* Ok to drop */ + + if (!state->dropping) { + int recently = 0; + int in_drop_cycle = 0; + if (timespecisset(&state->drop_next)) { + timespecsub(now, &state->drop_next, &delta); + in_drop_cycle = timespeccmp(&delta, &state->interval, <); + recently = in_drop_cycle; + } + if (!recently) { + timespecsub(now, &state->first_above_time, &delta); + recently = !timespeccmp(&delta, &state->interval, <); + }; + if (!recently) + return 0; + + state->dropping = 1; + + if (in_drop_cycle && state->count > 2) + state->count -= 2; + else + state->count = 1; + + state->drop_next = *now; + } else { + if (timespeccmp(now, &state->drop_next, <)) + return 0; + + state->count += 1; + } + + control_law(state, &delta); + timespecadd(&state->drop_next, &delta, &state->drop_next); + + LOGRLCMAC(LOGL_INFO, + "CoDel decided to drop packet, window = %d.%03dms, count = %d\n", + (int)delta.tv_sec, (int)(delta.tv_nsec / 1000000), state->count); + + return 1; + +stop_dropping: + timespecclear(&state->first_above_time); +not_ok_to_drop: + state->dropping = 0; + return 0; +} diff --git a/src/rlcmac/gre.c b/src/rlcmac/gre.c new file mode 100644 index 0000000..7acd4f6 --- /dev/null +++ b/src/rlcmac/gre.c @@ -0,0 +1,75 @@ +/* GPRS RLC/MAC Entity (one per MS) */ +/* + * (C) 2023 by sysmocom - s.f.m.c. GmbH info@sysmocom.de + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation; either version 3 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 Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see http://www.gnu.org/licenses/. + * + */ + +#include <stdbool.h> + +#include <osmocom/gprs/rlcmac/rlcmac.h> +#include <osmocom/gprs/rlcmac/rlcmac_prim.h> +#include <osmocom/gprs/rlcmac/rlcmac_private.h> +#include <osmocom/gprs/rlcmac/gre.h> + +struct gprs_rlcmac_entity *gprs_rlcmac_entity_alloc(uint32_t tlli) +{ + struct gprs_rlcmac_entity *gre; + + gre = talloc_zero(g_ctx, struct gprs_rlcmac_entity); + if (!gre) + return NULL; + + gre->llc_queue = gprs_rlcmac_llc_queue_alloc(gre); + if (!gre->llc_queue) + goto err_free_gre; + gprs_rlcmac_llc_queue_set_codel_params(gre->llc_queue, + g_ctx->cfg.codel.use, + g_ctx->cfg.codel.interval_msec); + + gre->tlli = tlli; + llist_add_tail(&gre->entry, &g_ctx->gre_list); + + return gre; + +err_free_gre: + talloc_free(gre); + return NULL; +} + +void gprs_rlcmac_entity_free(struct gprs_rlcmac_entity *gre) +{ + if (!gre) + return; + gprs_rlcmac_llc_queue_free(gre->llc_queue); + llist_del(&gre->entry); + talloc_free(gre); +} + +int gprs_rlcmac_entity_llc_enqueue(struct gprs_rlcmac_entity *gre, uint8_t *ll_pdu, unsigned int ll_pdu_len, + enum osmo_gprs_rlcmac_llc_sapi sapi, uint8_t radio_prio) +{ + int rc; + rc = gprs_rlcmac_llc_queue_enqueue(gre->llc_queue, ll_pdu, ll_pdu_len, + sapi, radio_prio); + if (rc < 0) + return rc; + + /* TODO: here a new UL TBF will be created if not available yet */ + + return rc; +} diff --git a/src/rlcmac/llc_queue.c b/src/rlcmac/llc_queue.c new file mode 100644 index 0000000..1422f1f --- /dev/null +++ b/src/rlcmac/llc_queue.c @@ -0,0 +1,212 @@ +/* llc_queue.c + * + * Copyright (C) 2012 Ivan Klyuchnikov + * Copyright (C) 2012 Andreas Eversberg jolly@eversberg.eu + * Copyright (C) 2013 by Holger Hans Peter Freyther + * Copyright (C) 2023 sysmocom - s.f.m.c. GmbH info@sysmocom.de + * + * 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. + */ + + +#include <stdio.h> + +#include <osmocom/core/msgb.h> +#include <osmocom/core/logging.h> +#include <osmocom/core/timer.h> +#include <osmocom/core/timer_compat.h> +#include <osmocom/gprs/rlcmac/rlcmac_private.h> +#include <osmocom/gprs/rlcmac/llc_queue.h> +#include <osmocom/gprs/rlcmac/gre.h> + +struct llc_queue_entry_hdr { + struct timespec recv_time; +}; + +struct gprs_rlcmac_llc_queue *gprs_rlcmac_llc_queue_alloc(struct gprs_rlcmac_entity *gre) +{ + struct gprs_rlcmac_llc_queue *q; + uint32_t i, j; + + q = talloc_zero(gre, struct gprs_rlcmac_llc_queue); + if (!q) + return NULL; + + q->gre = gre; + q->queue_size = 0; + q->queue_octets = 0; + q->avg_queue_delay = 0; + for (i = 0; i < ARRAY_SIZE(q->pq); i++) { + for (j = 0; j < ARRAY_SIZE(q->pq[i]); j++) { + INIT_LLIST_HEAD(&q->pq[i][j].queue); + gprs_codel_init(&q->pq[i][j].codel_state); + } + } + + return q; +} + +void gprs_rlcmac_llc_queue_free(struct gprs_rlcmac_llc_queue *q) +{ + talloc_free(q); +} + +void gprs_rlcmac_llc_queue_set_codel_params(struct gprs_rlcmac_llc_queue *q, bool use, unsigned int interval_msec) +{ + unsigned int i, j; + + q->use_codel = use; + + if (!q->use_codel) + return; + + for (i = 0; i < ARRAY_SIZE(q->pq); i++) + for (j = 0; j < ARRAY_SIZE(q->pq[i]); j++) + gprs_codel_set_interval(&q->pq[i][j].codel_state, interval_msec); +} + +static enum gprs_rlcmac_llc_queue_sapi_prio gprs_rlcmac_llc_sapi2prio(enum osmo_gprs_rlcmac_llc_sapi sapi) +{ + switch (sapi) { + case OSMO_GPRS_RLCMAC_LLC_SAPI_GMM: + return GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_GMM; + case OSMO_GPRS_RLCMAC_LLC_SAPI_TOM2: + case OSMO_GPRS_RLCMAC_LLC_SAPI_SMS: + case OSMO_GPRS_RLCMAC_LLC_SAPI_TOM8: + return GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_TOM_SMS; + default: + return GPRS_RLCMAC_LLC_QUEUE_SAPI_PRIO_OTHER; + } +} + +int gprs_rlcmac_llc_queue_enqueue(struct gprs_rlcmac_llc_queue *q, uint8_t *ll_pdu, unsigned int ll_pdu_len, + enum osmo_gprs_rlcmac_llc_sapi sapi, uint8_t radio_prio) +{ + struct llc_queue_entry_hdr *ehdr; + enum gprs_rlcmac_llc_queue_sapi_prio sapi_prio; + struct msgb *msg; + + /* Trim to expected values 1..4, (3GPP TS 24.008) 10.5.7.2 */ + if (radio_prio < _GPRS_RLCMAC_RADIO_PRIO_HIGHEST) + radio_prio = _GPRS_RLCMAC_RADIO_PRIO_HIGHEST; + else if (radio_prio > _GPRS_RLCMAC_RADIO_PRIO_LOWEST) + radio_prio = _GPRS_RLCMAC_RADIO_PRIO_LOWEST; + + sapi_prio = gprs_rlcmac_llc_sapi2prio(sapi); + + msg = msgb_alloc_headroom(sizeof(*ehdr) + ll_pdu_len, 0, "llc_queue_msg"); + msg->l1h = msgb_put(msg, sizeof(*ehdr)); + ehdr = (struct llc_queue_entry_hdr *)msg->l1h; + + osmo_clock_gettime(CLOCK_MONOTONIC, &ehdr->recv_time); + + if (ll_pdu_len) { + msg->l2h = msgb_put(msg, ll_pdu_len); + memcpy(msg->l2h, ll_pdu, ll_pdu_len); + } else { + msg->l2h = NULL; + } + + msgb_enqueue(&q->pq[RADIO_PRIO_NORM(radio_prio)][sapi_prio].queue, msg); + q->queue_size += 1; + q->queue_octets += ll_pdu_len; + + return 0; +} + +void gprs_rlcmac_llc_queue_clear(struct gprs_rlcmac_llc_queue *q) +{ + struct msgb *msg; + unsigned int i, j; + + for (i = 0; i < ARRAY_SIZE(q->pq); i++) { + for (j = 0; j < ARRAY_SIZE(q->pq[i]); j++) { + while ((msg = msgb_dequeue(&q->pq[i][j].queue))) + msgb_free(msg); + } + } + + q->queue_size = 0; + q->queue_octets = 0; +} + +#define ALPHA 0.5f + +static struct msgb *gprs_rlcmac_llc_queue_pick_msg(struct gprs_rlcmac_llc_queue *q, struct gprs_llc_prio_queue **prioq) +{ + struct msgb *msg; + struct timespec tv_now, tv_result; + uint32_t lifetime; + unsigned int i, j; + const struct llc_queue_entry_hdr *ehdr; + + for (i = 0; i < ARRAY_SIZE(q->pq); i++) { + for (j = 0; j < ARRAY_SIZE(q->pq[i]); j++) { + if ((msg = msgb_dequeue(&q->pq[i][j].queue))) { + *prioq = &q->pq[i][j]; + goto found; + } + } + } + return NULL; + +found: + ehdr = msgb_l1(msg); + + q->queue_size -= 1; + q->queue_octets -= msgb_l2len(msg); + + /* take the second time */ + osmo_clock_gettime(CLOCK_MONOTONIC, &tv_now); + timespecsub(&tv_now, &ehdr->recv_time, &tv_result); + + lifetime = tv_result.tv_sec*1000 + tv_result.tv_nsec/1000000; + q->avg_queue_delay = q->avg_queue_delay * ALPHA + lifetime * (1-ALPHA); + + return msg; +} + +struct msgb *gprs_rlcmac_llc_queue_dequeue(struct gprs_rlcmac_llc_queue *q) +{ + struct msgb *msg; + struct timespec tv_now; + uint32_t octets = 0, frames = 0; + struct gprs_llc_prio_queue *prioq; + const struct llc_queue_entry_hdr *ehdr; + + osmo_clock_gettime(CLOCK_MONOTONIC, &tv_now); + + while ((msg = gprs_rlcmac_llc_queue_pick_msg(q, &prioq))) { + ehdr = msgb_l1(msg); + if (q->use_codel) { + int bytes = gprs_rlcmac_llc_queue_octets(q); + if (gprs_codel_control(&prioq->codel_state, &ehdr->recv_time, &tv_now, bytes)) { + /* Drop frame: */ + frames++; + octets += msg->len; + msgb_free(msg); + /* rate_ctr_inc(CTR_LLC_FRAME_DROPPED); */ + } + } + + /* dequeue current msg */ + break; + } + + if (frames > 0) { + LOGGRE(q->gre, LOGL_NOTICE, "Discarding %u LLC PDUs (%u octets) due to codel algo, " + "new_queue_size=%zu\n", frames, octets, gprs_rlcmac_llc_queue_size(q)); + } + + msgb_pull_to_l2(msg); + + return msg; +} diff --git a/src/rlcmac/rlcmac.c b/src/rlcmac/rlcmac.c index faf3489..13a3e84 100644 --- a/src/rlcmac/rlcmac.c +++ b/src/rlcmac/rlcmac.c @@ -19,9 +19,14 @@ * */
+#include <stdbool.h> + #include <osmocom/gprs/rlcmac/rlcmac.h> #include <osmocom/gprs/rlcmac/rlcmac_prim.h> #include <osmocom/gprs/rlcmac/rlcmac_private.h> +#include <osmocom/gprs/rlcmac/gre.h> + +#define GPRS_CODEL_SLOW_INTERVAL_MS 4000
struct gprs_rlcmac_ctx *g_ctx;
@@ -33,7 +38,36 @@ talloc_free(g_ctx);
g_ctx = talloc_zero(NULL, struct gprs_rlcmac_ctx); - g_ctx->location = location; + g_ctx->cfg.location = location; + g_ctx->cfg.codel.use = true; + g_ctx->cfg.codel.interval_msec = GPRS_CODEL_SLOW_INTERVAL_MS; + INIT_LLIST_HEAD(&g_ctx->gre_list);
return 0; } + +/*! Set CoDel parameters used in the Tx queue of LLC PDUs waiting to be transmitted. + * \param[in] use Whether to enable or disable use of CoDel algo. + * \param[in] interval_msec Interval at which CoDel triggers, in milliseconds. (0 = use default interval value) + * \returns 0 on success; negative on error. + */ +int osmo_gprs_rlcmac_set_codel_params(bool use, unsigned int interval_msec) +{ + if (interval_msec == 0) + interval_msec = GPRS_CODEL_SLOW_INTERVAL_MS; + + g_ctx->cfg.codel.use = use; + g_ctx->cfg.codel.interval_msec = interval_msec; + return 0; +} + +struct gprs_rlcmac_entity *gprs_rlcmac_find_entity_by_tlli(uint32_t tlli) +{ + struct gprs_rlcmac_entity *gre; + + llist_for_each_entry(gre, &g_ctx->gre_list, entry) { + if (gre->tlli == tlli) + return gre; + } + return NULL; +} diff --git a/src/rlcmac/rlcmac_prim.c b/src/rlcmac/rlcmac_prim.c index 1d5dcc9..23de05d 100644 --- a/src/rlcmac/rlcmac_prim.c +++ b/src/rlcmac/rlcmac_prim.c @@ -35,6 +35,7 @@ #include <osmocom/gprs/rlcmac/rlcmac.h> #include <osmocom/gprs/rlcmac/rlcmac_prim.h> #include <osmocom/gprs/rlcmac/rlcmac_private.h> +#include <osmocom/gprs/rlcmac/gre.h>
#define RLCMAC_MSGB_HEADROOM 0
@@ -213,7 +214,22 @@
static int rlcmac_prim_handle_grr_unitdata_req(struct osmo_gprs_rlcmac_prim *rlcmac_prim) { - int rc = gprs_rlcmac_prim_handle_unsupported(rlcmac_prim); + struct gprs_rlcmac_entity *gre; + int rc; + + gre = gprs_rlcmac_find_entity_by_tlli(rlcmac_prim->grr.tlli); + if (!gre) { + LOGRLCMAC(LOGL_INFO, "TLLI=0x%08x not found, creating entity on the fly\n", + rlcmac_prim->grr.tlli); + gre = gprs_rlcmac_entity_alloc(rlcmac_prim->grr.tlli); + } + OSMO_ASSERT(gre); + + rc = gprs_rlcmac_entity_llc_enqueue(gre, + rlcmac_prim->grr.ll_pdu, + rlcmac_prim->grr.ll_pdu_len, + rlcmac_prim->grr.unitdata_req.sapi, + rlcmac_prim->grr.unitdata_req.radio_prio); return rc; }