agch: Manage AGCH queue length

Currently, the AGCH queue length is not limited. This can lead to
large delays and network malfunction if there are many IMM.ASS.REJ
messages.

This patch adds two features:
- Don't accept msgs from the RSL layer when the queue is way too
  full (safety measure, mainly if bts_ccch_copy_msg() is not being
  called by the L1 layer, currently hard coded to 1000 messages)
- Selectively drop IMM.ASS.REJ from the queue output depending on the
  queue length

Ticket: SYS#224
Sponsored-by: On-Waves ehf

4 files changed, 112 insertions, 10 deletions

diff --git a/include/osmo-bts/gsm_data.h b/include/osmo-bts/gsm_data.h
index b1399034..c7a0fc61 100644
--- a/include/osmo-bts/gsm_data.h
+++ b/include/osmo-bts/gsm_data.h
@@ -7,6 +7,11 @@
 
 #include <osmo-bts/paging.h>
 
+#define GSM_BTS_AGCH_QUEUE_THRESH_LEVEL_DEFAULT 41
+#define GSM_BTS_AGCH_QUEUE_THRESH_LEVEL_DISABLE 999999
+#define GSM_BTS_AGCH_QUEUE_LOW_LEVEL_DEFAULT 41
+#define GSM_BTS_AGCH_QUEUE_HIGH_LEVEL_DEFAULT 91
+
 struct pcu_sock_state;
 
 struct gsm_network {
@@ -54,6 +59,10 @@ struct gsm_bts_role_bts {
 	int agch_queue_length;
 	int agch_max_queue_length;
 
+	int agch_queue_thresh_level;	/* Cleanup threshold in percent of max len */
+	int agch_queue_low_level;	/* Low water mark in percent of max len */
+	int agch_queue_high_level;	/* High water mark in percent of max len */
+
 	/* TODO: Use a rate counter group instead */
 	uint64_t agch_queue_dropped_msgs;
 	uint64_t agch_queue_merged_msgs;
diff --git a/src/common/bts.c b/src/common/bts.c
index 211bbbfa..d456f7fb 100644
--- a/src/common/bts.c
+++ b/src/common/bts.c
@@ -89,6 +89,14 @@ int bts_init(struct gsm_bts *bts)
 	INIT_LLIST_HEAD(&btsb->agch_queue);
 	btsb->agch_queue_length = 0;
 
+	/* enable management with default levels,
+	 * raise threshold to GSM_BTS_AGCH_QUEUE_THRESH_LEVEL_DISABLE to
+	 * disable this feature.
+	 */
+	btsb->agch_queue_low_level = GSM_BTS_AGCH_QUEUE_LOW_LEVEL_DEFAULT;
+	btsb->agch_queue_high_level = GSM_BTS_AGCH_QUEUE_HIGH_LEVEL_DEFAULT;
+	btsb->agch_queue_thresh_level = GSM_BTS_AGCH_QUEUE_THRESH_LEVEL_DEFAULT;
+
 	/* configurable via VTY */
 	btsb->paging_state = paging_init(btsb, 200, 0);
 
@@ -301,6 +309,18 @@ void bts_update_agch_max_queue_length(struct gsm_bts *bts)
 int bts_agch_enqueue(struct gsm_bts *bts, struct msgb *msg)
 {
 	struct gsm_bts_role_bts *btsb = bts_role_bts(bts);
+	int hard_limit = 1000;
+
+	if (btsb->agch_queue_length > hard_limit) {
+		LOGP(DSUM, LOGL_ERROR,
+		     "AGCH: too many messages in queue, "
+		     "refusing message type 0x%02x, length = %d/%d\n",
+		     ((struct gsm48_imm_ass *)msgb_l3(msg))->msg_type,
+		     btsb->agch_queue_length, btsb->agch_max_queue_length);
+
+		btsb->agch_queue_rejected_msgs++;
+		return -ENOMEM;
+	}
 
 	msgb_enqueue(&btsb->agch_queue, msg);
 	btsb->agch_queue_length++;
@@ -319,26 +339,95 @@ struct msgb *bts_agch_dequeue(struct gsm_bts *bts)
 	return msg;
 }
 
+/*
+ * Remove lower prio messages if the queue has grown too long.
+ *
+ * \return 0 iff the number of messages in the queue would fit into the AGCH
+ *         reserved part of the CCCH.
+ */
+static void compact_agch_queue(struct gsm_bts *bts)
+{
+	struct gsm_bts_role_bts *btsb = bts_role_bts(bts);
+	struct msgb *msg, *msg2;
+	int max_len, slope, offs;
+	int level_low = btsb->agch_queue_low_level;
+	int level_high = btsb->agch_queue_high_level;
+	int level_thres = btsb->agch_queue_thresh_level;
+
+	max_len = btsb->agch_max_queue_length;
+
+	if (max_len == 0)
+		max_len = 1;
+
+	/* TODO: Make the constants configurable */
+	if (btsb->agch_queue_length < max_len * level_thres / 100)
+		return;
+
+	/* p^
+	 * 1+      /'''''
+	 *  |     /
+	 *  |    /
+	 * 0+---/--+----+--> Q length
+	 *    low high max_len
+	 */
+
+	offs = max_len * level_low / 100;
+	if (level_high > level_low)
+		slope = 0x10000 * 100 / (level_high - level_low);
+	else
+		slope = 0x10000 * max_len; /* p_drop >= 1 if len > offs */
+
+	llist_for_each_entry_safe(msg, msg2, &btsb->agch_queue, list) {
+		struct gsm48_imm_ass *imm_ass_cmd = msgb_l3(msg);
+		int p_drop;
+
+		if (imm_ass_cmd->msg_type != GSM48_MT_RR_IMM_ASS_REJ)
+			return;
+
+		/* IMMEDIATE ASSIGN REJECT */
+
+		p_drop = (btsb->agch_queue_length - offs) * slope / max_len;
+
+		if ((random() & 0xffff) >= p_drop)
+			return;
+
+		llist_del(&msg->list);
+		btsb->agch_queue_length--;
+		msgb_free(msg);
+
+		btsb->agch_queue_dropped_msgs++;
+	}
+	return;
+}
+
 int bts_ccch_copy_msg(struct gsm_bts *bts, uint8_t *out_buf, struct gsm_time *gt,
 		      int is_ag_res)
 {
-	struct msgb *msg;
+	struct msgb *msg = NULL;
 	struct gsm_bts_role_bts *btsb = bts->role;
-	int rc;
+	int rc = 0;
+	int is_empty = 1;
+
+	/* Do queue house keeping.
+	 * This needs to be done every time a CCCH message is requested, since
+	 * the queue max length is calculated based on the CCCH block rate and
+	 * PCH messages also reduce the drain of the AGCH queue.
+	 */
+	compact_agch_queue(bts);
 
-	if (!is_ag_res) {
-		int is_empty = 1;
+	/* Check for paging messages first if this is PCH */
+	if (!is_ag_res)
 		rc = paging_gen_msg(btsb->paging_state, out_buf, gt, &is_empty);
 
-		if (!is_empty)
-			return rc;
-	}
+	/* Check whether the block may be overwritten */
+	if (!is_empty)
+		return rc;
 
-	/* special queue of messages from IMM ASS CMD */
 	msg = bts_agch_dequeue(bts);
 	if (!msg)
-		return 0;
+		return rc;
 
+	/* Copy AGCH message */
 	memcpy(out_buf, msgb_l3(msg), msgb_l3len(msg));
 	rc = msgb_l3len(msg);
 	msgb_free(msg);
diff --git a/tests/agch/agch_test.c b/tests/agch/agch_test.c
index 7a154874..6d00ed86 100644
--- a/tests/agch/agch_test.c
+++ b/tests/agch/agch_test.c
@@ -122,6 +122,10 @@ static void test_agch_queue(void)
 	printf("Testing AGCH messages queue handling.\n");
 	btsb->agch_max_queue_length = 32;
 
+	btsb->agch_queue_low_level = 30;
+	btsb->agch_queue_high_level = 30;
+	btsb->agch_queue_thresh_level = 60;
+
 	for (round = 1; round <= num_rounds; round++) {
 		for (idx = 0; idx < num_ima_per_round; idx++) {
 			msg = msgb_alloc(GSM_MACBLOCK_LEN, __FUNCTION__);
diff --git a/tests/agch/agch_test.ok b/tests/agch/agch_test.ok
index f781383f..445d6840 100644
--- a/tests/agch/agch_test.ok
+++ b/tests/agch/agch_test.ok
@@ -19,5 +19,5 @@ T		BCCH slots
 50	28	14	28	28	28
 Testing AGCH messages queue handling.
 AGCH filled: count 720, imm.ass 80, imm.ass.rej 640 (refs 640), queue limit 32, occupied 720, dropped 0, merged 0, rejected 0, ag-res 0, non-res 0
-AGCH drained: multiframes 241, imm.ass 80, imm.ass.rej 641 (refs 641), queue limit 32, occupied 0, dropped 0, merged 0, rejected 0, ag-res 240, non-res 480
+AGCH drained: multiframes 33, imm.ass 80, imm.ass.rej 17 (refs 17), queue limit 32, occupied 0, dropped 624, merged 0, rejected 0, ag-res 32, non-res 64
 Success