tcp-tx-buffer.cc

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2010-2015 Adrian Sai-wah Tam
 * Copyright (c) 2016 Natale Patriciello <natale.patriciello@gmail.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Original author: Adrian Sai-wah Tam <adrian.sw.tam@gmail.com>
 */

#include <algorithm>
#include <iostream>

#include "ns3/packet.h"
#include "ns3/log.h"
#include "ns3/abort.h"
#include "ns3/tcp-option-ts.h"

#include "tcp-tx-buffer.h"

namespace ns3 {

NS_LOG_COMPONENT_DEFINE ("TcpTxBuffer");

void
TcpTxItem::Print (std::ostream &os) const
{
  bool comma = false;
  os << "[" << m_startSeq << ";" << m_startSeq + GetSeqSize () << "|"
     << GetSeqSize () << "]";

  if (m_lost)
    {
      os << "[lost]";
      comma = true;
    }
  if (m_retrans)
    {
      if (comma)
        {
          os << ",";
        }

      os << "[retrans]";
      comma = true;
    }
  if (m_sacked)
    {
      if (comma)
        {
          os << ",";
        }
      os << "[sacked]";
      comma = true;
    }
  if (comma)
    {
      os << ",";
    }
  os << "[" << m_lastSent.GetSeconds () << "]";
}

NS_OBJECT_ENSURE_REGISTERED (TcpTxBuffer);

TypeId
TcpTxBuffer::GetTypeId (void)
{
  static TypeId tid = TypeId ("ns3::TcpTxBuffer")
    .SetParent<Object> ()
    .SetGroupName ("Internet")
    .AddConstructor<TcpTxBuffer> ()
    .AddTraceSource ("UnackSequence",
                     "First unacknowledged sequence number (SND.UNA)",
                     MakeTraceSourceAccessor (&TcpTxBuffer::m_firstByteSeq),
                     "ns3::SequenceNumber32TracedValueCallback")
  ;
  return tid;
}

/* A user is supposed to create a TcpSocket through a factory. In TcpSocket,
 * there are attributes SndBufSize and RcvBufSize to control the default Tx and
 * Rx window sizes respectively, with default of 128 KiByte. The attribute
 * SndBufSize is passed to TcpTxBuffer by TcpSocketBase::SetSndBufSize() and in
 * turn, TcpTxBuffer:SetMaxBufferSize(). Therefore, the m_maxBuffer value
 * initialized below is insignificant.
 */
TcpTxBuffer::TcpTxBuffer (uint32_t n)
  : m_maxBuffer (32768), m_size (0), m_sentSize (0), m_firstByteSeq (n)
{
}

TcpTxBuffer::~TcpTxBuffer (void)
{
  PacketList::iterator it;

  for (it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      TcpTxItem *item = *it;
      m_sentSize -= item->m_packet->GetSize ();
      delete item;
    }

  for (it = m_appList.begin (); it != m_appList.end (); ++it)
    {
      TcpTxItem *item = *it;
      m_size -= item->m_packet->GetSize ();
      delete item;
    }
}

SequenceNumber32
TcpTxBuffer::HeadSequence (void) const
{
  return m_firstByteSeq;
}

SequenceNumber32
TcpTxBuffer::TailSequence (void) const
{
  return m_firstByteSeq + SequenceNumber32 (m_size);
}

uint32_t
TcpTxBuffer::Size (void) const
{
  return m_size;
}

uint32_t
TcpTxBuffer::MaxBufferSize (void) const
{
  return m_maxBuffer;
}

void
TcpTxBuffer::SetMaxBufferSize (uint32_t n)
{
  m_maxBuffer = n;
}

uint32_t
TcpTxBuffer::Available (void) const
{
  return m_maxBuffer - m_size;
}

void
TcpTxBuffer::SetHeadSequence (const SequenceNumber32& seq)
{
  NS_LOG_FUNCTION (this << seq);
  m_firstByteSeq = seq;

  if (m_sentList.size () > 0)
    {
      m_sentList.front ()->m_startSeq = seq;
    }

  // if you change the head with data already sent, something bad will happen
  NS_ASSERT (m_sentList.size () == 0);
  m_highestSack = std::make_pair (m_sentList.end (), SequenceNumber32 (0));
}

bool
TcpTxBuffer::Add (Ptr<Packet> p)
{
  NS_LOG_FUNCTION (this << p);
  NS_LOG_LOGIC ("Try to append " << p->GetSize () << " bytes to window starting at "
                                << m_firstByteSeq << ", availSize=" << Available ());
  if (p->GetSize () <= Available ())
    {
      if (p->GetSize () > 0)
        {
          TcpTxItem *item = new TcpTxItem ();
          item->m_packet = p->Copy ();
          m_appList.insert (m_appList.end (), item);
          m_size += p->GetSize ();

          NS_LOG_LOGIC ("Updated size=" << m_size << ", lastSeq=" <<
                        m_firstByteSeq + SequenceNumber32 (m_size));
        }
      return true;
    }
  NS_LOG_LOGIC ("Rejected. Not enough room to buffer packet.");
  return false;
}

uint32_t
TcpTxBuffer::SizeFromSequence (const SequenceNumber32& seq) const
{
  NS_LOG_FUNCTION (this << seq);
  // Sequence of last byte in buffer
  SequenceNumber32 lastSeq = TailSequence ();

  if (lastSeq >= seq)
    {
      return static_cast<uint32_t> (lastSeq - seq);
    }

  NS_LOG_ERROR ("Requested a sequence beyond our space (" << seq << " > " << lastSeq <<
                "). Returning 0 for convenience.");
  return 0;
}

Ptr<Packet>
TcpTxBuffer::CopyFromSequence (uint32_t numBytes, const SequenceNumber32& seq)
{
  NS_LOG_FUNCTION (this << numBytes << seq);

  NS_ABORT_MSG_IF (m_firstByteSeq > seq,
                   "Requested a sequence number which is not in the buffer anymore");
  ConsistencyCheck ();

  // Real size to extract. Insure not beyond end of data
  uint32_t s = std::min (numBytes, SizeFromSequence (seq));

  if (s == 0)
    {
      return Create<Packet> ();
    }

  TcpTxItem *outItem = nullptr;

  if (m_firstByteSeq + m_sentSize >= seq + s)
    {
      // already sent this block completely
      outItem = GetTransmittedSegment (s, seq);
      NS_ASSERT (outItem != nullptr);
      NS_ASSERT (!outItem->m_sacked);

      NS_LOG_DEBUG ("Returning already sent item " << *outItem << " from " << *this);
    }
  else if (m_firstByteSeq + m_sentSize <= seq)
    {
      NS_ABORT_MSG_UNLESS (m_firstByteSeq + m_sentSize == seq,
                           "Requesting a piece of new data with an hole");

      // this is the first time we transmit this block
      outItem = GetNewSegment (s);
      NS_ASSERT (outItem != nullptr);
      NS_ASSERT (outItem->m_retrans == false);

      NS_LOG_DEBUG ("Returning new item " << *outItem << " from " << *this);
    }
  else if (m_firstByteSeq.Get ().GetValue () + m_sentSize > seq.GetValue ()
           && m_firstByteSeq.Get ().GetValue () + m_sentSize < seq.GetValue () + s)
    {
      // Partial: a part is retransmission, the remaining data is new
      // Just return the old segment, without taking new data. Hopefully
      // TcpSocketBase will request new data

      uint32_t amount = (m_firstByteSeq.Get ().GetValue () + m_sentSize) - seq.GetValue ();

      return CopyFromSequence (amount, seq);
    }

  outItem->m_lastSent = Simulator::Now ();
  Ptr<Packet> toRet = outItem->m_packet->Copy ();

  NS_ASSERT (toRet->GetSize () <= s);
  NS_ASSERT_MSG (outItem->m_startSeq >= m_firstByteSeq,
                 "Returning an item " << *outItem << " with SND.UNA as " <<
                 m_firstByteSeq);
  ConsistencyCheck ();
  return toRet;
}

TcpTxItem*
TcpTxBuffer::GetNewSegment (uint32_t numBytes)
{
  NS_LOG_FUNCTION (this << numBytes);

  SequenceNumber32 startOfAppList = m_firstByteSeq + m_sentSize;

  NS_LOG_INFO ("AppList start at " << startOfAppList << ", sentSize = " <<
               m_sentSize << " firstByte: " << m_firstByteSeq);

  TcpTxItem *item = GetPacketFromList (m_appList, startOfAppList,
                                       numBytes, startOfAppList);
  item->m_startSeq = startOfAppList;

  // Move item from AppList to SentList (should be the first, not too complex)
  auto it = std::find (m_appList.begin (), m_appList.end (), item);
  NS_ASSERT (it != m_appList.end ());

  m_appList.erase (it);
  m_sentList.insert (m_sentList.end (), item);
  m_sentSize += item->m_packet->GetSize ();

  return item;
}

TcpTxItem*
TcpTxBuffer::GetTransmittedSegment (uint32_t numBytes, const SequenceNumber32 &seq)
{
  NS_LOG_FUNCTION (this << numBytes << seq);
  NS_ASSERT (seq >= m_firstByteSeq);
  NS_ASSERT (numBytes <= m_sentSize);
  NS_ASSERT (m_sentList.size () >= 1);

  auto it = m_sentList.begin ();
  bool listEdited = false;
  uint32_t s = numBytes;

  // Avoid to merge different packet for this retransmission if flags are
  // different.
  for (; it != m_sentList.end(); ++it)
    {
      if ((*it)->m_startSeq == seq)
        {
          auto next = it;
          next++;
          if (next != m_sentList.end ())
            {
              // Next is not sacked... there is the possibility to merge
              if (! (*next)->m_sacked)
                {
                  s = std::min(s, (*it)->m_packet->GetSize () + (*next)->m_packet->GetSize ());
                }
              else
                {
                  // Next is sacked... better to retransmit only the first segment
                  s = std::min(s, (*it)->m_packet->GetSize ());
                }
            }
          else
            {
              s = std::min(s, (*it)->m_packet->GetSize ());
            }
          break;
        }
    }

  TcpTxItem *item = GetPacketFromList (m_sentList, m_firstByteSeq, s, seq, &listEdited);

  if (! item->m_retrans)
    {
      m_retrans += item->m_packet->GetSize ();
      item->m_retrans = true;
    }

  return item;
}

std::pair <TcpTxBuffer::PacketList::const_iterator, SequenceNumber32>
TcpTxBuffer::FindHighestSacked () const
{
  NS_LOG_FUNCTION (this);

  SequenceNumber32 beginOfCurrentPacket = m_firstByteSeq;

  auto ret = std::make_pair (m_sentList.end (), SequenceNumber32 (0));

  for (auto it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      const TcpTxItem *item = *it;
      if (item->m_sacked)
        {
          ret = std::make_pair (it, beginOfCurrentPacket);
        }
      beginOfCurrentPacket += item->m_packet->GetSize ();
    }

  return ret;
}


void
TcpTxBuffer::SplitItems (TcpTxItem *t1, TcpTxItem *t2, uint32_t size) const
{
  NS_ASSERT (t1 != nullptr && t2 != nullptr);
  NS_LOG_FUNCTION (this << *t2 << size);

  t1->m_packet = t2->m_packet->CreateFragment (0, size);
  t2->m_packet->RemoveAtStart (size);

  t1->m_startSeq = t2->m_startSeq;
  t1->m_sacked = t2->m_sacked;
  t1->m_lastSent = t2->m_lastSent;
  t1->m_retrans = t2->m_retrans;
  t1->m_lost = t2->m_lost;

  t2->m_startSeq += size;

  NS_LOG_INFO ("Split of size " << size << " result: t1 " << *t1 << " t2 " << *t2);
}

TcpTxItem*
TcpTxBuffer::GetPacketFromList (PacketList &list, const SequenceNumber32 &listStartFrom,
                                uint32_t numBytes, const SequenceNumber32 &seq,
                                bool *listEdited) const
{
  NS_LOG_FUNCTION (this << numBytes << seq);

  /*
   * Our possibilities are sketched out in the following:
   *
   *                    |------|     |----|     |----|
   * GetList (m_data) = |      | --> |    | --> |    |
   *                    |------|     |----|     |----|
   *
   *                    ^ ^ ^  ^
   *                    | | |  |         (1)
   *                  seq | |  numBytes
   *                      | |
   *                      | |
   *                    seq numBytes     (2)
   *
   * (1) seq and numBytes are the boundary of some packet
   * (2) seq and numBytes are not the boundary of some packet
   *
   * We can have mixed case (e.g. seq over the boundary while numBytes not).
   *
   * If we discover that we are in (2) or in a mixed case, we split
   * packets accordingly to the requested bounds and re-run the function.
   *
   * In (1), things are pretty easy, it's just a matter of walking the list and
   * defragment packets, if needed (e.g. seq is the beginning of the first packet
   * while maxBytes is the end of some packet next in the list).
   */

  Ptr<Packet> currentPacket = nullptr;
  TcpTxItem *currentItem = nullptr;
  TcpTxItem *outItem = nullptr;
  PacketList::iterator it = list.begin ();
  SequenceNumber32 beginOfCurrentPacket = listStartFrom;

  while (it != list.end ())
    {
      currentItem = *it;
      currentPacket = currentItem->m_packet;
      NS_ASSERT_MSG (list != m_sentList || currentItem->m_startSeq >= m_firstByteSeq,
                     "start: " << m_firstByteSeq << " currentItem start: " <<
                     currentItem->m_startSeq);

      // The objective of this snippet is to find (or to create) the packet
      // that begin with the sequence seq

      if (seq < beginOfCurrentPacket + currentPacket->GetSize ())
        {
          // seq is inside the current packet
          if (seq == beginOfCurrentPacket)
            {
              // seq is the beginning of the current packet. Hurray!
              outItem = currentItem;
              NS_LOG_INFO ("Current packet starts at seq " << seq <<
                           " ends at " << seq + currentPacket->GetSize ());
            }
          else if (seq > beginOfCurrentPacket)
            {
              // seq is inside the current packet but seq is not the beginning,
              // it's somewhere in the middle. Just fragment the beginning and
              // start again.
              NS_LOG_INFO ("we are at " << beginOfCurrentPacket <<
                           " searching for " << seq <<
                           " and now we recurse because packet ends at "
                                        << beginOfCurrentPacket + currentPacket->GetSize ());
              TcpTxItem *firstPart = new TcpTxItem ();
              SplitItems (firstPart, currentItem, seq - beginOfCurrentPacket);

              // insert firstPart before currentItem
              list.insert (it, firstPart);
              if (listEdited)
                {
                  *listEdited = true;
                }

              return GetPacketFromList (list, listStartFrom, numBytes, seq, listEdited);
            }
          else
            {
              NS_FATAL_ERROR ("seq < beginOfCurrentPacket: our data is before");
            }
        }
      else
        {
          // Walk the list, the current packet does not contain seq
          beginOfCurrentPacket += currentPacket->GetSize ();
          it++;
          continue;
        }

      NS_ASSERT (outItem != nullptr);

      // The objective of this snippet is to find (or to create) the packet
      // that ends after numBytes bytes. We are sure that outPacket starts
      // at seq.

      if (seq + numBytes <= beginOfCurrentPacket + currentPacket->GetSize ())
        {
          // the end boundary is inside the current packet
          if (numBytes == currentPacket->GetSize ())
            {
              // the end boundary is exactly the end of the current packet. Hurray!
              if (currentItem->m_packet == outItem->m_packet)
                {
                  // A perfect match!
                  return outItem;
                }
              else
                {
                  // the end is exactly the end of current packet, but
                  // current > outPacket in the list. Merge current with the
                  // previous, and recurse.
                  NS_ASSERT (it != list.begin ());
                  TcpTxItem *previous = *(--it);

                  list.erase (it);

                  MergeItems (previous, currentItem);
                  delete currentItem;
                  if (listEdited)
                    {
                      *listEdited = true;
                    }

                  return GetPacketFromList (list, listStartFrom, numBytes, seq, listEdited);
                }
            }
          else if (numBytes < currentPacket->GetSize ())
            {
              // the end is inside the current packet, but it isn't exactly
              // the packet end. Just fragment, fix the list, and return.
              TcpTxItem *firstPart = new TcpTxItem ();
              SplitItems (firstPart, currentItem, numBytes);

              // insert firstPart before currentItem
              list.insert (it, firstPart);
              if (listEdited)
                {
                  *listEdited = true;
                }

              return firstPart;
            }
        }
      else
        {
          // The end isn't inside current packet, but there is an exception for
          // the merge and recurse strategy...
          if (++it == list.end ())
            {
              // ...current is the last packet we sent. We have not more data;
              // Go for this one.
              NS_LOG_WARN ("Cannot reach the end, but this case is covered "
                           "with conditional statements inside CopyFromSequence."
                           "Something has gone wrong, report a bug");
              return outItem;
            }

          // The current packet does not contain the requested end. Merge current
          // with the packet that follows, and recurse
          TcpTxItem *next = (*it); // Please remember we have incremented it
                                   // in the previous if

          MergeItems (currentItem, next);
          list.erase (it);

          delete next;

          if (listEdited)
            {
              *listEdited = true;
            }

          return GetPacketFromList (list, listStartFrom, numBytes, seq, listEdited);
        }
    }

  NS_FATAL_ERROR ("This point is not reachable");
}

static bool AreEquals (const bool &first, const bool &second)
{
  return first ? second : !second;
}

void
TcpTxBuffer::MergeItems (TcpTxItem *t1, TcpTxItem *t2) const
{
  NS_ASSERT (t1 != nullptr && t2 != nullptr);
  NS_LOG_FUNCTION (this << *t1 << *t2);
  NS_LOG_INFO ("Merging " << *t2 << " into " << *t1);

  NS_ASSERT_MSG (AreEquals (t1->m_sacked, t2->m_sacked),
                 "Merging one sacked and another not sacked. Impossible");
  NS_ASSERT_MSG (AreEquals (t1->m_lost, t2->m_lost),
                 "Merging one lost and another not lost. Impossible");

  // If one is retrans and the other is not, cancel the retransmitted flag.
  // We are merging this segment for the retransmit, so the count will
  // be updated in GetTransmittedSegment.
  if (! AreEquals (t1->m_retrans, t2->m_retrans))
    {
      if (t1->m_retrans)
        {
          TcpTxBuffer *self = const_cast<TcpTxBuffer*> (this);
          self->m_retrans -= t1->m_packet->GetSize ();
          t1->m_retrans = false;
        }
      else
        {
          NS_ASSERT (t2->m_retrans);
          TcpTxBuffer *self = const_cast<TcpTxBuffer*> (this);
          self->m_retrans -= t2->m_packet->GetSize ();
          t2->m_retrans = false;
        }
    }

  if (t1->m_lastSent < t2->m_lastSent)
    {
      t1->m_lastSent = t2->m_lastSent;
    }

  t1->m_packet->AddAtEnd (t2->m_packet);

  NS_LOG_INFO ("Situation after the merge: " << *t1);
}

void
TcpTxBuffer::RemoveFromCounts (TcpTxItem *item, uint32_t size)
{
  NS_LOG_FUNCTION (this << *item << size);
  if (item->m_sacked)
    {
      NS_ASSERT (m_sackedOut >= size);
      m_sackedOut -= size;
    }
  if (item->m_retrans)
    {
      NS_ASSERT (m_retrans >= size);
      m_retrans -= size;
    }
  if (item->m_lost)
    {
      NS_ASSERT_MSG (m_lostOut >= size, "Trying to remove " << size <<
                     " bytes from " << m_lostOut);
      m_lostOut -= size;
    }
}
void
TcpTxBuffer::DiscardUpTo (const SequenceNumber32& seq)
{
  NS_LOG_FUNCTION (this << seq);

  // Cases do not need to scan the buffer
  if (m_firstByteSeq >= seq)
    {
      NS_LOG_DEBUG ("Seq " << seq << " already discarded.");
      return;
    }
  NS_LOG_DEBUG ("Remove up to " << seq << " lost: " << m_lostOut <<
                " retrans: " << m_retrans << " sacked: " << m_sackedOut);

  // Scan the buffer and discard packets
  uint32_t offset = seq - m_firstByteSeq.Get ();  // Number of bytes to remove
  uint32_t pktSize;
  PacketList::iterator i = m_sentList.begin ();
  while (m_size > 0 && offset > 0)
    {
      if (i == m_sentList.end ())
        {
          // Move data from app list to sent list, so we can delete the item
          Ptr<Packet> p = CopyFromSequence (offset, m_firstByteSeq);
          NS_ASSERT (p != nullptr);
          NS_UNUSED (p);
          i = m_sentList.begin ();
          NS_ASSERT (i != m_sentList.end ());
        }
      TcpTxItem *item = *i;
      Ptr<Packet> p = item->m_packet;
      pktSize = p->GetSize ();
      NS_ASSERT_MSG (item->m_startSeq == m_firstByteSeq,
                     "Item starts at " << item->m_startSeq <<
                     " while SND.UNA is " << m_firstByteSeq << " from " << *this);

      if (offset >= pktSize)
        { // This packet is behind the seqnum. Remove this packet from the buffer
          m_size -= pktSize;
          m_sentSize -= pktSize;
          offset -= pktSize;
          m_firstByteSeq += pktSize;

          RemoveFromCounts (item, pktSize);

          i = m_sentList.erase (i);
          NS_LOG_INFO ("Removed " << *item << " lost: " << m_lostOut <<
                       " retrans: " << m_retrans << " sacked: " << m_sackedOut <<
                       ". Remaining data " << m_size);
          delete item;
        }
      else if (offset > 0)
        { // Part of the packet is behind the seqnum. Fragment
          pktSize -= offset;
          NS_LOG_INFO (*item);
          // PacketTags are preserved when fragmenting
          item->m_packet = item->m_packet->CreateFragment (offset, pktSize);
          item->m_startSeq += offset;
          m_size -= offset;
          m_sentSize -= offset;
          m_firstByteSeq += offset;

          RemoveFromCounts (item, offset);

          NS_LOG_INFO ("Fragmented one packet by size " << offset <<
                       ", new size=" << pktSize << " resulting item is " <<
                       *item << " status: " << *this);
          break;
        }
    }
  // Catching the case of ACKing a FIN
  if (m_size == 0)
    {
      m_firstByteSeq = seq;
    }

  if (!m_sentList.empty ())
    {
      TcpTxItem *head = m_sentList.front ();
      if (head->m_sacked)
        {
          NS_ASSERT (!head->m_lost);
          // It is not possible to have the UNA sacked; otherwise, it would
          // have been ACKed. This is, most likely, our wrong guessing
          // when adding Reno dupacks in the count.
          head->m_sacked = false;
          m_sackedOut -= head->m_packet->GetSize ();
          NS_LOG_INFO ("Moving the SACK flag from the HEAD to another segment");
          AddRenoSack ();
          MarkHeadAsLost ();
        }

      NS_ASSERT_MSG (head->m_startSeq == seq,
                     "While removing up to " << seq << " we get SND.UNA to " <<
                     m_firstByteSeq << " this is the result: " << *this);
    }

  if (m_highestSack.second <= m_firstByteSeq)
    {
      m_highestSack = std::make_pair (m_sentList.end (), SequenceNumber32 (0));
    }

  NS_LOG_DEBUG ("Discarded up to " << seq << " lost: " << m_lostOut <<
                " retrans: " << m_retrans << " sacked: " << m_sackedOut);
  NS_LOG_LOGIC ("Buffer status after discarding data " << *this);
  NS_ASSERT (m_firstByteSeq >= seq);
  NS_ASSERT (m_sentSize >= m_sackedOut + m_lostOut);
  ConsistencyCheck ();
}

bool
TcpTxBuffer::Update (const TcpOptionSack::SackList &list)
{
  NS_LOG_FUNCTION (this);
  NS_LOG_INFO ("Updating scoreboard, got " << list.size () << " blocks to analyze");

  bool modified = false;

  for (auto option_it = list.begin (); option_it != list.end (); ++option_it)
    {
      PacketList::iterator item_it = m_sentList.begin ();
      SequenceNumber32 beginOfCurrentPacket = m_firstByteSeq;

      if (m_firstByteSeq + m_sentSize < (*option_it).first && !modified)
        {
          NS_LOG_INFO ("Not updating scoreboard, the option block is outside the sent list");
          return false;
        }

      while (item_it != m_sentList.end ())
        {
          uint32_t pktSize = (*item_it)->m_packet->GetSize ();

          // Check the boundary of this packet ... only mark as sacked if
          // it is precisely mapped over the option. It means that if the receiver
          // is reporting as sacked single range bytes that are not mapped 1:1
          // in what we have, the option is discarded. There's room for improvement
          // here.
          if (beginOfCurrentPacket >= (*option_it).first
              && beginOfCurrentPacket + pktSize <= (*option_it).second)
            {
              if ((*item_it)->m_sacked)
                {
                  NS_ASSERT (!(*item_it)->m_lost);
                  NS_LOG_INFO ("Received block " << *option_it <<
                               ", checking sentList for block " << *(*item_it) <<
                               ", found in the sackboard already sacked");
                }
              else
                {
                  if ((*item_it)->m_lost)
                    {
                      (*item_it)->m_lost = false;
                      m_lostOut -= (*item_it)->m_packet->GetSize ();
                    }

                  (*item_it)->m_sacked = true;
                  m_sackedOut += (*item_it)->m_packet->GetSize ();

                  if (m_highestSack.first == m_sentList.end()
                      || m_highestSack.second <= beginOfCurrentPacket + pktSize)
                    {
                      m_highestSack = std::make_pair (item_it, beginOfCurrentPacket);
                    }

                  NS_LOG_INFO ("Received block " << *option_it <<
                               ", checking sentList for block " << *(*item_it) <<
                               ", found in the sackboard, sacking, current highSack: " <<
                               m_highestSack.second);
                }
              modified = true;
            }
          else if (beginOfCurrentPacket + pktSize > (*option_it).second)
            {
              // We already passed the received block end. Exit from the loop
              NS_LOG_INFO ("Received block [" << *option_it <<
                           ", checking sentList for block " << *(*item_it) <<
                           "], not found, breaking loop");
              break;
            }

          beginOfCurrentPacket += pktSize;
          ++item_it;
        }
    }

  if (modified)
    {
      NS_ASSERT_MSG (modified && m_highestSack.first != m_sentList.end(), "Buffer status: " << *this);
      UpdateLostCount ();
    }

  NS_ASSERT ((*(m_sentList.begin ()))->m_sacked == false);
  NS_ASSERT_MSG (m_sentSize >= m_sackedOut + m_lostOut, *this);
  //NS_ASSERT (list.size () == 0 || modified);   // Assert for duplicated SACK or
                                                 // impossiblity to map the option into the sent blocks
  ConsistencyCheck ();
  return modified;
}

void
TcpTxBuffer::UpdateLostCount ()
{
  NS_LOG_FUNCTION (this);
  uint32_t sacked = 0;
  SequenceNumber32 beginOfCurrentPacket = m_highestSack.second;
  if (m_highestSack.first == m_sentList.end ())
    {
      NS_LOG_INFO ("Status before the update: " << *this <<
                   ", will start from the latest sent item");
    }
  else
    {
      NS_LOG_INFO ("Status before the update: " << *this <<
                   ", will start from item " << *(*m_highestSack.first));
    }

  for (auto it = m_highestSack.first; it != m_sentList.begin(); --it)
    {
      TcpTxItem *item = *it;
      if (item->m_sacked)
        {
          sacked++;
        }

      if (sacked >= m_dupAckThresh)
        {
          if (!item->m_sacked && !item->m_lost)
            {
              item->m_lost = true;
              m_lostOut += item->m_packet->GetSize ();
            }
        }
      beginOfCurrentPacket -= item->m_packet->GetSize ();
    }

  if (sacked >= m_dupAckThresh)
    {
      TcpTxItem *item = *m_sentList.begin ();
      if (!item->m_lost)
        {
          item->m_lost = true;
          m_lostOut += item->m_packet->GetSize ();
        }
    }
  NS_LOG_INFO ("Status after the update: " << *this);
  ConsistencyCheck ();
}

bool
TcpTxBuffer::IsLost (const SequenceNumber32 &seq) const
{
  NS_LOG_FUNCTION (this << seq);

  SequenceNumber32 beginOfCurrentPacket = m_firstByteSeq;
  PacketList::const_iterator it;

  if (seq >= m_highestSack.second)
    {
      return false;
    }

  // In theory, using a map and hints when inserting elements can improve
  // performance
  for (it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      // Search for the right iterator before calling IsLost()
      if (beginOfCurrentPacket >= seq)
        {
          if ((*it)->m_lost == true)
            {
              NS_LOG_INFO ("seq=" << seq << " is lost because of lost flag");
              return true;
            }

          if ((*it)->m_sacked == true)
            {
              NS_LOG_INFO ("seq=" << seq << " is not lost because of sacked flag");
              return false;
            }
        }

      beginOfCurrentPacket += (*it)->m_packet->GetSize ();
    }

  return false;
}

bool
TcpTxBuffer::NextSeg (SequenceNumber32 *seq, bool isRecovery) const
{
  NS_LOG_FUNCTION (this);
  /* RFC 6675, NextSeg definition.
   *
   * (1) If there exists a smallest unSACKed sequence number 'S2' that
   *     meets the following three criteria for determining loss, the
   *     sequence range of one segment of up to SMSS octets starting
   *     with S2 MUST be returned.
   *
   *     (1.a) S2 is greater than HighRxt.
   *
   *     (1.b) S2 is less than the highest octet covered by any
   *           received SACK.
   *
   *     (1.c) IsLost (S2) returns true.
   */
  PacketList::const_iterator it;
  TcpTxItem *item;
  SequenceNumber32 seqPerRule3;
  bool isSeqPerRule3Valid = false;
  SequenceNumber32 beginOfCurrentPkt = m_firstByteSeq;

  for (it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      item = *it;

      // Condition 1.a , 1.b , and 1.c
      if (item->m_retrans == false && item->m_sacked == false)
        {
          if (item->m_lost)
            {
              NS_LOG_INFO("IsLost, returning" << beginOfCurrentPkt);
              *seq = beginOfCurrentPkt;
              return true;
            }
          else if (seqPerRule3.GetValue () == 0 && isRecovery)
            {
              NS_LOG_INFO ("Saving for rule 3 the seq " << beginOfCurrentPkt);
              isSeqPerRule3Valid = true;
              seqPerRule3 = beginOfCurrentPkt;
            }
        }

      // Nothing found, iterate
      beginOfCurrentPkt += item->m_packet->GetSize ();
    }

  /* (2) If no sequence number 'S2' per rule (1) exists but there
   *     exists available unsent data and the receiver's advertised
   *     window allows, the sequence range of one segment of up to SMSS
   *     octets of previously unsent data starting with sequence number
   *     HighData+1 MUST be returned.
   */
  if (SizeFromSequence (m_firstByteSeq + m_sentSize) > 0)
    {
      NS_LOG_INFO ("There is unsent data. Send it");
      *seq = m_firstByteSeq + m_sentSize;
      return true;
    }
  else
    {
      NS_LOG_INFO ("There isn't unsent data.");
    }

  /* (3) If the conditions for rules (1) and (2) fail, but there exists
   *     an unSACKed sequence number 'S3' that meets the criteria for
   *     detecting loss given in steps (1.a) and (1.b) above
   *     (specifically excluding step (1.c)), then one segment of up to
   *     SMSS octets starting with S3 SHOULD be returned.
   */
  if (isSeqPerRule3Valid)
    {
      NS_LOG_INFO ("Rule3 valid. " << seqPerRule3);
      *seq = seqPerRule3;
      return true;
    }

  /* (4) If the conditions for (1), (2), and (3) fail, but there exists
   *     outstanding unSACKed data, we provide the opportunity for a
   *     single "rescue" retransmission per entry into loss recovery.
   *     If HighACK is greater than RescueRxt (or RescueRxt is
   *     undefined), then one segment of up to SMSS octets that MUST
   *     include the highest outstanding unSACKed sequence number
   *     SHOULD be returned, and RescueRxt set to RecoveryPoint.
   *     HighRxt MUST NOT be updated.
   *
   * This point require too much interaction between us and TcpSocketBase.
   * We choose to not respect the SHOULD (allowed from RFC MUST/SHOULD definition)
   */
  NS_LOG_INFO ("Can't return anything");
  return false;
}

uint32_t
TcpTxBuffer::BytesInFlight () const
{
  NS_ASSERT_MSG (m_sackedOut + m_lostOut <= m_sentSize,
                 "Count of sacked " << m_sackedOut << " and lost " << m_lostOut <<
                 " is out of sync with sent list size " << m_sentSize <<
                 " " << *this);
  uint32_t leftOut = m_sackedOut + m_lostOut;
  uint32_t retrans = m_retrans;

  NS_LOG_INFO ("Sent size: " << m_sentSize << " leftOut: " << leftOut <<
               " retrans: " << retrans);
  uint32_t in_flight = m_sentSize - leftOut + retrans;

  //uint32_t rfc_in_flight = BytesInFlightRFC (3, segmentSize);
  //NS_ASSERT_MSG(in_flight == rfc_in_flight,
  //              "Calculated: " << in_flight << " RFC: " << rfc_in_flight <<
  //              "Sent size: " << m_sentSize << " leftOut: " << leftOut <<
  //                             " retrans: " << retrans);
  return in_flight;
}

uint32_t
TcpTxBuffer::BytesInFlightRFC () const
{
  PacketList::const_iterator it;
  TcpTxItem *item;
  uint32_t size = 0; // "pipe" in RFC
  SequenceNumber32 beginOfCurrentPkt = m_firstByteSeq;
  uint32_t sackedOut = 0;
  uint32_t lostOut = 0;
  uint32_t retrans = 0;
  uint32_t totalSize = 0;

  // After initializing pipe to zero, the following steps are taken for each
  // octet 'S1' in the sequence space between HighACK and HighData that has not
  // been SACKed:
  for (it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      item = *it;
      totalSize += item->m_packet->GetSize();
      if (!item->m_sacked)
        {
          bool isLost = IsLostRFC (beginOfCurrentPkt, it);
          // (a) If IsLost (S1) returns false: Pipe is incremented by 1 octet.
          if (!isLost)
            {
              size += item->m_packet->GetSize ();
            }
          // (b) If S1 <= HighRxt: Pipe is incremented by 1 octet.
          // (NOTE: we use the m_retrans flag instead of keeping and updating
          // another variable). Only if the item is not marked as lost
          else if (item->m_retrans)
            {
              size += item->m_packet->GetSize ();
            }

          if (isLost)
            {
              lostOut += item->m_packet->GetSize ();
            }
        }
      else
        {
          sackedOut += item->m_packet->GetSize ();
        }

      if (item->m_retrans)
        {
          retrans += item->m_packet->GetSize ();
        }
      beginOfCurrentPkt += item->m_packet->GetSize ();
    }

  NS_ASSERT_MSG(lostOut == m_lostOut, "Lost counted: " << lostOut << " " <<
                m_lostOut << "\n" << *this);
  NS_ASSERT_MSG(retrans == m_retrans, "Retrans Counted: " << retrans << " " <<
                m_retrans << "\n" << *this);
  NS_ASSERT_MSG(sackedOut == m_sackedOut, "Sacked counted: " << sackedOut <<
                " " << m_sackedOut << *this);
  NS_ASSERT_MSG(totalSize == m_sentSize,
                "Sent size counted: " << totalSize << " " << m_sentSize << *this);

  return size;
}

bool
TcpTxBuffer::IsLostRFC (const SequenceNumber32 &seq, const PacketList::const_iterator &segment) const
{
  NS_LOG_FUNCTION (this << seq);
  uint32_t count = 0;
  uint32_t bytes = 0;
  PacketList::const_iterator it;
  TcpTxItem *item;
  Ptr<const Packet> current;
  SequenceNumber32 beginOfCurrentPacket = seq;

  if ((*segment)->m_sacked == true)
    {
      return false;
    }

  // From RFC 6675:
  // > The routine returns true when either dupThresh discontiguous SACKed
  // > sequences have arrived above 'seq' or more than (dupThresh - 1) * SMSS bytes
  // > with sequence numbers greater than 'SeqNum' have been SACKed.  Otherwise, the
  // > routine returns false.
  for (it = segment; it != m_sentList.end (); ++it)
    {
      item = *it;
      current = item->m_packet;

      if (item->m_sacked)
        {
          NS_LOG_INFO ("Segment " << *item <<
                       " found to be SACKed while checking for " << seq);
          ++count;
          bytes += current->GetSize ();
          if ((count >= m_dupAckThresh) || (bytes > (m_dupAckThresh-1) * m_segmentSize))
            {
              NS_LOG_INFO ("seq=" << seq << " is lost because of 3 sacked blocks ahead");
              return true;
            }
        }

      if (beginOfCurrentPacket >= m_highestSack.second)
        {
          if (item->m_lost && !item->m_retrans)
            return true;

          NS_LOG_INFO ("seq=" << seq << " is not lost because there are no sacked segment ahead");
          return false;
        }

      beginOfCurrentPacket += current->GetSize ();
    }
  if (it == m_highestSack.first)
    {
      NS_LOG_INFO ("seq=" << seq << " is not lost because there are no sacked segment ahead " << m_highestSack.second);
    }
  return false;
}

void
TcpTxBuffer::ResetRenoSack ()
{
  NS_LOG_FUNCTION (this);

  m_sackedOut = 0;
  for (auto it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      (*it)->m_sacked = false;
    }

  m_highestSack = std::make_pair (m_sentList.end (), SequenceNumber32 (0));
}

void
TcpTxBuffer::ResetSentList ()
{
  NS_LOG_FUNCTION (this);
  TcpTxItem *item;

  // Keep the head items; they will then marked as lost
  while (m_sentList.size () > 0)
    {
      item = m_sentList.back ();
      item->m_retrans = item->m_sacked = item->m_lost = false;
      m_appList.push_front (item);
      m_sentList.pop_back ();
    }

  m_sentSize = 0;
  m_lostOut = 0;
  m_retrans = 0;
  m_sackedOut = 0;
  m_highestSack = std::make_pair (m_sentList.end (), SequenceNumber32 (0));
}

void
TcpTxBuffer::ResetLastSegmentSent ()
{
  NS_LOG_FUNCTION (this);
  if (!m_sentList.empty ())
    {
      TcpTxItem *item = m_sentList.back ();

      m_sentList.pop_back ();
      m_sentSize -= item->m_packet->GetSize ();
      if (item->m_retrans)
        {
          m_retrans -= item->m_packet->GetSize ();
        }
      m_appList.insert (m_appList.begin (), item);
    }
  ConsistencyCheck ();
}

void
TcpTxBuffer::SetSentListLost (bool resetSack)
{
  NS_LOG_FUNCTION (this);
  m_retrans = 0;

  if (resetSack)
    {
      m_sackedOut = 0;
      m_lostOut = m_sentSize;
      m_highestSack = std::make_pair (m_sentList.end (), SequenceNumber32 (0));
    }
  else
    {
      m_lostOut = 0;
    }

  for (auto it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      if (resetSack)
        {
          (*it)->m_sacked = false;
          (*it)->m_lost = true;
        }
      else
        {
          if ((*it)->m_lost)
            {
              // Have to increment it because we set it to 0 at line 1133
              m_lostOut += (*it)->m_packet->GetSize ();
            }
          else if (!(*it)->m_sacked)
            {
              // Packet is not marked lost, nor is sacked. Then it becomes lost.
              (*it)->m_lost = true;
              m_lostOut += (*it)->m_packet->GetSize ();
            }
        }

      (*it)->m_retrans = false;
    }

  NS_LOG_INFO ("Set sent list lost, status: " << *this);
  NS_ASSERT_MSG (m_sentSize >= m_sackedOut + m_lostOut, *this);
  ConsistencyCheck ();
}

bool
TcpTxBuffer::IsHeadRetransmitted () const
{
  NS_LOG_FUNCTION (this);

  if (m_sentSize == 0)
    {
      return false;
    }

  return m_sentList.front ()->m_retrans;
}

void
TcpTxBuffer::DeleteRetransmittedFlagFromHead ()
{
  NS_LOG_FUNCTION (this);

  if (m_sentSize == 0)
    {
      return;
    }

  if (m_sentList.front ()->m_retrans)
    {
      m_sentList.front ()->m_retrans = false;
      m_retrans -= m_sentList.front ()->m_packet->GetSize ();
    }
  ConsistencyCheck ();
}

void
TcpTxBuffer::MarkHeadAsLost ()
{
  if (m_sentList.size () > 0)
    {
      // If the head is sacked (reneging by the receiver the previously sent
      // information) we revert the sacked flag.
      // A sacked head means that we should advance SND.UNA.. so it's an error.
      if (m_sentList.front ()->m_sacked)
        {
          m_sentList.front ()->m_sacked = false;
          m_sackedOut -= m_sentList.front ()->m_packet->GetSize ();
        }

      if (m_sentList.front ()->m_retrans)
        {
          m_sentList.front ()->m_retrans = false;
          m_retrans -= m_sentList.front ()->m_packet->GetSize ();
        }

      if (! m_sentList.front()->m_lost)
        {
          m_sentList.front()->m_lost = true;
          m_lostOut += m_sentList.front ()->m_packet->GetSize ();
        }
    }
  ConsistencyCheck ();
}

void
TcpTxBuffer::AddRenoSack (void)
{
  NS_LOG_FUNCTION (this);
  
  if (m_sentList.size () <= 1)  //patch for the error of "not checking if SACK is enabled" before ASSERT
  {
    NS_LOG_INFO ("Request to add a reno SACK, but the sent list is 1. Ignore the request.");
    return;
  }

NS_ASSERT (m_sentList.size () > 1);

m_renoSack = true;

  // We can _never_ SACK the head, so start from the second segment sent
  auto it = ++m_sentList.begin ();

  // Find the "highest sacked" point, that is SND.UNA + m_sackedOut
  while (it != m_sentList.end () && (*it)->m_sacked)
    {
      ++it;
    }

  // Add to the sacked size the size of the first "not sacked" segment
  if (it != m_sentList.end ())
    {
      (*it)->m_sacked = true;
      m_sackedOut += (*it)->m_packet->GetSize ();
      m_highestSack = std::make_pair (it, (*it)->m_startSeq);
      NS_LOG_INFO ("Added a Reno SACK, status: " << *this);
    }
  else
    {
      NS_LOG_INFO ("Can't add a Reno SACK because we miss segments. This dupack"
                   " should be arrived from spurious retransmissions");
    }

  ConsistencyCheck ();
}

void
TcpTxBuffer::ConsistencyCheck () const
{
  static const bool enable = false;

  if (!enable)
    {
      return;
    }

  uint32_t sacked = 0;
  uint32_t lost = 0;
  uint32_t retrans = 0;

  for (auto it = m_sentList.begin (); it != m_sentList.end (); ++it)
    {
      if ((*it)->m_sacked)
        {
          sacked += (*it)->m_packet->GetSize ();
        }
      if ((*it)->m_lost)
        {
          lost += (*it)->m_packet->GetSize ();
        }
      if ((*it)->m_retrans)
        {
          retrans += (*it)->m_packet->GetSize ();
        }
    }

  NS_ASSERT_MSG (sacked == m_sackedOut, "Counted SACK: " << sacked <<
                 " stored SACK: " << m_sackedOut);
  NS_ASSERT_MSG (lost == m_lostOut, " Counted lost: " << lost <<
                 " stored lost: " << m_lostOut);
  NS_ASSERT_MSG (retrans == m_retrans, " Counted retrans: " << retrans <<
                 " stored retrans: " << m_retrans);
}

std::ostream &
operator<< (std::ostream & os, TcpTxItem const & item)
{
  item.Print (os);
  return os;
}

std::ostream &
operator<< (std::ostream & os, TcpTxBuffer const & tcpTxBuf)
{
  TcpTxBuffer::PacketList::const_iterator it;
  std::stringstream ss;
  SequenceNumber32 beginOfCurrentPacket = tcpTxBuf.m_firstByteSeq;
  uint32_t sentSize = 0, appSize = 0;

  Ptr<Packet> p;
  for (it = tcpTxBuf.m_sentList.begin (); it != tcpTxBuf.m_sentList.end (); ++it)
    {
      p = (*it)->m_packet;
      ss << "{";
      (*it)->Print (ss);
      ss << "}";
      sentSize += p->GetSize ();
      beginOfCurrentPacket += p->GetSize ();
    }

  for (it = tcpTxBuf.m_appList.begin (); it != tcpTxBuf.m_appList.end (); ++it)
    {
      appSize += (*it)->m_packet->GetSize ();
    }

  os << "Sent list: " << ss.str () << ", size = " << tcpTxBuf.m_sentList.size () <<
    " Total size: " << tcpTxBuf.m_size <<
    " m_firstByteSeq = " << tcpTxBuf.m_firstByteSeq <<
    " m_sentSize = " << tcpTxBuf.m_sentSize <<
    " m_retransOut = " << tcpTxBuf.m_retrans <<
    " m_lostOut = " << tcpTxBuf.m_lostOut <<
    " m_sackedOut = " << tcpTxBuf.m_sackedOut;

  NS_ASSERT (sentSize == tcpTxBuf.m_sentSize);
  NS_ASSERT (tcpTxBuf.m_size - tcpTxBuf.m_sentSize == appSize);
  return os;
}

} // namespace ns3