
/*
 * router.cc
 * Copyright (C) 2002 by John Heidemann <johnh@isi.edu>
 * $Id: router.cc,v 1.15 2002/04/20 03:49:00 johnh Exp $
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 *
 */

/*
 * router.cc: implements a router
 * handles sending messages, etc.
 */

#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
extern int errno;
#include <sys/time.h>

#include "router.hh"
#include "msg.hh"
#include "main.hh"


int
ActivityCallback::expire()
{
	if (active_) {
		cerr << "ActivityCallback::expire active\n";
		// reschedule
		active_ = false;
		return QUIESCENT_TIME_SECS * 1000;
	};
	cerr << "ActivityCallback::expire INACTIVE\n";
	router_->quiescent();
	// no need to continue
	return -1;
}


int
LSAFloodCallback::expire()
{
	// timer expired!
	// is it still needed?
	if (outdated_) {
		// cerr << "LSAFloodCallback::expire: timer at " << router_->id() << " origin_id_ " << origin_id_ << " dest_id_ " << dest_id_ << " is outdated.\n";
		// xxx: should do lsa_->deref(); here
		return -1;  // no, it's not
	}

	// yes, send or resend the message
	tx_count_++;
	int dest_port = router_->neighbor_id_to_port(dest_id_);
	// cerr << "LSAFloodCallback::expire: timer at " << router_->id() << " origin_id_ " << origin_id_ << " dest_id_ " << dest_id_ << " dest_port_ " << dest_port << " sending try " << tx_count_ << endl;
	struct hostent *he = gethostbyname("localhost");
	assert(he != NULL);
	struct sockaddr_in sa_to;
	memset(&sa_to, 0, sizeof(sa_to));
	sa_to.sin_family = AF_INET;
	memcpy(&sa_to.sin_addr, he->h_addr, he->h_length);
	sa_to.sin_port = htons(dest_port);

	assert(lsa_->bytes_marshalled_ > 0);
	router_->stats_.bump(RouterStats::SENT);
	router_->active();
	int e = sendto(source_socket_,
		   lsa_->bytes_, lsa_->bytes_marshalled_,
		   0,
		   (struct sockaddr*)&sa_to, sizeof(sa_to));
	assert(e == lsa_->bytes_marshalled_);

       // reschedule the timer after 5 seconds
       return 5000;

}


RealRouter::RealRouter(int master_port) :
	master_port_(master_port),
	master_socket_(-1),
	port_(0),
	socket_(-1),
	id_(0),
	stage_(0),
	loss_rate_(0),
	last_lsa_(NULL),
	next_seqno_(0),
	timers_(new Timers),
	act_cb_(this),
	lsa_routing_(NULL)
{
	// cerr << "RealRouter::RealRouter\n";
	assert(timers_ != NULL);

	init();
	loop();
	exit(0);
}


void
RealRouter::init()
{
	// cerr << "RealRouter::init\n";
	/*
	 * First setup our UDP port to listen on.
	 */
	assert(-1 != (socket_ = socket(PF_INET, SOCK_DGRAM, IPPROTO_UDP)));

	struct hostent *he = gethostbyname("localhost");
	assert(he != NULL);

	port_ = 0;  // dynamic assignment

	struct sockaddr_in udp_sa;
	udp_sa.sin_family = AF_INET;
	memset(&udp_sa, 0, sizeof(udp_sa));
	memcpy(&udp_sa.sin_addr, he->h_addr, he->h_length);
	udp_sa.sin_port = htons(port_);

	// cerr << "  RealRouter::init binding udp\n";
	assert (-1 != bind(socket_, (struct sockaddr *) &udp_sa, sizeof(udp_sa)));

	// read out the port
	socklen_t udp_sa_len = sizeof(udp_sa);
	assert(-1 != getsockname(socket_,  (struct sockaddr *) &udp_sa, &udp_sa_len));
	port_ = ntohs(udp_sa.sin_port);

	/*
	 * Now contact the master for configuration
	 */
	assert(-1 != (master_socket_ = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP)));

	struct sockaddr_in master_sa;
	memset(&master_sa, 0, sizeof(master_sa));
	master_sa.sin_family = AF_INET;
	memcpy(&master_sa.sin_addr, he->h_addr, he->h_length);
	master_sa.sin_port = htons(master_port_);

	// cerr << "  RealRouter::init connecting tcp\n";
	assert(-1 != (connect(master_socket_, (struct sockaddr *)&master_sa, sizeof(master_sa))));

	/* we tell them ours */
	RouterReport report;
	report.pid_ = getpid();
	report.udp_port_ = port_;
	// cerr << "  RealRouter::init reporting\n";
	int sent = write(master_socket_, &report, sizeof(report));
	assert(sent == sizeof(report));

	/* they tell us theirs */
	RouterConfig config;
	// cerr << "  RealRouter::init configing\n";
	assert (sizeof(config) == read(master_socket_, &config, sizeof(config)));
	// router, config thyself...
	assign(config.stage_, config.id_, config.loss_rate_);
	for (int i = 0; i < config.num_neighbors_; i++) {
		add_neighbor_id_port(config.neighbor_ids_[i],
				     config.neighbor_ports_[i]);
		
	};
	add_internal_route(new Route(new AddrPrefix(config.address_, config.prefix_), config.id_, 0));
	for (int i = 0; i < config.num_externals_; i++) {
		add_external_route(new Route(new AddrPrefix(config.external_addrs_[i], config.external_prefixes_[i]), config.external_ids_[i], 0, 0, config.external_meds_[i]));
	};

	// for debugging:
	cerr << "RealRouter::init, pid " << getpid() << " is id " <<  id_ << " port " << port_ << endl;
	if (debug)
		sleep(5);

}

