bat_v_ogm.c 33 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2
/* Copyright (C) 2013-2020  B.A.T.M.A.N. contributors:
3 4 5 6 7 8 9 10 11 12 13
 *
 * Antonio Quartulli
 */

#include "bat_v_ogm.h"
#include "main.h"

#include <linux/atomic.h>
#include <linux/byteorder/generic.h>
#include <linux/errno.h>
#include <linux/etherdevice.h>
14
#include <linux/gfp.h>
15 16 17
#include <linux/if_ether.h>
#include <linux/jiffies.h>
#include <linux/kernel.h>
18
#include <linux/kref.h>
19
#include <linux/list.h>
20
#include <linux/lockdep.h>
21
#include <linux/mutex.h>
22
#include <linux/netdevice.h>
23
#include <linux/prandom.h>
24 25 26 27 28
#include <linux/random.h>
#include <linux/rculist.h>
#include <linux/rcupdate.h>
#include <linux/skbuff.h>
#include <linux/slab.h>
29
#include <linux/spinlock.h>
30 31 32 33
#include <linux/stddef.h>
#include <linux/string.h>
#include <linux/types.h>
#include <linux/workqueue.h>
34
#include <uapi/linux/batadv_packet.h>
35

36
#include "bat_algo.h"
37
#include "hard-interface.h"
38
#include "hash.h"
39
#include "log.h"
40
#include "originator.h"
41 42 43
#include "routing.h"
#include "send.h"
#include "translation-table.h"
44
#include "tvlv.h"
45

46
/**
47
 * batadv_v_ogm_orig_get() - retrieve and possibly create an originator node
48 49 50
 * @bat_priv: the bat priv with all the soft interface information
 * @addr: the address of the originator
 *
51 52 53
 * Return: the orig_node corresponding to the specified address. If such an
 * object does not exist, it is allocated here. In case of allocation failure
 * returns NULL.
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
 */
struct batadv_orig_node *batadv_v_ogm_orig_get(struct batadv_priv *bat_priv,
					       const u8 *addr)
{
	struct batadv_orig_node *orig_node;
	int hash_added;

	orig_node = batadv_orig_hash_find(bat_priv, addr);
	if (orig_node)
		return orig_node;

	orig_node = batadv_orig_node_new(bat_priv, addr);
	if (!orig_node)
		return NULL;

69
	kref_get(&orig_node->refcount);
70 71 72 73
	hash_added = batadv_hash_add(bat_priv->orig_hash, batadv_compare_orig,
				     batadv_choose_orig, orig_node,
				     &orig_node->hash_entry);
	if (hash_added != 0) {
74
		/* remove refcnt for newly created orig_node and hash entry */
75 76 77 78 79 80 81 82
		batadv_orig_node_put(orig_node);
		batadv_orig_node_put(orig_node);
		orig_node = NULL;
	}

	return orig_node;
}

83 84 85 86 87 88 89 90 91
/**
 * batadv_v_ogm_start_queue_timer() - restart the OGM aggregation timer
 * @hard_iface: the interface to use to send the OGM
 */
static void batadv_v_ogm_start_queue_timer(struct batadv_hard_iface *hard_iface)
{
	unsigned int msecs = BATADV_MAX_AGGREGATION_MS * 1000;

	/* msecs * [0.9, 1.1] */
92
	msecs += prandom_u32_max(msecs / 5) - (msecs / 10);
93 94 95 96
	queue_delayed_work(batadv_event_workqueue, &hard_iface->bat_v.aggr_wq,
			   msecs_to_jiffies(msecs / 1000));
}

97
/**
98
 * batadv_v_ogm_start_timer() - restart the OGM sending timer
99 100 101 102 103 104 105 106 107 108 109 110
 * @bat_priv: the bat priv with all the soft interface information
 */
static void batadv_v_ogm_start_timer(struct batadv_priv *bat_priv)
{
	unsigned long msecs;
	/* this function may be invoked in different contexts (ogm rescheduling
	 * or hard_iface activation), but the work timer should not be reset
	 */
	if (delayed_work_pending(&bat_priv->bat_v.ogm_wq))
		return;

	msecs = atomic_read(&bat_priv->orig_interval) - BATADV_JITTER;
111
	msecs += prandom_u32_max(2 * BATADV_JITTER);
112 113 114 115 116
	queue_delayed_work(batadv_event_workqueue, &bat_priv->bat_v.ogm_wq,
			   msecs_to_jiffies(msecs));
}

/**
117
 * batadv_v_ogm_send_to_if() - send a batman ogm using a given interface
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
 * @skb: the OGM to send
 * @hard_iface: the interface to use to send the OGM
 */
static void batadv_v_ogm_send_to_if(struct sk_buff *skb,
				    struct batadv_hard_iface *hard_iface)
{
	struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);

	if (hard_iface->if_status != BATADV_IF_ACTIVE)
		return;

	batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_TX);
	batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES,
			   skb->len + ETH_HLEN);

133
	batadv_send_broadcast_skb(skb, hard_iface);
134 135
}

136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
/**
 * batadv_v_ogm_len() - OGMv2 packet length
 * @skb: the OGM to check
 *
 * Return: Length of the given OGMv2 packet, including tvlv length, excluding
 * ethernet header length.
 */
static unsigned int batadv_v_ogm_len(struct sk_buff *skb)
{
	struct batadv_ogm2_packet *ogm_packet;

	ogm_packet = (struct batadv_ogm2_packet *)skb->data;
	return BATADV_OGM2_HLEN + ntohs(ogm_packet->tvlv_len);
}

