rq.cc

Go to the documentation of this file.

/*
 * Copyright (c) Intel Corporation 2001. All rights reserved.
 *
 * License is granted to copy, to use, and to make and to use derivative
 * works for research and evaluation purposes, provided that Intel is
 * acknowledged in all documentation pertaining to any such copy or
 * derivative work. Intel grants no other licenses expressed or
 * implied. The Intel trade name should not be used in any advertising
 * without its written permission. 
 *
 * INTEL CORPORATION MAKES NO REPRESENTATIONS CONCERNING EITHER THE
 * MERCHANTABILITY OF THIS SOFTWARE OR THE SUITABILITY OF THIS SOFTWARE
 * FOR ANY PARTICULAR PURPOSE.  The software is provided "as is" without
 * express or implied warranty of any kind.
 *
 * These notices must be retained in any copies of any part of this
 * software. 
 */

/*
 * Copyright (c) 1991-1997 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 Computer Systems
 *      Engineering Group at Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory 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.
 *
 */

#include "rq.h"

ReassemblyQueue::seginfo* ReassemblyQueue::freelist_ = NULL;

ReassemblyQueue::seginfo* ReassemblyQueue::newseginfo()
{
        seginfo *s;
        
        if( (s = freelist_) ){
                freelist_ = s->next_;
                return s;
        }else{
                return new seginfo;
        }
}

void ReassemblyQueue::deleteseginfo(ReassemblyQueue::seginfo* s)
{
        s->next_ = freelist_;
        freelist_ = s;
}

/*
 * unlink a seginfo from its FIFO
 */
void
ReassemblyQueue::fremove(seginfo* p)
{
        if (hint_ == p)
                hint_ = NULL;

        if (p->prev_)
                p->prev_->next_ = p->next_;
        else
                head_ = p->next_;
        if (p->next_)
                p->next_->prev_ = p->prev_;
        else
                tail_ = p->prev_;
}

/*
 * unlink a seginfo from its LIFO
 */
void
ReassemblyQueue::sremove(seginfo* p)
{
        if (hint_ == p)
                hint_ = NULL;

        if (p->sprev_)
                p->sprev_->snext_ = p->snext_;
        else
                top_ = p->snext_;
        if (p->snext_)
                p->snext_->sprev_ = p->sprev_;
        else
                bottom_ = p->sprev_;

}

/*
 * push a seginfo on the LIFO
 */
void
ReassemblyQueue::push(seginfo *p)
{
        p->snext_ = top_;
        p->sprev_ = NULL;
        top_ = p;
        if (p->snext_)
                p->snext_->sprev_ = p;
        else
                bottom_ = p;
}

/*
 * counts: return the # of blks and byte counts in
 * them starting at the given node
 */
void
ReassemblyQueue::cnts(seginfo *p, int& blkcnt, int& bytecnt)
{
        int blks = 0;
        int bytes = 0;

        while (p != NULL) {
                ++blks;
                bytes += (p->endseq_ - p->startseq_);
                p = p->next_;
        }
        blkcnt = blks;
        bytecnt = bytes;
        return;
}


/*
 * clear out reassembly queue and stack
 */

void
ReassemblyQueue::clear()
{
        // clear stack and end of queue
        tail_ = top_ = bottom_ = hint_ = NULL;

        seginfo *p = head_;
        while (head_) {
                p = head_;
                head_= head_->next_;
                ReassemblyQueue::deleteseginfo(p);
        }
        tail_ = NULL;
        total_ = 0;
        return;
}

/*
 * clear out reassembly queue (and stack) up
 * to the given sequence number
 */

TcpFlag
ReassemblyQueue::clearto(TcpSeq seq)
{
        TcpFlag flag = 0;
        seginfo *p = head_, *q;
        while (p) {
                if (p->endseq_ <= seq) {
                        q = p->next_;
                        flag |= p->pflags_;
                        total_ -= (p->endseq_ - p->startseq_);
                        sremove(p);
                        fremove(p);
                        ReassemblyQueue::deleteseginfo(p);
                        p = q;
                } else
                        break;
        }
        /* we might be trimming in the middle */
        if (p && p->startseq_ <= seq && p->endseq_ > seq) {
                total_ -= (seq - p->startseq_);
                p->startseq_ = seq;
                flag |= p->pflags_;
        }
        return flag;
}

/*
 * gensack() -- generate 'maxsblock' sack blocks (start/end seq pairs)
 * at specified address
 * returns the number of blocks written into the buffer specified
 *
 * According to RFC2018, a sack block contains:
 *      left edge of block (first seq # of the block)
 *      right edge of block (seq# immed. following last seq# of the block)
 */

