Commit | Line | Data |
---|---|---|
8c60f3fa | 1 | /* |
f3166c07 | 2 | * net/dccp/packet_history.c |
8c60f3fa | 3 | * |
276f2edc ACM |
4 | * Copyright (c) 2007 The University of Aberdeen, Scotland, UK |
5 | * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. | |
8c60f3fa ACM |
6 | * |
7 | * An implementation of the DCCP protocol | |
8 | * | |
9 | * This code has been developed by the University of Waikato WAND | |
10 | * research group. For further information please see http://www.wand.net.nz/ | |
e6bccd35 | 11 | * or e-mail Ian McDonald - ian.mcdonald@jandi.co.nz |
8c60f3fa ACM |
12 | * |
13 | * This code also uses code from Lulea University, rereleased as GPL by its | |
14 | * authors: | |
15 | * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon | |
16 | * | |
17 | * Changes to meet Linux coding standards, to make it meet latest ccid3 draft | |
18 | * and to make it work as a loadable module in the DCCP stack written by | |
19 | * Arnaldo Carvalho de Melo <acme@conectiva.com.br>. | |
20 | * | |
21 | * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> | |
22 | * | |
23 | * This program is free software; you can redistribute it and/or modify | |
24 | * it under the terms of the GNU General Public License as published by | |
25 | * the Free Software Foundation; either version 2 of the License, or | |
26 | * (at your option) any later version. | |
27 | * | |
28 | * This program is distributed in the hope that it will be useful, | |
29 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
30 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
31 | * GNU General Public License for more details. | |
32 | * | |
33 | * You should have received a copy of the GNU General Public License | |
34 | * along with this program; if not, write to the Free Software | |
35 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
36 | */ | |
37 | ||
8c60f3fa | 38 | #include <linux/string.h> |
8c60f3fa ACM |
39 | #include "packet_history.h" |
40 | ||
9108d5f4 ACM |
41 | /** |
42 | * tfrc_tx_hist_entry - Simple singly-linked TX history list | |
43 | * @next: next oldest entry (LIFO order) | |
44 | * @seqno: sequence number of this entry | |
45 | * @stamp: send time of packet with sequence number @seqno | |
46 | */ | |
47 | struct tfrc_tx_hist_entry { | |
48 | struct tfrc_tx_hist_entry *next; | |
49 | u64 seqno; | |
50 | ktime_t stamp; | |
51 | }; | |
52 | ||
7af5af30 | 53 | /* |
276f2edc | 54 | * Transmitter History Routines |
7af5af30 | 55 | */ |
276f2edc | 56 | static struct kmem_cache *tfrc_tx_hist; |
7af5af30 | 57 | |
9108d5f4 | 58 | static struct tfrc_tx_hist_entry * |
276f2edc | 59 | tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno) |
7af5af30 | 60 | { |
276f2edc ACM |
61 | while (head != NULL && head->seqno != seqno) |
62 | head = head->next; | |
7af5af30 | 63 | |
276f2edc | 64 | return head; |
7af5af30 GR |
65 | } |
66 | ||
276f2edc | 67 | int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno) |
7af5af30 | 68 | { |
276f2edc ACM |
69 | struct tfrc_tx_hist_entry *entry = kmem_cache_alloc(tfrc_tx_hist, gfp_any()); |
70 | ||
71 | if (entry == NULL) | |
72 | return -ENOBUFS; | |
73 | entry->seqno = seqno; | |
74 | entry->stamp = ktime_get_real(); | |
75 | entry->next = *headp; | |
76 | *headp = entry; | |
77 | return 0; | |
7af5af30 | 78 | } |
276f2edc | 79 | EXPORT_SYMBOL_GPL(tfrc_tx_hist_add); |
7af5af30 | 80 | |
276f2edc | 81 | void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp) |
7af5af30 | 82 | { |
276f2edc | 83 | struct tfrc_tx_hist_entry *head = *headp; |
7af5af30 | 84 | |
276f2edc ACM |
85 | while (head != NULL) { |
86 | struct tfrc_tx_hist_entry *next = head->next; | |
7af5af30 | 87 | |
276f2edc ACM |
88 | kmem_cache_free(tfrc_tx_hist, head); |
89 | head = next; | |
7af5af30 | 90 | } |
7af5af30 | 91 | |
276f2edc ACM |
92 | *headp = NULL; |
93 | } | |
94 | EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge); | |
7af5af30 | 95 | |
9108d5f4 ACM |
96 | u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno, |
97 | const ktime_t now) | |
98 | { | |
99 | u32 rtt = 0; | |
100 | struct tfrc_tx_hist_entry *packet = tfrc_tx_hist_find_entry(head, seqno); | |
101 | ||
102 | if (packet != NULL) { | |
103 | rtt = ktime_us_delta(now, packet->stamp); | |
104 | /* | |
105 | * Garbage-collect older (irrelevant) entries: | |
106 | */ | |
107 | tfrc_tx_hist_purge(&packet->next); | |
108 | } | |
109 | ||
110 | return rtt; | |
111 | } | |
112 | EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt); | |
113 | ||
7af5af30 GR |
114 | /* |
115 | * Receiver History Routines | |
116 | */ | |
8c60f3fa ACM |
117 | struct dccp_rx_hist *dccp_rx_hist_new(const char *name) |
118 | { | |
119 | struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); | |
120 | static const char dccp_rx_hist_mask[] = "rx_hist_%s"; | |
121 | char *slab_name; | |
122 | ||
123 | if (hist == NULL) | |
124 | goto out; | |
125 | ||
126 | slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1, | |
127 | GFP_ATOMIC); | |
128 | if (slab_name == NULL) | |
129 | goto out_free_hist; | |
130 | ||
131 | sprintf(slab_name, dccp_rx_hist_mask, name); | |
132 | hist->dccprxh_slab = kmem_cache_create(slab_name, | |
7690af3f | 133 | sizeof(struct dccp_rx_hist_entry), |
276f2edc | 134 | 0, SLAB_HWCACHE_ALIGN, NULL); |
8c60f3fa ACM |
135 | if (hist->dccprxh_slab == NULL) |
136 | goto out_free_slab_name; | |
137 | out: | |
138 | return hist; | |
139 | out_free_slab_name: | |
140 | kfree(slab_name); | |
141 | out_free_hist: | |
142 | kfree(hist); | |
143 | hist = NULL; | |
144 | goto out; | |
145 | } | |
146 | ||
147 | EXPORT_SYMBOL_GPL(dccp_rx_hist_new); | |
148 | ||
149 | void dccp_rx_hist_delete(struct dccp_rx_hist *hist) | |
150 | { | |
151 | const char* name = kmem_cache_name(hist->dccprxh_slab); | |
152 | ||
153 | kmem_cache_destroy(hist->dccprxh_slab); | |
154 | kfree(name); | |
155 | kfree(hist); | |
156 | } | |
157 | ||
158 | EXPORT_SYMBOL_GPL(dccp_rx_hist_delete); | |
159 | ||
7af5af30 GR |
160 | int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, |
161 | u8 *ccval) | |
8c60f3fa | 162 | { |
7af5af30 | 163 | struct dccp_rx_hist_entry *packet = NULL, *entry; |
8c60f3fa | 164 | |
7af5af30 GR |
165 | list_for_each_entry(entry, list, dccphrx_node) |
166 | if (entry->dccphrx_seqno == seq) { | |
167 | packet = entry; | |
168 | break; | |
169 | } | |
8c60f3fa | 170 | |
7af5af30 GR |
171 | if (packet) |
172 | *ccval = packet->dccphrx_ccval; | |
8c60f3fa | 173 | |
7af5af30 GR |
174 | return packet != NULL; |
175 | } | |
176 | ||
177 | EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry); | |
8c60f3fa ACM |
178 | struct dccp_rx_hist_entry * |
179 | dccp_rx_hist_find_data_packet(const struct list_head *list) | |
180 | { | |
181 | struct dccp_rx_hist_entry *entry, *packet = NULL; | |
182 | ||
183 | list_for_each_entry(entry, list, dccphrx_node) | |
184 | if (entry->dccphrx_type == DCCP_PKT_DATA || | |
185 | entry->dccphrx_type == DCCP_PKT_DATAACK) { | |
186 | packet = entry; | |
187 | break; | |
188 | } | |
189 | ||
190 | return packet; | |
191 | } | |
192 | ||
193 | EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet); | |
194 | ||
66a377c5 | 195 | void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist, |
072ab6c6 ACM |
196 | struct list_head *rx_list, |
197 | struct list_head *li_list, | |
66a377c5 IM |
198 | struct dccp_rx_hist_entry *packet, |
199 | u64 nonloss_seqno) | |
072ab6c6 | 200 | { |
66a377c5 | 201 | struct dccp_rx_hist_entry *entry, *next; |
072ab6c6 ACM |
202 | u8 num_later = 0; |
203 | ||
66a377c5 | 204 | list_add(&packet->dccphrx_node, rx_list); |
072ab6c6 | 205 | |
072ab6c6 ACM |
206 | num_later = TFRC_RECV_NUM_LATE_LOSS + 1; |
207 | ||
208 | if (!list_empty(li_list)) { | |
209 | list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { | |
210 | if (num_later == 0) { | |
66a377c5 IM |
211 | if (after48(nonloss_seqno, |
212 | entry->dccphrx_seqno)) { | |
213 | list_del_init(&entry->dccphrx_node); | |
214 | dccp_rx_hist_entry_delete(hist, entry); | |
215 | } | |
072ab6c6 ACM |
216 | } else if (dccp_rx_hist_entry_data_packet(entry)) |
217 | --num_later; | |
218 | } | |
219 | } else { | |
220 | int step = 0; | |
221 | u8 win_count = 0; /* Not needed, but lets shut up gcc */ | |
222 | int tmp; | |
223 | /* | |
224 | * We have no loss interval history so we need at least one | |
225 | * rtt:s of data packets to approximate rtt. | |
226 | */ | |
227 | list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { | |
228 | if (num_later == 0) { | |
229 | switch (step) { | |
230 | case 0: | |
231 | step = 1; | |
232 | /* OK, find next data packet */ | |
233 | num_later = 1; | |
234 | break; | |
235 | case 1: | |
236 | step = 2; | |
237 | /* OK, find next data packet */ | |
238 | num_later = 1; | |
239 | win_count = entry->dccphrx_ccval; | |
240 | break; | |
241 | case 2: | |
242 | tmp = win_count - entry->dccphrx_ccval; | |
243 | if (tmp < 0) | |
244 | tmp += TFRC_WIN_COUNT_LIMIT; | |
245 | if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) { | |
246 | /* | |
247 | * We have found a packet older | |
248 | * than one rtt remove the rest | |
249 | */ | |
250 | step = 3; | |
251 | } else /* OK, find next data packet */ | |
252 | num_later = 1; | |
253 | break; | |
254 | case 3: | |
255 | list_del_init(&entry->dccphrx_node); | |
256 | dccp_rx_hist_entry_delete(hist, entry); | |
257 | break; | |
258 | } | |
259 | } else if (dccp_rx_hist_entry_data_packet(entry)) | |
260 | --num_later; | |
261 | } | |
262 | } | |
072ab6c6 ACM |
263 | } |
264 | ||
265 | EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet); | |
266 | ||
7af5af30 | 267 | void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list) |
8c60f3fa | 268 | { |
7af5af30 | 269 | struct dccp_rx_hist_entry *entry, *next; |
8c60f3fa | 270 | |
7af5af30 GR |
271 | list_for_each_entry_safe(entry, next, list, dccphrx_node) { |
272 | list_del_init(&entry->dccphrx_node); | |
273 | kmem_cache_free(hist->dccprxh_slab, entry); | |
8c60f3fa ACM |
274 | } |
275 | } | |
276 | ||
7af5af30 | 277 | EXPORT_SYMBOL_GPL(dccp_rx_hist_purge); |
8c60f3fa | 278 | |
c40616c5 | 279 | __init int packet_history_init(void) |
276f2edc | 280 | { |
276f2edc ACM |
281 | tfrc_tx_hist = kmem_cache_create("tfrc_tx_hist", |
282 | sizeof(struct tfrc_tx_hist_entry), 0, | |
283 | SLAB_HWCACHE_ALIGN, NULL); | |
276f2edc | 284 | |
c40616c5 | 285 | return tfrc_tx_hist == NULL ? -ENOBUFS : 0; |
276f2edc | 286 | } |
276f2edc | 287 | |
c40616c5 | 288 | void packet_history_exit(void) |
276f2edc ACM |
289 | { |
290 | if (tfrc_tx_hist != NULL) { | |
291 | kmem_cache_destroy(tfrc_tx_hist); | |
292 | tfrc_tx_hist = NULL; | |
293 | } | |
276f2edc | 294 | } |