/**
 * batadv_v_ogm_queue_left() - check if given OGM still fits aggregation queue
 * @skb: the OGM to check
 * @hard_iface: the interface to use to send the OGM
 *
156
 * Caller needs to hold the hard_iface->bat_v.aggr_list.lock.
157 158 159 160 161 162 163 164 165 166
 *
 * Return: True, if the given OGMv2 packet still fits, false otherwise.
 */
static bool batadv_v_ogm_queue_left(struct sk_buff *skb,
				    struct batadv_hard_iface *hard_iface)
{
	unsigned int max = min_t(unsigned int, hard_iface->net_dev->mtu,
				 BATADV_MAX_AGGREGATION_BYTES);
	unsigned int ogm_len = batadv_v_ogm_len(skb);

167
	lockdep_assert_held(&hard_iface->bat_v.aggr_list.lock);
168 169 170 171 172 173 174 175

	return hard_iface->bat_v.aggr_len + ogm_len <= max;
}

/**
 * batadv_v_ogm_aggr_list_free - free all elements in an aggregation queue
 * @hard_iface: the interface holding the aggregation queue
 *
176
 * Empties the OGMv2 aggregation queue and frees all the skbs it contains.
177
 *
178
 * Caller needs to hold the hard_iface->bat_v.aggr_list.lock.
179 180 181
 */
static void batadv_v_ogm_aggr_list_free(struct batadv_hard_iface *hard_iface)
{
182
	lockdep_assert_held(&hard_iface->bat_v.aggr_list.lock);
183

184
	__skb_queue_purge(&hard_iface->bat_v.aggr_list);
185 186 187 188 189 190 191
	hard_iface->bat_v.aggr_len = 0;
}

/**
 * batadv_v_ogm_aggr_send() - flush & send aggregation queue
 * @hard_iface: the interface with the aggregation queue to flush
 *
192 193 194 195 196
 * Aggregates all OGMv2 packets currently in the aggregation queue into a
 * single OGMv2 packet and transmits this aggregate.
 *
 * The aggregation queue is empty after this call.
 *
197
 * Caller needs to hold the hard_iface->bat_v.aggr_list.lock.
198 199 200
 */
static void batadv_v_ogm_aggr_send(struct batadv_hard_iface *hard_iface)
{
201 202 203
	unsigned int aggr_len = hard_iface->bat_v.aggr_len;
	struct sk_buff *skb_aggr;
	unsigned int ogm_len;
204 205
	struct sk_buff *skb;

206
	lockdep_assert_held(&hard_iface->bat_v.aggr_list.lock);
207

208 209 210 211 212 213 214 215 216 217 218 219
	if (!aggr_len)
		return;

	skb_aggr = dev_alloc_skb(aggr_len + ETH_HLEN + NET_IP_ALIGN);
	if (!skb_aggr) {
		batadv_v_ogm_aggr_list_free(hard_iface);
		return;
	}

	skb_reserve(skb_aggr, ETH_HLEN + NET_IP_ALIGN);
	skb_reset_network_header(skb_aggr);

220
	while ((skb = __skb_dequeue(&hard_iface->bat_v.aggr_list))) {
221
		hard_iface->bat_v.aggr_len -= batadv_v_ogm_len(skb);
222 223 224 225 226

		ogm_len = batadv_v_ogm_len(skb);
		skb_put_data(skb_aggr, skb->data, ogm_len);

		consume_skb(skb);
227
	}
228 229

	batadv_v_ogm_send_to_if(skb_aggr, hard_iface);
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
}

/**
 * batadv_v_ogm_queue_on_if() - queue a batman ogm on a given interface
 * @skb: the OGM to queue
 * @hard_iface: the interface to queue the OGM on
 */
static void batadv_v_ogm_queue_on_if(struct sk_buff *skb,
				     struct batadv_hard_iface *hard_iface)
{
	struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);

	if (!atomic_read(&bat_priv->aggregated_ogms)) {
		batadv_v_ogm_send_to_if(skb, hard_iface);
		return;
	}

247
	spin_lock_bh(&hard_iface->bat_v.aggr_list.lock);
248 249 250 251
	if (!batadv_v_ogm_queue_left(skb, hard_iface))
		batadv_v_ogm_aggr_send(hard_iface);

	hard_iface->bat_v.aggr_len += batadv_v_ogm_len(skb);
252 253
	__skb_queue_tail(&hard_iface->bat_v.aggr_list, skb);
	spin_unlock_bh(&hard_iface->bat_v.aggr_list.lock);
254 255
}

256
/**
257 258
 * batadv_v_ogm_send_softif() - periodic worker broadcasting the own OGM
 * @bat_priv: the bat priv with all the soft interface information
259
 */
260
static void batadv_v_ogm_send_softif(struct batadv_priv *bat_priv)
261 262 263 264
{
	struct batadv_hard_iface *hard_iface;
	struct batadv_ogm2_packet *ogm_packet;
	struct sk_buff *skb, *skb_tmp;
265
	unsigned char *ogm_buff;
266 267
	int ogm_buff_len;
	u16 tvlv_len = 0;
268
	int ret;
269

270
	lockdep_assert_held(&bat_priv->bat_v.ogm_buff_mutex);
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292

	if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_DEACTIVATING)
		goto out;

	ogm_buff = bat_priv->bat_v.ogm_buff;
	ogm_buff_len = bat_priv->bat_v.ogm_buff_len;
	/* tt changes have to be committed before the tvlv data is
	 * appended as it may alter the tt tvlv container
	 */
	batadv_tt_local_commit_changes(bat_priv);
	tvlv_len = batadv_tvlv_container_ogm_append(bat_priv, &ogm_buff,
						    &ogm_buff_len,
						    BATADV_OGM2_HLEN);

	bat_priv->bat_v.ogm_buff = ogm_buff;
	bat_priv->bat_v.ogm_buff_len = ogm_buff_len;

	skb = netdev_alloc_skb_ip_align(NULL, ETH_HLEN + ogm_buff_len);
	if (!skb)
		goto reschedule;

	skb_reserve(skb, ETH_HLEN);
