snoop.c

一种无线拥塞控制协议

/***************************************************************************
                          snoop.c  -  SNOOP METHODS
                             -------------------
    begin                : Thu Jun 13 2002
    copyright            : (C) 2002 by Indradeep Biswas
    email                : [e-mail]
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *                       PHASE 1 IMPLEMENTATION                            *
 *                                                                         *
 ***************************************************************************/

#include "snoop.h"	// Snoop header = includes + structures

//============ SNOOP MALLOC -allocates memory to structures=================

/*
 * The snoop_malloc(.) function is the Snoop memory allocation unit. 
 * It utilizes the kernel memory allocation macro called kmalloc(.), 
 * the kernel memory allocator.  snoop_malloc(.) takes the size of 
 * memory needed for allocation as a parameter, and returns a pointer 
 * to the chunk of memory that was allocated.
 */

void * snoop_malloc (int size){
	void *m;

	if ((m = kmalloc(size, GFP_ATOMIC)) == (void *) 0)
		snoop_error (SNOOPE_NOMEM, "snoop_malloc()");
	return m;
}

//============ SNOOP SKB CLONE - clones a skb ==============================

/*
 * The snoop_skb_clone(.) function uses the kernel macro skb_copy() to 
 * make a local copy of the sk_buff, or the kernel packet buffer.
 */

struct sk_buff *snoop_skb_clone(struct sk_buff *clone_skb)
{
	return skb_copy(clone_skb, GFP_ATOMIC);
}

//============ SNOOP INIT - initializes snoop on module install=============

/*
 * The snoop_init_control() function initializes Snoop for runtime. The 
 * initialization procedure includes allocating memory for the data 
 * structures, and initializing the variables.  For each allowable 
 * connection, the function allocates memory using snoop_malloc() first 
 * for the connection container itself, and then for each packet container 
 * within that connection.  In the case where memory is not allocated, 
 * the function returns an error, which is propagated to the init_module()
 * function.  This causes the module load to fail.  By allocating memory 
 * for the data structure at initialization, we ensure that the gateway, 
 * running Snoop, will always have enough memory to run the Snoop agent.
 */

int snoop_init_control(){
	int i, j;
	snoop_cs_t *cs;

	if (SNOOP_DEBUG) printk ("SNOOP: Initializing SNOOP module ... ");
	snoop_control.num_connections = 0;

	// Allocate the buffer for each connection state
	for (i = 0; i < SNOOP_MAXCONN; i++) {
		// If memory gets allocated
		if ((cs =(snoop_cs_t *) snoop_malloc(sizeof(snoop_cs_t)))){
			snoop_control.cstate[i] = cs;
			cs->state = SNOOP_CLOSED;
			cs->last_ack = cs->last_seq = 0;
			cs->head = 0;
			cs->tail = 1;
			cs->rto = SNOOP_RTO;
			sema_init(&cs->mutex, 1);

			if (!(cs->sock = (struct snoop_socket *) snoop_malloc (sizeof(struct snoop_socket))))
				{break;break;}

			// Allocate mem for all packets for all connection
			for (j = 0; j < SNOOP_MAXWINDOW; j++) {
				// If memory gets allocated
				if ((cs->pkts[j] = (snoop_packet_t *)
					snoop_malloc (sizeof (snoop_packet_t)))){
					cs->pkts[j]->conn_id = 0;
					cs->pkts[j]->seq = 0;
					cs->pkts[j]->size = 0;
					cs->pkts[j]->departure = 0;
					cs->pkts[j]->num_rxmit = 0;
					cs->pkts[j]->skb = 0;
					cs->pkts[j]->sock = 0;
					cs->pkts[j]->lock = SPIN_LOCK_UNLOCKED;
					cs->pkts[j]->irqflags = 0;

					
				}
				else {break;break;}
			}
		}
		else break;
	}
	// If the for loop has been broken,then, generate nomem error
	if (i != SNOOP_MAXCONN) return SNOOPE_NOMEM;

	if (SNOOP_DEBUG) printk("DONE. \n");
	return SNOOPE_SUCCESS;
}

//============ SNOOP INIT CONN - initializes a connection state ============
/*
 * The snoop_init_conn(.) function extracts information about the 
 * form the snoop buffer.  It finds a free connection container by 
 * traversing the cstate array of the snoop_control structure, and 
 * initializes the connection with the values from the snoop buffer.  
 *
 * The implementation, as of now assumes that connection is always 
 * initiated by the mobile host. Therefore the source IP and source port 
 * of the snoop socket are used later on by snoop_getconn to determine
 * whether the packet is from the mobile host, or from the fixed host.
 *
 * This funciton also sets the idle timer for the connection.
 */

