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 /* insert interface to the list of interfaces of one originator, if it
 118  * does not already exist in the list */
 119 static void proc_vis_insert_interface(const uint8_t *interface,
 120                                       struct hlist_head *if_list,
 121                                       bool primary)
 122 {
 123         struct if_list_entry *entry;
 124         struct hlist_node *pos;
 125
 126         hlist_for_each_entry(entry, pos, if_list, list) {
 127                 if (compare_orig(entry->addr, (void *)interface))
 128                         return;
 129         }
 130
 131         /* its a new address, add it to the list */
 132         entry = kmalloc(sizeof(*entry), GFP_KERNEL);
 133         if (!entry)
 134                 return;
 135         memcpy(entry->addr, interface, ETH_ALEN);
 136         entry->primary = primary;
 137         hlist_add_head(&entry->list, if_list);
 138 }
 139
 140 void proc_vis_read_prim_sec(struct seq_file *seq,
 141                             struct hlist_head *if_list)
 142 {
 143         struct if_list_entry *entry;
 144         struct hlist_node *pos, *n;
 145         char tmp_addr_str[ETH_STR_LEN];
 146
 147         hlist_for_each_entry_safe(entry, pos, n, if_list, list) {
 148                 if (entry->primary) {
 149                         seq_printf(seq, "PRIMARY, ");
 150                 } else {
 151                         addr_to_string(tmp_addr_str, entry->addr);
 152                         seq_printf(seq, "SEC %s, ", tmp_addr_str);
 153                 }
 154
 155                 hlist_del(&entry->list);
 156                 kfree(entry);
 157         }
 158 }
 159
 160 /* read an entry  */
 161 void proc_vis_read_entry(struct seq_file *seq,
 162                                 struct vis_info_entry *entry,
 163                                 struct hlist_head *if_list,
 164                                 uint8_t *vis_orig)
 165 {
 166         char to[40];
 167
 168         addr_to_string(to, entry->dest);
 169         if (entry->quality == 0) {
 170                 proc_vis_insert_interface(vis_orig, if_list, true);
 171                 seq_printf(seq, "HNA %s, ", to);
 172         } else {
 173                 proc_vis_insert_interface(entry->src, if_list,
 174                                           compare_orig(entry->src, vis_orig));
 175                 seq_printf(seq, "TQ %s %d, ", to, entry->quality);
 176         }
 177 }
 178
 179 /* tries to add one entry to the receive list. */
 180 static void recv_list_add(struct list_head *recv_list, char *mac)
 181 {
 182         struct recvlist_node *entry;
 183         entry = kmalloc(sizeof(struct recvlist_node), GFP_ATOMIC);
 184         if (!entry)
 185                 return;
 186
 187         memcpy(entry->mac, mac, ETH_ALEN);
 188         list_add_tail(&entry->list, recv_list);
 189 }
 190
 191 /* returns 1 if this mac is in the recv_list */
 192 static int recv_list_is_in(struct list_head *recv_list, char *mac)
 193 {
 194         struct recvlist_node *entry;
 195
 196         list_for_each_entry(entry, recv_list, list) {
 197                 if (memcmp(entry->mac, mac, ETH_ALEN) == 0)
 198                         return 1;
 199         }
 200
 201         return 0;
 202 }
 203
 204 /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old,
 205  * broken.. ).  vis hash must be locked outside.  is_new is set when the packet
 206  * is newer than old entries in the hash. */
 207 static struct vis_info *add_packet(struct vis_packet *vis_packet,
 208                                    int vis_info_len, int *is_new)
 209 {
 210         struct vis_info *info, *old_info;
 211         struct vis_info search_elem;
 212
 213         *is_new = 0;
 214         /* sanity check */
 215         if (vis_hash == NULL)
 216                 return NULL;
 217
 218         /* see if the packet is already in vis_hash */
 219         memcpy(search_elem.packet.vis_orig, vis_packet->vis_orig, ETH_ALEN);
 220         old_info = hash_find(vis_hash, &search_elem);
 221
 222         if (old_info != NULL) {
 223                 if (vis_packet->seqno - old_info->packet.seqno <= 0) {
 224                         if (old_info->packet.seqno == vis_packet->seqno) {
 225                                 recv_list_add(&old_info->recv_list,
 226                                               vis_packet->sender_orig);
 227                                 return old_info;
 228                         } else {
 229                                 /* newer packet is already in hash. */
 230                                 return NULL;
 231                         }
 232                 }
 233                 /* remove old entry */
 234                 hash_remove(vis_hash, old_info);
 235                 free_info(old_info);
 236         }
 237
 238         info = kmalloc(sizeof(struct vis_info) + vis_info_len, GFP_ATOMIC);
 239         if (info == NULL)
 240                 return NULL;
 241
 242         INIT_LIST_HEAD(&info->send_list);
 243         INIT_LIST_HEAD(&info->recv_list);
 244         info->first_seen = jiffies;
 245         memcpy(&info->packet, vis_packet,
 246                sizeof(struct vis_packet) + vis_info_len);
 247
 248         /* initialize and add new packet. */
 249         *is_new = 1;
 250
 251         /* repair if entries is longer than packet. */
 252         if (info->packet.entries * sizeof(struct vis_info_entry) > vis_info_len)
 253                 info->packet.entries = vis_info_len / sizeof(struct vis_info_entry);
 254
 255         recv_list_add(&info->recv_list, info->packet.sender_orig);
 256
 257         /* try to add it */
 258         if (hash_add(vis_hash, info) < 0) {
 259                 /* did not work (for some reason) */
 260                 free_info(info);
 261                 info = NULL;
 262         }
 263
 264         return info;
 265 }
 266
 267 /* handle the server sync packet, forward if needed. */
 268 void receive_server_sync_packet(struct vis_packet *vis_packet, int vis_info_len)
 269 {
 270         struct vis_info *info;
 271         int is_new;
 272
 273         spin_lock(&vis_hash_lock);
 274         info = add_packet(vis_packet, vis_info_len, &is_new);
 275         if (info == NULL)
 276                 goto end;
 277
 278         /* only if we are server ourselves and packet is newer than the one in
 279          * hash.*/
 280         if (is_vis_server_locked() && is_new) {
 281                 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 282                 if (list_empty(&info->send_list))
 283                         list_add_tail(&info->send_list, &send_list);
 284         }
 285 end:
 286         spin_unlock(&vis_hash_lock);
 287 }
 288
 289 /* handle an incoming client update packet and schedule forward if needed. */
 290 void receive_client_update_packet(struct vis_packet *vis_packet,
 291                                   int vis_info_len)
 292 {
 293         struct vis_info *info;
 294         int is_new;
 295
 296         /* clients shall not broadcast. */
 297         if (is_bcast(vis_packet->target_orig))
 298                 return;
 299
 300         spin_lock(&vis_hash_lock);
 301         info = add_packet(vis_packet, vis_info_len, &is_new);
 302         if (info == NULL)
 303                 goto end;
 304         /* note that outdated packets will be dropped at this point. */
 305
 306
 307         /* send only if we're the target server or ... */
 308         if (is_vis_server_locked() &&
 309             is_my_mac(info->packet.target_orig) &&
 310             is_new) {
 311                 info->packet.vis_type = VIS_TYPE_SERVER_SYNC;   /* upgrade! */
 312                 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 313                 if (list_empty(&info->send_list))
 314                         list_add_tail(&info->send_list, &send_list);
 315
 316                 /* ... we're not the recipient (and thus need to forward). */
 317         } else if (!is_my_mac(info->packet.target_orig)) {
 318                 if (list_empty(&info->send_list))
 319                         list_add_tail(&info->send_list, &send_list);
 320         }
 321 end:
 322         spin_unlock(&vis_hash_lock);
 323 }
 324
 325 /* Walk the originators and find the VIS server with the best tq. Set the packet
 326  * address to its address and return the best_tq.
 327  *
 328  * Must be called with the originator hash locked */
 329 static int find_best_vis_server(struct vis_info *info)
 330 {
 331         HASHIT(hashit);
 332         struct orig_node *orig_node;
 333         int best_tq = -1;
 334
 335         while (hash_iterate(orig_hash, &hashit)) {
 336                 orig_node = hashit.bucket->data;
 337                 if ((orig_node != NULL) &&
 338                     (orig_node->router != NULL) &&
 339                     (orig_node->flags & VIS_SERVER) &&
 340                     (orig_node->router->tq_avg > best_tq)) {
 341                         best_tq = orig_node->router->tq_avg;
 342                         memcpy(info->packet.target_orig, orig_node->orig,
 343                                ETH_ALEN);
 344                 }
 345         }
 346         return best_tq;
 347 }
 348
 349 /* Return true if the vis packet is full. */
 350 static bool vis_packet_full(struct vis_info *info)
 351 {
 352         if (info->packet.entries + 1 >
 353             (1000 - sizeof(struct vis_info)) / sizeof(struct vis_info_entry))
 354                 return true;
 355         return false;
 356 }
 357
 358 /* generates a packet of own vis data,
 359  * returns 0 on success, -1 if no packet could be generated */
 360 static int generate_vis_packet(void)
 361 {
 362         HASHIT(hashit_local);
 363         HASHIT(hashit_global);
 364         struct orig_node *orig_node;
 365         struct vis_info *info = (struct vis_info *)my_vis_info;
 366         struct vis_info_entry *entry, *entry_array;
 367         struct hna_local_entry *hna_local_entry;
 368         int best_tq = -1;
 369         unsigned long flags;
 370
 371         info->first_seen = jiffies;
 372
 373         spin_lock(&orig_hash_lock);
 374         memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 375         info->packet.ttl = TTL;
 376         info->packet.seqno++;
 377         info->packet.entries = 0;
 378
 379         if (!is_vis_server_locked()) {
 380                 best_tq = find_best_vis_server(info);
 381                 if (best_tq < 0) {
 382                         spin_unlock(&orig_hash_lock);
 383                         return -1;
 384                 }
 385         }
 386
 387         entry_array = (struct vis_info_entry *)
 388                 ((char *)info + sizeof(struct vis_info));
 389
 390         while (hash_iterate(orig_hash, &hashit_global)) {
 391                 orig_node = hashit_global.bucket->data;
 392                 if (orig_node->router != NULL
 393                         && compare_orig(orig_node->router->addr, orig_node->orig)
 394                         && orig_node->batman_if
 395                         && (orig_node->batman_if->if_active == IF_ACTIVE)
 396                     && orig_node->router->tq_avg > 0) {
 397
 398                         /* fill one entry into buffer. */
 399                         entry = &entry_array[info->packet.entries];
 400                         memcpy(entry->src, orig_node->batman_if->net_dev->dev_addr, ETH_ALEN);
 401                         memcpy(entry->dest, orig_node->orig, ETH_ALEN);
 402                         entry->quality = orig_node->router->tq_avg;
 403                         info->packet.entries++;
 404
 405                         if (vis_packet_full(info)) {
 406                                 spin_unlock(&orig_hash_lock);
 407                                 return 0;
 408                         }
 409                 }
 410         }
 411
 412         spin_unlock(&orig_hash_lock);
 413
 414         spin_lock_irqsave(&hna_local_hash_lock, flags);
 415         while (hash_iterate(hna_local_hash, &hashit_local)) {
 416                 hna_local_entry = hashit_local.bucket->data;
 417                 entry = &entry_array[info->packet.entries];
 418                 memset(entry->src, 0, ETH_ALEN);
 419                 memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN);
 420                 entry->quality = 0; /* 0 means HNA */
 421                 info->packet.entries++;
 422
 423                 if (vis_packet_full(info)) {
 424                         spin_unlock_irqrestore(&hna_local_hash_lock, flags);
 425                         return 0;
 426                 }
 427         }
 428         spin_unlock_irqrestore(&hna_local_hash_lock, flags);
 429         return 0;
 430 }
 431
 432 static void purge_vis_packets(void)
 433 {
 434         HASHIT(hashit);
 435         struct vis_info *info;
 436
 437         while (hash_iterate(vis_hash, &hashit)) {
 438                 info = hashit.bucket->data;
 439                 if (info == my_vis_info)        /* never purge own data. */
 440                         continue;
 441                 if (time_after(jiffies,
 442                                info->first_seen + (VIS_TIMEOUT*HZ)/1000)) {
 443                         hash_remove_bucket(vis_hash, &hashit);
 444                         free_info(info);
 445                 }
 446         }
 447 }
 448
 449 static void broadcast_vis_packet(struct vis_info *info, int packet_length)
 450 {
 451         HASHIT(hashit);
 452         struct orig_node *orig_node;
 453
 454         spin_lock(&orig_hash_lock);
 455
 456         /* send to all routers in range. */
 457         while (hash_iterate(orig_hash, &hashit)) {
 458                 orig_node = hashit.bucket->data;
 459
 460                 /* if it's a vis server and reachable, send it. */
 461                 if (orig_node &&
 462                     (orig_node->flags & VIS_SERVER) &&
 463                     orig_node->batman_if &&
 464                     orig_node->router) {
 465
 466                         /* don't send it if we already received the packet from
 467                          * this node. */
 468                         if (recv_list_is_in(&info->recv_list, orig_node->orig))
 469                                 continue;
 470
 471                         memcpy(info->packet.target_orig,
 472                                orig_node->orig, ETH_ALEN);
 473
 474                         send_raw_packet((unsigned char *) &info->packet,
 475                                         packet_length,
 476                                         orig_node->batman_if,
 477                                         orig_node->router->addr);
 478                 }
 479         }
 480         memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 481         spin_unlock(&orig_hash_lock);
 482 }
 483
 484 static void unicast_vis_packet(struct vis_info *info, int packet_length)
 485 {
 486         struct orig_node *orig_node;
 487
 488         spin_lock(&orig_hash_lock);
 489         orig_node = ((struct orig_node *)
 490                      hash_find(orig_hash, info->packet.target_orig));
 491
 492         if ((orig_node != NULL) &&
 493             (orig_node->batman_if != NULL) &&
 494             (orig_node->router != NULL)) {
 495                 send_raw_packet((unsigned char *) &info->packet, packet_length,
 496                                 orig_node->batman_if,
 497                                 orig_node->router->addr);
 498         }
 499         spin_unlock(&orig_hash_lock);
 500 }
 501
 502 /* only send one vis packet. called from send_vis_packets() */
 503 static void send_vis_packet(struct vis_info *info)
 504 {
 505         int packet_length;
 506
 507         if (info->packet.ttl < 2) {
 508                 printk(KERN_WARNING "batman-adv: Error - can't send vis packet: ttl exceeded\n");
 509                 return;
 510         }
 511
 512         memcpy(info->packet.sender_orig, mainIfAddr, ETH_ALEN);
 513         info->packet.ttl--;
 514
 515         packet_length = sizeof(struct vis_packet) +
 516                 info->packet.entries * sizeof(struct vis_info_entry);
 517
 518         if (is_bcast(info->packet.target_orig))
 519                 broadcast_vis_packet(info, packet_length);
 520         else
 521                 unicast_vis_packet(info, packet_length);
 522         info->packet.ttl++; /* restore TTL */
 523 }
 524
 525 /* called from timer; send (and maybe generate) vis packet. */
 526 static void send_vis_packets(struct work_struct *work)
 527 {
 528         struct vis_info *info, *temp;
 529
 530         spin_lock(&vis_hash_lock);
 531         purge_vis_packets();
 532
 533         if (generate_vis_packet() == 0)
 534                 /* schedule if generation was successful */
 535                 list_add_tail(&my_vis_info->send_list, &send_list);
 536
 537         list_for_each_entry_safe(info, temp, &send_list, send_list) {
 538                 list_del_init(&info->send_list);
 539                 send_vis_packet(info);
 540         }
 541         spin_unlock(&vis_hash_lock);
 542         start_vis_timer();
 543 }
 544 static DECLARE_DELAYED_WORK(vis_timer_wq, send_vis_packets);
 545
 546 /* init the vis server. this may only be called when if_list is already
 547  * initialized (e.g. bat0 is initialized, interfaces have been added) */
 548 int vis_init(void)
 549 {
 550         if (vis_hash)
 551                 return 1;
 552
 553         spin_lock(&vis_hash_lock);
 554
 555         vis_hash = hash_new(256, vis_info_cmp, vis_info_choose);
 556         if (!vis_hash) {
 557                 printk(KERN_ERR "batman-adv:Can't initialize vis_hash\n");
 558                 goto err;
 559         }
 560
 561         my_vis_info = kmalloc(1000, GFP_ATOMIC);
 562         if (!my_vis_info) {
 563                 printk(KERN_ERR "batman-adv:Can't initialize vis packet\n");
 564                 goto err;
 565         }
 566
 567         /* prefill the vis info */
 568         my_vis_info->first_seen = jiffies - atomic_read(&vis_interval);
 569         INIT_LIST_HEAD(&my_vis_info->recv_list);
 570         INIT_LIST_HEAD(&my_vis_info->send_list);
 571         my_vis_info->packet.version = COMPAT_VERSION;
 572         my_vis_info->packet.packet_type = BAT_VIS;
 573         my_vis_info->packet.vis_type = VIS_TYPE_CLIENT_UPDATE;
 574         my_vis_info->packet.ttl = TTL;
 575         my_vis_info->packet.seqno = 0;
 576         my_vis_info->packet.entries = 0;
 577
 578         INIT_LIST_HEAD(&send_list);
 579
 580         memcpy(my_vis_info->packet.vis_orig, mainIfAddr, ETH_ALEN);
 581         memcpy(my_vis_info->packet.sender_orig, mainIfAddr, ETH_ALEN);
 582
 583         if (hash_add(vis_hash, my_vis_info) < 0) {
 584                 printk(KERN_ERR
 585                           "batman-adv:Can't add own vis packet into hash\n");
 586                 free_info(my_vis_info); /* not in hash, need to remove it
 587                                          * manually. */
 588                 goto err;
 589         }
 590
 591         spin_unlock(&vis_hash_lock);
 592         start_vis_timer();
 593         return 1;
 594
 595 err:
 596         spin_unlock(&vis_hash_lock);
 597         vis_quit();
 598         return 0;
 599 }
 600
 601 /* shutdown vis-server */
 602 void vis_quit(void)
 603 {
 604         if (!vis_hash)
 605                 return;
 606
 607         cancel_delayed_work_sync(&vis_timer_wq);
 608
 609         spin_lock(&vis_hash_lock);
 610         /* properly remove, kill timers ... */
 611         hash_delete(vis_hash, free_info);
 612         vis_hash = NULL;
 613         my_vis_info = NULL;
 614         spin_unlock(&vis_hash_lock);
 615 }
 616
 617 /* schedule packets for (re)transmission */
 618 static void start_vis_timer(void)
 619 {
 620         queue_delayed_work(bat_event_workqueue, &vis_timer_wq,
 621                            (atomic_read(&vis_interval) * HZ) / 1000);
 622 }
 623