#include <stdlib.h>
#include <sys/types.h>

#include "ip.h"
#include "tcp.h"
#include "flags.h"
#include "math.h"
#include "random.h"

#define TRUE    1
#define FALSE   0
#define PR_MAX_SEQNO	1000000

typedef struct seqno_list_el {
	int seqno_;
	double send_time_;
	double cwnd_;
	struct seqno_list_el *next_;
} seqno_list_el;

class seqno_list {
  public:
	seqno_list() {head_=0; tail_=0; len_=0;}
	seqno_list_el* head() { return head_; }
	seqno_list_el* tail() { return tail_; }
	void enque (seqno_list_el *p) {
                if (!tail_) head_= tail_= p;
                else {
                        tail_->next_= p;
                        tail_= p;
                }
                tail_->next_= 0;
                ++len_;
	}
        seqno_list_el* deque() {
		if (!head_) return 0;
                seqno_list_el* p = head_;
                head_= p->next_; // 0 if p == tail_
                if (p == tail_) head_= tail_= 0;
                --len_;
                return p;
        }
	seqno_list_el* lookup(int seqno) {
		for (seqno_list_el* p = head_; p ; p = p->next_) 
			if (p->seqno_ == seqno) return(p);
		return 0;
	}
        int remove(int seqno) {

		for (seqno_list_el *pp= 0, *p= head_; p; pp=p, p=p->next_) {
			if (p->seqno_ == seqno) {
				if (!pp) 
					deque();
				else { 
					if (p == tail_) 
						tail_= pp; 
					pp->next_= p->next_;
					--len_;
					if (len_ == 0) 
						head_ = tail_ = 0;
				}
				free(p);
				return 0;
			}
		} 
		return -1;
	}

	int	length () const {return (len_);} 

	seqno_list clone() {
		seqno_list new_p ;
		seqno_list_el *qq = new seqno_list_el();

		new_p.len_=len_;
		if (head() == 0) {
			fprintf(stderr, "weird, unack is empty...\n"); 
			abort();
		}

		for (seqno_list_el *p= head_, *pp= 0, *q= 0, *qq= 0; p; \
					pp=p, p=p->next_, qq=q) {
			q = new seqno_list_el();
			if (p==head_)
				new_p.head_=q;
			if (p==tail_)
				new_p.tail_=q;
			q->seqno_ = p->seqno_;
			q->cwnd_ = p->cwnd_;
			q->send_time_ = p->send_time_;
			if (qq) 
				qq->next_=q;
		}
		new_p.tail()->next_=0;
		return(new_p);
	}
	void coalesce(seqno_list *p) {
		seqno_list_el *pp;
		while (p->length()) {
			pp = p->deque();
			enque(pp);
		}
	}
	void clobber() {
		seqno_list_el *pp;
		while (length()) {
			pp = deque();
			pp->next_=0;	
			free(pp);
		}
	}
#ifdef DEBUG_TCP_PR
	void dump()
	{
		seqno_list_el *p;
		int i;

		printf("PR dump length()=%d [",length());
		for (p=head(), i=0; i<length(); p=p->next_, i++)
			printf(" %d", p->seqno_);
		printf("]\n");
		fflush(stdout);
	}
#endif
	
  protected:
	seqno_list_el* head_;
	seqno_list_el* tail_;
	int	len_;
};

class PRTcpAgent : public TcpAgent {
 public:
	PRTcpAgent();
	virtual void recv(Packet *pkt, Handler*);
	void reset();
	int AreThereTOpkts();
	int collect_expired_pkts();
	virtual void timeout(int tno);
	virtual void send_much(int force, int reason, int maxburst);
	virtual double rtt_timeout();
	void newack(Packet *pkt);
	void rtt_update(double mrtt);
	void reset_rtx_timer(int mild, int backoff);
	void rtt_backoff();
	void slowdown(int how);
	virtual int window();

 protected:
	u_char have_updated_;
	u_char first_slowstart;
	u_char extreme_loss;
	u_char backoff;
	u_char TO_pkt_not_in_memorize_;

	u_char can_add_cburst;
	u_char rexmitted_before;
	int	multi_backoff_;