void
RealRouter::assign(int stage, int id, int loss_rate)
{
	stage_ = stage;
	id_ = id;
	loss_rate_ = loss_rate;
	char fname[128];
	sprintf(fname, "s%d-%d.out", stage,id_);

	// cerr << "writing to " << fname << endl;
	outstr_.open(fname);
	assert(outstr_.good());

	lsa_routing_ = new LinkStateRouting(id_);
	assert(lsa_routing_ != NULL);
}

void
RealRouter::add_neighbor_id_port(int id, int port)
{
	neighbor_ids_.push_back(id);
	neighbor_ports_.push_back(port);
	assert(neighbor_id_to_port_.find(id) == neighbor_id_to_port_.end());
	neighbor_id_to_port_[id] = port;
}

int
RealRouter::neighbor_id_to_port(int id)
{
	map<int,int>::iterator it = neighbor_id_to_port_.find(id);
	assert (it != neighbor_id_to_port_.end());
	return it->second;
}

void
RealRouter::loop()
{
	/*
	 * schedule reliable announcements to all of our neighbors
	 * loop, timing out and resending as necessary
	 * until the network is quiescent.
	 */
	timers_->AddTimer(1, &act_cb_);
	send_our_lsa();
	for (;;) {
		// find when our timers fire
		struct timeval tmv;
		timers_->NextTimerTime(&tmv);
		bool doing_polling = false;
		enum { ROUTER_POLL_THRESHOLD_SEC = 30 };
		if (tmv.tv_sec >= ROUTER_POLL_THRESHOLD_SEC) {
			cerr << "  " << id_ <<" polling\n";
			doing_polling = true;
			tmv.tv_sec = ROUTER_POLL_THRESHOLD_SEC;  // poll every 10s
			tmv.tv_usec = 0;
		} else {
			// cerr << "  " << id_ <<" non-polling " << tmv.tv_sec << "/" << tmv.tv_usec << endl;
		};
		fd_set read_fds;
		FD_ZERO(&read_fds);
		FD_SET(socket_, &read_fds);
		int e = select(socket_+1, &read_fds, NULL, NULL, &tmv);
		assert(e != -1);
		if (e == 0) {
			// expried, so run timer
			if (!doing_polling) {
				// cerr << "  " << id_ <<" timer\n";
				timers_->ExecuteNextTimer();
			};
		} else {
			cerr << "  " << id_ <<" data\n";
			LSA *lsa = new LSA;
			struct sockaddr_in source_sa;
			socklen_t source_sa_len = sizeof(source_sa);
			// data arrived
			int recv_size = recvfrom(socket_, lsa->bytes_, sizeof(lsa->bytes_), 0, (struct sockaddr*)&source_sa, &source_sa_len);
			assert(recv_size != -1);
			lsa->bytes_marshalled_ = recv_size;
			lsa->unmarshal();
			// handle loss
			active();
			if (rand()%100 < loss_rate_) {
				// drop it
				stats_.bump(RouterStats::DROPPED);
				lsa->deref();
			} else {
				stats_.bump(RouterStats::RECEIVED);
				// process it
				if (lsa->ack_)
					handle_lsa_ack(lsa, (struct sockaddr*)&source_sa, (int)source_sa_len);
				else handle_lsa(lsa, (struct sockaddr*)&source_sa, (int)source_sa_len);
			};
		};
	};
}

