libosmogb: Port BSSGP flow control from openbsc/laforge/bssgp_fc branch
This code is supposed to implement the BSSGP flow control algorithm,
both for the per-BSS and for the per-MS flow control.
The code currently has no test cases, they will come in a separate
commit.
diff --git a/src/gb/gprs_bssgp.c b/src/gb/gprs_bssgp.c
index 142e69b..93aa5aa 100644
--- a/src/gb/gprs_bssgp.c
+++ b/src/gb/gprs_bssgp.c
@@ -57,6 +57,9 @@
LLIST_HEAD(bssgp_bvc_ctxts);
+static int _bssgp_tx_dl_ud(struct bssgp_flow_control *fc, struct msgb *msg,
+ uint32_t llc_pdu_len, void *priv);
+
/* Find a BTS Context based on parsed RA ID and Cell ID */
struct bssgp_bvc_ctx *btsctx_by_raid_cid(const struct gprs_ra_id *raid, uint16_t cid)
{
@@ -93,6 +96,7 @@
ctx->nsei = nsei;
/* FIXME: BVCI is not unique, only BVCI+NSEI ?!? */
ctx->ctrg = rate_ctr_group_alloc(ctx, &bssgp_ctrg_desc, bvci);
+ ctx->fc.out_cb = &_bssgp_tx_dl_ud;
llist_add(&ctx->list, &bssgp_bvc_ctxts);
@@ -510,6 +514,204 @@
return bssgp_prim_cb(&nmp.oph, NULL);
}
+/* One element (msgb) in a BSSGP Flow Control queue */
+struct bssgp_fc_queue_element {
+ /* linked list of queue elements */
+ struct llist_head list;
+ /* The message that we have enqueued */
+ struct msgb *msg;
+ /* Length of the LLC PDU part of the contained message */
+ uint32_t llc_pdu_len;
+ /* private pointer passed to the flow control out_cb function */
+ void *priv;
+};
+
+static int fc_queue_timer_cfg(struct bssgp_flow_control *fc);
+static int bssgp_fc_needs_queueing(struct bssgp_flow_control *fc, uint32_t pdu_len);
+
+static void fc_timer_cb(void *data)
+{
+ struct bssgp_flow_control *fc = data;
+ struct bssgp_fc_queue_element *fcqe;
+ struct timeval time_now;
+
+ /* if the queue is empty, we return without sending something
+ * and without re-starting the timer */
+ if (llist_empty(&fc->queue))
+ return;
+
+ /* get the first entry from the queue */
+ fcqe = llist_entry(fc->queue.next, struct bssgp_fc_queue_element,
+ list);
+
+ if (bssgp_fc_needs_queueing(fc, fcqe->llc_pdu_len)) {
+ LOGP(DBSSGP, LOGL_NOTICE, "BSSGP-FC: fc_timer_cb() but still "
+ "not able to send PDU of %u bytes\n", fcqe->llc_pdu_len);
+ /* make sure we re-start the timer */
+ fc_queue_timer_cfg(fc);
+ return;
+ }
+
+ /* remove from the queue */
+ llist_del(&fcqe->list);
+
+ fc->queue_depth--;
+
+ /* record the time we transmitted this PDU */
+ gettimeofday(&time_now, NULL);
+ fc->time_last_pdu = time_now;
+
+ /* call the output callback for this FC instance */
+ fc->out_cb(fcqe->priv, fcqe->msg, fcqe->llc_pdu_len, NULL);
+
+ /* we expect that out_cb will in the end free the msgb once
+ * it is no longer needed */
+
+ /* but we have to free the queue element ourselves */
+ talloc_free(fcqe);
+
+ /* re-configure the timer for the next PDU */
+ fc_queue_timer_cfg(fc);
+}
+
+/* configure/schedule the flow control timer to expire once the bucket
+ * will have leaked a sufficient number of bytes to transmit the next
+ * PDU in the queue */
+static int fc_queue_timer_cfg(struct bssgp_flow_control *fc)
+{
+ struct bssgp_fc_queue_element *fcqe;
+ uint32_t msecs;
+
+ if (llist_empty(&fc->queue))
+ return 0;
+
+ fcqe = llist_entry(&fc->queue.next, struct bssgp_fc_queue_element,
+ list);
+
+ /* Calculate the point in time at which we will have leaked
+ * a sufficient number of bytes from the bucket to transmit
+ * the first PDU in the queue */
+ msecs = (fcqe->llc_pdu_len * 1000) / fc->bucket_leak_rate;
+ /* FIXME: add that time to fc->time_last_pdu and subtract it from
+ * current time */
+
+ fc->timer.data = fc;
+ fc->timer.cb = &fc_timer_cb;
+ osmo_timer_schedule(&fc->timer, msecs / 1000, (msecs % 1000) * 1000);
+
+ return 0;
+}
+
+/* Enqueue a PDU in the flow control queue for delayed transmission */
+static int fc_enqueue(struct bssgp_flow_control *fc, struct msgb *msg,
+ uint32_t llc_pdu_len, void *priv)
+{
+ struct bssgp_fc_queue_element *fcqe;
+
+ if (fc->queue_depth >= fc->max_queue_depth)
+ return -ENOSPC;
+
+ fcqe = talloc_zero(fc, struct bssgp_fc_queue_element);
+ if (!fcqe)
+ return -ENOMEM;
+ fcqe->msg = msg;
+ fcqe->llc_pdu_len = llc_pdu_len;
+ fcqe->priv = priv;
+
+ llist_add_tail(&fcqe->list, &fc->queue);
+
+ fc->queue_depth++;
+
+ /* re-configure the timer for dequeueing the pdu */
+ fc_queue_timer_cfg(fc);
+
+ return 0;
+}
+
+/* According to Section 8.2 */
+static int bssgp_fc_needs_queueing(struct bssgp_flow_control *fc, uint32_t pdu_len)
+{
+ struct timeval time_now, time_diff;
+ int64_t bucket_predicted;
+ uint32_t csecs_elapsed, leaked;
+
+ /* B' = B + L(p) - (Tc - Tp)*R */
+
+ /* compute number of centi-seconds that have elapsed since transmitting
+ * the last PDU (Tc - Tp) */
+ gettimeofday(&time_now, NULL);
+ timersub(&time_now, &fc->time_last_pdu, &time_diff);
+ csecs_elapsed = time_diff.tv_sec*100 + time_diff.tv_usec/10000;
+
+ /* compute number of bytes that have leaked in the elapsed number
+ * of centi-seconds */
+ leaked = csecs_elapsed * (fc->bucket_leak_rate / 100);
+ /* add the current PDU length to the last bucket level */
+ bucket_predicted = fc->bucket_counter + pdu_len;
+ /* ... and subtract the number of leaked bytes */
+ bucket_predicted -= leaked;
+
+ if (bucket_predicted < pdu_len) {
+ /* this is just to make sure the bucket doesn't underflow */
+ bucket_predicted = pdu_len;
+ goto pass;
+ }
+
+ if (bucket_predicted <= fc->bucket_size_max) {
+ /* the bucket is not full yet, we can pass the packet */
+ fc->bucket_counter = bucket_predicted;
+ goto pass;
+ }
+
+ /* bucket is full, PDU needs to be delayed */
+ return 1;
+
+pass:
+ /* if we reach here, the PDU can pass */
+ return 0;
+}
+
+/* output callback for BVC flow control */
+static int _bssgp_tx_dl_ud(struct bssgp_flow_control *fc, struct msgb *msg,
+ uint32_t llc_pdu_len, void *priv)
+{
+ return gprs_ns_sendmsg(bssgp_nsi, msg);
+}
+
+/* input function of the flow control implementation, called first
+ * for the MM flow control, and then as the MM flow control output
+ * callback in order to perform BVC flow control */
+int bssgp_fc_in(struct bssgp_flow_control *fc, struct msgb *msg,
+ uint32_t llc_pdu_len, void *priv)
+{
+ struct timeval time_now;
+
+ if (bssgp_fc_needs_queueing(fc, llc_pdu_len)) {
+ return fc_enqueue(fc, msg, llc_pdu_len, priv);
+ } else {
+ /* record the time we transmitted this PDU */
+ gettimeofday(&time_now, NULL);
+ fc->time_last_pdu = time_now;
+ return fc->out_cb(priv, msg, llc_pdu_len, NULL);
+ }
+}
+
+/* Initialize the Flow Control parameters for a new MS according to
+ * default values for the BVC specified by BVCI and NSEI */
+int bssgp_fc_ms_init(struct bssgp_flow_control *fc_ms, uint16_t bvci,
+ uint16_t nsei)
+{
+ struct bssgp_bvc_ctx *ctx;
+
+ ctx = btsctx_by_bvci_nsei(bvci, nsei);
+ if (!ctx)
+ return -ENODEV;
+ fc_ms->bucket_size_max = ctx->bmax_default_ms;
+ fc_ms->bucket_leak_rate = ctx->r_default_ms;
+
+ return 0;
+}
+
static int bssgp_rx_fc_bvc(struct msgb *msg, struct tlv_parsed *tp,
struct bssgp_bvc_ctx *bctx)
{
@@ -527,7 +729,18 @@
return bssgp_tx_status(BSSGP_CAUSE_MISSING_MAND_IE, NULL, msg);
}
- /* FIXME: actually implement flow control */
+ /* 11.3.5 */
+ bctx->fc.bucket_size_max = 100 *
+ ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BVC_BUCKET_SIZE));
+ /* 11.3.4 */
+ bctx->fc.bucket_leak_rate = 100 *
+ ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BUCKET_LEAK_RATE));
+ /* 11.3.2 */
+ bctx->bmax_default_ms = 100 *
+ ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BMAX_DEFAULT_MS));
+ /* 11.3.32 */
+ bctx->r_default_ms = 100 *
+ ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_R_DEFAULT_MS));
/* Send FLOW_CONTROL_BVC_ACK */
return bssgp_tx_fc_bvc_ack(msgb_nsei(msg), *TLVP_VAL(tp, BSSGP_IE_TAG),
@@ -777,8 +990,9 @@
bctx = btsctx_by_bvci_nsei(bvci, nsei);
if (!bctx) {
- /* FIXME: don't simply create missing context, but reject message */
- bctx = btsctx_alloc(bvci, nsei);
+ LOGP(DBSSGP, LOGL_ERROR, "Cannot send DL-UD to unknown BVCI %u\n",
+ bvci);
+ return -ENODEV;
}
if (msg->len > TVLV_MAX_ONEBYTE)
@@ -841,7 +1055,12 @@
/* Identifiers down: BVCI, NSEI (in msgb->cb) */
- return gprs_ns_sendmsg(bssgp_nsi, msg);
+ /* check if we have to go through per-ms flow control or can go
+ * directly to the per-BSS flow control */
+ if (dup->fc)
+ return bssgp_fc_in(dup->fc, msg, msg_len, &bctx->fc);
+ else
+ return bssgp_fc_in(&bctx->fc, msg, msg_len, NULL);
}
/* Send a single GMM-PAGING.req to a given NSEI/NS-BVCI */