Merge branch 'jerlbeck/agch-queue'

13 files changed, 714 insertions, 11 deletions

diff --git a/configure.ac b/configure.ac
index 34110179..ff46b5ab 100644
--- a/configure.ac
+++ b/configure.ac
@@ -59,6 +59,7 @@ AC_OUTPUT(
     include/osmo-bts/Makefile
     tests/Makefile
     tests/paging/Makefile
+    tests/agch/Makefile
     tests/cipher/Makefile
     tests/sysmobts/Makefile
     Makefile)
diff --git a/include/osmo-bts/bts.h b/include/osmo-bts/bts.h
index 49ef617c..d27eef0e 100644
--- a/include/osmo-bts/bts.h
+++ b/include/osmo-bts/bts.h
@@ -26,6 +26,8 @@ void bts_setup_slot(struct gsm_bts_trx_ts *slot, uint8_t comb);
 
 int bts_agch_enqueue(struct gsm_bts *bts, struct msgb *msg);
 struct msgb *bts_agch_dequeue(struct gsm_bts *bts);
+void bts_update_agch_max_queue_length(struct gsm_bts *bts);
+int bts_agch_max_queue_length(int T, int bcch_conf);
 int bts_ccch_copy_msg(struct gsm_bts *bts, uint8_t *out_buf, struct gsm_time *gt,
 		      int is_ag_res);
 