void
RealRouter::send_our_lsa()
{
	cerr << "RealRouter::send_our_lsa at " <<  id_ << endl;
	// make the LSA
	LSA *lsa = new LSA;
	lsa->ack_ = 0;
	lsa->seqno_ = next_seqno_++;
	lsa->ttl_ = DEFAULT_TTL;
	lsa->origin_id_ = id_;
	lsa->last_id_ = id_;
	lsa->num_routes_ = internal_routes_.size() + external_routes_.size();
	for (list<Route*>::iterator r_it = internal_routes_.begin();
	     r_it != internal_routes_.end();
	     r_it++) {
		(*r_it)->ref();
		lsa->routes_.push_back(*r_it);
	};
	for (list<Route*>::iterator r_it = external_routes_.begin();
	     r_it != external_routes_.end();
	     r_it++) {
		(*r_it)->ref();
		lsa->routes_.push_back(*r_it);
	};
	lsa_routing_->fill_in_neighbor_links_in_lsa(lsa);
	lsa->marshal();
	// remember our own LSAs so we don't re-forward them
	latest_lsa_seqno_[lsa->origin_id_] = lsa->seqno_;
	// and remember it for logging
	if (last_lsa_ != NULL) {
		last_lsa_->deref();
		last_lsa_ = NULL;
	};
	last_lsa_ = lsa;
	last_lsa_->ref();
	// and hand it to our routing alg (so we handle our own routes)
	lsa_routing_->new_lsa(lsa);
	// send it to our neighbors
	reliably_flood(lsa, 1);  // consumes lsa
}

/*
 * handle incoming lsa messages
 */
void
RealRouter::handle_lsa(LSA *lsa, struct sockaddr *source_sap, int source_sa_len)
{
	cerr << "RealRouter::handle_lsa at " <<  id_
	     << "  origin_id_ " << lsa->origin_id_
	     << "  last_id_ " << lsa->last_id_
	     << "  seqno_ " << lsa->seqno_
	     << endl;
#if 0
	if (id_ > 3) {
		cerr << "  RealRouter::handle_lsa rejected\n";
		return;
	}
#endif /* 0 */
	/*
	 * reliably flood it
	 */
	/*
	 * First, ACK it.
	 * (Ack it even if it's ttl'ed out because
	 * its sender expects us to ack if they sent it.)
	 */
	LSA *ack_lsa = new LSA;
	ack_lsa->ack_ = 1;
	ack_lsa->seqno_ = lsa->seqno_;
	ack_lsa->origin_id_ = lsa->origin_id_;
	ack_lsa->last_id_ = id_;
	ack_lsa->marshal();
	assert(ack_lsa->bytes_marshalled_ > 0);

	struct hostent *he = gethostbyname("localhost");
	assert(he != NULL);
	struct sockaddr_in sa_to;
	memset(&sa_to, 0, sizeof(sa_to));
	sa_to.sin_family = AF_INET;
	memcpy(&sa_to.sin_addr, he->h_addr, he->h_length);
	sa_to.sin_port = htons(neighbor_id_to_port(lsa->last_id_));

	stats_.bump(RouterStats::SENT);
	active();
	int e = sendto(socket_,
		       ack_lsa->bytes_, ack_lsa->bytes_marshalled_,
		       0,
		       (struct sockaddr*)&sa_to, sizeof(sa_to));
	assert(e == ack_lsa->bytes_marshalled_);
	ack_lsa->deref();  // done with ack

	/*
	 * Second, process it
	 */
	// 2a: ttl check
	if (--lsa->ttl_ <= 0) {
		cerr << "  *** RealRouter::handle_lsa dropped from ttl at " <<  id_ << endl;
		return;
	};
	// 2b: determine if we've already seen this message before
	if (latest_lsa_seqno_.find(lsa->origin_id_) != latest_lsa_seqno_.end() &&
	    latest_lsa_seqno_[lsa->origin_id_] >= lsa->seqno_) {
		// yes, seen it before
		// cerr << "    RealRouter::handle_lsa dup at " << id_ << endl;
		return;
	};
	// 2c: remember it
	latest_lsa_seqno_[lsa->origin_id_] = lsa->seqno_;
	// 2e: handle it wrt routing and report the result
	bool new_link_status = lsa_routing_->new_lsa(lsa);
	outstr_ << (*lsa_routing_) << "---\n";
	outstr_.flush();  // let the user watch what's going on
	// 2f: if our link status changed, propagate it
	if (new_link_status)
		send_our_lsa();

	/*
	 * 3: Forward it.
	 */
	// cerr << "  RealRouter::handle_lsa forwarding at " <<  id_ << endl;
	lsa->last_id_ = id_;
	lsa->marshal();
	reliably_flood(lsa, 1);  // consumes lsa
}

