From d11c05950200d91f559e0d159762bd51bc28593f Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Thu, 6 Sep 2012 21:57:11 +0200 Subject: 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. --- src/gb/gprs_bssgp.c | 227 ++++++++++++++++++++++++++++++++++++++++++++++++++- src/gb/libosmogb.map | 2 + 2 files changed, 225 insertions(+), 4 deletions(-) (limited to 'src/gb') diff --git a/src/gb/gprs_bssgp.c b/src/gb/gprs_bssgp.c index 142e69b8..93aa5aaa 100644 --- a/src/gb/gprs_bssgp.c +++ b/src/gb/gprs_bssgp.c @@ -57,6 +57,9 @@ static const struct rate_ctr_group_desc bssgp_ctrg_desc = { 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 @@ struct bssgp_bvc_ctx *btsctx_alloc(uint16_t bvci, uint16_t nsei) 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 @@ static int bssgp_rx_llc_disc(struct msgb *msg, struct tlv_parsed *tp, 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 @@ static int bssgp_rx_fc_bvc(struct msgb *msg, struct tlv_parsed *tp, 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 @@ int bssgp_tx_dl_ud(struct msgb *msg, uint16_t pdu_lifetime, 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 @@ int bssgp_tx_dl_ud(struct msgb *msg, uint16_t pdu_lifetime, /* 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 */ diff --git a/src/gb/libosmogb.map b/src/gb/libosmogb.map index a41a91a1..8e9f3727 100644 --- a/src/gb/libosmogb.map +++ b/src/gb/libosmogb.map @@ -2,6 +2,8 @@ LIBOSMOGB_1.0 { global: bssgp_cause_str; bssgp_create_cell_id; +bssgp_fc_in; +bssgp_fc_ms_init; bssgp_msgb_alloc; bssgp_msgb_tlli_put; bssgp_parse_cell_id; -- cgit v1.2.3