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