293
	skb_put_data(skb, ogm_buff, ogm_buff_len);
294 295 296 297 298 299 300 301 302 303 304 305

	ogm_packet = (struct batadv_ogm2_packet *)skb->data;
	ogm_packet->seqno = htonl(atomic_read(&bat_priv->bat_v.ogm_seqno));
	atomic_inc(&bat_priv->bat_v.ogm_seqno);
	ogm_packet->tvlv_len = htons(tvlv_len);

	/* broadcast on every interface */
	rcu_read_lock();
	list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
		if (hard_iface->soft_iface != bat_priv->soft_iface)
			continue;

306 307 308
		if (!kref_get_unless_zero(&hard_iface->refcount))
			continue;

309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
		ret = batadv_hardif_no_broadcast(hard_iface, NULL, NULL);
		if (ret) {
			char *type;

			switch (ret) {
			case BATADV_HARDIF_BCAST_NORECIPIENT:
				type = "no neighbor";
				break;
			case BATADV_HARDIF_BCAST_DUPFWD:
				type = "single neighbor is source";
				break;
			case BATADV_HARDIF_BCAST_DUPORIG:
				type = "single neighbor is originator";
				break;
			default:
				type = "unknown";
			}

327
			batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "OGM2 from ourselves on %s suppressed: %s\n",
328 329 330 331 332 333
				   hard_iface->net_dev->name, type);

			batadv_hardif_put(hard_iface);
			continue;
		}

334 335 336 337 338 339 340 341 342
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
			   "Sending own OGM2 packet (originator %pM, seqno %u, throughput %u, TTL %d) on interface %s [%pM]\n",
			   ogm_packet->orig, ntohl(ogm_packet->seqno),
			   ntohl(ogm_packet->throughput), ogm_packet->ttl,
			   hard_iface->net_dev->name,
			   hard_iface->net_dev->dev_addr);

		/* this skb gets consumed by batadv_v_ogm_send_to_if() */
		skb_tmp = skb_clone(skb, GFP_ATOMIC);
343 344
		if (!skb_tmp) {
			batadv_hardif_put(hard_iface);
345
			break;
346
		}
347

348
		batadv_v_ogm_queue_on_if(skb_tmp, hard_iface);
349
		batadv_hardif_put(hard_iface);
350 351 352 353 354 355 356 357 358 359 360
	}
	rcu_read_unlock();

	consume_skb(skb);

reschedule:
	batadv_v_ogm_start_timer(bat_priv);
out:
	return;
}

361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
/**
 * batadv_v_ogm_send() - periodic worker broadcasting the own OGM
 * @work: work queue item
 */
static void batadv_v_ogm_send(struct work_struct *work)
{
	struct batadv_priv_bat_v *bat_v;
	struct batadv_priv *bat_priv;

	bat_v = container_of(work, struct batadv_priv_bat_v, ogm_wq.work);
	bat_priv = container_of(bat_v, struct batadv_priv, bat_v);

	mutex_lock(&bat_priv->bat_v.ogm_buff_mutex);
	batadv_v_ogm_send_softif(bat_priv);
	mutex_unlock(&bat_priv->bat_v.ogm_buff_mutex);
}

378 379 380 381
/**
 * batadv_v_ogm_aggr_work() - OGM queue periodic task per interface
 * @work: work queue item
 *
382
 * Emits aggregated OGM messages in regular intervals.
383 384 385 386 387 388 389 390 391
 */
void batadv_v_ogm_aggr_work(struct work_struct *work)
{
	struct batadv_hard_iface_bat_v *batv;
	struct batadv_hard_iface *hard_iface;

	batv = container_of(work, struct batadv_hard_iface_bat_v, aggr_wq.work);
	hard_iface = container_of(batv, struct batadv_hard_iface, bat_v);

392
	spin_lock_bh(&hard_iface->bat_v.aggr_list.lock);
393
	batadv_v_ogm_aggr_send(hard_iface);
394
	spin_unlock_bh(&hard_iface->bat_v.aggr_list.lock);
395 396 397 398

	batadv_v_ogm_start_queue_timer(hard_iface);
}

399
/**
400
 * batadv_v_ogm_iface_enable() - prepare an interface for B.A.T.M.A.N. V
401 402
 * @hard_iface: the interface to prepare
 *
403
 * Takes care of scheduling its own OGM sending routine for this interface.
404 405 406 407 408 409 410
 *
 * Return: 0 on success or a negative error code otherwise
 */
int batadv_v_ogm_iface_enable(struct batadv_hard_iface *hard_iface)
{
	struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface);

411
	batadv_v_ogm_start_queue_timer(hard_iface);
412 413 414 415 416
	batadv_v_ogm_start_timer(bat_priv);

	return 0;
}

417 418 419 420 421 422 423 424
/**
 * batadv_v_ogm_iface_disable() - release OGM interface private resources
 * @hard_iface: interface for which the resources have to be released
 */
void batadv_v_ogm_iface_disable(struct batadv_hard_iface *hard_iface)
{
	cancel_delayed_work_sync(&hard_iface->bat_v.aggr_wq);

425
	spin_lock_bh(&hard_iface->bat_v.aggr_list.lock);
426
	batadv_v_ogm_aggr_list_free(hard_iface);
427
	spin_unlock_bh(&hard_iface->bat_v.aggr_list.lock);
428 429
}

