Bugzilla – Bug 2924
documentation about Peek/Dequeue usage
Last modified: 2018-06-07 18:02:41 UTC
In changeset 13361, traffic-control: Align the implementation of Peek methods to Linux, there was one new public method introduced to QueueDisc base class: Ptr<QueueDiscItem> DequeuePeeked (void); and one protected: Ptr<const QueueDiscItem> PeekDequeued (void); These are in parallel to Dequeue() and Peek(). Is it intended that DequeuePeeked() be public, or should it also be protected? It seems to me perhaps that DequeuePeeked() should also be protected, and clients advised to only call Dequeue and Peek, but perhaps there is a wrinkle to this (in which case, there should be some clearer guidelines for a queue disc user as to which method to use and when). Some documentation updates are needed on queue-disc.rst. I understand the idea of PeekDequeued (to resolve which packet will be dequeued in a multi-queue situation) but what will happen if PeekDequeued() is called but then later Dequeue() and not DequeuePeeked() is called? Also, what if the client does not want to actually dequeue the next packet, because the state of the queue will be different sometime later when Dequeue is called? I think that it probably should be clear in the documentation that there is a side effect of PeekDequeued() that it forces an immediate dequeue (but holds the packet).
Created attachment 3108 [details] Proposed patch PeekDequeued is a sort of default implementation for the peek method in Linux. Some qdiscs use it and some others don't. So, I thought that the virtual private DoPeek method could implement the PeekDequeued approach, which can be overridden by subclasses needing a different approach. In this way, we basically have one less method around (PeekDequeued). DequeuePeeked must be public because it needs to be called by a queue disc that queries another queue disc (e.g., a child queue disc) with Peek. I updated the documentation to make it clear that, if a queue disc queries another one with Peek, than it has to call DequeuePeeked instead of Dequeue.
Can we just have a public Peek() and public Dequeue() method and hide these details from the public API? I am not comfortable with relying on the user remembering to call DequeuePeeked() after Peek(); some other method may have previously called Peek() unbeknownst to the Dequeue() caller. I think that the default behavior should be that Peek() provides no guarantee on the next dequeued packet; it should provide a pointer to the object that would have been dequeued had Dequeue() instead been called. In most cases the eventual Dequeue() will in fact dequeue the same packet, but if some time passes, conditions may change. What do we lose with such an approach?
Created attachment 3109 [details] Proposed patch with only public Peek and Dequeue (In reply to Tom Henderson from comment #2) > Can we just have a public Peek() and public Dequeue() method and hide these > details from the public API? I am not comfortable with relying on the user > remembering to call DequeuePeeked() after Peek(); some other method may have > previously called Peek() unbeknownst to the Dequeue() caller. Yes, I also thought that Dequeue and DequeuePeeked can be merged. Dequeue can first check whether there is a peeked (requeued) packet; if not, the private DoDequeue method is called. I attached a new version of the patch following this approach. > I think that the default behavior should be that Peek() provides no > guarantee on the next dequeued packet; it should provide a pointer to the > object that would have been dequeued had Dequeue() instead been called. In > most cases the eventual Dequeue() will in fact dequeue the same packet, but > if some time passes, conditions may change. > > What do we lose with such an approach? Well, the thing is that a few qdiscs rely on the assumption that the peeked packet is exactly the next packet that will be dequeued: - TBF computes btoks and ptoks based on the size of the peeked packet and decides whether to dequeue a packet or block based on the btoks and ptoks values. Also, if the packet is dequeued, the amount of tokens are updated based on btoks and ptoks, that have been computed for the peeked packet. - DRR decides to serve or not a class based on the size of the peeked packet. Now, for some qdiscs it is difficult to determine which packet is going to be extracted without actually dequeuing the packet. Codel and Fq-Codel, which drop packets after dequeue, are prominent examples. Codel may dequeue multiple packets before finding the one to return. So, I see the following alternatives: - implement a simple, possibly inaccurate, peek method, which however breaks the assumption of TBF and DRR - implement an accurate peek without dequeuing the packet. This is difficult for CoDel and Fq-Codel. The solution I can think of is to move the current DoDequeue() method into a DoDequeuePriv(bool peek) method that peeks and drops packets until a packet that has not to be dropped is found; then dequeues that packet if the peek param is false. - implement the Linux approach (the one followed currently and by the attached patch). Issues may arise if Peek is invoked at some point in time and Dequeue is called after some time, because at that time the dequeued packet may have been another one. I don't know if you agree with the analysis above. I would stick to the Linux approach because it appears to be simpler to me and the possibility of issues is rather small (I do not know of any qdisc that peeks a packet and then asks to dequeue it after some time).
(In reply to Stefano Avallone from comment #3) > > > I think that the default behavior should be that Peek() provides no > > guarantee on the next dequeued packet; it should provide a pointer to the > > object that would have been dequeued had Dequeue() instead been called. In > > most cases the eventual Dequeue() will in fact dequeue the same packet, but > > if some time passes, conditions may change. > > > > What do we lose with such an approach? > > Well, the thing is that a few qdiscs rely on the assumption that the peeked > packet is exactly the next packet that will be dequeued: > > - TBF computes btoks and ptoks based on the size of the peeked packet and > decides whether to dequeue a packet or block based on the btoks and ptoks > values. Also, if the packet is dequeued, the amount of tokens are updated > based on btoks and ptoks, that have been computed for the peeked packet. > > - DRR decides to serve or not a class based on the size of the peeked packet. > > Now, for some qdiscs it is difficult to determine which packet is going to > be extracted without actually dequeuing the packet. Codel and Fq-Codel, > which drop packets after dequeue, are prominent examples. Codel may dequeue > multiple packets before finding the one to return. So, I see the following > alternatives: > > - implement a simple, possibly inaccurate, peek method, which however breaks > the assumption of TBF and DRR > > - implement an accurate peek without dequeuing the packet. This is difficult > for CoDel and Fq-Codel. The solution I can think of is to move the current > DoDequeue() method into a DoDequeuePriv(bool peek) method that peeks and > drops packets until a packet that has not to be dropped is found; then > dequeues that packet if the peek param is false. > > - implement the Linux approach (the one followed currently and by the > attached patch). Issues may arise if Peek is invoked at some point in time > and Dequeue is called after some time, because at that time the dequeued > packet may have been another one. > > I don't know if you agree with the analysis above. I would stick to the > Linux approach because it appears to be simpler to me and the possibility of > issues is rather small (I do not know of any qdisc that peeks a packet and > then asks to dequeue it after some time). OK, I am for simplicity and Linux alignment (if they can be simultaneously achieved) and can give up on my proposed default behavior (but let's clearly document that Peek() has side effects). And let's stay away from multiple Peek and Dequeue public variants.
(In reply to Tom Henderson from comment #4) > OK, I am for simplicity and Linux alignment (if they can be simultaneously > achieved) and can give up on my proposed default behavior (but let's clearly > document that Peek() has side effects). > > And let's stay away from multiple Peek and Dequeue public variants. Yes, there is now only one version of Peek and Dequeue in the QueueDisc class interface. Pushed with changeset 13636:598125ee899e.