ccid2.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731
  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. /* we got a new ack, so re-start RTO timer */
  353. ccid2_hc_tx_kill_rto_timer(sk);
  354. ccid2_start_rto_timer(sk);
  355. }
  356. static void ccid2_hc_tx_dec_pipe(struct sock *sk)
  357. {
  358. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  359. if (hc->tx_pipe == 0)
  360. DCCP_BUG("pipe == 0");
  361. else
  362. hc->tx_pipe--;
  363. if (hc->tx_pipe == 0)
  364. ccid2_hc_tx_kill_rto_timer(sk);
  365. }
  366. static void ccid2_congestion_event(struct sock *sk, struct ccid2_seq *seqp)
  367. {
  368. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  369. if (time_before(seqp->ccid2s_sent, hc->tx_last_cong)) {
  370. ccid2_pr_debug("Multiple losses in an RTT---treating as one\n");
  371. return;
  372. }
  373. hc->tx_last_cong = jiffies;
  374. hc->tx_cwnd = hc->tx_cwnd / 2 ? : 1U;
  375. hc->tx_ssthresh = max(hc->tx_cwnd, 2U);
  376. /* Avoid spurious timeouts resulting from Ack Ratio > cwnd */
  377. if (dccp_sk(sk)->dccps_l_ack_ratio > hc->tx_cwnd)
  378. ccid2_change_l_ack_ratio(sk, hc->tx_cwnd);
  379. }
  380. static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
  381. {
  382. struct dccp_sock *dp = dccp_sk(sk);
  383. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  384. u64 ackno, seqno;
  385. struct ccid2_seq *seqp;
  386. unsigned char *vector;
  387. unsigned char veclen;
  388. int offset = 0;
  389. int done = 0;
  390. unsigned int maxincr = 0;
  391. /* check reverse path congestion */
  392. seqno = DCCP_SKB_CB(skb)->dccpd_seq;
  393. /* XXX this whole "algorithm" is broken. Need to fix it to keep track
  394. * of the seqnos of the dupacks so that rpseq and rpdupack are correct
  395. * -sorbo.
  396. */
  397. /* need to bootstrap */
  398. if (hc->tx_rpdupack == -1) {
  399. hc->tx_rpdupack = 0;
  400. hc->tx_rpseq = seqno;
  401. } else {
  402. /* check if packet is consecutive */
  403. if (dccp_delta_seqno(hc->tx_rpseq, seqno) == 1)
  404. hc->tx_rpseq = seqno;
  405. /* it's a later packet */
  406. else if (after48(seqno, hc->tx_rpseq)) {
  407. hc->tx_rpdupack++;
  408. /* check if we got enough dupacks */
  409. if (hc->tx_rpdupack >= NUMDUPACK) {
  410. hc->tx_rpdupack = -1; /* XXX lame */
  411. hc->tx_rpseq = 0;
  412. ccid2_change_l_ack_ratio(sk, 2 * dp->dccps_l_ack_ratio);
  413. }
  414. }
  415. }
  416. /* check forward path congestion */
  417. /* still didn't send out new data packets */
  418. if (hc->tx_seqh == hc->tx_seqt)
  419. return;
  420. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  421. case DCCP_PKT_ACK:
  422. case DCCP_PKT_DATAACK:
  423. break;
  424. default:
  425. return;
  426. }
  427. ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
  428. if (after48(ackno, hc->tx_high_ack))
  429. hc->tx_high_ack = ackno;
  430. seqp = hc->tx_seqt;
  431. while (before48(seqp->ccid2s_seq, ackno)) {
  432. seqp = seqp->ccid2s_next;
  433. if (seqp == hc->tx_seqh) {
  434. seqp = hc->tx_seqh->ccid2s_prev;
  435. break;
  436. }
  437. }
  438. /*
  439. * In slow-start, cwnd can increase up to a maximum of Ack Ratio/2
  440. * packets per acknowledgement. Rounding up avoids that cwnd is not
  441. * advanced when Ack Ratio is 1 and gives a slight edge otherwise.
  442. */
  443. if (hc->tx_cwnd < hc->tx_ssthresh)
  444. maxincr = DIV_ROUND_UP(dp->dccps_l_ack_ratio, 2);
  445. /* go through all ack vectors */
  446. while ((offset = ccid2_ackvector(sk, skb, offset,
  447. &vector, &veclen)) != -1) {
  448. /* go through this ack vector */
  449. while (veclen--) {
  450. const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
  451. u64 ackno_end_rl = SUB48(ackno, rl);
  452. ccid2_pr_debug("ackvec start:%llu end:%llu\n",
  453. (unsigned long long)ackno,
  454. (unsigned long long)ackno_end_rl);
  455. /* if the seqno we are analyzing is larger than the
  456. * current ackno, then move towards the tail of our
  457. * seqnos.
  458. */
  459. while (after48(seqp->ccid2s_seq, ackno)) {
  460. if (seqp == hc->tx_seqt) {
  461. done = 1;
  462. break;
  463. }
  464. seqp = seqp->ccid2s_prev;
  465. }
  466. if (done)
  467. break;
  468. /* check all seqnos in the range of the vector
  469. * run length
  470. */
  471. while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) {
  472. const u8 state = *vector &
  473. DCCP_ACKVEC_STATE_MASK;
  474. /* new packet received or marked */
  475. if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED &&
  476. !seqp->ccid2s_acked) {
  477. if (state ==
  478. DCCP_ACKVEC_STATE_ECN_MARKED) {
  479. ccid2_congestion_event(sk,
  480. seqp);
  481. } else
  482. ccid2_new_ack(sk, seqp,
  483. &maxincr);
  484. seqp->ccid2s_acked = 1;
  485. ccid2_pr_debug("Got ack for %llu\n",
  486. (unsigned long long)seqp->ccid2s_seq);
  487. ccid2_hc_tx_dec_pipe(sk);
  488. }
  489. if (seqp == hc->tx_seqt) {
  490. done = 1;
  491. break;
  492. }
  493. seqp = seqp->ccid2s_prev;
  494. }
  495. if (done)
  496. break;
  497. ackno = SUB48(ackno_end_rl, 1);
  498. vector++;
  499. }
  500. if (done)
  501. break;
  502. }
  503. /* The state about what is acked should be correct now
  504. * Check for NUMDUPACK
  505. */
  506. seqp = hc->tx_seqt;
  507. while (before48(seqp->ccid2s_seq, hc->tx_high_ack)) {
  508. seqp = seqp->ccid2s_next;
  509. if (seqp == hc->tx_seqh) {
  510. seqp = hc->tx_seqh->ccid2s_prev;
  511. break;
  512. }
  513. }
  514. done = 0;
  515. while (1) {
  516. if (seqp->ccid2s_acked) {
  517. done++;
  518. if (done == NUMDUPACK)
  519. break;
  520. }
  521. if (seqp == hc->tx_seqt)
  522. break;
  523. seqp = seqp->ccid2s_prev;
  524. }
  525. /* If there are at least 3 acknowledgements, anything unacknowledged
  526. * below the last sequence number is considered lost
  527. */
  528. if (done == NUMDUPACK) {
  529. struct ccid2_seq *last_acked = seqp;
  530. /* check for lost packets */
  531. while (1) {
  532. if (!seqp->ccid2s_acked) {
  533. ccid2_pr_debug("Packet lost: %llu\n",
  534. (unsigned long long)seqp->ccid2s_seq);
  535. /* XXX need to traverse from tail -> head in
  536. * order to detect multiple congestion events in
  537. * one ack vector.
  538. */
  539. ccid2_congestion_event(sk, seqp);
  540. ccid2_hc_tx_dec_pipe(sk);
  541. }
  542. if (seqp == hc->tx_seqt)
  543. break;
  544. seqp = seqp->ccid2s_prev;
  545. }
  546. hc->tx_seqt = last_acked;
  547. }
  548. /* trim acked packets in tail */
  549. while (hc->tx_seqt != hc->tx_seqh) {
  550. if (!hc->tx_seqt->ccid2s_acked)
  551. break;
  552. hc->tx_seqt = hc->tx_seqt->ccid2s_next;
  553. }
  554. }
  555. static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)
  556. {
  557. struct ccid2_hc_tx_sock *hc = ccid_priv(ccid);
  558. struct dccp_sock *dp = dccp_sk(sk);
  559. u32 max_ratio;
  560. /* RFC 4341, 5: initialise ssthresh to arbitrarily high (max) value */
  561. hc->tx_ssthresh = ~0U;
  562. /*
  563. * RFC 4341, 5: "The cwnd parameter is initialized to at most four
  564. * packets for new connections, following the rules from [RFC3390]".
  565. * We need to convert the bytes of RFC3390 into the packets of RFC 4341.
  566. */
  567. hc->tx_cwnd = clamp(4380U / dp->dccps_mss_cache, 2U, 4U);
  568. /* Make sure that Ack Ratio is enabled and within bounds. */
  569. max_ratio = DIV_ROUND_UP(hc->tx_cwnd, 2);
  570. if (dp->dccps_l_ack_ratio == 0 || dp->dccps_l_ack_ratio > max_ratio)
  571. dp->dccps_l_ack_ratio = max_ratio;
  572. /* XXX init ~ to window size... */
  573. if (ccid2_hc_tx_alloc_seq(hc))
  574. return -ENOMEM;
  575. hc->tx_rto = 3 * HZ;
  576. ccid2_change_srtt(hc, -1);
  577. hc->tx_rttvar = -1;
  578. hc->tx_rpdupack = -1;
  579. hc->tx_last_cong = jiffies;
  580. setup_timer(&hc->tx_rtotimer, ccid2_hc_tx_rto_expire,
  581. (unsigned long)sk);
  582. return 0;
  583. }
  584. static void ccid2_hc_tx_exit(struct sock *sk)
  585. {
  586. struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk);
  587. int i;
  588. ccid2_hc_tx_kill_rto_timer(sk);
  589. for (i = 0; i < hc->tx_seqbufc; i++)
  590. kfree(hc->tx_seqbuf[i]);
  591. hc->tx_seqbufc = 0;
  592. }
  593. static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
  594. {
  595. const struct dccp_sock *dp = dccp_sk(sk);
  596. struct ccid2_hc_rx_sock *hc = ccid2_hc_rx_sk(sk);
  597. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  598. case DCCP_PKT_DATA:
  599. case DCCP_PKT_DATAACK:
  600. hc->rx_data++;
  601. if (hc->rx_data >= dp->dccps_r_ack_ratio) {
  602. dccp_send_ack(sk);
  603. hc->rx_data = 0;
  604. }
  605. break;
  606. }
  607. }
  608. struct ccid_operations ccid2_ops = {
  609. .ccid_id = DCCPC_CCID2,
  610. .ccid_name = "TCP-like",
  611. .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock),
  612. .ccid_hc_tx_init = ccid2_hc_tx_init,
  613. .ccid_hc_tx_exit = ccid2_hc_tx_exit,
  614. .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet,
  615. .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent,
  616. .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv,
  617. .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock),
  618. .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv,
  619. };
  620. #ifdef CONFIG_IP_DCCP_CCID2_DEBUG
  621. module_param(ccid2_debug, bool, 0644);
  622. MODULE_PARM_DESC(ccid2_debug, "Enable CCID-2 debug messages");
  623. #endif