net/batman-adv/translation-table.c

   1 /* Copyright (C) 2007-2012 B.A.T.M.A.N. contributors:
   2  *
   3  * Marek Lindner, Simon Wunderlich, Antonio Quartulli
   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 "translation-table.h"
  22 #include "soft-interface.h"
  23 #include "hard-interface.h"
  24 #include "send.h"
  25 #include "hash.h"
  26 #include "originator.h"
  27 #include "routing.h"
  28 #include "bridge_loop_avoidance.h"
  29
  30 #include <linux/crc16.h>
  31
  32 static void send_roam_adv(struct bat_priv *bat_priv, uint8_t *client,
  33                           struct orig_node *orig_node);
  34 static void tt_purge(struct work_struct *work);
  35 static void tt_global_del_orig_list(struct tt_global_entry *tt_global_entry);
  36
  37 /* returns 1 if they are the same mac addr */
  38 static int compare_tt(const struct hlist_node *node, const void *data2)
  39 {
  40         const void *data1 = container_of(node, struct tt_common_entry,
  41                                          hash_entry);
  42
  43         return (memcmp(data1, data2, ETH_ALEN) == 0 ? 1 : 0);
  44 }
  45
  46 static void tt_start_timer(struct bat_priv *bat_priv)
  47 {
  48         INIT_DELAYED_WORK(&bat_priv->tt_work, tt_purge);
  49         queue_delayed_work(batadv_event_workqueue, &bat_priv->tt_work,
  50                            msecs_to_jiffies(5000));
  51 }
  52
  53 static struct tt_common_entry *tt_hash_find(struct hashtable_t *hash,
  54                                             const void *data)
  55 {
  56         struct hlist_head *head;
  57         struct hlist_node *node;
  58         struct tt_common_entry *tt_common_entry, *tt_common_entry_tmp = NULL;
  59         uint32_t index;
  60
  61         if (!hash)
  62                 return NULL;
  63
  64         index = choose_orig(data, hash->size);
  65         head = &hash->table[index];
  66
  67         rcu_read_lock();
  68         hlist_for_each_entry_rcu(tt_common_entry, node, head, hash_entry) {
  69                 if (!compare_eth(tt_common_entry, data))
  70                         continue;
  71
  72                 if (!atomic_inc_not_zero(&tt_common_entry->refcount))
  73                         continue;
  74
  75                 tt_common_entry_tmp = tt_common_entry;
  76                 break;
  77         }
  78         rcu_read_unlock();
  79
  80         return tt_common_entry_tmp;
  81 }
  82
  83 static struct tt_local_entry *tt_local_hash_find(struct bat_priv *bat_priv,
  84                                                  const void *data)
  85 {
  86         struct tt_common_entry *tt_common_entry;
  87         struct tt_local_entry *tt_local_entry = NULL;
  88
  89         tt_common_entry = tt_hash_find(bat_priv->tt_local_hash, data);
  90         if (tt_common_entry)
  91                 tt_local_entry = container_of(tt_common_entry,
  92                                               struct tt_local_entry, common);
  93         return tt_local_entry;
  94 }
  95
  96 static struct tt_global_entry *tt_global_hash_find(struct bat_priv *bat_priv,
  97                                                    const void *data)
  98 {
  99         struct tt_common_entry *tt_common_entry;
 100         struct tt_global_entry *tt_global_entry = NULL;
 101
 102         tt_common_entry = tt_hash_find(bat_priv->tt_global_hash, data);
 103         if (tt_common_entry)
 104                 tt_global_entry = container_of(tt_common_entry,
 105                                                struct tt_global_entry, common);
 106         return tt_global_entry;
 107
 108 }
 109
 110 static void tt_local_entry_free_ref(struct tt_local_entry *tt_local_entry)
 111 {
 112         if (atomic_dec_and_test(&tt_local_entry->common.refcount))
 113                 kfree_rcu(tt_local_entry, common.rcu);
 114 }
 115
 116 static void tt_global_entry_free_rcu(struct rcu_head *rcu)
 117 {
 118         struct tt_common_entry *tt_common_entry;
 119         struct tt_global_entry *tt_global_entry;
 120
 121         tt_common_entry = container_of(rcu, struct tt_common_entry, rcu);
 122         tt_global_entry = container_of(tt_common_entry, struct tt_global_entry,
 123                                        common);
 124
 125         kfree(tt_global_entry);
 126 }
 127
 128 static void tt_global_entry_free_ref(struct tt_global_entry *tt_global_entry)
 129 {
 130         if (atomic_dec_and_test(&tt_global_entry->common.refcount)) {
 131                 tt_global_del_orig_list(tt_global_entry);
 132                 call_rcu(&tt_global_entry->common.rcu,
 133                          tt_global_entry_free_rcu);
 134         }
 135 }
 136
 137 static void tt_orig_list_entry_free_rcu(struct rcu_head *rcu)
 138 {
 139         struct tt_orig_list_entry *orig_entry;
 140
 141         orig_entry = container_of(rcu, struct tt_orig_list_entry, rcu);
 142         atomic_dec(&orig_entry->orig_node->tt_size);
 143         batadv_orig_node_free_ref(orig_entry->orig_node);
 144         kfree(orig_entry);
 145 }
 146
 147 static void tt_orig_list_entry_free_ref(struct tt_orig_list_entry *orig_entry)
 148 {
 149         call_rcu(&orig_entry->rcu, tt_orig_list_entry_free_rcu);
 150 }
 151
 152 static void tt_local_event(struct bat_priv *bat_priv, const uint8_t *addr,
 153                            uint8_t flags)
 154 {
 155         struct tt_change_node *tt_change_node;
 156
 157         tt_change_node = kmalloc(sizeof(*tt_change_node), GFP_ATOMIC);
 158
 159         if (!tt_change_node)
 160                 return;
 161
 162         tt_change_node->change.flags = flags;
 163         memcpy(tt_change_node->change.addr, addr, ETH_ALEN);
 164
 165         spin_lock_bh(&bat_priv->tt_changes_list_lock);
 166         /* track the change in the OGMinterval list */
 167         list_add_tail(&tt_change_node->list, &bat_priv->tt_changes_list);
 168         atomic_inc(&bat_priv->tt_local_changes);
 169         spin_unlock_bh(&bat_priv->tt_changes_list_lock);
 170
 171         atomic_set(&bat_priv->tt_ogm_append_cnt, 0);
 172 }
 173
 174 int batadv_tt_len(int changes_num)
 175 {
 176         return changes_num * sizeof(struct tt_change);
 177 }
 178
 179 static int tt_local_init(struct bat_priv *bat_priv)
 180 {
 181         if (bat_priv->tt_local_hash)
 182                 return 0;
 183
 184         bat_priv->tt_local_hash = batadv_hash_new(1024);
 185
 186         if (!bat_priv->tt_local_hash)
 187                 return -ENOMEM;
 188
 189         return 0;
 190 }
 191
 192 void batadv_tt_local_add(struct net_device *soft_iface, const uint8_t *addr,
 193                          int ifindex)
 194 {
 195         struct bat_priv *bat_priv = netdev_priv(soft_iface);
 196         struct tt_local_entry *tt_local_entry = NULL;
 197         struct tt_global_entry *tt_global_entry = NULL;
 198         struct hlist_head *head;
 199         struct hlist_node *node;
 200         struct tt_orig_list_entry *orig_entry;
 201         int hash_added;
 202
 203         tt_local_entry = tt_local_hash_find(bat_priv, addr);
 204
 205         if (tt_local_entry) {
 206                 tt_local_entry->last_seen = jiffies;
 207                 /* possibly unset the TT_CLIENT_PENDING flag */
 208                 tt_local_entry->common.flags &= ~TT_CLIENT_PENDING;
 209                 goto out;
 210         }
 211
 212         tt_local_entry = kmalloc(sizeof(*tt_local_entry), GFP_ATOMIC);
 213         if (!tt_local_entry)
 214                 goto out;
 215
 216         bat_dbg(DBG_TT, bat_priv,
 217                 "Creating new local tt entry: %pM (ttvn: %d)\n", addr,
 218                 (uint8_t)atomic_read(&bat_priv->ttvn));
 219
 220         memcpy(tt_local_entry->common.addr, addr, ETH_ALEN);
 221         tt_local_entry->common.flags = NO_FLAGS;
 222         if (batadv_is_wifi_iface(ifindex))
 223                 tt_local_entry->common.flags |= TT_CLIENT_WIFI;
 224         atomic_set(&tt_local_entry->common.refcount, 2);
 225         tt_local_entry->last_seen = jiffies;
 226
 227         /* the batman interface mac address should never be purged */
 228         if (compare_eth(addr, soft_iface->dev_addr))
 229                 tt_local_entry->common.flags |= TT_CLIENT_NOPURGE;
 230
 231         /* The local entry has to be marked as NEW to avoid to send it in
 232          * a full table response going out before the next ttvn increment
 233          * (consistency check)
 234          */
 235         tt_local_entry->common.flags |= TT_CLIENT_NEW;
 236
 237         hash_added = hash_add(bat_priv->tt_local_hash, compare_tt, choose_orig,
 238                          &tt_local_entry->common,
 239                          &tt_local_entry->common.hash_entry);
 240
 241         if (unlikely(hash_added != 0)) {
 242                 /* remove the reference for the hash */
 243                 tt_local_entry_free_ref(tt_local_entry);
 244                 goto out;
 245         }
 246
 247         tt_local_event(bat_priv, addr, tt_local_entry->common.flags);
 248
 249         /* remove address from global hash if present */
 250         tt_global_entry = tt_global_hash_find(bat_priv, addr);
 251
 252         /* Check whether it is a roaming! */
 253         if (tt_global_entry) {
 254                 /* These node are probably going to update their tt table */
 255                 head = &tt_global_entry->orig_list;
 256                 rcu_read_lock();
 257                 hlist_for_each_entry_rcu(orig_entry, node, head, list) {
 258                         orig_entry->orig_node->tt_poss_change = true;
 259
 260                         send_roam_adv(bat_priv, tt_global_entry->common.addr,
 261                                       orig_entry->orig_node);
 262                 }
 263                 rcu_read_unlock();
 264                 /* The global entry has to be marked as ROAMING and
 265                  * has to be kept for consistency purpose
 266                  */
 267                 tt_global_entry->common.flags |= TT_CLIENT_ROAM;
 268                 tt_global_entry->roam_at = jiffies;
 269         }
 270 out:
 271         if (tt_local_entry)
 272                 tt_local_entry_free_ref(tt_local_entry);
 273         if (tt_global_entry)
 274                 tt_global_entry_free_ref(tt_global_entry);
 275 }
 276
 277 static void tt_realloc_packet_buff(unsigned char **packet_buff,
 278                                    int *packet_buff_len, int min_packet_len,
 279                                    int new_packet_len)
 280 {
 281         unsigned char *new_buff;
 282
 283         new_buff = kmalloc(new_packet_len, GFP_ATOMIC);
 284
 285         /* keep old buffer if kmalloc should fail */
 286         if (new_buff) {
 287                 memcpy(new_buff, *packet_buff, min_packet_len);
 288                 kfree(*packet_buff);
 289                 *packet_buff = new_buff;
 290                 *packet_buff_len = new_packet_len;
 291         }
 292 }
 293
 294 static void tt_prepare_packet_buff(struct bat_priv *bat_priv,
 295                                    unsigned char **packet_buff,
 296                                    int *packet_buff_len, int min_packet_len)
 297 {
 298         struct hard_iface *primary_if;
 299         int req_len;
 300
 301         primary_if = batadv_primary_if_get_selected(bat_priv);
 302
 303         req_len = min_packet_len;
 304         req_len += batadv_tt_len(atomic_read(&bat_priv->tt_local_changes));
 305
 306         /* if we have too many changes for one packet don't send any
 307          * and wait for the tt table request which will be fragmented
 308          */
 309         if ((!primary_if) || (req_len > primary_if->soft_iface->mtu))
 310                 req_len = min_packet_len;
 311
 312         tt_realloc_packet_buff(packet_buff, packet_buff_len,
 313                                min_packet_len, req_len);
 314
 315         if (primary_if)
 316                 batadv_hardif_free_ref(primary_if);
 317 }
 318
 319 static int tt_changes_fill_buff(struct bat_priv *bat_priv,
 320                                 unsigned char **packet_buff,
 321                                 int *packet_buff_len, int min_packet_len)
 322 {
 323         struct tt_change_node *entry, *safe;
 324         int count = 0, tot_changes = 0, new_len;
 325         unsigned char *tt_buff;
 326
 327         tt_prepare_packet_buff(bat_priv, packet_buff,
 328                                packet_buff_len, min_packet_len);
 329
 330         new_len = *packet_buff_len - min_packet_len;
 331         tt_buff = *packet_buff + min_packet_len;
 332
 333         if (new_len > 0)
 334                 tot_changes = new_len / batadv_tt_len(1);
 335
 336         spin_lock_bh(&bat_priv->tt_changes_list_lock);
 337         atomic_set(&bat_priv->tt_local_changes, 0);
 338
 339         list_for_each_entry_safe(entry, safe, &bat_priv->tt_changes_list,
 340                                  list) {
 341                 if (count < tot_changes) {
 342                         memcpy(tt_buff + batadv_tt_len(count),
 343                                &entry->change, sizeof(struct tt_change));
 344                         count++;
 345                 }
 346                 list_del(&entry->list);
 347                 kfree(entry);
 348         }
 349         spin_unlock_bh(&bat_priv->tt_changes_list_lock);
 350
 351         /* Keep the buffer for possible tt_request */
 352         spin_lock_bh(&bat_priv->tt_buff_lock);
 353         kfree(bat_priv->tt_buff);
 354         bat_priv->tt_buff_len = 0;
 355         bat_priv->tt_buff = NULL;
 356         /* check whether this new OGM has no changes due to size problems */
 357         if (new_len > 0) {
 358                 /* if kmalloc() fails we will reply with the full table
 359                  * instead of providing the diff
 360                  */
 361                 bat_priv->tt_buff = kmalloc(new_len, GFP_ATOMIC);
 362                 if (bat_priv->tt_buff) {
 363                         memcpy(bat_priv->tt_buff, tt_buff, new_len);
 364                         bat_priv->tt_buff_len = new_len;
 365                 }
 366         }
 367         spin_unlock_bh(&bat_priv->tt_buff_lock);
 368
 369         return count;
 370 }
 371
 372 int batadv_tt_local_seq_print_text(struct seq_file *seq, void *offset)
 373 {
 374         struct net_device *net_dev = (struct net_device *)seq->private;
 375         struct bat_priv *bat_priv = netdev_priv(net_dev);
 376         struct hashtable_t *hash = bat_priv->tt_local_hash;
 377         struct tt_common_entry *tt_common_entry;
 378         struct hard_iface *primary_if;
 379         struct hlist_node *node;
 380         struct hlist_head *head;
 381         uint32_t i;
 382         int ret = 0;
 383
 384         primary_if = batadv_primary_if_get_selected(bat_priv);
 385         if (!primary_if) {
 386                 ret = seq_printf(seq,
 387                                  "BATMAN mesh %s disabled - please specify interfaces to enable it\n",
 388                                  net_dev->name);
 389                 goto out;
 390         }
 391
 392         if (primary_if->if_status != IF_ACTIVE) {
 393                 ret = seq_printf(seq,
 394                                  "BATMAN mesh %s disabled - primary interface not active\n",
 395                                  net_dev->name);
 396                 goto out;
 397         }
 398
 399         seq_printf(seq,
 400                    "Locally retrieved addresses (from %s) announced via TT (TTVN: %u):\n",
 401                    net_dev->name, (uint8_t)atomic_read(&bat_priv->ttvn));
 402
 403         for (i = 0; i < hash->size; i++) {
 404                 head = &hash->table[i];
 405
 406                 rcu_read_lock();
 407                 hlist_for_each_entry_rcu(tt_common_entry, node,
 408                                          head, hash_entry) {
 409                         seq_printf(seq, " * %pM [%c%c%c%c%c]\n",
 410                                    tt_common_entry->addr,
 411                                    (tt_common_entry->flags &
 412                                     TT_CLIENT_ROAM ? 'R' : '.'),
 413                                    (tt_common_entry->flags &
 414                                     TT_CLIENT_NOPURGE ? 'P' : '.'),
 415                                    (tt_common_entry->flags &
 416                                     TT_CLIENT_NEW ? 'N' : '.'),
 417                                    (tt_common_entry->flags &
 418                                     TT_CLIENT_PENDING ? 'X' : '.'),
 419                                    (tt_common_entry->flags &
 420                                     TT_CLIENT_WIFI ? 'W' : '.'));
 421                 }
 422                 rcu_read_unlock();
 423         }
 424 out:
 425         if (primary_if)
 426                 batadv_hardif_free_ref(primary_if);
 427         return ret;
 428 }
 429
 430 static void tt_local_set_pending(struct bat_priv *bat_priv,
 431                                  struct tt_local_entry *tt_local_entry,
 432                                  uint16_t flags, const char *message)
 433 {
 434         tt_local_event(bat_priv, tt_local_entry->common.addr,
 435                        tt_local_entry->common.flags | flags);
 436
 437         /* The local client has to be marked as "pending to be removed" but has
 438          * to be kept in the table in order to send it in a full table
 439          * response issued before the net ttvn increment (consistency check)
 440          */
 441         tt_local_entry->common.flags |= TT_CLIENT_PENDING;
 442
 443         bat_dbg(DBG_TT, bat_priv,
 444                 "Local tt entry (%pM) pending to be removed: %s\n",
 445                 tt_local_entry->common.addr, message);
 446 }
 447
 448 void batadv_tt_local_remove(struct bat_priv *bat_priv, const uint8_t *addr,
 449                             const char *message, bool roaming)
 450 {
 451         struct tt_local_entry *tt_local_entry = NULL;
 452
 453         tt_local_entry = tt_local_hash_find(bat_priv, addr);
 454         if (!tt_local_entry)
 455                 goto out;
 456
 457         tt_local_set_pending(bat_priv, tt_local_entry, TT_CLIENT_DEL |
 458                              (roaming ? TT_CLIENT_ROAM : NO_FLAGS), message);
 459 out:
 460         if (tt_local_entry)
 461                 tt_local_entry_free_ref(tt_local_entry);
 462 }
 463
 464 static void tt_local_purge(struct bat_priv *bat_priv)
 465 {
 466         struct hashtable_t *hash = bat_priv->tt_local_hash;
 467         struct tt_local_entry *tt_local_entry;
 468         struct tt_common_entry *tt_common_entry;
 469         struct hlist_node *node, *node_tmp;
 470         struct hlist_head *head;
 471         spinlock_t *list_lock; /* protects write access to the hash lists */
 472         uint32_t i;
 473
 474         for (i = 0; i < hash->size; i++) {
 475                 head = &hash->table[i];
 476                 list_lock = &hash->list_locks[i];
 477
 478                 spin_lock_bh(list_lock);
 479                 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
 480                                           head, hash_entry) {
 481                         tt_local_entry = container_of(tt_common_entry,
 482                                                       struct tt_local_entry,
 483                                                       common);
 484                         if (tt_local_entry->common.flags & TT_CLIENT_NOPURGE)
 485                                 continue;
 486
 487                         /* entry already marked for deletion */
 488                         if (tt_local_entry->common.flags & TT_CLIENT_PENDING)
 489                                 continue;
 490
 491                         if (!has_timed_out(tt_local_entry->last_seen,
 492                                            TT_LOCAL_TIMEOUT))
 493                                 continue;
 494
 495                         tt_local_set_pending(bat_priv, tt_local_entry,
 496                                              TT_CLIENT_DEL, "timed out");
 497                 }
 498                 spin_unlock_bh(list_lock);
 499         }
 500
 501 }
 502
 503 static void tt_local_table_free(struct bat_priv *bat_priv)
 504 {
 505         struct hashtable_t *hash;
 506         spinlock_t *list_lock; /* protects write access to the hash lists */
 507         struct tt_common_entry *tt_common_entry;
 508         struct tt_local_entry *tt_local_entry;
 509         struct hlist_node *node, *node_tmp;
 510         struct hlist_head *head;
 511         uint32_t i;
 512
 513         if (!bat_priv->tt_local_hash)
 514                 return;
 515
 516         hash = bat_priv->tt_local_hash;
 517
 518         for (i = 0; i < hash->size; i++) {
 519                 head = &hash->table[i];
 520                 list_lock = &hash->list_locks[i];
 521
 522                 spin_lock_bh(list_lock);
 523                 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
 524                                           head, hash_entry) {
 525                         hlist_del_rcu(node);
 526                         tt_local_entry = container_of(tt_common_entry,
 527                                                       struct tt_local_entry,
 528                                                       common);
 529                         tt_local_entry_free_ref(tt_local_entry);
 530                 }
 531                 spin_unlock_bh(list_lock);
 532         }
 533
 534         batadv_hash_destroy(hash);
 535
 536         bat_priv->tt_local_hash = NULL;
 537 }
 538
 539 static int tt_global_init(struct bat_priv *bat_priv)
 540 {
 541         if (bat_priv->tt_global_hash)
 542                 return 0;
 543
 544         bat_priv->tt_global_hash = batadv_hash_new(1024);
 545
 546         if (!bat_priv->tt_global_hash)
 547                 return -ENOMEM;
 548
 549         return 0;
 550 }
 551
 552 static void tt_changes_list_free(struct bat_priv *bat_priv)
 553 {
 554         struct tt_change_node *entry, *safe;
 555
 556         spin_lock_bh(&bat_priv->tt_changes_list_lock);
 557
 558         list_for_each_entry_safe(entry, safe, &bat_priv->tt_changes_list,
 559                                  list) {
 560                 list_del(&entry->list);
 561                 kfree(entry);
 562         }
 563
 564         atomic_set(&bat_priv->tt_local_changes, 0);
 565         spin_unlock_bh(&bat_priv->tt_changes_list_lock);
 566 }
 567
 568 /* find out if an orig_node is already in the list of a tt_global_entry.
 569  * returns 1 if found, 0 otherwise
 570  */
 571 static bool tt_global_entry_has_orig(const struct tt_global_entry *entry,
 572                                      const struct orig_node *orig_node)
 573 {
 574         struct tt_orig_list_entry *tmp_orig_entry;
 575         const struct hlist_head *head;
 576         struct hlist_node *node;
 577         bool found = false;
 578
 579         rcu_read_lock();
 580         head = &entry->orig_list;
 581         hlist_for_each_entry_rcu(tmp_orig_entry, node, head, list) {
 582                 if (tmp_orig_entry->orig_node == orig_node) {
 583                         found = true;
 584                         break;
 585                 }
 586         }
 587         rcu_read_unlock();
 588         return found;
 589 }
 590
 591 static void tt_global_add_orig_entry(struct tt_global_entry *tt_global_entry,
 592                                      struct orig_node *orig_node,
 593                                      int ttvn)
 594 {
 595         struct tt_orig_list_entry *orig_entry;
 596
 597         orig_entry = kzalloc(sizeof(*orig_entry), GFP_ATOMIC);
 598         if (!orig_entry)
 599                 return;
 600
 601         INIT_HLIST_NODE(&orig_entry->list);
 602         atomic_inc(&orig_node->refcount);
 603         atomic_inc(&orig_node->tt_size);
 604         orig_entry->orig_node = orig_node;
 605         orig_entry->ttvn = ttvn;
 606
 607         spin_lock_bh(&tt_global_entry->list_lock);
 608         hlist_add_head_rcu(&orig_entry->list,
 609                            &tt_global_entry->orig_list);
 610         spin_unlock_bh(&tt_global_entry->list_lock);
 611 }
 612
 613 /* caller must hold orig_node refcount */
 614 int batadv_tt_global_add(struct bat_priv *bat_priv, struct orig_node *orig_node,
 615                          const unsigned char *tt_addr, uint8_t ttvn,
 616                          bool roaming, bool wifi)
 617 {
 618         struct tt_global_entry *tt_global_entry = NULL;
 619         int ret = 0;
 620         int hash_added;
 621
 622         tt_global_entry = tt_global_hash_find(bat_priv, tt_addr);
 623
 624         if (!tt_global_entry) {
 625                 tt_global_entry = kzalloc(sizeof(*tt_global_entry),
 626                                           GFP_ATOMIC);
 627                 if (!tt_global_entry)
 628                         goto out;
 629
 630                 memcpy(tt_global_entry->common.addr, tt_addr, ETH_ALEN);
 631
 632                 tt_global_entry->common.flags = NO_FLAGS;
 633                 tt_global_entry->roam_at = 0;
 634                 atomic_set(&tt_global_entry->common.refcount, 2);
 635
 636                 INIT_HLIST_HEAD(&tt_global_entry->orig_list);
 637                 spin_lock_init(&tt_global_entry->list_lock);
 638
 639                 hash_added = hash_add(bat_priv->tt_global_hash, compare_tt,
 640                                  choose_orig, &tt_global_entry->common,
 641                                  &tt_global_entry->common.hash_entry);
 642
 643                 if (unlikely(hash_added != 0)) {
 644                         /* remove the reference for the hash */
 645                         tt_global_entry_free_ref(tt_global_entry);
 646                         goto out_remove;
 647                 }
 648
 649                 tt_global_add_orig_entry(tt_global_entry, orig_node, ttvn);
 650         } else {
 651                 /* there is already a global entry, use this one. */
 652
 653                 /* If there is the TT_CLIENT_ROAM flag set, there is only one
 654                  * originator left in the list and we previously received a
 655                  * delete + roaming change for this originator.
 656                  *
 657                  * We should first delete the old originator before adding the
 658                  * new one.
 659                  */
 660                 if (tt_global_entry->common.flags & TT_CLIENT_ROAM) {
 661                         tt_global_del_orig_list(tt_global_entry);
 662                         tt_global_entry->common.flags &= ~TT_CLIENT_ROAM;
 663                         tt_global_entry->roam_at = 0;
 664                 }
 665
 666                 if (!tt_global_entry_has_orig(tt_global_entry, orig_node))
 667                         tt_global_add_orig_entry(tt_global_entry, orig_node,
 668                                                  ttvn);
 669         }
 670
 671         if (wifi)
 672                 tt_global_entry->common.flags |= TT_CLIENT_WIFI;
 673
 674         bat_dbg(DBG_TT, bat_priv,
 675                 "Creating new global tt entry: %pM (via %pM)\n",
 676                 tt_global_entry->common.addr, orig_node->orig);
 677
 678 out_remove:
 679         /* remove address from local hash if present */
 680         batadv_tt_local_remove(bat_priv, tt_global_entry->common.addr,
 681                                "global tt received", roaming);
 682         ret = 1;
 683 out:
 684         if (tt_global_entry)
 685                 tt_global_entry_free_ref(tt_global_entry);
 686         return ret;
 687 }
 688
 689 /* print all orig nodes who announce the address for this global entry.
 690  * it is assumed that the caller holds rcu_read_lock();
 691  */
 692 static void tt_global_print_entry(struct tt_global_entry *tt_global_entry,
 693                                   struct seq_file *seq)
 694 {
 695         struct hlist_head *head;
 696         struct hlist_node *node;
 697         struct tt_orig_list_entry *orig_entry;
 698         struct tt_common_entry *tt_common_entry;
 699         uint16_t flags;
 700         uint8_t last_ttvn;
 701
 702         tt_common_entry = &tt_global_entry->common;
 703
 704         head = &tt_global_entry->orig_list;
 705
 706         hlist_for_each_entry_rcu(orig_entry, node, head, list) {
 707                 flags = tt_common_entry->flags;
 708                 last_ttvn = atomic_read(&orig_entry->orig_node->last_ttvn);
 709                 seq_printf(seq, " * %pM  (%3u) via %pM     (%3u)   [%c%c]\n",
 710                            tt_global_entry->common.addr, orig_entry->ttvn,
 711                            orig_entry->orig_node->orig, last_ttvn,
 712                            (flags & TT_CLIENT_ROAM ? 'R' : '.'),
 713                            (flags & TT_CLIENT_WIFI ? 'W' : '.'));
 714         }
 715 }
 716
 717 int batadv_tt_global_seq_print_text(struct seq_file *seq, void *offset)
 718 {
 719         struct net_device *net_dev = (struct net_device *)seq->private;
 720         struct bat_priv *bat_priv = netdev_priv(net_dev);
 721         struct hashtable_t *hash = bat_priv->tt_global_hash;
 722         struct tt_common_entry *tt_common_entry;
 723         struct tt_global_entry *tt_global_entry;
 724         struct hard_iface *primary_if;
 725         struct hlist_node *node;
 726         struct hlist_head *head;
 727         uint32_t i;
 728         int ret = 0;
 729
 730         primary_if = batadv_primary_if_get_selected(bat_priv);
 731         if (!primary_if) {
 732                 ret = seq_printf(seq,
 733                                  "BATMAN mesh %s disabled - please specify interfaces to enable it\n",
 734                                  net_dev->name);
 735                 goto out;
 736         }
 737
 738         if (primary_if->if_status != IF_ACTIVE) {
 739                 ret = seq_printf(seq,
 740                                  "BATMAN mesh %s disabled - primary interface not active\n",
 741                                  net_dev->name);
 742                 goto out;
 743         }
 744
 745         seq_printf(seq,
 746                    "Globally announced TT entries received via the mesh %s\n",
 747                    net_dev->name);
 748         seq_printf(seq, "       %-13s %s       %-15s %s %s\n",
 749                    "Client", "(TTVN)", "Originator", "(Curr TTVN)", "Flags");
 750
 751         for (i = 0; i < hash->size; i++) {
 752                 head = &hash->table[i];
 753
 754                 rcu_read_lock();
 755                 hlist_for_each_entry_rcu(tt_common_entry, node,
 756                                          head, hash_entry) {
 757                         tt_global_entry = container_of(tt_common_entry,
 758                                                        struct tt_global_entry,
 759                                                        common);
 760                         tt_global_print_entry(tt_global_entry, seq);
 761                 }
 762                 rcu_read_unlock();
 763         }
 764 out:
 765         if (primary_if)
 766                 batadv_hardif_free_ref(primary_if);
 767         return ret;
 768 }
 769
 770 /* deletes the orig list of a tt_global_entry */
 771 static void tt_global_del_orig_list(struct tt_global_entry *tt_global_entry)
 772 {
 773         struct hlist_head *head;
 774         struct hlist_node *node, *safe;
 775         struct tt_orig_list_entry *orig_entry;
 776
 777         spin_lock_bh(&tt_global_entry->list_lock);
 778         head = &tt_global_entry->orig_list;
 779         hlist_for_each_entry_safe(orig_entry, node, safe, head, list) {
 780                 hlist_del_rcu(node);
 781                 tt_orig_list_entry_free_ref(orig_entry);
 782         }
 783         spin_unlock_bh(&tt_global_entry->list_lock);
 784
 785 }
 786
 787 static void tt_global_del_orig_entry(struct bat_priv *bat_priv,
 788                                      struct tt_global_entry *tt_global_entry,
 789                                      struct orig_node *orig_node,
 790                                      const char *message)
 791 {
 792         struct hlist_head *head;
 793         struct hlist_node *node, *safe;
 794         struct tt_orig_list_entry *orig_entry;
 795
 796         spin_lock_bh(&tt_global_entry->list_lock);
 797         head = &tt_global_entry->orig_list;
 798         hlist_for_each_entry_safe(orig_entry, node, safe, head, list) {
 799                 if (orig_entry->orig_node == orig_node) {
 800                         bat_dbg(DBG_TT, bat_priv,
 801                                 "Deleting %pM from global tt entry %pM: %s\n",
 802                                 orig_node->orig, tt_global_entry->common.addr,
 803                                 message);
 804                         hlist_del_rcu(node);
 805                         tt_orig_list_entry_free_ref(orig_entry);
 806                 }
 807         }
 808         spin_unlock_bh(&tt_global_entry->list_lock);
 809 }
 810
 811 static void tt_global_del_struct(struct bat_priv *bat_priv,
 812                                  struct tt_global_entry *tt_global_entry,
 813                                  const char *message)
 814 {
 815         bat_dbg(DBG_TT, bat_priv,
 816                 "Deleting global tt entry %pM: %s\n",
 817                 tt_global_entry->common.addr, message);
 818
 819         hash_remove(bat_priv->tt_global_hash, compare_tt, choose_orig,
 820                     tt_global_entry->common.addr);
 821         tt_global_entry_free_ref(tt_global_entry);
 822
 823 }
 824
 825 /* If the client is to be deleted, we check if it is the last origantor entry
 826  * within tt_global entry. If yes, we set the TT_CLIENT_ROAM flag and the timer,
 827  * otherwise we simply remove the originator scheduled for deletion.
 828  */
 829 static void tt_global_del_roaming(struct bat_priv *bat_priv,
 830                                   struct tt_global_entry *tt_global_entry,
 831                                   struct orig_node *orig_node,
 832                                   const char *message)
 833 {
 834         bool last_entry = true;
 835         struct hlist_head *head;
 836         struct hlist_node *node;
 837         struct tt_orig_list_entry *orig_entry;
 838
 839         /* no local entry exists, case 1:
 840          * Check if this is the last one or if other entries exist.
 841          */
 842
 843         rcu_read_lock();
 844         head = &tt_global_entry->orig_list;
 845         hlist_for_each_entry_rcu(orig_entry, node, head, list) {
 846                 if (orig_entry->orig_node != orig_node) {
 847                         last_entry = false;
 848                         break;
 849                 }
 850         }
 851         rcu_read_unlock();
 852
 853         if (last_entry) {
 854                 /* its the last one, mark for roaming. */
 855                 tt_global_entry->common.flags |= TT_CLIENT_ROAM;
 856                 tt_global_entry->roam_at = jiffies;
 857         } else
 858                 /* there is another entry, we can simply delete this
 859                  * one and can still use the other one.
 860                  */
 861                 tt_global_del_orig_entry(bat_priv, tt_global_entry,
 862                                          orig_node, message);
 863 }
 864
 865
 866
 867 static void tt_global_del(struct bat_priv *bat_priv,
 868                           struct orig_node *orig_node,
 869                           const unsigned char *addr,
 870                           const char *message, bool roaming)
 871 {
 872         struct tt_global_entry *tt_global_entry = NULL;
 873         struct tt_local_entry *tt_local_entry = NULL;
 874
 875         tt_global_entry = tt_global_hash_find(bat_priv, addr);
 876         if (!tt_global_entry)
 877                 goto out;
 878
 879         if (!roaming) {
 880                 tt_global_del_orig_entry(bat_priv, tt_global_entry, orig_node,
 881                                          message);
 882
 883                 if (hlist_empty(&tt_global_entry->orig_list))
 884                         tt_global_del_struct(bat_priv, tt_global_entry,
 885                                              message);
 886
 887                 goto out;
 888         }
 889
 890         /* if we are deleting a global entry due to a roam
 891          * event, there are two possibilities:
 892          * 1) the client roamed from node A to node B => if there
 893          *    is only one originator left for this client, we mark
 894          *    it with TT_CLIENT_ROAM, we start a timer and we
 895          *    wait for node B to claim it. In case of timeout
 896          *    the entry is purged.
 897          *
 898          *    If there are other originators left, we directly delete
 899          *    the originator.
 900          * 2) the client roamed to us => we can directly delete
 901          *    the global entry, since it is useless now.
 902          */
 903         tt_local_entry = tt_local_hash_find(bat_priv,
 904                                             tt_global_entry->common.addr);
 905         if (tt_local_entry) {
 906                 /* local entry exists, case 2: client roamed to us. */
 907                 tt_global_del_orig_list(tt_global_entry);
 908                 tt_global_del_struct(bat_priv, tt_global_entry, message);
 909         } else
 910                 /* no local entry exists, case 1: check for roaming */
 911                 tt_global_del_roaming(bat_priv, tt_global_entry, orig_node,
 912                                       message);
 913
 914
 915 out:
 916         if (tt_global_entry)
 917                 tt_global_entry_free_ref(tt_global_entry);
 918         if (tt_local_entry)
 919                 tt_local_entry_free_ref(tt_local_entry);
 920 }
 921
 922 void batadv_tt_global_del_orig(struct bat_priv *bat_priv,
 923                                struct orig_node *orig_node, const char *message)
 924 {
 925         struct tt_global_entry *tt_global_entry;
 926         struct tt_common_entry *tt_common_entry;
 927         uint32_t i;
 928         struct hashtable_t *hash = bat_priv->tt_global_hash;
 929         struct hlist_node *node, *safe;
 930         struct hlist_head *head;
 931         spinlock_t *list_lock; /* protects write access to the hash lists */
 932
 933         if (!hash)
 934                 return;
 935
 936         for (i = 0; i < hash->size; i++) {
 937                 head = &hash->table[i];
 938                 list_lock = &hash->list_locks[i];
 939
 940                 spin_lock_bh(list_lock);
 941                 hlist_for_each_entry_safe(tt_common_entry, node, safe,
 942                                           head, hash_entry) {
 943                         tt_global_entry = container_of(tt_common_entry,
 944                                                        struct tt_global_entry,
 945                                                        common);
 946
 947                         tt_global_del_orig_entry(bat_priv, tt_global_entry,
 948                                                  orig_node, message);
 949
 950                         if (hlist_empty(&tt_global_entry->orig_list)) {
 951                                 bat_dbg(DBG_TT, bat_priv,
 952                                         "Deleting global tt entry %pM: %s\n",
 953                                         tt_global_entry->common.addr,
 954                                         message);
 955                                 hlist_del_rcu(node);
 956                                 tt_global_entry_free_ref(tt_global_entry);
 957                         }
 958                 }
 959                 spin_unlock_bh(list_lock);
 960         }
 961         atomic_set(&orig_node->tt_size, 0);
 962         orig_node->tt_initialised = false;
 963 }
 964
 965 static void tt_global_roam_purge(struct bat_priv *bat_priv)
 966 {
 967         struct hashtable_t *hash = bat_priv->tt_global_hash;
 968         struct tt_common_entry *tt_common_entry;
 969         struct tt_global_entry *tt_global_entry;
 970         struct hlist_node *node, *node_tmp;
 971         struct hlist_head *head;
 972         spinlock_t *list_lock; /* protects write access to the hash lists */
 973         uint32_t i;
 974
 975         for (i = 0; i < hash->size; i++) {
 976                 head = &hash->table[i];
 977                 list_lock = &hash->list_locks[i];
 978
 979                 spin_lock_bh(list_lock);
 980                 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
 981                                           head, hash_entry) {
 982                         tt_global_entry = container_of(tt_common_entry,
 983                                                        struct tt_global_entry,
 984                                                        common);
 985                         if (!(tt_global_entry->common.flags & TT_CLIENT_ROAM))
 986                                 continue;
 987                         if (!has_timed_out(tt_global_entry->roam_at,
 988                                            TT_CLIENT_ROAM_TIMEOUT))
 989                                 continue;
 990
 991                         bat_dbg(DBG_TT, bat_priv,
 992                                 "Deleting global tt entry (%pM): Roaming timeout\n",
 993                                 tt_global_entry->common.addr);
 994
 995                         hlist_del_rcu(node);
 996                         tt_global_entry_free_ref(tt_global_entry);
 997                 }
 998                 spin_unlock_bh(list_lock);
 999         }