	seqno_list unack_;
	seqno_list memorize_;
	seqno_list to_be_resent_;

	int	new_seqno_;
	int	cburst;		// number of packets lost in a burst.
	double	cwnd_n_;	// congestion window at the time this packet was sent.
	double	srtt_;		// exponentially weighted average of past rtt's.
	double	mxrtt_;		// estimate of the maximum possible rtt.
	double	beta_;
	double	alpha_;

	u_char rexmitted[PR_MAX_SEQNO];	
	// array to be used for checking how many times a packet was lost.
	// Currently, the size is fixed by PR_MAX_SEQNO. In a long-run test, 
	// this array should be tuned so that PR_MAX_SEQNO is sufficient.
	// In a future version, this should be modified so that it is
	// allocated or deallocated dynamically.
};

static class PRTcpClass : public TclClass {
public:
	PRTcpClass() : TclClass("Agent/TCP/PR") {}
	TclObject* create(int, const char*const*) {
		return (new PRTcpAgent());
	}
} class_PR;

PRTcpAgent::PRTcpAgent() : TcpAgent(), new_seqno_(0), srtt_(6.0), mxrtt_(0), have_updated_(FALSE), first_slowstart(TRUE), beta_(3.0), alpha_(0.99), cburst(0)
{
	bind("beta_", &beta_);
	bind("alpha_", &alpha_);
	memset(rexmitted,0,PR_MAX_SEQNO);
	// temporarily for the fairness test with other TCP.
	set_pkttype(PT_TFRC); 
	multi_backoff_=0;
}

void PRTcpAgent::reset ()
{
	TcpAgent::reset ();
}

void PRTcpAgent::rtt_backoff()
{

	double now = Scheduler::instance().clock();
	int t;

	t = 1<<multi_backoff_;

	if (t > 64) t = 64;

	if (t_backoff_ < 64)
		t_backoff_ <<= 1;

	if ( t_backoff_ < t) {
		t_backoff_ = t;
	}

}

void PRTcpAgent::reset_rtx_timer(int mild, int backoff)
{
	double now = Scheduler::instance().clock();

	if (backoff)
		rtt_backoff();

	set_rtx_timer();
	rtt_active_ = 0;
}

double PRTcpAgent::rtt_timeout()
{
	double now = Scheduler::instance().clock();
	if ( have_updated_ ) {
		if (extreme_loss)
			mxrtt_ = 1.0 * t_backoff_;
		else
			mxrtt_ = srtt_ * beta_ * t_backoff_;
	} else 
		mxrtt_ = srtt_;

	return(mxrtt_);
}

int PRTcpAgent::AreThereTOpkts()
{
	double now = Scheduler::instance().clock();
	int count;
	int set_cwnd_n_;

	if ( unack_.length() == 0 )
		return(FALSE);

	set_cwnd_n_=0;
	if ( now - unack_.head()->send_time_ >= rtt_timeout() ) {
		count = 0;
		for (seqno_list_el *p= unack_.head(); p; p=p->next_) {
			if (now - p->send_time_ >= rtt_timeout()) {
				if (!set_cwnd_n_) {
					set_cwnd_n_= 1;
					cwnd_n_ = p->cwnd_;
				}
				count++;
				seqno_list_el* p1 = memorize_.lookup(p->seqno_);
				if (!p1)
					TO_pkt_not_in_memorize_ = TRUE;
				else 
					TO_pkt_not_in_memorize_ = FALSE;
			} else 
				return(count);
		}
	} else 
		return(FALSE);

	return(count);
}

