A Discrete-Event Network Simulator
API
packet-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) 2006 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 
26 #include "packet-tag-list.h"
27 #include "tag-buffer.h"
28 #include "tag.h"
29 #include "ns3/fatal-error.h"
30 #include "ns3/log.h"
31 #include <cstring>
32 
33 namespace ns3 {
34 
35 NS_LOG_COMPONENT_DEFINE ("PacketTagList");
36 
37 PacketTagList::TagData *
39 {
40  NS_ASSERT_MSG (dataSize
41  < std::numeric_limits<decltype(TagData::size)>::max (),
42  "Requested TagData size " << dataSize
43  << " exceeds maximum "
44  << std::numeric_limits<decltype(TagData::size)>::max () );
45 
46  void * p = std::malloc (sizeof (TagData) + dataSize - 1);
47  // The matching frees are in RemoveAll and RemoveWriter
48 
49  TagData * tag = new (p) TagData;
50  tag->size = dataSize;
51  return tag;
52 }
53 
54 bool
56 {
57  TypeId tid = tag.GetInstanceTypeId ();
58  NS_LOG_FUNCTION (this << tid);
59  NS_LOG_INFO ("looking for " << tid);
60 
61  // trivial case when list is empty
62  if (m_next == 0)
63  {
64  return false;
65  }
66 
67  bool found = false;
68 
69  struct TagData ** prevNext = &m_next; // previous node's next pointer
70  struct TagData * cur = m_next; // cursor to current node
71  struct TagData * it = 0; // utility
72 
73  // Search from the head of the list until we find tid or a merge
74  while (cur != 0)
75  {
76  if (cur->count > 1)
77  {
78  // found merge
79  NS_LOG_INFO ("found initial merge before tid");
80  break;
81  }
82  else if (cur->tid == tid)
83  {
84  NS_LOG_INFO ("found tid before initial merge, calling writer");
85  found = (this->*Writer)(tag, true, cur, prevNext);
86  break;
87  }
88  else
89  {
90  // no merge or tid found yet, move on
91  prevNext = &cur->next;
92  cur = cur->next;
93  }
94  } // while !found && !cow
95 
96  // did we find it or run out of tags?
97  if (cur == 0 || found)
98  {
99  NS_LOG_INFO ("returning after header with found: " << found);
100  return found;
101  }
102 
103  // From here on out, we have to copy the list
104  // until we find tid, then link past it
105 
106  // Before we do all that work, let's make sure tid really exists
107  for (it = cur; it != 0; it = it->next)
108  {
109  if (it->tid == tid)
110  {
111  break;
112  }
113  }
114  if (it == 0)
115  {
116  // got to end of list without finding tid
117  NS_LOG_INFO ("tid not found after first merge");
118  return found;
119  }
120 
121  // At this point cur is a merge, but untested for tid
122  NS_ASSERT (cur != 0);
123  NS_ASSERT (cur->count > 1);
124 
125  /*
126  Walk the remainder of the list, copying, until we find tid
127  As we put a copy of the cur node onto our list,
128  we move the merge point down the list.
129 
130  Starting position End position
131  T1 is a merge T1.count decremented
132  T2 is a merge
133  T1' is a copy of T1
134 
135  other other
136  \ \
137  Prev -> T1 -> T2 -> ... T1 -> T2 -> ...
138  / / /|
139  pNext cur Prev -> T1' --/ |
140  / |
141  pNext cur
142 
143  When we reach tid, we link past it, decrement count, and we're done.
144  */
145 
146  // Should normally check for null cur pointer,
147  // but since we know tid exists, we'll skip this test
148  while ( /* cur && */ cur->tid != tid)
149  {
150  NS_ASSERT (cur != 0);
151  NS_ASSERT (cur->count > 1);
152  cur->count--; // unmerge cur
153  struct TagData * copy = CreateTagData (cur->size);
154  copy->tid = cur->tid;
155  copy->count = 1;
156  copy->size = cur->size;
157  memcpy (copy->data, cur->data, copy->size);
158  copy->next = cur->next; // merge into tail
159  copy->next->count++; // mark new merge
160  *prevNext = copy; // point prior list at copy
161  prevNext = &copy->next; // advance
162  cur = copy->next;
163  }
164  // Sanity check:
165  NS_ASSERT (cur != 0); // cur should be non-zero
166  NS_ASSERT (cur->tid == tid); // cur->tid should be tid
167  NS_ASSERT (cur->count > 1); // cur should be a merge
168 
169  // link around tid, removing it from our list
170  found = (this->*Writer)(tag, false, cur, prevNext);
171  return found;
172 
173 }
174 
175 bool
177 {
179 }
180 
181 // COWWriter implementing Remove
182 bool
183 PacketTagList::RemoveWriter (Tag & tag, bool preMerge,
184  struct PacketTagList::TagData * cur,
185  struct PacketTagList::TagData ** prevNext)
186 {
188 
189  // found tid
190  bool found = true;
191  tag.Deserialize (TagBuffer (cur->data, cur->data + cur->size));
192  *prevNext = cur->next; // link around cur
193 
194  if (preMerge)
195  {
196  // found tid before first merge, so delete cur
197  cur->~TagData ();
198  std::free (cur);
199  }
200  else
201  {
202  // cur is always a merge at this point
203  // unmerge cur, since we linked around it already
204  cur->count--;
205  if (cur->next != 0)
206  {
207  // there's a next, so make it a merge
208  cur->next->count++;
209  }
210  }
211  return found;
212 }
213 
214 bool
216 {
217  bool found = COWTraverse (tag, &PacketTagList::ReplaceWriter);
218  if (!found)
219  {
220  Add (tag);
221  }
222  return found;
223 }
224 
225 // COWWriter implementing Replace
226 bool
227 PacketTagList::ReplaceWriter (Tag & tag, bool preMerge,
228  struct PacketTagList::TagData * cur,
229  struct PacketTagList::TagData ** prevNext)
230 {
232 
233  // found tid
234  bool found = true;
235  if (preMerge)
236  {
237  // found tid before first merge, so just rewrite
238  tag.Serialize (TagBuffer (cur->data, cur->data + cur->size));
239  }
240  else
241  {
242  // cur is always a merge at this point
243  // need to copy, replace, and link past cur
244  cur->count--; // unmerge cur
245  struct TagData * copy = CreateTagData (tag.GetSerializedSize ());
246  copy->tid = tag.GetInstanceTypeId ();
247  copy->count = 1;
248  tag.Serialize (TagBuffer (copy->data, copy->data + copy->size));
249  copy->next = cur->next; // merge into tail
250  if (copy->next != 0)
251  {
252  copy->next->count++; // mark new merge
253  }
254  *prevNext = copy; // point prior list at copy
255  }
256  return found;
257 }
258 
259 void
260 PacketTagList::Add (const Tag &tag) const
261 {
262  NS_LOG_FUNCTION (this << tag.GetInstanceTypeId ());
263  // ensure this id was not yet added
264  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
265  {
266  NS_ASSERT_MSG (cur->tid != tag.GetInstanceTypeId (),
267  "Error: cannot add the same kind of tag twice.");
268  }
269  struct TagData * head = CreateTagData (tag.GetSerializedSize ());
270  head->count = 1;
271  head->next = 0;
272  head->tid = tag.GetInstanceTypeId ();
273  head->next = m_next;
274  tag.Serialize (TagBuffer (head->data, head->data + head->size));
275 
276  const_cast<PacketTagList *> (this)->m_next = head;
277 }
278 
279 bool
281 {
282  NS_LOG_FUNCTION (this << tag.GetInstanceTypeId ());
283  TypeId tid = tag.GetInstanceTypeId ();
284  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
285  {
286  if (cur->tid == tid)
287  {
288  /* found tag */
289  tag.Deserialize (TagBuffer (cur->data, cur->data + cur->size));
290  return true;
291  }
292  }
293  /* no tag found */
294  return false;
295 }
296 
297 const struct PacketTagList::TagData *
299 {
300  return m_next;
301 }
302 
303 uint32_t
305 {
307 
308  uint32_t size = 0;
309 
310  size = 4; // numberOfTags
311 
312  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
313  {
314  size += 4; // TagData -> size
315 
316  // TypeId hash; ensure size is multiple of 4 bytes
317  uint32_t hashSize = (sizeof (TypeId::hash_t)+3) & (~3);
318  size += hashSize;
319 
320  // TagData -> data; ensure size is multiple of 4 bytes
321  uint32_t tagWordSize = (cur->size+3) & (~3);
322  size += tagWordSize;
323  }
324 
325  return size;
326 }
327 
328 uint32_t
329 PacketTagList::Serialize (uint32_t* buffer, uint32_t maxSize) const
330 {
331  NS_LOG_FUNCTION (this << buffer << maxSize);
332 
333  uint32_t* p = buffer;
334  uint32_t size = 0;
335 
336  uint32_t* numberOfTags = 0;
337 
338  if (size + 4 <= maxSize)
339  {
340  numberOfTags = p;
341  *p++ = 0;
342  size += 4;
343  }
344  else
345  {
346  return 0;
347  }
348 
349  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
350  {
351  if (size + 4 <= maxSize)
352  {
353  *p++ = cur->size;
354  size += 4;
355  }
356  else
357  {
358  return 0;
359  }
360 
361  NS_LOG_INFO("Serializing tag id " << cur->tid);
362 
363  // ensure size is multiple of 4 bytes for 4 byte boundaries
364  uint32_t hashSize = (sizeof (TypeId::hash_t)+3) & (~3);
365  if (size + hashSize <= maxSize)
366  {
367  TypeId::hash_t tid = cur->tid.GetHash ();
368  memcpy (p, &tid, sizeof (TypeId::hash_t));
369  p += hashSize / 4;
370  size += hashSize;
371  }
372  else
373  {
374  return 0;
375  }
376 
377  // ensure size is multiple of 4 bytes for 4 byte boundaries
378  uint32_t tagWordSize = (cur->size+3) & (~3);
379  if (size + tagWordSize <= maxSize)
380  {
381  memcpy (p, cur->data, cur->size);
382  size += tagWordSize;
383  p += tagWordSize / 4;
384  }
385  else
386  {
387  return 0;
388  }
389 
390  (*numberOfTags)++;
391  }
392 
393  // Serialized successfully
394  return 1;
395 }
396 
397 uint32_t
398 PacketTagList::Deserialize (const uint32_t* buffer, uint32_t size)
399 {
400  NS_LOG_FUNCTION (this << buffer << size);
401  const uint32_t* p = buffer;
402  uint32_t sizeCheck = size - 4;
403 
404  NS_ASSERT (sizeCheck >= 4);
405  uint32_t numberOfTags = *p++;
406  sizeCheck -= 4;
407 
408  NS_LOG_INFO("Deserializing number of tags " << numberOfTags);
409 
410  struct TagData * prevTag = 0;
411  for (uint32_t i = 0; i < numberOfTags; ++i)
412  {
413  NS_ASSERT (sizeCheck >= 4);
414  uint32_t tagSize = *p++;
415  sizeCheck -= 4;
416 
417  uint32_t hashSize = (sizeof (TypeId::hash_t)+3) & (~3);
418  NS_ASSERT (sizeCheck >= hashSize);
420  memcpy (&hash, p, sizeof (TypeId::hash_t));
421  p += hashSize / 4;
422  sizeCheck -= hashSize;
423 
425 
426  NS_LOG_INFO ("Deserializing tag of type " << tid);
427 
428  struct TagData * newTag = CreateTagData (tagSize);
429  newTag->count = 1;
430  newTag->next = 0;
431  newTag->tid = tid;
432 
433  NS_ASSERT (sizeCheck >= tagSize);
434  memcpy (newTag->data, p, tagSize);
435 
436  // ensure 4 byte boundary
437  uint32_t tagWordSize = (tagSize+3) & (~3);
438  p += tagWordSize / 4;
439  sizeCheck -= tagWordSize;
440 
441  // Set link list pointers.
442  if (i==0)
443  {
444  m_next = newTag;
445  }
446  else
447  {
448  prevTag->next = newTag;
449  }
450 
451  prevTag = newTag;
452  }
453 
454  NS_ASSERT (sizeCheck == 0);
455 
456  // return zero if buffer did not
457  // contain a complete message
458  return (sizeCheck != 0) ? 0 : 1;
459 }
460 
461 
462 } /* namespace ns3 */
463 
ns3::TypeId
a unique identifier for an interface.
Definition: type-id.h:59
NS_LOG_COMPONENT_DEFINE
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
NS_ASSERT
#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
ns3::PacketTagList::Deserialize
uint32_t Deserialize(const uint32_t *buffer, uint32_t size)
Deserialize tag list from the provided buffer.
Definition: packet-tag-list.cc:398
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::PacketTagList::TagData::data
uint8_t data[1]
Serialization buffer.
Definition: packet-tag-list.h:147
ns3::PacketTagList::TagData
Tree node for sharing serialized tags.
Definition: packet-tag-list.h:142
ns3::ObjectBase::GetInstanceTypeId
virtual TypeId GetInstanceTypeId(void) const =0
Get the most derived TypeId for this Object.
ns3::PacketTagList::Peek
bool Peek(Tag &tag) const
Find a tag and return its value.
Definition: packet-tag-list.cc:280
ns3::PacketTagList::COWWriter
bool(PacketTagList::* COWWriter)(Tag &tag, bool preMerge, struct TagData *cur, struct TagData **prevNext)
Typedef of method function pointer for copy-on-write operations.
Definition: packet-tag-list.h:268
tag-buffer.h
ns3::TypeId::LookupByHash
static TypeId LookupByHash(hash_t hash)
Get a TypeId by hash.
Definition: type-id.cc:850
ns3::PacketTagList::TagData::tid
TypeId tid
Type of the tag serialized into data.
Definition: packet-tag-list.h:145
ns3::Tag
tag a set of bytes in a packet
Definition: tag.h:37
NS_LOG_INFO
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
ns3::PacketTagList::ReplaceWriter
bool ReplaceWriter(Tag &tag, bool preMerge, struct TagData *cur, struct TagData **prevNext)
Copy-on-write implementing Replace.
Definition: packet-tag-list.cc:227
ns3::PacketTagList::Add
void Add(Tag const &tag) const
Add a tag to the head of this branch.
Definition: packet-tag-list.cc:260
ns3::PacketTagList::TagData::next
struct TagData * next
Pointer to next in list.
Definition: packet-tag-list.h:143
NS_ASSERT_MSG
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition: assert.h:88
ns3::PacketTagList::CreateTagData
static TagData * CreateTagData(size_t dataSize)
Allocate and construct a TagData struct, sizing the data area large enough to serialize dataSize byte...
Definition: packet-tag-list.cc:38
ns3::TypeId::hash_t
uint32_t hash_t
Type of hash values.
Definition: type-id.h:116
hash
int32_t hash
Definition: fq-codel-queue-disc-test-suite.cc:41
ns3::Tag::GetSerializedSize
virtual uint32_t GetSerializedSize(void) const =0
NS_LOG_FUNCTION_NOARGS
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
Definition: log-macros-enabled.h:209
ns3::PacketTagList::Replace
bool Replace(Tag &tag)
Replace the value of a tag.
Definition: packet-tag-list.cc:215
ns3::PacketTagList::COWTraverse
bool COWTraverse(Tag &tag, PacketTagList::COWWriter Writer)
Traverse the list implementing copy-on-write, using Writer.
Definition: packet-tag-list.cc:55
NS_LOG_FUNCTION
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Definition: log-macros-enabled.h:244
ns3::PacketTagList::TagData::size
uint32_t size
Size of the data buffer.
Definition: packet-tag-list.h:146
ns3::PacketTagList::Remove
bool Remove(Tag &tag)
Remove (the first instance of) tag from the list.
Definition: packet-tag-list.cc:176
tag.h
ns3::PacketTagList::m_next
struct TagData * m_next
Pointer to first TagData on the list.
Definition: packet-tag-list.h:308
ns3::PacketTagList::TagData::count
uint32_t count
Number of incoming links.
Definition: packet-tag-list.h:144
ns3::PacketTagList::Serialize
uint32_t Serialize(uint32_t *buffer, uint32_t maxSize) const
Serialize the tag list into a byte buffer.
Definition: packet-tag-list.cc:329
ns3::max
double max(double x, double y)
Definition: cobalt-queue-disc.cc:137
ns3::Tag::Deserialize
virtual void Deserialize(TagBuffer i)=0
packet-tag-list.h
Defines a linked list of Packet tags, including copy-on-write semantics.
ns3::Tag::Serialize
virtual void Serialize(TagBuffer i) const =0
ns3::PacketTagList
List of the packet tags stored in a packet.
Definition: packet-tag-list.h:124
ns3::TagBuffer
read and write tag data
Definition: tag-buffer.h:52
ns3::PacketTagList::GetSerializedSize
uint32_t GetSerializedSize(void) const
Returns number of bytes required for packet serialization.
Definition: packet-tag-list.cc:304
ns3::PacketTagList::RemoveWriter
bool RemoveWriter(Tag &tag, bool preMerge, struct TagData *cur, struct TagData **prevNext)
Copy-on-write implementing Remove.
Definition: packet-tag-list.cc:183
ns3::PacketTagList::Head
const struct PacketTagList::TagData * Head(void) const
Definition: packet-tag-list.cc:298