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 */ 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 */ 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