Commit | Line | Data |
---|---|---|
8c60f3fa ACM |
1 | /* |
2 | * net/dccp/packet_history.h | |
3 | * | |
4 | * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand. | |
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 | * or e-mail Ian McDonald - iam4@cs.waikato.ac.nz | |
11 | * | |
12 | * This code also uses code from Lulea University, rereleased as GPL by its | |
13 | * authors: | |
14 | * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon | |
15 | * | |
16 | * Changes to meet Linux coding standards, to make it meet latest ccid3 draft | |
17 | * and to make it work as a loadable module in the DCCP stack written by | |
18 | * Arnaldo Carvalho de Melo <acme@conectiva.com.br>. | |
19 | * | |
20 | * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> | |
21 | * | |
22 | * This program is free software; you can redistribute it and/or modify | |
23 | * it under the terms of the GNU General Public License as published by | |
24 | * the Free Software Foundation; either version 2 of the License, or | |
25 | * (at your option) any later version. | |
26 | * | |
27 | * This program is distributed in the hope that it will be useful, | |
28 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
29 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
30 | * GNU General Public License for more details. | |
31 | * | |
32 | * You should have received a copy of the GNU General Public License | |
33 | * along with this program; if not, write to the Free Software | |
34 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
35 | */ | |
36 | ||
37 | #include <linux/config.h> | |
5cea0ddc | 38 | #include <linux/module.h> |
8c60f3fa ACM |
39 | #include <linux/string.h> |
40 | ||
41 | #include "packet_history.h" | |
42 | ||
43 | struct dccp_rx_hist *dccp_rx_hist_new(const char *name) | |
44 | { | |
45 | struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); | |
46 | static const char dccp_rx_hist_mask[] = "rx_hist_%s"; | |
47 | char *slab_name; | |
48 | ||
49 | if (hist == NULL) | |
50 | goto out; | |
51 | ||
52 | slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1, | |
53 | GFP_ATOMIC); | |
54 | if (slab_name == NULL) | |
55 | goto out_free_hist; | |
56 | ||
57 | sprintf(slab_name, dccp_rx_hist_mask, name); | |
58 | hist->dccprxh_slab = kmem_cache_create(slab_name, | |
7690af3f | 59 | sizeof(struct dccp_rx_hist_entry), |
8c60f3fa ACM |
60 | 0, SLAB_HWCACHE_ALIGN, |
61 | NULL, NULL); | |
62 | if (hist->dccprxh_slab == NULL) | |
63 | goto out_free_slab_name; | |
64 | out: | |
65 | return hist; | |
66 | out_free_slab_name: | |
67 | kfree(slab_name); | |
68 | out_free_hist: | |
69 | kfree(hist); | |
70 | hist = NULL; | |
71 | goto out; | |
72 | } | |
73 | ||
74 | EXPORT_SYMBOL_GPL(dccp_rx_hist_new); | |
75 | ||
76 | void dccp_rx_hist_delete(struct dccp_rx_hist *hist) | |
77 | { | |
78 | const char* name = kmem_cache_name(hist->dccprxh_slab); | |
79 | ||
80 | kmem_cache_destroy(hist->dccprxh_slab); | |
81 | kfree(name); | |
82 | kfree(hist); | |
83 | } | |
84 | ||
85 | EXPORT_SYMBOL_GPL(dccp_rx_hist_delete); | |
86 | ||
87 | void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list) | |
88 | { | |
89 | struct dccp_rx_hist_entry *entry, *next; | |
90 | ||
91 | list_for_each_entry_safe(entry, next, list, dccphrx_node) { | |
92 | list_del_init(&entry->dccphrx_node); | |
93 | kmem_cache_free(hist->dccprxh_slab, entry); | |
94 | } | |
95 | } | |
96 | ||
97 | EXPORT_SYMBOL_GPL(dccp_rx_hist_purge); | |
98 | ||
99 | struct dccp_rx_hist_entry * | |
100 | dccp_rx_hist_find_data_packet(const struct list_head *list) | |
101 | { | |
102 | struct dccp_rx_hist_entry *entry, *packet = NULL; | |
103 | ||
104 | list_for_each_entry(entry, list, dccphrx_node) | |
105 | if (entry->dccphrx_type == DCCP_PKT_DATA || | |
106 | entry->dccphrx_type == DCCP_PKT_DATAACK) { | |
107 | packet = entry; | |
108 | break; | |
109 | } | |
110 | ||
111 | return packet; | |
112 | } | |
113 | ||
114 | EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet); | |
115 | ||
072ab6c6 ACM |
116 | int dccp_rx_hist_add_packet(struct dccp_rx_hist *hist, |
117 | struct list_head *rx_list, | |
118 | struct list_head *li_list, | |
119 | struct dccp_rx_hist_entry *packet) | |
120 | { | |
121 | struct dccp_rx_hist_entry *entry, *next, *iter; | |
122 | u8 num_later = 0; | |
123 | ||
124 | iter = dccp_rx_hist_head(rx_list); | |
125 | if (iter == NULL) | |
126 | dccp_rx_hist_add_entry(rx_list, packet); | |
127 | else { | |
128 | const u64 seqno = packet->dccphrx_seqno; | |
129 | ||
130 | if (after48(seqno, iter->dccphrx_seqno)) | |
131 | dccp_rx_hist_add_entry(rx_list, packet); | |
132 | else { | |
133 | if (dccp_rx_hist_entry_data_packet(iter)) | |
134 | num_later = 1; | |
135 | ||
136 | list_for_each_entry_continue(iter, rx_list, | |
137 | dccphrx_node) { | |
138 | if (after48(seqno, iter->dccphrx_seqno)) { | |
139 | dccp_rx_hist_add_entry(&iter->dccphrx_node, | |
140 | packet); | |
141 | goto trim_history; | |
142 | } | |
143 | ||
144 | if (dccp_rx_hist_entry_data_packet(iter)) | |
145 | num_later++; | |
146 | ||
147 | if (num_later == TFRC_RECV_NUM_LATE_LOSS) { | |
148 | dccp_rx_hist_entry_delete(hist, packet); | |
149 | return 1; | |
150 | } | |
151 | } | |
152 | ||
153 | if (num_later < TFRC_RECV_NUM_LATE_LOSS) | |
154 | dccp_rx_hist_add_entry(rx_list, packet); | |
155 | /* | |
156 | * FIXME: else what? should we destroy the packet | |
157 | * like above? | |
158 | */ | |
159 | } | |
160 | } | |
161 | ||
162 | trim_history: | |
163 | /* | |
164 | * Trim history (remove all packets after the NUM_LATE_LOSS + 1 | |
165 | * data packets) | |
166 | */ | |
167 | num_later = TFRC_RECV_NUM_LATE_LOSS + 1; | |
168 | ||
169 | if (!list_empty(li_list)) { | |
170 | list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { | |
171 | if (num_later == 0) { | |
172 | list_del_init(&entry->dccphrx_node); | |
173 | dccp_rx_hist_entry_delete(hist, entry); | |
174 | } else if (dccp_rx_hist_entry_data_packet(entry)) | |
175 | --num_later; | |
176 | } | |
177 | } else { | |
178 | int step = 0; | |
179 | u8 win_count = 0; /* Not needed, but lets shut up gcc */ | |
180 | int tmp; | |
181 | /* | |
182 | * We have no loss interval history so we need at least one | |
183 | * rtt:s of data packets to approximate rtt. | |
184 | */ | |
185 | list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { | |
186 | if (num_later == 0) { | |
187 | switch (step) { | |
188 | case 0: | |
189 | step = 1; | |
190 | /* OK, find next data packet */ | |
191 | num_later = 1; | |
192 | break; | |
193 | case 1: | |
194 | step = 2; | |
195 | /* OK, find next data packet */ | |
196 | num_later = 1; | |
197 | win_count = entry->dccphrx_ccval; | |
198 | break; | |
199 | case 2: | |
200 | tmp = win_count - entry->dccphrx_ccval; | |
201 | if (tmp < 0) | |
202 | tmp += TFRC_WIN_COUNT_LIMIT; | |
203 | if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) { | |
204 | /* | |
205 | * We have found a packet older | |
206 | * than one rtt remove the rest | |
207 | */ | |
208 | step = 3; | |
209 | } else /* OK, find next data packet */ | |
210 | num_later = 1; | |
211 | break; | |
212 | case 3: | |
213 | list_del_init(&entry->dccphrx_node); | |
214 | dccp_rx_hist_entry_delete(hist, entry); | |
215 | break; | |
216 | } | |
217 | } else if (dccp_rx_hist_entry_data_packet(entry)) | |
218 | --num_later; | |
219 | } | |
220 | } | |
221 | ||
222 | return 0; | |
223 | } | |
224 | ||
225 | EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet); | |
226 | ||
29e4f8b3 ACM |
227 | u64 dccp_rx_hist_detect_loss(struct list_head *rx_list, |
228 | struct list_head *li_list, u8 *win_loss) | |
229 | { | |
230 | struct dccp_rx_hist_entry *entry, *next, *packet; | |
231 | struct dccp_rx_hist_entry *a_loss = NULL; | |
232 | struct dccp_rx_hist_entry *b_loss = NULL; | |
233 | u64 seq_loss = DCCP_MAX_SEQNO + 1; | |
234 | u8 num_later = TFRC_RECV_NUM_LATE_LOSS; | |
235 | ||
236 | list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { | |
237 | if (num_later == 0) { | |
238 | b_loss = entry; | |
239 | break; | |
240 | } else if (dccp_rx_hist_entry_data_packet(entry)) | |
241 | --num_later; | |
242 | } | |
243 | ||
244 | if (b_loss == NULL) | |
245 | goto out; | |
246 | ||
247 | num_later = 1; | |
248 | list_for_each_entry_safe_continue(entry, next, rx_list, dccphrx_node) { | |
249 | if (num_later == 0) { | |
250 | a_loss = entry; | |
251 | break; | |
252 | } else if (dccp_rx_hist_entry_data_packet(entry)) | |
253 | --num_later; | |
254 | } | |
255 | ||
256 | if (a_loss == NULL) { | |
257 | if (list_empty(li_list)) { | |
258 | /* no loss event have occured yet */ | |
259 | LIMIT_NETDEBUG("%s: TODO: find a lost data packet by " | |
260 | "comparing to initial seqno\n", | |
261 | __FUNCTION__); | |
262 | goto out; | |
263 | } else { | |
264 | LIMIT_NETDEBUG("%s: Less than 4 data pkts in history!", | |
265 | __FUNCTION__); | |
266 | goto out; | |
267 | } | |
268 | } | |
269 | ||
270 | /* Locate a lost data packet */ | |
271 | entry = packet = b_loss; | |
272 | list_for_each_entry_safe_continue(entry, next, rx_list, dccphrx_node) { | |
273 | u64 delta = dccp_delta_seqno(entry->dccphrx_seqno, | |
274 | packet->dccphrx_seqno); | |
275 | ||
276 | if (delta != 0) { | |
277 | if (dccp_rx_hist_entry_data_packet(packet)) | |
278 | --delta; | |
279 | /* | |
280 | * FIXME: check this, probably this % usage is because | |
281 | * in earlier drafts the ndp count was just 8 bits | |
282 | * long, but now it cam be up to 24 bits long. | |
283 | */ | |
284 | #if 0 | |
285 | if (delta % DCCP_NDP_LIMIT != | |
286 | (packet->dccphrx_ndp - | |
287 | entry->dccphrx_ndp) % DCCP_NDP_LIMIT) | |
288 | #endif | |
289 | if (delta != packet->dccphrx_ndp - entry->dccphrx_ndp) { | |
290 | seq_loss = entry->dccphrx_seqno; | |
291 | dccp_inc_seqno(&seq_loss); | |
292 | } | |
293 | } | |
294 | packet = entry; | |
295 | if (packet == a_loss) | |
296 | break; | |
297 | } | |
298 | out: | |
299 | if (seq_loss != DCCP_MAX_SEQNO + 1) | |
300 | *win_loss = a_loss->dccphrx_ccval; | |
301 | else | |
302 | *win_loss = 0; /* Paranoia */ | |
303 | ||
304 | return seq_loss; | |
305 | } | |
306 | ||
307 | EXPORT_SYMBOL_GPL(dccp_rx_hist_detect_loss); | |
308 | ||
8c60f3fa ACM |
309 | struct dccp_tx_hist *dccp_tx_hist_new(const char *name) |
310 | { | |
311 | struct dccp_tx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); | |
312 | static const char dccp_tx_hist_mask[] = "tx_hist_%s"; | |
313 | char *slab_name; | |
314 | ||
315 | if (hist == NULL) | |
316 | goto out; | |
317 | ||
318 | slab_name = kmalloc(strlen(name) + sizeof(dccp_tx_hist_mask) - 1, | |
319 | GFP_ATOMIC); | |
320 | if (slab_name == NULL) | |
321 | goto out_free_hist; | |
322 | ||
323 | sprintf(slab_name, dccp_tx_hist_mask, name); | |
324 | hist->dccptxh_slab = kmem_cache_create(slab_name, | |
7690af3f | 325 | sizeof(struct dccp_tx_hist_entry), |
8c60f3fa ACM |
326 | 0, SLAB_HWCACHE_ALIGN, |
327 | NULL, NULL); | |
328 | if (hist->dccptxh_slab == NULL) | |
329 | goto out_free_slab_name; | |
330 | out: | |
331 | return hist; | |
332 | out_free_slab_name: | |
333 | kfree(slab_name); | |
334 | out_free_hist: | |
335 | kfree(hist); | |
336 | hist = NULL; | |
337 | goto out; | |
338 | } | |
339 | ||
340 | EXPORT_SYMBOL_GPL(dccp_tx_hist_new); | |
341 | ||
342 | void dccp_tx_hist_delete(struct dccp_tx_hist *hist) | |
343 | { | |
344 | const char* name = kmem_cache_name(hist->dccptxh_slab); | |
345 | ||
346 | kmem_cache_destroy(hist->dccptxh_slab); | |
347 | kfree(name); | |
348 | kfree(hist); | |
349 | } | |
350 | ||
351 | EXPORT_SYMBOL_GPL(dccp_tx_hist_delete); | |
352 | ||
7690af3f ACM |
353 | struct dccp_tx_hist_entry * |
354 | dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq) | |
8c60f3fa ACM |
355 | { |
356 | struct dccp_tx_hist_entry *packet = NULL, *entry; | |
357 | ||
358 | list_for_each_entry(entry, list, dccphtx_node) | |
359 | if (entry->dccphtx_seqno == seq) { | |
360 | packet = entry; | |
361 | break; | |
362 | } | |
363 | ||
364 | return packet; | |
365 | } | |
366 | ||
367 | EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry); | |
368 | ||
7690af3f ACM |
369 | void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist, |
370 | struct list_head *list, | |
8c60f3fa ACM |
371 | struct dccp_tx_hist_entry *packet) |
372 | { | |
373 | struct dccp_tx_hist_entry *next; | |
374 | ||
375 | list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) { | |
376 | list_del_init(&packet->dccphtx_node); | |
377 | dccp_tx_hist_entry_delete(hist, packet); | |
378 | } | |
379 | } | |
380 | ||
381 | EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older); | |
382 | ||
383 | void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list) | |
384 | { | |
385 | struct dccp_tx_hist_entry *entry, *next; | |
386 | ||
387 | list_for_each_entry_safe(entry, next, list, dccphtx_node) { | |
388 | list_del_init(&entry->dccphtx_node); | |
389 | dccp_tx_hist_entry_delete(hist, entry); | |
390 | } | |
391 | } | |
392 | ||
393 | EXPORT_SYMBOL_GPL(dccp_tx_hist_purge); | |
5cea0ddc ACM |
394 | |
395 | MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, " | |
396 | "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>"); | |
397 | MODULE_DESCRIPTION("DCCP TFRC library"); | |
398 | MODULE_LICENSE("GPL"); |