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