rq.cc

Ns2 TCP 协议改进 版本 提高goodput

		r = p ? p : head_;
		while (r && r != q)  {
			if (start == r->startseq_ && end == r->endseq_) {
				// exact overlap
				r->pflags_ |= tiflags;
				if (RQC_CNTDUPS == TRUE)
					r->cnt_++;
				return (r->pflags_);
			} else if (start <= r->startseq_ && end >= r->endseq_) {
				// complete overlap, not exact
				total_ -= (r->endseq_ - r->startseq_);
				n = r;
				r = r->next_;
				tiflags |= n->pflags_;
				initcnt += n->cnt_;
				fremove(n);
				sremove(n);
				ReassemblyQueue::deleteseginfo(n);
				altered = TRUE;
			} else
				r = r->next_;
		}


		//
		// if we completely overlapped everything, the list
		// will now be empty.  In this case, just add the new one
		///

		if (empty())
			goto endfast;

		if (altered) {
			altered = FALSE;
			goto again2;
		}

		// look for left-side merge
		// update existing seg's start seq with new start
		if (p == NULL || p->next_->startseq_ < start) {
			if (p == NULL)
				p = head_;
			else
				p = p->next_;
				
			if (start < p->startseq_) {
				total_ += (p->startseq_ - start);
				p->startseq_ = start;
			}
			start = p->endseq_;
			needmerge = TRUE;
			p->pflags_ |= tiflags;
			p->cnt_++;
			--initcnt;
		}

		// look for right-side merge
		// update existing seg's end seq with new end
		if (q == NULL || q->prev_->endseq_ > end) {
			if (q == NULL)
				q = tail_;
			else
				q = q->prev_;

			if (end > q->endseq_) {
				total_ += (end - q->endseq_);
				q->endseq_ = end;
			}
			end = q->startseq_;
			needmerge = TRUE;
			q->pflags_ |= tiflags;
			if (!needmerge) {
				// if needmerge is TRUE, that can
				// only be the case if we did a left-side
				// merge (above), which has already taken
				// accounting of the new segment
				q->cnt_++;
				--initcnt;
			}
		}


		if (end <= start) {
			if (rcv_nxt_ >= head_->startseq_)
				rcv_nxt_ = head_->endseq_;
			return (tiflags);
		}
			

		//
		// if p & q are adjacent and new one
		// fits between, that is an easy case
		//

		if (!needmerge && p->next_ == q && p->endseq_ <= start && q->startseq_ >= end) {
			if (p->endseq_ == start || q->startseq_ == end)
				needmerge = TRUE;
		}

endfast:
		n = ReassemblyQueue::newseginfo();
		n->startseq_ = start;
		n->endseq_ = end;
		n->pflags_ = tiflags;
		n->rqflags_ = rqflags;
		n->cnt_=  initcnt;

		n->prev_ = p;
		n->next_ = q;

		push(n);

		if (p)
			p->next_ = n;
		else
			head_ = n;

		if (q)
			q->prev_ = n;
		else
			tail_ = n;


		//
		// If there is an adjacency condition,
		// call coalesce to deal with it.
		// If not, there is a chance we inserted
		// at the head at the rcv_nxt_ point.  In
		// this case we ned to update rcv_nxt_ to
		// the end of the newly-inserted segment
		//

		total_ += (end - start);

		if (needmerge)
			return(coalesce(p, n, q));
		else if (rcv_nxt_ >= start) {
			rcv_nxt_ = end;
		}

		return tiflags;
	}
}
/*
 * We need to see if we can coalesce together the
 * blocks in and around the new block
 *
 * Assumes p is prev, n is new, p is after
 */