430
/**
431
 * batadv_v_ogm_primary_iface_set() - set a new primary interface
432 433 434 435 436 437 438
 * @primary_iface: the new primary interface
 */
void batadv_v_ogm_primary_iface_set(struct batadv_hard_iface *primary_iface)
{
	struct batadv_priv *bat_priv = netdev_priv(primary_iface->soft_iface);
	struct batadv_ogm2_packet *ogm_packet;

439
	mutex_lock(&bat_priv->bat_v.ogm_buff_mutex);
440
	if (!bat_priv->bat_v.ogm_buff)
441
		goto unlock;
442 443 444

	ogm_packet = (struct batadv_ogm2_packet *)bat_priv->bat_v.ogm_buff;
	ether_addr_copy(ogm_packet->orig, primary_iface->net_dev->dev_addr);
445 446 447

unlock:
	mutex_unlock(&bat_priv->bat_v.ogm_buff_mutex);
448 449
}

450
/**
451 452
 * batadv_v_forward_penalty() - apply a penalty to the throughput metric
 *  forwarded with B.A.T.M.A.N. V OGMs
453 454 455 456 457 458
 * @bat_priv: the bat priv with all the soft interface information
 * @if_incoming: the interface where the OGM has been received
 * @if_outgoing: the interface where the OGM has to be forwarded to
 * @throughput: the current throughput
 *
 * Apply a penalty on the current throughput metric value based on the
459 460 461 462
 * characteristic of the interface where the OGM has been received.
 *
 * Initially the per hardif hop penalty is applied to the throughput. After
 * that the return value is then computed as follows:
463 464 465 466 467 468
 * - throughput * 50%          if the incoming and outgoing interface are the
 *                             same WiFi interface and the throughput is above
 *                             1MBit/s
 * - throughput                if the outgoing interface is the default
 *                             interface (i.e. this OGM is processed for the
 *                             internal table and not forwarded)
469
 * - throughput * node hop penalty  otherwise
470 471 472 473 474 475 476 477
 *
 * Return: the penalised throughput metric.
 */
static u32 batadv_v_forward_penalty(struct batadv_priv *bat_priv,
				    struct batadv_hard_iface *if_incoming,
				    struct batadv_hard_iface *if_outgoing,
				    u32 throughput)
{
478
	int if_hop_penalty = atomic_read(&if_incoming->hop_penalty);
479 480 481
	int hop_penalty = atomic_read(&bat_priv->hop_penalty);
	int hop_penalty_max = BATADV_TQ_MAX_VALUE;

482 483 484 485
	/* Apply per hardif hop penalty */
	throughput = throughput * (hop_penalty_max - if_hop_penalty) /
		     hop_penalty_max;

486 487 488 489 490 491 492 493
	/* Don't apply hop penalty in default originator table. */
	if (if_outgoing == BATADV_IF_DEFAULT)
		return throughput;

	/* Forwarding on the same WiFi interface cuts the throughput in half
	 * due to the store & forward characteristics of WIFI.
	 * Very low throughput values are the exception.
	 */
494 495
	if (throughput > 10 &&
	    if_incoming == if_outgoing &&
496
	    !(if_incoming->bat_v.flags & BATADV_FULL_DUPLEX))
497 498 499 500 501 502 503
		return throughput / 2;

	/* hop penalty of 255 equals 100% */
	return throughput * (hop_penalty_max - hop_penalty) / hop_penalty_max;
}

/**
504
 * batadv_v_ogm_forward() - check conditions and forward an OGM to the given
505
 *  outgoing interface
506 507
 * @bat_priv: the bat priv with all the soft interface information
 * @ogm_received: previously received OGM to be forwarded
508 509
 * @orig_node: the originator which has been updated
 * @neigh_node: the neigh_node through with the OGM has been received
510 511 512 513 514 515 516 517
 * @if_incoming: the interface on which this OGM was received on
 * @if_outgoing: the interface to which the OGM has to be forwarded to
 *
 * Forward an OGM to an interface after having altered the throughput metric and
 * the TTL value contained in it. The original OGM isn't modified.
 */
static void batadv_v_ogm_forward(struct batadv_priv *bat_priv,
				 const struct batadv_ogm2_packet *ogm_received,
518 519
				 struct batadv_orig_node *orig_node,
				 struct batadv_neigh_node *neigh_node,
520 521 522
				 struct batadv_hard_iface *if_incoming,
				 struct batadv_hard_iface *if_outgoing)
{
523 524 525
	struct batadv_neigh_ifinfo *neigh_ifinfo = NULL;
	struct batadv_orig_ifinfo *orig_ifinfo = NULL;
	struct batadv_neigh_node *router = NULL;
526 527 528 529 530 531
	struct batadv_ogm2_packet *ogm_forward;
	unsigned char *skb_buff;
	struct sk_buff *skb;
	size_t packet_len;
	u16 tvlv_len;

532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552
	/* only forward for specific interfaces, not for the default one. */
	if (if_outgoing == BATADV_IF_DEFAULT)
		goto out;

	orig_ifinfo = batadv_orig_ifinfo_new(orig_node, if_outgoing);
	if (!orig_ifinfo)
		goto out;

	/* acquire possibly updated router */
	router = batadv_orig_router_get(orig_node, if_outgoing);

	/* strict rule: forward packets coming from the best next hop only */
	if (neigh_node != router)
		goto out;

	/* don't forward the same seqno twice on one interface */
	if (orig_ifinfo->last_seqno_forwarded == ntohl(ogm_received->seqno))
		goto out;

