A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
tcp-rx-buffer.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010 Adrian Sai-wah Tam
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Adrian Sai-wah Tam <adrian.sw.tam@gmail.com>
7 */
8
9#include "tcp-rx-buffer.h"
10
11#include "ns3/log.h"
12#include "ns3/packet.h"
13
14namespace ns3
15{
16
17NS_LOG_COMPONENT_DEFINE("TcpRxBuffer");
18
20
21TypeId
23{
24 static TypeId tid = TypeId("ns3::TcpRxBuffer")
26 .SetGroupName("Internet")
27 .AddConstructor<TcpRxBuffer>()
28 .AddTraceSource("NextRxSequence",
29 "Next sequence number expected (RCV.NXT)",
31 "ns3::SequenceNumber32TracedValueCallback");
32 return tid;
33}
34
35/* A user is supposed to create a TcpSocket through a factory. In TcpSocket,
36 * there are attributes SndBufSize and RcvBufSize to control the default Tx and
37 * Rx window sizes respectively, with default of 128 KiByte. The attribute
38 * RcvBufSize is passed to TcpRxBuffer by TcpSocketBase::SetRcvBufSize() and in
39 * turn, TcpRxBuffer:SetMaxBufferSize(). Therefore, the m_maxBuffer value
40 * initialized below is insignificant.
41 */
43 : m_nextRxSeq(n),
44 m_gotFin(false),
45 m_size(0),
46 m_maxBuffer(32768),
47 m_availBytes(0)
48{
49}
50
54
57{
58 return m_nextRxSeq;
59}
60
61void
66
69{
70 return m_maxBuffer;
71}
72
73void
78
81{
82 return m_size;
83}
84
87{
88 return m_availBytes;
89}
90
91void
93{
94 NS_LOG_FUNCTION(this);
95 // Increment nextRxSeq is valid only if we don't have any data buffered,
96 // this is supposed to be called only during the three-way handshake
97 NS_ASSERT(m_size == 0);
99}
100
101// Return the lowest sequence number that this TcpRxBuffer cannot accept
104{
105 if (m_gotFin)
106 { // No data allowed beyond FIN
107 return m_finSeq;
108 }
109 else if (!m_data.empty() && m_nextRxSeq > m_data.begin()->first)
110 { // No data allowed beyond Rx window allowed
111 return m_data.begin()->first + SequenceNumber32(m_maxBuffer);
112 }
114}
115
116void
118{
119 NS_LOG_FUNCTION(this);
120
121 m_gotFin = true;
122 m_finSeq = s;
123 if (m_nextRxSeq == m_finSeq)
124 {
125 ++m_nextRxSeq;
126 }
127}
128
129bool
131{
132 return (m_gotFin && m_finSeq < m_nextRxSeq);
133}
134
135bool
137{
138 NS_LOG_FUNCTION(this << p << tcph);
139
140 uint32_t pktSize = p->GetSize();
141 SequenceNumber32 headSeq = tcph.GetSequenceNumber();
142 SequenceNumber32 tailSeq = headSeq + SequenceNumber32(pktSize);
143 NS_LOG_LOGIC("Add pkt " << p << " len=" << pktSize << " seq=" << headSeq
144 << ", when NextRxSeq=" << m_nextRxSeq << ", buffsize=" << m_size);
145
146 // Trim packet to fit Rx window specification
147 if (headSeq < m_nextRxSeq)
148 {
149 headSeq = m_nextRxSeq;
150 }
151 if (!m_data.empty())
152 {
153 SequenceNumber32 maxSeq = m_data.begin()->first + SequenceNumber32(m_maxBuffer);
154 if (maxSeq < tailSeq)
155 {
156 tailSeq = maxSeq;
157 }
158 if (tailSeq < headSeq)
159 {
160 headSeq = tailSeq;
161 }
162 }
163 // Remove overlapped bytes from packet
164 auto i = m_data.begin();
165 while (i != m_data.end() && i->first <= tailSeq)
166 {
167 SequenceNumber32 lastByteSeq = i->first + SequenceNumber32(i->second->GetSize());
168 if (lastByteSeq > headSeq)
169 {
170 if (i->first > headSeq && lastByteSeq < tailSeq)
171 { // Rare case: Existing packet is embedded fully in the new packet
172 m_size -= i->second->GetSize();
173 m_data.erase(i++);
174 continue;
175 }
176 if (i->first <= headSeq)
177 { // Incoming head is overlapped
178 headSeq = lastByteSeq;
179 }
180 if (lastByteSeq >= tailSeq)
181 { // Incoming tail is overlapped
182 tailSeq = i->first;
183 }
184 }
185 ++i;
186 }
187 // We now know how much we are going to store, trim the packet
188 if (headSeq >= tailSeq)
189 {
190 NS_LOG_LOGIC("Nothing to buffer");
191 return false; // Nothing to buffer anyway
192 }
193 else
194 {
195 uint32_t start = static_cast<uint32_t>(headSeq - tcph.GetSequenceNumber());
196 auto length = static_cast<uint32_t>(tailSeq - headSeq);
197 p = p->CreateFragment(start, length);
198 NS_ASSERT(length == p->GetSize());
199 }
200 // Insert packet into buffer
201 NS_ASSERT(m_data.find(headSeq) == m_data.end()); // Shouldn't be there yet
202 m_data[headSeq] = p;
203
204 if (headSeq > m_nextRxSeq)
205 {
206 // Generate a new SACK block
207 UpdateSackList(headSeq, tailSeq);
208 }
209
210 NS_LOG_LOGIC("Buffered packet of seqno=" << headSeq << " len=" << p->GetSize());
211 // Update variables
212 m_size += p->GetSize(); // Occupancy
213 for (i = m_data.begin(); i != m_data.end(); ++i)
214 {
215 if (i->first < m_nextRxSeq)
216 {
217 continue;
218 }
219 else if (i->first > m_nextRxSeq)
220 {
221 break;
222 };
223 m_nextRxSeq = i->first + SequenceNumber32(i->second->GetSize());
224 m_availBytes += i->second->GetSize();
226 }
227 NS_LOG_LOGIC("Updated buffer occupancy=" << m_size << " nextRxSeq=" << m_nextRxSeq);
228 if (m_gotFin && m_nextRxSeq == m_finSeq)
229 { // Account for the FIN packet
230 ++m_nextRxSeq;
231 };
232 return true;
233}
234
237{
238 NS_LOG_FUNCTION(this);
239
240 return static_cast<uint32_t>(m_sackList.size());
241}
242
243void
245{
246 NS_LOG_FUNCTION(this << head << tail);
247 NS_ASSERT(head > m_nextRxSeq);
248
250 current.first = head;
251 current.second = tail;
252
253 // The block "current" has been safely stored. Now we need to build the SACK
254 // list, to be advertised. From RFC 2018:
255 // (a) The first SACK block (i.e., the one immediately following the
256 // kind and length fields in the option) MUST specify the contiguous
257 // block of data containing the segment which triggered this ACK,
258 // unless that segment advanced the Acknowledgment Number field in
259 // the header. This assures that the ACK with the SACK option
260 // reflects the most recent change in the data receiver's buffer
261 // queue.
262 //
263 // (b) The data receiver SHOULD include as many distinct SACK blocks as
264 // possible in the SACK option. Note that the maximum available
265 // option space may not be sufficient to report all blocks present in
266 // the receiver's queue.
267 //
268 // (c) The SACK option SHOULD be filled out by repeating the most
269 // recently reported SACK blocks (based on first SACK blocks in
270 // previous SACK options) that are not subsets of a SACK block
271 // already included in the SACK option being constructed. This
272 // assures that in normal operation, any segment remaining part of a
273 // non-contiguous block of data held by the data receiver is reported
274 // in at least three successive SACK options, even for large-window
275 // TCP implementations [RFC1323]). After the first SACK block, the
276 // following SACK blocks in the SACK option may be listed in
277 // arbitrary order.
278
279 m_sackList.push_front(current);
280
281 // We have inserted the block at the beginning of the list. Now, we should
282 // check if any existing blocks overlap with that.
283 bool updated = false;
284 auto it = m_sackList.begin();
285 TcpOptionSack::SackBlock begin = *it;
287 ++it;
288
289 // Iterates until we examined all blocks in the list (maximum 4)
290 while (it != m_sackList.end())
291 {
292 current = *it;
293
294 // This is a left merge:
295 // [current_first; current_second] [beg_first; beg_second]
296 if (begin.first == current.second)
297 {
298 NS_ASSERT(current.first < begin.second);
299 merged = TcpOptionSack::SackBlock(current.first, begin.second);
300 updated = true;
301 }
302 // while this is a right merge
303 // [begin_first; begin_second] [current_first; current_second]
304 else if (begin.second == current.first)
305 {
306 NS_ASSERT(begin.first < current.second);
307 merged = TcpOptionSack::SackBlock(begin.first, current.second);
308 updated = true;
309 }
310
311 // If we have merged the blocks (and the result is in merged) we should
312 // delete the current block (it), the first block, and insert the merged
313 // one at the beginning.
314 if (updated)
315 {
316 m_sackList.erase(it);
317 m_sackList.pop_front();
318 m_sackList.push_front(merged);
319 it = m_sackList.begin();
320 begin = *it;
321 updated = false;
322 }
323
324 ++it;
325 }
326
327 // Since the maximum blocks that fits into a TCP header are 4, there's no
328 // point on maintaining the others.
329 if (m_sackList.size() > 4)
330 {
331 m_sackList.pop_back();
332 }
333
334 // Please note that, if a block b is discarded and then a block contiguous
335 // to b is received, only that new block (without the b part) is reported.
336 // This is perfectly fine for the RFC point (a), given that we do not report any
337 // overlapping blocks shortly after.
338}
339
340void
342{
343 NS_LOG_FUNCTION(this << seq);
344
345 for (auto it = m_sackList.begin(); it != m_sackList.end();)
346 {
347 TcpOptionSack::SackBlock block = *it;
348 NS_ASSERT(block.first < block.second);
349
350 if (block.second <= seq)
351 {
352 it = m_sackList.erase(it);
353 }
354 else
355 {
356 it++;
357 }
358 }
359}
360
363{
364 return m_sackList;
365}
366
369{
370 NS_LOG_FUNCTION(this << maxSize);
371
372 uint32_t extractSize = std::min(maxSize, m_availBytes);
373 NS_LOG_LOGIC("Requested to extract " << extractSize
374 << " bytes from TcpRxBuffer of size=" << m_size);
375 if (extractSize == 0)
376 {
377 return nullptr; // No contiguous block to return
378 }
379 NS_ASSERT(!m_data.empty()); // At least we have something to extract
380 Ptr<Packet> outPkt = Create<Packet>(); // The packet that contains all the data to return
381 BufIterator i;
382 while (extractSize)
383 { // Check the buffered data for delivery
384 i = m_data.begin();
385 NS_ASSERT(i->first <= m_nextRxSeq); // in-sequence data expected
386 // Check if we send the whole pkt or just a partial
387 uint32_t pktSize = i->second->GetSize();
388 if (pktSize <= extractSize)
389 { // Whole packet is extracted
390 outPkt->AddAtEnd(i->second);
391 m_data.erase(i);
392 m_size -= pktSize;
394 extractSize -= pktSize;
395 }
396 else
397 { // Partial is extracted and done
398 outPkt->AddAtEnd(i->second->CreateFragment(0, extractSize));
399 m_data[i->first + SequenceNumber32(extractSize)] =
400 i->second->CreateFragment(extractSize, pktSize - extractSize);
401 m_data.erase(i);
402 m_size -= extractSize;
403 m_availBytes -= extractSize;
404 extractSize = 0;
405 }
406 }
407 if (outPkt->GetSize() == 0)
408 {
409 NS_LOG_LOGIC("Nothing extracted.");
410 return nullptr;
411 }
412 NS_LOG_LOGIC("Extracted " << outPkt->GetSize() << " bytes, bufsize=" << m_size
413 << ", num pkts in buffer=" << m_data.size());
414 return outPkt;
415}
416
417} // namespace ns3
A base class which provides memory management and object aggregation.
Definition object.h:78
Smart pointer class similar to boost::intrusive_ptr.
Header for the Transmission Control Protocol.
Definition tcp-header.h:36
SequenceNumber32 GetSequenceNumber() const
Get the sequence number.
std::list< SackBlock > SackList
SACK list definition.
std::pair< SequenceNumber32, SequenceNumber32 > SackBlock
SACK block definition.
Rx reordering buffer for TCP.
~TcpRxBuffer() override
uint32_t GetSackListSize() const
Get the size of Sack list.
Ptr< Packet > Extract(uint32_t maxSize)
Extract data from the head of the buffer as indicated by nextRxSeq.
bool Finished()
Check if the buffer did receive all the data (and the connection is closed)
static TypeId GetTypeId()
Get the type ID.
void SetFinSequence(const SequenceNumber32 &s)
Set the FIN Sequence number (i.e., the one closing the connection)
void SetMaxBufferSize(uint32_t s)
Set the Maximum buffer size.
SequenceNumber32 NextRxSequence() const
Get Next Rx Sequence number.
std::map< SequenceNumber32, Ptr< Packet > > m_data
Corresponding data (may be null)
void SetNextRxSequence(const SequenceNumber32 &s)
Set the Next Sequence number.
SequenceNumber32 m_finSeq
Seqnum of the FIN packet.
uint32_t m_availBytes
Number of bytes available to read, i.e.
void IncNextRxSequence()
Increment the Next Sequence number.
uint32_t MaxBufferSize() const
Get the Maximum buffer size.
uint32_t Size() const
Get the actual buffer occupancy.
bool Add(Ptr< Packet > p, const TcpHeader &tcph)
Insert a packet into the buffer and update the availBytes counter to reflect the number of bytes read...
uint32_t m_maxBuffer
Upper bound of the number of data bytes in buffer (RCV.WND)
std::map< SequenceNumber32, Ptr< Packet > >::iterator BufIterator
container for data stored in the buffer
SequenceNumber32 MaxRxSequence() const
Get the lowest sequence number that this TcpRxBuffer cannot accept.
TracedValue< SequenceNumber32 > m_nextRxSeq
Seqnum of the first missing byte in data (RCV.NXT)
TcpRxBuffer(uint32_t n=0)
Constructor.
void UpdateSackList(const SequenceNumber32 &head, const SequenceNumber32 &tail)
Update the sack list, with the block seq starting at the beginning.
uint32_t Available() const
Get the actual number of bytes available to be read.
TcpOptionSack::SackList GetSackList() const
Get the sack list.
uint32_t m_size
Number of total data bytes in the buffer, not necessarily contiguous.
void ClearSackList(const SequenceNumber32 &seq)
Remove old blocks from the sack list.
bool m_gotFin
Did I received FIN packet?
TcpOptionSack::SackList m_sackList
Sack list (updated constantly)
a unique identifier for an interface.
Definition type-id.h:48
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition assert.h:55
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition log.h:271
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition object-base.h:35
Ptr< T > Create(Ts &&... args)
Create class instances by constructors with varying numbers of arguments and return them by Ptr.
Definition ptr.h:436
SequenceNumber< uint32_t, int32_t > SequenceNumber32
32 bit Sequence number.
Ptr< const TraceSourceAccessor > MakeTraceSourceAccessor(T a)
Create a TraceSourceAccessor which will control access to the underlying trace source.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
uint32_t pktSize
packet size used for the simulation (in bytes)