Created attachment 275 [details]
patch

This is the code I wrote today.  Possibly this could go into module core instead of contrib, but I don't really care as long as wifi, tcp, and olsr all converge to using it.

Conceptually, I am fine with the idea and would be happy to modify the wifi code to use this code. I would, however, be much happier if, instead of overloading c++ comparison operators, you could use explicit methods. I could live with your operators but the name of the class should not be abbreviated: SeqNum would be nicer as SequenceNumber.

The class name is abbreviated because there is already a SequenceNumber non-templated class, that is all.  The final patch would see TCP's SequenceNumber removed, and SeqNum renamed to SequenceNumber.

I don't understand the concern about C++ operators.  The TimeUnit class also uses C++ operators... prior art and all... :-)

(In reply to comment #3)

> I don't understand the concern about C++ operators.  The TimeUnit class also
> uses C++ operators... prior art and all... :-)

yes, but I always disliked it, especially after doing it myself there. Implementing correctly _all_ the c++ operators is very hard, impossible in a lot of cases, and, generally, a bad idea.

Sure but 1) you don't need to implement all operators, only the ones you want, and 2) not implementing operators usually just shifts more work onto the programmer.

(In reply to comment #5)
> Sure but 1) you don't need to implement all operators, only the ones you want,

No, you can't do this. Either you implement all operators or you don't. If you don't, strange and impossible-to-decipher error messages come up when you unknowingly try to use them (If you are lucky. If you are not, impossible-to-debug runtime errors happen). Remember about operator > for Ptr<>.

> and 2) not implementing operators usually just shifts more work onto the
> programmer.

I don't think so because spending hours to debug stupid c++ bugs is a _lot of work_.

I like the idea, agree with Mathieu about expanding the name of the class, and don't have a strong opinion about the operators.

Created attachment 669 [details]
yet another implementaiton of a sequence

I just stumbled over this having a similar problem. As I have already implemented my own version of a sequence number, I propose it here for review.

It seems to me that Gustavo's implementation is rather complex. I've tried to make mine as simple as possible and it should be usable like any other basic int type. I fully agree with Gustavo about the operators.

(In reply to comment #8)
> Created an attachment (id=669) [details]
> yet another implementaiton of a sequence
> 
> I just stumbled over this having a similar problem. As I have already
> implemented my own version of a sequence number, I propose it here for review.
> 
> It seems to me that Gustavo's implementation is rather complex. I've tried to
> make mine as simple as possible and it should be usable like any other basic
> int type. I fully agree with Gustavo about the operators.

I think my version is more complex mainly due to the way it handles operator-.  Your operator always returns another unsigned value, which is always positive even when the second operand is larger than the first, while I return a signed type that can be used to represent a negative difference.

The other simplification is in operator <=.  Your version is shorter and more efficient, but I think it a bit cryptic.  Or maybe it's just me...

If we're going to provide a sequence number class it should be easily traceable.  This is a real problem in some of our code.  If I remember correctly, our TCP implementation uses a sequence number class, but we just can't trace them.  This is one of the first things I think of tracing, but we can't do it.

It is easy to trace a number, but this overloads the same operators as a sequence number class would.  It would be wonderful to be able to:

  .AddTraceSource ("SequenceNumber",
                   "My sequence number to trace.",
                   MakeTraceSourceAccessor (&MyObject::m_sequence))

  ...

  TracedValue<uint32_t> m_sequence

It is very easy to trace an integer laying around, but much harder to wire tracing into a another class.

If we are goinig to do a sequence number, it should be easy to trace it.  I think this is where some real benefit would come from.

Unfortunately, off the top of my head, what seems to work best for tracing is not very elegant:

  static <T> Sequence::Set (T * sequence, T value);
  static <T> Sequence::Inc (T * sequence);
  static <T> Sequence::Inc (T * sequence, T count);
  static <T> Sequence::Dec (T * sequence);
  static <T> Sequence::Dec (T * sequence, T count);

You could then 

  .AddTraceSource ("Sequence",
                   "My sequence number to trace.",
                   MakeTraceSourceAccessor (&MyObject::m_sequence))

  ...

  TracedValue<uint32_t> m_sequence

  ... 

  Sequence::Set (m_sequence, 0);
  Sequence::Inc (m_sequence);
  Sequence::Inc (m_sequence);
  Sequence::Inc (m_sequence);
  etc.

For a user, tracing the sequence number would be trivial

  myObject->TraceConnectWithoutContext ("Sequence", MakeCallback(&SeqTrace));

but for a model author, it would be less than beautiful.

Any other bright ideas?

> For a user, tracing the sequence number would be trivial
> 
>   myObject->TraceConnectWithoutContext ("Sequence", MakeCallback(&SeqTrace));
> 
> but for a model author, it would be less than beautiful.
> 
> Any other bright ideas?

I vote for this type of solution because of the ease of tracing, as you explained.  I would much rather trace an int go through another level of indirection to trace.

> The other simplification is in operator <=.  Your version is shorter and more
> efficient, but I think it a bit cryptic.  Or maybe it's just me...
Yes, my operator <= is in deed a bit cryptic.

> while I return a signed
> type that can be used to represent a negative difference.
If I use a Sequence<uint8_t> I expect it to behave exactly like an uint8_t value (expect for the <, <=, >, >= operators), which is always positive. To get a negative result, you can either use a Sequence<int8_t> or cast the result to an int8_t.

> It is easy to trace a number, but this overloads the same operators as a
> sequence number class would.  It would be wonderful to be able to:
> 
>   .AddTraceSource ("SequenceNumber",
>                    "My sequence number to trace.",
>                    MakeTraceSourceAccessor (&MyObject::m_sequence))
> 
>   ...
> 
>   TracedValue<uint32_t> m_sequence
I'm not very used to traced values (I've never used them so far), but I tried the above with a TracedValue<Sequence<uint32_t> > and it seems to work. The only odd thing is that I can't directly assign an int value:

