drivers/staging/batman-adv/vis.c

   1 /*
   2  * Copyright (C) 2008-2009 B.A.T.M.A.N. contributors:
   3  *
   4  * Simon Wunderlich
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of version 2 of the GNU General Public
   8  * License as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18  * 02110-1301, USA
  19  *
  20  */
  21
  22 #include "main.h"
  23 #include "send.h"
  24 #include "translation-table.h"
  25 #include "vis.h"
  26 #include "soft-interface.h"
  27 #include "hard-interface.h"
  28 #include "hash.h"
  29 #include "compat.h"
  30
  31 struct hashtable_t *vis_hash;
  32 DEFINE_SPINLOCK(vis_hash_lock);
  33 static struct vis_info *my_vis_info;
  34 static struct list_head send_list;      /* always locked with vis_hash_lock */
  35
  36 static void start_vis_timer(void);
  37
  38 /* free the info */
  39 static void free_info(void *data)
  40 {
  41         struct vis_info *info = data;
  42         struct recvlist_node *entry, *tmp;
  43
  44         list_del_init(&info->send_list);
  45         list_for_each_entry_safe(entry, tmp, &info->recv_list, list) {
  46                 list_del(&entry->list);
  47                 kfree(entry);
  48         }
  49         kfree(info);
  50 }
  51
  52 /* set the mode of the visualization to client or server */
  53 void vis_set_mode(int mode)
  54 {
  55         spin_lock(&vis_hash_lock);
  56
  57         if (my_vis_info != NULL)
  58                 my_vis_info->packet.vis_type = mode;
  59
  60         spin_unlock(&vis_hash_lock);
  61 }
  62
  63 /* is_vis_server(), locked outside */
  64 static int is_vis_server_locked(void)
  65 {
  66         if (my_vis_info != NULL)
  67                 if (my_vis_info->packet.vis_type == VIS_TYPE_SERVER_SYNC)
  68                         return 1;
  69
  70         return 0;
  71 }
  72
  73 /* get the current set mode */
  74 int is_vis_server(void)
  75 {
  76         int ret = 0;
  77
  78         spin_lock(&vis_hash_lock);
  79         ret = is_vis_server_locked();
  80         spin_unlock(&vis_hash_lock);
  81
  82         return ret;
  83 }
  84
  85 /* Compare two vis packets, used by the hashing algorithm */
  86 static int vis_info_cmp(void *data1, void *data2)
  87 {
  88         struct vis_info *d1, *d2;
  89         d1 = data1;
  90         d2 = data2;
  91         return compare_orig(d1->packet.vis_orig, d2->packet.vis_orig);
  92 }
  93
  94 /* hash function to choose an entry in a hash table of given size */
  95 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
  96 static int vis_info_choose(void *data, int size)
  97 {
  98         struct vis_info *vis_info = data;
  99         unsigned char *key;
 100         uint32_t hash = 0;
 101         size_t i;
 102
 103         key = vis_info->packet.vis_orig;
 104         for (i = 0; i < ETH_ALEN; i++) {
 105                 hash += key[i];
 106                 hash += (hash << 10);
 107                 hash ^= (hash >> 6);
 108         }
 109
 110         hash += (hash << 3);
 111         hash ^= (hash >> 11);
 112         hash += (hash << 15);
 113
 114         return hash % size;
 115 }
 116
 117 /* tries to add one entry to the receive list. */
 118 static void recv_list_add(struct list_head *recv_list, char *mac)
 119 {
 120         struct recvlist_node *entry;
 121         entry = kmalloc(sizeof(struct recvlist_node), GFP_ATOMIC);
 122         if (!entry)
 123                 return;
 124
 125         memcpy(entry->mac, mac, ETH_ALEN);
 126         list_add_tail(&entry->list, recv_list);
 127 }
 128
 129 /* returns 1 if this mac is in the recv_list */
 130 static int recv_list_is_in(struct list_head *recv_list, char *mac)
 131 {
 132         struct recvlist_node *entry;
 133
 134         list_for_each_entry(entry, recv_list, list) {
 135                 if (memcmp(entry->mac, mac, ETH_ALEN) == 0)
 136                         return 1;
 137         }
 138
 139         return 0;
 140 }
 141
 142 /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old,
 143  * broken.. ).  vis hash must be locked outside.  is_new is set when the packet
 144  * is newer than old entries in the hash. */
 145 static struct vis_info *add_packet(struct vis_packet *vis_packet,
 146                                    int vis_info_len, int *is_new)
 147 {
 148         struct vis_info *info, *old_info;
 149         struct vis_info search_elem;
 150
 151         *is_new = 0;
 152         /* sanity check */
 153         if (vis_hash == NULL)
 154                 return NULL;
 155
 156         /* see if the packet is already in vis_hash */
 157         memcpy(search_elem.packet.vis_orig, vis_packet->vis_orig, ETH_ALEN);
 158         old_info = hash_find(vis_hash, &search_elem);
 159
 160         if (old_info != NULL) {
 161                 if (vis_packet->seqno - old_info->packet.seqno <= 0) {
 162                         if (old_info->packet.seqno == vis_packet->seqno) {
 163                                 recv_list_add(&old_info->recv_list,
 164                                               vis_packet->sender_orig);
 165                                 return old_info;
 166                         } else {
 167                                 /* newer packet is already in hash. */
 168                                 return NULL;
 169                         }
 170                 }
 171                 /* remove old entry */
 172                 hash_remove(vis_hash, old_info);
 173                 free_info(old_info);
 174         }
 175
 176         info = kmalloc(sizeof(struct vis_info) + vis_info_len, GFP_ATOMIC);
 177         if (info == NULL)
 178                 return NULL;
 179
 180         INIT_LIST_HEAD(&info->send_list);
 181         INIT_LIST_HEAD(&info->recv_list);
 182         info->first_seen = jiffies;
 183         memcpy(&info->packet, vis_packet,
 184                sizeof(struct vis_packet) + vis_info_len);
 185
 186         /* initialize and add new packet. */
 187         *is_new = 1;
 188
 189         /* repair if entries is longer than packet. */
 190         if (info->packet.entries * sizeof(struct vis_info_entry) > vis_info_len)
 191                 info->packet.entries = vis_info_len / sizeof(struct vis_info_entry);
 192
 193         recv_list_add(&info->recv_list, info->packet.sender_orig);
 194
 195         /* try to add it */
 196         if (hash_add(vis_hash, info) < 0) {
 197                 /* did not work (for some reason) */
 198                 free_info(info);
 199                 info = NULL;
 200         }
 201
 202         return info;
 203 }
 204
 205 /* handle the server sync packet, forward if needed. */
 206 void receive_server_sync_packet(struct vis_packet *vis_packet, int vis_info_len)
 207 {
 208         struct vis_info *info;
 209         int is_new;
 210
 211         spin_lock(&vis_hash_lock);
 212         info = add_packet(vis_packet, vis_info_len, &is_new);
 213         if (info == NULL)
 214                 goto end;
 215
 216         /* only if we are server ourselves and packet is newer than the one in
 217          * hash.*/
 218         if (is_vis_server_locked() && is_new) {
 219                 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 220                 if (list_empty(&info->send_list))
 221                         list_add_tail(&info->send_list, &send_list);
 222         }
 223 end:
 224         spin_unlock(&vis_hash_lock);
 225 }
 226
 227 /* handle an incoming client update packet and schedule forward if needed. */
 228 void receive_client_update_packet(struct vis_packet *vis_packet,
 229                                   int vis_info_len)
 230 {
 231         struct vis_info *info;
 232         int is_new;
 233
 234         /* clients shall not broadcast. */
 235         if (is_bcast(vis_packet->target_orig))
 236                 return;
 237
 238         spin_lock(&vis_hash_lock);
 239         info = add_packet(vis_packet, vis_info_len, &is_new);
 240         if (info == NULL)
 241                 goto end;
 242         /* note that outdated packets will be dropped at this point. */
 243
 244
 245         /* send only if we're the target server or ... */
 246         if (is_vis_server_locked() &&
 247             is_my_mac(info->packet.target_orig) &&
 248             is_new) {
 249                 info->packet.vis_type = VIS_TYPE_SERVER_SYNC;   /* upgrade! */
 250                 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 251                 if (list_empty(&info->send_list))
 252                         list_add_tail(&info->send_list, &send_list);
 253
 254                 /* ... we're not the recipient (and thus need to forward). */
 255         } else if (!is_my_mac(info->packet.target_orig)) {
 256                 if (list_empty(&info->send_list))
 257                         list_add_tail(&info->send_list, &send_list);
 258         }
 259 end:
 260         spin_unlock(&vis_hash_lock);
 261 }
 262
 263 /* Walk the originators and find the VIS server with the best tq. Set the packet
 264  * address to its address and return the best_tq.
 265  *
 266  * Must be called with the originator hash locked */
 267 static int find_best_vis_server(struct vis_info *info)
 268 {
 269         HASHIT(hashit);
 270         struct orig_node *orig_node;
 271         int best_tq = -1;
 272
 273         while (hash_iterate(orig_hash, &hashit)) {
 274                 orig_node = hashit.bucket->data;
 275                 if ((orig_node != NULL) &&
 276                     (orig_node->router != NULL) &&
 277                     (orig_node->flags & VIS_SERVER) &&
 278                     (orig_node->router->tq_avg > best_tq)) {
 279                         best_tq = orig_node->router->tq_avg;
 280                         memcpy(info->packet.target_orig, orig_node->orig,
 281                                ETH_ALEN);
 282                 }
 283         }
 284         return best_tq;
 285 }
 286
 287 /* Return true if the vis packet is full. */
 288 static bool vis_packet_full(struct vis_info *info)
 289 {
 290         if (info->packet.entries + 1 >
 291             (1000 - sizeof(struct vis_info)) / sizeof(struct vis_info_entry))
 292                 return true;
 293         return false;
 294 }
 295
 296 /* generates a packet of own vis data,
 297  * returns 0 on success, -1 if no packet could be generated */
 298 static int generate_vis_packet(void)
 299 {
 300         HASHIT(hashit_local);
 301         HASHIT(hashit_global);
 302         struct orig_node *orig_node;
 303         struct vis_info *info = (struct vis_info *)my_vis_info;
 304         struct vis_info_entry *entry, *entry_array;
 305         struct hna_local_entry *hna_local_entry;
 306         int best_tq = -1;
 307         unsigned long flags;
 308
 309         info->first_seen = jiffies;
 310
 311         spin_lock(&orig_hash_lock);
 312         memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 313         info->packet.ttl = TTL;
 314         info->packet.seqno++;
 315         info->packet.entries = 0;
 316
 317         if (!is_vis_server_locked()) {
 318                 best_tq = find_best_vis_server(info);
 319                 if (best_tq < 0) {
 320                         spin_unlock(&orig_hash_lock);
 321                         return -1;
 322                 }
 323         }
 324
 325         entry_array = (struct vis_info_entry *)
 326                 ((char *)info + sizeof(struct vis_info));
 327
 328         while (hash_iterate(orig_hash, &hashit_global)) {
 329                 orig_node = hashit_global.bucket->data;
 330                 if (orig_node->router != NULL
 331                         && compare_orig(orig_node->router->addr, orig_node->orig)
 332                         && orig_node->batman_if
 333                         && (orig_node->batman_if->if_active == IF_ACTIVE)
 334                     && orig_node->router->tq_avg > 0) {
 335
 336                         /* fill one entry into buffer. */
 337                         entry = &entry_array[info->packet.entries];
 338                         memcpy(entry->src, orig_node->batman_if->net_dev->dev_addr, ETH_ALEN);
 339                         memcpy(entry->dest, orig_node->orig, ETH_ALEN);
 340                         entry->quality = orig_node->router->tq_avg;
 341                         info->packet.entries++;
 342
 343                         if (vis_packet_full(info)) {
 344                                 spin_unlock(&orig_hash_lock);
 345                                 return 0;
 346                         }
 347                 }
 348         }
 349
 350         spin_unlock(&orig_hash_lock);
 351
 352         spin_lock_irqsave(&hna_local_hash_lock, flags);
 353         while (hash_iterate(hna_local_hash, &hashit_local)) {
 354                 hna_local_entry = hashit_local.bucket->data;
 355                 entry = &entry_array[info->packet.entries];
 356                 memset(entry->src, 0, ETH_ALEN);
 357                 memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN);
 358                 entry->quality = 0; /* 0 means HNA */
 359                 info->packet.entries++;
 360
 361                 if (vis_packet_full(info)) {
 362                         spin_unlock_irqrestore(&hna_local_hash_lock, flags);
 363                         return 0;
 364                 }
 365         }
 366         spin_unlock_irqrestore(&hna_local_hash_lock, flags);
 367         return 0;
 368 }
 369
 370 static void purge_vis_packets(void)
 371 {
 372         HASHIT(hashit);
 373         struct vis_info *info;
 374
 375         while (hash_iterate(vis_hash, &hashit)) {
 376                 info = hashit.bucket->data;
 377                 if (info == my_vis_info)        /* never purge own data. */
 378                         continue;
 379                 if (time_after(jiffies,
 380                                info->first_seen + (VIS_TIMEOUT/1000)*HZ)) {
 381                         hash_remove_bucket(vis_hash, &hashit);
 382                         free_info(info);
 383                 }
 384         }
 385 }
 386
 387 static void broadcast_vis_packet(struct vis_info *info, int packet_length)
 388 {
 389         HASHIT(hashit);
 390         struct orig_node *orig_node;
 391
 392         spin_lock(&orig_hash_lock);
 393
 394         /* send to all routers in range. */
 395         while (hash_iterate(orig_hash, &hashit)) {
 396                 orig_node = hashit.bucket->data;
 397
 398                 /* if it's a vis server and reachable, send it. */
 399                 if (orig_node &&
 400                     (orig_node->flags & VIS_SERVER) &&
 401                     orig_node->batman_if &&
 402                     orig_node->router) {
 403
 404                         /* don't send it if we already received the packet from
 405                          * this node. */
 406                         if (recv_list_is_in(&info->recv_list, orig_node->orig))
 407                                 continue;
 408
 409                         memcpy(info->packet.target_orig,
 410                                orig_node->orig, ETH_ALEN);
 411
 412                         send_raw_packet((unsigned char *) &info->packet,
 413                                         packet_length,
 414                                         orig_node->batman_if,
 415                                         orig_node->router->addr);
 416                 }
 417         }
 418         memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 419         spin_unlock(&orig_hash_lock);
 420 }
 421
 422 static void unicast_vis_packet(struct vis_info *info, int packet_length)
 423 {
 424         struct orig_node *orig_node;
 425
 426         spin_lock(&orig_hash_lock);
 427         orig_node = ((struct orig_node *)
 428                      hash_find(orig_hash, info->packet.target_orig));
 429
 430         if ((orig_node != NULL) &&
 431             (orig_node->batman_if != NULL) &&
 432             (orig_node->router != NULL)) {
 433                 send_raw_packet((unsigned char *) &info->packet, packet_length,
 434                                 orig_node->batman_if,
 435                                 orig_node->router->addr);
 436         }
 437         spin_unlock(&orig_hash_lock);
 438 }
 439
 440 /* only send one vis packet. called from send_vis_packets() */
 441 static void send_vis_packet(struct vis_info *info)
 442 {
 443         int packet_length;
 444
 445         if (info->packet.ttl < 2) {
 446                 printk(KERN_WARNING "batman-adv: Error - can't send vis packet: ttl exceeded\n");
 447                 return;
 448         }
 449
 450         memcpy(info->packet.sender_orig, mainIfAddr, ETH_ALEN);
 451         info->packet.ttl--;
 452
 453         packet_length = sizeof(struct vis_packet) +
 454                 info->packet.entries * sizeof(struct vis_info_entry);
 455
 456         if (is_bcast(info->packet.target_orig))
 457                 broadcast_vis_packet(info, packet_length);
 458         else
 459                 unicast_vis_packet(info, packet_length);
 460         info->packet.ttl++; /* restore TTL */
 461 }
 462
 463 /* called from timer; send (and maybe generate) vis packet. */
 464 static void send_vis_packets(struct work_struct *work)
 465 {
 466         struct vis_info *info, *temp;
 467
 468         spin_lock(&vis_hash_lock);
 469         purge_vis_packets();
 470
 471         if (generate_vis_packet() == 0)
 472                 /* schedule if generation was successful */
 473                 list_add_tail(&my_vis_info->send_list, &send_list);
 474
 475         list_for_each_entry_safe(info, temp, &send_list, send_list) {
 476                 list_del_init(&info->send_list);
 477                 send_vis_packet(info);
 478         }
 479         spin_unlock(&vis_hash_lock);
 480         start_vis_timer();
 481 }
 482 static DECLARE_DELAYED_WORK(vis_timer_wq, send_vis_packets);
 483
 484 /* init the vis server. this may only be called when if_list is already
 485  * initialized (e.g. bat0 is initialized, interfaces have been added) */
 486 int vis_init(void)
 487 {
 488         if (vis_hash)
 489                 return 1;
 490
 491         spin_lock(&vis_hash_lock);
 492
 493         vis_hash = hash_new(256, vis_info_cmp, vis_info_choose);
 494         if (!vis_hash) {
 495                 printk(KERN_ERR "batman-adv:Can't initialize vis_hash\n");
 496                 goto err;
 497         }
 498
 499         my_vis_info = kmalloc(1000, GFP_ATOMIC);
 500         if (!my_vis_info) {
 501                 printk(KERN_ERR "batman-adv:Can't initialize vis packet\n");
 502                 goto err;
 503         }
 504
 505         /* prefill the vis info */
 506         my_vis_info->first_seen = jiffies - atomic_read(&vis_interval);
 507         INIT_LIST_HEAD(&my_vis_info->recv_list);
 508         INIT_LIST_HEAD(&my_vis_info->send_list);
 509         my_vis_info->packet.version = COMPAT_VERSION;
 510         my_vis_info->packet.packet_type = BAT_VIS;
 511         my_vis_info->packet.vis_type = VIS_TYPE_CLIENT_UPDATE;
 512         my_vis_info->packet.ttl = TTL;
 513         my_vis_info->packet.seqno = 0;
 514         my_vis_info->packet.entries = 0;
 515
 516         INIT_LIST_HEAD(&send_list);
 517
 518         memcpy(my_vis_info->packet.vis_orig, mainIfAddr, ETH_ALEN);
 519         memcpy(my_vis_info->packet.sender_orig, mainIfAddr, ETH_ALEN);
 520
 521         if (hash_add(vis_hash, my_vis_info) < 0) {
 522                 printk(KERN_ERR
 523                           "batman-adv:Can't add own vis packet into hash\n");
 524                 free_info(my_vis_info); /* not in hash, need to remove it
 525                                          * manually. */
 526                 goto err;
 527         }
 528
 529         spin_unlock(&vis_hash_lock);
 530         start_vis_timer();
 531         return 1;
 532
 533 err:
 534         spin_unlock(&vis_hash_lock);
 535         vis_quit();
 536         return 0;
 537 }
 538
 539 /* shutdown vis-server */
 540 void vis_quit(void)
 541 {
 542         if (!vis_hash)
 543                 return;
 544
 545         cancel_delayed_work_sync(&vis_timer_wq);
 546
 547         spin_lock(&vis_hash_lock);
 548         /* properly remove, kill timers ... */
 549         hash_delete(vis_hash, free_info);
 550         vis_hash = NULL;
 551         my_vis_info = NULL;
 552         spin_unlock(&vis_hash_lock);
 553 }
 554
 555 /* schedule packets for (re)transmission */
 556 static void start_vis_timer(void)
 557 {
 558         queue_delayed_work(bat_event_workqueue, &vis_timer_wq,
 559                            (atomic_read(&vis_interval)/1000) * HZ);
 560 }
 561