net/batman-adv/bridge_loop_avoidance.c

   1 /* Copyright (C) 2011-2015 B.A.T.M.A.N. contributors:
   2  *
   3  * 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, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include "main.h"
  19 #include "hash.h"
  20 #include "hard-interface.h"
  21 #include "originator.h"
  22 #include "bridge_loop_avoidance.h"
  23 #include "translation-table.h"
  24 #include "send.h"
  25
  26 #include <linux/etherdevice.h>
  27 #include <linux/crc16.h>
  28 #include <linux/if_arp.h>
  29 #include <net/arp.h>
  30 #include <linux/if_vlan.h>
  31
  32 static const uint8_t batadv_announce_mac[4] = {0x43, 0x05, 0x43, 0x05};
  33
  34 static void batadv_bla_periodic_work(struct work_struct *work);
  35 static void
  36 batadv_bla_send_announce(struct batadv_priv *bat_priv,
  37                          struct batadv_bla_backbone_gw *backbone_gw);
  38
  39 /* return the index of the claim */
  40 static inline uint32_t batadv_choose_claim(const void *data, uint32_t size)
  41 {
  42         struct batadv_bla_claim *claim = (struct batadv_bla_claim *)data;
  43         uint32_t hash = 0;
  44
  45         hash = jhash(&claim->addr, sizeof(claim->addr), hash);
  46         hash = jhash(&claim->vid, sizeof(claim->vid), hash);
  47
  48         return hash % size;
  49 }
  50
  51 /* return the index of the backbone gateway */
  52 static inline uint32_t batadv_choose_backbone_gw(const void *data,
  53                                                  uint32_t size)
  54 {
  55         const struct batadv_bla_claim *claim = (struct batadv_bla_claim *)data;
  56         uint32_t hash = 0;
  57
  58         hash = jhash(&claim->addr, sizeof(claim->addr), hash);
  59         hash = jhash(&claim->vid, sizeof(claim->vid), hash);
  60
  61         return hash % size;
  62 }
  63
  64 /* compares address and vid of two backbone gws */
  65 static int batadv_compare_backbone_gw(const struct hlist_node *node,
  66                                       const void *data2)
  67 {
  68         const void *data1 = container_of(node, struct batadv_bla_backbone_gw,
  69                                          hash_entry);
  70         const struct batadv_bla_backbone_gw *gw1 = data1, *gw2 = data2;
  71
  72         if (!batadv_compare_eth(gw1->orig, gw2->orig))
  73                 return 0;
  74
  75         if (gw1->vid != gw2->vid)
  76                 return 0;
  77
  78         return 1;
  79 }
  80
  81 /* compares address and vid of two claims */
  82 static int batadv_compare_claim(const struct hlist_node *node,
  83                                 const void *data2)
  84 {
  85         const void *data1 = container_of(node, struct batadv_bla_claim,
  86                                          hash_entry);
  87         const struct batadv_bla_claim *cl1 = data1, *cl2 = data2;
  88
  89         if (!batadv_compare_eth(cl1->addr, cl2->addr))
  90                 return 0;
  91
  92         if (cl1->vid != cl2->vid)
  93                 return 0;
  94
  95         return 1;
  96 }
  97
  98 /* free a backbone gw */
  99 static void
 100 batadv_backbone_gw_free_ref(struct batadv_bla_backbone_gw *backbone_gw)
 101 {
 102         if (atomic_dec_and_test(&backbone_gw->refcount))
 103                 kfree_rcu(backbone_gw, rcu);
 104 }
 105
 106 /* finally deinitialize the claim */
 107 static void batadv_claim_free_rcu(struct rcu_head *rcu)
 108 {
 109         struct batadv_bla_claim *claim;
 110
 111         claim = container_of(rcu, struct batadv_bla_claim, rcu);
 112
 113         batadv_backbone_gw_free_ref(claim->backbone_gw);
 114         kfree(claim);
 115 }
 116
 117 /* free a claim, call claim_free_rcu if its the last reference */
 118 static void batadv_claim_free_ref(struct batadv_bla_claim *claim)
 119 {
 120         if (atomic_dec_and_test(&claim->refcount))
 121                 call_rcu(&claim->rcu, batadv_claim_free_rcu);
 122 }
 123
 124 /**
 125  * batadv_claim_hash_find
 126  * @bat_priv: the bat priv with all the soft interface information
 127  * @data: search data (may be local/static data)
 128  *
 129  * looks for a claim in the hash, and returns it if found
 130  * or NULL otherwise.
 131  */
 132 static struct batadv_bla_claim
 133 *batadv_claim_hash_find(struct batadv_priv *bat_priv,
 134                         struct batadv_bla_claim *data)
 135 {
 136         struct batadv_hashtable *hash = bat_priv->bla.claim_hash;
 137         struct hlist_head *head;
 138         struct batadv_bla_claim *claim;
 139         struct batadv_bla_claim *claim_tmp = NULL;
 140         int index;
 141
 142         if (!hash)
 143                 return NULL;
 144
 145         index = batadv_choose_claim(data, hash->size);
 146         head = &hash->table[index];
 147
 148         rcu_read_lock();
 149         hlist_for_each_entry_rcu(claim, head, hash_entry) {
 150                 if (!batadv_compare_claim(&claim->hash_entry, data))
 151                         continue;
 152
 153                 if (!atomic_inc_not_zero(&claim->refcount))
 154                         continue;
 155
 156                 claim_tmp = claim;
 157                 break;
 158         }
 159         rcu_read_unlock();
 160
 161         return claim_tmp;
 162 }
 163
 164 /**
 165  * batadv_backbone_hash_find - looks for a claim in the hash
 166  * @bat_priv: the bat priv with all the soft interface information
 167  * @addr: the address of the originator
 168  * @vid: the VLAN ID
 169  *
 170  * Returns claim if found or NULL otherwise.
 171  */
 172 static struct batadv_bla_backbone_gw *
 173 batadv_backbone_hash_find(struct batadv_priv *bat_priv,
 174                           uint8_t *addr, unsigned short vid)
 175 {
 176         struct batadv_hashtable *hash = bat_priv->bla.backbone_hash;
 177         struct hlist_head *head;
 178         struct batadv_bla_backbone_gw search_entry, *backbone_gw;
 179         struct batadv_bla_backbone_gw *backbone_gw_tmp = NULL;
 180         int index;
 181
 182         if (!hash)
 183                 return NULL;
 184
 185         ether_addr_copy(search_entry.orig, addr);
 186         search_entry.vid = vid;
 187
 188         index = batadv_choose_backbone_gw(&search_entry, hash->size);
 189         head = &hash->table[index];
 190
 191         rcu_read_lock();
 192         hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
 193                 if (!batadv_compare_backbone_gw(&backbone_gw->hash_entry,
 194                                                 &search_entry))
 195                         continue;
 196
 197                 if (!atomic_inc_not_zero(&backbone_gw->refcount))
 198                         continue;
 199
 200                 backbone_gw_tmp = backbone_gw;
 201                 break;
 202         }
 203         rcu_read_unlock();
 204
 205         return backbone_gw_tmp;
 206 }
 207
 208 /* delete all claims for a backbone */
 209 static void
 210 batadv_bla_del_backbone_claims(struct batadv_bla_backbone_gw *backbone_gw)
 211 {
 212         struct batadv_hashtable *hash;
 213         struct hlist_node *node_tmp;
 214         struct hlist_head *head;
 215         struct batadv_bla_claim *claim;
 216         int i;
 217         spinlock_t *list_lock;  /* protects write access to the hash lists */
 218
 219         hash = backbone_gw->bat_priv->bla.claim_hash;
 220         if (!hash)
 221                 return;
 222
 223         for (i = 0; i < hash->size; i++) {
 224                 head = &hash->table[i];
 225                 list_lock = &hash->list_locks[i];
 226
 227                 spin_lock_bh(list_lock);
 228                 hlist_for_each_entry_safe(claim, node_tmp,
 229                                           head, hash_entry) {
 230                         if (claim->backbone_gw != backbone_gw)
 231                                 continue;
 232
 233                         batadv_claim_free_ref(claim);
 234                         hlist_del_rcu(&claim->hash_entry);
 235                 }
 236                 spin_unlock_bh(list_lock);
 237         }
 238
 239         /* all claims gone, initialize CRC */
 240         backbone_gw->crc = BATADV_BLA_CRC_INIT;
 241 }
 242
 243 /**
 244  * batadv_bla_send_claim - sends a claim frame according to the provided info
 245  * @bat_priv: the bat priv with all the soft interface information
 246  * @mac: the mac address to be announced within the claim
 247  * @vid: the VLAN ID
 248  * @claimtype: the type of the claim (CLAIM, UNCLAIM, ANNOUNCE, ...)
 249  */
 250 static void batadv_bla_send_claim(struct batadv_priv *bat_priv, uint8_t *mac,
 251                                   unsigned short vid, int claimtype)
 252 {
 253         struct sk_buff *skb;
 254         struct ethhdr *ethhdr;
 255         struct batadv_hard_iface *primary_if;
 256         struct net_device *soft_iface;
 257         uint8_t *hw_src;
 258         struct batadv_bla_claim_dst local_claim_dest;
 259         __be32 zeroip = 0;
 260
 261         primary_if = batadv_primary_if_get_selected(bat_priv);
 262         if (!primary_if)
 263                 return;
 264
 265         memcpy(&local_claim_dest, &bat_priv->bla.claim_dest,
 266                sizeof(local_claim_dest));
 267         local_claim_dest.type = claimtype;
 268
 269         soft_iface = primary_if->soft_iface;
 270
 271         skb = arp_create(ARPOP_REPLY, ETH_P_ARP,
 272                          /* IP DST: 0.0.0.0 */
 273                          zeroip,
 274                          primary_if->soft_iface,
 275                          /* IP SRC: 0.0.0.0 */
 276                          zeroip,
 277                          /* Ethernet DST: Broadcast */
 278                          NULL,
 279                          /* Ethernet SRC/HW SRC:  originator mac */
 280                          primary_if->net_dev->dev_addr,
 281                          /* HW DST: FF:43:05:XX:YY:YY
 282                           * with XX   = claim type
 283                           * and YY:YY = group id
 284                           */
 285                          (uint8_t *)&local_claim_dest);
 286
 287         if (!skb)
 288                 goto out;
 289
 290         ethhdr = (struct ethhdr *)skb->data;
 291         hw_src = (uint8_t *)ethhdr + ETH_HLEN + sizeof(struct arphdr);
 292
 293         /* now we pretend that the client would have sent this ... */
 294         switch (claimtype) {
 295         case BATADV_CLAIM_TYPE_CLAIM:
 296                 /* normal claim frame
 297                  * set Ethernet SRC to the clients mac
 298                  */
 299                 ether_addr_copy(ethhdr->h_source, mac);
 300                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 301                            "bla_send_claim(): CLAIM %pM on vid %d\n", mac,
 302                            BATADV_PRINT_VID(vid));
 303                 break;
 304         case BATADV_CLAIM_TYPE_UNCLAIM:
 305                 /* unclaim frame
 306                  * set HW SRC to the clients mac
 307                  */
 308                 ether_addr_copy(hw_src, mac);
 309                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 310                            "bla_send_claim(): UNCLAIM %pM on vid %d\n", mac,
 311                            BATADV_PRINT_VID(vid));
 312                 break;
 313         case BATADV_CLAIM_TYPE_ANNOUNCE:
 314                 /* announcement frame
 315                  * set HW SRC to the special mac containg the crc
 316                  */
 317                 ether_addr_copy(hw_src, mac);
 318                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 319                            "bla_send_claim(): ANNOUNCE of %pM on vid %d\n",
 320                            ethhdr->h_source, BATADV_PRINT_VID(vid));
 321                 break;
 322         case BATADV_CLAIM_TYPE_REQUEST:
 323                 /* request frame
 324                  * set HW SRC and header destination to the receiving backbone
 325                  * gws mac
 326                  */
 327                 ether_addr_copy(hw_src, mac);
 328                 ether_addr_copy(ethhdr->h_dest, mac);
 329                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 330                            "bla_send_claim(): REQUEST of %pM to %pM on vid %d\n",
 331                            ethhdr->h_source, ethhdr->h_dest,
 332                            BATADV_PRINT_VID(vid));
 333                 break;
 334         }
 335
 336         if (vid & BATADV_VLAN_HAS_TAG)
 337                 skb = vlan_insert_tag(skb, htons(ETH_P_8021Q),
 338                                       vid & VLAN_VID_MASK);
 339
 340         skb_reset_mac_header(skb);
 341         skb->protocol = eth_type_trans(skb, soft_iface);
 342         batadv_inc_counter(bat_priv, BATADV_CNT_RX);
 343         batadv_add_counter(bat_priv, BATADV_CNT_RX_BYTES,
 344                            skb->len + ETH_HLEN);
 345         soft_iface->last_rx = jiffies;
 346
 347         netif_rx(skb);
 348 out:
 349         if (primary_if)
 350                 batadv_hardif_free_ref(primary_if);
 351 }
 352
 353 /**
 354  * batadv_bla_get_backbone_gw
 355  * @bat_priv: the bat priv with all the soft interface information
 356  * @orig: the mac address of the originator
 357  * @vid: the VLAN ID
 358  * @own_backbone: set if the requested backbone is local
 359  *
 360  * searches for the backbone gw or creates a new one if it could not
 361  * be found.
 362  */
 363 static struct batadv_bla_backbone_gw *
 364 batadv_bla_get_backbone_gw(struct batadv_priv *bat_priv, uint8_t *orig,
 365                            unsigned short vid, bool own_backbone)
 366 {
 367         struct batadv_bla_backbone_gw *entry;
 368         struct batadv_orig_node *orig_node;
 369         int hash_added;
 370
 371         entry = batadv_backbone_hash_find(bat_priv, orig, vid);
 372
 373         if (entry)
 374                 return entry;
 375
 376         batadv_dbg(BATADV_DBG_BLA, bat_priv,
 377                    "bla_get_backbone_gw(): not found (%pM, %d), creating new entry\n",
 378                    orig, BATADV_PRINT_VID(vid));
 379
 380         entry = kzalloc(sizeof(*entry), GFP_ATOMIC);
 381         if (!entry)
 382                 return NULL;
 383
 384         entry->vid = vid;
 385         entry->lasttime = jiffies;
 386         entry->crc = BATADV_BLA_CRC_INIT;
 387         entry->bat_priv = bat_priv;
 388         atomic_set(&entry->request_sent, 0);
 389         atomic_set(&entry->wait_periods, 0);
 390         ether_addr_copy(entry->orig, orig);
 391
 392         /* one for the hash, one for returning */
 393         atomic_set(&entry->refcount, 2);
 394
 395         hash_added = batadv_hash_add(bat_priv->bla.backbone_hash,
 396                                      batadv_compare_backbone_gw,
 397                                      batadv_choose_backbone_gw, entry,
 398                                      &entry->hash_entry);
 399
 400         if (unlikely(hash_added != 0)) {
 401                 /* hash failed, free the structure */
 402                 kfree(entry);
 403                 return NULL;
 404         }
 405
 406         /* this is a gateway now, remove any TT entry on this VLAN */
 407         orig_node = batadv_orig_hash_find(bat_priv, orig);
 408         if (orig_node) {
 409                 batadv_tt_global_del_orig(bat_priv, orig_node, vid,
 410                                           "became a backbone gateway");
 411                 batadv_orig_node_free_ref(orig_node);
 412         }
 413
 414         if (own_backbone) {
 415                 batadv_bla_send_announce(bat_priv, entry);
 416
 417                 /* this will be decreased in the worker thread */
 418                 atomic_inc(&entry->request_sent);
 419                 atomic_set(&entry->wait_periods, BATADV_BLA_WAIT_PERIODS);
 420                 atomic_inc(&bat_priv->bla.num_requests);
 421         }
 422
 423         return entry;
 424 }
 425
 426 /* update or add the own backbone gw to make sure we announce
 427  * where we receive other backbone gws
 428  */
 429 static void
 430 batadv_bla_update_own_backbone_gw(struct batadv_priv *bat_priv,
 431                                   struct batadv_hard_iface *primary_if,
 432                                   unsigned short vid)
 433 {
 434         struct batadv_bla_backbone_gw *backbone_gw;
 435
 436         backbone_gw = batadv_bla_get_backbone_gw(bat_priv,
 437                                                  primary_if->net_dev->dev_addr,
 438                                                  vid, true);
 439         if (unlikely(!backbone_gw))
 440                 return;
 441
 442         backbone_gw->lasttime = jiffies;
 443         batadv_backbone_gw_free_ref(backbone_gw);
 444 }
 445
 446 /**
 447  * batadv_bla_answer_request - answer a bla request by sending own claims
 448  * @bat_priv: the bat priv with all the soft interface information
 449  * @primary_if: interface where the request came on
 450  * @vid: the vid where the request came on
 451  *
 452  * Repeat all of our own claims, and finally send an ANNOUNCE frame
 453  * to allow the requester another check if the CRC is correct now.
 454  */
 455 static void batadv_bla_answer_request(struct batadv_priv *bat_priv,
 456                                       struct batadv_hard_iface *primary_if,
 457                                       unsigned short vid)
 458 {
 459         struct hlist_head *head;
 460         struct batadv_hashtable *hash;
 461         struct batadv_bla_claim *claim;
 462         struct batadv_bla_backbone_gw *backbone_gw;
 463         int i;
 464
 465         batadv_dbg(BATADV_DBG_BLA, bat_priv,
 466                    "bla_answer_request(): received a claim request, send all of our own claims again\n");
 467
 468         backbone_gw = batadv_backbone_hash_find(bat_priv,
 469                                                 primary_if->net_dev->dev_addr,
 470                                                 vid);
 471         if (!backbone_gw)
 472                 return;
 473
 474         hash = bat_priv->bla.claim_hash;
 475         for (i = 0; i < hash->size; i++) {
 476                 head = &hash->table[i];
 477
 478                 rcu_read_lock();
 479                 hlist_for_each_entry_rcu(claim, head, hash_entry) {
 480                         /* only own claims are interesting */
 481                         if (claim->backbone_gw != backbone_gw)
 482                                 continue;
 483
 484                         batadv_bla_send_claim(bat_priv, claim->addr, claim->vid,
 485                                               BATADV_CLAIM_TYPE_CLAIM);
 486                 }
 487                 rcu_read_unlock();
 488         }
 489
 490         /* finally, send an announcement frame */
 491         batadv_bla_send_announce(bat_priv, backbone_gw);
 492         batadv_backbone_gw_free_ref(backbone_gw);
 493 }
 494
 495 /**
 496  * batadv_bla_send_request - send a request to repeat claims
 497  * @backbone_gw: the backbone gateway from whom we are out of sync
 498  *
 499  * When the crc is wrong, ask the backbone gateway for a full table update.
 500  * After the request, it will repeat all of his own claims and finally
 501  * send an announcement claim with which we can check again.
 502  */
 503 static void batadv_bla_send_request(struct batadv_bla_backbone_gw *backbone_gw)
 504 {
 505         /* first, remove all old entries */
 506         batadv_bla_del_backbone_claims(backbone_gw);
 507
 508         batadv_dbg(BATADV_DBG_BLA, backbone_gw->bat_priv,
 509                    "Sending REQUEST to %pM\n", backbone_gw->orig);
 510
 511         /* send request */
 512         batadv_bla_send_claim(backbone_gw->bat_priv, backbone_gw->orig,
 513                               backbone_gw->vid, BATADV_CLAIM_TYPE_REQUEST);
 514
 515         /* no local broadcasts should be sent or received, for now. */
 516         if (!atomic_read(&backbone_gw->request_sent)) {
 517                 atomic_inc(&backbone_gw->bat_priv->bla.num_requests);
 518                 atomic_set(&backbone_gw->request_sent, 1);
 519         }
 520 }
 521
 522 /**
 523  * batadv_bla_send_announce
 524  * @bat_priv: the bat priv with all the soft interface information
 525  * @backbone_gw: our backbone gateway which should be announced
 526  *
 527  * This function sends an announcement. It is called from multiple
 528  * places.
 529  */
 530 static void batadv_bla_send_announce(struct batadv_priv *bat_priv,
 531                                      struct batadv_bla_backbone_gw *backbone_gw)
 532 {
 533         uint8_t mac[ETH_ALEN];
 534         __be16 crc;
 535
 536         memcpy(mac, batadv_announce_mac, 4);
 537         crc = htons(backbone_gw->crc);
 538         memcpy(&mac[4], &crc, 2);
 539
 540         batadv_bla_send_claim(bat_priv, mac, backbone_gw->vid,
 541                               BATADV_CLAIM_TYPE_ANNOUNCE);
 542 }
 543
 544 /**
 545  * batadv_bla_add_claim - Adds a claim in the claim hash
 546  * @bat_priv: the bat priv with all the soft interface information
 547  * @mac: the mac address of the claim
 548  * @vid: the VLAN ID of the frame
 549  * @backbone_gw: the backbone gateway which claims it
 550  */
 551 static void batadv_bla_add_claim(struct batadv_priv *bat_priv,
 552                                  const uint8_t *mac, const unsigned short vid,
 553                                  struct batadv_bla_backbone_gw *backbone_gw)
 554 {
 555         struct batadv_bla_claim *claim;
 556         struct batadv_bla_claim search_claim;
 557         int hash_added;
 558
 559         ether_addr_copy(search_claim.addr, mac);
 560         search_claim.vid = vid;
 561         claim = batadv_claim_hash_find(bat_priv, &search_claim);
 562
 563         /* create a new claim entry if it does not exist yet. */
 564         if (!claim) {
 565                 claim = kzalloc(sizeof(*claim), GFP_ATOMIC);
 566                 if (!claim)
 567                         return;
 568
 569                 ether_addr_copy(claim->addr, mac);
 570                 claim->vid = vid;
 571                 claim->lasttime = jiffies;
 572                 claim->backbone_gw = backbone_gw;
 573
 574                 atomic_set(&claim->refcount, 2);
 575                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 576                            "bla_add_claim(): adding new entry %pM, vid %d to hash ...\n",
 577                            mac, BATADV_PRINT_VID(vid));
 578                 hash_added = batadv_hash_add(bat_priv->bla.claim_hash,
 579                                              batadv_compare_claim,
 580                                              batadv_choose_claim, claim,
 581                                              &claim->hash_entry);
 582
 583                 if (unlikely(hash_added != 0)) {
 584                         /* only local changes happened. */
 585                         kfree(claim);
 586                         return;
 587                 }
 588         } else {
 589                 claim->lasttime = jiffies;
 590                 if (claim->backbone_gw == backbone_gw)
 591                         /* no need to register a new backbone */
 592                         goto claim_free_ref;
 593
 594                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 595                            "bla_add_claim(): changing ownership for %pM, vid %d\n",
 596                            mac, BATADV_PRINT_VID(vid));
 597
 598                 claim->backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN);
 599                 batadv_backbone_gw_free_ref(claim->backbone_gw);
 600         }
 601         /* set (new) backbone gw */
 602         atomic_inc(&backbone_gw->refcount);
 603         claim->backbone_gw = backbone_gw;
 604
 605         backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN);
 606         backbone_gw->lasttime = jiffies;
 607
 608 claim_free_ref:
 609         batadv_claim_free_ref(claim);
 610 }
 611
 612 /* Delete a claim from the claim hash which has the
 613  * given mac address and vid.
 614  */
 615 static void batadv_bla_del_claim(struct batadv_priv *bat_priv,
 616                                  const uint8_t *mac, const unsigned short vid)
 617 {
 618         struct batadv_bla_claim search_claim, *claim;
 619
 620         ether_addr_copy(search_claim.addr, mac);
 621         search_claim.vid = vid;
 622         claim = batadv_claim_hash_find(bat_priv, &search_claim);
 623         if (!claim)
 624                 return;
 625
 626         batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla_del_claim(): %pM, vid %d\n",
 627                    mac, BATADV_PRINT_VID(vid));
 628
 629         batadv_hash_remove(bat_priv->bla.claim_hash, batadv_compare_claim,
 630                            batadv_choose_claim, claim);
 631         batadv_claim_free_ref(claim); /* reference from the hash is gone */
 632
 633         claim->backbone_gw->crc ^= crc16(0, claim->addr, ETH_ALEN);
 634
 635         /* don't need the reference from hash_find() anymore */
 636         batadv_claim_free_ref(claim);
 637 }
 638
 639 /* check for ANNOUNCE frame, return 1 if handled */
 640 static int batadv_handle_announce(struct batadv_priv *bat_priv,
 641                                   uint8_t *an_addr, uint8_t *backbone_addr,
 642                                   unsigned short vid)
 643 {
 644         struct batadv_bla_backbone_gw *backbone_gw;
 645         uint16_t crc;
 646
 647         if (memcmp(an_addr, batadv_announce_mac, 4) != 0)
 648                 return 0;
 649
 650         backbone_gw = batadv_bla_get_backbone_gw(bat_priv, backbone_addr, vid,
 651                                                  false);
 652
 653         if (unlikely(!backbone_gw))
 654                 return 1;
 655
 656         /* handle as ANNOUNCE frame */
 657         backbone_gw->lasttime = jiffies;
 658         crc = ntohs(*((__be16 *)(&an_addr[4])));
 659
 660         batadv_dbg(BATADV_DBG_BLA, bat_priv,
 661                    "handle_announce(): ANNOUNCE vid %d (sent by %pM)... CRC = %#.4x\n",
 662                    BATADV_PRINT_VID(vid), backbone_gw->orig, crc);
 663
 664         if (backbone_gw->crc != crc) {
 665                 batadv_dbg(BATADV_DBG_BLA, backbone_gw->bat_priv,
 666                            "handle_announce(): CRC FAILED for %pM/%d (my = %#.4x, sent = %#.4x)\n",
 667                            backbone_gw->orig,
 668                            BATADV_PRINT_VID(backbone_gw->vid),
 669                            backbone_gw->crc, crc);
 670
 671                 batadv_bla_send_request(backbone_gw);
 672         } else {
 673                 /* if we have sent a request and the crc was OK,
 674                  * we can allow traffic again.
 675                  */
 676                 if (atomic_read(&backbone_gw->request_sent)) {
 677                         atomic_dec(&backbone_gw->bat_priv->bla.num_requests);
 678                         atomic_set(&backbone_gw->request_sent, 0);
 679                 }
 680         }
 681
 682         batadv_backbone_gw_free_ref(backbone_gw);
 683         return 1;
 684 }
 685
 686 /* check for REQUEST frame, return 1 if handled */
 687 static int batadv_handle_request(struct batadv_priv *bat_priv,
 688                                  struct batadv_hard_iface *primary_if,
 689                                  uint8_t *backbone_addr,
 690                                  struct ethhdr *ethhdr, unsigned short vid)
 691 {
 692         /* check for REQUEST frame */
 693         if (!batadv_compare_eth(backbone_addr, ethhdr->h_dest))
 694                 return 0;
 695
 696         /* sanity check, this should not happen on a normal switch,
 697          * we ignore it in this case.
 698          */
 699         if (!batadv_compare_eth(ethhdr->h_dest, primary_if->net_dev->dev_addr))
 700                 return 1;
 701
 702         batadv_dbg(BATADV_DBG_BLA, bat_priv,
 703                    "handle_request(): REQUEST vid %d (sent by %pM)...\n",
 704                    BATADV_PRINT_VID(vid), ethhdr->h_source);
 705
 706         batadv_bla_answer_request(bat_priv, primary_if, vid);
 707         return 1;
 708 }
 709
 710 /* check for UNCLAIM frame, return 1 if handled */
 711 static int batadv_handle_unclaim(struct batadv_priv *bat_priv,
 712                                  struct batadv_hard_iface *primary_if,
 713                                  uint8_t *backbone_addr,
 714                                  uint8_t *claim_addr, unsigned short vid)
 715 {
 716         struct batadv_bla_backbone_gw *backbone_gw;
 717
 718         /* unclaim in any case if it is our own */
 719         if (primary_if && batadv_compare_eth(backbone_addr,
 720                                              primary_if->net_dev->dev_addr))
 721                 batadv_bla_send_claim(bat_priv, claim_addr, vid,
 722                                       BATADV_CLAIM_TYPE_UNCLAIM);
 723
 724         backbone_gw = batadv_backbone_hash_find(bat_priv, backbone_addr, vid);
 725
 726         if (!backbone_gw)
 727                 return 1;
 728
 729         /* this must be an UNCLAIM frame */
 730         batadv_dbg(BATADV_DBG_BLA, bat_priv,
 731                    "handle_unclaim(): UNCLAIM %pM on vid %d (sent by %pM)...\n",
 732                    claim_addr, BATADV_PRINT_VID(vid), backbone_gw->orig);
 733
 734         batadv_bla_del_claim(bat_priv, claim_addr, vid);
 735         batadv_backbone_gw_free_ref(backbone_gw);
 736         return 1;
 737 }
 738
 739 /* check for CLAIM frame, return 1 if handled */
 740 static int batadv_handle_claim(struct batadv_priv *bat_priv,
 741                                struct batadv_hard_iface *primary_if,
 742                                uint8_t *backbone_addr, uint8_t *claim_addr,
 743                                unsigned short vid)
 744 {
 745         struct batadv_bla_backbone_gw *backbone_gw;
 746
 747         /* register the gateway if not yet available, and add the claim. */
 748
 749         backbone_gw = batadv_bla_get_backbone_gw(bat_priv, backbone_addr, vid,
 750                                                  false);
 751
 752         if (unlikely(!backbone_gw))
 753                 return 1;
 754
 755         /* this must be a CLAIM frame */
 756         batadv_bla_add_claim(bat_priv, claim_addr, vid, backbone_gw);
 757         if (batadv_compare_eth(backbone_addr, primary_if->net_dev->dev_addr))
 758                 batadv_bla_send_claim(bat_priv, claim_addr, vid,
 759                                       BATADV_CLAIM_TYPE_CLAIM);
 760
 761         /* TODO: we could call something like tt_local_del() here. */
 762
 763         batadv_backbone_gw_free_ref(backbone_gw);
 764         return 1;
 765 }
 766
 767 /**
 768  * batadv_check_claim_group
 769  * @bat_priv: the bat priv with all the soft interface information
 770  * @primary_if: the primary interface of this batman interface
 771  * @hw_src: the Hardware source in the ARP Header
 772  * @hw_dst: the Hardware destination in the ARP Header
 773  * @ethhdr: pointer to the Ethernet header of the claim frame
 774  *
 775  * checks if it is a claim packet and if its on the same group.
 776  * This function also applies the group ID of the sender
 777  * if it is in the same mesh.
 778  *
 779  * returns:
 780  *      2  - if it is a claim packet and on the same group
 781  *      1  - if is a claim packet from another group
 782  *      0  - if it is not a claim packet
 783  */
 784 static int batadv_check_claim_group(struct batadv_priv *bat_priv,
 785                                     struct batadv_hard_iface *primary_if,
 786                                     uint8_t *hw_src, uint8_t *hw_dst,
 787                                     struct ethhdr *ethhdr)
 788 {
 789         uint8_t *backbone_addr;
 790         struct batadv_orig_node *orig_node;
 791         struct batadv_bla_claim_dst *bla_dst, *bla_dst_own;
 792
 793         bla_dst = (struct batadv_bla_claim_dst *)hw_dst;
 794         bla_dst_own = &bat_priv->bla.claim_dest;
 795
 796         /* if announcement packet, use the source,
 797          * otherwise assume it is in the hw_src
 798          */
 799         switch (bla_dst->type) {
 800         case BATADV_CLAIM_TYPE_CLAIM:
 801                 backbone_addr = hw_src;
 802                 break;
 803         case BATADV_CLAIM_TYPE_REQUEST:
 804         case BATADV_CLAIM_TYPE_ANNOUNCE:
 805         case BATADV_CLAIM_TYPE_UNCLAIM:
 806                 backbone_addr = ethhdr->h_source;
 807                 break;
 808         default:
 809                 return 0;
 810         }
 811
 812         /* don't accept claim frames from ourselves */
 813         if (batadv_compare_eth(backbone_addr, primary_if->net_dev->dev_addr))
 814                 return 0;
 815
 816         /* if its already the same group, it is fine. */
 817         if (bla_dst->group == bla_dst_own->group)
 818                 return 2;
 819
 820         /* lets see if this originator is in our mesh */
 821         orig_node = batadv_orig_hash_find(bat_priv, backbone_addr);
 822
 823         /* dont accept claims from gateways which are not in
 824          * the same mesh or group.
 825          */
 826         if (!orig_node)
 827                 return 1;
 828
 829         /* if our mesh friends mac is bigger, use it for ourselves. */
 830         if (ntohs(bla_dst->group) > ntohs(bla_dst_own->group)) {
 831                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 832                            "taking other backbones claim group: %#.4x\n",
 833                            ntohs(bla_dst->group));
 834                 bla_dst_own->group = bla_dst->group;
 835         }
 836
 837         batadv_orig_node_free_ref(orig_node);
 838
 839         return 2;
 840 }
 841
 842 /**
 843  * batadv_bla_process_claim
 844  * @bat_priv: the bat priv with all the soft interface information
 845  * @primary_if: the primary hard interface of this batman soft interface
 846  * @skb: the frame to be checked
 847  *
 848  * Check if this is a claim frame, and process it accordingly.
 849  *
 850  * returns 1 if it was a claim frame, otherwise return 0 to
 851  * tell the callee that it can use the frame on its own.
 852  */
 853 static int batadv_bla_process_claim(struct batadv_priv *bat_priv,
 854                                     struct batadv_hard_iface *primary_if,
 855                                     struct sk_buff *skb)
 856 {
 857         struct batadv_bla_claim_dst *bla_dst, *bla_dst_own;
 858         uint8_t *hw_src, *hw_dst;
 859         struct vlan_hdr *vhdr, vhdr_buf;
 860         struct ethhdr *ethhdr;
 861         struct arphdr *arphdr;
 862         unsigned short vid;
 863         int vlan_depth = 0;
 864         __be16 proto;
 865         int headlen;
 866         int ret;
 867
 868         vid = batadv_get_vid(skb, 0);
 869         ethhdr = eth_hdr(skb);
 870
 871         proto = ethhdr->h_proto;
 872         headlen = ETH_HLEN;
 873         if (vid & BATADV_VLAN_HAS_TAG) {
 874                 /* Traverse the VLAN/Ethertypes.
 875                  *
 876                  * At this point it is known that the first protocol is a VLAN
 877                  * header, so start checking at the encapsulated protocol.
 878                  *
 879                  * The depth of the VLAN headers is recorded to drop BLA claim
 880                  * frames encapsulated into multiple VLAN headers (QinQ).
 881                  */
 882                 do {
 883                         vhdr = skb_header_pointer(skb, headlen, VLAN_HLEN,
 884                                                   &vhdr_buf);
 885                         if (!vhdr)
 886                                 return 0;
 887
 888                         proto = vhdr->h_vlan_encapsulated_proto;
 889                         headlen += VLAN_HLEN;
 890                         vlan_depth++;
 891                 } while (proto == htons(ETH_P_8021Q));
 892         }
 893
 894         if (proto != htons(ETH_P_ARP))
 895                 return 0; /* not a claim frame */
 896
 897         /* this must be a ARP frame. check if it is a claim. */
 898
 899         if (unlikely(!pskb_may_pull(skb, headlen + arp_hdr_len(skb->dev))))
 900                 return 0;
 901
 902         /* pskb_may_pull() may have modified the pointers, get ethhdr again */
 903         ethhdr = eth_hdr(skb);
 904         arphdr = (struct arphdr *)((uint8_t *)ethhdr + headlen);
 905
 906         /* Check whether the ARP frame carries a valid
 907          * IP information
 908          */
 909         if (arphdr->ar_hrd != htons(ARPHRD_ETHER))
 910                 return 0;
 911         if (arphdr->ar_pro != htons(ETH_P_IP))
 912                 return 0;
 913         if (arphdr->ar_hln != ETH_ALEN)
 914                 return 0;
 915         if (arphdr->ar_pln != 4)
 916                 return 0;
 917
 918         hw_src = (uint8_t *)arphdr + sizeof(struct arphdr);
 919         hw_dst = hw_src + ETH_ALEN + 4;
 920         bla_dst = (struct batadv_bla_claim_dst *)hw_dst;
 921         bla_dst_own = &bat_priv->bla.claim_dest;
 922
 923         /* check if it is a claim frame in general */
 924         if (memcmp(bla_dst->magic, bla_dst_own->magic,
 925                    sizeof(bla_dst->magic)) != 0)
 926                 return 0;
 927
 928         /* check if there is a claim frame encapsulated deeper in (QinQ) and
 929          * drop that, as this is not supported by BLA but should also not be
 930          * sent via the mesh.
 931          */
 932         if (vlan_depth > 1)
 933                 return 1;
 934
 935         /* check if it is a claim frame. */
 936         ret = batadv_check_claim_group(bat_priv, primary_if, hw_src, hw_dst,
 937                                        ethhdr);
 938         if (ret == 1)
 939                 batadv_dbg(BATADV_DBG_BLA, bat_priv,
 940                            "bla_process_claim(): received a claim frame from another group. From: %pM on vid %d ...(hw_src %pM, hw_dst %pM)\n",
 941                            ethhdr->h_source, BATADV_PRINT_VID(vid), hw_src,
 942                            hw_dst);
 943
 944         if (ret < 2)
 945                 return ret;
 946
 947         /* become a backbone gw ourselves on this vlan if not happened yet */
 948         batadv_bla_update_own_backbone_gw(bat_priv, primary_if, vid);
 949
 950         /* check for the different types of claim frames ... */
 951         switch (bla_dst->type) {
 952         case BATADV_CLAIM_TYPE_CLAIM:
 953                 if (batadv_handle_claim(bat_priv, primary_if, hw_src,
 954                                         ethhdr->h_source, vid))
 955                         return 1;
 956                 break;
 957         case BATADV_CLAIM_TYPE_UNCLAIM:
 958                 if (batadv_handle_unclaim(bat_priv, primary_if,
 959                                           ethhdr->h_source, hw_src, vid))
 960                         return 1;
 961                 break;
 962
 963         case BATADV_CLAIM_TYPE_ANNOUNCE:
 964                 if (batadv_handle_announce(bat_priv, hw_src, ethhdr->h_source,
 965                                            vid))
 966                         return 1;
 967                 break;
 968         case BATADV_CLAIM_TYPE_REQUEST:
 969                 if (batadv_handle_request(bat_priv, primary_if, hw_src, ethhdr,
 970                                           vid))
 971                         return 1;
 972                 break;
 973         }
 974
 975         batadv_dbg(BATADV_DBG_BLA, bat_priv,
 976                    "bla_process_claim(): ERROR - this looks like a claim frame, but is useless. eth src %pM on vid %d ...(hw_src %pM, hw_dst %pM)\n",
 977                    ethhdr->h_source, BATADV_PRINT_VID(vid), hw_src, hw_dst);
 978         return 1;
 979 }
 980
 981 /* Check when we last heard from other nodes, and remove them in case of
 982  * a time out, or clean all backbone gws if now is set.
 983  */
 984 static void batadv_bla_purge_backbone_gw(struct batadv_priv *bat_priv, int now)
 985 {
 986         struct batadv_bla_backbone_gw *backbone_gw;
 987         struct hlist_node *node_tmp;
 988         struct hlist_head *head;
 989         struct batadv_hashtable *hash;
 990         spinlock_t *list_lock;  /* protects write access to the hash lists */
 991         int i;
 992
 993         hash = bat_priv->bla.backbone_hash;
 994         if (!hash)
 995                 return;
 996
 997         for (i = 0; i < hash->size; i++) {
 998                 head = &hash->table[i];
 999                 list_lock = &hash->list_locks[i];
1000
1001                 spin_lock_bh(list_lock);
1002                 hlist_for_each_entry_safe(backbone_gw, node_tmp,
1003                                           head, hash_entry) {
1004                         if (now)
1005                                 goto purge_now;
1006                         if (!batadv_has_timed_out(backbone_gw->lasttime,
1007                                                   BATADV_BLA_BACKBONE_TIMEOUT))
1008                                 continue;
1009
1010                         batadv_dbg(BATADV_DBG_BLA, backbone_gw->bat_priv,
1011                                    "bla_purge_backbone_gw(): backbone gw %pM timed out\n",
1012                                    backbone_gw->orig);
1013
1014 purge_now:
1015                         /* don't wait for the pending request anymore */
1016                         if (atomic_read(&backbone_gw->request_sent))
1017                                 atomic_dec(&bat_priv->bla.num_requests);
1018
1019                         batadv_bla_del_backbone_claims(backbone_gw);
1020
1021                         hlist_del_rcu(&backbone_gw->hash_entry);
1022                         batadv_backbone_gw_free_ref(backbone_gw);
1023                 }
1024                 spin_unlock_bh(list_lock);
1025         }
1026 }
1027
1028 /**
1029  * batadv_bla_purge_claims
1030  * @bat_priv: the bat priv with all the soft interface information
1031  * @primary_if: the selected primary interface, may be NULL if now is set
1032  * @now: whether the whole hash shall be wiped now
1033  *
1034  * Check when we heard last time from our own claims, and remove them in case of
1035  * a time out, or clean all claims if now is set
1036  */
1037 static void batadv_bla_purge_claims(struct batadv_priv *bat_priv,
1038                                     struct batadv_hard_iface *primary_if,
1039                                     int now)
1040 {
1041         struct batadv_bla_claim *claim;
1042         struct hlist_head *head;
1043         struct batadv_hashtable *hash;
1044         int i;
1045
1046         hash = bat_priv->bla.claim_hash;
1047         if (!hash)
1048                 return;
1049
1050         for (i = 0; i < hash->size; i++) {
1051                 head = &hash->table[i];
1052
1053                 rcu_read_lock();
1054                 hlist_for_each_entry_rcu(claim, head, hash_entry) {
1055                         if (now)
1056                                 goto purge_now;
1057                         if (!batadv_compare_eth(claim->backbone_gw->orig,
1058                                                 primary_if->net_dev->dev_addr))
1059                                 continue;
1060                         if (!batadv_has_timed_out(claim->lasttime,
1061                                                   BATADV_BLA_CLAIM_TIMEOUT))
1062                                 continue;
1063
1064                         batadv_dbg(BATADV_DBG_BLA, bat_priv,
1065                                    "bla_purge_claims(): %pM, vid %d, time out\n",
1066                                    claim->addr, claim->vid);
1067
1068 purge_now:
1069                         batadv_handle_unclaim(bat_priv, primary_if,
1070                                               claim->backbone_gw->orig,
1071                                               claim->addr, claim->vid);
1072                 }
1073                 rcu_read_unlock();
1074         }
1075 }
1076
1077 /**
1078  * batadv_bla_update_orig_address
1079  * @bat_priv: the bat priv with all the soft interface information
1080  * @primary_if: the new selected primary_if
1081  * @oldif: the old primary interface, may be NULL
1082  *
1083  * Update the backbone gateways when the own orig address changes.
1084  */
1085 void batadv_bla_update_orig_address(struct batadv_priv *bat_priv,
1086                                     struct batadv_hard_iface *primary_if,
1087                                     struct batadv_hard_iface *oldif)
1088 {
1089         struct batadv_bla_backbone_gw *backbone_gw;
1090         struct hlist_head *head;
1091         struct batadv_hashtable *hash;
1092         __be16 group;
1093         int i;
1094
1095         /* reset bridge loop avoidance group id */
1096         group = htons(crc16(0, primary_if->net_dev->dev_addr, ETH_ALEN));
1097         bat_priv->bla.claim_dest.group = group;
1098
1099         /* purge everything when bridge loop avoidance is turned off */
1100         if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1101                 oldif = NULL;
1102
1103         if (!oldif) {
1104                 batadv_bla_purge_claims(bat_priv, NULL, 1);
1105                 batadv_bla_purge_backbone_gw(bat_priv, 1);
1106                 return;
1107         }
1108
1109         hash = bat_priv->bla.backbone_hash;
1110         if (!hash)
1111                 return;
1112
1113         for (i = 0; i < hash->size; i++) {
1114                 head = &hash->table[i];
1115
1116                 rcu_read_lock();
1117                 hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1118                         /* own orig still holds the old value. */
1119                         if (!batadv_compare_eth(backbone_gw->orig,
1120                                                 oldif->net_dev->dev_addr))
1121                                 continue;
1122
1123                         ether_addr_copy(backbone_gw->orig,
1124                                         primary_if->net_dev->dev_addr);
1125                         /* send an announce frame so others will ask for our
1126                          * claims and update their tables.
1127                          */
1128                         batadv_bla_send_announce(bat_priv, backbone_gw);
1129                 }
1130                 rcu_read_unlock();
1131         }
1132 }
1133
1134 /* periodic work to do:
1135  *  * purge structures when they are too old
1136  *  * send announcements
1137  */
1138 static void batadv_bla_periodic_work(struct work_struct *work)
1139 {
1140         struct delayed_work *delayed_work;
1141         struct batadv_priv *bat_priv;
1142         struct batadv_priv_bla *priv_bla;
1143         struct hlist_head *head;
1144         struct batadv_bla_backbone_gw *backbone_gw;
1145         struct batadv_hashtable *hash;
1146         struct batadv_hard_iface *primary_if;
1147         int i;
1148
1149         delayed_work = container_of(work, struct delayed_work, work);
1150         priv_bla = container_of(delayed_work, struct batadv_priv_bla, work);
1151         bat_priv = container_of(priv_bla, struct batadv_priv, bla);
1152         primary_if = batadv_primary_if_get_selected(bat_priv);
1153         if (!primary_if)
1154                 goto out;
1155
1156         batadv_bla_purge_claims(bat_priv, primary_if, 0);
1157         batadv_bla_purge_backbone_gw(bat_priv, 0);
1158
1159         if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1160                 goto out;
1161
1162         hash = bat_priv->bla.backbone_hash;
1163         if (!hash)
1164                 goto out;
1165
1166         for (i = 0; i < hash->size; i++) {
1167                 head = &hash->table[i];
1168
1169                 rcu_read_lock();
1170                 hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1171                         if (!batadv_compare_eth(backbone_gw->orig,
1172                                                 primary_if->net_dev->dev_addr))
1173                                 continue;
1174
1175                         backbone_gw->lasttime = jiffies;
1176
1177                         batadv_bla_send_announce(bat_priv, backbone_gw);
1178
1179                         /* request_sent is only set after creation to avoid
1180                          * problems when we are not yet known as backbone gw
1181                          * in the backbone.
1182                          *
1183                          * We can reset this now after we waited some periods
1184                          * to give bridge forward delays and bla group forming
1185                          * some grace time.
1186                          */
1187
1188                         if (atomic_read(&backbone_gw->request_sent) == 0)
1189                                 continue;
1190
1191                         if (!atomic_dec_and_test(&backbone_gw->wait_periods))
1192                                 continue;
1193
1194                         atomic_dec(&backbone_gw->bat_priv->bla.num_requests);
1195                         atomic_set(&backbone_gw->request_sent, 0);
1196                 }
1197                 rcu_read_unlock();
1198         }
1199 out:
1200         if (primary_if)
1201                 batadv_hardif_free_ref(primary_if);
1202
1203         queue_delayed_work(batadv_event_workqueue, &bat_priv->bla.work,
1204                            msecs_to_jiffies(BATADV_BLA_PERIOD_LENGTH));
1205 }
1206
1207 /* The hash for claim and backbone hash receive the same key because they
1208  * are getting initialized by hash_new with the same key. Reinitializing
1209  * them with to different keys to allow nested locking without generating
1210  * lockdep warnings
1211  */
1212 static struct lock_class_key batadv_claim_hash_lock_class_key;
1213 static struct lock_class_key batadv_backbone_hash_lock_class_key;
1214
1215 /* initialize all bla structures */
1216 int batadv_bla_init(struct batadv_priv *bat_priv)
1217 {
1218         int i;
1219         uint8_t claim_dest[ETH_ALEN] = {0xff, 0x43, 0x05, 0x00, 0x00, 0x00};
1220         struct batadv_hard_iface *primary_if;
1221         uint16_t crc;
1222         unsigned long entrytime;
1223
1224         spin_lock_init(&bat_priv->bla.bcast_duplist_lock);
1225
1226         batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla hash registering\n");
1227
1228         /* setting claim destination address */
1229         memcpy(&bat_priv->bla.claim_dest.magic, claim_dest, 3);
1230         bat_priv->bla.claim_dest.type = 0;
1231         primary_if = batadv_primary_if_get_selected(bat_priv);
1232         if (primary_if) {
1233                 crc = crc16(0, primary_if->net_dev->dev_addr, ETH_ALEN);
1234                 bat_priv->bla.claim_dest.group = htons(crc);
1235                 batadv_hardif_free_ref(primary_if);
1236         } else {
1237                 bat_priv->bla.claim_dest.group = 0; /* will be set later */
1238         }
1239
1240         /* initialize the duplicate list */
1241         entrytime = jiffies - msecs_to_jiffies(BATADV_DUPLIST_TIMEOUT);
1242         for (i = 0; i < BATADV_DUPLIST_SIZE; i++)
1243                 bat_priv->bla.bcast_duplist[i].entrytime = entrytime;
1244         bat_priv->bla.bcast_duplist_curr = 0;
1245
1246         if (bat_priv->bla.claim_hash)
1247                 return 0;
1248
1249         bat_priv->bla.claim_hash = batadv_hash_new(128);
1250         bat_priv->bla.backbone_hash = batadv_hash_new(32);
1251
1252         if (!bat_priv->bla.claim_hash || !bat_priv->bla.backbone_hash)
1253                 return -ENOMEM;
1254
1255         batadv_hash_set_lock_class(bat_priv->bla.claim_hash,
1256                                    &batadv_claim_hash_lock_class_key);
1257         batadv_hash_set_lock_class(bat_priv->bla.backbone_hash,
1258                                    &batadv_backbone_hash_lock_class_key);
1259
1260         batadv_dbg(BATADV_DBG_BLA, bat_priv, "bla hashes initialized\n");
1261
1262         INIT_DELAYED_WORK(&bat_priv->bla.work, batadv_bla_periodic_work);
1263
1264         queue_delayed_work(batadv_event_workqueue, &bat_priv->bla.work,
1265                            msecs_to_jiffies(BATADV_BLA_PERIOD_LENGTH));
1266         return 0;
1267 }
1268
1269 /**
1270  * batadv_bla_check_bcast_duplist
1271  * @bat_priv: the bat priv with all the soft interface information
1272  * @skb: contains the bcast_packet to be checked
1273  *
1274  * check if it is on our broadcast list. Another gateway might
1275  * have sent the same packet because it is connected to the same backbone,
1276  * so we have to remove this duplicate.
1277  *
1278  * This is performed by checking the CRC, which will tell us
1279  * with a good chance that it is the same packet. If it is furthermore
1280  * sent by another host, drop it. We allow equal packets from
1281  * the same host however as this might be intended.
1282  */
1283 int batadv_bla_check_bcast_duplist(struct batadv_priv *bat_priv,
1284                                    struct sk_buff *skb)
1285 {
1286         int i, curr, ret = 0;
1287         __be32 crc;
1288         struct batadv_bcast_packet *bcast_packet;
1289         struct batadv_bcast_duplist_entry *entry;
1290
1291         bcast_packet = (struct batadv_bcast_packet *)skb->data;
1292
1293         /* calculate the crc ... */
1294         crc = batadv_skb_crc32(skb, (u8 *)(bcast_packet + 1));
1295
1296         spin_lock_bh(&bat_priv->bla.bcast_duplist_lock);
1297
1298         for (i = 0; i < BATADV_DUPLIST_SIZE; i++) {
1299                 curr = (bat_priv->bla.bcast_duplist_curr + i);
1300                 curr %= BATADV_DUPLIST_SIZE;
1301                 entry = &bat_priv->bla.bcast_duplist[curr];
1302
1303                 /* we can stop searching if the entry is too old ;
1304                  * later entries will be even older
1305                  */
1306                 if (batadv_has_timed_out(entry->entrytime,
1307                                          BATADV_DUPLIST_TIMEOUT))
1308                         break;
1309
1310                 if (entry->crc != crc)
1311                         continue;
1312
1313                 if (batadv_compare_eth(entry->orig, bcast_packet->orig))
1314                         continue;
1315
1316                 /* this entry seems to match: same crc, not too old,
1317                  * and from another gw. therefore return 1 to forbid it.
1318                  */
1319                 ret = 1;
1320                 goto out;
1321         }
1322         /* not found, add a new entry (overwrite the oldest entry)
1323          * and allow it, its the first occurrence.
1324          */
1325         curr = (bat_priv->bla.bcast_duplist_curr + BATADV_DUPLIST_SIZE - 1);
1326         curr %= BATADV_DUPLIST_SIZE;
1327         entry = &bat_priv->bla.bcast_duplist[curr];
1328         entry->crc = crc;
1329         entry->entrytime = jiffies;
1330         ether_addr_copy(entry->orig, bcast_packet->orig);
1331         bat_priv->bla.bcast_duplist_curr = curr;
1332
1333 out:
1334         spin_unlock_bh(&bat_priv->bla.bcast_duplist_lock);
1335
1336         return ret;
1337 }
1338
1339 /**
1340  * batadv_bla_is_backbone_gw_orig
1341  * @bat_priv: the bat priv with all the soft interface information
1342  * @orig: originator mac address
1343  * @vid: VLAN identifier
1344  *
1345  * Check if the originator is a gateway for the VLAN identified by vid.
1346  *
1347  * Returns true if orig is a backbone for this vid, false otherwise.
1348  */
1349 bool batadv_bla_is_backbone_gw_orig(struct batadv_priv *bat_priv, uint8_t *orig,
1350                                     unsigned short vid)
1351 {
1352         struct batadv_hashtable *hash = bat_priv->bla.backbone_hash;
1353         struct hlist_head *head;
1354         struct batadv_bla_backbone_gw *backbone_gw;
1355         int i;
1356
1357         if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1358                 return false;
1359
1360         if (!hash)
1361                 return false;
1362
1363         for (i = 0; i < hash->size; i++) {
1364                 head = &hash->table[i];
1365
1366                 rcu_read_lock();
1367                 hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1368                         if (batadv_compare_eth(backbone_gw->orig, orig) &&
1369                             backbone_gw->vid == vid) {
1370                                 rcu_read_unlock();
1371                                 return true;
1372                         }
1373                 }
1374                 rcu_read_unlock();
1375         }
1376
1377         return false;
1378 }
1379
1380 /**
1381  * batadv_bla_is_backbone_gw
1382  * @skb: the frame to be checked
1383  * @orig_node: the orig_node of the frame
1384  * @hdr_size: maximum length of the frame
1385  *
1386  * bla_is_backbone_gw inspects the skb for the VLAN ID and returns 1
1387  * if the orig_node is also a gateway on the soft interface, otherwise it
1388  * returns 0.
1389  */
1390 int batadv_bla_is_backbone_gw(struct sk_buff *skb,
1391                               struct batadv_orig_node *orig_node, int hdr_size)
1392 {
1393         struct batadv_bla_backbone_gw *backbone_gw;
1394         unsigned short vid;
1395
1396         if (!atomic_read(&orig_node->bat_priv->bridge_loop_avoidance))
1397                 return 0;
1398
1399         /* first, find out the vid. */
1400         if (!pskb_may_pull(skb, hdr_size + ETH_HLEN))
1401                 return 0;
1402
1403         vid = batadv_get_vid(skb, hdr_size);
1404
1405         /* see if this originator is a backbone gw for this VLAN */
1406         backbone_gw = batadv_backbone_hash_find(orig_node->bat_priv,
1407                                                 orig_node->orig, vid);
1408         if (!backbone_gw)
1409                 return 0;
1410
1411         batadv_backbone_gw_free_ref(backbone_gw);
1412         return 1;
1413 }
1414
1415 /* free all bla structures (for softinterface free or module unload) */
1416 void batadv_bla_free(struct batadv_priv *bat_priv)
1417 {
1418         struct batadv_hard_iface *primary_if;
1419
1420         cancel_delayed_work_sync(&bat_priv->bla.work);
1421         primary_if = batadv_primary_if_get_selected(bat_priv);
1422
1423         if (bat_priv->bla.claim_hash) {
1424                 batadv_bla_purge_claims(bat_priv, primary_if, 1);
1425                 batadv_hash_destroy(bat_priv->bla.claim_hash);
1426                 bat_priv->bla.claim_hash = NULL;
1427         }
1428         if (bat_priv->bla.backbone_hash) {
1429                 batadv_bla_purge_backbone_gw(bat_priv, 1);
1430                 batadv_hash_destroy(bat_priv->bla.backbone_hash);
1431                 bat_priv->bla.backbone_hash = NULL;
1432         }
1433         if (primary_if)
1434                 batadv_hardif_free_ref(primary_if);
1435 }
1436
1437 /**
1438  * batadv_bla_rx
1439  * @bat_priv: the bat priv with all the soft interface information
1440  * @skb: the frame to be checked
1441  * @vid: the VLAN ID of the frame
1442  * @is_bcast: the packet came in a broadcast packet type.
1443  *
1444  * bla_rx avoidance checks if:
1445  *  * we have to race for a claim
1446  *  * if the frame is allowed on the LAN
1447  *
1448  * in these cases, the skb is further handled by this function and
1449  * returns 1, otherwise it returns 0 and the caller shall further
1450  * process the skb.
1451  */
1452 int batadv_bla_rx(struct batadv_priv *bat_priv, struct sk_buff *skb,
1453                   unsigned short vid, bool is_bcast)
1454 {
1455         struct ethhdr *ethhdr;
1456         struct batadv_bla_claim search_claim, *claim = NULL;
1457         struct batadv_hard_iface *primary_if;
1458         int ret;
1459
1460         ethhdr = eth_hdr(skb);
1461
1462         primary_if = batadv_primary_if_get_selected(bat_priv);
1463         if (!primary_if)
1464                 goto handled;
1465
1466         if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1467                 goto allow;
1468
1469         if (unlikely(atomic_read(&bat_priv->bla.num_requests)))
1470                 /* don't allow broadcasts while requests are in flight */
1471                 if (is_multicast_ether_addr(ethhdr->h_dest) && is_bcast)
1472                         goto handled;
1473
1474         ether_addr_copy(search_claim.addr, ethhdr->h_source);
1475         search_claim.vid = vid;
1476         claim = batadv_claim_hash_find(bat_priv, &search_claim);
1477
1478         if (!claim) {
1479                 /* possible optimization: race for a claim */
1480                 /* No claim exists yet, claim it for us!
1481                  */
1482                 batadv_handle_claim(bat_priv, primary_if,
1483                                     primary_if->net_dev->dev_addr,
1484                                     ethhdr->h_source, vid);
1485                 goto allow;
1486         }
1487
1488         /* if it is our own claim ... */
1489         if (batadv_compare_eth(claim->backbone_gw->orig,
1490                                primary_if->net_dev->dev_addr)) {
1491                 /* ... allow it in any case */
1492                 claim->lasttime = jiffies;
1493                 goto allow;
1494         }
1495
1496         /* if it is a broadcast ... */
1497         if (is_multicast_ether_addr(ethhdr->h_dest) && is_bcast) {
1498                 /* ... drop it. the responsible gateway is in charge.
1499                  *
1500                  * We need to check is_bcast because with the gateway
1501                  * feature, broadcasts (like DHCP requests) may be sent
1502                  * using a unicast packet type.
1503                  */
1504                 goto handled;
1505         } else {
1506                 /* seems the client considers us as its best gateway.
1507                  * send a claim and update the claim table
1508                  * immediately.
1509                  */
1510                 batadv_handle_claim(bat_priv, primary_if,
1511                                     primary_if->net_dev->dev_addr,
1512                                     ethhdr->h_source, vid);
1513                 goto allow;
1514         }
1515 allow:
1516         batadv_bla_update_own_backbone_gw(bat_priv, primary_if, vid);
1517         ret = 0;
1518         goto out;
1519
1520 handled:
1521         kfree_skb(skb);
1522         ret = 1;
1523
1524 out:
1525         if (primary_if)
1526                 batadv_hardif_free_ref(primary_if);
1527         if (claim)
1528                 batadv_claim_free_ref(claim);
1529         return ret;
1530 }
1531
1532 /**
1533  * batadv_bla_tx
1534  * @bat_priv: the bat priv with all the soft interface information
1535  * @skb: the frame to be checked
1536  * @vid: the VLAN ID of the frame
1537  *
1538  * bla_tx checks if:
1539  *  * a claim was received which has to be processed
1540  *  * the frame is allowed on the mesh
1541  *
1542  * in these cases, the skb is further handled by this function and
1543  * returns 1, otherwise it returns 0 and the caller shall further
1544  * process the skb.
1545  *
1546  * This call might reallocate skb data.
1547  */
1548 int batadv_bla_tx(struct batadv_priv *bat_priv, struct sk_buff *skb,
1549                   unsigned short vid)
1550 {
1551         struct ethhdr *ethhdr;
1552         struct batadv_bla_claim search_claim, *claim = NULL;
1553         struct batadv_hard_iface *primary_if;
1554         int ret = 0;
1555
1556         primary_if = batadv_primary_if_get_selected(bat_priv);
1557         if (!primary_if)
1558                 goto out;
1559
1560         if (!atomic_read(&bat_priv->bridge_loop_avoidance))
1561                 goto allow;
1562
1563         if (batadv_bla_process_claim(bat_priv, primary_if, skb))
1564                 goto handled;
1565
1566         ethhdr = eth_hdr(skb);
1567
1568         if (unlikely(atomic_read(&bat_priv->bla.num_requests)))
1569                 /* don't allow broadcasts while requests are in flight */
1570                 if (is_multicast_ether_addr(ethhdr->h_dest))
1571                         goto handled;
1572
1573         ether_addr_copy(search_claim.addr, ethhdr->h_source);
1574         search_claim.vid = vid;
1575
1576         claim = batadv_claim_hash_find(bat_priv, &search_claim);
1577
1578         /* if no claim exists, allow it. */
1579         if (!claim)
1580                 goto allow;
1581
1582         /* check if we are responsible. */
1583         if (batadv_compare_eth(claim->backbone_gw->orig,
1584                                primary_if->net_dev->dev_addr)) {
1585                 /* if yes, the client has roamed and we have
1586                  * to unclaim it.
1587                  */
1588                 batadv_handle_unclaim(bat_priv, primary_if,
1589                                       primary_if->net_dev->dev_addr,
1590                                       ethhdr->h_source, vid);
1591                 goto allow;
1592         }
1593
1594         /* check if it is a multicast/broadcast frame */
1595         if (is_multicast_ether_addr(ethhdr->h_dest)) {
1596                 /* drop it. the responsible gateway has forwarded it into
1597                  * the backbone network.
1598                  */
1599                 goto handled;
1600         } else {
1601                 /* we must allow it. at least if we are
1602                  * responsible for the DESTINATION.
1603                  */
1604                 goto allow;
1605         }
1606 allow:
1607         batadv_bla_update_own_backbone_gw(bat_priv, primary_if, vid);
1608         ret = 0;
1609         goto out;
1610 handled:
1611         ret = 1;
1612 out:
1613         if (primary_if)
1614                 batadv_hardif_free_ref(primary_if);
1615         if (claim)
1616                 batadv_claim_free_ref(claim);
1617         return ret;
1618 }
1619
1620 int batadv_bla_claim_table_seq_print_text(struct seq_file *seq, void *offset)
1621 {
1622         struct net_device *net_dev = (struct net_device *)seq->private;
1623         struct batadv_priv *bat_priv = netdev_priv(net_dev);
1624         struct batadv_hashtable *hash = bat_priv->bla.claim_hash;
1625         struct batadv_bla_claim *claim;
1626         struct batadv_hard_iface *primary_if;
1627         struct hlist_head *head;
1628         uint32_t i;
1629         bool is_own;
1630         uint8_t *primary_addr;
1631
1632         primary_if = batadv_seq_print_text_primary_if_get(seq);
1633         if (!primary_if)
1634                 goto out;
1635
1636         primary_addr = primary_if->net_dev->dev_addr;
1637         seq_printf(seq,
1638                    "Claims announced for the mesh %s (orig %pM, group id %#.4x)\n",
1639                    net_dev->name, primary_addr,
1640                    ntohs(bat_priv->bla.claim_dest.group));
1641         seq_printf(seq, "   %-17s    %-5s    %-17s [o] (%-6s)\n",
1642                    "Client", "VID", "Originator", "CRC");
1643         for (i = 0; i < hash->size; i++) {
1644                 head = &hash->table[i];
1645
1646                 rcu_read_lock();
1647                 hlist_for_each_entry_rcu(claim, head, hash_entry) {
1648                         is_own = batadv_compare_eth(claim->backbone_gw->orig,
1649                                                     primary_addr);
1650                         seq_printf(seq, " * %pM on %5d by %pM [%c] (%#.4x)\n",
1651                                    claim->addr, BATADV_PRINT_VID(claim->vid),
1652                                    claim->backbone_gw->orig,
1653                                    (is_own ? 'x' : ' '),
1654                                    claim->backbone_gw->crc);
1655                 }
1656                 rcu_read_unlock();
1657         }
1658 out:
1659         if (primary_if)
1660                 batadv_hardif_free_ref(primary_if);
1661         return 0;
1662 }
1663
1664 int batadv_bla_backbone_table_seq_print_text(struct seq_file *seq, void *offset)
1665 {
1666         struct net_device *net_dev = (struct net_device *)seq->private;
1667         struct batadv_priv *bat_priv = netdev_priv(net_dev);
1668         struct batadv_hashtable *hash = bat_priv->bla.backbone_hash;
1669         struct batadv_bla_backbone_gw *backbone_gw;
1670         struct batadv_hard_iface *primary_if;
1671         struct hlist_head *head;
1672         int secs, msecs;
1673         uint32_t i;
1674         bool is_own;
1675         uint8_t *primary_addr;
1676
1677         primary_if = batadv_seq_print_text_primary_if_get(seq);
1678         if (!primary_if)
1679                 goto out;
1680
1681         primary_addr = primary_if->net_dev->dev_addr;
1682         seq_printf(seq,
1683                    "Backbones announced for the mesh %s (orig %pM, group id %#.4x)\n",
1684                    net_dev->name, primary_addr,
1685                    ntohs(bat_priv->bla.claim_dest.group));
1686         seq_printf(seq, "   %-17s    %-5s %-9s (%-6s)\n",
1687                    "Originator", "VID", "last seen", "CRC");
1688         for (i = 0; i < hash->size; i++) {
1689                 head = &hash->table[i];
1690
1691                 rcu_read_lock();
1692                 hlist_for_each_entry_rcu(backbone_gw, head, hash_entry) {
1693                         msecs = jiffies_to_msecs(jiffies -
1694                                                  backbone_gw->lasttime);
1695                         secs = msecs / 1000;
1696                         msecs = msecs % 1000;
1697
1698                         is_own = batadv_compare_eth(backbone_gw->orig,
1699                                                     primary_addr);
1700                         if (is_own)
1701                                 continue;
1702
1703                         seq_printf(seq, " * %pM on %5d %4i.%03is (%#.4x)\n",
1704                                    backbone_gw->orig,
1705                                    BATADV_PRINT_VID(backbone_gw->vid), secs,
1706                                    msecs, backbone_gw->crc);
1707                 }
1708                 rcu_read_unlock();
1709         }
1710 out:
1711         if (primary_if)
1712                 batadv_hardif_free_ref(primary_if);
1713         return 0;
1714 }