rq.cc

Ns2 TCP 协议改进 版本 提高goodput

/*
 * Copyright (c) Intel Corporation 2001. All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
*/

/*
 * Copyright (c) 1991-1997 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the Computer Systems
 *	Engineering Group at Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 */

#include "rq.h"

ReassemblyQueue::seginfo* ReassemblyQueue::freelist_ = NULL;

ReassemblyQueue::seginfo* ReassemblyQueue::newseginfo()
{
	seginfo *s;
	
	if( (s = freelist_) ){
		freelist_ = s->next_;
		return s;
	}else{
		return new seginfo;
	}
}

void ReassemblyQueue::deleteseginfo(ReassemblyQueue::seginfo* s)
{
	s->next_ = freelist_;
	freelist_ = s;
}

/*
 * unlink a seginfo from its FIFO
 */
void
ReassemblyQueue::fremove(seginfo* p)
{
	if (hint_ == p)
		hint_ = NULL;

	if (p->prev_)
		p->prev_->next_ = p->next_;
	else
		head_ = p->next_;
	if (p->next_)
		p->next_->prev_ = p->prev_;
	else
		tail_ = p->prev_;
}

/*
 * unlink a seginfo from its LIFO
 */
void
ReassemblyQueue::sremove(seginfo* p)
{
	if (hint_ == p)
		hint_ = NULL;

	if (p->sprev_)
		p->sprev_->snext_ = p->snext_;
	else
		top_ = p->snext_;
	if (p->snext_)
		p->snext_->sprev_ = p->sprev_;
	else
		bottom_ = p->sprev_;

}

/*
 * push a seginfo on the LIFO
 */
void
ReassemblyQueue::push(seginfo *p)
{
	p->snext_ = top_;
	p->sprev_ = NULL;
	top_ = p;
	if (p->snext_)
		p->snext_->sprev_ = p;
	else
		bottom_ = p;
}

/*
 * counts: return the # of blks and byte counts in
 * them starting at the given node
 */
void
ReassemblyQueue::cnts(seginfo *p, int& blkcnt, int& bytecnt)
{
	int blks = 0;
	int bytes = 0;

	while (p != NULL) {
		++blks;
		bytes += (p->endseq_ - p->startseq_);
		p = p->next_;
	}
	blkcnt = blks;
	bytecnt = bytes;
	return;
}


/*
 * clear out reassembly queue and stack
 */

void
ReassemblyQueue::clear()
{
	// clear stack and end of queue
	tail_ = top_ = bottom_ = hint_ = NULL;

	seginfo *p = head_;
	while (head_) {
		p = head_;
		head_= head_->next_;
		ReassemblyQueue::deleteseginfo(p);
	}
	tail_ = NULL;
	total_ = 0;
	return;
}

/*
 * clear out reassembly queue (and stack) up
 * to the given sequence number
 */

TcpFlag
ReassemblyQueue::clearto(TcpSeq seq)
{
	TcpFlag flag = 0;
	seginfo *p = head_, *q;
	while (p) {
		if (p->endseq_ <= seq) {
			q = p->next_;
			flag |= p->pflags_;
			total_ -= (p->endseq_ - p->startseq_);
			sremove(p);
			fremove(p);
			ReassemblyQueue::deleteseginfo(p);
			p = q;
		} else
			break;
	}
	/* we might be trimming in the middle */
	if (p && p->startseq_ <= seq && p->endseq_ > seq) {
		total_ -= (seq - p->startseq_);
		p->startseq_ = seq;
		flag |= p->pflags_;
	}
	return flag;
}

/*
 * gensack() -- generate 'maxsblock' sack blocks (start/end seq pairs)
 * at specified address
 * returns the number of blocks written into the buffer specified
 *
 * According to RFC2018, a sack block contains:
 *	left edge of block (first seq # of the block)
 *	right edge of block (seq# immed. following last seq# of the block)
 */

int
ReassemblyQueue::gensack(int *sacks, int maxsblock)
{
	seginfo *p = top_;
	int cnt = maxsblock;

	while (p && maxsblock) {
		*sacks++ = p->startseq_;
		*sacks++ = p->endseq_;
		--maxsblock;
		p = p->snext_;
	}
	return (cnt - maxsblock);
}

/*
 * dumplist -- print out FIFO and LIFO (for debugging)
 */

