usched.c

wimax BS simulation code,implemented under linux.

/*
 * This piece of code is totally free. If any pitfalls found, 
 * please feel free to contact me at [e-mail]
 * THANKS A LOT!
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <netinet/in.h>
#include <semaphore.h>

#include "task.h"
#include "bitops.h"
#include "wxbuff.h"
#include "wxsched.h"


typedef struct cdmaallocieinfo_tag{
	struct list_head link;

	uint8_t frame_number_index;//the least four bits of the frame number
	uint8_t ranging_code;
	uint8_t ranging_symbol;
	uint8_t ranging_subchannel;
	uint8_t is_bwr;
}cdmaallocieinfo_t;

schedque_t g_ulschedque;

int32_t g_ulremain;	///3 symbols per slot in uplink 					/* unit in slot */
int32_t g_ulmapsize;


static int32_t ulbandwidth_alloc(sfattr_t *sf);
static void build_ulmap(wxbuff_t *map);
static void do_watchdog(uint32_t arga, void *argb);


int32_t usched_init()
{
	int32_t i;
	

	memset(&g_ulschedque, 0, sizeof(schedque_t));

	pthread_mutex_init(&g_ulschedque.mutex, NULL);
	g_ulschedque.watchdog = get_timer(WXTIMER_TRIGGER, 40, 0, NULL, do_watchdog);
	g_ulschedque.map = get_wxbuff(NULL);

	for ( i = 0; i < MAX_PRIORITY; i++ ) {
		INIT_LIST_HEAD(&g_ulschedque.array[0].queue[i]);//active
		INIT_LIST_HEAD(&g_ulschedque.array[1].queue[i]);//expired
	}

	g_ulschedque.active = &g_ulschedque.array[0];
	g_ulschedque.expired = &g_ulschedque.array[1];

	INIT_LIST_HEAD(&g_ulschedque.scheded_ss);
	INIT_LIST_HEAD(&g_ulschedque.mapie);
	
	return 0;
}


void * do_task_ulsched(void *arg)
{
	uint32_t prio;
	sfattr_t *sf;


	for ( ; ; ) {//nr_ulsymbol = 18;channel =30
		g_ulremain = g_bsinfo.nr_ulsymbol * g_bsinfo.channel_nr / UL_SYMBOLS_PER_SLOT -  12 - 18;//#define UL_SYMBOLS_PER_SLOT	3

		///10 = 6+4 6:genmachdr ; 4:crc
		g_ulmapsize = 30 * BYTES_PER_SLOT_QPSK_12 - 10 - sizeof(ulmaphdr_t) - sizeof(cdmarngie_t) - sizeof(cdmabwrie_sh4_t) + 1;

		sem_wait(&sem_usched);
		start_timer(g_ulschedque.watchdog);
		init_wxbuff(g_ulschedque.map);

		pthread_mutex_lock(&g_ulschedque.mutex);

		while ( g_ulmapsize > sizeof(ulmapie_t) ) {/*只要当前剩下的ulmap长度大于ulmapie,就继续调度*/
			
			if ( test_and_clear_bit(SCHED_WATCHDOG_TIMEOUT, (volatile unsigned long *)&g_ulschedque.signal) )
				break;

			if ( g_ulschedque.active->nr_active == 0 ) {/*如果当前active 个数为零,那么就把expired 赋值给active
													*并继续进行调度*/
				prio_array_t *temp;
				
				temp = g_ulschedque.active;
				g_ulschedque.active = g_ulschedque.expired;
				g_ulschedque.expired = temp;
				continue;
			}

			prio = find_first_bit((const unsigned long *)g_ulschedque.active->bitmap, MAX_PRIORITY);
                        sf = list_entry(g_ulschedque.active->queue[prio].next, sfattr_t, ulink);
                        list_del(g_ulschedque.active->queue[prio].next);
                        if ( list_empty(&g_ulschedque.active->queue[prio]) )
                                clear_bit(prio, (volatile unsigned long *)g_ulschedque.active->bitmap);
                        g_ulschedque.active->nr_active--;

			pthread_mutex_lock(&sf->mutex);
                        if ( ulbandwidth_alloc(sf) < 0 ) break;/*0:have no bandwidth to allocate  -1:bandwidth insufficent*/

			prio = trytobe_fair(sf);/*重新计算服务流的优先级并把它插入到上行调度expired优先级队列中*/
                        list_add_tail(&sf->ulink, &g_ulschedque.expired->queue[prio]);
                        pthread_mutex_unlock(&sf->mutex);

                        set_bit(prio, (volatile unsigned long *)g_ulschedque.expired->bitmap);
                        g_ulschedque.expired->nr_active++;/*expired 队列里存放的是已经调度过的并且重新计算过优先级的服务流*/
		}
                cancel_timer(g_ulschedque.watchdog);
                clear_bit(SCHED_WATCHDOG_TIMEOUT, (volatile unsigned long *)&g_ulschedque.signal);

                build_ulmap(g_ulschedque.map);
		set_bit(SCHED_MAP_STANDBY, (volatile unsigned long *)&g_ulschedque.signal);
                pthread_mutex_unlock(&g_ulschedque.mutex);
	}

	return NULL;
}