Sequence<uint32_t> a = 10; //works
Sequence<uint32_t> b = (Sequence<uint32_t>)10; //works, but not needed
TracedValue<Sequence<uint32_t> > c = 10 //doesn't work
TracedValue<Sequence<uint32_t> > d = (Sequence<uint32_t>)10; //works

Created attachment 683 [details]
yet another implementaiton of a sequence

I just realized that the operator+ and operator- are not needed. I also included some more unit tests.

I bumped the priority of this to P2 and cc'ed Josh because I would like to push for resolution of this issue so that we could actually trace TCP cwnd when ns-3.8 is released.  

Again, I favor a solution that makes it easy to trace these sequence numbers.

(In reply to comment #14)
> I bumped the priority of this to P2 and cc'ed Josh because I would like to push
> for resolution of this issue so that we could actually trace TCP cwnd when

oops, I meant TCP sequence numbers (not cwnd, which is already traced)

> ns-3.8 is released.  
> 
> Again, I favor a solution that makes it easy to trace these sequence numbers.

Created attachment 922 [details]
Easily traceable general sequence number

Craig is right that the sequence number should be easily traceable.  Given his suggestions and some of the code from the previous two patches, I created a new patch that (I think) is headed in the direction that Craig outlined.  If we decide to go this route, I would fill in the tests, rename to SequenceNumber, and replace sequence numbers in tcp code.

Now, given that, I'm not so sure this is a good way to do it, because:

1) Likely the most expected way to create a generic sequence number class is to do something like the previous two patches.  This way a sequence number is actually instantiated as a sequence number, and it can only be manipulated as a sequence number.  As mentioned above, this is not so good for tracing.

2) Related to above slightly, using the easily traceable method, a developer could manipulate sequence numbers mistakenly by using operators (>, >=, etc), rather than using SequenceNumber static methods.

I'm not that familiar with the design of TracedValue, but I think it would be nice if you could trace a custom class, like SequenceNumber, and just tie a private int to the TracedValue somehow.  This way, it's still easy for the end user to set up a trace, and the developer gets to use a generic sequence number as expected.

But, since I really have no suggestions for alternate solutions, I am ok with something like this, if we really want sequence number to be traceable.

(In reply to comment #16)
> Created an attachment (id=922) [details]
> Easily traceable general sequence number
> 
> Craig is right that the sequence number should be easily traceable.  Given his
> suggestions and some of the code from the previous two patches, I created a new
> patch that (I think) is headed in the direction that Craig outlined.  If we
> decide to go this route, I would fill in the tests, rename to SequenceNumber,
> and replace sequence numbers in tcp code.
> 
> Now, given that, I'm not so sure this is a good way to do it, because:
> 
> 1) Likely the most expected way to create a generic sequence number class is to
> do something like the previous two patches.  This way a sequence number is
> actually instantiated as a sequence number, and it can only be manipulated as a
> sequence number.  As mentioned above, this is not so good for tracing.
> 
> 2) Related to above slightly, using the easily traceable method, a developer
> could manipulate sequence numbers mistakenly by using operators (>, >=, etc),
> rather than using SequenceNumber static methods.

I don't know whether it is worth the trouble to try to prevent such errors.

I do have a comment about the scope of this.  These are the macros used in TCP:

