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