/*该函数重新编辑了服务流的优先级*/
int32_t trytobe_fair(sfattr_t *sf)
{
	int32_t prio;


	prio =  (sf->priority + sf->policy) >> 1;

	if ( sf->service_flow_scheduling_type == UPLINK_GRANT_SCHEDULING_TYPE_UGS 
	     || sf->service_flow_scheduling_type == UPLINK_GRANT_SCHEDULING_TYPE_ERTPS ) {
		uint32_t distance;
		
		if ( g_bsinfo.frame < sf->last )
			distance = g_bsinfo.frame + 0xffffff - sf->last;
		else 
			distance = g_bsinfo.frame - sf->last;

		prio += (sf->sdu_inter_arrival_interval << 1) / FRAME_LENGTH - distance - 16;
	}
	else {
		uint32_t min;
		
		/* overflow preventing */
		min = ((uint32_t)sf->_bwr < (uint32_t)sf->_data) ? sf->_bwr : sf->_data;
		sf->_bwr -= min;
		sf->_data -= min;
		prio += (sf->_bwr - sf->_data) >> 7;

	}

	if ( prio < 0 ) prio = 0;
	else if ( prio >= MAX_PRIORITY ) prio = MAX_PRIORITY - 1;

	sf->priority = prio;
		
	return prio;
}


/* return:	0, no bandwidth will be allocated for this service flow.
 *		>0, bandwidth allocated.
 *		-1, bandwidth resource is insufficient.
 */
 /*带宽分配的单位是时隙该函数把  
 分配好的带宽放到ssinfo中去,然
 后 再把这个ss插入上行调度队列中
* 而带宽分配是基于sf的,为什么?*/
static int32_t ulbandwidth_alloc(sfattr_t *sf)
{
	uint32_t bwg, slots, distance, bytes, least, elapse;
	uint32_t type, min, max, grant, policy, interval, ss;

	
	if ( sf->stat == SF_INVALID )
		return 0;

	type	= sf->service_flow_scheduling_type;
	min	= sf->minimum_reserved_traffic_rate;
	max	= sf->maximum_sustained_traffic_rate;
	grant	= sf->unsolicited_grant_interval;
	policy	= sf->request_transmission_policy;
	interval= sf->sdu_inter_arrival_interval;
	ss	= sf->ss;

//bwg:unit of bytes
	if ( g_bsinfo.frame < sf->last )//reder:g_bsinfo.frame ?sf->last :the frame number of the last scheded occurs
		distance = g_bsinfo.frame + 0xffffff - sf->last;///24 bits
	else 
		distance = g_bsinfo.frame - sf->last;//distance means the distance between the bs current number and the number of the sf when  the last scheded occurs

	/* do bandwidth calculation specific to scheduling types */
	elapse = distance * FRAME_LENGTH;//FRAME_LENGTH =5ms,elapse means the elapse time after the last scheded occurs 
	if ( type == UPLINK_GRANT_SCHEDULING_TYPE_UGS ) {
		
		if ( elapse >= grant ) {//grant = grant interval
			if ( sf->fixed_variable_length_indicator == FIXED_LENGTH_SDU )
				bwg = ((elapse * sf->sdu_size) >> 1) / interval;//why divided by interval ? unit of interval ?
			else
				bwg = (elapse * min) >> 13;//right moving means divided;  13 = 10 + 3  :2^13 = 2^10 * 2^3
		}
		else
			return 0;
	}
	else if ( type == UPLINK_GRANT_SCHEDULING_TYPE_ERTPS ) {

		if ( elapse >= grant )
			bwg = (elapse * min) >> 13;
		else
			return 0;
	}
	else if ( sf->bwr == 0 )
		return 0;
	else {
		bwg = (elapse * (min + max)) >> 14;
		if ( sf->bwr < bwg )
			bwg = sf->bwr;
	}
	
	least = policy & NO_CRC ? 10 : 6;//least:means the least bytes ss needs,if no crc,then least equal 6,else 10
	bytes = bytes_perslot(g_ssinfo[ss].uiuc, 1);

	/* map bytes into slots */
	if ( bwg > least ) {
		slots = (bwg + bytes - 1) / bytes;

		if ( slots < g_ulremain ) {/*上行仍有足够的时隙可供分配*/
			g_ulremain -= slots;
			g_ssinfo[ss].bwg += slots;/*分配的单位是时隙*/
			sf->last = g_bsinfo.frame;
			sf->bwr = 0;/*带宽请求在sf 中,带宽保证放在SS中*/

			if ( list_empty(&g_ssinfo[ss].uscheded_link) ) {
				list_add_tail(&g_ssinfo[ss].uscheded_link, &g_ulschedque.scheded_ss);/*为什么这样做,把调度过的ss放在队列中,而不是sf*/
				g_ulschedque.nr_ss++;
				g_ulmapsize -= sizeof(ulmapie_t);/*调度之后产生一个ulmapie,使得可用的ulmap长度减小*/
			}

			return 1;
		}
		else if ( g_ulremain * bytes > least ) {	/* g_ulremain <= slots */
			g_ulremain = 0;
			g_ssinfo[ss].bwg += g_ulremain;
			sf->last = g_bsinfo.frame;
			sf->bwr = 0;

			if ( list_empty(&g_ssinfo[ss].uscheded_link) ) {
				list_add_tail(&g_ssinfo[ss].uscheded_link, &g_ulschedque.scheded_ss);
				g_ulschedque.nr_ss++;
				g_ulmapsize -= sizeof(ulmapie_t);
			}

			return -1;
		}
		else
			return 0;
	}
	else
		return 0;
}


