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