rtt.c 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
  1. // SPDX-License-Identifier: GPL-2.0
  2. /* RTT/RTO calculation.
  3. *
  4. * Adapted from TCP for AF_RXRPC by David Howells (dhowells@redhat.com)
  5. *
  6. * https://tools.ietf.org/html/rfc6298
  7. * https://tools.ietf.org/html/rfc1122#section-4.2.3.1
  8. * http://ccr.sigcomm.org/archive/1995/jan95/ccr-9501-partridge87.pdf
  9. */
  10. #include <linux/net.h>
  11. #include "ar-internal.h"
  12. #define RXRPC_RTO_MAX ((unsigned)(120 * HZ))
  13. #define RXRPC_TIMEOUT_INIT ((unsigned)(1*HZ)) /* RFC6298 2.1 initial RTO value */
  14. #define rxrpc_jiffies32 ((u32)jiffies) /* As rxrpc_jiffies32 */
  15. static u32 rxrpc_rto_min_us(struct rxrpc_peer *peer)
  16. {
  17. return 200;
  18. }
  19. static u32 __rxrpc_set_rto(const struct rxrpc_peer *peer)
  20. {
  21. return usecs_to_jiffies((peer->srtt_us >> 3) + peer->rttvar_us);
  22. }
  23. static u32 rxrpc_bound_rto(u32 rto)
  24. {
  25. return min(rto, RXRPC_RTO_MAX);
  26. }
  27. /*
  28. * Called to compute a smoothed rtt estimate. The data fed to this
  29. * routine either comes from timestamps, or from segments that were
  30. * known _not_ to have been retransmitted [see Karn/Partridge
  31. * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88
  32. * piece by Van Jacobson.
  33. * NOTE: the next three routines used to be one big routine.
  34. * To save cycles in the RFC 1323 implementation it was better to break
  35. * it up into three procedures. -- erics
  36. */
  37. static void rxrpc_rtt_estimator(struct rxrpc_peer *peer, long sample_rtt_us)
  38. {
  39. long m = sample_rtt_us; /* RTT */
  40. u32 srtt = peer->srtt_us;
  41. /* The following amusing code comes from Jacobson's
  42. * article in SIGCOMM '88. Note that rtt and mdev
  43. * are scaled versions of rtt and mean deviation.
  44. * This is designed to be as fast as possible
  45. * m stands for "measurement".
  46. *
  47. * On a 1990 paper the rto value is changed to:
  48. * RTO = rtt + 4 * mdev
  49. *
  50. * Funny. This algorithm seems to be very broken.
  51. * These formulae increase RTO, when it should be decreased, increase
  52. * too slowly, when it should be increased quickly, decrease too quickly
  53. * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
  54. * does not matter how to _calculate_ it. Seems, it was trap
  55. * that VJ failed to avoid. 8)
  56. */
  57. if (srtt != 0) {
  58. m -= (srtt >> 3); /* m is now error in rtt est */
  59. srtt += m; /* rtt = 7/8 rtt + 1/8 new */
  60. if (m < 0) {
  61. m = -m; /* m is now abs(error) */
  62. m -= (peer->mdev_us >> 2); /* similar update on mdev */
  63. /* This is similar to one of Eifel findings.
  64. * Eifel blocks mdev updates when rtt decreases.
  65. * This solution is a bit different: we use finer gain
  66. * for mdev in this case (alpha*beta).
  67. * Like Eifel it also prevents growth of rto,
  68. * but also it limits too fast rto decreases,
  69. * happening in pure Eifel.
  70. */
  71. if (m > 0)
  72. m >>= 3;
  73. } else {
  74. m -= (peer->mdev_us >> 2); /* similar update on mdev */
  75. }
  76. peer->mdev_us += m; /* mdev = 3/4 mdev + 1/4 new */
  77. if (peer->mdev_us > peer->mdev_max_us) {
  78. peer->mdev_max_us = peer->mdev_us;
  79. if (peer->mdev_max_us > peer->rttvar_us)
  80. peer->rttvar_us = peer->mdev_max_us;
  81. }
  82. } else {
  83. /* no previous measure. */
  84. srtt = m << 3; /* take the measured time to be rtt */
  85. peer->mdev_us = m << 1; /* make sure rto = 3*rtt */
  86. peer->rttvar_us = max(peer->mdev_us, rxrpc_rto_min_us(peer));
  87. peer->mdev_max_us = peer->rttvar_us;
  88. }
  89. peer->srtt_us = max(1U, srtt);
  90. }
  91. /*
  92. * Calculate rto without backoff. This is the second half of Van Jacobson's
  93. * routine referred to above.
  94. */
  95. static void rxrpc_set_rto(struct rxrpc_peer *peer)
  96. {
  97. u32 rto;
  98. /* 1. If rtt variance happened to be less 50msec, it is hallucination.
  99. * It cannot be less due to utterly erratic ACK generation made
  100. * at least by solaris and freebsd. "Erratic ACKs" has _nothing_
  101. * to do with delayed acks, because at cwnd>2 true delack timeout
  102. * is invisible. Actually, Linux-2.4 also generates erratic
  103. * ACKs in some circumstances.
  104. */
  105. rto = __rxrpc_set_rto(peer);
  106. /* 2. Fixups made earlier cannot be right.
  107. * If we do not estimate RTO correctly without them,
  108. * all the algo is pure shit and should be replaced
  109. * with correct one. It is exactly, which we pretend to do.
  110. */
  111. /* NOTE: clamping at RXRPC_RTO_MIN is not required, current algo
  112. * guarantees that rto is higher.
  113. */
  114. peer->rto_j = rxrpc_bound_rto(rto);
  115. }
  116. static void rxrpc_ack_update_rtt(struct rxrpc_peer *peer, long rtt_us)
  117. {
  118. if (rtt_us < 0)
  119. return;
  120. //rxrpc_update_rtt_min(peer, rtt_us);
  121. rxrpc_rtt_estimator(peer, rtt_us);
  122. rxrpc_set_rto(peer);
  123. /* RFC6298: only reset backoff on valid RTT measurement. */
  124. peer->backoff = 0;
  125. }
  126. /*
  127. * Add RTT information to cache. This is called in softirq mode and has
  128. * exclusive access to the peer RTT data.
  129. */
  130. void rxrpc_peer_add_rtt(struct rxrpc_call *call, enum rxrpc_rtt_rx_trace why,
  131. int rtt_slot,
  132. rxrpc_serial_t send_serial, rxrpc_serial_t resp_serial,
  133. ktime_t send_time, ktime_t resp_time)
  134. {
  135. struct rxrpc_peer *peer = call->peer;
  136. s64 rtt_us;
  137. rtt_us = ktime_to_us(ktime_sub(resp_time, send_time));
  138. if (rtt_us < 0)
  139. return;
  140. spin_lock(&peer->rtt_input_lock);
  141. rxrpc_ack_update_rtt(peer, rtt_us);
  142. if (peer->rtt_count < 3)
  143. peer->rtt_count++;
  144. spin_unlock(&peer->rtt_input_lock);
  145. trace_rxrpc_rtt_rx(call, why, rtt_slot, send_serial, resp_serial,
  146. peer->srtt_us >> 3, peer->rto_j);
  147. }
  148. /*
  149. * Get the retransmission timeout to set in jiffies, backing it off each time
  150. * we retransmit.
  151. */
  152. unsigned long rxrpc_get_rto_backoff(struct rxrpc_peer *peer, bool retrans)
  153. {
  154. u64 timo_j;
  155. u8 backoff = READ_ONCE(peer->backoff);
  156. timo_j = peer->rto_j;
  157. timo_j <<= backoff;
  158. if (retrans && timo_j * 2 <= RXRPC_RTO_MAX)
  159. WRITE_ONCE(peer->backoff, backoff + 1);
  160. if (timo_j < 1)
  161. timo_j = 1;
  162. return timo_j;
  163. }
  164. void rxrpc_peer_init_rtt(struct rxrpc_peer *peer)
  165. {
  166. peer->rto_j = RXRPC_TIMEOUT_INIT;
  167. peer->mdev_us = jiffies_to_usecs(RXRPC_TIMEOUT_INIT);
  168. peer->backoff = 0;
  169. //minmax_reset(&peer->rtt_min, rxrpc_jiffies32, ~0U);
  170. }