net/batman-adv/bitarray.c

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