net/batman-adv/bridge_loop_avoidance.c

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