	orig_ifinfo->last_seqno_forwarded = ntohl(ogm_received->seqno);

553 554
	if (ogm_received->ttl <= 1) {
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "ttl exceeded\n");
555
		goto out;
556 557
	}

558 559 560 561
	neigh_ifinfo = batadv_neigh_ifinfo_get(neigh_node, if_outgoing);
	if (!neigh_ifinfo)
		goto out;

562 563 564 565 566 567
	tvlv_len = ntohs(ogm_received->tvlv_len);

	packet_len = BATADV_OGM2_HLEN + tvlv_len;
	skb = netdev_alloc_skb_ip_align(if_outgoing->net_dev,
					ETH_HLEN + packet_len);
	if (!skb)
568
		goto out;
569 570

	skb_reserve(skb, ETH_HLEN);
571
	skb_buff = skb_put_data(skb, ogm_received, packet_len);
572 573 574

	/* apply forward penalty */
	ogm_forward = (struct batadv_ogm2_packet *)skb_buff;
575
	ogm_forward->throughput = htonl(neigh_ifinfo->bat_v.throughput);
576 577 578 579
	ogm_forward->ttl--;

	batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
		   "Forwarding OGM2 packet on %s: throughput %u, ttl %u, received via %s\n",
580 581
		   if_outgoing->net_dev->name, ntohl(ogm_forward->throughput),
		   ogm_forward->ttl, if_incoming->net_dev->name);
582

583
	batadv_v_ogm_queue_on_if(skb, if_outgoing);
584 585 586 587 588 589 590 591

out:
	if (orig_ifinfo)
		batadv_orig_ifinfo_put(orig_ifinfo);
	if (router)
		batadv_neigh_node_put(router);
	if (neigh_ifinfo)
		batadv_neigh_ifinfo_put(neigh_ifinfo);
592 593 594
}

/**
595
 * batadv_v_ogm_metric_update() - update route metric based on OGM
596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614
 * @bat_priv: the bat priv with all the soft interface information
 * @ogm2: OGM2 structure
 * @orig_node: Originator structure for which the OGM has been received
 * @neigh_node: the neigh_node through with the OGM has been received
 * @if_incoming: the interface where this packet was received
 * @if_outgoing: the interface for which the packet should be considered
 *
 * Return:
 *  1  if the OGM is new,
 *  0  if it is not new but valid,
 *  <0 on error (e.g. old OGM)
 */
static int batadv_v_ogm_metric_update(struct batadv_priv *bat_priv,
				      const struct batadv_ogm2_packet *ogm2,
				      struct batadv_orig_node *orig_node,
				      struct batadv_neigh_node *neigh_node,
				      struct batadv_hard_iface *if_incoming,
				      struct batadv_hard_iface *if_outgoing)
{
615
	struct batadv_orig_ifinfo *orig_ifinfo;
616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644
	struct batadv_neigh_ifinfo *neigh_ifinfo = NULL;
	bool protection_started = false;
	int ret = -EINVAL;
	u32 path_throughput;
	s32 seq_diff;

	orig_ifinfo = batadv_orig_ifinfo_new(orig_node, if_outgoing);
	if (!orig_ifinfo)
		goto out;

	seq_diff = ntohl(ogm2->seqno) - orig_ifinfo->last_real_seqno;

	if (!hlist_empty(&orig_node->neigh_list) &&
	    batadv_window_protected(bat_priv, seq_diff,
				    BATADV_OGM_MAX_AGE,
				    &orig_ifinfo->batman_seqno_reset,
				    &protection_started)) {
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
			   "Drop packet: packet within window protection time from %pM\n",
			   ogm2->orig);
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
			   "Last reset: %ld, %ld\n",
			   orig_ifinfo->batman_seqno_reset, jiffies);
		goto out;
	}

	/* drop packets with old seqnos, however accept the first packet after
	 * a host has been rebooted.
	 */
645
	if (seq_diff < 0 && !protection_started)
646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679
		goto out;

	neigh_node->last_seen = jiffies;

	orig_node->last_seen = jiffies;

	orig_ifinfo->last_real_seqno = ntohl(ogm2->seqno);
	orig_ifinfo->last_ttl = ogm2->ttl;

	neigh_ifinfo = batadv_neigh_ifinfo_new(neigh_node, if_outgoing);
	if (!neigh_ifinfo)
		goto out;

	path_throughput = batadv_v_forward_penalty(bat_priv, if_incoming,
						   if_outgoing,
						   ntohl(ogm2->throughput));
	neigh_ifinfo->bat_v.throughput = path_throughput;
	neigh_ifinfo->bat_v.last_seqno = ntohl(ogm2->seqno);
	neigh_ifinfo->last_ttl = ogm2->ttl;

	if (seq_diff > 0 || protection_started)
		ret = 1;
	else
		ret = 0;
out:
	if (orig_ifinfo)
		batadv_orig_ifinfo_put(orig_ifinfo);
	if (neigh_ifinfo)
		batadv_neigh_ifinfo_put(neigh_ifinfo);

	return ret;
}

/**
680
 * batadv_v_ogm_route_update() - update routes based on OGM
681 682 683 684 685 686 687
 * @bat_priv: the bat priv with all the soft interface information
 * @ethhdr: the Ethernet header of the OGM2
 * @ogm2: OGM2 structure
 * @orig_node: Originator structure for which the OGM has been received
 * @neigh_node: the neigh_node through with the OGM has been received
 * @if_incoming: the interface where this packet was received
 * @if_outgoing: the interface for which the packet should be considered
688 689
 *
 * Return: true if the packet should be forwarded, false otherwise
690
 */
