]>
Commit | Line | Data |
---|---|---|
e19f9759 | 1 | /* Copyright (C) 2013-2014 B.A.T.M.A.N. contributors: |
610bfc6b MH |
2 | * |
3 | * Martin Hundebøll <martin@hundeboll.net> | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or | |
6 | * modify it under the terms of version 2 of the GNU General Public | |
7 | * License as published by the Free Software Foundation. | |
8 | * | |
9 | * This program is distributed in the hope that it will be useful, but | |
10 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
12 | * General Public License for more details. | |
13 | * | |
14 | * You should have received a copy of the GNU General Public License | |
ebf38fb7 | 15 | * along with this program; if not, see <http://www.gnu.org/licenses/>. |
610bfc6b MH |
16 | */ |
17 | ||
18 | #include "main.h" | |
19 | #include "fragmentation.h" | |
20 | #include "send.h" | |
21 | #include "originator.h" | |
22 | #include "routing.h" | |
23 | #include "hard-interface.h" | |
24 | #include "soft-interface.h" | |
25 | ||
26 | ||
27 | /** | |
28 | * batadv_frag_clear_chain - delete entries in the fragment buffer chain | |
29 | * @head: head of chain with entries. | |
30 | * | |
31 | * Free fragments in the passed hlist. Should be called with appropriate lock. | |
32 | */ | |
33 | static void batadv_frag_clear_chain(struct hlist_head *head) | |
34 | { | |
35 | struct batadv_frag_list_entry *entry; | |
36 | struct hlist_node *node; | |
37 | ||
38 | hlist_for_each_entry_safe(entry, node, head, list) { | |
39 | hlist_del(&entry->list); | |
40 | kfree_skb(entry->skb); | |
41 | kfree(entry); | |
42 | } | |
43 | } | |
44 | ||
45 | /** | |
46 | * batadv_frag_purge_orig - free fragments associated to an orig | |
47 | * @orig_node: originator to free fragments from | |
48 | * @check_cb: optional function to tell if an entry should be purged | |
49 | */ | |
50 | void batadv_frag_purge_orig(struct batadv_orig_node *orig_node, | |
51 | bool (*check_cb)(struct batadv_frag_table_entry *)) | |
52 | { | |
53 | struct batadv_frag_table_entry *chain; | |
54 | uint8_t i; | |
55 | ||
56 | for (i = 0; i < BATADV_FRAG_BUFFER_COUNT; i++) { | |
57 | chain = &orig_node->fragments[i]; | |
58 | spin_lock_bh(&orig_node->fragments[i].lock); | |
59 | ||
60 | if (!check_cb || check_cb(chain)) { | |
61 | batadv_frag_clear_chain(&orig_node->fragments[i].head); | |
62 | orig_node->fragments[i].size = 0; | |
63 | } | |
64 | ||
65 | spin_unlock_bh(&orig_node->fragments[i].lock); | |
66 | } | |
67 | } | |
68 | ||
69 | /** | |
70 | * batadv_frag_size_limit - maximum possible size of packet to be fragmented | |
71 | * | |
72 | * Returns the maximum size of payload that can be fragmented. | |
73 | */ | |
74 | static int batadv_frag_size_limit(void) | |
75 | { | |
76 | int limit = BATADV_FRAG_MAX_FRAG_SIZE; | |
77 | ||
78 | limit -= sizeof(struct batadv_frag_packet); | |
79 | limit *= BATADV_FRAG_MAX_FRAGMENTS; | |
80 | ||
81 | return limit; | |
82 | } | |
83 | ||
84 | /** | |
85 | * batadv_frag_init_chain - check and prepare fragment chain for new fragment | |
86 | * @chain: chain in fragments table to init | |
87 | * @seqno: sequence number of the received fragment | |
88 | * | |
89 | * Make chain ready for a fragment with sequence number "seqno". Delete existing | |
90 | * entries if they have an "old" sequence number. | |
91 | * | |
92 | * Caller must hold chain->lock. | |
93 | * | |
94 | * Returns true if chain is empty and caller can just insert the new fragment | |
95 | * without searching for the right position. | |
96 | */ | |
97 | static bool batadv_frag_init_chain(struct batadv_frag_table_entry *chain, | |
98 | uint16_t seqno) | |
99 | { | |
100 | if (chain->seqno == seqno) | |
101 | return false; | |
102 | ||
103 | if (!hlist_empty(&chain->head)) | |
104 | batadv_frag_clear_chain(&chain->head); | |
105 | ||
106 | chain->size = 0; | |
107 | chain->seqno = seqno; | |
108 | ||
109 | return true; | |
110 | } | |
111 | ||
112 | /** | |
113 | * batadv_frag_insert_packet - insert a fragment into a fragment chain | |
114 | * @orig_node: originator that the fragment was received from | |
115 | * @skb: skb to insert | |
116 | * @chain_out: list head to attach complete chains of fragments to | |
117 | * | |
118 | * Insert a new fragment into the reverse ordered chain in the right table | |
119 | * entry. The hash table entry is cleared if "old" fragments exist in it. | |
120 | * | |
121 | * Returns true if skb is buffered, false on error. If the chain has all the | |
122 | * fragments needed to merge the packet, the chain is moved to the passed head | |
123 | * to avoid locking the chain in the table. | |
124 | */ | |
125 | static bool batadv_frag_insert_packet(struct batadv_orig_node *orig_node, | |
126 | struct sk_buff *skb, | |
127 | struct hlist_head *chain_out) | |
128 | { | |
129 | struct batadv_frag_table_entry *chain; | |
130 | struct batadv_frag_list_entry *frag_entry_new = NULL, *frag_entry_curr; | |
131 | struct batadv_frag_packet *frag_packet; | |
132 | uint8_t bucket; | |
133 | uint16_t seqno, hdr_size = sizeof(struct batadv_frag_packet); | |
134 | bool ret = false; | |
135 | ||
136 | /* Linearize packet to avoid linearizing 16 packets in a row when doing | |
137 | * the later merge. Non-linear merge should be added to remove this | |
138 | * linearization. | |
139 | */ | |
140 | if (skb_linearize(skb) < 0) | |
141 | goto err; | |
142 | ||
143 | frag_packet = (struct batadv_frag_packet *)skb->data; | |
144 | seqno = ntohs(frag_packet->seqno); | |
145 | bucket = seqno % BATADV_FRAG_BUFFER_COUNT; | |
146 | ||
147 | frag_entry_new = kmalloc(sizeof(*frag_entry_new), GFP_ATOMIC); | |
148 | if (!frag_entry_new) | |
149 | goto err; | |
150 | ||
151 | frag_entry_new->skb = skb; | |
152 | frag_entry_new->no = frag_packet->no; | |
153 | ||
154 | /* Select entry in the "chain table" and delete any prior fragments | |
155 | * with another sequence number. batadv_frag_init_chain() returns true, | |
156 | * if the list is empty at return. | |
157 | */ | |
158 | chain = &orig_node->fragments[bucket]; | |
159 | spin_lock_bh(&chain->lock); | |
160 | if (batadv_frag_init_chain(chain, seqno)) { | |
161 | hlist_add_head(&frag_entry_new->list, &chain->head); | |
162 | chain->size = skb->len - hdr_size; | |
163 | chain->timestamp = jiffies; | |
164 | ret = true; | |
165 | goto out; | |
166 | } | |
167 | ||
168 | /* Find the position for the new fragment. */ | |
169 | hlist_for_each_entry(frag_entry_curr, &chain->head, list) { | |
170 | /* Drop packet if fragment already exists. */ | |
171 | if (frag_entry_curr->no == frag_entry_new->no) | |
172 | goto err_unlock; | |
173 | ||
174 | /* Order fragments from highest to lowest. */ | |
175 | if (frag_entry_curr->no < frag_entry_new->no) { | |
176 | hlist_add_before(&frag_entry_new->list, | |
177 | &frag_entry_curr->list); | |
178 | chain->size += skb->len - hdr_size; | |
179 | chain->timestamp = jiffies; | |
180 | ret = true; | |
181 | goto out; | |
182 | } | |
183 | } | |
184 | ||
185 | /* Reached the end of the list, so insert after 'frag_entry_curr'. */ | |
186 | if (likely(frag_entry_curr)) { | |
187 | hlist_add_after(&frag_entry_curr->list, &frag_entry_new->list); | |
188 | chain->size += skb->len - hdr_size; | |
189 | chain->timestamp = jiffies; | |
190 | ret = true; | |
191 | } | |
192 | ||
193 | out: | |
194 | if (chain->size > batadv_frag_size_limit() || | |
195 | ntohs(frag_packet->total_size) > batadv_frag_size_limit()) { | |
196 | /* Clear chain if total size of either the list or the packet | |
197 | * exceeds the maximum size of one merged packet. | |
198 | */ | |
199 | batadv_frag_clear_chain(&chain->head); | |
200 | chain->size = 0; | |
201 | } else if (ntohs(frag_packet->total_size) == chain->size) { | |
202 | /* All fragments received. Hand over chain to caller. */ | |
203 | hlist_move_list(&chain->head, chain_out); | |
204 | chain->size = 0; | |
205 | } | |
206 | ||
207 | err_unlock: | |
208 | spin_unlock_bh(&chain->lock); | |
209 | ||
210 | err: | |
211 | if (!ret) | |
212 | kfree(frag_entry_new); | |
213 | ||
214 | return ret; | |
215 | } | |
216 | ||
217 | /** | |
218 | * batadv_frag_merge_packets - merge a chain of fragments | |
219 | * @chain: head of chain with fragments | |
220 | * @skb: packet with total size of skb after merging | |
221 | * | |
222 | * Expand the first skb in the chain and copy the content of the remaining | |
223 | * skb's into the expanded one. After doing so, clear the chain. | |
224 | * | |
225 | * Returns the merged skb or NULL on error. | |
226 | */ | |
227 | static struct sk_buff * | |
228 | batadv_frag_merge_packets(struct hlist_head *chain, struct sk_buff *skb) | |
229 | { | |
230 | struct batadv_frag_packet *packet; | |
231 | struct batadv_frag_list_entry *entry; | |
232 | struct sk_buff *skb_out = NULL; | |
233 | int size, hdr_size = sizeof(struct batadv_frag_packet); | |
234 | ||
235 | /* Make sure incoming skb has non-bogus data. */ | |
236 | packet = (struct batadv_frag_packet *)skb->data; | |
237 | size = ntohs(packet->total_size); | |
238 | if (size > batadv_frag_size_limit()) | |
239 | goto free; | |
240 | ||
241 | /* Remove first entry, as this is the destination for the rest of the | |
242 | * fragments. | |
243 | */ | |
244 | entry = hlist_entry(chain->first, struct batadv_frag_list_entry, list); | |
245 | hlist_del(&entry->list); | |
246 | skb_out = entry->skb; | |
247 | kfree(entry); | |
248 | ||
249 | /* Make room for the rest of the fragments. */ | |
250 | if (pskb_expand_head(skb_out, 0, size - skb->len, GFP_ATOMIC) < 0) { | |
251 | kfree_skb(skb_out); | |
252 | skb_out = NULL; | |
253 | goto free; | |
254 | } | |
255 | ||
256 | /* Move the existing MAC header to just before the payload. (Override | |
257 | * the fragment header.) | |
258 | */ | |
259 | skb_pull_rcsum(skb_out, hdr_size); | |
260 | memmove(skb_out->data - ETH_HLEN, skb_mac_header(skb_out), ETH_HLEN); | |
261 | skb_set_mac_header(skb_out, -ETH_HLEN); | |
262 | skb_reset_network_header(skb_out); | |
263 | skb_reset_transport_header(skb_out); | |
264 | ||
265 | /* Copy the payload of the each fragment into the last skb */ | |
266 | hlist_for_each_entry(entry, chain, list) { | |
267 | size = entry->skb->len - hdr_size; | |
268 | memcpy(skb_put(skb_out, size), entry->skb->data + hdr_size, | |
269 | size); | |
270 | } | |
271 | ||
272 | free: | |
273 | /* Locking is not needed, because 'chain' is not part of any orig. */ | |
274 | batadv_frag_clear_chain(chain); | |
275 | return skb_out; | |
276 | } | |
277 | ||
278 | /** | |
279 | * batadv_frag_skb_buffer - buffer fragment for later merge | |
280 | * @skb: skb to buffer | |
281 | * @orig_node_src: originator that the skb is received from | |
282 | * | |
283 | * Add fragment to buffer and merge fragments if possible. | |
284 | * | |
285 | * There are three possible outcomes: 1) Packet is merged: Return true and | |
286 | * set *skb to merged packet; 2) Packet is buffered: Return true and set *skb | |
287 | * to NULL; 3) Error: Return false and leave skb as is. | |
288 | */ | |
289 | bool batadv_frag_skb_buffer(struct sk_buff **skb, | |
290 | struct batadv_orig_node *orig_node_src) | |
291 | { | |
292 | struct sk_buff *skb_out = NULL; | |
293 | struct hlist_head head = HLIST_HEAD_INIT; | |
294 | bool ret = false; | |
295 | ||
296 | /* Add packet to buffer and table entry if merge is possible. */ | |
297 | if (!batadv_frag_insert_packet(orig_node_src, *skb, &head)) | |
298 | goto out_err; | |
299 | ||
300 | /* Leave if more fragments are needed to merge. */ | |
301 | if (hlist_empty(&head)) | |
302 | goto out; | |
303 | ||
304 | skb_out = batadv_frag_merge_packets(&head, *skb); | |
305 | if (!skb_out) | |
306 | goto out_err; | |
307 | ||
308 | out: | |
309 | *skb = skb_out; | |
310 | ret = true; | |
311 | out_err: | |
312 | return ret; | |
313 | } | |
314 | ||
315 | /** | |
316 | * batadv_frag_skb_fwd - forward fragments that would exceed MTU when merged | |
317 | * @skb: skb to forward | |
318 | * @recv_if: interface that the skb is received on | |
319 | * @orig_node_src: originator that the skb is received from | |
320 | * | |
321 | * Look up the next-hop of the fragments payload and check if the merged packet | |
322 | * will exceed the MTU towards the next-hop. If so, the fragment is forwarded | |
323 | * without merging it. | |
324 | * | |
325 | * Returns true if the fragment is consumed/forwarded, false otherwise. | |
326 | */ | |
327 | bool batadv_frag_skb_fwd(struct sk_buff *skb, | |
328 | struct batadv_hard_iface *recv_if, | |
329 | struct batadv_orig_node *orig_node_src) | |
330 | { | |
331 | struct batadv_priv *bat_priv = netdev_priv(recv_if->soft_iface); | |
332 | struct batadv_orig_node *orig_node_dst = NULL; | |
333 | struct batadv_neigh_node *neigh_node = NULL; | |
334 | struct batadv_frag_packet *packet; | |
335 | uint16_t total_size; | |
336 | bool ret = false; | |
337 | ||
338 | packet = (struct batadv_frag_packet *)skb->data; | |
339 | orig_node_dst = batadv_orig_hash_find(bat_priv, packet->dest); | |
340 | if (!orig_node_dst) | |
341 | goto out; | |
342 | ||
343 | neigh_node = batadv_find_router(bat_priv, orig_node_dst, recv_if); | |
344 | if (!neigh_node) | |
345 | goto out; | |
346 | ||
347 | /* Forward the fragment, if the merged packet would be too big to | |
348 | * be assembled. | |
349 | */ | |
350 | total_size = ntohs(packet->total_size); | |
351 | if (total_size > neigh_node->if_incoming->net_dev->mtu) { | |
352 | batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_FWD); | |
353 | batadv_add_counter(bat_priv, BATADV_CNT_FRAG_FWD_BYTES, | |
354 | skb->len + ETH_HLEN); | |
355 | ||
a40d9b07 | 356 | packet->ttl--; |
610bfc6b MH |
357 | batadv_send_skb_packet(skb, neigh_node->if_incoming, |
358 | neigh_node->addr); | |
359 | ret = true; | |
360 | } | |
361 | ||
362 | out: | |
363 | if (orig_node_dst) | |
364 | batadv_orig_node_free_ref(orig_node_dst); | |
365 | if (neigh_node) | |
366 | batadv_neigh_node_free_ref(neigh_node); | |
367 | return ret; | |
368 | } | |
ee75ed88 MH |
369 | |
370 | /** | |
371 | * batadv_frag_create - create a fragment from skb | |
372 | * @skb: skb to create fragment from | |
373 | * @frag_head: header to use in new fragment | |
374 | * @mtu: size of new fragment | |
375 | * | |
376 | * Split the passed skb into two fragments: A new one with size matching the | |
377 | * passed mtu and the old one with the rest. The new skb contains data from the | |
378 | * tail of the old skb. | |
379 | * | |
380 | * Returns the new fragment, NULL on error. | |
381 | */ | |
382 | static struct sk_buff *batadv_frag_create(struct sk_buff *skb, | |
383 | struct batadv_frag_packet *frag_head, | |
384 | unsigned int mtu) | |
385 | { | |
386 | struct sk_buff *skb_fragment; | |
387 | unsigned header_size = sizeof(*frag_head); | |
388 | unsigned fragment_size = mtu - header_size; | |
389 | ||
390 | skb_fragment = netdev_alloc_skb(NULL, mtu + ETH_HLEN); | |
391 | if (!skb_fragment) | |
392 | goto err; | |
393 | ||
394 | skb->priority = TC_PRIO_CONTROL; | |
395 | ||
396 | /* Eat the last mtu-bytes of the skb */ | |
397 | skb_reserve(skb_fragment, header_size + ETH_HLEN); | |
398 | skb_split(skb, skb_fragment, skb->len - fragment_size); | |
399 | ||
400 | /* Add the header */ | |
401 | skb_push(skb_fragment, header_size); | |
402 | memcpy(skb_fragment->data, frag_head, header_size); | |
403 | ||
404 | err: | |
405 | return skb_fragment; | |
406 | } | |
407 | ||
408 | /** | |
409 | * batadv_frag_send_packet - create up to 16 fragments from the passed skb | |
410 | * @skb: skb to create fragments from | |
411 | * @orig_node: final destination of the created fragments | |
412 | * @neigh_node: next-hop of the created fragments | |
413 | * | |
414 | * Returns true on success, false otherwise. | |
415 | */ | |
416 | bool batadv_frag_send_packet(struct sk_buff *skb, | |
417 | struct batadv_orig_node *orig_node, | |
418 | struct batadv_neigh_node *neigh_node) | |
419 | { | |
420 | struct batadv_priv *bat_priv; | |
421 | struct batadv_hard_iface *primary_if; | |
422 | struct batadv_frag_packet frag_header; | |
423 | struct sk_buff *skb_fragment; | |
424 | unsigned mtu = neigh_node->if_incoming->net_dev->mtu; | |
425 | unsigned header_size = sizeof(frag_header); | |
426 | unsigned max_fragment_size, max_packet_size; | |
427 | ||
428 | /* To avoid merge and refragmentation at next-hops we never send | |
429 | * fragments larger than BATADV_FRAG_MAX_FRAG_SIZE | |
430 | */ | |
431 | mtu = min_t(unsigned, mtu, BATADV_FRAG_MAX_FRAG_SIZE); | |
432 | max_fragment_size = (mtu - header_size - ETH_HLEN); | |
433 | max_packet_size = max_fragment_size * BATADV_FRAG_MAX_FRAGMENTS; | |
434 | ||
435 | /* Don't even try to fragment, if we need more than 16 fragments */ | |
436 | if (skb->len > max_packet_size) | |
437 | goto out_err; | |
438 | ||
439 | bat_priv = orig_node->bat_priv; | |
440 | primary_if = batadv_primary_if_get_selected(bat_priv); | |
441 | if (!primary_if) | |
442 | goto out_err; | |
443 | ||
444 | /* Create one header to be copied to all fragments */ | |
a40d9b07 SW |
445 | frag_header.packet_type = BATADV_UNICAST_FRAG; |
446 | frag_header.version = BATADV_COMPAT_VERSION; | |
447 | frag_header.ttl = BATADV_TTL; | |
ee75ed88 MH |
448 | frag_header.seqno = htons(atomic_inc_return(&bat_priv->frag_seqno)); |
449 | frag_header.reserved = 0; | |
450 | frag_header.no = 0; | |
451 | frag_header.total_size = htons(skb->len); | |
452 | memcpy(frag_header.orig, primary_if->net_dev->dev_addr, ETH_ALEN); | |
453 | memcpy(frag_header.dest, orig_node->orig, ETH_ALEN); | |
454 | ||
455 | /* Eat and send fragments from the tail of skb */ | |
456 | while (skb->len > max_fragment_size) { | |
457 | skb_fragment = batadv_frag_create(skb, &frag_header, mtu); | |
458 | if (!skb_fragment) | |
459 | goto out_err; | |
460 | ||
461 | batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_TX); | |
462 | batadv_add_counter(bat_priv, BATADV_CNT_FRAG_TX_BYTES, | |
463 | skb_fragment->len + ETH_HLEN); | |
464 | batadv_send_skb_packet(skb_fragment, neigh_node->if_incoming, | |
465 | neigh_node->addr); | |
466 | frag_header.no++; | |
467 | ||
468 | /* The initial check in this function should cover this case */ | |
469 | if (frag_header.no == BATADV_FRAG_MAX_FRAGMENTS - 1) | |
470 | goto out_err; | |
471 | } | |
472 | ||
473 | /* Make room for the fragment header. */ | |
474 | if (batadv_skb_head_push(skb, header_size) < 0 || | |
475 | pskb_expand_head(skb, header_size + ETH_HLEN, 0, GFP_ATOMIC) < 0) | |
476 | goto out_err; | |
477 | ||
478 | memcpy(skb->data, &frag_header, header_size); | |
479 | ||
480 | /* Send the last fragment */ | |
481 | batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_TX); | |
482 | batadv_add_counter(bat_priv, BATADV_CNT_FRAG_TX_BYTES, | |
483 | skb->len + ETH_HLEN); | |
484 | batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr); | |
485 | ||
486 | return true; | |
487 | out_err: | |
488 | return false; | |
489 | } |