int PRTcpAgent::collect_expired_pkts()
{
	double now = Scheduler::instance().clock();
	int collected_pkts;

	can_add_cburst=0;
	rexmitted_before=0;
	collected_pkts=0;

	for (seqno_list_el *p= unack_.head(); p; ) {
		if (now - p->send_time_ >= rtt_timeout()) {
			seqno_list_el *pp = unack_.deque();

			if (p != pp) {
				fprintf(stderr,"weird... p and pp are diff.\n");
				abort();	
			}

			p=p->next_;

			if ( rexmitted[pp->seqno_] > 0) {

				int t=1<<rexmitted[pp->seqno_];

				rexmitted_before = 1;

				if ( t_backoff_ < t ) {
					if ( multi_backoff_ < rexmitted[pp->seqno_] )
						multi_backoff_ = rexmitted[pp->seqno_];
				}
			}

			if (memorize_.length()) {
				memorize_.remove(pp->seqno_);
				can_add_cburst=1;
			}
			
			to_be_resent_.enque(pp);
			collected_pkts++;

			// this return statement makes tcp-pr collect only
			// one expired packet at a time. And its side-effect
                        // is to reduce aggressiveness of tcp-pr.

			return(collected_pkts);

		} else {
			return(collected_pkts);
		}
	}
}


void PRTcpAgent::rtt_update(double mrtt)
{
	double now = Scheduler::instance().clock();
	double gamma;
	double grtt_;

	if ( !have_updated_ ) {
		srtt_ = mrtt;
		have_updated_ = TRUE;
	} 
	else {
		gamma = pow(alpha_, 1.0/double(cwnd_));
		grtt_ = gamma * srtt_;

		if ( grtt_ > mrtt ) {
			srtt_ = grtt_;
		}else {
			srtt_ = mrtt;
		}
	}
}

void PRTcpAgent::newack(Packet *pkt)
{
	hdr_tcp *tcph = hdr_tcp::access(pkt);
	double now = Scheduler::instance().clock();
	seqno_list_el* p = unack_.lookup(tcph->seqno());

	if (p) {
		rtt_update(now - p->send_time_);
		t_backoff_ = 1;
		multi_backoff_=0;
	} else {
		p=to_be_resent_.lookup(tcph->seqno());
		if (!p) {
			printf("PR [%2d] newack: lookup failure <%d>\n",addr(), tcph->seqno());
			abort();
		} 
	}
}

void PRTcpAgent::recv(Packet *pkt, Handler*)
{
	hdr_tcp *tcph = hdr_tcp::access(pkt);
	int	backoff=0;

	extreme_loss=FALSE;

#ifdef notdef
	if (pkt->type_ != PT_TFRC_ACK) {
		Tcl::instance().evalf("%s error \"received non-ack\"",
				      name());
		Packet::free(pkt);
		return;
	}
#endif

	++nackpack_;

	double now = Scheduler::instance().clock();

	if ( !rexmitted[tcph->seqno()] ) {
		newack(pkt);
	}

	if (!memorize_.length()) {

		cburst=0;
		unack_.remove(tcph->seqno());
		
	} else {

		unack_.remove(tcph->seqno());
		memorize_.remove(tcph->seqno());

		if (!memorize_.length())
			cburst=0;

		if ( to_be_resent_.length() > 0 )
			to_be_resent_.remove(tcph->seqno());
	}

	/* check if there are timeout'ed packets. */

	int TOpkts = 0;

	if ( TOpkts = AreThereTOpkts() ) {

		if ( TO_pkt_not_in_memorize_ ) { // New Drop
			memorize_ = unack_.clone();	// save the snapshot of 
							// unack_ into memorize_
			cburst=1;
			collect_expired_pkts();

			if ( cwnd_ < 2 || rexmitted_before )
				extreme_loss=TRUE;

			if ( cwnd_n_ > 1) {
				slowdown(CLOSE_CWND_HALF|CLOSE_SSTHRESH_HALF);
			} else {
				backoff=1;
				slowdown(CLOSE_SSTHRESH_HALF);
			}
			first_slowstart=FALSE;

		} else {
			collect_expired_pkts();
			if (can_add_cburst)
				cburst++;

			if ( cwnd_ < 2 || cburst > cwnd_ + 1 || rexmitted_before ) 
				extreme_loss=TRUE;
		}

	} else {

		if (memorize_.length()==0) 
			opencwnd();

	}
	reset_rtx_timer(0,backoff);
	send_much(FALSE, 0, maxburst_);
	Packet::free(pkt);

}

