1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (C) B.A.T.M.A.N. contributors:
3 *
4 * Simon Wunderlich, Marek Lindner
5 */
6
7 #include "bitarray.h"
8 #include "main.h"
9
10 #include <linux/bitmap.h>
11
12 #include "log.h"
13
14 /**
15 * batadv_bitmap_shift_left() - shift the sequence number bitmap left
16 * @seq_bits: the sequence number bitmap to shift
17 * @n: number of positions to shift left
18 *
19 * Shift @seq_bits by @n positions. No-op if @n is not within the bounds of
20 * the bitmap.
21 */
batadv_bitmap_shift_left(unsigned long * seq_bits,s32 n)22 static void batadv_bitmap_shift_left(unsigned long *seq_bits, s32 n)
23 {
24 if (n <= 0 || n >= BATADV_TQ_LOCAL_WINDOW_SIZE)
25 return;
26
27 bitmap_shift_left(seq_bits, seq_bits, n, BATADV_TQ_LOCAL_WINDOW_SIZE);
28 }
29
30 /**
31 * batadv_bit_get_packet() - receive and process one packet within the sequence
32 * number window
33 * @priv: the bat priv with all the mesh interface information
34 * @seq_bits: pointer to the sequence number bitmap of received packets
35 * @seq_num_diff: difference between the current/received sequence number and
36 * the last sequence number
37 * @set_mark: whether this packet should be marked in seq_bits
38 *
39 * Return: true if the window was moved (either new or very old),
40 * false if the window was not moved/shifted.
41 */
batadv_bit_get_packet(void * priv,unsigned long * seq_bits,s32 seq_num_diff,int set_mark)42 bool batadv_bit_get_packet(void *priv, unsigned long *seq_bits,
43 s32 seq_num_diff, int set_mark)
44 {
45 struct batadv_priv *bat_priv = priv;
46
47 /* sequence number is slightly older. We already got a sequence number
48 * higher than this one, so we just mark it.
49 */
50 if (seq_num_diff <= 0 && seq_num_diff > -BATADV_TQ_LOCAL_WINDOW_SIZE) {
51 if (set_mark)
52 batadv_set_bit(seq_bits, -seq_num_diff);
53 return false;
54 }
55
56 /* sequence number is slightly newer, so we shift the window and
57 * set the mark if required
58 */
59 if (seq_num_diff > 0 && seq_num_diff < BATADV_TQ_LOCAL_WINDOW_SIZE) {
60 batadv_bitmap_shift_left(seq_bits, seq_num_diff);
61
62 if (set_mark)
63 batadv_set_bit(seq_bits, 0);
64 return true;
65 }
66
67 /* sequence number is much newer, probably missed a lot of packets */
68 if (seq_num_diff >= BATADV_TQ_LOCAL_WINDOW_SIZE &&
69 seq_num_diff < BATADV_EXPECTED_SEQNO_RANGE) {
70 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
71 "We missed a lot of packets (%i) !\n",
72 seq_num_diff - 1);
73 bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
74 if (set_mark)
75 batadv_set_bit(seq_bits, 0);
76 return true;
77 }
78
79 /* received a much older packet. The other host either restarted
80 * or the old packet got delayed somewhere in the network. The
81 * packet should be dropped without calling this function if the
82 * seqno window is protected.
83 *
84 * seq_num_diff <= -BATADV_TQ_LOCAL_WINDOW_SIZE
85 * or
86 * seq_num_diff >= BATADV_EXPECTED_SEQNO_RANGE
87 */
88 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
89 "Other host probably restarted!\n");
90
91 bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
92 if (set_mark)
93 batadv_set_bit(seq_bits, 0);
94
95 return true;
96 }
97