net/batman-adv/translation-table.c

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