691
static bool batadv_v_ogm_route_update(struct batadv_priv *bat_priv,
692 693 694 695 696 697 698 699
				      const struct ethhdr *ethhdr,
				      const struct batadv_ogm2_packet *ogm2,
				      struct batadv_orig_node *orig_node,
				      struct batadv_neigh_node *neigh_node,
				      struct batadv_hard_iface *if_incoming,
				      struct batadv_hard_iface *if_outgoing)
{
	struct batadv_neigh_node *router = NULL;
700
	struct batadv_orig_node *orig_neigh_node;
701
	struct batadv_neigh_node *orig_neigh_router = NULL;
702 703 704 705 706
	struct batadv_neigh_ifinfo *router_ifinfo = NULL, *neigh_ifinfo = NULL;
	u32 router_throughput, neigh_throughput;
	u32 router_last_seqno;
	u32 neigh_last_seqno;
	s32 neigh_seq_diff;
707
	bool forward = false;
708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725

	orig_neigh_node = batadv_v_ogm_orig_get(bat_priv, ethhdr->h_source);
	if (!orig_neigh_node)
		goto out;

	orig_neigh_router = batadv_orig_router_get(orig_neigh_node,
						   if_outgoing);

	/* drop packet if sender is not a direct neighbor and if we
	 * don't route towards it
	 */
	router = batadv_orig_router_get(orig_node, if_outgoing);
	if (router && router->orig_node != orig_node && !orig_neigh_router) {
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
			   "Drop packet: OGM via unknown neighbor!\n");
		goto out;
	}

726 727 728
	/* Mark the OGM to be considered for forwarding, and update routes
	 * if needed.
	 */
729
	forward = true;
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757

	batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
		   "Searching and updating originator entry of received packet\n");

	/* if this neighbor already is our next hop there is nothing
	 * to change
	 */
	if (router == neigh_node)
		goto out;

	/* don't consider neighbours with worse throughput.
	 * also switch route if this seqno is BATADV_V_MAX_ORIGDIFF newer than
	 * the last received seqno from our best next hop.
	 */
	if (router) {
		router_ifinfo = batadv_neigh_ifinfo_get(router, if_outgoing);
		neigh_ifinfo = batadv_neigh_ifinfo_get(neigh_node, if_outgoing);

		/* if these are not allocated, something is wrong. */
		if (!router_ifinfo || !neigh_ifinfo)
			goto out;

		neigh_last_seqno = neigh_ifinfo->bat_v.last_seqno;
		router_last_seqno = router_ifinfo->bat_v.last_seqno;
		neigh_seq_diff = neigh_last_seqno - router_last_seqno;
		router_throughput = router_ifinfo->bat_v.throughput;
		neigh_throughput = neigh_ifinfo->bat_v.throughput;

758 759
		if (neigh_seq_diff < BATADV_OGM_MAX_ORIGDIFF &&
		    router_throughput >= neigh_throughput)
760 761 762 763
			goto out;
	}

	batadv_update_route(bat_priv, orig_node, if_outgoing, neigh_node);
764 765 766 767 768 769 770
out:
	if (router)
		batadv_neigh_node_put(router);
	if (orig_neigh_router)
		batadv_neigh_node_put(orig_neigh_router);
	if (orig_neigh_node)
		batadv_orig_node_put(orig_neigh_node);
771 772 773 774
	if (router_ifinfo)
		batadv_neigh_ifinfo_put(router_ifinfo);
	if (neigh_ifinfo)
		batadv_neigh_ifinfo_put(neigh_ifinfo);
775 776

	return forward;
777 778 779
}

/**
780
 * batadv_v_ogm_process_per_outif() - process a batman v OGM for an outgoing if
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798
 * @bat_priv: the bat priv with all the soft interface information
 * @ethhdr: the Ethernet header of the OGM2
 * @ogm2: OGM2 structure
 * @orig_node: Originator structure for which the OGM has been received
 * @neigh_node: the neigh_node through with the OGM has been received
 * @if_incoming: the interface where this packet was received
 * @if_outgoing: the interface for which the packet should be considered
 */
static void
batadv_v_ogm_process_per_outif(struct batadv_priv *bat_priv,
			       const struct ethhdr *ethhdr,
			       const struct batadv_ogm2_packet *ogm2,
			       struct batadv_orig_node *orig_node,
			       struct batadv_neigh_node *neigh_node,
			       struct batadv_hard_iface *if_incoming,
			       struct batadv_hard_iface *if_outgoing)
{
	int seqno_age;
799
	bool forward;
800 801 802 803 804 805 806 807 808 809 810

	/* first, update the metric with according sanity checks */
	seqno_age = batadv_v_ogm_metric_update(bat_priv, ogm2, orig_node,
					       neigh_node, if_incoming,
					       if_outgoing);

	/* outdated sequence numbers are to be discarded */
	if (seqno_age < 0)
		return;

	/* only unknown & newer OGMs contain TVLVs we are interested in */
811
	if (seqno_age > 0 && if_outgoing == BATADV_IF_DEFAULT)
812 813 814 815 816 817
		batadv_tvlv_containers_process(bat_priv, true, orig_node,
					       NULL, NULL,
					       (unsigned char *)(ogm2 + 1),
					       ntohs(ogm2->tvlv_len));

	/* if the metric update went through, update routes if needed */
818 819 820 821 822 823 824 825
	forward = batadv_v_ogm_route_update(bat_priv, ethhdr, ogm2, orig_node,
					    neigh_node, if_incoming,
					    if_outgoing);

	/* if the routes have been processed correctly, check and forward */
	if (forward)
		batadv_v_ogm_forward(bat_priv, ogm2, orig_node, neigh_node,
				     if_incoming, if_outgoing);
826 827 828
}

