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, | |
128 | struct timeval *last_feedback, | |
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; | |
135 | struct timeval tstamp = { 0, 0 }; | |
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)) { | |
169 | DCCP_WARN("%s(%p), Could not find a win_count interval > 0." | |
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 | ||
179 | delta = timeval_delta(&tstamp, &tail->dccphrx_tstamp); | |
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 | ||
199 | dccp_timestamp(sk, &tstamp); | |
200 | delta = timeval_delta(&tstamp, last_feedback); | |
201 | DCCP_BUG_ON(delta <= 0); | |
202 | ||
203 | x_recv = scaled_div32(bytes_recv, delta); | |
204 | if (x_recv == 0) { /* would also trigger divide-by-zero */ | |
205 | DCCP_WARN("X_recv==0\n"); | |
206 | if (previous_x_recv == 0) { | |
207 | DCCP_BUG("stored value of X_recv is zero"); | |
208 | return ~0; | |
209 | } | |
210 | x_recv = previous_x_recv; | |
211 | } | |
212 | ||
213 | fval = scaled_div(s, rtt); | |
214 | fval = scaled_div32(fval, x_recv); | |
215 | p = tfrc_calc_x_reverse_lookup(fval); | |
216 | ||
217 | dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied " | |
218 | "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); | |
219 | ||
220 | if (p == 0) | |
221 | return ~0; | |
222 | else | |
223 | return 1000000 / p; | |
224 | } | |
225 | ||
cc4d6a3a | 226 | void dccp_li_update_li(struct sock *sk, |
cc0a910b ACM |
227 | struct list_head *li_hist_list, |
228 | struct list_head *hist_list, | |
229 | struct timeval *last_feedback, u16 s, u32 bytes_recv, | |
23248005 | 230 | u32 previous_x_recv, u64 seq_loss, u8 win_loss) |
cc0a910b ACM |
231 | { |
232 | struct dccp_li_hist_entry *head; | |
233 | u64 seq_temp; | |
234 | ||
235 | if (list_empty(li_hist_list)) { | |
cc4d6a3a ACM |
236 | if (!dccp_li_hist_interval_new(li_hist_list, seq_loss, |
237 | win_loss)) | |
cc0a910b ACM |
238 | return; |
239 | ||
240 | head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, | |
241 | dccplih_node); | |
242 | head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list, | |
243 | last_feedback, | |
244 | s, bytes_recv, | |
245 | previous_x_recv); | |
246 | } else { | |
247 | struct dccp_li_hist_entry *entry; | |
248 | struct list_head *tail; | |
249 | ||
250 | head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, | |
251 | dccplih_node); | |
252 | /* FIXME win count check removed as was wrong */ | |
253 | /* should make this check with receive history */ | |
254 | /* and compare there as per section 10.2 of RFC4342 */ | |
255 | ||
256 | /* new loss event detected */ | |
257 | /* calculate last interval length */ | |
258 | seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss); | |
cc4d6a3a | 259 | entry = dccp_li_hist_entry_new(GFP_ATOMIC); |
cc0a910b ACM |
260 | |
261 | if (entry == NULL) { | |
262 | DCCP_BUG("out of memory - can not allocate entry"); | |
263 | return; | |
264 | } | |
265 | ||
266 | list_add(&entry->dccplih_node, li_hist_list); | |
267 | ||
268 | tail = li_hist_list->prev; | |
269 | list_del(tail); | |
cc4d6a3a | 270 | kmem_cache_free(dccp_li_cachep, tail); |
cc0a910b ACM |
271 | |
272 | /* Create the newest interval */ | |
273 | entry->dccplih_seqno = seq_loss; | |
274 | entry->dccplih_interval = seq_temp; | |
275 | entry->dccplih_win_count = win_loss; | |
276 | } | |
277 | } | |
278 | ||
279 | EXPORT_SYMBOL_GPL(dccp_li_update_li); | |
cc4d6a3a ACM |
280 | |
281 | static __init int dccp_li_init(void) | |
282 | { | |
283 | dccp_li_cachep = kmem_cache_create("dccp_li_hist", | |
284 | sizeof(struct dccp_li_hist_entry), | |
20c2df83 | 285 | 0, SLAB_HWCACHE_ALIGN, NULL); |
cc4d6a3a ACM |
286 | return dccp_li_cachep == NULL ? -ENOBUFS : 0; |
287 | } | |
288 | ||
289 | static __exit void dccp_li_exit(void) | |
290 | { | |
291 | kmem_cache_destroy(dccp_li_cachep); | |
292 | } | |
293 | ||
294 | module_init(dccp_li_init); | |
295 | module_exit(dccp_li_exit); |