tcp_nv.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * TCP NV: TCP with Congestion Avoidance
  4. *
  5. * TCP-NV is a successor of TCP-Vegas that has been developed to
  6. * deal with the issues that occur in modern networks.
  7. * Like TCP-Vegas, TCP-NV supports true congestion avoidance,
  8. * the ability to detect congestion before packet losses occur.
  9. * When congestion (queue buildup) starts to occur, TCP-NV
  10. * predicts what the cwnd size should be for the current
  11. * throughput and it reduces the cwnd proportionally to
  12. * the difference between the current cwnd and the predicted cwnd.
  13. *
  14. * NV is only recommeneded for traffic within a data center, and when
  15. * all the flows are NV (at least those within the data center). This
  16. * is due to the inherent unfairness between flows using losses to
  17. * detect congestion (congestion control) and those that use queue
  18. * buildup to detect congestion (congestion avoidance).
  19. *
  20. * Note: High NIC coalescence values may lower the performance of NV
  21. * due to the increased noise in RTT values. In particular, we have
  22. * seen issues with rx-frames values greater than 8.
  23. *
  24. * TODO:
  25. * 1) Add mechanism to deal with reverse congestion.
  26. */
  27. #include <linux/mm.h>
  28. #include <linux/module.h>
  29. #include <linux/math64.h>
  30. #include <net/tcp.h>
  31. #include <linux/inet_diag.h>
  32. /* TCP NV parameters
  33. *
  34. * nv_pad Max number of queued packets allowed in network
  35. * nv_pad_buffer Do not grow cwnd if this closed to nv_pad
  36. * nv_reset_period How often (in) seconds)to reset min_rtt
  37. * nv_min_cwnd Don't decrease cwnd below this if there are no losses
  38. * nv_cong_dec_mult Decrease cwnd by X% (30%) of congestion when detected
  39. * nv_ssthresh_factor On congestion set ssthresh to this * <desired cwnd> / 8
  40. * nv_rtt_factor RTT averaging factor
  41. * nv_loss_dec_factor Decrease cwnd to this (80%) when losses occur
  42. * nv_dec_eval_min_calls Wait this many RTT measurements before dec cwnd
  43. * nv_inc_eval_min_calls Wait this many RTT measurements before inc cwnd
  44. * nv_ssthresh_eval_min_calls Wait this many RTT measurements before stopping
  45. * slow-start due to congestion
  46. * nv_stop_rtt_cnt Only grow cwnd for this many RTTs after non-congestion
  47. * nv_rtt_min_cnt Wait these many RTTs before making congesion decision
  48. * nv_cwnd_growth_rate_neg
  49. * nv_cwnd_growth_rate_pos
  50. * How quickly to double growth rate (not rate) of cwnd when not
  51. * congested. One value (nv_cwnd_growth_rate_neg) for when
  52. * rate < 1 pkt/RTT (after losses). The other (nv_cwnd_growth_rate_pos)
  53. * otherwise.
  54. */
  55. static int nv_pad __read_mostly = 10;
  56. static int nv_pad_buffer __read_mostly = 2;
  57. static int nv_reset_period __read_mostly = 5; /* in seconds */
  58. static int nv_min_cwnd __read_mostly = 2;
  59. static int nv_cong_dec_mult __read_mostly = 30 * 128 / 100; /* = 30% */
  60. static int nv_ssthresh_factor __read_mostly = 8; /* = 1 */
  61. static int nv_rtt_factor __read_mostly = 128; /* = 1/2*old + 1/2*new */
  62. static int nv_loss_dec_factor __read_mostly = 819; /* => 80% */
  63. static int nv_cwnd_growth_rate_neg __read_mostly = 8;
  64. static int nv_cwnd_growth_rate_pos __read_mostly; /* 0 => fixed like Reno */
  65. static int nv_dec_eval_min_calls __read_mostly = 60;
  66. static int nv_inc_eval_min_calls __read_mostly = 20;
  67. static int nv_ssthresh_eval_min_calls __read_mostly = 30;
  68. static int nv_stop_rtt_cnt __read_mostly = 10;
  69. static int nv_rtt_min_cnt __read_mostly = 2;
  70. module_param(nv_pad, int, 0644);
  71. MODULE_PARM_DESC(nv_pad, "max queued packets allowed in network");
  72. module_param(nv_reset_period, int, 0644);
  73. MODULE_PARM_DESC(nv_reset_period, "nv_min_rtt reset period (secs)");
  74. module_param(nv_min_cwnd, int, 0644);
  75. MODULE_PARM_DESC(nv_min_cwnd, "NV will not decrease cwnd below this value"
  76. " without losses");
  77. /* TCP NV Parameters */
  78. struct tcpnv {
  79. unsigned long nv_min_rtt_reset_jiffies; /* when to switch to
  80. * nv_min_rtt_new */
  81. s8 cwnd_growth_factor; /* Current cwnd growth factor,
  82. * < 0 => less than 1 packet/RTT */
  83. u8 available8;
  84. u16 available16;
  85. u8 nv_allow_cwnd_growth:1, /* whether cwnd can grow */
  86. nv_reset:1, /* whether to reset values */
  87. nv_catchup:1; /* whether we are growing because
  88. * of temporary cwnd decrease */
  89. u8 nv_eval_call_cnt; /* call count since last eval */
  90. u8 nv_min_cwnd; /* nv won't make a ca decision if cwnd is
  91. * smaller than this. It may grow to handle
  92. * TSO, LRO and interrupt coalescence because
  93. * with these a small cwnd cannot saturate
  94. * the link. Note that this is different from
  95. * the file local nv_min_cwnd */
  96. u8 nv_rtt_cnt; /* RTTs without making ca decision */;
  97. u32 nv_last_rtt; /* last rtt */
  98. u32 nv_min_rtt; /* active min rtt. Used to determine slope */
  99. u32 nv_min_rtt_new; /* min rtt for future use */
  100. u32 nv_base_rtt; /* If non-zero it represents the threshold for
  101. * congestion */
  102. u32 nv_lower_bound_rtt; /* Used in conjunction with nv_base_rtt. It is
  103. * set to 80% of nv_base_rtt. It helps reduce
  104. * unfairness between flows */
  105. u32 nv_rtt_max_rate; /* max rate seen during current RTT */
  106. u32 nv_rtt_start_seq; /* current RTT ends when packet arrives
  107. * acking beyond nv_rtt_start_seq */
  108. u32 nv_last_snd_una; /* Previous value of tp->snd_una. It is
  109. * used to determine bytes acked since last
  110. * call to bictcp_acked */
  111. u32 nv_no_cong_cnt; /* Consecutive no congestion decisions */
  112. };
  113. #define NV_INIT_RTT U32_MAX
  114. #define NV_MIN_CWND 4
  115. #define NV_MIN_CWND_GROW 2
  116. #define NV_TSO_CWND_BOUND 80
  117. static inline void tcpnv_reset(struct tcpnv *ca, struct sock *sk)
  118. {
  119. struct tcp_sock *tp = tcp_sk(sk);
  120. ca->nv_reset = 0;
  121. ca->nv_no_cong_cnt = 0;
  122. ca->nv_rtt_cnt = 0;
  123. ca->nv_last_rtt = 0;
  124. ca->nv_rtt_max_rate = 0;
  125. ca->nv_rtt_start_seq = tp->snd_una;
  126. ca->nv_eval_call_cnt = 0;
  127. ca->nv_last_snd_una = tp->snd_una;
  128. }
  129. static void tcpnv_init(struct sock *sk)
  130. {
  131. struct tcpnv *ca = inet_csk_ca(sk);
  132. int base_rtt;
  133. tcpnv_reset(ca, sk);
  134. /* See if base_rtt is available from socket_ops bpf program.
  135. * It is meant to be used in environments, such as communication
  136. * within a datacenter, where we have reasonable estimates of
  137. * RTTs
  138. */
  139. base_rtt = tcp_call_bpf(sk, BPF_SOCK_OPS_BASE_RTT, 0, NULL);
  140. if (base_rtt > 0) {
  141. ca->nv_base_rtt = base_rtt;
  142. ca->nv_lower_bound_rtt = (base_rtt * 205) >> 8; /* 80% */
  143. } else {
  144. ca->nv_base_rtt = 0;
  145. ca->nv_lower_bound_rtt = 0;
  146. }
  147. ca->nv_allow_cwnd_growth = 1;
  148. ca->nv_min_rtt_reset_jiffies = jiffies + 2 * HZ;
  149. ca->nv_min_rtt = NV_INIT_RTT;
  150. ca->nv_min_rtt_new = NV_INIT_RTT;
  151. ca->nv_min_cwnd = NV_MIN_CWND;
  152. ca->nv_catchup = 0;
  153. ca->cwnd_growth_factor = 0;
  154. }
  155. /* If provided, apply upper (base_rtt) and lower (lower_bound_rtt)
  156. * bounds to RTT.
  157. */
  158. inline u32 nv_get_bounded_rtt(struct tcpnv *ca, u32 val)
  159. {
  160. if (ca->nv_lower_bound_rtt > 0 && val < ca->nv_lower_bound_rtt)
  161. return ca->nv_lower_bound_rtt;
  162. else if (ca->nv_base_rtt > 0 && val > ca->nv_base_rtt)
  163. return ca->nv_base_rtt;
  164. else
  165. return val;
  166. }
  167. static void tcpnv_cong_avoid(struct sock *sk, u32 ack, u32 acked)
  168. {
  169. struct tcp_sock *tp = tcp_sk(sk);
  170. struct tcpnv *ca = inet_csk_ca(sk);
  171. u32 cnt;
  172. if (!tcp_is_cwnd_limited(sk))
  173. return;
  174. /* Only grow cwnd if NV has not detected congestion */
  175. if (!ca->nv_allow_cwnd_growth)
  176. return;
  177. if (tcp_in_slow_start(tp)) {
  178. acked = tcp_slow_start(tp, acked);
  179. if (!acked)
  180. return;
  181. }
  182. if (ca->cwnd_growth_factor < 0) {
  183. cnt = tp->snd_cwnd << -ca->cwnd_growth_factor;
  184. tcp_cong_avoid_ai(tp, cnt, acked);
  185. } else {
  186. cnt = max(4U, tp->snd_cwnd >> ca->cwnd_growth_factor);
  187. tcp_cong_avoid_ai(tp, cnt, acked);
  188. }
  189. }
  190. static u32 tcpnv_recalc_ssthresh(struct sock *sk)
  191. {
  192. const struct tcp_sock *tp = tcp_sk(sk);
  193. return max((tp->snd_cwnd * nv_loss_dec_factor) >> 10, 2U);
  194. }
  195. static void tcpnv_state(struct sock *sk, u8 new_state)
  196. {
  197. struct tcpnv *ca = inet_csk_ca(sk);
  198. if (new_state == TCP_CA_Open && ca->nv_reset) {
  199. tcpnv_reset(ca, sk);
  200. } else if (new_state == TCP_CA_Loss || new_state == TCP_CA_CWR ||
  201. new_state == TCP_CA_Recovery) {
  202. ca->nv_reset = 1;
  203. ca->nv_allow_cwnd_growth = 0;
  204. if (new_state == TCP_CA_Loss) {
  205. /* Reset cwnd growth factor to Reno value */
  206. if (ca->cwnd_growth_factor > 0)
  207. ca->cwnd_growth_factor = 0;
  208. /* Decrease growth rate if allowed */
  209. if (nv_cwnd_growth_rate_neg > 0 &&
  210. ca->cwnd_growth_factor > -8)
  211. ca->cwnd_growth_factor--;
  212. }
  213. }
  214. }
  215. /* Do congestion avoidance calculations for TCP-NV
  216. */
  217. static void tcpnv_acked(struct sock *sk, const struct ack_sample *sample)
  218. {
  219. const struct inet_connection_sock *icsk = inet_csk(sk);
  220. struct tcp_sock *tp = tcp_sk(sk);
  221. struct tcpnv *ca = inet_csk_ca(sk);
  222. unsigned long now = jiffies;
  223. u64 rate64;
  224. u32 rate, max_win, cwnd_by_slope;
  225. u32 avg_rtt;
  226. u32 bytes_acked = 0;
  227. /* Some calls are for duplicates without timetamps */
  228. if (sample->rtt_us < 0)
  229. return;
  230. /* If not in TCP_CA_Open or TCP_CA_Disorder states, skip. */
  231. if (icsk->icsk_ca_state != TCP_CA_Open &&
  232. icsk->icsk_ca_state != TCP_CA_Disorder)
  233. return;
  234. /* Stop cwnd growth if we were in catch up mode */
  235. if (ca->nv_catchup && tp->snd_cwnd >= nv_min_cwnd) {
  236. ca->nv_catchup = 0;
  237. ca->nv_allow_cwnd_growth = 0;
  238. }
  239. bytes_acked = tp->snd_una - ca->nv_last_snd_una;
  240. ca->nv_last_snd_una = tp->snd_una;
  241. if (sample->in_flight == 0)
  242. return;
  243. /* Calculate moving average of RTT */
  244. if (nv_rtt_factor > 0) {
  245. if (ca->nv_last_rtt > 0) {
  246. avg_rtt = (((u64)sample->rtt_us) * nv_rtt_factor +
  247. ((u64)ca->nv_last_rtt)
  248. * (256 - nv_rtt_factor)) >> 8;
  249. } else {
  250. avg_rtt = sample->rtt_us;
  251. ca->nv_min_rtt = avg_rtt << 1;
  252. }
  253. ca->nv_last_rtt = avg_rtt;
  254. } else {
  255. avg_rtt = sample->rtt_us;
  256. }
  257. /* rate in 100's bits per second */
  258. rate64 = ((u64)sample->in_flight) * 80000;
  259. do_div(rate64, avg_rtt ?: 1);
  260. rate = (u32)rate64;
  261. /* Remember the maximum rate seen during this RTT
  262. * Note: It may be more than one RTT. This function should be
  263. * called at least nv_dec_eval_min_calls times.
  264. */
  265. if (ca->nv_rtt_max_rate < rate)
  266. ca->nv_rtt_max_rate = rate;
  267. /* We have valid information, increment counter */
  268. if (ca->nv_eval_call_cnt < 255)
  269. ca->nv_eval_call_cnt++;
  270. /* Apply bounds to rtt. Only used to update min_rtt */
  271. avg_rtt = nv_get_bounded_rtt(ca, avg_rtt);
  272. /* update min rtt if necessary */
  273. if (avg_rtt < ca->nv_min_rtt)
  274. ca->nv_min_rtt = avg_rtt;
  275. /* update future min_rtt if necessary */
  276. if (avg_rtt < ca->nv_min_rtt_new)
  277. ca->nv_min_rtt_new = avg_rtt;
  278. /* nv_min_rtt is updated with the minimum (possibley averaged) rtt
  279. * seen in the last sysctl_tcp_nv_reset_period seconds (i.e. a
  280. * warm reset). This new nv_min_rtt will be continued to be updated
  281. * and be used for another sysctl_tcp_nv_reset_period seconds,
  282. * when it will be updated again.
  283. * In practice we introduce some randomness, so the actual period used
  284. * is chosen randomly from the range:
  285. * [sysctl_tcp_nv_reset_period*3/4, sysctl_tcp_nv_reset_period*5/4)
  286. */
  287. if (time_after_eq(now, ca->nv_min_rtt_reset_jiffies)) {
  288. unsigned char rand;
  289. ca->nv_min_rtt = ca->nv_min_rtt_new;
  290. ca->nv_min_rtt_new = NV_INIT_RTT;
  291. get_random_bytes(&rand, 1);
  292. ca->nv_min_rtt_reset_jiffies =
  293. now + ((nv_reset_period * (384 + rand) * HZ) >> 9);
  294. /* Every so often we decrease ca->nv_min_cwnd in case previous
  295. * value is no longer accurate.
  296. */
  297. ca->nv_min_cwnd = max(ca->nv_min_cwnd / 2, NV_MIN_CWND);
  298. }
  299. /* Once per RTT check if we need to do congestion avoidance */
  300. if (before(ca->nv_rtt_start_seq, tp->snd_una)) {
  301. ca->nv_rtt_start_seq = tp->snd_nxt;
  302. if (ca->nv_rtt_cnt < 0xff)
  303. /* Increase counter for RTTs without CA decision */
  304. ca->nv_rtt_cnt++;
  305. /* If this function is only called once within an RTT
  306. * the cwnd is probably too small (in some cases due to
  307. * tso, lro or interrupt coalescence), so we increase
  308. * ca->nv_min_cwnd.
  309. */
  310. if (ca->nv_eval_call_cnt == 1 &&
  311. bytes_acked >= (ca->nv_min_cwnd - 1) * tp->mss_cache &&
  312. ca->nv_min_cwnd < (NV_TSO_CWND_BOUND + 1)) {
  313. ca->nv_min_cwnd = min(ca->nv_min_cwnd
  314. + NV_MIN_CWND_GROW,
  315. NV_TSO_CWND_BOUND + 1);
  316. ca->nv_rtt_start_seq = tp->snd_nxt +
  317. ca->nv_min_cwnd * tp->mss_cache;
  318. ca->nv_eval_call_cnt = 0;
  319. ca->nv_allow_cwnd_growth = 1;
  320. return;
  321. }
  322. /* Find the ideal cwnd for current rate from slope
  323. * slope = 80000.0 * mss / nv_min_rtt
  324. * cwnd_by_slope = nv_rtt_max_rate / slope
  325. */
  326. cwnd_by_slope = (u32)
  327. div64_u64(((u64)ca->nv_rtt_max_rate) * ca->nv_min_rtt,
  328. 80000ULL * tp->mss_cache);
  329. max_win = cwnd_by_slope + nv_pad;
  330. /* If cwnd > max_win, decrease cwnd
  331. * if cwnd < max_win, grow cwnd
  332. * else leave the same
  333. */
  334. if (tp->snd_cwnd > max_win) {
  335. /* there is congestion, check that it is ok
  336. * to make a CA decision
  337. * 1. We should have at least nv_dec_eval_min_calls
  338. * data points before making a CA decision
  339. * 2. We only make a congesion decision after
  340. * nv_rtt_min_cnt RTTs
  341. */
  342. if (ca->nv_rtt_cnt < nv_rtt_min_cnt) {
  343. return;
  344. } else if (tp->snd_ssthresh == TCP_INFINITE_SSTHRESH) {
  345. if (ca->nv_eval_call_cnt <
  346. nv_ssthresh_eval_min_calls)
  347. return;
  348. /* otherwise we will decrease cwnd */
  349. } else if (ca->nv_eval_call_cnt <
  350. nv_dec_eval_min_calls) {
  351. if (ca->nv_allow_cwnd_growth &&
  352. ca->nv_rtt_cnt > nv_stop_rtt_cnt)
  353. ca->nv_allow_cwnd_growth = 0;
  354. return;
  355. }
  356. /* We have enough data to determine we are congested */
  357. ca->nv_allow_cwnd_growth = 0;
  358. tp->snd_ssthresh =
  359. (nv_ssthresh_factor * max_win) >> 3;
  360. if (tp->snd_cwnd - max_win > 2) {
  361. /* gap > 2, we do exponential cwnd decrease */
  362. int dec;
  363. dec = max(2U, ((tp->snd_cwnd - max_win) *
  364. nv_cong_dec_mult) >> 7);
  365. tp->snd_cwnd -= dec;
  366. } else if (nv_cong_dec_mult > 0) {
  367. tp->snd_cwnd = max_win;
  368. }
  369. if (ca->cwnd_growth_factor > 0)
  370. ca->cwnd_growth_factor = 0;
  371. ca->nv_no_cong_cnt = 0;
  372. } else if (tp->snd_cwnd <= max_win - nv_pad_buffer) {
  373. /* There is no congestion, grow cwnd if allowed*/
  374. if (ca->nv_eval_call_cnt < nv_inc_eval_min_calls)
  375. return;
  376. ca->nv_allow_cwnd_growth = 1;
  377. ca->nv_no_cong_cnt++;
  378. if (ca->cwnd_growth_factor < 0 &&
  379. nv_cwnd_growth_rate_neg > 0 &&
  380. ca->nv_no_cong_cnt > nv_cwnd_growth_rate_neg) {
  381. ca->cwnd_growth_factor++;
  382. ca->nv_no_cong_cnt = 0;
  383. } else if (ca->cwnd_growth_factor >= 0 &&
  384. nv_cwnd_growth_rate_pos > 0 &&
  385. ca->nv_no_cong_cnt >
  386. nv_cwnd_growth_rate_pos) {
  387. ca->cwnd_growth_factor++;
  388. ca->nv_no_cong_cnt = 0;
  389. }
  390. } else {
  391. /* cwnd is in-between, so do nothing */
  392. return;
  393. }
  394. /* update state */
  395. ca->nv_eval_call_cnt = 0;
  396. ca->nv_rtt_cnt = 0;
  397. ca->nv_rtt_max_rate = 0;
  398. /* Don't want to make cwnd < nv_min_cwnd
  399. * (it wasn't before, if it is now is because nv
  400. * decreased it).
  401. */
  402. if (tp->snd_cwnd < nv_min_cwnd)
  403. tp->snd_cwnd = nv_min_cwnd;
  404. }
  405. }
  406. /* Extract info for Tcp socket info provided via netlink */
  407. static size_t tcpnv_get_info(struct sock *sk, u32 ext, int *attr,
  408. union tcp_cc_info *info)
  409. {
  410. const struct tcpnv *ca = inet_csk_ca(sk);
  411. if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
  412. info->vegas.tcpv_enabled = 1;
  413. info->vegas.tcpv_rttcnt = ca->nv_rtt_cnt;
  414. info->vegas.tcpv_rtt = ca->nv_last_rtt;
  415. info->vegas.tcpv_minrtt = ca->nv_min_rtt;
  416. *attr = INET_DIAG_VEGASINFO;
  417. return sizeof(struct tcpvegas_info);
  418. }
  419. return 0;
  420. }
  421. static struct tcp_congestion_ops tcpnv __read_mostly = {
  422. .init = tcpnv_init,
  423. .ssthresh = tcpnv_recalc_ssthresh,
  424. .cong_avoid = tcpnv_cong_avoid,
  425. .set_state = tcpnv_state,
  426. .undo_cwnd = tcp_reno_undo_cwnd,
  427. .pkts_acked = tcpnv_acked,
  428. .get_info = tcpnv_get_info,
  429. .owner = THIS_MODULE,
  430. .name = "nv",
  431. };
  432. static int __init tcpnv_register(void)
  433. {
  434. BUILD_BUG_ON(sizeof(struct tcpnv) > ICSK_CA_PRIV_SIZE);
  435. return tcp_register_congestion_control(&tcpnv);
  436. }
  437. static void __exit tcpnv_unregister(void)
  438. {
  439. tcp_unregister_congestion_control(&tcpnv);
  440. }
  441. module_init(tcpnv_register);
  442. module_exit(tcpnv_unregister);
  443. MODULE_AUTHOR("Lawrence Brakmo");
  444. MODULE_LICENSE("GPL");
  445. MODULE_DESCRIPTION("TCP NV");
  446. MODULE_VERSION("1.0");