cbq.cc

CBQ的源代码

	 * Add to per-level list
	 *	and store the highest level# we've seen
	 */

	if (p->level_ <= 0 || p->level_ > MAXLEVEL) {
		fprintf(stderr, "CBQ class %s has invalid level %d\n",
			p->name(), p->level_);
		return (-1);
	}

	p->level_peer_ = levels_[p->level_];
	levels_[p->level_] = p;
	if (p->level_ > maxlevel_)
		maxlevel_ = p->level_;

	/*
	 * Check that parent and borrow linkage are acyclic.
	 */
#ifdef notdef
	check_for_cycles(CBQClass::parent);
	check_for_cycles(CBQClass::borrow);
#endif
	return 0;
}

int CBQueue::command(int argc, const char*const* argv)
{

	Tcl& tcl = Tcl::instance();
	if (argc == 3) {
		if (strcmp(argv[1], "insert-class") == 0) {
			CBQClass *cl = (CBQClass*)TclObject::lookup(argv[2]);
			if (cl == 0) {
				tcl.resultf("CBQ: no class object %s",
					argv[2]);
				return (TCL_ERROR);
			}
			if (insert_class(cl) < 0) {
				tcl.resultf("CBQ: trouble inserting class %s",
					argv[2]);
				return (TCL_ERROR);
			}
			return (TCL_OK);
		}
		if (strcmp(argv[1], "link") == 0) {
			LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]);
			if (del == 0) {
				tcl.resultf("CBQ: no LinkDelay object %s",
					argv[2]);
				return(TCL_ERROR);
			}
			link_ = del;
			return (TCL_OK);
		}
		if (strcmp(argv[1], "algorithm") == 0) {
			if (algorithm(argv[2]) < 0)
				return (TCL_ERROR);
			return (TCL_OK);
		}
	}
	return (Queue::command(argc, argv));
}

class WRR_CBQueue : public CBQueue {
public:
	WRR_CBQueue() {
		memset(M_, '\0', sizeof(M_));
		memset(alloc_, '\0', sizeof(alloc_));
		memset(cnt_, '\0', sizeof(cnt_));
	}
	void	addallot(int prio, double diff) {
		alloc_[prio] += diff;
		setM();
	}
protected:
	Packet *deque();
	int	insert_class(CBQClass*);
	void	setM();
	double	alloc_[MAXPRIO];
	double	M_[MAXPRIO];
	int	cnt_[MAXPRIO];		// # classes at prio of index
	int	command(int argc, const char*const* argv);
};

static class WRR_CBQQueueClass : public TclClass {
public:
	WRR_CBQQueueClass() : TclClass("Queue/CBQ/WRR") { }
	TclObject* create(int, const char*const*) {
		return (new WRR_CBQueue);
	}
} class_wrr_cbq;

int WRR_CBQueue::command(int argc, const char*const* argv)
{
	Tcl& tcl = Tcl::instance();
	if (strcmp(argv[1], "insert-class") == 0) {
		CBQClass *cl = (CBQClass*)TclObject::lookup(argv[2]);
		if (cl == 0) {
			tcl.resultf("WRR-CBQ: no class object %s",
				argv[2]);
			return (TCL_ERROR);
		}
		if (insert_class(cl) < 0) {
			tcl.resultf("WRR-CBQ: trouble inserting class %s",
				argv[2]);
			return (TCL_ERROR);
		}
		return (TCL_OK);
	}
	return (CBQueue::command(argc, argv));
}