diff --git a/include/osmo-bts/gsm_data.h b/include/osmo-bts/gsm_data.h
index aee56a9a..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 {
@@ -48,8 +53,23 @@ struct gsm_bts_role_bts {
 	} load;
 	uint8_t ny1;
 	uint8_t max_ta;
+
+	/* AGCH queuing */
 	struct llist_head agch_queue;
 	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;
+	uint64_t agch_queue_rejected_msgs;
+	uint64_t agch_queue_agch_msgs;
+	uint64_t agch_queue_pch_msgs;
+
 	struct paging_state *paging_state;
 	char *bsc_oml_host;
 	unsigned int rtp_jitter_buf_ms;
diff --git a/include/osmo-bts/paging.h b/include/osmo-bts/paging.h
index d31f5c12..38accd72 100644
--- a/include/osmo-bts/paging.h
+++ b/include/osmo-bts/paging.h
@@ -40,7 +40,8 @@ int paging_add_imm_ass(struct paging_state *ps, const uint8_t *data,
                        uint8_t len);
 
 /* generate paging message for given gsm time */
-int paging_gen_msg(struct paging_state *ps, uint8_t *out_buf, struct gsm_time *gt);
+int paging_gen_msg(struct paging_state *ps, uint8_t *out_buf, struct gsm_time *gt,
+		   int *is_empty);
 
 
 /* inspection methods below */
diff --git a/src/common/bts.c b/src/common/bts.c
index 7bbf5870..856968ef 100644
--- a/src/common/bts.c
+++ b/src/common/bts.c
@@ -42,6 +42,7 @@
 #include <osmo-bts/bts_model.h>
 #include <osmo-bts/rsl.h>
 #include <osmo-bts/oml.h>
+#include <osmo-bts/signal.h>
 
 
 struct gsm_network bts_gsmnet = {
@@ -51,11 +52,32 @@ struct gsm_network bts_gsmnet = {
 
 void *tall_bts_ctx;
 
+/* Table 3.1 TS 04.08: Values of parameter S */
+static const uint8_t tx_integer[] = {
+	3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 20, 25, 32, 50,
+};
+
+static const uint8_t s_values[][2] = {
+	{ 55, 41 }, { 76, 52 }, { 109, 58 }, { 163, 86 }, { 217, 115 },
+};
+
+static int bts_signal_cbfn(unsigned int subsys, unsigned int signal,
+			   void *hdlr_data, void *signal_data)
+{
+	if (subsys == SS_GLOBAL && signal == S_NEW_SYSINFO) {
+		struct gsm_bts *bts = signal_data;
+
+		bts_update_agch_max_queue_length(bts);
+	}
+	return 0;
+}
+
 int bts_init(struct gsm_bts *bts)
 {
 	struct gsm_bts_role_bts *btsb;
 	struct gsm_bts_trx *trx;
 	int rc;
+	static int initialized = 0;
 
 	/* add to list of BTSs */
 	llist_add_tail(&bts->list, &bts_gsmnet.bts_list);
@@ -67,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);
 
@@ -110,6 +140,11 @@ int bts_init(struct gsm_bts *bts)
 
 	bts_gsmnet.num_bts++;
 
+	if (!initialized) {
+		osmo_signal_register_handler(SS_GLOBAL, bts_signal_cbfn, NULL);
+		initialized = 1;
+	}
+
 	return rc;
 }
 
@@ -209,11 +244,224 @@ int lchan_init_lapdm(struct gsm_lchan *lchan)
 	return 0;
 }
 
+#define CCCH_RACH_RATIO_COMBINED256      (256*1/9)
+#define CCCH_RACH_RATIO_SEPARATE256      (256*10/55)
+
+int bts_agch_max_queue_length(int T, int bcch_conf)
+{
+	int S, ccch_rach_ratio256, i;
+	int T_group = 0;
+	int is_ccch_comb = 0;
+
+	if (bcch_conf == RSL_BCCH_CCCH_CONF_1_C)
+		is_ccch_comb = 1;
+
+	/*
+	 * The calculation is based on the ratio of the number RACH slots and
+	 * CCCH blocks per time:
+	 *   Lmax = (T + 2*S) / R_RACH * R_CCCH
+	 * where
+	 *   T3126_min = (T + 2*S) / R_RACH, as defined in GSM 04.08, 11.1.1
+	 *   R_RACH is the RACH slot rate (e.g. RACHs per multiframe)
+	 *   R_CCCH is the CCCH block rate (same time base like R_RACH)
+	 *   S and T are defined in GSM 04.08, 3.3.1.1.2
+	 * The ratio is mainly influenced by the downlink only channels
+	 * (BCCH, FCCH, SCH, CBCH) that can not be used for CCCH.
+	 * An estimation with an error of < 10% is used:
+	 *   ~ 1/9 if CCCH is combined with SDCCH, and
+	 *   ~ 1/5.5 otherwise.
+	 */
+	ccch_rach_ratio256 = is_ccch_comb ?
+		CCCH_RACH_RATIO_COMBINED256 :
+		CCCH_RACH_RATIO_SEPARATE256;
+
+	for (i = 0; i < ARRAY_SIZE(tx_integer); i++) {
+		if (tx_integer[i] == T) {
+			T_group = i % 5;
+			break;
+		}
+	}
+	S = s_values[T_group][is_ccch_comb];
+
+	return (T + 2 * S) * ccch_rach_ratio256 / 256;
+}
+
+void bts_update_agch_max_queue_length(struct gsm_bts *bts)
+{
+	struct gsm_bts_role_bts *btsb = bts_role_bts(bts);
+	struct gsm48_system_information_type_3 *si3;
+	int old_max_length = btsb->agch_max_queue_length;
+
+	if (!(bts->si_valid & (1<<SYSINFO_TYPE_3)))
+		return;
+
+	si3 = GSM_BTS_SI(bts, SYSINFO_TYPE_3);
+
+	btsb->agch_max_queue_length =
+		bts_agch_max_queue_length(si3->rach_control.tx_integer,
+					  si3->control_channel_desc.ccch_conf);
+
+	if (btsb->agch_max_queue_length != old_max_length)
+		LOGP(DRSL, LOGL_INFO, "Updated AGCH max queue length to %d\n",
+		     btsb->agch_max_queue_length);
+}
+
+#define REQ_REFS_PER_IMM_ASS_REJ 4
+static int store_imm_ass_rej_refs(struct gsm48_imm_ass_rej *rej,
+				    struct gsm48_req_ref *req_refs,
+				    uint8_t *wait_inds,
+				    int count)
+{
+	switch (count) {
+	case 0:
+		/* TODO: Warning ? */
+		return 0;
+	default:
+		count = 4;
+		rej->req_ref4 = req_refs[3];
+		rej->wait_ind4 = wait_inds[3];
+		/* fall through */
+	case 3:
+		rej->req_ref3 = req_refs[2];
+		rej->wait_ind3 = wait_inds[2];
+		/* fall through */
+	case 2:
+		rej->req_ref2 = req_refs[1];
+		rej->wait_ind2 = wait_inds[1];
+		/* fall through */
+	case 1:
+		rej->req_ref1 = req_refs[0];
+		rej->wait_ind1 = wait_inds[0];
+		break;
+	}
+
+	switch (count) {
+	case 1:
+		rej->req_ref2 = req_refs[0];
+		rej->wait_ind2 = wait_inds[0];
+		/* fall through */
+	case 2:
+		rej->req_ref3 = req_refs[0];
+		rej->wait_ind3 = wait_inds[0];
+		/* fall through */
+	case 3:
+		rej->req_ref4 = req_refs[0];
+		rej->wait_ind4 = wait_inds[0];
+		/* fall through */
+	default:
+		break;
+	}
+
+	return count;
+}
+
+static int extract_imm_ass_rej_refs(struct gsm48_imm_ass_rej *rej,
+				    struct gsm48_req_ref *req_refs,
+				    uint8_t *wait_inds)
+{
+	int count = 0;
+	req_refs[count] = rej->req_ref1;
+	wait_inds[count] = rej->wait_ind1;
+	count++;
+
+	if (memcmp(&rej->req_ref1, &rej->req_ref2, sizeof(rej->req_ref2))) {
+		req_refs[count] = rej->req_ref2;
+		wait_inds[count] = rej->wait_ind2;
+		count++;
+	}
+
+	if (memcmp(&rej->req_ref1, &rej->req_ref3, sizeof(rej->req_ref3)) &&
+	    memcmp(&rej->req_ref2, &rej->req_ref3, sizeof(rej->req_ref3))) {
+		req_refs[count] = rej->req_ref3;
+		wait_inds[count] = rej->wait_ind3;
+		count++;
+	}
+
+	if (memcmp(&rej->req_ref1, &rej->req_ref4, sizeof(rej->req_ref4)) &&
+	    memcmp(&rej->req_ref2, &rej->req_ref4, sizeof(rej->req_ref4)) &&
+	    memcmp(&rej->req_ref3, &rej->req_ref4, sizeof(rej->req_ref4))) {
+		req_refs[count] = rej->req_ref4;
+		wait_inds[count] = rej->wait_ind4;
+		count++;
+	}
+
+	return count;
+}
+
+static int try_merge_imm_ass_rej(struct gsm48_imm_ass_rej *old_rej,
+				 struct gsm48_imm_ass_rej *new_rej)
+{
+	struct gsm48_req_ref req_refs[2 * REQ_REFS_PER_IMM_ASS_REJ];
+	uint8_t wait_inds[2 * REQ_REFS_PER_IMM_ASS_REJ];
+	int count = 0;
+	int stored = 0;
+
+	if (new_rej->msg_type != GSM48_MT_RR_IMM_ASS_REJ)
+		return 0;
+	if (old_rej->msg_type != GSM48_MT_RR_IMM_ASS_REJ)
+		return 0;
+
+	/* GSM 08.58, 5.7
+	 * -> The BTS may combine serveral IMM.ASS.REJ messages
+	 * -> Identical request refs in one message may be squeezed
+	 *
+	 * GSM 04.08, 9.1.20.2
+	 * -> Request ref and wait ind are duplicated to fill the message
+	 */
+
+	/* Extract all entries */
+	count = extract_imm_ass_rej_refs(old_rej,
+					 &req_refs[count], &wait_inds[count]);
+	if (count == REQ_REFS_PER_IMM_ASS_REJ)
+		return 0;
+
+	count += extract_imm_ass_rej_refs(new_rej,
+					  &req_refs[count], &wait_inds[count]);
+
+	/* Store entries into old message */
+	stored = store_imm_ass_rej_refs(old_rej,
+					&req_refs[stored], &wait_inds[stored],
+					count);
+	count -= stored;
+	if (count == 0)
+		return 1;
+
+	/* Store remaining entries into new message */
+	stored += store_imm_ass_rej_refs(new_rej,
+					 &req_refs[stored], &wait_inds[stored],
+					 count);
+	return 0;
+}
+
 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;
+	struct gsm48_imm_ass_rej *imm_ass_cmd = msgb_l3(msg);
+
+	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;
+	}
+
+	if (btsb->agch_queue_length > 0) {
+		struct msgb *last_msg =
+			llist_entry(btsb->agch_queue.prev, struct msgb, list);
+		struct gsm48_imm_ass_rej *last_imm_ass_rej = msgb_l3(last_msg);
+
+		if (try_merge_imm_ass_rej(last_imm_ass_rej, imm_ass_cmd)) {
+			btsb->agch_queue_merged_msgs++;
+			msgb_free(msg);
+			return 0;
+		}
+	}
 
