net/batman-adv/bridge_loop_avoidance.c

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