void PRTcpAgent::timeout(int tno)
{
	double	now = Scheduler::instance().clock();
	int	TOpkts = 0;
	int 	backoff;

	backoff = 0;

	if (tno == TCP_TIMER_RTX) {

	    TOpkts = AreThereTOpkts() ;

	    if (extreme_loss) {

		backoff=1;
		slowdown(CLOSE_CWND_ONE);
		memorize_.clobber();

		for (seqno_list_el *p= unack_.head(); p; p=p->next_ ) {
			if ( rexmitted[p->seqno_] > 0) {

				int t=1<<rexmitted[p->seqno_];

				rexmitted_before = 1;

				if ( t_backoff_ < t ) {
					if ( multi_backoff_ < rexmitted[p->seqno_] )
						multi_backoff_ = rexmitted[p->seqno_];
				}
			}
		}

		// put all the packets in unack_ into to_be_resent_
		to_be_resent_.coalesce(&unack_); 

	    } else if ( TOpkts ) {

		if ( TO_pkt_not_in_memorize_ ) { // New Drop
			memorize_ = unack_.clone();	// save the snapshot of 
							// unack_ into memorize_
			cburst=1;
			collect_expired_pkts();

			if ( cwnd_n_ > 1) {
				slowdown(CLOSE_CWND_HALF|CLOSE_SSTHRESH_HALF);
			} else {
				backoff=1;
				slowdown(CLOSE_SSTHRESH_HALF);
			}
			first_slowstart=FALSE;
			if ( cwnd_ < 2 || rexmitted_before ) 
				extreme_loss=TRUE;

		} else {	// other drops in burst

			collect_expired_pkts();
			if (can_add_cburst)
				cburst++;

			if ( cwnd_ < 2 || cburst > cwnd_ + 1 || rexmitted_before ) 
				extreme_loss=TRUE;
		}

	    } else {
		backoff=1;
		slowdown(CLOSE_CWND_ONE);

	    }
	    reset_rtx_timer(0,backoff);
	    send_much(FALSE,0, maxburst_);

	} else {

	timeout_nonrtx(tno);

	}
}

/* 
 * In send_much of PRTcpAgent, 'reason' is meaningless.
 * whatever the reason for send_much is, to_be_resent is referred first.
 */
void PRTcpAgent::send_much(int force, int reason, int maxburst)
{
	register int npacket = 0;
	double now = Scheduler::instance().clock();

	if (!force && delsnd_timer_.status() == TIMER_PENDING)
		return;

	/*
	 * As long as cwnd_ >= |unack|+1 and there is app data to send,
	 * we try to send a packet.
	 */
	while ( cwnd_ >= unack_.length() + 1 && t_seqno_ < curseq_ )  {

	    if ( overhead_ == 0 || force) {

		if ( to_be_resent_.length() > 0 ) {
			seqno_list_el *dequed_seqno = to_be_resent_.deque();
			output(dequed_seqno->seqno_, 0);
			dequed_seqno->send_time_ = now;
			dequed_seqno->cwnd_ = double(cwnd_);
			dequed_seqno->next_ = 0; 
			unack_.enque(dequed_seqno);		
			rexmitted[dequed_seqno->seqno_] += 1;

		} else if ( t_seqno_ < curseq_ ) {
			output(new_seqno_, 0);
			seqno_list_el *p = new seqno_list_el();
			p->seqno_ = new_seqno_;
			p->send_time_ = now;
			p->cwnd_ = double(cwnd_);
			p->next_ = 0; 
			unack_.enque(p);
			t_seqno_++;
			new_seqno_++;

			if ( new_seqno_ > PR_MAX_SEQNO ) {
				fprintf(stderr,"seqno greater than PR_MAX_SEQNO\n");
				fflush(stderr);
				abort();
			}
		} else {
			if ( unack_.length() == 0 )
				return;
		}
		npacket++;
	    } else if (!(delsnd_timer_.status() == TIMER_PENDING)) {
		/* 
		* Set a delayed send timeout.  
		* This is only for the simulator,to add some 
		* randomization if speficied.  
		*/ 
		delsnd_timer_.resched(Random::uniform(overhead_));
		return;

	    }
		if (maxburst && npacket == maxburst)
			break;

	} /* while */
}