/**
829
 * batadv_v_ogm_aggr_packet() - checks if there is another OGM aggregated
830 831
 * @buff_pos: current position in the skb
 * @packet_len: total length of the skb
832
 * @ogm2_packet: potential OGM2 in buffer
833 834 835
 *
 * Return: true if there is enough space for another OGM, false otherwise.
 */
836 837 838
static bool
batadv_v_ogm_aggr_packet(int buff_pos, int packet_len,
			 const struct batadv_ogm2_packet *ogm2_packet)
839 840 841
{
	int next_buff_pos = 0;

842 843 844 845 846 847 848
	/* check if there is enough space for the header */
	next_buff_pos += buff_pos + sizeof(*ogm2_packet);
	if (next_buff_pos > packet_len)
		return false;

	/* check if there is enough space for the optional TVLV */
	next_buff_pos += ntohs(ogm2_packet->tvlv_len);
849 850 851 852 853 854

	return (next_buff_pos <= packet_len) &&
	       (next_buff_pos <= BATADV_MAX_AGGREGATION_BYTES);
}

/**
855
 * batadv_v_ogm_process() - process an incoming batman v OGM
856 857
 * @skb: the skb containing the OGM
 * @ogm_offset: offset to the OGM which should be processed (for aggregates)
858
 * @if_incoming: the interface where this packet was received
859 860 861 862 863 864 865 866 867 868 869 870
 */
static void batadv_v_ogm_process(const struct sk_buff *skb, int ogm_offset,
				 struct batadv_hard_iface *if_incoming)
{
	struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
	struct ethhdr *ethhdr;
	struct batadv_orig_node *orig_node = NULL;
	struct batadv_hardif_neigh_node *hardif_neigh = NULL;
	struct batadv_neigh_node *neigh_node = NULL;
	struct batadv_hard_iface *hard_iface;
	struct batadv_ogm2_packet *ogm_packet;
	u32 ogm_throughput, link_throughput, path_throughput;
871
	int ret;
872 873 874 875 876 877 878

	ethhdr = eth_hdr(skb);
	ogm_packet = (struct batadv_ogm2_packet *)(skb->data + ogm_offset);

	ogm_throughput = ntohl(ogm_packet->throughput);

	batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
879
		   "Received OGM2 packet via NB: %pM, IF: %s [%pM] (from OG: %pM, seqno %u, throughput %u, TTL %u, V %u, tvlv_len %u)\n",
880 881 882 883 884
		   ethhdr->h_source, if_incoming->net_dev->name,
		   if_incoming->net_dev->dev_addr, ogm_packet->orig,
		   ntohl(ogm_packet->seqno), ogm_throughput, ogm_packet->ttl,
		   ogm_packet->version, ntohs(ogm_packet->tvlv_len));

885 886
	/* If the throughput metric is 0, immediately drop the packet. No need
	 * to create orig_node / neigh_node for an unusable route.
887 888 889
	 */
	if (ogm_throughput == 0) {
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
890
			   "Drop packet: originator packet with throughput metric of 0\n");
891 892 893 894 895 896 897 898 899 900 901 902 903
		return;
	}

	/* require ELP packets be to received from this neighbor first */
	hardif_neigh = batadv_hardif_neigh_get(if_incoming, ethhdr->h_source);
	if (!hardif_neigh) {
		batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
			   "Drop packet: OGM via unknown neighbor!\n");
		goto out;
	}

	orig_node = batadv_v_ogm_orig_get(bat_priv, ogm_packet->orig);
	if (!orig_node)
904
		goto out;
905

906 907
	neigh_node = batadv_neigh_node_get_or_create(orig_node, if_incoming,
						     ethhdr->h_source);
908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933
	if (!neigh_node)
		goto out;

	/* Update the received throughput metric to match the link
	 * characteristic:
	 *  - If this OGM traveled one hop so far (emitted by single hop
	 *    neighbor) the path throughput metric equals the link throughput.
	 *  - For OGMs traversing more than hop the path throughput metric is
	 *    the smaller of the path throughput and the link throughput.
	 */
	link_throughput = ewma_throughput_read(&hardif_neigh->bat_v.throughput);
	path_throughput = min_t(u32, link_throughput, ogm_throughput);
	ogm_packet->throughput = htonl(path_throughput);

	batadv_v_ogm_process_per_outif(bat_priv, ethhdr, ogm_packet, orig_node,
				       neigh_node, if_incoming,
				       BATADV_IF_DEFAULT);

	rcu_read_lock();
	list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) {
		if (hard_iface->if_status != BATADV_IF_ACTIVE)
			continue;

		if (hard_iface->soft_iface != bat_priv->soft_iface)
			continue;

934 935 936
		if (!kref_get_unless_zero(&hard_iface->refcount))
			continue;

937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957
		ret = batadv_hardif_no_broadcast(hard_iface,
						 ogm_packet->orig,
						 hardif_neigh->orig);

		if (ret) {
			char *type;

			switch (ret) {
			case BATADV_HARDIF_BCAST_NORECIPIENT:
				type = "no neighbor";
				break;
			case BATADV_HARDIF_BCAST_DUPFWD:
				type = "single neighbor is source";
				break;
			case BATADV_HARDIF_BCAST_DUPORIG:
				type = "single neighbor is originator";
				break;
			default:
				type = "unknown";
			}

958
			batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "OGM2 packet from %pM on %s suppressed: %s\n",
959 960 961 962 963 964 965
				   ogm_packet->orig, hard_iface->net_dev->name,
				   type);

			batadv_hardif_put(hard_iface);
			continue;
		}

