semantic-packetqueue.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1997 The 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 Daedalus Research
 *  Group at the University of California at Berkeley.
 * 4. Neither the name of the University nor of the Research Group 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.
 *
 * semantic-packetqueue.cc: contributed by the Daedalus Research Group, 
 * UC Berkeley (http://daedalus.cs.berkeley.edu).
 */

#include "ip.h"
#include "tcp.h"
#include "template.h"
#include "semantic-packetqueue.h"
#include "ack-recons.h"

static class SemanticPacketQueueClass : public TclClass {
public:
    SemanticPacketQueueClass() : TclClass("PacketQueue/Semantic") {}
    TclObject* create(int , const char*const*) {
        return (new SemanticPacketQueue());
    }
} class_semanticpacketqueue;

SemanticPacketQueue::SemanticPacketQueue() : ack_count(0), data_count(0), 
    acks_to_send(0), marked_count_(0), unmarked_count_(0) 
{
    bind_bool("acksfirst_", &acksfirst_);
    bind_bool("filteracks_", &filteracks_);
    bind_bool("reconsAcks_", &reconsAcks_);
    bind_bool("replace_head_", &replace_head_);
    bind_bool("priority_drop_", &priority_drop_);
    bind_bool("random_drop_", &random_drop_);
    bind_bool("random_ecn_", &random_ecn_);
}   

int
SemanticPacketQueue::command(int argc, const char*const* argv)
{
    if (argc == 3) {
        if (strcmp(argv[1], "ackrecons") == 0) {
            if ((reconsCtrl_ = (AckReconsController *) 
                 TclObject::lookup(argv[2]))) {
                reconsCtrl_->spq_ = this;
                reconsAcks_ = 1;
            }
        }
        return (TCL_OK);
    }
    return (TclObject::command(argc, argv));
}

/* 
 * Deque TCP acks before any other type of packet.
 */
Packet* 
SemanticPacketQueue::deque_acksfirst() {
    Packet* p = head_;
    Packet* pp = NULL;
    packet_t type;

    if (ack_count > 0) {
        while (p) {
            type = hdr_cmn::access(p)->ptype_;
            if (type == PT_ACK)
                break;
            pp = p;
            p = p->next_;
        }
        if (!p) 
            fprintf(stderr, "In deque_acksfirst(): ack_count: %d but no acks in queue, length = %d\n", ack_count, length());
        PacketQueue::remove(p, pp);
    } else {
        p = PacketQueue::deque();
    }
    return p;
}

/*
 * Purge the queue of acks that are older (i.e., have a smaller sequence 
 * number) than the most recent ack. If replace_head is set, the most recent
 * ack (pointed to by pkt) takes the place of the oldest ack that is purged. 
 * Otherwise, it remains at the tail of the queue.  pkt must be an ACK -- this
 * is checked by the caller.
 */
void
SemanticPacketQueue::filterAcks(Packet *pkt, int replace_head) 
{
    int done_replacement = 0;

    Packet *p, *pp, *new_p;
    hdr_tcp *tcph = hdr_tcp::access(pkt);
    int &ack = tcph->seqno();

    hdr_ip *iph = hdr_ip::access(pkt);
    for (p = head(), pp = p; p != 0; ) {
        /* 
         * Check if packet in the queue belongs to the 
         * same connection as the most recent ack
         */
        if (compareFlows(hdr_ip::access(p), iph)) {
            /* check if queued packet is an ack */
            if (hdr_cmn::access(p)->ptype_==PT_ACK) {
                hdr_tcp *th = hdr_tcp::access(p);
                /* is this ack older than the current one? */
                if ((th->seqno() < ack) ||
                    (replace_head && th->seqno() == ack)) { 
                    /* 
                     * If we haven't yet replaced the ack 
                     * closest to the head with the most 
                     * recent ack, do so now.
                     */
                    if (replace_head && pkt != p &&
                        !done_replacement) {
                        PacketQueue::remove(pkt);
                        ack_count--; /* XXX */
                        pkt->next_ = p;
                        if (pp)
                            pp->next_ = pkt;
                        pp = pkt;
                        done_replacement = 1;
                        continue;
                    } else if (done_replacement||pkt != p){
                        new_p = p->next_;
                        /* 
                         * If p is in scheduler queue,
                         * cancel the event. Also, 
                         * print out a warning because
                         * this should never happen.
                         */
                        Scheduler &s = Scheduler::instance();
                        if (s.lookup(p->uid_)) {
                            s.cancel(p);
                            fprintf(stderr, "Warning: In filterAcks(): packet being dropped from queue is in scheduler queue\n");
                        }
                        PacketQueue::remove(p, pp);
                        /* XXX should drop, but we
                           don't have access to q */
                        Packet::free(p); 
                        ack_count--;
                        p = new_p;
                        continue;
                    }
                    if (ack_count <= 0)
                        fprintf(stderr, 
                            "oops! ackcount %d\n",
                            ack_count);
                }
            }
        }
        pp = p;
        p = p->next_;
    }
}

/* check if packet is marked */
int
SemanticPacketQueue::isMarked(Packet *p) 
{
    return (hdr_flags::access(p)->fs_);
}


/* pick out the index'th of the appropriate kind (marked/unmarked) depending on markedFlag */
Packet*
SemanticPacketQueue::lookup(int index, int markedFlag) 
{
    if (index < 0) {
        fprintf(stderr, "In SemanticPacketQueue::lookup(): index = %d\n", index);
        return (NULL);
    }
    for (Packet* p = head_; p != 0; p = p->next_) {
        if (isMarked(p) == markedFlag)
            if (--index < 0)
                return (p);
    }
    return (NULL);
}

/*
 * If random_ecn_ is set, pick out the packet for ECN at random from among the
 * packets in the queue and the packet that just arrived ('pkt'). Otherwise, just
 * pick the packet that just arrived.
 */
Packet*
SemanticPacketQueue::pickPacketForECN(Packet* pkt) 
{
    Packet *victim;
    int victimIndex;

    if (random_ecn_) {
        victimIndex = Random::integer(length()+1);
        if (victimIndex == length())
            victim = pkt;
        else
            victim = PacketQueue::lookup(victimIndex);
    }
    else 
        victim = pkt;
    return (victim);
}
        

/* 
 * If priority_drop_ is set, drop marked packets before unmarked ones.
 * If in addition or separately random_drop_ is set, use randomization in
 * picking out the victim. XXX not used at present 
 */
Packet*
SemanticPacketQueue::pickPacketToDrop()
{
    Packet *victim;
    int victimIndex, victimMarked;

    if (!priority_drop_) {
        if (random_drop_)
            victim=PacketQueue::lookup(Random::integer(length()));
        else
            victim = PacketQueue::lookup(length() - 1);
    } else {
        /* if there are marked (low priority) packets */
        if (marked_count_) {
            victimMarked = 1;
            if (!random_drop_) 
                victimIndex = marked_count_ - 1;
            else
                victimIndex = Random::integer(marked_count_);
        }
        else {
            victimMarked = 0;
            if (!random_drop_)
                victimIndex = unmarked_count_ - 1;
            else
                victimIndex = Random::integer(unmarked_count_);
        }
        victim = lookup(victimIndex, victimMarked);
    }
    return (victim);
}
                
Packet*
SemanticPacketQueue::enque(Packet *pkt)
{
    if (reconsAcks_&&(hdr_cmn::access(pkt)->ptype_==PT_ACK)) {
        reconsCtrl_->recv(pkt);
        return NULL;
    }
    if (hdr_cmn::access(pkt)->ptype_ == PT_ACK)
        ack_count++;
    else
        data_count++;
    if (isMarked(pkt)) 
        marked_count_++;
    else
        unmarked_count_++;

    Packet* pt = PacketQueue::enque(pkt); /* actually enque the packet */

    if (filteracks_ && (hdr_cmn::access(pkt)->ptype_==PT_ACK))
        filterAcks(pkt, replace_head_);
    return pt;
}

Packet *
SemanticPacketQueue::deque()
{
    Packet *pkt;

    if (acksfirst_)
        pkt = deque_acksfirst();
    else
        pkt = PacketQueue::deque();
    
    if (pkt) {
        if (hdr_cmn::access(pkt)->ptype_ == PT_ACK)
            ack_count--;
        else
            data_count--;
        if (isMarked(pkt))
            marked_count_--;
        else
            unmarked_count_--;
    }
    return pkt;
}

void 
SemanticPacketQueue::remove(Packet *pkt)
{
    PacketQueue::remove(pkt);
    if (pkt) {
        if (hdr_cmn::access(pkt)->ptype_ == PT_ACK)
            ack_count--;
        else
            data_count--;
        if (isMarked(pkt))
            marked_count_--;
        else
            unmarked_count_--;
    }
}

---