byte-tag-list.cc

Go to the documentation of this file.

/*
 * Copyright (c) 2008 INRIA
 *
 * 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
 *
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
 */
#include "byte-tag-list.h"
 
#include "ns3/log.h"
 
#include <cstring>
#include <limits>
#include <vector>
 
#define USE_FREE_LIST 1
#define FREE_LIST_SIZE 1000
#define OFFSET_MAX (std::numeric_limits<int32_t>::max())
 
namespace ns3
{
 
NS_LOG_COMPONENT_DEFINE("ByteTagList");
 
struct ByteTagListData
{
    uint32_t size;   
    uint32_t count;  
    uint32_t dirty;  
    uint8_t data[4]; 
};
 
#ifdef USE_FREE_LIST
static class ByteTagListDataFreeList : public std::vector<ByteTagListData*>
{
  public:
    ~ByteTagListDataFreeList();
} g_freeList; 
 
static uint32_t g_maxSize = 0; 
 
ByteTagListDataFreeList::~ByteTagListDataFreeList()
{
    NS_LOG_FUNCTION(this);
    for (auto i = begin(); i != end(); i++)
    {
        auto buffer = (uint8_t*)(*i);
        delete[] buffer;
    }
}
#endif /* USE_FREE_LIST */
 
ByteTagList::Iterator::Item::Item(TagBuffer buf_)
    : buf(buf_)
{
    NS_LOG_FUNCTION(this << &buf_);
}
 
bool
ByteTagList::Iterator::HasNext() const
{
    NS_LOG_FUNCTION(this);
    return m_current < m_end;
}
 
ByteTagList::Iterator::Item
ByteTagList::Iterator::Next()
{
    NS_ASSERT(HasNext());
    Item item = Item(TagBuffer(m_current + 16, m_end));
    item.tid.SetUid(m_nextTid);
    item.size = m_nextSize;
    item.start = std::max(m_nextStart, m_offsetStart);
    item.end = std::min(m_nextEnd, m_offsetEnd);
    m_current += 4 + 4 + 4 + 4 + item.size;
    item.buf.TrimAtEnd(m_end - m_current);
    PrepareForNext();
    return item;
}
 
void
ByteTagList::Iterator::PrepareForNext()
{
    NS_LOG_FUNCTION(this);
    while (m_current < m_end)
    {
        TagBuffer buf = TagBuffer(m_current, m_end);
        m_nextTid = buf.ReadU32();
        m_nextSize = buf.ReadU32();
        m_nextStart = buf.ReadU32() + m_adjustment;
        m_nextEnd = buf.ReadU32() + m_adjustment;
        if (m_nextStart >= m_offsetEnd || m_nextEnd <= m_offsetStart)
        {
            m_current += 4 + 4 + 4 + 4 + m_nextSize;
        }
        else
        {
            break;
        }
    }
}
 
ByteTagList::Iterator::Iterator(uint8_t* start,
                                uint8_t* end,
                                int32_t offsetStart,
                                int32_t offsetEnd,
                                int32_t adjustment)
    : m_current(start),
      m_end(end),
      m_offsetStart(offsetStart),
      m_offsetEnd(offsetEnd),
      m_adjustment(adjustment)
{
    NS_LOG_FUNCTION(this << &start << &end << offsetStart << offsetEnd << adjustment);
    PrepareForNext();
}
 
uint32_t
ByteTagList::Iterator::GetOffsetStart() const
{
    NS_LOG_FUNCTION(this);
    return m_offsetStart;
}
 
ByteTagList::ByteTagList()
    : m_minStart(INT32_MAX),
      m_maxEnd(INT32_MIN),
      m_adjustment(0),
      m_used(0),
      m_data(nullptr)
{
    NS_LOG_FUNCTION(this);
}
 
ByteTagList::ByteTagList(const ByteTagList& o)
    : m_minStart(o.m_minStart),
      m_maxEnd(o.m_maxEnd),
      m_adjustment(o.m_adjustment),
      m_used(o.m_used),
      m_data(o.m_data)
{
    NS_LOG_FUNCTION(this << &o);
    if (m_data != nullptr)
    {
        m_data->count++;
    }
}
 
ByteTagList&
ByteTagList::operator=(const ByteTagList& o)
{
    if (this == &o)
    {
        return *this;
    }
 
    Deallocate(m_data);
    m_minStart = o.m_minStart;
    m_maxEnd = o.m_maxEnd;
    m_adjustment = o.m_adjustment;
    m_data = o.m_data;
    m_used = o.m_used;
    if (m_data != nullptr)
    {
        m_data->count++;
    }
    return *this;
}
 
ByteTagList::~ByteTagList()
{
    NS_LOG_FUNCTION(this);
    Deallocate(m_data);
    m_data = nullptr;
    m_used = 0;
}
 
TagBuffer
ByteTagList::Add(TypeId tid, uint32_t bufferSize, int32_t start, int32_t end)
{
    NS_LOG_FUNCTION(this << tid << bufferSize << start << end);
    uint32_t spaceNeeded = m_used + bufferSize + 4 + 4 + 4 + 4;
    NS_ASSERT(m_used <= spaceNeeded);
    if (m_data == nullptr)
    {
        m_data = Allocate(spaceNeeded);
        m_used = 0;
    }
    else if (m_data->size < spaceNeeded || (m_data->count != 1 && m_data->dirty != m_used))
    {
        ByteTagListData* newData = Allocate(spaceNeeded);
        std::memcpy(&newData->data, &m_data->data, m_used);
        Deallocate(m_data);
        m_data = newData;
    }
    TagBuffer tag = TagBuffer(&m_data->data[m_used], &m_data->data[spaceNeeded]);
    tag.WriteU32(tid.GetUid());
    tag.WriteU32(bufferSize);
    tag.WriteU32(start - m_adjustment);
    tag.WriteU32(end - m_adjustment);
    if (start - m_adjustment < m_minStart)
    {
        m_minStart = start - m_adjustment;
    }
    if (end - m_adjustment > m_maxEnd)
    {
        m_maxEnd = end - m_adjustment;
    }
    m_used = spaceNeeded;
    m_data->dirty = m_used;
    return tag;
}
 
void
ByteTagList::Add(const ByteTagList& o)
{
    NS_LOG_FUNCTION(this << &o);
    ByteTagList::Iterator i = o.BeginAll();
    while (i.HasNext())
    {
        ByteTagList::Iterator::Item item = i.Next();
        TagBuffer buf = Add(item.tid, item.size, item.start, item.end);
        buf.CopyFrom(item.buf);
    }
}
 
void
ByteTagList::RemoveAll()
{
    NS_LOG_FUNCTION(this);
    Deallocate(m_data);
    m_minStart = INT32_MAX;
    m_maxEnd = INT32_MIN;
    m_adjustment = 0;
    m_data = nullptr;
    m_used = 0;
}
 
ByteTagList::Iterator
ByteTagList::BeginAll() const
{
    NS_LOG_FUNCTION(this);
    // I am not totally sure but I might need to use
    // INT32_MIN instead of zero below.
    return Begin(0, OFFSET_MAX);
}
 
ByteTagList::Iterator
ByteTagList::Begin(int32_t offsetStart, int32_t offsetEnd) const
{
    NS_LOG_FUNCTION(this << offsetStart << offsetEnd);
    if (m_data == nullptr)
    {
        return Iterator(nullptr, nullptr, offsetStart, offsetEnd, 0);
    }
    else
    {
        return Iterator(m_data->data, &m_data->data[m_used], offsetStart, offsetEnd, m_adjustment);
    }
}
 
void
ByteTagList::AddAtEnd(int32_t appendOffset)
{
    NS_LOG_FUNCTION(this << appendOffset);
    if (m_maxEnd <= appendOffset - m_adjustment)
    {
        return;
    }
    ByteTagList list;
    ByteTagList::Iterator i = BeginAll();
    while (i.HasNext())
    {
        ByteTagList::Iterator::Item item = i.Next();
 
        if (item.start >= appendOffset)
        {
            continue;
        }
        if (item.end > appendOffset)
        {
            item.end = appendOffset;
        }
        TagBuffer buf = list.Add(item.tid, item.size, item.start, item.end);
        buf.CopyFrom(item.buf);
        if (item.end > m_maxEnd)
        {
            m_maxEnd = item.end;
        }
    }
    *this = list;
}
 
void
ByteTagList::AddAtStart(int32_t prependOffset)
{
    NS_LOG_FUNCTION(this << prependOffset);
    if (m_minStart >= prependOffset - m_adjustment)
    {
        return;
    }
    m_minStart = INT32_MAX;
    ByteTagList list;
    ByteTagList::Iterator i = BeginAll();
    while (i.HasNext())
    {
        ByteTagList::Iterator::Item item = i.Next();
 
        if (item.end <= prependOffset)
        {
            continue;
        }
        if (item.start < prependOffset)
        {
            item.start = prependOffset;
        }
        TagBuffer buf = list.Add(item.tid, item.size, item.start, item.end);
        buf.CopyFrom(item.buf);
        if (item.start < m_minStart)
        {
            m_minStart = item.start;
        }
    }
    *this = list;
}
 
#ifdef USE_FREE_LIST
 
ByteTagListData*
ByteTagList::Allocate(uint32_t size)
{
    NS_LOG_FUNCTION(this << size);
    while (!g_freeList.empty())
    {
        ByteTagListData* data = g_freeList.back();
        g_freeList.pop_back();
        NS_ASSERT(data != nullptr);
        if (data->size >= size)
        {
            data->count = 1;
            data->dirty = 0;
            return data;
        }
        auto buffer = (uint8_t*)data;
        delete[] buffer;
    }
    auto buffer = new uint8_t[std::max(size, g_maxSize) + sizeof(ByteTagListData) - 4];
    auto data = (ByteTagListData*)buffer;
    data->count = 1;
    data->size = size;
    data->dirty = 0;
    return data;
}
 
void
ByteTagList::Deallocate(ByteTagListData* data)
{
    NS_LOG_FUNCTION(this << data);
    if (data == nullptr)
    {
        return;
    }
    g_maxSize = std::max(g_maxSize, data->size);
    data->count--;
    if (data->count == 0)
    {
        if (g_freeList.size() > FREE_LIST_SIZE || data->size < g_maxSize)
        {
            auto buffer = (uint8_t*)data;
            delete[] buffer;
        }
        else
        {
            g_freeList.push_back(data);
        }
    }
}
 
#else /* USE_FREE_LIST */
 
ByteTagListData*
ByteTagList::Allocate(uint32_t size)
{
    NS_LOG_FUNCTION(this << size);
    uint8_t* buffer = new uint8_t[size + sizeof(ByteTagListData) - 4];
    ByteTagListData* data = (ByteTagListData*)buffer;
    data->count = 1;
    data->size = size;
    data->dirty = 0;
    return data;
}
 
void
ByteTagList::Deallocate(ByteTagListData* data)
{
    NS_LOG_FUNCTION(this << data);
    if (data == 0)
    {
        return;
    }
    data->count--;
    if (data->count == 0)
    {
        uint8_t* buffer = (uint8_t*)data;
        delete[] buffer;
    }
}
 
#endif /* USE_FREE_LIST */
 
uint32_t
ByteTagList::GetSerializedSize() const
{
    NS_LOG_FUNCTION_NOARGS();
 
    uint32_t size = 0;
 
    // Number of tags in list
    size += 4; // numberOfTags
 
    ByteTagList::Iterator i = BeginAll();
    while (i.HasNext())
    {
        ByteTagList::Iterator::Item item = i.Next();
 
        // TypeId hash; ensure size is multiple of 4 bytes
        uint32_t hashSize = (sizeof(TypeId::hash_t) + 3) & (~3);
        size += hashSize;
 
        size += 3 * 4; // size, start, end
 
        // tag data; ensure size is multiple of 4 bytes
        uint32_t tagWordSize = (item.size + 3) & (~3);
        size += tagWordSize;
    }
 
    return size;
}
 
uint32_t
ByteTagList::Serialize(uint32_t* buffer, uint32_t maxSize) const
{
    NS_LOG_FUNCTION(this << buffer << maxSize);
 
    uint32_t* p = buffer;
    uint32_t size = 0;
 
    size += 4;
 
    if (size > maxSize)
    {
        return 0;
    }
 
    uint32_t* numberOfTags = p;
    *p++ = 0;
 
    ByteTagList::Iterator i = BeginAll();
    while (i.HasNext())
    {
        ByteTagList::Iterator::Item item = i.Next();
 
        NS_LOG_INFO("Serializing " << item.tid);
 
        // ensure size is multiple of 4 bytes for 4 byte boundaries
        uint32_t hashSize = (sizeof(TypeId::hash_t) + 3) & (~3);
        size += hashSize;
 
        if (size > maxSize)
        {
            return 0;
        }
 
        TypeId::hash_t tid = item.tid.GetHash();
        memcpy(p, &tid, sizeof(TypeId::hash_t));
        p += hashSize / 4;
 
        size += 4;
 
        if (size > maxSize)
        {
            return 0;
        }
 
        *p++ = item.size;
 
        size += 4;
 
        if (size > maxSize)
        {
            return 0;
        }
 
        *p++ = item.start;
 
        size += 4;
 
        if (size > maxSize)
        {
            return 0;
        }
 
        *p++ = item.end;
 
        // ensure size is multiple of 4 bytes for 4 byte boundaries
        uint32_t tagWordSize = (item.size + 3) & (~3);
        size += tagWordSize;
 
        if (size > maxSize)
        {
            return 0;
        }
 
        item.buf.Read(reinterpret_cast<uint8_t*>(p), item.size);
        p += tagWordSize / 4;
 
        (*numberOfTags)++;
    }
 
    // Serialized successfully
    return 1;
}
 
uint32_t
ByteTagList::Deserialize(const uint32_t* buffer, uint32_t size)
{
    NS_LOG_FUNCTION(this << buffer << size);
    const uint32_t* p = buffer;
    uint32_t sizeCheck = size - 4;
 
    NS_ASSERT(sizeCheck >= 4);
    uint32_t numberTagData = *p++;
    sizeCheck -= 4;
 
    NS_LOG_INFO("Deserializing number of tags " << numberTagData);
 
    for (uint32_t i = 0; i < numberTagData; ++i)
    {
        uint32_t hashSize = (sizeof(TypeId::hash_t) + 3) & (~3);
        NS_ASSERT(sizeCheck >= hashSize);
        TypeId::hash_t hash;
        memcpy(&hash, p, sizeof(TypeId::hash_t));
        p += hashSize / 4;
        sizeCheck -= hashSize;
 
        TypeId tid = TypeId::LookupByHash(hash);
 
        NS_ASSERT(sizeCheck >= 4);
        uint32_t bufferSize = *p++;
        sizeCheck -= 4;
 
        NS_ASSERT(sizeCheck >= 4);
        uint32_t start = *p++;
        sizeCheck -= 4;
 
        NS_ASSERT(sizeCheck >= 4);
        uint32_t end = *p++;
        sizeCheck -= 4;
 
        NS_ASSERT(sizeCheck >= bufferSize);
        TagBuffer buf = Add(tid, bufferSize, start, end);
        buf.Write(reinterpret_cast<const uint8_t*>(p), bufferSize);
 
        // ensure 4 byte boundary
        uint32_t tagSizeBytes = (bufferSize + 3) & (~3);
        sizeCheck -= tagSizeBytes;
        p += tagSizeBytes / 4;
    }
 
    NS_ASSERT(sizeCheck == 0);
 
    // return zero if buffer did not
    // contain a complete message
    return (sizeCheck != 0) ? 0 : 1;
}
 
} // namespace ns3