1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3 * Copyright (c) 2010 Adrian Sai-wah Tam
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Author: Adrian Sai-wah Tam <adrian.sw.tam@gmail.com>
19 */
20
21 #include "ns3/packet.h"
22 #include "ns3/log.h"
23 #include "tcp-rx-buffer.h"
24
25 namespace ns3 {
26
27 NS_LOG_COMPONENT_DEFINE ("TcpRxBuffer");
28
29 NS_OBJECT_ENSURE_REGISTERED (TcpRxBuffer);
30
31 TypeId
GetTypeId(void)32 TcpRxBuffer::GetTypeId (void)
33 {
34 static TypeId tid = TypeId ("ns3::TcpRxBuffer")
35 .SetParent<Object> ()
36 .SetGroupName ("Internet")
37 .AddConstructor<TcpRxBuffer> ()
38 .AddTraceSource ("NextRxSequence",
39 "Next sequence number expected (RCV.NXT)",
40 MakeTraceSourceAccessor (&TcpRxBuffer::m_nextRxSeq),
41 "ns3::SequenceNumber32TracedValueCallback")
42 ;
43 return tid;
44 }
45
46 /* A user is supposed to create a TcpSocket through a factory. In TcpSocket,
47 * there are attributes SndBufSize and RcvBufSize to control the default Tx and
48 * Rx window sizes respectively, with default of 128 KiByte. The attribute
49 * RcvBufSize is passed to TcpRxBuffer by TcpSocketBase::SetRcvBufSize() and in
50 * turn, TcpRxBuffer:SetMaxBufferSize(). Therefore, the m_maxBuffer value
51 * initialized below is insignificant.
52 */
TcpRxBuffer(uint32_t n)53 TcpRxBuffer::TcpRxBuffer (uint32_t n)
54 : m_nextRxSeq (n), m_gotFin (false), m_size (0), m_maxBuffer (32768), m_availBytes (0)
55 {
56 }
57
~TcpRxBuffer()58 TcpRxBuffer::~TcpRxBuffer ()
59 {
60 }
61
62 SequenceNumber32
NextRxSequence(void) const63 TcpRxBuffer::NextRxSequence (void) const
64 {
65 return m_nextRxSeq;
66 }
67
68 void
SetNextRxSequence(const SequenceNumber32 & s)69 TcpRxBuffer::SetNextRxSequence (const SequenceNumber32& s)
70 {
71 m_nextRxSeq = s;
72 }
73
74 uint32_t
MaxBufferSize(void) const75 TcpRxBuffer::MaxBufferSize (void) const
76 {
77 return m_maxBuffer;
78 }
79
80 void
SetMaxBufferSize(uint32_t s)81 TcpRxBuffer::SetMaxBufferSize (uint32_t s)
82 {
83 m_maxBuffer = s;
84 }
85
86 uint32_t
Size(void) const87 TcpRxBuffer::Size (void) const
88 {
89 return m_size;
90 }
91
92 uint32_t
Available() const93 TcpRxBuffer::Available () const
94 {
95 return m_availBytes;
96 }
97
98 void
IncNextRxSequence()99 TcpRxBuffer::IncNextRxSequence ()
100 {
101 NS_LOG_FUNCTION (this);
102 // Increment nextRxSeq is valid only if we don't have any data buffered,
103 // this is supposed to be called only during the three-way handshake
104 NS_ASSERT (m_size == 0);
105 m_nextRxSeq++;
106 }
107
108 // Return the lowest sequence number that this TcpRxBuffer cannot accept
109 SequenceNumber32
MaxRxSequence(void) const110 TcpRxBuffer::MaxRxSequence (void) const
111 {
112 if (m_gotFin)
113 { // No data allowed beyond FIN
114 return m_finSeq;
115 }
116 else if (m_data.size () && m_nextRxSeq > m_data.begin ()->first)
117 { // No data allowed beyond Rx window allowed
118 return m_data.begin ()->first + SequenceNumber32 (m_maxBuffer);
119 }
120 return m_nextRxSeq + SequenceNumber32 (m_maxBuffer);
121 }
122
123 void
SetFinSequence(const SequenceNumber32 & s)124 TcpRxBuffer::SetFinSequence (const SequenceNumber32& s)
125 {
126 NS_LOG_FUNCTION (this);
127
128 m_gotFin = true;
129 m_finSeq = s;
130 if (m_nextRxSeq == m_finSeq) ++m_nextRxSeq;
131 }
132
133 bool
Finished(void)134 TcpRxBuffer::Finished (void)
135 {
136 return (m_gotFin && m_finSeq < m_nextRxSeq);
137 }
138
139 bool
Add(Ptr<Packet> p,TcpHeader const & tcph)140 TcpRxBuffer::Add (Ptr<Packet> p, TcpHeader const& tcph)
141 {
142 NS_LOG_FUNCTION (this << p << tcph);
143
144 uint32_t pktSize = p->GetSize ();
145 SequenceNumber32 headSeq = tcph.GetSequenceNumber ();
146 SequenceNumber32 tailSeq = headSeq + SequenceNumber32 (pktSize);
147 NS_LOG_LOGIC ("Add pkt " << p << " len=" << pktSize << " seq=" << headSeq
148 << ", when NextRxSeq=" << m_nextRxSeq << ", buffsize=" << m_size);
149
150 // Trim packet to fit Rx window specification
151 if (headSeq < m_nextRxSeq) headSeq = m_nextRxSeq;
152 if (m_data.size ())
153 {
154 SequenceNumber32 maxSeq = m_data.begin ()->first + SequenceNumber32 (m_maxBuffer);
155 if (maxSeq < tailSeq) tailSeq = maxSeq;
156 if (tailSeq < headSeq) headSeq = tailSeq;
157 }
158 // Remove overlapped bytes from packet
159 BufIterator i = m_data.begin ();
160 while (i != m_data.end () && i->first <= tailSeq)
161 {
162 SequenceNumber32 lastByteSeq = i->first + SequenceNumber32 (i->second->GetSize ());
163 if (lastByteSeq > headSeq)
164 {
165 if (i->first > headSeq && lastByteSeq < tailSeq)
166 { // Rare case: Existing packet is embedded fully in the new packet
167 m_size -= i->second->GetSize ();
168 m_data.erase (i++);
169 continue;
170 }
171 if (i->first <= headSeq)
172 { // Incoming head is overlapped
173 headSeq = lastByteSeq;
174 }
175 if (lastByteSeq >= tailSeq)
176 { // Incoming tail is overlapped
177 tailSeq = i->first;
178 }
179 }
180 ++i;
181 }
182 // We now know how much we are going to store, trim the packet
183 if (headSeq >= tailSeq)
184 {
185 NS_LOG_LOGIC ("Nothing to buffer");
186 return false; // Nothing to buffer anyway
187 }
188 else
189 {
190 uint32_t start = static_cast<uint32_t> (headSeq - tcph.GetSequenceNumber ());
191 uint32_t length = static_cast<uint32_t> (tailSeq - headSeq);
192 p = p->CreateFragment (start, length);
193 NS_ASSERT (length == p->GetSize ());
194 }
195 // Insert packet into buffer
196 NS_ASSERT (m_data.find (headSeq) == m_data.end ()); // Shouldn't be there yet
197 m_data [ headSeq ] = p;
198
199 if (headSeq > m_nextRxSeq)
200 {
201 // Generate a new SACK block
202 UpdateSackList (headSeq, tailSeq);
203 }
204
205 NS_LOG_LOGIC ("Buffered packet of seqno=" << headSeq << " len=" << p->GetSize ());
206 // Update variables
207 m_size += p->GetSize (); // Occupancy
208 for (i = m_data.begin (); i != m_data.end (); ++i)
209 {
210 if (i->first < m_nextRxSeq)
211 {
212 continue;
213 }
214 else if (i->first > m_nextRxSeq)
215 {
216 break;
217 };
218 m_nextRxSeq = i->first + SequenceNumber32 (i->second->GetSize ());
219 m_availBytes += i->second->GetSize ();
220 ClearSackList (m_nextRxSeq);
221 }
222 NS_LOG_LOGIC ("Updated buffer occupancy=" << m_size << " nextRxSeq=" << m_nextRxSeq);
223 if (m_gotFin && m_nextRxSeq == m_finSeq)
224 { // Account for the FIN packet
225 ++m_nextRxSeq;
226 };
227 return true;
228 }
229
230 uint32_t
GetSackListSize() const231 TcpRxBuffer::GetSackListSize () const
232 {
233 NS_LOG_FUNCTION (this);
234
235 return static_cast<uint32_t> (m_sackList.size ());
236 }
237
238 void
UpdateSackList(const SequenceNumber32 & head,const SequenceNumber32 & tail)239 TcpRxBuffer::UpdateSackList (const SequenceNumber32 &head, const SequenceNumber32 &tail)
240 {
241 NS_LOG_FUNCTION (this << head << tail);
242 NS_ASSERT (head > m_nextRxSeq);
243
244 TcpOptionSack::SackBlock current;
245 current.first = head;
246 current.second = tail;
247
248 // The block "current" has been safely stored. Now we need to build the SACK
249 // list, to be advertised. From RFC 2018:
250 // (a) The first SACK block (i.e., the one immediately following the
251 // kind and length fields in the option) MUST specify the contiguous
252 // block of data containing the segment which triggered this ACK,
253 // unless that segment advanced the Acknowledgment Number field in
254 // the header. This assures that the ACK with the SACK option
255 // reflects the most recent change in the data receiver's buffer
256 // queue.
257 //
258 // (b) The data receiver SHOULD include as many distinct SACK blocks as
259 // possible in the SACK option. Note that the maximum available
260 // option space may not be sufficient to report all blocks present in
261 // the receiver's queue.
262 //
263 // (c) The SACK option SHOULD be filled out by repeating the most
264 // recently reported SACK blocks (based on first SACK blocks in
265 // previous SACK options) that are not subsets of a SACK block
266 // already included in the SACK option being constructed. This
267 // assures that in normal operation, any segment remaining part of a
268 // non-contiguous block of data held by the data receiver is reported
269 // in at least three successive SACK options, even for large-window
270 // TCP implementations [RFC1323]). After the first SACK block, the
271 // following SACK blocks in the SACK option may be listed in
272 // arbitrary order.
273
274 m_sackList.push_front (current);
275
276 // We have inserted the block at the beginning of the list. Now, we should
277 // check if any existing blocks overlap with that.
278 bool updated = false;
279 TcpOptionSack::SackList::iterator it = m_sackList.begin ();
280 TcpOptionSack::SackBlock begin = *it;
281 TcpOptionSack::SackBlock merged;
282 ++it;
283
284 // Iterates until we examined all blocks in the list (maximum 4)
285 while (it != m_sackList.end ())
286 {
287 current = *it;
288
289 // This is a left merge:
290 // [current_first; current_second] [beg_first; beg_second]
291 if (begin.first == current.second)
292 {
293 NS_ASSERT (current.first < begin.second);
294 merged = TcpOptionSack::SackBlock (current.first, begin.second);
295 updated = true;
296 }
297 // while this is a right merge
298 // [begin_first; begin_second] [current_first; current_second]
299 else if (begin.second == current.first)
300 {
301 NS_ASSERT (begin.first < current.second);
302 merged = TcpOptionSack::SackBlock (begin.first, current.second);
303 updated = true;
304 }
305
306 // If we have merged the blocks (and the result is in merged) we should
307 // delete the current block (it), the first block, and insert the merged
308 // one at the beginning.
309 if (updated)
310 {
311 m_sackList.erase (it);
312 m_sackList.pop_front ();
313 m_sackList.push_front (merged);
314 it = m_sackList.begin ();
315 begin = *it;
316 updated = false;
317 }
318
319 ++it;
320 }
321
322 // Since the maximum blocks that fits into a TCP header are 4, there's no
323 // point on maintaining the others.
324 if (m_sackList.size () > 4)
325 {
326 m_sackList.pop_back ();
327 }
328
329 // Please note that, if a block b is discarded and then a block contiguous
330 // to b is received, only that new block (without the b part) is reported.
331 // This is perfectly fine for the RFC point (a), given that we do not report any
332 // overlapping blocks shortly after.
333 }
334
335 void
ClearSackList(const SequenceNumber32 & seq)336 TcpRxBuffer::ClearSackList (const SequenceNumber32 &seq)
337 {
338 NS_LOG_FUNCTION (this << seq);
339
340 TcpOptionSack::SackList::iterator it;
341 for (it = m_sackList.begin (); it != m_sackList.end (); )
342 {
343 TcpOptionSack::SackBlock block = *it;
344 NS_ASSERT (block.first < block.second);
345
346 if (block.second <= seq)
347 {
348 it = m_sackList.erase (it);
349 }
350 else
351 {
352 it++;
353 }
354 }
355 }
356
357 TcpOptionSack::SackList
GetSackList() const358 TcpRxBuffer::GetSackList () const
359 {
360 return m_sackList;
361 }
362
363 Ptr<Packet>
Extract(uint32_t maxSize)364 TcpRxBuffer::Extract (uint32_t maxSize)
365 {
366 NS_LOG_FUNCTION (this << maxSize);
367
368 uint32_t extractSize = std::min (maxSize, m_availBytes);
369 NS_LOG_LOGIC ("Requested to extract " << extractSize << " bytes from TcpRxBuffer of size=" << m_size);
370 if (extractSize == 0) return nullptr; // No contiguous block to return
371 NS_ASSERT (m_data.size ()); // At least we have something to extract
372 Ptr<Packet> outPkt = Create<Packet> (); // The packet that contains all the data to return
373 BufIterator i;
374 while (extractSize)
375 { // Check the buffered data for delivery
376 i = m_data.begin ();
377 NS_ASSERT (i->first <= m_nextRxSeq); // in-sequence data expected
378 // Check if we send the whole pkt or just a partial
379 uint32_t pktSize = i->second->GetSize ();
380 if (pktSize <= extractSize)
381 { // Whole packet is extracted
382 outPkt->AddAtEnd (i->second);
383 m_data.erase (i);
384 m_size -= pktSize;
385 m_availBytes -= pktSize;
386 extractSize -= pktSize;
387 }
388 else
389 { // Partial is extracted and done
390 outPkt->AddAtEnd (i->second->CreateFragment (0, extractSize));
391 m_data[i->first + SequenceNumber32 (extractSize)] = i->second->CreateFragment (extractSize, pktSize - extractSize);
392 m_data.erase (i);
393 m_size -= extractSize;
394 m_availBytes -= extractSize;
395 extractSize = 0;
396 }
397 }
398 if (outPkt->GetSize () == 0)
399 {
400 NS_LOG_LOGIC ("Nothing extracted.");
401 return nullptr;
402 }
403 NS_LOG_LOGIC ("Extracted " << outPkt->GetSize ( ) << " bytes, bufsize=" << m_size
404 << ", num pkts in buffer=" << m_data.size ());
405 return outPkt;
406 }
407
408 } //namespace ns3
409