00001 /* 00002 * Copyright (c) Intel Corporation 2001. All rights reserved. 00003 * 00004 * Licensed under the Apache License, Version 2.0 (the "License"); 00005 * you may not use this file except in compliance with the License. 00006 * You may obtain a copy of the License at 00007 * http://www.apache.org/licenses/LICENSE-2.0 00008 * 00009 * Unless required by applicable law or agreed to in writing, software 00010 * distributed under the License is distributed on an "AS IS" BASIS, 00011 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00012 * See the License for the specific language governing permissions and 00013 * limitations under the License. 00014 */ 00015 00016 /* 00017 * Copyright (c) 1991-1997 Regents of the University of California. 00018 * All rights reserved. 00019 * 00020 * Redistribution and use in source and binary forms, with or without 00021 * modification, are permitted provided that the following conditions 00022 * are met: 00023 * 1. Redistributions of source code must retain the above copyright 00024 * notice, this list of conditions and the following disclaimer. 00025 * 2. Redistributions in binary form must reproduce the above copyright 00026 * notice, this list of conditions and the following disclaimer in the 00027 * documentation and/or other materials provided with the distribution. 00028 * 3. All advertising materials mentioning features or use of this software 00029 * must display the following acknowledgement: 00030 * This product includes software developed by the Computer Systems 00031 * Engineering Group at Lawrence Berkeley Laboratory. 00032 * 4. Neither the name of the University nor of the Laboratory may be used 00033 * to endorse or promote products derived from this software without 00034 * specific prior written permission. 00035 * 00036 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00037 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00038 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00039 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00040 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00041 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00042 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00043 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00044 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00045 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00046 * SUCH DAMAGE. 00047 * 00048 */ 00049 00050 #ifndef ns_rq_h 00051 #define ns_rq_h 00052 00053 #define RQF_MARK 1 // for debugging 00054 00055 typedef int TcpSeq; // a TCP sequence number 00056 typedef int TcpFlag; // holds flags from TCP hdr 00057 typedef int RqFlag; // meta data (owned by ReassemblyQueue) 00058 00059 #ifndef TRUE 00060 #define TRUE 1 00061 #endif 00062 00063 #ifndef FALSE 00064 #define FALSE 0 00065 #endif 00066 00067 #define RQC_CNTDUPS FALSE // count exact dups on add()? 00068 00069 #include <stdio.h> 00070 #include <stdlib.h> 00071 00072 /* 00073 * ReassemblyQueue: keeps both a stack and linked list of segments 00074 * FIFO maintains list in sequence # order (very often a FIFO) 00075 * LIFO maintains list in insert order (used for generation of (D)SACKS 00076 * 00077 * Note that this code attempts to be largely independent of all 00078 * other code (no include files from the rest of the simulator) 00079 * 00080 * July, 2001 00081 * kfall@intel.com 00082 */ 00083 00084 /* 01/03 Tom Kelly <ctk21@cam.ac.uk> 00085 * 00086 * Made the newseginfo and deleteseginfo calls to avoid new/delete 00087 * overhead in generating SACK blocks good for HSTCP; see scoreboard-rq 00088 */ 00089 00090 class ReassemblyQueue { 00091 struct seginfo { 00092 seginfo* next_; // next on FIFO list 00093 seginfo* prev_; // prev on FIFO list 00094 seginfo* snext_; // next on LIFO list 00095 seginfo* sprev_; // prev on LIFO list 00096 00097 TcpSeq startseq_; // starting seq 00098 TcpSeq endseq_; // ending seq + 1 00099 TcpFlag pflags_; // flags derived from tcp hdr 00100 RqFlag rqflags_; // book-keeping flags 00101 int cnt_; // refs to this block 00102 }; 00103 00104 public: 00105 ReassemblyQueue(TcpSeq& rcvnxt) : 00106 head_(NULL), tail_(NULL), top_(NULL), bottom_(NULL), hint_(NULL), total_(0), rcv_nxt_(rcvnxt) { }; 00107 int empty() { return (head_ == NULL); } 00108 int add(TcpSeq sseq, TcpSeq eseq, TcpFlag pflags, RqFlag rqflags = 0); 00109 int maxseq() { return (tail_ ? (tail_->endseq_) : -1); } 00110 int minseq() { return (head_ ? (head_->startseq_) : -1); } 00111 int total() { return total_; } 00112 int nexthole(TcpSeq seq, int&, int&); // find next hole above seq, also 00113 // include cnt of following blk 00114 00115 int gensack(int *sacks, int maxsblock); 00116 00117 void clear(); // clear FIFO, LIFO 00118 void init(TcpSeq rcvnxt) { rcv_nxt_ = rcvnxt; clear(); } 00119 TcpFlag clearto(TcpSeq); // clear FIFO, LIFO up to seq # 00120 TcpFlag cleartonxt() { // clear FIFO, LIFO to rcv_nxt_ 00121 return (clearto(rcv_nxt_)); 00122 } 00123 void dumplist(); // for debugging 00124 00125 // cache of allocated seginfo blocks 00126 static seginfo* newseginfo(); 00127 static void deleteseginfo(seginfo*); 00128 00129 protected: 00130 static seginfo* freelist_; // cache of free seginfo blocks 00131 00132 seginfo* head_; // head of segs linked list 00133 seginfo* tail_; // end of segs linked list 00134 00135 seginfo* top_; // top of stack 00136 seginfo* bottom_; // bottom of stack 00137 seginfo* hint_; // hint for nexthole() function 00138 int total_; // # bytes in Reassembly Queue 00139 00140 // rcv_nxt_ is a reference to an externally allocated TcpSeq 00141 // (aka integer)that will be updated with the highest in-sequence sequence 00142 // number added [plus 1] by the user. This is the value ordinarily used 00143 // within TCP to set rcv_nxt and thus to set the ACK field. It is also 00144 // used in the SACK sender as sack_min_ 00145 00146 TcpSeq& rcv_nxt_; // start seq of next expected thing 00147 TcpFlag coalesce(seginfo*, seginfo*, seginfo*); 00148 void fremove(seginfo*); // remove from FIFO 00149 void sremove(seginfo*); // remove from LIFO 00150 void push(seginfo*); // add to LIFO 00151 void cnts(seginfo *, int&, int&); // byte/blk counts 00152 }; 00153 00154 #endif