ccid2.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803
  1. /*
  2. * net/dccp/ccids/ccid2.c
  3. *
  4. * Copyright (c) 2005, 2006 Andrea Bittau <a.bittau@cs.ucl.ac.uk>
  5. *
  6. * Changes to meet Linux coding standards, and DCCP infrastructure fixes.
  7. *
  8. * Copyright (c) 2006 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
  9. *
  10. * This program is free software; you can redistribute it and/or modify
  11. * it under the terms of the GNU General Public License as published by
  12. * the Free Software Foundation; either version 2 of the License, or
  13. * (at your option) any later version.
  14. *
  15. * This program is distributed in the hope that it will be useful,
  16. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  18. * GNU General Public License for more details.
  19. *
  20. * You should have received a copy of the GNU General Public License
  21. * along with this program; if not, write to the Free Software
  22. * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23. */
  24. /*
  25. * This implementation should follow: draft-ietf-dccp-ccid2-10.txt
  26. *
  27. * BUGS:
  28. * - sequence number wrapping
  29. * - jiffies wrapping
  30. */
  31. #include <linux/config.h>
  32. #include "../ccid.h"
  33. #include "../dccp.h"
  34. #include "ccid2.h"
  35. static int ccid2_debug;
  36. #if 0
  37. #define CCID2_DEBUG
  38. #endif
  39. #ifdef CCID2_DEBUG
  40. #define ccid2_pr_debug(format, a...) \
  41. do { if (ccid2_debug) \
  42. printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \
  43. } while (0)
  44. #else
  45. #define ccid2_pr_debug(format, a...)
  46. #endif
  47. static const int ccid2_seq_len = 128;
  48. #ifdef CCID2_DEBUG
  49. static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx)
  50. {
  51. int len = 0;
  52. struct ccid2_seq *seqp;
  53. int pipe = 0;
  54. seqp = hctx->ccid2hctx_seqh;
  55. /* there is data in the chain */
  56. if (seqp != hctx->ccid2hctx_seqt) {
  57. seqp = seqp->ccid2s_prev;
  58. len++;
  59. if (!seqp->ccid2s_acked)
  60. pipe++;
  61. while (seqp != hctx->ccid2hctx_seqt) {
  62. struct ccid2_seq *prev;
  63. prev = seqp->ccid2s_prev;
  64. len++;
  65. if (!prev->ccid2s_acked)
  66. pipe++;
  67. /* packets are sent sequentially */
  68. BUG_ON(seqp->ccid2s_seq <= prev->ccid2s_seq);
  69. BUG_ON(seqp->ccid2s_sent < prev->ccid2s_sent);
  70. BUG_ON(len > ccid2_seq_len);
  71. seqp = prev;
  72. }
  73. }
  74. BUG_ON(pipe != hctx->ccid2hctx_pipe);
  75. ccid2_pr_debug("len of chain=%d\n", len);
  76. do {
  77. seqp = seqp->ccid2s_prev;
  78. len++;
  79. BUG_ON(len > ccid2_seq_len);
  80. } while(seqp != hctx->ccid2hctx_seqh);
  81. BUG_ON(len != ccid2_seq_len);
  82. ccid2_pr_debug("total len=%d\n", len);
  83. }
  84. #else
  85. #define ccid2_hc_tx_check_sanity(hctx) do {} while (0)
  86. #endif
  87. static int ccid2_hc_tx_send_packet(struct sock *sk,
  88. struct sk_buff *skb, int len)
  89. {
  90. struct ccid2_hc_tx_sock *hctx;
  91. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  92. case 0: /* XXX data packets from userland come through like this */
  93. case DCCP_PKT_DATA:
  94. case DCCP_PKT_DATAACK:
  95. break;
  96. /* No congestion control on other packets */
  97. default:
  98. return 0;
  99. }
  100. hctx = ccid2_hc_tx_sk(sk);
  101. ccid2_pr_debug("pipe=%d cwnd=%d\n", hctx->ccid2hctx_pipe,
  102. hctx->ccid2hctx_cwnd);
  103. if (hctx->ccid2hctx_pipe < hctx->ccid2hctx_cwnd) {
  104. /* OK we can send... make sure previous packet was sent off */
  105. if (!hctx->ccid2hctx_sendwait) {
  106. hctx->ccid2hctx_sendwait = 1;
  107. return 0;
  108. }
  109. }
  110. return 100; /* XXX */
  111. }
  112. static void ccid2_change_l_ack_ratio(struct sock *sk, int val)
  113. {
  114. struct dccp_sock *dp = dccp_sk(sk);
  115. /*
  116. * XXX I don't really agree with val != 2. If cwnd is 1, ack ratio
  117. * should be 1... it shouldn't be allowed to become 2.
  118. * -sorbo.
  119. */
  120. if (val != 2) {
  121. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  122. int max = hctx->ccid2hctx_cwnd / 2;
  123. /* round up */
  124. if (hctx->ccid2hctx_cwnd & 1)
  125. max++;
  126. if (val > max)
  127. val = max;
  128. }
  129. ccid2_pr_debug("changing local ack ratio to %d\n", val);
  130. WARN_ON(val <= 0);
  131. dp->dccps_l_ack_ratio = val;
  132. }
  133. static void ccid2_change_cwnd(struct sock *sk, int val)
  134. {
  135. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  136. if (val == 0)
  137. val = 1;
  138. /* XXX do we need to change ack ratio? */
  139. ccid2_pr_debug("change cwnd to %d\n", val);
  140. BUG_ON(val < 1);
  141. hctx->ccid2hctx_cwnd = val;
  142. }
  143. static void ccid2_start_rto_timer(struct sock *sk);
  144. static void ccid2_hc_tx_rto_expire(unsigned long data)
  145. {
  146. struct sock *sk = (struct sock *)data;
  147. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  148. long s;
  149. /* XXX I don't think i'm locking correctly
  150. * -sorbo.
  151. */
  152. bh_lock_sock(sk);
  153. if (sock_owned_by_user(sk)) {
  154. sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer,
  155. jiffies + HZ / 5);
  156. goto out;
  157. }
  158. ccid2_pr_debug("RTO_EXPIRE\n");
  159. ccid2_hc_tx_check_sanity(hctx);
  160. /* back-off timer */
  161. hctx->ccid2hctx_rto <<= 1;
  162. s = hctx->ccid2hctx_rto / HZ;
  163. if (s > 60)
  164. hctx->ccid2hctx_rto = 60 * HZ;
  165. ccid2_start_rto_timer(sk);
  166. /* adjust pipe, cwnd etc */
  167. hctx->ccid2hctx_pipe = 0;
  168. hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd >> 1;
  169. if (hctx->ccid2hctx_ssthresh < 2)
  170. hctx->ccid2hctx_ssthresh = 2;
  171. ccid2_change_cwnd(sk, 1);
  172. /* clear state about stuff we sent */
  173. hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh;
  174. hctx->ccid2hctx_ssacks = 0;
  175. hctx->ccid2hctx_acks = 0;
  176. hctx->ccid2hctx_sent = 0;
  177. /* clear ack ratio state. */
  178. hctx->ccid2hctx_arsent = 0;
  179. hctx->ccid2hctx_ackloss = 0;
  180. hctx->ccid2hctx_rpseq = 0;
  181. hctx->ccid2hctx_rpdupack = -1;
  182. ccid2_change_l_ack_ratio(sk, 1);
  183. ccid2_hc_tx_check_sanity(hctx);
  184. out:
  185. bh_unlock_sock(sk);
  186. sock_put(sk);
  187. }
  188. static void ccid2_start_rto_timer(struct sock *sk)
  189. {
  190. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  191. ccid2_pr_debug("setting RTO timeout=%ld\n", hctx->ccid2hctx_rto);
  192. BUG_ON(timer_pending(&hctx->ccid2hctx_rtotimer));
  193. sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer,
  194. jiffies + hctx->ccid2hctx_rto);
  195. }
  196. static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, int len)
  197. {
  198. struct dccp_sock *dp = dccp_sk(sk);
  199. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  200. u64 seq;
  201. ccid2_hc_tx_check_sanity(hctx);
  202. BUG_ON(!hctx->ccid2hctx_sendwait);
  203. hctx->ccid2hctx_sendwait = 0;
  204. hctx->ccid2hctx_pipe++;
  205. BUG_ON(hctx->ccid2hctx_pipe < 0);
  206. /* There is an issue. What if another packet is sent between
  207. * packet_send() and packet_sent(). Then the sequence number would be
  208. * wrong.
  209. * -sorbo.
  210. */
  211. seq = dp->dccps_gss;
  212. hctx->ccid2hctx_seqh->ccid2s_seq = seq;
  213. hctx->ccid2hctx_seqh->ccid2s_acked = 0;
  214. hctx->ccid2hctx_seqh->ccid2s_sent = jiffies;
  215. hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqh->ccid2s_next;
  216. ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx->ccid2hctx_cwnd,
  217. hctx->ccid2hctx_pipe);
  218. if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt) {
  219. /* XXX allocate more space */
  220. WARN_ON(1);
  221. }
  222. hctx->ccid2hctx_sent++;
  223. /* Ack Ratio. Need to maintain a concept of how many windows we sent */
  224. hctx->ccid2hctx_arsent++;
  225. /* We had an ack loss in this window... */
  226. if (hctx->ccid2hctx_ackloss) {
  227. if (hctx->ccid2hctx_arsent >= hctx->ccid2hctx_cwnd) {
  228. hctx->ccid2hctx_arsent = 0;
  229. hctx->ccid2hctx_ackloss = 0;
  230. }
  231. }
  232. /* No acks lost up to now... */
  233. else {
  234. /* decrease ack ratio if enough packets were sent */
  235. if (dp->dccps_l_ack_ratio > 1) {
  236. /* XXX don't calculate denominator each time */
  237. int denom;
  238. denom = dp->dccps_l_ack_ratio * dp->dccps_l_ack_ratio -
  239. dp->dccps_l_ack_ratio;
  240. denom = hctx->ccid2hctx_cwnd * hctx->ccid2hctx_cwnd / denom;
  241. if (hctx->ccid2hctx_arsent >= denom) {
  242. ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio - 1);
  243. hctx->ccid2hctx_arsent = 0;
  244. }
  245. }
  246. /* we can't increase ack ratio further [1] */
  247. else {
  248. hctx->ccid2hctx_arsent = 0; /* or maybe set it to cwnd*/
  249. }
  250. }
  251. /* setup RTO timer */
  252. if (!timer_pending(&hctx->ccid2hctx_rtotimer)) {
  253. ccid2_start_rto_timer(sk);
  254. }
  255. #ifdef CCID2_DEBUG
  256. ccid2_pr_debug("pipe=%d\n", hctx->ccid2hctx_pipe);
  257. ccid2_pr_debug("Sent: seq=%llu\n", seq);
  258. do {
  259. struct ccid2_seq *seqp = hctx->ccid2hctx_seqt;
  260. while (seqp != hctx->ccid2hctx_seqh) {
  261. ccid2_pr_debug("out seq=%llu acked=%d time=%lu\n",
  262. seqp->ccid2s_seq, seqp->ccid2s_acked,
  263. seqp->ccid2s_sent);
  264. seqp = seqp->ccid2s_next;
  265. }
  266. } while(0);
  267. ccid2_pr_debug("=========\n");
  268. ccid2_hc_tx_check_sanity(hctx);
  269. #endif
  270. }
  271. /* XXX Lame code duplication!
  272. * returns -1 if none was found.
  273. * else returns the next offset to use in the function call.
  274. */
  275. static int ccid2_ackvector(struct sock *sk, struct sk_buff *skb, int offset,
  276. unsigned char **vec, unsigned char *veclen)
  277. {
  278. const struct dccp_hdr *dh = dccp_hdr(skb);
  279. unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb);
  280. unsigned char *opt_ptr;
  281. const unsigned char *opt_end = (unsigned char *)dh +
  282. (dh->dccph_doff * 4);
  283. unsigned char opt, len;
  284. unsigned char *value;
  285. BUG_ON(offset < 0);
  286. options += offset;
  287. opt_ptr = options;
  288. if (opt_ptr >= opt_end)
  289. return -1;
  290. while (opt_ptr != opt_end) {
  291. opt = *opt_ptr++;
  292. len = 0;
  293. value = NULL;
  294. /* Check if this isn't a single byte option */
  295. if (opt > DCCPO_MAX_RESERVED) {
  296. if (opt_ptr == opt_end)
  297. goto out_invalid_option;
  298. len = *opt_ptr++;
  299. if (len < 3)
  300. goto out_invalid_option;
  301. /*
  302. * Remove the type and len fields, leaving
  303. * just the value size
  304. */
  305. len -= 2;
  306. value = opt_ptr;
  307. opt_ptr += len;
  308. if (opt_ptr > opt_end)
  309. goto out_invalid_option;
  310. }
  311. switch (opt) {
  312. case DCCPO_ACK_VECTOR_0:
  313. case DCCPO_ACK_VECTOR_1:
  314. *vec = value;
  315. *veclen = len;
  316. return offset + (opt_ptr - options);
  317. break;
  318. }
  319. }
  320. return -1;
  321. out_invalid_option:
  322. BUG_ON(1); /* should never happen... options were previously parsed ! */
  323. return -1;
  324. }
  325. static void ccid2_hc_tx_kill_rto_timer(struct sock *sk)
  326. {
  327. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  328. sk_stop_timer(sk, &hctx->ccid2hctx_rtotimer);
  329. ccid2_pr_debug("deleted RTO timer\n");
  330. }
  331. static inline void ccid2_new_ack(struct sock *sk,
  332. struct ccid2_seq *seqp,
  333. unsigned int *maxincr)
  334. {
  335. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  336. /* slow start */
  337. if (hctx->ccid2hctx_cwnd < hctx->ccid2hctx_ssthresh) {
  338. hctx->ccid2hctx_acks = 0;
  339. /* We can increase cwnd at most maxincr [ack_ratio/2] */
  340. if (*maxincr) {
  341. /* increase every 2 acks */
  342. hctx->ccid2hctx_ssacks++;
  343. if (hctx->ccid2hctx_ssacks == 2) {
  344. ccid2_change_cwnd(sk, hctx->ccid2hctx_cwnd + 1);
  345. hctx->ccid2hctx_ssacks = 0;
  346. *maxincr = *maxincr - 1;
  347. }
  348. }
  349. /* increased cwnd enough for this single ack */
  350. else {
  351. hctx->ccid2hctx_ssacks = 0;
  352. }
  353. }
  354. else {
  355. hctx->ccid2hctx_ssacks = 0;
  356. hctx->ccid2hctx_acks++;
  357. if (hctx->ccid2hctx_acks >= hctx->ccid2hctx_cwnd) {
  358. ccid2_change_cwnd(sk, hctx->ccid2hctx_cwnd + 1);
  359. hctx->ccid2hctx_acks = 0;
  360. }
  361. }
  362. /* update RTO */
  363. if (hctx->ccid2hctx_srtt == -1 ||
  364. (jiffies - hctx->ccid2hctx_lastrtt) >= hctx->ccid2hctx_srtt) {
  365. unsigned long r = jiffies - seqp->ccid2s_sent;
  366. int s;
  367. /* first measurement */
  368. if (hctx->ccid2hctx_srtt == -1) {
  369. ccid2_pr_debug("R: %lu Time=%lu seq=%llu\n",
  370. r, jiffies, seqp->ccid2s_seq);
  371. hctx->ccid2hctx_srtt = r;
  372. hctx->ccid2hctx_rttvar = r >> 1;
  373. }
  374. else {
  375. /* RTTVAR */
  376. long tmp = hctx->ccid2hctx_srtt - r;
  377. if (tmp < 0)
  378. tmp *= -1;
  379. tmp >>= 2;
  380. hctx->ccid2hctx_rttvar *= 3;
  381. hctx->ccid2hctx_rttvar >>= 2;
  382. hctx->ccid2hctx_rttvar += tmp;
  383. /* SRTT */
  384. hctx->ccid2hctx_srtt *= 7;
  385. hctx->ccid2hctx_srtt >>= 3;
  386. tmp = r >> 3;
  387. hctx->ccid2hctx_srtt += tmp;
  388. }
  389. s = hctx->ccid2hctx_rttvar << 2;
  390. /* clock granularity is 1 when based on jiffies */
  391. if (!s)
  392. s = 1;
  393. hctx->ccid2hctx_rto = hctx->ccid2hctx_srtt + s;
  394. /* must be at least a second */
  395. s = hctx->ccid2hctx_rto / HZ;
  396. /* DCCP doesn't require this [but I like it cuz my code sux] */
  397. #if 1
  398. if (s < 1)
  399. hctx->ccid2hctx_rto = HZ;
  400. #endif
  401. /* max 60 seconds */
  402. if (s > 60)
  403. hctx->ccid2hctx_rto = HZ * 60;
  404. hctx->ccid2hctx_lastrtt = jiffies;
  405. ccid2_pr_debug("srtt: %ld rttvar: %ld rto: %ld (HZ=%d) R=%lu\n",
  406. hctx->ccid2hctx_srtt, hctx->ccid2hctx_rttvar,
  407. hctx->ccid2hctx_rto, HZ, r);
  408. hctx->ccid2hctx_sent = 0;
  409. }
  410. /* we got a new ack, so re-start RTO timer */
  411. ccid2_hc_tx_kill_rto_timer(sk);
  412. ccid2_start_rto_timer(sk);
  413. }
  414. static void ccid2_hc_tx_dec_pipe(struct sock *sk)
  415. {
  416. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  417. hctx->ccid2hctx_pipe--;
  418. BUG_ON(hctx->ccid2hctx_pipe < 0);
  419. if (hctx->ccid2hctx_pipe == 0)
  420. ccid2_hc_tx_kill_rto_timer(sk);
  421. }
  422. static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
  423. {
  424. struct dccp_sock *dp = dccp_sk(sk);
  425. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  426. u64 ackno, seqno;
  427. struct ccid2_seq *seqp;
  428. unsigned char *vector;
  429. unsigned char veclen;
  430. int offset = 0;
  431. int done = 0;
  432. int loss = 0;
  433. unsigned int maxincr = 0;
  434. ccid2_hc_tx_check_sanity(hctx);
  435. /* check reverse path congestion */
  436. seqno = DCCP_SKB_CB(skb)->dccpd_seq;
  437. /* XXX this whole "algorithm" is broken. Need to fix it to keep track
  438. * of the seqnos of the dupacks so that rpseq and rpdupack are correct
  439. * -sorbo.
  440. */
  441. /* need to bootstrap */
  442. if (hctx->ccid2hctx_rpdupack == -1) {
  443. hctx->ccid2hctx_rpdupack = 0;
  444. hctx->ccid2hctx_rpseq = seqno;
  445. }
  446. else {
  447. /* check if packet is consecutive */
  448. if ((hctx->ccid2hctx_rpseq + 1) == seqno) {
  449. hctx->ccid2hctx_rpseq++;
  450. }
  451. /* it's a later packet */
  452. else if (after48(seqno, hctx->ccid2hctx_rpseq)) {
  453. hctx->ccid2hctx_rpdupack++;
  454. /* check if we got enough dupacks */
  455. if (hctx->ccid2hctx_rpdupack >=
  456. hctx->ccid2hctx_numdupack) {
  457. hctx->ccid2hctx_rpdupack = -1; /* XXX lame */
  458. hctx->ccid2hctx_rpseq = 0;
  459. ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio << 1);
  460. }
  461. }
  462. }
  463. /* check forward path congestion */
  464. /* still didn't send out new data packets */
  465. if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt)
  466. return;
  467. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  468. case DCCP_PKT_ACK:
  469. case DCCP_PKT_DATAACK:
  470. break;
  471. default:
  472. return;
  473. }
  474. ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
  475. seqp = hctx->ccid2hctx_seqh->ccid2s_prev;
  476. /* If in slow-start, cwnd can increase at most Ack Ratio / 2 packets for
  477. * this single ack. I round up.
  478. * -sorbo.
  479. */
  480. maxincr = dp->dccps_l_ack_ratio >> 1;
  481. maxincr++;
  482. /* go through all ack vectors */
  483. while ((offset = ccid2_ackvector(sk, skb, offset,
  484. &vector, &veclen)) != -1) {
  485. /* go through this ack vector */
  486. while (veclen--) {
  487. const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
  488. u64 ackno_end_rl;
  489. dccp_set_seqno(&ackno_end_rl, ackno - rl);
  490. ccid2_pr_debug("ackvec start:%llu end:%llu\n", ackno,
  491. ackno_end_rl);
  492. /* if the seqno we are analyzing is larger than the
  493. * current ackno, then move towards the tail of our
  494. * seqnos.
  495. */
  496. while (after48(seqp->ccid2s_seq, ackno)) {
  497. if (seqp == hctx->ccid2hctx_seqt) {
  498. done = 1;
  499. break;
  500. }
  501. seqp = seqp->ccid2s_prev;
  502. }
  503. if (done)
  504. break;
  505. /* check all seqnos in the range of the vector
  506. * run length
  507. */
  508. while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) {
  509. const u8 state = (*vector &
  510. DCCP_ACKVEC_STATE_MASK) >> 6;
  511. /* new packet received or marked */
  512. if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED &&
  513. !seqp->ccid2s_acked) {
  514. if (state ==
  515. DCCP_ACKVEC_STATE_ECN_MARKED) {
  516. loss = 1;
  517. }
  518. else {
  519. ccid2_new_ack(sk, seqp,
  520. &maxincr);
  521. }
  522. seqp->ccid2s_acked = 1;
  523. ccid2_pr_debug("Got ack for %llu\n",
  524. seqp->ccid2s_seq);
  525. ccid2_hc_tx_dec_pipe(sk);
  526. }
  527. if (seqp == hctx->ccid2hctx_seqt) {
  528. done = 1;
  529. break;
  530. }
  531. seqp = seqp->ccid2s_next;
  532. }
  533. if (done)
  534. break;
  535. dccp_set_seqno(&ackno, ackno_end_rl - 1);
  536. vector++;
  537. }
  538. if (done)
  539. break;
  540. }
  541. /* The state about what is acked should be correct now
  542. * Check for NUMDUPACK
  543. */
  544. seqp = hctx->ccid2hctx_seqh->ccid2s_prev;
  545. done = 0;
  546. while (1) {
  547. if (seqp->ccid2s_acked) {
  548. done++;
  549. if (done == hctx->ccid2hctx_numdupack) {
  550. break;
  551. }
  552. }
  553. if (seqp == hctx->ccid2hctx_seqt) {
  554. break;
  555. }
  556. seqp = seqp->ccid2s_prev;
  557. }
  558. /* If there are at least 3 acknowledgements, anything unacknowledged
  559. * below the last sequence number is considered lost
  560. */
  561. if (done == hctx->ccid2hctx_numdupack) {
  562. struct ccid2_seq *last_acked = seqp;
  563. /* check for lost packets */
  564. while (1) {
  565. if (!seqp->ccid2s_acked) {
  566. loss = 1;
  567. ccid2_hc_tx_dec_pipe(sk);
  568. }
  569. if (seqp == hctx->ccid2hctx_seqt)
  570. break;
  571. seqp = seqp->ccid2s_prev;
  572. }
  573. hctx->ccid2hctx_seqt = last_acked;
  574. }
  575. /* trim acked packets in tail */
  576. while (hctx->ccid2hctx_seqt != hctx->ccid2hctx_seqh) {
  577. if (!hctx->ccid2hctx_seqt->ccid2s_acked)
  578. break;
  579. hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqt->ccid2s_next;
  580. }
  581. if (loss) {
  582. /* XXX do bit shifts guarantee a 0 as the new bit? */
  583. ccid2_change_cwnd(sk, hctx->ccid2hctx_cwnd >> 1);
  584. hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd;
  585. if (hctx->ccid2hctx_ssthresh < 2)
  586. hctx->ccid2hctx_ssthresh = 2;
  587. }
  588. ccid2_hc_tx_check_sanity(hctx);
  589. }
  590. static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk)
  591. {
  592. struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid);
  593. int seqcount = ccid2_seq_len;
  594. int i;
  595. /* XXX init variables with proper values */
  596. hctx->ccid2hctx_cwnd = 1;
  597. hctx->ccid2hctx_ssthresh = 10;
  598. hctx->ccid2hctx_numdupack = 3;
  599. /* XXX init ~ to window size... */
  600. hctx->ccid2hctx_seqbuf = kmalloc(sizeof(*hctx->ccid2hctx_seqbuf) *
  601. seqcount, gfp_any());
  602. if (hctx->ccid2hctx_seqbuf == NULL)
  603. return -ENOMEM;
  604. for (i = 0; i < (seqcount - 1); i++) {
  605. hctx->ccid2hctx_seqbuf[i].ccid2s_next =
  606. &hctx->ccid2hctx_seqbuf[i + 1];
  607. hctx->ccid2hctx_seqbuf[i + 1].ccid2s_prev =
  608. &hctx->ccid2hctx_seqbuf[i];
  609. }
  610. hctx->ccid2hctx_seqbuf[seqcount - 1].ccid2s_next =
  611. hctx->ccid2hctx_seqbuf;
  612. hctx->ccid2hctx_seqbuf->ccid2s_prev =
  613. &hctx->ccid2hctx_seqbuf[seqcount - 1];
  614. hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqbuf;
  615. hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh;
  616. hctx->ccid2hctx_sent = 0;
  617. hctx->ccid2hctx_rto = 3 * HZ;
  618. hctx->ccid2hctx_srtt = -1;
  619. hctx->ccid2hctx_rttvar = -1;
  620. hctx->ccid2hctx_lastrtt = 0;
  621. hctx->ccid2hctx_rpdupack = -1;
  622. hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire;
  623. hctx->ccid2hctx_rtotimer.data = (unsigned long)sk;
  624. init_timer(&hctx->ccid2hctx_rtotimer);
  625. ccid2_hc_tx_check_sanity(hctx);
  626. return 0;
  627. }
  628. static void ccid2_hc_tx_exit(struct sock *sk)
  629. {
  630. struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk);
  631. ccid2_hc_tx_kill_rto_timer(sk);
  632. kfree(hctx->ccid2hctx_seqbuf);
  633. hctx->ccid2hctx_seqbuf = NULL;
  634. }
  635. static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
  636. {
  637. const struct dccp_sock *dp = dccp_sk(sk);
  638. struct ccid2_hc_rx_sock *hcrx = ccid2_hc_rx_sk(sk);
  639. switch (DCCP_SKB_CB(skb)->dccpd_type) {
  640. case DCCP_PKT_DATA:
  641. case DCCP_PKT_DATAACK:
  642. hcrx->ccid2hcrx_data++;
  643. if (hcrx->ccid2hcrx_data >= dp->dccps_r_ack_ratio) {
  644. dccp_send_ack(sk);
  645. hcrx->ccid2hcrx_data = 0;
  646. }
  647. break;
  648. }
  649. }
  650. static struct ccid_operations ccid2 = {
  651. .ccid_id = 2,
  652. .ccid_name = "ccid2",
  653. .ccid_owner = THIS_MODULE,
  654. .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock),
  655. .ccid_hc_tx_init = ccid2_hc_tx_init,
  656. .ccid_hc_tx_exit = ccid2_hc_tx_exit,
  657. .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet,
  658. .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent,
  659. .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv,
  660. .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock),
  661. .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv,
  662. };
  663. module_param(ccid2_debug, int, 0444);
  664. MODULE_PARM_DESC(ccid2_debug, "Enable debug messages");
  665. static __init int ccid2_module_init(void)
  666. {
  667. return ccid_register(&ccid2);
  668. }
  669. module_init(ccid2_module_init);
  670. static __exit void ccid2_module_exit(void)
  671. {
  672. ccid_unregister(&ccid2);
  673. }
  674. module_exit(ccid2_module_exit);
  675. MODULE_AUTHOR("Andrea Bittau <a.bittau@cs.ucl.ac.uk>");
  676. MODULE_DESCRIPTION("DCCP TCP CCID2 CCID");
  677. MODULE_LICENSE("GPL");
  678. MODULE_ALIAS("net-dccp-ccid-2");