1 /* Copyright (C) 2007-2013 B.A.T.M.A.N. contributors: 2 * 3 * Marek Lindner, Simon Wunderlich 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 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 17 * 02110-1301, USA 18 */ 19 20 #include "main.h" 21 #include "translation-table.h" 22 #include "originator.h" 23 #include "routing.h" 24 #include "gateway_common.h" 25 #include "gateway_client.h" 26 #include "hard-interface.h" 27 #include "send.h" 28 #include "bat_algo.h" 29 #include "network-coding.h" 30 31 /** 32 * batadv_ring_buffer_set - update the ring buffer with the given value 33 * @lq_recv: pointer to the ring buffer 34 * @lq_index: index to store the value at 35 * @value: value to store in the ring buffer 36 */ 37 static void batadv_ring_buffer_set(uint8_t lq_recv[], uint8_t *lq_index, 38 uint8_t value) 39 { 40 lq_recv[*lq_index] = value; 41 *lq_index = (*lq_index + 1) % BATADV_TQ_GLOBAL_WINDOW_SIZE; 42 } 43 44 /** 45 * batadv_ring_buffer_set - compute the average of all non-zero values stored 46 * in the given ring buffer 47 * @lq_recv: pointer to the ring buffer 48 * 49 * Returns computed average value. 50 */ 51 static uint8_t batadv_ring_buffer_avg(const uint8_t lq_recv[]) 52 { 53 const uint8_t *ptr; 54 uint16_t count = 0, i = 0, sum = 0; 55 56 ptr = lq_recv; 57 58 while (i < BATADV_TQ_GLOBAL_WINDOW_SIZE) { 59 if (*ptr != 0) { 60 count++; 61 sum += *ptr; 62 } 63 64 i++; 65 ptr++; 66 } 67 68 if (count == 0) 69 return 0; 70 71 return (uint8_t)(sum / count); 72 } 73 74 /* 75 * batadv_dup_status - duplicate status 76 * @BATADV_NO_DUP: the packet is a duplicate 77 * @BATADV_ORIG_DUP: OGM is a duplicate in the originator (but not for the 78 * neighbor) 79 * @BATADV_NEIGH_DUP: OGM is a duplicate for the neighbor 80 * @BATADV_PROTECTED: originator is currently protected (after reboot) 81 */ 82 enum batadv_dup_status { 83 BATADV_NO_DUP = 0, 84 BATADV_ORIG_DUP, 85 BATADV_NEIGH_DUP, 86 BATADV_PROTECTED, 87 }; 88 89 static struct batadv_neigh_node * 90 batadv_iv_ogm_neigh_new(struct batadv_hard_iface *hard_iface, 91 const uint8_t *neigh_addr, 92 struct batadv_orig_node *orig_node, 93 struct batadv_orig_node *orig_neigh) 94 { 95 struct batadv_neigh_node *neigh_node; 96 97 neigh_node = batadv_neigh_node_new(hard_iface, neigh_addr); 98 if (!neigh_node) 99 goto out; 100 101 INIT_LIST_HEAD(&neigh_node->bonding_list); 102 103 neigh_node->orig_node = orig_neigh; 104 neigh_node->if_incoming = hard_iface; 105 106 spin_lock_bh(&orig_node->neigh_list_lock); 107 hlist_add_head_rcu(&neigh_node->list, &orig_node->neigh_list); 108 spin_unlock_bh(&orig_node->neigh_list_lock); 109 110 out: 111 return neigh_node; 112 } 113 114 static int batadv_iv_ogm_iface_enable(struct batadv_hard_iface *hard_iface) 115 { 116 struct batadv_ogm_packet *batadv_ogm_packet; 117 unsigned char *ogm_buff; 118 uint32_t random_seqno; 119 int res = -ENOMEM; 120 121 /* randomize initial seqno to avoid collision */ 122 get_random_bytes(&random_seqno, sizeof(random_seqno)); 123 atomic_set(&hard_iface->bat_iv.ogm_seqno, random_seqno); 124 125 hard_iface->bat_iv.ogm_buff_len = BATADV_OGM_HLEN; 126 ogm_buff = kmalloc(hard_iface->bat_iv.ogm_buff_len, GFP_ATOMIC); 127 if (!ogm_buff) 128 goto out; 129 130 hard_iface->bat_iv.ogm_buff = ogm_buff; 131 132 batadv_ogm_packet = (struct batadv_ogm_packet *)ogm_buff; 133 batadv_ogm_packet->header.packet_type = BATADV_IV_OGM; 134 batadv_ogm_packet->header.version = BATADV_COMPAT_VERSION; 135 batadv_ogm_packet->header.ttl = 2; 136 batadv_ogm_packet->flags = BATADV_NO_FLAGS; 137 batadv_ogm_packet->tq = BATADV_TQ_MAX_VALUE; 138 batadv_ogm_packet->tt_num_changes = 0; 139 batadv_ogm_packet->ttvn = 0; 140 141 res = 0; 142 143 out: 144 return res; 145 } 146 147 static void batadv_iv_ogm_iface_disable(struct batadv_hard_iface *hard_iface) 148 { 149 kfree(hard_iface->bat_iv.ogm_buff); 150 hard_iface->bat_iv.ogm_buff = NULL; 151 } 152 153 static void batadv_iv_ogm_iface_update_mac(struct batadv_hard_iface *hard_iface) 154 { 155 struct batadv_ogm_packet *batadv_ogm_packet; 156 unsigned char *ogm_buff = hard_iface->bat_iv.ogm_buff; 157 158 batadv_ogm_packet = (struct batadv_ogm_packet *)ogm_buff; 159 memcpy(batadv_ogm_packet->orig, 160 hard_iface->net_dev->dev_addr, ETH_ALEN); 161 memcpy(batadv_ogm_packet->prev_sender, 162 hard_iface->net_dev->dev_addr, ETH_ALEN); 163 } 164 165 static void 166 batadv_iv_ogm_primary_iface_set(struct batadv_hard_iface *hard_iface) 167 { 168 struct batadv_ogm_packet *batadv_ogm_packet; 169 unsigned char *ogm_buff = hard_iface->bat_iv.ogm_buff; 170 171 batadv_ogm_packet = (struct batadv_ogm_packet *)ogm_buff; 172 batadv_ogm_packet->flags = BATADV_PRIMARIES_FIRST_HOP; 173 batadv_ogm_packet->header.ttl = BATADV_TTL; 174 } 175 176 /* when do we schedule our own ogm to be sent */ 177 static unsigned long 178 batadv_iv_ogm_emit_send_time(const struct batadv_priv *bat_priv) 179 { 180 unsigned int msecs; 181 182 msecs = atomic_read(&bat_priv->orig_interval) - BATADV_JITTER; 183 msecs += prandom_u32() % (2 * BATADV_JITTER); 184 185 return jiffies + msecs_to_jiffies(msecs); 186 } 187 188 /* when do we schedule a ogm packet to be sent */ 189 static unsigned long batadv_iv_ogm_fwd_send_time(void) 190 { 191 return jiffies + msecs_to_jiffies(prandom_u32() % (BATADV_JITTER / 2)); 192 } 193 194 /* apply hop penalty for a normal link */ 195 static uint8_t batadv_hop_penalty(uint8_t tq, 196 const struct batadv_priv *bat_priv) 197 { 198 int hop_penalty = atomic_read(&bat_priv->hop_penalty); 199 int new_tq; 200 201 new_tq = tq * (BATADV_TQ_MAX_VALUE - hop_penalty); 202 new_tq /= BATADV_TQ_MAX_VALUE; 203 204 return new_tq; 205 } 206 207 /* is there another aggregated packet here? */ 208 static int batadv_iv_ogm_aggr_packet(int buff_pos, int packet_len, 209 int tt_num_changes) 210 { 211 int next_buff_pos = 0; 212 213 next_buff_pos += buff_pos + BATADV_OGM_HLEN; 214 next_buff_pos += batadv_tt_len(tt_num_changes); 215 216 return (next_buff_pos <= packet_len) && 217 (next_buff_pos <= BATADV_MAX_AGGREGATION_BYTES); 218 } 219 220 /* send a batman ogm to a given interface */ 221 static void batadv_iv_ogm_send_to_if(struct batadv_forw_packet *forw_packet, 222 struct batadv_hard_iface *hard_iface) 223 { 224 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); 225 char *fwd_str; 226 uint8_t packet_num; 227 int16_t buff_pos; 228 struct batadv_ogm_packet *batadv_ogm_packet; 229 struct sk_buff *skb; 230 uint8_t *packet_pos; 231 232 if (hard_iface->if_status != BATADV_IF_ACTIVE) 233 return; 234 235 packet_num = 0; 236 buff_pos = 0; 237 packet_pos = forw_packet->skb->data; 238 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos; 239 240 /* adjust all flags and log packets */ 241 while (batadv_iv_ogm_aggr_packet(buff_pos, forw_packet->packet_len, 242 batadv_ogm_packet->tt_num_changes)) { 243 /* we might have aggregated direct link packets with an 244 * ordinary base packet 245 */ 246 if (forw_packet->direct_link_flags & BIT(packet_num) && 247 forw_packet->if_incoming == hard_iface) 248 batadv_ogm_packet->flags |= BATADV_DIRECTLINK; 249 else 250 batadv_ogm_packet->flags &= ~BATADV_DIRECTLINK; 251 252 if (packet_num > 0 || !forw_packet->own) 253 fwd_str = "Forwarding"; 254 else 255 fwd_str = "Sending own"; 256 257 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 258 "%s %spacket (originator %pM, seqno %u, TQ %d, TTL %d, IDF %s, ttvn %d) on interface %s [%pM]\n", 259 fwd_str, (packet_num > 0 ? "aggregated " : ""), 260 batadv_ogm_packet->orig, 261 ntohl(batadv_ogm_packet->seqno), 262 batadv_ogm_packet->tq, batadv_ogm_packet->header.ttl, 263 (batadv_ogm_packet->flags & BATADV_DIRECTLINK ? 264 "on" : "off"), 265 batadv_ogm_packet->ttvn, hard_iface->net_dev->name, 266 hard_iface->net_dev->dev_addr); 267 268 buff_pos += BATADV_OGM_HLEN; 269 buff_pos += batadv_tt_len(batadv_ogm_packet->tt_num_changes); 270 packet_num++; 271 packet_pos = forw_packet->skb->data + buff_pos; 272 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos; 273 } 274 275 /* create clone because function is called more than once */ 276 skb = skb_clone(forw_packet->skb, GFP_ATOMIC); 277 if (skb) { 278 batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_TX); 279 batadv_add_counter(bat_priv, BATADV_CNT_MGMT_TX_BYTES, 280 skb->len + ETH_HLEN); 281 batadv_send_skb_packet(skb, hard_iface, batadv_broadcast_addr); 282 } 283 } 284 285 /* send a batman ogm packet */ 286 static void batadv_iv_ogm_emit(struct batadv_forw_packet *forw_packet) 287 { 288 struct batadv_hard_iface *hard_iface; 289 struct net_device *soft_iface; 290 struct batadv_priv *bat_priv; 291 struct batadv_hard_iface *primary_if = NULL; 292 struct batadv_ogm_packet *batadv_ogm_packet; 293 unsigned char directlink; 294 uint8_t *packet_pos; 295 296 packet_pos = forw_packet->skb->data; 297 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos; 298 directlink = (batadv_ogm_packet->flags & BATADV_DIRECTLINK ? 1 : 0); 299 300 if (!forw_packet->if_incoming) { 301 pr_err("Error - can't forward packet: incoming iface not specified\n"); 302 goto out; 303 } 304 305 soft_iface = forw_packet->if_incoming->soft_iface; 306 bat_priv = netdev_priv(soft_iface); 307 308 if (forw_packet->if_incoming->if_status != BATADV_IF_ACTIVE) 309 goto out; 310 311 primary_if = batadv_primary_if_get_selected(bat_priv); 312 if (!primary_if) 313 goto out; 314 315 /* multihomed peer assumed 316 * non-primary OGMs are only broadcasted on their interface 317 */ 318 if ((directlink && (batadv_ogm_packet->header.ttl == 1)) || 319 (forw_packet->own && (forw_packet->if_incoming != primary_if))) { 320 /* FIXME: what about aggregated packets ? */ 321 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 322 "%s packet (originator %pM, seqno %u, TTL %d) on interface %s [%pM]\n", 323 (forw_packet->own ? "Sending own" : "Forwarding"), 324 batadv_ogm_packet->orig, 325 ntohl(batadv_ogm_packet->seqno), 326 batadv_ogm_packet->header.ttl, 327 forw_packet->if_incoming->net_dev->name, 328 forw_packet->if_incoming->net_dev->dev_addr); 329 330 /* skb is only used once and than forw_packet is free'd */ 331 batadv_send_skb_packet(forw_packet->skb, 332 forw_packet->if_incoming, 333 batadv_broadcast_addr); 334 forw_packet->skb = NULL; 335 336 goto out; 337 } 338 339 /* broadcast on every interface */ 340 rcu_read_lock(); 341 list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { 342 if (hard_iface->soft_iface != soft_iface) 343 continue; 344 345 batadv_iv_ogm_send_to_if(forw_packet, hard_iface); 346 } 347 rcu_read_unlock(); 348 349 out: 350 if (primary_if) 351 batadv_hardif_free_ref(primary_if); 352 } 353 354 /* return true if new_packet can be aggregated with forw_packet */ 355 static bool 356 batadv_iv_ogm_can_aggregate(const struct batadv_ogm_packet *new_bat_ogm_packet, 357 struct batadv_priv *bat_priv, 358 int packet_len, unsigned long send_time, 359 bool directlink, 360 const struct batadv_hard_iface *if_incoming, 361 const struct batadv_forw_packet *forw_packet) 362 { 363 struct batadv_ogm_packet *batadv_ogm_packet; 364 int aggregated_bytes = forw_packet->packet_len + packet_len; 365 struct batadv_hard_iface *primary_if = NULL; 366 bool res = false; 367 unsigned long aggregation_end_time; 368 369 batadv_ogm_packet = (struct batadv_ogm_packet *)forw_packet->skb->data; 370 aggregation_end_time = send_time; 371 aggregation_end_time += msecs_to_jiffies(BATADV_MAX_AGGREGATION_MS); 372 373 /* we can aggregate the current packet to this aggregated packet 374 * if: 375 * 376 * - the send time is within our MAX_AGGREGATION_MS time 377 * - the resulting packet wont be bigger than 378 * MAX_AGGREGATION_BYTES 379 */ 380 if (time_before(send_time, forw_packet->send_time) && 381 time_after_eq(aggregation_end_time, forw_packet->send_time) && 382 (aggregated_bytes <= BATADV_MAX_AGGREGATION_BYTES)) { 383 /* check aggregation compatibility 384 * -> direct link packets are broadcasted on 385 * their interface only 386 * -> aggregate packet if the current packet is 387 * a "global" packet as well as the base 388 * packet 389 */ 390 primary_if = batadv_primary_if_get_selected(bat_priv); 391 if (!primary_if) 392 goto out; 393 394 /* packets without direct link flag and high TTL 395 * are flooded through the net 396 */ 397 if ((!directlink) && 398 (!(batadv_ogm_packet->flags & BATADV_DIRECTLINK)) && 399 (batadv_ogm_packet->header.ttl != 1) && 400 401 /* own packets originating non-primary 402 * interfaces leave only that interface 403 */ 404 ((!forw_packet->own) || 405 (forw_packet->if_incoming == primary_if))) { 406 res = true; 407 goto out; 408 } 409 410 /* if the incoming packet is sent via this one 411 * interface only - we still can aggregate 412 */ 413 if ((directlink) && 414 (new_bat_ogm_packet->header.ttl == 1) && 415 (forw_packet->if_incoming == if_incoming) && 416 417 /* packets from direct neighbors or 418 * own secondary interface packets 419 * (= secondary interface packets in general) 420 */ 421 (batadv_ogm_packet->flags & BATADV_DIRECTLINK || 422 (forw_packet->own && 423 forw_packet->if_incoming != primary_if))) { 424 res = true; 425 goto out; 426 } 427 } 428 429 out: 430 if (primary_if) 431 batadv_hardif_free_ref(primary_if); 432 return res; 433 } 434 435 /* create a new aggregated packet and add this packet to it */ 436 static void batadv_iv_ogm_aggregate_new(const unsigned char *packet_buff, 437 int packet_len, unsigned long send_time, 438 bool direct_link, 439 struct batadv_hard_iface *if_incoming, 440 int own_packet) 441 { 442 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); 443 struct batadv_forw_packet *forw_packet_aggr; 444 unsigned char *skb_buff; 445 unsigned int skb_size; 446 447 if (!atomic_inc_not_zero(&if_incoming->refcount)) 448 return; 449 450 /* own packet should always be scheduled */ 451 if (!own_packet) { 452 if (!batadv_atomic_dec_not_zero(&bat_priv->batman_queue_left)) { 453 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 454 "batman packet queue full\n"); 455 goto out; 456 } 457 } 458 459 forw_packet_aggr = kmalloc(sizeof(*forw_packet_aggr), GFP_ATOMIC); 460 if (!forw_packet_aggr) { 461 if (!own_packet) 462 atomic_inc(&bat_priv->batman_queue_left); 463 goto out; 464 } 465 466 if ((atomic_read(&bat_priv->aggregated_ogms)) && 467 (packet_len < BATADV_MAX_AGGREGATION_BYTES)) 468 skb_size = BATADV_MAX_AGGREGATION_BYTES; 469 else 470 skb_size = packet_len; 471 472 skb_size += ETH_HLEN; 473 474 forw_packet_aggr->skb = netdev_alloc_skb_ip_align(NULL, skb_size); 475 if (!forw_packet_aggr->skb) { 476 if (!own_packet) 477 atomic_inc(&bat_priv->batman_queue_left); 478 kfree(forw_packet_aggr); 479 goto out; 480 } 481 skb_reserve(forw_packet_aggr->skb, ETH_HLEN); 482 483 skb_buff = skb_put(forw_packet_aggr->skb, packet_len); 484 forw_packet_aggr->packet_len = packet_len; 485 memcpy(skb_buff, packet_buff, packet_len); 486 487 forw_packet_aggr->own = own_packet; 488 forw_packet_aggr->if_incoming = if_incoming; 489 forw_packet_aggr->num_packets = 0; 490 forw_packet_aggr->direct_link_flags = BATADV_NO_FLAGS; 491 forw_packet_aggr->send_time = send_time; 492 493 /* save packet direct link flag status */ 494 if (direct_link) 495 forw_packet_aggr->direct_link_flags |= 1; 496 497 /* add new packet to packet list */ 498 spin_lock_bh(&bat_priv->forw_bat_list_lock); 499 hlist_add_head(&forw_packet_aggr->list, &bat_priv->forw_bat_list); 500 spin_unlock_bh(&bat_priv->forw_bat_list_lock); 501 502 /* start timer for this packet */ 503 INIT_DELAYED_WORK(&forw_packet_aggr->delayed_work, 504 batadv_send_outstanding_bat_ogm_packet); 505 queue_delayed_work(batadv_event_workqueue, 506 &forw_packet_aggr->delayed_work, 507 send_time - jiffies); 508 509 return; 510 out: 511 batadv_hardif_free_ref(if_incoming); 512 } 513 514 /* aggregate a new packet into the existing ogm packet */ 515 static void batadv_iv_ogm_aggregate(struct batadv_forw_packet *forw_packet_aggr, 516 const unsigned char *packet_buff, 517 int packet_len, bool direct_link) 518 { 519 unsigned char *skb_buff; 520 unsigned long new_direct_link_flag; 521 522 skb_buff = skb_put(forw_packet_aggr->skb, packet_len); 523 memcpy(skb_buff, packet_buff, packet_len); 524 forw_packet_aggr->packet_len += packet_len; 525 forw_packet_aggr->num_packets++; 526 527 /* save packet direct link flag status */ 528 if (direct_link) { 529 new_direct_link_flag = BIT(forw_packet_aggr->num_packets); 530 forw_packet_aggr->direct_link_flags |= new_direct_link_flag; 531 } 532 } 533 534 static void batadv_iv_ogm_queue_add(struct batadv_priv *bat_priv, 535 unsigned char *packet_buff, 536 int packet_len, 537 struct batadv_hard_iface *if_incoming, 538 int own_packet, unsigned long send_time) 539 { 540 /* _aggr -> pointer to the packet we want to aggregate with 541 * _pos -> pointer to the position in the queue 542 */ 543 struct batadv_forw_packet *forw_packet_aggr = NULL; 544 struct batadv_forw_packet *forw_packet_pos = NULL; 545 struct batadv_ogm_packet *batadv_ogm_packet; 546 bool direct_link; 547 unsigned long max_aggregation_jiffies; 548 549 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_buff; 550 direct_link = batadv_ogm_packet->flags & BATADV_DIRECTLINK ? 1 : 0; 551 max_aggregation_jiffies = msecs_to_jiffies(BATADV_MAX_AGGREGATION_MS); 552 553 /* find position for the packet in the forward queue */ 554 spin_lock_bh(&bat_priv->forw_bat_list_lock); 555 /* own packets are not to be aggregated */ 556 if ((atomic_read(&bat_priv->aggregated_ogms)) && (!own_packet)) { 557 hlist_for_each_entry(forw_packet_pos, 558 &bat_priv->forw_bat_list, list) { 559 if (batadv_iv_ogm_can_aggregate(batadv_ogm_packet, 560 bat_priv, packet_len, 561 send_time, direct_link, 562 if_incoming, 563 forw_packet_pos)) { 564 forw_packet_aggr = forw_packet_pos; 565 break; 566 } 567 } 568 } 569 570 /* nothing to aggregate with - either aggregation disabled or no 571 * suitable aggregation packet found 572 */ 573 if (!forw_packet_aggr) { 574 /* the following section can run without the lock */ 575 spin_unlock_bh(&bat_priv->forw_bat_list_lock); 576 577 /* if we could not aggregate this packet with one of the others 578 * we hold it back for a while, so that it might be aggregated 579 * later on 580 */ 581 if (!own_packet && atomic_read(&bat_priv->aggregated_ogms)) 582 send_time += max_aggregation_jiffies; 583 584 batadv_iv_ogm_aggregate_new(packet_buff, packet_len, 585 send_time, direct_link, 586 if_incoming, own_packet); 587 } else { 588 batadv_iv_ogm_aggregate(forw_packet_aggr, packet_buff, 589 packet_len, direct_link); 590 spin_unlock_bh(&bat_priv->forw_bat_list_lock); 591 } 592 } 593 594 static void batadv_iv_ogm_forward(struct batadv_orig_node *orig_node, 595 const struct ethhdr *ethhdr, 596 struct batadv_ogm_packet *batadv_ogm_packet, 597 bool is_single_hop_neigh, 598 bool is_from_best_next_hop, 599 struct batadv_hard_iface *if_incoming) 600 { 601 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); 602 uint8_t tt_num_changes; 603 604 if (batadv_ogm_packet->header.ttl <= 1) { 605 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, "ttl exceeded\n"); 606 return; 607 } 608 609 if (!is_from_best_next_hop) { 610 /* Mark the forwarded packet when it is not coming from our 611 * best next hop. We still need to forward the packet for our 612 * neighbor link quality detection to work in case the packet 613 * originated from a single hop neighbor. Otherwise we can 614 * simply drop the ogm. 615 */ 616 if (is_single_hop_neigh) 617 batadv_ogm_packet->flags |= BATADV_NOT_BEST_NEXT_HOP; 618 else 619 return; 620 } 621 622 tt_num_changes = batadv_ogm_packet->tt_num_changes; 623 624 batadv_ogm_packet->header.ttl--; 625 memcpy(batadv_ogm_packet->prev_sender, ethhdr->h_source, ETH_ALEN); 626 627 /* apply hop penalty */ 628 batadv_ogm_packet->tq = batadv_hop_penalty(batadv_ogm_packet->tq, 629 bat_priv); 630 631 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 632 "Forwarding packet: tq: %i, ttl: %i\n", 633 batadv_ogm_packet->tq, batadv_ogm_packet->header.ttl); 634 635 /* switch of primaries first hop flag when forwarding */ 636 batadv_ogm_packet->flags &= ~BATADV_PRIMARIES_FIRST_HOP; 637 if (is_single_hop_neigh) 638 batadv_ogm_packet->flags |= BATADV_DIRECTLINK; 639 else 640 batadv_ogm_packet->flags &= ~BATADV_DIRECTLINK; 641 642 batadv_iv_ogm_queue_add(bat_priv, (unsigned char *)batadv_ogm_packet, 643 BATADV_OGM_HLEN + batadv_tt_len(tt_num_changes), 644 if_incoming, 0, batadv_iv_ogm_fwd_send_time()); 645 } 646 647 /** 648 * batadv_iv_ogm_slide_own_bcast_window - bitshift own OGM broadcast windows for 649 * the given interface 650 * @hard_iface: the interface for which the windows have to be shifted 651 */ 652 static void 653 batadv_iv_ogm_slide_own_bcast_window(struct batadv_hard_iface *hard_iface) 654 { 655 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); 656 struct batadv_hashtable *hash = bat_priv->orig_hash; 657 struct hlist_head *head; 658 struct batadv_orig_node *orig_node; 659 unsigned long *word; 660 uint32_t i; 661 size_t word_index; 662 uint8_t *w; 663 664 for (i = 0; i < hash->size; i++) { 665 head = &hash->table[i]; 666 667 rcu_read_lock(); 668 hlist_for_each_entry_rcu(orig_node, head, hash_entry) { 669 spin_lock_bh(&orig_node->ogm_cnt_lock); 670 word_index = hard_iface->if_num * BATADV_NUM_WORDS; 671 word = &(orig_node->bcast_own[word_index]); 672 673 batadv_bit_get_packet(bat_priv, word, 1, 0); 674 w = &orig_node->bcast_own_sum[hard_iface->if_num]; 675 *w = bitmap_weight(word, BATADV_TQ_LOCAL_WINDOW_SIZE); 676 spin_unlock_bh(&orig_node->ogm_cnt_lock); 677 } 678 rcu_read_unlock(); 679 } 680 } 681 682 static void batadv_iv_ogm_schedule(struct batadv_hard_iface *hard_iface) 683 { 684 struct batadv_priv *bat_priv = netdev_priv(hard_iface->soft_iface); 685 unsigned char **ogm_buff = &hard_iface->bat_iv.ogm_buff; 686 struct batadv_ogm_packet *batadv_ogm_packet; 687 struct batadv_hard_iface *primary_if; 688 int *ogm_buff_len = &hard_iface->bat_iv.ogm_buff_len; 689 int vis_server, tt_num_changes = 0; 690 uint32_t seqno; 691 uint8_t bandwidth; 692 693 vis_server = atomic_read(&bat_priv->vis_mode); 694 primary_if = batadv_primary_if_get_selected(bat_priv); 695 696 if (hard_iface == primary_if) 697 tt_num_changes = batadv_tt_append_diff(bat_priv, ogm_buff, 698 ogm_buff_len, 699 BATADV_OGM_HLEN); 700 701 batadv_ogm_packet = (struct batadv_ogm_packet *)(*ogm_buff); 702 703 /* change sequence number to network order */ 704 seqno = (uint32_t)atomic_read(&hard_iface->bat_iv.ogm_seqno); 705 batadv_ogm_packet->seqno = htonl(seqno); 706 atomic_inc(&hard_iface->bat_iv.ogm_seqno); 707 708 batadv_ogm_packet->ttvn = atomic_read(&bat_priv->tt.vn); 709 batadv_ogm_packet->tt_crc = htons(bat_priv->tt.local_crc); 710 if (tt_num_changes >= 0) 711 batadv_ogm_packet->tt_num_changes = tt_num_changes; 712 713 if (vis_server == BATADV_VIS_TYPE_SERVER_SYNC) 714 batadv_ogm_packet->flags |= BATADV_VIS_SERVER; 715 else 716 batadv_ogm_packet->flags &= ~BATADV_VIS_SERVER; 717 718 if (hard_iface == primary_if && 719 atomic_read(&bat_priv->gw_mode) == BATADV_GW_MODE_SERVER) { 720 bandwidth = (uint8_t)atomic_read(&bat_priv->gw_bandwidth); 721 batadv_ogm_packet->gw_flags = bandwidth; 722 } else { 723 batadv_ogm_packet->gw_flags = BATADV_NO_FLAGS; 724 } 725 726 batadv_iv_ogm_slide_own_bcast_window(hard_iface); 727 batadv_iv_ogm_queue_add(bat_priv, hard_iface->bat_iv.ogm_buff, 728 hard_iface->bat_iv.ogm_buff_len, hard_iface, 1, 729 batadv_iv_ogm_emit_send_time(bat_priv)); 730 731 if (primary_if) 732 batadv_hardif_free_ref(primary_if); 733 } 734 735 static void 736 batadv_iv_ogm_orig_update(struct batadv_priv *bat_priv, 737 struct batadv_orig_node *orig_node, 738 const struct ethhdr *ethhdr, 739 const struct batadv_ogm_packet *batadv_ogm_packet, 740 struct batadv_hard_iface *if_incoming, 741 const unsigned char *tt_buff, 742 enum batadv_dup_status dup_status) 743 { 744 struct batadv_neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL; 745 struct batadv_neigh_node *router = NULL; 746 struct batadv_orig_node *orig_node_tmp; 747 int if_num; 748 uint8_t sum_orig, sum_neigh; 749 uint8_t *neigh_addr; 750 uint8_t tq_avg; 751 752 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 753 "update_originator(): Searching and updating originator entry of received packet\n"); 754 755 rcu_read_lock(); 756 hlist_for_each_entry_rcu(tmp_neigh_node, 757 &orig_node->neigh_list, list) { 758 neigh_addr = tmp_neigh_node->addr; 759 if (batadv_compare_eth(neigh_addr, ethhdr->h_source) && 760 tmp_neigh_node->if_incoming == if_incoming && 761 atomic_inc_not_zero(&tmp_neigh_node->refcount)) { 762 if (WARN(neigh_node, "too many matching neigh_nodes")) 763 batadv_neigh_node_free_ref(neigh_node); 764 neigh_node = tmp_neigh_node; 765 continue; 766 } 767 768 if (dup_status != BATADV_NO_DUP) 769 continue; 770 771 spin_lock_bh(&tmp_neigh_node->lq_update_lock); 772 batadv_ring_buffer_set(tmp_neigh_node->tq_recv, 773 &tmp_neigh_node->tq_index, 0); 774 tq_avg = batadv_ring_buffer_avg(tmp_neigh_node->tq_recv); 775 tmp_neigh_node->tq_avg = tq_avg; 776 spin_unlock_bh(&tmp_neigh_node->lq_update_lock); 777 } 778 779 if (!neigh_node) { 780 struct batadv_orig_node *orig_tmp; 781 782 orig_tmp = batadv_get_orig_node(bat_priv, ethhdr->h_source); 783 if (!orig_tmp) 784 goto unlock; 785 786 neigh_node = batadv_iv_ogm_neigh_new(if_incoming, 787 ethhdr->h_source, 788 orig_node, orig_tmp); 789 790 batadv_orig_node_free_ref(orig_tmp); 791 if (!neigh_node) 792 goto unlock; 793 } else 794 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 795 "Updating existing last-hop neighbor of originator\n"); 796 797 rcu_read_unlock(); 798 799 orig_node->flags = batadv_ogm_packet->flags; 800 neigh_node->last_seen = jiffies; 801 802 spin_lock_bh(&neigh_node->lq_update_lock); 803 batadv_ring_buffer_set(neigh_node->tq_recv, 804 &neigh_node->tq_index, 805 batadv_ogm_packet->tq); 806 neigh_node->tq_avg = batadv_ring_buffer_avg(neigh_node->tq_recv); 807 spin_unlock_bh(&neigh_node->lq_update_lock); 808 809 if (dup_status == BATADV_NO_DUP) { 810 orig_node->last_ttl = batadv_ogm_packet->header.ttl; 811 neigh_node->last_ttl = batadv_ogm_packet->header.ttl; 812 } 813 814 batadv_bonding_candidate_add(orig_node, neigh_node); 815 816 /* if this neighbor already is our next hop there is nothing 817 * to change 818 */ 819 router = batadv_orig_node_get_router(orig_node); 820 if (router == neigh_node) 821 goto update_tt; 822 823 /* if this neighbor does not offer a better TQ we won't consider it */ 824 if (router && (router->tq_avg > neigh_node->tq_avg)) 825 goto update_tt; 826 827 /* if the TQ is the same and the link not more symmetric we 828 * won't consider it either 829 */ 830 if (router && (neigh_node->tq_avg == router->tq_avg)) { 831 orig_node_tmp = router->orig_node; 832 spin_lock_bh(&orig_node_tmp->ogm_cnt_lock); 833 if_num = router->if_incoming->if_num; 834 sum_orig = orig_node_tmp->bcast_own_sum[if_num]; 835 spin_unlock_bh(&orig_node_tmp->ogm_cnt_lock); 836 837 orig_node_tmp = neigh_node->orig_node; 838 spin_lock_bh(&orig_node_tmp->ogm_cnt_lock); 839 if_num = neigh_node->if_incoming->if_num; 840 sum_neigh = orig_node_tmp->bcast_own_sum[if_num]; 841 spin_unlock_bh(&orig_node_tmp->ogm_cnt_lock); 842 843 if (sum_orig >= sum_neigh) 844 goto update_tt; 845 } 846 847 batadv_update_route(bat_priv, orig_node, neigh_node); 848 849 update_tt: 850 /* I have to check for transtable changes only if the OGM has been 851 * sent through a primary interface 852 */ 853 if (((batadv_ogm_packet->orig != ethhdr->h_source) && 854 (batadv_ogm_packet->header.ttl > 2)) || 855 (batadv_ogm_packet->flags & BATADV_PRIMARIES_FIRST_HOP)) 856 batadv_tt_update_orig(bat_priv, orig_node, tt_buff, 857 batadv_ogm_packet->tt_num_changes, 858 batadv_ogm_packet->ttvn, 859 ntohs(batadv_ogm_packet->tt_crc)); 860 861 if (orig_node->gw_flags != batadv_ogm_packet->gw_flags) 862 batadv_gw_node_update(bat_priv, orig_node, 863 batadv_ogm_packet->gw_flags); 864 865 orig_node->gw_flags = batadv_ogm_packet->gw_flags; 866 867 /* restart gateway selection if fast or late switching was enabled */ 868 if ((orig_node->gw_flags) && 869 (atomic_read(&bat_priv->gw_mode) == BATADV_GW_MODE_CLIENT) && 870 (atomic_read(&bat_priv->gw_sel_class) > 2)) 871 batadv_gw_check_election(bat_priv, orig_node); 872 873 goto out; 874 875 unlock: 876 rcu_read_unlock(); 877 out: 878 if (neigh_node) 879 batadv_neigh_node_free_ref(neigh_node); 880 if (router) 881 batadv_neigh_node_free_ref(router); 882 } 883 884 static int batadv_iv_ogm_calc_tq(struct batadv_orig_node *orig_node, 885 struct batadv_orig_node *orig_neigh_node, 886 struct batadv_ogm_packet *batadv_ogm_packet, 887 struct batadv_hard_iface *if_incoming) 888 { 889 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); 890 struct batadv_neigh_node *neigh_node = NULL, *tmp_neigh_node; 891 uint8_t total_count; 892 uint8_t orig_eq_count, neigh_rq_count, neigh_rq_inv, tq_own; 893 unsigned int neigh_rq_inv_cube, neigh_rq_max_cube; 894 int tq_asym_penalty, inv_asym_penalty, ret = 0; 895 unsigned int combined_tq; 896 897 /* find corresponding one hop neighbor */ 898 rcu_read_lock(); 899 hlist_for_each_entry_rcu(tmp_neigh_node, 900 &orig_neigh_node->neigh_list, list) { 901 if (!batadv_compare_eth(tmp_neigh_node->addr, 902 orig_neigh_node->orig)) 903 continue; 904 905 if (tmp_neigh_node->if_incoming != if_incoming) 906 continue; 907 908 if (!atomic_inc_not_zero(&tmp_neigh_node->refcount)) 909 continue; 910 911 neigh_node = tmp_neigh_node; 912 break; 913 } 914 rcu_read_unlock(); 915 916 if (!neigh_node) 917 neigh_node = batadv_iv_ogm_neigh_new(if_incoming, 918 orig_neigh_node->orig, 919 orig_neigh_node, 920 orig_neigh_node); 921 922 if (!neigh_node) 923 goto out; 924 925 /* if orig_node is direct neighbor update neigh_node last_seen */ 926 if (orig_node == orig_neigh_node) 927 neigh_node->last_seen = jiffies; 928 929 orig_node->last_seen = jiffies; 930 931 /* find packet count of corresponding one hop neighbor */ 932 spin_lock_bh(&orig_node->ogm_cnt_lock); 933 orig_eq_count = orig_neigh_node->bcast_own_sum[if_incoming->if_num]; 934 neigh_rq_count = neigh_node->real_packet_count; 935 spin_unlock_bh(&orig_node->ogm_cnt_lock); 936 937 /* pay attention to not get a value bigger than 100 % */ 938 if (orig_eq_count > neigh_rq_count) 939 total_count = neigh_rq_count; 940 else 941 total_count = orig_eq_count; 942 943 /* if we have too few packets (too less data) we set tq_own to zero 944 * if we receive too few packets it is not considered bidirectional 945 */ 946 if (total_count < BATADV_TQ_LOCAL_BIDRECT_SEND_MINIMUM || 947 neigh_rq_count < BATADV_TQ_LOCAL_BIDRECT_RECV_MINIMUM) 948 tq_own = 0; 949 else 950 /* neigh_node->real_packet_count is never zero as we 951 * only purge old information when getting new 952 * information 953 */ 954 tq_own = (BATADV_TQ_MAX_VALUE * total_count) / neigh_rq_count; 955 956 /* 1 - ((1-x) ** 3), normalized to TQ_MAX_VALUE this does 957 * affect the nearly-symmetric links only a little, but 958 * punishes asymmetric links more. This will give a value 959 * between 0 and TQ_MAX_VALUE 960 */ 961 neigh_rq_inv = BATADV_TQ_LOCAL_WINDOW_SIZE - neigh_rq_count; 962 neigh_rq_inv_cube = neigh_rq_inv * neigh_rq_inv * neigh_rq_inv; 963 neigh_rq_max_cube = BATADV_TQ_LOCAL_WINDOW_SIZE * 964 BATADV_TQ_LOCAL_WINDOW_SIZE * 965 BATADV_TQ_LOCAL_WINDOW_SIZE; 966 inv_asym_penalty = BATADV_TQ_MAX_VALUE * neigh_rq_inv_cube; 967 inv_asym_penalty /= neigh_rq_max_cube; 968 tq_asym_penalty = BATADV_TQ_MAX_VALUE - inv_asym_penalty; 969 970 combined_tq = batadv_ogm_packet->tq * tq_own * tq_asym_penalty; 971 combined_tq /= BATADV_TQ_MAX_VALUE * BATADV_TQ_MAX_VALUE; 972 batadv_ogm_packet->tq = combined_tq; 973 974 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 975 "bidirectional: orig = %-15pM neigh = %-15pM => own_bcast = %2i, real recv = %2i, local tq: %3i, asym_penalty: %3i, total tq: %3i\n", 976 orig_node->orig, orig_neigh_node->orig, total_count, 977 neigh_rq_count, tq_own, 978 tq_asym_penalty, batadv_ogm_packet->tq); 979 980 /* if link has the minimum required transmission quality 981 * consider it bidirectional 982 */ 983 if (batadv_ogm_packet->tq >= BATADV_TQ_TOTAL_BIDRECT_LIMIT) 984 ret = 1; 985 986 out: 987 if (neigh_node) 988 batadv_neigh_node_free_ref(neigh_node); 989 return ret; 990 } 991 992 /** 993 * batadv_iv_ogm_update_seqnos - process a batman packet for all interfaces, 994 * adjust the sequence number and find out whether it is a duplicate 995 * @ethhdr: ethernet header of the packet 996 * @batadv_ogm_packet: OGM packet to be considered 997 * @if_incoming: interface on which the OGM packet was received 998 * 999 * Returns duplicate status as enum batadv_dup_status 1000 */ 1001 static enum batadv_dup_status 1002 batadv_iv_ogm_update_seqnos(const struct ethhdr *ethhdr, 1003 const struct batadv_ogm_packet *batadv_ogm_packet, 1004 const struct batadv_hard_iface *if_incoming) 1005 { 1006 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); 1007 struct batadv_orig_node *orig_node; 1008 struct batadv_neigh_node *tmp_neigh_node; 1009 int is_dup; 1010 int32_t seq_diff; 1011 int need_update = 0; 1012 int set_mark; 1013 enum batadv_dup_status ret = BATADV_NO_DUP; 1014 uint32_t seqno = ntohl(batadv_ogm_packet->seqno); 1015 uint8_t *neigh_addr; 1016 uint8_t packet_count; 1017 1018 orig_node = batadv_get_orig_node(bat_priv, batadv_ogm_packet->orig); 1019 if (!orig_node) 1020 return BATADV_NO_DUP; 1021 1022 spin_lock_bh(&orig_node->ogm_cnt_lock); 1023 seq_diff = seqno - orig_node->last_real_seqno; 1024 1025 /* signalize caller that the packet is to be dropped. */ 1026 if (!hlist_empty(&orig_node->neigh_list) && 1027 batadv_window_protected(bat_priv, seq_diff, 1028 &orig_node->batman_seqno_reset)) { 1029 ret = BATADV_PROTECTED; 1030 goto out; 1031 } 1032 1033 rcu_read_lock(); 1034 hlist_for_each_entry_rcu(tmp_neigh_node, 1035 &orig_node->neigh_list, list) { 1036 neigh_addr = tmp_neigh_node->addr; 1037 is_dup = batadv_test_bit(tmp_neigh_node->real_bits, 1038 orig_node->last_real_seqno, 1039 seqno); 1040 1041 if (batadv_compare_eth(neigh_addr, ethhdr->h_source) && 1042 tmp_neigh_node->if_incoming == if_incoming) { 1043 set_mark = 1; 1044 if (is_dup) 1045 ret = BATADV_NEIGH_DUP; 1046 } else { 1047 set_mark = 0; 1048 if (is_dup && (ret != BATADV_NEIGH_DUP)) 1049 ret = BATADV_ORIG_DUP; 1050 } 1051 1052 /* if the window moved, set the update flag. */ 1053 need_update |= batadv_bit_get_packet(bat_priv, 1054 tmp_neigh_node->real_bits, 1055 seq_diff, set_mark); 1056 1057 packet_count = bitmap_weight(tmp_neigh_node->real_bits, 1058 BATADV_TQ_LOCAL_WINDOW_SIZE); 1059 tmp_neigh_node->real_packet_count = packet_count; 1060 } 1061 rcu_read_unlock(); 1062 1063 if (need_update) { 1064 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1065 "updating last_seqno: old %u, new %u\n", 1066 orig_node->last_real_seqno, seqno); 1067 orig_node->last_real_seqno = seqno; 1068 } 1069 1070 out: 1071 spin_unlock_bh(&orig_node->ogm_cnt_lock); 1072 batadv_orig_node_free_ref(orig_node); 1073 return ret; 1074 } 1075 1076 static void batadv_iv_ogm_process(const struct ethhdr *ethhdr, 1077 struct batadv_ogm_packet *batadv_ogm_packet, 1078 const unsigned char *tt_buff, 1079 struct batadv_hard_iface *if_incoming) 1080 { 1081 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); 1082 struct batadv_hard_iface *hard_iface; 1083 struct batadv_orig_node *orig_neigh_node, *orig_node; 1084 struct batadv_neigh_node *router = NULL, *router_router = NULL; 1085 struct batadv_neigh_node *orig_neigh_router = NULL; 1086 int has_directlink_flag; 1087 int is_my_addr = 0, is_my_orig = 0, is_my_oldorig = 0; 1088 int is_bidirect; 1089 bool is_single_hop_neigh = false; 1090 bool is_from_best_next_hop = false; 1091 int sameseq, similar_ttl; 1092 enum batadv_dup_status dup_status; 1093 uint32_t if_incoming_seqno; 1094 uint8_t *prev_sender; 1095 1096 /* Silently drop when the batman packet is actually not a 1097 * correct packet. 1098 * 1099 * This might happen if a packet is padded (e.g. Ethernet has a 1100 * minimum frame length of 64 byte) and the aggregation interprets 1101 * it as an additional length. 1102 * 1103 * TODO: A more sane solution would be to have a bit in the 1104 * batadv_ogm_packet to detect whether the packet is the last 1105 * packet in an aggregation. Here we expect that the padding 1106 * is always zero (or not 0x01) 1107 */ 1108 if (batadv_ogm_packet->header.packet_type != BATADV_IV_OGM) 1109 return; 1110 1111 /* could be changed by schedule_own_packet() */ 1112 if_incoming_seqno = atomic_read(&if_incoming->bat_iv.ogm_seqno); 1113 1114 if (batadv_ogm_packet->flags & BATADV_DIRECTLINK) 1115 has_directlink_flag = 1; 1116 else 1117 has_directlink_flag = 0; 1118 1119 if (batadv_compare_eth(ethhdr->h_source, batadv_ogm_packet->orig)) 1120 is_single_hop_neigh = true; 1121 1122 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1123 "Received BATMAN packet via NB: %pM, IF: %s [%pM] (from OG: %pM, via prev OG: %pM, seqno %u, ttvn %u, crc %#.4x, changes %u, tq %d, TTL %d, V %d, IDF %d)\n", 1124 ethhdr->h_source, if_incoming->net_dev->name, 1125 if_incoming->net_dev->dev_addr, batadv_ogm_packet->orig, 1126 batadv_ogm_packet->prev_sender, 1127 ntohl(batadv_ogm_packet->seqno), batadv_ogm_packet->ttvn, 1128 ntohs(batadv_ogm_packet->tt_crc), 1129 batadv_ogm_packet->tt_num_changes, batadv_ogm_packet->tq, 1130 batadv_ogm_packet->header.ttl, 1131 batadv_ogm_packet->header.version, has_directlink_flag); 1132 1133 rcu_read_lock(); 1134 list_for_each_entry_rcu(hard_iface, &batadv_hardif_list, list) { 1135 if (hard_iface->if_status != BATADV_IF_ACTIVE) 1136 continue; 1137 1138 if (hard_iface->soft_iface != if_incoming->soft_iface) 1139 continue; 1140 1141 if (batadv_compare_eth(ethhdr->h_source, 1142 hard_iface->net_dev->dev_addr)) 1143 is_my_addr = 1; 1144 1145 if (batadv_compare_eth(batadv_ogm_packet->orig, 1146 hard_iface->net_dev->dev_addr)) 1147 is_my_orig = 1; 1148 1149 if (batadv_compare_eth(batadv_ogm_packet->prev_sender, 1150 hard_iface->net_dev->dev_addr)) 1151 is_my_oldorig = 1; 1152 } 1153 rcu_read_unlock(); 1154 1155 if (is_my_addr) { 1156 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1157 "Drop packet: received my own broadcast (sender: %pM)\n", 1158 ethhdr->h_source); 1159 return; 1160 } 1161 1162 if (is_my_orig) { 1163 unsigned long *word; 1164 int offset; 1165 int32_t bit_pos; 1166 int16_t if_num; 1167 uint8_t *weight; 1168 1169 orig_neigh_node = batadv_get_orig_node(bat_priv, 1170 ethhdr->h_source); 1171 if (!orig_neigh_node) 1172 return; 1173 1174 /* neighbor has to indicate direct link and it has to 1175 * come via the corresponding interface 1176 * save packet seqno for bidirectional check 1177 */ 1178 if (has_directlink_flag && 1179 batadv_compare_eth(if_incoming->net_dev->dev_addr, 1180 batadv_ogm_packet->orig)) { 1181 if_num = if_incoming->if_num; 1182 offset = if_num * BATADV_NUM_WORDS; 1183 1184 spin_lock_bh(&orig_neigh_node->ogm_cnt_lock); 1185 word = &(orig_neigh_node->bcast_own[offset]); 1186 bit_pos = if_incoming_seqno - 2; 1187 bit_pos -= ntohl(batadv_ogm_packet->seqno); 1188 batadv_set_bit(word, bit_pos); 1189 weight = &orig_neigh_node->bcast_own_sum[if_num]; 1190 *weight = bitmap_weight(word, 1191 BATADV_TQ_LOCAL_WINDOW_SIZE); 1192 spin_unlock_bh(&orig_neigh_node->ogm_cnt_lock); 1193 } 1194 1195 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1196 "Drop packet: originator packet from myself (via neighbor)\n"); 1197 batadv_orig_node_free_ref(orig_neigh_node); 1198 return; 1199 } 1200 1201 if (is_my_oldorig) { 1202 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1203 "Drop packet: ignoring all rebroadcast echos (sender: %pM)\n", 1204 ethhdr->h_source); 1205 return; 1206 } 1207 1208 if (batadv_ogm_packet->flags & BATADV_NOT_BEST_NEXT_HOP) { 1209 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1210 "Drop packet: ignoring all packets not forwarded from the best next hop (sender: %pM)\n", 1211 ethhdr->h_source); 1212 return; 1213 } 1214 1215 orig_node = batadv_get_orig_node(bat_priv, batadv_ogm_packet->orig); 1216 if (!orig_node) 1217 return; 1218 1219 dup_status = batadv_iv_ogm_update_seqnos(ethhdr, batadv_ogm_packet, 1220 if_incoming); 1221 1222 if (dup_status == BATADV_PROTECTED) { 1223 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1224 "Drop packet: packet within seqno protection time (sender: %pM)\n", 1225 ethhdr->h_source); 1226 goto out; 1227 } 1228 1229 if (batadv_ogm_packet->tq == 0) { 1230 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1231 "Drop packet: originator packet with tq equal 0\n"); 1232 goto out; 1233 } 1234 1235 router = batadv_orig_node_get_router(orig_node); 1236 if (router) 1237 router_router = batadv_orig_node_get_router(router->orig_node); 1238 1239 if ((router && router->tq_avg != 0) && 1240 (batadv_compare_eth(router->addr, ethhdr->h_source))) 1241 is_from_best_next_hop = true; 1242 1243 prev_sender = batadv_ogm_packet->prev_sender; 1244 /* avoid temporary routing loops */ 1245 if (router && router_router && 1246 (batadv_compare_eth(router->addr, prev_sender)) && 1247 !(batadv_compare_eth(batadv_ogm_packet->orig, prev_sender)) && 1248 (batadv_compare_eth(router->addr, router_router->addr))) { 1249 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1250 "Drop packet: ignoring all rebroadcast packets that may make me loop (sender: %pM)\n", 1251 ethhdr->h_source); 1252 goto out; 1253 } 1254 1255 /* if sender is a direct neighbor the sender mac equals 1256 * originator mac 1257 */ 1258 if (is_single_hop_neigh) 1259 orig_neigh_node = orig_node; 1260 else 1261 orig_neigh_node = batadv_get_orig_node(bat_priv, 1262 ethhdr->h_source); 1263 1264 if (!orig_neigh_node) 1265 goto out; 1266 1267 /* Update nc_nodes of the originator */ 1268 batadv_nc_update_nc_node(bat_priv, orig_node, orig_neigh_node, 1269 batadv_ogm_packet, is_single_hop_neigh); 1270 1271 orig_neigh_router = batadv_orig_node_get_router(orig_neigh_node); 1272 1273 /* drop packet if sender is not a direct neighbor and if we 1274 * don't route towards it 1275 */ 1276 if (!is_single_hop_neigh && (!orig_neigh_router)) { 1277 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1278 "Drop packet: OGM via unknown neighbor!\n"); 1279 goto out_neigh; 1280 } 1281 1282 is_bidirect = batadv_iv_ogm_calc_tq(orig_node, orig_neigh_node, 1283 batadv_ogm_packet, if_incoming); 1284 1285 batadv_bonding_save_primary(orig_node, orig_neigh_node, 1286 batadv_ogm_packet); 1287 1288 /* update ranking if it is not a duplicate or has the same 1289 * seqno and similar ttl as the non-duplicate 1290 */ 1291 sameseq = orig_node->last_real_seqno == ntohl(batadv_ogm_packet->seqno); 1292 similar_ttl = orig_node->last_ttl - 3 <= batadv_ogm_packet->header.ttl; 1293 if (is_bidirect && ((dup_status == BATADV_NO_DUP) || 1294 (sameseq && similar_ttl))) 1295 batadv_iv_ogm_orig_update(bat_priv, orig_node, ethhdr, 1296 batadv_ogm_packet, if_incoming, 1297 tt_buff, dup_status); 1298 1299 /* is single hop (direct) neighbor */ 1300 if (is_single_hop_neigh) { 1301 /* mark direct link on incoming interface */ 1302 batadv_iv_ogm_forward(orig_node, ethhdr, batadv_ogm_packet, 1303 is_single_hop_neigh, 1304 is_from_best_next_hop, if_incoming); 1305 1306 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1307 "Forwarding packet: rebroadcast neighbor packet with direct link flag\n"); 1308 goto out_neigh; 1309 } 1310 1311 /* multihop originator */ 1312 if (!is_bidirect) { 1313 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1314 "Drop packet: not received via bidirectional link\n"); 1315 goto out_neigh; 1316 } 1317 1318 if (dup_status == BATADV_NEIGH_DUP) { 1319 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1320 "Drop packet: duplicate packet received\n"); 1321 goto out_neigh; 1322 } 1323 1324 batadv_dbg(BATADV_DBG_BATMAN, bat_priv, 1325 "Forwarding packet: rebroadcast originator packet\n"); 1326 batadv_iv_ogm_forward(orig_node, ethhdr, batadv_ogm_packet, 1327 is_single_hop_neigh, is_from_best_next_hop, 1328 if_incoming); 1329 1330 out_neigh: 1331 if ((orig_neigh_node) && (!is_single_hop_neigh)) 1332 batadv_orig_node_free_ref(orig_neigh_node); 1333 out: 1334 if (router) 1335 batadv_neigh_node_free_ref(router); 1336 if (router_router) 1337 batadv_neigh_node_free_ref(router_router); 1338 if (orig_neigh_router) 1339 batadv_neigh_node_free_ref(orig_neigh_router); 1340 1341 batadv_orig_node_free_ref(orig_node); 1342 } 1343 1344 static int batadv_iv_ogm_receive(struct sk_buff *skb, 1345 struct batadv_hard_iface *if_incoming) 1346 { 1347 struct batadv_priv *bat_priv = netdev_priv(if_incoming->soft_iface); 1348 struct batadv_ogm_packet *batadv_ogm_packet; 1349 struct ethhdr *ethhdr; 1350 int buff_pos = 0, packet_len; 1351 unsigned char *tt_buff, *packet_buff; 1352 bool ret; 1353 uint8_t *packet_pos; 1354 1355 ret = batadv_check_management_packet(skb, if_incoming, BATADV_OGM_HLEN); 1356 if (!ret) 1357 return NET_RX_DROP; 1358 1359 /* did we receive a B.A.T.M.A.N. IV OGM packet on an interface 1360 * that does not have B.A.T.M.A.N. IV enabled ? 1361 */ 1362 if (bat_priv->bat_algo_ops->bat_ogm_emit != batadv_iv_ogm_emit) 1363 return NET_RX_DROP; 1364 1365 batadv_inc_counter(bat_priv, BATADV_CNT_MGMT_RX); 1366 batadv_add_counter(bat_priv, BATADV_CNT_MGMT_RX_BYTES, 1367 skb->len + ETH_HLEN); 1368 1369 packet_len = skb_headlen(skb); 1370 ethhdr = eth_hdr(skb); 1371 packet_buff = skb->data; 1372 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_buff; 1373 1374 /* unpack the aggregated packets and process them one by one */ 1375 while (batadv_iv_ogm_aggr_packet(buff_pos, packet_len, 1376 batadv_ogm_packet->tt_num_changes)) { 1377 tt_buff = packet_buff + buff_pos + BATADV_OGM_HLEN; 1378 1379 batadv_iv_ogm_process(ethhdr, batadv_ogm_packet, tt_buff, 1380 if_incoming); 1381 1382 buff_pos += BATADV_OGM_HLEN; 1383 buff_pos += batadv_tt_len(batadv_ogm_packet->tt_num_changes); 1384 1385 packet_pos = packet_buff + buff_pos; 1386 batadv_ogm_packet = (struct batadv_ogm_packet *)packet_pos; 1387 } 1388 1389 kfree_skb(skb); 1390 return NET_RX_SUCCESS; 1391 } 1392 1393 static struct batadv_algo_ops batadv_batman_iv __read_mostly = { 1394 .name = "BATMAN_IV", 1395 .bat_iface_enable = batadv_iv_ogm_iface_enable, 1396 .bat_iface_disable = batadv_iv_ogm_iface_disable, 1397 .bat_iface_update_mac = batadv_iv_ogm_iface_update_mac, 1398 .bat_primary_iface_set = batadv_iv_ogm_primary_iface_set, 1399 .bat_ogm_schedule = batadv_iv_ogm_schedule, 1400 .bat_ogm_emit = batadv_iv_ogm_emit, 1401 }; 1402 1403 int __init batadv_iv_init(void) 1404 { 1405 int ret; 1406 1407 /* batman originator packet */ 1408 ret = batadv_recv_handler_register(BATADV_IV_OGM, 1409 batadv_iv_ogm_receive); 1410 if (ret < 0) 1411 goto out; 1412 1413 ret = batadv_algo_register(&batadv_batman_iv); 1414 if (ret < 0) 1415 goto handler_unregister; 1416 1417 goto out; 1418 1419 handler_unregister: 1420 batadv_recv_handler_unregister(BATADV_IV_OGM); 1421 out: 1422 return ret; 1423 } 1424