/*
 * reliably_flood 
 * send an LSA packet reliably (either ours or someone elses)
 */
void
RealRouter::reliably_flood(LSA *lsa, int msec_delay)
{
	// this sends the packet and consumes the lsa ref
	cerr << "RealRouter::reliably_flood at " << id_ << " origin_id_ " << lsa->origin_id_ << " last_id_ " << lsa->last_id_ << " seqno_ " << lsa->seqno_ << endl;
	/*
	 * Send lsa on to all our neighbors
	 * and schedule a timer to make sure it gets there.
	 */
	// First, see if this message superceeds existing, unacked messages.
	// If so, terminate them.
	for (list<LSAFloodCallback*>::iterator cb_it = cbs_.begin();
	     cb_it != cbs_.end();
	     cb_it++) {
		if (lsa->seqno_ > (*cb_it)->seqno() &&
		    lsa->origin_id_ == (*cb_it)->origin_id() &&
		    lsa->last_id_ == (*cb_it)->dest_id()) {
			cerr << "      RealRouter::reliably_flood outdating timer at " << id_ << " origin_id_ " << (*cb_it)->origin_id() << " dest_id_ " << (*cb_it)->dest_id() << " since new seqno_ " << lsa->seqno_  << " beats old seqno_ " << (*cb_it)->seqno() << endl;
			(*cb_it)->outdate();
		};
	};
	// Next send it to all the neighbors.
	for (list<int>::iterator ni_it = neighbor_ids_.begin();
	     ni_it != neighbor_ids_.end();
	     ni_it++) {
		lsa->ref();
		LSAFloodCallback *cb = new LSAFloodCallback(this, socket_, lsa->origin_id_, *ni_it, lsa);
		// cerr << "    RealRouter::reliably_flood scheduling tx at " << id_ << " to id " << *(ni_it) << " origin_id_ " << lsa->origin_id_ << endl;
		cbs_.push_back(cb);
		// schedule it to go out shortly
		timers_->AddTimer(msec_delay, cb);
	};
	// we're done with it, consume it
	lsa->deref();
}

/*
 * handle ACKs to our LSA messages
 */
void
RealRouter::handle_lsa_ack(LSA *lsa, struct sockaddr *source_sap, int source_sa_len)
{
	cerr << "RealRouter::handle_lsa_ack at " << id_ << endl;
	// look through callbacks and outdate them
	// cerr << "  ack seqno_ " << lsa->seqno_ << " my id_ " << id_ << " ack id " << lsa->origin_id_ << " last id: " << lsa->last_id_ << endl;
	for (list<LSAFloodCallback*>::iterator cb_it = cbs_.begin();
	     cb_it != cbs_.end();
	     cb_it++) {
		// cerr << "    seqno: " << (*cb_it)->seqno() << " origin id: " << (*cb_it)->origin_id() << " dest id: " << (*cb_it)->dest_id() << endl;
		if (lsa->seqno_ >= (*cb_it)->seqno() &&
		    lsa->origin_id_ == (*cb_it)->origin_id() &&
		    lsa->last_id_ == (*cb_it)->dest_id()) {
			// cerr << "      RealRouter::handle_lsa_ack_ outdating at " << id_ << " origin_id_ " << (*cb_it)->origin_id() << " dest_id_ " << (*cb_it)->dest_id() << " since new seqno_ " << lsa->seqno_  << " beats old seqno_ " << (*cb_it)->seqno() << endl;
			(*cb_it)->outdate();
		};
	};

	// done with it
	lsa->deref();
}

/*
 * handle termination... print our report and give up
 */
void
RealRouter::quiescent()
{
	outstr_ << stats_;
	outstr_ << "last-lsa-msg-sent ";
	for (int i = 0; i < last_lsa_->bytes_marshalled_; i++) {
		char buf[10];
		sprintf(buf, "%02x", last_lsa_->bytes_[i]);
		outstr_ << buf;
	};
	outstr_ << endl;
	exit(0);
}
