From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-f67.google.com (mail-ed1-f67.google.com [209.85.208.67]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 704973B29E for ; Fri, 1 Mar 2019 10:04:08 -0500 (EST) Received: by mail-ed1-f67.google.com with SMTP id j89so20238510edb.9 for ; Fri, 01 Mar 2019 07:04:08 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:date:message-id:in-reply-to :references:user-agent:mime-version:content-transfer-encoding; bh=1LfnmhK8SZIryJQ9PyneQkZkHt/nqMGcRAzEK+mHaqU=; b=YAWGCXxInV5hgAZBAQ4BjMaThuC9l+l+AKP09iaFLX7fLMCI3dlAIe2iiAEkVX/PcG OTmRdyDZtGVAotYc6jqHboRpZ9aOIQpPXA5qE8WlPGctnJQDVNvu7YxbcgWZAMLouz8x Y/kWBGn9fH3q2QGqDCCADGIXLNWh0Vyg+Qsuq+jceOlKVALJdiaeoXaINgP1Fs+PCyGM cN6fOFJPeEh2qfhsrK/2sgdQeVouvzBKXBpLBh/AYjFMJUrQW1X/Tw7PkOR5b9nRouCM dNFCGnDJWcmHyCJ/cR9GukMYzFqevKQItuT7YTmGtPXirHQoRRgpA1xIW/ADnja4ujX7 7BLA== X-Gm-Message-State: APjAAAVW5rrmiK/WFLr7gkQYVjUwORm6MgO/Qrn6R6+oyoq74WY362ou 2saZLHMhvVqrslhLQQv6+Ro8/httGqpf8Q== X-Google-Smtp-Source: APXvYqyjcMXkOvKFsDzhco3Cehmms/khEHFW6XwIjTUAn82RlIFLLarKH3ypZXyo5MJ4KN4LrxY4GA== X-Received: by 2002:a50:86cf:: with SMTP id 15mr4488092edu.239.1551452647443; Fri, 01 Mar 2019 07:04:07 -0800 (PST) Received: from alrua-x1.borgediget.toke.dk (borgediget.toke.dk. [85.204.121.218]) by smtp.gmail.com with ESMTPSA id c25sm3795261ejx.59.2019.03.01.07.04.05 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 01 Mar 2019 07:04:06 -0800 (PST) Received: by alrua-x1.borgediget.toke.dk (Postfix, from userid 1000) id B03EE183BC2; Fri, 1 Mar 2019 16:04:05 +0100 (CET) From: Toke =?utf-8?q?H=C3=B8iland-J=C3=B8rgensen?= To: David Miller Cc: netdev@vger.kernel.org, cake@lists.bufferbloat.net Date: Fri, 01 Mar 2019 16:04:05 +0100 Message-ID: <155145264566.2564.5441035720427386183.stgit@alrua-x1> In-Reply-To: <155145264557.2564.18246059144961803752.stgit@alrua-x1> References: <155145264557.2564.18246059144961803752.stgit@alrua-x1> User-Agent: StGit/unknown-version MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit Subject: [Cake] [PATCH net-next v1 1/3] sch_cake: Make the dual modes fairer X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Mar 2019 15:04:08 -0000 From: George Amanakis CAKE host fairness does not work well with TCP flows in dual-srchost and dual-dsthost setup. The reason is that ACKs generated by TCP flows are classified as sparse flows, and affect flow isolation from other hosts. Fix this by calculating host_load based only on the bulk flows a host generates. In a hash collision the host_bulk_flow_count values must be decremented on the old hosts and incremented on the new ones *if* the queue is in the bulk set. Reported-by: Pete Heist Signed-off-by: George Amanakis Signed-off-by: Toke Høiland-Jørgensen --- net/sched/sch_cake.c | 92 ++++++++++++++++++++++++++++++++++---------------- 1 file changed, 63 insertions(+), 29 deletions(-) diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c index 73940293700d..4d688b3b471b 100644 --- a/net/sched/sch_cake.c +++ b/net/sched/sch_cake.c @@ -138,8 +138,8 @@ struct cake_flow { struct cake_host { u32 srchost_tag; u32 dsthost_tag; - u16 srchost_refcnt; - u16 dsthost_refcnt; + u16 srchost_bulk_flow_count; + u16 dsthost_bulk_flow_count; }; struct cake_heap_entry { @@ -746,8 +746,10 @@ static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb, * queue, accept the collision, update the host tags. */ q->way_collisions++; - q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--; - q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--; + if (q->flows[outer_hash + k].set == CAKE_SET_BULK) { + q->hosts[q->flows[reduced_hash].srchost].srchost_bulk_flow_count--; + q->hosts[q->flows[reduced_hash].dsthost].dsthost_bulk_flow_count--; + } allocate_src = cake_dsrc(flow_mode); allocate_dst = cake_ddst(flow_mode); found: @@ -767,13 +769,14 @@ static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb, } for (i = 0; i < CAKE_SET_WAYS; i++, k = (k + 1) % CAKE_SET_WAYS) { - if (!q->hosts[outer_hash + k].srchost_refcnt) + if (!q->hosts[outer_hash + k].srchost_bulk_flow_count) break; } q->hosts[outer_hash + k].srchost_tag = srchost_hash; found_src: srchost_idx = outer_hash + k; - q->hosts[srchost_idx].srchost_refcnt++; + if (q->flows[reduced_hash].set == CAKE_SET_BULK) + q->hosts[srchost_idx].srchost_bulk_flow_count++; q->flows[reduced_hash].srchost = srchost_idx; } @@ -789,13 +792,14 @@ static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb, } for (i = 0; i < CAKE_SET_WAYS; i++, k = (k + 1) % CAKE_SET_WAYS) { - if (!q->hosts[outer_hash + k].dsthost_refcnt) + if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count) break; } q->hosts[outer_hash + k].dsthost_tag = dsthost_hash; found_dst: dsthost_idx = outer_hash + k; - q->hosts[dsthost_idx].dsthost_refcnt++; + if (q->flows[reduced_hash].set == CAKE_SET_BULK) + q->hosts[dsthost_idx].dsthost_bulk_flow_count++; q->flows[reduced_hash].dsthost = dsthost_idx; } } @@ -1794,20 +1798,30 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch, b->sparse_flow_count++; if (cake_dsrc(q->flow_mode)) - host_load = max(host_load, srchost->srchost_refcnt); + host_load = max(host_load, srchost->srchost_bulk_flow_count); if (cake_ddst(q->flow_mode)) - host_load = max(host_load, dsthost->dsthost_refcnt); + host_load = max(host_load, dsthost->dsthost_bulk_flow_count); flow->deficit = (b->flow_quantum * quantum_div[host_load]) >> 16; } else if (flow->set == CAKE_SET_SPARSE_WAIT) { + struct cake_host *srchost = &b->hosts[flow->srchost]; + struct cake_host *dsthost = &b->hosts[flow->dsthost]; + /* this flow was empty, accounted as a sparse flow, but actually * in the bulk rotation. */ flow->set = CAKE_SET_BULK; b->sparse_flow_count--; b->bulk_flow_count++; + + if (cake_dsrc(q->flow_mode)) + srchost->srchost_bulk_flow_count++; + + if (cake_ddst(q->flow_mode)) + dsthost->dsthost_bulk_flow_count++; + } if (q->buffer_used > q->buffer_max_used) @@ -1975,23 +1989,8 @@ static struct sk_buff *cake_dequeue(struct Qdisc *sch) dsthost = &b->hosts[flow->dsthost]; host_load = 1; - if (cake_dsrc(q->flow_mode)) - host_load = max(host_load, srchost->srchost_refcnt); - - if (cake_ddst(q->flow_mode)) - host_load = max(host_load, dsthost->dsthost_refcnt); - - WARN_ON(host_load > CAKE_QUEUES); - /* flow isolation (DRR++) */ if (flow->deficit <= 0) { - /* The shifted prandom_u32() is a way to apply dithering to - * avoid accumulating roundoff errors - */ - flow->deficit += (b->flow_quantum * quantum_div[host_load] + - (prandom_u32() >> 16)) >> 16; - list_move_tail(&flow->flowchain, &b->old_flows); - /* Keep all flows with deficits out of the sparse and decaying * rotations. No non-empty flow can go into the decaying * rotation, so they can't get deficits @@ -2000,6 +1999,13 @@ static struct sk_buff *cake_dequeue(struct Qdisc *sch) if (flow->head) { b->sparse_flow_count--; b->bulk_flow_count++; + + if (cake_dsrc(q->flow_mode)) + srchost->srchost_bulk_flow_count++; + + if (cake_ddst(q->flow_mode)) + dsthost->dsthost_bulk_flow_count++; + flow->set = CAKE_SET_BULK; } else { /* we've moved it to the bulk rotation for @@ -2009,6 +2015,22 @@ static struct sk_buff *cake_dequeue(struct Qdisc *sch) flow->set = CAKE_SET_SPARSE_WAIT; } } + + if (cake_dsrc(q->flow_mode)) + host_load = max(host_load, srchost->srchost_bulk_flow_count); + + if (cake_ddst(q->flow_mode)) + host_load = max(host_load, dsthost->dsthost_bulk_flow_count); + + WARN_ON(host_load > CAKE_QUEUES); + + /* The shifted prandom_u32() is a way to apply dithering to + * avoid accumulating roundoff errors + */ + flow->deficit += (b->flow_quantum * quantum_div[host_load] + + (prandom_u32() >> 16)) >> 16; + list_move_tail(&flow->flowchain, &b->old_flows); + goto retry; } @@ -2029,6 +2051,13 @@ static struct sk_buff *cake_dequeue(struct Qdisc *sch) &b->decaying_flows); if (flow->set == CAKE_SET_BULK) { b->bulk_flow_count--; + + if (cake_dsrc(q->flow_mode)) + srchost->srchost_bulk_flow_count--; + + if (cake_ddst(q->flow_mode)) + dsthost->dsthost_bulk_flow_count--; + b->decaying_flow_count++; } else if (flow->set == CAKE_SET_SPARSE || flow->set == CAKE_SET_SPARSE_WAIT) { @@ -2042,14 +2071,19 @@ static struct sk_buff *cake_dequeue(struct Qdisc *sch) if (flow->set == CAKE_SET_SPARSE || flow->set == CAKE_SET_SPARSE_WAIT) b->sparse_flow_count--; - else if (flow->set == CAKE_SET_BULK) + else if (flow->set == CAKE_SET_BULK) { b->bulk_flow_count--; - else + + if (cake_dsrc(q->flow_mode)) + srchost->srchost_bulk_flow_count--; + + if (cake_ddst(q->flow_mode)) + dsthost->dsthost_bulk_flow_count--; + + } else b->decaying_flow_count--; flow->set = CAKE_SET_NONE; - srchost->srchost_refcnt--; - dsthost->dsthost_refcnt--; } goto begin; }