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(&entry->list);
44
45		if (dropped)
46			kfree_skb(entry->skb);
47		else
48			consume_skb(entry->skb);
49
50		kfree(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(&chain->lock);
68
69		if (!check_cb || check_cb(chain)) {
70			batadv_frag_clear_chain(&chain->fragment_list, true);
71			chain->size = 0;
72		}
73
74		spin_unlock_bh(&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(&chain->fragment_list))
115		batadv_frag_clear_chain(&chain->fragment_list, 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(&chain->lock);
172	if (batadv_frag_init_chain(chain, seqno)) {
173		hlist_add_head(&frag_entry_new->list, &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(&frag_entry_new->list,
190					 &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(&frag_entry_new->list, &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(&chain->fragment_list, 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(&chain->fragment_list, chain_out);
222		chain->size = 0;
223	}
224
225err_unlock:
226	spin_unlock_bh(&chain->lock);
227
228err:
229	if (!ret) {
230		kfree(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(&entry->list);
260	skb_out = entry->skb;
261	kfree(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_out, 0, size - skb_out->len, GFP_ATOMIC) < 0) {
268		kfree_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_out, 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_out, -ETH_HLEN);
281	skb_reset_network_header(skb_out);
282	skb_reset_transport_header(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_out, entry->skb->data + hdr_size, size);
288	}
289
290free:
291	/* Locking is not needed, because 'chain' is not part of any orig. */
292	batadv_frag_clear_chain(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_src, *skb, &head))
319		goto out_err;
320
321	/* Leave if more fragments are needed to merge. */
322	if (hlist_empty(&head))
323		goto out;
324
325	skb_out = batadv_frag_merge_packets(&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(recv_if->soft_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, packet->dest, 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, BATADV_CNT_FRAG_FWD_BYTES,
371				   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(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_fragment, ll_reserved + header_size);
415	skb_split(skb, skb_fragment, skb->len - fragment_size);
416
417	/* Add the header */
418	skb_push(skb_fragment, 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(frag_header.orig, primary_if->net_dev->dev_addr);
503	ether_addr_copy(frag_header.dest, 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_header,
514						  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, BATADV_CNT_FRAG_TX_BYTES,
522				   skb_fragment->len + ETH_HLEN);
523		ret = batadv_send_unicast_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, 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, BATADV_CNT_FRAG_TX_BYTES,
545			   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(primary_if);
552free_skb:
553	kfree_skb(skb);
554
555	return ret;
556}
557