| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAK6E8=cuuTY0u0xqSKmoVzAuCOMdCm2UhyFxAgpa=51bvh_u-A@mail.gmail.com>
Date: Tue, 11 Oct 2016 20:56:47 -0700
From: Yuchung Cheng <ycheng@...gle.com>
To: Lawrence Brakmo <brakmo@...com>
Cc: netdev <netdev@...r.kernel.org>, Kernel Team <Kernel-team@...com>,
Eric Dumazet <eric.dumazet@...il.com>,
Neal Cardwell <ncardwell@...gle.com>
Subject: Re: [PATCH net-next] tcp: Change txhash on some non-RTO retransmits
On Tue, Oct 11, 2016 at 6:01 PM, Yuchung Cheng <ycheng@...gle.com> wrote:
> On Tue, Oct 11, 2016 at 2:08 PM, Lawrence Brakmo <brakmo@...com> wrote:
>> Yuchung, thank you for your comments. Responses inline.
>>
>> On 10/11/16, 12:49 PM, "Yuchung Cheng" <ycheng@...gle.com> wrote:
>>
>>>On Mon, Oct 10, 2016 at 5:18 PM, Lawrence Brakmo <brakmo@...com> wrote:
>>>>
>>>> The purpose of this patch is to help balance flows across paths. A new
>>>> sysctl "tcp_retrans_txhash_prob" specifies the probability (0-100) that
>>>> the txhash (IPv6 flowlabel) will be changed after a non-RTO retransmit.
>>>> A probability is used in order to control how many flows are moved
>>>> during a congestion event and prevent the congested path from becoming
>>>> under utilized (which could occur if too many flows leave the current
>>>> path). Txhash changes may be delayed in order to decrease the likelihood
>>>> that it will trigger retransmists due to too much reordering.
>>>>
>>>> Another sysctl "tcp_retrans_txhash_mode" determines the behavior after
>>>> RTOs. If the sysctl is 0, then after an RTO, only RTOs can trigger
>>>> txhash changes. The idea is to decrease the likelihood of going back
>>>> to a broken path. That is, we don't want flow balancing to trigger
>>>> changes to broken paths. The drawback is that flow balancing does
>>>> not work as well. If the sysctl is greater than 1, then we always
>>>> do flow balancing, even after RTOs.
>>>>
>>>> Tested with packedrill tests (for correctness) and performance
>>>> experiments with 2 and 3 paths. Performance experiments looked at
>>>> aggregate goodput and fairness. For each run, we looked at the ratio of
>>>> the goodputs for the fastest and slowest flows. These were averaged for
>>>> all the runs. A fairness of 1 means all flows had the same goodput, a
>>>> fairness of 2 means the fastest flow was twice as fast as the slowest
>>>> flow.
>>>>
>>>> The setup for the performance experiments was 4 or 5 serves in a rack,
>>>> 10G links. I tested various probabilities, but 20 seemed to have the
>>>> best tradeoff for my setup (small RTTs).
>>>>
>>>> --- node1 -----
>>>> sender --- switch --- node2 ----- switch ---- receiver
>>>> --- node3 -----
>>>>
>>>> Scenario 1: One sender sends to one receiver through 2 routes (node1 or
>>>> node 2). The output from node1 and node2 is 1G (1gbit/sec). With only 2
>>>> flows, without flow balancing (prob=0) the average goodput is 1.6G vs.
>>>> 1.9G with flow balancing due to 2 flows ending up in one link and either
>>>> not moving and taking some time to move. Fairness was 1 in all cases.
>>>> For 7 flows, goodput was 1.9G for all, but fairness was 1.5, 1.4 or 1.2
>>>> for prob=0, prob=20,mode=0 and prob=20,mode=1 respectively. That is,
>>>> flow balancing increased fairness.
>>>>
>>>> Scenario 2: One sender to one receiver, through 3 routes (node1,...
>>>> node2). With 6 or 16 flows the goodput was the same for all, but
>>>> fairness was 1.8, 1.5 and 1.2 respectively. Interestingly, the worst
>>>> case fairness out of 10 runs were 2.2, 1.8 and 1.4 repectively. That is,
>>>> prob=20,mode=1 improved average and worst case fairness.
>>>I am wondering if we can build better API with routing layer to
>>>implement this type of feature, instead of creeping the tx_rehashing
>>>logic scatter in TCP. For example, we call dst_negative_advice on TCP
>>>write timeouts.
>>
>> Not sure. The route is not necessarily bad, may be temporarily congested
>> or they may all be congested. If all we want to do is change the txhash
>> (unlike dst_negative_advice), then calling a tx_rehashing function may
>> be the appropriate call.
>>
>>>
>>>On the patch itself, it seems aggressive to (attempt to) rehash every
>>>post-RTO retranmission. Also you can just use ca_state (==CA_Loss) to
>>>identify post-RTO retransmission directly.
>>
>> Thanks, I will add the test.
>>
>>>
>>>is this an implementation of the Flow Bender ?
>>>https://urldefense.proofpoint.com/v2/url?u=http-3A__dl.acm.org_citation.cf
>>>m-3Fid-3D2674985&d=DQIBaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=pq_Mqvzfy-C8ltkgyx1u_
>>>g&m=Q4nONH7kQ5AvQguw9UxpcHd79jfdDdrXj1YSJs7Ezhk&s=MA4fWBLMTGgRS0eGvBjxf7BJ
>>>Ol3-oxAzZDEYUG4cE-s&e=
>>
>> Part of flow bender, although there are also some similarities to flowlet
>> switching.
>>
>>>
>>>>
>>>> Scenario 3: One sender to one receiver, 2 routes, one route drops 50% of
>>>> the packets. With 7 flows, goodput was the same 1.1G, but fairness was
>>>> 1.8, 2.0 and 2.1 respectively. That is, if there is a bad route, then
>>>> balancing, which does more re-routes, is less fair.
>>>>
>>>> Signed-off-by: Lawrence Brakmo <brakmo@...com>
>>>> ---
>>>> Documentation/networking/ip-sysctl.txt | 15 +++++++++++++++
>>>> include/linux/tcp.h | 4 +++-
>>>> include/net/tcp.h | 2 ++
>>>> net/ipv4/sysctl_net_ipv4.c | 18 ++++++++++++++++++
>>>> net/ipv4/tcp_input.c | 10 ++++++++++
>>>> net/ipv4/tcp_output.c | 23 ++++++++++++++++++++++-
>>>> net/ipv4/tcp_timer.c | 4 ++++
>>>> 7 files changed, 74 insertions(+), 2 deletions(-)
>>>>
>>>> diff --git a/Documentation/networking/ip-sysctl.txt
>>>>b/Documentation/networking/ip-sysctl.txt
>>>> index 3db8c67..87a984c 100644
>>>> --- a/Documentation/networking/ip-sysctl.txt
>>>> +++ b/Documentation/networking/ip-sysctl.txt
>>>> @@ -472,6 +472,21 @@ tcp_max_reordering - INTEGER
>>>> if paths are using per packet load balancing (like bonding rr
>>>>mode)
>>>> Default: 300
>>>>
>>>> +tcp_retrans_txhash_mode - INTEGER
>>>> + If zero, disable txhash recalculation due to non-RTO
>>>>retransmissions
>>>> + after an RTO. The idea is that broken paths will trigger an RTO
>>>>and
>>>> + we don't want going back to that path due to standard
>>>>retransmissons
>>>> + (flow balancing). The drawback is that balancing is less robust.
>>>> + If greater than zero, can always (probabilistically) recalculate
>>>> + txhash after non-RTO retransmissions.
>>>> +
>>>> +tcp_retrans_txhash_prob - INTEGER
>>>> + Probability [0 to 100] that we will recalculate txhash when a
>>>> + packet is resent not due to RTO (for RTO txhash is always
>>>>recalculated).
>>>> + The recalculation of the txhash may be delayed to decrease the
>>>> + likelihood that reordering will trigger retransmissons.
>>>> + The purpose is to help balance the flows among the possible
>>>>paths.
>>>> +
>>>> tcp_retrans_collapse - BOOLEAN
>>>> Bug-to-bug compatibility with some broken printers.
>>>> On retransmit try to send bigger packets to work around bugs in
>>>> diff --git a/include/linux/tcp.h b/include/linux/tcp.h
>>>> index a17ae7b..e0e3b7d 100644
>>>> --- a/include/linux/tcp.h
>>>> +++ b/include/linux/tcp.h
>>>> @@ -214,7 +214,9 @@ struct tcp_sock {
>>>> } rack;
>>>> u16 advmss; /* Advertised MSS
>>>>*/
>>>> u8 rate_app_limited:1, /* rate_{delivered,interval_us}
>>>>limited? */
>>>> - unused:7;
>>>> + txhash_rto:1, /* If set, don't do flow balancing
>>>>*/
>>>> + txhash_want:1, /* We want to change txhash when safe
>>>>*/
>>>> + unused:5;
>>>> u8 nonagle : 4,/* Disable Nagle algorithm?
>>>>*/
>>>> thin_lto : 1,/* Use linear timeouts for thin streams
>>>>*/
>>>> thin_dupack : 1,/* Fast retransmit on first dupack
>>>>*/
>>>> diff --git a/include/net/tcp.h b/include/net/tcp.h
>>>> index f83b7f2..3abd304 100644
>>>> --- a/include/net/tcp.h
>>>> +++ b/include/net/tcp.h
>>>> @@ -271,6 +271,8 @@ extern int sysctl_tcp_autocorking;
>>>> extern int sysctl_tcp_invalid_ratelimit;
>>>> extern int sysctl_tcp_pacing_ss_ratio;
>>>> extern int sysctl_tcp_pacing_ca_ratio;
>>>> +extern int sysctl_tcp_retrans_txhash_prob;
>>>> +extern int sysctl_tcp_retrans_txhash_mode;
>>>>
>>>> extern atomic_long_t tcp_memory_allocated;
>>>> extern struct percpu_counter tcp_sockets_allocated;
>>>> diff --git a/net/ipv4/sysctl_net_ipv4.c b/net/ipv4/sysctl_net_ipv4.c
>>>> index 1cb67de..00d6f26 100644
>>>> --- a/net/ipv4/sysctl_net_ipv4.c
>>>> +++ b/net/ipv4/sysctl_net_ipv4.c
>>>> @@ -28,6 +28,7 @@
>>>> static int zero;
>>>> static int one = 1;
>>>> static int four = 4;
>>>> +static int hundred = 100;
>>>> static int thousand = 1000;
>>>> static int gso_max_segs = GSO_MAX_SEGS;
>>>> static int tcp_retr1_max = 255;
>>>> @@ -624,6 +625,23 @@ static struct ctl_table ipv4_table[] = {
>>>> .proc_handler = proc_dointvec_ms_jiffies,
>>>> },
>>>> {
>>>> + .procname = "tcp_retrans_txhash_prob",
>>>> + .data = &sysctl_tcp_retrans_txhash_prob,
>>>> + .maxlen = sizeof(int),
>>>> + .mode = 0644,
>>>> + .proc_handler = proc_dointvec_minmax,
>>>> + .extra1 = &zero,
>>>> + .extra2 = &hundred,
>>>> + },
>>>> + {
>>>> + .procname = "tcp_retrans_txhash_mode",
>>>> + .data = &sysctl_tcp_retrans_txhash_mode,
>>>> + .maxlen = sizeof(int),
>>>> + .mode = 0644,
>>>> + .proc_handler = proc_dointvec_minmax,
>>>> + .extra1 = &zero,
>>>> + },
>>>> + {
>>>> .procname = "icmp_msgs_per_sec",
>>>> .data = &sysctl_icmp_msgs_per_sec,
>>>> .maxlen = sizeof(int),
>>>> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
>>>> index a27b9c0..fed5366 100644
>>>> --- a/net/ipv4/tcp_input.c
>>>> +++ b/net/ipv4/tcp_input.c
>>>> @@ -101,6 +101,9 @@ int sysctl_tcp_moderate_rcvbuf __read_mostly = 1;
>>>> int sysctl_tcp_early_retrans __read_mostly = 3;
>>>> int sysctl_tcp_invalid_ratelimit __read_mostly = HZ/2;
>>>>
>>>> +int sysctl_tcp_retrans_txhash_prob __read_mostly;
>>>> +int sysctl_tcp_retrans_txhash_mode __read_mostly;
>>>> +
>>>> #define FLAG_DATA 0x01 /* Incoming frame contained data.
>>>> */
>>>> #define FLAG_WIN_UPDATE 0x02 /* Incoming ACK was a
>>>>window update. */
>>>> #define FLAG_DATA_ACKED 0x04 /* This ACK acknowledged
>>>>new data. */
>>>> @@ -3674,6 +3677,13 @@ static int tcp_ack(struct sock *sk, const struct
>>>>sk_buff *skb, int flag)
>>>> flag |= tcp_clean_rtx_queue(sk, prior_fackets, prior_snd_una,
>>>>&acked,
>>>> &sack_state, &now);
>>>>
>>>> + /* Check if we should set txhash (would not cause reordering) */
>>>> + if (tp->txhash_want &&
>>>> + (tp->packets_out - tp->sacked_out) < tp->reordering) {
>>>> + sk_set_txhash(sk);
>>>> + tp->txhash_want = 0;
>>>> + }
>>>> +
>>>> if (tcp_ack_is_dubious(sk, flag)) {
>>>> is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED |
>>>>FLAG_NOT_DUP));
>>>> tcp_fastretrans_alert(sk, acked, is_dupack, &flag,
>>>>&rexmit);
>>>> diff --git a/net/ipv4/tcp_output.c b/net/ipv4/tcp_output.c
>>>> index 896e9df..58490ac 100644
>>>> --- a/net/ipv4/tcp_output.c
>>>> +++ b/net/ipv4/tcp_output.c
>>>> @@ -2738,9 +2738,30 @@ int tcp_retransmit_skb(struct sock *sk, struct
>>>>sk_buff *skb, int segs)
>>>> tp->retrans_out += tcp_skb_pcount(skb);
>>>>
>>>> /* Save stamp of the first retransmit. */
>>>> - if (!tp->retrans_stamp)
>>>> + if (!tp->retrans_stamp) {
>>>> tp->retrans_stamp = tcp_skb_timestamp(skb);
>>>>
>>>> + /* Determine if we should reset hash, only done
>>>>once
>>>> + * per recovery
>>>> + */
>>>> + if ((!tp->txhash_rto ||
>>>> + sysctl_tcp_retrans_txhash_mode > 0) &&
>>>> + sk->sk_txhash &&
>>>> + (prandom_u32_max(100) <
>>>> + sysctl_tcp_retrans_txhash_prob)) {
>>>> + /* If not too much reordering, or RTT is
>>>> + * small enough that we don't care about
>>>> + * reordering, then change it now.
>>>> + * Else, wait until it is safe.
>>>> + */
>>>> + if ((tp->packets_out - tp->sacked_out) <
>>>> + tp->reordering)
>>>I don't parse this logic ... suppose reordering is 100 (not uncommon
>>>today due to the last packet being delivered slightly earlier than the
>>>rest), and cwnd==packets_out =~200,we only want to rehash until half
>>>of the packets are sacked, so we are still rehashing even when
>>>reordering is heavy?
>>
>> In your scenario, there would be no re-hashing until sacked_out is 101
>> ((packets_out - sacked_out) < 100). This code would mark txhash_want.
>> Then when an ACK is received and the conditional is true, txhash
>> would be changed.
>>
>> Now, the test does not prevent retransmissions due to reordering in all
>> cases, but hopefully in most. I will also add the test you recommended,
>> checking for CA_Loss, to prevent too much re-hashing.
> If the whole point is to rehash at most once between recovery events,
> why do we need this complicated change at per packet level in
> tcp_retransmit_skb()? there are functions that start and end recovery
> (tcp_enter_recovery, tcp_end_cwnd_reduction). our retransmission logic
> is already very complicated.
>
> I still don't understand the incentive of starting the rehashing
> half-way retransmitting depending on the sacking and reordering
> status, for temporarily congestion as you've mentioned.
>
> is this feature unique for intra-DC connections?
I thought more about this patch on my way home and have more
questions: why do we exclude RTO retransmission specifically? also
when we rehash, we'll introduce reordering either in recovery or after
recovery, as some TCP CC like bbr would continue sending regardlessly,
so starting in tcp_ack() with tp->txhash_want does not really prevent
causing more reordering.
so if we want to rehash upon a recovery event (fast or timeout), then
we can make a helper function ie tcp_retry_alt_path, and just call it
in tcp_enter_loss and tcp_recovery (which are called once per
recovery). Since it'll cause reordering anyways, I doubt we need to
check tp->reordering at all. If packets already traverse different
paths, rehashing can make it better or worse. if packets weren't
traversing different paths, the rehashing itself can introduce
reordering. so in the end there is much benefit to make decision based
on current inflight and reordering IMO...
>
>>
>>>
>>>also where do we check RTT is small?
>>
>> The RTT comment is left over from a previous version, I will remove it.
>>
>>>
>>>> + sk_set_txhash(sk);
>>>> + else
>>>> + tp->txhash_want = 1;
>>>> + }
>>>> + }
>>>> +
>>>> } else if (err != -EBUSY) {
>>>> NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPRETRANSFAIL);
>>>> }
>>>> diff --git a/net/ipv4/tcp_timer.c b/net/ipv4/tcp_timer.c
>>>> index 3ea1cf8..e66baad 100644
>>>> --- a/net/ipv4/tcp_timer.c
>>>> +++ b/net/ipv4/tcp_timer.c
>>>> @@ -186,6 +186,8 @@ static int tcp_write_timeout(struct sock *sk)
>>>>
>>>> if ((1 << sk->sk_state) & (TCPF_SYN_SENT | TCPF_SYN_RECV)) {
>>>> if (icsk->icsk_retransmits) {
>>>> + tp->txhash_rto = 1;
>>>> + tp->txhash_want = 0;
>>>> dst_negative_advice(sk);
>>>> if (tp->syn_fastopen || tp->syn_data)
>>>> tcp_fastopen_cache_set(sk, 0, NULL,
>>>>true, 0);
>>>> @@ -218,6 +220,8 @@ static int tcp_write_timeout(struct sock *sk)
>>>> } else {
>>>> sk_rethink_txhash(sk);
>>>> }
>>>> + tp->txhash_rto = 1;
>>>> + tp->txhash_want = 0;
>>>>
>>>> retry_until = net->ipv4.sysctl_tcp_retries2;
>>>> if (sock_flag(sk, SOCK_DEAD)) {
>>>> --
>>>> 2.9.3
>>>>
>>
Powered by blists - more mailing lists