#define SEQ_LT(a,b)     ((int)((a)-(b)) < 0)
#define SEQ_LEQ(a,b)    ((int)((a)-(b)) <= 0)
#define SEQ_GT(a,b)     ((int)((a)-(b)) > 0)
#define SEQ_GEQ(a,b)    ((int)((a)-(b)) >= 0)
#define SEQ_MIN(a, b)   ((SEQ_LT(a, b)) ? (a) : (b))
#define SEQ_MAX(a, b)   ((SEQ_GT(a, b)) ? (a) : (b))

Do we need more than these operators? 

What about providing the above macros too, for convenience?  

#define SEQ_LT(a,b)     SequenceNumber::IsLess (a,b)

I really really hate not having standard C++ operators for something that is practically     a plain number.  Making things more verbose does not always mean making them less error prone; certainly not in this case.  What makes things error prone is stuff like implicit conversion constructors and type casting operators (to allow implicit conversion to/from a plain number to a sequence number), but not arithmetic operators, IMHO.

(In reply to comment #18)
> I really really hate not having standard C++ operators for something that is
> practically     a plain number.  Making things more verbose does not always
> mean making them less error prone; certainly not in this case.  What makes
> things error prone is stuff like implicit conversion constructors and type
> casting operators (to allow implicit conversion to/from a plain number to a
> sequence number), but not arithmetic operators, IMHO.

Do you think you could take your original patch proposal and implement all standard operators and make it easy to turn into a TracedValue?  My suggestion to just implement the explicit comparison operators is mainly rooted in the assumption that we will not be able to easily trace sequence number evolution with a special class, and also because kernel code already uses a similar approach.

I would like to try to resolve the apparent deadlock here.  I perceive that I am just complicating things for Gustavo by insisting on easy tracing while he just wants a class with normal operators.

Not all sequence numbers need tracing, so one suggestion to move forward would be to support something like Gustavo's original proposal as the default SequenceNumber class, but for things where we want TracedValue support on them, separately provide explicit static methods such as the traditional SEQ_* macros.  

Comments on this possible way forward?

(In reply to comment #20)
> I would like to try to resolve the apparent deadlock here.  I perceive that I
> am just complicating things for Gustavo by insisting on easy tracing while he
> just wants a class with normal operators.
> 
> Not all sequence numbers need tracing, so one suggestion to move forward would
> be to support something like Gustavo's original proposal as the default
> SequenceNumber class, but for things where we want TracedValue support on them,
> separately provide explicit static methods such as the traditional SEQ_*
> macros.  
> 
> Comments on this possible way forward?

I have no idea how to make a class compatible with TracedValue.  But I am assuming implementing C++ operators or not is a completely orthogonal issue to making the class traceable.  If so, I do not see why we can't have both in the same class.  I just never found time to look into the tracing issue, and after Fabien's patch I wasn't sure which sequence number implementation you guys would prefer.  I'm ok with either implementation, but I am not convinced operators are bad.  Or else it's time to look for a new programming language, since C++ uses operators extensively...

(In reply to comment #21)

> I have no idea how to make a class compatible with TracedValue.  But I am
> assuming implementing C++ operators or not is a completely orthogonal issue to
> making the class traceable.  

I guess that the operator issue is somewhat related in the sense that if we just provide methods to manipulate unsigned integers, there is no need to create a separate SequenceNumber type and the issue goes away.

Ideally I would like something like your class but traceable in the way that Craig specified in his comment, but I don't know how easy that would be so I am guessing we are going to have to make choices about priorities.  

My sense is that, with the SequenceNumber class, we could have standard operators like you want and address Mathieu's concern about implementing all operators by declaring the unimplemented standard ones to be private, which I guess may have been your comment #5.

But in any case, it would be nice to try to resolve this now especially since we're considering a new TCP implementation now.

Created attachment 924 [details]
patch

Updated patch, with all non-implemented the C++ operators private (unless I missed some), unit tests including a tracing test case.

Is this what you want?  If so, next step I guess is rename SeqNum to SequenceNumber, and move it to core or common (which?)?

I'm trying to reconstruct what I was so concerned about last November, but I'm having trouble remembering it all.  I think it was something about objects that a particular class owns or has pointers to and, in turn, has values that we want to trace, as in:

  Protocol -> non-Object -> value1, value2

but that weren't designed to be traceable (didn't implement a slew of operators correctly).

I want to easily be able to trace value2, for example, without having to to large amounts of work to implement a bunch of operators and get access to it as an Object.  I'm having a hard time parsing what I wrote in the comment above, though :-)

In any case, I certainly don't want to block making a working, traceable, generic sequence class.

I want to point out how painful adding a traced value can be in conceptually simple situations can be.  We might consider another mechanism to make it easier to do in cases such as the current TCP sequence class.  IIRC it doesn't work with tracing at all.  We wave an underlying sequence "value" that does play by those rules,but we can't trace it without large amounts of rework.

Anyway, please do make a generic sequence number class that we can put in a "root" Object and trace.  Perhaps we should turn an agree-upon implementation into a design pattern showning what must be done.

Maybe there should be a separate feature request for a facility to trace objects that aren't designed to be traceable from the start; or cannot be easily stuffed into the "root" object.

(In reply to comment #24)
> Anyway, please do make a generic sequence number class that we can put in a
> "root" Object and trace.  Perhaps we should turn an agree-upon implementation
> into a design pattern showning what must be done.
> 
> Maybe there should be a separate feature request for a facility to trace
> objects that aren't designed to be traceable from the start; or cannot be
> easily stuffed into the "root" object.

Craig, the patch I uploaded adds a sequence number class that is traceable.  The code is simple:

+class SeqNumTestObj : public Object
+{
+  TracedValue<SeqNum32> m_testTracedSeqNum;
[...]
+  
+  static TypeId GetTypeId (void)
+  {
+    static TypeId tid = TypeId("ns3::SeqNumTestObj")
+      .SetParent<Object> ()
+      .AddTraceSource ("TestTracedSeqNum",
+                       "A traceable sequence number",
+                       MakeTraceSourceAccessor (&SeqNumTestObj::m_testTracedSeqNum))
+      .AddConstructor<SeqNumTestObj> ()
+      ;
+    return tid;
+  }
+  
+  void IncSeqNum ()
+  {
+    ++m_testTracedSeqNum;
+  }

I think this is as simple as anyone may wish.  The only change made is to wrap the value in a TracedValue<>, then it is traceable and behaves like a normal value.  I don't think you can reasonably expect something even easier to use than this.

If your problem is more generic, then I agree that you should open a new bug report.

To clarify, I looked into directly providing ConnectWithoutContext, Connect, DisconnectWithoutContext, Disconnect methods into the SeqNum<> class, to make it trace-able without wrapping it in TracedValue, but that would require adding a TracedCallback attribute, with consequent memory cost.  Since sometimes you may want to have internal sequence numbers, and not want to expose them as attributes, it seems bad to waste the extra memory when it may not be used.  It's probably better to just wrap in TracedValue when needed.

> It's probably better to just wrap in TracedValue when needed.

I agree with this.  When I say "easily traceable" what I mean is a sequence number class that works when used standalone in a model, and when I:

  .AddTraceSource ("SequenceNumber",
                   "My sequence number to trace.",
                   MakeTraceSourceAccessor (&MyObject::m_sequence))

  ...

  TracedValue<SequenceNumber> m_sequence;

it gets traced correctly and just works.

It seems to me that at least a couple of people have demonstrated classes that can work this way, and that's all I really want at the highest level.  Our protocol implementations should provide the trace hooks for important sequence numbers.

My other comments derive from the fact that I was appalled when writing a tracing tutorial how much work would've been required to backfit sequence number tracing into TCP.  It was a rather large project (still will be to convert to a new seq type).  I was looking for a way to enable tracing on something that was not explicitly written to support it, or to enable tracing without having to construct chains of Ptr<Object> which seems to confuse the heck out of our novice users.

In any case, I support adding Gustavo's class (without the Object overhead) and a trace test, and then actually using the class and exporting the trace hooks.

With Gustavo's patch, I assume an end-user won't be able to do something as simple as socket->TraceConnectWithoutContext ("Sequence", MakeCallback(&SeqTrace)).  Or can we just have a method in socket to return SequenceNumber object and connect that way?

(In reply to comment #28)
> With Gustavo's patch, I assume an end-user won't be able to do something as
> simple as socket->TraceConnectWithoutContext ("Sequence",
> MakeCallback(&SeqTrace)).  Or can we just have a method in socket to return
> SequenceNumber object and connect that way?

See line 177 of the patch.

Gustavo, this looks like it addresses the concerns.  Does anyone have any more to discuss or should we move towards merging it (possibly in src/common?) for the current release?

Created attachment 928 [details]
updated patch

Moved to src/common, rename from SeqNum* to SequenceNumber*, update code that was using the old sequence-number.h header to use the new class instead.  Also updated the wifi code to use SequenceNumber16 instead of MacRxMiddle::SequenceControlSmaller.

TODO: doxygen

comparing with ssh://code@code.nsnam.org/repos/ns-3-dev
searching for changes
changeset:   6434:ac8b4bf77e50
user:        Gustavo J. A. M. Carneiro  <gjc@inescporto.pt>
date:        Sun Jul 11 22:32:34 2010 +0100
summary:     Bug 385 - Add a generic "sequence number" class.