void
ReassemblyQueue::dumplist()
{

	printf("FIFO [size:%d]: ", total_);
	if (head_ == NULL) {
		printf("NULL\n");
	} else {
		register seginfo* p = head_;
		while (p != NULL) {
			if (p->rqflags_ & RQF_MARK) {
				printf("OOPS: LOOP1\n");
				abort();
			}
			printf("[->%d, %d<-<f:0x%x,c:%d>]",
				p->startseq_, p->endseq_, p->pflags_, p->cnt_);
			p->rqflags_ |= RQF_MARK;
			p = p->next_;
		}
		printf("\n");
		p = tail_;
		while (p != NULL) {
			printf("[->%d, %d<-]",
				p->startseq_, p->endseq_);
			p = p->prev_;
		}
		printf("\n");
	}

	printf("LIFO: ");
	if (top_ == NULL) {
		printf("NULL\n");
	} else {
		register seginfo* s = top_;
		while (s != NULL) {
			if (s->rqflags_ & RQF_MARK)
				s->rqflags_ &= ~RQF_MARK;
			else {
				printf("OOPS: LOOP2\n");
				abort();
			}
			printf("[->%d, %d<-]",
				s->startseq_, s->endseq_);
			s = s->snext_;
		}
		printf("\n");
		s = bottom_;
		while (s != NULL) {
			printf("[->%d, %d<-]",
				s->startseq_, s->endseq_);
			s = s->sprev_;
		}
		printf("\n");
	}
	printf("RCVNXT: %d\n", rcv_nxt_);
	printf("\n");
	fflush(stdout);
}

/*
 *
 * add() -- add a segment to the reassembly queue
 *	this is where the real action is...
 *	add the segment to both the LIFO and FIFO
 *
 * returns the aggregate header flags covering the block
 * just inserted (for historical reasons)
 *
 * add start/end seq to reassembly queue
 * start specifies starting seq# for segment, end specifies
 * last seq# number in the segment plus one
 */

TcpFlag
ReassemblyQueue::add(TcpSeq start, TcpSeq end, TcpFlag tiflags, RqFlag rqflags)
{

	int needmerge = FALSE;
	int altered = FALSE;
	int initcnt = 1;	// initial value of cnt_ for new blk

	if (end < start) {
		fprintf(stderr, "ReassemblyQueue::add() - end(%d) before start(%d)\n",
			end, start);
		abort();
	}

	if (head_ == NULL) {
		if (top_ != NULL) {
			fprintf(stderr, "ReassemblyQueue::add() - problem: FIFO empty, LIFO not\n");
			abort();
		}

		// nobody there, just insert this one


		tail_ = head_ = top_ = bottom_ =  ReassemblyQueue::newseginfo();
		head_->prev_ = head_->next_ = head_->snext_ = head_->sprev_ = NULL;
		head_->startseq_ = start;
		head_->endseq_ = end;
		head_->pflags_ = tiflags;
		head_->rqflags_ = rqflags;
		head_->cnt_ = initcnt;

		total_ = (end - start);

		//
		// this shouldn't really happen, but
		// do the right thing just in case
		if (rcv_nxt_ >= start)
			rcv_nxt_ = end;

		return (tiflags);
	} else {

again2:
		seginfo *p = NULL, *q = NULL, *n, *r;

		//
		// in the code below, arrange for:
		// q: points to segment after this one
		// p: points to segment before this one
		//

		if (start >= tail_->endseq_) {
			// at tail, no overlap
			p = tail_;
			if (start == tail_->endseq_)
				needmerge = TRUE;
			goto endfast;
		}

		if (end <= head_->startseq_) {
			// at head, no overlap
			q = head_;
			if (end == head_->startseq_)
				needmerge = TRUE;
			goto endfast;
		}

		//
		// search for segments before and after
		// the new one; could be overlapped
		//
		q = head_;
		while (q && q->startseq_ < end)
			q = q->next_;

		p = tail_;
		while (p && p->endseq_ > start)
			p = p->prev_;

#ifdef notdef
printf("Thinking of merging (s:%d, e:%d), p:%p (%d,%d), q:%p (%d,%d) into: \n",
start, end, p, q,
	p ? p->startseq_ : 0,
	p ? p->endseq_ : 0,
	q ? n->startseq_ : 0,
	q ? n->endseq_ : 0);
#endif


		//
		// kill anything that is completely overlapped
		//