1000
1001 }
1002
1003 static void tt_global_table_free(struct bat_priv *bat_priv)
1004 {
1005         struct hashtable_t *hash;
1006         spinlock_t *list_lock; /* protects write access to the hash lists */
1007         struct tt_common_entry *tt_common_entry;
1008         struct tt_global_entry *tt_global_entry;
1009         struct hlist_node *node, *node_tmp;
1010         struct hlist_head *head;
1011         uint32_t i;
1012
1013         if (!bat_priv->tt_global_hash)
1014                 return;
1015
1016         hash = bat_priv->tt_global_hash;
1017
1018         for (i = 0; i < hash->size; i++) {
1019                 head = &hash->table[i];
1020                 list_lock = &hash->list_locks[i];
1021
1022                 spin_lock_bh(list_lock);
1023                 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
1024                                           head, hash_entry) {
1025                         hlist_del_rcu(node);
1026                         tt_global_entry = container_of(tt_common_entry,
1027                                                        struct tt_global_entry,
1028                                                        common);
1029                         tt_global_entry_free_ref(tt_global_entry);
1030                 }
1031                 spin_unlock_bh(list_lock);
1032         }
1033
1034         batadv_hash_destroy(hash);
1035
1036         bat_priv->tt_global_hash = NULL;
1037 }
1038
1039 static bool _is_ap_isolated(struct tt_local_entry *tt_local_entry,
1040                             struct tt_global_entry *tt_global_entry)
1041 {
1042         bool ret = false;
1043
1044         if (tt_local_entry->common.flags & TT_CLIENT_WIFI &&
1045             tt_global_entry->common.flags & TT_CLIENT_WIFI)
1046                 ret = true;
1047
1048         return ret;
1049 }
1050
1051 struct orig_node *batadv_transtable_search(struct bat_priv *bat_priv,
1052                                            const uint8_t *src,
1053                                            const uint8_t *addr)
1054 {
1055         struct tt_local_entry *tt_local_entry = NULL;
1056         struct tt_global_entry *tt_global_entry = NULL;
1057         struct orig_node *orig_node = NULL;
1058         struct neigh_node *router = NULL;
1059         struct hlist_head *head;
1060         struct hlist_node *node;
1061         struct tt_orig_list_entry *orig_entry;
1062         int best_tq;
1063
1064         if (src && atomic_read(&bat_priv->ap_isolation)) {
1065                 tt_local_entry = tt_local_hash_find(bat_priv, src);
1066                 if (!tt_local_entry)
1067                         goto out;
1068         }
1069
1070         tt_global_entry = tt_global_hash_find(bat_priv, addr);
1071         if (!tt_global_entry)
1072                 goto out;
1073
1074         /* check whether the clients should not communicate due to AP
1075          * isolation
1076          */
1077         if (tt_local_entry && _is_ap_isolated(tt_local_entry, tt_global_entry))
1078                 goto out;
1079
1080         best_tq = 0;
1081
1082         rcu_read_lock();
1083         head = &tt_global_entry->orig_list;
1084         hlist_for_each_entry_rcu(orig_entry, node, head, list) {
1085                 router = batadv_orig_node_get_router(orig_entry->orig_node);
1086                 if (!router)
1087                         continue;
1088
1089                 if (router->tq_avg > best_tq) {
1090                         orig_node = orig_entry->orig_node;
1091                         best_tq = router->tq_avg;
1092                 }
1093                 batadv_neigh_node_free_ref(router);
1094         }
1095         /* found anything? */
1096         if (orig_node && !atomic_inc_not_zero(&orig_node->refcount))
1097                 orig_node = NULL;
1098         rcu_read_unlock();
1099 out:
1100         if (tt_global_entry)
1101                 tt_global_entry_free_ref(tt_global_entry);
1102         if (tt_local_entry)
1103                 tt_local_entry_free_ref(tt_local_entry);
1104
1105         return orig_node;
1106 }
1107
1108 /* Calculates the checksum of the local table of a given orig_node */
1109 static uint16_t tt_global_crc(struct bat_priv *bat_priv,
1110                               struct orig_node *orig_node)
1111 {
1112         uint16_t total = 0, total_one;
1113         struct hashtable_t *hash = bat_priv->tt_global_hash;
1114         struct tt_common_entry *tt_common_entry;
1115         struct tt_global_entry *tt_global_entry;
1116         struct hlist_node *node;
1117         struct hlist_head *head;
1118         uint32_t i;
1119         int j;
1120
1121         for (i = 0; i < hash->size; i++) {
1122                 head = &hash->table[i];
1123
1124                 rcu_read_lock();
1125                 hlist_for_each_entry_rcu(tt_common_entry, node,
1126                                          head, hash_entry) {
1127                         tt_global_entry = container_of(tt_common_entry,
1128                                                        struct tt_global_entry,
1129                                                        common);
1130                         /* Roaming clients are in the global table for
1131                          * consistency only. They don't have to be
1132                          * taken into account while computing the
1133                          * global crc
1134                          */
1135                         if (tt_global_entry->common.flags & TT_CLIENT_ROAM)
1136                                 continue;
1137
1138                         /* find out if this global entry is announced by this
1139                          * originator
1140                          */
1141                         if (!tt_global_entry_has_orig(tt_global_entry,
1142                                                       orig_node))
1143                                 continue;
1144
1145                         total_one = 0;
1146                         for (j = 0; j < ETH_ALEN; j++)
1147                                 total_one = crc16_byte(total_one,
1148                                         tt_global_entry->common.addr[j]);
1149                         total ^= total_one;
1150                 }
1151                 rcu_read_unlock();
1152         }
1153
1154         return total;
1155 }
1156
1157 /* Calculates the checksum of the local table */
1158 static uint16_t batadv_tt_local_crc(struct bat_priv *bat_priv)
1159 {
1160         uint16_t total = 0, total_one;
1161         struct hashtable_t *hash = bat_priv->tt_local_hash;
1162         struct tt_common_entry *tt_common_entry;
1163         struct hlist_node *node;
1164         struct hlist_head *head;
1165         uint32_t i;
1166         int j;
1167
1168         for (i = 0; i < hash->size; i++) {
1169                 head = &hash->table[i];
1170
1171                 rcu_read_lock();
1172                 hlist_for_each_entry_rcu(tt_common_entry, node,
1173                                          head, hash_entry) {
1174                         /* not yet committed clients have not to be taken into
1175                          * account while computing the CRC
1176                          */
1177                         if (tt_common_entry->flags & TT_CLIENT_NEW)
1178                                 continue;
1179                         total_one = 0;
1180                         for (j = 0; j < ETH_ALEN; j++)
1181                                 total_one = crc16_byte(total_one,
1182                                                    tt_common_entry->addr[j]);
1183                         total ^= total_one;
1184                 }
1185                 rcu_read_unlock();
1186         }
1187
1188         return total;
1189 }
1190
1191 static void tt_req_list_free(struct bat_priv *bat_priv)
1192 {
1193         struct tt_req_node *node, *safe;
1194
1195         spin_lock_bh(&bat_priv->tt_req_list_lock);
1196
1197         list_for_each_entry_safe(node, safe, &bat_priv->tt_req_list, list) {
1198                 list_del(&node->list);
1199                 kfree(node);
1200         }
1201
1202         spin_unlock_bh(&bat_priv->tt_req_list_lock);
1203 }
1204
1205 static void tt_save_orig_buffer(struct bat_priv *bat_priv,
1206                                 struct orig_node *orig_node,
1207                                 const unsigned char *tt_buff,
1208                                 uint8_t tt_num_changes)
1209 {
1210         uint16_t tt_buff_len = batadv_tt_len(tt_num_changes);
1211
1212         /* Replace the old buffer only if I received something in the
1213          * last OGM (the OGM could carry no changes)
1214          */
1215         spin_lock_bh(&orig_node->tt_buff_lock);
1216         if (tt_buff_len > 0) {
1217                 kfree(orig_node->tt_buff);
1218                 orig_node->tt_buff_len = 0;
1219                 orig_node->tt_buff = kmalloc(tt_buff_len, GFP_ATOMIC);
1220                 if (orig_node->tt_buff) {
1221                         memcpy(orig_node->tt_buff, tt_buff, tt_buff_len);
1222                         orig_node->tt_buff_len = tt_buff_len;
1223                 }
1224         }
1225         spin_unlock_bh(&orig_node->tt_buff_lock);
1226 }
1227
1228 static void tt_req_purge(struct bat_priv *bat_priv)
1229 {
1230         struct tt_req_node *node, *safe;
1231
1232         spin_lock_bh(&bat_priv->tt_req_list_lock);
1233         list_for_each_entry_safe(node, safe, &bat_priv->tt_req_list, list) {
1234                 if (has_timed_out(node->issued_at, TT_REQUEST_TIMEOUT)) {
1235                         list_del(&node->list);
1236                         kfree(node);
1237                 }
1238         }
1239         spin_unlock_bh(&bat_priv->tt_req_list_lock);
1240 }
1241
1242 /* returns the pointer to the new tt_req_node struct if no request
1243  * has already been issued for this orig_node, NULL otherwise
1244  */
1245 static struct tt_req_node *new_tt_req_node(struct bat_priv *bat_priv,
1246                                           struct orig_node *orig_node)
1247 {
1248         struct tt_req_node *tt_req_node_tmp, *tt_req_node = NULL;
1249
1250         spin_lock_bh(&bat_priv->tt_req_list_lock);
1251         list_for_each_entry(tt_req_node_tmp, &bat_priv->tt_req_list, list) {
1252                 if (compare_eth(tt_req_node_tmp, orig_node) &&
1253                     !has_timed_out(tt_req_node_tmp->issued_at,
1254                                    TT_REQUEST_TIMEOUT))
1255                         goto unlock;
1256         }
1257
1258         tt_req_node = kmalloc(sizeof(*tt_req_node), GFP_ATOMIC);
1259         if (!tt_req_node)
1260                 goto unlock;
1261
1262         memcpy(tt_req_node->addr, orig_node->orig, ETH_ALEN);
1263         tt_req_node->issued_at = jiffies;
1264
1265         list_add(&tt_req_node->list, &bat_priv->tt_req_list);
1266 unlock:
1267         spin_unlock_bh(&bat_priv->tt_req_list_lock);
1268         return tt_req_node;
1269 }
1270
1271 /* data_ptr is useless here, but has to be kept to respect the prototype */
1272 static int tt_local_valid_entry(const void *entry_ptr, const void *data_ptr)
1273 {
1274         const struct tt_common_entry *tt_common_entry = entry_ptr;
1275
1276         if (tt_common_entry->flags & TT_CLIENT_NEW)
1277                 return 0;
1278         return 1;
1279 }
1280
1281 static int tt_global_valid_entry(const void *entry_ptr, const void *data_ptr)
1282 {
1283         const struct tt_common_entry *tt_common_entry = entry_ptr;
1284         const struct tt_global_entry *tt_global_entry;
1285         const struct orig_node *orig_node = data_ptr;
1286
1287         if (tt_common_entry->flags & TT_CLIENT_ROAM)
1288                 return 0;
1289
1290         tt_global_entry = container_of(tt_common_entry, struct tt_global_entry,
1291                                        common);
1292
1293         return tt_global_entry_has_orig(tt_global_entry, orig_node);
1294 }
1295
1296 static struct sk_buff *tt_response_fill_table(uint16_t tt_len, uint8_t ttvn,
1297                                               struct hashtable_t *hash,
1298                                               struct hard_iface *primary_if,
1299                                               int (*valid_cb)(const void *,
1300                                                               const void *),
1301                                               void *cb_data)
1302 {
1303         struct tt_common_entry *tt_common_entry;
1304         struct tt_query_packet *tt_response;
1305         struct tt_change *tt_change;
1306         struct hlist_node *node;
1307         struct hlist_head *head;
1308         struct sk_buff *skb = NULL;
1309         uint16_t tt_tot, tt_count;
1310         ssize_t tt_query_size = sizeof(struct tt_query_packet);
1311         uint32_t i;
1312
1313         if (tt_query_size + tt_len > primary_if->soft_iface->mtu) {
1314                 tt_len = primary_if->soft_iface->mtu - tt_query_size;
1315                 tt_len -= tt_len % sizeof(struct tt_change);
1316         }
1317         tt_tot = tt_len / sizeof(struct tt_change);
1318
1319         skb = dev_alloc_skb(tt_query_size + tt_len + ETH_HLEN);
1320         if (!skb)
1321                 goto out;
1322
1323         skb_reserve(skb, ETH_HLEN);
1324         tt_response = (struct tt_query_packet *)skb_put(skb,
1325                                                      tt_query_size + tt_len);
1326         tt_response->ttvn = ttvn;
1327
1328         tt_change = (struct tt_change *)(skb->data + tt_query_size);
1329         tt_count = 0;
1330
1331         rcu_read_lock();
1332         for (i = 0; i < hash->size; i++) {
1333                 head = &hash->table[i];
1334
1335                 hlist_for_each_entry_rcu(tt_common_entry, node,
1336                                          head, hash_entry) {
1337                         if (tt_count == tt_tot)
1338                                 break;
1339
1340                         if ((valid_cb) && (!valid_cb(tt_common_entry, cb_data)))
1341                                 continue;
1342
1343                         memcpy(tt_change->addr, tt_common_entry->addr,
1344                                ETH_ALEN);
1345                         tt_change->flags = NO_FLAGS;
1346
1347                         tt_count++;
1348                         tt_change++;
1349                 }
1350         }
1351         rcu_read_unlock();
1352
1353         /* store in the message the number of entries we have successfully
1354          * copied
1355          */
1356         tt_response->tt_data = htons(tt_count);
1357
1358 out:
1359         return skb;
1360 }
1361
1362 static int send_tt_request(struct bat_priv *bat_priv,
1363                            struct orig_node *dst_orig_node,
1364                            uint8_t ttvn, uint16_t tt_crc, bool full_table)
1365 {
1366         struct sk_buff *skb = NULL;
1367         struct tt_query_packet *tt_request;
1368         struct neigh_node *neigh_node = NULL;
1369         struct hard_iface *primary_if;
1370         struct tt_req_node *tt_req_node = NULL;
1371         int ret = 1;
1372
1373         primary_if = batadv_primary_if_get_selected(bat_priv);
1374         if (!primary_if)
1375                 goto out;
1376
1377         /* The new tt_req will be issued only if I'm not waiting for a
1378          * reply from the same orig_node yet
1379          */
1380         tt_req_node = new_tt_req_node(bat_priv, dst_orig_node);
1381         if (!tt_req_node)
1382                 goto out;
1383
1384         skb = dev_alloc_skb(sizeof(struct tt_query_packet) + ETH_HLEN);
1385         if (!skb)
1386                 goto out;
1387
1388         skb_reserve(skb, ETH_HLEN);
1389
1390         tt_request = (struct tt_query_packet *)skb_put(skb,
1391                                 sizeof(struct tt_query_packet));
1392
1393         tt_request->header.packet_type = BAT_TT_QUERY;
1394         tt_request->header.version = COMPAT_VERSION;
1395         memcpy(tt_request->src, primary_if->net_dev->dev_addr, ETH_ALEN);
1396         memcpy(tt_request->dst, dst_orig_node->orig, ETH_ALEN);
1397         tt_request->header.ttl = TTL;
1398         tt_request->ttvn = ttvn;
1399         tt_request->tt_data = htons(tt_crc);
1400         tt_request->flags = TT_REQUEST;
1401
1402         if (full_table)
1403                 tt_request->flags |= TT_FULL_TABLE;
1404
1405         neigh_node = batadv_orig_node_get_router(dst_orig_node);
1406         if (!neigh_node)
1407                 goto out;
1408
1409         bat_dbg(DBG_TT, bat_priv,
1410                 "Sending TT_REQUEST to %pM via %pM [%c]\n",
1411                 dst_orig_node->orig, neigh_node->addr,
1412                 (full_table ? 'F' : '.'));
1413
1414         batadv_inc_counter(bat_priv, BAT_CNT_TT_REQUEST_TX);
1415
1416         batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1417         ret = 0;
1418
1419 out:
1420         if (neigh_node)
1421                 batadv_neigh_node_free_ref(neigh_node);
1422         if (primary_if)
1423                 batadv_hardif_free_ref(primary_if);
1424         if (ret)
1425                 kfree_skb(skb);
1426         if (ret && tt_req_node) {
1427                 spin_lock_bh(&bat_priv->tt_req_list_lock);
1428                 list_del(&tt_req_node->list);
1429                 spin_unlock_bh(&bat_priv->tt_req_list_lock);
1430                 kfree(tt_req_node);
1431         }
1432         return ret;
1433 }
1434
1435 static bool send_other_tt_response(struct bat_priv *bat_priv,
1436                                    struct tt_query_packet *tt_request)
1437 {
1438         struct orig_node *req_dst_orig_node = NULL, *res_dst_orig_node = NULL;
1439         struct neigh_node *neigh_node = NULL;
1440         struct hard_iface *primary_if = NULL;
1441         uint8_t orig_ttvn, req_ttvn, ttvn;
1442         int ret = false;
1443         unsigned char *tt_buff;
1444         bool full_table;
1445         uint16_t tt_len, tt_tot;
1446         struct sk_buff *skb = NULL;
1447         struct tt_query_packet *tt_response;
1448
1449         bat_dbg(DBG_TT, bat_priv,
1450                 "Received TT_REQUEST from %pM for ttvn: %u (%pM) [%c]\n",
1451                 tt_request->src, tt_request->ttvn, tt_request->dst,
1452                 (tt_request->flags & TT_FULL_TABLE ? 'F' : '.'));
1453
1454         /* Let's get the orig node of the REAL destination */
1455         req_dst_orig_node = orig_hash_find(bat_priv, tt_request->dst);
1456         if (!req_dst_orig_node)
1457                 goto out;
1458
1459         res_dst_orig_node = orig_hash_find(bat_priv, tt_request->src);
1460         if (!res_dst_orig_node)
1461                 goto out;
1462
1463         neigh_node = batadv_orig_node_get_router(res_dst_orig_node);
1464         if (!neigh_node)
1465                 goto out;
1466
1467         primary_if = batadv_primary_if_get_selected(bat_priv);
1468         if (!primary_if)
1469                 goto out;
1470
1471         orig_ttvn = (uint8_t)atomic_read(&req_dst_orig_node->last_ttvn);
1472         req_ttvn = tt_request->ttvn;
1473
1474         /* I don't have the requested data */
1475         if (orig_ttvn != req_ttvn ||
1476             tt_request->tt_data != htons(req_dst_orig_node->tt_crc))
1477                 goto out;
1478
1479         /* If the full table has been explicitly requested */
1480         if (tt_request->flags & TT_FULL_TABLE ||
1481             !req_dst_orig_node->tt_buff)
1482                 full_table = true;
1483         else
1484                 full_table = false;
1485
1486         /* In this version, fragmentation is not implemented, then
1487          * I'll send only one packet with as much TT entries as I can
1488          */
1489         if (!full_table) {
1490                 spin_lock_bh(&req_dst_orig_node->tt_buff_lock);
1491                 tt_len = req_dst_orig_node->tt_buff_len;
1492                 tt_tot = tt_len / sizeof(struct tt_change);
1493
1494                 skb = dev_alloc_skb(sizeof(struct tt_query_packet) +
1495                                     tt_len + ETH_HLEN);
1496                 if (!skb)
1497                         goto unlock;
1498
1499                 skb_reserve(skb, ETH_HLEN);
1500                 tt_response = (struct tt_query_packet *)skb_put(skb,
1501                                 sizeof(struct tt_query_packet) + tt_len);
1502                 tt_response->ttvn = req_ttvn;
1503                 tt_response->tt_data = htons(tt_tot);
1504
1505                 tt_buff = skb->data + sizeof(struct tt_query_packet);
1506                 /* Copy the last orig_node's OGM buffer */
1507                 memcpy(tt_buff, req_dst_orig_node->tt_buff,
1508                        req_dst_orig_node->tt_buff_len);
1509
1510                 spin_unlock_bh(&req_dst_orig_node->tt_buff_lock);
1511         } else {
1512                 tt_len = (uint16_t)atomic_read(&req_dst_orig_node->tt_size) *
1513                                                 sizeof(struct tt_change);
1514                 ttvn = (uint8_t)atomic_read(&req_dst_orig_node->last_ttvn);
1515
1516                 skb = tt_response_fill_table(tt_len, ttvn,
1517                                              bat_priv->tt_global_hash,
1518                                              primary_if, tt_global_valid_entry,
1519                                              req_dst_orig_node);
1520                 if (!skb)
1521                         goto out;
1522
1523                 tt_response = (struct tt_query_packet *)skb->data;
1524         }
1525
1526         tt_response->header.packet_type = BAT_TT_QUERY;
1527         tt_response->header.version = COMPAT_VERSION;
1528         tt_response->header.ttl = TTL;
1529         memcpy(tt_response->src, req_dst_orig_node->orig, ETH_ALEN);
1530         memcpy(tt_response->dst, tt_request->src, ETH_ALEN);
1531         tt_response->flags = TT_RESPONSE;
1532
1533         if (full_table)
1534                 tt_response->flags |= TT_FULL_TABLE;
1535
1536         bat_dbg(DBG_TT, bat_priv,
1537                 "Sending TT_RESPONSE %pM via %pM for %pM (ttvn: %u)\n",
1538                 res_dst_orig_node->orig, neigh_node->addr,
1539                 req_dst_orig_node->orig, req_ttvn);
1540
1541         batadv_inc_counter(bat_priv, BAT_CNT_TT_RESPONSE_TX);
1542
1543         batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1544         ret = true;
1545         goto out;
1546
1547 unlock:
1548         spin_unlock_bh(&req_dst_orig_node->tt_buff_lock);
1549
1550 out:
1551         if (res_dst_orig_node)
1552                 batadv_orig_node_free_ref(res_dst_orig_node);
1553         if (req_dst_orig_node)
1554                 batadv_orig_node_free_ref(req_dst_orig_node);
1555         if (neigh_node)
1556                 batadv_neigh_node_free_ref(neigh_node);
1557         if (primary_if)
1558                 batadv_hardif_free_ref(primary_if);
1559         if (!ret)
1560                 kfree_skb(skb);
1561         return ret;
1562
1563 }
1564 static bool send_my_tt_response(struct bat_priv *bat_priv,
1565                                 struct tt_query_packet *tt_request)
1566 {
1567         struct orig_node *orig_node = NULL;
1568         struct neigh_node *neigh_node = NULL;
1569         struct hard_iface *primary_if = NULL;
1570         uint8_t my_ttvn, req_ttvn, ttvn;
1571         int ret = false;
1572         unsigned char *tt_buff;
1573         bool full_table;
1574         uint16_t tt_len, tt_tot;
1575         struct sk_buff *skb = NULL;
1576         struct tt_query_packet *tt_response;
1577
1578         bat_dbg(DBG_TT, bat_priv,
1579                 "Received TT_REQUEST from %pM for ttvn: %u (me) [%c]\n",
1580                 tt_request->src, tt_request->ttvn,
1581                 (tt_request->flags & TT_FULL_TABLE ? 'F' : '.'));
1582
1583
1584         my_ttvn = (uint8_t)atomic_read(&bat_priv->ttvn);
1585         req_ttvn = tt_request->ttvn;
1586
1587         orig_node = orig_hash_find(bat_priv, tt_request->src);
1588         if (!orig_node)
1589                 goto out;
1590
1591         neigh_node = batadv_orig_node_get_router(orig_node);
1592         if (!neigh_node)
1593                 goto out;
1594
1595         primary_if = batadv_primary_if_get_selected(bat_priv);
1596         if (!primary_if)
1597                 goto out;
1598
1599         /* If the full table has been explicitly requested or the gap
1600          * is too big send the whole local translation table
1601          */
1602         if (tt_request->flags & TT_FULL_TABLE || my_ttvn != req_ttvn ||
1603             !bat_priv->tt_buff)
1604                 full_table = true;
1605         else
1606                 full_table = false;
1607
1608         /* In this version, fragmentation is not implemented, then
1609          * I'll send only one packet with as much TT entries as I can
1610          */
1611         if (!full_table) {
1612                 spin_lock_bh(&bat_priv->tt_buff_lock);
1613                 tt_len = bat_priv->tt_buff_len;
1614                 tt_tot = tt_len / sizeof(struct tt_change);
1615
1616                 skb = dev_alloc_skb(sizeof(struct tt_query_packet) +
1617                                     tt_len + ETH_HLEN);
1618                 if (!skb)
1619                         goto unlock;
1620
1621                 skb_reserve(skb, ETH_HLEN);
1622                 tt_response = (struct tt_query_packet *)skb_put(skb,
1623                                 sizeof(struct tt_query_packet) + tt_len);
1624                 tt_response->ttvn = req_ttvn;
1625                 tt_response->tt_data = htons(tt_tot);
1626
1627                 tt_buff = skb->data + sizeof(struct tt_query_packet);
1628                 memcpy(tt_buff, bat_priv->tt_buff,
1629                        bat_priv->tt_buff_len);
1630                 spin_unlock_bh(&bat_priv->tt_buff_lock);
1631         } else {
1632                 tt_len = (uint16_t)atomic_read(&bat_priv->num_local_tt) *
1633                                                 sizeof(struct tt_change);
1634                 ttvn = (uint8_t)atomic_read(&bat_priv->ttvn);
1635
1636                 skb = tt_response_fill_table(tt_len, ttvn,
1637                                              bat_priv->tt_local_hash,
1638                                              primary_if, tt_local_valid_entry,
1639                                              NULL);
1640                 if (!skb)
1641                         goto out;
1642
1643                 tt_response = (struct tt_query_packet *)skb->data;
1644         }
1645
1646         tt_response->header.packet_type = BAT_TT_QUERY;
1647         tt_response->header.version = COMPAT_VERSION;
1648         tt_response->header.ttl = TTL;
1649         memcpy(tt_response->src, primary_if->net_dev->dev_addr, ETH_ALEN);
1650         memcpy(tt_response->dst, tt_request->src, ETH_ALEN);
1651         tt_response->flags = TT_RESPONSE;
1652
1653         if (full_table)
1654                 tt_response->flags |= TT_FULL_TABLE;
1655
1656         bat_dbg(DBG_TT, bat_priv,
1657                 "Sending TT_RESPONSE to %pM via %pM [%c]\n",
1658                 orig_node->orig, neigh_node->addr,
1659                 (tt_response->flags & TT_FULL_TABLE ? 'F' : '.'));
1660
1661         batadv_inc_counter(bat_priv, BAT_CNT_TT_RESPONSE_TX);
1662
1663         batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1664         ret = true;
1665         goto out;
1666
1667 unlock:
1668         spin_unlock_bh(&bat_priv->tt_buff_lock);
1669 out:
1670         if (orig_node)
1671                 batadv_orig_node_free_ref(orig_node);
1672         if (neigh_node)
1673                 batadv_neigh_node_free_ref(neigh_node);
1674         if (primary_if)
1675                 batadv_hardif_free_ref(primary_if);
1676         if (!ret)
1677                 kfree_skb(skb);
1678         /* This packet was for me, so it doesn't need to be re-routed */
1679         return true;
1680 }
1681
1682 bool batadv_send_tt_response(struct bat_priv *bat_priv,
1683                              struct tt_query_packet *tt_request)
1684 {
1685         if (batadv_is_my_mac(tt_request->dst)) {
1686                 /* don't answer backbone gws! */
1687                 if (batadv_bla_is_backbone_gw_orig(bat_priv, tt_request->src))
1688                         return true;
1689
1690                 return send_my_tt_response(bat_priv, tt_request);
1691         } else {
1692                 return send_other_tt_response(bat_priv, tt_request);
1693         }
1694 }
1695
1696 static void _tt_update_changes(struct bat_priv *bat_priv,
1697                                struct orig_node *orig_node,
1698                                struct tt_change *tt_change,
1699                                uint16_t tt_num_changes, uint8_t ttvn)
1700 {
1701         int i;
1702         int is_wifi;
1703
1704         for (i = 0; i < tt_num_changes; i++) {
1705                 if ((tt_change + i)->flags & TT_CLIENT_DEL) {
1706                         tt_global_del(bat_priv, orig_node,
1707                                       (tt_change + i)->addr,
1708                                       "tt removed by changes",
1709                                       (tt_change + i)->flags & TT_CLIENT_ROAM);
1710                 } else {
1711                         is_wifi = (tt_change + i)->flags & TT_CLIENT_WIFI;
1712                         if (!batadv_tt_global_add(bat_priv, orig_node,
1713                                                   (tt_change + i)->addr, ttvn,
1714                                                   false, is_wifi))
1715                                 /* In case of problem while storing a
1716                                  * global_entry, we stop the updating
1717                                  * procedure without committing the
1718                                  * ttvn change. This will avoid to send
1719                                  * corrupted data on tt_request
1720                                  */
1721                                 return;
1722                 }
1723         }
1724         orig_node->tt_initialised = true;
1725 }
1726
1727 static void tt_fill_gtable(struct bat_priv *bat_priv,
1728                            struct tt_query_packet *tt_response)
1729 {
1730         struct orig_node *orig_node = NULL;
1731
1732         orig_node = orig_hash_find(bat_priv, tt_response->src);
1733         if (!orig_node)
1734                 goto out;
1735
1736         /* Purge the old table first.. */
1737         batadv_tt_global_del_orig(bat_priv, orig_node, "Received full table");
1738
1739         _tt_update_changes(bat_priv, orig_node,
1740                            (struct tt_change *)(tt_response + 1),
1741                            ntohs(tt_response->tt_data), tt_response->ttvn);
1742
1743         spin_lock_bh(&orig_node->tt_buff_lock);
1744         kfree(orig_node->tt_buff);
1745         orig_node->tt_buff_len = 0;
1746         orig_node->tt_buff = NULL;
1747         spin_unlock_bh(&orig_node->tt_buff_lock);
1748
1749         atomic_set(&orig_node->last_ttvn, tt_response->ttvn);
1750
1751 out:
1752         if (orig_node)
1753                 batadv_orig_node_free_ref(orig_node);
1754 }
1755
1756 static void tt_update_changes(struct bat_priv *bat_priv,
1757                               struct orig_node *orig_node,
1758                               uint16_t tt_num_changes, uint8_t ttvn,
1759                               struct tt_change *tt_change)
1760 {
1761         _tt_update_changes(bat_priv, orig_node, tt_change, tt_num_changes,
1762                            ttvn);
1763
1764         tt_save_orig_buffer(bat_priv, orig_node, (unsigned char *)tt_change,
1765                             tt_num_changes);
1766         atomic_set(&orig_node->last_ttvn, ttvn);
1767 }
1768
1769 bool batadv_is_my_client(struct bat_priv *bat_priv, const uint8_t *addr)
1770 {
1771         struct tt_local_entry *tt_local_entry = NULL;
1772         bool ret = false;
1773
1774         tt_local_entry = tt_local_hash_find(bat_priv, addr);
1775         if (!tt_local_entry)
1776                 goto out;
1777         /* Check if the client has been logically deleted (but is kept for
1778          * consistency purpose)
1779          */
1780         if (tt_local_entry->common.flags & TT_CLIENT_PENDING)
1781                 goto out;
1782         ret = true;
1783 out:
1784         if (tt_local_entry)
1785                 tt_local_entry_free_ref(tt_local_entry);
1786         return ret;
1787 }
1788
1789 void batadv_handle_tt_response(struct bat_priv *bat_priv,
1790                                struct tt_query_packet *tt_response)
1791 {
1792         struct tt_req_node *node, *safe;
1793         struct orig_node *orig_node = NULL;
1794
1795         bat_dbg(DBG_TT, bat_priv,
1796                 "Received TT_RESPONSE from %pM for ttvn %d t_size: %d [%c]\n",
1797                 tt_response->src, tt_response->ttvn,
1798                 ntohs(tt_response->tt_data),
1799                 (tt_response->flags & TT_FULL_TABLE ? 'F' : '.'));
1800
1801         /* we should have never asked a backbone gw */
1802         if (batadv_bla_is_backbone_gw_orig(bat_priv, tt_response->src))
1803                 goto out;
1804
1805         orig_node = orig_hash_find(bat_priv, tt_response->src);
1806         if (!orig_node)
1807                 goto out;
1808
1809         if (tt_response->flags & TT_FULL_TABLE)
1810                 tt_fill_gtable(bat_priv, tt_response);
1811         else
1812                 tt_update_changes(bat_priv, orig_node,
1813                                   ntohs(tt_response->tt_data),
1814                                   tt_response->ttvn,
1815                                   (struct tt_change *)(tt_response + 1));
1816
1817         /* Delete the tt_req_node from pending tt_requests list */
1818         spin_lock_bh(&bat_priv->tt_req_list_lock);
1819         list_for_each_entry_safe(node, safe, &bat_priv->tt_req_list, list) {
1820                 if (!compare_eth(node->addr, tt_response->src))
1821                         continue;
1822                 list_del(&node->list);
1823                 kfree(node);
1824         }
1825         spin_unlock_bh(&bat_priv->tt_req_list_lock);
1826
1827         /* Recalculate the CRC for this orig_node and store it */
1828         orig_node->tt_crc = tt_global_crc(bat_priv, orig_node);
1829         /* Roaming phase is over: tables are in sync again. I can
1830          * unset the flag
1831          */
1832         orig_node->tt_poss_change = false;
1833 out:
1834         if (orig_node)
1835                 batadv_orig_node_free_ref(orig_node);
1836 }
1837
1838 int batadv_tt_init(struct bat_priv *bat_priv)
1839 {
1840         int ret;
1841
1842         ret = tt_local_init(bat_priv);
1843         if (ret < 0)
1844                 return ret;
1845
1846         ret = tt_global_init(bat_priv);
1847         if (ret < 0)
1848                 return ret;
1849
1850         tt_start_timer(bat_priv);
1851
1852         return 1;
1853 }
1854
1855 static void tt_roam_list_free(struct bat_priv *bat_priv)
1856 {
1857         struct tt_roam_node *node, *safe;
1858
1859         spin_lock_bh(&bat_priv->tt_roam_list_lock);
1860
1861         list_for_each_entry_safe(node, safe, &bat_priv->tt_roam_list, list) {
1862                 list_del(&node->list);
1863                 kfree(node);
1864         }
1865
1866         spin_unlock_bh(&bat_priv->tt_roam_list_lock);
1867 }
1868
1869 static void tt_roam_purge(struct bat_priv *bat_priv)
1870 {
1871         struct tt_roam_node *node, *safe;
1872
1873         spin_lock_bh(&bat_priv->tt_roam_list_lock);
1874         list_for_each_entry_safe(node, safe, &bat_priv->tt_roam_list, list) {
1875                 if (!has_timed_out(node->first_time, ROAMING_MAX_TIME))
1876                         continue;
1877
1878                 list_del(&node->list);
1879                 kfree(node);
1880         }
1881         spin_unlock_bh(&bat_priv->tt_roam_list_lock);
1882 }
1883
1884 /* This function checks whether the client already reached the
1885  * maximum number of possible roaming phases. In this case the ROAMING_ADV
1886  * will not be sent.
1887  *
1888  * returns true if the ROAMING_ADV can be sent, false otherwise
1889  */
1890 static bool tt_check_roam_count(struct bat_priv *bat_priv,
1891                                 uint8_t *client)
1892 {
1893         struct tt_roam_node *tt_roam_node;
1894         bool ret = false;
1895
1896         spin_lock_bh(&bat_priv->tt_roam_list_lock);
1897         /* The new tt_req will be issued only if I'm not waiting for a
1898          * reply from the same orig_node yet
1899          */
1900         list_for_each_entry(tt_roam_node, &bat_priv->tt_roam_list, list) {
1901                 if (!compare_eth(tt_roam_node->addr, client))
1902                         continue;
1903
1904                 if (has_timed_out(tt_roam_node->first_time, ROAMING_MAX_TIME))
1905                         continue;
1906
1907                 if (!atomic_dec_not_zero(&tt_roam_node->counter))
1908                         /* Sorry, you roamed too many times! */
1909                         goto unlock;
1910                 ret = true;
1911                 break;
1912         }
1913
1914         if (!ret) {
1915                 tt_roam_node = kmalloc(sizeof(*tt_roam_node), GFP_ATOMIC);
1916                 if (!tt_roam_node)
1917                         goto unlock;
1918
1919                 tt_roam_node->first_time = jiffies;
1920                 atomic_set(&tt_roam_node->counter, ROAMING_MAX_COUNT - 1);
1921                 memcpy(tt_roam_node->addr, client, ETH_ALEN);
1922
1923                 list_add(&tt_roam_node->list, &bat_priv->tt_roam_list);
1924                 ret = true;
1925         }
1926
1927 unlock:
1928         spin_unlock_bh(&bat_priv->tt_roam_list_lock);
1929         return ret;
1930 }
1931
1932 static void send_roam_adv(struct bat_priv *bat_priv, uint8_t *client,
1933                           struct orig_node *orig_node)
1934 {
1935         struct neigh_node *neigh_node = NULL;
1936         struct sk_buff *skb = NULL;
1937         struct roam_adv_packet *roam_adv_packet;
1938         int ret = 1;
1939         struct hard_iface *primary_if;
1940
1941         /* before going on we have to check whether the client has
1942          * already roamed to us too many times
1943          */
1944         if (!tt_check_roam_count(bat_priv, client))
1945                 goto out;
1946
1947         skb = dev_alloc_skb(sizeof(struct roam_adv_packet) + ETH_HLEN);
1948         if (!skb)
1949                 goto out;
1950
1951         skb_reserve(skb, ETH_HLEN);
1952
1953         roam_adv_packet = (struct roam_adv_packet *)skb_put(skb,
1954                                         sizeof(struct roam_adv_packet));
1955
1956         roam_adv_packet->header.packet_type = BAT_ROAM_ADV;
1957         roam_adv_packet->header.version = COMPAT_VERSION;
1958         roam_adv_packet->header.ttl = TTL;
1959         primary_if = batadv_primary_if_get_selected(bat_priv);
1960         if (!primary_if)
1961                 goto out;
1962         memcpy(roam_adv_packet->src, primary_if->net_dev->dev_addr, ETH_ALEN);
1963         batadv_hardif_free_ref(primary_if);
1964         memcpy(roam_adv_packet->dst, orig_node->orig, ETH_ALEN);
1965         memcpy(roam_adv_packet->client, client, ETH_ALEN);
1966
1967         neigh_node = batadv_orig_node_get_router(orig_node);
1968         if (!neigh_node)
1969                 goto out;
1970
1971         bat_dbg(DBG_TT, bat_priv,
1972                 "Sending ROAMING_ADV to %pM (client %pM) via %pM\n",
1973                 orig_node->orig, client, neigh_node->addr);
1974
1975         batadv_inc_counter(bat_priv, BAT_CNT_TT_ROAM_ADV_TX);
1976
1977         batadv_send_skb_packet(skb, neigh_node->if_incoming, neigh_node->addr);
1978         ret = 0;
1979
1980 out:
1981         if (neigh_node)
1982                 batadv_neigh_node_free_ref(neigh_node);
1983         if (ret)
1984                 kfree_skb(skb);
1985         return;
1986 }
1987
1988 static void tt_purge(struct work_struct *work)
1989 {
1990         struct delayed_work *delayed_work =
1991                 container_of(work, struct delayed_work, work);
1992         struct bat_priv *bat_priv =
1993                 container_of(delayed_work, struct bat_priv, tt_work);
1994
1995         tt_local_purge(bat_priv);
1996         tt_global_roam_purge(bat_priv);
1997         tt_req_purge(bat_priv);
1998         tt_roam_purge(bat_priv);
1999
2000         tt_start_timer(bat_priv);
2001 }
2002
2003 void batadv_tt_free(struct bat_priv *bat_priv)
2004 {
2005         cancel_delayed_work_sync(&bat_priv->tt_work);
2006
2007         tt_local_table_free(bat_priv);
2008         tt_global_table_free(bat_priv);
2009         tt_req_list_free(bat_priv);
2010         tt_changes_list_free(bat_priv);
2011         tt_roam_list_free(bat_priv);
2012
2013         kfree(bat_priv->tt_buff);
2014 }
2015
2016 /* This function will enable or disable the specified flags for all the entries
2017  * in the given hash table and returns the number of modified entries
2018  */
2019 static uint16_t tt_set_flags(struct hashtable_t *hash, uint16_t flags,
2020                              bool enable)
2021 {
2022         uint32_t i;
2023         uint16_t changed_num = 0;
2024         struct hlist_head *head;
2025         struct hlist_node *node;
2026         struct tt_common_entry *tt_common_entry;
2027
2028         if (!hash)
2029                 goto out;
2030
2031         for (i = 0; i < hash->size; i++) {
2032                 head = &hash->table[i];
2033
2034                 rcu_read_lock();
2035                 hlist_for_each_entry_rcu(tt_common_entry, node,
2036                                          head, hash_entry) {
2037                         if (enable) {
2038                                 if ((tt_common_entry->flags & flags) == flags)
2039                                         continue;
2040                                 tt_common_entry->flags |= flags;
2041                         } else {
2042                                 if (!(tt_common_entry->flags & flags))
2043                                         continue;
2044                                 tt_common_entry->flags &= ~flags;
2045                         }
2046                         changed_num++;
2047                 }
2048                 rcu_read_unlock();
2049         }
2050 out:
2051         return changed_num;
2052 }
2053
2054 /* Purge out all the tt local entries marked with TT_CLIENT_PENDING */
2055 static void tt_local_purge_pending_clients(struct bat_priv *bat_priv)
2056 {
2057         struct hashtable_t *hash = bat_priv->tt_local_hash;
2058         struct tt_common_entry *tt_common_entry;
2059         struct tt_local_entry *tt_local_entry;
2060         struct hlist_node *node, *node_tmp;
2061         struct hlist_head *head;
2062         spinlock_t *list_lock; /* protects write access to the hash lists */
2063         uint32_t i;
2064
2065         if (!hash)
2066                 return;
2067
2068         for (i = 0; i < hash->size; i++) {
2069                 head = &hash->table[i];
2070                 list_lock = &hash->list_locks[i];
2071
2072                 spin_lock_bh(list_lock);
2073                 hlist_for_each_entry_safe(tt_common_entry, node, node_tmp,
2074                                           head, hash_entry) {
2075                         if (!(tt_common_entry->flags & TT_CLIENT_PENDING))
2076                                 continue;
2077
2078                         bat_dbg(DBG_TT, bat_priv,
2079                                 "Deleting local tt entry (%pM): pending\n",
2080                                 tt_common_entry->addr);
2081
2082                         atomic_dec(&bat_priv->num_local_tt);
2083                         hlist_del_rcu(node);
2084                         tt_local_entry = container_of(tt_common_entry,
2085                                                       struct tt_local_entry,
2086                                                       common);
2087                         tt_local_entry_free_ref(tt_local_entry);
2088                 }
2089                 spin_unlock_bh(list_lock);
2090         }
2091
2092 }
2093
2094 static int tt_commit_changes(struct bat_priv *bat_priv,
2095                              unsigned char **packet_buff, int *packet_buff_len,
2096                              int packet_min_len)
2097 {
2098         uint16_t changed_num = 0;
2099
2100         if (atomic_read(&bat_priv->tt_local_changes) < 1)
2101                 return -ENOENT;
2102
2103         changed_num = tt_set_flags(bat_priv->tt_local_hash,
2104                                    TT_CLIENT_NEW, false);
2105
2106         /* all reset entries have to be counted as local entries */
2107         atomic_add(changed_num, &bat_priv->num_local_tt);
2108         tt_local_purge_pending_clients(bat_priv);
2109         bat_priv->tt_crc = batadv_tt_local_crc(bat_priv);
2110
2111         /* Increment the TTVN only once per OGM interval */
2112         atomic_inc(&bat_priv->ttvn);
2113         bat_dbg(DBG_TT, bat_priv, "Local changes committed, updating to ttvn %u\n",
2114                 (uint8_t)atomic_read(&bat_priv->ttvn));
2115         bat_priv->tt_poss_change = false;
2116
2117         /* reset the sending counter */
2118         atomic_set(&bat_priv->tt_ogm_append_cnt, TT_OGM_APPEND_MAX);
2119
2120         return tt_changes_fill_buff(bat_priv, packet_buff,
2121                                     packet_buff_len, packet_min_len);
2122 }
2123
2124 /* when calling this function (hard_iface == primary_if) has to be true */
2125 int batadv_tt_append_diff(struct bat_priv *bat_priv,
2126                           unsigned char **packet_buff, int *packet_buff_len,
2127                           int packet_min_len)
2128 {
2129         int tt_num_changes;
2130
2131         /* if at least one change happened */
2132         tt_num_changes = tt_commit_changes(bat_priv, packet_buff,
2133                                            packet_buff_len, packet_min_len);
2134
2135         /* if the changes have been sent often enough */
2136         if ((tt_num_changes < 0) &&
2137             (!atomic_dec_not_zero(&bat_priv->tt_ogm_append_cnt))) {
2138                 tt_realloc_packet_buff(packet_buff, packet_buff_len,
2139                                        packet_min_len, packet_min_len);
2140                 tt_num_changes = 0;
2141         }
2142
2143         return tt_num_changes;
2144 }
2145
2146 bool batadv_is_ap_isolated(struct bat_priv *bat_priv, uint8_t *src,
2147                            uint8_t *dst)
2148 {
2149         struct tt_local_entry *tt_local_entry = NULL;
2150         struct tt_global_entry *tt_global_entry = NULL;
2151         bool ret = true;
2152
2153         if (!atomic_read(&bat_priv->ap_isolation))
2154                 return false;
2155
2156         tt_local_entry = tt_local_hash_find(bat_priv, dst);
2157         if (!tt_local_entry)
2158                 goto out;
2159
2160         tt_global_entry = tt_global_hash_find(bat_priv, src);
2161         if (!tt_global_entry)
2162                 goto out;
2163
2164         if (_is_ap_isolated(tt_local_entry, tt_global_entry))
2165                 goto out;
2166
2167         ret = false;
2168
2169 out:
2170         if (tt_global_entry)
2171                 tt_global_entry_free_ref(tt_global_entry);
2172         if (tt_local_entry)
2173                 tt_local_entry_free_ref(tt_local_entry);
2174         return ret;
2175 }
2176
2177 void batadv_tt_update_orig(struct bat_priv *bat_priv,
2178                            struct orig_node *orig_node,
2179                            const unsigned char *tt_buff, uint8_t tt_num_changes,
2180                            uint8_t ttvn, uint16_t tt_crc)
2181 {
2182         uint8_t orig_ttvn = (uint8_t)atomic_read(&orig_node->last_ttvn);
2183         bool full_table = true;
2184
2185         /* don't care about a backbone gateways updates. */
2186         if (batadv_bla_is_backbone_gw_orig(bat_priv, orig_node->orig))
2187                 return;
2188
2189         /* orig table not initialised AND first diff is in the OGM OR the ttvn
2190          * increased by one -> we can apply the attached changes
2191          */
2192         if ((!orig_node->tt_initialised && ttvn == 1) ||
2193             ttvn - orig_ttvn == 1) {
2194                 /* the OGM could not contain the changes due to their size or
2195                  * because they have already been sent TT_OGM_APPEND_MAX times.
2196                  * In this case send a tt request
2197                  */
2198                 if (!tt_num_changes) {
2199                         full_table = false;
2200                         goto request_table;
2201                 }
2202
2203                 tt_update_changes(bat_priv, orig_node, tt_num_changes, ttvn,
2204                                   (struct tt_change *)tt_buff);
2205
2206                 /* Even if we received the precomputed crc with the OGM, we
2207                  * prefer to recompute it to spot any possible inconsistency
2208                  * in the global table
2209                  */
2210                 orig_node->tt_crc = tt_global_crc(bat_priv, orig_node);
2211
2212                 /* The ttvn alone is not enough to guarantee consistency
2213                  * because a single value could represent different states
2214                  * (due to the wrap around). Thus a node has to check whether
2215                  * the resulting table (after applying the changes) is still
2216                  * consistent or not. E.g. a node could disconnect while its
2217                  * ttvn is X and reconnect on ttvn = X + TTVN_MAX: in this case
2218                  * checking the CRC value is mandatory to detect the
2219                  * inconsistency
2220                  */
2221                 if (orig_node->tt_crc != tt_crc)
2222                         goto request_table;
2223
2224                 /* Roaming phase is over: tables are in sync again. I can
2225                  * unset the flag
2226                  */
2227                 orig_node->tt_poss_change = false;
2228         } else {
2229                 /* if we missed more than one change or our tables are not
2230                  * in sync anymore -> request fresh tt data
2231                  */
2232                 if (!orig_node->tt_initialised || ttvn != orig_ttvn ||
2233                     orig_node->tt_crc != tt_crc) {
2234 request_table:
2235                         bat_dbg(DBG_TT, bat_priv,
2236                                 "TT inconsistency for %pM. Need to retrieve the correct information (ttvn: %u last_ttvn: %u crc: %u last_crc: %u num_changes: %u)\n",
2237                                 orig_node->orig, ttvn, orig_ttvn, tt_crc,
2238                                 orig_node->tt_crc, tt_num_changes);
2239                         send_tt_request(bat_priv, orig_node, ttvn, tt_crc,
2240                                         full_table);
2241                         return;
2242                 }
2243         }
2244 }
2245
2246 /* returns true whether we know that the client has moved from its old
2247  * originator to another one. This entry is kept is still kept for consistency
2248  * purposes
2249  */
2250 bool batadv_tt_global_client_is_roaming(struct bat_priv *bat_priv,
2251                                         uint8_t *addr)
2252 {
2253         struct tt_global_entry *tt_global_entry;
2254         bool ret = false;
2255
2256         tt_global_entry = tt_global_hash_find(bat_priv, addr);
2257         if (!tt_global_entry)
2258                 goto out;
2259
2260         ret = tt_global_entry->common.flags & TT_CLIENT_ROAM;
2261         tt_global_entry_free_ref(tt_global_entry);
2262 out:
2263         return ret;
2264 }