net/batman-adv/bitarray.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /* Copyright (C) B.A.T.M.A.N. contributors:
0003  *
0004  * Simon Wunderlich, Marek Lindner
0005  */
0006
0007 #include "bitarray.h"
0008 #include "main.h"
0009
0010 #include <linux/bitmap.h>
0011
0012 #include "log.h"
0013
0014 /* shift the packet array by n places. */
0015 static void batadv_bitmap_shift_left(unsigned long *seq_bits, s32 n)
0016 {
0017     if (n <= 0 || n >= BATADV_TQ_LOCAL_WINDOW_SIZE)
0018         return;
0019
0020     bitmap_shift_left(seq_bits, seq_bits, n, BATADV_TQ_LOCAL_WINDOW_SIZE);
0021 }
0022
0023 /**
0024  * batadv_bit_get_packet() - receive and process one packet within the sequence
0025  *  number window
0026  * @priv: the bat priv with all the soft interface information
0027  * @seq_bits: pointer to the sequence number receive packet
0028  * @seq_num_diff: difference between the current/received sequence number and
0029  *  the last sequence number
0030  * @set_mark: whether this packet should be marked in seq_bits
0031  *
0032  * Return: true if the window was moved (either new or very old),
0033  *  false if the window was not moved/shifted.
0034  */
0035 bool batadv_bit_get_packet(void *priv, unsigned long *seq_bits,
0036                s32 seq_num_diff, int set_mark)
0037 {
0038     struct batadv_priv *bat_priv = priv;
0039
0040     /* sequence number is slightly older. We already got a sequence number
0041      * higher than this one, so we just mark it.
0042      */
0043     if (seq_num_diff <= 0 && seq_num_diff > -BATADV_TQ_LOCAL_WINDOW_SIZE) {
0044         if (set_mark)
0045             batadv_set_bit(seq_bits, -seq_num_diff);
0046         return false;
0047     }
0048
0049     /* sequence number is slightly newer, so we shift the window and
0050      * set the mark if required
0051      */
0052     if (seq_num_diff > 0 && seq_num_diff < BATADV_TQ_LOCAL_WINDOW_SIZE) {
0053         batadv_bitmap_shift_left(seq_bits, seq_num_diff);
0054
0055         if (set_mark)
0056             batadv_set_bit(seq_bits, 0);
0057         return true;
0058     }
0059
0060     /* sequence number is much newer, probably missed a lot of packets */
0061     if (seq_num_diff >= BATADV_TQ_LOCAL_WINDOW_SIZE &&
0062         seq_num_diff < BATADV_EXPECTED_SEQNO_RANGE) {
0063         batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
0064                "We missed a lot of packets (%i) !\n",
0065                seq_num_diff - 1);
0066         bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
0067         if (set_mark)
0068             batadv_set_bit(seq_bits, 0);
0069         return true;
0070     }
0071
0072     /* received a much older packet. The other host either restarted
0073      * or the old packet got delayed somewhere in the network. The
0074      * packet should be dropped without calling this function if the
0075      * seqno window is protected.
0076      *
0077      * seq_num_diff <= -BATADV_TQ_LOCAL_WINDOW_SIZE
0078      * or
0079      * seq_num_diff >= BATADV_EXPECTED_SEQNO_RANGE
0080      */
0081     batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
0082            "Other host probably restarted!\n");
0083
0084     bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
0085     if (set_mark)
0086         batadv_set_bit(seq_bits, 0);
0087
0088     return true;
0089 }