966 967 968
		batadv_v_ogm_process_per_outif(bat_priv, ethhdr, ogm_packet,
					       orig_node, neigh_node,
					       if_incoming, hard_iface);
969 970

		batadv_hardif_put(hard_iface);
971 972 973 974 975 976 977 978 979 980 981
	}
	rcu_read_unlock();
out:
	if (orig_node)
		batadv_orig_node_put(orig_node);
	if (neigh_node)
		batadv_neigh_node_put(neigh_node);
	if (hardif_neigh)
		batadv_hardif_neigh_put(hardif_neigh);
}

982
/**
983
 * batadv_v_ogm_packet_recv() - OGM2 receiving handler
984 985 986 987 988 989 990 991 992 993 994 995
 * @skb: the received OGM
 * @if_incoming: the interface where this OGM has been received
 *
 * Return: NET_RX_SUCCESS and consume the skb on success or returns NET_RX_DROP
 * (without freeing the skb) on failure
 */
int batadv_v_ogm_packet_recv(struct sk_buff *skb,
			     struct batadv_hard_iface *if_incoming)
{
	struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface);
	struct batadv_ogm2_packet *ogm_packet;
	struct ethhdr *ethhdr = eth_hdr(skb);
996 997 998
	int ogm_offset;
	u8 *packet_pos;
	int ret = NET_RX_DROP;
999 1000 1001 1002

	/* did we receive a OGM2 packet on an interface that does not have
	 * B.A.T.M.A.N. V enabled ?
	 */
1003
	if (strcmp(bat_priv->algo_ops->name, "BATMAN_V") != 0)
1004
		goto free_skb;
1005 1006

	if (!batadv_check_management_packet(skb, if_incoming, BATADV_OGM2_HLEN))
1007
		goto free_skb;
1008 1009

	if (batadv_is_my_mac(bat_priv, ethhdr->h_source))
1010
		goto free_skb;
1011 1012 1013 1014

	ogm_packet = (struct batadv_ogm2_packet *)skb->data;

	if (batadv_is_my_mac(bat_priv, ogm_packet->orig))
1015
		goto free_skb;
1016 1017 1018 1019 1020

	batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_RX);
	batadv_add_counter(bat_priv, BATADV_CNT_MGMT_RX_BYTES,
			   skb->len + ETH_HLEN);

1021 1022 1023 1024
	ogm_offset = 0;
	ogm_packet = (struct batadv_ogm2_packet *)skb->data;

	while (batadv_v_ogm_aggr_packet(ogm_offset, skb_headlen(skb),
1025
					ogm_packet)) {
1026 1027 1028 1029 1030 1031 1032 1033 1034 1035
		batadv_v_ogm_process(skb, ogm_offset, if_incoming);

		ogm_offset += BATADV_OGM2_HLEN;
		ogm_offset += ntohs(ogm_packet->tvlv_len);

		packet_pos = skb->data + ogm_offset;
		ogm_packet = (struct batadv_ogm2_packet *)packet_pos;
	}

	ret = NET_RX_SUCCESS;
1036 1037 1038 1039 1040 1041

free_skb:
	if (ret == NET_RX_SUCCESS)
		consume_skb(skb);
	else
		kfree_skb(skb);
1042 1043

	return ret;
1044 1045 1046
}

/**
1047
 * batadv_v_ogm_init() - initialise the OGM2 engine
1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075
 * @bat_priv: the bat priv with all the soft interface information
 *
 * Return: 0 on success or a negative error code in case of failure
 */
int batadv_v_ogm_init(struct batadv_priv *bat_priv)
{
	struct batadv_ogm2_packet *ogm_packet;
	unsigned char *ogm_buff;
	u32 random_seqno;

	bat_priv->bat_v.ogm_buff_len = BATADV_OGM2_HLEN;
	ogm_buff = kzalloc(bat_priv->bat_v.ogm_buff_len, GFP_ATOMIC);
	if (!ogm_buff)
		return -ENOMEM;

	bat_priv->bat_v.ogm_buff = ogm_buff;
	ogm_packet = (struct batadv_ogm2_packet *)ogm_buff;
	ogm_packet->packet_type = BATADV_OGM2;
	ogm_packet->version = BATADV_COMPAT_VERSION;
	ogm_packet->ttl = BATADV_TTL;
	ogm_packet->flags = BATADV_NO_FLAGS;
	ogm_packet->throughput = htonl(BATADV_THROUGHPUT_MAX_VALUE);

	/* randomize initial seqno to avoid collision */
	get_random_bytes(&random_seqno, sizeof(random_seqno));
	atomic_set(&bat_priv->bat_v.ogm_seqno, random_seqno);
	INIT_DELAYED_WORK(&bat_priv->bat_v.ogm_wq, batadv_v_ogm_send);

1076 1077
	mutex_init(&bat_priv->bat_v.ogm_buff_mutex);

1078 1079 1080 1081
	return 0;
}

/**
1082
 * batadv_v_ogm_free() - free OGM private resources
1083 1084 1085 1086 1087 1088
 * @bat_priv: the bat priv with all the soft interface information
 */
void batadv_v_ogm_free(struct batadv_priv *bat_priv)
{
	cancel_delayed_work_sync(&bat_priv->bat_v.ogm_wq);

1089 1090
	mutex_lock(&bat_priv->bat_v.ogm_buff_mutex);

1091 1092 1093
	kfree(bat_priv->bat_v.ogm_buff);
	bat_priv->bat_v.ogm_buff = NULL;
	bat_priv->bat_v.ogm_buff_len = 0;
1094 1095

	mutex_unlock(&bat_priv->bat_v.ogm_buff_mutex);
1096
}