TcpFlag
ReassemblyQueue::coalesce(seginfo *p, seginfo *n, seginfo *q)
{
	TcpFlag flags = 0;

#ifdef RQDEBUG
printf("coalesce(%p,%p,%p)\n", p, n, q);
printf(" [(%d,%d),%d],[(%d,%d),%d],[(%d,%d),%d]\n",
	p ? p->startseq_ : 0,
	p ? p->endseq_ : 0,
	p ? p->cnt_ : -1000,
	n ? n->startseq_ : 0,
	n ? n->endseq_ : 0,
	n ? n->cnt_ : -1000,
	q ? n->startseq_ : 0,
	q ? n->endseq_ : 0,
	q ? n->cnt_ : -1000);
dumplist();
#endif

	if (p && q && p->endseq_ == n->startseq_ && n->endseq_ == q->startseq_) {
		// new block fills hole between p and q
		// delete the new block and the block after, update p
		sremove(n);
		fremove(n);
		sremove(q);
		fremove(q);
		p->endseq_ = q->endseq_;
		p->cnt_ += (n->cnt_ + q->cnt_);
		flags = (p->pflags_ |= n->pflags_);
		ReassemblyQueue::deleteseginfo(n);
		ReassemblyQueue::deleteseginfo(q);
	} else if (p && (p->endseq_ == n->startseq_)) {
		// new block joins p, but not q
		// update p with n's seq data, delete new block
		sremove(n);
		fremove(n);
		p->endseq_ = n->endseq_;
		flags = (p->pflags_ |= n->pflags_);
		p->cnt_ += n->cnt_;
		ReassemblyQueue::deleteseginfo(n);
	} else if (q && (n->endseq_ == q->startseq_)) {
		// new block joins q, but not p
		// update q with n's seq data, delete new block
		sremove(n);
		fremove(n);
		q->startseq_ = n->startseq_;
		flags = (q->pflags_ |= n->pflags_);
		q->cnt_ += n->cnt_;
		ReassemblyQueue::deleteseginfo(n);
		p = q;	// ensure p points to something
	}

	//
	// at this point, p points to the updated/coalesced
	// block.  If it advances the highest in-seq value,
	// update rcv_nxt_ appropriately
	//
	if (rcv_nxt_ >= p->startseq_)
		rcv_nxt_ = p->endseq_;
	return (flags);
}

/*
 * look for the next hole, starting with the given
 * sequence number.  If this seq number is contained in
 * a SACK block we have, return the ending sequence number
 * of the block.  Also, fill in the nxtcnt and nxtbytes fields
 * with the number and sum total size of the sack regions above
 * the block.
 */
int
ReassemblyQueue::nexthole(TcpSeq seq, int& nxtcnt, int& nxtbytes)
{

	nxtbytes = nxtcnt = -1;
	hint_ = head_;

	seginfo* p;
	for (p = hint_; p; p = p->next_) {
		// seq# is prior to SACK region
		// so seq# is a legit hole
		if (p->startseq_ > seq) {
			cnts(p, nxtcnt, nxtbytes);
			return (seq);
		}

		// seq# is covered by SACK region
		// so the hole is at the end of the region
		if ((p->startseq_ <= seq) && (p->endseq_ >= seq)) {
			if (p->next_) {
				cnts(p->next_, nxtcnt, nxtbytes);
			}
			return (p->endseq_);
		}
	}
	return (-1);
}


