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