ccid2.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720
  1. /*
  2. * Copyright (c) 2005, 2006 Andrea Bittau <a.bittau@cs.ucl.ac.uk>
  3. *
  4. * Changes to meet Linux coding standards, and DCCP infrastructure fixes.
  5. *
  6. * Copyright (c) 2006 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
  7. *
  8. * This program is free software; you can redistribute it and/or modify
  9. * it under the terms of the GNU General Public License as published by
  10. * the Free Software Foundation; either version 2 of the License, or
  11. * (at your option) any later version.
  12. *
  13. * This program is distributed in the hope that it will be useful,
  14. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16. * GNU General Public License for more details.
  17. *
  18. * You should have received a copy of the GNU General Public License
  19. * along with this program; if not, write to the Free Software
  20. * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21. */
  22. /*
  23. * This implementation should follow RFC 4341
  24. */
  25. #include <linux/slab.h>
  26. #include "../feat.h"
  27. #include "../ccid.h"
  28. #include "../dccp.h"
  29. #include "ccid2.h"
  30. #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
  31. static int ccid2_debug;
  32. #define ccid2_pr_debug(format, a...) DCCP_PR_DEBUG(ccid2_debug, format, ##a)
  33. #else
  34. #define ccid2_pr_debug(format, a...)
  35. #endif
  36. static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock *hc)
  37. {
  38. struct ccid2_seq *seqp;
  39. int i;
  40. /* check if we have space to preserve the pointer to the buffer */
  41. if (hc->tx_seqbufc >= (sizeof(hc->tx_seqbuf) /
  42. sizeof(struct ccid2_seq *)))
  43. return -ENOMEM;
  44. /* allocate buffer and initialize linked list */
  45. seqp = kmalloc(CCID2_SEQBUF_LEN * sizeof(struct ccid2_seq), gfp_any());
  46. if (seqp == NULL)
  47. return -ENOMEM;
  48. for (i = 0; i < (CCID2_SEQBUF_LEN - 1); i++) {
  49. seqp[i].ccid2s_next = &seqp[i + 1];
  50. seqp[i + 1].ccid2s_prev = &seqp[i];
  51. }
  52. seqp[CCID2_SEQBUF_LEN - 1].ccid2s_next = seqp;
  53. seqp->ccid2s_prev = &seqp[CCID2_SEQBUF_LEN - 1];
  54. /* This is the first allocation. Initiate the head and tail. */
  55. if (hc->tx_seqbufc == 0)
  56. hc->tx_seqh = hc->tx_seqt = seqp;
  57. else {
  58. /* link the existing list with the one we just created */
  59. hc->tx_seqh->ccid2s_next = seqp;
  60. seqp->ccid2s_prev = hc->tx_seqh;
  61. hc->tx_seqt->ccid2s_prev = &seqp[CCID2_SEQBUF_LEN - 1];
  62. seqp[CCID2_SEQBUF_LEN - 1].ccid2s_next = hc->tx_seqt;
  63. }
  64. /* store the original pointer to the buffer so we can free it */
  65. hc->tx_seqbuf[hc->tx_seqbufc] = seqp;
  66. hc->tx_seqbufc++;
  67. return 0;
  68. }
  69. static int ccid2_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb)
  70. {
  71. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  72. if (hc->tx_pipe < hc->tx_cwnd)
  73. return 0;
  74. return 1; /* XXX CCID should dequeue when ready instead of polling */
  75. }
  76. static void ccid2_change_l_ack_ratio(struct sock *sk, u32 val)
  77. {
  78. struct dccp_sock *dp = dccp_sk(sk);
  79. u32 max_ratio = DIV_ROUND_UP(ccid2_hc_tx_sk(sk)->tx_cwnd, 2);
  80. /*
  81. * Ensure that Ack Ratio does not exceed ceil(cwnd/2), which is (2) from
  82. * RFC 4341, 6.1.2. We ignore the statement that Ack Ratio 2 is always
  83. * acceptable since this causes starvation/deadlock whenever cwnd < 2.
  84. * The same problem arises when Ack Ratio is 0 (ie. Ack Ratio disabled).
  85. */
  86. if (val == 0 || val > max_ratio) {
  87. DCCP_WARN("Limiting Ack Ratio (%u) to %u\n", val, max_ratio);
  88. val = max_ratio;
  89. }
  90. if (val > DCCPF_ACK_RATIO_MAX)
  91. val = DCCPF_ACK_RATIO_MAX;
  92. if (val == dp->dccps_l_ack_ratio)
  93. return;
  94. ccid2_pr_debug("changing local ack ratio to %u\n", val);
  95. dp->dccps_l_ack_ratio = val;
  96. }
  97. static void ccid2_change_srtt(struct ccid2_hc_tx_sock *hc, long val)
  98. {
  99. ccid2_pr_debug("change SRTT to %ld\n", val);
  100. hc->tx_srtt = val;
  101. }
  102. static void ccid2_start_rto_timer(struct sock *sk);
  103. static void ccid2_hc_tx_rto_expire(unsigned long data)
  104. {
  105. struct sock *sk = (struct sock *)data;
  106. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  107. long s;
  108. bh_lock_sock(sk);
  109. if (sock_owned_by_user(sk)) {
  110. sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + HZ / 5);
  111. goto out;
  112. }
  113. ccid2_pr_debug("RTO_EXPIRE\n");
  114. /* back-off timer */
  115. hc->tx_rto <<= 1;
  116. s = hc->tx_rto / HZ;
  117. if (s > 60)
  118. hc->tx_rto = 60 * HZ;
  119. ccid2_start_rto_timer(sk);
  120. /* adjust pipe, cwnd etc */
  121. hc->tx_ssthresh = hc->tx_cwnd / 2;
  122. if (hc->tx_ssthresh < 2)
  123. hc->tx_ssthresh = 2;
  124. hc->tx_cwnd = 1;
  125. hc->tx_pipe = 0;
  126. /* clear state about stuff we sent */
  127. hc->tx_seqt = hc->tx_seqh;
  128. hc->tx_packets_acked = 0;
  129. /* clear ack ratio state. */
  130. hc->tx_rpseq = 0;
  131. hc->tx_rpdupack = -1;
  132. ccid2_change_l_ack_ratio(sk, 1);
  133. out:
  134. bh_unlock_sock(sk);
  135. sock_put(sk);
  136. }
  137. static void ccid2_start_rto_timer(struct sock *sk)
  138. {
  139. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  140. ccid2_pr_debug("setting RTO timeout=%ld\n", hc->tx_rto);
  141. BUG_ON(timer_pending(&hc->tx_rtotimer));
  142. sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto);
  143. }
  144. static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len)
  145. {
  146. struct dccp_sock *dp = dccp_sk(sk);
  147. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  148. struct ccid2_seq *next;
  149. hc->tx_pipe++;
  150. hc->tx_seqh->ccid2s_seq = dp->dccps_gss;
  151. hc->tx_seqh->ccid2s_acked = 0;
  152. hc->tx_seqh->ccid2s_sent = jiffies;
  153. next = hc->tx_seqh->ccid2s_next;
  154. /* check if we need to alloc more space */
  155. if (next == hc->tx_seqt) {
  156. if (ccid2_hc_tx_alloc_seq(hc)) {
  157. DCCP_CRIT("packet history - out of memory!");
  158. /* FIXME: find a more graceful way to bail out */
  159. return;
  160. }
  161. next = hc->tx_seqh->ccid2s_next;
  162. BUG_ON(next == hc->tx_seqt);
  163. }
  164. hc->tx_seqh = next;
  165. ccid2_pr_debug("cwnd=%d pipe=%d\n", hc->tx_cwnd, hc->tx_pipe);
  166. /*
  167. * FIXME: The code below is broken and the variables have been removed
  168. * from the socket struct. The `ackloss' variable was always set to 0,
  169. * and with arsent there are several problems:
  170. * (i) it doesn't just count the number of Acks, but all sent packets;
  171. * (ii) it is expressed in # of packets, not # of windows, so the
  172. * comparison below uses the wrong formula: Appendix A of RFC 4341
  173. * comes up with the number K = cwnd / (R^2 - R) of consecutive windows
  174. * of data with no lost or marked Ack packets. If arsent were the # of
  175. * consecutive Acks received without loss, then Ack Ratio needs to be
  176. * decreased by 1 when
  177. * arsent >= K * cwnd / R = cwnd^2 / (R^3 - R^2)
  178. * where cwnd / R is the number of Acks received per window of data
  179. * (cf. RFC 4341, App. A). The problems are that
  180. * - arsent counts other packets as well;
  181. * - the comparison uses a formula different from RFC 4341;
  182. * - computing a cubic/quadratic equation each time is too complicated.
  183. * Hence a different algorithm is needed.
  184. */
  185. #if 0
  186. /* Ack Ratio. Need to maintain a concept of how many windows we sent */
  187. hc->tx_arsent++;
  188. /* We had an ack loss in this window... */
  189. if (hc->tx_ackloss) {
  190. if (hc->tx_arsent >= hc->tx_cwnd) {
  191. hc->tx_arsent = 0;
  192. hc->tx_ackloss = 0;
  193. }
  194. } else {
  195. /* No acks lost up to now... */
  196. /* decrease ack ratio if enough packets were sent */
  197. if (dp->dccps_l_ack_ratio > 1) {
  198. /* XXX don't calculate denominator each time */
  199. int denom = dp->dccps_l_ack_ratio * dp->dccps_l_ack_ratio -
  200. dp->dccps_l_ack_ratio;
  201. denom = hc->tx_cwnd * hc->tx_cwnd / denom;
  202. if (hc->tx_arsent >= denom) {
  203. ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio - 1);
  204. hc->tx_arsent = 0;
  205. }
  206. } else {
  207. /* we can't increase ack ratio further [1] */
  208. hc->tx_arsent = 0; /* or maybe set it to cwnd*/
  209. }
  210. }
  211. #endif
  212. /* setup RTO timer */
  213. if (!timer_pending(&hc->tx_rtotimer))
  214. ccid2_start_rto_timer(sk);
  215. #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
  216. do {
  217. struct ccid2_seq *seqp = hc->tx_seqt;
  218. while (seqp != hc->tx_seqh) {
  219. ccid2_pr_debug("out seq=%llu acked=%d time=%lu\n",
  220. (unsigned long long)seqp->ccid2s_seq,
  221. seqp->ccid2s_acked, seqp->ccid2s_sent);
  222. seqp = seqp->ccid2s_next;
  223. }
  224. } while (0);
  225. ccid2_pr_debug("=========\n");
  226. #endif
  227. }
  228. /* XXX Lame code duplication!
  229. * returns -1 if none was found.
  230. * else returns the next offset to use in the function call.
  231. */
  232. static int ccid2_ackvector(struct sock *sk, struct sk_buff *skb, int offset,
  233. unsigned char **vec, unsigned char *veclen)
  234. {
  235. const struct dccp_hdr *dh = dccp_hdr(skb);
  236. unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb);
  237. unsigned char *opt_ptr;
  238. const unsigned char *opt_end = (unsigned char *)dh +
  239. (dh->dccph_doff * 4);
  240. unsigned char opt, len;
  241. unsigned char *value;
  242. BUG_ON(offset < 0);
  243. options += offset;
  244. opt_ptr = options;
  245. if (opt_ptr >= opt_end)
  246. return -1;
  247. while (opt_ptr != opt_end) {
  248. opt = *opt_ptr++;
  249. len = 0;
  250. value = NULL;
  251. /* Check if this isn't a single byte option */
  252. if (opt > DCCPO_MAX_RESERVED) {
  253. if (opt_ptr == opt_end)
  254. goto out_invalid_option;
  255. len = *opt_ptr++;
  256. if (len < 3)
  257. goto out_invalid_option;
  258. /*
  259. * Remove the type and len fields, leaving
  260. * just the value size
  261. */
  262. len -= 2;
  263. value = opt_ptr;
  264. opt_ptr += len;
  265. if (opt_ptr > opt_end)
  266. goto out_invalid_option;
  267. }
  268. switch (opt) {
  269. case DCCPO_ACK_VECTOR_0:
  270. case DCCPO_ACK_VECTOR_1:
  271. *vec = value;
  272. *veclen = len;
  273. return offset + (opt_ptr - options);
  274. }
  275. }
  276. return -1;
  277. out_invalid_option:
  278. DCCP_BUG("Invalid option - this should not happen (previous parsing)!");
  279. return -1;
  280. }
  281. static void ccid2_hc_tx_kill_rto_timer(struct sock *sk)
  282. {
  283. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  284. sk_stop_timer(sk, &hc->tx_rtotimer);
  285. ccid2_pr_debug("deleted RTO timer\n");
  286. }
  287. static inline void ccid2_new_ack(struct sock *sk,
  288. struct ccid2_seq *seqp,
  289. unsigned int *maxincr)
  290. {
  291. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  292. if (hc->tx_cwnd < hc->tx_ssthresh) {
  293. if (*maxincr > 0 && ++hc->tx_packets_acked == 2) {
  294. hc->tx_cwnd += 1;
  295. *maxincr -= 1;
  296. hc->tx_packets_acked = 0;
  297. }
  298. } else if (++hc->tx_packets_acked >= hc->tx_cwnd) {
  299. hc->tx_cwnd += 1;
  300. hc->tx_packets_acked = 0;
  301. }
  302. /* update RTO */
  303. if (hc->tx_srtt == -1 ||
  304. time_after(jiffies, hc->tx_lastrtt + hc->tx_srtt)) {
  305. unsigned long r = (long)jiffies - (long)seqp->ccid2s_sent;
  306. int s;
  307. /* first measurement */
  308. if (hc->tx_srtt == -1) {
  309. ccid2_pr_debug("R: %lu Time=%lu seq=%llu\n",
  310. r, jiffies,
  311. (unsigned long long)seqp->ccid2s_seq);
  312. ccid2_change_srtt(hc, r);
  313. hc->tx_rttvar = r >> 1;
  314. } else {
  315. /* RTTVAR */
  316. long tmp = hc->tx_srtt - r;
  317. long srtt;
  318. if (tmp < 0)
  319. tmp *= -1;
  320. tmp >>= 2;
  321. hc->tx_rttvar *= 3;
  322. hc->tx_rttvar >>= 2;
  323. hc->tx_rttvar += tmp;
  324. /* SRTT */
  325. srtt = hc->tx_srtt;
  326. srtt *= 7;
  327. srtt >>= 3;
  328. tmp = r >> 3;
  329. srtt += tmp;
  330. ccid2_change_srtt(hc, srtt);
  331. }
  332. s = hc->tx_rttvar << 2;
  333. /* clock granularity is 1 when based on jiffies */
  334. if (!s)
  335. s = 1;
  336. hc->tx_rto = hc->tx_srtt + s;
  337. /* must be at least a second */
  338. s = hc->tx_rto / HZ;
  339. /* DCCP doesn't require this [but I like it cuz my code sux] */
  340. #if 1
  341. if (s < 1)
  342. hc->tx_rto = HZ;
  343. #endif
  344. /* max 60 seconds */
  345. if (s > 60)
  346. hc->tx_rto = HZ * 60;
  347. hc->tx_lastrtt = jiffies;
  348. ccid2_pr_debug("srtt: %ld rttvar: %ld rto: %ld (HZ=%d) R=%lu\n",
  349. hc->tx_srtt, hc->tx_rttvar,
  350. hc->tx_rto, HZ, r);
  351. }
  352. }
  353. static void ccid2_congestion_event(struct sock *sk, struct ccid2_seq *seqp)
  354. {
  355. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  356. if (time_before(seqp->ccid2s_sent, hc->tx_last_cong)) {
  357. ccid2_pr_debug("Multiple losses in an RTT---treating as one\n");
  358. return;
  359. }
  360. hc->tx_last_cong = jiffies;
  361. hc->tx_cwnd = hc->tx_cwnd / 2 ? : 1U;
  362. hc->tx_ssthresh = max(hc->tx_cwnd, 2U);
  363. /* Avoid spurious timeouts resulting from Ack Ratio > cwnd */
  364. if (dccp_sk(sk)->dccps_l_ack_ratio > hc->tx_cwnd)
  365. ccid2_change_l_ack_ratio(sk, hc->tx_cwnd);
  366. }
  367. static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
  368. {
  369. struct dccp_sock *dp = dccp_sk(sk);
  370. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  371. u64 ackno, seqno;
  372. struct ccid2_seq *seqp;
  373. unsigned char *vector;
  374. unsigned char veclen;
  375. int offset = 0;
  376. int done = 0;
  377. unsigned int maxincr = 0;
  378. /* check reverse path congestion */
  379. seqno = DCCP_SKB_CB(skb)->dccpd_seq;
  380. /* XXX this whole "algorithm" is broken. Need to fix it to keep track
  381. * of the seqnos of the dupacks so that rpseq and rpdupack are correct
  382. * -sorbo.
  383. */
  384. /* need to bootstrap */
  385. if (hc->tx_rpdupack == -1) {
  386. hc->tx_rpdupack = 0;
  387. hc->tx_rpseq = seqno;
  388. } else {
  389. /* check if packet is consecutive */
  390. if (dccp_delta_seqno(hc->tx_rpseq, seqno) == 1)
  391. hc->tx_rpseq = seqno;
  392. /* it's a later packet */
  393. else if (after48(seqno, hc->tx_rpseq)) {
  394. hc->tx_rpdupack++;
  395. /* check if we got enough dupacks */
  396. if (hc->tx_rpdupack >= NUMDUPACK) {
  397. hc->tx_rpdupack = -1; /* XXX lame */
  398. hc->tx_rpseq = 0;
  399. ccid2_change_l_ack_ratio(sk, 2 * dp->dccps_l_ack_ratio);
  400. }
  401. }
  402. }
  403. /* check forward path congestion */
  404. /* still didn't send out new data packets */
  405. if (hc->tx_seqh == hc->tx_seqt)
  406. return;
  407. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  408. case DCCP_PKT_ACK:
  409. case DCCP_PKT_DATAACK:
  410. break;
  411. default:
  412. return;
  413. }
  414. ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
  415. if (after48(ackno, hc->tx_high_ack))
  416. hc->tx_high_ack = ackno;
  417. seqp = hc->tx_seqt;
  418. while (before48(seqp->ccid2s_seq, ackno)) {
  419. seqp = seqp->ccid2s_next;
  420. if (seqp == hc->tx_seqh) {
  421. seqp = hc->tx_seqh->ccid2s_prev;
  422. break;
  423. }
  424. }
  425. /*
  426. * In slow-start, cwnd can increase up to a maximum of Ack Ratio/2
  427. * packets per acknowledgement. Rounding up avoids that cwnd is not
  428. * advanced when Ack Ratio is 1 and gives a slight edge otherwise.
  429. */
  430. if (hc->tx_cwnd < hc->tx_ssthresh)
  431. maxincr = DIV_ROUND_UP(dp->dccps_l_ack_ratio, 2);
  432. /* go through all ack vectors */
  433. while ((offset = ccid2_ackvector(sk, skb, offset,
  434. &vector, &veclen)) != -1) {
  435. /* go through this ack vector */
  436. while (veclen--) {
  437. const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
  438. u64 ackno_end_rl = SUB48(ackno, rl);
  439. ccid2_pr_debug("ackvec start:%llu end:%llu\n",
  440. (unsigned long long)ackno,
  441. (unsigned long long)ackno_end_rl);
  442. /* if the seqno we are analyzing is larger than the
  443. * current ackno, then move towards the tail of our
  444. * seqnos.
  445. */
  446. while (after48(seqp->ccid2s_seq, ackno)) {
  447. if (seqp == hc->tx_seqt) {
  448. done = 1;
  449. break;
  450. }
  451. seqp = seqp->ccid2s_prev;
  452. }
  453. if (done)
  454. break;
  455. /* check all seqnos in the range of the vector
  456. * run length
  457. */
  458. while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) {
  459. const u8 state = *vector &
  460. DCCP_ACKVEC_STATE_MASK;
  461. /* new packet received or marked */
  462. if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED &&
  463. !seqp->ccid2s_acked) {
  464. if (state ==
  465. DCCP_ACKVEC_STATE_ECN_MARKED) {
  466. ccid2_congestion_event(sk,
  467. seqp);
  468. } else
  469. ccid2_new_ack(sk, seqp,
  470. &maxincr);
  471. seqp->ccid2s_acked = 1;
  472. ccid2_pr_debug("Got ack for %llu\n",
  473. (unsigned long long)seqp->ccid2s_seq);
  474. hc->tx_pipe--;
  475. }
  476. if (seqp == hc->tx_seqt) {
  477. done = 1;
  478. break;
  479. }
  480. seqp = seqp->ccid2s_prev;
  481. }
  482. if (done)
  483. break;
  484. ackno = SUB48(ackno_end_rl, 1);
  485. vector++;
  486. }
  487. if (done)
  488. break;
  489. }
  490. /* The state about what is acked should be correct now
  491. * Check for NUMDUPACK
  492. */
  493. seqp = hc->tx_seqt;
  494. while (before48(seqp->ccid2s_seq, hc->tx_high_ack)) {
  495. seqp = seqp->ccid2s_next;
  496. if (seqp == hc->tx_seqh) {
  497. seqp = hc->tx_seqh->ccid2s_prev;
  498. break;
  499. }
  500. }
  501. done = 0;
  502. while (1) {
  503. if (seqp->ccid2s_acked) {
  504. done++;
  505. if (done == NUMDUPACK)
  506. break;
  507. }
  508. if (seqp == hc->tx_seqt)
  509. break;
  510. seqp = seqp->ccid2s_prev;
  511. }
  512. /* If there are at least 3 acknowledgements, anything unacknowledged
  513. * below the last sequence number is considered lost
  514. */
  515. if (done == NUMDUPACK) {
  516. struct ccid2_seq *last_acked = seqp;
  517. /* check for lost packets */
  518. while (1) {
  519. if (!seqp->ccid2s_acked) {
  520. ccid2_pr_debug("Packet lost: %llu\n",
  521. (unsigned long long)seqp->ccid2s_seq);
  522. /* XXX need to traverse from tail -> head in
  523. * order to detect multiple congestion events in
  524. * one ack vector.
  525. */
  526. ccid2_congestion_event(sk, seqp);
  527. hc->tx_pipe--;
  528. }
  529. if (seqp == hc->tx_seqt)
  530. break;
  531. seqp = seqp->ccid2s_prev;
  532. }
  533. hc->tx_seqt = last_acked;
  534. }
  535. /* trim acked packets in tail */
  536. while (hc->tx_seqt != hc->tx_seqh) {
  537. if (!hc->tx_seqt->ccid2s_acked)
  538. break;
  539. hc->tx_seqt = hc->tx_seqt->ccid2s_next;
  540. }
  541. /* restart RTO timer if not all outstanding data has been acked */
  542. if (hc->tx_pipe == 0)
  543. sk_stop_timer(sk, &hc->tx_rtotimer);
  544. else
  545. sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto);
  546. }
  547. static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)
  548. {
  549. struct ccid2_hc_tx_sock *hc = ccid_priv(ccid);
  550. struct dccp_sock *dp = dccp_sk(sk);
  551. u32 max_ratio;
  552. /* RFC 4341, 5: initialise ssthresh to arbitrarily high (max) value */
  553. hc->tx_ssthresh = ~0U;
  554. /*
  555. * RFC 4341, 5: "The cwnd parameter is initialized to at most four
  556. * packets for new connections, following the rules from [RFC3390]".
  557. * We need to convert the bytes of RFC3390 into the packets of RFC 4341.
  558. */
  559. hc->tx_cwnd = clamp(4380U / dp->dccps_mss_cache, 2U, 4U);
  560. /* Make sure that Ack Ratio is enabled and within bounds. */
  561. max_ratio = DIV_ROUND_UP(hc->tx_cwnd, 2);
  562. if (dp->dccps_l_ack_ratio == 0 || dp->dccps_l_ack_ratio > max_ratio)
  563. dp->dccps_l_ack_ratio = max_ratio;
  564. /* XXX init ~ to window size... */
  565. if (ccid2_hc_tx_alloc_seq(hc))
  566. return -ENOMEM;
  567. hc->tx_rto = 3 * HZ;
  568. ccid2_change_srtt(hc, -1);
  569. hc->tx_rttvar = -1;
  570. hc->tx_rpdupack = -1;
  571. hc->tx_last_cong = jiffies;
  572. setup_timer(&hc->tx_rtotimer, ccid2_hc_tx_rto_expire,
  573. (unsigned long)sk);
  574. return 0;
  575. }
  576. static void ccid2_hc_tx_exit(struct sock *sk)
  577. {
  578. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  579. int i;
  580. ccid2_hc_tx_kill_rto_timer(sk);
  581. for (i = 0; i < hc->tx_seqbufc; i++)
  582. kfree(hc->tx_seqbuf[i]);
  583. hc->tx_seqbufc = 0;
  584. }
  585. static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
  586. {
  587. const struct dccp_sock *dp = dccp_sk(sk);
  588. struct ccid2_hc_rx_sock *hc = ccid2_hc_rx_sk(sk);
  589. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  590. case DCCP_PKT_DATA:
  591. case DCCP_PKT_DATAACK:
  592. hc->rx_data++;
  593. if (hc->rx_data >= dp->dccps_r_ack_ratio) {
  594. dccp_send_ack(sk);
  595. hc->rx_data = 0;
  596. }
  597. break;
  598. }
  599. }
  600. struct ccid_operations ccid2_ops = {
  601. .ccid_id = DCCPC_CCID2,
  602. .ccid_name = "TCP-like",
  603. .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock),
  604. .ccid_hc_tx_init = ccid2_hc_tx_init,
  605. .ccid_hc_tx_exit = ccid2_hc_tx_exit,
  606. .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet,
  607. .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent,
  608. .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv,
  609. .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock),
  610. .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv,
  611. };
  612. #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
  613. module_param(ccid2_debug, bool, 0644);
  614. MODULE_PARM_DESC(ccid2_debug, "Enable CCID-2 debug messages");
  615. #endif