-	/* FIXME: implement max queue length */
 	msgb_enqueue(&btsb->agch_queue, msg);
 	btsb->agch_queue_length++;
 
@@ -231,25 +479,104 @@ 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);
 
+	/* Check for paging messages first if this is PCH */
 	if (!is_ag_res)
-		return paging_gen_msg(btsb->paging_state, out_buf, gt);
+		rc = paging_gen_msg(btsb->paging_state, out_buf, gt, &is_empty);
+
+	/* 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);
 
+	if (is_ag_res)
+		btsb->agch_queue_agch_msgs++;
+	else
+		btsb->agch_queue_pch_msgs++;
+
 	return rc;
 }
 
diff --git a/src/common/paging.c b/src/common/paging.c
index 7c71c6f8..f75f12dc 100644
--- a/src/common/paging.c
+++ b/src/common/paging.c
@@ -377,12 +377,14 @@ static void sort_pr_tmsi_imsi(struct paging_record *pr[], unsigned int n)
 }
 
 /* generate paging message for given gsm time */
-int paging_gen_msg(struct paging_state *ps, uint8_t *out_buf, struct gsm_time *gt)
+int paging_gen_msg(struct paging_state *ps, uint8_t *out_buf, struct gsm_time *gt,
+		   int *is_empty)
 {
 	struct llist_head *group_q;
 	int group;
 	int len;
 
+	*is_empty = 0;
 	ps->btsb->load.ccch.pch_total += 1;
 
 	group = get_pag_subch_nr(ps, gt);
@@ -400,6 +402,7 @@ int paging_gen_msg(struct paging_state *ps, uint8_t *out_buf, struct gsm_time *g
 		//DEBUGP(DPAG, "Tx PAGING TYPE 1 (empty)\n");
 		len = fill_paging_type_1(out_buf, empty_id_lv, 0,
 					 NULL, 0);
+		*is_empty = 1;
 	} else {
 		struct paging_record *pr[4];
 		unsigned int num_pr = 0, imm_ass = 0;
diff --git a/src/common/vty.c b/src/common/vty.c
index 5eddc8df..99ad9739 100644
--- a/src/common/vty.c
+++ b/src/common/vty.c
@@ -189,6 +189,12 @@ static void config_write_bts_single(struct vty *vty, struct gsm_bts *bts)
 		VTY_NEWLINE);
 	vty_out(vty, " paging lifetime %u%s", paging_get_lifetime(btsb->paging_state),
 		VTY_NEWLINE);
+	if (btsb->agch_queue_thresh_level != GSM_BTS_AGCH_QUEUE_THRESH_LEVEL_DEFAULT
+		 || btsb->agch_queue_low_level != GSM_BTS_AGCH_QUEUE_LOW_LEVEL_DEFAULT
+		 || btsb->agch_queue_high_level != GSM_BTS_AGCH_QUEUE_HIGH_LEVEL_DEFAULT)
+		vty_out(vty, " agch-queue-mgmt threshold %d low %d high %d%s",
+			btsb->agch_queue_thresh_level, btsb->agch_queue_low_level,
+			btsb->agch_queue_high_level, VTY_NEWLINE);
 
 	bts_model_config_write_bts(vty, bts);
 
@@ -355,6 +361,41 @@ DEFUN(cfg_bts_paging_lifetime,
 	return CMD_SUCCESS;
 }
 
+#define AGCH_QUEUE_STR "AGCH queue mgmt\n"
+
+DEFUN(cfg_bts_agch_queue_mgmt_params,
+	cfg_bts_agch_queue_mgmt_params_cmd,
+	"agch-queue-mgmt threshold <0-100> low <0-100> high <0-100000>",
+	AGCH_QUEUE_STR
+	"Threshold to start cleanup\nin %% of the maximum queue length\n"
+	"Low water mark for cleanup\nin %% of the maximum queue length\n"
+	"High water mark for cleanup\nin %% of the maximum queue length\n")
+{
+	struct gsm_bts *bts = vty->index;
+	struct gsm_bts_role_bts *btsb = bts_role_bts(bts);
+
+	btsb->agch_queue_thresh_level = atoi(argv[0]);
+	btsb->agch_queue_low_level = atoi(argv[1]);
+	btsb->agch_queue_high_level = atoi(argv[2]);
+
+	return CMD_SUCCESS;
+}
+
+DEFUN(cfg_bts_agch_queue_mgmt_default,
+	cfg_bts_agch_queue_mgmt_default_cmd,
+	"agch-queue-mgmt default",
+	AGCH_QUEUE_STR
+	"Reset clean parameters to default values\n")
+{
+	struct gsm_bts *bts = vty->index;
+	struct gsm_bts_role_bts *btsb = bts_role_bts(bts);
+
+	btsb->agch_queue_thresh_level = GSM_BTS_AGCH_QUEUE_THRESH_LEVEL_DEFAULT;
+	btsb->agch_queue_low_level = GSM_BTS_AGCH_QUEUE_LOW_LEVEL_DEFAULT;
+	btsb->agch_queue_high_level = GSM_BTS_AGCH_QUEUE_HIGH_LEVEL_DEFAULT;
+
+	return CMD_SUCCESS;
+}
 
 
 /* ======================================================================
@@ -390,6 +431,14 @@ static void bts_dump_vty(struct vty *vty, struct gsm_bts *bts)
 	vty_out(vty, "  Paging: Queue size %u, occupied %u, lifetime %us%s",
 		paging_get_queue_max(btsb->paging_state), paging_queue_length(btsb->paging_state),
 		paging_get_lifetime(btsb->paging_state), VTY_NEWLINE);
+	vty_out(vty, "  AGCH: Queue limit %u, occupied %d, "
+		"dropped %llu, merged %llu, rejected %llu, "
+		"ag-res %llu, non-res %llu%s",
+		btsb->agch_max_queue_length, btsb->agch_queue_length,
+		btsb->agch_queue_dropped_msgs, btsb->agch_queue_merged_msgs,
+		btsb->agch_queue_rejected_msgs, btsb->agch_queue_agch_msgs,
+		btsb->agch_queue_pch_msgs,
+		VTY_NEWLINE);
 #if 0
 	vty_out(vty, "  Paging: %u pending requests, %u free slots%s",
 		paging_pending_requests_nr(bts),
@@ -519,6 +568,8 @@ int bts_vty_init(const struct log_info *cat)
 	install_element(BTS_NODE, &cfg_no_description_cmd);
 	install_element(BTS_NODE, &cfg_bts_paging_queue_size_cmd);
 	install_element(BTS_NODE, &cfg_bts_paging_lifetime_cmd);
+	install_element(BTS_NODE, &cfg_bts_agch_queue_mgmt_default_cmd);
+	install_element(BTS_NODE, &cfg_bts_agch_queue_mgmt_params_cmd);
 
 	/* add and link to TRX config node */
 	install_element(BTS_NODE, &cfg_bts_trx_cmd);
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 5fb128f1..b32241b9 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -1,4 +1,4 @@
-SUBDIRS = paging cipher sysmobts
+SUBDIRS = paging cipher sysmobts agch
 
 # The `:;' works around a Bash 3.2 bug when the output is not writeable.
 $(srcdir)/package.m4: $(top_srcdir)/configure.ac
diff --git a/tests/agch/Makefile.am b/tests/agch/Makefile.am
new file mode 100644
index 00000000..a0c5eeda
--- /dev/null
+++ b/tests/agch/Makefile.am
@@ -0,0 +1,8 @@
+AM_CPPFLAGS = $(all_includes) -I$(top_srcdir)/include -I$(OPENBSC_INCDIR)
+AM_CFLAGS = -Wall $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGSM_CFLAGS) $(LIBOSMOVTY_CFLAGS) $(LIBOSMOTRAU_CFLAGS)
+LDADD = $(LIBOSMOCORE_LIBS) $(LIBOSMOGSM_LIBS) $(LIBOSMOVTY_LIBS) $(LIBOSMOTRAU_LIBS) $(LIBOSMOABIS_LIBS) -lortp
+noinst_PROGRAMS = agch_test
+EXTRA_DIST = agch_test.ok
+
+agch_test_SOURCES = agch_test.c $(srcdir)/../stubs.c
+agch_test_LDADD = $(top_builddir)/src/common/libbts.a $(LDADD)
diff --git a/tests/agch/agch_test.c b/tests/agch/agch_test.c
new file mode 100644
index 00000000..6d00ed86
--- /dev/null
+++ b/tests/agch/agch_test.c
@@ -0,0 +1,248 @@
+/* testing the agch code */
+
+/* (C) 2011 by Holger Hans Peter Freyther
+ * (C) 2014 by sysmocom s.f.m.c. GmbH
+ *
+ * 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 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 <osmocom/core/talloc.h>
+
+#include <osmo-bts/bts.h>
+#include <osmo-bts/logging.h>
+#include <osmo-bts/gsm_data.h>
+
+#include <unistd.h>
+
+static struct gsm_bts *bts;
+static struct gsm_bts_role_bts *btsb;
+int pcu_direct = 0;
+
+static const uint8_t static_ilv[] = {
+	0x08, 0x59, 0x51, 0x30, 0x99, 0x00, 0x00, 0x00, 0x19
+};
+
+static int count_imm_ass_rej_refs(struct gsm48_imm_ass_rej *rej)
+{
+	int count = 0;
+	count++;
+
+	if (memcmp(&rej->req_ref1, &rej->req_ref2, sizeof(rej->req_ref2))) {
+		count++;
+	}
+
+	if (memcmp(&rej->req_ref1, &rej->req_ref3, sizeof(rej->req_ref3))
+	    && memcmp(&rej->req_ref2, &rej->req_ref3, sizeof(rej->req_ref3))) {
+		count++;
+	}
+
+	if (memcmp(&rej->req_ref1, &rej->req_ref4, sizeof(rej->req_ref4))
+	    && memcmp(&rej->req_ref2, &rej->req_ref4, sizeof(rej->req_ref4))
+	    && memcmp(&rej->req_ref3, &rej->req_ref4, sizeof(rej->req_ref4))) {
+		count++;
+	}
+
+	return count;
+}
+
+static void put_imm_ass_rej(struct msgb *msg, int idx, uint8_t wait_ind)
+{
+	/* GSM CCCH - Immediate Assignment Reject */
+	static const unsigned char gsm_a_ccch_data[23] = {
+		0x4d, 0x06, 0x3a, 0x03, 0x25, 0x00, 0x00, 0x0a,
+		0x25, 0x00, 0x00, 0x0a, 0x25, 0x00, 0x00, 0x0a,
+		0x25, 0x00, 0x00, 0x0a, 0x2b, 0x2b, 0x2b
+	};
+
+	struct gsm48_imm_ass_rej *rej;
+	msg->l3h = msgb_put(msg, sizeof(gsm_a_ccch_data));
+	rej = (struct gsm48_imm_ass_rej *)msg->l3h;
+	memmove(msg->l3h, gsm_a_ccch_data, sizeof(gsm_a_ccch_data));
+
+	rej->req_ref1.t1 = idx;
+	rej->wait_ind1 = wait_ind;
+
+	rej->req_ref2.t1 = idx;
+	rej->req_ref3.t1 = idx;
+	rej->req_ref4.t1 = idx;
+}
+
+static void put_imm_ass(struct msgb *msg, int idx)
+{
+	/* GSM CCCH - Immediate Assignment */
+	static const unsigned char gsm_a_ccch_data[23] = {
+		0x2d, 0x06, 0x3f, 0x03, 0x0c, 0xe3, 0x69, 0x25,
+		0x00, 0x00, 0x00, 0x00, 0x2b, 0x2b, 0x2b, 0x2b,
+		0x2b, 0x2b, 0x2b, 0x2b, 0x2b, 0x2b, 0x2b
+	};
+
+	struct gsm48_imm_ass *ima;
+	msg->l3h = msgb_put(msg, sizeof(gsm_a_ccch_data));
+	ima = (struct gsm48_imm_ass *)msg->l3h;
+	memmove(msg->l3h, gsm_a_ccch_data, sizeof(gsm_a_ccch_data));
+
+	ima->req_ref.t1 = idx;
+}
+
+static void test_agch_queue(void)
+{
+	int rc;
+	uint8_t out_buf[GSM_MACBLOCK_LEN];
+	struct gsm_time g_time;
+	const int num_rounds = 40;
+	const int num_ima_per_round = 2;
+	const int num_rej_per_round = 16;
+
+	int round, idx;
+	int count = 0;
+	struct msgb *msg = NULL;
+	int multiframes = 0;
+	int imm_ass_count = 0;
+	int imm_ass_rej_count = 0;
+	int imm_ass_rej_ref_count = 0;
+
+	g_time.fn = 0;
+	g_time.t1 = 0;
+	g_time.t2 = 0;
+	g_time.t3 = 6;
+
+	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__);
+			put_imm_ass(msg, ++count);
+			bts_agch_enqueue(bts, msg);
+			imm_ass_count++;
+		}
+		for (idx = 0; idx < num_rej_per_round; idx++) {
+			msg = msgb_alloc(GSM_MACBLOCK_LEN, __FUNCTION__);
+			put_imm_ass_rej(msg, ++count, 10);
+			bts_agch_enqueue(bts, msg);
+			imm_ass_rej_count++;
+			imm_ass_rej_ref_count++;
+		}
+	}
+
+	printf("AGCH filled: count %u, imm.ass %d, imm.ass.rej %d (refs %d), "
+	       "queue limit %u, occupied %d, "
+	       "dropped %llu, merged %llu, rejected %llu, "
+	       "ag-res %llu, non-res %llu\n",
+	       count, imm_ass_count, imm_ass_rej_count, imm_ass_rej_ref_count,
+	       btsb->agch_max_queue_length, btsb->agch_queue_length,
+	       btsb->agch_queue_dropped_msgs, btsb->agch_queue_merged_msgs,
+	       btsb->agch_queue_rejected_msgs, btsb->agch_queue_agch_msgs,
+	       btsb->agch_queue_pch_msgs);
+
+	imm_ass_count = 0;
+	imm_ass_rej_count = 0;
+	imm_ass_rej_ref_count = 0;
+
+	for (idx = 0; 1; idx++) {
+		struct gsm48_imm_ass *ima;
+		int is_agch = (idx % 3) == 0; /* 1 AG reserved, 2 PCH */
+		if (is_agch)
+			multiframes++;
+
+		rc = bts_ccch_copy_msg(bts, out_buf, &g_time, is_agch);
+		ima = (struct gsm48_imm_ass *)out_buf;
+		switch (ima->msg_type) {
+		case GSM48_MT_RR_IMM_ASS:
+			imm_ass_count++;
+			break;
+		case GSM48_MT_RR_IMM_ASS_REJ:
+			imm_ass_rej_count++;
+			imm_ass_rej_ref_count +=
+				count_imm_ass_rej_refs((struct gsm48_imm_ass_rej *)ima);
+			break;
+		default:
+			break;
+		}
+		if (is_agch && rc <= 0)
+			break;
+
+	}
+
+	printf("AGCH drained: multiframes %u, imm.ass %d, imm.ass.rej %d (refs %d), "
+	       "queue limit %u, occupied %d, "
+	       "dropped %llu, merged %llu, rejected %llu, "
+	       "ag-res %llu, non-res %llu\n",
+	       multiframes, imm_ass_count, imm_ass_rej_count, imm_ass_rej_ref_count,
+	       btsb->agch_max_queue_length, btsb->agch_queue_length,
+	       btsb->agch_queue_dropped_msgs, btsb->agch_queue_merged_msgs,
+	       btsb->agch_queue_rejected_msgs, btsb->agch_queue_agch_msgs,
+	       btsb->agch_queue_pch_msgs);
+}
+
+static void test_agch_queue_length_computation(void)
+{
+	static const int ccch_configs[] = {
+		RSL_BCCH_CCCH_CONF_1_NC,
+		RSL_BCCH_CCCH_CONF_1_C,
+		RSL_BCCH_CCCH_CONF_2_NC,
+		RSL_BCCH_CCCH_CONF_3_NC,
+		RSL_BCCH_CCCH_CONF_4_NC,
+	};
+	static const uint8_t tx_integer[] = {
+		3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 20, 25, 32, 50,
+	};
+
+	int T_idx, c_idx, max_len;
+
+	printf("Testing AGCH queue length computation.\n");
+
+	printf("T\t\tBCCH slots\n");
+	printf("\t1(NC)\t1(C)\t2(NC)\t3(NC)\t4(NC)\n");
+	for (T_idx = 0; T_idx < ARRAY_SIZE(tx_integer); T_idx++) {
+		printf("%d", tx_integer[T_idx]);
+		for (c_idx = 0; c_idx < ARRAY_SIZE(ccch_configs); c_idx++) {
+			max_len = bts_agch_max_queue_length(tx_integer[T_idx],
+							    ccch_configs[c_idx]);
+			printf("\t%d", max_len);
+		}
+		printf("\n");
+	}
+}
+
+int main(int argc, char **argv)
+{
+	void *tall_msgb_ctx;
+
+	tall_bts_ctx = talloc_named_const(NULL, 1, "OsmoBTS context");
+	tall_msgb_ctx = talloc_named_const(tall_bts_ctx, 1, "msgb");
+	msgb_set_talloc_ctx(tall_msgb_ctx);
+
+	bts_log_init(NULL);
+
+	bts = gsm_bts_alloc(tall_bts_ctx);
+	if (bts_init(bts) < 0) {
+		fprintf(stderr, "unable to open bts\n");
+		exit(1);
+	}
+
+	btsb = bts_role_bts(bts);
+	test_agch_queue_length_computation();
+	test_agch_queue();
+	printf("Success\n");
+
+	return 0;
+}
+
diff --git a/tests/agch/agch_test.ok b/tests/agch/agch_test.ok
new file mode 100644
index 00000000..49173a30
--- /dev/null
+++ b/tests/agch/agch_test.ok
@@ -0,0 +1,23 @@
+Testing AGCH queue length computation.
+T		BCCH slots
+	1(NC)	1(C)	2(NC)	3(NC)	4(NC)
+3	20	9	20	20	20
+4	28	11	28	28	28
+5	40	13	40	40	40
+6	59	19	59	59	59
+7	79	25	79	79	79
+8	21	9	21	21	21
+9	28	12	28	28	28
+10	40	13	40	40	40
+11	60	20	60	60	60
+12	80	26	80	80	80
+14	22	10	22	22	22
+16	30	13	30	30	30
+20	42	14	42	42	42
+25	63	21	63	63	63
+32	83	28	83	83	83
+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 240, dropped 0, merged 480, rejected 0, ag-res 0, non-res 0
+AGCH drained: multiframes 32, imm.ass 80, imm.ass.rej 12 (refs 48), queue limit 32, occupied 0, dropped 148, merged 480, rejected 0, ag-res 31, non-res 61
+Success
diff --git a/tests/paging/paging_test.c b/tests/paging/paging_test.c
index 95f1eba3..a6f8cfaf 100644
--- a/tests/paging/paging_test.c
+++ b/tests/paging/paging_test.c
@@ -47,6 +47,7 @@ static void test_paging_smoke(void)
 	int rc;
 	uint8_t out_buf[GSM_MACBLOCK_LEN];
 	struct gsm_time g_time;
