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