Message ID | 1331697865.2456.19.camel@edumazet-laptop |
---|---|
State | Accepted, archived |
Delegated to: | David Miller |
Headers | show |
On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of > flows) > > As Jesper found out, patch sounded great but has bad side effects. Well under most circumstances it IS great. As the depth of the sfq queue increases it gets increasingly hard to trigger the problem. I've been using values in the 200-300 range, and in combination with red, haven't seen it happen. Also in part the sfq behavior observed is due to an interaction with htb's 'capture' of a packet rather than peek. The situation that jesper encountered this issue (trying to regulate flows to hundreds of downstream clients on a very deterministic test) was different from where I don't encounter it (trying to regulate flows up from a very few clients) For more details: http://www.bufferbloat.net/issues/332 But I concur in reverting this for now. Sadly. wouldn't mind if there was a way to keep it as is as an option... > > In stress situation, pushing new flows in front of the queue can prevent > old flows doing any progress. Packets can stay in SFQ queue for > unlimited amount of time. > > It's possible to add heuristics to limit this problem, but this would > add complexity outside of SFQ scope. > > A more sensible answer to Dave Taht concerns (who reported the issued I > tried to solve in original commit) is probably to use a qdisc hierarchy > so that high prio packets dont enter a potentially crowded SFQ qdisc. Um, er, in today's port 80/433 world, there isn't any such thing as high prio packets. I am curious as to whether this problem can be made to happen with qfq. > Reported-by: Jesper Dangaard Brouer <jdb@comx.dk> > Cc: Dave Taht <dave.taht@gmail.com> > Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> > --- > I tried various tricks to avoid a revert but in the end it sounds better > to use a single queue. I had some hope for a semi-random alternating queue > > net/sched/sch_sfq.c | 6 +++++- > 1 file changed, 5 insertions(+), 1 deletion(-) > > diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c > index 60d4718..02a21ab 100644 > --- a/net/sched/sch_sfq.c > +++ b/net/sched/sch_sfq.c > @@ -469,11 +469,15 @@ enqueue: > if (slot->qlen == 1) { /* The flow is new */ > if (q->tail == NULL) { /* It is the first flow */ > slot->next = x; > - q->tail = slot; > } else { > slot->next = q->tail->next; > q->tail->next = x; > } > + /* We put this flow at the end of our flow list. > + * This might sound unfair for a new flow to wait after old ones, > + * but we could endup servicing new flows only, and freeze old ones. > + */ > + q->tail = slot; > /* We could use a bigger initial quantum for new flows */ > slot->allot = q->scaled_quantum; > } > >
Le mercredi 14 mars 2012 à 04:52 +0000, Dave Taht a écrit : > I had some hope for a semi-random alternating queue > I spent some time implementing two queues, one for new flows, one for old flows. As soon as a new flow uses its initial quantum, its moved at the tail of 'old flows queue'. But I always could find a way to starve some flows, even adding some kind of persistence. Right now, as soon as we empty one flow, we forget its history. Next packet coming will create a "new flow" with a full quantum credit, even if we nearly consume all flow quantum in the last micro second. Thats definitely not a trivial problem. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Mar 14, 2012 at 5:02 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > Le mercredi 14 mars 2012 à 04:52 +0000, Dave Taht a écrit : > >> I had some hope for a semi-random alternating queue >> > > I spent some time implementing two queues, one for new flows, one for > old flows. As soon as a new flow uses its initial quantum, its moved at > the tail of 'old flows queue'. > > But I always could find a way to starve some flows, even adding some > kind of persistence. Right now, as soon as we empty one flow, we forget > its history. > > Next packet coming will create a "new flow" with a full quantum credit, > even if we nearly consume all flow quantum in the last micro second. > > Thats definitely not a trivial problem. I've expended brain cells on this too (nobody has any experience with head drop, aqm managed queues!), and was unable to come up with a way of dealing with the corner case of too many new streams inside of sfq's current architecture. But I gotta say that the overall effect of this on optimizing sparse streams (dns,dhcp,tcp syn,ra,other routing packets,gaming packets,etc) was pretty freaking amazing, and it nearly eliminated any need for classification and prioritization, BE, and BK were enough. Ah, well. The other stuff in 3.3 is really good, too. Sometimes you win, sometimes you lose, sometimes... it rains. > > >
ons, 14 03 2012 kl. 04:52 +0000, skrev Dave Taht: > On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > > This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of > > flows) > > > > As Jesper found out, patch sounded great but has bad side effects. > > Well under most circumstances it IS great. Yes, I had really high hopes for this patch. It unfortunately it can cause starvation in some situations :-(. > As the depth of the sfq queue increases it gets increasingly hard to > trigger the problem. I've been using values in the 200-300 range, and > in combination with red, haven't seen it happen. I don't think you should adjust the "depth", but instead "limit" or "flows". The problem can be solved by SFQ parameter tuning. Perhaps, we could just change the default parameters? The problem occurs when all flows have ONE packet, then sfq_drop() cannot find a good flow to drop packets from... This situation can occur because the default setting is "limit=127" packets and "flows=127". If we just make sure that "limit" > "flows", then one flow with >=2 packets should exist, which is then chosen for drop. My practical experiments show that "limit" should be between 10-20 packets larger than "flows" (I'm not completely sure why this is needed). [cut] > > In stress situation, pushing new flows in front of the queue can prevent > > old flows doing any progress. Packets can stay in SFQ queue for > > unlimited amount of time. In my experiments, one "existing" flow would get all the bandwidth, while other flows got starved. And new flows could not be established. --Jesper Brouer -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Le mercredi 14 mars 2012 à 12:32 +0100, Jesper Dangaard Brouer a écrit : > ons, 14 03 2012 kl. 04:52 +0000, skrev Dave Taht: > > On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > > As the depth of the sfq queue increases it gets increasingly hard to > > trigger the problem. I've been using values in the 200-300 range, and > > in combination with red, haven't seen it happen. > > I don't think you should adjust the "depth", but instead "limit" or > "flows". > > The problem can be solved by SFQ parameter tuning. Perhaps, we could > just change the default parameters? > > The problem occurs when all flows have ONE packet, then sfq_drop() > cannot find a good flow to drop packets from... > > This situation can occur because the default setting is "limit=127" > packets and "flows=127". If we just make sure that "limit" > "flows", > then one flow with >=2 packets should exist, which is then chosen for > drop. > My practical experiments show that "limit" should be between 10-20 > packets larger than "flows" (I'm not completely sure why this is > needed). > There are many ways to starve SFQ if we dont revert the patch or add new logic in linux-3.4 Even if we change default settings, we can have following situation : SFQ in a state with several regular flows in queue, correctly behaving because they are nice. loop repeat_as_many_times_you_can_think enqueue : packet comes for a new flow X. OK lets favor this new flow against 'old' ones. dequeue : takes the packet for flow X. forget about flow X since dequeue all its packets. endloop All other flows are in a frozen state. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, Mar 14, 2012 at 2:04 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > Le mercredi 14 mars 2012 à 12:32 +0100, Jesper Dangaard Brouer a écrit : >> ons, 14 03 2012 kl. 04:52 +0000, skrev Dave Taht: >> > On Wed, Mar 14, 2012 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote: > >> > As the depth of the sfq queue increases it gets increasingly hard to >> > trigger the problem. I've been using values in the 200-300 range, and >> > in combination with red, haven't seen it happen. >> >> I don't think you should adjust the "depth", but instead "limit" or >> "flows". Sorry, I'd meant 'limit' above, with limiting the per flow depth (at 4Mbit depths of 12-24 are good + red doing byte limiting starting at 3000), and having lots of flows in the hash.... Anyway, as this change to sfq currently has pathological edge cases, I suggest: 1) reverting this patch (the new features of sfq - hugely increased number of flows, and increased limit, head drop/marking support, red, ecn, etc, can stay - and are rather nice in and of themselves) 2) trying again, but not in the context of sfq - starting with sfq as a base, with a copy and rename, getting the iproute infrastructure around it working, more thorough tests going. I'll note that while flow management is needed, it needent be red-based. nsfq? efq? >> >> The problem can be solved by SFQ parameter tuning. Perhaps, we could >> just change the default parameters? I can't think of a way to make existing users of sfq not hit this problem if they are overriding the default params in the first place. thus my suggestion we start again in a new namespace. >> The problem occurs when all flows have ONE packet, then sfq_drop() >> cannot find a good flow to drop packets from... >> >> This situation can occur because the default setting is "limit=127" >> packets and "flows=127". If we just make sure that "limit" > "flows", >> then one flow with >=2 packets should exist, which is then chosen for >> drop. >> My practical experiments show that "limit" should be between 10-20 >> packets larger than "flows" (I'm not completely sure why this is >> needed). flows and/or depth? if flows, then we could drop the flows parameter entirely and just use limit to calculate flows. But I think that it's more subtle than just this. more thorough tests exploring the pathological cases are needed. I'm on it. >> > > There are many ways to starve SFQ if we dont revert the patch or add new > logic in linux-3.4 > > Even if we change default settings, we can have following situation : > > SFQ in a state with several regular flows in queue, correctly behaving > because they are nice. > > loop repeat_as_many_times_you_can_think > enqueue : packet comes for a new flow X. > OK lets favor this new flow against 'old' ones. > dequeue : takes the packet for flow X. > forget about flow X since dequeue all its packets. > endloop > > All other flows are in a frozen state. some thoughts 1) Keeping more history around during the next X packet deliveries would help. 2) in case of being close up against various limits randomly enqueue on tail I note that htb introduces a window for new flows to win pathologically by holding onto a packet which perhaps it should be peeking (or so I understand it) > > >
From: Eric Dumazet <eric.dumazet@gmail.com> Date: Tue, 13 Mar 2012 21:04:25 -0700 > This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of > flows) > > As Jesper found out, patch sounded great but has bad side effects. > > In stress situation, pushing new flows in front of the queue can prevent > old flows doing any progress. Packets can stay in SFQ queue for > unlimited amount of time. > > It's possible to add heuristics to limit this problem, but this would > add complexity outside of SFQ scope. > > A more sensible answer to Dave Taht concerns (who reported the issued I > tried to solve in original commit) is probably to use a qdisc hierarchy > so that high prio packets dont enter a potentially crowded SFQ qdisc. > > Reported-by: Jesper Dangaard Brouer <jdb@comx.dk> > Cc: Dave Taht <dave.taht@gmail.com> > Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> Applied, thanks Eric. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c index 60d4718..02a21ab 100644 --- a/net/sched/sch_sfq.c +++ b/net/sched/sch_sfq.c @@ -469,11 +469,15 @@ enqueue: if (slot->qlen == 1) { /* The flow is new */ if (q->tail == NULL) { /* It is the first flow */ slot->next = x; - q->tail = slot; } else { slot->next = q->tail->next; q->tail->next = x; } + /* We put this flow at the end of our flow list. + * This might sound unfair for a new flow to wait after old ones, + * but we could endup servicing new flows only, and freeze old ones. + */ + q->tail = slot; /* We could use a bigger initial quantum for new flows */ slot->allot = q->scaled_quantum; }
This reverts commit d47a0ac7b6 (sch_sfq: dont put new flow at the end of flows) As Jesper found out, patch sounded great but has bad side effects. In stress situation, pushing new flows in front of the queue can prevent old flows doing any progress. Packets can stay in SFQ queue for unlimited amount of time. It's possible to add heuristics to limit this problem, but this would add complexity outside of SFQ scope. A more sensible answer to Dave Taht concerns (who reported the issued I tried to solve in original commit) is probably to use a qdisc hierarchy so that high prio packets dont enter a potentially crowded SFQ qdisc. Reported-by: Jesper Dangaard Brouer <jdb@comx.dk> Cc: Dave Taht <dave.taht@gmail.com> Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> --- I tried various tricks to avoid a revert but in the end it sounds better to use a single queue. net/sched/sch_sfq.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html