2 * net/dccp/ccids/lib/loss_interval.c
4 * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
5 * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz>
6 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
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.
14 #include <linux/module.h>
16 #include "../../dccp.h"
17 #include "loss_interval.h"
18 #include "packet_history.h"
21 struct dccp_li_hist
*dccp_li_hist_new(const char *name
)
23 struct dccp_li_hist
*hist
= kmalloc(sizeof(*hist
), GFP_ATOMIC
);
24 static const char dccp_li_hist_mask
[] = "li_hist_%s";
30 slab_name
= kmalloc(strlen(name
) + sizeof(dccp_li_hist_mask
) - 1,
32 if (slab_name
== NULL
)
35 sprintf(slab_name
, dccp_li_hist_mask
, name
);
36 hist
->dccplih_slab
= kmem_cache_create(slab_name
,
37 sizeof(struct dccp_li_hist_entry
),
38 0, SLAB_HWCACHE_ALIGN
,
40 if (hist
->dccplih_slab
== NULL
)
41 goto out_free_slab_name
;
52 EXPORT_SYMBOL_GPL(dccp_li_hist_new
);
54 void dccp_li_hist_delete(struct dccp_li_hist
*hist
)
56 const char* name
= kmem_cache_name(hist
->dccplih_slab
);
58 kmem_cache_destroy(hist
->dccplih_slab
);
63 EXPORT_SYMBOL_GPL(dccp_li_hist_delete
);
65 void dccp_li_hist_purge(struct dccp_li_hist
*hist
, struct list_head
*list
)
67 struct dccp_li_hist_entry
*entry
, *next
;
69 list_for_each_entry_safe(entry
, next
, list
, dccplih_node
) {
70 list_del_init(&entry
->dccplih_node
);
71 kmem_cache_free(hist
->dccplih_slab
, entry
);
75 EXPORT_SYMBOL_GPL(dccp_li_hist_purge
);
77 /* Weights used to calculate loss event rate */
79 * These are integers as per section 8 of RFC3448. We can then divide by 4 *
82 static const int dccp_li_hist_w
[DCCP_LI_HIST_IVAL_F_LENGTH
] = {
83 4, 4, 4, 4, 3, 2, 1, 1,
86 u32
dccp_li_hist_calc_i_mean(struct list_head
*list
)
88 struct dccp_li_hist_entry
*li_entry
, *li_next
;
95 list_for_each_entry_safe(li_entry
, li_next
, list
, dccplih_node
) {
96 if (li_entry
->dccplih_interval
!= ~0U) {
97 i_tot0
+= li_entry
->dccplih_interval
* dccp_li_hist_w
[i
];
98 w_tot
+= dccp_li_hist_w
[i
];
100 i_tot1
+= li_entry
->dccplih_interval
* dccp_li_hist_w
[i
- 1];
104 if (++i
> DCCP_LI_HIST_IVAL_F_LENGTH
)
108 if (i
!= DCCP_LI_HIST_IVAL_F_LENGTH
)
111 i_tot
= max(i_tot0
, i_tot1
);
114 DCCP_WARN("w_tot = 0\n");
118 return i_tot
/ w_tot
;
121 EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean
);
123 int dccp_li_hist_interval_new(struct dccp_li_hist
*hist
,
124 struct list_head
*list
, const u64 seq_loss
, const u8 win_loss
)
126 struct dccp_li_hist_entry
*entry
;
129 for (i
= 0; i
< DCCP_LI_HIST_IVAL_F_LENGTH
; i
++) {
130 entry
= dccp_li_hist_entry_new(hist
, GFP_ATOMIC
);
132 dccp_li_hist_purge(hist
, list
);
133 DCCP_BUG("loss interval list entry is NULL");
136 entry
->dccplih_interval
= ~0;
137 list_add(&entry
->dccplih_node
, list
);
140 entry
->dccplih_seqno
= seq_loss
;
141 entry
->dccplih_win_count
= win_loss
;
145 EXPORT_SYMBOL_GPL(dccp_li_hist_interval_new
);
147 /* calculate first loss interval
149 * returns estimated loss interval in usecs */
150 static u32
dccp_li_calc_first_li(struct sock
*sk
,
151 struct list_head
*hist_list
,
152 struct timeval
*last_feedback
,
153 u16 s
, u32 bytes_recv
,
156 struct dccp_rx_hist_entry
*entry
, *next
, *tail
= NULL
;
158 suseconds_t rtt
, delta
;
159 struct timeval tstamp
= { 0, 0 };
165 list_for_each_entry_safe(entry
, next
, hist_list
, dccphrx_node
) {
166 if (dccp_rx_hist_entry_data_packet(entry
)) {
171 tstamp
= entry
->dccphrx_tstamp
;
172 win_count
= entry
->dccphrx_ccval
;
176 interval
= win_count
- entry
->dccphrx_ccval
;
178 interval
+= TFRC_WIN_COUNT_LIMIT
;
186 if (unlikely(step
== 0)) {
187 DCCP_WARN("%s(%p), packet history has no data packets!\n",
192 if (unlikely(interval
== 0)) {
193 DCCP_WARN("%s(%p), Could not find a win_count interval > 0."
194 "Defaulting to 1\n", dccp_role(sk
), sk
);
199 DCCP_CRIT("tail is null\n");
203 delta
= timeval_delta(&tstamp
, &tail
->dccphrx_tstamp
);
204 DCCP_BUG_ON(delta
< 0);
206 rtt
= delta
* 4 / interval
;
207 dccp_pr_debug("%s(%p), approximated RTT to %dus\n",
208 dccp_role(sk
), sk
, (int)rtt
);
211 * Determine the length of the first loss interval via inverse lookup.
212 * Assume that X_recv can be computed by the throughput equation
216 * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1].
218 if (rtt
== 0) { /* would result in divide-by-zero */
219 DCCP_WARN("RTT==0\n");
223 dccp_timestamp(sk
, &tstamp
);
224 delta
= timeval_delta(&tstamp
, last_feedback
);
225 DCCP_BUG_ON(delta
<= 0);
227 x_recv
= scaled_div32(bytes_recv
, delta
);
228 if (x_recv
== 0) { /* would also trigger divide-by-zero */
229 DCCP_WARN("X_recv==0\n");
230 if (previous_x_recv
== 0) {
231 DCCP_BUG("stored value of X_recv is zero");
234 x_recv
= previous_x_recv
;
237 fval
= scaled_div(s
, rtt
);
238 fval
= scaled_div32(fval
, x_recv
);
239 p
= tfrc_calc_x_reverse_lookup(fval
);
241 dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied "
242 "loss rate=%u\n", dccp_role(sk
), sk
, x_recv
, p
);
250 void dccp_li_update_li(struct sock
*sk
, struct dccp_li_hist
*li_hist
,
251 struct list_head
*li_hist_list
,
252 struct list_head
*hist_list
,
253 struct timeval
*last_feedback
, u16 s
, u32 bytes_recv
,
254 u32 previous_x_recv
, u64 seq_loss
, u8 win_loss
)
256 struct dccp_li_hist_entry
*head
;
259 if (list_empty(li_hist_list
)) {
260 if (!dccp_li_hist_interval_new(li_hist
, li_hist_list
,
264 head
= list_entry(li_hist_list
->next
, struct dccp_li_hist_entry
,
266 head
->dccplih_interval
= dccp_li_calc_first_li(sk
, hist_list
,
271 struct dccp_li_hist_entry
*entry
;
272 struct list_head
*tail
;
274 head
= list_entry(li_hist_list
->next
, struct dccp_li_hist_entry
,
276 /* FIXME win count check removed as was wrong */
277 /* should make this check with receive history */
278 /* and compare there as per section 10.2 of RFC4342 */
280 /* new loss event detected */
281 /* calculate last interval length */
282 seq_temp
= dccp_delta_seqno(head
->dccplih_seqno
, seq_loss
);
283 entry
= dccp_li_hist_entry_new(li_hist
, GFP_ATOMIC
);
286 DCCP_BUG("out of memory - can not allocate entry");
290 list_add(&entry
->dccplih_node
, li_hist_list
);
292 tail
= li_hist_list
->prev
;
294 kmem_cache_free(li_hist
->dccplih_slab
, tail
);
296 /* Create the newest interval */
297 entry
->dccplih_seqno
= seq_loss
;
298 entry
->dccplih_interval
= seq_temp
;
299 entry
->dccplih_win_count
= win_loss
;
303 EXPORT_SYMBOL_GPL(dccp_li_update_li
);