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') 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 From bb8262275f8bbf2b2264d68c5328a8c1a8c634d3 Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Fri, 7 Sep 2012 10:22:01 +0200 Subject: BSSGP flow-control: various fixes * add more comments on units of struct members * make sure to parsre FC-BVC message correctly * add error message in case user passes PDU larger than bucket size * add new function to initialize flow control struct --- src/gb/gprs_bssgp.c | 45 +++++++++++++++++++++++++++++++++++---------- src/gb/libosmogb.map | 1 + 2 files changed, 36 insertions(+), 10 deletions(-) (limited to 'src') diff --git a/src/gb/gprs_bssgp.c b/src/gb/gprs_bssgp.c index 93aa5aaa..70e2a1c5 100644 --- a/src/gb/gprs_bssgp.c +++ b/src/gb/gprs_bssgp.c @@ -686,6 +686,13 @@ int bssgp_fc_in(struct bssgp_flow_control *fc, struct msgb *msg, { struct timeval time_now; + if (llc_pdu_len > fc->bucket_size_max) { + LOGP(DBSSGP, LOGL_NOTICE, "Single PDU (size=%u) is larger " + "than maximum bucket size (%u)!\n", llc_pdu_len, + fc->bucket_size_max); + return -EIO; + } + if (bssgp_fc_needs_queueing(fc, llc_pdu_len)) { return fc_enqueue(fc, msg, llc_pdu_len, priv); } else { @@ -696,18 +703,36 @@ int bssgp_fc_in(struct bssgp_flow_control *fc, struct msgb *msg, } } + +/* Initialize the Flow Control structure */ +void bssgp_fc_init(struct bssgp_flow_control *fc, + uint32_t bucket_size_max, uint32_t bucket_leak_rate, + uint32_t max_queue_depth, + int (*out_cb)(struct bssgp_flow_control *fc, struct msgb *msg, + uint32_t llc_pdu_len, void *priv)) +{ + fc->out_cb = out_cb; + fc->bucket_size_max = bucket_size_max; + fc->bucket_leak_rate = bucket_leak_rate; + fc->max_queue_depth = max_queue_depth; + INIT_LLIST_HEAD(&fc->queue); + gettimeofday(&fc->time_last_pdu, 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) + uint16_t nsei, uint32_t max_queue_depth) { 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; + + /* output call-back of per-MS FC is per-CTX FC */ + bssgp_fc_init(fc_ms, ctx->bmax_default_ms, ctx->r_default_ms, + max_queue_depth, bssgp_fc_in); return 0; } @@ -729,18 +754,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); } - /* 11.3.5 */ + /* 11.3.5 Bucket Size in 100 octets unit */ bctx->fc.bucket_size_max = 100 * ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BVC_BUCKET_SIZE)); - /* 11.3.4 */ + /* 11.3.4 Bucket Leak Rate in 100 bits/sec unit */ 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_BUCKET_LEAK_RATE)) / 8; + /* 11.3.2 in octets */ + bctx->bmax_default_ms = ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BMAX_DEFAULT_MS)); - /* 11.3.32 */ + /* 11.3.32 Bucket Leak rate in 100bits/sec unit */ bctx->r_default_ms = 100 * - ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_R_DEFAULT_MS)); + ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_R_DEFAULT_MS)) / 8; /* Send FLOW_CONTROL_BVC_ACK */ return bssgp_tx_fc_bvc_ack(msgb_nsei(msg), *TLVP_VAL(tp, BSSGP_IE_TAG), diff --git a/src/gb/libosmogb.map b/src/gb/libosmogb.map index 8e9f3727..d0f76f86 100644 --- a/src/gb/libosmogb.map +++ b/src/gb/libosmogb.map @@ -3,6 +3,7 @@ global: bssgp_cause_str; bssgp_create_cell_id; bssgp_fc_in; +bssgp_fc_init; bssgp_fc_ms_init; bssgp_msgb_alloc; bssgp_msgb_tlli_put; -- cgit v1.2.3 From d8b476988d38f3ef2267594a46d0e4a9fc6eb6a1 Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Fri, 7 Sep 2012 11:29:32 +0200 Subject: BSSGP: make bvc_ctx->fc a dynamic talloc allocation this ensures that we can talloc the flow-control queue entries as siblings off the bvc_ctx. --- src/gb/gprs_bssgp.c | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/gb/gprs_bssgp.c b/src/gb/gprs_bssgp.c index 70e2a1c5..e41c7efb 100644 --- a/src/gb/gprs_bssgp.c +++ b/src/gb/gprs_bssgp.c @@ -96,7 +96,9 @@ 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; + ctx->fc = talloc_zero(ctx, struct bssgp_flow_control); + /* cofigure for 2Mbit, 30 packets in queue */ + bssgp_fc_init(ctx->fc, 100000, 2*1024*1024/8, 30, &_bssgp_tx_dl_ud); llist_add(&ctx->list, &bssgp_bvc_ctxts); @@ -755,10 +757,10 @@ static int bssgp_rx_fc_bvc(struct msgb *msg, struct tlv_parsed *tp, } /* 11.3.5 Bucket Size in 100 octets unit */ - bctx->fc.bucket_size_max = 100 * + bctx->fc->bucket_size_max = 100 * ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BVC_BUCKET_SIZE)); /* 11.3.4 Bucket Leak Rate in 100 bits/sec unit */ - bctx->fc.bucket_leak_rate = 100 * + bctx->fc->bucket_leak_rate = 100 * ntohs(*(uint16_t *)TLVP_VAL(tp, BSSGP_IE_BUCKET_LEAK_RATE)) / 8; /* 11.3.2 in octets */ bctx->bmax_default_ms = @@ -1083,9 +1085,9 @@ int bssgp_tx_dl_ud(struct msgb *msg, uint16_t pdu_lifetime, /* 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); + return bssgp_fc_in(dup->fc, msg, msg_len, bctx->fc); else - return bssgp_fc_in(&bctx->fc, msg, msg_len, NULL); + return bssgp_fc_in(bctx->fc, msg, msg_len, NULL); } /* Send a single GMM-PAGING.req to a given NSEI/NS-BVCI */ -- cgit v1.2.3 From 0823e1e42a833be8030530fd26c46ed3c8b42fea Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Fri, 7 Sep 2012 12:13:09 +0200 Subject: BSSGP: print per-bvc flow control parameters on vty --- src/gb/gprs_bssgp_vty.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/gb/gprs_bssgp_vty.c b/src/gb/gprs_bssgp_vty.c index aa1f1065..d8e1d32f 100644 --- a/src/gb/gprs_bssgp_vty.c +++ b/src/gb/gprs_bssgp_vty.c @@ -88,8 +88,19 @@ static void dump_bvc(struct vty *vty, struct bssgp_bvc_ctx *bvc, int stats) bvc->ra_id.mnc, bvc->ra_id.lac, bvc->ra_id.rac, bvc->cell_id, bvc->state & BVC_S_BLOCKED ? "BLOCKED" : "UNBLOCKED", VTY_NEWLINE); - if (stats) + + if (stats) { + struct bssgp_flow_control *fc = bvc->fc; + vty_out_rate_ctr_group(vty, " ", bvc->ctrg); + + if (fc) + vty_out(vty, "FC-BVC(bucket_max: %uoct, leak_rate: " + "%uoct/s, cur_tokens: %uoct, max_q_d: %u, " + "cur_q_d: %u)\n", fc->bucket_size_max, + fc->bucket_leak_rate, fc->bucket_counter, + fc->max_queue_depth, fc->queue_depth); + } } static void dump_bssgp(struct vty *vty, int stats) -- cgit v1.2.3