From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt1-x830.google.com (mail-qt1-x830.google.com [IPv6:2607:f8b0:4864:20::830]) (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 7BFF73CB35 for ; Thu, 14 Feb 2019 13:02:22 -0500 (EST) Received: by mail-qt1-x830.google.com with SMTP id w4so7936234qtc.1 for ; Thu, 14 Feb 2019 10:02:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=oWmPYuU/U/fSfEN9MxhDDBTI9ZSeTFQ0FutlfBMOwSc=; b=QZgpbyxVqyhExUvmdMOz5XE414708wzSqZ3utjplzmimQQJCKZInHU2y7nsgUlfWQo l0rqVQY/ysjCdrfZMvrst8jlEzOKNkbx2rwaBFGB80Uo1WHSXAMJyoh5PuifIYjAM8Sf YKD+DyTFUerpdBAx3mJE04T2sATHdDf++ZENItdwectFehVNRs4t7SnVhNiVKTqlfMhS 0XR/aWLkIIZM9l4i+zKNih1jywPqEFDvYGlxsHBoGZCke3PqvGGlKfItf9BMv+k36/47 FhOpoJG1ukPF7L2BkXQvnKlDx1OzqjRmmWU5q/FREuM2xcKusHhisCW2GUzyrHtOE8Pu HYDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=oWmPYuU/U/fSfEN9MxhDDBTI9ZSeTFQ0FutlfBMOwSc=; b=DbWmVlJdYdgMO+vTCZV2tWRUa5H8Q1LbTCjzBuchApRcPH1Qi1hxSYJtBz+f3ggRWb Hxv5YyDF+R173L1+6/XbwjgGHAjAaXSbThG6nnxtjZU56UZ85q2t/zdOhNl5U6LJPo5L ORcnP71JT04g4YpRsfgzkbLSTftfQIDjL+FgKbVZq5mC9WAvwKJRa/iCmqwFiA/9dEXS ixnsuia95NkKFFLuPgQilTbdoDhbEjuY6m9ax2X8xslnLkpuRdnJueJZOrvf+HcKudtz KsOjYwC03MeE0UPKPqNcLqhOBeRliXnm4S+IctOWUigv9FikowwDzdufRwqxPvr46hY5 +Obg== X-Gm-Message-State: AHQUAuZjuatwhJHFZo+EDMN1z80U9qMZX90CJFnSVUEf5c2mniDaiTlu +bWNrdM4uYdKjOQ5USeemGc= X-Google-Smtp-Source: AHgI3IbeeaAnAwIaDV/65gJxmG8/YyuF/I2EoVWDOzVWFuXeg8QoVN22Al6NxTIYhZUoPmKucBzkHA== X-Received: by 2002:a0c:d2a5:: with SMTP id q34mr4096709qvh.102.1550167341772; Thu, 14 Feb 2019 10:02:21 -0800 (PST) Received: from x3200.lan ([2601:152:4302:ae1f::16e]) by smtp.gmail.com with ESMTPSA id o21sm1785968qto.18.2019.02.14.10.02.20 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 14 Feb 2019 10:02:20 -0800 (PST) From: George Amanakis To: toke@redhat.com Cc: cake@lists.bufferbloat.net, chromatix99@gmail.com, George Amanakis Date: Thu, 14 Feb 2019 13:02:17 -0500 Message-Id: <20190214180217.13090-1-gamanakis@gmail.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <87a7iymxie.fsf@toke.dk> References: <87a7iymxie.fsf@toke.dk> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Cake] progress? dual-src/dsthost unfairness 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: Thu, 14 Feb 2019 18:02:22 -0000 I tried Toke's and Jonathan's suggestion, dropping the sparse_flow_count. Tthe results are the same (fairness). In a hash collision in this patch the host_bulk_flow_count is not updated, does this make sense? -------------------8<------------------- Client A: Data file written to ./tcp_8down-2019-02-14T115248.702453.flent.gz. Summary of tcp_8down test run at 2019-02-14 16:52:48.702453: avg median # data pts Ping (ms) ICMP : 0.78 0.69 ms 341 TCP download avg : 6.00 5.81 Mbits/s 301 TCP download sum : 48.00 46.51 Mbits/s 301 TCP download::1 : 6.00 5.82 Mbits/s 297 TCP download::2 : 5.99 5.82 Mbits/s 297 TCP download::3 : 6.00 5.82 Mbits/s 297 TCP download::4 : 6.00 5.82 Mbits/s 297 TCP download::5 : 6.00 5.82 Mbits/s 297 TCP download::6 : 6.00 5.82 Mbits/s 298 TCP download::7 : 6.01 5.82 Mbits/s 297 TCP download::8 : 6.00 5.82 Mbits/s 298 Data file written to ./tcp_1up-2019-02-14T115249.700445.flent.gz. Summary of tcp_1up test run at 2019-02-14 16:52:49.700445: avg median # data pts Ping (ms) ICMP : 0.79 0.69 ms 341 TCP upload : 47.69 46.33 Mbits/s 266 Client B: Data file written to ./tcp_1down-2019-02-14T115250.817948.flent.gz. Summary of tcp_1down test run at 2019-02-14 16:52:50.817948: avg median # data pts Ping (ms) ICMP : 0.83 0.69 ms 341 TCP download : 47.82 46.57 Mbits/s 300 Data file written to ./tcp_8up-2019-02-14T115251.710755.flent.gz. Summary of tcp_8up test run at 2019-02-14 16:52:51.710755: avg median # data pts Ping (ms) ICMP : 0.78 0.69 ms 341 TCP upload avg : 5.99 5.79 Mbits/s 301 TCP upload sum : 47.88 46.30 Mbits/s 301 TCP upload::1 : 5.98 5.81 Mbits/s 224 TCP upload::2 : 5.99 5.82 Mbits/s 224 TCP upload::3 : 5.98 5.77 Mbits/s 219 TCP upload::4 : 5.98 5.82 Mbits/s 224 TCP upload::5 : 5.99 5.77 Mbits/s 218 TCP upload::6 : 5.99 5.77 Mbits/s 221 TCP upload::7 : 5.98 5.77 Mbits/s 219 TCP upload::8 : 5.99 5.77 Mbits/s 221 -------------------8<------------------- --- sch_cake.c | 84 +++++++++++++++++++++++++++++++++++------------------- 1 file changed, 55 insertions(+), 29 deletions(-) diff --git a/sch_cake.c b/sch_cake.c index d434ae0..ed3fbd9 100644 --- a/sch_cake.c +++ b/sch_cake.c @@ -146,8 +146,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 { @@ -844,8 +844,6 @@ skip_hash: * 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--; allocate_src = cake_dsrc(flow_mode); allocate_dst = cake_ddst(flow_mode); found: @@ -865,13 +863,12 @@ found: } 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++; q->flows[reduced_hash].srchost = srchost_idx; } @@ -887,13 +884,12 @@ found_src: } 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++; q->flows[reduced_hash].dsthost = dsthost_idx; } } @@ -1913,20 +1909,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) @@ -2097,23 +2103,8 @@ retry: 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 @@ -2122,6 +2113,13 @@ retry: 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 @@ -2131,6 +2129,22 @@ retry: 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; } @@ -2151,6 +2165,13 @@ retry: &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) { @@ -2164,14 +2185,19 @@ retry: 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; } -- 2.20.1