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