int
ReassemblyQueue::gensack(int *sacks, int maxsblock)
{
        seginfo *p = top_;
        int cnt = maxsblock;

        while (p && maxsblock) {
                *sacks++ = p->startseq_;
                *sacks++ = p->endseq_;
                --maxsblock;
                p = p->snext_;
        }
        return (cnt - maxsblock);
}

/*
 * dumplist -- print out FIFO and LIFO (for debugging)
 */

void
ReassemblyQueue::dumplist()
{

        printf("FIFO [size:%d]: ", total_);
        if (head_ == NULL) {
                printf("NULL\n");
        } else {
                register seginfo* p = head_;
                while (p != NULL) {
                        if (p->rqflags_ & RQF_MARK) {
                                printf("OOPS: LOOP1\n");
                                abort();
                        }
                        printf("[->%d, %d<-<f:0x%x,c:%d>]",
                                p->startseq_, p->endseq_, p->pflags_, p->cnt_);
                        p->rqflags_ |= RQF_MARK;
                        p = p->next_;
                }
                printf("\n");
                p = tail_;
                while (p != NULL) {
                        printf("[->%d, %d<-]",
                                p->startseq_, p->endseq_);
                        p = p->prev_;
                }
                printf("\n");
        }

        printf("LIFO: ");
        if (top_ == NULL) {
                printf("NULL\n");
        } else {
                register seginfo* s = top_;
                while (s != NULL) {
                        if (s->rqflags_ & RQF_MARK)
                                s->rqflags_ &= ~RQF_MARK;
                        else {
                                printf("OOPS: LOOP2\n");
                                abort();
                        }
                        printf("[->%d, %d<-]",
                                s->startseq_, s->endseq_);
                        s = s->snext_;
                }
                printf("\n");
                s = bottom_;
                while (s != NULL) {
                        printf("[->%d, %d<-]",
                                s->startseq_, s->endseq_);
                        s = s->sprev_;
                }
                printf("\n");
        }
        printf("RCVNXT: %d\n", rcv_nxt_);
        printf("\n");
        fflush(stdout);
}

/*
 *
 * add() -- add a segment to the reassembly queue
 *      this is where the real action is...
 *      add the segment to both the LIFO and FIFO
 *
 * returns the aggregate header flags covering the block
 * just inserted (for historical reasons)
 *
 * add start/end seq to reassembly queue
 * start specifies starting seq# for segment, end specifies
 * last seq# number in the segment plus one
 */

TcpFlag
ReassemblyQueue::add(TcpSeq start, TcpSeq end, TcpFlag tiflags, RqFlag rqflags)
{

        int needmerge = FALSE;
        int altered = FALSE;
        int initcnt = 1;        // initial value of cnt_ for new blk

        if (end < start) {
                fprintf(stderr, "ReassemblyQueue::add() - end(%d) before start(%d)\n",
                        end, start);
                abort();
        }

        if (head_ == NULL) {
                if (top_ != NULL) {
                        fprintf(stderr, "ReassemblyQueue::add() - problem: FIFO empty, LIFO not\n");
                        abort();
                }

                // nobody there, just insert this one


                tail_ = head_ = top_ = bottom_ =  ReassemblyQueue::newseginfo();
                head_->prev_ = head_->next_ = head_->snext_ = head_->sprev_ = NULL;
                head_->startseq_ = start;
                head_->endseq_ = end;
                head_->pflags_ = tiflags;
                head_->rqflags_ = rqflags;
                head_->cnt_ = initcnt;

                total_ = (end - start);

                //
                // this shouldn't really happen, but
                // do the right thing just in case
                if (rcv_nxt_ >= start)
                        rcv_nxt_ = end;

                return (tiflags);
        } else {

again2:
                seginfo *p = NULL, *q = NULL, *n, *r;

                //
                // in the code below, arrange for:
                // q: points to segment after this one
                // p: points to segment before this one
                //

                if (start >= tail_->endseq_) {
                        // at tail, no overlap
                        p = tail_;
                        if (start == tail_->endseq_)
                                needmerge = TRUE;
                        goto endfast;
                }

                if (end <= head_->startseq_) {
                        // at head, no overlap
                        q = head_;
                        if (end == head_->startseq_)
                                needmerge = TRUE;
                        goto endfast;
                }

                //
                // search for segments before and after
                // the new one; could be overlapped
                //
                q = head_;
                while (q && q->startseq_ < end)
                        q = q->next_;

                p = tail_;
                while (p && p->endseq_ > start)
                        p = p->prev_;

#ifdef notdef
printf("Thinking of merging (s:%d, e:%d), p:%p (%d,%d), q:%p (%d,%d) into: \n",
start, end, p, q,
        p ? p->startseq_ : 0,
        p ? p->endseq_ : 0,
        q ? n->startseq_ : 0,
        q ? n->endseq_ : 0);
#endif


                //
                // kill anything that is completely overlapped
                //
                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

---