+	int is_empty = -1;
 	printf("Testing that paging messages expire.\n");
 
 	/* add paging entry */
@@ -59,12 +60,22 @@ static void test_paging_smoke(void)
 	g_time.t1 = 0;
 	g_time.t2 = 0;
 	g_time.t3 = 6;
-	rc = paging_gen_msg(btsb->paging_state, out_buf, &g_time);
+	rc = paging_gen_msg(btsb->paging_state, out_buf, &g_time, &is_empty);
 	ASSERT_TRUE(rc == 13);
+	ASSERT_TRUE(is_empty == 0);
 
 	ASSERT_TRUE(paging_group_queue_empty(btsb->paging_state, 0));
 	ASSERT_TRUE(paging_queue_length(btsb->paging_state) == 0);
 
+	/* now test the empty queue */
+	g_time.fn = 0;
+	g_time.t1 = 0;
+	g_time.t2 = 0;
+	g_time.t3 = 6;
+	rc = paging_gen_msg(btsb->paging_state, out_buf, &g_time, &is_empty);
+	ASSERT_TRUE(rc == 6);
+	ASSERT_TRUE(is_empty == 1);
+
 	/*
 	 * TODO: test all the cases of different amount tmsi/imsi and check
 	 * if we fill the slots in a optimal way.
@@ -76,6 +87,7 @@ static void test_paging_sleep(void)
 	int rc;
 	uint8_t out_buf[GSM_MACBLOCK_LEN];
 	struct gsm_time g_time;
+	int is_empty = -1;
 	printf("Testing that paging messages expire with sleep.\n");
 
 	/* add paging entry */
