blob: 25cbc36e997adab14dca5e3be3ee832ce57acccb [file] [log] [blame]
Sven Eckelmann9f6446c2015-04-23 13:16:35 +02001/* Copyright (C) 2006-2015 B.A.T.M.A.N. contributors:
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +00002 *
3 * Simon Wunderlich, Marek Lindner
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of version 2 of the GNU General Public
7 * License as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
Antonio Quartulliebf38fb2013-11-03 20:40:48 +010015 * along with this program; if not, see <http://www.gnu.org/licenses/>.
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000016 */
17
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000018#include "bitarray.h"
Sven Eckelmann1e2c2a42015-04-17 19:40:28 +020019#include "main.h"
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000020
Sven Eckelmann1e2c2a42015-04-17 19:40:28 +020021#include <linux/bitmap.h>
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000022
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000023/* shift the packet array by n places. */
Sven Eckelmann6b5e9712015-05-26 18:34:26 +020024static void batadv_bitmap_shift_left(unsigned long *seq_bits, s32 n)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000025{
Sven Eckelmann42d0b042012-06-03 22:19:17 +020026 if (n <= 0 || n >= BATADV_TQ_LOCAL_WINDOW_SIZE)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000027 return;
28
Sven Eckelmann42d0b042012-06-03 22:19:17 +020029 bitmap_shift_left(seq_bits, seq_bits, n, BATADV_TQ_LOCAL_WINDOW_SIZE);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000030}
31
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000032/* receive and process one packet within the sequence number window.
33 *
34 * returns:
35 * 1 if the window was moved (either new or very old)
36 * 0 if the window was not moved/shifted.
37 */
Sven Eckelmann6b5e9712015-05-26 18:34:26 +020038int batadv_bit_get_packet(void *priv, unsigned long *seq_bits, s32 seq_num_diff,
39 int set_mark)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000040{
Sven Eckelmann56303d32012-06-05 22:31:31 +020041 struct batadv_priv *bat_priv = priv;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000042
43 /* sequence number is slightly older. We already got a sequence number
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020044 * higher than this one, so we just mark it.
45 */
Sven Eckelmann42d0b042012-06-03 22:19:17 +020046 if (seq_num_diff <= 0 && seq_num_diff > -BATADV_TQ_LOCAL_WINDOW_SIZE) {
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000047 if (set_mark)
Sven Eckelmann9b4a1152012-05-12 13:48:53 +020048 batadv_set_bit(seq_bits, -seq_num_diff);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000049 return 0;
50 }
51
52 /* sequence number is slightly newer, so we shift the window and
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020053 * set the mark if required
54 */
Sven Eckelmann42d0b042012-06-03 22:19:17 +020055 if (seq_num_diff > 0 && seq_num_diff < BATADV_TQ_LOCAL_WINDOW_SIZE) {
Sven Eckelmann0f5f9322012-05-12 02:09:25 +020056 batadv_bitmap_shift_left(seq_bits, seq_num_diff);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000057
58 if (set_mark)
Sven Eckelmann9b4a1152012-05-12 13:48:53 +020059 batadv_set_bit(seq_bits, 0);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000060 return 1;
61 }
62
63 /* sequence number is much newer, probably missed a lot of packets */
Sven Eckelmann42d0b042012-06-03 22:19:17 +020064 if (seq_num_diff >= BATADV_TQ_LOCAL_WINDOW_SIZE &&
65 seq_num_diff < BATADV_EXPECTED_SEQNO_RANGE) {
Sven Eckelmann39c75a52012-06-03 22:19:22 +020066 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
Sven Eckelmann1eda58b2012-05-12 13:48:58 +020067 "We missed a lot of packets (%i) !\n",
68 seq_num_diff - 1);
Sven Eckelmann42d0b042012-06-03 22:19:17 +020069 bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000070 if (set_mark)
Sven Eckelmann9b4a1152012-05-12 13:48:53 +020071 batadv_set_bit(seq_bits, 0);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000072 return 1;
73 }
74
75 /* received a much older packet. The other host either restarted
76 * or the old packet got delayed somewhere in the network. The
77 * packet should be dropped without calling this function if the
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020078 * seqno window is protected.
Sven Eckelmann8e7c15d2012-08-20 10:26:47 +020079 *
80 * seq_num_diff <= -BATADV_TQ_LOCAL_WINDOW_SIZE
81 * or
82 * seq_num_diff >= BATADV_EXPECTED_SEQNO_RANGE
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020083 */
Sven Eckelmann8e7c15d2012-08-20 10:26:47 +020084 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
85 "Other host probably restarted!\n");
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000086
Sven Eckelmann8e7c15d2012-08-20 10:26:47 +020087 bitmap_zero(seq_bits, BATADV_TQ_LOCAL_WINDOW_SIZE);
88 if (set_mark)
89 batadv_set_bit(seq_bits, 0);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000090
Sven Eckelmann8e7c15d2012-08-20 10:26:47 +020091 return 1;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000092}