Tom, this is code you added about 4 months ago, could you please have a look whether trace or code are fine?

(In reply to sebastien.deronne from comment #1)
> Tom, this is code you added about 4 months ago, could you please have a look
> whether trace or code are fine?

I can't remember why that is encoded as Peek(); I changed to Dequeue(), tested it, and the change passes regression tests.  Probably was a mistake on my part.

It feels a bit wrong to dequeue packets out of WifiMacQueue without any logging or hitting of drop traces, but I notice that WifiMacQueue::Cleanup() also does such silent removal of packets.

I have noticed when profiling wifi code that WifiMacQueue::Cleanup() is often near the top of the list, as it is called often and iterates the queue each time.  It might be a better design to avoid Cleanup() by using other techniques (queue sorted also by timestamp, or timeout on oldest packet in queue...), plus logging any drops.  I don't know whether Stefano is doing any rework of this class as part of traffic control integration?

(In reply to Tom Henderson from comment #2)
> It feels a bit wrong to dequeue packets out of WifiMacQueue without any
> logging or hitting of drop traces, but I notice that WifiMacQueue::Cleanup()
> also does such silent removal of packets.
> 
> I have noticed when profiling wifi code that WifiMacQueue::Cleanup() is
> often near the top of the list, as it is called often and iterates the queue
> each time.  It might be a better design to avoid Cleanup() by using other
> techniques (queue sorted also by timestamp, or timeout on oldest packet in
> queue...), plus logging any drops.  I don't know whether Stefano is doing
> any rework of this class as part of traffic control integration?

Yes, I just finished the work to make WifiMacQueue a subclass of Queue<WifiMacQueueItem>:

https://github.com/stavallo/ns-3-dev-git/commits/tc-next

The code compiles and all the tests pass. I want to polish some bits and add flow control support (should be really easy now) before publishing the code reviews (and updating the previous ones).

Being a subclass of Queue, WifiMacQueue gains the ability to trace enqueues, dequeues, and drops. I already added some logging to the WifiMacQueue methods, but plan to add more. Regarding the Cleanup() method, I removed it by adopting the following strategy. Keep in mind that packets are timestamped when inserted in the queue, so packets are already sorted by increasing timestamp (from head to tail). When a dequeue or peek operation is requested, packets are processed one-by-one (starting from the head of the queue) until a packet is found that satisfies the requested conditions (e.g., tid and address) and whose time-to-live is not expired yet. Processed packets whose time-to-live is expired are clearly dropped. Given that packets are sorted by increasing timestamp and the time-to-live of the returned packet (if any) is not expired, we manage to remove all the expired packets from the queue. This comes at no additional cost (we necessarily have to walk the list until we find the packet to be returned).

At the moment I do not perform any "cleaning" when packets are enqueued. Perhaps I can walk the list until a packet with an unexpired timer is found.

Any comment/feedback is clearly much appreciated.

Is this not fixed by bug 2633?

(In reply to sebastien.deronne from comment #4)
> Is this not fixed by bug 2633?

Nope, I just adapted the call to the Peek method, but the mismatch remains.

If you tell me that I have to drop the packet at the head of the queue (to match the comment), I can fix it as part of the queue rework.

(In reply to Stefano Avallone from comment #5)
> (In reply to sebastien.deronne from comment #4)
> > Is this not fixed by bug 2633?
> 
> Nope, I just adapted the call to the Peek method, but the mismatch remains.
> 
> If you tell me that I have to drop the packet at the head of the queue (to
> match the comment), I can fix it as part of the queue rework.

I guess Tom knows better what he expected there.
Then fine for me you deliver this together with your changes.

I guess this is a quite obvious one.
Could we come to a conclusion?
Thanks.

(In reply to sebastien.deronne from comment #7)
> I guess this is a quite obvious one.
> Could we come to a conclusion?
> Thanks.

I would suggest what I mentioned above in comment 2:
- change Peek to Dequeue
- make sure the drop is traced

(In reply to Tom Henderson from comment #8)
> (In reply to sebastien.deronne from comment #7)
> > I guess this is a quite obvious one.
> > Could we come to a conclusion?
> > Thanks.
> 
> I would suggest what I mentioned above in comment 2:
> - change Peek to Dequeue

Ok

> - make sure the drop is traced

It seems handled in the Queue class now. Stefano, could you confirm?

Moving Peek to Dequeue introduces some regression:

List of FAILed tests:
    devices-mesh-dot11s-regression
List of CRASHed tests:
    examples/wireless/wifi-multi-tos --simulationTime=1 --nWifi=16 --useRts=1 --useShortGuardInterval=1

I'll look into this later today.

(In reply to sebastien.deronne from comment #10)
> Moving Peek to Dequeue introduces some regression:
> 
> List of FAILed tests:
>     devices-mesh-dot11s-regression
> List of CRASHed tests:
>     examples/wireless/wifi-multi-tos --simulationTime=1 --nWifi=16
> --useRts=1 --useShortGuardInterval=1


I could not reproduce the above failures/crashes with the following patch on a Fedora 22 machine; everything passes for me.

diff -r f7bb8db1e6c8 src/wifi/model/edca-txop-n.cc
--- a/src/wifi/model/edca-txop-n.cc	Thu Mar 16 08:29:31 2017 -0700
+++ b/src/wifi/model/edca-txop-n.cc	Sat Mar 18 14:33:37 2017 -0700
@@ -416,12 +416,7 @@
           else
             {
               NS_LOG_DEBUG ("Dequeueing and discarding head of queue");
-              Ptr<const WifiMacQueueItem> item = m_queue->Peek ();
-              if (item)
-                {
-                  packet = item->GetPacket ();
-                  header = item->GetHeader ();
-                }
+              m_queue->Dequeue ();
             }
           m_dcf->ResetCw ();
         }

Created attachment 2805 [details]
Proposed patch

Since the packet is actually discarded, Remove should be used instead of Dequeue, so that the drop trace is fired. The attached patch also changes the implementation of the Remove method. Currently (as it was with the old Cleanup method), all the packets (starting from the head of the queue) that spent too much time in the queue are discarded, and the first packet with an unexpired timer is discarded and returned. I think this is not the intended (and advertised) behavior of Remove, which should remove the packet at the front of the queue. With the attached patch, Remove first discards the packet at the front of the queue (this packet will be returned) and then discards all the packets with an expired timer.

All the tests and examples pass with this patch applied on Mac OSX.

I am fine with the patch of Stefano.

I just suggest to add a small comment explaining what the for loop is doing, without looking at TtlExceeded some people might be wondering why this is there :-)

If Tom also agrees, then I think we can close this bug.

> Proposed patch
> 
> Since the packet is actually discarded, Remove should be used instead of
> Dequeue, so that the drop trace is fired. 

I am OK with that change; I see that Remove() was recently introduced.

> The attached patch also changes
> the implementation of the Remove method. Currently (as it was with the old
> Cleanup method), all the packets (starting from the head of the queue) that
> spent too much time in the queue are discarded, and the first packet with an
> unexpired timer is discarded and returned. I think this is not the intended
> (and advertised) behavior of Remove, which should remove the packet at the
> front of the queue. With the attached patch, Remove first discards the
> packet at the front of the queue (this packet will be returned) and then
> discards all the packets with an expired timer.
> 
> All the tests and examples pass with this patch applied on Mac OSX.

I'm skeptical of this second part.  Isn't the fact that some stale items are in queue an implementation detail hidden from users?  With your patch, couldn't Remove() return a stale item that logically shouldn't be in there?

Also, if Remove () is simply returning Head(), why does the cleanup need to be performed?  Won't some other queue operation perform cleanup when needed?

Finally, this kind of statement (semicolon without braces) is against the coding style; I'd instead put within braces with a LOG_DEBUG statement:

  for (auto it = Head (); it != Tail () && TtlExceeded (it); );

> > Since the packet is actually discarded, Remove should be used instead of
> > Dequeue, so that the drop trace is fired. 
> 
> I am OK with that change; I see that Remove() was recently introduced.

Yes, WifiMacQueue now inherits from Queue, hence it needs (see later, anyway) to implement the Remove() method.
 
> > The attached patch also changes
> > the implementation of the Remove method. Currently (as it was with the old
> > Cleanup method), all the packets (starting from the head of the queue) that
> > spent too much time in the queue are discarded, and the first packet with an
> > unexpired timer is discarded and returned. I think this is not the intended
> > (and advertised) behavior of Remove, which should remove the packet at the
> > front of the queue. With the attached patch, Remove first discards the
> > packet at the front of the queue (this packet will be returned) and then
> > discards all the packets with an expired timer.
> 
> I'm skeptical of this second part.  Isn't the fact that some stale items are
> in queue an implementation detail hidden from users?  With your patch,
> couldn't Remove() return a stale item that logically shouldn't be in there?
> 
> Also, if Remove () is simply returning Head(), why does the cleanup need to
> be performed?  Won't some other queue operation perform cleanup when needed?

You are correct. The thing is that the behavior of Remove() isn't well defined because of the cleanup operation. I thought that we might get rid of the Remove() method (i.e., raise a fatal error if it is called) so that we return to the previous interface where only Remove (Ptr<const Packet>) was present. The patch for this bug would become:

Ptr<const WifiMacQueueItem> item = m_queue->Peek ();
m_queue->Remove (item->GetPacket ());

If you agree on this approach, I can prepare a new patch.
Also, I noticed that I should modify the Peek() method to discard stale packets before returning a packet (currently, a stale packet could be returned), so as to make it consistent with the other Peek methods.

> Finally, this kind of statement (semicolon without braces) is against the
> coding style; I'd instead put within braces with a LOG_DEBUG statement:
> 
>   for (auto it = Head (); it != Tail () && TtlExceeded (it); );

Sorry, I didn't know.

Created attachment 2831 [details]
Proposed patch v2

I ended up with a new patch that only consists of the first part of the previous patch (i.e., Peek () is replaced by Remove ()). Thus:

- Remove () first discards the stale items and then removes the element at the head of the queue. In this way, the fact that some stale items are in queue is hidden from users

- I couldn't modify Peek () so that it removes stale items because Peek () is a const method (it is defined this way in the base class), hence the TtlExceeded() method cannot  be called

Tom, do you agree with this last solution?

(In reply to sebastien.deronne from comment #18)
> Tom, do you agree with this last solution?


I agree with the latest patch.

However, regarding Stefano's second comment about Peek (), I am concerned that Peek () presently can return a stale item.  This is probably a separate issue to resolve.

(In reply to Tom Henderson from comment #19)
> (In reply to sebastien.deronne from comment #18)
> > Tom, do you agree with this last solution?
> 
> 
> I agree with the latest patch.
> 
> However, regarding Stefano's second comment about Peek (), I am concerned
> that Peek () presently can return a stale item.  This is probably a separate
> issue to resolve.

I thought that we could prevent the usage of the Peek() method by raising a 
fatal error and provide a (non-const) PeekFront() method as a replacement. The Peek() method is just used twice (one of which should be removed by the patch proposed for this bug) in edca-txop-n.cc.

I prepared the following patch and verified that all the tests pass:

*diff --git a/src/wifi/model/edca-txop-n.cc b/src/wifi/model/edca-txop-n.cc* 
*index 6c7dd1c6c..31cb07c11 100644* 
*--- a/src/wifi/model/edca-txop-n.cc* 
*+++ b/src/wifi/model/edca-txop-n.cc* 
@@ -357,7 +357,7 @@ void EdcaTxopN::NotifyInternalCollision (void) 
-          Ptr<const WifiMacQueueItem> item = m_queue->Peek (); 
+          Ptr<const WifiMacQueueItem> item = m_queue->PeekFront (); 
@@ -416,7 +416,7 @@ void EdcaTxopN::NotifyInternalCollision (void) 
-              Ptr<const WifiMacQueueItem> item = m_queue->Peek (); 
+              Ptr<const WifiMacQueueItem> item = m_queue->PeekFront (); 
*diff --git a/src/wifi/model/wifi-mac-queue.cc b/src/wifi/model/wifi-mac-queue.cc* 
*index 9d5f68e10..997729ce4 100644* 
*--- a/src/wifi/model/wifi-mac-queue.cc* 
*+++ b/src/wifi/model/wifi-mac-queue.cc* 
@@ -273,8 +273,24 @@ template<> 
+  NS_FATAL_ERROR ("Do not use the Peek method. Use the PeekFront method instead"); 
+} 
+ 
+template<> 
+Ptr<const WifiMacQueueItem> 
+WifiMacQueue::PeekFront (void) 
+{ 
-  return DoPeek (Head ()); 
+ 
+  for (auto it = Head (); it != Tail (); ) 
+    { 
+      if (!TtlExceeded (it)) 
+        { 
+          return DoPeek (it); 
+        } 
+    } 
+  NS_LOG_DEBUG ("The queue is empty"); 
+  return 0; 
*diff --git a/src/wifi/model/wifi-mac-queue.h b/src/wifi/model/wifi-mac-queue.h* 
*index 3fbf8d27e..a63f4aa24 100644* 
*--- a/src/wifi/model/wifi-mac-queue.h* 
*+++ b/src/wifi/model/wifi-mac-queue.h* 
@@ -226,12 +226,20 @@ public: 
-   * Peek the packet in the front of the queue. The packet is not removed. 
+   * Do not use this method. To peek the packet in the front of the queue, 
+   * use the PeekFront method instead. 
+   * Peek the packet in the front of the queue. The packet is not removed. 
+   * Use this method instead of Peek. 
+   * 
+   * \return the packet 
+   */ 
+  Ptr<const Item> PeekFront (void); 
+  /** 

What do you think?

Created attachment 2839 [details]
Patch to solve the issue with Peek returning a stale item

Please find the patch of my previous comment as attachment.

(In reply to Stefano Avallone from comment #21)
> Created attachment 2839 [details]
> Patch to solve the issue with Peek returning a stale item
> 
> Please find the patch of my previous comment as attachment.

Why can't we make Peek () do the right thing instead?  Even if it is const it doesn't mean that it can't return a non-stale item.

Created attachment 2840 [details]
Patch to solve the issue with Peek returning a stale item v2

Correct! Sorry that I didn't think of it before. Find attached the updated patch, where Peek() simply skips the stale items.

Shall I push the two patches attached?

Thanks.

(In reply to Stefano Avallone from comment #24)
> Shall I push the two patches attached?
> 
> Thanks.

I agree.

Fixed with changeset 12857:d39b161e81d2