1// SPDX-License-Identifier: GPL-2.0
2/* Copyright (C) B.A.T.M.A.N. contributors:
3 *
4 * Martin Hundebøll <martin@hundeboll.net>
5 */
6
7#include "fragmentation.h"
8#include "main.h"
9
10#include <linux/atomic.h>
11#include <linux/byteorder/generic.h>
12#include <linux/errno.h>
13#include <linux/etherdevice.h>
14#include <linux/gfp.h>
15#include <linux/if_ether.h>
16#include <linux/jiffies.h>
17#include <linux/lockdep.h>
18#include <linux/minmax.h>
19#include <linux/netdevice.h>
20#include <linux/skbuff.h>
21#include <linux/slab.h>
22#include <linux/spinlock.h>
23#include <linux/string.h>
24#include <uapi/linux/batadv_packet.h>
25
26#include "hard-interface.h"
27#include "originator.h"
28#include "send.h"
29
30/**
31 * batadv_frag_clear_chain() - delete entries in the fragment buffer chain
32 * @head: head of chain with entries.
33 * @dropped: whether the chain is cleared because all fragments are dropped
34 *
35 * Free fragments in the passed hlist. Should be called with appropriate lock.
36 */
37static void batadv_frag_clear_chain(struct hlist_head *head, bool dropped)
38{
39 struct batadv_frag_list_entry *entry;
40 struct hlist_node *node;
41
42 hlist_for_each_entry_safe(entry, node, head, list) {
43 hlist_del(n: &entry->list);
44
45 if (dropped)
46 kfree_skb(skb: entry->skb);
47 else
48 consume_skb(skb: entry->skb);
49
50 kfree(objp: entry);
51 }
52}
53
54/**
55 * batadv_frag_purge_orig() - free fragments associated to an orig
56 * @orig_node: originator to free fragments from
57 * @check_cb: optional function to tell if an entry should be purged
58 */
59void batadv_frag_purge_orig(struct batadv_orig_node *orig_node,
60 bool (*check_cb)(struct batadv_frag_table_entry *))
61{
62 struct batadv_frag_table_entry *chain;
63 u8 i;
64
65 for (i = 0; i < BATADV_FRAG_BUFFER_COUNT; i++) {
66 chain = &orig_node->fragments[i];
67 spin_lock_bh(lock: &chain->lock);
68
69 if (!check_cb || check_cb(chain)) {
70 batadv_frag_clear_chain(head: &chain->fragment_list, dropped: true);
71 chain->size = 0;
72 }
73
74 spin_unlock_bh(lock: &chain->lock);
75 }
76}
77
78/**
79 * batadv_frag_size_limit() - maximum possible size of packet to be fragmented
80 *
81 * Return: the maximum size of payload that can be fragmented.
82 */
83static int batadv_frag_size_limit(void)
84{
85 int limit = BATADV_FRAG_MAX_FRAG_SIZE;
86
87 limit -= sizeof(struct batadv_frag_packet);
88 limit *= BATADV_FRAG_MAX_FRAGMENTS;
89
90 return limit;
91}
92
93/**
94 * batadv_frag_init_chain() - check and prepare fragment chain for new fragment
95 * @chain: chain in fragments table to init
96 * @seqno: sequence number of the received fragment
97 *
98 * Make chain ready for a fragment with sequence number "seqno". Delete existing
99 * entries if they have an "old" sequence number.
100 *
101 * Caller must hold chain->lock.
102 *
103 * Return: true if chain is empty and the caller can just insert the new
104 * fragment without searching for the right position.
105 */
106static bool batadv_frag_init_chain(struct batadv_frag_table_entry *chain,
107 u16 seqno)
108{
109 lockdep_assert_held(&chain->lock);
110
111 if (chain->seqno == seqno)
112 return false;
113
114 if (!hlist_empty(h: &chain->fragment_list))
115 batadv_frag_clear_chain(head: &chain->fragment_list, dropped: true);
116
117 chain->size = 0;
118 chain->seqno = seqno;
119
120 return true;
121}
122
123/**
124 * batadv_frag_insert_packet() - insert a fragment into a fragment chain
125 * @orig_node: originator that the fragment was received from
126 * @skb: skb to insert
127 * @chain_out: list head to attach complete chains of fragments to
128 *
129 * Insert a new fragment into the reverse ordered chain in the right table
130 * entry. The hash table entry is cleared if "old" fragments exist in it.
131 *
132 * Return: true if skb is buffered, false on error. If the chain has all the
133 * fragments needed to merge the packet, the chain is moved to the passed head
134 * to avoid locking the chain in the table.
135 */
136static bool batadv_frag_insert_packet(struct batadv_orig_node *orig_node,
137 struct sk_buff *skb,
138 struct hlist_head *chain_out)
139{
140 struct batadv_frag_table_entry *chain;
141 struct batadv_frag_list_entry *frag_entry_new = NULL, *frag_entry_curr;
142 struct batadv_frag_list_entry *frag_entry_last = NULL;
143 struct batadv_frag_packet *frag_packet;
144 u8 bucket;
145 u16 seqno, hdr_size = sizeof(struct batadv_frag_packet);
146 bool ret = false;
147
148 /* Linearize packet to avoid linearizing 16 packets in a row when doing
149 * the later merge. Non-linear merge should be added to remove this
150 * linearization.
151 */
152 if (skb_linearize(skb) < 0)
153 goto err;
154
155 frag_packet = (struct batadv_frag_packet *)skb->data;
156 seqno = ntohs(frag_packet->seqno);
157 bucket = seqno % BATADV_FRAG_BUFFER_COUNT;
158
159 frag_entry_new = kmalloc(sizeof(*frag_entry_new), GFP_ATOMIC);
160 if (!frag_entry_new)
161 goto err;
162
163 frag_entry_new->skb = skb;
164 frag_entry_new->no = frag_packet->no;
165
166 /* Select entry in the "chain table" and delete any prior fragments
167 * with another sequence number. batadv_frag_init_chain() returns true,
168 * if the list is empty at return.
169 */
170 chain = &orig_node->fragments[bucket];
171 spin_lock_bh(lock: &chain->lock);
172 if (batadv_frag_init_chain(chain, seqno)) {
173 hlist_add_head(n: &frag_entry_new->list, h: &chain->fragment_list);
174 chain->size = skb->len - hdr_size;
175 chain->timestamp = jiffies;
176 chain->total_size = ntohs(frag_packet->total_size);
177 ret = true;
178 goto out;
179 }
180
181 /* Find the position for the new fragment. */
182 hlist_for_each_entry(frag_entry_curr, &chain->fragment_list, list) {
183 /* Drop packet if fragment already exists. */
184 if (frag_entry_curr->no == frag_entry_new->no)
185 goto err_unlock;
186
187 /* Order fragments from highest to lowest. */
188 if (frag_entry_curr->no < frag_entry_new->no) {
189 hlist_add_before(n: &frag_entry_new->list,
190 next: &frag_entry_curr->list);
191 chain->size += skb->len - hdr_size;
192 chain->timestamp = jiffies;
193 ret = true;
194 goto out;
195 }
196
197 /* store current entry because it could be the last in list */
198 frag_entry_last = frag_entry_curr;
199 }
200
201 /* Reached the end of the list, so insert after 'frag_entry_last'. */
202 if (likely(frag_entry_last)) {
203 hlist_add_behind(n: &frag_entry_new->list, prev: &frag_entry_last->list);
204 chain->size += skb->len - hdr_size;
205 chain->timestamp = jiffies;
206 ret = true;
207 }
208
209out:
210 if (chain->size > batadv_frag_size_limit() ||
211 chain->total_size != ntohs(frag_packet->total_size) ||
212 chain->total_size > batadv_frag_size_limit()) {
213 /* Clear chain if total size of either the list or the packet
214 * exceeds the maximum size of one merged packet. Don't allow
215 * packets to have different total_size.
216 */
217 batadv_frag_clear_chain(head: &chain->fragment_list, dropped: true);
218 chain->size = 0;
219 } else if (ntohs(frag_packet->total_size) == chain->size) {
220 /* All fragments received. Hand over chain to caller. */
221 hlist_move_list(old: &chain->fragment_list, new: chain_out);
222 chain->size = 0;
223 }
224
225err_unlock:
226 spin_unlock_bh(lock: &chain->lock);
227
228err:
229 if (!ret) {
230 kfree(objp: frag_entry_new);
231 kfree_skb(skb);
232 }
233
234 return ret;
235}
236
237/**
238 * batadv_frag_merge_packets() - merge a chain of fragments
239 * @chain: head of chain with fragments
240 *
241 * Expand the first skb in the chain and copy the content of the remaining
242 * skb's into the expanded one. After doing so, clear the chain.
243 *
244 * Return: the merged skb or NULL on error.
245 */
246static struct sk_buff *
247batadv_frag_merge_packets(struct hlist_head *chain)
248{
249 struct batadv_frag_packet *packet;
250 struct batadv_frag_list_entry *entry;
251 struct sk_buff *skb_out;
252 int size, hdr_size = sizeof(struct batadv_frag_packet);
253 bool dropped = false;
254
255 /* Remove first entry, as this is the destination for the rest of the
256 * fragments.
257 */
258 entry = hlist_entry(chain->first, struct batadv_frag_list_entry, list);
259 hlist_del(n: &entry->list);
260 skb_out = entry->skb;
261 kfree(objp: entry);
262
263 packet = (struct batadv_frag_packet *)skb_out->data;
264 size = ntohs(packet->total_size) + hdr_size;
265
266 /* Make room for the rest of the fragments. */
267 if (pskb_expand_head(skb: skb_out, nhead: 0, ntail: size - skb_out->len, GFP_ATOMIC) < 0) {
268 kfree_skb(skb: skb_out);
269 skb_out = NULL;
270 dropped = true;
271 goto free;
272 }
273
274 /* Move the existing MAC header to just before the payload. (Override
275 * the fragment header.)
276 */
277 skb_pull(skb: skb_out, len: hdr_size);
278 skb_out->ip_summed = CHECKSUM_NONE;
279 memmove(skb_out->data - ETH_HLEN, skb_mac_header(skb_out), ETH_HLEN);
280 skb_set_mac_header(skb: skb_out, offset: -ETH_HLEN);
281 skb_reset_network_header(skb: skb_out);
282 skb_reset_transport_header(skb: skb_out);
283
284 /* Copy the payload of the each fragment into the last skb */
285 hlist_for_each_entry(entry, chain, list) {
286 size = entry->skb->len - hdr_size;
287 skb_put_data(skb: skb_out, data: entry->skb->data + hdr_size, len: size);
288 }
289
290free:
291 /* Locking is not needed, because 'chain' is not part of any orig. */
292 batadv_frag_clear_chain(head: chain, dropped);
293 return skb_out;
294}
295
296/**
297 * batadv_frag_skb_buffer() - buffer fragment for later merge
298 * @skb: skb to buffer
299 * @orig_node_src: originator that the skb is received from
300 *
301 * Add fragment to buffer and merge fragments if possible.
302 *
303 * There are three possible outcomes: 1) Packet is merged: Return true and
304 * set *skb to merged packet; 2) Packet is buffered: Return true and set *skb
305 * to NULL; 3) Error: Return false and free skb.
306 *
307 * Return: true when the packet is merged or buffered, false when skb is not
308 * used.
309 */
310bool batadv_frag_skb_buffer(struct sk_buff **skb,
311 struct batadv_orig_node *orig_node_src)
312{
313 struct sk_buff *skb_out = NULL;
314 struct hlist_head head = HLIST_HEAD_INIT;
315 bool ret = false;
316
317 /* Add packet to buffer and table entry if merge is possible. */
318 if (!batadv_frag_insert_packet(orig_node: orig_node_src, skb: *skb, chain_out: &head))
319 goto out_err;
320
321 /* Leave if more fragments are needed to merge. */
322 if (hlist_empty(h: &head))
323 goto out;
324
325 skb_out = batadv_frag_merge_packets(chain: &head);
326 if (!skb_out)
327 goto out_err;
328
329out:
330 ret = true;
331out_err:
332 *skb = skb_out;
333 return ret;
334}
335
336/**
337 * batadv_frag_skb_fwd() - forward fragments that would exceed MTU when merged
338 * @skb: skb to forward
339 * @recv_if: interface that the skb is received on
340 * @orig_node_src: originator that the skb is received from
341 *
342 * Look up the next-hop of the fragments payload and check if the merged packet
343 * will exceed the MTU towards the next-hop. If so, the fragment is forwarded
344 * without merging it.
345 *
346 * Return: true if the fragment is consumed/forwarded, false otherwise.
347 */
348bool batadv_frag_skb_fwd(struct sk_buff *skb,
349 struct batadv_hard_iface *recv_if,
350 struct batadv_orig_node *orig_node_src)
351{
352 struct batadv_priv *bat_priv = netdev_priv(dev: recv_if->mesh_iface);
353 struct batadv_neigh_node *neigh_node = NULL;
354 struct batadv_frag_packet *packet;
355 u16 total_size;
356 bool ret = false;
357
358 packet = (struct batadv_frag_packet *)skb->data;
359
360 neigh_node = batadv_orig_to_router(bat_priv, orig_addr: packet->dest, if_outgoing: recv_if);
361 if (!neigh_node)
362 goto out;
363
364 /* Forward the fragment, if the merged packet would be too big to
365 * be assembled.
366 */
367 total_size = ntohs(packet->total_size);
368 if (total_size > neigh_node->if_incoming->net_dev->mtu) {
369 batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_FWD);
370 batadv_add_counter(bat_priv, idx: BATADV_CNT_FRAG_FWD_BYTES,
371 count: skb->len + ETH_HLEN);
372
373 packet->ttl--;
374 batadv_send_unicast_skb(skb, neigh_node);
375 ret = true;
376 }
377
378out:
379 batadv_neigh_node_put(neigh_node);
380 return ret;
381}
382
383/**
384 * batadv_frag_create() - create a fragment from skb
385 * @net_dev: outgoing device for fragment
386 * @skb: skb to create fragment from
387 * @frag_head: header to use in new fragment
388 * @fragment_size: size of new fragment
389 *
390 * Split the passed skb into two fragments: A new one with size matching the
391 * passed mtu and the old one with the rest. The new skb contains data from the
392 * tail of the old skb.
393 *
394 * Return: the new fragment, NULL on error.
395 */
396static struct sk_buff *batadv_frag_create(struct net_device *net_dev,
397 struct sk_buff *skb,
398 struct batadv_frag_packet *frag_head,
399 unsigned int fragment_size)
400{
401 unsigned int ll_reserved = LL_RESERVED_SPACE(net_dev);
402 unsigned int tailroom = net_dev->needed_tailroom;
403 struct sk_buff *skb_fragment;
404 unsigned int header_size = sizeof(*frag_head);
405 unsigned int mtu = fragment_size + header_size;
406
407 skb_fragment = dev_alloc_skb(length: ll_reserved + mtu + tailroom);
408 if (!skb_fragment)
409 goto err;
410
411 skb_fragment->priority = skb->priority;
412
413 /* Eat the last mtu-bytes of the skb */
414 skb_reserve(skb: skb_fragment, len: ll_reserved + header_size);
415 skb_split(skb, skb1: skb_fragment, len: skb->len - fragment_size);
416
417 /* Add the header */
418 skb_push(skb: skb_fragment, len: header_size);
419 memcpy(skb_fragment->data, frag_head, header_size);
420
421err:
422 return skb_fragment;
423}
424
425/**
426 * batadv_frag_send_packet() - create up to 16 fragments from the passed skb
427 * @skb: skb to create fragments from
428 * @orig_node: final destination of the created fragments
429 * @neigh_node: next-hop of the created fragments
430 *
431 * Return: the netdev tx status or a negative errno code on a failure
432 */
433int batadv_frag_send_packet(struct sk_buff *skb,
434 struct batadv_orig_node *orig_node,
435 struct batadv_neigh_node *neigh_node)
436{
437 struct net_device *net_dev = neigh_node->if_incoming->net_dev;
438 struct batadv_priv *bat_priv;
439 struct batadv_hard_iface *primary_if = NULL;
440 struct batadv_frag_packet frag_header;
441 struct sk_buff *skb_fragment;
442 unsigned int mtu = net_dev->mtu;
443 unsigned int header_size = sizeof(frag_header);
444 unsigned int max_fragment_size, num_fragments;
445 int ret;
446
447 /* To avoid merge and refragmentation at next-hops we never send
448 * fragments larger than BATADV_FRAG_MAX_FRAG_SIZE
449 */
450 mtu = min_t(unsigned int, mtu, BATADV_FRAG_MAX_FRAG_SIZE);
451 max_fragment_size = mtu - header_size;
452
453 if (skb->len == 0 || max_fragment_size == 0)
454 return -EINVAL;
455
456 num_fragments = (skb->len - 1) / max_fragment_size + 1;
457 max_fragment_size = (skb->len - 1) / num_fragments + 1;
458
459 /* Don't even try to fragment, if we need more than 16 fragments */
460 if (num_fragments > BATADV_FRAG_MAX_FRAGMENTS) {
461 ret = -EAGAIN;
462 goto free_skb;
463 }
464
465 bat_priv = orig_node->bat_priv;
466 primary_if = batadv_primary_if_get_selected(bat_priv);
467 if (!primary_if) {
468 ret = -EINVAL;
469 goto free_skb;
470 }
471
472 /* GRO might have added fragments to the fragment list instead of
473 * frags[]. But this is not handled by skb_split and must be
474 * linearized to avoid incorrect length information after all
475 * batman-adv fragments were created and submitted to the
476 * hard-interface
477 */
478 if (skb_has_frag_list(skb) && __skb_linearize(skb)) {
479 ret = -ENOMEM;
480 goto free_skb;
481 }
482
483 /* Create one header to be copied to all fragments */
484 frag_header.packet_type = BATADV_UNICAST_FRAG;
485 frag_header.version = BATADV_COMPAT_VERSION;
486 frag_header.ttl = BATADV_TTL;
487 frag_header.seqno = htons(atomic_inc_return(&bat_priv->frag_seqno));
488 frag_header.reserved = 0;
489 frag_header.no = 0;
490 frag_header.total_size = htons(skb->len);
491
492 /* skb->priority values from 256->263 are magic values to
493 * directly indicate a specific 802.1d priority. This is used
494 * to allow 802.1d priority to be passed directly in from VLAN
495 * tags, etc.
496 */
497 if (skb->priority >= 256 && skb->priority <= 263)
498 frag_header.priority = skb->priority - 256;
499 else
500 frag_header.priority = 0;
501
502 ether_addr_copy(dst: frag_header.orig, src: primary_if->net_dev->dev_addr);
503 ether_addr_copy(dst: frag_header.dest, src: orig_node->orig);
504
505 /* Eat and send fragments from the tail of skb */
506 while (skb->len > max_fragment_size) {
507 /* The initial check in this function should cover this case */
508 if (unlikely(frag_header.no == BATADV_FRAG_MAX_FRAGMENTS - 1)) {
509 ret = -EINVAL;
510 goto put_primary_if;
511 }
512
513 skb_fragment = batadv_frag_create(net_dev, skb, frag_head: &frag_header,
514 fragment_size: max_fragment_size);
515 if (!skb_fragment) {
516 ret = -ENOMEM;
517 goto put_primary_if;
518 }
519
520 batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_TX);
521 batadv_add_counter(bat_priv, idx: BATADV_CNT_FRAG_TX_BYTES,
522 count: skb_fragment->len + ETH_HLEN);
523 ret = batadv_send_unicast_skb(skb: skb_fragment, neigh_node);
524 if (ret != NET_XMIT_SUCCESS) {
525 ret = NET_XMIT_DROP;
526 goto put_primary_if;
527 }
528
529 frag_header.no++;
530 }
531
532 /* make sure that there is at least enough head for the fragmentation
533 * and ethernet headers
534 */
535 ret = skb_cow_head(skb, ETH_HLEN + header_size);
536 if (ret < 0)
537 goto put_primary_if;
538
539 skb_push(skb, len: header_size);
540 memcpy(skb->data, &frag_header, header_size);
541
542 /* Send the last fragment */
543 batadv_inc_counter(bat_priv, BATADV_CNT_FRAG_TX);
544 batadv_add_counter(bat_priv, idx: BATADV_CNT_FRAG_TX_BYTES,
545 count: skb->len + ETH_HLEN);
546 ret = batadv_send_unicast_skb(skb, neigh_node);
547 /* skb was consumed */
548 skb = NULL;
549
550put_primary_if:
551 batadv_hardif_put(hard_iface: primary_if);
552free_skb:
553 kfree_skb(skb);
554
555 return ret;
556}
557

source code of linux/net/batman-adv/fragmentation.c