@@ -91,8 +103,9 @@ static void test_paging_sleep(void)
 	g_time.t1 = 0;
 	g_time.t2 = 0;
 	g_time.t3 = 6;
-	rc = paging_gen_msg(btsb->paging_state, out_buf, &g_time);
+	rc = paging_gen_msg(btsb->paging_state, out_buf, &g_time, &is_empty);
 	ASSERT_TRUE(rc == 13);
+	ASSERT_TRUE(is_empty == 0);
 
 	ASSERT_TRUE(paging_group_queue_empty(btsb->paging_state, 0));
 	ASSERT_TRUE(paging_queue_length(btsb->paging_state) == 0);
diff --git a/tests/testsuite.at b/tests/testsuite.at
index 12974218..ec3021fd 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -7,6 +7,12 @@ cat $abs_srcdir/paging/paging_test.ok > expout
 AT_CHECK([$OSMO_QEMU $abs_top_builddir/tests/paging/paging_test], [], [expout], [ignore])
 AT_CLEANUP
 
+AT_SETUP([agch])
+AT_KEYWORDS([agch])
+cat $abs_srcdir/agch/agch_test.ok > expout
+AT_CHECK([$OSMO_QEMU $abs_top_builddir/tests/agch/agch_test], [], [expout], [ignore])
+AT_CLEANUP
+
 AT_SETUP([cipher])
 AT_KEYWORDS([cipher])
 cat $abs_srcdir/cipher/cipher_test.ok > expout