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