net/batman-adv/translation-table.c

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