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