Commit | Line | Data |
---|---|---|
ae6706f0 ACM |
1 | /* |
2 | * net/dccp/ccids/lib/loss_interval.c | |
3 | * | |
b2f41ff4 IM |
4 | * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. |
5 | * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz> | |
ae6706f0 ACM |
6 | * Copyright (c) 2005 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 | ||
ae6706f0 | 14 | #include <linux/module.h> |
66a377c5 | 15 | #include <net/sock.h> |
59348b19 | 16 | #include "../../dccp.h" |
ae6706f0 | 17 | #include "loss_interval.h" |
cc0a910b ACM |
18 | #include "packet_history.h" |
19 | #include "tfrc.h" | |
ae6706f0 ACM |
20 | |
21 | struct dccp_li_hist *dccp_li_hist_new(const char *name) | |
22 | { | |
23 | struct dccp_li_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); | |
24 | static const char dccp_li_hist_mask[] = "li_hist_%s"; | |
25 | char *slab_name; | |
26 | ||
27 | if (hist == NULL) | |
28 | goto out; | |
29 | ||
30 | slab_name = kmalloc(strlen(name) + sizeof(dccp_li_hist_mask) - 1, | |
31 | GFP_ATOMIC); | |
32 | if (slab_name == NULL) | |
33 | goto out_free_hist; | |
34 | ||
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, | |
39 | NULL, NULL); | |
40 | if (hist->dccplih_slab == NULL) | |
41 | goto out_free_slab_name; | |
42 | out: | |
43 | return hist; | |
44 | out_free_slab_name: | |
45 | kfree(slab_name); | |
46 | out_free_hist: | |
47 | kfree(hist); | |
48 | hist = NULL; | |
49 | goto out; | |
50 | } | |
51 | ||
52 | EXPORT_SYMBOL_GPL(dccp_li_hist_new); | |
53 | ||
54 | void dccp_li_hist_delete(struct dccp_li_hist *hist) | |
55 | { | |
56 | const char* name = kmem_cache_name(hist->dccplih_slab); | |
57 | ||
58 | kmem_cache_destroy(hist->dccplih_slab); | |
59 | kfree(name); | |
60 | kfree(hist); | |
61 | } | |
62 | ||
63 | EXPORT_SYMBOL_GPL(dccp_li_hist_delete); | |
64 | ||
65 | void dccp_li_hist_purge(struct dccp_li_hist *hist, struct list_head *list) | |
66 | { | |
67 | struct dccp_li_hist_entry *entry, *next; | |
68 | ||
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); | |
72 | } | |
73 | } | |
74 | ||
75 | EXPORT_SYMBOL_GPL(dccp_li_hist_purge); | |
76 | ||
77 | /* Weights used to calculate loss event rate */ | |
78 | /* | |
79 | * These are integers as per section 8 of RFC3448. We can then divide by 4 * | |
80 | * when we use it. | |
81 | */ | |
82 | static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = { | |
83 | 4, 4, 4, 4, 3, 2, 1, 1, | |
84 | }; | |
85 | ||
86 | u32 dccp_li_hist_calc_i_mean(struct list_head *list) | |
87 | { | |
88 | struct dccp_li_hist_entry *li_entry, *li_next; | |
89 | int i = 0; | |
90 | u32 i_tot; | |
91 | u32 i_tot0 = 0; | |
92 | u32 i_tot1 = 0; | |
93 | u32 w_tot = 0; | |
94 | ||
95 | list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) { | |
551dc5f7 | 96 | if (li_entry->dccplih_interval != ~0U) { |
ae6706f0 ACM |
97 | i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i]; |
98 | w_tot += dccp_li_hist_w[i]; | |
66a377c5 IM |
99 | if (i != 0) |
100 | i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1]; | |
ae6706f0 ACM |
101 | } |
102 | ||
ae6706f0 ACM |
103 | |
104 | if (++i > DCCP_LI_HIST_IVAL_F_LENGTH) | |
105 | break; | |
106 | } | |
107 | ||
108 | if (i != DCCP_LI_HIST_IVAL_F_LENGTH) | |
109 | return 0; | |
110 | ||
111 | i_tot = max(i_tot0, i_tot1); | |
112 | ||
66a377c5 | 113 | if (!w_tot) { |
59348b19 | 114 | DCCP_WARN("w_tot = 0\n"); |
66a377c5 IM |
115 | return 1; |
116 | } | |
ae6706f0 | 117 | |
66a377c5 | 118 | return i_tot / w_tot; |
ae6706f0 ACM |
119 | } |
120 | ||
121 | EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean); | |
122 | ||
8c281780 ACM |
123 | static int dccp_li_hist_interval_new(struct dccp_li_hist *hist, |
124 | struct list_head *list, | |
125 | const u64 seq_loss, const u8 win_loss) | |
ae6706f0 | 126 | { |
66a377c5 | 127 | struct dccp_li_hist_entry *entry; |
ae6706f0 ACM |
128 | int i; |
129 | ||
66a377c5 | 130 | for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) { |
54e6ecb2 | 131 | entry = dccp_li_hist_entry_new(hist, GFP_ATOMIC); |
ae6706f0 ACM |
132 | if (entry == NULL) { |
133 | dccp_li_hist_purge(hist, list); | |
59348b19 | 134 | DCCP_BUG("loss interval list entry is NULL"); |
66a377c5 | 135 | return 0; |
ae6706f0 | 136 | } |
66a377c5 | 137 | entry->dccplih_interval = ~0; |
ae6706f0 ACM |
138 | list_add(&entry->dccplih_node, list); |
139 | } | |
140 | ||
141 | entry->dccplih_seqno = seq_loss; | |
142 | entry->dccplih_win_count = win_loss; | |
66a377c5 | 143 | return 1; |
ae6706f0 ACM |
144 | } |
145 | ||
cc0a910b ACM |
146 | /* calculate first loss interval |
147 | * | |
148 | * returns estimated loss interval in usecs */ | |
149 | static u32 dccp_li_calc_first_li(struct sock *sk, | |
150 | struct list_head *hist_list, | |
151 | struct timeval *last_feedback, | |
152 | u16 s, u32 bytes_recv, | |
153 | u32 previous_x_recv) | |
154 | { | |
155 | struct dccp_rx_hist_entry *entry, *next, *tail = NULL; | |
156 | u32 x_recv, p; | |
157 | suseconds_t rtt, delta; | |
158 | struct timeval tstamp = { 0, 0 }; | |
159 | int interval = 0; | |
160 | int win_count = 0; | |
161 | int step = 0; | |
162 | u64 fval; | |
163 | ||
164 | list_for_each_entry_safe(entry, next, hist_list, dccphrx_node) { | |
165 | if (dccp_rx_hist_entry_data_packet(entry)) { | |
166 | tail = entry; | |
167 | ||
168 | switch (step) { | |
169 | case 0: | |
170 | tstamp = entry->dccphrx_tstamp; | |
171 | win_count = entry->dccphrx_ccval; | |
172 | step = 1; | |
173 | break; | |
174 | case 1: | |
175 | interval = win_count - entry->dccphrx_ccval; | |
176 | if (interval < 0) | |
177 | interval += TFRC_WIN_COUNT_LIMIT; | |
178 | if (interval > 4) | |
179 | goto found; | |
180 | break; | |
181 | } | |
182 | } | |
183 | } | |
184 | ||
185 | if (unlikely(step == 0)) { | |
186 | DCCP_WARN("%s(%p), packet history has no data packets!\n", | |
187 | dccp_role(sk), sk); | |
188 | return ~0; | |
189 | } | |
190 | ||
191 | if (unlikely(interval == 0)) { | |
192 | DCCP_WARN("%s(%p), Could not find a win_count interval > 0." | |
193 | "Defaulting to 1\n", dccp_role(sk), sk); | |
194 | interval = 1; | |
195 | } | |
196 | found: | |
197 | if (!tail) { | |
198 | DCCP_CRIT("tail is null\n"); | |
199 | return ~0; | |
200 | } | |
201 | ||
202 | delta = timeval_delta(&tstamp, &tail->dccphrx_tstamp); | |
203 | DCCP_BUG_ON(delta < 0); | |
204 | ||
205 | rtt = delta * 4 / interval; | |
206 | dccp_pr_debug("%s(%p), approximated RTT to %dus\n", | |
207 | dccp_role(sk), sk, (int)rtt); | |
208 | ||
209 | /* | |
210 | * Determine the length of the first loss interval via inverse lookup. | |
211 | * Assume that X_recv can be computed by the throughput equation | |
212 | * s | |
213 | * X_recv = -------- | |
214 | * R * fval | |
215 | * Find some p such that f(p) = fval; return 1/p [RFC 3448, 6.3.1]. | |
216 | */ | |
217 | if (rtt == 0) { /* would result in divide-by-zero */ | |
218 | DCCP_WARN("RTT==0\n"); | |
219 | return ~0; | |
220 | } | |
221 | ||
222 | dccp_timestamp(sk, &tstamp); | |
223 | delta = timeval_delta(&tstamp, last_feedback); | |
224 | DCCP_BUG_ON(delta <= 0); | |
225 | ||
226 | x_recv = scaled_div32(bytes_recv, delta); | |
227 | if (x_recv == 0) { /* would also trigger divide-by-zero */ | |
228 | DCCP_WARN("X_recv==0\n"); | |
229 | if (previous_x_recv == 0) { | |
230 | DCCP_BUG("stored value of X_recv is zero"); | |
231 | return ~0; | |
232 | } | |
233 | x_recv = previous_x_recv; | |
234 | } | |
235 | ||
236 | fval = scaled_div(s, rtt); | |
237 | fval = scaled_div32(fval, x_recv); | |
238 | p = tfrc_calc_x_reverse_lookup(fval); | |
239 | ||
240 | dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied " | |
241 | "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); | |
242 | ||
243 | if (p == 0) | |
244 | return ~0; | |
245 | else | |
246 | return 1000000 / p; | |
247 | } | |
248 | ||
249 | void dccp_li_update_li(struct sock *sk, struct dccp_li_hist *li_hist, | |
250 | struct list_head *li_hist_list, | |
251 | struct list_head *hist_list, | |
252 | struct timeval *last_feedback, u16 s, u32 bytes_recv, | |
253 | u32 previous_x_recv, u64 seq_loss, u8 win_loss) | |
254 | { | |
255 | struct dccp_li_hist_entry *head; | |
256 | u64 seq_temp; | |
257 | ||
258 | if (list_empty(li_hist_list)) { | |
259 | if (!dccp_li_hist_interval_new(li_hist, li_hist_list, | |
260 | seq_loss, win_loss)) | |
261 | return; | |
262 | ||
263 | head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, | |
264 | dccplih_node); | |
265 | head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list, | |
266 | last_feedback, | |
267 | s, bytes_recv, | |
268 | previous_x_recv); | |
269 | } else { | |
270 | struct dccp_li_hist_entry *entry; | |
271 | struct list_head *tail; | |
272 | ||
273 | head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, | |
274 | dccplih_node); | |
275 | /* FIXME win count check removed as was wrong */ | |
276 | /* should make this check with receive history */ | |
277 | /* and compare there as per section 10.2 of RFC4342 */ | |
278 | ||
279 | /* new loss event detected */ | |
280 | /* calculate last interval length */ | |
281 | seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss); | |
282 | entry = dccp_li_hist_entry_new(li_hist, GFP_ATOMIC); | |
283 | ||
284 | if (entry == NULL) { | |
285 | DCCP_BUG("out of memory - can not allocate entry"); | |
286 | return; | |
287 | } | |
288 | ||
289 | list_add(&entry->dccplih_node, li_hist_list); | |
290 | ||
291 | tail = li_hist_list->prev; | |
292 | list_del(tail); | |
293 | kmem_cache_free(li_hist->dccplih_slab, tail); | |
294 | ||
295 | /* Create the newest interval */ | |
296 | entry->dccplih_seqno = seq_loss; | |
297 | entry->dccplih_interval = seq_temp; | |
298 | entry->dccplih_win_count = win_loss; | |
299 | } | |
300 | } | |
301 | ||
302 | EXPORT_SYMBOL_GPL(dccp_li_update_li); |