/*
 * PRTcpAgent::window() returns the congestion window at the time
 * when the packet on the head of memorize list was sent if memorize
 * list is not empty, i.e. there are timedout packets. Otherwise,
 * it returns the current congestion window.
 */
int PRTcpAgent::window()
{

	if (memorize_.head() != 0) {
		double temp = memorize_.head()->cwnd_;
		return (temp < wnd_ ? (int)temp : (int)wnd_);
	} else {
		return (cwnd_ < wnd_ ? (int)cwnd_ : (int)wnd_);
	}
}

/*
 * PRTcpAgent::slowdown() is the same as TcpAgent::slowdown() in 
 * ns-2.1b8a except that decreasewin and halfwin are set to 1.0 
 * whenever they become less than 1.0.
 */
void
PRTcpAgent::slowdown(int how)
{
	double win, halfwin, decreasewin;
	int slowstart = 0;

	// we are in slowstart for sure if cwnd < ssthresh
	if (cwnd_ < ssthresh_)
		slowstart = 1;
	// we are in slowstart - need to trace this event
	trace_event("SLOW_START");

        if (precision_reduce_) {
		halfwin = windowd() / 2;
                if (wnd_option_ == 6) {
                        /* binomial controls */
                        decreasewin = windowd() - (1.0-decrease_num_)*pow(windowd(),l_parameter_);
                } else
	 		decreasewin = decrease_num_ * windowd();
		win = windowd();
	} else  {

		int temp;

		temp = (int)(window() / 2);
		halfwin = (double) temp;
		if (halfwin < 1.0)
			halfwin = 1.0;
                if (wnd_option_ == 6) {
                        /* binomial controls */
                        temp = (int)(window() - (1.0-decrease_num_)*pow(window(),l_parameter_));
                } else
	 		temp = (int)(decrease_num_ * window());
		decreasewin = (double) temp;
		if (decreasewin < 1.0)
			decreasewin = 1.0;
		win = (double) window();
	}
	if (how & CLOSE_SSTHRESH_HALF)
		// For the first decrease, decrease by half
		// even for non-standard values of decrease_num_.
		if (first_decrease_ == 1 || slowstart ||
			last_cwnd_action_ == CWND_ACTION_TIMEOUT) {
			// Do we really want halfwin instead of decreasewin
			// after a timeout?
			ssthresh_ = (int) halfwin;
		} else {
			ssthresh_ = (int) decreasewin;
		}
        else if (how & THREE_QUARTER_SSTHRESH)
		if (ssthresh_ < 3*cwnd_/4)
			ssthresh_  = (int)(3*cwnd_/4);
	if (how & CLOSE_CWND_HALF)
{
		// For the first decrease, decrease by half
		// even for non-standard values of decrease_num_.
		if (first_decrease_ == 1 || slowstart || decrease_num_ == 0.5) {
			cwnd_ = halfwin;
		} else cwnd_ = decreasewin;
}
        else if (how & CWND_HALF_WITH_MIN) {
		// We have not thought about how non-standard TCPs, with
		// non-standard values of decrease_num_, should respond
		// after quiescent periods.
                cwnd_ = decreasewin;
                if (cwnd_ < 1)
                        cwnd_ = 1;
	}
	else if (how & CLOSE_CWND_RESTART) 
		cwnd_ = int(wnd_restart_);
	else if (how & CLOSE_CWND_INIT)
		cwnd_ = int(wnd_init_);
	else if (how & CLOSE_CWND_ONE)
		cwnd_ = 1;
	else if (how & CLOSE_CWND_HALF_WAY) {
		// cwnd_ = win - (win - W_used)/2 ;
		cwnd_ = W_used + decrease_num_ * (win - W_used);
                if (cwnd_ < 1)
                        cwnd_ = 1;
	}
	if (ssthresh_ < 2)
		ssthresh_ = 2;
	if (how & (CLOSE_CWND_HALF|CLOSE_CWND_RESTART|CLOSE_CWND_INIT|CLOSE_CWND_ONE))
		cong_action_ = TRUE;

	fcnt_ = count_ = 0;
	if (first_decrease_ == 1)
		first_decrease_ = 0;
}