Packet *
WRR_CBQueue::deque()
{

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

	CBQClass* first = NULL;
	CBQClass* eligible = NULL;
	CBQClass* next_eligible = NULL;
	CBQClass* cl;

	register int prio;
	int deficit, done;
	int none_found = 0;

	Packet* rval;

	/*
	 * prio runs from 0 .. maxprio_
	 *
	 * round-robin through all the classes at priority 'prio'
	 *      if any class is ok to send, resume it's queue
	 * go on to next lowest priority (higher prio nuber) and repeat
	 * [lowest priority number is the highest priority]
	 */

	for (prio = 0; prio <= maxprio_; prio++) {
		// see if there is any class at this prio
		if ((cl = active_[prio]) == NULL) {
			// nobody at this prio level
			continue;
		}
                /* 
                 * The WRR round for this priority level starts at deficit 0.
                 *  The round ends if some class is found that is ready
                 *  to send and has positive "bytes_alloc_".
                 * Status advances to deficit 1 if some class was found  
                 *  that was able to send except for insufficient
                 *  "bytes_alloc_".
                 * If status was deficit 1 at the end of the first round,
                 *  then status advances to deficit 2.
                 * Another round of WRR is then begun at deficit 2, looking
                 *  for a class to send even with insufficient "bytes_alloc_".
                 */
		deficit = done = 0;
		while (!done) {
                        // look for class at this priority level ok to send
			do {
                                // set up "weight" for WRR
				if (deficit < 2 && cl->bytes_alloc_ <= 0)
					cl->bytes_alloc_ +=
						(int)(cl->allotment_ * M_[cl->pri_]);
                                // anything to send?
				if (cl->demand()) {
					if (first == NULL && cl->permit_borrowing_ && cl->lender_ != NULL)
						first = cl;
					if (!send_permitted(cl, now)) {
                                                // not ok to send right now
						cl->delayed(now);
					} else {
                                                // ok to send, if class has
                                                //  enough "weight" for WRR.
						int bytes = cl->bytes_alloc_;
						if (bytes > 0 || deficit > 1) {
							eligible = cl;
							goto found;
						} else
							deficit = 1;
					}
				}
				cl->bytes_alloc_ = 0;
				cl = cl->peer_;
			} while (cl != active_[prio] && cl != 0);
			if (deficit == 1)
				deficit = 2;
			else
				done = 1;
		}
	}
        // did not find anyone so let first go
	if ((eligible == NULL) && first != NULL) {
		none_found = 1;
		eligible = first;
	}

found:
	// do accounting
	if (eligible != NULL) {
		next_eligible = eligible->peer_;
		eligible->q_->resume();
		if (pending_pkt_ != NULL && !none_found) {
			// reduce our alloc
			// by the packet size.  If we're
			// still positive, we get to go again
			int bytes = eligible->bytes_alloc_;
			hdr_cmn* hdr = hdr_cmn::access(pending_pkt_);
			if (bytes > 0) {
				eligible->bytes_alloc_ -= hdr->size();
			}
			bytes = eligible->bytes_alloc_;
			if (bytes > 0) {
				next_eligible = eligible;
			}
			eligible->update(pending_pkt_, now);
			if (toplevel())
				toplevel_departure(eligible, now);
		}
		active_[eligible->pri_] = next_eligible;
	}
	rval = pending_pkt_;
	pending_pkt_ = NULL;

	return (rval);
}

int
WRR_CBQueue::insert_class(CBQClass *p)
{
	if (CBQueue::insert_class(p) < 0)
		return (-1);
	++cnt_[p->pri_];
	setM();
	return (0);
}

void
WRR_CBQueue::setM()
{
	int i;
	for (i = 0; i <= maxprio_; i++) {
		if (alloc_[i] > 0.0)
                        // allocate "cnt_[i] * maxpkt_" bytes to each
                        //  priority level:
                        M_[i] = cnt_[i] * maxpkt_ * 1.0 / alloc_[i];
                        // allocate "alloc_[i] * 2.0 * cnt_[i] * maxpkt_"
                        //  bytes to each priority level:
                        //  M_[i] = 2.0 * cnt_[i] * maxpkt_;
		else
			M_[i] = 0.0;

		if (M_[i] < 0.0) {
			fprintf(stderr, "M_[i]: %f, cnt_[i]: %d, maxpkt_: %d, alloc_[i]: %f\n",
				M_[i], cnt_[i], maxpkt_, alloc_[i]);
			abort();
		}

	}
	return;
}