#ifdef RQDEBUG
main()
{
	int rcvnxt = 1;
	ReassemblyQueue rq(rcvnxt);

	static int blockstore[64];
	int *blocks = blockstore;
	int nblocks = 5;
	int i;

	printf("Simple---\n");
	rq.add(2, 4, 0, 0);
	rq.add(6, 8, 0, 0);	// disc
	printf("D1\n");
	rq.dumplist();	// [(2,4),1], [(6,8),1]

	rq.add(1,2, 0, 0);	// l merge
	printf("D2\n");
	rq.dumplist();	// [(1,4),2], [(6,8),1]

	rq.add(8, 10, 0, 00);	// r merge
	printf("D3\n");
	rq.dumplist();	// [(1,4),2], [(6, 10),2]

	rq.add(4, 6, 0, 0);	// m merge
	printf("Simple output:\n");
	rq.dumplist();	// [(1, 10),5]

	printf("X0:\n");
	rq.init(1);
	rq.add(5,10, 0, 0);
	rq.add(11,20, 0, 0);
	rq.add(5,10, 0, 0);	// dup left
	rq.dumplist();	// [(5,10),1], [(11,20),1]

	printf("X1:\n");
	rq.init(1);
	rq.add(5,10, 0, 0);
	rq.add(11,20, 0, 0);
	rq.add(11,20, 0, 0);	// dup rt
	rq.dumplist();	// [(5,10),1], [(11,20),1]

	printf("X2:\n");
	rq.init(1);
	rq.add(5,10, 0, 0);
	rq.add(11,20, 0, 0);
	rq.add(30, 40, 0, 0);
	rq.add(11,20, 0, 0);	// dup mid
	rq.dumplist();	// [(5,10),1], [(11,20),1], [(30,40),1]

	printf("X3\n");
	rq.add(30,50,0,0);	// dup rt
	rq.dumplist();	// [(5,10),1], [(11,20),1], [(30,50),2]

	printf("X4\n");
	rq.add(1,10,0,0);	// dup lt
	rq.dumplist();	// [(1,10),2], [(11,20),1], [(30,50),2]

	printf("C1:\n");
	rq.init(1);
	rq.add(2, 4, 0, 0);
	rq.add(1, 4, 0, 0);	// l overlap full
	rq.dumplist();	// [(1,4),2]

	printf("C2:\n");
	rq.init(1);
	rq.add(2, 4, 0, 0);
	rq.add(1, 3, 0, 0);	// l overlap part
	rq.dumplist();	// [(1,4),2]

	printf("C3:\n");
	rq.init(1);
	rq.add(2, 4, 0, 0);
	rq.add(2, 7, 0, 0);	// r overlap full
	rq.dumplist();	// [(2,7),2]

	printf("C4:\n");
	rq.init(1);
	rq.add(2, 4, 0, 0);
	rq.add(3, 7, 0, 0);	// r overlap part
	rq.dumplist();	// [(2,7),2]

	printf("C5:\n");
	rq.init(1);
	rq.add(2, 4, 0, 0);
	rq.add(6, 8, 0, 0);
	rq.add(1, 9, 0, 0);	// double olap - ends
	rq.dumplist();	// [(1,9),3]

	printf("C6:\n");
	rq.init(1);
	rq.add(2, 4, 0, 0);
	rq.add(6, 8, 0, 0);
	rq.add(15, 20, 0, 0);
	rq.dumplist();	// [(2,4),1], [(6,8),1], [(15,20),1]
	rq.add(5, 9, 0, 0);	// overlap middle
	rq.dumplist();	// [(2,4),1], [(5,9),2], [(15,20),1]

	printf("C7:\n");
	rq.init(1);
	rq.add(1, 2, 0, 0);
	rq.add(3, 5, 0, 0);
	rq.add(6, 8, 0, 0);
	rq.add(9, 10, 0, 0);
	rq.dumplist();	// [(1,2),1],[(3,5),1],[(6,8),1],[(9,10),1]
	rq.add(4, 7, 0, 0);	// double olap middle
	rq.dumplist();	// [(1,2),1], [(3,8),3], [(9,10),1]

	printf("C8:\n");
	rq.init(1);
	rq.add(1, 2, 0, 0);
	rq.add(3, 5, 0, 0);
	rq.add(10, 12, 0, 0);
	rq.add(20, 30, 0, 0);
	rq.dumplist();	// [(1,2),1], [(3,5),1], [(10,12),1], [(20,30),1]
	rq.add(4, 8, 0, 0);	// single olap middle
	rq.dumplist();	// [(1,2),1], [(3,8),2], [(10,12),1], [(20,30),1]

	rq.init(1);
	rq.add(1, 5, 0, 0);
	rq.add(10, 20, 0, 0);
	//rq.add(40321, 41281, 0, 0);
	//rq.add(42241, 43201, 0, 0);
	//rq.add(44161, 45121, 0, 0);
	rq.dumplist();	// [(1,5),1], [(10,20),1]
	//rq.add(40321, 41281, 0, 0);
	rq.add(1, 5, 0, 0);
	rq.dumplist();	// [(1,5),1], [(10,20),1]

	int x, y;
	printf("NH1: %d\n", rq.nexthole(3, x, y));
	printf("NH2: %d\n", rq.nexthole(5, x, y));
	printf("CLR to 4\n");
	rq.clearto(4);
	rq.dumplist();

	exit(0);
}
#endif