rq.cc

Go to the documentation of this file.

/*
 * Copyright (c) Intel Corporation 2001. All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
*/

/*
 * 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

---