/******************** CBQClass definitions **********************/

CBQClass::CBQClass() : cbq_(0), peer_(0), level_peer_(0), lender_(0),
	q_(0), qmon_(0), allotment_(0.0), maxidle_(-1.0), maxrate_(0.0),
	extradelay_(0.0), last_time_(0.0), undertime_(0.0), avgidle_(0.0),
	pri_(-1), level_(-1), delayed_(0), bytes_alloc_(0),
	permit_borrowing_(1)
{
	/* maxidle_ is no longer bound; it is now a method interface */
	bind("priority_", &pri_);
	bind("level_", &level_);
	bind("extradelay_", &extradelay_);
	bind_bool("okborrow_", &permit_borrowing_);

	if (pri_ < 0 || pri_ > (MAXPRIO-1))
		abort();

	if (level_ <= 0 || level_ > MAXLEVEL)
		abort();
}

// why can't these two be inline (?)
int
CBQClass::demand()
{
	return (qmon_->pkts() > 0);
}

int
CBQClass::leaf()
{
	return (level_ == LEAF_LEVEL);
}

/*
 * we are upstream from the queue
 * the queue should be unblocked if the downstream
 * cbq is not busy and blocked otherwise
 *
 * we get our packet from the classifier, because of
 * this the handler is NULL.  Besides the queue downstream
 * from us (Queue::recv) ignores the handler anyhow
 * 
 */
void
CBQClass::recv(Packet *pkt, Handler *h)
{
	if (cbq_->toplevel()) {
		Scheduler* s;
		if ((s = &Scheduler::instance()) != NULL)
			cbq_->toplevel_arrival(this, s->clock());
	}
	send(pkt, h);	// queue packet downstream
	if (!cbq_->blocked()) {
		cbq_->sched();
	}
	return;
}

/*
 * update a class' statistics and all parent classes
 * up to the root
 */
void CBQClass::update(Packet* p, double now)
{
	double idle, avgidle;

	hdr_cmn* hdr = hdr_cmn::access(p);
	int pktsize = hdr->size();

	double tx_time = cbq_->link()->txtime(p);
	double fin_time = now + tx_time;

	idle = (fin_time - last_time_) - (pktsize / maxrate_);
	avgidle = avgidle_;
	avgidle += (idle - avgidle) / POWEROFTWO;
	if (maxidle_ < 0) {
		fprintf(stderr,
			"CBQClass: warning: maxidle_ not configured!\n");
	} else if (avgidle > maxidle_)
		avgidle = maxidle_;
	avgidle_ = avgidle;

	if (avgidle <= 0) {
		undertime_ = fin_time + tx_time *
			(1.0 / allotment_ - 1.0);
		undertime_ += (1-POWEROFTWO) * avgidle;
	}
	last_time_ = fin_time;
	// tail-recurse up to root of tree performing updates
	if (lender_)
		lender_->update(p, now);

	return;
}

/*
 * satisfied: is this class satisfied?
 */

int
CBQClass::satisfied(double now)
{
	if (leaf()) {
		/* leaf is unsat if underlimit with backlog */
		if (undertime_ < now && demand())
			return (0);
		else
			return (1);
	}
	if (undertime_ < now && desc_with_demand())
		return (0);

	return (1);
}

/*
 * desc_with_demand: is there a descendant of this class with demand
 *	really, is there a leaf which is a descendant of me with
 *	a backlog
 */

int
CBQClass::desc_with_demand()
{
	CBQClass *p = cbq_->level(LEAF_LEVEL);
	for (; p != NULL; p = p->level_peer_) {
		if (p->demand() && ancestor(p))
			return (1);
	}
	return (0);
}

/*
 * happens when a class is unable to send because it
 * is being regulated
 */

