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