int snoop_init_conn(struct snoop_buffer *snb){
	unsigned int	conn_id;
	snoop_cs_t	*cs = 0;

	if (SNOOP_DEBUG) printk("SNOOP: Initializing new connection... ");

	for (conn_id = 0; conn_id < SNOOP_MAXCONN; conn_id++) {
		cs = snoop_control.cstate[conn_id];
		if (cs->state & SNOOP_CLOSED) break;
	}

	if (conn_id != SNOOP_MAXCONN){
	    ++snoop_control.num_connections;
	} 
	else return SNOOPE_CONFULL;
	
	down (&cs->mutex);
	
	cs->state = SNOOP_ACTIVE | SNOOP_NOACK;
	cs->last_seq = cs->last_ack = cs->head = 0;
	cs->tail = 1;
	cs->rto = SNOOP_RTO;

	cs->sock->daddr = snb->sock->daddr;
	cs->sock->saddr = snb->sock->saddr;
	cs->sock->dest = snb->sock->dest;
	cs->sock->source = snb->sock->source;

	init_timer(&cs->timeout);
	cs->timeout.expires = jiffies + (SNOOP_CONN_TIMEOUT * HZ);
	cs->timeout.data = (unsigned long)conn_id;
	cs->timeout.function = &snoop_conn_timeout;
	add_timer(&cs->timeout);
	if (SNOOP_DEBUG) printk("added timer");
	up(&cs->mutex);
	if (SNOOP_DEBUG) printk ("- connection timeout if idle for [%u] -", SNOOP_CONN_TIMEOUT);
	if (SNOOP_DEBUG) printk(" connection [%3d] created.\n", conn_id);
	
	return conn_id;
}

//============ SNOOP CONN TIMEOUT - handles timeout for cs =================

/*
 * This function is invoked by the kernel timer when the connection's idle
 * timer times out.  Whenever there is a timeout, the connection state
 * for that connection is cleared, and the variables are reset.
 *
 * The connection timeout value can be set through the constant defined in
 * snoop.h
 */

void snoop_conn_timeout (unsigned long conn_id){
	if (SNOOP_DEBUG)printk ("SNOOP: Conn[%3d] timed out! Cleaning up connection...\n",(unsigned int)conn_id);
	snoop_clean_conn ((unsigned int) conn_id);
}

//============ SNOOP DATA - handles packets from FH to MH ==================

/*
 * First of all, the function checks whether the packet container buffer 
 * is full.  If the buffer is full, and the packet is an old packet that 
 * has already been acknowledged, it is passed on.  
 *
 * Otherwise, snoop_insert(.) is invoked, and the function is passed the 
 * connection state, and the snoop buffer.    
 *
 * Once the insert function returns, the last sequence received is updated,
 * and the snoop buffer is freed.
 */

int snoop_data(struct snoop_buffer *snb, unsigned int conn_id){
	snoop_cs_t *cs = snoop_control.cstate[conn_id];
	int status;

	if (SNOOP_DEBUG) printk("SNOOP: **Fixed Host** ");

	if (cs->state & SNOOP_FULL && snb->seq < cs->last_ack) {
		if (SNOOP_DEBUG) printk ("BUFFER FULL - last seq %u, seq %u, size %u ]\n", cs->last_seq, snb->seq, snb->size);
		return SNOOPE_SUCCESS;
	}

	if ((status = snoop_insert(conn_id, snb)) != SNOOPE_SUCCESS){
		snoop_error(status, "snoop_data->snoop_insert");
		return status;
	}
	if (snb->seq > cs->last_seq) cs->last_seq = snb->seq;
	if (snb->flags) kfree(snb->flags);
	if (snb) kfree (snb);
	
	return SNOOPE_SUCCESS;
}

//============ SNOOP INSERT - inserts a packet into a connection ===========

