A Discrete-Event Network Simulator
API
byte-tag-list.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2008 INRIA
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: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19  */
20 #include "byte-tag-list.h"
21 #include "ns3/log.h"
22 #include <vector>
23 #include <cstring>
24 #include <limits>
25 
26 #define USE_FREE_LIST 1
27 #define FREE_LIST_SIZE 1000
28 #define OFFSET_MAX (std::numeric_limits<int32_t>::max ())
29 
30 namespace ns3 {
31 
32 NS_LOG_COMPONENT_DEFINE ("ByteTagList");
33 
42  uint32_t size;
43  uint32_t count;
44  uint32_t dirty;
45  uint8_t data[4];
46 };
47 
48 #ifdef USE_FREE_LIST
49 
56 static class ByteTagListDataFreeList : public std::vector<struct ByteTagListData *>
57 {
58 public:
60 } g_freeList;
61 static uint32_t g_maxSize = 0;
62 
64 {
65  NS_LOG_FUNCTION (this);
66  for (ByteTagListDataFreeList::iterator i = begin ();
67  i != end (); i++)
68  {
69  uint8_t *buffer = (uint8_t *)(*i);
70  delete [] buffer;
71  }
72 }
73 #endif /* USE_FREE_LIST */
74 
76  : buf (buf_)
77 {
78  NS_LOG_FUNCTION (this << &buf_);
79 }
80 
81 bool
83 {
84  NS_LOG_FUNCTION (this);
85  return m_current < m_end;
86 }
89 {
90  NS_ASSERT (HasNext ());
91  struct Item item = Item (TagBuffer (m_current+16, m_end));
92  item.tid.SetUid (m_nextTid);
93  item.size = m_nextSize;
96  m_current += 4 + 4 + 4 + 4 + item.size;
97  item.buf.TrimAtEnd (m_end - m_current);
98  PrepareForNext ();
99  return item;
100 }
101 void
103 {
104  NS_LOG_FUNCTION (this);
105  while (m_current < m_end)
106  {
108  m_nextTid = buf.ReadU32 ();
109  m_nextSize = buf.ReadU32 ();
110  m_nextStart = buf.ReadU32 () + m_adjustment;
111  m_nextEnd = buf.ReadU32 () + m_adjustment;
113  {
114  m_current += 4 + 4 + 4 + 4 + m_nextSize;
115  }
116  else
117  {
118  break;
119  }
120  }
121 }
122 ByteTagList::Iterator::Iterator (uint8_t *start, uint8_t *end, int32_t offsetStart, int32_t offsetEnd, int32_t adjustment)
123  : m_current (start),
124  m_end (end),
125  m_offsetStart (offsetStart),
126  m_offsetEnd (offsetEnd),
127  m_adjustment (adjustment)
128 {
129  NS_LOG_FUNCTION (this << &start << &end << offsetStart << offsetEnd << adjustment);
130  PrepareForNext ();
131 }
132 
133 uint32_t
135 {
136  NS_LOG_FUNCTION (this);
137  return m_offsetStart;
138 }
139 
140 
142  : m_minStart (INT32_MAX),
143  m_maxEnd (INT32_MIN),
144  m_adjustment (0),
145  m_used (0),
146  m_data (0)
147 {
148  NS_LOG_FUNCTION (this);
149 }
151  : m_minStart (o.m_minStart),
152  m_maxEnd (o.m_maxEnd),
153  m_adjustment (o.m_adjustment),
154  m_used (o.m_used),
155  m_data (o.m_data)
156 {
157  NS_LOG_FUNCTION (this << &o);
158  if (m_data != 0)
159  {
160  m_data->count++;
161  }
162 }
163 ByteTagList &
165 {
166  if (this == &o)
167  {
168  return *this;
169  }
170 
171  Deallocate (m_data);
173  m_maxEnd = o.m_maxEnd;
175  m_data = o.m_data;
176  m_used = o.m_used;
177  if (m_data != 0)
178  {
179  m_data->count++;
180  }
181  return *this;
182 }
184 {
185  NS_LOG_FUNCTION (this);
186  Deallocate (m_data);
187  m_data = 0;
188  m_used = 0;
189 }
190 
191 TagBuffer
192 ByteTagList::Add (TypeId tid, uint32_t bufferSize, int32_t start, int32_t end)
193 {
194  NS_LOG_FUNCTION (this << tid << bufferSize << start << end);
195  uint32_t spaceNeeded = m_used + bufferSize + 4 + 4 + 4 + 4;
196  NS_ASSERT (m_used <= spaceNeeded);
197  if (m_data == 0)
198  {
199  m_data = Allocate (spaceNeeded);
200  m_used = 0;
201  }
202  else if (m_data->size < spaceNeeded ||
203  (m_data->count != 1 && m_data->dirty != m_used))
204  {
205  struct ByteTagListData *newData = Allocate (spaceNeeded);
206  std::memcpy (&newData->data, &m_data->data, m_used);
207  Deallocate (m_data);
208  m_data = newData;
209  }
210  TagBuffer tag = TagBuffer (&m_data->data[m_used],
211  &m_data->data[spaceNeeded]);
212  tag.WriteU32 (tid.GetUid ());
213  tag.WriteU32 (bufferSize);
214  tag.WriteU32 (start - m_adjustment);
215  tag.WriteU32 (end - m_adjustment);
216  if (start - m_adjustment < m_minStart)
217  {
219  }
220  if (end - m_adjustment > m_maxEnd)
221  {
222  m_maxEnd = end - m_adjustment;
223  }
224  m_used = spaceNeeded;
225  m_data->dirty = m_used;
226  return tag;
227 }
228 
229 void
231 {
232  NS_LOG_FUNCTION (this << &o);
234  while (i.HasNext ())
235  {
236  ByteTagList::Iterator::Item item = i.Next ();
237  TagBuffer buf = Add (item.tid, item.size, item.start, item.end);
238  buf.CopyFrom (item.buf);
239  }
240 }
241 
242 void
244 {
245  NS_LOG_FUNCTION (this);
246  Deallocate (m_data);
247  m_minStart = INT32_MAX;
248  m_maxEnd = INT32_MIN;
249  m_adjustment = 0;
250  m_data = 0;
251  m_used = 0;
252 }
253 
256 {
257  NS_LOG_FUNCTION (this);
258  // I am not totally sure but I might need to use
259  // INT32_MIN instead of zero below.
260  return Begin (0, OFFSET_MAX);
261 }
262 
264 ByteTagList::Begin (int32_t offsetStart, int32_t offsetEnd) const
265 {
266  NS_LOG_FUNCTION (this << offsetStart << offsetEnd);
267  if (m_data == 0)
268  {
269  return Iterator (0, 0, offsetStart, offsetEnd, 0);
270  }
271  else
272  {
273  return Iterator (m_data->data, &m_data->data[m_used], offsetStart, offsetEnd, m_adjustment);
274  }
275 }
276 
277 void
278 ByteTagList::AddAtEnd (int32_t appendOffset)
279 {
280  NS_LOG_FUNCTION (this << appendOffset);
281  if (m_maxEnd <= appendOffset - m_adjustment)
282  {
283  return;
284  }
287  while (i.HasNext ())
288  {
289  ByteTagList::Iterator::Item item = i.Next ();
290 
291  if (item.start >= appendOffset)
292  {
293  continue;
294  }
295  if (item.end > appendOffset)
296  {
297  item.end = appendOffset;
298  }
299  TagBuffer buf = list.Add (item.tid, item.size, item.start, item.end);
300  buf.CopyFrom (item.buf);
301  if (item.end > m_maxEnd)
302  {
303  m_maxEnd = item.end;
304  }
305  }
306  *this = list;
307 }
308 
309 void
310 ByteTagList::AddAtStart (int32_t prependOffset)
311 {
312  NS_LOG_FUNCTION (this << prependOffset);
313  if (m_minStart >= prependOffset - m_adjustment)
314  {
315  return;
316  }
317  m_minStart = INT32_MAX;
320  while (i.HasNext ())
321  {
322  ByteTagList::Iterator::Item item = i.Next ();
323 
324  if (item.end <= prependOffset)
325  {
326  continue;
327  }
328  if (item.start < prependOffset)
329  {
330  item.start = prependOffset;
331  }
332  TagBuffer buf = list.Add (item.tid, item.size, item.start, item.end);
333  buf.CopyFrom (item.buf);
334  if (item.start < m_minStart)
335  {
336  m_minStart = item.start;
337  }
338  }
339  *this = list;
340 }
341 
342 #ifdef USE_FREE_LIST
343 
344 struct ByteTagListData *
345 ByteTagList::Allocate (uint32_t size)
346 {
347  NS_LOG_FUNCTION (this << size);
348  while (!g_freeList.empty ())
349  {
350  struct ByteTagListData *data = g_freeList.back ();
351  g_freeList.pop_back ();
352  NS_ASSERT (data != 0);
353  if (data->size >= size)
354  {
355  data->count = 1;
356  data->dirty = 0;
357  return data;
358  }
359  uint8_t *buffer = (uint8_t *)data;
360  delete [] buffer;
361  }
362  uint8_t *buffer = new uint8_t [std::max (size, g_maxSize) + sizeof (struct ByteTagListData) - 4];
363  struct ByteTagListData *data = (struct ByteTagListData *)buffer;
364  data->count = 1;
365  data->size = size;
366  data->dirty = 0;
367  return data;
368 }
369 
370 void
372 {
373  NS_LOG_FUNCTION (this << data);
374  if (data == 0)
375  {
376  return;
377  }
378  g_maxSize = std::max (g_maxSize, data->size);
379  data->count--;
380  if (data->count == 0)
381  {
382  if (g_freeList.size () > FREE_LIST_SIZE ||
383  data->size < g_maxSize)
384  {
385  uint8_t *buffer = (uint8_t *)data;
386  delete [] buffer;
387  }
388  else
389  {
390  g_freeList.push_back (data);
391  }
392  }
393 }
394 
395 #else /* USE_FREE_LIST */
396 
397 struct ByteTagListData *
398 ByteTagList::Allocate (uint32_t size)
399 {
400  NS_LOG_FUNCTION (this << size);
401  uint8_t *buffer = new uint8_t [size + sizeof (struct ByteTagListData) - 4];
402  struct ByteTagListData *data = (struct ByteTagListData *)buffer;
403  data->count = 1;
404  data->size = size;
405  data->dirty = 0;
406  return data;
407 }
408 
409 void
410 ByteTagList::Deallocate (struct ByteTagListData *data)
411 {
412  NS_LOG_FUNCTION (this << data);
413  if (data == 0)
414  {
415  return;
416  }
417  data->count--;
418  if (data->count == 0)
419  {
420  uint8_t *buffer = (uint8_t *)data;
421  delete [] buffer;
422  }
423 }
424 
425 #endif /* USE_FREE_LIST */
426 
427 uint32_t
429 {
431 
432  uint32_t size = 0;
433 
434  // Number of tags in list
435  size += 4; // numberOfTags
436 
438  while (i.HasNext ())
439  {
440  ByteTagList::Iterator::Item item = i.Next ();
441 
442  // TypeId hash; ensure size is multiple of 4 bytes
443  uint32_t hashSize = (sizeof (TypeId::hash_t)+3) & (~3);
444  size += hashSize;
445 
446  size += 3 * 4; // size, start, end
447 
448  // tag data; ensure size is multiple of 4 bytes
449  uint32_t tagWordSize = (item.size+3) & (~3);
450  size += tagWordSize;
451  }
452 
453  return size;
454 }
455 
456 uint32_t
457 ByteTagList::Serialize (uint32_t* buffer, uint32_t maxSize) const
458 {
459  NS_LOG_FUNCTION (this << buffer << maxSize);
460 
461  uint32_t* p = buffer;
462  uint32_t size = 0;
463 
464  uint32_t* numberOfTags = 0;
465 
466  if (size + 4 <= maxSize)
467  {
468  numberOfTags = p;
469  *p++ = 0;
470  size += 4;
471  }
472  else
473  {
474  return 0;
475  }
476 
478  while (i.HasNext ())
479  {
480  ByteTagList::Iterator::Item item = i.Next ();
481 
482  NS_LOG_INFO ("Serializing " << item.tid);
483 
484  // ensure size is multiple of 4 bytes for 4 byte boundaries
485  uint32_t hashSize = (sizeof (TypeId::hash_t)+3) & (~3);
486  if (size + hashSize <= maxSize)
487  {
488  TypeId::hash_t tid = item.tid.GetHash ();
489  memcpy (p, &tid, sizeof (TypeId::hash_t));
490  p += hashSize / 4;
491  size += hashSize;
492  }
493  else
494  {
495  return 0;
496  }
497 
498  if (size + 4 <= maxSize)
499  {
500  *p++ = item.size;
501  size += 4;
502  }
503  else
504  {
505  return 0;
506  }
507 
508  if (size + 4 <= maxSize)
509  {
510  *p++ = item.start;
511  size += 4;
512  }
513  else
514  {
515  return 0;
516  }
517 
518  if (size + 4 <= maxSize)
519  {
520  *p++ = item.end;
521  size += 4;
522  }
523  else
524  {
525  return 0;
526  }
527 
528  // ensure size is multiple of 4 bytes for 4 byte boundaries
529  uint32_t tagWordSize = (item.size+3) & (~3);
530 
531  if (size + tagWordSize <= maxSize)
532  {
533  item.buf.Read (reinterpret_cast<uint8_t *> (p), item.size);
534  size += tagWordSize;
535  p += tagWordSize / 4;
536  }
537  else
538  {
539  return 0;
540  }
541 
542  (*numberOfTags)++;
543  }
544 
545  // Serialized successfully
546  return 1;
547 }
548 
549 uint32_t
550 ByteTagList::Deserialize (const uint32_t* buffer, uint32_t size)
551 {
552  NS_LOG_FUNCTION (this << buffer << size);
553  const uint32_t* p = buffer;
554  uint32_t sizeCheck = size - 4;
555 
556  NS_ASSERT (sizeCheck >= 4);
557  uint32_t numberTagData = *p++;
558  sizeCheck -= 4;
559 
560  NS_LOG_INFO ("Deserializing number of tags " << numberTagData);
561 
562  for(uint32_t i = 0; i < numberTagData; ++i)
563  {
564  uint32_t hashSize = (sizeof (TypeId::hash_t)+3) & (~3);
565  NS_ASSERT (sizeCheck >= hashSize);
567  memcpy (&hash, p, sizeof (TypeId::hash_t));
568  p += hashSize / 4;
569  sizeCheck -= hashSize;
570 
572 
573  NS_ASSERT (sizeCheck >= 4);
574  uint32_t bufferSize = *p++;
575  sizeCheck -= 4;
576 
577  NS_ASSERT (sizeCheck >= 4);
578  uint32_t start = *p++;
579  sizeCheck -= 4;
580 
581  NS_ASSERT (sizeCheck >= 4);
582  uint32_t end = *p++;
583  sizeCheck -= 4;
584 
585  NS_ASSERT (sizeCheck >= bufferSize);
586  TagBuffer buf = Add (tid, bufferSize, start, end);
587  buf.Write ( reinterpret_cast<const uint8_t *> (p), bufferSize);
588 
589  // ensure 4 byte boundary
590  uint32_t tagSizeBytes = (bufferSize+3) & (~3);
591  sizeCheck -= tagSizeBytes;
592  p += tagSizeBytes / 4;
593  }
594 
595  NS_ASSERT (sizeCheck == 0);
596 
597  // return zero if buffer did not
598  // contain a complete message
599  return (sizeCheck != 0) ? 0 : 1;
600 }
601 
602 } // namespace ns3
uint32_t Deserialize(const uint32_t *buffer, uint32_t size)
Deserialize tag list from the provided buffer.
uint32_t hash_t
Type of hash values.
Definition: type-id.h:116
void Write(const uint8_t *buffer, uint32_t size)
Definition: tag-buffer.cc:125
hash_t GetHash(void) const
Get the hash.
Definition: type-id.cc:985
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
uint32_t dirty
number of bytes actually in use
ByteTagList & operator=(const ByteTagList &o)
Assignment operator, deallocates current data and assigns value of passed in ByteTagList.
#define min(a, b)
Definition: 80211b.c:42
static TypeId LookupByHash(hash_t hash)
Get a TypeId by hash.
Definition: type-id.cc:850
struct ByteTagListData * m_data
the ByteTagListData structure
uint32_t count
use counter (for smart deallocation)
def start()
Definition: core.py:1855
uint32_t GetSerializedSize(void) const
Returns number of bytes required for packet serialization.
keep track of the byte tags stored in a packet.
Definition: byte-tag-list.h:63
#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:205
TagBuffer Add(TypeId tid, uint32_t bufferSize, int32_t start, int32_t end)
void TrimAtEnd(uint32_t trim)
Trim some space from the end.
Definition: tag-buffer.cc:191
uint32_t m_nextTid
TypeId of the next tag.
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
TAG_BUFFER_INLINE uint32_t ReadU32(void)
Definition: tag-buffer.h:215
ns3::ByteTagListDataFreeList g_freeList
Container for struct ByteTagListData.
void Deallocate(struct ByteTagListData *data)
Deallocates a ByteTagListData.
uint8_t * m_current
Current tag.
#define FREE_LIST_SIZE
int32_t m_offsetEnd
Offset to the end of the tag from the virtual byte buffer.
void AddAtEnd(int32_t appendOffset)
Make sure that all offsets are smaller than appendOffset which represents the location where new byte...
void PrepareForNext(void)
Prepare the iterator for the next tag.
void RemoveAll(void)
Removes all of the tags from the ByteTagList.
#define max(a, b)
Definition: 80211b.c:43
ByteTagList::Iterator Begin(int32_t offsetStart, int32_t offsetEnd) const
Internal representation of the byte tags stored in a packet.
uint32_t m_nextSize
Size of the next tag.
uint8_t data[writeSize]
TAG_BUFFER_INLINE void WriteU32(uint32_t v)
Definition: tag-buffer.h:186
#define OFFSET_MAX
int32_t start
offset to the start of the tag from the virtual byte buffer
Definition: byte-tag-list.h:85
struct ByteTagList::Iterator::Item Next(void)
Returns the next Item from the ByteTagList.
#define list
uint16_t GetUid(void) const
Get the internal id of this TypeId.
Definition: type-id.cc:1185
struct ByteTagListData * Allocate(uint32_t size)
Allocate the memory for the ByteTagListData.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Iterator(uint8_t *start, uint8_t *end, int32_t offsetStart, int32_t offsetEnd, int32_t adjustment)
Constructor.
int32_t m_minStart
minimal start offset
int32_t m_nextStart
Start of the next tag.
int32_t end
offset to the end of the tag from the virtual byte buffer
Definition: byte-tag-list.h:86
ByteTagList::Iterator BeginAll(void) const
Returns an iterator pointing to the very first tag in this list.
uint32_t m_used
the number of used bytes in the buffer
int32_t m_offsetStart
Offset to the start of the tag from the virtual byte buffer.
Container class for struct ByteTagListData.
TypeId tid
type of the tag
Definition: byte-tag-list.h:83
uint32_t size
size of tag data
Definition: byte-tag-list.h:84
uint32_t size
size of the data
void SetUid(uint16_t uid)
Set the internal id of this TypeId.
Definition: type-id.cc:1191
int32_t m_adjustment
adjustment to byte tag offsets
TagBuffer buf
the data for the tag as generated by Tag::Serialize
Definition: byte-tag-list.h:87
An iterator for iterating through a byte tag list.
Definition: byte-tag-list.h:72
read and write tag data
Definition: tag-buffer.h:51
int32_t m_nextEnd
End of the next tag.
void AddAtStart(int32_t prependOffset)
Make sure that all offsets are bigger than prependOffset which represents the location where new byte...
int32_t m_maxEnd
maximal end offset
void Read(uint8_t *buffer, uint32_t size)
Definition: tag-buffer.cc:176
Item(TagBuffer buf)
Constructs an item with the given TagBuffer.
uint32_t GetOffsetStart(void) const
Returns the offset from the start of the virtual byte buffer to the ByteTagList.
uint32_t Serialize(uint32_t *buffer, uint32_t maxSize) const
Serialize the tag list into a byte buffer.
uint8_t data[4]
data
static uint32_t g_maxSize
maximum data size (used for allocation)
a unique identifier for an interface.
Definition: type-id.h:58
int32_t m_adjustment
Adjustment to byte tag offsets.
void CopyFrom(TagBuffer o)
Copy the nternal structure of another TagBuffer.
Definition: tag-buffer.cc:199
bool HasNext(void) const
Used to determine if the iterator is at the end of the byteTagList.
uint8_t * m_end
End tag.
An item specifies an individual tag within a byte buffer.
Definition: byte-tag-list.h:81