static void build_ulmap(wxbuff_t *map)
{
	int8_t sh = 0;
	genmachdr_t *machdr;
	ulmaphdr_t *hdr;
	struct list_head *pos, *tmp;

/*初始化的时候map->end = map->beg,随着数据的填入,map->end 再不断增加*/
	hdr = (ulmaphdr_t *)map->end;
	hdr->hdr.msgtype = UL_MAP;
	hdr->ucd_count = g_bsinfo.bp_active->count[1];
	hdr->allocation_start_time = htonl(g_bsinfo.allocation_start_time);
	hdr->no_ofdma_symbols = g_bsinfo.nr_ulsymbol;///18 symbols
	map->end += sizeof(ulmaphdr_t);

	/* cdma_ranging_ie
	 * cdma_bandwidth_request_ie
	 * normal_ie
	 * cdma_allocation_ie
	 */
	{
		cdmarngie_t cdmarngie;
		cdmabwrie_sh4_t cdmabwrie_sh4;

		memset(&cdmarngie, 0, sizeof(cdmarngie_t));
		cdmarngie_set(&cdmarngie,
			      0,
			      12,
			      0,
			      0,
			      2,
			      6,
			      0,
			      0);
		memcpy(map->end,  &cdmarngie, sizeof(cdmarngie_t));
		map->end += sizeof(cdmarngie_t);
		
		memset(&cdmabwrie_sh4, 0, sizeof(cdmabwrie_sh4_t));
		cdmabwrie_sh4_set(&cdmabwrie_sh4,
				  map->end,
				  0,
				  12,
				  2,
				  0,
				  3,
				  6,
				  2,
				  0);
		map->end--;
		memcpy(map->end, &cdmabwrie_sh4, sizeof(cdmabwrie_sh4_t));
		map->end += sizeof(cdmabwrie_sh4_t);
	}

/*上行调度器把分配好的带宽放在ssinfo中,然后再把该ss 放到scheded_ss中*/
/*这里根据分配给SS的带宽形成ulmap消息*/
	list_for_each_safe(pos, tmp, &g_ulschedque.scheded_ss) {//list_for_each_safe is a for( ; ; )
		ssinfo_t *ss;
		ulmapie_t ie;
		
		list_del_init(pos);
		ss = list_entry(pos, ssinfo_t, uscheded_link);
		
		pthread_mutex_lock(&ss->mutex);
		if ( ss->stat == SS_INVALID )
			continue;

		memset(&ie, 0, sizeof(ulmapie_t));
		ulmapie_set(&ie,
			    ss->sf[0]->cid,/*basic CID*/
			    ss->uiuc,
			    ss->bwg,
			    0);
		memcpy(map->end, &ie, sizeof(ulmapie_t));
		map->end += sizeof(ulmapie_t);
		
		/* make clean ASAP */
		ss->bwg = 0;
#if 0
		for ( i = 0; i < ss->nr_sf; i++ )
			sf->bwr = 0;
#endif
		pthread_mutex_unlock(&ss->mutex);
	}

	list_for_each_safe(pos, tmp, &g_ulschedque.mapie) {
		cdmaallocieinfo_t *cdmaallocieinfo;

		if ( g_ulmapsize < sizeof(cdmaallocie_t) || g_ulremain < 20 )
			break;

		list_del(pos);
		cdmaallocieinfo = list_entry(pos, cdmaallocieinfo_t, link);
		
		if ( sh == 0 ) {
			cdmaallocie_t cdmaallocie;

			memset(&cdmaallocie, 0, sizeof(cdmaallocie_t));
			cdmaallocie_set(&cdmaallocie, 
					0,			/* cid */
					12,			/* uiuc */
					20,			/* duration */
					0,			/* uiuc_for_transmission */
					0,			/* repetition_coding_indication */
					cdmaallocieinfo->frame_number_index, 
					cdmaallocieinfo->ranging_code, 
					cdmaallocieinfo->ranging_symbol, 
					cdmaallocieinfo->ranging_subchannel, 
					cdmaallocieinfo->is_bwr);
			memcpy(map->end, &cdmaallocie, sizeof(cdmaallocie_t));
			map->end += sizeof(cdmaallocie_t);
			g_ulmapsize -= sizeof(cdmaallocie_t);
		}
		else {
			cdmaallocie_sh4_t cdmaallocie_sh4;
			
			memset(&cdmaallocie_sh4, 0, sizeof(cdmaallocie_sh4_t));
			cdmaallocie_sh4_set(&cdmaallocie_sh4,
					    map->end,
					    0,
					    12,
					    20,
					    0,
					    0,
					    cdmaallocieinfo->frame_number_index, 
					    cdmaallocieinfo->ranging_code, 
					    cdmaallocieinfo->ranging_symbol, 
					    cdmaallocieinfo->ranging_subchannel, 
					    cdmaallocieinfo->is_bwr);
			map->end--;
			memcpy(map->end, &cdmaallocie_sh4, sizeof(cdmaallocie_sh4_t));
			map->end += sizeof(cdmaallocie_t);
			g_ulmapsize -= (sizeof(cdmaallocie_sh4_t) - 1);
		}
		
		g_ulremain -= 20;
		sh = !sh;
		free(cdmaallocieinfo);
	}

	memset(map->end, 0, 4);///4 bytes used as crc
	map->end += 4;
	map->beg -= sizeof(genmachdr_t);/*ulmap消息需要一个通用的mac 头*/
	map->tolen = map->len = map->end - map->beg;
	machdr = (genmachdr_t *)map->beg;
	genmachdr_set(machdr, 0, 0, 0, 0, 1, 0, map->tolen, 0xffff);

	/* may apply padding bits */

	return;
}


static void do_watchdog(uint32_t arga, void *argb)
{
	time_t tm;

	time(&tm);
	fprintf(stdout, "usched do_watchdog @ jiffies:%d, %s", jiffies, ctime(&tm));
	set_bit(SCHED_WATCHDOG_TIMEOUT, (volatile unsigned long *)&g_ulschedque.signal);

	return;
}


int32_t post_cdmaie(cdmacode_t *cdmacode)
{
	cdmaallocieinfo_t *cdmaallocieinfo;


	if ( (cdmaallocieinfo = (cdmaallocieinfo_t *)malloc(sizeof(cdmaallocieinfo_t))) != NULL ) {
		cdmaallocieinfo->frame_number_index = cdmacode->frame_number_index;
		cdmaallocieinfo->ranging_code = cdmacode->ranging_code;
		cdmaallocieinfo->ranging_symbol = cdmacode->ranging_symbol;
		cdmaallocieinfo->ranging_subchannel = cdmacode->ranging_subchannel;
		cdmaallocieinfo->is_bwr = cdmacode->is_bwr;

		list_add_tail(&g_ulschedque.mapie, &cdmaallocieinfo->link);
	}

	return 0;
}