/*
 * A series of checks are performed on the packet container buffer before 
 * the packet is added to the buffer.  If the sequence number of the 
 * received packet is less than the last acknowledged packet,  then the 
 * packet is a duplicate from the FH.  Since it is not necessary for Snoop 
 * to cache it, and the packet is forwarded.  
 *
 * An index is maintained which determinse where in the buffer the packet 
 * must be added.
 *
 * If the packet is new, and is the greated in sequence received so far, 
 * it is added at the end of the buffer.  If the packet's seq is smaller 
 * than the first packet in the buffer, the new packet is added at the 
 * beginning of the buffer.
 *
 * If the packet belongs somewhere in the middle, then the buffered 
 * packets are shifted to create room for the new packet.  Ideally, all the
 * packets in the buffer always remain in sequence.
 *
 * snoop_save_packet() is then invoked to actually store the packet in the 
 * buffer.  If the buffer is full, the buffer full flag is set in the 
 * connection state variable.
 */

int snoop_insert(unsigned int conn_id, struct snoop_buffer *snb){
	snoop_cs_t *cs = snoop_control.cstate[conn_id];
	int i = 0, j, status;
	
	// Packet belongs to the very end of the queue
	if (snb->seq > cs->last_seq || snb->seq >= cs->last_ack) {
		i = cs->tail;
		cs->tail = NEXT(cs->tail);
		goto found;
	}
	// Packet belongs to the very beginning of the queue
	else if (cs->pkts[NEXT(cs->head)] && snb->seq < cs->pkts[NEXT(cs->head)]->seq) {
		cs->head = PREV(cs->head);
		i = cs->head;
		goto found;
	}

	// Packet belongs somewhere in between
	for (i = NEXT(cs->head);i != cs->tail; i = NEXT(i)) {
		// If a the seq# exists, and new packet has more data
		if (cs->pkts[i]->seq == snb->seq){
			if (snb->size > cs->pkts[i]->size){
				cs->pkts[i]->num_rxmit = 0;
			 	goto found;
			}
			else return SNOOPE_SUCCESS;
		}
		// Find best place for out of order pacekts
		else if (cs->pkts[i]->seq > snb->seq) {
			snoop_packet_t *temp = cs->pkts[PREV(cs->head)];
			for (j = cs->head; NEXT(j) != i; j = NEXT(j))
				cs->pkts[PREV(j)] = cs->pkts[j];
			i = PREV(i);
			cs->pkts[i] = temp;
			cs->head = PREV(cs->head);
			goto found;
		}
	}

found:
	if (i == 0){
		if (SNOOP_DEBUG) printk(" NO PACKET BUFF ");
		return SNOOPE_SUCCESS;
	}
	if (cs->head == cs->tail) cs->state |= SNOOP_FULL;
	if (SNOOP_DEBUG) printk(" at packet buffer[%2d] [", i);
	if (SNOOP_DEBUG) printk(" -head [%2d] tail [%2d]- ", cs->head, cs->tail);
	if ((status = snoop_save_packet(cs->pkts[i], snb, conn_id)) != SNOOPE_SUCCESS){
		snoop_error(status, "snoop_insert->snoop_save_packet");
		return status;
	}
	
	if (SNOOP_DEBUG) printk(" ] \n\n");
	return SNOOPE_SUCCESS;
}

//============ SNOOP PACKET RETRANSMIT - retransmit timed out pacekts ======

/*
 * This function is invoked when the packet timer times out. From the 
 * argument, the packet structure is extracted, and the connection 
 * is identified.  If the number of retransmissions has not exceeded the 
 * max retransmission limit ( a constant which can be set in snoop.h),
 * the packet is retransmitted to the mobile host using the snoop_forward()
 * function. otherwise, the function returns without doing anything.
 *
 * The RTO is used from the connections state to reset the timer for the 
 * next timeout.
 *
 * The whole course of operating on the packet - forwarding and reseting
 * the timer must be done within a critical section. Thus, a spin lock 
 * is used for mutual exclusion.  This will prevent crashes if a fin
 * packet is received from either end, while an old packet is forwarded.
 */

void snoop_packet_retransmit (unsigned long rexmit_packet){
	snoop_packet_t * retransmit_packet = (snoop_packet_t *)rexmit_packet;
	snoop_cs_t *cs;
	
	if (SNOOP_DEBUG && retransmit_packet->seq) printk("-=SNOOP=-: Packet with seq: %u timed out... retransmitting packet for [%2d]th time...", retransmit_packet->seq, retransmit_packet->num_rxmit);
	if (retransmit_packet && retransmit_packet->seq == 0) return;
	else {
		cs = snoop_control.cstate[retransmit_packet->conn_id];
		if (cs->state & SNOOP_CLOSED) return;
	}