A Discrete-Event Network Simulator
API
tcp-rx-buffer.cc
Go to the documentation of this file.
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
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)",
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  */
54  : m_nextRxSeq (n), m_gotFin (false), m_size (0), m_maxBuffer (32768), m_availBytes (0)
55 {
56 }
57 
59 {
60 }
61 
64 {
65  return m_nextRxSeq;
66 }
67 
68 void
70 {
71  m_nextRxSeq = s;
72 }
73 
74 uint32_t
76 {
77  return m_maxBuffer;
78 }
79 
80 void
82 {
83  m_maxBuffer = s;
84 }
85 
86 uint32_t
87 TcpRxBuffer::Size (void) const
88 {
89  return m_size;
90 }
91 
92 uint32_t
94 {
95  return m_availBytes;
96 }
97 
98 void
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
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  }
121 }
122 
123 void
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
135 {
136  return (m_gotFin && m_finSeq < m_nextRxSeq);
137 }
138 
139 bool
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 ();
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
232 {
233  NS_LOG_FUNCTION (this);
234 
235  return static_cast<uint32_t> (m_sackList.size ());
236 }
237 
238 void
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;
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
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 
359 {
360  return m_sackList;
361 }
362 
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
uint32_t m_availBytes
Number of bytes available to read, i.e.
uint32_t m_maxBuffer
Upper bound of the number of data bytes in buffer (RCV.WND)
SequenceNumber32 NextRxSequence(void) const
Get Next Rx Sequence number.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
bool Add(Ptr< Packet > p, TcpHeader const &tcph)
Insert a packet into the buffer and update the availBytes counter to reflect the number of bytes read...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
uint32_t GetSize(void) const
Returns the the size in bytes of the packet (including the zero-filled initial payload).
Definition: packet.h:852
TracedValue< SequenceNumber32 > m_nextRxSeq
Seqnum of the first missing byte in data (RCV.NXT)
#define min(a, b)
Definition: 80211b.c:42
def start()
Definition: core.py:1855
std::list< SackBlock > SackList
SACK list definition.
Ptr< Packet > CreateFragment(uint32_t start, uint32_t length) const
Create a new packet which contains a fragment of the original packet.
Definition: packet.cc:227
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:67
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:204
void SetFinSequence(const SequenceNumber32 &s)
Set the FIN Sequence number (i.e., the one closing the connection)
SequenceNumber32 MaxRxSequence(void) const
Get the lowest sequence number that this TcpRxBuffer cannot accept.
void ClearSackList(const SequenceNumber32 &seq)
Remove old blocks from the sack list.
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
uint32_t GetSackListSize() const
Get the size of Sack list.
void IncNextRxSequence(void)
Increment the Next Sequence number.
bool m_gotFin
Did I received FIN packet?
void UpdateSackList(const SequenceNumber32 &head, const SequenceNumber32 &tail)
Update the sack list, with the block seq starting at the beginning.
Rx reordering buffer for TCP.
Definition: tcp-rx-buffer.h:73
void SetNextRxSequence(const SequenceNumber32 &s)
Set the Next Sequence number.
void SetMaxBufferSize(uint32_t s)
Set the Maximum buffer size.
uint32_t Size(void) const
Get the actual buffer occupancy.
TcpRxBuffer(uint32_t n=0)
Constructor.
SequenceNumber32 m_finSeq
Seqnum of the FIN packet.
Ptr< Packet > Extract(uint32_t maxSize)
Extract data from the head of the buffer as indicated by nextRxSeq.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Header for the Transmission Control Protocol.
Definition: tcp-header.h:44
std::map< SequenceNumber32, Ptr< Packet > > m_data
Corresponding data (may be null)
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
std::pair< SequenceNumber32, SequenceNumber32 > SackBlock
SACK block definition.
uint32_t m_size
Number of total data bytes in the buffer, not necessarily contiguous.
TcpOptionSack::SackList m_sackList
Sack list (updated constantly)
static TypeId GetTypeId(void)
Get the type ID.
SequenceNumber32 GetSequenceNumber() const
Get the sequence number.
Definition: tcp-header.cc:143
A base class which provides memory management and object aggregation.
Definition: object.h:87
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:915
SequenceNumber< uint32_t, int32_t > SequenceNumber32
32 bit Sequence number.
virtual ~TcpRxBuffer()
uint32_t MaxBufferSize(void) const
Get the Maximum buffer size.
bool Finished(void)
Check if the buffer did receive all the data (and the connection is closed)
uint32_t Available() const
Get the actual number of bytes available to be read.
std::map< SequenceNumber32, Ptr< Packet > >::iterator BufIterator
container for data stored in the buffer
TcpOptionSack::SackList GetSackList() const
Get the sack list.