Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/davej/cpufreq
[deliverable/linux.git] / net / dccp / ccids / ccid3.c
1 /*
2 * Copyright (c) 2007 The University of Aberdeen, Scotland, UK
3 * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
4 * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
5 *
6 * An implementation of the DCCP protocol
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 *
11 * This code also uses code from Lulea University, rereleased as GPL by its
12 * authors:
13 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
14 *
15 * Changes to meet Linux coding standards, to make it meet latest ccid3 draft
16 * and to make it work as a loadable module in the DCCP stack written by
17 * Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
18 *
19 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
20 *
21 * This program is free software; you can redistribute it and/or modify
22 * it under the terms of the GNU General Public License as published by
23 * the Free Software Foundation; either version 2 of the License, or
24 * (at your option) any later version.
25 *
26 * This program is distributed in the hope that it will be useful,
27 * but WITHOUT ANY WARRANTY; without even the implied warranty of
28 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
29 * GNU General Public License for more details.
30 *
31 * You should have received a copy of the GNU General Public License
32 * along with this program; if not, write to the Free Software
33 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
34 */
35 #include "../dccp.h"
36 #include "ccid3.h"
37
38 #include <asm/unaligned.h>
39
40 #ifdef CONFIG_IP_DCCP_CCID3_DEBUG
41 static int ccid3_debug;
42 #define ccid3_pr_debug(format, a...) DCCP_PR_DEBUG(ccid3_debug, format, ##a)
43 #else
44 #define ccid3_pr_debug(format, a...)
45 #endif
46
47 /*
48 * Transmitter Half-Connection Routines
49 */
50 #ifdef CONFIG_IP_DCCP_CCID3_DEBUG
51 static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state)
52 {
53 static const char *const ccid3_state_names[] = {
54 [TFRC_SSTATE_NO_SENT] = "NO_SENT",
55 [TFRC_SSTATE_NO_FBACK] = "NO_FBACK",
56 [TFRC_SSTATE_FBACK] = "FBACK",
57 [TFRC_SSTATE_TERM] = "TERM",
58 };
59
60 return ccid3_state_names[state];
61 }
62 #endif
63
64 static void ccid3_hc_tx_set_state(struct sock *sk,
65 enum ccid3_hc_tx_states state)
66 {
67 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
68 enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state;
69
70 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
71 dccp_role(sk), sk, ccid3_tx_state_name(oldstate),
72 ccid3_tx_state_name(state));
73 WARN_ON(state == oldstate);
74 hctx->ccid3hctx_state = state;
75 }
76
77 /*
78 * Compute the initial sending rate X_init in the manner of RFC 3390:
79 *
80 * X_init = min(4 * s, max(2 * s, 4380 bytes)) / RTT
81 *
82 * Note that RFC 3390 uses MSS, RFC 4342 refers to RFC 3390, and rfc3448bis
83 * (rev-02) clarifies the use of RFC 3390 with regard to the above formula.
84 * For consistency with other parts of the code, X_init is scaled by 2^6.
85 */
86 static inline u64 rfc3390_initial_rate(struct sock *sk)
87 {
88 const struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
89 const __u32 w_init = clamp_t(__u32, 4380U,
90 2 * hctx->ccid3hctx_s, 4 * hctx->ccid3hctx_s);
91
92 return scaled_div(w_init << 6, hctx->ccid3hctx_rtt);
93 }
94
95 /*
96 * Recalculate t_ipi and delta (should be called whenever X changes)
97 */
98 static void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx)
99 {
100 /* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */
101 hctx->ccid3hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s) << 6,
102 hctx->ccid3hctx_x);
103
104 /* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */
105 hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2,
106 TFRC_OPSYS_HALF_TIME_GRAN);
107
108 ccid3_pr_debug("t_ipi=%u, delta=%u, s=%u, X=%u\n",
109 hctx->ccid3hctx_t_ipi, hctx->ccid3hctx_delta,
110 hctx->ccid3hctx_s, (unsigned)(hctx->ccid3hctx_x >> 6));
111
112 }
113
114 static u32 ccid3_hc_tx_idle_rtt(struct ccid3_hc_tx_sock *hctx, ktime_t now)
115 {
116 u32 delta = ktime_us_delta(now, hctx->ccid3hctx_t_last_win_count);
117
118 return delta / hctx->ccid3hctx_rtt;
119 }
120
121 /**
122 * ccid3_hc_tx_update_x - Update allowed sending rate X
123 * @stamp: most recent time if available - can be left NULL.
124 * This function tracks draft rfc3448bis, check there for latest details.
125 *
126 * Note: X and X_recv are both stored in units of 64 * bytes/second, to support
127 * fine-grained resolution of sending rates. This requires scaling by 2^6
128 * throughout the code. Only X_calc is unscaled (in bytes/second).
129 *
130 */
131 static void ccid3_hc_tx_update_x(struct sock *sk, ktime_t *stamp)
132 {
133 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
134 __u64 min_rate = 2 * hctx->ccid3hctx_x_recv;
135 const __u64 old_x = hctx->ccid3hctx_x;
136 ktime_t now = stamp ? *stamp : ktime_get_real();
137
138 /*
139 * Handle IDLE periods: do not reduce below RFC3390 initial sending rate
140 * when idling [RFC 4342, 5.1]. Definition of idling is from rfc3448bis:
141 * a sender is idle if it has not sent anything over a 2-RTT-period.
142 * For consistency with X and X_recv, min_rate is also scaled by 2^6.
143 */
144 if (ccid3_hc_tx_idle_rtt(hctx, now) >= 2) {
145 min_rate = rfc3390_initial_rate(sk);
146 min_rate = max(min_rate, 2 * hctx->ccid3hctx_x_recv);
147 }
148
149 if (hctx->ccid3hctx_p > 0) {
150
151 hctx->ccid3hctx_x = min(((__u64)hctx->ccid3hctx_x_calc) << 6,
152 min_rate);
153 hctx->ccid3hctx_x = max(hctx->ccid3hctx_x,
154 (((__u64)hctx->ccid3hctx_s) << 6) /
155 TFRC_T_MBI);
156
157 } else if (ktime_us_delta(now, hctx->ccid3hctx_t_ld)
158 - (s64)hctx->ccid3hctx_rtt >= 0) {
159
160 hctx->ccid3hctx_x = min(2 * hctx->ccid3hctx_x, min_rate);
161 hctx->ccid3hctx_x = max(hctx->ccid3hctx_x,
162 scaled_div(((__u64)hctx->ccid3hctx_s) << 6,
163 hctx->ccid3hctx_rtt));
164 hctx->ccid3hctx_t_ld = now;
165 }
166
167 if (hctx->ccid3hctx_x != old_x) {
168 ccid3_pr_debug("X_prev=%u, X_now=%u, X_calc=%u, "
169 "X_recv=%u\n", (unsigned)(old_x >> 6),
170 (unsigned)(hctx->ccid3hctx_x >> 6),
171 hctx->ccid3hctx_x_calc,
172 (unsigned)(hctx->ccid3hctx_x_recv >> 6));
173
174 ccid3_update_send_interval(hctx);
175 }
176 }
177
178 /*
179 * Track the mean packet size `s' (cf. RFC 4342, 5.3 and RFC 3448, 4.1)
180 * @len: DCCP packet payload size in bytes
181 */
182 static inline void ccid3_hc_tx_update_s(struct ccid3_hc_tx_sock *hctx, int len)
183 {
184 const u16 old_s = hctx->ccid3hctx_s;
185
186 hctx->ccid3hctx_s = tfrc_ewma(hctx->ccid3hctx_s, len, 9);
187
188 if (hctx->ccid3hctx_s != old_s)
189 ccid3_update_send_interval(hctx);
190 }
191
192 /*
193 * Update Window Counter using the algorithm from [RFC 4342, 8.1].
194 * As elsewhere, RTT > 0 is assumed by using dccp_sample_rtt().
195 */
196 static inline void ccid3_hc_tx_update_win_count(struct ccid3_hc_tx_sock *hctx,
197 ktime_t now)
198 {
199 u32 delta = ktime_us_delta(now, hctx->ccid3hctx_t_last_win_count),
200 quarter_rtts = (4 * delta) / hctx->ccid3hctx_rtt;
201
202 if (quarter_rtts > 0) {
203 hctx->ccid3hctx_t_last_win_count = now;
204 hctx->ccid3hctx_last_win_count += min(quarter_rtts, 5U);
205 hctx->ccid3hctx_last_win_count &= 0xF; /* mod 16 */
206 }
207 }
208
209 static void ccid3_hc_tx_no_feedback_timer(unsigned long data)
210 {
211 struct sock *sk = (struct sock *)data;
212 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
213 unsigned long t_nfb = USEC_PER_SEC / 5;
214
215 bh_lock_sock(sk);
216 if (sock_owned_by_user(sk)) {
217 /* Try again later. */
218 /* XXX: set some sensible MIB */
219 goto restart_timer;
220 }
221
222 ccid3_pr_debug("%s(%p, state=%s) - entry \n", dccp_role(sk), sk,
223 ccid3_tx_state_name(hctx->ccid3hctx_state));
224
225 if (hctx->ccid3hctx_state == TFRC_SSTATE_FBACK)
226 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
227 else if (hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK)
228 goto out;
229
230 /*
231 * Determine new allowed sending rate X as per draft rfc3448bis-00, 4.4
232 */
233 if (hctx->ccid3hctx_t_rto == 0 || /* no feedback received yet */
234 hctx->ccid3hctx_p == 0) {
235
236 /* halve send rate directly */
237 hctx->ccid3hctx_x = max(hctx->ccid3hctx_x / 2,
238 (((__u64)hctx->ccid3hctx_s) << 6) /
239 TFRC_T_MBI);
240 ccid3_update_send_interval(hctx);
241 } else {
242 /*
243 * Modify the cached value of X_recv
244 *
245 * If (X_calc > 2 * X_recv)
246 * X_recv = max(X_recv / 2, s / (2 * t_mbi));
247 * Else
248 * X_recv = X_calc / 4;
249 *
250 * Note that X_recv is scaled by 2^6 while X_calc is not
251 */
252 BUG_ON(hctx->ccid3hctx_p && !hctx->ccid3hctx_x_calc);
253
254 if (hctx->ccid3hctx_x_calc > (hctx->ccid3hctx_x_recv >> 5))
255 hctx->ccid3hctx_x_recv =
256 max(hctx->ccid3hctx_x_recv / 2,
257 (((__u64)hctx->ccid3hctx_s) << 6) /
258 (2 * TFRC_T_MBI));
259 else {
260 hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc;
261 hctx->ccid3hctx_x_recv <<= 4;
262 }
263 ccid3_hc_tx_update_x(sk, NULL);
264 }
265 ccid3_pr_debug("Reduced X to %llu/64 bytes/sec\n",
266 (unsigned long long)hctx->ccid3hctx_x);
267
268 /*
269 * Set new timeout for the nofeedback timer.
270 * See comments in packet_recv() regarding the value of t_RTO.
271 */
272 if (unlikely(hctx->ccid3hctx_t_rto == 0)) /* no feedback yet */
273 t_nfb = TFRC_INITIAL_TIMEOUT;
274 else
275 t_nfb = max(hctx->ccid3hctx_t_rto, 2 * hctx->ccid3hctx_t_ipi);
276
277 restart_timer:
278 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
279 jiffies + usecs_to_jiffies(t_nfb));
280 out:
281 bh_unlock_sock(sk);
282 sock_put(sk);
283 }
284
285 /*
286 * returns
287 * > 0: delay (in msecs) that should pass before actually sending
288 * = 0: can send immediately
289 * < 0: error condition; do not send packet
290 */
291 static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb)
292 {
293 struct dccp_sock *dp = dccp_sk(sk);
294 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
295 ktime_t now = ktime_get_real();
296 s64 delay;
297
298 /*
299 * This function is called only for Data and DataAck packets. Sending
300 * zero-sized Data(Ack)s is theoretically possible, but for congestion
301 * control this case is pathological - ignore it.
302 */
303 if (unlikely(skb->len == 0))
304 return -EBADMSG;
305
306 switch (hctx->ccid3hctx_state) {
307 case TFRC_SSTATE_NO_SENT:
308 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
309 (jiffies +
310 usecs_to_jiffies(TFRC_INITIAL_TIMEOUT)));
311 hctx->ccid3hctx_last_win_count = 0;
312 hctx->ccid3hctx_t_last_win_count = now;
313
314 /* Set t_0 for initial packet */
315 hctx->ccid3hctx_t_nom = now;
316
317 hctx->ccid3hctx_s = skb->len;
318
319 /*
320 * Use initial RTT sample when available: recommended by erratum
321 * to RFC 4342. This implements the initialisation procedure of
322 * draft rfc3448bis, section 4.2. Remember, X is scaled by 2^6.
323 */
324 if (dp->dccps_syn_rtt) {
325 ccid3_pr_debug("SYN RTT = %uus\n", dp->dccps_syn_rtt);
326 hctx->ccid3hctx_rtt = dp->dccps_syn_rtt;
327 hctx->ccid3hctx_x = rfc3390_initial_rate(sk);
328 hctx->ccid3hctx_t_ld = now;
329 } else {
330 /*
331 * Sender does not have RTT sample:
332 * - set fallback RTT (RFC 4340, 3.4) since a RTT value
333 * is needed in several parts (e.g. window counter);
334 * - set sending rate X_pps = 1pps as per RFC 3448, 4.2.
335 */
336 hctx->ccid3hctx_rtt = DCCP_FALLBACK_RTT;
337 hctx->ccid3hctx_x = hctx->ccid3hctx_s;
338 hctx->ccid3hctx_x <<= 6;
339 }
340 ccid3_update_send_interval(hctx);
341
342 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK);
343 break;
344 case TFRC_SSTATE_NO_FBACK:
345 case TFRC_SSTATE_FBACK:
346 delay = ktime_us_delta(hctx->ccid3hctx_t_nom, now);
347 ccid3_pr_debug("delay=%ld\n", (long)delay);
348 /*
349 * Scheduling of packet transmissions [RFC 3448, 4.6]
350 *
351 * if (t_now > t_nom - delta)
352 * // send the packet now
353 * else
354 * // send the packet in (t_nom - t_now) milliseconds.
355 */
356 if (delay - (s64)hctx->ccid3hctx_delta >= 1000)
357 return (u32)delay / 1000L;
358
359 ccid3_hc_tx_update_win_count(hctx, now);
360 break;
361 case TFRC_SSTATE_TERM:
362 DCCP_BUG("%s(%p) - Illegal state TERM", dccp_role(sk), sk);
363 return -EINVAL;
364 }
365
366 /* prepare to send now (add options etc.) */
367 dp->dccps_hc_tx_insert_options = 1;
368 DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count;
369
370 /* set the nominal send time for the next following packet */
371 hctx->ccid3hctx_t_nom = ktime_add_us(hctx->ccid3hctx_t_nom,
372 hctx->ccid3hctx_t_ipi);
373 return 0;
374 }
375
376 static void ccid3_hc_tx_packet_sent(struct sock *sk, int more,
377 unsigned int len)
378 {
379 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
380
381 ccid3_hc_tx_update_s(hctx, len);
382
383 if (tfrc_tx_hist_add(&hctx->ccid3hctx_hist, dccp_sk(sk)->dccps_gss))
384 DCCP_CRIT("packet history - out of memory!");
385 }
386
387 static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb)
388 {
389 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
390 struct ccid3_options_received *opt_recv;
391 ktime_t now;
392 unsigned long t_nfb;
393 u32 pinv, r_sample;
394
395 /* we are only interested in ACKs */
396 if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK ||
397 DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK))
398 return;
399 /* ... and only in the established state */
400 if (hctx->ccid3hctx_state != TFRC_SSTATE_FBACK &&
401 hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK)
402 return;
403
404 opt_recv = &hctx->ccid3hctx_options_received;
405 now = ktime_get_real();
406
407 /* Estimate RTT from history if ACK number is valid */
408 r_sample = tfrc_tx_hist_rtt(hctx->ccid3hctx_hist,
409 DCCP_SKB_CB(skb)->dccpd_ack_seq, now);
410 if (r_sample == 0) {
411 DCCP_WARN("%s(%p): %s with bogus ACK-%llu\n", dccp_role(sk), sk,
412 dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type),
413 (unsigned long long)DCCP_SKB_CB(skb)->dccpd_ack_seq);
414 return;
415 }
416
417 /* Update receive rate in units of 64 * bytes/second */
418 hctx->ccid3hctx_x_recv = opt_recv->ccid3or_receive_rate;
419 hctx->ccid3hctx_x_recv <<= 6;
420
421 /* Update loss event rate (which is scaled by 1e6) */
422 pinv = opt_recv->ccid3or_loss_event_rate;
423 if (pinv == ~0U || pinv == 0) /* see RFC 4342, 8.5 */
424 hctx->ccid3hctx_p = 0;
425 else /* can not exceed 100% */
426 hctx->ccid3hctx_p = scaled_div(1, pinv);
427 /*
428 * Validate new RTT sample and update moving average
429 */
430 r_sample = dccp_sample_rtt(sk, r_sample);
431 hctx->ccid3hctx_rtt = tfrc_ewma(hctx->ccid3hctx_rtt, r_sample, 9);
432 /*
433 * Update allowed sending rate X as per draft rfc3448bis-00, 4.2/3
434 */
435 if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) {
436 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK);
437
438 if (hctx->ccid3hctx_t_rto == 0) {
439 /*
440 * Initial feedback packet: Larger Initial Windows (4.2)
441 */
442 hctx->ccid3hctx_x = rfc3390_initial_rate(sk);
443 hctx->ccid3hctx_t_ld = now;
444
445 ccid3_update_send_interval(hctx);
446
447 goto done_computing_x;
448 } else if (hctx->ccid3hctx_p == 0) {
449 /*
450 * First feedback after nofeedback timer expiry (4.3)
451 */
452 goto done_computing_x;
453 }
454 }
455
456 /* Update sending rate (step 4 of [RFC 3448, 4.3]) */
457 if (hctx->ccid3hctx_p > 0)
458 hctx->ccid3hctx_x_calc =
459 tfrc_calc_x(hctx->ccid3hctx_s,
460 hctx->ccid3hctx_rtt,
461 hctx->ccid3hctx_p);
462 ccid3_hc_tx_update_x(sk, &now);
463
464 done_computing_x:
465 ccid3_pr_debug("%s(%p), RTT=%uus (sample=%uus), s=%u, "
466 "p=%u, X_calc=%u, X_recv=%u, X=%u\n",
467 dccp_role(sk),
468 sk, hctx->ccid3hctx_rtt, r_sample,
469 hctx->ccid3hctx_s, hctx->ccid3hctx_p,
470 hctx->ccid3hctx_x_calc,
471 (unsigned)(hctx->ccid3hctx_x_recv >> 6),
472 (unsigned)(hctx->ccid3hctx_x >> 6));
473
474 /* unschedule no feedback timer */
475 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
476
477 /*
478 * As we have calculated new ipi, delta, t_nom it is possible
479 * that we now can send a packet, so wake up dccp_wait_for_ccid
480 */
481 sk->sk_write_space(sk);
482
483 /*
484 * Update timeout interval for the nofeedback timer.
485 * We use a configuration option to increase the lower bound.
486 * This can help avoid triggering the nofeedback timer too
487 * often ('spinning') on LANs with small RTTs.
488 */
489 hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt,
490 (CONFIG_IP_DCCP_CCID3_RTO *
491 (USEC_PER_SEC / 1000)));
492 /*
493 * Schedule no feedback timer to expire in
494 * max(t_RTO, 2 * s/X) = max(t_RTO, 2 * t_ipi)
495 */
496 t_nfb = max(hctx->ccid3hctx_t_rto, 2 * hctx->ccid3hctx_t_ipi);
497
498 ccid3_pr_debug("%s(%p), Scheduled no feedback timer to "
499 "expire in %lu jiffies (%luus)\n",
500 dccp_role(sk),
501 sk, usecs_to_jiffies(t_nfb), t_nfb);
502
503 sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer,
504 jiffies + usecs_to_jiffies(t_nfb));
505 }
506
507 static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option,
508 unsigned char len, u16 idx,
509 unsigned char *value)
510 {
511 int rc = 0;
512 const struct dccp_sock *dp = dccp_sk(sk);
513 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
514 struct ccid3_options_received *opt_recv;
515 __be32 opt_val;
516
517 opt_recv = &hctx->ccid3hctx_options_received;
518
519 if (opt_recv->ccid3or_seqno != dp->dccps_gsr) {
520 opt_recv->ccid3or_seqno = dp->dccps_gsr;
521 opt_recv->ccid3or_loss_event_rate = ~0;
522 opt_recv->ccid3or_loss_intervals_idx = 0;
523 opt_recv->ccid3or_loss_intervals_len = 0;
524 opt_recv->ccid3or_receive_rate = 0;
525 }
526
527 switch (option) {
528 case TFRC_OPT_LOSS_EVENT_RATE:
529 if (unlikely(len != 4)) {
530 DCCP_WARN("%s(%p), invalid len %d "
531 "for TFRC_OPT_LOSS_EVENT_RATE\n",
532 dccp_role(sk), sk, len);
533 rc = -EINVAL;
534 } else {
535 opt_val = get_unaligned((__be32 *)value);
536 opt_recv->ccid3or_loss_event_rate = ntohl(opt_val);
537 ccid3_pr_debug("%s(%p), LOSS_EVENT_RATE=%u\n",
538 dccp_role(sk), sk,
539 opt_recv->ccid3or_loss_event_rate);
540 }
541 break;
542 case TFRC_OPT_LOSS_INTERVALS:
543 opt_recv->ccid3or_loss_intervals_idx = idx;
544 opt_recv->ccid3or_loss_intervals_len = len;
545 ccid3_pr_debug("%s(%p), LOSS_INTERVALS=(%u, %u)\n",
546 dccp_role(sk), sk,
547 opt_recv->ccid3or_loss_intervals_idx,
548 opt_recv->ccid3or_loss_intervals_len);
549 break;
550 case TFRC_OPT_RECEIVE_RATE:
551 if (unlikely(len != 4)) {
552 DCCP_WARN("%s(%p), invalid len %d "
553 "for TFRC_OPT_RECEIVE_RATE\n",
554 dccp_role(sk), sk, len);
555 rc = -EINVAL;
556 } else {
557 opt_val = get_unaligned((__be32 *)value);
558 opt_recv->ccid3or_receive_rate = ntohl(opt_val);
559 ccid3_pr_debug("%s(%p), RECEIVE_RATE=%u\n",
560 dccp_role(sk), sk,
561 opt_recv->ccid3or_receive_rate);
562 }
563 break;
564 }
565
566 return rc;
567 }
568
569 static int ccid3_hc_tx_init(struct ccid *ccid, struct sock *sk)
570 {
571 struct ccid3_hc_tx_sock *hctx = ccid_priv(ccid);
572
573 hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT;
574 hctx->ccid3hctx_hist = NULL;
575 setup_timer(&hctx->ccid3hctx_no_feedback_timer,
576 ccid3_hc_tx_no_feedback_timer, (unsigned long)sk);
577
578 return 0;
579 }
580
581 static void ccid3_hc_tx_exit(struct sock *sk)
582 {
583 struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk);
584
585 ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM);
586 sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
587
588 tfrc_tx_hist_purge(&hctx->ccid3hctx_hist);
589 }
590
591 static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info)
592 {
593 struct ccid3_hc_tx_sock *hctx;
594
595 /* Listen socks doesn't have a private CCID block */
596 if (sk->sk_state == DCCP_LISTEN)
597 return;
598
599 hctx = ccid3_hc_tx_sk(sk);
600 info->tcpi_rto = hctx->ccid3hctx_t_rto;
601 info->tcpi_rtt = hctx->ccid3hctx_rtt;
602 }
603
604 static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len,
605 u32 __user *optval, int __user *optlen)
606 {
607 const struct ccid3_hc_tx_sock *hctx;
608 const void *val;
609
610 /* Listen socks doesn't have a private CCID block */
611 if (sk->sk_state == DCCP_LISTEN)
612 return -EINVAL;
613
614 hctx = ccid3_hc_tx_sk(sk);
615 switch (optname) {
616 case DCCP_SOCKOPT_CCID_TX_INFO:
617 if (len < sizeof(hctx->ccid3hctx_tfrc))
618 return -EINVAL;
619 len = sizeof(hctx->ccid3hctx_tfrc);
620 val = &hctx->ccid3hctx_tfrc;
621 break;
622 default:
623 return -ENOPROTOOPT;
624 }
625
626 if (put_user(len, optlen) || copy_to_user(optval, val, len))
627 return -EFAULT;
628
629 return 0;
630 }
631
632 /*
633 * Receiver Half-Connection Routines
634 */
635
636 /* CCID3 feedback types */
637 enum ccid3_fback_type {
638 CCID3_FBACK_NONE = 0,
639 CCID3_FBACK_INITIAL,
640 CCID3_FBACK_PERIODIC,
641 CCID3_FBACK_PARAM_CHANGE
642 };
643
644 #ifdef CONFIG_IP_DCCP_CCID3_DEBUG
645 static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state)
646 {
647 static const char *const ccid3_rx_state_names[] = {
648 [TFRC_RSTATE_NO_DATA] = "NO_DATA",
649 [TFRC_RSTATE_DATA] = "DATA",
650 [TFRC_RSTATE_TERM] = "TERM",
651 };
652
653 return ccid3_rx_state_names[state];
654 }
655 #endif
656
657 static void ccid3_hc_rx_set_state(struct sock *sk,
658 enum ccid3_hc_rx_states state)
659 {
660 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
661 enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state;
662
663 ccid3_pr_debug("%s(%p) %-8.8s -> %s\n",
664 dccp_role(sk), sk, ccid3_rx_state_name(oldstate),
665 ccid3_rx_state_name(state));
666 WARN_ON(state == oldstate);
667 hcrx->ccid3hcrx_state = state;
668 }
669
670 static void ccid3_hc_rx_send_feedback(struct sock *sk,
671 const struct sk_buff *skb,
672 enum ccid3_fback_type fbtype)
673 {
674 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
675 struct dccp_sock *dp = dccp_sk(sk);
676 ktime_t now;
677 s64 delta = 0;
678
679 if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_TERM))
680 return;
681
682 now = ktime_get_real();
683
684 switch (fbtype) {
685 case CCID3_FBACK_INITIAL:
686 hcrx->ccid3hcrx_x_recv = 0;
687 hcrx->ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */
688 break;
689 case CCID3_FBACK_PARAM_CHANGE:
690 /*
691 * When parameters change (new loss or p > p_prev), we do not
692 * have a reliable estimate for R_m of [RFC 3448, 6.2] and so
693 * need to reuse the previous value of X_recv. However, when
694 * X_recv was 0 (due to early loss), this would kill X down to
695 * s/t_mbi (i.e. one packet in 64 seconds).
696 * To avoid such drastic reduction, we approximate X_recv as
697 * the number of bytes since last feedback.
698 * This is a safe fallback, since X is bounded above by X_calc.
699 */
700 if (hcrx->ccid3hcrx_x_recv > 0)
701 break;
702 /* fall through */
703 case CCID3_FBACK_PERIODIC:
704 delta = ktime_us_delta(now, hcrx->ccid3hcrx_tstamp_last_feedback);
705 if (delta <= 0)
706 DCCP_BUG("delta (%ld) <= 0", (long)delta);
707 else
708 hcrx->ccid3hcrx_x_recv =
709 scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta);
710 break;
711 default:
712 return;
713 }
714
715 ccid3_pr_debug("Interval %ldusec, X_recv=%u, 1/p=%u\n", (long)delta,
716 hcrx->ccid3hcrx_x_recv, hcrx->ccid3hcrx_pinv);
717
718 hcrx->ccid3hcrx_tstamp_last_feedback = now;
719 hcrx->ccid3hcrx_last_counter = dccp_hdr(skb)->dccph_ccval;
720 hcrx->ccid3hcrx_bytes_recv = 0;
721
722 dp->dccps_hc_rx_insert_options = 1;
723 dccp_send_ack(sk);
724 }
725
726 static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb)
727 {
728 const struct ccid3_hc_rx_sock *hcrx;
729 __be32 x_recv, pinv;
730
731 if (!(sk->sk_state == DCCP_OPEN || sk->sk_state == DCCP_PARTOPEN))
732 return 0;
733
734 hcrx = ccid3_hc_rx_sk(sk);
735
736 if (dccp_packet_without_ack(skb))
737 return 0;
738
739 x_recv = htonl(hcrx->ccid3hcrx_x_recv);
740 pinv = htonl(hcrx->ccid3hcrx_pinv);
741
742 if (dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE,
743 &pinv, sizeof(pinv)) ||
744 dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE,
745 &x_recv, sizeof(x_recv)))
746 return -1;
747
748 return 0;
749 }
750
751 /**
752 * ccid3_first_li - Implements [RFC 5348, 6.3.1]
753 *
754 * Determine the length of the first loss interval via inverse lookup.
755 * Assume that X_recv can be computed by the throughput equation
756 * s
757 * X_recv = --------
758 * R * fval
759 * Find some p such that f(p) = fval; return 1/p (scaled).
760 */
761 static u32 ccid3_first_li(struct sock *sk)
762 {
763 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
764 u32 x_recv, p, delta;
765 u64 fval;
766
767 if (hcrx->ccid3hcrx_rtt == 0) {
768 DCCP_WARN("No RTT estimate available, using fallback RTT\n");
769 hcrx->ccid3hcrx_rtt = DCCP_FALLBACK_RTT;
770 }
771
772 delta = ktime_to_us(net_timedelta(hcrx->ccid3hcrx_tstamp_last_feedback));
773 x_recv = scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta);
774 if (x_recv == 0) { /* would also trigger divide-by-zero */
775 DCCP_WARN("X_recv==0\n");
776 if ((x_recv = hcrx->ccid3hcrx_x_recv) == 0) {
777 DCCP_BUG("stored value of X_recv is zero");
778 return ~0U;
779 }
780 }
781
782 fval = scaled_div(hcrx->ccid3hcrx_s, hcrx->ccid3hcrx_rtt);
783 fval = scaled_div32(fval, x_recv);
784 p = tfrc_calc_x_reverse_lookup(fval);
785
786 ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
787 "loss rate=%u\n", dccp_role(sk), sk, x_recv, p);
788
789 return p == 0 ? ~0U : scaled_div(1, p);
790 }
791
792 static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb)
793 {
794 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
795 enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE;
796 const u64 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp;
797 const bool is_data_packet = dccp_data_packet(skb);
798
799 if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA)) {
800 if (is_data_packet) {
801 const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
802 do_feedback = CCID3_FBACK_INITIAL;
803 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA);
804 hcrx->ccid3hcrx_s = payload;
805 /*
806 * Not necessary to update ccid3hcrx_bytes_recv here,
807 * since X_recv = 0 for the first feedback packet (cf.
808 * RFC 3448, 6.3) -- gerrit
809 */
810 }
811 goto update_records;
812 }
813
814 if (tfrc_rx_hist_duplicate(&hcrx->ccid3hcrx_hist, skb))
815 return; /* done receiving */
816
817 if (is_data_packet) {
818 const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4;
819 /*
820 * Update moving-average of s and the sum of received payload bytes
821 */
822 hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload, 9);
823 hcrx->ccid3hcrx_bytes_recv += payload;
824 }
825
826 /*
827 * Perform loss detection and handle pending losses
828 */
829 if (tfrc_rx_handle_loss(&hcrx->ccid3hcrx_hist, &hcrx->ccid3hcrx_li_hist,
830 skb, ndp, ccid3_first_li, sk)) {
831 do_feedback = CCID3_FBACK_PARAM_CHANGE;
832 goto done_receiving;
833 }
834
835 if (tfrc_rx_hist_loss_pending(&hcrx->ccid3hcrx_hist))
836 return; /* done receiving */
837
838 /*
839 * Handle data packets: RTT sampling and monitoring p
840 */
841 if (unlikely(!is_data_packet))
842 goto update_records;
843
844 if (!tfrc_lh_is_initialised(&hcrx->ccid3hcrx_li_hist)) {
845 const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->ccid3hcrx_hist, skb);
846 /*
847 * Empty loss history: no loss so far, hence p stays 0.
848 * Sample RTT values, since an RTT estimate is required for the
849 * computation of p when the first loss occurs; RFC 3448, 6.3.1.
850 */
851 if (sample != 0)
852 hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9);
853
854 } else if (tfrc_lh_update_i_mean(&hcrx->ccid3hcrx_li_hist, skb)) {
855 /*
856 * Step (3) of [RFC 3448, 6.1]: Recompute I_mean and, if I_mean
857 * has decreased (resp. p has increased), send feedback now.
858 */
859 do_feedback = CCID3_FBACK_PARAM_CHANGE;
860 }
861
862 /*
863 * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3
864 */
865 if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_last_counter) > 3)
866 do_feedback = CCID3_FBACK_PERIODIC;
867
868 update_records:
869 tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_hist, skb, ndp);
870
871 done_receiving:
872 if (do_feedback)
873 ccid3_hc_rx_send_feedback(sk, skb, do_feedback);
874 }
875
876 static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk)
877 {
878 struct ccid3_hc_rx_sock *hcrx = ccid_priv(ccid);
879
880 hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA;
881 tfrc_lh_init(&hcrx->ccid3hcrx_li_hist);
882 return tfrc_rx_hist_alloc(&hcrx->ccid3hcrx_hist);
883 }
884
885 static void ccid3_hc_rx_exit(struct sock *sk)
886 {
887 struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
888
889 ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM);
890
891 tfrc_rx_hist_purge(&hcrx->ccid3hcrx_hist);
892 tfrc_lh_cleanup(&hcrx->ccid3hcrx_li_hist);
893 }
894
895 static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info)
896 {
897 const struct ccid3_hc_rx_sock *hcrx;
898
899 /* Listen socks doesn't have a private CCID block */
900 if (sk->sk_state == DCCP_LISTEN)
901 return;
902
903 hcrx = ccid3_hc_rx_sk(sk);
904 info->tcpi_ca_state = hcrx->ccid3hcrx_state;
905 info->tcpi_options |= TCPI_OPT_TIMESTAMPS;
906 info->tcpi_rcv_rtt = hcrx->ccid3hcrx_rtt;
907 }
908
909 static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len,
910 u32 __user *optval, int __user *optlen)
911 {
912 const struct ccid3_hc_rx_sock *hcrx;
913 struct tfrc_rx_info rx_info;
914 const void *val;
915
916 /* Listen socks doesn't have a private CCID block */
917 if (sk->sk_state == DCCP_LISTEN)
918 return -EINVAL;
919
920 hcrx = ccid3_hc_rx_sk(sk);
921 switch (optname) {
922 case DCCP_SOCKOPT_CCID_RX_INFO:
923 if (len < sizeof(rx_info))
924 return -EINVAL;
925 rx_info.tfrcrx_x_recv = hcrx->ccid3hcrx_x_recv;
926 rx_info.tfrcrx_rtt = hcrx->ccid3hcrx_rtt;
927 rx_info.tfrcrx_p = hcrx->ccid3hcrx_pinv == 0 ? ~0U :
928 scaled_div(1, hcrx->ccid3hcrx_pinv);
929 len = sizeof(rx_info);
930 val = &rx_info;
931 break;
932 default:
933 return -ENOPROTOOPT;
934 }
935
936 if (put_user(len, optlen) || copy_to_user(optval, val, len))
937 return -EFAULT;
938
939 return 0;
940 }
941
942 struct ccid_operations ccid3_ops = {
943 .ccid_id = DCCPC_CCID3,
944 .ccid_name = "TCP-Friendly Rate Control",
945 .ccid_hc_tx_obj_size = sizeof(struct ccid3_hc_tx_sock),
946 .ccid_hc_tx_init = ccid3_hc_tx_init,
947 .ccid_hc_tx_exit = ccid3_hc_tx_exit,
948 .ccid_hc_tx_send_packet = ccid3_hc_tx_send_packet,
949 .ccid_hc_tx_packet_sent = ccid3_hc_tx_packet_sent,
950 .ccid_hc_tx_packet_recv = ccid3_hc_tx_packet_recv,
951 .ccid_hc_tx_parse_options = ccid3_hc_tx_parse_options,
952 .ccid_hc_rx_obj_size = sizeof(struct ccid3_hc_rx_sock),
953 .ccid_hc_rx_init = ccid3_hc_rx_init,
954 .ccid_hc_rx_exit = ccid3_hc_rx_exit,
955 .ccid_hc_rx_insert_options = ccid3_hc_rx_insert_options,
956 .ccid_hc_rx_packet_recv = ccid3_hc_rx_packet_recv,
957 .ccid_hc_rx_get_info = ccid3_hc_rx_get_info,
958 .ccid_hc_tx_get_info = ccid3_hc_tx_get_info,
959 .ccid_hc_rx_getsockopt = ccid3_hc_rx_getsockopt,
960 .ccid_hc_tx_getsockopt = ccid3_hc_tx_getsockopt,
961 };
962
963 #ifdef CONFIG_IP_DCCP_CCID3_DEBUG
964 module_param(ccid3_debug, bool, 0644);
965 MODULE_PARM_DESC(ccid3_debug, "Enable CCID-3 debug messages");
966 #endif
This page took 0.052363 seconds and 6 git commands to generate.