void CBQClass::delayed(double now)
{
	double delay = undertime_ - now + extradelay_;

	if (delay > 0 && !delayed_) {
		undertime_ += extradelay_;
		undertime_ -= (1-POWEROFTWO) * avgidle_;
		delayed_ = 1;
	}
}

/*
 * return 1 if we are an ancestor of p, 0 otherwise
 */
int
CBQClass::ancestor(CBQClass *p)
{
	if (!p->permit_borrowing_ || p->lender_ == NULL)
		return (0);
	else if (p->lender_ == this)
		return (1);
	return (ancestor(p->lender_));
}

/*
 * change an allotment
 */
void
CBQClass::newallot(double bw)
{
        if (allotment_ < 0)
                allotment_ = 0;
        if (bw < 0)
                bw = 0;
	maxrate_ = bw * ( cbq_->link()->bandwidth() / 8.0 );
	double diff = bw - allotment_;
	allotment_ = bw;
	cbq_->addallot(pri_, diff);
	return;
}


/*
 * OTcl Interface
 */
/* 
 * $class1 parent $class2
 * $class1 borrow $class2
 * $class1 qdisc $queue
 * $class1 allot
 * $class1 allot new-bw
 */
int CBQClass::command(int argc, const char*const* argv)
{
	Tcl& tcl = Tcl::instance();
	if (argc == 2) {
		if (strcmp(argv[1], "allot") == 0) {
			tcl.resultf("%g", allotment_);
			return (TCL_OK);
		}
		if (strcmp(argv[1], "cbq") == 0) {
			if (cbq_ != NULL)
				tcl.resultf("%s", cbq_->name());
			else
				tcl.resultf("");
			return(TCL_OK);
		}
		if (strcmp(argv[1], "qdisc") == 0) {
			if (q_ != NULL)
				tcl.resultf("%s", q_->name());
			else
				tcl.resultf("");
			return (TCL_OK);
		}
		if (strcmp(argv[1], "qmon") == 0) {
			if (qmon_ != NULL)
				tcl.resultf("%s", qmon_->name());
			else
				tcl.resultf("");
			return (TCL_OK);
		}
	} else if (argc == 3) {
		// for now these are the same
		if ((strcmp(argv[1], "parent") == 0)) {

			if (strcmp(argv[2], "none") == 0) {
				lender_ = NULL;
				return (TCL_OK);
			}
			lender_ = (CBQClass*)TclObject::lookup(argv[2]);
			if (lender_ != NULL)
				return (TCL_OK);

			return (TCL_ERROR);
		}
		if (strcmp(argv[1], "qdisc") == 0) {
			q_ = (Queue*) TclObject::lookup(argv[2]);
			if (q_ != NULL)
				return (TCL_OK);
			tcl.resultf("couldn't find object %s",
				argv[2]);
			return (TCL_ERROR);
		}
		if (strcmp(argv[1], "qmon") == 0) {
			qmon_ = (QueueMonitor*) TclObject::lookup(argv[2]);
			if (qmon_ != NULL)
				return (TCL_OK);
			return (TCL_ERROR);
		}
		if (strcmp(argv[1], "allot") == 0) {
			double bw = atof(argv[2]);
			if (bw < 0.0)
				return (TCL_ERROR);
			if (allotment_ != 0.0) {
				tcl.resultf(" class %s already has allotment of %f!",
					    name(), allotment_);
				return (TCL_ERROR);
			}
			allotment_ = bw;
			return (TCL_OK);
		}
		if (strcmp(argv[1], "newallot") == 0) {
			double bw = atof(argv[2]);
			if (bw < 0.0)
				return (TCL_ERROR);
			newallot(bw);
			return (TCL_OK);
		}
		if (strcmp(argv[1], "maxidle") == 0) {
			double m = atof(argv[2]);
			if (m < 0.0) {
				tcl.resultf("invalid maxidle value %s (must be non-negative)",
					    argv[2]);
				return (TCL_ERROR);
			}
			maxidle_ = m;
			return (TCL_OK);
		}
	}
	return (Connector::command(argc, argv));
}