2 * net/dccp/packet_history.c
4 * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand.
6 * An implementation of the DCCP protocol
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 - ian.mcdonald@jandi.co.nz
12 * This code also uses code from Lulea University, rereleased as GPL by its
14 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
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>.
20 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
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.
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.
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.
37 #include <linux/module.h>
38 #include <linux/string.h>
40 #include "packet_history.h"
42 struct dccp_rx_hist
*dccp_rx_hist_new(const char *name
)
44 struct dccp_rx_hist
*hist
= kmalloc(sizeof(*hist
), GFP_ATOMIC
);
45 static const char dccp_rx_hist_mask
[] = "rx_hist_%s";
51 slab_name
= kmalloc(strlen(name
) + sizeof(dccp_rx_hist_mask
) - 1,
53 if (slab_name
== NULL
)
56 sprintf(slab_name
, dccp_rx_hist_mask
, name
);
57 hist
->dccprxh_slab
= kmem_cache_create(slab_name
,
58 sizeof(struct dccp_rx_hist_entry
),
59 0, SLAB_HWCACHE_ALIGN
,
61 if (hist
->dccprxh_slab
== NULL
)
62 goto out_free_slab_name
;
73 EXPORT_SYMBOL_GPL(dccp_rx_hist_new
);
75 void dccp_rx_hist_delete(struct dccp_rx_hist
*hist
)
77 const char* name
= kmem_cache_name(hist
->dccprxh_slab
);
79 kmem_cache_destroy(hist
->dccprxh_slab
);
84 EXPORT_SYMBOL_GPL(dccp_rx_hist_delete
);
86 void dccp_rx_hist_purge(struct dccp_rx_hist
*hist
, struct list_head
*list
)
88 struct dccp_rx_hist_entry
*entry
, *next
;
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
);
96 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge
);
98 struct dccp_rx_hist_entry
*
99 dccp_rx_hist_find_data_packet(const struct list_head
*list
)
101 struct dccp_rx_hist_entry
*entry
, *packet
= NULL
;
103 list_for_each_entry(entry
, list
, dccphrx_node
)
104 if (entry
->dccphrx_type
== DCCP_PKT_DATA
||
105 entry
->dccphrx_type
== DCCP_PKT_DATAACK
) {
113 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet
);
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
)
120 struct dccp_rx_hist_entry
*entry
, *next
, *iter
;
123 iter
= dccp_rx_hist_head(rx_list
);
125 dccp_rx_hist_add_entry(rx_list
, packet
);
127 const u64 seqno
= packet
->dccphrx_seqno
;
129 if (after48(seqno
, iter
->dccphrx_seqno
))
130 dccp_rx_hist_add_entry(rx_list
, packet
);
132 if (dccp_rx_hist_entry_data_packet(iter
))
135 list_for_each_entry_continue(iter
, rx_list
,
137 if (after48(seqno
, iter
->dccphrx_seqno
)) {
138 dccp_rx_hist_add_entry(&iter
->dccphrx_node
,
143 if (dccp_rx_hist_entry_data_packet(iter
))
146 if (num_later
== TFRC_RECV_NUM_LATE_LOSS
) {
147 dccp_rx_hist_entry_delete(hist
, packet
);
152 if (num_later
< TFRC_RECV_NUM_LATE_LOSS
)
153 dccp_rx_hist_add_entry(rx_list
, packet
);
155 * FIXME: else what? should we destroy the packet
163 * Trim history (remove all packets after the NUM_LATE_LOSS + 1
166 num_later
= TFRC_RECV_NUM_LATE_LOSS
+ 1;
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
))
178 u8 win_count
= 0; /* Not needed, but lets shut up gcc */
181 * We have no loss interval history so we need at least one
182 * rtt:s of data packets to approximate rtt.
184 list_for_each_entry_safe(entry
, next
, rx_list
, dccphrx_node
) {
185 if (num_later
== 0) {
189 /* OK, find next data packet */
194 /* OK, find next data packet */
196 win_count
= entry
->dccphrx_ccval
;
199 tmp
= win_count
- entry
->dccphrx_ccval
;
201 tmp
+= TFRC_WIN_COUNT_LIMIT
;
202 if (tmp
> TFRC_WIN_COUNT_PER_RTT
+ 1) {
204 * We have found a packet older
205 * than one rtt remove the rest
208 } else /* OK, find next data packet */
212 list_del_init(&entry
->dccphrx_node
);
213 dccp_rx_hist_entry_delete(hist
, entry
);
216 } else if (dccp_rx_hist_entry_data_packet(entry
))
224 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet
);
226 u64
dccp_rx_hist_detect_loss(struct list_head
*rx_list
,
227 struct list_head
*li_list
, u8
*win_loss
)
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
;
235 list_for_each_entry_safe(entry
, next
, rx_list
, dccphrx_node
) {
236 if (num_later
== 0) {
239 } else if (dccp_rx_hist_entry_data_packet(entry
))
247 list_for_each_entry_safe_continue(entry
, next
, rx_list
, dccphrx_node
) {
248 if (num_later
== 0) {
251 } else if (dccp_rx_hist_entry_data_packet(entry
))
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",
263 LIMIT_NETDEBUG("%s: Less than 4 data pkts in history!",
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
);
276 if (dccp_rx_hist_entry_data_packet(packet
))
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.
284 if (delta
% DCCP_NDP_LIMIT
!=
285 (packet
->dccphrx_ndp
-
286 entry
->dccphrx_ndp
) % DCCP_NDP_LIMIT
)
288 if (delta
!= packet
->dccphrx_ndp
- entry
->dccphrx_ndp
) {
289 seq_loss
= entry
->dccphrx_seqno
;
290 dccp_inc_seqno(&seq_loss
);
294 if (packet
== a_loss
)
298 if (seq_loss
!= DCCP_MAX_SEQNO
+ 1)
299 *win_loss
= a_loss
->dccphrx_ccval
;
301 *win_loss
= 0; /* Paranoia */
306 EXPORT_SYMBOL_GPL(dccp_rx_hist_detect_loss
);
308 struct dccp_tx_hist
*dccp_tx_hist_new(const char *name
)
310 struct dccp_tx_hist
*hist
= kmalloc(sizeof(*hist
), GFP_ATOMIC
);
311 static const char dccp_tx_hist_mask
[] = "tx_hist_%s";
317 slab_name
= kmalloc(strlen(name
) + sizeof(dccp_tx_hist_mask
) - 1,
319 if (slab_name
== NULL
)
322 sprintf(slab_name
, dccp_tx_hist_mask
, name
);
323 hist
->dccptxh_slab
= kmem_cache_create(slab_name
,
324 sizeof(struct dccp_tx_hist_entry
),
325 0, SLAB_HWCACHE_ALIGN
,
327 if (hist
->dccptxh_slab
== NULL
)
328 goto out_free_slab_name
;
339 EXPORT_SYMBOL_GPL(dccp_tx_hist_new
);
341 void dccp_tx_hist_delete(struct dccp_tx_hist
*hist
)
343 const char* name
= kmem_cache_name(hist
->dccptxh_slab
);
345 kmem_cache_destroy(hist
->dccptxh_slab
);
350 EXPORT_SYMBOL_GPL(dccp_tx_hist_delete
);
352 struct dccp_tx_hist_entry
*
353 dccp_tx_hist_find_entry(const struct list_head
*list
, const u64 seq
)
355 struct dccp_tx_hist_entry
*packet
= NULL
, *entry
;
357 list_for_each_entry(entry
, list
, dccphtx_node
)
358 if (entry
->dccphtx_seqno
== seq
) {
366 EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry
);
368 void dccp_tx_hist_purge_older(struct dccp_tx_hist
*hist
,
369 struct list_head
*list
,
370 struct dccp_tx_hist_entry
*packet
)
372 struct dccp_tx_hist_entry
*next
;
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
);
380 EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older
);
382 void dccp_tx_hist_purge(struct dccp_tx_hist
*hist
, struct list_head
*list
)
384 struct dccp_tx_hist_entry
*entry
, *next
;
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
);
392 EXPORT_SYMBOL_GPL(dccp_tx_hist_purge
);
394 MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, "
395 "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
396 MODULE_DESCRIPTION("DCCP TFRC library");
397 MODULE_LICENSE("GPL");